ReactOS  0.4.15-dev-5142-g967f5b9
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 12 of file llmsort.c.

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 }
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
#define L(x)
Definition: ntvdm.h:50
GLuint base
Definition: 3dtext.c:35
int n1
Definition: dwarfget.c:148
#define index(s, c)
Definition: various.h:29
static unsigned __int64 next
Definition: rand_nt.c:6
#define NULL
Definition: types.h:112
static char * dest
Definition: rtl.c:135
GLfloat GLfloat p
Definition: glext.h:8902