Rewrote collating, search and tokens sections.
authorrms <rms>
Mon, 30 Dec 1991 08:07:38 +0000 (08:07 +0000)
committerrms <rms>
Mon, 30 Dec 1991 08:07:38 +0000 (08:07 +0000)
manual/string.texi

index 5217dbe..deda5a6 100644 (file)
@@ -8,15 +8,16 @@ comparing, and searching strings.  Many of these functions can also
 operate on arbitrary regions of storage; for example, the @code{memcpy}
 function can be used to copy the contents of any kind of array.  
 
-While it's fairly common for beginning C programmers to unwittingly
-``reinvent the wheel'' by duplicating this functionality in their own
-code, it pays to become familiar with the library functions and to make
-use of them, since this offers benefits in maintenance, efficiency, and
-portability.  For instance, you could easily compare one string to
-another in two lines of C code.  But if you use the built-in
-@code{strcmp} function, you're less likely to introduce bugs into your
-program.  And, since these library functions are typically highly
-optimized, your program may run faster too.
+It's fairly common for beginning C programmers to ``reinvent the wheel''
+by duplicating this functionality in their own code, but it pays to
+become familiar with the library functions and to make use of them,
+since this offers benefits in maintenance, efficiency, and portability.
+
+For instance, you could easily compare one string to another in two
+lines of C code, but if you use the built-in @code{strcmp} function,
+you're less likely to make a mistake.  And, since these library
+functions are typically highly optimized, your program may run faster
+too.
 
 @menu
 * Representation of Strings::  Introduction to basic concepts.
@@ -44,17 +45,18 @@ material, you can skip this section.
 
 @cindex string
 @cindex null character
-A @dfn{string} is an array of @code{char} objects.  Since arrays and
-pointers are equivalent in C, strings are usually declared to be of type
-@code{char *}.  By convention, a @dfn{null character}, @code{'\0'},
-marks the end of a string.  For example, in testing to see whether the
-@code{char *} @var{p} points to a null character marking the end of a
-string, you can write @code{!*@var{p}} or @code{*@var{p} == '\0'}.
+A @dfn{string} is an array of @code{char} objects.  Since array values
+in C are converted automatically to pointers, string-valued variables
+are usually declared to be of type @code{char *}.  By convention, a
+@dfn{null character}, @code{'\0'}, marks the end of a string.  For
+example, in testing to see whether the @code{char *} @var{p} points to a
+null character marking the end of a string, you can write
+@code{!*@var{p}} or @code{*@var{p} == '\0'}.
 
 A null character is quite different conceptually from a null pointer,
-although both are equivalent to an integer @code{0} in the appropriate
-context.
+although both are represented by the integer @code{0}.
 
+@c ??? rewrite
 Declaring a variable of type @code{char *} allocates storage only for a
 pointer to a string, not for the string itself.  If you declare a string
 as a @code{char *}, make sure that there is actually a character array
@@ -74,18 +76,19 @@ string literals can also be formed by @dfn{string concatenation}:
 literals is not allowed by the GNU C compiler, because literals
 are placed in read-only storage.
 
-String variables that are declared to be @code{const} cannot be modified
-either.  It's generally good style to declare non-modifiable strings to
-be of type @code{const char *}, since this allows the C compiler to
-detect accidental modifications as well as providing some amount of
-documentation about what your program intends to do with the string.
+Character arrays that are declared @code{const} cannot be modified
+either.  It's generally good style to declare non-modifiable string
+pointers to be of type @code{const char *}, since this often allows the
+C compiler to detect accidental modifications as well as providing some
+amount of documentation about what your program intends to do with the
+string.
 
 The amount of memory allocated for the character array may extend past
 the null character that normally marks the end of the string.  In this
-document, the term @dfn{allocation size} is carefully used to refer to
-the total amount of memory allocated for the string, while the term
-@dfn{length} refers to the number of characters up to (but not including)
-the terminating null character.
+document, the term @dfn{allocation size} is always used to refer to the
+total amount of memory allocated for the string, while the term
+@dfn{length} refers to the number of characters up to (but not
+including) the terminating null character.
 @cindex length of string
 @cindex allocation size of string
 @cindex size of string
@@ -93,12 +96,13 @@ the terminating null character.
 @cindex string allocation
 
 A notorious source of program bugs is trying to put more characters in a
