gtktreemodelsort.c 74.9 KB
Newer Older
1
/* gtktreemodelsort.c
2
 * Copyright (C) 2000,2001  Red Hat, Inc.,  Jonathan Blandford <jrb@redhat.com>
3
 * Copyright (C) 2001,2002  Kristian Rietveld <kris@gtk.org>
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
 *
 * 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, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

21
/* NOTE: There is a potential for confusion in this code as to whether an iter,
22 23
 * path or value refers to the GtkTreeModelSort model, or the child model being
 * sorted.  As a convention, variables referencing the child model will have an
24 25 26
 * s_ prefix before them (ie. s_iter, s_value, s_path);
 */

27 28 29 30 31 32 33
/* ITER FORMAT:
 *
 * iter->stamp = tree_model_sort->stamp
 * iter->user_data = SortLevel
 * iter->user_data2 = SortElt
 */

34 35 36 37 38 39
/* WARNING: this code is dangerous, can cause sleepless nights,
 * can cause your dog to die among other bad things
 *
 * we warned you and we're not liable for any head injuries.
 */

40
#include <config.h>
Manish Singh's avatar
Manish Singh committed
41 42
#include <string.h>

43
#include "gtktreemodelsort.h"
44
#include "gtktreesortable.h"
45
#include "gtktreestore.h"
46
#include "gtktreedatalist.h"
47
#include "gtkintl.h"
48
#include "gtkprivate.h"
49
#include "gtktreednd.h"
50
#include "gtkalias.h"
51 52

typedef struct _SortElt SortElt;
53 54 55 56
typedef struct _SortLevel SortLevel;
typedef struct _SortData SortData;
typedef struct _SortTuple SortTuple;

57 58
struct _SortElt
{
59 60 61 62 63 64 65 66 67 68 69 70 71
  GtkTreeIter  iter;
  SortLevel   *children;
  gint         offset;
  gint         ref_count;
  gint         zero_ref_count;
};

struct _SortLevel
{
  GArray    *array;
  gint       ref_count;
  SortElt   *parent_elt;
  SortLevel *parent_level;
72 73
};

Jonathan Blandford's avatar
Jonathan Blandford committed
74 75
struct _SortData
{
76
  GtkTreeModelSort *tree_model_sort;
77 78 79 80 81
  GtkTreePath *parent_path;
  gint parent_path_depth;
  gint *parent_path_indices;
  GtkTreeIterCompareFunc sort_func;
  gpointer sort_data;
Jonathan Blandford's avatar
Jonathan Blandford committed
82 83
};

84 85 86
struct _SortTuple
{
  SortElt   *elt;
87
  gint       offset;
88
};
89

90 91 92 93 94 95 96 97 98
/* Properties */
enum {
  PROP_0,
  /* Construct args */
  PROP_MODEL
};



99 100 101 102 103
#define GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS(tree_model_sort) \
	(((GtkTreeModelSort *)tree_model_sort)->child_flags&GTK_TREE_MODEL_ITERS_PERSIST)
#define SORT_ELT(sort_elt) ((SortElt *)sort_elt)
#define SORT_LEVEL(sort_level) ((SortLevel *)sort_level)

104
#define GET_CHILD_ITER(tree_model_sort,ch_iter,so_iter) gtk_tree_model_sort_convert_iter_to_child_iter(GTK_TREE_MODEL_SORT (tree_model_sort), ch_iter, so_iter);
105

106 107
#define NO_SORT_FUNC ((GtkTreeIterCompareFunc) 0x1)

Kristian Rietveld's avatar
Kristian Rietveld committed
108 109
#define VALID_ITER(iter, tree_model_sort) (iter != NULL && iter->user_data != NULL && iter->user_data2 != NULL && tree_model_sort->stamp == iter->stamp)

110
/* general (object/interface init, etc) */
111 112 113 114
static void gtk_tree_model_sort_init                  (GtkTreeModelSort      *tree_model_sort);
static void gtk_tree_model_sort_class_init            (GtkTreeModelSortClass *tree_model_sort_class);
static void gtk_tree_model_sort_tree_model_init       (GtkTreeModelIface     *iface);
static void gtk_tree_model_sort_tree_sortable_init    (GtkTreeSortableIface  *iface);
115
static void gtk_tree_model_sort_drag_source_init      (GtkTreeDragSourceIface*iface);
116
static void gtk_tree_model_sort_finalize              (GObject               *object);
117 118 119 120 121 122 123 124
static void gtk_tree_model_sort_set_property          (GObject               *object,
						       guint                  prop_id,
						       const GValue          *value,
						       GParamSpec            *pspec);
static void gtk_tree_model_sort_get_property          (GObject               *object,
						       guint                  prop_id,
						       GValue                *value,
						       GParamSpec            *pspec);
125

126
/* our signal handlers */
127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146
static void gtk_tree_model_sort_row_changed           (GtkTreeModel          *model,
						       GtkTreePath           *start_path,
						       GtkTreeIter           *start_iter,
						       gpointer               data);
static void gtk_tree_model_sort_row_inserted          (GtkTreeModel          *model,
						       GtkTreePath           *path,
						       GtkTreeIter           *iter,
						       gpointer               data);
static void gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel          *model,
						       GtkTreePath           *path,
						       GtkTreeIter           *iter,
						       gpointer               data);
