Initial revision

1 files changed, 184 insertions, 0 deletions

diff --git a/manual/search.texi b/manual/search.texi
new file mode 100644
index 0000000000..5442d4e228
--- /dev/null
+++ b/manual/search.texi
@@ -0,0 +1,184 @@
+@node Searching and Sorting
+@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}.
+
+@menu
+* Array Search Function::		The @code{bsearch} function.
+* Array Sort Function::			The @code{qsort} function.
+* Searching and Sorting Example::	An example program.
+@end menu
+
+@node Array Search Function
+@section 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
+the header file @file{<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 *))
+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}.
+
+The @var{compare} function is used to perform the comparison.  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.  The elements of the @var{array} must already
+be sorted in ascending order according to this comparison function.
+
+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.
+@end deftypefun
+
+@node Array Sort Function
+@section 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>}.
+
+@deftypefun void qsort (void *@var{array}, size_t @var{count}, size_t @var{size}, int (*@var{compare}) (const void *, const void *))
+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
+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.
+
+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.
+@end deftypefun
+
+
+@node Searching and Sorting Example
+@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
+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"@},
+                            @{"Link Hogthrob", "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
+
+The output from this program looks like:
+
+@example
+Animal, the animal
+Beaker, the human
+Camilla, the chicken
+Dr. Bunsen Honeydew, the human
+Dr. Strangepork, the pig
+Fozzie, the bear
+Gonzo, the whatever
+Kermit, the frog
+Link Hogthrob, the pig
+Piggy, the pig
+Robin, the frog
+Sam, the eagle
+Swedish Chef, the human
+Sweetums, the monster
+Zoot, the human
+
+
+Kermit, the frog
+Gonzo, the whatever
+Couldn't find Janice.
+@end example
+
+