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

hash.c

/* Handle a hash table.
 */

#include <stdlib.h>
#include <jmp.h>

struct hashnode
{
    void              *el;
    struct hashnode   *next;
};
typedef struct hashnode    hashnode;

struct hashtab
{
    size_t           size;      /** size of table */
    size_t           cardinal;  /** number of elements in hashtable */
    jmphash_f        hashfun;   /** Hash function used. */
    jmphash_cmp_f    cmp;       /** Comparison function used. */
    hashnode       **vec;       /** The table */
    hashnode        *next_free; /** next free hash node. */
    JVMPI_RawMonitor monitor;   /** The monitor for multi threaded access. */
};

#define HASH(tab, el) \
  ((tab)->hashfun (el, (tab)->size))

/** Good sizes of the hash table.
 *  primes, doubling in size so if we need to restructure 
 *  we know that (aprox) half of it is used...
 */
static unsigned long   primes[] =
{ 11UL, 23UL, 47UL, 97UL, 197UL, 307UL,
  617UL, 1237UL, 2477UL, 4957UL, 9923UL,
  19853UL, 39709UL, 79423UL, 158849UL,
  317701UL, 635413UL, 1270849UL,
  2541701UL, 5083423UL };

static size_t
make_prime (
    size_t   num)
{
    int      i;

    for (i = 0;
         i < sizeof (primes) / sizeof (int)
           && primes[i] < num;
         ++i)
        ;
    if (i < sizeof (primes) / sizeof (int))
        return primes[i];
    else
        return num;
}


static hashtab *
jmphash_new_internal (size_t size, jmphash_f hashfun, 
                  jmphash_cmp_f cmp, int new_monitor, 
                  char* name) {
    hashtab *htab;

    size = make_prime (size);
  
    if ((htab = (hashtab *)malloc(sizeof(*htab))) == NULL) {
      return NULL;
    }

    if ((htab->vec = (hashnode **)calloc(size, sizeof(hashnode *))) == NULL) {
      free (htab);
      return NULL;
    }

    htab->size = size;
    htab->cardinal = 0;
    htab->hashfun = hashfun;
    htab->cmp = cmp;
    htab->next_free = NULL;

    if (new_monitor) {
      char buf[64];
      snprintf(buf, 64, "%s_hashtab %p", name, htab);
      /* XXX Do we need to strdup this? */
      htab->monitor = jmp_create_monitor (buf);
    } else {
      htab->monitor = NULL;
    }
    return htab;
}

hashtab *
jmphash_new (size_t size, jmphash_f hashfun, jmphash_cmp_f cmp, char* name) {
    return jmphash_new_internal (size, hashfun, cmp, 1, name);
}

static hashnode* new_node (hashtab *table) {
    if (table->next_free) {
      hashnode *toreturn = table->next_free;
      table->next_free = toreturn->next;
      return toreturn;
    }
    return (hashnode*) malloc (sizeof (hashnode));
}

static void free_node (hashtab *table, hashnode *node)
{
    node->next = table->next_free;
    table->next_free = node;
}

void
jmphash_free (
    hashtab    *htab) {
    size_t      i;
    hashnode   *cur;
    hashnode   *next;

    for (i = 0; i < htab->size; ++i) {
        cur = htab->vec[i];
        while (cur != NULL) {
            next = cur->next;
            free (cur);
            cur = next;
        }
    }
    cur = htab->next_free;
    while (cur != NULL) {
      next = cur->next;
      free (cur);
      cur = next;
    }
    free (htab->vec);
    jmp_delete_monitor (htab->monitor);
    free (htab);
}

void 
jmphash_clear (
    hashtab   *htab) {
    size_t      i;
    hashnode   *cur;
    hashnode   *next;

    for (i = 0; i < htab->size; ++i) {
        cur = htab->vec[i];
        while (cur != NULL) {
            next = cur->next;
            free_node (htab, cur);
            cur = next;
        }
      htab->vec[i] = NULL;
    }    
    htab->cardinal = 0;
}


