Changes to m4/m4/hash.c,v

[Eric Blake]

CVSROOT:        /sources/m4
Module name:    m4
Changes by:     Eric Blake <ericb>      06/09/01 23:11:05

Index: m4/hash.c
===================================================================
RCS file: /sources/m4/m4/m4/hash.c,v
retrieving revision 1.19
retrieving revision 1.20
diff -u -b -r1.19 -r1.20
--- m4/hash.c   28 Jul 2006 01:49:37 -0000      1.19
+++ m4/hash.c   1 Sep 2006 23:11:05 -0000       1.20
@@ -37,6 +37,9 @@
   m4_hash_hash_func *hash_func;
   m4_hash_cmp_func *cmp_func;
   hash_node **buckets;
+#ifndef NDEBUG
+  m4_hash_iterator *iter;      /* current iterator */
+#endif
 };
 
 struct hash_node
@@ -47,6 +50,17 @@
 };
 
 
+struct m4_hash_iterator
+{
+  const m4_hash *hash;         /* contains the buckets */
+  hash_node *  place;          /* the node we are about to return */
+  hash_node *  next;           /* the next node, incase PLACE is removed */
+  size_t       next_bucket;    /* the next bucket index following NEXT */
+#ifndef NDEBUG
+  m4_hash_iterator *chain;     /* multiple iterators visiting one hash */
+#endif
+};
+
 
 #define HASH_SIZE(hash)                ((hash)->size)
 #define HASH_LENGTH(hash)      ((hash)->length)
@@ -58,13 +72,28 @@
 #define NODE_KEY(node) ((node)->key)
 #define NODE_VALUE(node)       ((node)->value)
 
+#define ITERATOR_HASH(i)       ((i)->hash)
+#define ITERATOR_PLACE(i)      ((i)->place)
+#define ITERATOR_NEXT(i)       ((i)->next)
+#define ITERATOR_NEXT_BUCKET(i)        ((i)->next_bucket)
+
+#define ITERATOR_NEXT_NEXT(i)   NODE_NEXT (ITERATOR_PLACE (i))
+
 /* Helper macros. */
 #define BUCKET_NTH(hash, n)    (HASH_BUCKETS (hash)[n])
 #define BUCKET_COUNT(hash, key)                                        \
-       ((*HASH_HASH_FUNC(hash))(key) % HASH_SIZE(hash))
+       ((*HASH_HASH_FUNC (hash))(key) % HASH_SIZE (hash))
 #define BUCKET_KEY(hash, key)                                  \
        (BUCKET_NTH ((hash), BUCKET_COUNT ((hash), (key))))
 
+/* Debugging macros.  */
+#ifdef NDEBUG
+# define HASH_ITER(hash)       0
+# define ITER_CHAIN(iter)      0
+#else
+# define HASH_ITER(hash)       (((m4_hash *) hash)->iter)
+# define ITER_CHAIN(iter)      ((iter)->chain)
+#endif
 
 
 static void            bucket_insert   (m4_hash *hash, hash_node *bucket);
@@ -77,7 +106,7 @@
 
 
 
-static hash_node *free_list = 0;
+static hash_node *free_list = NULL;
 
 
 
@@ -99,9 +128,12 @@
   hash                 = xmalloc (sizeof *hash);
   HASH_SIZE (hash)     = size;
   HASH_LENGTH (hash)   = 0;
-  HASH_BUCKETS (hash)  = xcalloc (size, sizeof HASH_BUCKETS (hash));
+  HASH_BUCKETS (hash)  = xcalloc (size, sizeof *HASH_BUCKETS (hash));
   HASH_HASH_FUNC (hash)        = hash_func;
   HASH_CMP_FUNC (hash) = cmp_func;
+#ifndef NDEBUG
+  HASH_ITER (hash)     = NULL;
+#endif
 
   return hash;
 }
