Index: libcfa/src/Makefile.am =================================================================== --- libcfa/src/Makefile.am (revision 6a33e40a808bb9559b1c8d240cf5414593d7b062) +++ libcfa/src/Makefile.am (revision 12c1eeff7e4358f66eb036d8fd54ae6257c2472c) @@ -63,4 +63,5 @@ containers/queueLockFree.hfa \ containers/stackLockFree.hfa \ + containers/string_sharectx.hfa \ containers/vector2.hfa \ vec/vec.hfa \ Index: libcfa/src/containers/string.cfa =================================================================== --- libcfa/src/containers/string.cfa (revision 6a33e40a808bb9559b1c8d240cf5414593d7b062) +++ libcfa/src/containers/string.cfa (revision 12c1eeff7e4358f66eb036d8fd54ae6257c2472c) @@ -92,5 +92,5 @@ } -string ?=?(string & this, string other) { +string & ?=?(string & this, string & other) { //// <---- straw man change (*this.inner) = (*other.inner); return this; Index: libcfa/src/containers/string.hfa =================================================================== --- libcfa/src/containers/string.hfa (revision 6a33e40a808bb9559b1c8d240cf5414593d7b062) +++ libcfa/src/containers/string.hfa (revision 12c1eeff7e4358f66eb036d8fd54ae6257c2472c) @@ -41,6 +41,6 @@ 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); Index: libcfa/src/containers/string_res.cfa =================================================================== --- libcfa/src/containers/string_res.cfa (revision 6a33e40a808bb9559b1c8d240cf5414593d7b062) +++ libcfa/src/containers/string_res.cfa (revision 12c1eeff7e4358f66eb036d8fd54ae6257c2472c) @@ -15,22 +15,10 @@ #include "string_res.hfa" +#include "string_sharectx.hfa" + #include // e.g. malloc -#include // e.g. strlen +#include //######################### VbyteHeap "header" ######################### - - - - - - - - -// DON'T COMMIT: -// #define VbyteDebug - - - - #ifdef VbyteDebug @@ -54,24 +42,24 @@ -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,4 +70,5 @@ ExtVbyte = (void *)( StartVbyte + CurrSize ); Header.flink = Header.blink = &Header; + Header.ulink = & this; #ifdef VbyteDebug HeaderPtr = &Header; @@ -91,5 +80,5 @@ // 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,5 +91,5 @@ // creator. -void ?{}( HandleNode & this ) with(this) { +static void ?{}( HandleNode & this ) with(this) { #ifdef VbyteDebug serr | "enter:HandleNode::HandleNode, this:" | &this; @@ -117,5 +106,5 @@ // 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,4 +112,5 @@ s = 0; lnth = 0; + ulink = &vh; AddThisAfter( this, *vh.Header.blink ); #ifdef VbyteDebug @@ -133,5 +123,5 @@ // 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,10 +139,38 @@ } // ~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,8 +178,11 @@ } +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,24 +208,41 @@ // 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,7 +253,20 @@ } -// 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,62 +274,51 @@ 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,15 +330,16 @@ 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,5 +359,5 @@ } 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,9 +367,9 @@ // 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,24 +385,117 @@ } } - 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,6 +508,10 @@ 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,4 +525,9 @@ } +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,17 +535,17 @@ 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,7 +560,4 @@ } -void ?+=?(string_res &s, const char* other) { - append( s, other, strlen(other) ); -} @@ -429,5 +569,5 @@ 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,8 +736,10 @@ // 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,5 +766,5 @@ // 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,8 +780,7 @@ // 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,10 +791,6 @@ 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,16 +803,45 @@ +// 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,21 +875,4 @@ //######################### 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,5 +881,5 @@ // -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,5 +938,5 @@ 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,5 +962,5 @@ // 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,4 +980,6 @@ int AmountUsed, AmountFree; +// assert( false ); + AmountUsed = 0; for ( HandleNode *i = Header.flink; i != &Header; i = i->flink ) { // calculate amount of byte area used @@ -837,8 +988,7 @@ 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,6 +1017,4 @@ #undef VbyteDebug -//WIP -#if 0 @@ -874,5 +1022,5 @@ // area is deleted. -void VbyteHeap::extend( int size ) { +void extend( VbyteHeap & this, int size ) with (this) { #ifdef VbyteDebug serr | "enter:extend, size:" | size; @@ -884,8 +1032,8 @@ 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,4 +1041,6 @@ } // 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 Index: libcfa/src/containers/string_res.hfa =================================================================== --- libcfa/src/containers/string_res.hfa (revision 6a33e40a808bb9559b1c8d240cf5414593d7b062) +++ libcfa/src/containers/string_res.hfa (revision 12c1eeff7e4358f66eb036d8fd54ae6257c2472c) @@ -17,4 +17,5 @@ #include +#include // e.g. strlen @@ -27,4 +28,5 @@ HandleNode *flink; // forward link HandleNode *blink; // backward link + VbyteHeap *ulink; // upward link char *s; // pointer to byte string @@ -32,10 +34,6 @@ }; // 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,4 +45,5 @@ struct string_res { HandleNode Handle; // chars, start, end, global neighbours + bool shareEditSet_owns_ulink; string_res * shareEditSet_prev; string_res * shareEditSet_next; @@ -74,6 +73,8 @@ // 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,9 +87,11 @@ } -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,10 +102,13 @@ // 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 Index: libcfa/src/containers/string_sharectx.hfa =================================================================== --- libcfa/src/containers/string_sharectx.hfa (revision 12c1eeff7e4358f66eb036d8fd54ae6257c2472c) +++ libcfa/src/containers/string_sharectx.hfa (revision 12c1eeff7e4358f66eb036d8fd54ae6257c2472c) @@ -0,0 +1,58 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// string_sharectx -- utility for controlling string sharing / isolation +// +// Author : Michael L. Brooks +// Created On : Fri Sep 03 11:00:00 2021 +// Last Modified By : Michael L. Brooks +// Last Modified On : Fri Sep 03 11:00:00 2021 +// Update Count : 1 +// + +#pragma once + +//######################### String Sharing Context ######################### + +struct VbyteHeap; + +// A string_sharectx +// +// Usage: +// void bar() { +// c(); +// string_sharectx c = {NEW_SHARING}; +// d(); +// } +// void foo() { +// a(); +// string_sharectx c = {NO_SHARING}; +// b(); +// bar(); +// e(); +// } +// int main() { +// foo(); +// } +// +// a, d: share string character ranges within themselves, not with each other +// b, c, e: never share anything +// +struct string_sharectx { + // private + VbyteHeap * activeHeap; + string_sharectx * older; +}; + +enum StringSharectx_Mode { NEW_SHARING, NO_SHARING }; + +void ?{}( string_sharectx &, StringSharectx_Mode ); +void ^?{}( string_sharectx & ); + +void ?{}( string_sharectx & ) = void; +void ?{}( string_sharectx &, string_sharectx ) = void; +void ?=?( string_sharectx &, string_sharectx ) = void; +