/* c3
 * Copyright 2022,2023 kmx.io <contact@kmx.io>
 *
 * Permission is hereby granted to use this software excepted
 * on Apple computers granted the above copyright notice and
 * this permission paragraph are included in all copies and
 * substantial portions of this software.
 *
 * THIS SOFTWARE IS PROVIDED "AS-IS" WITHOUT ANY GUARANTEE OF
 * PURPOSE AND PERFORMANCE. IN NO EVENT WHATSOEVER SHALL THE
 * AUTHOR BE CONSIDERED LIABLE FOR THE USE AND PERFORMANCE OF
 * THIS SOFTWARE.
 */
/* Gen from set.c.in NAME=_NAME$ TYPE=_TYPE$ */
#include <assert.h>
#include <stdlib.h>
#include "compare.h"
#include "_NAME$.h"
#include "set___NAME$.h"
#include "set_item___NAME$.h"

s_set_item___NAME$ *
set_add___NAME$ (s_set___NAME$ *set, const _TYPE$ *data)
{
  uw hash;
  assert(set);
  assert(data);
  hash = _NAME$_hash_uw(data);
  return set_add_h___NAME$(set, data, hash);
}

s_set_item___NAME$ *
set_add_collision___NAME$ (s_set___NAME$ *set, const _TYPE$ *data, uw hash, s_set_item___NAME$ *item)
{
  s_set_item___NAME$ *new_item;
  new_item = set_item_new___NAME$(data, hash, item->next);
  item->next = new_item;
  set->count++;
  set->collisions++;
  return new_item;
}

s_set_item___NAME$ *
set_add_h___NAME$ (s_set___NAME$ *set, const _TYPE$ *data, uw hash)
{
  uw h;
  s_set_item___NAME$ *i;
  assert(set);
  assert(data);
  if ((i = set_get_h___NAME$(set, data, hash)))
    return i;
  h = hash % set->max;
  if ((i = set->items[h]))
    return set_add_collision___NAME$(set, data, hash, i);
  i = set_item_new___NAME$(data, hash, NULL);
  set->items[h] = i;
  set->count++;
  return i;
}
                 
void
set_clean___NAME$ (s_set___NAME$ *set)
{
  uw i;
  assert(set);
  for (i = 0; i < set->max; i++) {
    set_item_delete_all___NAME$(set->items[i]);
  }
  free(set->items);
}

s_set_item___NAME$ *
set_get___NAME$ (const s_set___NAME$ *set, const _TYPE$ *data)
{
  uw hash;
  assert(set);
  assert(data);
  hash = _NAME$_hash_uw(data);
  return set_get_h___NAME$(set, data, hash);
}

s_set_item___NAME$ *
set_get_h___NAME$ (const s_set___NAME$ *set, const _TYPE$ *data, uw hash)
{
  s_set_item___NAME$ *i;
  assert(set);
  assert(data);
  i = set_get_hash___NAME$(set, hash);
  while (i) {
    if (compare__NAME$(&i->data, data) == 0)
      return i;
    i = set_get_hash_next___NAME$(i);
  }
  return NULL;
}

s_set_item___NAME$ *
set_get_hash___NAME$ (const s_set___NAME$ *set, uw hash)
{
  uw h;
  s_set_item___NAME$ *i;
  assert(set);
  h = hash % set->max;
  i = set->items[h];
  while (i && i->hash != hash)
    i = i->next;
  return i;
}

s_set_item___NAME$ *
set_get_hash_next___NAME$ (const s_set_item___NAME$ *item)
{
  s_set_item___NAME$ *i;
  assert(item);
  i = item->next;
  while (i && i->hash != item->hash)
    i = i->next;
  return i;
}

s_set___NAME$ *
set_init___NAME$ (s_set___NAME$ *set, uw max)
{
  assert(set);
  assert(max > 0);
  set->max = max;
  set->items = calloc(max, sizeof(s_set_item___NAME$ *));
  set->count = 0;
  set->collisions = 0;
  return set;
}

e_bool
set_remove___NAME$ (s_set___NAME$ *set, const _TYPE$ *data)
{
  s_set_item___NAME$ *item;
  if ((item = set_get___NAME$(set, data)))
    return set_remove_item___NAME$(set, item);
  return false;
}

e_bool
set_remove_item___NAME$ (s_set___NAME$ *set, s_set_item___NAME$ *item)
{
  sw h;
  s_set_item___NAME$ *i;
  s_set_item___NAME$ **j;
  s_set_item___NAME$ *k;
  assert(set);
  if (! item)
    return false;
  h = item->hash % set->max;
  j = set->items + h;
  while (*j && *j != item)
    j = &(*j)->next;
  if (!*j)
    return false;
  i = *j;
  k = i->next;
  set_item_delete___NAME$(i);
  *j = k;
  set->count--;
  if (set->items[h])
    set->collisions--;
  return true;
}

s_set___NAME$ *
set_resize___NAME$ (s_set___NAME$ *set, uw max)
{
  uw i;
  s_set_item___NAME$ *item;
  s_set___NAME$ n;
  if (set->max == max)
    return set;
  set_init___NAME$(&n, max);
  for (i = 0; i < set->max; i++) {
    item = set->items[i];
    while (item) {
      set_add_h___NAME$(&n, &item->data, item->hash);
      item = item->next;
    }
  }
  set_clean___NAME$(set);
  set->max = n.max;
  set->items = n.items;
  set->count = n.count;
  set->collisions = n.collisions;
  return set;
}
