X-Git-Url: https://pd.if.org/git/?p=jsw;a=blobdiff_plain;f=jsw_hlib.c;fp=jsw_hlib.c;h=6cc961ae791bebaa5f46d1f4c395d22e4c3c7e03;hp=e47927281023286a781bb452da2d50de780b87a1;hb=9fa959d28f32ae94111296c238b1e76caf152078;hpb=b8dc7e923f9cf71c3c722b872494fe639ba4621f

diff --git a/jsw_hlib.c b/jsw_hlib.c
index e479272..6cc961a 100644
--- a/jsw_hlib.c
+++ b/jsw_hlib.c
@@ -1,414 +1,414 @@
-/*
-  Hash table library using separate chaining
-
-    > Created (Julienne Walker): August 7, 2005
-    > Modified (Julienne Walker): August 11, 2005
-      Added a cast for malloc to enable clean
-      compilation as C++
-*/
-#include "jsw_hlib.h"
-
-#ifdef __cplusplus
-#include <cstdlib>
-
-using std::malloc;
-using std::free;
-#else
-#include <stdlib.h>
-#endif
-
-typedef struct jsw_node {
-  void            *key;  /* Key used for searching */
-  void            *item; /* Actual content of a node */
-  struct jsw_node *next; /* Next link in the chain */
-} jsw_node_t;
-
-typedef struct jsw_head {
-  jsw_node_t *first;     /* First link in the chain */
-  size_t      size;      /* Length of the chain */
-} jsw_head_t;
-
-struct jsw_hash {
-  jsw_head_t **table;    /* Dynamic chained hash table */
-  size_t       size;     /* Current item count */
-  size_t       capacity; /* Current table size */
-  size_t       curri;    /* Current index for traversal */
-  jsw_node_t  *currl;    /* Current link for traversal */
-  hash_f       hash;     /* User defined key hash function */
-  cmp_f        cmp;      /* User defined key comparison function */
-  keydup_f     keydup;   /* User defined key copy function */
-  itemdup_f    itemdup;  /* User defined item copy function */
-  keyrel_f     keyrel;   /* User defined key delete function */
-  itemrel_f    itemrel;  /* User defined item delete function */
-};
-
-static jsw_node_t *new_node ( void *key, void *item, jsw_node_t *next )
-{
-  jsw_node_t *node = (jsw_node_t *)malloc ( sizeof *node );
-
-  if ( node == NULL )
-    return NULL;
-
-  node->key = key;
-  node->item = item;
-  node->next = next;
-
-  return node;
-}
-
-static jsw_head_t *new_chain ( void )
-{
-  jsw_head_t *chain = (jsw_head_t *)malloc ( sizeof *chain );
-
-  if ( chain == NULL )
-    return NULL;
-
-  chain->first = NULL;
-  chain->size = 0;
-
-  return chain;
-}
-
-/*
-  Create a new hash table with a capacity of size, and
-  user defined functions for handling keys and items.
-
-  Returns: An empty hash table, or NULL on failure.
-*/
-jsw_hash_t  *jsw_hnew ( size_t size, hash_f hash, cmp_f cmp,
-  keydup_f keydup, itemdup_f itemdup,
-  keyrel_f keyrel, itemrel_f itemrel )
-{
-  jsw_hash_t *htab = (jsw_hash_t *)malloc ( sizeof *htab );
-  size_t i;
-
-  if ( htab == NULL )
-    return NULL;
-
-  htab->table = (jsw_head_t **)malloc ( size * sizeof *htab->table );
-
-  if ( htab->table == NULL ) {
-    free ( htab );
-    return NULL;
-  }
-
-  /* Empty chains have no head */
-  for ( i = 0; i < size; i++ )
-    htab->table[i] = NULL;
-
-  htab->size = 0;
-  htab->capacity = size;
-  htab->curri = 0;
-  htab->currl = NULL;
-  htab->hash = hash;
-  htab->cmp = cmp;
-  htab->keydup = keydup;
-  htab->itemdup = itemdup;
-  htab->keyrel = keyrel;
-  htab->itemrel = itemrel;
-
-  return htab;
-}
-
-/* Release all memory used by the hash table */
-void jsw_hdelete ( jsw_hash_t *htab )
-{
-  size_t i;
-
-  /* Release each chain individually */
-  for ( i = 0; i < htab->capacity; i++ ) {
-    jsw_node_t *save, *it;
-
-    if ( htab->table[i] == NULL )
-      continue;
-
-    it = htab->table[i]->first;
-
-    for ( ; it != NULL; it = save ) {
-      save = it->next;
-      htab->keyrel ( it->key );
-      htab->itemrel ( it->item );
-      free ( it );
-    }
-
-    free ( htab->table[i] );
-  }
-
-  /* Release the hash table */
-  free ( htab->table );
-  free ( htab );
-}
-
-/*
-  Find an item with the selected key
-
-  Returns: The item, or NULL if not found
-*/
-void *jsw_hfind ( jsw_hash_t *htab, void *key )
-{
-  unsigned h = htab->hash ( key ) % htab->capacity;
-
-  /* Search the chain only if it exists */
-  if ( htab->table[h] != NULL ) {
-    jsw_node_t *it = htab->table[h]->first;
-
-    for ( ; it != NULL; it = it->next ) {
-      if ( htab->cmp ( key, it->key ) == 0 )
-        return it->item;
-    }
-  }
-
-  return NULL;
-}
-
-/*
-  Insert an item with the selected key
-
-  Returns: non-zero for success, zero for failure
-*/
-int jsw_hinsert ( jsw_hash_t *htab, void *key, void *item )
-{
-  unsigned h = htab->hash ( key ) % htab->capacity;
-  void *dupkey, *dupitem;
-  jsw_node_t *new_item;
-
-  /* Disallow duplicate keys */
-  if ( jsw_hfind ( htab, key ) != NULL )
-    return 0;
-
-  /* Attempt to create a new item */
-  dupkey = htab->keydup ( key );
-  dupitem = htab->itemdup ( item );
-
-  new_item = new_node ( dupkey, dupitem, NULL );
-
-  if ( new_item == NULL )
-    return 0;
-
-  /* Create a chain if the bucket is empty */
-  if ( htab->table[h] == NULL ) {
-    htab->table[h] = new_chain();
-
-    if ( htab->table[h] == NULL ) {
-      htab->keyrel ( new_item->key );
-      htab->itemrel ( new_item->item );
-      free ( new_item );
-      return 0;
-    }
-  }
-
-  /* Insert at the front of the chain */
-  new_item->next = htab->table[h]->first;
-  htab->table[h]->first = new_item;
-
-  ++htab->table[h]->size;
-  ++htab->size;
-
-  return 1;
-}
-
-/*
-  Remove an item with the selected key
-
-  Returns: non-zero for success, zero for failure
-*/
-int jsw_herase ( jsw_hash_t *htab, void *key )
-{
-  unsigned h = htab->hash ( key ) % htab->capacity;
-  jsw_node_t *save, *it;
-
-  if ( htab->table[h] == NULL )
-    return 0;
-
-  it = htab->table[h]->first;
-
-  /* Remove the first node in the chain? */
-  if ( htab->cmp ( key, it->key ) == 0 ) {
-    htab->table[h]->first = it->next;
-
-    /* Release the node's memory */
-    htab->keyrel ( it->key );
-    htab->itemrel ( it->item );
-    free ( it );
-
-    /* Remove the chain if it's empty */
-    if ( htab->table[h]->first == NULL ) {
-      free ( htab->table[h] );
-      htab->table[h] = NULL;
-    }
-    else
-      --htab->table[h]->size;
-  }
-  else {
-    /* Search for the node */
-    while ( it->next != NULL ) {
-      if ( htab->cmp ( key, it->next->key ) == 0 )
-        break;
-
-      it = it->next;
-    }
-
-    /* Not found? */
-    if ( it->next == NULL )
-      return 0;
-
-    save = it->next;
-    it->next = it->next->next;
-
-    /* Release the node's memory */
-    htab->keyrel ( save->key );
-    htab->itemrel ( save->item );
-    free ( save );
-
-    --htab->table[h]->size;
-  }
-
-  /* Erasure invalidates traversal markers */
-  jsw_hreset ( htab );
-
-  --htab->size;
-
-  return 1;
-}
-
-/*
-  Grow or shrink the table, this is a slow operation
-  
-  Returns: non-zero for success, zero for failure
-*/
-int jsw_hresize ( jsw_hash_t *htab, size_t new_size )
-{
-  jsw_hash_t *new_htab;
-  jsw_node_t *it;
-  size_t i;
-
-  /* Build a new hash table, then assign it to the old one */
-  new_htab = jsw_hnew ( new_size, htab->hash, htab->cmp,
-    htab->keydup, htab->itemdup, htab->keyrel, htab->itemrel );
-
-  if ( new_htab == NULL )
-    return 0;
-
-  for ( i = 0; i < htab->capacity; i++ ) {
-    if ( htab->table[i] == NULL )
-      continue;
-
-    for ( it = htab->table[i]->first; it != NULL; it = it->next )
-      jsw_hinsert ( new_htab, it->key, it->item );
-  }
-
-  /* A hash table holds copies, so release the old table */
-  jsw_hdelete ( htab );
-  htab = new_htab;
-
-  return 1;
-}
-
-/* Reset the traversal markers to the beginning */
-void jsw_hreset ( jsw_hash_t *htab )
-{
-  size_t i;
-
-  htab->curri = 0;
-  htab->currl = NULL;
-
-  /* Find the first non-empty bucket */
-  for ( i = 0; i < htab->capacity; i++ ) {
-    if ( htab->table[i] != NULL )
-      break;
-  }
-
-  htab->curri = i;
-
-  /* Set the link marker if the table was not empty */
-  if ( i != htab->capacity )
-    htab->currl = htab->table[i]->first;
-}
-
-/* Traverse forward by one key */
-int jsw_hnext ( jsw_hash_t *htab )
-{
-  if ( htab->currl != NULL ) {
-    htab->currl = htab->currl->next;
-
-    /* At the end of the chain? */
-    if ( htab->currl == NULL ) {
-      /* Find the next chain */
-      while ( ++htab->curri < htab->capacity ) {
-        if ( htab->table[htab->curri] != NULL )
-          break;
-      }
-
-      /* No more chains? */
-      if ( htab->curri == htab->capacity )
-        return 0;
-
-      htab->currl = htab->table[htab->curri]->first;
-    }
-  }
-
-  return 1;
-}
-
-/* Get the current key */
-const void *jsw_hkey ( jsw_hash_t *htab )
-{
-  return htab->currl != NULL ? htab->currl->key : NULL;
-}
-
-/* Get the current item */
-void *jsw_hitem ( jsw_hash_t *htab )
-{
-  return htab->currl != NULL ? htab->currl->item : NULL;
-}
-
-/* Current number of items in the table */
-size_t jsw_hsize ( jsw_hash_t *htab )
-{
-  return htab->size;
-}
-
-/* Total allowable number of items without resizing */
-size_t jsw_hcapacity ( jsw_hash_t *htab )
-{
-  return htab->capacity;
-}
-
-/* Get statistics for the hash table */
-jsw_hstat_t *jsw_hstat ( jsw_hash_t *htab )
-{
-  jsw_hstat_t *stat;
-  double sum = 0, used = 0;
-  size_t i;
-
-  /* No stats for an empty table */
-  if ( htab->size == 0 )
-    return NULL;
-
-  stat = (jsw_hstat_t *)malloc ( sizeof *stat );
-
-  if ( stat == NULL )
-    return NULL;
-
-  stat->lchain = 0;
-  stat->schain = (size_t)-1;
-
-  for ( i = 0; i < htab->capacity; i++ ) {
-    if ( htab->table[i] != NULL ) {
-      sum += htab->table[i]->size;
-
-      ++used; /* Non-empty buckets */
-
-      if ( htab->table[i]->size > stat->lchain )
-        stat->lchain = htab->table[i]->size;
-
-      if ( htab->table[i]->size < stat->schain )
-        stat->schain = htab->table[i]->size;
-    }
-  }
-
-  stat->load = used / htab->capacity;
-  stat->achain = sum / used;
-
-  return stat;
-}
+/*
+  Hash table library using separate chaining
+
+    > Created (Julienne Walker): August 7, 2005
+    > Modified (Julienne Walker): August 11, 2005
+      Added a cast for malloc to enable clean
+      compilation as C++
+*/
+#include "jsw_hlib.h"
+
+#ifdef __cplusplus
+#include <cstdlib>
+
+using std::malloc;
+using std::free;
+#else
+#include <stdlib.h>
+#endif
+
+typedef struct jsw_node {
+  void            *key;  /* Key used for searching */
+  void            *item; /* Actual content of a node */
+  struct jsw_node *next; /* Next link in the chain */
+} jsw_node_t;
+
+typedef struct jsw_head {
+  jsw_node_t *first;     /* First link in the chain */
+  size_t      size;      /* Length of the chain */
+} jsw_head_t;
+
+struct jsw_hash {
+  jsw_head_t **table;    /* Dynamic chained hash table */
+  size_t       size;     /* Current item count */
+  size_t       capacity; /* Current table size */
+  size_t       curri;    /* Current index for traversal */
+  jsw_node_t  *currl;    /* Current link for traversal */
+  hash_f       hash;     /* User defined key hash function */
+  cmp_f        cmp;      /* User defined key comparison function */
+  keydup_f     keydup;   /* User defined key copy function */
+  itemdup_f    itemdup;  /* User defined item copy function */
+  keyrel_f     keyrel;   /* User defined key delete function */
+  itemrel_f    itemrel;  /* User defined item delete function */
+};
+
+static jsw_node_t *new_node ( void *key, void *item, jsw_node_t *next )
+{
+  jsw_node_t *node = (jsw_node_t *)malloc ( sizeof *node );
+
+  if ( node == NULL )
+    return NULL;
+
+  node->key = key;
+  node->item = item;
+  node->next = next;
+
+  return node;
+}
+
+static jsw_head_t *new_chain ( void )
+{
+  jsw_head_t *chain = (jsw_head_t *)malloc ( sizeof *chain );
+
+  if ( chain == NULL )
+    return NULL;
+
+  chain->first = NULL;
+  chain->size = 0;
+
+  return chain;
+}
+
+/*
+  Create a new hash table with a capacity of size, and
+  user defined functions for handling keys and items.
+
+  Returns: An empty hash table, or NULL on failure.
+*/
+jsw_hash_t  *jsw_hnew ( size_t size, hash_f hash, cmp_f cmp,
+  keydup_f keydup, itemdup_f itemdup,
+  keyrel_f keyrel, itemrel_f itemrel )
+{
+  jsw_hash_t *htab = (jsw_hash_t *)malloc ( sizeof *htab );
+  size_t i;
+
+  if ( htab == NULL )
+    return NULL;
+
+  htab->table = (jsw_head_t **)malloc ( size * sizeof *htab->table );
+
+  if ( htab->table == NULL ) {
+    free ( htab );
+    return NULL;
+  }
+
+  /* Empty chains have no head */
+  for ( i = 0; i < size; i++ )
+    htab->table[i] = NULL;
+
+  htab->size = 0;
+  htab->capacity = size;
+  htab->curri = 0;
+  htab->currl = NULL;
+  htab->hash = hash;
+  htab->cmp = cmp;
+  htab->keydup = keydup;
+  htab->itemdup = itemdup;
+  htab->keyrel = keyrel;
+  htab->itemrel = itemrel;
+
+  return htab;
+}
+
+/* Release all memory used by the hash table */
+void jsw_hdelete ( jsw_hash_t *htab )
+{
+  size_t i;
+
+  /* Release each chain individually */
+  for ( i = 0; i < htab->capacity; i++ ) {
+    jsw_node_t *save, *it;
+
+    if ( htab->table[i] == NULL )
+      continue;
+
+    it = htab->table[i]->first;
+
+    for ( ; it != NULL; it = save ) {
+      save = it->next;
+      htab->keyrel ( it->key );
+      htab->itemrel ( it->item );
+      free ( it );
+    }
+
+    free ( htab->table[i] );
+  }
+
+  /* Release the hash table */
+  free ( htab->table );
+  free ( htab );
+}
+
+/*
+  Find an item with the selected key
+
+  Returns: The item, or NULL if not found
+*/
+void *jsw_hfind ( jsw_hash_t *htab, void *key )
+{
+  unsigned h = htab->hash ( key ) % htab->capacity;
+
+  /* Search the chain only if it exists */
+  if ( htab->table[h] != NULL ) {
+    jsw_node_t *it = htab->table[h]->first;
+
+    for ( ; it != NULL; it = it->next ) {
+      if ( htab->cmp ( key, it->key ) == 0 )
+        return it->item;
+    }
+  }
+
+  return NULL;
+}
+
+/*
+  Insert an item with the selected key
+
+  Returns: non-zero for success, zero for failure
+*/
+int jsw_hinsert ( jsw_hash_t *htab, void *key, void *item )
+{
+  unsigned h = htab->hash ( key ) % htab->capacity;
+  void *dupkey, *dupitem;
+  jsw_node_t *new_item;
+
+  /* Disallow duplicate keys */
+  if ( jsw_hfind ( htab, key ) != NULL )
+    return 0;
+
+  /* Attempt to create a new item */
+  dupkey = htab->keydup ( key );
+  dupitem = htab->itemdup ( item );
+
+  new_item = new_node ( dupkey, dupitem, NULL );
+
+  if ( new_item == NULL )
+    return 0;
+
+  /* Create a chain if the bucket is empty */
+  if ( htab->table[h] == NULL ) {
+    htab->table[h] = new_chain();
+
+    if ( htab->table[h] == NULL ) {
+      htab->keyrel ( new_item->key );
+      htab->itemrel ( new_item->item );
+      free ( new_item );
+      return 0;
+    }
+  }
+
+  /* Insert at the front of the chain */
+  new_item->next = htab->table[h]->first;
+  htab->table[h]->first = new_item;
+
+  ++htab->table[h]->size;
+  ++htab->size;
+
+  return 1;
+}
+
+/*
+  Remove an item with the selected key
+
+  Returns: non-zero for success, zero for failure
+*/
+int jsw_herase ( jsw_hash_t *htab, void *key )
+{
+  unsigned h = htab->hash ( key ) % htab->capacity;
+  jsw_node_t *save, *it;
+
+  if ( htab->table[h] == NULL )
+    return 0;
+
+  it = htab->table[h]->first;
+
+  /* Remove the first node in the chain? */
+  if ( htab->cmp ( key, it->key ) == 0 ) {
+    htab->table[h]->first = it->next;
+
+    /* Release the node's memory */
+    htab->keyrel ( it->key );
+    htab->itemrel ( it->item );
+    free ( it );
+
+    /* Remove the chain if it's empty */
+    if ( htab->table[h]->first == NULL ) {
+      free ( htab->table[h] );
+      htab->table[h] = NULL;
+    }
+    else
+      --htab->table[h]->size;
+  }
+  else {
+    /* Search for the node */
+    while ( it->next != NULL ) {
+      if ( htab->cmp ( key, it->next->key ) == 0 )
+        break;
+
+      it = it->next;
+    }
+
+    /* Not found? */
+    if ( it->next == NULL )
+      return 0;
+
+    save = it->next;
+    it->next = it->next->next;
+
+    /* Release the node's memory */
+    htab->keyrel ( save->key );
+    htab->itemrel ( save->item );
+    free ( save );
+
+    --htab->table[h]->size;
+  }
+
+  /* Erasure invalidates traversal markers */
+  jsw_hreset ( htab );
+
+  --htab->size;
+
+  return 1;
+}
+
+/*
+  Grow or shrink the table, this is a slow operation
+  
+  Returns: non-zero for success, zero for failure
+*/
+int jsw_hresize ( jsw_hash_t *htab, size_t new_size )
+{
+  jsw_hash_t *new_htab;
+  jsw_node_t *it;
+  size_t i;
+
+  /* Build a new hash table, then assign it to the old one */
+  new_htab = jsw_hnew ( new_size, htab->hash, htab->cmp,
+    htab->keydup, htab->itemdup, htab->keyrel, htab->itemrel );
+
+  if ( new_htab == NULL )
+    return 0;
+
+  for ( i = 0; i < htab->capacity; i++ ) {
+    if ( htab->table[i] == NULL )
+      continue;
+
+    for ( it = htab->table[i]->first; it != NULL; it = it->next )
+      jsw_hinsert ( new_htab, it->key, it->item );
+  }
+
+  /* A hash table holds copies, so release the old table */
+  jsw_hdelete ( htab );
+  htab = new_htab;
+
+  return 1;
+}
+
+/* Reset the traversal markers to the beginning */
+void jsw_hreset ( jsw_hash_t *htab )
+{
+  size_t i;
+
+  htab->curri = 0;
+  htab->currl = NULL;
+
+  /* Find the first non-empty bucket */
+  for ( i = 0; i < htab->capacity; i++ ) {
+    if ( htab->table[i] != NULL )
+      break;
+  }
+
+  htab->curri = i;
+
+  /* Set the link marker if the table was not empty */
+  if ( i != htab->capacity )
+    htab->currl = htab->table[i]->first;
+}
+
+/* Traverse forward by one key */
+int jsw_hnext ( jsw_hash_t *htab )
+{
+  if ( htab->currl != NULL ) {
+    htab->currl = htab->currl->next;
+
+    /* At the end of the chain? */
+    if ( htab->currl == NULL ) {
+      /* Find the next chain */
+      while ( ++htab->curri < htab->capacity ) {
+        if ( htab->table[htab->curri] != NULL )
+          break;
+      }
+
+      /* No more chains? */
+      if ( htab->curri == htab->capacity )
+        return 0;
+
+      htab->currl = htab->table[htab->curri]->first;
+    }
+  }
+
+  return 1;
+}
+
+/* Get the current key */
+const void *jsw_hkey ( jsw_hash_t *htab )
+{
+  return htab->currl != NULL ? htab->currl->key : NULL;
+}
+
+/* Get the current item */
+void *jsw_hitem ( jsw_hash_t *htab )
+{
+  return htab->currl != NULL ? htab->currl->item : NULL;
+}
+
+/* Current number of items in the table */
+size_t jsw_hsize ( jsw_hash_t *htab )
+{
+  return htab->size;
+}
+
+/* Total allowable number of items without resizing */
+size_t jsw_hcapacity ( jsw_hash_t *htab )
+{
+  return htab->capacity;
+}
+
+/* Get statistics for the hash table */
+jsw_hstat_t *jsw_hstat ( jsw_hash_t *htab )
+{
+  jsw_hstat_t *stat;
+  double sum = 0, used = 0;
+  size_t i;
+
+  /* No stats for an empty table */
+  if ( htab->size == 0 )
+    return NULL;
+
+  stat = (jsw_hstat_t *)malloc ( sizeof *stat );
+
+  if ( stat == NULL )
+    return NULL;
+
+  stat->lchain = 0;
+  stat->schain = (size_t)-1;
+
+  for ( i = 0; i < htab->capacity; i++ ) {
+    if ( htab->table[i] != NULL ) {
+      sum += htab->table[i]->size;
+
+      ++used; /* Non-empty buckets */
+
+      if ( htab->table[i]->size > stat->lchain )
+        stat->lchain = htab->table[i]->size;
+
+      if ( htab->table[i]->size < stat->schain )
+        stat->schain = htab->table[i]->size;
+    }
+  }
+
+  stat->load = used / htab->capacity;
+  stat->achain = sum / used;
+
+  return stat;
+}