Logo Search packages:      
Sourcecode: lanmap version File versions  Download package

lhash.c

/* ex: set ts=4: */

#include <stdlib.h> /* NULL */
#include <assert.h>
#include <math.h>
#include <string.h>

#include "mem.h"
#include "debug.h"
#include "list.h"
#include "misc.h" /* vxstrcmp() */
#include "lhash.h"

/*
 * alloc/init new entry
 */
lhash_entry_t * lhash_entry_new(lhash_t *table, const void *key, const void *val)
{ 
      lhash_entry_t *entry;

#ifdef _DEBUG
      assert(NULL != table);
      assert(NULL != key);
      /* val may be NULL */
#endif

      if (NULL == (entry = xmalloc(sizeof(lhash_entry_t)))) {
            DEBUG(__FILE__, __LINE__, "could not allocate lhash_entry_t");
            return NULL;
      }

      /* copy key */
      if (NULL == table->func_key_copy) {
            entry->key = (void *)key; /* just save a pointer */
      } else {
            entry->key = (*(table->func_key_copy))((void *)key); /* use callback to copy key */
      }

      /* copy val */
      if (NULL == table->func_val_copy) {
            entry->val = (void *)val; /* just save a pointer */
      } else {
            entry->val = (*(table->func_val_copy))((void *)val); /* use callback to copy val */
      }

      return entry;
}

/*
 * add an entry to the hash table
 */
bool lhash_entry_add(lhash_t *table, list_t *list, lhash_entry_t *entry)
{
#ifdef _DEBUG
      assert(NULL != table);
      assert(NULL != list);
      assert(NULL != entry);
#endif

      /* remove list entry */
      if (NULL == list_append_ptr(list, (void *)entry)) {
            DEBUG(__FILE__, __LINE__, "list_append_ptr failed");
            return FALSE;
      }

      table->count++;

      return TRUE;
}

/*
 * remove an entry from an lhash
 */
bool lhash_entry_remove(lhash_t *table, list_t *list, list_node_t *node)
{
      lhash_entry_t *entry;

#ifdef _DEBUG
      assert(NULL != table);
      assert(NULL != list);
      assert(NULL != node);
#endif

      /* get lhash_entry_t from list_node_t */
      entry = list_node_data(node);
      if (NULL == entry) {
            DEBUG(__FILE__, __LINE__, "NULL data in node!");
            return FALSE;
      }

      /* free entry based on lhash rules */
      lhash_entry_free(table, entry);

      /* remove list entry */
      list_remove(list, node, NULL);

      table->count--;

      return TRUE;
}

/*
 * create an exact duplicate of an lhash_entry_t
 */
lhash_entry_t * lhash_entry_clone(lhash_t *dest_table, lhash_entry_t *orig)
{

      lhash_entry_t *clone;

#ifdef _DEBUG
      assert(NULL != dest_table);
      assert(NULL != orig);
#endif

      clone = lhash_entry_new(dest_table, orig->key, orig->val);
      if (NULL == clone) {
            DEBUG(__FILE__, __LINE__, "lhash_entry_new failed");
            return NULL;
      }

      return clone;
}


/*
 * free an lhash_entry_t and its key/val pair
 */
bool lhash_entry_free(lhash_t *table, lhash_entry_t *entry)
{

#ifdef _DEBUG
      assert(NULL != table);
      assert(NULL != entry);
#endif

      /* use callbacks to free key/val but not actual entry */
      /* NOTE: if callbacks are NULL, pointers are assumed to be pointing to things we don't "own" and don't need to free */

      /* free key, if necessary */
      if (NULL != table->func_key_free) {
            (*(table->func_key_free))((void *)entry->key); /* use callback to free key */
      }
      entry->key = NULL;

      /* free val, if necessary */
      if (NULL != table->func_val_free) {
            (*(table->func_val_free))((void *)entry->val); /* use callback to free val */
      }
      entry->val = NULL;

      xfree(entry);

      return TRUE;
}



