src/glx/x11/glxhash.c

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