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

extern const char *alloc_string (const char *);

/* Incremental garbage collector defs */

#define GC_DORMANT 0            /* not currently running */
#define GC_CLEAR   1            /* pass to clear string marks */
#define GC_CLEAR_CODE 2         /* pass to clear compiled code */
#define GC_SCAN    3            /* object scanning pass */
#define GC_RECOVER 4            /* pass to free unmarked strings */

#define GC_SCAN_COST 16         /* cost of scanning one object */
                                /* relative to clearing a string */

static void igc_reset (void);

static int igc_state = GC_DORMANT;
static datum igc_position = 0;  /* position in string or object table */

#ifdef NOISY_GC
static int gc_strcount = 0;     /* strings freed */
static int gc_codecount = 0;    /* code blobs freed */
static int gc_expcount = 0;     /* alias expansions freed */
#endif /* NOISY_GC */

/*** STRING TABLE ***/

static datum hash_function_table[256];
static int hft_initialized = 0;

static void init_hft (void)
{
  int i;

  for (i = 0; i < 256; i++)
    hash_function_table[i] = RAND ();
  hft_initialized = 1;
}

static datum hash_function (const char *string)
{
  datum hash;

  if (!hft_initialized)
    init_hft ();
  hash = 0;
  while (*string) {
    hash ^= ((hash >> 1) ^ hash_function_table[*string++]);
  }
  return (hash);
}

/* tags for st_elt's */
#define ST_EMPTY 0              /* empty element, reserved */
#define ST_FREE 1               /* free element */
#define ST_USED 2               /* element in use */
#define ST_MARKED 3             /* marked used element (for gc) */

struct st_elt {
  const char *s;                /* string held here */
  datum *code;                  /* compiled version of string */
  alist expansion;              /* expanded aliases */
  datum d;                      /* next item in free list OR hash value */
  char tag;
} *st = 0;

static datum st_top = 0;
static datum st_free_head = NOTHING;
static alist st_alist;

#define st_empty(loc) (loc < 0 || loc >= st_top || !(st[loc].tag & ST_USED))

static void grow_st (datum new_elt)
{
  datum old_top;
  datum i;

  if (new_elt < st_top)
    return;
  if (new_elt <= FIXED_STRINGS)
    new_elt = FIXED_STRINGS + 1;

  /* else get a new size */
  old_top = st_top;
#ifdef DB_DOUBLING
  while (new_elt < st_top)
    st_top *= 2;
#else
  st_top = new_elt + 1;
#endif /* DB_DOUBLING */

  /* grow it */
  if ((st
      = (struct st_elt *) realloc ((void *) st,
        (new_elt + 1) * sizeof (struct st_elt)))
    == 0)
    abort ();

  /* free all the new elements */
  for (i = st_top - 1; i >= old_top; i--) {
    if (i < FIXED_STRINGS) {
      st[i].tag = ST_EMPTY;
    } else {
      st[i].tag = ST_FREE;
      st[i].d = st_free_head;
      st_free_head = i;
    }
  }
}

static int add_string (const char *s, datum hash)
{
  datum loc;                    /* where to put it */

  if (strlen (s) >= MAX_STRLEN)
    return NOTHING;

  while (st_free_head == NOTHING) {
    grow_st (st_top);
  }

  loc = st_free_head;
  st_free_head = st[loc].d;

  st[loc].tag = ST_MARKED;      /* for incremental gc */
  st[loc].d = hash;
  st[loc].s = alloc_string (s);
  st[loc].code = 0;
  st[loc].expansion = empty_alist ();

  /* add it to the alist */
  st_alist = add_assoc (st_alist, hash, loc);

  return loc;
}

datum intern_soft (const char *s)
{
  datum hash;
  datum loc;

  if (s == 0)
    return NOTHING;

  hash = hash_function (s);

  FOREACH_MATCH (st_alist, hash, loc) {
    if (!strcmp (s, st[loc].s)) {
      st[loc].tag = ST_MARKED;
      return loc;
    }
  }
  END_FOREACH;

  return NOTHING;
}

