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
106     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()
112     table->entries  = 0;  in drmHashCreate()
113     table->hits     = 0;  in drmHashCreate()
114     table->partials = 0;  in drmHashCreate()
115     table->misses   = 0;  in drmHashCreate()
117     for (i = 0; i < HASH_SIZE; i++) table->buckets[i] = NULL;  in drmHashCreate()
118     return table;  in drmHashCreate()
123     HashTablePtr  table = (HashTablePtr)t;  in drmHashDestroy()  local
128     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */  in drmHashDestroy()
131 	for (bucket = table->buckets[i]; bucket;) {  in drmHashDestroy()
137     drmFree(table);  in drmHashDestroy()
144 static HashBucketPtr HashFind(HashTablePtr table,  in HashFind()  argument
153     for (bucket = table->buckets[hash]; bucket; bucket = bucket->next) {  in HashFind()
158 		bucket->next         = table->buckets[hash];  in HashFind()
159 		table->buckets[hash] = bucket;  in HashFind()
160 		++table->partials;  in HashFind()
162 		++table->hits;  in HashFind()
168     ++table->misses;  in HashFind()
174     HashTablePtr  table = (HashTablePtr)t;  in drmHashLookup()  local
177     if (!table || table->magic != HASH_MAGIC) return -1; /* Bad magic */  in drmHashLookup()
179     bucket = HashFind(table, key, NULL);  in drmHashLookup()
187     HashTablePtr  table = (HashTablePtr)t;  in drmHashInsert()  local
191     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */  in drmHashInsert()
193     if (HashFind(table, key, &hash)) return 1; /* Already in table */  in drmHashInsert()
199     bucket->next         = table->buckets[hash];  in drmHashInsert()
200     table->buckets[hash] = bucket;  in drmHashInsert()
201     return 0;			/* Added to table */  in drmHashInsert()
206     HashTablePtr  table = (HashTablePtr)t;  in drmHashDelete()  local
210     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */  in drmHashDelete()
212     bucket = HashFind(table, key, &hash);  in drmHashDelete()
216     table->buckets[hash] = bucket->next;  in drmHashDelete()
223     HashTablePtr  table = (HashTablePtr)t;  in drmHashNext()  local
225     while (table->p0 < HASH_SIZE) {  in drmHashNext()
226 	if (table->p1) {  in drmHashNext()
227 	    *key       = table->p1->key;  in drmHashNext()
228 	    *value     = table->p1->value;  in drmHashNext()
229 	    table->p1  = table->p1->next;  in drmHashNext()
232 	table->p1 = table->buckets[table->p0];  in drmHashNext()
233 	++table->p0;  in drmHashNext()
240     HashTablePtr  table = (HashTablePtr)t;  in drmHashFirst()  local
242     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */  in drmHashFirst()
244     table->p0 = 0;  in drmHashFirst()
245     table->p1 = table->buckets[0];  in drmHashFirst()
246     return drmHashNext(table, key, value);  in drmHashFirst()