/* GTK - The GIMP Toolkit

 * gtkfilesystemmodel.c: GtkTreeModel wrapping a GtkFileSystem

 * Copyright (C) 2003, Red Hat, Inc.

 *

 * This library is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Lesser 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

 * Lesser General Public License for more details.

 *

 * You should have received a copy of the GNU Lesser 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.

 */

#include "config.h"

#include "gtkfilesystemmodel.h"

#include <stdlib.h>

#include <string.h>

#include "gtkfilesystem.h"

#include "gtkintl.h"

#include "gtkmarshalers.h"

#include "gtktreedatalist.h"

#include "gtktreednd.h"

#include "gtktreemodel.h"

#include "gtkalias.h"

/*** Structure: how GtkFileSystemModel works

 *

 * This is a custom GtkTreeModel used to hold a collection of files for GtkFileChooser.  There are two use cases:

 *

 *   1. The model populates itself from a folder, using the GIO file enumerator API.  This happens if you use

 *      _gtk_file_system_model_new_for_directory().  This is the normal usage for showing the contents of a folder.

 *

 *   2. The caller populates the model by hand, with files not necessarily in the same folder.  This happens

 *      if you use _gtk_file_system_model_new() and then _gtk_file_system_model_add_and_query_file().  This is

 *      the special kind of usage for "search" and "recent-files", where the file chooser gives the model the

 *      files to be displayed.

 *

 * Internal data structure

 * -----------------------

 *

 * Each file is kept in a FileModelNode structure.  Each FileModelNode holds a GFile* and other data.  All the

 * node structures have the same size, determined at runtime, depending on the number of columns that were passed

 * to _gtk_file_system_model_new() or _gtk_file_system_model_new_for_directory() (that is, the size of a node is

 * not sizeof (FileModelNode), but rather model->node_size).  The last field in the FileModelNode structure,

 * node->values[], is an array of GValue, used to hold the data for those columns.

 *

 * The model stores an array of FileModelNode structures in model->files.  This is a GArray where each element is

 * model->node_size bytes in size (the model computes that node size when initializing itself).  There are

 * convenience macros, get_node() and node_index(), to access that array based on an array index or a pointer to

 * a node inside the array.

 *

 * The model accesses files through two of its fields:

 *

 *   model->files - GArray of FileModelNode structures.

 *

 *   model->file_lookup - hash table that maps a GFile* to an index inside the model->files array.

 *

 * The model->file_lookup hash table is populated lazily.  It is both accessed and populated with the

 * node_get_for_file() function.  The invariant is that the files in model->files[n] for n < g_hash_table_size

 * (model->file_lookup) are already added to the hash table. The hash table will get cleared when we re-sort the

 * files, as the array will be in a different order and the indexes need to be rebuilt.

 *

 * Each FileModelNode has a node->visible field, which indicates whether the node is visible in the GtkTreeView.

 * A node may be invisible if, for example, it corresponds to a hidden file and the file chooser is not showing

 * hidden files.  Also, a file filter may be explicitly set onto the model, for example, to only show files that

 * match "*.jpg".  In this case, node->filtered_out says whether the node failed the filter.  The ultimate

 * decision on whether a node is visible or not in the treeview is distilled into the node->visible field.

 * The reason for having a separate node->filtered_out field is so that the file chooser can query whether

 * a (filtered-out) folder should be made sensitive in the GUI.

 *

 * Visible rows vs. possibly-invisible nodes

 * -----------------------------------------

 *

 * Since not all nodes in the model->files array may be visible, we need a way to map visible row indexes from

 * the treeview to array indexes in our array of files.  And thus we introduce a bit of terminology:

 *

 *   index - An index in the model->files array.  All variables/fields that represent indexes are either called

 *   "index" or "i_*", or simply "i" for things like loop counters.

 *

 *   row - An index in the GtkTreeView, i.e. the index of a row within the outward-facing API of the

 *   GtkFileSystemModel.  However, note that our rows are 1-based, not 0-based, for the reason explained in the

 *   following paragraph.  Variables/fields that represent visible rows are called "row", or "r_*", or simply

 *   "r".

 *

 * Each FileModelNode has a node->row field which is the number of visible rows in the treeview, *before and

 * including* that node.  This means that node->row is 1-based, instead of 0-based --- this makes some code

 * simpler, believe it or not :)  This also means that when the calling GtkTreeView gives us a GtkTreePath, we

 * turn the 0-based treepath into a 1-based row for our purposes.  If a node is not visible, it will have the

 * same row number as its closest preceding visible node.

 *

 * We try to compute the node->row fields lazily.  A node is said to be "valid" if its node->row is accurate.

 * For this, the model keeps a model->n_nodes_valid field which is the count of valid nodes starting from the

 * beginning of the model->files array.  When a node changes its information, or when a node gets deleted, that

 * node and the following ones get invalidated by simply setting model->n_nodes_valid to the array index of the

 * node.  If the model happens to need a node's row number and that node is in the model->files array after

 * model->n_nodes_valid, then the nodes get re-validated up to the sought node.  See node_validate_rows() for

 * this logic.

 *

 * You never access a node->row directly.  Instead, call node_get_tree_row().  That function will validate the nodes

 * up to the sought one if the node is not valid yet, and it will return a proper 0-based row.

 *

 * Sorting

 * -------

 *

 * The model implements the GtkTreeSortable interface.  To avoid re-sorting

 * every time a node gets added (which would lead to O(n^2) performance during

 * the initial population of the model), the model can freeze itself (with

 * freeze_updates()) during the intial population process.  When the model is

 * frozen, sorting will not happen.  The model will sort itself when the freeze

 * count goes back to zero, via corresponding calls to thaw_updates().

 */