/*
 * allocate and initialize a new lhash_t
 */
lhash_t * lhash_new(
      int unsigned slots, /* number of lists */
      int unsigned (*func_hash)(const void *), /* pointer to hashing function */
      int (*func_key_cmp)(const void *, const void *) /* pointer to comparison function */
){

      lhash_t *table;

#ifdef _DEBUG
      assert(NULL != func_hash);
      assert(NULL != func_key_cmp);
#endif
      
      /* allocate space for "header" */
      if (NULL == (table = xmalloc(sizeof(lhash_t)))) {
            DEBUG(__FILE__, __LINE__, "could not allocate lhash_t");
            return NULL;
      }

      if (TRUE != lhash_init(table, slots, func_hash, func_key_cmp)) {
            DEBUG(__FILE__, __LINE__, "lhash_init failed");
            return NULL;
      }

      return table;
}

/*
 * a simplified method of creating an lhash, just tell it how many items you expect to have
 * NOTE: keys must be char *
 */
lhash_t * lhash_new_ez(const int unsigned expected_items)
{
      int unsigned slots;

#ifdef _DEBUG
      assert(0 != expected_items);
#endif

      slots = expected_items;
      if (0 == slots)
            slots = 1; /* if it's production, let it slide... */
      slots = (int unsigned)ceil(sqrt(slots) * log(slots)); /* FIXME: test this method more closely */
#if 0
      slots = power_of_2_up(slots); /* round up */
#endif
      return lhash_new(slots, hash_func_DJB, lhash_cmp_str);
}


/*
 * initialize a malloced or statically initialized lhash
 */
bool lhash_init(
      lhash_t *table,
      int unsigned slots, /* number of lists */
      int unsigned (*func_hash)(const void *), /* pointer to hashing function */
      int (*func_key_cmp)(const void *, const void *) /* pointer to comparison function */
      )
{

#ifdef _DEBUG
      assert(NULL != table);
#endif

#if 0
      /* round slots up to the next power of 2 */
      if (slots < 2 || FALSE == is_a_power_of_2(slots)) {
#if 0
            DEBUGF(__FILE__, __LINE__, "rounding %d slots up...", slots);
#endif
            slots = power_of_2_up(slots);
      }
#endif

#if 0
      DEBUGF(__FILE__, __LINE__, "using %d slots...", slots);
#endif

      /* allocate space for slots */
      table->data = calloc(slots, sizeof(list_t));
      if (NULL == table->data) {
            DEBUGF(__FILE__, __LINE__, "could not allocate %d bytes for hash->data", sizeof(list_t) * slots);
            return FALSE;
      }
      memset(table->data, 0, slots * sizeof(list_t));

      /* NOTE: actual slot lists are initialized upon use, not creation. this saves memory and speed */

      /* at this point we've allocated all our memory */

      table->slots = slots;
      table->bitmask = slots - 1; /* bitmask of what to keep from indices */
      table->func_hash = func_hash;
      table->func_key_cmp = func_key_cmp;
      table->func_val_cmp = LHASH_FUNC_VAL_CMP_DEFAULT;
      /* copy/free callbacks are NULL by default */
      table->func_key_copy = NULL;
      table->func_key_free = NULL;
      table->func_val_copy = NULL;
      table->func_val_free = NULL;
      table->count = 0;

      return TRUE;
}

/*
 * E-Z initialization of already-allocated lhash
 */
bool lhash_init_ez(lhash_t *table, const int unsigned expected_items)
{
      int unsigned slots = expected_items;

#ifdef _DEBUG
      assert(NULL != table);
      assert(0 != expected_items);
#endif

      if (0 == slots)
            slots = 1; /* if it's production, let it slide... */
      slots = (int unsigned)ceil(sqrt(slots) * log(slots)); /* FIXME: test this method more closely */
#if 0
      slots = power_of_2_up(slots); /* round up */
#endif
      return lhash_init(table, slots, hash_func_DJB, lhash_cmp_str);
}


