Line data Source code
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 :
30 : ISL_S(pair) {
31 : ISL_KEY *key;
32 : ISL_VAL *val;
33 : };
34 :
35 0 : __isl_give ISL_HMAP *ISL_FN(ISL_HMAP,alloc)(isl_ctx *ctx, int min_size)
36 : {
37 : ISL_HMAP *hmap;
38 :
39 0 : hmap = isl_calloc_type(ctx, ISL_HMAP);
40 0 : if (!hmap)
41 0 : return NULL;
42 :
43 0 : hmap->ctx = ctx;
44 0 : isl_ctx_ref(ctx);
45 0 : hmap->ref = 1;
46 :
47 0 : if (isl_hash_table_init(ctx, &hmap->table, min_size) < 0)
48 0 : return ISL_FN(ISL_HMAP,free)(hmap);
49 :
50 0 : return hmap;
51 : }
52 :
53 0 : static isl_stat free_pair(void **entry, void *user)
54 : {
55 0 : ISL_S(pair) *pair = *entry;
56 0 : ISL_FN(ISL_KEY,free)(pair->key);
57 0 : ISL_FN(ISL_VAL,free)(pair->val);
58 0 : free(pair);
59 0 : *entry = NULL;
60 0 : return isl_stat_ok;
61 : }
62 :
63 225882 : __isl_null ISL_HMAP *ISL_FN(ISL_HMAP,free)(__isl_take ISL_HMAP *hmap)
64 : {
65 225882 : if (!hmap)
66 225882 : return NULL;
67 0 : if (--hmap->ref > 0)
68 0 : return NULL;
69 0 : isl_hash_table_foreach(hmap->ctx, &hmap->table, &free_pair, NULL);
70 0 : isl_hash_table_clear(&hmap->table);
71 0 : isl_ctx_deref(hmap->ctx);
72 0 : free(hmap);
73 0 : return NULL;
74 : }
75 :
76 0 : isl_ctx *ISL_FN(ISL_HMAP,get_ctx)(__isl_keep ISL_HMAP *hmap)
77 : {
78 0 : 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 : */
84 0 : static isl_stat add_key_val(__isl_take ISL_KEY *key, __isl_take ISL_VAL *val,
85 : void *user)
86 : {
87 0 : ISL_HMAP **hmap = (ISL_HMAP **) user;
88 :
89 0 : *hmap = ISL_FN(ISL_HMAP,set)(*hmap, key, val);
90 :
91 0 : if (!*hmap)
92 0 : return isl_stat_error;
93 :
94 0 : return isl_stat_ok;
95 : }
96 :
97 0 : __isl_give ISL_HMAP *ISL_FN(ISL_HMAP,dup)(__isl_keep ISL_HMAP *hmap)
98 : {
99 : ISL_HMAP *dup;
100 :
101 0 : if (!hmap)
102 0 : return NULL;
103 :
104 0 : dup = ISL_FN(ISL_HMAP,alloc)(hmap->ctx, hmap->table.n);
105 0 : if (ISL_FN(ISL_HMAP,foreach)(hmap, &add_key_val, &dup) < 0)
106 0 : return ISL_FN(ISL_HMAP,free)(dup);
107 :
108 0 : return dup;
109 : }
110 :
111 0 : __isl_give ISL_HMAP *ISL_FN(ISL_HMAP,cow)(__isl_take ISL_HMAP *hmap)
112 : {
113 0 : if (!hmap)
114 0 : return NULL;
115 :
116 0 : if (hmap->ref == 1)
117 0 : return hmap;
118 0 : hmap->ref--;
119 0 : return ISL_FN(ISL_HMAP,dup)(hmap);
120 : }
121 :
122 0 : __isl_give ISL_HMAP *ISL_FN(ISL_HMAP,copy)(__isl_keep ISL_HMAP *hmap)
123 : {
124 0 : if (!hmap)
125 0 : return NULL;
126 :
127 0 : hmap->ref++;
128 0 : return hmap;
129 : }
130 :
131 0 : static int has_key(const void *entry, const void *c_key)
132 : {
133 0 : const ISL_S(pair) *pair = entry;
134 0 : ISL_KEY *key = (ISL_KEY *) c_key;
135 :
136 0 : 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 : */
146 0 : __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 0 : ISL_MAYBE(ISL_VAL) res = { isl_bool_false, NULL };
153 :
154 0 : if (!hmap || !key)
155 : goto error;
156 :
157 0 : hash = ISL_FN(ISL_KEY,get_hash)(key);
158 0 : entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash,
159 : &has_key, key, 0);
160 :
161 0 : if (!entry)
162 0 : return res;
163 :
164 0 : pair = entry->data;
165 :
166 0 : res.valid = isl_bool_true;
167 0 : res.value = ISL_FN(ISL_VAL,copy)(pair->val);
168 0 : if (!res.value)
169 0 : res.valid = isl_bool_error;
170 0 : return res;
171 : error:
172 0 : res.valid = isl_bool_error;
173 0 : res.value = NULL;
174 0 : 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 : */
181 0 : 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 0 : res = ISL_FN(ISL_HMAP,try_get)(hmap, key);
187 0 : ISL_FN(ISL_VAL,free)(res.value);
188 :
189 0 : 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 : */
196 0 : __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 0 : res = ISL_FN(ISL_HMAP,try_get)(hmap, key).value;
202 0 : ISL_FN(ISL_KEY,free)(key);
203 0 : 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 : */
211 0 : __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 0 : if (!hmap || !key)
219 : goto error;
220 :
221 0 : hash = ISL_FN(ISL_KEY,get_hash)(key);
222 0 : entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash,
223 : &has_key, key, 0);
224 0 : if (!entry) {
225 0 : ISL_FN(ISL_KEY,free)(key);
226 0 : return hmap;
227 : }
228 :
229 0 : hmap = ISL_FN(ISL_HMAP,cow)(hmap);
230 0 : if (!hmap)
231 0 : goto error;
232 0 : entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash,
233 : &has_key, key, 0);
234 0 : ISL_FN(ISL_KEY,free)(key);
235 :
236 0 : if (!entry)
237 0 : isl_die(hmap->ctx, isl_error_internal,
238 : "missing entry" , goto error);
239 :
240 0 : pair = entry->data;
241 0 : isl_hash_table_remove(hmap->ctx, &hmap->table, entry);
242 0 : ISL_FN(ISL_KEY,free)(pair->key);
243 0 : ISL_FN(ISL_VAL,free)(pair->val);
244 0 : free(pair);
245 :
246 0 : return hmap;
247 : error:
248 0 : ISL_FN(ISL_KEY,free)(key);
249 0 : ISL_FN(ISL_HMAP,free)(hmap);
250 0 : 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 : */
259 0 : __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 0 : if (!hmap || !key || !val)
267 : goto error;
268 :
269 0 : hash = ISL_FN(ISL_KEY,get_hash)(key);
270 0 : entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash,
271 : &has_key, key, 0);
272 0 : if (entry) {
273 : int equal;
274 0 : pair = entry->data;
275 0 : equal = ISL_VAL_IS_EQUAL(pair->val, val);
276 0 : if (equal < 0)
277 0 : goto error;
278 0 : if (equal) {
279 0 : ISL_FN(ISL_KEY,free)(key);
280 0 : ISL_FN(ISL_VAL,free)(val);
281 0 : return hmap;
282 : }
283 : }
284 :
285 0 : hmap = ISL_FN(ISL_HMAP,cow)(hmap);
286 0 : if (!hmap)
287 0 : goto error;
288 :
289 0 : entry = isl_hash_table_find(hmap->ctx, &hmap->table, hash,
290 : &has_key, key, 1);
291 :
292 0 : if (!entry)
293 0 : goto error;
294 :
295 0 : if (entry->data) {
296 0 : pair = entry->data;
297 0 : ISL_FN(ISL_VAL,free)(pair->val);
298 0 : pair->val = val;
299 0 : ISL_FN(ISL_KEY,free)(key);
300 0 : return hmap;
301 : }
302 :
303 0 : pair = isl_alloc_type(hmap->ctx, ISL_S(pair));
304 0 : if (!pair)
305 0 : goto error;
306 :
307 0 : entry->data = pair;
308 0 : pair->key = key;
309 0 : pair->val = val;
310 0 : return hmap;
311 : error:
312 0 : ISL_FN(ISL_KEY,free)(key);
313 0 : ISL_FN(ISL_VAL,free)(val);
314 0 : 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 : */
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 : */
330 0 : static isl_stat call_on_copy(void **entry, void *user)
331 : {
332 0 : ISL_S(pair) *pair = *entry;
333 0 : ISL_S(foreach_data) *data = (ISL_S(foreach_data) *) user;
334 :
335 0 : 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 : */
341 0 : 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 0 : ISL_S(foreach_data) data = { fn, user };
347 :
348 0 : if (!hmap)
349 0 : return isl_stat_error;
350 :
351 0 : 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 : */
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 : */
367 0 : static isl_stat print_pair(__isl_take ISL_KEY *key, __isl_take ISL_VAL *val,
368 : void *user)
369 : {
370 0 : ISL_S(print_data) *data = user;
371 :
372 0 : if (!data->first)
373 0 : data->p = isl_printer_print_str(data->p, ", ");
374 0 : data->p = ISL_KEY_PRINT(data->p, key);
375 0 : data->p = isl_printer_print_str(data->p, ": ");
376 0 : data->p = ISL_VAL_PRINT(data->p, val);
377 0 : data->first = 0;
378 :
379 0 : ISL_FN(ISL_KEY,free)(key);
380 0 : ISL_FN(ISL_VAL,free)(val);
381 0 : return isl_stat_ok;
382 : }
383 :
384 : /* Print the associative array to "p".
385 : */
386 0 : __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 0 : if (!p || !hmap)
392 0 : return isl_printer_free(p);
393 :
394 0 : p = isl_printer_print_str(p, "{");
395 0 : data.p = p;
396 0 : data.first = 1;
397 0 : if (ISL_FN(ISL_HMAP,foreach)(hmap, &print_pair, &data) < 0)
398 0 : data.p = isl_printer_free(data.p);
399 0 : p = data.p;
400 0 : p = isl_printer_print_str(p, "}");
401 :
402 0 : return p;
403 : }
404 :
405 0 : void ISL_FN(ISL_HMAP,dump)(__isl_keep ISL_HMAP *hmap)
406 : {
407 : isl_printer *printer;
408 :
409 0 : if (!hmap)
410 0 : return;
411 :
412 0 : printer = isl_printer_to_file(ISL_FN(ISL_HMAP,get_ctx)(hmap), stderr);
413 0 : printer = ISL_FN(isl_printer_print,ISL_HMAP_SUFFIX)(printer, hmap);
414 0 : printer = isl_printer_end_line(printer);
415 :
416 0 : isl_printer_free(printer);
417 : }
|
