intel: Add the Gen6+ version of MI_REPORT_PERF_COUNT to intel_decode.c.
[platform/upstream/libdrm.git] / xf86drmHash.c
1 /* xf86drmHash.c -- Small hash table support for integer -> integer mapping
2  * Created: Sun Apr 18 09:35:45 1999 by faith@precisioninsight.com
3  *
4  * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
5  * All Rights Reserved.
6  *
7  * Permission is hereby granted, free of charge, to any person obtaining a
8  * copy of this software and associated documentation files (the "Software"),
9  * to deal in the Software without restriction, including without limitation
10  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
11  * and/or sell copies of the Software, and to permit persons to whom the
12  * Software is furnished to do so, subject to the following conditions:
13  *
14  * The above copyright notice and this permission notice (including the next
15  * paragraph) shall be included in all copies or substantial portions of the
16  * Software.
17  *
18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
21  * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
22  * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
23  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
24  * DEALINGS IN THE SOFTWARE.
25  *
26  * Authors: Rickard E. (Rik) Faith <faith@valinux.com>
27  *
28  * DESCRIPTION
29  *
30  * This file contains a straightforward implementation of a fixed-sized
31  * hash table using self-organizing linked lists [Knuth73, pp. 398-399] for
32  * collision resolution.  There are two potentially interesting things
33  * about this implementation:
34  *
35  * 1) The table is power-of-two sized.  Prime sized tables are more
36  * traditional, but do not have a significant advantage over power-of-two
37  * sized table, especially when double hashing is not used for collision
38  * resolution.
39  *
40  * 2) The hash computation uses a table of random integers [Hanson97,
41  * pp. 39-41].
42  *
43  * FUTURE ENHANCEMENTS
44  *
45  * With a table size of 512, the current implementation is sufficient for a
46  * few hundred keys.  Since this is well above the expected size of the
47  * tables for which this implementation was designed, the implementation of
48  * dynamic hash tables was postponed until the need arises.  A common (and
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,
53  * distributing the expansion cost over several insertions, and 2) portions
54  * of the table can be locked, enabling a scalable thread-safe
55  * implementation.
56  *
57  * REFERENCES
58  *
59  * [Hanson97] David R. Hanson.  C Interfaces and Implementations:
60  * Techniques for Creating Reusable Software.  Reading, Massachusetts:
61  * Addison-Wesley, 1997.
62  *
63  * [Knuth73] Donald E. Knuth. The Art of Computer Programming.  Volume 3:
64  * Sorting and Searching.  Reading, Massachusetts: Addison-Wesley, 1973.
65  *
66  * [Larson88] Per-Ake Larson. "Dynamic Hash Tables".  CACM 31(4), April
67  * 1988, pp. 446-457.
68  *
69  */
70
71 #include <stdio.h>
72 #include <stdlib.h>
73
74 #define HASH_MAIN 0
75
76 #if !HASH_MAIN
77 # include "xf86drm.h"
78 #endif
79
80 #define HASH_MAGIC 0xdeadbeef
81 #define HASH_DEBUG 0
82 #define HASH_SIZE  512          /* Good for about 100 entries */
83                                 /* If you change this value, you probably
84                                    have to change the HashHash hashing
85                                    function! */
86
87 #if HASH_MAIN
88 #define HASH_ALLOC malloc
89 #define HASH_FREE  free
90 #define HASH_RANDOM_DECL
91 #define HASH_RANDOM_INIT(seed)  srandom(seed)
92 #define HASH_RANDOM             random()
93 #define HASH_RANDOM_DESTROY
94 #else
95 #define HASH_ALLOC drmMalloc
96 #define HASH_FREE  drmFree
97 #define HASH_RANDOM_DECL        void *state
98 #define HASH_RANDOM_INIT(seed)  state = drmRandomCreate(seed)
99 #define HASH_RANDOM             drmRandom(state)
100 #define HASH_RANDOM_DESTROY     drmRandomDestroy(state)
101
102 #endif
103
104 typedef struct HashBucket {
105     unsigned long     key;
106     void              *value;
107     struct HashBucket *next;
108 } HashBucket, *HashBucketPtr;
109
110 typedef struct HashTable {
111     unsigned long    magic;
112     unsigned long    entries;
113     unsigned long    hits;      /* At top of linked list */
114     unsigned long    partials;  /* Not at top of linked list */
115     unsigned long    misses;    /* Not in table */
116     HashBucketPtr    buckets[HASH_SIZE];
117     int              p0;
118     HashBucketPtr    p1;
119 } HashTable, *HashTablePtr;
120
121 #if HASH_MAIN
122 extern void *drmHashCreate(void);
123 extern int  drmHashDestroy(void *t);
124 extern int  drmHashLookup(void *t, unsigned long key, unsigned long *value);
125 extern int  drmHashInsert(void *t, unsigned long key, unsigned long value);
126 extern int  drmHashDelete(void *t, unsigned long key);
127 #endif
128
129 static unsigned long HashHash(unsigned long key)
130 {
131     unsigned long        hash = 0;
132     unsigned long        tmp  = key;
133     static int           init = 0;
134     static unsigned long scatter[256];
135     int                  i;
136
137     if (!init) {
138         HASH_RANDOM_DECL;
139         HASH_RANDOM_INIT(37);
140         for (i = 0; i < 256; i++) scatter[i] = HASH_RANDOM;
141         HASH_RANDOM_DESTROY;
142         ++init;
143     }
144
145     while (tmp) {
146         hash = (hash << 1) + scatter[tmp & 0xff];
147         tmp >>= 8;
148     }
149
150     hash %= HASH_SIZE;
151 #if HASH_DEBUG
152     printf( "Hash(%d) = %d\n", key, hash);
153 #endif
154     return hash;
155 }
156
157 void *drmHashCreate(void)
158 {
159     HashTablePtr table;
160     int          i;
161
162     table           = HASH_ALLOC(sizeof(*table));
163     if (!table) return NULL;
164     table->magic    = HASH_MAGIC;
165     table->entries  = 0;
166     table->hits     = 0;
167     table->partials = 0;
168     table->misses   = 0;
169
170     for (i = 0; i < HASH_SIZE; i++) table->buckets[i] = NULL;
171     return table;
172 }
173
174 int drmHashDestroy(void *t)
175 {
176     HashTablePtr  table = (HashTablePtr)t;
177     HashBucketPtr bucket;
178     HashBucketPtr next;
179     int           i;
180
181     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
182
183     for (i = 0; i < HASH_SIZE; i++) {
184         for (bucket = table->buckets[i]; bucket;) {
185             next = bucket->next;
186             HASH_FREE(bucket);
187             bucket = next;
188         }
189     }
190     HASH_FREE(table);
191     return 0;
192 }
193
194 /* Find the bucket and organize the list so that this bucket is at the
195    top. */
196
197 static HashBucketPtr HashFind(HashTablePtr table,
198                               unsigned long key, unsigned long *h)
199 {
200     unsigned long hash = HashHash(key);
201     HashBucketPtr prev = NULL;
202     HashBucketPtr bucket;
203
204     if (h) *h = hash;
205
206     for (bucket = table->buckets[hash]; bucket; bucket = bucket->next) {
207         if (bucket->key == key) {
208             if (prev) {
209                                 /* Organize */
210                 prev->next           = bucket->next;
211                 bucket->next         = table->buckets[hash];
212                 table->buckets[hash] = bucket;
213                 ++table->partials;
214             } else {
215                 ++table->hits;
216             }
217             return bucket;
218         }
219         prev = bucket;
220     }
221     ++table->misses;
222     return NULL;
223 }
224
225 int drmHashLookup(void *t, unsigned long key, void **value)
226 {
227     HashTablePtr  table = (HashTablePtr)t;
228     HashBucketPtr bucket;
229
230     if (!table || table->magic != HASH_MAGIC) return -1; /* Bad magic */
231
232     bucket = HashFind(table, key, NULL);
233     if (!bucket) return 1;      /* Not found */
234     *value = bucket->value;
235     return 0;                   /* Found */
236 }
237
238 int drmHashInsert(void *t, unsigned long key, void *value)
239 {
240     HashTablePtr  table = (HashTablePtr)t;
241     HashBucketPtr bucket;
242     unsigned long hash;
243
244     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
245
246     if (HashFind(table, key, &hash)) return 1; /* Already in table */
247
248     bucket               = HASH_ALLOC(sizeof(*bucket));
249     if (!bucket) return -1;     /* Error */
250     bucket->key          = key;
251     bucket->value        = value;
252     bucket->next         = table->buckets[hash];
253     table->buckets[hash] = bucket;
254 #if HASH_DEBUG
255     printf("Inserted %d at %d/%p\n", key, hash, bucket);
256 #endif
257     return 0;                   /* Added to table */
258 }
259
260 int drmHashDelete(void *t, unsigned long key)
261 {
262     HashTablePtr  table = (HashTablePtr)t;
263     unsigned long hash;
264     HashBucketPtr bucket;
265
266     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
267
268     bucket = HashFind(table, key, &hash);
269
270     if (!bucket) return 1;      /* Not found */
271
272     table->buckets[hash] = bucket->next;
273     HASH_FREE(bucket);
274     return 0;
275 }
276
277 int drmHashNext(void *t, unsigned long *key, void **value)
278 {
279     HashTablePtr  table = (HashTablePtr)t;
280
281     while (table->p0 < HASH_SIZE) {
282         if (table->p1) {
283             *key       = table->p1->key;
284             *value     = table->p1->value;
285             table->p1  = table->p1->next;
286             return 1;
287         }
288         table->p1 = table->buckets[table->p0];
289         ++table->p0;
290     }
291     return 0;
292 }
293
294 int drmHashFirst(void *t, unsigned long *key, void **value)
295 {
296     HashTablePtr  table = (HashTablePtr)t;
297
298     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
299
300     table->p0 = 0;
301     table->p1 = table->buckets[0];
302     return drmHashNext(table, key, value);
303 }
304
305 #if HASH_MAIN
306 #define DIST_LIMIT 10
307 static int dist[DIST_LIMIT];
308
309 static void clear_dist(void) {
310     int i;
311
312     for (i = 0; i < DIST_LIMIT; i++) dist[i] = 0;
313 }
314
315 static int count_entries(HashBucketPtr bucket)
316 {
317     int count = 0;
318
319     for (; bucket; bucket = bucket->next) ++count;
320     return count;
321 }
322
323 static void update_dist(int count)
324 {
325     if (count >= DIST_LIMIT) ++dist[DIST_LIMIT-1];
326     else                     ++dist[count];
327 }
328
329 static void compute_dist(HashTablePtr table)
330 {
331     int           i;
332     HashBucketPtr bucket;
333
334     printf("Entries = %ld, hits = %ld, partials = %ld, misses = %ld\n",
335            table->entries, table->hits, table->partials, table->misses);
336     clear_dist();
337     for (i = 0; i < HASH_SIZE; i++) {
338         bucket = table->buckets[i];
339         update_dist(count_entries(bucket));
340     }
341     for (i = 0; i < DIST_LIMIT; i++) {
342         if (i != DIST_LIMIT-1) printf("%5d %10d\n", i, dist[i]);
343         else                   printf("other %10d\n", dist[i]);
344     }
345 }
346
347 static void check_table(HashTablePtr table,
348                         unsigned long key, unsigned long value)
349 {
350     unsigned long retval  = 0;
351     int           retcode = drmHashLookup(table, key, &retval);
352
353     switch (retcode) {
354     case -1:
355         printf("Bad magic = 0x%08lx:"
356                " key = %lu, expected = %lu, returned = %lu\n",
357                table->magic, key, value, retval);
358         break;
359     case 1:
360         printf("Not found: key = %lu, expected = %lu returned = %lu\n",
361                key, value, retval);
362         break;
363     case 0:
364         if (value != retval)
365             printf("Bad value: key = %lu, expected = %lu, returned = %lu\n",
366                    key, value, retval);
367         break;
368     default:
369         printf("Bad retcode = %d: key = %lu, expected = %lu, returned = %lu\n",
370                retcode, key, value, retval);
371         break;
372     }
373 }
374
375 int main(void)
376 {
377     HashTablePtr table;
378     int          i;
379
380     printf("\n***** 256 consecutive integers ****\n");
381     table = drmHashCreate();
382     for (i = 0; i < 256; i++) drmHashInsert(table, i, i);
383     for (i = 0; i < 256; i++) check_table(table, i, i);
384     for (i = 256; i >= 0; i--) check_table(table, i, i);
385     compute_dist(table);
386     drmHashDestroy(table);
387
388     printf("\n***** 1024 consecutive integers ****\n");
389     table = drmHashCreate();
390     for (i = 0; i < 1024; i++) drmHashInsert(table, i, i);
391     for (i = 0; i < 1024; i++) check_table(table, i, i);
392     for (i = 1024; i >= 0; i--) check_table(table, i, i);
393     compute_dist(table);
394     drmHashDestroy(table);
395
396     printf("\n***** 1024 consecutive page addresses (4k pages) ****\n");
397     table = drmHashCreate();
398     for (i = 0; i < 1024; i++) drmHashInsert(table, i*4096, i);
399     for (i = 0; i < 1024; i++) check_table(table, i*4096, i);
400     for (i = 1024; i >= 0; i--) check_table(table, i*4096, i);
401     compute_dist(table);
402     drmHashDestroy(table);
403
404     printf("\n***** 1024 random integers ****\n");
405     table = drmHashCreate();
406     srandom(0xbeefbeef);
407     for (i = 0; i < 1024; i++) drmHashInsert(table, random(), i);
408     srandom(0xbeefbeef);
409     for (i = 0; i < 1024; i++) check_table(table, random(), i);
410     srandom(0xbeefbeef);
411     for (i = 0; i < 1024; i++) check_table(table, random(), i);
412     compute_dist(table);
413     drmHashDestroy(table);
414
415     printf("\n***** 5000 random integers ****\n");
416     table = drmHashCreate();
417     srandom(0xbeefbeef);
418     for (i = 0; i < 5000; i++) drmHashInsert(table, random(), i);
419     srandom(0xbeefbeef);
420     for (i = 0; i < 5000; i++) check_table(table, random(), i);
421     srandom(0xbeefbeef);
422     for (i = 0; i < 5000; i++) check_table(table, random(), i);
423     compute_dist(table);
424     drmHashDestroy(table);
425
426     return 0;
427 }
428 #endif