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
107 HashTablePtr table;
109 table = drmMalloc(sizeof(*table));
110 if (!table) return NULL;
111 table->magic = HASH_MAGIC;
113 return table;
118 HashTablePtr table = (HashTablePtr)t;
123 if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
126 for (bucket = table->buckets[i]; bucket;) {
132 drmFree(table);
139 static HashBucketPtr HashFind(HashTablePtr table,
148 for (bucket = table->buckets[hash]; bucket; bucket = bucket->next) {
153 bucket->next = table->buckets[hash];
154 table->buckets[hash] = bucket;
155 ++table->partials;
157 ++table->hits;
163 ++table->misses;
169 HashTablePtr table = (HashTablePtr)t;
172 if (!table || table->magic != HASH_MAGIC) return -1; /* Bad magic */
174 bucket = HashFind(table, key, NULL);
182 HashTablePtr table = (HashTablePtr)t;
186 if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
188 if (HashFind(table, key, &hash)) return 1; /* Already in table */
194 bucket->next = table->buckets[hash];
195 table->buckets[hash] = bucket;
196 return 0; /* Added to table */
201 HashTablePtr table = (HashTablePtr)t;
205 if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
207 bucket = HashFind(table, key, &hash);
211 table->buckets[hash] = bucket->next;
218 HashTablePtr table = (HashTablePtr)t;
220 while (table->p0 < HASH_SIZE) {
221 if (table->p1) {
222 *key = table->p1->key;
223 *value = table->p1->value;
224 table->p1 = table->p1->next;
227 table->p1 = table->buckets[table->p0];
228 ++table->p0;
235 HashTablePtr table = (HashTablePtr)t;
237 if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
239 table->p0 = 0;
240 table->p1 = table->buckets[0];
241 return drmHashNext(table, key, value);