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 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, write to the
17 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 * Boston, MA 02111-1307, USA.
19 */
20
21 #include <glib.h>
22 #include "gsequence.h"
23
24 typedef struct _GSequenceNode GSequenceNode;
25
26 struct _GSequence
27 {
28 GSequenceNode * end_node;
29 GDestroyNotify data_destroy_notify;
30 gboolean access_prohibited;
31
32 /* The 'real_sequence' is used when temporary sequences are created
33 * to hold nodes that are being rearranged. The 'real_sequence' of such
34 * a temporary sequence points to the sequence that is actually being
35 * manipulated. The only reason we need this is so that when the
36 * sort/sort_changed/search_iter() functions call out to the application
37 * g_sequence_iter_get_sequence() will return the correct sequence.
38 */
39 GSequence * real_sequence;
40 };
41
42 struct _GSequenceNode
43 {
44 gint n_nodes;
45 GSequenceNode * parent;
46 GSequenceNode * left;
47 GSequenceNode * right;
48 gpointer data; /* For the end node, this field points
49 * to the sequence
50 */
51 };
52
53 /*
54 * Declaration of GSequenceNode methods
55 */
56 static GSequenceNode *node_new (gpointer data);
57 static GSequenceNode *node_get_first (GSequenceNode *node);
58 static GSequenceNode *node_get_last (GSequenceNode *node);
59 static GSequenceNode *node_get_prev (GSequenceNode *node);
60 static GSequenceNode *node_get_next (GSequenceNode *node);
61 static gint node_get_pos (GSequenceNode *node);
62 static GSequenceNode *node_get_by_pos (GSequenceNode *node,
63 gint pos);
64 static GSequenceNode *node_find_closest (GSequenceNode *haystack,
65 GSequenceNode *needle,
66 GSequenceNode *end,
67 GSequenceIterCompareFunc cmp,
68 gpointer user_data);
69 static gint node_get_length (GSequenceNode *node);
70 static void node_free (GSequenceNode *node,
71 GSequence *seq);
72 static void node_cut (GSequenceNode *split);
73 static void node_insert_before (GSequenceNode *node,
74 GSequenceNode *new);
75 static void node_unlink (GSequenceNode *node);
76 static void node_join (GSequenceNode *left,
77 GSequenceNode *right);
78 static void node_insert_sorted (GSequenceNode *node,
79 GSequenceNode *new,
80 GSequenceNode *end,
81 GSequenceIterCompareFunc cmp_func,
82 gpointer cmp_data);
83
84
85 /*
86 * Various helper functions
87 */
88 static void
check_seq_access(GSequence * seq)89 check_seq_access (GSequence *seq)
90 {
91 if (G_UNLIKELY (seq->access_prohibited))
92 {
93 g_warning ("Accessing a sequence while it is "
94 "being sorted or searched is not allowed");
95 }
96 }
97
98 static GSequence *
get_sequence(GSequenceNode * node)99 get_sequence (GSequenceNode *node)
100 {
101 return (GSequence *)node_get_last (node)->data;
102 }
103
104 static void
check_iter_access(GSequenceIter * iter)105 check_iter_access (GSequenceIter *iter)
106 {
107 check_seq_access (get_sequence (iter));
108 }
109
110 static gboolean
is_end(GSequenceIter * iter)111 is_end (GSequenceIter *iter)
112 {
113 GSequence *seq;
114
115 if (iter->right)
116 return FALSE;
117
118 if (!iter->parent)
119 return TRUE;
120
121 if (iter->parent->right != iter)
122 return FALSE;
123
124 seq = get_sequence (iter);
125
126 return seq->end_node == iter;
127 }
128
129 typedef struct
130 {
131 GCompareDataFunc cmp_func;
132 gpointer cmp_data;
133 GSequenceNode *end_node;
134 } SortInfo;
135
136 /* This function compares two iters using a normal compare
137 * function and user_data passed in in a SortInfo struct
138 */
139 static gint
iter_compare(GSequenceIter * node1,GSequenceIter * node2,gpointer data)140 iter_compare (GSequenceIter *node1,
141 GSequenceIter *node2,
142 gpointer data)
143 {
144 const SortInfo *info = data;
145 gint retval;
146
147 if (node1 == info->end_node)
148 return 1;
149
150 if (node2 == info->end_node)
151 return -1;
152
153 retval = info->cmp_func (node1->data, node2->data, info->cmp_data);
154
155 return retval;
156 }
157
158 /*
159 * Public API
160 */
161
162 /**
163 * g_sequence_new:
164 * @data_destroy: a #GDestroyNotify function, or %NULL
165 *
166 * Creates a new GSequence. The @data_destroy function, if non-%NULL will
167 * be called on all items when the sequence is destroyed and on items that
168 * are removed from the sequence.
169 *
170 * Return value: a new #GSequence
171 *
172 * Since: 2.14
173 **/
174 GSequence *
g_sequence_new(GDestroyNotify data_destroy)175 g_sequence_new (GDestroyNotify data_destroy)
176 {
177 GSequence *seq = g_new (GSequence, 1);
178 seq->data_destroy_notify = data_destroy;
179
180 seq->end_node = node_new (seq);
181
182 seq->access_prohibited = FALSE;
183
184 seq->real_sequence = seq;
185
186 return seq;
187 }
188
189 /**
190 * g_sequence_free:
191 * @seq: a #GSequence
192 *
193 * Frees the memory allocated for @seq. If @seq has a data destroy
194 * function associated with it, that function is called on all items in
195 * @seq.
196 *
197 * Since: 2.14
198 **/
199 void
g_sequence_free(GSequence * seq)200 g_sequence_free (GSequence *seq)
201 {
202 g_return_if_fail (seq != NULL);
203
204 check_seq_access (seq);
205
206 node_free (seq->end_node, seq);
207
208 g_free (seq);
209 }
210
211 /**
212 * g_sequence_foreach_range:
213 * @begin: a #GSequenceIter
214 * @end: a #GSequenceIter
215 * @func: a #GFunc
216 * @user_data: user data passed to @func
217 *
218 * Calls @func for each item in the range (@begin, @end) passing
219 * @user_data to the function.
220 *
221 * Since: 2.14
222 **/
223 void
g_sequence_foreach_range(GSequenceIter * begin,GSequenceIter * end,GFunc func,gpointer user_data)224 g_sequence_foreach_range (GSequenceIter *begin,
225 GSequenceIter *end,
226 GFunc func,
227 gpointer user_data)
228 {
229 GSequence *seq;
230 GSequenceIter *iter;
231
232 g_return_if_fail (func != NULL);
233 g_return_if_fail (begin != NULL);
234 g_return_if_fail (end != NULL);
235
236 seq = get_sequence (begin);
237
238 seq->access_prohibited = TRUE;
239
240 iter = begin;
241 while (iter != end)
242 {
243 GSequenceIter *next = node_get_next (iter);
244
245 func (iter->data, user_data);
246
247 iter = next;
248 }
249
250 seq->access_prohibited = FALSE;
251 }
252
253 /**
254 * g_sequence_foreach:
255 * @seq: a #GSequence
256 * @func: the function to call for each item in @seq
257 * @user_data: user data passed to @func
258 *
259 * Calls @func for each item in the sequence passing @user_data
260 * to the function.
261 *
262 * Since: 2.14
263 **/
264 void
g_sequence_foreach(GSequence * seq,GFunc func,gpointer user_data)265 g_sequence_foreach (GSequence *seq,
266 GFunc func,
267 gpointer user_data)
268 {
269 GSequenceIter *begin, *end;
270
271 check_seq_access (seq);
272
273 begin = g_sequence_get_begin_iter (seq);
274 end = g_sequence_get_end_iter (seq);
275
276 g_sequence_foreach_range (begin, end, func, user_data);
277 }
278
279 /**
280 * g_sequence_range_get_midpoint:
281 * @begin: a #GSequenceIter
282 * @end: a #GSequenceIter
283 *
284 * Finds an iterator somewhere in the range (@begin, @end). This
285 * iterator will be close to the middle of the range, but is not
286 * guaranteed to be <emphasis>exactly</emphasis> in the middle.
287 *
288 * The @begin and @end iterators must both point to the same sequence and
289 * @begin must come before or be equal to @end in the sequence.
290 *
291 * Return value: A #GSequenceIter pointing somewhere in the
292 * (@begin, @end) range.
293 *
294 * Since: 2.14
295 **/
296 GSequenceIter *
g_sequence_range_get_midpoint(GSequenceIter * begin,GSequenceIter * end)297 g_sequence_range_get_midpoint (GSequenceIter *begin,
298 GSequenceIter *end)
299 {
300 int begin_pos, end_pos, mid_pos;
301
302 g_return_val_if_fail (begin != NULL, NULL);
303 g_return_val_if_fail (end != NULL, NULL);
304 g_return_val_if_fail (get_sequence (begin) == get_sequence (end), NULL);
305
306 begin_pos = node_get_pos (begin);
307 end_pos = node_get_pos (end);
308
309 g_return_val_if_fail (end_pos >= begin_pos, NULL);
310
311 mid_pos = begin_pos + (end_pos - begin_pos) / 2;
312
313 return node_get_by_pos (begin, mid_pos);
314 }
315
316 /**
317 * g_sequence_iter_compare:
318 * @a: a #GSequenceIter
319 * @b: a #GSequenceIter
320 *
321 * Returns a negative number if @a comes before @b, 0 if they are equal,
322 * and a positive number if @a comes after @b.
323 *
324 * The @a and @b iterators must point into the same sequence.
325 *
326 * Return value: A negative number if @a comes before @b, 0 if they are
327 * equal, and a positive number if @a comes after @b.
328 *
329 * Since: 2.14
330 **/
331 gint
g_sequence_iter_compare(GSequenceIter * a,GSequenceIter * b)332 g_sequence_iter_compare (GSequenceIter *a,
333 GSequenceIter *b)
334 {
335 gint a_pos, b_pos;
336
337 g_return_val_if_fail (a != NULL, 0);
338 g_return_val_if_fail (b != NULL, 0);
339 g_return_val_if_fail (get_sequence (a) == get_sequence (b), 0);
340
341 check_iter_access (a);
342 check_iter_access (b);
343
344 a_pos = node_get_pos (a);
345 b_pos = node_get_pos (b);
346
347 if (a_pos == b_pos)
348 return 0;
349 else if (a_pos > b_pos)
350 return 1;
351 else
352 return -1;
353 }
354
355 /**
356 * g_sequence_append:
357 * @seq: a #GSequencePointer
358 * @data: the data for the new item
359 *
360 * Adds a new item to the end of @seq.
361 *
362 * Return value: an iterator pointing to the new item
363 *
364 * Since: 2.14
365 **/
366 GSequenceIter *
g_sequence_append(GSequence * seq,gpointer data)367 g_sequence_append (GSequence *seq,
368 gpointer data)
369 {
370 GSequenceNode *node;
371
372 g_return_val_if_fail (seq != NULL, NULL);
373
374 check_seq_access (seq);
375
376 node = node_new (data);
377 node_insert_before (seq->end_node, node);
378
379 return node;
380 }
381
382 /**
383 * g_sequence_prepend:
384 * @seq: a #GSequence
385 * @data: the data for the new item
386 *
387 * Adds a new item to the front of @seq
388 *
389 * Return value: an iterator pointing to the new item
390 *
391 * Since: 2.14
392 **/
393 GSequenceIter *
g_sequence_prepend(GSequence * seq,gpointer data)394 g_sequence_prepend (GSequence *seq,
395 gpointer data)
396 {
397 GSequenceNode *node, *first;
398
399 g_return_val_if_fail (seq != NULL, NULL);
400
401 check_seq_access (seq);
402
403 node = node_new (data);
404 first = node_get_first (seq->end_node);
405
406 node_insert_before (first, node);
407
408 return node;
409 }
410
411 /**
412 * g_sequence_insert_before:
413 * @iter: a #GSequenceIter
414 * @data: the data for the new item
415 *
416 * Inserts a new item just before the item pointed to by @iter.
417 *
418 * Return value: an iterator pointing to the new item
419 *
420 * Since: 2.14
421 **/
422 GSequenceIter *
g_sequence_insert_before(GSequenceIter * iter,gpointer data)423 g_sequence_insert_before (GSequenceIter *iter,
424 gpointer data)
425 {
426 GSequenceNode *node;
427
428 g_return_val_if_fail (iter != NULL, NULL);
429
430 check_iter_access (iter);
431
432 node = node_new (data);
433
434 node_insert_before (iter, node);
435
436 return node;
437 }
438
439 /**
440 * g_sequence_remove:
441 * @iter: a #GSequenceIter
442 *
443 * Removes the item pointed to by @iter. It is an error to pass the
444 * end iterator to this function.
445 *
446 * If the sequnce has a data destroy function associated with it, this
447 * function is called on the data for the removed item.
448 *
449 * Since: 2.14
450 **/
451 void
g_sequence_remove(GSequenceIter * iter)452 g_sequence_remove (GSequenceIter *iter)
453 {
454 GSequence *seq;
455
456 g_return_if_fail (iter != NULL);
457 g_return_if_fail (!is_end (iter));
458
459 check_iter_access (iter);
460
461 seq = get_sequence (iter);
462
463 node_unlink (iter);
464 node_free (iter, seq);
465 }
466
467 /**
468 * g_sequence_remove_range:
469 * @begin: a #GSequenceIter
470 * @end: a #GSequenceIter
471 *
472 * Removes all items in the (@begin, @end) range.
473 *
474 * If the sequence has a data destroy function associated with it, this
475 * function is called on the data for the removed items.
476 *
477 * Since: 2.14
478 **/
479 void
g_sequence_remove_range(GSequenceIter * begin,GSequenceIter * end)480 g_sequence_remove_range (GSequenceIter *begin,
481 GSequenceIter *end)
482 {
483 g_return_if_fail (get_sequence (begin) == get_sequence (end));
484
485 check_iter_access (begin);
486 check_iter_access (end);
487
488 g_sequence_move_range (NULL, begin, end);
489 }
490
491 /**
492 * g_sequence_move_range:
493 * @dest: a #GSequenceIter
494 * @begin: a #GSequenceIter
495 * @end: a #GSequenceIter
496 *
497 * Inserts the (@begin, @end) range at the destination pointed to by ptr.
498 * The @begin and @end iters must point into the same sequence. It is
499 * allowed for @dest to point to a different sequence than the one pointed
500 * into by @begin and @end.
501 *
502 * If @dest is NULL, the range indicated by @begin and @end is
503 * removed from the sequence. If @dest iter points to a place within
504 * the (@begin, @end) range, the range does not move.
505 *
506 * Since: 2.14
507 **/
508 void
g_sequence_move_range(GSequenceIter * dest,GSequenceIter * begin,GSequenceIter * end)509 g_sequence_move_range (GSequenceIter *dest,
510 GSequenceIter *begin,
511 GSequenceIter *end)
512 {
513 GSequence *src_seq;
514 GSequenceNode *first;
515
516 g_return_if_fail (begin != NULL);
517 g_return_if_fail (end != NULL);
518
519 check_iter_access (begin);
520 check_iter_access (end);
521 if (dest)
522 check_iter_access (dest);
523
524 src_seq = get_sequence (begin);
525
526 g_return_if_fail (src_seq == get_sequence (end));
527
528 /* Dest points to begin or end? */
529 if (dest == begin || dest == end)
530 return;
531
532 /* begin comes after end? */
533 if (g_sequence_iter_compare (begin, end) >= 0)
534 return;
535
536 /* dest points somewhere in the (begin, end) range? */
537 if (dest && get_sequence (dest) == src_seq &&
538 g_sequence_iter_compare (dest, begin) > 0 &&
539 g_sequence_iter_compare (dest, end) < 0)
540 {
541 return;
542 }
543
544 src_seq = get_sequence (begin);
545
546 first = node_get_first (begin);
547
548 node_cut (begin);
549
550 node_cut (end);
551
552 if (first != begin)
553 node_join (first, end);
554
555 if (dest)
556 {
557 first = node_get_first (dest);
558
559 node_cut (dest);
560
561 node_join (begin, dest);
562
563 if (dest != first)
564 node_join (first, begin);
565 }
566 else
567 {
568 node_free (begin, src_seq);
569 }
570 }
571
572 /**
573 * g_sequence_sort:
574 * @seq: a #GSequence
575 * @cmp_func: the #GCompareDataFunc used to sort @seq. This function is
576 * passed two items of @seq and should return 0 if they are equal,
577 * a negative value fi the first comes before the second, and a
578 * positive value if the second comes before the first.
579 * @cmp_data: user data passed to @cmp_func
580 *
581 * Sorts @seq using @cmp_func.
582 *
583 * Since: 2.14
584 **/
585 void
g_sequence_sort(GSequence * seq,GCompareDataFunc cmp_func,gpointer cmp_data)586 g_sequence_sort (GSequence *seq,
587 GCompareDataFunc cmp_func,
588 gpointer cmp_data)
589 {
590 SortInfo info = { cmp_func, cmp_data, seq->end_node };
591
592 check_seq_access (seq);
593
594 g_sequence_sort_iter (seq, iter_compare, &info);
595 }
596
597 /**
598 * g_sequence_insert_sorted:
599 * @seq: a #GSequence
600 * @data: the data to insert
601 * @cmp_func: the #GCompareDataFunc used to compare items in the sequence. It
602 * is called with two items of the @seq and @user_data. It should
603 * return 0 if the items are equal, a negative value if the first
604 * item comes before the second, and a positive value if the second
605 * item comes before the first.
606 * @cmp_data: user data passed to @cmp_func.
607 *
608 * Inserts @data into @sequence using @func to determine the new position.
609 * The sequence must already be sorted according to @cmp_func; otherwise the
610 * new position of @data is undefined.
611 *
612 * Return value: a #GSequenceIter pointing to the new item.
613 *
614 * Since: 2.14
615 **/
616 GSequenceIter *
g_sequence_insert_sorted(GSequence * seq,gpointer data,GCompareDataFunc cmp_func,gpointer cmp_data)617 g_sequence_insert_sorted (GSequence *seq,
618 gpointer data,
619 GCompareDataFunc cmp_func,
620 gpointer cmp_data)
621 {
622 SortInfo info = { cmp_func, cmp_data, NULL };
623
624 g_return_val_if_fail (seq != NULL, NULL);
625 g_return_val_if_fail (cmp_func != NULL, NULL);
626
627 info.end_node = seq->end_node;
628 check_seq_access (seq);
629
630 return g_sequence_insert_sorted_iter (seq, data, iter_compare, &info);
631 }
632
633 /**
634 * g_sequence_sort_changed:
635 * @iter: A #GSequenceIter
636 * @cmp_func: the #GCompareDataFunc used to compare items in the sequence. It
637 * is called with two items of the @seq and @user_data. It should
638 * return 0 if the items are equal, a negative value if the first
639 * item comes before the second, and a positive value if the second
640 * item comes before the first.
641 * @cmp_data: user data passed to @cmp_func.
642 *
643 * Moves the data pointed to a new position as indicated by @cmp_func. This
644 * function should be called for items in a sequence already sorted according
645 * to @cmp_func whenever some aspect of an item changes so that @cmp_func
646 * may return different values for that item.
647 *
648 * Since: 2.14
649 **/
650 void
g_sequence_sort_changed(GSequenceIter * iter,GCompareDataFunc cmp_func,gpointer cmp_data)651 g_sequence_sort_changed (GSequenceIter *iter,
652 GCompareDataFunc cmp_func,
653 gpointer cmp_data)
654 {
655 SortInfo info = { cmp_func, cmp_data, NULL };
656
657 g_return_if_fail (!is_end (iter));
658
659 info.end_node = get_sequence (iter)->end_node;
660 check_iter_access (iter);
661
662 g_sequence_sort_changed_iter (iter, iter_compare, &info);
663 }
664
665 /**
666 * g_sequence_search:
667 * @seq: a #GSequence
668 * @data: data for the new item
669 * @cmp_func: the #GCompareDataFunc used to compare items in the sequence. It
670 * is called with two items of the @seq and @user_data. It should
671 * return 0 if the items are equal, a negative value if the first
672 * item comes before the second, and a positive value if the second
673 * item comes before the first.
674 * @cmp_data: user data passed to @cmp_func.
675 *
676 * Returns an iterator pointing to the position where @data would
677 * be inserted according to @cmp_func and @cmp_data.
678 *
679 * Return value: an #GSequenceIter pointing to the position where @data
680 * would have been inserted according to @cmp_func and @cmp_data.
681 *
682 * Since: 2.14
683 **/
684 GSequenceIter *
g_sequence_search(GSequence * seq,gpointer data,GCompareDataFunc cmp_func,gpointer cmp_data)685 g_sequence_search (GSequence *seq,
686 gpointer data,
687 GCompareDataFunc cmp_func,
688 gpointer cmp_data)
689 {
690 SortInfo info = { cmp_func, cmp_data, NULL };
691
692 g_return_val_if_fail (seq != NULL, NULL);
693
694 info.end_node = seq->end_node;
695 check_seq_access (seq);
696
697 return g_sequence_search_iter (seq, data, iter_compare, &info);
698 }
699
700 /**
701 * g_sequence_sort_iter:
702 * @seq: a #GSequence
703 * @cmp_func: the #GSequenceItercompare used to compare iterators in the
704 * sequence. It is called with two iterators pointing into @seq. It should
705 * return 0 if the iterators are equal, a negative value if the first
706 * iterator comes before the second, and a positive value if the second
707 * iterator comes before the first.
708 * @cmp_data: user data passed to @cmp_func
709 *
710 * Like g_sequence_sort(), but uses a #GSequenceIterCompareFunc instead
711 * of a GCompareDataFunc as the compare function
712 *
713 * Since: 2.14
714 **/
715 void
g_sequence_sort_iter(GSequence * seq,GSequenceIterCompareFunc cmp_func,gpointer cmp_data)716 g_sequence_sort_iter (GSequence *seq,
717 GSequenceIterCompareFunc cmp_func,
718 gpointer cmp_data)
719 {
720 GSequence *tmp;
721 GSequenceNode *begin, *end;
722
723 g_return_if_fail (seq != NULL);
724 g_return_if_fail (cmp_func != NULL);
725
726 check_seq_access (seq);
727
728 begin = g_sequence_get_begin_iter (seq);
729 end = g_sequence_get_end_iter (seq);
730
731 tmp = g_sequence_new (NULL);
732 tmp->real_sequence = seq;
733
734 g_sequence_move_range (g_sequence_get_begin_iter (tmp), begin, end);
735
736 seq->access_prohibited = TRUE;
737 tmp->access_prohibited = TRUE;
738
739 while (g_sequence_get_length (tmp) > 0)
740 {
741 GSequenceNode *node = g_sequence_get_begin_iter (tmp);
742
743 node_insert_sorted (seq->end_node, node, seq->end_node,
744 cmp_func, cmp_data);
745 }
746
747 tmp->access_prohibited = FALSE;
748 seq->access_prohibited = FALSE;
749
750 g_sequence_free (tmp);
751 }
752
753 /**
754 * g_sequence_sort_changed_iter:
755 * @iter: a #GSequenceIter
756 * @iter_cmp: the #GSequenceItercompare used to compare iterators in the
757 * sequence. It is called with two iterators pointing into @seq. It should
758 * return 0 if the iterators are equal, a negative value if the first
759 * iterator comes before the second, and a positive value if the second
760 * iterator comes before the first.
761 * @cmp_data: user data passed to @cmp_func
762 *
763 * Like g_sequence_sort_changed(), but uses
764 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
765 * the compare function.
766 *
767 * Since: 2.14
768 **/
769 void
g_sequence_sort_changed_iter(GSequenceIter * iter,GSequenceIterCompareFunc iter_cmp,gpointer cmp_data)770 g_sequence_sort_changed_iter (GSequenceIter *iter,
771 GSequenceIterCompareFunc iter_cmp,
772 gpointer cmp_data)
773 {
774 GSequence *seq, *tmp_seq;
775 GSequenceIter *next, *prev;
776
777 g_return_if_fail (iter != NULL);
778 g_return_if_fail (!is_end (iter));
779 g_return_if_fail (iter_cmp != NULL);
780 check_iter_access (iter);
781
782 /* If one of the neighbours is equal to iter, then
783 * don't move it. This ensures that sort_changed() is
784 * a stable operation.
785 */
786
787 next = node_get_next (iter);
788 prev = node_get_prev (iter);
789
790 if (prev != iter && iter_cmp (prev, iter, cmp_data) == 0)
791 return;
792
793 if (!is_end (next) && iter_cmp (next, iter, cmp_data) == 0)
794 return;
795
796 seq = get_sequence (iter);
797
798 seq->access_prohibited = TRUE;
799
800 tmp_seq = g_sequence_new (NULL);
801 tmp_seq->real_sequence = seq;
802
803 node_unlink (iter);
804 node_insert_before (tmp_seq->end_node, iter);
805
806 node_insert_sorted (seq->end_node, iter, seq->end_node,
807 iter_cmp, cmp_data);
808
809 g_sequence_free (tmp_seq);
810
811 seq->access_prohibited = FALSE;
812 }
813
814 /**
815 * g_sequence_insert_sorted_iter:
816 * @seq: a #GSequence
817 * @data: data for the new item
818 * @iter_cmp: the #GSequenceItercompare used to compare iterators in the
819 * sequence. It is called with two iterators pointing into @seq. It should
820 * return 0 if the iterators are equal, a negative value if the first
821 * iterator comes before the second, and a positive value if the second
822 * iterator comes before the first.
823 * @cmp_data: user data passed to @cmp_func
824 *
825 * Like g_sequence_insert_sorted(), but uses
826 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
827 * the compare function.
828 *
829 * Return value: a #GSequenceIter pointing to the new item
830 *
831 * Since: 2.14
832 **/
833 GSequenceIter *
g_sequence_insert_sorted_iter(GSequence * seq,gpointer data,GSequenceIterCompareFunc iter_cmp,gpointer cmp_data)834 g_sequence_insert_sorted_iter (GSequence *seq,
835 gpointer data,
836 GSequenceIterCompareFunc iter_cmp,
837 gpointer cmp_data)
838 {
839 GSequenceNode *new_node;
840 GSequence *tmp_seq;
841
842 g_return_val_if_fail (seq != NULL, NULL);
843 g_return_val_if_fail (iter_cmp != NULL, NULL);
844
845 check_seq_access (seq);
846
847 seq->access_prohibited = TRUE;
848
849 /* Create a new temporary sequence and put the new node into
850 * that. The reason for this is that the user compare function
851 * will be called with the new node, and if it dereferences,
852 * "is_end" will be called on it. But that will crash if the
853 * node is not actually in a sequence.
854 *
855 * node_insert_sorted() makes sure the node is unlinked before
856 * is is inserted.
857 *
858 * The reason we need the "iter" versions at all is that that
859 * is the only kind of compare functions GtkTreeView can use.
860 */
861 tmp_seq = g_sequence_new (NULL);
862 tmp_seq->real_sequence = seq;
863
864 new_node = g_sequence_append (tmp_seq, data);
865
866 node_insert_sorted (seq->end_node, new_node,
867 seq->end_node, iter_cmp, cmp_data);
868
869 g_sequence_free (tmp_seq);
870
871 seq->access_prohibited = FALSE;
872
873 return new_node;
874 }
875
876 /**
877 * g_sequence_search_iter:
878 * @seq: a #GSequence
879 * @data: data for the new item
880 * @iter_cmp: the #GSequenceIterCompare function used to compare iterators
881 * in the sequence. It is called with two iterators pointing into @seq.
882 * It should return 0 if the iterators are equal, a negative value if the
883 * first iterator comes before the second, and a positive value if the
884 * second iterator comes before the first.
885 * @cmp_data: user data passed to @iter_cmp
886 *
887 * Like g_sequence_search(), but uses
888 * a #GSequenceIterCompareFunc instead of a #GCompareDataFunc as
889 * the compare function.
890 *
891 * Return value: a #GSequenceIter pointing to the position in @seq
892 * where @data would have been inserted according to @iter_cmp and @cmp_data.
893 *
894 * Since: 2.14
895 **/
896 GSequenceIter *
g_sequence_search_iter(GSequence * seq,gpointer data,GSequenceIterCompareFunc iter_cmp,gpointer cmp_data)897 g_sequence_search_iter (GSequence *seq,
898 gpointer data,
899 GSequenceIterCompareFunc iter_cmp,
900 gpointer cmp_data)
901 {
902 GSequenceNode *node;
903 GSequenceNode *dummy;
904 GSequence *tmp_seq;
905
906 g_return_val_if_fail (seq != NULL, NULL);
907
908 check_seq_access (seq);
909
910 seq->access_prohibited = TRUE;
911
912 tmp_seq = g_sequence_new (NULL);
913 tmp_seq->real_sequence = seq;
914
915 dummy = g_sequence_append (tmp_seq, data);
916
917 node = node_find_closest (seq->end_node, dummy,
918 seq->end_node, iter_cmp, cmp_data);
919
920 g_sequence_free (tmp_seq);
921
922 seq->access_prohibited = FALSE;
923
924 return node;
925 }
926
927 /**
928 * g_sequence_iter_get_sequence:
929 * @iter: a #GSequenceIter
930 *
931 * Returns the #GSequence that @iter points into.
932 *
933 * Return value: the #GSequence that @iter points into.
934 *
935 * Since: 2.14
936 **/
937 GSequence *
g_sequence_iter_get_sequence(GSequenceIter * iter)938 g_sequence_iter_get_sequence (GSequenceIter *iter)
939 {
940 GSequence *seq;
941
942 g_return_val_if_fail (iter != NULL, NULL);
943
944 seq = get_sequence (iter);
945
946 /* For temporary sequences, this points to the sequence that
947 * is actually being manipulated
948 */
949 return seq->real_sequence;
950 }
951
952 /**
953 * g_sequence_get:
954 * @iter: a #GSequenceIter
955 *
956 * Returns the data that @iter points to.
957 *
958 * Return value: the data that @iter points to
959 *
960 * Since: 2.14
961 **/
962 gpointer
g_sequence_get(GSequenceIter * iter)963 g_sequence_get (GSequenceIter *iter)
964 {
965 g_return_val_if_fail (iter != NULL, NULL);
966 g_return_val_if_fail (!is_end (iter), NULL);
967
968 return iter->data;
969 }
970
971 /**
972 * g_sequence_set:
973 * @iter: a #GSequenceIter
974 * @data: new data for the item
975 *
976 * Changes the data for the item pointed to by @iter to be @data. If
977 * the sequence has a data destroy function associated with it, that
978 * function is called on the existing data that @iter pointed to.
979 *
980 * Since: 2.14
981 **/
982 void
g_sequence_set(GSequenceIter * iter,gpointer data)983 g_sequence_set (GSequenceIter *iter,
984 gpointer data)
985 {
986 GSequence *seq;
987
988 g_return_if_fail (iter != NULL);
989 g_return_if_fail (!is_end (iter));
990
991 seq = get_sequence (iter);
992
993 /* If @data is identical to iter->data, it is destroyed
994 * here. This will work right in case of ref-counted objects. Also
995 * it is similar to what ghashtables do.
996 *
997 * For non-refcounted data it's a little less convenient, but
998 * code relying on self-setting not destroying would be
999 * pretty dubious anyway ...
1000 */
1001
1002 if (seq->data_destroy_notify)
1003 seq->data_destroy_notify (iter->data);
1004
1005 iter->data = data;
1006 }
1007
1008 /**
1009 * g_sequence_get_length:
1010 * @seq: a #GSequence
1011 *
1012 * Returns the length of @seq
1013 *
1014 * Return value: the length of @seq
1015 *
1016 * Since: 2.14
1017 **/
1018 gint
g_sequence_get_length(GSequence * seq)1019 g_sequence_get_length (GSequence *seq)
1020 {
1021 return node_get_length (seq->end_node) - 1;
1022 }
1023
1024 /**
1025 * g_sequence_get_end_iter:
1026 * @seq: a #GSequence
1027 *
1028 * Returns the end iterator for @seg
1029 *
1030 * Return value: the end iterator for @seq
1031 *
1032 * Since: 2.14
1033 **/
1034 GSequenceIter *
g_sequence_get_end_iter(GSequence * seq)1035 g_sequence_get_end_iter (GSequence *seq)
1036 {
1037 g_return_val_if_fail (seq != NULL, NULL);
1038
1039 return seq->end_node;
1040 }
1041
1042 /**
1043 * g_sequence_get_begin_iter:
1044 * @seq: a #GSequence
1045 *
1046 * Returns the begin iterator for @seq.
1047 *
1048 * Return value: the begin iterator for @seq.
1049 *
1050 * Since: 2.14
1051 **/
1052 GSequenceIter *
g_sequence_get_begin_iter(GSequence * seq)1053 g_sequence_get_begin_iter (GSequence *seq)
1054 {
1055 g_return_val_if_fail (seq != NULL, NULL);
1056
1057 return node_get_first (seq->end_node);
1058 }
1059
1060 static int
clamp_position(GSequence * seq,int pos)1061 clamp_position (GSequence *seq,
1062 int pos)
1063 {
1064 gint len = g_sequence_get_length (seq);
1065
1066 if (pos > len || pos < 0)
1067 pos = len;
1068
1069 return pos;
1070 }
1071
1072 /*
1073 * if pos > number of items or -1, will return end pointer
1074 */
1075 /**
1076 * g_sequence_get_iter_at_pos:
1077 * @seq: a #GSequence
1078 * @pos: a position in @seq, or -1 for the end.
1079 *
1080 * Returns the iterator at position @pos. If @pos is negative or larger
1081 * than the number of items in @seq, the end iterator is returned.
1082 *
1083 * Return value: The #GSequenceIter at position @pos
1084 *
1085 * Since: 2.14
1086 **/
1087 GSequenceIter *
g_sequence_get_iter_at_pos(GSequence * seq,gint pos)1088 g_sequence_get_iter_at_pos (GSequence *seq,
1089 gint pos)
1090 {
1091 g_return_val_if_fail (seq != NULL, NULL);
1092
1093 pos = clamp_position (seq, pos);
1094
1095 return node_get_by_pos (seq->end_node, pos);
1096 }
1097
1098 /**
1099 * g_sequence_move:
1100 * @src: a #GSequenceIter pointing to the item to move
1101 * @dest: a #GSequenceIter pointing to the position to which
1102 * the item is moved.
1103 *
1104 * Moves the item pointed to by @src to the position indicated by @dest.
1105 * After calling this function @dest will point to the position immediately
1106 * after @src. It is allowed for @src and @dest to point into different
1107 * sequences.
1108 *
1109 * Since: 2.14
1110 **/
1111 void
g_sequence_move(GSequenceIter * src,GSequenceIter * dest)1112 g_sequence_move (GSequenceIter *src,
1113 GSequenceIter *dest)
1114 {
1115 g_return_if_fail (src != NULL);
1116 g_return_if_fail (dest != NULL);
1117 g_return_if_fail (!is_end (src));
1118
1119 if (src == dest)
1120 return;
1121
1122 node_unlink (src);
1123 node_insert_before (dest, src);
1124 }
1125
1126 /* GSequenceIter */
1127
1128 /**
1129 * g_sequence_iter_is_end:
1130 * @iter: a #GSequenceIter
1131 *
1132 * Returns whether @iter is the end iterator
1133 *
1134 * Return value: Whether @iter is the end iterator.
1135 *
1136 * Since: 2.14
1137 **/
1138 gboolean
g_sequence_iter_is_end(GSequenceIter * iter)1139 g_sequence_iter_is_end (GSequenceIter *iter)
1140 {
1141 g_return_val_if_fail (iter != NULL, FALSE);
1142
1143 return is_end (iter);
1144 }
1145
1146 /**
1147 * g_sequence_iter_is_begin:
1148 * @iter: a #GSequenceIter
1149 *
1150 * Returns whether @iter is the begin iterator
1151 *
1152 * Return value: whether @iter is the begin iterator
1153 *
1154 * Since: 2.14
1155 **/
1156 gboolean
g_sequence_iter_is_begin(GSequenceIter * iter)1157 g_sequence_iter_is_begin (GSequenceIter *iter)
1158 {
1159 g_return_val_if_fail (iter != NULL, FALSE);
1160
1161 return (node_get_prev (iter) == iter);
1162 }
1163
1164 /**
1165 * g_sequence_iter_get_position:
1166 * @iter: a #GSequenceIter
1167 *
1168 * Returns the position of @iter
1169 *
1170 * Return value: the position of @iter
1171 *
1172 * Since: 2.14
1173 **/
1174 gint
g_sequence_iter_get_position(GSequenceIter * iter)1175 g_sequence_iter_get_position (GSequenceIter *iter)
1176 {
1177 g_return_val_if_fail (iter != NULL, -1);
1178
1179 return node_get_pos (iter);
1180 }
1181
1182 /**
1183 * g_sequence_iter_next:
1184 * @iter: a #GSequenceIter
1185 *
1186 * Returns an iterator pointing to the next position after @iter. If
1187 * @iter is the end iterator, the end iterator is returned.
1188 *
1189 * Return value: a #GSequenceIter pointing to the next position after @iter.
1190 *
1191 * Since: 2.14
1192 **/
1193 GSequenceIter *
g_sequence_iter_next(GSequenceIter * iter)1194 g_sequence_iter_next (GSequenceIter *iter)
1195 {
1196 g_return_val_if_fail (iter != NULL, NULL);
1197
1198 return node_get_next (iter);
1199 }
1200
1201 /**
1202 * g_sequence_iter_prev:
1203 * @iter: a #GSequenceIter
1204 *
1205 * Returns an iterator pointing to the previous position before @iter. If
1206 * @iter is the begin iterator, the begin iterator is returned.
1207 *
1208 * Return value: a #GSequenceIter pointing to the previous position before
1209 * @iter.
1210 *
1211 * Since: 2.14
1212 **/
1213 GSequenceIter *
g_sequence_iter_prev(GSequenceIter * iter)1214 g_sequence_iter_prev (GSequenceIter *iter)
1215 {
1216 g_return_val_if_fail (iter != NULL, NULL);
1217
1218 return node_get_prev (iter);
1219 }
1220
1221 /**
1222 * g_sequence_iter_move:
1223 * @iter: a #GSequenceIter
1224 * @delta: A positive or negative number indicating how many positions away
1225 * from @iter the returned #GSequenceIter will be.
1226 *
1227 * Returns the #GSequenceIter which is @delta positions away from @iter.
1228 * If @iter is closer than -@delta positions to the beginning of the sequence,
1229 * the begin iterator is returned. If @iter is closer than @delta positions
1230 * to the end of the sequence, the end iterator is returned.
1231 *
1232 * Return value: a #GSequenceIter which is @delta positions away from @iter.
1233 *
1234 * Since: 2.14
1235 **/
1236 GSequenceIter *
g_sequence_iter_move(GSequenceIter * iter,gint delta)1237 g_sequence_iter_move (GSequenceIter *iter,
1238 gint delta)
1239 {
1240 gint new_pos;
1241
1242 g_return_val_if_fail (iter != NULL, NULL);
1243
1244 new_pos = node_get_pos (iter) + delta;
1245
1246 new_pos = clamp_position (get_sequence (iter), new_pos);
1247
1248 return node_get_by_pos (iter, new_pos);
1249 }
1250
1251 /**
1252 * g_sequence_swap:
1253 * @a: a #GSequenceIter
1254 * @b: a #GSequenceIter
1255 *
1256 * Swaps the items pointed to by @a and @b. It is allowed for @a and @b
1257 * to point into difference sequences.
1258 *
1259 * Since: 2.14
1260 **/
1261 void
g_sequence_swap(GSequenceIter * a,GSequenceIter * b)1262 g_sequence_swap (GSequenceIter *a,
1263 GSequenceIter *b)
1264 {
1265 GSequenceNode *leftmost, *rightmost, *rightmost_next;
1266 int a_pos, b_pos;
1267
1268 g_return_if_fail (!g_sequence_iter_is_end (a));
1269 g_return_if_fail (!g_sequence_iter_is_end (b));
1270
1271 if (a == b)
1272 return;
1273
1274 a_pos = g_sequence_iter_get_position (a);
1275 b_pos = g_sequence_iter_get_position (b);
1276
1277 if (a_pos > b_pos)
1278 {
1279 leftmost = b;
1280 rightmost = a;
1281 }
1282 else
1283 {
1284 leftmost = a;
1285 rightmost = b;
1286 }
1287
1288 rightmost_next = node_get_next (rightmost);
1289
1290 /* The situation is now like this:
1291 *
1292 * ..., leftmost, ......., rightmost, rightmost_next, ...
1293 *
1294 */
1295 g_sequence_move (rightmost, leftmost);
1296 g_sequence_move (leftmost, rightmost_next);
1297 }
1298
1299 /*
1300 * Implementation of a treap
1301 *
1302 *
1303 */
1304 static guint
get_priority(GSequenceNode * node)1305 get_priority (GSequenceNode *node)
1306 {
1307 guint key = GPOINTER_TO_UINT (node);
1308
1309 /* This hash function is based on one found on Thomas Wang's
1310 * web page at
1311 *
1312 * http://www.concentric.net/~Ttwang/tech/inthash.htm
1313 *
1314 */
1315 key = (key << 15) - key - 1;
1316 key = key ^ (key >> 12);
1317 key = key + (key << 2);
1318 key = key ^ (key >> 4);
1319 key = key + (key << 3) + (key << 11);
1320 key = key ^ (key >> 16);
1321
1322 /* We rely on 0 being less than all other priorities */
1323 return key? key : 1;
1324 }
1325
1326 static GSequenceNode *
find_root(GSequenceNode * node)1327 find_root (GSequenceNode *node)
1328 {
1329 while (node->parent)
1330 node = node->parent;
1331
1332 return node;
1333 }
1334
1335 static GSequenceNode *
node_new(gpointer data)1336 node_new (gpointer data)
1337 {
1338 GSequenceNode *node = g_slice_new0 (GSequenceNode);
1339
1340 node->n_nodes = 1;
1341 node->data = data;
1342 node->left = NULL;
1343 node->right = NULL;
1344 node->parent = NULL;
1345
1346 return node;
1347 }
1348
1349 static GSequenceNode *
node_get_first(GSequenceNode * node)1350 node_get_first (GSequenceNode *node)
1351 {
1352 node = find_root (node);
1353
1354 while (node->left)
1355 node = node->left;
1356
1357 return node;
1358 }
1359
1360 static GSequenceNode *
node_get_last(GSequenceNode * node)1361 node_get_last (GSequenceNode *node)
1362 {
1363 node = find_root (node);
1364
1365 while (node->right)
1366 node = node->right;
1367
1368 return node;
1369 }
1370
1371 #define NODE_LEFT_CHILD(n) (((n)->parent) && ((n)->parent->left) == (n))
1372 #define NODE_RIGHT_CHILD(n) (((n)->parent) && ((n)->parent->right) == (n))
1373
1374 static GSequenceNode *
node_get_next(GSequenceNode * node)1375 node_get_next (GSequenceNode *node)
1376 {
1377 GSequenceNode *n = node;
1378
1379 if (n->right)
1380 {
1381 n = n->right;
1382 while (n->left)
1383 n = n->left;
1384 }
1385 else
1386 {
1387 while (NODE_RIGHT_CHILD (n))
1388 n = n->parent;
1389
1390 if (n->parent)
1391 n = n->parent;
1392 else
1393 n = node;
1394 }
1395
1396 return n;
1397 }
1398
1399 static GSequenceNode *
node_get_prev(GSequenceNode * node)1400 node_get_prev (GSequenceNode *node)
1401 {
1402 GSequenceNode *n = node;
1403
1404 if (n->left)
1405 {
1406 n = n->left;
1407 while (n->right)
1408 n = n->right;
1409 }
1410 else
1411 {
1412 while (NODE_LEFT_CHILD (n))
1413 n = n->parent;
1414
1415 if (n->parent)
1416 n = n->parent;
1417 else
1418 n = node;
1419 }
1420
1421 return n;
1422 }
1423
1424 #define N_NODES(n) ((n)? (n)->n_nodes : 0)
1425
1426 static gint
node_get_pos(GSequenceNode * node)1427 node_get_pos (GSequenceNode *node)
1428 {
1429 int n_smaller = 0;
1430
1431 if (node->left)
1432 n_smaller = node->left->n_nodes;
1433
1434 while (node)
1435 {
1436 if (NODE_RIGHT_CHILD (node))
1437 n_smaller += N_NODES (node->parent->left) + 1;
1438
1439 node = node->parent;
1440 }
1441
1442 return n_smaller;
1443 }
1444
1445 static GSequenceNode *
node_get_by_pos(GSequenceNode * node,gint pos)1446 node_get_by_pos (GSequenceNode *node,
1447 gint pos)
1448 {
1449 int i;
1450
1451 node = find_root (node);
1452
1453 while ((i = N_NODES (node->left)) != pos)
1454 {
1455 if (i < pos)
1456 {
1457 node = node->right;
1458 pos -= (i + 1);
1459 }
1460 else
1461 {
1462 node = node->left;
1463 }
1464 }
1465
1466 return node;
1467 }
1468
1469 static GSequenceNode *
node_find_closest(GSequenceNode * haystack,GSequenceNode * needle,GSequenceNode * end,GSequenceIterCompareFunc iter_cmp,gpointer cmp_data)1470 node_find_closest (GSequenceNode *haystack,
1471 GSequenceNode *needle,
1472 GSequenceNode *end,
1473 GSequenceIterCompareFunc iter_cmp,
1474 gpointer cmp_data)
1475 {
1476 GSequenceNode *best;
1477 gint c;
1478
1479 haystack = find_root (haystack);
1480
1481 do
1482 {
1483 best = haystack;
1484
1485 /* iter_cmp can't be passed the end node, since the function may
1486 * be user-supplied
1487 */
1488 if (haystack == end)
1489 c = 1;
1490 else
1491 c = iter_cmp (haystack, needle, cmp_data);
1492
1493 /* In the following we don't break even if c == 0. Instaed we go on
1494 * searching along the 'bigger' nodes, so that we find the last one
1495 * that is equal to the needle.
1496 */
1497 if (c > 0)
1498 haystack = haystack->left;
1499 else
1500 haystack = haystack->right;
1501 }
1502 while (haystack != NULL);
1503
1504 /* If the best node is smaller or equal to the data, then move one step
1505 * to the right to make sure the best one is strictly bigger than the data
1506 */
1507 if (best != end && c <= 0)
1508 best = node_get_next (best);
1509
1510 return best;
1511 }
1512
1513 static gint
node_get_length(GSequenceNode * node)1514 node_get_length (GSequenceNode *node)
1515 {
1516 node = find_root (node);
1517
1518 return node->n_nodes;
1519 }
1520
1521 static void
real_node_free(GSequenceNode * node,GSequence * seq)1522 real_node_free (GSequenceNode *node,
1523 GSequence *seq)
1524 {
1525 if (node)
1526 {
1527 real_node_free (node->left, seq);
1528 real_node_free (node->right, seq);
1529
1530 if (seq && seq->data_destroy_notify && node != seq->end_node)
1531 seq->data_destroy_notify (node->data);
1532
1533 g_slice_free (GSequenceNode, node);
1534 }
1535 }
1536
1537 static void
node_free(GSequenceNode * node,GSequence * seq)1538 node_free (GSequenceNode *node,
1539 GSequence *seq)
1540 {
1541 node = find_root (node);
1542
1543 real_node_free (node, seq);
1544 }
1545
1546 static void
node_update_fields(GSequenceNode * node)1547 node_update_fields (GSequenceNode *node)
1548 {
1549 int n_nodes = 1;
1550
1551 n_nodes += N_NODES (node->left);
1552 n_nodes += N_NODES (node->right);
1553
1554 node->n_nodes = n_nodes;
1555 }
1556
1557 static void
node_rotate(GSequenceNode * node)1558 node_rotate (GSequenceNode *node)
1559 {
1560 GSequenceNode *tmp, *old;
1561
1562 g_assert (node->parent);
1563 g_assert (node->parent != node);
1564
1565 if (NODE_LEFT_CHILD (node))
1566 {
1567 /* rotate right */
1568 tmp = node->right;
1569
1570 node->right = node->parent;
1571 node->parent = node->parent->parent;
1572 if (node->parent)
1573 {
1574 if (node->parent->left == node->right)
1575 node->parent->left = node;
1576 else
1577 node->parent->right = node;
1578 }
1579
1580 g_assert (node->right);
1581
1582 node->right->parent = node;
1583 node->right->left = tmp;
1584
1585 if (node->right->left)
1586 node->right->left->parent = node->right;
1587
1588 old = node->right;
1589 }
1590 else
1591 {
1592 /* rotate left */
1593 tmp = node->left;
1594
1595 node->left = node->parent;
1596 node->parent = node->parent->parent;
1597 if (node->parent)
1598 {
1599 if (node->parent->right == node->left)
1600 node->parent->right = node;
1601 else
1602 node->parent->left = node;
1603 }
1604
1605 g_assert (node->left);
1606
1607 node->left->parent = node;
1608 node->left->right = tmp;
1609
1610 if (node->left->right)
1611 node->left->right->parent = node->left;
1612
1613 old = node->left;
1614 }
1615
1616 node_update_fields (old);
1617 node_update_fields (node);
1618 }
1619
1620 static void
node_update_fields_deep(GSequenceNode * node)1621 node_update_fields_deep (GSequenceNode *node)
1622 {
1623 if (node)
1624 {
1625 node_update_fields (node);
1626
1627 node_update_fields_deep (node->parent);
1628 }
1629 }
1630
1631 static void
rotate_down(GSequenceNode * node,guint priority)1632 rotate_down (GSequenceNode *node,
1633 guint priority)
1634 {
1635 guint left, right;
1636
1637 left = node->left ? get_priority (node->left) : 0;
1638 right = node->right ? get_priority (node->right) : 0;
1639
1640 while (priority < left || priority < right)
1641 {
1642 if (left > right)
1643 node_rotate (node->left);
1644 else
1645 node_rotate (node->right);
1646
1647 left = node->left ? get_priority (node->left) : 0;
1648 right = node->right ? get_priority (node->right) : 0;
1649 }
1650 }
1651
1652 static void
node_cut(GSequenceNode * node)1653 node_cut (GSequenceNode *node)
1654 {
1655 while (node->parent)
1656 node_rotate (node);
1657
1658 if (node->left)
1659 node->left->parent = NULL;
1660
1661 node->left = NULL;
1662 node_update_fields (node);
1663
1664 rotate_down (node, get_priority (node));
1665 }
1666
1667 static void
node_join(GSequenceNode * left,GSequenceNode * right)1668 node_join (GSequenceNode *left,
1669 GSequenceNode *right)
1670 {
1671 GSequenceNode *fake = node_new (NULL);
1672
1673 fake->left = find_root (left);
1674 fake->right = find_root (right);
1675 fake->left->parent = fake;
1676 fake->right->parent = fake;
1677
1678 node_update_fields (fake);
1679
1680 node_unlink (fake);
1681
1682 node_free (fake, NULL);
1683 }
1684
1685 static void
node_insert_before(GSequenceNode * node,GSequenceNode * new)1686 node_insert_before (GSequenceNode *node,
1687 GSequenceNode *new)
1688 {
1689 new->left = node->left;
1690 if (new->left)
1691 new->left->parent = new;
1692
1693 new->parent = node;
1694 node->left = new;
1695
1696 node_update_fields_deep (new);
1697
1698 while (new->parent && get_priority (new) > get_priority (new->parent))
1699 node_rotate (new);
1700
1701 rotate_down (new, get_priority (new));
1702 }
1703
1704 static void
node_unlink(GSequenceNode * node)1705 node_unlink (GSequenceNode *node)
1706 {
1707 rotate_down (node, 0);
1708
1709 if (NODE_RIGHT_CHILD (node))
1710 node->parent->right = NULL;
1711 else if (NODE_LEFT_CHILD (node))
1712 node->parent->left = NULL;
1713
1714 if (node->parent)
1715 node_update_fields_deep (node->parent);
1716
1717 node->parent = NULL;
1718 }
1719
1720 static void
node_insert_sorted(GSequenceNode * node,GSequenceNode * new,GSequenceNode * end,GSequenceIterCompareFunc iter_cmp,gpointer cmp_data)1721 node_insert_sorted (GSequenceNode *node,
1722 GSequenceNode *new,
1723 GSequenceNode *end,
1724 GSequenceIterCompareFunc iter_cmp,
1725 gpointer cmp_data)
1726 {
1727 GSequenceNode *closest;
1728
1729 closest = node_find_closest (node, new, end, iter_cmp, cmp_data);
1730
1731 node_unlink (new);
1732
1733 node_insert_before (closest, new);
1734 }
1735