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.36 by root, Fri Jun 12 00:43:16 2009 UTC vs.
Revision 1.38 by root, Fri Jun 12 20:01:42 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 int i, j;
1008
1009 if (size > EIO_QSORT_CUTOFF * 3) /* skip quicksort for small directories */
1010 {
1011 /* first, use quicksort */
1012 /* should be good for 2**31 entries */
1013 struct rng { int l, r; } rng [32];
1014
1015 i = 0;
1016 rng[0].l = 0;
1017 rng[0].r = size;
1018
1019 while (expect_true (i >= 0))
1020 {
1021 int L = rng [i].l;
1022 int R = rng [i].r - 1;
1023
1024 if (expect_false (L + EIO_QSORT_CUTOFF < R))
1025 {
1026 eio_dirent piv = dents [L];
1027
1028 while (L < R)
1029 {
1030 while (eio_dent_cmp (&dents [R], &piv) >= 0 && L < R)
1031 --R;
1032
1033 if (L < R)
1034 dents [L++] = dents [R];
1035
1036 while (eio_dent_cmp (&dents [L], &piv) <= 0 && L < R)
1037 ++L;
1038
1039 if (L < R)
1040 dents [R--] = dents [L];
1041 }
1042
1043 dents [L] = piv;
1044
1045 ++i;
1046 rng [i].l = L + 1;
1047 rng [i].r = rng [i - 1].r;
1048 rng [i - 1].r = L;
1049
1050 if (rng [i].r - rng [i].l > rng [i - 1].r - rng [i - 1].l)
1051 {
1052 struct rng t;
1053
1054 t = rng [i]; rng [i] = rng [i - 1]; rng [i - 1] = t;
1055 }
1056 }
1057 else
1058 --i;
1059 }
1060 }
1061
1062 /* use a simple insertion sort at the end */
1063 for (i = 1; i < size; ++i)
1064 {
1065 eio_dirent value = dents [i];
1066
1067 for (j = i - 1; j >= 0 && eio_dent_cmp (&dents [j], &value) > 0; --j)
1068 dents [j + 1] = dents [j];
1069
1070 dents [j + 1] = value;
1071 }
1002} 1072}
1003 1073
1004/* read a full directory */ 1074/* read a full directory */
1005static void 1075static void
1006eio__scandir (eio_req *req, etp_worker *self) 1076eio__scandir (eio_req *req, etp_worker *self)
1007{ 1077{
1008 DIR *dirp; 1078 DIR *dirp;
1009 EIO_STRUCT_DIRENT *entp; 1079 EIO_STRUCT_DIRENT *entp;
1010 unsigned char *name, *names; 1080 char *name, *names;
1011 int namesalloc = 4096; 1081 int namesalloc = 4096;
1012 int namesoffs = 0; 1082 int namesoffs = 0;
1013 int flags = req->int1; 1083 int flags = req->int1;
1014 eio_dirent *dents = 0; 1084 eio_dirent *dents = 0;
1015 int dentalloc = 128; 1085 int dentalloc = 128;
… …
1051 (--ent)->name = names + (size_t)ent->name; 1121 (--ent)->name = names + (size_t)ent->name;
1052 } 1122 }
1053 1123
1054 if (flags & EIO_READDIR_STAT_ORDER 1124 if (flags & EIO_READDIR_STAT_ORDER
1055 || !(~flags & (EIO_READDIR_DIRS_FIRST | EIO_READDIR_FOUND_UNKNOWN))) 1125 || !(~flags & (EIO_READDIR_DIRS_FIRST | EIO_READDIR_FOUND_UNKNOWN)))
1056 { 1126 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) 1127 else if (flags & EIO_READDIR_DIRS_FIRST)
1061 { 1128 {
1062 /* in this case, all is known, and we just put dirs first and sort them */ 1129 /* in this case, all is known, and we just put dirs first and sort them */
1063 eio_dirent *ent = dents + dentoffs; 1130 eio_dirent *ent = dents + dentoffs;
1064 eio_dirent *dir = dents; 1131 eio_dirent *dir = dents;
1065 1132
1066 /* now move dirs to the front, and non-dirs to the back */ 1133 /* now move dirs to the front, and non-dirs to the back */
1067 /* by walkign from both sides and swapping if necessary */ 1134 /* by walking from both sides and swapping if necessary */
1068 while (ent > dir) 1135 while (ent > dir)
1069 { 1136 {
1070 if (dir->type == DT_DIR) 1137 if (dir->type == DT_DIR)
1071 ++dir; 1138 ++dir;
1072 else 1139 else
… …
1083 } 1150 }
1084 } 1151 }
1085 } 1152 }
1086 1153
1087 /* now sort the dirs only */ 1154 /* now sort the dirs only */
1088 qsort (dents, dir - dents, sizeof (*dents), eio_dent_cmp); 1155 eio_dent_sort (dents, dir - dents);
1089 } 1156 }
1090 1157
1091 /* only provide the names array unless DENTS is specified */ 1158 /* only provide the names array unless DENTS is specified */
1092 if (!(flags & EIO_READDIR_DENTS)) 1159 if (!(flags & EIO_READDIR_DENTS))
1093 { 1160 {
… …
1748/* misc garbage */ 1815/* misc garbage */
1749 1816
1750ssize_t eio_sendfile_sync (int ofd, int ifd, off_t offset, size_t count) 1817ssize_t eio_sendfile_sync (int ofd, int ifd, off_t offset, size_t count)
1751{ 1818{
1752 etp_worker wrk; 1819 etp_worker wrk;
1820 ssize_t ret;
1753 1821
1754 wrk.dbuf = 0; 1822 wrk.dbuf = 0;
1755 1823
1756 eio__sendfile (ofd, ifd, offset, count, &wrk); 1824 ret = eio__sendfile (ofd, ifd, offset, count, &wrk);
1757 1825
1758 if (wrk.dbuf) 1826 if (wrk.dbuf)
1759 free (wrk.dbuf); 1827 free (wrk.dbuf);
1760}
1761 1828
1829 return ret;
1830}
1831

Diff Legend

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