Break low-level hashtable code out from sym.

[mLib] / sym.c

diff --git a/sym.c b/sym.c
index 394b761e8fd6e4005aabc38e977cb2a75db2aa92..03d2e82b19a4aff9114e23693f43226dbd7e076d 100644 (file)
--- a/sym.c
+++ b/sym.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
 /* -*-c-*-
  *

- * $Id: sym.c,v 1.7 1999/06/01 09:49:08 mdw Exp $
+ * $Id: sym.c,v 1.8 1999/08/02 14:45:48 mdw Exp $

  *
  * Symbol table management
  *
  *
  * Symbol table management
  *


@@ -30,6 +30,9 @@
 /*----- Revision history --------------------------------------------------*
  *
  * $Log: sym.c,v $
 /*----- Revision history --------------------------------------------------*
  *
  * $Log: sym.c,v $

+ * Revision 1.8  1999/08/02 14:45:48  mdw
+ * Break low-level hashtable code out from sym.
+ *

  * Revision 1.7  1999/06/01 09:49:08  mdw
  * Allow things to be looked up by just their caller-supplied hashes.  This
  * actually needs to be thought through better.
  * Revision 1.7  1999/06/01 09:49:08  mdw
  * Allow things to be looked up by just their caller-supplied hashes.  This
  * actually needs to be thought through better.


@@ -68,6 +71,7 @@
 #include "bits.h"
 #include "crc32.h"
 #include "exc.h"
 #include "bits.h"
 #include "crc32.h"
 #include "exc.h"

+#include "hash.h"

 #include "sub.h"
 #include "sym.h"
 #include "track.h"
 #include "sub.h"
 #include "sym.h"
 #include "track.h"


@@ -80,7 +84,7 @@
  * so that it can be used to mask of the bottom bits of a hash value.
  */
 
  * so that it can be used to mask of the bottom bits of a hash value.
  */
 

-#define SYM_INITSZ 255                 /* Size of a new hash table */
+#define SYM_INITSZ 64                  /* Size of a new hash table */

 
 /* --- Maximum load factor --- *
  *
 
 /* --- Maximum load factor --- *
  *


@@ -91,7 +95,7 @@
  * doubled in size.
  */
 
  * doubled in size.
  */
 

-#define SYM_LIMIT(n) ((n) * 4)         /* Load factor for growing table */
+#define SYM_LIMIT(n) ((n) * 2)         /* Load factor for growing table */

 
 /*----- Main code ---------------------------------------------------------*/
 
 
 /*----- Main code ---------------------------------------------------------*/
 


@@ -107,18 +111,10 @@
 
 void sym_create(sym_table *t)
 {
 
 void sym_create(sym_table *t)
 {

-  size_t i;
-

   TRACK_CTX("symbol table creation");
   TRACK_PUSH;
   TRACK_CTX("symbol table creation");
   TRACK_PUSH;

-
-  t->mask = SYM_INITSZ;
-  t->c = SYM_LIMIT(SYM_INITSZ);
-  t->a = xmalloc((t->mask + 1) * sizeof(sym_base *));
-
-  for (i = 0; i < SYM_INITSZ + 1; i++)
-    t->a[i] = 0;
-
+  hash_create(&t->t, SYM_INITSZ);
+  t->load = SYM_LIMIT(SYM_INITSZ);

   TRACK_POP;
 }
 
   TRACK_POP;
 }
 


@@ -134,23 +130,22 @@ void sym_create(sym_table *t)
 
 void sym_destroy(sym_table *t)
 {
 
 void sym_destroy(sym_table *t)
 {

-  size_t i;
-  sym_base *p, *q;
+  sym_iter i;

 
 

-  TRACK_CTX("symbol table deletion");
+  TRACK_CTX("symbol table destruction");

   TRACK_PUSH;
 
   TRACK_PUSH;
 

-  for (i = 0; i <= t->mask; i++) {
-    p = t->a[i];
-    while (p) {
-      q = p->next;
-      if (p->len > SYM_BUFSZ)
-       sub_free(p->name.p, p->len);
-      free(p);
-      p = q;
-    }
+  SYM_MKITER(&i, t);
+  for (;;) {
+    sym_base *p;
+    SYM_NEXT(&i, p);
+    if (!p)
+      break;
+    if (p->len > SYM_BUFSZ)
+      sub_free(p->name.p, p->len);
+    free(p);

   }
   }

-  free(t->a);
+  hash_destroy(&t->t);

 
   TRACK_POP;
 }
 
   TRACK_POP;
 }


