/* gtktreestore.c
 * Copyright (C) 2000  Red Hat, Inc.,  Jonathan Blandford <jrb@redhat.com>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library. If not, see <http://www.gnu.org/licenses/>.
 */

#include "config.h"
#include <string.h>
#include <gobject/gvaluecollector.h>
#include "gtktreemodel.h"
#include "gtktreestore.h"
#include "gtktreedatalistprivate.h"
#include "gtktreednd.h"
#include "gtkbuildable.h"
#include "gtkbuilderprivate.h"
#include "gtkdebug.h"

G_GNUC_BEGIN_IGNORE_DEPRECATIONS

/**
 * GtkTreeStore:
 *
 * A tree-like data structure that can be used with the [class@Gtk.TreeView].
 *
 * The `GtkTreeStore` object is a list model for use with a `GtkTreeView`
 * widget. It implements the [iface@Gtk.TreeModel] interface, and consequently,
 * can use all of the methods available there. It also implements the
 * [iface@Gtk.TreeSortable] interface so it can be sorted by the view.
 * Finally, it also implements the tree [drag][iface@Gtk.TreeDragSource]
 * and [drop][iface@Gtk.TreeDragDest] interfaces.
 *
 * `GtkTreeStore` is deprecated since GTK 4.10, and should not be used in newly
 * written code. You should use [class@Gtk.TreeListModel] for a tree-like model
 * object.
 *
 * ## GtkTreeStore as GtkBuildable
 *
 * The GtkTreeStore implementation of the `GtkBuildable` interface allows
 * to specify the model columns with a `<columns>` element that may contain
 * multiple `<column>` elements, each specifying one model column. The “type”
 * attribute specifies the data type for the column.
 *
 * An example of a UI Definition fragment for a tree store:
 *
 * ```xml
 * <object class="GtkTreeStore">
 *   <columns>
 *     <column type="gchararray"/>
 *     <column type="gchararray"/>
 *     <column type="gint"/>
 *   </columns>
 * </object>
 * ```
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 */

struct _GtkTreeStorePrivate
{
  int stamp;
  GtkSortType order;
  gpointer root;
  gpointer last;
  int n_columns;
  int sort_column_id;
  GList *sort_list;
  GType *column_headers;
  GtkTreeIterCompareFunc default_sort_func;
  gpointer default_sort_data;
  GDestroyNotify default_sort_destroy;
  guint columns_dirty : 1;
};


#define G_NODE(node) ((GNode *)node)
#define GTK_TREE_STORE_IS_SORTED(tree) (((GtkTreeStore*)(tree))->priv->sort_column_id != GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID)
#define VALID_ITER(iter, tree_store) ((iter)!= NULL && (iter)->user_data != NULL && ((GtkTreeStore*)(tree_store))->priv->stamp == (iter)->stamp)

static void         gtk_tree_store_tree_model_init (GtkTreeModelIface *iface);
static void         gtk_tree_store_drag_source_init(GtkTreeDragSourceIface *iface);
static void         gtk_tree_store_drag_dest_init  (GtkTreeDragDestIface   *iface);
static void         gtk_tree_store_sortable_init   (GtkTreeSortableIface   *iface);
static void         gtk_tree_store_buildable_init  (GtkBuildableIface      *iface);
static void         gtk_tree_store_finalize        (GObject           *object);
static GtkTreeModelFlags gtk_tree_store_get_flags  (GtkTreeModel      *tree_model);
static int          gtk_tree_store_get_n_columns   (GtkTreeModel      *tree_model);
static GType        gtk_tree_store_get_column_type (GtkTreeModel      *tree_model,
          int                index);
static gboolean     gtk_tree_store_get_iter        (GtkTreeModel      *tree_model,
          GtkTreeIter       *iter,
          GtkTreePath       *path);
static GtkTreePath *gtk_tree_store_get_path        (GtkTreeModel      *tree_model,
          GtkTreeIter       *iter);
static void         gtk_tree_store_get_value       (GtkTreeModel      *tree_model,
          GtkTreeIter       *iter,
          int                column,
          GValue            *value);
static gboolean     gtk_tree_store_iter_next       (GtkTreeModel      *tree_model,
          GtkTreeIter       *iter);
static gboolean     gtk_tree_store_iter_previous   (GtkTreeModel      *tree_model,
          GtkTreeIter       *iter);
static gboolean     gtk_tree_store_iter_children   (GtkTreeModel      *tree_model,
          GtkTreeIter       *iter,
          GtkTreeIter       *parent);
static gboolean     gtk_tree_store_iter_has_child  (GtkTreeModel      *tree_model,
          GtkTreeIter       *iter);
static int          gtk_tree_store_iter_n_children (GtkTreeModel      *tree_model,
          GtkTreeIter       *iter);
static gboolean     gtk_tree_store_iter_nth_child  (GtkTreeModel      *tree_model,
          GtkTreeIter       *iter,
          GtkTreeIter       *parent,
          int                n);
static gboolean     gtk_tree_store_iter_parent     (GtkTreeModel      *tree_model,
          GtkTreeIter       *iter,
          GtkTreeIter       *child);


static void gtk_tree_store_set_n_columns   (GtkTreeStore *tree_store,
         int           n_columns);
static void gtk_tree_store_set_column_type (GtkTreeStore *tree_store,
         int           column,
         GType         type);

static void gtk_tree_store_increment_stamp (GtkTreeStore  *tree_store);


/* DND interfaces */
static gboolean real_gtk_tree_store_row_draggable   (GtkTreeDragSource *drag_source,
         GtkTreePath       *path);
static gboolean gtk_tree_store_drag_data_delete   (GtkTreeDragSource *drag_source,
         GtkTreePath       *path);
static GdkContentProvider *
                gtk_tree_store_drag_data_get      (GtkTreeDragSource *drag_source,
         GtkTreePath       *path);
static gboolean gtk_tree_store_drag_data_received (GtkTreeDragDest   *drag_dest,
         GtkTreePath       *dest,
         const GValue      *value);
static gboolean gtk_tree_store_row_drop_possible  (GtkTreeDragDest   *drag_dest,
         GtkTreePath       *dest_path,
         const GValue      *value);

/* Sortable Interfaces */

static void     gtk_tree_store_sort                    (GtkTreeStore           *tree_store);
static void     gtk_tree_store_sort_iter_changed       (GtkTreeStore           *tree_store,
       GtkTreeIter            *iter,
       int                     column,
       gboolean                emit_signal);
static gboolean gtk_tree_store_get_sort_column_id      (GtkTreeSortable        *sortable,
       int                    *sort_column_id,
       GtkSortType            *order);
static void     gtk_tree_store_set_sort_column_id      (GtkTreeSortable        *sortable,
       int                     sort_column_id,
       GtkSortType             order);
static void     gtk_tree_store_set_sort_func           (GtkTreeSortable        *sortable,
       int                     sort_column_id,
       GtkTreeIterCompareFunc  func,
       gpointer                data,
       GDestroyNotify          destroy);
static void     gtk_tree_store_set_default_sort_func   (GtkTreeSortable        *sortable,
       GtkTreeIterCompareFunc  func,
       gpointer                data,
       GDestroyNotify          destroy);
static gboolean gtk_tree_store_has_default_sort_func   (GtkTreeSortable        *sortable);


/* buildable */

static gboolean gtk_tree_store_buildable_custom_tag_start (GtkBuildable       *buildable,
                                                           GtkBuilder         *builder,
                                                           GObject            *child,
                                                           const char         *tagname,
                                                           GtkBuildableParser *parser,
                                                           gpointer           *data);
static void     gtk_tree_store_buildable_custom_tag_end   (GtkBuildable       *buildable,
                                                           GtkBuilder         *builder,
                                                           GObject            *child,
                                                           const char         *tagname,
                                                           gpointer            parser_data);

static void     gtk_tree_store_move                    (GtkTreeStore           *tree_store,
                                                        GtkTreeIter            *iter,
                                                        GtkTreeIter            *position,
                                                        gboolean                before);


static void     validate_gnode                         (GNode *node);

static inline void
validate_tree (GtkTreeStore *tree_store)
{
  if (GTK_DEBUG_CHECK (TREE))
    {
      g_assert (G_NODE (tree_store->priv->root)->parent == NULL);
      validate_gnode (G_NODE (tree_store->priv->root));
    }
}

G_DEFINE_TYPE_WITH_CODE (GtkTreeStore, gtk_tree_store, G_TYPE_OBJECT,
                         G_ADD_PRIVATE (GtkTreeStore)
    G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_MODEL,
      gtk_tree_store_tree_model_init)
    G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_DRAG_SOURCE,
      gtk_tree_store_drag_source_init)
    G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_DRAG_DEST,
      gtk_tree_store_drag_dest_init)
    G_IMPLEMENT_INTERFACE (GTK_TYPE_TREE_SORTABLE,
      gtk_tree_store_sortable_init)
    G_IMPLEMENT_INTERFACE (GTK_TYPE_BUILDABLE,
      gtk_tree_store_buildable_init))

static void
gtk_tree_store_class_init (GtkTreeStoreClass *class)
{
  GObjectClass *object_class;

  object_class = (GObjectClass *) class;

  object_class->finalize = gtk_tree_store_finalize;
}

static void
gtk_tree_store_tree_model_init (GtkTreeModelIface *iface)
{
  iface->get_flags = gtk_tree_store_get_flags;
  iface->get_n_columns = gtk_tree_store_get_n_columns;
  iface->get_column_type = gtk_tree_store_get_column_type;
  iface->get_iter = gtk_tree_store_get_iter;
  iface->get_path = gtk_tree_store_get_path;
  iface->get_value = gtk_tree_store_get_value;
  iface->iter_next = gtk_tree_store_iter_next;
  iface->iter_previous = gtk_tree_store_iter_previous;
  iface->iter_children = gtk_tree_store_iter_children;
  iface->iter_has_child = gtk_tree_store_iter_has_child;
  iface->iter_n_children = gtk_tree_store_iter_n_children;
  iface->iter_nth_child = gtk_tree_store_iter_nth_child;
  iface->iter_parent = gtk_tree_store_iter_parent;
}

static void
gtk_tree_store_drag_source_init (GtkTreeDragSourceIface *iface)
{
  iface->row_draggable = real_gtk_tree_store_row_draggable;
  iface->drag_data_delete = gtk_tree_store_drag_data_delete;
  iface->drag_data_get = gtk_tree_store_drag_data_get;
}

static void
gtk_tree_store_drag_dest_init (GtkTreeDragDestIface *iface)
{
  iface->drag_data_received = gtk_tree_store_drag_data_received;
  iface->row_drop_possible = gtk_tree_store_row_drop_possible;
}

static void
gtk_tree_store_sortable_init (GtkTreeSortableIface *iface)
{
  iface->get_sort_column_id = gtk_tree_store_get_sort_column_id;
  iface->set_sort_column_id = gtk_tree_store_set_sort_column_id;
  iface->set_sort_func = gtk_tree_store_set_sort_func;
  iface->set_default_sort_func = gtk_tree_store_set_default_sort_func;
  iface->has_default_sort_func = gtk_tree_store_has_default_sort_func;
}

void
gtk_tree_store_buildable_init (GtkBuildableIface *iface)
{
  iface->custom_tag_start = gtk_tree_store_buildable_custom_tag_start;
  iface->custom_tag_end = gtk_tree_store_buildable_custom_tag_end;
}

static void
gtk_tree_store_init (GtkTreeStore *tree_store)
{
  GtkTreeStorePrivate *priv;

  priv = gtk_tree_store_get_instance_private (tree_store);
  tree_store->priv = priv;
  priv->root = g_node_new (NULL);
  /* While the odds are against us getting 0...  */
  do
    {
      priv->stamp = g_random_int ();
    }
  while (priv->stamp == 0);

  priv->sort_list = NULL;
  priv->sort_column_id = GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID;
  priv->columns_dirty = FALSE;
}

/**
 * gtk_tree_store_new:
 * @n_columns: number of columns in the tree store
 * @...: all `GType` types for the columns, from first to last
 *
 * Creates a new tree store.
 *
 * The tree store will have @n_columns, with each column using the
 * corresponding type passed to this function.
 *
 * Note that only types derived from standard GObject fundamental types
 * are supported.
 *
 * As an example:
 *
 * ```c
 * gtk_tree_store_new (3, G_TYPE_INT, G_TYPE_STRING, GDK_TYPE_TEXTURE);
 * ```
 *
 * will create a new `GtkTreeStore` with three columns of type
 * `int`, `gchararray`, and `GdkTexture` respectively.
 *
 * Returns: a new `GtkTreeStore`
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 **/
GtkTreeStore *
gtk_tree_store_new (int n_columns,
          ...)
{
  GtkTreeStore *retval;
  va_list args;
  int i;

  g_return_val_if_fail (n_columns > 0, NULL);

  retval = g_object_new (GTK_TYPE_TREE_STORE, NULL);
  gtk_tree_store_set_n_columns (retval, n_columns);

  va_start (args, n_columns);

  for (i = 0; i < n_columns; i++)
    {
      GType type = va_arg (args, GType);
      if (! _gtk_tree_data_list_check_type (type))
 {
   g_warning ("%s: Invalid type %s", G_STRLOC, g_type_name (type));
   g_object_unref (retval);
          va_end (args);
   return NULL;
 }
      gtk_tree_store_set_column_type (retval, i, type);
    }
  va_end (args);

  return retval;
}
/**
 * gtk_tree_store_newv: (rename-to gtk_tree_store_new)
 * @n_columns: number of columns in the tree store
 * @types: (array length=n_columns): an array of `GType` types for the columns, from first to last
 *
 * Creates a new tree store.
 *
 * This constructor is meant for language bindings.
 *
 * Returns: (transfer full): a new `GtkTreeStore`
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 **/
GtkTreeStore *
gtk_tree_store_newv (int    n_columns,
       GType *types)
{
  GtkTreeStore *retval;
  int i;

  g_return_val_if_fail (n_columns > 0, NULL);

  retval = g_object_new (GTK_TYPE_TREE_STORE, NULL);
  gtk_tree_store_set_n_columns (retval, n_columns);

   for (i = 0; i < n_columns; i++)
    {
      if (! _gtk_tree_data_list_check_type (types[i]))
 {
   g_warning ("%s: Invalid type %s", G_STRLOC, g_type_name (types[i]));
   g_object_unref (retval);
   return NULL;
 }
      gtk_tree_store_set_column_type (retval, i, types[i]);
    }

  return retval;
}


