util_hash.c revision 09361395363805b5892d48d7bc10cf717e4d2927
109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher/************************************************************************** 209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * 309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * Copyright 2007 VMware, Inc. 409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * All Rights Reserved. 509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * 609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * Permission is hereby granted, free of charge, to any person obtaining a 709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * copy of this software and associated documentation files (the 809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * "Software"), to deal in the Software without restriction, including 909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * without limitation the rights to use, copy, modify, merge, publish, 1009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * distribute, sub license, and/or sell copies of the Software, and to 1109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * permit persons to whom the Software is furnished to do so, subject to 1209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * the following conditions: 1309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * 1409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * The above copyright notice and this permission notice (including the 1509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * next paragraph) shall be included in all copies or substantial portions 1609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * of the Software. 1709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * 1809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 1909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 2009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. 2109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR 2209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 2309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 2409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 2509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * 2609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher **************************************************************************/ 2709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 2809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher /* 2909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * Authors: 3009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher * Zack Rusin <zackr@vmware.com> 3109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher */ 3209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 3309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher#include "util_hash.h" 3409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 3509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher#include <stdlib.h> 3609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher#include <assert.h> 3709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 3809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher#define MAX(a, b) ((a > b) ? (a) : (b)) 3909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 4009361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic const int MinNumBits = 4; 4109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 4209361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic const unsigned char prime_deltas[] = { 4309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 9, 25, 3, 4409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 1, 21, 3, 21, 7, 15, 9, 5, 3, 29, 15, 0, 0, 0, 0, 0 4509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher}; 4609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 4709361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic int primeForNumBits(int numBits) 4809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 4909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return (1 << numBits) + prime_deltas[numBits]; 5009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 5109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 5209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher/* Returns the smallest integer n such that 5309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher primeForNumBits(n) >= hint. 5409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher*/ 5509361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic int countBits(int hint) 5609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 5709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int numBits = 0; 5809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int bits = hint; 5909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 6009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (bits > 1) { 6109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher bits >>= 1; 6209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher numBits++; 6309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 6409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 6509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (numBits >= (int)sizeof(prime_deltas)) { 6609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher numBits = sizeof(prime_deltas) - 1; 6709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } else if (primeForNumBits(numBits) < hint) { 6809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher ++numBits; 6909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 7009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return numBits; 7109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 7209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 7309361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstruct util_node { 7409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *next; 7509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher unsigned key; 7609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher void *value; 7709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher}; 7809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 7909361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstruct util_hash_data { 8009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *fakeNext; 8109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **buckets; 8209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int size; 8309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int nodeSize; 8409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher short userNumBits; 8509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher short numBits; 8609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int numBuckets; 8709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher}; 8809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 8909361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstruct util_hash { 9009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher union { 9109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_hash_data *d; 9209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *e; 9309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } data; 9409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher}; 9509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 9609361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic void *util_data_allocate_node(struct util_hash_data *hash) 9709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 9809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return malloc(hash->nodeSize); 9909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 10009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 10109361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic void util_free_node(struct util_node *node) 10209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 10309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher free(node); 10409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 10509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 10609361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic struct util_node * 10709361395363805b5892d48d7bc10cf717e4d2927Alex Deucherutil_hash_create_node(struct util_hash *hash, 10809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher unsigned akey, void *avalue, 10909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **anextNode) 11009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 11109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *node = util_data_allocate_node(hash->data.d); 11209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 11309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (!node) 11409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return NULL; 11509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 11609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher node->key = akey; 11709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher node->value = avalue; 11809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 11909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher node->next = (struct util_node*)(*anextNode); 12009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher *anextNode = node; 12109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher ++hash->data.d->size; 12209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return node; 12309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 12409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 12509361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic void util_data_rehash(struct util_hash_data *hash, int hint) 12609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 12709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (hint < 0) { 12809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hint = countBits(-hint); 12909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (hint < MinNumBits) 13009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hint = MinNumBits; 13109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->userNumBits = (short)hint; 13209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (primeForNumBits(hint) < (hash->size >> 1)) 13309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher ++hint; 13409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } else if (hint < MinNumBits) { 13509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hint = MinNumBits; 13609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 13709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 13809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (hash->numBits != hint) { 13909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *e = (struct util_node *)(hash); 14009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **oldBuckets = hash->buckets; 14109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int oldNumBuckets = hash->numBuckets; 14209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int i = 0; 14309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 14409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->numBits = (short)hint; 14509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->numBuckets = primeForNumBits(hint); 14609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->buckets = malloc(sizeof(struct util_node*) * hash->numBuckets); 14709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher for (i = 0; i < hash->numBuckets; ++i) 14809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->buckets[i] = e; 14909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 15009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher for (i = 0; i < oldNumBuckets; ++i) { 15109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *firstNode = oldBuckets[i]; 15209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (firstNode != e) { 15309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher unsigned h = firstNode->key; 15409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *lastNode = firstNode; 15509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *afterLastNode; 15609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **beforeFirstNode; 15709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 15809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (lastNode->next != e && lastNode->next->key == h) 15909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher lastNode = lastNode->next; 16009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 16109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher afterLastNode = lastNode->next; 16209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher beforeFirstNode = &hash->buckets[h % hash->numBuckets]; 16309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (*beforeFirstNode != e) 16409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher beforeFirstNode = &(*beforeFirstNode)->next; 16509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher lastNode->next = *beforeFirstNode; 16609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher *beforeFirstNode = firstNode; 16709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher firstNode = afterLastNode; 16809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 16909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 17009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher free(oldBuckets); 17109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 17209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 17309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 17409361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic void util_data_might_grow(struct util_hash_data *hash) 17509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 17609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (hash->size >= hash->numBuckets) 17709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher util_data_rehash(hash, hash->numBits + 1); 17809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 17909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 18009361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic void util_data_has_shrunk(struct util_hash_data *hash) 18109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 18209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (hash->size <= (hash->numBuckets >> 3) && 18309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->numBits > hash->userNumBits) { 18409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int max = MAX(hash->numBits-2, hash->userNumBits); 18509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher util_data_rehash(hash, max); 18609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 18709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 18809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 18909361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic struct util_node *util_data_first_node(struct util_hash_data *hash) 19009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 19109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *e = (struct util_node *)(hash); 19209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **bucket = hash->buckets; 19309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int n = hash->numBuckets; 19409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (n--) { 19509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (*bucket != e) 19609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return *bucket; 19709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher ++bucket; 19809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 19909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return e; 20009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 20109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 20209361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic struct util_node **util_hash_find_node(struct util_hash *hash, unsigned akey) 20309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 20409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **node; 20509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 20609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (hash->data.d->numBuckets) { 20709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher node = (struct util_node **)(&hash->data.d->buckets[akey % hash->data.d->numBuckets]); 20809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher assert(*node == hash->data.e || (*node)->next); 20909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (*node != hash->data.e && (*node)->key != akey) 21009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher node = &(*node)->next; 21109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } else { 21209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher node = (struct util_node **)((const struct util_node * const *)(&hash->data.e)); 21309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 21409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return node; 21509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 21609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 21709361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstruct util_hash_iter util_hash_insert(struct util_hash *hash, 21809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher unsigned key, void *data) 21909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 22009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher util_data_might_grow(hash->data.d); 22109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 22209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher { 22309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **nextNode = util_hash_find_node(hash, key); 22409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *node = util_hash_create_node(hash, key, data, nextNode); 22509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (!node) { 22609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_hash_iter null_iter = {hash, 0}; 22709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return null_iter; 22809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 22909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 23009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher { 23109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_hash_iter iter = {hash, node}; 23209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return iter; 23309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 23409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 23509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 23609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 23709361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstruct util_hash * util_hash_create(void) 23809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 23909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_hash *hash = malloc(sizeof(struct util_hash)); 24009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (!hash) 24109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return NULL; 24209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 24309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->data.d = malloc(sizeof(struct util_hash_data)); 24409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (!hash->data.d) { 24509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher free(hash); 24609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return NULL; 24709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 24809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 24909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->data.d->fakeNext = 0; 25009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->data.d->buckets = 0; 25109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->data.d->size = 0; 25209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->data.d->nodeSize = sizeof(struct util_node); 25309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->data.d->userNumBits = (short)MinNumBits; 25409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->data.d->numBits = 0; 25509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->data.d->numBuckets = 0; 25609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 25709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return hash; 25809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 25909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 26009361395363805b5892d48d7bc10cf717e4d2927Alex Deuchervoid util_hash_delete(struct util_hash *hash) 26109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 26209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *e_for_x = (struct util_node *)(hash->data.d); 26309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **bucket = (struct util_node **)(hash->data.d->buckets); 26409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int n = hash->data.d->numBuckets; 26509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (n--) { 26609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *cur = *bucket++; 26709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (cur != e_for_x) { 26809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *next = cur->next; 26909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher util_free_node(cur); 27009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher cur = next; 27109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 27209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 27309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher free(hash->data.d->buckets); 27409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher free(hash->data.d); 27509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher free(hash); 27609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 27709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 27809361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstruct util_hash_iter util_hash_find(struct util_hash *hash, 27909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher unsigned key) 28009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 28109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **nextNode = util_hash_find_node(hash, key); 28209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_hash_iter iter = {hash, *nextNode}; 28309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return iter; 28409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 28509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 28609361395363805b5892d48d7bc10cf717e4d2927Alex Deucherunsigned util_hash_iter_key(struct util_hash_iter iter) 28709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 28809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (!iter.node || iter.hash->data.e == iter.node) 28909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return 0; 29009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return iter.node->key; 29109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 29209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 29309361395363805b5892d48d7bc10cf717e4d2927Alex Deuchervoid * util_hash_iter_data(struct util_hash_iter iter) 29409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 29509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (!iter.node || iter.hash->data.e == iter.node) 29609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return 0; 29709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return iter.node->value; 29809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 29909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 30009361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic struct util_node *util_hash_data_next(struct util_node *node) 30109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 30209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher union { 30309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *next; 30409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *e; 30509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_hash_data *d; 30609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } a; 30709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int start; 30809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **bucket; 30909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int n; 31009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 31109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher a.next = node->next; 31209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (!a.next) { 31309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher /* iterating beyond the last element */ 31409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return 0; 31509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 31609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (a.next->next) 31709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return a.next; 31809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 31909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher start = (node->key % a.d->numBuckets) + 1; 32009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher bucket = a.d->buckets + start; 32109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher n = a.d->numBuckets - start; 32209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (n--) { 32309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (*bucket != a.e) 32409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return *bucket; 32509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher ++bucket; 32609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 32709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return a.e; 32809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 32909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 33009361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstruct util_hash_iter util_hash_iter_next(struct util_hash_iter iter) 33109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 33209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_hash_iter next = {iter.hash, util_hash_data_next(iter.node)}; 33309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return next; 33409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 33509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 33609361395363805b5892d48d7bc10cf717e4d2927Alex Deucherint util_hash_iter_is_null(struct util_hash_iter iter) 33709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 33809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (!iter.node || iter.node == iter.hash->data.e) 33909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return 1; 34009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return 0; 34109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 34209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 34309361395363805b5892d48d7bc10cf717e4d2927Alex Deuchervoid * util_hash_take(struct util_hash *hash, 34409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher unsigned akey) 34509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 34609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **node = util_hash_find_node(hash, akey); 34709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (*node != hash->data.e) { 34809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher void *t = (*node)->value; 34909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *next = (*node)->next; 35009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher util_free_node(*node); 35109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher *node = next; 35209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher --hash->data.d->size; 35309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher util_data_has_shrunk(hash->data.d); 35409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return t; 35509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 35609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return 0; 35709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 35809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 35909361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstruct util_hash_iter util_hash_first_node(struct util_hash *hash) 36009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 36109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_hash_iter iter = {hash, util_data_first_node(hash->data.d)}; 36209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return iter; 36309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 36409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 36509361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstruct util_hash_iter util_hash_erase(struct util_hash *hash, struct util_hash_iter iter) 36609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 36709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_hash_iter ret = iter; 36809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *node = iter.node; 36909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **node_ptr; 37009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 37109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (node == hash->data.e) 37209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return iter; 37309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 37409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher ret = util_hash_iter_next(ret); 37509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher node_ptr = (struct util_node**)(&hash->data.d->buckets[node->key % hash->data.d->numBuckets]); 37609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (*node_ptr != node) 37709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher node_ptr = &(*node_ptr)->next; 37809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher *node_ptr = node->next; 37909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher util_free_node(node); 38009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher --hash->data.d->size; 38109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return ret; 38209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 383