]>
git.proxmox.com Git - libgit2.git/blob - src/tsort.c
2 * Copyright (C) the libgit2 contributors. All rights reserved.
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)))
27 void **dst
, const void *x
, size_t size
, git__sort_r_cmp cmp
, void *payload
)
39 /* check for beginning conditions */
40 if (cmp(x
, lx
, payload
) < 0)
43 else if (cmp(x
, lx
, payload
) == 0) {
45 while (cmp(x
, dst
[i
], payload
) == 0)
50 /* guaranteed not to be >= rx */
53 const int val
= cmp(x
, cx
, payload
);
55 if (c
- l
<= 1) return c
;
58 if (r
- c
<= 1) return c
+ 1;
64 } while (cmp(x
, cx
, payload
) == 0);
67 c
= l
+ ((r
- l
) >> 1);
72 /* Binary insertion sort, but knowing that the first "start" entries are sorted. Used in timsort. */
74 void **dst
, size_t start
, size_t size
, git__sort_r_cmp cmp
, void *payload
)
80 for (i
= start
; i
< size
; i
++) {
82 /* If this entry is already correct, just move along */
83 if (cmp(dst
[i
- 1], dst
[i
], payload
) <= 0)
86 /* Else we need to find the right place, shift everything over, and squeeze in */
88 location
= binsearch(dst
, x
, i
, cmp
, payload
);
89 for (j
= (int)i
- 1; j
>= location
; j
--) {
97 /* timsort implementation, based on timsort.txt */
110 static void reverse_elements(void **dst
, ssize_t start
, ssize_t end
)
112 while (start
< end
) {
113 void *tmp
= dst
[start
];
114 dst
[start
] = dst
[end
];
122 static ssize_t
count_run(
123 void **dst
, ssize_t start
, ssize_t size
, struct tsort_store
*store
)
125 ssize_t curr
= start
+ 2;
127 if (size
- start
== 1)
130 if (start
>= size
- 2) {
131 if (store
->cmp(dst
[size
- 2], dst
[size
- 1], store
->payload
) > 0) {
132 void *tmp
= dst
[size
- 1];
133 dst
[size
- 1] = dst
[size
- 2];
140 if (store
->cmp(dst
[start
], dst
[start
+ 1], store
->payload
) <= 0) {
141 while (curr
< size
- 1 &&
142 store
->cmp(dst
[curr
- 1], dst
[curr
], store
->payload
) <= 0)
147 while (curr
< size
- 1 &&
148 store
->cmp(dst
[curr
- 1], dst
[curr
], store
->payload
) > 0)
151 /* reverse in-place */
152 reverse_elements(dst
, start
, curr
- 1);
157 static size_t compute_minrun(size_t n
)
167 static int check_invariant(struct tsort_run
*stack
, ssize_t stack_curr
)
172 else if (stack_curr
== 2) {
173 const ssize_t A
= stack
[stack_curr
- 2].length
;
174 const ssize_t B
= stack
[stack_curr
- 1].length
;
177 const ssize_t A
= stack
[stack_curr
- 3].length
;
178 const ssize_t B
= stack
[stack_curr
- 2].length
;
179 const ssize_t C
= stack
[stack_curr
- 1].length
;
180 return !((A
<= B
+ C
) || (B
<= C
));
184 static int resize(struct tsort_store
*store
, size_t new_size
)
186 if (store
->alloc
< new_size
) {
189 tempstore
= git__reallocarray(store
->storage
, new_size
, sizeof(void *));
192 * Do not propagate on OOM; this will abort the sort and
193 * leave the array unsorted, but no error code will be
196 if (tempstore
== NULL
)
199 store
->storage
= tempstore
;
200 store
->alloc
= new_size
;
206 static void merge(void **dst
, const struct tsort_run
*stack
, ssize_t stack_curr
, struct tsort_store
*store
)
208 const ssize_t A
= stack
[stack_curr
- 2].length
;
209 const ssize_t B
= stack
[stack_curr
- 1].length
;
210 const ssize_t curr
= stack
[stack_curr
- 2].start
;
215 if (resize(store
, MIN(A
, B
)) < 0)
218 storage
= store
->storage
;
222 memcpy(storage
, &dst
[curr
], A
* sizeof(void *));
226 for (k
= curr
; k
< curr
+ A
+ B
; k
++) {
227 if ((i
< A
) && (j
< curr
+ A
+ B
)) {
228 if (store
->cmp(storage
[i
], dst
[j
], store
->payload
) <= 0)
229 dst
[k
] = storage
[i
++];
233 dst
[k
] = storage
[i
++];
238 memcpy(storage
, &dst
[curr
+ A
], B
* sizeof(void *));
242 for (k
= curr
+ A
+ B
- 1; k
>= curr
; k
--) {
243 if ((i
>= 0) && (j
>= curr
)) {
244 if (store
->cmp(dst
[j
], storage
[i
], store
->payload
) > 0)
247 dst
[k
] = storage
[i
--];
249 dst
[k
] = storage
[i
--];
256 static ssize_t
collapse(void **dst
, struct tsort_run
*stack
, ssize_t stack_curr
, struct tsort_store
*store
, ssize_t size
)
261 /* if the stack only has one thing on it, we are done with the collapse */
265 /* if this is the last merge, just do it */
266 if ((stack_curr
== 2) && (stack
[0].length
+ stack
[1].length
== size
)) {
267 merge(dst
, stack
, stack_curr
, store
);
268 stack
[0].length
+= stack
[1].length
;
273 /* check if the invariant is off for a stack of 2 elements */
274 else if ((stack_curr
== 2) && (stack
[0].length
<= stack
[1].length
)) {
275 merge(dst
, stack
, stack_curr
, store
);
276 stack
[0].length
+= stack
[1].length
;
280 else if (stack_curr
== 2)
283 A
= stack
[stack_curr
- 3].length
;
284 B
= stack
[stack_curr
- 2].length
;
285 C
= stack
[stack_curr
- 1].length
;
287 /* check first invariant */
290 merge(dst
, stack
, stack_curr
- 1, store
);
291 stack
[stack_curr
- 3].length
+= stack
[stack_curr
- 2].length
;
292 stack
[stack_curr
- 2] = stack
[stack_curr
- 1];
295 merge(dst
, stack
, stack_curr
, store
);
296 stack
[stack_curr
- 2].length
+= stack
[stack_curr
- 1].length
;
300 merge(dst
, stack
, stack_curr
, store
);
301 stack
[stack_curr
- 2].length
+= stack
[stack_curr
- 1].length
;
310 #define PUSH_NEXT() do {\
311 len = count_run(dst, curr, size, store);\
313 if (run < minrun) run = minrun;\
314 if (run > (ssize_t)size - curr) run = size - curr;\
316 bisort(&dst[curr], len, run, cmp, payload);\
319 run_stack[stack_curr].start = curr;\
320 run_stack[stack_curr++].length = len;\
322 if (curr == (ssize_t)size) {\
324 while (stack_curr > 1) { \
325 merge(dst, run_stack, stack_curr, store); \
326 run_stack[stack_curr - 2].length += run_stack[stack_curr - 1].length; \
329 if (store->storage != NULL) {\
330 git__free(store->storage);\
331 store->storage = NULL;\
339 void **dst
, size_t size
, git__sort_r_cmp cmp
, void *payload
)
341 struct tsort_store _store
, *store
= &_store
;
342 struct tsort_run run_stack
[128];
344 ssize_t stack_curr
= 0;
350 bisort(dst
, 1, size
, cmp
, payload
);
354 /* compute the minimum run length */
355 minrun
= (ssize_t
)compute_minrun(size
);
357 /* temporary storage for merges */
359 store
->storage
= NULL
;
361 store
->payload
= payload
;
368 if (!check_invariant(run_stack
, stack_curr
)) {
369 stack_curr
= collapse(dst
, run_stack
, stack_curr
, store
, size
);
377 static int tsort_r_cmp(const void *a
, const void *b
, void *payload
)
379 return ((git__tsort_cmp
)payload
)(a
, b
);
382 void git__tsort(void **dst
, size_t size
, git__tsort_cmp cmp
)
384 git__tsort_r(dst
, size
, tsort_r_cmp
, cmp
);