index 5442d4e..abb93bb 100644 (file)
@@ -1,30 +1,74 @@
-@node Searching and Sorting
-@chapter Searching and Sorting
+@node Searching and Sorting, Pattern Matching, Message Translation, Top
+@chapter Searching and Sorting

This chapter describes functions for searching and sorting arrays of
arbitrary objects.  You pass the appropriate comparison function to be
applied as an argument, along with the size of the objects in the array
-and the total number of elements.  The return value from the comparison
-function should follow the same conventions as the @code{strcmp}
-function; @pxref{String/Array Comparison}.
+and the total number of elements.

-* Array Search Function::              The @code{bsearch} function.
-* Array Sort Function::                        The @code{qsort} function.
-* Searching and Sorting Example::      An example program.
+* Comparison Functions::        Defining how to compare two objects.
+                                Since the sort and search facilities
+                                 are general, you have to specify the
+                                 ordering.
+* Array Search Function::       The @code{bsearch} function.
+* Array Sort Function::         The @code{qsort} function.
+* Search/Sort Example::         An example program.

-@node Array Search Function
+@node Comparison Functions, Array Search Function,  , Searching and Sorting
+@section Defining the Comparison Function
+@cindex Comparison Function
+
+In order to use the sorted array library functions, you have to describe
+how to compare the elements of the array.
+
+To do this, you supply a comparison function to compare two elements of
+the array.  The library will call this function, passing as arguments
+pointers to two array elements to be compared.  Your comparison function
+should return a value the way @code{strcmp} (@pxref{String/Array
+Comparison}) does: negative if the first argument is ``less'' than the
+second, zero if they are ``equal'', and positive if the first argument
+is ``greater''.
+
+Here is an example of a comparison function which works with an array of
+numbers of type @code{double}:
+
+@smallexample
+int
+compare_doubles (const double *a, const double *b)
+@{
+  return (int) (*a - *b);
+@}
+@end smallexample
+
+The header file @file{stdlib.h} defines a name for the data type of
+comparison functions.  This type is a GNU extension.
+
+@comment stdlib.h
+@comment GNU
+@tindex comparison_fn_t
+@smallexample
+int comparison_fn_t (const void *, const void *);
+@end smallexample
+
+@node Array Search Function, Array Sort Function, Comparison Functions, Searching and Sorting
@section Array Search Function
+@cindex search function (for arrays)
+@cindex binary search function (for arrays)
+@cindex array search function

To search a sorted array for an element matching the key, use the
@code{bsearch} function.  The prototype for this function is in
+@pindex stdlib.h

