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

Comparing cvsroot/libeio/eio.c (file contents):
Revision 1.33 by root, Sat Jun 6 19:44:17 2009 UTC vs.
Revision 1.37 by root, Fri Jun 12 16:48:08 2009 UTC

 #else
 # include "config.h"
 # include <sys/time.h>
 # include <sys/select.h>
+# include <sys/mman.h>
 # include <unistd.h>
 # include <utime.h>
 # include <signal.h>
 # include <dirent.h>
     }
   return res;
 }
-static int
+static signed char
-eio_dent_cmp (const void *a_, const void *b_)
+eio_dent_cmp (const eio_dirent *a, const eio_dirent *b)
 {
-  const eio_dirent *a = (const eio_dirent *)a_;
+  return b->score - a->score ? b->score - a->score /* works because our signed char is always 0..100 */
-  const eio_dirent *b = (const eio_dirent *)b_;
-  return (int)b->score - (int)a->score ? (int)b->score - (int)a->score
-         : a->inode < b->inode ? -1 : a->inode > b->inode ? 1 : 0; /* int might be < ino_t */
+         : a->inode < b->inode ? -1 : a->inode > b->inode ? 1 : 0;
+}
+#define EIO_QSORT_CUTOFF 20 /* quite high, but performs well on many filesystems */
+static void
+eio_dent_sort (eio_dirent *dents, int size)
+{
+  /* should be good for 2**31 entries */
+  struct rng { int l, r; } rng [32];
+  int i, j;
+  i = 0;
+  rng[0].l = 0;
+  rng[0].r = size;
+  while (expect_true (i >= 0))
+    {
+      int L = rng [i].l;
+      int R = rng [i].r - 1;
+      if (expect_false (L + EIO_QSORT_CUTOFF < R))
+        {
+          eio_dirent piv = dents [L];
+          while (L < R)
+            {
+              while (eio_dent_cmp (&dents [R], &piv) >= 0 && L < R)
+                --R;
+              if (L < R)
+                dents [L++] = dents [R];
+              while (eio_dent_cmp (&dents [L], &piv) <= 0 && L < R)
+                ++L;
+              if (L < R)
+                dents [R--] = dents [L];
+            }
+          dents [L] = piv;
+          ++i;
+          rng [i].l = L + 1;
+          rng [i].r = rng [i - 1].r;
+          rng [i - 1].r = L;
+          if (rng [i].r - rng [i].l > rng [i - 1].r - rng [i - 1].l)
+            {
+              struct rng t;
+              t = rng [i]; rng [i] = rng [i - 1]; rng [i - 1] = t;
+            }
+        }
+      else
+        --i;
+    }
+  /* use a simple insertion sort at the end */
+  for (i = 1; i < size; ++i)
+    {
+      eio_dirent value = dents [i];
+      for (j = i - 1; j >= 0 && eio_dent_cmp (&dents [j], &value) > 0; --j)
+        dents [j + 1] = dents [j];
+      dents [j + 1] = value;
+    }
 }
 /* read a full directory */
 static void
 eio__scandir (eio_req *req, etp_worker *self)
 {
   DIR *dirp;
   EIO_STRUCT_DIRENT *entp;
-  unsigned char *name, *names;
+  char *name, *names;
   int namesalloc = 4096;
   int namesoffs = 0;
   int flags = req->int1;
   eio_dirent *dents = 0;
   int dentalloc = 128;
                   (--ent)->name = names + (size_t)ent->name;
               }
             if (flags & EIO_READDIR_STAT_ORDER
                 || !(~flags & (EIO_READDIR_DIRS_FIRST | EIO_READDIR_FOUND_UNKNOWN)))
-              {
+              eio_dent_sort (dents, dentoffs); /* score depends of DIRS_FIRST */
-                /* pray your qsort doesn't use quicksort */
-                qsort (dents, dentoffs, sizeof (*dents), eio_dent_cmp); /* score depends of DIRS_FIRST */
-              }
             else if (flags & EIO_READDIR_DIRS_FIRST)
               {
                 /* in this case, all is known, and we just put dirs first and sort them */
                 eio_dirent *ent = dents + dentoffs;
                 eio_dirent *dir = dents;
+                /* 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;
                     else
                           }
                       }
                   }
                 /* now sort the dirs only */
-                qsort (dents, dir - dents, sizeof (*dents), eio_dent_cmp);
+                eio_dent_sort (dents, dir - dents);
               }
             /* only provide the names array unless DENTS is specified */
             if (!(flags & EIO_READDIR_DENTS))
               {
                     if (ent->type == EIO_DT_UNKNOWN)
                       {
                         if (*name == '.') /* leading dots are likely directories, and, in any case, rare */
                           ent->score = 98;
                         else if (!strchr (name, '.')) /* absense of dots indicate likely dirs */
-                          ent->score = len <= 2 ? len + 60 : len <= 4 ? 50 : len <= 7 ? 40 : 10; /* shorter == more likely dir, but avoid too many classes */
+                          ent->score = len <= 2 ? len + 6 : len <= 4 ? 5 : len <= 7 ? 4 : 1; /* shorter == more likely dir, but avoid too many classes */
                       }
                     else if (ent->type == EIO_DT_DIR)
                       ent->score = 100;
                   }
               }
             namesoffs += len;
             ++dentoffs;
           }
+        if (EIO_CANCELLED (req))
+          {
+            errno = ECANCELED;
+            break;
+          }
       }
-  else
-    req->result = -1;
 }
 #if !(_POSIX_MAPPED_FILES && _POSIX_SYNCHRONIZED_IO)
 # undef msync
 # define msync(a,b,c) ((errno = ENOSYS), -1)
 /* misc garbage */
 ssize_t eio_sendfile_sync (int ofd, int ifd, off_t offset, size_t count)
 {
   etp_worker wrk;
+  ssize_t ret;
   wrk.dbuf = 0;
-  eio__sendfile (ofd, ifd, offset, count, &wrk);
+  ret = eio__sendfile (ofd, ifd, offset, count, &wrk);
   if (wrk.dbuf)
     free (wrk.dbuf);
-}
+  return ret;
+}

Diff Legend

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

Comparing cvsroot/libeio/eio.c (file contents): Revision 1.33 by root, Sat Jun 6 19:44:17 2009 UTC vs. Revision 1.37 by root, Fri Jun 12 16:48:08 2009 UTC

Diff Legend

Comparing cvsroot/libeio/eio.c (file contents):
Revision 1.33 by root, Sat Jun 6 19:44:17 2009 UTC vs.
Revision 1.37 by root, Fri Jun 12 16:48:08 2009 UTC