13a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/* glxhash.c -- Small hash table support for integer -> integer mapping 23a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Taken from libdrm. 33a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 43a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Created: Sun Apr 18 09:35:45 1999 by faith@precisioninsight.com 53a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 63a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas. 73a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * All Rights Reserved. 83a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 93a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Permission is hereby granted, free of charge, to any person obtaining a 103a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * copy of this software and associated documentation files (the "Software"), 113a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * to deal in the Software without restriction, including without limitation 123a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * the rights to use, copy, modify, merge, publish, distribute, sublicense, 133a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * and/or sell copies of the Software, and to permit persons to whom the 143a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Software is furnished to do so, subject to the following conditions: 153a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 163a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * The above copyright notice and this permission notice (including the next 173a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * paragraph) shall be included in all copies or substantial portions of the 183a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Software. 193a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 203a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 213a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 223a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 233a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR 243a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 253a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 263a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * DEALINGS IN THE SOFTWARE. 273a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 283a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Authors: Rickard E. (Rik) Faith <faith@valinux.com> 293a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 303a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * DESCRIPTION 313a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 323a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * This file contains a straightforward implementation of a fixed-sized 333a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * hash table using self-organizing linked lists [Knuth73, pp. 398-399] for 343a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * collision resolution. There are two potentially interesting things 353a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * about this implementation: 363a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 373a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 1) The table is power-of-two sized. Prime sized tables are more 383a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * traditional, but do not have a significant advantage over power-of-two 393a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * sized table, especially when double hashing is not used for collision 403a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * resolution. 413a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 423a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 2) The hash computation uses a table of random integers [Hanson97, 433a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * pp. 39-41]. 443a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 453a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * FUTURE ENHANCEMENTS 463a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 473a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * With a table size of 512, the current implementation is sufficient for a 483a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * few hundred keys. Since this is well above the expected size of the 493a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * tables for which this implementation was designed, the implementation of 503a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * dynamic hash tables was postponed until the need arises. A common (and 513a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * naive) approach to dynamic hash table implementation simply creates a 523a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * new hash table when necessary, rehashes all the data into the new table, 533a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * and destroys the old table. The approach in [Larson88] is superior in 543a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * two ways: 1) only a portion of the table is expanded when needed, 553a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * distributing the expansion cost over several insertions, and 2) portions 563a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * of the table can be locked, enabling a scalable thread-safe 573a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * implementation. 583a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 593a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * REFERENCES 603a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 613a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * [Hanson97] David R. Hanson. C Interfaces and Implementations: 623a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Techniques for Creating Reusable Software. Reading, Massachusetts: 633a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Addison-Wesley, 1997. 643a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 653a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * [Knuth73] Donald E. Knuth. The Art of Computer Programming. Volume 3: 663a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Sorting and Searching. Reading, Massachusetts: Addison-Wesley, 1973. 673a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 683a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * [Larson88] Per-Ake Larson. "Dynamic Hash Tables". CACM 31(4), April 693a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 1988, pp. 446-457. 703a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 713a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 723a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 733a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#include "glxhash.h" 743a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#include <X11/Xfuncproto.h> 753a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 763a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define HASH_MAIN 0 773a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 783a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#include <stdio.h> 793a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#include <stdlib.h> 803a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#include <string.h> 813a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 823a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define HASH_MAGIC 0xdeadbeef 833a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define HASH_DEBUG 0 843a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define HASH_SIZE 512 /* Good for about 100 entries */ 853a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org /* If you change this value, you probably 863a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org have to change the HashHash hashing 873a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org function! */ 883a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 893a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define HASH_ALLOC malloc 903a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define HASH_FREE free 913a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#ifndef __GLIBC__ 923a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define HASH_RANDOM_DECL char *ps, rs[256] 933a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define HASH_RANDOM_INIT(seed) ps = initstate(seed, rs, sizeof(rs)) 943a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define HASH_RANDOM random() 953a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define HASH_RANDOM_DESTROY setstate(ps) 963a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#else 973a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define HASH_RANDOM_DECL struct random_data rd; int32_t rv; char rs[256] 983a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define HASH_RANDOM_INIT(seed) \ 993a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org do { \ 1003a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org (void) memset(&rd, 0, sizeof(rd)); \ 1013a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org (void) initstate_r(seed, rs, sizeof(rs), &rd); \ 1023a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } while(0) 1033a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define HASH_RANDOM ((void) random_r(&rd, &rv), rv) 1043a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define HASH_RANDOM_DESTROY 1053a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#endif 1063a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1073a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgtypedef struct __glxHashBucket 1083a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 1093a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned long key; 1103a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org void *value; 1113a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org struct __glxHashBucket *next; 1123a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} __glxHashBucket, *__glxHashBucketPtr; 1133a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1143a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgtypedef struct __glxHashTable *__glxHashTablePtr; 1153a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstruct __glxHashTable 1163a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 1173a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned long magic; 1183a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned long hits; /* At top of linked list */ 1193a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned long partials; /* Not at top of linked list */ 1203a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned long misses; /* Not in table */ 1213a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashBucketPtr buckets[HASH_SIZE]; 1223a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int p0; 1233a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashBucketPtr p1; 1243a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org}; 1253a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1263a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic unsigned long 1273a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgHashHash(unsigned long key) 1283a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 1293a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned long hash = 0; 1303a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned long tmp = key; 1313a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org static int init = 0; 1323a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org static unsigned long scatter[256]; 1333a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int i; 1343a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1353a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (!init) { 1363a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org HASH_RANDOM_DECL; 1373a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org HASH_RANDOM_INIT(37); 1383a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 0; i < 256; i++) 1393a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org scatter[i] = HASH_RANDOM; 1403a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org HASH_RANDOM_DESTROY; 1413a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ++init; 1423a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 1433a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1443a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org while (tmp) { 1453a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org hash = (hash << 1) + scatter[tmp & 0xff]; 1463a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org tmp >>= 8; 1473a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 1483a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1493a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org hash %= HASH_SIZE; 1503a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#if HASH_DEBUG 1513a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org printf("Hash(%d) = %d\n", key, hash); 1523a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#endif 1533a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return hash; 1543a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 1553a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1563a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org_X_HIDDEN __glxHashTable * 1573a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org__glxHashCreate(void) 1583a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 1593a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashTablePtr table; 1603a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int i; 1613a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1623a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org table = HASH_ALLOC(sizeof(*table)); 1633a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (!table) 1643a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return NULL; 1653a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org table->magic = HASH_MAGIC; 1663a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org table->hits = 0; 1673a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org table->partials = 0; 1683a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org table->misses = 0; 1693a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1703a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 0; i < HASH_SIZE; i++) 1713a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org table->buckets[i] = NULL; 1723a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return table; 1733a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 1743a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1753a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org_X_HIDDEN int 1763a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org__glxHashDestroy(__glxHashTable * t) 1773a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 1783a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashTablePtr table = (__glxHashTablePtr) t; 1793a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashBucketPtr bucket; 1803a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashBucketPtr next; 1813a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int i; 1823a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1833a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (table->magic != HASH_MAGIC) 1843a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return -1; /* Bad magic */ 1853a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1863a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 0; i < HASH_SIZE; i++) { 1873a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (bucket = table->buckets[i]; bucket;) { 1883a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org next = bucket->next; 1893a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org HASH_FREE(bucket); 1903a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bucket = next; 1913a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 1923a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 1933a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org HASH_FREE(table); 1943a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return 0; 1953a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 1963a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1973a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/* Find the bucket and organize the list so that this bucket is at the 1983a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org top. */ 1993a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2003a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic __glxHashBucketPtr 2013a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgHashFind(__glxHashTablePtr table, unsigned long key, unsigned long *h) 2023a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 2033a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned long hash = HashHash(key); 2043a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashBucketPtr prev = NULL; 2053a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashBucketPtr bucket; 2063a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2073a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (h) 2083a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org *h = hash; 2093a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2103a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (bucket = table->buckets[hash]; bucket; bucket = bucket->next) { 2113a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (bucket->key == key) { 2123a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (prev) { 2133a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org /* Organize */ 2143a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org prev->next = bucket->next; 2153a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bucket->next = table->buckets[hash]; 2163a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org table->buckets[hash] = bucket; 2173a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ++table->partials; 2183a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 2193a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org else { 2203a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ++table->hits; 2213a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 2223a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return bucket; 2233a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 2243a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org prev = bucket; 2253a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 2263a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ++table->misses; 2273a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return NULL; 2283a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 2293a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2303a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org_X_HIDDEN int 2313a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org__glxHashLookup(__glxHashTable * t, unsigned long key, void **value) 2323a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 2333a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashTablePtr table = (__glxHashTablePtr) t; 2343a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashBucketPtr bucket; 2353a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2363a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (!table || table->magic != HASH_MAGIC) 2373a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return -1; /* Bad magic */ 2383a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2393a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bucket = HashFind(table, key, NULL); 2403a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (!bucket) 2413a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return 1; /* Not found */ 2423a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org *value = bucket->value; 2433a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return 0; /* Found */ 2443a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 2453a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2463a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org_X_HIDDEN int 2473a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org__glxHashInsert(__glxHashTable * t, unsigned long key, void *value) 2483a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 2493a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashTablePtr table = (__glxHashTablePtr) t; 2503a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashBucketPtr bucket; 2513a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned long hash; 2523a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2533a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (table->magic != HASH_MAGIC) 2543a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return -1; /* Bad magic */ 2553a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2563a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (HashFind(table, key, &hash)) 2573a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return 1; /* Already in table */ 2583a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2593a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bucket = HASH_ALLOC(sizeof(*bucket)); 2603a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (!bucket) 2613a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return -1; /* Error */ 2623a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bucket->key = key; 2633a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bucket->value = value; 2643a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bucket->next = table->buckets[hash]; 2653a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org table->buckets[hash] = bucket; 2663a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#if HASH_DEBUG 2673a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org printf("Inserted %d at %d/%p\n", key, hash, bucket); 2683a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#endif 2693a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return 0; /* Added to table */ 2703a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 2713a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2723a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org_X_HIDDEN int 2733a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org__glxHashDelete(__glxHashTable * t, unsigned long key) 2743a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 2753a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashTablePtr table = (__glxHashTablePtr) t; 2763a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned long hash; 2773a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashBucketPtr bucket; 2783a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2793a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (table->magic != HASH_MAGIC) 2803a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return -1; /* Bad magic */ 2813a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2823a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bucket = HashFind(table, key, &hash); 2833a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2843a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (!bucket) 2853a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return 1; /* Not found */ 2863a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2873a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org table->buckets[hash] = bucket->next; 2883a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org HASH_FREE(bucket); 2893a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return 0; 2903a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 2913a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2923a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org_X_HIDDEN int 2933a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org__glxHashNext(__glxHashTable * t, unsigned long *key, void **value) 2943a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 2953a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashTablePtr table = (__glxHashTablePtr) t; 2963a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 2973a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org while (table->p0 < HASH_SIZE) { 2983a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (table->p1) { 2993a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org *key = table->p1->key; 3003a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org *value = table->p1->value; 3013a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org table->p1 = table->p1->next; 3023a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return 1; 3033a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 3043a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org table->p1 = table->buckets[table->p0]; 3053a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ++table->p0; 3063a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 3073a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return 0; 3083a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 3093a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3103a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org_X_HIDDEN int 3113a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org__glxHashFirst(__glxHashTable * t, unsigned long *key, void **value) 3123a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 3133a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashTablePtr table = (__glxHashTablePtr) t; 3143a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3153a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (table->magic != HASH_MAGIC) 3163a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return -1; /* Bad magic */ 3173a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3183a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org table->p0 = 0; 3193a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org table->p1 = table->buckets[0]; 3203a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return __glxHashNext(table, key, value); 3213a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 3223a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3233a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#if HASH_MAIN 3243a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define DIST_LIMIT 10 3253a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic int dist[DIST_LIMIT]; 3263a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3273a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic void 3283a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgclear_dist(void) 3293a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 3303a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int i; 3313a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3323a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 0; i < DIST_LIMIT; i++) 3333a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org dist[i] = 0; 3343a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 3353a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3363a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic int 3373a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgcount_entries(__glxHashBucketPtr bucket) 3383a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 3393a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int count = 0; 3403a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3413a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (; bucket; bucket = bucket->next) 3423a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ++count; 3433a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return count; 3443a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 3453a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3463a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic void 3473a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgupdate_dist(int count) 3483a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 3493a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (count >= DIST_LIMIT) 3503a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ++dist[DIST_LIMIT - 1]; 3513a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org else 3523a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org ++dist[count]; 3533a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 3543a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3553a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic void 3563a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgcompute_dist(__glxHashTablePtr table) 3573a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 3583a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int i; 3593a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashBucketPtr bucket; 3603a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3613a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org printf("Hits = %ld, partials = %ld, misses = %ld\n", 3623a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org table->hits, table->partials, table->misses); 3633a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org clear_dist(); 3643a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 0; i < HASH_SIZE; i++) { 3653a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org bucket = table->buckets[i]; 3663a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org update_dist(count_entries(bucket)); 3673a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 3683a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 0; i < DIST_LIMIT; i++) { 3693a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (i != DIST_LIMIT - 1) 3703a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org printf("%5d %10d\n", i, dist[i]); 3713a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org else 3723a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org printf("other %10d\n", dist[i]); 3733a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 3743a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 3753a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3763a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgstatic void 3773a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgcheck_table(__glxHashTablePtr table, unsigned long key, unsigned long value) 3783a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 3793a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org unsigned long retval = 0; 3803a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int retcode = __glxHashLookup(table, key, &retval); 3813a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 3823a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org switch (retcode) { 3833a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org case -1: 3843a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org printf("Bad magic = 0x%08lx:" 3853a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org " key = %lu, expected = %lu, returned = %lu\n", 3863a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org table->magic, key, value, retval); 3873a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org break; 3883a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org case 1: 3893a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org printf("Not found: key = %lu, expected = %lu returned = %lu\n", 3903a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org key, value, retval); 3913a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org break; 3923a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org case 0: 3933a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org if (value != retval) 3943a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org printf("Bad value: key = %lu, expected = %lu, returned = %lu\n", 3953a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org key, value, retval); 3963a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org break; 3973a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org default: 3983a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org printf("Bad retcode = %d: key = %lu, expected = %lu, returned = %lu\n", 3993a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org retcode, key, value, retval); 4003a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org break; 4013a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org } 4023a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 4033a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 4043a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgint 4053a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgmain(void) 4063a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org{ 4073a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashTablePtr table; 4083a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org int i; 4093a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 4103a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org printf("\n***** 256 consecutive integers ****\n"); 4113a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org table = __glxHashCreate(); 4123a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 0; i < 256; i++) 4133a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashInsert(table, i, i); 4143a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 0; i < 256; i++) 4153a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org check_table(table, i, i); 4163a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 256; i >= 0; i--) 4173a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org check_table(table, i, i); 4183a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org compute_dist(table); 4193a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashDestroy(table); 4203a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 4213a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org printf("\n***** 1024 consecutive integers ****\n"); 4223a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org table = __glxHashCreate(); 4233a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 0; i < 1024; i++) 4243a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashInsert(table, i, i); 4253a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 0; i < 1024; i++) 4263a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org check_table(table, i, i); 4273a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 1024; i >= 0; i--) 4283a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org check_table(table, i, i); 4293a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org compute_dist(table); 4303a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashDestroy(table); 4313a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 4323a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org printf("\n***** 1024 consecutive page addresses (4k pages) ****\n"); 4333a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org table = __glxHashCreate(); 4343a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 0; i < 1024; i++) 4353a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashInsert(table, i * 4096, i); 4363a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 0; i < 1024; i++) 4373a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org check_table(table, i * 4096, i); 4383a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 1024; i >= 0; i--) 4393a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org check_table(table, i * 4096, i); 4403a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org compute_dist(table); 4413a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashDestroy(table); 4423a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 4433a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org printf("\n***** 1024 random integers ****\n"); 4443a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org table = __glxHashCreate(); 4453a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org srandom(0xbeefbeef); 4463a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 0; i < 1024; i++) 4473a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashInsert(table, random(), i); 4483a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org srandom(0xbeefbeef); 4493a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 0; i < 1024; i++) 4503a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org check_table(table, random(), i); 4513a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org srandom(0xbeefbeef); 4523a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 0; i < 1024; i++) 4533a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org check_table(table, random(), i); 4543a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org compute_dist(table); 4553a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashDestroy(table); 4563a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 4573a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org printf("\n***** 5000 random integers ****\n"); 4583a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org table = __glxHashCreate(); 4593a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org srandom(0xbeefbeef); 4603a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 0; i < 5000; i++) 4613a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashInsert(table, random(), i); 4623a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org srandom(0xbeefbeef); 4633a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 0; i < 5000; i++) 4643a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org check_table(table, random(), i); 4653a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org srandom(0xbeefbeef); 4663a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for (i = 0; i < 5000; i++) 4673a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org check_table(table, random(), i); 4683a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org compute_dist(table); 4693a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org __glxHashDestroy(table); 4703a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 4713a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org return 0; 4723a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} 4733a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#endif 474