/**
 * gtk_tree_store_set_column_types:
 * @tree_store: A `GtkTreeStore`
 * @n_columns: Number of columns for the tree store
 * @types: (array length=n_columns): An array of `GType` types, one for each column
 *
 * Sets the type of the columns in a tree store.
 *
 * This function is meant primarily for types that inherit from
 * `GtkTreeStore`, and should only be used when constructing a new
 * `GtkTreeStore`.
 *
 * This functions cannot be called after a row has been added,
 * or a method on the `GtkTreeModel` interface is called on the
 * tree store.
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 **/
void
gtk_tree_store_set_column_types (GtkTreeStore *tree_store,
     int           n_columns,
     GType        *types)
{
  int i;

  g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
  g_return_if_fail (tree_store->priv->columns_dirty == 0);

  gtk_tree_store_set_n_columns (tree_store, n_columns);
   for (i = 0; i < n_columns; i++)
    {
      if (! _gtk_tree_data_list_check_type (types[i]))
 {
   g_warning ("%s: Invalid type %s", G_STRLOC, g_type_name (types[i]));
   continue;
 }
      gtk_tree_store_set_column_type (tree_store, i, types[i]);
    }
}

static void
gtk_tree_store_set_n_columns (GtkTreeStore *tree_store,
         int           n_columns)
{
  GtkTreeStorePrivate *priv = tree_store->priv;
  int i;

  if (priv->n_columns == n_columns)
    return;

  priv->column_headers = g_renew (GType, priv->column_headers, n_columns);
  for (i = priv->n_columns; i < n_columns; i++)
    priv->column_headers[i] = G_TYPE_INVALID;
  priv->n_columns = n_columns;

  if (priv->sort_list)
    _gtk_tree_data_list_header_free (priv->sort_list);

  priv->sort_list = _gtk_tree_data_list_header_new (n_columns, priv->column_headers);
}

/**
 * gtk_tree_store_set_column_type:
 * @tree_store: a `GtkTreeStore`
 * @column: column number
 * @type: type of the data to be stored in @column
 *
 * Sets the type of the given column in a tree store.
 *
 * This function is meant primarily for types that inherit from
 * `GtkTreeStore`, and should only be used when constructing a new
 * `GtkTreeStore`.
 *
 * This functions cannot be called after a row has been added,
 * or a method on the `GtkTreeModel` interface is called on the
 * tree store.
 *
 * Supported types include:
 *
 * - `G_TYPE_UINT`
 * - `G_TYPE_INT`
 * - `G_TYPE_UCHAR`
 * - `G_TYPE_CHAR`
 * - `G_TYPE_BOOLEAN`
 * - `G_TYPE_POINTER`
 * - `G_TYPE_FLOAT`
 * - `G_TYPE_DOUBLE`
 * - `G_TYPE_STRING`
 * - `G_TYPE_BOXED` and its derived types
 * - `G_TYPE_OBJECT` and its derived types
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 **/
static void
gtk_tree_store_set_column_type (GtkTreeStore *tree_store,
    int           column,
    GType         type)
{
  GtkTreeStorePrivate *priv = tree_store->priv;

  if (!_gtk_tree_data_list_check_type (type))
    {
      g_warning ("%s: Invalid type %s", G_STRLOC, g_type_name (type));
      return;
    }
  priv->column_headers[column] = type;
}

static gboolean
node_free (GNode *node, gpointer data)
{
  if (node->data)
    _gtk_tree_data_list_free (node->data, (GType*)data);
  node->data = NULL;

  return FALSE;
}

static void
gtk_tree_store_finalize (GObject *object)
{
  GtkTreeStore *tree_store = GTK_TREE_STORE (object);
  GtkTreeStorePrivate *priv = tree_store->priv;

  g_node_traverse (priv->root, G_POST_ORDER, G_TRAVERSE_ALL, -1,
     node_free, priv->column_headers);
  g_node_destroy (priv->root);
  _gtk_tree_data_list_header_free (priv->sort_list);
  g_free (priv->column_headers);

  if (priv->default_sort_destroy)
    {
      GDestroyNotify d = priv->default_sort_destroy;

      priv->default_sort_destroy = NULL;
      d (priv->default_sort_data);
      priv->default_sort_data = NULL;
    }

  /* must chain up */
  G_OBJECT_CLASS (gtk_tree_store_parent_class)->finalize (object);
}

/* fulfill the GtkTreeModel requirements */
/* NOTE: GtkTreeStore::root is a GNode, that acts as the parent node.  However,
 * it is not visible to the tree or to the user., and the path “0” refers to the
 * first child of GtkTreeStore::root.
 */


static GtkTreeModelFlags
gtk_tree_store_get_flags (GtkTreeModel *tree_model)
{
  return GTK_TREE_MODEL_ITERS_PERSIST;
}

static int
gtk_tree_store_get_n_columns (GtkTreeModel *tree_model)
{
  GtkTreeStore *tree_store = (GtkTreeStore *) tree_model;
  GtkTreeStorePrivate *priv = tree_store->priv;

  priv->columns_dirty = TRUE;

  return priv->n_columns;
}

static GType
gtk_tree_store_get_column_type (GtkTreeModel *tree_model,
    int           index)
{
  GtkTreeStore *tree_store = (GtkTreeStore *) tree_model;
  GtkTreeStorePrivate *priv = tree_store->priv;

  g_return_val_if_fail (index < priv->n_columns, G_TYPE_INVALID);

  priv->columns_dirty = TRUE;

  return priv->column_headers[index];
}

static gboolean
gtk_tree_store_get_iter (GtkTreeModel *tree_model,
    GtkTreeIter  *iter,
    GtkTreePath  *path)
{
  GtkTreeStore *tree_store = (GtkTreeStore *) tree_model;
  GtkTreeStorePrivate *priv = tree_store->priv;
  GtkTreeIter parent;
  int *indices;
  int depth, i;

  priv->columns_dirty = TRUE;

  indices = gtk_tree_path_get_indices (path);
  depth = gtk_tree_path_get_depth (path);

  g_return_val_if_fail (depth > 0, FALSE);

  parent.stamp = priv->stamp;
  parent.user_data = priv->root;

  if (!gtk_tree_store_iter_nth_child (tree_model, iter, &parent, indices[0]))
    {
      iter->stamp = 0;
      return FALSE;
    }

  for (i = 1; i < depth; i++)
    {
      parent = *iter;
      if (!gtk_tree_store_iter_nth_child (tree_model, iter, &parent, indices[i]))
        {
          iter->stamp = 0;
          return FALSE;
        }
    }

  return TRUE;
}

static GtkTreePath *
gtk_tree_store_get_path (GtkTreeModel *tree_model,
    GtkTreeIter  *iter)
{
  GtkTreeStore *tree_store = (GtkTreeStore *) tree_model;
  GtkTreeStorePrivate *priv = tree_store->priv;
  GtkTreePath *retval;
  GNode *tmp_node;
  int i = 0;

  g_return_val_if_fail (iter->user_data != NULL, NULL);
  g_return_val_if_fail (iter->stamp == priv->stamp, NULL);

  validate_tree (tree_store);

  if (G_NODE (iter->user_data)->parent == NULL &&
      G_NODE (iter->user_data) == priv->root)
    return gtk_tree_path_new ();
  g_assert (G_NODE (iter->user_data)->parent != NULL);

  if (G_NODE (iter->user_data)->parent == G_NODE (priv->root))
    {
      retval = gtk_tree_path_new ();
      tmp_node = G_NODE (priv->root)->children;
    }
  else
    {
      GtkTreeIter tmp_iter = *iter;

      tmp_iter.user_data = G_NODE (iter->user_data)->parent;

      retval = gtk_tree_store_get_path (tree_model, &tmp_iter);
      tmp_node = G_NODE (iter->user_data)->parent->children;
    }

  if (retval == NULL)
    return NULL;

  if (tmp_node == NULL)
    {
      gtk_tree_path_free (retval);
      return NULL;
    }

  for (; tmp_node; tmp_node = tmp_node->next)
    {
      if (tmp_node == G_NODE (iter->user_data))
 break;
      i++;
    }

  if (tmp_node == NULL)
    {
      /* We couldn't find node, meaning it's prolly not ours */
      /* Perhaps I should do a g_return_if_fail here. */
      gtk_tree_path_free (retval);
      return NULL;
    }

  gtk_tree_path_append_index (retval, i);

  return retval;
}


static void
gtk_tree_store_get_value (GtkTreeModel *tree_model,
     GtkTreeIter  *iter,
     int           column,
     GValue       *value)
{
  GtkTreeStore *tree_store = (GtkTreeStore *) tree_model;
  GtkTreeStorePrivate *priv = tree_store->priv;
  GtkTreeDataList *list;
  int tmp_column = column;

  g_return_if_fail (column < priv->n_columns);
  g_return_if_fail (VALID_ITER (iter, tree_store));

  list = G_NODE (iter->user_data)->data;

  while (tmp_column-- > 0 && list)
    list = list->next;

  if (list)
    {
      _gtk_tree_data_list_node_to_value (list,
      priv->column_headers[column],
      value);
    }
  else
    {
      /* We want to return an initialized but empty (default) value */
      g_value_init (value, priv->column_headers[column]);
    }
}

static gboolean
gtk_tree_store_iter_next (GtkTreeModel  *tree_model,
     GtkTreeIter   *iter)
{
  g_return_val_if_fail (iter->user_data != NULL, FALSE);
  g_return_val_if_fail (iter->stamp == GTK_TREE_STORE (tree_model)->priv->stamp, FALSE);

  if (G_NODE (iter->user_data)->next == NULL)
    {
      iter->stamp = 0;
      return FALSE;
    }

  iter->user_data = G_NODE (iter->user_data)->next;

  return TRUE;
}

static gboolean
gtk_tree_store_iter_previous (GtkTreeModel *tree_model,
                              GtkTreeIter  *iter)
{
  g_return_val_if_fail (iter->user_data != NULL, FALSE);
  g_return_val_if_fail (iter->stamp == GTK_TREE_STORE (tree_model)->priv->stamp, FALSE);

  if (G_NODE (iter->user_data)->prev == NULL)
    {
      iter->stamp = 0;
      return FALSE;
    }

  iter->user_data = G_NODE (iter->user_data)->prev;

  return TRUE;
}

static gboolean
gtk_tree_store_iter_children (GtkTreeModel *tree_model,
         GtkTreeIter  *iter,
         GtkTreeIter  *parent)
{
  GtkTreeStore *tree_store = (GtkTreeStore *) tree_model;
  GtkTreeStorePrivate *priv = tree_store->priv;
  GNode *children;

  if (parent)
    g_return_val_if_fail (VALID_ITER (parent, tree_store), FALSE);

  if (parent)
    children = G_NODE (parent->user_data)->children;
  else
    children = G_NODE (priv->root)->children;

  if (children)
    {
      iter->stamp = priv->stamp;
      iter->user_data = children;
      return TRUE;
    }
  else
    {
      iter->stamp = 0;
      return FALSE;
    }
}

static gboolean
gtk_tree_store_iter_has_child (GtkTreeModel *tree_model,
          GtkTreeIter  *iter)
{
  g_return_val_if_fail (iter->user_data != NULL, FALSE);
  g_return_val_if_fail (VALID_ITER (iter, tree_model), FALSE);

  return G_NODE (iter->user_data)->children != NULL;
}

static int
gtk_tree_store_iter_n_children (GtkTreeModel *tree_model,
    GtkTreeIter  *iter)
{
  GNode *node;
  int i = 0;

  g_return_val_if_fail (iter == NULL || iter->user_data != NULL, 0);

  if (iter == NULL)
    node = G_NODE (GTK_TREE_STORE (tree_model)->priv->root)->children;
  else
    node = G_NODE (iter->user_data)->children;

  while (node)
    {
      i++;
      node = node->next;
    }

  return i;
}

static gboolean
gtk_tree_store_iter_nth_child (GtkTreeModel *tree_model,
          GtkTreeIter  *iter,
          GtkTreeIter  *parent,
          int           n)
{
  GtkTreeStore *tree_store = (GtkTreeStore *) tree_model;
  GtkTreeStorePrivate *priv = tree_store->priv;
  GNode *parent_node;
  GNode *child;

  g_return_val_if_fail (parent == NULL || parent->user_data != NULL, FALSE);

  if (parent == NULL)
    parent_node = priv->root;
  else
    parent_node = parent->user_data;

  child = g_node_nth_child (parent_node, n);

  if (child)
    {
      iter->user_data = child;
      iter->stamp = priv->stamp;
      return TRUE;
    }
  else
    {
      iter->stamp = 0;
      return FALSE;
    }
}

