tools/rgenstat/llmosrt.c

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