diff options
| -rw-r--r-- | generic/tclCmdIL.c | 44 | ||||
| -rw-r--r-- | generic/tclInt.h | 232 | ||||
| -rw-r--r-- | generic/tclInterp.c | 17 | ||||
| -rw-r--r-- | generic/tclListObj.c | 3537 | ||||
| -rw-r--r-- | tests-perf/comparePerf.tcl | 371 | ||||
| -rw-r--r-- | tests-perf/listPerf.tcl | 1290 | ||||
| -rw-r--r-- | tests/lrepeat.test | 2 |
7 files changed, 4254 insertions, 1239 deletions
diff --git a/generic/tclCmdIL.c b/generic/tclCmdIL.c index f59d832..f0969fe 100644 --- a/generic/tclCmdIL.c +++ b/generic/tclCmdIL.c @@ -2888,7 +2888,7 @@ Tcl_LrepeatObjCmd( if (elementCount && objc > LIST_MAX/elementCount) { Tcl_SetObjResult(interp, Tcl_ObjPrintf( - "max length of a Tcl list (%d elements) exceeded", LIST_MAX)); + "max length of a Tcl list (%" TCL_Z_MODIFIER "u elements) exceeded", LIST_MAX)); Tcl_SetErrorCode(interp, "TCL", "MEMORY", NULL); return TCL_ERROR; } @@ -2901,10 +2901,15 @@ Tcl_LrepeatObjCmd( listPtr = Tcl_NewListObj(totalElems, NULL); if (totalElems) { - List *listRepPtr = ListRepPtr(listPtr); - - listRepPtr->elemCount = elementCount*objc; - dataArray = listRepPtr->elements; + ListRep listRep; + ListObjGetRep(listPtr, &listRep); + dataArray = ListRepElementsBase(&listRep); + listRep.storePtr->numUsed = totalElems; + if (listRep.spanPtr) { + /* Future proofing in case Tcl_NewListObj returns a span */ + listRep.spanPtr->spanStart = listRep.storePtr->firstUsed; + listRep.spanPtr->spanLength = listRep.storePtr->numUsed; + } } /* @@ -3084,14 +3089,21 @@ Tcl_LreverseObjCmd( } if (Tcl_IsShared(objv[1]) - || (ListRepPtr(objv[1])->refCount > 1)) { /* Bug 1675044 */ + || ListObjRepIsShared(objv[1])) { /* Bug 1675044 */ Tcl_Obj *resultObj, **dataArray; - List *listRepPtr; + ListRep listRep; resultObj = Tcl_NewListObj(elemc, NULL); - listRepPtr = ListRepPtr(resultObj); - listRepPtr->elemCount = elemc; - dataArray = listRepPtr->elements; + + /* Modify the internal rep in-place */ + ListObjGetRep(resultObj, &listRep); + listRep.storePtr->numUsed = elemc; + dataArray = ListRepElementsBase(&listRep); + if (listRep.spanPtr) { + /* Future proofing */ + listRep.spanPtr->spanStart = listRep.storePtr->firstUsed; + listRep.spanPtr->spanLength = listRep.storePtr->numUsed; + } for (i=0,j=elemc-1 ; i<elemc ; i++,j--) { dataArray[j] = elemv[i]; @@ -4419,12 +4431,12 @@ Tcl_LsortObjCmd( */ if (sortInfo.resultCode == TCL_OK) { - List *listRepPtr; + ListRep listRep; Tcl_Obj **newArray, *objPtr; resultPtr = Tcl_NewListObj(sortInfo.numElements * groupSize, NULL); - listRepPtr = ListRepPtr(resultPtr); - newArray = listRepPtr->elements; + ListObjGetRep(resultPtr, &listRep); + newArray = ListRepElementsBase(&listRep); if (group) { for (i=0; elementPtr!=NULL ; elementPtr=elementPtr->nextPtr) { idx = elementPtr->payload.index; @@ -4453,7 +4465,11 @@ Tcl_LsortObjCmd( Tcl_IncrRefCount(objPtr); } } - listRepPtr->elemCount = i; + listRep.storePtr->numUsed = i; + if (listRep.spanPtr) { + listRep.spanPtr->spanStart = listRep.storePtr->firstUsed; + listRep.spanPtr->spanLength = listRep.storePtr->numUsed; + } Tcl_SetObjResult(interp, resultPtr); } diff --git a/generic/tclInt.h b/generic/tclInt.h index b6d5b9a..5a59e39 100644 --- a/generic/tclInt.h +++ b/generic/tclInt.h @@ -2381,59 +2381,208 @@ typedef enum TclEolTranslation { #define TCL_INVOKE_NO_TRACEBACK (1<<2) /* - * The structure used as the internal representation of Tcl list objects. This - * struct is grown (reallocated and copied) as necessary to hold all the - * list's element pointers. The struct might contain more slots than currently - * used to hold all element pointers. This is done to make append operations - * faster. + * TclListSizeT is the type for holding list element counts. It's defined + * simplify sharing source between Tcl8 and Tcl9. */ +#if TCL_MAJOR_VERSION > 8 -typedef struct List { - size_t refCount; - size_t maxElemCount; /* Total number of element array slots. */ - size_t elemCount; /* Current number of list elements. */ - int canonicalFlag; /* Set if the string representation was - * derived from the list representation. May - * be ignored if there is no string rep at - * all.*/ - Tcl_Obj *elements[TCLFLEXARRAY]; /* First list element; the struct is grown to - * accommodate all elements. */ -} List; +typedef ptrdiff_t ListSizeT; /* TODO - may need to fix to match Tcl9's API */ + +/* + * SSIZE_MAX, NOT SIZE_MAX as negative differences need to be expressed + * between values of the ListSizeT type so limit the range to signed + */ +#define ListSizeT_MAX PTRDIFF_MAX -#define LIST_MAX \ - ((int)(((size_t)UINT_MAX - offsetof(List, elements))/sizeof(Tcl_Obj *))) -#define LIST_SIZE(numElems) \ - (TCL_HASH_TYPE)(offsetof(List, elements) + ((numElems) * sizeof(Tcl_Obj *))) +#else + +typedef int ListSizeT; +#define ListSizeT_MAX INT_MAX + +#endif /* - * Macro used to get the elements of a list object. + * ListStore -- + * + * A Tcl list's internal representation is defined through three structures. + * + * A ListStore struct is a structure that includes a variable size array that + * serves as storage for a Tcl list. A contiguous sequence of slots in the + * array, the "in-use" area, holds valid pointers to Tcl_Obj values that + * belong to one or more Tcl lists. The unused slots before and after these + * are free slots that may be used to prepend and append without having to + * reallocate the struct. The ListStore may be shared amongst multiple lists + * and reference counted. + * + * A ListSpan struct defines a sequence of slots within a ListStore. This sequence + * always lies within the "in-use" area of the ListStore. Like ListStore, the + * structure may be shared among multiple lists and is reference counted. + * + * A ListRep struct holds the internal representation of a Tcl list as stored + * in a Tcl_Obj. It is composed of a ListStore and a ListSpan that together + * define the content of the list. The ListSpan specifies the range of slots + * within the ListStore that hold elements for this list. The ListSpan is + * optional in which case the list includes all the "in-use" slots of the + * ListStore. + * */ +typedef struct ListStore { + ListSizeT firstUsed; /* Index of first slot in use within slots[] */ + ListSizeT numUsed; /* Number of slots in use (starting firstUsed) */ + ListSizeT numAllocated; /* Total number of slots[] array slots. */ + int refCount; /* Number of references to this instance */ + int flags; /* LISTSTORE_* flags */ + Tcl_Obj *slots[TCLFLEXARRAY]; /* Variable size array. Grown as needed */ +} ListStore; -#define ListRepPtr(listPtr) \ - ((List *) (listPtr)->internalRep.twoPtrValue.ptr1) +#define LISTSTORE_CANONICAL 0x1 /* All Tcl_Obj's referencing this + store have their string representation + derived from the list representation */ -#define ListObjGetElements(listPtr, objc, objv) \ - ((objv) = ListRepPtr(listPtr)->elements, \ - (objc) = ListRepPtr(listPtr)->elemCount) +/* Max number of elements that can be contained in a list */ +#define LIST_MAX \ + ((ListSizeT)(((size_t)ListSizeT_MAX - offsetof(ListStore, slots)) \ + / sizeof(Tcl_Obj *))) +/* Memory size needed for a ListStore to hold numSlots_ elements */ +#define LIST_SIZE(numSlots_) \ + ((int)(offsetof(ListStore, slots) + ((numSlots_) * sizeof(Tcl_Obj *)))) -#define ListObjLength(listPtr, len) \ - ((len) = ListRepPtr(listPtr)->elemCount) +/* + * ListSpan -- + * See comments above for ListStore + */ +typedef struct ListSpan { + ListSizeT spanStart; /* Starting index of the span */ + ListSizeT spanLength; /* Number of elements in the span */ + int refCount; /* Count of references to this span record */ +} ListSpan; -#define ListObjIsCanonical(listPtr) \ - (((listPtr)->bytes == NULL) || ListRepPtr(listPtr)->canonicalFlag) +/* + * ListRep -- + * See comments above for ListStore + */ +typedef struct ListRep { + ListStore *storePtr;/* element array shared amongst different lists */ + ListSpan *spanPtr; /* If not NULL, the span holds the range of slots + within *storePtr that contain this list elements. */ +} ListRep; -#define TclListObjGetElementsM(interp, listPtr, objcPtr, objvPtr) \ - (((listPtr)->typePtr == &tclListType) \ - ? ((ListObjGetElements((listPtr), *(objcPtr), *(objvPtr))), TCL_OK)\ - : Tcl_ListObjGetElements((interp), (listPtr), (objcPtr), (objvPtr))) +/* + * Macros used to get access list internal representations. + * + * Naming conventions: + * ListRep* - expect a pointer to a valid ListRep + * ListObj* - expect a pointer to a Tcl_Obj whose internal type is known to + * be a list (tclListType). Will crash otherwise. + * TclListObj* - expect a pointer to a Tcl_Obj whose internal type may or may not + * be tclListType. These will convert as needed and return error if + * conversion not possible. + */ + +/* Returns the starting slot for this listRep in the contained ListStore */ +#define ListRepStart(listRepPtr_) \ + ((listRepPtr_)->spanPtr ? (listRepPtr_)->spanPtr->spanStart \ + : (listRepPtr_)->storePtr->firstUsed) + +/* Returns the number of elements in this listRep */ +#define ListRepLength(listRepPtr_) \ + ((listRepPtr_)->spanPtr ? (listRepPtr_)->spanPtr->spanLength \ + : (listRepPtr_)->storePtr->numUsed) + +/* Returns a pointer to the first slot containing this ListRep elements */ +#define ListRepElementsBase(listRepPtr_) \ + (&(listRepPtr_)->storePtr->slots[ListRepStart(listRepPtr_)]) + +/* Stores the number of elements and base address of the element array */ +#define ListRepElements(listRepPtr_, objc_, objv_) \ + (((objv_) = ListRepElementsBase(listRepPtr_)), \ + ((objc_) = ListRepLength(listRepPtr_))) + +/* Returns 1/0 whether the ListRep's ListStore is shared. */ +#define ListRepIsShared(listRepPtr_) ((listRepPtr_)->storePtr->refCount > 1) + +/* Returns a pointer to the ListStore component */ +#define ListObjStorePtr(listObj_) \ + ((ListStore *)((listObj_)->internalRep.twoPtrValue.ptr1)) + +/* Returns a pointer to the ListSpan component */ +#define ListObjSpanPtr(listObj_) \ + ((ListSpan *)((listObj_)->internalRep.twoPtrValue.ptr2)) + +/* Returns the ListRep internal representaton in a Tcl_Obj */ +#define ListObjGetRep(listObj_, listRepPtr_) \ + do { \ + (listRepPtr_)->storePtr = ListObjStorePtr(listObj_); \ + (listRepPtr_)->spanPtr = ListObjSpanPtr(listObj_); \ + } while (0) + +/* Returns the length of the list */ +#define ListObjLength(listObj_, len_) \ + ((len_) = ListObjSpanPtr(listObj_) ? ListObjSpanPtr(listObj_)->spanLength \ + : ListObjStorePtr(listObj_)->numUsed) + +/* Returns the starting slot index of this list's elements in the ListStore */ +#define ListObjStart(listObj_) \ + (ListObjSpanPtr(listObj_) ? ListObjSpanPtr(listObj_)->spanStart \ + : ListObjStorePtr(listObj_)->firstUsed) + +/* Stores the element count and base address of this list's elements */ +#define ListObjGetElements(listObj_, objc_, objv_) \ + (((objv_) = &ListObjStorePtr(listObj_)->slots[ListObjStart(listObj_)]), \ + (ListObjLength(listObj_, (objc_)))) + +/* + * Returns 1/0 whether the internal representation (not the Tcl_Obj itself) + * is shared. Note by intent this only checks for sharing of ListStore, + * not spans. + */ +#define ListObjRepIsShared(listObj_) (ListObjStorePtr(listObj_)->refCount > 1) -#define TclListObjLengthM(interp, listPtr, lenPtr) \ - (((listPtr)->typePtr == &tclListType) \ - ? ((ListObjLength((listPtr), *(lenPtr))), TCL_OK)\ - : Tcl_ListObjLength((interp), (listPtr), (lenPtr))) +/* + * Certain commands like concat are optimized if an existing string + * representation of a list object is known to be in canonical format (i.e. + * generated from the list representation). There are three conditions when + * this will be the case: + * (1) No string representation exists which means it will obviously have + * to be generated from the list representation when needed + * (2) The ListStore flags is marked canonical. This is done at the time + * the string representation is generated from the list IF the list + * representation does not have a span (see comments in UpdateStringOfList). + * (3) The list representation does not have a span component. This is + * because list Tcl_Obj's with spans are always created from existing lists + * and never from strings (see SetListFromAny) and thus their string + * representation will always be canonical. + */ +#define ListObjIsCanonical(listObj_) \ + (((listObj_)->bytes == NULL) \ + || (ListObjStorePtr(listObj_)->flags & LISTSTORE_CANONICAL) \ + || ListObjSpanPtr(listObj_) != NULL) + +/* + * Converts the Tcl_Obj to a list if it isn't one and stores the element + * count and base address of this list's elements in objcPtr_ and objvPtr_. + * Return TCL_OK on success or TCL_ERROR if the Tcl_Obj cannot be + * converted to a list. + */ +#define TclListObjGetElementsM(interp_, listObj_, objcPtr_, objvPtr_) \ + (((listObj_)->typePtr == &tclListType) \ + ? ((ListObjGetElements((listObj_), *(objcPtr_), *(objvPtr_))), \ + TCL_OK) \ + : Tcl_ListObjGetElements( \ + (interp_), (listObj_), (objcPtr_), (objvPtr_))) + +/* + * Converts the Tcl_Obj to a list if it isn't one and stores the element + * count in lenPtr_. Returns TCL_OK on success or TCL_ERROR if the + * Tcl_Obj cannot be converted to a list. + */ +#define TclListObjLengthM(interp_, listObj_, lenPtr_) \ + (((listObj_)->typePtr == &tclListType) \ + ? ((ListObjLength((listObj_), *(lenPtr_))), TCL_OK) \ + : Tcl_ListObjLength((interp_), (listObj_), (lenPtr_))) -#define TclListObjIsCanonical(listPtr) \ - (((listPtr)->typePtr == &tclListType) ? ListObjIsCanonical((listPtr)) : 0) +#define TclListObjIsCanonical(listObj_) \ + (((listObj_)->typePtr == &tclListType) ? ListObjIsCanonical((listObj_)) : 0) /* * Modes for collecting (or not) in the implementations of TclNRForeachCmd, @@ -3030,6 +3179,9 @@ MODULE_SCOPE Tcl_Obj * TclLindexFlat(Tcl_Interp *interp, Tcl_Obj *listPtr, MODULE_SCOPE void TclListLines(Tcl_Obj *listObj, size_t line, int n, int *lines, Tcl_Obj *const *elems); MODULE_SCOPE Tcl_Obj * TclListObjCopy(Tcl_Interp *interp, Tcl_Obj *listPtr); +MODULE_SCOPE int TclListObjAppendElements(Tcl_Interp *interp, + Tcl_Obj *toObj, size_t elemCount, + Tcl_Obj *const elemObjv[]); MODULE_SCOPE Tcl_Obj * TclListObjRange(Tcl_Obj *listPtr, size_t fromIdx, size_t toIdx); MODULE_SCOPE Tcl_Obj * TclLsetList(Tcl_Interp *interp, Tcl_Obj *listPtr, diff --git a/generic/tclInterp.c b/generic/tclInterp.c index d368829..589b0da 100644 --- a/generic/tclInterp.c +++ b/generic/tclInterp.c @@ -1829,7 +1829,7 @@ AliasNRCmd( int prefc, cmdc, i; Tcl_Obj **prefv, **cmdv; Tcl_Obj *listPtr; - List *listRep; + ListRep listRep; int flags = TCL_EVAL_INVOKE; /* @@ -1841,14 +1841,19 @@ AliasNRCmd( prefv = &aliasPtr->objPtr; cmdc = prefc + objc - 1; + /* TODO - encapsulate this into tclListObj.c */ listPtr = Tcl_NewListObj(cmdc, NULL); - listRep = ListRepPtr(listPtr); - listRep->elemCount = cmdc; - cmdv = listRep->elements; + ListObjGetRep(listPtr, &listRep); + cmdv = ListRepElementsBase(&listRep); + listRep.storePtr->numUsed = cmdc; + if (listRep.spanPtr) { + listRep.spanPtr->spanStart = listRep.storePtr->firstUsed; + listRep.spanPtr->spanLength = listRep.storePtr->numUsed; + } prefv = &aliasPtr->objPtr; - memcpy(cmdv, prefv, (prefc * sizeof(Tcl_Obj *))); - memcpy(cmdv+prefc, objv+1, ((objc-1) * sizeof(Tcl_Obj *))); + memcpy(cmdv, prefv, prefc * sizeof(Tcl_Obj *)); + memcpy(cmdv+prefc, objv+1, (objc-1) * sizeof(Tcl_Obj *)); for (i=0; i<cmdc; i++) { Tcl_IncrRefCount(cmdv[i]); diff --git a/generic/tclListObj.c b/generic/tclListObj.c index b0a21ca..95f2d61 100644 --- a/generic/tclListObj.c +++ b/generic/tclListObj.c @@ -3,9 +3,7 @@ * * This file contains functions that implement the Tcl list object type. * - * Copyright © 1995-1997 Sun Microsystems, Inc. - * Copyright © 1998 Scriptics Corporation. - * Copyright © 2001 Kevin B. Kenny. All rights reserved. + * Copyright © 2022 Ashok P. Nadkarni. All rights reserved. * * See the file "license.terms" for information on usage and redistribution of * this file, and for a DISCLAIMER OF ALL WARRANTIES. @@ -14,13 +12,131 @@ #include "tclInt.h" #include <assert.h> +/* TODO - memmove is fast. Measure at what size we should prefer memmove + (for unshared objects only) in lieu of range operations */ + +/* + * Macros for validation and bug checking. + */ + /* - * Prototypes for functions defined later in this file: + * Control whether asserts are enabled. Always enable in debug builds. In non-debug + * builds, can be set with cdebug="-DENABLE_LIST_ASSERTS" on the nmake command line. */ +#ifdef ENABLE_LIST_ASSERTS +# ifdef NDEBUG +# undef NDEBUG /* Activate assert() macro */ +# endif +#else +# ifndef NDEBUG +# define ENABLE_LIST_ASSERTS /* Always activate list asserts in debug mode */ +# endif +#endif + +#ifdef ENABLE_LIST_ASSERTS + +#define LIST_ASSERT(cond_) assert(cond_) /* TODO - is there a Tcl-specific one? */ +/* + * LIST_INDEX_ASSERT is to catch errors with negative indices and counts + * being passed AFTER validation. On Tcl9 length types are unsigned hence + * the checks against LIST_MAX. On Tcl8 length types are signed hence the + * also checks against 0. + */ +#define LIST_INDEX_ASSERT(idxarg_) \ + do { \ + ListSizeT idx_ = (idxarg_); /* To guard against ++ etc. */ \ + LIST_ASSERT(idx_ >= 0 && idx_ < LIST_MAX); \ + } while (0) +/* Ditto for counts except upper limit is different */ +#define LIST_COUNT_ASSERT(countarg_) \ + do { \ + ListSizeT count_ = (countarg_); /* To guard against ++ etc. */ \ + LIST_ASSERT(count_ >= 0 && count_ <= LIST_MAX); \ + } while (0) + +#else + +#define LIST_ASSERT(cond_) ((void) 0) +#define LIST_INDEX_ASSERT(idx_) ((void) 0) +#define LIST_COUNT_ASSERT(count_) ((void) 0) + +#endif + +/* Checks for when caller should have already converted to internal list type */ +#define LIST_ASSERT_TYPE(listObj_) \ + LIST_ASSERT((listObj_)->typePtr == &tclListType); + + +/* + * If ENABLE_LIST_INVARIANTS is enabled (-DENABLE_LIST_INVARIANTS from the + * command line), the entire list internal representation is checked for + * inconsistencies. This has a non-trivial cost so has to be separately + * enabled and not part of assertions checking. + */ +#ifdef ENABLE_LIST_INVARIANTS +#define LISTREP_CHECK(listRepPtr_) ListRepValidate(listRepPtr_) +#else +#define LISTREP_CHECK(listRepPtr_) (void) 0 +#endif + +/* + * Flags used for controlling behavior of allocation of list + * internal representations. + * + * If the LISTREP_PANIC_ON_FAIL bit is set, the function will panic if + * list is too large or memory cannot be allocated. Without the flag + * a NULL pointer is returned. + * + * The LISTREP_SPACE_FAVOR_NONE, LISTREP_SPACE_FAVOR_FRONT, + * LISTREP_SPACE_FAVOR_BACK, LISTREP_SPACE_ONLY_BACK flags are used to + * control additional space when allocating. + * - If none of these flags is present, the exact space requested is + * allocated, nothing more. + * - Otherwise, if only LISTREP_FAVOR_FRONT is present, extra space is + * allocated with more towards the front. + * - Conversely, if only LISTREP_FAVOR_BACK is present extra space is allocated + * with more to the back. + * - If both flags are present (LISTREP_SPACE_FAVOR_NONE), the extra space + * is equally apportioned. + * - Finally if LISTREP_SPACE_ONLY_BACK is present, ALL extra space is at + * the back. + */ +#define LISTREP_PANIC_ON_FAIL 0x00000001 +#define LISTREP_SPACE_FAVOR_FRONT 0x00000002 +#define LISTREP_SPACE_FAVOR_BACK 0x00000004 +#define LISTREP_SPACE_ONLY_BACK 0x00000008 +#define LISTREP_SPACE_FAVOR_NONE \ + (LISTREP_SPACE_FAVOR_FRONT | LISTREP_SPACE_FAVOR_BACK) +#define LISTREP_SPACE_FLAGS \ + (LISTREP_SPACE_FAVOR_FRONT | LISTREP_SPACE_FAVOR_BACK \ + | LISTREP_SPACE_ONLY_BACK) + +/* + * Prototypes for non-inline static functions defined later in this file: + */ +static int MemoryAllocationError(Tcl_Interp *, size_t size); +static int ListLimitExceededError(Tcl_Interp *); +static ListStore * +ListStoreNew(ListSizeT objc, Tcl_Obj *const objv[], int flags); +static int +ListRepInit(ListSizeT objc, Tcl_Obj *const objv[], int flags, ListRep *); +static int ListRepInitAttempt(Tcl_Interp *, + ListSizeT objc, + Tcl_Obj *const objv[], + ListRep *); +static void ListRepClone(ListRep *fromRepPtr, ListRep *toRepPtr, int flags); +static void ListRepUnsharedFreeUnreferenced(const ListRep *repPtr); +static int TclListObjGetRep(Tcl_Interp *, Tcl_Obj *listPtr, ListRep *repPtr); +static void ListRepRange(ListRep *srcRepPtr, + ListSizeT rangeStart, + ListSizeT rangeEnd, + int preserveSrcRep, + ListRep *rangeRepPtr); +static ListStore *ListStoreReallocate(ListStore *storePtr, ListSizeT numSlots); +#ifdef ENABLE_LIST_ASSERTS /* Else gcc complains about unused static */ +static void ListRepValidate(const ListRep *repPtr); +#endif -static List * AttemptNewList(Tcl_Interp *interp, size_t objc, - Tcl_Obj *const objv[]); -static List * NewListInternalRep(size_t objc, Tcl_Obj *const objv[], size_t p); static void DupListInternalRep(Tcl_Obj *srcPtr, Tcl_Obj *copyPtr); static void FreeListInternalRep(Tcl_Obj *listPtr); static int SetListFromAny(Tcl_Interp *interp, Tcl_Obj *objPtr); @@ -30,13 +146,7 @@ static void UpdateStringOfList(Tcl_Obj *listPtr); * The structure below defines the list Tcl object type by means of functions * that can be invoked by generic object code. * - * The internal representation of a list object is a two-pointer - * representation. The first pointer designates a List structure that contains - * an array of pointers to the element objects, together with integers that - * represent the current element count and the allocated size of the array. - * The second pointer is normally NULL; during execution of functions in this - * file that operate on nested sublists, it is occasionally used as working - * storage to avoid an auxiliary stack. + * The internal representation of a list object is ListRep defined in tcl.h. */ const Tcl_ObjType tclListType = { @@ -48,144 +158,929 @@ const Tcl_ObjType tclListType = { }; /* Macros to manipulate the List internal rep */ +#define ListRepIncrRefs(repPtr_) \ + do { \ + (repPtr_)->storePtr->refCount++; \ + if ((repPtr_)->spanPtr) \ + (repPtr_)->spanPtr->refCount++; \ + } while (0) + +/* Returns number of free unused slots at the back of the ListRep's ListStore */ +#define ListRepNumFreeTail(repPtr_) \ + ((repPtr_)->storePtr->numAllocated \ + - ((repPtr_)->storePtr->firstUsed + (repPtr_)->storePtr->numUsed)) + +/* Returns number of free unused slots at the front of the ListRep's ListStore */ +#define ListRepNumFreeHead(repPtr_) ((repPtr_)->storePtr->firstUsed) + +/* Returns a pointer to the slot corresponding to list index listIdx_ */ +#define ListRepSlotPtr(repPtr_, listIdx_) \ + (&(repPtr_)->storePtr->slots[ListRepStart(repPtr_) + (listIdx_)]) + +/* + * Macros to replace the internal representation in a Tcl_Obj. There are + * subtle differences in each so make sure to use the right one to avoid + * memory leaks, access to freed memory and the like. + * + * ListObjStompRep - assumes the Tcl_Obj internal representation can be + * overwritten AND that the passed ListRep already has reference counts that + * include the reference from the Tcl_Obj. Basically just copies the pointers + * and sets the internal Tcl_Obj type to list + * + * ListObjOverwriteRep - like ListObjOverwriteRep but additionally + * increments reference counts on the passed ListRep. Generally used when + * the string representation of the Tcl_Obj is not to be modified. + * + * ListObjReplaceRepAndInvalidate - Like ListObjOverwriteRep but additionally + * assumes the Tcl_Obj internal rep is valid (and possibly even same as + * passed ListRep) and frees it first. Additionally invalidates the string + * representation. Generally used when modifying a Tcl_Obj value. + */ +#define ListObjStompRep(objPtr_, repPtr_) \ + do { \ + (objPtr_)->internalRep.twoPtrValue.ptr1 = (repPtr_)->storePtr; \ + (objPtr_)->internalRep.twoPtrValue.ptr2 = (repPtr_)->spanPtr; \ + (objPtr_)->typePtr = &tclListType; \ + } while (0) -#define ListSetInternalRep(objPtr, listRepPtr) \ - do { \ - Tcl_ObjInternalRep ir; \ - ir.twoPtrValue.ptr1 = (listRepPtr); \ - ir.twoPtrValue.ptr2 = NULL; \ - (listRepPtr)->refCount++; \ - Tcl_StoreInternalRep((objPtr), &tclListType, &ir); \ +#define ListObjOverwriteRep(objPtr_, repPtr_) \ + do { \ + ListRepIncrRefs(repPtr_); \ + ListObjStompRep(objPtr_, repPtr_); \ } while (0) -#define ListGetInternalRep(objPtr, listRepPtr) \ - do { \ - const Tcl_ObjInternalRep *irPtr; \ - irPtr = TclFetchInternalRep((objPtr), &tclListType); \ - (listRepPtr) = irPtr ? (List *)irPtr->twoPtrValue.ptr1 : NULL; \ +#define ListObjReplaceRepAndInvalidate(objPtr_, repPtr_) \ + do { \ + /* Note order important, don't use ListObjOverwriteRep! */ \ + ListRepIncrRefs(repPtr_); \ + TclFreeInternalRep(objPtr_); \ + TclInvalidateStringRep(objPtr_); \ + ListObjStompRep(objPtr_, repPtr_); \ } while (0) -#define ListResetInternalRep(objPtr, listRepPtr) \ - TclFetchInternalRep((objPtr), &tclListType)->twoPtrValue.ptr1 = (listRepPtr) +/* + *------------------------------------------------------------------------ + * + * ListSpanNew -- + * + * Allocates and initializes memory for a new ListSpan. The reference + * count on the returned struct is 0. + * + * Results: + * Non-NULL pointer to the allocated ListSpan. + * + * Side effects: + * The function will panic on memory allocation failure. + * + *------------------------------------------------------------------------ + */ +static inline ListSpan * +ListSpanNew( + ListSizeT firstSlot, /* Starting slot index of the span */ + ListSizeT numSlots) /* Number of slots covered by the span */ +{ + ListSpan *spanPtr = (ListSpan *) Tcl_Alloc(sizeof(*spanPtr)); + spanPtr->refCount = 0; + spanPtr->spanStart = firstSlot; + spanPtr->spanLength = numSlots; + return spanPtr; +} -#ifndef TCL_MIN_ELEMENT_GROWTH -#define TCL_MIN_ELEMENT_GROWTH TCL_MIN_GROWTH/sizeof(Tcl_Obj *) +/* + *------------------------------------------------------------------------ + * + * ListSpanIncrRefs -- + * + * Increments the reference count on the spanPtr + * + * Results: + * None. + * + * Side effects: + * The obvious. + * + *------------------------------------------------------------------------ + */ + +static inline void +ListSpanIncrRefs(ListSpan *spanPtr) +{ + spanPtr->refCount += 1; +} + +/* + *------------------------------------------------------------------------ + * + * ListSpanDecrRefs -- + * + * Decrements the reference count on a span, freeing the memory if + * it drops to zero or less. + * + * Results: + * None. + * + * Side effects: + * The memory may be freed. + * + *------------------------------------------------------------------------ + */ + +static inline void +ListSpanDecrRefs(ListSpan *spanPtr) +{ + if (spanPtr->refCount <= 1) { + Tcl_Free(spanPtr); + } else { + spanPtr->refCount -= 1; + } +} + +/* + *------------------------------------------------------------------------ + * + * ListSpanMerited -- + * + * Creation of a new list may sometimes be done as a span on existing + * storage instead of allocating new. The tradeoff is that if the + * original list is released, the new span-based list may hold on to + * more memory than desired. This function implements heuristics for + * deciding which option is better. + * + * Results: + * Returns non-0 if a span-based list is likely to be more optimal + * and 0 if not. + * + * Side effects: + * None. + * + *------------------------------------------------------------------------ + */ + +static inline int +ListSpanMerited( + ListSizeT length, /* Length of the proposed span */ + ListSizeT usedStorageLength, /* Number of slots currently in used */ + ListSizeT allocatedStorageLength) /* Length of the currently allocation */ +{ + /* + TODO + - heuristics thresholds need to be determined + - currently, information about the sharing (ref count) of existing + storage is not passed. Perhaps it should be. For example if the + existing storage has a "large" ref count, then it might make sense + to do even a small span. + */ +#ifndef TCL_LIST_SPAN_MINSIZE /* May be set on build line */ +#define TCL_LIST_SPAN_MINSIZE 101 #endif - + + if (length < TCL_LIST_SPAN_MINSIZE) + return 0;/* No span for small lists */ + if (length < (allocatedStorageLength/2 - allocatedStorageLength/8)) + return 0; /* No span if less than 3/8 of allocation */ + if (length < usedStorageLength / 2) + return 0; /* No span if less than half current storage */ + + return 1; +} + /* - *---------------------------------------------------------------------- + *------------------------------------------------------------------------ + * + * ListStoreUpSize -- + * + * For reasons of efficiency, extra space is allocated for a ListStore + * compared to what was requested. This function calculates how many + * slots should actually be allocated for a given request size. + * + * Results: + * Number of slots to allocate. * - * NewListInternalRep -- + * Side effects: + * None. * - * Creates a 'List' structure with space for 'objc' elements. 'objc' must - * be > 0. If 'objv' is not NULL, The list is initialized with first - * 'objc' values in that array. Otherwise the list is initialized to have - * 0 elements, with space to add 'objc' more. Flag value 'p' indicates - * how to behave on failure. + *------------------------------------------------------------------------ + */ +static inline ListSizeT +ListStoreUpSize(ListSizeT numSlotsRequested) { + /* TODO -how much extra? May be double only for smaller requests? */ + return numSlotsRequested < (LIST_MAX / 2) ? 2 * numSlotsRequested + : LIST_MAX; +} + +/* + *------------------------------------------------------------------------ * - * Value + * ListRepFreeUnreferenced -- * - * A new 'List' structure with refCount 0. If some failure - * prevents this NULL is returned if 'p' is 0 , and 'Tcl_Panic' - * is called if it is not. + * Inline wrapper for ListRepUnsharedFreeUnreferenced that does quick checks + * before calling it. * - * Effect + * IMPORTANT: this function must not be called on an internal + * representation of a Tcl_Obj that is itself shared. * - * The refCount of each value in 'objv' is incremented as it is added - * to the list. + * Results: + * None. * - *---------------------------------------------------------------------- + * Side effects: + * See comments for ListRepUnsharedFreeUnreferenced. + * + *------------------------------------------------------------------------ + */ +static inline void +ListRepFreeUnreferenced(const ListRep *repPtr) +{ + if (! ListRepIsShared(repPtr) && repPtr->spanPtr) { + ListRepUnsharedFreeUnreferenced(repPtr); + } +} + +/* + *------------------------------------------------------------------------ + * + * ObjArrayIncrRefs -- + * + * Increments the reference counts for Tcl_Obj's in a subarray. + * + * Results: + * None. + * + * Side effects: + * As above. + * + *------------------------------------------------------------------------ + */ +static inline void +ObjArrayIncrRefs( + Tcl_Obj * const *objv, /* Pointer to the array */ + ListSizeT startIdx, /* Starting index of subarray within objv */ + ListSizeT count) /* Number of elements in the subarray */ +{ + Tcl_Obj * const *end; + LIST_INDEX_ASSERT(startIdx); + LIST_COUNT_ASSERT(count); + objv += startIdx; + end = objv + count; + while (objv < end) { + Tcl_IncrRefCount(*objv); + ++objv; + } +} + +/* + *------------------------------------------------------------------------ + * + * ObjArrayDecrRefs -- + * + * Decrements the reference counts for Tcl_Obj's in a subarray. + * + * Results: + * None. + * + * Side effects: + * As above. + * + *------------------------------------------------------------------------ + */ +static inline void +ObjArrayDecrRefs( + Tcl_Obj * const *objv, /* Pointer to the array */ + ListSizeT startIdx, /* Starting index of subarray within objv */ + ListSizeT count) /* Number of elements in the subarray */ +{ + Tcl_Obj * const *end; + LIST_INDEX_ASSERT(startIdx); + LIST_COUNT_ASSERT(count); + objv += startIdx; + end = objv + count; + while (objv < end) { + Tcl_DecrRefCount(*objv); + ++objv; + } +} + +/* + *------------------------------------------------------------------------ + * + * ObjArrayCopy -- + * + * Copies an array of Tcl_Obj* pointers. + * + * Results: + * None. + * + * Side effects: + * Reference counts on copied Tcl_Obj's are incremented. + * + *------------------------------------------------------------------------ + */ +static inline void +ObjArrayCopy( + Tcl_Obj **to, /* Destination */ + ListSizeT count, /* Number of pointers to copy */ + Tcl_Obj *const from[]) /* Source array of Tcl_Obj* */ +{ + Tcl_Obj **end; + LIST_COUNT_ASSERT(count); + end = to + count; + /* TODO - would memmove followed by separate IncrRef loop be faster? */ + while (to < end) { + Tcl_IncrRefCount(*from); + *to++ = *from++; + } +} + +/* + *------------------------------------------------------------------------ + * + * MemoryAllocationError -- + * + * Generates a memory allocation failure error. + * + * Results: + * Always TCL_ERROR. + * + * Side effects: + * Error message and code are stored in the interpreter if not NULL. + * + *------------------------------------------------------------------------ + */ +static int +MemoryAllocationError( + Tcl_Interp *interp, /* Interpreter for error message. May be NULL */ + size_t size) /* Size of attempted allocation that failed */ +{ + if (interp != NULL) { + Tcl_SetObjResult( + interp, + Tcl_ObjPrintf( + "list construction failed: unable to alloc %" TCL_LL_MODIFIER + "u bytes", + (Tcl_WideInt)size)); + Tcl_SetErrorCode(interp, "TCL", "MEMORY", NULL); + } + return TCL_ERROR; +} + +/* + *------------------------------------------------------------------------ + * + * ListLimitExceeded -- + * + * Generates an error for exceeding maximum list size. + * + * Results: + * Always TCL_ERROR. + * + * Side effects: + * Error message and code are stored in the interpreter if not NULL. + * + *------------------------------------------------------------------------ + */ +static int +ListLimitExceededError(Tcl_Interp *interp) +{ + if (interp != NULL) { + Tcl_SetObjResult( + interp, + Tcl_ObjPrintf("max length of a Tcl list (%" TCL_Z_MODIFIER "u) elements) exceeded", + LIST_MAX)); + Tcl_SetErrorCode(interp, "TCL", "MEMORY", NULL); + } + return TCL_ERROR; +} + +/* + *------------------------------------------------------------------------ + * + * ListRepUnsharedShiftDown -- + * + * Shifts the "in-use" contents in the ListStore for a ListRep down + * by the given number of slots. The ListStore must be unshared and + * the free space at the front of the storage area must be big enough. + * It is the caller's responsibility to check. + * + * Results: + * None. + * + * Side effects: + * The contents of the ListRep's ListStore area are shifted down in the + * storage area. The ListRep's ListSpan is updated accordingly. + * + *------------------------------------------------------------------------ + */ +static inline void +ListRepUnsharedShiftDown(ListRep *repPtr, ListSizeT shiftCount) +{ + ListStore *storePtr; + + LISTREP_CHECK(repPtr); + LIST_ASSERT(!ListRepIsShared(repPtr)); + + storePtr = repPtr->storePtr; + + LIST_COUNT_ASSERT(shiftCount); + LIST_ASSERT(storePtr->firstUsed >= shiftCount); + + memmove(&storePtr->slots[storePtr->firstUsed - shiftCount], + &storePtr->slots[storePtr->firstUsed], + storePtr->numUsed * sizeof(Tcl_Obj *)); + storePtr->firstUsed -= shiftCount; + if (repPtr->spanPtr) { + repPtr->spanPtr->spanStart -= shiftCount; + LIST_ASSERT(repPtr->spanPtr->spanLength == storePtr->numUsed); + } else { + /* + * If there was no span, firstUsed must have been 0 (Invariant) + * AND shiftCount must have been 0 (<= firstUsed on call) + * In other words, this would have been a no-op + */ + + LIST_ASSERT(storePtr->firstUsed == 0); + LIST_ASSERT(shiftCount == 0); + } + + LISTREP_CHECK(repPtr); +} + +/* + *------------------------------------------------------------------------ + * + * ListRepUnsharedShiftUp -- + * + * Shifts the "in-use" contents in the ListStore for a ListRep up + * by the given number of slots. The ListStore must be unshared and + * the free space at the back of the storage area must be big enough. + * It is the caller's responsibility to check. + * TODO - this function is not currently used. + * + * Results: + * None. + * + * Side effects: + * The contents of the ListRep's ListStore area are shifted up in the + * storage area. The ListRep's ListSpan is updated accordingly. + * + *------------------------------------------------------------------------ + */ +static inline void +ListRepUnsharedShiftUp(ListRep *repPtr, ListSizeT shiftCount) +{ + ListStore *storePtr; + + LISTREP_CHECK(repPtr); + LIST_ASSERT(!ListRepIsShared(repPtr)); + LIST_COUNT_ASSERT(shiftCount); + + storePtr = repPtr->storePtr; + LIST_ASSERT((storePtr->firstUsed + storePtr->numUsed + shiftCount) + <= storePtr->numAllocated); + + memmove(&storePtr->slots[storePtr->firstUsed + shiftCount], + &storePtr->slots[storePtr->firstUsed], + storePtr->numUsed * sizeof(Tcl_Obj *)); + storePtr->firstUsed += shiftCount; + if (repPtr->spanPtr) { + repPtr->spanPtr->spanStart += shiftCount; + } else { + /* No span means entire original list is span */ + /* Should have been zero before shift - Invariant TBD */ + LIST_ASSERT(storePtr->firstUsed == shiftCount); + repPtr->spanPtr = ListSpanNew(shiftCount, storePtr->numUsed); + } + + LISTREP_CHECK(repPtr); +} + +#ifdef ENABLE_LIST_ASSERTS /* Else gcc complains about unused static */ +/* + *------------------------------------------------------------------------ + * + * ListRepValidate -- + * + * Checks all invariants for a ListRep. + * + * Results: + * None. + * + * Side effects: + * Panics (assertion failure) if any invariant is not met. + * + *------------------------------------------------------------------------ */ +static void +ListRepValidate(const ListRep *repPtr) +{ + ListStore *storePtr = repPtr->storePtr; + + (void)storePtr; /* To stop gcc from whining about unused vars */ + + /* Separate each condition so line number gives exact reason for failure */ + LIST_ASSERT(storePtr != NULL); + LIST_ASSERT(storePtr->numAllocated >= 0); + LIST_ASSERT(storePtr->numAllocated <= LIST_MAX); + LIST_ASSERT(storePtr->firstUsed >= 0); + LIST_ASSERT(storePtr->firstUsed < storePtr->numAllocated); + LIST_ASSERT(storePtr->numUsed >= 0); + LIST_ASSERT(storePtr->numUsed <= storePtr->numAllocated); + LIST_ASSERT(storePtr->firstUsed + <= (storePtr->numAllocated - storePtr->numUsed)); + +#if 0 && defined(LIST_MEM_DEBUG) + /* Corresponding zeroing out not implemented yet */ + for (i = 0; i < storePtr->firstUsed; ++i) { + LIST_ASSERT(storePtr->slots[i] == NULL); + } + for (i = storePtr->firstUsed + storePtr->numUsed; + i < storePtr->numAllocated; + ++i) { + LIST_ASSERT(storePtr->slots[i] == NULL); + } +#endif -static List * -NewListInternalRep( - size_t objc, + if (! ListRepIsShared(repPtr)) { + /* + * If this is the only reference and there is no span, then store + * occupancy must begin at 0 + */ + LIST_ASSERT(repPtr->spanPtr || repPtr->storePtr->firstUsed == 0); + } + + LIST_ASSERT(ListRepStart(repPtr) >= storePtr->firstUsed); + LIST_ASSERT(ListRepLength(repPtr) <= storePtr->numUsed); + LIST_ASSERT(ListRepStart(repPtr) + <= (storePtr->firstUsed + storePtr->numUsed - ListRepLength(repPtr))); + +} +#endif /* ENABLE_LIST_ASSERTS */ + +/* + *---------------------------------------------------------------------- + * + * ListStoreNew -- + * + * Allocates a new ListStore with space for at least objc elements. objc + * must be > 0. If objv!=NULL, initializes with the first objc values + * in that array. If objv==NULL, initalize 0 elements, with space + * to add objc more. + * + * Normally the function allocates the exact space requested unless + * the flags arguments has any LISTREP_SPACE_* + * bits set. See the comments for those #defines. + * + * Results: + * On success, a pointer to the allocated ListStore is returned. + * On allocation failure, panics if LISTREP_PANIC_ON_FAIL is set in + * flags; otherwise returns NULL. + * + * Side effects: + * The ref counts of the elements in objv are incremented on success + * since the returned ListStore references them. + * + *---------------------------------------------------------------------- + */ +static ListStore * +ListStoreNew( + ListSizeT objc, Tcl_Obj *const objv[], - size_t p) + int flags) { - List *listRepPtr; + ListStore *storePtr; + ListSizeT capacity; - listRepPtr = (List *)Tcl_AttemptAlloc(LIST_SIZE(objc)); - if (listRepPtr == NULL) { - if (p) { - Tcl_Panic("list creation failed: unable to alloc %" TCL_Z_MODIFIER "u bytes", + /* + * First check to see if we'd overflow and try to allocate an object + * larger than our memory allocator allows. + */ + if (objc > LIST_MAX) { + if (flags & LISTREP_PANIC_ON_FAIL) { + Tcl_Panic("max length of a Tcl list (%" TCL_Z_MODIFIER "u elements) exceeded", + LIST_MAX); + } + return NULL; + } + + if (flags & LISTREP_SPACE_FLAGS) { + capacity = ListStoreUpSize(objc); + } else { + capacity = objc; + } + + storePtr = (ListStore *)Tcl_AttemptAlloc(LIST_SIZE(capacity)); + if (storePtr == NULL && capacity != objc) { + capacity = objc; /* Try allocating exact size */ + storePtr = (ListStore *)Tcl_AttemptAlloc(LIST_SIZE(capacity)); + } + if (storePtr == NULL) { + if (flags & LISTREP_PANIC_ON_FAIL) { + Tcl_Panic("list creation failed: unable to alloc %u bytes", LIST_SIZE(objc)); } return NULL; } - listRepPtr->canonicalFlag = 0; - listRepPtr->refCount = 0; - listRepPtr->maxElemCount = objc; + storePtr->refCount = 0; + storePtr->flags = 0; + storePtr->numAllocated = capacity; + if (capacity == objc) { + storePtr->firstUsed = 0; + } else { + ListSizeT extra = capacity - objc; + int spaceFlags = flags & LISTREP_SPACE_FLAGS; + if (spaceFlags == LISTREP_SPACE_ONLY_BACK) { + storePtr->firstUsed = 0; + } else if (spaceFlags == LISTREP_SPACE_FAVOR_FRONT) { + /* Leave more space in the front */ + storePtr->firstUsed = + extra - (extra / 4); /* NOT same as 3*extra/4 */ + } else if (spaceFlags == LISTREP_SPACE_FAVOR_BACK) { + /* Leave more space in the back */ + storePtr->firstUsed = extra / 4; + } else { + /* Apportion equally */ + storePtr->firstUsed = extra / 2; + } + } if (objv) { - Tcl_Obj **elemPtrs; - size_t i; - - listRepPtr->elemCount = objc; - elemPtrs = listRepPtr->elements; - for (i = 0; i < objc; i++) { - elemPtrs[i] = objv[i]; - Tcl_IncrRefCount(elemPtrs[i]); - } + storePtr->numUsed = objc; + ObjArrayCopy(&storePtr->slots[storePtr->firstUsed], objc, objv); } else { - listRepPtr->elemCount = 0; + storePtr->numUsed = 0; } - return listRepPtr; + + return storePtr; } - + +/* + *------------------------------------------------------------------------ + * + * ListStoreReallocate -- + * + * Reallocates the memory for a ListStore. + * + * Results: + * Pointer to the ListStore which may be the same as storePtr or pointer + * to a new block of memory. On reallocation failure, NULL is returned. + * + * + * Side effects: + * The memory pointed to by storePtr is freed if it a new block has to + * be returned. + * + * + *------------------------------------------------------------------------ + */ +ListStore * +ListStoreReallocate (ListStore *storePtr, ListSizeT numSlots) +{ + ListSizeT newCapacity; + ListStore *newStorePtr; + + newCapacity = ListStoreUpSize(numSlots); + newStorePtr = + (ListStore *)Tcl_AttemptRealloc(storePtr, LIST_SIZE(newCapacity)); + if (newStorePtr == NULL) { + newCapacity = numSlots; + newStorePtr = (ListStore *)Tcl_AttemptRealloc(storePtr, + LIST_SIZE(newCapacity)); + if (newStorePtr == NULL) + return NULL; + } + /* Only the capacity has changed, fix it in the header */ + newStorePtr->numAllocated = newCapacity; + return newStorePtr; +} + /* *---------------------------------------------------------------------- * - * AttemptNewList -- + * ListRepInit -- + * + * Initializes a ListRep to hold a list internal representation + * with space for objc elements. + * + * objc must be > 0. If objv!=NULL, initializes with the first objc + * values in that array. If objv==NULL, initalize list internal rep to + * have 0 elements, with space to add objc more. + * + * Normally the function allocates the exact space requested unless + * the flags arguments has one of the LISTREP_SPACE_* bits set. + * See the comments for those #defines. + * + * The reference counts of the ListStore and ListSpan (if present) + * pointed to by the initialized repPtr are set to zero. + * Caller has to manage them as necessary. * - * Like NewListInternalRep, but additionally sets an error message on failure. + * Results: + * On success, TCL_OK is returned with *listRepPtr initialized. + * On failure, panics if LISTREP_PANIC_ON_FAIL is set in flags; otherwise + * returns TCL_ERROR with *listRepPtr fields set to NULL. + * + * Side effects: + * The ref counts of the elements in objv are incremented since the + * resulting list now refers to them. * *---------------------------------------------------------------------- */ +static int +ListRepInit( + ListSizeT objc, + Tcl_Obj *const objv[], + int flags, + ListRep *repPtr + ) +{ + ListStore *storePtr; + + /* + * The whole list implementation has an implicit assumption that lenths + * and indices used a signed integer type. Tcl9 API's currently use + * unsigned types. This assert is to remind that need to review code + * when adapting for Tcl9. + */ + LIST_ASSERT(((ListSizeT)-1) < 0); + + storePtr = ListStoreNew(objc, objv, flags); + if (storePtr) { + repPtr->storePtr = storePtr; + if (storePtr->firstUsed == 0) { + repPtr->spanPtr = NULL; + } else { + repPtr->spanPtr = + ListSpanNew(storePtr->firstUsed, storePtr->numUsed); + } + return TCL_OK; + } + /* + * Initialize to keep gcc happy at the call site. Else it complains + * about possibly uninitialized use. + */ + repPtr->storePtr = NULL; + repPtr->spanPtr = NULL; + return TCL_ERROR; +} -static List * -AttemptNewList( +/* + *---------------------------------------------------------------------- + * + * ListRepInitAttempt -- + * + * Creates a list internal rep with space for objc elements. See + * ListRepInit for requirements for parameters (in particular objc must + * be > 0). This function only adds error messages to the interpreter if + * not NULL. + * + * The reference counts of the ListStore and ListSpan (if present) + * pointed to by the initialized repPtr are set to zero. + * Caller has to manage them as necessary. + * + * Results: + * On success, TCL_OK is returned with *listRepPtr initialized. + * On allocation failure, returnes TCL_ERROR with an error message + * in the interpreter if non-NULL. + * + * Side effects: + * The ref counts of the elements in objv are incremented since the + * resulting list now refers to them. + * + *---------------------------------------------------------------------- + */ +static int +ListRepInitAttempt( Tcl_Interp *interp, - size_t objc, - Tcl_Obj *const objv[]) + ListSizeT objc, + Tcl_Obj *const objv[], + ListRep *repPtr) { - List *listRepPtr = NewListInternalRep(objc, objv, 0); + int result = ListRepInit(objc, objv, 0, repPtr); - if (interp != NULL && listRepPtr == NULL) { + if (result != TCL_OK && interp != NULL) { if (objc > LIST_MAX) { - Tcl_SetObjResult(interp, Tcl_ObjPrintf( - "max length of a Tcl list (%d elements) exceeded", - LIST_MAX)); + ListLimitExceededError(interp); } else { - Tcl_SetObjResult(interp, Tcl_ObjPrintf( - "list creation failed: unable to alloc %" TCL_Z_MODIFIER "u bytes", - LIST_SIZE(objc))); + MemoryAllocationError(interp, LIST_SIZE(objc)); } - Tcl_SetErrorCode(interp, "TCL", "MEMORY", NULL); } - return listRepPtr; + return result; } - + +/* + *------------------------------------------------------------------------ + * + * ListRepClone -- + * + * Does a deep clone of an existing ListRep. + * + * Normally the function allocates the exact space needed unless + * the flags arguments has one of the LISTREP_SPACE_* bits set. + * See the comments for those #defines. + * + * Results: + * None. + * + * Side effects: + * The toRepPtr location is initialized with the ListStore and ListSpan + * (if needed) containing a copy of the list elements in fromRepPtr. + * The function will panic if memory cannot be allocated. + * + *------------------------------------------------------------------------ + */ +static void +ListRepClone(ListRep *fromRepPtr, ListRep *toRepPtr, int flags) +{ + Tcl_Obj **fromObjs; + ListSizeT numFrom; + + ListRepElements(fromRepPtr, numFrom, fromObjs); + ListRepInit(numFrom, fromObjs, flags | LISTREP_PANIC_ON_FAIL, toRepPtr); +} + +/* + *------------------------------------------------------------------------ + * + * ListRepUnsharedFreeUnreferenced -- + * + * Frees any Tcl_Obj's from the "in-use" area of the ListStore for a + * ListRep that are not actually references from any lists. + * + * IMPORTANT: this function must not be called on a shared internal + * representation or the internal representation of a shared Tcl_Obj. + * + * Results: + * None. + * + * Side effects: + * The firstUsed and numUsed fields of the ListStore are updated to + * reflect the new "in-use" extent. + * + *------------------------------------------------------------------------ + */ + +static void ListRepUnsharedFreeUnreferenced(const ListRep *repPtr) +{ + ListSizeT count; + ListStore *storePtr; + ListSpan *spanPtr; + + LIST_ASSERT(!ListRepIsShared(repPtr)); + LISTREP_CHECK(repPtr); + + storePtr = repPtr->storePtr; + spanPtr = repPtr->spanPtr; + if (spanPtr == NULL) { + LIST_ASSERT(storePtr->firstUsed == 0); /* Invariant TBD */ + return; + } + + /* Collect garbage at front */ + count = spanPtr->spanStart - storePtr->firstUsed; + LIST_COUNT_ASSERT(count); + if (count > 0) { + ObjArrayDecrRefs(storePtr->slots, storePtr->firstUsed, count); + storePtr->firstUsed = spanPtr->spanStart; + LIST_ASSERT(storePtr->numUsed >= count); + storePtr->numUsed -= count; + } + + /* Collect garbage at back */ + count = (storePtr->firstUsed + storePtr->numUsed) + - (spanPtr->spanStart + spanPtr->spanLength); + LIST_COUNT_ASSERT(count); + if (count > 0) { + ObjArrayDecrRefs( + storePtr->slots, spanPtr->spanStart + spanPtr->spanLength, count); + LIST_ASSERT(storePtr->numUsed >= count); + storePtr->numUsed -= count; + } + + LIST_ASSERT(ListRepStart(repPtr) == storePtr->firstUsed); + LIST_ASSERT(ListRepLength(repPtr) == storePtr->numUsed); + LISTREP_CHECK(repPtr); +} + /* *---------------------------------------------------------------------- * * Tcl_NewListObj -- * - * Creates a new list object and adds values to it. When TCL_MEM_DEBUG is - * defined, 'Tcl_DbNewListObj' is called instead. - * - * Value + * This function is normally called when not debugging: i.e., when + * TCL_MEM_DEBUG is not defined. It creates a new list object from an + * (objc,objv) array: that is, each of the objc elements of the array + * referenced by objv is inserted as an element into a new Tcl object. * - * A new list 'Tcl_Obj' to which is appended values from 'objv', or if - * 'objc' is less than or equal to zero, a list 'Tcl_Obj' having no - * elements. The string representation of the new 'Tcl_Obj' is set to - * NULL. The refCount of the list is 0. + * When TCL_MEM_DEBUG is defined, this function just returns the result + * of calling the debugging version Tcl_DbNewListObj. * - * Effect + * Results: + * A new list object is returned that is initialized from the object + * pointers in objv. If objc is less than or equal to zero, an empty + * object is returned. The new object's string representation is left + * NULL. The resulting new list object has ref count 0. * - * The refCount of each elements in 'objv' is incremented as it is added - * to the list. + * Side effects: + * The ref counts of the elements in objv are incremented since the + * resulting list now refers to them. * *---------------------------------------------------------------------- */ @@ -195,7 +1090,7 @@ AttemptNewList( Tcl_Obj * Tcl_NewListObj( - size_t objc, /* Count of objects referenced by objv. */ + ListSizeT objc, /* Count of objects referenced by objv. */ Tcl_Obj *const objv[]) /* An array of pointers to Tcl objects. */ { return Tcl_DbNewListObj(objc, objv, "unknown", 0); @@ -205,45 +1100,50 @@ Tcl_NewListObj( Tcl_Obj * Tcl_NewListObj( - size_t objc, /* Count of objects referenced by objv. */ + size_t objc, /* Count of objects referenced by objv. */ Tcl_Obj *const objv[]) /* An array of pointers to Tcl objects. */ { - List *listRepPtr; - Tcl_Obj *listPtr; + ListRep listRep; + Tcl_Obj *listObj; - TclNewObj(listPtr); + TclNewObj(listObj); if (objc + 1 <= 1) { - return listPtr; + return listObj; } - /* - * Create the internal rep. - */ - - listRepPtr = NewListInternalRep(objc, objv, 1); + ListRepInit(objc, objv, LISTREP_PANIC_ON_FAIL, &listRep); + ListObjReplaceRepAndInvalidate(listObj, &listRep); - /* - * Now create the object. - */ - - TclInvalidateStringRep(listPtr); - ListSetInternalRep(listPtr, listRepPtr); - return listPtr; + return listObj; } #endif /* if TCL_MEM_DEBUG */ - + /* *---------------------------------------------------------------------- * - * Tcl_DbNewListObj -- + * Tcl_DbNewListObj -- + * + * This function is normally called when debugging: i.e., when + * TCL_MEM_DEBUG is defined. It creates new list objects. It is the same + * as the Tcl_NewListObj function above except that it calls + * Tcl_DbCkalloc directly with the file name and line number from its + * caller. This simplifies debugging since then the [memory active] + * command will report the correct file name and line number when + * reporting objects that haven't been freed. + * + * When TCL_MEM_DEBUG is not defined, this function just returns the + * result of calling Tcl_NewListObj. * - * Like 'Tcl_NewListObj', but it calls Tcl_DbCkalloc directly with the - * file name and line number from its caller. This simplifies debugging - * since the [memory active] command will report the correct file - * name and line number when reporting objects that haven't been freed. + * Results: + * A new list object is returned that is initialized from the object + * pointers in objv. If objc is less than or equal to zero, an empty + * object is returned. The new object's string representation is left + * NULL. The new list object has ref count 0. * - * When TCL_MEM_DEBUG is not defined, 'Tcl_NewListObj' is called instead. + * Side effects: + * The ref counts of the elements in objv are incremented since the + * resulting list now refers to them. * *---------------------------------------------------------------------- */ @@ -252,43 +1152,33 @@ Tcl_NewListObj( Tcl_Obj * Tcl_DbNewListObj( - size_t objc, /* Count of objects referenced by objv. */ + ListSizeT objc, /* Count of objects referenced by objv. */ Tcl_Obj *const objv[], /* An array of pointers to Tcl objects. */ const char *file, /* The name of the source file calling this * function; used for debugging. */ int line) /* Line number in the source file; used for * debugging. */ { - Tcl_Obj *listPtr; - List *listRepPtr; + Tcl_Obj *listObj; + ListRep listRep; - TclDbNewObj(listPtr, file, line); + TclDbNewObj(listObj, file, line); - if (objc + 1 <= 1) { - return listPtr; + if (objc <= 0) { + return listObj; } - /* - * Create the internal rep. - */ - - listRepPtr = NewListInternalRep(objc, objv, 1); - - /* - * Now create the object. - */ + ListRepInit(objc, objv, LISTREP_PANIC_ON_FAIL, &listRep); + ListObjReplaceRepAndInvalidate(listObj, &listRep); - TclInvalidateStringRep(listPtr); - ListSetInternalRep(listPtr, listRepPtr); - - return listPtr; + return listObj; } #else /* if not TCL_MEM_DEBUG */ Tcl_Obj * Tcl_DbNewListObj( - size_t objc, /* Count of objects referenced by objv. */ + size_t objc, /* Count of objects referenced by objv. */ Tcl_Obj *const objv[], /* An array of pointers to Tcl objects. */ TCL_UNUSED(const char *) /*file*/, TCL_UNUSED(int) /*line*/) @@ -296,47 +1186,154 @@ Tcl_DbNewListObj( return Tcl_NewListObj(objc, objv); } #endif /* TCL_MEM_DEBUG */ - + +/* + *------------------------------------------------------------------------ + * + * TclNewListObj2 -- + * + * Create a new Tcl_Obj list comprising of the concatenation of two + * Tcl_Obj* arrays. + * TODO - currently this function is not used within tclListObj but + * need to see if it would be useful in other files that preallocate + * lists and then append. + * + * Results: + * Non-NULL pointer to the allocate Tcl_Obj. + * + * Side effects: + * None. + * + *------------------------------------------------------------------------ + */ +Tcl_Obj * +TclNewListObj2( + ListSizeT objc1, /* Count of objects referenced by objv1. */ + Tcl_Obj *const objv1[], /* First array of pointers to Tcl objects. */ + ListSizeT objc2, /* Count of objects referenced by objv2. */ + Tcl_Obj *const objv2[] /* Second array of pointers to Tcl objects. */ +) +{ + Tcl_Obj *listObj; + ListStore *storePtr; + ListSizeT objc = objc1 + objc2; + + listObj = Tcl_NewListObj(objc, NULL); + if (objc == 0) { + return listObj; /* An empty object */ + } + LIST_ASSERT_TYPE(listObj); + + storePtr = ListObjStorePtr(listObj); + + LIST_ASSERT(ListObjSpanPtr(listObj) == NULL); + LIST_ASSERT(storePtr->firstUsed == 0); + LIST_ASSERT(storePtr->numUsed == 0); + LIST_ASSERT(storePtr->numAllocated >= objc); + + if (objc1) { + ObjArrayCopy(storePtr->slots, objc1, objv1); + } + if (objc2) { + ObjArrayCopy(&storePtr->slots[objc1], objc2, objv2); + } + storePtr->numUsed = objc; + return listObj; +} + /* *---------------------------------------------------------------------- * - * Tcl_SetListObj -- + * TclListObjGetRep -- + * + * This function returns a copy of the ListRep stored + * as the internal representation of an object. The reference + * counts of the (ListStore, ListSpan) contained in the representation + * are NOT incremented. * - * Like 'Tcl_NewListObj', but operates on an existing 'Tcl_Obj'instead of - * creating a new one. + * Results: + * The return value is normally TCL_OK; in this case *listRepP + * is set to a copy of the descriptor stored as the internal + * representation of the Tcl_Obj containing a list. if listPtr does not + * refer to a list object and the object can not be converted to one, + * TCL_ERROR is returned and an error message will be left in the + * interpreter's result if interp is not NULL. * + * Side effects: + * The possible conversion of the object referenced by listPtr + * to a list object. *repPtr is initialized to the internal rep + * if result is TCL_OK, or set to NULL on error. *---------------------------------------------------------------------- */ +static int +TclListObjGetRep( + Tcl_Interp *interp, /* Used to report errors if not NULL. */ + Tcl_Obj *listObj, /* List object for which an element array is + * to be returned. */ + ListRep *repPtr) /* Location to store descriptor */ +{ + if (!TclHasInternalRep(listObj, &tclListType)) { + int result; + result = SetListFromAny(interp, listObj); + if (result != TCL_OK) { + /* Init to keep gcc happy wrt uninitialized fields at call site */ + repPtr->storePtr = NULL; + repPtr->spanPtr = NULL; + return result; + } + } + ListObjGetRep(listObj, repPtr); + LISTREP_CHECK(repPtr); + return TCL_OK; +} + +/* + *---------------------------------------------------------------------- + * + * Tcl_SetListObj -- + * + * Modify an object to be a list containing each of the objc elements of + * the object array referenced by objv. + * + * Results: + * None. + * + * Side effects: + * The object is made a list object and is initialized from the object + * pointers in objv. If objc is less than or equal to zero, an empty + * object is returned. The new object's string representation is left + * NULL. The ref counts of the elements in objv are incremented since the + * list now refers to them. The object's old string and internal + * representations are freed and its type is set NULL. + * + *---------------------------------------------------------------------- + */ void Tcl_SetListObj( Tcl_Obj *objPtr, /* Object whose internal rep to init. */ - size_t objc, /* Count of objects referenced by objv. */ + size_t objc, /* Count of objects referenced by objv. */ Tcl_Obj *const objv[]) /* An array of pointers to Tcl objects. */ { - List *listRepPtr; - if (Tcl_IsShared(objPtr)) { Tcl_Panic("%s called with shared object", "Tcl_SetListObj"); } /* - * Free any old string rep and any internal rep for the old type. - */ - - TclFreeInternalRep(objPtr); - TclInvalidateStringRep(objPtr); - - /* * Set the object's type to "list" and initialize the internal rep. * However, if there are no elements to put in the list, just give the - * object an empty string rep and a NULL type. + * object an empty string rep and a NULL type. NOTE ListRepInit must + * not be called with objc == 0! */ - if (objc > 0) { - listRepPtr = NewListInternalRep(objc, objv, 1); - ListSetInternalRep(objPtr, listRepPtr); + if (objc + 1 > 1) { + ListRep listRep; + /* TODO - perhaps ask for extra space? */ + ListRepInit(objc, objv, LISTREP_PANIC_ON_FAIL, &listRep); + ListObjReplaceRepAndInvalidate(objPtr, &listRep); } else { + TclFreeInternalRep(objPtr); + TclInvalidateStringRep(objPtr); Tcl_InitStringRep(objPtr, NULL, 0); } } @@ -346,20 +1343,18 @@ Tcl_SetListObj( * * TclListObjCopy -- * - * Creates a new 'Tcl_Obj' which is a pure copy of a list value. This - * provides for the C level a counterpart of the [lrange $list 0 end] - * command, while using internals details to be as efficient as possible. - * - * Value - * - * The address of the new 'Tcl_Obj' which shares its internal - * representation with 'listPtr', and whose refCount is 0. If 'listPtr' - * is not actually a list, the value is NULL, and an error message is left - * in 'interp' if it is not NULL. + * Makes a "pure list" copy of a list value. This provides for the C + * level a counterpart of the [lrange $list 0 end] command, while using + * internals details to be as efficient as possible. * - * Effect + * Results: + * Normally returns a pointer to a new Tcl_Obj, that contains the same + * list value as *listPtr does. The returned Tcl_Obj has a refCount of + * zero. If *listPtr does not hold a list, NULL is returned, and if + * interp is non-NULL, an error message is recorded there. * - * 'listPtr' is converted to a list if it isn't one already. + * Side effects: + * None. * *---------------------------------------------------------------------- */ @@ -367,137 +1362,254 @@ Tcl_SetListObj( Tcl_Obj * TclListObjCopy( Tcl_Interp *interp, /* Used to report errors if not NULL. */ - Tcl_Obj *listPtr) /* List object for which an element array is + Tcl_Obj *listObj) /* List object for which an element array is * to be returned. */ { - Tcl_Obj *copyPtr; - List *listRepPtr; + Tcl_Obj *copyObj; - ListGetInternalRep(listPtr, listRepPtr); - if (NULL == listRepPtr) { - if (SetListFromAny(interp, listPtr) != TCL_OK) { + if (!TclHasInternalRep(listObj, &tclListType)) { + if (SetListFromAny(interp, listObj) != TCL_OK) { return NULL; } } - TclNewObj(copyPtr); - TclInvalidateStringRep(copyPtr); - DupListInternalRep(listPtr, copyPtr); - return copyPtr; + TclNewObj(copyObj); + TclInvalidateStringRep(copyObj); + DupListInternalRep(listObj, copyObj); + return copyObj; } /* - *---------------------------------------------------------------------- + *------------------------------------------------------------------------ * - * TclListObjRange -- + * ListRepRange -- * - * Makes a slice of a list value. - * *listPtr must be known to be a valid list. + * Initializes a ListRep as a range within the passed ListRep. + * The range limits are clamped to the list boundaries. * * Results: - * Returns a pointer to the sliced list. - * This may be a new object or the same object if not shared. + * None. * * Side effects: - * The possible conversion of the object referenced by listPtr - * to a list object. - * - *---------------------------------------------------------------------- + * The ListStore and ListSpan referenced by in the returned ListRep + * may or may not be the same as those passed in. For example, the + * ListStore may differ because the range is small enough that a new + * ListStore is more memory-optimal. The ListSpan may differ because + * it is NULL or shared. Regardless, reference counts on the returned + * values are not incremented. Generally, ListObjReplaceRepAndInvalidate may be + * used to store the new ListRep back into an object or a ListRepIncRefs + * followed by ListRepDecrRefs to free in case of errors. + * TODO WARNING:- this is not a very clean interface and easy for caller + * to get wrong. Better change it to pass in the source ListObj + * + *------------------------------------------------------------------------ */ - -Tcl_Obj * -TclListObjRange( - Tcl_Obj *listPtr, /* List object to take a range from. */ - size_t fromIdx, /* Index of first element to include. */ - size_t toIdx) /* Index of last element to include. */ +static void +ListRepRange( + ListRep *srcRepPtr, /* Contains source of the range */ + ListSizeT rangeStart, /* Index of first element to include */ + ListSizeT rangeEnd, /* Index of last element to include */ + int preserveSrcRep, /* If true, srcRepPtr contents must not be + modified (generally because a shared Tcl_Obj + references it) */ + ListRep *rangeRepPtr) /* Output. Must NOT be == srcRepPtr */ { - Tcl_Obj **elemPtrs; - size_t listLen, i, newLen; - List *listRepPtr; + Tcl_Obj **srcElems; + ListSizeT numSrcElems = ListRepLength(srcRepPtr); + ListSizeT rangeLen; + int doSpan; - TclListObjGetElementsM(NULL, listPtr, &listLen, &elemPtrs); + LISTREP_CHECK(srcRepPtr); - if (fromIdx == TCL_INDEX_NONE) { - fromIdx = 0; + /* Take the opportunity to garbage collect */ + /* TODO - we probably do not need the preserveSrcRep here unlike later */ + if (!preserveSrcRep) { + ListRepFreeUnreferenced(srcRepPtr); } - if (toIdx + 1 >= listLen + 1) { - toIdx = listLen-1; + + if (rangeStart < 0) { + rangeStart = 0; } - if (fromIdx + 1 > toIdx + 1) { - Tcl_Obj *obj; - TclNewObj(obj); - return obj; + if (rangeEnd >= numSrcElems) { + rangeEnd = numSrcElems - 1; } - - newLen = toIdx - fromIdx + 1; - - if (Tcl_IsShared(listPtr) || - ((ListRepPtr(listPtr)->refCount > 1))) { - return Tcl_NewListObj(newLen, &elemPtrs[fromIdx]); + if (rangeStart > rangeEnd) { + /* Empty list of capacity 1. */ + ListRepInit(1, NULL, LISTREP_PANIC_ON_FAIL, rangeRepPtr); + return; } - /* - * In-place is possible. - */ + rangeLen = rangeEnd - rangeStart + 1; /* - * Even if nothing below cause any changes, we still want the - * string-canonizing effect of [lrange 0 end]. + * We can create a range one of three ways: + * (1) Use a ListSpan referencing the current ListStore + * (2) Creating a new ListStore + * (3) Removing all elements outside the range in the current ListStore + * Option (3) may only be done if caller has not disallowed it AND + * the ListStore is not shared. + * + * The choice depends on heuristics related to speed and memory. + * TODO - heuristics below need to be measured and tuned. + * + * Note: Even if nothing below cause any changes, we still want the + * string-canonizing effect of [lrange 0 end] so the Tcl_Obj should not + * be returned as is even if the range encompasses the whole list. */ + doSpan = ListSpanMerited(rangeLen, + srcRepPtr->storePtr->numUsed, + srcRepPtr->storePtr->numAllocated); + + if (doSpan) { + /* Option 1 - because span would be most efficient */ + ListSizeT spanStart = ListRepStart(srcRepPtr) + rangeStart; + if (!preserveSrcRep && srcRepPtr->spanPtr + && srcRepPtr->spanPtr->refCount <= 1) { + /* If span is not shared reuse it */ + srcRepPtr->spanPtr->spanStart = spanStart; + srcRepPtr->spanPtr->spanLength = rangeLen; + *rangeRepPtr = *srcRepPtr; + } else { + /* Span not present or is shared - Allocate a new span */ + rangeRepPtr->storePtr = srcRepPtr->storePtr; + rangeRepPtr->spanPtr = ListSpanNew(spanStart, rangeLen); + } + /* + * We have potentially created a new internal representation that + * references the same storage as srcRep but not yet incremented its + * reference count. So do NOT call freezombies if preserveSrcRep + * is mandated. + */ + if (!preserveSrcRep) { + ListRepFreeUnreferenced(rangeRepPtr); + } + } else if (preserveSrcRep || ListRepIsShared(srcRepPtr)) { + /* Option 2 - span or modification in place not allowed/desired */ + ListRepElements(srcRepPtr, numSrcElems, srcElems); + /* TODO - allocate extra space? */ + ListRepInit(rangeLen, + &srcElems[rangeStart], + LISTREP_PANIC_ON_FAIL, + rangeRepPtr); + } else { + /* + * Option 3 - modify in place. Note that because of the invariant + * that spanless list stores must start at 0, we have to move + * everything to the front. + * TODO - perhaps if a span already exists, no need to move to front? + * or maybe no need to move all the way to the front? + * TODO - if range is small relative to allocation, allocate new? + */ + ListSizeT numAfterRangeEnd; - TclInvalidateStringRep(listPtr); - - /* - * Delete elements that should not be included. - */ + /* Asserts follow from call to ListRepFreeUnreferenced earlier */ + LIST_ASSERT(!preserveSrcRep); + LIST_ASSERT(!ListRepIsShared(srcRepPtr)); + LIST_ASSERT(ListRepStart(srcRepPtr) == srcRepPtr->storePtr->firstUsed); + LIST_ASSERT(ListRepLength(srcRepPtr) == srcRepPtr->storePtr->numUsed); - for (i = 0; i < fromIdx; i++) { - TclDecrRefCount(elemPtrs[i]); - } - for (i = toIdx + 1; i < (size_t)listLen; i++) { - TclDecrRefCount(elemPtrs[i]); - } + ListRepElements(srcRepPtr, numSrcElems, srcElems); - if (fromIdx > 0) { - memmove(elemPtrs, &elemPtrs[fromIdx], - (size_t) newLen * sizeof(Tcl_Obj*)); + /* Free leading elements outside range */ + if (rangeStart != 0) { + ObjArrayDecrRefs(srcElems, 0, rangeStart); + } + /* Ditto for trailing */ + numAfterRangeEnd = numSrcElems - (rangeEnd + 1); + LIST_ASSERT(numAfterRangeEnd + >= 0); /* Because numSrcElems > rangeEnd earlier */ + if (numAfterRangeEnd != 0) { + ObjArrayDecrRefs(srcElems, rangeEnd + 1, numAfterRangeEnd); + } + memmove(&srcRepPtr->storePtr->slots[0], + &srcRepPtr->storePtr + ->slots[srcRepPtr->storePtr->firstUsed + rangeStart], + rangeLen * sizeof(Tcl_Obj *)); + srcRepPtr->storePtr->firstUsed = 0; + srcRepPtr->storePtr->numUsed = rangeLen; + srcRepPtr->storePtr->flags = 0; + rangeRepPtr->storePtr = srcRepPtr->storePtr; /* Note no incr ref */ + rangeRepPtr->spanPtr = NULL; } - listRepPtr = ListRepPtr(listPtr); - listRepPtr->elemCount = newLen; + /* TODO - call freezombies here if !preserveSrcRep? */ - return listPtr; + /* Note ref counts intentionally not incremented */ + LISTREP_CHECK(rangeRepPtr); + return; } - + /* *---------------------------------------------------------------------- * - * Tcl_ListObjGetElements -- - * - * Retreive the elements in a list 'Tcl_Obj'. + * TclListObjRange -- * - * Value + * Makes a slice of a list value. + * *listObj must be known to be a valid list. * - * TCL_OK + * Results: + * Returns a pointer to the sliced list. + * This may be a new object or the same object if not shared. + * Returns NULL if passed listObj was not a list and could not be + * converted to one. * - * A count of list elements is stored, 'objcPtr', And a pointer to the - * array of elements in the list is stored in 'objvPtr'. + * Side effects: + * The possible conversion of the object referenced by listPtr + * to a list object. * - * The elements accessible via 'objvPtr' should be treated as readonly - * and the refCount for each object is _not_ incremented; the caller - * must do that if it holds on to a reference. Furthermore, the - * pointer and length returned by this function may change as soon as - * any function is called on the list object. Be careful about - * retaining the pointer in a local data structure. + *---------------------------------------------------------------------- + */ + +Tcl_Obj * +TclListObjRange( + Tcl_Obj *listObj, /* List object to take a range from. */ + size_t rangeStart, /* Index of first element to include. */ + size_t rangeEnd) /* Index of last element to include. */ +{ + ListRep listRep; + ListRep resultRep; + + int isShared; + if (TclListObjGetRep(NULL, listObj, &listRep) != TCL_OK) + return NULL; + + isShared = Tcl_IsShared(listObj); + + ListRepRange(&listRep, rangeStart, rangeEnd, isShared, &resultRep); + + if (isShared) { + TclNewObj(listObj); + } + ListObjReplaceRepAndInvalidate(listObj, &resultRep); + return listObj; +} + +/* + *---------------------------------------------------------------------- * - * TCL_ERROR + * Tcl_ListObjGetElements -- * - * 'listPtr' is not a valid list. An error message is left in the - * interpreter's result if 'interp' is not NULL. + * This function returns an (objc,objv) array of the elements in a list + * object. * - * Effect + * Results: + * The return value is normally TCL_OK; in this case *objcPtr is set to + * the count of list elements and *objvPtr is set to a pointer to an + * array of (*objcPtr) pointers to each list element. If listPtr does not + * refer to a list object and the object can not be converted to one, + * TCL_ERROR is returned and an error message will be left in the + * interpreter's result if interp is not NULL. + * + * The objects referenced by the returned array should be treated as + * readonly and their ref counts are _not_ incremented; the caller must + * do that if it holds on to a reference. Furthermore, the pointer and + * length returned by this function may change as soon as any function is + * called on the list object; be careful about retaining the pointer in a + * local data structure. * - * 'listPtr' is converted to a list object if it isn't one already. + * Side effects: + * The possible conversion of the object referenced by listPtr + * to a list object. * *---------------------------------------------------------------------- */ @@ -506,35 +1618,18 @@ TclListObjRange( int Tcl_ListObjGetElements( Tcl_Interp *interp, /* Used to report errors if not NULL. */ - Tcl_Obj *listPtr, /* List object for which an element array is + Tcl_Obj *objPtr, /* List object for which an element array is * to be returned. */ size_t *objcPtr, /* Where to store the count of objects * referenced by objv. */ Tcl_Obj ***objvPtr) /* Where to store the pointer to an array of * pointers to the list's objects. */ { - List *listRepPtr; - - ListGetInternalRep(listPtr, listRepPtr); - - if (listRepPtr == NULL) { - int result; - size_t length; + ListRep listRep; - (void) Tcl_GetStringFromObj(listPtr, &length); - if (length == 0) { - *objcPtr = 0; - *objvPtr = NULL; - return TCL_OK; - } - result = SetListFromAny(interp, listPtr); - if (result != TCL_OK) { - return result; - } - ListGetInternalRep(listPtr, listRepPtr); - } - *objcPtr = listRepPtr->elemCount; - *objvPtr = listRepPtr->elements; + if (TclListObjGetRep(interp, objPtr, &listRep) != TCL_OK) + return TCL_ERROR; + ListRepElements(&listRep, *objcPtr, *objvPtr); return TCL_OK; } @@ -543,27 +1638,20 @@ Tcl_ListObjGetElements( * * Tcl_ListObjAppendList -- * - * Appends the elements of elemListPtr to those of listPtr. - * - * Value - * - * TCL_OK - * - * Success. + * This function appends the elements in the list fromObj + * to toObj. toObj must not be shared else the function will panic. * - * TCL_ERROR - * - * 'listPtr' or 'elemListPtr' are not valid lists. An error - * message is left in the interpreter's result if 'interp' is not NULL. - * - * Effect + * Results: + * The return value is normally TCL_OK. If fromObj or toObj do not + * refer to list values, TCL_ERROR is returned and an error message is + * left in the interpreter's result if interp is not NULL. * - * The reference count of each element of 'elemListPtr' as it is added to - * 'listPtr'. 'listPtr' and 'elemListPtr' are converted to 'tclListType' - * if they are not already. Appending the new elements may cause the - * array of element pointers in 'listObj' to grow. If any objects are - * appended to 'listPtr'. Any preexisting string representation of - * 'listPtr' is invalidated. + * Side effects: + * The reference counts of the elements in fromObj are incremented + * since the list now refers to them. toObj and fromObj are + * converted, if necessary, to list objects. Also, appending the new + * elements may cause toObj's array of element pointers to grow. + * toObj's old string representation, if any, is invalidated. * *---------------------------------------------------------------------- */ @@ -571,21 +1659,17 @@ Tcl_ListObjGetElements( int Tcl_ListObjAppendList( Tcl_Interp *interp, /* Used to report errors if not NULL. */ - Tcl_Obj *listPtr, /* List object to append elements to. */ - Tcl_Obj *elemListPtr) /* List obj with elements to append. */ + Tcl_Obj *toObj, /* List object to append elements to. */ + Tcl_Obj *fromObj) /* List obj with elements to append. */ { size_t objc; Tcl_Obj **objv; - if (Tcl_IsShared(listPtr)) { + if (Tcl_IsShared(toObj)) { Tcl_Panic("%s called with shared object", "Tcl_ListObjAppendList"); } - /* - * Pull the elements to append from elemListPtr. - */ - - if (TCL_OK != TclListObjGetElementsM(interp, elemListPtr, &objc, &objv)) { + if (TclListObjGetElementsM(interp, fromObj, &objc, &objv) != TCL_OK) { return TCL_ERROR; } @@ -594,249 +1678,241 @@ Tcl_ListObjAppendList( * Delete zero existing elements. */ - return Tcl_ListObjReplace(interp, listPtr, LIST_MAX, 0, objc, objv); + return TclListObjAppendElements(interp, toObj, objc, objv); } - + /* - *---------------------------------------------------------------------- - * - * Tcl_ListObjAppendElement -- - * - * Like 'Tcl_ListObjAppendList', but Appends a single value to a list. - * - * Value + *------------------------------------------------------------------------ * - * TCL_OK + * TclListObjAppendElements -- * - * 'objPtr' is appended to the elements of 'listPtr'. + * Appends multiple elements to a Tcl_Obj list object. If + * the passed Tcl_Obj is not a list object, it will be converted to one + * and an error raised if the conversion fails. * - * TCL_ERROR + * The Tcl_Obj must not be shared though the internal representation + * may be. * - * listPtr does not refer to a list object and the object can not be - * converted to one. An error message will be left in the - * interpreter's result if interp is not NULL. - * - * Effect + * Results: + * On success, TCL_OK is returned with the specified elements appended. + * On failure, TCL_ERROR is returned with an error message in the + * interpreter if not NULL. * - * If 'listPtr' is not already of type 'tclListType', it is converted. - * The 'refCount' of 'objPtr' is incremented as it is added to 'listPtr'. - * Appending the new element may cause the the array of element pointers - * in 'listObj' to grow. Any preexisting string representation of - * 'listPtr' is invalidated. + * Side effects: + * None. * - *---------------------------------------------------------------------- + *------------------------------------------------------------------------ */ - -int -Tcl_ListObjAppendElement( + int TclListObjAppendElements ( Tcl_Interp *interp, /* Used to report errors if not NULL. */ - Tcl_Obj *listPtr, /* List object to append objPtr to. */ - Tcl_Obj *objPtr) /* Object to append to listPtr's list. */ + Tcl_Obj *toObj, /* List object to append */ + size_t elemCount, /* Number of elements in elemObjs[] */ + Tcl_Obj * const elemObjv[]) /* Objects to append to toObj's list. */ { - List *listRepPtr, *newPtr = NULL; - size_t numElems, numRequired; - int needGrow, isShared, attempt; + ListRep listRep; + Tcl_Obj **toObjv; + size_t toLen; + size_t finalLen; - if (Tcl_IsShared(listPtr)) { - Tcl_Panic("%s called with shared object", "Tcl_ListObjAppendElement"); + if (Tcl_IsShared(toObj)) { + Tcl_Panic("%s called with shared object", "TclListObjAppendElements"); } - ListGetInternalRep(listPtr, listRepPtr); - if (listRepPtr == NULL) { - int result; - size_t length; - - (void) Tcl_GetStringFromObj(listPtr, &length); - if (length == 0) { - Tcl_SetListObj(listPtr, 1, &objPtr); - return TCL_OK; - } - result = SetListFromAny(interp, listPtr); - if (result != TCL_OK) { - return result; - } - ListGetInternalRep(listPtr, listRepPtr); - } + if (TclListObjGetRep(interp, toObj, &listRep) != TCL_OK) + return TCL_ERROR; /* Cannot be converted to a list */ - numElems = listRepPtr->elemCount; - numRequired = numElems + 1 ; - needGrow = (numRequired > listRepPtr->maxElemCount); - isShared = (listRepPtr->refCount > 1); + if (elemCount == 0) + return TCL_OK; /* Nothing to do. Note AFTER check for list above */ - if (numRequired > LIST_MAX) { - if (interp != NULL) { - Tcl_SetObjResult(interp, Tcl_ObjPrintf( - "max length of a Tcl list (%d elements) exceeded", - LIST_MAX)); - Tcl_SetErrorCode(interp, "TCL", "MEMORY", NULL); - } - return TCL_ERROR; + ListRepElements(&listRep, toLen, toObjv); + if (elemCount > LIST_MAX || toLen > (LIST_MAX - elemCount)) { + return ListLimitExceededError(interp); } - if (needGrow && !isShared) { + finalLen = toLen + elemCount; + if (!ListRepIsShared(&listRep)) { /* - * Need to grow + unshared internalrep => try to realloc + * Reuse storage if possible. Even if too small, realloc-ing instead + * of creating a new ListStore will save us on manipulating Tcl_Obj + * reference counts on the elements which is a substantial cost + * if the list is not small. */ + size_t numTailFree; - attempt = 2 * numRequired; - if (attempt <= LIST_MAX) { - newPtr = (List *)Tcl_AttemptRealloc(listRepPtr, LIST_SIZE(attempt)); - } - if (newPtr == NULL) { - attempt = numRequired + 1 + TCL_MIN_ELEMENT_GROWTH; - if (attempt > LIST_MAX) { - attempt = LIST_MAX; - } - newPtr = (List *)Tcl_AttemptRealloc(listRepPtr, LIST_SIZE(attempt)); - } - if (newPtr == NULL) { - attempt = numRequired; - newPtr = (List *)Tcl_AttemptRealloc(listRepPtr, LIST_SIZE(attempt)); - } - if (newPtr) { - listRepPtr = newPtr; - listRepPtr->maxElemCount = attempt; - needGrow = 0; - } - } - if (isShared || needGrow) { - Tcl_Obj **dst, **src = listRepPtr->elements; + ListRepFreeUnreferenced(&listRep); /* Collect garbage before checking room */ - /* - * Either we have a shared internalrep and we must copy to write, or we - * need to grow and realloc attempts failed. Attempt internalrep copy. - */ + LIST_ASSERT(ListRepStart(&listRep) == listRep.storePtr->firstUsed); + LIST_ASSERT(ListRepLength(&listRep) == listRep.storePtr->numUsed); + LIST_ASSERT(toLen == listRep.storePtr->numUsed); - attempt = 2 * numRequired; - newPtr = AttemptNewList(NULL, attempt, NULL); - if (newPtr == NULL) { - attempt = numRequired + 1 + TCL_MIN_ELEMENT_GROWTH; - if (attempt > LIST_MAX) { - attempt = LIST_MAX; + if (finalLen > (size_t)listRep.storePtr->numAllocated) { + ListStore *newStorePtr; + newStorePtr = ListStoreReallocate(listRep.storePtr, finalLen); + if (newStorePtr == NULL) { + return MemoryAllocationError(interp, LIST_SIZE(finalLen)); } - newPtr = AttemptNewList(NULL, attempt, NULL); - } - if (newPtr == NULL) { - attempt = numRequired; - newPtr = AttemptNewList(interp, attempt, NULL); - } - if (newPtr == NULL) { + LIST_ASSERT(newStorePtr->numAllocated >= finalLen); + listRep.storePtr = newStorePtr; /* - * All growth attempts failed; throw the error. + * WARNING: at this point the Tcl_Obj internal rep potentially + * points to freed storage if the reallocation returned a + * different location. Overwrite it to bring it back in sync. */ - - return TCL_ERROR; + ListObjStompRep(toObj, &listRep); } - - dst = newPtr->elements; - newPtr->refCount++; - newPtr->canonicalFlag = listRepPtr->canonicalFlag; - newPtr->elemCount = listRepPtr->elemCount; - - if (isShared) { - /* - * The original internalrep must remain undisturbed. Copy into the new - * one and bump refcounts - */ - while (numElems--) { - *dst = *src++; - Tcl_IncrRefCount(*dst++); - } - listRepPtr->refCount--; - } else { - /* - * Old internalrep to be freed, re-use refCounts. - */ - - memcpy(dst, src, numElems * sizeof(Tcl_Obj *)); - Tcl_Free(listRepPtr); + LIST_ASSERT(listRep.storePtr->numAllocated >= finalLen); + /* Current store big enough */ + numTailFree = ListRepNumFreeTail(&listRep); + LIST_ASSERT((numTailFree + listRep.storePtr->firstUsed) + >= elemCount); /* Total free */ + if (numTailFree < elemCount) { + /* Not enough room at back. Move some to front */ + ListSizeT shiftCount = elemCount - numTailFree; + /* Divide remaining space between front and back */ + shiftCount += (listRep.storePtr->numAllocated - finalLen) / 2; + LIST_ASSERT(shiftCount <= listRep.storePtr->firstUsed); + if (shiftCount) + ListRepUnsharedShiftDown(&listRep, shiftCount); } - listRepPtr = newPtr; - } - ListResetInternalRep(listPtr, listRepPtr); - listRepPtr->refCount++; - TclFreeInternalRep(listPtr); - ListSetInternalRep(listPtr, listRepPtr); - listRepPtr->refCount--; - - /* - * Add objPtr to the end of listPtr's array of element pointers. Increment - * the ref count for the (now shared) objPtr. - */ + ObjArrayCopy(&listRep.storePtr->slots[ListRepStart(&listRep) + + ListRepLength(&listRep)], + elemCount, + elemObjv); + listRep.storePtr->numUsed = finalLen; + if (listRep.spanPtr) { + LIST_ASSERT(listRep.spanPtr->spanStart + == listRep.storePtr->firstUsed); + listRep.spanPtr->spanLength = finalLen; + } + LIST_ASSERT(ListRepStart(&listRep) == listRep.storePtr->firstUsed); + LIST_ASSERT(ListRepLength(&listRep) == finalLen); + LISTREP_CHECK(&listRep); - listRepPtr->elements[listRepPtr->elemCount] = objPtr; - Tcl_IncrRefCount(objPtr); - listRepPtr->elemCount++; + ListObjReplaceRepAndInvalidate(toObj, &listRep); + return TCL_OK; + } /* - * Invalidate any old string representation since the list's internal - * representation has changed. + * Have to make a new list rep, either shared or no room in old one. + * If the old list did not have a span (all elements at front), do + * not leave space in the front either, assuming all appends and no + * prepends. */ + if (ListRepInit(finalLen, + NULL, + listRep.spanPtr ? LISTREP_SPACE_FAVOR_BACK + : LISTREP_SPACE_ONLY_BACK, + &listRep) + != TCL_OK) { + return TCL_ERROR; + } + LIST_ASSERT(listRep.storePtr->numAllocated >= finalLen); - TclInvalidateStringRep(listPtr); + if (toLen) { + ObjArrayCopy(ListRepSlotPtr(&listRep, 0), toLen, toObjv); + } + ObjArrayCopy(ListRepSlotPtr(&listRep, toLen), elemCount, elemObjv); + listRep.storePtr->numUsed = finalLen; + if (listRep.spanPtr) { + LIST_ASSERT(listRep.spanPtr->spanStart == listRep.storePtr->firstUsed); + listRep.spanPtr->spanLength = finalLen; + } + LISTREP_CHECK(&listRep); + ListObjReplaceRepAndInvalidate(toObj, &listRep); return TCL_OK; } - + /* *---------------------------------------------------------------------- * - * Tcl_ListObjIndex -- + * Tcl_ListObjAppendElement -- * - * Retrieve a pointer to the element of 'listPtr' at 'index'. The index - * of the first element is 0. + * This function is a special purpose version of Tcl_ListObjAppendList: + * it appends a single object referenced by elemObj to the list object + * referenced by toObj. If toObj is not already a list object, an + * attempt will be made to convert it to one. * - * Value + * Results: + * The return value is normally TCL_OK; in this case elemObj is added to + * the end of toObj's list. If toObj does not refer to a list object + * and the object can not be converted to one, TCL_ERROR is returned and + * an error message will be left in the interpreter's result if interp is + * not NULL. * - * TCL_OK + * Side effects: + * The ref count of elemObj is incremented since the list now refers to + * it. toObj will be converted, if necessary, to a list object. Also, + * appending the new element may cause listObj's array of element + * pointers to grow. toObj's old string representation, if any, is + * invalidated. * - * A pointer to the element at 'index' is stored in 'objPtrPtr'. If - * 'index' is out of range, NULL is stored in 'objPtrPtr'. This - * object should be treated as readonly and its 'refCount' is _not_ - * incremented. The caller must do that if it holds on to the - * reference. + *---------------------------------------------------------------------- + */ + +int +Tcl_ListObjAppendElement( + Tcl_Interp *interp, /* Used to report errors if not NULL. */ + Tcl_Obj *toObj, /* List object to append elemObj to. */ + Tcl_Obj *elemObj) /* Object to append to toObj's list. */ +{ + /* + * TODO - compare perf with 8.6 to see if worth optimizing single + * element case + */ + return TclListObjAppendElements(interp, toObj, 1, &elemObj); +} + +/* + *---------------------------------------------------------------------- * - * TCL_ERROR + * Tcl_ListObjIndex -- * - * 'listPtr' is not a valid list. An an error message is left in the - * interpreter's result if 'interp' is not NULL. + * This function returns a pointer to the index'th object from the list + * referenced by listPtr. The first element has index 0. If index is + * negative or greater than or equal to the number of elements in the + * list, a NULL is returned. If listPtr is not a list object, an attempt + * will be made to convert it to a list. * - * Effect + * Results: + * The return value is normally TCL_OK; in this case objPtrPtr is set to + * the Tcl_Obj pointer for the index'th list element or NULL if index is + * out of range. This object should be treated as readonly and its ref + * count is _not_ incremented; the caller must do that if it holds on to + * the reference. If listPtr does not refer to a list and can't be + * converted to one, TCL_ERROR is returned and an error message is left + * in the interpreter's result if interp is not NULL. * - * If 'listPtr' is not already of type 'tclListType', it is converted. + * Side effects: + * listPtr will be converted, if necessary, to a list object. * *---------------------------------------------------------------------- */ int Tcl_ListObjIndex( - Tcl_Interp *interp, /* Used to report errors if not NULL. */ - Tcl_Obj *listPtr, /* List object to index into. */ - size_t index, /* Index of element to return. */ - Tcl_Obj **objPtrPtr) /* The resulting Tcl_Obj* is stored here. */ + Tcl_Interp *interp, /* Used to report errors if not NULL. */ + Tcl_Obj *listObj, /* List object to index into. */ + size_t index, /* Index of element to return. */ + Tcl_Obj **objPtrPtr) /* The resulting Tcl_Obj* is stored here. */ { - List *listRepPtr; + Tcl_Obj **elemObjs; + size_t numElems; - ListGetInternalRep(listPtr, listRepPtr); - if (listRepPtr == NULL) { - int result; - size_t length; - - (void) Tcl_GetStringFromObj(listPtr, &length); - if (length == 0) { - *objPtrPtr = NULL; - return TCL_OK; - } - result = SetListFromAny(interp, listPtr); - if (result != TCL_OK) { - return result; - } - ListGetInternalRep(listPtr, listRepPtr); + /* + * TODO + * Unlike the original list code, this does not optimize for lindex'ing + * an empty string when the internal rep is not already a list. On the + * other hand, this code will be faster for the case where the object + * is currently a dict. Benchmark the two cases. + */ + if (TclListObjGetElementsM(interp, listObj, &numElems, &elemObjs) + != TCL_OK) { + return TCL_ERROR; } - - if (index >= listRepPtr->elemCount) { + if (index >= numElems) { *objPtrPtr = NULL; } else { - *objPtrPtr = listRepPtr->elements[index]; + *objPtrPtr = elemObjs[index]; } return TCL_OK; @@ -847,20 +1923,19 @@ Tcl_ListObjIndex( * * Tcl_ListObjLength -- * - * Retrieve the number of elements in a list. + * This function returns the number of elements in a list object. If the + * object is not already a list object, an attempt will be made to + * convert it to one. * - * Value - * - * TCL_OK - * - * A count of list elements is stored at the address provided by - * 'intPtr'. If 'listPtr' is not already of type 'tclListPtr', it is - * converted. - * - * TCL_ERROR + * Results: + * The return value is normally TCL_OK; in this case *intPtr will be set + * to the integer count of list elements. If listPtr does not refer to a + * list object and the object can not be converted to one, TCL_ERROR is + * returned and an error message will be left in the interpreter's result + * if interp is not NULL. * - * 'listPtr' is not a valid list. An error message will be left in - * the interpreter's result if 'interp' is not NULL. + * Side effects: + * The possible conversion of the argument object to a list object. * *---------------------------------------------------------------------- */ @@ -868,337 +1943,498 @@ Tcl_ListObjIndex( #undef Tcl_ListObjLength int Tcl_ListObjLength( - Tcl_Interp *interp, /* Used to report errors if not NULL. */ - Tcl_Obj *listPtr, /* List object whose #elements to return. */ - size_t *intPtr) /* The resulting length is stored here. */ + Tcl_Interp *interp, /* Used to report errors if not NULL. */ + Tcl_Obj *listObj, /* List object whose #elements to return. */ + size_t *lenPtr) /* The resulting int is stored here. */ { - List *listRepPtr; - - ListGetInternalRep(listPtr, listRepPtr); - if (listRepPtr == NULL) { - int result; - size_t length; + ListRep listRep; - (void) Tcl_GetStringFromObj(listPtr, &length); - if (length == 0) { - *intPtr = 0; - return TCL_OK; - } - result = SetListFromAny(interp, listPtr); - if (result != TCL_OK) { - return result; - } - ListGetInternalRep(listPtr, listRepPtr); + /* + * TODO + * Unlike the original list code, this does not optimize for lindex'ing + * an empty string when the internal rep is not already a list. On the + * other hand, this code will be faster for the case where the object + * is currently a dict. Benchmark the two cases. + */ + if (TclListObjGetRep(interp, listObj, &listRep) != TCL_OK) { + return TCL_ERROR; } - - *intPtr = listRepPtr->elemCount; + *lenPtr = ListRepLength(&listRep); return TCL_OK; } - + /* *---------------------------------------------------------------------- * * Tcl_ListObjReplace -- * - * Replace values in a list. - * - * If 'first' is zero or TCL_INDEX_NONE, it refers to the first element. If - * 'first' outside the range of elements in the list, no elements are - * deleted. - * - * If 'count' is zero or TCL_INDEX_NONE no elements are deleted, and any new - * elements are inserted at the beginning of the list. + * This function replaces zero or more elements of the list referenced by + * listObj with the objects from an (objc,objv) array. The objc elements + * of the array referenced by objv replace the count elements in listPtr + * starting at first. * - * Value + * If the argument first is zero or negative, it refers to the first + * element. If first is greater than or equal to the number of elements + * in the list, then no elements are deleted; the new elements are + * appended to the list. Count gives the number of elements to replace. + * If count is zero or negative then no elements are deleted; the new + * elements are simply inserted before first. * - * TCL_OK + * The argument objv refers to an array of objc pointers to the new + * elements to be added to listPtr in place of those that were deleted. + * If objv is NULL, no new elements are added. If listPtr is not a list + * object, an attempt will be made to convert it to one. * - * The first 'objc' values of 'objv' replaced 'count' elements in 'listPtr' - * starting at 'first'. If 'objc' 0, no new elements are added. - * - * TCL_ERROR - * - * 'listPtr' is not a valid list. An error message is left in the - * interpreter's result if 'interp' is not NULL. - * - * Effect - * - * If 'listPtr' is not of type 'tclListType', it is converted if possible. - * - * The 'refCount' of each element appended to the list is incremented. - * Similarly, the 'refCount' for each replaced element is decremented. + * Results: + * The return value is normally TCL_OK. If listPtr does not refer to a + * list object and can not be converted to one, TCL_ERROR is returned and + * an error message will be left in the interpreter's result if interp is + * not NULL. * - * If 'listPtr' is modified, any previous string representation is - * invalidated. + * Side effects: + * The ref counts of the objc elements in objv are incremented since the + * resulting list now refers to them. Similarly, the ref counts for + * replaced objects are decremented. listObj is converted, if necessary, + * to a list object. listObj's old string representation, if any, is + * freed. * *---------------------------------------------------------------------- */ - int Tcl_ListObjReplace( Tcl_Interp *interp, /* Used for error reporting if not NULL. */ - Tcl_Obj *listPtr, /* List object whose elements to replace. */ - size_t first, /* Index of first element to replace. */ - size_t count, /* Number of elements to replace. */ - size_t objc, /* Number of objects to insert. */ - Tcl_Obj *const objv[]) /* An array of objc pointers to Tcl objects to - * insert. */ + Tcl_Obj *listObj, /* List object whose elements to replace. */ + size_t first, /* Index of first element to replace. */ + size_t numToDelete, /* Number of elements to replace. */ + size_t numToInsert, /* Number of objects to insert. */ + Tcl_Obj *const insertObjs[])/* Tcl objects to insert */ { - List *listRepPtr; - Tcl_Obj **elemPtrs; - size_t numElems, numRequired, numAfterLast, start, i, j; - int needGrow, isShared; - - if (Tcl_IsShared(listPtr)) { + ListRep listRep; + ListSizeT origListLen; + ListSizeT lenChange; + ListSizeT leadSegmentLen; + ListSizeT tailSegmentLen; + ListSizeT numFreeSlots; + ListSizeT leadShift; + ListSizeT tailShift; + Tcl_Obj **listObjs; + + if (Tcl_IsShared(listObj)) { Tcl_Panic("%s called with shared object", "Tcl_ListObjReplace"); } - ListGetInternalRep(listPtr, listRepPtr); - if (listRepPtr == NULL) { - size_t length; + if (TclListObjGetRep(interp, listObj, &listRep) != TCL_OK) + return TCL_ERROR; /* Cannot be converted to a list */ - (void) Tcl_GetStringFromObj(listPtr, &length); - if (length == 0) { - if (objc == 0) { - return TCL_OK; - } - Tcl_SetListObj(listPtr, objc, NULL); - } else { - int result = SetListFromAny(interp, listPtr); + /* TODO - will need modification if Tcl9 sticks to unsigned indices */ - if (result != TCL_OK) { - return result; - } - } - ListGetInternalRep(listPtr, listRepPtr); + /* Make limits sane */ + origListLen = ListRepLength(&listRep); + if (first == TCL_INDEX_NONE) { + first = 0; + } + if (first > (size_t)origListLen) { + first = origListLen; /* So we'll insert after last element. */ + } + if (numToDelete == TCL_INDEX_NONE) { + numToDelete = 0; + } else if (first > ListSizeT_MAX - numToDelete /* Handle integer overflow */ + || (size_t)origListLen < first + numToDelete) { + numToDelete = origListLen - first; + } + + if (numToInsert > ListSizeT_MAX - (origListLen - numToDelete)) { + return ListLimitExceededError(interp); } /* - * Note that when count == 0 and objc == 0, this routine is logically a - * no-op, removing and adding no elements to the list. However, by flowing - * through this routine anyway, we get the important side effect that the - * resulting listPtr is a list in canoncial form. This is important. - * Resist any temptation to optimize this case. + * There are a number of special cases to consider from an optimization + * point of view. + * (1) Pure deletes (numToInsert==0) from the front or back can be treated + * as a range op irrespective of whether the ListStore is shared or not + * (2) Pure inserts (numToDelete == 0) + * (2a) Pure inserts at the back can be treated as appends + * (2b) Pure inserts from the *front* can be optimized under certain + * conditions by inserting before first ListStore slot in use if there + * is room, again irrespective of sharing + * (3) If the ListStore is shared OR there is insufficient free space + * OR existing allocation is too large compared to new size, create + * a new ListStore + * (4) Unshared ListStore with sufficient free space. Delete, shift and + * insert within the ListStore. */ - elemPtrs = listRepPtr->elements; - numElems = listRepPtr->elemCount; + /* Note: do not do TclInvalidateStringRep as yet in case there are errors */ - if (first == TCL_INDEX_NONE) { - first = 0; - } - if (first >= numElems) { - first = numElems; /* So we'll insert after last element. */ + /* Check Case (1) - Treat pure deletes from front or back as range ops */ + if (numToInsert == 0) { + if (numToDelete == 0) { + /* Should force canonical even for no-op */ + TclInvalidateStringRep(listObj); + return TCL_OK; + } + if (first == 0) { + /* Delete from front, so return tail */ + ListRep tailRep; + ListRepRange(&listRep, numToDelete, origListLen-1, 0, &tailRep); + ListObjReplaceRepAndInvalidate(listObj, &tailRep); + return TCL_OK; + } else if ((first+numToDelete) >= (size_t)origListLen) { + /* Delete from tail, so return head */ + ListRep headRep; + ListRepRange(&listRep, 0, first-1, 0, &headRep); + ListObjReplaceRepAndInvalidate(listObj, &headRep); + return TCL_OK; + } + /* Deletion from middle. Fall through to general case */ } - if (count == TCL_INDEX_NONE) { - count = 0; - } else if (count > LIST_MAX /* Handle integer overflow */ - || numElems < first+count) { - count = numElems - first; + /* Garbage collect before checking the pure insert optimization */ + ListRepFreeUnreferenced(&listRep); + + /* + * Check Case (2) - pure inserts under certain conditions: + */ + if (numToDelete == 0) { + /* Case (2a) - Append to list */ + if (first == (size_t)origListLen) { + return TclListObjAppendElements( + interp, listObj, numToInsert, insertObjs); + } + + /* + * Case (2b) - pure inserts at front under some circumstances + * (i) Insertion must be at head of list + * (ii) The list's span must be at head of the in-use slots in the store + * (iii) There must be unused room at front of the store + * NOTE THIS IS TRUE EVEN IF THE ListStore IS SHARED as it will not + * affect the other Tcl_Obj's referencing this ListStore. See the TIP. + */ + if (first == 0 && /* (i) */ + ListRepStart(&listRep) == listRep.storePtr->firstUsed && /* (ii) */ + numToInsert <= (size_t)listRep.storePtr->firstUsed /* (iii) */ + ) { + ListSizeT newLen; + LIST_ASSERT(numToInsert); /* Else would have returned above */ + listRep.storePtr->firstUsed -= numToInsert; + ObjArrayCopy(&listRep.storePtr->slots[listRep.storePtr->firstUsed], + numToInsert, + insertObjs); + listRep.storePtr->numUsed += numToInsert; + newLen = listRep.spanPtr->spanLength + numToInsert; + if (listRep.spanPtr && listRep.spanPtr->refCount <= 1) { + /* An unshared span record, re-use it */ + listRep.spanPtr->spanStart = listRep.storePtr->firstUsed; + listRep.spanPtr->spanLength = newLen; + } else { + /* Need a new span record */ + if (listRep.storePtr->firstUsed == 0) { + listRep.spanPtr = NULL; + } else { + listRep.spanPtr = + ListSpanNew(listRep.storePtr->firstUsed, newLen); + } + } + ListObjReplaceRepAndInvalidate(listObj, &listRep); + return TCL_OK; + } } - isShared = (listRepPtr->refCount > 1); - numRequired = numElems - count + objc; /* Known <= LIST_MAX */ - needGrow = numRequired > listRepPtr->maxElemCount; - for (i = 0; i < objc; i++) { - Tcl_IncrRefCount(objv[i]); + /* Just for readability of the code */ + lenChange = numToInsert - numToDelete; + leadSegmentLen = first; + tailSegmentLen = origListLen - (first + numToDelete); + numFreeSlots = listRep.storePtr->numAllocated - listRep.storePtr->numUsed; + + /* + * Before further processing, if unshared, try and reallocate to avoid + * new allocation below. This avoids expensive ref count manipulation + * later by not having to go through the ListRepInit and + * ListObjReplaceAndInvalidate below. + */ + if (numFreeSlots < lenChange && !ListRepIsShared(&listRep)) { + ListStore *newStorePtr = + ListStoreReallocate(listRep.storePtr, origListLen + lenChange); + if (newStorePtr == NULL) { + return MemoryAllocationError(interp, + LIST_SIZE(origListLen + lenChange)); + } + listRep.storePtr = newStorePtr; + numFreeSlots = + listRep.storePtr->numAllocated - listRep.storePtr->numUsed; + /* + * WARNING: at this point the Tcl_Obj internal rep potentially + * points to freed storage if the reallocation returned a + * different location. Overwrite it to bring it back in sync. + */ + ListObjStompRep(listObj, &listRep); } - if (needGrow && !isShared) { - /* Try to use realloc */ - List *newPtr = NULL; - size_t attempt = 2 * numRequired; - if (attempt <= LIST_MAX) { - newPtr = (List *)Tcl_AttemptRealloc(listRepPtr, LIST_SIZE(attempt)); + /* + * Case (3) a new ListStore is required + * (a) The passed-in ListStore is shared + * (b) There is not enough free space in the unshared passed-in ListStore + * (c) The new unshared size is much "smaller" (TODO) than the allocated space + * TODO - for unshared case ONLY, consider a "move" based implementation + */ + if (ListRepIsShared(&listRep) || /* 3a */ + numFreeSlots < lenChange || /* 3b */ + (origListLen + lenChange) < (listRep.storePtr->numAllocated / 4) /* 3c */ + ) { + ListRep newRep; + Tcl_Obj **toObjs; + listObjs = &listRep.storePtr->slots[ListRepStart(&listRep)]; + ListRepInit(origListLen + lenChange, + NULL, + LISTREP_PANIC_ON_FAIL | LISTREP_SPACE_FAVOR_NONE, + &newRep); + toObjs = ListRepSlotPtr(&newRep, 0); + if (leadSegmentLen > 0) { + ObjArrayCopy(toObjs, leadSegmentLen, listObjs); } - if (newPtr == NULL) { - attempt = numRequired + 1 + TCL_MIN_ELEMENT_GROWTH; - if (attempt > LIST_MAX) { - attempt = LIST_MAX; - } - newPtr = (List *)Tcl_AttemptRealloc(listRepPtr, LIST_SIZE(attempt)); + if (numToInsert > 0) { + ObjArrayCopy(&toObjs[leadSegmentLen], + numToInsert, + insertObjs); } - if (newPtr == NULL) { - attempt = numRequired; - newPtr = (List *)Tcl_AttemptRealloc(listRepPtr, LIST_SIZE(attempt)); + if (tailSegmentLen > 0) { + ObjArrayCopy(&toObjs[leadSegmentLen + numToInsert], + tailSegmentLen, + &listObjs[leadSegmentLen+numToDelete]); } - if (newPtr) { - listRepPtr = newPtr; - ListResetInternalRep(listPtr, listRepPtr); - elemPtrs = listRepPtr->elements; - listRepPtr->maxElemCount = attempt; - needGrow = numRequired > listRepPtr->maxElemCount; + newRep.storePtr->numUsed = origListLen + lenChange; + if (newRep.spanPtr) { + newRep.spanPtr->spanLength = newRep.storePtr->numUsed; } + LISTREP_CHECK(&newRep); + ListObjReplaceRepAndInvalidate(listObj, &newRep); + return TCL_OK; } - if (!needGrow && !isShared) { - int shift; - /* - * Can use the current List struct. First "delete" count elements - * starting at first. - */ + /* + * Case (4) - unshared ListStore with sufficient room. + * After deleting elements, there will be a corresponding gap. If this + * gap does not match number of insertions, either the lead segment, + * or the tail segment, or both will have to be moved. + * The general strategy is to move the fewest number of elements. If + * + * TODO - what about appends to unshared ? Is below sufficiently optimal? + */ - for (j = first; j < first + count; j++) { - Tcl_Obj *victimPtr = elemPtrs[j]; + /* Following must hold for unshared listreps after ListRepFreeUnreferenced above */ + LIST_ASSERT(origListLen == listRep.storePtr->numUsed); + LIST_ASSERT(origListLen == ListRepLength(&listRep)); + LIST_ASSERT(ListRepStart(&listRep) == listRep.storePtr->firstUsed); - TclDecrRefCount(victimPtr); - } + LIST_ASSERT((numToDelete + numToInsert) > 0); - /* - * Shift the elements after the last one removed to their new - * locations. - */ + /* Base of slot array holding the list elements */ + listObjs = &listRep.storePtr->slots[ListRepStart(&listRep)]; - start = first + count; - numAfterLast = numElems - start; - shift = objc - count; /* numNewElems - numDeleted */ - if ((numAfterLast > 0) && (shift != 0)) { - Tcl_Obj **src = elemPtrs + start; + /* + * Free up elements to be deleted. Before that, increment the ref counts + * for objects to be inserted in case there is overlap. See bug3598580 + * or test listobj-11.1 + */ + if (numToInsert) { + ObjArrayIncrRefs(insertObjs, 0, numToInsert); + } + if (numToDelete) { + ObjArrayDecrRefs(listObjs, first, numToDelete); + } - memmove(src+shift, src, numAfterLast * sizeof(Tcl_Obj*)); - } - } else { + /* + * Calculate shifts if necessary to accomodate insertions. + * NOTE: all indices are relative to listObjs which is not necessarily the + * start of the ListStore storage area. + * + * leadShift - how much to shift the lead segment + * tailShift - how much to shift the tail segment + * insertTarget - index where to insert. + */ + + if (lenChange == 0) { + /* Exact fit */ + leadShift = 0; + tailShift = 0; + } else if (lenChange < 0) { /* - * Cannot use the current List struct; it is shared, too small, or - * both. Allocate a new struct and insert elements into it. + * More deletions than insertions. The gap after deletions is large + * enough for insertions. Move a segment depending on size. */ - - List *oldListRepPtr = listRepPtr; - Tcl_Obj **oldPtrs = elemPtrs; - int newMax; - - if (needGrow) { - newMax = 2 * numRequired; + if (leadSegmentLen > tailSegmentLen) { + /* Tail segment smaller. Insert after lead, move tail down */ + leadShift = 0; + tailShift = lenChange; } else { - newMax = listRepPtr->maxElemCount; + /* Lead segment smaller. Insert before tail, move lead up */ + leadShift = -lenChange; + tailShift = 0; } + } else { + LIST_ASSERT(lenChange > 0); /* Reminder */ - listRepPtr = AttemptNewList(NULL, newMax, NULL); - if (listRepPtr == NULL) { - unsigned int limit = LIST_MAX - numRequired; - unsigned int extra = numRequired - numElems - + TCL_MIN_ELEMENT_GROWTH; - int growth = (int) ((extra > limit) ? limit : extra); - - listRepPtr = AttemptNewList(NULL, numRequired + growth, NULL); - if (listRepPtr == NULL) { - listRepPtr = AttemptNewList(interp, numRequired, NULL); - if (listRepPtr == NULL) { - for (i = 0; i < objc; i++) { - /* See bug 3598580 */ - Tcl_DecrRefCount(objv[i]); - } - return TCL_ERROR; + /* + * We need to make room for the insertions. Again we have multiple + * possibilities. We may be able to get by just shifting one segment + * or need to shift both. In the former case, favor shifting the + * smaller segment. + */ + ListSizeT leadSpace = ListRepNumFreeHead(&listRep); + ListSizeT tailSpace = ListRepNumFreeTail(&listRep); + ListSizeT finalFreeSpace = leadSpace + tailSpace - lenChange; + + LIST_ASSERT((leadSpace + tailSpace) >= lenChange); + if (leadSpace >= lenChange + && (leadSegmentLen < tailSegmentLen || tailSpace < lenChange)) { + /* Move only lead to the front to make more room */ + leadShift = -lenChange; + tailShift = 0; + /* + * Redistribute the remaining free space between the front and + * back if either there is no tail space left or if the + * entire list is the head anyways. This is an important + * optimization for further operations like further asymmetric + * insertions. + */ + if (finalFreeSpace > 1 && (tailSpace == 0 || tailSegmentLen == 0)) { + ListSizeT postShiftLeadSpace = leadSpace - lenChange; + if (postShiftLeadSpace > (finalFreeSpace/2)) { + ListSizeT extraShift = postShiftLeadSpace - (finalFreeSpace / 2); + leadShift -= extraShift; + tailShift = -extraShift; /* Move tail to the front as well */ } } - } - - ListResetInternalRep(listPtr, listRepPtr); - listRepPtr->refCount++; - - elemPtrs = listRepPtr->elements; - - if (isShared) { + LIST_ASSERT(leadShift >= 0 || leadSpace >= -leadShift); + } else if (tailSpace >= lenChange) { + /* Move only tail segment to the back to make more room. */ + leadShift = 0; + tailShift = lenChange; /* - * The old struct will remain in place; need new refCounts for the - * new List struct references. Copy over only the surviving - * elements. + * See comments above. This is analogous. */ - - for (i=0; i < first; i++) { - elemPtrs[i] = oldPtrs[i]; - Tcl_IncrRefCount(elemPtrs[i]); - } - for (i = first + count, j = first + objc; - j < numRequired; i++, j++) { - elemPtrs[j] = oldPtrs[i]; - Tcl_IncrRefCount(elemPtrs[j]); + if (finalFreeSpace > 1 && (leadSpace == 0 || leadSegmentLen == 0)) { + ListSizeT postShiftTailSpace = tailSpace - lenChange; + if (postShiftTailSpace > (finalFreeSpace/2)) { + ListSizeT extraShift = postShiftTailSpace - (finalFreeSpace / 2); + tailShift += extraShift; + leadShift = extraShift; /* Move head to the back as well */ + } } - - oldListRepPtr->refCount--; + LIST_ASSERT(tailShift <= tailSpace); } else { /* - * The old struct will be removed; use its inherited refCounts. + * Both lead and tail need to be shifted to make room. + * Divide remaining free space equally between front and back. */ - - if (first > 0) { - memcpy(elemPtrs, oldPtrs, first * sizeof(Tcl_Obj *)); - } + LIST_ASSERT(leadSpace < lenChange); + LIST_ASSERT(tailSpace < lenChange); /* - * "Delete" count elements starting at first. + * leadShift = leadSpace - (finalFreeSpace/2) + * Thus leadShift <= leadSpace + * Also, + * = leadSpace - (leadSpace + tailSpace - lenChange)/2 + * = leadSpace/2 - tailSpace/2 + lenChange/2 + * >= 0 because lenChange > tailSpace */ - - for (j = first; j < first + count; j++) { - Tcl_Obj *victimPtr = oldPtrs[j]; - - TclDecrRefCount(victimPtr); + leadShift = leadSpace - (finalFreeSpace / 2); + tailShift = lenChange - leadShift; + if (tailShift > tailSpace) { + /* Account for integer division errors */ + leadShift += 1; + tailShift -= 1; } - /* - * Copy the elements after the last one removed, shifted to their - * new locations. + * Following must be true because otherwise one of the previous + * if clauses would have been taken. */ - - start = first + count; - numAfterLast = numElems - start; - if (numAfterLast > 0) { - memcpy(elemPtrs + first + objc, oldPtrs + start, - (size_t) numAfterLast * sizeof(Tcl_Obj *)); - } - - Tcl_Free(oldListRepPtr); + LIST_ASSERT(leadShift > 0 && leadShift < lenChange); + LIST_ASSERT(tailShift > 0 && tailShift < lenChange); + leadShift = -leadShift; /* Lead is actually shifted downward */ } } - /* - * Insert the new elements into elemPtrs before "first". - */ - - for (i=0,j=first ; i<objc ; i++,j++) { - elemPtrs[j] = objv[i]; + /* Careful about order of moves! */ + if (leadShift > 0) { + /* Will happen when we have to make room at bottom */ + if (tailShift != 0 && tailSegmentLen != 0) { + ListSizeT tailStart = leadSegmentLen + numToDelete; + memmove(&listObjs[tailStart + tailShift], + &listObjs[tailStart], + tailSegmentLen * sizeof(Tcl_Obj *)); + } + if (leadSegmentLen != 0) { + memmove(&listObjs[leadShift], + &listObjs[0], + leadSegmentLen * sizeof(Tcl_Obj *)); + } + } else { + if (leadShift != 0 && leadSegmentLen != 0) { + memmove(&listObjs[leadShift], + &listObjs[0], + leadSegmentLen * sizeof(Tcl_Obj *)); + } + if (tailShift != 0 && tailSegmentLen != 0) { + ListSizeT tailStart = leadSegmentLen + numToDelete; + memmove(&listObjs[tailStart + tailShift], + &listObjs[tailStart], + tailSegmentLen * sizeof(Tcl_Obj *)); + } + } + if (numToInsert) { + /* Do NOT use ObjArrayCopy here since we have already incr'ed ref counts */ + memmove(&listObjs[leadSegmentLen + leadShift], + insertObjs, + numToInsert * sizeof(Tcl_Obj *)); } - /* - * Update the count of elements. - */ - - listRepPtr->elemCount = numRequired; + listRep.storePtr->firstUsed += leadShift; + listRep.storePtr->numUsed = origListLen + lenChange; + listRep.storePtr->flags = 0; - /* - * Invalidate and free any old representations that may not agree - * with the revised list's internal representation. - */ - - listRepPtr->refCount++; - TclFreeInternalRep(listPtr); - ListSetInternalRep(listPtr, listRepPtr); - listRepPtr->refCount--; + if (listRep.spanPtr && listRep.spanPtr->refCount <= 1) { + /* An unshared span record, re-use it, even if not required */ + listRep.spanPtr->spanStart = listRep.storePtr->firstUsed; + listRep.spanPtr->spanLength = listRep.storePtr->numUsed; + } else { + /* Need a new span record */ + if (listRep.storePtr->firstUsed == 0) { + listRep.spanPtr = NULL; + } else { + listRep.spanPtr = ListSpanNew(listRep.storePtr->firstUsed, + listRep.storePtr->numUsed); + } + } - TclInvalidateStringRep(listPtr); + LISTREP_CHECK(&listRep); + ListObjReplaceRepAndInvalidate(listObj, &listRep); return TCL_OK; } + /* *---------------------------------------------------------------------- * * TclLindexList -- * - * Implements the 'lindex' command when objc==3. + * This procedure handles the 'lindex' command when objc==3. * - * Implemented entirely as a wrapper around 'TclLindexFlat'. Reconfigures - * the argument format into required form while taking care to manage - * shimmering so as to tend to keep the most useful internalreps - * and/or avoid the most expensive conversions. - * - * Value + * Results: + * Returns a pointer to the object extracted, or NULL if an error + * occurred. The returned object already includes one reference count for + * the pointer returned. * - * A pointer to the specified element, with its 'refCount' incremented, or - * NULL if an error occurred. + * Side effects: + * None. * - * Notes + * Notes: + * This procedure is implemented entirely as a wrapper around + * TclLindexFlat. All it does is reconfigure the argument format into the + * form required by TclLindexFlat, while taking care to manage shimmering + * in such a way that we tend to keep the most useful internalreps and/or + * avoid the most expensive conversions. * *---------------------------------------------------------------------- */ @@ -1206,28 +2442,27 @@ Tcl_ListObjReplace( Tcl_Obj * TclLindexList( Tcl_Interp *interp, /* Tcl interpreter. */ - Tcl_Obj *listPtr, /* List being unpacked. */ - Tcl_Obj *argPtr) /* Index or index list. */ + Tcl_Obj *listObj, /* List being unpacked. */ + Tcl_Obj *argObj) /* Index or index list. */ { - size_t index; /* Index into the list. */ Tcl_Obj *indexListCopy; - List *listRepPtr; + Tcl_Obj **indexObjs; + ListSizeT numIndexObjs; /* * Determine whether argPtr designates a list or a single index. We have * to be careful about the order of the checks to avoid repeated - * shimmering; see TIP#22 and TIP#33 for the details. + * shimmering; if internal rep is already a list do not shimmer it. + * see TIP#22 and TIP#33 for the details. */ - - ListGetInternalRep(argPtr, listRepPtr); - if ((listRepPtr == NULL) - && TclGetIntForIndexM(NULL , argPtr, (size_t)WIDE_MAX - 1, &index) == TCL_OK) { + if (!TclHasInternalRep(argObj, &tclListType) + && TclGetIntForIndexM(NULL, argObj, ListSizeT_MAX - 1, &index) + == TCL_OK) { /* * argPtr designates a single index. */ - - return TclLindexFlat(interp, listPtr, 1, &argPtr); + return TclLindexFlat(interp, listObj, 1, &argObj); } /* @@ -1242,43 +2477,44 @@ TclLindexList( * implementation does not. */ - indexListCopy = TclListObjCopy(NULL, argPtr); + indexListCopy = TclListObjCopy(NULL, argObj); if (indexListCopy == NULL) { /* - * argPtr designates something that is neither an index nor a - * well-formed list. Report the error via TclLindexFlat. + * The argument is neither an index nor a well-formed list. + * Report the error via TclLindexFlat. + * TODO - This is as original. why not directly return an error? */ - - return TclLindexFlat(interp, listPtr, 1, &argPtr); + return TclLindexFlat(interp, listObj, 1, &argObj); } - ListGetInternalRep(indexListCopy, listRepPtr); - - assert(listRepPtr != NULL); - - listPtr = TclLindexFlat(interp, listPtr, listRepPtr->elemCount, - listRepPtr->elements); + ListObjGetElements(indexListCopy, numIndexObjs, indexObjs); + listObj = TclLindexFlat(interp, listObj, numIndexObjs, indexObjs); Tcl_DecrRefCount(indexListCopy); - return listPtr; + return listObj; } /* *---------------------------------------------------------------------- * - * TclLindexFlat -- - * - * The core of the 'lindex' command, with all index - * arguments presented as a flat list. + * TclLindexFlat -- * - * Value + * This procedure is the core of the 'lindex' command, with all index + * arguments presented as a flat list. * - * A pointer to the object extracted, with its 'refCount' incremented, or - * NULL if an error occurred. Thus, the calling code will usually do - * something like: + * Results: + * Returns a pointer to the object extracted, or NULL if an error + * occurred. The returned object already includes one reference count for + * the pointer returned. * - * Tcl_SetObjResult(interp, result); - * Tcl_DecrRefCount(result); + * Side effects: + * None. * + * Notes: + * The reference count of the returned object includes one reference + * corresponding to the pointer returned. Thus, the calling code will + * usually do something like: + * Tcl_SetObjResult(interp, result); + * Tcl_DecrRefCount(result); * *---------------------------------------------------------------------- */ @@ -1286,16 +2522,16 @@ TclLindexList( Tcl_Obj * TclLindexFlat( Tcl_Interp *interp, /* Tcl interpreter. */ - Tcl_Obj *listPtr, /* Tcl object representing the list. */ + Tcl_Obj *listObj, /* Tcl object representing the list. */ size_t indexCount, /* Count of indices. */ Tcl_Obj *const indexArray[])/* Array of pointers to Tcl objects that * represent the indices in the list. */ { size_t i; - Tcl_IncrRefCount(listPtr); + Tcl_IncrRefCount(listObj); - for (i=0 ; i<indexCount && listPtr ; i++) { + for (i=0 ; i<indexCount && listObj ; i++) { size_t index, listLen = 0; Tcl_Obj **elemPtrs = NULL, *sublistCopy; @@ -1305,48 +2541,44 @@ TclLindexFlat( * while we are still using it. See test lindex-8.4. */ - sublistCopy = TclListObjCopy(interp, listPtr); - Tcl_DecrRefCount(listPtr); - listPtr = NULL; + sublistCopy = TclListObjCopy(interp, listObj); + Tcl_DecrRefCount(listObj); + listObj = NULL; if (sublistCopy == NULL) { - /* - * The sublist is not a list at all => error. - */ - + /* The sublist is not a list at all => error. */ break; } - TclListObjGetElementsM(NULL, sublistCopy, &listLen, &elemPtrs); + LIST_ASSERT_TYPE(sublistCopy); + ListObjGetElements(sublistCopy, listLen, elemPtrs); if (TclGetIntForIndexM(interp, indexArray[i], /*endValue*/ listLen-1, &index) == TCL_OK) { - if (index >= (size_t)listLen) { + if (index >= listLen) { /* * Index is out of range. Break out of loop with empty result. * First check remaining indices for validity */ while (++i < indexCount) { - if (TclGetIntForIndexM(interp, indexArray[i], (size_t)WIDE_MAX - 1, &index) + if (TclGetIntForIndexM( + interp, indexArray[i], ListSizeT_MAX - 1, &index) != TCL_OK) { Tcl_DecrRefCount(sublistCopy); return NULL; } } - TclNewObj(listPtr); + TclNewObj(listObj); } else { - /* - * Extract the pointer to the appropriate element. - */ - - listPtr = elemPtrs[index]; + /* Extract the pointer to the appropriate element. */ + listObj = elemPtrs[index]; } - Tcl_IncrRefCount(listPtr); + Tcl_IncrRefCount(listObj); } Tcl_DecrRefCount(sublistCopy); } - return listPtr; + return listObj; } /* @@ -1354,17 +2586,24 @@ TclLindexFlat( * * TclLsetList -- * - * The core of [lset] when objc == 4. Objv[2] may be either a + * Core of the 'lset' command when objc == 4. Objv[2] may be either a * scalar index or a list of indices. * It also handles 'lpop' when given a NULL value. * - * Implemented entirely as a wrapper around 'TclLindexFlat', as described - * for 'TclLindexList'. + * Results: + * Returns the new value of the list variable, or NULL if there was an + * error. The returned object includes one reference count for the + * pointer returned. * - * Value + * Side effects: + * None. * - * The new list, with the 'refCount' of 'valuPtr' incremented, or NULL if - * there was an error. + * Notes: + * This procedure is implemented entirely as a wrapper around + * TclLsetFlat. All it does is reconfigure the argument format into the + * form required by TclLsetFlat, while taking care to manage shimmering + * in such a way that we tend to keep the most useful internalreps and/or + * avoid the most expensive conversions. * *---------------------------------------------------------------------- */ @@ -1372,16 +2611,15 @@ TclLindexFlat( Tcl_Obj * TclLsetList( Tcl_Interp *interp, /* Tcl interpreter. */ - Tcl_Obj *listPtr, /* Pointer to the list being modified. */ - Tcl_Obj *indexArgPtr, /* Index or index-list arg to 'lset'. */ - Tcl_Obj *valuePtr) /* Value arg to 'lset' or NULL to 'lpop'. */ + Tcl_Obj *listObj, /* Pointer to the list being modified. */ + Tcl_Obj *indexArgObj, /* Index or index-list arg to 'lset'. */ + Tcl_Obj *valueObj) /* Value arg to 'lset' or NULL to 'lpop'. */ { - size_t indexCount = 0; /* Number of indices in the index list. */ + ListSizeT indexCount = 0; /* Number of indices in the index list. */ Tcl_Obj **indices = NULL; /* Vector of indices in the index list. */ - Tcl_Obj *retValuePtr; /* Pointer to the list to be returned. */ - size_t index; /* Current index in the list - discarded. */ + Tcl_Obj *retValueObj; /* Pointer to the list to be returned. */ + size_t index; /* Current index in the list - discarded. */ Tcl_Obj *indexListCopy; - List *listRepPtr; /* * Determine whether the index arg designates a list or a single index. @@ -1389,36 +2627,32 @@ TclLsetList( * shimmering; see TIP #22 and #23 for details. */ - ListGetInternalRep(indexArgPtr, listRepPtr); - if (listRepPtr == NULL - && TclGetIntForIndexM(NULL, indexArgPtr, (size_t)WIDE_MAX - 1, &index) == TCL_OK) { - /* - * indexArgPtr designates a single index. - */ - - return TclLsetFlat(interp, listPtr, 1, &indexArgPtr, valuePtr); - + if (!TclHasInternalRep(indexArgObj, &tclListType) + && TclGetIntForIndexM(NULL, indexArgObj, ListSizeT_MAX - 1, &index) + == TCL_OK) { + /* indexArgPtr designates a single index. */ + return TclLsetFlat(interp, listObj, 1, &indexArgObj, valueObj); } - indexListCopy = TclListObjCopy(NULL, indexArgPtr); + indexListCopy = TclListObjCopy(NULL, indexArgObj); if (indexListCopy == NULL) { /* * indexArgPtr designates something that is neither an index nor a * well formed list. Report the error via TclLsetFlat. */ - - return TclLsetFlat(interp, listPtr, 1, &indexArgPtr, valuePtr); + return TclLsetFlat(interp, listObj, 1, &indexArgObj, valueObj); } - TclListObjGetElementsM(NULL, indexArgPtr, &indexCount, &indices); + LIST_ASSERT_TYPE(indexListCopy); + ListObjGetElements(indexListCopy, indexCount, indices); /* * Let TclLsetFlat handle the actual lset'ting. */ - retValuePtr = TclLsetFlat(interp, listPtr, indexCount, indices, valuePtr); + retValueObj = TclLsetFlat(interp, listObj, indexCount, indices, valueObj); Tcl_DecrRefCount(indexListCopy); - return retValuePtr; + return retValueObj; } /* @@ -1429,41 +2663,31 @@ TclLsetList( * Core engine of the 'lset' command. * It also handles 'lpop' when given a NULL value. * - * Value - * - * The resulting list - * - * The 'refCount' of 'valuePtr' is incremented. If 'listPtr' was not - * duplicated, its 'refCount' is incremented. The reference count of - * an unduplicated object is therefore 2 (one for the returned pointer - * and one for the variable that holds it). The reference count of a - * duplicate object is 1, reflecting that result is the only active - * reference. The caller is expected to store the result in the - * variable and decrement its reference count. (INST_STORE_* does - * exactly this.) - * - * NULL - * - * An error occurred. If 'listPtr' was duplicated, the reference - * count on the duplicate is decremented so that it is 0, causing any - * memory allocated by this function to be freed. - * - * - * Effect - * - * On entry, the reference count of 'listPtr' does not reflect any - * references held on the stack. The first action of this function is to - * determine whether 'listPtr' is shared and to create a duplicate - * unshared copy if it is. The reference count of the duplicate is - * incremented. At this point, the reference count is 1 in either case so - * that the object is considered unshared. + * Results: + * Returns the new value of the list variable, or NULL if an error + * occurred. The returned object includes one reference count for the + * pointer returned. * - * The unshared list is altered directly to produce the result. - * 'TclLsetFlat' maintains a linked list of 'Tcl_Obj' values whose string - * representations must be spoilt by threading via 'ptr2' of the - * two-pointer internal representation. On entry to 'TclLsetFlat', the - * values of 'ptr2' are immaterial; on exit, the 'ptr2' field of any - * Tcl_Obj that has been modified is set to NULL. + * Side effects: + * On entry, the reference count of the variable value does not reflect + * any references held on the stack. The first action of this function is + * to determine whether the object is shared, and to duplicate it if it + * is. The reference count of the duplicate is incremented. At this + * point, the reference count will be 1 for either case, so that the + * object will appear to be unshared. + * + * If an error occurs, and the object has been duplicated, the reference + * count on the duplicate is decremented so that it is now 0: this + * dismisses any memory that was allocated by this function. + * + * If no error occurs, the reference count of the original object is + * incremented if the object has not been duplicated, and nothing is done + * to a reference count of the duplicate. Now the reference count of an + * unduplicated object is 2 (the returned pointer, plus the one stored in + * the variable). The reference count of a duplicate object is 1, + * reflecting that the returned pointer is the only active reference. The + * caller is expected to store the returned value back in the variable + * and decrement its reference count. (INST_STORE_* does exactly this.) * *---------------------------------------------------------------------- */ @@ -1471,52 +2695,60 @@ TclLsetList( Tcl_Obj * TclLsetFlat( Tcl_Interp *interp, /* Tcl interpreter. */ - Tcl_Obj *listPtr, /* Pointer to the list being modified. */ + Tcl_Obj *listObj, /* Pointer to the list being modified. */ size_t indexCount, /* Number of index args. */ Tcl_Obj *const indexArray[], /* Index args. */ - Tcl_Obj *valuePtr) /* Value arg to 'lset' or NULL to 'lpop'. */ + Tcl_Obj *valueObj) /* Value arg to 'lset' or NULL to 'lpop'. */ { size_t index, len; - int result; - Tcl_Obj *subListPtr, *retValuePtr, *chainPtr; - Tcl_ObjInternalRep *irPtr; + int result; + Tcl_Obj *subListObj, *retValueObj; + Tcl_Obj *pendingInvalidates[10]; + Tcl_Obj **pendingInvalidatesPtr = pendingInvalidates; + ListSizeT numPendingInvalidates = 0; /* * If there are no indices, simply return the new value. (Without * indices, [lset] is a synonym for [set]. - * [lpop] does not use this but protect for NULL valuePtr just in case. + * [lpop] does not use this but protect for NULL valueObj just in case. */ if (indexCount == 0) { - if (valuePtr != NULL) { - Tcl_IncrRefCount(valuePtr); + if (valueObj != NULL) { + Tcl_IncrRefCount(valueObj); } - return valuePtr; + return valueObj; } /* * If the list is shared, make a copy we can modify (copy-on-write). We * use Tcl_DuplicateObj() instead of TclListObjCopy() for a few reasons: - * 1) we have not yet confirmed listPtr is actually a list; 2) We make a + * 1) we have not yet confirmed listObj is actually a list; 2) We make a * verbatim copy of any existing string rep, and when we combine that with * the delayed invalidation of string reps of modified Tcl_Obj's * implemented below, the outcome is that any error condition that causes - * this routine to return NULL, will leave the string rep of listPtr and + * this routine to return NULL, will leave the string rep of listObj and * all elements to be unchanged. */ - subListPtr = Tcl_IsShared(listPtr) ? Tcl_DuplicateObj(listPtr) : listPtr; + subListObj = Tcl_IsShared(listObj) ? Tcl_DuplicateObj(listObj) : listObj; /* * Anchor the linked list of Tcl_Obj's whose string reps must be * invalidated if the operation succeeds. */ - retValuePtr = subListPtr; - chainPtr = NULL; + retValueObj = subListObj; result = TCL_OK; + /* Allocate if static array for pending invalidations is too small */ + if (indexCount + > (int) (sizeof(pendingInvalidates) / sizeof(pendingInvalidates[0]))) { + pendingInvalidatesPtr = + (Tcl_Obj **) Tcl_Alloc(indexCount * sizeof(*pendingInvalidatesPtr)); + } + /* * Loop through all the index arguments, and for each one dive into the * appropriate sublist. @@ -1530,8 +2762,8 @@ TclLsetFlat( * Check for the possible error conditions... */ - if (TclListObjGetElementsM(interp, subListPtr, &elemCount, &elemPtrs) - != TCL_OK) { + if (TclListObjGetElementsM(interp, subListObj, &elemCount, &elemPtrs) + != TCL_OK) { /* ...the sublist we're indexing into isn't a list at all. */ result = TCL_ERROR; break; @@ -1543,22 +2775,27 @@ TclLsetFlat( */ if (TclGetIntForIndexM(interp, *indexArray, elemCount - 1, &index) - != TCL_OK) { + != TCL_OK) { /* ...the index we're trying to use isn't an index at all. */ result = TCL_ERROR; - indexArray++; + indexArray++; /* Why bother with this increment? TBD */ break; } indexArray++; if (index > elemCount - || (valuePtr == NULL && index >= elemCount)) { + || (valueObj == NULL && index >= elemCount)) { /* ...the index points outside the sublist. */ if (interp != NULL) { - Tcl_SetObjResult(interp, Tcl_ObjPrintf( - "index \"%s\" out of range", Tcl_GetString(indexArray[-1]))); - Tcl_SetErrorCode(interp, "TCL", "VALUE", "INDEX" - "OUTOFRANGE", NULL); + Tcl_SetObjResult(interp, + Tcl_ObjPrintf("index \"%s\" out of range", + Tcl_GetString(indexArray[-1]))); + Tcl_SetErrorCode(interp, + "TCL", + "VALUE", + "INDEX" + "OUTOFRANGE", + NULL); } result = TCL_ERROR; break; @@ -1566,128 +2803,126 @@ TclLsetFlat( /* * No error conditions. As long as we're not yet on the last index, - * determine the next sublist for the next pass through the loop, and - * take steps to make sure it is an unshared copy, as we intend to - * modify it. + * determine the next sublist for the next pass through the loop, + * and take steps to make sure it is an unshared copy, as we intend + * to modify it. */ if (--indexCount) { - parentList = subListPtr; - if (index == (size_t)elemCount) { - TclNewObj(subListPtr); + parentList = subListObj; + if (index == elemCount) { + TclNewObj(subListObj); } else { - subListPtr = elemPtrs[index]; + subListObj = elemPtrs[index]; } - if (Tcl_IsShared(subListPtr)) { - subListPtr = Tcl_DuplicateObj(subListPtr); + if (Tcl_IsShared(subListObj)) { + subListObj = Tcl_DuplicateObj(subListObj); } /* * Replace the original elemPtr[index] in parentList with a copy * we know to be unshared. This call will also deal with the * situation where parentList shares its internalrep with other - * Tcl_Obj's. Dealing with the shared internalrep case can cause - * subListPtr to become shared again, so detect that case and make - * and store another copy. + * Tcl_Obj's. Dealing with the shared internalrep case can + * cause subListObj to become shared again, so detect that case + * and make and store another copy. */ - if (index == (size_t)elemCount) { - Tcl_ListObjAppendElement(NULL, parentList, subListPtr); + if (index == elemCount) { + Tcl_ListObjAppendElement(NULL, parentList, subListObj); } else { - TclListObjSetElement(NULL, parentList, index, subListPtr); + TclListObjSetElement(NULL, parentList, index, subListObj); } - if (Tcl_IsShared(subListPtr)) { - subListPtr = Tcl_DuplicateObj(subListPtr); - TclListObjSetElement(NULL, parentList, index, subListPtr); + if (Tcl_IsShared(subListObj)) { + subListObj = Tcl_DuplicateObj(subListObj); + TclListObjSetElement(NULL, parentList, index, subListObj); } /* - * The TclListObjSetElement() calls do not spoil the string rep of - * parentList, and that's fine for now, since all we've done so - * far is replace a list element with an unshared copy. The list - * value remains the same, so the string rep. is still valid, and - * unchanged, which is good because if this whole routine returns - * NULL, we'd like to leave no change to the value of the lset - * variable. Later on, when we set valuePtr in its proper place, - * then all containing lists will have their values changed, and - * will need their string reps spoiled. We maintain a list of all - * those Tcl_Obj's (via a little internalrep surgery) so we can spoil - * them at that time. + * The TclListObjSetElement() calls do not spoil the string rep + * of parentList, and that's fine for now, since all we've done + * so far is replace a list element with an unshared copy. The + * list value remains the same, so the string rep. is still + * valid, and unchanged, which is good because if this whole + * routine returns NULL, we'd like to leave no change to the + * value of the lset variable. Later on, when we set valueObj + * in its proper place, then all containing lists will have + * their values changed, and will need their string reps + * spoiled. We maintain a list of all those Tcl_Obj's (via a + * little internalrep surgery) so we can spoil them at that + * time. */ - irPtr = TclFetchInternalRep(parentList, &tclListType); - irPtr->twoPtrValue.ptr2 = chainPtr; - chainPtr = parentList; + pendingInvalidatesPtr[numPendingInvalidates] = parentList; + ++numPendingInvalidates; } } while (indexCount > 0); /* * Either we've detected and error condition, and exited the loop with * result == TCL_ERROR, or we've successfully reached the last index, and - * we're ready to store valuePtr. In either case, we need to clean up our - * string spoiling list of Tcl_Obj's. + * we're ready to store valueObj. On success, we need to invalidate + * the string representations of intermediate lists whose contained + * list element would have changed. */ + if (result == TCL_OK) { + while (numPendingInvalidates > 0) { + Tcl_Obj *objPtr; - while (chainPtr) { - Tcl_Obj *objPtr = chainPtr; - List *listRepPtr; - - /* - * Clear away our internalrep surgery mess. - */ - - irPtr = TclFetchInternalRep(objPtr, &tclListType); - listRepPtr = (List *)irPtr->twoPtrValue.ptr1; - chainPtr = (Tcl_Obj *)irPtr->twoPtrValue.ptr2; - - if (result == TCL_OK) { - - /* - * We're going to store valuePtr, so spoil string reps of all - * containing lists. - */ + --numPendingInvalidates; + objPtr = pendingInvalidatesPtr[numPendingInvalidates]; - listRepPtr->refCount++; - TclFreeInternalRep(objPtr); - ListSetInternalRep(objPtr, listRepPtr); - listRepPtr->refCount--; - - TclInvalidateStringRep(objPtr); - } else { - irPtr->twoPtrValue.ptr2 = NULL; + if (result == TCL_OK) { + /* + * We're going to store valueObj, so spoil string reps of all + * containing lists. + * TODO - historically, the storing of the internal rep was done + * because the ptr2 field of the internal rep was used to chain + * objects whose string rep needed to be invalidated. Now this + * is no longer the case, so replacing of the internal rep + * should not be needed. The TclInvalidateStringRep should + * suffice. Formulate a test case before changing. + */ + ListRep objInternalRep; + TclListObjGetRep(NULL, objPtr, &objInternalRep); + ListObjReplaceRepAndInvalidate(objPtr, &objInternalRep); + } } } + if (pendingInvalidatesPtr != pendingInvalidates) + Tcl_Free(pendingInvalidatesPtr); + if (result != TCL_OK) { /* * Error return; message is already in interp. Clean up any excess * memory. */ - if (retValuePtr != listPtr) { - Tcl_DecrRefCount(retValuePtr); + if (retValueObj != listObj) { + Tcl_DecrRefCount(retValueObj); } return NULL; } /* - * Store valuePtr in proper sublist and return. The TCL_INDEX_NONE is - * to avoid a compiler warning (not a problem because we checked that - * we have a proper list - or something convertible to one - above). + * Store valueObj in proper sublist and return. The -1 is to avoid a + * compiler warning (not a problem because we checked that we have a + * proper list - or something convertible to one - above). */ - len = TCL_INDEX_NONE; - TclListObjLengthM(NULL, subListPtr, &len); - if (valuePtr == NULL) { - Tcl_ListObjReplace(NULL, subListPtr, index, 1, 0, NULL); - } else if (index == (size_t)len) { - Tcl_ListObjAppendElement(NULL, subListPtr, valuePtr); + len = -1; + TclListObjLengthM(NULL, subListObj, &len); + if (valueObj == NULL) { + Tcl_ListObjReplace(NULL, subListObj, index, 1, 0, NULL); + } else if (index == len) { + Tcl_ListObjAppendElement(NULL, subListObj, valueObj); } else { - TclListObjSetElement(NULL, subListPtr, index, valuePtr); - TclInvalidateStringRep(subListPtr); + TclListObjSetElement(NULL, subListObj, index, valueObj); + TclInvalidateStringRep(subListObj); } - Tcl_IncrRefCount(retValuePtr); - return retValuePtr; + Tcl_IncrRefCount(retValueObj); + return retValueObj; } /* @@ -1695,38 +2930,23 @@ TclLsetFlat( * * TclListObjSetElement -- * - * Set a single element of a list to a specified value. - * - * It is the caller's responsibility to invalidate the string - * representation of the 'listPtr'. - * - * Value - * - * TCL_OK - * - * Success. - * - * TCL_ERROR - * - * 'listPtr' does not refer to a list object and cannot be converted - * to one. An error message will be left in the interpreter result if - * interp is not NULL. + * Set a single element of a list to a specified value * - * TCL_ERROR - * - * An index designates an element outside the range [0..listLength-1], - * where 'listLength' is the count of elements in the list object - * designated by 'listPtr'. An error message is left in the - * interpreter result. - * - * Effect - * - * If 'listPtr' designates a shared object, 'Tcl_Panic' is called. If - * 'listPtr' is not already of type 'tclListType', it is converted and the - * internal representation is unshared. The 'refCount' of the element at - * 'index' is decremented and replaced in the list with the 'valuePtr', - * whose 'refCount' in turn is incremented. + * Results: + * The return value is normally TCL_OK. If listObj does not refer to a + * list object and cannot be converted to one, TCL_ERROR is returned and + * an error message will be left in the interpreter result if interp is + * not NULL. Similarly, if index designates an element outside the range + * [0..listLength-1], where listLength is the count of elements in the + * list object designated by listObj, TCL_ERROR is returned and an error + * message is left in the interpreter result. * + * Side effects: + * Tcl_Panic if listObj designates a shared object. Otherwise, attempts + * to convert it to a list with a non-shared internal rep. Decrements the + * ref count of the object at the specified index within the list, + * replaces with the object designated by valueObj, and increments the + * ref count of the replacement object. * *---------------------------------------------------------------------- */ @@ -1735,53 +2955,29 @@ int TclListObjSetElement( Tcl_Interp *interp, /* Tcl interpreter; used for error reporting * if not NULL. */ - Tcl_Obj *listPtr, /* List object in which element should be + Tcl_Obj *listObj, /* List object in which element should be * stored. */ - size_t index, /* Index of element to store. */ - Tcl_Obj *valuePtr) /* Tcl object to store in the designated list + size_t index, /* Index of element to store. */ + Tcl_Obj *valueObj) /* Tcl object to store in the designated list * element. */ { - List *listRepPtr; /* Internal representation of the list being - * modified. */ - Tcl_Obj **elemPtrs; /* Pointers to elements of the list. */ + ListRep listRep; + Tcl_Obj **elemPtrs; /* Pointers to elements of the list. */ size_t elemCount; /* Number of elements in the list. */ - /* - * Ensure that the listPtr parameter designates an unshared list. - */ + /* Ensure that the listObj parameter designates an unshared list. */ - if (Tcl_IsShared(listPtr)) { + if (Tcl_IsShared(listObj)) { Tcl_Panic("%s called with shared object", "TclListObjSetElement"); } - ListGetInternalRep(listPtr, listRepPtr); - if (listRepPtr == NULL) { - int result; - size_t length; - - (void) Tcl_GetStringFromObj(listPtr, &length); - if (length == 0) { - if (interp != NULL) { - Tcl_SetObjResult(interp, Tcl_ObjPrintf( - "index \"%" TCL_Z_MODIFIER "u\" out of range", index)); - Tcl_SetErrorCode(interp, "TCL", "VALUE", "INDEX", - "OUTOFRANGE", NULL); - } - return TCL_ERROR; - } - result = SetListFromAny(interp, listPtr); - if (result != TCL_OK) { - return result; - } - ListGetInternalRep(listPtr, listRepPtr); + if (TclListObjGetRep(interp, listObj, &listRep) != TCL_OK) { + return TCL_ERROR; } - elemCount = listRepPtr->elemCount; - - /* - * Ensure that the index is in bounds. - */ + elemCount = ListRepLength(&listRep); + /* Ensure that the index is in bounds. */ if (index>=elemCount) { if (interp != NULL) { Tcl_SetObjResult(interp, Tcl_ObjPrintf( @@ -1792,66 +2988,27 @@ TclListObjSetElement( return TCL_ERROR; } - /* - * If the internal rep is shared, replace it with an unshared copy. - */ - - if (listRepPtr->refCount > 1) { - Tcl_Obj **dst, **src = listRepPtr->elements; - List *newPtr = AttemptNewList(NULL, listRepPtr->maxElemCount, NULL); - - if (newPtr == NULL) { - newPtr = AttemptNewList(interp, elemCount, NULL); - if (newPtr == NULL) { - return TCL_ERROR; - } - } - newPtr->refCount++; - newPtr->elemCount = elemCount; - newPtr->canonicalFlag = listRepPtr->canonicalFlag; - - dst = newPtr->elements; - while (elemCount--) { - *dst = *src++; - Tcl_IncrRefCount(*dst++); - } - - listRepPtr->refCount--; - - listRepPtr = newPtr; - ListResetInternalRep(listPtr, listRepPtr); + /* Replace a shared internal rep with an unshared copy */ + if (listRep.storePtr->refCount > 1) { + ListRep newInternalRep; + /* TODO - leave extra space? */ + ListRepClone(&listRep, &newInternalRep, LISTREP_PANIC_ON_FAIL); + listRep = newInternalRep; } - elemPtrs = listRepPtr->elements; - - /* - * Add a reference to the new list element. - */ - Tcl_IncrRefCount(valuePtr); + /* Retrieve element array AFTER potential cloning above */ + ListRepElements(&listRep, elemCount, elemPtrs); /* - * Remove a reference from the old list element. + * Add a reference to the new list element and remove from old before + * replacing it. Order is important! */ - + Tcl_IncrRefCount(valueObj); Tcl_DecrRefCount(elemPtrs[index]); + elemPtrs[index] = valueObj; - /* - * Stash the new object in the list. - */ - - elemPtrs[index] = valuePtr; - - /* - * Invalidate outdated internalreps. - */ - - ListGetInternalRep(listPtr, listRepPtr); - listRepPtr->refCount++; - TclFreeInternalRep(listPtr); - ListSetInternalRep(listPtr, listRepPtr); - listRepPtr->refCount--; - - TclInvalidateStringRep(listPtr); + /* Internal rep may be cloned so replace */ + ListObjReplaceRepAndInvalidate(listObj, &listRep); return TCL_OK; } @@ -1861,11 +3018,13 @@ TclListObjSetElement( * * FreeListInternalRep -- * - * Deallocate the storage associated with the internal representation of a - * a list object. + * Deallocate the storage associated with a list object's internal + * representation. * - * Effect + * Results: + * None. * + * Side effects: * Frees listPtr's List* internal representation, if no longer shared. * May decrement the ref counts of element objects, which may free them. * @@ -1874,21 +3033,19 @@ TclListObjSetElement( static void FreeListInternalRep( - Tcl_Obj *listPtr) /* List object with internal rep to free. */ + Tcl_Obj *listObj) /* List object with internal rep to free. */ { - List *listRepPtr; - - ListGetInternalRep(listPtr, listRepPtr); - assert(listRepPtr != NULL); - - if (listRepPtr->refCount-- <= 1) { - Tcl_Obj **elemPtrs = listRepPtr->elements; - int i, numElems = listRepPtr->elemCount; - - for (i = 0; i < numElems; i++) { - Tcl_DecrRefCount(elemPtrs[i]); - } - Tcl_Free(listRepPtr); + ListRep listRep; + + ListObjGetRep(listObj, &listRep); + if (listRep.storePtr->refCount-- <= 1) { + ObjArrayDecrRefs( + listRep.storePtr->slots, + listRep.storePtr->firstUsed, listRep.storePtr->numUsed); + Tcl_Free(listRep.storePtr); + } + if (listRep.spanPtr) { + ListSpanDecrRefs(listRep.spanPtr); } } @@ -1897,47 +3054,43 @@ FreeListInternalRep( * * DupListInternalRep -- * - * Initialize the internal representation of a list 'Tcl_Obj' to share the + * Initialize the internal representation of a list Tcl_Obj to share the * internal representation of an existing list object. * - * Effect + * Results: + * None. * - * The 'refCount' of the List internal rep is incremented. + * Side effects: + * The reference count of the List internal rep is incremented. * *---------------------------------------------------------------------- */ static void DupListInternalRep( - Tcl_Obj *srcPtr, /* Object with internal rep to copy. */ - Tcl_Obj *copyPtr) /* Object with internal rep to set. */ + Tcl_Obj *srcObj, /* Object with internal rep to copy. */ + Tcl_Obj *copyObj) /* Object with internal rep to set. */ { - List *listRepPtr; - - ListGetInternalRep(srcPtr, listRepPtr); - assert(listRepPtr != NULL); - ListSetInternalRep(copyPtr, listRepPtr); + ListRep listRep; + ListObjGetRep(srcObj, &listRep); + ListObjOverwriteRep(copyObj, &listRep); } - + /* *---------------------------------------------------------------------- * * SetListFromAny -- * - * Convert any object to a list. + * Attempt to generate a list internal form for the Tcl object "objPtr". * - * Value - * - * TCL_OK - * - * Success. The internal representation of 'objPtr' is set, and the type - * of 'objPtr' is 'tclListType'. - * - * TCL_ERROR - * - * An error occured during conversion. An error message is left in the - * interpreter's result if 'interp' is not NULL. + * Results: + * The return value is TCL_OK or TCL_ERROR. If an error occurs during + * conversion, an error message is left in the interpreter's result + * unless "interp" is NULL. * + * Side effects: + * If no error occurs, a list is stored as "objPtr"s internal + * representation. * *---------------------------------------------------------------------- */ @@ -1947,8 +3100,8 @@ SetListFromAny( Tcl_Interp *interp, /* Used for error reporting if not NULL. */ Tcl_Obj *objPtr) /* The object to convert. */ { - List *listRepPtr; Tcl_Obj **elemPtrs; + ListRep listRep; /* * Dictionaries are a special case; they have a string representation such @@ -1962,7 +3115,7 @@ SetListFromAny( Tcl_Obj *keyPtr, *valuePtr; Tcl_DictSearch search; int done; - size_t size; + ListSizeT size; /* * Create the new list representation. Note that we do not need to do @@ -1974,17 +3127,22 @@ SetListFromAny( */ Tcl_DictObjSize(NULL, objPtr, &size); - listRepPtr = AttemptNewList(interp, size > 0 ? 2*size : 1, NULL); - if (!listRepPtr) { + /* TODO - leave space in front and/or back? */ + if (ListRepInitAttempt( + interp, size > 0 ? 2 * size : 1, NULL, &listRep) + != TCL_OK) { return TCL_ERROR; } - listRepPtr->elemCount = 2 * size; - /* - * Populate the list representation. - */ + LIST_ASSERT(listRep.spanPtr == NULL); /* Guard against future changes */ + LIST_ASSERT(listRep.storePtr->firstUsed == 0); + LIST_ASSERT((listRep.storePtr->flags & LISTSTORE_CANONICAL) == 0); + + listRep.storePtr->numUsed = 2 * size; - elemPtrs = listRepPtr->elements; + /* Populate the list representation. */ + + elemPtrs = listRep.storePtr->slots; Tcl_DictObjFirst(NULL, objPtr, &search, &keyPtr, &valuePtr, &done); while (!done) { *elemPtrs++ = keyPtr; @@ -1994,7 +3152,7 @@ SetListFromAny( Tcl_DictObjNext(&search, &keyPtr, &valuePtr, &done); } } else { - size_t estCount, length; + ListSizeT estCount, length; const char *limit, *nextElem = Tcl_GetStringFromObj(objPtr, &length); /* @@ -2005,15 +3163,18 @@ SetListFromAny( estCount = TclMaxListLength(nextElem, length, &limit); estCount += (estCount == 0); /* Smallest list struct holds 1 * element. */ - listRepPtr = AttemptNewList(interp, estCount, NULL); - if (listRepPtr == NULL) { + /* TODO - allocate additional space? */ + if (ListRepInitAttempt(interp, estCount, NULL, &listRep) + != TCL_OK) { return TCL_ERROR; } - elemPtrs = listRepPtr->elements; - /* - * Each iteration, parse and store a list element. - */ + LIST_ASSERT(listRep.spanPtr == NULL); /* Guard against future changes */ + LIST_ASSERT(listRep.storePtr->firstUsed == 0); + + elemPtrs = listRep.storePtr->slots; + + /* Each iteration, parse and store a list element. */ while (nextElem < limit) { const char *elemStart; @@ -2023,11 +3184,11 @@ SetListFromAny( if (TCL_OK != TclFindElement(interp, nextElem, limit - nextElem, &elemStart, &nextElem, &elemSize, &literal)) { - fail: - while (--elemPtrs >= listRepPtr->elements) { +fail: + while (--elemPtrs >= listRep.storePtr->slots) { Tcl_DecrRefCount(*elemPtrs); } - Tcl_Free(listRepPtr); + Tcl_Free(listRep.storePtr); return TCL_ERROR; } if (elemStart == limit) { @@ -2039,11 +3200,7 @@ SetListFromAny( check = Tcl_InitStringRep(*elemPtrs, literal ? elemStart : NULL, elemSize); if (elemSize && check == NULL) { - if (interp) { - Tcl_SetObjResult(interp, Tcl_NewStringObj( - "cannot construct list, out of memory", -1)); - Tcl_SetErrorCode(interp, "TCL", "MEMORY", NULL); - } + MemoryAllocationError(interp, elemSize); goto fail; } if (!literal) { @@ -2054,16 +3211,29 @@ SetListFromAny( Tcl_IncrRefCount(*elemPtrs++);/* Since list now holds ref to it. */ } - listRepPtr->elemCount = elemPtrs - listRepPtr->elements; + listRep.storePtr->numUsed = + elemPtrs - listRep.storePtr->slots; } + LISTREP_CHECK(&listRep); + /* * Store the new internalRep. We do this as late * as possible to allow the conversion code, in particular * Tcl_GetStringFromObj, to use the old internalRep. */ - ListSetInternalRep(objPtr, listRepPtr); + /* + * Note old string representation NOT to be invalidated. + * So do NOT use ListObjReplaceRepAndInvalidate. InternalRep to be freed AFTER + * IncrRefs so do not use ListObjOverwriteRep + */ + ListRepIncrRefs(&listRep); + TclFreeInternalRep(objPtr); + objPtr->internalRep.twoPtrValue.ptr1 = listRep.storePtr; + objPtr->internalRep.twoPtrValue.ptr2 = listRep.spanPtr; + objPtr->typePtr = &tclListType; + return TCL_OK; } @@ -2072,73 +3242,84 @@ SetListFromAny( * * UpdateStringOfList -- * - * Update the string representation for a list object. - * - * Any previously-exising string representation is not invalidated, so - * storage is lost if this has not been taken care of. + * Update the string representation for a list object. Note: This + * function does not invalidate an existing old string rep so storage + * will be lost if this has not already been done. * - * Effect + * Results: + * None. * - * The string representation of 'listPtr' is set to the resulting string. - * This string will be empty if the list has no elements. It is assumed - * that the list internal representation is not NULL. + * Side effects: + * The object's string is set to a valid string that results from the + * list-to-string conversion. This string will be empty if the list has + * no elements. The list internal representation should not be NULL and + * we assume it is not NULL. * *---------------------------------------------------------------------- */ static void UpdateStringOfList( - Tcl_Obj *listPtr) /* List object with string rep to update. */ + Tcl_Obj *listObj) /* List object with string rep to update. */ { # define LOCAL_SIZE 64 char localFlags[LOCAL_SIZE], *flagPtr = NULL; - size_t numElems, i, length, bytesNeeded = 0; + ListSizeT numElems, i, length, bytesNeeded = 0; const char *elem, *start; char *dst; Tcl_Obj **elemPtrs; - List *listRepPtr; + ListRep listRep; - ListGetInternalRep(listPtr, listRepPtr); + ListObjGetRep(listObj, &listRep); + LISTREP_CHECK(&listRep); - assert(listRepPtr != NULL); - - numElems = listRepPtr->elemCount; + ListRepElements(&listRep, numElems, elemPtrs); /* * Mark the list as being canonical; although it will now have a string * rep, it is one we derived through proper "canonical" quoting and so * it's known to be free from nasties relating to [concat] and [eval]. + * However, we only do this if this is not a spanned list. Marking the + * storage canonical for a spanned list make ALL lists using the storage + * canonical which is not right. (Consider a list generated from a + * string and then this function called for a spanned list generated + * from it). On the other hand, a spanned list is always canonical + * (never generated from a string) so it does not have to be explicitly + * marked as such. The ListObjIsCanonical macro takes this into account. + * See the comments there. */ + if (listRep.spanPtr == NULL) { + LIST_ASSERT(listRep.storePtr->firstUsed == 0);/* Invariant */ + listRep.storePtr->flags |= LISTSTORE_CANONICAL; + } - listRepPtr->canonicalFlag = 1; - - /* - * Handle empty list case first, so rest of the routine is simpler. - */ + /* Handle empty list case first, so rest of the routine is simpler. */ if (numElems == 0) { - Tcl_InitStringRep(listPtr, NULL, 0); + Tcl_InitStringRep(listObj, NULL, 0); return; } - /* - * Pass 1: estimate space, gather flags. - */ + /* Pass 1: estimate space, gather flags. */ if (numElems <= LOCAL_SIZE) { flagPtr = localFlags; } else { - /* - * We know numElems <= LIST_MAX, so this is safe. - */ - + /* We know numElems <= LIST_MAX, so this is safe. */ flagPtr = (char *)Tcl_Alloc(numElems); } - elemPtrs = listRepPtr->elements; for (i = 0; i < numElems; i++) { flagPtr[i] = (i ? TCL_DONT_QUOTE_HASH : 0); elem = Tcl_GetStringFromObj(elemPtrs[i], &length); bytesNeeded += TclScanElement(elem, length, flagPtr+i); + if (bytesNeeded < 0) { + /* TODO - what is the max #define for Tcl9? */ + Tcl_Panic("max size for a Tcl value (%d bytes) exceeded", INT_MAX); + } + } + /* TODO - what is the max #define for Tcl9? */ + if (bytesNeeded > INT_MAX - numElems + 1) { + Tcl_Panic("max size for a Tcl value (%d bytes) exceeded", INT_MAX); } bytesNeeded += numElems - 1; @@ -2146,7 +3327,7 @@ UpdateStringOfList( * Pass 2: copy into string rep buffer. */ - start = dst = Tcl_InitStringRep(listPtr, NULL, bytesNeeded); + start = dst = Tcl_InitStringRep(listObj, NULL, bytesNeeded); TclOOM(dst, bytesNeeded); for (i = 0; i < numElems; i++) { flagPtr[i] |= (i ? TCL_DONT_QUOTE_HASH : 0); @@ -2156,7 +3337,7 @@ UpdateStringOfList( } /* Set the string length to what was actually written, the safe choice */ - (void) Tcl_InitStringRep(listPtr, NULL, dst - 1 - start); + (void) Tcl_InitStringRep(listObj, NULL, dst - 1 - start); if (flagPtr != localFlags) { Tcl_Free(flagPtr); diff --git a/tests-perf/comparePerf.tcl b/tests-perf/comparePerf.tcl new file mode 100644 index 0000000..f35da21 --- /dev/null +++ b/tests-perf/comparePerf.tcl @@ -0,0 +1,371 @@ +#!/usr/bin/tclsh +# ------------------------------------------------------------------------ +# +# comparePerf.tcl -- +# +# Script to compare performance data from multiple runs. +# +# ------------------------------------------------------------------------ +# +# See the file "license.terms" for information on usage and redistribution +# of this file. +# +# Usage: +# tclsh comparePerf.tcl [--regexp RE] [--ratio time|rate] [--combine] [--base BASELABEL] PERFFILE ... +# +# The test data from each input file is tabulated so as to compare the results +# of test runs. If a PERFFILE does not exist, it is retried by adding the +# .perf extension. If the --regexp is specified, only test results whose +# id matches RE are examined. +# +# If the --combine option is specified, results of test sets with the same +# label are combined and averaged in the output. +# +# If the --base option is specified, the BASELABEL is used as the label to use +# the base timing. Otherwise, the label of the first data file is used. +# +# If --ratio option is "time" the ratio of test timing vs base test timing +# is shown. If "rate" (default) the inverse is shown. +# +# If --no-header is specified, the header describing test configuration is +# not output. +# +# The format of input files is as follows: +# +# Each line must begin with one of the characters below followed by a space +# followed by a string whose semantics depend on the initial character. +# E - Full path to the Tcl executable that was used to generate the file +# V - The Tcl patchlevel of the implementation +# D - A description for the test run for human consumption +# L - A label used to identify run environment. The --combine option will +# average all measuremets that have the same label. An input file without +# a label is treated as having a unique label and not combined with any other. +# P - A test measurement (see below) +# R - The number of runs made for the each test +# # - A comment, may be an arbitrary string. Usually included in performance +# data to describe the test. This is silently ignored +# +# Any lines not matching one of the above are ignored with a warning to stderr. +# +# A line beginning with the "P" marker is a test measurement. The first word +# following is a floating point number representing the test runtime. +# The remaining line (after trimming of whitespace) is the id of the test. +# Test generators are encouraged to make the id a well-defined machine-parseable +# as well human readable description of the test. The id must not appear more +# than once. An example test measurement line: +# P 2.32280 linsert in unshared L[10000] 1 elems 10000 times at 0 (var) +# Note here the iteration count is not present. +# + +namespace eval perf::compare { + # List of dictionaries, one per input file + variable PerfData +} + +proc perf::compare::warn {message} { + puts stderr "Warning: $message" +} +proc perf::compare::print {text} { + puts stdout $text +} +proc perf::compare::slurp {testrun_path} { + variable PerfData + + set runtimes [dict create] + + set path [file normalize $testrun_path] + set fd [open $path] + array set header {} + while {[gets $fd line] >= 0} { + set line [regsub -all {\s+} [string trim $line] " "] + switch -glob -- $line { + "#*" { + # Skip comments + } + "R *" - + "L *" - + "D *" - + "V *" - + "T *" - + "E *" { + set marker [lindex $line 0] + if {[info exists header($marker)]} { + warn "Ignoring $marker record (duplicate): \"$line\"" + } + set header($marker) [string range $line 2 end] + } + "P *" { + if {[scan $line "P %f %n" runtime id_start] == 2} { + set id [string range $line $id_start end] + if {[dict exists $runtimes $id]} { + warn "Ignoring duplicate test id \"$id\"" + } else { + dict set runtimes $id $runtime + } + } else { + warn "Invalid test result line format: \"$line\"" + } + } + default { + puts stderr "Warning: ignoring unrecognized line \"$line\"" + } + } + } + close $fd + + set result [dict create Input $path Runtimes $runtimes] + foreach {c k} { + L Label + V Version + E Executable + D Description + } { + if {[info exists header($c)]} { + dict set result $k $header($c) + } + } + + return $result +} + +proc perf::compare::burp {test_sets} { + variable Options + + # Print the key for each test run + set header " " + set separator " " + foreach test_set $test_sets { + set test_set_key "\[[incr test_set_num]\]" + if {! $Options(--no-header)} { + print "$test_set_key" + foreach k {Label Executable Version Input Description} { + if {[dict exists $test_set $k]} { + print "$k: [dict get $test_set $k]" + } + } + } + append header $test_set_key $separator + set separator " "; # Expand because later columns have ratio + } + set header [string trimright $header] + + if {! $Options(--no-header)} { + print "" + if {$Options(--ratio) eq "rate"} { + set ratio_description "ratio of baseline to the measurement (higher is faster)." + } else { + set ratio_description "ratio of measurement to the baseline (lower is faster)." + } + print "The first column \[1\] is the baseline measurement." + print "Subsequent columns are pairs of the additional measurement and " + print $ratio_description + print "" + } + + # Print the actual test run data + + print $header + set test_sets [lassign $test_sets base_set] + set fmt {%#10.5f} + set fmt_ratio {%-6.2f} + foreach {id base_runtime} [dict get $base_set Runtimes] { + if {[info exists Options(--regexp)]} { + if {![regexp $Options(--regexp) $id]} { + continue + } + } + if {$Options(--print-test-number)} { + set line "[format %-4s [incr counter].]" + } else { + set line "" + } + append line [format $fmt $base_runtime] + foreach test_set $test_sets { + if {[dict exists $test_set Runtimes $id]} { + set runtime [dict get $test_set Runtimes $id] + if {$Options(--ratio) eq "time"} { + if {$base_runtime != 0} { + set ratio [format $fmt_ratio [expr {$runtime/$base_runtime}]] + } else { + if {$runtime == 0} { + set ratio "NaN " + } else { + set ratio "Inf " + } + } + } else { + if {$runtime != 0} { + set ratio [format $fmt_ratio [expr {$base_runtime/$runtime}]] + } else { + if {$base_runtime == 0} { + set ratio "NaN " + } else { + set ratio "Inf " + } + } + } + append line "|" [format $fmt $runtime] "|" $ratio + } else { + append line [string repeat { } 11] + } + } + append line "|" $id + print $line + } +} + +proc perf::compare::chew {test_sets} { + variable Options + + # Combine test sets that have the same label, averaging the values + set unlabeled_sets {} + array set labeled_sets {} + + foreach test_set $test_sets { + # If there is no label, treat as independent set + if {![dict exists $test_set Label]} { + lappend unlabeled_sets $test_set + } else { + lappend labeled_sets([dict get $test_set Label]) $test_set + } + } + + foreach label [array names labeled_sets] { + set combined_set [lindex $labeled_sets($label) 0] + set runtimes [dict get $combined_set Runtimes] + foreach test_set [lrange $labeled_sets($label) 1 end] { + dict for {id timing} [dict get $test_set Runtimes] { + dict lappend runtimes $id $timing + } + } + dict for {id timings} $runtimes { + set total [tcl::mathop::+ {*}$timings] + dict set runtimes $id [expr {$total/[llength $timings]}] + } + dict set combined_set Runtimes $runtimes + set labeled_sets($label) $combined_set + } + + # Choose the "base" test set + if {![info exists Options(--base)]} { + set first_set [lindex $test_sets 0] + if {[dict exists $first_set Label]} { + # Use label of first as the base + set Options(--base) [dict get $first_set Label] + } + } + + if {[info exists Options(--base)] && $Options(--base) ne ""} { + lappend combined_sets $labeled_sets($Options(--base));# Will error if no such + unset labeled_sets($Options(--base)) + } else { + lappend combined_sets [lindex $unlabeled_sets 0] + set unlabeled_sets [lrange $unlabeled_sets 1 end] + } + foreach label [array names labeled_sets] { + lappend combined_sets $labeled_sets($label) + } + lappend combined_sets {*}$unlabeled_sets + + return $combined_sets +} + +proc perf::compare::setup {argv} { + variable Options + + array set Options { + --ratio rate + --combine 0 + --print-test-number 0 + --no-header 0 + } + while {[llength $argv]} { + set argv [lassign $argv arg] + switch -glob -- $arg { + -r - + --regexp { + if {[llength $argv] == 0} { + error "Missing value for option $arg" + } + set argv [lassign $argv val] + set Options(--regexp) $val + } + --ratio { + if {[llength $argv] == 0} { + error "Missing value for option $arg" + } + set argv [lassign $argv val] + if {$val ni {time rate}} { + error "Value for option $arg must be either \"time\" or \"rate\"" + } + set Options(--ratio) $val + } + --print-test-number - + --combine - + --no-header { + set Options($arg) 1 + } + --base { + if {[llength $argv] == 0} { + error "Missing value for option $arg" + } + set argv [lassign $argv val] + set Options($arg) $val + } + -- { + # Remaining will be passed back to the caller + break + } + --* { + error "Unknown option $arg" + } + -* { + error "Unknown option -[lindex $arg 0]" + } + default { + # Remaining will be passed back to the caller + set argv [linsert $argv 0 $arg] + break; + } + } + } + + set paths {} + foreach path $argv { + set path [file join $path]; # Convert from native else glob fails + if {[file isfile $path]} { + lappend paths $path + continue + } + if {[file isfile $path.perf]} { + lappend paths $path.perf + continue + } + lappend paths {*}[glob -nocomplain $path] + } + return $paths +} +proc perf::compare::main {} { + variable Options + + set paths [setup $::argv] + if {[llength $paths] == 0} { + error "No test data files specified." + } + set test_data [list ] + set seen [dict create] + foreach path $paths { + if {![dict exists $seen $path]} { + lappend test_data [slurp $path] + dict set seen $path "" + } + } + + if {$Options(--combine)} { + set test_data [chew $test_data] + } + + burp $test_data +} + +perf::compare::main diff --git a/tests-perf/listPerf.tcl b/tests-perf/listPerf.tcl new file mode 100644 index 0000000..4472810 --- /dev/null +++ b/tests-perf/listPerf.tcl @@ -0,0 +1,1290 @@ +#!/usr/bin/tclsh +# ------------------------------------------------------------------------ +# +# listPerf.tcl -- +# +# This file provides performance tests for list operations. +# +# ------------------------------------------------------------------------ +# +# See the file "license.terms" for information on usage and redistribution +# of this file. +# +# Note: this file does not use the test-performance.tcl framework as we want +# more direct control over timerate options. + +catch {package require twapi} + +namespace eval perf::list { + variable perfScript [file normalize [info script]] + + # Test for each of these lengths + variable Lengths {10 100 1000 10000} + + variable RunTimes + set RunTimes(command) 0.0 + set RunTimes(total) 0.0 + + variable Options + array set Options { + --print-comments 0 + --print-iterations 0 + } + + # Procs used for calibrating overhead + proc proc2args {a b} {} + proc proc3args {a b c} {} + + proc print {s} { + puts $s + } + proc print_usage {} { + puts stderr "Usage: [file tail [info nameofexecutable]] $::argv0 \[options\] \[command ...\]" + puts stderr "\t--description DESC\tHuman readable description of test run" + puts stderr "\t--label LABEL\tA label used to identify test environment" + puts stderr "\t--print-comments\tPrint comment for each test" + puts stderr "\t--print-iterations\tPrint number of iterations run for each test" + } + + proc setup {argv} { + variable Options + variable Lengths + + while {[llength $argv]} { + set argv [lassign $argv arg] + switch -glob -- $arg { + --print-comments - + --print-iterations { + set Options($arg) 1 + } + --label - + --description { + if {[llength $argv] == 0} { + error "Missing value for option $arg" + } + set argv [lassign $argv val] + set Options($arg) $val + } + --lengths { + if {[llength $argv] == 0} { + error "Missing value for option $arg" + } + set argv [lassign $argv val] + set Lengths $val + } + -- { + # Remaining will be passed back to the caller + break + } + --* { + error "Unknown option $arg" + } + default { + # Remaining will be passed back to the caller + set argv [linsert $argv 0 $arg] + break; + } + } + } + + return $argv + } + proc format_timings {us iters} { + variable Options + if {!$Options(--print-iterations)} { + return "[format {%#10.4f} $us]" + } + return "[format {%#10.4f} $us] [format {%8d} $iters]" + } + proc measure {id script args} { + variable NullOverhead + variable RunTimes + variable Options + + set opts(-overhead) "" + set opts(-runs) 5 + while {[llength $args]} { + set args [lassign $args opt] + if {[llength $args] == 0} { + error "No argument supplied for $opt option. Test: $id" + } + set args [lassign $args val] + switch $opt { + -setup - + -cleanup - + -overhead - + -time - + -runs - + -reps { + set opts($opt) $val + } + default { + error "Unknown option $opt. Test: $id" + } + } + } + + set timerate_args {} + if {[info exists opts(-time)]} { + lappend timerate_args $opts(-time) + } + if {[info exists opts(-reps)]} { + if {[info exists opts(-time)]} { + set timerate_args [list $opts(-time) $opts(-reps)] + } else { + # Force the default for first time option + set timerate_args [list 1000 $opts(-reps)] + } + } elseif {[info exists opts(-time)]} { + set timerate_args [list $opts(-time)] + } + if {[info exists opts(-setup)]} { + uplevel 1 $opts(-setup) + } + # Cache the empty overhead to prevent unnecessary delays. Note if you modify + # to cache other scripts, the cache key must be AFTER substituting the + # overhead script in the caller's context. + if {$opts(-overhead) eq ""} { + if {![info exists NullOverhead]} { + set NullOverhead [lindex [timerate {}] 0] + } + set overhead_us $NullOverhead + } else { + # The overhead measurements might use setup so we need to setup + # first and then cleanup in preparation for setting up again for + # the script to be measured + if {[info exists opts(-setup)]} { + uplevel 1 $opts(-setup) + } + set overhead_us [lindex [uplevel 1 [list timerate $opts(-overhead)]] 0] + if {[info exists opts(-cleanup)]} { + uplevel 1 $opts(-cleanup) + } + } + set timings {} + for {set i 0} {$i < $opts(-runs)} {incr i} { + if {[info exists opts(-setup)]} { + uplevel 1 $opts(-setup) + } + lappend timings [uplevel 1 [list timerate -overhead $overhead_us $script {*}$timerate_args]] + if {[info exists opts(-cleanup)]} { + uplevel 1 $opts(-cleanup) + } + } + set timings [lsort -real -index 0 $timings] + if {$opts(-runs) > 15} { + set ignore [expr {$opts(-runs)/8}] + } elseif {$opts(-runs) >= 5} { + set ignore 2 + } else { + set ignore 0 + } + # Ignore highest and lowest + set timings [lrange $timings 0 end-$ignore] + # Average it out + set us 0 + set iters 0 + foreach timing $timings { + set us [expr {$us + [lindex $timing 0]}] + set iters [expr {$iters + [lindex $timing 2]}] + } + set us [expr {$us/[llength $timings]}] + set iters [expr {$iters/[llength $timings]}] + + set RunTimes(command) [expr {$RunTimes(command) + $us}] + print "P [format_timings $us $iters] $id" + } + proc comment {args} { + variable Options + if {$Options(--print-comments)} { + print "# [join $args { }]" + } + } + proc spanned_list {len} { + # Note - for small len, this will not create a spanned list + set delta [expr {$len/8}] + return [lrange [lrepeat [expr {$len+(2*$delta)}] a] $delta [expr {$delta+$len-1}]] + } + proc print_separator {command} { + comment [string repeat = 80] + comment Command: $command + } + + oo::class create ListPerf { + constructor {args} { + my variable Opts + # Note default Opts can be overridden in construct as well as in measure + set Opts [dict merge { + -setup { + set L [lrepeat $len a] + set Lspan [perf::list::spanned_list $len] + } -cleanup { + unset -nocomplain L + unset -nocomplain Lspan + unset -nocomplain L2 + } + } $args] + } + method measure {comment script locals args} { + my variable Opts + dict with locals {} + ::perf::list::measure $comment $script {*}[dict merge $Opts $args] + } + method option {opt val} { + my variable Opts + dict set Opts $opt $val + } + method option_unset {opt} { + my variable Opts + unset -nocomplain Opts($opt) + } + } + + proc linsert_describe {share_mode len at num iters} { + return "linsert L\[$len\] $share_mode $num elems $iters times at $at" + } + proc linsert_perf {} { + variable Lengths + + print_separator linsert + + ListPerf create perf -overhead {set L {}} -time 1000 + + # Note: Const indices take different path through bytecode than variable + # indices hence separate cases below + + + # Var case + foreach share_mode {shared unshared} { + set idx 0 + if {$share_mode eq "shared"} { + comment == Insert into empty lists + comment Insert one element into empty list + measure [linsert_describe shared 0 "0 (var)" 1 1] {linsert $L $idx ""} -setup {set idx 0; set L {}} + } else { + comment == Insert into empty lists + comment Insert one element into empty list + measure [linsert_describe unshared 0 "0 (var)" 1 1] {linsert {} $idx ""} -setup {set idx 0} + } + foreach idx_str [list 0 1 mid end-1 end] { + foreach len $Lengths { + if {$idx_str eq "mid"} { + set idx [expr {$len/2}] + } else { + set idx $idx_str + } + # perf option -reps $reps + set reps 1000 + if {$share_mode eq "shared"} { + comment Insert once to shared list with variable index + perf measure [linsert_describe shared $len "$idx (var)" 1 1] \ + {linsert $L $idx x} [list len $len idx $idx] -overhead {} -reps 100000 + + comment Insert multiple times to shared list with variable index + perf measure [linsert_describe shared $len "$idx (var)" 1 $reps] { + set L [linsert $L $idx X] + } [list len $len idx $idx] -reps $reps + + comment Insert multiple items multiple times to shared list with variable index + perf measure [linsert_describe shared $len "$idx (var)" 5 $reps] { + set L [linsert $L $idx X X X X X] + } [list len $len idx $idx] -reps $reps + } else { + # NOTE : the Insert once case is left out for unshared lists + # because it requires re-init on every iteration resulting + # in a lot of measurement noise + comment Insert multiple times to unshared list with variable index + perf measure [linsert_describe unshared $len "$idx (var)" 1 $reps] { + set L [linsert $L[set L {}] $idx X] + } [list len $len idx $idx] -reps $reps + comment Insert multiple items multiple times to unshared list with variable index + perf measure [linsert_describe unshared $len "$idx (var)" 5 $reps] { + set L [linsert $L[set L {}] $idx X X X X X] + } [list len $len idx $idx] -reps $reps + } + } + } + } + + # Const index + foreach share_mode {shared unshared} { + if {$share_mode eq "shared"} { + comment == Insert into empty lists + comment Insert one element into empty list + measure [linsert_describe shared 0 "0 (const)" 1 1] {linsert $L 0 ""} -setup {set L {}} + } else { + comment == Insert into empty lists + comment Insert one element into empty list + measure [linsert_describe unshared 0 "0 (const)" 1 1] {linsert {} 0 ""} + } + foreach idx_str [list 0 1 mid end end-1] { + foreach len $Lengths { + # Note end, end-1 explicitly calculated as otherwise they + # are not treated as const + if {$idx_str eq "mid"} { + set idx [expr {$len/2}] + } elseif {$idx_str eq "end"} { + set idx [expr {$len-1}] + } elseif {$idx_str eq "end-1"} { + set idx [expr {$len-2}] + } else { + set idx $idx_str + } + #perf option -reps $reps + set reps 100 + if {$share_mode eq "shared"} { + comment Insert once to shared list with const index + perf measure [linsert_describe shared $len "$idx (const)" 1 1] \ + "linsert \$L $idx x" [list len $len] -overhead {} -reps 10000 + + comment Insert multiple times to shared list with const index + perf measure [linsert_describe shared $len "$idx (const)" 1 $reps] \ + "set L \[linsert \$L $idx X\]" [list len $len] -reps $reps + + comment Insert multiple items multiple times to shared list with const index + perf measure [linsert_describe shared $len "$idx (const)" 5 $reps] \ + "set L \[linsert \$L $idx X X X X X\]" [list len $len] -reps $reps + } else { + comment Insert multiple times to unshared list with const index + perf measure [linsert_describe unshared $len "$idx (const)" 1 $reps] \ + "set L \[linsert \$L\[set L {}\] $idx X]" [list len $len] -reps $reps + + comment Insert multiple items multiple times to unshared list with const index + perf measure [linsert_describe unshared $len "$idx (const)" 5 $reps] \ + "set L \[linsert \$L\[set L {}\] $idx X X X X X]" [list len $len] -reps $reps + } + } + } + } + + # Note: no span tests because the inserts above will themselves create + # spanned lists + + perf destroy + } + + proc list_describe {len text} { + return "list L\[$len\] $text" + } + proc list_perf {} { + variable Lengths + + print_separator list + + ListPerf create perf + foreach len $Lengths { + set s [join [lrepeat $len x]] + comment Create a list from a string + perf measure [list_describe $len "from a string"] {list $s} [list s $s len $len] + } + foreach len $Lengths { + comment Create a list from expansion - single list (special optimal case) + perf measure [list_describe $len "from a {*}list"] {list {*}$L} [list len $len] + comment Create a list from two lists - real test of expansion speed + perf measure [list_describe $len "from a {*}list {*}list"] {list {*}$L {*}$L} [list len [expr {$len/2}]] + } + } + + proc lappend_describe {share_mode len num iters} { + return "lappend L\[$len\] $share_mode $num elems $iters times" + } + proc lappend_perf {} { + variable Lengths + + print_separator lappend + + ListPerf create perf -setup {set L [lrepeat [expr {$len/4}] x]} + + # Shared + foreach len $Lengths { + comment Append to a shared list variable multiple times + perf measure [lappend_describe shared [expr {$len/2}] 1 $len] { + set L2 $L; # Make shared + lappend L x + } [list len $len] -reps $len -overhead {set L2 $L} + } + + # Unshared + foreach len $Lengths { + comment Append to a unshared list variable multiple times + perf measure [lappend_describe unshared [expr {$len/2}] 1 $len] { + lappend L x + } [list len $len] -reps $len + } + + # Span + foreach len $Lengths { + comment Append to a unshared-span list variable multiple times + perf measure [lappend_describe unshared-span [expr {$len/2}] 1 $len] { + lappend Lspan x + } [list len $len] -reps $len + } + + perf destroy + } + + proc lpop_describe {share_mode len at reps} { + return "lpop L\[$len\] $share_mode at $at $reps times" + } + proc lpop_perf {} { + variable Lengths + + print_separator lpop + + ListPerf create perf + + # Shared + perf option -overhead {set L2 $L} + foreach len $Lengths { + set reps [expr {($len >= 1000 ? ($len/2) : $len) - 2}] + foreach idx {0 1 end-1 end} { + comment Pop element at position $idx from a shared list variable + perf measure [lpop_describe shared $len $idx $reps] { + set L2 $L + lpop L $idx + } [list len $len idx $idx] -reps $reps + } + } + + # Unshared + perf option -overhead {} + foreach len $Lengths { + set reps [expr {($len >= 1000 ? ($len/2) : $len) - 2}] + foreach idx {0 1 end-1 end} { + comment Pop element at position $idx from an unshared list variable + perf measure [lpop_describe unshared $len $idx $reps] { + lpop L $idx + } [list len $len idx $idx] -reps $reps + } + } + + perf destroy + + # Nested + ListPerf create perf -setup { + set L [lrepeat $len [list a b]] + } + + # Shared, nested index + perf option -overhead {set L2 $L; set L L2} + foreach len $Lengths { + set reps [expr {($len >= 1000 ? ($len/2) : $len) - 2}] + foreach idx {0 1 end-1 end} { + perf measure [lpop_describe shared $len "{$idx 0}" $reps] { + set L2 $L + lpop L $idx 0 + set L $L2 + } [list len $len idx $idx] -reps $reps + } + } + + # TODO - Nested Unshared + # Not sure how to measure performance. When unshared there is no copy + # so deleting a nested index repeatedly is not feasible + + perf destroy + } + + proc lassign_describe {share_mode len num reps} { + return "lassign L\[$len\] $share_mode $num elems $reps times" + } + proc lassign_perf {} { + variable Lengths + + print_separator lassign + + ListPerf create perf + + foreach share_mode {shared unshared} { + foreach len $Lengths { + if {$share_mode eq "shared"} { + set reps 1000 + comment Reflexive lassign - shared + perf measure [lassign_describe shared $len 1 $reps] { + set L2 $L + set L2 [lassign $L2 v] + } [list len $len] -overhead {set L2 $L} -reps $reps + + comment Reflexive lassign - shared, multiple + perf measure [lassign_describe shared $len 5 $reps] { + set L2 $L + set L2 [lassign $L2 a b c d e] + } [list len $len] -overhead {set L2 $L} -reps $reps + } else { + set reps [expr {($len >= 1000 ? ($len/2) : $len) - 2}] + comment Reflexive lassign - unshared + perf measure [lassign_describe unshared $len 1 $reps] { + set L [lassign $L v] + } [list len $len] -reps $reps + } + } + } + perf destroy + } + + proc lrepeat_describe {len num} { + return "lrepeat L\[$len\] $num elems at a time" + } + proc lrepeat_perf {} { + variable Lengths + + print_separator lrepeat + + ListPerf create perf -reps 100000 + foreach len $Lengths { + comment Generate a list from a single repeated element + perf measure [lrepeat_describe $len 1] { + lrepeat $len a + } [list len $len] + + comment Generate a list from multiple repeated elements + perf measure [lrepeat_describe $len 5] { + lrepeat $len a b c d e + } [list len $len] + } + + perf destroy + } + + proc lreverse_describe {share_mode len} { + return "lreverse L\[$len\] $share_mode" + } + proc lreverse_perf {} { + variable Lengths + + print_separator lreverse + + ListPerf create perf -reps 10000 + + foreach share_mode {shared unshared} { + foreach len $Lengths { + if {$share_mode eq "shared"} { + comment Reverse a shared list + perf measure [lreverse_describe shared $len] { + lreverse $L + } [list len $len] + + if {$len > 100} { + comment Reverse a shared-span list + perf measure [lreverse_describe shared-span $len] { + lreverse $Lspan + } [list len $len] + } + } else { + comment Reverse a unshared list + perf measure [lreverse_describe unshared $len] { + set L [lreverse $L[set L {}]] + } [list len $len] -overhead {set L $L; set L {}} + + if {$len >= 100} { + comment Reverse a unshared-span list + perf measure [lreverse_describe unshared-span $len] { + set Lspan [lreverse $Lspan[set Lspan {}]] + } [list len $len] -overhead {set Lspan $Lspan; set Lspan {}} + } + } + } + } + + perf destroy + } + + proc llength_describe {share_mode len} { + return "llength L\[$len\] $share_mode" + } + proc llength_perf {} { + variable Lengths + + print_separator llength + + ListPerf create perf -reps 100000 + + foreach len $Lengths { + comment Length of a list + perf measure [llength_describe shared $len] { + llength $L + } [list len $len] + + if {$len >= 100} { + comment Length of a span list + perf measure [llength_describe shared-span $len] { + llength $Lspan + } [list len $len] + } + } + + perf destroy + } + + proc lindex_describe {share_mode len at} { + return "lindex L\[$len\] $share_mode at $at" + } + proc lindex_perf {} { + variable Lengths + + print_separator lindex + + ListPerf create perf -reps 100000 + + foreach len $Lengths { + comment Index into a list + set idx [expr {$len/2}] + perf measure [lindex_describe shared $len $idx] { + lindex $L $idx + } [list len $len idx $idx] + + if {$len >= 100} { + comment Index into a span list + perf measure [lindex_describe shared-span $len $idx] { + lindex $Lspan $idx + } [list len $len idx $idx] + } + } + + perf destroy + } + + proc lrange_describe {share_mode len range} { + return "lrange L\[$len\] $share_mode range $range" + } + + proc lrange_perf {} { + variable Lengths + + print_separator lrange + + ListPerf create perf -time 1000 -reps 100000 + + foreach share_mode {shared unshared} { + foreach len $Lengths { + set eighth [expr {$len/8}] + set ranges [list \ + [list 0 0] [list 0 end-1] \ + [list $eighth [expr {3*$eighth}]] \ + [list $eighth [expr {7*$eighth}]] \ + [list 1 end] [list end-1 end] \ + ] + foreach range $ranges { + comment Range $range in $share_mode list of length $len + if {$share_mode eq "shared"} { + perf measure [lrange_describe shared $len $range] \ + "lrange \$L $range" [list len $len range $range] + } else { + perf measure [lrange_describe unshared $len $range] \ + "lrange \[lrepeat \$len\ a] $range" \ + [list len $len range $range] -overhead {lrepeat $len a} + } + } + + if {$len >= 100} { + foreach range $ranges { + comment Range $range in ${share_mode}-span list of length $len + if {$share_mode eq "shared"} { + perf measure [lrange_describe shared-span $len $range] \ + "lrange \$Lspan {*}$range" [list len $len range $range] + } else { + perf measure [lrange_describe unshared-span $len $range] \ + "lrange \[perf::list::spanned_list \$len\] $range" \ + [list len $len range $range] -overhead {perf::list::spanned_list $len} + } + } + } + } + } + + perf destroy + } + + proc lset_describe {share_mode len at} { + return "lset L\[$len\] $share_mode at $at" + } + proc lset_perf {} { + variable Lengths + + print_separator lset + + ListPerf create perf -reps 10000 + + # Shared + foreach share_mode {shared unshared} { + foreach len $Lengths { + foreach idx {0 1 end-1 end end+1} { + comment lset at position $idx in a $share_mode list variable + if {$share_mode eq "shared"} { + perf measure [lset_describe shared $len $idx] { + set L2 $L + lset L $idx X + } [list len $len idx $idx] -overhead {set L2 $L} + } else { + perf measure [lset_describe unshared $len $idx] { + lset L $idx X + } [list len $len idx $idx] + } + } + } + } + + perf destroy + + # Nested + ListPerf create perf -setup { + set L [lrepeat $len [list a b]] + } + + foreach share_mode {shared unshared} { + foreach len $Lengths { + foreach idx {0 1 end-1 end} { + comment lset at position $idx in a $share_mode list variable + if {$share_mode eq "shared"} { + perf measure [lset_describe shared $len "{$idx 0}"] { + set L2 $L + lset L $idx 0 X + } [list len $len idx $idx] -overhead {set L2 $L} + } else { + perf measure [lset_describe unshared $len "{$idx 0}"] { + lset L $idx 0 {X Y} + } [list len $len idx $idx] + } + } + } + } + + perf destroy + } + + proc lremove_describe {share_mode len at nremoved} { + return "lremove L\[$len\] $share_mode $nremoved elements at $at" + } + proc lremove_perf {} { + variable Lengths + + print_separator lremove + + ListPerf create perf -reps 10000 + + foreach share_mode {shared unshared} { + foreach len $Lengths { + foreach idx [list 0 1 [expr {$len/2}] end-1 end] { + if {$share_mode eq "shared"} { + comment Remove one element from shared list + perf measure [lremove_describe shared $len $idx 1] \ + {lremove $L $idx} [list len $len idx $idx] + + } else { + comment Remove one element from unshared list + set reps [expr {$len >= 1000 ? ($len/8) : ($len-2)}] + perf measure [lremove_describe unshared $len $idx 1] \ + {set L [lremove $L[set L {}] $idx]} [list len $len idx $idx] \ + -overhead {set L $L; set L {}} -reps $reps + } + } + if {$share_mode eq "shared"} { + comment Remove multiple elements from shared list + perf measure [lremove_describe shared $len [list 0 1 [expr {$len/2}] end-1 end] 5] { + lremove $L 0 1 [expr {$len/2}] end-1 end + } [list len $len] + } + } + # Span + foreach len $Lengths { + foreach idx [list 0 1 [expr {$len/2}] end-1 end] { + if {$share_mode eq "shared"} { + comment Remove one element from shared-span list + perf measure [lremove_describe shared-span $len $idx 1] \ + {lremove $Lspan $idx} [list len $len idx $idx] + } else { + comment Remove one element from unshared-span list + set reps [expr {$len >= 1000 ? ($len/8) : ($len-2)}] + perf measure [lremove_describe unshared-span $len $idx 1] \ + {set Lspan [lremove $Lspan[set Lspan {}] $idx]} [list len $len idx $idx] \ + -overhead {set Lspan $Lspan; set Lspan {}} -reps $reps + } + } + if {$share_mode eq "shared"} { + comment Remove multiple elements from shared-span list + perf measure [lremove_describe shared-span $len [list 0 1 [expr {$len/2}] end-1 end] 5] { + lremove $Lspan 0 1 [expr {$len/2}] end-1 end + } [list len $len] + } + } + } + + perf destroy + } + + proc lreplace_describe {share_mode len first last ninsert {times 1}} { + if {$last < $first} { + return "lreplace L\[$len\] $share_mode 0 ($first:$last) elems at $first with $ninsert elems $times times." + } + return "lreplace L\[$len\] $share_mode $first:$last with $ninsert elems $times times." + } + proc lreplace_perf {} { + variable Lengths + + print_separator lreplace + + set default_reps 10000 + ListPerf create perf -reps $default_reps + + foreach share_mode {shared unshared} { + # Insert only + foreach len $Lengths { + set reps [expr {$len <= 100 ? ($len-2) : ($len/8)}] + foreach first [list 0 1 [expr {$len/2}] end-1 end] { + if {$share_mode eq "shared"} { + comment Insert one to shared list + perf measure [lreplace_describe shared $len $first -1 1] { + lreplace $L $first -1 x + } [list len $len first $first] + + comment Insert multiple to shared list + perf measure [lreplace_describe shared $len $first -1 10] { + lreplace $L $first -1 X X X X X X X X X X + } [list len $len first $first] + + comment Insert one to shared list repeatedly + perf measure [lreplace_describe shared $len $first -1 1 $reps] { + set L [lreplace $L $first -1 x] + } [list len $len first $first] -reps $reps + + comment Insert multiple to shared list repeatedly + perf measure [lreplace_describe shared $len $first -1 10 $reps] { + set L [lreplace $L $first -1 X X X X X X X X X X] + } [list len $len first $first] -reps $reps + + } else { + comment Insert one to unshared list + perf measure [lreplace_describe unshared $len $first -1 1] { + set L [lreplace $L[set L {}] $first -1 x] + } [list len $len first $first] -overhead { + set L $L; set L {} + } -reps $reps + + comment Insert multiple to unshared list + perf measure [lreplace_describe unshared $len $first -1 10] { + set L [lreplace $L[set L {}] $first -1 X X X X X X X X X X] + } [list len $len first $first] -overhead { + set L $L; set L {} + } -reps $reps + } + } + } + + # Delete only + foreach len $Lengths { + set reps [expr {$len <= 100 ? ($len-2) : ($len/8)}] + foreach first [list 0 1 [expr {$len/2}] end-1 end] { + if {$share_mode eq "shared"} { + comment Delete one from shared list + perf measure [lreplace_describe shared $len $first $first 0] { + lreplace $L $first $first + } [list len $len first $first] + } else { + comment Delete one from unshared list + perf measure [lreplace_describe unshared $len $first $first 0] { + set L [lreplace $L[set L {}] $first $first x] + } [list len $len first $first] -overhead { + set L $L; set L {} + } -reps $reps + } + } + } + + # Insert + delete + foreach len $Lengths { + set reps [expr {$len <= 100 ? ($len-2) : ($len/8)}] + foreach range [list {0 1} {1 2} {end-2 end-1} {end-1 end}] { + lassign $range first last + if {$share_mode eq "shared"} { + comment Insertions more than deletions from shared list + perf measure [lreplace_describe shared $len $first $last 3] { + lreplace $L $first $last X Y Z + } [list len $len first $first last $last] + + comment Insertions same as deletions from shared list + perf measure [lreplace_describe shared $len $first $last 2] { + lreplace $L $first $last X Y + } [list len $len first $first last $last] + + comment Insertions fewer than deletions from shared list + perf measure [lreplace_describe shared $len $first $last 1] { + lreplace $L $first $last X + } [list len $len first $first last $last] + } else { + comment Insertions more than deletions from unshared list + perf measure [lreplace_describe unshared $len $first $last 3] { + set L [lreplace $L[set L {}] $first $last X Y Z] + } [list len $len first $first last $last] -overhead { + set L $L; set L {} + } -reps $reps + + comment Insertions same as deletions from unshared list + perf measure [lreplace_describe unshared $len $first $last 2] { + set L [lreplace $L[set L {}] $first $last X Y ] + } [list len $len first $first last $last] -overhead { + set L $L; set L {} + } -reps $reps + + comment Insertions fewer than deletions from unshared list + perf measure [lreplace_describe unshared $len $first $last 1] { + set L [lreplace $L[set L {}] $first $last X] + } [list len $len first $first last $last] -overhead { + set L $L; set L {} + } -reps $reps + } + } + } + # Spanned Insert + delete + foreach len $Lengths { + set reps [expr {$len <= 100 ? ($len-2) : ($len/8)}] + foreach range [list {0 1} {1 2} {end-2 end-1} {end-1 end}] { + lassign $range first last + if {$share_mode eq "shared"} { + comment Insertions more than deletions from shared-span list + perf measure [lreplace_describe shared-span $len $first $last 3] { + lreplace $Lspan $first $last X Y Z + } [list len $len first $first last $last] + + comment Insertions same as deletions from shared-span list + perf measure [lreplace_describe shared-span $len $first $last 2] { + lreplace $Lspan $first $last X Y + } [list len $len first $first last $last] + + comment Insertions fewer than deletions from shared-span list + perf measure [lreplace_describe shared-span $len $first $last 1] { + lreplace $Lspan $first $last X + } [list len $len first $first last $last] + } else { + comment Insertions more than deletions from unshared-span list + perf measure [lreplace_describe unshared-span $len $first $last 3] { + set Lspan [lreplace $Lspan[set Lspan {}] $first $last X Y Z] + } [list len $len first $first last $last] -overhead { + set Lspan $Lspan; set Lspan {} + } -reps $reps + + comment Insertions same as deletions from unshared-span list + perf measure [lreplace_describe unshared-span $len $first $last 2] { + set Lspan [lreplace $Lspan[set Lspan {}] $first $last X Y ] + } [list len $len first $first last $last] -overhead { + set Lspan $Lspan; set Lspan {} + } -reps $reps + + comment Insertions fewer than deletions from unshared-span list + perf measure [lreplace_describe unshared-span $len $first $last 1] { + set Lspan [lreplace $Lspan[set Lspan {}] $first $last X] + } [list len $len first $first last $last] -overhead { + set Lspan $Lspan; set Lspan {} + } -reps $reps + } + } + } + } + + perf destroy + } + + proc split_describe {len} { + return "split L\[$len\]" + } + proc split_perf {} { + variable Lengths + print_separator split + + ListPerf create perf -setup {set S [string repeat "x " $len]} + foreach len $Lengths { + comment Split a string + perf measure [split_describe $len] { + split $S " " + } [list len $len] + } + } + + proc join_describe {share_mode len} { + return "join L\[$len\] $share_mode" + } + proc join_perf {} { + variable Lengths + + print_separator join + + ListPerf create perf -reps 10000 + foreach len $Lengths { + comment Join a list + perf measure [join_describe shared $len] { + join $L + } [list len $len] + } + foreach len $Lengths { + comment Join a spanned list + perf measure [join_describe shared-span $len] { + join $Lspan + } [list len $len] + } + perf destroy + } + + proc lsearch_describe {share_mode len} { + return "lsearch L\[$len\] $share_mode" + } + proc lsearch_perf {} { + variable Lengths + + print_separator lsearch + + ListPerf create perf -reps 100000 + foreach len $Lengths { + comment Search a list + perf measure [lsearch_describe shared $len] { + lsearch $L needle + } [list len $len] + } + foreach len $Lengths { + comment Search a spanned list + perf measure [lsearch_describe shared-span $len] { + lsearch $Lspan needle + } [list len $len] + } + perf destroy + } + + proc foreach_describe {share_mode len} { + return "foreach L\[$len\] $share_mode" + } + proc foreach_perf {} { + variable Lengths + + print_separator foreach + + ListPerf create perf -reps 10000 + foreach len $Lengths { + comment Iterate through a list + perf measure [foreach_describe shared $len] { + foreach e $L {} + } [list len $len] + } + foreach len $Lengths { + comment Iterate a spanned list + perf measure [foreach_describe shared-span $len] { + foreach e $Lspan {} + } [list len $len] + } + perf destroy + } + + proc lmap_describe {share_mode len} { + return "lmap L\[$len\] $share_mode" + } + proc lmap_perf {} { + variable Lengths + + print_separator lmap + + ListPerf create perf -reps 10000 + foreach len $Lengths { + comment Iterate through a list + perf measure [lmap_describe shared $len] { + lmap e $L {} + } [list len $len] + } + foreach len $Lengths { + comment Iterate a spanned list + perf measure [lmap_describe shared-span $len] { + lmap e $Lspan {} + } [list len $len] + } + perf destroy + } + + proc get_sort_sample {{spanned 0}} { + variable perfScript + variable sortSampleText + + if {![info exists sortSampleText]} { + set fd [open $perfScript] + set sortSampleText [split [read $fd] ""] + close $fd + } + set sortSampleText [string range $sortSampleText 0 9999] + + # NOTE: do NOT cache list result in a variable as we need it unshared + if {$spanned} { + return [lrange [split $sortSampleText ""] 1 end-1] + } else { + return [split $sortSampleText ""] + } + } + proc lsort_describe {share_mode len} { + return "lsort L\[$len] $share_mode" + } + proc lsort_perf {} { + print_separator lsort + + ListPerf create perf -setup {} + + comment Sort a shared list + perf measure [lsort_describe shared [llength [perf::list::get_sort_sample]]] { + lsort $L + } {} -setup {set L [perf::list::get_sort_sample]} + + comment Sort a shared-span list + perf measure [lsort_describe shared-span [llength [perf::list::get_sort_sample 1]]] { + lsort $L + } {} -setup {set L [perf::list::get_sort_sample 1]} + + comment Sort an unshared list + perf measure [lsort_describe unshared [llength [perf::list::get_sort_sample]]] { + lsort [perf::list::get_sort_sample] + } {} -overhead {perf::list::get_sort_sample} + + comment Sort an unshared-span list + perf measure [lsort_describe unshared-span [llength [perf::list::get_sort_sample 1]]] { + lsort [perf::list::get_sort_sample 1] + } {} -overhead {perf::list::get_sort_sample 1} + + perf destroy + } + + proc concat_describe {canonicality len elemlen} { + return "concat L\[$len\] $canonicality with elements of length $elemlen" + } + proc concat_perf {} { + variable Lengths + + print_separator concat + + ListPerf create perf -reps 100000 + + foreach len $Lengths { + foreach elemlen {1 100} { + comment Pure lists (no string representation) + perf measure [concat_describe "pure lists" $len $elemlen] { + concat $L $L + } [list len $len elemlen $elemlen] -setup { + set L [lrepeat $len [string repeat a $elemlen]] + } + + comment Canonical lists (with string representation) + perf measure [concat_describe "canonical lists" $len $elemlen] { + concat $L $L + } [list len $len elemlen $elemlen] -setup { + set L [lrepeat $len [string repeat a $elemlen]] + append x x $L; # Generate string while keeping internal rep list + unset x + } + + comment Non-canonical lists + perf measure [concat_describe "non-canonical lists" $len $elemlen] { + concat $L $L + } [list len $len elemlen $elemlen] -setup { + set L [string repeat "[string repeat a $elemlen] " $len] + llength $L + } + } + } + + # Span version + foreach len $Lengths { + foreach elemlen {1 100} { + comment Pure span lists (no string representation) + perf measure [concat_describe "pure spanned lists" $len $elemlen] { + concat $L $L + } [list len $len elemlen $elemlen] -setup { + set L [lrange [lrepeat [expr {$len+2}] [string repeat a $elemlen]] 1 end-1] + } + + comment Canonical span lists (with string representation) + perf measure [concat_describe "canonical spanned lists" $len $elemlen] { + concat $L $L + } [list len $len elemlen $elemlen] -setup { + set L [lrange [lrepeat [expr {$len+2}] [string repeat a $elemlen]] 1 end-1] + append x x $L; # Generate string while keeping internal rep list + unset x + } + } + } + + perf destroy + } + + proc test {} { + variable RunTimes + variable Options + + set selections [perf::list::setup $::argv] + if {[llength $selections] == 0} { + set commands [info commands ::perf::list::*_perf] + } else { + set commands [lmap sel $selections { + if {$sel eq "help"} { + print_usage + continue + } + set cmd ::perf::list::${sel}_perf + if {$cmd ni [info commands ::perf::list::*_perf]} { + puts stderr "Error: command $sel is not known or supported. Skipping." + continue + } + set cmd + }] + } + comment Setting up + timerate -calibrate {} + if {[info exists Options(--label)]} { + print "L $Options(--label)" + } + print "V [info patchlevel]" + print "E [info nameofexecutable]" + if {[info exists Options(--description)]} { + print "D $Options(--description)" + } + set twapi_keys {-privatebytes -workingset -workingsetpeak} + if {[info commands ::twapi::get_process_memory_info] ne ""} { + set twapi_vm_pre [::twapi::get_process_memory_info] + } + foreach cmd [lsort -dictionary $commands] { + set RunTimes(command) 0.0 + $cmd + set RunTimes(total) [expr {$RunTimes(total)+$RunTimes(command)}] + print "P [format_timings $RunTimes(command) 1] [string range $cmd 14 end-5] total run time" + } + # Print total runtime in same format as timerate output + print "P [format_timings $RunTimes(total) 1] Total run time" + + if {[info exists twapi_vm_pre]} { + set twapi_vm_post [::twapi::get_process_memory_info] + set MB 1048576.0 + foreach key $twapi_keys { + set pre [expr {[dict get $twapi_vm_pre $key]/$MB}] + set post [expr {[dict get $twapi_vm_post $key]/$MB}] + print "P [format_timings $pre 1] Memory (MB) $key pre-test" + print "P [format_timings $post 1] Memory (MB) $key post-test" + print "P [format_timings [expr {$post-$pre}] 1] Memory (MB) delta $key" + } + } + if {[info commands memory] ne ""} { + foreach line [split [memory info] \n] { + if {$line eq ""} continue + set line [split $line] + set val [expr {[lindex $line end]/1000.0}] + set line [string trim [join [lrange $line 0 end-1]]] + print "P [format_timings $val 1] memdbg $line (in thousands)" + } + print "# Allocations not freed on exit written to the lost-memory.tmp file." + print "# These will have to be manually compared." + # env TCL_FINALIZE_ON_EXIT must be set to 1 for this. + # DO NOT SET HERE - set ::env(TCL_FINALIZE_ON_EXIT) 1 + # Must be set in environment before starting tclsh else bogus results + if {[info exists Options(--label)]} { + set dump_file list-memory-$Options(--label).memdmp + } else { + set dump_file list-memory-[pid].memdmp + } + memory onexit $dump_file + } + } +} + + +if {[info exists ::argv0] && [file tail $::argv0] eq [file tail [info script]]} { + ::perf::list::test +} diff --git a/tests/lrepeat.test b/tests/lrepeat.test index c1c8b02..6734281 100644 --- a/tests/lrepeat.test +++ b/tests/lrepeat.test @@ -61,7 +61,7 @@ test lrepeat-1.7 {Accept zero repetitions (TIP 323)} { } -result {} } -test lrepeat-1.8 {Do not build enormous lists - Bug 2130992} -body { +test lrepeat-1.8 {Do not build enormous lists - Bug 2130992} -constraints knownBug -body { lrepeat 0x10000000 a b c d e f g h } -returnCodes error -match glob -result * |