/*
 * set key copy/free callbacks in an lhash
 */
void lhash_set_key_funcs(lhash_t *table, void * (*func_key_copy)(void *), void (*func_key_free)(void *))
{
#ifdef _DEBUG
      assert(NULL != table);
      /* func_key_copy may be NULL */
      /* func_key_free may be NULL */
#endif
      table->func_key_copy = func_key_copy;
      table->func_key_free = func_key_free;
}

/*
 * set key cmp callback
 */
void lhash_set_key_func_cmp(lhash_t *table,
      int (*func_key_cmp)(const void *, const void *))
{
#ifdef _DEBUG
      assert(NULL != table);
      /* func_key_cmp may be NULL */
#endif
      table->func_key_cmp = func_key_cmp;
}


/*
 * set key copy callback in an lhash
 */
void lhash_set_key_func_copy(lhash_t *table, void * (*func_key_copy)(void *))
{
#ifdef _DEBUG
      assert(NULL != table);
      /* func_key_copy may be NULL */
#endif
      table->func_key_copy = func_key_copy;
}

/*
 * set key copy callback in an lhash
 */
void lhash_set_key_func_free(lhash_t *table, void (*func_key_free)(void *))
{
#ifdef _DEBUG
      assert(NULL != table);
      /* func_key_free may be NULL */
#endif
      table->func_key_free = func_key_free;
}

/*
 * set val copy/free callbacks in an lhash
 */
void lhash_set_val_funcs(lhash_t *table, void * (*func_val_copy)(void *), void (*func_val_free)(void *))
{
#ifdef _DEBUG
      assert(NULL != table);
      /* func_val_copy may be NULL */
      /* func_val_free may be NULL */
#endif
      table->func_val_copy = func_val_copy;
      table->func_val_free = func_val_free;
}

/*
 * set val cmp callback
 */
void lhash_set_val_func_cmp(lhash_t *table,
      int (*func_val_cmp)(const void *, const void *))
{
#ifdef _DEBUG
      assert(NULL != table);
      /* func_val_cmp may be NULL */
#endif
      table->func_val_cmp = func_val_cmp;
}

/*
 * set val copy callback in an lhash
 */
void lhash_set_val_func_copy(lhash_t *table, void * (*func_val_copy)(void *))
{
#ifdef _DEBUG
      assert(NULL != table);
      /* func_val_copy may be NULL */
#endif
      table->func_val_copy = func_val_copy;
}

/*
 * set val copy callback in an lhash
 */
void lhash_set_val_func_free(lhash_t *table, void (*func_val_free)(void *))
{
#ifdef _DEBUG
      assert(NULL != table);
      /* func_val_free may be NULL */
#endif
      table->func_val_free = func_val_free;
}

/*
 * free table entries and metadata
 */
bool lhash_destroy(lhash_t *table)
{
#ifdef _DEBUG
      assert(NULL != table);
#endif

      if (TRUE != lhash_delete_all(table)) {
            DEBUG(__FILE__, __LINE__,
                  "lhash_destroy() lhash_delete_all failed!");
            return FALSE;
      }

      /* free slots */
      xfree(table->data);

      /* reset values so we can re-init table if necessary */
      table->count = 0;
      table->slots = 0;
      table->bitmask = 0;
      table->func_hash = NULL;
      table->func_key_cmp = NULL;
      table->func_val_cmp = NULL;
      table->func_key_copy = NULL;
      table->func_key_free = NULL;
      table->func_val_copy = NULL;
      table->func_val_free = NULL;

      return TRUE;

}

/*
 * free an entire lhash_t from memory
 */
bool lhash_free(lhash_t *table)
{

#ifdef _DEBUG
      assert(NULL != table);
#endif

      if (FALSE == lhash_destroy(table)) {
            DEBUG(__FILE__, __LINE__, "lhash_destroy failed");
            return FALSE;
      }

      xfree(table);

      return TRUE;
}