@@ -171,9 +166,7 @@ void sym_destroy(sym_table *t)
  *             may be given, in which case the name may contain arbitrary
  *             binary data, or it may be given as a negative number, in
  *             which case the length of the name is calculated as
  *             may be given, in which case the name may contain arbitrary
  *             binary data, or it may be given as a negative number, in
  *             which case the length of the name is calculated as

- *             @strlen(n) + 1@.  The name pointer @n@ may also be zero; in
- *             this case, @l@ is taken to be a raw hash, and any element
- *             with a matching hash is taken to be the one wanted.
+ *             @strlen(n) + 1@.

  *
  *             The return value is the address of a pointer to a @sym_base@
  *             block (which may have other things on the end, as above).  If
  *
  *             The return value is the address of a pointer to a @sym_base@
  *             block (which may have other things on the end, as above).  If


@@ -192,43 +185,36 @@ void *sym_find(sym_table *t, const char *n, long l, size_t sz, unsigned *f)
 {
   uint32 hash;
   size_t len = 0;
 {
   uint32 hash;
   size_t len = 0;

-  sym_base *bin;
-  sym_base *p, *q;
+  hash_base **bin, **p;
+  sym_base *q;

 
   /* --- Find the correct bin --- */
 
 
   /* --- Find the correct bin --- */
 

-  if (n) {
-    len = l < 0 ? strlen(n) + 1 : l;
-    CRC32(hash, 0, n, len);
-  } else
-    hash = (uint32)l;
-  bin = p = (sym_base *)(t->a + (hash & t->mask));
+  len = l < 0 ? strlen(n) + 1 : l;
+  CRC32(hash, 0, n, len);
+  bin = HASH_BIN(&t->t, hash);

 
   /* --- Search the bin list --- */
 
 
   /* --- Search the bin list --- */
 

-  while (p->next) {
-    if (hash == p->next->hash &&
-       (n == 0 || (len == p->next->len &&
-                   !memcmp(n, SYM_NAME(p->next), len))))
-    {
+  for (p = bin; *p; p = &(*p)->next) {
+    q = (sym_base *)*p;
+    if (hash == q->b.hash && len == q->len && !memcmp(n, SYM_NAME(q), len)) {
+

       /* --- Found a match --- *
        *
        * As a minor, and probably pointless, tweak, move the item to the
        * front of its bin list.
        */
 
       /* --- Found a match --- *
        *
        * As a minor, and probably pointless, tweak, move the item to the
        * front of its bin list.
        */
 

-      q = p->next;
-      p->next = q->next;
-      q->next = bin->next;
-      bin->next = q;
+      (*p) = q->b.next;
+      q->b.next = *bin;
+      *bin = &q->b;

 
       /* --- Return the block --- */
 
       if (f) *f = 1;
       return (q);
     }
 
       /* --- Return the block --- */
 
       if (f) *f = 1;
       return (q);
     }

-
-    p = p->next;

   }
 
   /* --- Couldn't find the item there --- */
   }
 
   /* --- Couldn't find the item there --- */


@@ -242,19 +228,19 @@ void *sym_find(sym_table *t, const char *n, long l, size_t sz, unsigned *f)
     TRACK_CTX("new symbol creation");
     TRACK_PUSH;
 
     TRACK_CTX("new symbol creation");
     TRACK_PUSH;
 

-    p = xmalloc(sz);
-    p->next = bin->next;
-    p->hash = hash;
-    p->len = len;
+    q = xmalloc(sz);
+    q->b.next = *bin;
+    q->b.hash = hash;
+    q->len = len;

     if (n) {
       if (len <= SYM_BUFSZ)
     if (n) {
       if (len <= SYM_BUFSZ)

-       memcpy(p->name.b, n, len);
+       memcpy(q->name.b, n, len);

       else {
        TRY {
       else {
        TRY {

-         p->name.p = sub_alloc(len);
-         memcpy(p->name.p, n, len);
+         q->name.p = sub_alloc(len);
+         memcpy(q->name.p, n, len);

        } CATCH {
        } CATCH {

-         free(p);
+         free(q);

          TRACK_POP;
          RETHROW;
        } END_TRY;
          TRACK_POP;
          RETHROW;
        } END_TRY;


@@ -264,76 +250,24 @@ void *sym_find(sym_table *t, const char *n, long l, size_t sz, unsigned *f)
     TRACK_POP;
   }
 
     TRACK_POP;
   }
 

-  bin->next = p;
+  *bin = &q->b;

 
   /* --- Consider growing the array --- */
 
 
   /* --- Consider growing the array --- */
 

-  if (t->c)
-    t->c--;
-  if (!t->c) {
-    uint32 m = t->mask + 1;
-    sym_base *p, *q, *r;
-    size_t i, lim;
-
-    TRACK_CTX("symbol table extension");
-    TRACK_PUSH;
-
-    /* --- Update values in the anchor block --- */
-
-    TRY {
-      t->a = xrealloc(t->a, (t->mask + 1) * 2 * sizeof(sym_base *));
-    } CATCH switch (exc_type) {
-      case EXC_NOMEM:
-       TRACK_POP;
-       return (bin->next);
-      default:
-       TRACK_POP;
-       RETHROW;
-    } END_TRY;
-
-    t->c = SYM_LIMIT(t->mask + 1);
-    t->mask = (t->mask + 1) * 2 - 1;
-
-    /* --- Now wander through the table rehashing things --- *
-     *
-     * This loop is very careful to avoid problems with aliasing.  The items
-     * are dealt with from the end backwards to avoid overwriting bins before
-     * they've been processed.
-     */
-
-    lim = (t->mask + 1) >> 1;
-    for (i = 0; i < lim; i++) {
-
-      /* --- Some initialization --- */
-
-      r = t->a[i];
-      p = (sym_base *)(t->a + i);
-      q = (sym_base *)(t->a + i + lim);
-
-      /* --- Now go through the @r@ list --- */
-
-      while (r) {
-       if (r->hash & m)
-         q = q->next = r;
-       else
-         p = p->next = r;
-       r = r->next;
-      }
-      p->next = q->next = 0;
-    }
-
-    TRACK_POP;
-  }
+  if (t->load)
+    t->load--;
+  if (!t->load && hash_extend(&t->t))
+    t->load = SYM_LIMIT(t->t.mask / 2 + 1);

 
   /* --- Finished that, so return the new symbol block --- */
 
 
   /* --- Finished that, so return the new symbol block --- */
 

-  return (p);
+  return (q);

 }
 
 /* --- @sym_remove@ --- *
  *
  * Arguments:  @sym_table *i@ = pointer to a symbol table object
 }
 
 /* --- @sym_remove@ --- *
  *
  * Arguments:  @sym_table *i@ = pointer to a symbol table object

- *             @void *b@ = pointer to symbol table entry
+ *             @void *p@ = pointer to symbol table entry

  *
  * Returns:    ---
  *
  *
  * Returns:    ---
  *


@@ -342,38 +276,14 @@ void *sym_find(sym_table *t, const char *n, long l, size_t sz, unsigned *f)
  *             to the entry should already be gone by this point.
  */
 
  *             to the entry should already be gone by this point.
  */
 

-void sym_remove(sym_table *t, void *b)
+void sym_remove(sym_table *t, void *p)

 {
 {

-  /* --- A quick comment --- *
-   *
-   * Since the @sym_base@ block contains the hash, finding the element in the
-   * bin list is really quick -- it's not worth bothering with things like
-   * doubly linked lists.
-   */
-
-  sym_base *p = b;
-  sym_base *bin = (sym_base *)(t->a + (p->hash & t->mask));
-
-  /* --- Find the item in the bin list --- */
-
-  while (bin->next) {
-    if (bin->next == p)
-      break;
-    bin = bin->next;
-  }
-  if (!bin->next)
-    return;
-
-  /* --- Now just remove the item from the list and free it --- *
-   *
-   * Oh, and bump the load counter.
-   */
-
-  bin->next = p->next;
-  if (p->len > SYM_BUFSZ)
-    sub_free(p->name.p, p->len);
-  free(p);
-  t->c++;
+  sym_base *q = p;
+  hash_remove(&t->t, &q->b);
+  if (q->len > SYM_BUFSZ)
+    sub_free(q->name.p, q->len);
+  free(q);
+  t->load++;

 }
 
 /* --- @sym_mkiter@ --- *
 }
 
 /* --- @sym_mkiter@ --- *


@@ -387,12 +297,7 @@ void sym_remove(sym_table *t, void *b)
  *             iterate through a symbol table.
  */
 
  *             iterate through a symbol table.
  */
 

-void sym_mkiter(sym_iter *i, sym_table *t)
-{
-  i->t = t;
-  i->i = 0;
-  i->n = 0;
-}
+void sym_mkiter(sym_iter *i, sym_table *t) { SYM_MKITER(i, t); }

 
 /* --- @sym_next@ --- *
  *
 
 /* --- @sym_next@ --- *
  *


@@ -406,23 +311,8 @@ void sym_mkiter(sym_iter *i, sym_table *t)
 
 void *sym_next(sym_iter *i)
 {
 
 void *sym_next(sym_iter *i)
 {

-  sym_base *p;
-
-  /* --- Find the next item --- */
-
-  while (!i->n) {
-    if (i->i > i->t->mask)
-      return (0);
-    i->n = i->t->a[i->i++];
-  }
-
-  /* --- Update the iterator block --- */
-
-  p = i->n;
-  i->n = p->next;
-
-  /* --- Done --- */
-
+  void *p;
+  SYM_NEXT(i, p);

   return (p);
 }
 
   return (p);
 }
 


@@ -522,10 +412,7 @@ int main(void)
       case 0: {
        sym_word *w;
 
       case 0: {
        sym_word *w;
 

-       printf("find `%s'\n", line[i]);
-       if ((rand() & 1023) == 0) {
-         putchar('.'); fflush(stdout);
-       }
+       printf("? %s\n", line[i]);

 
        w = sym_find(&tbl, line[i], -1, 0, 0);
        if (w != flag[i])
 
        w = sym_find(&tbl, line[i], -1, 0, 0);
        if (w != flag[i])


@@ -540,10 +427,7 @@ int main(void)
        unsigned f;
        sym_word *w;
 
        unsigned f;
        sym_word *w;
 

-       printf("create `%s'\n", line[i]);
-       if ((rand() & 1023) == 0) {
-         putchar('+'); fflush(stdout);
-       }
+       printf("+ %s\n", line[i]);

 
        w = sym_find(&tbl, line[i], -1, sizeof(sym_word), &f);
        if (f)
 
        w = sym_find(&tbl, line[i], -1, sizeof(sym_word), &f);
        if (f)


@@ -578,10 +462,8 @@ int main(void)
        v = (rand() % entries) == 0;
        if (!v)
          break;
        v = (rand() % entries) == 0;
        if (!v)
          break;

-       printf("\niterated %i entries\n", entries);
-       break;

 
 

-       printf("iterate\n");
+       printf(".\n");

 
        ntbl = xmalloc(sz * sizeof(sym_word *));
        memcpy(ntbl, flag, sz * sizeof(sym_word *));
 
        ntbl = xmalloc(sz * sizeof(sym_word *));
        memcpy(ntbl, flag, sz * sizeof(sym_word *));


@@ -589,14 +471,16 @@ int main(void)
 
        while ((w = sym_next(&it)) != 0) {
          if (ntbl[w->i] == 0)
 
        while ((w = sym_next(&it)) != 0) {
          if (ntbl[w->i] == 0)

-           printf("*** error: iterate returned duff item %i\n", w->i);
-         else
+           printf("*** error: iterate returned duff item %s\n", SYM_NAME(w));
+         else {
+           printf(": %s\n", SYM_NAME(w));

            ntbl[w->i] = 0;
            ntbl[w->i] = 0;

+         }

        }
 
        for (i = 0; i < sz; i++)
        }
 
        for (i = 0; i < sz; i++)

-         if (ntbl[i]) printf("*** error: iterate didn't return item %i\n",
-                             i);
+         if (ntbl[i]) printf("*** error: iterate didn't return item %s\n",
+                             SYM_NAME(ntbl[i]));

        free(ntbl);
       } break;
 
        free(ntbl);
       } break;
 


@@ -607,18 +491,18 @@ int main(void)
 
        printf("dump\n");
 
 
        printf("dump\n");
 

-       for (i = 0; i <= tbl.mask; i++) {
-         if (!tbl.a[i]) continue;
+       for (i = 0; i <= tbl.b.mask; i++) {
+         if (!tbl.b.v[i]) continue;

          if (v) printf("  %i: ", i);
          if (v) printf("  %i: ", i);

-         b = tbl.a[i];
+         b = (sym_base *)tbl.b.v[i];

          while (b) {
          while (b) {

-           if ((b->hash & tbl.mask) != i)
+           if ((b->b.hash & tbl.b.mask) != i)

              printf("*** error: bad hash value found");
            if (v) printf("`%s'(%08lx:%lu) ",
                          line[((sym_word *)b)->i],
              printf("*** error: bad hash value found");
            if (v) printf("`%s'(%08lx:%lu) ",
                          line[((sym_word *)b)->i],

-                         b->hash,
-                         b->hash & tbl.mask);
-           b = b->next;
+                         b->b.hash,
+                         b->b.hash & tbl.b.mask);
+           b = (sym_base *)b->b.next;

          }
          if (v) putchar('\n');
        }
          }
          if (v) putchar('\n');
        }


@@ -626,7 +510,7 @@ int main(void)
 
       case 4: {
        if (flag[i]) {
 
       case 4: {
        if (flag[i]) {

-         printf("remove `%s'\n", SYM_NAME(&flag[i]->base));
+         printf("- %s\n", SYM_NAME(&flag[i]->base));

          if ((rand() & 1023) == 0) {
            putchar('-'); fflush(stdout);
          }
          if ((rand() & 1023) == 0) {
            putchar('-'); fflush(stdout);
          }