gtktreemodelsort.c 74.2 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 "gtktreednd.h"
49 50

typedef struct _SortElt SortElt;
51 52 53 54
typedef struct _SortLevel SortLevel;
typedef struct _SortData SortData;
typedef struct _SortTuple SortTuple;

55 56
struct _SortElt
{
57 58 59 60 61 62 63 64 65 66 67 68 69
  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;
70 71
};

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

82 83 84
struct _SortTuple
{
  SortElt   *elt;
85
  gint       offset;
86
};
87

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



97 98 99 100 101 102
#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)

#define GET_CHILD_ITER(tree_model_sort,child_iter,sort_iter) gtk_tree_model_sort_convert_iter_to_child_iter(GTK_TREE_MODEL_SORT (tree_model_sort), child_iter, sort_iter);
103

104 105
#define NO_SORT_FUNC ((GtkTreeIterCompareFunc) 0x1)

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

108
/* general (object/interface init, etc) */
109 110 111 112
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);
113
static void gtk_tree_model_sort_drag_source_init      (GtkTreeDragSourceIface*iface);
114
static void gtk_tree_model_sort_finalize              (GObject               *object);
115 116 117 118 119 120 121 122
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);
123

124
/* our signal handlers */
125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144
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);
145 146

/* TreeModel interface */
147
static GtkTreeModelFlags gtk_tree_model_sort_get_flags     (GtkTreeModel          *tree_model);
148 149 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
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);
178 179 180
static void         gtk_tree_model_sort_real_unref_node    (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter,
							    gboolean               propagate_unref);
181 182 183
static void         gtk_tree_model_sort_unref_node         (GtkTreeModel          *tree_model,
                                                            GtkTreeIter           *iter);

184 185 186 187 188 189 190 191 192
/* 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);

193
/* TreeSortable interface */
194 195 196 197 198 199 200 201 202 203 204
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);
205 206 207 208 209
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);
210

211
/* Private functions (sort funcs, level handling and other utils) */
212 213 214 215 216 217 218 219 220 221 222
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);
223 224 225
static gint         gtk_tree_model_sort_level_find_insert (GtkTreeModelSort *tree_model_sort,
							   SortLevel        *level,
							   GtkTreeIter      *iter,
Kristian Rietveld's avatar
Kristian Rietveld committed
226
							   gint             skip_index);
227
static gboolean     gtk_tree_model_sort_insert_value      (GtkTreeModelSort *tree_model_sort,
228
							   SortLevel        *level,
229 230
							   GtkTreePath      *s_path,
							   GtkTreeIter      *s_iter);
231 232 233 234
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);
235 236 237
static GtkTreePath *gtk_real_tree_model_sort_convert_child_path_to_path (GtkTreeModelSort *tree_model_sort,
									 GtkTreePath      *child_path,
									 gboolean          build_levels);
238

239
static GObjectClass *parent_class = NULL;
240

241
GType
242 243
gtk_tree_model_sort_get_type (void)
{
244
  static GType tree_model_sort_type = 0;
245

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

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

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

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

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

286
      g_type_add_interface_static (tree_model_sort_type,
287 288
                                   GTK_TYPE_TREE_MODEL,
                                   &tree_model_info);
289

290
      g_type_add_interface_static (tree_model_sort_type,
291 292
                                   GTK_TYPE_TREE_SORTABLE,
                                   &sortable_info);
293 294 295 296

      g_type_add_interface_static (tree_model_sort_type,
                                   GTK_TYPE_TREE_DRAG_SOURCE,
                                   &drag_source_info);
297 298 299 300 301 302
    }

  return tree_model_sort_type;
}

static void
303 304 305 306 307 308 309 310 311 312 313
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)
314 315 316
{
  GObjectClass *object_class;

317
  object_class = (GObjectClass *) class;
318
  parent_class = g_type_class_peek_parent (class);
319

320 321 322
  object_class->set_property = gtk_tree_model_sort_set_property;
  object_class->get_property = gtk_tree_model_sort_get_property;

323
  object_class->finalize = gtk_tree_model_sort_finalize;
324 325 326 327 328

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

static void
gtk_tree_model_sort_tree_model_init (GtkTreeModelIface *iface)
{
338
  iface->get_flags = gtk_tree_model_sort_get_flags;
339 340 341 342 343 344 345 346 347 348 349
  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;
350 351
  iface->ref_node = gtk_tree_model_sort_ref_node;
  iface->unref_node = gtk_tree_model_sort_unref_node;
352 353
}

354 355 356 357 358
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;
359
  iface->set_sort_func = gtk_tree_model_sort_set_sort_func;
360 361
  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;
362 363
}

