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][glib-Sequences] 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 : 9141242 : check_seq_access (GSequence *seq)
128 : : {
129 [ - + ]: 9141242 : 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 : 9141242 : }
135 : :
136 : : static GSequence *
137 : 19777034 : get_sequence (GSequenceNode *node)
138 : : {
139 : 19777034 : return (GSequence *)node_get_last (node)->data;
140 : : }
141 : :
142 : : static gboolean
143 : 2082334 : seq_is_end (GSequence *seq,
144 : : GSequenceIter *iter)
145 : : {
146 : 2082334 : return seq->end_node == iter;
147 : : }
148 : :
149 : : static gboolean
150 : 247958266 : is_end (GSequenceIter *iter)
151 : : {
152 : 247958266 : GSequenceIter *parent = iter->parent;
153 : :
154 [ + + ]: 247958266 : if (iter->right)
155 : 126465043 : return FALSE;
156 : :
157 [ + + ]: 121493223 : if (!parent)
158 : 337263 : return TRUE;
159 : :
160 [ + + ]: 221255090 : while (parent->right == iter)
161 : : {
162 : 100452584 : iter = parent;
163 : 100452584 : parent = iter->parent;
164 : :
165 [ + + ]: 100452584 : if (!parent)
166 : 353454 : return TRUE;
167 : : }
168 : :
169 : 120802506 : 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 : 29448122 : iter_compare (GSequenceIter *node1,
184 : : GSequenceIter *node2,
185 : : gpointer data)
186 : : {
187 : 29448122 : const SortInfo *info = data;
188 : : gint retval;
189 : :
190 [ - + ]: 29448122 : if (node1 == info->end_node)
191 : 0 : return 1;
192 : :
193 [ - + ]: 29448122 : if (node2 == info->end_node)
194 : 0 : return -1;
195 : :
196 : 29448122 : retval = info->cmp_func (node1->data, node2->data, info->cmp_data);
197 : :
198 : 29448122 : 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 : 2145690 : g_sequence_new (GDestroyNotify data_destroy)
219 : : {
220 : 2145690 : GSequence *seq = g_new (GSequence, 1);
221 : 2145690 : seq->data_destroy_notify = data_destroy;
222 : :
223 : 2145690 : seq->end_node = node_new (seq);
224 : :
225 : 2145690 : seq->access_prohibited = FALSE;
226 : :
227 : 2145690 : seq->real_sequence = seq;
228 : :
229 : 2145690 : 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 : 2145492 : g_sequence_free (GSequence *seq)
244 : : {
245 : 2145492 : g_return_if_fail (seq != NULL);
246 : :
247 : 2145492 : check_seq_access (seq);
248 : :
249 : 2145492 : node_free (seq->end_node, seq);
250 : :
251 : 2145492 : 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 : 35766 : 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 : 35766 : g_return_if_fail (func != NULL);
277 : 35766 : g_return_if_fail (begin != NULL);
278 : 35766 : g_return_if_fail (end != NULL);
279 : :
280 : 35766 : seq = get_sequence (begin);
281 : :
282 : 35766 : seq->access_prohibited = TRUE;
283 : :
284 : 35766 : iter = begin;
285 [ + + ]: 793813 : while (iter != end)
286 : : {
287 : 758047 : GSequenceIter *next = node_get_next (iter);
288 : :
289 : 758047 : func (iter->data, user_data);
290 : :
291 : 758047 : iter = next;
292 : : }
293 : :
294 : 35766 : 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 : 17951 : g_sequence_foreach (GSequence *seq,
310 : : GFunc func,
311 : : gpointer user_data)
312 : : {
313 : : GSequenceIter *begin, *end;
314 : :
315 : 17951 : check_seq_access (seq);
316 : :
317 : 17951 : begin = g_sequence_get_begin_iter (seq);
318 : 17951 : end = g_sequence_get_end_iter (seq);
319 : :
320 : 17951 : g_sequence_foreach_range (begin, end, func, user_data);
321 : 17951 : }
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 : 17965 : g_sequence_range_get_midpoint (GSequenceIter *begin,
342 : : GSequenceIter *end)
343 : : {
344 : : int begin_pos, end_pos, mid_pos;
345 : :
346 : 17965 : g_return_val_if_fail (begin != NULL, NULL);
347 : 17965 : g_return_val_if_fail (end != NULL, NULL);
348 : 17965 : g_return_val_if_fail (get_sequence (begin) == get_sequence (end), NULL);
349 : :
350 : 17965 : begin_pos = node_get_pos (begin);
351 : 17965 : end_pos = node_get_pos (end);
352 : :
353 : 17965 : g_return_val_if_fail (end_pos >= begin_pos, NULL);
354 : :
355 : 17965 : mid_pos = begin_pos + (end_pos - begin_pos) / 2;
356 : :
357 : 17965 : 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 : 327845 : g_sequence_iter_compare (GSequenceIter *a,
377 : : GSequenceIter *b)
378 : : {
379 : : gint a_pos, b_pos;
380 : : GSequence *seq_a, *seq_b;
381 : :
382 : 327845 : g_return_val_if_fail (a != NULL, 0);
383 : 327845 : g_return_val_if_fail (b != NULL, 0);
384 : :
385 : 327845 : seq_a = get_sequence (a);
386 : 327845 : seq_b = get_sequence (b);
387 : 327845 : g_return_val_if_fail (seq_a == seq_b, 0);
388 : :
389 : 327845 : check_seq_access (seq_a);
390 : 327845 : check_seq_access (seq_b);
391 : :
392 : 327845 : a_pos = node_get_pos (a);
393 : 327845 : b_pos = node_get_pos (b);
394 : :
395 [ + + ]: 327845 : if (a_pos == b_pos)
396 : 50066 : return 0;
397 [ + + ]: 277779 : else if (a_pos > b_pos)
398 : 14011 : return 1;
399 : : else
400 : 263768 : 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 : 1434031 : g_sequence_append (GSequence *seq,
416 : : gpointer data)
417 : : {
418 : : GSequenceNode *node;
419 : :
420 : 1434031 : g_return_val_if_fail (seq != NULL, NULL);
421 : :
422 : 1434031 : check_seq_access (seq);
423 : :
424 : 1434031 : node = node_new (data);
425 : 1434031 : node_insert_before (seq->end_node, node);
426 : :
427 : 1434031 : 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 : 233429 : g_sequence_prepend (GSequence *seq,
443 : : gpointer data)
444 : : {
445 : : GSequenceNode *node, *first;
446 : :
447 : 233429 : g_return_val_if_fail (seq != NULL, NULL);
448 : :
449 : 233429 : check_seq_access (seq);
450 : :
451 : 233429 : node = node_new (data);
452 : 233429 : first = node_get_first (seq->end_node);
453 : :
454 : 233429 : node_insert_before (first, node);
455 : :
456 : 233429 : 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 : 955680 : g_sequence_insert_before (GSequenceIter *iter,
472 : : gpointer data)
473 : : {
474 : : GSequence *seq;
475 : : GSequenceNode *node;
476 : :
477 : 955680 : g_return_val_if_fail (iter != NULL, NULL);
478 : :
479 : 955680 : seq = get_sequence (iter);
480 : 955680 : check_seq_access (seq);
481 : :
482 : 955680 : node = node_new (data);
483 : :
484 : 955680 : node_insert_before (iter, node);
485 : :
486 : 955680 : 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 : 225664 : g_sequence_remove (GSequenceIter *iter)
503 : : {
504 : : GSequence *seq;
505 : :
506 : 225664 : g_return_if_fail (iter != NULL);
507 : :
508 : 225664 : seq = get_sequence (iter);
509 : 225664 : g_return_if_fail (!seq_is_end (seq, iter));
510 : :
511 : 225664 : check_seq_access (seq);
512 : :
513 : 225664 : node_unlink (iter);
514 : 225664 : 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 : 94360 : g_sequence_remove_range (GSequenceIter *begin,
531 : : GSequenceIter *end)
532 : : {
533 : : GSequence *seq_begin, *seq_end;
534 : :
535 : 94360 : seq_begin = get_sequence (begin);
536 : 94360 : seq_end = get_sequence (end);
537 : 94360 : g_return_if_fail (seq_begin == seq_end);
538 : : /* check_seq_access() calls are done by g_sequence_move_range() */
539 : :
540 : 94360 : 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 : 290515 : g_sequence_move_range (GSequenceIter *dest,
562 : : GSequenceIter *begin,
563 : : GSequenceIter *end)
564 : : {
565 : 290515 : GSequence *src_seq, *end_seq, *dest_seq = NULL;
566 : : GSequenceNode *first;
567 : :
568 : 290515 : g_return_if_fail (begin != NULL);
569 : 290515 : g_return_if_fail (end != NULL);
570 : :
571 : 290515 : src_seq = get_sequence (begin);
572 : 290515 : check_seq_access (src_seq);
573 : :
574 : 290515 : end_seq = get_sequence (end);
575 : 290515 : check_seq_access (end_seq);
576 : :
577 [ + + ]: 290515 : if (dest)
578 : : {
579 : 196155 : dest_seq = get_sequence (dest);
580 : 196155 : check_seq_access (dest_seq);
581 : : }
582 : :
583 : 290515 : g_return_if_fail (src_seq == end_seq);
584 : :
585 : : /* Dest points to begin or end? */
586 [ + + + + ]: 290515 : if (dest == begin || dest == end)
587 : 603 : return;
588 : :
589 : : /* begin comes after end? */
590 [ + + ]: 289912 : if (g_sequence_iter_compare (begin, end) >= 0)
591 : 39635 : return;
592 : :
593 : : /* dest points somewhere in the (begin, end) range? */
594 [ + + + + : 251571 : if (dest && dest_seq == src_seq &&
+ + ]
595 [ + + ]: 2048 : g_sequence_iter_compare (dest, begin) > 0 &&
596 : 754 : g_sequence_iter_compare (dest, end) < 0)
597 : : {
598 : 262 : return;
599 : : }
600 : :
601 : 250015 : first = node_get_first (begin);
602 : :
603 : 250015 : node_cut (begin);
604 : :
605 : 250015 : node_cut (end);
606 : :
607 [ + + ]: 250015 : if (first != begin)
608 : 74657 : node_join (first, end);
609 : :
610 [ + + ]: 250015 : if (dest)
611 : : {
612 : 162012 : first = node_get_first (dest);
613 : :
614 : 162012 : node_cut (dest);
615 : :
616 : 162012 : node_join (begin, dest);
617 : :
618 [ + + ]: 162012 : if (dest != first)
619 : 9514 : node_join (first, begin);
620 : : }
621 : : else
622 : : {
623 : 88003 : 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 : 160361 : g_sequence_sort (GSequence *seq,
644 : : GCompareDataFunc cmp_func,
645 : : gpointer cmp_data)
646 : : {
647 : : SortInfo info;
648 : :
649 : 160361 : info.cmp_func = cmp_func;
650 : 160361 : info.cmp_data = cmp_data;
651 : 160361 : info.end_node = seq->end_node;
652 : :
653 : 160361 : check_seq_access (seq);
654 : :
655 : 160361 : g_sequence_sort_iter (seq, iter_compare, &info);
656 : 160361 : }
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 : 601549 : g_sequence_insert_sorted (GSequence *seq,
684 : : gpointer data,
685 : : GCompareDataFunc cmp_func,
686 : : gpointer cmp_data)
687 : : {
688 : : SortInfo info;
689 : :
690 : 601549 : g_return_val_if_fail (seq != NULL, NULL);
691 : 601549 : g_return_val_if_fail (cmp_func != NULL, NULL);
692 : :
693 : 601549 : info.cmp_func = cmp_func;
694 : 601549 : info.cmp_data = cmp_data;
695 : 601549 : info.end_node = seq->end_node;
696 : 601549 : check_seq_access (seq);
697 : :
698 : 601549 : 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 : 257206 : g_sequence_sort_changed (GSequenceIter *iter,
722 : : GCompareDataFunc cmp_func,
723 : : gpointer cmp_data)
724 : : {
725 : : GSequence *seq;
726 : : SortInfo info;
727 : :
728 : 257206 : g_return_if_fail (iter != NULL);
729 : :
730 : 257206 : seq = get_sequence (iter);
731 : : /* check_seq_access() call is done by g_sequence_sort_changed_iter() */
732 : 257206 : g_return_if_fail (!seq_is_end (seq, iter));
733 : :
734 : 257206 : info.cmp_func = cmp_func;
735 : 257206 : info.cmp_data = cmp_data;
736 : 257206 : info.end_node = seq->end_node;
737 : :
738 : 257206 : 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 : 17960 : g_sequence_search (GSequence *seq,
769 : : gpointer data,
770 : : GCompareDataFunc cmp_func,
771 : : gpointer cmp_data)
772 : : {
773 : : SortInfo info;
774 : :
775 : 17960 : g_return_val_if_fail (seq != NULL, NULL);
776 : :
777 : 17960 : info.cmp_func = cmp_func;
778 : 17960 : info.cmp_data = cmp_data;
779 : 17960 : info.end_node = seq->end_node;
780 : 17960 : check_seq_access (seq);
781 : :
782 : 17960 : 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 : 17628 : g_sequence_lookup (GSequence *seq,
814 : : gpointer data,
815 : : GCompareDataFunc cmp_func,
816 : : gpointer cmp_data)
817 : : {
818 : : SortInfo info;
819 : :
820 : 17628 : g_return_val_if_fail (seq != NULL, NULL);
821 : :
822 : 17628 : info.cmp_func = cmp_func;
823 : 17628 : info.cmp_data = cmp_data;
824 : 17628 : info.end_node = seq->end_node;
825 : 17628 : check_seq_access (seq);
826 : :
827 : 17628 : 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 : 178334 : g_sequence_sort_iter (GSequence *seq,
848 : : GSequenceIterCompareFunc cmp_func,
849 : : gpointer cmp_data)
850 : : {
851 : : GSequence *tmp;
852 : : GSequenceNode *begin, *end;
853 : :
854 : 178334 : g_return_if_fail (seq != NULL);
855 : 178334 : g_return_if_fail (cmp_func != NULL);
856 : :
857 : 178334 : check_seq_access (seq);
858 : :
859 : 178334 : begin = g_sequence_get_begin_iter (seq);
860 : 178334 : end = g_sequence_get_end_iter (seq);
861 : :
862 : 178334 : tmp = g_sequence_new (NULL);
863 : 178334 : tmp->real_sequence = seq;
864 : :
865 : 178334 : g_sequence_move_range (g_sequence_get_begin_iter (tmp), begin, end);
866 : :
867 : 178334 : seq->access_prohibited = TRUE;
868 : 178334 : tmp->access_prohibited = TRUE;
869 : :
870 [ + + ]: 6135527 : while (!g_sequence_is_empty (tmp))
871 : : {
872 : 5957193 : GSequenceNode *node = g_sequence_get_begin_iter (tmp);
873 : :
874 : 5957193 : node_insert_sorted (seq->end_node, node, seq->end_node,
875 : : cmp_func, cmp_data);
876 : : }
877 : :
878 : 178334 : tmp->access_prohibited = FALSE;
879 : 178334 : seq->access_prohibited = FALSE;
880 : :
881 : 178334 : 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 : 519444 : 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 : 519444 : g_return_if_fail (iter != NULL);
911 : 519444 : g_return_if_fail (iter_cmp != NULL);
912 : :
913 : 519444 : seq = get_sequence (iter);
914 : 519444 : g_return_if_fail (!seq_is_end (seq, iter));
915 : :
916 : 519444 : 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 : 519444 : next = node_get_next (iter);
924 : 519444 : prev = node_get_prev (iter);
925 : :
926 [ + + + + ]: 519444 : if (prev != iter && iter_cmp (prev, iter, cmp_data) == 0)
927 : 999 : return;
928 : :
929 [ + + + + ]: 518445 : if (!is_end (next) && iter_cmp (next, iter, cmp_data) == 0)
930 : 1 : return;
931 : :
932 : 518444 : seq->access_prohibited = TRUE;
933 : :
934 : 518444 : tmp_seq = g_sequence_new (NULL);
935 : 518444 : tmp_seq->real_sequence = seq;
936 : :
937 : 518444 : node_unlink (iter);
938 : 518444 : node_insert_before (tmp_seq->end_node, iter);
939 : :
940 : 518444 : node_insert_sorted (seq->end_node, iter, seq->end_node,
941 : : iter_cmp, cmp_data);
942 : :
943 : 518444 : g_sequence_free (tmp_seq);
944 : :
945 : 518444 : 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 : 1129661 : 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 : 1129661 : g_return_val_if_fail (seq != NULL, NULL);
982 : 1129661 : g_return_val_if_fail (iter_cmp != NULL, NULL);
983 : :
984 : 1129661 : check_seq_access (seq);
985 : :
986 : 1129661 : 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 : 1129661 : tmp_seq = g_sequence_new (NULL);
1001 : 1129661 : tmp_seq->real_sequence = seq;
1002 : :
1003 : 1129661 : new_node = g_sequence_append (tmp_seq, data);
1004 : :
1005 : 1129661 : node_insert_sorted (seq->end_node, new_node,
1006 : : seq->end_node, iter_cmp, cmp_data);
1007 : :
1008 : 1129661 : g_sequence_free (tmp_seq);
1009 : :
1010 : 1129661 : seq->access_prohibited = FALSE;
1011 : :
1012 : 1129661 : 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 : 35752 : 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 : 35752 : g_return_val_if_fail (seq != NULL, NULL);
1053 : :
1054 : 35752 : check_seq_access (seq);
1055 : :
1056 : 35752 : seq->access_prohibited = TRUE;
1057 : :
1058 : 35752 : tmp_seq = g_sequence_new (NULL);
1059 : 35752 : tmp_seq->real_sequence = seq;
1060 : :
1061 : 35752 : dummy = g_sequence_append (tmp_seq, data);
1062 : :
1063 : 35752 : node = node_find_closest (seq->end_node, dummy,
1064 : : seq->end_node, iter_cmp, cmp_data);
1065 : :
1066 : 35752 : g_sequence_free (tmp_seq);
1067 : :
1068 : 35752 : seq->access_prohibited = FALSE;
1069 : :
1070 : 35752 : 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 : 35431 : 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 : 35431 : g_return_val_if_fail (seq != NULL, NULL);
1108 : :
1109 : 35431 : check_seq_access (seq);
1110 : :
1111 : 35431 : seq->access_prohibited = TRUE;
1112 : :
1113 : 35431 : tmp_seq = g_sequence_new (NULL);
1114 : 35431 : tmp_seq->real_sequence = seq;
1115 : :
1116 : 35431 : dummy = g_sequence_append (tmp_seq, data);
1117 : :
1118 : 35431 : node = node_find (seq->end_node, dummy,
1119 : : seq->end_node, iter_cmp, cmp_data);
1120 : :
1121 : 35431 : g_sequence_free (tmp_seq);
1122 : :
1123 : 35431 : seq->access_prohibited = FALSE;
1124 : :
1125 : 35431 : 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 : 14755232 : g_sequence_iter_get_sequence (GSequenceIter *iter)
1140 : : {
1141 : : GSequence *seq;
1142 : :
1143 : 14755232 : g_return_val_if_fail (iter != NULL, NULL);
1144 : :
1145 : 14755232 : seq = get_sequence (iter);
1146 : :
1147 : : /* For temporary sequences, this points to the sequence that
1148 : : * is actually being manipulated
1149 : : */
1150 : 14755232 : 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 : 245630057 : g_sequence_get (GSequenceIter *iter)
1165 : : {
1166 : 245630057 : g_return_val_if_fail (iter != NULL, NULL);
1167 : 245630057 : g_return_val_if_fail (!is_end (iter), NULL);
1168 : :
1169 : 245630057 : 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 : 1080020 : g_sequence_set (GSequenceIter *iter,
1185 : : gpointer data)
1186 : : {
1187 : : GSequence *seq;
1188 : :
1189 : 1080020 : g_return_if_fail (iter != NULL);
1190 : :
1191 : 1080020 : seq = get_sequence (iter);
1192 : 1080020 : 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 [ + - ]: 1080020 : if (seq->data_destroy_notify)
1204 : 1080020 : seq->data_destroy_notify (iter->data);
1205 : :
1206 : 1080020 : 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 : 13014625 : g_sequence_get_length (GSequence *seq)
1223 : : {
1224 : 13014625 : 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 : 6139711 : g_sequence_is_empty (GSequence *seq)
1243 : : {
1244 [ + + + + ]: 6139711 : 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 : 82063614 : g_sequence_get_end_iter (GSequence *seq)
1259 : : {
1260 : 82063614 : g_return_val_if_fail (seq != NULL, NULL);
1261 : :
1262 : 82063614 : 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 : 8765091 : g_sequence_get_begin_iter (GSequence *seq)
1277 : : {
1278 : 8765091 : g_return_val_if_fail (seq != NULL, NULL);
1279 : :
1280 : 8765091 : return node_get_first (seq->end_node);
1281 : : }
1282 : :
1283 : : static int
1284 : 5161608 : clamp_position (GSequence *seq,
1285 : : int pos)
1286 : : {
1287 : 5161608 : gint len = g_sequence_get_length (seq);
1288 : :
1289 [ + + + + ]: 5161608 : if (pos > len || pos < 0)
1290 : 666801 : pos = len;
1291 : :
1292 : 5161608 : 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 : 5161608 : g_sequence_get_iter_at_pos (GSequence *seq,
1309 : : gint pos)
1310 : : {
1311 : 5161608 : g_return_val_if_fail (seq != NULL, NULL);
1312 : :
1313 : 5161608 : pos = clamp_position (seq, pos);
1314 : :
1315 : 5161608 : 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 : 34800 : g_sequence_move (GSequenceIter *src,
1333 : : GSequenceIter *dest)
1334 : : {
1335 : 34800 : g_return_if_fail (src != NULL);
1336 : 34800 : g_return_if_fail (dest != NULL);
1337 : 34800 : g_return_if_fail (!is_end (src));
1338 : :
1339 [ + + ]: 34800 : if (src == dest)
1340 : 10768 : return;
1341 : :
1342 : 24032 : node_unlink (src);
1343 : 24032 : 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 : 1774964 : g_sequence_iter_is_end (GSequenceIter *iter)
1360 : : {
1361 : 1774964 : g_return_val_if_fail (iter != NULL, FALSE);
1362 : :
1363 : 1774964 : 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 : 1888596 : g_sequence_iter_get_position (GSequenceIter *iter)
1396 : : {
1397 : 1888596 : g_return_val_if_fail (iter != NULL, -1);
1398 : :
1399 : 1888596 : 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 : 115170079 : g_sequence_iter_next (GSequenceIter *iter)
1415 : : {
1416 : 115170079 : g_return_val_if_fail (iter != NULL, NULL);
1417 : :
1418 : 115170079 : 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 : 109058 : g_sequence_iter_prev (GSequenceIter *iter)
1435 : : {
1436 : 109058 : g_return_val_if_fail (iter != NULL, NULL);
1437 : :
1438 : 109058 : 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 : 290497 : g_sequence_iter_move (GSequenceIter *iter,
1458 : : gint delta)
1459 : : {
1460 : : gint new_pos;
1461 : : gint len;
1462 : :
1463 : 290497 : g_return_val_if_fail (iter != NULL, NULL);
1464 : :
1465 : 290497 : len = g_sequence_get_length (get_sequence (iter));
1466 : :
1467 : 290497 : new_pos = node_get_pos (iter) + delta;
1468 : :
1469 [ + + ]: 290497 : if (new_pos < 0)
1470 : 1 : new_pos = 0;
1471 [ + + ]: 290496 : else if (new_pos > len)
1472 : 2 : new_pos = len;
1473 : :
1474 : 290497 : 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 : 6725 : g_sequence_swap (GSequenceIter *a,
1489 : : GSequenceIter *b)
1490 : : {
1491 : : GSequenceNode *leftmost, *rightmost, *rightmost_next;
1492 : : int a_pos, b_pos;
1493 : :
1494 : 6725 : g_return_if_fail (!g_sequence_iter_is_end (a));
1495 : 6725 : g_return_if_fail (!g_sequence_iter_is_end (b));
1496 : :
1497 [ + + ]: 6725 : if (a == b)
1498 : 43 : return;
1499 : :
1500 : 6682 : a_pos = g_sequence_iter_get_position (a);
1501 : 6682 : b_pos = g_sequence_iter_get_position (b);
1502 : :
1503 [ + + ]: 6682 : if (a_pos > b_pos)
1504 : : {
1505 : 3325 : leftmost = b;
1506 : 3325 : rightmost = a;
1507 : : }
1508 : : else
1509 : : {
1510 : 3357 : leftmost = a;
1511 : 3357 : rightmost = b;
1512 : : }
1513 : :
1514 : 6682 : rightmost_next = node_get_next (rightmost);
1515 : :
1516 : : /* The situation is now like this:
1517 : : *
1518 : : * ..., leftmost, ......., rightmost, rightmost_next, ...
1519 : : *
1520 : : */
1521 : 6682 : g_sequence_move (rightmost, leftmost);
1522 : 6682 : g_sequence_move (leftmost, rightmost_next);
1523 : : }
1524 : :
1525 : : /*
1526 : : * Implementation of a treap
1527 : : *
1528 : : *
1529 : : */
1530 : : static guint32
1531 : 5015013 : 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 : 5015013 : key = (key << 15) - key - 1;
1540 : 5015013 : key = key ^ (key >> 12);
1541 : 5015013 : key = key + (key << 2);
1542 : 5015013 : key = key ^ (key >> 4);
1543 : 5015013 : key = key + (key << 3) + (key << 11);
1544 : 5015013 : key = key ^ (key >> 16);
1545 : :
1546 : 5015013 : return key;
1547 : : }
1548 : :
1549 : : static inline guint
1550 : 73926540 : get_priority (GSequenceNode *node)
1551 : : {
1552 : 73926540 : return node->priority;
1553 : : }
1554 : :
1555 : : static guint
1556 : 5015013 : make_priority (guint32 key)
1557 : : {
1558 : 5015013 : key = hash_uint32 (key);
1559 : :
1560 : : /* We rely on 0 being less than all other priorities */
1561 [ + - ]: 5015013 : return key? key : 1;
1562 : : }
1563 : :
1564 : : static GSequenceNode *
1565 : 58546465 : find_root (GSequenceNode *node)
1566 : : {
1567 [ + + ]: 193221567 : while (node->parent)
1568 : 134675102 : node = node->parent;
1569 : :
1570 : 58546465 : return node;
1571 : : }
1572 : :
1573 : : static GSequenceNode *
1574 : 5015013 : node_new (gpointer data)
1575 : : {
1576 : 5015013 : 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 : 5015013 : guint32 hash_key = (guint32) GPOINTER_TO_UINT (node);
1607 : 5015013 : hash_key ^= (guint32) counter;
1608 : 5015013 : counter++;
1609 : :
1610 : 5015013 : node->n_nodes = 1;
1611 : 5015013 : node->priority = make_priority (hash_key);
1612 : 5015013 : node->data = data;
1613 : 5015013 : node->left = NULL;
1614 : 5015013 : node->right = NULL;
1615 : 5015013 : node->parent = NULL;
1616 : :
1617 : 5015013 : return node;
1618 : : }
1619 : :
1620 : : static GSequenceNode *
1621 : 9410547 : node_get_first (GSequenceNode *node)
1622 : : {
1623 : 9410547 : node = find_root (node);
1624 : :
1625 [ + + ]: 33887299 : while (node->left)
1626 : 24476752 : node = node->left;
1627 : :
1628 : 9410547 : return node;
1629 : : }
1630 : :
1631 : : static GSequenceNode *
1632 : 19777034 : node_get_last (GSequenceNode *node)
1633 : : {
1634 : 19777034 : node = find_root (node);
1635 : :
1636 [ + + ]: 67281153 : while (node->right)
1637 : 47504119 : node = node->right;
1638 : :
1639 : 19777034 : 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 : 120108062 : node_get_next (GSequenceNode *node)
1647 : : {
1648 : 120108062 : GSequenceNode *n = node;
1649 : :
1650 [ + + ]: 120108062 : if (n->right)
1651 : : {
1652 : 58207886 : n = n->right;
1653 [ + + ]: 108551690 : while (n->left)
1654 : 50343804 : n = n->left;
1655 : : }
1656 : : else
1657 : : {
1658 [ + + + + ]: 114947528 : while (NODE_RIGHT_CHILD (n))
1659 : 53047352 : n = n->parent;
1660 : :
1661 [ + + ]: 61900176 : if (n->parent)
1662 : 61882348 : n = n->parent;
1663 : : else
1664 : 17828 : n = node;
1665 : : }
1666 : :
1667 : 120108062 : return n;
1668 : : }
1669 : :
1670 : : static GSequenceNode *
1671 : 681286 : node_get_prev (GSequenceNode *node)
1672 : : {
1673 : 681286 : GSequenceNode *n = node;
1674 : :
1675 [ + + ]: 681286 : if (n->left)
1676 : : {
1677 : 286310 : n = n->left;
1678 [ + + ]: 502045 : while (n->right)
1679 : 215735 : n = n->right;
1680 : : }
1681 : : else
1682 : : {
1683 [ + + + + ]: 851078 : while (NODE_LEFT_CHILD (n))
1684 : 456102 : n = n->parent;
1685 : :
1686 [ + + ]: 394976 : if (n->parent)
1687 : 285592 : n = n->parent;
1688 : : else
1689 : 109384 : n = node;
1690 : : }
1691 : :
1692 : 681286 : return n;
1693 : : }
1694 : :
1695 : : #define N_NODES(n) ((n)? (n)->n_nodes : 0)
1696 : :
1697 : : static gint
1698 : 2870713 : node_get_pos (GSequenceNode *node)
1699 : : {
1700 : 2870713 : int n_smaller = 0;
1701 : :
1702 [ + + ]: 2870713 : if (node->left)
1703 : 1117517 : n_smaller = node->left->n_nodes;
1704 : :
1705 [ + + ]: 15162745 : while (node)
1706 : : {
1707 [ + + + + ]: 12292032 : if (NODE_RIGHT_CHILD (node))
1708 [ + + ]: 5249077 : n_smaller += N_NODES (node->parent->left) + 1;
1709 : :
1710 : 12292032 : node = node->parent;
1711 : : }
1712 : :
1713 : 2870713 : return n_smaller;
1714 : : }
1715 : :
1716 : : static GSequenceNode *
1717 : 5470070 : node_get_by_pos (GSequenceNode *node,
1718 : : gint pos)
1719 : : {
1720 : : int i;
1721 : :
1722 : 5470070 : node = find_root (node);
1723 : :
1724 [ + + + + ]: 17858715 : while ((i = N_NODES (node->left)) != pos)
1725 : : {
1726 [ + + ]: 12388645 : if (i < pos)
1727 : : {
1728 : 6291071 : node = node->right;
1729 : 6291071 : pos -= (i + 1);
1730 : : }
1731 : : else
1732 : : {
1733 : 6097574 : node = node->left;
1734 : : }
1735 : : }
1736 : :
1737 : 5470070 : return node;
1738 : : }
1739 : :
1740 : : static GSequenceNode *
1741 : 35431 : node_find (GSequenceNode *haystack,
1742 : : GSequenceNode *needle,
1743 : : GSequenceNode *end,
1744 : : GSequenceIterCompareFunc iter_cmp,
1745 : : gpointer cmp_data)
1746 : : {
1747 : : gint c;
1748 : :
1749 : 35431 : haystack = find_root (haystack);
1750 : :
1751 : : do
1752 : : {
1753 : : /* iter_cmp can't be passed the end node, since the function may
1754 : : * be user-supplied
1755 : : */
1756 [ + + ]: 162983 : if (haystack == end)
1757 : 6988 : c = 1;
1758 : : else
1759 : 155995 : c = iter_cmp (haystack, needle, cmp_data);
1760 : :
1761 [ + + ]: 162983 : if (c == 0)
1762 : 35431 : break;
1763 : :
1764 [ + + ]: 127552 : if (c > 0)
1765 : 67149 : haystack = haystack->left;
1766 : : else
1767 : 60403 : haystack = haystack->right;
1768 : : }
1769 [ + - ]: 127552 : while (haystack != NULL);
1770 : :
1771 : 35431 : return haystack;
1772 : : }
1773 : :
1774 : : static GSequenceNode *
1775 : 7641050 : node_find_closest (GSequenceNode *haystack,
1776 : : GSequenceNode *needle,
1777 : : GSequenceNode *end,
1778 : : GSequenceIterCompareFunc iter_cmp,
1779 : : gpointer cmp_data)
1780 : : {
1781 : : GSequenceNode *best;
1782 : : gint c;
1783 : :
1784 : 7641050 : haystack = find_root (haystack);
1785 : :
1786 : : do
1787 : : {
1788 : 42263244 : best = haystack;
1789 : :
1790 : : /* iter_cmp can't be passed the end node, since the function may
1791 : : * be user-supplied
1792 : : */
1793 [ + + ]: 42263244 : if (haystack == end)
1794 : 4811605 : c = 1;
1795 : : else
1796 : 37451639 : c = iter_cmp (haystack, needle, cmp_data);
1797 : :
1798 : : /* In the following we don't break even if c == 0. Instead we go on
1799 : : * searching along the 'bigger' nodes, so that we find the last one
1800 : : * that is equal to the needle.
1801 : : */
1802 [ + + ]: 42263244 : if (c > 0)
1803 : 15197372 : haystack = haystack->left;
1804 : : else
1805 : 27065872 : haystack = haystack->right;
1806 : : }
1807 [ + + ]: 42263244 : while (haystack != NULL);
1808 : :
1809 : : /* If the best node is smaller or equal to the data, then move one step
1810 : : * to the right to make sure the best one is strictly bigger than the data
1811 : : */
1812 [ + + + + ]: 7641050 : if (best != end && c <= 0)
1813 : 3653810 : best = node_get_next (best);
1814 : :
1815 : 7641050 : return best;
1816 : : }
1817 : :
1818 : : static gint
1819 : 13014625 : node_get_length (GSequenceNode *node)
1820 : : {
1821 : 13014625 : node = find_root (node);
1822 : :
1823 : 13014625 : return node->n_nodes;
1824 : : }
1825 : :
1826 : : static void
1827 : 12734968 : real_node_free (GSequenceNode *node,
1828 : : GSequence *seq)
1829 : : {
1830 [ + + ]: 12734968 : if (node)
1831 : : {
1832 : 5014813 : real_node_free (node->left, seq);
1833 : 5014813 : real_node_free (node->right, seq);
1834 : :
1835 [ + + + + : 5014813 : if (seq && seq->data_destroy_notify && node != seq->end_node)
+ + ]
1836 : 2349945 : seq->data_destroy_notify (node->data);
1837 : :
1838 : 5014813 : g_slice_free (GSequenceNode, node);
1839 : : }
1840 : 12734968 : }
1841 : :
1842 : : static void
1843 : 2705342 : node_free (GSequenceNode *node,
1844 : : GSequence *seq)
1845 : : {
1846 : 2705342 : node = find_root (node);
1847 : :
1848 : 2705342 : real_node_free (node, seq);
1849 : 2705342 : }
1850 : :
1851 : : static void
1852 : 131486480 : node_update_fields (GSequenceNode *node)
1853 : : {
1854 : 131486480 : int n_nodes = 1;
1855 : :
1856 [ + + ]: 131486480 : n_nodes += N_NODES (node->left);
1857 [ + + ]: 131486480 : n_nodes += N_NODES (node->right);
1858 : :
1859 : 131486480 : node->n_nodes = n_nodes;
1860 : 131486480 : }
1861 : :
1862 : : static void
1863 : 24320287 : node_rotate (GSequenceNode *node)
1864 : : {
1865 : : GSequenceNode *tmp, *old;
1866 : :
1867 : 24320287 : g_assert (node->parent);
1868 : 24320287 : g_assert (node->parent != node);
1869 : :
1870 [ + - + + ]: 24320287 : if (NODE_LEFT_CHILD (node))
1871 : : {
1872 : : /* rotate right */
1873 : 12256228 : tmp = node->right;
1874 : :
1875 : 12256228 : node->right = node->parent;
1876 : 12256228 : node->parent = node->parent->parent;
1877 [ + + ]: 12256228 : if (node->parent)
1878 : : {
1879 [ + + ]: 10551479 : if (node->parent->left == node->right)
1880 : 4461431 : node->parent->left = node;
1881 : : else
1882 : 6090048 : node->parent->right = node;
1883 : : }
1884 : :
1885 : 12256228 : g_assert (node->right);
1886 : :
1887 : 12256228 : node->right->parent = node;
1888 : 12256228 : node->right->left = tmp;
1889 : :
1890 [ + + ]: 12256228 : if (node->right->left)
1891 : 4740678 : node->right->left->parent = node->right;
1892 : :
1893 : 12256228 : old = node->right;
1894 : : }
1895 : : else
1896 : : {
1897 : : /* rotate left */
1898 : 12064059 : tmp = node->left;
1899 : :
1900 : 12064059 : node->left = node->parent;
1901 : 12064059 : node->parent = node->parent->parent;
1902 [ + + ]: 12064059 : if (node->parent)
1903 : : {
1904 [ + + ]: 9880884 : if (node->parent->right == node->left)
1905 : 3311929 : node->parent->right = node;
1906 : : else
1907 : 6568955 : node->parent->left = node;
1908 : : }
1909 : :
1910 : 12064059 : g_assert (node->left);
1911 : :
1912 : 12064059 : node->left->parent = node;
1913 : 12064059 : node->left->right = tmp;
1914 : :
1915 [ + + ]: 12064059 : if (node->left->right)
1916 : 5939032 : node->left->right->parent = node->left;
1917 : :
1918 : 12064059 : old = node->left;
1919 : : }
1920 : :
1921 : 24320287 : node_update_fields (old);
1922 : 24320287 : node_update_fields (node);
1923 : 24320287 : }
1924 : :
1925 : : static void
1926 : 101328216 : node_update_fields_deep (GSequenceNode *node)
1927 : : {
1928 [ + + ]: 101328216 : if (node)
1929 : : {
1930 : 81937681 : node_update_fields (node);
1931 : :
1932 : 81937681 : node_update_fields_deep (node->parent);
1933 : : }
1934 : 101328216 : }
1935 : :
1936 : : static void
1937 : 20052577 : rotate_down (GSequenceNode *node,
1938 : : guint priority)
1939 : : {
1940 : : guint left, right;
1941 : :
1942 [ + + ]: 20052577 : left = node->left ? get_priority (node->left) : 0;
1943 [ + + ]: 20052577 : right = node->right ? get_priority (node->right) : 0;
1944 : :
1945 [ + + + + ]: 32881522 : while (priority < left || priority < right)
1946 : : {
1947 [ + + ]: 12828945 : if (left > right)
1948 : 4824007 : node_rotate (node->left);
1949 : : else
1950 : 8004938 : node_rotate (node->right);
1951 : :
1952 [ + + ]: 12828945 : left = node->left ? get_priority (node->left) : 0;
1953 [ + + ]: 12828945 : right = node->right ? get_priority (node->right) : 0;
1954 : : }
1955 : 20052577 : }
1956 : :
1957 : : static void
1958 : 662042 : node_cut (GSequenceNode *node)
1959 : : {
1960 [ + + ]: 1931100 : while (node->parent)
1961 : 1269058 : node_rotate (node);
1962 : :
1963 [ + + ]: 662042 : if (node->left)
1964 : 334186 : node->left->parent = NULL;
1965 : :
1966 : 662042 : node->left = NULL;
1967 : 662042 : node_update_fields (node);
1968 : :
1969 : 662042 : rotate_down (node, get_priority (node));
1970 : 662042 : }
1971 : :
1972 : : static void
1973 : 246183 : node_join (GSequenceNode *left,
1974 : : GSequenceNode *right)
1975 : : {
1976 : 246183 : GSequenceNode *fake = node_new (NULL);
1977 : :
1978 : 246183 : fake->left = find_root (left);
1979 : 246183 : fake->right = find_root (right);
1980 : 246183 : fake->left->parent = fake;
1981 : 246183 : fake->right->parent = fake;
1982 : :
1983 : 246183 : node_update_fields (fake);
1984 : :
1985 : 246183 : node_unlink (fake);
1986 : :
1987 : 246183 : node_free (fake, NULL);
1988 : 246183 : }
1989 : :
1990 : : static void
1991 : 10770914 : node_insert_before (GSequenceNode *node,
1992 : : GSequenceNode *new)
1993 : : {
1994 : 10770914 : new->left = node->left;
1995 [ + + ]: 10770914 : if (new->left)
1996 : 4116683 : new->left->parent = new;
1997 : :
1998 : 10770914 : new->parent = node;
1999 : 10770914 : node->left = new;
2000 : :
2001 : 10770914 : node_update_fields_deep (new);
2002 : :
2003 [ + + + + ]: 20993198 : while (new->parent && get_priority (new) > get_priority (new->parent))
2004 : 10222284 : node_rotate (new);
2005 : :
2006 : 10770914 : rotate_down (new, get_priority (new));
2007 : 10770914 : }
2008 : :
2009 : : static void
2010 : 8619621 : node_unlink (GSequenceNode *node)
2011 : : {
2012 : 8619621 : rotate_down (node, 0);
2013 : :
2014 [ + - + + ]: 8619621 : if (NODE_RIGHT_CHILD (node))
2015 : 482463 : node->parent->right = NULL;
2016 [ + - + - ]: 8137158 : else if (NODE_LEFT_CHILD (node))
2017 : 8137158 : node->parent->left = NULL;
2018 : :
2019 [ + - ]: 8619621 : if (node->parent)
2020 : 8619621 : node_update_fields_deep (node->parent);
2021 : :
2022 : 8619621 : node->parent = NULL;
2023 : 8619621 : }
2024 : :
2025 : : static void
2026 : 7605298 : node_insert_sorted (GSequenceNode *node,
2027 : : GSequenceNode *new,
2028 : : GSequenceNode *end,
2029 : : GSequenceIterCompareFunc iter_cmp,
2030 : : gpointer cmp_data)
2031 : : {
2032 : : GSequenceNode *closest;
2033 : :
2034 : 7605298 : closest = node_find_closest (node, new, end, iter_cmp, cmp_data);
2035 : :
2036 : 7605298 : node_unlink (new);
2037 : :
2038 : 7605298 : node_insert_before (closest, new);
2039 : 7605298 : }
|
