zcurve/list_sort.c at master · bmuratshin/zcurve · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/*
 * contrib/zcurve/list_sort.c
 *
 *
 * list_sort.c -- a kind of mergesort for a generic list
 *
 *
 * Modified by Boris Muratshin, mailto:bmuratshin@gmail.com
 */
#include "postgres.h"
#include "list_sort.h"

static gen_list_t *
intersect_sorted(
	gen_list_t * plist1,
	gen_list_t * plist2,
	int (*compare_proc) (const void *, const void *, const void *),
	const void *arg)
{
	gen_list_t *pcur_item, *res;
	gen_list_t *p1, *p2;
	int cmp = 0;

	p1 = plist1;
	p2 = plist2;

	cmp = compare_proc (p1->data, p2->data, arg);
	if (cmp < 0)
	{
		pcur_item = p1;
		p1 = p1->next;
	}
	else
	{
		pcur_item = p2;
		p2 = p2->next;
	}
	res = pcur_item;
	while (NULL != p1 && NULL != p2)
	{
		cmp = compare_proc (p1->data, p2->data, arg);
		if (cmp < 0)
		{
			pcur_item->next = p1;
			pcur_item = p1;
			p1 = p1->next;
		}
		else
		{
			pcur_item->next = p2;
			pcur_item = p2;
			p2 = p2->next;
		}
	}
	pcur_item->next = (p1) ? p1 : p2;
	return res;
}

typedef struct sort_stack_item_s
{
	int level_;
	gen_list_t *item_;
} sort_stack_item_t;


#define MAX_SORT_STACK 32
gen_list_t *
list_sort (
	gen_list_t * list,
	int (*compare_proc) (const void *, const void *, const void *),
	const void *arg)
{
	sort_stack_item_t stack[MAX_SORT_STACK];
	int stack_pos = 0;
	gen_list_t *p = list;

	while (NULL != p)
	{
		stack[stack_pos].level_ = 1;
		stack[stack_pos].item_ = p;
		p = p->next;
		stack[stack_pos].item_->next = NULL;
		stack_pos++;
		Assert (stack_pos < MAX_SORT_STACK);
		while (stack_pos > 1
			&& stack[stack_pos - 1].level_ == stack[stack_pos - 2].level_)
		{
			stack[stack_pos - 2].item_ =
				intersect_sorted(
					stack[stack_pos - 2].item_,
					stack[stack_pos - 1].item_,
					compare_proc,
					arg);
			stack[stack_pos - 2].level_++;
			stack_pos--;
			Assert (stack_pos >= 0);
		}
	}
	while (stack_pos > 1)
	{
		stack[stack_pos - 2].item_ =
			intersect_sorted(
				stack[stack_pos - 2].item_,
				stack[stack_pos - 1].item_,
				compare_proc,
				arg);
		stack[stack_pos - 2].level_++;
		stack_pos--;
		Assert(stack_pos >= 0);
	}
	if (stack_pos > 0)
		list = stack[0].item_;
	return list;
}