364 365 366 367 368 369 370 371
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;
}

372 373 374 375 376 377 378 379
/**
 * gtk_tree_model_sort_new_with_model:
 * @child_model: A #GtkTreeModel
 *
 * Creates a new #GtkTreeModel, with @child_model as the child_model.
 *
 * Return value: A new #GtkTreeModel.
 */
380
GtkTreeModel *
381
gtk_tree_model_sort_new_with_model (GtkTreeModel      *child_model)
382 383 384
{
  GtkTreeModel *retval;

385 386
  g_return_val_if_fail (GTK_IS_TREE_MODEL (child_model), NULL);

Manish Singh's avatar
Manish Singh committed
387
  retval = g_object_new (gtk_tree_model_sort_get_type (), NULL);
388

389
  gtk_tree_model_sort_set_model (GTK_TREE_MODEL_SORT (retval), child_model);
390 391 392 393

  return retval;
}

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

400 401
  gtk_tree_model_sort_set_model (tree_model_sort, NULL);

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

  if (tree_model_sort->sort_list)
    {
      _gtk_tree_data_list_header_free (tree_model_sort->sort_list);
      tree_model_sort->sort_list = NULL;
    }
410 411 412

  /* must chain up */
  parent_class->finalize (object);
413 414
}

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
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;
    }
}

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

464
  SortElt tmp;
465 466
  SortElt *elt;
  SortLevel *level;
467

468 469
  gboolean free_s_path = FALSE;

Kristian Rietveld's avatar
Kristian Rietveld committed
470
  gint index = 0, old_index, i;
471 472

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

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

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

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

492 493
  level = iter.user_data;
  elt = iter.user_data2;
494

495 496 497
  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))
498 499
    {
      if (free_s_path)
500
	gtk_tree_path_free (start_s_path);
501

502
      gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);
503

504
      gtk_tree_path_free (path);
505

506 507 508
      return;
    }

509
  if (!GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
510 511 512 513
    {
      gtk_tree_model_get_iter (tree_model_sort->child_model,
			       &tmpiter, start_s_path);
    }
514

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

517
  memcpy (&tmp, elt, sizeof (SortElt));
518

519 520 521
  if (GTK_TREE_MODEL_SORT_CACHE_CHILD_ITERS (tree_model_sort))
    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
						   level,
522
						   &tmp.iter,
Kristian Rietveld's avatar
Kristian Rietveld committed
523
						   old_index);
524
  else
525 526
    index = gtk_tree_model_sort_level_find_insert (tree_model_sort,
						   level,
527
						   &tmpiter,
Kristian Rietveld's avatar
Kristian Rietveld committed
528
						   old_index);
529

530 531 532 533 534 535 536 537 538 539 540 541 542 543
  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));
544

545 546 547
  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);
548

549 550
  gtk_tree_path_up (path);
  gtk_tree_path_append_index (path, index);
551

552
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
553

554 555 556 557 558 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
  /* 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);
    }

  /* emit row_changed signal (at new location) */
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
613 614
  gtk_tree_model_row_changed (GTK_TREE_MODEL (data), path, &iter);

615 616
  gtk_tree_path_free (path);
  if (free_s_path)
617
    gtk_tree_path_free (start_s_path);
618 619
}

620 621 622 623 624
static void
gtk_tree_model_sort_row_inserted (GtkTreeModel          *s_model,
				  GtkTreePath           *s_path,
				  GtkTreeIter           *s_iter,
				  gpointer               data)
625
{
626 627
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
  GtkTreePath *path;
628
  GtkTreeIter iter;
629 630 631 632 633 634 635 636 637 638 639
  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);
640

641
  g_return_if_fail (s_path != NULL || s_iter != NULL);
642

643
  if (!s_path)
644
    {
645 646
      s_path = gtk_tree_model_get_path (s_model, s_iter);
      free_s_path = TRUE;
647
    }
648