static gboolean
gtk_tree_store_iter_parent (GtkTreeModel *tree_model,
       GtkTreeIter  *iter,
       GtkTreeIter  *child)
{
  GtkTreeStore *tree_store = (GtkTreeStore *) tree_model;
  GtkTreeStorePrivate *priv = tree_store->priv;
  GNode *parent;

  g_return_val_if_fail (iter != NULL, FALSE);
  g_return_val_if_fail (VALID_ITER (child, tree_store), FALSE);

  parent = G_NODE (child->user_data)->parent;

  g_assert (parent != NULL);

  if (parent != priv->root)
    {
      iter->user_data = parent;
      iter->stamp = priv->stamp;
      return TRUE;
    }
  else
    {
      iter->stamp = 0;
      return FALSE;
    }
}


/* Does not emit a signal */
static gboolean
gtk_tree_store_real_set_value (GtkTreeStore *tree_store,
          GtkTreeIter  *iter,
          int           column,
          GValue       *value,
          gboolean      sort)
{
  GtkTreeStorePrivate *priv = tree_store->priv;
  GtkTreeDataList *list;
  GtkTreeDataList *prev;
  int old_column = column;
  GValue real_value = G_VALUE_INIT;
  gboolean converted = FALSE;
  gboolean retval = FALSE;

  if (! g_type_is_a (G_VALUE_TYPE (value), priv->column_headers[column]))
    {
      if (! (g_value_type_transformable (G_VALUE_TYPE (value), priv->column_headers[column])))
 {
   g_warning ("%s: Unable to convert from %s to %s",
       G_STRLOC,
       g_type_name (G_VALUE_TYPE (value)),
       g_type_name (priv->column_headers[column]));
   return retval;
 }

      g_value_init (&real_value, priv->column_headers[column]);
      if (!g_value_transform (value, &real_value))
 {
   g_warning ("%s: Unable to make conversion from %s to %s",
       G_STRLOC,
       g_type_name (G_VALUE_TYPE (value)),
       g_type_name (priv->column_headers[column]));
   g_value_unset (&real_value);
   return retval;
 }
      converted = TRUE;
    }

  prev = list = G_NODE (iter->user_data)->data;

  while (list != NULL)
    {
      if (column == 0)
 {
   if (converted)
     _gtk_tree_data_list_value_to_node (list, &real_value);
   else
     _gtk_tree_data_list_value_to_node (list, value);
   retval = TRUE;
   if (converted)
     g_value_unset (&real_value);
          if (sort && GTK_TREE_STORE_IS_SORTED (tree_store))
            gtk_tree_store_sort_iter_changed (tree_store, iter, old_column, TRUE);
   return retval;
 }

      column--;
      prev = list;
      list = list->next;
    }

  if (G_NODE (iter->user_data)->data == NULL)
    {
      G_NODE (iter->user_data)->data = list = _gtk_tree_data_list_alloc ();
      list->next = NULL;
    }
  else
    {
      list = prev->next = _gtk_tree_data_list_alloc ();
      list->next = NULL;
    }

  while (column != 0)
    {
      list->next = _gtk_tree_data_list_alloc ();
      list = list->next;
      list->next = NULL;
      column --;
    }

  if (converted)
    _gtk_tree_data_list_value_to_node (list, &real_value);
  else
    _gtk_tree_data_list_value_to_node (list, value);

  retval = TRUE;
  if (converted)
    g_value_unset (&real_value);

  if (sort && GTK_TREE_STORE_IS_SORTED (tree_store))
    gtk_tree_store_sort_iter_changed (tree_store, iter, old_column, TRUE);

  return retval;
}

/**
 * gtk_tree_store_set_value:
 * @tree_store: a `GtkTreeStore`
 * @iter: A valid `GtkTreeIter` for the row being modified
 * @column: column number to modify
 * @value: new value for the cell
 *
 * Sets the data in the cell specified by @iter and @column.
 *
 * The type of @value must be convertible to the type of the
 * column.
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 **/
void
gtk_tree_store_set_value (GtkTreeStore *tree_store,
     GtkTreeIter  *iter,
     int           column,
     GValue       *value)
{
  g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
  g_return_if_fail (VALID_ITER (iter, tree_store));
  g_return_if_fail (column >= 0 && column < tree_store->priv->n_columns);
  g_return_if_fail (G_IS_VALUE (value));

  if (gtk_tree_store_real_set_value (tree_store, iter, column, value, TRUE))
    {
      GtkTreePath *path;

      path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
      gtk_tree_model_row_changed (GTK_TREE_MODEL (tree_store), path, iter);
      gtk_tree_path_free (path);
    }
}

static GtkTreeIterCompareFunc
gtk_tree_store_get_compare_func (GtkTreeStore *tree_store)
{
  GtkTreeStorePrivate *priv = tree_store->priv;
  GtkTreeIterCompareFunc func = NULL;

  if (GTK_TREE_STORE_IS_SORTED (tree_store))
    {
      if (priv->sort_column_id != -1)
 {
   GtkTreeDataSortHeader *header;
   header = _gtk_tree_data_list_get_header (priv->sort_list,
         priv->sort_column_id);
   g_return_val_if_fail (header != NULL, NULL);
   g_return_val_if_fail (header->func != NULL, NULL);
   func = header->func;
 }
      else
 {
   func = priv->default_sort_func;
 }
    }

  return func;
}

static void
gtk_tree_store_set_vector_internal (GtkTreeStore *tree_store,
        GtkTreeIter  *iter,
        gboolean     *emit_signal,
        gboolean     *maybe_need_sort,
        int          *columns,
        GValue       *values,
        int           n_values)
{
  GtkTreeStorePrivate *priv = tree_store->priv;
  int i;
  GtkTreeIterCompareFunc func = NULL;

  func = gtk_tree_store_get_compare_func (tree_store);
  if (func != _gtk_tree_data_list_compare_func)
    *maybe_need_sort = TRUE;

  for (i = 0; i < n_values; i++)
    {
      *emit_signal = gtk_tree_store_real_set_value (tree_store, iter,
          columns[i], &values[i],
          FALSE) || *emit_signal;

      if (func == _gtk_tree_data_list_compare_func &&
   columns[i] == priv->sort_column_id)
 *maybe_need_sort = TRUE;
    }
}

static void
gtk_tree_store_set_valist_internal (GtkTreeStore *tree_store,
                                    GtkTreeIter  *iter,
                                    gboolean     *emit_signal,
                                    gboolean     *maybe_need_sort,
                                    va_list       var_args)
{
  GtkTreeStorePrivate *priv = tree_store->priv;
  int column;
  GtkTreeIterCompareFunc func = NULL;

  column = va_arg (var_args, int);

  func = gtk_tree_store_get_compare_func (tree_store);
  if (func != _gtk_tree_data_list_compare_func)
    *maybe_need_sort = TRUE;

  while (column != -1)
    {
      GValue value = G_VALUE_INIT;
      char *error = NULL;

      if (column < 0 || column >= priv->n_columns)
 {
   g_warning ("%s: Invalid column number %d added to iter (remember to end your list of columns with a -1)", G_STRLOC, column);
   break;
 }

      G_VALUE_COLLECT_INIT (&value, priv->column_headers[column],
                            var_args, 0, &error);
      if (error)
 {
   g_warning ("%s: %s", G_STRLOC, error);
   g_free (error);

    /* we purposely leak the value here, it might not be
    * in a sane state if an error condition occurred
   */
   break;
 }

      *emit_signal = gtk_tree_store_real_set_value (tree_store,
          iter,
          column,
          &value,
          FALSE) || *emit_signal;

      if (func == _gtk_tree_data_list_compare_func &&
   column == priv->sort_column_id)
 *maybe_need_sort = TRUE;

      g_value_unset (&value);

      column = va_arg (var_args, int);
    }
}

/**
 * gtk_tree_store_set_valuesv: (rename-to gtk_tree_store_set)
 * @tree_store: A `GtkTreeStore`
 * @iter: A valid `GtkTreeIter` for the row being modified
 * @columns: (array length=n_values): an array of column numbers
 * @values: (array length=n_values): an array of GValues
 * @n_values: the length of the @columns and @values arrays
 *
 * A variant of gtk_tree_store_set_valist() which takes
 * the columns and values as two arrays, instead of using variadic
 * arguments.
 *
 * This function is mainly intended for language bindings or in case
 * the number of columns to change is not known until run-time.
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 **/
void
gtk_tree_store_set_valuesv (GtkTreeStore *tree_store,
       GtkTreeIter  *iter,
       int          *columns,
       GValue       *values,
       int           n_values)
{
  GtkTreeStorePrivate *priv = tree_store->priv;
  gboolean emit_signal = FALSE;
  gboolean maybe_need_sort = FALSE;

  g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
  g_return_if_fail (VALID_ITER (iter, tree_store));

  gtk_tree_store_set_vector_internal (tree_store, iter,
          &emit_signal,
          &maybe_need_sort,
          columns, values, n_values);

  if (maybe_need_sort && GTK_TREE_STORE_IS_SORTED (tree_store))
    gtk_tree_store_sort_iter_changed (tree_store, iter, priv->sort_column_id, TRUE);

  if (emit_signal)
    {
      GtkTreePath *path;

      path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
      gtk_tree_model_row_changed (GTK_TREE_MODEL (tree_store), path, iter);
      gtk_tree_path_free (path);
    }
}

/**
 * gtk_tree_store_set_valist:
 * @tree_store: A `GtkTreeStore`
 * @iter: A valid `GtkTreeIter` for the row being modified
 * @var_args: va_list of column/value pairs
 *
 * A version of gtk_tree_store_set() using `va_list`.
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 **/
void
gtk_tree_store_set_valist (GtkTreeStore *tree_store,
                           GtkTreeIter  *iter,
                           va_list       var_args)
{
  GtkTreeStorePrivate *priv = tree_store->priv;
  gboolean emit_signal = FALSE;
  gboolean maybe_need_sort = FALSE;

  g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
  g_return_if_fail (VALID_ITER (iter, tree_store));

  gtk_tree_store_set_valist_internal (tree_store, iter,
          &emit_signal,
          &maybe_need_sort,
          var_args);

  if (maybe_need_sort && GTK_TREE_STORE_IS_SORTED (tree_store))
    gtk_tree_store_sort_iter_changed (tree_store, iter, priv->sort_column_id, TRUE);

  if (emit_signal)
    {
      GtkTreePath *path;

      path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
      gtk_tree_model_row_changed (GTK_TREE_MODEL (tree_store), path, iter);
      gtk_tree_path_free (path);
    }
}

/**
 * gtk_tree_store_set:
 * @tree_store: A `GtkTreeStore`
 * @iter: A valid `GtkTreeIter` for the row being modified
 * @...: pairs of column number and value, terminated with -1
 *
 * Sets the value of one or more cells in the row referenced by @iter.
 *
 * The variable argument list should contain integer column numbers,
 * each column number followed by the value to be set.
 *
 * The list is terminated by a value of `-1`.
 *
 * For example, to set column 0 with type `G_TYPE_STRING` to “Foo”, you would
 * write
 *
 * ```c
 * gtk_tree_store_set (store, iter, 0, "Foo", -1);
 * ```
 *
 * The value will be referenced by the store if it is a `G_TYPE_OBJECT`, and it
 * will be copied if it is a `G_TYPE_STRING` or `G_TYPE_BOXED`.
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 **/
void
gtk_tree_store_set (GtkTreeStore *tree_store,
      GtkTreeIter  *iter,
      ...)
{
  va_list var_args;

  va_start (var_args, iter);
  gtk_tree_store_set_valist (tree_store, iter, var_args);
  va_end (var_args);
}

/**
 * gtk_tree_store_remove:
 * @tree_store: A `GtkTreeStore`
 * @iter: A valid `GtkTreeIter`
 *
 * Removes @iter from @tree_store.
 *
 * After being removed, @iter is set to the next valid row at that level, or
 * invalidated if it previously pointed to the last one.
 *
 * Returns: true if @iter is still valid, and false otherwise
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 **/
gboolean
gtk_tree_store_remove (GtkTreeStore *tree_store,
         GtkTreeIter  *iter)
{
  GtkTreeStorePrivate *priv = tree_store->priv;
  GtkTreePath *path;
  GtkTreeIter new_iter = {0,};
  GNode *parent;
  GNode *next_node;

  g_return_val_if_fail (GTK_IS_TREE_STORE (tree_store), FALSE);
  g_return_val_if_fail (VALID_ITER (iter, tree_store), FALSE);

  parent = G_NODE (iter->user_data)->parent;

  g_assert (parent != NULL);
  next_node = G_NODE (iter->user_data)->next;

  if (G_NODE (iter->user_data)->data)
    g_node_traverse (G_NODE (iter->user_data), G_POST_ORDER, G_TRAVERSE_ALL,
       -1, node_free, priv->column_headers);

  path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
  g_node_destroy (G_NODE (iter->user_data));

  gtk_tree_model_row_deleted (GTK_TREE_MODEL (tree_store), path);

  if (parent != G_NODE (priv->root))
    {
      /* child_toggled */
      if (parent->children == NULL)
 {
   gtk_tree_path_up (path);

   new_iter.stamp = priv->stamp;
   new_iter.user_data = parent;
   gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (tree_store), path, &new_iter);
 }
    }
  gtk_tree_path_free (path);

  /* revalidate iter */
  if (next_node != NULL)
    {
      iter->stamp = priv->stamp;
      iter->user_data = next_node;
      return TRUE;
    }
  else
    {
      iter->stamp = 0;
      iter->user_data = NULL;
    }

  return FALSE;
}