/*** DEFINES ***/

/* priority used for all async callbacks in the main loop

 * This should be higher than redraw priorities so multiple callbacks

 * firing can be handled without intermediate redraws */

#define IO_PRIORITY G_PRIORITY_DEFAULT

/* random number that everyone else seems to use, too */

#define FILES_PER_QUERY 100

typedef struct _FileModelNode           FileModelNode;

typedef struct _GtkFileSystemModelClass GtkFileSystemModelClass;

struct _FileModelNode

{

  GFile *               file;           /* file represented by this node or NULL for editable */

  GFileInfo *           info;           /* info for this file or NULL if unknown */

  guint                 row;            /* if valid (see model->n_valid_indexes), visible nodes before and including

					 * this one - see the "Structure" comment above.

					 */

  guint                 visible :1;     /* if the file is currently visible */

  guint                 filtered_out :1;/* if the file is currently filtered out (i.e. it didn't pass the filters) */

  guint                 frozen_add :1;  /* true if the model was frozen and the entry has not been added yet */

  GValue                values[1];      /* actually n_columns values */

};

struct _GtkFileSystemModel

{

  GObject               parent_instance;

  GFile *               dir;            /* directory that's displayed */

  guint                 dir_thaw_source;/* GSource id for unfreezing the model */

  char *                attributes;     /* attributes the file info must contain, or NULL for all attributes */

  GFileMonitor *        dir_monitor;    /* directory that is monitored, or NULL if monitoring was not supported */

  GCancellable *        cancellable;    /* cancellable in use for all operations - cancelled on dispose */

  GArray *              files;          /* array of FileModelNode containing all our files */

  gsize                 node_size;	/* Size of a FileModelNode structure once its ->values field has n_columns */

  guint                 n_nodes_valid;  /* count of valid nodes (i.e. those whose node->row is accurate) */

  GHashTable *          file_lookup;    /* mapping of GFile => array index in model->files

					 * This hash table doesn't always have the same number of entries as the files array;

					 * it can get cleared completely when we resort.

					 * The hash table gets re-populated in node_get_for_file() if this mismatch is

					 * detected.

					 */

  guint                 n_columns;      /* number of columns */

  GType *               column_types;   /* types of each column */

  GtkFileSystemModelGetValue get_func;  /* function to call to fill in values in columns */

  gpointer              get_data;       /* data to pass to get_func */

  GtkFileFilter *       filter;         /* filter to use for deciding which nodes are visible */

  int                   sort_column_id; /* current sorting column */

  GtkSortType           sort_order;     /* current sorting order */

  GList *               sort_list;      /* list of sorting functions */

  GtkTreeIterCompareFunc default_sort_func; /* default sort function */

