[GNUnet-SVN] r2432 - in GNUnet: . src/applications/gap

[grothoff]

Author: grothoff
Date: 2006-01-01 21:13:06 -0800 (Sun, 01 Jan 2006)
New Revision: 2432

Modified:
   GNUnet/ChangeLog
   GNUnet/src/applications/gap/gap.c
Log:
sync

Modified: GNUnet/ChangeLog
===================================================================
--- GNUnet/ChangeLog    2006-01-01 10:21:05 UTC (rev 2431)
+++ GNUnet/ChangeLog    2006-01-02 05:13:06 UTC (rev 2432)
@@ -1,3 +1,8 @@
+Sun Jan  1 21:35:59 PST 2006
+       Reduced amount of hashing done to be O(n) and not O(n^2) for
+       n local search results (for example, for 100 results, this can
+       make the difference between hashing 200 MB and hashing 20 MB).
+
 Sat Dec 31 17:02:37 PST 2005
        Added support for using -k multiple times in gnunet-pseudonym.
 

Modified: GNUnet/src/applications/gap/gap.c
===================================================================
--- GNUnet/src/applications/gap/gap.c   2006-01-01 10:21:05 UTC (rev 2431)
+++ GNUnet/src/applications/gap/gap.c   2006-01-02 05:13:06 UTC (rev 2432)
@@ -1512,6 +1512,8 @@
   const PeerIdentity * sender;
   DataContainer ** values;
   unsigned int valueCount;
+  HashCode512 * hashes;
+  unsigned int hashCount;
 };
 
 /**
@@ -1532,7 +1534,6 @@
                         void * closure) {
   struct qLRC * cls = closure;
   HashCode512 hc;
-  HashCode512 hc1;
   int i;
   IndirectionTableEntry * ite;
 
@@ -1553,14 +1554,10 @@
     if (equalsHashCode512(&hc,
                          &ite->seen[i]))
       return OK; /* drop, duplicate result! */
-  for (i=0;i<cls->valueCount;i++) {
-    hash(&cls->values[i][1],
-        ntohl(cls->values[i]->size) - sizeof(DataContainer),
-        &hc1);
+  for (i=0;i<cls->valueCount;i++) 
     if (equalsHashCode512(&hc,
-                         &hc1))
-      return OK; /* drop, duplicate entry in DB! */
-  }
+                         &cls->hashes[i]))
+      return OK; /* drop, duplicate entry in DB! */  
   GROW(cls->values,
        cls->valueCount,
        cls->valueCount+1);
@@ -1569,6 +1566,11 @@
   memcpy(cls->values[cls->valueCount-1],
         value,
         ntohl(value->size));
+  if (cls->hashCount < cls->valueCount) 
+    GROW(cls->hashes,
+        cls->hashCount,
+        cls->hashCount * 2 + 8);
+  cls->hashes[cls->valueCount-1] = hc;
   return OK;
 }
 
@@ -1641,6 +1643,8 @@
 #endif
   cls.values = NULL;
   cls.valueCount = 0;
+  cls.hashes = NULL;
+  cls.hashCount = 0;
   cls.sender = sender;
   if ( (isRouted == YES) && /* if we can't route, lookup useless! */
        ( (policy & QUERY_ANSWER) > 0) ) {
@@ -1696,9 +1700,11 @@
   GROW(cls.values,
        cls.valueCount,
        0);
+  GROW(cls.hashes,
+       cls.hashCount,
+       0);
 
 
-
   MUTEX_UNLOCK(&lookup_exclusion);
   if (doForward)
     forwardQuery(query,