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
);