[Pspp-cvs] pspp/src/libpspp hash.c ChangeLog

[Ben Pfaff]

CVSROOT:        /cvsroot/pspp
Module name:    pspp
Changes by:     Ben Pfaff <blp> 06/06/26 05:37:53

Modified files:
        src/libpspp    : hash.c ChangeLog 

Log message:
        Small optimization for hash library.

CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/hash.c?cvsroot=pspp&r1=1.4&r2=1.5
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/ChangeLog?cvsroot=pspp&r1=1.28&r2=1.29

Patches:
Index: hash.c
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/hash.c,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -b -r1.4 -r1.5
--- hash.c      26 Jun 2006 05:25:17 -0000      1.4
+++ hash.c      26 Jun 2006 05:37:53 -0000      1.5
@@ -251,6 +251,24 @@
     }
 }
 
+/* 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. */
@@ -277,7 +295,7 @@
     {
       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);
 

Index: ChangeLog
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/ChangeLog,v
retrieving revision 1.28
retrieving revision 1.29
diff -u -b -r1.28 -r1.29
--- ChangeLog   9 Jun 2006 22:51:24 -0000       1.28
+++ ChangeLog   26 Jun 2006 05:37:53 -0000      1.29
@@ -1,3 +1,13 @@
+Sun Jun 25 22:35:28 2006  Ben Pfaff  <address@hidden>
+
+       Optimize rehashing: we know that none of the entries in the hash
+       table are equal, so we need not compare them to each other during
+       rehashing.
+       
+       * hash.c: (locate_empty_entry) New function.
+       (rehash) Use locate_empty_entry() instead of
+       locate_matching_entry().
+
 Fri Jun  9 14:03:29 2006  Ben Pfaff  <address@hidden>
 
        Reform string library.