-string than fit in its allocated size.  When writing code that
-extends strings or moves characters into a pre-allocated array, you
-should be very careful to keep track of the size of the array and make
-explicit checks for overflow.  Many of the library functions @emph{do
-not} do this for you!  Remember also that you need to allocate an extra
-byte to hold the null character that marks the end of the string.
+string than fit in its allocated size.  When writing code that extends
+strings or moves characters into a pre-allocated array, you should be
+very careful to keep track of the length of the text and make explicit
+checks for overflowing the array.  Many of the library functions
+@emph{do not} do this for you!  Remember also that you need to allocate
+an extra byte to hold the null character that marks the end of the
+string.
 
 @node String/Array Conventions
 @section String/Array Conventions
@@ -119,7 +123,9 @@ computing the value for the size argument.
 In contrast, functions that operate specifically on strings have names
 beginning with @samp{str} (such as @code{strcpy}) and look for a null
 character to terminate the string instead of requiring an explicit size
-argument to be passed.  The array arguments and return values for these
+argument to be passed.  (Some of these functions accept a specified
+maximum length, but they also check for premature termination with a
+null character.)  The array arguments and return values for these
 functions have type @code{char *}, and the array elements are referred
 to as ``characters''.
 
@@ -151,9 +157,10 @@ strlen ("hello, world")
     @result{} 12
 @end example
 
-The @code{strlen} function returns the length of a string, not its
-allocation size.  You can get the allocation size of the character array
-that holds a string using the @code{sizeof} operator:
+When applied to a character array, the @code{strlen} function returns
+the length of the string stored there, not its allocation size.  You can
+get the allocation size of the character array that holds a string using
+the @code{sizeof} operator:
 
 @example
 char string[32] = "hello, world"; 
@@ -183,7 +190,7 @@ in this section is that it corresponds to an assignment expression, with
 the destination array specified to the left of the source array.  All
 of these functions return the address of the destination array.
 
-Some of these functions might not work properly if the source and
+Most of these functions do not work properly if the source and
 destination arrays overlap.  For example, if the beginning of the
 destination array overlaps the end of the source array, the original
 contents of that part of the source array may get overwritten before it
@@ -192,7 +199,7 @@ character marking the end of the string may be lost, and the copy
 function might get stuck in a loop trashing all the memory allocated to
 your program.
 
-Any functions that have problems copying between overlapping arrays are
+All functions that have problems copying between overlapping arrays are
 explicitly identified in this manual.  In addition to functions in this
 section, there are a few others like @code{sprintf} and @code{scanf}.
 
@@ -223,64 +230,94 @@ The @code{memmove} function is just like @code{memcpy}, except that it works
 even if the objects @var{to} and @var{from} overlap.  However, since 
 @code{memmove} needs to make an intermediate copy into a temporary area,
 it can be less efficient than @code{memcpy}.
+@c ??? memmove should need just a few insns to detect the non-overlap case
+@c ??? and then act just like memcpy
 @end deftypefun
 
 @comment string.h
 @comment SVID
 @deftypefun {void *} memccpy (void *@var{to}, const void *@var{from}, int @var{c}, size_t @var{size})
-This function copies no more than @var{size} bytes from @var{from} to @var{to},
-stopping if a byte matching @var{c} is found.  The return value is a pointer
-into @var{to} one byte past where @var{c} was copied, or a null pointer if
-no byte matching @var{c} appeared in the first @var{size} bytes of @var{from}.
+This function copies no more than @var{size} bytes from @var{from} to
+@var{to}, stopping if a byte matching @var{c} is found.  The return
+value is a pointer into @var{to} one byte past where @var{c} was copied,
+or a null pointer if no byte matching @var{c} appeared in the first
+@var{size} bytes of @var{from}.
 @end deftypefun
 
 @comment string.h
 @comment ANSI
-@deftypefun {void *} memset (void *@var{a}, int @var{c}, size_t @var{size})
-This function copies the value of @var{c} (converted to an @code{unsigned
-char}) into each of the first @var{size} bytes of the object beginning at
-@var{a}.  It returns the value of @var{a}.
+@deftypefun {void *} memset (void *@var{block}, int @var{c}, size_t @var{size})
+This function copies the value of @var{c} (converted to an
+@code{unsigned char}) into each of the first @var{size} bytes of the
+object beginning at @var{block}.  It returns the value of @var{block}.
 @end deftypefun
 
 @comment string.h
 @comment ANSI
 @deftypefun {char *} strcpy (char *@var{to}, const char *@var{from})