static void gtk_tree_model_sort_row_deleted           (GtkTreeModel          *model,
						       GtkTreePath           *path,
						       gpointer               data);
static void gtk_tree_model_sort_rows_reordered        (GtkTreeModel          *s_model,
						       GtkTreePath           *s_path,
						       GtkTreeIter           *s_iter,
						       gint                  *new_order,
						       gpointer               data);
147 148

/* TreeModel interface */
149
static GtkTreeModelFlags gtk_tree_model_sort_get_flags     (GtkTreeModel          *tree_model);
150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179
static gint         gtk_tree_model_sort_get_n_columns      (GtkTreeModel          *tree_model);
static GType        gtk_tree_model_sort_get_column_type    (GtkTreeModel          *tree_model,
                                                            gint                   index);
static gboolean     gtk_tree_model_sort_get_iter           (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            GtkTreePath           *path);
static GtkTreePath *gtk_tree_model_sort_get_path           (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
static void         gtk_tree_model_sort_get_value          (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            gint                   column,
                                                            GValue                *value);
static gboolean     gtk_tree_model_sort_iter_next          (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
static gboolean     gtk_tree_model_sort_iter_children      (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            GtkTreeIter           *parent);
static gboolean     gtk_tree_model_sort_iter_has_child     (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
static gint         gtk_tree_model_sort_iter_n_children    (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
static gboolean     gtk_tree_model_sort_iter_nth_child     (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            GtkTreeIter           *parent,
                                                            gint                   n);
static gboolean     gtk_tree_model_sort_iter_parent        (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
                                                            GtkTreeIter           *child);
static void         gtk_tree_model_sort_ref_node           (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);
180 181 182
static void         gtk_tree_model_sort_real_unref_node    (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
							    gboolean               propagate_unref);
183 184 185
static void         gtk_tree_model_sort_unref_node         (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);

186 187 188 189 190 191 192 193 194
/* TreeDragSource interface */
static gboolean     gtk_tree_model_sort_row_draggable         (GtkTreeDragSource      *drag_source,
                                                               GtkTreePath            *path);
static gboolean     gtk_tree_model_sort_drag_data_get         (GtkTreeDragSource      *drag_source,
                                                               GtkTreePath            *path,
							       GtkSelectionData       *selection_data);
static gboolean     gtk_tree_model_sort_drag_data_delete      (GtkTreeDragSource      *drag_source,
                                                               GtkTreePath            *path);

195
/* TreeSortable interface */
196 197 198 199 200 201 202 203 204 205 206
static gboolean     gtk_tree_model_sort_get_sort_column_id    (GtkTreeSortable        *sortable,
							       gint                   *sort_column_id,
							       GtkSortType            *order);
static void         gtk_tree_model_sort_set_sort_column_id    (GtkTreeSortable        *sortable,
							       gint                    sort_column_id,
							       GtkSortType        order);
static void         gtk_tree_model_sort_set_sort_func         (GtkTreeSortable        *sortable,
							       gint                    sort_column_id,
							       GtkTreeIterCompareFunc  func,
							       gpointer                data,
							       GtkDestroyNotify        destroy);
207 208 209 210 211
static void         gtk_tree_model_sort_set_default_sort_func (GtkTreeSortable        *sortable,
							       GtkTreeIterCompareFunc  func,
							       gpointer                data,
							       GtkDestroyNotify        destroy);
static gboolean     gtk_tree_model_sort_has_default_sort_func (GtkTreeSortable     *sortable);
212

213
/* Private functions (sort funcs, level handling and other utils) */
214 215 216 217 218 219 220 221 222 223 224
static void         gtk_tree_model_sort_build_level       (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *parent_level,
							   SortElt          *parent_elt);
static void         gtk_tree_model_sort_free_level        (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *sort_level);
static void         gtk_tree_model_sort_increment_stamp   (GtkTreeModelSort *tree_model_sort);
static void         gtk_tree_model_sort_sort_level        (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *level,
							   gboolean          recurse,
							   gboolean          emit_reordered);
static void         gtk_tree_model_sort_sort              (GtkTreeModelSort *tree_model_sort);
225 226 227
static gint         gtk_tree_model_sort_level_find_insert (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *level,
							   GtkTreeIter      *iter,
Kristian Rietveld's avatar
Kristian Rietveld committed
228
							   gint             skip_index);
229
static gboolean     gtk_tree_model_sort_insert_value      (GtkTreeModelSort *tree_model_sort,
230
							   SortLevel        *level,
231 232
							   GtkTreePath      *s_path,
							   GtkTreeIter      *s_iter);
233 234 235 236
static GtkTreePath *gtk_tree_model_sort_elt_get_path      (SortLevel        *level,
							   SortElt          *elt);
static void         gtk_tree_model_sort_set_model         (GtkTreeModelSort *tree_model_sort,
							   GtkTreeModel     *child_model);
237 238 239
static GtkTreePath *gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
									 GtkTreePath      *child_path,
									 gboolean          build_levels);
240

241
static GObjectClass *parent_class = NULL;
242

243
GType
244 245
gtk_tree_model_sort_get_type (void)
{
246
  static GType tree_model_sort_type = 0;
247

248 249 250 251 252
  if (!tree_model_sort_type)
    {
      static const GTypeInfo tree_model_sort_info =
      {
        sizeof (GtkTreeModelSortClass),
253 254
        NULL,           /* base_init */
        NULL,           /* base_finalize */
255
        (GClassInitFunc) gtk_tree_model_sort_class_init,
256 257
        NULL,           /* class_finalize */
        NULL,           /* class_data */
258
        sizeof (GtkTreeModelSort),
259
        0,              /* n_preallocs */
260 261 262 263 264
        (GInstanceInitFunc) gtk_tree_model_sort_init
      };

      static const GInterfaceInfo tree_model_info =
      {
265 266 267
        (GInterfaceInitFunc) gtk_tree_model_sort_tree_model_init,
        NULL,
        NULL
268 269
      };

270 271
      static const GInterfaceInfo sortable_info =
      {
272 273 274
        (GInterfaceInitFunc) gtk_tree_model_sort_tree_sortable_init,
        NULL,
        NULL
275 276
      };

277 278 279 280 281 282 283
      static const GInterfaceInfo drag_source_info =
      {
        (GInterfaceInitFunc) gtk_tree_model_sort_drag_source_init,
        NULL,
        NULL
      };

Manish Singh's avatar
Manish Singh committed
284
      tree_model_sort_type =
285
	g_type_register_static (G_TYPE_OBJECT, I_("GtkTreeModelSort"),
Manish Singh's avatar
Manish Singh committed
286 287
				&tree_model_sort_info, 0);

288
      g_type_add_interface_static (tree_model_sort_type,
289 290
                                   GTK_TYPE_TREE_MODEL,
                                   &tree_model_info);
291

292
      g_type_add_interface_static (tree_model_sort_type,
293 294
                                   GTK_TYPE_TREE_SORTABLE,
                                   &sortable_info);
295 296 297 298

      g_type_add_interface_static (tree_model_sort_type,
                                   GTK_TYPE_TREE_DRAG_SOURCE,
                                   &drag_source_info);
299 300 301 302 303 304
    }

  return tree_model_sort_type;
}

static void
305 306 307 308 309 310 311 312 313 314 315
gtk_tree_model_sort_init (GtkTreeModelSort *tree_model_sort)
{
  tree_model_sort->sort_column_id = GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID;
  tree_model_sort->stamp = 0;
  tree_model_sort->zero_ref_count = 0;
  tree_model_sort->root = NULL;
  tree_model_sort->sort_list = NULL;
}

static void
gtk_tree_model_sort_class_init (GtkTreeModelSortClass *class)
316 317 318
{
  GObjectClass *object_class;

319
  object_class = (GObjectClass *) class;
320
  parent_class = g_type_class_peek_parent (class);
321

322 323 324
  object_class->set_property = gtk_tree_model_sort_set_property;
  object_class->get_property = gtk_tree_model_sort_get_property;

325
  object_class->finalize = gtk_tree_model_sort_finalize;
326 327 328 329 330

  /* Properties */
  g_object_class_install_property (object_class,
                                   PROP_MODEL,
                                   g_param_spec_object ("model",
331 332
							P_("TreeModelSort Model"),
							P_("The model for the TreeModelSort to sort"),
333
							GTK_TYPE_TREE_MODEL,
334
							GTK_PARAM_READWRITE | G_PARAM_CONSTRUCT_ONLY));
335 336 337 338 339
}

static void
gtk_tree_model_sort_tree_model_init (GtkTreeModelIface *iface)
{
340
  iface->get_flags = gtk_tree_model_sort_get_flags;
341 342 343 344 345 346 347 348 349 350 351
  iface->get_n_columns = gtk_tree_model_sort_get_n_columns;
  iface->get_column_type = gtk_tree_model_sort_get_column_type;
  iface->get_iter = gtk_tree_model_sort_get_iter;
  iface->get_path = gtk_tree_model_sort_get_path;
  iface->get_value = gtk_tree_model_sort_get_value;
  iface->iter_next = gtk_tree_model_sort_iter_next;
  iface->iter_children = gtk_tree_model_sort_iter_children;
  iface->iter_has_child = gtk_tree_model_sort_iter_has_child;
  iface->iter_n_children = gtk_tree_model_sort_iter_n_children;
  iface->iter_nth_child = gtk_tree_model_sort_iter_nth_child;
  iface->iter_parent = gtk_tree_model_sort_iter_parent;
352 353
  iface->ref_node = gtk_tree_model_sort_ref_node;
  iface->unref_node = gtk_tree_model_sort_unref_node;
354 355
}

356 357 358 359 360
static void
gtk_tree_model_sort_tree_sortable_init (GtkTreeSortableIface *iface)
{
  iface->get_sort_column_id = gtk_tree_model_sort_get_sort_column_id;
  iface->set_sort_column_id = gtk_tree_model_sort_set_sort_column_id;
361
  iface->set_sort_func = gtk_tree_model_sort_set_sort_func;
362 363
  iface->set_default_sort_func = gtk_tree_model_sort_set_default_sort_func;
  iface->has_default_sort_func = gtk_tree_model_sort_has_default_sort_func;
364 365
}

366 367 368 369 370 371 372 373
static void
gtk_tree_model_sort_drag_source_init (GtkTreeDragSourceIface *iface)
{
  iface->row_draggable = gtk_tree_model_sort_row_draggable;
  iface->drag_data_delete = gtk_tree_model_sort_drag_data_delete;
  iface->drag_data_get = gtk_tree_model_sort_drag_data_get;
}

374 375 376 377
/**
 * gtk_tree_model_sort_new_with_model:
 * @child_model: A #GtkTreeModel
 *
Matthias Clasen's avatar
Matthias Clasen committed
378
 * Creates a new #GtkTreeModel, with @child_model as the child model.
379 380 381
 *
 * Return value: A new #GtkTreeModel.
 */
382
GtkTreeModel *
383
gtk_tree_model_sort_new_with_model (GtkTreeModel      *child_model)
384 385 386
{
  GtkTreeModel *retval;

387 388
  g_return_val_if_fail (GTK_IS_TREE_MODEL (child_model), NULL);

Manish Singh's avatar
Manish Singh committed
389
  retval = g_object_new (gtk_tree_model_sort_get_type (), NULL);
390

391
  gtk_tree_model_sort_set_model (GTK_TREE_MODEL_SORT (retval), child_model);
392 393 394 395

  return retval;
}

396 397 398
/* GObject callbacks */
static void
gtk_tree_model_sort_finalize (GObject *object)
399
{
400
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) object;
401

402 403
  gtk_tree_model_sort_set_model (tree_model_sort, NULL);

404
  if (tree_model_sort->root)
405
    gtk_tree_model_sort_free_level (tree_model_sort, tree_model_sort->root);
406 407 408 409 410 411

  if (tree_model_sort->sort_list)
    {
      _gtk_tree_data_list_header_free (tree_model_sort->sort_list);
      tree_model_sort->sort_list = NULL;
    }
412 413 414

  /* must chain up */
  parent_class->finalize (object);
415 416
}

417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454
static void
gtk_tree_model_sort_set_property (GObject      *object,
				  guint         prop_id,
				  const GValue *value,
				  GParamSpec   *pspec)
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (object);

  switch (prop_id)
    {
    case PROP_MODEL:
      gtk_tree_model_sort_set_model (tree_model_sort, g_value_get_object (value));
      break;
    default:
      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
      break;
    }
}

static void
gtk_tree_model_sort_get_property (GObject    *object,
				  guint       prop_id,
				  GValue     *value,
				  GParamSpec *pspec)
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (object);

  switch (prop_id)
    {
    case PROP_MODEL:
      g_value_set_object (value, gtk_tree_model_sort_get_model(tree_model_sort));
      break;
    default:
      G_OBJECT_WARN_INVALID_PROPERTY_ID (object, prop_id, pspec);
      break;
    }
}

