1 /* glxhash.c -- Small hash table support for integer -> integer mapping
33  * hash table using self-organizing linked lists [Knuth73, pp. 398-399] for
37  * 1) The table is power-of-two sized.  Prime sized tables are more
39  * sized table, especially when double hashing is not used for collision
42  * 2) The hash computation uses a table of random integers [Hanson97,
47  * With a table size of 512, the current implementation is sufficient for a
51  * naive) approach to dynamic hash table implementation simply creates a
52  * new hash table when necessary, rehashes all the data into the new table,
53  * and destroys the old table.  The approach in [Larson88] is superior in
54  * two ways: 1) only a portion of the table is expanded when needed,
56  * of the table can be locked, enabling a scalable thread-safe
120    unsigned long misses;        /* Not in table */
159    __glxHashTablePtr table;  in __glxHashCreate()  local
162    table = HASH_ALLOC(sizeof(*table));  in __glxHashCreate()
163    if (!table)  in __glxHashCreate()
165    table->magic = HASH_MAGIC;  in __glxHashCreate()
166    table->hits = 0;  in __glxHashCreate()
167    table->partials = 0;  in __glxHashCreate()
168    table->misses = 0;  in __glxHashCreate()
171       table->buckets[i] = NULL;  in __glxHashCreate()
172    return table;  in __glxHashCreate()
178    __glxHashTablePtr table = (__glxHashTablePtr) t;  in __glxHashDestroy()  local
183    if (table->magic != HASH_MAGIC)  in __glxHashDestroy()
187       for (bucket = table->buckets[i]; bucket;) {  in __glxHashDestroy()
193    HASH_FREE(table);  in __glxHashDestroy()
201 HashFind(__glxHashTablePtr table, unsigned long key, unsigned long *h)  in HashFind()  argument
210    for (bucket = table->buckets[hash]; bucket; bucket = bucket->next) {  in HashFind()
215             bucket->next = table->buckets[hash];  in HashFind()
216             table->buckets[hash] = bucket;  in HashFind()
217             ++table->partials;  in HashFind()
220             ++table->hits;  in HashFind()
226    ++table->misses;  in HashFind()
233    __glxHashTablePtr table = (__glxHashTablePtr) t;  in __glxHashLookup()  local
236    if (!table || table->magic != HASH_MAGIC)  in __glxHashLookup()
239    bucket = HashFind(table, key, NULL);  in __glxHashLookup()
249    __glxHashTablePtr table = (__glxHashTablePtr) t;  in __glxHashInsert()  local
253    if (table->magic != HASH_MAGIC)  in __glxHashInsert()
256    if (HashFind(table, key, &hash))  in __glxHashInsert()
257       return 1;                 /* Already in table */  in __glxHashInsert()
264    bucket->next = table->buckets[hash];  in __glxHashInsert()
265    table->buckets[hash] = bucket;  in __glxHashInsert()
269    return 0;                    /* Added to table */  in __glxHashInsert()
275    __glxHashTablePtr table = (__glxHashTablePtr) t;  in __glxHashDelete()  local
279    if (table->magic != HASH_MAGIC)  in __glxHashDelete()
282    bucket = HashFind(table, key, &hash);  in __glxHashDelete()
287    table->buckets[hash] = bucket->next;  in __glxHashDelete()
295    __glxHashTablePtr table = (__glxHashTablePtr) t;  in __glxHashNext()  local
297    while (table->p0 < HASH_SIZE) {  in __glxHashNext()
298       if (table->p1) {  in __glxHashNext()
299          *key = table->p1->key;  in __glxHashNext()
300          *value = table->p1->value;  in __glxHashNext()
301          table->p1 = table->p1->next;  in __glxHashNext()
304       table->p1 = table->buckets[table->p0];  in __glxHashNext()
305       ++table->p0;  in __glxHashNext()
313    __glxHashTablePtr table = (__glxHashTablePtr) t;  in __glxHashFirst()  local
315    if (table->magic != HASH_MAGIC)  in __glxHashFirst()
318    table->p0 = 0;  in __glxHashFirst()
319    table->p1 = table->buckets[0];  in __glxHashFirst()
320    return __glxHashNext(table, key, value);  in __glxHashFirst()
356 compute_dist(__glxHashTablePtr table)  in compute_dist()  argument
362           table->hits, table->partials, table->misses);  in compute_dist()
365       bucket = table->buckets[i];  in compute_dist()
377 check_table(__glxHashTablePtr table, unsigned long key, unsigned long value)  in check_table()  argument
380    int retcode = __glxHashLookup(table, key, &retval);  in check_table()
386              table->magic, key, value, retval);  in check_table()
407    __glxHashTablePtr table;  in main()  local
411    table = __glxHashCreate();  in main()
413       __glxHashInsert(table, i, i);  in main()
415       check_table(table, i, i);  in main()
417       check_table(table, i, i);  in main()
418    compute_dist(table);  in main()
419    __glxHashDestroy(table);  in main()
422    table = __glxHashCreate();  in main()
424       __glxHashInsert(table, i, i);  in main()
426       check_table(table, i, i);  in main()
428       check_table(table, i, i);  in main()
429    compute_dist(table);  in main()
430    __glxHashDestroy(table);  in main()
433    table = __glxHashCreate();  in main()
435       __glxHashInsert(table, i * 4096, i);  in main()
437       check_table(table, i * 4096, i);  in main()
439       check_table(table, i * 4096, i);  in main()
440    compute_dist(table);  in main()
441    __glxHashDestroy(table);  in main()
444    table = __glxHashCreate();  in main()
447       __glxHashInsert(table, random(), i);  in main()
450       check_table(table, random(), i);  in main()
453       check_table(table, random(), i);  in main()
454    compute_dist(table);  in main()
455    __glxHashDestroy(table);  in main()
458    table = __glxHashCreate();  in main()
461       __glxHashInsert(table, random(), i);  in main()
464       check_table(table, random(), i);  in main()
467       check_table(table, random(), i);  in main()
468    compute_dist(table);  in main()
469    __glxHashDestroy(table);  in main()