1 /* cut - remove parts of lines of files
2 Copyright (C) 1984, 1997-2003 by David M. Ihnat
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2, or (at your option)
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software Foundation,
16 Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
18 /* Written by David Ihnat. */
20 /* POSIX changes, bug fixes, long-named options, and cleanup
21 by David MacKenzie <djm@gnu.ai.mit.edu>.
23 Rewrite cut_fields and cut_bytes -- Jim Meyering. */
30 #include <sys/types.h>
34 #include "getndelim2.h"
39 /* The official name of this program (e.g., no `g' prefix). */
40 #define PROGRAM_NAME "cut"
42 #define WRITTEN_BY _("Written by David Ihnat, David MacKenzie, and Jim Meyering.")
44 #define FATAL_ERROR(Message) \
47 error (0, 0, (Message)); \
52 /* Append LOW, HIGH to the list RP of range pairs, allocating additional
53 space if necessary. Update local variable N_RP. When allocating,
54 update global variable N_RP_ALLOCATED. */
56 #define ADD_RANGE_PAIR(rp, low, high) \
59 if (n_rp >= n_rp_allocated) \
61 n_rp_allocated *= 2; \
62 (rp) = xrealloc (rp, n_rp_allocated * sizeof (*(rp))); \
64 rp[n_rp].lo = (low); \
65 rp[n_rp].hi = (high); \
76 /* This buffer is used to support the semantics of the -s option
77 (or lack of same) when the specified field list includes (does
78 not include) the first field. In both of those cases, the entire
79 first field must be read into this buffer to determine whether it
80 is followed by a delimiter or a newline before any of it may be
81 output. Otherwise, cut_fields can do the job without using this
83 static char *field_1_buffer;
85 /* The number of bytes allocated for FIELD_1_BUFFER. */
86 static size_t field_1_bufsize;
88 /* The largest field or byte index used as an endpoint of a closed
89 or degenerate range specification; this doesn't include the starting
90 index of right-open-ended ranges. For example, with either range spec
91 `2-5,9-', `2-3,5,9-' this variable would be set to 5. */
92 static unsigned int max_range_endpoint;
94 /* If nonzero, this is the index of the first field in a range that goes
96 static unsigned int eol_range_start;
98 /* This is a bit vector.
99 In byte mode, which bytes to output.
100 In field mode, which DELIM-separated fields to output.
101 Both bytes and fields are numbered starting with 1,
102 so the zeroth bit of this array is unused.
103 A field or byte K has been selected if
104 (K <= MAX_RANGE_ENDPOINT and is_printable_field(K))
105 || (EOL_RANGE_START > 0 && K >= EOL_RANGE_START). */
106 static unsigned char *printable_field;
112 /* Output characters that are in the given bytes. */
115 /* Output the given delimeter-separated fields. */
119 /* The name this program was run with. */
122 static enum operating_mode operating_mode;
124 /* If nonzero do not output lines containing no delimeter characters.
125 Otherwise, all such lines are printed. This option is valid only
127 static int suppress_non_delimited;
129 /* The delimeter character for field mode. */
132 /* Nonzero if the --output-delimiter=STRING option was specified. */
133 static int output_delimiter_specified;
135 /* The length of output_delimiter_string. */
136 static size_t output_delimiter_length;
138 /* The output field separator string. Defaults to the 1-character
139 string consisting of the input delimiter. */
140 static char *output_delimiter_string;
142 /* Nonzero if we have ever read standard input. */
143 static int have_read_stdin;
145 #define HT_RANGE_START_INDEX_INITIAL_CAPACITY 31
147 /* The set of range-start indices. For example, given a range-spec list like
148 `-b1,3-5,4-9,15-', the following indices will be recorded here: 1, 3, 15.
149 Note that although `4' looks like a range-start index, it is in the middle
150 of the `3-5' range, so it doesn't count.
151 This table is created/used IFF output_delimiter_specified is set. */
152 static Hash_table *range_start_ht;
154 /* For long options that have no equivalent short option, use a
155 non-character as a pseudo short option, starting with CHAR_MAX + 1. */
158 OUTPUT_DELIMITER_OPTION = CHAR_MAX + 1
161 static struct option const longopts[] =
163 {"bytes", required_argument, 0, 'b'},
164 {"characters", required_argument, 0, 'c'},
165 {"fields", required_argument, 0, 'f'},
166 {"delimiter", required_argument, 0, 'd'},
167 {"only-delimited", no_argument, 0, 's'},
168 {"output-delimiter", required_argument, 0, OUTPUT_DELIMITER_OPTION},
169 {GETOPT_HELP_OPTION_DECL},
170 {GETOPT_VERSION_OPTION_DECL},
178 fprintf (stderr, _("Try `%s --help' for more information.\n"),
183 Usage: %s [OPTION]... [FILE]...\n\
187 Print selected parts of lines from each FILE to standard output.\n\
191 Mandatory arguments to long options are mandatory for short options too.\n\
194 -b, --bytes=LIST output only these bytes\n\
195 -c, --characters=LIST output only these characters\n\
196 -d, --delimiter=DELIM use DELIM instead of TAB for field delimiter\n\
199 -f, --fields=LIST output only these fields; also print any line\n\
200 that contains no delimiter character, unless\n\
201 the -s option is specified\n\
205 -s, --only-delimited do not print lines not containing delimiters\n\
206 --output-delimiter=STRING use STRING as the output delimiter\n\
207 the default is to use the input delimiter\n\
209 fputs (HELP_OPTION_DESCRIPTION, stdout);
210 fputs (VERSION_OPTION_DESCRIPTION, stdout);
213 Use one, and only one of -b, -c or -f. Each LIST is made up of one\n\
214 range, or many ranges separated by commas. Each range is one of:\n\
216 N N'th byte, character or field, counted from 1\n\
217 N- from N'th byte, character or field, to end of line\n\
218 N-M from N'th to M'th (included) byte, character or field\n\
219 -M from first to M'th (included) byte, character or field\n\
221 With no FILE, or when FILE is -, read standard input.\n\
223 printf (_("\nReport bugs to <%s>.\n"), PACKAGE_BUGREPORT);
225 exit (status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
229 mark_printable_field (unsigned int i)
231 size_t n = i / CHAR_BIT;
232 printable_field[n] |= (1 << (i % CHAR_BIT));
236 is_printable_field (unsigned int i)
238 size_t n = i / CHAR_BIT;
239 return (printable_field[n] >> (i % CHAR_BIT)) & 1;
243 hash_int (const void *x, unsigned int tablesize)
245 unsigned int y = (unsigned int) x;
246 return (y % tablesize);
250 hash_compare_ints (void const *x, void const *y)
252 return (x == y) ? true : false;
256 is_range_start_index (int i)
258 return hash_lookup (range_start_ht, (void *) i) ? true : false;
261 /* Return nonzero if the K'th field or byte is printable.
262 When returning nonzero, if RANGE_START is non-NULL,
263 set *RANGE_START to nonzero if K is the beginning of a range, and
264 set *RANGE_START to zero if K is not the beginning of a range. */
267 print_kth (unsigned int k, int *range_start)
269 if (0 < eol_range_start && eol_range_start <= k)
272 *range_start = (k == eol_range_start);
276 if (k <= max_range_endpoint && is_printable_field (k))
279 *range_start = is_range_start_index (k);
286 /* Given the list of field or byte range specifications FIELDSTR, set
287 MAX_RANGE_ENDPOINT and allocate and initialize the PRINTABLE_FIELD
288 array. If there is a right-open-ended range, set EOL_RANGE_START
289 to its starting index. FIELDSTR should be composed of one or more
290 numbers or ranges of numbers, separated by blanks or commas.
291 Incomplete ranges may be given: `-m' means `1-m'; `n-' means `n'
292 through end of line. Return nonzero if FIELDSTR contains at least
293 one field specification, zero otherwise. */
295 /* FIXME-someday: What if the user wants to cut out the 1,000,000-th
296 field of some huge input file? This function shouldn't have to
297 allocate a table of a million bits just so we can test every
298 field < 10^6 with an array dereference. Instead, consider using
299 an adaptive approach: if the range of selected fields is too large,
300 but only a few fields/byte-offsets are actually selected, use a
301 hash table. If the range of selected fields is too large, and
302 too many are selected, then resort to using the range-pairs (the
303 `rp' array) directly. */
306 set_fields (const char *fieldstr)
308 unsigned int initial = 1; /* Value of first number in a range. */
309 unsigned int value = 0; /* If nonzero, a number being accumulated. */
310 int dash_found = 0; /* Nonzero if a '-' is found in this field. */
311 int field_found = 0; /* Non-zero if at least one field spec
312 has been processed. */
314 struct range_pair *rp;
316 unsigned int n_rp_allocated;
318 bool in_digits = false;
322 rp = xmalloc (n_rp_allocated * sizeof (*rp));
324 /* Collect and store in RP the range end points.
325 It also sets EOL_RANGE_START if appropriate. */
329 if (*fieldstr == '-')
332 /* Starting a range. */
334 FATAL_ERROR (_("invalid byte or field list"));
346 else if (*fieldstr == ',' || ISBLANK (*fieldstr) || *fieldstr == '\0')
349 /* Ending the string, or this field/byte sublist. */
354 /* A range. Possibilites: -n, m-n, n-.
355 In any case, `initial' contains the start of the range. */
358 /* `n-'. From `initial' to end of line. */
359 eol_range_start = initial;
364 /* `m-n' or `-n' (1-n). */
366 FATAL_ERROR (_("invalid byte or field list"));
368 /* Is there already a range going to end of line? */
369 if (eol_range_start != 0)
371 /* Yes. Is the new sequence already contained
372 in the old one? If so, no processing is
374 if (initial < eol_range_start)
376 /* No, the new sequence starts before the
377 old. Does the old range going to end of line
378 extend into the new range? */
379 if (eol_range_start <= value)
381 /* Yes. Simply move the end of line marker. */
382 eol_range_start = initial;
386 /* No. A simple range, before and disjoint from
387 the range going to end of line. Fill it. */
388 ADD_RANGE_PAIR (rp, initial, value);
391 /* In any case, some fields were selected. */
397 /* There is no range going to end of line. */
398 ADD_RANGE_PAIR (rp, initial, value);
406 /* A simple field number, not a range. */
407 ADD_RANGE_PAIR (rp, value, value);
412 if (*fieldstr == '\0')
419 else if (ISDIGIT (*fieldstr))
422 /* Record beginning of digit string, in case we have to
423 complain about it. */
424 static char const *num_start;
425 if (!in_digits || !num_start)
426 num_start = fieldstr;
429 /* Detect overflow. */
430 new_v = 10 * value + *fieldstr - '0';
431 if (UINT_MAX / 10 < value || new_v < value * 10)
433 /* In case the user specified -c4294967296-22,
434 complain only about the first number. */
435 /* Determine the length of the offending number. */
436 size_t len = strspn (num_start, "0123456789");
437 char *bad_num = xstrndup (num_start, len);
438 if (operating_mode == byte_mode)
440 _("byte offset %s is too large"), quote (bad_num));
443 _("field number %s is too large"), quote (bad_num));
452 FATAL_ERROR (_("invalid byte or field list"));
455 max_range_endpoint = 0;
456 for (i = 0; i < n_rp; i++)
458 if (rp[i].hi > max_range_endpoint)
459 max_range_endpoint = rp[i].hi;
462 /* Allocate an array large enough so that it may be indexed by
463 the field numbers corresponding to all finite ranges
464 (i.e. `2-6' or `-4', but not `5-') in FIELDSTR. */
466 printable_field = xcalloc (((max_range_endpoint / CHAR_BIT + 1)
467 * sizeof (*printable_field)), 1);
469 /* Set the array entries corresponding to integers in the ranges of RP. */
470 for (i = 0; i < n_rp; i++)
473 for (j = rp[i].lo; j <= rp[i].hi; j++)
475 mark_printable_field (j);
479 if (output_delimiter_specified)
481 /* Record the range-start indices. */
482 for (i = 0; i < n_rp; i++)
484 unsigned int j = rp[i].lo;
485 for (j = rp[i].lo; j <= rp[i].hi; j++)
487 if (0 < j && is_printable_field (j)
488 && !is_printable_field (j - 1))
490 /* Record the fact that `j' is a range-start index. */
491 void *ent_from_table = hash_insert (range_start_ht,
493 if (ent_from_table == NULL)
495 /* Insertion failed due to lack of memory. */
498 assert ((unsigned int) ent_from_table == j);
509 /* Read from stream STREAM, printing to standard output any selected bytes. */
512 cut_bytes (FILE *stream)
514 unsigned int byte_idx; /* Number of bytes in the line so far. */
515 /* Whether to begin printing delimiters between ranges for the current line.
516 Set after we've begun printing data corresponding to the first range. */
523 register int c; /* Each character from the file. */
542 int *rs = output_delimiter_specified ? &range_start : NULL;
543 if (print_kth (++byte_idx, rs))
545 if (rs && *rs && print_delimiter)
547 fwrite (output_delimiter_string, sizeof (char),
548 output_delimiter_length, stdout);
557 /* Read from stream STREAM, printing to standard output any selected fields. */
560 cut_fields (FILE *stream)
563 unsigned int field_idx;
564 int found_any_selected_field;
565 int buffer_first_field;
567 found_any_selected_field = 0;
576 /* To support the semantics of the -s flag, we may have to buffer
577 all of the first field to determine whether it is `delimited.'
578 But that is unnecessary if all non-delimited lines must be printed
579 and the first field has been selected, or if non-delimited lines
580 must be suppressed and the first field has *not* been selected.
581 That is because a non-delimited line has exactly one field. */
582 buffer_first_field = (suppress_non_delimited ^ !print_kth (1, NULL));
586 if (field_idx == 1 && buffer_first_field)
591 len = getndelim2 (&field_1_buffer, &field_1_bufsize, SIZE_MAX,
592 stream, delim, '\n', 0);
595 if (ferror (stream) || feof (stream))
601 assert (n_bytes != 0);
603 /* If the first field extends to the end of line (it is not
604 delimited) and we are printing all non-delimited lines,
606 if ((unsigned char) field_1_buffer[n_bytes - 1] != delim)
608 if (suppress_non_delimited)
614 fwrite (field_1_buffer, sizeof (char), n_bytes, stdout);
615 /* Make sure the output line is newline terminated. */
616 if (field_1_buffer[n_bytes - 1] != '\n')
621 if (print_kth (1, NULL))
623 /* Print the field, but not the trailing delimiter. */
624 fwrite (field_1_buffer, sizeof (char), n_bytes - 1, stdout);
625 found_any_selected_field = 1;
632 if (print_kth (field_idx, NULL))
634 if (found_any_selected_field)
636 fwrite (output_delimiter_string, sizeof (char),
637 output_delimiter_length, stdout);
639 found_any_selected_field = 1;
641 while ((c = getc (stream)) != delim && c != '\n' && c != EOF)
648 while ((c = getc (stream)) != delim && c != '\n' && c != EOF)
667 else if (c == '\n' || c == EOF)
669 if (found_any_selected_field
670 || !(suppress_non_delimited && field_idx == 1))
675 found_any_selected_field = 0;
681 cut_stream (FILE *stream)
683 if (operating_mode == byte_mode)
689 /* Process file FILE to standard output.
690 Return 0 if successful, 1 if not. */
693 cut_file (char *file)
697 if (STREQ (file, "-"))
704 stream = fopen (file, "r");
707 error (0, errno, "%s", file);
716 error (0, errno, "%s", file);
719 if (STREQ (file, "-"))
720 clearerr (stream); /* Also clear EOF. */
721 else if (fclose (stream) == EOF)
723 error (0, errno, "%s", file);
730 main (int argc, char **argv)
732 int optc, exit_status = 0;
733 int delim_specified = 0;
734 char *spec_list_string IF_LINT(= NULL);
736 initialize_main (&argc, &argv);
737 program_name = argv[0];
738 setlocale (LC_ALL, "");
739 bindtextdomain (PACKAGE, LOCALEDIR);
740 textdomain (PACKAGE);
742 atexit (close_stdout);
744 operating_mode = undefined_mode;
746 /* By default, all non-delimited lines are printed. */
747 suppress_non_delimited = 0;
752 while ((optc = getopt_long (argc, argv, "b:c:d:f:ns", longopts, NULL)) != -1)
761 /* Build the byte list. */
762 if (operating_mode != undefined_mode)
763 FATAL_ERROR (_("only one type of list may be specified"));
764 operating_mode = byte_mode;
765 spec_list_string = optarg;
769 /* Build the field list. */
770 if (operating_mode != undefined_mode)
771 FATAL_ERROR (_("only one type of list may be specified"));
772 operating_mode = field_mode;
773 spec_list_string = optarg;
778 /* Interpret -d '' to mean `use the NUL byte as the delimiter.' */
779 if (optarg[0] != '\0' && optarg[1] != '\0')
780 FATAL_ERROR (_("the delimiter must be a single character"));
781 delim = (unsigned char) optarg[0];
785 case OUTPUT_DELIMITER_OPTION:
786 output_delimiter_specified = 1;
787 /* Interpret --output-delimiter='' to mean
788 `use the NUL byte as the delimiter.' */
789 output_delimiter_length = (optarg[0] == '\0'
790 ? 1 : strlen (optarg));
791 output_delimiter_string = xstrdup (optarg);
798 suppress_non_delimited = 1;
801 case_GETOPT_HELP_CHAR;
803 case_GETOPT_VERSION_CHAR (PROGRAM_NAME, WRITTEN_BY);
810 if (operating_mode == undefined_mode)
811 FATAL_ERROR (_("you must specify a list of bytes, characters, or fields"));
813 if (delim != '\0' && operating_mode != field_mode)
814 FATAL_ERROR (_("an input delimiter may be specified only\
815 when operating on fields"));
817 if (suppress_non_delimited && operating_mode != field_mode)
818 FATAL_ERROR (_("suppressing non-delimited lines makes sense\n\
819 \tonly when operating on fields"));
821 if (output_delimiter_specified)
823 range_start_ht = hash_initialize (HT_RANGE_START_INDEX_INITIAL_CAPACITY,
825 hash_compare_ints, NULL);
826 if (range_start_ht == NULL)
831 if (set_fields (spec_list_string) == 0)
833 if (operating_mode == field_mode)
834 FATAL_ERROR (_("missing list of fields"));
836 FATAL_ERROR (_("missing list of positions"));
839 if (!delim_specified)
842 if (output_delimiter_string == NULL)
844 static char dummy[2];
847 output_delimiter_string = dummy;
848 output_delimiter_length = 1;
852 exit_status |= cut_file ("-");
854 for (; optind < argc; optind++)
855 exit_status |= cut_file (argv[optind]);
858 hash_free (range_start_ht);
860 if (have_read_stdin && fclose (stdin) == EOF)
862 error (0, errno, "-");
866 exit (exit_status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);