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