/**
 * gtk_tree_store_insert:
 * @tree_store: A `GtkTreeStore`
 * @iter: (out): An unset `GtkTreeIter` to set to the new row
 * @parent: (nullable): A valid `GtkTreeIter`
 * @position: position to insert the new row, or -1 for last
 *
 * Creates a new row at @position.
 *
 * If parent is non-%NULL, then the row will be made a child of @parent.
 * Otherwise, the row will be created at the toplevel.
 *
 * If @position is `-1` or is larger than the number of rows at that level,
 * then the new row will be inserted to the end of the list.
 *
 * The @iter parameter will be changed to point to this new row. The row
 * will be empty after this function is called. To fill in values, you
 * need to call gtk_tree_store_set() or gtk_tree_store_set_value().
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 **/
void
gtk_tree_store_insert (GtkTreeStore *tree_store,
         GtkTreeIter  *iter,
         GtkTreeIter  *parent,
         int           position)
{
  GtkTreeStorePrivate *priv = tree_store->priv;
  GtkTreePath *path;
  GNode *parent_node;
  GNode *new_node;

  g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
  g_return_if_fail (iter != NULL);
  if (parent)
    g_return_if_fail (VALID_ITER (parent, tree_store));

  if (parent)
    parent_node = parent->user_data;
  else
    parent_node = priv->root;

  priv->columns_dirty = TRUE;

  new_node = g_node_new (NULL);

  iter->stamp = priv->stamp;
  iter->user_data = new_node;
  g_node_insert (parent_node, position, new_node);

  path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
  gtk_tree_model_row_inserted (GTK_TREE_MODEL (tree_store), path, iter);

  if (parent_node != priv->root)
    {
      if (new_node->prev == NULL && new_node->next == NULL)
        {
          gtk_tree_path_up (path);
          gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (tree_store), path, parent);
        }
    }

  gtk_tree_path_free (path);

  validate_tree ((GtkTreeStore*)tree_store);
}

/**
 * gtk_tree_store_insert_before:
 * @tree_store: A `GtkTreeStore`
 * @iter: (out): An unset `GtkTreeIter` to set to the new row
 * @parent: (nullable): A valid `GtkTreeIter`
 * @sibling: (nullable): A valid `GtkTreeIter`
 *
 * Inserts a new row before @sibling.
 *
 * If @sibling is %NULL, then the row will be appended to @parent’s children.
 *
 * If @parent and @sibling are %NULL, then the row will be appended to the
 * toplevel.
 *
 * If both @sibling and @parent are set, then @parent must be the parent
 * of @sibling. When @sibling is set, @parent is optional.
 *
 * The @iter parameter will be changed to point to this new row. The row will
 * be empty after this function is called. To fill in values, you need to call
 * gtk_tree_store_set() or gtk_tree_store_set_value().
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 **/
void
gtk_tree_store_insert_before (GtkTreeStore *tree_store,
         GtkTreeIter  *iter,
         GtkTreeIter  *parent,
         GtkTreeIter  *sibling)
{
  GtkTreeStorePrivate *priv = tree_store->priv;
  GtkTreePath *path;
  GNode *parent_node = NULL;
  GNode *new_node;

  g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
  g_return_if_fail (iter != NULL);
  if (parent != NULL)
    g_return_if_fail (VALID_ITER (parent, tree_store));
  if (sibling != NULL)
    g_return_if_fail (VALID_ITER (sibling, tree_store));

  if (parent == NULL && sibling == NULL)
    parent_node = priv->root;
  else if (parent == NULL)
    parent_node = G_NODE (sibling->user_data)->parent;
  else if (sibling == NULL)
    parent_node = G_NODE (parent->user_data);
  else
    {
      g_return_if_fail (G_NODE (sibling->user_data)->parent == G_NODE (parent->user_data));
      parent_node = G_NODE (parent->user_data);
    }

  priv->columns_dirty = TRUE;

  new_node = g_node_new (NULL);

  g_node_insert_before (parent_node,
   sibling ? G_NODE (sibling->user_data) : NULL,
                        new_node);

  iter->stamp = priv->stamp;
  iter->user_data = new_node;

  path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
  gtk_tree_model_row_inserted (GTK_TREE_MODEL (tree_store), path, iter);

  if (parent_node != priv->root)
    {
      if (new_node->prev == NULL && new_node->next == NULL)
        {
          GtkTreeIter parent_iter;

          parent_iter.stamp = priv->stamp;
          parent_iter.user_data = parent_node;

          gtk_tree_path_up (path);
          gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (tree_store), path, &parent_iter);
        }
    }

  gtk_tree_path_free (path);

  validate_tree (tree_store);
}

/**
 * gtk_tree_store_insert_after:
 * @tree_store: A `GtkTreeStore`
 * @iter: (out): An unset `GtkTreeIter` to set to the new row
 * @parent: (nullable): A valid `GtkTreeIter`
 * @sibling: (nullable): A valid `GtkTreeIter`
 *
 * Inserts a new row after @sibling.
 *
 * If @sibling is %NULL, then the row will be prepended to @parent’s children.
 *
 * If @parent and @sibling are %NULL, then the row will be prepended to the
 * toplevel.
 *
 * If both @sibling and @parent are set, then @parent must be the parent
 * of @sibling. When @sibling is set, @parent is optional.
 *
 * The @iter parameter will be changed to point to this new row. The row will
 * be empty after this function is called. To fill in values, you need to call
 * gtk_tree_store_set() or gtk_tree_store_set_value().
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 **/
void
gtk_tree_store_insert_after (GtkTreeStore *tree_store,
        GtkTreeIter  *iter,
        GtkTreeIter  *parent,
        GtkTreeIter  *sibling)
{
  GtkTreeStorePrivate *priv = tree_store->priv;
  GtkTreePath *path;
  GNode *parent_node;
  GNode *new_node;

  g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
  g_return_if_fail (iter != NULL);
  if (parent != NULL)
    g_return_if_fail (VALID_ITER (parent, tree_store));
  if (sibling != NULL)
    g_return_if_fail (VALID_ITER (sibling, tree_store));

  if (parent == NULL && sibling == NULL)
    parent_node = priv->root;
  else if (parent == NULL)
    parent_node = G_NODE (sibling->user_data)->parent;
  else if (sibling == NULL)
    parent_node = G_NODE (parent->user_data);
  else
    {
      g_return_if_fail (G_NODE (sibling->user_data)->parent ==
                        G_NODE (parent->user_data));
      parent_node = G_NODE (parent->user_data);
    }

  priv->columns_dirty = TRUE;

  new_node = g_node_new (NULL);

  g_node_insert_after (parent_node,
         sibling ? G_NODE (sibling->user_data) : NULL,
                       new_node);

  iter->stamp = priv->stamp;
  iter->user_data = new_node;

  path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
  gtk_tree_model_row_inserted (GTK_TREE_MODEL (tree_store), path, iter);

  if (parent_node != priv->root)
    {
      if (new_node->prev == NULL && new_node->next == NULL)
        {
          GtkTreeIter parent_iter;

          parent_iter.stamp = priv->stamp;
          parent_iter.user_data = parent_node;

          gtk_tree_path_up (path);
          gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (tree_store), path, &parent_iter);
        }
    }

  gtk_tree_path_free (path);

  validate_tree (tree_store);
}

/**
 * gtk_tree_store_insert_with_values:
 * @tree_store: A `GtkTreeStore`
 * @iter: (out) (optional): An unset `GtkTreeIter` to set the new row
 * @parent: (nullable): A valid `GtkTreeIter`
 * @position: position to insert the new row, or -1 to append after existing rows
 * @...: pairs of column number and value, terminated with -1
 *
 * Creates a new row at the given @position.
 *
 * The @iter parameter will be changed to point to this  new row.
 *
 * If @position is -1, or larger than the number of rows on the list, then
 * the new row will be appended to the list. The row will be filled with
 * the values given to this function.
 *
 * Calling
 *
 *     gtk_tree_store_insert_with_values (tree_store, iter, position, ...)
 *
 * has the same effect as calling
 *
 * ```c
 * gtk_tree_store_insert (tree_store, iter, position);
 * gtk_tree_store_set (tree_store, iter, ...);
 * ```
 *
 * with the different that the former will only emit a row_inserted signal,
 * while the latter will emit row_inserted, row_changed and if the tree store
 * is sorted, rows_reordered.
 *
 * Since emitting the rows_reordered signal repeatedly can affect the
 * performance of the program, gtk_tree_store_insert_with_values() should
 * generally be preferred when inserting rows in a sorted tree store.
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 */
void
gtk_tree_store_insert_with_values (GtkTreeStore *tree_store,
       GtkTreeIter  *iter,
       GtkTreeIter  *parent,
       int           position,
       ...)
{
  GtkTreeStorePrivate *priv = tree_store->priv;
  GtkTreePath *path;
  GNode *parent_node;
  GNode *new_node;
  GtkTreeIter tmp_iter;
  va_list var_args;
  gboolean changed = FALSE;
  gboolean maybe_need_sort = FALSE;

  g_return_if_fail (GTK_IS_TREE_STORE (tree_store));

  if (!iter)
    iter = &tmp_iter;

  if (parent)
    g_return_if_fail (VALID_ITER (parent, tree_store));

  if (parent)
    parent_node = parent->user_data;
  else
    parent_node = priv->root;

  priv->columns_dirty = TRUE;

  new_node = g_node_new (NULL);

  iter->stamp = priv->stamp;
  iter->user_data = new_node;
  g_node_insert (parent_node, position, new_node);

  va_start (var_args, position);
  gtk_tree_store_set_valist_internal (tree_store, iter,
          &changed, &maybe_need_sort,
          var_args);
  va_end (var_args);

  if (maybe_need_sort && GTK_TREE_STORE_IS_SORTED (tree_store))
    gtk_tree_store_sort_iter_changed (tree_store, iter, priv->sort_column_id, FALSE);

  path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
  gtk_tree_model_row_inserted (GTK_TREE_MODEL (tree_store), path, iter);

  if (parent_node != priv->root)
    {
      if (new_node->prev == NULL && new_node->next == NULL)
        {
   gtk_tree_path_up (path);
   gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (tree_store), path, parent);
 }
    }

  gtk_tree_path_free (path);

  validate_tree ((GtkTreeStore *)tree_store);
}

/**
 * gtk_tree_store_insert_with_valuesv: (rename-to gtk_tree_store_insert_with_values)
 * @tree_store: A `GtkTreeStore`
 * @iter: (out) (optional): An unset `GtkTreeIter` to set the new row
 * @parent: (nullable): A valid `GtkTreeIter`
 * @position: position to insert the new row, or -1 for last
 * @columns: (array length=n_values): an array of column numbers
 * @values: (array length=n_values): an array of GValues
 * @n_values: the length of the @columns and @values arrays
 *
 * A variant of gtk_tree_store_insert_with_values() which takes
 * the columns and values as two arrays, instead of varargs.
 *
 * This function is mainly intended for language bindings.
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 */
void
gtk_tree_store_insert_with_valuesv (GtkTreeStore *tree_store,
        GtkTreeIter  *iter,
        GtkTreeIter  *parent,
        int           position,
        int          *columns,
        GValue       *values,
        int           n_values)
{
  GtkTreeStorePrivate *priv = tree_store->priv;
  GtkTreePath *path;
  GNode *parent_node;
  GNode *new_node;
  GtkTreeIter tmp_iter;
  gboolean changed = FALSE;
  gboolean maybe_need_sort = FALSE;

  g_return_if_fail (GTK_IS_TREE_STORE (tree_store));

  if (!iter)
    iter = &tmp_iter;

  if (parent)
    g_return_if_fail (VALID_ITER (parent, tree_store));

  if (parent)
    parent_node = parent->user_data;
  else
    parent_node = priv->root;

  priv->columns_dirty = TRUE;

  new_node = g_node_new (NULL);

  iter->stamp = priv->stamp;
  iter->user_data = new_node;
  g_node_insert (parent_node, position, new_node);

  gtk_tree_store_set_vector_internal (tree_store, iter,
          &changed, &maybe_need_sort,
          columns, values, n_values);

  if (maybe_need_sort && GTK_TREE_STORE_IS_SORTED (tree_store))
    gtk_tree_store_sort_iter_changed (tree_store, iter, priv->sort_column_id, FALSE);

  path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
  gtk_tree_model_row_inserted (GTK_TREE_MODEL (tree_store), path, iter);

  if (parent_node != priv->root)
    {
      if (new_node->prev == NULL && new_node->next == NULL)
        {
   gtk_tree_path_up (path);
   gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (tree_store), path, parent);
 }
    }

  gtk_tree_path_free (path);

  validate_tree ((GtkTreeStore *)tree_store);
}

/**
 * gtk_tree_store_prepend:
 * @tree_store: A `GtkTreeStore`
 * @iter: (out): An unset `GtkTreeIter` to set to the prepended row
 * @parent: (nullable): A valid `GtkTreeIter`
 *
 * Prepends a new row to @tree_store.
 *
 * If @parent is non-%NULL, then it will prepend the new row before the first
 * child of @parent, otherwise it will prepend a row to the top level. The
 * `iter` parameter will be changed to point to this new row.  The row will
 * be empty after this function is called. To fill in values, you need to
 * call gtk_tree_store_set() or gtk_tree_store_set_value().
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 **/
void
gtk_tree_store_prepend (GtkTreeStore *tree_store,
   GtkTreeIter  *iter,
   GtkTreeIter  *parent)
{
  GtkTreeStorePrivate *priv = tree_store->priv;
  GNode *parent_node;

  g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
  g_return_if_fail (iter != NULL);
  if (parent != NULL)
    g_return_if_fail (VALID_ITER (parent, tree_store));

  priv->columns_dirty = TRUE;

  if (parent == NULL)
    parent_node = priv->root;
  else
    parent_node = parent->user_data;

  if (parent_node->children == NULL)
    {
      GtkTreePath *path;

      iter->stamp = priv->stamp;
      iter->user_data = g_node_new (NULL);

      g_node_prepend (parent_node, G_NODE (iter->user_data));

      path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
      gtk_tree_model_row_inserted (GTK_TREE_MODEL (tree_store), path, iter);

      if (parent_node != priv->root)
 {
   gtk_tree_path_up (path);
   gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (tree_store), path, parent);
 }
      gtk_tree_path_free (path);
    }
  else
    {
      gtk_tree_store_insert_after (tree_store, iter, parent, NULL);
    }

  validate_tree (tree_store);
}

