mono/eglib/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 typedef list_node *digit;
  39
  40 /*
  41  * The maximum possible depth of the merge tree
  42  *   = ceiling (log2 (maximum number of list nodes))
  43  *   = ceiling (log2 (maximum possible memory size/size of each list node))
  44  *   = number of bits in 'size_t' - floor (log2 (sizeof digit))
  45  * Also, each list in sort_info is at least 2 nodes long: we can reduce the depth by 1
  46  */
  47 #define FLOOR_LOG2(x) (((x)>=2) + ((x)>=4) + ((x)>=8) + ((x)>=16) + ((x)>=32) + ((x)>=64) + ((x)>=128))
  48 #define MAX_RANKS ((sizeof (size_t) * 8) - FLOOR_LOG2(sizeof (list_node)) - 1)
  49
  50 struct sort_info
  51 {
  52         int min_rank, n_ranks;
  53         GCompareFunc func;
  54
  55         /* Invariant: ranks[i] == NULL || length(ranks[i]) >= 2**(i+1) */
  56         list_node *ranks [MAX_RANKS]; /* ~ 128 bytes on 32bit, ~ 512 bytes on 64bit */
  57 };
  58
  59 static inline void
  60 init_sort_info (struct sort_info *si, GCompareFunc func)
  61 {
  62         si->min_rank = si->n_ranks = 0;
  63         si->func = func;
  64         /* we don't need to initialize si->ranks, since we never lookup past si->n_ranks.  */
  65 }
  66
  67 static inline list_node *
  68 merge_lists (list_node *first, list_node *second, GCompareFunc func)
  69 {
  70         /* merge the two lists */
  71         list_node *list = NULL;
  72         list_node **pos = &list;
  73         while (first && second) {
  74                 if (func (first->data, second->data) > 0) {
  75                         *pos = second;
  76                         second = second->next;
  77                 } else {
  78                         *pos = first;
  79                         first = first->next;
  80                 }
  81                 pos = &((*pos)->next);
  82         }
  83         *pos = first ? first : second;
  84         return list;
  85 }
  86
  87 /* Pre-condition: upto <= si->n_ranks, list == NULL || length(list) == 1 */
  88 static inline list_node *
  89 sweep_up (struct sort_info *si, list_node *list, int upto)
  90 {
  91 #if defined(__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 406)
  92         /*
  93          * GCC incorrectly thinks we're writing below si->ranks array bounds.
  94          */
  95 #pragma GCC diagnostic push
  96 #pragma GCC diagnostic ignored "-Warray-bounds"
  97 #endif
  98
  99         int i;
 100         for (i = si->min_rank; i < upto; ++i) {
 101                 list = merge_lists (si->ranks [i], list, si->func);
 102                 si->ranks [i] = NULL;
 103         }
 104         return list;
 105
 106 #if defined(__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 406)
 107 #pragma GCC diagnostic pop
 108 #endif
 109 }
 110
 111 /*
 112  * The 'ranks' array essentially captures the recursion stack of a mergesort.
 113  * The merge tree is built in a bottom-up manner.  The control loop for
 114  * updating the 'ranks' array is analogous to incrementing a binary integer,
 115  * and the O(n) time for counting upto n translates to O(n) merges when
 116  * inserting rank-0 lists.  When we plug in the sizes of the lists involved in
 117  * those merges, we get the O(n log n) time for the sort.
 118  *
 119  * Inserting higher-ranked lists reduce the height of the merge tree, and also
 120  * eliminate a lot of redundant comparisons when merging two lists that would've
 121  * been part of the same run.  Adding a rank-i list is analogous to incrementing
 122  * a binary integer by 2**i in one operation, thus sharing a similar speedup.
 123  *
 124  * When inserting higher-ranked lists, we choose to clear out the lower ranks
 125  * in the interests of keeping the sort stable, but this makes analysis harder.
 126  * Note that clearing the lower-ranked lists is O(length(list))-- thus it
 127  * shouldn't affect the O(n log n) behaviour.  IOW, inserting one rank-i list
 128  * is equivalent to inserting 2**i rank-0 lists, thus even if we do i additional
 129  * merges in the clearing-out (taking at most 2**i time) we are still fine.
 130  */
 131
 132 #define stringify2(x) #x
 133 #define stringify(x) stringify2(x)
 134
 135 /* Pre-condition: 2**(rank+1) <= length(list) < 2**(rank+2) (therefore: length(list) >= 2) */
 136 static inline void
 137 insert_list (struct sort_info *si, list_node* list, int rank)
 138 {
 139 #if defined(__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 406)
 140         /*
 141          * GCC incorrectly thinks we're writing below si->ranks array bounds.
 142          */
 143 #pragma GCC diagnostic push
 144 #pragma GCC diagnostic ignored "-Warray-bounds"
 145 #endif
 146
 147         int i;
 148
 149         if (rank > si->n_ranks) {
 150                 if (rank > MAX_RANKS) {
 151                         g_warning ("Rank '%d' should not exceed " stringify (MAX_RANKS), rank);
 152                         rank = MAX_RANKS;
 153                 }
 154                 list = merge_lists (sweep_up (si, NULL, si->n_ranks), list, si->func);
 155                 for (i = si->n_ranks; i < rank; ++i)
 156                         si->ranks [i] = NULL;
 157         } else {
 158                 if (rank)
 159                         list = merge_lists (sweep_up (si, NULL, rank), list, si->func);
 160                 for (i = rank; i < si->n_ranks && si->ranks [i]; ++i) {
 161                         list = merge_lists (si->ranks [i], list, si->func);
 162                         si->ranks [i] = NULL;
 163                 }
 164         }
 165
 166         if (i == MAX_RANKS) /* Will _never_ happen: so we can just devolve into quadratic ;-) */
 167                 --i;
 168         if (i >= si->n_ranks)
 169                 si->n_ranks = i + 1;
 170         si->min_rank = i;
 171         si->ranks [i] = list;
 172
 173 #if defined(__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 406)
 174 #pragma GCC diagnostic pop
 175 #endif
 176 }
 177
 178 #undef stringify2
 179 #undef stringify
 180 #undef MAX_RANKS
 181 #undef FLOOR_LOG2
 182
 183 /* A non-recursive mergesort */
 184 static inline digit
 185 do_sort (list_node* list, GCompareFunc func)
 186 {
 187         struct sort_info si;
 188
 189         init_sort_info (&si, func);
 190
 191         while (list && list->next) {
 192                 list_node* next = list->next;
 193                 list_node* tail = next->next;
 194
 195                 if (func (list->data, next->data) > 0) {
 196                         next->next = list;
 197                         next = list;
 198                         list = list->next;
 199                 }
 200                 next->next = NULL;
 201
 202                 insert_list (&si, list, 0);
 203
 204                 list = tail;
 205         }
 206
 207         return sweep_up (&si, list, si.n_ranks);
 208 }