diff options
| -rw-r--r-- | widgets/table/e-cell-tree.c | 14 | ||||
| -rw-r--r-- | widgets/table/e-table-model.c | 27 | ||||
| -rw-r--r-- | widgets/table/e-table-model.h | 7 | ||||
| -rw-r--r-- | widgets/table/e-table-sorted-variable.c | 348 | ||||
| -rw-r--r-- | widgets/table/e-table-sorted-variable.h | 3 | ||||
| -rw-r--r-- | widgets/table/e-tree-model.c | 46 | ||||
| -rw-r--r-- | widgets/table/e-tree-model.h | 1 |
7 files changed, 428 insertions, 18 deletions
diff --git a/widgets/table/e-cell-tree.c b/widgets/table/e-cell-tree.c index 0d159ded19..bae0ecaa8d 100644 --- a/widgets/table/e-cell-tree.c +++ b/widgets/table/e-cell-tree.c @@ -63,9 +63,9 @@ offset_of_node (ETreeModel *tree_model, ETreePath *path) } static ETreePath* -e_cell_tree_get_node (ETreeModel *tree_model, int row) +e_cell_tree_get_node (ETableModel *table_model, int row) { - return (ETreePath*)e_table_model_value_at (E_TABLE_MODEL(tree_model), -1, row); + return (ETreePath*)e_table_model_value_at (table_model, -1, row); } static ETreeModel* @@ -177,7 +177,7 @@ ect_draw (ECellView *ecell_view, GdkDrawable *drawable, int node_image_width = 0, node_image_height = 0; ETreePath *parent_node; - node = e_cell_tree_get_node (tree_model, row); + node = e_cell_tree_get_node (ecell_view->e_table_model, row); offset = offset_of_node (tree_model, node); expandable = e_tree_model_node_is_expandable (tree_model, node); @@ -304,7 +304,7 @@ ect_event (ECellView *ecell_view, GdkEvent *event, int model_col, int view_col, { ECellTreeView *tree_view = (ECellTreeView *) ecell_view; ETreeModel *tree_model = e_cell_tree_get_tree_model (ecell_view->e_table_model, row); - ETreePath *node = e_cell_tree_get_node (tree_model, row); + ETreePath *node = e_cell_tree_get_node (ecell_view->e_table_model, row); int offset = offset_of_node (tree_model, node); switch (event->type) { @@ -378,7 +378,7 @@ ect_max_width (ECellView *ecell_view, int model_col, int view_col) int offset, subcell_offset; gboolean expanded, expandable; - node = e_cell_tree_get_node (tree_model, row); + node = e_cell_tree_get_node (ecell_view->e_table_model, row); offset = offset_of_node (tree_model, node); expandable = e_tree_model_node_is_expandable (tree_model, node); @@ -422,7 +422,7 @@ ect_show_tooltip (ECellView *ecell_view, int model_col, int view_col, int row, { ECellTreeView *tree_view = (ECellTreeView *) ecell_view; ETreeModel *tree_model = e_cell_tree_get_tree_model (ecell_view->e_table_model, row); - ETreePath *node = e_cell_tree_get_node (tree_model, row); + ETreePath *node = e_cell_tree_get_node (ecell_view->e_table_model, row); int offset = offset_of_node (tree_model, node); GdkPixbuf *node_image; @@ -471,7 +471,7 @@ ect_print (ECellView *ecell_view, GnomePrintContext *context, if (/* XXX only if we're the active sort */ TRUE) { ETreeModel *tree_model = e_cell_tree_get_tree_model (ecell_view->e_table_model, row); - ETreePath *node = e_cell_tree_get_node (tree_model, row); + ETreePath *node = e_cell_tree_get_node (ecell_view->e_table_model, row); int offset = offset_of_node (tree_model, node); int subcell_offset = offset; gboolean expandable = e_tree_model_node_is_expandable (tree_model, node); diff --git a/widgets/table/e-table-model.c b/widgets/table/e-table-model.c index d9c0c4fd38..5138fb8edd 100644 --- a/widgets/table/e-table-model.c +++ b/widgets/table/e-table-model.c @@ -91,6 +91,30 @@ e_table_model_append_row (ETableModel *e_table_model, ETableModel *source, int r ETM_CLASS (e_table_model)->append_row (e_table_model, source, row); } +const char * +e_table_model_row_sort_group(ETableModel *e_table_model, int row) +{ + g_return_val_if_fail (e_table_model != NULL, "/"); + g_return_val_if_fail (E_IS_TABLE_MODEL (e_table_model), "/"); + + if (ETM_CLASS (e_table_model)->row_sort_group) + return ETM_CLASS (e_table_model)->row_sort_group (e_table_model, row); + else + return "/"; +} + +gboolean +e_table_model_has_sort_group(ETableModel *e_table_model) +{ + g_return_val_if_fail (e_table_model != NULL, FALSE); + g_return_val_if_fail (E_IS_TABLE_MODEL (e_table_model), FALSE); + + if (ETM_CLASS (e_table_model)->has_sort_group) + return ETM_CLASS (e_table_model)->has_sort_group (e_table_model); + else + return FALSE; +} + void * e_table_model_duplicate_value (ETableModel *e_table_model, int col, const void *value) { @@ -221,6 +245,9 @@ e_table_model_class_init (GtkObjectClass *object_class) klass->is_cell_editable = NULL; klass->append_row = NULL; + klass->row_sort_group = NULL; + klass->has_sort_group = NULL; + klass->duplicate_value = NULL; klass->free_value = NULL; klass->initialize_value = NULL; diff --git a/widgets/table/e-table-model.h b/widgets/table/e-table-model.h index d4fae1659e..b58614d150 100644 --- a/widgets/table/e-table-model.h +++ b/widgets/table/e-table-model.h @@ -27,6 +27,10 @@ typedef struct { gboolean (*is_cell_editable) (ETableModel *etm, int col, int row); void (*append_row) (ETableModel *etm, ETableModel *source, int row); + /* the sort group id for this row */ + const char *(*row_sort_group) (ETableModel *etm, int row); + gboolean (*has_sort_group) (ETableModel *etm); + /* Allocate a copy of the given value. */ void *(*duplicate_value) (ETableModel *etm, int col, const void *value); /* Free an allocated value. */ @@ -69,6 +73,9 @@ void e_table_model_set_value_at (ETableModel *e_table_model, int col, gboolean e_table_model_is_cell_editable (ETableModel *e_table_model, int col, int row); void e_table_model_append_row (ETableModel *e_table_model, ETableModel *source, int row); +const char *e_table_model_row_sort_group (ETableModel *e_table_model, int row); +gboolean e_table_model_has_sort_group (ETableModel *e_table_model); + void *e_table_model_duplicate_value (ETableModel *e_table_model, int col, const void *value); void e_table_model_free_value (ETableModel *e_table_model, int col, void *value); void *e_table_model_initialize_value (ETableModel *e_table_model, int col); diff --git a/widgets/table/e-table-sorted-variable.c b/widgets/table/e-table-sorted-variable.c index a9907079d0..f6682ca28b 100644 --- a/widgets/table/e-table-sorted-variable.c +++ b/widgets/table/e-table-sorted-variable.c @@ -14,10 +14,15 @@ #include "gal/util/e-util.h" #include "e-table-sorted-variable.h" +#define d(x) + #define PARENT_TYPE E_TABLE_SUBSET_VARIABLE_TYPE #define INCREMENT_AMOUNT 100 +/* maximum insertions between an idle event that we will do without scheduling an idle sort */ +#define ETSV_INSERT_MAX (4) + static ETableSubsetVariableClass *etsv_parent_class; static void etsv_proxy_model_changed (ETableModel *etm, ETableSortedVariable *etsv); @@ -54,7 +59,7 @@ etsv_destroy (GtkObject *object) etsv->table_model_changed_id = 0; etsv->table_model_row_changed_id = 0; etsv->table_model_cell_changed_id = 0; - + if (etsv->sort_info) gtk_object_unref(GTK_OBJECT(etsv->sort_info)); if (etsv->full_header) @@ -88,6 +93,7 @@ etsv_init (ETableSortedVariable *etsv) etsv->sort_info_changed_id = 0; etsv->sort_idle_id = 0; + etsv->insert_count = 0; } E_MAKE_TYPE(e_table_sorted_variable, "ETableSortedVariable", ETableSortedVariable, etsv_class_init, etsv_init, PARENT_TYPE); @@ -98,10 +104,19 @@ etsv_sort_idle(ETableSortedVariable *etsv) gtk_object_ref(GTK_OBJECT(etsv)); etsv_sort(etsv); etsv->sort_idle_id = 0; + etsv->insert_count = 0; gtk_object_unref(GTK_OBJECT(etsv)); return FALSE; } +static gboolean +etsv_insert_idle(ETableSortedVariable *etsv) +{ + etsv->insert_count = 0; + etsv->insert_idle_id = 0; + return FALSE; +} + /* This takes source rows. */ static int etsv_compare(ETableSortedVariable *etsv, int row1, int row2) @@ -145,17 +160,71 @@ etsv_add (ETableSubsetVariable *etssv, ETableSubset *etss = E_TABLE_SUBSET(etssv); ETableSortedVariable *etsv = E_TABLE_SORTED_VARIABLE (etssv); int i; - + 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)); } i = etss->n_map; if (etsv->sort_idle_id == 0) { - i = 0; - while (i < etss->n_map && etsv_compare(etsv, etss->map_table[i], row) < 0) - i++; - memmove(etss->map_table + i + 1, etss->map_table + i, (etss->n_map - i) * sizeof(int)); + /* this is to see if we're inserting a lot of things between idle loops. + If we are, we're busy, its faster to just append and perform a full sort later */ + etsv->insert_count++; + if (etsv->insert_count > ETSV_INSERT_MAX) { + /* schedule a sort, and append instead */ + etsv->sort_idle_id = g_idle_add_full(50, (GSourceFunc) etsv_sort_idle, etsv, NULL); + } else { + /* make sure we have an idle handler to reset the count every now and then */ + if (etsv->insert_idle_id == 0) { + etsv->insert_idle_id = g_idle_add_full(40, (GSourceFunc) etsv_insert_idle, etsv, NULL); + } + i = 0; + /* handle insertions when we have a 'sort group' */ + if (e_table_model_has_sort_group(etss->source)) { + /* find the row this row maps to */ + char *group = g_strdup(e_table_model_row_sort_group(etss->source, row)); + const char *newgroup; + int cmp, grouplen, newgrouplen; + + newgroup = strrchr(group, '/'); + grouplen = strlen(group); + if (newgroup) + cmp = newgroup-group; + else + cmp = grouplen; + + /* find first common parent */ + while (i<etss->n_map) { + newgroup = e_table_model_row_sort_group(etss->source, etss->map_table[i]); + if (strncmp(newgroup, group, cmp) == 0) { + break; + } + i++; + } + + /* check matching records */ + while (i<etss->n_map) { + newgroup = e_table_model_row_sort_group(etss->source, etss->map_table[i]); + newgrouplen = strlen(newgroup); + if (strncmp(newgroup, group, cmp) == 0) { + /* common parent, check for same level */ + if (grouplen == newgrouplen) { + if (etsv_compare(etsv, etss->map_table[i], row) >= 0) + break; + } + } else { + /* ran out of common parents, insert here */ + break; + } + i++; + } + g_free(group); + } else { + while (i < etss->n_map && etsv_compare(etsv, etss->map_table[i], row) < 0) + i++; + } + memmove(etss->map_table + i + 1, etss->map_table + i, (etss->n_map - i) * sizeof(int)); + } } etss->map_table[i] = row; etss->n_map++; @@ -175,7 +244,7 @@ etsv_add_all (ETableSubsetVariable *etssv) e_table_model_pre_change(etm); rows = e_table_model_row_count(etss->source); - + if (etss->n_map + rows > etssv->n_vals_allocated){ etssv->n_vals_allocated += MAX(INCREMENT_AMOUNT, rows); etss->map_table = g_realloc (etss->map_table, etssv->n_vals_allocated * sizeof(int)); @@ -200,7 +269,7 @@ e_table_sorted_variable_new (ETableModel *source, ETableHeader *full_header, ETa gtk_object_destroy (GTK_OBJECT (etsv)); return NULL; } - + etsv->sort_info = sort_info; gtk_object_ref(GTK_OBJECT(etsv->sort_info)); etsv->full_header = full_header; @@ -216,7 +285,7 @@ e_table_sorted_variable_new (ETableModel *source, ETableHeader *full_header, ETa #endif etsv->sort_info_changed_id = gtk_signal_connect (GTK_OBJECT (sort_info), "sort_info_changed", GTK_SIGNAL_FUNC (etsv_sort_info_changed), etsv); - + return E_TABLE_MODEL(etsv); } @@ -285,6 +354,260 @@ qsort_callback(const void *data1, const void *data2) return comp_val; } +struct _subinfo { + int start; + GArray *rowsort; /* an array of row info's */ +}; + +struct _rowinfo { + int row; + struct _subinfo *subinfo; + struct _group_info *groupinfo; +}; + +static int +qsort_callback_complex(const void *data1, const void *data2) +{ + gint row1 = ((struct _rowinfo *)data1)->row; + gint row2 = ((struct _rowinfo *)data2)->row; + int j; + int sort_count = e_table_sort_info_sorting_get_count(etsv_closure->sort_info); + int comp_val = 0; + int ascending = 1; + for (j = 0; j < sort_count; j++) { + comp_val = (*(compare_closure[j]))(vals_closure[cols_closure * row1 + j], vals_closure[cols_closure * row2 + j]); + ascending = ascending_closure[j]; + 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; +} + +/* if sortgroup is like: +0 1 1 1 +1 1 2 2 +2 2 3 2 +3 2 4 3 +4 3 5 3 +5 2 6 1 +6 1 0 1 + + Want to sort the 1's first + Then sort each group of 2's, offsetting into the output by the new root 1 location + ... Recursively ... +*/ + +struct _group_info { + char *group; + int row; +}; + +#ifdef DEBUG +#undef DEBUG +#endif +/*#define DEBUG*/ + +#ifdef DEBUG +static int total=0; +static int total_sorted=0; +#endif + +/* builds the info needed to sort everything */ +static struct _subinfo * +etsv_sort_build_subset(ETableSortedVariable *etsv, struct _group_info *groupinfo, int start, int *end) +{ +/* ETableSubset *etss = E_TABLE_SUBSET(etsv);*/ + int rows = E_TABLE_SUBSET(etsv)->n_map; + int i, lastinsert; + GArray *rowsort = g_array_new(0, 0, sizeof(struct _rowinfo)); + struct _subinfo *subinfo, *newsub; + char *id, *newid; + int idlen, newidlen; + int cmp; + int cmplen; + + subinfo = g_malloc0(sizeof(*subinfo)); + subinfo->rowsort = rowsort; + subinfo->start = start; + lastinsert = -1; + id = groupinfo[start].group; + newid = strrchr(id, '/'); + idlen = strlen(id); + if (newid) + cmplen = newid-id; + else + cmplen = idlen; + d(printf("%d scanning level %s\n", start, id)); + for (i=start;i<rows;i++) { + newid = groupinfo[i].group; + newidlen = strlen(newid); + d(printf("%d checking group %s\n", start, newid)); + cmp = strncmp(id, newid, cmplen); + /* check for common parent */ + if (idlen == newidlen && cmp == 0) { + struct _rowinfo rowinfo; + + d(printf("%d Same parent\n", start)); + rowinfo.row = groupinfo[i].row; + rowinfo.subinfo = NULL; + rowinfo.groupinfo = &groupinfo[i]; + lastinsert = rowsort->len; + g_array_append_val(rowsort, rowinfo); +#ifdef DEBUG + total++; +#endif + } else if (newidlen > idlen) { + /* must be a new subtree */ + d(printf("%d checking subtree instead\n", start)); + newsub = etsv_sort_build_subset(etsv, groupinfo, i, &i); + d(printf("found %d nodes in subtree\n", newsub->rowsort->len)); + g_array_index(rowsort, struct _rowinfo, lastinsert).subinfo = newsub; + } else { + i--; + break; + } + } + if (end) + *end = i; + d(printf("finished level %s start was %d end was %d\n", id, start, i)); + return subinfo; +} + +/* sort each level, and then sort each level below that level (once we know + where the sublevel will fit in the overall list) */ +static int +etsv_sort_subset(ETableSortedVariable *etsv, struct _subinfo *subinfo, int startoffset) +{ + GArray *rowsort = subinfo->rowsort; + ETableSubset *etss = E_TABLE_SUBSET(etsv); + int offset, i; + + d(printf("sorting subset start %d rows %d\n", startoffset, rowsort->len)); + + /* first, sort the actual data */ + qsort(rowsort->data, rowsort->len, sizeof(struct _rowinfo), qsort_callback_complex); + + /* then put it back in the map table, where appropriate */ + offset = startoffset; + for (i=0;i<rowsort->len;i++) { + struct _rowinfo *rowinfo; + + d(printf("setting offset %d\n", offset)); + + rowinfo = &g_array_index(rowsort, struct _rowinfo, i); + etss->map_table[offset] = rowinfo->row; + if (rowinfo->subinfo) { + offset = etsv_sort_subset(etsv, rowinfo->subinfo, offset+1); + } else + offset += 1; + } + d(printf("end sort subset start %d\n", startoffset)); + + return offset; +} + +static void +etsv_sort_free_subset(ETableSortedVariable *etsv, struct _subinfo *subinfo) +{ + int i; + + for (i=0;i<subinfo->rowsort->len;i++) { + struct _rowinfo *rowinfo; + + rowinfo = &g_array_index(subinfo->rowsort, struct _rowinfo, i); + if (rowinfo->subinfo) + etsv_sort_free_subset(etsv, rowinfo->subinfo); + } + g_array_free(subinfo->rowsort, TRUE); + g_free(subinfo); +} + +static int +sort_groups_compare(const void *ap, const void *bp) +{ + struct _group_info *a = (struct _group_info *)ap; + struct _group_info *b = (struct _group_info *)bp; + + return strcmp(a->group, b->group); +} + +#ifdef DEBUG +static void +print_id(int key, int val, void *data) +{ + printf("gained id %d\n", key); +} +#endif + +/* use the sort group to select subsorts */ +static void +etsv_sort_by_group(ETableSortedVariable *etsv) +{ + ETableSubset *etss = E_TABLE_SUBSET(etsv); + int rows = E_TABLE_SUBSET(etsv)->n_map; + struct _group_info *groups; + struct _subinfo *subinfo; + int i; +#ifdef DEBUG + GHashTable *members = g_hash_table_new(0, 0); + + total = 0; + total_sorted = 0; +#endif + + d(printf("sorting %d rows\n", rows)); + + if (rows == 0) + return; + + /* get the subset rows */ + groups = g_malloc(sizeof(struct _group_info) * rows); + for (i=0;i<rows;i++) { + groups[i].row = etss->map_table[i]; + groups[i].group = g_strdup(e_table_model_row_sort_group(etss->source, groups[i].row)); +#ifdef DEBUG + g_hash_table_insert(members, etss->map_table[i], 1); + etss->map_table[i] = 0; +#endif + } + + /* sort the group info */ + qsort(groups, rows, sizeof(struct _group_info), sort_groups_compare); + + d(printf("sorted groups:\n"); + for (i=0;i<rows;i++) { + printf(" %s\n", groups[i].group); + }); + + /* now sort based on the group info */ + subinfo = etsv_sort_build_subset(etsv, groups, 0, NULL); + for (i=0;i<rows;i++) { + g_free(groups[i].group); + } + g_free(groups); + etsv_sort_subset(etsv, subinfo, 0); + etsv_sort_free_subset(etsv, subinfo); +#ifdef DEBUG + for (i=0;i<rows;i++) { + if (g_hash_table_lookup(members, etss->map_table[i]) == 0) { + printf("lost id %d\n", etss->map_table[i]); + } + g_hash_table_remove(members, etss->map_table[i]); + } + g_hash_table_foreach(members, print_id, 0); + + printf("total rows = %d, total processed = %d, total sorted = %d\n", rows, total, total_sorted); +#endif + +} static void etsv_sort(ETableSortedVariable *etsv) @@ -328,7 +651,12 @@ etsv_sort(ETableSortedVariable *etsv) compare_closure[j] = col->compare; ascending_closure[j] = column.ascending; } - qsort(E_TABLE_SUBSET(etsv)->map_table, rows, sizeof(int), qsort_callback); + + if (e_table_model_has_sort_group(etss->source)) { + etsv_sort_by_group(etsv); + } else { + qsort(E_TABLE_SUBSET(etsv)->map_table, rows, sizeof(int), qsort_callback); + } g_free(vals_closure); g_free(ascending_closure); g_free(compare_closure); diff --git a/widgets/table/e-table-sorted-variable.h b/widgets/table/e-table-sorted-variable.h index b533346bc7..0a2ad744af 100644 --- a/widgets/table/e-table-sorted-variable.h +++ b/widgets/table/e-table-sorted-variable.h @@ -26,6 +26,9 @@ typedef struct { int table_model_cell_changed_id; int sort_info_changed_id; int sort_idle_id; + int insert_idle_id; + int insert_count; + } ETableSortedVariable; typedef struct { diff --git a/widgets/table/e-tree-model.c b/widgets/table/e-tree-model.c index d5b69656d5..7687b5b185 100644 --- a/widgets/table/e-tree-model.c +++ b/widgets/table/e-tree-model.c @@ -72,6 +72,7 @@ etree_destroy (GtkObject *object) g_hash_table_foreach_remove (etree->expanded_state, expanded_remove_func, NULL); + g_string_free(etree->sort_group, TRUE); GTK_OBJECT_CLASS (e_tree_model_parent_class)->destroy (object); } @@ -347,6 +348,38 @@ etable_is_cell_editable (ETableModel *etm, int col, int row) return et_class->is_editable (etree, node, col); } +static void +build_sort_group(GString *out, ETreePath *node) +{ + if (node->parent) { + build_sort_group(out, node->parent); + } + g_string_sprintfa(out, "/%p", node); +} + +static const char * +etable_row_sort_group(ETableModel *etm, int row) +{ + ETreeModel *etree = E_TREE_MODEL(etm); + ETreeModelClass *et_class = ETM_CLASS(etm); + ETreePath* node = e_tree_model_node_at_row (etree, row); + + g_return_val_if_fail (node, ""); + + g_string_truncate(etree->sort_group, 0); + if (node) + build_sort_group(etree->sort_group, node); + + return etree->sort_group->str; +} + +static gboolean +etable_has_sort_group(ETableModel *etm) +{ + /* could optimise for the flat &/or unexpanded tree case */ + return TRUE; +} + static void e_tree_model_class_init (GtkObjectClass *klass) @@ -414,6 +447,9 @@ e_tree_model_class_init (GtkObjectClass *klass) table_class->thaw = etable_thaw; #endif + table_class->row_sort_group = etable_row_sort_group; + table_class->has_sort_group = etable_has_sort_group; + tree_class->get_root = etree_get_root; tree_class->get_prev = etree_get_prev; tree_class->get_next = etree_get_next; @@ -432,7 +468,15 @@ e_tree_model_class_init (GtkObjectClass *klass) tree_class->node_at_row = etree_node_at_row; } -E_MAKE_TYPE(e_tree_model, "ETreeModel", ETreeModel, e_tree_model_class_init, NULL, PARENT_TYPE) +static void +e_tree_init (GtkObject *object) +{ + ETreeModel *etree = (ETreeModel *)object; + + etree->sort_group = g_string_new(""); +} + +E_MAKE_TYPE(e_tree_model, "ETreeModel", ETreeModel, e_tree_model_class_init, e_tree_init, PARENT_TYPE) /* signals */ diff --git a/widgets/table/e-tree-model.h b/widgets/table/e-tree-model.h index ab142cc217..8a8e4c177d 100644 --- a/widgets/table/e-tree-model.h +++ b/widgets/table/e-tree-model.h @@ -24,6 +24,7 @@ struct ETreeModel { guint32 num_expanded_to_save; guint32 num_collapsed_to_save; GHashTable *expanded_state; /* used for loading/saving expanded state */ + GString *sort_group; /* for caching the last sort group info */ }; struct ETreeModelClass { |