src/list/lsort.h

Go to the documentation of this file.

/*
 * $Id: lsort.h,v 1.6 2005/04/15 23:23:47 fabio Exp $
 *
 */
/*
 *  Generic linked-list sorting package
 *  Richard Rudell, UC Berkeley, 4/1/87
 *
 *  Use:
 *      #define TYPE            the linked-list type (a struct or typedef)
 *      #define SORT            sorting routine (see below)
 *      #include "lsort.h"
 *
 *  Optional:
 *      #define NEXT            'next' field name in the linked-list structure
 *      #define DECL_SORT       'static' or undefined
 *      #define DECL_SORT1      'static' or undefined
 *      #define SORT1           optional sorting routine interface
 *      #define FIELD           select subfield of the structure for compare
 *      #define DIRECT_COMPARE  in-line expand the compare routine
 *
 *  This defines up to two routines:
 *      DECL_SORT TYPE *
 *      SORT1(list, compare)
 *      TYPE *list;
 *      int (*compare)(TYPE *x, TYPE *y);
 *          sort the linked list 'list' according to the compare function
 *          'compare'
 *
 *      DECL_SORT1 TYPE *
 *      SORT(list, compare, length)
 *      TYPE *list;
 *      int (*compare)(TYPE *x, TYPE *y);
 *      int length;
 *          sort the linked list 'list' according to the compare function
 *          'compare'.  length is the length of the linked list.
 *
 *  Both routines gracefully handle length == 0 (in which case, list == 0 
 *  is also allowed).
 *
 *  NEXT defines the name of the next field in the linked list.  If not
 *  given, 'next' is assumed.
 *
 *  By default, both routines are declared 'static'.  This can be changed
 *  using '#define DECL_SORT' or '#define DECL_SORT1'.
 *
 *  If FIELD is used, then a pointer to the particular field is passed
 *  to the comparison function (rather than a TYPE *).  In this case,
 *  the compare function is called with:
 *      
 *              if ((*compare)(x->FIELD, y->FIELD)) {
 *
 *  If DIRECT_COMPARE is used, then the 'FIELD' items are compared using
 *  a simple '>' (useful for scalars to save subroutine overhead)
 */

#ifndef NEXT
#define NEXT next
#endif

#ifndef DECL_SORT1
#define DECL_SORT1 static
#endif

#ifndef DECL_SORT
#define DECL_SORT static
#endif

#ifdef FIELD
#define COMPTYPE void *
#else
#define COMPTYPE TYPE
#endif

DECL_SORT TYPE *SORT(TYPE *list_in,
                     int (*compare)(COMPTYPE, COMPTYPE), int cnt);


#ifdef SORT1

DECL_SORT1 TYPE *
SORT1(TYPE *list_in, int (*compare)(COMPTYPE, COMPTYPE))
{
    register int cnt;
    register TYPE *p;

    /* Find the length of the list */
    for(p = list_in, cnt = 0; p != 0; p = p->NEXT, cnt++)
        ;
    return SORT(list_in, compare, cnt);
}

#endif

DECL_SORT TYPE *
SORT(TYPE *list_in, int (*compare)(COMPTYPE, COMPTYPE), int cnt)
{
    register TYPE *p, **plast, *list1, *list2;
    register int i;

    if (cnt > 1) {
        /* break the list in half */
        for(p = list_in, i = cnt/2-1; i > 0; p = p->NEXT, i--)
            ;
        list1 = list_in;
        list2 = p->NEXT;
        p->NEXT = 0;

        /* Recursively sort the sub-lists (unless only 1 element) */
        if ((i = cnt/2) > 1) {
            list1 = SORT(list1, compare, i);
        }
        if ((i = cnt - i) > 1) {
            list2 = SORT(list2, compare, i);
        }

        /* Merge the two sorted sub-lists */
        plast = &list_in;
        for(;;) {
#ifdef FIELD
#ifdef DIRECT_COMPARE
            if (list1->FIELD < list2->FIELD) {
#else
            if ((*compare)(list1->FIELD, list2->FIELD) <= 0) {
#endif
#else
            if ((*compare)(list1, list2) <= 0) {
#endif
                *plast = list1;
                plast = &(list1->NEXT);
                if ((list1 = list1->NEXT) == 0) {
                    *plast = list2;
                    break;
                }
            } else {
                *plast = list2;
                plast = &(list2->NEXT);
                if ((list2 = list2->NEXT) == 0) {
                    *plast = list1;
                    break;
                }
            }
        }
    }

    return list_in;
}

#undef TYPE
#undef SORT
#undef SORT1
#undef DECL_SORT
#undef DECL_SORT1
#undef FIELD
#undef DIRECT_COMPARE
#undef NEXT

---