add zpm-search to look for packages and libraries

[zpackage] / lib / jsw / jsw_hlib.c

diff --git a/lib/jsw/jsw_hlib.c b/lib/jsw/jsw_hlib.c
index 6cc961ae791bebaa5f46d1f4c395d22e4c3c7e03..a43140538eb0cdce47da2d8ac214454be65e4bfb 100644 (file)
--- a/lib/jsw/jsw_hlib.c
+++ b/lib/jsw/jsw_hlib.c
@@ -6,16 +6,12 @@
       Added a cast for malloc to enable clean
       compilation as C++
 */
-#include "jsw_hlib.h"
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
 
-#ifdef __cplusplus
-#include <cstdlib>
+#include "jsw_hlib.h"
 
-using std::malloc;
-using std::free;
-#else
-#include <stdlib.h>
-#endif
 
 typedef struct jsw_node {
   void            *key;  /* Key used for searching */
@@ -42,9 +38,28 @@ struct jsw_hash {
   itemrel_f    itemrel;  /* User defined item delete function */
 };
 
+static unsigned int default_hash(const void *key) {
+       const unsigned char *p = key;
+       unsigned h = 0;
+       int i;
+       int len = strlen((char *)p);
+
+       for (i = 0; i < len; i++) {
+               h += p[i];
+               h += (h << 10);
+               h ^= (h >> 6);
+       }
+
+       h += (h << 3);
+       h ^= (h >> 11);
+       h += (h << 15);
+
+       return h;
+}
+
 static jsw_node_t *new_node ( void *key, void *item, jsw_node_t *next )
 {
-  jsw_node_t *node = (jsw_node_t *)malloc ( sizeof *node );
+  jsw_node_t *node = malloc ( sizeof *node );
 
   if ( node == NULL )
     return NULL;
@@ -58,7 +73,7 @@ static jsw_node_t *new_node ( void *key, void *item, jsw_node_t *next )
 
 static jsw_head_t *new_chain ( void )
 {
-  jsw_head_t *chain = (jsw_head_t *)malloc ( sizeof *chain );
+  jsw_head_t *chain = malloc ( sizeof *chain );
 
   if ( chain == NULL )
     return NULL;
@@ -79,13 +94,13 @@ 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 );
+  jsw_hash_t *htab = malloc ( sizeof *htab );
   size_t i;
 
   if ( htab == NULL )
     return NULL;
 
-  htab->table = (jsw_head_t **)malloc ( size * sizeof *htab->table );
+  htab->table = malloc ( size * sizeof *htab->table );
 
   if ( htab->table == NULL ) {
     free ( htab );
@@ -100,7 +115,7 @@ jsw_hash_t  *jsw_hnew ( size_t size, hash_f hash, cmp_f cmp,
   htab->capacity = size;
   htab->curri = 0;
   htab->currl = NULL;
-  htab->hash = hash;
+  htab->hash = hash ? hash : default_hash;
   htab->cmp = cmp;
   htab->keydup = keydup;
   htab->itemdup = itemdup;
@@ -161,6 +176,25 @@ void *jsw_hfind ( jsw_hash_t *htab, void *key )
   return NULL;
 }
 
+static int insert_item(jsw_head_t **table, jsw_node_t *item, unsigned int chain) {
+       /* Create a chain if the bucket is empty */
+       if ( table[chain] == NULL ) {
+               table[chain] = new_chain();
+       }
+
+       if ( table[chain] == NULL ) {
+               return 0;
+       }
+
+       /* Insert at the front of the chain */
+       item->next = table[chain]->first;
+       table[chain]->first = item;
+
+       ++table[chain]->size;
+
+       return 1;
+}
+
 /*
   Insert an item with the selected key
 
@@ -173,8 +207,9 @@ int jsw_hinsert ( jsw_hash_t *htab, void *key, void *item )
   jsw_node_t *new_item;
 
   /* Disallow duplicate keys */
-  if ( jsw_hfind ( htab, key ) != NULL )
+  if ( jsw_hfind ( htab, key ) != NULL ) {
     return 0;
+  }
 
   /* Attempt to create a new item */
   dupkey = htab->keydup ( key );
@@ -182,8 +217,9 @@ int jsw_hinsert ( jsw_hash_t *htab, void *key, void *item )
 
   new_item = new_node ( dupkey, dupitem, NULL );
 
-  if ( new_item == NULL )
+  if ( new_item == NULL ) {
     return 0;
+  }
 
   /* Create a chain if the bucket is empty */
   if ( htab->table[h] == NULL ) {
@@ -278,28 +314,36 @@ int jsw_herase ( jsw_hash_t *htab, void *key )
 */
 int jsw_hresize ( jsw_hash_t *htab, size_t new_size )
 {
-  jsw_hash_t *new_htab;
   jsw_node_t *it;
+  jsw_head_t **newtable;
   size_t i;
+  unsigned int bucket;
 
-  /* 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_size == htab->capacity) {
+         return 1;
+  }
 
-  if ( new_htab == NULL )
-    return 0;
+  newtable = malloc(new_size * sizeof *htab->table);
+
+  if (!newtable) {
+         return 0;
+  }
+
+  for(i=0; i < new_size; i++) {
+         newtable[i] = 0;
+  }
 
   for ( i = 0; i < htab->capacity; i++ ) {
-    if ( htab->table[i] == NULL )
-      continue;
+         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 );
+         for ( it = htab->table[i]->first; it != NULL; it = it->next ) {
+                 bucket = htab->hash(it->key) % new_size;
+                 insert_item(newtable, it, bucket);
+         }
   }
 
-  /* A hash table holds copies, so release the old table */
-  jsw_hdelete ( htab );
-  htab = new_htab;
+  htab->capacity = new_size;
+  htab->table = newtable;
 
   return 1;
 }
@@ -385,7 +429,7 @@ jsw_hstat_t *jsw_hstat ( jsw_hash_t *htab )
   if ( htab->size == 0 )
     return NULL;
 
-  stat = (jsw_hstat_t *)malloc ( sizeof *stat );
+  stat = malloc ( sizeof *stat );
 
   if ( stat == NULL )
     return NULL;