13a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/************************************************************************** 23a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 33a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Copyright 2007 Tungsten Graphics, Inc., Cedar Park, Texas. 43a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * All Rights Reserved. 53a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 63a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Permission is hereby granted, free of charge, to any person obtaining a 73a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * copy of this software and associated documentation files (the 83a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * "Software"), to deal in the Software without restriction, including 93a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * without limitation the rights to use, copy, modify, merge, publish, 103a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * distribute, sub license, and/or sell copies of the Software, and to 113a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * permit persons to whom the Software is furnished to do so, subject to 123a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * the following conditions: 133a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 143a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * The above copyright notice and this permission notice (including the 153a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * next paragraph) shall be included in all copies or substantial portions 163a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * of the Software. 173a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 183a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 193a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 203a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. 213a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * IN NO EVENT SHALL TUNGSTEN GRAPHICS AND/OR ITS SUPPLIERS BE LIABLE FOR 223a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 233a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 243a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 253a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 263a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org **************************************************************************/ 273a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 283a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org /* 293a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Authors: 303a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Zack Rusin <zack@tungstengraphics.com> 313a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 323a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 333a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#include "util/u_debug.h" 343a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#include "util/u_memory.h" 353a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 363a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#include "cso_hash.h" 373a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 383a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define MAX(a, b) ((a > b) ? (a) : (b)) 393a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 403a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic const int MinNumBits = 4; 413a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 423a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic const unsigned char prime_deltas[] = { 433a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 9, 25, 3, 443a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1, 21, 3, 21, 7, 15, 9, 5, 3, 29, 15, 0, 0, 0, 0, 0 453a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org}; 463a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 473a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic int primeForNumBits(int numBits) 483a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 493a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return (1 << numBits) + prime_deltas[numBits]; 503a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 513a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 523a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/* 533a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org Returns the smallest integer n such that 543a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org primeForNumBits(n) >= hint. 553a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org*/ 563a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic int countBits(int hint) 573a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 583a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int numBits = 0; 593a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int bits = hint; 603a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 613a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org while (bits > 1) { 623a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bits >>= 1; 633a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org numBits++; 643a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 653a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 663a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (numBits >= (int)sizeof(prime_deltas)) { 673a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org numBits = sizeof(prime_deltas) - 1; 683a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } else if (primeForNumBits(numBits) < hint) { 693a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ++numBits; 703a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 713a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return numBits; 723a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 733a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 743a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct cso_node { 753a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node *next; 763a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned key; 773a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org void *value; 783a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org}; 793a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 803a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct cso_hash_data { 813a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node *fakeNext; 823a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node **buckets; 833a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int size; 843a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int nodeSize; 853a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org short userNumBits; 863a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org short numBits; 873a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int numBuckets; 883a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org}; 893a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 903a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct cso_hash { 913a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org union { 923a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_hash_data *d; 933a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node *e; 943a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } data; 953a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org}; 963a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 973a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic void *cso_data_allocate_node(struct cso_hash_data *hash) 983a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 993a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return MALLOC(hash->nodeSize); 1003a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 1013a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1023a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic void cso_free_node(struct cso_node *node) 1033a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 1043a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org FREE(node); 1053a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 1063a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1073a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic struct cso_node * 1083a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgcso_hash_create_node(struct cso_hash *hash, 1093a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned akey, void *avalue, 1103a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node **anextNode) 1113a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 1123a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node *node = cso_data_allocate_node(hash->data.d); 1133a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1143a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (!node) 1153a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return NULL; 1163a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1173a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org node->key = akey; 1183a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org node->value = avalue; 1193a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1203a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org node->next = (struct cso_node*)(*anextNode); 1213a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org *anextNode = node; 1223a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ++hash->data.d->size; 1233a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return node; 1243a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 1253a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1263a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic void cso_data_rehash(struct cso_hash_data *hash, int hint) 1273a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 1283a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (hint < 0) { 1293a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org hint = countBits(-hint); 1303a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (hint < MinNumBits) 1313a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org hint = MinNumBits; 1323a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org hash->userNumBits = (short)hint; 1333a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org while (primeForNumBits(hint) < (hash->size >> 1)) 1343a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ++hint; 1353a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } else if (hint < MinNumBits) { 1363a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org hint = MinNumBits; 1373a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 1383a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1393a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (hash->numBits != hint) { 1403a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node *e = (struct cso_node *)(hash); 1413a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node **oldBuckets = hash->buckets; 1423a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int oldNumBuckets = hash->numBuckets; 1433a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int i = 0; 1443a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1453a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org hash->numBits = (short)hint; 1463a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org hash->numBuckets = primeForNumBits(hint); 1473a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org hash->buckets = MALLOC(sizeof(struct cso_node*) * hash->numBuckets); 1483a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 0; i < hash->numBuckets; ++i) 1493a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org hash->buckets[i] = e; 1503a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1513a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 0; i < oldNumBuckets; ++i) { 1523a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node *firstNode = oldBuckets[i]; 1533a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org while (firstNode != e) { 1543a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned h = firstNode->key; 1553a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node *lastNode = firstNode; 1563a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node *afterLastNode; 1573a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node **beforeFirstNode; 1583a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1593a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org while (lastNode->next != e && lastNode->next->key == h) 1603a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org lastNode = lastNode->next; 1613a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1623a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org afterLastNode = lastNode->next; 1633a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org beforeFirstNode = &hash->buckets[h % hash->numBuckets]; 1643a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org while (*beforeFirstNode != e) 1653a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org beforeFirstNode = &(*beforeFirstNode)->next; 1663a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org lastNode->next = *beforeFirstNode; 1673a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org *beforeFirstNode = firstNode; 1683a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org firstNode = afterLastNode; 1693a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 1703a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 1713a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org FREE(oldBuckets); 1723a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 1733a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 1743a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1753a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic void cso_data_might_grow(struct cso_hash_data *hash) 1763a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 1773a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (hash->size >= hash->numBuckets) 1783a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org cso_data_rehash(hash, hash->numBits + 1); 1793a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 1803a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1813a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic void cso_data_has_shrunk(struct cso_hash_data *hash) 1823a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 1833a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (hash->size <= (hash->numBuckets >> 3) && 1843a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org hash->numBits > hash->userNumBits) { 1853a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int max = MAX(hash->numBits-2, hash->userNumBits); 1863a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org cso_data_rehash(hash, max); 1873a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 1883a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 1893a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1903a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic struct cso_node *cso_data_first_node(struct cso_hash_data *hash) 1913a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 1923a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node *e = (struct cso_node *)(hash); 1933a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node **bucket = hash->buckets; 1943a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int n = hash->numBuckets; 1953a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org while (n--) { 1963a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (*bucket != e) 1973a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return *bucket; 1983a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ++bucket; 1993a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 2003a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return e; 2013a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 2023a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2033a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic struct cso_node **cso_hash_find_node(struct cso_hash *hash, unsigned akey) 2043a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 2053a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node **node; 2063a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2073a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (hash->data.d->numBuckets) { 2083a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org node = (struct cso_node **)(&hash->data.d->buckets[akey % hash->data.d->numBuckets]); 2093a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org assert(*node == hash->data.e || (*node)->next); 2103a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org while (*node != hash->data.e && (*node)->key != akey) 2113a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org node = &(*node)->next; 2123a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } else { 2133a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org node = (struct cso_node **)((const struct cso_node * const *)(&hash->data.e)); 2143a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 2153a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return node; 2163a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 2173a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2183a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct cso_hash_iter cso_hash_insert(struct cso_hash *hash, 2193a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned key, void *data) 2203a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 2213a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org cso_data_might_grow(hash->data.d); 2223a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2233a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org { 2243a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node **nextNode = cso_hash_find_node(hash, key); 2253a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node *node = cso_hash_create_node(hash, key, data, nextNode); 2263a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (!node) { 2273a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_hash_iter null_iter = {hash, 0}; 2283a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return null_iter; 2293a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 2303a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2313a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org { 2323a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_hash_iter iter = {hash, node}; 2333a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return iter; 2343a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 2353a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 2363a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 2373a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2383a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct cso_hash * cso_hash_create(void) 2393a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 2403a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_hash *hash = MALLOC_STRUCT(cso_hash); 2413a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (!hash) 2423a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return NULL; 2433a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2443a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org hash->data.d = MALLOC_STRUCT(cso_hash_data); 2453a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (!hash->data.d) { 2463a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org FREE(hash); 2473a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return NULL; 2483a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 2493a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2503a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org hash->data.d->fakeNext = 0; 2513a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org hash->data.d->buckets = 0; 2523a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org hash->data.d->size = 0; 2533a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org hash->data.d->nodeSize = sizeof(struct cso_node); 2543a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org hash->data.d->userNumBits = (short)MinNumBits; 2553a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org hash->data.d->numBits = 0; 2563a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org hash->data.d->numBuckets = 0; 2573a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2583a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return hash; 2593a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 2603a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2613a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgvoid cso_hash_delete(struct cso_hash *hash) 2623a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 2633a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node *e_for_x = (struct cso_node *)(hash->data.d); 2643a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node **bucket = (struct cso_node **)(hash->data.d->buckets); 2653a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int n = hash->data.d->numBuckets; 2663a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org while (n--) { 2673a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node *cur = *bucket++; 2683a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org while (cur != e_for_x) { 2693a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node *next = cur->next; 2703a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org cso_free_node(cur); 2713a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org cur = next; 2723a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 2733a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 2743a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org FREE(hash->data.d->buckets); 2753a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org FREE(hash->data.d); 2763a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org FREE(hash); 2773a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 2783a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2793a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct cso_hash_iter cso_hash_find(struct cso_hash *hash, 2803a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned key) 2813a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 2823a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node **nextNode = cso_hash_find_node(hash, key); 2833a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_hash_iter iter = {hash, *nextNode}; 2843a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return iter; 2853a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 2863a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2873a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgunsigned cso_hash_iter_key(struct cso_hash_iter iter) 2883a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 2893a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (!iter.node || iter.hash->data.e == iter.node) 2903a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return 0; 2913a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return iter.node->key; 2923a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 2933a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2943a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgvoid * cso_hash_iter_data(struct cso_hash_iter iter) 2953a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 2963a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (!iter.node || iter.hash->data.e == iter.node) 2973a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return 0; 2983a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return iter.node->value; 2993a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 3003a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3013a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic struct cso_node *cso_hash_data_next(struct cso_node *node) 3023a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 3033a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org union { 3043a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node *next; 3053a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node *e; 3063a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_hash_data *d; 3073a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } a; 3083a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int start; 3093a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node **bucket; 3103a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int n; 3113a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3123a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org a.next = node->next; 3133a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (!a.next) { 3143a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org debug_printf("iterating beyond the last element\n"); 3153a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return 0; 3163a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 3173a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (a.next->next) 3183a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return a.next; 3193a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3203a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org start = (node->key % a.d->numBuckets) + 1; 3213a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bucket = a.d->buckets + start; 3223a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org n = a.d->numBuckets - start; 3233a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org while (n--) { 3243a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (*bucket != a.e) 3253a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return *bucket; 3263a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ++bucket; 3273a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 3283a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return a.e; 3293a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 3303a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3313a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3323a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic struct cso_node *cso_hash_data_prev(struct cso_node *node) 3333a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 3343a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org union { 3353a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node *e; 3363a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_hash_data *d; 3373a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } a; 3383a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int start; 3393a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node *sentinel; 3403a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node **bucket; 3413a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3423a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org a.e = node; 3433a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org while (a.e->next) 3443a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org a.e = a.e->next; 3453a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3463a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (node == a.e) 3473a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org start = a.d->numBuckets - 1; 3483a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org else 3493a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org start = node->key % a.d->numBuckets; 3503a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3513a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org sentinel = node; 3523a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bucket = a.d->buckets + start; 3533a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org while (start >= 0) { 3543a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (*bucket != sentinel) { 3553a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node *prev = *bucket; 3563a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org while (prev->next != sentinel) 3573a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org prev = prev->next; 3583a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return prev; 3593a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 3603a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3613a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org sentinel = a.e; 3623a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org --bucket; 3633a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org --start; 3643a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 3653a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org debug_printf("iterating backward beyond first element\n"); 3663a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return a.e; 3673a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 3683a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3693a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct cso_hash_iter cso_hash_iter_next(struct cso_hash_iter iter) 3703a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 3713a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_hash_iter next = {iter.hash, cso_hash_data_next(iter.node)}; 3723a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return next; 3733a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 3743a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3753a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgint cso_hash_iter_is_null(struct cso_hash_iter iter) 3763a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 3773a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (!iter.node || iter.node == iter.hash->data.e) 3783a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return 1; 3793a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return 0; 3803a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 3813a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3823a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgvoid * cso_hash_take(struct cso_hash *hash, 3833a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned akey) 3843a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 3853a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node **node = cso_hash_find_node(hash, akey); 3863a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (*node != hash->data.e) { 3873a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org void *t = (*node)->value; 3883a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node *next = (*node)->next; 3893a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org cso_free_node(*node); 3903a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org *node = next; 3913a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org --hash->data.d->size; 3923a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org cso_data_has_shrunk(hash->data.d); 3933a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return t; 3943a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 3953a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return 0; 3963a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 3973a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3983a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct cso_hash_iter cso_hash_iter_prev(struct cso_hash_iter iter) 3993a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 4003a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_hash_iter prev = {iter.hash, 4013a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org cso_hash_data_prev(iter.node)}; 4023a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return prev; 4033a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 4043a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 4053a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct cso_hash_iter cso_hash_first_node(struct cso_hash *hash) 4063a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 4073a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_hash_iter iter = {hash, cso_data_first_node(hash->data.d)}; 4083a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return iter; 4093a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 4103a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 4113a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgint cso_hash_size(struct cso_hash *hash) 4123a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 4133a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return hash->data.d->size; 4143a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 4153a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 4163a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct cso_hash_iter cso_hash_erase(struct cso_hash *hash, struct cso_hash_iter iter) 4173a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 4183a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_hash_iter ret = iter; 4193a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node *node = iter.node; 4203a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node **node_ptr; 4213a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 4223a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (node == hash->data.e) 4233a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return iter; 4243a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 4253a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ret = cso_hash_iter_next(ret); 4263a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org node_ptr = (struct cso_node**)(&hash->data.d->buckets[node->key % hash->data.d->numBuckets]); 4273a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org while (*node_ptr != node) 4283a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org node_ptr = &(*node_ptr)->next; 4293a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org *node_ptr = node->next; 4303a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org cso_free_node(node); 4313a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org --hash->data.d->size; 4323a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return ret; 4333a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 4343a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 4353a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgboolean cso_hash_contains(struct cso_hash *hash, unsigned key) 4363a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 4373a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct cso_node **node = cso_hash_find_node(hash, key); 4383a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return (*node != hash->data.e); 4393a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 440