/* Copyright 1989, 1990 by James Aspnes, David Applegate, and Bennet Yee */
/* See the file COPYING for distribution information */
#include "os.h"
#include "alist.h"

#define alist_space_needed(size) (sizeof(datum) * 2 * (size + 1))

#define shrink_threshold(size) ((size) >> 3)    /* below this you shrink */
#define grow_threshold(size) (3 * ((size) >> 2))        /* above this you grow */

#define resize_leeway(count) ((count) << 1)     /* how much space to guarantee */

/* we don't worry about running off the end of this */
/* because malloc would blow out long before */
static unsigned long nice_primes[] = {
  3,
  7,
  13,
  31,
  61,
  127,
  251,
  509,
  1021,
  2039,
  4093,
  8191,
  16381,
  32749,
  65521,
  131071,
  262139,
  524287,
  1048573,
  2097143,
  4194301,
  8388593,
  16777213,
  33554393,
  67108859,
  134217689,
  268435399,
  536870909,
  1073741789,
  2147483647,
  4294967291
};

#define HASH(a, key) hash_range(alist_size(a), (key))
#define NEXT(a, key) next_probe(alist_size(a), key)
#define BETWEEN(lb, c, ub) \
    (((lb) <= (ub)) ? ((lb) <= (c) && (c) <= (ub)) \
     : ((c) >= (lb) || (c) <= (ub)))

int assoc (alist a, datum key, datum * value)
{
  unsigned long p;

  if (a == 0)
    return 0;

  for (p = HASH (a, key);
    alist_key (a, p) != NOTHING && alist_key (a, p) != key; p = NEXT (a, p));
  if (alist_key (a, p)) {
    if (value)
      *value = alist_value (a, p);
    return 1;
  } else {
    return 0;
  }
}


/* this just shoves it in without checking the count */
static void add_assoc1 (alist a, datum key, datum value)
{
  unsigned long p;

  /* find an empty slot */
  for (p = HASH (a, key); alist_key (a, p) != NOTHING; p = NEXT (a, p));

  alist_key (a, p) = key;
  alist_value (a, p) = value;
  alist_count (a)++;
}

/* resizes an alist to fit */
static alist resize_alist (alist a)
{
  unsigned long i;
  alist a1;

  if (a) {
    for (i = 0; nice_primes[i] <= (unsigned long)resize_leeway (alist_count (a)); i++);
  } else {
    i = 0;
  }

  /* nice_primes[i] is the new size */
  a1 = (alist) malloc (alist_space_needed (nice_primes[i]));
  alist_size (a1) = nice_primes[i];
  alist_count (a1) = 0;

  /* clear it out */
  for (i = 0; i < (unsigned long)alist_size (a1); i++) {
    alist_key (a1, i) = NOTHING;
  }

  /* throw in everything from the old one */
  if (a) {
    for (i = 0; i < (unsigned long)alist_size (a); i++) {
      if (alist_key (a, i) != NOTHING) {
        add_assoc1 (a1, alist_key (a, i), alist_value (a, i));
      }
    }
    free ((void *) a);
  }

  return a1;
}

/* adds an element to an alist */
alist add_assoc (alist a, datum key, datum value)
{
  if (a == 0 || alist_count (a) >= grow_threshold (alist_size (a))) {
    a = resize_alist (a);
  }

  add_assoc1 (a, key, value);

  return a;
}

/* deletes an element from an alist */
/* Don't ask me how it works, read Knuth vol. 2 p. 527 (Algorithm R) */
alist del_assoc (alist a, datum key, datum value)
{
  unsigned long p;
  unsigned long ub;

  /* skip until we get it */
  for (p = HASH (a, key);
    alist_key (a, p) != NOTHING
    && (alist_key (a, p) != key || alist_value (a, p) != value);
    p = NEXT (a, p));

  if (alist_key (a, p) == NOTHING) {
    return a;                   /* not found */
  } else if (--alist_count (a) == 0) {
    /* completely empty, nuke it */
    free ((void *) a);
    return 0;
  } else {
    /* scan for a replacement */
    for (;;) {
      alist_key (a, p) = NOTHING;       /* nuke this place */

      /* otherwise, look for something we can move up into p */
      ub = p;

      for (;;) {
        p = NEXT (a, p);
        if (alist_key (a, p) == NOTHING) {
          /* hit the end of the block */
          /* check for shrinkage */
          if (alist_count (a) <= shrink_threshold (alist_size (a))) {
            a = resize_alist (a);
          }
          return a;
        } else if (!BETWEEN (p, HASH (a, alist_key (a, p)), NEXT (a, ub))) {
          /* we've got something we can move up */
          alist_key (a, ub) = alist_key (a, p);
          alist_value (a, ub) = alist_value (a, p);
          break;                /* have to fill this slot now */
        }
      }
    }
  }
}

/* delete all occurences of key */
alist del_assocs (alist a, datum key)
{
  datum value;

  /* we'll be stupid about it, since a smart version would be painful */
  while (assoc (a, key, &value))
    a = del_assoc (a, key, value);

  return a;
}

/* sets first instance of key to point to value */
/* or adds (key, value) if key isn't there already */
alist set_assoc (alist a, datum key, datum value)
{
  unsigned long p;

  if (a) {
    for (p = HASH (a, key); alist_key (a, p) != NOTHING; p = NEXT (a, p)) {
      if (alist_key (a, p) == key) {
        /* got it */
        alist_value (a, p) = value;
        return a;
      }
    }
  }

  /* not there */
  return add_assoc (a, key, value);
}

alist copy_alist (alist a)
{
  alist a1;

  if (a == 0)
    return 0;                   /* empty */

  a1 = (alist) malloc (alist_space_needed (alist_size (a)));
  bcopy ((void *) a, (void *) a1, alist_space_needed (alist_size (a)));

  return a1;
}

datum alist_next (alist a, alist_iterator * i, datum * value)
{
  datum key;

  if (a) {
    for (i->pos++; i->pos < alist_size (a); i->pos++) {
      if ((key = alist_key (a, i->pos)) != NOTHING) {
        if (value)
          *value = alist_value (a, i->pos);
        return key;
      }
    }
  }

  if (value)
    *value = NOTHING;
  return NOTHING;
}

datum alist_first (alist a, alist_iterator * i, datum * value)
{
  i->pos = -1;
  return alist_next (a, i, value);
}

int alist_next_match (alist a, alist_iterator * i, datum * value)
{
  datum oldpos;
  datum key;

  if (a) {
    while ((key = alist_key (a, i->pos)) != NOTHING) {
      oldpos = i->pos;
      i->pos = next_probe (alist_size (a), i->pos);

      if (key == i->key) {
        if (value)
          *value = alist_value (a, oldpos);
        return 1;
      }
      /* else continue */
    }
  }
  return 0;
}

int alist_first_match (alist a, alist_iterator * i, datum * value, datum key)
{
  if (a) {
    i->key = key;
    i->pos = hash_range (alist_size (a), key);
    return alist_next_match (a, i, value);
  }
  return 0;
}

int alist_member (alist a, datum key, datum value)
{
  datum v;

  FOREACH_MATCH (a, key, v) {
    if (v == value)
      return 1;
  }
  END_FOREACH;

  return 0;
}