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