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