-This copies characters from the string @var{from} (up to and including the
-terminating null character) into the string @var{to}.  Like
-@code{memcpy}, this function can fail if the strings overlap.  The
-return value is the value of @var{to}.
+This copies characters from the string @var{from} (up to and including
+the terminating null character) into the string @var{to}.  Like
+@code{memcpy}, this function has undefined results if the strings
+overlap.  The return value is the value of @var{to}.
 @end deftypefun
 
 @comment string.h
 @comment ANSI
 @deftypefun {char *} strncpy (char *@var{to}, const char *@var{from}, size_t @var{size})
-This function is similar to @code{strcpy} except that no more than @var{size}
-characters are copied.  If the length of @var{from} is less than @var{size} 
-characters, then the end of @var{to} is filled with null characters until
-@var{size} characters in all have been written.  
+This function is similar to @code{strcpy} but always copies exactly
+@var{size}.
 
-The behavior is undefined if the strings overlap.
+If the length of @var{from} is more than @var{size}, then @code{strncpy}
+copies just the first @var{size} characters.
 
-Unless you know in advance that the length of @var{from} is less than the
-allocation size of @var{from}, using @code{strncpy} as opposed to
-@code{strcpy} can avoid bugs relating to writing past the end of a
-string.
+If the length of @var{from} is less than @var{size}, then @code{strncpy}
+copies all of @var{from}, followed by enough null characters to add up
+to @var{size} characters in all.  This behavior is rarely useful, but it
+is specified by the ANSI C standard.
+
+The behavior of @code{strncpy} is undefined if the strings overlap.
+
+Using @code{strncpy} as opposed to @code{strcpy} is a way to avoid bugs
+relating to writing past the end of the allocated space for @var{to}.
+However, it can also make your program much slower in one common case:
+copying a string which is probably small into a potentially large buffer.
+In this case, @var{size} may be large, and when it is, @code{strncpy} will
+waste a considerable amount of time copying null characters.
 @end deftypefun
 
 @comment string.h
 @comment SVID
 @deftypefun {char *} strdup (const char *@var{s})
 This function copies the null-terminated string @var{s} into a newly
-allocated (as with @code{malloc}; @pxref{Unconstrained Allocation}
-string.
+allocated string.  The string is allocated using @code{malloc};
+see @ref{Unconstrained Allocation}.
 @end deftypefun
 
 @comment string.h
-@comment GNU
+@comment Unknown origin
 @deftypefun {char *} stpcpy (char *@var{to}, const char *@var{from})
 This function is like @code{strcpy}, except that it returns a pointer to
 the end of the string @var{to} (that is, the address of the terminating
 null pointer) rather than the beginning.
+
+For example, this program uses @code{stpcpy} to concatenate @samp{foo}
+and @samp{bar} to produce @samp{foobar}, which it then prints.
+
+@example
+main ()
+@{
+  char *to = buffer;
+  to = stpcpy (to, "foo");
+  to = stpcpy (to, "bar");
+  printf ("%s\n", buffer);
+@}
+@end example
+
+This function is not part of the ANSI or POSIX standards, and is not
+customary on Unix systems, but we did not invent it either.  Perhaps it
+comes from MS-DOG.
+
+Its behavior is undefined if the strings overlap.
 @end deftypefun
 
 @comment string.h
@@ -289,19 +326,41 @@ null pointer) rather than the beginning.
 The @code{strcat} function is similar to @code{strcpy}, except that the
 characters from @var{from} are concatenated or appended to the end of
 @var{to}, instead of overwriting it.  That is, the first character from
-@var{from} overwrites the null character marking the end of @var{to}.  
+@var{from} overwrites the null character marking the end of @var{to}.
+
+An equivalent definition for @code{strcat} would be:
 
-This function can fail if the strings overlap.
+@example
+char *
+strcat (char *to, const char *from)
+@{
+  strcpy (to + strlen (to), from);
+  return to;
+@}
+@end example
+
+This function has undefined results if the strings overlap.
 @end deftypefun
 
 @comment string.h
 @comment ANSI
 @deftypefun {char *} strncat (char *@var{to}, const char *@var{from}, size_t @var{size})
 This function is like @code{strcat} except that not more than @var{size}
-characters from @var{from} are appended to the end of @var{to}.  A single
-null character is also always appended to @var{to}, so the total
+characters from @var{from} are appended to the end of @var{to}.  A
+single null character is also always appended to @var{to}, so the total
 allocated size of @var{to} must be at least @code{@var{size} + 1} bytes
 longer than its initial length.
+
+@example
+char *
+strncat (char *to, const char *from, size_t size)
+@{
+  strncpy (to + strlen (to), from, size);
+  return to;
+@}
+@end example
+
+The behavior of @code{strncat} is undefined if the strings overlap.
 @end deftypefun
 
 Here is an example showing the use of @code{strncpy} and @code{strncat}.
