mirror of
https://github.com/reactos/reactos.git
synced 2024-06-30 09:50:07 +00:00
106 lines
3 KiB
C
106 lines
3 KiB
C
/*
|
|
* A Linked-List Memory Sort
|
|
* by Philip J. Erdelsky
|
|
* pje@acm.org
|
|
* http://alumnus.caltech.edu/~pje/
|
|
*/
|
|
|
|
/* According to his website, this file was released into the public domain by Philip J. Erdelsky */
|
|
|
|
#include <stdio.h>
|
|
|
|
void *sort_linked_list(void *p, unsigned index, int (*compare)(void *, void *))
|
|
{
|
|
unsigned base;
|
|
unsigned long block_size;
|
|
|
|
struct record
|
|
{
|
|
struct record *next[1];
|
|
/* other members not directly accessed by this function */
|
|
};
|
|
|
|
struct tape
|
|
{
|
|
struct record *first, *last;
|
|
unsigned long count;
|
|
} tape[4];
|
|
|
|
/* Distribute the records alternately to tape[0] and tape[1]. */
|
|
|
|
tape[0].count = tape[1].count = 0L;
|
|
tape[0].first = NULL;
|
|
base = 0;
|
|
while (p != NULL)
|
|
{
|
|
struct record *next = ((struct record *)p)->next[index];
|
|
((struct record *)p)->next[index] = tape[base].first;
|
|
tape[base].first = ((struct record *)p);
|
|
tape[base].count++;
|
|
p = next;
|
|
base ^= 1;
|
|
}
|
|
|
|
/* If the list is empty or contains only a single record, then */
|
|
/* tape[1].count == 0L and this part is vacuous. */
|
|
|
|
for (base = 0, block_size = 1L; tape[base+1].count != 0L;
|
|
base ^= 2, block_size <<= 1)
|
|
{
|
|
int dest;
|
|
struct tape *tape0, *tape1;
|
|
tape0 = tape + base;
|
|
tape1 = tape + base + 1;
|
|
dest = base ^ 2;
|
|
tape[dest].count = tape[dest+1].count = 0;
|
|
for (; tape0->count != 0; dest ^= 1)
|
|
{
|
|
unsigned long n0, n1;
|
|
struct tape *output_tape = tape + dest;
|
|
n0 = n1 = block_size;
|
|
while (1)
|
|
{
|
|
struct record *chosen_record;
|
|
struct tape *chosen_tape;
|
|
if (n0 == 0 || tape0->count == 0)
|
|
{
|
|
if (n1 == 0 || tape1->count == 0)
|
|
break;
|
|
chosen_tape = tape1;
|
|
n1--;
|
|
}
|
|
else if (n1 == 0 || tape1->count == 0)
|
|
{
|
|
chosen_tape = tape0;
|
|
n0--;
|
|
}
|
|
else if ((*compare)(tape0->first, tape1->first) > 0)
|
|
{
|
|
chosen_tape = tape1;
|
|
n1--;
|
|
}
|
|
else
|
|
{
|
|
chosen_tape = tape0;
|
|
n0--;
|
|
}
|
|
chosen_tape->count--;
|
|
chosen_record = chosen_tape->first;
|
|
chosen_tape->first = chosen_record->next[index];
|
|
if (output_tape->count == 0)
|
|
output_tape->first = chosen_record;
|
|
else
|
|
output_tape->last->next[index] = chosen_record;
|
|
output_tape->last = chosen_record;
|
|
output_tape->count++;
|
|
}
|
|
}
|
|
}
|
|
|
|
if (tape[base].count > 1L)
|
|
tape[base].last->next[index] = NULL;
|
|
return tape[base].first;
|
|
}
|
|
|
|
/* EOF */
|