Changeset 9146

Timestamp:

Aug 28, 2002, 4:12:55 AM (23 years ago)

Author:

bird

Message:

Use binary search on the dependency history. (saves another 20-30 on linux headers.)

File:

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

trunk/tools/fastdep/fastdep.c

@@ -1 @@
-/* $Id: fastdep.c,v 1.40 2002-08-27 21:48:45 bird Exp $
+/* $Id: fastdep.c,v 1.41 2002-08-28 02:12:55 bird Exp $
  *
  * Fast dependents. (Fast = Quick and Dirty!)
@@ -3781 +3781 @@
     int     iHistory;
     int     j;
-    int     k;
+    int     iStart;
+    int     iEnd;
     int     iCmp;
 #endif
@@ -3827 +3828 @@
                  * Check if in history, if so we'll skip it.
                  */
-                #if 1
+                #if 0
                 for (j = 0;  j < iHistory; j++)
                     if (!strcmp(apszHistory[j], pdep->pszRule))
                         break;
                 if (j != iHistory)
-                    continue;
+                    continue;           /* found */
 
                 /*
@@ -3841 +3842 @@
 
                 #else
+
                 /*
                  * Check if in history, if so we'll skip it.
@@ -3846 +3848 @@
                  * ASSUMES: Always something in the history!
                  */
+                iEnd = iHistory - 1;
+                iStart = 0;
                 j = iHistory / 2;
-                k = (iHistory + 1) / 2;
-                do 
+                while (    (iCmp = strcmp(pdep->pszRule, apszHistory[j])) != 0
+                       &&   iEnd != iStart)
                 {
-                    iCmp = strcmp(pdep->pszRule, apszHistroy[j]);
-                    if (!iCmp) 
+                    if (iCmp < 0)
+                        iEnd = j - 1;
+                    else
+                        iStart = j + 1;
+                    if (iStart > iEnd)
                         break;
-                    k = (k + 1) / 2;
-                    if (iCmp > 0)
-                        j += k;
-                    else
-                        j -= k;
-                } while (!k);
-
-                if (!iCmp) 
+                    j = (iStart + iEnd) / 2;
+                }
+
+                if (!iCmp)
                     continue;           /* found */
 
@@ -3868 +3871 @@
                 if (iHistory < HISTORY)
                 {
+                    int k;
                     if (iCmp > 0)       /* Insert after. */
                         j++;
-                    for (k = iHistory; k < j; k--) 
+                    for (k = iHistory; k > j; k--)
                         apszHistory[k] = apszHistory[k - 1];
                     apszHistory[j] = pdep->pszRule;