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 #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
  31 ISL_S(pair) {
  32         ISL_KEY *key;
  33         ISL_VAL *val;
  34 };
  35
  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
  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
  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
  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  */
  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
  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
 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
 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
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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
 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  */
 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  */
 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  */
 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