Changeset 9145 for trunk/tools

Timestamp:

Aug 27, 2002, 11:48:45 PM (23 years ago)

Author:

bird

Message:

going home, taking code with me.

File:

• trunk/tools/fastdep/fastdep.c (modified) (4 diffs)

trunk/tools/fastdep/fastdep.c

@@ -1 @@
-/* $Id: fastdep.c,v 1.39 2002-08-21 01:51:56 bird Exp $
+/* $Id: fastdep.c,v 1.40 2002-08-27 21:48:45 bird Exp $
  *
  * Fast dependents. (Fast = Quick and Dirty!)
@@ -3781 +3781 @@
     int     iHistory;
     int     j;
+    int     k;
+    int     iCmp;
 #endif
     PDEPRULE pdep;
@@ -3825 +3827 @@
                  * Check if in history, if so we'll skip it.
                  */
+                #if 1
                 for (j = 0;  j < iHistory; j++)
                     if (!strcmp(apszHistory[j], pdep->pszRule))
@@ -3836 +3839 @@
                 if (iHistory < HISTORY)
                     apszHistory[iHistory++] = pdep->pszRule;
+
+                #else
+                /*
+                 * Check if in history, if so we'll skip it.
+                 *  (Binary search)
+                 * ASSUMES: Always something in the history!
+                 */
+                j = iHistory / 2;
+                k = (iHistory + 1) / 2;
+                do 
+                {
+                    iCmp = strcmp(pdep->pszRule, apszHistroy[j]);
+                    if (!iCmp) 
+                        break;
+                    k = (k + 1) / 2;
+                    if (iCmp > 0)
+                        j += k;
+                    else
+                        j -= k;
+                } while (!k);
+
+                if (!iCmp) 
+                    continue;           /* found */
+
+                /*
+                 * Push into history - might concider make this binary sorted one day.
+                 */
+                if (iHistory < HISTORY)
+                {
+                    if (iCmp > 0)       /* Insert after. */
+                        j++;
+                    for (k = iHistory; k < j; k--) 
+                        apszHistory[k] = apszHistory[k - 1];
+                    apszHistory[j] = pdep->pszRule;
+                    iHistory++;
+                }
+
+                #endif
+
 #endif
                 /*