/*
 * free an entire lhash_t from memory
 */
void lhash_free_cb(void *table)
{
#ifdef _DEBUG
      assert(NULL != table);
#endif
      (void)lhash_free(table);
}


/* returns non-zero if key exists */
bool lhash_key_exists(lhash_t *table, const void *key)
{
      list_t *list;
      list_node_t *node;

#ifdef _DEBUG
      assert(NULL != table);
      assert(NULL != key);
#endif

      node = lhash_key_to_node(table, &list, key);
      return ((NULL != node) ? TRUE : FALSE);
}

/* set a value at a certain key. if key exists, old value written over */
bool lhash_set(lhash_t *table, const void *key, const void *val)
{
      list_t *list = NULL;
      list_node_t *node;
      lhash_entry_t *entry;

#ifdef _DEBUG
      assert(NULL != table);
      assert(NULL != key);
      /* assert(NULL != val); FIXME: why not allow NULL vals? */
#endif

#if 0
      DEBUGF(__FILE__, __LINE__, "lhash_put(%p, %p, %p)", table, key, val);
#endif

      /* !!!FIXME!!! this function is broken when entry exists and is being
       * replaced and is at the end of a list! */
      
      /* create hash entry */
      entry = lhash_entry_new(table, (void *)key, (void *)val);
      if (NULL == entry) {
            DEBUG(__FILE__, __LINE__, "lhash_entry_new failed");
            return FALSE;
      }

      /* does key already exist? */
      node = lhash_key_to_node(table, &list, key);
      if (NULL == list) { /* list at this index does not yet exist, key definately doesn't exist */
            int unsigned index;
            index = lhash_key_to_index(table, key); /* figure out where the list is going */
            if (index >= table->slots) {
                  DEBUGF(__FILE__, __LINE__, "lhash_key_to_index returned invalid index (%d)", index);
                  return FALSE;
            }
            table->data[index] = list_new(); /* create list */
            if (NULL == table->data[index]) { /* list creation failed */
                  DEBUGF(__FILE__, __LINE__, "list_new failed at table->data[%d]", index);
                  return FALSE;
            }
            list = table->data[index];
            /* list was set up */
      } else { /* list was not NULL, maybe key exists... */
            if (NULL != node) { /* key already exists, remove it */
                  /* don't care about return val */

#if 0
                  DEBUGF(__FILE__, __LINE__, "removing key '%s' from lhash_t(%p)...",
                        (char *)key, table);
                  lhash_dump(table);
#endif

                  lhash_entry_remove(table, list, node);
            }
      }

      return lhash_entry_add(table, list, entry);
}

/* apply a single value to all keys in the hash */
bool lhash_set_all(lhash_t *table, const void *val)
{
      lhash_each_t each;
      lhash_entry_t *entry;

#ifdef _DEBUG
      assert(NULL != table);
#endif

      lhash_each_reset(&each, table);

      while (NULL != (entry = lhash_next(&each))) {
            entry = list_node_data(each.curr_node);
            if (NULL == entry) {
                  DEBUG(__FILE__, __LINE__, "NULL entry!");
                  continue;
            }
            /* NOTE: this could be optimized by replacing lhash_set() with a subset
             * of what lhash_set() does, but screw it*/
            lhash_set(table, entry->key, val);
      }

      return TRUE;
}

/*
 * returns a pointer to val stored at location 'key', or NULL if key does not exist
 */
/* NOTE: val can be set to NULL so a return value of NULL doesn't mean the key doesn't exist. see lhash_key_exists() */
void * lhash_get(lhash_t *table, const void *key)
{
      list_t *list = NULL;
      list_node_t *node;
      lhash_entry_t *entry;

#ifdef _DEBUG
      assert(NULL != table);
      assert(NULL != key);
#endif

      node = lhash_key_to_node(table, &list, key);
      if (NULL == node) { /* key doesn't exist */
            return NULL;
      }

      entry = list_node_data(node);
      if (NULL == entry) { /* shouldn't happen */
            DEBUG(__FILE__, __LINE__, "entry is NULL!");
      }

      return entry->val;
}

