| /* |
| * Copyright 2010 INRIA Saclay |
| * Copyright 2013 Ecole Normale Superieure |
| * Copyright 2015 INRIA Paris-Rocquencourt |
| * |
| * Use of this software is governed by the MIT license |
| * |
| * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France, |
| * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod, |
| * 91893 Orsay, France |
| * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France |
| * and INRIA Paris-Rocquencourt, Domaine de Voluceau, Rocquenqourt, B.P. 105, |
| * 78153 Le Chesnay Cedex France |
| */ |
| |
| #include <isl_hash_private.h> |
| #include <isl_union_macro.h> |
| |
| /* A group of expressions defined over the same domain space "domain_space". |
| * The entries of "part_table" are the individual expressions, |
| * keyed on the entire space of the expression. |
| * |
| * Each UNION has its own groups, so there can only ever be a single |
| * reference to each group. |
| */ |
| S(UNION,group) { |
| isl_space *domain_space; |
| struct isl_hash_table part_table; |
| }; |
| |
| /* A union of expressions defined over different disjoint domains. |
| * "space" describes the parameters. |
| * The entries of "table" are keyed on the domain space of the entry and |
| * contain groups of expressions that are defined over the same domain space. |
| */ |
| struct UNION { |
| int ref; |
| isl_space *space; |
| |
| struct isl_hash_table table; |
| }; |
| |
| /* Internal data structure for isl_union_*_foreach_group. |
| * "fn" is the function that needs to be called on each group. |
| */ |
| S(UNION,foreach_group_data) |
| { |
| isl_stat (*fn)(__isl_keep S(UNION,group) *group, void *user); |
| void *user; |
| }; |
| |
| /* Call data->fn on the group stored at *entry. |
| */ |
| static isl_stat FN(UNION,call_on_group)(void **entry, void *user) |
| { |
| S(UNION,group) *group = *entry; |
| S(UNION,foreach_group_data) *data; |
| |
| data = (S(UNION,foreach_group_data) *) user; |
| return data->fn(group, data->user); |
| } |
| |
| /* Call "fn" on each group of expressions in "u". |
| */ |
| static isl_stat FN(UNION,foreach_group)(__isl_keep UNION *u, |
| isl_stat (*fn)(__isl_keep S(UNION,group) *group, void *user), |
| void *user) |
| { |
| S(UNION,foreach_group_data) data = { fn, user }; |
| |
| if (!u) |
| return isl_stat_error; |
| |
| return isl_hash_table_foreach(u->space->ctx, &u->table, |
| &FN(UNION,call_on_group), &data); |
| } |
| |
| /* A isl_union_*_foreach_group callback for counting the total number |
| * of expressions in a UNION. Add the number of expressions in "group" |
| * to *n. |
| */ |
| static isl_stat FN(UNION,count_part)(__isl_keep S(UNION,group) *group, |
| void *user) |
| { |
| int *n = user; |
| |
| if (!group) |
| return isl_stat_error; |
| |
| *n += group->part_table.n; |
| return isl_stat_ok; |
| } |
| |
| /* Return the number of base expressions in "u". |
| */ |
| int FN(FN(UNION,n),BASE)(__isl_keep UNION *u) |
| { |
| int n; |
| |
| n = 0; |
| if (FN(UNION,foreach_group)(u, &FN(UNION,count_part), &n) < 0) |
| n = -1; |
| return n; |
| } |
| |
| /* Free an entry in a group of expressions. |
| * Each entry in such a group is a single expression. |
| */ |
| static isl_stat FN(UNION,free_group_entry)(void **entry, void *user) |
| { |
| PART *part = *entry; |
| |
| FN(PART,free)(part); |
| return isl_stat_ok; |
| } |
| |
| /* Free all memory allocated for "group" and return NULL. |
| */ |
| static __isl_null S(UNION,group) *FN(UNION,group_free)( |
| __isl_take S(UNION,group) *group) |
| { |
| isl_ctx *ctx; |
| |
| if (!group) |
| return NULL; |
| |
| ctx = isl_space_get_ctx(group->domain_space); |
| isl_hash_table_foreach(ctx, &group->part_table, |
| &FN(UNION,free_group_entry), NULL); |
| isl_hash_table_clear(&group->part_table); |
| isl_space_free(group->domain_space); |
| free(group); |
| return NULL; |
| } |
| |
| /* Allocate a group of expressions defined over the same domain space |
| * with domain space "domain_space" and initial size "size". |
| */ |
| static __isl_give S(UNION,group) *FN(UNION,group_alloc)( |
| __isl_take isl_space *domain_space, int size) |
| { |
| isl_ctx *ctx; |
| S(UNION,group) *group; |
| |
| if (!domain_space) |
| return NULL; |
| ctx = isl_space_get_ctx(domain_space); |
| group = isl_calloc_type(ctx, S(UNION,group)); |
| if (!group) |
| goto error; |
| group->domain_space = domain_space; |
| if (isl_hash_table_init(ctx, &group->part_table, size) < 0) |
| return FN(UNION,group_free)(group); |
| |
| return group; |
| error: |
| isl_space_free(domain_space); |
| return NULL; |
| } |
| |
| /* Is the space of "entry" equal to "space"? |
| */ |
| static int FN(UNION,has_space)(const void *entry, const void *val) |
| { |
| PART *part = (PART *) entry; |
| isl_space *space = (isl_space *) val; |
| |
| return isl_space_is_equal(part->dim, space); |
| } |
| |
| /* Return a group equal to "group", but with a single reference. |
| * Since all groups have only a single reference, simply return "group". |
| */ |
| static __isl_give S(UNION,group) *FN(UNION,group_cow)( |
| __isl_take S(UNION,group) *group) |
| { |
| return group; |
| } |
| |
| S(UNION,foreach_data) |
| { |
| isl_stat (*fn)(__isl_take PART *part, void *user); |
| void *user; |
| }; |
| |
| static isl_stat FN(UNION,call_on_copy)(void **entry, void *user) |
| { |
| PART *part = *entry; |
| S(UNION,foreach_data) *data = (S(UNION,foreach_data) *) user; |
| |
| part = FN(PART,copy)(part); |
| if (!part) |
| return isl_stat_error; |
| return data->fn(part, data->user); |
| } |
| |
| /* Call data->fn on a copy of each expression in "group". |
| */ |
| static isl_stat FN(UNION,group_call_on_copy)(__isl_keep S(UNION,group) *group, |
| void *user) |
| { |
| isl_ctx *ctx; |
| |
| if (!group) |
| return isl_stat_error; |
| |
| ctx = isl_space_get_ctx(group->domain_space); |
| return isl_hash_table_foreach(ctx, &group->part_table, |
| &FN(UNION,call_on_copy), user); |
| } |
| |
| isl_stat FN(FN(UNION,foreach),BASE)(__isl_keep UNION *u, |
| isl_stat (*fn)(__isl_take PART *part, void *user), void *user) |
| { |
| S(UNION,foreach_data) data = { fn, user }; |
| |
| if (!u) |
| return isl_stat_error; |
| |
| return FN(UNION,foreach_group)(u, &FN(UNION,group_call_on_copy), &data); |
| } |
| |
| /* Is the domain space of the group of expressions at "entry" |
| * equal to "space"? |
| */ |
| static int FN(UNION,group_has_domain_space)(const void *entry, const void *val) |
| { |
| S(UNION,group) *group = (S(UNION,group) *) entry; |
| isl_space *space = (isl_space *) val; |
| |
| return isl_space_is_domain_internal(group->domain_space, space); |
| } |
| |
| /* Return the entry, if any, in "u" that lives in "space". |
| * If "reserve" is set, then an entry is created if it does not exist yet. |
| * Return NULL on error and isl_hash_table_entry_none if no entry was found. |
| * Note that when "reserve" is set, the function will never return |
| * isl_hash_table_entry_none. |
| * |
| * First look for the group of expressions with the same domain space, |
| * creating one if needed. |
| * Then look for the expression living in the specified space in that group. |
| */ |
| static struct isl_hash_table_entry *FN(UNION,find_part_entry)( |
| __isl_keep UNION *u, __isl_keep isl_space *space, int reserve) |
| { |
| isl_ctx *ctx; |
| uint32_t hash; |
| struct isl_hash_table_entry *group_entry, *part_entry; |
| S(UNION,group) *group; |
| |
| if (!u || !space) |
| return NULL; |
| |
| ctx = FN(UNION,get_ctx)(u); |
| hash = isl_space_get_domain_hash(space); |
| group_entry = isl_hash_table_find(ctx, &u->table, hash, |
| &FN(UNION,group_has_domain_space), space, reserve); |
| if (!group_entry) |
| return reserve ? NULL : isl_hash_table_entry_none; |
| if (reserve && !group_entry->data) { |
| isl_space *domain = isl_space_domain(isl_space_copy(space)); |
| group = FN(UNION,group_alloc)(domain, 1); |
| group_entry->data = group; |
| } else { |
| group = group_entry->data; |
| if (reserve) |
| group = FN(UNION,group_cow)(group); |
| } |
| if (!group) |
| return NULL; |
| hash = isl_space_get_hash(space); |
| part_entry = isl_hash_table_find(ctx, &group->part_table, hash, |
| &FN(UNION,has_space), space, reserve); |
| if (!reserve && !part_entry) |
| return isl_hash_table_entry_none; |
| return part_entry; |
| } |
| |
| /* Remove "part_entry" from the hash table of "u". |
| * |
| * First look the group_entry in "u" holding the group that |
| * contains "part_entry". Remove "part_entry" from that group. |
| * If the group becomes empty, then also remove the group_entry from "u". |
| */ |
| static __isl_give UNION *FN(UNION,remove_part_entry)(__isl_take UNION *u, |
| struct isl_hash_table_entry *part_entry) |
| { |
| isl_ctx *ctx; |
| uint32_t hash; |
| PART *part; |
| struct isl_hash_table_entry *group_entry; |
| S(UNION,group) *group; |
| |
| if (!u || !part_entry) |
| return FN(UNION,free)(u); |
| |
| part = part_entry->data; |
| ctx = FN(UNION,get_ctx)(u); |
| hash = isl_space_get_domain_hash(part->dim); |
| group_entry = isl_hash_table_find(ctx, &u->table, hash, |
| &FN(UNION,group_has_domain_space), part->dim, 0); |
| if (!group_entry) |
| isl_die(ctx, isl_error_internal, "missing group", |
| return FN(UNION,free)(u)); |
| group = group_entry->data; |
| isl_hash_table_remove(ctx, &group->part_table, part_entry); |
| FN(PART,free)(part); |
| |
| if (group->part_table.n != 0) |
| return u; |
| |
| isl_hash_table_remove(ctx, &u->table, group_entry); |
| FN(UNION,group_free)(group); |
| |
| return u; |
| } |
| |
| /* Are the domains of "part1" and "part2" disjoint? |
| */ |
| static isl_bool FN(UNION,disjoint_domain)(__isl_keep PART *part1, |
| __isl_keep PART *part2) |
| { |
| isl_set *dom1, *dom2; |
| isl_bool disjoint; |
| |
| if (!part1 || !part2) |
| return isl_bool_error; |
| dom1 = FN(PART,domain)(FN(PART,copy)(part1)); |
| dom2 = FN(PART,domain)(FN(PART,copy)(part2)); |
| disjoint = isl_set_is_disjoint(dom1, dom2); |
| isl_set_free(dom1); |
| isl_set_free(dom2); |
| |
| return disjoint; |
| } |
| |
| /* Check that the expression at *entry has a domain that is disjoint |
| * from that of "part", unless they also have the same target space. |
| */ |
| static isl_stat FN(UNION,check_disjoint_domain_entry)(void **entry, void *user) |
| { |
| PART *part = user; |
| PART *other = *entry; |
| isl_bool equal; |
| isl_bool disjoint; |
| |
| equal = isl_space_is_equal(part->dim, other->dim); |
| if (equal < 0) |
| return isl_stat_error; |
| if (equal) |
| return isl_stat_ok; |
| |
| disjoint = FN(UNION,disjoint_domain)(part, other); |
| if (disjoint < 0) |
| return isl_stat_error; |
| if (!disjoint) |
| isl_die(FN(PART,get_ctx)(part), isl_error_invalid, |
| "overlapping domain with other part", |
| return isl_stat_error); |
| return isl_stat_ok; |
| } |
| |
| /* Check that the domain of "part" is disjoint from the domain of the entries |
| * in "u" that are defined on the same domain space, but have a different |
| * target space. |
| * If there is no group of expressions in "u" with the same domain space, |
| * then everything is fine. Otherwise, check the individual expressions |
| * in that group. |
| */ |
| static isl_stat FN(UNION,check_disjoint_domain_other)(__isl_keep UNION *u, |
| __isl_keep PART *part) |
| { |
| isl_ctx *ctx; |
| uint32_t hash; |
| struct isl_hash_table_entry *group_entry; |
| S(UNION,group) *group; |
| |
| if (!u || !part) |
| return isl_stat_error; |
| ctx = FN(UNION,get_ctx)(u); |
| hash = isl_space_get_domain_hash(part->dim); |
| group_entry = isl_hash_table_find(ctx, &u->table, hash, |
| &FN(UNION,group_has_domain_space), part->dim, 0); |
| if (!group_entry) |
| return isl_stat_ok; |
| group = group_entry->data; |
| return isl_hash_table_foreach(ctx, &group->part_table, |
| &FN(UNION,check_disjoint_domain_entry), part); |
| } |
| |
| /* Check that the domain of "part1" is disjoint from the domain of "part2". |
| * This check is performed before "part2" is added to a UNION to ensure |
| * that the UNION expression remains a function. |
| */ |
| static isl_stat FN(UNION,check_disjoint_domain)(__isl_keep PART *part1, |
| __isl_keep PART *part2) |
| { |
| isl_bool disjoint; |
| |
| disjoint = FN(UNION,disjoint_domain)(part1, part2); |
| if (disjoint < 0) |
| return isl_stat_error; |
| if (!disjoint) |
| isl_die(FN(PART,get_ctx)(part1), isl_error_invalid, |
| "domain of additional part should be disjoint", |
| return isl_stat_error); |
| return isl_stat_ok; |
| } |
| |
| /* Internal data structure for isl_union_*_foreach_inplace. |
| * "fn" is the function that needs to be called on each entry. |
| */ |
| S(UNION,foreach_inplace_data) |
| { |
| isl_stat (*fn)(void **entry, void *user); |
| void *user; |
| }; |
| |
| /* isl_union_*_foreach_group callback for calling data->fn on |
| * each part entry in the group. |
| */ |
| static isl_stat FN(UNION,group_call_inplace)(__isl_keep S(UNION,group) *group, |
| void *user) |
| { |
| isl_ctx *ctx; |
| S(UNION,foreach_inplace_data) *data; |
| |
| if (!group) |
| return isl_stat_error; |
| |
| data = (S(UNION,foreach_inplace_data) *) user; |
| ctx = isl_space_get_ctx(group->domain_space); |
| return isl_hash_table_foreach(ctx, &group->part_table, |
| data->fn, data->user); |
| } |
| |
| /* Call "fn" on each part entry of "u". |
| */ |
| static isl_stat FN(UNION,foreach_inplace)(__isl_keep UNION *u, |
| isl_stat (*fn)(void **part, void *user), void *user) |
| { |
| S(UNION,foreach_inplace_data) data = { fn, user }; |
| |
| return FN(UNION,foreach_group)(u, &FN(UNION,group_call_inplace), &data); |
| } |
| |
| /* Does "u" have a single reference? |
| * That is, can we change "u" inplace? |
| */ |
| static isl_bool FN(UNION,has_single_reference)(__isl_keep UNION *u) |
| { |
| if (!u) |
| return isl_bool_error; |
| return u->ref == 1; |
| } |
| |
| static isl_stat FN(UNION,free_u_entry)(void **entry, void *user) |
| { |
| S(UNION,group) *group = *entry; |
| FN(UNION,group_free)(group); |
| return isl_stat_ok; |
| } |
| |
| #include <isl_union_templ.c> |