[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Final patch version (was Re: [patch #3596] Sort directories before f
From: |
Francesco Montorsi |
Subject: |
Re: Final patch version (was Re: [patch #3596] Sort directories before files in "ls") |
Date: |
Thu, 09 Feb 2006 23:46:00 +0100 |
User-agent: |
Mozilla Thunderbird 1.5 (X11/20051201) |
Hi,
I've got the reply from FSF copyright !
Finally copyright stuff should be okay.
So, I repost the patch ;)
Francesco
ChangeLog changes:
2005-12-27 Francesco Montorsi <address@hidden>
Add a --group-directories-first option to ls to group
directories before files.
* NEWS: Document new option.
* src/ls.c (sort_type): Rearrange to use as an array index when
choosing sort function; added new sort_numtypes member for
compile-time check.
(time_type): added new time_numtypes member for compile-time check
(directories_first): New variable.
(GROUP_DIRECTORIES_FIRST_OPTION): New enum.
(long_options): Add --directories-first.
(main): Support new option.
(is_directory): New function.
(extract_dirs_from_files): Use it.
(DIRFIRST_CHECK, DEFINE_SORT_FUNCTIONS)
(LIST_SORTFUNCTION_VARIANTS): New macros.
(sort_functions): New variable.
(sort_files): Use it.
(usage): Document new option.
* doc/coreutils.texi: Documented the new option
Index: NEWS
===================================================================
RCS file: /sources/coreutils/coreutils/NEWS,v
retrieving revision 1.354
diff -b -u -2 -r1.354 NEWS
--- NEWS 15 Dec 2005 12:24:54 -0000 1.354
+++ NEWS 1 Jan 2006 15:36:45 -0000
@@ -24,4 +24,7 @@
attempts to have the default be the best of both worlds.
+ ls now supports the '--group-directories-first' option to group directories
+ before files.
+
sort now reports incompatible options (e.g., -i and -n) rather than
silently ignoring one of them.
Index: THANKS
===================================================================
RCS file: /sources/coreutils/coreutils/THANKS,v
retrieving revision 1.413
diff -b -u -2 -r1.413 THANKS
--- THANKS 9 Dec 2005 16:27:26 -0000 1.413
+++ THANKS 1 Jan 2006 15:36:46 -0000
@@ -152,4 +152,5 @@
Fletcher Mattox address@hidden
Florin Iucha address@hidden
+Francesco Montorsi address@hidden
François Pinard address@hidden
Frank Adler address@hidden
Index: doc/coreutils.texi
===================================================================
RCS file: /sources/coreutils/coreutils/doc/coreutils.texi,v
retrieving revision 1.302
diff -b -u -2 -r1.302 coreutils.texi
--- doc/coreutils.texi 17 Dec 2005 10:50:00 -0000 1.302
+++ doc/coreutils.texi 1 Jan 2006 15:37:01 -0000
@@ -5470,4 +5470,12 @@
@option{--dereference-command-line} (@option{-H})).
address@hidden --group-directories-first
address@hidden --group-directories-first
+Groups all the directories before the files and then sorts the
+directories and the files separately using the selected sort key
+(see --sort option).
+That is, this option acts as primary sort key using the value of
+the --sort option as secondary key.
+
@item --hide=PATTERN
@opindex address@hidden
Index: src/ls.c
===================================================================
RCS file: /sources/coreutils/coreutils/src/ls.c,v
retrieving revision 1.404
diff -b -u -2 -r1.404 ls.c
--- src/ls.c 17 Dec 2005 10:33:08 -0000 1.404
+++ src/ls.c 1 Jan 2006 15:37:06 -0000
@@ -399,5 +399,7 @@
ARGMATCH_VERIFY (time_style_args, time_style_types);
-/* Type of time to print or sort by. Controlled by -c and -u. */
+/* Type of time to print or sort by. Controlled by -c and -u.
+ The values of each item of this enum are important since they are
+ used as indices in the sort functions array (see sort_files()). */
enum time_type
@@ -405,19 +407,23 @@
time_mtime, /* default */
time_ctime, /* -c */
- time_atime /* -u */
+ time_atime, /* -u */
+ time_numtypes /* the number of elements of this enum */
};
static enum time_type time_type;
-/* The file characteristic to sort by. Controlled by -t, -S, -U, -X, -v. */
+/* The file characteristic to sort by. Controlled by -t, -S, -U, -X, -v.
+ The values of each item of this enum are important since they are
+ used as indices in the sort functions array (see sort_files()). */
enum sort_type
{
- sort_none, /* -U */
+ sort_none = -1, /* -U */
sort_name, /* default */
sort_extension, /* -X */
- sort_time, /* -t */
sort_size, /* -S */
- sort_version /* -v */
+ sort_version, /* -v */
+ sort_time, /* -t */
+ sort_numtypes /* the number of elements of this enum */
};
@@ -592,4 +598,8 @@
static bool immediate_dirs;
+/* True means that directories are grouped before files. */
+
+static bool directories_first;
+
/* Which files to ignore. */
@@ -731,4 +741,5 @@
FORMAT_OPTION,
FULL_TIME_OPTION,
+ GROUP_DIRECTORIES_FIRST_OPTION,
HIDE_OPTION,
INDICATOR_STYLE_OPTION,
@@ -752,4 +763,5 @@
{"dired", no_argument, NULL, 'D'},
{"full-time", no_argument, NULL, FULL_TIME_OPTION},
+ {"group-directories-first", no_argument, NULL,
GROUP_DIRECTORIES_FIRST_OPTION},
{"human-readable", no_argument, NULL, 'h'},
{"inode", no_argument, NULL, 'i'},
@@ -1224,5 +1236,6 @@
|| format == long_format
|| dereference == DEREF_ALWAYS
- || print_block_size || print_inode;
+ || print_block_size || print_inode
+ || directories_first;
format_needs_type = (!format_needs_stat
&& (recursive || print_with_color
@@ -1713,4 +1726,8 @@
break;
+ case GROUP_DIRECTORIES_FIRST_OPTION:
+ directories_first = true;
+ break;
+
case TIME_OPTION:
time_type = XARGMATCH ("--time", optarg, time_args, time_types);
@@ -2728,4 +2745,13 @@
}
+
+/* Returns true if the given fileinfo refers to a directory */
+static bool
+is_directory (const struct fileinfo *f)
+{
+ return f->filetype == directory || f->filetype == arg_directory;
+}
+
+
#ifdef S_ISLNK
@@ -2810,7 +2836,7 @@
order. */
for (i = files_index; i-- != 0; )
- if ((files[i].filetype == directory || files[i].filetype == arg_directory)
- && (!ignore_dot_and_dot_dot
- || !basename_is_dot_or_dotdot (files[i].name)))
+ if (is_directory(&files[i])
+ && (! ignore_dot_and_dot_dot
+ || ! basename_is_dot_or_dotdot (files[i].name)))
{
if (!dirname || files[i].name[0] == '/')
@@ -2868,4 +2894,49 @@
typedef void const *V;
+typedef int (*qsortFunc)(V a, V b);
+
+/* Used below in DEFINE_SORT_FUNCTIONS for _df_ sort function variants.
+ The do { ... } while(0) makes it possible to use the macro more like
+ a statement, without violating C89 rules: */
+#define DIRFIRST_CHECK(a, b) \
+ do { \
+ bool a_is_dir = is_directory((struct fileinfo const *)a); \
+ bool b_is_dir = is_directory((struct fileinfo const *)b); \
+ if (a_is_dir && !b_is_dir) \
+ return -1; /* a goes before b */ \
+ if (!a_is_dir && b_is_dir) \
+ return 1; /* b goes before a */ \
+ } while (0)
+
+/*
+ Defines the 8 different sort function variants required for each sortkey.
+ The 'basefunc' should be an inline function so that compiler will be able
+ to optimize all these functions. The 'basename' argument will be prefixed
+ with the '[rev_][x]str{cmp|coll}[_df]_' string to create the function name.
+*/
+#define DEFINE_SORT_FUNCTIONS(basename, basefunc) \
+ /* direct, non-dirfirst versions */ \
+ static int xstrcoll_##basename (V a, V b) \
+ { return basefunc (a, b, xstrcoll); } \
+ static int strcmp_##basename (V a, V b) \
+ { return basefunc (a, b, strcmp); } \
+ \
+ /* reverse, non-dirfirst versions */ \
+ static int rev_xstrcoll_##basename (V a, V b) \
+ { return basefunc (b, a, xstrcoll); } \
+ static int rev_strcmp_##basename (V a, V b) \
+ { return basefunc (b, a, strcmp); } \
+ \
+ /* direct, dirfirst versions */ \
+ static int xstrcoll_df_##basename (V a, V b) \
+ { DIRFIRST_CHECK (a, b); return basefunc (a, b, xstrcoll); } \
+ static int strcmp_df_##basename (V a, V b) \
+ { DIRFIRST_CHECK (a, b); return basefunc (a, b, strcmp); } \
+ \
+ /* reverse, dirfirst versions */ \
+ static int rev_xstrcoll_df_##basename (V a, V b) \
+ { DIRFIRST_CHECK (a, b); return basefunc (b, a, xstrcoll); } \
+ static int rev_strcmp_df_##basename (V a, V b) \
+ { DIRFIRST_CHECK (a, b); return basefunc (b, a, strcmp); }
static inline int
@@ -2877,8 +2948,4 @@
return diff ? diff : cmp (a->name, b->name);
}
-static int compare_ctime (V a, V b) { return cmp_ctime (a, b, xstrcoll); }
-static int compstr_ctime (V a, V b) { return cmp_ctime (a, b, strcmp); }
-static int rev_cmp_ctime (V a, V b) { return compare_ctime (b, a); }
-static int rev_str_ctime (V a, V b) { return compstr_ctime (b, a); }
static inline int
@@ -2890,8 +2957,4 @@
return diff ? diff : cmp (a->name, b->name);
}
-static int compare_mtime (V a, V b) { return cmp_mtime (a, b, xstrcoll); }
-static int compstr_mtime (V a, V b) { return cmp_mtime (a, b, strcmp); }
-static int rev_cmp_mtime (V a, V b) { return compare_mtime (b, a); }
-static int rev_str_mtime (V a, V b) { return compstr_mtime (b, a); }
static inline int
@@ -2903,8 +2966,4 @@
return diff ? diff : cmp (a->name, b->name);
}
-static int compare_atime (V a, V b) { return cmp_atime (a, b, xstrcoll); }
-static int compstr_atime (V a, V b) { return cmp_atime (a, b, strcmp); }
-static int rev_cmp_atime (V a, V b) { return compare_atime (b, a); }
-static int rev_str_atime (V a, V b) { return compstr_atime (b, a); }
static inline int
@@ -2915,16 +2974,4 @@
return diff ? diff : cmp (a->name, b->name);
}
-static int compare_size (V a, V b) { return cmp_size (a, b, xstrcoll); }
-static int compstr_size (V a, V b) { return cmp_size (a, b, strcmp); }
-static int rev_cmp_size (V a, V b) { return compare_size (b, a); }
-static int rev_str_size (V a, V b) { return compstr_size (b, a); }
-
-static inline int
-cmp_version (struct fileinfo const *a, struct fileinfo const *b)
-{
- return strverscmp (a->name, b->name);
-}
-static int compare_version (V a, V b) { return cmp_version (a, b); }
-static int rev_cmp_version (V a, V b) { return compare_version (b, a); }
static inline int
@@ -2934,8 +2981,4 @@
return cmp (a->name, b->name);
}
-static int compare_name (V a, V b) { return cmp_name (a, b, xstrcoll); }
-static int compstr_name (V a, V b) { return cmp_name (a, b, strcmp); }
-static int rev_cmp_name (V a, V b) { return compare_name (b, a); }
-static int rev_str_name (V a, V b) { return compstr_name (b, a); }
/* Compare file extensions. Files with no extension are `smallest'.
@@ -2951,8 +2994,103 @@
return diff ? diff : cmp (a->name, b->name);
}
-static int compare_extension (V a, V b) { return cmp_extension (a, b,
xstrcoll); }
-static int compstr_extension (V a, V b) { return cmp_extension (a, b, strcmp);
}
-static int rev_cmp_extension (V a, V b) { return compare_extension (b, a); }
-static int rev_str_extension (V a, V b) { return compstr_extension (b, a); }
+
+
+DEFINE_SORT_FUNCTIONS(ctime, cmp_ctime)
+DEFINE_SORT_FUNCTIONS(mtime, cmp_mtime)
+DEFINE_SORT_FUNCTIONS(atime, cmp_atime)
+DEFINE_SORT_FUNCTIONS(size, cmp_size)
+DEFINE_SORT_FUNCTIONS(name, cmp_name)
+DEFINE_SORT_FUNCTIONS(extension, cmp_extension)
+
+
+
+/* Compares file versions.
+ Unlike all other compare functions above, cmp_version only depends
+ on strverscmp, which does not fail (even for locale reasons), and does not
+ need a secondary sort key.
+ All the other sort options, in fact, need an xstrcoll and strcmp variants,
+ because they all use a string comparison (either as the primary or secondary
+ sort key), and xstrcoll has the ability to do a longjmp if strcoll fails for
+ locale reasons. Last, strverscmp is ALWAYS available in coreutils,
+ thanks to the gnulib library. */
+static inline int
+cmp_version (struct fileinfo const *a, struct fileinfo const *b)
+{
+ return strverscmp (a->name, b->name);
+}
+
+static int xstrcoll_version (V a, V b)
+{ return cmp_version (a, b); }
+static int rev_xstrcoll_version (V a, V b)
+{ return cmp_version (b, a); }
+static int xstrcoll_df_version (V a, V b)
+{ DIRFIRST_CHECK(a,b); return cmp_version (a, b); }
+static int rev_xstrcoll_df_version (V a, V b)
+{ DIRFIRST_CHECK(a,b); return cmp_version (b, a); }
+
+
+/*
+ We have 2^3 different variants for each sortkey function
+ (for 3 indipendent sort modes).
+ The function pointers stored in this array must be dereferenced as:
+
+ sort_variants[sort_key][use_strcmp][reverse][dirs_first]
+
+ Note that the order in which sortkeys are listed in the function pointer
+ array below is defined by the order of the elements in the time_type and
+ sort_type enums !
+*/
+
+#define LIST_SORTFUNCTION_VARIANTS(basename) \
+ { \
+ { \
+ { xstrcoll_##basename, xstrcoll_df_##basename }, \
+ { rev_xstrcoll_##basename, rev_xstrcoll_df_##basename }, \
+ }, \
+ { \
+ { strcmp_##basename, strcmp_df_##basename }, \
+ { rev_strcmp_##basename, rev_strcmp_df_##basename }, \
+ } \
+ }
+
+qsortFunc sort_functions[][2][2][2] = {
+ LIST_SORTFUNCTION_VARIANTS(name),
+ LIST_SORTFUNCTION_VARIANTS(extension),
+ LIST_SORTFUNCTION_VARIANTS(size),
+
+ {
+ {
+ { xstrcoll_version, xstrcoll_df_version },
+ { rev_xstrcoll_version, rev_xstrcoll_df_version },
+ },
+
+ /* We use NULL for the strcmp variants of version comparison
+ since as explained in cmp_version definition, version comparison
+ does not rely on xstrcoll, so it will never longjmp, and never
+ need to try the strcmp fallback. */
+ {
+ { NULL, NULL },
+ { NULL, NULL },
+ }
+ },
+
+ /* last are time sort functions */
+ LIST_SORTFUNCTION_VARIANTS(mtime),
+ LIST_SORTFUNCTION_VARIANTS(ctime),
+ LIST_SORTFUNCTION_VARIANTS(atime)
+ };
+
+/*
+ The number of sortkeys are calculated as
+ the number of elements in the sort_type enum (i.e. sort_numtypes) +
+ the number of elements in the time_type enum (i.e. time_numtypes) - 1
+ This is because when sort_type==sort_time, we have up to
+ time_numtypes possible sortkeys.
+
+ This line verifies at compile-time that the array of sort functions has been
+ initialized for all possible sortkeys.
+*/
+verify (ARRAY_CARDINALITY (sort_functions) == sort_numtypes + time_numtypes -
1 );
+
/* Sort the files now in the table. */
@@ -2961,5 +3099,8 @@
sort_files (void)
{
- int (*func) (V, V);
+ bool use_strcmp;
+
+ if (sort_type == sort_none)
+ return;
/* Try strcoll. If it fails, fall back on strcmp. We can't safely
@@ -2969,76 +3110,20 @@
if (! setjmp (failed_strcoll))
- {
- switch (sort_type)
- {
- case sort_none:
- return;
- case sort_time:
- switch (time_type)
- {
- case time_ctime:
- func = sort_reverse ? rev_cmp_ctime : compare_ctime;
- break;
- case time_mtime:
- func = sort_reverse ? rev_cmp_mtime : compare_mtime;
- break;
- case time_atime:
- func = sort_reverse ? rev_cmp_atime : compare_atime;
- break;
- default:
- abort ();
- }
- break;
- case sort_name:
- func = sort_reverse ? rev_cmp_name : compare_name;
- break;
- case sort_extension:
- func = sort_reverse ? rev_cmp_extension : compare_extension;
- break;
- case sort_size:
- func = sort_reverse ? rev_cmp_size : compare_size;
- break;
- case sort_version:
- func = sort_reverse ? rev_cmp_version : compare_version;
- break;
- default:
- abort ();
- }
- }
+ use_strcmp = false; /* strcoll() did not failed ! */
else
{
- switch (sort_type)
- {
- case sort_time:
- switch (time_type)
- {
- case time_ctime:
- func = sort_reverse ? rev_str_ctime : compstr_ctime;
- break;
- case time_mtime:
- func = sort_reverse ? rev_str_mtime : compstr_mtime;
- break;
- case time_atime:
- func = sort_reverse ? rev_str_atime : compstr_atime;
- break;
- default:
- abort ();
- }
- break;
- case sort_name:
- func = sort_reverse ? rev_str_name : compstr_name;
- break;
- case sort_extension:
- func = sort_reverse ? rev_str_extension : compstr_extension;
- break;
- case sort_size:
- func = sort_reverse ? rev_str_size : compstr_size;
- break;
- default:
- abort ();
- }
+ use_strcmp = true;
+ if (sort_type == sort_version)
+ abort();
}
- qsort (files, files_index, sizeof *files, func);
+ /* when sort_type == sort_time we need to use time_type as subindex. */
+ int timeoffset = 0;
+ if (sort_type == sort_time)
+ timeoffset = time_type;
+
+ qsort (files, files_index, sizeof *files,
+ sort_functions[sort_type + timeoffset][use_strcmp][sort_reverse]
+ [directories_first]);
}
@@ -4147,4 +4232,10 @@
fputs (_("\
-g like -l, but do not list owner\n\
+"), stdout);
+ fputs(_("\
+ --group-directories-first\n\
+ group directories before files\n\
+"), stdout);
+ fputs(_("\
-G, --no-group like -l, but do not list group\n\
-h, --human-readable with -l, print sizes in human readable format\n\