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.

Defining the 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 strcmp (see 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 double:

     int
     compare_doubles (const void *a, const void *b)
     {
       const double *da = (const double *) a;
       const double *db = (const double *) b;

       return (*da > *db) - (*da < *db);
     }

The header file stdlib.h defines a name for the data type of comparison functions.  This type is a GNU extension.

     int comparison_fn_t (const void *, const void *);

Array Search Function
=====================

Generally searching for a specific element in an array means that potentially all elements must be checked.  Theglibc contains functions to perform linear search.  The prototypes for the following two functions can be found in search.h.

 -- Function: void * lfind (const void *KEY, const void *BASE, size_t *NMEMB, size_t SIZE, comparison_fn_t COMPAR)
     SVID, search.h The lfind function searches in the array with *NMEMB elements of SIZE bytes pointed to by BASE for an element which matches the one pointed to by KEY.  The function pointed to by COMPAR is used to decide whether two elements match.

     The return value is a pointer to the matching element in the array starting at BASE if it is found.  If no matching element is available NULL is returned.

     The mean runtime of this function is *NMEMB/2.  This function should only be used if elements often get added to or deleted from the array in which case it might not be useful to sort the array before searching.

 -- Function: void * lsearch (const void *KEY, void *BASE, size_t *NMEMB, size_t SIZE, comparison_fn_t COMPAR)
     SVID, search.h

     The lsearch function is similar to the lfind function.  It searches the given array for an element and returns it if found.  The difference is that if no matching element is found the lsearch function adds the object pointed to by KEY (with a size of SIZE bytes) at the end of the array and it increments the value of *NMEMB to reflect this addition.

     This means for the caller that if it is not sure that the array contains the element one is searching for the memory allocated for the array starting at BASE must have room for at least SIZE more bytes.  If one is sure the element is in the array it is better to use lfind so having more room in the array is always necessary when calling lsearch.

To search a sorted array for an element matching the key, use the bsearch function.  The prototype for this function is in the header file stdlib.h.

 -- Function: void * bsearch (const void *KEY, const void *ARRAY, size_t COUNT, size_t SIZE, comparison_fn_t COMPARE)
     ISO, stdlib.h The bsearch function searches the sorted array ARRAY for an object that is equivalent to KEY.  The array contains COUNT elements, each of which is of size SIZE bytes.

     The 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 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.

     This function derives its name from the fact that it is implemented using the binary search algorithm.

Array Sort Function
===================

To sort an array using an arbitrary comparison function, use the qsort function.  The prototype for this function is in stdlib.h.

 -- Function: void qsort (void *ARRAY, size_t COUNT, size_t SIZE, comparison_fn_t COMPARE)
     ISO, stdlib.h The qsort function sorts the array ARRAY.  The array contains COUNT elements, each of which is of size SIZE.

     The 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.

     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.

     Although the object addresses passed to the comparison function lie within the array, they need not correspond with the original locations of those objects because the sorting algorithm may swap around objects in the array before making some comparisons.  The only way to perform a stable sort with qsort is to first augment the objects with a monotonic counter of some kind.

     Here is a simple example of sorting an array of doubles in numerical order, using the comparison function defined above (see Comparison Functions):

          {
            double *array;
            int size;
            ...
            qsort (array, size, sizeof (double), compare_doubles);
          }

     The qsort function derives its name from the fact that it was originally implemented using the ``quick sort'' algorithm.

     The implementation of qsort in this library might not be an in-place sort and might thereby use an extra amount of memory to store the array.

Searching and Sorting Example
=============================

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

          [file search.c.texi not included]

The output from this program looks like:

     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
     Link Hogthrob, 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
     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.

The hsearch function.
=====================

The functions mentioned so far in this chapter are for searching in a sorted or unsorted array.  There are other methods to organize information which later should be searched.  The costs of insert, delete and search differ.  One possible implementation is using hashing tables. The following functions are declared in the header file search.h.

 -- Function: int hcreate (size_t NEL)
     SVID, search.h prelim:hsearch The hcreate function creates a hashing table which can contain at least NEL elements.  There is no possibility to grow this table so it is necessary to choose the value for NEL wisely.  The method used to implement this function might make it necessary to make the number of elements in the hashing table larger than the expected maximal number of elements.  Hashing tables usually work inefficiently if they are filled 80% or more.  The constant access time guaranteed by hashing can only be achieved if few collisions exist.  See Knuth's ``The Art of Computer Programming, Part 3: Searching and Sorting'' for more information.

     The weakest aspect of this function is that there can be at most one hashing table used through the whole program.  The table is allocated in local memory out of control of the programmer.  As an extension theglibc provides an additional set of functions with a reentrant interface which provides a similar interface but which allows keeping arbitrarily many hashing tables.

     It is possible to use more than one hashing table in the program run if the former table is first destroyed by a call to hdestroy.

     The function returns a non-zero value if successful.  If it returns zero, something went wrong.  This could either mean there is already a hashing table in use or the program ran out of memory.

 -- Function: void hdestroy (void)
     SVID, search.h prelim:hsearch The hdestroy function can be used to free all the resources allocated in a previous call of hcreate.  After a call to this function it is again possible to call hcreate and allocate a new table with possibly different size.

     It is important to remember that the elements contained in the hashing table at the time hdestroy is called are not freed by this function.  It is the responsibility of the program code to free those strings (if necessary at all).  Freeing all the element memory is not possible without extra, separately kept information since there is no function to iterate through all available elements in the hashing table. If it is really necessary to free a table and all elements the programmer has to keep a list of all table elements and before calling hdestroy s/he has to free all element's data using this list. This is a very unpleasant mechanism and it also shows that this kind of hashing table is mainly meant for tables which are created once and used until the end of the program run.

Entries of the hashing table and keys for the search are defined using this type:

 -- Data type: struct ENTRY
     Both elements of this structure are pointers to zero-terminated strings. This is a limiting restriction of the functionality of the hsearch functions.  They can only be used for data sets which use the NUL character always and solely to terminate the records.  It is not possible to handle general binary data.

     char *key
          Pointer to a zero-terminated string of characters describing the key for the search or the element in the hashing table.

     char *data
          Pointer to a zero-terminated string of characters describing the data. If the functions will be called only for searching an existing entry this element might stay undefined since it is not used.

 -- Function: ENTRY * hsearch (ENTRY ITEM, ACTION ACTION)
     SVID, search.h prelim:hsearch asunsafe/action==ENTER To search in a hashing table created using hcreate the hsearch function must be used.  This function can perform a simple search for an element (if ACTION has the value FIND) or it can alternatively insert the key element into the hashing table.  Entries are never replaced.

     The key is denoted by a pointer to an object of type ENTRY.  For locating the corresponding position in the hashing table only the key element of the structure is used.

     If an entry with a matching key is found the ACTION parameter is irrelevant.  The found entry is returned.  If no matching entry is found and the ACTION parameter has the value FIND the function returns a NULL pointer.  If no entry is found and the ACTION parameter has the value ENTER a new entry is added to the hashing table which is initialized with the parameter ITEM. A pointer to the newly added entry is returned.

As mentioned before, the hashing table used by the functions described so far is global and there can be at any time at most one hashing table in the program.  A solution is to use the following functions which are a GNU extension.  All have in common that they operate on a hashing table which is described by the content of an object of the type struct hsearch_data.  This type should be treated as opaque, none of its members should be changed directly.

 -- Function: int hcreate_r (size_t NEL, struct hsearch_data *HTAB)
     GNU, search.h prelim:htab

     The hcreate_r function initializes the object pointed to by HTAB to contain a hashing table with at least NEL elements. So this function is equivalent to the hcreate function except that the initialized data structure is controlled by the user.

     This allows having more than one hashing table at one time.  The memory necessary for the struct hsearch_data object can be allocated dynamically.  It must be initialized with zero before calling this function.

     The return value is non-zero if the operation was successful.  If the return value is zero, something went wrong, which probably means the program ran out of memory.

 -- Function: void hdestroy_r (struct hsearch_data *HTAB)
     GNU, search.h prelim:htab

     The hdestroy_r function frees all resources allocated by the hcreate_r function for this very same object HTAB.  As for hdestroy it is the program's responsibility to free the strings for the elements of the table.

 -- Function: int hsearch_r (ENTRY ITEM, ACTION ACTION, ENTRY **RETVAL, struct hsearch_data *HTAB)
     GNU, search.h prelim:htab assafe/action==ENTER

     The hsearch_r function is equivalent to hsearch.  The meaning of the first two arguments is identical.  But instead of operating on a single global hashing table the function works on the table described by the object pointed to by HTAB (which is initialized by a call to hcreate_r).

     Another difference to hcreate is that the pointer to the found entry in the table is not the return value of the function.  It is returned by storing it in a pointer variable pointed to by the RETVAL parameter.  The return value of the function is an integer value indicating success if it is non-zero and failure if it is zero. In the latter case the global variable errno signals the reason for the failure.

     ENOMEM
          The table is filled and hsearch_r was called with a so far unknown key and ACTION set to ENTER.

     ESRCH
          The ACTION parameter is FIND and no corresponding element is found in the table.

The tsearch function.
=====================

Another common form to organize data for efficient search is to use trees.  The tsearch function family provides a nice interface to functions to organize possibly large amounts of data by providing a mean access time proportional to the logarithm of the number of elements. Theglibc implementation even guarantees that this bound is never exceeded even for input data which cause problems for simple binary tree implementations.

The functions described in the chapter are all described in the System V and X/Open specifications and are therefore quite portable.

In contrast to the hsearch functions the tsearch functions can be used with arbitrary data and not only zero-terminated strings.

The tsearch functions have the advantage that no function to initialize data structures is necessary.  A simple pointer of type void * initialized to NULL is a valid tree and can be extended or searched.  The prototypes for these functions can be found in the header file search.h.

 -- Function: void * tsearch (const void *KEY, void **ROOTP, comparison_fn_t COMPAR)
     SVID, search.h prelim:rootp The tsearch function searches in the tree pointed to by *ROOTP for an element matching KEY.  The function pointed to by COMPAR is used to determine whether two elements match.  See Comparison Functions, for a specification of the functions which can be used for the COMPAR parameter.

     If the tree does not contain a matching entry the KEY value will be added to the tree.  tsearch does not make a copy of the object pointed to by KEY (how could it since the size is unknown). Instead it adds a reference to this object which means the object must be available as long as the tree data structure is used.

     The tree is represented by a pointer to a pointer since it is sometimes necessary to change the root node of the tree.  So it must not be assumed that the variable pointed to by ROOTP has the same value after the call.  This also shows that it is not safe to call the tsearch function more than once at the same time using the same tree.  It is no problem to run it more than once at a time on different trees.

     The return value is a pointer to the matching element in the tree.  If a new element was created the pointer points to the new data (which is in fact KEY).  If an entry had to be created and the program ran out of space NULL is returned.

 -- Function: void * tfind (const void *KEY, void *const *ROOTP, comparison_fn_t COMPAR)
     SVID, search.h prelim:rootp assafe acsafe The tfind function is similar to the tsearch function.  It locates an element matching the one pointed to by KEY and returns a pointer to this element.  But if no matching element is available no new element is entered (note that the ROOTP parameter points to a constant pointer).  Instead the function returns NULL.

Another advantage of the tsearch functions in contrast to the hsearch functions is that there is an easy way to remove elements.

 -- Function: void * tdelete (const void *KEY, void **ROOTP, comparison_fn_t COMPAR)
     SVID, search.h prelim:rootp To remove a specific element matching KEY from the tree tdelete can be used.  It locates the matching element using the same method as tfind.  The corresponding element is then removed and a pointer to the parent of the deleted node is returned by the function.  If there is no matching entry in the tree nothing can be deleted and the function returns NULL.  If the root of the tree is deleted tdelete returns some unspecified value not equal to NULL.

 -- Function: void tdestroy (void *VROOT, __free_fn_t FREEFCT)
     GNU, search.h If the complete search tree has to be removed one can use tdestroy.  It frees all resources allocated by the tsearch functions to generate the tree pointed to by VROOT.

     For the data in each tree node the function FREEFCT is called. The pointer to the data is passed as the argument to the function.  If no such work is necessary FREEFCT must point to a function doing nothing.  It is called in any case.

     This function is a GNU extension and not covered by the System V or X/Open specifications.

In addition to the functions to create and destroy the tree data structure, there is another function which allows you to apply a function to all elements of the tree.  The function must have this type:

     void __action_fn_t (const void *nodep, VISIT value, int level);

The NODEP is the data value of the current node (once given as the KEY argument to tsearch).  LEVEL is a numeric value which corresponds to the depth of the current node in the tree.  The root node has the depth 0 and its children have a depth of 1 and so on.  The VISIT type is an enumeration type.

 -- Data Type: VISIT
     The VISIT value indicates the status of the current node in the tree and how the function is called.  The status of a node is either `leaf' or `internal node'.  For each leaf node the function is called exactly once, for each internal node it is called three times: before the first child is processed, after the first child is processed and after both children are processed.  This makes it possible to handle all three methods of tree traversal (or even a combination of them).

     preorder
          The current node is an internal node and the function is called before the first child was processed.

     postorder
          The current node is an internal node and the function is called after the first child was processed.

     endorder
          The current node is an internal node and the function is called after the second child was processed.

     leaf
          The current node is a leaf.

 -- Function: void twalk (const void *ROOT, __action_fn_t ACTION)
     SVID, search.h prelim:root assafe acsafe For each node in the tree with a node pointed to by ROOT, the twalk function calls the function provided by the parameter ACTION.  For leaf nodes the function is called exactly once with VALUE set to leaf.  For internal nodes the function is called three times, setting the VALUE parameter or ACTION to the appropriate value.  The LEVEL argument for the ACTION function is computed while descending the tree by increasing the value by one for each descent to a child, starting with the value 0 for the root node.

     Since the functions used for the ACTION parameter to twalk must not modify the tree data, it is safe to run twalk in more than one thread at the same time, working on the same tree.  It is also safe to call tfind in parallel.  Functions which modify the tree must not be used, otherwise the behavior is undefined.  However, it is difficult to pass data external to the tree to the callback function without resorting to global variables (and thread safety issues), so see the twalk_r function below.

 -- Function: void twalk_r (const void *ROOT, void (*ACTION) (const void *KEY, VISIT WHICH, void *CLOSURE), void *CLOSURE)
     GNU, search.h prelim:root assafe acsafe For each node in the tree with a node pointed to by ROOT, the twalk_r function calls the function provided by the parameter ACTION.  For leaf nodes the function is called exactly once with WHICH set to leaf.  For internal nodes the function is called three times, setting the WHICH parameter of ACTION to the appropriate value.  The CLOSURE parameter is passed down to each call of the ACTION function, unmodified.

     It is possible to implement the twalk function on top of the twalk_r function, which is why there is no separate level parameter.

               [file twalk.c.texi not included]