ia64/xen-unstable

view tools/xenstore/hashtable.c @ 19731:01748ccc4da3

Intel VT-d: fix Stoakley boot issue with iommu=1

Signed-off-by: Weidong Han <Weidong.han@intel.com>
Signed-off-by: Allen Kay <allen.m.kay@intel.com>
author Keir Fraser <keir.fraser@citrix.com>
date Fri Jun 05 09:25:50 2009 +0100 (2009-06-05)
parents 57b8c74c35ef
children
line source
1 /* Copyright (C) 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
3 #include "hashtable.h"
4 #include "hashtable_private.h"
5 #include <stdlib.h>
6 #include <stdio.h>
7 #include <string.h>
8 #include <math.h>
9 #include <stdint.h>
11 /*
12 Credit for primes table: Aaron Krowne
13 http://br.endernet.org/~akrowne/
14 http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
15 */
16 static const unsigned int primes[] = {
17 53, 97, 193, 389,
18 769, 1543, 3079, 6151,
19 12289, 24593, 49157, 98317,
20 196613, 393241, 786433, 1572869,
21 3145739, 6291469, 12582917, 25165843,
22 50331653, 100663319, 201326611, 402653189,
23 805306457, 1610612741
24 };
25 const unsigned int prime_table_length = sizeof(primes)/sizeof(primes[0]);
26 const unsigned int max_load_factor = 65; /* percentage */
28 /*****************************************************************************/
29 struct hashtable *
30 create_hashtable(unsigned int minsize,
31 unsigned int (*hashf) (void*),
32 int (*eqf) (void*,void*))
33 {
34 struct hashtable *h;
35 unsigned int pindex, size = primes[0];
37 /* Check requested hashtable isn't too large */
38 if (minsize > (1u << 30)) return NULL;
40 /* Enforce size as prime */
41 for (pindex=0; pindex < prime_table_length; pindex++) {
42 if (primes[pindex] > minsize) { size = primes[pindex]; break; }
43 }
45 h = (struct hashtable *)calloc(1, sizeof(struct hashtable));
46 if (NULL == h)
47 goto err0;
48 h->table = (struct entry **)calloc(size, sizeof(struct entry *));
49 if (NULL == h->table)
50 goto err1;
52 h->tablelength = size;
53 h->primeindex = pindex;
54 h->entrycount = 0;
55 h->hashfn = hashf;
56 h->eqfn = eqf;
57 h->loadlimit = (unsigned int)(((uint64_t)size * max_load_factor) / 100);
58 return h;
60 err1:
61 free(h);
62 err0:
63 return NULL;
64 }
66 /*****************************************************************************/
67 unsigned int
68 hash(struct hashtable *h, void *k)
69 {
70 /* Aim to protect against poor hash functions by adding logic here
71 * - logic taken from java 1.4 hashtable source */
72 unsigned int i = h->hashfn(k);
73 i += ~(i << 9);
74 i ^= ((i >> 14) | (i << 18)); /* >>> */
75 i += (i << 4);
76 i ^= ((i >> 10) | (i << 22)); /* >>> */
77 return i;
78 }
80 /*****************************************************************************/
81 static int
82 hashtable_expand(struct hashtable *h)
83 {
84 /* Double the size of the table to accomodate more entries */
85 struct entry **newtable;
86 struct entry *e;
87 struct entry **pE;
88 unsigned int newsize, i, index;
89 /* Check we're not hitting max capacity */
90 if (h->primeindex == (prime_table_length - 1)) return 0;
91 newsize = primes[++(h->primeindex)];
93 newtable = (struct entry **)calloc(newsize, sizeof(struct entry*));
94 if (NULL != newtable)
95 {
96 /* This algorithm is not 'stable'. ie. it reverses the list
97 * when it transfers entries between the tables */
98 for (i = 0; i < h->tablelength; i++) {
99 while (NULL != (e = h->table[i])) {
100 h->table[i] = e->next;
101 index = indexFor(newsize,e->h);
102 e->next = newtable[index];
103 newtable[index] = e;
104 }
105 }
106 free(h->table);
107 h->table = newtable;
108 }
109 /* Plan B: realloc instead */
110 else
111 {
112 newtable = (struct entry **)
113 realloc(h->table, newsize * sizeof(struct entry *));
114 if (NULL == newtable) { (h->primeindex)--; return 0; }
115 h->table = newtable;
116 memset(newtable[h->tablelength], 0, newsize - h->tablelength);
117 for (i = 0; i < h->tablelength; i++) {
118 for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) {
119 index = indexFor(newsize,e->h);
120 if (index == i)
121 {
122 pE = &(e->next);
123 }
124 else
125 {
126 *pE = e->next;
127 e->next = newtable[index];
128 newtable[index] = e;
129 }
130 }
131 }
132 }
133 h->tablelength = newsize;
134 h->loadlimit = (unsigned int)
135 (((uint64_t)newsize * max_load_factor) / 100);
136 return -1;
137 }
139 /*****************************************************************************/
140 unsigned int
141 hashtable_count(struct hashtable *h)
142 {
143 return h->entrycount;
144 }
146 /*****************************************************************************/
147 int
148 hashtable_insert(struct hashtable *h, void *k, void *v)
149 {
150 /* This method allows duplicate keys - but they shouldn't be used */
151 unsigned int index;
152 struct entry *e;
153 if (++(h->entrycount) > h->loadlimit)
154 {
155 /* Ignore the return value. If expand fails, we should
156 * still try cramming just this value into the existing table
157 * -- we may not have memory for a larger table, but one more
158 * element may be ok. Next time we insert, we'll try expanding again.*/
159 hashtable_expand(h);
160 }
161 e = (struct entry *)calloc(1, sizeof(struct entry));
162 if (NULL == e) { --(h->entrycount); return 0; } /*oom*/
163 e->h = hash(h,k);
164 index = indexFor(h->tablelength,e->h);
165 e->k = k;
166 e->v = v;
167 e->next = h->table[index];
168 h->table[index] = e;
169 return -1;
170 }
172 /*****************************************************************************/
173 void * /* returns value associated with key */
174 hashtable_search(struct hashtable *h, void *k)
175 {
176 struct entry *e;
177 unsigned int hashvalue, index;
178 hashvalue = hash(h,k);
179 index = indexFor(h->tablelength,hashvalue);
180 e = h->table[index];
181 while (NULL != e)
182 {
183 /* Check hash value to short circuit heavier comparison */
184 if ((hashvalue == e->h) && (h->eqfn(k, e->k))) return e->v;
185 e = e->next;
186 }
187 return NULL;
188 }
190 /*****************************************************************************/
191 void * /* returns value associated with key */
192 hashtable_remove(struct hashtable *h, void *k)
193 {
194 /* TODO: consider compacting the table when the load factor drops enough,
195 * or provide a 'compact' method. */
197 struct entry *e;
198 struct entry **pE;
199 void *v;
200 unsigned int hashvalue, index;
202 hashvalue = hash(h,k);
203 index = indexFor(h->tablelength,hash(h,k));
204 pE = &(h->table[index]);
205 e = *pE;
206 while (NULL != e)
207 {
208 /* Check hash value to short circuit heavier comparison */
209 if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
210 {
211 *pE = e->next;
212 h->entrycount--;
213 v = e->v;
214 freekey(e->k);
215 free(e);
216 return v;
217 }
218 pE = &(e->next);
219 e = e->next;
220 }
221 return NULL;
222 }
224 /*****************************************************************************/
225 /* destroy */
226 void
227 hashtable_destroy(struct hashtable *h, int free_values)
228 {
229 unsigned int i;
230 struct entry *e, *f;
231 struct entry **table = h->table;
232 if (free_values)
233 {
234 for (i = 0; i < h->tablelength; i++)
235 {
236 e = table[i];
237 while (NULL != e)
238 { f = e; e = e->next; freekey(f->k); free(f->v); free(f); }
239 }
240 }
241 else
242 {
243 for (i = 0; i < h->tablelength; i++)
244 {
245 e = table[i];
246 while (NULL != e)
247 { f = e; e = e->next; freekey(f->k); free(f); }
248 }
249 }
250 free(h->table);
251 free(h);
252 }
254 /*
255 * Copyright (c) 2002, Christopher Clark
256 * All rights reserved.
257 *
258 * Redistribution and use in source and binary forms, with or without
259 * modification, are permitted provided that the following conditions
260 * are met:
261 *
262 * * Redistributions of source code must retain the above copyright
263 * notice, this list of conditions and the following disclaimer.
264 *
265 * * Redistributions in binary form must reproduce the above copyright
266 * notice, this list of conditions and the following disclaimer in the
267 * documentation and/or other materials provided with the distribution.
268 *
269 * * Neither the name of the original author; nor the names of any contributors
270 * may be used to endorse or promote products derived from this software
271 * without specific prior written permission.
272 *
273 *
274 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
275 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
276 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
277 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
278 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
279 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
280 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
281 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
282 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
283 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
284 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
285 */