OSDN Git Service

amdgpu: fix off by one in handle_table_insert
[android-x86/external-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 #include "xf86drm.h"
75 #include "xf86drmHash.h"
76
77 #define HASH_MAGIC 0xdeadbeef
78
79 static unsigned long HashHash(unsigned long key)
80 {
81     unsigned long        hash = 0;
82     unsigned long        tmp  = key;
83     static int           init = 0;
84     static unsigned long scatter[256];
85     int                  i;
86
87     if (!init) {
88         void *state;
89         state = drmRandomCreate(37);
90         for (i = 0; i < 256; i++) scatter[i] = drmRandom(state);
91         drmRandomDestroy(state);
92         ++init;
93     }
94
95     while (tmp) {
96         hash = (hash << 1) + scatter[tmp & 0xff];
97         tmp >>= 8;
98     }
99
100     hash %= HASH_SIZE;
101     return hash;
102 }
103
104 void *drmHashCreate(void)
105 {
106     HashTablePtr table;
107     int          i;
108
109     table           = drmMalloc(sizeof(*table));
110     if (!table) return NULL;
111     table->magic    = HASH_MAGIC;
112     table->entries  = 0;
113     table->hits     = 0;
114     table->partials = 0;
115     table->misses   = 0;
116
117     for (i = 0; i < HASH_SIZE; i++) table->buckets[i] = NULL;
118     return table;
119 }
120
121 int drmHashDestroy(void *t)
122 {
123     HashTablePtr  table = (HashTablePtr)t;
124     HashBucketPtr bucket;
125     HashBucketPtr next;
126     int           i;
127
128     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
129
130     for (i = 0; i < HASH_SIZE; i++) {
131         for (bucket = table->buckets[i]; bucket;) {
132             next = bucket->next;
133             drmFree(bucket);
134             bucket = next;
135         }
136     }
137     drmFree(table);
138     return 0;
139 }
140
141 /* Find the bucket and organize the list so that this bucket is at the
142    top. */
143
144 static HashBucketPtr HashFind(HashTablePtr table,
145                               unsigned long key, unsigned long *h)
146 {
147     unsigned long hash = HashHash(key);
148     HashBucketPtr prev = NULL;
149     HashBucketPtr bucket;
150
151     if (h) *h = hash;
152
153     for (bucket = table->buckets[hash]; bucket; bucket = bucket->next) {
154         if (bucket->key == key) {
155             if (prev) {
156                                 /* Organize */
157                 prev->next           = bucket->next;
158                 bucket->next         = table->buckets[hash];
159                 table->buckets[hash] = bucket;
160                 ++table->partials;
161             } else {
162                 ++table->hits;
163             }
164             return bucket;
165         }
166         prev = bucket;
167     }
168     ++table->misses;
169     return NULL;
170 }
171
172 int drmHashLookup(void *t, unsigned long key, void **value)
173 {
174     HashTablePtr  table = (HashTablePtr)t;
175     HashBucketPtr bucket;
176
177     if (!table || table->magic != HASH_MAGIC) return -1; /* Bad magic */
178
179     bucket = HashFind(table, key, NULL);
180     if (!bucket) return 1;      /* Not found */
181     *value = bucket->value;
182     return 0;                   /* Found */
183 }
184
185 int drmHashInsert(void *t, unsigned long key, void *value)
186 {
187     HashTablePtr  table = (HashTablePtr)t;
188     HashBucketPtr bucket;
189     unsigned long hash;
190
191     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
192
193     if (HashFind(table, key, &hash)) return 1; /* Already in table */
194
195     bucket               = drmMalloc(sizeof(*bucket));
196     if (!bucket) return -1;     /* Error */
197     bucket->key          = key;
198     bucket->value        = value;
199     bucket->next         = table->buckets[hash];
200     table->buckets[hash] = bucket;
201     return 0;                   /* Added to table */
202 }
203
204 int drmHashDelete(void *t, unsigned long key)
205 {
206     HashTablePtr  table = (HashTablePtr)t;
207     unsigned long hash;
208     HashBucketPtr bucket;
209
210     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
211
212     bucket = HashFind(table, key, &hash);
213
214     if (!bucket) return 1;      /* Not found */
215
216     table->buckets[hash] = bucket->next;
217     drmFree(bucket);
218     return 0;
219 }
220
221 int drmHashNext(void *t, unsigned long *key, void **value)
222 {
223     HashTablePtr  table = (HashTablePtr)t;
224
225     while (table->p0 < HASH_SIZE) {
226         if (table->p1) {
227             *key       = table->p1->key;
228             *value     = table->p1->value;
229             table->p1  = table->p1->next;
230             return 1;
231         }
232         table->p1 = table->buckets[table->p0];
233         ++table->p0;
234     }
235     return 0;
236 }
237
238 int drmHashFirst(void *t, unsigned long *key, void **value)
239 {
240     HashTablePtr  table = (HashTablePtr)t;
241
242     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
243
244     table->p0 = 0;
245     table->p1 = table->buckets[0];
246     return drmHashNext(table, key, value);
247 }