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         u = FN(UNION,cow)(u);
 112
 113         if (!part || !u)
 114                 goto error;
 115
 116         isl_assert(u->dim->ctx, isl_dim_match(part->dim, isl_dim_param, u->dim,
 117                                               isl_dim_param), goto error);
 118
 119         hash = isl_dim_get_hash(part->dim);
 120         entry = isl_hash_table_find(u->dim->ctx, &u->table, hash,
 121                                     &has_dim, part->dim, 1);
 122         if (!entry)
 123                 goto error;
 124
 125         if (!entry->data)
 126                 entry->data = part;
 127         else {
 128                 entry->data = FN(PART,add)(entry->data, FN(PART,copy)(part));
 129                 if (!entry->data)
 130                         goto error;
 131                 FN(PART,free)(part);
 132                 if (FN(PART,is_zero)(entry->data)) {
 133                         FN(PART,free)(entry->data);
 134                         isl_hash_table_remove(u->dim->ctx, &u->table, entry);
 135                 }
 136         }
 137
 138         return u;
 139 error:
 140         FN(PART,free)(part);
 141         FN(UNION,free)(u);
 142         return NULL;
 143 }
 144
 145 static int add_part(__isl_take PART *part, void *user)
 146 {
 147         UNION **u = (UNION **)user;
 148
 149         *u = FN(FN(UNION,add),PARTS)(*u, part);
 150
 151         return 0;
 152 }
 153
 154 __isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u)
 155 {
 156         UNION *dup;
 157
 158         if (!u)
 159                 return NULL;
 160
 161         dup = FN(UNION,zero)(isl_dim_copy(u->dim));
 162         if (FN(FN(UNION,foreach),PARTS)(u, &add_part, &dup) < 0)
 163                 goto error;
 164         return dup;
 165 error:
 166         FN(UNION,free)(dup);
 167         return NULL;
 168 }
 169
 170 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u)
 171 {
 172         if (!u)
 173                 return NULL;
 174
 175         if (u->ref == 1)
 176                 return u;
 177         u->ref--;
 178         return FN(UNION,dup)(u);
 179 }
 180
 181 static int free_u_entry(void **entry, void *user)
 182 {
 183         PART *part = *entry;
 184         FN(PART,free)(part);
 185         return 0;
 186 }
 187
 188 void FN(UNION,free)(__isl_take UNION *u)
 189 {
 190         if (!u)
 191                 return;
 192
 193         if (--u->ref > 0)
 194                 return;
 195
 196         isl_hash_table_foreach(u->dim->ctx, &u->table, &free_u_entry, NULL);
 197         isl_hash_table_clear(&u->table);
 198         isl_dim_free(u->dim);
 199         free(u);
 200 }
 201
 202 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
 203 {
 204         u1 = FN(UNION,cow)(u1);
 205
 206         if (!u1 || !u2)
 207                 goto error;
 208
 209         if (FN(FN(UNION,foreach),PARTS)(u2, &add_part, &u1) < 0)
 210                 goto error;
 211
 212         FN(UNION,free)(u2);
 213
 214         return u1;
 215 error:
 216         FN(UNION,free)(u1);
 217         FN(UNION,free)(u2);
 218         return NULL;
 219 }
 220
 221 __isl_give UNION *FN(FN(UNION,from),PARTS)(__isl_take PART *part)
 222 {
 223         isl_dim *dim;
 224         UNION *u;
 225
 226         if (!part)
 227                 return NULL;
 228
 229         dim = FN(PART,get_dim)(part);
 230         dim = isl_dim_drop(dim, isl_dim_in, 0, isl_dim_size(dim, isl_dim_in));
 231         dim = isl_dim_drop(dim, isl_dim_out, 0, isl_dim_size(dim, isl_dim_out));
 232         u = FN(UNION,zero)(dim);
 233         u = FN(FN(UNION,add),PARTS)(u, part);
 234
 235         return u;
 236 }
 237
 238 S(UNION,match_bin_data) {
 239         UNION *upwqp2;
 240         UNION *res;
 241 };
 242
 243 static __isl_give UNION *match_bin_op(__isl_take UNION *u1,
 244         __isl_take UNION *u2, int (*fn)(void **, void *))
 245 {
 246         S(UNION,match_bin_data) data = { u2, NULL };
 247
 248         if (!u1 || !u2)
 249                 goto error;
 250
 251         data.res = FN(UNION,alloc)(isl_dim_copy(u1->dim), u1->table.n);
 252         if (isl_hash_table_foreach(u1->dim->ctx, &u1->table, fn, &data) < 0)
 253                 goto error;
 254
 255         FN(UNION,free)(u1);
 256         FN(UNION,free)(u2);
 257         return data.res;
 258 error:
 259         FN(UNION,free)(u1);
 260         FN(UNION,free)(u2);
 261         FN(UNION,free)(data.res);
 262         return NULL;
 263 }
 264
 265 S(UNION,match_set_data) {
 266         isl_union_set *uset;
 267         UNION *res;
 268         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
 269 };
 270
 271 static int set_has_dim(const void *entry, const void *val)
 272 {
 273         isl_set *set = (isl_set *)entry;
 274         isl_dim *dim = (isl_dim *)val;
 275
 276         return isl_dim_equal(set->dim, dim);
 277 }
 278
 279 static int match_set_entry(void **entry, void *user)
 280 {
 281         S(UNION,match_set_data) *data = user;
 282         uint32_t hash;
 283         struct isl_hash_table_entry *entry2;
 284         isl_dim *dim;
 285         PW *pw = *entry;
 286         int empty;
 287
 288         hash = isl_dim_get_hash(pw->dim);
 289         entry2 = isl_hash_table_find(data->uset->dim->ctx, &data->uset->table,
 290                                      hash, &set_has_dim, pw->dim, 0);
 291         if (!entry2)
 292                 return 0;
 293
 294         pw = FN(PW,copy)(pw);
 295         pw = data->fn(pw, isl_set_copy(entry2->data));
 296
 297         empty = FN(PW,is_zero)(pw);
 298         if (empty < 0) {
 299                 FN(PW,free)(pw);
 300                 return -1;
 301         }
 302         if (empty) {
 303                 FN(PW,free)(pw);
 304                 return 0;
 305         }
 306
 307         data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
 308
 309         return 0;
 310 }
 311
 312 static __isl_give UNION *match_set_op(__isl_take UNION *u,
 313         __isl_take isl_union_set *uset,
 314         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
 315 {
 316         S(UNION,match_set_data) data = { uset, NULL, fn };
 317
 318         if (!u || !uset)
 319                 goto error;
 320
 321         data.res = FN(UNION,alloc)(isl_dim_copy(u->dim), u->table.n);
 322         if (isl_hash_table_foreach(u->dim->ctx, &u->table,
 323                                    &match_set_entry, &data) < 0)
 324                 goto error;
 325
 326         FN(UNION,free)(u);
 327         isl_union_set_free(uset);
 328         return data.res;
 329 error:
 330         FN(UNION,free)(u);
 331         isl_union_set_free(uset);
 332         FN(UNION,free)(data.res);
 333         return NULL;
 334 }
 335
 336 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
 337         __isl_take isl_union_set *uset)
 338 {
 339         return match_set_op(u, uset, &FN(PW,intersect_domain));
 340 }
 341
 342 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
 343         __isl_take isl_union_set *uset)
 344 {
 345         return match_set_op(u, uset, &FN(PW,gist));
 346 }
 347
 348 __isl_give isl_qpolynomial *FN(UNION,eval)(__isl_take UNION *u,
 349         __isl_take isl_point *pnt)
 350 {
 351         uint32_t hash;
 352         struct isl_hash_table_entry *entry;
 353         isl_qpolynomial *qp;
 354
 355         if (!u || !pnt)
 356                 goto error;
 357
 358         hash = isl_dim_get_hash(pnt->dim);
 359         entry = isl_hash_table_find(u->dim->ctx, &u->table,
 360                                     hash, &has_dim, pnt->dim, 0);
 361         if (!entry) {
 362                 qp = isl_qpolynomial_zero(isl_dim_copy(pnt->dim));
 363                 isl_point_free(pnt);
 364         } else {
 365                 qp = FN(PART,eval)(FN(PART,copy)(entry->data), pnt);
 366         }
 367         FN(UNION,free)(u);
 368         return qp;
 369 error:
 370         FN(UNION,free)(u);
 371         isl_point_free(pnt);
 372         return NULL;
 373 }
 374
 375 static int coalesce_entry(void **entry, void *user)
 376 {
 377         PW **pw = (PW **)entry;
 378
 379         *pw = FN(PW,coalesce)(*pw);
 380         if (!*pw)
 381                 return -1;
 382
 383         return 0;
 384 }
 385
 386 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
 387 {
 388         if (!u)
 389                 return NULL;
 390
 391         if (isl_hash_table_foreach(u->dim->ctx, &u->table,
 392                                    &coalesce_entry, NULL) < 0)
 393                 goto error;
 394
 395         return u;
 396 error:
 397         FN(UNION,free)(u);
 398         return NULL;
 399 }
 400
 401 static int domain(__isl_take PART *part, void *user)
 402 {
 403         isl_union_set **uset = (isl_union_set **)user;
 404
 405         *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
 406
 407         return 0;
 408 }
 409
 410 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
 411 {
 412         isl_union_set *uset;
 413
 414         uset = isl_union_set_empty(FN(UNION,get_dim)(u));
 415         if (FN(FN(UNION,foreach),PARTS)(u, &domain, &uset) < 0)
 416                 goto error;
 417
 418         FN(UNION,free)(u);
 419
 420         return uset;
 421 error:
 422         isl_union_set_free(uset);
 423         FN(UNION,free)(u);
 424         return NULL;
 425 }