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