649 650
  if (!s_iter)
    gtk_tree_model_get_iter (s_model, &real_s_iter, s_path);
651
  else
652
    real_s_iter = *s_iter;
653

654 655 656
  if (!tree_model_sort->root)
    {
      gtk_tree_model_sort_build_level (tree_model_sort, NULL, NULL);
657

658 659
      /* the build level already put the inserted iter in the level,
	 so no need to handle this signal anymore */
660

661
      goto done_and_submit;
662
    }
663

664 665 666
  /* find the parent level */
  while (i < gtk_tree_path_get_depth (s_path) - 1)
    {
667 668
      gint j;

669 670 671 672 673
      if (!level)
	{
	  /* level not yet build, we won't cover this signal */
	  goto done;
	}
674

675 676 677 678 679 680 681
      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;
	}
682

683 684 685 686 687 688 689 690 691
      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);
692 693 694 695 696

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

698 699 700 701 702
	  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);
703 704 705 706 707 708 709
	  if (tmppath)
	    {
	      gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data),
						    tmppath,
						    &tmpiter);
	      gtk_tree_path_free (tmppath);
	    }
710

711 712 713 714 715 716 717 718
	  /* not covering this signal */
	  goto done;
	}

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

720
  if (!parent_level)
721
    goto done;
722

723 724 725 726 727
  if (!gtk_tree_model_sort_insert_value (tree_model_sort,
					 parent_level,
					 s_path,
					 &real_s_iter))
    goto done;
728

729
 done_and_submit:
730 731 732
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort,
							      s_path,
							      FALSE);
733

734
  if (!path)
Jonathan Blandford's avatar
Jonathan Blandford committed
735
    return;
736

737
  gtk_tree_model_sort_increment_stamp (tree_model_sort);
738

739
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
740
  gtk_tree_model_row_inserted (GTK_TREE_MODEL (data), path, &iter);
741
  gtk_tree_path_free (path);
742

743
 done:
744 745
  if (free_s_path)
    gtk_tree_path_free (s_path);
746

747
  return;
748 749 750
}

static void
751 752 753 754
gtk_tree_model_sort_row_has_child_toggled (GtkTreeModel *s_model,
					   GtkTreePath  *s_path,
					   GtkTreeIter  *s_iter,
					   gpointer      data)
755 756
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
757 758
  GtkTreePath *path;
  GtkTreeIter iter;
759

760
  g_return_if_fail (s_path != NULL && s_iter != NULL);
761

762 763
  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
764
    return;
765

766
  gtk_tree_model_get_iter (GTK_TREE_MODEL (data), &iter, path);
767
  gtk_tree_model_row_has_child_toggled (GTK_TREE_MODEL (data), path, &iter);
768

769
  gtk_tree_path_free (path);
770 771
}

772
/* FIXME: I still have doubts if this works */
773
static void
774 775 776
gtk_tree_model_sort_row_deleted (GtkTreeModel *s_model,
				 GtkTreePath  *s_path,
				 gpointer      data)
777 778
{
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
779
  GtkTreePath *path = NULL;
780 781 782 783 784
  SortElt *elt;
  SortLevel *level;
  GtkTreeIter iter;
  gint offset;
  gint i;
785

786
  g_return_if_fail (s_path != NULL);
787

788 789
  path = gtk_real_tree_model_sort_convert_child_path_to_path (tree_model_sort, s_path, FALSE);
  if (path == NULL)
790 791
    return;

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

794 795 796 797
  level = SORT_LEVEL (iter.user_data);
  elt = SORT_ELT (iter.user_data2);
  offset = elt->offset;

798 799 800 801 802 803 804 805
  /* 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);

806
  while (elt->ref_count > 0)
807
    gtk_tree_model_sort_real_unref_node (GTK_TREE_MODEL (data), &iter, FALSE);
808

809
  if (level->ref_count == 0)
810
    {
811 812
      /* This will prune the level, so I can just emit the signal and not worry
       * about cleaning this level up. */
813
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
814
      gtk_tree_path_free (path);
815 816
      if (level == tree_model_sort->root)
	tree_model_sort->root = NULL;
817 818
      return;
    }
819

820 821
  gtk_tree_model_sort_increment_stamp (tree_model_sort);