datum intern (const char *s)
{
  datum hash;
  datum loc;

  if (s == 0)
    return NOTHING;

  hash = hash_function (s);

  FOREACH_MATCH (st_alist, hash, loc) {
    if (!strcmp (s, st[loc].s)) {
      st[loc].tag = ST_MARKED;
      return loc;
    }
  }
  END_FOREACH;

  /* else stuff it in */
  return add_string (s, hash);
}

const char *string (datum loc)
{
  if (st_empty (loc)) {
    return 0;                   /* you lose */
  } else {
    return st[loc].s;
  }
}

void set_compiled_string (datum loc, datum * c)
{
  if (st_empty (loc))
    abort ();
  if (st[loc].code)
    free ((void *) st[loc].code);
  st[loc].code = c;
}

datum *get_compiled_string (datum loc)
{
  if (st_empty (loc)) {
    return 0;
  } else {
    return st[loc].code;
  }
}

void set_expansion (datum loc, alist a)
{
  if (st_empty (loc))
    abort ();
  st[loc].expansion = a;
}

alist get_expansion (datum loc)
{
  if (st_empty (loc)) {
    return 0;
  } else {
    return st[loc].expansion;
  }
}

static void clear_st (void)
{
  datum i;

  /* clear out the old string table */
  if (st) {
    free_alist (st_alist);
    for (i = 0; i < st_top; i++) {
      if (!st_empty (i)) {
        free ((void *) st[i].s);
        if (st[i].code)
          free ((void *) st[i].code);
        free_alist (st[i].expansion);
      }
    }
    st_top = 0;
    free ((void *) st);
  }

  /* make a new string table */
  st = (struct st_elt *) malloc (1);
  st_top = 0;
  st_alist = empty_alist ();
}

/* call this if the free list has been trashed */
static void rebuild_st_free (void)
{
  datum i;

  /* nuke the old one */
  st_free_head = 0;

  /* go from the top so small numbers end up near front */
  for (i = st_top - 1; i >= FIXED_STRINGS; i--) {
    if (st[i].tag == ST_FREE) {
      st[i].d = st_free_head;
      st_free_head = i;
    }
  }
}

static int put_datum (datum x, FILE * f)
{
  fprintf (f, "%ld\n", x);

  return 0;
}

static int put_string (const char *s, FILE * f)
{
  while (*s) {
    switch (*s) {
    case '\n':
      /* mark it */
      putc ('\\', f);
      putc ('n', f);
      break;
    case '\\':
      putc ('\\', f);
      putc ('\\', f);
      break;
    default:
      putc (*s, f);
    }
    s++;
  }
  putc ('\n', f);

  return 0;
}

static int write_st (FILE * f)
{
  datum i;

  for (i = 0; i < st_top; i++) {
    if (!st_empty (i)) {
      put_datum (i, f);
      put_string (st[i].s, f);
    }
  }
  put_datum (NOTHING, f);       /* end of table */

  return 0;
}

static datum get_datum (FILE * f)
{
  static char buf[32];

  FGETS (buf, sizeof (buf), f);
  return atol (buf);
}

static const char *get_string (FILE * f)
{
  static char buf[MAX_STRLEN + 1];
  int i;
  int c;

  for (i = 0; i < MAX_STRLEN;) {
    switch (c = getc (f)) {
    case '\\':
      /* escape sequence */
      switch (c = getc (f)) {
      case 'n':
        buf[i++] = '\n';
        break;
      case '\\':
        buf[i++] = '\\';
        break;
      default:
        return 0;               /* bad input */
      }
      break;
    case '\n':
      /* end of input */
      buf[i] = '\0';
      return buf;
    case EOF:
      /* disaster */
      return 0;
    default:
      buf[i++] = c;
      break;
    }
  }

  /* ran off the end */
  return 0;
}