static void
restructure (hashtab *htab) {
    hashtab *ntab = NULL;
    hashnode *cur;
    hashnode **tmpvec;
    size_t i;
    int factor;
    size_t tmpsize;
  
    for (factor = 8; ntab == NULL && factor > 1; factor /= 2) {
      ntab = jmphash_new_internal (factor * htab->size,
                             htab->hashfun,
                             htab->cmp,
                             0, 
                             NULL);
    }

    if (ntab == NULL) {
      return;
    }

    for (i = 0; i < htab->size; ++i) {
      cur = htab->vec[i];

      while (cur != NULL) {
          if (jmphash_insert(cur->el, ntab) != 0) {
            jmphash_free(ntab);
            return;
            }
          cur = cur->next;
        }
    }

    tmpvec = htab->vec;
    tmpsize = htab->size;
    htab->vec = ntab->vec;
    htab->size = ntab->size;
    /* The monitor stays with the orginal hashtab */
    ntab->vec = tmpvec;
    ntab->size = tmpsize;
    jmphash_free (ntab);
}


int
jmphash_insert (
    void       *el,
    hashtab    *htab) {
    size_t      i;
    hashnode   *hnode;

    if (htab == NULL) 
      return 0;
    
    ++htab->cardinal;
    if (htab->cardinal > htab->size * 10)
        restructure (htab);
    hnode = new_node(htab);
    if (hnode == NULL)
        return 1;
    
    i = HASH (htab, el);
    hnode->next = htab->vec[i];
    hnode->el = el;
    htab->vec[i] = hnode;
    return 0;
}

static hashnode **
find_elem (
    void        *el,
    hashtab     *htab) {
    hashnode   **hnode_p;
    
    hnode_p = &htab->vec[HASH (htab, el)];
    while ((*hnode_p != NULL) && (htab->cmp ((*hnode_p)->el, el)))
        hnode_p = &(*hnode_p)->next;
    return hnode_p;
}

void *
jmphash_search (
    void        *el,
    hashtab     *htab) {
    hashnode   **hnode_ptr;

    if (htab == NULL)
      return NULL;
    if (el == NULL) {
      return NULL;
    }
    hnode_ptr = find_elem (el, htab);
    if (*hnode_ptr == NULL)
        return NULL;
    else
        return (*hnode_ptr)->el;
}

void *
jmphash_remove (
    void        *el,
    hashtab     *htab) {
    hashnode   **hnode_ptr;
    hashnode    *remove;
    void        *ret_el;

    hnode_ptr = find_elem (el, htab);
    if (*hnode_ptr == NULL)
        return NULL;

    ret_el = (*hnode_ptr)->el;
    remove = *hnode_ptr;
    *hnode_ptr = (*hnode_ptr)->next;
    free_node (htab, remove);
    --htab->cardinal;

    return ret_el;
}

size_t
jmphash_cardinal (
    hashtab   *htab) {
    return htab->cardinal;
}

void
jmphash_for_each (
    jmphash_iter_f    proc,
    hashtab       *htab) {
    size_t         i;
    hashnode      *hnode;

    if (htab == NULL) {
      return;
    }

    for (i = 0; i < htab->size; ++i) {
        for (hnode = htab->vec[i];
             hnode != NULL;
             hnode = hnode->next) {
            proc (hnode->el);
        }
    }
}

void
jmphash_for_each_with_arg (
    jmphash_iter_fa   proc,
    hashtab       *htab,
    void          *data) {
    size_t         i;
    hashnode      *hnode;

    if (htab == NULL)
      return;

    for (i = 0; i < htab->size; ++i) {
        for (hnode = htab->vec[i];
             hnode != NULL;
             hnode = hnode->next) {
            proc (hnode->el, data);
        }
    }
}


void
jmphash_lock (hashtab *htab) {
    if (htab == NULL)
      return;
    jmp_lock_monitor (htab->monitor);
}


void
jmphash_unlock (hashtab *htab) {
    if (htab == NULL)
      return;
    jmp_unlock_monitor (htab->monitor);
}

JVMPI_RawMonitor jmphash_get_monitor (
    hashtab       *htab) {
    return htab->monitor;
}


/* Emacs Local Variables: */
/* Emacs mode:C */
/* Emacs c-indentation-style:"gnu" */
/* Emacs c-hanging-braces-alist:((brace-list-open)(brace-entry-open)(defun-open after)(substatement-open after)(block-close . c-snug-do-while)(extern-lang-open after)) */
/* Emacs c-cleanup-list:(brace-else-brace brace-elseif-brace space-before-funcall) */
/* Emacs c-basic-offset:4 */
/* Emacs End: */

Generated by  Doxygen 1.6.0   Back to index