sort.c

   1 /*
   2  * sort_list: a stable sort for lists.
   3  *
   4  * Time complexity: O(n*log n)
   5  *   [assuming limited zero-element fragments]
   6  *
   7  * Space complexity: O(1).
   8  *
   9  * Stable: yes.
  10  */
  11
  12 #include "lib.h"
  13 #include <stdio.h>
  14 #include <stdlib.h>
  15 #include <string.h>
  16
  17 #undef PARANOIA
  18 #undef COVERAGE
  19
  20 #ifdef PARANOIA
  21 #include <assert.h>
  22 #else
  23 #define assert(x)
  24 #endif
  25
  26 #ifdef COVERAGE
  27 static unsigned char been_there[256];
  28 #define BEEN_THERE(_c)                                  \
  29   do {                                                  \
  30         if (!been_there[_c]) {                          \
  31                 been_there[_c] = 1;                     \
  32                 printf ("Been there: %c\n", _c);        \
  33         }                                               \
  34   } while (0)
  35 #else
  36 #define BEEN_THERE(_c) do { } while (0)
  37 #endif
  38
  39 // Sort one fragment.  LIST_NODE_NR (==29) is a bit too high for my
  40 // taste for something this simple.  But, hey, it's O(1).
  41 //
  42 // I would use libc qsort for this, but its comparison function
  43 // gets a pointer indirection extra.
  44 static void array_sort(void **ptr, int nr, int (*cmp)(const void *, const void *))
  45 {
  46         int i;
  47         for (i = 1; i < nr; i++) {
  48                 void *p = ptr[i];
  49                 if (cmp(ptr[i-1],p) > 0) {
  50                         int j = i;
  51                         do {
  52                                 ptr[j] = ptr[j-1];
  53                                 if (!--j)
  54                                         break;
  55                         } while (cmp(ptr[j-1], p) > 0);
  56                         ptr[j] = p;
  57                 }
  58         }
  59 }
  60
  61 #ifdef PARANOIA
  62 static void verify_seq_sorted (struct ptr_list *l, int n,
  63                                int (*cmp)(const void *, const void *))
  64 {
  65         int i = 0;
  66         const void *a;
  67         struct ptr_list *head = l;
  68
  69         while (l->nr == 0) {
  70                 l = l->next;
  71                 if (--n == 0)
  72                         return;
  73                 assert (l != head);
  74         }
  75
  76         a = l->list[0];
  77         while (n > 0) {
  78                 const void *b;
  79                 if (++i >= l->nr) {
  80                         i = 0;
  81                         l = l->next;
  82                         n--;
  83                         assert (l != head || n == 0);
  84                         continue;
  85                 }
  86                 b = l->list[i];
  87                 assert (cmp (a, b) <= 0);
  88                 a = b;
  89         }
  90 }
  91 #endif
  92
  93
  94 #define FLUSH_TO(b)                                             \
  95   do {                                                          \
  96         int nr = (b)->nr;                                       \
  97         assert (nbuf >= nr);                                    \
  98         memcpy ((b)->list, buffer, nr * sizeof (void *));       \
  99         nbuf -= nr;                                             \
 100         memcpy (buffer, buffer + nr, nbuf * sizeof (void *));   \
 101   } while (0)
 102
 103 #define DUMP_TO(b)                                              \
 104   do {                                                          \
 105         assert (nbuf <= (b)->nr);                               \
 106         memcpy ((b)->list, buffer, nbuf * sizeof (void *));     \
 107   } while (0)
 108
 109
 110 // Merge two already-sorted sequences of blocks:
 111 //   (b1_1, ..., b1_n)  and  (b2_1, ..., b2_m)
 112 // Since we may be moving blocks around, we return the new head
 113 // of the merged list.
 114 static struct ptr_list *
 115 merge_block_seqs (struct ptr_list *b1, int n,
 116                   struct ptr_list *b2, int m,
 117                   int (*cmp)(const void *, const void *))
 118 {
 119         int i1 = 0, i2 = 0;
 120         const void *buffer[2 * LIST_NODE_NR];
 121         int nbuf = 0;
 122         struct ptr_list *newhead = b1;
 123
 124         // printf ("Merging %d blocks at %p with %d blocks at %p\n", n, b1, m, b2);
 125
 126         // Skip empty blocks in b2.
 127         while (b2->nr == 0) {
 128                 BEEN_THERE('F');
 129                 b2 = b2->next;
 130                 if (--m == 0) {
 131                         BEEN_THERE('G');
 132                         return newhead;
 133                 }
 134         }
 135
 136         // Do a quick skip in case entire blocks from b1 are
 137         // already less than smallest element in b2.
 138         while (b1->nr == 0 ||
 139                cmp (b1->list[b1->nr - 1], b2->list[0]) < 0) {
 140                 // printf ("Skipping whole block.\n");
 141                 BEEN_THERE('H');
 142                 b1 = b1->next;
 143                 if (--n == 0) {
 144                         BEEN_THERE('I');
 145                         return newhead;
 146                 }
 147         }
 148
 149         while (1) {
 150                 const void *d1 = b1->list[i1];
 151                 const void *d2 = b2->list[i2];
 152
 153                 assert (i1 >= 0 && i1 < b1->nr);
 154                 assert (i2 >= 0 && i2 < b2->nr);
 155                 assert (b1 != b2);
 156                 assert (n > 0);
 157                 assert (m > 0);
 158
 159                 if (cmp (d1, d2) <= 0) {
 160                         BEEN_THERE('J');
 161                         buffer[nbuf++] = d1;
 162                         // Element from b1 is smaller
 163                         if (++i1 >= b1->nr) {
 164                                 BEEN_THERE('L');
 165                                 FLUSH_TO(b1);
 166                                 do {
 167                                         b1 = b1->next;
 168                                         if (--n == 0) {
 169                                                 BEEN_THERE('O');
 170                                                 while (b1 != b2) {
 171                                                         BEEN_THERE('P');
 172                                                         FLUSH_TO(b1);
 173                                                         b1 = b1->next;
 174                                                 }
 175                                                 assert (nbuf == i2);
 176                                                 DUMP_TO(b2);
 177                                                 return newhead;
 178                                         }
 179                                 } while (b1->nr == 0);
 180                                 i1 = 0;
 181                         }
 182                 } else {
 183                         BEEN_THERE('K');
 184                         // Element from b2 is smaller
 185                         buffer[nbuf++] = d2;
 186                         if (++i2 >= b2->nr) {
 187                                 BEEN_THERE('M');
 188                                 // Ok, we finished with b2.  Pull it out
 189                                 // and plug it in before b1.
 190                                 struct ptr_list *l = b2;
 191
 192                                 b2 = b2->next;
 193                                 b2->prev = l->prev;
 194                                 b2->prev->next = b2;
 195                                 l->next = b1;
 196                                 l->prev = b1->prev;
 197                                 l->next->prev = l;
 198                                 l->prev->next = l;
 199
 200                                 if (b1 == newhead) {
 201                                         BEEN_THERE('N');
 202                                         newhead = l;
 203                                 }
 204
 205                                 FLUSH_TO(l);
 206                                 b2 = b2->prev;
 207                                 do {
 208                                         b2 = b2->next;
 209                                         if (--m == 0) {
 210                                                 BEEN_THERE('Q');
 211                                                 assert (nbuf == i1);
 212                                                 DUMP_TO(b1);
 213                                                 return newhead;
 214                                         }
 215                                 } while (b2->nr == 0);
 216                                 i2 = 0;
 217                         }
 218                 }
 219         }
 220 }
 221
 222
 223 void sort_list(struct ptr_list **plist, int (*cmp)(const void *, const void *))
 224 {
 225         struct ptr_list *head = *plist;
 226         int blocks = 1;
 227
 228         if (!head)
 229                 return;
 230
 231         // Sort all the sub-lists
 232         struct ptr_list *list = head;
 233         do {
 234                 array_sort(list->list, list->nr, cmp);
 235 #ifdef PARANOIA
 236                 verify_seq_sorted (list, 1, cmp);
 237 #endif
 238                 list = list->next;
 239         } while (list != head);
 240
 241         // Merge the damn things together
 242         while (1) {
 243                 struct ptr_list *block1 = head;
 244
 245                 do {
 246                         struct ptr_list *block2 = block1;
 247                         struct ptr_list *next, *newhead;
 248                         int i;
 249
 250                         for (i = 0; i < blocks; i++) {
 251                                 block2 = block2->next;
 252                                 if (block2 == head) {
 253                                         if (block1 == head) {
 254                                                 BEEN_THERE('A');
 255                                                 *plist = head;
 256                                                 return;
 257                                         }
 258                                         BEEN_THERE('B');
 259                                         goto next_pass;
 260                                 }
 261                         }
 262
 263                         next = block2;
 264                         for (i = 0; i < blocks; ) {
 265                                 next = next->next;
 266                                 i++;
 267                                 if (next == head) {
 268                                         BEEN_THERE('C');
 269                                         break;
 270                                 }
 271                                 BEEN_THERE('D');
 272                         }
 273
 274                         newhead = merge_block_seqs (block1, blocks,
 275                                                     block2, i,
 276                                                     cmp);
 277 #ifdef PARANOIA
 278                         verify_seq_sorted (newhead, blocks + i, cmp);
 279 #endif
 280                         if (block1 == head) {
 281                                 BEEN_THERE('E');
 282                                 head = newhead;
 283                         }
 284                         block1 = next;
 285                 } while (block1 != head);
 286         next_pass:
 287                 blocks <<= 1;
 288         }
 289 }