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 | |
31 | typedef struct _GtkTimSort GtkTimSort; |
32 | typedef struct _GtkTimSortRun GtkTimSortRun; |
33 | |
34 | struct _GtkTimSortRun |
35 | { |
36 | void *base; |
37 | gsize len; |
38 | }; |
39 | |
40 | struct _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 | |
96 | void gtk_tim_sort_init (GtkTimSort *self, |
97 | gpointer base, |
98 | gsize size, |
99 | gsize element_size, |
100 | GCompareDataFunc compare_func, |
101 | gpointer data); |
102 | void gtk_tim_sort_finish (GtkTimSort *self); |
103 | |
104 | void gtk_tim_sort_get_runs (GtkTimSort *self, |
105 | gsize runs[GTK_TIM_SORT_MAX_PENDING + 1]); |
106 | void gtk_tim_sort_set_runs (GtkTimSort *self, |
107 | gsize *runs); |
108 | void gtk_tim_sort_set_max_merge_size (GtkTimSort *self, |
109 | gsize max_merge_size); |
110 | |
111 | gsize gtk_tim_sort_get_progress (GtkTimSort *self); |
112 | |
113 | gboolean gtk_tim_sort_step (GtkTimSort *self, |
114 | GtkTimSortRun *out_change); |
115 | |
116 | void 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 | |