From 41dfcdb070f5c052908ca15bb304c91ae637795c Mon Sep 17 00:00:00 2001 From: Milan Crha Date: Wed, 20 Jan 2010 15:48:31 +0100 Subject: Bug #606301 - Slow sort by subject --- widgets/table/e-table-sorting-utils.c | 131 +++++++++++++++++++++++++++++----- 1 file changed, 113 insertions(+), 18 deletions(-) (limited to 'widgets/table/e-table-sorting-utils.c') diff --git a/widgets/table/e-table-sorting-utils.c b/widgets/table/e-table-sorting-utils.c index 344a7cf6b1..8ad797a9d1 100644 --- a/widgets/table/e-table-sorting-utils.c +++ b/widgets/table/e-table-sorting-utils.c @@ -24,6 +24,8 @@ #include +#include + #include "e-util/e-util.h" #include "e-table-sorting-utils.h" @@ -32,7 +34,7 @@ /* This takes source rows. */ static gint -etsu_compare(ETableModel *source, ETableSortInfo *sort_info, ETableHeader *full_header, gint row1, gint row2) +etsu_compare(ETableModel *source, ETableSortInfo *sort_info, ETableHeader *full_header, gint row1, gint row2, gpointer cmp_cache) { gint j; gint sort_count = e_table_sort_info_sorting_get_count(sort_info); @@ -46,7 +48,8 @@ etsu_compare(ETableModel *source, ETableSortInfo *sort_info, ETableHeader *full_ if (col == NULL) col = e_table_header_get_column (full_header, e_table_header_count (full_header) - 1); comp_val = (*col->compare)(e_table_model_value_at (source, col->compare_col, row1), - e_table_model_value_at (source, col->compare_col, row2)); + e_table_model_value_at (source, col->compare_col, row2), + cmp_cache); ascending = column.ascending; if (comp_val != 0) break; @@ -66,13 +69,15 @@ typedef struct { gint cols; gpointer *vals; gint *ascending; - GCompareFunc *compare; + GCompareDataFunc *compare; + gpointer cmp_cache; } ETableSortClosure; typedef struct { ETreeModel *tree; ETableSortInfo *sort_info; ETableHeader *full_header; + gpointer cmp_cache; } ETreeSortClosure; /* FIXME: Make it not cache the second and later columns (as if anyone cares.) */ @@ -88,7 +93,7 @@ e_sort_callback(gconstpointer data1, gconstpointer data2, gpointer user_data) gint comp_val = 0; gint ascending = 1; for (j = 0; j < sort_count; j++) { - comp_val = (*(closure->compare[j]))(closure->vals[closure->cols * row1 + j], closure->vals[closure->cols * row2 + j]); + comp_val = (*(closure->compare[j]))(closure->vals[closure->cols * row1 + j], closure->vals[closure->cols * row2 + j], closure->cmp_cache); ascending = closure->ascending[j]; if (comp_val != 0) break; @@ -126,7 +131,8 @@ e_table_sorting_utils_sort(ETableModel *source, ETableSortInfo *sort_info, ETabl closure.vals = g_new(gpointer , total_rows * cols); closure.ascending = g_new(int, cols); - closure.compare = g_new(GCompareFunc, cols); + closure.compare = g_new(GCompareDataFunc, cols); + closure.cmp_cache = e_table_sorting_utils_create_cmp_cache (); for (j = 0; j < cols; j++) { ETableSortColumn column = e_table_sort_info_sorting_get_nth(sort_info, j); @@ -147,6 +153,7 @@ e_table_sorting_utils_sort(ETableModel *source, ETableSortInfo *sort_info, ETabl g_free(closure.vals); g_free(closure.ascending); g_free(closure.compare); + e_table_sorting_utils_free_cmp_cache (closure.cmp_cache); } gboolean @@ -181,12 +188,15 @@ gint e_table_sorting_utils_insert(ETableModel *source, ETableSortInfo *sort_info, ETableHeader *full_header, gint *map_table, gint rows, gint row) { gint i; + gpointer cmp_cache = e_table_sorting_utils_create_cmp_cache (); i = 0; /* handle insertions when we have a 'sort group' */ - while (i < rows && etsu_compare(source, sort_info, full_header, map_table[i], row) < 0) + while (i < rows && etsu_compare(source, sort_info, full_header, map_table[i], row, cmp_cache) < 0) i++; + e_table_sorting_utils_free_cmp_cache (cmp_cache); + return i; } @@ -196,26 +206,31 @@ e_table_sorting_utils_check_position (ETableModel *source, ETableSortInfo *sort_ { gint i; gint row; + gpointer cmp_cache; i = view_row; row = map_table[i]; + cmp_cache = e_table_sorting_utils_create_cmp_cache (); i = view_row; - if (i < rows - 1 && etsu_compare(source, sort_info, full_header, map_table[i + 1], row) < 0) { + if (i < rows - 1 && etsu_compare(source, sort_info, full_header, map_table[i + 1], row, cmp_cache) < 0) { i ++; - while (i < rows - 1 && etsu_compare(source, sort_info, full_header, map_table[i], row) < 0) + while (i < rows - 1 && etsu_compare(source, sort_info, full_header, map_table[i], row, cmp_cache) < 0) i ++; - } else if (i > 0 && etsu_compare(source, sort_info, full_header, map_table[i - 1], row) > 0) { + } else if (i > 0 && etsu_compare(source, sort_info, full_header, map_table[i - 1], row, cmp_cache) > 0) { i --; - while (i > 0 && etsu_compare(source, sort_info, full_header, map_table[i], row) > 0) + while (i > 0 && etsu_compare(source, sort_info, full_header, map_table[i], row, cmp_cache) > 0) i --; } + + e_table_sorting_utils_free_cmp_cache (cmp_cache); + return i; } /* This takes source rows. */ static gint -etsu_tree_compare(ETreeModel *source, ETableSortInfo *sort_info, ETableHeader *full_header, ETreePath path1, ETreePath path2) +etsu_tree_compare(ETreeModel *source, ETableSortInfo *sort_info, ETableHeader *full_header, ETreePath path1, ETreePath path2, gpointer cmp_cache) { gint j; gint sort_count = e_table_sort_info_sorting_get_count(sort_info); @@ -229,7 +244,8 @@ etsu_tree_compare(ETreeModel *source, ETableSortInfo *sort_info, ETableHeader *f if (col == NULL) col = e_table_header_get_column (full_header, e_table_header_count (full_header) - 1); comp_val = (*col->compare)(e_tree_model_value_at (source, path1, col->compare_col), - e_tree_model_value_at (source, path2, col->compare_col)); + e_tree_model_value_at (source, path2, col->compare_col), + cmp_cache); ascending = column.ascending; if (comp_val != 0) break; @@ -246,7 +262,7 @@ e_sort_tree_callback(gconstpointer data1, gconstpointer data2, gpointer user_dat ETreePath *path2 = *(ETreePath *)data2; ETreeSortClosure *closure = user_data; - return etsu_tree_compare(closure->tree, closure->sort_info, closure->full_header, path1, path2); + return etsu_tree_compare (closure->tree, closure->sort_info, closure->full_header, path1, path2, closure->cmp_cache); } void @@ -269,7 +285,8 @@ e_table_sorting_utils_tree_sort(ETreeModel *source, ETableSortInfo *sort_info, E closure.vals = g_new(gpointer , count * cols); closure.ascending = g_new(int, cols); - closure.compare = g_new(GCompareFunc, cols); + closure.compare = g_new (GCompareDataFunc, cols); + closure.cmp_cache = e_table_sorting_utils_create_cmp_cache (); for (j = 0; j < cols; j++) { ETableSortColumn column = e_table_sort_info_sorting_get_nth(sort_info, j); @@ -308,6 +325,7 @@ e_table_sorting_utils_tree_sort(ETreeModel *source, ETableSortInfo *sort_info, E g_free(closure.vals); g_free(closure.ascending); g_free(closure.compare); + e_table_sorting_utils_free_cmp_cache (closure.cmp_cache); } /* FIXME: This could be done in time log n instead of time n with a binary search. */ @@ -316,19 +334,23 @@ e_table_sorting_utils_tree_check_position (ETreeModel *source, ETableSortInfo *s { gint i; ETreePath path; + gpointer cmp_cache = e_table_sorting_utils_create_cmp_cache (); i = old_index; path = map_table[i]; - if (i < count - 1 && etsu_tree_compare(source, sort_info, full_header, map_table[i + 1], path) < 0) { + if (i < count - 1 && etsu_tree_compare(source, sort_info, full_header, map_table[i + 1], path, cmp_cache) < 0) { i ++; - while (i < count - 1 && etsu_tree_compare(source, sort_info, full_header, map_table[i], path) < 0) + while (i < count - 1 && etsu_tree_compare(source, sort_info, full_header, map_table[i], path, cmp_cache) < 0) i ++; - } else if (i > 0 && etsu_tree_compare(source, sort_info, full_header, map_table[i - 1], path) > 0) { + } else if (i > 0 && etsu_tree_compare(source, sort_info, full_header, map_table[i - 1], path, cmp_cache) > 0) { i --; - while (i > 0 && etsu_tree_compare(source, sort_info, full_header, map_table[i], path) > 0) + while (i > 0 && etsu_tree_compare(source, sort_info, full_header, map_table[i], path, cmp_cache) > 0) i --; } + + e_table_sorting_utils_free_cmp_cache (cmp_cache); + return i; } @@ -343,7 +365,80 @@ e_table_sorting_utils_tree_insert(ETreeModel *source, ETableSortInfo *sort_info, closure.tree = source; closure.sort_info = sort_info; closure.full_header = full_header; + closure.cmp_cache = e_table_sorting_utils_create_cmp_cache (); e_bsearch(&path, map_table, count, sizeof(ETreePath), e_sort_tree_callback, &closure, &start, &end); + + e_table_sorting_utils_free_cmp_cache (closure.cmp_cache); + return end; } + +/** + * e_table_sorting_utils_create_cmp_cache: + * + * Creates a new compare cache, which is storing pairs of string keys and string values. + * This can be accessed by @ref e_table_sorting_utils_lookup_cmp_cache and + * @ref e_table_sorting_utils_add_to_cmp_cache. + * + * Returned pointer should be freed with @ref e_table_sorting_utils_free_cmp_cache. + **/ +gpointer +e_table_sorting_utils_create_cmp_cache (void) +{ + return g_hash_table_new_full (g_str_hash, g_str_equal, (GDestroyNotify) camel_pstring_free, g_free); +} + +/** + * e_table_sorting_utils_free_cmp_cache: + * @cmp_cache: a compare cache; cannot be %NULL + * + * Frees a compare cache previously created + * with @ref e_table_sorting_utils_create_cmp_cache. + **/ +void +e_table_sorting_utils_free_cmp_cache (gpointer cmp_cache) +{ + g_return_if_fail (cmp_cache != NULL); + + g_hash_table_destroy (cmp_cache); +} + +/** + * e_table_sorting_utils_add_to_cmp_cache: + * @cmp_cache: a compare cache; cannot be %NULL + * @key: unique key to a cache; cannot be %NULL + * @value: value to store for a key + * + * Adds a new value for a given key to a compare cache. If such key + * already exists in a cache then its value will be replaced. + * Note: Given @value will be stolen and later freed with g_free. + **/ +void +e_table_sorting_utils_add_to_cmp_cache (gpointer cmp_cache, const gchar *key, gchar *value) +{ + g_return_if_fail (cmp_cache != NULL); + g_return_if_fail (key != NULL); + + g_hash_table_insert (cmp_cache, (gchar *) camel_pstring_strdup (key), value); +} + +/** + * e_table_sorting_utils_lookup_cmp_cache: + * @cmp_cache: a compare cache + * @key: unique key to a cache + * + * Lookups for a key in a compare cache, which is passed in GCompareDataFunc as 'data'. + * Returns %NULL when not found or the cache wasn't provided, otherwise value stored + * with a key. + **/ +const gchar * +e_table_sorting_utils_lookup_cmp_cache (gpointer cmp_cache, const gchar *key) +{ + g_return_val_if_fail (key != NULL, NULL); + + if (!cmp_cache) + return NULL; + + return g_hash_table_lookup (cmp_cache, key); +} -- cgit v1.2.3