/*
 * performs an 'lhash_get' using supplied callback instead of func_key_cmp
 */
void * lhash_get_cb(lhash_t *table, const void *key, int (*cmp)(const void *, const void *))
{
      int (*save_func_key_cmp)(const void *, const void *);
      void *ret;

#ifdef _DEBUG
      assert(NULL != table);
      assert(NULL != key);
      assert(NULL != cmp);
#endif

      /* store real func_key_cmp */
      save_func_key_cmp = table->func_key_cmp;
      /* temporarily override func_key_cmp */
      table->func_key_cmp = cmp;

      /* perform get */
      ret = lhash_get(table, key);

      /* restore func_key_cmp */
      table->func_key_cmp = save_func_key_cmp;

      return ret;
}

/* remove key from hash */
bool lhash_delete(lhash_t *table, const void *key)
{
      list_t *list = NULL;
      list_node_t *node = NULL;

#ifdef _DEBUG
      assert(NULL != table);
      assert(NULL != key);
#endif

      /* if key exists, remove it */
      node = lhash_key_to_node(table, &list, key);
      if (NULL == node || NULL == list) {
            /* wasn't found in the list */
            return FALSE;
      }

      /* remove entry */
      if (TRUE != lhash_entry_remove(table, list, node)) {
            DEBUG(__FILE__, __LINE__, "lhash_entry_remove failed");
            return FALSE;
      }

      /* FIXME: broken */
#if 0
      /* is list in this slot empty? if so, delete it */
      if (0 == list_size(list)) {
            int unsigned slot = lhash_key_to_index(table, key);
            if (slot >= table->slots) {
                  DEBUGF(__FILE__, __LINE__, "lhash_key_to_index returned bogus slot (%d)", slot);
                  return FALSE;
            }
            list_free(table->data[slot], NULL);
            table->data[slot] = NULL;
      }
#endif

      return TRUE;
}

/*
 * delete all k=>v pairs from a table without altering its structure
 */
bool lhash_delete_all(lhash_t *table)
{     
      int unsigned index;

#ifdef _DEBUG
      assert(NULL != table);
#endif

      /* free all lists */
      for (index = 0; index < table->slots; index++) {
            if (NULL != table->data[index]) {
                  /* free lhash entries from list data */
                  list_node_t *node;
                  for (
                        node = list_first(table->data[index]);
                        node != NULL;
                        node = list_node_next(node)
                  ) {
                        lhash_entry_t *entry = list_node_data(node);
                        if (NULL == entry) { /* error, NULL entry */
                              DEBUG(__FILE__, __LINE__, "NULL entry found");
                              continue;
                        }
                        if (TRUE != lhash_entry_free(table, entry)) {
                              DEBUG(__FILE__, __LINE__,
                                    "lhash_delete_all lhash_entry_free failed");
                        }
                  }
                  /* free the actual list once we've freed its entries */
                  if (TRUE != list_free(table->data[index], NULL)) {
                        DEBUGF(__FILE__, __LINE__,
                              "lhash_delete_all list_free failed on slot %u", index);
                  }
                  table->data[index] = NULL;
            }
      }

      return TRUE;
}

/********************** each/next/reset; iteration! *************************/

/* reset 'each' to the first spot in the table in preparation for traversing a
 * table's keys */
bool lhash_each_reset(lhash_each_t *each, lhash_t *table)
{

#ifdef _DEBUG
      assert(NULL != table);
      assert(NULL != each);
#endif

      each->table = table;
      each->curr_slot = 0;
      each->curr_node = NULL;
      each->done = FALSE;

      return TRUE;
}

