1/*
2 * Copyright © 2020 Benjamin Otte
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library. If not, see <http://www.gnu.org/licenses/>.
16 */
17
18#ifndef __GTK_TIMSORT_PRIVATE_H__
19#define __GTK_TIMSORT_PRIVATE_H__
20
21#include <gdk/gdk.h>
22
23/* The maximum number of entries in a GtkTimState's pending-runs stack.
24 * This is enough to sort arrays of size up to about
25 * 32 * phi ** GTK_TIM_SORT_MAX_PENDING
26 * where phi ~= 1.618. 85 is ridiculously large enough, good for an array
27 * with 2**64 elements.
28 */
29#define GTK_TIM_SORT_MAX_PENDING 86
30
31typedef struct _GtkTimSort GtkTimSort;
32typedef struct _GtkTimSortRun GtkTimSortRun;
33
34struct _GtkTimSortRun
35{
36 void *base;
37 gsize len;
38};
39
40struct _GtkTimSort
41{
42 /*
43 * Size of elements. Used to decide on fast paths.
44 */
45 gsize element_size;
46
47 /* The comparator for this sort.
48 */
49 GCompareDataFunc compare_func;
50 gpointer data;
51
52 /*
53 * The array being sorted.
54 */
55 gpointer base;
56 gsize size;
57
58 /*
59 * The maximum size of a merge. It's guaranteed >0 and user-provided.
60 * See the comments for gtk_tim_sort_set_max_merge_size() for details.
61 */
62 gsize max_merge_size;
63
64 /*
65 * This controls when we get *into* galloping mode. It is initialized
66 * to MIN_GALLOP. The mergeLo and mergeHi methods nudge it higher for
67 * random data, and lower for highly structured data.
68 */
69 gsize min_gallop;
70
71 /*
72 * The minimum run length. See compute_min_run() for details.
73 */
74 gsize min_run;
75
76 /*
77 * Temp storage for merges.
78 */
79 void *tmp;
80 gsize tmp_length;
81
82 /*
83 * A stack of pending runs yet to be merged. Run i starts at
84 * address base[i] and extends for len[i] elements. It's always
85 * true (so long as the indices are in bounds) that:
86 *
87 * runBase[i] + runLen[i] == runBase[i + 1]
88 *
89 * so we could cut the storage for this, but it's a minor amount,
90 * and keeping all the info explicit simplifies the code.
91 */
92 gsize pending_runs; // Number of pending runs on stack
93 GtkTimSortRun run[GTK_TIM_SORT_MAX_PENDING];
94};
95
96void gtk_tim_sort_init (GtkTimSort *self,
97 gpointer base,
98 gsize size,
99 gsize element_size,
100 GCompareDataFunc compare_func,
101 gpointer data);
102void gtk_tim_sort_finish (GtkTimSort *self);
103
104void gtk_tim_sort_get_runs (GtkTimSort *self,
105 gsize runs[GTK_TIM_SORT_MAX_PENDING + 1]);
106void gtk_tim_sort_set_runs (GtkTimSort *self,
107 gsize *runs);
108void gtk_tim_sort_set_max_merge_size (GtkTimSort *self,
109 gsize max_merge_size);
110
111gsize gtk_tim_sort_get_progress (GtkTimSort *self);
112
113gboolean gtk_tim_sort_step (GtkTimSort *self,
114 GtkTimSortRun *out_change);
115
116void gtk_tim_sort (gpointer base,
117 gsize size,
118 gsize element_size,
119 GCompareDataFunc compare_func,
120 gpointer user_data);
121
122#endif /* __GTK_TIMSORT_PRIVATE_H__ */
123

source code of gtk/gtk/timsort/gtktimsortprivate.h