← Back to branch summary

~ubuntu-branches/ubuntu/intrepid/xserver-xgl/intrepid

« back to all changes in this revision

Viewing changes to hw/xfree86/os-support/drm/xf86drmHash.c

  • Committer: Bazaar Package Importer
  • Author(s): Matthew Garrett
  • Date: 2006-02-13 14:21:43 UTC
  • Revision ID: james.westby@ubuntu.com-20060213142143-mad6z9xzem7hzxz9
Tags: upstream-7.0.0
Import upstream version 7.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
hw/xfree86/os-support/drm/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
 * $XFree86: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmHash.c,v 1.4 2001/03/21 18:08:54 dawes Exp $
 
29
 *
 
30
 * DESCRIPTION
 
31
 *
 
32
 * This file contains a straightforward implementation of a fixed-sized
 
33
 * hash table using self-organizing linked lists [Knuth73, pp. 398-399] for
 
34
 * collision resolution.  There are two potentially interesting things
 
35
 * about this implementation:
 
36
 *
 
37
 * 1) The table is power-of-two sized.  Prime sized tables are more
 
38
 * traditional, but do not have a significant advantage over power-of-two
 
39
 * sized table, especially when double hashing is not used for collision
 
40
 * resolution.
 
41
 *
 
42
 * 2) The hash computation uses a table of random integers [Hanson97,
 
43
 * pp. 39-41].
 
44
 *
 
45
 * FUTURE ENHANCEMENTS
 
46
 *
 
47
 * With a table size of 512, the current implementation is sufficient for a
 
48
 * few hundred keys.  Since this is well above the expected size of the
 
49
 * tables for which this implementation was designed, the implementation of
 
50
 * dynamic hash tables was postponed until the need arises.  A common (and
 
51
 * naive) approach to dynamic hash table implementation simply creates a
 
52
 * new hash table when necessary, rehashes all the data into the new table,
 
53
 * and destroys the old table.  The approach in [Larson88] is superior in
 
54
 * two ways: 1) only a portion of the table is expanded when needed,
 
55
 * distributing the expansion cost over several insertions, and 2) portions
 
56
 * of the table can be locked, enabling a scalable thread-safe
 
57
 * implementation.
 
58
 *
 
59
 * REFERENCES
 
60
 *
 
61
 * [Hanson97] David R. Hanson.  C Interfaces and Implementations:
 
62
 * Techniques for Creating Reusable Software.  Reading, Massachusetts:
 
63
 * Addison-Wesley, 1997.
 
64
 *
 
65
 * [Knuth73] Donald E. Knuth. The Art of Computer Programming.  Volume 3:
 
66
 * Sorting and Searching.  Reading, Massachusetts: Addison-Wesley, 1973.
 
67
 *
 
68
 * [Larson88] Per-Ake Larson. "Dynamic Hash Tables".  CACM 31(4), April
 
69
 * 1988, pp. 446-457.
 
70
 *
 
71
 */
 
72
 
 
73
#ifdef HAVE_XORG_CONFIG_H
 
74
#include <xorg-config.h>
 
75
#endif
 
76
 
 
77
#define HASH_MAIN 0
 
78
 
 
79
#if HASH_MAIN
 
80
# include <stdio.h>
 
81
# include <stdlib.h>
 
82
#else
 
83
# include "drm.h"
 
84
# include "xf86drm.h"
 
85
# ifdef XFree86LOADER
 
86
#  include "xf86.h"
 
87
#  include "xf86_ansic.h"
 
88
# else
 
89
#  include <stdio.h>
 
90
#  include <stdlib.h>
 
91
# endif
 
92
#endif
 
93
 
 
94
#define N(x)  drm##x
 
95
 
 
96
#define HASH_MAGIC 0xdeadbeef
 
97
#define HASH_DEBUG 0
 
98
#define HASH_SIZE  512          /* Good for about 100 entries */
 
99
                                /* If you change this value, you probably
 
100
                                   have to change the HashHash hashing
 
101
                                   function! */
 
102
 
 
103
#if HASH_MAIN
 
104
#define HASH_ALLOC malloc
 
105
#define HASH_FREE  free
 
106
#define HASH_RANDOM_DECL
 
107
#define HASH_RANDOM_INIT(seed)  srandom(seed)
 
108
#define HASH_RANDOM             random()
 
109
#else
 
110
#define HASH_ALLOC drmMalloc
 
111
#define HASH_FREE  drmFree
 
112
#define HASH_RANDOM_DECL        void *state
 