/* retrieve next key/val pair from hash */
lhash_entry_t * lhash_next(lhash_each_t *each)
{
      bool newlist = FALSE;

#ifdef _DEBUG
      assert(NULL != each);
      assert(NULL != each->table);
      assert(NULL != each->table->data);
#endif

      /* don't allow this to be run against a set that's already finished...
       & force programmer to reset */
      if (TRUE == each->done) {
            PROGRAMMER_OOPS(__FILE__, __LINE__,
                  "you need to call lhash_each_reset before iterating again");
            return NULL;
      }

      /* if we're already on a node... */
      if (NULL != each->curr_node) {
            each->curr_node = list_node_next(each->curr_node); /* advance once */
            if (NULL == each->curr_node) { /* did we run out of items? */
                  each->curr_slot++; /* advance to next slot... even we're on the last. we check below */
                  newlist = TRUE; /* we're switching lists */
            } else { /* we successfully advanced to next non-NULL entry, cya! */
                  return list_node_data(each->curr_node);
            }
      }

      if (NULL == each->curr_node)
            newlist = TRUE; /* moved to a new list */

      /* it's either our initial seek or we ran off the end of a list... */

      /* find next non-NULL slot if we're on one */
      while (
            each->curr_slot < lhash_slots(each->table)
            && NULL == each->table->data[each->curr_slot]
      ) {
            each->curr_slot++;
      }

      /* did we run out of slots looking? */
      if (each->curr_slot >= lhash_slots(each->table)) {
            each->done = TRUE; /* stick a fork in us! */
            return NULL;
      }

      /* we didn't run out of slots, slot must not be NULL */

      if (TRUE == newlist) { /* switched lists, set to first */
            each->curr_node = list_first(each->table->data[each->curr_slot]);
      }

      return list_node_data(each->curr_node);
}

/***************************************************************************/

/*
 * return >0 if a>b, 0 if eq, <0 if b>a
 * NOTE: we can't do a "HARD" comparison, because these hash tables could
 * have differing slots and/or hashing functions but still contain exactly
 * the same data
 */
int lhash_cmp(lhash_t *a, lhash_t *b)
{
      /* tolerate NULLs, just to be friendly */
      if (NULL == a) {
            if (NULL == b) {
                  return 0;
            } else {
                  return -1;
            }
      } else if (NULL == b) {
            return 1;
      }
      /* ok, neither is NULL */

      /* NOTE: ensure both hashes use the same func_val_cmp; we can't
       * examine hashes storing different types of data */
      if (a->func_val_cmp != b->func_val_cmp) {
            PROGRAMMER_OOPS(__FILE__, __LINE__,
                  "why are you comparing different types of lhash_ts?");
            return -696969;
      }

      if (lhash_size(a) != lhash_size(b)) {
            return lhash_size(a) - lhash_size(b);
      }
      /* ok, same number of items */

      { /* examine each entry */
            lhash_each_t ae;
            lhash_entry_t *entry;

            lhash_each_reset(&ae, a);

            while (NULL != (entry = lhash_next(&ae))) {
                  if (TRUE != lhash_key_exists(b, lhash_entry_key(entry))) {
                        return 1;
                  } else if (0 !=
                        (*a->func_val_cmp)(lhash_entry_val(entry),
                              lhash_get(b, lhash_entry_key(entry)))
                  ) {
                        return 1;
                  }
            }
            /* well shoot, they's equal! */
      }

      return 0;
}

/******************* apply to all members methods ***************************/

/*
 * apply a function to each member in an lhash
 */
bool lhash_map(lhash_t *table, void (*func)(lhash_entry_t *))
{
      list_node_t *node;
      lhash_entry_t *entry;
      int unsigned curr_list;

#ifdef _DEBUG
      assert(NULL != table);
      assert(NULL != func);
#endif

      for (curr_list = 0; curr_list < lhash_slots(table); curr_list++) {
            if (NULL == table->data[curr_list]) /* slots may not be initialized */
                  continue;
            for (node = list_first(table->data[curr_list]); node != NULL; node = list_node_next(node)) {
                  entry = (lhash_entry_t *)list_node_data(node);
                  if (NULL == entry) {
                        continue;
                  }
                  (*func)(entry); /* pass entry to callback */
            }
      }

      return TRUE;
}

