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>
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 /* Return a hash value that digests "vec".
25 uint32_t isl_vec_get_hash(__isl_keep isl_vec
*vec
)
30 return isl_seq_get_hash(vec
->el
, vec
->size
);
33 __isl_give isl_vec
*isl_vec_alloc(struct isl_ctx
*ctx
, unsigned size
)
37 vec
= isl_alloc_type(ctx
, struct isl_vec
);
41 vec
->block
= isl_blk_alloc(ctx
, size
);
42 if (isl_blk_is_error(vec
->block
))
49 vec
->el
= vec
->block
.data
;
53 isl_blk_free(ctx
, vec
->block
);
58 __isl_give isl_vec
*isl_vec_extend(__isl_take isl_vec
*vec
, unsigned size
)
62 if (size
<= vec
->size
)
65 vec
= isl_vec_cow(vec
);
69 vec
->block
= isl_blk_extend(vec
->ctx
, vec
->block
, size
);
74 vec
->el
= vec
->block
.data
;
82 /* Apply the expansion specified by "exp" to the "n" elements starting at "pos".
83 * "expanded" it the number of elements that need to replace those "n"
84 * elements. The entries in "exp" have increasing values between
87 __isl_give isl_vec
*isl_vec_expand(__isl_take isl_vec
*vec
, int pos
, int n
,
88 int *exp
, int expanded
)
96 isl_die(isl_vec_get_ctx(vec
), isl_error_invalid
,
97 "not an expansion", return isl_vec_free(vec
));
100 if (pos
< 0 || n
< 0 || pos
+ n
> vec
->size
)
101 isl_die(isl_vec_get_ctx(vec
), isl_error_invalid
,
102 "position out of bounds", return isl_vec_free(vec
));
104 old_size
= vec
->size
;
105 extra
= expanded
- n
;
106 vec
= isl_vec_extend(vec
, old_size
+ extra
);
107 vec
= isl_vec_cow(vec
);
111 for (i
= old_size
- 1; i
>= pos
+ n
; --i
)
112 isl_int_set(vec
->el
[i
+ extra
], vec
->el
[i
]);
115 for (i
= expanded
- 1; i
>= 0; --i
) {
116 if (j
>= 0 && exp
[j
] == i
) {
118 isl_int_swap(vec
->el
[pos
+ i
],
122 isl_int_set_si(vec
->el
[pos
+ i
], 0);
129 /* Create a vector of size "size" with zero-valued elements.
131 __isl_give isl_vec
*isl_vec_zero(isl_ctx
*ctx
, unsigned size
)
135 vec
= isl_vec_alloc(ctx
, size
);
138 isl_seq_clr(vec
->el
, size
);
142 __isl_give isl_vec
*isl_vec_zero_extend(__isl_take isl_vec
*vec
, unsigned size
)
148 if (size
<= vec
->size
)
151 vec
= isl_vec_cow(vec
);
155 extra
= size
- vec
->size
;
156 vec
= isl_vec_extend(vec
, size
);
160 isl_seq_clr(vec
->el
+ size
- extra
, extra
);
165 /* Return a vector containing the elements of "vec1" followed by
168 __isl_give isl_vec
*isl_vec_concat(__isl_take isl_vec
*vec1
,
169 __isl_take isl_vec
*vec2
)
174 if (vec2
->size
== 0) {
179 if (vec1
->size
== 0) {
184 vec1
= isl_vec_extend(vec1
, vec1
->size
+ vec2
->size
);
188 isl_seq_cpy(vec1
->el
+ vec1
->size
- vec2
->size
, vec2
->el
, vec2
->size
);
198 struct isl_vec
*isl_vec_copy(struct isl_vec
*vec
)
207 struct isl_vec
*isl_vec_dup(struct isl_vec
*vec
)
209 struct isl_vec
*vec2
;
213 vec2
= isl_vec_alloc(vec
->ctx
, vec
->size
);
216 isl_seq_cpy(vec2
->el
, vec
->el
, vec
->size
);
220 struct isl_vec
*isl_vec_cow(struct isl_vec
*vec
)
222 struct isl_vec
*vec2
;
229 vec2
= isl_vec_dup(vec
);
234 __isl_null isl_vec
*isl_vec_free(__isl_take isl_vec
*vec
)
242 isl_ctx_deref(vec
->ctx
);
243 isl_blk_free(vec
->ctx
, vec
->block
);
249 int isl_vec_size(__isl_keep isl_vec
*vec
)
251 return vec
? vec
->size
: -1;
254 int isl_vec_get_element(__isl_keep isl_vec
*vec
, int pos
, isl_int
*v
)
259 if (pos
< 0 || pos
>= vec
->size
)
260 isl_die(vec
->ctx
, isl_error_invalid
, "position out of range",
262 isl_int_set(*v
, vec
->el
[pos
]);
266 /* Extract the element at position "pos" of "vec".
268 __isl_give isl_val
*isl_vec_get_element_val(__isl_keep isl_vec
*vec
, int pos
)
274 ctx
= isl_vec_get_ctx(vec
);
275 if (pos
< 0 || pos
>= vec
->size
)
276 isl_die(ctx
, isl_error_invalid
, "position out of range",
278 return isl_val_int_from_isl_int(ctx
, vec
->el
[pos
]);
281 __isl_give isl_vec
*isl_vec_set_element(__isl_take isl_vec
*vec
,
284 vec
= isl_vec_cow(vec
);
287 if (pos
< 0 || pos
>= vec
->size
)
288 isl_die(vec
->ctx
, isl_error_invalid
, "position out of range",
290 isl_int_set(vec
->el
[pos
], v
);
297 __isl_give isl_vec
*isl_vec_set_element_si(__isl_take isl_vec
*vec
,
300 vec
= isl_vec_cow(vec
);
303 if (pos
< 0 || pos
>= vec
->size
)
304 isl_die(vec
->ctx
, isl_error_invalid
, "position out of range",
306 isl_int_set_si(vec
->el
[pos
], v
);
313 /* Replace the element at position "pos" of "vec" by "v".
315 __isl_give isl_vec
*isl_vec_set_element_val(__isl_take isl_vec
*vec
,
316 int pos
, __isl_take isl_val
*v
)
319 return isl_vec_free(vec
);
320 if (!isl_val_is_int(v
))
321 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
322 "expecting integer value", goto error
);
323 vec
= isl_vec_set_element(vec
, pos
, v
->n
);
328 return isl_vec_free(vec
);
331 /* Compare the elements of "vec1" and "vec2" at position "pos".
333 int isl_vec_cmp_element(__isl_keep isl_vec
*vec1
, __isl_keep isl_vec
*vec2
,
338 if (pos
< 0 || pos
>= vec1
->size
|| pos
>= vec2
->size
)
339 isl_die(isl_vec_get_ctx(vec1
), isl_error_invalid
,
340 "position out of range", return 0);
341 return isl_int_cmp(vec1
->el
[pos
], vec2
->el
[pos
]);
344 /* Does "vec" contain only zero elements?
346 isl_bool
isl_vec_is_zero(__isl_keep isl_vec
*vec
)
349 return isl_bool_error
;
350 return isl_seq_first_non_zero(vec
->el
, vec
->size
) < 0;
353 isl_bool
isl_vec_is_equal(__isl_keep isl_vec
*vec1
, __isl_keep isl_vec
*vec2
)
356 return isl_bool_error
;
358 if (vec1
->size
!= vec2
->size
)
359 return isl_bool_false
;
361 return isl_seq_eq(vec1
->el
, vec2
->el
, vec1
->size
);
364 __isl_give isl_printer
*isl_printer_print_vec(__isl_take isl_printer
*printer
,
365 __isl_keep isl_vec
*vec
)
369 if (!printer
|| !vec
)
372 printer
= isl_printer_print_str(printer
, "[");
373 for (i
= 0; i
< vec
->size
; ++i
) {
375 printer
= isl_printer_print_str(printer
, ",");
376 printer
= isl_printer_print_isl_int(printer
, vec
->el
[i
]);
378 printer
= isl_printer_print_str(printer
, "]");
382 isl_printer_free(printer
);
386 void isl_vec_dump(struct isl_vec
*vec
)
388 isl_printer
*printer
;
393 printer
= isl_printer_to_file(vec
->ctx
, stderr
);
394 printer
= isl_printer_print_vec(printer
, vec
);
395 printer
= isl_printer_end_line(printer
);
397 isl_printer_free(printer
);
400 __isl_give isl_vec
*isl_vec_set(__isl_take isl_vec
*vec
, isl_int v
)
402 vec
= isl_vec_cow(vec
);
405 isl_seq_set(vec
->el
, v
, vec
->size
);
409 __isl_give isl_vec
*isl_vec_set_si(__isl_take isl_vec
*vec
, int v
)
411 vec
= isl_vec_cow(vec
);
414 isl_seq_set_si(vec
->el
, v
, vec
->size
);
418 /* Replace all elements of "vec" by "v".
420 __isl_give isl_vec
*isl_vec_set_val(__isl_take isl_vec
*vec
,
421 __isl_take isl_val
*v
)
423 vec
= isl_vec_cow(vec
);
426 if (!isl_val_is_int(v
))
427 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
428 "expecting integer value", goto error
);
429 isl_seq_set(vec
->el
, v
->n
, vec
->size
);
438 __isl_give isl_vec
*isl_vec_clr(__isl_take isl_vec
*vec
)
440 vec
= isl_vec_cow(vec
);
443 isl_seq_clr(vec
->el
, vec
->size
);
447 void isl_vec_lcm(struct isl_vec
*vec
, isl_int
*lcm
)
449 isl_seq_lcm(vec
->block
.data
, vec
->size
, lcm
);
452 /* Given a rational vector, with the denominator in the first element
453 * of the vector, round up all coordinates.
455 __isl_give isl_vec
*isl_vec_ceil(__isl_take isl_vec
*vec
)
457 vec
= isl_vec_cow(vec
);
461 isl_seq_cdiv_q(vec
->el
+ 1, vec
->el
+ 1, vec
->el
[0], vec
->size
- 1);
463 isl_int_set_si(vec
->el
[0], 1);
468 struct isl_vec
*isl_vec_normalize(struct isl_vec
*vec
)
472 isl_seq_normalize(vec
->ctx
, vec
->el
, vec
->size
);
476 __isl_give isl_vec
*isl_vec_neg(__isl_take isl_vec
*vec
)
478 vec
= isl_vec_cow(vec
);
481 isl_seq_neg(vec
->el
, vec
->el
, vec
->size
);
485 __isl_give isl_vec
*isl_vec_scale(__isl_take isl_vec
*vec
, isl_int m
)
487 if (isl_int_is_one(m
))
489 vec
= isl_vec_cow(vec
);
492 isl_seq_scale(vec
->el
, vec
->el
, m
, vec
->size
);
496 /* Reduce the elements of "vec" modulo "m".
498 __isl_give isl_vec
*isl_vec_fdiv_r(__isl_take isl_vec
*vec
, isl_int m
)
500 vec
= isl_vec_cow(vec
);
504 isl_seq_fdiv_r(vec
->el
, vec
->el
, m
, vec
->size
);
509 __isl_give isl_vec
*isl_vec_add(__isl_take isl_vec
*vec1
,
510 __isl_take isl_vec
*vec2
)
512 vec1
= isl_vec_cow(vec1
);
516 isl_assert(vec1
->ctx
, vec1
->size
== vec2
->size
, goto error
);
518 isl_seq_combine(vec1
->el
, vec1
->ctx
->one
, vec1
->el
,
519 vec1
->ctx
->one
, vec2
->el
, vec1
->size
);
529 static int qsort_int_cmp(const void *p1
, const void *p2
)
531 const isl_int
*i1
= (const isl_int
*) p1
;
532 const isl_int
*i2
= (const isl_int
*) p2
;
534 return isl_int_cmp(*i1
, *i2
);
537 __isl_give isl_vec
*isl_vec_sort(__isl_take isl_vec
*vec
)
542 qsort(vec
->el
, vec
->size
, sizeof(*vec
->el
), &qsort_int_cmp
);
547 __isl_give isl_vec
*isl_vec_drop_els(__isl_take isl_vec
*vec
,
548 unsigned pos
, unsigned n
)
552 vec
= isl_vec_cow(vec
);
556 if (pos
+ n
> vec
->size
)
557 isl_die(vec
->ctx
, isl_error_invalid
,
558 "range out of bounds", goto error
);
560 if (pos
+ n
!= vec
->size
)
561 isl_seq_cpy(vec
->el
+ pos
, vec
->el
+ pos
+ n
,
562 vec
->size
- pos
- n
);
572 __isl_give isl_vec
*isl_vec_insert_els(__isl_take isl_vec
*vec
,
573 unsigned pos
, unsigned n
)
583 isl_die(vec
->ctx
, isl_error_invalid
,
584 "position out of bounds", goto error
);
586 ext
= isl_vec_alloc(vec
->ctx
, vec
->size
+ n
);
590 isl_seq_cpy(ext
->el
, vec
->el
, pos
);
591 isl_seq_cpy(ext
->el
+ pos
+ n
, vec
->el
+ pos
, vec
->size
- pos
);
601 __isl_give isl_vec
*isl_vec_insert_zero_els(__isl_take isl_vec
*vec
,
602 unsigned pos
, unsigned n
)
604 vec
= isl_vec_insert_els(vec
, pos
, n
);
608 isl_seq_clr(vec
->el
+ pos
, n
);
613 /* Move the "n" elements starting as "src_pos" of "vec"
614 * to "dst_pos". The elements originally at "dst_pos" are moved
615 * up or down depending on whether "dst_pos" is smaller or greater
618 __isl_give isl_vec
*isl_vec_move_els(__isl_take isl_vec
*vec
,
619 unsigned dst_pos
, unsigned src_pos
, unsigned n
)
626 if (src_pos
+ n
> vec
->size
)
627 isl_die(vec
->ctx
, isl_error_invalid
,
628 "source range out of bounds", return isl_vec_free(vec
));
629 if (dst_pos
+ n
> vec
->size
)
630 isl_die(vec
->ctx
, isl_error_invalid
,
631 "destination range out of bounds",
632 return isl_vec_free(vec
));
634 if (n
== 0 || dst_pos
== src_pos
)
637 res
= isl_vec_alloc(vec
->ctx
, vec
->size
);
639 return isl_vec_free(vec
);
641 if (dst_pos
< src_pos
) {
642 isl_seq_cpy(res
->el
, vec
->el
, dst_pos
);
643 isl_seq_cpy(res
->el
+ dst_pos
, vec
->el
+ src_pos
, n
);
644 isl_seq_cpy(res
->el
+ dst_pos
+ n
,
645 vec
->el
+ dst_pos
, src_pos
- dst_pos
);
646 isl_seq_cpy(res
->el
+ src_pos
+ n
,
647 vec
->el
+ src_pos
+ n
, res
->size
- src_pos
- n
);
649 isl_seq_cpy(res
->el
, vec
->el
, src_pos
);
650 isl_seq_cpy(res
->el
+ src_pos
,
651 vec
->el
+ src_pos
+ n
, dst_pos
- src_pos
);
652 isl_seq_cpy(res
->el
+ dst_pos
, vec
->el
+ src_pos
, n
);
653 isl_seq_cpy(res
->el
+ dst_pos
+ n
,
654 vec
->el
+ dst_pos
+ n
, res
->size
- dst_pos
- n
);