Lines Matching refs:table
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;
162 table = HASH_ALLOC(sizeof(*table));
163 if (!table)
165 table->magic = HASH_MAGIC;
166 table->hits = 0;
167 table->partials = 0;
168 table->misses = 0;
171 table->buckets[i] = NULL;
172 return table;
178 __glxHashTablePtr table = (__glxHashTablePtr) t;
183 if (table->magic != HASH_MAGIC)
187 for (bucket = table->buckets[i]; bucket;) {
193 HASH_FREE(table);
201 HashFind(__glxHashTablePtr table, unsigned long key, unsigned long *h)
210 for (bucket = table->buckets[hash]; bucket; bucket = bucket->next) {
215 bucket->next = table->buckets[hash];
216 table->buckets[hash] = bucket;
217 ++table->partials;
220 ++table->hits;
226 ++table->misses;
233 __glxHashTablePtr table = (__glxHashTablePtr) t;
236 if (!table || table->magic != HASH_MAGIC)
239 bucket = HashFind(table, key, NULL);
249 __glxHashTablePtr table = (__glxHashTablePtr) t;
253 if (table->magic != HASH_MAGIC)
256 if (HashFind(table, key, &hash))
257 return 1; /* Already in table */
264 bucket->next = table->buckets[hash];
265 table->buckets[hash] = bucket;
269 return 0; /* Added to table */
275 __glxHashTablePtr table = (__glxHashTablePtr) t;
279 if (table->magic != HASH_MAGIC)
282 bucket = HashFind(table, key, &hash);
287 table->buckets[hash] = bucket->next;
295 __glxHashTablePtr table = (__glxHashTablePtr) t;
297 while (table->p0 < HASH_SIZE) {
298 if (table->p1) {
299 *key = table->p1->key;
300 *value = table->p1->value;
301 table->p1 = table->p1->next;
304 table->p1 = table->buckets[table->p0];
305 ++table->p0;
313 __glxHashTablePtr table = (__glxHashTablePtr) t;
315 if (table->magic != HASH_MAGIC)
318 table->p0 = 0;
319 table->p1 = table->buckets[0];
320 return __glxHashNext(table, key, value);
356 compute_dist(__glxHashTablePtr table)
362 table->hits, table->partials, table->misses);
365 bucket = table->buckets[i];
377 check_table(__glxHashTablePtr table, unsigned long key, unsigned long value)
380 int retcode = __glxHashLookup(table, key, &retval);
386 table->magic, key, value, retval);
407 __glxHashTablePtr table;
411 table = __glxHashCreate();
413 __glxHashInsert(table, i, i);
415 check_table(table, i, i);
417 check_table(table, i, i);
418 compute_dist(table);
419 __glxHashDestroy(table);
422 table = __glxHashCreate();
424 __glxHashInsert(table, i, i);
426 check_table(table, i, i);
428 check_table(table, i, i);
429 compute_dist(table);
430 __glxHashDestroy(table);
433 table = __glxHashCreate();
435 __glxHashInsert(table, i * 4096, i);
437 check_table(table, i * 4096, i);
439 check_table(table, i * 4096, i);
440 compute_dist(table);
441 __glxHashDestroy(table);
444 table = __glxHashCreate();
447 __glxHashInsert(table, random(), i);
450 check_table(table, random(), i);
453 check_table(table, random(), i);
454 compute_dist(table);
455 __glxHashDestroy(table);
458 table = __glxHashCreate();
461 __glxHashInsert(table, random(), i);
464 check_table(table, random(), i);
467 check_table(table, random(), i);
468 compute_dist(table);
469 __glxHashDestroy(table);