← Back to branch summary

~mmach/netext73/isl

« back to all changes in this revision

Viewing changes to isl_point.c

  • Committer: NetBit73
  • Date: 2018-06-06 06:57:54 UTC
  • Revision ID: netbit73@gmail.com-20180606065754-qw4x4wd2t39mx8wl
synchronizacja 1

Show diffs side-by-side

added added

removed removed

Lines of Context:
isl_point.c
 
1
#include <isl_map_private.h>
 
2
#include <isl_point_private.h>
 
3
#include <isl/set.h>
 
4
#include <isl/union_set.h>
 
5
#include <isl_sample.h>
 
6
#include <isl_scan.h>
 
7
#include <isl_seq.h>
 
8
#include <isl_space_private.h>
 
9
#include <isl_val_private.h>
 
10
#include <isl_vec_private.h>
 
11
#include <isl_output_private.h>
 
12
 
 
13
#include <set_to_map.c>
 
14
 
 
15
isl_ctx *isl_point_get_ctx(__isl_keep isl_point *pnt)
 
16
{
 
17
        return pnt ? isl_space_get_ctx(pnt->dim) : NULL;
 
18
}
 
19
 
 
20
__isl_give isl_space *isl_point_get_space(__isl_keep isl_point *pnt)
 
21
{
 
22
        return pnt ? isl_space_copy(pnt->dim) : NULL;
 
23
}
 
24
 
 
25
__isl_give isl_point *isl_point_alloc(__isl_take isl_space *dim,
 
26
        __isl_take isl_vec *vec)
 
27
{
 
28
        struct isl_point *pnt;
 
29
 
 
30
        if (!dim || !vec)
 
31
                goto error;
 
32
 
 
33
        if (vec->size > 1 + isl_space_dim(dim, isl_dim_all)) {
 
34
                vec = isl_vec_cow(vec);
 
35
                if (!vec)
 
36
                        goto error;
 
37
                vec->size = 1 + isl_space_dim(dim, isl_dim_all);
 
38
        }
 
39
 
 
40
        pnt = isl_alloc_type(dim->ctx, struct isl_point);
 
41
        if (!pnt)
 
42
                goto error;
 
43
 
 
44
        pnt->ref = 1;
 
45
        pnt->dim = dim;
 
46
        pnt->vec = vec;
 
47
 
 
48
        return pnt;
 
49
error:
 
50
        isl_space_free(dim);
 
51
        isl_vec_free(vec);
 
52
        return NULL;
 
53
}
 
54
 
 
55
__isl_give isl_point *isl_point_zero(__isl_take isl_space *dim)
 
56
{
 
57
        isl_vec *vec;
 
58
 
 
59
        if (!dim)
 
60
                return NULL;
 
61
        vec = isl_vec_alloc(dim->ctx, 1 + isl_space_dim(dim, isl_dim_all));
 
62
        if (!vec)
 
63
                goto error;
 
64
        isl_int_set_si(vec->el[0], 1);
 
65
        isl_seq_clr(vec->el + 1, vec->size - 1);
 
66
        return isl_point_alloc(dim, vec);
 
67
error:
 
68
        isl_space_free(dim);
 
69
        return NULL;
 
70
}
 
71
 
 
72
__isl_give isl_point *isl_point_dup(__isl_keep isl_point *pnt)
 
73
{
 
74
        struct isl_point *pnt2;
 
75
 
 
76
        if (!pnt)
 
77
                return NULL;
 
78
        pnt2 = isl_point_alloc(isl_space_copy(pnt->dim), isl_vec_copy(pnt->vec));
 
79
        return pnt2;
 
80
}
 
81
 
 
82
__isl_give isl_point *isl_point_cow(__isl_take isl_point *pnt)
 
83
{
 
84
        struct isl_point *pnt2;
 
85
        if (!pnt)
 
86
                return NULL;
 
87
 
 
88
        if (pnt->ref == 1)
 
89
                return pnt;
 
90
 
 
91
        pnt2 = isl_point_dup(pnt);
 
92
        isl_point_free(pnt);
 
93
        return pnt2;
 
94
}
 
95
 
 
96
__isl_give isl_point *isl_point_copy(__isl_keep isl_point *pnt)
 
