From c5a9356ac1e26c8496345ade51485f65671eca74 Mon Sep 17 00:00:00 2001 From: dkf Date: Thu, 11 Apr 2024 13:19:29 +0000 Subject: Style cleanup, plus added comments on memory management --- generic/tclStrIdxTree.c | 230 +++++++++++++++++++++++++----------------------- generic/tclStrIdxTree.h | 31 +++++-- 2 files changed, 147 insertions(+), 114 deletions(-) diff --git a/generic/tclStrIdxTree.c b/generic/tclStrIdxTree.c index 2924829..af45c53 100644 --- a/generic/tclStrIdxTree.c +++ b/generic/tclStrIdxTree.c @@ -56,33 +56,45 @@ #include "tclInt.h" #include "tclStrIdxTree.h" +static void StrIdxTreeObj_DupIntRepProc(Tcl_Obj *srcPtr, Tcl_Obj *copyPtr); +static void StrIdxTreeObj_FreeIntRepProc(Tcl_Obj *objPtr); +static void StrIdxTreeObj_UpdateStringProc(Tcl_Obj *objPtr); + +Tcl_ObjType StrIdxTreeObjType = { + "str-idx-tree", /* name */ + StrIdxTreeObj_FreeIntRepProc, /* freeIntRepProc */ + StrIdxTreeObj_DupIntRepProc, /* dupIntRepProc */ + StrIdxTreeObj_UpdateStringProc, /* updateStringProc */ + NULL, /* setFromAnyProc */ + TCL_OBJTYPE_V0 +}; /* *---------------------------------------------------------------------- * * TclStrIdxTreeSearch -- * - * Find largest part of string "start" in indexed tree (case sensitive). + * Find largest part of string "start" in indexed tree (case sensitive). * - * Also used for building of string index tree. + * Also used for building of string index tree. * * Results: - * Return position of UTF character in start after last equal character - * and found item (with parent). + * Return position of UTF character in start after last equal character + * and found item (with parent). * * Side effects: - * None. + * None. * *---------------------------------------------------------------------- */ -const char* +const char * TclStrIdxTreeSearch( TclStrIdxTree **foundParent, /* Return value of found sub tree (used for tree build) */ - TclStrIdx **foundItem, /* Return value of found item */ - TclStrIdxTree *tree, /* Index tree will be browsed */ - const char *start, /* UTF string to find in tree */ - const char *end) /* End of string */ + TclStrIdx **foundItem, /* Return value of found item */ + TclStrIdxTree *tree, /* Index tree will be browsed */ + const char *start, /* UTF string to find in tree */ + const char *end) /* End of string */ { TclStrIdxTree *parent = tree, *prevParent = tree; TclStrIdx *item = tree->firstPtr, *prevItem = NULL; @@ -103,7 +115,7 @@ TclStrIdxTreeSearch( if (f >= end) { start = f; goto done; - }; + } /* set new offset and shift start string */ offs += cinf - cin; s = f; @@ -126,7 +138,6 @@ TclStrIdxTreeSearch( } item = item->nextPtr; - } while (item != NULL); /* fallback (few greedy match) not ambigous (has a value) */ @@ -136,12 +147,13 @@ TclStrIdxTreeSearch( start = prevf; } -done: - - if (foundParent) + done: + if (foundParent) { *foundParent = parent; - if (foundItem) + } + if (foundItem) { *foundItem = item; + } return start; } @@ -150,12 +162,13 @@ TclStrIdxTreeFree( TclStrIdx *tree) { while (tree != NULL) { - TclStrIdx *t; + TclStrIdx *t = tree; + Tcl_DecrRefCount(tree->key); if (tree->childTree.firstPtr != NULL) { TclStrIdxTreeFree(tree->childTree.firstPtr); } - t = tree, tree = tree->nextPtr; + tree = tree->nextPtr; ckfree(t); } } @@ -169,15 +182,17 @@ TclStrIdxTreeInsertBranch( TclStrIdx *item, TclStrIdx *child) { - if (parent->firstPtr == child) + if (parent->firstPtr == child) { parent->firstPtr = item; - if (parent->lastPtr == child) + } + if (parent->lastPtr == child) { parent->lastPtr = item; - if ( (item->nextPtr = child->nextPtr) ) { + } + if ((item->nextPtr = child->nextPtr) != NULL) { item->nextPtr->prevPtr = item; child->nextPtr = NULL; } - if ( (item->prevPtr = child->prevPtr) ) { + if ((item->prevPtr = child->prevPtr) != NULL) { item->prevPtr->nextPtr = item; child->prevPtr = NULL; } @@ -188,7 +203,7 @@ TclStrIdxTreeInsertBranch( static inline void TclStrIdxTreeAppend( TclStrIdxTree *parent, - TclStrIdx *item) + TclStrIdx *item) { if (parent->lastPtr != NULL) { parent->lastPtr->nextPtr = item; @@ -200,25 +215,24 @@ TclStrIdxTreeAppend( parent->firstPtr = item; } } - /* *---------------------------------------------------------------------- * * TclStrIdxTreeBuildFromList -- * - * Build or extend string indexed tree from tcl list. - * If the values not given the values of built list are indices starts with 1. - * Value of 0 is thereby reserved to the ambigous values. + * Build or extend string indexed tree from tcl list. If the values not + * given the values of built list are indices starts with 1. Value of 0 + * is thereby reserved to the ambigous values. * - * Important: by multiple lists, optimal tree can be created only if list with - * larger strings used firstly. + * Important: by multiple lists, optimal tree can be created only if list + * with larger strings used firstly. * * Results: - * Returns a standard Tcl result. + * Returns a standard Tcl result. * * Side effects: - * None. + * None. * *---------------------------------------------------------------------- */ @@ -227,19 +241,19 @@ int TclStrIdxTreeBuildFromList( TclStrIdxTree *idxTree, Tcl_Size lstc, - Tcl_Obj **lstv, + Tcl_Obj **lstv, void **values) { - Tcl_Obj **lwrv; + Tcl_Obj **lwrv; Tcl_Size i; int ret = TCL_ERROR; void *val; const char *s, *e, *f; - TclStrIdx *item; + TclStrIdx *item; /* create lowercase reflection of the list keys */ - lwrv = (Tcl_Obj **)ckalloc(sizeof(Tcl_Obj*) * lstc); + lwrv = (Tcl_Obj **) attemptckalloc(sizeof(Tcl_Obj*) * lstc); if (lwrv == NULL) { return TCL_ERROR; } @@ -255,18 +269,22 @@ TclStrIdxTreeBuildFromList( /* build index tree of the list keys */ for (i = 0; i < lstc; i++) { TclStrIdxTree *foundParent = idxTree; + e = s = TclGetString(lwrv[i]); e += lwrv[i]->length; val = values ? values[i] : INT2PTR(i+1); /* ignore empty keys (impossible to index it) */ - if (lwrv[i]->length == 0) continue; + if (lwrv[i]->length == 0) { + continue; + } item = NULL; if (idxTree->firstPtr != NULL) { - TclStrIdx *foundItem; + TclStrIdx *foundItem; + f = TclStrIdxTreeSearch(&foundParent, &foundItem, - idxTree, s, e); + idxTree, s, e); /* if common prefix was found */ if (f > s) { /* ignore element if fulfilled or ambigous */ @@ -275,11 +293,10 @@ TclStrIdxTreeBuildFromList( } /* if shortest key was found with the same value, * just replace its current key with longest key */ - if ( foundItem->value == val - && foundItem->length <= lwrv[i]->length - && foundItem->length <= (f - s) /* only if found item is covered in full */ - && foundItem->childTree.firstPtr == NULL - ) { + if (foundItem->value == val + && foundItem->length <= lwrv[i]->length + && foundItem->length <= (f - s) /* only if found item is covered in full */ + && foundItem->childTree.firstPtr == NULL) { TclSetObjRef(foundItem->key, lwrv[i]); foundItem->length = lwrv[i]->length; continue; @@ -288,7 +305,7 @@ TclStrIdxTreeBuildFromList( * but don't split by fulfilled child of found item ( ii->iii->iiii ) */ if (foundItem->length != (f - s)) { /* first split found item (insert one between parent and found + new one) */ - item = (TclStrIdx *)ckalloc(sizeof(TclStrIdx)); + item = (TclStrIdx *) attemptckalloc(sizeof(TclStrIdx)); if (item == NULL) { goto done; } @@ -306,7 +323,7 @@ TclStrIdxTreeBuildFromList( } } /* append item at end of found parent */ - item = (TclStrIdx *)ckalloc(sizeof(TclStrIdx)); + item = (TclStrIdx *) attemptckalloc(sizeof(TclStrIdx)); if (item == NULL) { goto done; } @@ -315,120 +332,118 @@ TclStrIdxTreeBuildFromList( item->length = lwrv[i]->length; item->value = val; TclStrIdxTreeAppend(foundParent, item); - }; + } ret = TCL_OK; - -done: - + done: if (lwrv != NULL) { for (i = 0; i < lstc; i++) { Tcl_DecrRefCount(lwrv[i]); } ckfree(lwrv); } - if (ret != TCL_OK) { if (idxTree->firstPtr != NULL) { TclStrIdxTreeFree(idxTree->firstPtr); } } - return ret; } +/* Follow links (smart pointers). */ +static inline Tcl_Obj * +FollowPossibleLink( + Tcl_Obj *objPtr) +{ + if (objPtr->internalRep.twoPtrValue.ptr1 != NULL + && objPtr->internalRep.twoPtrValue.ptr2 == NULL) { + objPtr = (Tcl_Obj *) objPtr->internalRep.twoPtrValue.ptr1; + } + return objPtr; +} -static void -StrIdxTreeObj_DupIntRepProc(Tcl_Obj *srcPtr, Tcl_Obj *copyPtr); -static void -StrIdxTreeObj_FreeIntRepProc(Tcl_Obj *objPtr); -static void -StrIdxTreeObj_UpdateStringProc(Tcl_Obj *objPtr); - -Tcl_ObjType StrIdxTreeObjType = { - "str-idx-tree", /* name */ - StrIdxTreeObj_FreeIntRepProc, /* freeIntRepProc */ - StrIdxTreeObj_DupIntRepProc, /* dupIntRepProc */ - StrIdxTreeObj_UpdateStringProc, /* updateStringProc */ - NULL, /* setFromAnyProc */ - TCL_OBJTYPE_V0 -}; - -Tcl_Obj* -TclStrIdxTreeNewObj() +Tcl_Obj * +TclStrIdxTreeNewObj(void) { Tcl_Obj *objPtr = Tcl_NewObj(); - objPtr->internalRep.twoPtrValue.ptr1 = NULL; - objPtr->internalRep.twoPtrValue.ptr2 = NULL; + TclStrIdxTree *tree = (TclStrIdxTree *) &objPtr->internalRep.twoPtrValue; + + /* + * This assert states that we can safely directly have a tree node as the + * internal representation of a Tcl_Obj instead of needing to hang it + * off the back with an extra alloc. + */ + TCL_CT_ASSERT(sizeof(TclStrIdxTree) <= sizeof(Tcl_ObjInternalRep)); + + tree->firstPtr = NULL; + tree->lastPtr = NULL; objPtr->typePtr = &StrIdxTreeObjType; /* return tree root in internal representation */ return objPtr; } static void -StrIdxTreeObj_DupIntRepProc(Tcl_Obj *srcPtr, Tcl_Obj *copyPtr) +StrIdxTreeObj_DupIntRepProc( + Tcl_Obj *srcPtr, + Tcl_Obj *copyPtr) { /* follow links (smart pointers) */ - if ( srcPtr->internalRep.twoPtrValue.ptr1 != NULL - && srcPtr->internalRep.twoPtrValue.ptr2 == NULL - ) { - srcPtr = (Tcl_Obj*)srcPtr->internalRep.twoPtrValue.ptr1; - } + srcPtr = FollowPossibleLink(srcPtr); /* create smart pointer to it (ptr1 != NULL, ptr2 = NULL) */ - TclInitObjRef(*((Tcl_Obj **)©Ptr->internalRep.twoPtrValue.ptr1), - srcPtr); + TclInitObjRef(*((Tcl_Obj **) ©Ptr->internalRep.twoPtrValue.ptr1), + srcPtr); copyPtr->internalRep.twoPtrValue.ptr2 = NULL; copyPtr->typePtr = &StrIdxTreeObjType; } static void -StrIdxTreeObj_FreeIntRepProc(Tcl_Obj *objPtr) +StrIdxTreeObj_FreeIntRepProc( + Tcl_Obj *objPtr) { /* follow links (smart pointers) */ - if ( objPtr->internalRep.twoPtrValue.ptr1 != NULL - && objPtr->internalRep.twoPtrValue.ptr2 == NULL - ) { + if (objPtr->internalRep.twoPtrValue.ptr1 != NULL + && objPtr->internalRep.twoPtrValue.ptr2 == NULL) { /* is a link */ - TclUnsetObjRef(*((Tcl_Obj **)&objPtr->internalRep.twoPtrValue.ptr1)); + TclUnsetObjRef(*((Tcl_Obj **) &objPtr->internalRep.twoPtrValue.ptr1)); } else { /* is a tree */ - TclStrIdxTree *tree = (TclStrIdxTree*)&objPtr->internalRep.twoPtrValue.ptr1; + TclStrIdxTree *tree = (TclStrIdxTree *) &objPtr->internalRep.twoPtrValue; + if (tree->firstPtr != NULL) { TclStrIdxTreeFree(tree->firstPtr); } - objPtr->internalRep.twoPtrValue.ptr1 = NULL; - objPtr->internalRep.twoPtrValue.ptr2 = NULL; + tree->firstPtr = NULL; + tree->lastPtr = NULL; } objPtr->typePtr = NULL; -}; +} static void -StrIdxTreeObj_UpdateStringProc(Tcl_Obj *objPtr) +StrIdxTreeObj_UpdateStringProc( + Tcl_Obj *objPtr) { /* currently only dummy empty string possible */ objPtr->length = 0; objPtr->bytes = &tclEmptyString; -}; +} TclStrIdxTree * -TclStrIdxTreeGetFromObj(Tcl_Obj *objPtr) { - /* follow links (smart pointers) */ +TclStrIdxTreeGetFromObj( + Tcl_Obj *objPtr) +{ if (objPtr->typePtr != &StrIdxTreeObjType) { return NULL; } - if ( objPtr->internalRep.twoPtrValue.ptr1 != NULL - && objPtr->internalRep.twoPtrValue.ptr2 == NULL - ) { - objPtr = (Tcl_Obj*)objPtr->internalRep.twoPtrValue.ptr1; - } + /* follow links (smart pointers) */ + objPtr = FollowPossibleLink(objPtr); /* return tree root in internal representation */ - return (TclStrIdxTree*)&objPtr->internalRep.twoPtrValue.ptr1; + return (TclStrIdxTree *) &objPtr->internalRep.twoPtrValue; } - + /* * Several debug primitives */ -#if 0 +#ifdef TEST_STR_IDX_TREE /* currently unused, debug resp. test purposes only */ static void @@ -439,6 +454,7 @@ TclStrIdxTreePrint( { Tcl_Obj *obj[2]; const char *s; + TclInitObjRef(obj[0], Tcl_NewStringObj("::puts", -1)); while (tree != NULL) { s = TclGetString(tree->key) + offs; @@ -454,14 +470,12 @@ TclStrIdxTreePrint( TclUnsetObjRef(obj[0]); } - int TclStrIdxTreeTestObjCmd( ClientData clientData, Tcl_Interp *interp, int objc, Tcl_Obj *const objv[]) { const char *cs, *cin, *ret; - static const char *const options[] = { "index", "puts-index", "findequal", NULL @@ -476,7 +490,7 @@ TclStrIdxTreeTestObjCmd( return TCL_ERROR; } if (Tcl_GetIndexFromObj(interp, objv[1], options, - "option", 0, &optionIndex) != TCL_OK) { + "option", 0, &optionIndex) != TCL_OK) { Tcl_SetErrorCode(interp, "CLOCK", "badOption", TclGetString(objv[1]), (char *)NULL); return TCL_ERROR; @@ -490,33 +504,33 @@ TclStrIdxTreeTestObjCmd( cs = TclGetString(objv[2]); cin = TclGetString(objv[3]); ret = TclUtfFindEqual( - cs, cs + objv[1]->length, cin, cin + objv[2]->length); + cs, cs + objv[1]->length, cin, cin + objv[2]->length); Tcl_SetObjResult(interp, Tcl_NewIntObj(ret - cs)); - break; + break; case O_INDEX: case O_PUTS_INDEX: { Tcl_Obj **lstv; int i, lstc; TclStrIdxTree idxTree = {NULL, NULL}; + i = 1; while (++i < objc) { if (TclListObjGetElements(interp, objv[i], &lstc, &lstv) != TCL_OK) { return TCL_ERROR; - }; + } TclStrIdxTreeBuildFromList(&idxTree, lstc, lstv, NULL); } if (optionIndex == O_PUTS_INDEX) { TclStrIdxTreePrint(interp, idxTree.firstPtr, 0); } TclStrIdxTreeFree(idxTree.firstPtr); + break; } - break; } return TCL_OK; } - #endif /* diff --git a/generic/tclStrIdxTree.h b/generic/tclStrIdxTree.h index 28e0710..c5a6716 100644 --- a/generic/tclStrIdxTree.h +++ b/generic/tclStrIdxTree.h @@ -13,17 +13,36 @@ #ifndef _TCLSTRIDXTREE_H #define _TCLSTRIDXTREE_H +#include "tclInt.h" + /* * Main structures declarations of index tree and entry */ typedef struct TclStrIdx TclStrIdx; +/* + * Top level structure of the tree, or first two fields of the interior + * structure. + * + * Note that this is EXACTLY two pointers so it is the same size as the + * twoPtrValue of a Tcl_ObjInternalRep. This is how the top level structure + * of the tree is always allocated. (This type constraint is asserted in + * TclStrIdxTreeNewObj() so it's guaranteed.) + * + * Also note that if firstPtr is not NULL, lastPtr must also be not NULL. + * The case where firstPtr is not NULL and lastPtr is NULL is special (a + * smart pointer to one of these) and is not actually a valid instance of + * this structure. + */ typedef struct TclStrIdxTree { TclStrIdx *firstPtr; TclStrIdx *lastPtr; } TclStrIdxTree; +/* + * An interior node of the tree. Always directly allocated. + */ struct TclStrIdx { TclStrIdxTree childTree; TclStrIdx *nextPtr; @@ -38,13 +57,13 @@ struct TclStrIdx { * * TclUtfFindEqual, TclUtfFindEqualNC -- * - * Find largest part of string cs in string cin (case sensitive and not). + * Find largest part of string cs in string cin (case sensitive and not). * * Results: - * Return position of UTF character in cs after last equal character. + * Return position of UTF character in cs after last equal character. * * Side effects: - * None. + * None. * *---------------------------------------------------------------------- */ @@ -133,14 +152,14 @@ TclUtfFindEqualNCInLwr( } while (0) #define TclInitObjRef(obj, val) \ do { \ - obj = val; \ + obj = (val); \ if (obj) { \ Tcl_IncrRefCount(obj); \ } \ } while (0) #define TclSetObjRef(obj, val) \ do { \ - Tcl_Obj *nval = val; \ + Tcl_Obj *nval = (val); \ if (obj != nval) { \ Tcl_Obj *prev = obj; \ TclInitObjRef(obj, nval); \ @@ -162,7 +181,7 @@ MODULE_SCOPE int TclStrIdxTreeBuildFromList(TclStrIdxTree *idxTree, MODULE_SCOPE Tcl_Obj * TclStrIdxTreeNewObj(); MODULE_SCOPE TclStrIdxTree*TclStrIdxTreeGetFromObj(Tcl_Obj *objPtr); -#if 0 +#ifdef TEST_STR_IDX_TREE /* currently unused, debug resp. test purposes only */ MODULE_SCOPE Tcl_ObjCmdProc TclStrIdxTreeTestObjCmd; #endif -- cgit v0.12