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 | */ |
40 | static 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 | */ |
84 | static gsize |
85 | gtk_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 | */ |
144 | static 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 | |
223 | static gboolean |
224 | gtk_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 | */ |
264 | static gsize |
265 | gtk_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 | */ |
347 | static gsize |
348 | gtk_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 | */ |
433 | static void |
434 | gtk_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 */ |
563 | outer: |
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 | */ |
596 | static void |
597 | gtk_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 */ |
722 | outer: |
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 | */ |
754 | static void |
755 | gtk_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 | |
835 | done: |
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 | */ |
867 | static gboolean |
868 | gtk_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 | */ |
897 | static gboolean |
898 | gtk_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 | |
913 | static gboolean |
914 | gtk_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 | |