Changeset 3d5c1b18b9912541a77e63bdb908db34f068b328

Timestamp:

04/23/08 10:02:37 (9 months ago)

Author:

David Balmain <dbalmain@…>

Parents:

399100f1271aa3320cae55afa2d8364875291971

Children:

b39568e8202274e6aed953a924659cef1f971d55, aee5f1150b23fd9469c1afe18187627c2320550d

git-committer:

David Balmain <dbalmain@gmail.com> / 2008-04-23T10:02:37Z+1000

Message:

Modifed integer Hash to also accept pointers

Integer hash has been improved so that it stores a dummy key instead of any old
junk which it was storing before. The h_lookup_int has been changed to
h_lookup_ptr but it is still used by h_set_int etc. I'll soon be adding
h_new_ptr which will be an optimized hash, especially for storing Symbols.

Location:

c

Files:

• Rakefile (modified) (1 diff)
• include/hash.h (modified) (2 diffs)
• include/internal.h (modified) (1 diff)
• src/hash.c (modified) (17 diffs)
• src/index.c (modified) (1 diff)
• test/test_term_vectors.c (modified) (2 diffs)

c/Rakefile

@@ -386 +386 @@
 end
 
-task :valgrind => 'testall' do
-        sh "valgrind --suppressions=valgrind.supp " +
-                "--leak-check=yes             " +
-                "--show-reachable=yes         " +
-                "--workaround-gcc296-bugs=yes -v ./testall -q"
-end
-
-task :gen_valgrind => 'build:testall' do
-        sh "valgrind --suppressions=valgrind.supp " +
-                "--leak-check=yes             " +
-                "--show-reachable=yes         " +
-                "--gen-suppressions=yes       " +
-                "--workaround-gcc296-bugs=yes -v ./testall -q"
+task :valgrind do
+  check_coptions
+  Rake::Task[:testall].invoke
+  sh "valgrind --suppressions=valgrind.supp " +
+              "--leak-check=yes             " +
+              "--show-reachable=yes         " +
+              "--workaround-gcc296-bugs=yes -v ./testall -q"
+end
+
+task :gen_valgrind do
+  check_coptions
+  Rake::Task[:testall].invoke
+  sh "valgrind --suppressions=valgrind.supp " +
+              "--leak-check=yes             " +
+              "--show-reachable=yes         " +
+              "--gen-suppressions=yes       " +
+              "--workaround-gcc296-bugs=yes -v ./testall -q"
 end
 

c/include/hash.h

@@ -61 +61 @@
      * used outside of the Hash methods */
     FrtHashEntry *(*lookup_i)(struct FrtHash *self,
-                                    register const void *key);
+                              register const void *key);
     unsigned long (*hash_i)(const void *key);
     int           (*eq_i)(const void *key1, const void *key2);
@@ -275 +275 @@
  * @param self the Hash to add the value to
  * @param key the key to use to reference the value
- * @return HashEntry a pointer to the hash entry object now reserved for this
+ * @param he HashEntry a pointer to the hash entry object now reserved for this
  * value. Be sure to set both the *key* and the *value*
- */
-extern FrtHashEntry *frt_h_set_ext(FrtHash *ht, const void *key);
+ * @return true if the key was empty, false otherwise
+ */
+extern FRT_INLINE bool h_set_ext(FrtHash *self,
+                                 const void *key,
+                                 FrtHashEntry **he);
 
 /**

c/include/internal.h

@@ -528 +528 @@
 #define h_rem_int                               frt_h_rem_int
 #define h_set                                   frt_h_set
-#define h_set_ext                               frt_h_set_ext
 #define h_set_int                               frt_h_set_int
 #define h_set_safe                              frt_h_set_safe

c/src/hash.c

@@ -13 +13 @@
 
 static char *dummy_key = "";
+static char *dummy_int_key = "i";
+
 
 #define PERTURB_SHIFT 5
@@ -47 +49 @@
 }
 
-static int int_eq(const void *q1, const void *q2)
-{
-    (void)q1;
-    (void)q2;
-    return true;
-}
-
-static unsigned long int_hash(const void *i)
-{
-    return *((unsigned long *)i);
-}
-
-typedef HashEntry *(*lookup_ft)(struct Hash *ht, register const void *key);
+typedef HashEntry *(*lookup_ft)(struct Hash *self, register const void *key);
 
 /**
@@ -65 +55 @@
  * deletes to worry about.
  *
- * @param ht the Hash to do the fast lookup in
+ * @param self the Hash to do the fast lookup in
  * @param the hashkey we are looking for
  */
