X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;ds=sidebyside;f=src%2Fhash.c;h=588b311b45774c37cc52d5476b4a79b24b589b17;hb=d2f8593a1f1d39a3264682af0da898a3d67b68cf;hp=f6bad64b8889dbc2b3bf860924f8fc21d470489a;hpb=2bfc3a138f308ffb38634a92b23bdc7b62592324;p=pspp

diff --git a/src/hash.c b/src/hash.c
index f6bad64b88..588b311b45 100644
--- a/src/hash.c
+++ b/src/hash.c
@@ -18,12 +18,12 @@
    02111-1307, USA. */
 
 #include <config.h>
-#include <assert.h>
+#include "hash.h"
+#include "error.h"
 #include <limits.h>
 #include <stdlib.h>
 #include "algorithm.h"
 #include "alloc.h"
-#include "hash.h"
 #include "misc.h"
 #include "str.h"
 
@@ -76,43 +76,39 @@ next_power_of_2 (size_t x)
     }
 }
 
-/* Colin Plumb's "one-at-a-time" hash, for bytes. */
+/* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */
+#define FNV_32_PRIME 16777619u
+#define FNV_32_BASIS 2166136261u
+
+/* Fowler-Noll-Vo 32-bit hash, for bytes. */
 unsigned
 hsh_hash_bytes (const void *buf_, size_t size)
 {
   const unsigned char *buf = buf_;
-  unsigned hash = 0;
+  unsigned hash;
 
   assert (buf != NULL);
-  while (size-- > 0) 
-    {
-      hash += *buf++;
-      hash += (hash << 10);
-      hash ^= (hash >> 6);
-    } 
-  hash += (hash << 3);
-  hash ^= (hash >> 11);
-  hash += (hash << 15);
+
+  hash = FNV_32_BASIS;
+  while (size-- > 0)
+    hash = (hash * FNV_32_PRIME) ^ *buf++;
+
   return hash;
 } 
 
-/* Colin Plumb's "one-at-a-time" hash, for strings. */
+/* Fowler-Noll-Vo 32-bit hash, for strings. */
 unsigned
 hsh_hash_string (const char *s_) 
 {
   const unsigned char *s = s_;
-  unsigned hash = 0;
+  unsigned hash;
 
   assert (s != NULL);
-  while (*s != '\0') 
-    {
-      hash += *s++;
-      hash += (hash << 10);
-      hash ^= (hash >> 6);
-    } 
-  hash += (hash << 3);
-  hash ^= (hash >> 11);
-  hash += (hash << 15);
+
+  hash = FNV_32_BASIS;
+  while (*s != '\0')
+    hash = (hash * FNV_32_PRIME) ^ *s++;
+
   return hash;
 }
 
@@ -216,24 +212,21 @@ hsh_rehash (struct hsh_table *h, size_t new_size)
   for (i = 0; i < h->size; i++)
     h->entries[i] = NULL;
   for (table_p = begin; table_p < end; table_p++)
-    {
-      void **entry;
-
-      if (*table_p == NULL)
-	continue;
-      entry = &h->entries[h->hash (*table_p, h->aux) & (h->size - 1)];
-      while (*entry)
-	if (--entry < h->entries)
-	  entry = &h->entries[h->size - 1];
-      *entry = *table_p;
-    }
+    if (*table_p != NULL)
+      {
+        void **entry = &h->entries[h->hash (*table_p, h->aux) & (h->size - 1)];
+        while (*entry != NULL)
+          if (++entry >= h->entries + h->size)
+            entry = h->entries;
+        *entry = *table_p;
+      }
   free (begin);
 }
 
 /* A "algo_predicate_func" that returns nonzero if DATA points
    to a non-null void. */
 static int
-not_null (const void *data_, void *aux unused) 
+not_null (const void *data_, void *aux UNUSED) 
 {
   void *const *data = data_;
 
@@ -259,7 +252,7 @@ hsh_data (struct hsh_table *h)
 
 /* Dereferences void ** pointers and passes them to the hash
    comparison function. */
-int
+static int
 comparison_helper (const void *a_, const void *b_, void *h_) 
 {
   void *const *a = a_;
@@ -341,8 +334,8 @@ hsh_probe (struct hsh_table *h, const void *target)
     {
       if (!h->compare (*entry, target, h->aux))
 	return entry;
-      if (--entry < h->entries)
-	entry = &h->entries[h->size - 1];
+      if (++entry >= h->entries + h->size)
+	entry = h->entries;
     }
   h->used++;
   return entry;
@@ -392,8 +385,8 @@ locate_matching_entry (struct hsh_table *h, const void *target)
     {
       if (!h->compare (*entry, target, h->aux))
 	return entry;
-      if (--entry < h->entries)
-	entry = &h->entries[h->size - 1];
+      if (++entry >= h->entries + h->size)
+	entry = h->entries;
     }
   return NULL;
 }
@@ -410,20 +403,43 @@ hsh_find (struct hsh_table *h, const void *target)
 /* Deletes the entry in hash table H that matches TARGET.
    Returns nonzero if an entry was deleted.
 
-   Note: this function is very slow because it rehashes the
-   entire table.  Don't use this hash table implementation if
-   deletion is a common operation. */
+   Uses Knuth's Algorithm 6.4R (Deletion with linear probing).
+   Because our load factor is at most 1/2, the average number of
+   moves that this algorithm makes should be at most 2 - ln 2 ~=
+   1.65.
+
+   Not well tested. */
 int
 hsh_delete (struct hsh_table *h, const void *target) 
 {
   void **entry = locate_matching_entry (h, target);
   if (entry != NULL) 
     {
+      ptrdiff_t i;
+      
+      h->used--;
       if (h->free != NULL)
         h->free (*entry, h->aux);
       *entry = 0;
-      hsh_rehash (h, h->size);
-      return 1;
+
+      i = entry - h->entries;
+      for (;;) 
+        {
+          unsigned r;
+          ptrdiff_t j = i;
+
+          do 
+            {
+              if (--i < 0)
+                i = h->size - 1;
+              if (h->entries[i] == NULL)
+                return 1;
+              
+              r = h->hash (h->entries[i], h->aux) & (h->size - 1);
+            }
+          while ((i <= r && r < j) || (r < j && j < i) || (j < i && i <= r));
+          h->entries[i] = h->entries[j]; 
+        }
     }
   else
     return 0;
@@ -483,7 +499,7 @@ hsh_count (struct hsh_table *h)
 
 #if GLOBAL_DEBUGGING
 #undef NDEBUG
-#include <assert.h>
+#include "error.h"
 #include <stdio.h>
 
 /* Displays contents of hash table H on stdout. */