eglib/src/sort.frag.h

   1 /*
   2  * sort.frag.h: Common implementation of linked-list sorting
   3  *
   4  * Author:
   5  *   Raja R Harinath (rharinath@novell.com)
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining
   8  * a copy of this software and associated documentation files (the
   9  * "Software"), to deal in the Software without restriction, including
  10  * without limitation the rights to use, copy, modify, merge, publish,
  11  * distribute, sublicense, and/or sell copies of the Software, and to
  12  * permit persons to whom the Software is furnished to do so, subject to
  13  * the following conditions:
  14  *
  15  * The above copyright notice and this permission notice shall be
  16  * included in all copies or substantial portions of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  19  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  21  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  22  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  23  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  24  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  *
  26  * (C) 2006 Novell, Inc.
  27  */
  28
  29 /*
  30  * This code requires a typedef named 'list_node' for the list node.  It
  31  * is assumed that the list type is the type of a pointer to a list
  32  * node, and that the node has a field named 'next' that implements to
  33  * the linked list.  No additional invariant is maintained (e.g. the
  34  * 'prev' pointer of a doubly-linked list node is _not_ updated).  Any
  35  * invariant would require a post-processing pass to fix matters if
  36  * necessary.
  37  *
  38  * Note: We refer to a list fragment as a "digit" because the code for
  39  * maintaining the invariants of the core data structure parallels the
  40  * code for incrementing the binary representation of a number.
  41  */
  42 typedef list_node *digit;
  43
  44 /*
  45  * The maximum possible depth of the merge tree
  46  *   = ceiling (log2 (maximum number of list nodes))
  47  *   = ceiling (log2 (maximum possible memory size/size of each list node))
  48  *   = number of bits in 'size_t' - floor (log2 (sizeof digit))
  49  * Also, each "digit" is at least 2 nodes long: we can reduce the depth by 1
  50  */
  51
  52 #define FLOOR_LOG2(x) (((x)>=2) + ((x)>=4) + ((x)>=8) + ((x)>=16) + ((x)>=32) + ((x)>=64) + ((x)>=128))
  53 #define MAX_DIGITS ((sizeof (size_t) * 8) - FLOOR_LOG2(sizeof (list_node)) - 1)
  54
  55 static inline digit
  56 add_digits (digit first, digit second, GCompareFunc func)
  57 {
  58         /* merge the two lists */
  59         digit list = NULL;
  60         digit *pos = &list;
  61         while (first && second) {
  62                 if (func (first->data, second->data) > 0) {
  63                         *pos = second;
  64                         second = second->next;
  65                 } else {
  66                         *pos = first;
  67                         first = first->next;
  68                 }
  69                 pos = &((*pos)->next);
  70         }
  71         *pos = first ? first : second;
  72         return list;
  73 }
  74
  75 static inline digit
  76 combine_digits (digit *digits, digit list, int n_digits, GCompareFunc func)
  77 {
  78         int i;
  79         for (i = 0; i < n_digits; ++i)
  80                 list = add_digits (digits [i], list, func);
  81         return list;
  82 }
  83
  84 /*
  85  * Given: length(list) == k
  86  * Invariant: digit[i] == NULL || length(digit[i]) == k * 2**i
  87  */
  88 static inline int
  89 increment (digit *digits, digit list, int n_digits, GCompareFunc func)
  90 {
  91         int i;
  92         for (i = 0; i < n_digits && digits [i]; i++) {
  93                 list = add_digits (digits [i], list, func);
  94                 digits [i] = NULL;
  95         }
  96         if (i == MAX_DIGITS) /* Will _never_ happen: so we can just devolve into quadratic ;-) */
  97                 --i;
  98
  99         if (i == n_digits)
 100                 ++n_digits;
 101         digits [i] = list;
 102         return n_digits;
 103 }
 104
 105 /*
 106  * A mergesort that avoids recursion.  The 'digits' array essentially
 107  * captures the recursion stack.  The actual merge tree is built in a
 108  * bottom-up manner.  It's "counting", since we "increment" a set of
 109  * "digit"s.
 110  */
 111 static inline digit
 112 do_sort (digit list, GCompareFunc func)
 113 {
 114         int n_digits = 0;
 115         digit digits [MAX_DIGITS]; /* ~ 128 bytes on 32bit, ~ 512 bytes on 64bit */
 116
 117         while (list && list->next) {
 118                 digit next = list->next;
 119                 digit tail = next->next;
 120
 121                 if (func (list->data, next->data) > 0) {
 122                         next->next = list;
 123                         next = list;
 124                         list = list->next;
 125                 }
 126                 next->next = NULL;
 127
 128                 n_digits = increment (digits, list, n_digits, func);
 129
 130                 list = tail;
 131         }
 132
 133         return combine_digits (digits, list, n_digits, func);
 134 }
 135
 136 #undef MAX_DIGITS
 137 #undef FLOOR_LOG2