455
static void
456
gtk_tree_model_sort_row_changed (GtkTreeModel *s_model,
457 458
				 GtkTreePath  *start_s_path,
				 GtkTreeIter  *start_s_iter,
459
				 gpointer      data)
460 461
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
462
  GtkTreePath *path = NULL;
463
  GtkTreeIter iter;
464
  GtkTreeIter tmpiter;
465

466
  SortElt tmp;
467 468
  SortElt *elt;
  SortLevel *level;
469

470 471
  gboolean free_s_path = FALSE;

Kristian Rietveld's avatar
Kristian Rietveld committed
472
  gint index = 0, old_index, i;
473 474

  g_return_if_fail (start_s_path != NULL || start_s_iter != NULL);
475

476
  if (!start_s_path)
477 478
    {
      free_s_path = TRUE;
479
      start_s_path = gtk_tree_model_get_path (s_model, start_s_iter);
480
    }
481

482 483 484
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							      start_s_path,
							      FALSE);
485
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
486 487
    {
      if (free_s_path)
488
	gtk_tree_path_free (start_s_path);
Jonathan Blandford's avatar
Jonathan Blandford committed
489 490
      return;
    }
Jonathan Blandford's avatar
Jonathan Blandford committed
491

492
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
493

494 495
  level = iter.user_data;
  elt = iter.user_data2;
