1/*
2 * Copyright (C) 2020 Benjamin Otte
3 * Copyright (C) 2011 Patrick O. Perry
4 * Copyright (C) 2008 The Android Open Source Project
5 *
6 * Licensed under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18
19#ifndef NAME
20#define NAME WIDTH
21#endif
22
23#define DEFINE_TEMP(temp) gpointer temp = g_alloca (WIDTH)
24#define ASSIGN(x, y) memcpy (x, y, WIDTH)
25#define INCPTR(x) ((gpointer) ((char *) (x) + WIDTH))
26#define DECPTR(x) ((gpointer) ((char *) (x) - WIDTH))
27#define ELEM(a, i) ((char *) (a) + (i) * WIDTH)
28#define LEN(n) ((n) * WIDTH)
29
30#define CONCAT(x, y) gtk_tim_sort_ ## x ## _ ## y
31#define MAKE_STR(x, y) CONCAT (x, y)
32#define gtk_tim_sort(x) MAKE_STR (x, NAME)
33
34/*
35 * Reverse the specified range of the specified array.
36 *
37 * @param a the array in which a range is to be reversed
38 * @param hi the index after the last element in the range to be reversed
39 */
40static void gtk_tim_sort(reverse_range) (GtkTimSort *self,
41 gpointer a,
42 gsize hi)
43{
44 DEFINE_TEMP (t);
45 char *front = a;
46 char *back = ELEM (a, hi - 1);
47
48 g_assert (hi > 0);
49
50 while (front < back)
51 {
52 ASSIGN (t, front);
53 ASSIGN (front, back);
54 ASSIGN (back, t);
55 front = INCPTR (front);
56 back = DECPTR (back);
57 }
58}
59
60/*
61 * Returns the length of the run beginning at the specified position in
62 * the specified array and reverses the run if it is descending (ensuring
63 * that the run will always be ascending when the method returns).
64 *
65 * A run is the longest ascending sequence with:
66 *
67 * a[0] <= a[1] <= a[2] <= ...
68 *
69 * or the longest descending sequence with:
70 *
71 * a[0] > a[1] > a[2] > ...
72 *
73 * For its intended use in a stable mergesort, the strictness of the
74 * definition of "descending" is needed so that the call can safely
75 * reverse a descending sequence without violating stability.
76 *
77 * @param a the array in which a run is to be counted and possibly reversed
78 * @param hi index after the last element that may be contained in the run.
79 * It is required that {@code 0 < hi}.
80 * @param compare the comparator to used for the sort
81 * @return the length of the run beginning at the specified position in
82 * the specified array
83 */
84static gsize
85gtk_tim_sort(prepare_run) (GtkTimSort *self,
86 GtkTimSortRun *out_change)
87{
88 gsize run_hi = 1;
89 char *cur;
90 char *next;
91
92 if (self->size <= run_hi)
93 {
94 gtk_tim_sort_set_change (out_change, NULL, len: 0);
95 return self->size;
96 }
97
98 cur = INCPTR (self->base);
99 next = INCPTR (cur);
100 run_hi++;
101
102 /* Find end of run, and reverse range if descending */
103 if (gtk_tim_sort_compare (self, a: cur, b: self->base) < 0) /* Descending */
104 {
105 while (run_hi < self->size && gtk_tim_sort_compare (self, a: next, b: cur) < 0)
106 {
107 run_hi++;
108 cur = next;
109 next = INCPTR (next);
110 }
111 gtk_tim_sort(reverse_range) (self, a: self->base, hi: run_hi);
112 gtk_tim_sort_set_change (out_change, base: self->base, len: run_hi);
113 }
114 else /* Ascending */
115 {
116 while (run_hi < self->size && gtk_tim_sort_compare (self, a: next, b: cur) >= 0)
117 {
118 run_hi++;
119 cur = next;
120 next = INCPTR (next);
121 }
122 gtk_tim_sort_set_change (out_change, NULL, len: 0);
123 }
124
125 return run_hi;
126}
127
128/*
129 * Sorts the specified portion of the specified array using a binary
130 * insertion sort. This is the best method for sorting small numbers
131 * of elements. It requires O(n log n) compares, but O(n^2) data
132 * movement (worst case).
133 *
134 * If the initial part of the specified range is already sorted,
135 * this method can take advantage of it: the method assumes that the
136 * elements from index {@code lo}, inclusive, to {@code start},
137 * exclusive are already sorted.
138 *
139 * @param a the array in which a range is to be sorted
140 * @param hi the index after the last element in the range to be sorted
141 * @param start the index of the first element in the range that is
142 * not already known to be sorted ({@code lo <= start <= hi})
143 */
144static void gtk_tim_sort(binary_sort) (GtkTimSort *self,
145 gpointer a,
146 gsize hi,
147 gsize start,
148 GtkTimSortRun *inout_change)
149{
150 DEFINE_TEMP (pivot);
151 char *startp;
152 char *change_min = ELEM (a, hi);
153 char *change_max = a;
154
155 g_assert (start <= hi);
156
157 if (start == 0)
158 start++;
159
160 startp = ELEM (a, start);
161
162 for (; start < hi; start++, startp = INCPTR (startp))
163 {
164 /* Set left (and right) to the index where a[start] (pivot) belongs */
165 char *leftp = a;
166 gsize right = start;
167 gsize n;
168
169 /*
170 * Invariants:
171 * pivot >= all in [0, left).
172 * pivot < all in [right, start).
173 */
174 while (0 < right)
175 {
176 gsize mid = right >> 1;
177 gpointer midp = ELEM (leftp, mid);
178 if (gtk_tim_sort_compare (self, a: startp, b: midp) < 0)
179 {
180 right = mid;
181 }
182 else
183 {
184 leftp = INCPTR (midp);
185 right -= (mid + 1);
186 }
187 }
188 g_assert (0 == right);
189
190 /*
191 * The invariants still hold: pivot >= all in [lo, left) and
192 * pivot < all in [left, start), so pivot belongs at left. Note
193 * that if there are elements equal to pivot, left points to the
194 * first slot after them -- that's why this sort is stable.
195 * Slide elements over to make room to make room for pivot.
196 */
197 n = startp - leftp; /* The number of bytes to move */
198 if (n == 0)
199 continue;
200
201 ASSIGN (pivot, startp);
202 memmove (INCPTR (leftp), src: leftp, n: n); /* POP: overlaps */
203
204 /* a[left] = pivot; */
205 ASSIGN (leftp, pivot);
206
207 change_min = MIN (change_min, leftp);
208 change_max = MAX (change_max, ELEM (startp, 1));
209 }
210
211 if (change_max > (char *) a)
212 {
213 g_assert (change_min < ELEM (a, hi));
214 if (inout_change && inout_change->len)
215 {
216 change_max = MAX (change_max, ELEM (inout_change->base, inout_change->len));
217 change_min = MIN (change_min, (char *) inout_change->base);
218 }
219 gtk_tim_sort_set_change (out_change: inout_change, base: change_min, len: (change_max - change_min) / WIDTH);
220 }
221}
222
223static gboolean
224gtk_tim_sort(merge_append) (GtkTimSort *self,
225 GtkTimSortRun *out_change)
226{
227 /* Identify next run */
228 gsize run_len;
229
230 run_len = gtk_tim_sort(prepare_run) (self, out_change);
231 if (run_len == 0)
232 return FALSE;
233
234 /* If run is short, extend to min(self->min_run, self->size) */
235 if (run_len < self->min_run)
236 {
237 gsize force = MIN (self->size, self->min_run);
238 gtk_tim_sort(binary_sort) (self, a: self->base, hi: force, start: run_len, inout_change: out_change);
239 run_len = force;
240 }
241 /* Push run onto pending-run stack, and maybe merge */
242 gtk_tim_sort_push_run (self, base: self->base, len: run_len);
243
244 return TRUE;
245}
246
247/*
248 * Locates the position at which to insert the specified key into the
249 * specified sorted range; if the range contains an element equal to key,
250 * returns the index of the leftmost equal element.
251 *
252 * @param key the key whose insertion point to search for
253 * @param base the array in which to search
254 * @param len the length of the range; must be > 0
255 * @param hint the index at which to begin the search, 0 <= hint < n.
256 * The closer hint is to the result, the faster this method will run.
257 * @param c the comparator used to order the range, and to search
258 * @return the int k, 0 <= k <= n such that a[b + k - 1] < key <= a[b + k],
259 * pretending that a[b - 1] is minus infinity and a[b + n] is infinity.
260 * In other words, key belongs at index b + k; or in other words,
261 * the first k elements of a should precede key, and the last n - k
262 * should follow it.
263 */
264static gsize
265gtk_tim_sort(gallop_left) (GtkTimSort *self,
266 gpointer key,
267 gpointer base,
268 gsize len,
269 gsize hint)
270{
271 char *hintp = ELEM (base, hint);
272 gsize last_ofs = 0;
273 gsize ofs = 1;
274
275 g_assert (len > 0 && hint < len);
276 if (gtk_tim_sort_compare (self, a: key, b: hintp) > 0)
277 {
278 /* Gallop right until a[hint+last_ofs] < key <= a[hint+ofs] */
279 gsize max_ofs = len - hint;
280 while (ofs < max_ofs
281 && gtk_tim_sort_compare (self, a: key, ELEM (hintp, ofs)) > 0)
282 {
283 last_ofs = ofs;
284 ofs = (ofs << 1) + 1; /* eventually this becomes SIZE_MAX */
285 }
286 if (ofs > max_ofs)
287 ofs = max_ofs;
288
289 /* Make offsets relative to base */
290 last_ofs += hint + 1; /* POP: we add 1 here so last_ofs stays non-negative */
291 ofs += hint;
292 }
293 else /* key <= a[hint] */
294 /* Gallop left until a[hint-ofs] < key <= a[hint-last_ofs] */
295 {
296 const gsize max_ofs = hint + 1;
297 gsize tmp;
298 while (ofs < max_ofs
299 && gtk_tim_sort_compare (self, a: key, ELEM (hintp, -ofs)) <= 0)
300 {
301 last_ofs = ofs;
302 ofs = (ofs << 1) + 1; /* no need to check for overflow */
303 }
304 if (ofs > max_ofs)
305 ofs = max_ofs;
306
307 /* Make offsets relative to base */
308 tmp = last_ofs;
309 last_ofs = hint + 1 - ofs; /* POP: we add 1 here so last_ofs stays non-negative */
310 ofs = hint - tmp;
311 }
312 g_assert (last_ofs <= ofs && ofs <= len);
313
314 /*
315 * Now a[last_ofs-1] < key <= a[ofs], so key belongs somewhere
316 * to the right of last_ofs but no farther right than ofs. Do a binary
317 * search, with invariant a[last_ofs - 1] < key <= a[ofs].
318 */
319 /* last_ofs++; POP: we added 1 above to keep last_ofs non-negative */
320 while (last_ofs < ofs)
321 {
322 /*gsize m = last_ofs + ((ofs - last_ofs) >> 1); */
323 /* http://stackoverflow.com/questions/4844165/safe-integer-middle-value-formula */
324 gsize m = (last_ofs & ofs) + ((last_ofs ^ ofs) >> 1);
325
326 if (gtk_tim_sort_compare (self, a: key, ELEM (base, m)) > 0)
327 last_ofs = m + 1; /* a[m] < key */
328 else
329 ofs = m; /* key <= a[m] */
330 }
331 g_assert (last_ofs == ofs); /* so a[ofs - 1] < key <= a[ofs] */
332 return ofs;
333}
334
335/*
336 * Like gallop_left, except that if the range contains an element equal to
337 * key, gallop_right returns the index after the rightmost equal element.
338 *
339 * @param key the key whose insertion point to search for
340 * @param base the array in which to search
341 * @param len the length of the range; must be > 0
342 * @param hint the index at which to begin the search, 0 <= hint < n.
343 * The closer hint is to the result, the faster this method will run.
344 * @param c the comparator used to order the range, and to search
345 * @return the int k, 0 <= k <= n such that a[b + k - 1] <= key < a[b + k]
346 */
347static gsize
348gtk_tim_sort(gallop_right) (GtkTimSort *self,
349 gpointer key,
350 gpointer base,
351 gsize len,
352 gsize hint)
353{
354 char *hintp = ELEM (base, hint);
355 gsize ofs = 1;
356 gsize last_ofs = 0;
357
358 g_assert (len > 0 && hint < len);
359
360 if (gtk_tim_sort_compare (self, a: key, b: hintp) < 0)
361 {
362 /* Gallop left until a[hint - ofs] <= key < a[hint - last_ofs] */
363 gsize max_ofs = hint + 1;
364 gsize tmp;
365 while (ofs < max_ofs
366 && gtk_tim_sort_compare (self, a: key, ELEM (hintp, -ofs)) < 0)
367 {
368 last_ofs = ofs;
369 ofs = (ofs << 1) + 1; /* no need to check for overflow */
370 }
371 if (ofs > max_ofs)
372 ofs = max_ofs;
373
374 /* Make offsets relative to base */
375 tmp = last_ofs;
376 last_ofs = hint + 1 - ofs;
377 ofs = hint - tmp;
378 }
379 else /* a[hint] <= key */
380 /* Gallop right until a[hint + last_ofs] <= key < a[hint + ofs] */
381 {
382 gsize max_ofs = len - hint;
383 while (ofs < max_ofs
384 && gtk_tim_sort_compare (self, a: key, ELEM (hintp, ofs)) >= 0)
385 {
386 last_ofs = ofs;
387 ofs = (ofs << 1) + 1; /* no need to check for overflow */
388 }
389 if (ofs > max_ofs)
390 ofs = max_ofs;
391
392 /* Make offsets relative to base */
393 last_ofs += hint + 1;
394 ofs += hint;
395 }
396 g_assert (last_ofs <= ofs && ofs <= len);
397
398 /*
399 * Now a[last_ofs - 1] <= key < a[ofs], so key belongs somewhere to
400 * the right of last_ofs but no farther right than ofs. Do a binary
401 * search, with invariant a[last_ofs - 1] <= key < a[ofs].
402 */
403 while (last_ofs < ofs)
404 {
405 /* gsize m = last_ofs + ((ofs - last_ofs) >> 1); */
406 gsize m = (last_ofs & ofs) + ((last_ofs ^ ofs) >> 1);
407
408 if (gtk_tim_sort_compare (self, a: key, ELEM (base, m)) < 0)
409 ofs = m; /* key < a[m] */
410 else
411 last_ofs = m + 1; /* a[m] <= key */
412 }
413 g_assert (last_ofs == ofs); /* so a[ofs - 1] <= key < a[ofs] */
414 return ofs;
415}
416
417/*
418 * Merges two adjacent runs in place, in a stable fashion. The first
419 * element of the first run must be greater than the first element of the
420 * second run (a[base1] > a[base2]), and the last element of the first run
421 * (a[base1 + len1-1]) must be greater than all elements of the second run.
422 *
423 * For performance, this method should be called only when len1 <= len2;
424 * its twin, merge_hi should be called if len1 >= len2. (Either method
425 * may be called if len1 == len2.)
426 *
427 * @param base1 first element in first run to be merged
428 * @param len1 length of first run to be merged (must be > 0)
429 * @param base2 first element in second run to be merged
430 * (must be aBase + aLen)
431 * @param len2 length of second run to be merged (must be > 0)
432 */
433static void
434gtk_tim_sort(merge_lo) (GtkTimSort *self,
435 gpointer base1,
436 gsize len1,
437 gpointer base2,
438 gsize len2)
439{
440 /* Copy first run into temp array */
441 gpointer tmp = gtk_tim_sort_ensure_capacity (self, min_capacity: len1);
442 char *cursor1;
443 char *cursor2;
444 char *dest;
445 gsize min_gallop;
446
447 g_assert (len1 > 0 && len2 > 0 && ELEM (base1, len1) == base2);
448
449 /* System.arraycopy(a, base1, tmp, 0, len1); */
450 memcpy (dest: tmp, src: base1, LEN (len1)); /* POP: can't overlap */
451
452 cursor1 = tmp; /* Indexes into tmp array */
453 cursor2 = base2; /* Indexes int a */
454 dest = base1; /* Indexes int a */
455
456 /* Move first element of second run and deal with degenerate cases */
457 /* a[dest++] = a[cursor2++]; */
458 ASSIGN (dest, cursor2);
459 dest = INCPTR (dest);
460 cursor2 = INCPTR (cursor2);
461
462 if (--len2 == 0)
463 {
464 memcpy (dest: dest, src: cursor1, LEN (len1)); /* POP: can't overlap */
465 return;
466 }
467 if (len1 == 1)
468 {
469 memmove (dest: dest, src: cursor2, LEN (len2)); /* POP: overlaps */
470
471 /* a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge */
472 ASSIGN (ELEM (dest, len2), cursor1);
473 return;
474 }
475
476 /* Use local variable for performance */
477 min_gallop = self->min_gallop;
478
479 while (TRUE)
480 {
481 gsize count1 = 0; /* Number of times in a row that first run won */
482 gsize count2 = 0; /* Number of times in a row that second run won */
483
484 /*
485 * Do the straightforward thing until (if ever) one run starts
486 * winning consistently.
487 */
488 do
489 {
490 g_assert (len1 > 1 && len2 > 0);
491 if (gtk_tim_sort_compare (self, a: cursor2, b: cursor1) < 0)
492 {
493 ASSIGN (dest, cursor2);
494 dest = INCPTR (dest);
495 cursor2 = INCPTR (cursor2);
496 count2++;
497 count1 = 0;
498 if (--len2 == 0)
499 goto outer;
500 if (count2 >= min_gallop)
501 break;
502 }
503 else
504 {
505 ASSIGN (dest, cursor1);
506 dest = INCPTR (dest);
507 cursor1 = INCPTR (cursor1);
508 count1++;
509 count2 = 0;
510 if (--len1 == 1)
511 goto outer;
512 if (count1 >= min_gallop)
513 break;
514 }
515 }
516 while (TRUE); /* (count1 | count2) < min_gallop); */
517
518 /*
519 * One run is winning so consistently that galloping may be a
520 * huge win. So try that, and continue galloping until (if ever)
521 * neither run appears to be winning consistently anymore.
522 */
523 do
524 {
525 g_assert (len1 > 1 && len2 > 0);
526 count1 = gtk_tim_sort(gallop_right) (self, key: cursor2, base: cursor1, len: len1, hint: 0);
527 if (count1 != 0)
528 {
529 memcpy (dest: dest, src: cursor1, LEN (count1)); /* POP: can't overlap */
530 dest = ELEM (dest, count1);
531 cursor1 = ELEM (cursor1, count1);
532 len1 -= count1;
533 if (len1 <= 1) /* len1 == 1 || len1 == 0 */
534 goto outer;
535 }
536 ASSIGN (dest, cursor2);
537 dest = INCPTR (dest);
538 cursor2 = INCPTR (cursor2);
539 if (--len2 == 0)
540 goto outer;
541
542 count2 = gtk_tim_sort(gallop_left) (self, key: cursor1, base: cursor2, len: len2, hint: 0);
543 if (count2 != 0)
544 {
545 memmove (dest: dest, src: cursor2, LEN (count2)); /* POP: might overlap */
546 dest = ELEM (dest, count2);
547 cursor2 = ELEM (cursor2, count2);
548 len2 -= count2;
549 if (len2 == 0)
550 goto outer;
551 }
552 ASSIGN (dest, cursor1);
553 dest = INCPTR (dest);
554 cursor1 = INCPTR (cursor1);
555 if (--len1 == 1)
556 goto outer;
557 if (min_gallop > 0)
558 min_gallop--;
559 }
560 while (count1 >= MIN_GALLOP || count2 >= MIN_GALLOP);
561 min_gallop += 2; /* Penalize for leaving gallop mode */
562 } /* End of "outer" loop */
563outer:
564 self->min_gallop = min_gallop < 1 ? 1 : min_gallop; /* Write back to field */
565
566 if (len1 == 1)
567 {
568 g_assert (len2 > 0);
569 memmove (dest: dest, src: cursor2, LEN (len2)); /* POP: might overlap */
570 ASSIGN (ELEM (dest, len2), cursor1); /* Last elt of run 1 to end of merge */
571 }
572 else if (len1 == 0)
573 {
574 g_critical ("Comparison method violates its general contract");
575 return;
576 }
577 else
578 {
579 g_assert (len2 == 0);
580 g_assert (len1 > 1);
581 memcpy (dest: dest, src: cursor1, LEN (len1)); /* POP: can't overlap */
582 }
583}
584
585/*
586 * Like merge_lo, except that this method should be called only if
587 * len1 >= len2; merge_lo should be called if len1 <= len2. (Either method
588 * may be called if len1 == len2.)
589 *
590 * @param base1 first element in first run to be merged
591 * @param len1 length of first run to be merged (must be > 0)
592 * @param base2 first element in second run to be merged
593 * (must be aBase + aLen)
594 * @param len2 length of second run to be merged (must be > 0)
595 */
596static void
597gtk_tim_sort(merge_hi) (GtkTimSort *self,
598 gpointer base1,
599 gsize len1,
600 gpointer base2,
601 gsize len2)
602{
603 /* Copy second run into temp array */
604 gpointer tmp = gtk_tim_sort_ensure_capacity (self, min_capacity: len2);
605 char *cursor1; /* Indexes into a */
606 char *cursor2; /* Indexes into tmp array */
607 char *dest; /* Indexes into a */
608 gsize min_gallop;
609
610 g_assert (len1 > 0 && len2 > 0 && ELEM (base1, len1) == base2);
611
612 memcpy (dest: tmp, src: base2, LEN (len2)); /* POP: can't overlap */
613
614 cursor1 = ELEM (base1, len1 - 1); /* Indexes into a */
615 cursor2 = ELEM (tmp, len2 - 1); /* Indexes into tmp array */
616 dest = ELEM (base2, len2 - 1); /* Indexes into a */
617
618 /* Move last element of first run and deal with degenerate cases */
619 /* a[dest--] = a[cursor1--]; */
620 ASSIGN (dest, cursor1);
621 dest = DECPTR (dest);
622 cursor1 = DECPTR (cursor1);
623 if (--len1 == 0)
624 {
625 memcpy (ELEM (dest, -(len2 - 1)), src: tmp, LEN (len2)); /* POP: can't overlap */
626 return;
627 }
628 if (len2 == 1)
629 {
630 dest = ELEM (dest, -len1);
631 cursor1 = ELEM (cursor1, -len1);
632 memmove (ELEM (dest, 1), ELEM (cursor1, 1), LEN (len1)); /* POP: overlaps */
633 /* a[dest] = tmp[cursor2]; */
634 ASSIGN (dest, cursor2);
635 return;
636 }
637
638 /* Use local variable for performance */
639 min_gallop = self->min_gallop;
640
641 while (TRUE)
642 {
643 gsize count1 = 0; /* Number of times in a row that first run won */
644 gsize count2 = 0; /* Number of times in a row that second run won */
645
646 /*
647 * Do the straightforward thing until (if ever) one run
648 * appears to win consistently.
649 */
650 do
651 {
652 g_assert (len1 > 0 && len2 > 1);
653 if (gtk_tim_sort_compare (self, a: cursor2, b: cursor1) < 0)
654 {
655 ASSIGN (dest, cursor1);
656 dest = DECPTR (dest);
657 cursor1 = DECPTR (cursor1);
658 count1++;
659 count2 = 0;
660 if (--len1 == 0)
661 goto outer;
662 }
663 else
664 {
665 ASSIGN (dest, cursor2);
666 dest = DECPTR (dest);
667 cursor2 = DECPTR (cursor2);
668 count2++;
669 count1 = 0;
670 if (--len2 == 1)
671 goto outer;
672 }
673 }
674 while ((count1 | count2) < min_gallop);
675
676 /*
677 * One run is winning so consistently that galloping may be a
678 * huge win. So try that, and continue galloping until (if ever)
679 * neither run appears to be winning consistently anymore.
680 */
681 do
682 {
683 g_assert (len1 > 0 && len2 > 1);
684 count1 = len1 - gtk_tim_sort(gallop_right) (self, key: cursor2, base: base1, len: len1, hint: len1 - 1);
685 if (count1 != 0)
686 {
687 dest = ELEM (dest, -count1);
688 cursor1 = ELEM (cursor1, -count1);
689 len1 -= count1;
690 memmove (INCPTR (dest), INCPTR (cursor1),
691 LEN (count1)); /* POP: might overlap */
692 if (len1 == 0)
693 goto outer;
694 }
695 ASSIGN (dest, cursor2);
696 dest = DECPTR (dest);
697 cursor2 = DECPTR (cursor2);
698 if (--len2 == 1)
699 goto outer;
700
701 count2 = len2 - gtk_tim_sort(gallop_left) (self, key: cursor1, base: tmp, len: len2, hint: len2 - 1);
702 if (count2 != 0)
703 {
704 dest = ELEM (dest, -count2);
705 cursor2 = ELEM (cursor2, -count2);
706 len2 -= count2;
707 memcpy (INCPTR (dest), INCPTR (cursor2), LEN (count2)); /* POP: can't overlap */
708 if (len2 <= 1) /* len2 == 1 || len2 == 0 */
709 goto outer;
710 }
711 ASSIGN (dest, cursor1);
712 dest = DECPTR (dest);
713 cursor1 = DECPTR (cursor1);
714 if (--len1 == 0)
715 goto outer;
716 if (min_gallop > 0)
717 min_gallop--;
718 }
719 while (count1 >= MIN_GALLOP || count2 >= MIN_GALLOP);
720 min_gallop += 2; /* Penalize for leaving gallop mode */
721 } /* End of "outer" loop */
722outer:
723 self->min_gallop = min_gallop < 1 ? 1 : min_gallop; /* Write back to field */
724
725 if (len2 == 1)
726 {
727 g_assert (len1 > 0);
728 dest = ELEM (dest, -len1);
729 cursor1 = ELEM (cursor1, -len1);
730 memmove (INCPTR (dest), INCPTR (cursor1), LEN (len1)); /* POP: might overlap */
731 /* a[dest] = tmp[cursor2]; // Move first elt of run2 to front of merge */
732 ASSIGN (dest, cursor2);
733 }
734 else if (len2 == 0)
735 {
736 g_critical ("Comparison method violates its general contract");
737 return;
738 }
739 else
740 {
741 g_assert (len1 == 0);
742 g_assert (len2 > 0);
743 memcpy (ELEM (dest, -(len2 - 1)), src: tmp, LEN (len2)); /* POP: can't overlap */
744 }
745}
746
747/*
748 * Merges the two runs at stack indices i and i+1. Run i must be
749 * the penultimate or antepenultimate run on the stack. In other words,
750 * i must be equal to pending_runs-2 or pending_runs-3.
751 *
752 * @param i stack index of the first of the two runs to merge
753 */
754static void
755gtk_tim_sort(merge_at) (GtkTimSort *self,
756 gsize i,
757 GtkTimSortRun *out_change)
758{
759 gpointer base1 = self->run[i].base;
760 gsize len1 = self->run[i].len;
761 gpointer base2 = self->run[i + 1].base;
762 gsize len2 = self->run[i + 1].len;
763 gsize k;
764
765 g_assert (self->pending_runs >= 2);
766 g_assert (i == self->pending_runs - 2 || i == self->pending_runs - 3);
767 g_assert (len1 > 0 && len2 > 0);
768 g_assert (ELEM (base1, len1) == base2);
769
770 /*
771 * Find where the first element of run2 goes in run1. Prior elements
772 * in run1 can be ignored (because they're already in place).
773 */
774 k = gtk_tim_sort(gallop_right) (self, key: base2, base: base1, len: len1, hint: 0);
775 base1 = ELEM (base1, k);
776 len1 -= k;
777 if (len1 == 0)
778 {
779 gtk_tim_sort_set_change (out_change, NULL, len: 0);
780 goto done;
781 }
782
783 /*
784 * Find where the last element of run1 goes in run2. Subsequent elements
785 * in run2 can be ignored (because they're already in place).
786 */
787 len2 = gtk_tim_sort(gallop_left) (self,
788 ELEM (base1, len1 - 1),
789 base: base2, len: len2, hint: len2 - 1);
790 if (len2 == 0)
791 {
792 gtk_tim_sort_set_change (out_change, NULL, len: 0);
793 goto done;
794 }
795
796 /* Merge remaining runs, using tmp array with min(len1, len2) elements */
797 if (len1 <= len2)
798 {
799 if (len1 > self->max_merge_size)
800 {
801 base1 = ELEM (self->run[i].base, self->run[i].len - self->max_merge_size);
802 gtk_tim_sort(merge_lo) (self, base1, len1: self->max_merge_size, base2, len2);
803 gtk_tim_sort_set_change (out_change, base: base1, len: self->max_merge_size + len2);
804 self->run[i].len -= self->max_merge_size;
805 self->run[i + 1].base = ELEM (self->run[i + 1].base, - self->max_merge_size);
806 self->run[i + 1].len += self->max_merge_size;
807 g_assert (ELEM (self->run[i].base, self->run[i].len) == self->run[i + 1].base);
808 return;
809 }
810 else
811 {
812 gtk_tim_sort(merge_lo) (self, base1, len1, base2, len2);
813 gtk_tim_sort_set_change (out_change, base: base1, len: len1 + len2);
814 }
815 }
816 else
817 {
818 if (len2 > self->max_merge_size)
819 {
820 gtk_tim_sort(merge_hi) (self, base1, len1, base2, len2: self->max_merge_size);
821 gtk_tim_sort_set_change (out_change, base: base1, len: len1 + self->max_merge_size);
822 self->run[i].len += self->max_merge_size;
823 self->run[i + 1].base = ELEM (self->run[i + 1].base, self->max_merge_size);
824 self->run[i + 1].len -= self->max_merge_size;
825 g_assert (ELEM (self->run[i].base, self->run[i].len) == self->run[i + 1].base);
826 return;
827 }
828 else
829 {
830 gtk_tim_sort(merge_hi) (self, base1, len1, base2, len2);
831 gtk_tim_sort_set_change (out_change, base: base1, len: len1 + len2);
832 }
833 }
834
835done:
836 /*
837 * Record the length of the combined runs; if i is the 3rd-last
838 * run now, also slide over the last run (which isn't involved
839 * in this merge). The current run (i+1) goes away in any case.
840 */
841 self->run[i].len += self->run[i + 1].len;
842 if (i == self->pending_runs - 3)
843 self->run[i + 1] = self->run[i + 2];
844 self->pending_runs--;
845}
846
847
848/*
849 * Examines the stack of runs waiting to be merged and merges adjacent runs
850 * until the stack invariants are reestablished:
851 *
852 * 1. run_len[i - 3] > run_len[i - 2] + run_len[i - 1]
853 * 2. run_len[i - 2] > run_len[i - 1]
854 *
855 * This method is called each time a new run is pushed onto the stack,
856 * so the invariants are guaranteed to hold for i < pending_runs upon
857 * entry to the method.
858 *
859 * POP:
860 * Modified according to http://envisage-project.eu/wp-content/uploads/2015/02/sorting.pdf
861 *
862 * and
863 *
864 * https://bugs.openjdk.java.net/browse/JDK-8072909 (suggestion 2)
865 *
866 */
867static gboolean
868gtk_tim_sort(merge_collapse) (GtkTimSort *self,
869 GtkTimSortRun *out_change)
870{
871 GtkTimSortRun *run = self->run;
872 gsize n;
873
874 if (self->pending_runs <= 1)
875 return FALSE;
876
877 n = self->pending_runs - 2;
878 if ((n > 0 && run[n - 1].len <= run[n].len + run[n + 1].len) ||
879 (n > 1 && run[n - 2].len <= run[n].len + run[n - 1].len))
880 {
881 if (run[n - 1].len < run[n + 1].len)
882 n--;
883 }
884 else if (run[n].len > run[n + 1].len)
885 {
886 return FALSE; /* Invariant is established */
887 }
888
889 gtk_tim_sort(merge_at) (self, i: n, out_change);
890 return TRUE;
891}
892
893/*
894 * Merges all runs on the stack until only one remains. This method is
895 * called once, to complete the sort.
896 */
897static gboolean
898gtk_tim_sort(merge_force_collapse) (GtkTimSort *self,
899 GtkTimSortRun *out_change)
900{
901 gsize n;
902
903 if (self->pending_runs <= 1)
904 return FALSE;
905
906 n = self->pending_runs - 2;
907 if (n > 0 && self->run[n - 1].len < self->run[n + 1].len)
908 n--;
909 gtk_tim_sort(merge_at) (self, i: n, out_change);
910 return TRUE;
911}
912
913static gboolean
914gtk_tim_sort(step) (GtkTimSort *self,
915 GtkTimSortRun *out_change)
916{
917 g_assert (self);
918
919 if (gtk_tim_sort(merge_collapse) (self, out_change))
920 return TRUE;
921
922 if (gtk_tim_sort(merge_append) (self, out_change))
923 return TRUE;
924
925 if (gtk_tim_sort(merge_force_collapse) (self, out_change))
926 return TRUE;
927
928 return FALSE;
929}
930
931#undef DEFINE_TEMP
932#undef ASSIGN
933#undef INCPTR
934#undef DECPTR
935#undef ELEM
936#undef LEN
937
938#undef CONCAT
939#undef MAKE_STR
940#undef gtk_tim_sort
941
942#undef WIDTH
943#undef NAME
944

source code of gtk/gtk/timsort/gtktimsort-impl.c