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
76static struct cso_node *
77cso_hash_create_node(struct cso_hash *hash,
78                     unsigned akey, void *avalue,
79                     struct cso_node **anextNode)
80{
81   struct cso_node *node = MALLOC(sizeof(struct cso_node));
82
83   if (!node)
84      return NULL;
85
86   node->key = akey;
87   node->value = avalue;
88
89   node->next = *anextNode;
90   *anextNode = node;
91   ++hash->size;
92   return node;
93}
94
95static void cso_data_rehash(struct cso_hash *hash, int hint)
96{
97   if (hint < 0) {
98      hint = countBits(-hint);
99      if (hint < MinNumBits)
100         hint = MinNumBits;
101      hash->userNumBits = (short)hint;
102      while (primeForNumBits(hint) < (hash->size >> 1))
103         ++hint;
104   } else if (hint < MinNumBits) {
105      hint = MinNumBits;
106   }
107
108   if (hash->numBits != hint) {
109      struct cso_node *e = (struct cso_node *)hash;
110      struct cso_node **oldBuckets = hash->buckets;
111      int oldNumBuckets = hash->numBuckets;
112      int  i = 0;
113
114      hash->numBits = (short)hint;
115      hash->numBuckets = primeForNumBits(hint);
116      hash->buckets = MALLOC(sizeof(struct cso_node*) * hash->numBuckets);
117      for (i = 0; i < hash->numBuckets; ++i)
118         hash->buckets[i] = e;
119
120      for (i = 0; i < oldNumBuckets; ++i) {
121         struct cso_node *firstNode = oldBuckets[i];
122         while (firstNode != e) {
123            unsigned h = firstNode->key;
124            struct cso_node *lastNode = firstNode;
125            struct cso_node *afterLastNode;
126            struct cso_node **beforeFirstNode;
127
128            while (lastNode->next != e && lastNode->next->key == h)
129               lastNode = lastNode->next;
130
131            afterLastNode = lastNode->next;
132            beforeFirstNode = &hash->buckets[h % hash->numBuckets];
133            while (*beforeFirstNode != e)
134               beforeFirstNode = &(*beforeFirstNode)->next;
135            lastNode->next = *beforeFirstNode;
136            *beforeFirstNode = firstNode;
137            firstNode = afterLastNode;
138         }
139      }
140      FREE(oldBuckets);
141   }
142}
143
144static void cso_data_might_grow(struct cso_hash *hash)
145{
146   if (hash->size >= hash->numBuckets)
147      cso_data_rehash(hash, hash->numBits + 1);
148}
149
150static void cso_data_has_shrunk(struct cso_hash *hash)
151{
152   if (hash->size <= (hash->numBuckets >> 3) &&
153       hash->numBits > hash->userNumBits) {
154      int max = MAX(hash->numBits-2, hash->userNumBits);
155      cso_data_rehash(hash,  max);
156   }
157}
158
159static struct cso_node *cso_data_first_node(struct cso_hash *hash)
160{
161   struct cso_node *e = (struct cso_node *)hash;
162   struct cso_node **bucket = hash->buckets;
163   int n = hash->numBuckets;
164
165   while (n--) {
166      if (*bucket != e)
167         return *bucket;
168      ++bucket;
169   }
170   return e;
171}
172
173struct cso_hash_iter cso_hash_insert(struct cso_hash *hash,
174                                     unsigned key, void *data)
175{
176   cso_data_might_grow(hash);
177
178   struct cso_node **nextNode = cso_hash_find_node(hash, key);
179   struct cso_node *node = cso_hash_create_node(hash, key, data, nextNode);
180   if (!node) {
181      struct cso_hash_iter null_iter = {hash, NULL};
182      return null_iter;
183   }
184
185   struct cso_hash_iter iter = {hash, node};
186   return iter;
187}
188
189void cso_hash_init(struct cso_hash *hash)
190{
191   hash->fakeNext = NULL;
192   hash->buckets = NULL;
193   hash->size = 0;
194   hash->userNumBits = (short)MinNumBits;
195   hash->numBits = 0;
196   hash->numBuckets = 0;
197   hash->end = (struct cso_node*)hash;
198}
199
200void cso_hash_deinit(struct cso_hash *hash)
201{
202   struct cso_node *e_for_x = hash->end;
203   struct cso_node **bucket = hash->buckets;
204   int n = hash->numBuckets;
205
206   while (n--) {
207      struct cso_node *cur = *bucket++;
208      while (cur != e_for_x) {
209         struct cso_node *next = cur->next;
210         FREE(cur);
211         cur = next;
212      }
213   }
214   FREE(hash->buckets);
215}
216
217unsigned cso_hash_iter_key(struct cso_hash_iter iter)
218{
219   if (!iter.node || iter.hash->end == iter.node)
220      return 0;
221   return iter.node->key;
222}
223
224struct cso_node *cso_hash_data_next(struct cso_node *node)
225{
226   union {
227      struct cso_node *next;
228      struct cso_node *e;
229      struct cso_hash *d;
230   } a;
231   int start;
232   struct cso_node **bucket;
233   int n;
234
235   a.next = node->next;
236   if (!a.next) {
237      debug_printf("iterating beyond the last element\n");
238      return NULL;
239   }
240   if (a.next->next)
241      return a.next;
242
243   start = (node->key % a.d->numBuckets) + 1;
244   bucket = a.d->buckets + start;
245   n = a.d->numBuckets - start;
246   while (n--) {
247      if (*bucket != a.e)
248         return *bucket;
249      ++bucket;
250   }
251   return a.e;
252}
253
254void *cso_hash_take(struct cso_hash *hash, unsigned akey)
255{
256   struct cso_node **node = cso_hash_find_node(hash, akey);
257
258   if (*node != hash->end) {
259      void *t = (*node)->value;
260      struct cso_node *next = (*node)->next;
261      FREE(*node);
262      *node = next;
263      --hash->size;
264      cso_data_has_shrunk(hash);
265      return t;
266   }
267   return NULL;
268}
269
270struct cso_hash_iter cso_hash_first_node(struct cso_hash *hash)
271{
272   struct cso_hash_iter iter = {hash, cso_data_first_node(hash)};
273   return iter;
274}
275
276int cso_hash_size(struct cso_hash *hash)
277{
278   return hash->size;
279}
280
281struct cso_hash_iter cso_hash_erase(struct cso_hash *hash, struct cso_hash_iter iter)
282{
283   struct cso_hash_iter ret = iter;
284   struct cso_node *node = iter.node;
285   struct cso_node **node_ptr;
286
287   if (node == hash->end)
288      return iter;
289
290   ret = cso_hash_iter_next(ret);
291   node_ptr = &hash->buckets[node->key % hash->numBuckets];
292   while (*node_ptr != node)
293      node_ptr = &(*node_ptr)->next;
294   *node_ptr = node->next;
295   FREE(node);
296   --hash->size;
297   return ret;
298}
299
300bool cso_hash_contains(struct cso_hash *hash, unsigned key)
301{
302   struct cso_node **node = cso_hash_find_node(hash, key);
303   return *node != hash->end;
304}
305