1 /**
2 * WinPR: Windows Portable Runtime
3 * System.Collections.Hashtable
4 *
5 * Copyright 2014 Marc-Andre Moreau <marcandre.moreau@gmail.com>
6 *
7 * Licensed under the Apache License, Version 2.0 (the "License");
8 * you may not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
18 */
19
20 #ifdef HAVE_CONFIG_H
21 #include "config.h"
22 #endif
23
24 #include <winpr/crt.h>
25
26 #include <winpr/collections.h>
27
28 /**
29 * This implementation is based on the public domain
30 * hash table implementation made by Keith Pomakis:
31 *
32 * http://www.pomakis.com/hashtable/hashtable.c
33 * http://www.pomakis.com/hashtable/hashtable.h
34 */
35
HashTable_PointerCompare(void * pointer1,void * pointer2)36 BOOL HashTable_PointerCompare(void* pointer1, void* pointer2)
37 {
38 return (pointer1 == pointer2);
39 }
40
HashTable_PointerHash(void * pointer)41 UINT32 HashTable_PointerHash(void* pointer)
42 {
43 return ((UINT32)(UINT_PTR)pointer) >> 4;
44 }
45
HashTable_StringCompare(void * string1,void * string2)46 BOOL HashTable_StringCompare(void* string1, void* string2)
47 {
48 if (!string1 || !string2)
49 return (string1 == string2);
50
51 return (strcmp((char*)string1, (char*)string2) == 0);
52 }
53
HashTable_StringHash(void * key)54 UINT32 HashTable_StringHash(void* key)
55 {
56 UINT32 c;
57 UINT32 hash = 5381;
58 BYTE* str = (BYTE*)key;
59
60 /* djb2 algorithm */
61 while ((c = *str++) != '\0')
62 hash = (hash * 33) + c;
63
64 return hash;
65 }
66
HashTable_StringClone(void * str)67 void* HashTable_StringClone(void* str)
68 {
69 return _strdup((char*)str);
70 }
71
HashTable_StringFree(void * str)72 void HashTable_StringFree(void* str)
73 {
74 free(str);
75 }
76
HashTable_IsProbablePrime(int oddNumber)77 static int HashTable_IsProbablePrime(int oddNumber)
78 {
79 int i;
80
81 for (i = 3; i < 51; i += 2)
82 {
83 if (oddNumber == i)
84 return 1;
85 else if (oddNumber % i == 0)
86 return 0;
87 }
88
89 return 1; /* maybe */
90 }
91
HashTable_CalculateIdealNumOfBuckets(wHashTable * table)92 static long HashTable_CalculateIdealNumOfBuckets(wHashTable* table)
93 {
94 int idealNumOfBuckets = table->numOfElements / ((int)table->idealRatio);
95
96 if (idealNumOfBuckets < 5)
97 idealNumOfBuckets = 5;
98 else
99 idealNumOfBuckets |= 0x01;
100
101 while (!HashTable_IsProbablePrime(idealNumOfBuckets))
102 idealNumOfBuckets += 2;
103
104 return idealNumOfBuckets;
105 }
106
HashTable_Rehash(wHashTable * table,int numOfBuckets)107 static void HashTable_Rehash(wHashTable* table, int numOfBuckets)
108 {
109 int index;
110 UINT32 hashValue;
111 wKeyValuePair* pair;
112 wKeyValuePair* nextPair;
113 wKeyValuePair** newBucketArray;
114
115 if (numOfBuckets == 0)
116 numOfBuckets = HashTable_CalculateIdealNumOfBuckets(table);
117
118 if (numOfBuckets == table->numOfBuckets)
119 return; /* already the right size! */
120
121 newBucketArray = (wKeyValuePair**)calloc(numOfBuckets, sizeof(wKeyValuePair*));
122
123 if (!newBucketArray)
124 {
125 /*
126 * Couldn't allocate memory for the new array.
127 * This isn't a fatal error; we just can't perform the rehash.
128 */
129 return;
130 }
131
132 for (index = 0; index < table->numOfBuckets; index++)
133 {
134 pair = table->bucketArray[index];
135
136 while (pair)
137 {
138 nextPair = pair->next;
139 hashValue = table->hash(pair->key) % numOfBuckets;
140 pair->next = newBucketArray[hashValue];
141 newBucketArray[hashValue] = pair;
142 pair = nextPair;
143 }
144 }
145
146 free(table->bucketArray);
147 table->bucketArray = newBucketArray;
148 table->numOfBuckets = numOfBuckets;
149 }
150
HashTable_Get(wHashTable * table,void * key)151 wKeyValuePair* HashTable_Get(wHashTable* table, void* key)
152 {
153 UINT32 hashValue;
154 wKeyValuePair* pair;
155 hashValue = table->hash(key) % table->numOfBuckets;
156 pair = table->bucketArray[hashValue];
157
158 while (pair && !table->keyCompare(key, pair->key))
159 pair = pair->next;
160
161 return pair;
162 }
163
164 /**
165 * C equivalent of the C# Hashtable Class:
166 * http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx
167 */
168
169 /**
170 * Properties
171 */
172
173 /**
174 * Gets the number of key/value pairs contained in the HashTable.
175 */
176
HashTable_Count(wHashTable * table)177 int HashTable_Count(wHashTable* table)
178 {
179 return table->numOfElements;
180 }
181
182 /**
183 * Methods
184 */
185
186 /**
187 * Adds an element with the specified key and value into the HashTable.
188 */
189
HashTable_Add(wHashTable * table,void * key,void * value)190 int HashTable_Add(wHashTable* table, void* key, void* value)
191 {
192 int status = 0;
193 UINT32 hashValue;
194 wKeyValuePair* pair;
195 wKeyValuePair* newPair;
196
197 if (!key || !value)
198 return -1;
199
200 if (table->keyClone)
201 {
202 key = table->keyClone(key);
203
204 if (!key)
205 return -1;
206 }
207
208 if (table->valueClone)
209 {
210 value = table->valueClone(value);
211
212 if (!value)
213 return -1;
214 }
215
216 if (table->synchronized)
217 EnterCriticalSection(&table->lock);
218
219 hashValue = table->hash(key) % table->numOfBuckets;
220 pair = table->bucketArray[hashValue];
221
222 while (pair && !table->keyCompare(key, pair->key))
223 pair = pair->next;
224
225 if (pair)
226 {
227 if (pair->key != key)
228 {
229 if (table->keyFree)
230 table->keyFree(pair->key);
231
232 pair->key = key;
233 }
234
235 if (pair->value != value)
236 {
237 if (table->valueFree)
238 table->valueFree(pair->value);
239
240 pair->value = value;
241 }
242 }
243 else
244 {
245 newPair = (wKeyValuePair*)malloc(sizeof(wKeyValuePair));
246
247 if (!newPair)
248 {
249 status = -1;
250 }
251 else
252 {
253 newPair->key = key;
254 newPair->value = value;
255 newPair->next = table->bucketArray[hashValue];
256 table->bucketArray[hashValue] = newPair;
257 table->numOfElements++;
258
259 if (table->upperRehashThreshold > table->idealRatio)
260 {
261 float elementToBucketRatio =
262 (float)table->numOfElements / (float)table->numOfBuckets;
263
264 if (elementToBucketRatio > table->upperRehashThreshold)
265 HashTable_Rehash(table, 0);
266 }
267 }
268 }
269
270 if (table->synchronized)
271 LeaveCriticalSection(&table->lock);
272
273 return status;
274 }
275
276 /**
277 * Removes the element with the specified key from the HashTable.
278 */
279
HashTable_Remove(wHashTable * table,void * key)280 BOOL HashTable_Remove(wHashTable* table, void* key)
281 {
282 UINT32 hashValue;
283 BOOL status = TRUE;
284 wKeyValuePair* pair = NULL;
285 wKeyValuePair* previousPair = NULL;
286
287 if (table->synchronized)
288 EnterCriticalSection(&table->lock);
289
290 hashValue = table->hash(key) % table->numOfBuckets;
291 pair = table->bucketArray[hashValue];
292
293 while (pair && !table->keyCompare(key, pair->key))
294 {
295 previousPair = pair;
296 pair = pair->next;
297 }
298
299 if (!pair)
300 {
301 status = FALSE;
302 }
303 else
304 {
305 if (table->keyFree)
306 table->keyFree(pair->key);
307
308 if (table->valueFree)
309 table->valueFree(pair->value);
310
311 if (previousPair)
312 previousPair->next = pair->next;
313 else
314 table->bucketArray[hashValue] = pair->next;
315
316 free(pair);
317 table->numOfElements--;
318
319 if (table->lowerRehashThreshold > 0.0)
320 {
321 float elementToBucketRatio = (float)table->numOfElements / (float)table->numOfBuckets;
322
323 if (elementToBucketRatio < table->lowerRehashThreshold)
324 HashTable_Rehash(table, 0);
325 }
326 }
327
328 if (table->synchronized)
329 LeaveCriticalSection(&table->lock);
330
331 return status;
332 }
333
334 /**
335 * Get an item value using key
336 */
337
HashTable_GetItemValue(wHashTable * table,void * key)338 void* HashTable_GetItemValue(wHashTable* table, void* key)
339 {
340 void* value = NULL;
341 wKeyValuePair* pair;
342
343 if (table->synchronized)
344 EnterCriticalSection(&table->lock);
345
346 pair = HashTable_Get(table, key);
347
348 if (pair)
349 value = pair->value;
350
351 if (table->synchronized)
352 LeaveCriticalSection(&table->lock);
353
354 return value;
355 }
356
357 /**
358 * Set an item value using key
359 */
360
HashTable_SetItemValue(wHashTable * table,void * key,void * value)361 BOOL HashTable_SetItemValue(wHashTable* table, void* key, void* value)
362 {
363 BOOL status = TRUE;
364 wKeyValuePair* pair;
365
366 if (table->valueClone && value)
367 {
368 value = table->valueClone(value);
369
370 if (!value)
371 return FALSE;
372 }
373
374 if (table->synchronized)
375 EnterCriticalSection(&table->lock);
376
377 pair = HashTable_Get(table, key);
378
379 if (!pair)
380 status = FALSE;
381 else
382 {
383 if (table->valueClone && table->valueFree)
384 table->valueFree(pair->value);
385
386 pair->value = value;
387 }
388
389 if (table->synchronized)
390 LeaveCriticalSection(&table->lock);
391
392 return status;
393 }
394
395 /**
396 * Removes all elements from the HashTable.
397 */
398
HashTable_Clear(wHashTable * table)399 void HashTable_Clear(wHashTable* table)
400 {
401 int index;
402 wKeyValuePair* pair;
403 wKeyValuePair* nextPair;
404
405 if (table->synchronized)
406 EnterCriticalSection(&table->lock);
407
408 for (index = 0; index < table->numOfBuckets; index++)
409 {
410 pair = table->bucketArray[index];
411
412 while (pair)
413 {
414 nextPair = pair->next;
415
416 if (table->keyFree)
417 table->keyFree(pair->key);
418
419 if (table->valueFree)
420 table->valueFree(pair->value);
421
422 free(pair);
423 pair = nextPair;
424 }
425
426 table->bucketArray[index] = NULL;
427 }
428
429 table->numOfElements = 0;
430 HashTable_Rehash(table, 5);
431
432 if (table->synchronized)
433 LeaveCriticalSection(&table->lock);
434 }
435
436 /**
437 * Gets the list of keys as an array
438 */
439
HashTable_GetKeys(wHashTable * table,ULONG_PTR ** ppKeys)440 int HashTable_GetKeys(wHashTable* table, ULONG_PTR** ppKeys)
441 {
442 int iKey;
443 int count;
444 int index;
445 ULONG_PTR* pKeys;
446 wKeyValuePair* pair;
447 wKeyValuePair* nextPair;
448
449 if (table->synchronized)
450 EnterCriticalSection(&table->lock);
451
452 iKey = 0;
453 count = table->numOfElements;
454 *ppKeys = NULL;
455
456 if (count < 1)
457 {
458 if (table->synchronized)
459 LeaveCriticalSection(&table->lock);
460
461 return 0;
462 }
463
464 pKeys = (ULONG_PTR*)calloc(count, sizeof(ULONG_PTR));
465
466 if (!pKeys)
467 {
468 if (table->synchronized)
469 LeaveCriticalSection(&table->lock);
470
471 return -1;
472 }
473
474 for (index = 0; index < table->numOfBuckets; index++)
475 {
476 pair = table->bucketArray[index];
477
478 while (pair)
479 {
480 nextPair = pair->next;
481 pKeys[iKey++] = (ULONG_PTR)pair->key;
482 pair = nextPair;
483 }
484 }
485
486 if (table->synchronized)
487 LeaveCriticalSection(&table->lock);
488
489 *ppKeys = pKeys;
490 return count;
491 }
492
493 /**
494 * Determines whether the HashTable contains a specific key.
495 */
496
HashTable_Contains(wHashTable * table,void * key)497 BOOL HashTable_Contains(wHashTable* table, void* key)
498 {
499 BOOL status;
500
501 if (table->synchronized)
502 EnterCriticalSection(&table->lock);
503
504 status = (HashTable_Get(table, key) != NULL) ? TRUE : FALSE;
505
506 if (table->synchronized)
507 LeaveCriticalSection(&table->lock);
508
509 return status;
510 }
511
512 /**
513 * Determines whether the HashTable contains a specific key.
514 */
515
HashTable_ContainsKey(wHashTable * table,void * key)516 BOOL HashTable_ContainsKey(wHashTable* table, void* key)
517 {
518 BOOL status;
519
520 if (table->synchronized)
521 EnterCriticalSection(&table->lock);
522
523 status = (HashTable_Get(table, key) != NULL) ? TRUE : FALSE;
524
525 if (table->synchronized)
526 LeaveCriticalSection(&table->lock);
527
528 return status;
529 }
530
531 /**
532 * Determines whether the HashTable contains a specific value.
533 */
534
HashTable_ContainsValue(wHashTable * table,void * value)535 BOOL HashTable_ContainsValue(wHashTable* table, void* value)
536 {
537 int index;
538 BOOL status = FALSE;
539 wKeyValuePair* pair;
540
541 if (table->synchronized)
542 EnterCriticalSection(&table->lock);
543
544 for (index = 0; index < table->numOfBuckets; index++)
545 {
546 pair = table->bucketArray[index];
547
548 while (pair)
549 {
550 if (table->valueCompare(value, pair->value))
551 {
552 status = TRUE;
553 break;
554 }
555
556 pair = pair->next;
557 }
558
559 if (status)
560 break;
561 }
562
563 if (table->synchronized)
564 LeaveCriticalSection(&table->lock);
565
566 return status;
567 }
568
569 /**
570 * Construction, Destruction
571 */
572
HashTable_New(BOOL synchronized)573 wHashTable* HashTable_New(BOOL synchronized)
574 {
575 wHashTable* table;
576 table = (wHashTable*)calloc(1, sizeof(wHashTable));
577
578 if (table)
579 {
580 table->synchronized = synchronized;
581 InitializeCriticalSectionAndSpinCount(&(table->lock), 4000);
582 table->numOfBuckets = 64;
583 table->numOfElements = 0;
584 table->bucketArray = (wKeyValuePair**)calloc(table->numOfBuckets, sizeof(wKeyValuePair*));
585
586 if (!table->bucketArray)
587 {
588 free(table);
589 return NULL;
590 }
591
592 table->idealRatio = 3.0;
593 table->lowerRehashThreshold = 0.0;
594 table->upperRehashThreshold = 15.0;
595 table->hash = HashTable_PointerHash;
596 table->keyCompare = HashTable_PointerCompare;
597 table->valueCompare = HashTable_PointerCompare;
598 table->keyClone = NULL;
599 table->valueClone = NULL;
600 table->keyFree = NULL;
601 table->valueFree = NULL;
602 }
603
604 return table;
605 }
606
HashTable_Free(wHashTable * table)607 void HashTable_Free(wHashTable* table)
608 {
609 int index;
610 wKeyValuePair* pair;
611 wKeyValuePair* nextPair;
612
613 if (table)
614 {
615 for (index = 0; index < table->numOfBuckets; index++)
616 {
617 pair = table->bucketArray[index];
618
619 while (pair)
620 {
621 nextPair = pair->next;
622
623 if (table->keyFree)
624 table->keyFree(pair->key);
625
626 if (table->valueFree)
627 table->valueFree(pair->value);
628
629 free(pair);
630 pair = nextPair;
631 }
632 }
633
634 DeleteCriticalSection(&(table->lock));
635 free(table->bucketArray);
636 free(table);
637 }
638 }
639