11f5207b7SJohn Levon /*
21f5207b7SJohn Levon * sort_list: a stable sort for lists.
31f5207b7SJohn Levon *
41f5207b7SJohn Levon * Time complexity: O(n*log n)
51f5207b7SJohn Levon * [assuming limited zero-element fragments]
61f5207b7SJohn Levon *
71f5207b7SJohn Levon * Space complexity: O(1).
81f5207b7SJohn Levon *
91f5207b7SJohn Levon * Stable: yes.
101f5207b7SJohn Levon */
111f5207b7SJohn Levon
121f5207b7SJohn Levon #include <stdio.h>
131f5207b7SJohn Levon #include <stdlib.h>
141f5207b7SJohn Levon #include <string.h>
151f5207b7SJohn Levon
161f5207b7SJohn Levon #include "lib.h"
171f5207b7SJohn Levon #include "allocate.h"
181f5207b7SJohn Levon
191f5207b7SJohn Levon #undef PARANOIA
201f5207b7SJohn Levon #undef COVERAGE
211f5207b7SJohn Levon
221f5207b7SJohn Levon #ifdef PARANOIA
231f5207b7SJohn Levon #include <assert.h>
241f5207b7SJohn Levon #else
251f5207b7SJohn Levon #define assert(x)
261f5207b7SJohn Levon #endif
271f5207b7SJohn Levon
281f5207b7SJohn Levon #ifdef COVERAGE
291f5207b7SJohn Levon static unsigned char been_there[256];
301f5207b7SJohn Levon #define BEEN_THERE(_c) \
311f5207b7SJohn Levon do { \
321f5207b7SJohn Levon if (!been_there[_c]) { \
331f5207b7SJohn Levon been_there[_c] = 1; \
341f5207b7SJohn Levon printf ("Been there: %c\n", _c); \
351f5207b7SJohn Levon } \
361f5207b7SJohn Levon } while (0)
371f5207b7SJohn Levon #else
381f5207b7SJohn Levon #define BEEN_THERE(_c) do { } while (0)
391f5207b7SJohn Levon #endif
401f5207b7SJohn Levon
411f5207b7SJohn Levon // Sort one fragment. LIST_NODE_NR (==29) is a bit too high for my
421f5207b7SJohn Levon // taste for something this simple. But, hey, it's O(1).
431f5207b7SJohn Levon //
441f5207b7SJohn Levon // I would use libc qsort for this, but its comparison function
451f5207b7SJohn Levon // gets a pointer indirection extra.
array_sort(void ** ptr,int nr,int (* cmp)(const void *,const void *))461f5207b7SJohn Levon static void array_sort(void **ptr, int nr, int (*cmp)(const void *, const void *))
471f5207b7SJohn Levon {
481f5207b7SJohn Levon int i;
491f5207b7SJohn Levon for (i = 1; i < nr; i++) {
501f5207b7SJohn Levon void *p = ptr[i];
511f5207b7SJohn Levon if (cmp(ptr[i-1],p) > 0) {
521f5207b7SJohn Levon int j = i;
531f5207b7SJohn Levon do {
541f5207b7SJohn Levon ptr[j] = ptr[j-1];
551f5207b7SJohn Levon if (!--j)
561f5207b7SJohn Levon break;
571f5207b7SJohn Levon } while (cmp(ptr[j-1], p) > 0);
581f5207b7SJohn Levon ptr[j] = p;
591f5207b7SJohn Levon }
601f5207b7SJohn Levon }
611f5207b7SJohn Levon }
621f5207b7SJohn Levon
631f5207b7SJohn Levon #ifdef PARANOIA
verify_seq_sorted(struct ptr_list * l,int n,int (* cmp)(const void *,const void *))641f5207b7SJohn Levon static void verify_seq_sorted (struct ptr_list *l, int n,
651f5207b7SJohn Levon int (*cmp)(const void *, const void *))
661f5207b7SJohn Levon {
671f5207b7SJohn Levon int i = 0;
681f5207b7SJohn Levon const void *a;
691f5207b7SJohn Levon struct ptr_list *head = l;
701f5207b7SJohn Levon
711f5207b7SJohn Levon while (l->nr == 0) {
721f5207b7SJohn Levon l = l->next;
731f5207b7SJohn Levon if (--n == 0)
741f5207b7SJohn Levon return;
751f5207b7SJohn Levon assert (l != head);
761f5207b7SJohn Levon }
771f5207b7SJohn Levon
781f5207b7SJohn Levon a = l->list[0];
791f5207b7SJohn Levon while (n > 0) {
801f5207b7SJohn Levon const void *b;
811f5207b7SJohn Levon if (++i >= l->nr) {
821f5207b7SJohn Levon i = 0;
831f5207b7SJohn Levon l = l->next;
841f5207b7SJohn Levon n--;
851f5207b7SJohn Levon assert (l != head || n == 0);
861f5207b7SJohn Levon continue;
871f5207b7SJohn Levon }
881f5207b7SJohn Levon b = l->list[i];
891f5207b7SJohn Levon assert (cmp (a, b) <= 0);
901f5207b7SJohn Levon a = b;
911f5207b7SJohn Levon }
921f5207b7SJohn Levon }
931f5207b7SJohn Levon #endif
941f5207b7SJohn Levon
951f5207b7SJohn Levon
961f5207b7SJohn Levon #define FLUSH_TO(b) \
971f5207b7SJohn Levon do { \
981f5207b7SJohn Levon int nr = (b)->nr; \
991f5207b7SJohn Levon assert (nbuf >= nr); \
1001f5207b7SJohn Levon memcpy ((b)->list, buffer, nr * sizeof (void *)); \
1011f5207b7SJohn Levon nbuf -= nr; \
1021f5207b7SJohn Levon memmove (buffer, buffer + nr, nbuf * sizeof (void *)); \
1031f5207b7SJohn Levon } while (0)
1041f5207b7SJohn Levon
1051f5207b7SJohn Levon #define DUMP_TO(b) \
1061f5207b7SJohn Levon do { \
1071f5207b7SJohn Levon assert (nbuf <= (b)->nr); \
1081f5207b7SJohn Levon memcpy ((b)->list, buffer, nbuf * sizeof (void *)); \
1091f5207b7SJohn Levon } while (0)
1101f5207b7SJohn Levon
1111f5207b7SJohn Levon
1121f5207b7SJohn Levon // Merge two already-sorted sequences of blocks:
1131f5207b7SJohn Levon // (b1_1, ..., b1_n) and (b2_1, ..., b2_m)
1141f5207b7SJohn Levon // Since we may be moving blocks around, we return the new head
1151f5207b7SJohn Levon // of the merged list.
1161f5207b7SJohn Levon static struct ptr_list *
merge_block_seqs(struct ptr_list * b1,int n,struct ptr_list * b2,int m,int (* cmp)(const void *,const void *))1171f5207b7SJohn Levon merge_block_seqs (struct ptr_list *b1, int n,
1181f5207b7SJohn Levon struct ptr_list *b2, int m,
1191f5207b7SJohn Levon int (*cmp)(const void *, const void *))
1201f5207b7SJohn Levon {
1211f5207b7SJohn Levon int i1 = 0, i2 = 0;
1221f5207b7SJohn Levon const void *buffer[2 * LIST_NODE_NR];
1231f5207b7SJohn Levon int nbuf = 0;
1241f5207b7SJohn Levon struct ptr_list *newhead = b1;
1251f5207b7SJohn Levon
1261f5207b7SJohn Levon // printf ("Merging %d blocks at %p with %d blocks at %p\n", n, b1, m, b2);
1271f5207b7SJohn Levon
1281f5207b7SJohn Levon // Skip empty blocks in b2.
1291f5207b7SJohn Levon while (b2->nr == 0) {
1301f5207b7SJohn Levon BEEN_THERE('F');
1311f5207b7SJohn Levon b2 = b2->next;
1321f5207b7SJohn Levon if (--m == 0) {
1331f5207b7SJohn Levon BEEN_THERE('G');
1341f5207b7SJohn Levon return newhead;
1351f5207b7SJohn Levon }
1361f5207b7SJohn Levon }
1371f5207b7SJohn Levon
1381f5207b7SJohn Levon // Do a quick skip in case entire blocks from b1 are
1391f5207b7SJohn Levon // already less than smallest element in b2.
1401f5207b7SJohn Levon while (b1->nr == 0 ||
141*c85f09ccSJohn Levon cmp (PTR_ENTRY_NOTAG(b1, b1->nr - 1), PTR_ENTRY_NOTAG(b2,0)) < 0) {
1421f5207b7SJohn Levon // printf ("Skipping whole block.\n");
1431f5207b7SJohn Levon BEEN_THERE('H');
1441f5207b7SJohn Levon b1 = b1->next;
1451f5207b7SJohn Levon if (--n == 0) {
1461f5207b7SJohn Levon BEEN_THERE('I');
1471f5207b7SJohn Levon return newhead;
1481f5207b7SJohn Levon }
1491f5207b7SJohn Levon }
1501f5207b7SJohn Levon
1511f5207b7SJohn Levon while (1) {
152*c85f09ccSJohn Levon const void *d1 = PTR_ENTRY_NOTAG(b1,i1);
153*c85f09ccSJohn Levon const void *d2 = PTR_ENTRY_NOTAG(b2,i2);
1541f5207b7SJohn Levon
1551f5207b7SJohn Levon assert (i1 >= 0 && i1 < b1->nr);
1561f5207b7SJohn Levon assert (i2 >= 0 && i2 < b2->nr);
1571f5207b7SJohn Levon assert (b1 != b2);
1581f5207b7SJohn Levon assert (n > 0);
1591f5207b7SJohn Levon assert (m > 0);
1601f5207b7SJohn Levon
1611f5207b7SJohn Levon if (cmp (d1, d2) <= 0) {
1621f5207b7SJohn Levon BEEN_THERE('J');
1631f5207b7SJohn Levon buffer[nbuf++] = d1;
1641f5207b7SJohn Levon // Element from b1 is smaller
1651f5207b7SJohn Levon if (++i1 >= b1->nr) {
1661f5207b7SJohn Levon BEEN_THERE('L');
1671f5207b7SJohn Levon FLUSH_TO(b1);
1681f5207b7SJohn Levon do {
1691f5207b7SJohn Levon b1 = b1->next;
1701f5207b7SJohn Levon if (--n == 0) {
1711f5207b7SJohn Levon BEEN_THERE('O');
1721f5207b7SJohn Levon while (b1 != b2) {
1731f5207b7SJohn Levon BEEN_THERE('P');
1741f5207b7SJohn Levon FLUSH_TO(b1);
1751f5207b7SJohn Levon b1 = b1->next;
1761f5207b7SJohn Levon }
1771f5207b7SJohn Levon assert (nbuf == i2);
1781f5207b7SJohn Levon DUMP_TO(b2);
1791f5207b7SJohn Levon return newhead;
1801f5207b7SJohn Levon }
1811f5207b7SJohn Levon } while (b1->nr == 0);
1821f5207b7SJohn Levon i1 = 0;
1831f5207b7SJohn Levon }
1841f5207b7SJohn Levon } else {
1851f5207b7SJohn Levon BEEN_THERE('K');
1861f5207b7SJohn Levon // Element from b2 is smaller
1871f5207b7SJohn Levon buffer[nbuf++] = d2;
1881f5207b7SJohn Levon if (++i2 >= b2->nr) {
1891f5207b7SJohn Levon struct ptr_list *l = b2;
1901f5207b7SJohn Levon BEEN_THERE('M');
1911f5207b7SJohn Levon // OK, we finished with b2. Pull it out
1921f5207b7SJohn Levon // and plug it in before b1.
1931f5207b7SJohn Levon
1941f5207b7SJohn Levon b2 = b2->next;
1951f5207b7SJohn Levon b2->prev = l->prev;
1961f5207b7SJohn Levon b2->prev->next = b2;
1971f5207b7SJohn Levon l->next = b1;
1981f5207b7SJohn Levon l->prev = b1->prev;
1991f5207b7SJohn Levon l->next->prev = l;
2001f5207b7SJohn Levon l->prev->next = l;
2011f5207b7SJohn Levon
2021f5207b7SJohn Levon if (b1 == newhead) {
2031f5207b7SJohn Levon BEEN_THERE('N');
2041f5207b7SJohn Levon newhead = l;
2051f5207b7SJohn Levon }
2061f5207b7SJohn Levon
2071f5207b7SJohn Levon FLUSH_TO(l);
2081f5207b7SJohn Levon b2 = b2->prev;
2091f5207b7SJohn Levon do {
2101f5207b7SJohn Levon b2 = b2->next;
2111f5207b7SJohn Levon if (--m == 0) {
2121f5207b7SJohn Levon BEEN_THERE('Q');
2131f5207b7SJohn Levon assert (nbuf == i1);
2141f5207b7SJohn Levon DUMP_TO(b1);
2151f5207b7SJohn Levon return newhead;
2161f5207b7SJohn Levon }
2171f5207b7SJohn Levon } while (b2->nr == 0);
2181f5207b7SJohn Levon i2 = 0;
2191f5207b7SJohn Levon }
2201f5207b7SJohn Levon }
2211f5207b7SJohn Levon }
2221f5207b7SJohn Levon }
2231f5207b7SJohn Levon
2241f5207b7SJohn Levon
sort_list(struct ptr_list ** plist,int (* cmp)(const void *,const void *))2251f5207b7SJohn Levon void sort_list(struct ptr_list **plist, int (*cmp)(const void *, const void *))
2261f5207b7SJohn Levon {
2271f5207b7SJohn Levon struct ptr_list *head = *plist, *list = head;
2281f5207b7SJohn Levon int blocks = 1;
2291f5207b7SJohn Levon
2301f5207b7SJohn Levon if (!head)
2311f5207b7SJohn Levon return;
2321f5207b7SJohn Levon
2331f5207b7SJohn Levon // Sort all the sub-lists
2341f5207b7SJohn Levon do {
2351f5207b7SJohn Levon array_sort(list->list, list->nr, cmp);
2361f5207b7SJohn Levon #ifdef PARANOIA
2371f5207b7SJohn Levon verify_seq_sorted (list, 1, cmp);
2381f5207b7SJohn Levon #endif
2391f5207b7SJohn Levon list = list->next;
2401f5207b7SJohn Levon } while (list != head);
2411f5207b7SJohn Levon
2421f5207b7SJohn Levon // Merge the damn things together
2431f5207b7SJohn Levon while (1) {
2441f5207b7SJohn Levon struct ptr_list *block1 = head;
2451f5207b7SJohn Levon
2461f5207b7SJohn Levon do {
2471f5207b7SJohn Levon struct ptr_list *block2 = block1;
2481f5207b7SJohn Levon struct ptr_list *next, *newhead;
2491f5207b7SJohn Levon int i;
2501f5207b7SJohn Levon
2511f5207b7SJohn Levon for (i = 0; i < blocks; i++) {
2521f5207b7SJohn Levon block2 = block2->next;
2531f5207b7SJohn Levon if (block2 == head) {
2541f5207b7SJohn Levon if (block1 == head) {
2551f5207b7SJohn Levon BEEN_THERE('A');
2561f5207b7SJohn Levon *plist = head;
2571f5207b7SJohn Levon return;
2581f5207b7SJohn Levon }
2591f5207b7SJohn Levon BEEN_THERE('B');
2601f5207b7SJohn Levon goto next_pass;
2611f5207b7SJohn Levon }
2621f5207b7SJohn Levon }
2631f5207b7SJohn Levon
2641f5207b7SJohn Levon next = block2;
2651f5207b7SJohn Levon for (i = 0; i < blocks; ) {
2661f5207b7SJohn Levon next = next->next;
2671f5207b7SJohn Levon i++;
2681f5207b7SJohn Levon if (next == head) {
2691f5207b7SJohn Levon BEEN_THERE('C');
2701f5207b7SJohn Levon break;
2711f5207b7SJohn Levon }
2721f5207b7SJohn Levon BEEN_THERE('D');
2731f5207b7SJohn Levon }
2741f5207b7SJohn Levon
2751f5207b7SJohn Levon newhead = merge_block_seqs (block1, blocks,
2761f5207b7SJohn Levon block2, i,
2771f5207b7SJohn Levon cmp);
2781f5207b7SJohn Levon #ifdef PARANOIA
2791f5207b7SJohn Levon verify_seq_sorted (newhead, blocks + i, cmp);
2801f5207b7SJohn Levon #endif
2811f5207b7SJohn Levon if (block1 == head) {
2821f5207b7SJohn Levon BEEN_THERE('E');
2831f5207b7SJohn Levon head = newhead;
2841f5207b7SJohn Levon }
2851f5207b7SJohn Levon block1 = next;
2861f5207b7SJohn Levon } while (block1 != head);
2871f5207b7SJohn Levon next_pass:
2881f5207b7SJohn Levon blocks <<= 1;
2891f5207b7SJohn Levon }
2901f5207b7SJohn Levon }
291