@@ -320,6 +379,7 @@ main ()
 @{
   strncpy (buffer, "hello", SIZE);
   printf ("%s\n", buffer);
+  /* strlen (buffer) @r{is 5, leaving room for 4 more characters.}  */
   strncat (buffer, ", world", SIZE - strlen (buffer) - 1);
   printf ("%s\n", buffer);
 @}
@@ -333,8 +393,29 @@ hello
 hello, wo
 @end example
 
+@comment string.h
+@comment BSD
+@deftypefun {void *} bcopy (void *@var{from}, const void *@var{to}, size_t @var{size})
+This is a partially obsolete alternative for @code{memcpy}, derived from
+BSD.  Note that it is not quite equivalent to @code{memcpy}, because the
+arguments are not in the same order.
+@end deftypefun
+
+@comment string.h
+@comment BSD
+@deftypefun {void *} bzero (void *@var{block}, size_t @var{size})
+This is a partially obsolete alternative for @code{bzero}, derived from
+BSD.  Note that it is not as powerful as @code{bzero}, because the only
+value it can store is zero.
+@end deftypefun
+
 @node String/Array Comparison
 @section String/Array Comparison
+@cindex comparing strings and arrays
+@cindex string comparison functions
+@cindex array comparison functions
+@cindex predicates on strings
+@cindex predicates on arrays
 
 You can use the functions in this section to perform comparisons on the
 contents of strings and arrays.  As well as checking for equality, these
@@ -348,14 +429,10 @@ of the first characters in the strings that are not equivalent:  a
 negative value indicates that the first string is ``less'' than the
 second, while a positive value indicates that the first string is 
 ``greater''.
-@cindex comparing strings and arrays
-@cindex string comparison functions
-@cindex array comparison functions
-@cindex predicates on strings
-@cindex predicates on arrays
 
-If you are only interested in using these functions as predicates, you
-might find it helpful to hide them behind a macro definition, like this:
+If you are using these functions only to check for equality, you might
+find it makes for a cleaner program to hide them behind a macro
+definition, like this:
 
 @example
 #define str_eq(s1,s2)  (!strcmp ((s1),(s2)))
@@ -368,10 +445,13 @@ All of these functions are declared in the header file @file{string.h}.
 @comment ANSI
 @deftypefun int memcmp (const void *@var{a1}, const void *@var{a2}, size_t @var{size})
 The function @code{memcmp} compares the @var{size} bytes of memory
-beginning at @var{a1} against the @var{size} bytes of memory beginning at
-@var{a1}.  The value returned has the same sign as the difference
-between the first pair of bytes (interpreted as @code{unsigned
-char} objects) that differ.
+beginning at @var{a1} against the @var{size} bytes of memory beginning
+at @var{a1}.  The value returned has the same sign as the difference
+between the first differing pair of bytes (interpreted as @code{unsigned
+char} objects, then promoted to @code{int}).
+
+If the contents of the two blocks are equal, @code{memcmp} returns
+@code{0}.
 @end deftypefun
 
 On arbitrary arrays, the @code{memcmp} function is mostly useful for
@@ -387,8 +467,8 @@ objects to enforce alignment requirements, extra space at the end of
 unions, and extra characters at the ends of strings whose length is less
 than their allocated size.  The contents of these ``holes'' are
 indeterminate and may cause strange behavior when performing byte-wise
-comparisons.  In some cases, it may be more appropriate to perform an
-explicit component-wise comparison.
+comparisons.  For more predictable results, perform an explicit
+component-wise comparison.
 
 For example, given a structure type definition like:
 
@@ -410,10 +490,12 @@ you are better off writing a specialized comparison function to compare
 @comment string.h
 @comment ANSI
 @deftypefun int strcmp (const char *@var{s1}, const char *@var{s2})
-The @code{strcmp} function compares the string @var{s1} against @var{s2},
-returning a value that has the same sign as the difference between
-the first pair of characters (interpreted as @code{unsigned char} objects)
-that are not the same.
+The @code{strcmp} function compares the string @var{s1} against
+@var{s2}, returning a value that has the same sign as the difference
+between the first differing pair of characters (interpreted as
+@code{unsigned char} objects, then promoted to @code{int}).
+
+If the two strings are equal, @code{strcmp} returns @code{0}.
 
 A consequence of the ordering used by @code{strcmp} is that if @var{s1}
 is an initial substring of @var{s2}, then @var{s1} is considered to be
