add isl_vec_sort
[isl.git] / isl_union_templ.c
blob0737a589aa0e8c2434d24fdcc966399611f5b9df
1 /*
2 * Copyright 2010 INRIA Saclay
4 * Use of this software is governed by the GNU LGPLv2.1 license
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 */
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)
16 struct UNION {
17 int ref;
18 #ifdef HAS_TYPE
19 enum isl_fold type;
20 #endif
21 isl_dim *dim;
23 struct isl_hash_table table;
26 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u);
28 isl_ctx *FN(UNION,get_ctx)(__isl_keep UNION *u)
30 return u ? u->dim->ctx : NULL;
33 __isl_give isl_dim *FN(UNION,get_dim)(__isl_keep UNION *u)
35 if (!u)
36 return NULL;
37 return isl_dim_copy(u->dim);
40 #ifdef HAS_TYPE
41 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_dim *dim,
42 enum isl_fold type, int size)
43 #else
44 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_dim *dim, int size)
45 #endif
47 UNION *u;
49 if (!dim)
50 return NULL;
52 u = isl_calloc_type(dim->ctx, UNION);
53 if (!u)
54 return NULL;
56 u->ref = 1;
57 #ifdef HAS_TYPE
58 u->type = type;
59 #endif
60 u->dim = dim;
61 if (isl_hash_table_init(dim->ctx, &u->table, size) < 0)
62 goto error;
64 return u;
65 error:
66 isl_dim_free(dim);
67 FN(UNION,free)(u);
68 return NULL;
71 #ifdef HAS_TYPE
72 __isl_give UNION *FN(UNION,zero)(__isl_take isl_dim *dim, enum isl_fold type)
74 return FN(UNION,alloc)(dim, type, 16);
76 #else
77 __isl_give UNION *FN(UNION,zero)(__isl_take isl_dim *dim)
79 return FN(UNION,alloc)(dim, 16);
81 #endif
83 __isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u)
85 if (!u)
86 return NULL;
88 u->ref++;
89 return u;
92 S(UNION,foreach_data)
94 int (*fn)(__isl_take PART *part, void *user);
95 void *user;
98 static int call_on_copy(void **entry, void *user)
100 PART *part = *entry;
101 S(UNION,foreach_data) *data = (S(UNION,foreach_data) *)user;
103 return data->fn(FN(PART,copy)(part), data->user);
106 int FN(FN(UNION,foreach),PARTS)(__isl_keep UNION *u,
107 int (*fn)(__isl_take PART *part, void *user), void *user)
109 S(UNION,foreach_data) data = { fn, user };
111 if (!u)
112 return -1;
114 return isl_hash_table_foreach(u->dim->ctx, &u->table,
115 &call_on_copy, &data);
118 static int has_dim(const void *entry, const void *val)
120 PART *part = (PART *)entry;
121 isl_dim *dim = (isl_dim *)val;
123 return isl_dim_equal(part->dim, dim);
126 __isl_give PART *FN(FN(UNION,extract),PARTS)(__isl_keep UNION *u,
127 __isl_take isl_dim *dim)
129 uint32_t hash;
130 struct isl_hash_table_entry *entry;
132 if (!u || !dim)
133 goto error;
135 hash = isl_dim_get_hash(dim);
136 entry = isl_hash_table_find(u->dim->ctx, &u->table, hash,
137 &has_dim, dim, 0);
138 if (!entry)
139 #ifdef HAS_TYPE
140 return FN(PART,zero)(dim, u->type);
141 #else
142 return FN(PART,zero)(dim);
143 #endif
144 isl_dim_free(dim);
145 return FN(PART,copy)(entry->data);
146 error:
147 isl_dim_free(dim);
148 return NULL;
151 __isl_give UNION *FN(FN(UNION,add),PARTS)(__isl_take UNION *u,
152 __isl_take PART *part)
154 uint32_t hash;
155 struct isl_hash_table_entry *entry;
157 if (!part)
158 goto error;
160 if (FN(PART,is_zero)(part)) {
161 FN(PART,free)(part);
162 return u;
165 u = FN(UNION,cow)(u);
167 if (!u)
168 goto error;
170 isl_assert(u->dim->ctx, isl_dim_match(part->dim, isl_dim_param, u->dim,
171 isl_dim_param), goto error);
173 hash = isl_dim_get_hash(part->dim);
174 entry = isl_hash_table_find(u->dim->ctx, &u->table, hash,
175 &has_dim, part->dim, 1);
176 if (!entry)
177 goto error;
179 if (!entry->data)
180 entry->data = part;
181 else {
182 entry->data = FN(PART,add)(entry->data, FN(PART,copy)(part));
183 if (!entry->data)
184 goto error;
185 FN(PART,free)(part);
186 if (FN(PART,is_zero)(entry->data)) {
187 FN(PART,free)(entry->data);
188 isl_hash_table_remove(u->dim->ctx, &u->table, entry);
192 return u;
193 error:
194 FN(PART,free)(part);
195 FN(UNION,free)(u);
196 return NULL;
199 static int add_part(__isl_take PART *part, void *user)
201 UNION **u = (UNION **)user;
203 *u = FN(FN(UNION,add),PARTS)(*u, part);
205 return 0;
208 __isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u)
210 UNION *dup;
212 if (!u)
213 return NULL;
215 #ifdef HAS_TYPE
216 dup = FN(UNION,zero)(isl_dim_copy(u->dim), u->type);
217 #else
218 dup = FN(UNION,zero)(isl_dim_copy(u->dim));
219 #endif
220 if (FN(FN(UNION,foreach),PARTS)(u, &add_part, &dup) < 0)
221 goto error;
222 return dup;
223 error:
224 FN(UNION,free)(dup);
225 return NULL;
228 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u)
230 if (!u)
231 return NULL;
233 if (u->ref == 1)
234 return u;
235 u->ref--;
236 return FN(UNION,dup)(u);
239 static int free_u_entry(void **entry, void *user)
241 PART *part = *entry;
242 FN(PART,free)(part);
243 return 0;
246 void FN(UNION,free)(__isl_take UNION *u)
248 if (!u)
249 return;
251 if (--u->ref > 0)
252 return;
254 isl_hash_table_foreach(u->dim->ctx, &u->table, &free_u_entry, NULL);
255 isl_hash_table_clear(&u->table);
256 isl_dim_free(u->dim);
257 free(u);
260 S(UNION,align) {
261 isl_reordering *exp;
262 UNION *res;
265 static int align_entry(__isl_take PART *part, void *user)
267 isl_reordering *exp;
268 S(UNION,align) *data = user;
270 exp = isl_reordering_extend_dim(isl_reordering_copy(data->exp),
271 FN(PART,get_dim)(part));
273 data->res = FN(FN(UNION,add),PARTS)(data->res,
274 FN(PART,realign)(part, exp));
276 return 0;
279 __isl_give UNION *FN(UNION,align_params)(__isl_take UNION *u,
280 __isl_take isl_dim *model)
282 int i, j;
283 S(UNION,align) data = { NULL, NULL };
285 if (!u || !model)
286 goto error;
288 if (isl_dim_match(u->dim, isl_dim_param, model, isl_dim_param)) {
289 isl_dim_free(model);
290 return u;
293 data.exp = isl_parameter_alignment_reordering(u->dim, model);
294 if (!data.exp)
295 goto error;
297 #ifdef HAS_TYPE
298 data.res = FN(UNION,alloc)(isl_dim_copy(data.exp->dim),
299 u->type, u->table.n);
300 #else
301 data.res = FN(UNION,alloc)(isl_dim_copy(data.exp->dim), u->table.n);
302 #endif
303 if (FN(FN(UNION,foreach),PARTS)(u, &align_entry, &data) < 0)
304 goto error;
306 isl_reordering_free(data.exp);
307 FN(UNION,free)(u);
308 isl_dim_free(model);
309 return data.res;
310 error:
311 isl_reordering_free(data.exp);
312 FN(UNION,free)(u);
313 FN(UNION,free)(data.res);
314 isl_dim_free(model);
315 return NULL;
318 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
320 u1 = FN(UNION,align_params)(u1, FN(UNION,get_dim)(u2));
321 u2 = FN(UNION,align_params)(u2, FN(UNION,get_dim)(u1));
323 u1 = FN(UNION,cow)(u1);
325 if (!u1 || !u2)
326 goto error;
328 if (FN(FN(UNION,foreach),PARTS)(u2, &add_part, &u1) < 0)
329 goto error;
331 FN(UNION,free)(u2);
333 return u1;
334 error:
335 FN(UNION,free)(u1);
336 FN(UNION,free)(u2);
337 return NULL;
340 __isl_give UNION *FN(FN(UNION,from),PARTS)(__isl_take PART *part)
342 isl_dim *dim;
343 UNION *u;
345 if (!part)
346 return NULL;
348 dim = FN(PART,get_dim)(part);
349 dim = isl_dim_drop(dim, isl_dim_in, 0, isl_dim_size(dim, isl_dim_in));
350 dim = isl_dim_drop(dim, isl_dim_out, 0, isl_dim_size(dim, isl_dim_out));
351 #ifdef HAS_TYPE
352 u = FN(UNION,zero)(dim, part->type);
353 #else
354 u = FN(UNION,zero)(dim);
355 #endif
356 u = FN(FN(UNION,add),PARTS)(u, part);
358 return u;
361 S(UNION,match_bin_data) {
362 UNION *u2;
363 UNION *res;
366 static __isl_give UNION *match_bin_op(__isl_take UNION *u1,
367 __isl_take UNION *u2, int (*fn)(void **, void *))
369 S(UNION,match_bin_data) data = { NULL, NULL };
371 u1 = FN(UNION,align_params)(u1, FN(UNION,get_dim)(u2));
372 u2 = FN(UNION,align_params)(u2, FN(UNION,get_dim)(u1));
374 if (!u1 || !u2)
375 goto error;
377 data.u2 = u2;
378 #ifdef HAS_TYPE
379 data.res = FN(UNION,alloc)(isl_dim_copy(u1->dim), u1->type, u1->table.n);
380 #else
381 data.res = FN(UNION,alloc)(isl_dim_copy(u1->dim), u1->table.n);
382 #endif
383 if (isl_hash_table_foreach(u1->dim->ctx, &u1->table, fn, &data) < 0)
384 goto error;
386 FN(UNION,free)(u1);
387 FN(UNION,free)(u2);
388 return data.res;
389 error:
390 FN(UNION,free)(u1);
391 FN(UNION,free)(u2);
392 FN(UNION,free)(data.res);
393 return NULL;
396 S(UNION,match_set_data) {
397 isl_union_set *uset;
398 UNION *res;
399 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
402 static int set_has_dim(const void *entry, const void *val)
404 isl_set *set = (isl_set *)entry;
405 isl_dim *dim = (isl_dim *)val;
407 return isl_dim_equal(set->dim, dim);
410 static int match_set_entry(void **entry, void *user)
412 S(UNION,match_set_data) *data = user;
413 uint32_t hash;
414 struct isl_hash_table_entry *entry2;
415 isl_dim *dim;
416 PW *pw = *entry;
417 int empty;
419 hash = isl_dim_get_hash(pw->dim);
420 entry2 = isl_hash_table_find(data->uset->dim->ctx, &data->uset->table,
421 hash, &set_has_dim, pw->dim, 0);
422 if (!entry2)
423 return 0;
425 pw = FN(PW,copy)(pw);
426 pw = data->fn(pw, isl_set_copy(entry2->data));
428 empty = FN(PW,is_zero)(pw);
429 if (empty < 0) {
430 FN(PW,free)(pw);
431 return -1;
433 if (empty) {
434 FN(PW,free)(pw);
435 return 0;
438 data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
440 return 0;
443 static __isl_give UNION *match_set_op(__isl_take UNION *u,
444 __isl_take isl_union_set *uset,
445 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
447 S(UNION,match_set_data) data = { NULL, NULL, fn };
449 u = FN(UNION,align_params)(u, isl_union_set_get_dim(uset));
450 uset = isl_union_set_align_params(uset, FN(UNION,get_dim)(u));
452 if (!u || !uset)
453 goto error;
455 data.uset = uset;
456 #ifdef HAS_TYPE
457 data.res = FN(UNION,alloc)(isl_dim_copy(u->dim), u->type, u->table.n);
458 #else
459 data.res = FN(UNION,alloc)(isl_dim_copy(u->dim), u->table.n);
460 #endif
461 if (isl_hash_table_foreach(u->dim->ctx, &u->table,
462 &match_set_entry, &data) < 0)
463 goto error;
465 FN(UNION,free)(u);
466 isl_union_set_free(uset);
467 return data.res;
468 error:
469 FN(UNION,free)(u);
470 isl_union_set_free(uset);
471 FN(UNION,free)(data.res);
472 return NULL;
475 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
476 __isl_take isl_union_set *uset)
478 return match_set_op(u, uset, &FN(PW,intersect_domain));
481 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
482 __isl_take isl_union_set *uset)
484 return match_set_op(u, uset, &FN(PW,gist));
487 __isl_give isl_qpolynomial *FN(UNION,eval)(__isl_take UNION *u,
488 __isl_take isl_point *pnt)
490 uint32_t hash;
491 struct isl_hash_table_entry *entry;
492 isl_qpolynomial *qp;
494 if (!u || !pnt)
495 goto error;
497 hash = isl_dim_get_hash(pnt->dim);
498 entry = isl_hash_table_find(u->dim->ctx, &u->table,
499 hash, &has_dim, pnt->dim, 0);
500 if (!entry) {
501 qp = isl_qpolynomial_zero(isl_dim_copy(pnt->dim));
502 isl_point_free(pnt);
503 } else {
504 qp = FN(PART,eval)(FN(PART,copy)(entry->data), pnt);
506 FN(UNION,free)(u);
507 return qp;
508 error:
509 FN(UNION,free)(u);
510 isl_point_free(pnt);
511 return NULL;
514 static int coalesce_entry(void **entry, void *user)
516 PW **pw = (PW **)entry;
518 *pw = FN(PW,coalesce)(*pw);
519 if (!*pw)
520 return -1;
522 return 0;
525 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
527 if (!u)
528 return NULL;
530 if (isl_hash_table_foreach(u->dim->ctx, &u->table,
531 &coalesce_entry, NULL) < 0)
532 goto error;
534 return u;
535 error:
536 FN(UNION,free)(u);
537 return NULL;
540 static int domain(__isl_take PART *part, void *user)
542 isl_union_set **uset = (isl_union_set **)user;
544 *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
546 return 0;
549 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
551 isl_union_set *uset;
553 uset = isl_union_set_empty(FN(UNION,get_dim)(u));
554 if (FN(FN(UNION,foreach),PARTS)(u, &domain, &uset) < 0)
555 goto error;
557 FN(UNION,free)(u);
559 return uset;
560 error:
561 isl_union_set_free(uset);
562 FN(UNION,free)(u);
563 return NULL;
566 static int mul_isl_int(void **entry, void *user)
568 PW **pw = (PW **)entry;
569 isl_int *v = user;
571 *pw = FN(PW,mul_isl_int)(*pw, *v);
572 if (!*pw)
573 return -1;
575 return 0;
578 __isl_give UNION *FN(UNION,mul_isl_int)(__isl_take UNION *u, isl_int v)
580 if (isl_int_is_one(v))
581 return u;
583 if (u && isl_int_is_zero(v)) {
584 UNION *zero;
585 isl_dim *dim = FN(UNION,get_dim)(u);
586 #ifdef HAS_TYPE
587 zero = FN(UNION,zero)(dim, u->type);
588 #else
589 zero = FN(UNION,zero)(dim);
590 #endif
591 FN(UNION,free)(u);
592 return zero;
595 u = FN(UNION,cow)(u);
596 if (!u)
597 return NULL;
599 #ifdef HAS_TYPE
600 if (isl_int_is_neg(v))
601 u->type = isl_fold_type_negate(u->type);
602 #endif
603 if (isl_hash_table_foreach(u->dim->ctx, &u->table, &mul_isl_int, v) < 0)
604 goto error;
606 return u;
607 error:
608 FN(UNION,free)(u);
609 return NULL;