eglib/src/sort.frag.h

   1 /* A "counting" merge sort that avoids recursion */
   2
   3 #define N_DIGITS (sizeof (size_t) * 8)
   4
   5 static inline digit
   6 add_digits (digit first, digit second, GCompareFunc func)
   7 {
   8         /* merge the two lists */
   9         digit list = NULL;
  10         digit *pos = &list;
  11         while (first && second) {
  12                 if (func (first->data, second->data) > 0) {
  13                         *pos = second;
  14                         second = second->next;
  15                 } else {
  16                         *pos = first;
  17                         first = first->next;
  18                 }
  19                 pos = &((*pos)->next);
  20         }
  21         *pos = first ? first : second;
  22         return list;
  23 }
  24
  25 static inline digit
  26 combine_digits (digit *digits, int max_digit, GCompareFunc func)
  27 {
  28         int i;
  29         digit list = digits [0];
  30         for (i = 1; i <= max_digit; ++i)
  31                 list = add_digits (digits [i], list, func);
  32         return list;
  33 }
  34
  35 static inline int
  36 increment (digit *digits, digit list, int max_digit, GCompareFunc func)
  37 {
  38         int i;
  39
  40         if (!list)
  41                 return max_digit;
  42
  43         for (i = 0; digits [i]; i++) {
  44                 list = add_digits (digits [i], list, func);
  45                 digits [i] = NULL;
  46                 if (i == N_DIGITS-1) /* Should _never_ happen, but if it does, we just devolve into quadratic ;-) */
  47                         break;
  48         }
  49         digits [i] = list;
  50         return i > max_digit ? i : max_digit;
  51 }
  52
  53 static inline digit
  54 do_sort (digit list, GCompareFunc func)
  55 {
  56         int max_digit = 0;
  57         digit digits [N_DIGITS]; /* 128 bytes on 32bit, 512 bytes on 64bit */
  58         memset (digits, 0, sizeof digits);
  59
  60         while (list && list->next) {
  61                 digit next = list->next;
  62                 digit tail = next->next;
  63
  64                 if (func (list->data, next->data) > 0) {
  65                         next->next = list;
  66                         next = list;
  67                         list = list->next;
  68                 }
  69                 next->next = NULL;
  70
  71                 max_digit = increment (digits, list, max_digit, func);
  72
  73                 list = tail;
  74         }
  75
  76         max_digit = increment (digits, list, max_digit, func);
  77
  78         return combine_digits (digits, max_digit, func);
  79 }
  80
  81 #undef N_DIGITS