/*

 * 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->data14.5k
) {

    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_entry12
)

    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_die1
(FN(PART,get_ctx)(part), isl_error_invalid,

      "overlapping domain with other part",

      return isl_stat_error);

  
return isl_stat_ok3
;

}

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