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>
17 isl_ctx
*isl_vec_get_ctx(__isl_keep isl_vec
*vec
)
19 return vec
? vec
->ctx
: NULL
;
22 /* Return a hash value that digests "vec".
24 uint32_t isl_vec_get_hash(__isl_keep isl_vec
*vec
)
29 return isl_seq_get_hash(vec
->el
, vec
->size
);
32 __isl_give isl_vec
*isl_vec_alloc(struct isl_ctx
*ctx
, unsigned size
)
36 vec
= isl_alloc_type(ctx
, struct isl_vec
);
40 vec
->block
= isl_blk_alloc(ctx
, size
);
41 if (isl_blk_is_error(vec
->block
))
48 vec
->el
= vec
->block
.data
;
52 isl_blk_free(ctx
, vec
->block
);
57 __isl_give isl_vec
*isl_vec_extend(__isl_take isl_vec
*vec
, unsigned size
)
61 if (size
<= vec
->size
)
64 vec
= isl_vec_cow(vec
);
68 vec
->block
= isl_blk_extend(vec
->ctx
, vec
->block
, size
);
73 vec
->el
= vec
->block
.data
;
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
86 __isl_give isl_vec
*isl_vec_expand(__isl_take isl_vec
*vec
, int pos
, int n
,
87 int *exp
, int expanded
)
95 isl_die(isl_vec_get_ctx(vec
), isl_error_invalid
,
96 "not an expansion", return isl_vec_free(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
));
103 old_size
= vec
->size
;
104 extra
= expanded
- n
;
105 vec
= isl_vec_extend(vec
, old_size
+ extra
);
106 vec
= isl_vec_cow(vec
);
110 for (i
= old_size
- 1; i
>= pos
+ n
; --i
)
111 isl_int_set(vec
->el
[i
+ extra
], vec
->el
[i
]);
114 for (i
= expanded
- 1; i
>= 0; --i
) {
115 if (j
>= 0 && exp
[j
] == i
) {
117 isl_int_swap(vec
->el
[pos
+ i
],
121 isl_int_set_si(vec
->el
[pos
+ i
], 0);
128 /* Create a vector of size "size" with zero-valued elements.
130 __isl_give isl_vec
*isl_vec_zero(isl_ctx
*ctx
, unsigned size
)
134 vec
= isl_vec_alloc(ctx
, size
);
137 isl_seq_clr(vec
->el
, size
);
141 __isl_give isl_vec
*isl_vec_zero_extend(__isl_take isl_vec
*vec
, unsigned size
)
147 if (size
<= vec
->size
)
150 vec
= isl_vec_cow(vec
);
154 extra
= size
- vec
->size
;
155 vec
= isl_vec_extend(vec
, size
);
159 isl_seq_clr(vec
->el
+ size
- extra
, extra
);
164 /* Return a vector containing the elements of "vec1" followed by
167 __isl_give isl_vec
*isl_vec_concat(__isl_take isl_vec
*vec1
,
168 __isl_take isl_vec
*vec2
)
173 if (vec2
->size
== 0) {
178 if (vec1
->size
== 0) {
183 vec1
= isl_vec_extend(vec1
, vec1
->size
+ vec2
->size
);
187 isl_seq_cpy(vec1
->el
+ vec1
->size
- vec2
->size
, vec2
->el
, vec2
->size
);
197 struct isl_vec
*isl_vec_copy(struct isl_vec
*vec
)
206 struct isl_vec
*isl_vec_dup(struct isl_vec
*vec
)
208 struct isl_vec
*vec2
;
212 vec2
= isl_vec_alloc(vec
->ctx
, vec
->size
);
215 isl_seq_cpy(vec2
->el
, vec
->el
, vec
->size
);
219 struct isl_vec
*isl_vec_cow(struct isl_vec
*vec
)
221 struct isl_vec
*vec2
;
228 vec2
= isl_vec_dup(vec
);
233 __isl_null isl_vec
*isl_vec_free(__isl_take isl_vec
*vec
)
241 isl_ctx_deref(vec
->ctx
);
242 isl_blk_free(vec
->ctx
, vec
->block
);
248 int isl_vec_size(__isl_keep isl_vec
*vec
)
250 return vec
? vec
->size
: -1;
253 /* Check that "pos" is a valid element position for "vec".
255 static isl_stat
check_pos(__isl_keep isl_vec
*vec
, int pos
)
258 return isl_stat_error
;
259 if (pos
< 0 || pos
>= vec
->size
)
260 isl_die(isl_vec_get_ctx(vec
), isl_error_invalid
,
261 "position out of range", return isl_stat_error
);
265 /* Is the element at position "pos" of "vec" equal to zero?
267 isl_bool
isl_vec_element_is_zero(__isl_keep isl_vec
*vec
, int pos
)
269 if (check_pos(vec
, pos
) < 0)
270 return isl_bool_error
;
271 return isl_int_is_zero(vec
->el
[pos
]);
274 /* Extract the element at position "pos" of "vec".
276 __isl_give isl_val
*isl_vec_get_element_val(__isl_keep isl_vec
*vec
, int pos
)
280 if (check_pos(vec
, pos
) < 0)
282 ctx
= isl_vec_get_ctx(vec
);
283 return isl_val_int_from_isl_int(ctx
, vec
->el
[pos
]);
286 __isl_give isl_vec
*isl_vec_set_element(__isl_take isl_vec
*vec
,
289 if (check_pos(vec
, pos
) < 0)
290 return isl_vec_free(vec
);
291 vec
= isl_vec_cow(vec
);
294 isl_int_set(vec
->el
[pos
], v
);
298 __isl_give isl_vec
*isl_vec_set_element_si(__isl_take isl_vec
*vec
,
301 if (check_pos(vec
, pos
) < 0)
302 return isl_vec_free(vec
);
303 vec
= isl_vec_cow(vec
);
306 isl_int_set_si(vec
->el
[pos
], v
);
310 /* Replace the element at position "pos" of "vec" by "v".
312 __isl_give isl_vec
*isl_vec_set_element_val(__isl_take isl_vec
*vec
,
313 int pos
, __isl_take isl_val
*v
)
316 return isl_vec_free(vec
);
317 if (!isl_val_is_int(v
))
318 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
319 "expecting integer value", goto error
);
320 vec
= isl_vec_set_element(vec
, pos
, v
->n
);
325 return isl_vec_free(vec
);
328 /* Compare the elements of "vec1" and "vec2" at position "pos".
330 int isl_vec_cmp_element(__isl_keep isl_vec
*vec1
, __isl_keep isl_vec
*vec2
,
333 if (check_pos(vec1
, pos
) < 0 || check_pos(vec2
, pos
) < 0)
335 return isl_int_cmp(vec1
->el
[pos
], vec2
->el
[pos
]);
338 /* Does "vec" contain only zero elements?
340 isl_bool
isl_vec_is_zero(__isl_keep isl_vec
*vec
)
343 return isl_bool_error
;
344 return isl_seq_first_non_zero(vec
->el
, vec
->size
) < 0;
347 isl_bool
isl_vec_is_equal(__isl_keep isl_vec
*vec1
, __isl_keep isl_vec
*vec2
)
350 return isl_bool_error
;
352 if (vec1
->size
!= vec2
->size
)
353 return isl_bool_false
;
355 return isl_seq_eq(vec1
->el
, vec2
->el
, vec1
->size
);
358 __isl_give isl_printer
*isl_printer_print_vec(__isl_take isl_printer
*printer
,
359 __isl_keep isl_vec
*vec
)
363 if (!printer
|| !vec
)
366 printer
= isl_printer_print_str(printer
, "[");
367 for (i
= 0; i
< vec
->size
; ++i
) {
369 printer
= isl_printer_print_str(printer
, ",");
370 printer
= isl_printer_print_isl_int(printer
, vec
->el
[i
]);
372 printer
= isl_printer_print_str(printer
, "]");
376 isl_printer_free(printer
);
380 void isl_vec_dump(struct isl_vec
*vec
)
382 isl_printer
*printer
;
387 printer
= isl_printer_to_file(vec
->ctx
, stderr
);
388 printer
= isl_printer_print_vec(printer
, vec
);
389 printer
= isl_printer_end_line(printer
);
391 isl_printer_free(printer
);
394 __isl_give isl_vec
*isl_vec_set(__isl_take isl_vec
*vec
, isl_int v
)
396 vec
= isl_vec_cow(vec
);
399 isl_seq_set(vec
->el
, v
, vec
->size
);
403 __isl_give isl_vec
*isl_vec_set_si(__isl_take isl_vec
*vec
, int v
)
405 vec
= isl_vec_cow(vec
);
408 isl_seq_set_si(vec
->el
, v
, vec
->size
);
412 /* Replace all elements of "vec" by "v".
414 __isl_give isl_vec
*isl_vec_set_val(__isl_take isl_vec
*vec
,
415 __isl_take isl_val
*v
)
417 vec
= isl_vec_cow(vec
);
420 if (!isl_val_is_int(v
))
421 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
422 "expecting integer value", goto error
);
423 isl_seq_set(vec
->el
, v
->n
, vec
->size
);
432 __isl_give isl_vec
*isl_vec_clr(__isl_take isl_vec
*vec
)
434 vec
= isl_vec_cow(vec
);
437 isl_seq_clr(vec
->el
, vec
->size
);
441 void isl_vec_lcm(struct isl_vec
*vec
, isl_int
*lcm
)
443 isl_seq_lcm(vec
->block
.data
, vec
->size
, lcm
);
446 /* Given a rational vector, with the denominator in the first element
447 * of the vector, round up all coordinates.
449 __isl_give isl_vec
*isl_vec_ceil(__isl_take isl_vec
*vec
)
451 vec
= isl_vec_cow(vec
);
455 isl_seq_cdiv_q(vec
->el
+ 1, vec
->el
+ 1, vec
->el
[0], vec
->size
- 1);
457 isl_int_set_si(vec
->el
[0], 1);
462 struct isl_vec
*isl_vec_normalize(struct isl_vec
*vec
)
466 isl_seq_normalize(vec
->ctx
, vec
->el
, vec
->size
);
470 __isl_give isl_vec
*isl_vec_neg(__isl_take isl_vec
*vec
)
472 vec
= isl_vec_cow(vec
);
475 isl_seq_neg(vec
->el
, vec
->el
, vec
->size
);
479 __isl_give isl_vec
*isl_vec_scale(__isl_take isl_vec
*vec
, isl_int m
)
481 if (isl_int_is_one(m
))
483 vec
= isl_vec_cow(vec
);
486 isl_seq_scale(vec
->el
, vec
->el
, m
, vec
->size
);
490 /* Reduce the elements of "vec" modulo "m".
492 __isl_give isl_vec
*isl_vec_fdiv_r(__isl_take isl_vec
*vec
, isl_int m
)
494 vec
= isl_vec_cow(vec
);
498 isl_seq_fdiv_r(vec
->el
, vec
->el
, m
, vec
->size
);
503 __isl_give isl_vec
*isl_vec_add(__isl_take isl_vec
*vec1
,
504 __isl_take isl_vec
*vec2
)
506 vec1
= isl_vec_cow(vec1
);
510 isl_assert(vec1
->ctx
, vec1
->size
== vec2
->size
, goto error
);
512 isl_seq_combine(vec1
->el
, vec1
->ctx
->one
, vec1
->el
,
513 vec1
->ctx
->one
, vec2
->el
, vec1
->size
);
523 static int qsort_int_cmp(const void *p1
, const void *p2
)
525 const isl_int
*i1
= (const isl_int
*) p1
;
526 const isl_int
*i2
= (const isl_int
*) p2
;
528 return isl_int_cmp(*i1
, *i2
);
531 __isl_give isl_vec
*isl_vec_sort(__isl_take isl_vec
*vec
)
536 qsort(vec
->el
, vec
->size
, sizeof(*vec
->el
), &qsort_int_cmp
);
541 __isl_give isl_vec
*isl_vec_drop_els(__isl_take isl_vec
*vec
,
542 unsigned pos
, unsigned n
)
546 vec
= isl_vec_cow(vec
);
550 if (pos
+ n
> vec
->size
)
551 isl_die(vec
->ctx
, isl_error_invalid
,
552 "range out of bounds", goto error
);
554 if (pos
+ n
!= vec
->size
)
555 isl_seq_cpy(vec
->el
+ pos
, vec
->el
+ pos
+ n
,
556 vec
->size
- pos
- n
);
566 __isl_give isl_vec
*isl_vec_insert_els(__isl_take isl_vec
*vec
,
567 unsigned pos
, unsigned n
)
577 isl_die(vec
->ctx
, isl_error_invalid
,
578 "position out of bounds", goto error
);
580 ext
= isl_vec_alloc(vec
->ctx
, vec
->size
+ n
);
584 isl_seq_cpy(ext
->el
, vec
->el
, pos
);
585 isl_seq_cpy(ext
->el
+ pos
+ n
, vec
->el
+ pos
, vec
->size
- pos
);
595 __isl_give isl_vec
*isl_vec_insert_zero_els(__isl_take isl_vec
*vec
,
596 unsigned pos
, unsigned n
)
598 vec
= isl_vec_insert_els(vec
, pos
, n
);
602 isl_seq_clr(vec
->el
+ pos
, n
);
607 /* Move the "n" elements starting as "src_pos" of "vec"
608 * to "dst_pos". The elements originally at "dst_pos" are moved
609 * up or down depending on whether "dst_pos" is smaller or greater
612 __isl_give isl_vec
*isl_vec_move_els(__isl_take isl_vec
*vec
,
613 unsigned dst_pos
, unsigned src_pos
, unsigned n
)
620 if (src_pos
+ n
> vec
->size
)
621 isl_die(vec
->ctx
, isl_error_invalid
,
622 "source range out of bounds", return isl_vec_free(vec
));
623 if (dst_pos
+ n
> vec
->size
)
624 isl_die(vec
->ctx
, isl_error_invalid
,
625 "destination range out of bounds",
626 return isl_vec_free(vec
));
628 if (n
== 0 || dst_pos
== src_pos
)
631 res
= isl_vec_alloc(vec
->ctx
, vec
->size
);
633 return isl_vec_free(vec
);
635 if (dst_pos
< src_pos
) {
636 isl_seq_cpy(res
->el
, vec
->el
, dst_pos
);
637 isl_seq_cpy(res
->el
+ dst_pos
, vec
->el
+ src_pos
, n
);
638 isl_seq_cpy(res
->el
+ dst_pos
+ n
,
639 vec
->el
+ dst_pos
, src_pos
- dst_pos
);
640 isl_seq_cpy(res
->el
+ src_pos
+ n
,
641 vec
->el
+ src_pos
+ n
, res
->size
- src_pos
- n
);
643 isl_seq_cpy(res
->el
, vec
->el
, src_pos
);
644 isl_seq_cpy(res
->el
+ src_pos
,
645 vec
->el
+ src_pos
+ n
, dst_pos
- src_pos
);
646 isl_seq_cpy(res
->el
+ dst_pos
, vec
->el
+ src_pos
, n
);
647 isl_seq_cpy(res
->el
+ dst_pos
+ n
,
648 vec
->el
+ dst_pos
+ n
, res
->size
- dst_pos
- n
);