@@ -425,6 +507,8 @@ is an initial substring of @var{s2}, then @var{s1} is considered to be
 @deftypefun int strcasecmp (const char *@var{s1}, const char *@var{s2})
 This function is like @code{strcmp}, except that differences in case
 are ignored.
+
+@code{strcasecmp} is a GNU extension.
 @end deftypefun
 
 @comment string.h
@@ -437,7 +521,7 @@ the same in their first @var{size} characters, the return value is zero.
 
 Here are some examples showing the use of @code{strcmp} and @code{strncmp}.
 These examples assume the use of the ASCII character set.  (If some
-other character set --- say, EBCDIC --- is used instead, then the glyphs
+other character set---say, EBCDIC---is used instead, then the glyphs
 are associated with different numeric codes, and the return values
 and ordering may differ.)
 
@@ -456,6 +540,11 @@ strncmp ("hello, world", "hello, stupid world!!!", 5)
     @result{} 0    /* @r{The initial 5 characters are the same.} */
 @end example
 
+@comment string.h
+@comment BSD
+@deftypefun int bcmp (const void *@var{a1}, const void *@var{a2}, size_t @var{size})
+This is an obsolete alias for @code{memcmp}, derived from BSD.
+@end deftypefun
 
 @node Collation Functions
 @section Collation Functions
@@ -472,67 +561,157 @@ collated immediately after @samp{l}.
 
 You can use the functions @code{strcoll} and @code{strxfrm} (declared in
 the header file @file{string.h}) to compare strings using a collation
-ordering appropriate for the current locale.  The exact ordering
-conventions used by these functions are determined by the
-@code{LC_COLLATE} category; @pxref{Localization}.
+ordering appropriate for the current locale.  The locale used by these
+functions in particular can be specified by setting the locale for the
+@code{LC_COLLATE} category; see @ref{Localization}.
 @pindex string.h
 
-@strong{Incomplete:} I believe that in the standard C locale, the
-collation sequence for @code{strcoll} is the same as that for
-@code{strcmp}.  I'm not sure if the ANSI C standard specifies this or
-if that's just the way we've implemented it.
+In the standard C locale, the collation sequence for @code{strcoll} is
+the same as that for @code{strcmp}.
 
 Effectively, the way these functions work is by applying a mapping to
-transform the glyphs in a string to an array of codes that reflects the
-collation ordering appropriate to the current locale.
-The function @code{strcoll} performs this mapping implicitly,
-while @code{strxfrm} can be used to perform the mapping explicitly.  If
-you are making multiple comparisons using the same string or set of
-strings, it is likely to be more efficient to use @code{strxfrm} to
-transform the strings once and then do the comparisons on the
-transformed strings with @code{strcmp}, instead of passing the
-untransformed strings to @code{strcoll}.
+transform the characters in a string to a byte sequence that represents
+the string's position in the collating sequence of the current locale.
+Comparing two such byte sequences in a simple fashion is equivalent to
+comparing the strings with the locale's collating sequence.
+
+The function @code{strcoll} performs this translation implicitly, in
+order to do one comparison.  By contrast, @code{strxfrm} performs the
+mapping explicitly.  If you are making multiple comparisons using the
+same string or set of strings, it is likely to be more efficient to use
+@code{strxfrm} to transform all the strings just once, and subsequently
+compare the transformed strings with @code{strcmp}.
 
 @comment string.h
 @comment ANSI
 @deftypefun int strcoll (const char *@var{s1}, const char *@var{s2})
 The @code{strcoll} function is similar to @code{strcmp} but uses the
-current locale's collation ordering, determined by the @code{LC_COLLATE}
-category.
+collating sequence of the current locale for collation (the
+@code{LC_COLLATE} locale).
 @end deftypefun
 
+Here is an example of sorting an array of strings, using @code{strcoll}
+to compare them.  The actual sort algorithm is not written here; it
+comes from @code{qsort} (@pxref{Array Sort Function}).  The job of the
+code shown here is to say how to compare the strings while sorting them.
+(Later on in this section, we will show a way to do this more
+efficiently using @code{strxfrm}.)
+
+@example
+/* @r{This is the comparison function used with @code{qsort}.} */
+
+int
+compare_elements (char **p1, char **p2)
+@{
+  return strcmp (*p1, *p2);
+@}
+
+/* @r{This is the entry point---the function to sort}
+   @r{strings using the locale's collating sequence.} */
+
+void
+sort_strings (char **array, int nstrings)
+@{
+  /* @r{Sort @code{temp_array} by comparing the strings.} */
+  qsort (array, sizeof (char *),
+         nstrings, compare_elements);
+@}
+@end example
+
 @cindex converting string to collation order
 @comment string.h
 @comment ANSI
 @deftypefun size_t strxfrm (char *@var{to}, const char *@var{from}, size_t @var{size})
