1/*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 *
4 * Use of this software is governed by the MIT license
5 *
6 * Written by Sven Verdoolaege, K.U.Leuven, Departement
7 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
8 */
9
10#include <stdlib.h>
11#include <isl_hash_private.h>
12#include <isl/ctx.h>
13#include "isl_config.h"
14
15uint32_t isl_hash_string(uint32_t hash, const char *s)
16{
17 for (; *s; s++)
18 isl_hash_byte(hash, *s);
19 return hash;
20}
21
22uint32_t isl_hash_mem(uint32_t hash, const void *p, size_t len)
23{
24 int i;
25 const char *s = p;
26 for (i = 0; i < len; ++i)
27 isl_hash_byte(hash, s[i]);
28 return hash;
29}
30
31static unsigned int round_up(unsigned int v)
32{
33 int old_v = v;
34
35 while (v) {
36 old_v = v;
37 v ^= v & -v;
38 }
39 return old_v << 1;
40}
41
42int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table,
43 int min_size)
44{
45 size_t size;
46
47 if (!table)
48 return -1;
49
50 if (min_size < 2)
51 min_size = 2;
52 table->bits = ffs(i: round_up(v: 4 * (min_size + 1) / 3 - 1)) - 1;
53 table->n = 0;
54
55 size = 1 << table->bits;
56 table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
57 size);
58 if (!table->entries)
59 return -1;
60
61 return 0;
62}
63
64/* Dummy comparison function that always returns false.
65 */
66static isl_bool no(const void *entry, const void *val)
67{
68 return isl_bool_false;
69}
70
71/* Extend "table" to twice its size.
72 * Return 0 on success and -1 on error.
73 *
74 * We reuse isl_hash_table_find to create entries in the extended table.
75 * Since all entries in the original table are assumed to be different,
76 * there is no need to compare them against each other.
77 */
78static int grow_table(struct isl_ctx *ctx, struct isl_hash_table *table)
79{
80 int n;
81 size_t old_size, size;
82 struct isl_hash_table_entry *entries;
83 uint32_t h;
84
85 entries = table->entries;
86 old_size = 1 << table->bits;
87 size = 2 * old_size;
88 table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
89 size);
90 if (!table->entries) {
91 table->entries = entries;
92 return -1;
93 }
94
95 n = table->n;
96 table->n = 0;
97 table->bits++;
98
99 for (h = 0; h < old_size; ++h) {
100 struct isl_hash_table_entry *entry;
101
102 if (!entries[h].data)
103 continue;
104
105 entry = isl_hash_table_find(ctx, table, key_hash: entries[h].hash,
106 eq: &no, NULL, reserve: 1);
107 if (!entry) {
108 table->bits--;
109 free(ptr: table->entries);
110 table->entries = entries;
111 table->n = n;
112 return -1;
113 }
114
115 *entry = entries[h];
116 }
117
118 free(ptr: entries);
119
120 return 0;
121}
122
123struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size)
124{
125 struct isl_hash_table *table = NULL;
126
127 table = isl_alloc_type(ctx, struct isl_hash_table);
128 if (isl_hash_table_init(ctx, table, min_size))
129 goto error;
130 return table;
131error:
132 isl_hash_table_free(ctx, table);
133 return NULL;
134}
135
136void isl_hash_table_clear(struct isl_hash_table *table)
137{
138 if (!table)
139 return;
140 free(ptr: table->entries);
141}
142
143void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table)
144{
145 if (!table)
146 return;
147 isl_hash_table_clear(table);
148 free(ptr: table);
149}
150
151/* A dummy entry that is used by isl_hash_table_find
152 * to make a distinction between a missing entry and an error condition.
153 */
154static struct isl_hash_table_entry none = { 0, NULL };
155struct isl_hash_table_entry *isl_hash_table_entry_none = &none;
156
157struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
158 struct isl_hash_table *table,
159 uint32_t key_hash,
160 isl_bool (*eq)(const void *entry, const void *val),
161 const void *val, int reserve)
162{
163 size_t size;
164 uint32_t h, key_bits;
165
166 key_bits = isl_hash_bits(key_hash, table->bits);
167 size = 1 << table->bits;
168 for (h = key_bits; table->entries[h].data; h = (h+1) % size) {
169 isl_bool equal;
170
171 if (table->entries[h].hash != key_hash)
172 continue;
173 equal = eq(table->entries[h].data, val);
174 if (equal < 0)
175 return NULL;
176 if (equal)
177 return &table->entries[h];
178 }
179
180 if (!reserve)
181 return isl_hash_table_entry_none;
182
183 if (4 * table->n >= 3 * size) {
184 if (grow_table(ctx, table) < 0)
185 return NULL;
186 return isl_hash_table_find(ctx, table, key_hash, eq, val, reserve: 1);
187 }
188
189 table->n++;
190 table->entries[h].hash = key_hash;
191
192 return &table->entries[h];
193}
194
195/* Return the first entry containing data in "table".
196 * Return isl_hash_table_entry_none is there is no such entry and
197 * NULL on error.
198 */
199struct isl_hash_table_entry *isl_hash_table_first(struct isl_hash_table *table)
200{
201 size_t size;
202 uint32_t h;
203
204 if (!table->entries)
205 return NULL;
206
207 size = 1 << table->bits;
208 for (h = 0; h < size; ++ h)
209 if (table->entries[h].data)
210 return &table->entries[h];
211
212 return isl_hash_table_entry_none;
213}
214
215isl_stat isl_hash_table_foreach(isl_ctx *ctx, struct isl_hash_table *table,
216 isl_stat (*fn)(void **entry, void *user), void *user)
217{
218 size_t size;
219 uint32_t h;
220
221 if (!table->entries)
222 return isl_stat_error;
223
224 size = 1 << table->bits;
225 for (h = 0; h < size; ++ h)
226 if (table->entries[h].data &&
227 fn(&table->entries[h].data, user) < 0)
228 return isl_stat_error;
229
230 return isl_stat_ok;
231}
232
233/* Does "test" succeed on every (non-empty) entry of "table"?
234 */
235isl_bool isl_hash_table_every(isl_ctx *ctx, struct isl_hash_table *table,
236 isl_bool (*test)(void **entry, void *user), void *user)
237{
238 size_t size;
239 uint32_t h;
240
241 if (!table->entries)
242 return isl_bool_error;
243
244 size = 1 << table->bits;
245 for (h = 0; h < size; ++ h) {
246 isl_bool r;
247
248 if (!table->entries[h].data)
249 continue;
250 r = test(&table->entries[h].data, user);
251 if (r < 0 || !r)
252 return r;
253 }
254
255 return isl_bool_true;
256}
257
258void isl_hash_table_remove(struct isl_ctx *ctx,
259 struct isl_hash_table *table,
260 struct isl_hash_table_entry *entry)
261{
262 int h, h2;
263 size_t size;
264
265 if (!table || !entry)
266 return;
267
268 size = 1 << table->bits;
269 h = entry - table->entries;
270 isl_assert(ctx, h >= 0 && h < size, return);
271
272 for (h2 = h+1; table->entries[h2 % size].data; h2++) {
273 uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,
274 table->bits);
275 uint32_t offset = (size + bits - (h+1)) % size;
276 if (offset <= h2 - (h+1))
277 continue;
278 *entry = table->entries[h2 % size];
279 h = h2;
280 entry = &table->entries[h % size];
281 }
282
283 entry->hash = 0;
284 entry->data = NULL;
285 table->n--;
286}
287

source code of polly/lib/External/isl/isl_hash.c