/*
 * apply a function to each member in an lhash
 */
bool lhash_map_data(lhash_t *table, void (*func)(void *))
{
      list_node_t *node;
      lhash_entry_t *entry;
      int unsigned curr_list;

#ifdef _DEBUG
      assert(NULL != table);
      assert(NULL != func);
#endif

      for (curr_list = 0; curr_list < lhash_slots(table); curr_list++) {
            if (NULL == table->data[curr_list]) /* slots may not be initialized */
                  continue;
            for (node = list_first(table->data[curr_list]); node != NULL; node = list_node_next(node)) {
                  entry = (lhash_entry_t *)list_node_data(node);
                  if (NULL == entry) {
                        continue;
                  }
                  (*func)(entry->val); /* pass entry to callback */
            }
      }

      return TRUE;
}

/*
 * return a list of pointers to all keys in hash table
 */
list_t * lhash_keys(lhash_t *table)
{
      list_t *keys;
      list_node_t *node;
      lhash_entry_t *entry;
      int unsigned slot;

#ifdef _DEBUG
      assert(NULL != table);
#endif

      keys = list_new();
      if (NULL == keys) {
            DEBUG(__FILE__, __LINE__, "could not create list");
            return NULL;
      }

      for (slot = 0; slot < lhash_slots(table); slot++) {
            if (NULL == table->data[slot]) /* slots may not be initialized */
                  continue;
            for (node = list_first(table->data[slot]); node != NULL; node = list_node_next(node)) {
                  entry = list_node_data(node);
                  if (NULL == entry)
                        continue;
                  if (NULL == list_append_ptr(keys, (void *)entry->key)) {
                        DEBUG(__FILE__, __LINE__, "could not append key to list");
                        list_free(keys, NULL);
                        return NULL;
                  }
            }
      }

      return keys;
}

/*
 * returns an lhash of all items in an lhash for which the 'func' callback returns true
 */
lhash_t * lhash_filter(lhash_t *table, bool (*func)(lhash_entry_t *))
{
      lhash_t *results;
      list_node_t *node;
      lhash_entry_t *entry;
      int unsigned curr_list;

#ifdef _DEBUG
      assert(NULL != table);
      assert(NULL != func);
#endif

      /* our results lhash; clone settings from existing */
      results = lhash_new(table->slots, table->func_hash, table->func_key_cmp);
      if (NULL == results) {
            DEBUG(__FILE__, __LINE__, "lhash_new failed");
            return NULL;
      }

      for (curr_list = 0; curr_list < lhash_slots(table); curr_list++) {
            if (NULL == table->data[curr_list]) /* slots may not be initialized */
                  continue;
            for (node = list_first(table->data[curr_list]); node != NULL; node = list_node_next(node)) {
                  entry = (lhash_entry_t *)list_node_data(node);
                  if (TRUE == (*func)(entry)) {
                        lhash_set(results, entry->key, entry->val);
                  }
            }
      }

      return results;
}

/*
 * translate a key into a slot
 */
int unsigned lhash_key_to_index(lhash_t *table, const void *key)
{
      int unsigned index;

#ifdef _DEBUG
      assert(NULL != table);
      assert(NULL != key);
#endif

      index = (((table->func_hash)(key)) & table->bitmask);
      if (index > table->slots) {
            DEBUGF(__FILE__, __LINE__, "hash function error: index %d is larger than hash slots", index);
            return table->slots; /* return invalid value! */
      }

      return index;
}

/*
 * translate a key into a node
 */