97
{
 
98
        if (!pnt)
 
99
                return NULL;
 
100
 
 
101
        pnt->ref++;
 
102
        return pnt;
 
103
}
 
104
 
 
105
__isl_null isl_point *isl_point_free(__isl_take isl_point *pnt)
 
106
{
 
107
        if (!pnt)
 
108
                return NULL;
 
109
 
 
110
        if (--pnt->ref > 0)
 
111
                return NULL;
 
112
 
 
113
        isl_space_free(pnt->dim);
 
114
        isl_vec_free(pnt->vec);
 
115
        free(pnt);
 
116
        return NULL;
 
117
}
 
118
 
 
119
__isl_give isl_point *isl_point_void(__isl_take isl_space *dim)
 
120
{
 
121
        if (!dim)
 
122
                return NULL;
 
123
 
 
124
        return isl_point_alloc(dim, isl_vec_alloc(dim->ctx, 0));
 
125
}
 
126
 
 
127
isl_bool isl_point_is_void(__isl_keep isl_point *pnt)
 
128
{
 
129
        if (!pnt)
 
130
                return isl_bool_error;
 
131
 
 
132
        return pnt->vec->size == 0;
 
133
}
 
134
 
 
135
/* Return the value of coordinate "pos" of type "type" of "pnt".
 
136
 */
 
137
__isl_give isl_val *isl_point_get_coordinate_val(__isl_keep isl_point *pnt,
 
138
        enum isl_dim_type type, int pos)
 
139
{
 
140
        isl_ctx *ctx;
 
141
        isl_val *v;
 
142
 
 
143
        if (!pnt)
 
144
                return NULL;
 
145
 
 
146
        ctx = isl_point_get_ctx(pnt);
 
147
        if (isl_point_is_void(pnt))
 
148
                isl_die(ctx, isl_error_invalid,
 
149
                        "void point does not have coordinates", return NULL);
 
150
        if (pos < 0 || pos >= isl_space_dim(pnt->dim, type))
 
151
                isl_die(ctx, isl_error_invalid,
 
152
                        "position out of bounds", return NULL);
 
153
 
 
154
        if (type == isl_dim_set)
 
155
                pos += isl_space_dim(pnt->dim, isl_dim_param);
 
156
 
 
157
        v = isl_val_rat_from_isl_int(ctx, pnt->vec->el[1 + pos],
 
158
                                                pnt->vec->el[0]);
 
159
        return isl_val_normalize(v);
 
160
}
 
161
 
 
162
/* Replace coordinate "pos" of type "type" of "pnt" by "v".
 
163
 */
 
164
__isl_give isl_point *isl_point_set_coordinate_val(__isl_take isl_point *pnt,
 
165
        enum isl_dim_type type, int pos, __isl_take isl_val *v)
 
166
{
 
167
        if (!pnt || !v)
 
168
                goto error;
 
169
        if (isl_point_is_void(pnt))
 
170
                isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
 
171
                        "void point does not have coordinates", goto error);
 
172
        if (pos < 0 || pos >= isl_space_dim(pnt->dim, type))
 
173
                isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
 
174
                        "position out of bounds", goto error);
 
175
        if (!isl_val_is_rat(v))
 
176
                isl_die(isl_point_get_ctx(pnt), isl_error_invalid,
 
177
                        "expecting rational value", goto error);
 
178
 
 
179
        if (isl_int_eq(pnt->vec->el[1 + pos], v->n) &&
 
180
            isl_int_eq(pnt->vec->el[0], v->d)) {
 
181
                isl_val_free(v);
 
182
                return pnt;
 
183
        }
 
184
 
 
185
        pnt = isl_point_cow(pnt);
 
186
        if (!pnt)
 
187
                goto error;
 
188
        pnt->vec = isl_vec_cow(pnt->vec);
 
189
        if (!pnt->vec)
 
190
                goto error;
 