static int read_st (FILE * f)
{
  datum loc;

  clear_st ();

  while ((loc = get_datum (f)) != NOTHING) {
    grow_st (loc);

    /* we'll clean up the free list later */
    st[loc].tag = ST_USED;
    st[loc].s = alloc_string (get_string (f));
    if (st[loc].s == 0) {
      return -1;                /* error */
    }
    st[loc].d = hash_function (st[loc].s);
    st[loc].code = 0;
    st[loc].expansion = empty_alist ();

    st_alist = add_assoc (st_alist, st[loc].d, loc);
  }

  /* fix the free list, which we have so happily trashed above */
  rebuild_st_free ();

  return 0;
}

/*** OBJECT TABLE ***/
/* Uses bucket hashing 'cuz the overhead isn't that bad here */

struct hashed_object {
  datum id;
  struct object object;
  struct hashed_object *next;
};

static struct hashed_object **object_table = 0;
static datum object_table_size = 0;
static datum object_table_count = 0;
static datum top_object = 1;

struct object *_safe_get_TMP;

struct object *object (datum id)
{
  struct hashed_object *h;

  if (object_table_size != 0) {
    h = object_table[hash_range (object_table_size, id)];
    while (h) {
      if (h->id == id)
        return &h->object;
      h = h->next;
    }
  }
  return 0;
}

#define OBJECT_TABLE_INITIAL_SIZE (1)

static void init_object_table (void)
{
  datum i;

  object_table_size = OBJECT_TABLE_INITIAL_SIZE;
  object_table_count = 0;
  object_table = (struct hashed_object **)
    malloc (object_table_size * sizeof (struct hashed_object *));

  for (i = 0; i < object_table_size; i++)
    object_table[i] = 0;
}

static void grow_object_table (void)
{
  datum i;
  struct hashed_object **old_table;
  datum old_size;
  struct hashed_object **new_table;
  datum new_size;
  struct hashed_object *h;
  struct hashed_object *next;
  datum loc;

  /* get a new table */
  /* we don't assign directly to object_table so it will still be valid */
  /* even if the malloc fails */
  new_size = object_table_size << 1;
  if ((new_table = (struct hashed_object **)
      malloc (new_size * sizeof (struct hashed_object *))) == 0) {
    /* disaster */
    abort ();
  }

  /* got it ok, map everything over */
  old_table = object_table;
  old_size = object_table_size;

  object_table = new_table;
  object_table_size = new_size;
  /* count doesn't change */

  /* clear the new table */
  for (i = 0; i < object_table_size; i++)
    object_table[i] = 0;

  /* bring the old objects */
  for (i = 0; i < old_size; i++) {
    h = old_table[i];
    while (h) {
      next = h->next;
      loc = hash_range (object_table_size, h->id);
      h->next = object_table[loc];
      object_table[loc] = h;
      h = next;
    }
  }

  /* free the old table */
  free ((void *) old_table);

  /* reset the incremental garbage collector */
  /* values are now bogus */
  igc_reset ();
}

/* creates a new entry if there wasn't one before */
static struct object *get_object (datum id)
{
  datum loc;
  struct hashed_object *h;

  /* make sure the table is there */
  if (object_table_size == 0) {
    init_object_table ();
  }

  loc = hash_range (object_table_size, id);

  h = object_table[loc];
  while (h) {
    if (h->id == id)
      return &h->object;
    h = h->next;
  }

  /* not there */
  /* create it */
  h = (struct hashed_object *) malloc (sizeof (struct hashed_object));
  h->id = id;
  h->next = object_table[loc];
  object_table[loc] = h;

  /* make sure it won't get allocated by new_object */
  if (id >= top_object)
    top_object = id + 1;

  /* load factor threshold for rehash is 1 */
  if (++object_table_count >= object_table_size) {
    grow_object_table ();
  }

