nexmon – Blame information for rev 1

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