File: mergesort.c

package info (click to toggle)
git 1:2.20.1-2+deb10u3
  • links: PTS, VCS
  • area: main
  • in suites: buster
  • size: 45,676 kB
  • sloc: ansic: 210,769; sh: 180,432; perl: 29,102; tcl: 21,663; python: 6,143; makefile: 3,700; sed: 189; php: 120; asm: 98; csh: 45; ruby: 24; lisp: 12
file content (73 lines) | stat: -rw-r--r-- 1,514 bytes parent folder | download | duplicates (18)
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
#include "cache.h"
#include "mergesort.h"

struct mergesort_sublist {
	void *ptr;
	unsigned long len;
};

static void *get_nth_next(void *list, unsigned long n,
			  void *(*get_next_fn)(const void *))
{
	while (n-- && list)
		list = get_next_fn(list);
	return list;
}

static void *pop_item(struct mergesort_sublist *l,
		      void *(*get_next_fn)(const void *))
{
	void *p = l->ptr;
	l->ptr = get_next_fn(l->ptr);
	l->len = l->ptr ? (l->len - 1) : 0;
	return p;
}

void *llist_mergesort(void *list,
		      void *(*get_next_fn)(const void *),
		      void (*set_next_fn)(void *, void *),
		      int (*compare_fn)(const void *, const void *))
{
	unsigned long l;

	if (!list)
		return NULL;
	for (l = 1; ; l *= 2) {
		void *curr;
		struct mergesort_sublist p, q;

		p.ptr = list;
		q.ptr = get_nth_next(p.ptr, l, get_next_fn);
		if (!q.ptr)
			break;
		p.len = q.len = l;

		if (compare_fn(p.ptr, q.ptr) > 0)
			list = curr = pop_item(&q, get_next_fn);
		else
			list = curr = pop_item(&p, get_next_fn);

		while (p.ptr) {
			while (p.len || q.len) {
				void *prev = curr;

				if (!p.len)
					curr = pop_item(&q, get_next_fn);
				else if (!q.len)
					curr = pop_item(&p, get_next_fn);
				else if (compare_fn(p.ptr, q.ptr) > 0)
					curr = pop_item(&q, get_next_fn);
				else
					curr = pop_item(&p, get_next_fn);
				set_next_fn(prev, curr);
			}
			p.ptr = q.ptr;
			p.len = l;
			q.ptr = get_nth_next(p.ptr, l, get_next_fn);
			q.len = q.ptr ? l : 0;

		}
		set_next_fn(curr, NULL);
	}
	return list;
}