[ViewVC] Diff of: cvs/libeio/eio.c

Comparing libeio/eio.c (file contents):
Revision 1.38 by root, Fri Jun 12 20:01:42 2009 UTC vs.
Revision 1.41 by root, Sun Jun 14 20:36:59 2009 UTC

 }
 static signed char
 eio_dent_cmp (const eio_dirent *a, const eio_dirent *b)
 {
-  return b->score - a->score ? b->score - a->score /* works because our signed char is always 0..100 */
+    return b->score - a->score ? b->score - a->score /* works because our signed char is always 0..100 */
-         : a->inode < b->inode ? -1 : a->inode > b->inode ? 1 : 0;
+              : a->inode < b->inode ? -1 : a->inode > b->inode ? 1 : 0;
 }
+#define EIO_DENT_CMP(i,op,j) eio_dent_cmp (&i, &j) op 0
+#define EIO_DENT_NUM_SCORES 9
-#define EIO_QSORT_CUTOFF 20 /* quite high, but performs well on many filesystems */
+#define EIO_QSORT_CUTOFF 30 /* quite high, but performs well on many filesystems */
+#define EIO_QSORT_SKIP   60 /* when to skip qsort completely */
 static void
 eio_dent_sort (eio_dirent *dents, int size)
 {
-  int i, j;
+  if (size <= 1)
+    return; /* our insertion sort relies on size > 0 */
-  if (size > EIO_QSORT_CUTOFF * 3) /* skip quicksort for small directories */
+  if (size > EIO_QSORT_SKIP) /* skip quicksort for small directories */
     {
       /* first, use quicksort */
       /* should be good for 2**31 entries */
+      int i;
-      struct rng { int l, r; } rng [32];
+      struct rng { eio_dirent *l, *r; } rng [32];
       i = 0;
-      rng[0].l = 0;
+      rng[0].l = dents;
-      rng[0].r = size;
+      rng[0].r = dents + size;
       while (expect_true (i >= 0))
         {
-          int L = rng [i].l;
+          eio_dirent *L = rng [i].l;
-          int R = rng [i].r - 1;
+          eio_dirent *R = rng [i].r - 1;
           if (expect_false (L + EIO_QSORT_CUTOFF < R))
             {
-              eio_dirent piv = dents [L];
+              eio_dirent *mid = &dents [((L - dents) + (R - dents)) >> 1];
+              eio_dirent piv = *mid; *mid = *L; *L = piv;
               while (L < R)
                 {
-                  while (eio_dent_cmp (&dents [R], &piv) >= 0 && L < R)
+                  while (EIO_DENT_CMP (*R, >=, piv) && L < R)
                     --R;
                   if (L < R)
-                    dents [L++] = dents [R];
+                    *L++ = *R;
-                  while (eio_dent_cmp (&dents [L], &piv) <= 0 && L < R)
+                  while (EIO_DENT_CMP (*L, <=, piv) && L < R)
                     ++L;
                   if (L < R)
-                    dents [R--] = dents [L];
+                    *R-- = *L;
                 }
-              dents [L] = piv;
+              *L = piv;
               ++i;
               rng [i].l = L + 1;
               rng [i].r = rng [i - 1].r;
               rng [i - 1].r = L;
           else
             --i;
         }
     }
-  /* use a simple insertion sort at the end */
+  /* use an insertion sort after qsort, or for small arrays */
-  for (i = 1; i < size; ++i)
+  /* first move the smallest element to the front, to act as a sentinel */
+  {
+    int i;
+    eio_dirent *min = dents;
+    for (i = size > EIO_QSORT_SKIP ? EIO_QSORT_CUTOFF + 1 : size; --i; )
+      if (EIO_DENT_CMP (dents [i], <, *min))
+        min = &dents [i];
+    /* swap elements 0 and j (minimum) */
     {
+      eio_dirent tmp = *dents; *dents = *min; *min = tmp;
+    }
+  }
+  {
+    /* then do standard insertion sort */
+    eio_dirent *i, *j;
+    for (i = dents + 1; i < dents + size; ++i)
+      {
-      eio_dirent value = dents [i];
+        eio_dirent value = *i;
-      for (j = i - 1; j >= 0 && eio_dent_cmp (&dents [j], &value) > 0; --j)
+        for (j = i - 1; EIO_DENT_CMP (*j, >, value); --j)
-        dents [j + 1] = dents [j];
+          j [1] = j [0];
-      dents [j + 1] = value;
+        j [1] = value;
-    }
+      }
+  }
 }
 /* read a full directory */
 static void
 eio__scandir (eio_req *req, etp_worker *self)
                 /* now move dirs to the front, and non-dirs to the back */
                 /* by walking from both sides and swapping if necessary */
                 while (ent > dir)
                   {
                     if (dir->type == DT_DIR)
+                      {
+                        dir->score = 0;
-                      ++dir;
+                        ++dir;
+                      }
                     else
                       {
                         --ent;
                         if (ent->type == DT_DIR)
                           {
                             eio_dirent tmp = *dir;
                             *dir = *ent;
                             *ent = tmp;
+                            dir->score = 0;
                             ++dir;
                           }
                       }
                   }
                 ent = dents + dentoffs;
                 ent->name    = (char *)(size_t)namesoffs; /* rather dirtily we store the offset in the pointer */
                 ent->namelen = len - 1;
-                ent->inode   = D_INO (entp);
+                ent->inode   = D_INO (entp) ? D_INO (entp) : dentoffs;
                 switch (D_TYPE (entp))
                   {
                     default:
                       ent->type = EIO_DT_UNKNOWN;
                 if (flags & EIO_READDIR_DIRS_FIRST)
                   {
                     if (ent->type == EIO_DT_UNKNOWN)
                       {
                         if (*name == '.') /* leading dots are likely directories, and, in any case, rare */
-                          ent->score = 98;
+                          ent->score = 7;
                         else if (!strchr (name, '.')) /* absense of dots indicate likely dirs */
-                          ent->score = len <= 2 ? len + 6 : len <= 4 ? 5 : len <= 7 ? 4 : 1; /* shorter == more likely dir, but avoid too many classes */
+                          ent->score = len <= 2 ? len + 4 : len <= 4 ? 3 : len <= 7 ? 2 : 1; /* shorter == more likely dir, but avoid too many classes */
                       }
                     else if (ent->type == EIO_DT_DIR)
-                      ent->score = 100;
+                      ent->score = 8;
                   }
               }
             namesoffs += len;
             ++dentoffs;

Diff Legend

-–
+Removed lines
-+
+Added lines
-<
+Changed lines
->
+Changed lines

Comparing libeio/eio.c (file contents): Revision 1.38 by root, Fri Jun 12 20:01:42 2009 UTC vs. Revision 1.41 by root, Sun Jun 14 20:36:59 2009 UTC

Diff Legend

Comparing libeio/eio.c (file contents):
Revision 1.38 by root, Fri Jun 12 20:01:42 2009 UTC vs.
Revision 1.41 by root, Sun Jun 14 20:36:59 2009 UTC