isl_union_templ.c

   1 /*
   2  * Copyright 2010      INRIA Saclay
   3  *
   4  * Use of this software is governed by the GNU LGPLv2.1 license
   5  *
   6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   8  * 91893 Orsay, France
   9  */
  10
  11 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
  12 #define FN(TYPE,NAME) xFN(TYPE,NAME)
  13 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
  14 #define S(TYPE,NAME) xS(TYPE,NAME)
  15
  16 struct UNION {
  17         int ref;
  18         isl_dim *dim;
  19
  20         struct isl_hash_table   table;
  21 };
  22
  23 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u);
  24
  25 isl_ctx *FN(UNION,get_ctx)(__isl_keep UNION *u)
  26 {
  27         return u ? u->dim->ctx : NULL;
  28 }
  29
  30 __isl_give isl_dim *FN(UNION,get_dim)(__isl_keep UNION *u)
  31 {
  32         if (!u)
  33                 return NULL;
  34         return isl_dim_copy(u->dim);
  35 }
  36
  37 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_dim *dim, int size)
  38 {
  39         UNION *u;
  40
  41         u = isl_calloc_type(ctx, UNION);
  42         if (!u)
  43                 return NULL;
  44
  45         u->ref = 1;
  46         u->dim = dim;
  47         if (isl_hash_table_init(dim->ctx, &u->table, size) < 0)
  48                 goto error;
  49
  50         return u;
  51 error:
  52         isl_dim_free(dim);
  53         FN(UNION,free)(u);
  54         return NULL;
  55 }
  56
  57 __isl_give UNION *FN(UNION,zero)(__isl_take isl_dim *dim)
  58 {
  59         return FN(UNION,alloc)(dim, 16);
  60 }
  61
  62 __isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u)
  63 {
  64         if (!u)
  65                 return NULL;
  66
  67         u->ref++;
  68         return u;
  69 }
  70
  71 S(UNION,foreach_data)
  72 {
  73         int (*fn)(__isl_take PART *part, void *user);
  74         void *user;
  75 };
  76
  77 static int call_on_copy(void **entry, void *user)
  78 {
  79         PART *part = *entry;
  80         S(UNION,foreach_data) *data = (S(UNION,foreach_data) *)user;
  81
  82         return data->fn(FN(PART,copy)(part), data->user);
  83 }
  84
  85 int FN(FN(UNION,foreach),PARTS)(__isl_keep UNION *u,
  86         int (*fn)(__isl_take PART *part, void *user), void *user)
  87 {
  88         S(UNION,foreach_data) data = { fn, user };
  89
  90         if (!u)
  91                 return -1;
  92
  93         return isl_hash_table_foreach(u->dim->ctx, &u->table,
  94                                       &call_on_copy, &data);
  95 }
  96
  97 static int has_dim(const void *entry, const void *val)
  98 {
  99         PART *part = (PART *)entry;
 100         isl_dim *dim = (isl_dim *)val;
 101
 102         return isl_dim_equal(part->dim, dim);
 103 }
 104
 105 __isl_give UNION *FN(FN(UNION,add),PARTS)(__isl_take UNION *u,
 106         __isl_take PART *part)
 107 {
 108         uint32_t hash;
 109         struct isl_hash_table_entry *entry;
 110
 111         if (!part)
 112                 goto error;
 113
 114         if (FN(PART,is_zero)(part)) {
 115                 FN(PART,free)(part);
 116                 return u;
 117         }
 118
 119         u = FN(UNION,cow)(u);
 120
 121         if (!u)
 122                 goto error;
 123
 124         isl_assert(u->dim->ctx, isl_dim_match(part->dim, isl_dim_param, u->dim,
 125                                               isl_dim_param), goto error);
 126
 127         hash = isl_dim_get_hash(part->dim);
 128         entry = isl_hash_table_find(u->dim->ctx, &u->table, hash,
 129                                     &has_dim, part->dim, 1);
 130         if (!entry)
 131                 goto error;
 132
 133         if (!entry->data)
 134                 entry->data = part;
 135         else {
 136                 entry->data = FN(PART,add)(entry->data, FN(PART,copy)(part));
 137                 if (!entry->data)
 138                         goto error;
 139                 FN(PART,free)(part);
 140                 if (FN(PART,is_zero)(entry->data)) {
 141                         FN(PART,free)(entry->data);
 142                         isl_hash_table_remove(u->dim->ctx, &u->table, entry);
 143                 }
 144         }
 145
 146         return u;
 147 error:
 148         FN(PART,free)(part);
 149         FN(UNION,free)(u);
 150         return NULL;
 151 }
 152
 153 static int add_part(__isl_take PART *part, void *user)
 154 {
 155         UNION **u = (UNION **)user;
 156
 157         *u = FN(FN(UNION,add),PARTS)(*u, part);
 158
 159         return 0;
 160 }
 161
 162 __isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u)
 163 {
 164         UNION *dup;
 165
 166         if (!u)
 167                 return NULL;
 168
 169         dup = FN(UNION,zero)(isl_dim_copy(u->dim));
 170         if (FN(FN(UNION,foreach),PARTS)(u, &add_part, &dup) < 0)
 171                 goto error;
 172         return dup;
 173 error:
 174         FN(UNION,free)(dup);
 175         return NULL;
 176 }
 177
 178 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u)
 179 {
 180         if (!u)
 181                 return NULL;
 182
 183         if (u->ref == 1)
 184                 return u;
 185         u->ref--;
 186         return FN(UNION,dup)(u);
 187 }
 188
 189 static int free_u_entry(void **entry, void *user)
 190 {
 191         PART *part = *entry;
 192         FN(PART,free)(part);
 193         return 0;
 194 }
 195
 196 void FN(UNION,free)(__isl_take UNION *u)
 197 {
 198         if (!u)
 199                 return;
 200
 201         if (--u->ref > 0)
 202                 return;
 203
 204         isl_hash_table_foreach(u->dim->ctx, &u->table, &free_u_entry, NULL);
 205         isl_hash_table_clear(&u->table);
 206         isl_dim_free(u->dim);
 207         free(u);
 208 }
 209
 210 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
 211 {
 212         u1 = FN(UNION,cow)(u1);
 213
 214         if (!u1 || !u2)
 215                 goto error;
 216
 217         if (FN(FN(UNION,foreach),PARTS)(u2, &add_part, &u1) < 0)
 218                 goto error;
 219
 220         FN(UNION,free)(u2);
 221
 222         return u1;
 223 error:
 224         FN(UNION,free)(u1);
 225         FN(UNION,free)(u2);
 226         return NULL;
 227 }
 228
 229 __isl_give UNION *FN(FN(UNION,from),PARTS)(__isl_take PART *part)
 230 {
 231         isl_dim *dim;
 232         UNION *u;
 233
 234         if (!part)
 235                 return NULL;
 236
 237         dim = FN(PART,get_dim)(part);
 238         dim = isl_dim_drop(dim, isl_dim_in, 0, isl_dim_size(dim, isl_dim_in));
 239         dim = isl_dim_drop(dim, isl_dim_out, 0, isl_dim_size(dim, isl_dim_out));
 240         u = FN(UNION,zero)(dim);
 241         u = FN(FN(UNION,add),PARTS)(u, part);
 242
 243         return u;
 244 }
 245
 246 S(UNION,match_bin_data) {
 247         UNION *upwqp2;
 248         UNION *res;
 249 };
 250
 251 static __isl_give UNION *match_bin_op(__isl_take UNION *u1,
 252         __isl_take UNION *u2, int (*fn)(void **, void *))
 253 {
 254         S(UNION,match_bin_data) data = { u2, NULL };
 255
 256         if (!u1 || !u2)
 257                 goto error;
 258
 259         data.res = FN(UNION,alloc)(isl_dim_copy(u1->dim), u1->table.n);
 260         if (isl_hash_table_foreach(u1->dim->ctx, &u1->table, fn, &data) < 0)
 261                 goto error;
 262
 263         FN(UNION,free)(u1);
 264         FN(UNION,free)(u2);
 265         return data.res;
 266 error:
 267         FN(UNION,free)(u1);
 268         FN(UNION,free)(u2);
 269         FN(UNION,free)(data.res);
 270         return NULL;
 271 }
 272
 273 S(UNION,match_set_data) {
 274         isl_union_set *uset;
 275         UNION *res;
 276         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
 277 };
 278
 279 static int set_has_dim(const void *entry, const void *val)
 280 {
 281         isl_set *set = (isl_set *)entry;
 282         isl_dim *dim = (isl_dim *)val;
 283
 284         return isl_dim_equal(set->dim, dim);
 285 }
 286
 287 static int match_set_entry(void **entry, void *user)
 288 {
 289         S(UNION,match_set_data) *data = user;
 290         uint32_t hash;
 291         struct isl_hash_table_entry *entry2;
 292         isl_dim *dim;
 293         PW *pw = *entry;
 294         int empty;
 295
 296         hash = isl_dim_get_hash(pw->dim);
 297         entry2 = isl_hash_table_find(data->uset->dim->ctx, &data->uset->table,
 298                                      hash, &set_has_dim, pw->dim, 0);
 299         if (!entry2)
 300                 return 0;
 301
 302         pw = FN(PW,copy)(pw);
 303         pw = data->fn(pw, isl_set_copy(entry2->data));
 304
 305         empty = FN(PW,is_zero)(pw);
 306         if (empty < 0) {
 307                 FN(PW,free)(pw);
 308                 return -1;
 309         }
 310         if (empty) {
 311                 FN(PW,free)(pw);
 312                 return 0;
 313         }
 314
 315         data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
 316
 317         return 0;
 318 }
 319
 320 static __isl_give UNION *match_set_op(__isl_take UNION *u,
 321         __isl_take isl_union_set *uset,
 322         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
 323 {
 324         S(UNION,match_set_data) data = { uset, NULL, fn };
 325
 326         if (!u || !uset)
 327                 goto error;
 328
 329         data.res = FN(UNION,alloc)(isl_dim_copy(u->dim), u->table.n);
 330         if (isl_hash_table_foreach(u->dim->ctx, &u->table,
 331                                    &match_set_entry, &data) < 0)
 332                 goto error;
 333
 334         FN(UNION,free)(u);
 335         isl_union_set_free(uset);
 336         return data.res;
 337 error:
 338         FN(UNION,free)(u);
 339         isl_union_set_free(uset);
 340         FN(UNION,free)(data.res);
 341         return NULL;
 342 }
 343
 344 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
 345         __isl_take isl_union_set *uset)
 346 {
 347         return match_set_op(u, uset, &FN(PW,intersect_domain));
 348 }
 349
 350 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
 351         __isl_take isl_union_set *uset)
 352 {
 353         return match_set_op(u, uset, &FN(PW,gist));
 354 }
 355
 356 __isl_give isl_qpolynomial *FN(UNION,eval)(__isl_take UNION *u,
 357         __isl_take isl_point *pnt)
 358 {
 359         uint32_t hash;
 360         struct isl_hash_table_entry *entry;
 361         isl_qpolynomial *qp;
 362
 363         if (!u || !pnt)
 364                 goto error;
 365
 366         hash = isl_dim_get_hash(pnt->dim);
 367         entry = isl_hash_table_find(u->dim->ctx, &u->table,
 368                                     hash, &has_dim, pnt->dim, 0);
 369         if (!entry) {
 370                 qp = isl_qpolynomial_zero(isl_dim_copy(pnt->dim));
 371                 isl_point_free(pnt);
 372         } else {
 373                 qp = FN(PART,eval)(FN(PART,copy)(entry->data), pnt);
 374         }
 375         FN(UNION,free)(u);
 376         return qp;
 377 error:
 378         FN(UNION,free)(u);
 379         isl_point_free(pnt);
 380         return NULL;
 381 }
 382
 383 static int coalesce_entry(void **entry, void *user)
 384 {
 385         PW **pw = (PW **)entry;
 386
 387         *pw = FN(PW,coalesce)(*pw);
 388         if (!*pw)
 389                 return -1;
 390
 391         return 0;
 392 }
 393
 394 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
 395 {
 396         if (!u)
 397                 return NULL;
 398
 399         if (isl_hash_table_foreach(u->dim->ctx, &u->table,
 400                                    &coalesce_entry, NULL) < 0)
 401                 goto error;
 402
 403         return u;
 404 error:
 405         FN(UNION,free)(u);
 406         return NULL;
 407 }
 408
 409 static int domain(__isl_take PART *part, void *user)
 410 {
 411         isl_union_set **uset = (isl_union_set **)user;
 412
 413         *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
 414
 415         return 0;
 416 }
 417
 418 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
 419 {
 420         isl_union_set *uset;
 421
 422         uset = isl_union_set_empty(FN(UNION,get_dim)(u));
 423         if (FN(FN(UNION,foreach),PARTS)(u, &domain, &uset) < 0)
 424                 goto error;
 425
 426         FN(UNION,free)(u);
 427
 428         return uset;
 429 error:
 430         isl_union_set_free(uset);
 431         FN(UNION,free)(u);
 432         return NULL;
 433 }