text: /*
   * 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".
   */
  isl_size 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)
  		return isl_size_error;
  	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);
  }
  
  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>
  