Aware: fast_merge_sort.h Source File

00001 /*
00002 
00003    A macro to sort linked lists efficiently.
00004    O(n log n) worst case, O(n) on nearly sorted lists.
00005 
00006    Copyright (C) 1995, 1996, 1999 Jamie Lokier.
00007 
00008    This program is free software; you can redistribute it and/or modify
00009    it under the terms of the GNU General Public License as published by
00010    the Free Software Foundation; either version 2 of the License, or
00011    (at your option) any later version.
00012 
00013    This program is distributed in the hope that it will be useful,
00014    but WITHOUT ANY WARRANTY; without even the implied warranty of
00015    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00016    GNU General Public License for more details.
00017 
00018    You should have received a copy of the GNU General Public License
00019    along with this program; if not, write to the Free Software
00020    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 
00021 */
00022 
00023 #ifndef __fast_merge_sort_h
00024 #define __fast_merge_sort_h
00025 
00026 /* {{{ Description */
00027 
00176 /* }}} */
00177 
00178 
00179 #if !defined(__GNUC__) || defined(__STRICT_ANSI__)
00180 #define FAST_MERGE_SORT(__LIST, __TYPE, __NEXT, __LESS_THAN_OR_EQUAL_P) \
00181   __FAST_MERGE_SORT(1, 0, __LIST, __TYPE, __NEXT, __LESS_THAN_OR_EQUAL_P)
00182 #define FAST_MERGE_SORT_APPEND(__ALREADY_SORTED, __LIST,                \
00183                                __TYPE, __NEXT, __LESS_THAN_OR_EQUAL_P)  \
00184   __FAST_MERGE_SORT(0, __ALREADY_SORTED, __LIST,                        \
00185                     __TYPE, __NEXT, __LESS_THAN_OR_EQUAL_P)
00186 #define __FAST_MERGE_SORT_LABEL(name) \
00187   __FAST_MERGE_SORT_LABEL2 (name,__LINE__)
00188 #define __FAST_MERGE_SORT_LABEL2(name,line) \
00189   __FAST_MERGE_SORT_LABEL3 (name,line)
00190 #ifdef __STDC__
00191 #define __FAST_MERGE_SORT_LABEL3(name,line) \
00192   __FAST_MERGE_SORT_ ## name ## _ ## line
00193 #else
00194 #define __FAST_MERGE_SORT_LABEL3(name,line) \
00195   __FAST_MERGE_SORT_name_line
00196 #endif
00197 #else
00198 #define FAST_MERGE_SORT(__LIST, __TYPE, __NEXT, __LESS_THAN_OR_EQUAL_P)       \
00199   do ({                                                                       \
00200     __label__ __merge_1, __merge_2, __merge_done, __final_merge, __empty_list;\
00201     __FAST_MERGE_SORT(1, 0, __LIST, __TYPE, __NEXT, __LESS_THAN_OR_EQUAL_P);  \
00202   }); while (0)
00203 #define FAST_MERGE_SORT_APPEND(__ALREADY_SORTED, __LIST,                      \
00204                                __TYPE, __NEXT, __LESS_THAN_OR_EQUAL_P)        \
00205   do ({                                                                       \
00206     __label__ __merge_1, __merge_2, __merge_done, __final_merge, __empty_list;\
00207     __FAST_MERGE_SORT(0, __ALREADY_SORTED, __LIST,                            \
00208                       __TYPE, __NEXT, __LESS_THAN_OR_EQUAL_P);                \
00209   }); while (0)
00210 #define __FAST_MERGE_SORT_LABEL(name) __ ## name
00211 #endif
00212 
00213 #define __FAST_MERGE_SORT\
00214 (__ASG, __ALREADY_SORTED, __LIST, __NODE_TYPE, __NEXT, __LESS_THAN_OR_EQUAL_P)\
00215   do                                                                        \
00216     {                                                                       \
00217       __NODE_TYPE * _stack [8 * sizeof (unsigned long)];                    \
00218       __NODE_TYPE ** _stack_ptr           = _stack;                         \
00219       unsigned long _run_number           = 0UL - 1;                        \
00220       register __NODE_TYPE * _list        = (__LIST);                       \
00221       register __NODE_TYPE * _current_run = (__ALREADY_SORTED);             \
00222                                                                             \
00223       /* Handle zero length separately. */                                  \
00224       if (__ASG && (_list == 0 || _list->__NEXT == 0))                      \
00225         break;                                                              \
00226       if (!__ASG && _list == 0)                                             \
00227         goto __FAST_MERGE_SORT_LABEL (empty_list);                          \
00228                                                                             \
00229       while (_list != 0)                                                    \
00230         {                                                                   \
00231           /* Identify a run.  Ensure that the run is at least three         \
00232              elements long, if there are three elements.  Rearrange them    \
00233              to be in order, if necessary. */                               \
00234           *_stack_ptr++ = _current_run;                                     \
00235           _current_run = _list;                                             \
00236                                                                             \
00237           /* This conditional makes the runs at least 2 long. */            \
00238           if (_list->__NEXT != 0)                                           \
00239             {                                                               \
00240               if (__LESS_THAN_OR_EQUAL_P (_list, (_list->__NEXT)))          \
00241                 _list = _list->__NEXT;                                      \
00242               else                                                          \
00243                 {                                                           \
00244                   /* Exchange the first two elements. */                    \
00245                   _current_run = _list->__NEXT;                             \
00246                   _list->__NEXT = _current_run->__NEXT;                     \
00247                   _current_run->__NEXT = _list;                             \
00248                 }                                                           \
00249                                                                             \
00250               /* This conditional makes the runs at least 3 long. */        \
00251               if (_list->__NEXT != 0)                                       \
00252                 {                                                           \
00253                   if (__LESS_THAN_OR_EQUAL_P (_list, _list->__NEXT))        \
00254                     _list = _list->__NEXT;                                  \
00255                   else                                                      \
00256                     {                                                       \
00257                       /* Move the third element back to the right place. */ \
00258                       __NODE_TYPE * _tmp = _list->__NEXT;                   \
00259                       _list->__NEXT = _tmp->__NEXT;                         \
00260                                                                             \
00261                       if (__LESS_THAN_OR_EQUAL_P (_current_run, _tmp))      \
00262                         {                                                   \
00263                           _tmp->__NEXT = _list;                             \
00264                           _current_run->__NEXT = _tmp;                      \
00265                         }                                                   \
00266                       else                                                  \
00267                         {                                                   \
00268                           _tmp->__NEXT = _current_run;                      \
00269                           _current_run->__NEXT = _list;                     \
00270                           _current_run = _tmp;                              \
00271                         }                                                   \
00272                     }                                                       \
00273                                                                             \
00274                   /* Find more ascending elements. */                       \
00275                   while (_list->__NEXT != 0                                 \
00276                          && __LESS_THAN_OR_EQUAL_P (_list,                  \
00277                                                     (_list->__NEXT)))       \
00278                     _list = _list->__NEXT;                                  \
00279                 }                                                           \
00280             }                                                               \
00281                                                                             \
00282           {                                                                 \
00283             __NODE_TYPE * _tmp = _list->__NEXT;                             \
00284             _list->__NEXT = 0;                                              \
00285             _list = _tmp;                                                   \
00286           }                                                                 \
00287                                                                             \
00288           /* Half the runs are pushed onto the stack without being          \
00289              merged until another run has been found.  Test for that        \
00290              here to keep this bit of the loop fast. */                     \
00291                                                                             \
00292           if (!(++_run_number & 1))                                         \
00293             continue;                                                       \
00294                                                                             \
00295           /* Now merge the appropriate number of times.  The idea is to     \
00296              merge pairs of runs, then pairs of those merged pairs, and     \
00297              so on.  One strategy is to store a "merge depth" with each     \
00298              stack entry, indicating the number of merge operations done    \
00299              to produce that entry, and only merge the current run with     \
00300              the top one if they have the same merge depth.  Another is     \
00301              to count the number of runs identified so far, and work out    \
00302              what to do from that count.  The latter strategy is            \
00303              implemented here.                                              \
00304                                                                             \
00305              The sequence 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,      \
00306              4, etc. is the number of merge operations to do after each     \
00307              run has been identified.  That number is the same as the       \
00308              number of consecutive `1' bits at the bottom of                \
00309              `_run_number' here. */                                         \
00310                                                                             \
00311         __FAST_MERGE_SORT_LABEL (final_merge):                              \
00312           {                                                                 \
00313             unsigned long _tmp_run_number = _run_number;                    \
00314                                                                             \
00315             do                                                              \
00316               {                                                             \
00317                 /* Here, merge `_current_run' with the one on top of the    \
00318                    stack.  The new run is stored in `_current_run'.  The    \
00319                    order of arguments to the comparison function is         \
00320                    important, in order for the sort to be stable.  The      \
00321                    run on the stack was earlier in the original list        \
00322                    than `_current_run'.                                     \
00323                                                                             \
00324                    Two loops are used mainly to reduce the number of        \
00325                    memory writes.  They also bias the loops to run          \
00326                    quickest where contiguous elements are taken from the    \
00327                    same input list. */                                      \
00328                                                                             \
00329                 register __NODE_TYPE * _other_run   = *--_stack_ptr;        \
00330                 __NODE_TYPE * _output_run           = _other_run;           \
00331                 register __NODE_TYPE ** _output_ptr = &_output_run;         \
00332                                                                             \
00333                 for (;;)                                                    \
00334                   {                                                         \
00335                     if (__LESS_THAN_OR_EQUAL_P (_other_run, _current_run))  \
00336                       {                                                     \
00337                       __FAST_MERGE_SORT_LABEL (merge_1):                    \
00338                         _output_ptr = &_other_run->__NEXT;                  \
00339                         _other_run = *_output_ptr;                          \
00340                         if (_other_run != 0)                                \
00341                           continue;                                         \
00342                         *_output_ptr = _current_run;                        \
00343                         goto __FAST_MERGE_SORT_LABEL (merge_done);          \
00344                       }                                                     \
00345                     *_output_ptr = _current_run;                            \
00346                     goto __FAST_MERGE_SORT_LABEL (merge_2);                 \
00347                   }                                                         \
00348                                                                             \
00349                 /* The body of this loop is only reached by jumping         \
00350                    into it. */                                              \
00351                                                                             \
00352                 for (;;)                                                    \
00353                   {                                                         \
00354                     if (!__LESS_THAN_OR_EQUAL_P (_other_run, _current_run)) \
00355                       {                                                     \
00356                       __FAST_MERGE_SORT_LABEL (merge_2):                    \
00357                         _output_ptr = &_current_run->__NEXT;                \
00358                         _current_run = *_output_ptr;                        \
00359                         if (_current_run != 0)                              \
00360                           continue;                                         \
00361                         *_output_ptr = _other_run;                          \
00362                         goto __FAST_MERGE_SORT_LABEL (merge_done);          \
00363                       }                                                     \
00364                     *_output_ptr = _other_run;                              \
00365                     goto __FAST_MERGE_SORT_LABEL (merge_1);                 \
00366                   }                                                         \
00367                                                                             \
00368               __FAST_MERGE_SORT_LABEL (merge_done):                         \
00369                 _current_run = _output_run;                                 \
00370               }                                                             \
00371             while ((_tmp_run_number >>= 1) & 1);                            \
00372           }                                                                 \
00373         }                                                                   \
00374                                                                             \
00375       /* There are no more runs in the input list now.  Just merge runs     \
00376          on the stack together until there is only one.  Keep the code      \
00377          small by using the merge code in the main loop.  These tests       \
00378          are outside the main loop to keep the main loop as fast and        \
00379          small as possible.  This jumps to a point which shouldn't          \
00380          disrupt the quality of the main loop's compiled code too           \
00381          much. */                                                           \
00382                                                                             \
00383       _run_number = (1UL << (_stack_ptr                                     \
00384                              - (_stack + (__ASG || _stack [0] == 0)))) - 1; \
00385       if (_run_number)                                                      \
00386         goto __FAST_MERGE_SORT_LABEL (final_merge);                         \
00387                                                                             \
00388     __FAST_MERGE_SORT_LABEL (empty_list):                                   \
00389       (__LIST) = _current_run;                                              \
00390     }                                                                       \
00391   while (0)
00392 
00393 #endif /* __fast_merge_sort_h */
00394