  gpointer              default_sort_data; /* data to pass to default sort func */

  GDestroyNotify        default_sort_destroy; /* function to call to destroy default_sort_data */

  guint                 frozen;         /* number of times we're frozen */

  gboolean              filter_on_thaw :1;/* set when filtering needs to happen upon thawing */

  gboolean              sort_on_thaw :1;/* set when sorting needs to happen upon thawing */

  guint                 show_hidden :1; /* whether to show hidden files */

  guint                 show_folders :1;/* whether to show folders */

  guint                 show_files :1;  /* whether to show files */

  guint                 filter_folders :1;/* whether filter applies to folders */

};

#define GTK_FILE_SYSTEM_MODEL_CLASS(klass)     (G_TYPE_CHECK_CLASS_CAST ((klass), GTK_TYPE_FILE_SYSTEM_MODEL, GtkFileSystemModelClass))

#define GTK_IS_FILE_SYSTEM_MODEL_CLASS(klass)  (G_TYPE_CHECK_CLASS_TYPE ((klass), GTK_TYPE_FILE_SYSTEM_MODEL))

#define GTK_FILE_SYSTEM_MODEL_GET_CLASS(obj)   (G_TYPE_INSTANCE_GET_CLASS ((obj), GTK_TYPE_FILE_SYSTEM_MODEL, GtkFileSystemModelClass))

struct _GtkFileSystemModelClass

{

  GObjectClass parent_class;

  /* Signals */

  void (*finished_loading) (GtkFileSystemModel *model, GError *error);

};

static void freeze_updates (GtkFileSystemModel *model);

static void thaw_updates (GtkFileSystemModel *model);

static guint node_get_for_file (GtkFileSystemModel *model,

				GFile              *file);

static void add_file (GtkFileSystemModel *model,

		      GFile              *file,

		      GFileInfo          *info);

static void remove_file (GtkFileSystemModel *model,

			 GFile              *file);

/* iter setup:

 * @user_data: the model

 * @user_data2: GUINT_TO_POINTER of array index of current entry

 *

 * All other fields are unused. Note that the array index does not corrspond

 * 1:1 with the path index as entries might not be visible.

 */

#define ITER_INDEX(iter) GPOINTER_TO_UINT((iter)->user_data2)

#define ITER_IS_VALID(model, iter) ((model) == (iter)->user_data)

#define ITER_INIT_FROM_INDEX(model, _iter, _index) G_STMT_START {\

  g_assert (_index < (model)->files->len); \

  (_iter)->user_data = (model); \

  (_iter)->user_data2 = GUINT_TO_POINTER (_index); \

}G_STMT_END

/*** FileModelNode ***/

/* Get a FileModelNode structure given an index in the model->files array of nodes */

#define get_node(_model, _index) ((FileModelNode *) ((_model)->files->data + (_index) * (_model)->node_size))

/* Get an index within the model->files array of nodes, given a FileModelNode* */

#define node_index(_model, _node) (((gchar *) (_node) - (_model)->files->data) / (_model)->node_size)

/* @up_to_index: smallest model->files array index that will be valid after this call

 * @up_to_row: smallest node->row that will be valid after this call

 *

 * If you want to validate up to an index or up to a row, specify the index or

 * the row you want and specify G_MAXUINT for the other argument.  Pass

 * G_MAXUINT for both arguments for "validate everything".

 */

static void

node_validate_rows (GtkFileSystemModel *model, guint up_to_index, guint up_to_row)

{

  guint i, row;

  if (model->files->len == 0)

    return;

  up_to_index = MIN (up_to_index, model->files->len - 1);

  i = model->n_nodes_valid;

  if (i != 0)

    row = get_node (model, i - 1)->row;

  else

    row = 0;

  while (i <= up_to_index && row <= up_to_row)

    {

      FileModelNode *node = get_node (model, i);

      if (node->visible)

        row++;

      node->row = row;

      i++;

    }

  model->n_nodes_valid = i;

}

static guint

node_get_tree_row (GtkFileSystemModel *model, guint index)

{

  if (model->n_nodes_valid <= index)

    node_validate_rows (model, index, G_MAXUINT);

  return get_node (model, index)->row - 1;

}

static void 

