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