-static INLINE HashEntry *h_resize_lookup(Hash *ht,
+static INLINE HashEntry *h_resize_lookup(Hash *self,
                                          register const unsigned long hash)
 {
     register unsigned long perturb;
-    register int mask = ht->mask;
-    register HashEntry *he0 = ht->table;
+    register int mask = self->mask;
+    register HashEntry *he0 = self->table;
     register int i = hash & mask;
     register HashEntry *he = &he0[i];
@@ -92 +82 @@
 }
 
-static HashEntry *h_lookup_int(Hash *ht, const void *key)
-{
-    register const unsigned long hash = *((int *)key);
+static HashEntry *h_lookup_ptr(Hash *self, const void *key)
+{
+    register const unsigned long hash = (long)key;
     register unsigned long perturb;
-    register int mask = ht->mask;
-    register HashEntry *he0 = ht->table;
+    register int mask = self->mask;
+    register HashEntry *he0 = self->table;
     register int i = hash & mask;
     register HashEntry *he = &he0[i];
@@ -129 +119 @@
 }
 
-HashEntry *h_lookup(Hash *ht, register const void *key)
-{
-    register const unsigned long hash = ht->hash_i(key);
+HashEntry *h_lookup(Hash *self, register const void *key)
+{
+    register const unsigned long hash = self->hash_i(key);
     register unsigned long perturb;
-    register int mask = ht->mask;
-    register HashEntry *he0 = ht->table;
+    register int mask = self->mask;
+    register HashEntry *he0 = self->table;
     register int i = hash & mask;
     register HashEntry *he = &he0[i];
     register HashEntry *freeslot = NULL;
-    eq_ft eq = ht->eq_i;
+    eq_ft eq = self->eq_i;
 
     if (he->key == NULL || he->key == key) {
@@ -176 +166 @@
 Hash *h_new_str(free_ft free_key, free_ft free_value)
 {
-    Hash *ht;
+    Hash *self;
     if (num_free_hts > 0) {
-        ht = free_hts[--num_free_hts];
+        self = free_hts[--num_free_hts];
     }
     else {
-        ht = ALLOC(Hash);
-    }
-    ht->fill = 0;
-    ht->size = 0;
-    ht->mask = HASH_MINSIZE - 1;
-    ht->table = ht->smalltable;
-    memset(ht->smalltable, 0, sizeof(ht->smalltable));
-    ht->lookup_i = (lookup_ft)&h_lookup;
-    ht->eq_i = str_eq;
-    ht->hash_i = (hash_ft)str_hash;
-
-    ht->free_key_i = free_key != NULL ? free_key : &dummy_free;
-    ht->free_value_i = free_value != NULL ? free_value : &dummy_free;
-    ht->ref_cnt = 1;
-    return ht;
+        self = ALLOC(Hash);
+    }
+    self->fill = 0;
+    self->size = 0;
+    self->mask = HASH_MINSIZE - 1;
+    self->table = self->smalltable;
+    memset(self->smalltable, 0, sizeof(self->smalltable));
+    self->lookup_i = (lookup_ft)&h_lookup;
+    self->eq_i = str_eq;
+    self->hash_i = (hash_ft)str_hash;
+
+    self->free_key_i = free_key != NULL ? free_key : &dummy_free;
+    self->free_value_i = free_value != NULL ? free_value : &dummy_free;
+    self->ref_cnt = 1;
+    return self;
 }
 
 Hash *h_new_int(free_ft free_value)
 {
-    Hash *ht = h_new_str(NULL, free_value);
-    ht->lookup_i = &h_lookup_int;
-    ht->eq_i = int_eq;
-    ht->hash_i = int_hash;
-    return ht;
+    Hash *self     = h_new_str(NULL, free_value);
+
+    self->lookup_i = &h_lookup_ptr;
+    self->eq_i     = NULL;
+    self->hash_i   = NULL;
+
+    return self;
+}
+
+Hash *h_new_ptr(free_ft free_key, free_ft free_value)
+{
+    Hash *self     = h_new_str(free_key, free_value);
+
+    self->lookup_i = &h_lookup_ptr;
+    self->eq_i     = NULL;
+    self->hash_i   = NULL;
+
+    return self;
 }
 
 Hash *h_new(hash_ft hash, eq_ft eq, free_ft free_key, free_ft free_value)
 {
-    Hash *ht = h_new_str(free_key, free_value);
-
-    ht->lookup_i = &h_lookup;
-    ht->eq_i = eq;
-    ht->hash_i = hash;
-    return ht;
-}
-
-void h_clear(Hash *ht)
+    Hash *self     = h_new_str(free_key, free_value);
+
+    self->lookup_i = &h_lookup;
+    self->eq_i     = eq;
+    self->hash_i   = hash;
+
+    return self;
+}
+
+void h_clear(Hash *self)
 {
     int i;
     HashEntry *he;
-    free_ft free_key = ht->free_key_i;
-    free_ft free_value = ht->free_value_i;
+    free_ft free_key   = self->free_key_i;
+    free_ft free_value = self->free_value_i;
 
     /* Clear all the hash values and keys as necessary */
     if (free_key != dummy_free || free_value != dummy_free) {
-        for (i = 0; i <= ht->mask; i++) {
-            he = &ht->table[i];
+        for (i = 0; i <= self->mask; i++) {
+            he = &self->table[i];
             if (he->key != NULL && he->key != dummy_key) {
                 free_value(he->value);
@@ -235 +239 @@
         }
     }
-    ZEROSET_N(ht->table, HashEntry, ht->mask + 1);
-    ht->size = 0;
-    ht->fill = 0;
-}
-
-void h_destroy(Hash *ht)
-{
-    if (--(ht->ref_cnt) <= 0) {
-        h_clear(ht);
+    ZEROSET_N(self->table, HashEntry, self->mask + 1);
+    self->size = 0;
+    self->fill = 0;
+}
+
+void h_destroy(Hash *self)
+{
+    if (--(self->ref_cnt) <= 0) {
+        h_clear(self);
 
         /* if a new table was created, be sure to free it */
-        if (ht->table != ht->smalltable) {
-            free(ht->table);
+        if (self->table != self->smalltable) {
+            free(self->table);
         }
 
 #ifdef DEBUG
-        free(ht);
+        free(self);
 #else
         if (num_free_hts < MAX_FREE_HASH_TABLES) {
-            free_hts[num_free_hts++] = ht;
+            free_hts[num_free_hts++] = self;
         }
         else {
-            free(ht);
+            free(self);
         }
 #endif
@@ -263 +267 @@
 }
 
-void *h_get(Hash *ht, const void *key)
+void *h_get(Hash *self, const void *key)
 {
     /* Note: lookup_i will never return NULL. */
-    return ht->lookup_i(ht, key)->value;
-}
-
-int h_del(Hash *ht, const void *key)
-{
-    HashEntry *he = ht->lookup_i(ht, key);
+    return self->lookup_i(self, key)->value;
+}
+
+int h_del(Hash *self, const void *key)
+{
+    HashEntry *he = self->lookup_i(self, key);
 
     if (he->key != NULL && he->key != dummy_key) {
-        ht->free_key_i(he->key);
-        ht->free_value_i(he->value);
+        self->free_key_i(he->key);
+        self->free_value_i(he->value);
         he->key = dummy_key;
         he->value = NULL;
-        ht->size--;
+        self->size--;
         return true;
     }
@@ -286 +290 @@
 }
 
-void *h_rem(Hash *ht, const void *key, bool destroy_key)
+void *h_rem(Hash *self, const void *key, bool destroy_key)
 {
     void *val;
-    HashEntry *he = ht->lookup_i(ht, key);
+    HashEntry *he = self->lookup_i(self, key);
 
     if (he->key != NULL && he->key != dummy_key) {
         if (destroy_key) {
-            ht->free_key_i(he->key);
+            self->free_key_i(he->key);
         }
 
@@ -299 +303 @@
         val = he->value;
         he->value = NULL;
-        ht->size--;
+        self->size--;
         return val;
     }
@@ -307 +311 @@
 }
 
-static int h_resize(Hash *ht, int min_newsize)
+static int h_resize(Hash *self, int min_newsize)
 {
     HashEntry smallcopy[HASH_MINSIZE];
@@ -318 +322 @@
     }
 
-    oldtable = ht->table;
+    oldtable = self->table;
     if (newsize == HASH_MINSIZE) {
-        if (ht->table == ht->smalltable) {
-            /* need to copy the d*(int *)ata out so we can rebuild the table into
+        if (self->table == self->smalltable) {
+            /* need to copy the data out so we can rebuild the table into
              * the same space */
-            memcpy(smallcopy, ht->smalltable, sizeof(smallcopy));
+            memcpy(smallcopy, self->smalltable, sizeof(smallcopy));
             oldtable = smallcopy;
         }
         else {
-            ht->table = ht->smalltable;
+            self->table = self->smalltable;
         }
     }
     else {
-        ht->table = ALLOC_N(HashEntry, newsize);
-    }
-    memset(ht->table, 0, sizeof(HashEntry) * newsize);
-    ht->fill = ht->size;
-    ht->mask = newsize - 1;
-
-    for (num_active = ht->size, he_old = oldtable; num_active > 0; he_old++) {
+        self->table = ALLOC_N(HashEntry, newsize);
+    }
+    memset(self->table, 0, sizeof(HashEntry) * newsize);
+    self->fill = self->size;
+    self->mask = newsize - 1;
+
+    for (num_active = self->size, he_old = oldtable; num_active > 0; he_old++) {
         if (he_old->key && he_old->key != dummy_key) {    /* active entry */
-            /*he_new = ht->lookup_i(ht, he_old->key); */
-            he_new = h_resize_lookup(ht, he_old->hash);
+            /*he_new = self->lookup_i(self, he_old->key); */
+            he_new = h_resize_lookup(self, he_old->hash);
             he_new->key = he_old->key;
             he_new->value = he_old->value;
@@ -346 +350 @@
         }                       /* else empty entry so nothing to do */
     }
-    if (oldtable != smallcopy && oldtable != ht->smalltable) {
+    if (oldtable != smallcopy && oldtable != self->smalltable) {
         free(oldtable);
     }
@@ -352 +356 @@
 }
 
-HashKeyStatus h_set(Hash *ht, const void *key, void *value)
+INLINE bool h_set_ext(Hash *self, const void *key, HashEntry **he)
+{
+    *he = self->lookup_i(self, key);
+    if ((*he)->key == NULL) {
+        if (self->fill * 3 > self->mask * 2) {
+            h_resize(self, self->size * ((self->size > SLOW_DOWN) ? 4 : 2));
+            *he = self->lookup_i(self, key);
+        }
+        self->fill++;
+        self->size++;
+        return true;
+    }
+    else if ((*he)->key == dummy_key) {
+        self->size++;
+        return true;
+    }
+
+    return false;
+}
+
+HashKeyStatus h_set(Hash *self, const void *key, void *value)
 {
     HashKeyStatus ret_val = HASH_KEY_DOES_NOT_EXIST;
-    HashEntry *he = ht->lookup_i(ht, key);
-    if (he->key == NULL) {
-        if (ht->fill * 3 > ht->mask * 2) {
-            h_resize(ht, ht->size * ((ht->size > SLOW_DOWN) ? 4 : 2));
-            he = ht->lookup_i(ht, key);
-        }
-        ht->fill++;
-        ht->size++;
-    }
-    else if (he->key == dummy_key) {
-        ht->size++;
-    }
-    else if (he->key != key) {
-        ht->free_key_i(he->key);
-        if (he->value != value) {
-            ht->free_value_i(he->value);
-        }
-        ret_val = HASH_KEY_EQUAL;
-    }
-    else {
-        /* safety check. Only free old value if it isn't the new value */
-        if (he->value != value) {
-            ht->free_value_i(he->value);
-        }
-        ret_val = HASH_KEY_SAME;
+    HashEntry *he;
+    if (!h_set_ext(self, key, &he)) {
+        if (he->key != key) {
+            self->free_key_i(he->key);
+            if (he->value != value) {
+                self->free_value_i(he->value);
+            }
+            ret_val = HASH_KEY_EQUAL;
+        }
+        else {
+            /* Only free old value if it isn't the new value */
+            if (he->value != value) {
+                self->free_value_i(he->value);
+            }
+            ret_val = HASH_KEY_SAME;
+        }
     }
     he->key = (void *)key;
     he->value = value;
 
-    /*
-    if ((ht->fill > fill) && (ht->fill * 3 > ht->mask * 2)) {
-        h_resize(ht, ht->size * ((ht->size > SLOW_DOWN) ? 4 : 2));
-    }
-    */
     return ret_val;
 }
 
-HashEntry *h_set_ext(Hash *ht, const void *key)
-{
-    HashEntry *he = ht->lookup_i(ht, key);
-    if (he->key == NULL) {
-        if (ht->fill * 3 > ht->mask * 2) {
-            h_resize(ht, ht->size * ((ht->size > SLOW_DOWN) ? 4 : 2));
-            he = ht->lookup_i(ht, key);
-        }
-        ht->fill++;
-        ht->size++;
-    }
-    else if (he->key == dummy_key) {
-        ht->size++;
-    }
-
-    return he;
-}
-
-int h_set_safe(Hash *ht, const void *key, void *value)
-{
-    HashEntry *he = ht->lookup_i(ht, key);
-    int fill = ht->fill;
-    if (he->key == NULL) {
-        ht->fill++;
-        ht->size++;
-    }
-    else if (he->key == dummy_key) {
-        ht->size++;
+int h_set_safe(Hash *self, const void *key, void *value)
+{
+    HashEntry *he;
+    if (h_set_ext(self, key, &he)) {
+        he->key = (void *)key;
+        he->value = value;
+        return true;
     }
     else {
         return false;
     }
-    he->key = (void *)key;
-    he->value = value;
-
-    if ((ht->fill > fill) && (ht->fill * 3 > ht->mask * 2)) {
-        h_resize(ht, ht->size * ((ht->size > SLOW_DOWN) ? 4 : 2));
-    }
-    return true;
-}
-
-HashKeyStatus h_has_key(Hash *ht, const void *key)
-{
-    HashEntry *he = ht->lookup_i(ht, key);
+}
+
+HashKeyStatus h_has_key(Hash *self, const void *key)
+{
+    HashEntry *he = self->lookup_i(self, key);
     if (he->key == NULL || he->key == dummy_key) {
         return HASH_KEY_DOES_NOT_EXIST;
@@ -445 +427 @@
 }
 
-void *h_get_int(Hash *self, const unsigned long key)
-{
-    return h_get(self, &key);
-}
-
-int h_del_int(Hash *self, const unsigned long key)
-{
-    return h_del(self, &key);
-}
-
-void *h_rem_int(Hash *self, const unsigned long key)
-{
-    return h_rem(self, &key, false);
-}
-
-HashKeyStatus h_set_int(Hash *self,
-                             const unsigned long key,
-                             void *value)
-{
-    return h_set(self, &key, value);
-}
-
-int h_set_safe_int(Hash *self, const unsigned long key, void *value)
-{
-    return h_set_safe(self, &key, value);
-}
-
-int h_has_key_int(Hash *self, const unsigned long key)
-{
-    return h_has_key(self, &key);
-}
-
-void h_each(Hash *ht,
+INLINE void *h_get_int(Hash *self, const unsigned long key)
+{
+    return h_get(self, (const void *)key);
+}
+
+INLINE int h_del_int(Hash *self, const unsigned long key)
+{
+    return h_del(self, (const void *)key);
+}
+
+INLINE void *h_rem_int(Hash *self, const unsigned long key)
+{
+    return h_rem(self, (const void *)key, false);
+}
+
+INLINE HashKeyStatus h_set_int(Hash *self,
+                               const unsigned long key,
+                               void *value)
+{
+    HashKeyStatus ret_val = HASH_KEY_DOES_NOT_EXIST;
+    HashEntry *he;
+    if (!h_set_ext(self, (const void *)key, &he)) {
+        /* Only free old value if it isn't the new value */
+        if (he->value != value) {
+            self->free_value_i(he->value);
+        }
+        ret_val = HASH_KEY_EQUAL;
+    }
+    he->key = dummy_int_key;
+    he->value = value;
+
+    return ret_val;
+}
+
+INLINE int h_set_safe_int(Hash *self, const unsigned long key, void *value)
+{
+    HashEntry *he;
+    if (h_set_ext(self, (const void *)key, &he)) {
+        he->key = dummy_int_key;
+        he->value = value;
+        return true;
+    }
+    return false;
+}
+
+INLINE int h_has_key_int(Hash *self, const unsigned long key)
+{
+    return h_has_key(self, (const void *)key);
+}
+
+void h_each(Hash *self,
             void (*each_kv) (void *key, void *value, void *arg), void *arg)
 {
     HashEntry *he;
-    int i = ht->size;
-    for (he = ht->table; i > 0; he++) {
+    int i = self->size;
+    for (he = self->table; i > 0; he++) {
         if (he->key && he->key != dummy_key) {        /* active entry */
             each_kv(he->key, he->value, arg);
@@ -490 +490 @@
 }
 
-Hash *h_clone(Hash *ht,
-                   h_clone_ft clone_key, h_clone_ft clone_value)
+Hash *h_clone(Hash *self, h_clone_ft clone_key, h_clone_ft clone_value)
 {
     void *key, *value;
     HashEntry *he;
-    int i = ht->size;
+    int i = self->size;
     Hash *ht_clone;
 
-  &n