1 /*
2 Copyright (c) 2003, 2021, Oracle and/or its affiliates.
3 All rights reserved. Use is subject to license terms.
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License, version 2.0,
7 as published by the Free Software Foundation.
8
9 This program is also distributed with certain software (including
10 but not limited to OpenSSL) that is licensed under separate terms,
11 as designated in a particular file or component or in included license
12 documentation. The authors of MySQL hereby grant you an additional
13 permission to link the program and your derivative works with the
14 separately licensed software that they have included with MySQL.
15
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License, version 2.0, for more details.
20
21 You should have received a copy of the GNU General Public License
22 along with this program; if not, write to the Free Software
23 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
24 */
25
26 #ifndef NdbLinHash_H
27 #define NdbLinHash_H
28
29 #include <ndb_types.h>
30
31 #define SEGMENTSIZE 64
32 #define SEGMENTLOGSIZE 6
33 #define DIRECTORYSIZE 64
34 #define DIRINDEX(adress) ((adress) >> SEGMENTLOGSIZE)
35 #define SEGINDEX(adress) ((adress) & (SEGMENTSIZE-1))
36
37 #if !defined(MAXLOADFCTR)
38 #define MAXLOADFCTR 2
39 #endif
40 #if !defined(MINLOADFCTR)
41 #define MINLOADFCTR (MAXLOADFCTR/2)
42 #endif
43
44 template<class C>
45 class NdbElement_t {
46 public:
47 NdbElement_t();
48 ~NdbElement_t();
49
50 Uint32 len;
51 Uint32 hash;
52 Uint32 localkey1;
53 Uint32 *str;
54 NdbElement_t<C> *next;
55 C* theData;
56 private:
57 NdbElement_t(const NdbElement_t<C> & aElement_t);
58 NdbElement_t & operator = (const NdbElement_t<C> & aElement_t);
59 };
60
61
62 template <class C>
63 class NdbLinHash {
64 public:
65 NdbLinHash();
66 ~NdbLinHash();
67 void createHashTable(void);
68 void releaseHashTable(void);
69
70 int insertKey(const char * str, Uint32 len, Uint32 lkey1, C* data);
71 C *deleteKey(const char * str, Uint32 len);
72
73 C* getData(const char *, Uint32);
74 Uint32* getKey(const char *, Uint32);
75
76 void shrinkTable(void);
77 void expandHashTable(void);
78
79 Uint32 Hash(const char *str, Uint32 len);
80 Uint32 Hash(Uint32 h);
81
82 NdbElement_t<C> * getNext(NdbElement_t<C> * curr);
83
84 private:
85 void getBucket(Uint32 hash, int * dirindex, int * segindex);
86
87 struct Segment_t {
88 NdbElement_t<C> * elements[SEGMENTSIZE];
89 };
90
91 Uint32 p; /*bucket to be split*/
92 Uint32 max; /*max is the upper bound*/
93 Int32 slack; /*number of insertions before splits*/
94 Segment_t * directory[DIRECTORYSIZE];
95
96 NdbLinHash(const NdbLinHash<C> & aLinHash);
97 NdbLinHash<C> & operator = (const NdbLinHash<C> & aLinHash);
98 };
99
100 // All template methods must be inline
101
102 template <class C>
103 inline
NdbLinHash()104 NdbLinHash<C>::NdbLinHash() {
105 }
106
107 template <class C>
108 inline
NdbLinHash(const NdbLinHash<C> & aLinHash)109 NdbLinHash<C>::NdbLinHash(const NdbLinHash<C>& aLinHash)
110 {
111 }
112
113 template <class C>
114 inline
~NdbLinHash()115 NdbLinHash<C>::~NdbLinHash()
116 {
117 }
118
119 template <class C>
120 inline
121 Uint32
Hash(const char * str,Uint32 len)122 NdbLinHash<C>::Hash( const char* str, Uint32 len )
123 {
124 Uint32 h = 0;
125 while(len >= 4){
126 h = (h << 5) + h + str[0];
127 h = (h << 5) + h + str[1];
128 h = (h << 5) + h + str[2];
129 h = (h << 5) + h + str[3];
130 len -= 4;
131 str += 4;
132 }
133
134 while(len > 0){
135 h = (h << 5) + h + *str++;
136 len--;
137 }
138 return h;
139 }
140
141 template <class C>
142 inline
143 Uint32
Hash(Uint32 h)144 NdbLinHash<C>::Hash( Uint32 h ){
145 return h;
146 }
147
148 template <class C>
149 inline
NdbElement_t()150 NdbElement_t<C>::NdbElement_t() :
151 len(0),
152 hash(0),
153 localkey1(0),
154 str(NULL),
155 next(NULL),
156 theData(NULL)
157 {
158 }
159
160 template <class C>
161 inline
~NdbElement_t()162 NdbElement_t<C>::~NdbElement_t()
163 {
164 delete []str;
165 }
166
167
168 /* Initialize the hashtable HASH_T */
169 template <class C>
170 inline
171 void
createHashTable()172 NdbLinHash<C>::createHashTable() {
173 p = 0;
174 max = SEGMENTSIZE - 1;
175 slack = SEGMENTSIZE * MAXLOADFCTR;
176 directory[0] = new Segment_t();
177 int i;
178
179 /* The first segment cleared before used */
180 for(i = 0; i < SEGMENTSIZE; i++ )
181 directory[0]->elements[i] = 0;
182
183 /* clear the rest of the directory */
184 for(i = 1; i < DIRECTORYSIZE; i++)
185 directory[i] = 0;
186 }
187
188 template <class C>
189 inline
190 void
getBucket(Uint32 hash,int * dir,int * seg)191 NdbLinHash<C>::getBucket(Uint32 hash, int * dir, int * seg){
192 Uint32 adress = hash & max;
193 if(adress < p)
194 adress = hash & (2 * max + 1);
195
196 * dir = DIRINDEX(adress);
197 * seg = SEGINDEX(adress);
198 }
199
200 template <class C>
201 inline
202 Int32
insertKey(const char * str,Uint32 len,Uint32 lkey1,C * data)203 NdbLinHash<C>::insertKey( const char* str, Uint32 len, Uint32 lkey1, C* data )
204 {
205 const Uint32 hash = Hash(str, len);
206 int dir, seg;
207 getBucket(hash, &dir, &seg);
208
209 NdbElement_t<C> **chainp = &directory[dir]->elements[seg];
210
211 /**
212 * Check if the string already are in the hash table
213 * chain=chainp will copy the contents of HASH_T into chain
214 */
215 NdbElement_t<C> * oldChain = 0;
216 NdbElement_t<C> * chain;
217 for(chain = *chainp; chain != 0; chain = chain->next){
218 if(chain->len == len && !memcmp(chain->str, str, len))
219 return -1; /* Element already exists */
220 else
221 oldChain = chain;
222 }
223
224 /* New entry */
225 chain = new NdbElement_t<C>();
226 chain->len = len;
227 chain->hash = hash;
228 chain->localkey1 = lkey1;
229 chain->next = 0;
230 chain->theData = data;
231 len++; // Null terminated
232 chain->str = new Uint32[((len + 3) >> 2)];
233 memcpy( &chain->str[0], str, len);
234 if (oldChain != 0)
235 oldChain->next = chain;
236 else
237 *chainp = chain;
238
239 #if 0
240 if(--(slack) < 0)
241 expandHashTable();
242 #endif
243
244 return chain->localkey1;
245 }
246
247
248 template <class C>
249 inline
250 Uint32*
getKey(const char * str,Uint32 len)251 NdbLinHash<C>::getKey( const char* str, Uint32 len )
252 {
253 const Uint32 tHash = Hash(str, len);
254 int dir, seg;
255 getBucket(tHash, &dir, &seg);
256
257 NdbElement_t<C> ** keyp = &directory[dir]->elements[seg];
258
259 /*Check if the string are in the hash table*/
260 for(NdbElement_t<C> * key = *keyp; key != 0; key = key->next ) {
261 if(key->len == len && !memcmp(key->str, str, len)) {
262 return &key->localkey1;
263 }
264 }
265 return NULL ; /* The key was not found */
266 }
267
268 template <class C>
269 inline
270 C*
getData(const char * str,Uint32 len)271 NdbLinHash<C>::getData( const char* str, Uint32 len ){
272
273 const Uint32 tHash = Hash(str, len);
274 int dir, seg;
275 getBucket(tHash, &dir, &seg);
276
277 NdbElement_t<C> ** keyp = &directory[dir]->elements[seg];
278
279 /*Check if the string are in the hash table*/
280 for(NdbElement_t<C> * key = *keyp; key != 0; key = key->next ) {
281 if(key->len == len && !memcmp(key->str, str, len)) {
282 return key->theData;
283 }
284 }
285 return NULL ; /* The key was not found */
286 }
287
288 template <class C>
289 inline
290 C *
deleteKey(const char * str,Uint32 len)291 NdbLinHash<C>::deleteKey ( const char* str, Uint32 len){
292 const Uint32 hash = Hash(str, len);
293 int dir, seg;
294 getBucket(hash, &dir, &seg);
295
296 NdbElement_t<C> *oldChain = 0;
297 NdbElement_t<C> **chainp = &directory[dir]->elements[seg];
298 for(NdbElement_t<C> * chain = *chainp; chain != 0; chain = chain->next){
299 if(chain->len == len && !memcmp(chain->str, str, len)){
300 C *data= chain->theData;
301 if (oldChain == 0) {
302 * chainp = chain->next;
303 } else {
304 oldChain->next = chain->next;
305 }
306 delete chain;
307 return data;
308 } else {
309 oldChain = chain;
310 }
311 }
312 return 0; /* Element doesn't exist */
313 }
314
315 template <class C>
316 inline
317 void
releaseHashTable(void)318 NdbLinHash<C>::releaseHashTable( void ){
319 NdbElement_t<C>* tNextElement;
320 NdbElement_t<C>* tElement;
321
322 //Traverse the whole directory structure
323 for(int countd = 0; countd < DIRECTORYSIZE;countd++ ){
324 if (directory[countd] != 0) {
325 //Traverse whole hashtable
326 for(int counts = 0; counts < SEGMENTSIZE; counts++ )
327 if (directory[countd]->elements[counts] != 0) {
328 tElement = directory[countd]->elements[counts];
329 //Delete all elements even those who is linked
330 do {
331 tNextElement = tElement->next;
332 delete tElement;
333 tElement = tNextElement;
334 } while (tNextElement != 0);
335 }
336 delete directory[countd];
337 }
338 }
339 }
340
341 template <class C>
342 inline
343 void
shrinkTable(void)344 NdbLinHash<C>::shrinkTable( void )
345 {
346 Segment_t *lastseg;
347 NdbElement_t<C> **chainp;
348 Uint32 oldlast = p + max;
349
350 if( oldlast == 0 )
351 return;
352
353 // Adjust the state variables.
354 if( p == 0 ) {
355 max >>= 1;
356 p = max;
357 }
358 else
359 --(p);
360
361 // Update slack after shrink.
362
363 slack -= MAXLOADFCTR;
364
365 // Insert the chain oldlast at the end of chain p.
366
367 chainp = &directory[DIRINDEX(p)]->elements[SEGINDEX(p)];
368 while( *chainp != 0 ) {
369 chainp = &((*chainp)->next);
370 lastseg = directory[DIRINDEX(oldlast)];
371 *chainp = lastseg->elements[SEGINDEX(oldlast)];
372
373 // If necessary free last segment.
374 if( SEGINDEX(oldlast) == 0)
375 delete lastseg;
376 }
377 }
378
379 template <class C>
380 inline
381 void
expandHashTable(void)382 NdbLinHash<C>::expandHashTable( void )
383 {
384
385 NdbElement_t<C> **oldbucketp, *chain, *headofold, *headofnew, *next;
386 Uint32 maxp = max + 1;
387 Uint32 newadress = maxp + p;
388
389
390 // Still room in the adress space?
391 if( newadress >= DIRECTORYSIZE * SEGMENTSIZE ) {
392 return;
393 }
394
395 // If necessary, create a new segment.
396 if( SEGINDEX(newadress) == 0 )
397 directory[DIRINDEX(newadress)] = new Segment_t();
398
399 // Locate the old (to be split) bucket.
400 oldbucketp = &directory[DIRINDEX(p)]->elements[SEGINDEX(p)];
401
402 // Adjust the state variables.
403 p++;
404 if( p > max ) {
405 max = 2 *max + 1;
406 p = 0;
407 }
408
409 // Update slack after expandation.
410 slack += MAXLOADFCTR;
411
412 // Relocate records to the new bucket.
413 headofold = 0;
414 headofnew = 0;
415
416 for( chain = *oldbucketp; chain != 0; chain = next ) {
417 next = chain->next;
418 if( chain->hash & maxp ) {
419 chain->next = headofnew;
420 headofnew = chain;
421 }
422 else {
423 chain->next = headofold;
424 headofold = chain;
425 }
426 }
427 *oldbucketp = headofold;
428 directory[DIRINDEX(newadress)]->elements[SEGINDEX(newadress)] = headofnew;
429 }
430
431 template <class C>
432 inline
433 NdbElement_t<C> *
getNext(NdbElement_t<C> * curr)434 NdbLinHash<C>::getNext(NdbElement_t<C> * curr){
435 if(curr != 0 && curr->next != 0)
436 return curr->next;
437
438 int dir = 0, seg = 0;
439 int counts;
440 if(curr != 0)
441 {
442 getBucket(curr->hash, &dir, &seg);
443 counts = seg + 1;
444 }
445 else
446 {
447 counts = 0;
448 }
449
450 for(int countd = dir; countd < DIRECTORYSIZE;countd++ ){
451 if (directory[countd] != 0) {
452 for(; counts < SEGMENTSIZE; counts++ ){
453 if (directory[countd]->elements[counts] != 0) {
454 return directory[countd]->elements[counts];
455 }
456 }
457 }
458 counts = 0;
459 }
460
461 return 0;
462 }
463
464 #endif
465