Say bcopy is like memmove, not memcpy.
[kopensolaris-gnu/glibc.git] / manual / string.texi
1 @node String and Array Utilities
2 @chapter String and Array Utilities
3
4 Operations on strings (or arrays of characters) are an important part of
5 many programs.  The GNU C library provides an extensive set of string
6 utility functions, including functions for copying, concatenating,
7 comparing, and searching strings.  Many of these functions can also
8 operate on arbitrary regions of storage; for example, the @code{memcpy}
9 function can be used to copy the contents of any kind of array.  
10
11 It's fairly common for beginning C programmers to ``reinvent the wheel''
12 by duplicating this functionality in their own code, but it pays to
13 become familiar with the library functions and to make use of them,
14 since this offers benefits in maintenance, efficiency, and portability.
15
16 For instance, you could easily compare one string to another in two
17 lines of C code, but if you use the built-in @code{strcmp} function,
18 you're less likely to make a mistake.  And, since these library
19 functions are typically highly optimized, your program may run faster
20 too.
21
22 @menu
23 * Representation of Strings::   Introduction to basic concepts.
24 * String/Array Conventions::    Whether to use a string function or an
25                                  arbitrary array function.
26 * String Length::               Determining the length of a string.
27 * Copying and Concatenation::   Functions to copy the contents of strings
28                                  and arrays.
29 * String/Array Comparison::     Functions for byte-wise and character-wise
30                                  comparison.
31 * Collation Functions::         Functions for collating strings.
32 * Search Functions::            Searching for a specific element or substring.
33 * Finding Tokens in a String::  Splitting a string into tokens by looking
34                                  for delimiters.
35 @end menu
36
37 @node Representation of Strings
38 @section Representation of Strings
39 @cindex string, representation of
40
41 This section is a quick summary of string concepts for beginning C
42 programmers.  It describes how character strings are represented in C
43 and some common pitfalls.  If you are already familiar with this
44 material, you can skip this section.
45
46 @cindex string
47 @cindex null character
48 A @dfn{string} is an array of @code{char} objects.  Since array values
49 in C are converted automatically to pointers, string-valued variables
50 are usually declared to be of type @code{char *}.  By convention, a
51 @dfn{null character}, @code{'\0'}, marks the end of a string.  For
52 example, in testing to see whether the @code{char *} @var{p} points to a
53 null character marking the end of a string, you can write
54 @code{!*@var{p}} or @code{*@var{p} == '\0'}.
55
56 A null character is quite different conceptually from a null pointer,
57 although both are represented by the integer @code{0}.
58
59 @c ??? rewrite
60 Declaring a variable of type @code{char *} allocates storage only for a
61 pointer to a string, not for the string itself.  If you declare a string
62 as a @code{char *}, make sure that there is actually a character array
63 allocated for it to point to, and that the pointer is actually
64 initialized to point at the array.  Otherwise, you can get into big
65 trouble by accessing random memory locations.  You can allocate storage
66 for a string either by defining a character array variable, by
67 allocating memory dynamically using a library function like
68 @code{malloc} (@pxref{Unconstrained Allocation}), or by means of a
69 string literal.
70
71 @cindex string literal
72 @dfn{String literals} appear in C program source as strings of
73 characters between double-quote characters (@samp{"}).  In ANSI C,
74 string literals can also be formed by @dfn{string concatenation}:
75 @code{"a" "b"} is the same as @code{"ab"}.  Modification of string
76 literals is not allowed by the GNU C compiler, because literals
77 are placed in read-only storage.
78
79 Character arrays that are declared @code{const} cannot be modified
80 either.  It's generally good style to declare non-modifiable string
81 pointers to be of type @code{const char *}, since this often allows the
82 C compiler to detect accidental modifications as well as providing some
83 amount of documentation about what your program intends to do with the
84 string.
85
86 The amount of memory allocated for the character array may extend past
87 the null character that normally marks the end of the string.  In this
88 document, the term @dfn{allocation size} is always used to refer to the
89 total amount of memory allocated for the string, while the term
90 @dfn{length} refers to the number of characters up to (but not
91 including) the terminating null character.
92 @cindex length of string
93 @cindex allocation size of string
94 @cindex size of string
95 @cindex string length
96 @cindex string allocation
97
98 A notorious source of program bugs is trying to put more characters in a
99 string than fit in its allocated size.  When writing code that extends
100 strings or moves characters into a pre-allocated array, you should be
101 very careful to keep track of the length of the text and make explicit
102 checks for overflowing the array.  Many of the library functions
103 @emph{do not} do this for you!  Remember also that you need to allocate
104 an extra byte to hold the null character that marks the end of the
105 string.
106
107 @node String/Array Conventions
108 @section String/Array Conventions
109
110 This chapter describes both functions that work on arbitrary arrays or
111 blocks of memory, and functions that are specific to null-terminated
112 arrays of characters.
113
114 Functions that operate on arbitrary blocks of memory have names
115 beginning with @samp{mem} (such as @code{memcpy}) and invariably take an
116 argument which specifies the size (in bytes) of the block of memory to
117 operate on.  The array arguments and return values for these functions
118 have type @code{void *}, and as a matter of style, the elements of these
119 arrays are referred to as ``bytes''.  You can pass any kind of pointer
120 to these functions, and the @code{sizeof} operator is useful in
121 computing the value for the size argument.
122
123 In contrast, functions that operate specifically on strings have names
124 beginning with @samp{str} (such as @code{strcpy}) and look for a null
125 character to terminate the string instead of requiring an explicit size
126 argument to be passed.  (Some of these functions accept a specified
127 maximum length, but they also check for premature termination with a
128 null character.)  The array arguments and return values for these
129 functions have type @code{char *}, and the array elements are referred
130 to as ``characters''.
131
132 In many cases, there are both @samp{mem} and @samp{str} versions of a
133 function.  The one that is more appropriate to use depends on the exact
134 situation.  When your program is manipulating arbitrary arrays or blocks of
135 storage, then you should always use the @samp{mem} functions.  On the
136 other hand, when you are manipulating null-terminated strings it is
137 usually more convenient to use the @samp{str} functions, unless you
138 already know the length of the string in advance.
139
140 @node String Length
141 @section String Length
142
143 You can get the length of a string using the @code{strlen} function.
144 This function is declared in the header file @file{string.h}.
145 @pindex string.h
146
147 @comment string.h
148 @comment ANSI
149 @deftypefun size_t strlen (const char *@var{s})
150 The @code{strlen} function returns the length of the null-terminated
151 string @var{s}.  (In other words, it returns the offset of the terminating
152 null character within the array.)
153
154 For example,
155 @example
156 strlen ("hello, world")
157     @result{} 12
158 @end example
159
160 When applied to a character array, the @code{strlen} function returns
161 the length of the string stored there, not its allocation size.  You can
162 get the allocation size of the character array that holds a string using
163 the @code{sizeof} operator:
164
165 @example
166 char string[32] = "hello, world"; 
167 sizeof (string)
168     @result{} 32
169 strlen (string)
170     @result{} 12
171 @end example
172 @end deftypefun
173
174 @node Copying and Concatenation
175 @section Copying and Concatenation
176
177 You can use the functions described in this section to copy the contents
178 of strings and arrays, or to append the contents of one string to
179 another.  These functions are declared in the header file
180 @file{string.h}.
181 @pindex string.h
182 @cindex copying strings and arrays
183 @cindex string copy functions
184 @cindex array copy functions
185 @cindex concatenating strings
186 @cindex string concatenation functions
187
188 A helpful way to remember the ordering of the arguments to the functions
189 in this section is that it corresponds to an assignment expression, with
190 the destination array specified to the left of the source array.  All
191 of these functions return the address of the destination array.
192
193 Most of these functions do not work properly if the source and
194 destination arrays overlap.  For example, if the beginning of the
195 destination array overlaps the end of the source array, the original
196 contents of that part of the source array may get overwritten before it
197 is copied.  Even worse, in the case of the string functions, the null
198 character marking the end of the string may be lost, and the copy
199 function might get stuck in a loop trashing all the memory allocated to
200 your program.
201
202 All functions that have problems copying between overlapping arrays are
203 explicitly identified in this manual.  In addition to functions in this
204 section, there are a few others like @code{sprintf} and @code{scanf}.
205
206 @comment string.h
207 @comment ANSI
208 @deftypefun {void *} memcpy (void *@var{to}, const void *@var{from}, size_t @var{size})
209 The @code{memcpy} function copies @var{size} bytes from the object
210 beginning at @var{from} into the object beginning at @var{to}.  The
211 behavior of this function is undefined if the two arrays @var{to} and
212 @var{from} overlap; use @code{memmove} instead if overlapping is possible.
213
214 The value returned by @code{memcpy} is the value of @var{to}.
215
216 Here is an example of how you might use @code{memcpy} to copy the
217 contents of a @code{struct}:
218
219 @example
220 struct foo *old, *new;
221 @dots{}
222 memcpy (new, old, sizeof(struct foo));
223 @end example
224 @end deftypefun
225
226 @comment string.h
227 @comment ANSI
228 @deftypefun {void *} memmove (void *@var{to}, const void *@var{from}, size_t @var{size})
229 The @code{memmove} function is just like @code{memcpy}, except that it works
230 even if the objects @var{to} and @var{from} overlap.  However, since 
231 @code{memmove} needs to make an intermediate copy into a temporary area,
232 it can be less efficient than @code{memcpy}.
233 @c ??? memmove should need just a few insns to detect the non-overlap case
234 @c ??? and then act just like memcpy
235 @end deftypefun
236
237 @comment string.h
238 @comment SVID
239 @deftypefun {void *} memccpy (void *@var{to}, const void *@var{from}, int @var{c}, size_t @var{size})
240 This function copies no more than @var{size} bytes from @var{from} to
241 @var{to}, stopping if a byte matching @var{c} is found.  The return
242 value is a pointer into @var{to} one byte past where @var{c} was copied,
243 or a null pointer if no byte matching @var{c} appeared in the first
244 @var{size} bytes of @var{from}.
245 @end deftypefun
246
247 @comment string.h
248 @comment ANSI
249 @deftypefun {void *} memset (void *@var{block}, int @var{c}, size_t @var{size})
250 This function copies the value of @var{c} (converted to an
251 @code{unsigned char}) into each of the first @var{size} bytes of the
252 object beginning at @var{block}.  It returns the value of @var{block}.
253 @end deftypefun
254
255 @comment string.h
256 @comment ANSI
257 @deftypefun {char *} strcpy (char *@var{to}, const char *@var{from})
258 This copies characters from the string @var{from} (up to and including
259 the terminating null character) into the string @var{to}.  Like
260 @code{memcpy}, this function has undefined results if the strings
261 overlap.  The return value is the value of @var{to}.
262 @end deftypefun
263
264 @comment string.h
265 @comment ANSI
266 @deftypefun {char *} strncpy (char *@var{to}, const char *@var{from}, size_t @var{size})
267 This function is similar to @code{strcpy} but always copies exactly
268 @var{size}.
269
270 If the length of @var{from} is more than @var{size}, then @code{strncpy}
271 copies just the first @var{size} characters.
272
273 If the length of @var{from} is less than @var{size}, then @code{strncpy}
274 copies all of @var{from}, followed by enough null characters to add up
275 to @var{size} characters in all.  This behavior is rarely useful, but it
276 is specified by the ANSI C standard.
277
278 The behavior of @code{strncpy} is undefined if the strings overlap.
279
280 Using @code{strncpy} as opposed to @code{strcpy} is a way to avoid bugs
281 relating to writing past the end of the allocated space for @var{to}.
282 However, it can also make your program much slower in one common case:
283 copying a string which is probably small into a potentially large buffer.
284 In this case, @var{size} may be large, and when it is, @code{strncpy} will
285 waste a considerable amount of time copying null characters.
286 @end deftypefun
287
288 @comment string.h
289 @comment SVID
290 @deftypefun {char *} strdup (const char *@var{s})
291 This function copies the null-terminated string @var{s} into a newly
292 allocated string.  The string is allocated using @code{malloc};
293 see @ref{Unconstrained Allocation}.
294 @end deftypefun
295
296 @comment string.h
297 @comment Unknown origin
298 @deftypefun {char *} stpcpy (char *@var{to}, const char *@var{from})
299 This function is like @code{strcpy}, except that it returns a pointer to
300 the end of the string @var{to} (that is, the address of the terminating
301 null character) rather than the beginning.
302
303 For example, this program uses @code{stpcpy} to concatenate @samp{foo}
304 and @samp{bar} to produce @samp{foobar}, which it then prints.
305
306 @example
307 main ()
308 @{
309   char *to = buffer;
310   to = stpcpy (to, "foo");
311   to = stpcpy (to, "bar");
312   printf ("%s\n", buffer);
313 @}
314 @end example
315
316 This function is not part of the ANSI or POSIX standards, and is not
317 customary on Unix systems, but we did not invent it either.  Perhaps it
318 comes from MS-DOG.
319
320 Its behavior is undefined if the strings overlap.
321 @end deftypefun
322
323 @comment string.h
324 @comment ANSI
325 @deftypefun {char *} strcat (char *@var{to}, const char *@var{from})
326 The @code{strcat} function is similar to @code{strcpy}, except that the
327 characters from @var{from} are concatenated or appended to the end of
328 @var{to}, instead of overwriting it.  That is, the first character from
329 @var{from} overwrites the null character marking the end of @var{to}.
330
331 An equivalent definition for @code{strcat} would be:
332
333 @example
334 char *
335 strcat (char *to, const char *from)
336 @{
337   strcpy (to + strlen (to), from);
338   return to;
339 @}
340 @end example
341
342 This function has undefined results if the strings overlap.
343 @end deftypefun
344
345 @comment string.h
346 @comment ANSI
347 @deftypefun {char *} strncat (char *@var{to}, const char *@var{from}, size_t @var{size})
348 This function is like @code{strcat} except that not more than @var{size}
349 characters from @var{from} are appended to the end of @var{to}.  A
350 single null character is also always appended to @var{to}, so the total
351 allocated size of @var{to} must be at least @code{@var{size} + 1} bytes
352 longer than its initial length.
353
354 @example
355 char *
356 strncat (char *to, const char *from, size_t size)
357 @{
358   strncpy (to + strlen (to), from, size);
359   return to;
360 @}
361 @end example
362
363 The behavior of @code{strncat} is undefined if the strings overlap.
364 @end deftypefun
365
366 Here is an example showing the use of @code{strncpy} and @code{strncat}.
367 Notice how, in the call to @code{strncat}, the @var{size} parameter
368 is computed to avoid overflowing the character array @code{buffer}.
369
370 @example
371 #include <string.h>
372 #include <stdio.h>
373
374 #define SIZE 10
375
376 static char buffer[SIZE];
377
378 main ()
379 @{
380   strncpy (buffer, "hello", SIZE);
381   printf ("%s\n", buffer);
382   /* strlen (buffer) @r{is 5, leaving room for 4 more characters.}  */
383   strncat (buffer, ", world", SIZE - strlen (buffer) - 1);
384   printf ("%s\n", buffer);
385 @}
386 @end example
387
388 @noindent
389 The output produced by this program looks like:
390
391 @example
392 hello
393 hello, wo
394 @end example
395
396 @comment string.h
397 @comment BSD
398 @deftypefun {void *} bcopy (void *@var{from}, const void *@var{to}, size_t @var{size})
399 This is a partially obsolete alternative for @code{memmove}, derived from
400 BSD.  Note that it is not quite equivalent to @code{memmove}, because the
401 arguments are not in the same order.
402 @end deftypefun
403
404 @comment string.h
405 @comment BSD
406 @deftypefun {void *} bzero (void *@var{block}, size_t @var{size})
407 This is a partially obsolete alternative for @code{bzero}, derived from
408 BSD.  Note that it is not as powerful as @code{bzero}, because the only
409 value it can store is zero.
410 @end deftypefun
411
412 @node String/Array Comparison
413 @section String/Array Comparison
414 @cindex comparing strings and arrays
415 @cindex string comparison functions
416 @cindex array comparison functions
417 @cindex predicates on strings
418 @cindex predicates on arrays
419
420 You can use the functions in this section to perform comparisons on the
421 contents of strings and arrays.  As well as checking for equality, these
422 functions can also be used as the ordering functions for sorting
423 operations.  @xref{Searching and Sorting}, for an example of this.
424
425 Unlike most comparison operations in C, the string comparison functions
426 return a nonzero value if the strings are @emph{not} equivalent rather
427 than if they are.  The sign of the value indicates the relative ordering
428 of the first characters in the strings that are not equivalent:  a
429 negative value indicates that the first string is ``less'' than the
430 second, while a positive value indicates that the first string is 
431 ``greater''.
432
433 If you are using these functions only to check for equality, you might
434 find it makes for a cleaner program to hide them behind a macro
435 definition, like this:
436
437 @example
438 #define str_eq(s1,s2)  (!strcmp ((s1),(s2)))
439 @end example
440
441 All of these functions are declared in the header file @file{string.h}.
442 @pindex string.h
443
444 @comment string.h
445 @comment ANSI
446 @deftypefun int memcmp (const void *@var{a1}, const void *@var{a2}, size_t @var{size})
447 The function @code{memcmp} compares the @var{size} bytes of memory
448 beginning at @var{a1} against the @var{size} bytes of memory beginning
449 at @var{a1}.  The value returned has the same sign as the difference
450 between the first differing pair of bytes (interpreted as @code{unsigned
451 char} objects, then promoted to @code{int}).
452
453 If the contents of the two blocks are equal, @code{memcmp} returns
454 @code{0}.
455 @end deftypefun
456
457 On arbitrary arrays, the @code{memcmp} function is mostly useful for
458 testing equality.  It usually isn't meaningful to do byte-wise ordering
459 comparisons on arrays of things other than bytes.  For example, a
460 byte-wise comparison on the bytes that make up floating-point numbers
461 isn't likely to tell you anything about the relationship between the
462 values of the floating-point numbers.
463
464 You should also be careful about using @code{memcmp} to compare objects
465 that can contain ``holes'', such as the padding inserted into structure
466 objects to enforce alignment requirements, extra space at the end of
467 unions, and extra characters at the ends of strings whose length is less
468 than their allocated size.  The contents of these ``holes'' are
469 indeterminate and may cause strange behavior when performing byte-wise
470 comparisons.  For more predictable results, perform an explicit
471 component-wise comparison.
472
473 For example, given a structure type definition like:
474
475 @example
476 struct foo @{
477   unsigned char tag;
478   union @{
479     double f;
480     long i;
481     char *p;
482     @} value;
483   @};
484 @end example
485
486 @noindent
487 you are better off writing a specialized comparison function to compare
488 @code{struct foo} objects instead of comparing them with @code{memcmp}.
489
490 @comment string.h
491 @comment ANSI
492 @deftypefun int strcmp (const char *@var{s1}, const char *@var{s2})
493 The @code{strcmp} function compares the string @var{s1} against
494 @var{s2}, returning a value that has the same sign as the difference
495 between the first differing pair of characters (interpreted as
496 @code{unsigned char} objects, then promoted to @code{int}).
497
498 If the two strings are equal, @code{strcmp} returns @code{0}.
499
500 A consequence of the ordering used by @code{strcmp} is that if @var{s1}
501 is an initial substring of @var{s2}, then @var{s1} is considered to be
502 ``less than'' @var{s2}.
503 @end deftypefun
504
505 @comment string.h
506 @comment BSD
507 @deftypefun int strcasecmp (const char *@var{s1}, const char *@var{s2})
508 This function is like @code{strcmp}, except that differences in case
509 are ignored.
510
511 @code{strcasecmp} is a GNU extension.
512 @end deftypefun
513
514 @comment string.h
515 @comment ANSI
516 @deftypefun int strncmp (const char *@var{s1}, const char *@var{s2}, size_t @var{size})
517 This function is the similar to @code{strcmp}, except that no more than
518 @var{size} characters are compared.  In other words, if the two strings are
519 the same in their first @var{size} characters, the return value is zero.
520 @end deftypefun
521
522 Here are some examples showing the use of @code{strcmp} and @code{strncmp}.
523 These examples assume the use of the ASCII character set.  (If some
524 other character set---say, EBCDIC---is used instead, then the glyphs
525 are associated with different numeric codes, and the return values
526 and ordering may differ.)
527
528 @example
529 strcmp ("hello", "hello")
530     @result{} 0    /* @r{These two strings are the same.} */
531 strcmp ("hello", "Hello")
532     @result{} 32   /* @r{Comparisons are case-sensitive.} */
533 strcmp ("hello", "world")
534     @result{} -15  /* @r{The character @code{'h'} comes before @code{'w'}.} */
535 strcmp ("hello", "hello, world")
536     @result{} -44  /* @r{Comparing a null character against a comma.} */
537 strncmp ("hello", "hello, world"", 5)
538     @result{} 0    /* @r{The initial 5 characters are the same.} */
539 strncmp ("hello, world", "hello, stupid world!!!", 5)
540     @result{} 0    /* @r{The initial 5 characters are the same.} */
541 @end example
542
543 @comment string.h
544 @comment BSD
545 @deftypefun int bcmp (const void *@var{a1}, const void *@var{a2}, size_t @var{size})
546 This is an obsolete alias for @code{memcmp}, derived from BSD.
547 @end deftypefun
548
549 @node Collation Functions
550 @section Collation Functions
551
552 @cindex collating strings
553 @cindex string collation functions
554
555 In some locales, the conventions for lexicographic ordering differ from
556 the strict numeric ordering of character codes.  For example, in Spanish
557 most glyphs with diacritical marks such as accents are not considered
558 distinct letters for the purposes of collation.  On the other hand, the
559 two-character sequence @samp{ll} is treated as a single letter that is
560 collated immediately after @samp{l}.
561
562 You can use the functions @code{strcoll} and @code{strxfrm} (declared in
563 the header file @file{string.h}) to compare strings using a collation
564 ordering appropriate for the current locale.  The locale used by these
565 functions in particular can be specified by setting the locale for the
566 @code{LC_COLLATE} category; see @ref{Locales}.
567 @pindex string.h
568
569 In the standard C locale, the collation sequence for @code{strcoll} is
570 the same as that for @code{strcmp}.
571
572 Effectively, the way these functions work is by applying a mapping to
573 transform the characters in a string to a byte sequence that represents
574 the string's position in the collating sequence of the current locale.
575 Comparing two such byte sequences in a simple fashion is equivalent to
576 comparing the strings with the locale's collating sequence.
577
578 The function @code{strcoll} performs this translation implicitly, in
579 order to do one comparison.  By contrast, @code{strxfrm} performs the
580 mapping explicitly.  If you are making multiple comparisons using the
581 same string or set of strings, it is likely to be more efficient to use
582 @code{strxfrm} to transform all the strings just once, and subsequently
583 compare the transformed strings with @code{strcmp}.
584
585 @comment string.h
586 @comment ANSI
587 @deftypefun int strcoll (const char *@var{s1}, const char *@var{s2})
588 The @code{strcoll} function is similar to @code{strcmp} but uses the
589 collating sequence of the current locale for collation (the
590 @code{LC_COLLATE} locale).
591 @end deftypefun
592
593 Here is an example of sorting an array of strings, using @code{strcoll}
594 to compare them.  The actual sort algorithm is not written here; it
595 comes from @code{qsort} (@pxref{Array Sort Function}).  The job of the
596 code shown here is to say how to compare the strings while sorting them.
597 (Later on in this section, we will show a way to do this more
598 efficiently using @code{strxfrm}.)
599
600 @example
601 /* @r{This is the comparison function used with @code{qsort}.} */
602
603 int
604 compare_elements (char **p1, char **p2)
605 @{
606   return strcmp (*p1, *p2);
607 @}
608
609 /* @r{This is the entry point---the function to sort}
610    @r{strings using the locale's collating sequence.} */
611
612 void
613 sort_strings (char **array, int nstrings)
614 @{
615   /* @r{Sort @code{temp_array} by comparing the strings.} */
616   qsort (array, sizeof (char *),
617          nstrings, compare_elements);
618 @}
619 @end example
620
621 @cindex converting string to collation order
622 @comment string.h
623 @comment ANSI
624 @deftypefun size_t strxfrm (char *@var{to}, const char *@var{from}, size_t @var{size})
625 The function @code{strxfrm} transforms @var{string} using the collation
626 transformation determined by the locale currently selected for
627 collation, and stores the transformed string in the array @var{to}.  Up
628 to @var{size} characters (including a terminating null character) are
629 stored.
630
631 The behavior is undefined if the strings @var{to} and @var{from}
632 overlap; see @ref{Copying and Concatenation}.
633
634 The return value is the length of the entire transformed string.  This
635 value is not affected by the value of @var{size}, but if it is greater
636 than @var{size}, it means that the transformed string did not entirely
637 fit in the array @var{to}.  In this case, only as much of the string as
638 actually fits was stored.  To get the whole transformed string, call
639 @code{strxfrm} again with a bigger output array.
640
641 The transformed string may be longer than the original string, and it
642 may also be shorter.
643
644 If @var{size} is zero, no characters are stored in @var{to}.  In this
645 case, @code{strxfrm} simply returns the number of characters that would
646 be the length of the transformed string.  This is useful for determining
647 what size string to allocate.  It does not matter what @var{to} is if
648 @var{size} is zero; @var{to} may even be a null pointer.
649 @end deftypefun
650
651 Here is an example of how you can use @code{strxfrm} when
652 you plan to do many comparisons.  It does the same thing as the previous
653 example, but much faster, because it has to transform each string only
654 once, no matter how many times it is compared with other strings.  Even
655 the time needed to allocate and free storage is much less than the time
656 we save, when there are many strings.
657
658 @example
659 struct sorter @{char *input; char *transformed; @};
660
661 /* @r{This is the comparison function used with @code{qsort}}
662    @r{to sort an array of @code{struct sorter}.} */
663
664 int
665 compare_elements (struct sorter *p1, struct sorter *p2)
666 @{
667   return strcmp (p1->transformed, p2->transformed);
668 @}
669
670 /* @r{This is the entry point---the function to sort}
671    @r{strings using the locale's collating sequence.} */
672
673 void
674 sort_strings_fast (char **array, int nstrings)
675 @{
676   struct sorter temp_array[nstrings];
677   int i;
678
679   /* @r{Set up @code{temp_array}.  Each element contains}
680      @r{one input string and its transformed string.} */
681   for (i = 0; i < nstrings; i++) @{
682     int length = strlen (array[i]) * 2;
683
684     temp_array[i].input = array[i];
685
686     /* @r{Transform @code{array[i]}.}
687        @r{First try a buffer probably big enough.} */
688     while (1) @{
689       char *transformed = (char *) xmalloc (length);
690       if (strxfrm (transformed, array[i], length)
691           < length) @{
692         temp_array[i].transformed = transformed;
693         break;
694       @}
695       /* @r{Try again with a bigger buffer.} */
696       free (transformed);
697       length *= 2;
698     @}
699   @}
700
701   /* @r{Sort @code{temp_array} by comparing transformed strings.} */
702   qsort (temp_array, sizeof (struct sorter),
703          nstrings, compare_elements);
704
705   /* @r{Put the elements back in the permanent array}
706      @r{in their sorted order.} */
707   for (i = 0; i < nstrings; i++)
708     array[i] = temp_array[i].input;
709
710   /* @r{Free the strings we allocated.} */
711   for (i = 0; i < nstrings; i++)
712     free (temp_array[i].transformed);
713 @}
714 @end example
715
716 @strong{Compatibility Note:}  The string collation functions are a new
717 feature of ANSI C.  Older C dialects have no equivalent feature.
718
719 @node Search Functions
720 @section Search Functions
721
722 This section describes library functions which perform various kinds
723 of searching operations on strings and arrays.  These functions are
724 declared in the header file @file{string.h}.
725 @pindex string.h
726 @cindex search functions (for strings)
727 @cindex string search functions
728
729 @comment string.h
730 @comment ANSI
731 @deftypefun {void *} memchr (const void *@var{block}, int @var{c}, size_t @var{size})
732 This function finds the first occurrence of the byte @var{c} (converted
733 to an @code{unsigned char}) in the initial @var{size} bytes of the
734 object beginning at @var{block}.  The return value is a pointer to the
735 located byte, or a null pointer if no match was found.
736 @end deftypefun
737
738 @comment string.h
739 @comment ANSI
740 @deftypefun {char *} strchr (const char *@var{string}, int @var{c})
741 The @code{strchr} function finds the first occurrence of the character
742 @var{c} (converted to a @code{char}) in the null-terminated string
743 beginning at @var{string}.  The return value is a pointer to the located
744 character, or a null pointer if no match was found.
745
746 For example,
747 @example
748 strchr ("hello, world", 'l')
749     @result{} "llo, world"
750 strchr ("hello, world", '?')
751     @result{} NULL
752 @end example    
753
754 The terminating null character is considered to be part of the string,
755 so you can use this function get a pointer to the end of a string by
756 specifying a null character as the value of the @var{c} argument.
757 @end deftypefun
758
759 @comment string.h
760 @comment ANSI
761 @deftypefun {char *} strrchr (const char *@var{string}, int @var{c})
762 The function @code{strrchr} is like @code{strchr}, except that it searches
763 backwards from the end of the string @var{string} (instead of forwards
764 from the front).
765
766 For example,
767 @example
768 strrchr ("hello, world", 'l')
769     @result{} "ld"
770 @end example
771 @end deftypefun
772
773 @comment string.h
774 @comment ANSI
775 @deftypefun {char *} strstr (const char *@var{needle}, const char *@var{haystack})
776 This is like @code{strchr}, except that it searches @var{needle} for a
777 substring @var{haystack} rather than just a single character.  It
778 returns a pointer into the string @var{needle} that is the first
779 character of the substring, or a null pointer if no match was found.  If
780 @var{haystack} is an empty string, the function returns @var{needle}.
781
782 For example,
783 @example
784 strstr ("hello, world", "l")
785     @result{} "llo, world"
786 strstr ("hello, world", "wo")
787     @result{} "world"
788 @end example
789 @end deftypefun
790
791
792 @comment string.h
793 @comment GNU
794 @deftypefun {void *} memstr (const void *@var{needle}, size_t @var{needle_len},@*const void *@var{haystack}, size_t @var{haystack_len})
795 This is like @code{strstr}, but @var{needle} and @var{haystack} are byte
796 arrays rather than null-terminated strings.  @var{needle_len} is the
797 length of @var{needle} and @var{haystack_len} is the length of
798 @var{haystack}.@refill
799
800 This function is a GNU extension.
801 @end deftypefun
802
803 @comment string.h
804 @comment ANSI
805 @deftypefun size_t strspn (const char *@var{string}, const char *@var{skipset})
806 The @code{strspn} (``string span'') function returns the length of the
807 initial substring of @var{string} that consists entirely of characters that
808 are members of the set specified by the string @var{skipset}.  The order
809 of the characters in @var{skipset} is not important.
810
811 For example,
812 @example
813 strspn ("hello, world", "abcdefghijklmnopqrstuvwxyz")
814     @result{} 5
815 @end example
816 @end deftypefun
817
818 @comment string.h
819 @comment ANSI
820 @deftypefun size_t strcspn (const char *@var{string}, const char *@var{stopset})
821 The @code{strcspn} (``string complement span'') function returns the length
822 of the initial substring of @var{string} that consists entirely of characters
823 that are @emph{not} members of the set specified by the string @var{stopset}.
824 (In other words, it returns the offset of the first character in @var{string}
825 that is a member of the set @var{stopset}.)
826
827 For example,
828 @example
829 strcspn ("hello, world", " \t\n,.;!?")
830     @result{} 5
831 @end example
832 @end deftypefun
833
834 @comment string.h
835 @comment ANSI
836 @deftypefun {char *} strpbrk (const char *@var{string}, const char *@var{stopset})
837 The @code{strpbrk} (``string pointer break'') function is related to
838 @code{strcspn}, except that it returns a pointer to the first character
839 in @var{string} that is a member of the set @var{stopset} instead of the
840 length of the initial substring.  It returns a null pointer if no such
841 character from @var{stopset} is found.
842
843 For example,
844 @example
845 strpbrk ("hello, world", " \t\n,.;!?")
846     @result{} ", world"
847 @end example
848 @end deftypefun
849
850 @node Finding Tokens in a String
851 @section Finding Tokens in a String
852
853 @cindex tokenizing strings
854 @cindex breaking a string into tokens
855 @cindex parsing tokens from a string
856 It's fairly common for programs to have a need to do some simple kinds
857 of lexical analysis and parsing, such as splitting a command string up
858 into tokens.  You can do this with the @code{strtok} function, declared
859 in the header file @file{string.h}.
860 @pindex string.h
861
862 @comment string.h
863 @comment ANSI
864 @deftypefun {char *} strtok (char *@var{newstring}, const char *@var{delimiters})
865 A string can be split into tokens by making a series of calls to the
866 function @code{strtok}.
867
868 The string to be split up is passed as the @var{newstring} argument on
869 the first call only.  The @code{strtok} function uses this to set up
870 some internal state information.  Subsequent calls to get additional
871 tokens from the same string are indicated by passing a null pointer as
872 the @var{newstring} argument.  Calling @code{strtok} with another
873 non-null @var{newstring} argument reinitializes the state information.
874 It is guaranteed that no other library function ever calls @code{strtok}
875 behind your back (which would mess up this internal state information).
876
877 The @var{delimiters} argument is a string that specifies a set of delimiters
878 that may surround the token being extracted.  All the initial characters
879 that are members of this set are discarded.  The first character that is
880 @emph{not} a member of this set of delimiters marks the beginning of the
881 next token.  The end of the token is found by looking for the next
882 character that is a member of the delimiter set.  This character in the
883 original string @var{newstring} is overwritten by a null character, and the
884 pointer to the beginning of the token in @var{newstring} is returned.
885
886 On the next call to @code{strtok}, the searching begins at the next
887 character beyond the one that marked the end of the previous token.
888 Note that the set of delimiters @var{delimiters} do not have to be the
889 same on every call in a series of calls to @code{strtok}.
890
891 If the end of the string @var{newstring} is reached, or if the remainder of
892 string consists only of delimiter characters, @code{strtok} returns
893 a null pointer.
894 @end deftypefun
895
896 @strong{Warning:} Since @code{strtok} alters the string it is parsing,
897 you always copy the string to a temporary buffer before parsing it with
898 @code{strtok}.  If you allow @code{strtok} to modify a string that came
899 from another part of your program, you are asking for trouble; that
900 string may be part of a data structure that could be used for other
901 purposes during the parsing, when alteration by @code{strtok} makes the
902 data structure temporarily inaccurate.
903
904 The string that you are operating on might even be a constant.  Then
905 when @code{strtok} tries to modify it, your program will get a fatal
906 signal for writing in read-only memory.  @xref{Program Error Signals}.
907
908 This is a special case of a general principle: if a part of a program
909 does not have as its purpose the modification of a certain data
910 structure, then it is error-prone to modify the data structure
911 temporarily.
912
913 The function @code{strtok} is not reentrant.  @xref{Nonreentrancy}, for
914 a discussion of where and why reentrancy is important.
915
916 Here is a simple example showing the use of @code{strtok}.
917
918 @comment Yes, this example has been tested.
919 @example
920 #include <string.h>
921 #include <stddef.h>
922
923 @dots{}
924
925 char string[] = "words separated by spaces -- and, punctuation!";
926 const char delimiters[] = " .,;:!-";
927 char *token;
928
929 @dots{}
930
931 token = strtok (string, delimiters);  /* token => "words" */
932 token = strtok (NULL, delimiters);    /* token => "separated" */
933 token = strtok (NULL, delimiters);    /* token => "by" */
934 token = strtok (NULL, delimiters);    /* token => "spaces" */
935 token = strtok (NULL, delimiters);    /* token => "and" */
936 token = strtok (NULL, delimiters);    /* token => "punctuation" */
937 token = strtok (NULL, delimiters);    /* token => NULL */
938 @end example