From bf51b17a1f4fc7f073738dae704e9b675c258699 Mon Sep 17 00:00:00 2001 From: treectrl Date: Tue, 11 Jul 2006 00:07:20 +0000 Subject: Did some work on better distributing space when a style spans multiple columns. Not used yet. Renamed SortData.count to columnCount for readability. Reformatted some function headers. CompareProc: identity test to save work. find_pivot: bug fix. ItemSortCmd: fix memory leak with -command option. --- generic/tkTreeItem.c | 282 ++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 232 insertions(+), 50 deletions(-) diff --git a/generic/tkTreeItem.c b/generic/tkTreeItem.c index 58b7a15..32faaeb 100644 --- a/generic/tkTreeItem.c +++ b/generic/tkTreeItem.c @@ -5,7 +5,7 @@ * * Copyright (c) 2002-2005 Tim Baker * - * RCS: @(#) $Id: tkTreeItem.c,v 1.54 2005/09/28 21:55:31 treectrl Exp $ + * RCS: @(#) $Id: tkTreeItem.c,v 1.55 2006/07/11 00:07:20 treectrl Exp $ */ #include "tkTreeCtrl.h" @@ -178,6 +178,121 @@ TreeItemColumn_NeededWidth( return 0; } +#ifdef EXPENSIVE_SPAN_WIDTH /* NOT USED */ + +/* + * When a style spans 2 or more columns, all of the requested width goes + * to the first column in the span. Ideally the width needed by the style + * would be distributed over each column in the span. To be done properly, + * the visibility and fixed-width of each column needs to be considered. + * + * This routine does an okay job of calculating the requested width of a + * column in an item when spans are involved; however there is a lot of + * processing involved, and this routine is called for each column in + * a span separately (it would be better to calculate the width of all + * the columns in a span at the same time). + */ + +int +TreeItem_NeededWidthOfColumn( + TreeCtrl *tree, /* Widget info. */ + TreeItem item_, /* Item token. */ + int _columnIndex /* Column index. */ + ) +{ + Item *item = (Item *) item_; + TreeColumn treeColumn = tree->columns; + Column *column = item->columns; + int columnIndex = 0, itemColumnIndex = 0, span = 1; + int selfIndex = _columnIndex, fixedWidth = 0, width = 0; + int spanStart, spanEnd; + struct span { + Column *itemColumn; + int itemColumnIndex; + int fixedWidth; + int spanWidth; + int visible; + } staticSpans[STATIC_SIZE], *spans = staticSpans; + + STATIC_ALLOC(spans, struct span, tree->columnCount); + + while (treeColumn != NULL) { + spans[columnIndex].visible = TreeColumn_Visible(treeColumn); + if (--span == 0) { + if (spans[columnIndex].visible) + span = column ? column->span : 1; + else + span = 1; + itemColumnIndex = columnIndex; + } + spans[columnIndex].itemColumn = column; + spans[columnIndex].itemColumnIndex = itemColumnIndex; + spans[columnIndex].spanWidth = 0; + spans[columnIndex].fixedWidth = TreeColumn_FixedWidth(treeColumn); + ++columnIndex; + treeColumn = TreeColumn_Next(treeColumn); + if (column != NULL) + column = column->next; + } + + span = 0; + columnIndex = spanStart = spanEnd = spans[selfIndex].itemColumnIndex; + while (spans[columnIndex].itemColumnIndex == spanStart) { + if (spans[columnIndex].visible) { + if (spans[columnIndex].fixedWidth >= 0) { + fixedWidth += spans[columnIndex].fixedWidth; + spans[columnIndex].spanWidth = spans[columnIndex].fixedWidth; + } else + ++span; /* number of visible columns in the span with no + * fixed width */ + } + spanEnd = columnIndex; + ++columnIndex; + if (columnIndex == tree->columnCount) + break; + } + + column = spans[spanStart].itemColumn; + if (column != NULL && column->style != NULL) { + width = TreeStyle_NeededWidth(tree, column->style, + item->state | column->cstate); + if (width > fixedWidth && span > 0) { + width -= fixedWidth; + while (width > 0) { + int each = (width > span) ? width / span : 1; + columnIndex = spanStart; + while (columnIndex <= spanEnd) { + if (spans[columnIndex].visible) { + if (spans[columnIndex].fixedWidth < 0) { + spans[columnIndex].spanWidth += each; + width -= each; + if (width <= 0) + break; + } + } + ++columnIndex; + } + } + }; + } + +if (0) +{ + int i; + for (i = 0; i < tree->columnCount; i++) { + dbwin("%d,%d: itemColumn %p itemColumnIndex %d fixedWidth %d spanWidth %d\n", + item->id, i, spans[i].itemColumn, spans[i].itemColumnIndex, spans[i].fixedWidth, + spans[i].spanWidth); + } +} + width = spans[selfIndex].spanWidth; + STATIC_FREE(spans, struct span, tree->columnCount); + + return width; +} + +#endif /* COLUMN_SPAN */ + /* *---------------------------------------------------------------------- * @@ -4311,12 +4426,16 @@ struct SortData struct SortItem1 *item1s; /* SortItem.item1 points in here */ #define MAX_SORT_COLUMNS 40 struct SortColumn columns[MAX_SORT_COLUMNS]; - int count; /* max number of columns to compare */ + int columnCount; /* max number of columns to compare */ int result; }; /* from Tcl 8.4.0 */ -static int DictionaryCompare(char *left, char *right) +static int +DictionaryCompare( + char *left, + char *right + ) { Tcl_UniChar uniLeft, uniRight, uniLeftLower, uniRightLower; int diff, zeros; @@ -4422,7 +4541,12 @@ static int DictionaryCompare(char *left, char *right) } static int -CompareAscii(SortData *sortData, struct SortItem *a, struct SortItem *b, int n) +CompareAscii( + SortData *sortData, + struct SortItem *a, + struct SortItem *b, + int n /* Column index. */ + ) { char *left = a->item1[n].string; char *right = b->item1[n].string; @@ -4438,7 +4562,12 @@ CompareAscii(SortData *sortData, struct SortItem *a, struct SortItem *b, int n) } static int -CompareDict(SortData *sortData, struct SortItem *a, struct SortItem *b, int n) +CompareDict( + SortData *sortData, + struct SortItem *a, + struct SortItem *b, + int n /* Column index. */ + ) { char *left = a->item1[n].string; char *right = b->item1[n].string; @@ -4454,21 +4583,36 @@ CompareDict(SortData *sortData, struct SortItem *a, struct SortItem *b, int n) } static int -CompareDouble(SortData *sortData, struct SortItem *a, struct SortItem *b, int n) +CompareDouble( + SortData *sortData, + struct SortItem *a, + struct SortItem *b, + int n /* Column index. */ + ) { return (a->item1[n].doubleValue < b->item1[n].doubleValue) ? -1 : ((a->item1[n].doubleValue == b->item1[n].doubleValue) ? 0 : 1); } static int -CompareLong(SortData *sortData, struct SortItem *a, struct SortItem *b, int n) +CompareLong( + SortData *sortData, + struct SortItem *a, + struct SortItem *b, + int n /* Column index. */ + ) { return (a->item1[n].longValue < b->item1[n].longValue) ? -1 : ((a->item1[n].longValue == b->item1[n].longValue) ? 0 : 1); } static int -CompareCmd(SortData *sortData, struct SortItem *a, struct SortItem *b, int n) +CompareCmd( + SortData *sortData, + struct SortItem *a, + struct SortItem *b, + int n /* Column index. */ + ) { Tcl_Interp *interp = sortData->tree->interp; Tcl_Obj **objv, *paramObjv[2]; @@ -4501,11 +4645,19 @@ CompareCmd(SortData *sortData, struct SortItem *a, struct SortItem *b, int n) return v; } -static int CompareProc(SortData *sortData, struct SortItem *a, struct SortItem *b) +static int +CompareProc( + SortData *sortData, + struct SortItem *a, + struct SortItem *b + ) { int i, v; - for (i = 0; i < sortData->count; i++) { + if (a->item == b->item) + return 0; + + for (i = 0; i < sortData->columnCount; i++) { v = (*sortData->columns[i].proc)(sortData, a, b, i); /* -command returned error */ @@ -4523,30 +4675,38 @@ static int CompareProc(SortData *sortData, struct SortItem *a, struct SortItem * /* BEGIN custom quicksort() */ -static int find_pivot(SortData *sortData, struct SortItem *left, struct SortItem *right, struct SortItem *pivot) +static int +find_pivot( + SortData *sortData, + struct SortItem *left, + struct SortItem *right, + struct SortItem *pivot + ) { - struct SortItem *a, *b, *c, *p; + struct SortItem *a, *b, *c, *p, *tmp; int v; a = left; b = (left + (right - left) / 2); c = right; + /* Arrange a <= b <= c. */ v = CompareProc(sortData, a, b); if (sortData->result != TCL_OK) return 0; - if (v < 0) { p = a; a = b; b = p; } + if (v > 0) { tmp = a; a = b; b = tmp; } v = CompareProc(sortData, a, c); if (sortData->result != TCL_OK) return 0; - if (v < 0) { p = a; a = c; c = p; } + if (v > 0) { tmp = a; a = c; c = tmp; } v = CompareProc(sortData, b, c); if (sortData->result != TCL_OK) return 0; - if (v < 0) { p = b; b = c; c = p; } + if (v > 0) { tmp = b; b = c; c = tmp; } + /* if (a < b) pivot = b */ v = CompareProc(sortData, a, b); if (sortData->result != TCL_OK) return 0; @@ -4555,6 +4715,7 @@ static int find_pivot(SortData *sortData, struct SortItem *left, struct SortItem return 1; } + /* if (b < c) pivot = c */ v = CompareProc(sortData, b, c); if (sortData->result != TCL_OK) return 0; @@ -4581,7 +4742,13 @@ static int find_pivot(SortData *sortData, struct SortItem *left, struct SortItem * quicksort, but are present to detect the aforementioned bugs. */ #define BUGGY_COMMAND -static struct SortItem *partition(SortData *sortData, struct SortItem *left, struct SortItem *right, struct SortItem *pivot) +static struct SortItem * +partition( + SortData *sortData, + struct SortItem *left, + struct SortItem *right, + struct SortItem *pivot + ) { int v; #ifdef BUGGY_COMMAND @@ -4591,7 +4758,7 @@ static struct SortItem *partition(SortData *sortData, struct SortItem *left, str while (left <= right) { /* while (*left < *pivot) - ++left; + ++left; */ while (1) { v = CompareProc(sortData, left, pivot); @@ -4608,7 +4775,7 @@ static struct SortItem *partition(SortData *sortData, struct SortItem *left, str } /* while (*right >= *pivot) - --right; + --right; */ while (1) { v = CompareProc(sortData, right, pivot); @@ -4640,22 +4807,27 @@ static struct SortItem *partition(SortData *sortData, struct SortItem *left, str #endif } -static void quicksort(SortData *sortData, struct SortItem *left, struct SortItem *right) +static void +quicksort( + SortData *sortData, + struct SortItem *left, + struct SortItem *right + ) { struct SortItem *p, pivot; if (sortData->result != TCL_OK) return; + if (left == right) + return; + + /* FIXME: switch to insertion sort or similar when the number of + * elements is small. */ + if (find_pivot(sortData, left, right, &pivot) == 1) { p = partition(sortData, left, right, &pivot); - if (sortData->result != TCL_OK) - return; - quicksort(sortData, left, p - 1); - if (sortData->result != TCL_OK) - return; - quicksort(sortData, p, right); } } @@ -4713,7 +4885,7 @@ ItemSortCmd( /* Defaults: sort ascii strings in column 0 only */ sortData.tree = tree; - sortData.count = 1; + sortData.columnCount = 1; sortData.columns[0].column = 0; sortData.columns[0].sortBy = SORT_ASCII; sortData.columns[0].order = 1; @@ -4742,7 +4914,7 @@ ItemSortCmd( } switch (index) { case OPT_ASCII: - sortData.columns[sortData.count - 1].sortBy = SORT_ASCII; + sortData.columns[sortData.columnCount - 1].sortBy = SORT_ASCII; break; case OPT_COLUMN: if (TreeColumn_FromObj(tree, objv[i + 1], &treeColumn, @@ -4750,31 +4922,31 @@ ItemSortCmd( return TCL_ERROR; /* The first -column we see is the first column we compare */ if (sawColumn) { - if (sortData.count + 1 > MAX_SORT_COLUMNS) { + if (sortData.columnCount + 1 > MAX_SORT_COLUMNS) { FormatResult(interp, "can't compare more than %d columns", MAX_SORT_COLUMNS); return TCL_ERROR; } - sortData.count++; + sortData.columnCount++; /* Defaults for this column */ - sortData.columns[sortData.count - 1].sortBy = SORT_ASCII; - sortData.columns[sortData.count - 1].order = 1; - sortData.columns[sortData.count - 1].elemCount = 0; + sortData.columns[sortData.columnCount - 1].sortBy = SORT_ASCII; + sortData.columns[sortData.columnCount - 1].order = 1; + sortData.columns[sortData.columnCount - 1].elemCount = 0; } - sortData.columns[sortData.count - 1].column = TreeColumn_Index(treeColumn); + sortData.columns[sortData.columnCount - 1].column = TreeColumn_Index(treeColumn); sawColumn = TRUE; break; case OPT_COMMAND: - sortData.columns[sortData.count - 1].command = objv[i + 1]; - sortData.columns[sortData.count - 1].sortBy = SORT_COMMAND; + sortData.columns[sortData.columnCount - 1].command = objv[i + 1]; + sortData.columns[sortData.columnCount - 1].sortBy = SORT_COMMAND; sawCmd = TRUE; break; case OPT_DECREASING: - sortData.columns[sortData.count - 1].order = 0; + sortData.columns[sortData.columnCount - 1].order = 0; break; case OPT_DICT: - sortData.columns[sortData.count - 1].sortBy = SORT_DICT; + sortData.columns[sortData.columnCount - 1].sortBy = SORT_DICT; break; case OPT_ELEMENT: { @@ -4784,8 +4956,8 @@ ItemSortCmd( if (Tcl_ListObjGetElements(interp, objv[i + 1], &listObjc, &listObjv) != TCL_OK) return TCL_ERROR; - elemPtr = sortData.columns[sortData.count - 1].elems; - sortData.columns[sortData.count - 1].elemCount = 0; + elemPtr = sortData.columns[sortData.columnCount - 1].elems; + sortData.columns[sortData.columnCount - 1].elemCount = 0; if (listObjc == 0) { } else if (listObjc == 1) { if (TreeElement_FromObj(tree, listObjv[0], &elemPtr->elem) @@ -4804,7 +4976,7 @@ ItemSortCmd( } elemPtr->style = NULL; elemPtr->elemIndex = -1; - sortData.columns[sortData.count - 1].elemCount++; + sortData.columns[sortData.columnCount - 1].elemCount++; } else { if (listObjc & 1) { FormatResult(interp, @@ -4832,7 +5004,7 @@ ItemSortCmd( "\n (processing -element option)"); return TCL_ERROR; } - sortData.columns[sortData.count - 1].elemCount++; + sortData.columns[sortData.columnCount - 1].elemCount++; elemPtr++; } } @@ -4850,10 +5022,10 @@ ItemSortCmd( } break; case OPT_INCREASING: - sortData.columns[sortData.count - 1].order = 1; + sortData.columns[sortData.columnCount - 1].order = 1; break; case OPT_INTEGER: - sortData.columns[sortData.count - 1].sortBy = SORT_LONG; + sortData.columns[sortData.columnCount - 1].sortBy = SORT_LONG; break; case OPT_LAST: if (TreeItem_FromObj(tree, objv[i + 1], &_item, 0) != TCL_OK) @@ -4870,7 +5042,7 @@ ItemSortCmd( notReally = TRUE; break; case OPT_REAL: - sortData.columns[sortData.count - 1].sortBy = SORT_DOUBLE; + sortData.columns[sortData.columnCount - 1].sortBy = SORT_DOUBLE; break; } i += numArgs[index]; @@ -4883,15 +5055,21 @@ ItemSortCmd( return TCL_ERROR; } + /* If there is only one item to sort, then return early. */ if (first == last) { if (notReally) Tcl_SetObjResult(interp, TreeItem_ToObj(tree, (TreeItem) first)); return TCL_OK; } - for (i = 0; i < sortData.count; i++) { + for (i = 0; i < sortData.columnCount; i++) { + + /* Initialize the sort procedure for this column. */ sortData.columns[i].proc = sortProc[sortData.columns[i].sortBy]; + /* Append two dummy args to the -command argument. These two dummy + * args are replaced by the 2 item ids being compared. See + * CompareCmd(). */ if (sortData.columns[i].sortBy == SORT_COMMAND) { Tcl_Obj *obj = Tcl_DuplicateObj(sortData.columns[i].command); Tcl_Obj *obj2 = Tcl_NewObj(); @@ -4900,7 +5078,11 @@ ItemSortCmd( Tcl_DecrRefCount(obj); Tcl_IncrRefCount(obj2); Tcl_DecrRefCount(obj2); - /* FIXME: free other .command[] */ + + for (j = 0; j < i; j++) + if (sortData.columns[j].sortBy == SORT_COMMAND) + Tcl_DecrRefCount(sortData.columns[j].command); + return TCL_ERROR; } (void) Tcl_ListObjAppendElement(interp, obj, obj2); @@ -4929,10 +5111,10 @@ ItemSortCmd( } count = indexL - indexF + 1; - sortData.item1s = (struct SortItem1 *) ckalloc(sizeof(struct SortItem1) * count * sortData.count); + sortData.item1s = (struct SortItem1 *) ckalloc(sizeof(struct SortItem1) * count * sortData.columnCount); sortData.items = (struct SortItem *) ckalloc(sizeof(struct SortItem) * count); for (i = 0; i < count; i++) { - sortData.items[i].item1 = sortData.item1s + i * sortData.count; + sortData.items[i].item1 = sortData.item1s + i * sortData.columnCount; sortData.items[i].obj = NULL; } @@ -4947,7 +5129,7 @@ ItemSortCmd( Tcl_IncrRefCount(obj); sortData.items[index].obj = obj; } - for (i = 0; i < sortData.count; i++) { + for (i = 0; i < sortData.columnCount; i++) { struct SortItem1 *sortItem1 = sortItem->item1 + i; if (sortData.columns[i].sortBy == SORT_COMMAND) @@ -5098,7 +5280,7 @@ ItemSortCmd( for (i = 0; i < count; i++) if (sortData.items[i].obj != NULL) Tcl_DecrRefCount(sortData.items[i].obj); - for (i = 0; i < sortData.count; i++) + for (i = 0; i < sortData.columnCount; i++) if (sortData.columns[i].sortBy == SORT_COMMAND) Tcl_DecrRefCount(sortData.columns[i].command); ckfree((char *) sortData.item1s); -- cgit v0.12