+#include "gtkintl.h"
+#include "gtkprivate.h"
+#include "gtktreednd.h"
+
+
+/**
+ * SECTION:gtktreemodelsort
+ * @Short_description: A GtkTreeModel which makes an underlying tree model sortable
+ * @Title: GtkTreeModelSort
+ * @See_also: #GtkTreeModel, #GtkListStore, #GtkTreeStore, #GtkTreeSortable, #GtkTreeModelFilter
+ *
+ * The #GtkTreeModelSort is a model which implements the #GtkTreeSortable
+ * interface. It does not hold any data itself, but rather is created with
+ * a child model and proxies its data. It has identical column types to
+ * this child model, and the changes in the child are propagated. The
+ * primary purpose of this model is to provide a way to sort a different
+ * model without modifying it. Note that the sort function used by
+ * #GtkTreeModelSort is not guaranteed to be stable.
+ *
+ * The use of this is best demonstrated through an example. In the
+ * following sample code we create two #GtkTreeView widgets each with a
+ * view of the same data. As the model is wrapped here by a
+ * #GtkTreeModelSort, the two #GtkTreeView<!-- -->s can each sort their
+ * view of the data without affecting the other. By contrast, if we
+ * simply put the same model in each widget, then sorting the first would
+ * sort the second.
+ *
+ * <example>
+ * <title>Using a <structname>GtkTreeModelSort</structname></title>
+ * <programlisting>
+ * {
+ * GtkTreeView *tree_view1;
+ * GtkTreeView *tree_view2;
+ * GtkTreeModel *sort_model1;
+ * GtkTreeModel *sort_model2;
+ * GtkTreeModel *child_model;
+ *
+ * // get the child model
+ * child_model = get_my_model ();
+ *
+ * // Create the first tree
+ * sort_model1 = gtk_tree_model_sort_new_with_model (child_model);
+ * tree_view1 = gtk_tree_view_new_with_model (sort_model1);
+ *
+ * // Create the second tree
+ * sort_model2 = gtk_tree_model_sort_new_with_model (child_model);
+ * tree_view2 = gtk_tree_view_new_with_model (sort_model2);
+ *
+ * // Now we can sort the two models independently
+ * gtk_tree_sortable_set_sort_column_id (GTK_TREE_SORTABLE (sort_model1),
+ * COLUMN_1, GTK_SORT_ASCENDING);
+ * gtk_tree_sortable_set_sort_column_id (GTK_TREE_SORTABLE (sort_model2),
+ * COLUMN_1, GTK_SORT_DESCENDING);
+ * }
+ * </programlisting>
+ * </example>
+ *
+ * To demonstrate how to access the underlying child model from the sort
+ * model, the next example will be a callback for the #GtkTreeSelection
+ * #GtkTreeSelection::changed signal. In this callback, we get a string
+ * from COLUMN_1 of the model. We then modify the string, find the same
+ * selected row on the child model, and change the row there.
+ *
+ * <example>
+ * <title>Accessing the child model of in a selection changed callback</title>
+ * <programlisting>
+ * void
+ * selection_changed (GtkTreeSelection *selection, gpointer data)
+ * {
+ * GtkTreeModel *sort_model = NULL;
+ * GtkTreeModel *child_model;
+ * GtkTreeIter sort_iter;
+ * GtkTreeIter child_iter;
+ * char *some_data = NULL;
+ * char *modified_data;
+ *
+ * // Get the current selected row and the model.
+ * if (! gtk_tree_selection_get_selected (selection,
+ * &sort_model,
+ * &sort_iter))
+ * return;
+ *
+ * /<!---->* Look up the current value on the selected row and get a new value
+ * * to change it to.
+ * *<!---->/
+ * gtk_tree_model_get (GTK_TREE_MODEL (sort_model), &sort_iter,
+ * COLUMN_1, &some_data,
+ * -1);
+ *
+ * modified_data = change_the_data (some_data);
+ * g_free (some_data);
+ *
+ * // Get an iterator on the child model, instead of the sort model.
+ * gtk_tree_model_sort_convert_iter_to_child_iter (GTK_TREE_MODEL_SORT (sort_model),
+ * &child_iter,
+ * &sort_iter);
+ *
+ * /<!---->* Get the child model and change the value of the row. In this
+ * * example, the child model is a GtkListStore. It could be any other
+ * * type of model, though.
+ * *<!---->/
+ * child_model = gtk_tree_model_sort_get_model (GTK_TREE_MODEL_SORT (sort_model));
+ * gtk_list_store_set (GTK_LIST_STORE (child_model), &child_iter,
+ * COLUMN_1, &modified_data,
+ * -1);
+ * g_free (modified_data);
+ * }
+ * </programlisting>
+ * </example>
+ */
+
+
+/* Notes on this implementation of GtkTreeModelSort
+ * ================================================
+ *
+ * Warnings
+ * --------
+ *
+ * In this code there is a potential for confusion as to whether an iter,
+ * path or value refers to the GtkTreeModelSort model, or to the child model
+ * that has been set. As a convention, variables referencing the child model
+ * will have an s_ prefix before them (ie. s_iter, s_value, s_path);
+ * Conversion of iterators and paths between GtkTreeModelSort and the child
+ * model is done through the various gtk_tree_model_sort_convert_* functions.
+ *
+ * Iterator format
+ * ---------------
+ *
+ * The iterator format of iterators handed out by GtkTreeModelSort is as
+ * follows:
+ *
+ * iter->stamp = tree_model_sort->stamp
+ * iter->user_data = SortLevel
+ * iter->user_data2 = SortElt
+ *
+ * Internal data structure
+ * -----------------------
+ *
+ * Using SortLevel and SortElt, GtkTreeModelSort maintains a "cache" of
+ * the mapping from GtkTreeModelSort nodes to nodes in the child model.
+ * This is to avoid sorting a level each time an operation is requested
+ * on GtkTreeModelSort, such as get iter, get path, get value.
+ *
+ * A SortElt corresponds to a single node. A node and its siblings are
+ * stored in a SortLevel. The SortLevel keeps a reference to the parent
+ * SortElt and its SortLevel (if any). The SortElt can have a "children"
+ * pointer set, which points at a child level (a sub level).
+ *
+ * In a SortLevel, nodes are stored in a GSequence. The GSequence
+ * allows for fast additions and removals, and supports sorting
+ * the level of SortElt nodes.
+ *
+ * It is important to recognize the two different mappings that play
+ * a part in this code:
+ * I. The mapping from the client to this model. The order in which
+ * nodes are stored in the GSequence is the order in which the
+ * nodes are exposed to clients of the GtkTreeModelSort.
+ * II. The mapping from this model to its child model. Each SortElt
+ * contains an "offset" field which is the offset of the
+ * corresponding node in the child model.
+ *
+ * Reference counting
+ * ------------------
+ *
+ * GtkTreeModelSort forwards all reference and unreference operations
+ * to the corresponding node in the child model. The reference count
+ * of each node is also maintained internally, in the "ref_count"
+ * fields in SortElt and SortLevel. For each ref and unref operation on
+ * a SortElt, the "ref_count" of the SortLevel is updated accordingly.
+ * In addition, if a SortLevel has a parent, a reference is taken on
+ * this parent. This happens in gtk_tree_model_sort_build_level() and
+ * the reference is released again in gtk_tree_model_sort_free_level().
+ * This ensures that when GtkTreeModelSort takes a reference on a node
+ * (for example during sorting), all parent nodes are referenced
+ * according to reference counting rule 1, see the GtkTreeModel
+ * documentation.
+ *
+ * When a level has a reference count of zero, which means that
+ * none of the nodes in the level is referenced, the level has
+ * a "zero ref count" on all its parents. As soon as the level
+ * reaches a reference count of zero, the zero ref count value is
+ * incremented by one on all parents of this level. Similarly, as
+ * soon as the reference count of a level changes from zero, the
+ * zero ref count value is decremented by one on all parents.
+ *
+ * The zero ref count value is used to clear unused portions of
+ * the cache. If a SortElt has a zero ref count of one, then
+ * its child level is unused and can be removed from the cache.
+ * If the zero ref count value is higher than one, then the
+ * child level contains sublevels which are unused as well.
+ * gtk_tree_model_sort_clear_cache() uses this to not recurse
+ * into levels which have a zero ref count of zero.
+ */