X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Fhash.c;h=dcf8d8fffdc28945ed983614f28912d9179a9623;hb=92f198d13c9214c0d75b936f0ea0dc2684ea914b;hp=76503664f016816cdd0ac49e9b5bd31ebb8eeed8;hpb=dcf9b154cbcaa35c3d8459a201b77eec8bcb30bd;p=pspp

diff --git a/src/libpspp/hash.c b/src/libpspp/hash.c
index 76503664f0..dcf8d8fffd 100644
--- a/src/libpspp/hash.c
+++ b/src/libpspp/hash.c
@@ -23,10 +23,11 @@
 #include <assert.h>
 #include <ctype.h>
 #include <limits.h>
+#include <stdbool.h>
 #include <stdlib.h>
 #include "array.h"
 #include "alloc.h"
-#include <stdbool.h>
+#include "compiler.h"
 #include "misc.h"
 #include "str.h"
 
@@ -230,8 +231,9 @@ hsh_destroy (struct hsh_table *h)
     }
 }
 
-/* Locates an entry matching TARGET.  Returns a pointer to the
-   entry, or a null pointer on failure. */
+/* Locates an entry matching TARGET.  Returns the index for the
+   entry, if found, or the index of an empty entry that indicates
+   where TARGET should go, otherwise. */
 static inline unsigned
 locate_matching_entry (struct hsh_table *h, const void *target) 
 {
@@ -249,6 +251,24 @@ locate_matching_entry (struct hsh_table *h, const void *target)
     }
 }
 
+/* Returns the index of an empty entry that indicates
+   where TARGET should go, assuming that TARGET is not equal to
+   any item already in the hash table. */
+static inline unsigned
+locate_empty_entry (struct hsh_table *h, const void *target) 
+{
+  unsigned i = h->hash (target, h->aux);
+
+  assert (h->hash_ordered);
+  for (;;)
+    {
+      i &= h->size - 1;
+      if (h->entries[i] == NULL)
+	return i;
+      i--;
+    }
+}
+
 /* Changes the capacity of H to NEW_SIZE, which must be a
    positive power of 2 at least as large as the number of
    elements in H. */
@@ -275,7 +295,7 @@ rehash (struct hsh_table *h, size_t new_size)
     {
       void *entry = *table_p;
       if (entry != NULL)
-        h->entries[locate_matching_entry (h, entry)] = entry;
+        h->entries[locate_empty_entry (h, entry)] = entry;
     }
   free (begin);
 
@@ -566,7 +586,7 @@ hsh_count (struct hsh_table *h)
 
 /* Debug helpers. */
 
-#if GLOBAL_DEBUGGING
+#if DEBUGGING
 #undef NDEBUG
 #include "message.h"
 #include <stdio.h>