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 #include <isl/stream.h>
16
17 #define ISL_xCAT(A,B) A ## B
18 #define ISL_CAT(A,B) ISL_xCAT(A,B)
19 #define ISL_xFN(TYPE,NAME) TYPE ## _ ## NAME
20 #define ISL_FN(TYPE,NAME) ISL_xFN(TYPE,NAME)
21 #define ISL_xS(TYPE1,TYPE2,NAME) struct isl_ ## TYPE1 ## _ ## TYPE2 ## _ ## NAME
22 #define ISL_yS(TYPE1,TYPE2,NAME) ISL_xS(TYPE1,TYPE2,NAME)
23 #define ISL_S(NAME) ISL_yS(ISL_KEY,ISL_VAL,NAME)
24
25 struct ISL_HMAP {
26 int ref;
27 isl_ctx *ctx;
28 struct isl_hash_table table;
29 };
30
ISL_S(pair)31 ISL_S(pair) {
32 ISL_KEY *key;
33 ISL_VAL *val;
34 };
35
ISL_FN(ISL_HMAP,alloc)36 __isl_give ISL_HMAP *ISL_FN(ISL_HMAP,alloc)(isl_ctx *ctx, int min_size)
37 {
38 ISL_HMAP *hmap;
39
40 hmap = isl_calloc_type(ctx, ISL_HMAP);
41 if (!hmap)
42 return NULL;
43
44 hmap->ctx = ctx;
45 isl_ctx_ref(ctx);
46 hmap->ref = 1;
47
48 if (isl_hash_table_init(ctx, &hmap->table, min_size) < 0)
49 return ISL_FN(ISL_HMAP,free)(hmap);
50
51 return hmap;
52 }
53
free_pair(void ** entry,void * user)54 static isl_stat free_pair(void **entry, void *user)
55 {
56 ISL_S(pair) *pair = *entry;
57 ISL_FN(ISL_KEY,free)(pair->key);
58 ISL_FN(ISL_VAL,free)(pair->val);
59 free(pair);
60 *entry = NULL;
61 return isl_stat_ok;
62 }
63
ISL_FN(ISL_HMAP,free)64 __isl_null ISL_HMAP *ISL_FN(ISL_HMAP,free)(__isl_take ISL_HMAP *hmap)
65 {
66 if (!hmap)
67 return NULL;
68 if (--hmap->ref > 0)
69 return NULL;
70 isl_hash_table_foreach(hmap->ctx, &hmap->table, &free_pair, NULL);
71 isl_hash_table_clear(&hmap->table);
72 isl_ctx_deref(hmap->ctx);
73 free(hmap);
74 return NULL;
75 }
76
ISL_FN(ISL_HMAP,get_ctx)77 isl_ctx *ISL_FN(ISL_HMAP,get_ctx)(__isl_keep ISL_HMAP *hmap)
78 {
79 return hmap ? hmap->ctx : NULL;
80 }
81
82 /* Add a mapping from "key" to "val" to the associative array
83 * pointed to by user.
84 */
add_key_val(__isl_take ISL_KEY * key,__isl_take ISL_VAL * val,void * user)85 static isl_stat add_key_val(__isl_take ISL_KEY *key, __isl_take ISL_VAL *val,
86 void *user)
87 {
88 ISL_HMAP **hmap = (ISL_HMAP **) user;
89
90 *hmap = ISL_FN(ISL_HMAP,set)(*hmap, key, val);
91
92 if (!*hmap)
93 return isl_stat_error;
94
95 return isl_stat_ok;
96 }
97
ISL_FN(ISL_HMAP,dup)98 __isl_give ISL_HMAP *ISL_FN(ISL_HMAP,dup)(__isl_keep ISL_HMAP *hmap)
99 {
100 ISL_HMAP *dup;
101
102 if (!hmap)
103 return NULL;
104
105 dup = ISL_FN(ISL_HMAP,alloc)(hmap->ctx, hmap->table.n);
106 if (ISL_FN(ISL_HMAP,foreach)(hmap, &add_key_val, &dup) < 0)
107 return ISL_FN(ISL_HMAP,free)(dup);
108
109 return dup;
110 }
111
ISL_FN(ISL_HMAP,cow)112 __isl_give ISL_HMAP *ISL_FN(ISL_HMAP,cow)(__isl_take ISL_HMAP *hmap)
113 {
114 if (!hmap)
115 return NULL;
116
117 if (hmap->ref == 1)
118 return hmap;
119 hmap->ref--;
120 return ISL_FN(ISL_HMAP,dup)(hmap);
121 }
122
ISL_FN(ISL_HMAP,copy)123 __isl_give ISL_HMAP *ISL_FN(ISL_HMAP,copy)(__isl_keep ISL_HMAP *hmap)
124 {
125 if (!hmap)
126 return NULL;
127
128 hmap->ref++;
129 return hmap;
130 }
131
has_key(const void * entry,const void * c_key)132 static isl_bool has_key(const void *entry, const void *c_key)
133 {
134 const ISL_S(pair) *pair = entry;
135 ISL_KEY *key = (ISL_KEY *) c_key;
136
137 return ISL_KEY_IS_EQUAL(pair->key, key);
138 }
139
140 /* If "hmap" contains a value associated to "key", then return
141 * (isl_bool_true, copy of value).
142 * Otherwise, return
143 * (isl_bool_false, NULL).
144 * If an error occurs, then return
145 * (isl_bool_error, NULL).
146 */
ISL_MAYBE(ISL_VAL)147 __isl_give ISL_MAYBE(ISL_VAL) ISL_FN(ISL_HMAP,try_get)(
148 __isl_keep ISL_HMAP *hmap, __isl_keep ISL_KEY *key)
149 {
150 struct isl_hash_table_entry *entry;
151 ISL_S(pair) *pair;
152 uint32_t hash;
153 ISL_MAYBE(ISL_VAL) res = { isl_bool_false, NULL };
154
155 if (!hmap || !key)
156 goto error;
157
158 hash = ISL_FN(ISL_KEY,get_hash)(key);
159 entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash,
160 &has_key, key, 0);
161
162 if (!entry)
163 goto error;
164 if (entry == isl_hash_table_entry_none)
165 return res;
166
167 pair = entry->data;
168
169 res.valid = isl_bool_true;
170 res.value = ISL_FN(ISL_VAL,copy)(pair->val);
171 if (!res.value)
172 res.valid = isl_bool_error;
173 return res;
174 error:
175 res.valid = isl_bool_error;
176 res.value = NULL;
177 return res;
178 }
179
180 /* If "hmap" contains a value associated to "key", then return
181 * isl_bool_true. Otherwise, return isl_bool_false.
182 * Return isl_bool_error on error.
183 */
ISL_FN(ISL_HMAP,has)184 isl_bool ISL_FN(ISL_HMAP,has)(__isl_keep ISL_HMAP *hmap,
185 __isl_keep ISL_KEY *key)
186 {
187 ISL_MAYBE(ISL_VAL) res;
188
189 res = ISL_FN(ISL_HMAP,try_get)(hmap, key);
190 ISL_FN(ISL_VAL,free)(res.value);
191
192 return res.valid;
193 }
194
195 /* If "hmap" contains a value associated to "key", then return
196 * a copy of that value. Otherwise, return NULL.
197 * Return NULL on error.
198 */
ISL_FN(ISL_HMAP,get)199 __isl_give ISL_VAL *ISL_FN(ISL_HMAP,get)(__isl_keep ISL_HMAP *hmap,
200 __isl_take ISL_KEY *key)
201 {
202 ISL_VAL *res;
203
204 res = ISL_FN(ISL_HMAP,try_get)(hmap, key).value;
205 ISL_FN(ISL_KEY,free)(key);
206 return res;
207 }
208
209 /* Remove the mapping between "key" and its associated value (if any)
210 * from "hmap".
211 *
212 * If "key" is not mapped to anything, then we leave "hmap" untouched"
213 */
ISL_FN(ISL_HMAP,drop)214 __isl_give ISL_HMAP *ISL_FN(ISL_HMAP,drop)(__isl_take ISL_HMAP *hmap,
215 __isl_take ISL_KEY *key)
216 {
217 struct isl_hash_table_entry *entry;
218 ISL_S(pair) *pair;
219 uint32_t hash;
220
221 if (!hmap || !key)
222 goto error;
223
224 hash = ISL_FN(ISL_KEY,get_hash)(key);
225 entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash,
226 &has_key, key, 0);
227 if (!entry)
228 goto error;
229 if (entry == isl_hash_table_entry_none) {
230 ISL_FN(ISL_KEY,free)(key);
231 return hmap;
232 }
233
234 hmap = ISL_FN(ISL_HMAP,cow)(hmap);
235 if (!hmap)
236 goto error;
237 entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash,
238 &has_key, key, 0);
239 ISL_FN(ISL_KEY,free)(key);
240
241 if (!entry)
242 return ISL_FN(ISL_HMAP,free)(hmap);
243 if (entry == isl_hash_table_entry_none)
244 isl_die(hmap->ctx, isl_error_internal,
245 "missing entry" , return ISL_FN(ISL_HMAP,free)(hmap));
246
247 pair = entry->data;
248 isl_hash_table_remove(hmap->ctx, &hmap->table, entry);
249 ISL_FN(ISL_KEY,free)(pair->key);
250 ISL_FN(ISL_VAL,free)(pair->val);
251 free(pair);
252
253 return hmap;
254 error:
255 ISL_FN(ISL_KEY,free)(key);
256 ISL_FN(ISL_HMAP,free)(hmap);
257 return NULL;
258 }
259
260 /* Add a mapping from "key" to "val" to "hmap".
261 * If "key" was already mapped to something else, then that mapping
262 * is replaced.
263 * If key happened to be mapped to "val" already, then we leave
264 * "hmap" untouched.
265 */
ISL_FN(ISL_HMAP,set)266 __isl_give ISL_HMAP *ISL_FN(ISL_HMAP,set)(__isl_take ISL_HMAP *hmap,
267 __isl_take ISL_KEY *key, __isl_take ISL_VAL *val)
268 {
269 struct isl_hash_table_entry *entry;
270 ISL_S(pair) *pair;
271 uint32_t hash;
272
273 if (!hmap || !key || !val)
274 goto error;
275
276 hash = ISL_FN(ISL_KEY,get_hash)(key);
277 entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash,
278 &has_key, key, 0);
279 if (!entry)
280 goto error;
281 if (entry != isl_hash_table_entry_none) {
282 isl_bool equal;
283 pair = entry->data;
284 equal = ISL_VAL_IS_EQUAL(pair->val, val);
285 if (equal < 0)
286 goto error;
287 if (equal) {
288 ISL_FN(ISL_KEY,free)(key);
289 ISL_FN(ISL_VAL,free)(val);
290 return hmap;
291 }
292 }
293
294 hmap = ISL_FN(ISL_HMAP,cow)(hmap);
295 if (!hmap)
296 goto error;
297
298 entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash,
299 &has_key, key, 1);
300
301 if (!entry)
302 goto error;
303
304 if (entry->data) {
305 pair = entry->data;
306 ISL_FN(ISL_VAL,free)(pair->val);
307 pair->val = val;
308 ISL_FN(ISL_KEY,free)(key);
309 return hmap;
310 }
311
312 pair = isl_alloc_type(hmap->ctx, ISL_S(pair));
313 if (!pair)
314 goto error;
315
316 entry->data = pair;
317 pair->key = key;
318 pair->val = val;
319 return hmap;
320 error:
321 ISL_FN(ISL_KEY,free)(key);
322 ISL_FN(ISL_VAL,free)(val);
323 return ISL_FN(ISL_HMAP,free)(hmap);
324 }
325
326 /* Internal data structure for isl_*_to_*_foreach.
327 *
328 * fn is the function that should be called on each entry.
329 * user is the user-specified final argument to fn.
330 */
ISL_S(foreach_data)331 ISL_S(foreach_data) {
332 isl_stat (*fn)(__isl_take ISL_KEY *key, __isl_take ISL_VAL *val,
333 void *user);
334 void *user;
335 };
336
337 /* Call data->fn on a copy of the key and value in *entry.
338 */
call_on_copy(void ** entry,void * user)339 static isl_stat call_on_copy(void **entry, void *user)
340 {
341 ISL_S(pair) *pair = *entry;
342 ISL_S(foreach_data) *data = (ISL_S(foreach_data) *) user;
343
344 return data->fn(ISL_FN(ISL_KEY,copy)(pair->key),
345 ISL_FN(ISL_VAL,copy)(pair->val), data->user);
346 }
347
348 /* Call "fn" on each pair of key and value in "hmap".
349 */
ISL_FN(ISL_HMAP,foreach)350 isl_stat ISL_FN(ISL_HMAP,foreach)(__isl_keep ISL_HMAP *hmap,
351 isl_stat (*fn)(__isl_take ISL_KEY *key, __isl_take ISL_VAL *val,
352 void *user),
353 void *user)
354 {
355 ISL_S(foreach_data) data = { fn, user };
356
357 if (!hmap)
358 return isl_stat_error;
359
360 return isl_hash_table_foreach(hmap->ctx, &hmap->table,
361 &call_on_copy, &data);
362 }
363
364 /* Internal data structure for isl_*_to_*_every.
365 *
366 * "test" is the function that should be called on each entry,
367 * until any invocation returns isl_bool_false.
368 * "test_user" is the user-specified final argument to "test".
369 */
ISL_S(every_data)370 ISL_S(every_data) {
371 isl_bool (*test)(__isl_keep ISL_KEY *key, __isl_keep ISL_VAL *val,
372 void *user);
373 void *test_user;
374 };
375
376 /* Call data->test on the key and value in *entry.
377 */
call_on_pair(void ** entry,void * user)378 static isl_bool call_on_pair(void **entry, void *user)
379 {
380 ISL_S(pair) *pair = *entry;
381 ISL_S(every_data) *data = (ISL_S(every_data) *) user;
382
383 return data->test(pair->key, pair->val, data->test_user);
384 }
385
386 /* Does "test" succeed on every entry of "hmap"?
387 */
ISL_FN(ISL_HMAP,every)388 isl_bool ISL_FN(ISL_HMAP,every)(__isl_keep ISL_HMAP *hmap,
389 isl_bool (*test)(__isl_keep ISL_KEY *key, __isl_keep ISL_VAL *val,
390 void *user),
391 void *user)
392 {
393 ISL_S(every_data) data = { test, user };
394
395 if (!hmap)
396 return isl_bool_error;
397
398 return isl_hash_table_every(hmap->ctx, &hmap->table,
399 &call_on_pair, &data);
400 }
401
402 #ifdef ISL_HMAP_IS_EQUAL
403
404 /* Does "hmap" have an entry with key "key" and value "val"?
405 */
has_entry(__isl_keep ISL_KEY * key,__isl_keep ISL_VAL * val,void * user)406 static isl_bool has_entry(__isl_keep ISL_KEY *key, __isl_keep ISL_VAL *val,
407 void *user)
408 {
409 ISL_HMAP *hmap = user;
410 ISL_MAYBE(ISL_VAL) maybe_val;
411 isl_bool equal;
412
413 maybe_val = ISL_FN(ISL_HMAP,try_get)(hmap, key);
414 if (maybe_val.valid < 0 || !maybe_val.valid)
415 return maybe_val.valid;
416 equal = ISL_VAL_IS_EQUAL(maybe_val.value, val);
417 ISL_FN(ISL_VAL,free)(maybe_val.value);
418 return equal;
419 }
420
421 /* Is "hmap1" (obviously) equal to "hmap2"?
422 *
423 * In particular, do the two associative arrays have
424 * the same number of entries and does every entry of the first
425 * also appear in the second?
426 */
ISL_HMAP_IS_EQUAL(__isl_keep ISL_HMAP * hmap1,__isl_keep ISL_HMAP * hmap2)427 isl_bool ISL_HMAP_IS_EQUAL(__isl_keep ISL_HMAP *hmap1,
428 __isl_keep ISL_HMAP *hmap2)
429 {
430 if (!hmap1 || !hmap2)
431 return isl_bool_error;
432 if (hmap1 == hmap2)
433 return isl_bool_true;
434 if (hmap1->table.n != hmap2->table.n)
435 return isl_bool_false;
436 return ISL_FN(ISL_HMAP,every)(hmap1, &has_entry, hmap2);
437 }
438
439 #endif
440
441 /* Internal data structure for print_pair.
442 *
443 * p is the printer on which the associative array is being printed.
444 * first is set if the current key-value pair is the first to be printed.
445 */
ISL_S(print_data)446 ISL_S(print_data) {
447 isl_printer *p;
448 int first;
449 };
450
451 /* Print the given key-value pair to data->p.
452 */
print_pair(__isl_take ISL_KEY * key,__isl_take ISL_VAL * val,void * user)453 static isl_stat print_pair(__isl_take ISL_KEY *key, __isl_take ISL_VAL *val,
454 void *user)
455 {
456 ISL_S(print_data) *data = user;
457
458 if (!data->first)
459 data->p = isl_printer_print_str(data->p, ", ");
460 data->p = ISL_KEY_PRINT(data->p, key);
461 data->p = isl_printer_print_str(data->p, ": ");
462 data->p = ISL_VAL_PRINT(data->p, val);
463 data->first = 0;
464
465 ISL_FN(ISL_KEY,free)(key);
466 ISL_FN(ISL_VAL,free)(val);
467 return isl_stat_ok;
468 }
469
470 /* Print the associative array to "p".
471 */
ISL_FN(isl_printer_print,ISL_HMAP_SUFFIX)472 __isl_give isl_printer *ISL_FN(isl_printer_print,ISL_HMAP_SUFFIX)(
473 __isl_take isl_printer *p, __isl_keep ISL_HMAP *hmap)
474 {
475 ISL_S(print_data) data;
476
477 if (!p || !hmap)
478 return isl_printer_free(p);
479
480 p = isl_printer_print_str(p, "{");
481 data.p = p;
482 data.first = 1;
483 if (ISL_FN(ISL_HMAP,foreach)(hmap, &print_pair, &data) < 0)
484 data.p = isl_printer_free(data.p);
485 p = data.p;
486 p = isl_printer_print_str(p, "}");
487
488 return p;
489 }
490
ISL_FN(ISL_HMAP,dump)491 void ISL_FN(ISL_HMAP,dump)(__isl_keep ISL_HMAP *hmap)
492 {
493 isl_printer *printer;
494
495 if (!hmap)
496 return;
497
498 printer = isl_printer_to_file(ISL_FN(ISL_HMAP,get_ctx)(hmap), stderr);
499 printer = ISL_FN(isl_printer_print,ISL_HMAP_SUFFIX)(printer, hmap);
500 printer = isl_printer_end_line(printer);
501
502 isl_printer_free(printer);
503 }
504
505 /* Return a string representation of "hmap".
506 */
ISL_FN(ISL_HMAP,to_str)507 __isl_give char *ISL_FN(ISL_HMAP,to_str)(__isl_keep ISL_HMAP *hmap)
508 {
509 isl_printer *p;
510 char *s;
511
512 if (!hmap)
513 return NULL;
514 p = isl_printer_to_str(ISL_FN(ISL_HMAP,get_ctx)(hmap));
515 p = ISL_FN(isl_printer_print,ISL_HMAP_SUFFIX)(p, hmap);
516 s = isl_printer_get_str(p);
517 isl_printer_free(p);
518
519 return s;
520 }
521
522 #ifdef ISL_HMAP_HAVE_READ_FROM_STR
523
524 /* Read an associative array from "s".
525 * The input format corresponds to the way associative arrays are printed
526 * by isl_printer_print_*_to_*.
527 * In particular, each key-value pair is separated by a colon,
528 * the key-value pairs are separated by a comma and
529 * the entire associative array is surrounded by braces.
530 */
ISL_FN(isl_stream_read,ISL_HMAP_SUFFIX)531 __isl_give ISL_HMAP *ISL_FN(isl_stream_read,ISL_HMAP_SUFFIX)(isl_stream *s)
532 {
533 isl_ctx *ctx;
534 ISL_HMAP *hmap;
535
536 if (!s)
537 return NULL;
538 ctx = isl_stream_get_ctx(s);
539 hmap = ISL_FN(ISL_HMAP,alloc)(ctx, 0);
540 if (!hmap)
541 return NULL;
542 if (isl_stream_eat(s, '{') < 0)
543 return ISL_FN(ISL_HMAP,free)(hmap);
544 if (isl_stream_eat_if_available(s, '}'))
545 return hmap;
546 do {
547 ISL_KEY *key;
548 ISL_VAL *val = NULL;
549
550 key = ISL_KEY_READ(s);
551 if (isl_stream_eat(s, ':') >= 0)
552 val = ISL_VAL_READ(s);
553 hmap = ISL_FN(ISL_HMAP,set)(hmap, key, val);
554 if (!hmap)
555 return NULL;
556 } while (isl_stream_eat_if_available(s, ','));
557 if (isl_stream_eat(s, '}') < 0)
558 return ISL_FN(ISL_HMAP,free)(hmap);
559 return hmap;
560 }
561
562 /* Read an associative array from the string "str".
563 * The input format corresponds to the way associative arrays are printed
564 * by isl_printer_print_*_to_*.
565 * In particular, each key-value pair is separated by a colon,
566 * the key-value pairs are separated by a comma and
567 * the entire associative array is surrounded by braces.
568 */
ISL_FN(ISL_HMAP,read_from_str)569 __isl_give ISL_HMAP *ISL_FN(ISL_HMAP,read_from_str)(isl_ctx *ctx,
570 const char *str)
571 {
572 ISL_HMAP *hmap;
573 isl_stream *s;
574
575 s = isl_stream_new_str(ctx, str);
576 if (!s)
577 return NULL;
578 hmap = ISL_FN(isl_stream_read,ISL_HMAP_SUFFIX)(s);
579 isl_stream_free(s);
580 return hmap;
581 }
582
583 #endif
584