Lines Matching refs:table
1 /* xf86drmHash.c -- Small hash table support for integer -> integer mapping
31 * hash table using self-organizing linked lists [Knuth73, pp. 398-399] for
35 * 1) The table is power-of-two sized. Prime sized tables are more
37 * sized table, especially when double hashing is not used for collision
40 * 2) The hash computation uses a table of random integers [Hanson97,
45 * With a table size of 512, the current implementation is sufficient for a
49 * naive) approach to dynamic hash table implementation simply creates a
50 * new hash table when necessary, rehashes all the data into the new table,
51 * and destroys the old table. The approach in [Larson88] is superior in
52 * two ways: 1) only a portion of the table is expanded when needed,
54 * of the table can be locked, enabling a scalable thread-safe
104 static void compute_dist(HashTablePtr table)
110 table->entries, table->hits, table->partials, table->misses);
113 bucket = table->buckets[i];
124 static int check_table(HashTablePtr table,
128 int retcode = drmHashLookup(table, key, &retval);
134 table->magic, key, value, retval);
157 HashTablePtr table;
162 table = drmHashCreate();
164 drmHashInsert(table, i, (void *)(i << 16 | i));
166 ret |= check_table(table, i, (void *)(i << 16 | i));
167 compute_dist(table);
168 drmHashDestroy(table);
171 table = drmHashCreate();
173 drmHashInsert(table, i, (void *)(i << 16 | i));
175 ret |= check_table(table, i, (void *)(i << 16 | i));
176 compute_dist(table);
177 drmHashDestroy(table);
180 table = drmHashCreate();
182 drmHashInsert(table, i*4096, (void *)(i << 16 | i));
184 ret |= check_table(table, i*4096, (void *)(i << 16 | i));
185 compute_dist(table);
186 drmHashDestroy(table);
189 table = drmHashCreate();
192 drmHashInsert(table, random(), (void *)(i << 16 | i));
195 ret |= check_table(table, random(), (void *)(i << 16 | i));
198 ret |= check_table(table, random(), (void *)(i << 16 | i));
199 compute_dist(table);
200 drmHashDestroy(table);
203 table = drmHashCreate();
206 drmHashInsert(table, random(), (void *)(i << 16 | i));
209 ret |= check_table(table, random(), (void *)(i << 16 | i));
212 ret |= check_table(table, random(), (void *)(i << 16 | i));
213 compute_dist(table);
214 drmHashDestroy(table);
