diff -Nur coreutils-5.0.orig/lib/xalloc.h coreutils-5.0/lib/xalloc.h --- coreutils-5.0.orig/lib/xalloc.h Tue Oct 31 08:09:56 2000 +++ coreutils-5.0/lib/xalloc.h Mon Dec 1 16:46:22 2003 @@ -56,32 +56,23 @@ memory allocation failure. */ extern void xalloc_die PARAMS ((void)) ATTRIBUTE_NORETURN; -void *xmalloc PARAMS ((size_t n)); +void *xmalloc PARAMS ((size_t s)); +void *xnmalloc PARAMS ((size_t n, size_t s)); +void *xzalloc PARAMS ((size_t s)); void *xcalloc PARAMS ((size_t n, size_t s)); -void *xrealloc PARAMS ((void *p, size_t n)); +void *xrealloc PARAMS ((void *p, size_t s)); +void *xnrealloc PARAMS ((void *p, size_t n, size_t s)); char *xstrdup PARAMS ((const char *str)); +void *xclone PARAMS ((void const *p, size_t s)); -# define XMALLOC(Type, N_items) ((Type *) xmalloc (sizeof (Type) * (N_items))) -# define XCALLOC(Type, N_items) ((Type *) xcalloc (sizeof (Type), (N_items))) -# define XREALLOC(Ptr, Type, N_items) \ - ((Type *) xrealloc ((void *) (Ptr), sizeof (Type) * (N_items))) - -/* Declare and alloc memory for VAR of type TYPE. */ -# define NEW(Type, Var) Type *(Var) = XMALLOC (Type, 1) - -/* Free VAR only if non NULL. */ -# define XFREE(Var) \ - do { \ - if (Var) \ - free (Var); \ - } while (0) - -/* Return a pointer to a malloc'ed copy of the array SRC of NUM elements. */ -# define CCLONE(Src, Num) \ - (memcpy (xmalloc (sizeof (*Src) * (Num)), (Src), sizeof (*Src) * (Num))) - -/* Return a malloc'ed copy of SRC. */ -# define CLONE(Src) CCLONE (Src, 1) - +/* These macros are deprecated; they will go away soon, and are retained + temporarily only to ease conversion to the functions described above. */ +# define CCLONE(p, n) xclone (p, (n) * sizeof *(p)) +# define CLONE(p) xclone (p, sizeof *(p)) +# define NEW(type, var) type *var = xmalloc (sizeof (type)) +# define XCALLOC(type, n) xcalloc (n, sizeof (type)) +# define XMALLOC(type, n) xnmalloc (n, sizeof (type)) +# define XREALLOC(p, type, n) xnrealloc (p, n, sizeof (type)) +# define XFREE(p) free (p) #endif /* !XALLOC_H_ */ diff -Nur coreutils-5.0.orig/lib/xmalloc.c coreutils-5.0/lib/xmalloc.c --- coreutils-5.0.orig/lib/xmalloc.c Thu Nov 21 21:39:59 2002 +++ coreutils-5.0/lib/xmalloc.c Mon Dec 1 16:46:22 2003 @@ -22,7 +22,9 @@ #include #if STDC_HEADERS +# include # include +# include #else void *calloc (); void *malloc (); @@ -43,6 +45,10 @@ /* The following tests require AC_PREREQ(2.54). */ +#ifndef SIZE_MAX +# define SIZE_MAX ((size_t) -1) +#endif + #ifndef HAVE_MALLOC "you must run the autoconf test for a GNU libc compatible malloc" #endif @@ -58,6 +64,15 @@ /* If non NULL, call this function when memory is exhausted. */ void (*xalloc_fail_func) PARAMS ((void)) = 0; +/* Return true if array of N objects, each of size S, cannot exist due + to arithmetic overflow. S must be nonzero. */ + +static inline bool +array_size_overflow (size_t n, size_t s) +{ + return SIZE_MAX / s < n; +} + /* If XALLOC_FAIL_FUNC is NULL, or does return, display this message before exiting when memory is exhausted. Goes through gettext. */ char const xalloc_msg_memory_exhausted[] = N_("memory exhausted"); @@ -70,8 +85,20 @@ error (xalloc_exit_failure, 0, "%s", _(xalloc_msg_memory_exhausted)); /* The `noreturn' cannot be given to error, since it may return if its first argument is 0. To help compilers understand the - xalloc_die does terminate, call exit. */ - exit (EXIT_FAILURE); + xalloc_die does terminate, call abort. */ + abort (); +} + +/* Allocate an array of N objects, each with S bytes of memory, + dynamically, with error checking. S must be nonzero. */ + +void * +xnmalloc (size_t n, size_t s) +{ + void *p; + if (array_size_overflow (n, s) || ! (p = malloc (n * s))) + xalloc_die (); + return p; } /* Allocate N bytes of memory dynamically, with error checking. */ @@ -79,10 +106,16 @@ void * xmalloc (size_t n) { - void *p; + return xnmalloc (n, 1); +} - p = malloc (n); - if (p == 0) +/* Change the size of an allocated block of memory P to an array of N + objects each of S bytes, with error checking. S must be nonzero. */ + +void * +xnrealloc (void *p, size_t n, size_t s) +{ + if (array_size_overflow (n, s) || ! (p = realloc (p, n * s))) xalloc_die (); return p; } @@ -93,21 +126,39 @@ void * xrealloc (void *p, size_t n) { - p = realloc (p, n); - if (p == 0) - xalloc_die (); - return p; + return xnrealloc (p, n, 1); } -/* Allocate memory for N elements of S bytes, with error checking. */ +/* Allocate S bytes of zeroed memory dynamically, with error checking. + There's no need for xnzalloc (N, S), since it would be equivalent + to xcalloc (N, S). */ + +void * +xzalloc (size_t s) +{ + return memset (xmalloc (s), 0, s); +} + +/* Allocate zeroed memory for N elements of S bytes, with error + checking. S must be nonzero. */ void * xcalloc (size_t n, size_t s) { void *p; - - p = calloc (n, s); - if (p == 0) + /* Test for overflow, since some calloc implementations don't have + proper overflow checks. */ + if (array_size_overflow (n, s) || ! (p = calloc (n, s))) xalloc_die (); return p; } + +/* Clone an object P of size S, with error checking. There's no need + for xnclone (P, N, S), since xclone (P, N * S) works without any + need for an arithmetic overflow check. */ + +void * +xclone (void const *p, size_t s) +{ + return memcpy (xmalloc (s), p, s); +} diff -Nur coreutils-5.0.orig/lib/xstrdup.c coreutils-5.0/lib/xstrdup.c --- coreutils-5.0.orig/lib/xstrdup.c Fri Nov 30 15:32:22 2001 +++ coreutils-5.0/lib/xstrdup.c Mon Dec 1 16:46:22 2003 @@ -34,5 +34,5 @@ char * xstrdup (const char *string) { - return strcpy (xmalloc (strlen (string) + 1), string); + return xclone (string, strlen (string) + 1); } diff -Nur coreutils-5.0.orig/src/ls.c coreutils-5.0/src/ls.c --- coreutils-5.0.orig/src/ls.c Mon Dec 1 16:45:36 2003 +++ coreutils-5.0/src/ls.c Mon Dec 1 16:55:07 2003 @@ -243,7 +243,7 @@ struct bin_str { - int len; /* Number of bytes */ + size_t len; /* Number of bytes */ const char *string; /* Pointer to the same */ }; @@ -265,15 +265,15 @@ static void print_color_indicator (const char *name, mode_t mode, int linkok); static void put_indicator (const struct bin_str *ind); static int put_indicator_direct (const struct bin_str *ind); -static int length_of_file_name_and_frills (const struct fileinfo *f); +static size_t length_of_file_name_and_frills (const struct fileinfo *f); static void add_ignore_pattern (const char *pattern); static void attach (char *dest, const char *dirname, const char *name); static void clear_files (void); static void extract_dirs_from_files (const char *dirname, int ignore_dot_and_dot_dot); static void get_link_name (const char *filename, struct fileinfo *f); -static void indent (int from, int to); -static void init_column_info (void); +static void indent (size_t from, size_t to); +static size_t calculate_columns (bool by_columns); static void print_current_files (void); static void print_dir (const char *name, const char *realname); static void print_file_name_and_frills (const struct fileinfo *f); @@ -319,10 +319,10 @@ static struct fileinfo *files; /* FIXME: rename this to e.g. cwd_file */ /* Length of block that `files' points to, measured in files. */ -static int nfiles; /* FIXME: rename this to e.g. cwd_n_alloc */ +static size_t nfiles; /* FIXME: rename this to e.g. cwd_n_alloc */ /* Index of first unused in `files'. */ -static int files_index; /* FIXME: rename this to e.g. cwd_n_used */ +static size_t files_index; /* FIXME: rename this to e.g. cwd_n_used */ /* When nonzero, in a color listing, color each symlink name according to the type of file it points to. Otherwise, color them according to the `ln' @@ -632,7 +632,7 @@ /* The number of chars per hardware tab stop. Setting this to zero inhibits the use of TAB characters for separating columns. -T */ -static int tabsize; +static size_t tabsize; /* Nonzero means we are listing the working directory because no non-option arguments were given. */ @@ -646,7 +646,7 @@ /* The line length to use for breaking lines in many-per-line format. Can be set with -w. */ -static int line_length; +static size_t line_length; /* If nonzero, the file listing format requires that stat be called on each file. */ @@ -799,16 +799,16 @@ /* Information about filling a column. */ struct column_info { - int valid_len; - int line_len; - int *col_arr; + bool valid_len; + size_t line_len; + size_t *col_arr; }; /* Array with information about column filledness. */ static struct column_info *column_info; /* Maximum number of columns ever possible for this display. */ -static int max_idx; +static size_t max_idx; /* The minimum width of a colum is 3: 1 character for the name and 2 for the separating white space. */ @@ -904,18 +904,18 @@ static void dired_dump_obstack (const char *prefix, struct obstack *os) { - int n_pos; + size_t n_pos; n_pos = obstack_object_size (os) / sizeof (dired_pos); if (n_pos > 0) { - int i; + size_t i; size_t *pos; pos = (size_t *) obstack_finish (os); fputs (prefix, stdout); for (i = 0; i < n_pos; i++) - printf (" %lu", (unsigned long) pos[i]); + printf (" %lu", (unsigned long int) pos[i]); putchar ('\n'); } } @@ -952,7 +952,7 @@ struct dev_ino *ent_from_table; int found_match; - ent = XMALLOC (struct dev_ino, 1); + ent = xmalloc (sizeof *ent); ent->st_ino = ino; ent->st_dev = dev; @@ -1134,7 +1134,7 @@ } nfiles = 100; - files = XMALLOC (struct fileinfo, nfiles); + files = xnmalloc (nfiles, sizeof *files); files_index = 0; clear_files (); @@ -1322,11 +1322,11 @@ char const *p = getenv ("COLUMNS"); if (p && *p) { - long int tmp_long; - if (xstrtol (p, NULL, 0, &tmp_long, NULL) == LONGINT_OK - && 0 < tmp_long && tmp_long <= INT_MAX) + unsigned long int tmp_ulong; + if (xstrtoul (p, NULL, 0, &tmp_ulong, NULL) == LONGINT_OK + && 0 < tmp_ulong && tmp_ulong <= SIZE_MAX) { - line_length = (int) tmp_long; + line_length = tmp_ulong; } else { @@ -1341,7 +1341,8 @@ { struct winsize ws; - if (ioctl (STDOUT_FILENO, TIOCGWINSZ, &ws) != -1 && ws.ws_col != 0) + if (ioctl (STDOUT_FILENO, TIOCGWINSZ, &ws) != -1 + && 0 < ws.ws_col && ws.ws_col <= SIZE_MAX) line_length = ws.ws_col; } #endif @@ -1353,11 +1354,11 @@ tabsize = 8; if (!getenv ("POSIXLY_CORRECT") && (p = getenv ("TABSIZE"))) { - long int tmp_long; - if (xstrtol (p, NULL, 0, &tmp_long, NULL) == LONGINT_OK - && 0 <= tmp_long && tmp_long <= INT_MAX) + unsigned long int tmp_ulong; + if (xstrtoul (p, NULL, 0, &tmp_ulong, NULL) == LONGINT_OK + && tmp_ulong <= SIZE_MAX) { - tabsize = (int) tmp_long; + tabsize = tmp_ulong; } else { @@ -1476,12 +1477,12 @@ case 'w': { - long int tmp_long; - if (xstrtol (optarg, NULL, 0, &tmp_long, NULL) != LONGINT_OK - || tmp_long <= 0 || tmp_long > INT_MAX) + unsigned long int tmp_ulong; + if (xstrtoul (optarg, NULL, 0, &tmp_ulong, NULL) != LONGINT_OK + || ! (0 < tmp_ulong && tmp_ulong <= SIZE_MAX)) error (EXIT_FAILURE, 0, _("invalid line width: %s"), quotearg (optarg)); - line_length = (int) tmp_long; + line_length = tmp_ulong; break; } @@ -1550,12 +1551,12 @@ case 'T': { - long int tmp_long; - if (xstrtol (optarg, NULL, 0, &tmp_long, NULL) != LONGINT_OK - || tmp_long < 0 || tmp_long > INT_MAX) + unsigned long int tmp_ulong; + if (xstrtoul (optarg, NULL, 0, &tmp_ulong, NULL) != LONGINT_OK + || SIZE_MAX < tmp_ulong) error (EXIT_FAILURE, 0, _("invalid tab size: %s"), quotearg (optarg)); - tabsize = (int) tmp_long; + tabsize = tmp_ulong; break; } @@ -1661,6 +1662,8 @@ } } + max_idx = MAX (1, line_length / MIN_COLUMN_WIDTH); + filename_quoting_options = clone_quoting_options (NULL); if (get_quoting_style (filename_quoting_options) == escape_quoting_style) set_char_quoting (filename_quoting_options, ' ', 1); @@ -1762,7 +1765,8 @@ /* Parse a string as part of the LS_COLORS variable; this may involve decoding all kinds of escape characters. If equals_end is set an unescaped equal sign ends the string, otherwise only a : or \0 - does. Returns the number of characters output, or -1 on failure. + does. Set *OUTPUT_COUNT to the number of bytes output. Return + true if successful. The resulting string is *not* null-terminated, but may contain embedded nulls. @@ -1771,11 +1775,12 @@ the first free byte after the array and the character that ended the input string, respectively. */ -static int -get_funky_string (char **dest, const char **src, int equals_end) +static bool +get_funky_string (char **dest, const char **src, bool equals_end, + size_t *output_count) { int num; /* For numerical codes */ - int count; /* Something to count with */ + size_t count; /* Something to count with */ enum { ST_GND, ST_BACKSLASH, ST_OCTAL, ST_HEX, ST_CARET, ST_END, ST_ERROR } state; @@ -1960,8 +1965,9 @@ *dest = q; *src = p; + *output_count = count; - return state == ST_ERROR ? -1 : count; + return state != ST_ERROR; } static void @@ -2004,15 +2010,15 @@ override an earlier one, which can be useful for having terminal-specific defs override global). */ - ext = XMALLOC (struct color_ext_type, 1); + ext = xmalloc (sizeof *ext); ext->next = color_ext_list; color_ext_list = ext; ++p; ext->ext.string = buf; - state = (ext->ext.len = - get_funky_string (&buf, &p, 1)) < 0 ? -1 : 4; + state = (get_funky_string (&buf, &p, true, &ext->ext.len) + ? 4 : -1); break; case '\0': @@ -2045,8 +2051,9 @@ if (STREQ (label, indicator_name[ind_no])) { color_indicator[ind_no].string = buf; - state = ((color_indicator[ind_no].len = - get_funky_string (&buf, &p, 0)) < 0 ? -1 : 1); + state = (get_funky_string (&buf, &p, false, + &color_indicator[ind_no].len) + ? 1 : -1); break; } } @@ -2059,8 +2066,8 @@ if (*(p++) == '=') { ext->seq.string = buf; - state = (ext->seq.len = - get_funky_string (&buf, &p, 0)) < 0 ? -1 : 1; + state = (get_funky_string (&buf, &p, false, &ext->seq.len) + ? 1 : -1); } else state = -1; @@ -2104,7 +2111,7 @@ { struct pending *new; - new = XMALLOC (struct pending, 1); + new = xmalloc (sizeof *new); new->realname = realname ? xstrdup (realname) : NULL; new->name = name ? xstrdup (name) : NULL; new->next = pending_dirs; @@ -2259,7 +2266,7 @@ { register struct ignore_pattern *ignore; - ignore = XMALLOC (struct ignore_pattern, 1); + ignore = xmalloc (sizeof *ignore); ignore->pattern = pattern; /* Add it to the head of the linked list. */ ignore->next = ignore_patterns; @@ -2294,7 +2301,7 @@ static void clear_files (void) { - register int i; + register size_t i; for (i = 0; i < files_index; i++) { @@ -2320,8 +2327,8 @@ if (files_index == nfiles) { + files = xnrealloc (files, nfiles, 2 * sizeof *files); nfiles *= 2; - files = XREALLOC (files, struct fileinfo, nfiles); } files[files_index].linkname = 0; @@ -2547,7 +2554,8 @@ static void extract_dirs_from_files (const char *dirname, int ignore_dot_and_dot_dot) { - register int i, j; + register size_t i; + register size_t j; if (*dirname && LOOP_DETECT) { @@ -2559,7 +2567,7 @@ /* Queue the directories last one first, because queueing reverses the order. */ - for (i = files_index - 1; i >= 0; i--) + 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))) @@ -2786,7 +2794,7 @@ static void print_current_files (void) { - register int i; + register size_t i; switch (format) { @@ -2799,12 +2807,10 @@ break; case many_per_line: - init_column_info (); print_many_per_line (); break; case horizontal: - init_column_info (); print_horizontal (); break; @@ -2907,7 +2913,7 @@ if (name) sprintf (buffer, "%-8s ", name); else - sprintf (buffer, "%-8lu ", (unsigned long) u); + sprintf (buffer, "%-8lu ", (unsigned long int) u); return strlen (buffer); } @@ -2981,7 +2987,7 @@ /* The last byte of the mode string is the POSIX "optional alternate access method flag". */ - sprintf (p, "%s %3lu ", modebuf, (unsigned long) f->stat.st_nlink); + sprintf (p, "%s %3lu ", modebuf, (unsigned long int) f->stat.st_nlink); p += strlen (p); if (print_owner) @@ -2993,7 +2999,7 @@ if (group_name) sprintf (p, "%-8s ", group_name); else - sprintf (p, "%-8lu ", (unsigned long) f->stat.st_gid); + sprintf (p, "%-8lu ", (unsigned long int) f->stat.st_gid); p += strlen (p); } @@ -3002,8 +3008,8 @@ if (S_ISCHR (f->stat.st_mode) || S_ISBLK (f->stat.st_mode)) sprintf (p, "%3lu, %3lu ", - (unsigned long) major (f->stat.st_rdev), - (unsigned long) minor (f->stat.st_rdev)); + (unsigned long int) major (f->stat.st_rdev), + (unsigned long int) minor (f->stat.st_rdev)); else { char hbuf[LONGEST_HUMAN_READABLE + 1]; @@ -3405,7 +3411,7 @@ name += len; /* Pointer to final \0. */ for (ext = color_ext_list; ext != NULL; ext = ext->next) { - if ((size_t) ext->ext.len <= len + if (ext->ext.len <= len && strncmp (name - ext->ext.len, ext->ext.string, ext->ext.len) == 0) break; @@ -3422,12 +3428,12 @@ static void put_indicator (const struct bin_str *ind) { - register int i; + register size_t i; register const char *p; p = ind->string; - for (i = ind->len; i > 0; --i) + for (i = ind->len; i != 0; --i) putchar (*(p++)); } @@ -3445,10 +3451,10 @@ return (full_write (STDOUT_FILENO, ind->string, len) != len); } -static int +static size_t length_of_file_name_and_frills (const struct fileinfo *f) { - register int len = 0; + register size_t len = 0; size_t name_width; if (print_inode) @@ -3485,70 +3491,25 @@ static void print_many_per_line (void) { - struct column_info *line_fmt; - int filesno; /* Index into files. */ - int row; /* Current row. */ - int max_name_length; /* Length of longest file name + frills. */ - int name_length; /* Length of each file name + frills. */ - int pos; /* Current character column. */ - int cols; /* Number of files across. */ - int rows; /* Maximum number of files down. */ - int max_cols; - - /* Normally the maximum number of columns is determined by the - screen width. But if few files are available this might limit it - as well. */ - max_cols = max_idx > files_index ? files_index : max_idx; - - /* Compute the maximum number of possible columns. */ - for (filesno = 0; filesno < files_index; ++filesno) - { - int i; - - name_length = length_of_file_name_and_frills (files + filesno); - - for (i = 0; i < max_cols; ++i) - { - if (column_info[i].valid_len) - { - int idx = filesno / ((files_index + i) / (i + 1)); - int real_length = name_length + (idx == i ? 0 : 2); - - if (real_length > column_info[i].col_arr[idx]) - { - column_info[i].line_len += (real_length - - column_info[i].col_arr[idx]); - column_info[i].col_arr[idx] = real_length; - column_info[i].valid_len = column_info[i].line_len < line_length; - } - } - } - } - - /* Find maximum allowed columns. */ - for (cols = max_cols; cols > 1; --cols) - { - if (column_info[cols - 1].valid_len) - break; - } - - line_fmt = &column_info[cols - 1]; + size_t row; /* Current row. */ + size_t cols = calculate_columns (true); + struct column_info const *line_fmt = &column_info[cols - 1]; /* Calculate the number of rows that will be in each column except possibly for a short column on the right. */ - rows = files_index / cols + (files_index % cols != 0); + size_t rows = files_index / cols + (files_index % cols != 0); for (row = 0; row < rows; row++) { - int col = 0; - filesno = row; - pos = 0; + size_t col = 0; + size_t filesno = row; + size_t pos = 0; /* Print the next row. */ while (1) { + size_t name_length = length_of_file_name_and_frills (files + filesno); + size_t max_name_length = line_fmt->col_arr[col++]; print_file_name_and_frills (files + filesno); - name_length = length_of_file_name_and_frills (files + filesno); - max_name_length = line_fmt->col_arr[col++]; filesno += rows; if (filesno >= files_index) @@ -3564,65 +3525,20 @@ static void print_horizontal (void) { - struct column_info *line_fmt; - int filesno; - int max_name_length; - int name_length; - int cols; - int pos; - int max_cols; - - /* Normally the maximum number of columns is determined by the - screen width. But if few files are available this might limit it - as well. */ - max_cols = max_idx > files_index ? files_index : max_idx; - - /* Compute the maximum file name length. */ - max_name_length = 0; - for (filesno = 0; filesno < files_index; ++filesno) - { - int i; - - name_length = length_of_file_name_and_frills (files + filesno); - - for (i = 0; i < max_cols; ++i) - { - if (column_info[i].valid_len) - { - int idx = filesno % (i + 1); - int real_length = name_length + (idx == i ? 0 : 2); - - if (real_length > column_info[i].col_arr[idx]) - { - column_info[i].line_len += (real_length - - column_info[i].col_arr[idx]); - column_info[i].col_arr[idx] = real_length; - column_info[i].valid_len = column_info[i].line_len < line_length; - } - } - } - } - - /* Find maximum allowed columns. */ - for (cols = max_cols; cols > 1; --cols) - { - if (column_info[cols - 1].valid_len) - break; - } - - line_fmt = &column_info[cols - 1]; - - pos = 0; + size_t filesno; + size_t pos = 0; + size_t cols = calculate_columns (false); + struct column_info const *line_fmt = &column_info[cols - 1]; + size_t name_length = length_of_file_name_and_frills (files); + size_t max_name_length = line_fmt->col_arr[0]; /* Print first entry. */ print_file_name_and_frills (files); - name_length = length_of_file_name_and_frills (files); - max_name_length = line_fmt->col_arr[0]; /* Now the rest. */ for (filesno = 1; filesno < files_index; ++filesno) { - int col = filesno % cols; + size_t col = filesno % cols; if (col == 0) { @@ -3646,8 +3562,9 @@ static void print_with_commas (void) { - int filesno; - int pos, old_pos; + size_t filesno; + size_t pos; + size_t old_pos; pos = 0; @@ -3679,11 +3596,11 @@ Use a TAB character instead of two or more spaces whenever possible. */ static void -indent (int from, int to) +indent (size_t from, size_t to) { while (from < to) { - if (tabsize > 0 && to / tabsize > (from + 1) / tabsize) + if (tabsize != 0 && to / tabsize > (from + 1) / tabsize) { putchar ('\t'); from += tabsize - from % tabsize; @@ -3719,37 +3636,129 @@ *dest = 0; } +/* Allocate enough column info suitable for the current number of + files and display columns, and initialize the info to represent the + narrowest possible columns. */ + static void init_column_info (void) { - int i; - int allocate = 0; + size_t i; - max_idx = line_length / MIN_COLUMN_WIDTH; - if (max_idx == 0) - max_idx = 1; + size_t max_cols = MIN (max_idx, files_index); - if (column_info == NULL) + /* Currently allocated columns in column_info. */ + static size_t column_info_alloc; + + if (column_info_alloc < max_cols) { - column_info = XMALLOC (struct column_info, max_idx); - allocate = 1; + size_t new_column_info_alloc; + size_t *p; + + if (max_cols < max_idx / 2) + { + /* The number of columns is far less than the display width + allows. Grow the allocation, but only so that it's + double the current requirements. If the display is + extremely wide, this avoids allocating a lot of memory + that is never needed. */ + column_info = xnrealloc (column_info, max_cols, + 2 * sizeof *column_info); + new_column_info_alloc = 2 * max_cols; + } + else + { + column_info = xnrealloc (column_info, max_idx, sizeof *column_info); + new_column_info_alloc = max_idx; + } + + /* Allocate the new size_t objects by computing the triangle + formula n * (n + 1) / 2, except that we don't need to + allocate the part of the triangle that we've already + allocated. Check for address arithmetic overflow. */ + { + size_t column_info_growth = new_column_info_alloc - column_info_alloc; + size_t s = column_info_alloc + 1 + new_column_info_alloc; + size_t t = s * column_info_growth; + if (s < new_column_info_alloc || t / column_info_growth != s) + xalloc_die (); + p = xnmalloc (t / 2, sizeof *p); + } + + /* Grow the triangle by parceling out the cells just allocated. */ + for (i = column_info_alloc; i < new_column_info_alloc; i++) + { + column_info[i].col_arr = p; + p += i + 1; + } + + column_info_alloc = new_column_info_alloc; } - for (i = 0; i < max_idx; ++i) + for (i = 0; i < max_cols; ++i) { - int j; + size_t j; - column_info[i].valid_len = 1; + column_info[i].valid_len = true; column_info[i].line_len = (i + 1) * MIN_COLUMN_WIDTH; - - if (allocate) - column_info[i].col_arr = XMALLOC (int, i + 1); - for (j = 0; j <= i; ++j) column_info[i].col_arr[j] = MIN_COLUMN_WIDTH; } } +/* Calculate the number of columns needed to represent the current set + of files in the current display width. */ + +static size_t +calculate_columns (bool by_columns) +{ + size_t filesno; /* Index into files. */ + size_t cols; /* Number of files across. */ + + /* Normally the maximum number of columns is determined by the + screen width. But if few files are available this might limit it + as well. */ + size_t max_cols = MIN (max_idx, files_index); + + init_column_info (); + + /* Compute the maximum number of possible columns. */ + for (filesno = 0; filesno < files_index; ++filesno) + { + size_t name_length = length_of_file_name_and_frills (files + filesno); + size_t i; + + for (i = 0; i < max_cols; ++i) + { + if (column_info[i].valid_len) + { + size_t idx = (by_columns + ? filesno / ((files_index + i) / (i + 1)) + : filesno % (i + 1)); + size_t real_length = name_length + (idx == i ? 0 : 2); + + if (column_info[i].col_arr[idx] < real_length) + { + column_info[i].line_len += (real_length + - column_info[i].col_arr[idx]); + column_info[i].col_arr[idx] = real_length; + column_info[i].valid_len = (column_info[i].line_len + < line_length); + } + } + } + } + + /* Find maximum allowed columns. */ + for (cols = max_cols; 1 < cols; --cols) + { + if (column_info[cols - 1].valid_len) + break; + } + + return cols; +} + void usage (int status) {