Line data Source code
1 : /*
2 : * Copyright 2010 INRIA Saclay
3 : * Copyright 2013 Ecole Normale Superieure
4 : * Copyright 2015 INRIA Paris-Rocquencourt
5 : *
6 : * Use of this software is governed by the MIT license
7 : *
8 : * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9 : * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 : * 91893 Orsay, France
11 : * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
12 : * and INRIA Paris-Rocquencourt, Domaine de Voluceau, Rocquenqourt, B.P. 105,
13 : * 78153 Le Chesnay Cedex France
14 : */
15 :
16 : #include <isl_hash_private.h>
17 : #include <isl_union_macro.h>
18 :
19 : /* A group of expressions defined over the same domain space "domain_space".
20 : * The entries of "part_table" are the individual expressions,
21 : * keyed on the entire space of the expression.
22 : *
23 : * Each UNION has its own groups, so there can only ever be a single
24 : * reference to each group.
25 : */
26 : S(UNION,group) {
27 : isl_space *domain_space;
28 : struct isl_hash_table part_table;
29 : };
30 :
31 : /* A union of expressions defined over different disjoint domains.
32 : * "space" describes the parameters.
33 : * The entries of "table" are keyed on the domain space of the entry and
34 : * contain groups of expressions that are defined over the same domain space.
35 : */
36 : struct UNION {
37 : int ref;
38 : isl_space *space;
39 :
40 : struct isl_hash_table table;
41 : };
42 :
43 : /* Internal data structure for isl_union_*_foreach_group.
44 : * "fn" is the function that needs to be called on each group.
45 : */
46 : S(UNION,foreach_group_data)
47 : {
48 : isl_stat (*fn)(__isl_keep S(UNION,group) *group, void *user);
49 : void *user;
50 : };
51 :
52 : /* Call data->fn on the group stored at *entry.
53 : */
54 0 : static isl_stat FN(UNION,call_on_group)(void **entry, void *user)
55 : {
56 0 : S(UNION,group) *group = *entry;
57 : S(UNION,foreach_group_data) *data;
58 :
59 0 : data = (S(UNION,foreach_group_data) *) user;
60 0 : return data->fn(group, data->user);
61 : }
62 :
63 : /* Call "fn" on each group of expressions in "u".
64 : */
65 0 : static isl_stat FN(UNION,foreach_group)(__isl_keep UNION *u,
66 : isl_stat (*fn)(__isl_keep S(UNION,group) *group, void *user),
67 : void *user)
68 : {
69 0 : S(UNION,foreach_group_data) data = { fn, user };
70 :
71 0 : if (!u)
72 0 : return isl_stat_error;
73 :
74 0 : return isl_hash_table_foreach(u->space->ctx, &u->table,
75 : &FN(UNION,call_on_group), &data);
76 : }
77 :
78 : /* A isl_union_*_foreach_group callback for counting the total number
79 : * of expressions in a UNION. Add the number of expressions in "group"
80 : * to *n.
81 : */
82 0 : static isl_stat FN(UNION,count_part)(__isl_keep S(UNION,group) *group,
83 : void *user)
84 : {
85 0 : int *n = user;
86 :
87 0 : if (!group)
88 0 : return isl_stat_error;
89 :
90 0 : *n += group->part_table.n;
91 0 : return isl_stat_ok;
92 : }
93 :
94 : /* Return the number of base expressions in "u".
95 : */
96 0 : int FN(FN(UNION,n),BASE)(__isl_keep UNION *u)
97 : {
98 : int n;
99 :
100 0 : n = 0;
101 0 : if (FN(UNION,foreach_group)(u, &FN(UNION,count_part), &n) < 0)
102 0 : n = -1;
103 0 : return n;
104 : }
105 :
106 : /* Free an entry in a group of expressions.
107 : * Each entry in such a group is a single expression.
108 : */
109 0 : static isl_stat FN(UNION,free_group_entry)(void **entry, void *user)
110 : {
111 0 : PART *part = *entry;
112 :
113 0 : FN(PART,free)(part);
114 0 : return isl_stat_ok;
115 : }
116 :
117 : /* Free all memory allocated for "group" and return NULL.
118 : */
119 0 : static __isl_null S(UNION,group) *FN(UNION,group_free)(
120 : __isl_take S(UNION,group) *group)
121 : {
122 : isl_ctx *ctx;
123 :
124 0 : if (!group)
125 0 : return NULL;
126 :
127 0 : ctx = isl_space_get_ctx(group->domain_space);
128 0 : isl_hash_table_foreach(ctx, &group->part_table,
129 : &FN(UNION,free_group_entry), NULL);
130 0 : isl_hash_table_clear(&group->part_table);
131 0 : isl_space_free(group->domain_space);
132 0 : free(group);
133 0 : return NULL;
134 : }
135 :
136 : /* Allocate a group of expressions defined over the same domain space
137 : * with domain space "domain_space" and initial size "size".
138 : */
139 0 : static __isl_give S(UNION,group) *FN(UNION,group_alloc)(
140 : __isl_take isl_space *domain_space, int size)
141 : {
142 : isl_ctx *ctx;
143 : S(UNION,group) *group;
144 :
145 0 : if (!domain_space)
146 0 : return NULL;
147 0 : ctx = isl_space_get_ctx(domain_space);
148 0 : group = isl_calloc_type(ctx, S(UNION,group));
149 0 : if (!group)
150 0 : goto error;
151 0 : group->domain_space = domain_space;
152 0 : if (isl_hash_table_init(ctx, &group->part_table, size) < 0)
153 0 : return FN(UNION,group_free)(group);
154 :
155 0 : return group;
156 : error:
157 0 : isl_space_free(domain_space);
158 0 : return NULL;
159 : }
160 :
161 : /* Is the space of "entry" equal to "space"?
162 : */
163 0 : static int FN(UNION,has_space)(const void *entry, const void *val)
164 : {
165 0 : PART *part = (PART *) entry;
166 0 : isl_space *space = (isl_space *) val;
167 :
168 0 : return isl_space_is_equal(part->dim, space);
169 : }
170 :
171 : /* Return a group equal to "group", but with a single reference.
172 : * Since all groups have only a single reference, simply return "group".
173 : */
174 0 : static __isl_give S(UNION,group) *FN(UNION,group_cow)(
175 : __isl_take S(UNION,group) *group)
176 : {
177 0 : return group;
178 : }
179 :
180 : S(UNION,foreach_data)
181 : {
182 : isl_stat (*fn)(__isl_take PART *part, void *user);
183 : void *user;
184 : };
185 :
186 0 : static isl_stat FN(UNION,call_on_copy)(void **entry, void *user)
187 : {
188 0 : PART *part = *entry;
189 0 : S(UNION,foreach_data) *data = (S(UNION,foreach_data) *) user;
190 :
191 0 : part = FN(PART,copy)(part);
192 0 : if (!part)
193 0 : return isl_stat_error;
194 0 : return data->fn(part, data->user);
195 : }
196 :
197 : /* Call data->fn on a copy of each expression in "group".
198 : */
199 0 : static isl_stat FN(UNION,group_call_on_copy)(__isl_keep S(UNION,group) *group,
200 : void *user)
201 : {
202 : isl_ctx *ctx;
203 :
204 0 : if (!group)
205 0 : return isl_stat_error;
206 :
207 0 : ctx = isl_space_get_ctx(group->domain_space);
208 0 : return isl_hash_table_foreach(ctx, &group->part_table,
209 : &FN(UNION,call_on_copy), user);
210 : }
211 :
212 0 : isl_stat FN(FN(UNION,foreach),BASE)(__isl_keep UNION *u,
213 : isl_stat (*fn)(__isl_take PART *part, void *user), void *user)
214 : {
215 0 : S(UNION,foreach_data) data = { fn, user };
216 :
217 0 : if (!u)
218 0 : return isl_stat_error;
219 :
220 0 : return FN(UNION,foreach_group)(u, &FN(UNION,group_call_on_copy), &data);
221 : }
222 :
223 : /* Is the domain space of the group of expressions at "entry"
224 : * equal to "space"?
225 : */
226 0 : static int FN(UNION,group_has_domain_space)(const void *entry, const void *val)
227 : {
228 0 : S(UNION,group) *group = (S(UNION,group) *) entry;
229 0 : isl_space *space = (isl_space *) val;
230 :
231 0 : return isl_space_is_domain_internal(group->domain_space, space);
232 : }
233 :
234 : /* Return the entry, if any, in "u" that lives in "space".
235 : * If "reserve" is set, then an entry is created if it does not exist yet.
236 : * Return NULL on error and isl_hash_table_entry_none if no entry was found.
237 : * Note that when "reserve" is set, the function will never return
238 : * isl_hash_table_entry_none.
239 : *
240 : * First look for the group of expressions with the same domain space,
241 : * creating one if needed.
242 : * Then look for the expression living in the specified space in that group.
243 : */
244 0 : static struct isl_hash_table_entry *FN(UNION,find_part_entry)(
245 : __isl_keep UNION *u, __isl_keep isl_space *space, int reserve)
246 : {
247 : isl_ctx *ctx;
248 : uint32_t hash;
249 : struct isl_hash_table_entry *group_entry, *part_entry;
250 : S(UNION,group) *group;
251 :
252 0 : if (!u || !space)
253 0 : return NULL;
254 :
255 0 : ctx = FN(UNION,get_ctx)(u);
256 0 : hash = isl_space_get_domain_hash(space);
257 0 : group_entry = isl_hash_table_find(ctx, &u->table, hash,
258 : &FN(UNION,group_has_domain_space), space, reserve);
259 0 : if (!group_entry)
260 0 : return reserve ? NULL : isl_hash_table_entry_none;
261 0 : if (reserve && !group_entry->data) {
262 0 : isl_space *domain = isl_space_domain(isl_space_copy(space));
263 0 : group = FN(UNION,group_alloc)(domain, 1);
264 0 : group_entry->data = group;
265 : } else {
266 0 : group = group_entry->data;
267 0 : if (reserve)
268 0 : group = FN(UNION,group_cow)(group);
269 : }
270 0 : if (!group)
271 0 : return NULL;
272 0 : hash = isl_space_get_hash(space);
273 0 : part_entry = isl_hash_table_find(ctx, &group->part_table, hash,
274 : &FN(UNION,has_space), space, reserve);
275 0 : if (!reserve && !part_entry)
276 0 : return isl_hash_table_entry_none;
277 0 : return part_entry;
278 : }
279 :
280 : /* Remove "part_entry" from the hash table of "u".
281 : *
282 : * First look the group_entry in "u" holding the group that
283 : * contains "part_entry". Remove "part_entry" from that group.
284 : * If the group becomes empty, then also remove the group_entry from "u".
285 : */
286 0 : static __isl_give UNION *FN(UNION,remove_part_entry)(__isl_take UNION *u,
287 : struct isl_hash_table_entry *part_entry)
288 : {
289 : isl_ctx *ctx;
290 : uint32_t hash;
291 : PART *part;
292 : struct isl_hash_table_entry *group_entry;
293 : S(UNION,group) *group;
294 :
295 0 : if (!u || !part_entry)
296 0 : return FN(UNION,free)(u);
297 :
298 0 : part = part_entry->data;
299 0 : ctx = FN(UNION,get_ctx)(u);
300 0 : hash = isl_space_get_domain_hash(part->dim);
301 0 : group_entry = isl_hash_table_find(ctx, &u->table, hash,
302 0 : &FN(UNION,group_has_domain_space), part->dim, 0);
303 0 : if (!group_entry)
304 0 : isl_die(ctx, isl_error_internal, "missing group",
305 : return FN(UNION,free)(u));
306 0 : group = group_entry->data;
307 0 : isl_hash_table_remove(ctx, &group->part_table, part_entry);
308 0 : FN(PART,free)(part);
309 :
310 0 : if (group->part_table.n != 0)
311 0 : return u;
312 :
313 0 : isl_hash_table_remove(ctx, &u->table, group_entry);
314 0 : FN(UNION,group_free)(group);
315 :
316 0 : return u;
317 : }
318 :
319 : /* Are the domains of "part1" and "part2" disjoint?
320 : */
321 0 : static isl_bool FN(UNION,disjoint_domain)(__isl_keep PART *part1,
322 : __isl_keep PART *part2)
323 : {
324 : isl_set *dom1, *dom2;
325 : isl_bool disjoint;
326 :
327 0 : if (!part1 || !part2)
328 0 : return isl_bool_error;
329 0 : dom1 = FN(PART,domain)(FN(PART,copy)(part1));
330 0 : dom2 = FN(PART,domain)(FN(PART,copy)(part2));
331 0 : disjoint = isl_set_is_disjoint(dom1, dom2);
332 0 : isl_set_free(dom1);
333 0 : isl_set_free(dom2);
334 :
335 0 : return disjoint;
336 : }
337 :
338 : /* Check that the expression at *entry has a domain that is disjoint
339 : * from that of "part", unless they also have the same target space.
340 : */
341 0 : static isl_stat FN(UNION,check_disjoint_domain_entry)(void **entry, void *user)
342 : {
343 0 : PART *part = user;
344 0 : PART *other = *entry;
345 : isl_bool equal;
346 : isl_bool disjoint;
347 :
348 0 : equal = isl_space_is_equal(part->dim, other->dim);
349 0 : if (equal < 0)
350 0 : return isl_stat_error;
351 0 : if (equal)
352 0 : return isl_stat_ok;
353 :
354 0 : disjoint = FN(UNION,disjoint_domain)(part, other);
355 0 : if (disjoint < 0)
356 0 : return isl_stat_error;
357 0 : if (!disjoint)
358 0 : isl_die(FN(PART,get_ctx)(part), isl_error_invalid,
359 : "overlapping domain with other part",
360 : return isl_stat_error);
361 0 : return isl_stat_ok;
362 : }
363 :
364 : /* Check that the domain of "part" is disjoint from the domain of the entries
365 : * in "u" that are defined on the same domain space, but have a different
366 : * target space.
367 : * If there is no group of expressions in "u" with the same domain space,
368 : * then everything is fine. Otherwise, check the individual expressions
369 : * in that group.
370 : */
371 0 : static isl_stat FN(UNION,check_disjoint_domain_other)(__isl_keep UNION *u,
372 : __isl_keep PART *part)
373 : {
374 : isl_ctx *ctx;
375 : uint32_t hash;
376 : struct isl_hash_table_entry *group_entry;
377 : S(UNION,group) *group;
378 :
379 0 : if (!u || !part)
380 0 : return isl_stat_error;
381 0 : ctx = FN(UNION,get_ctx)(u);
382 0 : hash = isl_space_get_domain_hash(part->dim);
383 0 : group_entry = isl_hash_table_find(ctx, &u->table, hash,
384 0 : &FN(UNION,group_has_domain_space), part->dim, 0);
385 0 : if (!group_entry)
386 0 : return isl_stat_ok;
387 0 : group = group_entry->data;
388 0 : return isl_hash_table_foreach(ctx, &group->part_table,
389 : &FN(UNION,check_disjoint_domain_entry), part);
390 : }
391 :
392 : /* Check that the domain of "part1" is disjoint from the domain of "part2".
393 : * This check is performed before "part2" is added to a UNION to ensure
394 : * that the UNION expression remains a function.
395 : */
396 0 : static isl_stat FN(UNION,check_disjoint_domain)(__isl_keep PART *part1,
397 : __isl_keep PART *part2)
398 : {
399 : isl_bool disjoint;
400 :
401 0 : disjoint = FN(UNION,disjoint_domain)(part1, part2);
402 0 : if (disjoint < 0)
403 0 : return isl_stat_error;
404 0 : if (!disjoint)
405 0 : isl_die(FN(PART,get_ctx)(part1), isl_error_invalid,
406 : "domain of additional part should be disjoint",
407 : return isl_stat_error);
408 0 : return isl_stat_ok;
409 : }
410 :
411 : /* Internal data structure for isl_union_*_foreach_inplace.
412 : * "fn" is the function that needs to be called on each entry.
413 : */
414 : S(UNION,foreach_inplace_data)
415 : {
416 : isl_stat (*fn)(void **entry, void *user);
417 : void *user;
418 : };
419 :
420 : /* isl_union_*_foreach_group callback for calling data->fn on
421 : * each part entry in the group.
422 : */
423 0 : static isl_stat FN(UNION,group_call_inplace)(__isl_keep S(UNION,group) *group,
424 : void *user)
425 : {
426 : isl_ctx *ctx;
427 : S(UNION,foreach_inplace_data) *data;
428 :
429 0 : if (!group)
430 0 : return isl_stat_error;
431 :
432 0 : data = (S(UNION,foreach_inplace_data) *) user;
433 0 : ctx = isl_space_get_ctx(group->domain_space);
434 0 : return isl_hash_table_foreach(ctx, &group->part_table,
435 : data->fn, data->user);
436 : }
437 :
438 : /* Call "fn" on each part entry of "u".
439 : */
440 0 : static isl_stat FN(UNION,foreach_inplace)(__isl_keep UNION *u,
441 : isl_stat (*fn)(void **part, void *user), void *user)
442 : {
443 0 : S(UNION,foreach_inplace_data) data = { fn, user };
444 :
445 0 : return FN(UNION,foreach_group)(u, &FN(UNION,group_call_inplace), &data);
446 : }
447 :
448 0 : static isl_stat FN(UNION,free_u_entry)(void **entry, void *user)
449 : {
450 0 : S(UNION,group) *group = *entry;
451 0 : FN(UNION,group_free)(group);
452 0 : return isl_stat_ok;
453 : }
454 :
455 : #include <isl_union_templ.c>
|
