1 /*
2 * Copyright (C) 2021-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
16 #include "hash_table.h"
17 #include <stdlib.h>
18 #include "common.h"
19 #include "log.h"
20
21 #undef LOG_TAG
22 #define LOG_TAG "WifiRpcHashTable"
23
24 const int START_PRIME_NUM = 3;
25 const int START_CALC_PRIME_NUM = 2;
26
CalcHash(const HashTable * p,int element)27 static int CalcHash(const HashTable *p, int element)
28 {
29 return element % (p->slots);
30 }
31
32 /* Search for the first prime number greater than or equal to the integer i */
CalcNextPrime(int i)33 static int CalcNextPrime(int i)
34 {
35 if (i <= START_PRIME_NUM) {
36 return START_PRIME_NUM;
37 }
38 while (1) {
39 int j = START_CALC_PRIME_NUM;
40 int k = i / START_CALC_PRIME_NUM;
41 for (; j <= k; ++j) {
42 if (i % j == 0) {
43 break;
44 }
45 }
46 if (j > k) {
47 return i;
48 } else {
49 ++i;
50 }
51 }
52 }
53
InitHashTable(int slots)54 HashTable *InitHashTable(int slots)
55 {
56 HashTable *p = (HashTable *)calloc(1, sizeof(HashTable));
57 if (p == NULL) {
58 return NULL;
59 }
60 p->slots = CalcNextPrime(slots);
61 p->list = (ListNode **)calloc(p->slots, sizeof(ListNode *));
62 if (p->list == NULL) {
63 free(p);
64 return NULL;
65 }
66 return p;
67 }
68
DestroyHashTable(HashTable * p)69 void DestroyHashTable(HashTable *p)
70 {
71 int i = 0;
72 int nCount = p->slots;
73 for (; i < nCount; ++i) {
74 ListNode *t = p->list[i];
75 while (t != NULL) {
76 ListNode *next = t->next;
77 ReleaseContext(t->context);
78 free(t);
79 t = next;
80 }
81 }
82 free(p->list);
83 free(p);
84 p = NULL;
85 }
86
RebuildHashTable(HashTable * p)87 static int RebuildHashTable(HashTable *p)
88 {
89 if (p == NULL) {
90 return -1;
91 }
92 int slot = (p->slots << 1); /* double size */
93 slot = CalcNextPrime(slot);
94 if (slot <= 0) {
95 return -1;
96 }
97 ListNode **new_list = (ListNode **)calloc(slot, sizeof(ListNode *));
98 if (new_list == NULL) {
99 LOGE("rebuild hash table calloc failed!");
100 return -1;
101 }
102 int orgSlot = p->slots;
103 p->slots = slot;
104 for (int i = 0; i < orgSlot; ++i) {
105 ListNode *t = p->list[i];
106 while (t != NULL) {
107 ListNode *q = t->next;
108 int pos = CalcHash(p, t->context->fd);
109 t->next = new_list[pos];
110 new_list[pos] = t;
111 t = q;
112 }
113 }
114 free(p->list);
115 p->list = new_list;
116 return 0;
117 }
118
FindContext(HashTable * p,int fd)119 Context *FindContext(HashTable *p, int fd)
120 {
121 if (p == NULL) {
122 return NULL;
123 }
124
125 int slot = CalcHash(p, fd);
126 ListNode *t = p->list[slot];
127 while (t != NULL) {
128 if (t->context->fd == fd) {
129 break;
130 } else {
131 t = t->next;
132 }
133 }
134 return (t == NULL) ? NULL : t->context;
135 }
136
InsertHashTable(HashTable * p,Context * context)137 int InsertHashTable(HashTable *p, Context *context)
138 {
139 if ((p == NULL) || (context == NULL)) {
140 return -1;
141 }
142
143 int slot = CalcHash(p, context->fd);
144 ListNode *t = p->list[slot];
145 ListNode *q = t;
146 while (t != NULL && t->context->fd != context->fd) {
147 q = t;
148 t = t->next;
149 }
150 if (t == NULL) {
151 ListNode *n = (ListNode *)calloc(1, sizeof(ListNode));
152 if (n == NULL) {
153 LOGE("insert element calloc failed!");
154 return -1;
155 }
156 n->context = context;
157 n->next = NULL;
158 if (q == NULL) {
159 p->list[slot] = n;
160 } else {
161 q->next = n;
162 }
163 p->size += 1;
164 int count = p->slots << 1;
165 if (p->size > count) {
166 return RebuildHashTable(p);
167 }
168 } else {
169 return INSERT_HASH_DUPLICATE; /* fd is duplicate */
170 }
171 return 0;
172 }
173
DeleteHashTable(HashTable * p,const Context * context)174 void DeleteHashTable(HashTable *p, const Context *context)
175 {
176 if ((p == NULL) || (context == NULL)) {
177 return;
178 }
179
180 int slot = CalcHash(p, context->fd);
181 ListNode *t = p->list[slot];
182 ListNode *q = t;
183 while (t != NULL && t->context->fd != context->fd) {
184 q = t;
185 t = t->next;
186 }
187 if (t != NULL) {
188 if (t == p->list[slot]) {
189 p->list[slot] = t->next;
190 } else {
191 q->next = t->next;
192 }
193 free(t);
194 t = NULL;
195 p->size -= 1;
196 }
197 return;
198 }
199