tests/hash.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 #include "xf86drm.h"
  75 #include "xf86drmHash.h"
  76
  77 #define DIST_LIMIT 10
  78 static int dist[DIST_LIMIT];
  79
  80 static void clear_dist(void) {
  81     int i;
  82
  83     for (i = 0; i < DIST_LIMIT; i++)
  84         dist[i] = 0;
  85 }
  86
  87 static int count_entries(HashBucketPtr bucket)
  88 {
  89     int count = 0;
  90
  91     for (; bucket; bucket = bucket->next)
  92         ++count;
  93     return count;
  94 }
  95
  96 static void update_dist(int count)
  97 {
  98     if (count >= DIST_LIMIT)
  99         ++dist[DIST_LIMIT-1];
 100     else
 101         ++dist[count];
 102 }
 103
 104 static void compute_dist(HashTablePtr table)
 105 {
 106     int           i;
 107     HashBucketPtr bucket;
 108
 109     printf("Entries = %ld, hits = %ld, partials = %ld, misses = %ld\n",
 110           table->entries, table->hits, table->partials, table->misses);
 111     clear_dist();
 112     for (i = 0; i < HASH_SIZE; i++) {
 113         bucket = table->buckets[i];
 114         update_dist(count_entries(bucket));
 115     }
 116     for (i = 0; i < DIST_LIMIT; i++) {
 117         if (i != DIST_LIMIT-1)
 118             printf("%5d %10d\n", i, dist[i]);
 119         else
 120             printf("other %10d\n", dist[i]);
 121     }
 122 }
 123
 124 static int check_table(HashTablePtr table,
 125                        unsigned long key, void * value)
 126 {
 127     void *retval;
 128     int   retcode = drmHashLookup(table, key, &retval);
 129
 130     switch (retcode) {
 131     case -1:
 132         printf("Bad magic = 0x%08lx:"
 133                " key = %lu, expected = %p, returned = %p\n",
 134                table->magic, key, value, retval);
 135         break;
 136     case 1:
 137         printf("Not found: key = %lu, expected = %p, returned = %p\n",
 138                key, value, retval);
 139         break;
 140     case 0:
 141         if (value != retval) {
 142             printf("Bad value: key = %lu, expected = %p, returned = %p\n",
 143                    key, value, retval);
 144             retcode = -1;
 145         }
 146         break;
 147     default:
 148         printf("Bad retcode = %d: key = %lu, expected = %p, returned = %p\n",
 149                retcode, key, value, retval);
 150         break;
 151     }
 152     return retcode;
 153 }
 154
 155 int main(void)
 156 {
 157     HashTablePtr  table;
 158     unsigned long i;
 159     int           ret = 0;
 160
 161     printf("\n***** 256 consecutive integers ****\n");
 162     table = drmHashCreate();
 163     for (i = 0; i < 256; i++)
 164         drmHashInsert(table, i, (void *)(i << 16 | i));
 165     for (i = 0; i < 256; i++)
 166         ret |= check_table(table, i, (void *)(i << 16 | i));
 167     compute_dist(table);
 168     drmHashDestroy(table);
 169
 170     printf("\n***** 1024 consecutive integers ****\n");
 171     table = drmHashCreate();
 172     for (i = 0; i < 1024; i++)
 173         drmHashInsert(table, i, (void *)(i << 16 | i));
 174     for (i = 0; i < 1024; i++)
 175         ret |= check_table(table, i, (void *)(i << 16 | i));
 176     compute_dist(table);
 177     drmHashDestroy(table);
 178
 179     printf("\n***** 1024 consecutive page addresses (4k pages) ****\n");
 180     table = drmHashCreate();
 181     for (i = 0; i < 1024; i++)
 182         drmHashInsert(table, i*4096, (void *)(i << 16 | i));
 183     for (i = 0; i < 1024; i++)
 184         ret |= check_table(table, i*4096, (void *)(i << 16 | i));
 185     compute_dist(table);
 186     drmHashDestroy(table);
 187
 188     printf("\n***** 1024 random integers ****\n");
 189     table = drmHashCreate();
 190     srandom(0xbeefbeef);
 191     for (i = 0; i < 1024; i++)
 192         drmHashInsert(table, random(), (void *)(i << 16 | i));
 193     srandom(0xbeefbeef);
 194     for (i = 0; i < 1024; i++)
 195         ret |= check_table(table, random(), (void *)(i << 16 | i));
 196     srandom(0xbeefbeef);
 197     for (i = 0; i < 1024; i++)
 198         ret |= check_table(table, random(), (void *)(i << 16 | i));
 199     compute_dist(table);
 200     drmHashDestroy(table);
 201
 202     printf("\n***** 5000 random integers ****\n");
 203     table = drmHashCreate();
 204     srandom(0xbeefbeef);
 205     for (i = 0; i < 5000; i++)
 206         drmHashInsert(table, random(), (void *)(i << 16 | i));
 207     srandom(0xbeefbeef);
 208     for (i = 0; i < 5000; i++)
 209         ret |= check_table(table, random(), (void *)(i << 16 | i));
 210     srandom(0xbeefbeef);
 211     for (i = 0; i < 5000; i++)
 212         ret |= check_table(table, random(), (void *)(i << 16 | i));
 213     compute_dist(table);
 214     drmHashDestroy(table);
 215
 216     return ret;
 217 }