-@deftypefun {void *} bsearch (const void *@var{key}, const void *@var{array}, size_t @var{count}, size_t @var{size}, int (*@var{compare}) (const void *, const void *))
+@comment stdlib.h
+@comment ISO
+@deftypefun {void *} bsearch (const void *@var{key}, const void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
The @code{bsearch} function searches the sorted array @var{array} for an object
that is equivalent to @var{key}.  The array contains @var{count} elements,
-each of which is of size @var{size}.
+each of which is of size @var{size} bytes.

The @var{compare} function is used to perform the comparison.  This
function is called with two pointer arguments and should return an
@@ -37,128 +81,96 @@ The return value is a pointer to the matching array element, or a null
pointer if no match is found.  If the array contains more than one element
that matches, the one that is returned is unspecified.

-Although the specific algorithm used by this function is not specified,
-traditionally a binary search algorithm has been used; hence the name of
-the function.
+This function derives its name from the fact that it is implemented
+using the binary search algorithm.
@end deftypefun

-@node Array Sort Function
+@node Array Sort Function, Search/Sort Example, Array Search Function, Searching and Sorting
@section Array Sort Function
+@cindex sort function (for arrays)
+@cindex quick sort function (for arrays)
+@cindex array sort function

To sort an array using an arbitrary comparison function, use the
@code{qsort} function.  The prototype for this function is in
-@file{<stdlib.h>}.
+@file{stdlib.h}.
+@pindex stdlib.h

-@deftypefun void qsort (void *@var{array}, size_t @var{count}, size_t @var{size}, int (*@var{compare}) (const void *, const void *))
+@comment stdlib.h
+@comment ISO
+@deftypefun void qsort (void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
The @var{qsort} function sorts the array @var{array}.  The array contains
@var{count} elements, each of which is of size @var{size}.

-The @var{compare} function is used to compare perform the comparison on
-the array elements.  This function is called with two pointer arguments
-and should return an integer less than, equal to, or greater than zero
+The @var{compare} function is used to perform the comparison on the
+array elements.  This function is called with two pointer arguments and
+should return an integer less than, equal to, or greater than zero
corresponding to whether its first argument is considered less than,
-equal to, or greater than its second argument.  If two objects compare
-as equal, their order in the sorted array is unspecified.
+equal to, or greater than its second argument.
+
+@cindex stable sorting
+@strong{Warning:} If two objects compare as equal, their order after
+sorting is unpredictable.  That is to say, the sorting is not stable.
+This can make a difference when the comparison considers only part of
+the elements.  Two elements with the same sort key may differ in other
+respects.
+
+If you want the effect of a stable sort, you can get this result by
+writing the comparison function so that, lacking other reason
+distinguish between two elements, it compares them by their addresses.
+Note that doing this may make the sorting algorithm less efficient, so
+do it only if necessary.
+
+Here is a simple example of sorting an array of doubles in numerical
+order, using the comparison function defined above (@pxref{Comparison
+Functions}):
+
+@smallexample
+@{
+  double *array;
+  int size;
+  @dots{}
+  qsort (array, size, sizeof (double), compare_doubles);
+@}
+@end smallexample

-Although the specific algorithm used by this function is not specified,
-traditionally a quick sort algorithm has been used; hence the name of
-the function.
+The @code{qsort} function derives its name from the fact that it was
+originally implemented using the ``quick sort'' algorithm.
@end deftypefun

-
-@node Searching and Sorting Example
+@node Search/Sort Example,  , Array Sort Function, Searching and Sorting
@section Searching and Sorting Example

Here is an example showing the use of @code{qsort} and @code{bsearch}
-with an array of @code{struct}s.  The objects in the array are sorted
+with an array of structures.  The objects in the array are sorted
by comparing their @code{name} fields with the @code{strcmp} function.
Then, we can look up individual objects based on their names.

@comment This example is dedicated to the memory of Jim Henson.  RIP.
-@example
-#include <stdlib.h>
-#include <stdio.h>
-#include <string.h>
-
-/* @r{Define an array of critters to sort.} */
-
-struct critter @{
-  char *name;
-  char *species;
-  @};
-
-struct critter muppets[] = @{@{"Kermit", "frog"@},
-                            @{"Piggy", "pig"@},
-                            @{"Gonzo", "whatever"@},
-                            @{"Fozzie", "bear"@},
-                            @{"Sam", "eagle"@},
-                            @{"Robin", "frog"@},
-                            @{"Animal", "animal"@},
-                            @{"Camilla", "chicken"@},
-                            @{"Sweetums", "monster"@},
-                            @{"Dr. Strangepork", "pig"@},
-                            @{"Zoot", "human"@},
-                            @{"Dr. Bunsen Honeydew", "human"@},
-                            @{"Beaker", "human"@},
-                            @{"Swedish Chef", "human"@}@};
-
-int count = sizeof(muppets) / sizeof(struct critter);
-
-
-
-/* @r{This is the comparison function used for sorting and searching.} */
-
-int critter_cmp (const struct critter *c1, const struct critter *c2)
-@{
-  return strcmp (c1->name, c2->name);
-@}
-
-
-/* @r{Print information about a critter.} */
-
-void print_critter (const struct critter *c)
-@{
-  printf ("%s, the %s\n", c->name, c->species);
-@}
-
-
-/* @r{Do the lookup into the sorted array.} */
-
-void find_critter (char *name)
-@{
-  struct critter target, *result;
-  target.name = name;
-  result = bsearch (&target, muppets, count, sizeof(struct critter),
-                    critter_cmp);
-  if (result)
-    print_critter (result);
-  else
-    printf ("Couldn't find %s.\n", name);
-@}
-
-
-/* @r{Main program.} */
-
-void main (void)
-@{
-  int i;
-
-  qsort (muppets, count, sizeof(struct critter), critter_cmp);
-
-  for (i=0; i<count; i++)
-    print_critter (&muppets[i]);
-  printf ("\n");
-
-  find_critter ("Kermit");
-  find_critter ("Gonzo");
-  find_critter ("Janice");
-@}
-@end example
+@smallexample
+@include search.c.texi
+@end smallexample

+@cindex Kermit the frog
The output from this program looks like:

-@example
+@smallexample
+Kermit, the frog
+Piggy, the pig
+Gonzo, the whatever
+Fozzie, the bear
+Sam, the eagle
+Robin, the frog
+Animal, the animal
+Camilla, the chicken
+Sweetums, the monster
+Dr. Strangepork, the pig
+Zoot, the human
+Dr. Bunsen Honeydew, the human
+Beaker, the human
+Swedish Chef, the human
+
Animal, the animal
Beaker, the human
Camilla, the chicken
@@ -175,10 +187,7 @@ Swedish Chef, the human
Sweetums, the monster
Zoot, the human

-
Kermit, the frog
Gonzo, the whatever
Couldn't find Janice.
-@end example
-
-
+@end smallexample