@@ -123,15 +155,17 @@
 }
 
 /* Recycle each of the nodes in HASH onto the free list, and release
-   the rest of the memory used by the table.  Memory addressed by
-   the recycled nodes is _NOT_ freed:  this needs to be done manually
-   to prevent memory leaks.  */
+   the rest of the memory used by the table.  Memory addressed by the
+   recycled nodes is _NOT_ freed: this needs to be done manually to
+   prevent memory leaks.  This is not safe to call while HASH is being
+   iterated.  */
 void
 m4_hash_delete (m4_hash *hash)
 {
   size_t i;
 
   assert (hash);
+  assert (!HASH_ITER (hash));
 
   for (i = 0; i < HASH_SIZE (hash); ++i)
     if (BUCKET_NTH (hash, i))
@@ -154,16 +188,16 @@
 
   for (node = BUCKET_NTH (hash, i); node->next; node = NODE_NEXT (node))
     {
-      assert (NODE_KEY(node) == 0);
+      assert (NODE_KEY (node) == NULL);
       --HASH_LENGTH (hash);
     }
 
-  assert (NODE_KEY(node) == 0);
+  assert (NODE_KEY (node) == NULL);
   --HASH_LENGTH (hash);
 
   NODE_NEXT (node)     = free_list;
   free_list            = BUCKET_NTH (hash, i);
-  BUCKET_NTH (hash, i) = 0;
+  BUCKET_NTH (hash, i) = NULL;
 }
 
 /* Create and initialise a new node with KEY and VALUE, by reusing a
@@ -171,7 +205,7 @@
 static hash_node *
 node_new (const void *key, void *value)
 {
-  hash_node *node = 0;
+  hash_node *node = NULL;
 
   if (free_list)
     {
@@ -185,7 +219,7 @@
 
   assert (node);
 
-  NODE_NEXT  (node)    = 0;
+  NODE_NEXT  (node)    = NULL;
   NODE_KEY   (node)    = key;
   NODE_VALUE (node)    = value;
 
@@ -197,7 +231,7 @@
 node_delete (m4_hash *hash, hash_node *node)
 {
   assert (node);
-  assert (NODE_KEY(node) == 0);
+  assert (NODE_KEY (node) == NULL);
 
   NODE_NEXT (node)     = free_list;
   free_list            = node;
@@ -205,15 +239,18 @@
   --HASH_LENGTH (hash);
 }
 
-/* Create a new entry in HASH with KEY and VALUE, making use of
-   nodes in the free list if possible, and potentially growing
-   the size of the table if node density is too high.  */
+/* Create a new entry in HASH with KEY and VALUE, making use of nodes
+   in the free list if possible, and potentially growing the size of
+   the table if node density is too high.  This is not safe to call
+   while HASH is being iterated.  Currently, it is not safe to call
+   this if another entry already matches KEY.  */
 const void *
 m4_hash_insert (m4_hash *hash, const void *key, void *value)
 {
   hash_node *node;
 
   assert (hash);
+  assert (!HASH_ITER (hash));
 
   node = node_new (key, value);
   node_insert (hash, node);
@@ -233,7 +270,7 @@
 
   assert (hash);
   assert (node);
-  assert (NODE_NEXT (node) == 0);
+  assert (NODE_NEXT (node) == NULL);
 
   n = BUCKET_COUNT (hash, NODE_KEY (node));
   NODE_NEXT (node)     = BUCKET_NTH (hash, n);
@@ -242,21 +279,32 @@
   ++HASH_LENGTH (hash);
 }
 