-The function @code{strxfrm} applies the collation transformation
-determined by the @code{LC_COLLATE} category of the current locale to
-the string @var{from}, and stores the transformed string in @var{to}.  Up
+The function @code{strxfrm} transforms @var{string} using the collation
+transformation determined by the locale currently selected for
+collation, and stores the transformed string in the array @var{to}.  Up
 to @var{size} characters (including a terminating null character) are
-stored.  
+stored.
 
 The behavior is undefined if the strings @var{to} and @var{from}
-overlap; @pxref{Copying and Concatenation}.
+overlap; see @ref{Copying and Concatenation}.
+
+The return value is the length of the entire transformed string.  This
+value is not affected by the value of @var{size}, but if it is greater
+than @var{size}, it means that the transformed string did not entirely
+fit in the array @var{to}.  In this case, only as much of the string as
+actually fits was stored.  To get the whole transformed string, call
+@code{strxfrm} again with a bigger output array.
+
+The transformed string may be longer than the original string, and it
+may also be shorter.
+
+If @var{size} is zero, no characters are stored in @var{to}.  In this
+case, @code{strxfrm} simply returns the number of characters that would
+be the length of the transformed string.  This is useful for determining
+what size string to allocate.  It does not matter what @var{to} is if
+@var{size} is zero; @var{to} may even be a null pointer.
+@end deftypefun
 
-The length of the entire transformed string @var{to} is returned.  This
-value is not affected by the value of @var{size}, and might be more or
-less than the length of the original string @var{from}.
+Here is an example of how you can use @code{strxfrm} when
+you plan to do many comparisons.  It does the same thing as the previous
+example, but much faster, because it has to transform each string only
+once, no matter how many times it is compared with other strings.  Even
+the time needed to allocate and free storage is much less than the time
+we save, when there are many strings.
 
-If @var{size} is zero, @var{to} is permitted to be a null pointer.  In
-this case, @code{strxfrm} simply returns the number of characters that
-would be the length of the transformed string.  This is useful for
-determining what size string to allocate.
-@end deftypefun
+@example
+struct sorter @{char *input; char *transformed; @};
 
-The string collation functions are most typically used in conjunction
-with sorting.  For example, you could use the @code{strcoll} function as
-the comparison function in conjunction with the @code{qsort} function;
-@pxref{Searching and Sorting}.  Alternatively, since sorting usually
-involves doing multiple comparisons, you could set up your data
-structures so that the key field in the objects being sorted is a 
-string produced by @code{strxfrm}.
+/* @r{This is the comparison function used with @code{qsort}}
+   @r{to sort an array of @code{struct sorter}.} */
+
+int
+compare_elements (struct sorter *p1, struct sorter *p2)
+@{
+  return strcmp (p1->transformed, p2->transformed);
+@}
 
-@strong{Incomplete:} An example is probably appropriate here.
+/* @r{This is the entry point---the function to sort}
+   @r{strings using the locale's collating sequence.} */
+
+void
+sort_strings_fast (char **array, int nstrings)
+@{
+  struct sorter temp_array[nstrings];
+  int i;
+
+  /* @r{Set up @code{temp_array}.  Each element contains}
+     @r{one input string and its transformed string.} */
+  for (i = 0; i < nstrings; i++) @{
+    int length = strlen (array[i]) * 2;
+
+    temp_array[i].input = array[i];
+
+    /* @r{Transform @code{array[i]}.}
+       @r{First try a buffer probably big enough.} */
+    while (1) @{
+      char *transformed = (char *) xmalloc (length);
+      if (strxfrm (transformed, array[i], length)
+          < length) @{
+        temp_array[i].transformed = transformed;
+        break;
+      @}
+      /* @r{Try again with a bigger buffer.} */
+      free (transformed);
+      length *= 2;
+    @}
+  @}
+
+  /* @r{Sort @code{temp_array} by comparing transformed strings.} */
+  qsort (temp_array, sizeof (struct sorter),
+         nstrings, compare_elements);
+
+  /* @r{Put the elements back in the permanent array}
+     @r{in their sorted order.} */
+  for (i = 0; i < nstrings; i++)
+    array[i] = temp_array[i].input;
+
+  /* @r{Free the strings we allocated.} */
+  for (i = 0; i < nstrings; i++)
+    free (temp_array[i].transformed);
+@}
+@end example
 
 @strong{Compatibility Note:}  The string collation functions are a new
 feature of ANSI C.  Older C dialects have no equivalent feature.
