/* associative.c:
 *
 ****************************************************************
 * Copyright (C) 2003 Tom Lord
 *
 * See the file "COPYING" for further information about
 * the copyright and warranty status of this work.
 */


#include "hackerlab/hash/hashtree.h"
#include "hackerlab/hash/hash-utils.h"
#include "hackerlab/char/str.h"
#include "libawk/associative.h"


/* __STDC__ prototypes for static functions */
static t_ulong hash_key (t_uchar * key);
static int str_key_eq (void * va, void * vb, struct hashtree_rules * r);
static void pointer_map_hashfree_fn (struct hashtree_item * it, struct hashtree_rules * rules);



static struct hashtree_rules assoc_rules = { str_key_eq, 0, 0, 0, 0, 0 };
struct hashtree_breakaround {
    struct hashtree_rules rules;
    void (*free) (void *);
};


/************************************************************************
 *(h1 "Associative Tables")
 * 
 * Tla makes heavy use of a simple data structure for storing an
 * associative array of keys and value which are string: the
 * `assoc_table' type.
 * 
 * In general, these functions will cause the process to exit with 
 * non-0 status and a error message to the standard error descriptor
 * if an allocation failure occurs.
 */
/*(menu)
 */


/************************************************************************
 *(h1 "Associative Table Types")
 * 
 * Associative tables should be declared to be of type `assoc_table' and
 * initialized to 0, as in:
 *  
 *    assoc_table assoc = 0;
 */

/*(c assoc_table :category type)
 * typedef <unspecified> assoc_table;
 * 
 * An associative table.   Although the definition of the typedef
 * is unspecified, `assoc_table' values should be initialized to 0.
 */


/************************************************************************
 *(h1 "Associative Table Functions")
 * 
 */

static void free (void *foo)
{
    lim_free (0, foo);
}

/*(c assoc_set)
 * void assoc_set (assoc_table * table,
 *                 t_uchar const * key,
 *                 t_uchar const * value);
 * 
 * Record a binding of `key' to `value' in `*table'.
 * 
 * The value of `*table' might change as a result.
 * 
 * New copies of `key' and `value' are allocated for the
 * table.
 */
void
assoc_set (assoc_table * vtable,
           t_uchar const * key,
           t_uchar const * value)
{
  pointer_map_insert ((pointer_map *)vtable, key, str_save (0, value), free);
}

/**
 * \brief insert a value into a mapping
 *
 * the value of mapping may change as a result
 * \param key - copied if needed
 * \param value the value to insert - ownership is transferred
 */
void
pointer_map_insert (pointer_map * vtable,
           t_uchar const * key,
           void * value,
	   void (*free_callback) (void *))
{
  struct hashtree * table;
  struct hashtree_item * item;

  table = *(struct hashtree **)vtable;

  if (!table)
    {
      table = hashtree_alloc (&assoc_rules);
      *vtable = (pointer_map)table;
    }

  item = hashtree_store (table, hash_key ((t_uchar *)key), (void *)key, &assoc_rules);
  if (item->key == key)
    {
      item->key = str_save (0, key);
    }

  if (item->binding)
    free_callback (item->binding);

  item->binding = value;
}


/*(c assoc_ref)
 * t_uchar * assoc_ref (assoc_table table,
 *                      t_uchar * key);
 * 
 * Return the value (if any, 0 otherwise) associated
 * with `key' in `table'.
 * 
 * The value retured is _not_ newly allocated.  Callers 
 * should neither free the value, nor presume that it 
 * will remain value after later `assoc_set' or `assoc_del'
 * operations on this table.
 */
t_uchar *
assoc_ref (assoc_table vtable,
           t_uchar const * key)
{
    return pointer_map_find ((pointer_map) vtable, key);
}

/**
 * \brief find a pointer in a map
 * \return NULL on failure (or if the pointer is NULL - don't put NULL in ;)
 */
void *
pointer_map_find (pointer_map vtable, t_uchar const * key)
{
  struct hashtree * table;
  struct hashtree_item * item;

  table = (struct hashtree *)vtable;

  if (!table)
    return 0;

  item = hashtree_find (table, hash_key ((t_uchar *)key), (void *)key, &assoc_rules);

  if (!item)
    return 0;

  return item->binding;
}


/*(c assoc_del)
 * void assoc_del (assoc_table table,
 *                 t_uchar * key);
 * 
 * Remove the binding of `key' (if any) in `table'.
 */
void
assoc_del (assoc_table vtable,
           t_uchar * key)
{
    pointer_map_remove ((pointer_map) vtable, key, free);
}

/**
 * \brief remove a mapping
 */
void
pointer_map_remove (pointer_map vtable, t_uchar const * key, void (*free_callback) (void *))
{
  struct hashtree * table;
  struct hashtree_item * item;

  table = (struct hashtree *)vtable;

  if (!table)
    return;

  item = hashtree_find (table, hash_key ((t_uchar *)key), (void *)key, &assoc_rules);

  if (!item)
    return;

  if (item->key)
    lim_free (0, item->key);

  if (item->binding)
    free_callback (item->binding);

  hashtree_delete (item, &assoc_rules);
}


/*(c free_assoc_table)
 * void free_assoc_table (assoc_table table);
 * 
 * Free all storage associated with `table'.
 */
void
free_assoc_table (assoc_table table)
{
    pointer_map_free ((pointer_map) table, free);
}

/**
 * \brief free a map, calling free_callback on each pointer
 */
void
pointer_map_free (pointer_map table, void (*callback) (void *))
{
  struct hashtree_breakaround breakaround;
  breakaround.rules = assoc_rules;
  breakaround.free = callback;
  if (table)
    hashtree_free ((struct hashtree *)table, pointer_map_hashfree_fn, &breakaround.rules);
}




static t_ulong
hash_key (t_uchar * key)
{
 /* From GNU Emacs via Stephen Turnbull.   Fair use?
  * (GPL, anyway....)
  */
  t_uchar c;
  t_ulong hash;

  hash = 0;

  if (!key)
    return 0xde7a115L;

  while (*key)
    {
      c = *key;
      ++key;

      if (c >= 0140)
        c -= 40;                /* I dunno why either -tl */

      hash = ((hash << 3) + (hash >> 28) + c);
    }

  return hash;
}


static int
str_key_eq (void * va, void * vb, struct hashtree_rules * r)
{
  t_uchar * a;
  t_uchar * b;

  a = (t_uchar *)va;
  b = (t_uchar *)vb;

  return !str_cmp (a, b);
}

static void
pointer_map_hashfree_fn (struct hashtree_item * it, struct hashtree_rules * rules)
{
  struct hashtree_breakaround *breakaround = (struct hashtree_breakaround *)rules;
  if (it->key)
    lim_free (0, it->key);
  breakaround->free (it->binding);
}

struct intersection_state
{
    assoc_table right;
    rel_table answer;
};

static void
assoc_visit_intersection (struct hashtree_item * it,
			  void *user_data,
			  struct hashtree_rules * rules)
{
    struct intersection_state *state = (struct intersection_state *) user_data;
    if (assoc_ref (state->right, it->key))
      {
	rel_add_records (&state->answer, rel_make_record (it->key, 0), 0);
      }
}

rel_table
assoc_intersection(assoc_table left, assoc_table right)
{
    struct hashtree *h_left;
    struct intersection_state state;
    h_left = (struct hashtree *)left;
    state.right = right;
    state.answer = 0;
    hashtree_fold (h_left, assoc_visit_intersection, &state, &assoc_rules);
    return state.answer;
}


/* tag: Tom Lord Mon May  5 17:29:01 2003 (associative.c)
 */