-/* Remove from HASH, the first node with key KEY; comparing keys
-   with HASH's cmp_func.  Any nodes with the same KEY previously
-   hidden by the removed node will become visible again.  The key
-   field of the removed node is returned.  */
+/* Remove from HASH, the first node with key KEY; comparing keys with
+   HASH's cmp_func.  Any nodes with the same KEY previously hidden by
+   the removed node will become visible again.  The key field of the
+   removed node is returned, or the original KEY If there was no
+   match.  This is unsafe if multiple iterators are visiting HASH, or
+   when a lone iterator is visiting on a different key.  */
 void *
 m4_hash_remove (m4_hash *hash, const void *key)
 {
   size_t n;
 
+#ifndef NDEBUG
+  m4_hash_iterator *iter = HASH_ITER (hash);
+
   assert (hash);
+  if (HASH_ITER (hash))
+    {
+      assert (!ITER_CHAIN (iter));
+      assert (ITERATOR_PLACE (iter));
+    }
+#endif
 
   n = BUCKET_COUNT (hash, key);
 
   {
-    hash_node *node = 0;
+    hash_node *node = NULL;
 
     do
       {
@@ -271,7 +319,9 @@
 
            key = NODE_KEY (next);
 #ifndef NDEBUG
-           NODE_KEY (next) = 0;
+           if (iter)
+             assert (ITERATOR_PLACE (iter) == next);
+           NODE_KEY (next) = NULL;
 #endif
            node_delete (hash, next);
            break;
@@ -284,11 +334,12 @@
   return (void *) key;
 }
 
-/* Return the address of the value field of the first node in
-   HASH that has a matching KEY.  The address is returned so that
-   an explicit 0 value can be distinguished from a failed lookup
-   (also 0).  Fortuitously for M4, this also means that the value
-   field can be changed `in situ' to implement a value stack.  */
+/* Return the address of the value field of the first node in HASH
+   that has a matching KEY.  The address is returned so that an
+   explicit NULL value can be distinguished from a failed lookup (also
+   NULL).  Fortuitously for M4, this also means that the value field
+   can be changed `in situ' to implement a value stack.  Safe to call
+   even when an iterator is in force.  */
 void **
 m4_hash_lookup (m4_hash *hash, const void *key)
 {
@@ -298,7 +349,7 @@
 
   node = node_lookup (hash, key);
 
-  return node ? &NODE_VALUE (node) : 0;
+  return node ? &NODE_VALUE (node) : NULL;
 }
 
 /* Return the first node in HASH that has a matching KEY.  */
@@ -317,7 +368,8 @@
   return node;
 }
 
-/* How many entries are currently contained by HASH.  */
+/* How many entries are currently contained by HASH.  Safe to call
+   even during an interation.  */
 size_t
 m4_get_hash_length (m4_hash *hash)
 {
@@ -334,7 +386,8 @@
    to set a smaller or larger initial size if you know in advance what
    order of magnitude of entries will be in the table.  Be aware that
    the efficiency of the lookup and grow features require that the size
-   always be 1 less than a power of 2.  */
+   always be 1 less than a power of 2.  Unsafe if HASH is being visited
+   by an iterator.  */
 void
 m4_hash_resize (m4_hash *hash, size_t size)
 {
@@ -342,12 +395,13 @@
   size_t original_size;
 
   assert (hash);
+  assert (!HASH_ITER (hash));
 
   original_size                = HASH_SIZE (hash);
   original_buckets     = HASH_BUCKETS (hash);
 
   HASH_SIZE (hash)     = size;
-  HASH_BUCKETS (hash)   = xcalloc (size, sizeof HASH_BUCKETS (hash));
+  HASH_BUCKETS (hash)   = xcalloc (size, sizeof *HASH_BUCKETS (hash));
 
   {
     size_t i;
@@ -377,8 +431,9 @@
       hash_node **original_buckets = HASH_BUCKETS (hash);
 
       /* HASH sizes are always 1 less than a power of 2.  */
-      HASH_SIZE (hash)    = (2* (1+ original_size)) -1;
-      HASH_BUCKETS (hash) = xcalloc (hash->size, sizeof HASH_BUCKETS (hash));
+      HASH_SIZE (hash)    = (2 * (1 + original_size)) -1;
+      HASH_BUCKETS (hash) = xcalloc (HASH_SIZE (hash),
+                                    sizeof *HASH_BUCKETS (hash));
 
       {
        size_t i;
@@ -392,7 +447,8 @@
 }
 
 /* Insert each node in BUCKET into HASH.  Relative ordering of nodes
-   is not preserved.  */
+   is not preserved.  This would need to change if we were to
+   guarantee relative ordering within a bucket for identical keys.  */
 static void
 bucket_insert (m4_hash *hash, hash_node *bucket)
 {
@@ -404,7 +460,7 @@
       hash_node *next = NODE_NEXT (bucket);
 
       /* Break link to rest of the bucket before reinserting.  */
-      NODE_NEXT (bucket) = 0;
+      NODE_NEXT (bucket) = NULL;
       node_insert (hash, bucket);
 
       bucket = next;
@@ -412,6 +468,9 @@
   while (bucket);
 }
 
+/* Reclaim all memory used by free nodes.  Safe to call at any time,
+   although only worth calling at program shutdown to verify no
+   leaks.  */
 void
 m4_hash_exit (void)
 {
@@ -425,21 +484,14 @@
 
 
 
-struct m4_hash_iterator
-{
-  const m4_hash *hash;         /* contains the buckets */
-  hash_node *  place;          /* the node we are about to return */
-  hash_node *  next;           /* the next node, incase PLACE is removed */
-  size_t       next_bucket;    /* the next bucket index following NEXT */
-};
-
-#define ITERATOR_HASH(i)       ((i)->hash)
-#define ITERATOR_PLACE(i)      ((i)->place)
-#define ITERATOR_NEXT(i)       ((i)->next)
-#define ITERATOR_NEXT_BUCKET(i)        ((i)->next_bucket)
-
-#define ITERATOR_NEXT_NEXT(i)   NODE_NEXT (ITERATOR_PLACE (i))
-
+/* Iterate over a given HASH.  Start with PLACE being NULL, then
+   repeat with PLACE being the previous return value.  The return
+   value is the current location of the iterator, or NULL when the
+   walk is complete.  Call m4_free_hash_iterator to abort iteration.
+   During the iteration, it is safe to search the list, and if no
+   other iterator is active, it is safe to remove the key pointed to
+   by this iterator.  All other actions that modify HASH are
+   unsafe.  */
 m4_hash_iterator *
 m4_get_hash_iterator_next (const m4_hash *hash, m4_hash_iterator *place)
 {
@@ -451,6 +503,10 @@
     {
       place = xzalloc (sizeof *place);
       ITERATOR_HASH (place) = hash;
+#ifndef NDEBUG
+      ITER_CHAIN (place) = HASH_ITER (hash);
+      HASH_ITER (hash) = place;
+#endif
     }
 
  next:
@@ -465,7 +521,7 @@
     {
       /* Find the next non-empty bucket.  */
       while ((ITERATOR_NEXT_BUCKET (place) < HASH_SIZE (hash))
-        && (BUCKET_NTH (hash, ITERATOR_NEXT_BUCKET (place)) == 0))
+        && (BUCKET_NTH (hash, ITERATOR_NEXT_BUCKET (place)) == NULL))
        {
          ++ITERATOR_NEXT_BUCKET (place);
        }
@@ -477,7 +533,7 @@
            = BUCKET_NTH (hash, ITERATOR_NEXT_BUCKET (place));
        }
       else
-       ITERATOR_NEXT (place) = 0;
+       ITERATOR_NEXT (place) = NULL;
 
       /* Advance the `next' reference.  */
       ++ITERATOR_NEXT_BUCKET (place);
@@ -486,8 +542,8 @@
   /* If there are no more nodes to return, recycle the iterator memory.  */
   if (! (ITERATOR_PLACE (place) || ITERATOR_NEXT (place)))
     {
-      free (place);
-      return 0;
+      m4_free_hash_iterator (hash, place);
+      return NULL;
     }
 
   /* On the first call we need to put the 1st node in PLACE and
@@ -500,6 +556,38 @@
   return place;
 }
 
+/* Clean up the iterator PLACE within HASH when aborting an iteration
+   early.  */
+void
+m4_free_hash_iterator (const m4_hash *hash, m4_hash_iterator *place)
+{
+#ifndef NDEBUG
+  m4_hash_iterator *iter = NULL;
+  m4_hash_iterator *next;
+
+  assert (hash);
+  assert (place && (ITERATOR_HASH (place) == hash));
+
+  do
+    {
+      next = iter ? ITER_CHAIN (iter) : HASH_ITER (hash);
+      if (place == next)
+       {
+         if (iter)
+           ITER_CHAIN (iter) = ITER_CHAIN (next);
+         else
+           HASH_ITER (hash) = ITER_CHAIN (next);
+         break;
+       }
+      iter = next;
+    }
+  while (iter);
+  assert (next);
+#endif
+  free (place);
+}
+
+/* Return the key being visited by the iterator PLACE.  */
 const void *
 m4_get_hash_iterator_key (m4_hash_iterator *place)
 {
@@ -508,6 +596,7 @@
   return NODE_KEY (ITERATOR_PLACE (place));
 }
 
+/* Return the value being visited by the iterator PLACE.  */
 void *
 m4_get_hash_iterator_value (m4_hash_iterator *place)
 {
@@ -517,10 +606,12 @@
 }
 
 /* The following function is used for the cases where we want to do
-   something to each and every entry in HASH.  This function
-   traverses the hash table, and calls a specified function FUNC for
-   each entry in the table.  FUNC is called with a pointer to the
-   entry key, value, and the passed DATA argument.  */
+   something to each and every entry in HASH.  This function traverses
+   the hash table, and calls a specified function FUNC for each entry
+   in the table.  FUNC is called with a pointer to the entry key,
+   value, and the passed DATA argument.  If FUNC returns non-NULL,
+   abort the iteration and return that value; a return of NULL implies
+   success on all entries.  */
 void *
 m4_hash_apply (m4_hash *hash, m4_hash_apply_func *func, void *userdata)
 {
@@ -536,8 +627,11 @@
                        m4_get_hash_iterator_value (place), userdata);
 
       if (result != NULL)
+       {
+         m4_free_hash_iterator (hash, place);
        break;
     }
+    }
 
   return result;
 }