include/isl/hmap_templ.c

   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 __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
  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
  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
  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  */
  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
  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
 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
 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
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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 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  */
 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  */
 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 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  */
 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
 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 }