1e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin/************************************************************************** 2e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * 3e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * Copyright 2007 Tungsten Graphics, Inc., Cedar Park, Texas. 4e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * All Rights Reserved. 5e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * 6e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * Permission is hereby granted, free of charge, to any person obtaining a 7e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * copy of this software and associated documentation files (the 8e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * "Software"), to deal in the Software without restriction, including 9e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * without limitation the rights to use, copy, modify, merge, publish, 10e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * distribute, sub license, and/or sell copies of the Software, and to 11e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * permit persons to whom the Software is furnished to do so, subject to 12e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * the following conditions: 13e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * 14e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * The above copyright notice and this permission notice (including the 15e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * next paragraph) shall be included in all copies or substantial portions 16e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * of the Software. 17e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * 18e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 19e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 20e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. 21e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * IN NO EVENT SHALL TUNGSTEN GRAPHICS AND/OR ITS SUPPLIERS BE LIABLE FOR 22e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 23e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 24e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 25e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * 26e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin **************************************************************************/ 27e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 28e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin /* 29e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * Authors: 30e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin * Zack Rusin <zack@tungstengraphics.com> 31e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin */ 32e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 33ea4bf267e4b023b08043f91ac44592fed1736e7fJosé Fonseca#include "util/u_debug.h" 344f25420bdd834e81a3e22733304efc5261c2998aBrian Paul#include "util/u_memory.h" 35e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 362a0675eb75b8ca52efab739218bf93922bf884b5José Fonseca#include "cso_hash.h" 37e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 38e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin#define MAX(a, b) ((a > b) ? (a) : (b)) 39e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 40e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstatic const int MinNumBits = 4; 41e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 42e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstatic const unsigned char prime_deltas[] = { 43e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 9, 25, 3, 44e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 1, 21, 3, 21, 7, 15, 9, 5, 3, 29, 15, 0, 0, 0, 0, 0 45e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin}; 46e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 47e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstatic int primeForNumBits(int numBits) 48e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 49e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return (1 << numBits) + prime_deltas[numBits]; 50e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 51e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 52e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin/* 53e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin Returns the smallest integer n such that 54e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin primeForNumBits(n) >= hint. 55e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin*/ 56e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstatic int countBits(int hint) 57e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 58e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin int numBits = 0; 59e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin int bits = hint; 60e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 61e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin while (bits > 1) { 62e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin bits >>= 1; 63e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin numBits++; 64e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } 65e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 66e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin if (numBits >= (int)sizeof(prime_deltas)) { 67e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin numBits = sizeof(prime_deltas) - 1; 68e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } else if (primeForNumBits(numBits) < hint) { 69e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin ++numBits; 70e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } 71e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return numBits; 72e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 73e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 74e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstruct cso_node { 75e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node *next; 76e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin unsigned key; 77e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin void *value; 78e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin}; 79e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 80e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstruct cso_hash_data { 81e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node *fakeNext; 82e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node **buckets; 83e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin int size; 84e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin int nodeSize; 85e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin short userNumBits; 86e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin short numBits; 87e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin int numBuckets; 88e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin}; 89e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 90e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstruct cso_hash { 91e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin union { 92e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_hash_data *d; 93e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node *e; 94e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } data; 95e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin}; 96e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 97e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstatic void *cso_data_allocate_node(struct cso_hash_data *hash) 98e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 992a0675eb75b8ca52efab739218bf93922bf884b5José Fonseca return MALLOC(hash->nodeSize); 100e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 101e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 102a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusinstatic void cso_free_node(struct cso_node *node) 103e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 1042a0675eb75b8ca52efab739218bf93922bf884b5José Fonseca FREE(node); 105e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 106e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 107e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstatic struct cso_node * 108e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusincso_hash_create_node(struct cso_hash *hash, 109e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin unsigned akey, void *avalue, 110e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node **anextNode) 111e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 112e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node *node = cso_data_allocate_node(hash->data.d); 1130879237725eca893318137b795d4234300a37e9aZack Rusin 1140879237725eca893318137b795d4234300a37e9aZack Rusin if (!node) 1150879237725eca893318137b795d4234300a37e9aZack Rusin return NULL; 1160879237725eca893318137b795d4234300a37e9aZack Rusin 117e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin node->key = akey; 118e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin node->value = avalue; 119e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 120e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin node->next = (struct cso_node*)(*anextNode); 121e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin *anextNode = node; 122e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin ++hash->data.d->size; 123e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return node; 124e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 125e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 126e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstatic void cso_data_rehash(struct cso_hash_data *hash, int hint) 127e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 128e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin if (hint < 0) { 129e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin hint = countBits(-hint); 130e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin if (hint < MinNumBits) 131e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin hint = MinNumBits; 1322cf860b866d80595b7287d6991dc96abc3ca8dd3José Fonseca hash->userNumBits = (short)hint; 133e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin while (primeForNumBits(hint) < (hash->size >> 1)) 134e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin ++hint; 135e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } else if (hint < MinNumBits) { 136e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin hint = MinNumBits; 137e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } 138e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 139e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin if (hash->numBits != hint) { 140e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node *e = (struct cso_node *)(hash); 141e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node **oldBuckets = hash->buckets; 142e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin int oldNumBuckets = hash->numBuckets; 143e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin int i = 0; 144e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 1452cf860b866d80595b7287d6991dc96abc3ca8dd3José Fonseca hash->numBits = (short)hint; 146e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin hash->numBuckets = primeForNumBits(hint); 1472a0675eb75b8ca52efab739218bf93922bf884b5José Fonseca hash->buckets = MALLOC(sizeof(struct cso_node*) * hash->numBuckets); 148e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin for (i = 0; i < hash->numBuckets; ++i) 149e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin hash->buckets[i] = e; 150e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 151e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin for (i = 0; i < oldNumBuckets; ++i) { 152e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node *firstNode = oldBuckets[i]; 153e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin while (firstNode != e) { 154e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin unsigned h = firstNode->key; 155e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node *lastNode = firstNode; 156b62f0ddd09f8ef9c400feca321412b3f0bc77e63José Fonseca struct cso_node *afterLastNode; 157b62f0ddd09f8ef9c400feca321412b3f0bc77e63José Fonseca struct cso_node **beforeFirstNode; 158b62f0ddd09f8ef9c400feca321412b3f0bc77e63José Fonseca 159e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin while (lastNode->next != e && lastNode->next->key == h) 160e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin lastNode = lastNode->next; 161e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 162b62f0ddd09f8ef9c400feca321412b3f0bc77e63José Fonseca afterLastNode = lastNode->next; 163b62f0ddd09f8ef9c400feca321412b3f0bc77e63José Fonseca beforeFirstNode = &hash->buckets[h % hash->numBuckets]; 164e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin while (*beforeFirstNode != e) 165e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin beforeFirstNode = &(*beforeFirstNode)->next; 166e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin lastNode->next = *beforeFirstNode; 167e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin *beforeFirstNode = firstNode; 168e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin firstNode = afterLastNode; 169e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } 170e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } 1712a0675eb75b8ca52efab739218bf93922bf884b5José Fonseca FREE(oldBuckets); 172e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } 173e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 174e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 175e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstatic void cso_data_might_grow(struct cso_hash_data *hash) 176e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 177e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin if (hash->size >= hash->numBuckets) 178e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin cso_data_rehash(hash, hash->numBits + 1); 179e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 180e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 181e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstatic void cso_data_has_shrunk(struct cso_hash_data *hash) 182e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 183e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin if (hash->size <= (hash->numBuckets >> 3) && 184e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin hash->numBits > hash->userNumBits) { 185e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin int max = MAX(hash->numBits-2, hash->userNumBits); 186e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin cso_data_rehash(hash, max); 187e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } 188e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 189e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 190e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstatic struct cso_node *cso_data_first_node(struct cso_hash_data *hash) 191e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 192e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node *e = (struct cso_node *)(hash); 193e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node **bucket = hash->buckets; 194e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin int n = hash->numBuckets; 195e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin while (n--) { 196e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin if (*bucket != e) 197e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return *bucket; 198e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin ++bucket; 199e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } 200e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return e; 201e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 202e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 203e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstatic struct cso_node **cso_hash_find_node(struct cso_hash *hash, unsigned akey) 204e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 205e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node **node; 206e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 207e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin if (hash->data.d->numBuckets) { 208e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin node = (struct cso_node **)(&hash->data.d->buckets[akey % hash->data.d->numBuckets]); 209e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin assert(*node == hash->data.e || (*node)->next); 210e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin while (*node != hash->data.e && (*node)->key != akey) 211e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin node = &(*node)->next; 212e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } else { 213e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin node = (struct cso_node **)((const struct cso_node * const *)(&hash->data.e)); 214e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } 215e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return node; 216e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 217e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 218e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstruct cso_hash_iter cso_hash_insert(struct cso_hash *hash, 219e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin unsigned key, void *data) 220e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 221e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin cso_data_might_grow(hash->data.d); 222e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 223b62f0ddd09f8ef9c400feca321412b3f0bc77e63José Fonseca { 224b62f0ddd09f8ef9c400feca321412b3f0bc77e63José Fonseca struct cso_node **nextNode = cso_hash_find_node(hash, key); 225b62f0ddd09f8ef9c400feca321412b3f0bc77e63José Fonseca struct cso_node *node = cso_hash_create_node(hash, key, data, nextNode); 2260879237725eca893318137b795d4234300a37e9aZack Rusin if (!node) { 2270879237725eca893318137b795d4234300a37e9aZack Rusin struct cso_hash_iter null_iter = {hash, 0}; 2280879237725eca893318137b795d4234300a37e9aZack Rusin return null_iter; 2290879237725eca893318137b795d4234300a37e9aZack Rusin } 2300879237725eca893318137b795d4234300a37e9aZack Rusin 23183fec372b45eb0af9e2d83549b3d92afb17c38afMichal Krol { 23283fec372b45eb0af9e2d83549b3d92afb17c38afMichal Krol struct cso_hash_iter iter = {hash, node}; 23383fec372b45eb0af9e2d83549b3d92afb17c38afMichal Krol return iter; 23483fec372b45eb0af9e2d83549b3d92afb17c38afMichal Krol } 235b62f0ddd09f8ef9c400feca321412b3f0bc77e63José Fonseca } 236e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 237e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 238e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstruct cso_hash * cso_hash_create(void) 239e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 2402a0675eb75b8ca52efab739218bf93922bf884b5José Fonseca struct cso_hash *hash = MALLOC_STRUCT(cso_hash); 2410879237725eca893318137b795d4234300a37e9aZack Rusin if (!hash) 2420879237725eca893318137b795d4234300a37e9aZack Rusin return NULL; 2430879237725eca893318137b795d4234300a37e9aZack Rusin 2442a0675eb75b8ca52efab739218bf93922bf884b5José Fonseca hash->data.d = MALLOC_STRUCT(cso_hash_data); 2450879237725eca893318137b795d4234300a37e9aZack Rusin if (!hash->data.d) { 2460879237725eca893318137b795d4234300a37e9aZack Rusin FREE(hash); 2470879237725eca893318137b795d4234300a37e9aZack Rusin return NULL; 2480879237725eca893318137b795d4234300a37e9aZack Rusin } 2490879237725eca893318137b795d4234300a37e9aZack Rusin 250e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin hash->data.d->fakeNext = 0; 251e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin hash->data.d->buckets = 0; 252e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin hash->data.d->size = 0; 253e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin hash->data.d->nodeSize = sizeof(struct cso_node); 2542cf860b866d80595b7287d6991dc96abc3ca8dd3José Fonseca hash->data.d->userNumBits = (short)MinNumBits; 255e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin hash->data.d->numBits = 0; 256e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin hash->data.d->numBuckets = 0; 257e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 258e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return hash; 259e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 260e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 261e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinvoid cso_hash_delete(struct cso_hash *hash) 262e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 263e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node *e_for_x = (struct cso_node *)(hash->data.d); 264e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node **bucket = (struct cso_node **)(hash->data.d->buckets); 265e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin int n = hash->data.d->numBuckets; 266e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin while (n--) { 267e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node *cur = *bucket++; 268e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin while (cur != e_for_x) { 269e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node *next = cur->next; 270a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusin cso_free_node(cur); 271e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin cur = next; 272e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } 273e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } 2742a0675eb75b8ca52efab739218bf93922bf884b5José Fonseca FREE(hash->data.d->buckets); 2752a0675eb75b8ca52efab739218bf93922bf884b5José Fonseca FREE(hash->data.d); 2762a0675eb75b8ca52efab739218bf93922bf884b5José Fonseca FREE(hash); 277e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 278e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 279e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstruct cso_hash_iter cso_hash_find(struct cso_hash *hash, 280e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin unsigned key) 281e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 282e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node **nextNode = cso_hash_find_node(hash, key); 283e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_hash_iter iter = {hash, *nextNode}; 284e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return iter; 285e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 286e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 287e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinunsigned cso_hash_iter_key(struct cso_hash_iter iter) 288e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 289e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin if (!iter.node || iter.hash->data.e == iter.node) 290e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return 0; 291e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return iter.node->key; 292e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 293e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 294e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinvoid * cso_hash_iter_data(struct cso_hash_iter iter) 295e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 296e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin if (!iter.node || iter.hash->data.e == iter.node) 297e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return 0; 298e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return iter.node->value; 299e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 300e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 301e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstatic struct cso_node *cso_hash_data_next(struct cso_node *node) 302e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 303e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin union { 304e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node *next; 305e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node *e; 306e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_hash_data *d; 307e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } a; 308b62f0ddd09f8ef9c400feca321412b3f0bc77e63José Fonseca int start; 309b62f0ddd09f8ef9c400feca321412b3f0bc77e63José Fonseca struct cso_node **bucket; 310b62f0ddd09f8ef9c400feca321412b3f0bc77e63José Fonseca int n; 311b62f0ddd09f8ef9c400feca321412b3f0bc77e63José Fonseca 312e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin a.next = node->next; 313e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin if (!a.next) { 3142a0675eb75b8ca52efab739218bf93922bf884b5José Fonseca debug_printf("iterating beyond the last element\n"); 315e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return 0; 316e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } 317e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin if (a.next->next) 318e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return a.next; 319e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 320b62f0ddd09f8ef9c400feca321412b3f0bc77e63José Fonseca start = (node->key % a.d->numBuckets) + 1; 321b62f0ddd09f8ef9c400feca321412b3f0bc77e63José Fonseca bucket = a.d->buckets + start; 322b62f0ddd09f8ef9c400feca321412b3f0bc77e63José Fonseca n = a.d->numBuckets - start; 323e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin while (n--) { 324e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin if (*bucket != a.e) 325e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return *bucket; 326e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin ++bucket; 327e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } 328e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return a.e; 329e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 330e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 331e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 332e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstatic struct cso_node *cso_hash_data_prev(struct cso_node *node) 333e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 334e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin union { 335e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node *e; 336e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_hash_data *d; 337e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } a; 338b62f0ddd09f8ef9c400feca321412b3f0bc77e63José Fonseca int start; 339b62f0ddd09f8ef9c400feca321412b3f0bc77e63José Fonseca struct cso_node *sentinel; 340b62f0ddd09f8ef9c400feca321412b3f0bc77e63José Fonseca struct cso_node **bucket; 341e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 342e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin a.e = node; 343e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin while (a.e->next) 344e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin a.e = a.e->next; 345e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 346e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin if (node == a.e) 347e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin start = a.d->numBuckets - 1; 348e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin else 349e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin start = node->key % a.d->numBuckets; 350e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 351b62f0ddd09f8ef9c400feca321412b3f0bc77e63José Fonseca sentinel = node; 352b62f0ddd09f8ef9c400feca321412b3f0bc77e63José Fonseca bucket = a.d->buckets + start; 353e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin while (start >= 0) { 354e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin if (*bucket != sentinel) { 355e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node *prev = *bucket; 356e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin while (prev->next != sentinel) 357e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin prev = prev->next; 358e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return prev; 359e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } 360e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 361e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin sentinel = a.e; 362e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin --bucket; 363e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin --start; 364e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } 3652a0675eb75b8ca52efab739218bf93922bf884b5José Fonseca debug_printf("iterating backward beyond first element\n"); 366e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return a.e; 367e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 368e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 369e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstruct cso_hash_iter cso_hash_iter_next(struct cso_hash_iter iter) 370e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 371e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_hash_iter next = {iter.hash, cso_hash_data_next(iter.node)}; 372e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return next; 373e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 374e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 375e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinint cso_hash_iter_is_null(struct cso_hash_iter iter) 376e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 377e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin if (!iter.node || iter.node == iter.hash->data.e) 378e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return 1; 379e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return 0; 380e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 381e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 382e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinvoid * cso_hash_take(struct cso_hash *hash, 383e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin unsigned akey) 384e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 385e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node **node = cso_hash_find_node(hash, akey); 386e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin if (*node != hash->data.e) { 387e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin void *t = (*node)->value; 388e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_node *next = (*node)->next; 389a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusin cso_free_node(*node); 390e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin *node = next; 391e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin --hash->data.d->size; 392e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin cso_data_has_shrunk(hash->data.d); 393e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return t; 394e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin } 395e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return 0; 396e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 397e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 398e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstruct cso_hash_iter cso_hash_iter_prev(struct cso_hash_iter iter) 399e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 400e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_hash_iter prev = {iter.hash, 401e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin cso_hash_data_prev(iter.node)}; 402e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return prev; 403e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 404e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin 405e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusinstruct cso_hash_iter cso_hash_first_node(struct cso_hash *hash) 406e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin{ 407e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin struct cso_hash_iter iter = {hash, cso_data_first_node(hash->data.d)}; 408e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin return iter; 409e16c045b83f5c5b4f4064df67623bb76b46b6619Zack Rusin} 4107838aaffdb9d34427ebcb73aac585c85d9622018Zack Rusin 4117838aaffdb9d34427ebcb73aac585c85d9622018Zack Rusinint cso_hash_size(struct cso_hash *hash) 4127838aaffdb9d34427ebcb73aac585c85d9622018Zack Rusin{ 4137838aaffdb9d34427ebcb73aac585c85d9622018Zack Rusin return hash->data.d->size; 4147838aaffdb9d34427ebcb73aac585c85d9622018Zack Rusin} 415a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusin 416a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusinstruct cso_hash_iter cso_hash_erase(struct cso_hash *hash, struct cso_hash_iter iter) 417a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusin{ 418a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusin struct cso_hash_iter ret = iter; 419a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusin struct cso_node *node = iter.node; 420a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusin struct cso_node **node_ptr; 421a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusin 422a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusin if (node == hash->data.e) 423a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusin return iter; 424a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusin 425a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusin ret = cso_hash_iter_next(ret); 426a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusin node_ptr = (struct cso_node**)(&hash->data.d->buckets[node->key % hash->data.d->numBuckets]); 427a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusin while (*node_ptr != node) 428a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusin node_ptr = &(*node_ptr)->next; 429a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusin *node_ptr = node->next; 430a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusin cso_free_node(node); 431a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusin --hash->data.d->size; 432a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusin return ret; 433a889928d85ac8ba7e1a7fe15393858a9422cf750Zack Rusin} 4344fe186f8dc4fc7eeab3b1069c886458cfc2e517cAlan Hourihane 4354fe186f8dc4fc7eeab3b1069c886458cfc2e517cAlan Hourihaneboolean cso_hash_contains(struct cso_hash *hash, unsigned key) 4364fe186f8dc4fc7eeab3b1069c886458cfc2e517cAlan Hourihane{ 4374fe186f8dc4fc7eeab3b1069c886458cfc2e517cAlan Hourihane struct cso_node **node = cso_hash_find_node(hash, key); 4384fe186f8dc4fc7eeab3b1069c886458cfc2e517cAlan Hourihane return (*node != hash->data.e); 4394fe186f8dc4fc7eeab3b1069c886458cfc2e517cAlan Hourihane} 440