113
#define HASH_RANDOM_INIT(seed)  state = drmRandomCreate(seed)
 
114
#define HASH_RANDOM             drmRandom(state)
 
115
 
 
116
#endif
 
117
 
 
118
typedef struct HashBucket {
 
119
    unsigned long     key;
 
120
    void              *value;
 
121
    struct HashBucket *next;
 
122
} HashBucket, *HashBucketPtr;
 
123
 
 
124
typedef struct HashTable {
 
125
    unsigned long    magic;
 
126
    unsigned long    entries;
 
127
    unsigned long    hits;      /* At top of linked list */
 
128
    unsigned long    partials;  /* Not at top of linked list */
 
129
    unsigned long    misses;    /* Not in table */
 
130
    HashBucketPtr    buckets[HASH_SIZE];
 
131
    int              p0;
 
132
    HashBucketPtr    p1;
 
133
} HashTable, *HashTablePtr;
 
134
 
 
135
#if HASH_MAIN
 
136
extern void *N(HashCreate)(void);
 
137
extern int  N(HashDestroy)(void *t);
 
138
extern int  N(HashLookup)(void *t, unsigned long key, unsigned long *value);
 
139
extern int  N(HashInsert)(void *t, unsigned long key, unsigned long value);
 
140
extern int  N(HashDelete)(void *t, unsigned long key);
 
141
#endif
 
142
 
 
143
static unsigned long HashHash(unsigned long key)
 
144
{
 
145
    unsigned long        hash = 0;
 
146
    unsigned long        tmp  = key;
 
147
    static int           init = 0;
 
148
    static unsigned long scatter[256];
 
149
    int                  i;
 
150
 
 
151
    if (!init) {
 
152
        HASH_RANDOM_DECL;
 
153
        HASH_RANDOM_INIT(37);
 
154
        for (i = 0; i < 256; i++) scatter[i] = HASH_RANDOM;
 
155
        ++init;
 
156
    }
 
157
 
 
158
    while (tmp) {
 
159
        hash = (hash << 1) + scatter[tmp & 0xff];
 
160
        tmp >>= 8;
 
161
    }
 
162
 
 
163
    hash %= HASH_SIZE;
 
164
#if HASH_DEBUG
 
165
    printf( "Hash(%d) = %d\n", key, hash);
 
166
#endif
 
167
    return hash;
 
168
}
 
169
 
 
170
void *N(HashCreate)(void)
 
171
{
 
172
    HashTablePtr table;
 
173
    int          i;
 
174
 
 
175
    table           = HASH_ALLOC(sizeof(*table));
 
176
    if (!table) return NULL;
 
177
    table->magic    = HASH_MAGIC;
 
178
    table->entries  = 0;
 
179
    table->hits     = 0;
 
180
    table->partials = 0;
 
181
    table->misses   = 0;
 
182
 
 
183
    for (i = 0; i < HASH_SIZE; i++) table->buckets[i] = NULL;
 
184
    return table;
 
185
}
 
186
 
 
187
int N(HashDestroy)(void *t)
 
188
{
 
189
    HashTablePtr  table = (HashTablePtr)t;
 
190
    HashBucketPtr bucket;
 
191
    HashBucketPtr next;
 
192
    int           i;
 
193
 
 
194
    if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
 
195
 
 
196
    for (i = 0; i < HASH_SIZE; i++) {
 
197
        for (bucket = table->buckets[i]; bucket;) {
 
198
            next = bucket->next;
 
199
            HASH_FREE(bucket);
 
200
            bucket = next;
 
201
        }
 
202
    }
 
203
    HASH_FREE(table);
 
204
    return 0;
 
205
}
 
206
 
 
207
/* Find the bucket and organize the list so that this bucket is at the
 
208
   top. */
 
209
 
 
210
static HashBucketPtr HashFind(HashTablePtr table,
 
211
                              unsigned long key, unsigned long *h)
 
212
{
 
213
    unsigned long hash = HashHash(key);
 
214
    HashBucketPtr prev = NULL;
 
215
    HashBucketPtr bucket;
 
216
 
 
217
    if (h) *h = hash;
 
218
 
 
219
    for (bucket = table->buckets[hash]; bucket; bucket = bucket->next) {
 
220
        if (bucket->key == key) {
 
221
            if (prev) {
 
222
                                /* Organize */
 
223
                prev->next           = bucket->next;
 
224
                bucket->next         = table->buckets[hash];
 
225
                table->buckets[hash] = bucket;
 
226
                ++table->partials;
 
227
            } else {
 
228
                ++table->hits;
 
229
            }
 
230
            return bucket;
 
231
        }
 
232
        prev = bucket;
 
233
    }
 
234
    ++table->misses;
 
235
    return NULL;
 
236
}
 
