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