191
 
 
192
        if (isl_int_eq(pnt->vec->el[0], v->d)) {
 
193
                isl_int_set(pnt->vec->el[1 + pos], v->n);
 
194
        } else if (isl_int_is_one(v->d)) {
 
195
                isl_int_mul(pnt->vec->el[1 + pos], pnt->vec->el[0], v->n);
 
196
        } else {
 
197
                isl_seq_scale(pnt->vec->el + 1,
 
198
                                pnt->vec->el + 1, v->d, pnt->vec->size - 1);
 
199
                isl_int_mul(pnt->vec->el[1 + pos], pnt->vec->el[0], v->n);
 
200
                isl_int_mul(pnt->vec->el[0], pnt->vec->el[0], v->d);
 
201
                pnt->vec = isl_vec_normalize(pnt->vec);
 
202
                if (!pnt->vec)
 
203
                        goto error;
 
204
        }
 
205
 
 
206
        isl_val_free(v);
 
207
        return pnt;
 
208
error:
 
209
        isl_val_free(v);
 
210
        isl_point_free(pnt);
 
211
        return NULL;
 
212
}
 
213
 
 
214
__isl_give isl_point *isl_point_add_ui(__isl_take isl_point *pnt,
 
215
        enum isl_dim_type type, int pos, unsigned val)
 
216
{
 
217
        if (!pnt || isl_point_is_void(pnt))
 
218
                return pnt;
 
219
 
 
220
        pnt = isl_point_cow(pnt);
 
221
        if (!pnt)
 
222
                return NULL;
 
223
        pnt->vec = isl_vec_cow(pnt->vec);
 
224
        if (!pnt->vec)
 
225
                goto error;
 
226
 
 
227
        if (type == isl_dim_set)
 
228
                pos += isl_space_dim(pnt->dim, isl_dim_param);
 
229
 
 
230
        isl_int_add_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
 
231
 
 
232
        return pnt;
 
233
error:
 
234
        isl_point_free(pnt);
 
235
        return NULL;
 
236
}
 
237
 
 
238
__isl_give isl_point *isl_point_sub_ui(__isl_take isl_point *pnt,
 
239
        enum isl_dim_type type, int pos, unsigned val)
 
240
{
 
241
        if (!pnt || isl_point_is_void(pnt))
 
242
                return pnt;
 
243
 
 
244
        pnt = isl_point_cow(pnt);
 
245
        if (!pnt)
 
246
                return NULL;
 
247
        pnt->vec = isl_vec_cow(pnt->vec);
 
248
        if (!pnt->vec)
 
249
                goto error;
 
250
 
 
251
        if (type == isl_dim_set)
 
252
                pos += isl_space_dim(pnt->dim, isl_dim_param);
 
253
 
 
254
        isl_int_sub_ui(pnt->vec->el[1 + pos], pnt->vec->el[1 + pos], val);
 
255
 
 
256
        return pnt;
 
257
error:
 
258
        isl_point_free(pnt);
 
259
        return NULL;
 
260
}
 
261
 
 
262
struct isl_foreach_point {
 
263
        struct isl_scan_callback callback;
 
264
        isl_stat (*fn)(__isl_take isl_point *pnt, void *user);
 
265
        void *user;
 
266
        isl_space *dim;
 
267
};
 
268
 
 
269
static isl_stat foreach_point(struct isl_scan_callback *cb,
 
270
        __isl_take isl_vec *sample)
 
271
{
 
272
        struct isl_foreach_point *fp = (struct isl_foreach_point *)cb;
 
273
        isl_point *pnt;
 
274
 
 
275
        pnt = isl_point_alloc(isl_space_copy(fp->dim), sample);
 
276
 
 
277
        return fp->fn(pnt, fp->user);
 
278
}
 
279
 
 
280
isl_stat isl_set_foreach_point(__isl_keep isl_set *set,
 
281
        isl_stat (*fn)(__isl_take isl_point *pnt, void *user), void *user)
 
