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.h>
12 #include <isl/ctx.h>
13 #include "isl_config.h"
14
isl_hash_string(uint32_t hash,const char * s)15 uint32_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
isl_hash_mem(uint32_t hash,const void * p,size_t len)22 uint32_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
round_up(unsigned int v)31 static 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
isl_hash_table_init(struct isl_ctx * ctx,struct isl_hash_table * table,int min_size)42 int 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(round_up(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 */
no(const void * entry,const void * val)66 static 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 */
grow_table(struct isl_ctx * ctx,struct isl_hash_table * table)78 static 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, entries[h].hash,
106 &no, NULL, 1);
107 if (!entry) {
108 table->bits--;
109 free(table->entries);
110 table->entries = entries;
111 table->n = n;
112 return -1;
113 }
114
115 *entry = entries[h];
116 }
117
118 free(entries);
119
120 return 0;
121 }
122
isl_hash_table_alloc(struct isl_ctx * ctx,int min_size)123 struct 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;
131 error:
132 isl_hash_table_free(ctx, table);
133 return NULL;
134 }
135
isl_hash_table_clear(struct isl_hash_table * table)136 void isl_hash_table_clear(struct isl_hash_table *table)
137 {
138 if (!table)
139 return;
140 free(table->entries);
141 }
142
isl_hash_table_free(struct isl_ctx * ctx,struct isl_hash_table * table)143 void 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(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 */
154 static struct isl_hash_table_entry none = { 0, NULL };
155 struct isl_hash_table_entry *isl_hash_table_entry_none = &none;
156
isl_hash_table_find(struct isl_ctx * ctx,struct isl_hash_table * table,uint32_t key_hash,isl_bool (* eq)(const void * entry,const void * val),const void * val,int reserve)157 struct 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, 1);
187 }
188
189 table->n++;
190 table->entries[h].hash = key_hash;
191
192 return &table->entries[h];
193 }
194
isl_hash_table_foreach(isl_ctx * ctx,struct isl_hash_table * table,isl_stat (* fn)(void ** entry,void * user),void * user)195 isl_stat isl_hash_table_foreach(isl_ctx *ctx, struct isl_hash_table *table,
196 isl_stat (*fn)(void **entry, void *user), void *user)
197 {
198 size_t size;
199 uint32_t h;
200
201 if (!table->entries)
202 return isl_stat_error;
203
204 size = 1 << table->bits;
205 for (h = 0; h < size; ++ h)
206 if (table->entries[h].data &&
207 fn(&table->entries[h].data, user) < 0)
208 return isl_stat_error;
209
210 return isl_stat_ok;
211 }
212
isl_hash_table_remove(struct isl_ctx * ctx,struct isl_hash_table * table,struct isl_hash_table_entry * entry)213 void isl_hash_table_remove(struct isl_ctx *ctx,
214 struct isl_hash_table *table,
215 struct isl_hash_table_entry *entry)
216 {
217 int h, h2;
218 size_t size;
219
220 if (!table || !entry)
221 return;
222
223 size = 1 << table->bits;
224 h = entry - table->entries;
225 isl_assert(ctx, h >= 0 && h < size, return);
226
227 for (h2 = h+1; table->entries[h2 % size].data; h2++) {
228 uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,
229 table->bits);
230 uint32_t offset = (size + bits - (h+1)) % size;
231 if (offset <= h2 - (h+1))
232 continue;
233 *entry = table->entries[h2 % size];
234 h = h2;
235 entry = &table->entries[h % size];
236 }
237
238 entry->hash = 0;
239 entry->data = NULL;
240 table->n--;
241 }
242