ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/libeio/eio.c
(Generate patch)

Comparing libeio/eio.c (file contents):
Revision 1.36 by root, Fri Jun 12 00:43:16 2009 UTC vs.
Revision 1.37 by root, Fri Jun 12 16:48:08 2009 UTC

… …
73#else 73#else
74 74
75# include "config.h" 75# include "config.h"
76# include <sys/time.h> 76# include <sys/time.h>
77# include <sys/select.h> 77# include <sys/select.h>
78# include <sys/mman.h>
78# include <unistd.h> 79# include <unistd.h>
79# include <utime.h> 80# include <utime.h>
80# include <signal.h> 81# include <signal.h>
81# include <dirent.h> 82# include <dirent.h>
82 83
… …
989 } 990 }
990 991
991 return res; 992 return res;
992} 993}
993 994
994static int 995static signed char
995eio_dent_cmp (const void *a_, const void *b_) 996eio_dent_cmp (const eio_dirent *a, const eio_dirent *b)
996{ 997{
997 const eio_dirent *a = (const eio_dirent *)a_; 998 return b->score - a->score ? b->score - a->score /* works because our signed char is always 0..100 */
998 const eio_dirent *b = (const eio_dirent *)b_;
999
1000 return (int)b->score - (int)a->score ? (int)b->score - (int)a->score
1001 : a->inode < b->inode ? -1 : a->inode > b->inode ? 1 : 0; /* int might be < ino_t */ 999 : a->inode < b->inode ? -1 : a->inode > b->inode ? 1 : 0;
1000}
1001
1002#define EIO_QSORT_CUTOFF 20 /* quite high, but performs well on many filesystems */
1003
1004static void
1005eio_dent_sort (eio_dirent *dents, int size)
1006{
1007 /* should be good for 2**31 entries */
1008 struct rng { int l, r; } rng [32];
1009 int i, j;
1010
1011 i = 0;
1012 rng[0].l = 0;
1013 rng[0].r = size;
1014
1015 while (expect_true (i >= 0))
1016 {
1017 int L = rng [i].l;
1018 int R = rng [i].r - 1;
1019
1020 if (expect_false (L + EIO_QSORT_CUTOFF < R))
1021 {
1022 eio_dirent piv = dents [L];
1023
1024 while (L < R)
1025 {
1026 while (eio_dent_cmp (&dents [R], &piv) >= 0 && L < R)
1027 --R;
1028
1029 if (L < R)
1030 dents [L++] = dents [R];
1031
1032 while (eio_dent_cmp (&dents [L], &piv) <= 0 && L < R)
1033 ++L;
1034
1035 if (L < R)
1036 dents [R--] = dents [L];
1037 }
1038
1039 dents [L] = piv;
1040
1041 ++i;
1042 rng [i].l = L + 1;
1043 rng [i].r = rng [i - 1].r;
1044 rng [i - 1].r = L;
1045
1046 if (rng [i].r - rng [i].l > rng [i - 1].r - rng [i - 1].l)
1047 {
1048 struct rng t;
1049
1050 t = rng [i]; rng [i] = rng [i - 1]; rng [i - 1] = t;
1051 }
1052 }
1053 else
1054 --i;
1055 }
1056
1057 /* use a simple insertion sort at the end */
1058 for (i = 1; i < size; ++i)
1059 {
1060 eio_dirent value = dents [i];
1061
1062 for (j = i - 1; j >= 0 && eio_dent_cmp (&dents [j], &value) > 0; --j)
1063 dents [j + 1] = dents [j];
1064
1065 dents [j + 1] = value;
1066 }
1002} 1067}
1003 1068
1004/* read a full directory */ 1069/* read a full directory */
1005static void 1070static void
1006eio__scandir (eio_req *req, etp_worker *self) 1071eio__scandir (eio_req *req, etp_worker *self)
1007{ 1072{
1008 DIR *dirp; 1073 DIR *dirp;
1009 EIO_STRUCT_DIRENT *entp; 1074 EIO_STRUCT_DIRENT *entp;
1010 unsigned char *name, *names; 1075 char *name, *names;
1011 int namesalloc = 4096; 1076 int namesalloc = 4096;
1012 int namesoffs = 0; 1077 int namesoffs = 0;
1013 int flags = req->int1; 1078 int flags = req->int1;
1014 eio_dirent *dents = 0; 1079 eio_dirent *dents = 0;
1015 int dentalloc = 128; 1080 int dentalloc = 128;
… …
1051 (--ent)->name = names + (size_t)ent->name; 1116 (--ent)->name = names + (size_t)ent->name;
1052 } 1117 }
1053 1118
1054 if (flags & EIO_READDIR_STAT_ORDER 1119 if (flags & EIO_READDIR_STAT_ORDER
1055 || !(~flags & (EIO_READDIR_DIRS_FIRST | EIO_READDIR_FOUND_UNKNOWN))) 1120 || !(~flags & (EIO_READDIR_DIRS_FIRST | EIO_READDIR_FOUND_UNKNOWN)))
1056 { 1121 eio_dent_sort (dents, dentoffs); /* score depends of DIRS_FIRST */
1057 /* pray your qsort doesn't use quicksort */
1058 qsort (dents, dentoffs, sizeof (*dents), eio_dent_cmp); /* score depends of DIRS_FIRST */
1059 }
1060 else if (flags & EIO_READDIR_DIRS_FIRST) 1122 else if (flags & EIO_READDIR_DIRS_FIRST)
1061 { 1123 {
1062 /* in this case, all is known, and we just put dirs first and sort them */ 1124 /* in this case, all is known, and we just put dirs first and sort them */
1063 eio_dirent *ent = dents + dentoffs; 1125 eio_dirent *ent = dents + dentoffs;
1064 eio_dirent *dir = dents; 1126 eio_dirent *dir = dents;
1065 1127
1066 /* now move dirs to the front, and non-dirs to the back */ 1128 /* now move dirs to the front, and non-dirs to the back */
1067 /* by walkign from both sides and swapping if necessary */ 1129 /* by walking from both sides and swapping if necessary */
1068 while (ent > dir) 1130 while (ent > dir)
1069 { 1131 {
1070 if (dir->type == DT_DIR) 1132 if (dir->type == DT_DIR)
1071 ++dir; 1133 ++dir;
1072 else 1134 else
… …
1083 } 1145 }
1084 } 1146 }
1085 } 1147 }
1086 1148
1087 /* now sort the dirs only */ 1149 /* now sort the dirs only */
1088 qsort (dents, dir - dents, sizeof (*dents), eio_dent_cmp); 1150 eio_dent_sort (dents, dir - dents);
1089 } 1151 }
1090 1152
1091 /* only provide the names array unless DENTS is specified */ 1153 /* only provide the names array unless DENTS is specified */
1092 if (!(flags & EIO_READDIR_DENTS)) 1154 if (!(flags & EIO_READDIR_DENTS))
1093 { 1155 {
… …
1748/* misc garbage */ 1810/* misc garbage */
1749 1811
1750ssize_t eio_sendfile_sync (int ofd, int ifd, off_t offset, size_t count) 1812ssize_t eio_sendfile_sync (int ofd, int ifd, off_t offset, size_t count)
1751{ 1813{
1752 etp_worker wrk; 1814 etp_worker wrk;
1815 ssize_t ret;
1753 1816
1754 wrk.dbuf = 0; 1817 wrk.dbuf = 0;
1755 1818
1756 eio__sendfile (ofd, ifd, offset, count, &wrk); 1819 ret = eio__sendfile (ofd, ifd, offset, count, &wrk);
1757 1820
1758 if (wrk.dbuf) 1821 if (wrk.dbuf)
1759 free (wrk.dbuf); 1822 free (wrk.dbuf);
1760}
1761 1823
1824 return ret;
1825}
1826

Diff Legend

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