From 9e77fc653dc92b552b78bc64523cfaf1a2166d04 Mon Sep 17 00:00:00 2001 From: apnadkarni Date: Tue, 26 Jul 2022 17:20:16 +0000 Subject: List rep tests for lappend,lset,lassign,lremove,lrange,lpop --- generic/tclListObj.c | 18 +- tests/listRep.test | 1377 ++++++++++++++++++++++++++++++++++++++++++++++---- 2 files changed, 1299 insertions(+), 96 deletions(-) diff --git a/generic/tclListObj.c b/generic/tclListObj.c index 529a790..6e195e3 100644 --- a/generic/tclListObj.c +++ b/generic/tclListObj.c @@ -385,6 +385,7 @@ static inline void ListRepFreeUnreferenced(const ListRep *repPtr) { if (! ListRepIsShared(repPtr) && repPtr->spanPtr) { + /* T:listrep-1.5.1 */ ListRepUnsharedFreeUnreferenced(repPtr); } } @@ -1058,6 +1059,7 @@ static void ListRepUnsharedFreeUnreferenced(const ListRep *repPtr) count = spanPtr->spanStart - storePtr->firstUsed; LIST_COUNT_ASSERT(count); if (count > 0) { + /* T:listrep-1.5.1 */ ObjArrayDecrRefs(storePtr->slots, storePtr->firstUsed, count); storePtr->firstUsed = spanPtr->spanStart; LIST_ASSERT(storePtr->numUsed >= count); @@ -1447,7 +1449,7 @@ ListRepRange( /* Take the opportunity to garbage collect */ /* TODO - we probably do not need the preserveSrcRep here unlike later */ if (!preserveSrcRep) { - /* T:listrep-1.{4,5,8,9},2.{4,5,6,7},3.{15,16,17,18},4.{7,8} */ + /* T:listrep-1.{4,5,8,9},2.{4:7},3.{15:18},4.{7,8} */ ListRepFreeUnreferenced(srcRepPtr); } @@ -1484,6 +1486,7 @@ ListRepRange( */ if (rangeStart == 0 && rangeEnd == (numSrcElems-1)) { /* Option 0 - entire list. This may be used to canonicalize */ + /* T:listrep-1.10.1 */ *rangeRepPtr = *srcRepPtr; /* Not ref counts not incremented */ } else if (rangeStart == 0 && (!preserveSrcRep) && (!ListRepIsShared(srcRepPtr) && srcRepPtr->spanPtr == NULL)) { @@ -1527,7 +1530,7 @@ ListRepRange( * is mandated. */ if (!preserveSrcRep) { - /* T:listrep-2.{5,7},3.{16,18},4.{7,8} */ + /* T:listrep-1.{5.1,5.2,5.4},2.{5,7},3.{16,18},4.{7,8} */ ListRepFreeUnreferenced(rangeRepPtr); } } else if (preserveSrcRep || ListRepIsShared(srcRepPtr)) { @@ -1633,8 +1636,9 @@ TclListObjRange( ListRepRange(&listRep, rangeStart, rangeEnd, isShared, &resultRep); if (isShared) { + /* T:listrep-1.10.1 */ TclNewObj(listObj); - } + } /* T:listrep-1.{4.3,5.1,5.2} */ ListObjReplaceRepAndInvalidate(listObj, &resultRep); return listObj; } @@ -2511,7 +2515,7 @@ Tcl_ListObjReplace( /* T:listrep-1.{7,12,15,17,19,20} */ listRep.spanPtr = NULL; } else { - /* T:listrep-1.{1,3,13,14,16,18,21} */ + /* T:listrep-1.{1,3,6.1,13,14,16,18,21} */ listRep.spanPtr = ListSpanNew(listRep.storePtr->firstUsed, listRep.storePtr->numUsed); } @@ -2736,6 +2740,7 @@ TclLsetList( && TclGetIntForIndexM(NULL, indexArgObj, ListSizeT_MAX - 1, &index) == TCL_OK) { /* indexArgPtr designates a single index. */ + /* T:listrep-1.{2.1,12.1,15.1,19.1} */ return TclLsetFlat(interp, listObj, 1, &indexArgObj, valueObj); } @@ -3018,10 +3023,13 @@ TclLsetFlat( len = -1; TclListObjLengthM(NULL, subListObj, &len); if (valueObj == NULL) { + /* T:listrep-1.{4.2,5.4,6.1,7.1,8.3} */ Tcl_ListObjReplace(NULL, subListObj, index, 1, 0, NULL); } else if (index == len) { + /* T:listrep-1.2.1 */ Tcl_ListObjAppendElement(NULL, subListObj, valueObj); } else { + /* T:listrep-1.{12.1,15.1,19.1} */ TclListObjSetElement(NULL, subListObj, index, valueObj); TclInvalidateStringRep(subListObj); } @@ -3097,7 +3105,7 @@ TclListObjSetElement( /* TODO - leave extra space? */ ListRepClone(&listRep, &newInternalRep, LISTREP_PANIC_ON_FAIL); listRep = newInternalRep; - } + } /* else T:listrep-1.{12.1,15.1,19.1} */ /* Retrieve element array AFTER potential cloning above */ ListRepElements(&listRep, elemCount, elemPtrs); diff --git a/tests/listRep.test b/tests/listRep.test index 9937f3c..9cfaeb2 100644 --- a/tests/listRep.test +++ b/tests/listRep.test @@ -194,110 +194,334 @@ set end end test listrep-1.1 { Inserts in front of unshared list with no free space should reallocate with - equal free space at front and back + equal free space at front and back -- linsert version } -constraints testlistrep -body { set l [linsert [freeSpaceNone] $zero 99] validate $l list $l [spaceEqual $l] } -result [list {99 0 1 2 3 4 5 6 7} 1] +test listrep-1.1.1 { + Inserts in front of unshared list with no free space should reallocate with + equal free space at front and back -- lreplace version +} -constraints testlistrep -body { + set l [lreplace [freeSpaceNone] $zero -1 99] + validate $l + list $l [spaceEqual $l] +} -result [list {99 0 1 2 3 4 5 6 7} 1] + test listrep-1.2 { Inserts at back of unshared list with no free space should allocate all - space at back (essentially old lappend behavior) + space at back -- linsert version } -constraints testlistrep -body { set l [linsert [freeSpaceNone] $end 99] validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {0 1 2 3 4 5 6 7 99} 0 9] +test listrep-1.2.1 { + Inserts at back of unshared list with no free space should allocate all + space at back -- lset version +} -constraints testlistrep -body { + set l [freeSpaceNone] + lset l $end+1 99 + validate $l + list $l [leadSpace $l] [tailSpace $l] +} -result [list {0 1 2 3 4 5 6 7 99} 0 9] + +test listrep-1.2.2 { + Inserts at back of unshared list with no free space should allocate all + space at back -- lappend version +} -constraints testlistrep -body { + set l [freeSpaceNone] + lappend l 99 + validate $l + list $l [leadSpace $l] [tailSpace $l] +} -result [list {0 1 2 3 4 5 6 7 99} 0 9] + test listrep-1.3 { Inserts in middle of unshared list with no free space should reallocate with - equal free space at front and back + equal free space at front and back - linsert version } -constraints testlistrep -body { set l [linsert [freeSpaceNone] $four 99] validate $l list $l [spaceEqual $l] } -result [list {0 1 2 3 99 4 5 6 7} 1] +test listrep-1.3.1 { + Inserts in middle of unshared list with no free space should reallocate with + equal free space at front and back - lreplace version +} -constraints testlistrep -body { + set l [lreplace [freeSpaceNone] $four $four-1 99] + validate $l + list $l [spaceEqual $l] +} -result [list {0 1 2 3 99 4 5 6 7} 1] + test listrep-1.4 { Deletes from front of small unshared list with no free space should - just shift up leaving room at back + just shift up leaving room at back - lreplace version } -constraints testlistrep -body { set l [lreplace [freeSpaceNone] $zero $zero] validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {1 2 3 4 5 6 7} 0 1] +test listrep-1.4.1 { + Deletes from front of small unshared list with no free space should + just shift up leaving room at back - lassign version +} -constraints testlistrep -body { + set l [lassign [freeSpaceNone] e] + validate $l + list $e $l [leadSpace $l] [tailSpace $l] +} -result [list 0 {1 2 3 4 5 6 7} 0 1] + +test listrep-1.4.2 { + Deletes from front of small unshared list with no free space should + just shift up leaving room at back - lpop version +} -constraints testlistrep -body { + set l [freeSpaceNone] + set e [lpop l $zero] + validate $l + list $e $l [leadSpace $l] [tailSpace $l] +} -result [list 0 {1 2 3 4 5 6 7} 0 1] + +test listrep-1.4.3 { + Deletes from front of small unshared list with no free space should + just shift up leaving room at back - lrange version +} -constraints testlistrep -body { + set l [lrange [freeSpaceNone] $one $end] + validate $l + list $l [leadSpace $l] [tailSpace $l] +} -result [list {1 2 3 4 5 6 7} 0 1] + +test listrep-1.4.4 { + Deletes from front of small unshared list with no free space should + just shift up leaving room at back - lremove version +} -constraints testlistrep -body { + set l [lremove [freeSpaceNone] $zero] + validate $l + list $l [leadSpace $l] [tailSpace $l] +} -result [list {1 2 3 4 5 6 7} 0 1] + test listrep-1.5 { Deletes from front of large unshared list with no free space should - create a span + create a span - lreplace version } -constraints testlistrep -body { set l [lreplace [freeSpaceNone 1000] $zero $one] validate $l list $l [leadSpace $l] [tailSpace $l] [hasSpan $l 2 998] } -result [list [irange 2 999] 2 0 1] +test listrep-1.5.1 { + Deletes from front of large unshared list with no free space should + create a span - lassign version +} -constraints testlistrep -body { + set l [lassign [freeSpaceNone 1000] e] + validate $l + list $e $l [leadSpace $l] [tailSpace $l] [hasSpan $l 1 999] +} -result [list 0 [irange 1 999] 1 0 1] + +test listrep-1.5.2 { + Deletes from front of large unshared list with no free space should + create a span - lrange version +} -constraints testlistrep -body { + set l [lrange [freeSpaceNone 1000] $two end] + validate $l + list $l [leadSpace $l] [tailSpace $l] [hasSpan $l 2 998] +} -result [list [irange 2 999] 2 0 1] + +test listrep-1.5.3 { + Deletes from front of large unshared list with no free space should + create a span - lremove version +} -constraints testlistrep -body { + set l [lremove [freeSpaceNone 1000] $zero] + validate $l + list $l [leadSpace $l] [tailSpace $l] [hasSpan $l 1 999] +} -result [list [irange 1 999] 1 0 1] + +test listrep-1.5.4 { + Deletes from front of large unshared list with no free space should + create a span - lpop version +} -constraints testlistrep -body { + set l [freeSpaceNone 1000] + set e [lpop l 0] + validate $l + list $e $l [leadSpace $l] [tailSpace $l] [hasSpan $l 1 999] +} -result [list 0 [irange 1 999] 1 0 1] + test listrep-1.6 { Deletes closer to front of large list should move (smaller) front segment + -- lreplace version } -constraints testlistrep -body { set l [lreplace [freeSpaceNone 1000] $four $four] validate $l list $l [leadSpace $l] [tailSpace $l] [hasSpan $l 1 999] } -result [list [concat [irange 0 3] [irange 5 999]] 1 0 1] +test listrep-1.6.1 { + Deletes closer to front of large list should move (smaller) front segment + -- lpop version +} -constraints testlistrep -body { + set l [freeSpaceNone 1000] + set e [lpop l $four] + validate $l + list $e $l [leadSpace $l] [tailSpace $l] [hasSpan $l 1 999] +} -result [list 4 [concat [irange 0 3] [irange 5 999]] 1 0 1] + test listrep-1.7 { Deletes closer to back of large list should move (smaller) back segment - and will not need a span + and will not need a span - lreplace version } -constraints testlistrep -body { set l [lreplace [freeSpaceNone 1000] end-$four end-$four] validate $l list $l [leadSpace $l] [tailSpace $l] [hasSpan $l] } -result [list [concat [irange 0 994] [irange 996 999]] 0 1 0] +test listrep-1.7.1 { + Deletes closer to back of large list should move (smaller) back segment + and will not need a span - lpop version +} -constraints testlistrep -body { + set l [freeSpaceNone 1000] + set e [lpop l $end-4] + validate $l + list $e $l [leadSpace $l] [tailSpace $l] [hasSpan $l] +} -result [list 995 [concat [irange 0 994] [irange 996 999]] 0 1 0] + test listrep-1.8 { - Deletes at back of small unshared list should not need a span + Deletes at back of small unshared list should not need a span - lreplace version } -constraints testlistrep -body { set l [lreplace [freeSpaceNone] end-$one end] validate $l list $l [leadSpace $l] [tailSpace $l] [hasSpan $l] } -result [list {0 1 2 3 4 5} 0 2 0] +test listrep-1.8.1 { + Deletes at back of small unshared list should not need a span - lrange version +} -constraints testlistrep -body { + set l [lrange [freeSpaceNone] $zero end-$two] + validate $l + list $l [leadSpace $l] [tailSpace $l] [hasSpan $l] +} -result [list {0 1 2 3 4 5} 0 2 0] + +test listrep-1.8.2 { + Deletes at back of small unshared list should not need a span - lremove version +} -constraints testlistrep -body { + set l [lremove [freeSpaceNone] $end-1 $end] + validate $l + list $l [leadSpace $l] [tailSpace $l] [hasSpan $l] +} -result [list {0 1 2 3 4 5} 0 2 0] + +test listrep-1.8.3 { + Deletes at back of small unshared list should not need a span - lpop version +} -constraints testlistrep -body { + set l [freeSpaceNone] + set e [lpop l $end] + validate $l + list $e $l [leadSpace $l] [tailSpace $l] [hasSpan $l] +} -result [list 7 {0 1 2 3 4 5 6} 0 1 0] + test listrep-1.9 { - Deletes at back of large unshared list should not need a span + Deletes at back of large unshared list should not need a span - lreplace version } -constraints testlistrep -body { set l [lreplace [freeSpaceNone 1000] end-$four end] validate $l list $l [leadSpace $l] [tailSpace $l] [hasSpan $l] } -result [list [irange 0 994] 0 5 0] +test listrep-1.9.1 { + Deletes at back of large unshared list should not need a span - lrange version +} -constraints testlistrep -body { + set l [lrange [freeSpaceNone 1000] 0 $end-5] + validate $l + list $l [leadSpace $l] [tailSpace $l] [hasSpan $l] +} -result [list [irange 0 994] 0 5 0] + +test listrep-1.9.2 { + Deletes at back of large unshared list should not need a span - lremove version +} -constraints testlistrep -body { + set l [lremove [freeSpaceNone 1000] end-$four $end-3 end-$two $end-1 $end] + validate $l + list $l [leadSpace $l] [tailSpace $l] [hasSpan $l] +} -result [list [irange 0 994] 0 5 0] + +test listrep-1.9.3 { + Deletes at back of large unshared list should not need a span - lpop version +} -constraints testlistrep -body { + set l [freeSpaceNone 1000] + set e [lpop l $end] + validate $l + list $e $l [leadSpace $l] [tailSpace $l] [hasSpan $l] +} -result [list 999 [irange 0 998] 0 1 0] + test listrep-1.10 { - lreplace no-op on unshared list should force a canonical list representation + no-op on unshared list should force a canonical list string - lreplace version } -body { lreplace { 1 2 3 4 } $zero -1 } -result {1 2 3 4} +test listrep-1.10.1 { + no-op on unshared list should force a canonical list string - lrange version +} -body { + lrange { 1 2 3 4 } $zero $end +} -result {1 2 3 4} + test listrep-1.11 { - Append elements to large unshared list using lreplace is optimized as lappend - so no free space in front + Append elements to large unshared list is optimized as lappend + so no free space in front - lreplace version } -body { # Note $end, not end else byte code compiler short-cuts set l [lreplace [freeSpaceNone 1000] $end+1 $end+1 1000] + validate $l + list $l [leadSpace $l] [expr {[tailSpace $l] > 0}] [hasSpan $l] +} -result [list [irange 0 1000] 0 1 0] + +test listrep-1.11.1 { + Append elements to large unshared list is optimized as lappend + so no free space in front - linsert version +} -body { + # Note $end, not end else byte code compiler short-cuts + set l [linsert [freeSpaceNone 1000] $end+1 1000] + validate $l list $l [leadSpace $l] [expr {[tailSpace $l] > 0}] [hasSpan $l] } -result [list [irange 0 1000] 0 1 0] +test listrep-1.11.2 { + Append elements to large unshared list leaves no free space in front + - lappend version +} -body { + # Note $end, not end else byte code compiler short-cuts + set l [freeSpaceNone 1000] + lappend l 1000 1001 + validate $l + list $l [leadSpace $l] [expr {[tailSpace $l] > 0}] [hasSpan $l] +} -result [list [irange 0 1001] 0 1 0] + + test listrep-1.12 { Replacement of elements at front with same number elements in unshared list - is in-place + is in-place - lreplace version } -body { set l [lreplace [freeSpaceNone] $zero $one 10 11] + validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {10 11 2 3 4 5 6 7} 0 0] +test listrep-1.12.1 { + Replacement of elements at front with same number elements in unshared list + is in-place - lset version +} -body { + set l [freeSpaceNone] + lset l 0 -1 + validate $l + list $l [leadSpace $l] [tailSpace $l] +} -result [list {-1 1 2 3 4 5 6 7} 0 0] + test listrep-1.13 { Replacement of elements at front with fewer elements in unshared list results in a spanned list with space only in front } -body { set l [lreplace [freeSpaceNone] $zero $four 10] + validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {10 5 6 7} 4 0] @@ -306,22 +530,35 @@ test listrep-1.14 { results in a reallocated spanned list with space at front and back } -body { set l [lreplace [freeSpaceNone] $zero $one 10 11 12] + validate $l list $l [spaceEqual $l] } -result [list {10 11 12 2 3 4 5 6 7} 1] test listrep-1.15 { Replacement of elements in middle with same number elements in unshared list - is in-place + is in-place - lreplace version } -body { set l [lreplace [freeSpaceNone] $one $two 10 11] + validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {0 10 11 3 4 5 6 7} 0 0] +test listrep-1.15.1 { + Replacement of elements in middle with same number elements in unshared list + is in-place - lset version +} -body { + set l [freeSpaceNone] + lset l $two -1 + validate $l + list $l [leadSpace $l] [tailSpace $l] +} -result [list {0 1 -1 3 4 5 6 7} 0 0] + test listrep-1.16 { Replacement of elements in front half with fewer elements in unshared list results in a spanned list with space only in front since smaller segment moved } -body { set l [lreplace [freeSpaceNone] $one $four 10] + validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {0 10 5 6 7} 3 0] @@ -330,6 +567,7 @@ test listrep-1.17 { results in a spanned list with space only at back } -body { set l [lreplace [freeSpaceNone] end-$four end-$one 10] + validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {0 1 2 10 7} 0 3] @@ -338,22 +576,35 @@ test listrep-1.18 { results in a reallocated spanned list with space at front and back } -body { set l [lreplace [freeSpaceNone] $one $two 10 11 12] + validate $l list $l [spaceEqual $l] } -result [list {0 10 11 12 3 4 5 6 7} 1] test listrep-1.19 { Replacement of elements at back with same number elements in unshared list - is in-place + is in-place - lreplace version } -body { set l [lreplace [freeSpaceNone] $end-1 $end 10 11] + validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {0 1 2 3 4 5 10 11} 0 0] +test listrep-1.19.1 { + Replacement of elements at back with same number elements in unshared list + is in-place - lset version +} -body { + set l [freeSpaceNone] + lset l $end 10 + validate $l + list $l [leadSpace $l] [tailSpace $l] +} -result [list {0 1 2 3 4 5 6 10} 0 0] + test listrep-1.20 { Replacement of elements at back with fewer elements in unshared list is in-place with space only at the back } -body { set l [lreplace [freeSpaceNone] $end-2 $end 10] + validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {0 1 2 3 4 10} 0 2] @@ -362,6 +613,7 @@ test listrep-1.21 { allocates new representation with equal space at front and back } -body { set l [lreplace [freeSpaceNone] $end-1 $end 10 11 12] + validate $l list $l [spaceEqual $l] } -result [list {0 1 2 3 4 5 10 11 12} 1] @@ -373,119 +625,387 @@ test listrep-1.21 { test listrep-2.1 { Inserts in front of shared list with no free space should reallocate with - more leading space in front + more leading space in front - linsert version } -constraints testlistrep -body { set a [freeSpaceNone] - set b [lrange $a 0 end]; # Ensure shared listrep + set b [lrange $a $zero end]; # Ensure shared listrep set l [linsert $b $zero 99] validate $l list [repStoreRefCount $b] $l [leadSpaceMore $l] [repStoreRefCount $l] } -result [list 2 {99 0 1 2 3 4 5 6 7} 1 1] +test listrep-2.1.1 { + Inserts in front of shared list with no free space should reallocate with + more leading space in front - lreplace version +} -constraints testlistrep -body { + set a [freeSpaceNone] + set b [lrange $a $zero end]; # Ensure shared listrep + set l [lreplace $b $zero -1 99] + validate $l + list [repStoreRefCount $b] $l [leadSpaceMore $l] [repStoreRefCount $l] +} -result [list 2 {99 0 1 2 3 4 5 6 7} 1 1] + test listrep-2.2 { Inserts at back of shared list with no free space should reallocate with - more leading space in back + more leading space in back - linsert version } -constraints testlistrep -body { set a [freeSpaceNone] - set b [lrange $a 0 end]; # Ensure shared listrep + set b [lrange $a $zero end]; # Ensure shared listrep set l [linsert $b $end 99] validate $l list [repStoreRefCount $b] $l [tailSpaceMore $l] [repStoreRefCount $l] } -result [list 2 {0 1 2 3 4 5 6 7 99} 1 1] +test listrep-2.2.1 { + Inserts at back of shared list with no free space should reallocate with + more leading space in back - lreplace version +} -constraints testlistrep -body { + set a [freeSpaceNone] + set b [lrange $a $zero end]; # Ensure shared listrep + set l [lreplace $b $end+1 end+$one 99] + validate $l + list [repStoreRefCount $b] $l [tailSpaceMore $l] [repStoreRefCount $l] +} -result [list 2 {0 1 2 3 4 5 6 7 99} 1 1] + +test listrep-2.2.2 { + Inserts at back of shared list with no free space should reallocate with + more leading space in back - lappend version +} -constraints testlistrep -body { + set a [freeSpaceNone] + set b [lrange $a $zero end]; # Ensure shared listrep + set l [lappend b 99] + validate $l + list [repStoreRefCount $b] $l [tailSpaceMore $l] [repStoreRefCount $l] +} -result [list 1 {0 1 2 3 4 5 6 7 99} 1 1] + +test listrep-2.2.3 { + Inserts at back of shared list with no free space should reallocate with + more leading space in back - lset version +} -constraints testlistrep -body { + set a [freeSpaceNone] + set b [lrange $a $zero end]; # Ensure shared listrep + set l [lset b $end+1 99] + validate $l + list [repStoreRefCount $b] $l [tailSpaceMore $l] [repStoreRefCount $l] +} -result [list 1 {0 1 2 3 4 5 6 7 99} 1 1] + test listrep-2.3 { Inserts in middle of shared list with no free space should reallocate with - equal spacing + equal spacing - linsert version } -constraints testlistrep -body { set a [freeSpaceNone] - set b [lrange $a 0 end]; # Ensure shared listrep + set b [lrange $a $zero end]; # Ensure shared listrep set l [linsert $b $four 99] validate $l list [repStoreRefCount $b] $l [spaceEqual $l] [repStoreRefCount $l] } -result [list 2 {0 1 2 3 99 4 5 6 7} 1 1] +test listrep-2.3.1 { + Inserts in middle of shared list with no free space should reallocate with + equal spacing - lreplace version +} -constraints testlistrep -body { + set a [freeSpaceNone] + set b [lrange $a $zero end]; # Ensure shared listrep + set l [lreplace $b $four $four-1 99] + validate $l + list [repStoreRefCount $b] $l [spaceEqual $l] [repStoreRefCount $l] +} -result [list 2 {0 1 2 3 99 4 5 6 7} 1 1] + test listrep-2.4 { Deletes from front of small shared list with no free space should - allocate new list of exact size + allocate new list of exact size - lreplace version } -constraints testlistrep -body { set a [freeSpaceNone] - set b [lrange $a 0 end]; # Ensure shared listrep + set b [lrange $a $zero end]; # Ensure shared listrep set l [lreplace $b $zero $zero] validate $l list [repStoreRefCount $b] $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] } -result [list 2 {1 2 3 4 5 6 7} 0 0 1] +test listrep-2.4.1 { + Deletes from front of small shared list with no free space should + allocate new list of exact size - lremove version +} -constraints testlistrep -body { + set a [freeSpaceNone] + set b [lrange $a $zero end]; # Ensure shared listrep + set l [lremove $b $zero $one] + validate $l + list [repStoreRefCount $b] $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list 2 {2 3 4 5 6 7} 0 0 1] + +test listrep-2.4.2 { + Deletes from front of small shared list with no free space should + allocate new list of exact size - lrange version +} -constraints testlistrep -body { + set a [freeSpaceNone] + set b [lrange $a $zero end]; # Ensure shared listrep + set l [lrange $b $one $end] + validate $l + list [repStoreRefCount $b] $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list 2 {1 2 3 4 5 6 7} 0 0 1] + +test listrep-2.4.3 { + Deletes from front of small shared list with no free space should + allocate new list of exact size - lassign version +} -constraints testlistrep -body { + set a [freeSpaceNone] + set b [lrange $a $zero end]; # Ensure shared listrep + set l [lassign $b e] + validate $l + list $e [repStoreRefCount $b] $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list 0 2 {1 2 3 4 5 6 7} 0 0 1] + +test listrep-2.4.4 { + Deletes from front of small shared list with no free space should + allocate new list of exact size - lpop version +} -constraints testlistrep -body { + set a [freeSpaceNone] + set l [lrange $a $zero end]; # Ensure shared listrep + set e [lpop l $zero] + validate $l + list $e $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list 0 {1 2 3 4 5 6 7} 0 0 1] + test listrep-2.5 { Deletes from front of large shared list with no free space should - create span + create span - lreplace version } -constraints testlistrep -body { set a [freeSpaceNone 1000] - set b [lrange $a 0 end]; # Ensure shared listrep + set b [lrange $a $zero end]; # Ensure shared listrep set l [lreplace $b $zero $zero] validate $l # The listrep store should be shared among a, b, l (3 refs) - list [repStoreRefCount $b] $l [hasSpan $l] [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] -} -result [list 3 [irange 1 999] 1 0 0 3] + list [sameStore $b $l] [repStoreRefCount $b] $l [hasSpan $l] [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list 1 3 [irange 1 999] 1 0 0 3] + +test listrep-2.5.1 { + Deletes from front of large shared list with no free space should + create span - lremove version +} -constraints testlistrep -body { + set a [freeSpaceNone 1000] + set b [lrange $a $zero end]; # Ensure shared listrep + set l [lremove $b $zero $one] + validate $l + # The listrep store should be shared among a, b, l (3 refs) + list [sameStore $b $l] [repStoreRefCount $b] $l [hasSpan $l] [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list 1 3 [irange 2 999] 1 0 0 3] + +test listrep-2.5.2 { + Deletes from front of large shared list with no free space should + create span - lrange version +} -constraints testlistrep -body { + set a [freeSpaceNone 1000] + set b [lrange $a $zero end]; # Ensure shared listrep + set l [lrange $b $two $end] + validate $l + # The listrep store should be shared among a, b, l (3 refs) + list [sameStore $b $l] [repStoreRefCount $b] $l [hasSpan $l] [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list 1 3 [irange 2 999] 1 0 0 3] + +test listrep-2.5.3 { + Deletes from front of large shared list with no free space should + create span - lassign version +} -constraints testlistrep -body { + set a [freeSpaceNone 1000] + set b [lrange $a $zero end]; # Ensure shared listrep + set l [lassign $b e] + validate $l + # The listrep store should be shared among a, b, l (3 refs) + list $e [sameStore $b $l] [repStoreRefCount $b] $l [hasSpan $l] [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list 0 1 3 [irange 1 999] 1 0 0 3] + +test listrep-2.5.4 { + Deletes from front of large shared list with no free space should + create span - lpop version +} -constraints testlistrep -body { + set a [freeSpaceNone 1000] + set l [lrange $a $zero end]; # Ensure shared listrep + set e [lpop l $zero] + validate $l + # The listrep store should be shared among a, b, l (3 refs) + list $e $l [hasSpan $l] [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list 0 [irange 1 999] 1 0 0 2] test listrep-2.6 { Deletes from back of small shared list with no free space should - allocate new list of exact size + allocate new list of exact size - lreplace version } -constraints testlistrep -body { set a [freeSpaceNone] - set b [lrange $a 0 end]; # Ensure shared listrep + set b [lrange $a $zero end]; # Ensure shared listrep set l [lreplace $b $end $end] validate $l list [repStoreRefCount $b] $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] } -result [list 2 {0 1 2 3 4 5 6} 0 0 1] +test listrep-2.6.1 { + Deletes from back of small shared list with no free space should + allocate new list of exact size - lremove version +} -constraints testlistrep -body { + set a [freeSpaceNone] + set b [lrange $a $zero end]; # Ensure shared listrep + set l [lremove $b $end $end-1] + validate $l + list [repStoreRefCount $b] $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list 2 {0 1 2 3 4 5} 0 0 1] + +test listrep-2.6.2 { + Deletes from back of small shared list with no free space should + allocate new list of exact size - lrange version +} -constraints testlistrep -body { + set a [freeSpaceNone] + set b [lrange $a $zero end]; # Ensure shared listrep + set l [lrange $b $zero $end-1] + validate $l + list [repStoreRefCount $b] $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list 2 {0 1 2 3 4 5 6} 0 0 1] + +test listrep-2.6.3 { + Deletes from back of small shared list with no free space should + allocate new list of exact size - lpop version +} -constraints testlistrep -body { + set a [freeSpaceNone] + set l [lrange $a $zero end]; # Ensure shared listrep + set e [lpop l] + validate $l + list $e $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list 7 {0 1 2 3 4 5 6} 0 0 1] + test listrep-2.7 { Deletes from back of large shared list with no free space should - use a span + use a span - lreplace version } -constraints testlistrep -body { set a [freeSpaceNone 1000] - set b [lrange $a 0 end]; # Ensure shared listrep + set b [lrange $a $zero end]; # Ensure shared listrep set l [lreplace $b $end $end] validate $l # Note lead and tail space is 0 because original list store in a,b is used list [repStoreRefCount $b] $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] } -result [list 3 [irange 0 998] 0 0 3] +test listrep-2.7.1 { + Deletes from back of large shared list with no free space should + use a span - lremove version +} -constraints testlistrep -body { + set a [freeSpaceNone 1000] + set b [lrange $a $zero end]; # Ensure shared listrep + set l [lremove $b $end-1 $end] + validate $l + # Note lead and tail space is 0 because original list store in a,b is used + list [repStoreRefCount $b] $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list 3 [irange 0 997] 0 0 3] + +test listrep-2.7.2 { + Deletes from back of large shared list with no free space should + use a span - lrange version +} -constraints testlistrep -body { + set a [freeSpaceNone 1000] + set b [lrange $a $zero end]; # Ensure shared listrep + set l [lrange $b $zero $end-1] + validate $l + # Note lead and tail space is 0 because original list store in a,b is used + list [repStoreRefCount $b] $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list 3 [irange 0 998] 0 0 3] + +test listrep-2.7.3 { + Deletes from back of large shared list with no free space should + use a span - lpop version +} -constraints testlistrep -body { + set a [freeSpaceNone 1000] + set l [lrange $a $zero end]; # Ensure shared listrep + set e [lpop l] + validate $l + # Note lead and tail space is 0 because original list store in a,b is used + list $e $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list 999 [irange 0 998] 0 0 2] + test listrep-2.8 { - lreplace no-op on shared list should force a canonical list representation - with original unchanged + no-op on shared list should force a canonical list representation + with original unchanged - lreplace version } -body { set l { 1 2 3 4 } list [lreplace $l $zero -1] $l } -result [list {1 2 3 4} { 1 2 3 4 }] +test listrep-2.8.1 { + no-op on shared list should force a canonical list representation + with original unchanged - lrange version +} -body { + set l { 1 2 3 4 } + list [lrange $l $zero end] $l +} -result [list {1 2 3 4} { 1 2 3 4 }] + test listrep-2.9 { Appends to back of large shared list with no free space allocates new - list with space only at the back. + list with space only at the back - lreplace version } -constraints testlistrep -body { set a [freeSpaceNone 1000] - set b [lrange $a 0 end]; # Ensure shared listrep + set b [lrange $a $zero end]; # Ensure shared listrep set l [lreplace $b $end+1 $end+1 1000] validate $l list [repStoreRefCount $b] $l [leadSpace $l] [expr {[tailSpace $l]>0}] [repStoreRefCount $l] } -result [list 2 [irange 0 1000] 0 1 1] +test listrep-2.9.1 { + Appends to back of large shared list with no free space allocates new + list with space only at the back - linsert version +} -constraints testlistrep -body { + set a [freeSpaceNone 1000] + set b [lrange $a $zero end]; # Ensure shared listrep + set l [linsert $b $end+1 1000 1001] + validate $l + list [repStoreRefCount $b] $l [leadSpace $l] [expr {[tailSpace $l]>0}] [repStoreRefCount $l] +} -result [list 2 [irange 0 1001] 0 1 1] + +test listrep-2.9.2 { + Appends to back of large shared list with no free space allocates new + list with space only at the back - lappend version +} -constraints testlistrep -body { + set a [freeSpaceNone 1000] + set l [lrange $a $zero end]; # Ensure shared listrep + lappend l 1000 + validate $l + list $l [leadSpace $l] [expr {[tailSpace $l]>0}] [repStoreRefCount $l] +} -result [list [irange 0 1000] 0 1 1] + +test listrep-2.9.3 { + Appends to back of large shared list with no free space allocates new + list with space only at the back - lset version +} -constraints testlistrep -body { + set a [freeSpaceNone 1000] + set l [lrange $a $zero end]; # Ensure shared listrep + lset l $end+1 1000 + validate $l + list $l [leadSpace $l] [expr {[tailSpace $l]>0}] [repStoreRefCount $l] +} -result [list [irange 0 1000] 0 1 1] + test listrep-2.10 { - Replacement of elements at front with same number elements in shared list - results in a new list store with more space in front than back + Replacement of elements at front with same number in shared list results + in a new list store with more space in front than back - lreplace version } -constraints testlistrep -body { set a [freeSpaceNone] - set b [lrange $a 0 end]; # Ensure shared listrep + set b [lrange $a $zero end]; # Ensure shared listrep set l [lreplace $b $zero $one 10 11] validate $l list [repStoreRefCount $b] $l [leadSpaceMore $l] [repStoreRefCount $l] } -result [list 2 {10 11 2 3 4 5 6 7} 1 1] +test listrep-2.10.1 { + Replacement of elements at front with same number in shared list results + in a new list store with no extra space - lset version +} -constraints testlistrep -body { + set a [freeSpaceNone] + set l [lrange $a $zero end]; # Ensure shared listrep + lset l $zero 10 + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list {10 1 2 3 4 5 6 7} 0 0 1] + test listrep-2.11 { Replacement of elements at front with fewer elements in shared list results in a new list store with more space in front than back } -constraints testlistrep -body { set a [freeSpaceNone] - set b [lrange $a 0 end]; # Ensure shared listrep + set b [lrange $a $zero end]; # Ensure shared listrep set l [lreplace $b $zero $four 10] validate $l list [repStoreRefCount $b] $l [leadSpaceMore $l] [repStoreRefCount $l] @@ -496,29 +1016,40 @@ test listrep-2.12 { results in a new spanned list with more space in front } -constraints testlistrep -body { set a [freeSpaceNone] - set b [lrange $a 0 end]; # Ensure shared listrep + set b [lrange $a $zero end]; # Ensure shared listrep set l [lreplace $b $zero $one 10 11 12] validate $l list [repStoreRefCount $b] $l [leadSpaceMore $l] [repStoreRefCount $l] } -result [list 2 {10 11 12 2 3 4 5 6 7} 1 1] test listrep-2.13 { - Replacement of elements in middle with same number elements in shared list - results in a new list store with equal space in front and back + Replacement of elements in middle with same number in shared list results + in a new list store with equal space in front and back - lreplace version } -constraints testlistrep -body { set a [freeSpaceNone] - set b [lrange $a 0 end]; # Ensure shared listrep + set b [lrange $a $zero end]; # Ensure shared listrep set l [lreplace $b $one $two 10 11] validate $l list [repStoreRefCount $b] $l [spaceEqual $l] [repStoreRefCount $l] } -result [list 2 {0 10 11 3 4 5 6 7} 1 1] +test listrep-2.13.1 { + Replacement of elements in middle with same number in shared list results + in a new list store with exact allocation - lset version +} -constraints testlistrep -body { + set a [freeSpaceNone] + set l [lrange $a $zero end]; # Ensure shared listrep + lset l $one 10 + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list {0 10 2 3 4 5 6 7} 0 0 1] + test listrep-2.14 { Replacement of elements in middle with fewer elements in shared list results in a new list store with equal space } -constraints testlistrep -body { set a [freeSpaceNone] - set b [lrange $a 0 end]; # Ensure shared listrep + set b [lrange $a $zero end]; # Ensure shared listrep set l [lreplace $b $one 5 10] validate $l list [repStoreRefCount $b] $l [spaceEqual $l] [repStoreRefCount $l] @@ -529,29 +1060,40 @@ test listrep-2.15 { results in a new spanned list with space in front and back } -constraints testlistrep -body { set a [freeSpaceNone] - set b [lrange $a 0 end]; # Ensure shared listrep + set b [lrange $a $zero end]; # Ensure shared listrep set l [lreplace $b $one $two 10 11 12] validate $l list [repStoreRefCount $b] $l [spaceEqual $l] [repStoreRefCount $l] } -result [list 2 {0 10 11 12 3 4 5 6 7} 1 1] test listrep-2.16 { - Replacement of elements at back with same number elements in shared list - results in a new list store with more space in back than front + Replacement of elements at back with same number in shared list results + in a new list store with more space in back than front - lreplace version } -constraints testlistrep -body { set a [freeSpaceNone] - set b [lrange $a 0 end]; # Ensure shared listrep + set b [lrange $a $zero end]; # Ensure shared listrep set l [lreplace $b end-$one $end 10 11] validate $l list [repStoreRefCount $b] $l [tailSpaceMore $l] [repStoreRefCount $l] } -result [list 2 {0 1 2 3 4 5 10 11} 1 1] +test listrep-2.16.1 { + Replacement of elements at back with same number in shared list results + in a new list store with no extra - lreplace version +} -constraints testlistrep -body { + set a [freeSpaceNone] + set l [lrange $a $zero end]; # Ensure shared listrep + lset l $end 10 + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list {0 1 2 3 4 5 6 10} 0 0 1] + test listrep-2.17 { Replacement of elements at back with fewer elements in shared list results in a new list store with more space in back than front } -constraints testlistrep -body { set a [freeSpaceNone] - set b [lrange $a 0 end]; # Ensure shared listrep + set b [lrange $a $zero end]; # Ensure shared listrep set l [lreplace $b end-$four $end 10] validate $l list [repStoreRefCount $b] $l [tailSpaceMore $l] [repStoreRefCount $l] @@ -562,7 +1104,7 @@ test listrep-2.18 { results in a new list store with more space in back than front } -constraints testlistrep -body { set a [freeSpaceNone] - set b [lrange $a 0 end]; # Ensure shared listrep + set b [lrange $a $zero end]; # Ensure shared listrep set l [lreplace $b end-$four $end 10] validate $l list [repStoreRefCount $b] $l [tailSpaceMore $l] [repStoreRefCount $l] @@ -573,59 +1115,176 @@ test listrep-2.18 { test listrep-3.1 { Inserts in front of unshared spanned list with room in front should just - shrink the lead space + shrink the lead space - linsert version } -constraints testlistrep -body { set l [linsert [freeSpaceBoth] $zero -2 -1] validate $l list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] } -result [list [irange -2 7] 1 3 1] +test listrep-3.1.1 { + Inserts in front of unshared spanned list with room in front should just + shrink the lead space - lreplace version +} -constraints testlistrep -body { + set l [lreplace [freeSpaceBoth] $zero -1 -2 -1] + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list [irange -2 7] 1 3 1] + test listrep-3.2 { Inserts in front of unshared spanned list with insufficient room in front - but enough total freespace should redistribute free space + but enough total freespace should redistribute free space - linsert version } -constraints testlistrep -body { set l [linsert [freeSpaceBoth 8 1 10] $zero -2 -1] validate $l list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] } -result [list [irange -2 7] 5 4 1] +test listrep-3.2.1 { + Inserts in front of unshared spanned list with insufficient room in front + but enough total freespace should redistribute free space - lreplace version +} -constraints testlistrep -body { + set l [lreplace [freeSpaceBoth 8 1 10] $zero -1 -2 -1] + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list [irange -2 7] 5 4 1] + test listrep-3.3 { Inserts in front of unshared spanned list with insufficient total freespace - should reallocate with equal free space + should reallocate with equal free space - linsert version } -constraints testlistrep -body { set l [linsert [freeSpaceBoth 8 1 1] $zero -3 -2 -1] validate $l list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] } -result [list [irange -3 7] 6 5 1] +test listrep-3.3.1 { + Inserts in front of unshared spanned list with insufficient total freespace + should reallocate with equal free space - lreplace version +} -constraints testlistrep -body { + set l [lreplace [freeSpaceBoth 8 1 1] $zero -1 -3 -2 -1] + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list [irange -3 7] 6 5 1] + test listrep-3.4 { Inserts at back of unshared spanned list with room at back should not - reallocate + reallocate - linsert version } -constraints testlistrep -body { set l [linsert [freeSpaceBoth] $end 8] validate $l list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] } -result [list [irange 0 8] 3 2 1] +test listrep-3.4.1 { + Inserts at back of unshared spanned list with room at back should not + reallocate - lreplace version +} -constraints testlistrep -body { + set l [lreplace [freeSpaceBoth] $end+1 $end+1 8 9] + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list [irange 0 9] 3 1 1] + +test listrep-3.4.2 { + Inserts at back of unshared spanned list with room at back should not + reallocate - lappend version +} -constraints testlistrep -body { + set l [freeSpaceBoth] + lappend l 8 9 10 + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list [irange 0 10] 3 0 1] + +test listrep-3.4.3 { + Inserts at back of unshared spanned list with room at back should not + reallocate - lset version +} -constraints testlistrep -body { + set l [freeSpaceBoth] + lset l $end+1 8 + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list [irange 0 8] 3 2 1] + test listrep-3.5 { Inserts at back of unshared spanned list with insufficient room in back - but enough total freespace should redistribute free space + but enough total freespace should redistribute free space - linsert version } -constraints testlistrep -body { set l [linsert [freeSpaceBoth 8 10 1] $end 8 9] validate $l list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] } -result [list [irange 0 9] 5 4 1] +test listrep-3.5.1 { + Inserts at back of unshared spanned list with insufficient room in back + but enough total freespace should redistribute free space - lreplace version +} -constraints testlistrep -body { + set l [lreplace [freeSpaceBoth 8 10 1] $end+1 $end+1 8 9] + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list [irange 0 9] 5 4 1] + +test listrep-3.5.2 { + Inserts at back of unshared spanned list with insufficient room in back + but enough total freespace should redistribute free space - lappend version +} -constraints testlistrep -body { + set l [freeSpaceBoth 8 10 1] + lappend l 8 9 + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list [irange 0 9] 5 4 1] + +test listrep-3.5.3 { + Inserts at back of unshared spanned list with insufficient room in back + but enough total freespace should redistribute free space - lset version +} -constraints testlistrep -body { + set l [freeSpaceBoth 8 10 0] + lset l $end+1 8 + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list [irange 0 8] 5 4 1] + test listrep-3.6 { Inserts in back of unshared spanned list with insufficient total freespace should reallocate with all *additional* space at back. Note this differs - from the insert in front case because here we can realloc() + from the insert in front case because here we realloc(). - linsert version } -constraints testlistrep -body { set l [linsert [freeSpaceBoth 8 1 1] $end 8 9 10] validate $l list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] } -result [list [irange 0 10] 1 10 1] +test listrep-3.6.1 { + Inserts in back of unshared spanned list with insufficient total freespace + should reallocate with all *additional* space at back. Note this differs + from the insert in front case because here we realloc() - lreplace version +} -constraints testlistrep -body { + set l [lreplace [freeSpaceBoth 8 1 1] $end+1 $end+1 8 9 10] + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list [irange 0 10] 1 10 1] + +test listrep-3.6.2 { + Inserts in back of unshared spanned list with insufficient total freespace + should reallocate with all *additional* space at back. Note this differs + from the insert in front case because here we realloc() - lappend version +} -constraints testlistrep -body { + set l [freeSpaceBoth 8 1 1] + lappend l 8 9 10 + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list [irange 0 10] 1 10 1] + +test listrep-3.6.3 { + Inserts in back of unshared spanned list with insufficient total freespace + should reallocate with all *additional* space at back. Note this differs + from the insert in front case because here we realloc() - lset version +} -constraints testlistrep -body { + set l [freeSpaceNone] + lset l $end+1 8 + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list [irange 0 8] 0 9 1] + test listrep-3.7 { Inserts in front half of unshared spanned list with room in front should not reallocate and should move front segment @@ -637,148 +1296,390 @@ test listrep-3.7 { test listrep-3.8 { Inserts in front half of unshared spanned list with insufficient leading - space but with enough tail space + space but with enough tail space - linsert version } -constraints testlistrep -body { set l [linsert [freeSpaceBoth 8 1 5] $one -2 -1] validate $l list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] } -result [list {0 -2 -1 1 2 3 4 5 6 7} 1 3 1] +test listrep-3.8.1 { + Inserts in front half of unshared spanned list with insufficient leading + space but with enough tail space - lreplace version +} -constraints testlistrep -body { + set l [lreplace [freeSpaceBoth 8 1 5] $one -1 -2 -1] + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list {0 -2 -1 1 2 3 4 5 6 7} 1 3 1] + test listrep-3.9 { - Inserts in front half of unshared spanned list with sufficient total free space + Inserts in front half of unshared spanned list with sufficient total + free space - linsert version } -constraints testlistrep -body { set l [linsert [freeSpaceBoth 8 2 2] $one -3 -2 -1] validate $l list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] } -result [list {0 -3 -2 -1 1 2 3 4 5 6 7} 0 1 1] +test listrep-3.9.1 { + Inserts in front half of unshared spanned list with sufficient total + free space - lreplace version +} -constraints testlistrep -body { + set l [lreplace [freeSpaceBoth 8 2 2] $one -1 -3 -2 -1] + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list {0 -3 -2 -1 1 2 3 4 5 6 7} 0 1 1] + test listrep-3.10 { Inserts in front half of unshared spanned list with insufficient total space. - Note use of realloc() means new space will be at the back + Note use of realloc() means new space will be at the back - linsert version } -constraints testlistrep -body { set l [linsert [freeSpaceBoth 8 1 1] $one -3 -2 -1] validate $l list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] } -result [list {0 -3 -2 -1 1 2 3 4 5 6 7} 1 10 1] +test listrep-3.10.1 { + Inserts in front half of unshared spanned list with insufficient total space. + Note use of realloc() means new space will be at the back - lreplace version +} -constraints testlistrep -body { + set l [lreplace [freeSpaceBoth 8 1 1] $one -1 -3 -2 -1] + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list {0 -3 -2 -1 1 2 3 4 5 6 7} 1 10 1] + test listrep-3.11 { Inserts in back half of unshared spanned list with room in back should not - reallocate and should move back segment + reallocate and should move back segment - linsert version } -constraints testlistrep -body { set l [linsert [freeSpaceBoth] $end-$one 8 9] validate $l list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] } -result [list {0 1 2 3 4 5 6 8 9 7} 3 1 1] +test listrep-3.11.1 { + Inserts in back half of unshared spanned list with room in back should not + reallocate and should move back segment - lreplace version +} -constraints testlistrep -body { + set l [lreplace [freeSpaceBoth] $end -1 8 9] + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list {0 1 2 3 4 5 6 8 9 7} 3 1 1] + test listrep-3.12 { Inserts in back half of unshared spanned list with insufficient tail - space but with enough leading space + space but with enough leading space - linsert version } -constraints testlistrep -body { set l [linsert [freeSpaceBoth 8 5 1] $end-$one 8 9] validate $l list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] } -result [list {0 1 2 3 4 5 6 8 9 7} 3 1 1] +test listrep-3.12.1 { + Inserts in back half of unshared spanned list with insufficient tail + space but with enough leading space - lreplace version +} -constraints testlistrep -body { + set l [lreplace [freeSpaceBoth 8 5 1] $end -1 8 9] + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list {0 1 2 3 4 5 6 8 9 7} 3 1 1] + test listrep-3.13 { - Inserts in back half of unshared spanned list with sufficient total free space + Inserts in back half of unshared spanned list with sufficient total + free space - linsert version } -constraints testlistrep -body { set l [linsert [freeSpaceBoth 8 2 2] $end-$one 8 9 10] validate $l list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] } -result [list {0 1 2 3 4 5 6 8 9 10 7} 0 1 1] +test listrep-3.13.1 { + Inserts in back half of unshared spanned list with sufficient total + free space - lreplace version +} -constraints testlistrep -body { + set l [lreplace [freeSpaceBoth 8 2 2] $end -1 8 9 10] + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list {0 1 2 3 4 5 6 8 9 10 7} 0 1 1] + test listrep-3.14 { - Inserts in back half of unshared spanned list with insufficient total space. - Note use of realloc() means new space will be at the back + Inserts in back half of unshared spanned list with insufficient + total space. Note use of realloc() means new space will be at the + back - linsert version } -constraints testlistrep -body { set l [linsert [freeSpaceBoth 8 1 1] $end-$one 8 9 10] validate $l list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] } -result [list {0 1 2 3 4 5 6 8 9 10 7} 1 10 1] +test listrep-3.14.1 { + Inserts in back half of unshared spanned list with insufficient + total space. Note use of realloc() means new space will be at the + back - lrepalce version +} -constraints testlistrep -body { + set l [lreplace [freeSpaceBoth 8 1 1] $end -1 8 9 10] + validate $l + list $l [leadSpace $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list {0 1 2 3 4 5 6 8 9 10 7} 1 10 1] + test listrep-3.15 { Deletes from front of small unshared span list results in elements - moved up front and span removal + moved up front and span removal - lreplace version } -constraints testlistrep -body { set l [lreplace [freeSpaceBoth] $zero $zero] validate $l - list $l [leadSpace $l] [tailSpace $l] [hasSpan $l] -} -result [list {1 2 3 4 5 6 7} 0 7 0] + list $l [leadSpace $l] [tailSpace $l] [hasSpan $l] +} -result [list {1 2 3 4 5 6 7} 0 7 0] + +test listrep-3.15.1 { + Deletes from front of small unshared span list results in elements + moved up front and span removal - lremove version +} -constraints testlistrep -body { + set l [lremove [freeSpaceBoth] $zero $one] + validate $l + list $l [leadSpace $l] [tailSpace $l] [hasSpan $l] +} -result [list {2 3 4 5 6 7} 0 8 0] + +test listrep-3.15.2 { + Deletes from front of small unshared span list results in elements + moved up front and span removal - lrange version +} -constraints testlistrep -body { + set l [lrange [freeSpaceBoth] $one $end] + validate $l + list $l [leadSpace $l] [tailSpace $l] [hasSpan $l] +} -result [list {1 2 3 4 5 6 7} 0 7 0] + +test listrep-3.15.3 { + Deletes from front of small unshared span list results in elements + moved up front and span removal - lassign version +} -constraints testlistrep -body { + set l [lassign [freeSpaceBoth] e] + validate $l + list $e $l [leadSpace $l] [tailSpace $l] [hasSpan $l] +} -result [list 0 {1 2 3 4 5 6 7} 0 7 0] + +test listrep-3.15.4 { + Deletes from front of small unshared span list results in elements + moved up front and span removal - lpop version +} -constraints testlistrep -body { + set l [freeSpaceBoth] + set e [lpop l $zero] + validate $l + list $l [leadSpace $l] [tailSpace $l] [hasSpan $l] +} -result [list {1 2 3 4 5 6 7} 0 7 0] + +test listrep-3.16 { + Deletes from front of large unshared span list results in another + span - lreplace version +} -constraints testlistrep -body { + set l [lreplace [freeSpaceBoth 1000 10 10] $zero $one] + validate $l + list $l [leadSpace $l] [tailSpace $l] [hasSpan $l 12 998] +} -result [list [irange 2 999] 12 10 1] + +test listrep-3.16.1 { + Deletes from front of large unshared span list results in another + span - lremove version +} -constraints testlistrep -body { + set l [lremove [freeSpaceBoth 1000 10 10] $zero $one] + validate $l + list $l [leadSpace $l] [tailSpace $l] [hasSpan $l 12 998] +} -result [list [irange 2 999] 12 10 1] + +test listrep-3.16.2 { + Deletes from front of large unshared span list results in another + span - lrange version +} -constraints testlistrep -body { + set l [lrange [freeSpaceBoth 1000 10 10] $two $end] + validate $l + list $l [leadSpace $l] [tailSpace $l] [hasSpan $l 12 998] +} -result [list [irange 2 999] 12 10 1] + +test listrep-3.16.3 { + Deletes from front of large unshared span list results in another + span - lassign version +} -constraints testlistrep -body { + set l [lassign [freeSpaceBoth 1000 10 10] e] + validate $l + list $e $l [leadSpace $l] [tailSpace $l] [hasSpan $l 11 999] +} -result [list 0 [irange 1 999] 11 10 1] -test listrep-3.16 { +test listrep-3.16.4 { Deletes from front of large unshared span list results in another - span + span - lpop version } -constraints testlistrep -body { - set l [lreplace [freeSpaceBoth 1000 10 10] $zero $one] + set l [freeSpaceBoth 1000 10 10] + set e [lpop l $zero] validate $l - list $l [leadSpace $l] [tailSpace $l] [hasSpan $l 12 998] -} -result [list [irange 2 999] 12 10 1] + list $e $l [leadSpace $l] [tailSpace $l] [hasSpan $l 11 999] +} -result [list 0 [irange 1 999] 11 10 1] test listrep-3.17 { Deletes from back of small unshared span list results in new store - without span + without span - lreplace version } -constraints testlistrep -body { set l [lreplace [freeSpaceBoth] $end $end] validate $l list $l [leadSpace $l] [tailSpace $l] [hasSpan $l] } -result [list {0 1 2 3 4 5 6} 0 7 0] +test listrep-3.17.1 { + Deletes from back of small unshared span list results in new store + without span - lremove version +} -constraints testlistrep -body { + set l [lremove [freeSpaceBoth] $end] + validate $l + list $l [leadSpace $l] [tailSpace $l] [hasSpan $l] +} -result [list {0 1 2 3 4 5 6} 0 7 0] + +test listrep-3.17.2 { + Deletes from back of small unshared span list results in new store + without span - lrange version +} -constraints testlistrep -body { + set l [lrange [freeSpaceBoth] $zero $end-1] + validate $l + list $l [leadSpace $l] [tailSpace $l] [hasSpan $l] +} -result [list {0 1 2 3 4 5 6} 0 7 0] + +test listrep-3.17.3 { + Deletes from back of small unshared span list results in new store + without span - lpop version +} -constraints testlistrep -body { + set l [freeSpaceBoth] + set e [lpop l] + validate $l + list $e $l [leadSpace $l] [tailSpace $l] [hasSpan $l] +} -result [list 7 {0 1 2 3 4 5 6} 0 7 0] + test listrep-3.18 { Deletes from back of large unshared span list results in another - span + span - lreplace version } -constraints testlistrep -body { set l [lreplace [freeSpaceBoth 1000 10 10] $end-1 $end] validate $l list $l [leadSpace $l] [tailSpace $l] [hasSpan $l 10 998] } -result [list [irange 0 997] 10 12 1] +test listrep-3.18.1 { + Deletes from back of large unshared span list results in another + span - lremove version +} -constraints testlistrep -body { + set l [lremove [freeSpaceBoth 1000 10 10] $end-1 $end] + validate $l + list $l [leadSpace $l] [tailSpace $l] [hasSpan $l 10 998] +} -result [list [irange 0 997] 10 12 1] + +test listrep-3.18.2 { + Deletes from back of large unshared span list results in another + span - lrange version +} -constraints testlistrep -body { + set l [lrange [freeSpaceBoth 1000 10 10] $zero $end-2] + validate $l + list $l [leadSpace $l] [tailSpace $l] [hasSpan $l 10 998] +} -result [list [irange 0 997] 10 12 1] + +test listrep-3.18.3 { + Deletes from back of large unshared span list results in another + span - lpop version +} -constraints testlistrep -body { + set l [freeSpaceBoth 1000 10 10] + set e [lpop l] + validate $l + list $e $l [leadSpace $l] [tailSpace $l] [hasSpan $l 10 999] +} -result [list 999 [irange 0 998] 10 11 1] + test listrep-3.19 { Deletes from front half of small unshared span list results in - movement of smaller front segment + movement of smaller front segment - lreplace version } -constraints testlistrep -body { set l [lreplace [freeSpaceBoth] $one $two] validate $l list $l [leadSpace $l] [tailSpace $l] [hasSpan $l 5 6] } -result [list {0 3 4 5 6 7} 5 3 1] +test listrep-3.19.1 { + Deletes from front half of small unshared span list results in + movement of smaller front segment - lremove version +} -constraints testlistrep -body { + set l [lremove [freeSpaceBoth] $one $two] + validate $l + list $l [leadSpace $l] [tailSpace $l] [hasSpan $l 5 6] +} -result [list {0 3 4 5 6 7} 5 3 1] + test listrep-3.20 { Deletes from front half of large unshared span list results in - movement of smaller front segment + movement of smaller front segment - lreplace version } -constraints testlistrep -body { set l [lreplace [freeSpaceBoth 1000 10 10] $one $two] validate $l list $l [leadSpace $l] [tailSpace $l] [hasSpan $l 12 998] } -result [list [list 0 {*}[irange 3 999]] 12 10 1] +test listrep-3.20.1 { + Deletes from front half of large unshared span list results in + movement of smaller front segment - lremove version +} -constraints testlistrep -body { + set l [lremove [freeSpaceBoth 1000 10 10] $one $two] + validate $l + list $l [leadSpace $l] [tailSpace $l] [hasSpan $l 12 998] +} -result [list [list 0 {*}[irange 3 999]] 12 10 1] + test listrep-3.21 { Deletes from back half of small unshared span list results in - movement of smaller back segment + movement of smaller back segment - lreplace version } -constraints testlistrep -body { set l [lreplace [freeSpaceBoth] $end-2 $end-1] validate $l list $l [leadSpace $l] [tailSpace $l] [hasSpan $l 3 6] } -result [list {0 1 2 3 4 7} 3 5 1] -test listrep-3.22 { +test listrep-3.21.1 { Deletes from back half of small unshared span list results in - movement of smaller back segment + movement of smaller back segment - lremove version +} -constraints testlistrep -body { + set l [lremove [freeSpaceBoth] $end-2 $end-1] + validate $l + list $l [leadSpace $l] [tailSpace $l] [hasSpan $l 3 6] +} -result [list {0 1 2 3 4 7} 3 5 1] + +test listrep-3.22 { + Deletes from back half of large unshared span list results in + movement of smaller back segment - lreplace version } -constraints testlistrep -body { set l [lreplace [freeSpaceBoth 1000 10 10] $end-2 $end-1] validate $l list $l [leadSpace $l] [tailSpace $l] [hasSpan $l 10 998] } -result [list [list {*}[irange 0 996] 999] 10 12 1] +test listrep-3.22.1 { + Deletes from back half of large unshared span list results in + movement of smaller back segment - lremove version +} -constraints testlistrep -body { + set l [lremove [freeSpaceBoth 1000 10 10] $end-2 $end-1] + validate $l + list $l [leadSpace $l] [tailSpace $l] [hasSpan $l 10 998] +} -result [list [list {*}[irange 0 996] 999] 10 12 1] + test listrep-3.23 { Replacement of elements at front with same number elements in unshared - spanned list is in-place + spanned list is in-place - lreplace version } -body { set l [lreplace [freeSpaceBoth] $zero $one 10 11] list $l [leadSpace $l] [tailSpace $l] } -result [list {10 11 2 3 4 5 6 7} 3 3] +test listrep-3.23.1 { + Replacement of elements at front with same number elements in unshared + spanned list is in-place - lset version +} -body { + set l [freeSpaceBoth] + lset l $zero 10 + list $l [leadSpace $l] [tailSpace $l] +} -result [list {10 1 2 3 4 5 6 7} 3 3] + test listrep-3.24 { Replacement of elements at front with fewer elements in unshared - spanned list expands leading space + spanned list expands leading space - lreplace version } -body { set l [lreplace [freeSpaceBoth] $zero $four 10] list $l [leadSpace $l] [tailSpace $l] @@ -813,17 +1714,29 @@ test listrep-3.27 { test listrep-3.28 { Replacement of elements at back with same number of elements in unshared - spanned list is in-place + spanned list is in-place - lreplace version } -body { set l [lreplace [freeSpaceBoth] $end-1 $end 10 11] + validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {0 1 2 3 4 5 10 11} 3 3] +test listrep-3.28.1 { + Replacement of elements at back with same number of elements in unshared + spanned list is in-place - lset version +} -body { + set l [freeSpaceBoth] + lset l $end 10 + validate $l + list $l [leadSpace $l] [tailSpace $l] +} -result [list {0 1 2 3 4 5 6 10} 3 3] + test listrep-3.29 { Replacement of elements at back with fewer elements in unshared spanned list expands tail space } -body { set l [lreplace [freeSpaceBoth] $end-2 $end 10] + validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {0 1 2 3 4 10} 3 5] @@ -832,6 +1745,7 @@ test listrep-3.30 { spanned list with sufficient tail space shrinks tailspace } -body { set l [lreplace [freeSpaceBoth] $end-1 $end 10 11 12] + validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {0 1 2 3 4 5 10 11 12} 3 2] @@ -840,6 +1754,7 @@ test listrep-3.31 { with insufficient tail space but enough total free space moves up the span } -body { set l [lreplace [freeSpaceBoth 8 2 2] $end-1 $end 10 11 12 13 14] + validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {0 1 2 3 4 5 10 11 12 13 14} 0 1] @@ -849,22 +1764,35 @@ test listrep-3.32 { of realloc() } -body { set l [lreplace [freeSpaceBoth 8 1 1] $end-1 $end 10 11 12 13 14] + validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {0 1 2 3 4 5 10 11 12 13 14} 1 10] test listrep-3.33 { Replacement of elements in the middle in an unshared spanned list with - the same number of elements + the same number of elements - lreplace version } -body { set l [lreplace [freeSpaceBoth] $two $four 10 11 12] + validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {0 1 10 11 12 5 6 7} 3 3] +test listrep-3.33.1 { + Replacement of elements in the middle in an unshared spanned list with + the same number of elements - lset version +} -body { + set l [freeSpaceBoth] + lset l $two 10 + validate $l + list $l [leadSpace $l] [tailSpace $l] +} -result [list {0 1 10 3 4 5 6 7} 3 3] + test listrep-3.34 { Replacement of elements in an unshared spanned list with fewer elements in the front half moves the front (smaller) segment } -body { set l [lreplace [freeSpaceBoth] $two $four 10 11] + validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {0 1 10 11 5 6 7} 4 3] @@ -873,6 +1801,7 @@ test listrep-3.35 { in the back half moves the tail (smaller) segment } -body { set l [lreplace [freeSpaceBoth] $end-2 $end-1 10] + validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {0 1 2 3 4 10 7} 3 4] @@ -882,6 +1811,7 @@ test listrep-3.36 { (front case) } -body { set l [lreplace [freeSpaceBoth] $one $two 8 9 10] + validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {0 8 9 10 3 4 5 6 7} 2 3] @@ -891,6 +1821,7 @@ test listrep-3.37 { (back case) } -body { set l [lreplace [freeSpaceBoth] $end-2 $end-1 8 9 10] + validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {0 1 2 3 4 8 9 10 7} 3 2] @@ -899,6 +1830,7 @@ test listrep-3.38 { when only front has room } -body { set l [lreplace [freeSpaceBoth 8 3 1] $end-1 $end-1 8 9 10] + validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {0 1 2 3 4 5 8 9 10 7} 1 1] @@ -907,6 +1839,7 @@ test listrep-3.39 { when only back has room } -body { set l [lreplace [freeSpaceBoth 8 1 3] $one $one 8 9 10] + validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {0 8 9 10 2 3 4 5 6 7} 1 1] @@ -915,6 +1848,7 @@ test listrep-3.40 { when neither send has enough room by itself } -body { set l [lreplace [freeSpaceBoth] $one $one 8 9 10 11 12] + validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {0 8 9 10 11 12 2 3 4 5 6 7} 1 1] @@ -924,6 +1858,7 @@ test listrep-3.41 { end has more space because of realloc() } -body { set l [lreplace [freeSpaceBoth 8 1 1] $one $one 8 9 10 11 12] + validate $l list $l [leadSpace $l] [tailSpace $l] } -result [list {0 8 9 10 11 12 2 3 4 5 6 7} 1 11] @@ -932,17 +1867,29 @@ test listrep-3.41 { test listrep-4.1 { Inserts in front of shared spanned list with used elements in lead space - creates a new list rep without more lead space than tail space. + creates new list rep with more lead than tail space - linsert version } -constraints testlistrep -body { set master [freeSpaceNone 1000] set spanl [lrange $master $two $end-2] set l [linsert $spanl $zero -1] + validate $l list $master $spanl $l [leadSpaceMore $l] [hasSpan $l] [repStoreRefCount $master] [repStoreRefCount $spanl] [repStoreRefCount $l] } -result [list [irange 0 999] [irange 2 997] [list -1 {*}[irange 2 997]] 1 1 2 2 1] +test listrep-4.1.1 { + Inserts in front of shared spanned list with used elements in lead space + creates new list rep with more lead than tail space - lreplace version +} -constraints testlistrep -body { + set master [freeSpaceNone 1000] + set spanl [lrange $master $two $end-2] + set l [lreplace $spanl $zero -1 -2] + validate $l + list $master $spanl $l [leadSpaceMore $l] [hasSpan $l] [repStoreRefCount $master] [repStoreRefCount $spanl] [repStoreRefCount $l] +} -result [list [irange 0 999] [irange 2 997] [list -2 {*}[irange 2 997]] 1 1 2 2 1] + test listrep-4.2 { Inserts in front of shared spanned list with orphaned leading elements - allocate a new list rep with more lead space than tail space. + allocate a new list rep with more lead than tail space - linsert version TODO - ideally this should garbage collect the orphans and reuse the lead space but that needs a "lprepend" command else the listrep operand is shared and hence orphans cannot be freed @@ -951,16 +1898,44 @@ test listrep-4.2 { set spanl [lrange $master $two $end-2] unset master; # So elements at 0, 1 are not used set l [linsert $spanl $zero -1] + validate $l list $spanl $l [sameStore $spanl $l] [leadSpaceMore $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] } -result [list [irange 2 997] [list -1 {*}[irange 2 997]] 0 1 1 1 1] +test listrep-4.2.1 { + Inserts in front of shared spanned list with orphaned leading elements + allocate a new list rep with more lead than tail space - lreplace version + TODO - ideally this should garbage collect the orphans and reuse the lead space + but that needs a "lprepend" command else the listrep operand is shared and hence + orphans cannot be freed +} -constraints testlistrep -body { + set master [freeSpaceLead 1000 100] + set spanl [lrange $master $two $end-2] + unset master; # So elements at 0, 1 are not used + set l [lreplace $spanl $zero -1 -2] + validate $l + list $spanl $l [sameStore $spanl $l] [leadSpaceMore $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] +} -result [list [irange 2 997] [list -2 {*}[irange 2 997]] 0 1 1 1 1] + test listrep-4.3 { Inserts in front of shared spanned list where span is at front of used - space reuses the same list store. + space reuses the same list store - linsert version } -constraints testlistrep -body { set master [freeSpaceLead 1000 100] set spanl [lrange $master $zero $end-2] set l [linsert $spanl $zero -1] + validate $l + list $spanl $l [sameStore $spanl $l] [leadSpace $l] [tailSpace $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] +} -result [list [irange 0 997] [irange -1 997] 1 99 0 1 3 3] + +test listrep-4.3.1 { + Inserts in front of shared spanned list where span is at front of used + space reuses the same list store - lreplace version +} -constraints testlistrep -body { + set master [freeSpaceLead 1000 100] + set spanl [lrange $master $zero $end-2] + set l [lreplace $spanl $zero -1 -1] + validate $l list $spanl $l [sameStore $spanl $l] [leadSpace $l] [tailSpace $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] } -result [list [irange 0 997] [irange -1 997] 1 99 0 1 3 3] @@ -968,73 +1943,258 @@ test listrep-4.4 { Inserts in front of shared spanned list where span is at front of used space allocates new listrep if lead space insufficient even if total free space is sufficient. New listrep should have more lead space than tail space. + - linsert version } -constraints testlistrep -body { set master [freeSpaceBoth 1000 2] set spanl [lrange $master $zero $end-2] set l [linsert $spanl $zero -3 -2 -1] + validate $l + list $spanl $l [sameStore $spanl $l] [leadSpaceMore $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] +} -result [list [irange 0 997] [irange -3 997] 0 1 1 2 1] + +test listrep-4.4.1 { + Inserts in front of shared spanned list where span is at front of used + space allocates new listrep if lead space insufficient even if total free space + is sufficient. New listrep should have more lead space than tail space. + - lreplace version +} -constraints testlistrep -body { + set master [freeSpaceBoth 1000 2] + set spanl [lrange $master $zero $end-2] + set l [lreplace $spanl $zero -1 -3 -2 -1] + validate $l list $spanl $l [sameStore $spanl $l] [leadSpaceMore $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] } -result [list [irange 0 997] [irange -3 997] 0 1 1 2 1] test listrep-4.5 { Inserts in back of shared spanned list where span is at end of used space still allocates a new listrep and trailing space is more than leading space + - linsert version } -constraints testlistrep -body { set master [freeSpaceBoth 1000 2] set spanl [lrange $master $two $end] set l [linsert $spanl $end 1000] + validate $l + list $spanl $l [sameStore $spanl $l] [tailSpaceMore $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] +} -result [list [irange 2 999] [irange 2 1000] 0 1 1 2 1] + +test listrep-4.5.1 { + Inserts in back of shared spanned list where span is at end of used space + still allocates a new listrep and trailing space is more than leading space + - lreplace version +} -constraints testlistrep -body { + set master [freeSpaceBoth 1000 2] + set spanl [lrange $master $two $end] + set l [lreplace $spanl $end+1 $end+1 1000] + validate $l list $spanl $l [sameStore $spanl $l] [tailSpaceMore $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] } -result [list [irange 2 999] [irange 2 1000] 0 1 1 2 1] +test listrep-4.5.2 { + Inserts in back of shared spanned list where span is at end of used space + still allocates a new listrep and trailing space is more than leading space + - lappend version +} -constraints testlistrep -body { + set master [freeSpaceBoth 1000 2] + set l [lrange $master $two $end] + lappend l 1000 + validate $l + list $l [sameStore $master $l] [tailSpaceMore $l] [hasSpan $l] [repStoreRefCount $l] +} -result [list [irange 2 1000] 0 1 1 1] + +test listrep-4.5.3 { + Inserts in back of shared spanned list where span is at end of used space + still allocates a new listrep and trailing space is more than leading space + - lset version +} -constraints testlistrep -body { + set master [freeSpaceBoth 1000 2] + set l [lrange $master $two $end] + lset l $end+1 1000 + validate $l + list $l [sameStore $master $l] [tailSpaceMore $l] [hasSpan $l] [repStoreRefCount $l] +} -result [list [irange 2 1000] 0 1 1 1] + + test listrep-4.6 { Inserts in middle of shared spanned list allocates a new listrep with equal - lead and tail space + lead and tail space - linsert version } -constraints testlistrep -body { set master [freeSpaceBoth 1000 2] set spanl [lrange $master $two $end-2] set i 200 set l [linsert $spanl $i 1000] + validate $l + list $spanl $l [sameStore $spanl $l] [spaceEqual $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] +} -result [list [irange 2 997] [concat [irange 2 201] 1000 [irange 202 997]] 0 1 1 2 1] + +test listrep-4.6.1 { + Inserts in middle of shared spanned list allocates a new listrep with equal + lead and tail space - lreplace version +} -constraints testlistrep -body { + set master [freeSpaceBoth 1000 2] + set spanl [lrange $master $two $end-2] + set i 200 + set l [lreplace $spanl $i -1 1000] + validate $l list $spanl $l [sameStore $spanl $l] [spaceEqual $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] } -result [list [irange 2 997] [concat [irange 2 201] 1000 [irange 202 997]] 0 1 1 2 1] test listrep-4.7 { Deletes from front of shared spanned list do not create a new allocation + - lreplace version } -constraints testlistrep -body { set master [freeSpaceNone 1000] set spanl [lrange $master $two $end-2] set l [lreplace $spanl $zero $one] + validate $l + list $spanl $l [sameStore $spanl $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] +} -result [list [irange 2 997] [irange 4 997] 1 1 3 3] + +test listrep-4.7.1 { + Deletes from front of shared spanned list do not create a new allocation + - lremove version +} -constraints testlistrep -body { + set master [freeSpaceNone 1000] + set spanl [lrange $master $two $end-2] + set l [lremove $spanl $zero $one] + validate $l + list $spanl $l [sameStore $spanl $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] +} -result [list [irange 2 997] [irange 4 997] 1 1 3 3] + +test listrep-4.7.2 { + Deletes from front of shared spanned list do not create a new allocation + - lrange version +} -constraints testlistrep -body { + set master [freeSpaceNone 1000] + set spanl [lrange $master $two $end-2] + set l [lrange $spanl $two $end] + validate $l list $spanl $l [sameStore $spanl $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] } -result [list [irange 2 997] [irange 4 997] 1 1 3 3] +test listrep-4.7.3 { + Deletes from front of shared spanned list do not create a new allocation + - lassign version +} -constraints testlistrep -body { + set master [freeSpaceNone 1000] + set spanl [lrange $master $two $end-2] + set l [lassign $spanl e] + validate $l + list $e $spanl $l [sameStore $spanl $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] +} -result [list 2 [irange 2 997] [irange 3 997] 1 1 3 3] + +test listrep-4.7.4 { + Deletes from front of shared spanned list do not create a new allocation + - lpop version +} -constraints testlistrep -body { + set master [freeSpaceNone 1000] + set l [lrange $master $two $end-2] + set e [lpop l $zero] + validate $l + list $e $l [sameStore $master $l] [hasSpan $l] [repStoreRefCount $l] +} -result [list 2 [irange 3 997] 1 1 2] + test listrep-4.8 { Deletes from end of shared spanned list do not create a new allocation + - lreplace version } -constraints testlistrep -body { set master [freeSpaceNone 1000] set spanl [lrange $master $two $end-2] set l [lreplace $spanl $end-1 $end] + validate $l list $spanl $l [sameStore $spanl $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] } -result [list [irange 2 997] [irange 2 995] 1 1 3 3] +test listrep-4.8.1 { + Deletes from end of shared spanned list do not create a new allocation + - lremove version +} -constraints testlistrep -body { + set master [freeSpaceNone 1000] + set spanl [lrange $master $two $end-2] + set l [lremove $spanl $end-1 $end] + validate $l + list $spanl $l [sameStore $spanl $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] +} -result [list [irange 2 997] [irange 2 995] 1 1 3 3] + +test listrep-4.8.2 { + Deletes from end of shared spanned list do not create a new allocation + - lrange version +} -constraints testlistrep -body { + set master [freeSpaceNone 1000] + set spanl [lrange $master $two $end-2] + set l [lrange $spanl 0 $end-2] + validate $l + list $spanl $l [sameStore $spanl $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] +} -result [list [irange 2 997] [irange 2 995] 1 1 3 3] + +test listrep-4.8.3 { + Deletes from end of shared spanned list do not create a new allocation + - lpop version +} -constraints testlistrep -body { + set master [freeSpaceNone 1000] + set l [lrange $master $two $end-2] + set e [lpop l] + validate $l + list $e $l [sameStore $master $l] [hasSpan $l] [repStoreRefCount $l] +} -result [list 997 [irange 2 996] 1 1 2] + test listrep-4.9 { Deletes from middle of shared spanned list creates a new allocation with - equal free space at front and back + equal free space at front and back - lreplace version } -constraints testlistrep -body { set master [freeSpaceNone 1000] set spanl [lrange $master $two $end-2] set i 500 set l [lreplace $spanl $i $i] + validate $l + list $spanl $l [sameStore $spanl $l] [hasSpan $l] [spaceEqual $l] [repStoreRefCount $spanl] [repStoreRefCount $l] +} -result [list [irange 2 997] [concat [irange 2 501] [irange 503 997]] 0 1 1 2 1] + +test listrep-4.9.1 { + Deletes from middle of shared spanned list creates a new allocation with + equal free space at front and back - lremove version +} -constraints testlistrep -body { + set master [freeSpaceNone 1000] + set spanl [lrange $master $two $end-2] + set i 500 + set l [lremove $spanl $i $i] + validate $l list $spanl $l [sameStore $spanl $l] [hasSpan $l] [spaceEqual $l] [repStoreRefCount $spanl] [repStoreRefCount $l] } -result [list [irange 2 997] [concat [irange 2 501] [irange 503 997]] 0 1 1 2 1] +test listrep-4.9.2 { + Deletes from middle of shared spanned list creates a new allocation with + equal free space at front and back - lpop version +} -constraints testlistrep -body { + set master [freeSpaceNone 1000] + set l [lrange $master $two $end-2] + set i 500 + set e [lpop l $i] + validate $l + list $e $l [sameStore $master $l] [hasSpan $l] [spaceEqual $l] [repStoreRefCount $l] +} -result [list 502 [concat [irange 2 501] [irange 503 997]] 0 1 1 1] + test listrep-4.10 { Replacements with same number of elements at front of shared spanned list - create a new allocation with more space in front + create a new allocation with more space in front - lreplace version } -constraints testlistrep -body { set master [freeSpaceNone 1000] set spanl [lrange $master $two $end-2] set l [lreplace $spanl $zero $one -2 -1] + validate $l list $spanl $l [sameStore $spanl $l] [leadSpaceMore $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] } -result [list [irange 2 997] [concat {-2 -1} [irange 4 997]] 0 1 1 2 1] +test listrep-4.10.1 { + Replacements with same number of elements at front of shared spanned list + create a new allocation with exact size +} -constraints testlistrep -body { + set master [freeSpaceNone 1000] + set l [lrange $master $two $end-2] + lset l $zero -1 + validate $l + list $l [sameStore $master $l] [hasSpan $l] [repStoreRefCount $l] +} -result [list [concat {-1} [irange 3 997]] 0 0 1] + test listrep-4.11 { Replacements with fewer elements at front of shared spanned list create a new allocation with more space in front @@ -1042,6 +2202,7 @@ test listrep-4.11 { set master [freeSpaceNone 1000] set spanl [lrange $master $two $end-2] set l [lreplace $spanl $zero $one -1] + validate $l list $spanl $l [sameStore $spanl $l] [leadSpaceMore $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] } -result [list [irange 2 997] [concat {-1} [irange 4 997]] 0 1 1 2 1] @@ -1052,19 +2213,32 @@ test listrep-4.12 { set master [freeSpaceNone 1000] set spanl [lrange $master $two $end-2] set l [lreplace $spanl $zero $one -3 -2 -1] + validate $l list $spanl $l [sameStore $spanl $l] [leadSpaceMore $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] } -result [list [irange 2 997] [concat {-3 -2 -1} [irange 4 997]] 0 1 1 2 1] test listrep-4.13 { Replacements with same number of elements at back of shared spanned list - create a new allocation with more space in back + create a new allocation with more space in back - lreplace version } -constraints testlistrep -body { set master [freeSpaceNone 1000] set spanl [lrange $master $two $end-2] set l [lreplace $spanl $end-1 $end 1000 1001] + validate $l list $spanl $l [sameStore $spanl $l] [tailSpaceMore $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] } -result [list [irange 2 997] [concat [irange 2 995] {1000 1001}] 0 1 1 2 1] +test listrep-4.13.1 { + Replacements with same number of elements at back of shared spanned list + create a new exact allocation with no span - lset version +} -constraints testlistrep -body { + set master [freeSpaceNone 1000] + set l [lrange $master $two $end-2] + lset l $end 1000 + validate $l + list $l [sameStore $master $l] [tailSpace $l] [hasSpan $l] [repStoreRefCount $l] +} -result [list [concat [irange 2 996] {1000}] 0 0 0 1] + test listrep-4.14 { Replacements with fewer elements at back of shared spanned list create a new allocation with more space in back @@ -1072,6 +2246,7 @@ test listrep-4.14 { set master [freeSpaceNone 1000] set spanl [lrange $master $two $end-2] set l [lreplace $spanl $end-1 $end 1000] + validate $l list $spanl $l [sameStore $spanl $l] [tailSpaceMore $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] } -result [list [irange 2 997] [concat [irange 2 995] {1000}] 0 1 1 2 1] @@ -1082,6 +2257,7 @@ test listrep-4.15 { set master [freeSpaceNone 1000] set spanl [lrange $master $two $end-2] set l [lreplace $spanl $end-1 $end 1000 1001 1002] + validate $l list $spanl $l [sameStore $spanl $l] [tailSpaceMore $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] } -result [list [irange 2 997] [concat [irange 2 995] {1000 1001 1002}] 0 1 1 2 1] @@ -1092,9 +2268,21 @@ test listrep-4.16 { set master [freeSpaceNone 1000] set spanl [lrange $master $two $end-2] set l [lreplace $spanl $one $two -2 -1] + validate $l list $spanl $l [sameStore $spanl $l] [spaceEqual $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] } -result [list [irange 2 997] [concat {2 -2 -1} [irange 5 997]] 0 1 1 2 1] +test listrep-4.16.1 { + Replacements with same number of elements in middle of shared spanned list + create a new exact allocation - lset version +} -constraints testlistrep -body { + set master [freeSpaceNone 1000] + set l [lrange $master $two $end-2] + lset l $one -2 + validate $l + list $l [sameStore $master $l] [hasSpan $l] [tailSpace $l] [repStoreRefCount $l] +} -result [list [concat {2 -2} [irange 4 997]] 0 0 0 1] + test listrep-4.17 { Replacements with fewer elements in middle of shared spanned list create a new allocation with equal lead and tail sapce @@ -1102,6 +2290,7 @@ test listrep-4.17 { set master [freeSpaceNone 1000] set spanl [lrange $master $two $end-2] set l [lreplace $spanl $end-2 $end-1 1000] + validate $l list $spanl $l [sameStore $spanl $l] [spaceEqual $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] } -result [list [irange 2 997] [concat [irange 2 994] {1000 997}] 0 1 1 2 1] @@ -1112,16 +2301,22 @@ test listrep-4.18 { set master [freeSpaceNone 1000] set spanl [lrange $master $two $end-2] set l [lreplace $spanl $end-2 $end-1 1000 1001 1002] + validate $l list $spanl $l [sameStore $spanl $l] [spaceEqual $l] [hasSpan $l] [repStoreRefCount $spanl] [repStoreRefCount $l] } -result [list [irange 2 997] [concat [irange 2 994] {1000 1001 1002 997}] 0 1 1 2 1] +# +# Tests when tcl-obj is shared but listrep is not (lappend, lset etc.) -# TBD - tests when tcl-obj is shared but listrep is not (lappend, lset etc.) +# TBD - canonical output on shared and spanned lists (see 1.10) # TBD - range and subrange tests # - spanned and unspanned # TBD - zombie tests # -# Special case - nested lremove (does not seem tested in 8.6) +# Special cases +# - nested lset (does not seem tested in 8.6) +# - lremove with multiple indices +# - nested lpop ::tcltest::cleanupTests return -- cgit v0.12