282
{
 
283
        struct isl_foreach_point fp = { { &foreach_point }, fn, user };
 
284
        int i;
 
285
 
 
286
        if (!set)
 
287
                return isl_stat_error;
 
288
 
 
289
        fp.dim = isl_set_get_space(set);
 
290
        if (!fp.dim)
 
291
                return isl_stat_error;
 
292
 
 
293
        set = isl_set_copy(set);
 
294
        set = isl_set_cow(set);
 
295
        set = isl_set_make_disjoint(set);
 
296
        set = isl_set_compute_divs(set);
 
297
        if (!set)
 
298
                goto error;
 
299
 
 
300
        for (i = 0; i < set->n; ++i)
 
301
                if (isl_basic_set_scan(isl_basic_set_copy(set->p[i]),
 
302
                                        &fp.callback) < 0)
 
303
                        goto error;
 
304
 
 
305
        isl_set_free(set);
 
306
        isl_space_free(fp.dim);
 
307
 
 
308
        return isl_stat_ok;
 
309
error:
 
310
        isl_set_free(set);
 
311
        isl_space_free(fp.dim);
 
312
        return isl_stat_error;
 
313
}
 
314
 
 
315
/* Return 1 if "bmap" contains the point "point".
 
316
 * "bmap" is assumed to have known divs.
 
317
 * The point is first extended with the divs and then passed
 
318
 * to basic_map_contains.
 
319
 */
 
320
isl_bool isl_basic_map_contains_point(__isl_keep isl_basic_map *bmap,
 
321
        __isl_keep isl_point *point)
 
322
{
 
323
        int i;
 
324
        struct isl_vec *vec;
 
325
        unsigned dim;
 
326
        isl_bool contains;
 
327
 
 
328
        if (!bmap || !point)
 
329
                return isl_bool_error;
 
330
        isl_assert(bmap->ctx, isl_space_is_equal(bmap->dim, point->dim),
 
331
                return isl_bool_error);
 
332
        if (bmap->n_div == 0)
 
333
                return isl_basic_map_contains(bmap, point->vec);
 
334
 
 
335
        dim = isl_basic_map_total_dim(bmap) - bmap->n_div;
 
336
        vec = isl_vec_alloc(bmap->ctx, 1 + dim + bmap->n_div);
 
337
        if (!vec)
 
338
                return isl_bool_error;
 
339
 
 
340
        isl_seq_cpy(vec->el, point->vec->el, point->vec->size);
 
341
        for (i = 0; i < bmap->n_div; ++i) {
 
342
                isl_seq_inner_product(bmap->div[i] + 1, vec->el,
 
343
                                        1 + dim + i, &vec->el[1+dim+i]);
 
344
                isl_int_fdiv_q(vec->el[1+dim+i], vec->el[1+dim+i],
 
345
                                bmap->div[i][0]);
 
346
        }
 
347
 
 
348
        contains = isl_basic_map_contains(bmap, vec);
 
349
 
 
350
        isl_vec_free(vec);
 
351
        return contains;
 
352
}
 
353
 
 
354
isl_bool isl_map_contains_point(__isl_keep isl_map *map,
 
355
        __isl_keep isl_point *point)
 
356
{
 
357
        int i;
 
358
        isl_bool found = isl_bool_false;
 
359
 
 
360
        if (!map || !point)
 
361
                return isl_bool_error;
 
362
 
 
363
        map = isl_map_copy(map);
 
364
        map = isl_map_compute_divs(map);
 
365
        if (!map)
 
366
                return isl_bool_error;
 
367
 
 
368
        for (i = 0; i < map->n; ++i) {
 
369
                found = isl_basic_map_contains_point(map->p[i], point);
 
370
                if (found < 0)
 
371
                        goto error;
 
372
                if (found)
 
373
                        break;
 
374
        }
 
375
        isl_map_free(map);
 
376
 
 
377
        return found;
 
378
error:
 
379
        isl_map_free(map);
 
380
        return isl_bool_error;
 
381
}
 
382
 
 
383
isl_bool isl_set_contains_point(__isl_keep isl_set *set,
 
384
        __isl_keep isl_point *point)
 
385
{
 
386
        return isl_map_contains_point(set_to_map(set), point);
 
387
}
 
388
 
 
389
__isl_give isl_basic_set *isl_basic_set_from_point(__isl_take isl_point *pnt)
 
390
{
 
391
        isl_basic_set *bset;
 
392
        isl_basic_set *model;
 
393
 
 
394
        if (!pnt)
 
395
                return NULL;
 
396
 
 
397
        model = isl_basic_set_empty(isl_space_copy(pnt->dim));
 
398
        bset = isl_basic_set_from_vec(isl_vec_copy(pnt->vec));
 
399
        bset = isl_basic_set_from_underlying_set(bset, model);
 
400
        isl_point_free(pnt);
 
401
 
 
402
        return bset;
 
403
}
 
