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 33f4c2bfd63e55b9c878f4c1420af15a88c57b43a2Emil Velikov#ifdef HAVE_CONFIG_H 34f4c2bfd63e55b9c878f4c1420af15a88c57b43a2Emil Velikov#include "config.h" 35f4c2bfd63e55b9c878f4c1420af15a88c57b43a2Emil Velikov#endif 36f4c2bfd63e55b9c878f4c1420af15a88c57b43a2Emil Velikov 3709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher#include "util_hash.h" 3809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 3909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher#include <stdlib.h> 4009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher#include <assert.h> 4109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 4209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher#define MAX(a, b) ((a > b) ? (a) : (b)) 4309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 4409361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic const int MinNumBits = 4; 4509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 4609361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic const unsigned char prime_deltas[] = { 4709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 9, 25, 3, 4809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 1, 21, 3, 21, 7, 15, 9, 5, 3, 29, 15, 0, 0, 0, 0, 0 4909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher}; 5009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 5109361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic int primeForNumBits(int numBits) 5209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 5309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return (1 << numBits) + prime_deltas[numBits]; 5409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 5509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 5609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher/* Returns the smallest integer n such that 5709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher primeForNumBits(n) >= hint. 5809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher*/ 5909361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic int countBits(int hint) 6009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 6109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int numBits = 0; 6209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int bits = hint; 6309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 6409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (bits > 1) { 6509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher bits >>= 1; 6609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher numBits++; 6709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 6809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 6909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (numBits >= (int)sizeof(prime_deltas)) { 7009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher numBits = sizeof(prime_deltas) - 1; 7109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } else if (primeForNumBits(numBits) < hint) { 7209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher ++numBits; 7309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 7409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return numBits; 7509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 7609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 7709361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstruct util_node { 7809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *next; 7909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher unsigned key; 8009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher void *value; 8109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher}; 8209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 8309361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstruct util_hash_data { 8409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *fakeNext; 8509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **buckets; 8609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int size; 8709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int nodeSize; 8809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher short userNumBits; 8909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher short numBits; 9009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int numBuckets; 9109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher}; 9209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 9309361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstruct util_hash { 9409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher union { 9509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_hash_data *d; 9609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *e; 9709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } data; 9809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher}; 9909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 10009361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic void *util_data_allocate_node(struct util_hash_data *hash) 10109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 10209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return malloc(hash->nodeSize); 10309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 10409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 10509361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic void util_free_node(struct util_node *node) 10609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 10709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher free(node); 10809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 10909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 11009361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic struct util_node * 11109361395363805b5892d48d7bc10cf717e4d2927Alex Deucherutil_hash_create_node(struct util_hash *hash, 11209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher unsigned akey, void *avalue, 11309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **anextNode) 11409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 11509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *node = util_data_allocate_node(hash->data.d); 11609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 11709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (!node) 11809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return NULL; 11909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 12009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher node->key = akey; 12109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher node->value = avalue; 12209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 12309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher node->next = (struct util_node*)(*anextNode); 12409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher *anextNode = node; 12509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher ++hash->data.d->size; 12609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return node; 12709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 12809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 12909361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic void util_data_rehash(struct util_hash_data *hash, int hint) 13009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 13109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (hint < 0) { 13209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hint = countBits(-hint); 13309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (hint < MinNumBits) 13409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hint = MinNumBits; 13509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->userNumBits = (short)hint; 13609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (primeForNumBits(hint) < (hash->size >> 1)) 13709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher ++hint; 13809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } else if (hint < MinNumBits) { 13909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hint = MinNumBits; 14009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 14109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 14209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (hash->numBits != hint) { 14309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *e = (struct util_node *)(hash); 14409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **oldBuckets = hash->buckets; 14509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int oldNumBuckets = hash->numBuckets; 14609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int i = 0; 14709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 14809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->numBits = (short)hint; 14909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->numBuckets = primeForNumBits(hint); 15009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->buckets = malloc(sizeof(struct util_node*) * hash->numBuckets); 15109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher for (i = 0; i < hash->numBuckets; ++i) 15209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->buckets[i] = e; 15309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 15409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher for (i = 0; i < oldNumBuckets; ++i) { 15509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *firstNode = oldBuckets[i]; 15609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (firstNode != e) { 15709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher unsigned h = firstNode->key; 15809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *lastNode = firstNode; 15909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *afterLastNode; 16009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **beforeFirstNode; 16109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 16209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (lastNode->next != e && lastNode->next->key == h) 16309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher lastNode = lastNode->next; 16409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 16509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher afterLastNode = lastNode->next; 16609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher beforeFirstNode = &hash->buckets[h % hash->numBuckets]; 16709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (*beforeFirstNode != e) 16809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher beforeFirstNode = &(*beforeFirstNode)->next; 16909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher lastNode->next = *beforeFirstNode; 17009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher *beforeFirstNode = firstNode; 17109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher firstNode = afterLastNode; 17209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 17309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 17409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher free(oldBuckets); 17509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 17609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 17709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 17809361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic void util_data_might_grow(struct util_hash_data *hash) 17909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 18009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (hash->size >= hash->numBuckets) 18109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher util_data_rehash(hash, hash->numBits + 1); 18209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 18309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 18409361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic void util_data_has_shrunk(struct util_hash_data *hash) 18509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 18609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (hash->size <= (hash->numBuckets >> 3) && 18709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->numBits > hash->userNumBits) { 18809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int max = MAX(hash->numBits-2, hash->userNumBits); 18909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher util_data_rehash(hash, max); 19009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 19109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 19209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 19309361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic struct util_node *util_data_first_node(struct util_hash_data *hash) 19409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 19509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *e = (struct util_node *)(hash); 19609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **bucket = hash->buckets; 19709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int n = hash->numBuckets; 19809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (n--) { 19909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (*bucket != e) 20009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return *bucket; 20109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher ++bucket; 20209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 20309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return e; 20409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 20509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 20609361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic struct util_node **util_hash_find_node(struct util_hash *hash, unsigned akey) 20709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 20809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **node; 20909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 21009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (hash->data.d->numBuckets) { 21109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher node = (struct util_node **)(&hash->data.d->buckets[akey % hash->data.d->numBuckets]); 21209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher assert(*node == hash->data.e || (*node)->next); 21309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (*node != hash->data.e && (*node)->key != akey) 21409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher node = &(*node)->next; 21509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } else { 21609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher node = (struct util_node **)((const struct util_node * const *)(&hash->data.e)); 21709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 21809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return node; 21909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 22009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 2215f0f6387a6abe9e20c94d99a1e59aa7fa231b17aEmil Velikovdrm_private struct util_hash_iter 2225f0f6387a6abe9e20c94d99a1e59aa7fa231b17aEmil Velikovutil_hash_insert(struct util_hash *hash, unsigned key, void *data) 22309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 22409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher util_data_might_grow(hash->data.d); 22509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 22609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher { 22709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **nextNode = util_hash_find_node(hash, key); 22809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *node = util_hash_create_node(hash, key, data, nextNode); 22909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (!node) { 23009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_hash_iter null_iter = {hash, 0}; 23109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return null_iter; 23209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 23309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 23409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher { 23509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_hash_iter iter = {hash, node}; 23609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return iter; 23709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 23809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 23909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 24009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 2415f0f6387a6abe9e20c94d99a1e59aa7fa231b17aEmil Velikovdrm_private struct util_hash *util_hash_create(void) 24209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 24309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_hash *hash = malloc(sizeof(struct util_hash)); 24409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (!hash) 24509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return NULL; 24609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 24709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->data.d = malloc(sizeof(struct util_hash_data)); 24809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (!hash->data.d) { 24909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher free(hash); 25009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return NULL; 25109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 25209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 25309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->data.d->fakeNext = 0; 25409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->data.d->buckets = 0; 25509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->data.d->size = 0; 25609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->data.d->nodeSize = sizeof(struct util_node); 25709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->data.d->userNumBits = (short)MinNumBits; 25809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->data.d->numBits = 0; 25909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher hash->data.d->numBuckets = 0; 26009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 26109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return hash; 26209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 26309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 2645f0f6387a6abe9e20c94d99a1e59aa7fa231b17aEmil Velikovdrm_private void util_hash_delete(struct util_hash *hash) 26509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 26609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *e_for_x = (struct util_node *)(hash->data.d); 26709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **bucket = (struct util_node **)(hash->data.d->buckets); 26809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int n = hash->data.d->numBuckets; 26909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (n--) { 27009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *cur = *bucket++; 27109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (cur != e_for_x) { 27209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *next = cur->next; 27309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher util_free_node(cur); 27409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher cur = next; 27509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 27609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 27709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher free(hash->data.d->buckets); 27809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher free(hash->data.d); 27909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher free(hash); 28009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 28109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 2825f0f6387a6abe9e20c94d99a1e59aa7fa231b17aEmil Velikovdrm_private struct util_hash_iter 2835f0f6387a6abe9e20c94d99a1e59aa7fa231b17aEmil Velikovutil_hash_find(struct util_hash *hash, unsigned key) 28409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 28509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **nextNode = util_hash_find_node(hash, key); 28609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_hash_iter iter = {hash, *nextNode}; 28709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return iter; 28809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 28909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 2905f0f6387a6abe9e20c94d99a1e59aa7fa231b17aEmil Velikovdrm_private unsigned util_hash_iter_key(struct util_hash_iter iter) 29109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 29209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (!iter.node || iter.hash->data.e == iter.node) 29309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return 0; 29409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return iter.node->key; 29509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 29609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 2975f0f6387a6abe9e20c94d99a1e59aa7fa231b17aEmil Velikovdrm_private void *util_hash_iter_data(struct util_hash_iter iter) 29809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 29909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (!iter.node || iter.hash->data.e == iter.node) 30009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return 0; 30109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return iter.node->value; 30209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 30309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 30409361395363805b5892d48d7bc10cf717e4d2927Alex Deucherstatic struct util_node *util_hash_data_next(struct util_node *node) 30509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 30609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher union { 30709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *next; 30809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *e; 30909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_hash_data *d; 31009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } a; 31109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int start; 31209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **bucket; 31309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher int n; 31409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 31509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher a.next = node->next; 31609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (!a.next) { 31709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher /* iterating beyond the last element */ 31809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return 0; 31909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 32009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (a.next->next) 32109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return a.next; 32209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 32309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher start = (node->key % a.d->numBuckets) + 1; 32409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher bucket = a.d->buckets + start; 32509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher n = a.d->numBuckets - start; 32609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (n--) { 32709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (*bucket != a.e) 32809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return *bucket; 32909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher ++bucket; 33009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 33109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return a.e; 33209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 33309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 3345f0f6387a6abe9e20c94d99a1e59aa7fa231b17aEmil Velikovdrm_private struct util_hash_iter 3355f0f6387a6abe9e20c94d99a1e59aa7fa231b17aEmil Velikovutil_hash_iter_next(struct util_hash_iter iter) 33609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 33709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_hash_iter next = {iter.hash, util_hash_data_next(iter.node)}; 33809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return next; 33909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 34009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 3415f0f6387a6abe9e20c94d99a1e59aa7fa231b17aEmil Velikovdrm_private int util_hash_iter_is_null(struct util_hash_iter iter) 34209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 34309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (!iter.node || iter.node == iter.hash->data.e) 34409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return 1; 34509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return 0; 34609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 34709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 3485f0f6387a6abe9e20c94d99a1e59aa7fa231b17aEmil Velikovdrm_private void *util_hash_take(struct util_hash *hash, unsigned akey) 34909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 35009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **node = util_hash_find_node(hash, akey); 35109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (*node != hash->data.e) { 35209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher void *t = (*node)->value; 35309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *next = (*node)->next; 35409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher util_free_node(*node); 35509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher *node = next; 35609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher --hash->data.d->size; 35709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher util_data_has_shrunk(hash->data.d); 35809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return t; 35909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher } 36009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return 0; 36109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 36209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 3635f0f6387a6abe9e20c94d99a1e59aa7fa231b17aEmil Velikovdrm_private struct util_hash_iter util_hash_first_node(struct util_hash *hash) 36409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 36509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_hash_iter iter = {hash, util_data_first_node(hash->data.d)}; 36609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return iter; 36709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 36809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 3695f0f6387a6abe9e20c94d99a1e59aa7fa231b17aEmil Velikovdrm_private struct util_hash_iter 3705f0f6387a6abe9e20c94d99a1e59aa7fa231b17aEmil Velikovutil_hash_erase(struct util_hash *hash, struct util_hash_iter iter) 37109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher{ 37209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_hash_iter ret = iter; 37309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node *node = iter.node; 37409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher struct util_node **node_ptr; 37509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 37609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher if (node == hash->data.e) 37709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return iter; 37809361395363805b5892d48d7bc10cf717e4d2927Alex Deucher 37909361395363805b5892d48d7bc10cf717e4d2927Alex Deucher ret = util_hash_iter_next(ret); 38009361395363805b5892d48d7bc10cf717e4d2927Alex Deucher node_ptr = (struct util_node**)(&hash->data.d->buckets[node->key % hash->data.d->numBuckets]); 38109361395363805b5892d48d7bc10cf717e4d2927Alex Deucher while (*node_ptr != node) 38209361395363805b5892d48d7bc10cf717e4d2927Alex Deucher node_ptr = &(*node_ptr)->next; 38309361395363805b5892d48d7bc10cf717e4d2927Alex Deucher *node_ptr = node->next; 38409361395363805b5892d48d7bc10cf717e4d2927Alex Deucher util_free_node(node); 38509361395363805b5892d48d7bc10cf717e4d2927Alex Deucher --hash->data.d->size; 38609361395363805b5892d48d7bc10cf717e4d2927Alex Deucher return ret; 38709361395363805b5892d48d7bc10cf717e4d2927Alex Deucher} 388