node_invalidate_index (GtkFileSystemModel *model, guint id)

{

  model->n_nodes_valid = MIN (model->n_nodes_valid, id);

}

static GtkTreePath *

tree_path_new_from_node (GtkFileSystemModel *model, guint id)

{

  guint r = node_get_tree_row (model, id);

  g_assert (r < model->files->len);

  return gtk_tree_path_new_from_indices (r, -1);

}

static void

emit_row_inserted_for_node (GtkFileSystemModel *model, guint id)

{

  GtkTreePath *path;

  GtkTreeIter iter;

  path = tree_path_new_from_node (model, id);

  ITER_INIT_FROM_INDEX (model, &iter, id);

  gtk_tree_model_row_inserted (GTK_TREE_MODEL (model), path, &iter);

  gtk_tree_path_free (path);

}

static void

emit_row_changed_for_node (GtkFileSystemModel *model, guint id)

{

  GtkTreePath *path;

  GtkTreeIter iter;

  path = tree_path_new_from_node (model, id);

  ITER_INIT_FROM_INDEX (model, &iter, id);

  gtk_tree_model_row_changed (GTK_TREE_MODEL (model), path, &iter);

  gtk_tree_path_free (path);

}

static void

emit_row_deleted_for_row (GtkFileSystemModel *model, guint row)

{

  GtkTreePath *path;

  path = gtk_tree_path_new_from_indices (row, -1);

  gtk_tree_model_row_deleted (GTK_TREE_MODEL (model), path);

  gtk_tree_path_free (path);

}

static void

node_set_visible_and_filtered_out (GtkFileSystemModel *model, guint id, gboolean visible, gboolean filtered_out)

{

  FileModelNode *node = get_node (model, id);

  /* Filteredness */

  if (node->filtered_out != filtered_out)

    {

      node->filtered_out = filtered_out;

      if (node->visible && visible)

        emit_row_changed_for_node (model, id);

    }

  /* Visibility */

  if (node->visible == visible ||

      node->frozen_add)

    return;

  if (visible)

    {

      node->visible = TRUE;

      node_invalidate_index (model, id);

      emit_row_inserted_for_node (model, id);

    }

  else

    {

      guint row;

      row = node_get_tree_row (model, id);

      g_assert (row < model->files->len);

      node->visible = FALSE;

      node_invalidate_index (model, id);

      emit_row_deleted_for_row (model, row);

    }

}

static gboolean

node_should_be_filtered_out (GtkFileSystemModel *model, guint id)

{

  FileModelNode *node = get_node (model, id);

  GtkFileFilterInfo filter_info = { 0, };

  GtkFileFilterFlags required;

  gboolean result;

  char *mime_type = NULL;

  char *filename = NULL;

  char *uri = NULL;

  if (node->info == NULL)

    return TRUE;

  if (model->filter == NULL)

    return FALSE;

  /* fill info */

  required = gtk_file_filter_get_needed (model->filter);

  filter_info.contains = GTK_FILE_FILTER_DISPLAY_NAME;

  filter_info.display_name = g_file_info_get_display_name (node->info);

  if (required & GTK_FILE_FILTER_MIME_TYPE)

    {

      const char *s = g_file_info_get_content_type (node->info);

      if (s)

	{

	  mime_type = g_content_type_get_mime_type (s);

	  if (mime_type)

	    {

	      filter_info.mime_type = mime_type;

	      filter_info.contains |= GTK_FILE_FILTER_MIME_TYPE;

	    }

	}

    }

  if (required & GTK_FILE_FILTER_FILENAME)

    {

      filename = g_file_get_path (node->file);

      if (filename)

        {

          filter_info.filename = filename;

	  filter_info.contains |= GTK_FILE_FILTER_FILENAME;

        }

    }

  if (required & GTK_FILE_FILTER_URI)

    {

      uri = g_file_get_uri (node->file);

      if (uri)

        {

          filter_info.uri = uri;

	  filter_info.contains |= GTK_FILE_FILTER_URI;

        }

    }

  result = !gtk_file_filter_filter (model->filter, &filter_info);

  g_free (mime_type);

  g_free (filename);

  g_free (uri);

  return result;

}

static gboolean