237
 
 
238
int N(HashLookup)(void *t, unsigned long key, void **value)
 
239
{
 
240
    HashTablePtr  table = (HashTablePtr)t;
 
241
    HashBucketPtr bucket;
 
242
 
 
243
    if (!table || table->magic != HASH_MAGIC) return -1; /* Bad magic */
 
244
 
 
245
    bucket = HashFind(table, key, NULL);
 
246
    if (!bucket) return 1;      /* Not found */
 
247
    *value = bucket->value;
 
248
    return 0;                   /* Found */
 
249
}
 
250
 
 
251
int N(HashInsert)(void *t, unsigned long key, void *value)
 
252
{
 
253
    HashTablePtr  table = (HashTablePtr)t;
 
254
    HashBucketPtr bucket;
 
255
    unsigned long hash;
 
256
 
 
257
    if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
 
258
 
 
259
    if (HashFind(table, key, &hash)) return 1; /* Already in table */
 
260
 
 
261
    bucket               = HASH_ALLOC(sizeof(*bucket));
 
262
    if (!bucket) return -1;     /* Error */
 
263
    bucket->key          = key;
 
264
    bucket->value        = value;
 
265
    bucket->next         = table->buckets[hash];
 
266
    table->buckets[hash] = bucket;
 
267
#if HASH_DEBUG
 
268
    printf("Inserted %d at %d/%p\n", key, hash, bucket);
 
269
#endif
 
270
    return 0;                   /* Added to table */
 
271
}
 
272
 
 
273
int N(HashDelete)(void *t, unsigned long key)
 
274
{
 
275
    HashTablePtr  table = (HashTablePtr)t;
 
276
    unsigned long hash;
 
277
    HashBucketPtr bucket;
 
278
 
 
279
    if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
 
280
 
 
281
    bucket = HashFind(table, key, &hash);
 
282
 
 
283
    if (!bucket) return 1;      /* Not found */
 
284
 
 
285
    table->buckets[hash] = bucket->next;
 
286
    HASH_FREE(bucket);
 
287
    return 0;
 
288
}
 
289
 
 
290
int N(HashNext)(void *t, unsigned long *key, void **value)
 
291
{
 
292
    HashTablePtr  table = (HashTablePtr)t;
 
293
 
 
294
    for (; table->p0 < HASH_SIZE;
 
295
         ++table->p0, table->p1 = table->buckets[table->p0]) {
 
296
        if (table->p1) {
 
297
            *key       = table->p1->key;
 
298
            *value     = table->p1->value;
 
299
            table->p1  = table->p1->next;
 
300
            return 1;
 
301
        }
 
302
    }
 
303
    return 0;
 
304
}
 
305
 
 
306
int N(HashFirst)(void *t, unsigned long *key, void **value)
 
307
{
 
308
    HashTablePtr  table = (HashTablePtr)t;
 
309
 
 
310
    if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
 
311
 
 
312
    table->p0 = 0;
 
313
    table->p1 = table->buckets[0];
 
314
    return N(HashNext)(table, key, value);
 
315
}
 
316
 
 
317
#if HASH_MAIN
 
318
#define DIST_LIMIT 10
 
319
static int dist[DIST_LIMIT];
 
320
 
 
321
static void clear_dist(void) {
 
322
    int i;
 
323
 
 
324
    for (i = 0; i < DIST_LIMIT; i++) dist[i] = 0;
 
325
}
 
326
 
 
327
static int count_entries(HashBucketPtr bucket)
 
328
{
 
329
    int count = 0;
 
330
 
 
331
    for (; bucket; bucket = bucket->next) ++count;
 
332
    return count;
 
333
}
 
334
 
 
335
static void update_dist(int count)
 
336
{
 
337
    if (count >= DIST_LIMIT) ++dist[DIST_LIMIT-1];
 
338
    else                     ++dist[count];
 
339
}
 
340
 
 
341
static void compute_dist(HashTablePtr table)
 
