← Back to branch summary

~mmach/netext73/mesa-haswell

« back to all changes in this revision

Viewing changes to src/gallium/auxiliary/cso_cache/cso_hash.c

  • Committer: mmach
  • Date: 2022-09-22 19:56:13 UTC
  • Revision ID: netbit73@gmail.com-20220922195613-wtik9mmy20tmor0i
2022-09-22 21:17:09

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/gallium/auxiliary/cso_cache/cso_hash.c
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
 
 
42
 
static const int MinNumBits = 4;
43
 
 
44
 
static 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
 
 
49
 
static 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
 
*/
58
 
static 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
 
 
76
 
static struct cso_node *
77
 
cso_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
 
 
95
 
static 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
 
 
144
 
static 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
 
 
150
 
static 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
 
 
159
 
static 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
 
 
173
 
struct 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
 
 
189
 
void 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
 
 
200
 
void 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
 
 
217
 
unsigned 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
 
 
224
 
struct 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
 
 
254
 
void *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
 
 
270
 
struct 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
 
 
276
 
int cso_hash_size(struct cso_hash *hash)
277
 
{
278
 
   return hash->size;
279
 
}
280
 
 
281
 
struct 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
 
 
300
 
bool 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
 
}