node_should_be_visible (GtkFileSystemModel *model, guint id, gboolean filtered_out)

{

  FileModelNode *node = get_node (model, id);

  gboolean result;

  if (node->info == NULL)

    return FALSE;

  if (!model->show_hidden &&

      (g_file_info_get_is_hidden (node->info) || g_file_info_get_is_backup (node->info)))

    return FALSE;

  if (_gtk_file_info_consider_as_directory (node->info))

    {

      if (!model->show_folders)

        return FALSE;

      if (!model->filter_folders)

        return TRUE;

    }

  else

    {

      if (!model->show_files)

        return FALSE;

    }

  result = !filtered_out;

  return result;

}

static void

node_compute_visibility_and_filters (GtkFileSystemModel *model, guint id)

{

  gboolean filtered_out;

  gboolean visible;

  filtered_out = node_should_be_filtered_out (model, id);

  visible = node_should_be_visible (model, id, filtered_out);

  node_set_visible_and_filtered_out (model, id, visible, filtered_out);

}

/*** GtkTreeModel ***/

static GtkTreeModelFlags

gtk_file_system_model_get_flags (GtkTreeModel *tree_model)

{

  /* GTK_TREE_MODEL_ITERS_PERSIST doesn't work with arrays :( */

  return GTK_TREE_MODEL_LIST_ONLY;

}

static gint

gtk_file_system_model_get_n_columns (GtkTreeModel *tree_model)

{

  GtkFileSystemModel *model = GTK_FILE_SYSTEM_MODEL (tree_model);

  return model->n_columns;

}

static GType

gtk_file_system_model_get_column_type (GtkTreeModel *tree_model,

				       gint          i)

{

  GtkFileSystemModel *model = GTK_FILE_SYSTEM_MODEL (tree_model);

  g_return_val_if_fail (i >= 0 && (guint) i < model->n_columns, G_TYPE_NONE);

  return model->column_types[i];

}

static int

compare_indices (gconstpointer key, gconstpointer _node)

{

  const FileModelNode *node = _node;

  return GPOINTER_TO_UINT (key) - node->row;

}

static gboolean

gtk_file_system_model_iter_nth_child (GtkTreeModel *tree_model,

				      GtkTreeIter  *iter,

				      GtkTreeIter  *parent,

				      gint          n)

{

  GtkFileSystemModel *model = GTK_FILE_SYSTEM_MODEL (tree_model);

  char *node;

  guint id;

  guint row_to_find;

  g_return_val_if_fail (n >= 0, FALSE);

  if (parent != NULL)

    return FALSE;

  row_to_find = n + 1; /* plus one as our node->row numbers are 1-based; see the "Structure" comment at the beginning */

  if (model->n_nodes_valid > 0 &&

      get_node (model, model->n_nodes_valid - 1)->row >= row_to_find)

    {

      /* Fast path - the nodes are valid up to the sought one.

       *

       * First, find a node with the sought row number...*/

      node = bsearch (GUINT_TO_POINTER (row_to_find), 

                      model->files->data,

                      model->n_nodes_valid,

                      model->node_size,

                      compare_indices);

      if (node == NULL)

        return FALSE;

      /* ... Second, back up until we find the first visible node with that row number */

      id = node_index (model, node);

      while (!get_node (model, id)->visible)

        id--;

      g_assert (get_node (model, id)->row == row_to_find);

    }

  else

    {

      /* Slow path - the nodes need to be validated up to the sought one */

      node_validate_rows (model, G_MAXUINT, n); /* note that this is really "n", not row_to_find - see node_validate_rows() */

      id = model->n_nodes_valid - 1;

      if (model->n_nodes_valid == 0 || get_node (model, id)->row != row_to_find)

        return FALSE;

    }

  ITER_INIT_FROM_INDEX (model, iter, id);

  return TRUE;

}

static gboolean

gtk_file_system_model_get_iter (GtkTreeModel *tree_model,

				GtkTreeIter  *iter,

				GtkTreePath  *path)

{

  g_return_val_if_fail (gtk_tree_path_get_depth (path) > 0, FALSE);

  if (gtk_tree_path_get_depth (path) > 1)

    return FALSE;

  return gtk_file_system_model_iter_nth_child (tree_model, 

                                               iter,

                                               NULL, 

                                               gtk_tree_path_get_indices (path)[0]);

}

