polly/lib/External/isl/isl_union_multi.c - third_party/llvm-project - Git at Google

 /*
  * 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>
	/*
	* 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>