@@ -549,20 +728,20 @@ declared in the header file @file{string.h}.
 
 @comment string.h
 @comment ANSI
-@deftypefun {void *} memchr (const void *@var{a}, int @var{c}, size_t @var{size})
-This function finds the first occurrence of the byte @var{c} (converted to an
-@code{unsigned char}) in the initial @var{size} bytes of the object beginning
-at @var{a}.  A pointer to the located byte is returned, or a null pointer
-if no match was found.
+@deftypefun {void *} memchr (const void *@var{block}, int @var{c}, size_t @var{size})
+This function finds the first occurrence of the byte @var{c} (converted
+to an @code{unsigned char}) in the initial @var{size} bytes of the
+object beginning at @var{block}.  The return value is a pointer to the
+located byte, or a null pointer if no match was found.
 @end deftypefun
 
 @comment string.h
 @comment ANSI
-@deftypefun {char *} strchr (const char *@var{s}, int @var{c})
+@deftypefun {char *} strchr (const char *@var{string}, int @var{c})
 The @code{strchr} function finds the first occurrence of the character
 @var{c} (converted to a @code{char}) in the null-terminated string
-beginning at @var{s}.  A pointer to the located character is returned, or
-a null pointer if no match was found.
+beginning at @var{string}.  The return value is a pointer to the located
+character, or a null pointer if no match was found.
 
 For example,
 @example
@@ -579,9 +758,9 @@ specifying a null character as the value of the @var{c} argument.
 
 @comment string.h
 @comment ANSI
-@deftypefun {char *} strrchr (const char *@var{s}, int @var{c})
+@deftypefun {char *} strrchr (const char *@var{string}, int @var{c})
 The function @code{strrchr} is like @code{strchr}, except that it searches