404
 
 
405
__isl_give isl_set *isl_set_from_point(__isl_take isl_point *pnt)
 
406
{
 
407
        isl_basic_set *bset;
 
408
        bset = isl_basic_set_from_point(pnt);
 
409
        return isl_set_from_basic_set(bset);
 
410
}
 
411
 
 
412
/* Construct a union set, containing the single element "pnt".
 
413
 * If "pnt" is void, then return an empty union set.
 
414
 */
 
415
__isl_give isl_union_set *isl_union_set_from_point(__isl_take isl_point *pnt)
 
416
{
 
417
        if (!pnt)
 
418
                return NULL;
 
419
        if (isl_point_is_void(pnt)) {
 
420
                isl_space *space;
 
421
 
 
422
                space = isl_point_get_space(pnt);
 
423
                isl_point_free(pnt);
 
424
                return isl_union_set_empty(space);
 
425
        }
 
426
 
 
427
        return isl_union_set_from_set(isl_set_from_point(pnt));
 
428
}
 
429
 
 
430
__isl_give isl_basic_set *isl_basic_set_box_from_points(
 
431
        __isl_take isl_point *pnt1, __isl_take isl_point *pnt2)
 
432
{
 
433
        isl_basic_set *bset = NULL;
 
434
        unsigned total;
 
435
        int i;
 
436
        int k;
 
437
        isl_int t;
 
438
 
 
439
        isl_int_init(t);
 
440
 
 
441
        if (!pnt1 || !pnt2)
 
442
                goto error;
 
443
 
 
444
        isl_assert(pnt1->dim->ctx,
 
445
                        isl_space_is_equal(pnt1->dim, pnt2->dim), goto error);
 
446
 
 
447
        if (isl_point_is_void(pnt1) && isl_point_is_void(pnt2)) {
 
448
                isl_space *dim = isl_space_copy(pnt1->dim);
 
449
                isl_point_free(pnt1);
 
450
                isl_point_free(pnt2);
 
451
                isl_int_clear(t);
 
452
                return isl_basic_set_empty(dim);
 
453
        }
 
454
        if (isl_point_is_void(pnt1)) {
 
455
                isl_point_free(pnt1);
 
456
                isl_int_clear(t);
 
457
                return isl_basic_set_from_point(pnt2);
 
458
        }
 
459
        if (isl_point_is_void(pnt2)) {
 
460
                isl_point_free(pnt2);
 
461
                isl_int_clear(t);
 
462
                return isl_basic_set_from_point(pnt1);
 
463
        }
 
464
 
 
465
        total = isl_space_dim(pnt1->dim, isl_dim_all);
 
466
        bset = isl_basic_set_alloc_space(isl_space_copy(pnt1->dim), 0, 0, 2 * total);
 
467
 
 
468
        for (i = 0; i < total; ++i) {
 
469
                isl_int_mul(t, pnt1->vec->el[1 + i], pnt2->vec->el[0]);
 
470
                isl_int_submul(t, pnt2->vec->el[1 + i], pnt1->vec->el[0]);
 
471
 
 
472
                k = isl_basic_set_alloc_inequality(bset);
 
473
                if (k < 0)
 
474
                        goto error;
 
475
                isl_seq_clr(bset->ineq[k] + 1, total);
 
476
                if (isl_int_is_pos(t)) {
 
477
                        isl_int_set_si(bset->ineq[k][1 + i], -1);
 
478
                        isl_int_set(bset->ineq[k][0], pnt1->vec->el[1 + i]);
 
479
                } else {
 
480
                        isl_int_set_si(bset->ineq[k][1 + i], 1);
 
481
                        isl_int_neg(bset->ineq[k][0], pnt1->vec->el[1 + i]);
 
482
                }
 
483
                isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt1->vec->el[0]);
 
484
 
 
485
                k = isl_basic_set_alloc_inequality(bset);
 
486
                if (k < 0)
 
487
                        goto error;
 
488
                isl_seq_clr(bset->ineq[k] + 1, total);
 
489
                if (isl_int_is_pos(t)) {
 
490
                        isl_int_set_si(bset->ineq[k][1 + i], 1);
 
491
                        isl_int_neg(bset->ineq[k][0], pnt2->vec->el[1 + i]);
 
492
                } else {
 
493
                        isl_int_set_si(bset->ineq[k][1 + i], -1);
 
494
                        isl_int_set(bset->ineq[k][0], pnt2->vec->el[1 + i]);
 
495
                }
 
496
                isl_int_fdiv_q(bset->ineq[k][0], bset->ineq[k][0], pnt2->vec->el[0]);
 
497
        }
 
