1 /* timsort.c generated by valac 0.19.0.4-d6d4, the Vala compiler
2 * generated from timsort.vala, do not modify */
3
4 /* timsort.vala
5 *
6 * Copyright (C) 2009 Didier Villevalois
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
12
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
17
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this library; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
21 *
22 * Author:
23 * Didier 'Ptitjes Villevalois <ptitjes@free.fr>
24 */
25
26 #include <glib.h>
27 #include <glib-object.h>
28 #include <string.h>
29
30
31 #define GEE_TYPE_TIM_SORT (gee_tim_sort_get_type ())
32 #define GEE_TIM_SORT(obj) (G_TYPE_CHECK_INSTANCE_CAST ((obj), GEE_TYPE_TIM_SORT, GeeTimSort))
33 #define GEE_TIM_SORT_CLASS(klass) (G_TYPE_CHECK_CLASS_CAST ((klass), GEE_TYPE_TIM_SORT, GeeTimSortClass))
34 #define GEE_IS_TIM_SORT(obj) (G_TYPE_CHECK_INSTANCE_TYPE ((obj), GEE_TYPE_TIM_SORT))
35 #define GEE_IS_TIM_SORT_CLASS(klass) (G_TYPE_CHECK_CLASS_TYPE ((klass), GEE_TYPE_TIM_SORT))
36 #define GEE_TIM_SORT_GET_CLASS(obj) (G_TYPE_INSTANCE_GET_CLASS ((obj), GEE_TYPE_TIM_SORT, GeeTimSortClass))
37
38 typedef struct _GeeTimSort GeeTimSort;
39 typedef struct _GeeTimSortClass GeeTimSortClass;
40 typedef struct _GeeTimSortPrivate GeeTimSortPrivate;
41
42 #define GEE_TYPE_ITERABLE (gee_iterable_get_type ())
43 #define GEE_ITERABLE(obj) (G_TYPE_CHECK_INSTANCE_CAST ((obj), GEE_TYPE_ITERABLE, GeeIterable))
44 #define GEE_IS_ITERABLE(obj) (G_TYPE_CHECK_INSTANCE_TYPE ((obj), GEE_TYPE_ITERABLE))
45 #define GEE_ITERABLE_GET_INTERFACE(obj) (G_TYPE_INSTANCE_GET_INTERFACE ((obj), GEE_TYPE_ITERABLE, GeeIterableIface))
46
47 typedef struct _GeeIterable GeeIterable;
48 typedef struct _GeeIterableIface GeeIterableIface;
49
50 #define GEE_TYPE_ITERATOR (gee_iterator_get_type ())
51 #define GEE_ITERATOR(obj) (G_TYPE_CHECK_INSTANCE_CAST ((obj), GEE_TYPE_ITERATOR, GeeIterator))
52 #define GEE_IS_ITERATOR(obj) (G_TYPE_CHECK_INSTANCE_TYPE ((obj), GEE_TYPE_ITERATOR))
53 #define GEE_ITERATOR_GET_INTERFACE(obj) (G_TYPE_INSTANCE_GET_INTERFACE ((obj), GEE_TYPE_ITERATOR, GeeIteratorIface))
54
55 typedef struct _GeeIterator GeeIterator;
56 typedef struct _GeeIteratorIface GeeIteratorIface;
57
58 #define GEE_TYPE_COLLECTION (gee_collection_get_type ())
59 #define GEE_COLLECTION(obj) (G_TYPE_CHECK_INSTANCE_CAST ((obj), GEE_TYPE_COLLECTION, GeeCollection))
60 #define GEE_IS_COLLECTION(obj) (G_TYPE_CHECK_INSTANCE_TYPE ((obj), GEE_TYPE_COLLECTION))
61 #define GEE_COLLECTION_GET_INTERFACE(obj) (G_TYPE_INSTANCE_GET_INTERFACE ((obj), GEE_TYPE_COLLECTION, GeeCollectionIface))
62
63 typedef struct _GeeCollection GeeCollection;
64 typedef struct _GeeCollectionIface GeeCollectionIface;
65
66 #define GEE_TYPE_LIST (gee_list_get_type ())
67 #define GEE_LIST(obj) (G_TYPE_CHECK_INSTANCE_CAST ((obj), GEE_TYPE_LIST, GeeList))
68 #define GEE_IS_LIST(obj) (G_TYPE_CHECK_INSTANCE_TYPE ((obj), GEE_TYPE_LIST))
69 #define GEE_LIST_GET_INTERFACE(obj) (G_TYPE_INSTANCE_GET_INTERFACE ((obj), GEE_TYPE_LIST, GeeListIface))
70
71 typedef struct _GeeList GeeList;
72 typedef struct _GeeListIface GeeListIface;
73
74 #define GEE_TYPE_BIDIR_ITERATOR (gee_bidir_iterator_get_type ())
75 #define GEE_BIDIR_ITERATOR(obj) (G_TYPE_CHECK_INSTANCE_CAST ((obj), GEE_TYPE_BIDIR_ITERATOR, GeeBidirIterator))
76 #define GEE_IS_BIDIR_ITERATOR(obj) (G_TYPE_CHECK_INSTANCE_TYPE ((obj), GEE_TYPE_BIDIR_ITERATOR))
77 #define GEE_BIDIR_ITERATOR_GET_INTERFACE(obj) (G_TYPE_INSTANCE_GET_INTERFACE ((obj), GEE_TYPE_BIDIR_ITERATOR, GeeBidirIteratorIface))
78
79 typedef struct _GeeBidirIterator GeeBidirIterator;
80 typedef struct _GeeBidirIteratorIface GeeBidirIteratorIface;
81
82 #define GEE_TYPE_LIST_ITERATOR (gee_list_iterator_get_type ())
83 #define GEE_LIST_ITERATOR(obj) (G_TYPE_CHECK_INSTANCE_CAST ((obj), GEE_TYPE_LIST_ITERATOR, GeeListIterator))
84 #define GEE_IS_LIST_ITERATOR(obj) (G_TYPE_CHECK_INSTANCE_TYPE ((obj), GEE_TYPE_LIST_ITERATOR))
85 #define GEE_LIST_ITERATOR_GET_INTERFACE(obj) (G_TYPE_INSTANCE_GET_INTERFACE ((obj), GEE_TYPE_LIST_ITERATOR, GeeListIteratorIface))
86
87 typedef struct _GeeListIterator GeeListIterator;
88 typedef struct _GeeListIteratorIface GeeListIteratorIface;
89 typedef struct _GeeTimSortSlice GeeTimSortSlice;
90 #define _g_object_unref0(var) ((var == NULL) ? NULL : (var = (g_object_unref (var), NULL)))
91
92 #define GEE_TYPE_ABSTRACT_COLLECTION (gee_abstract_collection_get_type ())
93 #define GEE_ABSTRACT_COLLECTION(obj) (G_TYPE_CHECK_INSTANCE_CAST ((obj), GEE_TYPE_ABSTRACT_COLLECTION, GeeAbstractCollection))
94 #define GEE_ABSTRACT_COLLECTION_CLASS(klass) (G_TYPE_CHECK_CLASS_CAST ((klass), GEE_TYPE_ABSTRACT_COLLECTION, GeeAbstractCollectionClass))
95 #define GEE_IS_ABSTRACT_COLLECTION(obj) (G_TYPE_CHECK_INSTANCE_TYPE ((obj), GEE_TYPE_ABSTRACT_COLLECTION))
96 #define GEE_IS_ABSTRACT_COLLECTION_CLASS(klass) (G_TYPE_CHECK_CLASS_TYPE ((klass), GEE_TYPE_ABSTRACT_COLLECTION))
97 #define GEE_ABSTRACT_COLLECTION_GET_CLASS(obj) (G_TYPE_INSTANCE_GET_CLASS ((obj), GEE_TYPE_ABSTRACT_COLLECTION, GeeAbstractCollectionClass))
98
99 typedef struct _GeeAbstractCollection GeeAbstractCollection;
100 typedef struct _GeeAbstractCollectionClass GeeAbstractCollectionClass;
101
102 #define GEE_TYPE_ABSTRACT_LIST (gee_abstract_list_get_type ())
103 #define GEE_ABSTRACT_LIST(obj) (G_TYPE_CHECK_INSTANCE_CAST ((obj), GEE_TYPE_ABSTRACT_LIST, GeeAbstractList))
104 #define GEE_ABSTRACT_LIST_CLASS(klass) (G_TYPE_CHECK_CLASS_CAST ((klass), GEE_TYPE_ABSTRACT_LIST, GeeAbstractListClass))
105 #define GEE_IS_ABSTRACT_LIST(obj) (G_TYPE_CHECK_INSTANCE_TYPE ((obj), GEE_TYPE_ABSTRACT_LIST))
106 #define GEE_IS_ABSTRACT_LIST_CLASS(klass) (G_TYPE_CHECK_CLASS_TYPE ((klass), GEE_TYPE_ABSTRACT_LIST))
107 #define GEE_ABSTRACT_LIST_GET_CLASS(obj) (G_TYPE_INSTANCE_GET_CLASS ((obj), GEE_TYPE_ABSTRACT_LIST, GeeAbstractListClass))
108
109 typedef struct _GeeAbstractList GeeAbstractList;
110 typedef struct _GeeAbstractListClass GeeAbstractListClass;
111
112 #define GEE_TYPE_ARRAY_LIST (gee_array_list_get_type ())
113 #define GEE_ARRAY_LIST(obj) (G_TYPE_CHECK_INSTANCE_CAST ((obj), GEE_TYPE_ARRAY_LIST, GeeArrayList))
114 #define GEE_ARRAY_LIST_CLASS(klass) (G_TYPE_CHECK_CLASS_CAST ((klass), GEE_TYPE_ARRAY_LIST, GeeArrayListClass))
115 #define GEE_IS_ARRAY_LIST(obj) (G_TYPE_CHECK_INSTANCE_TYPE ((obj), GEE_TYPE_ARRAY_LIST))
116 #define GEE_IS_ARRAY_LIST_CLASS(klass) (G_TYPE_CHECK_CLASS_TYPE ((klass), GEE_TYPE_ARRAY_LIST))
117 #define GEE_ARRAY_LIST_GET_CLASS(obj) (G_TYPE_INSTANCE_GET_CLASS ((obj), GEE_TYPE_ARRAY_LIST, GeeArrayListClass))
118
119 typedef struct _GeeArrayList GeeArrayList;
120 typedef struct _GeeArrayListClass GeeArrayListClass;
121 #define _g_destroy_func0(var) (((var == NULL) || (g_destroy_func == NULL)) ? NULL : (var = (g_destroy_func (var), NULL)))
122 typedef struct _GeeAbstractCollectionPrivate GeeAbstractCollectionPrivate;
123 typedef struct _GeeAbstractListPrivate GeeAbstractListPrivate;
124 typedef struct _GeeArrayListPrivate GeeArrayListPrivate;
125 #define _gee_tim_sort_slice_free0(var) ((var == NULL) ? NULL : (var = (gee_tim_sort_slice_free (var), NULL)))
126 #define _vala_assert(expr, msg) if G_LIKELY (expr) ; else g_assertion_message_expr (G_LOG_DOMAIN, __FILE__, __LINE__, G_STRFUNC, msg);
127
128 struct _GeeTimSort {
129 GObject parent_instance;
130 GeeTimSortPrivate * priv;
131 };
132
133 struct _GeeTimSortClass {
134 GObjectClass parent_class;
135 };
136
137 struct _GeeIteratorIface {
138 GTypeInterface parent_iface;
139 gboolean (*next) (GeeIterator* self);
140 gboolean (*has_next) (GeeIterator* self);
141 gboolean (*first) (GeeIterator* self);
142 gpointer (*get) (GeeIterator* self);
143 void (*remove) (GeeIterator* self);
144 };
145
146 struct _GeeIterableIface {
147 GTypeInterface parent_iface;
148 GeeIterator* (*iterator) (GeeIterable* self);
149 GType (*get_element_type) (GeeIterable* self);
150 };
151
152 struct _GeeCollectionIface {
153 GTypeInterface parent_iface;
154 gboolean (*contains) (GeeCollection* self, gconstpointer item);
155 gboolean (*add) (GeeCollection* self, gconstpointer item);
156 gboolean (*remove) (GeeCollection* self, gconstpointer item);
157 void (*clear) (GeeCollection* self);
158 gboolean (*add_all) (GeeCollection* self, GeeCollection* collection);
159 gboolean (*contains_all) (GeeCollection* self, GeeCollection* collection);
160 gboolean (*remove_all) (GeeCollection* self, GeeCollection* collection);
161 gboolean (*retain_all) (GeeCollection* self, GeeCollection* collection);
162 gpointer* (*to_array) (GeeCollection* self, int* result_length1);
163 gint (*get_size) (GeeCollection* self);
164 gboolean (*get_is_empty) (GeeCollection* self);
165 GeeCollection* (*get_read_only_view) (GeeCollection* self);
166 };
167
168 struct _GeeBidirIteratorIface {
169 GTypeInterface parent_iface;
170 gboolean (*previous) (GeeBidirIterator* self);
171 gboolean (*has_previous) (GeeBidirIterator* self);
172 gboolean (*last) (GeeBidirIterator* self);
173 };
174
175 struct _GeeListIteratorIface {
176 GTypeInterface parent_iface;
177 void (*set) (GeeListIterator* self, gconstpointer item);
178 void (*insert) (GeeListIterator* self, gconstpointer item);
179 void (*add) (GeeListIterator* self, gconstpointer item);
180 gint (*index) (GeeListIterator* self);
181 };
182
183 struct _GeeListIface {
184 GTypeInterface parent_iface;
185 GeeListIterator* (*list_iterator) (GeeList* self);
186 gpointer (*get) (GeeList* self, gint index);
187 void (*set) (GeeList* self, gint index, gconstpointer item);
188 gint (*index_of) (GeeList* self, gconstpointer item);
189 void (*insert) (GeeList* self, gint index, gconstpointer item);
190 gpointer (*remove_at) (GeeList* self, gint index);
191 GeeList* (*slice) (GeeList* self, gint start, gint stop);
192 gpointer (*first) (GeeList* self);
193 gpointer (*last) (GeeList* self);
194 void (*insert_all) (GeeList* self, gint index, GeeCollection* collection);
195 void (*sort) (GeeList* self, GCompareFunc compare_func);
196 GeeList* (*get_read_only_view) (GeeList* self);
197 };
198
199 struct _GeeTimSortPrivate {
200 GType g_type;
201 GBoxedCopyFunc g_dup_func;
202 GDestroyNotify g_destroy_func;
203 GeeList* list_collection;
204 gpointer* array;
205 gint array_length1;
206 gint _array_size_;
207 void** list;
208 gint index;
209 gint size;
210 GeeTimSortSlice** pending;
211 gint pending_length1;
212 gint _pending_size_;
213 gint minimum_gallop;
214 GCompareFunc compare;
215 GCompareDataFunc compare_data;
216 gpointer compare_data_target;
217 GDestroyNotify compare_data_target_destroy_notify;
218 };
219
220 struct _GeeAbstractCollection {
221 GObject parent_instance;
222 GeeAbstractCollectionPrivate * priv;
223 };
224
225 struct _GeeAbstractCollectionClass {
226 GObjectClass parent_class;
227 gboolean (*contains) (GeeAbstractCollection* self, gconstpointer item);
228 gboolean (*add) (GeeAbstractCollection* self, gconstpointer item);
229 gboolean (*remove) (GeeAbstractCollection* self, gconstpointer item);
230 void (*clear) (GeeAbstractCollection* self);
231 gpointer* (*to_array) (GeeAbstractCollection* self, int* result_length1);
232 gboolean (*add_all) (GeeAbstractCollection* self, GeeCollection* collection);
233 gboolean (*contains_all) (GeeAbstractCollection* self, GeeCollection* collection);
234 gboolean (*remove_all) (GeeAbstractCollection* self, GeeCollection* collection);
235 gboolean (*retain_all) (GeeAbstractCollection* self, GeeCollection* collection);
236 GeeIterator* (*iterator) (GeeAbstractCollection* self);
237 gint (*get_size) (GeeAbstractCollection* self);
238 gboolean (*get_is_empty) (GeeAbstractCollection* self);
239 GeeCollection* (*get_read_only_view) (GeeAbstractCollection* self);
240 };
241
242 struct _GeeAbstractList {
243 GeeAbstractCollection parent_instance;
244 GeeAbstractListPrivate * priv;
245 };
246
247 struct _GeeAbstractListClass {
248 GeeAbstractCollectionClass parent_class;
249 GeeListIterator* (*list_iterator) (GeeAbstractList* self);
250 gpointer (*get) (GeeAbstractList* self, gint index);
251 void (*set) (GeeAbstractList* self, gint index, gconstpointer item);
252 gint (*index_of) (GeeAbstractList* self, gconstpointer item);
253 void (*insert) (GeeAbstractList* self, gint index, gconstpointer item);
254 gpointer (*remove_at) (GeeAbstractList* self, gint index);
255 GeeList* (*slice) (GeeAbstractList* self, gint start, gint stop);
256 gpointer (*first) (GeeAbstractList* self);
257 gpointer (*last) (GeeAbstractList* self);
258 void (*insert_all) (GeeAbstractList* self, gint index, GeeCollection* collection);
259 GeeList* (*get_read_only_view) (GeeAbstractList* self);
260 };
261
262 struct _GeeArrayList {
263 GeeAbstractList parent_instance;
264 GeeArrayListPrivate * priv;
265 gpointer* _items;
266 gint _items_length1;
267 gint __items_size_;
268 gint _size;
269 };
270
271 struct _GeeArrayListClass {
272 GeeAbstractListClass parent_class;
273 };
274
275 struct _GeeTimSortSlice {
276 void** list;
277 void** new_list;
278 gint index;
279 gint length;
280 };
281
282 typedef gboolean (*GeeTimSortLowerFunc) (gconstpointer left, gconstpointer right, void* user_data);
283
284 static gpointer gee_tim_sort_parent_class = NULL;
285
286 GType gee_tim_sort_get_type (void) G_GNUC_CONST;
287 GType gee_iterator_get_type (void) G_GNUC_CONST;
288 GType gee_iterable_get_type (void) G_GNUC_CONST;
289 GType gee_collection_get_type (void) G_GNUC_CONST;
290 GType gee_bidir_iterator_get_type (void) G_GNUC_CONST;
291 GType gee_list_iterator_get_type (void) G_GNUC_CONST;
292 GType gee_list_get_type (void) G_GNUC_CONST;
293 static void gee_tim_sort_slice_free (GeeTimSortSlice* self);
294 #define GEE_TIM_SORT_GET_PRIVATE(o) (G_TYPE_INSTANCE_GET_PRIVATE ((o), GEE_TYPE_TIM_SORT, GeeTimSortPrivate))
295 enum {
296 GEE_TIM_SORT_DUMMY_PROPERTY,
297 GEE_TIM_SORT_G_TYPE,
298 GEE_TIM_SORT_G_DUP_FUNC,
299 GEE_TIM_SORT_G_DESTROY_FUNC
300 };
301 #define GEE_TIM_SORT_MINIMUM_GALLOP 7
302 void gee_tim_sort_sort (GType g_type, GBoxedCopyFunc g_dup_func, GDestroyNotify g_destroy_func, GeeList* list, GCompareFunc compare);
303 GType gee_abstract_collection_get_type (void) G_GNUC_CONST;
304 GType gee_abstract_list_get_type (void) G_GNUC_CONST;
305 GType gee_array_list_get_type (void) G_GNUC_CONST;
306 static void gee_tim_sort_sort_arraylist (GType g_type, GBoxedCopyFunc g_dup_func, GDestroyNotify g_destroy_func, GeeArrayList* list, GCompareFunc compare, GCompareDataFunc compare_data, void* compare_data_target);
307 static void gee_tim_sort_sort_list (GType g_type, GBoxedCopyFunc g_dup_func, GDestroyNotify g_destroy_func, GeeList* list, GCompareFunc compare, GCompareDataFunc compare_data, void* compare_data_target);
308 void gee_tim_sort_sort_with_data (GType g_type, GBoxedCopyFunc g_dup_func, GDestroyNotify g_destroy_func, GeeList* list, GCompareDataFunc compare_data, void* compare_data_target);
309 GeeTimSort* gee_tim_sort_new (GType g_type, GBoxedCopyFunc g_dup_func, GDestroyNotify g_destroy_func);
310 GeeTimSort* gee_tim_sort_construct (GType object_type, GType g_type, GBoxedCopyFunc g_dup_func, GDestroyNotify g_destroy_func);
311 gpointer* gee_collection_to_array (GeeCollection* self, int* result_length1);
312 gint gee_collection_get_size (GeeCollection* self);
313 static void gee_tim_sort_do_sort (GeeTimSort* self);
314 void gee_collection_clear (GeeCollection* self);
315 gboolean gee_collection_add (GeeCollection* self, gconstpointer item);
316 static GeeTimSortSlice* gee_tim_sort_slice_new (void** list, gint index, gint length);
317 static GeeTimSortSlice* gee_tim_sort_slice_new (void** list, gint index, gint length);
318 static gint gee_tim_sort_compute_minimum_run_length (GeeTimSort* self, gint length);
319 static GeeTimSortSlice* gee_tim_sort_compute_longest_run (GeeTimSort* self, GeeTimSortSlice* a, gboolean* descending);
320 static void gee_tim_sort_slice_reverse (GeeTimSortSlice* self);
321 static void gee_tim_sort_insertion_sort (GeeTimSort* self, GeeTimSortSlice* a, gint offset);
322 static inline void gee_tim_sort_slice_shorten_start (GeeTimSortSlice* self, gint n);
323 static void _vala_array_add1 (GeeTimSortSlice*** array, int* length, int* size, GeeTimSortSlice* value);
324 static void gee_tim_sort_merge_collapse (GeeTimSort* self);
325 static void gee_tim_sort_merge_force_collapse (GeeTimSort* self);
326 static inline gboolean gee_tim_sort_lower_than (GeeTimSort* self, gconstpointer left, gconstpointer right);
327 static inline gboolean gee_tim_sort_lower_than_or_equal_to (GeeTimSort* self, gconstpointer left, gconstpointer right);
328 static void gee_tim_sort_merge_at (GeeTimSort* self, gint index);
329 static gint gee_tim_sort_gallop_rightmost (GeeTimSort* self, gconstpointer key, GeeTimSortSlice* a, gint hint);
330 static inline void* gee_tim_sort_slice_peek_first (GeeTimSortSlice* self);
331 static gint gee_tim_sort_gallop_leftmost (GeeTimSort* self, gconstpointer key, GeeTimSortSlice* a, gint hint);
332 static inline void* gee_tim_sort_slice_peek_last (GeeTimSortSlice* self);
333 static void gee_tim_sort_merge_low (GeeTimSort* self, GeeTimSortSlice* a, GeeTimSortSlice* b);
334 static void gee_tim_sort_merge_high (GeeTimSort* self, GeeTimSortSlice* a, GeeTimSortSlice* b);
335 static void gee_tim_sort_slice_copy (GeeTimSortSlice* self);
336 static inline void* gee_tim_sort_slice_pop_first (GeeTimSortSlice* self);
337 static inline void gee_tim_sort_slice_merge_in (GeeTimSortSlice* self, void** dest_array, gint index, gint dest_index, gint count);
338 static inline void* gee_tim_sort_slice_pop_last (GeeTimSortSlice* self);
339 static inline void gee_tim_sort_slice_merge_in_reversed (GeeTimSortSlice* self, void** dest_array, gint index, gint dest_index, gint count);
340 static inline void gee_tim_sort_slice_shorten_end (GeeTimSortSlice* self, gint n);
341 static void gee_tim_sort_slice_instance_init (GeeTimSortSlice * self);
342 static inline void gee_tim_sort_slice_swap (GeeTimSortSlice* self, gint i, gint j);
343 static void gee_tim_sort_finalize (GObject* obj);
344 static void _vala_gee_tim_sort_get_property (GObject * object, guint property_id, GValue * value, GParamSpec * pspec);
345 static void _vala_gee_tim_sort_set_property (GObject * object, guint property_id, const GValue * value, GParamSpec * pspec);
346 static void _vala_array_destroy (gpointer array, gint array_length, GDestroyNotify destroy_func);
347 static void _vala_array_free (gpointer array, gint array_length, GDestroyNotify destroy_func);
348 static void _vala_array_move (gpointer array, gsize element_size, gint src, gint dest, gint length);
349
350
gee_tim_sort_sort(GType g_type,GBoxedCopyFunc g_dup_func,GDestroyNotify g_destroy_func,GeeList * list,GCompareFunc compare)351 void gee_tim_sort_sort (GType g_type, GBoxedCopyFunc g_dup_func, GDestroyNotify g_destroy_func, GeeList* list, GCompareFunc compare) {
352 GeeList* _tmp0_;
353 g_return_if_fail (list != NULL);
354 _tmp0_ = list;
355 if (G_TYPE_CHECK_INSTANCE_TYPE (_tmp0_, GEE_TYPE_ARRAY_LIST)) {
356 GeeList* _tmp1_;
357 GCompareFunc _tmp2_;
358 _tmp1_ = list;
359 _tmp2_ = compare;
360 gee_tim_sort_sort_arraylist (g_type, (GBoxedCopyFunc) g_dup_func, g_destroy_func, G_TYPE_CHECK_INSTANCE_CAST (_tmp1_, GEE_TYPE_ARRAY_LIST, GeeArrayList), _tmp2_, NULL, NULL);
361 } else {
362 GeeList* _tmp3_;
363 GCompareFunc _tmp4_;
364 _tmp3_ = list;
365 _tmp4_ = compare;
366 gee_tim_sort_sort_list (g_type, (GBoxedCopyFunc) g_dup_func, g_destroy_func, _tmp3_, _tmp4_, NULL, NULL);
367 }
368 }
369
370
gee_tim_sort_sort_with_data(GType g_type,GBoxedCopyFunc g_dup_func,GDestroyNotify g_destroy_func,GeeList * list,GCompareDataFunc compare_data,void * compare_data_target)371 void gee_tim_sort_sort_with_data (GType g_type, GBoxedCopyFunc g_dup_func, GDestroyNotify g_destroy_func, GeeList* list, GCompareDataFunc compare_data, void* compare_data_target) {
372 GeeList* _tmp0_;
373 g_return_if_fail (list != NULL);
374 _tmp0_ = list;
375 if (G_TYPE_CHECK_INSTANCE_TYPE (_tmp0_, GEE_TYPE_ARRAY_LIST)) {
376 GeeList* _tmp1_;
377 GCompareDataFunc _tmp2_;
378 void* _tmp2__target;
379 _tmp1_ = list;
380 _tmp2_ = compare_data;
381 _tmp2__target = compare_data_target;
382 gee_tim_sort_sort_arraylist (g_type, (GBoxedCopyFunc) g_dup_func, g_destroy_func, G_TYPE_CHECK_INSTANCE_CAST (_tmp1_, GEE_TYPE_ARRAY_LIST, GeeArrayList), NULL, _tmp2_, _tmp2__target);
383 } else {
384 GeeList* _tmp3_;
385 GCompareDataFunc _tmp4_;
386 void* _tmp4__target;
387 _tmp3_ = list;
388 _tmp4_ = compare_data;
389 _tmp4__target = compare_data_target;
390 gee_tim_sort_sort_list (g_type, (GBoxedCopyFunc) g_dup_func, g_destroy_func, _tmp3_, NULL, _tmp4_, _tmp4__target);
391 }
392 }
393
394
_g_object_ref0(gpointer self)395 static gpointer _g_object_ref0 (gpointer self) {
396 return self ? g_object_ref (self) : NULL;
397 }
398
399
gee_tim_sort_sort_list(GType g_type,GBoxedCopyFunc g_dup_func,GDestroyNotify g_destroy_func,GeeList * list,GCompareFunc compare,GCompareDataFunc compare_data,void * compare_data_target)400 static void gee_tim_sort_sort_list (GType g_type, GBoxedCopyFunc g_dup_func, GDestroyNotify g_destroy_func, GeeList* list, GCompareFunc compare, GCompareDataFunc compare_data, void* compare_data_target) {
401 gboolean _tmp0_ = FALSE;
402 GCompareFunc _tmp1_;
403 gboolean _tmp3_;
404 GeeTimSort* _tmp4_;
405 GeeTimSort* helper;
406 GeeTimSort* _tmp5_;
407 GeeList* _tmp6_;
408 GeeList* _tmp7_;
409 GeeTimSort* _tmp8_;
410 GeeList* _tmp9_;
411 gint _tmp10_ = 0;
412 gpointer* _tmp11_ = NULL;
413 GeeTimSort* _tmp12_;
414 GeeTimSort* _tmp13_;
415 gpointer* _tmp14_;
416 gint _tmp14__length1;
417 GeeTimSort* _tmp15_;
418 GeeTimSort* _tmp16_;
419 GeeList* _tmp17_;
420 gint _tmp18_;
421 gint _tmp19_;
422 GeeTimSort* _tmp20_;
423 GCompareFunc _tmp21_;
424 GeeTimSort* _tmp22_;
425 GCompareDataFunc _tmp23_;
426 void* _tmp23__target;
427 GeeTimSort* _tmp24_;
428 GeeList* _tmp25_;
429 GeeTimSort* _tmp26_;
430 gpointer* _tmp27_;
431 gint _tmp27__length1;
432 g_return_if_fail (list != NULL);
433 _tmp1_ = compare;
434 if (_tmp1_ != NULL) {
435 _tmp0_ = TRUE;
436 } else {
437 GCompareDataFunc _tmp2_;
438 void* _tmp2__target;
439 _tmp2_ = compare_data;
440 _tmp2__target = compare_data_target;
441 _tmp0_ = _tmp2_ != NULL;
442 }
443 _tmp3_ = _tmp0_;
444 _vala_assert (_tmp3_, "compare != null || compare_data != null");
445 _tmp4_ = gee_tim_sort_new (g_type, (GBoxedCopyFunc) g_dup_func, g_destroy_func);
446 helper = _tmp4_;
447 _tmp5_ = helper;
448 _tmp6_ = list;
449 _tmp7_ = _g_object_ref0 (_tmp6_);
450 _g_object_unref0 (_tmp5_->priv->list_collection);
451 _tmp5_->priv->list_collection = _tmp7_;
452 _tmp8_ = helper;
453 _tmp9_ = list;
454 _tmp11_ = gee_collection_to_array ((GeeCollection*) _tmp9_, &_tmp10_);
455 _tmp8_->priv->array = (_vala_array_free (_tmp8_->priv->array, _tmp8_->priv->array_length1, (GDestroyNotify) g_destroy_func), NULL);
456 _tmp8_->priv->array = _tmp11_;
457 _tmp8_->priv->array_length1 = _tmp10_;
458 _tmp8_->priv->_array_size_ = _tmp8_->priv->array_length1;
459 _tmp12_ = helper;
460 _tmp13_ = helper;
461 _tmp14_ = _tmp13_->priv->array;
462 _tmp14__length1 = _tmp13_->priv->array_length1;
463 _tmp12_->priv->list = _tmp14_;
464 _tmp15_ = helper;
465 _tmp15_->priv->index = 0;
466 _tmp16_ = helper;
467 _tmp17_ = list;
468 _tmp18_ = gee_collection_get_size ((GeeCollection*) _tmp17_);
469 _tmp19_ = _tmp18_;
470 _tmp16_->priv->size = _tmp19_;
471 _tmp20_ = helper;
472 _tmp21_ = compare;
473 _tmp20_->priv->compare = _tmp21_;
474 _tmp22_ = helper;
475 _tmp23_ = compare_data;
476 _tmp23__target = compare_data_target;
477 (_tmp22_->priv->compare_data_target_destroy_notify == NULL) ? NULL : (_tmp22_->priv->compare_data_target_destroy_notify (_tmp22_->priv->compare_data_target), NULL);
478 _tmp22_->priv->compare_data = NULL;
479 _tmp22_->priv->compare_data_target = NULL;
480 _tmp22_->priv->compare_data_target_destroy_notify = NULL;
481 _tmp22_->priv->compare_data = _tmp23_;
482 _tmp22_->priv->compare_data_target = _tmp23__target;
483 _tmp22_->priv->compare_data_target_destroy_notify = NULL;
484 _tmp24_ = helper;
485 gee_tim_sort_do_sort (_tmp24_);
486 _tmp25_ = list;
487 gee_collection_clear ((GeeCollection*) _tmp25_);
488 _tmp26_ = helper;
489 _tmp27_ = _tmp26_->priv->array;
490 _tmp27__length1 = _tmp26_->priv->array_length1;
491 {
492 gpointer* item_collection = NULL;
493 gint item_collection_length1 = 0;
494 gint _item_collection_size_ = 0;
495 gint item_it = 0;
496 item_collection = _tmp27_;
497 item_collection_length1 = _tmp27__length1;
498 for (item_it = 0; item_it < _tmp27__length1; item_it = item_it + 1) {
499 gpointer _tmp28_;
500 gpointer item = NULL;
501 _tmp28_ = ((item_collection[item_it] != NULL) && (g_dup_func != NULL)) ? g_dup_func ((gpointer) item_collection[item_it]) : ((gpointer) item_collection[item_it]);
502 item = _tmp28_;
503 {
504 GeeList* _tmp29_;
505 gconstpointer _tmp30_;
506 _tmp29_ = list;
507 _tmp30_ = item;
508 gee_collection_add ((GeeCollection*) _tmp29_, _tmp30_);
509 _g_destroy_func0 (item);
510 }
511 }
512 }
513 _g_object_unref0 (helper);
514 }
515
516
gee_tim_sort_sort_arraylist(GType g_type,GBoxedCopyFunc g_dup_func,GDestroyNotify g_destroy_func,GeeArrayList * list,GCompareFunc compare,GCompareDataFunc compare_data,void * compare_data_target)517 static void gee_tim_sort_sort_arraylist (GType g_type, GBoxedCopyFunc g_dup_func, GDestroyNotify g_destroy_func, GeeArrayList* list, GCompareFunc compare, GCompareDataFunc compare_data, void* compare_data_target) {
518 gboolean _tmp0_ = FALSE;
519 GCompareFunc _tmp1_;
520 gboolean _tmp3_;
521 GeeTimSort* _tmp4_;
522 GeeTimSort* helper;
523 GeeArrayList* _tmp5_;
524 GeeList* _tmp6_;
525 GeeArrayList* _tmp7_;
526 gpointer* _tmp8_;
527 gint _tmp8__length1;
528 GeeArrayList* _tmp9_;
529 gint _tmp10_;
530 GCompareFunc _tmp11_;
531 GCompareDataFunc _tmp12_;
532 void* _tmp12__target;
533 g_return_if_fail (list != NULL);
534 _tmp1_ = compare;
535 if (_tmp1_ != NULL) {
536 _tmp0_ = TRUE;
537 } else {
538 GCompareDataFunc _tmp2_;
539 void* _tmp2__target;
540 _tmp2_ = compare_data;
541 _tmp2__target = compare_data_target;
542 _tmp0_ = _tmp2_ != NULL;
543 }
544 _tmp3_ = _tmp0_;
545 _vala_assert (_tmp3_, "compare != null || compare_data != null");
546 _tmp4_ = gee_tim_sort_new (g_type, (GBoxedCopyFunc) g_dup_func, g_destroy_func);
547 helper = _tmp4_;
548 _tmp5_ = list;
549 _tmp6_ = _g_object_ref0 ((GeeList*) _tmp5_);
550 _g_object_unref0 (helper->priv->list_collection);
551 helper->priv->list_collection = _tmp6_;
552 _tmp7_ = list;
553 _tmp8_ = _tmp7_->_items;
554 _tmp8__length1 = _tmp7_->_items_length1;
555 helper->priv->list = _tmp8_;
556 helper->priv->index = 0;
557 _tmp9_ = list;
558 _tmp10_ = _tmp9_->_size;
559 helper->priv->size = _tmp10_;
560 _tmp11_ = compare;
561 helper->priv->compare = _tmp11_;
562 _tmp12_ = compare_data;
563 _tmp12__target = compare_data_target;
564 (helper->priv->compare_data_target_destroy_notify == NULL) ? NULL : (helper->priv->compare_data_target_destroy_notify (helper->priv->compare_data_target), NULL);
565 helper->priv->compare_data = NULL;
566 helper->priv->compare_data_target = NULL;
567 helper->priv->compare_data_target_destroy_notify = NULL;
568 helper->priv->compare_data = _tmp12_;
569 helper->priv->compare_data_target = _tmp12__target;
570 helper->priv->compare_data_target_destroy_notify = NULL;
571 gee_tim_sort_do_sort (helper);
572 _g_object_unref0 (helper);
573 }
574
575
_vala_array_add1(GeeTimSortSlice *** array,int * length,int * size,GeeTimSortSlice * value)576 static void _vala_array_add1 (GeeTimSortSlice*** array, int* length, int* size, GeeTimSortSlice* value) {
577 if ((*length) == (*size)) {
578 *size = (*size) ? (2 * (*size)) : 4;
579 *array = g_renew (GeeTimSortSlice*, *array, (*size) + 1);
580 }
581 (*array)[(*length)++] = value;
582 (*array)[*length] = NULL;
583 }
584
585
gee_tim_sort_do_sort(GeeTimSort * self)586 static void gee_tim_sort_do_sort (GeeTimSort* self) {
587 gint _tmp0_;
588 GeeTimSortSlice** _tmp1_ = NULL;
589 void** _tmp2_;
590 gint _tmp3_;
591 gint _tmp4_;
592 GeeTimSortSlice* _tmp5_;
593 GeeTimSortSlice* remaining;
594 GeeTimSortSlice* _tmp6_;
595 gint _tmp7_;
596 gint _tmp8_ = 0;
597 gint minimum_length;
598 GeeTimSortSlice* _tmp33_;
599 gint _tmp34_;
600 gint _tmp35_;
601 GeeTimSortSlice** _tmp36_;
602 gint _tmp36__length1;
603 GeeTimSortSlice** _tmp37_;
604 gint _tmp37__length1;
605 GeeTimSortSlice* _tmp38_;
606 gint _tmp39_;
607 GeeTimSortSlice** _tmp40_;
608 gint _tmp40__length1;
609 GeeTimSortSlice* _tmp41_;
610 gint _tmp42_;
611 gint _tmp43_;
612 g_return_if_fail (self != NULL);
613 _tmp0_ = self->priv->size;
614 if (_tmp0_ < 2) {
615 return;
616 }
617 _tmp1_ = g_new0 (GeeTimSortSlice*, 0 + 1);
618 self->priv->pending = (_vala_array_free (self->priv->pending, self->priv->pending_length1, (GDestroyNotify) gee_tim_sort_slice_free), NULL);
619 self->priv->pending = _tmp1_;
620 self->priv->pending_length1 = 0;
621 self->priv->_pending_size_ = self->priv->pending_length1;
622 self->priv->minimum_gallop = GEE_TIM_SORT_MINIMUM_GALLOP;
623 _tmp2_ = self->priv->list;
624 _tmp3_ = self->priv->index;
625 _tmp4_ = self->priv->size;
626 _tmp5_ = gee_tim_sort_slice_new (_tmp2_, _tmp3_, _tmp4_);
627 remaining = _tmp5_;
628 _tmp6_ = remaining;
629 _tmp7_ = _tmp6_->length;
630 _tmp8_ = gee_tim_sort_compute_minimum_run_length (self, _tmp7_);
631 minimum_length = _tmp8_;
632 while (TRUE) {
633 GeeTimSortSlice* _tmp9_;
634 gint _tmp10_;
635 gboolean descending = FALSE;
636 GeeTimSortSlice* _tmp11_;
637 gboolean _tmp12_ = FALSE;
638 GeeTimSortSlice* _tmp13_ = NULL;
639 GeeTimSortSlice* run;
640 gboolean _tmp14_;
641 GeeTimSortSlice* _tmp16_;
642 gint _tmp17_;
643 gint _tmp18_;
644 GeeTimSortSlice* _tmp28_;
645 GeeTimSortSlice* _tmp29_;
646 gint _tmp30_;
647 GeeTimSortSlice** _tmp31_;
648 gint _tmp31__length1;
649 GeeTimSortSlice* _tmp32_;
650 _tmp9_ = remaining;
651 _tmp10_ = _tmp9_->length;
652 if (!(_tmp10_ > 0)) {
653 break;
654 }
655 _tmp11_ = remaining;
656 _tmp13_ = gee_tim_sort_compute_longest_run (self, _tmp11_, &_tmp12_);
657 descending = _tmp12_;
658 run = _tmp13_;
659 _tmp14_ = descending;
660 if (_tmp14_) {
661 GeeTimSortSlice* _tmp15_;
662 _tmp15_ = run;
663 gee_tim_sort_slice_reverse (_tmp15_);
664 }
665 _tmp16_ = run;
666 _tmp17_ = _tmp16_->length;
667 _tmp18_ = minimum_length;
668 if (_tmp17_ < _tmp18_) {
669 GeeTimSortSlice* _tmp19_;
670 gint _tmp20_;
671 gint sorted_count;
672 GeeTimSortSlice* _tmp21_;
673 gint _tmp22_;
674 GeeTimSortSlice* _tmp23_;
675 gint _tmp24_;
676 gint _tmp25_ = 0;
677 GeeTimSortSlice* _tmp26_;
678 gint _tmp27_;
679 _tmp19_ = run;
680 _tmp20_ = _tmp19_->length;
681 sorted_count = _tmp20_;
682 _tmp21_ = run;
683 _tmp22_ = minimum_length;
684 _tmp23_ = remaining;
685 _tmp24_ = _tmp23_->length;
686 _tmp25_ = MIN (_tmp22_, _tmp24_);
687 _tmp21_->length = _tmp25_;
688 _tmp26_ = run;
689 _tmp27_ = sorted_count;
690 gee_tim_sort_insertion_sort (self, _tmp26_, _tmp27_);
691 }
692 _tmp28_ = remaining;
693 _tmp29_ = run;
694 _tmp30_ = _tmp29_->length;
695 gee_tim_sort_slice_shorten_start (_tmp28_, _tmp30_);
696 _tmp31_ = self->priv->pending;
697 _tmp31__length1 = self->priv->pending_length1;
698 _tmp32_ = run;
699 run = NULL;
700 _vala_array_add1 (&self->priv->pending, &self->priv->pending_length1, &self->priv->_pending_size_, _tmp32_);
701 gee_tim_sort_merge_collapse (self);
702 _gee_tim_sort_slice_free0 (run);
703 }
704 _tmp33_ = remaining;
705 _tmp34_ = _tmp33_->index;
706 _tmp35_ = self->priv->size;
707 _vala_assert (_tmp34_ == _tmp35_, "remaining.index == size");
708 gee_tim_sort_merge_force_collapse (self);
709 _tmp36_ = self->priv->pending;
710 _tmp36__length1 = self->priv->pending_length1;
711 _vala_assert (_tmp36__length1 == 1, "pending.length == 1");
712 _tmp37_ = self->priv->pending;
713 _tmp37__length1 = self->priv->pending_length1;
714 _tmp38_ = _tmp37_[0];
715 _tmp39_ = _tmp38_->index;
716 _vala_assert (_tmp39_ == 0, "pending[0].index == 0");
717 _tmp40_ = self->priv->pending;
718 _tmp40__length1 = self->priv->pending_length1;
719 _tmp41_ = _tmp40_[0];
720 _tmp42_ = _tmp41_->length;
721 _tmp43_ = self->priv->size;
722 _vala_assert (_tmp42_ == _tmp43_, "pending[0].length == size");
723 _gee_tim_sort_slice_free0 (remaining);
724 }
725
726
gee_tim_sort_lower_than(GeeTimSort * self,gconstpointer left,gconstpointer right)727 static inline gboolean gee_tim_sort_lower_than (GeeTimSort* self, gconstpointer left, gconstpointer right) {
728 gboolean result = FALSE;
729 GCompareFunc _tmp0_;
730 g_return_val_if_fail (self != NULL, FALSE);
731 _tmp0_ = self->priv->compare;
732 if (_tmp0_ != NULL) {
733 GCompareFunc _tmp1_;
734 gconstpointer _tmp2_;
735 gconstpointer _tmp3_;
736 gint _tmp4_ = 0;
737 _tmp1_ = self->priv->compare;
738 _tmp2_ = left;
739 _tmp3_ = right;
740 _tmp4_ = _tmp1_ (_tmp2_, _tmp3_);
741 result = _tmp4_ < 0;
742 return result;
743 } else {
744 GCompareDataFunc _tmp5_;
745 void* _tmp5__target;
746 gconstpointer _tmp6_;
747 gconstpointer _tmp7_;
748 gint _tmp8_ = 0;
749 _tmp5_ = self->priv->compare_data;
750 _tmp5__target = self->priv->compare_data_target;
751 _tmp6_ = left;
752 _tmp7_ = right;
753 _tmp8_ = _tmp5_ (_tmp6_, _tmp7_, _tmp5__target);
754 result = _tmp8_ < 0;
755 return result;
756 }
757 }
758
759
gee_tim_sort_lower_than_or_equal_to(GeeTimSort * self,gconstpointer left,gconstpointer right)760 static inline gboolean gee_tim_sort_lower_than_or_equal_to (GeeTimSort* self, gconstpointer left, gconstpointer right) {
761 gboolean result = FALSE;
762 GCompareFunc _tmp0_;
763 g_return_val_if_fail (self != NULL, FALSE);
764 _tmp0_ = self->priv->compare;
765 if (_tmp0_ != NULL) {
766 GCompareFunc _tmp1_;
767 gconstpointer _tmp2_;
768 gconstpointer _tmp3_;
769 gint _tmp4_ = 0;
770 _tmp1_ = self->priv->compare;
771 _tmp2_ = left;
772 _tmp3_ = right;
773 _tmp4_ = _tmp1_ (_tmp2_, _tmp3_);
774 result = _tmp4_ <= 0;
775 return result;
776 } else {
777 GCompareDataFunc _tmp5_;
778 void* _tmp5__target;
779 gconstpointer _tmp6_;
780 gconstpointer _tmp7_;
781 gint _tmp8_ = 0;
782 _tmp5_ = self->priv->compare_data;
783 _tmp5__target = self->priv->compare_data_target;
784 _tmp6_ = left;
785 _tmp7_ = right;
786 _tmp8_ = _tmp5_ (_tmp6_, _tmp7_, _tmp5__target);
787 result = _tmp8_ <= 0;
788 return result;
789 }
790 }
791
792
gee_tim_sort_compute_minimum_run_length(GeeTimSort * self,gint length)793 static gint gee_tim_sort_compute_minimum_run_length (GeeTimSort* self, gint length) {
794 gint result = 0;
795 gint run_length;
796 gint _tmp4_;
797 gint _tmp5_;
798 g_return_val_if_fail (self != NULL, 0);
799 run_length = 0;
800 while (TRUE) {
801 gint _tmp0_;
802 gint _tmp1_;
803 gint _tmp2_;
804 gint _tmp3_;
805 _tmp0_ = length;
806 if (!(_tmp0_ >= 64)) {
807 break;
808 }
809 _tmp1_ = run_length;
810 _tmp2_ = length;
811 run_length = _tmp1_ | (_tmp2_ & 1);
812 _tmp3_ = length;
813 length = _tmp3_ >> 1;
814 }
815 _tmp4_ = length;
816 _tmp5_ = run_length;
817 result = _tmp4_ + _tmp5_;
818 return result;
819 }
820
821
gee_tim_sort_compute_longest_run(GeeTimSort * self,GeeTimSortSlice * a,gboolean * descending)822 static GeeTimSortSlice* gee_tim_sort_compute_longest_run (GeeTimSort* self, GeeTimSortSlice* a, gboolean* descending) {
823 gboolean _vala_descending = FALSE;
824 GeeTimSortSlice* result = NULL;
825 gint run_length = 0;
826 GeeTimSortSlice* _tmp0_;
827 gint _tmp1_;
828 GeeTimSortSlice* _tmp55_;
829 void** _tmp56_;
830 GeeTimSortSlice* _tmp57_;
831 gint _tmp58_;
832 gint _tmp59_;
833 GeeTimSortSlice* _tmp60_;
834 g_return_val_if_fail (self != NULL, NULL);
835 g_return_val_if_fail (a != NULL, NULL);
836 _tmp0_ = a;
837 _tmp1_ = _tmp0_->length;
838 if (_tmp1_ <= 1) {
839 GeeTimSortSlice* _tmp2_;
840 gint _tmp3_;
841 _tmp2_ = a;
842 _tmp3_ = _tmp2_->length;
843 run_length = _tmp3_;
844 _vala_descending = FALSE;
845 } else {
846 GeeTimSortSlice* _tmp4_;
847 void** _tmp5_;
848 GeeTimSortSlice* _tmp6_;
849 gint _tmp7_;
850 void* _tmp8_;
851 GeeTimSortSlice* _tmp9_;
852 void** _tmp10_;
853 GeeTimSortSlice* _tmp11_;
854 gint _tmp12_;
855 void* _tmp13_;
856 gboolean _tmp14_ = FALSE;
857 run_length = 2;
858 _tmp4_ = a;
859 _tmp5_ = _tmp4_->list;
860 _tmp6_ = a;
861 _tmp7_ = _tmp6_->index;
862 _tmp8_ = _tmp5_[_tmp7_ + 1];
863 _tmp9_ = a;
864 _tmp10_ = _tmp9_->list;
865 _tmp11_ = a;
866 _tmp12_ = _tmp11_->index;
867 _tmp13_ = _tmp10_[_tmp12_];
868 _tmp14_ = gee_tim_sort_lower_than (self, _tmp8_, _tmp13_);
869 if (_tmp14_) {
870 _vala_descending = TRUE;
871 {
872 GeeTimSortSlice* _tmp15_;
873 gint _tmp16_;
874 gint i;
875 _tmp15_ = a;
876 _tmp16_ = _tmp15_->index;
877 i = _tmp16_ + 2;
878 {
879 gboolean _tmp17_;
880 _tmp17_ = TRUE;
881 while (TRUE) {
882 gboolean _tmp18_;
883 gint _tmp20_;
884 GeeTimSortSlice* _tmp21_;
885 gint _tmp22_;
886 GeeTimSortSlice* _tmp23_;
887 gint _tmp24_;
888 GeeTimSortSlice* _tmp25_;
889 void** _tmp26_;
890 gint _tmp27_;
891 void* _tmp28_;
892 GeeTimSortSlice* _tmp29_;
893 void** _tmp30_;
894 gint _tmp31_;
895 void* _tmp32_;
896 gboolean _tmp33_ = FALSE;
897 _tmp18_ = _tmp17_;
898 if (!_tmp18_) {
899 gint _tmp19_;
900 _tmp19_ = i;
901 i = _tmp19_ + 1;
902 }
903 _tmp17_ = FALSE;
904 _tmp20_ = i;
905 _tmp21_ = a;
906 _tmp22_ = _tmp21_->index;
907 _tmp23_ = a;
908 _tmp24_ = _tmp23_->length;
909 if (!(_tmp20_ < (_tmp22_ + _tmp24_))) {
910 break;
911 }
912 _tmp25_ = a;
913 _tmp26_ = _tmp25_->list;
914 _tmp27_ = i;
915 _tmp28_ = _tmp26_[_tmp27_];
916 _tmp29_ = a;
917 _tmp30_ = _tmp29_->list;
918 _tmp31_ = i;
919 _tmp32_ = _tmp30_[_tmp31_ - 1];
920 _tmp33_ = gee_tim_sort_lower_than (self, _tmp28_, _tmp32_);
921 if (_tmp33_) {
922 gint _tmp34_;
923 _tmp34_ = run_length;
924 run_length = _tmp34_ + 1;
925 } else {
926 break;
927 }
928 }
929 }
930 }
931 } else {
932 _vala_descending = FALSE;
933 {
934 GeeTimSortSlice* _tmp35_;
935 gint _tmp36_;
936 gint i;
937 _tmp35_ = a;
938 _tmp36_ = _tmp35_->index;
939 i = _tmp36_ + 2;
940 {
941 gboolean _tmp37_;
942 _tmp37_ = TRUE;
943 while (TRUE) {
944 gboolean _tmp38_;
945 gint _tmp40_;
946 GeeTimSortSlice* _tmp41_;
947 gint _tmp42_;
948 GeeTimSortSlice* _tmp43_;
949 gint _tmp44_;
950 GeeTimSortSlice* _tmp45_;
951 void** _tmp46_;
952 gint _tmp47_;
953 void* _tmp48_;
954 GeeTimSortSlice* _tmp49_;
955 void** _tmp50_;
956 gint _tmp51_;
957 void* _tmp52_;
958 gboolean _tmp53_ = FALSE;
959 _tmp38_ = _tmp37_;
960 if (!_tmp38_) {
961 gint _tmp39_;
962 _tmp39_ = i;
963 i = _tmp39_ + 1;
964 }
965 _tmp37_ = FALSE;
966 _tmp40_ = i;
967 _tmp41_ = a;
968 _tmp42_ = _tmp41_->index;
969 _tmp43_ = a;
970 _tmp44_ = _tmp43_->length;
971 if (!(_tmp40_ < (_tmp42_ + _tmp44_))) {
972 break;
973 }
974 _tmp45_ = a;
975 _tmp46_ = _tmp45_->list;
976 _tmp47_ = i;
977 _tmp48_ = _tmp46_[_tmp47_];
978 _tmp49_ = a;
979 _tmp50_ = _tmp49_->list;
980 _tmp51_ = i;
981 _tmp52_ = _tmp50_[_tmp51_ - 1];
982 _tmp53_ = gee_tim_sort_lower_than (self, _tmp48_, _tmp52_);
983 if (_tmp53_) {
984 break;
985 } else {
986 gint _tmp54_;
987 _tmp54_ = run_length;
988 run_length = _tmp54_ + 1;
989 }
990 }
991 }
992 }
993 }
994 }
995 _tmp55_ = a;
996 _tmp56_ = _tmp55_->list;
997 _tmp57_ = a;
998 _tmp58_ = _tmp57_->index;
999 _tmp59_ = run_length;
1000 _tmp60_ = gee_tim_sort_slice_new (_tmp56_, _tmp58_, _tmp59_);
1001 result = _tmp60_;
1002 if (descending) {
1003 *descending = _vala_descending;
1004 }
1005 return result;
1006 }
1007
1008
gee_tim_sort_insertion_sort(GeeTimSort * self,GeeTimSortSlice * a,gint offset)1009 static void gee_tim_sort_insertion_sort (GeeTimSort* self, GeeTimSortSlice* a, gint offset) {
1010 g_return_if_fail (self != NULL);
1011 g_return_if_fail (a != NULL);
1012 {
1013 GeeTimSortSlice* _tmp0_;
1014 gint _tmp1_;
1015 gint _tmp2_;
1016 gint start;
1017 _tmp0_ = a;
1018 _tmp1_ = _tmp0_->index;
1019 _tmp2_ = offset;
1020 start = _tmp1_ + _tmp2_;
1021 {
1022 gboolean _tmp3_;
1023 _tmp3_ = TRUE;
1024 while (TRUE) {
1025 gboolean _tmp4_;
1026 gint _tmp6_;
1027 GeeTimSortSlice* _tmp7_;
1028 gint _tmp8_;
1029 GeeTimSortSlice* _tmp9_;
1030 gint _tmp10_;
1031 GeeTimSortSlice* _tmp11_;
1032 gint _tmp12_;
1033 gint left;
1034 gint _tmp13_;
1035 gint right;
1036 GeeTimSortSlice* _tmp14_;
1037 void** _tmp15_;
1038 gint _tmp16_;
1039 void* _tmp17_;
1040 void* pivot;
1041 gint _tmp31_;
1042 gint _tmp32_;
1043 GeeTimSortSlice* _tmp33_;
1044 void** _tmp34_;
1045 gint _tmp35_;
1046 GeeTimSortSlice* _tmp36_;
1047 void** _tmp37_;
1048 gint _tmp38_;
1049 gint _tmp39_;
1050 gint _tmp40_;
1051 GeeTimSortSlice* _tmp41_;
1052 void** _tmp42_;
1053 gint _tmp43_;
1054 void* _tmp44_;
1055 void* _tmp45_;
1056 _tmp4_ = _tmp3_;
1057 if (!_tmp4_) {
1058 gint _tmp5_;
1059 _tmp5_ = start;
1060 start = _tmp5_ + 1;
1061 }
1062 _tmp3_ = FALSE;
1063 _tmp6_ = start;
1064 _tmp7_ = a;
1065 _tmp8_ = _tmp7_->index;
1066 _tmp9_ = a;
1067 _tmp10_ = _tmp9_->length;
1068 if (!(_tmp6_ < (_tmp8_ + _tmp10_))) {
1069 break;
1070 }
1071 _tmp11_ = a;
1072 _tmp12_ = _tmp11_->index;
1073 left = _tmp12_;
1074 _tmp13_ = start;
1075 right = _tmp13_;
1076 _tmp14_ = a;
1077 _tmp15_ = _tmp14_->list;
1078 _tmp16_ = right;
1079 _tmp17_ = _tmp15_[_tmp16_];
1080 pivot = _tmp17_;
1081 while (TRUE) {
1082 gint _tmp18_;
1083 gint _tmp19_;
1084 gint _tmp20_;
1085 gint _tmp21_;
1086 gint _tmp22_;
1087 gint p;
1088 void* _tmp23_;
1089 GeeTimSortSlice* _tmp24_;
1090 void** _tmp25_;
1091 gint _tmp26_;
1092 void* _tmp27_;
1093 gboolean _tmp28_ = FALSE;
1094 _tmp18_ = left;
1095 _tmp19_ = right;
1096 if (!(_tmp18_ < _tmp19_)) {
1097 break;
1098 }
1099 _tmp20_ = left;
1100 _tmp21_ = right;
1101 _tmp22_ = left;
1102 p = _tmp20_ + ((_tmp21_ - _tmp22_) >> 1);
1103 _tmp23_ = pivot;
1104 _tmp24_ = a;
1105 _tmp25_ = _tmp24_->list;
1106 _tmp26_ = p;
1107 _tmp27_ = _tmp25_[_tmp26_];
1108 _tmp28_ = gee_tim_sort_lower_than (self, _tmp23_, _tmp27_);
1109 if (_tmp28_) {
1110 gint _tmp29_;
1111 _tmp29_ = p;
1112 right = _tmp29_;
1113 } else {
1114 gint _tmp30_;
1115 _tmp30_ = p;
1116 left = _tmp30_ + 1;
1117 }
1118 }
1119 _tmp31_ = left;
1120 _tmp32_ = right;
1121 _vala_assert (_tmp31_ == _tmp32_, "left == right");
1122 _tmp33_ = a;
1123 _tmp34_ = _tmp33_->list;
1124 _tmp35_ = left;
1125 _tmp36_ = a;
1126 _tmp37_ = _tmp36_->list;
1127 _tmp38_ = left;
1128 _tmp39_ = start;
1129 _tmp40_ = left;
1130 g_memmove (&_tmp34_[_tmp35_ + 1], &_tmp37_[_tmp38_], (gsize) (sizeof (gpointer) * (_tmp39_ - _tmp40_)));
1131 _tmp41_ = a;
1132 _tmp42_ = _tmp41_->list;
1133 _tmp43_ = left;
1134 _tmp44_ = pivot;
1135 _tmp42_[_tmp43_] = _tmp44_;
1136 _tmp45_ = _tmp42_[_tmp43_];
1137 }
1138 }
1139 }
1140 }
1141
1142
gee_tim_sort_merge_collapse(GeeTimSort * self)1143 static void gee_tim_sort_merge_collapse (GeeTimSort* self) {
1144 GeeTimSortSlice** _tmp0_;
1145 gint _tmp0__length1;
1146 gint count;
1147 g_return_if_fail (self != NULL);
1148 _tmp0_ = self->priv->pending;
1149 _tmp0__length1 = self->priv->pending_length1;
1150 count = _tmp0__length1;
1151 while (TRUE) {
1152 gint _tmp1_;
1153 gboolean _tmp2_ = FALSE;
1154 gint _tmp3_;
1155 gboolean _tmp16_;
1156 GeeTimSortSlice** _tmp36_;
1157 gint _tmp36__length1;
1158 _tmp1_ = count;
1159 if (!(_tmp1_ > 1)) {
1160 break;
1161 }
1162 _tmp3_ = count;
1163 if (_tmp3_ >= 3) {
1164 GeeTimSortSlice** _tmp4_;
1165 gint _tmp4__length1;
1166 gint _tmp5_;
1167 GeeTimSortSlice* _tmp6_;
1168 gint _tmp7_;
1169 GeeTimSortSlice** _tmp8_;
1170 gint _tmp8__length1;
1171 gint _tmp9_;
1172 GeeTimSortSlice* _tmp10_;
1173 gint _tmp11_;
1174 GeeTimSortSlice** _tmp12_;
1175 gint _tmp12__length1;
1176 gint _tmp13_;
1177 GeeTimSortSlice* _tmp14_;
1178 gint _tmp15_;
1179 _tmp4_ = self->priv->pending;
1180 _tmp4__length1 = self->priv->pending_length1;
1181 _tmp5_ = count;
1182 _tmp6_ = _tmp4_[_tmp5_ - 3];
1183 _tmp7_ = _tmp6_->length;
1184 _tmp8_ = self->priv->pending;
1185 _tmp8__length1 = self->priv->pending_length1;
1186 _tmp9_ = count;
1187 _tmp10_ = _tmp8_[_tmp9_ - 2];
1188 _tmp11_ = _tmp10_->length;
1189 _tmp12_ = self->priv->pending;
1190 _tmp12__length1 = self->priv->pending_length1;
1191 _tmp13_ = count;
1192 _tmp14_ = _tmp12_[_tmp13_ - 1];
1193 _tmp15_ = _tmp14_->length;
1194 _tmp2_ = _tmp7_ <= (_tmp11_ + _tmp15_);
1195 } else {
1196 _tmp2_ = FALSE;
1197 }
1198 _tmp16_ = _tmp2_;
1199 if (_tmp16_) {
1200 GeeTimSortSlice** _tmp17_;
1201 gint _tmp17__length1;
1202 gint _tmp18_;
1203 GeeTimSortSlice* _tmp19_;
1204 gint _tmp20_;
1205 GeeTimSortSlice** _tmp21_;
1206 gint _tmp21__length1;
1207 gint _tmp22_;
1208 GeeTimSortSlice* _tmp23_;
1209 gint _tmp24_;
1210 _tmp17_ = self->priv->pending;
1211 _tmp17__length1 = self->priv->pending_length1;
1212 _tmp18_ = count;
1213 _tmp19_ = _tmp17_[_tmp18_ - 3];
1214 _tmp20_ = _tmp19_->length;
1215 _tmp21_ = self->priv->pending;
1216 _tmp21__length1 = self->priv->pending_length1;
1217 _tmp22_ = count;
1218 _tmp23_ = _tmp21_[_tmp22_ - 1];
1219 _tmp24_ = _tmp23_->length;
1220 if (_tmp20_ < _tmp24_) {
1221 gint _tmp25_;
1222 _tmp25_ = count;
1223 gee_tim_sort_merge_at (self, _tmp25_ - 3);
1224 } else {
1225 gint _tmp26_;
1226 _tmp26_ = count;
1227 gee_tim_sort_merge_at (self, _tmp26_ - 2);
1228 }
1229 } else {
1230 GeeTimSortSlice** _tmp27_;
1231 gint _tmp27__length1;
1232 gint _tmp28_;
1233 GeeTimSortSlice* _tmp29_;
1234 gint _tmp30_;
1235 GeeTimSortSlice** _tmp31_;
1236 gint _tmp31__length1;
1237 gint _tmp32_;
1238 GeeTimSortSlice* _tmp33_;
1239 gint _tmp34_;
1240 _tmp27_ = self->priv->pending;
1241 _tmp27__length1 = self->priv->pending_length1;
1242 _tmp28_ = count;
1243 _tmp29_ = _tmp27_[_tmp28_ - 2];
1244 _tmp30_ = _tmp29_->length;
1245 _tmp31_ = self->priv->pending;
1246 _tmp31__length1 = self->priv->pending_length1;
1247 _tmp32_ = count;
1248 _tmp33_ = _tmp31_[_tmp32_ - 1];
1249 _tmp34_ = _tmp33_->length;
1250 if (_tmp30_ <= _tmp34_) {
1251 gint _tmp35_;
1252 _tmp35_ = count;
1253 gee_tim_sort_merge_at (self, _tmp35_ - 2);
1254 } else {
1255 break;
1256 }
1257 }
1258 _tmp36_ = self->priv->pending;
1259 _tmp36__length1 = self->priv->pending_length1;
1260 count = _tmp36__length1;
1261 }
1262 }
1263
1264
gee_tim_sort_merge_force_collapse(GeeTimSort * self)1265 static void gee_tim_sort_merge_force_collapse (GeeTimSort* self) {
1266 GeeTimSortSlice** _tmp0_;
1267 gint _tmp0__length1;
1268 gint count;
1269 g_return_if_fail (self != NULL);
1270 _tmp0_ = self->priv->pending;
1271 _tmp0__length1 = self->priv->pending_length1;
1272 count = _tmp0__length1;
1273 while (TRUE) {
1274 gint _tmp1_;
1275 gboolean _tmp2_ = FALSE;
1276 gint _tmp3_;
1277 gboolean _tmp12_;
1278 GeeTimSortSlice** _tmp15_;
1279 gint _tmp15__length1;
1280 _tmp1_ = count;
1281 if (!(_tmp1_ > 1)) {
1282 break;
1283 }
1284 _tmp3_ = count;
1285 if (_tmp3_ >= 3) {
1286 GeeTimSortSlice** _tmp4_;
1287 gint _tmp4__length1;
1288 gint _tmp5_;
1289 GeeTimSortSlice* _tmp6_;
1290 gint _tmp7_;
1291 GeeTimSortSlice** _tmp8_;
1292 gint _tmp8__length1;
1293 gint _tmp9_;
1294 GeeTimSortSlice* _tmp10_;
1295 gint _tmp11_;
1296 _tmp4_ = self->priv->pending;
1297 _tmp4__length1 = self->priv->pending_length1;
1298 _tmp5_ = count;
1299 _tmp6_ = _tmp4_[_tmp5_ - 3];
1300 _tmp7_ = _tmp6_->length;
1301 _tmp8_ = self->priv->pending;
1302 _tmp8__length1 = self->priv->pending_length1;
1303 _tmp9_ = count;
1304 _tmp10_ = _tmp8_[_tmp9_ - 1];
1305 _tmp11_ = _tmp10_->length;
1306 _tmp2_ = _tmp7_ < _tmp11_;
1307 } else {
1308 _tmp2_ = FALSE;
1309 }
1310 _tmp12_ = _tmp2_;
1311 if (_tmp12_) {
1312 gint _tmp13_;
1313 _tmp13_ = count;
1314 gee_tim_sort_merge_at (self, _tmp13_ - 3);
1315 } else {
1316 gint _tmp14_;
1317 _tmp14_ = count;
1318 gee_tim_sort_merge_at (self, _tmp14_ - 2);
1319 }
1320 _tmp15_ = self->priv->pending;
1321 _tmp15__length1 = self->priv->pending_length1;
1322 count = _tmp15__length1;
1323 }
1324 }
1325
1326
gee_tim_sort_merge_at(GeeTimSort * self,gint index)1327 static void gee_tim_sort_merge_at (GeeTimSort* self, gint index) {
1328 GeeTimSortSlice** _tmp0_;
1329 gint _tmp0__length1;
1330 gint _tmp1_;
1331 GeeTimSortSlice* _tmp2_;
1332 GeeTimSortSlice* a;
1333 GeeTimSortSlice** _tmp3_;
1334 gint _tmp3__length1;
1335 gint _tmp4_;
1336 GeeTimSortSlice* _tmp5_;
1337 GeeTimSortSlice* b;
1338 GeeTimSortSlice* _tmp6_;
1339 gint _tmp7_;
1340 GeeTimSortSlice* _tmp8_;
1341 gint _tmp9_;
1342 GeeTimSortSlice* _tmp10_;
1343 gint _tmp11_;
1344 GeeTimSortSlice* _tmp12_;
1345 gint _tmp13_;
1346 GeeTimSortSlice* _tmp14_;
1347 gint _tmp15_;
1348 GeeTimSortSlice** _tmp16_;
1349 gint _tmp16__length1;
1350 gint _tmp17_;
1351 void** _tmp18_;
1352 GeeTimSortSlice* _tmp19_;
1353 gint _tmp20_;
1354 GeeTimSortSlice* _tmp21_;
1355 gint _tmp22_;
1356 GeeTimSortSlice* _tmp23_;
1357 gint _tmp24_;
1358 GeeTimSortSlice* _tmp25_;
1359 GeeTimSortSlice* _tmp26_;
1360 gint _tmp27_;
1361 gint _tmp28_;
1362 GeeTimSortSlice** _tmp29_;
1363 gint _tmp29__length1;
1364 gint _tmp30_;
1365 gint _tmp31_;
1366 GeeTimSortSlice* _tmp32_;
1367 void* _tmp33_ = NULL;
1368 GeeTimSortSlice* _tmp34_;
1369 gint _tmp35_ = 0;
1370 gint sorted_count;
1371 GeeTimSortSlice* _tmp36_;
1372 gint _tmp37_;
1373 GeeTimSortSlice* _tmp38_;
1374 gint _tmp39_;
1375 GeeTimSortSlice* _tmp40_;
1376 GeeTimSortSlice* _tmp41_;
1377 void* _tmp42_ = NULL;
1378 GeeTimSortSlice* _tmp43_;
1379 GeeTimSortSlice* _tmp44_;
1380 gint _tmp45_;
1381 gint _tmp46_ = 0;
1382 GeeTimSortSlice* _tmp47_;
1383 gint _tmp48_;
1384 GeeTimSortSlice* _tmp49_;
1385 gint _tmp50_;
1386 GeeTimSortSlice* _tmp51_;
1387 gint _tmp52_;
1388 g_return_if_fail (self != NULL);
1389 _tmp0_ = self->priv->pending;
1390 _tmp0__length1 = self->priv->pending_length1;
1391 _tmp1_ = index;
1392 _tmp2_ = _tmp0_[_tmp1_];
1393 _tmp0_[_tmp1_] = NULL;
1394 a = _tmp2_;
1395 _tmp3_ = self->priv->pending;
1396 _tmp3__length1 = self->priv->pending_length1;
1397 _tmp4_ = index;
1398 _tmp5_ = _tmp3_[_tmp4_ + 1];
1399 _tmp3_[_tmp4_ + 1] = NULL;
1400 b = _tmp5_;
1401 _tmp6_ = a;
1402 _tmp7_ = _tmp6_->length;
1403 _vala_assert (_tmp7_ > 0, "a.length > 0");
1404 _tmp8_ = b;
1405 _tmp9_ = _tmp8_->length;
1406 _vala_assert (_tmp9_ > 0, "b.length > 0");
1407 _tmp10_ = a;
1408 _tmp11_ = _tmp10_->index;
1409 _tmp12_ = a;
1410 _tmp13_ = _tmp12_->length;
1411 _tmp14_ = b;
1412 _tmp15_ = _tmp14_->index;
1413 _vala_assert ((_tmp11_ + _tmp13_) == _tmp15_, "a.index + a.length == b.index");
1414 _tmp16_ = self->priv->pending;
1415 _tmp16__length1 = self->priv->pending_length1;
1416 _tmp17_ = index;
1417 _tmp18_ = self->priv->list;
1418 _tmp19_ = a;
1419 _tmp20_ = _tmp19_->index;
1420 _tmp21_ = a;
1421 _tmp22_ = _tmp21_->length;
1422 _tmp23_ = b;
1423 _tmp24_ = _tmp23_->length;
1424 _tmp25_ = gee_tim_sort_slice_new (_tmp18_, _tmp20_, _tmp22_ + _tmp24_);
1425 _gee_tim_sort_slice_free0 (_tmp16_[_tmp17_]);
1426 _tmp16_[_tmp17_] = _tmp25_;
1427 _tmp26_ = _tmp16_[_tmp17_];
1428 _tmp27_ = index;
1429 _tmp28_ = index;
1430 _tmp29_ = self->priv->pending;
1431 _tmp29__length1 = self->priv->pending_length1;
1432 _tmp30_ = index;
1433 _vala_array_move (self->priv->pending, sizeof (GeeTimSortSlice*), _tmp27_ + 2, _tmp28_ + 1, (_tmp29__length1 - _tmp30_) - 2);
1434 self->priv->pending_length1 = self->priv->pending_length1 - 1;
1435 _tmp31_ = self->priv->pending_length1;
1436 _tmp32_ = b;
1437 _tmp33_ = gee_tim_sort_slice_peek_first (_tmp32_);
1438 _tmp34_ = a;
1439 _tmp35_ = gee_tim_sort_gallop_rightmost (self, _tmp33_, _tmp34_, 0);
1440 sorted_count = _tmp35_;
1441 _tmp36_ = a;
1442 _tmp37_ = sorted_count;
1443 gee_tim_sort_slice_shorten_start (_tmp36_, _tmp37_);
1444 _tmp38_ = a;
1445 _tmp39_ = _tmp38_->length;
1446 if (_tmp39_ == 0) {
1447 _gee_tim_sort_slice_free0 (b);
1448 _gee_tim_sort_slice_free0 (a);
1449 return;
1450 }
1451 _tmp40_ = b;
1452 _tmp41_ = a;
1453 _tmp42_ = gee_tim_sort_slice_peek_last (_tmp41_);
1454 _tmp43_ = b;
1455 _tmp44_ = b;
1456 _tmp45_ = _tmp44_->length;
1457 _tmp46_ = gee_tim_sort_gallop_leftmost (self, _tmp42_, _tmp43_, _tmp45_ - 1);
1458 _tmp40_->length = _tmp46_;
1459 _tmp47_ = b;
1460 _tmp48_ = _tmp47_->length;
1461 if (_tmp48_ == 0) {
1462 _gee_tim_sort_slice_free0 (b);
1463 _gee_tim_sort_slice_free0 (a);
1464 return;
1465 }
1466 _tmp49_ = a;
1467 _tmp50_ = _tmp49_->length;
1468 _tmp51_ = b;
1469 _tmp52_ = _tmp51_->length;
1470 if (_tmp50_ <= _tmp52_) {
1471 GeeTimSortSlice* _tmp53_;
1472 GeeTimSortSlice* _tmp54_;
1473 _tmp53_ = a;
1474 a = NULL;
1475 _tmp54_ = b;
1476 b = NULL;
1477 gee_tim_sort_merge_low (self, _tmp53_, _tmp54_);
1478 } else {
1479 GeeTimSortSlice* _tmp55_;
1480 GeeTimSortSlice* _tmp56_;
1481 _tmp55_ = a;
1482 a = NULL;
1483 _tmp56_ = b;
1484 b = NULL;
1485 gee_tim_sort_merge_high (self, _tmp55_, _tmp56_);
1486 }
1487 _gee_tim_sort_slice_free0 (b);
1488 _gee_tim_sort_slice_free0 (a);
1489 }
1490
1491
gee_tim_sort_gallop_leftmost(GeeTimSort * self,gconstpointer key,GeeTimSortSlice * a,gint hint)1492 static gint gee_tim_sort_gallop_leftmost (GeeTimSort* self, gconstpointer key, GeeTimSortSlice* a, gint hint) {
1493 gint result = 0;
1494 gint _tmp0_;
1495 gint _tmp1_;
1496 GeeTimSortSlice* _tmp2_;
1497 gint _tmp3_;
1498 GeeTimSortSlice* _tmp4_;
1499 gint _tmp5_;
1500 gint _tmp6_;
1501 gint p;
1502 gint last_offset;
1503 gint offset;
1504 GeeTimSortSlice* _tmp7_;
1505 void** _tmp8_;
1506 gint _tmp9_;
1507 void* _tmp10_;
1508 gconstpointer _tmp11_;
1509 gboolean _tmp12_ = FALSE;
1510 gint _tmp57_;
1511 gint _tmp58_;
1512 gint _tmp59_;
1513 gint _tmp60_;
1514 GeeTimSortSlice* _tmp61_;
1515 gint _tmp62_;
1516 gint _tmp63_;
1517 gint _tmp79_;
1518 gint _tmp80_;
1519 g_return_val_if_fail (self != NULL, 0);
1520 g_return_val_if_fail (a != NULL, 0);
1521 _tmp0_ = hint;
1522 _vala_assert (0 <= _tmp0_, "0 <= hint");
1523 _tmp1_ = hint;
1524 _tmp2_ = a;
1525 _tmp3_ = _tmp2_->length;
1526 _vala_assert (_tmp1_ < _tmp3_, "hint < a.length");
1527 _tmp4_ = a;
1528 _tmp5_ = _tmp4_->index;
1529 _tmp6_ = hint;
1530 p = _tmp5_ + _tmp6_;
1531 last_offset = 0;
1532 offset = 1;
1533 _tmp7_ = a;
1534 _tmp8_ = _tmp7_->list;
1535 _tmp9_ = p;
1536 _tmp10_ = _tmp8_[_tmp9_];
1537 _tmp11_ = key;
1538 _tmp12_ = gee_tim_sort_lower_than (self, _tmp10_, _tmp11_);
1539 if (_tmp12_) {
1540 GeeTimSortSlice* _tmp13_;
1541 gint _tmp14_;
1542 gint _tmp15_;
1543 gint max_offset;
1544 gint _tmp28_;
1545 gint _tmp29_;
1546 gint _tmp31_;
1547 gint _tmp32_;
1548 gint _tmp33_;
1549 gint _tmp34_;
1550 _tmp13_ = a;
1551 _tmp14_ = _tmp13_->length;
1552 _tmp15_ = hint;
1553 max_offset = _tmp14_ - _tmp15_;
1554 while (TRUE) {
1555 gint _tmp16_;
1556 gint _tmp17_;
1557 GeeTimSortSlice* _tmp18_;
1558 void** _tmp19_;
1559 gint _tmp20_;
1560 gint _tmp21_;
1561 void* _tmp22_;
1562 gconstpointer _tmp23_;
1563 gboolean _tmp24_ = FALSE;
1564 _tmp16_ = offset;
1565 _tmp17_ = max_offset;
1566 if (!(_tmp16_ < _tmp17_)) {
1567 break;
1568 }
1569 _tmp18_ = a;
1570 _tmp19_ = _tmp18_->list;
1571 _tmp20_ = p;
1572 _tmp21_ = offset;
1573 _tmp22_ = _tmp19_[_tmp20_ + _tmp21_];
1574 _tmp23_ = key;
1575 _tmp24_ = gee_tim_sort_lower_than (self, _tmp22_, _tmp23_);
1576 if (_tmp24_) {
1577 gint _tmp25_;
1578 gint _tmp26_;
1579 gint _tmp27_;
1580 _tmp25_ = offset;
1581 last_offset = _tmp25_;
1582 _tmp26_ = offset;
1583 offset = _tmp26_ << 1;
1584 _tmp27_ = offset;
1585 offset = _tmp27_ + 1;
1586 } else {
1587 break;
1588 }
1589 }
1590 _tmp28_ = offset;
1591 _tmp29_ = max_offset;
1592 if (_tmp28_ > _tmp29_) {
1593 gint _tmp30_;
1594 _tmp30_ = max_offset;
1595 offset = _tmp30_;
1596 }
1597 _tmp31_ = hint;
1598 _tmp32_ = last_offset;
1599 last_offset = _tmp31_ + _tmp32_;
1600 _tmp33_ = hint;
1601 _tmp34_ = offset;
1602 offset = _tmp33_ + _tmp34_;
1603 } else {
1604 gint _tmp35_;
1605 gint max_offset;
1606 gint _tmp48_;
1607 gint _tmp49_;
1608 gint _tmp51_;
1609 gint temp_last_offset;
1610 gint _tmp52_;
1611 gint temp_offset;
1612 gint _tmp53_;
1613 gint _tmp54_;
1614 gint _tmp55_;
1615 gint _tmp56_;
1616 _tmp35_ = hint;
1617 max_offset = _tmp35_ + 1;
1618 while (TRUE) {
1619 gint _tmp36_;
1620 gint _tmp37_;
1621 GeeTimSortSlice* _tmp38_;
1622 void** _tmp39_;
1623 gint _tmp40_;
1624 gint _tmp41_;
1625 void* _tmp42_;
1626 gconstpointer _tmp43_;
1627 gboolean _tmp44_ = FALSE;
1628 _tmp36_ = offset;
1629 _tmp37_ = max_offset;
1630 if (!(_tmp36_ < _tmp37_)) {
1631 break;
1632 }
1633 _tmp38_ = a;
1634 _tmp39_ = _tmp38_->list;
1635 _tmp40_ = p;
1636 _tmp41_ = offset;
1637 _tmp42_ = _tmp39_[_tmp40_ - _tmp41_];
1638 _tmp43_ = key;
1639 _tmp44_ = gee_tim_sort_lower_than (self, _tmp42_, _tmp43_);
1640 if (_tmp44_) {
1641 break;
1642 } else {
1643 gint _tmp45_;
1644 gint _tmp46_;
1645 gint _tmp47_;
1646 _tmp45_ = offset;
1647 last_offset = _tmp45_;
1648 _tmp46_ = offset;
1649 offset = _tmp46_ << 1;
1650 _tmp47_ = offset;
1651 offset = _tmp47_ + 1;
1652 }
1653 }
1654 _tmp48_ = offset;
1655 _tmp49_ = max_offset;
1656 if (_tmp48_ > _tmp49_) {
1657 gint _tmp50_;
1658 _tmp50_ = max_offset;
1659 offset = _tmp50_;
1660 }
1661 _tmp51_ = last_offset;
1662 temp_last_offset = _tmp51_;
1663 _tmp52_ = offset;
1664 temp_offset = _tmp52_;
1665 _tmp53_ = hint;
1666 _tmp54_ = temp_offset;
1667 last_offset = _tmp53_ - _tmp54_;
1668 _tmp55_ = hint;
1669 _tmp56_ = temp_last_offset;
1670 offset = _tmp55_ - _tmp56_;
1671 }
1672 _tmp57_ = last_offset;
1673 _vala_assert ((-1) <= _tmp57_, "-1 <= last_offset");
1674 _tmp58_ = last_offset;
1675 _tmp59_ = offset;
1676 _vala_assert (_tmp58_ < _tmp59_, "last_offset < offset");
1677 _tmp60_ = offset;
1678 _tmp61_ = a;
1679 _tmp62_ = _tmp61_->length;
1680 _vala_assert (_tmp60_ <= _tmp62_, "offset <= a.length");
1681 _tmp63_ = last_offset;
1682 last_offset = _tmp63_ + 1;
1683 while (TRUE) {
1684 gint _tmp64_;
1685 gint _tmp65_;
1686 gint _tmp66_;
1687 gint _tmp67_;
1688 gint _tmp68_;
1689 gint m;
1690 GeeTimSortSlice* _tmp69_;
1691 void** _tmp70_;
1692 GeeTimSortSlice* _tmp71_;
1693 gint _tmp72_;
1694 gint _tmp73_;
1695 void* _tmp74_;
1696 gconstpointer _tmp75_;
1697 gboolean _tmp76_ = FALSE;
1698 _tmp64_ = last_offset;
1699 _tmp65_ = offset;
1700 if (!(_tmp64_ < _tmp65_)) {
1701 break;
1702 }
1703 _tmp66_ = last_offset;
1704 _tmp67_ = offset;
1705 _tmp68_ = last_offset;
1706 m = _tmp66_ + ((_tmp67_ - _tmp68_) >> 1);
1707 _tmp69_ = a;
1708 _tmp70_ = _tmp69_->list;
1709 _tmp71_ = a;
1710 _tmp72_ = _tmp71_->index;
1711 _tmp73_ = m;
1712 _tmp74_ = _tmp70_[_tmp72_ + _tmp73_];
1713 _tmp75_ = key;
1714 _tmp76_ = gee_tim_sort_lower_than (self, _tmp74_, _tmp75_);
1715 if (_tmp76_) {
1716 gint _tmp77_;
1717 _tmp77_ = m;
1718 last_offset = _tmp77_ + 1;
1719 } else {
1720 gint _tmp78_;
1721 _tmp78_ = m;
1722 offset = _tmp78_;
1723 }
1724 }
1725 _tmp79_ = last_offset;
1726 _tmp80_ = offset;
1727 _vala_assert (_tmp79_ == _tmp80_, "last_offset == offset");
1728 result = offset;
1729 return result;
1730 }
1731
1732
gee_tim_sort_gallop_rightmost(GeeTimSort * self,gconstpointer key,GeeTimSortSlice * a,gint hint)1733 static gint gee_tim_sort_gallop_rightmost (GeeTimSort* self, gconstpointer key, GeeTimSortSlice* a, gint hint) {
1734 gint result = 0;
1735 gint _tmp0_;
1736 gint _tmp1_;
1737 GeeTimSortSlice* _tmp2_;
1738 gint _tmp3_;
1739 GeeTimSortSlice* _tmp4_;
1740 gint _tmp5_;
1741 gint _tmp6_;
1742 gint p;
1743 gint last_offset;
1744 gint offset;
1745 GeeTimSortSlice* _tmp7_;
1746 void** _tmp8_;
1747 gint _tmp9_;
1748 void* _tmp10_;
1749 gconstpointer _tmp11_;
1750 gboolean _tmp12_ = FALSE;
1751 gint _tmp57_;
1752 gint _tmp58_;
1753 gint _tmp59_;
1754 gint _tmp60_;
1755 GeeTimSortSlice* _tmp61_;
1756 gint _tmp62_;
1757 gint _tmp63_;
1758 gint _tmp79_;
1759 gint _tmp80_;
1760 g_return_val_if_fail (self != NULL, 0);
1761 g_return_val_if_fail (a != NULL, 0);
1762 _tmp0_ = hint;
1763 _vala_assert (0 <= _tmp0_, "0 <= hint");
1764 _tmp1_ = hint;
1765 _tmp2_ = a;
1766 _tmp3_ = _tmp2_->length;
1767 _vala_assert (_tmp1_ < _tmp3_, "hint < a.length");
1768 _tmp4_ = a;
1769 _tmp5_ = _tmp4_->index;
1770 _tmp6_ = hint;
1771 p = _tmp5_ + _tmp6_;
1772 last_offset = 0;
1773 offset = 1;
1774 _tmp7_ = a;
1775 _tmp8_ = _tmp7_->list;
1776 _tmp9_ = p;
1777 _tmp10_ = _tmp8_[_tmp9_];
1778 _tmp11_ = key;
1779 _tmp12_ = gee_tim_sort_lower_than_or_equal_to (self, _tmp10_, _tmp11_);
1780 if (_tmp12_) {
1781 GeeTimSortSlice* _tmp13_;
1782 gint _tmp14_;
1783 gint _tmp15_;
1784 gint max_offset;
1785 gint _tmp28_;
1786 gint _tmp29_;
1787 gint _tmp31_;
1788 gint _tmp32_;
1789 gint _tmp33_;
1790 gint _tmp34_;
1791 _tmp13_ = a;
1792 _tmp14_ = _tmp13_->length;
1793 _tmp15_ = hint;
1794 max_offset = _tmp14_ - _tmp15_;
1795 while (TRUE) {
1796 gint _tmp16_;
1797 gint _tmp17_;
1798 GeeTimSortSlice* _tmp18_;
1799 void** _tmp19_;
1800 gint _tmp20_;
1801 gint _tmp21_;
1802 void* _tmp22_;
1803 gconstpointer _tmp23_;
1804 gboolean _tmp24_ = FALSE;
1805 _tmp16_ = offset;
1806 _tmp17_ = max_offset;
1807 if (!(_tmp16_ < _tmp17_)) {
1808 break;
1809 }
1810 _tmp18_ = a;
1811 _tmp19_ = _tmp18_->list;
1812 _tmp20_ = p;
1813 _tmp21_ = offset;
1814 _tmp22_ = _tmp19_[_tmp20_ + _tmp21_];
1815 _tmp23_ = key;
1816 _tmp24_ = gee_tim_sort_lower_than_or_equal_to (self, _tmp22_, _tmp23_);
1817 if (_tmp24_) {
1818 gint _tmp25_;
1819 gint _tmp26_;
1820 gint _tmp27_;
1821 _tmp25_ = offset;
1822 last_offset = _tmp25_;
1823 _tmp26_ = offset;
1824 offset = _tmp26_ << 1;
1825 _tmp27_ = offset;
1826 offset = _tmp27_ + 1;
1827 } else {
1828 break;
1829 }
1830 }
1831 _tmp28_ = offset;
1832 _tmp29_ = max_offset;
1833 if (_tmp28_ > _tmp29_) {
1834 gint _tmp30_;
1835 _tmp30_ = max_offset;
1836 offset = _tmp30_;
1837 }
1838 _tmp31_ = hint;
1839 _tmp32_ = last_offset;
1840 last_offset = _tmp31_ + _tmp32_;
1841 _tmp33_ = hint;
1842 _tmp34_ = offset;
1843 offset = _tmp33_ + _tmp34_;
1844 } else {
1845 gint _tmp35_;
1846 gint max_offset;
1847 gint _tmp48_;
1848 gint _tmp49_;
1849 gint _tmp51_;
1850 gint temp_last_offset;
1851 gint _tmp52_;
1852 gint temp_offset;
1853 gint _tmp53_;
1854 gint _tmp54_;
1855 gint _tmp55_;
1856 gint _tmp56_;
1857 _tmp35_ = hint;
1858 max_offset = _tmp35_ + 1;
1859 while (TRUE) {
1860 gint _tmp36_;
1861 gint _tmp37_;
1862 GeeTimSortSlice* _tmp38_;
1863 void** _tmp39_;
1864 gint _tmp40_;
1865 gint _tmp41_;
1866 void* _tmp42_;
1867 gconstpointer _tmp43_;
1868 gboolean _tmp44_ = FALSE;
1869 _tmp36_ = offset;
1870 _tmp37_ = max_offset;
1871 if (!(_tmp36_ < _tmp37_)) {
1872 break;
1873 }
1874 _tmp38_ = a;
1875 _tmp39_ = _tmp38_->list;
1876 _tmp40_ = p;
1877 _tmp41_ = offset;
1878 _tmp42_ = _tmp39_[_tmp40_ - _tmp41_];
1879 _tmp43_ = key;
1880 _tmp44_ = gee_tim_sort_lower_than_or_equal_to (self, _tmp42_, _tmp43_);
1881 if (_tmp44_) {
1882 break;
1883 } else {
1884 gint _tmp45_;
1885 gint _tmp46_;
1886 gint _tmp47_;
1887 _tmp45_ = offset;
1888 last_offset = _tmp45_;
1889 _tmp46_ = offset;
1890 offset = _tmp46_ << 1;
1891 _tmp47_ = offset;
1892 offset = _tmp47_ + 1;
1893 }
1894 }
1895 _tmp48_ = offset;
1896 _tmp49_ = max_offset;
1897 if (_tmp48_ > _tmp49_) {
1898 gint _tmp50_;
1899 _tmp50_ = max_offset;
1900 offset = _tmp50_;
1901 }
1902 _tmp51_ = last_offset;
1903 temp_last_offset = _tmp51_;
1904 _tmp52_ = offset;
1905 temp_offset = _tmp52_;
1906 _tmp53_ = hint;
1907 _tmp54_ = temp_offset;
1908 last_offset = _tmp53_ - _tmp54_;
1909 _tmp55_ = hint;
1910 _tmp56_ = temp_last_offset;
1911 offset = _tmp55_ - _tmp56_;
1912 }
1913 _tmp57_ = last_offset;
1914 _vala_assert ((-1) <= _tmp57_, "-1 <= last_offset");
1915 _tmp58_ = last_offset;
1916 _tmp59_ = offset;
1917 _vala_assert (_tmp58_ < _tmp59_, "last_offset < offset");
1918 _tmp60_ = offset;
1919 _tmp61_ = a;
1920 _tmp62_ = _tmp61_->length;
1921 _vala_assert (_tmp60_ <= _tmp62_, "offset <= a.length");
1922 _tmp63_ = last_offset;
1923 last_offset = _tmp63_ + 1;
1924 while (TRUE) {
1925 gint _tmp64_;
1926 gint _tmp65_;
1927 gint _tmp66_;
1928 gint _tmp67_;
1929 gint _tmp68_;
1930 gint m;
1931 GeeTimSortSlice* _tmp69_;
1932 void** _tmp70_;
1933 GeeTimSortSlice* _tmp71_;
1934 gint _tmp72_;
1935 gint _tmp73_;
1936 void* _tmp74_;
1937 gconstpointer _tmp75_;
1938 gboolean _tmp76_ = FALSE;
1939 _tmp64_ = last_offset;
1940 _tmp65_ = offset;
1941 if (!(_tmp64_ < _tmp65_)) {
1942 break;
1943 }
1944 _tmp66_ = last_offset;
1945 _tmp67_ = offset;
1946 _tmp68_ = last_offset;
1947 m = _tmp66_ + ((_tmp67_ - _tmp68_) >> 1);
1948 _tmp69_ = a;
1949 _tmp70_ = _tmp69_->list;
1950 _tmp71_ = a;
1951 _tmp72_ = _tmp71_->index;
1952 _tmp73_ = m;
1953 _tmp74_ = _tmp70_[_tmp72_ + _tmp73_];
1954 _tmp75_ = key;
1955 _tmp76_ = gee_tim_sort_lower_than_or_equal_to (self, _tmp74_, _tmp75_);
1956 if (_tmp76_) {
1957 gint _tmp77_;
1958 _tmp77_ = m;
1959 last_offset = _tmp77_ + 1;
1960 } else {
1961 gint _tmp78_;
1962 _tmp78_ = m;
1963 offset = _tmp78_;
1964 }
1965 }
1966 _tmp79_ = last_offset;
1967 _tmp80_ = offset;
1968 _vala_assert (_tmp79_ == _tmp80_, "last_offset == offset");
1969 result = offset;
1970 return result;
1971 }
1972
1973
gee_tim_sort_merge_low(GeeTimSort * self,GeeTimSortSlice * a,GeeTimSortSlice * b)1974 static void gee_tim_sort_merge_low (GeeTimSort* self, GeeTimSortSlice* a, GeeTimSortSlice* b) {
1975 GeeTimSortSlice* _tmp0_;
1976 gint _tmp1_;
1977 GeeTimSortSlice* _tmp2_;
1978 gint _tmp3_;
1979 GeeTimSortSlice* _tmp4_;
1980 gint _tmp5_;
1981 GeeTimSortSlice* _tmp6_;
1982 gint _tmp7_;
1983 GeeTimSortSlice* _tmp8_;
1984 gint _tmp9_;
1985 gint _tmp10_;
1986 gint minimum_gallop;
1987 GeeTimSortSlice* _tmp11_;
1988 gint _tmp12_;
1989 gint dest;
1990 GeeTimSortSlice* _tmp13_;
1991 GError * _inner_error_ = NULL;
1992 g_return_if_fail (self != NULL);
1993 g_return_if_fail (a != NULL);
1994 g_return_if_fail (b != NULL);
1995 _tmp0_ = a;
1996 _tmp1_ = _tmp0_->length;
1997 _vala_assert (_tmp1_ > 0, "a.length > 0");
1998 _tmp2_ = b;
1999 _tmp3_ = _tmp2_->length;
2000 _vala_assert (_tmp3_ > 0, "b.length > 0");
2001 _tmp4_ = a;
2002 _tmp5_ = _tmp4_->index;
2003 _tmp6_ = a;
2004 _tmp7_ = _tmp6_->length;
2005 _tmp8_ = b;
2006 _tmp9_ = _tmp8_->index;
2007 _vala_assert ((_tmp5_ + _tmp7_) == _tmp9_, "a.index + a.length == b.index");
2008 _tmp10_ = self->priv->minimum_gallop;
2009 minimum_gallop = _tmp10_;
2010 _tmp11_ = a;
2011 _tmp12_ = _tmp11_->index;
2012 dest = _tmp12_;
2013 _tmp13_ = a;
2014 gee_tim_sort_slice_copy (_tmp13_);
2015 {
2016 void** _tmp14_;
2017 gint _tmp15_;
2018 GeeTimSortSlice* _tmp16_;
2019 void* _tmp17_ = NULL;
2020 void* _tmp18_;
2021 gboolean _tmp19_ = FALSE;
2022 GeeTimSortSlice* _tmp20_;
2023 gint _tmp21_;
2024 gboolean _tmp24_;
2025 _tmp14_ = self->priv->list;
2026 _tmp15_ = dest;
2027 dest = _tmp15_ + 1;
2028 _tmp16_ = b;
2029 _tmp17_ = gee_tim_sort_slice_pop_first (_tmp16_);
2030 _tmp14_[_tmp15_] = _tmp17_;
2031 _tmp18_ = _tmp14_[_tmp15_];
2032 _tmp20_ = a;
2033 _tmp21_ = _tmp20_->length;
2034 if (_tmp21_ == 1) {
2035 _tmp19_ = TRUE;
2036 } else {
2037 GeeTimSortSlice* _tmp22_;
2038 gint _tmp23_;
2039 _tmp22_ = b;
2040 _tmp23_ = _tmp22_->length;
2041 _tmp19_ = _tmp23_ == 0;
2042 }
2043 _tmp24_ = _tmp19_;
2044 if (_tmp24_) {
2045 {
2046 GeeTimSortSlice* _tmp25_;
2047 gint _tmp26_;
2048 GeeTimSortSlice* _tmp27_;
2049 gint _tmp28_;
2050 GeeTimSortSlice* _tmp29_;
2051 void** _tmp30_;
2052 GeeTimSortSlice* _tmp31_;
2053 gint _tmp32_;
2054 gint _tmp33_;
2055 GeeTimSortSlice* _tmp34_;
2056 gint _tmp35_;
2057 GeeTimSortSlice* _tmp36_;
2058 void** _tmp37_;
2059 GeeTimSortSlice* _tmp38_;
2060 gint _tmp39_;
2061 gint _tmp40_;
2062 GeeTimSortSlice* _tmp41_;
2063 gint _tmp42_;
2064 GeeTimSortSlice* _tmp43_;
2065 gint _tmp44_;
2066 _tmp25_ = a;
2067 _tmp26_ = _tmp25_->length;
2068 _vala_assert (_tmp26_ >= 0, "a.length >= 0");
2069 _tmp27_ = b;
2070 _tmp28_ = _tmp27_->length;
2071 _vala_assert (_tmp28_ >= 0, "b.length >= 0");
2072 _tmp29_ = b;
2073 _tmp30_ = self->priv->list;
2074 _tmp31_ = b;
2075 _tmp32_ = _tmp31_->index;
2076 _tmp33_ = dest;
2077 _tmp34_ = b;
2078 _tmp35_ = _tmp34_->length;
2079 gee_tim_sort_slice_merge_in (_tmp29_, _tmp30_, _tmp32_, _tmp33_, _tmp35_);
2080 _tmp36_ = a;
2081 _tmp37_ = self->priv->list;
2082 _tmp38_ = a;
2083 _tmp39_ = _tmp38_->index;
2084 _tmp40_ = dest;
2085 _tmp41_ = b;
2086 _tmp42_ = _tmp41_->length;
2087 _tmp43_ = a;
2088 _tmp44_ = _tmp43_->length;
2089 gee_tim_sort_slice_merge_in (_tmp36_, _tmp37_, _tmp39_, _tmp40_ + _tmp42_, _tmp44_);
2090 }
2091 _gee_tim_sort_slice_free0 (a);
2092 _gee_tim_sort_slice_free0 (b);
2093 return;
2094 }
2095 while (TRUE) {
2096 gint a_count;
2097 gint b_count;
2098 gint _tmp110_;
2099 gint _tmp246_;
2100 gint _tmp247_;
2101 a_count = 0;
2102 b_count = 0;
2103 while (TRUE) {
2104 GeeTimSortSlice* _tmp45_;
2105 void* _tmp46_ = NULL;
2106 GeeTimSortSlice* _tmp47_;
2107 void* _tmp48_ = NULL;
2108 gboolean _tmp49_ = FALSE;
2109 _tmp45_ = b;
2110 _tmp46_ = gee_tim_sort_slice_peek_first (_tmp45_);
2111 _tmp47_ = a;
2112 _tmp48_ = gee_tim_sort_slice_peek_first (_tmp47_);
2113 _tmp49_ = gee_tim_sort_lower_than (self, _tmp46_, _tmp48_);
2114 if (_tmp49_) {
2115 void** _tmp50_;
2116 gint _tmp51_;
2117 GeeTimSortSlice* _tmp52_;
2118 void* _tmp53_ = NULL;
2119 void* _tmp54_;
2120 GeeTimSortSlice* _tmp55_;
2121 gint _tmp56_;
2122 gint _tmp77_;
2123 gint _tmp78_;
2124 gint _tmp79_;
2125 _tmp50_ = self->priv->list;
2126 _tmp51_ = dest;
2127 dest = _tmp51_ + 1;
2128 _tmp52_ = b;
2129 _tmp53_ = gee_tim_sort_slice_pop_first (_tmp52_);
2130 _tmp50_[_tmp51_] = _tmp53_;
2131 _tmp54_ = _tmp50_[_tmp51_];
2132 _tmp55_ = b;
2133 _tmp56_ = _tmp55_->length;
2134 if (_tmp56_ == 0) {
2135 {
2136 GeeTimSortSlice* _tmp57_;
2137 gint _tmp58_;
2138 GeeTimSortSlice* _tmp59_;
2139 gint _tmp60_;
2140 GeeTimSortSlice* _tmp61_;
2141 void** _tmp62_;
2142 GeeTimSortSlice* _tmp63_;
2143 gint _tmp64_;
2144 gint _tmp65_;
2145 GeeTimSortSlice* _tmp66_;
2146 gint _tmp67_;
2147 GeeTimSortSlice* _tmp68_;
2148 void** _tmp69_;
2149 GeeTimSortSlice* _tmp70_;
2150 gint _tmp71_;
2151 gint _tmp72_;
2152 GeeTimSortSlice* _tmp73_;
2153 gint _tmp74_;
2154 GeeTimSortSlice* _tmp75_;
2155 gint _tmp76_;
2156 _tmp57_ = a;
2157 _tmp58_ = _tmp57_->length;
2158 _vala_assert (_tmp58_ >= 0, "a.length >= 0");
2159 _tmp59_ = b;
2160 _tmp60_ = _tmp59_->length;
2161 _vala_assert (_tmp60_ >= 0, "b.length >= 0");
2162 _tmp61_ = b;
2163 _tmp62_ = self->priv->list;
2164 _tmp63_ = b;
2165 _tmp64_ = _tmp63_->index;
2166 _tmp65_ = dest;
2167 _tmp66_ = b;
2168 _tmp67_ = _tmp66_->length;
2169 gee_tim_sort_slice_merge_in (_tmp61_, _tmp62_, _tmp64_, _tmp65_, _tmp67_);
2170 _tmp68_ = a;
2171 _tmp69_ = self->priv->list;
2172 _tmp70_ = a;
2173 _tmp71_ = _tmp70_->index;
2174 _tmp72_ = dest;
2175 _tmp73_ = b;
2176 _tmp74_ = _tmp73_->length;
2177 _tmp75_ = a;
2178 _tmp76_ = _tmp75_->length;
2179 gee_tim_sort_slice_merge_in (_tmp68_, _tmp69_, _tmp71_, _tmp72_ + _tmp74_, _tmp76_);
2180 }
2181 _gee_tim_sort_slice_free0 (a);
2182 _gee_tim_sort_slice_free0 (b);
2183 return;
2184 }
2185 _tmp77_ = b_count;
2186 b_count = _tmp77_ + 1;
2187 a_count = 0;
2188 _tmp78_ = b_count;
2189 _tmp79_ = minimum_gallop;
2190 if (_tmp78_ >= _tmp79_) {
2191 break;
2192 }
2193 } else {
2194 void** _tmp80_;
2195 gint _tmp81_;
2196 GeeTimSortSlice* _tmp82_;
2197 void* _tmp83_ = NULL;
2198 void* _tmp84_;
2199 GeeTimSortSlice* _tmp85_;
2200 gint _tmp86_;
2201 gint _tmp107_;
2202 gint _tmp108_;
2203 gint _tmp109_;
2204 _tmp80_ = self->priv->list;
2205 _tmp81_ = dest;
2206 dest = _tmp81_ + 1;
2207 _tmp82_ = a;
2208 _tmp83_ = gee_tim_sort_slice_pop_first (_tmp82_);
2209 _tmp80_[_tmp81_] = _tmp83_;
2210 _tmp84_ = _tmp80_[_tmp81_];
2211 _tmp85_ = a;
2212 _tmp86_ = _tmp85_->length;
2213 if (_tmp86_ == 1) {
2214 {
2215 GeeTimSortSlice* _tmp87_;
2216 gint _tmp88_;
2217 GeeTimSortSlice* _tmp89_;
2218 gint _tmp90_;
2219 GeeTimSortSlice* _tmp91_;
2220 void** _tmp92_;
2221 GeeTimSortSlice* _tmp93_;
2222 gint _tmp94_;
2223 gint _tmp95_;
2224 GeeTimSortSlice* _tmp96_;
2225 gint _tmp97_;
2226 GeeTimSortSlice* _tmp98_;
2227 void** _tmp99_;
2228 GeeTimSortSlice* _tmp100_;
2229 gint _tmp101_;
2230 gint _tmp102_;
2231 GeeTimSortSlice* _tmp103_;
2232 gint _tmp104_;
2233 GeeTimSortSlice* _tmp105_;
2234 gint _tmp106_;
2235 _tmp87_ = a;
2236 _tmp88_ = _tmp87_->length;
2237 _vala_assert (_tmp88_ >= 0, "a.length >= 0");
2238 _tmp89_ = b;
2239 _tmp90_ = _tmp89_->length;
2240 _vala_assert (_tmp90_ >= 0, "b.length >= 0");
2241 _tmp91_ = b;
2242 _tmp92_ = self->priv->list;
2243 _tmp93_ = b;
2244 _tmp94_ = _tmp93_->index;
2245 _tmp95_ = dest;
2246 _tmp96_ = b;
2247 _tmp97_ = _tmp96_->length;
2248 gee_tim_sort_slice_merge_in (_tmp91_, _tmp92_, _tmp94_, _tmp95_, _tmp97_);
2249 _tmp98_ = a;
2250 _tmp99_ = self->priv->list;
2251 _tmp100_ = a;
2252 _tmp101_ = _tmp100_->index;
2253 _tmp102_ = dest;
2254 _tmp103_ = b;
2255 _tmp104_ = _tmp103_->length;
2256 _tmp105_ = a;
2257 _tmp106_ = _tmp105_->length;
2258 gee_tim_sort_slice_merge_in (_tmp98_, _tmp99_, _tmp101_, _tmp102_ + _tmp104_, _tmp106_);
2259 }
2260 _gee_tim_sort_slice_free0 (a);
2261 _gee_tim_sort_slice_free0 (b);
2262 return;
2263 }
2264 _tmp107_ = a_count;
2265 a_count = _tmp107_ + 1;
2266 b_count = 0;
2267 _tmp108_ = a_count;
2268 _tmp109_ = minimum_gallop;
2269 if (_tmp108_ >= _tmp109_) {
2270 break;
2271 }
2272 }
2273 }
2274 _tmp110_ = minimum_gallop;
2275 minimum_gallop = _tmp110_ + 1;
2276 while (TRUE) {
2277 gint _tmp111_ = 0;
2278 gint _tmp112_;
2279 gint _tmp113_;
2280 gint _tmp114_;
2281 gint _tmp115_;
2282 GeeTimSortSlice* _tmp116_;
2283 void* _tmp117_ = NULL;
2284 GeeTimSortSlice* _tmp118_;
2285 gint _tmp119_ = 0;
2286 GeeTimSortSlice* _tmp120_;
2287 void** _tmp121_;
2288 GeeTimSortSlice* _tmp122_;
2289 gint _tmp123_;
2290 gint _tmp124_;
2291 gint _tmp125_;
2292 gint _tmp126_;
2293 gint _tmp127_;
2294 GeeTimSortSlice* _tmp128_;
2295 gint _tmp129_;
2296 GeeTimSortSlice* _tmp130_;
2297 gint _tmp131_;
2298 void** _tmp152_;
2299 gint _tmp153_;
2300 GeeTimSortSlice* _tmp154_;
2301 void* _tmp155_ = NULL;
2302 void* _tmp156_;
2303 GeeTimSortSlice* _tmp157_;
2304 gint _tmp158_;
2305 GeeTimSortSlice* _tmp179_;
2306 void* _tmp180_ = NULL;
2307 GeeTimSortSlice* _tmp181_;
2308 gint _tmp182_ = 0;
2309 GeeTimSortSlice* _tmp183_;
2310 void** _tmp184_;
2311 GeeTimSortSlice* _tmp185_;
2312 gint _tmp186_;
2313 gint _tmp187_;
2314 gint _tmp188_;
2315 gint _tmp189_;
2316 gint _tmp190_;
2317 GeeTimSortSlice* _tmp191_;
2318 gint _tmp192_;
2319 GeeTimSortSlice* _tmp193_;
2320 gint _tmp194_;
2321 void** _tmp215_;
2322 gint _tmp216_;
2323 GeeTimSortSlice* _tmp217_;
2324 void* _tmp218_ = NULL;
2325 void* _tmp219_;
2326 GeeTimSortSlice* _tmp220_;
2327 gint _tmp221_;
2328 gboolean _tmp242_ = FALSE;
2329 gint _tmp243_;
2330 gboolean _tmp245_;
2331 _tmp112_ = minimum_gallop;
2332 if (_tmp112_ > 1) {
2333 _tmp111_ = 1;
2334 } else {
2335 _tmp111_ = 0;
2336 }
2337 _tmp113_ = minimum_gallop;
2338 _tmp114_ = _tmp111_;
2339 minimum_gallop = _tmp113_ - _tmp114_;
2340 _tmp115_ = minimum_gallop;
2341 self->priv->minimum_gallop = _tmp115_;
2342 _tmp116_ = b;
2343 _tmp117_ = gee_tim_sort_slice_peek_first (_tmp116_);
2344 _tmp118_ = a;
2345 _tmp119_ = gee_tim_sort_gallop_rightmost (self, _tmp117_, _tmp118_, 0);
2346 a_count = _tmp119_;
2347 _tmp120_ = a;
2348 _tmp121_ = self->priv->list;
2349 _tmp122_ = a;
2350 _tmp123_ = _tmp122_->index;
2351 _tmp124_ = dest;
2352 _tmp125_ = a_count;
2353 gee_tim_sort_slice_merge_in (_tmp120_, _tmp121_, _tmp123_, _tmp124_, _tmp125_);
2354 _tmp126_ = dest;
2355 _tmp127_ = a_count;
2356 dest = _tmp126_ + _tmp127_;
2357 _tmp128_ = a;
2358 _tmp129_ = a_count;
2359 gee_tim_sort_slice_shorten_start (_tmp128_, _tmp129_);
2360 _tmp130_ = a;
2361 _tmp131_ = _tmp130_->length;
2362 if (_tmp131_ <= 1) {
2363 {
2364 GeeTimSortSlice* _tmp132_;
2365 gint _tmp133_;
2366 GeeTimSortSlice* _tmp134_;
2367 gint _tmp135_;
2368 GeeTimSortSlice* _tmp136_;
2369 void** _tmp137_;
2370 GeeTimSortSlice* _tmp138_;
2371 gint _tmp139_;
2372 gint _tmp140_;
2373 GeeTimSortSlice* _tmp141_;
2374 gint _tmp142_;
2375 GeeTimSortSlice* _tmp143_;
2376 void** _tmp144_;
2377 GeeTimSortSlice* _tmp145_;
2378 gint _tmp146_;
2379 gint _tmp147_;
2380 GeeTimSortSlice* _tmp148_;
2381 gint _tmp149_;
2382 GeeTimSortSlice* _tmp150_;
2383 gint _tmp151_;
2384 _tmp132_ = a;
2385 _tmp133_ = _tmp132_->length;
2386 _vala_assert (_tmp133_ >= 0, "a.length >= 0");
2387 _tmp134_ = b;
2388 _tmp135_ = _tmp134_->length;
2389 _vala_assert (_tmp135_ >= 0, "b.length >= 0");
2390 _tmp136_ = b;
2391 _tmp137_ = self->priv->list;
2392 _tmp138_ = b;
2393 _tmp139_ = _tmp138_->index;
2394 _tmp140_ = dest;
2395 _tmp141_ = b;
2396 _tmp142_ = _tmp141_->length;
2397 gee_tim_sort_slice_merge_in (_tmp136_, _tmp137_, _tmp139_, _tmp140_, _tmp142_);
2398 _tmp143_ = a;
2399 _tmp144_ = self->priv->list;
2400 _tmp145_ = a;
2401 _tmp146_ = _tmp145_->index;
2402 _tmp147_ = dest;
2403 _tmp148_ = b;
2404 _tmp149_ = _tmp148_->length;
2405 _tmp150_ = a;
2406 _tmp151_ = _tmp150_->length;
2407 gee_tim_sort_slice_merge_in (_tmp143_, _tmp144_, _tmp146_, _tmp147_ + _tmp149_, _tmp151_);
2408 }
2409 _gee_tim_sort_slice_free0 (a);
2410 _gee_tim_sort_slice_free0 (b);
2411 return;
2412 }
2413 _tmp152_ = self->priv->list;
2414 _tmp153_ = dest;
2415 dest = _tmp153_ + 1;
2416 _tmp154_ = b;
2417 _tmp155_ = gee_tim_sort_slice_pop_first (_tmp154_);
2418 _tmp152_[_tmp153_] = _tmp155_;
2419 _tmp156_ = _tmp152_[_tmp153_];
2420 _tmp157_ = b;
2421 _tmp158_ = _tmp157_->length;
2422 if (_tmp158_ == 0) {
2423 {
2424 GeeTimSortSlice* _tmp159_;
2425 gint _tmp160_;
2426 GeeTimSortSlice* _tmp161_;
2427 gint _tmp162_;
2428 GeeTimSortSlice* _tmp163_;
2429 void** _tmp164_;
2430 GeeTimSortSlice* _tmp165_;
2431 gint _tmp166_;
2432 gint _tmp167_;
2433 GeeTimSortSlice* _tmp168_;
2434 gint _tmp169_;
2435 GeeTimSortSlice* _tmp170_;
2436 void** _tmp171_;
2437 GeeTimSortSlice* _tmp172_;
2438 gint _tmp173_;
2439 gint _tmp174_;
2440 GeeTimSortSlice* _tmp175_;
2441 gint _tmp176_;
2442 GeeTimSortSlice* _tmp177_;
2443 gint _tmp178_;
2444 _tmp159_ = a;
2445 _tmp160_ = _tmp159_->length;
2446 _vala_assert (_tmp160_ >= 0, "a.length >= 0");
2447 _tmp161_ = b;
2448 _tmp162_ = _tmp161_->length;
2449 _vala_assert (_tmp162_ >= 0, "b.length >= 0");
2450 _tmp163_ = b;
2451 _tmp164_ = self->priv->list;
2452 _tmp165_ = b;
2453 _tmp166_ = _tmp165_->index;
2454 _tmp167_ = dest;
2455 _tmp168_ = b;
2456 _tmp169_ = _tmp168_->length;
2457 gee_tim_sort_slice_merge_in (_tmp163_, _tmp164_, _tmp166_, _tmp167_, _tmp169_);
2458 _tmp170_ = a;
2459 _tmp171_ = self->priv->list;
2460 _tmp172_ = a;
2461 _tmp173_ = _tmp172_->index;
2462 _tmp174_ = dest;
2463 _tmp175_ = b;
2464 _tmp176_ = _tmp175_->length;
2465 _tmp177_ = a;
2466 _tmp178_ = _tmp177_->length;
2467 gee_tim_sort_slice_merge_in (_tmp170_, _tmp171_, _tmp173_, _tmp174_ + _tmp176_, _tmp178_);
2468 }
2469 _gee_tim_sort_slice_free0 (a);
2470 _gee_tim_sort_slice_free0 (b);
2471 return;
2472 }
2473 _tmp179_ = a;
2474 _tmp180_ = gee_tim_sort_slice_peek_first (_tmp179_);
2475 _tmp181_ = b;
2476 _tmp182_ = gee_tim_sort_gallop_leftmost (self, _tmp180_, _tmp181_, 0);
2477 b_count = _tmp182_;
2478 _tmp183_ = b;
2479 _tmp184_ = self->priv->list;
2480 _tmp185_ = b;
2481 _tmp186_ = _tmp185_->index;
2482 _tmp187_ = dest;
2483 _tmp188_ = b_count;
2484 gee_tim_sort_slice_merge_in (_tmp183_, _tmp184_, _tmp186_, _tmp187_, _tmp188_);
2485 _tmp189_ = dest;
2486 _tmp190_ = b_count;
2487 dest = _tmp189_ + _tmp190_;
2488 _tmp191_ = b;
2489 _tmp192_ = b_count;
2490 gee_tim_sort_slice_shorten_start (_tmp191_, _tmp192_);
2491 _tmp193_ = b;
2492 _tmp194_ = _tmp193_->length;
2493 if (_tmp194_ == 0) {
2494 {
2495 GeeTimSortSlice* _tmp195_;
2496 gint _tmp196_;
2497 GeeTimSortSlice* _tmp197_;
2498 gint _tmp198_;
2499 GeeTimSortSlice* _tmp199_;
2500 void** _tmp200_;
2501 GeeTimSortSlice* _tmp201_;
2502 gint _tmp202_;
2503 gint _tmp203_;
2504 GeeTimSortSlice* _tmp204_;
2505 gint _tmp205_;
2506 GeeTimSortSlice* _tmp206_;
2507 void** _tmp207_;
2508 GeeTimSortSlice* _tmp208_;
2509 gint _tmp209_;
2510 gint _tmp210_;
2511 GeeTimSortSlice* _tmp211_;
2512 gint _tmp212_;
2513 GeeTimSortSlice* _tmp213_;
2514 gint _tmp214_;
2515 _tmp195_ = a;
2516 _tmp196_ = _tmp195_->length;
2517 _vala_assert (_tmp196_ >= 0, "a.length >= 0");
2518 _tmp197_ = b;
2519 _tmp198_ = _tmp197_->length;
2520 _vala_assert (_tmp198_ >= 0, "b.length >= 0");
2521 _tmp199_ = b;
2522 _tmp200_ = self->priv->list;
2523 _tmp201_ = b;
2524 _tmp202_ = _tmp201_->index;
2525 _tmp203_ = dest;
2526 _tmp204_ = b;
2527 _tmp205_ = _tmp204_->length;
2528 gee_tim_sort_slice_merge_in (_tmp199_, _tmp200_, _tmp202_, _tmp203_, _tmp205_);
2529 _tmp206_ = a;
2530 _tmp207_ = self->priv->list;
2531 _tmp208_ = a;
2532 _tmp209_ = _tmp208_->index;
2533 _tmp210_ = dest;
2534 _tmp211_ = b;
2535 _tmp212_ = _tmp211_->length;
2536 _tmp213_ = a;
2537 _tmp214_ = _tmp213_->length;
2538 gee_tim_sort_slice_merge_in (_tmp206_, _tmp207_, _tmp209_, _tmp210_ + _tmp212_, _tmp214_);
2539 }
2540 _gee_tim_sort_slice_free0 (a);
2541 _gee_tim_sort_slice_free0 (b);
2542 return;
2543 }
2544 _tmp215_ = self->priv->list;
2545 _tmp216_ = dest;
2546 dest = _tmp216_ + 1;
2547 _tmp217_ = a;
2548 _tmp218_ = gee_tim_sort_slice_pop_first (_tmp217_);
2549 _tmp215_[_tmp216_] = _tmp218_;
2550 _tmp219_ = _tmp215_[_tmp216_];
2551 _tmp220_ = a;
2552 _tmp221_ = _tmp220_->length;
2553 if (_tmp221_ == 1) {
2554 {
2555 GeeTimSortSlice* _tmp222_;
2556 gint _tmp223_;
2557 GeeTimSortSlice* _tmp224_;
2558 gint _tmp225_;
2559 GeeTimSortSlice* _tmp226_;
2560 void** _tmp227_;
2561 GeeTimSortSlice* _tmp228_;
2562 gint _tmp229_;
2563 gint _tmp230_;
2564 GeeTimSortSlice* _tmp231_;
2565 gint _tmp232_;
2566 GeeTimSortSlice* _tmp233_;
2567 void** _tmp234_;
2568 GeeTimSortSlice* _tmp235_;
2569 gint _tmp236_;
2570 gint _tmp237_;
2571 GeeTimSortSlice* _tmp238_;
2572 gint _tmp239_;
2573 GeeTimSortSlice* _tmp240_;
2574 gint _tmp241_;
2575 _tmp222_ = a;
2576 _tmp223_ = _tmp222_->length;
2577 _vala_assert (_tmp223_ >= 0, "a.length >= 0");
2578 _tmp224_ = b;
2579 _tmp225_ = _tmp224_->length;
2580 _vala_assert (_tmp225_ >= 0, "b.length >= 0");
2581 _tmp226_ = b;
2582 _tmp227_ = self->priv->list;
2583 _tmp228_ = b;
2584 _tmp229_ = _tmp228_->index;
2585 _tmp230_ = dest;
2586 _tmp231_ = b;
2587 _tmp232_ = _tmp231_->length;
2588 gee_tim_sort_slice_merge_in (_tmp226_, _tmp227_, _tmp229_, _tmp230_, _tmp232_);
2589 _tmp233_ = a;
2590 _tmp234_ = self->priv->list;
2591 _tmp235_ = a;
2592 _tmp236_ = _tmp235_->index;
2593 _tmp237_ = dest;
2594 _tmp238_ = b;
2595 _tmp239_ = _tmp238_->length;
2596 _tmp240_ = a;
2597 _tmp241_ = _tmp240_->length;
2598 gee_tim_sort_slice_merge_in (_tmp233_, _tmp234_, _tmp236_, _tmp237_ + _tmp239_, _tmp241_);
2599 }
2600 _gee_tim_sort_slice_free0 (a);
2601 _gee_tim_sort_slice_free0 (b);
2602 return;
2603 }
2604 _tmp243_ = a_count;
2605 if (_tmp243_ < GEE_TIM_SORT_MINIMUM_GALLOP) {
2606 gint _tmp244_;
2607 _tmp244_ = b_count;
2608 _tmp242_ = _tmp244_ < GEE_TIM_SORT_MINIMUM_GALLOP;
2609 } else {
2610 _tmp242_ = FALSE;
2611 }
2612 _tmp245_ = _tmp242_;
2613 if (_tmp245_) {
2614 break;
2615 }
2616 }
2617 _tmp246_ = minimum_gallop;
2618 minimum_gallop = _tmp246_ + 1;
2619 _tmp247_ = minimum_gallop;
2620 self->priv->minimum_gallop = _tmp247_;
2621 }
2622 }
2623 __finally0:
2624 {
2625 GeeTimSortSlice* _tmp248_;
2626 gint _tmp249_;
2627 GeeTimSortSlice* _tmp250_;
2628 gint _tmp251_;
2629 GeeTimSortSlice* _tmp252_;
2630 void** _tmp253_;
2631 GeeTimSortSlice* _tmp254_;
2632 gint _tmp255_;
2633 gint _tmp256_;
2634 GeeTimSortSlice* _tmp257_;
2635 gint _tmp258_;
2636 GeeTimSortSlice* _tmp259_;
2637 void** _tmp260_;
2638 GeeTimSortSlice* _tmp261_;
2639 gint _tmp262_;
2640 gint _tmp263_;
2641 GeeTimSortSlice* _tmp264_;
2642 gint _tmp265_;
2643 GeeTimSortSlice* _tmp266_;
2644 gint _tmp267_;
2645 _tmp248_ = a;
2646 _tmp249_ = _tmp248_->length;
2647 _vala_assert (_tmp249_ >= 0, "a.length >= 0");
2648 _tmp250_ = b;
2649 _tmp251_ = _tmp250_->length;
2650 _vala_assert (_tmp251_ >= 0, "b.length >= 0");
2651 _tmp252_ = b;
2652 _tmp253_ = self->priv->list;
2653 _tmp254_ = b;
2654 _tmp255_ = _tmp254_->index;
2655 _tmp256_ = dest;
2656 _tmp257_ = b;
2657 _tmp258_ = _tmp257_->length;
2658 gee_tim_sort_slice_merge_in (_tmp252_, _tmp253_, _tmp255_, _tmp256_, _tmp258_);
2659 _tmp259_ = a;
2660 _tmp260_ = self->priv->list;
2661 _tmp261_ = a;
2662 _tmp262_ = _tmp261_->index;
2663 _tmp263_ = dest;
2664 _tmp264_ = b;
2665 _tmp265_ = _tmp264_->length;
2666 _tmp266_ = a;
2667 _tmp267_ = _tmp266_->length;
2668 gee_tim_sort_slice_merge_in (_tmp259_, _tmp260_, _tmp262_, _tmp263_ + _tmp265_, _tmp267_);
2669 }
2670 _gee_tim_sort_slice_free0 (a);
2671 _gee_tim_sort_slice_free0 (b);
2672 g_critical ("file %s: line %d: uncaught error: %s (%s, %d)", __FILE__, __LINE__, _inner_error_->message, g_quark_to_string (_inner_error_->domain), _inner_error_->code);
2673 g_clear_error (&_inner_error_);
2674 return;
2675 }
2676
2677
gee_tim_sort_merge_high(GeeTimSort * self,GeeTimSortSlice * a,GeeTimSortSlice * b)2678 static void gee_tim_sort_merge_high (GeeTimSort* self, GeeTimSortSlice* a, GeeTimSortSlice* b) {
2679 GeeTimSortSlice* _tmp0_;
2680 gint _tmp1_;
2681 GeeTimSortSlice* _tmp2_;
2682 gint _tmp3_;
2683 GeeTimSortSlice* _tmp4_;
2684 gint _tmp5_;
2685 GeeTimSortSlice* _tmp6_;
2686 gint _tmp7_;
2687 GeeTimSortSlice* _tmp8_;
2688 gint _tmp9_;
2689 gint _tmp10_;
2690 gint minimum_gallop;
2691 GeeTimSortSlice* _tmp11_;
2692 gint _tmp12_;
2693 GeeTimSortSlice* _tmp13_;
2694 gint _tmp14_;
2695 gint dest;
2696 GeeTimSortSlice* _tmp15_;
2697 GError * _inner_error_ = NULL;
2698 g_return_if_fail (self != NULL);
2699 g_return_if_fail (a != NULL);
2700 g_return_if_fail (b != NULL);
2701 _tmp0_ = a;
2702 _tmp1_ = _tmp0_->length;
2703 _vala_assert (_tmp1_ > 0, "a.length > 0");
2704 _tmp2_ = b;
2705 _tmp3_ = _tmp2_->length;
2706 _vala_assert (_tmp3_ > 0, "b.length > 0");
2707 _tmp4_ = a;
2708 _tmp5_ = _tmp4_->index;
2709 _tmp6_ = a;
2710 _tmp7_ = _tmp6_->length;
2711 _tmp8_ = b;
2712 _tmp9_ = _tmp8_->index;
2713 _vala_assert ((_tmp5_ + _tmp7_) == _tmp9_, "a.index + a.length == b.index");
2714 _tmp10_ = self->priv->minimum_gallop;
2715 minimum_gallop = _tmp10_;
2716 _tmp11_ = b;
2717 _tmp12_ = _tmp11_->index;
2718 _tmp13_ = b;
2719 _tmp14_ = _tmp13_->length;
2720 dest = _tmp12_ + _tmp14_;
2721 _tmp15_ = b;
2722 gee_tim_sort_slice_copy (_tmp15_);
2723 {
2724 void** _tmp16_;
2725 gint _tmp17_;
2726 gint _tmp18_;
2727 GeeTimSortSlice* _tmp19_;
2728 void* _tmp20_ = NULL;
2729 void* _tmp21_;
2730 gboolean _tmp22_ = FALSE;
2731 GeeTimSortSlice* _tmp23_;
2732 gint _tmp24_;
2733 gboolean _tmp27_;
2734 _tmp16_ = self->priv->list;
2735 _tmp17_ = dest;
2736 dest = _tmp17_ - 1;
2737 _tmp18_ = dest;
2738 _tmp19_ = a;
2739 _tmp20_ = gee_tim_sort_slice_pop_last (_tmp19_);
2740 _tmp16_[_tmp18_] = _tmp20_;
2741 _tmp21_ = _tmp16_[_tmp18_];
2742 _tmp23_ = a;
2743 _tmp24_ = _tmp23_->length;
2744 if (_tmp24_ == 0) {
2745 _tmp22_ = TRUE;
2746 } else {
2747 GeeTimSortSlice* _tmp25_;
2748 gint _tmp26_;
2749 _tmp25_ = b;
2750 _tmp26_ = _tmp25_->length;
2751 _tmp22_ = _tmp26_ == 1;
2752 }
2753 _tmp27_ = _tmp22_;
2754 if (_tmp27_) {
2755 {
2756 GeeTimSortSlice* _tmp28_;
2757 gint _tmp29_;
2758 GeeTimSortSlice* _tmp30_;
2759 gint _tmp31_;
2760 GeeTimSortSlice* _tmp32_;
2761 void** _tmp33_;
2762 GeeTimSortSlice* _tmp34_;
2763 gint _tmp35_;
2764 gint _tmp36_;
2765 GeeTimSortSlice* _tmp37_;
2766 gint _tmp38_;
2767 GeeTimSortSlice* _tmp39_;
2768 gint _tmp40_;
2769 GeeTimSortSlice* _tmp41_;
2770 void** _tmp42_;
2771 GeeTimSortSlice* _tmp43_;
2772 gint _tmp44_;
2773 gint _tmp45_;
2774 GeeTimSortSlice* _tmp46_;
2775 gint _tmp47_;
2776 GeeTimSortSlice* _tmp48_;
2777 gint _tmp49_;
2778 GeeTimSortSlice* _tmp50_;
2779 gint _tmp51_;
2780 _tmp28_ = a;
2781 _tmp29_ = _tmp28_->length;
2782 _vala_assert (_tmp29_ >= 0, "a.length >= 0");
2783 _tmp30_ = b;
2784 _tmp31_ = _tmp30_->length;
2785 _vala_assert (_tmp31_ >= 0, "b.length >= 0");
2786 _tmp32_ = a;
2787 _tmp33_ = self->priv->list;
2788 _tmp34_ = a;
2789 _tmp35_ = _tmp34_->index;
2790 _tmp36_ = dest;
2791 _tmp37_ = a;
2792 _tmp38_ = _tmp37_->length;
2793 _tmp39_ = a;
2794 _tmp40_ = _tmp39_->length;
2795 gee_tim_sort_slice_merge_in_reversed (_tmp32_, _tmp33_, _tmp35_, _tmp36_ - _tmp38_, _tmp40_);
2796 _tmp41_ = b;
2797 _tmp42_ = self->priv->list;
2798 _tmp43_ = b;
2799 _tmp44_ = _tmp43_->index;
2800 _tmp45_ = dest;
2801 _tmp46_ = a;
2802 _tmp47_ = _tmp46_->length;
2803 _tmp48_ = b;
2804 _tmp49_ = _tmp48_->length;
2805 _tmp50_ = b;
2806 _tmp51_ = _tmp50_->length;
2807 gee_tim_sort_slice_merge_in_reversed (_tmp41_, _tmp42_, _tmp44_, (_tmp45_ - _tmp47_) - _tmp49_, _tmp51_);
2808 }
2809 _gee_tim_sort_slice_free0 (a);
2810 _gee_tim_sort_slice_free0 (b);
2811 return;
2812 }
2813 while (TRUE) {
2814 gint a_count;
2815 gint b_count;
2816 gint _tmp127_;
2817 gint _tmp295_;
2818 gint _tmp296_;
2819 a_count = 0;
2820 b_count = 0;
2821 while (TRUE) {
2822 GeeTimSortSlice* _tmp52_;
2823 void* _tmp53_ = NULL;
2824 GeeTimSortSlice* _tmp54_;
2825 void* _tmp55_ = NULL;
2826 gboolean _tmp56_ = FALSE;
2827 _tmp52_ = b;
2828 _tmp53_ = gee_tim_sort_slice_peek_last (_tmp52_);
2829 _tmp54_ = a;
2830 _tmp55_ = gee_tim_sort_slice_peek_last (_tmp54_);
2831 _tmp56_ = gee_tim_sort_lower_than (self, _tmp53_, _tmp55_);
2832 if (_tmp56_) {
2833 void** _tmp57_;
2834 gint _tmp58_;
2835 gint _tmp59_;
2836 GeeTimSortSlice* _tmp60_;
2837 void* _tmp61_ = NULL;
2838 void* _tmp62_;
2839 GeeTimSortSlice* _tmp63_;
2840 gint _tmp64_;
2841 gint _tmp89_;
2842 gint _tmp90_;
2843 gint _tmp91_;
2844 _tmp57_ = self->priv->list;
2845 _tmp58_ = dest;
2846 dest = _tmp58_ - 1;
2847 _tmp59_ = dest;
2848 _tmp60_ = a;
2849 _tmp61_ = gee_tim_sort_slice_pop_last (_tmp60_);
2850 _tmp57_[_tmp59_] = _tmp61_;
2851 _tmp62_ = _tmp57_[_tmp59_];
2852 _tmp63_ = a;
2853 _tmp64_ = _tmp63_->length;
2854 if (_tmp64_ == 0) {
2855 {
2856 GeeTimSortSlice* _tmp65_;
2857 gint _tmp66_;
2858 GeeTimSortSlice* _tmp67_;
2859 gint _tmp68_;
2860 GeeTimSortSlice* _tmp69_;
2861 void** _tmp70_;
2862 GeeTimSortSlice* _tmp71_;
2863 gint _tmp72_;
2864 gint _tmp73_;
2865 GeeTimSortSlice* _tmp74_;
2866 gint _tmp75_;
2867 GeeTimSortSlice* _tmp76_;
2868 gint _tmp77_;
2869 GeeTimSortSlice* _tmp78_;
2870 void** _tmp79_;
2871 GeeTimSortSlice* _tmp80_;
2872 gint _tmp81_;
2873 gint _tmp82_;
2874 GeeTimSortSlice* _tmp83_;
2875 gint _tmp84_;
2876 GeeTimSortSlice* _tmp85_;
2877 gint _tmp86_;
2878 GeeTimSortSlice* _tmp87_;
2879 gint _tmp88_;
2880 _tmp65_ = a;
2881 _tmp66_ = _tmp65_->length;
2882 _vala_assert (_tmp66_ >= 0, "a.length >= 0");
2883 _tmp67_ = b;
2884 _tmp68_ = _tmp67_->length;
2885 _vala_assert (_tmp68_ >= 0, "b.length >= 0");
2886 _tmp69_ = a;
2887 _tmp70_ = self->priv->list;
2888 _tmp71_ = a;
2889 _tmp72_ = _tmp71_->index;
2890 _tmp73_ = dest;
2891 _tmp74_ = a;
2892 _tmp75_ = _tmp74_->length;
2893 _tmp76_ = a;
2894 _tmp77_ = _tmp76_->length;
2895 gee_tim_sort_slice_merge_in_reversed (_tmp69_, _tmp70_, _tmp72_, _tmp73_ - _tmp75_, _tmp77_);
2896 _tmp78_ = b;
2897 _tmp79_ = self->priv->list;
2898 _tmp80_ = b;
2899 _tmp81_ = _tmp80_->index;
2900 _tmp82_ = dest;
2901 _tmp83_ = a;
2902 _tmp84_ = _tmp83_->length;
2903 _tmp85_ = b;
2904 _tmp86_ = _tmp85_->length;
2905 _tmp87_ = b;
2906 _tmp88_ = _tmp87_->length;
2907 gee_tim_sort_slice_merge_in_reversed (_tmp78_, _tmp79_, _tmp81_, (_tmp82_ - _tmp84_) - _tmp86_, _tmp88_);
2908 }
2909 _gee_tim_sort_slice_free0 (a);
2910 _gee_tim_sort_slice_free0 (b);
2911 return;
2912 }
2913 _tmp89_ = a_count;
2914 a_count = _tmp89_ + 1;
2915 b_count = 0;
2916 _tmp90_ = a_count;
2917 _tmp91_ = minimum_gallop;
2918 if (_tmp90_ >= _tmp91_) {
2919 break;
2920 }
2921 } else {
2922 void** _tmp92_;
2923 gint _tmp93_;
2924 gint _tmp94_;
2925 GeeTimSortSlice* _tmp95_;
2926 void* _tmp96_ = NULL;
2927 void* _tmp97_;
2928 GeeTimSortSlice* _tmp98_;
2929 gint _tmp99_;
2930 gint _tmp124_;
2931 gint _tmp125_;
2932 gint _tmp126_;
2933 _tmp92_ = self->priv->list;
2934 _tmp93_ = dest;
2935 dest = _tmp93_ - 1;
2936 _tmp94_ = dest;
2937 _tmp95_ = b;
2938 _tmp96_ = gee_tim_sort_slice_pop_last (_tmp95_);
2939 _tmp92_[_tmp94_] = _tmp96_;
2940 _tmp97_ = _tmp92_[_tmp94_];
2941 _tmp98_ = b;
2942 _tmp99_ = _tmp98_->length;
2943 if (_tmp99_ == 1) {
2944 {
2945 GeeTimSortSlice* _tmp100_;
2946 gint _tmp101_;
2947 GeeTimSortSlice* _tmp102_;
2948 gint _tmp103_;
2949 GeeTimSortSlice* _tmp104_;
2950 void** _tmp105_;
2951 GeeTimSortSlice* _tmp106_;
2952 gint _tmp107_;
2953 gint _tmp108_;
2954 GeeTimSortSlice* _tmp109_;
2955 gint _tmp110_;
2956 GeeTimSortSlice* _tmp111_;
2957 gint _tmp112_;
2958 GeeTimSortSlice* _tmp113_;
2959 void** _tmp114_;
2960 GeeTimSortSlice* _tmp115_;
2961 gint _tmp116_;
2962 gint _tmp117_;
2963 GeeTimSortSlice* _tmp118_;
2964 gint _tmp119_;
2965 GeeTimSortSlice* _tmp120_;
2966 gint _tmp121_;
2967 GeeTimSortSlice* _tmp122_;
2968 gint _tmp123_;
2969 _tmp100_ = a;
2970 _tmp101_ = _tmp100_->length;
2971 _vala_assert (_tmp101_ >= 0, "a.length >= 0");
2972 _tmp102_ = b;
2973 _tmp103_ = _tmp102_->length;
2974 _vala_assert (_tmp103_ >= 0, "b.length >= 0");
2975 _tmp104_ = a;
2976 _tmp105_ = self->priv->list;
2977 _tmp106_ = a;
2978 _tmp107_ = _tmp106_->index;
2979 _tmp108_ = dest;
2980 _tmp109_ = a;
2981 _tmp110_ = _tmp109_->length;
2982 _tmp111_ = a;
2983 _tmp112_ = _tmp111_->length;
2984 gee_tim_sort_slice_merge_in_reversed (_tmp104_, _tmp105_, _tmp107_, _tmp108_ - _tmp110_, _tmp112_);
2985 _tmp113_ = b;
2986 _tmp114_ = self->priv->list;
2987 _tmp115_ = b;
2988 _tmp116_ = _tmp115_->index;
2989 _tmp117_ = dest;
2990 _tmp118_ = a;
2991 _tmp119_ = _tmp118_->length;
2992 _tmp120_ = b;
2993 _tmp121_ = _tmp120_->length;
2994 _tmp122_ = b;
2995 _tmp123_ = _tmp122_->length;
2996 gee_tim_sort_slice_merge_in_reversed (_tmp113_, _tmp114_, _tmp116_, (_tmp117_ - _tmp119_) - _tmp121_, _tmp123_);
2997 }
2998 _gee_tim_sort_slice_free0 (a);
2999 _gee_tim_sort_slice_free0 (b);
3000 return;
3001 }
3002 _tmp124_ = b_count;
3003 b_count = _tmp124_ + 1;
3004 a_count = 0;
3005 _tmp125_ = b_count;
3006 _tmp126_ = minimum_gallop;
3007 if (_tmp125_ >= _tmp126_) {
3008 break;
3009 }
3010 }
3011 }
3012 _tmp127_ = minimum_gallop;
3013 minimum_gallop = _tmp127_ + 1;
3014 while (TRUE) {
3015 gint _tmp128_ = 0;
3016 gint _tmp129_;
3017 gint _tmp130_;
3018 gint _tmp131_;
3019 gint _tmp132_;
3020 GeeTimSortSlice* _tmp133_;
3021 void* _tmp134_ = NULL;
3022 GeeTimSortSlice* _tmp135_;
3023 GeeTimSortSlice* _tmp136_;
3024 gint _tmp137_;
3025 gint _tmp138_ = 0;
3026 gint k;
3027 GeeTimSortSlice* _tmp139_;
3028 gint _tmp140_;
3029 gint _tmp141_;
3030 GeeTimSortSlice* _tmp142_;
3031 void** _tmp143_;
3032 GeeTimSortSlice* _tmp144_;
3033 gint _tmp145_;
3034 gint _tmp146_;
3035 gint _tmp147_;
3036 gint _tmp148_;
3037 gint _tmp149_;
3038 gint _tmp150_;
3039 gint _tmp151_;
3040 GeeTimSortSlice* _tmp152_;
3041 gint _tmp153_;
3042 GeeTimSortSlice* _tmp154_;
3043 gint _tmp155_;
3044 void** _tmp180_;
3045 gint _tmp181_;
3046 gint _tmp182_;
3047 GeeTimSortSlice* _tmp183_;
3048 void* _tmp184_ = NULL;
3049 void* _tmp185_;
3050 GeeTimSortSlice* _tmp186_;
3051 gint _tmp187_;
3052 GeeTimSortSlice* _tmp212_;
3053 void* _tmp213_ = NULL;
3054 GeeTimSortSlice* _tmp214_;
3055 GeeTimSortSlice* _tmp215_;
3056 gint _tmp216_;
3057 gint _tmp217_ = 0;
3058 GeeTimSortSlice* _tmp218_;
3059 gint _tmp219_;
3060 gint _tmp220_;
3061 GeeTimSortSlice* _tmp221_;
3062 void** _tmp222_;
3063 GeeTimSortSlice* _tmp223_;
3064 gint _tmp224_;
3065 gint _tmp225_;
3066 gint _tmp226_;
3067 gint _tmp227_;
3068 gint _tmp228_;
3069 gint _tmp229_;
3070 gint _tmp230_;
3071 GeeTimSortSlice* _tmp231_;
3072 gint _tmp232_;
3073 GeeTimSortSlice* _tmp233_;
3074 gint _tmp234_;
3075 void** _tmp259_;
3076 gint _tmp260_;
3077 gint _tmp261_;
3078 GeeTimSortSlice* _tmp262_;
3079 void* _tmp263_ = NULL;
3080 void* _tmp264_;
3081 GeeTimSortSlice* _tmp265_;
3082 gint _tmp266_;
3083 gboolean _tmp291_ = FALSE;
3084 gint _tmp292_;
3085 gboolean _tmp294_;
3086 _tmp129_ = minimum_gallop;
3087 if (_tmp129_ > 1) {
3088 _tmp128_ = 1;
3089 } else {
3090 _tmp128_ = 0;
3091 }
3092 _tmp130_ = minimum_gallop;
3093 _tmp131_ = _tmp128_;
3094 minimum_gallop = _tmp130_ - _tmp131_;
3095 _tmp132_ = minimum_gallop;
3096 self->priv->minimum_gallop = _tmp132_;
3097 _tmp133_ = b;
3098 _tmp134_ = gee_tim_sort_slice_peek_last (_tmp133_);
3099 _tmp135_ = a;
3100 _tmp136_ = a;
3101 _tmp137_ = _tmp136_->length;
3102 _tmp138_ = gee_tim_sort_gallop_rightmost (self, _tmp134_, _tmp135_, _tmp137_ - 1);
3103 k = _tmp138_;
3104 _tmp139_ = a;
3105 _tmp140_ = _tmp139_->length;
3106 _tmp141_ = k;
3107 a_count = _tmp140_ - _tmp141_;
3108 _tmp142_ = a;
3109 _tmp143_ = self->priv->list;
3110 _tmp144_ = a;
3111 _tmp145_ = _tmp144_->index;
3112 _tmp146_ = k;
3113 _tmp147_ = dest;
3114 _tmp148_ = a_count;
3115 _tmp149_ = a_count;
3116 gee_tim_sort_slice_merge_in_reversed (_tmp142_, _tmp143_, _tmp145_ + _tmp146_, _tmp147_ - _tmp148_, _tmp149_);
3117 _tmp150_ = dest;
3118 _tmp151_ = a_count;
3119 dest = _tmp150_ - _tmp151_;
3120 _tmp152_ = a;
3121 _tmp153_ = a_count;
3122 gee_tim_sort_slice_shorten_end (_tmp152_, _tmp153_);
3123 _tmp154_ = a;
3124 _tmp155_ = _tmp154_->length;
3125 if (_tmp155_ == 0) {
3126 {
3127 GeeTimSortSlice* _tmp156_;
3128 gint _tmp157_;
3129 GeeTimSortSlice* _tmp158_;
3130 gint _tmp159_;
3131 GeeTimSortSlice* _tmp160_;
3132 void** _tmp161_;
3133 GeeTimSortSlice* _tmp162_;
3134 gint _tmp163_;
3135 gint _tmp164_;
3136 GeeTimSortSlice* _tmp165_;
3137 gint _tmp166_;
3138 GeeTimSortSlice* _tmp167_;
3139 gint _tmp168_;
3140 GeeTimSortSlice* _tmp169_;
3141 void** _tmp170_;
3142 GeeTimSortSlice* _tmp171_;
3143 gint _tmp172_;
3144 gint _tmp173_;
3145 GeeTimSortSlice* _tmp174_;
3146 gint _tmp175_;
3147 GeeTimSortSlice* _tmp176_;
3148 gint _tmp177_;
3149 GeeTimSortSlice* _tmp178_;
3150 gint _tmp179_;
3151 _tmp156_ = a;
3152 _tmp157_ = _tmp156_->length;
3153 _vala_assert (_tmp157_ >= 0, "a.length >= 0");
3154 _tmp158_ = b;
3155 _tmp159_ = _tmp158_->length;
3156 _vala_assert (_tmp159_ >= 0, "b.length >= 0");
3157 _tmp160_ = a;
3158 _tmp161_ = self->priv->list;
3159 _tmp162_ = a;
3160 _tmp163_ = _tmp162_->index;
3161 _tmp164_ = dest;
3162 _tmp165_ = a;
3163 _tmp166_ = _tmp165_->length;
3164 _tmp167_ = a;
3165 _tmp168_ = _tmp167_->length;
3166 gee_tim_sort_slice_merge_in_reversed (_tmp160_, _tmp161_, _tmp163_, _tmp164_ - _tmp166_, _tmp168_);
3167 _tmp169_ = b;
3168 _tmp170_ = self->priv->list;
3169 _tmp171_ = b;
3170 _tmp172_ = _tmp171_->index;
3171 _tmp173_ = dest;
3172 _tmp174_ = a;
3173 _tmp175_ = _tmp174_->length;
3174 _tmp176_ = b;
3175 _tmp177_ = _tmp176_->length;
3176 _tmp178_ = b;
3177 _tmp179_ = _tmp178_->length;
3178 gee_tim_sort_slice_merge_in_reversed (_tmp169_, _tmp170_, _tmp172_, (_tmp173_ - _tmp175_) - _tmp177_, _tmp179_);
3179 }
3180 _gee_tim_sort_slice_free0 (a);
3181 _gee_tim_sort_slice_free0 (b);
3182 return;
3183 }
3184 _tmp180_ = self->priv->list;
3185 _tmp181_ = dest;
3186 dest = _tmp181_ - 1;
3187 _tmp182_ = dest;
3188 _tmp183_ = b;
3189 _tmp184_ = gee_tim_sort_slice_pop_last (_tmp183_);
3190 _tmp180_[_tmp182_] = _tmp184_;
3191 _tmp185_ = _tmp180_[_tmp182_];
3192 _tmp186_ = b;
3193 _tmp187_ = _tmp186_->length;
3194 if (_tmp187_ == 1) {
3195 {
3196 GeeTimSortSlice* _tmp188_;
3197 gint _tmp189_;
3198 GeeTimSortSlice* _tmp190_;
3199 gint _tmp191_;
3200 GeeTimSortSlice* _tmp192_;
3201 void** _tmp193_;
3202 GeeTimSortSlice* _tmp194_;
3203 gint _tmp195_;
3204 gint _tmp196_;
3205 GeeTimSortSlice* _tmp197_;
3206 gint _tmp198_;
3207 GeeTimSortSlice* _tmp199_;
3208 gint _tmp200_;
3209 GeeTimSortSlice* _tmp201_;
3210 void** _tmp202_;
3211 GeeTimSortSlice* _tmp203_;
3212 gint _tmp204_;
3213 gint _tmp205_;
3214 GeeTimSortSlice* _tmp206_;
3215 gint _tmp207_;
3216 GeeTimSortSlice* _tmp208_;
3217 gint _tmp209_;
3218 GeeTimSortSlice* _tmp210_;
3219 gint _tmp211_;
3220 _tmp188_ = a;
3221 _tmp189_ = _tmp188_->length;
3222 _vala_assert (_tmp189_ >= 0, "a.length >= 0");
3223 _tmp190_ = b;
3224 _tmp191_ = _tmp190_->length;
3225 _vala_assert (_tmp191_ >= 0, "b.length >= 0");
3226 _tmp192_ = a;
3227 _tmp193_ = self->priv->list;
3228 _tmp194_ = a;
3229 _tmp195_ = _tmp194_->index;
3230 _tmp196_ = dest;
3231 _tmp197_ = a;
3232 _tmp198_ = _tmp197_->length;
3233 _tmp199_ = a;
3234 _tmp200_ = _tmp199_->length;
3235 gee_tim_sort_slice_merge_in_reversed (_tmp192_, _tmp193_, _tmp195_, _tmp196_ - _tmp198_, _tmp200_);
3236 _tmp201_ = b;
3237 _tmp202_ = self->priv->list;
3238 _tmp203_ = b;
3239 _tmp204_ = _tmp203_->index;
3240 _tmp205_ = dest;
3241 _tmp206_ = a;
3242 _tmp207_ = _tmp206_->length;
3243 _tmp208_ = b;
3244 _tmp209_ = _tmp208_->length;
3245 _tmp210_ = b;
3246 _tmp211_ = _tmp210_->length;
3247 gee_tim_sort_slice_merge_in_reversed (_tmp201_, _tmp202_, _tmp204_, (_tmp205_ - _tmp207_) - _tmp209_, _tmp211_);
3248 }
3249 _gee_tim_sort_slice_free0 (a);
3250 _gee_tim_sort_slice_free0 (b);
3251 return;
3252 }
3253 _tmp212_ = a;
3254 _tmp213_ = gee_tim_sort_slice_peek_last (_tmp212_);
3255 _tmp214_ = b;
3256 _tmp215_ = b;
3257 _tmp216_ = _tmp215_->length;
3258 _tmp217_ = gee_tim_sort_gallop_leftmost (self, _tmp213_, _tmp214_, _tmp216_ - 1);
3259 k = _tmp217_;
3260 _tmp218_ = b;
3261 _tmp219_ = _tmp218_->length;
3262 _tmp220_ = k;
3263 b_count = _tmp219_ - _tmp220_;
3264 _tmp221_ = b;
3265 _tmp222_ = self->priv->list;
3266 _tmp223_ = b;
3267 _tmp224_ = _tmp223_->index;
3268 _tmp225_ = k;
3269 _tmp226_ = dest;
3270 _tmp227_ = b_count;
3271 _tmp228_ = b_count;
3272 gee_tim_sort_slice_merge_in_reversed (_tmp221_, _tmp222_, _tmp224_ + _tmp225_, _tmp226_ - _tmp227_, _tmp228_);
3273 _tmp229_ = dest;
3274 _tmp230_ = b_count;
3275 dest = _tmp229_ - _tmp230_;
3276 _tmp231_ = b;
3277 _tmp232_ = b_count;
3278 gee_tim_sort_slice_shorten_end (_tmp231_, _tmp232_);
3279 _tmp233_ = b;
3280 _tmp234_ = _tmp233_->length;
3281 if (_tmp234_ <= 1) {
3282 {
3283 GeeTimSortSlice* _tmp235_;
3284 gint _tmp236_;
3285 GeeTimSortSlice* _tmp237_;
3286 gint _tmp238_;
3287 GeeTimSortSlice* _tmp239_;
3288 void** _tmp240_;
3289 GeeTimSortSlice* _tmp241_;
3290 gint _tmp242_;
3291 gint _tmp243_;
3292 GeeTimSortSlice* _tmp244_;
3293 gint _tmp245_;
3294 GeeTimSortSlice* _tmp246_;
3295 gint _tmp247_;
3296 GeeTimSortSlice* _tmp248_;
3297 void** _tmp249_;
3298 GeeTimSortSlice* _tmp250_;
3299 gint _tmp251_;
3300 gint _tmp252_;
3301 GeeTimSortSlice* _tmp253_;
3302 gint _tmp254_;
3303 GeeTimSortSlice* _tmp255_;
3304 gint _tmp256_;
3305 GeeTimSortSlice* _tmp257_;
3306 gint _tmp258_;
3307 _tmp235_ = a;
3308 _tmp236_ = _tmp235_->length;
3309 _vala_assert (_tmp236_ >= 0, "a.length >= 0");
3310 _tmp237_ = b;
3311 _tmp238_ = _tmp237_->length;
3312 _vala_assert (_tmp238_ >= 0, "b.length >= 0");
3313 _tmp239_ = a;
3314 _tmp240_ = self->priv->list;
3315 _tmp241_ = a;
3316 _tmp242_ = _tmp241_->index;
3317 _tmp243_ = dest;
3318 _tmp244_ = a;
3319 _tmp245_ = _tmp244_->length;
3320 _tmp246_ = a;
3321 _tmp247_ = _tmp246_->length;
3322 gee_tim_sort_slice_merge_in_reversed (_tmp239_, _tmp240_, _tmp242_, _tmp243_ - _tmp245_, _tmp247_);
3323 _tmp248_ = b;
3324 _tmp249_ = self->priv->list;
3325 _tmp250_ = b;
3326 _tmp251_ = _tmp250_->index;
3327 _tmp252_ = dest;
3328 _tmp253_ = a;
3329 _tmp254_ = _tmp253_->length;
3330 _tmp255_ = b;
3331 _tmp256_ = _tmp255_->length;
3332 _tmp257_ = b;
3333 _tmp258_ = _tmp257_->length;
3334 gee_tim_sort_slice_merge_in_reversed (_tmp248_, _tmp249_, _tmp251_, (_tmp252_ - _tmp254_) - _tmp256_, _tmp258_);
3335 }
3336 _gee_tim_sort_slice_free0 (a);
3337 _gee_tim_sort_slice_free0 (b);
3338 return;
3339 }
3340 _tmp259_ = self->priv->list;
3341 _tmp260_ = dest;
3342 dest = _tmp260_ - 1;
3343 _tmp261_ = dest;
3344 _tmp262_ = a;
3345 _tmp263_ = gee_tim_sort_slice_pop_last (_tmp262_);
3346 _tmp259_[_tmp261_] = _tmp263_;
3347 _tmp264_ = _tmp259_[_tmp261_];
3348 _tmp265_ = a;
3349 _tmp266_ = _tmp265_->length;
3350 if (_tmp266_ == 0) {
3351 {
3352 GeeTimSortSlice* _tmp267_;
3353 gint _tmp268_;
3354 GeeTimSortSlice* _tmp269_;
3355 gint _tmp270_;
3356 GeeTimSortSlice* _tmp271_;
3357 void** _tmp272_;
3358 GeeTimSortSlice* _tmp273_;
3359 gint _tmp274_;
3360 gint _tmp275_;
3361 GeeTimSortSlice* _tmp276_;
3362 gint _tmp277_;
3363 GeeTimSortSlice* _tmp278_;
3364 gint _tmp279_;
3365 GeeTimSortSlice* _tmp280_;
3366 void** _tmp281_;
3367 GeeTimSortSlice* _tmp282_;
3368 gint _tmp283_;
3369 gint _tmp284_;
3370 GeeTimSortSlice* _tmp285_;
3371 gint _tmp286_;
3372 GeeTimSortSlice* _tmp287_;
3373 gint _tmp288_;
3374 GeeTimSortSlice* _tmp289_;
3375 gint _tmp290_;
3376 _tmp267_ = a;
3377 _tmp268_ = _tmp267_->length;
3378 _vala_assert (_tmp268_ >= 0, "a.length >= 0");
3379 _tmp269_ = b;
3380 _tmp270_ = _tmp269_->length;
3381 _vala_assert (_tmp270_ >= 0, "b.length >= 0");
3382 _tmp271_ = a;
3383 _tmp272_ = self->priv->list;
3384 _tmp273_ = a;
3385 _tmp274_ = _tmp273_->index;
3386 _tmp275_ = dest;
3387 _tmp276_ = a;
3388 _tmp277_ = _tmp276_->length;
3389 _tmp278_ = a;
3390 _tmp279_ = _tmp278_->length;
3391 gee_tim_sort_slice_merge_in_reversed (_tmp271_, _tmp272_, _tmp274_, _tmp275_ - _tmp277_, _tmp279_);
3392 _tmp280_ = b;
3393 _tmp281_ = self->priv->list;
3394 _tmp282_ = b;
3395 _tmp283_ = _tmp282_->index;
3396 _tmp284_ = dest;
3397 _tmp285_ = a;
3398 _tmp286_ = _tmp285_->length;
3399 _tmp287_ = b;
3400 _tmp288_ = _tmp287_->length;
3401 _tmp289_ = b;
3402 _tmp290_ = _tmp289_->length;
3403 gee_tim_sort_slice_merge_in_reversed (_tmp280_, _tmp281_, _tmp283_, (_tmp284_ - _tmp286_) - _tmp288_, _tmp290_);
3404 }
3405 _gee_tim_sort_slice_free0 (a);
3406 _gee_tim_sort_slice_free0 (b);
3407 return;
3408 }
3409 _tmp292_ = a_count;
3410 if (_tmp292_ < GEE_TIM_SORT_MINIMUM_GALLOP) {
3411 gint _tmp293_;
3412 _tmp293_ = b_count;
3413 _tmp291_ = _tmp293_ < GEE_TIM_SORT_MINIMUM_GALLOP;
3414 } else {
3415 _tmp291_ = FALSE;
3416 }
3417 _tmp294_ = _tmp291_;
3418 if (_tmp294_) {
3419 break;
3420 }
3421 }
3422 _tmp295_ = minimum_gallop;
3423 minimum_gallop = _tmp295_ + 1;
3424 _tmp296_ = minimum_gallop;
3425 self->priv->minimum_gallop = _tmp296_;
3426 }
3427 }
3428 __finally1:
3429 {
3430 GeeTimSortSlice* _tmp297_;
3431 gint _tmp298_;
3432 GeeTimSortSlice* _tmp299_;
3433 gint _tmp300_;
3434 GeeTimSortSlice* _tmp301_;
3435 void** _tmp302_;
3436 GeeTimSortSlice* _tmp303_;
3437 gint _tmp304_;
3438 gint _tmp305_;
3439 GeeTimSortSlice* _tmp306_;
3440 gint _tmp307_;
3441 GeeTimSortSlice* _tmp308_;
3442 gint _tmp309_;
3443 GeeTimSortSlice* _tmp310_;
3444 void** _tmp311_;
3445 GeeTimSortSlice* _tmp312_;
3446 gint _tmp313_;
3447 gint _tmp314_;
3448 GeeTimSortSlice* _tmp315_;
3449 gint _tmp316_;
3450 GeeTimSortSlice* _tmp317_;
3451 gint _tmp318_;
3452 GeeTimSortSlice* _tmp319_;
3453 gint _tmp320_;
3454 _tmp297_ = a;
3455 _tmp298_ = _tmp297_->length;
3456 _vala_assert (_tmp298_ >= 0, "a.length >= 0");
3457 _tmp299_ = b;
3458 _tmp300_ = _tmp299_->length;
3459 _vala_assert (_tmp300_ >= 0, "b.length >= 0");
3460 _tmp301_ = a;
3461 _tmp302_ = self->priv->list;
3462 _tmp303_ = a;
3463 _tmp304_ = _tmp303_->index;
3464 _tmp305_ = dest;
3465 _tmp306_ = a;
3466 _tmp307_ = _tmp306_->length;
3467 _tmp308_ = a;
3468 _tmp309_ = _tmp308_->length;
3469 gee_tim_sort_slice_merge_in_reversed (_tmp301_, _tmp302_, _tmp304_, _tmp305_ - _tmp307_, _tmp309_);
3470 _tmp310_ = b;
3471 _tmp311_ = self->priv->list;
3472 _tmp312_ = b;
3473 _tmp313_ = _tmp312_->index;
3474 _tmp314_ = dest;
3475 _tmp315_ = a;
3476 _tmp316_ = _tmp315_->length;
3477 _tmp317_ = b;
3478 _tmp318_ = _tmp317_->length;
3479 _tmp319_ = b;
3480 _tmp320_ = _tmp319_->length;
3481 gee_tim_sort_slice_merge_in_reversed (_tmp310_, _tmp311_, _tmp313_, (_tmp314_ - _tmp316_) - _tmp318_, _tmp320_);
3482 }
3483 _gee_tim_sort_slice_free0 (a);
3484 _gee_tim_sort_slice_free0 (b);
3485 g_critical ("file %s: line %d: uncaught error: %s (%s, %d)", __FILE__, __LINE__, _inner_error_->message, g_quark_to_string (_inner_error_->domain), _inner_error_->code);
3486 g_clear_error (&_inner_error_);
3487 return;
3488 }
3489
3490
gee_tim_sort_construct(GType object_type,GType g_type,GBoxedCopyFunc g_dup_func,GDestroyNotify g_destroy_func)3491 GeeTimSort* gee_tim_sort_construct (GType object_type, GType g_type, GBoxedCopyFunc g_dup_func, GDestroyNotify g_destroy_func) {
3492 GeeTimSort * self = NULL;
3493 self = (GeeTimSort*) g_object_new (object_type, NULL);
3494 self->priv->g_type = g_type;
3495 self->priv->g_dup_func = g_dup_func;
3496 self->priv->g_destroy_func = g_destroy_func;
3497 return self;
3498 }
3499
3500
gee_tim_sort_new(GType g_type,GBoxedCopyFunc g_dup_func,GDestroyNotify g_destroy_func)3501 GeeTimSort* gee_tim_sort_new (GType g_type, GBoxedCopyFunc g_dup_func, GDestroyNotify g_destroy_func) {
3502 return gee_tim_sort_construct (GEE_TYPE_TIM_SORT, g_type, g_dup_func, g_destroy_func);
3503 }
3504
3505
gee_tim_sort_slice_new(void ** list,gint index,gint length)3506 static GeeTimSortSlice* gee_tim_sort_slice_new (void** list, gint index, gint length) {
3507 GeeTimSortSlice* self;
3508 void** _tmp0_;
3509 gint _tmp1_;
3510 gint _tmp2_;
3511 self = g_slice_new0 (GeeTimSortSlice);
3512 gee_tim_sort_slice_instance_init (self);
3513 _tmp0_ = list;
3514 self->list = _tmp0_;
3515 _tmp1_ = index;
3516 self->index = _tmp1_;
3517 _tmp2_ = length;
3518 self->length = _tmp2_;
3519 return self;
3520 }
3521
3522
gee_tim_sort_slice_copy(GeeTimSortSlice * self)3523 static void gee_tim_sort_slice_copy (GeeTimSortSlice* self) {
3524 void** _tmp0_;
3525 gint _tmp1_;
3526 gint _tmp2_;
3527 void* _tmp3_ = NULL;
3528 void** _tmp4_;
3529 g_return_if_fail (self != NULL);
3530 _tmp0_ = self->list;
3531 _tmp1_ = self->index;
3532 _tmp2_ = self->length;
3533 _tmp3_ = g_memdup (&_tmp0_[_tmp1_], ((guint) sizeof (gpointer)) * _tmp2_);
3534 self->new_list = _tmp3_;
3535 _tmp4_ = self->new_list;
3536 self->list = _tmp4_;
3537 self->index = 0;
3538 }
3539
3540
gee_tim_sort_slice_merge_in(GeeTimSortSlice * self,void ** dest_array,gint index,gint dest_index,gint count)3541 static inline void gee_tim_sort_slice_merge_in (GeeTimSortSlice* self, void** dest_array, gint index, gint dest_index, gint count) {
3542 void** _tmp0_;
3543 gint _tmp1_;
3544 void** _tmp2_;
3545 gint _tmp3_;
3546 gint _tmp4_;
3547 g_return_if_fail (self != NULL);
3548 _tmp0_ = dest_array;
3549 _tmp1_ = dest_index;
3550 _tmp2_ = self->list;
3551 _tmp3_ = index;
3552 _tmp4_ = count;
3553 g_memmove (&_tmp0_[_tmp1_], &_tmp2_[_tmp3_], (gsize) (sizeof (gpointer) * _tmp4_));
3554 }
3555
3556
gee_tim_sort_slice_merge_in_reversed(GeeTimSortSlice * self,void ** dest_array,gint index,gint dest_index,gint count)3557 static inline void gee_tim_sort_slice_merge_in_reversed (GeeTimSortSlice* self, void** dest_array, gint index, gint dest_index, gint count) {
3558 void** _tmp0_;
3559 gint _tmp1_;
3560 void** _tmp2_;
3561 gint _tmp3_;
3562 gint _tmp4_;
3563 g_return_if_fail (self != NULL);
3564 _tmp0_ = dest_array;
3565 _tmp1_ = dest_index;
3566 _tmp2_ = self->list;
3567 _tmp3_ = index;
3568 _tmp4_ = count;
3569 g_memmove (&_tmp0_[_tmp1_], &_tmp2_[_tmp3_], (gsize) (sizeof (gpointer) * _tmp4_));
3570 }
3571
3572
gee_tim_sort_slice_shorten_start(GeeTimSortSlice * self,gint n)3573 static inline void gee_tim_sort_slice_shorten_start (GeeTimSortSlice* self, gint n) {
3574 gint _tmp0_;
3575 gint _tmp1_;
3576 gint _tmp2_;
3577 gint _tmp3_;
3578 g_return_if_fail (self != NULL);
3579 _tmp0_ = self->index;
3580 _tmp1_ = n;
3581 self->index = _tmp0_ + _tmp1_;
3582 _tmp2_ = self->length;
3583 _tmp3_ = n;
3584 self->length = _tmp2_ - _tmp3_;
3585 }
3586
3587
gee_tim_sort_slice_shorten_end(GeeTimSortSlice * self,gint n)3588 static inline void gee_tim_sort_slice_shorten_end (GeeTimSortSlice* self, gint n) {
3589 gint _tmp0_;
3590 gint _tmp1_;
3591 g_return_if_fail (self != NULL);
3592 _tmp0_ = self->length;
3593 _tmp1_ = n;
3594 self->length = _tmp0_ - _tmp1_;
3595 }
3596
3597
gee_tim_sort_slice_pop_first(GeeTimSortSlice * self)3598 static inline void* gee_tim_sort_slice_pop_first (GeeTimSortSlice* self) {
3599 void* result = NULL;
3600 gint _tmp0_;
3601 void** _tmp1_;
3602 gint _tmp2_;
3603 void* _tmp3_;
3604 g_return_val_if_fail (self != NULL, NULL);
3605 _tmp0_ = self->length;
3606 self->length = _tmp0_ - 1;
3607 _tmp1_ = self->list;
3608 _tmp2_ = self->index;
3609 self->index = _tmp2_ + 1;
3610 _tmp3_ = _tmp1_[_tmp2_];
3611 result = _tmp3_;
3612 return result;
3613 }
3614
3615
gee_tim_sort_slice_pop_last(GeeTimSortSlice * self)3616 static inline void* gee_tim_sort_slice_pop_last (GeeTimSortSlice* self) {
3617 void* result = NULL;
3618 gint _tmp0_;
3619 void** _tmp1_;
3620 gint _tmp2_;
3621 gint _tmp3_;
3622 void* _tmp4_;
3623 g_return_val_if_fail (self != NULL, NULL);
3624 _tmp0_ = self->length;
3625 self->length = _tmp0_ - 1;
3626 _tmp1_ = self->list;
3627 _tmp2_ = self->index;
3628 _tmp3_ = self->length;
3629 _tmp4_ = _tmp1_[_tmp2_ + _tmp3_];
3630 result = _tmp4_;
3631 return result;
3632 }
3633
3634
gee_tim_sort_slice_peek_first(GeeTimSortSlice * self)3635 static inline void* gee_tim_sort_slice_peek_first (GeeTimSortSlice* self) {
3636 void* result = NULL;
3637 void** _tmp0_;
3638 gint _tmp1_;
3639 void* _tmp2_;
3640 g_return_val_if_fail (self != NULL, NULL);
3641 _tmp0_ = self->list;
3642 _tmp1_ = self->index;
3643 _tmp2_ = _tmp0_[_tmp1_];
3644 result = _tmp2_;
3645 return result;
3646 }
3647
3648
gee_tim_sort_slice_peek_last(GeeTimSortSlice * self)3649 static inline void* gee_tim_sort_slice_peek_last (GeeTimSortSlice* self) {
3650 void* result = NULL;
3651 void** _tmp0_;
3652 gint _tmp1_;
3653 gint _tmp2_;
3654 void* _tmp3_;
3655 g_return_val_if_fail (self != NULL, NULL);
3656 _tmp0_ = self->list;
3657 _tmp1_ = self->index;
3658 _tmp2_ = self->length;
3659 _tmp3_ = _tmp0_[(_tmp1_ + _tmp2_) - 1];
3660 result = _tmp3_;
3661 return result;
3662 }
3663
3664
gee_tim_sort_slice_reverse(GeeTimSortSlice * self)3665 static void gee_tim_sort_slice_reverse (GeeTimSortSlice* self) {
3666 gint _tmp0_;
3667 gint low;
3668 gint _tmp1_;
3669 gint _tmp2_;
3670 gint high;
3671 g_return_if_fail (self != NULL);
3672 _tmp0_ = self->index;
3673 low = _tmp0_;
3674 _tmp1_ = self->index;
3675 _tmp2_ = self->length;
3676 high = (_tmp1_ + _tmp2_) - 1;
3677 while (TRUE) {
3678 gint _tmp3_;
3679 gint _tmp4_;
3680 gint _tmp5_;
3681 gint _tmp6_;
3682 _tmp3_ = low;
3683 _tmp4_ = high;
3684 if (!(_tmp3_ < _tmp4_)) {
3685 break;
3686 }
3687 _tmp5_ = low;
3688 low = _tmp5_ + 1;
3689 _tmp6_ = high;
3690 high = _tmp6_ - 1;
3691 gee_tim_sort_slice_swap (self, _tmp5_, _tmp6_);
3692 }
3693 }
3694
3695
gee_tim_sort_slice_swap(GeeTimSortSlice * self,gint i,gint j)3696 static inline void gee_tim_sort_slice_swap (GeeTimSortSlice* self, gint i, gint j) {
3697 void** _tmp0_;
3698 gint _tmp1_;
3699 void* _tmp2_;
3700 void* temp;
3701 void** _tmp3_;
3702 gint _tmp4_;
3703 void** _tmp5_;
3704 gint _tmp6_;
3705 void* _tmp7_;
3706 void* _tmp8_;
3707 void** _tmp9_;
3708 gint _tmp10_;
3709 void* _tmp11_;
3710 g_return_if_fail (self != NULL);
3711 _tmp0_ = self->list;
3712 _tmp1_ = i;
3713 _tmp2_ = _tmp0_[_tmp1_];
3714 temp = _tmp2_;
3715 _tmp3_ = self->list;
3716 _tmp4_ = i;
3717 _tmp5_ = self->list;
3718 _tmp6_ = j;
3719 _tmp7_ = _tmp5_[_tmp6_];
3720 _tmp3_[_tmp4_] = _tmp7_;
3721 _tmp8_ = _tmp3_[_tmp4_];
3722 _tmp9_ = self->list;
3723 _tmp10_ = j;
3724 _tmp9_[_tmp10_] = temp;
3725 _tmp11_ = _tmp9_[_tmp10_];
3726 }
3727
3728
gee_tim_sort_slice_instance_init(GeeTimSortSlice * self)3729 static void gee_tim_sort_slice_instance_init (GeeTimSortSlice * self) {
3730 }
3731
3732
gee_tim_sort_slice_free(GeeTimSortSlice * self)3733 static void gee_tim_sort_slice_free (GeeTimSortSlice* self) {
3734 void** _tmp0_;
3735 _tmp0_ = self->new_list;
3736 if (_tmp0_ != NULL) {
3737 void** _tmp1_;
3738 _tmp1_ = self->new_list;
3739 g_free (_tmp1_);
3740 }
3741 g_slice_free (GeeTimSortSlice, self);
3742 }
3743
3744
gee_tim_sort_class_init(GeeTimSortClass * klass)3745 static void gee_tim_sort_class_init (GeeTimSortClass * klass) {
3746 gee_tim_sort_parent_class = g_type_class_peek_parent (klass);
3747 g_type_class_add_private (klass, sizeof (GeeTimSortPrivate));
3748 G_OBJECT_CLASS (klass)->get_property = _vala_gee_tim_sort_get_property;
3749 G_OBJECT_CLASS (klass)->set_property = _vala_gee_tim_sort_set_property;
3750 G_OBJECT_CLASS (klass)->finalize = gee_tim_sort_finalize;
3751 g_object_class_install_property (G_OBJECT_CLASS (klass), GEE_TIM_SORT_G_TYPE, g_param_spec_gtype ("g-type", "type", "type", G_TYPE_NONE, G_PARAM_STATIC_NAME | G_PARAM_STATIC_NICK | G_PARAM_STATIC_BLURB | G_PARAM_WRITABLE | G_PARAM_CONSTRUCT_ONLY));
3752 g_object_class_install_property (G_OBJECT_CLASS (klass), GEE_TIM_SORT_G_DUP_FUNC, g_param_spec_pointer ("g-dup-func", "dup func", "dup func", G_PARAM_STATIC_NAME | G_PARAM_STATIC_NICK | G_PARAM_STATIC_BLURB | G_PARAM_WRITABLE | G_PARAM_CONSTRUCT_ONLY));
3753 g_object_class_install_property (G_OBJECT_CLASS (klass), GEE_TIM_SORT_G_DESTROY_FUNC, g_param_spec_pointer ("g-destroy-func", "destroy func", "destroy func", G_PARAM_STATIC_NAME | G_PARAM_STATIC_NICK | G_PARAM_STATIC_BLURB | G_PARAM_WRITABLE | G_PARAM_CONSTRUCT_ONLY));
3754 }
3755
3756
gee_tim_sort_instance_init(GeeTimSort * self)3757 static void gee_tim_sort_instance_init (GeeTimSort * self) {
3758 self->priv = GEE_TIM_SORT_GET_PRIVATE (self);
3759 }
3760
3761
gee_tim_sort_finalize(GObject * obj)3762 static void gee_tim_sort_finalize (GObject* obj) {
3763 GeeTimSort * self;
3764 self = G_TYPE_CHECK_INSTANCE_CAST (obj, GEE_TYPE_TIM_SORT, GeeTimSort);
3765 _g_object_unref0 (self->priv->list_collection);
3766 self->priv->array = (_vala_array_free (self->priv->array, self->priv->array_length1, (GDestroyNotify) self->priv->g_destroy_func), NULL);
3767 self->priv->pending = (_vala_array_free (self->priv->pending, self->priv->pending_length1, (GDestroyNotify) gee_tim_sort_slice_free), NULL);
3768 (self->priv->compare_data_target_destroy_notify == NULL) ? NULL : (self->priv->compare_data_target_destroy_notify (self->priv->compare_data_target), NULL);
3769 self->priv->compare_data = NULL;
3770 self->priv->compare_data_target = NULL;
3771 self->priv->compare_data_target_destroy_notify = NULL;
3772 G_OBJECT_CLASS (gee_tim_sort_parent_class)->finalize (obj);
3773 }
3774
3775
3776 /**
3777 * A stable, adaptive, iterative mergesort that requires far fewer than n*lg(n)
3778 * comparisons when running on partially sorted arrays, while offering
3779 * performance comparable to a traditional mergesort when run on random arrays.
3780 * Like all proper mergesorts, this sort is stable and runs O(n*log(n)) time
3781 * (worst case). In the worst case, this sort requires temporary storage space
3782 * for n/2 object references; in the best case, it requires only a small
3783 * constant amount of space.
3784 *
3785 * This implementation was adapted from Tim Peters's list sort for Python,
3786 * which is described in detail here:
3787 * [[http://svn.python.org/projects/python/trunk/Objects/listsort.txt]]
3788 *
3789 * Tim's C code may be found here:
3790 * [[http://svn.python.org/projects/python/trunk/Objects/listobject.c]]
3791 *
3792 * The underlying techniques are described in this paper (and may have even
3793 * earlier origins):
3794 *
3795 * "Optimistic Sorting and Information Theoretic Complexity"
3796 * Peter McIlroy
3797 * SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms), pp
3798 * 467-474, Austin, Texas, 25-27 January 1993.
3799 */
gee_tim_sort_get_type(void)3800 GType gee_tim_sort_get_type (void) {
3801 static volatile gsize gee_tim_sort_type_id__volatile = 0;
3802 if (g_once_init_enter (&gee_tim_sort_type_id__volatile)) {
3803 static const GTypeInfo g_define_type_info = { sizeof (GeeTimSortClass), (GBaseInitFunc) NULL, (GBaseFinalizeFunc) NULL, (GClassInitFunc) gee_tim_sort_class_init, (GClassFinalizeFunc) NULL, NULL, sizeof (GeeTimSort), 0, (GInstanceInitFunc) gee_tim_sort_instance_init, NULL };
3804 GType gee_tim_sort_type_id;
3805 gee_tim_sort_type_id = g_type_register_static (G_TYPE_OBJECT, "GeeTimSort", &g_define_type_info, 0);
3806 g_once_init_leave (&gee_tim_sort_type_id__volatile, gee_tim_sort_type_id);
3807 }
3808 return gee_tim_sort_type_id__volatile;
3809 }
3810
3811
_vala_gee_tim_sort_get_property(GObject * object,guint property_id,GValue * value,GParamSpec * pspec)3812 static void _vala_gee_tim_sort_get_property (GObject * object, guint property_id, GValue * value, GParamSpec * pspec) {
3813 GeeTimSort * self;
3814 self = G_TYPE_CHECK_INSTANCE_CAST (object, GEE_TYPE_TIM_SORT, GeeTimSort);
3815 switch (property_id) {
3816 default:
3817 G_OBJECT_WARN_INVALID_PROPERTY_ID (object, property_id, pspec);
3818 break;
3819 }
3820 }
3821
3822
_vala_gee_tim_sort_set_property(GObject * object,guint property_id,const GValue * value,GParamSpec * pspec)3823 static void _vala_gee_tim_sort_set_property (GObject * object, guint property_id, const GValue * value, GParamSpec * pspec) {
3824 GeeTimSort * self;
3825 self = G_TYPE_CHECK_INSTANCE_CAST (object, GEE_TYPE_TIM_SORT, GeeTimSort);
3826 switch (property_id) {
3827 case GEE_TIM_SORT_G_TYPE:
3828 self->priv->g_type = g_value_get_gtype (value);
3829 break;
3830 case GEE_TIM_SORT_G_DUP_FUNC:
3831 self->priv->g_dup_func = g_value_get_pointer (value);
3832 break;
3833 case GEE_TIM_SORT_G_DESTROY_FUNC:
3834 self->priv->g_destroy_func = g_value_get_pointer (value);
3835 break;
3836 default:
3837 G_OBJECT_WARN_INVALID_PROPERTY_ID (object, property_id, pspec);
3838 break;
3839 }
3840 }
3841
3842
_vala_array_destroy(gpointer array,gint array_length,GDestroyNotify destroy_func)3843 static void _vala_array_destroy (gpointer array, gint array_length, GDestroyNotify destroy_func) {
3844 if ((array != NULL) && (destroy_func != NULL)) {
3845 int i;
3846 for (i = 0; i < array_length; i = i + 1) {
3847 if (((gpointer*) array)[i] != NULL) {
3848 destroy_func (((gpointer*) array)[i]);
3849 }
3850 }
3851 }
3852 }
3853
3854
_vala_array_free(gpointer array,gint array_length,GDestroyNotify destroy_func)3855 static void _vala_array_free (gpointer array, gint array_length, GDestroyNotify destroy_func) {
3856 _vala_array_destroy (array, array_length, destroy_func);
3857 g_free (array);
3858 }
3859
3860
_vala_array_move(gpointer array,gsize element_size,gint src,gint dest,gint length)3861 static void _vala_array_move (gpointer array, gsize element_size, gint src, gint dest, gint length) {
3862 g_memmove (((char*) array) + (dest * element_size), ((char*) array) + (src * element_size), length * element_size);
3863 if ((src < dest) && ((src + length) > dest)) {
3864 memset (((char*) array) + (src * element_size), 0, (dest - src) * element_size);
3865 } else if ((src > dest) && (src < (dest + length))) {
3866 memset (((char*) array) + ((dest + length) * element_size), 0, (src - dest) * element_size);
3867 } else if (src != dest) {
3868 memset (((char*) array) + (src * element_size), 0, length * element_size);
3869 }
3870 }
3871
3872
3873
3874