1/**************************************************************************
2 *
3 * Copyright 2007 VMware, Inc.
4 * All Rights Reserved.
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sub license, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice (including the
15 * next paragraph) shall be included in all copies or substantial portions
16 * of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
19 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
21 * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
22 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
23 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
24 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
25 *
26 **************************************************************************/
27
28 /*
29  * Authors:
30  *   Zack Rusin <zackr@vmware.com>
31  */
32
33#include "util/u_debug.h"
34#include "util/u_memory.h"
35
36#include "cso_hash.h"
37
38#ifndef MAX
39#define MAX(a, b) ((a > b) ? (a) : (b))
40#endif
41
42static const int MinNumBits = 4;
43
44static const unsigned char prime_deltas[] = {
45   0,  0,  1,  3,  1,  5,  3,  3,  1,  9,  7,  5,  3,  9, 25,  3,
46   1, 21,  3, 21,  7, 15,  9,  5,  3, 29, 15,  0,  0,  0,  0,  0
47};
48
49static int primeForNumBits(int numBits)
50{
51   return (1 << numBits) + prime_deltas[numBits];
52}
53
54/*
55    Returns the smallest integer n such that
56    primeForNumBits(n) >= hint.
57*/
58static int countBits(int hint)
59{
60   int numBits = 0;
61   int bits = hint;
62
63   while (bits > 1) {
64      bits >>= 1;
65      numBits++;
66   }
67
68   if (numBits >= (int)sizeof(prime_deltas)) {
69      numBits = sizeof(prime_deltas) - 1;
70   } else if (primeForNumBits(numBits) < hint) {
71      ++numBits;
72   }
73   return numBits;
74}
75
76struct cso_hash_data {
77   struct cso_node *fakeNext;
78   struct cso_node **buckets;
79   int size;
80   int nodeSize;
81   short userNumBits;
82   short numBits;
83   int numBuckets;
84};
85
86static void *cso_data_allocate_node(struct cso_hash_data *hash)
87{
88   return MALLOC(hash->nodeSize);
89}
90
91static void cso_free_node(struct cso_node *node)
92{
93   FREE(node);
94}
95
96static struct cso_node *
97cso_hash_create_node(struct cso_hash *hash,
98                      unsigned akey, void *avalue,
99                      struct cso_node **anextNode)
100{
101   struct cso_node *node = cso_data_allocate_node(hash->data.d);
102
103   if (!node)
104      return NULL;
105
106   node->key = akey;
107   node->value = avalue;
108
109   node->next = (struct cso_node*)(*anextNode);
110   *anextNode = node;
111   ++hash->data.d->size;
112   return node;
113}
114
115static void cso_data_rehash(struct cso_hash_data *hash, int hint)
116{
117   if (hint < 0) {
118      hint = countBits(-hint);
119      if (hint < MinNumBits)
120         hint = MinNumBits;
121      hash->userNumBits = (short)hint;
122      while (primeForNumBits(hint) < (hash->size >> 1))
123         ++hint;
124   } else if (hint < MinNumBits) {
125      hint = MinNumBits;
126   }
127
128   if (hash->numBits != hint) {
129      struct cso_node *e = (struct cso_node *)(hash);
130      struct cso_node **oldBuckets = hash->buckets;
131      int oldNumBuckets = hash->numBuckets;
132      int  i = 0;
133
134      hash->numBits = (short)hint;
135      hash->numBuckets = primeForNumBits(hint);
136      hash->buckets = MALLOC(sizeof(struct cso_node*) * hash->numBuckets);
137      for (i = 0; i < hash->numBuckets; ++i)
138         hash->buckets[i] = e;
139
140      for (i = 0; i < oldNumBuckets; ++i) {
141         struct cso_node *firstNode = oldBuckets[i];
142         while (firstNode != e) {
143            unsigned h = firstNode->key;
144            struct cso_node *lastNode = firstNode;
145            struct cso_node *afterLastNode;
146            struct cso_node **beforeFirstNode;
147
148            while (lastNode->next != e && lastNode->next->key == h)
149               lastNode = lastNode->next;
150
151            afterLastNode = lastNode->next;
152            beforeFirstNode = &hash->buckets[h % hash->numBuckets];
153            while (*beforeFirstNode != e)
154               beforeFirstNode = &(*beforeFirstNode)->next;
155            lastNode->next = *beforeFirstNode;
156            *beforeFirstNode = firstNode;
157            firstNode = afterLastNode;
158         }
159      }
160      FREE(oldBuckets);
161   }
162}
163
164static void cso_data_might_grow(struct cso_hash_data *hash)
165{
166   if (hash->size >= hash->numBuckets)
167      cso_data_rehash(hash, hash->numBits + 1);
168}
169
170static void cso_data_has_shrunk(struct cso_hash_data *hash)
171{
172   if (hash->size <= (hash->numBuckets >> 3) &&
173       hash->numBits > hash->userNumBits) {
174      int max = MAX(hash->numBits-2, hash->userNumBits);
175      cso_data_rehash(hash,  max);
176   }
177}
178
179static struct cso_node *cso_data_first_node(struct cso_hash_data *hash)
180{
181   struct cso_node *e = (struct cso_node *)(hash);
182   struct cso_node **bucket = hash->buckets;
183   int n = hash->numBuckets;
184   while (n--) {
185      if (*bucket != e)
186         return *bucket;
187      ++bucket;
188   }
189   return e;
190}
191
192static struct cso_node **cso_hash_find_node(struct cso_hash *hash, unsigned akey)
193{
194   struct cso_node **node;
195
196   if (hash->data.d->numBuckets) {
197      node = (struct cso_node **)(&hash->data.d->buckets[akey % hash->data.d->numBuckets]);
198      assert(*node == hash->data.e || (*node)->next);
199      while (*node != hash->data.e && (*node)->key != akey)
200         node = &(*node)->next;
201   } else {
202      node = (struct cso_node **)((const struct cso_node * const *)(&hash->data.e));
203   }
204   return node;
205}
206
207struct cso_hash_iter cso_hash_insert(struct cso_hash *hash,
208                                       unsigned key, void *data)
209{
210   cso_data_might_grow(hash->data.d);
211
212   {
213      struct cso_node **nextNode = cso_hash_find_node(hash, key);
214      struct cso_node *node = cso_hash_create_node(hash, key, data, nextNode);
215      if (!node) {
216         struct cso_hash_iter null_iter = {hash, 0};
217         return null_iter;
218      }
219
220      {
221         struct cso_hash_iter iter = {hash, node};
222         return iter;
223      }
224   }
225}
226
227struct cso_hash * cso_hash_create(void)
228{
229   struct cso_hash *hash = MALLOC_STRUCT(cso_hash);
230   if (!hash)
231      return NULL;
232
233   hash->data.d = MALLOC_STRUCT(cso_hash_data);
234   if (!hash->data.d) {
235      FREE(hash);
236      return NULL;
237   }
238
239   hash->data.d->fakeNext = 0;
240   hash->data.d->buckets = 0;
241   hash->data.d->size = 0;
242   hash->data.d->nodeSize = sizeof(struct cso_node);
243   hash->data.d->userNumBits = (short)MinNumBits;
244   hash->data.d->numBits = 0;
245   hash->data.d->numBuckets = 0;
246
247   return hash;
248}
249
250void cso_hash_delete(struct cso_hash *hash)
251{
252   struct cso_node *e_for_x = (struct cso_node *)(hash->data.d);
253   struct cso_node **bucket = (struct cso_node **)(hash->data.d->buckets);
254   int n = hash->data.d->numBuckets;
255   while (n--) {
256      struct cso_node *cur = *bucket++;
257      while (cur != e_for_x) {
258         struct cso_node *next = cur->next;
259         cso_free_node(cur);
260         cur = next;
261      }
262   }
263   FREE(hash->data.d->buckets);
264   FREE(hash->data.d);
265   FREE(hash);
266}
267
268struct cso_hash_iter cso_hash_find(struct cso_hash *hash,
269                                     unsigned key)
270{
271   struct cso_node **nextNode = cso_hash_find_node(hash, key);
272   struct cso_hash_iter iter = {hash, *nextNode};
273   return iter;
274}
275
276unsigned cso_hash_iter_key(struct cso_hash_iter iter)
277{
278   if (!iter.node || iter.hash->data.e == iter.node)
279      return 0;
280   return iter.node->key;
281}
282
283static struct cso_node *cso_hash_data_next(struct cso_node *node)
284{
285   union {
286      struct cso_node *next;
287      struct cso_node *e;
288      struct cso_hash_data *d;
289   } a;
290   int start;
291   struct cso_node **bucket;
292   int n;
293
294   a.next = node->next;
295   if (!a.next) {
296      debug_printf("iterating beyond the last element\n");
297      return 0;
298   }
299   if (a.next->next)
300      return a.next;
301
302   start = (node->key % a.d->numBuckets) + 1;
303   bucket = a.d->buckets + start;
304   n = a.d->numBuckets - start;
305   while (n--) {
306      if (*bucket != a.e)
307         return *bucket;
308      ++bucket;
309   }
310   return a.e;
311}
312
313
314static struct cso_node *cso_hash_data_prev(struct cso_node *node)
315{
316   union {
317      struct cso_node *e;
318      struct cso_hash_data *d;
319   } a;
320   int start;
321   struct cso_node *sentinel;
322   struct cso_node **bucket;
323
324   a.e = node;
325   while (a.e->next)
326      a.e = a.e->next;
327
328   if (node == a.e)
329      start = a.d->numBuckets - 1;
330   else
331      start = node->key % a.d->numBuckets;
332
333   sentinel = node;
334   bucket = a.d->buckets + start;
335   while (start >= 0) {
336      if (*bucket != sentinel) {
337         struct cso_node *prev = *bucket;
338         while (prev->next != sentinel)
339            prev = prev->next;
340         return prev;
341      }
342
343      sentinel = a.e;
344      --bucket;
345      --start;
346   }
347   debug_printf("iterating backward beyond first element\n");
348   return a.e;
349}
350
351struct cso_hash_iter cso_hash_iter_next(struct cso_hash_iter iter)
352{
353   struct cso_hash_iter next = {iter.hash, cso_hash_data_next(iter.node)};
354   return next;
355}
356
357void * cso_hash_take(struct cso_hash *hash,
358                      unsigned akey)
359{
360   struct cso_node **node = cso_hash_find_node(hash, akey);
361   if (*node != hash->data.e) {
362      void *t = (*node)->value;
363      struct cso_node *next = (*node)->next;
364      cso_free_node(*node);
365      *node = next;
366      --hash->data.d->size;
367      cso_data_has_shrunk(hash->data.d);
368      return t;
369   }
370   return 0;
371}
372
373struct cso_hash_iter cso_hash_iter_prev(struct cso_hash_iter iter)
374{
375   struct cso_hash_iter prev = {iter.hash,
376                                 cso_hash_data_prev(iter.node)};
377   return prev;
378}
379
380struct cso_hash_iter cso_hash_first_node(struct cso_hash *hash)
381{
382   struct cso_hash_iter iter = {hash, cso_data_first_node(hash->data.d)};
383   return iter;
384}
385
386int cso_hash_size(struct cso_hash *hash)
387{
388   return hash->data.d->size;
389}
390
391struct cso_hash_iter cso_hash_erase(struct cso_hash *hash, struct cso_hash_iter iter)
392{
393   struct cso_hash_iter ret = iter;
394   struct cso_node *node = iter.node;
395   struct cso_node **node_ptr;
396
397   if (node == hash->data.e)
398      return iter;
399
400   ret = cso_hash_iter_next(ret);
401   node_ptr = (struct cso_node**)(&hash->data.d->buckets[node->key % hash->data.d->numBuckets]);
402   while (*node_ptr != node)
403      node_ptr = &(*node_ptr)->next;
404   *node_ptr = node->next;
405   cso_free_node(node);
406   --hash->data.d->size;
407   return ret;
408}
409
410boolean cso_hash_contains(struct cso_hash *hash, unsigned key)
411{
412   struct cso_node **node = cso_hash_find_node(hash, key);
413   return (*node != hash->data.e);
414}
415