]>
git.proxmox.com Git - libgit2.git/blob - src/tsort.c
2 * Copyright (C) 2009-2011 the libgit2 contributors
4 * This file is part of libgit2, distributed under the GNU GPL v2 with
5 * a Linking Exception. For full terms see the included COPYING file.
11 * An array-of-pointers implementation of Python's Timsort
12 * Based on code by Christopher Swenson under the MIT license
14 * Copyright (c) 2010 Christopher Swenson
15 * Copyright (c) 2011 Vicent Marti
19 # define MAX(x,y) (((x) > (y) ? (x) : (y)))
23 # define MIN(x,y) (((x) < (y) ? (x) : (y)))
26 typedef int (*cmp_ptr_t
)(const void *, const void *);
28 static int binsearch(void **dst
, const void *x
, size_t size
, cmp_ptr_t cmp
)
38 /* check for beginning conditions */
42 else if (cmp(x
, lx
) == 0) {
44 while (cmp(x
, dst
[i
]) == 0)
49 /* guaranteed not to be >= rx */
52 const int val
= cmp(x
, cx
);
54 if (c
- l
<= 1) return c
;
57 if (r
- c
<= 1) return c
+ 1;
63 } while (cmp(x
, cx
) == 0);
66 c
= l
+ ((r
- l
) >> 1);
71 /* Binary insertion sort, but knowing that the first "start" entries are sorted. Used in timsort. */
72 static void bisort(void **dst
, size_t start
, size_t size
, cmp_ptr_t cmp
)
78 for (i
= start
; i
< size
; i
++) {
80 /* If this entry is already correct, just move along */
81 if (cmp(dst
[i
- 1], dst
[i
]) <= 0)
84 /* Else we need to find the right place, shift everything over, and squeeze in */
86 location
= binsearch(dst
, x
, i
, cmp
);
87 for (j
= i
- 1; j
>= location
; j
--) {
95 /* timsort implementation, based on timsort.txt */
107 static void reverse_elements(void **dst
, int start
, int end
)
109 while (start
< end
) {
110 void *tmp
= dst
[start
];
111 dst
[start
] = dst
[end
];
119 static int count_run(void **dst
, ssize_t start
, ssize_t size
, struct tsort_store
*store
)
121 ssize_t curr
= start
+ 2;
123 if (size
- start
== 1)
126 if (start
>= size
- 2) {
127 if (store
->cmp(dst
[size
- 2], dst
[size
- 1]) > 0) {
128 void *tmp
= dst
[size
- 1];
129 dst
[size
- 1] = dst
[size
- 2];
136 if (store
->cmp(dst
[start
], dst
[start
+ 1]) <= 0) {
137 while (curr
< size
- 1 && store
->cmp(dst
[curr
- 1], dst
[curr
]) <= 0)
142 while (curr
< size
- 1 && store
->cmp(dst
[curr
- 1], dst
[curr
]) > 0)
145 /* reverse in-place */
146 reverse_elements(dst
, start
, curr
- 1);
151 static int compute_minrun(size_t n
)
161 static int check_invariant(struct tsort_run
*stack
, int stack_curr
)
166 else if (stack_curr
== 2) {
167 const int A
= stack
[stack_curr
- 2].length
;
168 const int B
= stack
[stack_curr
- 1].length
;
171 const int A
= stack
[stack_curr
- 3].length
;
172 const int B
= stack
[stack_curr
- 2].length
;
173 const int C
= stack
[stack_curr
- 1].length
;
174 return !((A
<= B
+ C
) || (B
<= C
));
178 static int resize(struct tsort_store
*store
, size_t new_size
)
180 if (store
->alloc
< new_size
) {
181 void **tempstore
= git__realloc(store
->storage
, new_size
* sizeof(void *));
184 * Do not propagate on OOM; this will abort the sort and
185 * leave the array unsorted, but no error code will be
188 if (tempstore
== NULL
)
191 store
->storage
= tempstore
;
192 store
->alloc
= new_size
;
198 static void merge(void **dst
, const struct tsort_run
*stack
, int stack_curr
, struct tsort_store
*store
)
200 const ssize_t A
= stack
[stack_curr
- 2].length
;
201 const ssize_t B
= stack
[stack_curr
- 1].length
;
202 const ssize_t curr
= stack
[stack_curr
- 2].start
;
207 if (resize(store
, MIN(A
, B
)) < 0)
210 storage
= store
->storage
;
214 memcpy(storage
, &dst
[curr
], A
* sizeof(void *));
218 for (k
= curr
; k
< curr
+ A
+ B
; k
++) {
219 if ((i
< A
) && (j
< curr
+ A
+ B
)) {
220 if (store
->cmp(storage
[i
], dst
[j
]) <= 0)
221 dst
[k
] = storage
[i
++];
225 dst
[k
] = storage
[i
++];
230 memcpy(storage
, &dst
[curr
+ A
], B
* sizeof(void *));
234 for (k
= curr
+ A
+ B
- 1; k
>= curr
; k
--) {
235 if ((i
>= 0) && (j
>= curr
)) {
236 if (store
->cmp(dst
[j
], storage
[i
]) > 0)
239 dst
[k
] = storage
[i
--];
241 dst
[k
] = storage
[i
--];
248 static ssize_t
collapse(void **dst
, struct tsort_run
*stack
, ssize_t stack_curr
, struct tsort_store
*store
, ssize_t size
)
253 /* if the stack only has one thing on it, we are done with the collapse */
257 /* if this is the last merge, just do it */
258 if ((stack_curr
== 2) && (stack
[0].length
+ stack
[1].length
== size
)) {
259 merge(dst
, stack
, stack_curr
, store
);
260 stack
[0].length
+= stack
[1].length
;
265 /* check if the invariant is off for a stack of 2 elements */
266 else if ((stack_curr
== 2) && (stack
[0].length
<= stack
[1].length
)) {
267 merge(dst
, stack
, stack_curr
, store
);
268 stack
[0].length
+= stack
[1].length
;
272 else if (stack_curr
== 2)
275 A
= stack
[stack_curr
- 3].length
;
276 B
= stack
[stack_curr
- 2].length
;
277 C
= stack
[stack_curr
- 1].length
;
279 /* check first invariant */
282 merge(dst
, stack
, stack_curr
- 1, store
);
283 stack
[stack_curr
- 3].length
+= stack
[stack_curr
- 2].length
;
284 stack
[stack_curr
- 2] = stack
[stack_curr
- 1];
287 merge(dst
, stack
, stack_curr
, store
);
288 stack
[stack_curr
- 2].length
+= stack
[stack_curr
- 1].length
;
292 merge(dst
, stack
, stack_curr
, store
);
293 stack
[stack_curr
- 2].length
+= stack
[stack_curr
- 1].length
;
302 #define PUSH_NEXT() do {\
303 len = count_run(dst, curr, size, store);\
305 if (run < minrun) run = minrun;\
306 if (run > (ssize_t)size - curr) run = size - curr;\
308 bisort(&dst[curr], len, run, cmp);\
311 run_stack[stack_curr].start = curr;\
312 run_stack[stack_curr++].length = len;\
314 if (curr == (ssize_t)size) {\
316 while (stack_curr > 1) { \
317 merge(dst, run_stack, stack_curr, store); \
318 run_stack[stack_curr - 2].length += run_stack[stack_curr - 1].length; \
321 if (store->storage != NULL) {\
322 git__free(store->storage);\
323 store->storage = NULL;\
330 void git__tsort(void **dst
, size_t size
, cmp_ptr_t cmp
)
332 struct tsort_store _store
, *store
= &_store
;
333 struct tsort_run run_stack
[128];
335 ssize_t stack_curr
= 0;
341 bisort(dst
, 1, size
, cmp
);
345 /* compute the minimum run length */
346 minrun
= compute_minrun(size
);
348 /* temporary storage for merges */
350 store
->storage
= NULL
;
358 if (!check_invariant(run_stack
, stack_curr
)) {
359 stack_curr
= collapse(dst
, run_stack
, stack_curr
, store
, size
);