2 * Copyright (c) 1984 through 2008, William LeFebvre
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
8 * * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
11 * * Redistributions in binary form must reproduce the above
12 * copyright notice, this list of conditions and the following disclaimer
13 * in the documentation and/or other materials provided with the
16 * * Neither the name of William LeFebvre nor the names of other
17 * contributors may be used to endorse or promote products derived from
18 * this software without specific prior written permission.
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35 /* The file hash.c is generated from hash.m4c via the preprocessor M4 */
38 * Hash table functions: init, add, lookup, first, next, sizeinfo.
39 * This is a conventional "bucket hash". The key is hashed in to a number
40 * less than or equal to the number of buckets and the result is used
41 * to index in to the array of buckets. Each bucket is a linked list
42 * that contains all the key/value pairs which hashed to that index.
50 #define memzero(a, b) memset((a), 0, (b))
51 #else /* !STDC_HEADERS */
53 #define memzero(a, b) memset((a), 0, (b))
55 #define memcpy(a, b, c) bcopy((b), (a), (c))
56 #define memzero(a, b) bzero((a), (b))
57 #define memcmp(a, b, c) bcmp((a), (b), (c))
58 #endif /* HAVE_MEMCPY */
69 #endif /* !STDC_HEADERS */
71 /* After all that there are still some systems that don't have NULL defined */
107 if ((i/j)==floor(i/j))
124 string_hash(hash_table *ht, char *key)
131 while ((ch = (unsigned char)*key++) != '\0')
140 s = s + (ch << shifting);
145 return (s % ht->num_buckets);
148 void ll_init(llist *q)
155 llistitem *ll_newitem(int size)
160 qi = (llistitem *)malloc(sizeof(llistitem) + size);
161 qi->datum = ((void *)qi + sizeof(llistitem));
165 void ll_freeitem(llistitem *li)
171 void ll_add(llist *q, llistitem *new)
179 void ll_extract(llist *q, llistitem *qi, llistitem *last)
188 last->next = qi->next;
194 #define LL_FIRST(q) ((q)->head)
202 #define LL_NEXT(q, qi) ((qi) != NULL ? (qi)->next : NULL)
204 ll_next(llist *q, llistitem *qi)
207 return (qi != NULL ? qi->next : NULL);
210 #define LL_ISEMPTY(ll) ((ll)->count == 0)
212 ll_isempty(llist *ll)
215 return (ll->count == 0);
219 * hash_table *hash_create(int num)
221 * Creates a hash table structure with at least "num" buckets.
233 /* create the resultant structure */
234 result = (hash_table *)malloc(sizeof(hash_table));
236 /* adjust bucket count to be prime */
237 num = next_prime(num);
239 /* create the buckets */
240 bytes = sizeof(bucket_t) * num;
241 result->buckets = b = (bucket_t *)malloc(bytes);
242 result->num_buckets = num;
244 /* create each bucket as a linked list */
256 * unsigned int hash_count(hash_table *ht)
258 * Return total number of elements contained in hash table.
262 hash_count(hash_table *ht)
266 register int cnt = 0;
267 register bucket_t *bucket;
269 bucket = ht->buckets;
270 while (i++ < ht->num_buckets)
272 cnt += bucket->list.count;
280 * void hash_sizeinfo(unsigned int *sizes, int max, hash_table *ht)
282 * Fill in "sizes" with information about bucket lengths in hash
287 hash_sizeinfo(unsigned int *sizes, int max, hash_table *ht)
292 register bucket_t *bucket;
294 memzero(sizes, max * sizeof(unsigned int));
296 bucket = ht->buckets;
298 while (i++ < ht->num_buckets)
300 idx = bucket->list.count;
301 sizes[idx >= max ? max-1 : idx]++;
313 * void hash_add_uint(hash_table *ht, unsigned int key, void *value)
315 * Add an element to table "ht". The element is described by
316 * "key" and "value". Return NULL on success. If the key
317 * already exists in the table, then no action is taken and
318 * the data for the existing element is returned.
319 * Key type is unsigned int
323 hash_add_uint(hash_table *ht, unsigned int key, void *value)
334 /* allocate the space we will need */
335 newli = ll_newitem(sizeof(hash_item_uint));
336 hi = (hash_item_uint *)newli->datum;
338 /* fill in the values */
342 /* hash to the bucket */
343 bucket = &(ht->buckets[(key % ht->num_buckets)]);
345 /* walk the list to make sure we do not have a duplicate */
346 ll = &(bucket->list);
350 h = (hash_item_uint *)li->datum;
357 li = LL_NEXT(ll, li);
361 /* is there already one there? */
364 /* add the unique element to the buckets list */
365 ll_add(&(bucket->list), newli);
370 /* free the stuff we just allocated */
372 return ((hash_item_uint *)(li->datum))->value;
377 * void *hash_replace_uint(hash_table *ht, unsigned int key, void *value)
379 * Replace an existing value in the hash table with a new one and
380 * return the old value. If the key does not already exist in
381 * the hash table, add a new element and return NULL.
382 * Key type is unsigned int
386 hash_replace_uint(hash_table *ht, unsigned int key, void *value)
396 /* find the bucket */
397 bucket = &(ht->buckets[(key % ht->num_buckets)]);
399 /* walk the list until we find the existing item */
400 ll = &(bucket->list);
404 hi = (hash_item_uint *)li->datum;
408 /* found it: now replace the value with the new one */
413 li = LL_NEXT(ll, li);
416 /* if the element wasnt found, add it */
419 li = ll_newitem(sizeof(hash_item_uint));
420 hi = (hash_item_uint *)li->datum;
423 ll_add(&(bucket->list), li);
426 /* return the old value (so it can be freed) */
431 * void *hash_lookup_uint(hash_table *ht, unsigned int key)
433 * Look up "key" in "ht" and return the associated value. If "key"
434 * is not found, return NULL. Key type is unsigned int
438 hash_lookup_uint(hash_table *ht, unsigned int key)
449 if ((bucket = &(ht->buckets[(key % ht->num_buckets)])) != NULL)
451 ll = &(bucket->list);
455 h = (hash_item_uint *)li->datum;
462 li = LL_NEXT(ll, li);
469 * void *hash_remove_uint(hash_table *ht, unsigned int key)
471 * Remove the element associated with "key" from the hash table
472 * "ht". Return the value or NULL if the key was not found.
476 hash_remove_uint(hash_table *ht, unsigned int key)
488 if ((bucket = &(ht->buckets[(key % ht->num_buckets)])) != NULL)
490 ll = &(bucket->list);
495 hi = (hash_item_uint *)li->datum;
499 ll_extract(ll, li, lilast);
507 li = LL_NEXT(ll, li);
514 * hash_item_uint *hash_first_uint(hash_table *ht, hash_pos *pos)
516 * First function to call when iterating through all items in the hash
517 * table. Returns the first item in "ht" and initializes "*pos" to track
518 * the current position.
522 hash_first_uint(hash_table *ht, hash_pos *pos)
525 /* initialize pos for first item in first bucket */
526 pos->num_buckets = ht->num_buckets;
527 pos->hash_bucket = ht->buckets;
531 /* find the first non-empty bucket */
532 while(pos->hash_bucket->list.count == 0)
535 if (++pos->curr >= pos->num_buckets)
541 /* set and return the first item */
542 pos->ll_item = LL_FIRST(&(pos->hash_bucket->list));
543 return (hash_item_uint *)pos->ll_item->datum;
548 * hash_item_uint *hash_next_uint(hash_pos *pos)
550 * Return the next item in the hash table, using "pos" as a description
551 * of the present position in the hash table. "pos" also identifies the
552 * specific hash table. Return NULL if there are no more elements.
556 hash_next_uint(hash_pos *pos)
561 /* move item to last and check for NULL */
562 if ((pos->ll_last = pos->ll_item) == NULL)
564 /* are we really at the end of the hash table? */
565 if (pos->curr >= pos->num_buckets)
567 /* yes: return NULL */
570 /* no: regrab first item in current bucket list (might be NULL) */
571 li = LL_FIRST(&(pos->hash_bucket->list));
575 /* get the next item in the llist */
576 li = LL_NEXT(&(pos->hash_bucket->list), pos->ll_item);
579 /* if its NULL we have to find another bucket */
582 /* locate another bucket */
585 /* move to the next one */
587 if (++pos->curr >= pos->num_buckets)
589 /* at the end of the hash table */
594 /* get the first element (might be NULL) */
595 li = LL_FIRST(&(pos->hash_bucket->list));
598 /* li is the next element to dish out */
600 return (hash_item_uint *)li->datum;
604 * void *hash_remove_pos_uint(hash_pos *pos)
606 * Remove the hash table entry pointed to by position marker "pos".
607 * The data from the entry is returned upon success, otherwise NULL.
612 hash_remove_pos_uint(hash_pos *pos)
621 if (pos == NULL || pos->ll_last == pos->ll_item)
626 /* at this point pos contains the item to remove (ll_item)
627 and its predecesor (ll_last) */
628 /* extract the item from the llist */
630 ll_extract(&(pos->hash_bucket->list), li, pos->ll_last);
632 /* retain the data */
633 hi = (hash_item_uint *)li->datum;
636 /* free up the space */
641 /* back up to previous item */
642 /* its okay for ll_item to be null: hash_next will detect it */
643 pos->ll_item = pos->ll_last;
651 * void hash_add_pid(hash_table *ht, pid_t key, void *value)
653 * Add an element to table "ht". The element is described by
654 * "key" and "value". Return NULL on success. If the key
655 * already exists in the table, then no action is taken and
656 * the data for the existing element is returned.
661 hash_add_pid(hash_table *ht, pid_t key, void *value)
672 /* allocate the space we will need */
673 newli = ll_newitem(sizeof(hash_item_pid));
674 hi = (hash_item_pid *)newli->datum;
676 /* fill in the values */
680 /* hash to the bucket */
681 bucket = &(ht->buckets[(key % ht->num_buckets)]);
683 /* walk the list to make sure we do not have a duplicate */
684 ll = &(bucket->list);
688 h = (hash_item_pid *)li->datum;
695 li = LL_NEXT(ll, li);
699 /* is there already one there? */
702 /* add the unique element to the buckets list */
703 ll_add(&(bucket->list), newli);
708 /* free the stuff we just allocated */
710 return ((hash_item_pid *)(li->datum))->value;
715 * void *hash_replace_pid(hash_table *ht, pid_t key, void *value)
717 * Replace an existing value in the hash table with a new one and
718 * return the old value. If the key does not already exist in
719 * the hash table, add a new element and return NULL.
724 hash_replace_pid(hash_table *ht, pid_t key, void *value)
734 /* find the bucket */
735 bucket = &(ht->buckets[(key % ht->num_buckets)]);
737 /* walk the list until we find the existing item */
738 ll = &(bucket->list);
742 hi = (hash_item_pid *)li->datum;
746 /* found it: now replace the value with the new one */
751 li = LL_NEXT(ll, li);
754 /* if the element wasnt found, add it */
757 li = ll_newitem(sizeof(hash_item_pid));
758 hi = (hash_item_pid *)li->datum;
761 ll_add(&(bucket->list), li);
764 /* return the old value (so it can be freed) */
769 * void *hash_lookup_pid(hash_table *ht, pid_t key)
771 * Look up "key" in "ht" and return the associated value. If "key"
772 * is not found, return NULL. Key type is pid_t
776 hash_lookup_pid(hash_table *ht, pid_t key)
787 if ((bucket = &(ht->buckets[(key % ht->num_buckets)])) != NULL)
789 ll = &(bucket->list);
793 h = (hash_item_pid *)li->datum;
800 li = LL_NEXT(ll, li);
807 * void *hash_remove_pid(hash_table *ht, pid_t key)
809 * Remove the element associated with "key" from the hash table
810 * "ht". Return the value or NULL if the key was not found.
814 hash_remove_pid(hash_table *ht, pid_t key)
826 if ((bucket = &(ht->buckets[(key % ht->num_buckets)])) != NULL)
828 ll = &(bucket->list);
833 hi = (hash_item_pid *)li->datum;
837 ll_extract(ll, li, lilast);
845 li = LL_NEXT(ll, li);
852 * hash_item_pid *hash_first_pid(hash_table *ht, hash_pos *pos)
854 * First function to call when iterating through all items in the hash
855 * table. Returns the first item in "ht" and initializes "*pos" to track
856 * the current position.
860 hash_first_pid(hash_table *ht, hash_pos *pos)
863 /* initialize pos for first item in first bucket */
864 pos->num_buckets = ht->num_buckets;
865 pos->hash_bucket = ht->buckets;
869 /* find the first non-empty bucket */
870 while(pos->hash_bucket->list.count == 0)
873 if (++pos->curr >= pos->num_buckets)
879 /* set and return the first item */
880 pos->ll_item = LL_FIRST(&(pos->hash_bucket->list));
881 return (hash_item_pid *)pos->ll_item->datum;
886 * hash_item_pid *hash_next_pid(hash_pos *pos)
888 * Return the next item in the hash table, using "pos" as a description
889 * of the present position in the hash table. "pos" also identifies the
890 * specific hash table. Return NULL if there are no more elements.
894 hash_next_pid(hash_pos *pos)
899 /* move item to last and check for NULL */
900 if ((pos->ll_last = pos->ll_item) == NULL)
902 /* are we really at the end of the hash table? */
903 if (pos->curr >= pos->num_buckets)
905 /* yes: return NULL */
908 /* no: regrab first item in current bucket list (might be NULL) */
909 li = LL_FIRST(&(pos->hash_bucket->list));
913 /* get the next item in the llist */
914 li = LL_NEXT(&(pos->hash_bucket->list), pos->ll_item);
917 /* if its NULL we have to find another bucket */
920 /* locate another bucket */
923 /* move to the next one */
925 if (++pos->curr >= pos->num_buckets)
927 /* at the end of the hash table */
932 /* get the first element (might be NULL) */
933 li = LL_FIRST(&(pos->hash_bucket->list));
936 /* li is the next element to dish out */
938 return (hash_item_pid *)li->datum;
942 * void *hash_remove_pos_pid(hash_pos *pos)
944 * Remove the hash table entry pointed to by position marker "pos".
945 * The data from the entry is returned upon success, otherwise NULL.
950 hash_remove_pos_pid(hash_pos *pos)
959 if (pos == NULL || pos->ll_last == pos->ll_item)
964 /* at this point pos contains the item to remove (ll_item)
965 and its predecesor (ll_last) */
966 /* extract the item from the llist */
968 ll_extract(&(pos->hash_bucket->list), li, pos->ll_last);
970 /* retain the data */
971 hi = (hash_item_pid *)li->datum;
974 /* free up the space */
979 /* back up to previous item */
980 /* its okay for ll_item to be null: hash_next will detect it */
981 pos->ll_item = pos->ll_last;
989 * void hash_add_string(hash_table *ht, char * key, void *value)
991 * Add an element to table "ht". The element is described by
992 * "key" and "value". Return NULL on success. If the key
993 * already exists in the table, then no action is taken and
994 * the data for the existing element is returned.
999 hash_add_string(hash_table *ht, char * key, void *value)
1003 hash_item_string *hi;
1004 hash_item_string *h;
1010 /* allocate the space we will need */
1011 newli = ll_newitem(sizeof(hash_item_string));
1012 hi = (hash_item_string *)newli->datum;
1014 /* fill in the values */
1015 hi->key = strdup(key);
1018 /* hash to the bucket */
1019 bucket = &(ht->buckets[string_hash(ht, key)]);
1021 /* walk the list to make sure we do not have a duplicate */
1022 ll = &(bucket->list);
1026 h = (hash_item_string *)li->datum;
1028 if (strcmp(key, k1) == 0)
1033 li = LL_NEXT(ll, li);
1037 /* is there already one there? */
1040 /* add the unique element to the buckets list */
1041 ll_add(&(bucket->list), newli);
1046 /* free the stuff we just allocated */
1048 return ((hash_item_string *)(li->datum))->value;
1053 * void *hash_replace_string(hash_table *ht, char * key, void *value)
1055 * Replace an existing value in the hash table with a new one and
1056 * return the old value. If the key does not already exist in
1057 * the hash table, add a new element and return NULL.
1058 * Key type is char *
1062 hash_replace_string(hash_table *ht, char * key, void *value)
1066 hash_item_string *hi;
1069 void *result = NULL;
1072 /* find the bucket */
1073 bucket = &(ht->buckets[string_hash(ht, key)]);
1075 /* walk the list until we find the existing item */
1076 ll = &(bucket->list);
1080 hi = (hash_item_string *)li->datum;
1082 if (strcmp(key, k1) == 0)
1084 /* found it: now replace the value with the new one */
1089 li = LL_NEXT(ll, li);
1092 /* if the element wasnt found, add it */
1095 li = ll_newitem(sizeof(hash_item_string));
1096 hi = (hash_item_string *)li->datum;
1097 hi->key = strdup(key);
1099 ll_add(&(bucket->list), li);
1102 /* return the old value (so it can be freed) */
1107 * void *hash_lookup_string(hash_table *ht, char * key)
1109 * Look up "key" in "ht" and return the associated value. If "key"
1110 * is not found, return NULL. Key type is char *
1114 hash_lookup_string(hash_table *ht, char * key)
1120 hash_item_string *h;
1125 if ((bucket = &(ht->buckets[string_hash(ht, key)])) != NULL)
1127 ll = &(bucket->list);
1131 h = (hash_item_string *)li->datum;
1133 if (strcmp(key, k1) == 0)
1138 li = LL_NEXT(ll, li);
1145 * void *hash_remove_string(hash_table *ht, char * key)
1147 * Remove the element associated with "key" from the hash table
1148 * "ht". Return the value or NULL if the key was not found.
1152 hash_remove_string(hash_table *ht, char * key)
1159 hash_item_string *hi;
1164 if ((bucket = &(ht->buckets[string_hash(ht, key)])) != NULL)
1166 ll = &(bucket->list);
1171 hi = (hash_item_string *)li->datum;
1173 if (strcmp(key, k1) == 0)
1175 ll_extract(ll, li, lilast);
1183 li = LL_NEXT(ll, li);
1190 * hash_item_string *hash_first_string(hash_table *ht, hash_pos *pos)
1192 * First function to call when iterating through all items in the hash
1193 * table. Returns the first item in "ht" and initializes "*pos" to track
1194 * the current position.
1198 hash_first_string(hash_table *ht, hash_pos *pos)
1201 /* initialize pos for first item in first bucket */
1202 pos->num_buckets = ht->num_buckets;
1203 pos->hash_bucket = ht->buckets;
1205 pos->ll_last = NULL;
1207 /* find the first non-empty bucket */
1208 while(pos->hash_bucket->list.count == 0)
1211 if (++pos->curr >= pos->num_buckets)
1217 /* set and return the first item */
1218 pos->ll_item = LL_FIRST(&(pos->hash_bucket->list));
1219 return (hash_item_string *)pos->ll_item->datum;
1224 * hash_item_string *hash_next_string(hash_pos *pos)
1226 * Return the next item in the hash table, using "pos" as a description
1227 * of the present position in the hash table. "pos" also identifies the
1228 * specific hash table. Return NULL if there are no more elements.
1232 hash_next_string(hash_pos *pos)
1237 /* move item to last and check for NULL */
1238 if ((pos->ll_last = pos->ll_item) == NULL)
1240 /* are we really at the end of the hash table? */
1241 if (pos->curr >= pos->num_buckets)
1243 /* yes: return NULL */
1246 /* no: regrab first item in current bucket list (might be NULL) */
1247 li = LL_FIRST(&(pos->hash_bucket->list));
1251 /* get the next item in the llist */
1252 li = LL_NEXT(&(pos->hash_bucket->list), pos->ll_item);
1255 /* if its NULL we have to find another bucket */
1258 /* locate another bucket */
1259 pos->ll_last = NULL;
1261 /* move to the next one */
1263 if (++pos->curr >= pos->num_buckets)
1265 /* at the end of the hash table */
1266 pos->ll_item = NULL;
1270 /* get the first element (might be NULL) */
1271 li = LL_FIRST(&(pos->hash_bucket->list));
1274 /* li is the next element to dish out */
1276 return (hash_item_string *)li->datum;
1280 * void *hash_remove_pos_string(hash_pos *pos)
1282 * Remove the hash table entry pointed to by position marker "pos".
1283 * The data from the entry is returned upon success, otherwise NULL.
1288 hash_remove_pos_string(hash_pos *pos)
1293 hash_item_string *hi;
1297 if (pos == NULL || pos->ll_last == pos->ll_item)
1302 /* at this point pos contains the item to remove (ll_item)
1303 and its predecesor (ll_last) */
1304 /* extract the item from the llist */
1306 ll_extract(&(pos->hash_bucket->list), li, pos->ll_last);
1308 /* retain the data */
1309 hi = (hash_item_string *)li->datum;
1312 /* free up the space */
1317 /* back up to previous item */
1318 /* its okay for ll_item to be null: hash_next will detect it */
1319 pos->ll_item = pos->ll_last;
1327 * void hash_add_pidthr(hash_table *ht, pidthr_t key, void *value)
1329 * Add an element to table "ht". The element is described by
1330 * "key" and "value". Return NULL on success. If the key
1331 * already exists in the table, then no action is taken and
1332 * the data for the existing element is returned.
1333 * Key type is pidthr_t
1337 hash_add_pidthr(hash_table *ht, pidthr_t key, void *value)
1341 hash_item_pidthr *hi;
1342 hash_item_pidthr *h;
1348 /* allocate the space we will need */
1349 newli = ll_newitem(sizeof(hash_item_pidthr));
1350 hi = (hash_item_pidthr *)newli->datum;
1352 /* fill in the values */
1356 /* hash to the bucket */
1357 bucket = &(ht->buckets[((key.k_thr * 10000 + key.k_pid) % ht->num_buckets)]);
1359 /* walk the list to make sure we do not have a duplicate */
1360 ll = &(bucket->list);
1364 h = (hash_item_pidthr *)li->datum;
1366 if ((key.k_pid == k1.k_pid && key.k_thr == k1.k_thr))
1371 li = LL_NEXT(ll, li);
1375 /* is there already one there? */
1378 /* add the unique element to the buckets list */
1379 ll_add(&(bucket->list), newli);
1384 /* free the stuff we just allocated */
1386 return ((hash_item_pidthr *)(li->datum))->value;
1391 * void *hash_replace_pidthr(hash_table *ht, pidthr_t key, void *value)
1393 * Replace an existing value in the hash table with a new one and
1394 * return the old value. If the key does not already exist in
1395 * the hash table, add a new element and return NULL.
1396 * Key type is pidthr_t
1400 hash_replace_pidthr(hash_table *ht, pidthr_t key, void *value)
1404 hash_item_pidthr *hi;
1407 void *result = NULL;
1410 /* find the bucket */
1411 bucket = &(ht->buckets[((key.k_thr * 10000 + key.k_pid) % ht->num_buckets)]);
1413 /* walk the list until we find the existing item */
1414 ll = &(bucket->list);
1418 hi = (hash_item_pidthr *)li->datum;
1420 if ((key.k_pid == k1.k_pid && key.k_thr == k1.k_thr))
1422 /* found it: now replace the value with the new one */
1427 li = LL_NEXT(ll, li);
1430 /* if the element wasnt found, add it */
1433 li = ll_newitem(sizeof(hash_item_pidthr));
1434 hi = (hash_item_pidthr *)li->datum;
1437 ll_add(&(bucket->list), li);
1440 /* return the old value (so it can be freed) */
1445 * void *hash_lookup_pidthr(hash_table *ht, pidthr_t key)
1447 * Look up "key" in "ht" and return the associated value. If "key"
1448 * is not found, return NULL. Key type is pidthr_t
1452 hash_lookup_pidthr(hash_table *ht, pidthr_t key)
1458 hash_item_pidthr *h;
1463 if ((bucket = &(ht->buckets[((key.k_thr * 10000 + key.k_pid) % ht->num_buckets)])) != NULL)
1465 ll = &(bucket->list);
1469 h = (hash_item_pidthr *)li->datum;
1471 if ((key.k_pid == k1.k_pid && key.k_thr == k1.k_thr))
1476 li = LL_NEXT(ll, li);
1483 * void *hash_remove_pidthr(hash_table *ht, pidthr_t key)
1485 * Remove the element associated with "key" from the hash table
1486 * "ht". Return the value or NULL if the key was not found.
1490 hash_remove_pidthr(hash_table *ht, pidthr_t key)
1497 hash_item_pidthr *hi;
1502 if ((bucket = &(ht->buckets[((key.k_thr * 10000 + key.k_pid) % ht->num_buckets)])) != NULL)
1504 ll = &(bucket->list);
1509 hi = (hash_item_pidthr *)li->datum;
1511 if ((key.k_pid == k1.k_pid && key.k_thr == k1.k_thr))
1513 ll_extract(ll, li, lilast);
1521 li = LL_NEXT(ll, li);
1528 * hash_item_pidthr *hash_first_pidthr(hash_table *ht, hash_pos *pos)
1530 * First function to call when iterating through all items in the hash
1531 * table. Returns the first item in "ht" and initializes "*pos" to track
1532 * the current position.
1536 hash_first_pidthr(hash_table *ht, hash_pos *pos)
1539 /* initialize pos for first item in first bucket */
1540 pos->num_buckets = ht->num_buckets;
1541 pos->hash_bucket = ht->buckets;
1543 pos->ll_last = NULL;
1545 /* find the first non-empty bucket */
1546 while(pos->hash_bucket->list.count == 0)
1549 if (++pos->curr >= pos->num_buckets)
1555 /* set and return the first item */
1556 pos->ll_item = LL_FIRST(&(pos->hash_bucket->list));
1557 return (hash_item_pidthr *)pos->ll_item->datum;
1562 * hash_item_pidthr *hash_next_pidthr(hash_pos *pos)
1564 * Return the next item in the hash table, using "pos" as a description
1565 * of the present position in the hash table. "pos" also identifies the
1566 * specific hash table. Return NULL if there are no more elements.
1570 hash_next_pidthr(hash_pos *pos)
1575 /* move item to last and check for NULL */
1576 if ((pos->ll_last = pos->ll_item) == NULL)
1578 /* are we really at the end of the hash table? */
1579 if (pos->curr >= pos->num_buckets)
1581 /* yes: return NULL */
1584 /* no: regrab first item in current bucket list (might be NULL) */
1585 li = LL_FIRST(&(pos->hash_bucket->list));
1589 /* get the next item in the llist */
1590 li = LL_NEXT(&(pos->hash_bucket->list), pos->ll_item);
1593 /* if its NULL we have to find another bucket */
1596 /* locate another bucket */
1597 pos->ll_last = NULL;
1599 /* move to the next one */
1601 if (++pos->curr >= pos->num_buckets)
1603 /* at the end of the hash table */
1604 pos->ll_item = NULL;
1608 /* get the first element (might be NULL) */
1609 li = LL_FIRST(&(pos->hash_bucket->list));
1612 /* li is the next element to dish out */
1614 return (hash_item_pidthr *)li->datum;
1618 * void *hash_remove_pos_pidthr(hash_pos *pos)
1620 * Remove the hash table entry pointed to by position marker "pos".
1621 * The data from the entry is returned upon success, otherwise NULL.
1626 hash_remove_pos_pidthr(hash_pos *pos)
1631 hash_item_pidthr *hi;
1635 if (pos == NULL || pos->ll_last == pos->ll_item)
1640 /* at this point pos contains the item to remove (ll_item)
1641 and its predecesor (ll_last) */
1642 /* extract the item from the llist */
1644 ll_extract(&(pos->hash_bucket->list), li, pos->ll_last);
1646 /* retain the data */
1647 hi = (hash_item_pidthr *)li->datum;
1650 /* free up the space */
1655 /* back up to previous item */
1656 /* its okay for ll_item to be null: hash_next will detect it */
1657 pos->ll_item = pos->ll_last;
1666 * void hash_add_lwpid(hash_table *ht, lwpid_t key, void *value)
1668 * Add an element to table "ht". The element is described by
1669 * "key" and "value". Return NULL on success. If the key
1670 * already exists in the table, then no action is taken and
1671 * the data for the existing element is returned.
1672 * Key type is lwpid_t
1676 hash_add_lwpid(hash_table *ht, lwpid_t key, void *value)
1680 hash_item_lwpid *hi;
1687 /* allocate the space we will need */
1688 newli = ll_newitem(sizeof(hash_item_lwpid));
1689 hi = (hash_item_lwpid *)newli->datum;
1691 /* fill in the values */
1695 /* hash to the bucket */
1696 bucket = &(ht->buckets[(key % ht->num_buckets)]);
1698 /* walk the list to make sure we do not have a duplicate */
1699 ll = &(bucket->list);
1703 h = (hash_item_lwpid *)li->datum;
1710 li = LL_NEXT(ll, li);
1714 /* is there already one there? */
1717 /* add the unique element to the buckets list */
1718 ll_add(&(bucket->list), newli);
1723 /* free the stuff we just allocated */
1725 return ((hash_item_lwpid *)(li->datum))->value;
1730 * void *hash_replace_lwpid(hash_table *ht, lwpid_t key, void *value)
1732 * Replace an existing value in the hash table with a new one and
1733 * return the old value. If the key does not already exist in
1734 * the hash table, add a new element and return NULL.
1735 * Key type is lwpid_t
1739 hash_replace_lwpid(hash_table *ht, lwpid_t key, void *value)
1743 hash_item_lwpid *hi;
1746 void *result = NULL;
1749 /* find the bucket */
1750 bucket = &(ht->buckets[(key % ht->num_buckets)]);
1752 /* walk the list until we find the existing item */
1753 ll = &(bucket->list);
1757 hi = (hash_item_lwpid *)li->datum;
1761 /* found it: now replace the value with the new one */
1766 li = LL_NEXT(ll, li);
1769 /* if the element wasnt found, add it */
1772 li = ll_newitem(sizeof(hash_item_lwpid));
1773 hi = (hash_item_lwpid *)li->datum;
1776 ll_add(&(bucket->list), li);
1779 /* return the old value (so it can be freed) */
1784 * void *hash_lookup_lwpid(hash_table *ht, lwpid_t key)
1786 * Look up "key" in "ht" and return the associated value. If "key"
1787 * is not found, return NULL. Key type is lwpid_t
1791 hash_lookup_lwpid(hash_table *ht, lwpid_t key)
1802 if ((bucket = &(ht->buckets[(key % ht->num_buckets)])) != NULL)
1804 ll = &(bucket->list);
1808 h = (hash_item_lwpid *)li->datum;
1815 li = LL_NEXT(ll, li);
1822 * void *hash_remove_lwpid(hash_table *ht, lwpid_t key)
1824 * Remove the element associated with "key" from the hash table
1825 * "ht". Return the value or NULL if the key was not found.
1829 hash_remove_lwpid(hash_table *ht, lwpid_t key)
1836 hash_item_lwpid *hi;
1841 if ((bucket = &(ht->buckets[(key % ht->num_buckets)])) != NULL)
1843 ll = &(bucket->list);
1848 hi = (hash_item_lwpid *)li->datum;
1852 ll_extract(ll, li, lilast);
1860 li = LL_NEXT(ll, li);
1867 * hash_item_lwpid *hash_first_lwpid(hash_table *ht, hash_pos *pos)
1869 * First function to call when iterating through all items in the hash
1870 * table. Returns the first item in "ht" and initializes "*pos" to track
1871 * the current position.
1875 hash_first_lwpid(hash_table *ht, hash_pos *pos)
1878 /* initialize pos for first item in first bucket */
1879 pos->num_buckets = ht->num_buckets;
1880 pos->hash_bucket = ht->buckets;
1882 pos->ll_last = NULL;
1884 /* find the first non-empty bucket */
1885 while(pos->hash_bucket->list.count == 0)
1888 if (++pos->curr >= pos->num_buckets)
1894 /* set and return the first item */
1895 pos->ll_item = LL_FIRST(&(pos->hash_bucket->list));
1896 return (hash_item_lwpid *)pos->ll_item->datum;
1901 * hash_item_lwpid *hash_next_lwpid(hash_pos *pos)
1903 * Return the next item in the hash table, using "pos" as a description
1904 * of the present position in the hash table. "pos" also identifies the
1905 * specific hash table. Return NULL if there are no more elements.
1909 hash_next_lwpid(hash_pos *pos)
1914 /* move item to last and check for NULL */
1915 if ((pos->ll_last = pos->ll_item) == NULL)
1917 /* are we really at the end of the hash table? */
1918 if (pos->curr >= pos->num_buckets)
1920 /* yes: return NULL */
1923 /* no: regrab first item in current bucket list (might be NULL) */
1924 li = LL_FIRST(&(pos->hash_bucket->list));
1928 /* get the next item in the llist */
1929 li = LL_NEXT(&(pos->hash_bucket->list), pos->ll_item);
1932 /* if its NULL we have to find another bucket */
1935 /* locate another bucket */
1936 pos->ll_last = NULL;
1938 /* move to the next one */
1940 if (++pos->curr >= pos->num_buckets)
1942 /* at the end of the hash table */
1943 pos->ll_item = NULL;
1947 /* get the first element (might be NULL) */
1948 li = LL_FIRST(&(pos->hash_bucket->list));
1951 /* li is the next element to dish out */
1953 return (hash_item_lwpid *)li->datum;
1957 * void *hash_remove_pos_lwpid(hash_pos *pos)
1959 * Remove the hash table entry pointed to by position marker "pos".
1960 * The data from the entry is returned upon success, otherwise NULL.
1965 hash_remove_pos_lwpid(hash_pos *pos)
1970 hash_item_lwpid *hi;
1974 if (pos == NULL || pos->ll_last == pos->ll_item)
1979 /* at this point pos contains the item to remove (ll_item)
1980 and its predecesor (ll_last) */
1981 /* extract the item from the llist */
1983 ll_extract(&(pos->hash_bucket->list), li, pos->ll_last);
1985 /* retain the data */
1986 hi = (hash_item_lwpid *)li->datum;
1989 /* free up the space */
1994 /* back up to previous item */
1995 /* its okay for ll_item to be null: hash_next will detect it */
1996 pos->ll_item = pos->ll_last;