From 1f89b12d0b057db33cf771d38e43aa29352f323a Mon Sep 17 00:00:00 2001 From: Christopher James Lahey Date: Thu, 4 May 2000 01:36:06 +0000 Subject: Replace insert sort completely with a qsort. 2000-05-04 Christopher James Lahey * e-table-sorted-variable.c: Replace insert sort completely with a qsort. svn path=/trunk/; revision=2786 --- widgets/e-table/ChangeLog | 7 +- widgets/e-table/e-table-sorted-variable.c | 139 +++++++++++++----------------- widgets/e-table/e-table-sorted-variable.h | 1 + 3 files changed, 69 insertions(+), 78 deletions(-) (limited to 'widgets/e-table') diff --git a/widgets/e-table/ChangeLog b/widgets/e-table/ChangeLog index 3939f479cc..19a6e05620 100644 --- a/widgets/e-table/ChangeLog +++ b/widgets/e-table/ChangeLog @@ -1,8 +1,13 @@ +2000-05-04 Christopher James Lahey + + * e-table-sorted-variable.c: Replace insert sort completely with a + qsort. + 2000-05-04 Christopher James Lahey * e-table-sorted-variable.c: Changed the insert sort to be binary instead of linear. - + 2000-05-02 Matt Loper * Makefile.am: set G_LOG_DOMAIN. diff --git a/widgets/e-table/e-table-sorted-variable.c b/widgets/e-table/e-table-sorted-variable.c index 79840cc259..c687ebc871 100644 --- a/widgets/e-table/e-table-sorted-variable.c +++ b/widgets/e-table/e-table-sorted-variable.c @@ -20,11 +20,12 @@ static ETableSubsetVariableClass *etsv_parent_class; -static void etsv_proxy_model_changed (ETableModel *etm, ETableSortedVariable *etsv); -static void etsv_proxy_model_row_changed (ETableModel *etm, int row, ETableSortedVariable *etsv); +static void etsv_proxy_model_changed (ETableModel *etm, ETableSortedVariable *etsv); +static void etsv_proxy_model_row_changed (ETableModel *etm, int row, ETableSortedVariable *etsv); static void etsv_proxy_model_cell_changed (ETableModel *etm, int col, int row, ETableSortedVariable *etsv); -static void etsv_sort_info_changed (ETableSortInfo *info, ETableSortedVariable *etsv); -static void etsv_add (ETableSubsetVariable *etssv, gint row); +static void etsv_sort_info_changed (ETableSortInfo *info, ETableSortedVariable *etsv); +static void etsv_sort (ETableSortedVariable *etsv); +static void etsv_add (ETableSubsetVariable *etssv, gint row); static void etsv_destroy (GtkObject *object) @@ -41,6 +42,10 @@ etsv_destroy (GtkObject *object) gtk_signal_disconnect (GTK_OBJECT (etsv->sort_info), etsv->sort_info_changed_id); + if (etsv->sort_idle_id) { + g_source_remove(etsv->sort_idle_id); + } + etsv->table_model_changed_id = 0; etsv->table_model_row_changed_id = 0; etsv->table_model_cell_changed_id = 0; @@ -65,45 +70,28 @@ etsv_class_init (GtkObjectClass *object_class) etssv_class->add = etsv_add; } -E_MAKE_TYPE(e_table_sorted_variable, "ETableSortedVariable", ETableSortedVariable, etsv_class_init, NULL, PARENT_TYPE); +static void +etsv_init (ETableSortedVariable *etsv) +{ + etsv->full_header = NULL; + etsv->sort_info = NULL; -static int -etsv_compare(ETableSortedVariable *etsv, - gint row1, - gint row2) + etsv->table_model_changed_id = 0; + etsv->table_model_row_changed_id = 0; + etsv->table_model_cell_changed_id = 0; + etsv->sort_info_changed_id = 0; + + etsv->sort_idle_id = 0; +} + +E_MAKE_TYPE(e_table_sorted_variable, "ETableSortedVariable", ETableSortedVariable, etsv_class_init, etsv_init, PARENT_TYPE); + +static gboolean +etsv_sort_idle(ETableSortedVariable *etsv) { - static ETableCol *last_col = NULL; - static int last_row = -1; - static void *val = NULL; - ETableSubset *etss = E_TABLE_SUBSET(etsv); - int j; - int sort_count = e_table_sort_info_sorting_get_count(etsv->sort_info); - int comp_val = 0; - int ascending = 1; - for (j = 0; j < sort_count; j++) { - ETableSortColumn column = e_table_sort_info_sorting_get_nth(etsv->sort_info, j); - ETableCol *col; - if (column.column > e_table_header_count (etsv->full_header)) - col = e_table_header_get_columns (etsv->full_header)[e_table_header_count (etsv->full_header) - 1]; - else - col = e_table_header_get_columns (etsv->full_header)[column.column]; - if (last_col != col || last_row != row1) - val = e_table_model_value_at (etss->source, col->col_idx, row1); - last_col = col; - comp_val = (*col->compare)(val, e_table_model_value_at (etss->source, col->col_idx, row2)); - ascending = column.ascending; - if (comp_val != 0) - break; - } - if (comp_val == 0) { - if (row1 < row2) - comp_val = -1; - if (row1 > row2) - comp_val = 1; - } - if (!ascending) - comp_val = -comp_val; - return comp_val; + etsv_sort(etsv); + etsv->sort_idle_id = 0; + return FALSE; } static void @@ -112,31 +100,17 @@ etsv_add (ETableSubsetVariable *etssv, { ETableModel *etm = E_TABLE_MODEL(etssv); ETableSubset *etss = E_TABLE_SUBSET(etssv); - ETableSortedVariable *etsv = E_TABLE_SORTED_VARIABLE(etssv); - int i; - int length_to_search; - - /* FIXME: binary search anyone? */ + ETableSortedVariable *etsv = E_TABLE_SORTED_VARIABLE (etssv); - i = 0; - length_to_search = etss->n_map; - while(length_to_search > 1) { - int center = i + length_to_search / 2; - if (etsv_compare(etsv, row, etss->map_table[center])) - length_to_search /= 2; - else { - i += length_to_search / 2; - length_to_search -= length_to_search / 2; - } - } if (etss->n_map + 1 > etssv->n_vals_allocated){ etssv->n_vals_allocated += INCREMENT_AMOUNT; etss->map_table = g_realloc (etss->map_table, (etssv->n_vals_allocated) * sizeof(int)); } - if (i < etss->n_map) - memmove (etss->map_table + i + 1, etss->map_table + i, (etss->n_map - i) * sizeof(int)); - etss->map_table[i] = row; + etss->map_table[etss->n_map] = row; etss->n_map++; + if (etsv->sort_idle_id == 0) { + etsv->sort_idle_id = g_idle_add_full(50, (GSourceFunc) etsv_sort_idle, etsv, NULL); + } if (!etm->frozen) e_table_model_changed (etm); } @@ -197,45 +171,56 @@ etsv_proxy_model_cell_changed (ETableModel *etm, int col, int row, ETableSortedV } } +static void +etsv_sort_info_changed (ETableSortInfo *info, ETableSortedVariable *etsv) +{ + etsv_sort(etsv); +} + static ETableSortedVariable *etsv_closure; static int qsort_callback(const void *data1, const void *data2) { + gint row1 = *(int *)data1; + gint row2 = *(int *)data2; + static ETableCol *last_col = NULL; + static int last_row = -1; + static void *val = NULL; + ETableSubset *etss = E_TABLE_SUBSET(etsv_closure); int j; + int sort_count = e_table_sort_info_sorting_get_count(etsv_closure->sort_info); int comp_val = 0; int ascending = 1; - int sort_count = e_table_sort_info_sorting_get_count(etsv_closure->sort_info); - int row1 = *(int *)data1; - int row2 = *(int *)data2; - - while(gtk_events_pending()) - gtk_main_iteration(); for (j = 0; j < sort_count; j++) { ETableSortColumn column = e_table_sort_info_sorting_get_nth(etsv_closure->sort_info, j); ETableCol *col; - void *val; if (column.column > e_table_header_count (etsv_closure->full_header)) col = e_table_header_get_columns (etsv_closure->full_header)[e_table_header_count (etsv_closure->full_header) - 1]; else col = e_table_header_get_columns (etsv_closure->full_header)[column.column]; - val = e_table_model_value_at (E_TABLE_SUBSET(etsv_closure)->source, col->col_idx, row1); - comp_val = (*col->compare)(val, e_table_model_value_at (E_TABLE_SUBSET(etsv_closure)->source, col->col_idx, row2)); + if (last_col != col || last_row != row1) + val = e_table_model_value_at (etss->source, col->col_idx, row1); + last_col = col; + comp_val = (*col->compare)(val, e_table_model_value_at (etss->source, col->col_idx, row2)); ascending = column.ascending; if (comp_val != 0) break; } - if (((ascending && comp_val < 0) || ((!ascending) && comp_val > 0))) - return -1; - - if (comp_val == 0) - if ((ascending && row1 < row2) || ((!ascending) && row1 > row2)) - return -1; - return 1; + if (comp_val == 0) { + if (row1 < row2) + comp_val = -1; + if (row1 > row2) + comp_val = 1; + } + if (!ascending) + comp_val = -comp_val; + return comp_val; } + static void -etsv_sort_info_changed (ETableSortInfo *info, ETableSortedVariable *etsv) +etsv_sort(ETableSortedVariable *etsv) { etsv_closure = etsv; qsort(E_TABLE_SUBSET(etsv)->map_table, E_TABLE_SUBSET(etsv)->n_map, sizeof(int), qsort_callback); diff --git a/widgets/e-table/e-table-sorted-variable.h b/widgets/e-table/e-table-sorted-variable.h index 53740e85f0..c6a57c5ede 100644 --- a/widgets/e-table/e-table-sorted-variable.h +++ b/widgets/e-table/e-table-sorted-variable.h @@ -25,6 +25,7 @@ typedef struct { int table_model_row_changed_id; int table_model_cell_changed_id; int sort_info_changed_id; + int sort_idle_id; } ETableSortedVariable; typedef struct { -- cgit v1.2.3