342
{
 
343
    int           i;
 
344
    HashBucketPtr bucket;
 
345
 
 
346
    printf("Entries = %ld, hits = %ld, partials = %ld, misses = %ld\n",
 
347
           table->entries, table->hits, table->partials, table->misses);
 
348
    clear_dist();
 
349
    for (i = 0; i < HASH_SIZE; i++) {
 
350
        bucket = table->buckets[i];
 
351
        update_dist(count_entries(bucket));
 
352
    }
 
353
    for (i = 0; i < DIST_LIMIT; i++) {
 
354
        if (i != DIST_LIMIT-1) printf("%5d %10d\n", i, dist[i]);
 
355
        else                   printf("other %10d\n", dist[i]);
 
356
    }
 
357
}
 
358
 
 
359
static void check_table(HashTablePtr table,
 
360
                        unsigned long key, unsigned long value)
 
361
{
 
362
    unsigned long retval  = 0;
 
363
    int           retcode = N(HashLookup)(table, key, &retval);
 
364
 
 
365
    switch (retcode) {
 
366
    case -1:
 
367
        printf("Bad magic = 0x%08lx:"
 
368
               " key = %lu, expected = %lu, returned = %lu\n",
 
369
               table->magic, key, value, retval);
 
370
        break;
 
371
    case 1:
 
372
        printf("Not found: key = %lu, expected = %lu returned = %lu\n",
 
373
               key, value, retval);
 
374
        break;
 
375
    case 0:
 
376
        if (value != retval)
 
377
            printf("Bad value: key = %lu, expected = %lu, returned = %lu\n",
 
378
                   key, value, retval);
 
379
        break;
 
380
    default:
 
381
        printf("Bad retcode = %d: key = %lu, expected = %lu, returned = %lu\n",
 
382
               retcode, key, value, retval);
 
383
        break;
 
384
    }
 
385
}
 
386
 
 
387
int main(void)
 
388
{
 
389
    HashTablePtr table;
 
390
    int          i;
 
391
 
 
392
    printf("\n***** 256 consecutive integers ****\n");
 
393
    table = N(HashCreate)();
 
394
    for (i = 0; i < 256; i++) N(HashInsert)(table, i, i);
 
395
    for (i = 0; i < 256; i++) check_table(table, i, i);
 
396
    for (i = 256; i >= 0; i--) check_table(table, i, i);
 
397
    compute_dist(table);
 
398
    N(HashDestroy)(table);
 
399
 
 
400
    printf("\n***** 1024 consecutive integers ****\n");
 
401
    table = N(HashCreate)();
 
402
    for (i = 0; i < 1024; i++) N(HashInsert)(table, i, i);
 
403
    for (i = 0; i < 1024; i++) check_table(table, i, i);
 
404
    for (i = 1024; i >= 0; i--) check_table(table, i, i);
 
405
    compute_dist(table);
 
406
    N(HashDestroy)(table);
 
407
 
 
408
    printf("\n***** 1024 consecutive page addresses (4k pages) ****\n");
 
409
    table = N(HashCreate)();
 
410
    for (i = 0; i < 1024; i++) N(HashInsert)(table, i*4096, i);
 
411
    for (i = 0; i < 1024; i++) check_table(table, i*4096, i);
 
412
    for (i = 1024; i >= 0; i--) check_table(table, i*4096, i);
 
413
    compute_dist(table);
 
414
    N(HashDestroy)(table);
 
415
 
 
416
    printf("\n***** 1024 random integers ****\n");
 
417
    table = N(HashCreate)();
 
418
    srandom(0xbeefbeef);
 
419
    for (i = 0; i < 1024; i++) N(HashInsert)(table, random(), i);
 
420
    srandom(0xbeefbeef);
 
421
    for (i = 0; i < 1024; i++) check_table(table, random(), i);
 
422
    srandom(0xbeefbeef);
 
423
    for (i = 0; i < 1024; i++) check_table(table, random(), i);
 
424
    compute_dist(table);
 
425
    N(HashDestroy)(table);
 
426
 
 
427
    printf("\n***** 5000 random integers ****\n");
 
428
    table = N(HashCreate)();
 
429
    srandom(0xbeefbeef);
 
430
    for (i = 0; i < 5000; i++) N(HashInsert)(table, random(), i);
 
431
    srandom(0xbeefbeef);
 
432
    for (i = 0; i < 5000; i++) check_table(table, random(), i);
 
433
    srandom(0xbeefbeef);
 
434
    for (i = 0; i < 5000; i++) check_table(table, random(), i);
 
435
    compute_dist(table);
 
436
    N(HashDestroy)(table);
 
437
 
 
438
    return 0;
 
439
}
 
440
#endif