(Search Functions): Add missing end for memrchr description.
[kopensolaris-gnu/glibc.git] / manual / string.texi
1 @node String and Array Utilities, Character Set Handling, Character Handling, Top
2 @c %MENU% Utilities for copying and comparing strings and arrays
3 @chapter String and Array Utilities
4
5 Operations on strings (or arrays of characters) are an important part of
6 many programs.  The GNU C library provides an extensive set of string
7 utility functions, including functions for copying, concatenating,
8 comparing, and searching strings.  Many of these functions can also
9 operate on arbitrary regions of storage; for example, the @code{memcpy}
10 function can be used to copy the contents of any kind of array.
11
12 It's fairly common for beginning C programmers to ``reinvent the wheel''
13 by duplicating this functionality in their own code, but it pays to
14 become familiar with the library functions and to make use of them,
15 since this offers benefits in maintenance, efficiency, and portability.
16
17 For instance, you could easily compare one string to another in two
18 lines of C code, but if you use the built-in @code{strcmp} function,
19 you're less likely to make a mistake.  And, since these library
20 functions are typically highly optimized, your program may run faster
21 too.
22
23 @menu
24 * Representation of Strings::   Introduction to basic concepts.
25 * String/Array Conventions::    Whether to use a string function or an
26                                  arbitrary array function.
27 * String Length::               Determining the length of a string.
28 * Copying and Concatenation::   Functions to copy the contents of strings
29                                  and arrays.
30 * String/Array Comparison::     Functions for byte-wise and character-wise
31                                  comparison.
32 * Collation Functions::         Functions for collating strings.
33 * Search Functions::            Searching for a specific element or substring.
34 * Finding Tokens in a String::  Splitting a string into tokens by looking
35                                  for delimiters.
36 * Encode Binary Data::          Encoding and Decoding of Binary Data.
37 * Argz and Envz Vectors::       Null-separated string vectors.
38 @end menu
39
40 @node Representation of Strings
41 @section Representation of Strings
42 @cindex string, representation of
43
44 This section is a quick summary of string concepts for beginning C
45 programmers.  It describes how character strings are represented in C
46 and some common pitfalls.  If you are already familiar with this
47 material, you can skip this section.
48
49 @cindex string
50 @cindex null character
51 A @dfn{string} is an array of @code{char} objects.  But string-valued
52 variables are usually declared to be pointers of type @code{char *}.
53 Such variables do not include space for the text of a string; that has
54 to be stored somewhere else---in an array variable, a string constant,
55 or dynamically allocated memory (@pxref{Memory Allocation}).  It's up to
56 you to store the address of the chosen memory space into the pointer
57 variable.  Alternatively you can store a @dfn{null pointer} in the
58 pointer variable.  The null pointer does not point anywhere, so
59 attempting to reference the string it points to gets an error.
60
61 By convention, a @dfn{null character}, @code{'\0'}, marks the end of a
62 string.  For example, in testing to see whether the @code{char *}
63 variable @var{p} points to a null character marking the end of a string,
64 you can write @code{!*@var{p}} or @code{*@var{p} == '\0'}.
65
66 A null character is quite different conceptually from a null pointer,
67 although both are represented by the integer @code{0}.
68
69 @cindex string literal
70 @dfn{String literals} appear in C program source as strings of
71 characters between double-quote characters (@samp{"}).  In @w{ISO C},
72 string literals can also be formed by @dfn{string concatenation}:
73 @code{"a" "b"} is the same as @code{"ab"}.  Modification of string
74 literals is not allowed by the GNU C compiler, because literals
75 are placed in read-only storage.
76
77 Character arrays that are declared @code{const} cannot be modified
78 either.  It's generally good style to declare non-modifiable string
79 pointers to be of type @code{const char *}, since this often allows the
80 C compiler to detect accidental modifications as well as providing some
81 amount of documentation about what your program intends to do with the
82 string.
83
84 The amount of memory allocated for the character array may extend past
85 the null character that normally marks the end of the string.  In this
86 document, the term @dfn{allocated size} is always used to refer to the
87 total amount of memory allocated for the string, while the term
88 @dfn{length} refers to the number of characters up to (but not
89 including) the terminating null character.
90 @cindex length of string
91 @cindex allocation size of string
92 @cindex size of string
93 @cindex string length
94 @cindex string allocation
95
96 A notorious source of program bugs is trying to put more characters in a
97 string than fit in its allocated size.  When writing code that extends
98 strings or moves characters into a pre-allocated array, you should be
99 very careful to keep track of the length of the text and make explicit
100 checks for overflowing the array.  Many of the library functions
101 @emph{do not} do this for you!  Remember also that you need to allocate
102 an extra byte to hold the null character that marks the end of the
103 string.
104
105 @node String/Array Conventions
106 @section String and Array Conventions
107
108 This chapter describes both functions that work on arbitrary arrays or
109 blocks of memory, and functions that are specific to null-terminated
110 arrays of characters.
111
112 Functions that operate on arbitrary blocks of memory have names
113 beginning with @samp{mem} (such as @code{memcpy}) and invariably take an
114 argument which specifies the size (in bytes) of the block of memory to
115 operate on.  The array arguments and return values for these functions
116 have type @code{void *}, and as a matter of style, the elements of these
117 arrays are referred to as ``bytes''.  You can pass any kind of pointer
118 to these functions, and the @code{sizeof} operator is useful in
119 computing the value for the size argument.
120
121 In contrast, functions that operate specifically on strings have names
122 beginning with @samp{str} (such as @code{strcpy}) and look for a null
123 character to terminate the string instead of requiring an explicit size
124 argument to be passed.  (Some of these functions accept a specified
125 maximum length, but they also check for premature termination with a
126 null character.)  The array arguments and return values for these
127 functions have type @code{char *}, and the array elements are referred
128 to as ``characters''.
129
130 In many cases, there are both @samp{mem} and @samp{str} versions of a
131 function.  The one that is more appropriate to use depends on the exact
132 situation.  When your program is manipulating arbitrary arrays or blocks of
133 storage, then you should always use the @samp{mem} functions.  On the
134 other hand, when you are manipulating null-terminated strings it is
135 usually more convenient to use the @samp{str} functions, unless you
136 already know the length of the string in advance.
137
138 @node String Length
139 @section String Length
140
141 You can get the length of a string using the @code{strlen} function.
142 This function is declared in the header file @file{string.h}.
143 @pindex string.h
144
145 @comment string.h
146 @comment ISO
147 @deftypefun size_t strlen (const char *@var{s})
148 The @code{strlen} function returns the length of the null-terminated
149 string @var{s}.  (In other words, it returns the offset of the terminating
150 null character within the array.)
151
152 For example,
153 @smallexample
154 strlen ("hello, world")
155     @result{} 12
156 @end smallexample
157
158 When applied to a character array, the @code{strlen} function returns
159 the length of the string stored there, not its allocated size.  You can
160 get the allocated size of the character array that holds a string using
161 the @code{sizeof} operator:
162
163 @smallexample
164 char string[32] = "hello, world";
165 sizeof (string)
166     @result{} 32
167 strlen (string)
168     @result{} 12
169 @end smallexample
170
171 But beware, this will not work unless @var{string} is the character
172 array itself, not a pointer to it.  For example:
173
174 @smallexample
175 char string[32] = "hello, world";
176 char *ptr = string;
177 sizeof (string)
178     @result{} 32
179 sizeof (ptr)
180     @result{} 4  /* @r{(on a machine with 4 byte pointers)} */
181 @end smallexample
182
183 This is an easy mistake to make when you are working with functions that
184 take string arguments; those arguments are always pointers, not arrays.
185
186 @end deftypefun
187
188 @comment string.h
189 @comment GNU
190 @deftypefun size_t strnlen (const char *@var{s}, size_t @var{maxlen})
191 The @code{strnlen} function returns the length of the null-terminated
192 string @var{s} is this length is smaller than @var{maxlen}.  Otherwise
193 it returns @var{maxlen}.  Therefore this function is equivalent to
194 @code{(strlen (@var{s}) < n ? strlen (@var{s}) : @var{maxlen})} but it
195 is more efficient.
196
197 @smallexample
198 char string[32] = "hello, world";
199 strnlen (string, 32)
200     @result{} 12
201 strnlen (string, 5)
202     @result{} 5
203 @end smallexample
204
205 This function is a GNU extension.
206 @end deftypefun
207
208 @node Copying and Concatenation
209 @section Copying and Concatenation
210
211 You can use the functions described in this section to copy the contents
212 of strings and arrays, or to append the contents of one string to
213 another.  These functions are declared in the header file
214 @file{string.h}.
215 @pindex string.h
216 @cindex copying strings and arrays
217 @cindex string copy functions
218 @cindex array copy functions
219 @cindex concatenating strings
220 @cindex string concatenation functions
221
222 A helpful way to remember the ordering of the arguments to the functions
223 in this section is that it corresponds to an assignment expression, with
224 the destination array specified to the left of the source array.  All
225 of these functions return the address of the destination array.
226
227 Most of these functions do not work properly if the source and
228 destination arrays overlap.  For example, if the beginning of the
229 destination array overlaps the end of the source array, the original
230 contents of that part of the source array may get overwritten before it
231 is copied.  Even worse, in the case of the string functions, the null
232 character marking the end of the string may be lost, and the copy
233 function might get stuck in a loop trashing all the memory allocated to
234 your program.
235
236 All functions that have problems copying between overlapping arrays are
237 explicitly identified in this manual.  In addition to functions in this
238 section, there are a few others like @code{sprintf} (@pxref{Formatted
239 Output Functions}) and @code{scanf} (@pxref{Formatted Input
240 Functions}).
241
242 @comment string.h
243 @comment ISO
244 @deftypefun {void *} memcpy (void *@var{to}, const void *@var{from}, size_t @var{size})
245 The @code{memcpy} function copies @var{size} bytes from the object
246 beginning at @var{from} into the object beginning at @var{to}.  The
247 behavior of this function is undefined if the two arrays @var{to} and
248 @var{from} overlap; use @code{memmove} instead if overlapping is possible.
249
250 The value returned by @code{memcpy} is the value of @var{to}.
251
252 Here is an example of how you might use @code{memcpy} to copy the
253 contents of an array:
254
255 @smallexample
256 struct foo *oldarray, *newarray;
257 int arraysize;
258 @dots{}
259 memcpy (new, old, arraysize * sizeof (struct foo));
260 @end smallexample
261 @end deftypefun
262
263 @comment string.h
264 @comment GNU
265 @deftypefun {void *} mempcpy (void *@var{to}, const void *@var{from}, size_t @var{size})
266 The @code{mempcpy} function is nearly identical to the @code{memcpy}
267 function.  It copies @var{size} bytes from the object beginning at
268 @code{from} into the object pointed to by @var{to}.  But instead of
269 returning the value of @code{to} it returns a pointer to the byte
270 following the last written byte in the object beginning at @var{to}.
271 I.e., the value is @code{((void *) ((char *) @var{to} + @var{size}))}.
272
273 This function is useful in situations where a number of objects shall be
274 copied to consecutive memory positions.
275
276 @smallexample
277 void *
278 combine (void *o1, size_t s1, void *o2, size_t s2)
279 @{
280   void *result = malloc (s1 + s2);
281   if (result != NULL)
282     mempcpy (mempcpy (result, o1, s1), o2, s2);
283   return result;
284 @}
285 @end smallexample
286
287 This function is a GNU extension.
288 @end deftypefun
289
290 @comment string.h
291 @comment ISO
292 @deftypefun {void *} memmove (void *@var{to}, const void *@var{from}, size_t @var{size})
293 @code{memmove} copies the @var{size} bytes at @var{from} into the
294 @var{size} bytes at @var{to}, even if those two blocks of space
295 overlap.  In the case of overlap, @code{memmove} is careful to copy the
296 original values of the bytes in the block at @var{from}, including those
297 bytes which also belong to the block at @var{to}.
298 @end deftypefun
299
300 @comment string.h
301 @comment SVID
302 @deftypefun {void *} memccpy (void *@var{to}, const void *@var{from}, int @var{c}, size_t @var{size})
303 This function copies no more than @var{size} bytes from @var{from} to
304 @var{to}, stopping if a byte matching @var{c} is found.  The return
305 value is a pointer into @var{to} one byte past where @var{c} was copied,
306 or a null pointer if no byte matching @var{c} appeared in the first
307 @var{size} bytes of @var{from}.
308 @end deftypefun
309
310 @comment string.h
311 @comment ISO
312 @deftypefun {void *} memset (void *@var{block}, int @var{c}, size_t @var{size})
313 This function copies the value of @var{c} (converted to an
314 @code{unsigned char}) into each of the first @var{size} bytes of the
315 object beginning at @var{block}.  It returns the value of @var{block}.
316 @end deftypefun
317
318 @comment string.h
319 @comment ISO
320 @deftypefun {char *} strcpy (char *@var{to}, const char *@var{from})
321 This copies characters from the string @var{from} (up to and including
322 the terminating null character) into the string @var{to}.  Like
323 @code{memcpy}, this function has undefined results if the strings
324 overlap.  The return value is the value of @var{to}.
325 @end deftypefun
326
327 @comment string.h
328 @comment ISO
329 @deftypefun {char *} strncpy (char *@var{to}, const char *@var{from}, size_t @var{size})
330 This function is similar to @code{strcpy} but always copies exactly
331 @var{size} characters into @var{to}.
332
333 If the length of @var{from} is more than @var{size}, then @code{strncpy}
334 copies just the first @var{size} characters.  Note that in this case
335 there is no null terminator written into @var{to}.
336
337 If the length of @var{from} is less than @var{size}, then @code{strncpy}
338 copies all of @var{from}, followed by enough null characters to add up
339 to @var{size} characters in all.  This behavior is rarely useful, but it
340 is specified by the @w{ISO C} standard.
341
342 The behavior of @code{strncpy} is undefined if the strings overlap.
343
344 Using @code{strncpy} as opposed to @code{strcpy} is a way to avoid bugs
345 relating to writing past the end of the allocated space for @var{to}.
346 However, it can also make your program much slower in one common case:
347 copying a string which is probably small into a potentially large buffer.
348 In this case, @var{size} may be large, and when it is, @code{strncpy} will
349 waste a considerable amount of time copying null characters.
350 @end deftypefun
351
352 @comment string.h
353 @comment SVID
354 @deftypefun {char *} strdup (const char *@var{s})
355 This function copies the null-terminated string @var{s} into a newly
356 allocated string.  The string is allocated using @code{malloc}; see
357 @ref{Unconstrained Allocation}.  If @code{malloc} cannot allocate space
358 for the new string, @code{strdup} returns a null pointer.  Otherwise it
359 returns a pointer to the new string.
360 @end deftypefun
361
362 @comment string.h
363 @comment GNU
364 @deftypefun {char *} strndup (const char *@var{s}, size_t @var{size})
365 This function is similar to @code{strdup} but always copies at most
366 @var{size} characters into the newly allocated string.
367
368 If the length of @var{s} is more than @var{size}, then @code{strndup}
369 copies just the first @var{size} characters and adds a closing null
370 terminator.  Otherwise all characters are copied and the string is
371 terminated.
372
373 This function is different to @code{strncpy} in that it always
374 terminates the destination string.
375
376 @code{strndup} is a GNU extension.
377 @end deftypefun
378
379 @comment string.h
380 @comment Unknown origin
381 @deftypefun {char *} stpcpy (char *@var{to}, const char *@var{from})
382 This function is like @code{strcpy}, except that it returns a pointer to
383 the end of the string @var{to} (that is, the address of the terminating
384 null character) rather than the beginning.
385
386 For example, this program uses @code{stpcpy} to concatenate @samp{foo}
387 and @samp{bar} to produce @samp{foobar}, which it then prints.
388
389 @smallexample
390 @include stpcpy.c.texi
391 @end smallexample
392
393 This function is not part of the ISO or POSIX standards, and is not
394 customary on Unix systems, but we did not invent it either.  Perhaps it
395 comes from MS-DOG.
396
397 Its behavior is undefined if the strings overlap.
398 @end deftypefun
399
400 @comment string.h
401 @comment GNU
402 @deftypefun {char *} stpncpy (char *@var{to}, const char *@var{from}, size_t @var{size})
403 This function is similar to @code{stpcpy} but copies always exactly
404 @var{size} characters into @var{to}.
405
406 If the length of @var{from} is more then @var{size}, then @code{stpncpy}
407 copies just the first @var{size} characters and returns a pointer to the
408 character directly following the one which was copied last.  Note that in
409 this case there is no null terminator written into @var{to}.
410
411 If the length of @var{from} is less than @var{size}, then @code{stpncpy}
412 copies all of @var{from}, followed by enough null characters to add up
413 to @var{size} characters in all.  This behaviour is rarely useful, but it
414 is implemented to be useful in contexts where this behaviour of the
415 @code{strncpy} is used.  @code{stpncpy} returns a pointer to the
416 @emph{first} written null character.
417
418 This function is not part of ISO or POSIX but was found useful while
419 developing the GNU C Library itself.
420
421 Its behaviour is undefined if the strings overlap.
422 @end deftypefun
423
424 @comment string.h
425 @comment GNU
426 @deftypefn {Macro} {char *} strdupa (const char *@var{s})
427 This function is similar to @code{strdup} but allocates the new string
428 using @code{alloca} instead of @code{malloc} (@pxref{Variable Size
429 Automatic}).  This means of course the returned string has the same
430 limitations as any block of memory allocated using @code{alloca}.
431
432 For obvious reasons @code{strdupa} is implemented only as a macro;
433 you cannot get the address of this function.  Despite this limitation
434 it is a useful function.  The following code shows a situation where
435 using @code{malloc} would be a lot more expensive.
436
437 @smallexample
438 @include strdupa.c.texi
439 @end smallexample
440
441 Please note that calling @code{strtok} using @var{path} directly is
442 invalid.
443
444 This function is only available if GNU CC is used.
445 @end deftypefn
446
447 @comment string.h
448 @comment GNU
449 @deftypefn {Macro} {char *} strndupa (const char *@var{s}, size_t @var{size})
450 This function is similar to @code{strndup} but like @code{strdupa} it
451 allocates the new string using @code{alloca}
452 @pxref{Variable Size Automatic}.  The same advantages and limitations
453 of @code{strdupa} are valid for @code{strndupa}, too.
454
455 This function is implemented only as a macro, just like @code{strdupa}.
456
457 @code{strndupa} is only available if GNU CC is used.
458 @end deftypefn
459
460 @comment string.h
461 @comment ISO
462 @deftypefun {char *} strcat (char *@var{to}, const char *@var{from})
463 The @code{strcat} function is similar to @code{strcpy}, except that the
464 characters from @var{from} are concatenated or appended to the end of
465 @var{to}, instead of overwriting it.  That is, the first character from
466 @var{from} overwrites the null character marking the end of @var{to}.
467
468 An equivalent definition for @code{strcat} would be:
469
470 @smallexample
471 char *
472 strcat (char *to, const char *from)
473 @{
474   strcpy (to + strlen (to), from);
475   return to;
476 @}
477 @end smallexample
478
479 This function has undefined results if the strings overlap.
480 @end deftypefun
481
482 Programmers using the @code{strcat} function (or the following
483 @code{strncat} function for that matter) can easily be recognize as
484 lazy.  In almost all situations the lengths of the participating strings
485 are known.  Or at least, one could know them if one keeps track of the
486 results of the various function calls.  But then it is very inefficient
487 to use @code{strcat}.  A lot of time is wasted finding the end of the
488 destination string so that the actual copying can start.  This is a
489 common example:
490
491 @cindex __va_copy
492 @cindex va_copy
493 @smallexample
494 /* @r{This function concats arbitrary many strings.  The last}
495    @r{parameter must be @code{NULL}.}  */
496 char *
497 concat (const char *str, ...)
498 @{
499   va_list ap, ap2;
500   size_t total = 1;
501   const char *s;
502   char *result;
503
504   va_start (ap, str);
505   /* @r{Actually @code{va_copy}, but this is the name more gcc versions}
506      @r{understand.}  */
507   __va_copy (ap2, ap);
508
509   /* @r{Determine how much space we need.}  */
510   for (s = str; s != NULL; s = va_arg (ap, const char *))
511     total += strlen (s);
512
513   va_end (ap);
514
515   result = (char *) malloc (total);
516   if (result != NULL)
517     @{
518       result[0] = '\0';
519
520       /* @r{Copy the strings.}  */
521       for (s = str; s != NULL; s = va_arg (ap2, const char *))
522         strcat (result, s);
523     @}
524
525   va_end (ap2);
526
527   return result;
528 @}
529 @end smallexample
530
531 This looks quite simple, especially the second loop where the strings
532 are actually copied.  But these innocent lines hide a major performance
533 penalty.  Just imagine that ten strings of 100 bytes each have to be
534 concatenated.  For the second string we search the already stored 100
535 bytes for the end of the string so that we can append the next string.
536 For all strings in total the comparisons necessary to find the end of
537 the intermediate results sums up to 5500!  If we combine the copying
538 with the search for the allocation we can write this function more
539 efficent:
540
541 @smallexample
542 char *
543 concat (const char *str, ...)
544 @{
545   va_list ap;
546   size_t allocated = 100;
547   char *result = (char *) malloc (allocated);
548   char *wp;
549
550   if (allocated != NULL)
551     @{
552       char *newp;
553
554       va_start (ap, atr);
555
556       wp = result;
557       for (s = str; s != NULL; s = va_arg (ap, const char *))
558         @{
559           size_t len = strlen (s);
560
561           /* @r{Resize the allocated memory if necessary.}  */
562           if (wp + len + 1 > result + allocated)
563             @{
564               allocated = (allocated + len) * 2;
565               newp = (char *) realloc (result, allocated);
566               if (newp == NULL)
567                 @{
568                   free (result);
569                   return NULL;
570                 @}
571               wp = newp + (wp - result);
572               result = newp;
573             @}
574
575           wp = mempcpy (wp, s, len);
576         @}
577
578       /* @r{Terminate the result string.}  */
579       *wp++ = '\0';
580
581       /* @r{Resize memory to the optimal size.}  */
582       newp = realloc (result, wp - result);
583       if (newp != NULL)
584         result = newp;
585
586       va_end (ap);
587     @}
588
589   return result;
590 @}
591 @end smallexample
592
593 With a bit more knowledge about the input strings one could fine-tune
594 the memory allocation.  The difference we are pointing to here is that
595 we don't use @code{strcat} anymore.  We always keep track of the length
596 of the current intermediate result so we can safe us the search for the
597 end of the string and use @code{mempcpy}.  Please note that we also
598 don't use @code{stpcpy} which might seem more natural since we handle
599 with strings.  But this is not necessary since we already know the
600 length of the string and therefore can use the faster memory copying
601 function.
602
603 Whenever a programmer feels the need to use @code{strcat} she or he
604 should think twice and look through the program whether the code cannot
605 be rewritten to take advantage of already calculated results.  Again: it
606 is almost always unnecessary to use @code{strcat}.
607
608 @comment string.h
609 @comment ISO
610 @deftypefun {char *} strncat (char *@var{to}, const char *@var{from}, size_t @var{size})
611 This function is like @code{strcat} except that not more than @var{size}
612 characters from @var{from} are appended to the end of @var{to}.  A
613 single null character is also always appended to @var{to}, so the total
614 allocated size of @var{to} must be at least @code{@var{size} + 1} bytes
615 longer than its initial length.
616
617 The @code{strncat} function could be implemented like this:
618
619 @smallexample
620 @group
621 char *
622 strncat (char *to, const char *from, size_t size)
623 @{
624   strncpy (to + strlen (to), from, size);
625   return to;
626 @}
627 @end group
628 @end smallexample
629
630 The behavior of @code{strncat} is undefined if the strings overlap.
631 @end deftypefun
632
633 Here is an example showing the use of @code{strncpy} and @code{strncat}.
634 Notice how, in the call to @code{strncat}, the @var{size} parameter
635 is computed to avoid overflowing the character array @code{buffer}.
636
637 @smallexample
638 @include strncat.c.texi
639 @end smallexample
640
641 @noindent
642 The output produced by this program looks like:
643
644 @smallexample
645 hello
646 hello, wo
647 @end smallexample
648
649 @comment string.h
650 @comment BSD
651 @deftypefun void bcopy (const void *@var{from}, void *@var{to}, size_t @var{size})
652 This is a partially obsolete alternative for @code{memmove}, derived from
653 BSD.  Note that it is not quite equivalent to @code{memmove}, because the
654 arguments are not in the same order and there is no return value.
655 @end deftypefun
656
657 @comment string.h
658 @comment BSD
659 @deftypefun void bzero (void *@var{block}, size_t @var{size})
660 This is a partially obsolete alternative for @code{memset}, derived from
661 BSD.  Note that it is not as general as @code{memset}, because the only
662 value it can store is zero.
663 @end deftypefun
664
665 @node String/Array Comparison
666 @section String/Array Comparison
667 @cindex comparing strings and arrays
668 @cindex string comparison functions
669 @cindex array comparison functions
670 @cindex predicates on strings
671 @cindex predicates on arrays
672
673 You can use the functions in this section to perform comparisons on the
674 contents of strings and arrays.  As well as checking for equality, these
675 functions can also be used as the ordering functions for sorting
676 operations.  @xref{Searching and Sorting}, for an example of this.
677
678 Unlike most comparison operations in C, the string comparison functions
679 return a nonzero value if the strings are @emph{not} equivalent rather
680 than if they are.  The sign of the value indicates the relative ordering
681 of the first characters in the strings that are not equivalent:  a
682 negative value indicates that the first string is ``less'' than the
683 second, while a positive value indicates that the first string is
684 ``greater''.
685
686 The most common use of these functions is to check only for equality.
687 This is canonically done with an expression like @w{@samp{! strcmp (s1, s2)}}.
688
689 All of these functions are declared in the header file @file{string.h}.
690 @pindex string.h
691
692 @comment string.h
693 @comment ISO
694 @deftypefun int memcmp (const void *@var{a1}, const void *@var{a2}, size_t @var{size})
695 The function @code{memcmp} compares the @var{size} bytes of memory
696 beginning at @var{a1} against the @var{size} bytes of memory beginning
697 at @var{a2}.  The value returned has the same sign as the difference
698 between the first differing pair of bytes (interpreted as @code{unsigned
699 char} objects, then promoted to @code{int}).
700
701 If the contents of the two blocks are equal, @code{memcmp} returns
702 @code{0}.
703 @end deftypefun
704
705 On arbitrary arrays, the @code{memcmp} function is mostly useful for
706 testing equality.  It usually isn't meaningful to do byte-wise ordering
707 comparisons on arrays of things other than bytes.  For example, a
708 byte-wise comparison on the bytes that make up floating-point numbers
709 isn't likely to tell you anything about the relationship between the
710 values of the floating-point numbers.
711
712 You should also be careful about using @code{memcmp} to compare objects
713 that can contain ``holes'', such as the padding inserted into structure
714 objects to enforce alignment requirements, extra space at the end of
715 unions, and extra characters at the ends of strings whose length is less
716 than their allocated size.  The contents of these ``holes'' are
717 indeterminate and may cause strange behavior when performing byte-wise
718 comparisons.  For more predictable results, perform an explicit
719 component-wise comparison.
720
721 For example, given a structure type definition like:
722
723 @smallexample
724 struct foo
725   @{
726     unsigned char tag;
727     union
728       @{
729         double f;
730         long i;
731         char *p;
732       @} value;
733   @};
734 @end smallexample
735
736 @noindent
737 you are better off writing a specialized comparison function to compare
738 @code{struct foo} objects instead of comparing them with @code{memcmp}.
739
740 @comment string.h
741 @comment ISO
742 @deftypefun int strcmp (const char *@var{s1}, const char *@var{s2})
743 The @code{strcmp} function compares the string @var{s1} against
744 @var{s2}, returning a value that has the same sign as the difference
745 between the first differing pair of characters (interpreted as
746 @code{unsigned char} objects, then promoted to @code{int}).
747
748 If the two strings are equal, @code{strcmp} returns @code{0}.
749
750 A consequence of the ordering used by @code{strcmp} is that if @var{s1}
751 is an initial substring of @var{s2}, then @var{s1} is considered to be
752 ``less than'' @var{s2}.
753 @end deftypefun
754
755 @comment string.h
756 @comment BSD
757 @deftypefun int strcasecmp (const char *@var{s1}, const char *@var{s2})
758 This function is like @code{strcmp}, except that differences in case are
759 ignored.  How uppercase and lowercase characters are related is
760 determined by the currently selected locale.  In the standard @code{"C"}
761 locale the characters @"A and @"a do not match but in a locale which
762 regards these characters as parts of the alphabet they do match.
763
764 @noindent
765 @code{strcasecmp} is derived from BSD.
766 @end deftypefun
767
768 @comment string.h
769 @comment BSD
770 @deftypefun int strncasecmp (const char *@var{s1}, const char *@var{s2}, size_t @var{n})
771 This function is like @code{strncmp}, except that differences in case
772 are ignored.  Like @code{strcasecmp}, it is locale dependent how
773 uppercase and lowercase characters are related.
774
775 @noindent
776 @code{strncasecmp} is a GNU extension.
777 @end deftypefun
778
779 @comment string.h
780 @comment ISO
781 @deftypefun int strncmp (const char *@var{s1}, const char *@var{s2}, size_t @var{size})
782 This function is the similar to @code{strcmp}, except that no more than
783 @var{size} characters are compared.  In other words, if the two strings are
784 the same in their first @var{size} characters, the return value is zero.
785 @end deftypefun
786
787 Here are some examples showing the use of @code{strcmp} and @code{strncmp}.
788 These examples assume the use of the ASCII character set.  (If some
789 other character set---say, EBCDIC---is used instead, then the glyphs
790 are associated with different numeric codes, and the return values
791 and ordering may differ.)
792
793 @smallexample
794 strcmp ("hello", "hello")
795     @result{} 0    /* @r{These two strings are the same.} */
796 strcmp ("hello", "Hello")
797     @result{} 32   /* @r{Comparisons are case-sensitive.} */
798 strcmp ("hello", "world")
799     @result{} -15  /* @r{The character @code{'h'} comes before @code{'w'}.} */
800 strcmp ("hello", "hello, world")
801     @result{} -44  /* @r{Comparing a null character against a comma.} */
802 strncmp ("hello", "hello, world", 5)
803     @result{} 0    /* @r{The initial 5 characters are the same.} */
804 strncmp ("hello, world", "hello, stupid world!!!", 5)
805     @result{} 0    /* @r{The initial 5 characters are the same.} */
806 @end smallexample
807
808 @comment string.h
809 @comment GNU
810 @deftypefun int strverscmp (const char *@var{s1}, const char *@var{s2})
811 The @code{strverscmp} function compares the string @var{s1} against
812 @var{s2}, considering them as holding indices/version numbers.  Return
813 value follows the same conventions as found in the @code{strverscmp}
814 function.  In fact, if @var{s1} and @var{s2} contain no digits,
815 @code{strverscmp} behaves like @code{strcmp}.
816
817 Basically, we compare strings normally (character by character), until
818 we find a digit in each string - then we enter a special comparison
819 mode, where each sequence of digits is taken as a whole.  If we reach the
820 end of these two parts without noticing a difference, we return to the
821 standard comparison mode.  There are two types of numeric parts:
822 "integral" and "fractional" (those  begin with a '0'). The types
823 of the numeric parts affect the way we sort them:
824
825 @itemize @bullet
826 @item
827 integral/integral: we compare values as you would expect.
828
829 @item
830 fractional/integral: the fractional part is less than the integral one.
831 Again, no surprise.
832
833 @item
834 fractional/fractional: the things become a bit more complex.
835 If the common prefix contains only leading zeroes, the longest part is less
836 than the other one; else the comparison behaves normally.
837 @end itemize
838
839 @smallexample
840 strverscmp ("no digit", "no digit")
841     @result{} 0    /* @r{same behaviour as strcmp.} */
842 strverscmp ("item#99", "item#100")
843     @result{} <0   /* @r{same prefix, but 99 < 100.} */
844 strverscmp ("alpha1", "alpha001")
845     @result{} >0   /* @r{fractional part inferior to integral one.} */
846 strverscmp ("part1_f012", "part1_f01")
847     @result{} >0   /* @r{two fractional parts.} */
848 strverscmp ("foo.009", "foo.0")
849     @result{} <0   /* @r{idem, but with leading zeroes only.} */
850 @end smallexample
851
852 This function is especially useful when dealing with filename sorting,
853 because filenames frequently hold indices/version numbers.
854
855 @code{strverscmp} is a GNU extension.
856 @end deftypefun
857
858 @comment string.h
859 @comment BSD
860 @deftypefun int bcmp (const void *@var{a1}, const void *@var{a2}, size_t @var{size})
861 This is an obsolete alias for @code{memcmp}, derived from BSD.
862 @end deftypefun
863
864 @node Collation Functions
865 @section Collation Functions
866
867 @cindex collating strings
868 @cindex string collation functions
869
870 In some locales, the conventions for lexicographic ordering differ from
871 the strict numeric ordering of character codes.  For example, in Spanish
872 most glyphs with diacritical marks such as accents are not considered
873 distinct letters for the purposes of collation.  On the other hand, the
874 two-character sequence @samp{ll} is treated as a single letter that is
875 collated immediately after @samp{l}.
876
877 You can use the functions @code{strcoll} and @code{strxfrm} (declared in
878 the header file @file{string.h}) to compare strings using a collation
879 ordering appropriate for the current locale.  The locale used by these
880 functions in particular can be specified by setting the locale for the
881 @code{LC_COLLATE} category; see @ref{Locales}.
882 @pindex string.h
883
884 In the standard C locale, the collation sequence for @code{strcoll} is
885 the same as that for @code{strcmp}.
886
887 Effectively, the way these functions work is by applying a mapping to
888 transform the characters in a string to a byte sequence that represents
889 the string's position in the collating sequence of the current locale.
890 Comparing two such byte sequences in a simple fashion is equivalent to
891 comparing the strings with the locale's collating sequence.
892
893 The function @code{strcoll} performs this translation implicitly, in
894 order to do one comparison.  By contrast, @code{strxfrm} performs the
895 mapping explicitly.  If you are making multiple comparisons using the
896 same string or set of strings, it is likely to be more efficient to use
897 @code{strxfrm} to transform all the strings just once, and subsequently
898 compare the transformed strings with @code{strcmp}.
899
900 @comment string.h
901 @comment ISO
902 @deftypefun int strcoll (const char *@var{s1}, const char *@var{s2})
903 The @code{strcoll} function is similar to @code{strcmp} but uses the
904 collating sequence of the current locale for collation (the
905 @code{LC_COLLATE} locale).
906 @end deftypefun
907
908 Here is an example of sorting an array of strings, using @code{strcoll}
909 to compare them.  The actual sort algorithm is not written here; it
910 comes from @code{qsort} (@pxref{Array Sort Function}).  The job of the
911 code shown here is to say how to compare the strings while sorting them.
912 (Later on in this section, we will show a way to do this more
913 efficiently using @code{strxfrm}.)
914
915 @smallexample
916 /* @r{This is the comparison function used with @code{qsort}.} */
917
918 int
919 compare_elements (char **p1, char **p2)
920 @{
921   return strcoll (*p1, *p2);
922 @}
923
924 /* @r{This is the entry point---the function to sort}
925    @r{strings using the locale's collating sequence.} */
926
927 void
928 sort_strings (char **array, int nstrings)
929 @{
930   /* @r{Sort @code{temp_array} by comparing the strings.} */
931   qsort (array, nstrings,
932          sizeof (char *), compare_elements);
933 @}
934 @end smallexample
935
936 @cindex converting string to collation order
937 @comment string.h
938 @comment ISO
939 @deftypefun size_t strxfrm (char *@var{to}, const char *@var{from}, size_t @var{size})
940 The function @code{strxfrm} transforms @var{string} using the collation
941 transformation determined by the locale currently selected for
942 collation, and stores the transformed string in the array @var{to}.  Up
943 to @var{size} characters (including a terminating null character) are
944 stored.
945
946 The behavior is undefined if the strings @var{to} and @var{from}
947 overlap; see @ref{Copying and Concatenation}.
948
949 The return value is the length of the entire transformed string.  This
950 value is not affected by the value of @var{size}, but if it is greater
951 or equal than @var{size}, it means that the transformed string did not
952 entirely fit in the array @var{to}.  In this case, only as much of the
953 string as actually fits was stored.  To get the whole transformed
954 string, call @code{strxfrm} again with a bigger output array.
955
956 The transformed string may be longer than the original string, and it
957 may also be shorter.
958
959 If @var{size} is zero, no characters are stored in @var{to}.  In this
960 case, @code{strxfrm} simply returns the number of characters that would
961 be the length of the transformed string.  This is useful for determining
962 what size string to allocate.  It does not matter what @var{to} is if
963 @var{size} is zero; @var{to} may even be a null pointer.
964 @end deftypefun
965
966 Here is an example of how you can use @code{strxfrm} when
967 you plan to do many comparisons.  It does the same thing as the previous
968 example, but much faster, because it has to transform each string only
969 once, no matter how many times it is compared with other strings.  Even
970 the time needed to allocate and free storage is much less than the time
971 we save, when there are many strings.
972
973 @smallexample
974 struct sorter @{ char *input; char *transformed; @};
975
976 /* @r{This is the comparison function used with @code{qsort}}
977    @r{to sort an array of @code{struct sorter}.} */
978
979 int
980 compare_elements (struct sorter *p1, struct sorter *p2)
981 @{
982   return strcmp (p1->transformed, p2->transformed);
983 @}
984
985 /* @r{This is the entry point---the function to sort}
986    @r{strings using the locale's collating sequence.} */
987
988 void
989 sort_strings_fast (char **array, int nstrings)
990 @{
991   struct sorter temp_array[nstrings];
992   int i;
993
994   /* @r{Set up @code{temp_array}.  Each element contains}
995      @r{one input string and its transformed string.} */
996   for (i = 0; i < nstrings; i++)
997     @{
998       size_t length = strlen (array[i]) * 2;
999       char *transformed;
1000       size_t transformed_length;
1001
1002       temp_array[i].input = array[i];
1003
1004       /* @r{First try a buffer perhaps big enough.}  */
1005       transformed = (char *) xmalloc (length);
1006
1007       /* @r{Transform @code{array[i]}.}  */
1008       transformed_length = strxfrm (transformed, array[i], length);
1009
1010       /* @r{If the buffer was not large enough, resize it}
1011          @r{and try again.}  */
1012       if (transformed_length >= length)
1013         @{
1014           /* @r{Allocate the needed space. +1 for terminating}
1015              @r{@code{NUL} character.}  */
1016           transformed = (char *) xrealloc (transformed,
1017                                            transformed_length + 1);
1018
1019           /* @r{The return value is not interesting because we know}
1020              @r{how long the transformed string is.}  */
1021           (void) strxfrm (transformed, array[i],
1022                           transformed_length + 1);
1023         @}
1024
1025       temp_array[i].transformed = transformed;
1026     @}
1027
1028   /* @r{Sort @code{temp_array} by comparing transformed strings.} */
1029   qsort (temp_array, sizeof (struct sorter),
1030          nstrings, compare_elements);
1031
1032   /* @r{Put the elements back in the permanent array}
1033      @r{in their sorted order.} */
1034   for (i = 0; i < nstrings; i++)
1035     array[i] = temp_array[i].input;
1036
1037   /* @r{Free the strings we allocated.} */
1038   for (i = 0; i < nstrings; i++)
1039     free (temp_array[i].transformed);
1040 @}
1041 @end smallexample
1042
1043 @strong{Compatibility Note:}  The string collation functions are a new
1044 feature of @w{ISO C 89}.  Older C dialects have no equivalent feature.
1045
1046 @node Search Functions
1047 @section Search Functions
1048
1049 This section describes library functions which perform various kinds
1050 of searching operations on strings and arrays.  These functions are
1051 declared in the header file @file{string.h}.
1052 @pindex string.h
1053 @cindex search functions (for strings)
1054 @cindex string search functions
1055
1056 @comment string.h
1057 @comment ISO
1058 @deftypefun {void *} memchr (const void *@var{block}, int @var{c}, size_t @var{size})
1059 This function finds the first occurrence of the byte @var{c} (converted
1060 to an @code{unsigned char}) in the initial @var{size} bytes of the
1061 object beginning at @var{block}.  The return value is a pointer to the
1062 located byte, or a null pointer if no match was found.
1063 @end deftypefun
1064
1065 @comment string.h
1066 @comment GNU
1067 @deftypefun {void *} memrchr (const void *@var{block}, int @var{c}, size_t @var{size})
1068 The function @code{memrchr} is like @code{memchr}, except that it searches
1069 backwards from the end of the block defined by @var{block} and @var{size}
1070 (instead of forwards from the front).
1071 @end deftypefun
1072
1073 @comment string.h
1074 @comment ISO
1075 @deftypefun {char *} strchr (const char *@var{string}, int @var{c})
1076 The @code{strchr} function finds the first occurrence of the character
1077 @var{c} (converted to a @code{char}) in the null-terminated string
1078 beginning at @var{string}.  The return value is a pointer to the located
1079 character, or a null pointer if no match was found.
1080
1081 For example,
1082 @smallexample
1083 strchr ("hello, world", 'l')
1084     @result{} "llo, world"
1085 strchr ("hello, world", '?')
1086     @result{} NULL
1087 @end smallexample
1088
1089 The terminating null character is considered to be part of the string,
1090 so you can use this function get a pointer to the end of a string by
1091 specifying a null character as the value of the @var{c} argument.
1092 @end deftypefun
1093
1094 @comment string.h
1095 @comment BSD
1096 @deftypefun {char *} index (const char *@var{string}, int @var{c})
1097 @code{index} is another name for @code{strchr}; they are exactly the same.
1098 New code should always use @code{strchr} since this name is defined in
1099 @w{ISO C} while @code{index} is a BSD invention which never was available
1100 on @w{System V} derived systems.
1101 @end deftypefun
1102
1103 One useful, but unusual, use of the @code{strchr} or @code{index}
1104 function is when one wants to have a pointer pointing to the NUL byte
1105 terminating a string.  This is often written in this way:
1106
1107 @smallexample
1108   s += strlen (s);
1109 @end smallexample
1110
1111 @noindent
1112 This is almost optimal but the addition operation duplicated a bit of
1113 the work already done in the @code{strlen} function.  A better solution
1114 is this:
1115
1116 @smallexample
1117   s = strchr (s, '\0');
1118 @end smallexample
1119
1120 There is no restriction on the second parameter of @code{strchr} so it
1121 could very well also be the NUL character.  Those readers thinking very
1122 hard about this might now point out that the @code{strchr} function is
1123 more expensive than the @code{strlen} function since we have two abort
1124 criteria.  This is right.  But when using the GNU C library is used this
1125 @code{strchr} call gets optimized in a special way so that this version
1126 actually is faster.
1127
1128 @comment string.h
1129 @comment ISO
1130 @deftypefun {char *} strrchr (const char *@var{string}, int @var{c})
1131 The function @code{strrchr} is like @code{strchr}, except that it searches
1132 backwards from the end of the string @var{string} (instead of forwards
1133 from the front).
1134
1135 For example,
1136 @smallexample
1137 strrchr ("hello, world", 'l')
1138     @result{} "ld"
1139 @end smallexample
1140 @end deftypefun
1141
1142 @comment string.h
1143 @comment BSD
1144 @deftypefun {char *} rindex (const char *@var{string}, int @var{c})
1145 @code{rindex} is another name for @code{strrchr}; they are exactly the same.
1146 New code should always use @code{strrchr} since this name is defined in
1147 @w{ISO C} while @code{rindex} is a BSD invention which never was available
1148 on @w{System V} derived systems.
1149 @end deftypefun
1150
1151 @comment string.h
1152 @comment ISO
1153 @deftypefun {char *} strstr (const char *@var{haystack}, const char *@var{needle})
1154 This is like @code{strchr}, except that it searches @var{haystack} for a
1155 substring @var{needle} rather than just a single character.  It
1156 returns a pointer into the string @var{haystack} that is the first
1157 character of the substring, or a null pointer if no match was found.  If
1158 @var{needle} is an empty string, the function returns @var{haystack}.
1159
1160 For example,
1161 @smallexample
1162 strstr ("hello, world", "l")
1163     @result{} "llo, world"
1164 strstr ("hello, world", "wo")
1165     @result{} "world"
1166 @end smallexample
1167 @end deftypefun
1168
1169
1170 @comment string.h
1171 @comment GNU
1172 @deftypefun {void *} memmem (const void *@var{haystack}, size_t @var{haystack-len},@*const void *@var{needle}, size_t @var{needle-len})
1173 This is like @code{strstr}, but @var{needle} and @var{haystack} are byte
1174 arrays rather than null-terminated strings.  @var{needle-len} is the
1175 length of @var{needle} and @var{haystack-len} is the length of
1176 @var{haystack}.@refill
1177
1178 This function is a GNU extension.
1179 @end deftypefun
1180
1181 @comment string.h
1182 @comment ISO
1183 @deftypefun size_t strspn (const char *@var{string}, const char *@var{skipset})
1184 The @code{strspn} (``string span'') function returns the length of the
1185 initial substring of @var{string} that consists entirely of characters that
1186 are members of the set specified by the string @var{skipset}.  The order
1187 of the characters in @var{skipset} is not important.
1188
1189 For example,
1190 @smallexample
1191 strspn ("hello, world", "abcdefghijklmnopqrstuvwxyz")
1192     @result{} 5
1193 @end smallexample
1194 @end deftypefun
1195
1196 @comment string.h
1197 @comment ISO
1198 @deftypefun size_t strcspn (const char *@var{string}, const char *@var{stopset})
1199 The @code{strcspn} (``string complement span'') function returns the length
1200 of the initial substring of @var{string} that consists entirely of characters
1201 that are @emph{not} members of the set specified by the string @var{stopset}.
1202 (In other words, it returns the offset of the first character in @var{string}
1203 that is a member of the set @var{stopset}.)
1204
1205 For example,
1206 @smallexample
1207 strcspn ("hello, world", " \t\n,.;!?")
1208     @result{} 5
1209 @end smallexample
1210 @end deftypefun
1211
1212 @comment string.h
1213 @comment ISO
1214 @deftypefun {char *} strpbrk (const char *@var{string}, const char *@var{stopset})
1215 The @code{strpbrk} (``string pointer break'') function is related to
1216 @code{strcspn}, except that it returns a pointer to the first character
1217 in @var{string} that is a member of the set @var{stopset} instead of the
1218 length of the initial substring.  It returns a null pointer if no such
1219 character from @var{stopset} is found.
1220
1221 @c @group  Invalid outside the example.
1222 For example,
1223
1224 @smallexample
1225 strpbrk ("hello, world", " \t\n,.;!?")
1226     @result{} ", world"
1227 @end smallexample
1228 @c @end group
1229 @end deftypefun
1230
1231 @node Finding Tokens in a String
1232 @section Finding Tokens in a String
1233
1234 @cindex tokenizing strings
1235 @cindex breaking a string into tokens
1236 @cindex parsing tokens from a string
1237 It's fairly common for programs to have a need to do some simple kinds
1238 of lexical analysis and parsing, such as splitting a command string up
1239 into tokens.  You can do this with the @code{strtok} function, declared
1240 in the header file @file{string.h}.
1241 @pindex string.h
1242
1243 @comment string.h
1244 @comment ISO
1245 @deftypefun {char *} strtok (char *@var{newstring}, const char *@var{delimiters})
1246 A string can be split into tokens by making a series of calls to the
1247 function @code{strtok}.
1248
1249 The string to be split up is passed as the @var{newstring} argument on
1250 the first call only.  The @code{strtok} function uses this to set up
1251 some internal state information.  Subsequent calls to get additional
1252 tokens from the same string are indicated by passing a null pointer as
1253 the @var{newstring} argument.  Calling @code{strtok} with another
1254 non-null @var{newstring} argument reinitializes the state information.
1255 It is guaranteed that no other library function ever calls @code{strtok}
1256 behind your back (which would mess up this internal state information).
1257
1258 The @var{delimiters} argument is a string that specifies a set of delimiters
1259 that may surround the token being extracted.  All the initial characters
1260 that are members of this set are discarded.  The first character that is
1261 @emph{not} a member of this set of delimiters marks the beginning of the
1262 next token.  The end of the token is found by looking for the next
1263 character that is a member of the delimiter set.  This character in the
1264 original string @var{newstring} is overwritten by a null character, and the
1265 pointer to the beginning of the token in @var{newstring} is returned.
1266
1267 On the next call to @code{strtok}, the searching begins at the next
1268 character beyond the one that marked the end of the previous token.
1269 Note that the set of delimiters @var{delimiters} do not have to be the
1270 same on every call in a series of calls to @code{strtok}.
1271
1272 If the end of the string @var{newstring} is reached, or if the remainder of
1273 string consists only of delimiter characters, @code{strtok} returns
1274 a null pointer.
1275 @end deftypefun
1276
1277 @strong{Warning:} Since @code{strtok} alters the string it is parsing,
1278 you should always copy the string to a temporary buffer before parsing
1279 it with @code{strtok}.  If you allow @code{strtok} to modify a string
1280 that came from another part of your program, you are asking for trouble;
1281 that string might be used for other purposes after @code{strtok} has
1282 modified it, and it would not have the expected value.
1283
1284 The string that you are operating on might even be a constant.  Then
1285 when @code{strtok} tries to modify it, your program will get a fatal
1286 signal for writing in read-only memory.  @xref{Program Error Signals}.
1287
1288 This is a special case of a general principle: if a part of a program
1289 does not have as its purpose the modification of a certain data
1290 structure, then it is error-prone to modify the data structure
1291 temporarily.
1292
1293 The function @code{strtok} is not reentrant.  @xref{Nonreentrancy}, for
1294 a discussion of where and why reentrancy is important.
1295
1296 Here is a simple example showing the use of @code{strtok}.
1297
1298 @comment Yes, this example has been tested.
1299 @smallexample
1300 #include <string.h>
1301 #include <stddef.h>
1302
1303 @dots{}
1304
1305 const char string[] = "words separated by spaces -- and, punctuation!";
1306 const char delimiters[] = " .,;:!-";
1307 char *token, *cp;
1308
1309 @dots{}
1310
1311 cp = strdupa (string);                /* Make writable copy.  */
1312 token = strtok (cp, delimiters);      /* token => "words" */
1313 token = strtok (NULL, delimiters);    /* token => "separated" */
1314 token = strtok (NULL, delimiters);    /* token => "by" */
1315 token = strtok (NULL, delimiters);    /* token => "spaces" */
1316 token = strtok (NULL, delimiters);    /* token => "and" */
1317 token = strtok (NULL, delimiters);    /* token => "punctuation" */
1318 token = strtok (NULL, delimiters);    /* token => NULL */
1319 @end smallexample
1320
1321 The GNU C library contains two more functions for tokenizing a string
1322 which overcome the limitation of non-reentrancy.
1323
1324 @comment string.h
1325 @comment POSIX
1326 @deftypefun {char *} strtok_r (char *@var{newstring}, const char *@var{delimiters}, char **@var{save_ptr})
1327 Just like @code{strtok}, this function splits the string into several
1328 tokens which can be accessed by successive calls to @code{strtok_r}.
1329 The difference is that the information about the next token is stored in
1330 the space pointed to by the third argument, @var{save_ptr}, which is a
1331 pointer to a string pointer.  Calling @code{strtok_r} with a null
1332 pointer for @var{newstring} and leaving @var{save_ptr} between the calls
1333 unchanged does the job without hindering reentrancy.
1334
1335 This function is defined in POSIX-1 and can be found on many systems
1336 which support multi-threading.
1337 @end deftypefun
1338
1339 @comment string.h
1340 @comment BSD
1341 @deftypefun {char *} strsep (char **@var{string_ptr}, const char *@var{delimiter})
1342 This function has a similar functionality as @code{strtok_r} with the
1343 @var{newstring} argument replaced by the @var{save_ptr} argument.  The
1344 initialization of the moving pointer has to be done by the user.
1345 Successive calls to @code{strsep} move the pointer along the tokens
1346 separated by @var{delimiter}, returning the address of the next token
1347 and updating @var{string_ptr} to point to the beginning of the next
1348 token.
1349
1350 One difference between @code{strsep} and @code{strtok_r} is that if the
1351 input string contains more than one character from @var{delimiter} in a
1352 row @code{strsep} returns an empty string for each pair of characters
1353 from @var{delimiter}.  This means that a program normally should test
1354 for @code{strsep} returning an empty string before processing it.
1355
1356 This function was introduced in 4.3BSD and therefore is widely available.
1357 @end deftypefun
1358
1359 Here is how the above example looks like when @code{strsep} is used.
1360
1361 @comment Yes, this example has been tested.
1362 @smallexample
1363 #include <string.h>
1364 #include <stddef.h>
1365
1366 @dots{}
1367
1368 const char string[] = "words separated by spaces -- and, punctuation!";
1369 const char delimiters[] = " .,;:!-";
1370 char *running;
1371 char *token;
1372
1373 @dots{}
1374
1375 running = strdupa (string);
1376 token = strsep (&running, delimiters);    /* token => "words" */
1377 token = strsep (&running, delimiters);    /* token => "separated" */
1378 token = strsep (&running, delimiters);    /* token => "by" */
1379 token = strsep (&running, delimiters);    /* token => "spaces" */
1380 token = strsep (&running, delimiters);    /* token => "" */
1381 token = strsep (&running, delimiters);    /* token => "" */
1382 token = strsep (&running, delimiters);    /* token => "" */
1383 token = strsep (&running, delimiters);    /* token => "and" */
1384 token = strsep (&running, delimiters);    /* token => "" */
1385 token = strsep (&running, delimiters);    /* token => "punctuation" */
1386 token = strsep (&running, delimiters);    /* token => "" */
1387 token = strsep (&running, delimiters);    /* token => NULL */
1388 @end smallexample
1389
1390 @node Encode Binary Data
1391 @section Encode Binary Data
1392
1393 To store or transfer binary data in environments which only support text
1394 one has to encode the binary data by mapping the input bytes to
1395 characters in the range allowed for storing or transfering.  SVID
1396 systems (and nowadays XPG compliant systems) provide minimal support for
1397 this task.
1398
1399 @comment stdlib.h
1400 @comment XPG
1401 @deftypefun {char *} l64a (long int @var{n})
1402 This function encodes a 32-bit input value using characters from the
1403 basic character set.  It returns a pointer to a 6 character buffer which
1404 contains an encoded version of @var{n}.  To encode a series of bytes the
1405 user must copy the returned string to a destination buffer.  It returns
1406 the empty string if @var{n} is zero, which is somewhat bizarre but
1407 mandated by the standard.@*
1408 @strong{Warning:} Since a static buffer is used this function should not
1409 be used in multi-threaded programs.  There is no thread-safe alternative
1410 to this function in the C library.@*
1411 @strong{Compatibility Note:} The XPG standard states that the return
1412 value of @code{l64a} is undefined if @var{n} is negative.  In the GNU
1413 implementation, @code{l64a} treats its argument as unsigned, so it will
1414 return a sensible encoding for any nonzero @var{n}; however, portable
1415 programs should not rely on this.
1416
1417 To encode a large buffer @code{l64a} must be called in a loop, once for
1418 each 32-bit word of the buffer.  For example, one could do something
1419 like this:
1420
1421 @smallexample
1422 char *
1423 encode (const void *buf, size_t len)
1424 @{
1425   /* @r{We know in advance how long the buffer has to be.} */
1426   unsigned char *in = (unsigned char *) buf;
1427   char *out = malloc (6 + ((len + 3) / 4) * 6 + 1);
1428   char *cp = out;
1429
1430   /* @r{Encode the length.} */
1431   /* @r{Using `htonl' is necessary so that the data can be}
1432      @r{decoded even on machines with different byte order.} */
1433
1434   cp = mempcpy (cp, l64a (htonl (len)), 6);
1435
1436   while (len > 3)
1437     @{
1438       unsigned long int n = *in++;
1439       n = (n << 8) | *in++;
1440       n = (n << 8) | *in++;
1441       n = (n << 8) | *in++;
1442       len -= 4;
1443       if (n)
1444         cp = mempcpy (cp, l64a (htonl (n)), 6);
1445       else
1446             /* @r{`l64a' returns the empty string for n==0, so we }
1447                @r{must generate its encoding (}"......"@r{) by hand.} */
1448         cp = stpcpy (cp, "......");
1449     @}
1450   if (len > 0)
1451     @{
1452       unsigned long int n = *in++;
1453       if (--len > 0)
1454         @{
1455           n = (n << 8) | *in++;
1456           if (--len > 0)
1457             n = (n << 8) | *in;
1458         @}
1459       memcpy (cp, l64a (htonl (n)), 6);
1460       cp += 6;
1461     @}
1462   *cp = '\0';
1463   return out;
1464 @}
1465 @end smallexample
1466
1467 It is strange that the library does not provide the complete
1468 functionality needed but so be it.
1469
1470 @end deftypefun
1471
1472 To decode data produced with @code{l64a} the following function should be
1473 used.
1474
1475 @comment stdlib.h
1476 @comment XPG
1477 @deftypefun {long int} a64l (const char *@var{string})
1478 The parameter @var{string} should contain a string which was produced by
1479 a call to @code{l64a}.  The function processes at least 6 characters of
1480 this string, and decodes the characters it finds according to the table
1481 below.  It stops decoding when it finds a character not in the table,
1482 rather like @code{atoi}; if you have a buffer which has been broken into
1483 lines, you must be careful to skip over the end-of-line characters.
1484
1485 The decoded number is returned as a @code{long int} value.
1486 @end deftypefun
1487
1488 The @code{l64a} and @code{a64l} functions use a base 64 encoding, in
1489 which each character of an encoded string represents six bits of an
1490 input word.  These symbols are used for the base 64 digits:
1491
1492 @multitable {xxxxx} {xxx} {xxx} {xxx} {xxx} {xxx} {xxx} {xxx} {xxx}
1493 @item              @tab 0 @tab 1 @tab 2 @tab 3 @tab 4 @tab 5 @tab 6 @tab 7
1494 @item       0      @tab @code{.} @tab @code{/} @tab @code{0} @tab @code{1}
1495                    @tab @code{2} @tab @code{3} @tab @code{4} @tab @code{5}
1496 @item       8      @tab @code{6} @tab @code{7} @tab @code{8} @tab @code{9}
1497                    @tab @code{A} @tab @code{B} @tab @code{C} @tab @code{D}
1498 @item       16     @tab @code{E} @tab @code{F} @tab @code{G} @tab @code{H}
1499                    @tab @code{I} @tab @code{J} @tab @code{K} @tab @code{L}
1500 @item       24     @tab @code{M} @tab @code{N} @tab @code{O} @tab @code{P}
1501                    @tab @code{Q} @tab @code{R} @tab @code{S} @tab @code{T}
1502 @item       32     @tab @code{U} @tab @code{V} @tab @code{W} @tab @code{X}
1503                    @tab @code{Y} @tab @code{Z} @tab @code{a} @tab @code{b}
1504 @item       40     @tab @code{c} @tab @code{d} @tab @code{e} @tab @code{f}
1505                    @tab @code{g} @tab @code{h} @tab @code{i} @tab @code{j}
1506 @item       48     @tab @code{k} @tab @code{l} @tab @code{m} @tab @code{n}
1507                    @tab @code{o} @tab @code{p} @tab @code{q} @tab @code{r}
1508 @item       56     @tab @code{s} @tab @code{t} @tab @code{u} @tab @code{v}
1509                    @tab @code{w} @tab @code{x} @tab @code{y} @tab @code{z}
1510 @end multitable
1511
1512 This encoding scheme is not standard.  There are some other encoding
1513 methods which are much more widely used (UU encoding, MIME encoding).
1514 Generally, it is better to use one of these encodings.
1515
1516 @node Argz and Envz Vectors
1517 @section Argz and Envz Vectors
1518
1519 @cindex argz vectors (string vectors)
1520 @cindex string vectors, null-character separated
1521 @cindex argument vectors, null-character separated
1522 @dfn{argz vectors} are vectors of strings in a contiguous block of
1523 memory, each element separated from its neighbors by null-characters
1524 (@code{'\0'}).
1525
1526 @cindex envz vectors (environment vectors)
1527 @cindex environment vectors, null-character separated
1528 @dfn{Envz vectors} are an extension of argz vectors where each element is a
1529 name-value pair, separated by a @code{'='} character (as in a Unix
1530 environment).
1531
1532 @menu
1533 * Argz Functions::              Operations on argz vectors.
1534 * Envz Functions::              Additional operations on environment vectors.
1535 @end menu
1536
1537 @node Argz Functions, Envz Functions, , Argz and Envz Vectors
1538 @subsection Argz Functions
1539
1540 Each argz vector is represented by a pointer to the first element, of
1541 type @code{char *}, and a size, of type @code{size_t}, both of which can
1542 be initialized to @code{0} to represent an empty argz vector.  All argz
1543 functions accept either a pointer and a size argument, or pointers to
1544 them, if they will be modified.
1545
1546 The argz functions use @code{malloc}/@code{realloc} to allocate/grow
1547 argz vectors, and so any argz vector creating using these functions may
1548 be freed by using @code{free}; conversely, any argz function that may
1549 grow a string expects that string to have been allocated using
1550 @code{malloc} (those argz functions that only examine their arguments or
1551 modify them in place will work on any sort of memory).
1552 @xref{Unconstrained Allocation}.
1553
1554 All argz functions that do memory allocation have a return type of
1555 @code{error_t}, and return @code{0} for success, and @code{ENOMEM} if an
1556 allocation error occurs.
1557
1558 @pindex argz.h
1559 These functions are declared in the standard include file @file{argz.h}.
1560
1561 @comment argz.h
1562 @comment GNU
1563 @deftypefun {error_t} argz_create (char *const @var{argv}[], char **@var{argz}, size_t *@var{argz_len})
1564 The @code{argz_create} function converts the Unix-style argument vector
1565 @var{argv} (a vector of pointers to normal C strings, terminated by
1566 @code{(char *)0}; @pxref{Program Arguments}) into an argz vector with
1567 the same elements, which is returned in @var{argz} and @var{argz_len}.
1568 @end deftypefun
1569
1570 @comment argz.h
1571 @comment GNU
1572 @deftypefun {error_t} argz_create_sep (const char *@var{string}, int @var{sep}, char **@var{argz}, size_t *@var{argz_len})
1573 The @code{argz_create_sep} function converts the null-terminated string
1574 @var{string} into an argz vector (returned in @var{argz} and
1575 @var{argz_len}) by splitting it into elements at every occurance of the
1576 character @var{sep}.
1577 @end deftypefun
1578
1579 @comment argz.h
1580 @comment GNU
1581 @deftypefun {size_t} argz_count (const char *@var{argz}, size_t @var{arg_len})
1582 Returns the number of elements in the argz vector @var{argz} and
1583 @var{argz_len}.
1584 @end deftypefun
1585
1586 @comment argz.h
1587 @comment GNU
1588 @deftypefun {void} argz_extract (char *@var{argz}, size_t @var{argz_len}, char **@var{argv})
1589 The @code{argz_extract} function converts the argz vector @var{argz} and
1590 @var{argz_len} into a Unix-style argument vector stored in @var{argv},
1591 by putting pointers to every element in @var{argz} into successive
1592 positions in @var{argv}, followed by a terminator of @code{0}.
1593 @var{Argv} must be pre-allocated with enough space to hold all the
1594 elements in @var{argz} plus the terminating @code{(char *)0}
1595 (@code{(argz_count (@var{argz}, @var{argz_len}) + 1) * sizeof (char *)}
1596 bytes should be enough).  Note that the string pointers stored into
1597 @var{argv} point into @var{argz}---they are not copies---and so
1598 @var{argz} must be copied if it will be changed while @var{argv} is
1599 still active.  This function is useful for passing the elements in
1600 @var{argz} to an exec function (@pxref{Executing a File}).
1601 @end deftypefun
1602
1603 @comment argz.h
1604 @comment GNU
1605 @deftypefun {void} argz_stringify (char *@var{argz}, size_t @var{len}, int @var{sep})
1606 The @code{argz_stringify} converts @var{argz} into a normal string with
1607 the elements separated by the character @var{sep}, by replacing each
1608 @code{'\0'} inside @var{argz} (except the last one, which terminates the
1609 string) with @var{sep}.  This is handy for printing @var{argz} in a
1610 readable manner.
1611 @end deftypefun
1612
1613 @comment argz.h
1614 @comment GNU
1615 @deftypefun {error_t} argz_add (char **@var{argz}, size_t *@var{argz_len}, const char *@var{str})
1616 The @code{argz_add} function adds the string @var{str} to the end of the
1617 argz vector @code{*@var{argz}}, and updates @code{*@var{argz}} and
1618 @code{*@var{argz_len}} accordingly.
1619 @end deftypefun
1620
1621 @comment argz.h
1622 @comment GNU
1623 @deftypefun {error_t} argz_add_sep (char **@var{argz}, size_t *@var{argz_len}, const char *@var{str}, int @var{delim})
1624 The @code{argz_add_sep} function is similar to @code{argz_add}, but
1625 @var{str} is split into separate elements in the result at occurances of
1626 the character @var{delim}.  This is useful, for instance, for
1627 adding the components of a Unix search path to an argz vector, by using
1628 a value of @code{':'} for @var{delim}.
1629 @end deftypefun
1630
1631 @comment argz.h
1632 @comment GNU
1633 @deftypefun {error_t} argz_append (char **@var{argz}, size_t *@var{argz_len}, const char *@var{buf}, size_t @var{buf_len})
1634 The @code{argz_append} function appends @var{buf_len} bytes starting at
1635 @var{buf} to the argz vector @code{*@var{argz}}, reallocating
1636 @code{*@var{argz}} to accommodate it, and adding @var{buf_len} to
1637 @code{*@var{argz_len}}.
1638 @end deftypefun
1639
1640 @comment argz.h
1641 @comment GNU
1642 @deftypefun {error_t} argz_delete (char **@var{argz}, size_t *@var{argz_len}, char *@var{entry})
1643 If @var{entry} points to the beginning of one of the elements in the
1644 argz vector @code{*@var{argz}}, the @code{argz_delete} function will
1645 remove this entry and reallocate @code{*@var{argz}}, modifying
1646 @code{*@var{argz}} and @code{*@var{argz_len}} accordingly.  Note that as
1647 destructive argz functions usually reallocate their argz argument,
1648 pointers into argz vectors such as @var{entry} will then become invalid.
1649 @end deftypefun
1650
1651 @comment argz.h
1652 @comment GNU
1653 @deftypefun {error_t} argz_insert (char **@var{argz}, size_t *@var{argz_len}, char *@var{before}, const char *@var{entry})
1654 The @code{argz_insert} function inserts the string @var{entry} into the
1655 argz vector @code{*@var{argz}} at a point just before the existing
1656 element pointed to by @var{before}, reallocating @code{*@var{argz}} and
1657 updating @code{*@var{argz}} and @code{*@var{argz_len}}.  If @var{before}
1658 is @code{0}, @var{entry} is added to the end instead (as if by
1659 @code{argz_add}).  Since the first element is in fact the same as
1660 @code{*@var{argz}}, passing in @code{*@var{argz}} as the value of
1661 @var{before} will result in @var{entry} being inserted at the beginning.
1662 @end deftypefun
1663
1664 @comment argz.h
1665 @comment GNU
1666 @deftypefun {char *} argz_next (char *@var{argz}, size_t @var{argz_len}, const char *@var{entry})
1667 The @code{argz_next} function provides a convenient way of iterating
1668 over the elements in the argz vector @var{argz}.  It returns a pointer
1669 to the next element in @var{argz} after the element @var{entry}, or
1670 @code{0} if there are no elements following @var{entry}.  If @var{entry}
1671 is @code{0}, the first element of @var{argz} is returned.
1672
1673 This behavior suggests two styles of iteration:
1674
1675 @smallexample
1676     char *entry = 0;
1677     while ((entry = argz_next (@var{argz}, @var{argz_len}, entry)))
1678       @var{action};
1679 @end smallexample
1680
1681 (the double parentheses are necessary to make some C compilers shut up
1682 about what they consider a questionable @code{while}-test) and:
1683
1684 @smallexample
1685     char *entry;
1686     for (entry = @var{argz};
1687          entry;
1688          entry = argz_next (@var{argz}, @var{argz_len}, entry))
1689       @var{action};
1690 @end smallexample
1691
1692 Note that the latter depends on @var{argz} having a value of @code{0} if
1693 it is empty (rather than a pointer to an empty block of memory); this
1694 invariant is maintained for argz vectors created by the functions here.
1695 @end deftypefun
1696
1697 @comment argz.h
1698 @comment GNU
1699 @deftypefun error_t argz_replace (@w{char **@var{argz}, size_t *@var{argz_len}}, @w{const char *@var{str}, const char *@var{with}}, @w{unsigned *@var{replace_count}})
1700 Replace any occurances of the string @var{str} in @var{argz} with
1701 @var{with}, reallocating @var{argz} as necessary.  If
1702 @var{replace_count} is non-zero, @code{*@var{replace_count}} will be
1703 incremented by number of replacements performed.
1704 @end deftypefun
1705
1706 @node Envz Functions, , Argz Functions, Argz and Envz Vectors
1707 @subsection Envz Functions
1708
1709 Envz vectors are just argz vectors with additional constraints on the form
1710 of each element; as such, argz functions can also be used on them, where it
1711 makes sense.
1712
1713 Each element in an envz vector is a name-value pair, separated by a @code{'='}
1714 character; if multiple @code{'='} characters are present in an element, those
1715 after the first are considered part of the value, and treated like all other
1716 non-@code{'\0'} characters.
1717
1718 If @emph{no} @code{'='} characters are present in an element, that element is
1719 considered the name of a ``null'' entry, as distinct from an entry with an
1720 empty value: @code{envz_get} will return @code{0} if given the name of null
1721 entry, whereas an entry with an empty value would result in a value of
1722 @code{""}; @code{envz_entry} will still find such entries, however.  Null
1723 entries can be removed with @code{envz_strip} function.
1724
1725 As with argz functions, envz functions that may allocate memory (and thus
1726 fail) have a return type of @code{error_t}, and return either @code{0} or
1727 @code{ENOMEM}.
1728
1729 @pindex envz.h
1730 These functions are declared in the standard include file @file{envz.h}.
1731
1732 @comment envz.h
1733 @comment GNU
1734 @deftypefun {char *} envz_entry (const char *@var{envz}, size_t @var{envz_len}, const char *@var{name})
1735 The @code{envz_entry} function finds the entry in @var{envz} with the name
1736 @var{name}, and returns a pointer to the whole entry---that is, the argz
1737 element which begins with @var{name} followed by a @code{'='} character.  If
1738 there is no entry with that name, @code{0} is returned.
1739 @end deftypefun
1740
1741 @comment envz.h
1742 @comment GNU
1743 @deftypefun {char *} envz_get (const char *@var{envz}, size_t @var{envz_len}, const char *@var{name})
1744 The @code{envz_get} function finds the entry in @var{envz} with the name
1745 @var{name} (like @code{envz_entry}), and returns a pointer to the value
1746 portion of that entry (following the @code{'='}).  If there is no entry with
1747 that name (or only a null entry), @code{0} is returned.
1748 @end deftypefun
1749
1750 @comment envz.h
1751 @comment GNU
1752 @deftypefun {error_t} envz_add (char **@var{envz}, size_t *@var{envz_len}, const char *@var{name}, const char *@var{value})
1753 The @code{envz_add} function adds an entry to @code{*@var{envz}}
1754 (updating @code{*@var{envz}} and @code{*@var{envz_len}}) with the name
1755 @var{name}, and value @var{value}.  If an entry with the same name
1756 already exists in @var{envz}, it is removed first.  If @var{value} is
1757 @code{0}, then the new entry will the special null type of entry
1758 (mentioned above).
1759 @end deftypefun
1760
1761 @comment envz.h
1762 @comment GNU
1763 @deftypefun {error_t} envz_merge (char **@var{envz}, size_t *@var{envz_len}, const char *@var{envz2}, size_t @var{envz2_len}, int @var{override})
1764 The @code{envz_merge} function adds each entry in @var{envz2} to @var{envz},
1765 as if with @code{envz_add}, updating @code{*@var{envz}} and
1766 @code{*@var{envz_len}}.  If @var{override} is true, then values in @var{envz2}
1767 will supersede those with the same name in @var{envz}, otherwise not.
1768
1769 Null entries are treated just like other entries in this respect, so a null
1770 entry in @var{envz} can prevent an entry of the same name in @var{envz2} from
1771 being added to @var{envz}, if @var{override} is false.
1772 @end deftypefun
1773
1774 @comment envz.h
1775 @comment GNU
1776 @deftypefun {void} envz_strip (char **@var{envz}, size_t *@var{envz_len})
1777 The @code{envz_strip} function removes any null entries from @var{envz},
1778 updating @code{*@var{envz}} and @code{*@var{envz_len}}.
1779 @end deftypefun