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

Comparing libeio/eio.c (file contents):
Revision 1.33 by root, Sat Jun 6 19:44:17 2009 UTC vs.
Revision 1.39 by root, Sat Jun 13 03:59:04 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_DENT_CMP(i,op,j) eio_dent_cmp (&i, &j) op 0
1003
1004#define EIO_QSORT_CUTOFF 30 /* quite high, but performs well on many filesystems */
1005#define EIO_QSORT_SKIP 60 /* when to skip qsort completely */
1006
1007static void
1008eio_dent_sort (eio_dirent *dents, int size)
1009{
1010 int i, j;
1011
1012 if (size <= 1)
1013 return; /* our insertion sort relies on size > 0 */
1014
1015 if (size > EIO_QSORT_SKIP) /* skip quicksort for small directories */
1016 {
1017 /* first, use quicksort */
1018 /* should be good for 2**31 entries */
1019 struct rng { int l, r; } rng [32];
1020
1021 i = 0;
1022 rng[0].l = 0;
1023 rng[0].r = size;
1024
1025 while (expect_true (i >= 0))
1026 {
1027 int L = rng [i].l;
1028 int R = rng [i].r - 1;
1029
1030 if (expect_false (L + EIO_QSORT_CUTOFF < R))
1031 {
1032 eio_dirent piv = dents [L];
1033
1034 while (L < R)
1035 {
1036 while (EIO_DENT_CMP (dents [R], >=, piv) && L < R)
1037 --R;
1038
1039 if (L < R)
1040 dents [L++] = dents [R];
1041
1042 while (EIO_DENT_CMP (dents [L], <=, piv) && L < R)
1043 ++L;
1044
1045 if (L < R)
1046 dents [R--] = dents [L];
1047 }
1048
1049 dents [L] = piv;
1050
1051 ++i;
1052 rng [i].l = L + 1;
1053 rng [i].r = rng [i - 1].r;
1054 rng [i - 1].r = L;
1055
1056 if (rng [i].r - rng [i].l > rng [i - 1].r - rng [i - 1].l)
1057 {
1058 struct rng t;
1059
1060 t = rng [i]; rng [i] = rng [i - 1]; rng [i - 1] = t;
1061 }
1062 }
1063 else
1064 --i;
1065 }
1066 }
1067
1068 /* use an insertion sort after qsort, or for small arrays */
1069 /* first move the smallest element to the front, to act as a sentinel */
1070 {
1071 int min = 0;
1072
1073 for (i = size > EIO_QSORT_SKIP ? EIO_QSORT_CUTOFF : size; --i; )
1074 if (EIO_DENT_CMP (dents [i], <, dents [min]))
1075 min = i;
1076
1077 /* swap elements 0 and j (minimum) */
1078 {
1079 eio_dirent tmp = dents [0]; dents [0] = dents [min]; dents [min] = tmp;
1080 }
1081 }
1082
1083 /* then do standard insertion sort */
1084 for (i = 1; i < size; ++i)
1085 {
1086 eio_dirent value = dents [i];
1087
1088 for (j = i - 1; EIO_DENT_CMP (dents [j], >, value); --j)
1089 dents [j + 1] = dents [j];
1090
1091 dents [j + 1] = value;
1092 }
1002} 1093}
1003 1094
1004/* read a full directory */ 1095/* read a full directory */
1005static void 1096static void
1006eio__scandir (eio_req *req, etp_worker *self) 1097eio__scandir (eio_req *req, etp_worker *self)
1007{ 1098{
1008 DIR *dirp; 1099 DIR *dirp;
1009 EIO_STRUCT_DIRENT *entp; 1100 EIO_STRUCT_DIRENT *entp;
1010 unsigned char *name, *names; 1101 char *name, *names;
1011 int namesalloc = 4096; 1102 int namesalloc = 4096;
1012 int namesoffs = 0; 1103 int namesoffs = 0;
1013 int flags = req->int1; 1104 int flags = req->int1;
1014 eio_dirent *dents = 0; 1105 eio_dirent *dents = 0;
1015 int dentalloc = 128; 1106 int dentalloc = 128;
… …
1051 (--ent)->name = names + (size_t)ent->name; 1142 (--ent)->name = names + (size_t)ent->name;
1052 } 1143 }
1053 1144
1054 if (flags & EIO_READDIR_STAT_ORDER 1145 if (flags & EIO_READDIR_STAT_ORDER
1055 || !(~flags & (EIO_READDIR_DIRS_FIRST | EIO_READDIR_FOUND_UNKNOWN))) 1146 || !(~flags & (EIO_READDIR_DIRS_FIRST | EIO_READDIR_FOUND_UNKNOWN)))
1056 { 1147 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) 1148 else if (flags & EIO_READDIR_DIRS_FIRST)
1061 { 1149 {
1062 /* in this case, all is known, and we just put dirs first and sort them */ 1150 /* in this case, all is known, and we just put dirs first and sort them */
1063 eio_dirent *ent = dents + dentoffs; 1151 eio_dirent *ent = dents + dentoffs;
1064 eio_dirent *dir = dents; 1152 eio_dirent *dir = dents;
1065 1153
1154 /* now move dirs to the front, and non-dirs to the back */
1155 /* by walking from both sides and swapping if necessary */
1066 while (ent > dir) 1156 while (ent > dir)
1067 { 1157 {
1068 if (dir->type == DT_DIR) 1158 if (dir->type == DT_DIR)
1069 ++dir; 1159 ++dir;
1070 else 1160 else
… …
1081 } 1171 }
1082 } 1172 }
1083 } 1173 }
1084 1174
1085 /* now sort the dirs only */ 1175 /* now sort the dirs only */
1086 qsort (dents, dir - dents, sizeof (*dents), eio_dent_cmp); 1176 eio_dent_sort (dents, dir - dents);
1087 } 1177 }
1088 1178
1089 /* only provide the names array unless DENTS is specified */ 1179 /* only provide the names array unless DENTS is specified */
1090 if (!(flags & EIO_READDIR_DENTS)) 1180 if (!(flags & EIO_READDIR_DENTS))
1091 { 1181 {
… …
1199 if (ent->type == EIO_DT_UNKNOWN) 1289 if (ent->type == EIO_DT_UNKNOWN)
1200 { 1290 {
1201 if (*name == '.') /* leading dots are likely directories, and, in any case, rare */ 1291 if (*name == '.') /* leading dots are likely directories, and, in any case, rare */
1202 ent->score = 98; 1292 ent->score = 98;
1203 else if (!strchr (name, '.')) /* absense of dots indicate likely dirs */ 1293 else if (!strchr (name, '.')) /* absense of dots indicate likely dirs */
1204 ent->score = len <= 2 ? len + 60 : len <= 4 ? 50 : len <= 7 ? 40 : 10; /* shorter == more likely dir, but avoid too many classes */ 1294 ent->score = len <= 2 ? len + 6 : len <= 4 ? 5 : len <= 7 ? 4 : 1; /* shorter == more likely dir, but avoid too many classes */
1205 } 1295 }
1206 else if (ent->type == EIO_DT_DIR) 1296 else if (ent->type == EIO_DT_DIR)
1207 ent->score = 100; 1297 ent->score = 100;
1208 } 1298 }
1209 } 1299 }
1210 1300
1211 namesoffs += len; 1301 namesoffs += len;
1212 ++dentoffs; 1302 ++dentoffs;
1213 } 1303 }
1304
1305 if (EIO_CANCELLED (req))
1306 {
1307 errno = ECANCELED;
1308 break;
1309 }
1214 } 1310 }
1215 else
1216 req->result = -1;
1217} 1311}
1218 1312
1219#if !(_POSIX_MAPPED_FILES && _POSIX_SYNCHRONIZED_IO) 1313#if !(_POSIX_MAPPED_FILES && _POSIX_SYNCHRONIZED_IO)
1220# undef msync 1314# undef msync
1221# define msync(a,b,c) ((errno = ENOSYS), -1) 1315# define msync(a,b,c) ((errno = ENOSYS), -1)
… …
1742/* misc garbage */ 1836/* misc garbage */
1743 1837
1744ssize_t eio_sendfile_sync (int ofd, int ifd, off_t offset, size_t count) 1838ssize_t eio_sendfile_sync (int ofd, int ifd, off_t offset, size_t count)
1745{ 1839{
1746 etp_worker wrk; 1840 etp_worker wrk;
1841 ssize_t ret;
1747 1842
1748 wrk.dbuf = 0; 1843 wrk.dbuf = 0;
1749 1844
1750 eio__sendfile (ofd, ifd, offset, count, &wrk); 1845 ret = eio__sendfile (ofd, ifd, offset, count, &wrk);
1751 1846
1752 if (wrk.dbuf) 1847 if (wrk.dbuf)
1753 free (wrk.dbuf); 1848 free (wrk.dbuf);
1754}
1755 1849
1850 return ret;
1851}
1852

Diff Legend

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