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