496

497 498
  level->ref_count++;

499 500 501
  if (level->array->len < 2 ||
      (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
       tree_model_sort->default_sort_func == NO_SORT_FUNC))
502 503
    {
      if (free_s_path)
504
	gtk_tree_path_free (start_s_path);
505

506
      gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);
507

508
      gtk_tree_path_free (path);
509

510 511
      level->ref_count--;

512 513
      return;
    }
514
  
515
  if (!GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
516 517 518 519
    {
      gtk_tree_model_get_iter (tree_model_sort->child_model,
			       &tmpiter, start_s_path);
    }
520

Kristian Rietveld's avatar
Kristian Rietveld committed
521
  old_index = elt - SORT_ELT (level->array->data);
522

523
  memcpy (&tmp, elt, sizeof (SortElt));
524

525 526 527
  if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
						   level,
528
						   &tmp.iter,
Kristian Rietveld's avatar
Kristian Rietveld committed
529
						   old_index);
530
  else
531 532
    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
						   level,
533
						   &tmpiter,
Kristian Rietveld's avatar
Kristian Rietveld committed
534
						   old_index);
535

536 537 538 539 540 541 542 543 544 545 546 547 548 549
  if (index < old_index)
    {
      g_memmove (level->array->data + ((index + 1)*sizeof (SortElt)),
		 level->array->data + ((index)*sizeof (SortElt)),
		 (old_index - index)* sizeof(SortElt));
    }
  else if (index > old_index)
    {
      g_memmove (level->array->data + ((old_index)*sizeof (SortElt)),
		 level->array->data + ((old_index + 1)*sizeof (SortElt)),
		 (index - old_index)* sizeof(SortElt));
    }
  memcpy (level->array->data + ((index)*sizeof (SortElt)),
	  &tmp, sizeof (SortElt));