  return &h->object;
}

datum new_object (datum owner)
{
  datum id;
  struct object *o;

  id = top_object++;            /* get a new number */
  o = get_object (id);          /* allocate the new object */

  o->vars = empty_alist ();
  o->sets = empty_alist ();
  o->actions = empty_alist ();
  o->owner = owner;
  o->parent = NOTHING;
  o->location = NOTHING;
  o->flags = 0;

  return id;
}

void free_object (datum id)
{
  datum loc;
  struct hashed_object *prev;
  struct hashed_object *h;
  struct object *l;
  set c;                        /* contents list */

  loc = hash_range (object_table_size, id);
  if (object_table[loc]->id == id) {
    /* delete the very first entry */
    h = object_table[loc];
    object_table[loc] = h->next;
  } else {
    for (prev = object_table[loc]; prev->next; prev = prev->next) {
      if (prev->next->id == id) {
        /* nuke prev->next */
        h = prev->next;
        prev->next = h->next;
        goto got_it;
      }
    }
    /* not there! */
    return;
  }

got_it:
  /* remove it from its location if it has one */
  if ((l = object (h->object.location))
    && assoc (l->sets, CONTENTS_NAME, (datum *) &c)) {
    set_assoc (l->sets, CONTENTS_NAME, (datum) del_member (c, h->id));
  }

  /* free up everything */
  free_alist (h->object.vars);
  free_alist (h->object.actions);

  free ((void *) h);
}

static int put_alist (alist a, FILE * f)
{
  datum key;
  datum value;

  FOREACH (a, key, value) {
    put_datum (key, f);
    put_datum (value, f);
  } END_FOREACH;
  put_datum (NOTHING, f);

  return 0;
}

static int put_set (set s, FILE * f)
{
  datum x;

  SET_FOREACH (s, x) {
    put_datum (x, f);
  } END_SET_FOREACH;

  put_datum (NOTHING, f);

  return 0;
}

static int put_sets (alist a, FILE * f)
{
  datum key;
  datum value;

  FOREACH (a, key, value) {
    put_datum (key, f);
    put_set ((set) value, f);
  } END_FOREACH;
  put_datum (NOTHING, f);

  return 0;
}

static int put_object (struct hashed_object *h, FILE * f)
{
  putc ('#', f);
  put_datum (h->id, f);
  put_alist (h->object.vars, f);
  put_sets (h->object.sets, f);
  put_alist (h->object.actions, f);
  put_datum (h->object.owner, f);
  put_datum (h->object.parent, f);
  put_datum (h->object.location, f);
  put_datum (h->object.flags, f);

  return 0;
}

int db_write (FILE * f)
{
  datum i;
  struct hashed_object *h;

  fputs (DB_HEADER, f);

  if (write_st (f) < 0)
    return -1;

  for (i = 0; i < object_table_size; i++) {
    for (h = object_table[i]; h; h = h->next) {
      if (put_object (h, f) < 0)
        return -1;
    }
  }

  /* end it with a NOTHING id */
  putc ('#', f);
  put_datum (NOTHING, f);

  return 0;
}

static alist get_alist (FILE * f)
{
  datum key;
  datum value;
  alist a;

  a = empty_alist ();

  while ((key = get_datum (f)) != NOTHING) {
    value = get_datum (f);
    a = add_assoc (a, key, value);
  }
  return a;
}

static set get_set (FILE * f)
{
  datum x;
  set s;

  s = empty_set ();

  while ((x = get_datum (f)) != NOTHING) {
    s = add_member (s, x);
  }
  return s;
}

static alist get_sets (FILE * f)
{
  alist a;
  set s;

  datum key;

  a = empty_alist ();

  while ((key = get_datum (f)) != NOTHING) {
    s = get_set (f);
    a = add_assoc (a, key, (datum) s);
  }
  return a;
}