static GtkTreePath *

gtk_file_system_model_get_path (GtkTreeModel *tree_model,

				GtkTreeIter  *iter)

{

  GtkFileSystemModel *model = GTK_FILE_SYSTEM_MODEL (tree_model);

  g_return_val_if_fail (ITER_IS_VALID (model, iter), NULL);

  return tree_path_new_from_node (model, ITER_INDEX (iter));

}

static void

gtk_file_system_model_get_value (GtkTreeModel *tree_model,

				 GtkTreeIter  *iter,

				 gint          column,

				 GValue       *value)

{

  GtkFileSystemModel *model = GTK_FILE_SYSTEM_MODEL (tree_model);

  const GValue *original;

  g_return_if_fail ((guint) column < model->n_columns);

  g_return_if_fail (ITER_IS_VALID (model, iter));

  original = _gtk_file_system_model_get_value (model, iter, column);

  if (original)

    {

      g_value_init (value, G_VALUE_TYPE (original));

      g_value_copy (original, value);

    }

  else

    g_value_init (value, model->column_types[column]);

}

static gboolean

gtk_file_system_model_iter_next (GtkTreeModel *tree_model,

				 GtkTreeIter  *iter)

{

  GtkFileSystemModel *model = GTK_FILE_SYSTEM_MODEL (tree_model);

  guint i;

  g_return_val_if_fail (ITER_IS_VALID (model, iter), FALSE);

  for (i = ITER_INDEX (iter) + 1; i < model->files->len; i++) 

    {

      FileModelNode *node = get_node (model, i);

      if (node->visible)

        {

          ITER_INIT_FROM_INDEX (model, iter, i);

          return TRUE;

        }

    }

  return FALSE;

}

static gboolean

gtk_file_system_model_iter_children (GtkTreeModel *tree_model,

				     GtkTreeIter  *iter,

				     GtkTreeIter  *parent)

{

  return FALSE;

}

static gboolean

gtk_file_system_model_iter_has_child (GtkTreeModel *tree_model,

				      GtkTreeIter  *iter)

{

  return FALSE;

}

static gint

gtk_file_system_model_iter_n_children (GtkTreeModel *tree_model,

				       GtkTreeIter  *iter)

{

  GtkFileSystemModel *model = GTK_FILE_SYSTEM_MODEL (tree_model);

  if (iter)

    return 0;

  return node_get_tree_row (model, model->files->len - 1) + 1;

}

static gboolean

gtk_file_system_model_iter_parent (GtkTreeModel *tree_model,

				   GtkTreeIter  *iter,

				   GtkTreeIter  *child)

{

  return FALSE;

}

static void

gtk_file_system_model_ref_node (GtkTreeModel *tree_model,

				GtkTreeIter  *iter)

{

  /* nothing to do */

}

static void

gtk_file_system_model_unref_node (GtkTreeModel *tree_model,

				  GtkTreeIter  *iter)

{

  /* nothing to do */

}

static void

gtk_file_system_model_iface_init (GtkTreeModelIface *iface)

{

  iface->get_flags =       gtk_file_system_model_get_flags;

  iface->get_n_columns =   gtk_file_system_model_get_n_columns;

  iface->get_column_type = gtk_file_system_model_get_column_type;

  iface->get_iter =        gtk_file_system_model_get_iter;

  iface->get_path =        gtk_file_system_model_get_path;

  iface->get_value =       gtk_file_system_model_get_value;

  iface->iter_next =       gtk_file_system_model_iter_next;

  iface->iter_children =   gtk_file_system_model_iter_children;

  iface->iter_has_child =  gtk_file_system_model_iter_has_child;

  iface->iter_n_children = gtk_file_system_model_iter_n_children;

  iface->iter_nth_child =  gtk_file_system_model_iter_nth_child;

  iface->iter_parent =     gtk_file_system_model_iter_parent;

  iface->ref_node =        gtk_file_system_model_ref_node;

  iface->unref_node =      gtk_file_system_model_unref_node;

}

/*** GtkTreeSortable ***/

typedef struct _SortData SortData;

struct _SortData {

  GtkFileSystemModel *    model;