550

551 552 553
  for (i = 0; i < level->array->len; i++)
    if (g_array_index (level->array, SortElt, i).children)
      g_array_index (level->array, SortElt, i).children->parent_elt = &g_array_index (level->array, SortElt, i);
554

555 556
  gtk_tree_path_up (path);
  gtk_tree_path_append_index (path, index);
557

558
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
559

560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616
  /* if the item moved, then emit rows_reordered */
  if (old_index != index)
    {
      gint *new_order;
      gint j;

      GtkTreePath *tmppath;

      new_order = g_new (gint, level->array->len);

      for (j = 0; j < level->array->len; j++)
        {
	  if (index > old_index)
	    {
	      if (j == index)
		new_order[j] = old_index;
	      else if (j >= old_index && j < index)
		new_order[j] = j + 1;
	      else
		new_order[j] = j;
	    }
	  else if (index < old_index)
	    {
	      if (j == index)
		new_order[j] = old_index;
	      else if (j > index && j <= old_index)
		new_order[j] = j - 1;
	      else
		new_order[j] = j;
	    }
	  /* else? shouldn't really happen */
	}

      if (level->parent_elt)
        {
	  iter.stamp = tree_model_sort->stamp;
	  iter.user_data = level->parent_level;
	  iter.user_data2 = level->parent_elt;

	  tmppath = gtk_tree_model_get_path (GTK_TREE_MODEL (tree_model_sort), &iter);

	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
	                                 tmppath, &iter, new_order);
	}
      else
        {
	  /* toplevel */
	  tmppath = gtk_tree_path_new ();

          gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort), tmppath,
	                                 NULL, new_order);
	}

      gtk_tree_path_free (tmppath);
      g_free (new_order);
    }

617 618
  level->ref_count--;

619 620
  /* emit row_changed signal (at new location) */
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
621 622
  gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);

623 624
  gtk_tree_path_free (path);
  if (free_s_path)
625
    gtk_tree_path_free (start_s_path);
626 627
}

628 629 630 631 632
static void
gtk_tree_model_sort_row_inserted (GtkTreeModel          *s_model,
				  GtkTreePath           *s_path,
				  GtkTreeIter           *s_iter,
				  gpointer               data)
633
{
634 635
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
  GtkTreePath *path;
636
  GtkTreeIter iter;
637 638 639 640 641 642 643 644 645 646 647
  GtkTreeIter real_s_iter;

  gint i = 0;

  gboolean free_s_path = FALSE;

  SortElt *elt;
  SortLevel *level;
  SortLevel *parent_level = NULL;

  parent_level = level = SORT_LEVEL (tree_model_sort->root);
648

649
  g_return_if_fail (s_path != NULL || s_iter != NULL);
650

651
  if (!s_path)
652
    {
653 654
      s_path = gtk_tree_model_get_path (s_model, s_iter);
      free_s_path = TRUE;
655
    }
656

657 658
  if (!s_iter)
    gtk_tree_model_get_iter (s_model, &real_s_iter, s_path);
659
  else
660
    real_s_iter = *s_iter;
661

662 663 664
  if (!tree_model_sort->root)
    {
      gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
665

666 667
      /* the build level already put the inserted iter in the level,
	 so no need to handle this signal anymore */
668

669
      goto done_and_submit;
670
    }
671

672 673 674
  /* find the parent level */
  while (i < gtk_tree_path_get_depth (s_path) - 1)
    {
675 676
      gint j;

677 678 679 680 681
      if (!level)
	{
	  /* level not yet build, we won't cover this signal */
	  goto done;
	}
682

683 684 685 686 687 688 689
      if (level->array->len < gtk_tree_path_get_indices (s_path)[i])
	{
	  g_warning ("A node was inserted with a parent that's not in the tree.\n"
		     "This possibly means that a GtkTreeModel inserted a child node\n"
		     "before the parent was inserted.");
	  goto done;
	}
690

691 692 693 694 695 696 697 698 699
      elt = NULL;
      for (j = 0; j < level->array->len; j++)
	if (g_array_index (level->array, SortElt, j).offset == gtk_tree_path_get_indices (s_path)[i])
	  {
	    elt = &g_array_index (level->array, SortElt, j);
	    break;
	  }

      g_return_if_fail (elt != NULL);
700 701 702 703 704

      if (!elt->children)
	{
	  GtkTreePath *tmppath;
	  GtkTreeIter  tmpiter;
705

706 707 708 709 710
	  tmpiter.stamp = tree_model_sort->stamp;
	  tmpiter.user_data = level;
	  tmpiter.user_data2 = elt;

	  tmppath = gtk_tree_model_get_path (GTK_TREE_MODEL (data), &tmpiter);
711 712 713 714 715 716 717
	  if (tmppath)
	    {
	      gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data),
						    tmppath,
						    &tmpiter);
	      gtk_tree_path_free (tmppath);
	    }
718

719 720 721 722 723 724 725 726
	  /* not covering this signal */
	  goto done;
	}

      level = elt->children;
      parent_level = level;
      i++;
    }
727

728
  if (!parent_level)
729
    goto done;
730

731 732 733 734 735 736
  if (level->ref_count == 0 && level != tree_model_sort->root)
    {
      gtk_tree_model_sort_free_level (tree_model_sort, level);
      goto done;
    }