822 823 824 825 826 827
  /* 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);
828

829 830 831 832 833 834
  /* 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--;
835 836
      if (elt->children)
	elt->children->parent_elt = elt;
837
    }
838 839

  gtk_tree_path_free (path);
840 841
}

842
static void
843 844 845 846 847
gtk_tree_model_sort_rows_reordered (GtkTreeModel *s_model,
				    GtkTreePath  *s_path,
				    GtkTreeIter  *s_iter,
				    gint         *new_order,
				    gpointer      data)
848
{
849 850
  SortElt *elt;
  SortLevel *level;
Jonathan Blandford's avatar
Jonathan Blandford committed
851 852
  GtkTreeIter iter;
  gint *tmp_array;
853
  int i, j;
854
  GtkTreePath *path;
855
  GtkTreeModelSort *tree_model_sort = GTK_TREE_MODEL_SORT (data);
856

857
  g_return_if_fail (new_order != NULL);
858

Jonathan Blandford's avatar
Jonathan Blandford committed
859
  if (s_path == NULL || gtk_tree_path_get_indices (s_path) == NULL)
860
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
861 862
      if (tree_model_sort->root == NULL)
	return;
Jonathan Blandford's avatar
Jonathan Blandford committed
863
      path = gtk_tree_path_new ();
Jonathan Blandford's avatar
Jonathan Blandford committed
864
      level = SORT_LEVEL (tree_model_sort->root);
865 866
    }
  else
867
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
868 869 870 871
      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);
872

873 874
      level = SORT_LEVEL (iter.user_data);
      elt = SORT_ELT (iter.user_data2);
875 876

      if (!elt->children)
Jonathan Blandford's avatar
Jonathan Blandford committed
877 878 879 880
	{
	  gtk_tree_path_free (path);
	  return;
	}
881

882 883 884
      level = elt->children;
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
885
  if (level->array->len < 2)
886
    {
Jonathan Blandford's avatar
Jonathan Blandford committed
887 888 889
      gtk_tree_path_free (path);
      return;
    }
890

Jonathan Blandford's avatar
Jonathan Blandford committed
891 892
  tmp_array = g_new (int, level->array->len);
  for (i = 0; i < level->array->len; i++)
893 894 895 896 897 898 899 900
    {
      for (j = 0; j < level->array->len; j++)
	{
	  if (g_array_index (level->array, SortElt, i).offset == new_order[j])
	    tmp_array[i] = j;
	}
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
901 902 903
  for (i = 0; i < level->array->len; i++)
    g_array_index (level->array, SortElt, i).offset = tmp_array[i];
  g_free (tmp_array);
904

905 906
  if (tree_model_sort->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID &&
      tree_model_sort->default_sort_func == NO_SORT_FUNC)
Jonathan Blandford's avatar
Jonathan Blandford committed
907
    {
908

909 910
      gtk_tree_model_sort_sort_level (tree_model_sort, level,
				      FALSE, FALSE);
Owen Taylor's avatar
Owen Taylor committed
911
      gtk_tree_model_sort_increment_stamp (tree_model_sort);
912

913
      if (gtk_tree_path_get_depth (path))
914
	{
915 916 917 918 919
	  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);
920
	}
921
      else
922 923 924 925
	{
	  gtk_tree_model_rows_reordered (GTK_TREE_MODEL (tree_model_sort),
					 path, NULL, new_order);
	}
926 927
    }

Jonathan Blandford's avatar
Jonathan Blandford committed
928
  gtk_tree_path_free (path);
929 930 931
}

/* Fulfill our model requirements */
932
static GtkTreeModelFlags
933 934
gtk_tree_model_sort_get_flags (GtkTreeModel *tree_model)
{
935 936
  GtkTreeModelFlags flags;

937
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
938 939 940 941 942 943
  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;
944 945

  return 0;
946 947
}

948 949 950
static gint
gtk_tree_model_sort_get_n_columns (GtkTreeModel *tree_model)
{
951 952
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;

953
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), 0);
954 955 956

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

958
  return gtk_tree_model_get_n_columns (tree_model_sort->child_model);
959 960 961 962
}

static GType
gtk_tree_model_sort_get_column_type (GtkTreeModel *tree_model,
963
                                     gint          index)
964 965
{
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), G_TYPE_INVALID);
966
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, G_TYPE_INVALID);
967

