1 /*
2 * Copyright (c) 2022 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15 #include "selinux_map.h"
16 #include <stdlib.h>
17 #include <string.h>
18
19 static const int32_t MAX_BUCKET = 32;
20
GenerateHashCode(const char * key,uint32_t len)21 static int GenerateHashCode(const char *key, uint32_t len)
22 {
23 int code = 0;
24 for (size_t i = 0; i < len; i++) {
25 code += key[i] - 'A';
26 }
27 return code;
28 }
29
GroupNodeNodeCompare(const HashNode * node1,const HashNode * node2)30 static int GroupNodeNodeCompare(const HashNode *node1, const HashNode *node2)
31 {
32 ParamHashNode *groupNode1 = HASHMAP_ENTRY(node1, ParamHashNode, hashNode);
33 ParamHashNode *groupNode2 = HASHMAP_ENTRY(node2, ParamHashNode, hashNode);
34 return strcmp(groupNode1->name, groupNode2->name);
35 }
36
GroupNodeKeyCompare(const HashNode * node1,const char * key)37 static int GroupNodeKeyCompare(const HashNode *node1, const char *key)
38 {
39 ParamHashNode *groupNode1 = HASHMAP_ENTRY(node1, ParamHashNode, hashNode);
40 return strncmp(groupNode1->name, key, groupNode1->nameLen);
41 }
42
GroupNodeGetKeyHashCode(const char * key,uint32_t len)43 static int GroupNodeGetKeyHashCode(const char *key, uint32_t len)
44 {
45 return GenerateHashCode(key, len);
46 }
47
GroupNodeGetNodeHashCode(const HashNode * node)48 static int GroupNodeGetNodeHashCode(const HashNode *node)
49 {
50 ParamHashNode *groupNode = HASHMAP_ENTRY(node, ParamHashNode, hashNode);
51 return GenerateHashCode(groupNode->name, groupNode->nameLen);
52 }
53
GroupNodeFree(const HashNode * node)54 static void GroupNodeFree(const HashNode *node)
55 {
56 ParamHashNode *groupNode = HASHMAP_ENTRY(node, ParamHashNode, hashNode);
57 free(groupNode);
58 }
59
HashMapCreate(HashTab ** handle)60 int32_t HashMapCreate(HashTab **handle)
61 {
62 if (handle == NULL) {
63 return -1;
64 }
65
66 HashTab *tab = (HashTab *)calloc(1, sizeof(HashTab) + sizeof(HashNode *) * MAX_BUCKET);
67 if (tab == NULL) {
68 return -1;
69 }
70 *handle = tab;
71 return 0;
72 }
73
GetHashNodeByNode(HashNode * root,const HashNode * nodeKey)74 static HashNode *GetHashNodeByNode(HashNode *root, const HashNode *nodeKey)
75 {
76 while (root != NULL) {
77 int ret = GroupNodeNodeCompare(root, nodeKey);
78 if (ret == 0) {
79 return root;
80 }
81 root = root->next;
82 }
83 return NULL;
84 }
85
GetHashNodeByKey(HashNode * root,const char * key)86 static HashNode *GetHashNodeByKey(HashNode *root, const char *key)
87 {
88 while (root != NULL) {
89 int ret = GroupNodeKeyCompare(root, key);
90 if (ret == 0) {
91 return root;
92 }
93 root = root->next;
94 }
95 return NULL;
96 }
97
HashMapAdd(HashTab * handle,HashNode * node)98 int32_t HashMapAdd(HashTab *handle, HashNode *node)
99 {
100 if (handle == NULL || !(node != NULL && node->next == NULL)) {
101 return -1;
102 }
103 int hashCode = GroupNodeGetNodeHashCode(node);
104 hashCode = (hashCode < 0) ? -hashCode : hashCode;
105 hashCode = hashCode % MAX_BUCKET;
106
107 // check key exist
108 HashNode *tmp = GetHashNodeByNode(handle->buckets[hashCode], node);
109 if (tmp != NULL) {
110 return -1;
111 }
112 node->next = handle->buckets[hashCode];
113 handle->buckets[hashCode] = node;
114 return 0;
115 }
116
HashMapRemove(HashTab * handle,const char * key)117 void HashMapRemove(HashTab *handle, const char *key)
118 {
119 if (handle == NULL || key == NULL) {
120 return;
121 }
122 int hashCode = GroupNodeGetKeyHashCode(key, strlen(key));
123 hashCode = (hashCode < 0) ? -hashCode : hashCode;
124 hashCode = hashCode % MAX_BUCKET;
125
126 HashNode *node = handle->buckets[hashCode];
127 HashNode *preNode = node;
128 while (node != NULL) {
129 int ret = GroupNodeKeyCompare(node, key);
130 if (ret == 0) {
131 if (node == handle->buckets[hashCode]) {
132 handle->buckets[hashCode] = node->next;
133 } else {
134 preNode->next = node->next;
135 }
136 return;
137 }
138 preNode = node;
139 node = node->next;
140 }
141 }
142
HashMapGet(HashTab * handle,const char * key,uint32_t len)143 HashNode *HashMapGet(HashTab *handle, const char *key, uint32_t len)
144 {
145 int hashCode = GenerateHashCode(key, len);
146 hashCode = (hashCode < 0) ? -hashCode : hashCode;
147 hashCode = hashCode % MAX_BUCKET;
148
149 return GetHashNodeByKey(handle->buckets[hashCode], key);
150 }
151
HashListFree(HashNode * root)152 static void HashListFree(HashNode *root)
153 {
154 if (root == NULL) {
155 return;
156 }
157 HashNode *node = root;
158 while (node != NULL) {
159 HashNode *next = node->next;
160 GroupNodeFree(node);
161 node = next;
162 }
163 }
164
HashMapDestroy(HashTab * handle)165 void HashMapDestroy(HashTab *handle)
166 {
167 if (handle == NULL) {
168 return;
169 }
170 for (int i = 0; i < MAX_BUCKET; i++) {
171 HashListFree(handle->buckets[i]);
172 }
173 free(handle);
174 }
175
HashMapFind(HashTab * handle,int hashCode,const char * key)176 HashNode *HashMapFind(HashTab *handle, int hashCode, const char *key)
177 {
178 if (handle == NULL || key == NULL) {
179 return NULL;
180 }
181 return GetHashNodeByKey(handle->buckets[hashCode], key);
182 }