-backwards from the end of the string @var{s} (instead of forwards
+backwards from the end of the string @var{string} (instead of forwards
 from the front).
 
 For example,
@@ -617,15 +796,17 @@ This is like @code{strstr}, but @var{needle} and @var{haystack} are byte
 arrays rather than null-terminated strings.  @var{needle_len} is the
 length of @var{needle} and @var{haystack_len} is the length of
 @var{haystack}.@refill
+
+This function is a GNU extension.
 @end deftypefun
 
 @comment string.h
 @comment ANSI
-@deftypefun size_t strspn (const char *@var{s1}, const char *@var{s2})
+@deftypefun size_t strspn (const char *@var{string}, const char *@var{skipset})
 The @code{strspn} (``string span'') function returns the length of the
-initial substring of @var{s1} that consists entirely of characters that
-are members of the set specified by the string @var{s2}.  The order
-of the characters in @var{s2} is not important.
+initial substring of @var{string} that consists entirely of characters that
+are members of the set specified by the string @var{skipset}.  The order
+of the characters in @var{skipset} is not important.
 
 For example,
 @example
@@ -636,12 +817,12 @@ strspn ("hello, world", "abcdefghijklmnopqrstuvwxyz")
 
 @comment string.h
 @comment ANSI
-@deftypefun size_t strcspn (const char *@var{s1}, const char *@var{s2})
+@deftypefun size_t strcspn (const char *@var{string}, const char *@var{stopset})
 The @code{strcspn} (``string complement span'') function returns the length
-of the initial substring of @var{s1} that consists entirely of characters
-that are @emph{not} members of the set specified by the string @var{s2}.
-(In other words, it returns the offset of the first character in @var{s1}
-that is a member of the set @var{s2}.)
+of the initial substring of @var{string} that consists entirely of characters
+that are @emph{not} members of the set specified by the string @var{stopset}.
+(In other words, it returns the offset of the first character in @var{string}
+that is a member of the set @var{stopset}.)
 
 For example,
 @example
@@ -652,12 +833,12 @@ strcspn ("hello, world", " \t\n,.;!?")
 
 @comment string.h
 @comment ANSI
-@deftypefun {char *} strpbrk (const char *@var{s1}, const char *@var{s2})
+@deftypefun {char *} strpbrk (const char *@var{string}, const char *@var{stopset})
 The @code{strpbrk} (``string pointer break'') function is related to
 @code{strcspn}, except that it returns a pointer to the first character
-in @var{s1} that is a member of the set @var{s2} instead of the length
-of the initial substring.  It returns a null pointer if no such character
-from @var{s2} is found.
+in @var{string} that is a member of the set @var{stopset} instead of the
+length of the initial substring.  It returns a null pointer if no such
+character from @var{stopset} is found.
 
 For example,
 @example
@@ -680,42 +861,62 @@ in the header file @file{string.h}.
 
 @comment string.h
 @comment ANSI
-@deftypefun {char *} strtok (char *@var{s1}, const char *@var{s2})
+@deftypefun {char *} strtok (char *@var{newstring}, const char *@var{delimiters})
 A string can be split into tokens by making a series of calls to the
 function @code{strtok}.
 
-The string to be split up is passed as the @var{s1} argument on the
-first call only.  The @code{strtok} function uses this to set up some
-internal state information.  Subsequent calls to get additional tokens
-from the same string are indicated by passing a null pointer as the
-@var{s1} argument.  Calling @code{strtok} with another non-null @var{s1}
-argument reinitializes the state information.  It is guaranteed that no
-other library function ever calls @code{strtok} behind your back (which
-would mess up this internal state information).
+The string to be split up is passed as the @var{newstring} argument on
+the first call only.  The @code{strtok} function uses this to set up
+some internal state information.  Subsequent calls to get additional
+tokens from the same string are indicated by passing a null pointer as
+the @var{newstring} argument.  Calling @code{strtok} with another
+non-null @var{newstring} argument reinitializes the state information.
+It is guaranteed that no other library function ever calls @code{strtok}
+behind your back (which would mess up this internal state information).
 
-The @var{s2} argument is a string that specifies a set of delimiters
+The @var{delimiters} argument is a string that specifies a set of delimiters
 that may surround the token being extracted.  All the initial characters
 that are members of this set are discarded.  The first character that is
 @emph{not} a member of this set of delimiters marks the beginning of the
 next token.  The end of the token is found by looking for the next
 character that is a member of the delimiter set.  This character in the
-original string @var{s1} is overwritten by a null character, and the
-pointer to the beginning of the token in @var{s1} is returned.
+original string @var{newstring} is overwritten by a null character, and the
+pointer to the beginning of the token in @var{newstring} is returned.
 
 On the next call to @code{strtok}, the searching begins at the next
 character beyond the one that marked the end of the previous token.
-Note that the set of delimiters @var{s2} do not have to be the same on
-every call in a series of calls to @code{strtok}.
+Note that the set of delimiters @var{delimiters} do not have to be the
+same on every call in a series of calls to @code{strtok}.
 
-If the end of the string @var{s1} is reached, or if the remainder of
+If the end of the string @var{newstring} is reached, or if the remainder of
 string consists only of delimiter characters, @code{strtok} returns
 a null pointer.
 @end deftypefun
 
+@strong{Warning:} Since @code{strtok} alters the string it is parsing,
+you always copy the string to a tempoarary buffer before parsing it with
+@code{strtok}.  If you allow @code{strtok} to modify a string that came
+from another part of your program, you are asking for trouble; that
+string may be part of a data structure that could be used for other
+purposes during the parsing, when alteration by @code{strtok} makes the
+data structure temporarily inaccurate.
+
+The string that you are operating on might even be a constant.  Then
+when @code{strtok} tries to modify it, your program will get a fatal
+signal for writing in read-only memory.  @xref{Program Error Signals}.
+
+This is a special case of a general principle: if a part of a program
+does not have as its purpose the modification of a certain data
+structure, then it is error-prone to modify the data structure
+temporarily.
+
+The function @code{strtok} is not reentrant.  @xref{Restrictions on
+Handler Functions}, for a discussion of where and why reentrancy is
+important.
+
 Here is a simple example showing the use of @code{strtok}.
 
 @comment Yes, this example has been tested.
-
 @example
 #include <string.h>
 #include <stddef.h>
@@ -736,22 +937,3 @@ token = strtok (NULL, delimiters);    /* token => "and" */
 token = strtok (NULL, delimiters);    /* token => "punctuation" */
 token = strtok (NULL, delimiters);    /* token => NULL */
 @end example
-
-Using @code{strtok} is often a bad idea, for two reasons:
-
-@itemize @bullet
-@item
-It's not reentrant.  @xref{Restrictions on Handler Functions}, for
-a discussion of where and why reentrancy is important.
-
-@item
-It won't work if the string is a constant.  For example, in the program
-above we were very careful to pass it a string variable rather than a
-string literal.  Even on non-constant strings, the destructive
-modification of the string by @code{strtok} can cause unexpected
-behavior if your program has multiple pointers to the same string.
-To some extent, passing a copy of the string (made with @code{strcpy},
-for example) can address this problem.
-@end itemize
-
-