1 /*
2 * A Linked-List Memory Sort
3 * by Philip J. Erdelsky
4 * pje@acm.org
5 * http://alumnus.caltech.edu/~pje/
6 */
7
8 /* According to his website, this file was released into the public domain by Philip J. Erdelsky */
9
10 #include <stdio.h>
11
sort_linked_list(void * p,unsigned index,int (* compare)(void *,void *))12 void *sort_linked_list(void *p, unsigned index, int (*compare)(void *, void *))
13 {
14 unsigned base;
15 unsigned long block_size;
16
17 struct record
18 {
19 struct record *next[1];
20 /* other members not directly accessed by this function */
21 };
22
23 struct tape
24 {
25 struct record *first, *last;
26 unsigned long count;
27 } tape[4];
28
29 /* Distribute the records alternately to tape[0] and tape[1]. */
30
31 tape[0].count = tape[1].count = 0L;
32 tape[0].first = NULL;
33 base = 0;
34 while (p != NULL)
35 {
36 struct record *next = ((struct record *)p)->next[index];
37 ((struct record *)p)->next[index] = tape[base].first;
38 tape[base].first = ((struct record *)p);
39 tape[base].count++;
40 p = next;
41 base ^= 1;
42 }
43
44 /* If the list is empty or contains only a single record, then */
45 /* tape[1].count == 0L and this part is vacuous. */
46
47 for (base = 0, block_size = 1L; tape[base+1].count != 0L;
48 base ^= 2, block_size <<= 1)
49 {
50 int dest;
51 struct tape *tape0, *tape1;
52 tape0 = tape + base;
53 tape1 = tape + base + 1;
54 dest = base ^ 2;
55 tape[dest].count = tape[dest+1].count = 0;
56 for (; tape0->count != 0; dest ^= 1)
57 {
58 unsigned long n0, n1;
59 struct tape *output_tape = tape + dest;
60 n0 = n1 = block_size;
61 while (1)
62 {
63 struct record *chosen_record;
64 struct tape *chosen_tape;
65 if (n0 == 0 || tape0->count == 0)
66 {
67 if (n1 == 0 || tape1->count == 0)
68 break;
69 chosen_tape = tape1;
70 n1--;
71 }
72 else if (n1 == 0 || tape1->count == 0)
73 {
74 chosen_tape = tape0;
75 n0--;
76 }
77 else if ((*compare)(tape0->first, tape1->first) > 0)
78 {
79 chosen_tape = tape1;
80 n1--;
81 }
82 else
83 {
84 chosen_tape = tape0;
85 n0--;
86 }
87 chosen_tape->count--;
88 chosen_record = chosen_tape->first;
89 chosen_tape->first = chosen_record->next[index];
90 if (output_tape->count == 0)
91 output_tape->first = chosen_record;
92 else
93 output_tape->last->next[index] = chosen_record;
94 output_tape->last = chosen_record;
95 output_tape->count++;
96 }
97 }
98 }
99
100 if (tape[base].count > 1L)
101 tape[base].last->next[index] = NULL;
102 return tape[base].first;
103 }
104
105 /* EOF */
106