Changes in / [db1ebed:5235d49]

Files:

• libcfa/src/Makefile.am (modified) (1 diff)
• libcfa/src/containers/string.cfa (modified) (1 diff)
• libcfa/src/containers/string.hfa (modified) (1 diff)
• libcfa/src/containers/string_res.cfa (modified) (37 diffs)
• libcfa/src/containers/string_res.hfa (modified) (7 diffs)
• libcfa/src/containers/string_sharectx.hfa (added)
• tests/collections/.expect/string-api-coverage-noshare.txt (added)
• tests/collections/.expect/string-api-coverage.txt (modified) (1 diff)
• tests/collections/.expect/string-ctx-manage.txt (added)
• tests/collections/.expect/string-gc.txt (modified) (1 diff)
• tests/collections/.expect/string-overwrite-noshare.txt (added)
• tests/collections/string-api-coverage-noshare.cfa (added)
• tests/collections/string-api-coverage.cfa (modified) (3 diffs)
• tests/collections/string-ctx-manage.cfa (added)
• tests/collections/string-gc.cfa (modified) (2 diffs)
• tests/collections/string-overwrite-noshare.cfa (added)
• tests/collections/string-overwrite.cfa (modified) (6 diffs)
• tests/zombies/string-perf/.gitignore (added)
• tests/zombies/string-perf/Makefile (added)
• tests/zombies/string-perf/corpus-100-1-1.txt (added)
• tests/zombies/string-perf/corpus-100-10-1.txt (added)
• tests/zombies/string-perf/corpus-100-2-1.txt (added)
• tests/zombies/string-perf/corpus-100-20-1.txt (added)
• tests/zombies/string-perf/corpus-100-5-1.txt (added)
• tests/zombies/string-perf/corpus-5-20-1.txt (added)
• tests/zombies/string-perf/corpus-5-20-2.txt (added)
• tests/zombies/string-perf/corpus-5-20-3.txt (added)
• tests/zombies/string-perf/make-corpus.cfa (added)
• tests/zombies/string-perf/prog.cfa (added)

libcfa/src/Makefile.am

@@ -63 +63 @@
         containers/queueLockFree.hfa \
         containers/stackLockFree.hfa \
+        containers/string_sharectx.hfa \
         containers/vector2.hfa \
         vec/vec.hfa \

libcfa/src/containers/string.cfa

@@ -92 +92 @@
 }
 