list_node_t * lhash_key_to_node(lhash_t *table, list_t **list, const void *key)
{

      int unsigned index;

#ifdef _DEBUG
      assert(NULL != table);
            assert(NULL != table->data);
            assert(NULL != table->func_hash);
            assert(NULL != table->func_key_cmp);
      assert(NULL != list);
      assert(NULL != key);
#endif

#if 0
      DEBUGF(__FILE__, __LINE__, "lhash_key_to_node() key=\"%s\"", (char *)key);
#endif

      /* calculate hash and pull off the applicable bits */
      index = ((table->func_hash)(key) & table->bitmask);
      if (index >= table->slots) {
            DEBUGF(__FILE__, __LINE__, "lhash_key_to_node() hash_func returned bogus index! (%d)", index);
            return NULL;
      }

#if 0
      DEBUGF(__FILE__, __LINE__, "lhash_key_to_node() index: %d", index);
#endif

      *list = table->data[index];
      if (NULL == *list) {
            return NULL; /* slot uninitialized, key doesn't exist */
      }

#if 0
      DEBUGF(__FILE__, __LINE__, "lhash_key_to_node: key: %s, index: %d, size of list: %d",
            (char *)key, index, list_size(*list));
#endif

      /* search list in this index for key */
      {
            lhash_entry_t *entry;
            list_node_t *node;

            for (node = list_first(*list); node != NULL; node = list_node_next(node)) {
                  entry = list_node_data(node);
                  if (NULL == entry) {
                        DEBUGF(__FILE__, __LINE__, "NULL data found in list [%d]", index);
                        continue;
                  }
                  if (0 == (table->func_key_cmp)(key, entry->key)) {
                        return node;
                  }
            }
      }

      /* list exhausted, item not found */
      return NULL;
}

/*
 * default cmp method for lhash_new_ez, which assumes char * keys
 */
int lhash_cmp_str(const void *a, const void *b)
{
#if 0
      DEBUGF(__FILE__, __LINE__, "lhash_cmp_str(\"%s\", \"%s\")",
            (char *)a, (char *)b);
#endif
      return vxstrcmp((void *)a, (void *)b);
}

/*
 * dump table to stdout
 */
/* FIXME: assumes keys are char *! */
void lhash_dump(lhash_t *table)
{

#ifdef _DEBUG
      assert(NULL != table);
#endif

      /* print metadata */
      PRINTF(
            "lhash_t(%p){\n"
            "\tslots: %d\n"
            "\tcount: %d\n"
            "\tbitmask: 0x%08x\n"
            "\tfunc_hash: %p\n"
            "\tfunc_key_cmp: %p\n"
            "\tfunc_key_copy: %p\n"
            "\tfunc_key_free: %p\n"
            "\tfunc_val_cmp: %p\n"
            "\tfunc_val_copy: %p\n"
            "\tfunc_val_free: %p\n"
            "\tdata(%p){",
            table,
            table->slots,
            table->count,
            table->bitmask,
            table->func_hash,
            table->func_key_cmp,
            table->func_key_copy,
            table->func_key_free,
            table->func_val_cmp,
            table->func_val_copy,
            table->func_val_free,
            table->data
      );

      {
            int unsigned i;
            list_node_t *node;
            lhash_entry_t *entry;
      
            /* dump data */
            for (i = 0; i < table->slots; i++) {
                  PRINTF("\n\t\t[%d](%d)-|",
                        i, (NULL == table->data[i] ? 0 : list_size(table->data[i])));
                  if (NULL != table->data[i]) {
                        for (
                              node = list_first(table->data[i]);
                              NULL != node;
                              node = list_node_next(node)
                        ) {
                              entry = list_node_data(node);
                              if (NULL == entry) {
                                    DEBUGF(__FILE__, __LINE__, "NULL entry found in slot [%d]", i);
                                    continue;
                              }
                              PRINTF("[%s]-|", (NULL == entry ? NULL : (char *)(entry->key)));
                        }
                  }
            }
      }

      PRINTF("\n\t}\n}\n");
}


Generated by  Doxygen 1.6.0   Back to index