chiark / gitweb /
Allow things to be looked up by just their caller-supplied hashes. This
authormdw <mdw>
Tue, 1 Jun 1999 09:49:33 +0000 (09:49 +0000)
committermdw <mdw>
Tue, 1 Jun 1999 09:49:33 +0000 (09:49 +0000)
actually needs to be thought through better.

sym.c
sym.h

diff --git a/sym.c b/sym.c
index 6ddc45c..394b761 100644 (file)
--- a/sym.c
+++ b/sym.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: sym.c,v 1.6 1999/05/26 21:08:31 mdw Exp $
+ * $Id: sym.c,v 1.7 1999/06/01 09:49:08 mdw Exp $
  *
  * Symbol table management
  *
 /*----- Revision history --------------------------------------------------*
  *
  * $Log: sym.c,v $
+ * 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.6  1999/05/26 21:08:31  mdw
  * Rename symbols in line with newer conventions.
  *
@@ -61,6 +65,7 @@
 /* --- Local headers --- */
 
 #include "alloc.h"
+#include "bits.h"
 #include "crc32.h"
 #include "exc.h"
 #include "sub.h"
@@ -166,7 +171,9 @@ 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
- *             @strlen(n) + 1@.
+ *             @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.
  *
  *             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
@@ -183,22 +190,26 @@ void sym_destroy(sym_table *t)
 
 void *sym_find(sym_table *t, const char *n, long l, size_t sz, unsigned *f)
 {
-  unsigned long hash;                  /* Hash value for user's name */
-  size_t len = l < 0 ? strlen(n) + 1 : l; /* Find length of user's name */
-  sym_base *bin;                       /* Bin containing our item */
-  sym_base *p, *q;                     /* Pointer wandering through list */
+  uint32 hash;
+  size_t len = 0;
+  sym_base *bin;
+  sym_base *p, *q;
 
   /* --- Find the correct bin --- */
 
-  CRC32(hash, 0, n, len);              /* Find hash value for this name */
+  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));
 
   /* --- Search the bin list --- */
 
   while (p->next) {
-    if (hash == p->next->hash &&       /* Check full hash values first */
-       len == p->next->len &&          /* Then compare string lengths */
-       !memcmp(n, SYM_NAME(p->next), len)) /* And finally compare names */
+    if (hash == p->next->hash &&
+       (n == 0 || (len == p->next->len &&
+                   !memcmp(n, SYM_NAME(p->next), len))))
     {
       /* --- Found a match --- *
        *
@@ -206,24 +217,24 @@ void *sym_find(sym_table *t, const char *n, long l, size_t sz, unsigned *f)
        * front of its bin list.
        */
 
-      q = p->next;                     /* Find the actual symbol block */
-      p->next = q->next;               /* Extract block from bin list */
-      q->next = bin->next;             /* Set up symbol's next pointer */
-      bin->next = q;                   /* And reinsert the block */
+      q = p->next;
+      p->next = q->next;
+      q->next = bin->next;
+      bin->next = q;
 
       /* --- Return the block --- */
 
-      if (f) *f = 1;                   /* Didn't fail to find the item */
-      return (q);                      /* And return the block */
+      if (f) *f = 1;
+      return (q);
     }
 
-    p = p->next;                       /* Move onto the next item */
+    p = p->next;
   }
 
   /* --- Couldn't find the item there --- */
 
-  if (f) *f = 0;                       /* Failed to find the block */
-  if (!sz) return (0);                 /* Return zero if not creating */
+  if (f) *f = 0;
+  if (!sz) return (0);
 
   /* --- Create a new symbol block and initialize it --- */
 
@@ -231,36 +242,38 @@ void *sym_find(sym_table *t, const char *n, long l, size_t sz, unsigned *f)
     TRACK_CTX("new symbol creation");
     TRACK_PUSH;
 