/* Don't do this more than once if you care about storage leaks */
int db_read (FILE * f)
{
  datum id;
  struct object *o;
  char buf[sizeof (DB_HEADER) + 1];

  /* check the header */
  if (FGETS (buf, sizeof (DB_HEADER), f) == 0 || strcmp (buf, DB_HEADER))
    return -1;

  if (read_st (f) < 0)
    return -1;

  for (;;) {
    if (getc (f) != '#')
      return -1;                /* bad object head */
    if ((id = get_datum (f)) == NOTHING)
      break;                    /* done */

    /* else */
    o = get_object (id);
    o->vars = get_alist (f);
    o->sets = get_sets (f);
    o->actions = get_alist (f);
    o->owner = get_datum (f);
    o->parent = get_datum (f);
    o->location = get_datum (f);
    o->flags = get_datum (f);
  }

  return 0;
}

/*** GARBAGE COLLECTOR ***/

void gc_mark_string (datum s)
{
  if (s != NOTHING) {
#ifdef DEBUG
    if (st_empty (s))
      abort ();
#endif /* DEBUG */
    st[s].tag = ST_MARKED;
  }
}

static void gc_mark_keys (alist a)
{
  datum key;
  datum value;

  FOREACH (a, key, value) {
    gc_mark_string (key);
  } END_FOREACH;
}

static void gc_free (datum s)
{
  /* take it out of the alist */
  st_alist = del_assoc (st_alist, st[s].d, s);

  /* nuke the string */
  free ((void *) st[s].s);

  /* nuke the code and expansion */
  if (st[s].code)
    free ((void *) st[s].code);
  free_alist (st[s].expansion);

  /* put it on the free list */
  st[s].tag = ST_FREE;
  st[s].d = st_free_head;
  st_free_head = s;

#ifdef NOISY_GC
  /* count it */
  gc_strcount++;
#endif /* NOISY_GC */
}

static int gc_mark_objects (datum position)
{
  struct hashed_object *ho;
  struct object *o;
  datum key;
  datum value;
  int count;

  count = 0;
  for (ho = object_table[position]; ho; ho = ho->next) {
    count++;
    o = &ho->object;

    /* mark all keys */
    gc_mark_keys (o->vars);
    gc_mark_keys (o->sets);
    gc_mark_keys (o->actions);

    /* mark string variables */
    FOREACH (o->vars, key, value) {
      if (*string (key) == STRING_MARKER) {
        gc_mark_string (value);
      }
    }
    END_FOREACH;

    /* mark action values */
    FOREACH (o->actions, key, value) {
      gc_mark_string (value);
    }
    END_FOREACH;

    /* blast name lists */
    FOREACH (o->sets, key, value) {
      set_clear_name_list ((set) value);
    }
    END_FOREACH;
  }

  return count;
}


/* GC everything */
void full_gc (void)
{
  int i;

  /* clear string table marks */
  for (i = 0; i < st_top; i++) {
    if (st[i].tag == ST_MARKED)
      st[i].tag = ST_USED;

    /* we can combine CLEAR and CLEAR_CODE steps */
    /* because nobody can compile new code while we're running */
    if (!st_empty (i) && st[i].code) {
      free ((void *) st[i].code);
      st[i].code = 0;
#ifdef NOISY_GC
      gc_codecount++;
#endif /* NOISY_GC */
    }
    if (!st_empty (i) && !isempty (st[i].expansion)) {
      free_alist (st[i].expansion);
      st[i].expansion = empty_alist ();
#ifdef NOISY_GC
      gc_expcount++;
#endif /* NOISY_GC */
    }
  }

  /* walk the object table */
  for (i = 0; i < object_table_size; i++) {
    gc_mark_objects (i);
  }

  /* clear unfixed strings that aren't marked */
  for (i = FIXED_STRINGS; i < st_top; i++) {
    if (st[i].tag == ST_USED) {
      /* zap it */
      gc_free (i);
    }
  }
#ifdef NOISY_GC
  fprintf (stderr,
    "GC finished, reclaimed %d strings %d codes %d aliases\n",
    gc_strcount, gc_codecount, gc_expcount);
#endif /* NOISY_GC */

  igc_reset ();
}