/**
 * gtk_tree_store_append:
 * @tree_store: A `GtkTreeStore`
 * @iter: (out): An unset `GtkTreeIter` to set to the appended row
 * @parent: (nullable): A valid `GtkTreeIter`
 *
 * Appends a new row to @tree_store.
 *
 * If @parent is non-%NULL, then it will append the new row after the last
 * child of @parent, otherwise it will append a row to the top level.
 *
 * The @iter parameter will be changed to point to this new row. The row will
 * be empty after this function is called. To fill in values, you need to call
 * gtk_tree_store_set() or gtk_tree_store_set_value().
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 **/
void
gtk_tree_store_append (GtkTreeStore *tree_store,
         GtkTreeIter  *iter,
         GtkTreeIter  *parent)
{
  GtkTreeStorePrivate *priv = tree_store->priv;
  GNode *parent_node;

  g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
  g_return_if_fail (iter != NULL);
  if (parent != NULL)
    g_return_if_fail (VALID_ITER (parent, tree_store));

  if (parent == NULL)
    parent_node = priv->root;
  else
    parent_node = parent->user_data;

  priv->columns_dirty = TRUE;

  if (parent_node->children == NULL)
    {
      GtkTreePath *path;

      iter->stamp = priv->stamp;
      iter->user_data = g_node_new (NULL);

      g_node_append (parent_node, G_NODE (iter->user_data));

      path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
      gtk_tree_model_row_inserted (GTK_TREE_MODEL (tree_store), path, iter);

      if (parent_node != priv->root)
 {
   gtk_tree_path_up (path);
   gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (tree_store), path, parent);
 }
      gtk_tree_path_free (path);
    }
  else
    {
      gtk_tree_store_insert_before (tree_store, iter, parent, NULL);
    }

  validate_tree (tree_store);
}

/**
 * gtk_tree_store_is_ancestor:
 * @tree_store: A `GtkTreeStore`
 * @iter: A valid `GtkTreeIter`
 * @descendant: A valid `GtkTreeIter`
 *
 * Checks if @iter is an ancestor of @descendant.
 *
 * Returns: true if @iter is an ancestor of @descendant, and false otherwise
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 **/
gboolean
gtk_tree_store_is_ancestor (GtkTreeStore *tree_store,
       GtkTreeIter  *iter,
       GtkTreeIter  *descendant)
{
  g_return_val_if_fail (GTK_IS_TREE_STORE (tree_store), FALSE);
  g_return_val_if_fail (VALID_ITER (iter, tree_store), FALSE);
  g_return_val_if_fail (VALID_ITER (descendant, tree_store), FALSE);

  return g_node_is_ancestor (G_NODE (iter->user_data),
        G_NODE (descendant->user_data));
}


/**
 * gtk_tree_store_iter_depth:
 * @tree_store: A `GtkTreeStore`
 * @iter: A valid `GtkTreeIter`
 *
 * Returns the depth of the position pointed by the iterator
 *
 * The depth will be 0 for anything on the root level, 1 for anything down
 * a level, etc.
 *
 * Returns: The depth of the position pointed by the iterator
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 **/
int
gtk_tree_store_iter_depth (GtkTreeStore *tree_store,
      GtkTreeIter  *iter)
{
  g_return_val_if_fail (GTK_IS_TREE_STORE (tree_store), 0);
  g_return_val_if_fail (VALID_ITER (iter, tree_store), 0);

  return g_node_depth (G_NODE (iter->user_data)) - 2;
}

/* simple ripoff from g_node_traverse_post_order */
static gboolean
gtk_tree_store_clear_traverse (GNode        *node,
          GtkTreeStore *store)
{
  GtkTreeIter iter;

  if (node->children)
    {
      GNode *child;

      child = node->children;
      while (child)
        {
   register GNode *current;

   current = child;
   child = current->next;
   if (gtk_tree_store_clear_traverse (current, store))
     return TRUE;
 }

      if (node->parent)
        {
   iter.stamp = store->priv->stamp;
   iter.user_data = node;

   gtk_tree_store_remove (store, &iter);
 }
    }
  else if (node->parent)
    {
      iter.stamp = store->priv->stamp;
      iter.user_data = node;

      gtk_tree_store_remove (store, &iter);
    }

  return FALSE;
}

static void
gtk_tree_store_increment_stamp (GtkTreeStore *tree_store)
{
  GtkTreeStorePrivate *priv = tree_store->priv;
  do
    {
      priv->stamp++;
    }
  while (priv->stamp == 0);
}

/**
 * gtk_tree_store_clear:
 * @tree_store: a `GtkTreeStore`
 *
 * Removes all rows from @tree_store
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 **/
void
gtk_tree_store_clear (GtkTreeStore *tree_store)
{
  g_return_if_fail (GTK_IS_TREE_STORE (tree_store));

  gtk_tree_store_clear_traverse (tree_store->priv->root, tree_store);
  gtk_tree_store_increment_stamp (tree_store);
}

static gboolean
gtk_tree_store_iter_is_valid_helper (GtkTreeIter *iter,
         GNode       *first)
{
  GNode *node;

  node = first;

  do
    {
      if (node == iter->user_data)
 return TRUE;

      if (node->children)
 if (gtk_tree_store_iter_is_valid_helper (iter, node->children))
   return TRUE;

      node = node->next;
    }
  while (node);

  return FALSE;
}

/**
 * gtk_tree_store_iter_is_valid:
 * @tree_store: a tree store
 * @iter: the iterator to check
 *
 * Checks if the given iter is a valid iter for this `GtkTreeStore`.
 *
 * This function is slow. Only use it for debugging and/or testing
 * purposes.
 *
 * Returns: true if the iter is valid, and false otherwise
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 **/
gboolean
gtk_tree_store_iter_is_valid (GtkTreeStore *tree_store,
                              GtkTreeIter  *iter)
{
  g_return_val_if_fail (GTK_IS_TREE_STORE (tree_store), FALSE);
  g_return_val_if_fail (iter != NULL, FALSE);

  if (!VALID_ITER (iter, tree_store))
    return FALSE;

  return gtk_tree_store_iter_is_valid_helper (iter, tree_store->priv->root);
}

/* DND */


static gboolean real_gtk_tree_store_row_draggable (GtkTreeDragSource *drag_source,
                                                   GtkTreePath       *path)
{
  return TRUE;
}

static gboolean
gtk_tree_store_drag_data_delete (GtkTreeDragSource *drag_source,
                                 GtkTreePath       *path)
{
  GtkTreeIter iter;

  if (gtk_tree_store_get_iter (GTK_TREE_MODEL (drag_source),
                               &iter,
                               path))
    {
      gtk_tree_store_remove (GTK_TREE_STORE (drag_source),
                             &iter);
      return TRUE;
    }
  else
    {
      return FALSE;
    }
}

static GdkContentProvider *
gtk_tree_store_drag_data_get (GtkTreeDragSource *drag_source,
                              GtkTreePath       *path)
{
  /* Note that we don't need to handle the GTK_TREE_MODEL_ROW
   * target, because the default handler does it for us, but
   * we do anyway for the convenience of someone maybe overriding the
   * default handler.
   */
  return gtk_tree_create_row_drag_content (GTK_TREE_MODEL (drag_source), path);
}

static void
copy_node_data (GtkTreeStore *tree_store,
                GtkTreeIter  *src_iter,
                GtkTreeIter  *dest_iter)
{
  GtkTreeDataList *dl = G_NODE (src_iter->user_data)->data;
  GtkTreeDataList *copy_head = NULL;
  GtkTreeDataList *copy_prev = NULL;
  GtkTreeDataList *copy_iter = NULL;
  GtkTreePath *path;
  int col;

  col = 0;
  while (dl)
    {
      copy_iter = _gtk_tree_data_list_node_copy (dl, tree_store->priv->column_headers[col]);

      if (copy_head == NULL)
        copy_head = copy_iter;

      if (copy_prev)
        copy_prev->next = copy_iter;

      copy_prev = copy_iter;

      dl = dl->next;
      ++col;
    }

  G_NODE (dest_iter->user_data)->data = copy_head;

  path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), dest_iter);
  gtk_tree_model_row_changed (GTK_TREE_MODEL (tree_store), path, dest_iter);
  gtk_tree_path_free (path);
}

static void
recursive_node_copy (GtkTreeStore *tree_store,
                     GtkTreeIter  *src_iter,
                     GtkTreeIter  *dest_iter)
{
  GtkTreeIter child;
  GtkTreeModel *model;

  model = GTK_TREE_MODEL (tree_store);

  copy_node_data (tree_store, src_iter, dest_iter);

  if (gtk_tree_store_iter_children (model,
                                    &child,
                                    src_iter))
    {
      /* Need to create children and recurse. Note our
       * dependence on persistent iterators here.
       */
      do
        {
          GtkTreeIter copy;

          /* Gee, a really slow algorithm... ;-) FIXME */
          gtk_tree_store_append (tree_store,
                                 ©,
                                 dest_iter);

          recursive_node_copy (tree_store, &child, ©);
        }
      while (gtk_tree_store_iter_next (model, &child));
    }
}

static gboolean
gtk_tree_store_drag_data_received (GtkTreeDragDest *drag_dest,
                                   GtkTreePath     *dest,
                                   const GValue    *value)
{
  GtkTreeModel *tree_model;
  GtkTreeStore *tree_store;
  GtkTreeModel *src_model = NULL;
  GtkTreePath *src_path = NULL;
  gboolean retval = FALSE;

  tree_model = GTK_TREE_MODEL (drag_dest);
  tree_store = GTK_TREE_STORE (drag_dest);

  validate_tree (tree_store);

  if (gtk_tree_get_row_drag_data (value,
      &src_model,
      &src_path) &&
      src_model == tree_model)
    {
      /* Copy the given row to a new position */
      GtkTreeIter src_iter;
      GtkTreeIter dest_iter;
      GtkTreePath *prev;

      if (!gtk_tree_store_get_iter (src_model,
                                    &src_iter,
                                    src_path))
        {
          goto out;
        }

      /* Get the path to insert _after_ (dest is the path to insert _before_) */
      prev = gtk_tree_path_copy (dest);

      if (!gtk_tree_path_prev (prev))
        {
          GtkTreeIter dest_parent;
          GtkTreePath *parent;
          GtkTreeIter *dest_parent_p;

          /* dest was the first spot at the current depth; which means
           * we are supposed to prepend.
           */

          /* Get the parent, NULL if parent is the root */
          dest_parent_p = NULL;
          parent = gtk_tree_path_copy (dest);
          if (gtk_tree_path_up (parent) &&
       gtk_tree_path_get_depth (parent) > 0)
            {
              gtk_tree_store_get_iter (tree_model,
                                       &dest_parent,
                                       parent);
              dest_parent_p = &dest_parent;
            }
          g_clear_pointer (&parent, gtk_tree_path_free);

          gtk_tree_store_prepend (tree_store,
                                  &dest_iter,
                                  dest_parent_p);

          retval = TRUE;
        }
      else
        {
          if (gtk_tree_store_get_iter (tree_model, &dest_iter, prev))
            {
              GtkTreeIter tmp_iter = dest_iter;

              gtk_tree_store_insert_after (tree_store, &dest_iter, NULL,
                                           &tmp_iter);

              retval = TRUE;
            }
        }

      gtk_tree_path_free (prev);

      /* If we succeeded in creating dest_iter, walk src_iter tree branch,
       * duplicating it below dest_iter.
       */

      if (retval)
        {
          recursive_node_copy (tree_store,
                               &src_iter,
                               &dest_iter);
        }
    }
  else
    {
      /* FIXME maybe add some data targets eventually, or handle text
       * targets in the simple case.
       */

    }

 out:

  if (src_path)
    gtk_tree_path_free (src_path);

  return retval;
}

static gboolean
gtk_tree_store_row_drop_possible (GtkTreeDragDest *drag_dest,
                                  GtkTreePath     *dest_path,
      const GValue    *value)
{
  GtkTreeModel *src_model = NULL;
  GtkTreePath *src_path = NULL;
  GtkTreePath *tmp = NULL;
  gboolean retval = FALSE;

  /* don't accept drops if the tree has been sorted */
  if (GTK_TREE_STORE_IS_SORTED (drag_dest))
    return FALSE;

  if (!gtk_tree_get_row_drag_data (value,
       &src_model,
       &src_path))
    goto out;

  /* can only drag to ourselves */
  if (src_model != GTK_TREE_MODEL (drag_dest))
    goto out;

  /* Can't drop into ourself. */
  if (gtk_tree_path_is_ancestor (src_path,
                                 dest_path))
    goto out;

  /* Can't drop if dest_path's parent doesn't exist */
  {
    GtkTreeIter iter;

    if (gtk_tree_path_get_depth (dest_path) > 1)
      {
 tmp = gtk_tree_path_copy (dest_path);
 gtk_tree_path_up (tmp);

 if (!gtk_tree_store_get_iter (GTK_TREE_MODEL (drag_dest),
          &iter, tmp))
   goto out;
      }
  }

  /* Can otherwise drop anywhere. */
  retval = TRUE;

 out:

  if (src_path)
    gtk_tree_path_free (src_path);
  if (tmp)
    gtk_tree_path_free (tmp);

  return retval;
}

/* Sorting and reordering */
typedef struct _SortTuple
{
  int offset;
  GNode *node;
} SortTuple;

/* Reordering */
static int
gtk_tree_store_reorder_func (gconstpointer a,
        gconstpointer b,
        gpointer      user_data)
{
  SortTuple *a_reorder;
  SortTuple *b_reorder;

  a_reorder = (SortTuple *)a;
  b_reorder = (SortTuple *)b;

  if (a_reorder->offset < b_reorder->offset)
    return -1;
  if (a_reorder->offset > b_reorder->offset)
    return 1;

  return 0;
}

/**
 * gtk_tree_store_reorder: (skip)
 * @tree_store: A `GtkTreeStore`
 * @parent: (nullable): the parent of the children to re-order
 * @new_order: (array): an array of integers mapping the new position
 *   of each child to its old position before the re-ordering,
 *   i.e. `new_order[newpos] = oldpos`
 *
 * Reorders the children of @parent in @tree_store to follow the order
 * indicated by @new_order.
 *
 * Note that this function only works with unsorted stores.
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 */
void
gtk_tree_store_reorder (GtkTreeStore *tree_store,
   GtkTreeIter  *parent,
   int          *new_order)
{
  int i, length = 0;
  GNode *level, *node;
  GtkTreePath *path;
  SortTuple *sort_array;

  g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
  g_return_if_fail (!GTK_TREE_STORE_IS_SORTED (tree_store));
  g_return_if_fail (parent == NULL || VALID_ITER (parent, tree_store));
  g_return_if_fail (new_order != NULL);

  if (!parent)
    level = G_NODE (tree_store->priv->root)->children;
  else
    level = G_NODE (parent->user_data)->children;

  if (G_UNLIKELY (!level))
    {
      g_warning ("%s: Cannot reorder, parent has no children", G_STRLOC);
      return;
    }

  /* count nodes */
  node = level;
  while (node)
    {
      length++;
      node = node->next;
    }

  /* set up sortarray */
  sort_array = g_new (SortTuple, length);

  node = level;
  for (i = 0; i < length; i++)
    {
      sort_array[new_order[i]].offset = i;
      sort_array[i].node = node;

      node = node->next;
    }

  g_sort_array (sort_array, length, sizeof (SortTuple), gtk_tree_store_reorder_func, NULL);

  /* fix up level */
  for (i = 0; i < length - 1; i++)
    {
      sort_array[i].node->next = sort_array[i+1].node;
      sort_array[i+1].node->prev = sort_array[i].node;
    }

  sort_array[length-1].node->next = NULL;
  sort_array[0].node->prev = NULL;
  if (parent)
    G_NODE (parent->user_data)->children = sort_array[0].node;
  else
    G_NODE (tree_store->priv->root)->children = sort_array[0].node;

  /* emit signal */
  if (parent)
    path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), parent);
  else
    path = gtk_tree_path_new ();
  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_store), path,
     parent, new_order);
  gtk_tree_path_free (path);
  g_free (sort_array);
}

/**
 * gtk_tree_store_swap:
 * @tree_store: A `GtkTreeStore`.
 * @a: A `GtkTreeIter`.
 * @b: Another `GtkTreeIter`.
 *
 * Swaps @a and @b in the same level of @tree_store.
 *
 * Note that this function only works with unsorted stores.
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 **/
void
gtk_tree_store_swap (GtkTreeStore *tree_store,
       GtkTreeIter  *a,
       GtkTreeIter  *b)
{
  GNode *tmp, *node_a, *node_b, *parent_node;
  GNode *a_prev, *a_next, *b_prev, *b_next;
  int i, a_count, b_count, length, *order;
  GtkTreePath *path_a, *path_b;
  GtkTreeIter parent;

  g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
  g_return_if_fail (VALID_ITER (a, tree_store));
  g_return_if_fail (VALID_ITER (b, tree_store));

  node_a = G_NODE (a->user_data);
  node_b = G_NODE (b->user_data);

  /* basic sanity checking */
  if (node_a == node_b)
    return;

  path_a = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), a);
  path_b = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), b);

  g_return_if_fail (path_a && path_b);

  gtk_tree_path_up (path_a);
  gtk_tree_path_up (path_b);

  if (gtk_tree_path_get_depth (path_a) == 0
      || gtk_tree_path_get_depth (path_b) == 0)
    {
      if (gtk_tree_path_get_depth (path_a) != gtk_tree_path_get_depth (path_b))
        {
          gtk_tree_path_free (path_a);
          gtk_tree_path_free (path_b);

          g_warning ("Given children are not in the same level\n");
          return;
        }
      parent_node = G_NODE (tree_store->priv->root);
    }
  else
    {
      if (gtk_tree_path_compare (path_a, path_b))
        {
          gtk_tree_path_free (path_a);
          gtk_tree_path_free (path_b);

          g_warning ("Given children don't have a common parent\n");
          return;
        }
      gtk_tree_store_get_iter (GTK_TREE_MODEL (tree_store), &parent,
                               path_a);
      parent_node = G_NODE (parent.user_data);
    }
  gtk_tree_path_free (path_b);

  /* old links which we have to keep around */
  a_prev = node_a->prev;
  a_next = node_a->next;

  b_prev = node_b->prev;
  b_next = node_b->next;

  /* fix up links if the nodes are next to each other */
  if (a_prev == node_b)
    a_prev = node_a;
  if (a_next == node_b)
    a_next = node_a;

  if (b_prev == node_a)
    b_prev = node_b;
  if (b_next == node_a)
    b_next = node_b;

  /* counting nodes */
  tmp = parent_node->children;
  i = a_count = b_count = 0;
  while (tmp)
    {
      if (tmp == node_a)
 a_count = i;
      if (tmp == node_b)
 b_count = i;

      tmp = tmp->next;
      i++;
    }
  length = i;

  /* hacking the tree */
  if (!a_prev)
    parent_node->children = node_b;
  else
    a_prev->next = node_b;

  if (a_next)
    a_next->prev = node_b;

  if (!b_prev)
    parent_node->children = node_a;
  else
    b_prev->next = node_a;

  if (b_next)
    b_next->prev = node_a;

  node_a->prev = b_prev;
  node_a->next = b_next;

  node_b->prev = a_prev;
  node_b->next = a_next;

  /* emit signal */
  order = g_new (int, length);
  for (i = 0; i < length; i++)
    if (i == a_count)
      order[i] = b_count;
    else if (i == b_count)
      order[i] = a_count;
    else
      order[i] = i;

  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_store), path_a,
     parent_node == tree_store->priv->root
     ? NULL : &parent, order);
  gtk_tree_path_free (path_a);
  g_free (order);
}

/* WARNING: this function is *incredibly* fragile. Please smashtest after
 * making changes here.
 * -Kris
 */
static void
gtk_tree_store_move (GtkTreeStore *tree_store,
                     GtkTreeIter  *iter,
       GtkTreeIter  *position,
       gboolean      before)
{
  GNode *parent, *node, *a, *b, *tmp, *tmp_a, *tmp_b;
  int old_pos, new_pos, length, i, *order;
  GtkTreePath *path = NULL, *tmppath, *pos_path = NULL;
  GtkTreeIter parent_iter = { 0, };
  GtkTreeIter dst_a = { 0, };
  GtkTreeIter dst_b = { 0, };
  int depth = 0;
  gboolean handle_b = TRUE;

  g_return_if_fail (GTK_IS_TREE_STORE (tree_store));
  g_return_if_fail (!GTK_TREE_STORE_IS_SORTED (tree_store));
  g_return_if_fail (VALID_ITER (iter, tree_store));
  if (position)
    g_return_if_fail (VALID_ITER (position, tree_store));

  a = b = NULL;

  /* sanity checks */
  if (position)
    {
      path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
      pos_path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store),
                                   position);

      /* if before:
       *   moving the iter before path or "path + 1" doesn't make sense
       * else
       *   moving the iter before path or "path - 1" doesn't make sense
       */
      if (!gtk_tree_path_compare (path, pos_path))
 goto free_paths_and_out;

      if (before)
        gtk_tree_path_next (path);
      else
        gtk_tree_path_prev (path);

      if (!gtk_tree_path_compare (path, pos_path))
 goto free_paths_and_out;

      if (before)
        gtk_tree_path_prev (path);
      else
        gtk_tree_path_next (path);

      if (gtk_tree_path_get_depth (path) != gtk_tree_path_get_depth (pos_path))
        {
          g_warning ("Given children are not in the same level\n");

   goto free_paths_and_out;
        }

      tmppath = gtk_tree_path_copy (pos_path);
      gtk_tree_path_up (path);
      gtk_tree_path_up (tmppath);

      if (gtk_tree_path_get_depth (path) > 0 &&
   gtk_tree_path_compare (path, tmppath))
        {
          g_warning ("Given children are not in the same level\n");

          gtk_tree_path_free (tmppath);
   goto free_paths_and_out;
        }

      gtk_tree_path_free (tmppath);
    }

  if (!path)
    {
      path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), iter);
      gtk_tree_path_up (path);
    }

  depth = gtk_tree_path_get_depth (path);

  if (depth)
    {
      gtk_tree_store_get_iter (GTK_TREE_MODEL (tree_store),
          &parent_iter, path);

      parent = G_NODE (parent_iter.user_data);
    }
  else
    parent = G_NODE (tree_store->priv->root);

  /* yes, I know that this can be done shorter, but I'm doing it this way
   * so the code is also maintainable
   */

  if (before && position)
    {
      b = G_NODE (position->user_data);

      if (gtk_tree_path_get_indices (pos_path)[gtk_tree_path_get_depth (pos_path) - 1] > 0)
        {
          gtk_tree_path_prev (pos_path);
          if (gtk_tree_store_get_iter (GTK_TREE_MODEL (tree_store),
           &dst_a, pos_path))
            a = G_NODE (dst_a.user_data);
          else
            a = NULL;
          gtk_tree_path_next (pos_path);
 }

      /* if b is NULL, a is NULL too -- we are at the beginning of the list
       * yes and we leak memory here ...
       */
      g_return_if_fail (b);
    }
  else if (before && !position)
    {
      /* move before without position is appending */
      a = NULL;
      b = NULL;
    }
  else /* !before */
    {
      if (position)
        a = G_NODE (position->user_data);
      else
        a = NULL;

      if (position)
        {
          gtk_tree_path_next (pos_path);
          if (gtk_tree_store_get_iter (GTK_TREE_MODEL (tree_store), &dst_b, pos_path))
             b = G_NODE (dst_b.user_data);
          else
             b = NULL;
          gtk_tree_path_prev (pos_path);
 }
      else
        {
   /* move after without position is prepending */
   if (depth)
     gtk_tree_store_iter_children (GTK_TREE_MODEL (tree_store), &dst_b,
                                   &parent_iter);
   else
     gtk_tree_store_iter_children (GTK_TREE_MODEL (tree_store), &dst_b,
                            NULL);

   b = G_NODE (dst_b.user_data);
 }

      /* if a is NULL, b is NULL too -- we are at the end of the list
       * yes and we leak memory here ...
       */
      if (position)
        g_return_if_fail (a);
    }

  /* counting nodes */
  tmp = parent->children;

  length = old_pos = 0;
  while (tmp)
    {
      if (tmp == iter->user_data)
 old_pos = length;

      tmp = tmp->next;
      length++;
    }

  /* remove node from list */
  node = G_NODE (iter->user_data);
  tmp_a = node->prev;
  tmp_b = node->next;

  if (tmp_a)
    tmp_a->next = tmp_b;
  else
    parent->children = tmp_b;

  if (tmp_b)
    tmp_b->prev = tmp_a;

  /* and reinsert the node */
  if (a)
    {
      tmp = a->next;

      a->next = node;
      node->next = tmp;
      node->prev = a;
    }
  else if (!a && !before)
    {
      tmp = parent->children;

      node->prev = NULL;
      parent->children = node;

      node->next = tmp;
      if (tmp)
 tmp->prev = node;

      handle_b = FALSE;
    }
  else if (!a && before)
    {
      if (!position)
        {
          node->parent = NULL;
          node->next = node->prev = NULL;

          /* before with sibling = NULL appends */
          g_node_insert_before (parent, NULL, node);
 }
      else
        {
   node->parent = NULL;
   node->next = node->prev = NULL;

   /* after with sibling = NULL prepends */
   g_node_insert_after (parent, NULL, node);
 }

      handle_b = FALSE;
    }

  if (handle_b)
    {
      if (b)
        {
          tmp = b->prev;

          b->prev = node;
          node->prev = tmp;
          node->next = b;
        }
      else if (!(!a && before)) /* !a && before is completely handled above */
        node->next = NULL;
    }

  /* emit signal */
  if (position)
    new_pos = gtk_tree_path_get_indices (pos_path)[gtk_tree_path_get_depth (pos_path)-1];
  else if (before)
    {
      if (depth)
        new_pos = gtk_tree_store_iter_n_children (GTK_TREE_MODEL (tree_store),
                                           &parent_iter) - 1;
      else
 new_pos = gtk_tree_store_iter_n_children (GTK_TREE_MODEL (tree_store),
                                           NULL) - 1;
    }
  else
    new_pos = 0;

  if (new_pos > old_pos)
    {
      if (before && position)
        new_pos--;
    }
  else
    {
      if (!before && position)
        new_pos++;
    }

  order = g_new (int, length);
  if (new_pos > old_pos)
    {
      for (i = 0; i < length; i++)
        if (i < old_pos)
          order[i] = i;
        else if (i >= old_pos && i < new_pos)
          order[i] = i + 1;
        else if (i == new_pos)
          order[i] = old_pos;
        else
   order[i] = i;
    }
  else
    {
      for (i = 0; i < length; i++)
        if (i == new_pos)
   order[i] = old_pos;
        else if (i > new_pos && i <= old_pos)
   order[i] = i - 1;
 else
   order[i] = i;
    }

  if (depth)
    {
      tmppath = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store),
      &parent_iter);
      gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_store),
         tmppath, &parent_iter, order);
    }
  else
    {
      tmppath = gtk_tree_path_new ();
      gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_store),
         tmppath, NULL, order);
    }

  gtk_tree_path_free (tmppath);
  gtk_tree_path_free (path);
  if (position)
    gtk_tree_path_free (pos_path);
  g_free (order);

  return;

free_paths_and_out:
  gtk_tree_path_free (path);
  gtk_tree_path_free (pos_path);
}

/**
 * gtk_tree_store_move_before:
 * @tree_store: A `GtkTreeStore`
 * @iter: A `GtkTreeIter`
 * @position: (nullable): A `GtkTreeIter`
 *
 * Moves @iter in @tree_store to the position before @position.
 *
 * @iter and @position should be in the same level.
 *
 * Note that this function only works with unsorted stores.
 *
 * If @position is %NULL, @iter will be moved to the end of the level.
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 **/
void
gtk_tree_store_move_before (GtkTreeStore *tree_store,
                            GtkTreeIter  *iter,
       GtkTreeIter  *position)
{
  gtk_tree_store_move (tree_store, iter, position, TRUE);
}

/**
 * gtk_tree_store_move_after:
 * @tree_store: A `GtkTreeStore`
 * @iter: A `GtkTreeIter`.
 * @position: (nullable): A `GtkTreeIter`.
 *
 * Moves @iter in @tree_store to the position after @position.
 *
 * @iter and @position should be in the same level.
 *
 * Note that this function only works with unsorted stores.
 *
 * If @position is %NULL, @iter will be moved to the start of the level.
 *
 * Deprecated: 4.10: Use [class@Gtk.TreeListModel] instead
 **/
void
gtk_tree_store_move_after (GtkTreeStore *tree_store,
                           GtkTreeIter  *iter,
      GtkTreeIter  *position)
{
  gtk_tree_store_move (tree_store, iter, position, FALSE);
}

/* Sorting */
static int
gtk_tree_store_compare_func (gconstpointer a,
        gconstpointer b,
        gpointer      user_data)
{
  GtkTreeStore *tree_store = user_data;
  GtkTreeStorePrivate *priv = tree_store->priv;
  GNode *node_a;
  GNode *node_b;
  GtkTreeIterCompareFunc func;
  gpointer data;

  GtkTreeIter iter_a;
  GtkTreeIter iter_b;
  int retval;

  if (priv->sort_column_id != -1)
    {
      GtkTreeDataSortHeader *header;

      header = _gtk_tree_data_list_get_header (priv->sort_list,
            priv->sort_column_id);
      g_return_val_if_fail (header != NULL, 0);
      g_return_val_if_fail (header->func != NULL, 0);

      func = header->func;
      data = header->data;
    }
  else
    {
      g_return_val_if_fail (priv->default_sort_func != NULL, 0);
      func = priv->default_sort_func;
      data = priv->default_sort_data;
    }

  node_a = ((SortTuple *) a)->node;
  node_b = ((SortTuple *) b)->node;

  iter_a.stamp = priv->stamp;
  iter_a.user_data = node_a;
  iter_b.stamp = priv->stamp;
  iter_b.user_data = node_b;

  retval = (* func) (GTK_TREE_MODEL (user_data), &iter_a, &iter_b, data);

  if (priv->order == GTK_SORT_DESCENDING)
    {
      if (retval > 0)
 retval = -1;
      else if (retval < 0)
 retval = 1;
    }
  return retval;
}

static void
gtk_tree_store_sort_helper (GtkTreeStore *tree_store,
       GNode        *parent,
       gboolean      recurse)
{
  GtkTreeIter iter;
  GArray *sort_array;
  GNode *node;
  GNode *tmp_node;
  int list_length;
  int i;
  int *new_order;
  GtkTreePath *path;

  node = parent->children;
  if (node == NULL || node->next == NULL)
    {
      if (recurse && node && node->children)
        gtk_tree_store_sort_helper (tree_store, node, TRUE);

      return;
    }

  list_length = 0;
  for (tmp_node = node; tmp_node; tmp_node = tmp_node->next)
    list_length++;

  sort_array = g_array_sized_new (FALSE, FALSE, sizeof (SortTuple), list_length);

  i = 0;
  for (tmp_node = node; tmp_node; tmp_node = tmp_node->next)
    {
      SortTuple tuple;

      tuple.offset = i;
      tuple.node = tmp_node;
      g_array_append_val (sort_array, tuple);
      i++;
    }

  /* Sort the array */
  g_array_sort_with_data (sort_array, gtk_tree_store_compare_func, tree_store);

  for (i = 0; i < list_length - 1; i++)
    {
      g_array_index (sort_array, SortTuple, i).node->next =
 g_array_index (sort_array, SortTuple, i + 1).node;
      g_array_index (sort_array, SortTuple, i + 1).node->prev =
 g_array_index (sort_array, SortTuple, i).node;
    }
  g_array_index (sort_array, SortTuple, list_length - 1).node->next = NULL;
  g_array_index (sort_array, SortTuple, 0).node->prev = NULL;
  parent->children = g_array_index (sort_array, SortTuple, 0).node;

  /* Let the world know about our new order */
  new_order = g_new (int, list_length);
  for (i = 0; i < list_length; i++)
    new_order[i] = g_array_index (sort_array, SortTuple, i).offset;

  iter.stamp = tree_store->priv->stamp;
  iter.user_data = parent;
  path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), &iter);
  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_store),
     path, &iter, new_order);
  gtk_tree_path_free (path);
  g_free (new_order);
  g_array_free (sort_array, TRUE);

  if (recurse)
    {
      for (tmp_node = parent->children; tmp_node; tmp_node = tmp_node->next)
 {
   if (tmp_node->children)
     gtk_tree_store_sort_helper (tree_store, tmp_node, TRUE);
 }
    }
}

static void
gtk_tree_store_sort (GtkTreeStore *tree_store)
{
  GtkTreeStorePrivate *priv = tree_store->priv;

  if (!GTK_TREE_STORE_IS_SORTED (tree_store))
    return;

  if (priv->sort_column_id != -1)
    {
      GtkTreeDataSortHeader *header = NULL;

      header = _gtk_tree_data_list_get_header (priv->sort_list,
            priv->sort_column_id);

      /* We want to make sure that we have a function */
      g_return_if_fail (header != NULL);
      g_return_if_fail (header->func != NULL);
    }
  else
    {
      g_return_if_fail (priv->default_sort_func != NULL);
    }

  gtk_tree_store_sort_helper (tree_store, G_NODE (priv->root), TRUE);
}

static void
gtk_tree_store_sort_iter_changed (GtkTreeStore *tree_store,
      GtkTreeIter  *iter,
      int           column,
      gboolean      emit_signal)
{
  GtkTreeStorePrivate *priv = tree_store->priv;
  GNode *prev = NULL;
  GNode *next = NULL;
  GNode *node;
  GtkTreePath *tmp_path;
  GtkTreeIter tmp_iter;
  int cmp_a = 0;
  int cmp_b = 0;
  int i;
  int old_location;
  int new_location;
  int *new_order;
  int length;
  GtkTreeIterCompareFunc func;
  gpointer data;

  g_return_if_fail (G_NODE (iter->user_data)->parent != NULL);

  tmp_iter.stamp = priv->stamp;
  if (priv->sort_column_id != -1)
    {
      GtkTreeDataSortHeader *header;
      header = _gtk_tree_data_list_get_header (priv->sort_list,
            priv->sort_column_id);
      g_return_if_fail (header != NULL);
      g_return_if_fail (header->func != NULL);
      func = header->func;
      data = header->data;
    }
  else
    {
      g_return_if_fail (priv->default_sort_func != NULL);
      func = priv->default_sort_func;
      data = priv->default_sort_data;
    }

  /* If it's the built in function, we don't sort. */
  if (func == _gtk_tree_data_list_compare_func &&
      priv->sort_column_id != column)
    return;

  old_location = 0;
  node = G_NODE (iter->user_data)->parent->children;
  /* First we find the iter, its prev, and its next */
  while (node)
    {
      if (node == G_NODE (iter->user_data))
 break;
      old_location++;
      node = node->next;
    }
  g_assert (node != NULL);

  prev = node->prev;
  next = node->next;

  /* Check the common case, where we don't need to sort it moved. */
  if (prev != NULL)
    {
      tmp_iter.user_data = prev;
      cmp_a = (* func) (GTK_TREE_MODEL (tree_store), &tmp_iter, iter, data);
    }

  if (next != NULL)
    {
      tmp_iter.user_data = next;
      cmp_b = (* func) (GTK_TREE_MODEL (tree_store), iter, &tmp_iter, data);
    }

  if (priv->order == GTK_SORT_DESCENDING)
    {
      if (cmp_a < 0)
 cmp_a = 1;
      else if (cmp_a > 0)
 cmp_a = -1;

      if (cmp_b < 0)
 cmp_b = 1;
      else if (cmp_b > 0)
 cmp_b = -1;
    }

  if (prev == NULL && cmp_b <= 0)
    return;
  else if (next == NULL && cmp_a <= 0)
    return;
  else if (prev != NULL && next != NULL &&
    cmp_a <= 0 && cmp_b <= 0)
    return;

  /* We actually need to sort it */
  /* First, remove the old link. */

  if (prev)
    prev->next = next;
  else
    node->parent->children = next;

  if (next)
    next->prev = prev;

  node->prev = NULL;
  node->next = NULL;

  /* FIXME: as an optimization, we can potentially start at next */
  prev = NULL;
  node = node->parent->children;
  new_location = 0;
  tmp_iter.user_data = node;
  if (priv->order == GTK_SORT_DESCENDING)
    cmp_a = (* func) (GTK_TREE_MODEL (tree_store), &tmp_iter, iter, data);
  else
    cmp_a = (* func) (GTK_TREE_MODEL (tree_store), iter, &tmp_iter, data);

  while ((node->next) && (cmp_a > 0))
    {
      prev = node;
      node = node->next;
      new_location++;
      tmp_iter.user_data = node;
      if (priv->order == GTK_SORT_DESCENDING)
 cmp_a = (* func) (GTK_TREE_MODEL (tree_store), &tmp_iter, iter, data);
      else
 cmp_a = (* func) (GTK_TREE_MODEL (tree_store), iter, &tmp_iter, data);
    }

  if ((!node->next) && (cmp_a > 0))
    {
      new_location++;
      node->next = G_NODE (iter->user_data);
      node->next->prev = node;
    }
  else if (prev)
    {
      prev->next = G_NODE (iter->user_data);
      prev->next->prev = prev;
      G_NODE (iter->user_data)->next = node;
      G_NODE (iter->user_data)->next->prev = G_NODE (iter->user_data);
    }
  else
    {
      G_NODE (iter->user_data)->next = G_NODE (iter->user_data)->parent->children;
      G_NODE (iter->user_data)->next->prev = G_NODE (iter->user_data);
      G_NODE (iter->user_data)->parent->children = G_NODE (iter->user_data);
    }

  if (!emit_signal)
    return;

  /* Emit the reordered signal. */
  length = g_node_n_children (node->parent);
  new_order = g_new (int, length);
  if (old_location < new_location)
    for (i = 0; i < length; i++)
      {
 if (i < old_location ||
     i > new_location)
   new_order[i] = i;
 else if (i >= old_location &&
   i < new_location)
   new_order[i] = i + 1;
 else if (i == new_location)
   new_order[i] = old_location;
      }
  else
    for (i = 0; i < length; i++)
      {
 if (i < new_location ||
     i > old_location)
   new_order[i] = i;
 else if (i > new_location &&
   i <= old_location)
   new_order[i] = i - 1;
 else if (i == new_location)
   new_order[i] = old_location;
      }

  tmp_iter.user_data = node->parent;
  tmp_path = gtk_tree_store_get_path (GTK_TREE_MODEL (tree_store), &tmp_iter);

  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_store),
     tmp_path, &tmp_iter,
     new_order);

  gtk_tree_path_free (tmp_path);
  g_free (new_order);
}


static gboolean
gtk_tree_store_get_sort_column_id (GtkTreeSortable  *sortable,
       int              *sort_column_id,
       GtkSortType      *order)
{
  GtkTreeStore *tree_store = (GtkTreeStore *) sortable;
  GtkTreeStorePrivate *priv = tree_store->priv;

  if (sort_column_id)
    * sort_column_id = priv->sort_column_id;
  if (order)
    * order = priv->order;

  if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID ||
      priv->sort_column_id == GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID)
    return FALSE;

  return TRUE;
}

static void
gtk_tree_store_set_sort_column_id (GtkTreeSortable  *sortable,
       int               sort_column_id,
       GtkSortType       order)
{
  GtkTreeStore *tree_store = (GtkTreeStore *) sortable;
  GtkTreeStorePrivate *priv = tree_store->priv;

  if ((priv->sort_column_id == sort_column_id) &&
      (priv->order == order))
    return;

  if (sort_column_id != GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID)
    {
      if (sort_column_id != GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
 {
   GtkTreeDataSortHeader *header = NULL;

   header = _gtk_tree_data_list_get_header (priv->sort_list,
         sort_column_id);

   /* We want to make sure that we have a function */
   g_return_if_fail (header != NULL);
   g_return_if_fail (header->func != NULL);
 }
      else
 {
   g_return_if_fail (priv->default_sort_func != NULL);
 }
    }

  priv->sort_column_id = sort_column_id;
  priv->order = order;

  gtk_tree_sortable_sort_column_changed (sortable);

  gtk_tree_store_sort (tree_store);
}

static void
gtk_tree_store_set_sort_func (GtkTreeSortable        *sortable,
         int                     sort_column_id,
         GtkTreeIterCompareFunc  func,
         gpointer                data,
         GDestroyNotify          destroy)
{
  GtkTreeStore *tree_store = (GtkTreeStore *) sortable;
  GtkTreeStorePrivate *priv = tree_store->priv;

  priv->sort_list = _gtk_tree_data_list_set_header (priv->sort_list,
          sort_column_id,
          func, data, destroy);

  if (priv->sort_column_id == sort_column_id)
    gtk_tree_store_sort (tree_store);
}

static void
gtk_tree_store_set_default_sort_func (GtkTreeSortable        *sortable,
          GtkTreeIterCompareFunc  func,
          gpointer                data,
          GDestroyNotify          destroy)
{
  GtkTreeStore *tree_store = (GtkTreeStore *) sortable;
  GtkTreeStorePrivate *priv = tree_store->priv;

  if (priv->default_sort_destroy)
    {
      GDestroyNotify d = priv->default_sort_destroy;

      priv->default_sort_destroy = NULL;
      d (priv->default_sort_data);
    }

  priv->default_sort_func = func;
  priv->default_sort_data = data;
  priv->default_sort_destroy = destroy;

  if (priv->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID)
    gtk_tree_store_sort (tree_store);
}

static gboolean
gtk_tree_store_has_default_sort_func (GtkTreeSortable *sortable)
{
  GtkTreeStore *tree_store = (GtkTreeStore *) sortable;

  return (tree_store->priv->default_sort_func != NULL);
}

static void
validate_gnode (GNode* node)
{
  GNode *iter;

  iter = node->children;
  while (iter != NULL)
    {
      g_assert (iter->parent == node);
      if (iter->prev)
        g_assert (iter->prev->next == iter);
      validate_gnode (iter);
      iter = iter->next;
    }
}

/* GtkBuildable custom tag implementation
 *
 * <columns>
 *   <column type="..."/>
 *   <column type="..."/>
 * </columns>
 */
typedef struct {
  gboolean translatable;
  char *context;
  int id;
} ColInfo;

typedef struct {
  GtkBuilder *builder;
  GObject *object;
  GSList *column_type_names;
  GType *column_types;
  GValue *values;
  int *colids;
  ColInfo **columns;
  int last_row;
  int n_columns;
  int row_column;
  gboolean is_data;
  const char *domain;
  GList *parents;
  gboolean row_is_open;
} SubParserData;

static void
append_current_row (SubParserData *data)
{
  GtkTreeIter *parent;
  GtkTreeIter iter;
  int i;

  if (data->parents)
    parent = data->parents->data;
  else
    parent = NULL;

  gtk_tree_store_insert_with_valuesv (GTK_TREE_STORE (data->object),
                                      &iter,
                                      parent,
                                      -1,
                                      data->colids,
                                      data->values,
                                      data->row_column);

  data->parents = g_list_prepend (data->parents, gtk_tree_iter_copy (&iter));

  for (i = 0; i < data->row_column; i++)
    {
      ColInfo *info = data->columns[i];
      g_free (info->context);
      g_slice_free (ColInfo, info);
      data->columns[i] = NULL;
      g_value_unset (&data->values[i]);
    }
  g_free (data->values);
  data->values = g_new0 (GValue, data->n_columns);
  data->last_row++;
  data->row_column = 0;
  data->row_is_open = FALSE;
}

static void
tree_store_start_element (GtkBuildableParseContext  *context,
                          const char                *element_name,
                          const char               **names,
                          const char               **values,
                          gpointer                   user_data,
                          GError                   **error)
{
  SubParserData *data = (SubParserData*)user_data;

  if (strcmp (element_name, "col") == 0)
    {
      int id = -1;
      const char *id_str;
      const char *msg_context = NULL;
      gboolean translatable = FALSE;
      ColInfo *info;
      GValue val = G_VALUE_INIT;

      if (!_gtk_builder_check_parent (data->builder, context, "row", error))
        return;

      if (!data->row_is_open)
        {
          g_set_error (error,
                       GTK_BUILDER_ERROR,
                       GTK_BUILDER_ERROR_INVALID_TAG,
                       "Can't use <col> here");
          _gtk_builder_prefix_error (data->builder, context, error);
          return;
        }

      if (data->row_column >= data->n_columns)
        {
          g_set_error (error,
                       GTK_BUILDER_ERROR, GTK_BUILDER_ERROR_INVALID_VALUE,
                       "Too many columns, maximum is %d", data->n_columns - 1);
          _gtk_builder_prefix_error (data->builder, context, error);
          return;
        }

      if (!g_markup_collect_attributes (element_name, names, values, error,
                                        G_MARKUP_COLLECT_STRING, "id", &id_str,
                                        G_MARKUP_COLLECT_BOOLEAN|G_MARKUP_COLLECT_OPTIONAL, "translatable", &translatable,
                                        G_MARKUP_COLLECT_STRING|G_MARKUP_COLLECT_OPTIONAL, "comments", NULL,
                                        G_MARKUP_COLLECT_STRING|G_MARKUP_COLLECT_OPTIONAL, "context", &msg_context,
                                        G_MARKUP_COLLECT_INVALID))
        {
          _gtk_builder_prefix_error (data->builder, context, error);
          return;
        }

     if (!gtk_builder_value_from_string_type (data->builder, G_TYPE_INT, id_str, &val, error))
        {
          _gtk_builder_prefix_error (data->builder, context, error);
          return;
        }

      id = g_value_get_int (&val);
      if (id < 0 || id >= data->n_columns)
        {
          g_set_error (error,
                       GTK_BUILDER_ERROR, GTK_BUILDER_ERROR_INVALID_VALUE,
                       "id value %d out of range", id);
          _gtk_builder_prefix_error (data->builder, context, error);
          return;
        }

      info = g_slice_new0 (ColInfo);
      info->translatable = translatable;
      info->context = g_strdup (msg_context);
      info->id = id;

      data->colids[data->row_column] = id;
      data->columns[data->row_column] = info;
      data->row_column++;
      data->is_data = TRUE;
    }
  else if (strcmp (element_name, "row") == 0)
    {
      if (!_gtk_builder_check_parents (data->builder, context, error, "data", "row", NULL))
        return;

      if (data->row_is_open)
        append_current_row (data);

      if (!g_markup_collect_attributes (element_name, names, values, error,
                                        G_MARKUP_COLLECT_INVALID, NULL, NULL,
                                        G_MARKUP_COLLECT_INVALID))
        _gtk_builder_prefix_error (data->builder, context, error);

      data->row_is_open = TRUE;
    }
  else if (strcmp (element_name, "columns") == 0 ||
           strcmp (element_name, "data") == 0)
    {
      if (!_gtk_builder_check_parent (data->builder, context, "object", error))
        return;

      if (!g_markup_collect_attributes (element_name, names, values, error,
                                        G_MARKUP_COLLECT_INVALID, NULL, NULL,
                                        G_MARKUP_COLLECT_INVALID))
        _gtk_builder_prefix_error (data->builder, context, error);
    }
  else if (strcmp (element_name, "column") == 0)
    {
      const char *type;

      if (!_gtk_builder_check_parent (data->builder, context, "columns", error))
        return;

      if (!g_markup_collect_attributes (element_name, names, values, error,
                                        G_MARKUP_COLLECT_STRING, "type", &type,
                                        G_MARKUP_COLLECT_INVALID))
        {
          _gtk_builder_prefix_error (data->builder, context, error);
          return;
        }

      data->column_type_names = g_slist_prepend (data->column_type_names, g_strdup (type));
    }

  else
    {
      _gtk_builder_error_unhandled_tag (data->builder, context,
                                        "GtkTreeStore", element_name,
                                        error);
    }
}

static void
tree_store_end_element (GtkBuildableParseContext  *context,
                        const char                *element_name,
                        gpointer                   user_data,
                        GError                   **error)
{
  SubParserData *data = (SubParserData*)user_data;

  g_assert(data->builder);

  if (strcmp (element_name, "row") == 0)
    {
      GtkTreeIter *parent;

      if (data->row_column > 0)
        append_current_row (data);

      parent = data->parents->data;
      data->parents = g_list_remove (data->parents, parent);
      gtk_tree_iter_free (parent);
    }
  else if (strcmp (element_name, "columns") == 0)
    {
      GType *column_types;
      GSList *l;
      int i;
      GType type;

      data = (SubParserData*)user_data;
      data->column_type_names = g_slist_reverse (data->column_type_names);
      column_types = g_new0 (GType, g_slist_length (data->column_type_names));

      for (l = data->column_type_names, i = 0; l; l = l->next, i++)
        {
          type = gtk_builder_get_type_from_name (data->builder, l->data);
          if (type == G_TYPE_INVALID)
            {
              g_warning ("Unknown type %s specified in treemodel %s",
                         (const char *)l->data,
                         gtk_buildable_get_buildable_id (GTK_BUILDABLE (data->object)));
              continue;
            }
          column_types[i] = type;

          g_free (l->data);
        }

      gtk_tree_store_set_column_types (GTK_TREE_STORE (data->object), i, column_types);

      g_free (column_types);
    }
  else if (strcmp (element_name, "col") == 0)
    {
      data->is_data = FALSE;
    }
}

static void
tree_store_text (GtkBuildableParseContext  *context,
                 const char                *text,
                 gsize                      text_len,
                 gpointer                   user_data,
                 GError                   **error)
{
  SubParserData *data = (SubParserData*)user_data;
  int i;
  char *string;
  ColInfo *info;

  if (!data->is_data)
    return;

  i = data->row_column - 1;
  info = data->columns[i];

  string = g_strndup (text, text_len);
  if (info->translatable && text_len)
    {
      char *translated;

      /* FIXME: This will not use the domain set in the .ui file,
       * since the parser is not telling the builder about the domain.
       * However, it will work for gtk_builder_set_translation_domain() calls.
       */
      translated = g_strdup (_gtk_builder_parser_translate (data->domain,
                                                            info->context,
                                                            string));
      g_free (string);
      string = translated;
    }

  if (!gtk_builder_value_from_string_type (data->builder,
                                           data->column_types[info->id],
                                           string,
                                           &data->values[i],
                                           error))
    {
      _gtk_builder_prefix_error (data->builder, context, error);
    }
  g_free (string);
}

static const GtkBuildableParser tree_store_parser =
{
  tree_store_start_element,
  tree_store_end_element,
  tree_store_text
};

static gboolean
gtk_tree_store_buildable_custom_tag_start (GtkBuildable       *buildable,
                                           GtkBuilder         *builder,
                                           GObject            *child,
                                           const char         *tagname,
                                           GtkBuildableParser *parser,
                                           gpointer           *parser_data)
{
  SubParserData *data;

  if (child)
    return FALSE;

  if (strcmp (tagname, "columns") == 0)
    {
      data = g_slice_new0 (SubParserData);
      data->builder = builder;
      data->column_type_names = NULL;
      data->object = G_OBJECT (buildable);

      *parser = tree_store_parser;
      *parser_data = data;

      return TRUE;
    }
  else if (strcmp (tagname, "data") == 0)
    {
      int n_columns = gtk_tree_store_get_n_columns (GTK_TREE_MODEL (buildable));
      if (n_columns == 0)
        g_error ("Cannot append data to an empty model");

      data = g_slice_new0 (SubParserData);
      data->builder = builder;
      data->object = G_OBJECT (buildable);
      data->values = g_new0 (GValue, n_columns);
      data->colids = g_new0 (int, n_columns);
      data->columns = g_new0 (ColInfo *, n_columns);
      data->column_types = GTK_TREE_STORE (buildable)->priv->column_headers;
      data->n_columns = n_columns;
      data->last_row = 0;
      data->domain = gtk_builder_get_translation_domain (builder);

      *parser = tree_store_parser;
      *parser_data = data;

      return TRUE;
    }

  return FALSE;
}

static void
gtk_tree_store_buildable_custom_tag_end (GtkBuildable *buildable,
                                         GtkBuilder   *builder,
                                         GObject      *child,
                                         const char   *tagname,
                                         gpointer      parser_data)
{
  SubParserData *data = (SubParserData*)parser_data;

  if (strcmp (tagname, "columns") == 0)
    {
      g_slist_free (data->column_type_names);
      g_slice_free (SubParserData, data);
    }
  else if (strcmp (tagname, "data") == 0)
    {
      int i;
      for (i = 0; i < data->n_columns; i++)
        {
          ColInfo *info = data->columns[i];
          if (info)
            {
              g_free (info->context);
              g_slice_free (ColInfo, info);
            }
        }
      g_free (data->colids);
      g_free (data->columns);
      g_free (data->values);
      g_slice_free (SubParserData, data);
    }
}