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 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