737 738 739 740 741
  if (!gtk_tree_model_sort_insert_value (tree_model_sort,
					 parent_level,
					 s_path,
					 &real_s_iter))
    goto done;
742

743
 done_and_submit:
744 745 746
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							      s_path,
							      FALSE);
747

748
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
749
    return;
750

751
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
752

753
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
754
  gtk_tree_model_row_inserted (GTK_TREE_MODEL (data), path, &iter);
755
  gtk_tree_path_free (path);
756

757
 done:
758 759
  if (free_s_path)
    gtk_tree_path_free (s_path);
760

761
  return;
762 763 764
}

static void
765 766 767 768
gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel *s_model,
					   GtkTreePath  *s_path,
					   GtkTreeIter  *s_iter,
					   gpointer      data)
769 770
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
771 772
  GtkTreePath *path;
  GtkTreeIter iter;
773

774
  g_return_if_fail (s_path != NULL && s_iter != NULL);
775

776 777
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
  if (path == NULL)
Jonathan Blandford's avatar
Jonathan Blandford committed
778
    return;
779

780
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
781
  gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data), path, &iter);
782

783
  gtk_tree_path_free (path);
784 785
}

786
/* FIXME: I still have doubts if this works */
787
static void
788 789 790
gtk_tree_model_sort_row_deleted (GtkTreeModel *s_model,
				 GtkTreePath  *s_path,
				 gpointer      data)
791 792
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
793
  GtkTreePath *path = NULL;
794 795 796 797 798
  SortElt *elt;
  SortLevel *level;
  GtkTreeIter iter;
  gint offset;
  gint i;
799

800
  g_return_if_fail (s_path != NULL);
801

802 803
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
  if (path == NULL)
804 805
    return;

806
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
807

808 809 810 811
  level = SORT_LEVEL (iter.user_data);
  elt = SORT_ELT (iter.user_data2);
  offset = elt->offset;

812 813 814 815 816 817 818 819
  /* we _need_ to emit ::row_deleted before we start unreffing the node
   * itself. This is because of the row refs, which start unreffing nodes
   * when we emit ::row_deleted
   */
  gtk_tree_model_row_deleted (GTK_TREE_MODEL (data), path);

  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);

820
  while (elt->ref_count > 0)
821
    gtk_tree_model_sort_real_unref_node (GTK_TREE_MODEL (data), &iter, FALSE);
822

823
  if (level->ref_count == 0)
824
    {
825 826 827 828
      /* This will prune the level, so I can just emit the signal and 
       * not worry about cleaning this level up. 
       * Careful, root level is not cleaned up in increment stamp.
       */
829
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
830
      gtk_tree_path_free (path);
831
      if (level == tree_model_sort->root)
832 833 834 835 836
	{
	  gtk_tree_model_sort_free_level (tree_model_sort, 
					  tree_model_sort->root);
	  tree_model_sort->root = NULL;
	}
837 838
      return;
    }
839

840 841
  gtk_tree_model_sort_increment_stamp (tree_model_sort);

842 843 844 845 846 847
  /* Remove the row */
  for (i = 0; i < level->array->len; i++)
    if (elt->offset == g_array_index (level->array, SortElt, i).offset)
      break;

  g_array_remove_index (level->array, i);
848

849 850 851 852 853 854
  /* update all offsets */
  for (i = 0; i < level->array->len; i++)
    {
      elt = & (g_array_index (level->array, SortElt, i));
      if (elt->offset > offset)
	elt->offset--;
855 856
      if (elt->children)
	elt->children->parent_elt = elt;
857
    }
858 859

  gtk_tree_path_free (path);
860 861
}

862
static void
863 864 865 866 867
gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,
				    GtkTreePath  *s_path,
				    GtkTreeIter  *s_iter,
				    gint         *new_order,
				    gpointer      data)
868
{
869 870
  SortElt *elt;
  SortLevel *level;
871 872
  GtkTreeIter iter;
  gint *tmp_array;
873
  int i, j;
874
  GtkTreePath *path;
875
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
876

877
  g_return_if_fail (new_order != NULL);
878

Jonathan Blandford's avatar
Jonathan Blandford committed
879
  if (s_path == NULL || gtk_tree_path_get_indices (s_path) == NULL)
880
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
881 882
      if (tree_model_sort->root == NULL)
	return;
883
      path = gtk_tree_path_new ();
Jonathan Blandford's avatar
Jonathan Blandford committed
884
      level = SORT_LEVEL (tree_model_sort->root);
885 886
    }
  else
887
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
888 889 890 891
      path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
      if (path == NULL)
	return;
      gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
892

893 894
      level = SORT_LEVEL (iter.user_data);
      elt = SORT_ELT (iter.user_data2);
895 896

      if (!elt->children)
897 898 899 900
	{
	  gtk_tree_path_free (path);
	  return;
	}
901

902 903 904
      level = elt->children;
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
905
  if (level->array->len < 2)
906
    {
907 908 909
      gtk_tree_path_free (path);
      return;
    }
910

911 912
  tmp_array = g_new (int, level->array->len);
  for (i = 0; i < level->array->len; i++)
913 914 915 916 917 918 919 920
    {
      for (j = 0; j < level->array->len; j++)
	{
	  if (g_array_index (level->array, SortElt, i).offset == new_order[j])
	    tmp_array[i] = j;
	}
    }