  GtkTreeIterCompareFunc  func;

  gpointer                data;

  int                     order;        /* -1 to invert sort order or 1 to keep it */

};

/* returns FALSE if no sort necessary */

static gboolean

sort_data_init (SortData *data, GtkFileSystemModel *model)

{

  GtkTreeDataSortHeader *header;

  if (model->files->len <= 2)

    return FALSE;

  switch (model->sort_column_id)

    {

    case GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID:

      if (!model->default_sort_func)

        return FALSE;

      data->func = model->default_sort_func;

      data->data = model->default_sort_data;

      break;

    case GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID:

      return FALSE;

    default:

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

      if (header == NULL)

        return FALSE;

      data->func = header->func;

      data->data = header->data;

      break;

    }

  data->order = model->sort_order == GTK_SORT_DESCENDING ? -1 : 1;

  data->model = model;

  return TRUE;

}

static int

compare_array_element (gconstpointer a, gconstpointer b, gpointer user_data)

{

  SortData *data = user_data;

  GtkTreeIter itera, iterb;

  ITER_INIT_FROM_INDEX (data->model, &itera, node_index (data->model, a));

  ITER_INIT_FROM_INDEX (data->model, &iterb, node_index (data->model, b));

  return data->func (GTK_TREE_MODEL (data->model), &itera, &iterb, data->data) * data->order;

}

static void

gtk_file_system_model_sort (GtkFileSystemModel *model)

{

  SortData data;

  if (model->frozen)

    {

      model->sort_on_thaw = TRUE;

      return;

    }

  if (sort_data_init (&data, model))

    {

      GtkTreePath *path;

      guint i;

      guint r, n_visible_rows;

      node_validate_rows (model, G_MAXUINT, G_MAXUINT);

      n_visible_rows = node_get_tree_row (model, model->files->len - 1) + 1;

      model->n_nodes_valid = 0;

      g_hash_table_remove_all (model->file_lookup);

      g_qsort_with_data (get_node (model, 1), /* start at index 1; don't sort the editable row */

                         model->files->len - 1,

                         model->node_size,

                         compare_array_element,

                         &data);

      g_assert (model->n_nodes_valid == 0);

      g_assert (g_hash_table_size (model->file_lookup) == 0);

      if (n_visible_rows)

        {

          int *new_order = g_new (int, n_visible_rows);

          r = 0;

          for (i = 0; i < model->files->len; i++)

            {

              FileModelNode *node = get_node (model, i);

              if (!node->visible)

                {

                  node->row = r;

                  continue;

                }

              new_order[r] = node->row - 1;

              r++;

              node->row = r;

            }

          g_assert (r == n_visible_rows);

          path = gtk_tree_path_new ();

          gtk_tree_model_rows_reordered (GTK_TREE_MODEL (model),

                                         path,

                                         NULL,

                                         new_order);

          gtk_tree_path_free (path);

          g_free (new_order);

        }

    }

  model->sort_on_thaw = FALSE;

}

static void

gtk_file_system_model_sort_node (GtkFileSystemModel *model, guint node)

{

  /* FIXME: improve */

  gtk_file_system_model_sort (model);

}

static gboolean

gtk_file_system_model_get_sort_column_id (GtkTreeSortable  *sortable,

                                          gint             *sort_column_id,

                                          GtkSortType      *order)

{

  GtkFileSystemModel *model = GTK_FILE_SYSTEM_MODEL (sortable);

  if (sort_column_id)

    *sort_column_id = model->sort_column_id;

  if (order)

    *order = model->sort_order;

  if (model->sort_column_id == GTK_TREE_SORTABLE_DEFAULT_SORT_COLUMN_ID ||

      model->sort_column_id == GTK_TREE_SORTABLE_UNSORTED_SORT_COLUMN_ID)

    return FALSE;

  return TRUE;

}

static void

gtk_file_system_model_set_sort_column_id (GtkTreeSortable  *sortable,

                                          gint              sort_column_id,

                                          GtkSortType       order)

{

  GtkFileSystemModel *model = GTK_FILE_SYSTEM_MODEL (sortable);

  if ((model->sort_column_id == sort_column_id) &&

      (model->sort_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 (model->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);