ReactOS  0.4.15-dev-494-g1d8c567
llmsort.c File Reference
#include <stdio.h>
Include dependency graph for llmsort.c:

Go to the source code of this file.

Functions

voidsort_linked_list (void *p, unsigned index, int(*compare)(void *, void *))
 

Function Documentation

◆ sort_linked_list()

void* sort_linked_list ( void p,
unsigned  index,
int(*)(void *, void *)  compare 
)

Definition at line 20 of file llmsort.c.

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 }
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
smooth NULL
Definition: ftsmooth.c:416
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