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