Branch data Line data Source code
1 : : /* GLIB - Library of useful routines for C programming
2 : : * Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007
3 : : * Soeren Sandmann (sandmann@daimi.au.dk)
4 : : *
5 : : * SPDX-License-Identifier: LGPL-2.1-or-later
6 : : *
7 : : * This library is free software; you can redistribute it and/or
8 : : * modify it under the terms of the GNU Lesser General Public
9 : : * License as published by the Free Software Foundation; either
10 : : * version 2.1 of the License, or (at your option) any later version.
11 : : *
12 : : * This library is distributed in the hope that it will be useful,
13 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 : : * Lesser General Public License for more details.
16 : : *
17 : : * You should have received a copy of the GNU Lesser General Public
18 : : * License along with this library; if not, see <http://www.gnu.org/licenses/>.
19 : : */
20 : :
21 : : #include "config.h"
22 : :
23 : : #include "gsequence.h"
24 : :
25 : : #include "gmem.h"
26 : : #include "gtestutils.h"
27 : : #include "gslice.h"
28 : :
29 : : /**
30 : : * GSequenceIter:
31 : : *
32 : : * The #GSequenceIter struct is an opaque data type representing an
33 : : * iterator pointing into a #GSequence.
34 : : */
35 : :
36 : : /**
37 : : * GSequenceIterCompareFunc:
38 : : * @a: a #GSequenceIter
39 : : * @b: a #GSequenceIter
40 : : * @data: user data
41 : : *
42 : : * A #GSequenceIterCompareFunc is a function used to compare iterators.
43 : : * It must return zero if the iterators compare equal, a negative value
44 : : * if @a comes before @b, and a positive value if @b comes before @a.
45 : : *
46 : : * Returns: zero if the iterators are equal, a negative value if @a
47 : : * comes before @b, and a positive value if @b comes before @a.
48 : : */
49 : :
50 : : typedef struct _GSequenceNode GSequenceNode;
51 : :
52 : : /**
53 : : * GSequence:
54 : : *
55 : : * The #GSequence struct is an opaque data type representing a
56 : : * [sequence](data-structures.html#scalable-lists) data type.
57 : : */
58 : : struct _GSequence
59 : : {
60 : : GSequenceNode * end_node;
61 : : GDestroyNotify data_destroy_notify;
62 : : gboolean access_prohibited;
63 : :
64 : : /* The 'real_sequence' is used when temporary sequences are created
65 : : * to hold nodes that are being rearranged. The 'real_sequence' of such
66 : : * a temporary sequence points to the sequence that is actually being
67 : : * manipulated. The only reason we need this is so that when the
68 : : * sort/sort_changed/search_iter() functions call out to the application
69 : : * g_sequence_iter_get_sequence() will return the correct sequence.
70 : : */
71 : : GSequence * real_sequence;
72 : : };
73 : :
74 : : struct _GSequenceNode
75 : : {
76 : : gint n_nodes;
77 : : guint32 priority;
78 : : GSequenceNode * parent;
79 : : GSequenceNode * left;
80 : : GSequenceNode * right;
81 : : gpointer data; /* For the end node, this field points
82 : : * to the sequence
83 : : */
84 : : };
85 : :
86 : : /*
87 : : * Declaration of GSequenceNode methods
88 : : */
89 : : static GSequenceNode *node_new (gpointer data);
90 : : static GSequenceNode *node_get_first (GSequenceNode *node);
91 : : static GSequenceNode *node_get_last (GSequenceNode *node);
92 : : static GSequenceNode *node_get_prev (GSequenceNode *node);
93 : : static GSequenceNode *node_get_next (GSequenceNode *node);
94 : : static gint node_get_pos (GSequenceNode *node);
95 : : static GSequenceNode *node_get_by_pos (GSequenceNode *node,
96 : : gint pos);
97 : : static GSequenceNode *node_find (GSequenceNode *haystack,
98 : : GSequenceNode *needle,
99 : : GSequenceNode *end,
100 : : GSequenceIterCompareFunc cmp,
101 : : gpointer user_data);
102 : : static GSequenceNode *node_find_closest (GSequenceNode *haystack,
103 : : GSequenceNode *needle,
104 : : GSequenceNode *end,
105 : : GSequenceIterCompareFunc cmp,
106 : : gpointer user_data);
107 : : static gint node_get_length (GSequenceNode *node);
108 : : static void node_free (GSequenceNode *node,
109 : : GSequence *seq);
110 : : static void node_cut (GSequenceNode *split);
111 : : static void node_insert_before (GSequenceNode *node,
112 : : GSequenceNode *new);
113 : : static void node_unlink (GSequenceNode *node);
114 : : static void node_join (GSequenceNode *left,
115 : : GSequenceNode *right);
116 : : static void node_insert_sorted (GSequenceNode *node,
117 : : GSequenceNode *new,
118 : : GSequenceNode *end,
119 : : GSequenceIterCompareFunc cmp_func,
120 : : gpointer cmp_data);
121 : :
122 : :
123 : : /*
124 : : * Various helper functions
125 : : */
126 : : static void
127 : 9130009 : check_seq_access (GSequence *seq)
128 : : {
129 : 9130009 : if (G_UNLIKELY (seq->access_prohibited))
130 : : {
131 : 0 : g_warning ("Accessing a sequence while it is "
132 : : "being sorted or searched is not allowed");
133 : : }
134 : 9130009 : }
135 : :
136 : : static GSequence *
137 : 19710229 : get_sequence (GSequenceNode *node)
138 : : {
139 : 19710229 : return (GSequence *)node_get_last (node)->data;
140 : : }
141 : :
142 : : static gboolean
143 : 2080912 : seq_is_end (GSequence *seq,
144 : : GSequenceIter *iter)
145 : : {
146 : 2080912 : return seq->end_node == iter;
147 : : }
148 : :
149 : : static gboolean
150 : 247414964 : is_end (GSequenceIter *iter)
151 : : {
152 : 247414964 : GSequenceIter *parent = iter->parent;
153 : :
154 : 247414964 : if (iter->right)
155 : 126197257 : return FALSE;
156 : :
157 : 121217707 : if (!parent)
158 : 336109 : return TRUE;
159 : :
160 : 220908055 : while (parent->right == iter)
161 : : {
162 : 100381030 : iter = parent;
163 : 100381030 : parent = iter->parent;
164 : :
165 : 100381030 : if (!parent)
166 : 354573 : return TRUE;
167 : : }
168 : :
169 : 120527025 : return FALSE;
170 : : }
171 : :
172 : : typedef struct
173 : : {
174 : : GCompareDataFunc cmp_func;
175 : : gpointer cmp_data;
176 : : GSequenceNode *end_node;
177 : : } SortInfo;
178 : :
179 : : /* This function compares two iters using a normal compare
180 : : * function and user_data passed in in a SortInfo struct
181 : : */
182 : : static gint
183 : 29456381 : iter_compare (GSequenceIter *node1,
184 : : GSequenceIter *node2,
185 : : gpointer data)
186 : : {
187 : 29456381 : const SortInfo *info = data;
188 : : gint retval;
189 : :
190 : 29456381 : if (node1 == info->end_node)
191 : 0 : return 1;
192 : :
193 : 29456381 : if (node2 == info->end_node)
194 : 0 : return -1;
195 : :
196 : 29456381 : retval = info->cmp_func (node1->data, node2->data, info->cmp_data);
197 : :
198 : 29456381 : return retval;
199 : : }
200 : :
201 : : /*
202 : : * Public API
203 : : */
204 : :
205 : : /**
206 : : * g_sequence_new:
207 : : * @data_destroy: (nullable): a #GDestroyNotify function, or %NULL
208 : : *
209 : : * Creates a new GSequence. The @data_destroy function, if non-%NULL will
210 : : * be called on all items when the sequence is destroyed and on items that
211 : : * are removed from the sequence.
212 : : *
213 : : * Returns: (transfer full): a new #GSequence
214 : : *
215 : : * Since: 2.14
216 : : **/
217 : : GSequence *
218 : 2142551 : g_sequence_new (GDestroyNotify data_destroy)
219 : : {
220 : 2142551 : GSequence *seq = g_new (GSequence, 1);
221 : 2142551 : seq->data_destroy_notify = data_destroy;
222 : :
223 : 2142551 : seq->end_node = node_new (seq);
224 : :
225 : 2142551 : seq->access_prohibited = FALSE;
226 : :
227 : 2142551 : seq->real_sequence = seq;
228 : :
229 : 2142551 : return seq;
230 : : }
231 : :
232 : : /**
233 : : * g_sequence_free:
234 : : * @seq: a #GSequence
235 : : *
236 : : * Frees the memory allocated for @seq. If @seq has a data destroy
237 : : * function associated with it, that function is called on all items
238 : : * in @seq.
239 : : *
240 : : * Since: 2.14
241 : : */
242 : : void
243 : 2142321 : g_sequence_free (GSequence *seq)
244 : : {
245 : 2142321 : g_return_if_fail (seq != NULL);
246 : :
247 : 2142321 : check_seq_access (seq);
248 : :
249 : 2142321 : node_free (seq->end_node, seq);
250 : :
251 : 2142321 : g_free (seq);
252 : : }
253 : :
254 : : /**
255 : : * g_sequence_foreach_range:
256 : : * @begin: a #GSequenceIter
257 : : * @end: a #GSequenceIter
258 : : * @func: (scope call): a #GFunc
259 : : * @user_data: user data passed to @func
260 : : *
261 : : * Calls @func for each item in the range (@begin, @end) passing
262 : : * @user_data to the function. @func must not modify the sequence
263 : : * itself.
264 : : *
265 : : * Since: 2.14
266 : : */
267 : : void
268 : 35791 : g_sequence_foreach_range (GSequenceIter *begin,
269 : : GSequenceIter *end,
270 : : GFunc func,
271 : : gpointer user_data)
272 : : {
273 : : GSequence *seq;
274 : : GSequenceIter *iter;
275 : :
276 : 35791 : g_return_if_fail (func != NULL);
277 : 35791 : g_return_if_fail (begin != NULL);
278 : 35791 : g_return_if_fail (end != NULL);
279 : :
280 : 35791 : seq = get_sequence (begin);
281 : :
282 : 35791 : seq->access_prohibited = TRUE;
283 : :
284 : 35791 : iter = begin;
285 : 793917 : while (iter != end)
286 : : {
287 : 758126 : GSequenceIter *next = node_get_next (iter);
288 : :
289 : 758126 : func (iter->data, user_data);
290 : :
291 : 758126 : iter = next;
292 : : }
293 : :
294 : 35791 : seq->access_prohibited = FALSE;
295 : : }
296 : :
297 : : /**
298 : : * g_sequence_foreach:
299 : : * @seq: a #GSequence
300 : : * @func: (scope call): the function to call for each item in @seq
301 : : * @user_data: user data passed to @func
302 : : *
303 : : * Calls @func for each item in the sequence passing @user_data
304 : : * to the function. @func must not modify the sequence itself.
305 : : *
306 : : * Since: 2.14
307 : : */
308 : : void
309 : 17977 : g_sequence_foreach (GSequence *seq,
310 : : GFunc func,
311 : : gpointer user_data)
312 : : {
313 : : GSequenceIter *begin, *end;
314 : :
315 : 17977 : check_seq_access (seq);
316 : :
317 : 17977 : begin = g_sequence_get_begin_iter (seq);
318 : 17977 : end = g_sequence_get_end_iter (seq);
319 : :
320 : 17977 : g_sequence_foreach_range (begin, end, func, user_data);
321 : 17977 : }
322 : :
323 : : /**
324 : : * g_sequence_range_get_midpoint:
325 : : * @begin: a #GSequenceIter
326 : : * @end: a #GSequenceIter
327 : : *
328 : : * Finds an iterator somewhere in the range (@begin, @end). This
329 : : * iterator will be close to the middle of the range, but is not
330 : : * guaranteed to be exactly in the middle.
331 : : *
332 : : * The @begin and @end iterators must both point to the same sequence
333 : : * and @begin must come before or be equal to @end in the sequence.
334 : : *
335 : : * Returns: (transfer none): a #GSequenceIter pointing somewhere in the
336 : : * (@begin, @end) range
337 : : *
338 : : * Since: 2.14
339 : : */
340 : : GSequenceIter *
341 : 17943 : g_sequence_range_get_midpoint (GSequenceIter *begin,
342 : : GSequenceIter *end)
343 : : {
344 : : int begin_pos, end_pos, mid_pos;
345 : :
346 : 17943 : g_return_val_if_fail (begin != NULL, NULL);
347 : 17943 : g_return_val_if_fail (end != NULL, NULL);
348 : 17943 : g_return_val_if_fail (get_sequence (begin) == get_sequence (end), NULL);
349 : :
350 : 17943 : begin_pos = node_get_pos (begin);
351 : 17943 : end_pos = node_get_pos (end);
352 : :
353 : 17943 : g_return_val_if_fail (end_pos >= begin_pos, NULL);
354 : :
355 : 17943 : mid_pos = begin_pos + (end_pos - begin_pos) / 2;
356 : :
357 : 17943 : return node_get_by_pos (begin, mid_pos);
358 : : }
359 : :
360 : : /**
361 : : * g_sequence_iter_compare:
362 : : * @a: a #GSequenceIter
363 : : * @b: a #GSequenceIter
364 : : *
365 : : * Returns a negative number if @a comes before @b, 0 if they are equal,
366 : : * and a positive number if @a comes after @b.
367 : : *
368 : : * The @a and @b iterators must point into the same sequence.
369 : : *
370 : : * Returns: a negative number if @a comes before @b, 0 if they are
371 : : * equal, and a positive number if @a comes after @b
372 : : *
373 : : * Since: 2.14
374 : : */
375 : : gint
376 : 327504 : g_sequence_iter_compare (GSequenceIter *a,
377 : : GSequenceIter *b)
378 : : {
379 : : gint a_pos, b_pos;
380 : : GSequence *seq_a, *seq_b;
381 : :
382 : 327504 : g_return_val_if_fail (a != NULL, 0);
383 : 327504 : g_return_val_if_fail (b != NULL, 0);
384 : :
385 : 327504 : seq_a = get_sequence (a);
386 : 327504 : seq_b = get_sequence (b);
387 : 327504 : g_return_val_if_fail (seq_a == seq_b, 0);
388 : :
389 : 327504 : check_seq_access (seq_a);
390 : 327504 : check_seq_access (seq_b);
391 : :
392 : 327504 : a_pos = node_get_pos (a);
393 : 327504 : b_pos = node_get_pos (b);
394 : :
395 : 327504 : if (a_pos == b_pos)
396 : 50171 : return 0;
397 : 277333 : else if (a_pos > b_pos)
398 : 13974 : return 1;
399 : : else
400 : 263359 : return -1;
401 : : }
402 : :
403 : : /**
404 : : * g_sequence_append:
405 : : * @seq: a #GSequence
406 : : * @data: the data for the new item
407 : : *
408 : : * Adds a new item to the end of @seq.
409 : : *
410 : : * Returns: (transfer none): an iterator pointing to the new item
411 : : *
412 : : * Since: 2.14
413 : : */
414 : : GSequenceIter *
415 : 1435148 : g_sequence_append (GSequence *seq,
416 : : gpointer data)
417 : : {
418 : : GSequenceNode *node;
419 : :
420 : 1435148 : g_return_val_if_fail (seq != NULL, NULL);
421 : :
422 : 1435148 : check_seq_access (seq);
423 : :
424 : 1435148 : node = node_new (data);
425 : 1435148 : node_insert_before (seq->end_node, node);
426 : :
427 : 1435148 : return node;
428 : : }
429 : :
430 : : /**
431 : : * g_sequence_prepend:
432 : : * @seq: a #GSequence
433 : : * @data: the data for the new item
434 : : *
435 : : * Adds a new item to the front of @seq
436 : : *
437 : : * Returns: (transfer none): an iterator pointing to the new item
438 : : *
439 : : * Since: 2.14
440 : : */
441 : : GSequenceIter *
442 : 232973 : g_sequence_prepend (GSequence *seq,
443 : : gpointer data)
444 : : {
445 : : GSequenceNode *node, *first;
446 : :
447 : 232973 : g_return_val_if_fail (seq != NULL, NULL);
448 : :
449 : 232973 : check_seq_access (seq);
450 : :
451 : 232973 : node = node_new (data);
452 : 232973 : first = node_get_first (seq->end_node);
453 : :
454 : 232973 : node_insert_before (first, node);
455 : :
456 : 232973 : return node;
457 : : }
458 : :
459 : : /**
460 : : * g_sequence_insert_before:
461 : : * @iter: a #GSequenceIter
462 : : * @data: the data for the new item
463 : : *
464 : : * Inserts a new item just before the item pointed to by @iter.
465 : : *
466 : : * Returns: (transfer none): an iterator pointing to the new item
467 : : *
468 : : * Since: 2.14
469 : : */
470 : : GSequenceIter *
471 : 948615 : g_sequence_insert_before (GSequenceIter *iter,
472 : : gpointer data)
473 : : {
474 : : GSequence *seq;
475 : : GSequenceNode *node;
476 : :
477 : 948615 : g_return_val_if_fail (iter != NULL, NULL);
478 : :
479 : 948615 : seq = get_sequence (iter);
480 : 948615 : check_seq_access (seq);
481 : :
482 : 948615 : node = node_new (data);
483 : :
484 : 948615 : node_insert_before (iter, node);
485 : :
486 : 948615 : return node;
487 : : }
488 : :
489 : : /**
490 : : * g_sequence_remove:
491 : : * @iter: a #GSequenceIter
492 : : *
493 : : * Removes the item pointed to by @iter. It is an error to pass the
494 : : * end iterator to this function.
495 : : *
496 : : * If the sequence has a data destroy function associated with it, this
497 : : * function is called on the data for the removed item.
498 : : *
499 : : * Since: 2.14
500 : : */
501 : : void
502 : 226349 : g_sequence_remove (GSequenceIter *iter)
503 : : {
504 : : GSequence *seq;
505 : :
506 : 226349 : g_return_if_fail (iter != NULL);
507 : :
508 : 226349 : seq = get_sequence (iter);
509 : 226349 : g_return_if_fail (!seq_is_end (seq, iter));
510 : :
511 : 226349 : check_seq_access (seq);
512 : :
513 : 226349 : node_unlink (iter);
514 : 226349 : node_free (iter, seq);
515 : : }
516 : :
517 : : /**
518 : : * g_sequence_remove_range:
519 : : * @begin: a #GSequenceIter
520 : : * @end: a #GSequenceIter
521 : : *
522 : : * Removes all items in the (@begin, @end) range.
523 : : *
524 : : * If the sequence has a data destroy function associated with it, this
525 : : * function is called on the data for the removed items.
526 : : *
527 : : * Since: 2.14
528 : : */
529 : : void
530 : 94140 : g_sequence_remove_range (GSequenceIter *begin,
531 : : GSequenceIter *end)
532 : : {
533 : : GSequence *seq_begin, *seq_end;
534 : :
535 : 94140 : seq_begin = get_sequence (begin);
536 : 94140 : seq_end = get_sequence (end);
537 : 94140 : g_return_if_fail (seq_begin == seq_end);
538 : : /* check_seq_access() calls are done by g_sequence_move_range() */
539 : :
540 : 94140 : g_sequence_move_range (NULL, begin, end);
541 : : }
542 : :
543 : : /**
544 : : * g_sequence_move_range:
545 : : * @dest: a #GSequenceIter
546 : : * @begin: a #GSequenceIter
547 : : * @end: a #GSequenceIter
548 : : *
549 : : * Inserts the (@begin, @end) range at the destination pointed to by @dest.
550 : : * The @begin and @end iters must point into the same sequence. It is
551 : : * allowed for @dest to point to a different sequence than the one pointed
552 : : * into by @begin and @end.
553 : : *
554 : : * If @dest is %NULL, the range indicated by @begin and @end is
555 : : * removed from the sequence. If @dest points to a place within
556 : : * the (@begin, @end) range, the range does not move.
557 : : *
558 : : * Since: 2.14
559 : : */
560 : : void
561 : 290283 : g_sequence_move_range (GSequenceIter *dest,
562 : : GSequenceIter *begin,
563 : : GSequenceIter *end)
564 : : {
565 : 290283 : GSequence *src_seq, *end_seq, *dest_seq = NULL;
566 : : GSequenceNode *first;
567 : :
568 : 290283 : g_return_if_fail (begin != NULL);
569 : 290283 : g_return_if_fail (end != NULL);
570 : :
571 : 290283 : src_seq = get_sequence (begin);
572 : 290283 : check_seq_access (src_seq);
573 : :
574 : 290283 : end_seq = get_sequence (end);
575 : 290283 : check_seq_access (end_seq);
576 : :
577 : 290283 : if (dest)
578 : : {
579 : 196143 : dest_seq = get_sequence (dest);
580 : 196143 : check_seq_access (dest_seq);
581 : : }
582 : :
583 : 290283 : g_return_if_fail (src_seq == end_seq);
584 : :
585 : : /* Dest points to begin or end? */
586 : 290283 : if (dest == begin || dest == end)
587 : 594 : return;
588 : :
589 : : /* begin comes after end? */
590 : 289689 : if (g_sequence_iter_compare (begin, end) >= 0)
591 : 39725 : return;
592 : :
593 : : /* dest points somewhere in the (begin, end) range? */
594 : 251235 : if (dest && dest_seq == src_seq &&
595 : 2016 : g_sequence_iter_compare (dest, begin) > 0 &&
596 : 745 : g_sequence_iter_compare (dest, end) < 0)
597 : : {
598 : 257 : return;
599 : : }
600 : :
601 : 249707 : first = node_get_first (begin);
602 : :
603 : 249707 : node_cut (begin);
604 : :
605 : 249707 : node_cut (end);
606 : :
607 : 249707 : if (first != begin)
608 : 74301 : node_join (first, end);
609 : :
610 : 249707 : if (dest)
611 : : {
612 : 161936 : first = node_get_first (dest);
613 : :
614 : 161936 : node_cut (dest);
615 : :
616 : 161936 : node_join (begin, dest);
617 : :
618 : 161936 : if (dest != first)
619 : 9496 : node_join (first, begin);
620 : : }
621 : : else
622 : : {
623 : 87771 : node_free (begin, src_seq);
624 : : }
625 : : }
626 : :
627 : : /**
628 : : * g_sequence_sort:
629 : : * @seq: a #GSequence
630 : : * @cmp_func: (scope call): the function used to sort the sequence
631 : : * @cmp_data: user data passed to @cmp_func
632 : : *
633 : : * Sorts @seq using @cmp_func.
634 : : *
635 : : * @cmp_func is passed two items of @seq and should
636 : : * return 0 if they are equal, a negative value if the
637 : : * first comes before the second, and a positive value
638 : : * if the second comes before the first.
639 : : *
640 : : * Since: 2.14
641 : : */
642 : : void
643 : 160350 : g_sequence_sort (GSequence *seq,
644 : : GCompareDataFunc cmp_func,
645 : : gpointer cmp_data)
646 : : {
647 : : SortInfo info;
648 : :
649 : 160350 : info.cmp_func = cmp_func;
650 : 160350 : info.cmp_data = cmp_data;
651 : 160350 : info.end_node = seq->end_node;
652 : :
653 : 160350 : check_seq_access (seq);
654 : :
655 : 160350 : g_sequence_sort_iter (seq, iter_compare, &info);
656 : 160350 : }
657 : :
658 : : /**
659 : : * g_sequence_insert_sorted:
660 : : * @seq: a #GSequence
661 : : * @data: the data to insert
662 : : * @cmp_func: (scope call): the function used to compare items in the sequence
663 : : * @cmp_data: user data passed to @cmp_func.
664 : : *
665 : : * Inserts @data into @seq using @cmp_func to determine the new
666 : : * position. The sequence must already be sorted according to @cmp_func;
667 : : * otherwise the new position of @data is undefined.
668 : : *
669 : : * @cmp_func is called with two items of the @seq, and @cmp_data.
670 : : * It should return 0 if the items are equal, a negative value
671 : : * if the first item comes before the second, and a positive value
672 : : * if the second item comes before the first.
673 : : *
674 : : * Note that when adding a large amount of data to a #GSequence,
675 : : * it is more efficient to do unsorted insertions and then call
676 : : * g_sequence_sort() or g_sequence_sort_iter().
677 : : *
678 : : * Returns: (transfer none): a #GSequenceIter pointing to the new item.
679 : : *
680 : : * Since: 2.14
681 : : */
682 : : GSequenceIter *
683 : 601647 : g_sequence_insert_sorted (GSequence *seq,
684 : : gpointer data,
685 : : GCompareDataFunc cmp_func,
686 : : gpointer cmp_data)
687 : : {
688 : : SortInfo info;
689 : :
690 : 601647 : g_return_val_if_fail (seq != NULL, NULL);
691 : 601647 : g_return_val_if_fail (cmp_func != NULL, NULL);
692 : :
693 : 601647 : info.cmp_func = cmp_func;
694 : 601647 : info.cmp_data = cmp_data;
695 : 601647 : info.end_node = seq->end_node;
696 : 601647 : check_seq_access (seq);
697 : :
698 : 601647 : return g_sequence_insert_sorted_iter (seq, data, iter_compare, &info);
699 : : }
700 : :
701 : : /**
702 : : * g_sequence_sort_changed:
703 : : * @iter: A #GSequenceIter
704 : : * @cmp_func: (scope call): the function used to compare items in the sequence
705 : : * @cmp_data: user data passed to @cmp_func.
706 : : *
707 : : * Moves the data pointed to by @iter to a new position as indicated by
708 : : * @cmp_func. This
709 : : * function should be called for items in a sequence already sorted according
710 : : * to @cmp_func whenever some aspect of an item changes so that @cmp_func
711 : : * may return different values for that item.
712 : : *
713 : : * @cmp_func is called with two items of the @seq, and @cmp_data.
714 : : * It should return 0 if the items are equal, a negative value if
715 : : * the first item comes before the second, and a positive value if
716 : : * the second item comes before the first.
717 : : *
718 : : * Since: 2.14
719 : : */
720 : : void
721 : 257381 : g_sequence_sort_changed (GSequenceIter *iter,
722 : : GCompareDataFunc cmp_func,
723 : : gpointer cmp_data)
724 : : {
725 : : GSequence *seq;
726 : : SortInfo info;
727 : :
728 : 257381 : g_return_if_fail (iter != NULL);
729 : :
730 : 257381 : seq = get_sequence (iter);
731 : : /* check_seq_access() call is done by g_sequence_sort_changed_iter() */
732 : 257381 : g_return_if_fail (!seq_is_end (seq, iter));
733 : :
734 : 257381 : info.cmp_func = cmp_func;
735 : 257381 : info.cmp_data = cmp_data;
736 : 257381 : info.end_node = seq->end_node;
737 : :
738 : 257381 : g_sequence_sort_changed_iter (iter, iter_compare, &info);
739 : : }
740 : :
741 : : /**
742 : : * g_sequence_search:
743 : : * @seq: a #GSequence
744 : : * @data: data for the new item
745 : : * @cmp_func: (scope call): the function used to compare items in the sequence
746 : : * @cmp_data: user data passed to @cmp_func
747 : : *
748 : : * Returns an iterator pointing to the position where @data would
749 : : * be inserted according to @cmp_func and @cmp_data.
750 : : *
751 : : * @cmp_func is called with two items of the @seq, and @cmp_data.
752 : : * It should return 0 if the items are equal, a negative value if
753 : : * the first item comes before the second, and a positive value if
754 : : * the second item comes before the first.
755 : : *
756 : : * If you are simply searching for an existing element of the sequence,
757 : : * consider using g_sequence_lookup().
758 : : *
759 : : * This function will fail if the data contained in the sequence is
760 : : * unsorted.
761 : : *
762 : : * Returns: (transfer none): an #GSequenceIter pointing to the position where @data
763 : : * would have been inserted according to @cmp_func and @cmp_data
764 : : *
765 : : * Since: 2.14
766 : : */
767 : : GSequenceIter *
768 : 17980 : g_sequence_search (GSequence *seq,
769 : : gpointer data,
770 : : GCompareDataFunc cmp_func,
771 : : gpointer cmp_data)
772 : : {
773 : : SortInfo info;
774 : :
775 : 17980 : g_return_val_if_fail (seq != NULL, NULL);
776 : :
777 : 17980 : info.cmp_func = cmp_func;
778 : 17980 : info.cmp_data = cmp_data;
779 : 17980 : info.end_node = seq->end_node;
780 : 17980 : check_seq_access (seq);
781 : :
782 : 17980 : return g_sequence_search_iter (seq, data, iter_compare, &info);
783 : : }
784 : :
785 : : /**
786 : : * g_sequence_lookup:
787 : : * @seq: a #GSequence
788 : : * @data: data to look up
789 : : * @cmp_func: (scope call): the function used to compare items in the sequence
790 : : * @cmp_data: user data passed to @cmp_func
791 : : *
792 : : * Returns an iterator pointing to the position of the first item found
793 : : * equal to @data according to @cmp_func and @cmp_data. If more than one
794 : : * item is equal, it is not guaranteed that it is the first which is
795 : : * returned. In that case, you can use g_sequence_iter_next() and
796 : : * g_sequence_iter_prev() to get others.
797 : : *
798 : : * @cmp_func is called with two items of the @seq, and @cmp_data.
799 : : * It should return 0 if the items are equal, a negative value if
800 : : * the first item comes before the second, and a positive value if
801 : : * the second item comes before the first.
802 : : *
803 : : * This function will fail if the data contained in the sequence is
804 : : * unsorted.
805 : : *
806 : : * Returns: (transfer none) (nullable): an #GSequenceIter pointing to the position of the
807 : : * first item found equal to @data according to @cmp_func and
808 : : * @cmp_data, or %NULL if no such item exists
809 : : *
810 : : * Since: 2.28
811 : : */
812 : : GSequenceIter *
813 : 17790 : g_sequence_lookup (GSequence *seq,
814 : : gpointer data,
815 : : GCompareDataFunc cmp_func,
816 : : gpointer cmp_data)
817 : : {
818 : : SortInfo info;
819 : :
820 : 17790 : g_return_val_if_fail (seq != NULL, NULL);
821 : :
822 : 17790 : info.cmp_func = cmp_func;
823 : 17790 : info.cmp_data = cmp_data;
824 : 17790 : info.end_node = seq->end_node;
825 : 17790 : check_seq_access (seq);
826 : :
827 : 17790 : return g_sequence_lookup_iter (seq, data, iter_compare, &info);
828 : : }
829 : :
830 : : /**
831 : : * g_sequence_sort_iter:
832 : : * @seq: a #GSequence
833 : : * @cmp_func: (scope call): the function used to compare iterators in the sequence
834 : : * @cmp_data: user data passed to @cmp_func
835 : : *
836 : : * Like g_sequence_sort(), but uses a #GSequenceIterCompareFunc instead
837 : : * of a #GCompareDataFunc as the compare function
838 : : *
839 : : * @cmp_func is called with two iterators pointing into @seq. It should
840 : : * return 0 if the iterators are equal, a negative value if the first
841 : : * iterator comes before the second, and a positive value if the second
842 : : * iterator comes before the first.
843 : : *
844 : : * Since: 2.14
845 : : */
846 : : void
847 : 178341 : g_sequence_sort_iter (GSequence *seq,
848 : : GSequenceIterCompareFunc cmp_func,
849 : : gpointer cmp_data)
850 : : {
851 : : GSequence *tmp;
852 : : GSequenceNode *begin, *end;
853 : :
854 : 178341 : g_return_if_fail (seq != NULL);
855 : 178341 : g_return_if_fail (cmp_func != NULL);
856 : :
857 : 178341 : check_seq_access (seq);
858 : :
859 : 178341 : begin = g_sequence_get_begin_iter (seq);
860 : 178341 : end = g_sequence_get_end_iter (seq);
861 : :
862 : 178341 : tmp = g_sequence_new (NULL);
863 : 178341 : tmp->real_sequence = seq;
864 : :
865 : 178341 : g_sequence_move_range (g_sequence_get_begin_iter (tmp), begin, end);
866 : :
867 : 178341 : seq->access_prohibited = TRUE;
868 : 178341 : tmp->access_prohibited = TRUE;
869 : :
870 : 6125379 : while (!g_sequence_is_empty (tmp))
871 : : {
872 : 5947038 : GSequenceNode *node = g_sequence_get_begin_iter (tmp);
873 : :
874 : 5947038 : node_insert_sorted (seq->end_node, node, seq->end_node,
875 : : cmp_func, cmp_data);
876 : : }
877 : :
878 : 178341 : tmp->access_prohibited = FALSE;
879 : 178341 : seq->access_prohibited = FALSE;
880 : :
881 : 178341 : g_sequence_free (tmp);
882 : : }
883 : :
884 : : /**
885 : : * g_sequence_sort_changed_iter:
886 : : * @iter: a #GSequenceIter
887 : : * @iter_cmp: (scope call): the function used to compare iterators in the sequence
888 : : * @cmp_data: user data passed to @cmp_func
889 : : *
890 : : * Like g_sequence_sort_changed(), but uses
891 : : * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
892 : : * the compare function.
893 : : *
894 : : * @iter_cmp is called with two iterators pointing into the #GSequence that
895 : : * @iter points into. It should
896 : : * return 0 if the iterators are equal, a negative value if the first
897 : : * iterator comes before the second, and a positive value if the second
898 : : * iterator comes before the first.
899 : : *
900 : : * Since: 2.14
901 : : */
902 : : void
903 : 517910 : g_sequence_sort_changed_iter (GSequenceIter *iter,
904 : : GSequenceIterCompareFunc iter_cmp,
905 : : gpointer cmp_data)
906 : : {
907 : : GSequence *seq, *tmp_seq;
908 : : GSequenceIter *next, *prev;
909 : :
910 : 517910 : g_return_if_fail (iter != NULL);
911 : 517910 : g_return_if_fail (iter_cmp != NULL);
912 : :
913 : 517910 : seq = get_sequence (iter);
914 : 517910 : g_return_if_fail (!seq_is_end (seq, iter));
915 : :
916 : 517910 : check_seq_access (seq);
917 : :
918 : : /* If one of the neighbours is equal to iter, then
919 : : * don't move it. This ensures that sort_changed() is
920 : : * a stable operation.
921 : : */
922 : :
923 : 517910 : next = node_get_next (iter);
924 : 517910 : prev = node_get_prev (iter);
925 : :
926 : 517910 : if (prev != iter && iter_cmp (prev, iter, cmp_data) == 0)
927 : 999 : return;
928 : :
929 : 516911 : if (!is_end (next) && iter_cmp (next, iter, cmp_data) == 0)
930 : 1 : return;
931 : :
932 : 516910 : seq->access_prohibited = TRUE;
933 : :
934 : 516910 : tmp_seq = g_sequence_new (NULL);
935 : 516910 : tmp_seq->real_sequence = seq;
936 : :
937 : 516910 : node_unlink (iter);
938 : 516910 : node_insert_before (tmp_seq->end_node, iter);
939 : :
940 : 516910 : node_insert_sorted (seq->end_node, iter, seq->end_node,
941 : : iter_cmp, cmp_data);
942 : :
943 : 516910 : g_sequence_free (tmp_seq);
944 : :
945 : 516910 : seq->access_prohibited = FALSE;
946 : : }
947 : :
948 : : /**
949 : : * g_sequence_insert_sorted_iter:
950 : : * @seq: a #GSequence
951 : : * @data: data for the new item
952 : : * @iter_cmp: (scope call): the function used to compare iterators in the sequence
953 : : * @cmp_data: user data passed to @iter_cmp
954 : : *
955 : : * Like g_sequence_insert_sorted(), but uses
956 : : * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
957 : : * the compare function.
958 : : *
959 : : * @iter_cmp is called with two iterators pointing into @seq.
960 : : * It should return 0 if the iterators are equal, a negative
961 : : * value if the first iterator comes before the second, and a
962 : : * positive value if the second iterator comes before the first.
963 : : *
964 : : * Note that when adding a large amount of data to a #GSequence,
965 : : * it is more efficient to do unsorted insertions and then call
966 : : * g_sequence_sort() or g_sequence_sort_iter().
967 : : *
968 : : * Returns: (transfer none): a #GSequenceIter pointing to the new item
969 : : *
970 : : * Since: 2.14
971 : : */
972 : : GSequenceIter *
973 : 1129687 : g_sequence_insert_sorted_iter (GSequence *seq,
974 : : gpointer data,
975 : : GSequenceIterCompareFunc iter_cmp,
976 : : gpointer cmp_data)
977 : : {
978 : : GSequenceNode *new_node;
979 : : GSequence *tmp_seq;
980 : :
981 : 1129687 : g_return_val_if_fail (seq != NULL, NULL);
982 : 1129687 : g_return_val_if_fail (iter_cmp != NULL, NULL);
983 : :
984 : 1129687 : check_seq_access (seq);
985 : :
986 : 1129687 : seq->access_prohibited = TRUE;
987 : :
988 : : /* Create a new temporary sequence and put the new node into
989 : : * that. The reason for this is that the user compare function
990 : : * will be called with the new node, and if it dereferences,
991 : : * "is_end" will be called on it. But that will crash if the
992 : : * node is not actually in a sequence.
993 : : *
994 : : * node_insert_sorted() makes sure the node is unlinked before
995 : : * it is inserted.
996 : : *
997 : : * The reason we need the "iter" versions at all is that that
998 : : * is the only kind of compare functions GtkTreeView can use.
999 : : */
1000 : 1129687 : tmp_seq = g_sequence_new (NULL);
1001 : 1129687 : tmp_seq->real_sequence = seq;
1002 : :
1003 : 1129687 : new_node = g_sequence_append (tmp_seq, data);
1004 : :
1005 : 1129687 : node_insert_sorted (seq->end_node, new_node,
1006 : : seq->end_node, iter_cmp, cmp_data);
1007 : :
1008 : 1129687 : g_sequence_free (tmp_seq);
1009 : :
1010 : 1129687 : seq->access_prohibited = FALSE;
1011 : :
1012 : 1129687 : return new_node;
1013 : : }
1014 : :
1015 : : /**
1016 : : * g_sequence_search_iter:
1017 : : * @seq: a #GSequence
1018 : : * @data: data for the new item
1019 : : * @iter_cmp: (scope call): the function used to compare iterators in the sequence
1020 : : * @cmp_data: user data passed to @iter_cmp
1021 : : *
1022 : : * Like g_sequence_search(), but uses a #GSequenceIterCompareFunc
1023 : : * instead of a #GCompareDataFunc as the compare function.
1024 : : *
1025 : : * @iter_cmp is called with two iterators pointing into @seq.
1026 : : * It should return 0 if the iterators are equal, a negative value
1027 : : * if the first iterator comes before the second, and a positive
1028 : : * value if the second iterator comes before the first.
1029 : : *
1030 : : * If you are simply searching for an existing element of the sequence,
1031 : : * consider using g_sequence_lookup_iter().
1032 : : *
1033 : : * This function will fail if the data contained in the sequence is
1034 : : * unsorted.
1035 : : *
1036 : : * Returns: (transfer none): a #GSequenceIter pointing to the position in @seq
1037 : : * where @data would have been inserted according to @iter_cmp
1038 : : * and @cmp_data
1039 : : *
1040 : : * Since: 2.14
1041 : : */
1042 : : GSequenceIter *
1043 : 35714 : g_sequence_search_iter (GSequence *seq,
1044 : : gpointer data,
1045 : : GSequenceIterCompareFunc iter_cmp,
1046 : : gpointer cmp_data)
1047 : : {
1048 : : GSequenceNode *node;
1049 : : GSequenceNode *dummy;
1050 : : GSequence *tmp_seq;
1051 : :
1052 : 35714 : g_return_val_if_fail (seq != NULL, NULL);
1053 : :
1054 : 35714 : check_seq_access (seq);
1055 : :
1056 : 35714 : seq->access_prohibited = TRUE;
1057 : :
1058 : 35714 : tmp_seq = g_sequence_new (NULL);
1059 : 35714 : tmp_seq->real_sequence = seq;
1060 : :
1061 : 35714 : dummy = g_sequence_append (tmp_seq, data);
1062 : :
1063 : 35714 : node = node_find_closest (seq->end_node, dummy,
1064 : : seq->end_node, iter_cmp, cmp_data);
1065 : :
1066 : 35714 : g_sequence_free (tmp_seq);
1067 : :
1068 : 35714 : seq->access_prohibited = FALSE;
1069 : :
1070 : 35714 : return node;
1071 : : }
1072 : :
1073 : : /**
1074 : : * g_sequence_lookup_iter:
1075 : : * @seq: a #GSequence
1076 : : * @data: data to look up
1077 : : * @iter_cmp: (scope call): the function used to compare iterators in the sequence
1078 : : * @cmp_data: user data passed to @iter_cmp
1079 : : *
1080 : : * Like g_sequence_lookup(), but uses a #GSequenceIterCompareFunc
1081 : : * instead of a #GCompareDataFunc as the compare function.
1082 : : *
1083 : : * @iter_cmp is called with two iterators pointing into @seq.
1084 : : * It should return 0 if the iterators are equal, a negative value
1085 : : * if the first iterator comes before the second, and a positive
1086 : : * value if the second iterator comes before the first.
1087 : : *
1088 : : * This function will fail if the data contained in the sequence is
1089 : : * unsorted.
1090 : : *
1091 : : * Returns: (transfer none) (nullable): an #GSequenceIter pointing to the position of
1092 : : * the first item found equal to @data according to @iter_cmp
1093 : : * and @cmp_data, or %NULL if no such item exists
1094 : : *
1095 : : * Since: 2.28
1096 : : */
1097 : : GSequenceIter *
1098 : 35490 : g_sequence_lookup_iter (GSequence *seq,
1099 : : gpointer data,
1100 : : GSequenceIterCompareFunc iter_cmp,
1101 : : gpointer cmp_data)
1102 : : {
1103 : : GSequenceNode *node;
1104 : : GSequenceNode *dummy;
1105 : : GSequence *tmp_seq;
1106 : :
1107 : 35490 : g_return_val_if_fail (seq != NULL, NULL);
1108 : :
1109 : 35490 : check_seq_access (seq);
1110 : :
1111 : 35490 : seq->access_prohibited = TRUE;
1112 : :
1113 : 35490 : tmp_seq = g_sequence_new (NULL);
1114 : 35490 : tmp_seq->real_sequence = seq;
1115 : :
1116 : 35490 : dummy = g_sequence_append (tmp_seq, data);
1117 : :
1118 : 35490 : node = node_find (seq->end_node, dummy,
1119 : : seq->end_node, iter_cmp, cmp_data);
1120 : :
1121 : 35490 : g_sequence_free (tmp_seq);
1122 : :
1123 : 35490 : seq->access_prohibited = FALSE;
1124 : :
1125 : 35490 : return node;
1126 : : }
1127 : :
1128 : : /**
1129 : : * g_sequence_iter_get_sequence:
1130 : : * @iter: a #GSequenceIter
1131 : : *
1132 : : * Returns the #GSequence that @iter points into.
1133 : : *
1134 : : * Returns: (transfer none): the #GSequence that @iter points into
1135 : : *
1136 : : * Since: 2.14
1137 : : */
1138 : : GSequence *
1139 : 14699096 : g_sequence_iter_get_sequence (GSequenceIter *iter)
1140 : : {
1141 : : GSequence *seq;
1142 : :
1143 : 14699096 : g_return_val_if_fail (iter != NULL, NULL);
1144 : :
1145 : 14699096 : seq = get_sequence (iter);
1146 : :
1147 : : /* For temporary sequences, this points to the sequence that
1148 : : * is actually being manipulated
1149 : : */
1150 : 14699096 : return seq->real_sequence;
1151 : : }
1152 : :
1153 : : /**
1154 : : * g_sequence_get:
1155 : : * @iter: a #GSequenceIter
1156 : : *
1157 : : * Returns the data that @iter points to.
1158 : : *
1159 : : * Returns: (transfer none): the data that @iter points to
1160 : : *
1161 : : * Since: 2.14
1162 : : */
1163 : : gpointer
1164 : 245090001 : g_sequence_get (GSequenceIter *iter)
1165 : : {
1166 : 245090001 : g_return_val_if_fail (iter != NULL, NULL);
1167 : 245090001 : g_return_val_if_fail (!is_end (iter), NULL);
1168 : :
1169 : 245090001 : return iter->data;
1170 : : }
1171 : :
1172 : : /**
1173 : : * g_sequence_set:
1174 : : * @iter: a #GSequenceIter
1175 : : * @data: new data for the item
1176 : : *
1177 : : * Changes the data for the item pointed to by @iter to be @data. If
1178 : : * the sequence has a data destroy function associated with it, that
1179 : : * function is called on the existing data that @iter pointed to.
1180 : : *
1181 : : * Since: 2.14
1182 : : */
1183 : : void
1184 : 1079272 : g_sequence_set (GSequenceIter *iter,
1185 : : gpointer data)
1186 : : {
1187 : : GSequence *seq;
1188 : :
1189 : 1079272 : g_return_if_fail (iter != NULL);
1190 : :
1191 : 1079272 : seq = get_sequence (iter);
1192 : 1079272 : g_return_if_fail (!seq_is_end (seq, iter));
1193 : :
1194 : : /* If @data is identical to iter->data, it is destroyed
1195 : : * here. This will work right in case of ref-counted objects. Also
1196 : : * it is similar to what ghashtables do.
1197 : : *
1198 : : * For non-refcounted data it's a little less convenient, but
1199 : : * code relying on self-setting not destroying would be
1200 : : * pretty dubious anyway ...
1201 : : */
1202 : :
1203 : 1079272 : if (seq->data_destroy_notify)
1204 : 1079272 : seq->data_destroy_notify (iter->data);
1205 : :
1206 : 1079272 : iter->data = data;
1207 : : }
1208 : :
1209 : : /**
1210 : : * g_sequence_get_length:
1211 : : * @seq: a #GSequence
1212 : : *
1213 : : * Returns the positive length (>= 0) of @seq. Note that this method is
1214 : : * O(h) where `h' is the height of the tree. It is thus more efficient
1215 : : * to use g_sequence_is_empty() when comparing the length to zero.
1216 : : *
1217 : : * Returns: the length of @seq
1218 : : *
1219 : : * Since: 2.14
1220 : : */
1221 : : gint
1222 : 12849631 : g_sequence_get_length (GSequence *seq)
1223 : : {
1224 : 12849631 : return node_get_length (seq->end_node) - 1;
1225 : : }
1226 : :
1227 : : /**
1228 : : * g_sequence_is_empty:
1229 : : * @seq: a #GSequence
1230 : : *
1231 : : * Returns %TRUE if the sequence contains zero items.
1232 : : *
1233 : : * This function is functionally identical to checking the result of
1234 : : * g_sequence_get_length() being equal to zero. However this function is
1235 : : * implemented in O(1) running time.
1236 : : *
1237 : : * Returns: %TRUE if the sequence is empty, otherwise %FALSE.
1238 : : *
1239 : : * Since: 2.48
1240 : : */
1241 : : gboolean
1242 : 6129676 : g_sequence_is_empty (GSequence *seq)
1243 : : {
1244 : 6129676 : return (seq->end_node->parent == NULL) && (seq->end_node->left == NULL);
1245 : : }
1246 : :
1247 : : /**
1248 : : * g_sequence_get_end_iter:
1249 : : * @seq: a #GSequence
1250 : : *
1251 : : * Returns the end iterator for @seg
1252 : : *
1253 : : * Returns: (transfer none): the end iterator for @seq
1254 : : *
1255 : : * Since: 2.14
1256 : : */
1257 : : GSequenceIter *
1258 : 81943662 : g_sequence_get_end_iter (GSequence *seq)
1259 : : {
1260 : 81943662 : g_return_val_if_fail (seq != NULL, NULL);
1261 : :
1262 : 81943662 : return seq->end_node;
1263 : : }
1264 : :
1265 : : /**
1266 : : * g_sequence_get_begin_iter:
1267 : : * @seq: a #GSequence
1268 : : *
1269 : : * Returns the begin iterator for @seq.
1270 : : *
1271 : : * Returns: (transfer none): the begin iterator for @seq.
1272 : : *
1273 : : * Since: 2.14
1274 : : */
1275 : : GSequenceIter *
1276 : 8752843 : g_sequence_get_begin_iter (GSequence *seq)
1277 : : {
1278 : 8752843 : g_return_val_if_fail (seq != NULL, NULL);
1279 : :
1280 : 8752843 : return node_get_first (seq->end_node);
1281 : : }
1282 : :
1283 : : static int
1284 : 5022332 : clamp_position (GSequence *seq,
1285 : : int pos)
1286 : : {
1287 : 5022332 : gint len = g_sequence_get_length (seq);
1288 : :
1289 : 5022332 : if (pos > len || pos < 0)
1290 : 666440 : pos = len;
1291 : :
1292 : 5022332 : return pos;
1293 : : }
1294 : :
1295 : : /**
1296 : : * g_sequence_get_iter_at_pos:
1297 : : * @seq: a #GSequence
1298 : : * @pos: a position in @seq, or -1 for the end
1299 : : *
1300 : : * Returns the iterator at position @pos. If @pos is negative or larger
1301 : : * than the number of items in @seq, the end iterator is returned.
1302 : : *
1303 : : * Returns: (transfer none): The #GSequenceIter at position @pos
1304 : : *
1305 : : * Since: 2.14
1306 : : */
1307 : : GSequenceIter *
1308 : 5022332 : g_sequence_get_iter_at_pos (GSequence *seq,
1309 : : gint pos)
1310 : : {
1311 : 5022332 : g_return_val_if_fail (seq != NULL, NULL);
1312 : :
1313 : 5022332 : pos = clamp_position (seq, pos);
1314 : :
1315 : 5022332 : return node_get_by_pos (seq->end_node, pos);
1316 : : }
1317 : :
1318 : : /**
1319 : : * g_sequence_move:
1320 : : * @src: a #GSequenceIter pointing to the item to move
1321 : : * @dest: a #GSequenceIter pointing to the position to which
1322 : : * the item is moved
1323 : : *
1324 : : * Moves the item pointed to by @src to the position indicated by @dest.
1325 : : * After calling this function @dest will point to the position immediately
1326 : : * after @src. It is allowed for @src and @dest to point into different
1327 : : * sequences.
1328 : : *
1329 : : * Since: 2.14
1330 : : **/
1331 : : void
1332 : 34628 : g_sequence_move (GSequenceIter *src,
1333 : : GSequenceIter *dest)
1334 : : {
1335 : 34628 : g_return_if_fail (src != NULL);
1336 : 34628 : g_return_if_fail (dest != NULL);
1337 : 34628 : g_return_if_fail (!is_end (src));
1338 : :
1339 : 34628 : if (src == dest)
1340 : 10709 : return;
1341 : :
1342 : 23919 : node_unlink (src);
1343 : 23919 : node_insert_before (dest, src);
1344 : : }
1345 : :
1346 : : /* GSequenceIter */
1347 : :
1348 : : /**
1349 : : * g_sequence_iter_is_end:
1350 : : * @iter: a #GSequenceIter
1351 : : *
1352 : : * Returns whether @iter is the end iterator
1353 : : *
1354 : : * Returns: Whether @iter is the end iterator
1355 : : *
1356 : : * Since: 2.14
1357 : : */
1358 : : gboolean
1359 : 1773424 : g_sequence_iter_is_end (GSequenceIter *iter)
1360 : : {
1361 : 1773424 : g_return_val_if_fail (iter != NULL, FALSE);
1362 : :
1363 : 1773424 : return is_end (iter);
1364 : : }
1365 : :
1366 : : /**
1367 : : * g_sequence_iter_is_begin:
1368 : : * @iter: a #GSequenceIter
1369 : : *
1370 : : * Returns whether @iter is the begin iterator
1371 : : *
1372 : : * Returns: whether @iter is the begin iterator
1373 : : *
1374 : : * Since: 2.14
1375 : : */
1376 : : gboolean
1377 : 52784 : g_sequence_iter_is_begin (GSequenceIter *iter)
1378 : : {
1379 : 52784 : g_return_val_if_fail (iter != NULL, FALSE);
1380 : :
1381 : 52784 : return (node_get_prev (iter) == iter);
1382 : : }
1383 : :
1384 : : /**
1385 : : * g_sequence_iter_get_position:
1386 : : * @iter: a #GSequenceIter
1387 : : *
1388 : : * Returns the position of @iter
1389 : : *
1390 : : * Returns: the position of @iter
1391 : : *
1392 : : * Since: 2.14
1393 : : */
1394 : : gint
1395 : 1886866 : g_sequence_iter_get_position (GSequenceIter *iter)
1396 : : {
1397 : 1886866 : g_return_val_if_fail (iter != NULL, -1);
1398 : :
1399 : 1886866 : return node_get_pos (iter);
1400 : : }
1401 : :
1402 : : /**
1403 : : * g_sequence_iter_next:
1404 : : * @iter: a #GSequenceIter
1405 : : *
1406 : : * Returns an iterator pointing to the next position after @iter.
1407 : : * If @iter is the end iterator, the end iterator is returned.
1408 : : *
1409 : : * Returns: (transfer none): a #GSequenceIter pointing to the next position after @iter
1410 : : *
1411 : : * Since: 2.14
1412 : : */
1413 : : GSequenceIter *
1414 : 114957606 : g_sequence_iter_next (GSequenceIter *iter)
1415 : : {
1416 : 114957606 : g_return_val_if_fail (iter != NULL, NULL);
1417 : :
1418 : 114957606 : return node_get_next (iter);
1419 : : }
1420 : :
1421 : : /**
1422 : : * g_sequence_iter_prev:
1423 : : * @iter: a #GSequenceIter
1424 : : *
1425 : : * Returns an iterator pointing to the previous position before @iter.
1426 : : * If @iter is the begin iterator, the begin iterator is returned.
1427 : : *
1428 : : * Returns: (transfer none): a #GSequenceIter pointing to the previous position
1429 : : * before @iter
1430 : : *
1431 : : * Since: 2.14
1432 : : */
1433 : : GSequenceIter *
1434 : 109146 : g_sequence_iter_prev (GSequenceIter *iter)
1435 : : {
1436 : 109146 : g_return_val_if_fail (iter != NULL, NULL);
1437 : :
1438 : 109146 : return node_get_prev (iter);
1439 : : }
1440 : :
1441 : : /**
1442 : : * g_sequence_iter_move:
1443 : : * @iter: a #GSequenceIter
1444 : : * @delta: A positive or negative number indicating how many positions away
1445 : : * from @iter the returned #GSequenceIter will be
1446 : : *
1447 : : * Returns the #GSequenceIter which is @delta positions away from @iter.
1448 : : * If @iter is closer than -@delta positions to the beginning of the sequence,
1449 : : * the begin iterator is returned. If @iter is closer than @delta positions
1450 : : * to the end of the sequence, the end iterator is returned.
1451 : : *
1452 : : * Returns: (transfer none): a #GSequenceIter which is @delta positions away from @iter
1453 : : *
1454 : : * Since: 2.14
1455 : : */
1456 : : GSequenceIter *
1457 : 289932 : g_sequence_iter_move (GSequenceIter *iter,
1458 : : gint delta)
1459 : : {
1460 : : gint new_pos;
1461 : : gint len;
1462 : :
1463 : 289932 : g_return_val_if_fail (iter != NULL, NULL);
1464 : :
1465 : 289932 : len = g_sequence_get_length (get_sequence (iter));
1466 : :
1467 : 289932 : new_pos = node_get_pos (iter) + delta;
1468 : :
1469 : 289932 : if (new_pos < 0)
1470 : 1 : new_pos = 0;
1471 : 289931 : else if (new_pos > len)
1472 : 2 : new_pos = len;
1473 : :
1474 : 289932 : return node_get_by_pos (iter, new_pos);
1475 : : }
1476 : :
1477 : : /**
1478 : : * g_sequence_swap:
1479 : : * @a: a #GSequenceIter
1480 : : * @b: a #GSequenceIter
1481 : : *
1482 : : * Swaps the items pointed to by @a and @b. It is allowed for @a and @b
1483 : : * to point into difference sequences.
1484 : : *
1485 : : * Since: 2.14
1486 : : */
1487 : : void
1488 : 6698 : g_sequence_swap (GSequenceIter *a,
1489 : : GSequenceIter *b)
1490 : : {
1491 : : GSequenceNode *leftmost, *rightmost, *rightmost_next;
1492 : : int a_pos, b_pos;
1493 : :
1494 : 6698 : g_return_if_fail (!g_sequence_iter_is_end (a));
1495 : 6698 : g_return_if_fail (!g_sequence_iter_is_end (b));
1496 : :
1497 : 6698 : if (a == b)
1498 : 43 : return;
1499 : :
1500 : 6655 : a_pos = g_sequence_iter_get_position (a);
1501 : 6655 : b_pos = g_sequence_iter_get_position (b);
1502 : :
1503 : 6655 : if (a_pos > b_pos)
1504 : : {
1505 : 3309 : leftmost = b;
1506 : 3309 : rightmost = a;
1507 : : }
1508 : : else
1509 : : {
1510 : 3346 : leftmost = a;
1511 : 3346 : rightmost = b;
1512 : : }
1513 : :
1514 : 6655 : rightmost_next = node_get_next (rightmost);
1515 : :
1516 : : /* The situation is now like this:
1517 : : *
1518 : : * ..., leftmost, ......., rightmost, rightmost_next, ...
1519 : : *
1520 : : */
1521 : 6655 : g_sequence_move (rightmost, leftmost);
1522 : 6655 : g_sequence_move (leftmost, rightmost_next);
1523 : : }
1524 : :
1525 : : /*
1526 : : * Implementation of a treap
1527 : : *
1528 : : *
1529 : : */
1530 : : static guint32
1531 : 5005020 : hash_uint32 (guint32 key)
1532 : : {
1533 : : /* This hash function is based on one found on Thomas Wang's
1534 : : * web page at
1535 : : *
1536 : : * http://www.concentric.net/~Ttwang/tech/inthash.htm
1537 : : *
1538 : : */
1539 : 5005020 : key = (key << 15) - key - 1;
1540 : 5005020 : key = key ^ (key >> 12);
1541 : 5005020 : key = key + (key << 2);
1542 : 5005020 : key = key ^ (key >> 4);
1543 : 5005020 : key = key + (key << 3) + (key << 11);
1544 : 5005020 : key = key ^ (key >> 16);
1545 : :
1546 : 5005020 : return key;
1547 : : }
1548 : :
1549 : : static inline guint
1550 : 73906985 : get_priority (GSequenceNode *node)
1551 : : {
1552 : 73906985 : return node->priority;
1553 : : }
1554 : :
1555 : : static guint
1556 : 5005020 : make_priority (guint32 key)
1557 : : {
1558 : 5005020 : key = hash_uint32 (key);
1559 : :
1560 : : /* We rely on 0 being less than all other priorities */
1561 : 5005020 : return key? key : 1;
1562 : : }
1563 : :
1564 : : static GSequenceNode *
1565 : 58146005 : find_root (GSequenceNode *node)
1566 : : {
1567 : 192864984 : while (node->parent)
1568 : 134718979 : node = node->parent;
1569 : :
1570 : 58146005 : return node;
1571 : : }
1572 : :
1573 : : static GSequenceNode *
1574 : 5005020 : node_new (gpointer data)
1575 : : {
1576 : 5005020 : GSequenceNode *node = g_slice_new0 (GSequenceNode);
1577 : :
1578 : : /*
1579 : : * Make a random number quickly. Some binary magic is used to avoid
1580 : : * the costs of proper RNG, such as locking around global GRand.
1581 : : *
1582 : : * Using just the node pointer alone is not enough, because in this
1583 : : * case freeing and re-allocating sequence causes node's priorities
1584 : : * to no longer be random. This happens for two reasons:
1585 : : * 1) Nodes are freed from the root and the treap's property is that
1586 : : * node's priority is >= than its children's priorities.
1587 : : * 2) g_slice_new0() will reuse freed nodes in the order similar to
1588 : : * the order of freeing.
1589 : : * As a result, there are severe problems where building the treap is
1590 : : * much slower (100x and more after a few sequence new/free
1591 : : * iterations) and treap becomes more like a list (tree height
1592 : : * approaches tree's number of elements), which increases costs of
1593 : : * using the built treap.
1594 : : *
1595 : : * Note that for performance reasons, counter completely ignores
1596 : : * multi-threading issues. This is fine because it's merely a source
1597 : : * of additional randomness. Even if it fails to ++ sometimes, this
1598 : : * won't really matter for its goal.
1599 : : *
1600 : : * Note that 64-bit counter is used to avoid undefined behavior on
1601 : : * overflow.
1602 : : *
1603 : : * See https://gitlab.gnome.org/GNOME/glib/-/issues/2468
1604 : : */
1605 : : static guint64 counter = 0;
1606 : 5005020 : guint32 hash_key = (guint32) GPOINTER_TO_UINT (node);
1607 : 5005020 : hash_key ^= (guint32) counter;
1608 : 5005020 : counter++;
1609 : :
1610 : 5005020 : node->n_nodes = 1;
1611 : 5005020 : node->priority = make_priority (hash_key);
1612 : 5005020 : node->data = data;
1613 : 5005020 : node->left = NULL;
1614 : 5005020 : node->right = NULL;
1615 : 5005020 : node->parent = NULL;
1616 : :
1617 : 5005020 : return node;
1618 : : }
1619 : :
1620 : : static GSequenceNode *
1621 : 9397459 : node_get_first (GSequenceNode *node)
1622 : : {
1623 : 9397459 : node = find_root (node);
1624 : :
1625 : 33842916 : while (node->left)
1626 : 24445457 : node = node->left;
1627 : :
1628 : 9397459 : return node;
1629 : : }
1630 : :
1631 : : static GSequenceNode *
1632 : 19710229 : node_get_last (GSequenceNode *node)
1633 : : {
1634 : 19710229 : node = find_root (node);
1635 : :
1636 : 67123337 : while (node->right)
1637 : 47413108 : node = node->right;
1638 : :
1639 : 19710229 : return node;
1640 : : }
1641 : :
1642 : : #define NODE_LEFT_CHILD(n) (((n)->parent) && ((n)->parent->left) == (n))
1643 : : #define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n))
1644 : :
1645 : : static GSequenceNode *
1646 : 119844775 : node_get_next (GSequenceNode *node)
1647 : : {
1648 : 119844775 : GSequenceNode *n = node;
1649 : :
1650 : 119844775 : if (n->right)
1651 : : {
1652 : 58121639 : n = n->right;
1653 : 108369604 : while (n->left)
1654 : 50247965 : n = n->left;
1655 : : }
1656 : : else
1657 : : {
1658 : 114576109 : while (NODE_RIGHT_CHILD (n))
1659 : 52852973 : n = n->parent;
1660 : :
1661 : 61723136 : if (n->parent)
1662 : 61705268 : n = n->parent;
1663 : : else
1664 : 17868 : n = node;
1665 : : }
1666 : :
1667 : 119844775 : return n;
1668 : : }
1669 : :
1670 : : static GSequenceNode *
1671 : 679840 : node_get_prev (GSequenceNode *node)
1672 : : {
1673 : 679840 : GSequenceNode *n = node;
1674 : :
1675 : 679840 : if (n->left)
1676 : : {
1677 : 284471 : n = n->left;
1678 : 498558 : while (n->right)
1679 : 214087 : n = n->right;
1680 : : }
1681 : : else
1682 : : {
1683 : 850621 : while (NODE_LEFT_CHILD (n))
1684 : 455252 : n = n->parent;
1685 : :
1686 : 395369 : if (n->parent)
1687 : 286089 : n = n->parent;
1688 : : else
1689 : 109280 : n = node;
1690 : : }
1691 : :
1692 : 679840 : return n;
1693 : : }
1694 : :
1695 : : #define N_NODES(n) ((n)? (n)->n_nodes : 0)
1696 : :
1697 : : static gint
1698 : 2867692 : node_get_pos (GSequenceNode *node)
1699 : : {
1700 : 2867692 : int n_smaller = 0;
1701 : :
1702 : 2867692 : if (node->left)
1703 : 1118014 : n_smaller = node->left->n_nodes;
1704 : :
1705 : 15157946 : while (node)
1706 : : {
1707 : 12290254 : if (NODE_RIGHT_CHILD (node))
1708 : 5248923 : n_smaller += N_NODES (node->parent->left) + 1;
1709 : :
1710 : 12290254 : node = node->parent;
1711 : : }
1712 : :
1713 : 2867692 : return n_smaller;
1714 : : }
1715 : :
1716 : : static GSequenceNode *
1717 : 5330207 : node_get_by_pos (GSequenceNode *node,
1718 : : gint pos)
1719 : : {
1720 : : int i;
1721 : :
1722 : 5330207 : node = find_root (node);
1723 : :
1724 : 17527292 : while ((i = N_NODES (node->left)) != pos)
1725 : : {
1726 : 12197085 : if (i < pos)
1727 : : {
1728 : 6241969 : node = node->right;
1729 : 6241969 : pos -= (i + 1);
1730 : : }
1731 : : else
1732 : : {
1733 : 5955116 : node = node->left;
1734 : : }
1735 : 12197085 : g_assert (node != NULL);
1736 : : }
1737 : :
1738 : 5330207 : return node;
1739 : : }
1740 : :
1741 : : static GSequenceNode *
1742 : 35490 : node_find (GSequenceNode *haystack,
1743 : : GSequenceNode *needle,
1744 : : GSequenceNode *end,
1745 : : GSequenceIterCompareFunc iter_cmp,
1746 : : gpointer cmp_data)
1747 : : {
1748 : : gint c;
1749 : :
1750 : 35490 : haystack = find_root (haystack);
1751 : :
1752 : : do
1753 : : {
1754 : : /* iter_cmp can't be passed the end node, since the function may
1755 : : * be user-supplied
1756 : : */
1757 : 162684 : if (haystack == end)
1758 : 6914 : c = 1;
1759 : : else
1760 : 155770 : c = iter_cmp (haystack, needle, cmp_data);
1761 : :
1762 : 162684 : if (c == 0)
1763 : 35490 : break;
1764 : :
1765 : 127194 : if (c > 0)
1766 : 66982 : haystack = haystack->left;
1767 : : else
1768 : 60212 : haystack = haystack->right;
1769 : : }
1770 : 127194 : while (haystack != NULL);
1771 : :
1772 : 35490 : return haystack;
1773 : : }
1774 : :
1775 : : static GSequenceNode *
1776 : 7629349 : node_find_closest (GSequenceNode *haystack,
1777 : : GSequenceNode *needle,
1778 : : GSequenceNode *end,
1779 : : GSequenceIterCompareFunc iter_cmp,
1780 : : gpointer cmp_data)
1781 : : {
1782 : : GSequenceNode *best;
1783 : : gint c;
1784 : :
1785 : 7629349 : haystack = find_root (haystack);
1786 : :
1787 : : do
1788 : : {
1789 : 42211427 : best = haystack;
1790 : :
1791 : : /* iter_cmp can't be passed the end node, since the function may
1792 : : * be user-supplied
1793 : : */
1794 : 42211427 : if (haystack == end)
1795 : 4790341 : c = 1;
1796 : : else
1797 : 37421086 : c = iter_cmp (haystack, needle, cmp_data);
1798 : :
1799 : : /* In the following we don't break even if c == 0. Instead we go on
1800 : : * searching along the 'bigger' nodes, so that we find the last one
1801 : : * that is equal to the needle.
1802 : : */
1803 : 42211427 : if (c > 0)
1804 : 15156231 : haystack = haystack->left;
1805 : : else
1806 : 27055196 : haystack = haystack->right;
1807 : : }
1808 : 42211427 : while (haystack != NULL);
1809 : :
1810 : : /* If the best node is smaller or equal to the data, then move one step
1811 : : * to the right to make sure the best one is strictly bigger than the data
1812 : : */
1813 : 7629349 : if (best != end && c <= 0)
1814 : 3604478 : best = node_get_next (best);
1815 : :
1816 : 7629349 : return best;
1817 : : }
1818 : :
1819 : : static gint
1820 : 12849631 : node_get_length (GSequenceNode *node)
1821 : : {
1822 : 12849631 : node = find_root (node);
1823 : :
1824 : 12849631 : return node->n_nodes;
1825 : : }
1826 : :
1827 : : static void
1828 : 12711754 : real_node_free (GSequenceNode *node,
1829 : : GSequence *seq)
1830 : : {
1831 : 12711754 : if (node)
1832 : : {
1833 : 5004790 : real_node_free (node->left, seq);
1834 : 5004790 : real_node_free (node->right, seq);
1835 : :
1836 : 5004790 : if (seq && seq->data_destroy_notify && node != seq->end_node)
1837 : 2343522 : seq->data_destroy_notify (node->data);
1838 : :
1839 : 5004790 : g_slice_free (GSequenceNode, node);
1840 : : }
1841 : 12711754 : }
1842 : :
1843 : : static void
1844 : 2702174 : node_free (GSequenceNode *node,
1845 : : GSequence *seq)
1846 : : {
1847 : 2702174 : node = find_root (node);
1848 : :
1849 : 2702174 : real_node_free (node, seq);
1850 : 2702174 : }
1851 : :
1852 : : static void
1853 : 131469609 : node_update_fields (GSequenceNode *node)
1854 : : {
1855 : 131469609 : int n_nodes = 1;
1856 : :
1857 : 131469609 : n_nodes += N_NODES (node->left);
1858 : 131469609 : n_nodes += N_NODES (node->right);
1859 : :
1860 : 131469609 : node->n_nodes = n_nodes;
1861 : 131469609 : }
1862 : :
1863 : : static void
1864 : 24294787 : node_rotate (GSequenceNode *node)
1865 : : {
1866 : : GSequenceNode *tmp, *old;
1867 : :
1868 : 24294787 : g_assert (node->parent);
1869 : 24294787 : g_assert (node->parent != node);
1870 : :
1871 : 24294787 : if (NODE_LEFT_CHILD (node))
1872 : : {
1873 : : /* rotate right */
1874 : 12207898 : tmp = node->right;
1875 : :
1876 : 12207898 : node->right = node->parent;
1877 : 12207898 : node->parent = node->parent->parent;
1878 : 12207898 : if (node->parent)
1879 : : {
1880 : 10503617 : if (node->parent->left == node->right)
1881 : 4422643 : node->parent->left = node;
1882 : : else
1883 : 6080974 : node->parent->right = node;
1884 : : }
1885 : :
1886 : 12207898 : g_assert (node->right);
1887 : :
1888 : 12207898 : node->right->parent = node;
1889 : 12207898 : node->right->left = tmp;
1890 : :
1891 : 12207898 : if (node->right->left)
1892 : 4685671 : node->right->left->parent = node->right;
1893 : :
1894 : 12207898 : old = node->right;
1895 : : }
1896 : : else
1897 : : {
1898 : : /* rotate left */
1899 : 12086889 : tmp = node->left;
1900 : :
1901 : 12086889 : node->left = node->parent;
1902 : 12086889 : node->parent = node->parent->parent;
1903 : 12086889 : if (node->parent)
1904 : : {
1905 : 9905380 : if (node->parent->right == node->left)
1906 : 3342029 : node->parent->right = node;
1907 : : else
1908 : 6563351 : node->parent->left = node;
1909 : : }
1910 : :
1911 : 12086889 : g_assert (node->left);
1912 : :
1913 : 12086889 : node->left->parent = node;
1914 : 12086889 : node->left->right = tmp;
1915 : :
1916 : 12086889 : if (node->left->right)
1917 : 5955409 : node->left->right->parent = node->left;
1918 : :
1919 : 12086889 : old = node->left;
1920 : : }
1921 : :
1922 : 24294787 : node_update_fields (old);
1923 : 24294787 : node_update_fields (node);
1924 : 24294787 : }
1925 : :
1926 : : static void
1927 : 101330698 : node_update_fields_deep (GSequenceNode *node)
1928 : : {
1929 : 101330698 : if (node)
1930 : : {
1931 : 81972952 : node_update_fields (node);
1932 : :
1933 : 81972952 : node_update_fields_deep (node->parent);
1934 : : }
1935 : 101330698 : }
1936 : :
1937 : : static void
1938 : 20019096 : rotate_down (GSequenceNode *node,
1939 : : guint priority)
1940 : : {
1941 : : guint left, right;
1942 : :
1943 : 20019096 : left = node->left ? get_priority (node->left) : 0;
1944 : 20019096 : right = node->right ? get_priority (node->right) : 0;
1945 : :
1946 : 32769150 : while (priority < left || priority < right)
1947 : : {
1948 : 12750054 : if (left > right)
1949 : 4744877 : node_rotate (node->left);
1950 : : else
1951 : 8005177 : node_rotate (node->right);
1952 : :
1953 : 12750054 : left = node->left ? get_priority (node->left) : 0;
1954 : 12750054 : right = node->right ? get_priority (node->right) : 0;
1955 : : }
1956 : 20019096 : }
1957 : :
1958 : : static void
1959 : 661350 : node_cut (GSequenceNode *node)
1960 : : {
1961 : 1934595 : while (node->parent)
1962 : 1273245 : node_rotate (node);
1963 : :
1964 : 661350 : if (node->left)
1965 : 333504 : node->left->parent = NULL;
1966 : :
1967 : 661350 : node->left = NULL;
1968 : 661350 : node_update_fields (node);
1969 : :
1970 : 661350 : rotate_down (node, get_priority (node));
1971 : 661350 : }
1972 : :
1973 : : static void
1974 : 245733 : node_join (GSequenceNode *left,
1975 : : GSequenceNode *right)
1976 : : {
1977 : 245733 : GSequenceNode *fake = node_new (NULL);
1978 : :
1979 : 245733 : fake->left = find_root (left);
1980 : 245733 : fake->right = find_root (right);
1981 : 245733 : fake->left->parent = fake;
1982 : 245733 : fake->right->parent = fake;
1983 : :
1984 : 245733 : node_update_fields (fake);
1985 : :
1986 : 245733 : node_unlink (fake);
1987 : :
1988 : 245733 : node_free (fake, NULL);
1989 : 245733 : }
1990 : :
1991 : : static void
1992 : 10751200 : node_insert_before (GSequenceNode *node,
1993 : : GSequenceNode *new)
1994 : : {
1995 : 10751200 : new->left = node->left;
1996 : 10751200 : if (new->left)
1997 : 4072623 : new->left->parent = new;
1998 : :
1999 : 10751200 : new->parent = node;
2000 : 10751200 : node->left = new;
2001 : :
2002 : 10751200 : node_update_fields_deep (new);
2003 : :
2004 : 21022688 : while (new->parent && get_priority (new) > get_priority (new->parent))
2005 : 10271488 : node_rotate (new);
2006 : :
2007 : 10751200 : rotate_down (new, get_priority (new));
2008 : 10751200 : }
2009 : :
2010 : : static void
2011 : 8606546 : node_unlink (GSequenceNode *node)
2012 : : {
2013 : 8606546 : rotate_down (node, 0);
2014 : :
2015 : 8606546 : if (NODE_RIGHT_CHILD (node))
2016 : 484882 : node->parent->right = NULL;
2017 : 8121664 : else if (NODE_LEFT_CHILD (node))
2018 : 8121664 : node->parent->left = NULL;
2019 : :
2020 : 8606546 : if (node->parent)
2021 : 8606546 : node_update_fields_deep (node->parent);
2022 : :
2023 : 8606546 : node->parent = NULL;
2024 : 8606546 : }
2025 : :
2026 : : static void
2027 : 7593635 : node_insert_sorted (GSequenceNode *node,
2028 : : GSequenceNode *new,
2029 : : GSequenceNode *end,
2030 : : GSequenceIterCompareFunc iter_cmp,
2031 : : gpointer cmp_data)
2032 : : {
2033 : : GSequenceNode *closest;
2034 : :
2035 : 7593635 : closest = node_find_closest (node, new, end, iter_cmp, cmp_data);
2036 : :
2037 : 7593635 : node_unlink (new);
2038 : :
2039 : 7593635 : node_insert_before (closest, new);
2040 : 7593635 : }
|