968
  return gtk_tree_model_get_column_type (GTK_TREE_MODEL_SORT (tree_model)->child_model, index);
969 970 971
}

static gboolean
972 973 974
gtk_tree_model_sort_get_iter (GtkTreeModel *tree_model,
			      GtkTreeIter  *iter,
			      GtkTreePath  *path)
975
{
976 977 978 979
  GtkTreeModelSort *tree_model_sort;
  gint *indices;
  SortLevel *level;
  gint depth, i;
980

981 982
  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);
983

984 985 986 987 988 989 990 991 992
  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)
993
    return FALSE;
994

995
  for (i = 0; i < depth - 1; i++)
996
    {
997
      if ((level == NULL) ||
998
	  (indices[i] >= level->array->len))
999
	return FALSE;
1000

1001 1002 1003
      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;
1004 1005
    }

1006 1007 1008 1009 1010 1011
  if (!level || indices[i] >= level->array->len)
    {
      iter->stamp = 0;
      return FALSE;
    }

1012 1013 1014
  iter->stamp = tree_model_sort->stamp;
  iter->user_data = level;
  iter->user_data2 = &g_array_index (level->array, SortElt, indices[depth - 1]);
1015

1016
  return TRUE;
1017 1018 1019 1020
}

static GtkTreePath *
gtk_tree_model_sort_get_path (GtkTreeModel *tree_model,
1021
			      GtkTreeIter  *iter)
1022
{
1023 1024 1025 1026
  GtkTreePath *retval;
  SortLevel *level;
  SortElt *elt;

1027
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), NULL);
1028
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, NULL);
1029
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, NULL);
1030

1031 1032 1033 1034
  retval = gtk_tree_path_new ();
  level = iter->user_data;
  elt = iter->user_data2;
  while (level != NULL)
1035
    {
1036 1037 1038 1039
      gtk_tree_path_prepend_index (retval, elt - (SortElt *)level->array->data);

      elt = level->parent_elt;
      level = level->parent_level;
1040
    }
1041 1042

  return retval;
1043 1044 1045 1046
}

static void
gtk_tree_model_sort_get_value (GtkTreeModel *tree_model,
1047 1048 1049
			       GtkTreeIter  *iter,
			       gint          column,
			       GValue       *value)
1050
{
1051
  GtkTreeIter child_iter;
1052 1053

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

1057
  GET_CHILD_ITER (tree_model, &child_iter, iter);
1058 1059
  gtk_tree_model_get_value (GTK_TREE_MODEL_SORT (tree_model)->child_model,
			    &child_iter, column, value);
1060 1061 1062 1063
}

static gboolean
gtk_tree_model_sort_iter_next (GtkTreeModel *tree_model,
1064
			       GtkTreeIter  *iter)
1065
{
1066
  SortLevel *level;
1067 1068 1069
  SortElt *elt;

  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1070
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->child_model != NULL, FALSE);
1071 1072
  g_return_val_if_fail (GTK_TREE_MODEL_SORT (tree_model)->stamp == iter->stamp, FALSE);

1073 1074
  level = iter->user_data;
  elt = iter->user_data2;
1075

1076
  if (elt - (SortElt *)level->array->data >= level->array->len - 1)
1077 1078 1079 1080
    {
      iter->stamp = 0;
      return FALSE;
    }
1081
  iter->user_data2 = elt + 1;
1082

1083 1084 1085 1086 1087
  return TRUE;
}

static gboolean
gtk_tree_model_sort_iter_children (GtkTreeModel *tree_model,
1088 1089
				   GtkTreeIter  *iter,
				   GtkTreeIter  *parent)
1090
{
1091 1092
  GtkTreeModelSort *tree_model_sort = (GtkTreeModelSort *) tree_model;
  SortLevel *level;
1093

1094
  iter->stamp = 0;
1095
  g_return_val_if_fail (GTK_IS_TREE_MODEL_SORT (tree_model), FALSE);
1096 1097
  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
1098

1099 1100 1101 1102 1103 1104
  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;
1105

1106 1107 1108 1109 1110
      level = tree_model_sort->root;
      iter->stamp = tree_model_sort->stamp;
      iter->user_data = level;
      iter->user_data2 = level->array->data;
    }
1111
  else
1112
    {
1113 1114 1115 1116 1117
      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)
Kristian Rietveld's avatar