-string ?=?(string & this, string other) {
+string & ?=?(string & this, string & other) { //// <---- straw man change
     (*this.inner) = (*other.inner);
     return this;

libcfa/src/containers/string.hfa

@@ -41 +41 @@
 void ?=?(string &s, const string &other);
 void ?=?(string &s, char other);
-string ?=?(string &s, string other);  // string tolerates memcpys; still saw calls to autogen 
-
+string & ?=?(string &s, string &other);  // surprising ret seems to help avoid calls to autogen
+//string ?=?( string &, string ) = void;
 void ^?{}(string &s);
 

libcfa/src/containers/string_res.cfa

@@ -15 +15 @@
 
 #include "string_res.hfa"
+#include "string_sharectx.hfa"
+
 #include <stdlib.hfa>  // e.g. malloc
-#include <string.h>    // e.g. strlen
+#include <assert.h>
 
 //######################### VbyteHeap "header" #########################
-
-
-
-
-
-
-
-
-// DON'T COMMIT:
-// #define VbyteDebug
-
-
-
-
 
 #ifdef VbyteDebug
@@ -54 +42 @@
 
     
-static inline void compaction( VbyteHeap & );                           // compaction of the byte area
-static inline void garbage( VbyteHeap & );                              // garbage collect the byte area
-static inline void extend( VbyteHeap &, int );                  // extend the size of the byte area
-static inline void reduce( VbyteHeap &, int );                  // reduce the size of the byte area
-
-static inline void ?{}( VbyteHeap &, int = 1000 );
-static inline void ^?{}( VbyteHeap & );
-static inline void ByteCopy( VbyteHeap &, char *, int, int, char *, int, int ); // copy a block of bytes from one location in the heap to another
-static inline int ByteCmp( VbyteHeap &, char *, int, int, char *, int, int );   // compare 2 blocks of bytes
-static inline char *VbyteAlloc( VbyteHeap &, int );                     // allocate a block bytes in the heap
-
-
-static inline void AddThisAfter( HandleNode &, HandleNode & );
-static inline void DeleteNode( HandleNode & );
-static inline void MoveThisAfter( HandleNode &, const HandleNode & );           // move current handle after parameter handle
+static void compaction( VbyteHeap & );                          // compaction of the byte area
+static void garbage( VbyteHeap &, int );                                // garbage collect the byte area
+static void extend( VbyteHeap &, int );                 // extend the size of the byte area
+static void reduce( VbyteHeap &, int );                 // reduce the size of the byte area
+
+static void ?{}( VbyteHeap &, size_t = 1000 );
+static void ^?{}( VbyteHeap & );
+
+static int ByteCmp( char *, int, int, char *, int, int );       // compare 2 blocks of bytes
+static char *VbyteAlloc( VbyteHeap &, int );                    // allocate a block bytes in the heap
+static char *VbyteTryAdjustLast( VbyteHeap &, int );
+
+static void AddThisAfter( HandleNode &, HandleNode & );
+static void DeleteNode( HandleNode & );
+static void MoveThisAfter( HandleNode &, const HandleNode & );          // move current handle after parameter handle
 
 
 // Allocate the storage for the variable sized area and intialize the heap variables.
 
-static inline void ?{}( VbyteHeap & this, int Size ) with(this) {
+static void ?{}( VbyteHeap & this, size_t Size ) with(this) {
 #ifdef VbyteDebug
     serr | "enter:VbyteHeap::VbyteHeap, this:" | &this | " Size:" | Size;
@@ -82 +70 @@
     ExtVbyte = (void *)( StartVbyte + CurrSize );
     Header.flink = Header.blink = &Header;
+    Header.ulink = & this;
 #ifdef VbyteDebug
     HeaderPtr = &Header;
@@ -91 +80 @@
 // Release the dynamically allocated storage for the byte area.
 
-static inline void ^?{}( VbyteHeap & this ) with(this) {
+static void ^?{}( VbyteHeap & this ) with(this) {
     free( StartVbyte );
 } // ~VbyteHeap
@@ -102 +91 @@
 // creator.
 
-void ?{}( HandleNode & this ) with(this) {
+static void ?{}( HandleNode & this ) with(this) {
 #ifdef VbyteDebug
     serr | "enter:HandleNode::HandleNode, this:" | &this;
@@ -117 +106 @@
 // collection.
 
-void ?{}( HandleNode & this, VbyteHeap & vh ) with(this) {
+static void ?{}( HandleNode & this, VbyteHeap & vh ) with(this) {
 #ifdef VbyteDebug
     serr | "enter:HandleNode::HandleNode, this:" | &this;
@@ -123 +112 @@
     s = 0;
     lnth = 0;
+    ulink = &vh;
     AddThisAfter( this, *vh.Header.blink );
 #ifdef VbyteDebug
@@ -133 +123 @@
 // is the responsibility of the creator to destroy it.
 
-void ^?{}( HandleNode & this ) with(this) {
+static void ^?{}( HandleNode & this ) with(this) {
 #ifdef VbyteDebug
     serr | "enter:HandleNode::~HandleNode, this:" | & this;
@@ -149 +139 @@
 } // ~HandleNode
 
+
+//######################### String Sharing Context #########################
+
+static string_sharectx * ambient_string_sharectx;               // fickle top of stack
+static string_sharectx default_string_sharectx = {NEW_SHARING}; // stable bottom of stack
+
+void ?{}( string_sharectx & this, StringSharectx_Mode mode ) with( this ) {
+    (older){ ambient_string_sharectx };
+    if ( mode == NEW_SHARING ) {
+        (activeHeap){ new( (size_t) 1000 ) };
+    } else {
+        verify( mode == NO_SHARING );
+        (activeHeap){ 0p };
+    }
+    ambient_string_sharectx = & this;
+}
+
+void ^?{}( string_sharectx & this ) with( this ) {
+    if ( activeHeap ) delete( activeHeap );
+
+    // unlink this from older-list starting from ambient_string_sharectx
+    // usually, this==ambient_string_sharectx and the loop runs zero times
+    string_sharectx *& c = ambient_string_sharectx;
+    while ( c != &this ) &c = &c->older;              // find this
+    c = this.older;                                   // unlink
+}
+
 //######################### String Resource #########################
 
 
-VbyteHeap HeapArea;
-
-VbyteHeap * DEBUG_string_heap = & HeapArea;
+VbyteHeap * DEBUG_string_heap() {
+    assert( ambient_string_sharectx->activeHeap && "No sharing context is active" );
+    return ambient_string_sharectx->activeHeap;
+}
 
 size_t DEBUG_string_bytes_avail_until_gc( VbyteHeap * heap ) {
@@ -160 +178 @@
 }
 
+size_t DEBUG_string_bytes_in_heap( VbyteHeap * heap ) {
+    return heap->CurrSize;
+}
+
 const char * DEBUG_string_heap_start( VbyteHeap * heap ) {
     return heap->StartVbyte;
 }
-
 
 // Returns the size of the string in bytes
@@ -187 +208 @@
     // Store auto-newline state so it can be restored
     bool anl = getANL$(out);
-    nlOff(out);
-    for (size_t i = 0; i < s.Handle.lnth; i++) {
-        // Need to re-apply on the last output operator, for whole-statement version
-        if (anl && i == s.Handle.lnth-1) nlOn(out);
-        out | s[i];
-    }
-    return out;
+    if( s.Handle.lnth == 0 ) {
+        sout | "";
+    } else {
+        nlOff(out);
+        for (size_t i = 0; i < s.Handle.lnth; i++) {
+            // Need to re-apply on the last output operator, for whole-statement version
+            if (anl && i == s.Handle.lnth-1) nlOn(out);
+            out | s[i];
+        }
+    }
 }
 
 // Empty constructor
 void ?{}(string_res &s) with(s) {
-    (Handle){ HeapArea };
+    if( ambient_string_sharectx->activeHeap ) {
+        (Handle){ * ambient_string_sharectx->activeHeap };
+        (shareEditSet_owns_ulink){ false };
+        verify( Handle.s == 0p && Handle.lnth == 0 );
+    } else {
+        (Handle){ * new( (size_t) 10 ) };  // TODO: can I lazily avoid allocating for empty string
+        (shareEditSet_owns_ulink){ true };
+        Handle.s = Handle.ulink->StartVbyte;
+        verify( Handle.lnth == 0 );
+    }
     s.shareEditSet_prev = &s;
     s.shareEditSet_next = &s;
 }
 
-// Constructor from a raw buffer and size
-void ?{}(string_res &s, const char* rhs, size_t rhslnth) with(s) {
-    (Handle){ HeapArea };
-    Handle.s = VbyteAlloc(HeapArea, rhslnth);
+static void eagerCopyCtorHelper(string_res &s, const char* rhs, size_t rhslnth) with(s) {
+    if( ambient_string_sharectx->activeHeap ) {
+        (Handle){ * ambient_string_sharectx->activeHeap };
+        (shareEditSet_owns_ulink){ false };
+    } else {
+        (Handle){ * new( rhslnth ) };
+        (shareEditSet_owns_ulink){ true };
+    }
+    Handle.s = VbyteAlloc(*Handle.ulink, rhslnth);
     Handle.lnth = rhslnth;
     for ( int i = 0; i < rhslnth; i += 1 ) {            // copy characters
@@ -215 +253 @@
 }
 
-// String literal constructor
-void ?{}(string_res &s, const char* rhs) {
-    (s){ rhs, strlen(rhs) };
+// Constructor from a raw buffer and size
+void ?{}(string_res &s, const char* rhs, size_t rhslnth) with(s) {
+    eagerCopyCtorHelper(s, rhs, rhslnth);
+}
+
+// private ctor (not in header): use specified heap (ignore ambient) and copy chars in
+void ?{}( string_res &s, VbyteHeap & heap, const char* rhs, size_t rhslnth ) with(s) {
+    (Handle){ heap };
+    Handle.s = VbyteAlloc(*Handle.ulink, rhslnth);
+    Handle.lnth = rhslnth;
+    (s.shareEditSet_owns_ulink){ false };
+    for ( int i = 0; i < rhslnth; i += 1 ) {            // copy characters
+        Handle.s[i] = rhs[i];
+    } // for
+    s.shareEditSet_prev = &s;
+    s.shareEditSet_next = &s;
 }
 
@@ -223 +274 @@
 void ?{}(string_res &s, const string_res & s2, StrResInitMode mode, size_t start, size_t end ) {
 
-    (s.Handle){ HeapArea };
-    s.Handle.s = s2.Handle.s + start;
-    s.Handle.lnth = end - start;
-    MoveThisAfter(s.Handle, s2.Handle );                        // insert this handle after rhs handle
-    // ^ bug?  skip others at early point in string
-    
-    if (mode == COPY_VALUE) {
-        // make s alone in its shareEditSet
-        s.shareEditSet_prev = &s;
-        s.shareEditSet_next = &s;
+    verify( start <= end && end <= s2.Handle.lnth );
+
+    if (s2.Handle.ulink != ambient_string_sharectx->activeHeap && mode == COPY_VALUE) {
+        // crossing heaps (including private): copy eagerly
+        eagerCopyCtorHelper(s, s2.Handle.s + start, end - start);
+        verify(s.shareEditSet_prev == &s);
+        verify(s.shareEditSet_next == &s);
     } else {
-        assert( mode == SHARE_EDITS );
-
-        // s2 is logically const but not implementation const
-        string_res & s2mod = (string_res &) s2;
-
-        // insert s after s2 on shareEditSet
-        s.shareEditSet_next = s2mod.shareEditSet_next;
-        s.shareEditSet_prev = &s2mod;
-        s.shareEditSet_next->shareEditSet_prev = &s;
-        s.shareEditSet_prev->shareEditSet_next = &s;
-    }
-}
-
-void assign(string_res &this, const char* buffer, size_t bsize) {
-
-    // traverse the incumbent share-edit set (SES) to recover the range of a base string to which `this` belongs
-    string_res * shareEditSetStartPeer = & this;
-    string_res * shareEditSetEndPeer = & this;
-    for (string_res * editPeer = this.shareEditSet_next; editPeer != &this; editPeer = editPeer->shareEditSet_next) {
-        if ( editPeer->Handle.s < shareEditSetStartPeer->Handle.s ) {
-            shareEditSetStartPeer = editPeer;
+        (s.Handle){};
+        s.Handle.s = s2.Handle.s + start;
+        s.Handle.lnth = end - start;
+        s.Handle.ulink = s2.Handle.ulink;
+
+        AddThisAfter(s.Handle, s2.Handle );                     // insert this handle after rhs handle
+        // ^ bug?  skip others at early point in string
+
+        if (mode == COPY_VALUE) {
+            verify(s2.Handle.ulink == ambient_string_sharectx->activeHeap);
+            // requested logical copy in same heap: defer copy until write
+
+            (s.shareEditSet_owns_ulink){ false };
+
+            // make s alone in its shareEditSet
+            s.shareEditSet_prev = &s;
+            s.shareEditSet_next = &s;
+        } else {
+            verify( mode == SHARE_EDITS );
+            // sharing edits with source forces same heap as source (ignore context)
+
+            (s.shareEditSet_owns_ulink){ s2.shareEditSet_owns_ulink };
+
+            // s2 is logically const but not implementation const
+            string_res & s2mod = (string_res &) s2;
+
+            // insert s after s2 on shareEditSet
+            s.shareEditSet_next = s2mod.shareEditSet_next;
+            s.shareEditSet_prev = &s2mod;
+            s.shareEditSet_next->shareEditSet_prev = &s;
+            s.shareEditSet_prev->shareEditSet_next = &s;
         }
-        if ( shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth < editPeer->Handle.s + editPeer->Handle.lnth) {
-            shareEditSetEndPeer = editPeer;
-        }
-    }
-
-    // full string is from start of shareEditSetStartPeer thru end of shareEditSetEndPeer
-    // `this` occurs in the middle of it, to be replaced
-    // build up the new text in `pasting`
-
-    string_res pasting = {
-        shareEditSetStartPeer->Handle.s,                   // start of SES
-        this.Handle.s - shareEditSetStartPeer->Handle.s }; // length of SES, before this
-    append( pasting,
-        buffer,                                            // start of replacement for this
-        bsize );                                           // length of replacement for this
-    append( pasting,
-        this.Handle.s + this.Handle.lnth,                  // start of SES after this
-        shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth -
-        (this.Handle.s + this.Handle.lnth) );              // length of SES, after this
-
-    // The above string building can trigger compaction.
-    // The reference points (that are arguments of the string building) may move during that building.
-    // From this point on, they are stable.
-    // So now, capture their values for use in the overlap cases, below.
-    // Do not factor these definitions with the arguments used above.
+    }
+}
+
+static void assignEditSet(string_res & this, string_res * shareEditSetStartPeer, string_res * shareEditSetEndPeer,
+    char * resultSesStart,
+    size_t resultSesLnth,
+    HandleNode * resultPadPosition, size_t bsize ) {
 
     char * beforeBegin = shareEditSetStartPeer->Handle.s;
@@ -290 +330 @@
     size_t oldLnth = this.Handle.lnth;
 
-    this.Handle.s = pasting.Handle.s + beforeLen;
+    this.Handle.s = resultSesStart + beforeLen;
     this.Handle.lnth = bsize;
-    MoveThisAfter( this.Handle, pasting.Handle );
+    if (resultPadPosition)
+        MoveThisAfter( this.Handle, *resultPadPosition );
 
     // adjust all substring string and handle locations, and check if any substring strings are outside the new base string
-    char *limit = pasting.Handle.s + pasting.Handle.lnth;
+    char *limit = resultSesStart + resultSesLnth;
     for (string_res * p = this.shareEditSet_next; p != &this; p = p->shareEditSet_next) {
-        assert (p->Handle.s >= beforeBegin);
+        verify (p->Handle.s >= beforeBegin);
         if ( p->Handle.s >= afterBegin ) {
-            assert ( p->Handle.s <= afterBegin + afterLen );
-            assert ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen );
+            verify ( p->Handle.s <= afterBegin + afterLen );
+            verify ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen );
             // p starts after the edit
             // take start and end as end-anchored
@@ -318 +359 @@
             } else {
                 // p ends after the edit
-                assert ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen );
+                verify ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen );
                 // take end as end-anchored
                 // stretch-shrink p according to the edit
@@ -326 +367 @@
             // take start as start-anchored
             size_t startOffsetFromStart = p->Handle.s - beforeBegin;
-            p->Handle.s = pasting.Handle.s + startOffsetFromStart;
+            p->Handle.s = resultSesStart + startOffsetFromStart;
         } else {
-            assert ( p->Handle.s < afterBegin );
+            verify ( p->Handle.s < afterBegin );
             // p starts during the edit
-            assert( p->Handle.s + p->Handle.lnth >= beforeBegin + beforeLen );
+            verify( p->Handle.s + p->Handle.lnth >= beforeBegin + beforeLen );
             if ( p->Handle.s + p->Handle.lnth < afterBegin ) {
                 // p ends during the edit; p does not include the last character replaced
@@ -344 +385 @@
             }
         }
-        MoveThisAfter( p->Handle, pasting.Handle );     // move substring handle to maintain sorted order by string position
-    }
-}
-
-void ?=?(string_res &s, const char* other) {
-    assign(s, other, strlen(other));
-}
-
-void ?=?(string_res &s, char other) {
-    assign(s, &other, 1);
+        if (resultPadPosition)
+            MoveThisAfter( p->Handle, *resultPadPosition );     // move substring handle to maintain sorted order by string position
+    }
+}
+
+static string_res & assign_(string_res &this, const char* buffer, size_t bsize, const string_res & valSrc) {
+
+    // traverse the incumbent share-edit set (SES) to recover the range of a base string to which `this` belongs
+    string_res * shareEditSetStartPeer = & this;
+    string_res * shareEditSetEndPeer = & this;
+    for (string_res * editPeer = this.shareEditSet_next; editPeer != &this; editPeer = editPeer->shareEditSet_next) {
+        if ( editPeer->Handle.s < shareEditSetStartPeer->Handle.s ) {
+            shareEditSetStartPeer = editPeer;
+        }
+        if ( shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth < editPeer->Handle.s + editPeer->Handle.lnth) {
+            shareEditSetEndPeer = editPeer;
+        }
+    }
+
+    verify( shareEditSetEndPeer->Handle.s >= shareEditSetStartPeer->Handle.s );
+    size_t origEditSetLength = shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - shareEditSetStartPeer->Handle.s;
+    verify( origEditSetLength >= this.Handle.lnth );
+
+    if ( this.shareEditSet_owns_ulink ) {                 // assigning to private context
+        // ok to overwrite old value within LHS
+        char * prefixStartOrig = shareEditSetStartPeer->Handle.s;
+        int prefixLen = this.Handle.s - prefixStartOrig;
+        char * suffixStartOrig = this.Handle.s + this.Handle.lnth;
+        int suffixLen = shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - suffixStartOrig;
+
+        int delta = bsize - this.Handle.lnth;
+        if ( char * oldBytes = VbyteTryAdjustLast( *this.Handle.ulink, delta ) ) {
+            // growing: copy from old to new
+            char * dest = VbyteAlloc( *this.Handle.ulink, origEditSetLength + delta );
+            char *destCursor = dest;  memcpy(destCursor, prefixStartOrig, prefixLen);
+            destCursor += prefixLen;  memcpy(destCursor, buffer         , bsize    );
+            destCursor += bsize;      memcpy(destCursor, suffixStartOrig, suffixLen);
+            assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer, 
+                dest,
+                origEditSetLength + delta,
+                0p, bsize);
+            free( oldBytes );
+        } else {
+            // room is already allocated in-place: bubble suffix and overwite middle
+            memmove( suffixStartOrig + delta, suffixStartOrig, suffixLen );
+            memcpy( this.Handle.s, buffer, bsize );
+
+            assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer, 
+                shareEditSetStartPeer->Handle.s,
+                origEditSetLength + delta,
+                0p, bsize);
+        }
+
+    } else if (                                           // assigning to shared context
+        this.Handle.lnth == origEditSetLength &&          // overwriting entire run of SES
+        & valSrc &&                                       // sourcing from a managed string
+        valSrc.Handle.ulink == this.Handle.ulink  ) {     // sourcing from same heap
+
+        // SES's result will only use characters from the source string => reuse source
+        assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer, 
+            valSrc.Handle.s,
+            valSrc.Handle.lnth,
+            &((string_res&)valSrc).Handle, bsize);
+        
+    } else {
+        // overwriting a proper substring of some string: mash characters from old and new together (copy on write)
+        // OR we are importing characters: need to copy eagerly (can't refer to source)
+
+        // full string is from start of shareEditSetStartPeer thru end of shareEditSetEndPeer
+        // `this` occurs in the middle of it, to be replaced
+        // build up the new text in `pasting`
+
+        string_res pasting = {
+            * this.Handle.ulink,                               // maintain same heap, regardless of context
+            shareEditSetStartPeer->Handle.s,                   // start of SES
+            this.Handle.s - shareEditSetStartPeer->Handle.s }; // length of SES, before this
+        append( pasting,
+            buffer,                                            // start of replacement for this
+            bsize );                                           // length of replacement for this
+        append( pasting,
+            this.Handle.s + this.Handle.lnth,                  // start of SES after this
+            shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth -
+            (this.Handle.s + this.Handle.lnth) );              // length of SES, after this
+
+        // The above string building can trigger compaction.
+        // The reference points (that are arguments of the string building) may move during that building.
+        // From this point on, they are stable.
+
+        assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer, 
+            pasting.Handle.s,
+            pasting.Handle.lnth,
+            &pasting.Handle, bsize);
+    }
+
+    return this;
+}
+
+string_res & assign(string_res &this, const char* buffer, size_t bsize) {
+    return assign_(this, buffer, bsize, *0p);
+}
+
+string_res & ?=?(string_res &s, char other) {
+    return assign(s, &other, 1);
 }
 
 // Copy assignment operator
-void ?=?(string_res & this, const string_res & rhs) with( this ) {
-    assign(this, rhs.Handle.s, rhs.Handle.lnth);
-}
-
-void ?=?(string_res & this, string_res & rhs) with( this ) {
+string_res & ?=?(string_res & this, const string_res & rhs) with( this ) {
+    return assign_(this, rhs.Handle.s, rhs.Handle.lnth, rhs);
+}
+
+string_res & ?=?(string_res & this, string_res & rhs) with( this ) {
     const string_res & rhs2 = rhs;
-    this = rhs2;
+    return this = rhs2;
 }
 
@@ -374 +508 @@
     s.shareEditSet_prev->shareEditSet_next = s.shareEditSet_next;
     s.shareEditSet_next->shareEditSet_prev = s.shareEditSet_prev;
-    s.shareEditSet_next = &s;
-    s.shareEditSet_prev = &s;
+    // s.shareEditSet_next = &s;
+    // s.shareEditSet_prev = &s;
+
+    if (shareEditSet_owns_ulink && s.shareEditSet_next == &s) { // last one out
+        delete( s.Handle.ulink );
+    }
 }
 
@@ -387 +525 @@
 }
 
+void assignAt(const string_res &s, size_t index, char val) {
+    string_res editZone = { s, SHARE_EDITS, index, index+1 };
+    assign(editZone, &val, 1);
+}
+
 
 ///////////////////////////////////////////////////////////////////
@@ -392 +535 @@
 
 void append(string_res &str1, const char * buffer, size_t bsize) {
-    size_t clnth = size(str1) + bsize;
-    if ( str1.Handle.s + size(str1) == buffer ) { // already juxtapose ?
+    size_t clnth = str1.Handle.lnth + bsize;
+    if ( str1.Handle.s + str1.Handle.lnth == buffer ) { // already juxtapose ?
         // no-op
     } else {                                            // must copy some text
-        if ( str1.Handle.s + size(str1) == VbyteAlloc(HeapArea, 0) ) { // str1 at end of string area ?
-            VbyteAlloc(HeapArea, bsize); // create room for 2nd part at the end of string area
+        if ( str1.Handle.s + str1.Handle.lnth == VbyteAlloc(*str1.Handle.ulink, 0) ) { // str1 at end of string area ?
+            VbyteAlloc( *str1.Handle.ulink, bsize ); // create room for 2nd part at the end of string area
         } else {                                        // copy the two parts
-            char * str1oldBuf = str1.Handle.s;
-            str1.Handle.s = VbyteAlloc( HeapArea, clnth );
-            ByteCopy( HeapArea, str1.Handle.s, 0, str1.Handle.lnth, str1oldBuf, 0, str1.Handle.lnth);
+            char * str1newBuf = VbyteAlloc( *str1.Handle.ulink, clnth );
+            char * str1oldBuf = str1.Handle.s;  // must read after VbyteAlloc call in case it gs's
+            str1.Handle.s = str1newBuf;
+            memcpy( str1.Handle.s, str1oldBuf,  str1.Handle.lnth );
         } // if
-        ByteCopy( HeapArea, str1.Handle.s, str1.Handle.lnth, bsize, (char*)buffer, 0, (int)bsize);
-        //       VbyteHeap & this, char *Dst, int DstStart, int DstLnth, char *Src, int SrcStart, int SrcLnth 
+        memcpy( str1.Handle.s + str1.Handle.lnth, buffer, bsize );
     } // if
     str1.Handle.lnth = clnth;
@@ -417 +560 @@
 }
 
-void ?+=?(string_res &s, const char* other) {
-    append( s, other, strlen(other) );
-}
 
 
@@ -429 +569 @@
 
 bool ?==?(const string_res &s1, const string_res &s2) {
-    return ByteCmp( HeapArea, s1.Handle.s, 0, s1.Handle.lnth, s2.Handle.s, 0, s2.Handle.lnth) == 0;
+    return ByteCmp( s1.Handle.s, 0, s1.Handle.lnth, s2.Handle.s, 0, s2.Handle.lnth) == 0;
 }
 
@@ -596 +736 @@
 // Add a new HandleNode node n after the current HandleNode node.
 
-static inline void AddThisAfter( HandleNode & this, HandleNode & n ) with(this) {
+static void AddThisAfter( HandleNode & this, HandleNode & n ) with(this) {
 #ifdef VbyteDebug
     serr | "enter:AddThisAfter, this:" | &this | " n:" | &n;
 #endif // VbyteDebug
+    verify( n.ulink != 0p );
+    verify( this.ulink == n.ulink );
     flink = n.flink;
     blink = &n;
@@ -624 +766 @@
 // Delete the current HandleNode node.
 
-static inline void DeleteNode( HandleNode & this ) with(this) {
+static void DeleteNode( HandleNode & this ) with(this) {
 #ifdef VbyteDebug
     serr | "enter:DeleteNode, this:" | &this;
@@ -638 +780 @@
 
 // Allocates specified storage for a string from byte-string area. If not enough space remains to perform the
-// allocation, the garbage collection routine is called and a second attempt is made to allocate the space. If the
-// second attempt fails, a further attempt is made to create a new, larger byte-string area.
-
-static inline char * VbyteAlloc( VbyteHeap & this, int size ) with(this) {
+// allocation, the garbage collection routine is called.
+
+static char * VbyteAlloc( VbyteHeap & this, int size ) with(this) {
 #ifdef VbyteDebug
     serr | "enter:VbyteAlloc, size:" | size;
@@ -650 +791 @@
     NoBytes = ( uintptr_t )EndVbyte + size;
     if ( NoBytes > ( uintptr_t )ExtVbyte ) {            // enough room for new byte-string ?
-                garbage( this );                                        // firer up the garbage collector
-                NoBytes = ( uintptr_t )EndVbyte + size;         // try again
-                if ( NoBytes > ( uintptr_t )ExtVbyte ) {        // enough room for new byte-string ?
-assert( 0 && "need to implement actual growth" );
-                        // extend( size );                              // extend the byte-string area
-                } // if
+                garbage( this, size );                                  // firer up the garbage collector
+                verify( (( uintptr_t )EndVbyte + size) <= ( uintptr_t )ExtVbyte  && "garbage run did not free up required space" );
     } // if
     r = EndVbyte;
@@ -666 +803 @@
 
 
+// Adjusts the last allocation in this heap by delta bytes, or resets this heap to be able to offer
+// new allocations of its original size + delta bytes. Positive delta means bigger;
+// negative means smaller.  A null return indicates that the original heap location has room for
+// the requested growth.  A non-null return indicates that copying to a new location is required
+// but has not been done; the returned value is the old heap storage location; `this` heap is
+// modified to reference the new location.  In the copy-requred case, the caller should use
+// VbyteAlloc to claim the new space, while doing optimal copying from old to new, then free old.
+
+static char * VbyteTryAdjustLast( VbyteHeap & this, int delta ) with(this) {
+
+    if ( ( uintptr_t )EndVbyte + delta <= ( uintptr_t )ExtVbyte ) {
+        // room available
+        EndVbyte += delta;
+        return 0p;
+    }
+
+    char *oldBytes = StartVbyte;
+
+    NoOfExtensions += 1;
+    CurrSize *= 2;
+    StartVbyte = EndVbyte = alloc(CurrSize);
+    ExtVbyte = StartVbyte + CurrSize;
+
+    return oldBytes;
+}
+
+
 // Move an existing HandleNode node h somewhere after the current HandleNode node so that it is in ascending order by
 // the address in the byte string area.
 
-static inline void MoveThisAfter( HandleNode & this, const HandleNode  & h ) with(this) {
+static void MoveThisAfter( HandleNode & this, const HandleNode  & h ) with(this) {
 #ifdef VbyteDebug
     serr | "enter:MoveThisAfter, this:" | & this | " h:" | & h;
 #endif // VbyteDebug
+    verify( h.ulink != 0p );
+    verify( this.ulink == h.ulink );
     if ( s < h.s ) {                                    // check argument values
                 // serr | "VbyteSM: Error - Cannot move byte string starting at:" | s | " after byte string starting at:"
                 //      | ( h->s ) | " and keep handles in ascending order";
                 // exit(-1 );
-                assert( 0 && "VbyteSM: Error - Cannot move byte strings as requested and keep handles in ascending order");
+                verify( 0 && "VbyteSM: Error - Cannot move byte strings as requested and keep handles in ascending order");
     } // if
 
@@ -709 +875 @@
 //######################### VbyteHeap #########################
 
-// Move characters from one location in the byte-string area to another. The routine handles the following situations:
-//
-// if the |Src| > |Dst| => truncate
-// if the |Dst| > |Src| => pad Dst with blanks
-
-void ByteCopy( VbyteHeap & this, char *Dst, int DstStart, int DstLnth, char *Src, int SrcStart, int SrcLnth ) {
-    for ( int i = 0; i < DstLnth; i += 1 ) {
-      if ( i == SrcLnth ) {                             // |Dst| > |Src|
-            for ( ; i < DstLnth; i += 1 ) {             // pad Dst with blanks
-                Dst[DstStart + i] = ' ';
-            } // for
-            break;
-        } // exit
-        Dst[DstStart + i] = Src[SrcStart + i];
-    } // for
-} // ByteCopy
-
 // Compare two byte strings in the byte-string area. The routine returns the following values:
 //
@@ -732 +881 @@
 // -1 => Src1-byte-string < Src2-byte-string
 
-int ByteCmp( VbyteHeap & this, char *Src1, int Src1Start, int Src1Lnth, char *Src2, int Src2Start, int Src2Lnth )  with(this) {
+int ByteCmp( char *Src1, int Src1Start, int Src1Lnth, char *Src2, int Src2Start, int Src2Lnth )  {
 #ifdef VbyteDebug
     serr | "enter:ByteCmp, Src1Start:" | Src1Start | " Src1Lnth:" | Src1Lnth | " Src2Start:" | Src2Start | " Src2Lnth:" | Src2Lnth;
@@ -789 +938 @@
     h = Header.flink;                                   // ignore header node
     for (;;) {
-                ByteCopy( this, EndVbyte, 0, h->lnth, h->s, 0, h->lnth );
+                memmove( EndVbyte, h->s, h->lnth );
                 obase = h->s;
                 h->s = EndVbyte;
@@ -813 +962 @@
 // the heap.  The heap is then compacted in the existing heap or into the newly allocated heap.
 
-void garbage(VbyteHeap & this ) with(this) {
+void garbage(VbyteHeap & this, int minreq ) with(this) {
 #ifdef VbyteDebug
     serr | "enter:garbage";
@@ -831 +980 @@
     int AmountUsed, AmountFree;
 
+//    assert( false );
+
     AmountUsed = 0;
     for ( HandleNode *i = Header.flink; i != &Header; i = i->flink ) { // calculate amount of byte area used
@@ -837 +988 @@
     AmountFree = ( uintptr_t )ExtVbyte - ( uintptr_t )StartVbyte - AmountUsed;
     
-    if ( AmountFree < ( int )( CurrSize * 0.1 )) {      // free space less than 10% ?
-
-assert( 0 && "need to implement actual growth" );
-//              extend( CurrSize );                             // extend the heap
+    if ( ( double ) AmountFree < ( CurrSize * 0.1 ) || AmountFree < minreq ) {  // free space less than 10%  or not enough to serve cur request
+
+                extend( this, max( CurrSize, minreq ) );                                // extend the heap
 
                         //  Peter says, "This needs work before it should be used."
@@ -867 +1017 @@
 #undef VbyteDebug
 
-//WIP
-#if 0
 
 
@@ -874 +1022 @@
 // area is deleted.
 
-void VbyteHeap::extend( int size ) {
+void extend( VbyteHeap & this, int size ) with (this) {
 #ifdef VbyteDebug
     serr | "enter:extend, size:" | size;
@@ -884 +1032 @@
     
     CurrSize += size > InitSize ? size : InitSize;      // minimum extension, initial size
-    StartVbyte = EndVbyte = new char[CurrSize];
+    StartVbyte = EndVbyte = alloc(CurrSize);
     ExtVbyte = (void *)( StartVbyte + CurrSize );
-    compaction();                                       // copy from old heap to new & adjust pointers to new heap
-    delete OldStartVbyte;                               // release old heap
+    compaction(this);                                   // copy from old heap to new & adjust pointers to new heap
+    free( OldStartVbyte );                              // release old heap
 #ifdef VbyteDebug
     serr | "exit:extend, CurrSize:" | CurrSize;
@@ -893 +1041 @@
 } // extend
 
+//WIP
+#if 0
 
 // Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string

libcfa/src/containers/string_res.hfa

@@ -17 +17 @@
 
 #include <fstream.hfa>
+#include <string.h>    // e.g. strlen
 
     
@@ -27 +28 @@
     HandleNode *flink;                                  // forward link
     HandleNode *blink;                                  // backward link
+    VbyteHeap *ulink;                   // upward link
 
     char *s;                                            // pointer to byte string
@@ -32 +34 @@
 }; // HandleNode
 
-void ?{}( HandleNode & );                       // constructor for header node
-
-void ?{}( HandleNode &, VbyteHeap & );          // constructor for nodes in the handle list
-void ^?{}( HandleNode & );                      // destructor for handle nodes
-
-extern VbyteHeap * DEBUG_string_heap;
+VbyteHeap * DEBUG_string_heap();
+size_t DEBUG_string_bytes_in_heap( VbyteHeap * heap );
 size_t DEBUG_string_bytes_avail_until_gc( VbyteHeap * heap );
 const char * DEBUG_string_heap_start( VbyteHeap * heap );
@@ -47 +45 @@
 struct string_res {
     HandleNode Handle; // chars, start, end, global neighbours
+    bool shareEditSet_owns_ulink;
     string_res * shareEditSet_prev;
     string_res * shareEditSet_next;
@@ -74 +73 @@
 // Constructors, Assignment Operators, Destructor
 void ?{}(string_res &s); // empty string
-void ?{}(string_res &s, const char* initial); // copy from string literal (NULL-terminated)
 void ?{}(string_res &s, const char* buffer, size_t bsize); // copy specific length from buffer
+static inline void ?{}(string_res &s, const char* rhs) { // copy from string literal (NULL-terminated)
+    (s){ rhs, strlen(rhs) };
+}
 
 void ?{}(string_res &s, const string_res & s2) = void;
@@ -86 +87 @@
 }
 
-void assign(string_res &s, const char* buffer, size_t bsize); // copy specific length from buffer
-void ?=?(string_res &s, const char* other); // copy from string literal (NULL-terminated)
-void ?=?(string_res &s, const string_res &other);
-void ?=?(string_res &s, string_res &other);
-void ?=?(string_res &s, char other);
+string_res & assign(string_res &s, const char* buffer, size_t bsize); // copy specific length from buffer
+static inline string_res & ?=?(string_res &s, const char* other) {  // copy from string literal (NULL-terminated)
+    return assign(s, other, strlen(other));
+}
+string_res & ?=?(string_res &s, const string_res &other);
+string_res & ?=?(string_res &s, string_res &other);
+string_res & ?=?(string_res &s, char other);
 
 void ^?{}(string_res &s);
@@ -99 +102 @@
 
 // Concatenation
+void append(string_res &s, const char* buffer, size_t bsize);
 void ?+=?(string_res &s, char other); // append a character
 void ?+=?(string_res &s, const string_res &s2); // append-concatenate to first string
-void ?+=?(string_res &s, const char* other);
-void append(string_res &s, const char* buffer, size_t bsize);
+static inline void ?+=?(string_res &s, const char* other) {
+    append( s, other, strlen(other) );
+}
 
 // Character access
+void assignAt(const string_res &s, size_t index, char val);
 char ?[?](const string_res &s, size_t index); // Mike changed to ret by val from Sunjay's ref, to match Peter's
 //char codePointAt(const string_res &s, size_t index); // revisit under Unicode

tests/collections/.expect/string-api-coverage.txt

@@ -1 +1 @@
 hello hello hello
+
+hello
 true false
 true false

tests/collections/.expect/string-gc.txt

@@ -38 +38 @@
 x from 5 to 15
 y from 5 to 15
+======================== fillNoCompact
+about to expand, a = aaa
+expanded, a = aaa
+about to expand, a = aaa
+expanded, a = aaa
+about to expand, a = aaa
+expanded, a = aaa
+about to expand, a = aaa
+expanded, a = aaa
+about to expand, a = aaa
+expanded, a = aaa

tests/collections/string-api-coverage.cfa

@@ -1 +1 @@
 #include <containers/string.hfa>
+#include <string_sharectx.hfa>
 
 void assertWellFormedHandleList( int maxLen ) { // with(HeapArea)
@@ -25 +26 @@
 
 int main () {
+
+    #ifdef STRING_SHARING_OFF
+    string_sharectx c = { NO_SHARING };
+    #endif
+
     string s = "hello";
     string s2 = "hello";
@@ -31 +37 @@
 
     // IO operator, x2
-    sout | s | s | s;
+    sout | s | s | s;  // hello hello hello
+
+    // empty ctor then assign
+    string sxx;
+    sout | sxx;  // (blank line)
+    sxx = s;
+    sout | sxx;  // hello
 
     // Comparisons

tests/collections/string-gc.cfa

@@ -2 +2 @@
 
 size_t bytesRemaining() {
-    return DEBUG_string_bytes_avail_until_gc( DEBUG_string_heap );
+    return DEBUG_string_bytes_avail_until_gc( DEBUG_string_heap() );
 }
 
 size_t heapOffsetStart( string_res & s ) {
-    const char * startByte = DEBUG_string_heap_start( DEBUG_string_heap );
+    const char * startByte = DEBUG_string_heap_start( DEBUG_string_heap() );
     assert( s.Handle.s >= startByte );
     return s.Handle.s - startByte;
@@ -120 +120 @@
 }
 
+void fillNoCompact() {
+    // show that allocating in a heap filled with mostly live strings (no collectable garbage) causes heap growth
+
+    sout | "======================== fillNoCompact";
+
+    size_t lastTimeBytesAvail = bytesRemaining();
+    assert( lastTimeBytesAvail >= 200 ); // starting this test with nontrivial room
+
+    // mostly fill the pad
+    string_res a = "aaa";  // will have to be moved
+    string_res z = "zzz";
+    for (i; 5) {
+        while ( bytesRemaining() > 10 ) {
+            z += ".";
+        }
+        sout | "about to expand, a = " | a;
+        while ( bytesRemaining() <= 10 ) {
+            z += ".";
+        }
+        sout | "expanded, a = " | a;
+
+        // each growth gives more usable space than the last
+        assert( bytesRemaining() > lastTimeBytesAvail );
+        lastTimeBytesAvail = bytesRemaining();
+    }
+}
+
 int main() {
     basicFillCompact();
     fillCompact_withSharedEdits();
+    fillNoCompact();
 }

tests/collections/string-overwrite.cfa

@@ -1 +1 @@
 #include <containers/string.hfa>
+#include <string_sharectx.hfa>
 
 /*
@@ -11 +12 @@
 WE = witness end
 
-The dest does:
+The test does:
   starts with the entire string being, initially, the alphabet; prints this entire alphabet
   sets up modifier and witness as ranges within it, and prints a visualization of those ranges
@@ -24 +25 @@
 This API's convention has Start positions being inclusive and end positions being exclusive.
 
+                                v Case number in output
 With 1 equivalence class:
 MS = ME = WS = WE               1
@@ -118 +120 @@
     struct { int ms; int me; int ws; int we; char *replaceWith; char *label; } cases[] = {
         { 12, 14, 10, 20, "xxxxx", "warmup" },
-//        { 12, 14, 12, 14, "xxxxx", ""       },  // the bug that got me into this test (should be a dup with case 6)
         { 10, 10, 10, 10, "=====", "1"      },
         { 10, 10, 10, 10, "=="   , ""       },
@@ -223 +224 @@
         { 12, 14, 10, 16, "="    , ""       },
         { 12, 14, 10, 16, ""     , ""       },
-/*
-        { , , , , "=====", "NN"     },
-        {  "=="   , ""       },
-        {  "="    , ""       },
-        {  ""     , ""       },
-*/
     };
     for ( i; sizeof(cases)/sizeof(cases[0]) ) {
@@ -238 +233 @@
 
 
-// void f( string & s, string & toEdit ) {
-
-//     sout | s | "|" | toEdit | "|";
-
-//     s(14, 16) = "-";
-//     sout | s | "|" | toEdit | "|";
-// }
-
 int main() {
+
+    #ifdef STRING_SHARING_OFF
+    string_sharectx c = { NO_SHARING };
+    #endif
+
+
     //          0         1         2
     //          01234567890123456789012345