xref: /netbsd-src/external/mit/isl/dist/isl_point.c (revision 5971e316fdea024efff6be8f03536623db06833e)
1 /*
2  * Copyright 2010      INRIA Saclay
3  * Copyright 2013      Ecole Normale Superieure
4  * Copyright 2015      Sven Verdoolaege
5  * Copyright 2019,2022 Cerebras Systems
6  *
7  * Use of this software is governed by the MIT license
8  *
9  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
10  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
11  * 91893 Orsay, France
12  * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
13  * and Cerebras Systems, 175 S San Antonio Rd, Los Altos, CA, USA
14  * and Cerebras Systems, 1237 E Arques Ave, Sunnyvale, CA, USA
15  */
16 
17 #include <isl_map_private.h>
18 #include <isl_point_private.h>
19 #include <isl/set.h>
20 #include <isl/union_set.h>
21 #include <isl_sample.h>
22 #include <isl_scan.h>
23 #include <isl_seq.h>
24 #include <isl_space_private.h>
25 #include <isl_local_private.h>
26 #include <isl_val_private.h>
27 #include <isl_vec_private.h>
28 #include <isl_output_private.h>
29 
30 #include <set_to_map.c>
31 
isl_point_get_ctx(__isl_keep isl_point * pnt)32 isl_ctx *isl_point_get_ctx(__isl_keep isl_point *pnt)
33 {
34 	return pnt ? isl_space_get_ctx(pnt->dim) : NULL;
35 }
36 
37 /* Return the space of "pnt".
38  */
isl_point_peek_space(__isl_keep isl_point * pnt)39 __isl_keep isl_space *isl_point_peek_space(__isl_keep isl_point *pnt)
40 {
41 	return pnt ? pnt->dim : NULL;
42 }
43 
isl_point_get_space(__isl_keep isl_point * pnt)44 __isl_give isl_space *isl_point_get_space(__isl_keep isl_point *pnt)
45 {
46 	return isl_space_copy(isl_point_peek_space(pnt));
47 }
48 
49 #undef TYPE1
50 #define TYPE1		isl_basic_map
51 #undef TYPE2
52 #define TYPE2		isl_point
53 #undef TYPE_PAIR
54 #define TYPE_PAIR	isl_basic_map_point
55 
56 static
57 #include "isl_type_has_equal_space_templ.c"
58 static
59 #include "isl_type_check_equal_space_templ.c"
60 
61 #undef TYPE
62 #define TYPE isl_point
63 
64 #include "isl_check_named_params_templ.c"
65 
isl_point_alloc(__isl_take isl_space * space,__isl_take isl_vec * vec)66 __isl_give isl_point *isl_point_alloc(__isl_take isl_space *space,
67 	__isl_take isl_vec *vec)
68 {
69 	struct isl_point *pnt;
70 	isl_size dim;
71 
72 	dim = isl_space_dim(space, isl_dim_all);
73 	if (dim < 0 || !vec)
74 		goto error;
75 
76 	if (vec->size > 1 + dim) {
77 		vec = isl_vec_cow(vec);
78 		if (!vec)
79 			goto error;
80 		vec->size = 1 + dim;
81 	}
82 
83 	pnt = isl_alloc_type(space->ctx, struct isl_point);
84 	if (!pnt)
85 		goto error;
86 
87 	pnt->ref = 1;
88 	pnt->dim = space;
89 	pnt->vec = vec;
90 
91 	return pnt;
92 error:
93 	isl_space_free(space);
94 	isl_vec_free(vec);
95 	return NULL;
96 }
97 
isl_point_zero(__isl_take isl_space * space)98 __isl_give isl_point *isl_point_zero(__isl_take isl_space *space)
99 {
100 	isl_vec *vec;
101 	isl_size dim;
102 
103 	dim = isl_space_dim(space, isl_dim_all);
104 	if (dim < 0)
105 		goto error;
106 	vec = isl_vec_alloc(space->ctx, 1 + dim);
107 	if (!vec)
108 		goto error;
109 	isl_int_set_si(vec->el[0], 1);
110 	isl_seq_clr(vec->el + 1, vec->size - 1);
111 	return isl_point_alloc(space, vec);
112 error:
113 	isl_space_free(space);
114 	return NULL;
115 }
116 
isl_point_dup(__isl_keep isl_point * pnt)117 __isl_give isl_point *isl_point_dup(__isl_keep isl_point *pnt)
118 {
119 	struct isl_point *pnt2;
120 
121 	if (!pnt)
122 		return NULL;
123 	pnt2 = isl_point_alloc(isl_space_copy(pnt->dim), isl_vec_copy(pnt->vec));
124 	return pnt2;
125 }
126 
isl_point_cow(__isl_take isl_point * pnt)127 __isl_give isl_point *isl_point_cow(__isl_take isl_point *pnt)
128 {
129 	struct isl_point *pnt2;
130 	if (!pnt)
131 		return NULL;
132 
133 	if (pnt->ref == 1)
134 		return pnt;
135 
136 	pnt2 = isl_point_dup(pnt);
137 	isl_point_free(pnt);
138 	return pnt2;
139 }
140 
isl_point_copy(__isl_keep isl_point * pnt)141 __isl_give isl_point *isl_point_copy(__isl_keep isl_point *pnt)
142 {
143 	if (!pnt)
144 		return NULL;
145 
146 	pnt->ref++;
147 	return pnt;
148 }
149 
isl_point_free(__isl_take isl_point * pnt)150 __isl_null isl_point *isl_point_free(__isl_take isl_point *pnt)
151 {
152 	if (!pnt)
153 		return NULL;
154 
155 	if (--pnt->ref > 0)
156 		return NULL;
157 
158 	isl_space_free(pnt->dim);
159 	isl_vec_free(pnt->vec);
160 	free(pnt);
161 	return NULL;
162 }
163 
isl_point_void(__isl_take isl_space * space)164 __isl_give isl_point *isl_point_void(__isl_take isl_space *space)
165 {
166 	if (!space)
167 		return NULL;
168 
169 	return isl_point_alloc(space, isl_vec_alloc(space->ctx, 0));
170 }
171 
isl_point_is_void(__isl_keep isl_point * pnt)172 isl_bool isl_point_is_void(__isl_keep isl_point *pnt)
173 {
174 	if (!pnt)
175 		return isl_bool_error;
176 
177 	return isl_bool_ok(pnt->vec->size == 0);
178 }
179 
180 /* Return the space of "pnt".
181  * This may be either a copy or the space itself
182  * if there is only one reference to "pnt".
183  * This allows the space to be modified inplace
184  * if both the point and its space have only a single reference.
185  * The caller is not allowed to modify "pnt" between this call and
186  * a subsequent call to isl_point_restore_space.
187  * The only exception is that isl_point_free can be called instead.
188  */
isl_point_take_space(__isl_keep isl_point * pnt)189 __isl_give isl_space *isl_point_take_space(__isl_keep isl_point *pnt)
190 {
191 	isl_space *space;
192 
193 	if (!pnt)
194 		return NULL;
195 	if (pnt->ref != 1)
196 		return isl_point_get_space(pnt);
197 	space = pnt->dim;
198 	pnt->dim = NULL;
199 	return space;
200 }
201 
202 /* Set the space of "pnt" to "space", where the space of "pnt" may be missing
203  * due to a preceding call to isl_point_take_space.
204  * However, in this case, "pnt" only has a single reference and
205  * then the call to isl_point_cow has no effect.
206  */
isl_point_restore_space(__isl_take isl_point * pnt,__isl_take isl_space * space)207 __isl_give isl_point *isl_point_restore_space(__isl_take isl_point *pnt,
208 	__isl_take isl_space *space)
209 {
210 	if (!pnt || !space)
211 		goto error;
212 
213 	if (pnt->dim == space) {
214 		isl_space_free(space);
215 		return pnt;
216 	}
217 
218 	pnt = isl_point_cow(pnt);
219 	if (!pnt)
220 		goto error;
221 	isl_space_free(pnt->dim);
222 	pnt->dim = space;
223 
224 	return pnt;
225 error:
226 	isl_point_free(pnt);
227 	isl_space_free(space);
228 	return NULL;
229 }
230 
231 /* Return the coordinate vector of "pnt".
232  */
isl_point_peek_vec(__isl_keep isl_point * pnt)233 __isl_keep isl_vec *isl_point_peek_vec(__isl_keep isl_point *pnt)
234 {
235 	return pnt ? pnt->vec : NULL;
236 }
237 
238 /* Return a copy of the coordinate vector of "pnt".
239  */
isl_point_get_vec(__isl_keep isl_point * pnt)240 __isl_give isl_vec *isl_point_get_vec(__isl_keep isl_point *pnt)
241 {
242 	return isl_vec_copy(isl_point_peek_vec(pnt));
243 }
244 
245 /* Return the coordinate vector of "pnt".
246  * This may be either a copy or the coordinate vector itself
247  * if there is only one reference to "pnt".
248  * This allows the coordinate vector to be modified inplace
249  * if both the point and its coordinate vector have only a single reference.
250  * The caller is not allowed to modify "pnt" between this call and
251  * a subsequent call to isl_point_restore_vec.
252  * The only exception is that isl_point_free can be called instead.
253  */
isl_point_take_vec(__isl_keep isl_point * pnt)254 __isl_give isl_vec *isl_point_take_vec(__isl_keep isl_point *pnt)
255 {
256 	isl_vec *vec;
257 
258 	if (!pnt)
259 		return NULL;
260 	if (pnt->ref != 1)
261 		return isl_point_get_vec(pnt);
262 	vec = pnt->vec;
263 	pnt->vec = NULL;
264 	return vec;
265 }
266 
267 /* Set the coordinate vector of "pnt" to "vec",
268  * where the coordinate vector of "pnt" may be missing
269  * due to a preceding call to isl_point_take_vec.
270  * However, in this case, "pnt" only has a single reference and
271  * then the call to isl_point_cow has no effect.
272  */
isl_point_restore_vec(__isl_take isl_point * pnt,__isl_take isl_vec * vec)273 __isl_give isl_point *isl_point_restore_vec(__isl_take isl_point *pnt,
274 	__isl_take isl_vec *vec)
275 {
276 	if (!pnt || !vec)
277 		goto error;
278 
279 	if (pnt->vec == vec) {
280 		isl_vec_free(vec);
281 		return pnt;
282 	}
283 
284 	pnt = isl_point_cow(pnt);
285 	if (!pnt)
286 		goto error;
287 	isl_vec_free(pnt->vec);
288 	pnt->vec = vec;
289 
290 	return pnt;
291 error:
292 	isl_point_free(pnt);
293 	isl_vec_free(vec);
294 	return NULL;
295 }
296 
297 /* Return the number of variables of the given type.
298  */
isl_point_dim(__isl_keep isl_point * pnt,enum isl_dim_type type)299 static isl_size isl_point_dim(__isl_keep isl_point *pnt, enum isl_dim_type type)
300 {
301 	return isl_space_dim(isl_point_peek_space(pnt), type);
302 }
303 
304 /* Return the position of the coordinates of the given type
305  * within the sequence of coordinates of "pnt".
306  */
isl_point_var_offset(__isl_keep isl_point * pnt,enum isl_dim_type type)307 static isl_size isl_point_var_offset(__isl_keep isl_point *pnt,
308 	enum isl_dim_type type)
309 {
310 	return pnt ? isl_space_offset(pnt->dim, type) : isl_size_error;
311 }
312 
313 /* Reorder the coordinates of "pnt" based on the given reordering.
314  */
isl_point_reorder(__isl_take isl_point * pnt,__isl_take isl_reordering * r)315 static __isl_give isl_point *isl_point_reorder(__isl_take isl_point *pnt,
316 	__isl_take isl_reordering *r)
317 {
318 	isl_vec *vec;
319 
320 	isl_space_free(isl_point_take_space(pnt));
321 	pnt = isl_point_restore_space(pnt, isl_reordering_get_space(r));
322 
323 	vec = isl_point_take_vec(pnt);
324 	vec = isl_vec_reorder(vec, 1, isl_reordering_copy(r));
325 	pnt = isl_point_restore_vec(pnt, vec);
326 
327 	return pnt;
328 }
329 
330 /* Align the parameters of "pnt" along those of "model".
331  *
332  * Note that "model" is not allowed to have any parameters
333  * that do not already appear in "pnt" since "pnt" does not specify
334  * any value for such parameters.
335  */
isl_point_align_params(__isl_take isl_point * pnt,__isl_take isl_space * model)336 __isl_give isl_point *isl_point_align_params(__isl_take isl_point *pnt,
337 	__isl_take isl_space *model)
338 {
339 	isl_space *space;
340 	isl_bool equal_params;
341 
342 	space = isl_point_peek_space(pnt);
343 	equal_params = isl_space_has_equal_params(space, model);
344 	if (equal_params < 0)
345 		goto error;
346 	if (!equal_params) {
347 		isl_reordering *r;
348 
349 		r = isl_parameter_alignment_reordering(space, model);
350 		if (!r)
351 			goto error;
352 		if (r->src_len != r->dst_len)
353 			isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
354 				"no value specified for some parameters",
355 				r = isl_reordering_free(r));
356 		pnt = isl_point_reorder(pnt, r);
357 	}
358 
359 	isl_space_free(model);
360 	return pnt;
361 error:
362 	isl_space_free(model);
363 	isl_point_free(pnt);
364 	return NULL;
365 }
366 
367 #undef TYPE
368 #define TYPE	isl_point
369 static
370 #include "check_type_range_templ.c"
371 
372 /* Return the value of coordinate "pos" of type "type" of "pnt".
373  */
isl_point_get_coordinate_val(__isl_keep isl_point * pnt,enum isl_dim_type type,int pos)374 __isl_give isl_val *isl_point_get_coordinate_val(__isl_keep isl_point *pnt,
375 	enum isl_dim_type type, int pos)
376 {
377 	isl_ctx *ctx;
378 	isl_val *v;
379 	isl_size off;
380 
381 	if (!pnt)
382 		return NULL;
383 
384 	ctx = isl_point_get_ctx(pnt);
385 	if (isl_point_is_void(pnt))
386 		isl_die(ctx, isl_error_invalid,
387 			"void point does not have coordinates", return NULL);
388 	if (isl_point_check_range(pnt, type, pos, 1) < 0)
389 		return NULL;
390 
391 	off = isl_point_var_offset(pnt, type);
392 	if (off < 0)
393 		return NULL;
394 	pos += off;
395 
396 	v = isl_val_rat_from_isl_int(ctx, pnt->vec->el[1 + pos],
397 						pnt->vec->el[0]);
398 	return isl_val_normalize(v);
399 }
400 
401 /* Set all entries of "mv" to NaN.
402  */
set_nan(__isl_take isl_multi_val * mv)403 static __isl_give isl_multi_val *set_nan(__isl_take isl_multi_val *mv)
404 {
405 	int i;
406 	isl_size n;
407 	isl_val *v;
408 
409 	n = isl_multi_val_size(mv);
410 	if (n < 0)
411 		return isl_multi_val_free(mv);
412 	v = isl_val_nan(isl_multi_val_get_ctx(mv));
413 	for (i = 0; i < n; ++i)
414 		mv = isl_multi_val_set_at(mv, i, isl_val_copy(v));
415 	isl_val_free(v);
416 
417 	return mv;
418 }
419 
420 /* Return the values of the set dimensions of "pnt".
421  * Return a sequence of NaNs in case of a void point.
422  */
isl_point_get_multi_val(__isl_keep isl_point * pnt)423 __isl_give isl_multi_val *isl_point_get_multi_val(__isl_keep isl_point *pnt)
424 {
425 	int i;
426 	isl_bool is_void;
427 	isl_size n;
428 	isl_multi_val *mv;
429 
430 	is_void = isl_point_is_void(pnt);
431 	if (is_void < 0)
432 		return NULL;
433 
434 	mv = isl_multi_val_alloc(isl_point_get_space(pnt));
435 	if (is_void)
436 		return set_nan(mv);
437 	n = isl_multi_val_size(mv);
438 	if (n < 0)
439 		return isl_multi_val_free(mv);
440 	for (i = 0; i < n; ++i) {
441 		isl_val *v;
442 
443 		v = isl_point_get_coordinate_val(pnt, isl_dim_set, i);
444 		mv = isl_multi_val_set_at(mv, i, v);
445 	}
446 
447 	return mv;
448 }
449 
450 /* Replace coordinate "pos" of type "type" of "pnt" by "v".
451  */
isl_point_set_coordinate_val(__isl_take isl_point * pnt,enum isl_dim_type type,int pos,__isl_take isl_val * v)452 __isl_give isl_point *isl_point_set_coordinate_val(__isl_take isl_point *pnt,
453 	enum isl_dim_type type, int pos, __isl_take isl_val *v)
454 {
455 	isl_size off;
456 
457 	off = isl_space_offset(isl_point_peek_space(pnt), type);
458 	if (off < 0 || !v)
459 		goto error;
460 	if (isl_point_is_void(pnt))
461 		isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
462 			"void point does not have coordinates", goto error);
463 	if (isl_point_check_range(pnt, type, pos, 1) < 0)
464 		goto error;
465 	if (!isl_val_is_rat(v))
466 		isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
467 			"expecting rational value", goto error);
468 
469 	pos += off;
470 	if (isl_int_eq(pnt->vec->el[1 + pos], v->n) &&
471 	    isl_int_eq(pnt->vec->el[0], v->d)) {
472 		isl_val_free(v);
473 		return pnt;
474 	}
475 
476 	pnt = isl_point_cow(pnt);
477 	if (!pnt)
478 		goto error;
479 	pnt->vec = isl_vec_cow(pnt->vec);
480 	if (!pnt->vec)
481 		goto error;
482 
483 	if (isl_int_eq(pnt->vec->el[0], v->d)) {
484 		isl_int_set(pnt->vec->el[1 + pos], v->n);
485 	} else if (isl_int_is_one(v->d)) {
486 		isl_int_mul(pnt->vec->el[1 + pos], pnt->vec->el[0], v->n);
487 	} else {
488 		isl_seq_scale(pnt->vec->el + 1,
489 				pnt->vec->el + 1, v->d, pnt->vec->size - 1);
490 		isl_int_mul(pnt->vec->el[1 + pos], pnt->vec->el[0], v->n);
491 		isl_int_mul(pnt->vec->el[0], pnt->vec->el[0], v->d);
492 		pnt->vec = isl_vec_normalize(pnt->vec);
493 		if (!pnt->vec)
494 			goto error;
495 	}
496 
497 	isl_val_free(v);
498 	return pnt;
499 error:
500 	isl_val_free(v);
501 	isl_point_free(pnt);
502 	return NULL;
503 }
504 
isl_point_add_ui(__isl_take isl_point * pnt,enum isl_dim_type type,int pos,unsigned val)505 __isl_give isl_point *isl_point_add_ui(__isl_take isl_point *pnt,
506 	enum isl_dim_type type, int pos, unsigned val)
507 {
508 	isl_size off;
509 
510 	if (!pnt || isl_point_is_void(pnt))
511 		return pnt;
512 
513 	pnt = isl_point_cow(pnt);
514 	if (!pnt)
515 		return NULL;
516 	pnt->vec = isl_vec_cow(pnt->vec);
517 	if (!pnt->vec)
518 		goto error;
519 
520 	off = isl_point_var_offset(pnt, type);
521 	if (off < 0)
522 		goto error;
523 	pos += off;
524 
525 	isl_int_add_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
526 
527 	return pnt;
528 error:
529 	isl_point_free(pnt);
530 	return NULL;
531 }
532 
isl_point_sub_ui(__isl_take isl_point * pnt,enum isl_dim_type type,int pos,unsigned val)533 __isl_give isl_point *isl_point_sub_ui(__isl_take isl_point *pnt,
534 	enum isl_dim_type type, int pos, unsigned val)
535 {
536 	isl_size off;
537 
538 	if (!pnt || isl_point_is_void(pnt))
539 		return pnt;
540 
541 	pnt = isl_point_cow(pnt);
542 	if (!pnt)
543 		return NULL;
544 	pnt->vec = isl_vec_cow(pnt->vec);
545 	if (!pnt->vec)
546 		goto error;
547 
548 	off = isl_point_var_offset(pnt, type);
549 	if (off < 0)
550 		goto error;
551 	pos += off;
552 
553 	isl_int_sub_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
554 
555 	return pnt;
556 error:
557 	isl_point_free(pnt);
558 	return NULL;
559 }
560 
561 struct isl_foreach_point {
562 	struct isl_scan_callback callback;
563 	isl_stat (*fn)(__isl_take isl_point *pnt, void *user);
564 	void *user;
565 	isl_space *dim;
566 };
567 
foreach_point(struct isl_scan_callback * cb,__isl_take isl_vec * sample)568 static isl_stat foreach_point(struct isl_scan_callback *cb,
569 	__isl_take isl_vec *sample)
570 {
571 	struct isl_foreach_point *fp = (struct isl_foreach_point *)cb;
572 	isl_point *pnt;
573 
574 	pnt = isl_point_alloc(isl_space_copy(fp->dim), sample);
575 
576 	return fp->fn(pnt, fp->user);
577 }
578 
isl_set_foreach_point(__isl_keep isl_set * set,isl_stat (* fn)(__isl_take isl_point * pnt,void * user),void * user)579 isl_stat isl_set_foreach_point(__isl_keep isl_set *set,
580 	isl_stat (*fn)(__isl_take isl_point *pnt, void *user), void *user)
581 {
582 	struct isl_foreach_point fp = { { &foreach_point }, fn, user };
583 	int i;
584 
585 	if (!set)
586 		return isl_stat_error;
587 
588 	fp.dim = isl_set_get_space(set);
589 	if (!fp.dim)
590 		return isl_stat_error;
591 
592 	set = isl_set_copy(set);
593 	set = isl_set_cow(set);
594 	set = isl_set_make_disjoint(set);
595 	set = isl_set_compute_divs(set);
596 	if (!set)
597 		goto error;
598 
599 	for (i = 0; i < set->n; ++i)
600 		if (isl_basic_set_scan(isl_basic_set_copy(set->p[i]),
601 					&fp.callback) < 0)
602 			goto error;
603 
604 	isl_set_free(set);
605 	isl_space_free(fp.dim);
606 
607 	return isl_stat_ok;
608 error:
609 	isl_set_free(set);
610 	isl_space_free(fp.dim);
611 	return isl_stat_error;
612 }
613 
614 /* Return 1 if "bmap" contains the point "point".
615  * "bmap" is assumed to have known divs.
616  * The point is first extended with the divs and then passed
617  * to basic_map_contains.
618  */
isl_basic_map_contains_point(__isl_keep isl_basic_map * bmap,__isl_keep isl_point * point)619 isl_bool isl_basic_map_contains_point(__isl_keep isl_basic_map *bmap,
620 	__isl_keep isl_point *point)
621 {
622 	isl_local *local;
623 	isl_vec *vec;
624 	isl_bool contains;
625 
626 	if (isl_basic_map_point_check_equal_space(bmap, point) < 0)
627 		return isl_bool_error;
628 	if (bmap->n_div == 0)
629 		return isl_basic_map_contains(bmap, point->vec);
630 
631 	local = isl_local_alloc_from_mat(isl_basic_map_get_divs(bmap));
632 	vec = isl_point_get_vec(point);
633 	vec = isl_local_extend_point_vec(local, vec);
634 	isl_local_free(local);
635 
636 	contains = isl_basic_map_contains(bmap, vec);
637 
638 	isl_vec_free(vec);
639 	return contains;
640 }
641 
isl_map_contains_point(__isl_keep isl_map * map,__isl_keep isl_point * point)642 isl_bool isl_map_contains_point(__isl_keep isl_map *map,
643 	__isl_keep isl_point *point)
644 {
645 	int i;
646 	isl_bool found = isl_bool_false;
647 
648 	if (!map || !point)
649 		return isl_bool_error;
650 
651 	map = isl_map_copy(map);
652 	map = isl_map_compute_divs(map);
653 	if (!map)
654 		return isl_bool_error;
655 
656 	for (i = 0; i < map->n; ++i) {
657 		found = isl_basic_map_contains_point(map->p[i], point);
658 		if (found < 0)
659 			goto error;
660 		if (found)
661 			break;
662 	}
663 	isl_map_free(map);
664 
665 	return found;
666 error:
667 	isl_map_free(map);
668 	return isl_bool_error;
669 }
670 
isl_set_contains_point(__isl_keep isl_set * set,__isl_keep isl_point * point)671 isl_bool isl_set_contains_point(__isl_keep isl_set *set,
672 	__isl_keep isl_point *point)
673 {
674 	return isl_map_contains_point(set_to_map(set), point);
675 }
676 
isl_basic_set_from_point(__isl_take isl_point * pnt)677 __isl_give isl_basic_set *isl_basic_set_from_point(__isl_take isl_point *pnt)
678 {
679 	isl_basic_set *bset;
680 	isl_basic_set *model;
681 
682 	if (!pnt)
683 		return NULL;
684 
685 	model = isl_basic_set_empty(isl_space_copy(pnt->dim));
686 	bset = isl_basic_set_from_vec(isl_vec_copy(pnt->vec));
687 	bset = isl_basic_set_from_underlying_set(bset, model);
688 	isl_point_free(pnt);
689 
690 	return bset;
691 }
692 
isl_set_from_point(__isl_take isl_point * pnt)693 __isl_give isl_set *isl_set_from_point(__isl_take isl_point *pnt)
694 {
695 	isl_basic_set *bset;
696 	bset = isl_basic_set_from_point(pnt);
697 	return isl_set_from_basic_set(bset);
698 }
699 
700 /* This function performs the same operation as isl_set_from_point,
701  * but is considered as a function on an isl_point when exported.
702  */
isl_point_to_set(__isl_take isl_point * pnt)703 __isl_give isl_set *isl_point_to_set(__isl_take isl_point *pnt)
704 {
705 	return isl_set_from_point(pnt);
706 }
707 
708 /* Construct a union set, containing the single element "pnt".
709  * If "pnt" is void, then return an empty union set.
710  */
isl_union_set_from_point(__isl_take isl_point * pnt)711 __isl_give isl_union_set *isl_union_set_from_point(__isl_take isl_point *pnt)
712 {
713 	if (!pnt)
714 		return NULL;
715 	if (isl_point_is_void(pnt)) {
716 		isl_space *space;
717 
718 		space = isl_point_get_space(pnt);
719 		isl_point_free(pnt);
720 		return isl_union_set_empty(space);
721 	}
722 
723 	return isl_union_set_from_set(isl_set_from_point(pnt));
724 }
725 
isl_basic_set_box_from_points(__isl_take isl_point * pnt1,__isl_take isl_point * pnt2)726 __isl_give isl_basic_set *isl_basic_set_box_from_points(
727 	__isl_take isl_point *pnt1, __isl_take isl_point *pnt2)
728 {
729 	isl_basic_set *bset = NULL;
730 	isl_size total;
731 	int i;
732 	int k;
733 	isl_int t;
734 
735 	isl_int_init(t);
736 
737 	if (!pnt1 || !pnt2)
738 		goto error;
739 
740 	isl_assert(pnt1->dim->ctx,
741 			isl_space_is_equal(pnt1->dim, pnt2->dim), goto error);
742 
743 	if (isl_point_is_void(pnt1) && isl_point_is_void(pnt2)) {
744 		isl_space *space = isl_space_copy(pnt1->dim);
745 		isl_point_free(pnt1);
746 		isl_point_free(pnt2);
747 		isl_int_clear(t);
748 		return isl_basic_set_empty(space);
749 	}
750 	if (isl_point_is_void(pnt1)) {
751 		isl_point_free(pnt1);
752 		isl_int_clear(t);
753 		return isl_basic_set_from_point(pnt2);
754 	}
755 	if (isl_point_is_void(pnt2)) {
756 		isl_point_free(pnt2);
757 		isl_int_clear(t);
758 		return isl_basic_set_from_point(pnt1);
759 	}
760 
761 	total = isl_point_dim(pnt1, isl_dim_all);
762 	if (total < 0)
763 		goto error;
764 	bset = isl_basic_set_alloc_space(isl_space_copy(pnt1->dim), 0, 0, 2 * total);
765 
766 	for (i = 0; i < total; ++i) {
767 		isl_int_mul(t, pnt1->vec->el[1 + i], pnt2->vec->el[0]);
768 		isl_int_submul(t, pnt2->vec->el[1 + i], pnt1->vec->el[0]);
769 
770 		k = isl_basic_set_alloc_inequality(bset);
771 		if (k < 0)
772 			goto error;
773 		isl_seq_clr(bset->ineq[k] + 1, total);
774 		if (isl_int_is_pos(t)) {
775 			isl_int_set_si(bset->ineq[k][1 + i], -1);
776 			isl_int_set(bset->ineq[k][0], pnt1->vec->el[1 + i]);
777 		} else {
778 			isl_int_set_si(bset->ineq[k][1 + i], 1);
779 			isl_int_neg(bset->ineq[k][0], pnt1->vec->el[1 + i]);
780 		}
781 		isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt1->vec->el[0]);
782 
783 		k = isl_basic_set_alloc_inequality(bset);
784 		if (k < 0)
785 			goto error;
786 		isl_seq_clr(bset->ineq[k] + 1, total);
787 		if (isl_int_is_pos(t)) {
788 			isl_int_set_si(bset->ineq[k][1 + i], 1);
789 			isl_int_neg(bset->ineq[k][0], pnt2->vec->el[1 + i]);
790 		} else {
791 			isl_int_set_si(bset->ineq[k][1 + i], -1);
792 			isl_int_set(bset->ineq[k][0], pnt2->vec->el[1 + i]);
793 		}
794 		isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt2->vec->el[0]);
795 	}
796 
797 	bset = isl_basic_set_finalize(bset);
798 
799 	isl_point_free(pnt1);
800 	isl_point_free(pnt2);
801 
802 	isl_int_clear(t);
803 
804 	return bset;
805 error:
806 	isl_point_free(pnt1);
807 	isl_point_free(pnt2);
808 	isl_int_clear(t);
809 	isl_basic_set_free(bset);
810 	return NULL;
811 }
812 
isl_set_box_from_points(__isl_take isl_point * pnt1,__isl_take isl_point * pnt2)813 __isl_give isl_set *isl_set_box_from_points(__isl_take isl_point *pnt1,
814 	__isl_take isl_point *pnt2)
815 {
816 	isl_basic_set *bset;
817 	bset = isl_basic_set_box_from_points(pnt1, pnt2);
818 	return isl_set_from_basic_set(bset);
819 }
820 
821 /* Print the coordinate at position "pos" of the point "pnt".
822  */
print_coordinate(__isl_take isl_printer * p,struct isl_print_space_data * data,unsigned pos)823 static __isl_give isl_printer *print_coordinate(__isl_take isl_printer *p,
824 	struct isl_print_space_data *data, unsigned pos)
825 {
826 	isl_point *pnt = data->user;
827 	isl_size off;
828 
829 	off = isl_space_offset(data->space, data->type);
830 	if (off < 0)
831 		return isl_printer_free(p);
832 	pos += off;
833 	p = isl_printer_print_isl_int(p, pnt->vec->el[1 + pos]);
834 	if (!isl_int_is_one(pnt->vec->el[0])) {
835 		p = isl_printer_print_str(p, "/");
836 		p = isl_printer_print_isl_int(p, pnt->vec->el[0]);
837 	}
838 
839 	return p;
840 }
841 
isl_printer_print_point(__isl_take isl_printer * p,__isl_keep isl_point * pnt)842 __isl_give isl_printer *isl_printer_print_point(
843 	__isl_take isl_printer *p, __isl_keep isl_point *pnt)
844 {
845 	struct isl_print_space_data data = { 0 };
846 	int i;
847 	isl_size nparam;
848 
849 	if (!pnt)
850 		return p;
851 	if (isl_point_is_void(pnt)) {
852 		p = isl_printer_print_str(p, "void");
853 		return p;
854 	}
855 
856 	nparam = isl_point_dim(pnt, isl_dim_param);
857 	if (nparam < 0)
858 		return isl_printer_free(p);
859 	if (nparam > 0) {
860 		p = isl_printer_print_str(p, "[");
861 		for (i = 0; i < nparam; ++i) {
862 			const char *name;
863 			if (i)
864 				p = isl_printer_print_str(p, ", ");
865 			name = isl_space_get_dim_name(pnt->dim, isl_dim_param, i);
866 			if (name) {
867 				p = isl_printer_print_str(p, name);
868 				p = isl_printer_print_str(p, " = ");
869 			}
870 			p = isl_printer_print_isl_int(p, pnt->vec->el[1 + i]);
871 			if (!isl_int_is_one(pnt->vec->el[0])) {
872 				p = isl_printer_print_str(p, "/");
873 				p = isl_printer_print_isl_int(p, pnt->vec->el[0]);
874 			}
875 		}
876 		p = isl_printer_print_str(p, "]");
877 		p = isl_printer_print_str(p, " -> ");
878 	}
879 	data.print_dim = &print_coordinate;
880 	data.user = pnt;
881 	p = isl_printer_print_str(p, "{ ");
882 	p = isl_print_space(pnt->dim, p, 0, &data);
883 	p = isl_printer_print_str(p, " }");
884 	return p;
885 }
886