1 /*
2 * Copyright 2011 INRIA Saclay
3 * Copyright 2013 Ecole Normale Superieure
4 *
5 * Use of this software is governed by the MIT license
6 *
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
9 * 91893 Orsay, France
10 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
11 */
12
13 #include <isl/ctx.h>
14 #include <isl/hash.h>
15
16 #define ISL_xCAT(A,B) A ## B
17 #define ISL_CAT(A,B) ISL_xCAT(A,B)
18 #define ISL_xFN(TYPE,NAME) TYPE ## _ ## NAME
19 #define ISL_FN(TYPE,NAME) ISL_xFN(TYPE,NAME)
20 #define ISL_xS(TYPE1,TYPE2,NAME) struct isl_ ## TYPE1 ## _ ## TYPE2 ## _ ## NAME
21 #define ISL_yS(TYPE1,TYPE2,NAME) ISL_xS(TYPE1,TYPE2,NAME)
22 #define ISL_S(NAME) ISL_yS(ISL_KEY,ISL_VAL,NAME)
23
24 struct ISL_HMAP {
25 int ref;
26 isl_ctx *ctx;
27 struct isl_hash_table table;
28 };
29
ISL_S(pair)30 ISL_S(pair) {
31 ISL_KEY *key;
32 ISL_VAL *val;
33 };
34
ISL_FN(ISL_HMAP,alloc)35 __isl_give ISL_HMAP *ISL_FN(ISL_HMAP,alloc)(isl_ctx *ctx, int min_size)
36 {
37 ISL_HMAP *hmap;
38
39 hmap = isl_calloc_type(ctx, ISL_HMAP);
40 if (!hmap)
41 return NULL;
42
43 hmap->ctx = ctx;
44 isl_ctx_ref(ctx);
45 hmap->ref = 1;
46
47 if (isl_hash_table_init(ctx, &hmap->table, min_size) < 0)
48 return ISL_FN(ISL_HMAP,free)(hmap);
49
50 return hmap;
51 }
52
free_pair(void ** entry,void * user)53 static isl_stat free_pair(void **entry, void *user)
54 {
55 ISL_S(pair) *pair = *entry;
56 ISL_FN(ISL_KEY,free)(pair->key);
57 ISL_FN(ISL_VAL,free)(pair->val);
58 free(pair);
59 *entry = NULL;
60 return isl_stat_ok;
61 }
62
ISL_FN(ISL_HMAP,free)63 __isl_null ISL_HMAP *ISL_FN(ISL_HMAP,free)(__isl_take ISL_HMAP *hmap)
64 {
65 if (!hmap)
66 return NULL;
67 if (--hmap->ref > 0)
68 return NULL;
69 isl_hash_table_foreach(hmap->ctx, &hmap->table, &free_pair, NULL);
70 isl_hash_table_clear(&hmap->table);
71 isl_ctx_deref(hmap->ctx);
72 free(hmap);
73 return NULL;
74 }
75
ISL_FN(ISL_HMAP,get_ctx)76 isl_ctx *ISL_FN(ISL_HMAP,get_ctx)(__isl_keep ISL_HMAP *hmap)
77 {
78 return hmap ? hmap->ctx : NULL;
79 }
80
81 /* Add a mapping from "key" to "val" to the associative array
82 * pointed to by user.
83 */
add_key_val(__isl_take ISL_KEY * key,__isl_take ISL_VAL * val,void * user)84 static isl_stat add_key_val(__isl_take ISL_KEY *key, __isl_take ISL_VAL *val,
85 void *user)
86 {
87 ISL_HMAP **hmap = (ISL_HMAP **) user;
88
89 *hmap = ISL_FN(ISL_HMAP,set)(*hmap, key, val);
90
91 if (!*hmap)
92 return isl_stat_error;
93
94 return isl_stat_ok;
95 }
96
ISL_FN(ISL_HMAP,dup)97 __isl_give ISL_HMAP *ISL_FN(ISL_HMAP,dup)(__isl_keep ISL_HMAP *hmap)
98 {
99 ISL_HMAP *dup;
100
101 if (!hmap)
102 return NULL;
103
104 dup = ISL_FN(ISL_HMAP,alloc)(hmap->ctx, hmap->table.n);
105 if (ISL_FN(ISL_HMAP,foreach)(hmap, &add_key_val, &dup) < 0)
106 return ISL_FN(ISL_HMAP,free)(dup);
107
108 return dup;
109 }
110
ISL_FN(ISL_HMAP,cow)111 __isl_give ISL_HMAP *ISL_FN(ISL_HMAP,cow)(__isl_take ISL_HMAP *hmap)
112 {
113 if (!hmap)
114 return NULL;
115
116 if (hmap->ref == 1)
117 return hmap;
118 hmap->ref--;
119 return ISL_FN(ISL_HMAP,dup)(hmap);
120 }
121
ISL_FN(ISL_HMAP,copy)122 __isl_give ISL_HMAP *ISL_FN(ISL_HMAP,copy)(__isl_keep ISL_HMAP *hmap)
123 {
124 if (!hmap)
125 return NULL;
126
127 hmap->ref++;
128 return hmap;
129 }
130
has_key(const void * entry,const void * c_key)131 static int has_key(const void *entry, const void *c_key)
132 {
133 const ISL_S(pair) *pair = entry;
134 ISL_KEY *key = (ISL_KEY *) c_key;
135
136 return ISL_KEY_IS_EQUAL(pair->key, key);
137 }
138
139 /* If "hmap" contains a value associated to "key", then return
140 * (isl_bool_true, copy of value).
141 * Otherwise, return
142 * (isl_bool_false, NULL).
143 * If an error occurs, then return
144 * (isl_bool_error, NULL).
145 */
ISL_MAYBE(ISL_VAL)146 __isl_give ISL_MAYBE(ISL_VAL) ISL_FN(ISL_HMAP,try_get)(
147 __isl_keep ISL_HMAP *hmap, __isl_keep ISL_KEY *key)
148 {
149 struct isl_hash_table_entry *entry;
150 ISL_S(pair) *pair;
151 uint32_t hash;
152 ISL_MAYBE(ISL_VAL) res = { isl_bool_false, NULL };
153
154 if (!hmap || !key)
155 goto error;
156
157 hash = ISL_FN(ISL_KEY,get_hash)(key);
158 entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash,
159 &has_key, key, 0);
160
161 if (!entry)
162 return res;
163
164 pair = entry->data;
165
166 res.valid = isl_bool_true;
167 res.value = ISL_FN(ISL_VAL,copy)(pair->val);
168 if (!res.value)
169 res.valid = isl_bool_error;
170 return res;
171 error:
172 res.valid = isl_bool_error;
173 res.value = NULL;
174 return res;
175 }
176
177 /* If "hmap" contains a value associated to "key", then return
178 * isl_bool_true. Otherwise, return isl_bool_false.
179 * Return isl_bool_error on error.
180 */
ISL_FN(ISL_HMAP,has)181 isl_bool ISL_FN(ISL_HMAP,has)(__isl_keep ISL_HMAP *hmap,
182 __isl_keep ISL_KEY *key)
183 {
184 ISL_MAYBE(ISL_VAL) res;
185
186 res = ISL_FN(ISL_HMAP,try_get)(hmap, key);
187 ISL_FN(ISL_VAL,free)(res.value);
188
189 return res.valid;
190 }
191
192 /* If "hmap" contains a value associated to "key", then return
193 * a copy of that value. Otherwise, return NULL.
194 * Return NULL on error.
195 */
ISL_FN(ISL_HMAP,get)196 __isl_give ISL_VAL *ISL_FN(ISL_HMAP,get)(__isl_keep ISL_HMAP *hmap,
197 __isl_take ISL_KEY *key)
198 {
199 ISL_VAL *res;
200
201 res = ISL_FN(ISL_HMAP,try_get)(hmap, key).value;
202 ISL_FN(ISL_KEY,free)(key);
203 return res;
204 }
205
206 /* Remove the mapping between "key" and its associated value (if any)
207 * from "hmap".
208 *
209 * If "key" is not mapped to anything, then we leave "hmap" untouched"
210 */
ISL_FN(ISL_HMAP,drop)211 __isl_give ISL_HMAP *ISL_FN(ISL_HMAP,drop)(__isl_take ISL_HMAP *hmap,
212 __isl_take ISL_KEY *key)
213 {
214 struct isl_hash_table_entry *entry;
215 ISL_S(pair) *pair;
216 uint32_t hash;
217
218 if (!hmap || !key)
219 goto error;
220
221 hash = ISL_FN(ISL_KEY,get_hash)(key);
222 entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash,
223 &has_key, key, 0);
224 if (!entry) {
225 ISL_FN(ISL_KEY,free)(key);
226 return hmap;
227 }
228
229 hmap = ISL_FN(ISL_HMAP,cow)(hmap);
230 if (!hmap)
231 goto error;
232 entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash,
233 &has_key, key, 0);
234 ISL_FN(ISL_KEY,free)(key);
235
236 if (!entry)
237 isl_die(hmap->ctx, isl_error_internal,
238 "missing entry" , goto error);
239
240 pair = entry->data;
241 isl_hash_table_remove(hmap->ctx, &hmap->table, entry);
242 ISL_FN(ISL_KEY,free)(pair->key);
243 ISL_FN(ISL_VAL,free)(pair->val);
244 free(pair);
245
246 return hmap;
247 error:
248 ISL_FN(ISL_KEY,free)(key);
249 ISL_FN(ISL_HMAP,free)(hmap);
250 return NULL;
251 }
252
253 /* Add a mapping from "key" to "val" to "hmap".
254 * If "key" was already mapped to something else, then that mapping
255 * is replaced.
256 * If key happened to be mapped to "val" already, then we leave
257 * "hmap" untouched.
258 */
ISL_FN(ISL_HMAP,set)259 __isl_give ISL_HMAP *ISL_FN(ISL_HMAP,set)(__isl_take ISL_HMAP *hmap,
260 __isl_take ISL_KEY *key, __isl_take ISL_VAL *val)
261 {
262 struct isl_hash_table_entry *entry;
263 ISL_S(pair) *pair;
264 uint32_t hash;
265
266 if (!hmap || !key || !val)
267 goto error;
268
269 hash = ISL_FN(ISL_KEY,get_hash)(key);
270 entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash,
271 &has_key, key, 0);
272 if (entry) {
273 int equal;
274 pair = entry->data;
275 equal = ISL_VAL_IS_EQUAL(pair->val, val);
276 if (equal < 0)
277 goto error;
278 if (equal) {
279 ISL_FN(ISL_KEY,free)(key);
280 ISL_FN(ISL_VAL,free)(val);
281 return hmap;
282 }
283 }
284
285 hmap = ISL_FN(ISL_HMAP,cow)(hmap);
286 if (!hmap)
287 goto error;
288
289 entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash,
290 &has_key, key, 1);
291
292 if (!entry)
293 goto error;
294
295 if (entry->data) {
296 pair = entry->data;
297 ISL_FN(ISL_VAL,free)(pair->val);
298 pair->val = val;
299 ISL_FN(ISL_KEY,free)(key);
300 return hmap;
301 }
302
303 pair = isl_alloc_type(hmap->ctx, ISL_S(pair));
304 if (!pair)
305 goto error;
306
307 entry->data = pair;
308 pair->key = key;
309 pair->val = val;
310 return hmap;
311 error:
312 ISL_FN(ISL_KEY,free)(key);
313 ISL_FN(ISL_VAL,free)(val);
314 return ISL_FN(ISL_HMAP,free)(hmap);
315 }
316
317 /* Internal data structure for isl_map_to_basic_set_foreach.
318 *
319 * fn is the function that should be called on each entry.
320 * user is the user-specified final argument to fn.
321 */
ISL_S(foreach_data)322 ISL_S(foreach_data) {
323 isl_stat (*fn)(__isl_take ISL_KEY *key, __isl_take ISL_VAL *val,
324 void *user);
325 void *user;
326 };
327
328 /* Call data->fn on a copy of the key and value in *entry.
329 */
call_on_copy(void ** entry,void * user)330 static isl_stat call_on_copy(void **entry, void *user)
331 {
332 ISL_S(pair) *pair = *entry;
333 ISL_S(foreach_data) *data = (ISL_S(foreach_data) *) user;
334
335 return data->fn(ISL_FN(ISL_KEY,copy)(pair->key),
336 ISL_FN(ISL_VAL,copy)(pair->val), data->user);
337 }
338
339 /* Call "fn" on each pair of key and value in "hmap".
340 */
ISL_FN(ISL_HMAP,foreach)341 isl_stat ISL_FN(ISL_HMAP,foreach)(__isl_keep ISL_HMAP *hmap,
342 isl_stat (*fn)(__isl_take ISL_KEY *key, __isl_take ISL_VAL *val,
343 void *user),
344 void *user)
345 {
346 ISL_S(foreach_data) data = { fn, user };
347
348 if (!hmap)
349 return isl_stat_error;
350
351 return isl_hash_table_foreach(hmap->ctx, &hmap->table,
352 &call_on_copy, &data);
353 }
354
355 /* Internal data structure for print_pair.
356 *
357 * p is the printer on which the associative array is being printed.
358 * first is set if the current key-value pair is the first to be printed.
359 */
ISL_S(print_data)360 ISL_S(print_data) {
361 isl_printer *p;
362 int first;
363 };
364
365 /* Print the given key-value pair to data->p.
366 */
print_pair(__isl_take ISL_KEY * key,__isl_take ISL_VAL * val,void * user)367 static isl_stat print_pair(__isl_take ISL_KEY *key, __isl_take ISL_VAL *val,
368 void *user)
369 {
370 ISL_S(print_data) *data = user;
371
372 if (!data->first)
373 data->p = isl_printer_print_str(data->p, ", ");
374 data->p = ISL_KEY_PRINT(data->p, key);
375 data->p = isl_printer_print_str(data->p, ": ");
376 data->p = ISL_VAL_PRINT(data->p, val);
377 data->first = 0;
378
379 ISL_FN(ISL_KEY,free)(key);
380 ISL_FN(ISL_VAL,free)(val);
381 return isl_stat_ok;
382 }
383
384 /* Print the associative array to "p".
385 */
ISL_FN(isl_printer_print,ISL_HMAP_SUFFIX)386 __isl_give isl_printer *ISL_FN(isl_printer_print,ISL_HMAP_SUFFIX)(
387 __isl_take isl_printer *p, __isl_keep ISL_HMAP *hmap)
388 {
389 ISL_S(print_data) data;
390
391 if (!p || !hmap)
392 return isl_printer_free(p);
393
394 p = isl_printer_print_str(p, "{");
395 data.p = p;
396 data.first = 1;
397 if (ISL_FN(ISL_HMAP,foreach)(hmap, &print_pair, &data) < 0)
398 data.p = isl_printer_free(data.p);
399 p = data.p;
400 p = isl_printer_print_str(p, "}");
401
402 return p;
403 }
404
ISL_FN(ISL_HMAP,dump)405 void ISL_FN(ISL_HMAP,dump)(__isl_keep ISL_HMAP *hmap)
406 {
407 isl_printer *printer;
408
409 if (!hmap)
410 return;
411
412 printer = isl_printer_to_file(ISL_FN(ISL_HMAP,get_ctx)(hmap), stderr);
413 printer = ISL_FN(isl_printer_print,ISL_HMAP_SUFFIX)(printer, hmap);
414 printer = isl_printer_end_line(printer);
415
416 isl_printer_free(printer);
417 }
418