2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2011 INRIA Saclay
4 * Copyright 2012-2013 Ecole Normale Superieure
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege, K.U.Leuven, Departement
9 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
10 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
11 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
12 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
17 #define xCAT(A,B) A ## B
18 #define CAT(A,B) xCAT(A,B)
20 #define EL CAT(isl_,BASE)
21 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
22 #define FN(TYPE,NAME) xFN(TYPE,NAME)
23 #define xLIST(EL) EL ## _list
24 #define LIST(EL) xLIST(EL)
25 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
26 #define S(TYPE,NAME) xS(TYPE,NAME)
28 isl_ctx *FN(LIST(EL),get_ctx)(__isl_keep LIST(EL) *list)
30 return list ? list->ctx : NULL;
33 __isl_give LIST(EL) *FN(LIST(EL),alloc)(isl_ctx *ctx, int n)
38 isl_die(ctx, isl_error_invalid,
39 "cannot create list of negative length",
41 list = isl_alloc(ctx, LIST(EL),
42 sizeof(LIST(EL)) + (n - 1) * sizeof(struct EL *));
54 __isl_give LIST(EL) *FN(LIST(EL),copy)(__isl_keep LIST(EL) *list)
63 __isl_give LIST(EL) *FN(LIST(EL),dup)(__isl_keep LIST(EL) *list)
71 dup = FN(LIST(EL),alloc)(FN(LIST(EL),get_ctx)(list), list->n);
74 for (i = 0; i < list->n; ++i)
75 dup = FN(LIST(EL),add)(dup, FN(EL,copy)(list->p[i]));
79 __isl_give LIST(EL) *FN(LIST(EL),cow)(__isl_take LIST(EL) *list)
87 return FN(LIST(EL),dup)(list);
90 /* Make sure "list" has room for at least "n" more pieces.
92 * If there is only one reference to list, we extend it in place.
93 * Otherwise, we create a new LIST(EL) and copy the elements.
95 static __isl_give LIST(EL) *FN(LIST(EL),grow)(__isl_take LIST(EL) *list, int n)
103 if (list->n + n <= list->size)
106 ctx = FN(LIST(EL),get_ctx)(list);
107 new_size = ((list->n + n + 1) * 3) / 2;
108 if (list->ref == 1) {
109 res = isl_realloc(ctx, list, LIST(EL),
110 sizeof(LIST(EL)) + (new_size - 1) * sizeof(EL *));
112 return FN(LIST(EL),free)(list);
113 res->size = new_size;
117 res = FN(LIST(EL),alloc)(ctx, new_size);
119 return FN(LIST(EL),free)(list);
121 for (i = 0; i < list->n; ++i)
122 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
124 FN(LIST(EL),free)(list);
128 __isl_give LIST(EL) *FN(LIST(EL),add)(__isl_take LIST(EL) *list,
129 __isl_take struct EL *el)
131 list = FN(LIST(EL),grow)(list, 1);
134 list->p[list->n] = el;
139 FN(LIST(EL),free)(list);
143 /* Remove the "n" elements starting at "first" from "list".
145 __isl_give LIST(EL) *FN(LIST(EL),drop)(__isl_take LIST(EL) *list,
146 unsigned first, unsigned n)
152 if (first + n > list->n || first + n < first)
153 isl_die(list->ctx, isl_error_invalid,
154 "index out of bounds", return FN(LIST(EL),free)(list));
157 list = FN(LIST(EL),cow)(list);
160 for (i = 0; i < n; ++i)
161 FN(EL,free)(list->p[first + i]);
162 for (i = first; i + n < list->n; ++i)
163 list->p[i] = list->p[i + n];
168 /* Insert "el" at position "pos" in "list".
170 * If there is only one reference to "list" and if it already has space
171 * for one extra element, we insert it directly into "list".
172 * Otherwise, we create a new list consisting of "el" and copied
173 * elements from "list".
175 __isl_give LIST(EL) *FN(LIST(EL),insert)(__isl_take LIST(EL) *list,
176 unsigned pos, __isl_take struct EL *el)
184 ctx = FN(LIST(EL),get_ctx)(list);
186 isl_die(ctx, isl_error_invalid,
187 "index out of bounds", goto error);
189 if (list->ref == 1 && list->size > list->n) {
190 for (i = list->n - 1; i >= pos; --i)
191 list->p[i + 1] = list->p[i];
197 res = FN(LIST(EL),alloc)(ctx, list->n + 1);
198 for (i = 0; i < pos; ++i)
199 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
200 res = FN(LIST(EL),add)(res, el);
201 for (i = pos; i < list->n; ++i)
202 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
203 FN(LIST(EL),free)(list);
208 FN(LIST(EL),free)(list);
212 void *FN(LIST(EL),free)(__isl_take LIST(EL) *list)
222 isl_ctx_deref(list->ctx);
223 for (i = 0; i < list->n; ++i)
224 FN(EL,free)(list->p[i]);
230 int FN(FN(LIST(EL),n),BASE)(__isl_keep LIST(EL) *list)
232 return list ? list->n : 0;
235 __isl_give EL *FN(FN(LIST(EL),get),BASE)(__isl_keep LIST(EL) *list, int index)
239 if (index < 0 || index >= list->n)
240 isl_die(list->ctx, isl_error_invalid,
241 "index out of bounds", return NULL);
242 return FN(EL,copy)(list->p[index]);
245 /* Replace the element at position "index" in "list" by "el".
247 __isl_give LIST(EL) *FN(FN(LIST(EL),set),BASE)(__isl_take LIST(EL) *list,
248 int index, __isl_take EL *el)
252 if (index < 0 || index >= list->n)
253 isl_die(list->ctx, isl_error_invalid,
254 "index out of bounds", goto error);
255 if (list->p[index] == el) {
259 list = FN(LIST(EL),cow)(list);
262 FN(EL,free)(list->p[index]);
267 FN(LIST(EL),free)(list);
271 int FN(LIST(EL),foreach)(__isl_keep LIST(EL) *list,
272 int (*fn)(__isl_take EL *el, void *user), void *user)
279 for (i = 0; i < list->n; ++i) {
280 EL *el = FN(EL,copy(list->p[i]));
283 if (fn(el, user) < 0)
290 /* Internal data structure for isl_*_list_sort.
292 * "cmp" is the original comparison function.
293 * "user" is a user provided pointer that should be passed to "cmp".
295 S(LIST(EL),sort_data) {
296 int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user);
300 /* Compare two entries of an isl_*_list based on the user provided
301 * comparison function on pairs of isl_* objects.
303 static int FN(LIST(EL),cmp)(const void *a, const void *b, void *user)
305 S(LIST(EL),sort_data) *data = user;
309 return data->cmp(*el1, *el2, data->user);
312 /* Sort the elements of "list" in ascending order according to
313 * comparison function "cmp".
315 __isl_give LIST(EL) *FN(LIST(EL),sort)(__isl_take LIST(EL) *list,
316 int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user), void *user)
318 S(LIST(EL),sort_data) data = { cmp, user };
324 list = FN(LIST(EL),cow)(list);
328 if (isl_sort(list->p, list->n, sizeof(list->p[0]),
329 &FN(LIST(EL),cmp), &data) < 0)
330 return FN(LIST(EL),free)(list);
335 __isl_give LIST(EL) *FN(FN(LIST(EL),from),BASE)(__isl_take EL *el)
342 ctx = FN(EL,get_ctx)(el);
343 list = FN(LIST(EL),alloc)(ctx, 1);
346 list = FN(LIST(EL),add)(list, el);
353 __isl_give LIST(EL) *FN(LIST(EL),concat)(__isl_take LIST(EL) *list1,
354 __isl_take LIST(EL) *list2)
360 if (!list1 || !list2)
363 ctx = FN(LIST(EL),get_ctx)(list1);
364 res = FN(LIST(EL),alloc)(ctx, list1->n + list2->n);
365 for (i = 0; i < list1->n; ++i)
366 res = FN(LIST(EL),add)(res, FN(EL,copy)(list1->p[i]));
367 for (i = 0; i < list2->n; ++i)
368 res = FN(LIST(EL),add)(res, FN(EL,copy)(list2->p[i]));
370 FN(LIST(EL),free)(list1);
371 FN(LIST(EL),free)(list2);
374 FN(LIST(EL),free)(list1);
375 FN(LIST(EL),free)(list2);
379 __isl_give isl_printer *CAT(isl_printer_print_,LIST(BASE))(
380 __isl_take isl_printer *p, __isl_keep LIST(EL) *list)
386 p = isl_printer_print_str(p, "(");
387 for (i = 0; i < list->n; ++i) {
389 p = isl_printer_print_str(p, ",");
390 p = CAT(isl_printer_print_,BASE)(p, list->p[i]);
392 p = isl_printer_print_str(p, ")");
399 void FN(LIST(EL),dump)(__isl_keep LIST(EL) *list)
401 isl_printer *printer;
406 printer = isl_printer_to_file(FN(LIST(EL),get_ctx)(list), stderr);
407 printer = CAT(isl_printer_print_,LIST(BASE))(printer, list);
408 printer = isl_printer_end_line(printer);
410 isl_printer_free(printer);