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

Comparing cvsroot/libeio/eio.c (file contents):
Revision 1.34 by root, Sat Jun 6 19:57:22 2009 UTC vs.
Revision 1.41 by root, Sun Jun 14 20:36:59 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#define EIO_DENT_NUM_SCORES 9
1004
1005#define EIO_QSORT_CUTOFF 30 /* quite high, but performs well on many filesystems */
1006#define EIO_QSORT_SKIP 60 /* when to skip qsort completely */
1007
1008static void
1009eio_dent_sort (eio_dirent *dents, int size)
1010{
1011 if (size <= 1)
1012 return; /* our insertion sort relies on size > 0 */
1013
1014 if (size > EIO_QSORT_SKIP) /* skip quicksort for small directories */
1015 {
1016 /* first, use quicksort */
1017 /* should be good for 2**31 entries */
1018 int i;
1019 struct rng { eio_dirent *l, *r; } rng [32];
1020
1021 i = 0;
1022 rng[0].l = dents;
1023 rng[0].r = dents + size;
1024
1025 while (expect_true (i >= 0))
1026 {
1027 eio_dirent *L = rng [i].l;
1028 eio_dirent *R = rng [i].r - 1;
1029
1030 if (expect_false (L + EIO_QSORT_CUTOFF < R))
1031 {
1032 eio_dirent *mid = &dents [((L - dents) + (R - dents)) >> 1];
1033 eio_dirent piv = *mid; *mid = *L; *L = piv;
1034
1035 while (L < R)
1036 {
1037 while (EIO_DENT_CMP (*R, >=, piv) && L < R)
1038 --R;
1039
1040 if (L < R)
1041 *L++ = *R;
1042
1043 while (EIO_DENT_CMP (*L, <=, piv) && L < R)
1044 ++L;
1045
1046 if (L < R)
1047 *R-- = *L;
1048 }
1049
1050 *L = piv;
1051
1052 ++i;
1053 rng [i].l = L + 1;
1054 rng [i].r = rng [i - 1].r;
1055 rng [i - 1].r = L;
1056
1057 if (rng [i].r - rng [i].l > rng [i - 1].r - rng [i - 1].l)
1058 {
1059 struct rng t;
1060
1061 t = rng [i]; rng [i] = rng [i - 1]; rng [i - 1] = t;
1062 }
1063 }
1064 else
1065 --i;
1066 }
1067 }
1068
1069 /* use an insertion sort after qsort, or for small arrays */
1070 /* first move the smallest element to the front, to act as a sentinel */
1071 {
1072 int i;
1073 eio_dirent *min = dents;
1074
1075 for (i = size > EIO_QSORT_SKIP ? EIO_QSORT_CUTOFF + 1 : size; --i; )
1076 if (EIO_DENT_CMP (dents [i], <, *min))
1077 min = &dents [i];
1078
1079 /* swap elements 0 and j (minimum) */
1080 {
1081 eio_dirent tmp = *dents; *dents = *min; *min = tmp;
1082 }
1083 }
1084
1085 {
1086 /* then do standard insertion sort */
1087 eio_dirent *i, *j;
1088
1089 for (i = dents + 1; i < dents + size; ++i)
1090 {
1091 eio_dirent value = *i;
1092
1093 for (j = i - 1; EIO_DENT_CMP (*j, >, value); --j)
1094 j [1] = j [0];
1095
1096 j [1] = value;
1097 }
1098 }
1002} 1099}
1003 1100
1004/* read a full directory */ 1101/* read a full directory */
1005static void 1102static void
1006eio__scandir (eio_req *req, etp_worker *self) 1103eio__scandir (eio_req *req, etp_worker *self)
1007{ 1104{
1008 DIR *dirp; 1105 DIR *dirp;
1009 EIO_STRUCT_DIRENT *entp; 1106 EIO_STRUCT_DIRENT *entp;
1010 unsigned char *name, *names; 1107 char *name, *names;
1011 int namesalloc = 4096; 1108 int namesalloc = 4096;
1012 int namesoffs = 0; 1109 int namesoffs = 0;
1013 int flags = req->int1; 1110 int flags = req->int1;
1014 eio_dirent *dents = 0; 1111 eio_dirent *dents = 0;
1015 int dentalloc = 128; 1112 int dentalloc = 128;
… …
1051 (--ent)->name = names + (size_t)ent->name; 1148 (--ent)->name = names + (size_t)ent->name;
1052 } 1149 }
1053 1150
1054 if (flags & EIO_READDIR_STAT_ORDER 1151 if (flags & EIO_READDIR_STAT_ORDER
1055 || !(~flags & (EIO_READDIR_DIRS_FIRST | EIO_READDIR_FOUND_UNKNOWN))) 1152 || !(~flags & (EIO_READDIR_DIRS_FIRST | EIO_READDIR_FOUND_UNKNOWN)))
1056 { 1153 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) 1154 else if (flags & EIO_READDIR_DIRS_FIRST)
1061 { 1155 {
1062 /* in this case, all is known, and we just put dirs first and sort them */ 1156 /* in this case, all is known, and we just put dirs first and sort them */
1063 eio_dirent *ent = dents + dentoffs; 1157 eio_dirent *ent = dents + dentoffs;
1064 eio_dirent *dir = dents; 1158 eio_dirent *dir = dents;
1065 1159
1160 /* now move dirs to the front, and non-dirs to the back */
1161 /* by walking from both sides and swapping if necessary */
1066 while (ent > dir) 1162 while (ent > dir)
1067 { 1163 {
1068 if (dir->type == DT_DIR) 1164 if (dir->type == DT_DIR)
1165 {
1166 dir->score = 0;
1069 ++dir; 1167 ++dir;
1168 }
1070 else 1169 else
1071 { 1170 {
1072 --ent; 1171 --ent;
1073 1172
1074 if (ent->type == DT_DIR) 1173 if (ent->type == DT_DIR)
1075 { 1174 {
1076 eio_dirent tmp = *dir; 1175 eio_dirent tmp = *dir;
1077 *dir = *ent; 1176 *dir = *ent;
1078 *ent = tmp; 1177 *ent = tmp;
1079 1178
1179 dir->score = 0;
1080 ++dir; 1180 ++dir;
1081 } 1181 }
1082 } 1182 }
1083 } 1183 }
1084 1184
1085 /* now sort the dirs only */ 1185 /* now sort the dirs only */
1086 qsort (dents, dir - dents, sizeof (*dents), eio_dent_cmp); 1186 eio_dent_sort (dents, dir - dents);
1087 } 1187 }
1088 1188
1089 /* only provide the names array unless DENTS is specified */ 1189 /* only provide the names array unless DENTS is specified */
1090 if (!(flags & EIO_READDIR_DENTS)) 1190 if (!(flags & EIO_READDIR_DENTS))
1091 { 1191 {
… …
1137 1237
1138 ent = dents + dentoffs; 1238 ent = dents + dentoffs;
1139 1239
1140 ent->name = (char *)(size_t)namesoffs; /* rather dirtily we store the offset in the pointer */ 1240 ent->name = (char *)(size_t)namesoffs; /* rather dirtily we store the offset in the pointer */
1141 ent->namelen = len - 1; 1241 ent->namelen = len - 1;
1142 ent->inode = D_INO (entp); 1242 ent->inode = D_INO (entp) ? D_INO (entp) : dentoffs;
1143 1243
1144 switch (D_TYPE (entp)) 1244 switch (D_TYPE (entp))
1145 { 1245 {
1146 default: 1246 default:
1147 ent->type = EIO_DT_UNKNOWN; 1247 ent->type = EIO_DT_UNKNOWN;
… …
1197 if (flags & EIO_READDIR_DIRS_FIRST) 1297 if (flags & EIO_READDIR_DIRS_FIRST)
1198 { 1298 {
1199 if (ent->type == EIO_DT_UNKNOWN) 1299 if (ent->type == EIO_DT_UNKNOWN)
1200 { 1300 {
1201 if (*name == '.') /* leading dots are likely directories, and, in any case, rare */ 1301 if (*name == '.') /* leading dots are likely directories, and, in any case, rare */
1202 ent->score = 98; 1302 ent->score = 7;
1203 else if (!strchr (name, '.')) /* absense of dots indicate likely dirs */ 1303 else if (!strchr (name, '.')) /* absense of dots indicate likely dirs */
1204 ent->score = len <= 2 ? len + 6 : len <= 4 ? 5 : len <= 7 ? 4 : 1; /* shorter == more likely dir, but avoid too many classes */ 1304 ent->score = len <= 2 ? len + 4 : len <= 4 ? 3 : len <= 7 ? 2 : 1; /* shorter == more likely dir, but avoid too many classes */
1205 } 1305 }
1206 else if (ent->type == EIO_DT_DIR) 1306 else if (ent->type == EIO_DT_DIR)
1207 ent->score = 100; 1307 ent->score = 8;
1208 } 1308 }
1209 } 1309 }
1210 1310
1211 namesoffs += len; 1311 namesoffs += len;
1212 ++dentoffs; 1312 ++dentoffs;
1213 } 1313 }
1314
1315 if (EIO_CANCELLED (req))
1316 {
1317 errno = ECANCELED;
1318 break;
1319 }
1214 } 1320 }
1215 else
1216 req->result = -1;
1217} 1321}
1218 1322
1219#if !(_POSIX_MAPPED_FILES && _POSIX_SYNCHRONIZED_IO) 1323#if !(_POSIX_MAPPED_FILES && _POSIX_SYNCHRONIZED_IO)
1220# undef msync 1324# undef msync
1221# define msync(a,b,c) ((errno = ENOSYS), -1) 1325# define msync(a,b,c) ((errno = ENOSYS), -1)
… …
1742/* misc garbage */ 1846/* misc garbage */
1743 1847
1744ssize_t eio_sendfile_sync (int ofd, int ifd, off_t offset, size_t count) 1848ssize_t eio_sendfile_sync (int ofd, int ifd, off_t offset, size_t count)
1745{ 1849{
1746 etp_worker wrk; 1850 etp_worker wrk;
1851 ssize_t ret;
1747 1852
1748 wrk.dbuf = 0; 1853 wrk.dbuf = 0;
1749 1854
1750 eio__sendfile (ofd, ifd, offset, count, &wrk); 1855 ret = eio__sendfile (ofd, ifd, offset, count, &wrk);
1751 1856
1752 if (wrk.dbuf) 1857 if (wrk.dbuf)
1753 free (wrk.dbuf); 1858 free (wrk.dbuf);
1754}
1755 1859
1860 return ret;
1861}
1862

Diff Legend

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