archive: improve documentation of --prefix
[git/debian.git] / mergesort.c
blobbd9c6ef8eec5bc23f8c83fe8d373be946b8b2f48
1 #include "cache.h"
2 #include "mergesort.h"
4 /* Combine two sorted lists. Take from `list` on equality. */
5 static void *llist_merge(void *list, void *other,
6 void *(*get_next_fn)(const void *),
7 void (*set_next_fn)(void *, void *),
8 int (*compare_fn)(const void *, const void *))
10 void *result = list, *tail;
12 if (compare_fn(list, other) > 0) {
13 result = other;
14 goto other;
16 for (;;) {
17 do {
18 tail = list;
19 list = get_next_fn(list);
20 if (!list) {
21 set_next_fn(tail, other);
22 return result;
24 } while (compare_fn(list, other) <= 0);
25 set_next_fn(tail, other);
26 other:
27 do {
28 tail = other;
29 other = get_next_fn(other);
30 if (!other) {
31 set_next_fn(tail, list);
32 return result;
34 } while (compare_fn(list, other) > 0);
35 set_next_fn(tail, list);
40 * Perform an iterative mergesort using an array of sublists.
42 * n is the number of items.
43 * ranks[i] is undefined if n & 2^i == 0, and assumed empty.
44 * ranks[i] contains a sublist of length 2^i otherwise.
46 * The number of bits in a void pointer limits the number of objects
47 * that can be created, and thus the number of array elements necessary
48 * to be able to sort any valid list.
50 * Adding an item to this array is like incrementing a binary number;
51 * positional values for set bits correspond to sublist lengths.
53 void *llist_mergesort(void *list,
54 void *(*get_next_fn)(const void *),
55 void (*set_next_fn)(void *, void *),
56 int (*compare_fn)(const void *, const void *))
58 void *ranks[bitsizeof(void *)];
59 size_t n = 0;
60 int i;
62 while (list) {
63 void *next = get_next_fn(list);
64 if (next)
65 set_next_fn(list, NULL);
66 for (i = 0; n & ((size_t)1 << i); i++)
67 list = llist_merge(ranks[i], list, get_next_fn,
68 set_next_fn, compare_fn);
69 n++;
70 ranks[i] = list;
71 list = next;
74 for (i = 0; n; i++, n >>= 1) {
75 if (!(n & 1))
76 continue;
77 if (list)
78 list = llist_merge(ranks[i], list, get_next_fn,
79 set_next_fn, compare_fn);
80 else
81 list = ranks[i];
83 return list;