[13] | 1 | /* |
---|
| 2 | * $Id: lsort.h,v 1.6 2005/04/15 23:23:47 fabio Exp $ |
---|
| 3 | * |
---|
| 4 | */ |
---|
| 5 | /* |
---|
| 6 | * Generic linked-list sorting package |
---|
| 7 | * Richard Rudell, UC Berkeley, 4/1/87 |
---|
| 8 | * |
---|
| 9 | * Use: |
---|
| 10 | * #define TYPE the linked-list type (a struct or typedef) |
---|
| 11 | * #define SORT sorting routine (see below) |
---|
| 12 | * #include "lsort.h" |
---|
| 13 | * |
---|
| 14 | * Optional: |
---|
| 15 | * #define NEXT 'next' field name in the linked-list structure |
---|
| 16 | * #define DECL_SORT 'static' or undefined |
---|
| 17 | * #define DECL_SORT1 'static' or undefined |
---|
| 18 | * #define SORT1 optional sorting routine interface |
---|
| 19 | * #define FIELD select subfield of the structure for compare |
---|
| 20 | * #define DIRECT_COMPARE in-line expand the compare routine |
---|
| 21 | * |
---|
| 22 | * This defines up to two routines: |
---|
| 23 | * DECL_SORT TYPE * |
---|
| 24 | * SORT1(list, compare) |
---|
| 25 | * TYPE *list; |
---|
| 26 | * int (*compare)(TYPE *x, TYPE *y); |
---|
| 27 | * sort the linked list 'list' according to the compare function |
---|
| 28 | * 'compare' |
---|
| 29 | * |
---|
| 30 | * DECL_SORT1 TYPE * |
---|
| 31 | * SORT(list, compare, length) |
---|
| 32 | * TYPE *list; |
---|
| 33 | * int (*compare)(TYPE *x, TYPE *y); |
---|
| 34 | * int length; |
---|
| 35 | * sort the linked list 'list' according to the compare function |
---|
| 36 | * 'compare'. length is the length of the linked list. |
---|
| 37 | * |
---|
| 38 | * Both routines gracefully handle length == 0 (in which case, list == 0 |
---|
| 39 | * is also allowed). |
---|
| 40 | * |
---|
| 41 | * NEXT defines the name of the next field in the linked list. If not |
---|
| 42 | * given, 'next' is assumed. |
---|
| 43 | * |
---|
| 44 | * By default, both routines are declared 'static'. This can be changed |
---|
| 45 | * using '#define DECL_SORT' or '#define DECL_SORT1'. |
---|
| 46 | * |
---|
| 47 | * If FIELD is used, then a pointer to the particular field is passed |
---|
| 48 | * to the comparison function (rather than a TYPE *). In this case, |
---|
| 49 | * the compare function is called with: |
---|
| 50 | * |
---|
| 51 | * if ((*compare)(x->FIELD, y->FIELD)) { |
---|
| 52 | * |
---|
| 53 | * If DIRECT_COMPARE is used, then the 'FIELD' items are compared using |
---|
| 54 | * a simple '>' (useful for scalars to save subroutine overhead) |
---|
| 55 | */ |
---|
| 56 | |
---|
| 57 | #ifndef NEXT |
---|
| 58 | #define NEXT next |
---|
| 59 | #endif |
---|
| 60 | |
---|
| 61 | #ifndef DECL_SORT1 |
---|
| 62 | #define DECL_SORT1 static |
---|
| 63 | #endif |
---|
| 64 | |
---|
| 65 | #ifndef DECL_SORT |
---|
| 66 | #define DECL_SORT static |
---|
| 67 | #endif |
---|
| 68 | |
---|
| 69 | #ifdef FIELD |
---|
| 70 | #define COMPTYPE void * |
---|
| 71 | #else |
---|
| 72 | #define COMPTYPE TYPE |
---|
| 73 | #endif |
---|
| 74 | |
---|
| 75 | DECL_SORT TYPE *SORT(TYPE *list_in, |
---|
| 76 | int (*compare)(COMPTYPE, COMPTYPE), int cnt); |
---|
| 77 | |
---|
| 78 | |
---|
| 79 | #ifdef SORT1 |
---|
| 80 | |
---|
| 81 | DECL_SORT1 TYPE * |
---|
| 82 | SORT1(TYPE *list_in, int (*compare)(COMPTYPE, COMPTYPE)) |
---|
| 83 | { |
---|
| 84 | register int cnt; |
---|
| 85 | register TYPE *p; |
---|
| 86 | |
---|
| 87 | /* Find the length of the list */ |
---|
| 88 | for(p = list_in, cnt = 0; p != 0; p = p->NEXT, cnt++) |
---|
| 89 | ; |
---|
| 90 | return SORT(list_in, compare, cnt); |
---|
| 91 | } |
---|
| 92 | |
---|
| 93 | #endif |
---|
| 94 | |
---|
| 95 | DECL_SORT TYPE * |
---|
| 96 | SORT(TYPE *list_in, int (*compare)(COMPTYPE, COMPTYPE), int cnt) |
---|
| 97 | { |
---|
| 98 | register TYPE *p, **plast, *list1, *list2; |
---|
| 99 | register int i; |
---|
| 100 | |
---|
| 101 | if (cnt > 1) { |
---|
| 102 | /* break the list in half */ |
---|
| 103 | for(p = list_in, i = cnt/2-1; i > 0; p = p->NEXT, i--) |
---|
| 104 | ; |
---|
| 105 | list1 = list_in; |
---|
| 106 | list2 = p->NEXT; |
---|
| 107 | p->NEXT = 0; |
---|
| 108 | |
---|
| 109 | /* Recursively sort the sub-lists (unless only 1 element) */ |
---|
| 110 | if ((i = cnt/2) > 1) { |
---|
| 111 | list1 = SORT(list1, compare, i); |
---|
| 112 | } |
---|
| 113 | if ((i = cnt - i) > 1) { |
---|
| 114 | list2 = SORT(list2, compare, i); |
---|
| 115 | } |
---|
| 116 | |
---|
| 117 | /* Merge the two sorted sub-lists */ |
---|
| 118 | plast = &list_in; |
---|
| 119 | for(;;) { |
---|
| 120 | #ifdef FIELD |
---|
| 121 | #ifdef DIRECT_COMPARE |
---|
| 122 | if (list1->FIELD < list2->FIELD) { |
---|
| 123 | #else |
---|
| 124 | if ((*compare)(list1->FIELD, list2->FIELD) <= 0) { |
---|
| 125 | #endif |
---|
| 126 | #else |
---|
| 127 | if ((*compare)(list1, list2) <= 0) { |
---|
| 128 | #endif |
---|
| 129 | *plast = list1; |
---|
| 130 | plast = &(list1->NEXT); |
---|
| 131 | if ((list1 = list1->NEXT) == 0) { |
---|
| 132 | *plast = list2; |
---|
| 133 | break; |
---|
| 134 | } |
---|
| 135 | } else { |
---|
| 136 | *plast = list2; |
---|
| 137 | plast = &(list2->NEXT); |
---|
| 138 | if ((list2 = list2->NEXT) == 0) { |
---|
| 139 | *plast = list1; |
---|
| 140 | break; |
---|
| 141 | } |
---|
| 142 | } |
---|
| 143 | } |
---|
| 144 | } |
---|
| 145 | |
---|
| 146 | return list_in; |
---|
| 147 | } |
---|
| 148 | |
---|
| 149 | #undef TYPE |
---|
| 150 | #undef SORT |
---|
| 151 | #undef SORT1 |
---|
| 152 | #undef DECL_SORT |
---|
| 153 | #undef DECL_SORT1 |
---|
| 154 | #undef FIELD |
---|
| 155 | #undef DIRECT_COMPARE |
---|
| 156 | #undef NEXT |
---|