ReactOS  0.4.15-dev-341-g17c5fb8
llmsort.c
Go to the documentation of this file.
1 /*
2  * A Linked-List Memory Sort
3  * by Philip J. Erdelsky
4  * pje@acm.org
5  * pje@efgh.com
6  * http://alumnus.caltech.edu/~pje/
7  *
8  * Version taken from:
9  * http://alumnus.caltech.edu/~pje/cdmake.txt
10  *
11  * An extended version can be found at:
12  * http://alumnus.caltech.edu/~pje/llmsort.html
13  * http://www.efgh.com/software/llmsort.htm
14  *
15  * Public domain; no restrictions on use.
16  */
17 
18 #include <stdio.h>
19 
20 void *sort_linked_list(void *p, unsigned index, int (*compare)(void *, void *))
21 {
22  unsigned base;
23  unsigned long block_size;
24 
25  struct record
26  {
27  struct record *next[1];
28  /* other members not directly accessed by this function */
29  };
30 
31  struct tape
32  {
33  struct record *first, *last;
34  unsigned long count;
35  } tape[4];
36 
37  /* Distribute the records alternately to tape[0] and tape[1]. */
38 
39  tape[0].count = tape[1].count = 0L;
40  tape[0].first = NULL;
41  base = 0;
42  while (p != NULL)
43  {
44  struct record *next = ((struct record *)p)->next[index];
45  ((struct record *)p)->next[index] = tape[base].first;
46  tape[base].first = ((struct record *)p);
47  tape[base].count++;
48  p = next;
49  base ^= 1;
50  }
51 
52  /* If the list is empty or contains only a single record, then */
53  /* tape[1].count == 0L and this part is vacuous. */
54 
55  for (base = 0, block_size = 1L; tape[base+1].count != 0L;
56  base ^= 2, block_size <<= 1)
57  {
58  int dest;
59  struct tape *tape0, *tape1;
60  tape0 = tape + base;
61  tape1 = tape + base + 1;
62  dest = base ^ 2;
63  tape[dest].count = tape[dest+1].count = 0;
64  for (; tape0->count != 0; dest ^= 1)
65  {
66  unsigned long n0, n1;
67  struct tape *output_tape = tape + dest;
68  n0 = n1 = block_size;
69  while (1)
70  {
71  struct record *chosen_record;
72  struct tape *chosen_tape;
73  if (n0 == 0 || tape0->count == 0)
74  {
75  if (n1 == 0 || tape1->count == 0)
76  break;
77  chosen_tape = tape1;
78  n1--;
79  }
80  else if (n1 == 0 || tape1->count == 0)
81  {
82  chosen_tape = tape0;
83  n0--;
84  }
85  else if ((*compare)(tape0->first, tape1->first) > 0)
86  {
87  chosen_tape = tape1;
88  n1--;
89  }
90  else
91  {
92  chosen_tape = tape0;
93  n0--;
94  }
95  chosen_tape->count--;
96  chosen_record = chosen_tape->first;
97  chosen_tape->first = chosen_record->next[index];
98  if (output_tape->count == 0)
99  output_tape->first = chosen_record;
100  else
101  output_tape->last->next[index] = chosen_record;
102  output_tape->last = chosen_record;
103  output_tape->count++;
104  }
105  }
106  }
107 
108  if (tape[base].count > 1L)
109  tape[base].last->next[index] = NULL;
110  return tape[base].first;
111 }
112 
113 /* EOF */
Definition: bug.cpp:7
POINT last
Definition: font.c:46
GLuint GLuint GLsizei count
Definition: gl.h:1545
const GLint * first
Definition: glext.h:5794
static DWORD block_size(DWORD block)
Definition: jsutils.c:66
GLuint base
Definition: 3dtext.c:35
void * sort_linked_list(void *p, unsigned index, int(*compare)(void *, void *))
Definition: llmsort.c:20
smooth NULL
Definition: ftsmooth.c:416
GLuint index
Definition: glext.h:6031
int n1
Definition: dwarfget.c:148
#define index(s, c)
Definition: various.h:29
static const WCHAR L[]
Definition: oid.c:1250
static unsigned __int64 next
Definition: rand_nt.c:6
static char * dest
Definition: rtl.c:135
GLfloat GLfloat p
Definition: glext.h:8902