compiler/alib/mergesortlist.c

   1 /*
   2      Copyright © 1995-2001, The AROS Development Team. All rights reserved.
   3      $Id$
   4
   5      Desc: Sort a list using a variant of the MergeSort algorithm.
   6      Lang: english
   7 */
   8
   9 #include <exec/lists.h>
  10 #include <stddef.h>
  11
  12 /*****************************************************************************
  13
  14     NAME */
  15 #if defined(__GNUC__) && (defined(__x86_64__) || defined(__i386__))
  16         __attribute__((regparm(2)))
  17 #endif
  18         static inline struct MinNode *Merge(
  19
  20 /*  SYNOPSIS */
  21         struct MinNode *l,
  22         int (*compare)(struct MinNode *n1, struct MinNode *n2, void *data),
  23         void *data)
  24
  25 /*  FUNCTION
  26         Given a list of ordered circular sublists, merge pairs of ordered sublists into one
  27         ordered circular sublist.
  28
  29     INPUTS
  30         l       - The first node of the first sublist. The sublists must be linked one
  31                   after the other one, and must be circular lists, that is their
  32                   first node's Pred pointer must point to their last node.
  33
  34                   I.e., the 2nd sublist will be at l->mln_Pred->mln_Succ, the 3rd will be at
  35                   l->mln_Pred->mln_Succ->mln_Pred->mln_Succ and so on.
  36
  37         compare - Pointer to the comparison function used to merge the
  38                   sublists
  39
  40         data    - Pointer to user-defined data which will be passed untouched
  41                   to the comparison function.
  42
  43     RESULT
  44         Pointer to the first node of the resulting list of sublists, with the same
  45         format of the input list, but with pairs of sublists merged into one.
  46
  47 ******************************************************************************/
  48 {
  49     struct MinNode *l1, *last_l1, *l2, *last_l2, *next_l;
  50     struct MinNode *first = NULL, **first_ptr, **last_ptr = &first;
  51
  52     l1 = l;
  53
  54     /* l1 points to the 1st sublist, l2 points to the 2nd.
  55
  56        Should there be no l2, we don't need to do anything special, as
  57        l1 will already be linked with the rest of the list AND it won't
  58        obviously need to be merged with another list.  */
  59     while (l1 && (l2 = (last_l1 = l1->mln_Pred)->mln_Succ))
  60     {
  61         last_l2 = l2->mln_Pred;
  62
  63         next_l  = last_l2->mln_Succ;
  64
  65         /* This will make the below loop slightly faster, since there will only
  66            be tests against the constant NULL.  */
  67         last_l1->mln_Succ = NULL;
  68         last_l2->mln_Succ = NULL;
  69
  70         /* Pointer to the beginning of the merged sublist */
  71         first_ptr = last_ptr;
  72         do
  73         {
  74             if (compare(l1, l2, data) < 0)
  75             {
  76                 l1->mln_Pred = (struct MinNode *)((char *)last_ptr -
  77                                offsetof(struct MinNode, mln_Succ));
  78                 *last_ptr    = l1;
  79                 l1           = l1->mln_Succ;
  80             }
  81             else
  82             {
  83                 l2->mln_Pred = (struct MinNode *)((char *)last_ptr -
  84                                offsetof(struct MinNode, mln_Succ));
  85                 *last_ptr    = l2;
  86                 l2           = l2->mln_Succ;
  87             }
  88
  89             last_ptr = &(*last_ptr)->mln_Succ;
  90         } while (l1 && l2);
  91
  92         if (l1)
  93         {
  94             l1->mln_Pred = (struct MinNode *)((char *)last_ptr -
  95                            offsetof(struct MinNode, mln_Succ));
  96
  97             *last_ptr              = l1;
  98             (*first_ptr)->mln_Pred = last_l1;
  99             last_ptr               = &last_l1->mln_Succ;
 100         }
 101         else
 102         if (l2)
 103         {
 104             l2->mln_Pred = (struct MinNode *)((char *)last_ptr -
 105                            offsetof(struct MinNode, mln_Succ));
 106
 107             *last_ptr              = l2;
 108             (*first_ptr)->mln_Pred = last_l2;
 109             last_ptr               = &last_l2->mln_Succ;
 110         }
 111         else
 112         {
 113             (*first_ptr)->mln_Pred = (struct MinNode *)((char *)last_ptr -
 114                                      offsetof(struct MinNode, mln_Succ));
 115         }
 116
 117         l1 = *last_ptr = next_l;
 118     }
 119
 120     return first;
 121 }
 122
 123 /*****************************************************************************
 124
 125     NAME */
 126 #include <clib/alib_protos.h>
 127         void MergeSortList(
 128
 129 /*  SYNOPSIS */
 130         struct MinList *l,
 131         int (*compare)(struct MinNode *n1, struct MinNode *n2, void *data),
 132         void *data)
 133
 134 /*  FUNCTION
 135         Sorts an Exec-style doubly linked list, by using a variant of the merge sorting
 136         algorithm, which is Theta(n log n ). No additional space is required other than
 137         the one needed for local variables in the function itself. The function is not
 138         recursive.
 139
 140     INPUTS
 141        l       - The list to sort.
 142
 143        compare - Pointer to the comparison function which establishes the order
 144                  of the elements in the list
 145
 146        data    - Pointer to user-defined data which will be passed untouched
 147                  to the comparison function.
 148
 149     RESULT
 150         The given list, sorted in place.
 151
 152 ******************************************************************************/
 153 {
 154     struct MinNode *head = (struct MinNode *)GetHead(l);
 155     struct MinNode *tail = (struct MinNode *)GetTail(l);
 156
 157     struct MinNode *l1, *l2,
 158                    *first, **last_ptr;
 159
 160     if (!head || head == tail)
 161         return;
 162
 163     tail->mln_Succ = NULL;
 164     last_ptr = &first;
 165
 166     /* The Merge() function requires a list of sublists, each of which
 167        has to be a circular list. Since the given list doesn't have these
 168        properties, we need to divide the sorting algorithm in 2 parts:
 169
 170            1) we first go trough the list once, making every node's Pred pointer
 171               point to the node itself, so that the given list of n nodes is
 172               transformed in a list of n circular sublists. Here we do the merging
 173               "manually", without the help of the Merge() function, as we have to
 174               deal with just couples of nodes, thus we can do some extra optimization.
 175
 176            2) We then feed the resulting list to the Merge() function, as many times as
 177               it takes to the Merge() function to give back just one circular list, rather
 178               than a list of circular sublists: that will be our sorted list. */
 179
 180     /* This is the first part.  */
 181     l1 = head;
 182     l2 = l1->mln_Succ;
 183     do
 184     {
 185         /* It can happen that the 2 nodes are already in the right,
 186            order and thus we only need to make a circular list out
 187            of them, or their order needs to be reversed, but
 188            in either case, the below line is necessary, because:
 189
 190                1) In the first case, it serves to build the
 191                   circular list.
 192
 193                2) In the 2nd case, it does 1/4 of the job of
 194                   reversing the order of the nodes (the
 195                   other 3/4 are done inside the if block).  */
 196         l1->mln_Pred = l2;
 197
 198         if (compare(l1, l2, data) >= 0)
 199         {
 200             /* l2 comes before l1, so rearrange them and
 201                make a circular list out of them.  */
 202             l1->mln_Succ = l2->mln_Succ;
 203             l2->mln_Succ = l1;
 204             l2->mln_Pred = l1;
 205
 206             l1 = l2;
 207         }
 208
 209         *last_ptr = l1;
 210         last_ptr  = &l1->mln_Pred->mln_Succ;
 211         l1        = *last_ptr;
 212     } while (l1 && (l2 = l1->mln_Succ));
 213
 214     /* An orphan node? Add it at the end of the list of sublists and
 215        make a circular list out of it.  */
 216     if (l1)
 217     {
 218         l1->mln_Pred = l1;
 219         *last_ptr = l1;
 220     }
 221
 222     /* And this is the 2nd part.  */
 223     while (first->mln_Pred->mln_Succ)
 224         first = Merge(first, compare, data);
 225
 226     /* Now we fix up the list header */
 227     l->mlh_Head     = first;
 228     l->mlh_TailPred = first->mln_Pred;
 229     first->mln_Pred->mln_Succ = (struct MinNode *)&l->mlh_Tail;
 230     first->mln_Pred = (struct MinNode *)&l->mlh_Head;
 231 }