-    p = xmalloc(sz);                   /* Create a new symbol block */
-    p->next = bin->next;               /* Set up the next pointer */
-    p->hash = hash;                    /* Set up the hash value too */
-    p->len = len;                      /* And set up the string length */
-    if (len <= SYM_BUFSZ)
-      memcpy(p->name.b, n, len);       /* And copy the string over */
-    else {
-      TRY {
-       p->name.p = sub_alloc(len);     /* Allocate a block for the name */
-       memcpy(p->name.p, n, len);      /* And copy the string over */
-      } CATCH {
-       free(p);
-       TRACK_POP;
-       RETHROW;
-      } END_TRY;
+    p = xmalloc(sz);
+    p->next = bin->next;
+    p->hash = hash;
+    p->len = len;
+    if (n) {
+      if (len <= SYM_BUFSZ)
+       memcpy(p->name.b, n, len);
+      else {
+       TRY {
+         p->name.p = sub_alloc(len);
+         memcpy(p->name.p, n, len);
+       } CATCH {
+         free(p);
+         TRACK_POP;
+         RETHROW;
+       } END_TRY;
+      }
     }
 
     TRACK_POP;
   }
 
-  bin->next = p;                       /* Put the pointer into the bin */
+  bin->next = p;
 
   /* --- Consider growing the array --- */
 
   if (t->c)
     t->c--;
   if (!t->c) {
-    unsigned long m = t->mask + 1;     /* Next set bit in has word */
-    sym_base *p, *q, *r;               /* More useful pointers */
-    size_t i, lim;                     /* Loop counter and limit */
+    uint32 m = t->mask + 1;
+    sym_base *p, *q, *r;
+    size_t i, lim;
 
     TRACK_CTX("symbol table extension");
     TRACK_PUSH;
@@ -278,8 +291,8 @@ void *sym_find(sym_table *t, const char *n, long l, size_t sz, unsigned *f)
        RETHROW;
     } END_TRY;
 
-    t->c = SYM_LIMIT(t->mask + 1);     /* Set load value */
-    t->mask = (t->mask + 1) * 2 - 1;   /* Set the new mask value */
+    t->c = SYM_LIMIT(t->mask + 1);
+    t->mask = (t->mask + 1) * 2 - 1;
 
     /* --- Now wander through the table rehashing things --- *
      *
@@ -291,22 +304,22 @@ void *sym_find(sym_table *t, const char *n, long l, size_t sz, unsigned *f)
     lim = (t->mask + 1) >> 1;
     for (i = 0; i < lim; i++) {
 
-      /* --- Some initialisation --- */
+      /* --- Some initialization --- */
 
-      r = t->a[i];                     /* Find the list we're dissecting */
-      p = (sym_base *)(t->a + i);      /* Find bit-clear list */
-      q = (sym_base *)(t->a + i + lim);        /* And the bit-set lsit */
+      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)                /* Is the next bit set? */
-         q = q->next = r;              /* Yes, so fit up previous link */
+       if (r->hash & m)
+         q = q->next = r;
        else
-         p = p->next = r;              /* No, so fit up previous link */
-       r = r->next;                    /* Move onto the next item */
+         p = p->next = r;
+       r = r->next;
       }
-      p->next = q->next = 0;           /* Null terminate the new lists */
+      p->next = q->next = 0;
     }
 
     TRACK_POP;
diff --git a/sym.h b/sym.h
index fab6915..94d43c5 100644 (file)
--- a/sym.h
+++ b/sym.h
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: sym.h,v 1.6 1999/05/26 21:08:31 mdw Exp $
+ * $Id: sym.h,v 1.7 1999/06/01 09:49:33 mdw Exp $
  *
  * Symbol table management
  *
 /*----- Revision history --------------------------------------------------*
  *
  * $Log: sym.h,v $
+ * Revision 1.7  1999/06/01 09:49:33  mdw
+ * Allow things to be looked up by just their caller-supplied hashes.  This
+ * actually needs to be thought through better.
+ *
  * Revision 1.6  1999/05/26 21:08:31  mdw
  * Rename symbols in line with newer conventions.
  *
 
 #include <stddef.h>
 
+#ifndef BITS_H
+#  include "bits.h"
+#endif
+
 /*----- Type definitions --------------------------------------------------*/
 
 /* --- Symbol table --- *
@@ -89,7 +97,7 @@ typedef struct sym_table {
 
 typedef struct sym_base {
   struct sym_base *next;               /* Next symbol in hash bin */
-  unsigned long hash;                  /* Hash value for symbol's name */
+  uint32 hash;                         /* Hash value for symbol's name */
   union {
     char *p;                           /* Pointer to name string */
     char b[SYM_BUFSZ];                 /* Buffer containing a short name */
@@ -154,7 +162,9 @@ extern 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
- *             @strlen(n)@.
+ *             @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.
  *
  *             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