isl_scheduler.c: move sort_statements down
[isl.git] / isl_vec.c
bloba8582be399615637051ba84fb87e60a5c2d95c8e
1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2013 Ecole Normale Superieure
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege, K.U.Leuven, Departement
8 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
9 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
12 #include <isl_ctx_private.h>
13 #include <isl_seq.h>
14 #include <isl_val_private.h>
15 #include <isl_vec_private.h>
16 #include <isl/deprecated/vec_int.h>
18 isl_ctx *isl_vec_get_ctx(__isl_keep isl_vec *vec)
20 return vec ? vec->ctx : NULL;
23 struct isl_vec *isl_vec_alloc(struct isl_ctx *ctx, unsigned size)
25 struct isl_vec *vec;
27 vec = isl_alloc_type(ctx, struct isl_vec);
28 if (!vec)
29 return NULL;
31 vec->block = isl_blk_alloc(ctx, size);
32 if (isl_blk_is_error(vec->block))
33 goto error;
35 vec->ctx = ctx;
36 isl_ctx_ref(ctx);
37 vec->ref = 1;
38 vec->size = size;
39 vec->el = vec->block.data;
41 return vec;
42 error:
43 isl_blk_free(ctx, vec->block);
44 return NULL;
47 __isl_give isl_vec *isl_vec_extend(__isl_take isl_vec *vec, unsigned size)
49 if (!vec)
50 return NULL;
51 if (size <= vec->size)
52 return vec;
54 vec = isl_vec_cow(vec);
55 if (!vec)
56 return NULL;
58 vec->block = isl_blk_extend(vec->ctx, vec->block, size);
59 if (!vec->block.data)
60 goto error;
62 vec->size = size;
63 vec->el = vec->block.data;
65 return vec;
66 error:
67 isl_vec_free(vec);
68 return NULL;
71 __isl_give isl_vec *isl_vec_zero_extend(__isl_take isl_vec *vec, unsigned size)
73 int extra;
75 if (!vec)
76 return NULL;
77 if (size <= vec->size)
78 return vec;
80 vec = isl_vec_cow(vec);
81 if (!vec)
82 return NULL;
84 extra = size - vec->size;
85 vec = isl_vec_extend(vec, size);
86 if (!vec)
87 return NULL;
89 isl_seq_clr(vec->el + size - extra, extra);
91 return vec;
94 /* Return a vector containing the elements of "vec1" followed by
95 * those of "vec2".
97 __isl_give isl_vec *isl_vec_concat(__isl_take isl_vec *vec1,
98 __isl_take isl_vec *vec2)
100 if (!vec1 || !vec2)
101 goto error;
103 if (vec2->size == 0) {
104 isl_vec_free(vec2);
105 return vec1;
108 if (vec1->size == 0) {
109 isl_vec_free(vec1);
110 return vec2;
113 vec1 = isl_vec_extend(vec1, vec1->size + vec2->size);
114 if (!vec1)
115 goto error;
117 isl_seq_cpy(vec1->el + vec1->size - vec2->size, vec2->el, vec2->size);
119 isl_vec_free(vec2);
120 return vec1;
121 error:
122 isl_vec_free(vec1);
123 isl_vec_free(vec2);
124 return NULL;
127 struct isl_vec *isl_vec_copy(struct isl_vec *vec)
129 if (!vec)
130 return NULL;
132 vec->ref++;
133 return vec;
136 struct isl_vec *isl_vec_dup(struct isl_vec *vec)
138 struct isl_vec *vec2;
140 if (!vec)
141 return NULL;
142 vec2 = isl_vec_alloc(vec->ctx, vec->size);
143 if (!vec2)
144 return NULL;
145 isl_seq_cpy(vec2->el, vec->el, vec->size);
146 return vec2;
149 struct isl_vec *isl_vec_cow(struct isl_vec *vec)
151 struct isl_vec *vec2;
152 if (!vec)
153 return NULL;
155 if (vec->ref == 1)
156 return vec;
158 vec2 = isl_vec_dup(vec);
159 isl_vec_free(vec);
160 return vec2;
163 __isl_null isl_vec *isl_vec_free(__isl_take isl_vec *vec)
165 if (!vec)
166 return NULL;
168 if (--vec->ref > 0)
169 return NULL;
171 isl_ctx_deref(vec->ctx);
172 isl_blk_free(vec->ctx, vec->block);
173 free(vec);
175 return NULL;
178 int isl_vec_size(__isl_keep isl_vec *vec)
180 return vec ? vec->size : -1;
183 int isl_vec_get_element(__isl_keep isl_vec *vec, int pos, isl_int *v)
185 if (!vec)
186 return -1;
188 if (pos < 0 || pos >= vec->size)
189 isl_die(vec->ctx, isl_error_invalid, "position out of range",
190 return -1);
191 isl_int_set(*v, vec->el[pos]);
192 return 0;
195 /* Extract the element at position "pos" of "vec".
197 __isl_give isl_val *isl_vec_get_element_val(__isl_keep isl_vec *vec, int pos)
199 isl_ctx *ctx;
201 if (!vec)
202 return NULL;
203 ctx = isl_vec_get_ctx(vec);
204 if (pos < 0 || pos >= vec->size)
205 isl_die(ctx, isl_error_invalid, "position out of range",
206 return NULL);
207 return isl_val_int_from_isl_int(ctx, vec->el[pos]);
210 __isl_give isl_vec *isl_vec_set_element(__isl_take isl_vec *vec,
211 int pos, isl_int v)
213 vec = isl_vec_cow(vec);
214 if (!vec)
215 return NULL;
216 if (pos < 0 || pos >= vec->size)
217 isl_die(vec->ctx, isl_error_invalid, "position out of range",
218 goto error);
219 isl_int_set(vec->el[pos], v);
220 return vec;
221 error:
222 isl_vec_free(vec);
223 return NULL;
226 __isl_give isl_vec *isl_vec_set_element_si(__isl_take isl_vec *vec,
227 int pos, int v)
229 vec = isl_vec_cow(vec);
230 if (!vec)
231 return NULL;
232 if (pos < 0 || pos >= vec->size)
233 isl_die(vec->ctx, isl_error_invalid, "position out of range",
234 goto error);
235 isl_int_set_si(vec->el[pos], v);
236 return vec;
237 error:
238 isl_vec_free(vec);
239 return NULL;
242 /* Replace the element at position "pos" of "vec" by "v".
244 __isl_give isl_vec *isl_vec_set_element_val(__isl_take isl_vec *vec,
245 int pos, __isl_take isl_val *v)
247 if (!v)
248 return isl_vec_free(vec);
249 if (!isl_val_is_int(v))
250 isl_die(isl_val_get_ctx(v), isl_error_invalid,
251 "expecting integer value", goto error);
252 vec = isl_vec_set_element(vec, pos, v->n);
253 isl_val_free(v);
254 return vec;
255 error:
256 isl_val_free(v);
257 return isl_vec_free(vec);
260 /* Compare the elements of "vec1" and "vec2" at position "pos".
262 int isl_vec_cmp_element(__isl_keep isl_vec *vec1, __isl_keep isl_vec *vec2,
263 int pos)
265 if (!vec1 || !vec2)
266 return 0;
267 if (pos < 0 || pos >= vec1->size || pos >= vec2->size)
268 isl_die(isl_vec_get_ctx(vec1), isl_error_invalid,
269 "position out of range", return 0);
270 return isl_int_cmp(vec1->el[pos], vec2->el[pos]);
273 int isl_vec_is_equal(__isl_keep isl_vec *vec1, __isl_keep isl_vec *vec2)
275 if (!vec1 || !vec2)
276 return -1;
278 if (vec1->size != vec2->size)
279 return 0;
281 return isl_seq_eq(vec1->el, vec2->el, vec1->size);
284 __isl_give isl_printer *isl_printer_print_vec(__isl_take isl_printer *printer,
285 __isl_keep isl_vec *vec)
287 int i;
289 if (!printer || !vec)
290 goto error;
292 printer = isl_printer_print_str(printer, "[");
293 for (i = 0; i < vec->size; ++i) {
294 if (i)
295 printer = isl_printer_print_str(printer, ",");
296 printer = isl_printer_print_isl_int(printer, vec->el[i]);
298 printer = isl_printer_print_str(printer, "]");
300 return printer;
301 error:
302 isl_printer_free(printer);
303 return NULL;
306 void isl_vec_dump(struct isl_vec *vec)
308 isl_printer *printer;
310 if (!vec)
311 return;
313 printer = isl_printer_to_file(vec->ctx, stderr);
314 printer = isl_printer_print_vec(printer, vec);
315 printer = isl_printer_end_line(printer);
317 isl_printer_free(printer);
320 __isl_give isl_vec *isl_vec_set(__isl_take isl_vec *vec, isl_int v)
322 vec = isl_vec_cow(vec);
323 if (!vec)
324 return NULL;
325 isl_seq_set(vec->el, v, vec->size);
326 return vec;
329 __isl_give isl_vec *isl_vec_set_si(__isl_take isl_vec *vec, int v)
331 vec = isl_vec_cow(vec);
332 if (!vec)
333 return NULL;
334 isl_seq_set_si(vec->el, v, vec->size);
335 return vec;
338 /* Replace all elements of "vec" by "v".
340 __isl_give isl_vec *isl_vec_set_val(__isl_take isl_vec *vec,
341 __isl_take isl_val *v)
343 vec = isl_vec_cow(vec);
344 if (!vec || !v)
345 goto error;
346 if (!isl_val_is_int(v))
347 isl_die(isl_val_get_ctx(v), isl_error_invalid,
348 "expecting integer value", goto error);
349 isl_seq_set(vec->el, v->n, vec->size);
350 isl_val_free(v);
351 return vec;
352 error:
353 isl_vec_free(vec);
354 isl_val_free(v);
355 return NULL;
358 __isl_give isl_vec *isl_vec_clr(__isl_take isl_vec *vec)
360 vec = isl_vec_cow(vec);
361 if (!vec)
362 return NULL;
363 isl_seq_clr(vec->el, vec->size);
364 return vec;
367 void isl_vec_lcm(struct isl_vec *vec, isl_int *lcm)
369 isl_seq_lcm(vec->block.data, vec->size, lcm);
372 /* Given a rational vector, with the denominator in the first element
373 * of the vector, round up all coordinates.
375 struct isl_vec *isl_vec_ceil(struct isl_vec *vec)
377 vec = isl_vec_cow(vec);
378 if (!vec)
379 return NULL;
381 isl_seq_cdiv_q(vec->el + 1, vec->el + 1, vec->el[0], vec->size - 1);
383 isl_int_set_si(vec->el[0], 1);
385 return vec;
388 struct isl_vec *isl_vec_normalize(struct isl_vec *vec)
390 if (!vec)
391 return NULL;
392 isl_seq_normalize(vec->ctx, vec->el, vec->size);
393 return vec;
396 __isl_give isl_vec *isl_vec_neg(__isl_take isl_vec *vec)
398 vec = isl_vec_cow(vec);
399 if (!vec)
400 return NULL;
401 isl_seq_neg(vec->el, vec->el, vec->size);
402 return vec;
405 __isl_give isl_vec *isl_vec_scale(__isl_take isl_vec *vec, isl_int m)
407 if (isl_int_is_one(m))
408 return vec;
409 vec = isl_vec_cow(vec);
410 if (!vec)
411 return NULL;
412 isl_seq_scale(vec->el, vec->el, m, vec->size);
413 return vec;
416 /* Reduce the elements of "vec" modulo "m".
418 __isl_give isl_vec *isl_vec_fdiv_r(__isl_take isl_vec *vec, isl_int m)
420 vec = isl_vec_cow(vec);
421 if (!vec)
422 return NULL;
424 isl_seq_fdiv_r(vec->el, vec->el, m, vec->size);
426 return vec;
429 __isl_give isl_vec *isl_vec_add(__isl_take isl_vec *vec1,
430 __isl_take isl_vec *vec2)
432 vec1 = isl_vec_cow(vec1);
433 if (!vec1 || !vec2)
434 goto error;
436 isl_assert(vec1->ctx, vec1->size == vec2->size, goto error);
438 isl_seq_combine(vec1->el, vec1->ctx->one, vec1->el,
439 vec1->ctx->one, vec2->el, vec1->size);
441 isl_vec_free(vec2);
442 return vec1;
443 error:
444 isl_vec_free(vec1);
445 isl_vec_free(vec2);
446 return NULL;
449 static int qsort_int_cmp(const void *p1, const void *p2)
451 const isl_int *i1 = (const isl_int *) p1;
452 const isl_int *i2 = (const isl_int *) p2;
454 return isl_int_cmp(*i1, *i2);
457 __isl_give isl_vec *isl_vec_sort(__isl_take isl_vec *vec)
459 if (!vec)
460 return NULL;
462 qsort(vec->el, vec->size, sizeof(*vec->el), &qsort_int_cmp);
464 return vec;
467 __isl_give isl_vec *isl_vec_drop_els(__isl_take isl_vec *vec,
468 unsigned pos, unsigned n)
470 if (n == 0)
471 return vec;
472 vec = isl_vec_cow(vec);
473 if (!vec)
474 return NULL;
476 if (pos + n > vec->size)
477 isl_die(vec->ctx, isl_error_invalid,
478 "range out of bounds", goto error);
480 if (pos + n != vec->size)
481 isl_seq_cpy(vec->el + pos, vec->el + pos + n,
482 vec->size - pos - n);
484 vec->size -= n;
486 return vec;
487 error:
488 isl_vec_free(vec);
489 return NULL;
492 __isl_give isl_vec *isl_vec_insert_els(__isl_take isl_vec *vec,
493 unsigned pos, unsigned n)
495 isl_vec *ext = NULL;
497 if (n == 0)
498 return vec;
499 if (!vec)
500 return NULL;
502 if (pos > vec->size)
503 isl_die(vec->ctx, isl_error_invalid,
504 "position out of bounds", goto error);
506 ext = isl_vec_alloc(vec->ctx, vec->size + n);
507 if (!ext)
508 goto error;
510 isl_seq_cpy(ext->el, vec->el, pos);
511 isl_seq_cpy(ext->el + pos + n, vec->el + pos, vec->size - pos);
513 isl_vec_free(vec);
514 return ext;
515 error:
516 isl_vec_free(vec);
517 isl_vec_free(ext);
518 return NULL;
521 __isl_give isl_vec *isl_vec_insert_zero_els(__isl_take isl_vec *vec,
522 unsigned pos, unsigned n)
524 vec = isl_vec_insert_els(vec, pos, n);
525 if (!vec)
526 return NULL;
528 isl_seq_clr(vec->el + pos, n);
530 return vec;
533 /* Move the "n" elements starting as "src_pos" of "vec"
534 * to "dst_pos". The elements originally at "dst_pos" are moved
535 * up or down depending on whether "dst_pos" is smaller or greater
536 * than "src_pos".
538 __isl_give isl_vec *isl_vec_move_els(__isl_take isl_vec *vec,
539 unsigned dst_pos, unsigned src_pos, unsigned n)
541 isl_vec *res;
543 if (!vec)
544 return NULL;
546 if (src_pos + n > vec->size)
547 isl_die(vec->ctx, isl_error_invalid,
548 "source range out of bounds", return isl_vec_free(vec));
549 if (dst_pos + n > vec->size)
550 isl_die(vec->ctx, isl_error_invalid,
551 "destination range out of bounds",
552 return isl_vec_free(vec));
554 if (n == 0 || dst_pos == src_pos)
555 return vec;
557 res = isl_vec_alloc(vec->ctx, vec->size);
558 if (!res)
559 return isl_vec_free(vec);
561 if (dst_pos < src_pos) {
562 isl_seq_cpy(res->el, vec->el, dst_pos);
563 isl_seq_cpy(res->el + dst_pos, vec->el + src_pos, n);
564 isl_seq_cpy(res->el + dst_pos + n,
565 vec->el + dst_pos, src_pos - dst_pos);
566 isl_seq_cpy(res->el + src_pos + n,
567 vec->el + src_pos + n, res->size - src_pos - n);
568 } else {
569 isl_seq_cpy(res->el, vec->el, src_pos);
570 isl_seq_cpy(res->el + src_pos,
571 vec->el + src_pos + n, dst_pos - src_pos);
572 isl_seq_cpy(res->el + dst_pos, vec->el + src_pos, n);
573 isl_seq_cpy(res->el + dst_pos + n,
574 vec->el + dst_pos + n, res->size - dst_pos - n);
577 isl_vec_free(vec);
578 return res;