498
 
 
499
        bset = isl_basic_set_finalize(bset);
 
500
 
 
501
        isl_point_free(pnt1);
 
502
        isl_point_free(pnt2);
 
503
 
 
504
        isl_int_clear(t);
 
505
 
 
506
        return bset;
 
507
error:
 
508
        isl_point_free(pnt1);
 
509
        isl_point_free(pnt2);
 
510
        isl_int_clear(t);
 
511
        isl_basic_set_free(bset);
 
512
        return NULL;
 
513
}
 
514
 
 
515
__isl_give isl_set *isl_set_box_from_points(__isl_take isl_point *pnt1,
 
516
        __isl_take isl_point *pnt2)
 
517
{
 
518
        isl_basic_set *bset;
 
519
        bset = isl_basic_set_box_from_points(pnt1, pnt2);
 
520
        return isl_set_from_basic_set(bset);
 
521
}
 
522
 
 
523
/* Print the coordinate at position "pos" of the point "pnt".
 
524
 */
 
525
static __isl_give isl_printer *print_coordinate(__isl_take isl_printer *p,
 
526
        struct isl_print_space_data *data, unsigned pos)
 
527
{
 
528
        isl_point *pnt = data->user;
 
529
 
 
530
        p = isl_printer_print_isl_int(p, pnt->vec->el[1 + pos]);
 
531
        if (!isl_int_is_one(pnt->vec->el[0])) {
 
532
                p = isl_printer_print_str(p, "/");
 
533
                p = isl_printer_print_isl_int(p, pnt->vec->el[0]);
 
534
        }
 
535
 
 
536
        return p;
 
537
}
 
538
 
 
539
__isl_give isl_printer *isl_printer_print_point(
 
540
        __isl_take isl_printer *p, __isl_keep isl_point *pnt)
 
541
{
 
542
        struct isl_print_space_data data = { 0 };
 
543
        int i;
 
544
        unsigned nparam;
 
545
 
 
546
        if (!pnt)
 
547
                return p;
 
548
        if (isl_point_is_void(pnt)) {
 
549
                p = isl_printer_print_str(p, "void");
 
550
                return p;
 
551
        }
 
552
 
 
553
        nparam = isl_space_dim(pnt->dim, isl_dim_param);
 
554
        if (nparam > 0) {
 
555
                p = isl_printer_print_str(p, "[");
 
556
                for (i = 0; i < nparam; ++i) {
 
557
                        const char *name;
 
558
                        if (i)
 
559
                                p = isl_printer_print_str(p, ", ");
 
560
                        name = isl_space_get_dim_name(pnt->dim, isl_dim_param, i);
 
561
                        if (name) {
 
562
                                p = isl_printer_print_str(p, name);
 
563
                                p = isl_printer_print_str(p, " = ");
 
564
                        }
 
565
                        p = isl_printer_print_isl_int(p, pnt->vec->el[1 + i]);
 
566
                        if (!isl_int_is_one(pnt->vec->el[0])) {
 
567
                                p = isl_printer_print_str(p, "/");
 
568
                                p = isl_printer_print_isl_int(p, pnt->vec->el[0]);
 
569
                        }
 
570
                }
 
571
                p = isl_printer_print_str(p, "]");
 
572
                p = isl_printer_print_str(p, " -> ");
 
573
        }
 
574
        data.print_dim = &print_coordinate;
 
575
        data.user = pnt;
 
576
        p = isl_printer_print_str(p, "{ ");
 
577
        p = isl_print_space(pnt->dim, p, 0, &data);
 
578
        p = isl_printer_print_str(p, " }");
 
579
        return p;
 
580
}