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
109 HashTablePtr table;
112 table = drmMalloc(sizeof(*table));
113 if (!table) return NULL;
114 table->magic = HASH_MAGIC;
115 table->entries = 0;
116 table->hits = 0;
117 table->partials = 0;
118 table->misses = 0;
120 for (i = 0; i < HASH_SIZE; i++) table->buckets[i] = NULL;
121 return table;
126 HashTablePtr table = (HashTablePtr)t;
131 if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
134 for (bucket = table->buckets[i]; bucket;) {
140 drmFree(table);
147 static HashBucketPtr HashFind(HashTablePtr table,
156 for (bucket = table->buckets[hash]; bucket; bucket = bucket->next) {
161 bucket->next = table->buckets[hash];
162 table->buckets[hash] = bucket;
163 ++table->partials;
165 ++table->hits;
171 ++table->misses;
177 HashTablePtr table = (HashTablePtr)t;
180 if (!table || table->magic != HASH_MAGIC) return -1; /* Bad magic */
182 bucket = HashFind(table, key, NULL);
190 HashTablePtr table = (HashTablePtr)t;
194 if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
196 if (HashFind(table, key, &hash)) return 1; /* Already in table */
202 bucket->next = table->buckets[hash];
203 table->buckets[hash] = bucket;
207 return 0; /* Added to table */
212 HashTablePtr table = (HashTablePtr)t;
216 if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
218 bucket = HashFind(table, key, &hash);
222 table->buckets[hash] = bucket->next;
229 HashTablePtr table = (HashTablePtr)t;
231 while (table->p0 < HASH_SIZE) {
232 if (table->p1) {
233 *key = table->p1->key;
234 *value = table->p1->value;
235 table->p1 = table->p1->next;
238 table->p1 = table->buckets[table->p0];
239 ++table->p0;
246 HashTablePtr table = (HashTablePtr)t;
248 if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
250 table->p0 = 0;
251 table->p1 = table->buckets[0];
252 return drmHashNext(table, key, value);