921 922 923
  for (i = 0; i < level->array->len; i++)
    g_array_index (level->array, SortElt, i).offset = tmp_array[i];
  g_free (tmp_array);
924

925 926
  if (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
      tree_model_sort->default_sort_func == NO_SORT_FUNC)
927
    {
928

929 930
      gtk_tree_model_sort_sort_level (tree_model_sort, level,
				      FALSE, FALSE);
931
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
932

933
      if (gtk_tree_path_get_depth (path))
934
	{
935 936 937 938 939
	  gtk_tree_model_get_iter (GTK_TREE_MODEL (tree_model_sort),
				   &iter,
				   path);
	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
					 path, &iter, new_order);
940
	}
941
      else
942 943 944 945
	{
	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
					 path, NULL, new_order);
	}
946 947
    }

948
  gtk_tree_path_free (path);
949 950 951
}

/* Fulfill our model requirements */
952
static GtkTreeModelFlags
953 954
gtk_tree_model_sort_get_flags (GtkTreeModel *tree_model)
{
955 956
  GtkTreeModelFlags flags;

957
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
958 959 960 961 962 963
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, 0);

  flags = gtk_tree_model_get_flags (GTK_TREE_MODEL_SORT (tree_model)->child_model);

  if ((flags & GTK_TREE_MODEL_LIST_ONLY) == GTK_TREE_MODEL_LIST_ONLY)
    return GTK_TREE_MODEL_LIST_ONLY;
964 965

  return 0;
966 967
}

968 969 970
static gint
gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
{
971 972
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;

973
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
974 975 976

  if (tree_model_sort->child_model == 0)
    return 0;
977

978
  return gtk_tree_model_get_n_columns (tree_model_sort->child_model);
979 980 981 982
}

static GType
gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
983
                                     gint          index)
984 985
{
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), G_TYPE_INVALID);
986
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, G_TYPE_INVALID);
987

988
  return gtk_tree_model_get_column_type (GTK_TREE_MODEL_SORT (tree_model)->child_model, index);
989 990 991
}

static gboolean
992 993 994
gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
			      GtkTreeIter  *iter,
			      GtkTreePath  *path)
995
{
996 997 998 999
  GtkTreeModelSort *tree_model_sort;
  gint *indices;
  SortLevel *level;
  gint depth, i;
1000

1001 1002
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
1003

1004 1005 1006 1007 1008 1009 1010 1011 1012
  tree_model_sort = (GtkTreeModelSort *) tree_model;
  indices = gtk_tree_path_get_indices (path);

  if (tree_model_sort->root == NULL)
    gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
  level = SORT_LEVEL (tree_model_sort->root);

  depth = gtk_tree_path_get_depth (path);
  if (depth == 0)
1013
    return FALSE;
1014

1015
  for (i = 0; i < depth - 1; i++)
1016
    {
1017
      if ((level == NULL) ||
1018
	  (indices[i] >= level->array->len))
1019
	return FALSE;
1020

1021 1022 1023
      if (g_array_index (level->array, SortElt, indices[i]).children == NULL)
	gtk_tree_model_sort_build_level (tree_model_sort, level, &g_array_index (level->array, SortElt, indices[i]));
      level = g_array_index (level->array, SortElt, indices[i]).children;
1024 1025
    }

1026 1027 1028 1029 1030 1031
  if (!level || indices[i] >= level->array->len)
    {
      iter->stamp = 0;
      return FALSE;
    }

1032 1033 1034
  iter->stamp = tree_model_sort->stamp;
  iter->user_data = level;
  iter->user_data2 = &g_array_index (level->array, SortElt, indices[depth - 1]);
1035

1036
  return TRUE;
1037 1038 1039 1040
}

static GtkTreePath *
gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
1041
			      GtkTreeIter  *iter)
1042
{
1043 1044 1045 1046
  GtkTreePath *retval;
  SortLevel *level;
  SortElt *elt;

1047
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
1048
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, NULL);
1049
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, NULL);
1050

1051 1052 1053 1054
  retval = gtk_tree_path_new ();
  level = iter->user_data;
  elt = iter->user_data2;
  while (level != NULL)
1055
    {
1056 1057 1058 1059
      gtk_tree_path_prepend_index (retval, elt - (SortElt *)level->array->data);

      elt = level->parent_elt;
      level = level->parent_level;
1060
    }
1061 1062

  return retval;
1063 1064 1065 1066
}

static void
gtk_tree_model_sort_get_value (GtkTreeModel *tree_model,
1067 1068 1069
			       GtkTreeIter  *iter,
			       gint          column,
			       GValue       *value)
1070
{
1071
  GtkTreeIter child_iter;
1072 1073

  g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model));
1074
  g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL);
1075 1076
  g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp);

1077
  GET_CHILD_ITER (tree_model, &child_iter, iter);
1078 1079
  gtk_tree_model_get_value (GTK_TREE_MODEL_SORT (tree_model)->child_model,
			    &child_iter, column, value);
1080 1081 1082 1083
}

static gboolean
gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
1084
			       GtkTreeIter  *iter)
1085
{
1086
  SortLevel *level;
1087 1088 1089
  SortElt *elt;

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1090
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
1091 1092
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);

1093 1094
  level = iter->user_data;
  elt = iter->user_data2;
1095

1096
  if (elt - (SortElt *)level->array->data >= level->array->len - 1)
