1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2013 Ecole Normale Superieure
4 *
5 * Use of this software is governed by the MIT license
6 *
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
10 */
11
12 #include <isl_ctx_private.h>
13 #include <isl_seq.h>
14 #include <isl_val_private.h>
15 #include <isl_vec_private.h>
16
isl_vec_get_ctx(__isl_keep isl_vec * vec)17 isl_ctx *isl_vec_get_ctx(__isl_keep isl_vec *vec)
18 {
19 return vec ? vec->ctx : NULL;
20 }
21
22 /* Return a hash value that digests "vec".
23 */
isl_vec_get_hash(__isl_keep isl_vec * vec)24 uint32_t isl_vec_get_hash(__isl_keep isl_vec *vec)
25 {
26 if (!vec)
27 return 0;
28
29 return isl_seq_get_hash(vec->el, vec->size);
30 }
31
isl_vec_alloc(struct isl_ctx * ctx,unsigned size)32 __isl_give isl_vec *isl_vec_alloc(struct isl_ctx *ctx, unsigned size)
33 {
34 struct isl_vec *vec;
35
36 vec = isl_alloc_type(ctx, struct isl_vec);
37 if (!vec)
38 return NULL;
39
40 vec->block = isl_blk_alloc(ctx, size);
41 if (isl_blk_is_error(vec->block))
42 goto error;
43
44 vec->ctx = ctx;
45 isl_ctx_ref(ctx);
46 vec->ref = 1;
47 vec->size = size;
48 vec->el = vec->block.data;
49
50 return vec;
51 error:
52 isl_blk_free(ctx, vec->block);
53 free(vec);
54 return NULL;
55 }
56
isl_vec_extend(__isl_take isl_vec * vec,unsigned size)57 __isl_give isl_vec *isl_vec_extend(__isl_take isl_vec *vec, unsigned size)
58 {
59 if (!vec)
60 return NULL;
61 if (size <= vec->size)
62 return vec;
63
64 vec = isl_vec_cow(vec);
65 if (!vec)
66 return NULL;
67
68 vec->block = isl_blk_extend(vec->ctx, vec->block, size);
69 if (!vec->block.data)
70 goto error;
71
72 vec->size = size;
73 vec->el = vec->block.data;
74
75 return vec;
76 error:
77 isl_vec_free(vec);
78 return NULL;
79 }
80
81 /* Apply the expansion specified by "exp" to the "n" elements starting at "pos".
82 * "expanded" it the number of elements that need to replace those "n"
83 * elements. The entries in "exp" have increasing values between
84 * 0 and "expanded".
85 */
isl_vec_expand(__isl_take isl_vec * vec,int pos,int n,int * exp,int expanded)86 __isl_give isl_vec *isl_vec_expand(__isl_take isl_vec *vec, int pos, int n,
87 int *exp, int expanded)
88 {
89 int i, j;
90 int old_size, extra;
91
92 if (!vec)
93 return NULL;
94 if (expanded < n)
95 isl_die(isl_vec_get_ctx(vec), isl_error_invalid,
96 "not an expansion", return isl_vec_free(vec));
97 if (expanded == n)
98 return vec;
99 if (pos < 0 || n < 0 || pos + n > vec->size)
100 isl_die(isl_vec_get_ctx(vec), isl_error_invalid,
101 "position out of bounds", return isl_vec_free(vec));
102
103 old_size = vec->size;
104 extra = expanded - n;
105 vec = isl_vec_extend(vec, old_size + extra);
106 vec = isl_vec_cow(vec);
107 if (!vec)
108 return NULL;
109
110 for (i = old_size - 1; i >= pos + n; --i)
111 isl_int_set(vec->el[i + extra], vec->el[i]);
112
113 j = n - 1;
114 for (i = expanded - 1; i >= 0; --i) {
115 if (j >= 0 && exp[j] == i) {
116 if (i != j)
117 isl_int_swap(vec->el[pos + i],
118 vec->el[pos + j]);
119 j--;
120 } else {
121 isl_int_set_si(vec->el[pos + i], 0);
122 }
123 }
124
125 return vec;
126 }
127
128 /* Create a vector of size "size" with zero-valued elements.
129 */
isl_vec_zero(isl_ctx * ctx,unsigned size)130 __isl_give isl_vec *isl_vec_zero(isl_ctx *ctx, unsigned size)
131 {
132 isl_vec *vec;
133
134 vec = isl_vec_alloc(ctx, size);
135 if (!vec)
136 return NULL;
137 isl_seq_clr(vec->el, size);
138 return vec;
139 }
140
isl_vec_zero_extend(__isl_take isl_vec * vec,unsigned size)141 __isl_give isl_vec *isl_vec_zero_extend(__isl_take isl_vec *vec, unsigned size)
142 {
143 int extra;
144
145 if (!vec)
146 return NULL;
147 if (size <= vec->size)
148 return vec;
149
150 vec = isl_vec_cow(vec);
151 if (!vec)
152 return NULL;
153
154 extra = size - vec->size;
155 vec = isl_vec_extend(vec, size);
156 if (!vec)
157 return NULL;
158
159 isl_seq_clr(vec->el + size - extra, extra);
160
161 return vec;
162 }
163
164 /* Return a vector containing the elements of "vec1" followed by
165 * those of "vec2".
166 */
isl_vec_concat(__isl_take isl_vec * vec1,__isl_take isl_vec * vec2)167 __isl_give isl_vec *isl_vec_concat(__isl_take isl_vec *vec1,
168 __isl_take isl_vec *vec2)
169 {
170 if (!vec1 || !vec2)
171 goto error;
172
173 if (vec2->size == 0) {
174 isl_vec_free(vec2);
175 return vec1;
176 }
177
178 if (vec1->size == 0) {
179 isl_vec_free(vec1);
180 return vec2;
181 }
182
183 vec1 = isl_vec_extend(vec1, vec1->size + vec2->size);
184 if (!vec1)
185 goto error;
186
187 isl_seq_cpy(vec1->el + vec1->size - vec2->size, vec2->el, vec2->size);
188
189 isl_vec_free(vec2);
190 return vec1;
191 error:
192 isl_vec_free(vec1);
193 isl_vec_free(vec2);
194 return NULL;
195 }
196
isl_vec_copy(__isl_keep isl_vec * vec)197 __isl_give isl_vec *isl_vec_copy(__isl_keep isl_vec *vec)
198 {
199 if (!vec)
200 return NULL;
201
202 vec->ref++;
203 return vec;
204 }
205
isl_vec_dup(__isl_keep isl_vec * vec)206 __isl_give isl_vec *isl_vec_dup(__isl_keep isl_vec *vec)
207 {
208 struct isl_vec *vec2;
209
210 if (!vec)
211 return NULL;
212 vec2 = isl_vec_alloc(vec->ctx, vec->size);
213 if (!vec2)
214 return NULL;
215 isl_seq_cpy(vec2->el, vec->el, vec->size);
216 return vec2;
217 }
218
isl_vec_cow(__isl_take isl_vec * vec)219 __isl_give isl_vec *isl_vec_cow(__isl_take isl_vec *vec)
220 {
221 struct isl_vec *vec2;
222 if (!vec)
223 return NULL;
224
225 if (vec->ref == 1)
226 return vec;
227
228 vec2 = isl_vec_dup(vec);
229 isl_vec_free(vec);
230 return vec2;
231 }
232
isl_vec_free(__isl_take isl_vec * vec)233 __isl_null isl_vec *isl_vec_free(__isl_take isl_vec *vec)
234 {
235 if (!vec)
236 return NULL;
237
238 if (--vec->ref > 0)
239 return NULL;
240
241 isl_ctx_deref(vec->ctx);
242 isl_blk_free(vec->ctx, vec->block);
243 free(vec);
244
245 return NULL;
246 }
247
isl_vec_size(__isl_keep isl_vec * vec)248 isl_size isl_vec_size(__isl_keep isl_vec *vec)
249 {
250 return vec ? vec->size : isl_size_error;
251 }
252
253 /* Extract the element at position "pos" of "vec".
254 */
isl_vec_get_element_val(__isl_keep isl_vec * vec,int pos)255 __isl_give isl_val *isl_vec_get_element_val(__isl_keep isl_vec *vec, int pos)
256 {
257 isl_ctx *ctx;
258
259 if (!vec)
260 return NULL;
261 ctx = isl_vec_get_ctx(vec);
262 if (pos < 0 || pos >= vec->size)
263 isl_die(ctx, isl_error_invalid, "position out of range",
264 return NULL);
265 return isl_val_int_from_isl_int(ctx, vec->el[pos]);
266 }
267
isl_vec_set_element(__isl_take isl_vec * vec,int pos,isl_int v)268 __isl_give isl_vec *isl_vec_set_element(__isl_take isl_vec *vec,
269 int pos, isl_int v)
270 {
271 vec = isl_vec_cow(vec);
272 if (!vec)
273 return NULL;
274 if (pos < 0 || pos >= vec->size)
275 isl_die(vec->ctx, isl_error_invalid, "position out of range",
276 goto error);
277 isl_int_set(vec->el[pos], v);
278 return vec;
279 error:
280 isl_vec_free(vec);
281 return NULL;
282 }
283
isl_vec_set_element_si(__isl_take isl_vec * vec,int pos,int v)284 __isl_give isl_vec *isl_vec_set_element_si(__isl_take isl_vec *vec,
285 int pos, int v)
286 {
287 vec = isl_vec_cow(vec);
288 if (!vec)
289 return NULL;
290 if (pos < 0 || pos >= vec->size)
291 isl_die(vec->ctx, isl_error_invalid, "position out of range",
292 goto error);
293 isl_int_set_si(vec->el[pos], v);
294 return vec;
295 error:
296 isl_vec_free(vec);
297 return NULL;
298 }
299
300 /* Replace the element at position "pos" of "vec" by "v".
301 */
isl_vec_set_element_val(__isl_take isl_vec * vec,int pos,__isl_take isl_val * v)302 __isl_give isl_vec *isl_vec_set_element_val(__isl_take isl_vec *vec,
303 int pos, __isl_take isl_val *v)
304 {
305 if (!v)
306 return isl_vec_free(vec);
307 if (!isl_val_is_int(v))
308 isl_die(isl_val_get_ctx(v), isl_error_invalid,
309 "expecting integer value", goto error);
310 vec = isl_vec_set_element(vec, pos, v->n);
311 isl_val_free(v);
312 return vec;
313 error:
314 isl_val_free(v);
315 return isl_vec_free(vec);
316 }
317
318 /* Compare the elements of "vec1" and "vec2" at position "pos".
319 */
isl_vec_cmp_element(__isl_keep isl_vec * vec1,__isl_keep isl_vec * vec2,int pos)320 int isl_vec_cmp_element(__isl_keep isl_vec *vec1, __isl_keep isl_vec *vec2,
321 int pos)
322 {
323 if (!vec1 || !vec2)
324 return 0;
325 if (pos < 0 || pos >= vec1->size || pos >= vec2->size)
326 isl_die(isl_vec_get_ctx(vec1), isl_error_invalid,
327 "position out of range", return 0);
328 return isl_int_cmp(vec1->el[pos], vec2->el[pos]);
329 }
330
331 /* Does "vec" contain only zero elements?
332 */
isl_vec_is_zero(__isl_keep isl_vec * vec)333 isl_bool isl_vec_is_zero(__isl_keep isl_vec *vec)
334 {
335 if (!vec)
336 return isl_bool_error;
337 return isl_bool_ok(isl_seq_first_non_zero(vec->el, vec->size) < 0);
338 }
339
isl_vec_is_equal(__isl_keep isl_vec * vec1,__isl_keep isl_vec * vec2)340 isl_bool isl_vec_is_equal(__isl_keep isl_vec *vec1, __isl_keep isl_vec *vec2)
341 {
342 if (!vec1 || !vec2)
343 return isl_bool_error;
344
345 if (vec1->size != vec2->size)
346 return isl_bool_false;
347
348 return isl_bool_ok(isl_seq_eq(vec1->el, vec2->el, vec1->size));
349 }
350
isl_printer_print_vec(__isl_take isl_printer * printer,__isl_keep isl_vec * vec)351 __isl_give isl_printer *isl_printer_print_vec(__isl_take isl_printer *printer,
352 __isl_keep isl_vec *vec)
353 {
354 int i;
355
356 if (!printer || !vec)
357 goto error;
358
359 printer = isl_printer_print_str(printer, "[");
360 for (i = 0; i < vec->size; ++i) {
361 if (i)
362 printer = isl_printer_print_str(printer, ",");
363 printer = isl_printer_print_isl_int(printer, vec->el[i]);
364 }
365 printer = isl_printer_print_str(printer, "]");
366
367 return printer;
368 error:
369 isl_printer_free(printer);
370 return NULL;
371 }
372
isl_vec_dump(__isl_keep isl_vec * vec)373 void isl_vec_dump(__isl_keep isl_vec *vec)
374 {
375 isl_printer *printer;
376
377 if (!vec)
378 return;
379
380 printer = isl_printer_to_file(vec->ctx, stderr);
381 printer = isl_printer_print_vec(printer, vec);
382 printer = isl_printer_end_line(printer);
383
384 isl_printer_free(printer);
385 }
386
isl_vec_set(__isl_take isl_vec * vec,isl_int v)387 __isl_give isl_vec *isl_vec_set(__isl_take isl_vec *vec, isl_int v)
388 {
389 vec = isl_vec_cow(vec);
390 if (!vec)
391 return NULL;
392 isl_seq_set(vec->el, v, vec->size);
393 return vec;
394 }
395
isl_vec_set_si(__isl_take isl_vec * vec,int v)396 __isl_give isl_vec *isl_vec_set_si(__isl_take isl_vec *vec, int v)
397 {
398 vec = isl_vec_cow(vec);
399 if (!vec)
400 return NULL;
401 isl_seq_set_si(vec->el, v, vec->size);
402 return vec;
403 }
404
405 /* Replace all elements of "vec" by "v".
406 */
isl_vec_set_val(__isl_take isl_vec * vec,__isl_take isl_val * v)407 __isl_give isl_vec *isl_vec_set_val(__isl_take isl_vec *vec,
408 __isl_take isl_val *v)
409 {
410 vec = isl_vec_cow(vec);
411 if (!vec || !v)
412 goto error;
413 if (!isl_val_is_int(v))
414 isl_die(isl_val_get_ctx(v), isl_error_invalid,
415 "expecting integer value", goto error);
416 isl_seq_set(vec->el, v->n, vec->size);
417 isl_val_free(v);
418 return vec;
419 error:
420 isl_vec_free(vec);
421 isl_val_free(v);
422 return NULL;
423 }
424
isl_vec_clr(__isl_take isl_vec * vec)425 __isl_give isl_vec *isl_vec_clr(__isl_take isl_vec *vec)
426 {
427 vec = isl_vec_cow(vec);
428 if (!vec)
429 return NULL;
430 isl_seq_clr(vec->el, vec->size);
431 return vec;
432 }
433
isl_vec_lcm(__isl_keep isl_vec * vec,isl_int * lcm)434 void isl_vec_lcm(__isl_keep isl_vec *vec, isl_int *lcm)
435 {
436 isl_seq_lcm(vec->block.data, vec->size, lcm);
437 }
438
439 /* Given a rational vector, with the denominator in the first element
440 * of the vector, round up all coordinates.
441 */
isl_vec_ceil(__isl_take isl_vec * vec)442 __isl_give isl_vec *isl_vec_ceil(__isl_take isl_vec *vec)
443 {
444 vec = isl_vec_cow(vec);
445 if (!vec)
446 return NULL;
447
448 isl_seq_cdiv_q(vec->el + 1, vec->el + 1, vec->el[0], vec->size - 1);
449
450 isl_int_set_si(vec->el[0], 1);
451
452 return vec;
453 }
454
isl_vec_normalize(__isl_take isl_vec * vec)455 __isl_give isl_vec *isl_vec_normalize(__isl_take isl_vec *vec)
456 {
457 if (!vec)
458 return NULL;
459 isl_seq_normalize(vec->ctx, vec->el, vec->size);
460 return vec;
461 }
462
isl_vec_neg(__isl_take isl_vec * vec)463 __isl_give isl_vec *isl_vec_neg(__isl_take isl_vec *vec)
464 {
465 vec = isl_vec_cow(vec);
466 if (!vec)
467 return NULL;
468 isl_seq_neg(vec->el, vec->el, vec->size);
469 return vec;
470 }
471
isl_vec_scale(__isl_take isl_vec * vec,isl_int m)472 __isl_give isl_vec *isl_vec_scale(__isl_take isl_vec *vec, isl_int m)
473 {
474 if (isl_int_is_one(m))
475 return vec;
476 vec = isl_vec_cow(vec);
477 if (!vec)
478 return NULL;
479 isl_seq_scale(vec->el, vec->el, m, vec->size);
480 return vec;
481 }
482
483 /* Reduce the elements of "vec" modulo "m".
484 */
isl_vec_fdiv_r(__isl_take isl_vec * vec,isl_int m)485 __isl_give isl_vec *isl_vec_fdiv_r(__isl_take isl_vec *vec, isl_int m)
486 {
487 vec = isl_vec_cow(vec);
488 if (!vec)
489 return NULL;
490
491 isl_seq_fdiv_r(vec->el, vec->el, m, vec->size);
492
493 return vec;
494 }
495
isl_vec_add(__isl_take isl_vec * vec1,__isl_take isl_vec * vec2)496 __isl_give isl_vec *isl_vec_add(__isl_take isl_vec *vec1,
497 __isl_take isl_vec *vec2)
498 {
499 vec1 = isl_vec_cow(vec1);
500 if (!vec1 || !vec2)
501 goto error;
502
503 isl_assert(vec1->ctx, vec1->size == vec2->size, goto error);
504
505 isl_seq_combine(vec1->el, vec1->ctx->one, vec1->el,
506 vec1->ctx->one, vec2->el, vec1->size);
507
508 isl_vec_free(vec2);
509 return vec1;
510 error:
511 isl_vec_free(vec1);
512 isl_vec_free(vec2);
513 return NULL;
514 }
515
qsort_int_cmp(const void * p1,const void * p2)516 static int qsort_int_cmp(const void *p1, const void *p2)
517 {
518 const isl_int *i1 = (const isl_int *) p1;
519 const isl_int *i2 = (const isl_int *) p2;
520
521 return isl_int_cmp(*i1, *i2);
522 }
523
isl_vec_sort(__isl_take isl_vec * vec)524 __isl_give isl_vec *isl_vec_sort(__isl_take isl_vec *vec)
525 {
526 if (!vec)
527 return NULL;
528
529 qsort(vec->el, vec->size, sizeof(*vec->el), &qsort_int_cmp);
530
531 return vec;
532 }
533
isl_vec_drop_els(__isl_take isl_vec * vec,unsigned pos,unsigned n)534 __isl_give isl_vec *isl_vec_drop_els(__isl_take isl_vec *vec,
535 unsigned pos, unsigned n)
536 {
537 if (n == 0)
538 return vec;
539 vec = isl_vec_cow(vec);
540 if (!vec)
541 return NULL;
542
543 if (pos + n > vec->size)
544 isl_die(vec->ctx, isl_error_invalid,
545 "range out of bounds", goto error);
546
547 if (pos + n != vec->size)
548 isl_seq_cpy(vec->el + pos, vec->el + pos + n,
549 vec->size - pos - n);
550
551 vec->size -= n;
552
553 return vec;
554 error:
555 isl_vec_free(vec);
556 return NULL;
557 }
558
isl_vec_insert_els(__isl_take isl_vec * vec,unsigned pos,unsigned n)559 __isl_give isl_vec *isl_vec_insert_els(__isl_take isl_vec *vec,
560 unsigned pos, unsigned n)
561 {
562 isl_vec *ext = NULL;
563
564 if (n == 0)
565 return vec;
566 if (!vec)
567 return NULL;
568
569 if (pos > vec->size)
570 isl_die(vec->ctx, isl_error_invalid,
571 "position out of bounds", goto error);
572
573 ext = isl_vec_alloc(vec->ctx, vec->size + n);
574 if (!ext)
575 goto error;
576
577 isl_seq_cpy(ext->el, vec->el, pos);
578 isl_seq_cpy(ext->el + pos + n, vec->el + pos, vec->size - pos);
579
580 isl_vec_free(vec);
581 return ext;
582 error:
583 isl_vec_free(vec);
584 isl_vec_free(ext);
585 return NULL;
586 }
587
588 /* Add "n" elements at the end of "vec".
589 */
isl_vec_add_els(__isl_take isl_vec * vec,unsigned n)590 __isl_give isl_vec *isl_vec_add_els(__isl_take isl_vec *vec, unsigned n)
591 {
592 if (!vec)
593 return NULL;
594 return isl_vec_insert_els(vec, vec->size, n);
595 }
596
isl_vec_insert_zero_els(__isl_take isl_vec * vec,unsigned pos,unsigned n)597 __isl_give isl_vec *isl_vec_insert_zero_els(__isl_take isl_vec *vec,
598 unsigned pos, unsigned n)
599 {
600 vec = isl_vec_insert_els(vec, pos, n);
601 if (!vec)
602 return NULL;
603
604 isl_seq_clr(vec->el + pos, n);
605
606 return vec;
607 }
608
609 /* Move the "n" elements starting as "src_pos" of "vec"
610 * to "dst_pos". The elements originally at "dst_pos" are moved
611 * up or down depending on whether "dst_pos" is smaller or greater
612 * than "src_pos".
613 */
isl_vec_move_els(__isl_take isl_vec * vec,unsigned dst_pos,unsigned src_pos,unsigned n)614 __isl_give isl_vec *isl_vec_move_els(__isl_take isl_vec *vec,
615 unsigned dst_pos, unsigned src_pos, unsigned n)
616 {
617 isl_vec *res;
618
619 if (!vec)
620 return NULL;
621
622 if (src_pos + n > vec->size)
623 isl_die(vec->ctx, isl_error_invalid,
624 "source range out of bounds", return isl_vec_free(vec));
625 if (dst_pos + n > vec->size)
626 isl_die(vec->ctx, isl_error_invalid,
627 "destination range out of bounds",
628 return isl_vec_free(vec));
629
630 if (n == 0 || dst_pos == src_pos)
631 return vec;
632
633 res = isl_vec_alloc(vec->ctx, vec->size);
634 if (!res)
635 return isl_vec_free(vec);
636
637 if (dst_pos < src_pos) {
638 isl_seq_cpy(res->el, vec->el, dst_pos);
639 isl_seq_cpy(res->el + dst_pos, vec->el + src_pos, n);
640 isl_seq_cpy(res->el + dst_pos + n,
641 vec->el + dst_pos, src_pos - dst_pos);
642 isl_seq_cpy(res->el + src_pos + n,
643 vec->el + src_pos + n, res->size - src_pos - n);
644 } else {
645 isl_seq_cpy(res->el, vec->el, src_pos);
646 isl_seq_cpy(res->el + src_pos,
647 vec->el + src_pos + n, dst_pos - src_pos);
648 isl_seq_cpy(res->el + dst_pos, vec->el + src_pos, n);
649 isl_seq_cpy(res->el + dst_pos + n,
650 vec->el + dst_pos + n, res->size - dst_pos - n);
651 }
652
653 isl_vec_free(vec);
654 return res;
655 }
656