/*** INCREMENTAL GC ***/
static void igc_reset (void)
{
  igc_state = GC_DORMANT;
#ifdef NOISY_GC
  gc_codecount = 0;
  gc_strcount = 0;
  gc_expcount = 0;
#endif /* NOISY_GC */
}

void incremental_gc (void)
{
  int count;

  /* compute the count for this step */
  count = (st_top               /* CLEAR */
    + st_top                    /* CLEAR_CODE */
    + GC_SCAN_COST * object_table_size  /* SCAN */
    + st_top                    /* RECOVER */
    + GC_RATE - 1               /* round up */
    ) / GC_RATE;

  switch (igc_state) {
  case GC_DORMANT:
    igc_state = GC_CLEAR;
    igc_position = 0;
    /* fall through */
  case GC_CLEAR:
    while (igc_position < st_top) {
      if (--count < 0)
        return;
      if (st[igc_position].tag == ST_MARKED) {
        st[igc_position].tag = ST_USED;
      }
      igc_position++;
    }

    /* if got here we're done with the CLEAR stage */
    igc_state = GC_CLEAR_CODE;
    igc_position = 0;

    /* fall through */
  case GC_CLEAR_CODE:
    while (igc_position < st_top) {
      if (--count < 0)
        return;
      if (!st_empty (igc_position)) {
        if (st[igc_position].code) {
          free ((void *) st[igc_position].code);
          st[igc_position].code = 0;
#ifdef NOISY_GC
          gc_codecount++;
#endif /* NOISY_GC */
        }
        if (!isempty (st[igc_position].expansion)) {
          free_alist (st[igc_position].expansion);
          st[igc_position].expansion = empty_alist ();
#ifdef NOISY_GC
          gc_expcount++;
#endif /* NOISY_GC */
        }
      }
      igc_position++;
    }
    /* if got here we're done with the CLEAR_CODE stage */
    igc_state = GC_SCAN;
    igc_position = 0;

    /* fall through */
  case GC_SCAN:
    while (igc_position < object_table_size) {
      if (count < 0)
        return;
      count -= GC_SCAN_COST * gc_mark_objects (igc_position);
      igc_position++;
    }

    /* if we got here we're done with the SCAN stage */
    igc_state = GC_RECOVER;
    igc_position = FIXED_STRINGS;

    /* fall through */
  case GC_RECOVER:
    while (igc_position < st_top) {
      if (--count < 0)
        return;
      if (st[igc_position].tag == ST_USED) {
        gc_free (igc_position);
      }
      igc_position++;
    }

    /* if got here we're done with the RECOVER stage */
    /* give up and go home */
#ifdef NOISY_GC
    fprintf (stderr,
      "GC finished, reclaimed %d strings %d codes %d aliases\n",
      gc_strcount, gc_codecount, gc_expcount);
#endif /* NOISY_GC */
    igc_reset ();
    return;
  }
}

/*** for mapping over every object in the database ***/
int foreach_object (void (*func) (datum))
{
  datum pos;
  struct hashed_object *h;
  datum *object_list;
  datum i;

  /* construct a list of all object id's currently in the database */
  /* this way it doesn't matter if the list changes */
  object_list = (datum *) malloc (sizeof (datum) * object_table_count);

  i = 0;
  for (pos = 0; pos < object_table_size; pos++) {
    for (h = object_table[pos]; h; h = h->next) {
      object_list[i++] = h->id;
    }
  }

  if (i != object_table_count)
    abort ();                   /* object_table_count lied! */

  /* now call func on all of them */
  while (--i >= 0)
    (*func) (object_list[i]);

  /* free up the list */
  free ((void *) object_list);

  return object_table_count;
}