1097 1098 1099 1100
    {
      iter->stamp = 0;
      return FALSE;
    }
1101
  iter->user_data2 = elt + 1;
1102

1103 1104 1105 1106 1107
  return TRUE;
}

static gboolean
gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
1108 1109
				   GtkTreeIter  *iter,
				   GtkTreeIter  *parent)
1110
{
1111 1112
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
  SortLevel *level;
1113

1114
  iter->stamp = 0;
1115
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1116 1117
  g_return_val_if_fail (tree_model_sort->child_model != NULL, FALSE);
  if (parent) g_return_val_if_fail (tree_model_sort->stamp == parent->stamp, FALSE);
Jonathan Blandford's avatar
Jonathan Blandford committed
1118

1119 1120 1121 1122 1123 1124
  if (parent == NULL)
    {
      if (tree_model_sort->root == NULL)
	gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
      if (tree_model_sort->root == NULL)
	return FALSE;
1125

1126 1127 1128 1129 1130
      level = tree_model_sort->root;
      iter->stamp = tree_model_sort->stamp;
      iter->user_data = level;
      iter->user_data2 = level->array->data;
    }
1131
  else
1132
    {
1133 1134 1135 1136 1137
      if (((SortElt *)parent->user_data2)->children == NULL)
	gtk_tree_model_sort_build_level (tree_model_sort,
					 (SortLevel *)parent->user_data,
					 (SortElt *)parent->user_data2);
      if (((SortElt *)parent->user_data2)->children == NULL)
1138
	return FALSE;
1139 1140 1141
      iter->stamp = tree_model_sort->stamp;
      iter->user_data = ((SortElt *)parent->user_data2)->children;
      iter->user_data2 = ((SortLevel *)iter->user_data)->array->data;
1142
    }
1143

1144 1145 1146 1147 1148
  return TRUE;
}

static gboolean
gtk_tree_model_sort_iter_has_child (GtkTreeModel *tree_model,
1149
				    GtkTreeIter  *iter)
1150
{
1151
  GtkTreeIter child_iter;
1152 1153

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1154
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
1155 1156
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);

1157
  GET_CHILD_ITER (tree_model, &child_iter, iter);
1158

1159
  return gtk_tree_model_iter_has_child (GTK_TREE_MODEL_SORT (tree_model)->child_model, &child_iter);
1160 1161 1162 1163 1164 1165
}

static gint
gtk_tree_model_sort_iter_n_children (GtkTreeModel *tree_model,
				     GtkTreeIter  *iter)
{
1166
  GtkTreeIter child_iter;
1167 1168

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
1169
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, 0);
1170
  if (iter) g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, 0);
1171

1172 1173
  if (iter == NULL)
    return gtk_tree_model_iter_n_children (GTK_TREE_MODEL_SORT (tree_model)->child_model, NULL);
1174

1175
  GET_CHILD_ITER (tree_model, &child_iter, iter);
1176

1177
  return gtk_tree_model_iter_n_children (GTK_TREE_MODEL_SORT (tree_model)->child_model, &child_iter);
1178
}
1179 1180 1181

static gboolean
gtk_tree_model_sort_iter_nth_child (GtkTreeModel *tree_model,
1182 1183 1184
				    GtkTreeIter  *iter,
				    GtkTreeIter  *parent,
				    gint          n)
1185
{
1186
  SortLevel *level;
1187 1188
  /* We have this for the iter == parent case */
  GtkTreeIter children;
1189 1190

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1191
  if (parent) g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == parent->stamp, FALSE);
1192

1193 1194 1195 1196 1197 1198
  /* Use this instead of has_child to force us to build the level, if needed */
  if (gtk_tree_model_sort_iter_children (tree_model, &children, parent) == FALSE)
    {
      iter->stamp = 0;
      return FALSE;
    }
1199

1200
  level = children.user_data;
1201
  if (n >= level->array->len)
1202
    {
1203 1204
      iter->stamp = 0;
      return FALSE;
1205 1206
    }

1207 1208
  iter->stamp = GTK_TREE_MODEL_SORT (tree_model)->stamp;
  iter->user_data = level;
1209
  iter->user_data2 = &g_array_index (level->array, SortElt, n);
1210

1211 1212 1213 1214 1215
  return TRUE;
}

static gboolean
gtk_tree_model_sort_iter_parent (GtkTreeModel *tree_model,
1216 1217
				 GtkTreeIter  *iter,
				 GtkTreeIter  *child)
1218
{
1219
  SortLevel *level;
1220

1221
  iter->stamp = 0;
1222
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1223
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
1224 1225
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == child->stamp, FALSE);

1226
  level = child->user_data;
1227

1228
  if (level->parent_level)
1229 1230
    {
      iter->stamp = GTK_TREE_MODEL_SORT (tree_model)->stamp;
1231 1232 1233
      iter->user_data = level->parent_level;
      iter->user_data2 = level->parent_elt;

1234 1235 1236 1237 1238 1239
      return TRUE;
    }
  return FALSE;
}

static void
1240
gtk_tree_model_sort_ref_node (GtkTreeModel *tree_model,
1241
			      GtkTreeIter  *iter)
1242
{
1243
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
1244
  GtkTreeIter child_iter;
1245
  SortLevel *level;
1246 1247 1248 1249 1250 1251
  SortElt *elt;

  g_return_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model));
  g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL);
  g_return_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp);