source: libcfa/src/containers/string_res.cfa@ 9a9ca36

//
// 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_res -- variable-length, mutable run of text, with resource semantics
//
// 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
//

#include "string_res.hfa"
#include "string_sharectx.hfa"
#include "stdlib.hfa"

// Workaround for observed performance penalty from calling CFA's alloc.
// Workaround is:  EndVbyte = TEMP_ALLOC(char, CurrSize)
// Should be:      EndVbyte = alloc(CurrSize)
#define TEMP_ALLOC(T, n) (( T* ) malloc( n * sizeof( T ) ))

#include <assert.h>

//######################### VbyteHeap "header" #########################

#ifdef VbyteDebug
HandleNode *HeaderPtr;
#endif // VbyteDebug

struct VbyteHeap {

    int NoOfCompactions;                                // number of compactions of the byte area
    int NoOfExtensions;                                 // number of extensions in the size of the byte area
    int NoOfReductions;                                 // number of reductions in the size of the byte area
    
    int InitSize;                                       // initial number of bytes in the byte-string area
    int CurrSize;                                       // current number of bytes in the byte-string area
    char *StartVbyte;                                   // pointer to the `st byte of the start of the byte-string area
    char *EndVbyte;                                     // pointer to the next byte after the end of the currently used portion of byte-string area
    void *ExtVbyte;                                     // pointer to the next byte after the end of the byte-string area

    HandleNode Header;                                  // header node for handle list
}; // VbyteHeap

    
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 void ?{}( VbyteHeap & this, size_t Size ) with(this) {
#ifdef VbyteDebug
    serr | "enter:VbyteHeap::VbyteHeap, this:" | &this | " Size:" | Size;
#endif // VbyteDebug
    NoOfCompactions = NoOfExtensions = NoOfReductions = 0;
    InitSize = CurrSize = Size;
    StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize);
    ExtVbyte = (void *)( StartVbyte + CurrSize );
    Header.flink = Header.blink = &Header;
    Header.ulink = & this;
#ifdef VbyteDebug
    HeaderPtr = &Header;
    serr | "exit:VbyteHeap::VbyteHeap, this:" | &this;
#endif // VbyteDebug
} // VbyteHeap


// Release the dynamically allocated storage for the byte area.

static void ^?{}( VbyteHeap & this ) with(this) {
    free( StartVbyte );
} // ~VbyteHeap


//######################### HandleNode #########################


// Create a handle node. The handle is not linked into the handle list.  This is the responsibilitiy of the handle
// creator.

static void ?{}( HandleNode & this ) with(this) {
#ifdef VbyteDebug
    serr | "enter:HandleNode::HandleNode, this:" | &this;
#endif // VbyteDebug
    s = 0;
    lnth = 0;
#ifdef VbyteDebug
    serr | "exit:HandleNode::HandleNode, this:" | &this;
#endif // VbyteDebug
} // HandleNode

// Create a handle node. The handle is linked into the handle list at the end. This means that this handle will NOT be
// in order by string address, but this is not a problem because a string with length zero does nothing during garbage
// collection.

static void ?{}( HandleNode & this, VbyteHeap & vh ) with(this) {
#ifdef VbyteDebug
    serr | "enter:HandleNode::HandleNode, this:" | &this;
#endif // VbyteDebug
    s = 0;
    lnth = 0;
    ulink = &vh;
    AddThisAfter( this, *vh.Header.blink );
#ifdef VbyteDebug
    serr | "exit:HandleNode::HandleNode, this:" | &this;
#endif // VbyteDebug
} // HandleNode


// Delete a node from the handle list by unchaining it from the list. If the handle node was allocated dynamically, it
// is the responsibility of the creator to destroy it.

static void ^?{}( HandleNode & this ) with(this) {
#ifdef VbyteDebug
    serr | "enter:HandleNode::~HandleNode, this:" | & this;
    {
        serr | nlOff;
        serr | " lnth:" | lnth | " s:" | (void *)s | ",\"";
        for ( int i = 0; i < lnth; i += 1 ) {
            serr | s[i];
        } // for
        serr | "\" flink:" | flink | " blink:" | blink | nl;
        serr | nlOn;
    }
#endif // VbyteDebug
    DeleteNode( this );
} // ~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 * 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 ) {
    return ((char*)heap->ExtVbyte) - heap->EndVbyte;
}

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
size_t size(const string_res &s) with(s) {
    return Handle.lnth;
}

// Output operator
ofstream & ?|?(ofstream &out, const string_res &s) {
    // 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++) {
        out | s[i];
    }
    out | sep;
    // Re-apply newlines after done, for chaining version
    if (anl) nlOn(out);
    return out;
}

void ?|?(ofstream &out, const string_res &s) {
    // Store auto-newline state so it can be restored
    bool anl = getANL$(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) {
    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;
}

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;
    memmove( Handle.s, rhs, rhslnth );
    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) {
    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 };
    memmove( Handle.s, rhs, rhslnth );
    s.shareEditSet_prev = &s;
    s.shareEditSet_next = &s;
}

// General copy constructor
void ?{}(string_res &s, const string_res & s2, StrResInitMode mode, size_t start, size_t end ) {

    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 {
        (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;
        }
    }
}

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;
    size_t beforeLen = this.Handle.s - beforeBegin;

    char * afterBegin = this.Handle.s + this.Handle.lnth;
    size_t afterLen = shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - afterBegin;

    size_t oldLnth = this.Handle.lnth;

    this.Handle.s = resultSesStart + beforeLen;
    this.Handle.lnth = bsize;
    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 = resultSesStart + resultSesLnth;
    for (string_res * p = this.shareEditSet_next; p != &this; p = p->shareEditSet_next) {
        verify (p->Handle.s >= beforeBegin);
        if ( p->Handle.s >= afterBegin ) {
            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
            size_t startOffsetFromEnd = afterBegin + afterLen - p->Handle.s;
            p->Handle.s = limit - startOffsetFromEnd;
            // p->Handle.lnth unaffected
        } else if ( p->Handle.s <= beforeBegin + beforeLen ) {
            // p starts before, or at the start of, the edit
            if ( p->Handle.s + p->Handle.lnth <= beforeBegin + beforeLen ) {
                // p ends before the edit
                // take end as start-anchored too
                // p->Handle.lnth unaffected
            } else if ( p->Handle.s + p->Handle.lnth < afterBegin ) {
                // p ends during the edit; p does not include the last character replaced
                // clip end of p to end at start of edit
                p->Handle.lnth = beforeLen - ( p->Handle.s - beforeBegin );
            } else {
                // p ends after the edit
                verify ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen );
                // take end as end-anchored
                // stretch-shrink p according to the edit
                p->Handle.lnth += this.Handle.lnth;
                p->Handle.lnth -= oldLnth;
            }
            // take start as start-anchored
            size_t startOffsetFromStart = p->Handle.s - beforeBegin;
            p->Handle.s = resultSesStart + startOffsetFromStart;
        } else {
            verify ( p->Handle.s < afterBegin );
            // p starts during the edit
            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
                // set p to empty string at start of edit
                p->Handle.s = this.Handle.s;
                p->Handle.lnth = 0;
            } else {
                // p includes the end of the edit
                // clip start of p to start at end of edit
                int charsToClip = afterBegin - p->Handle.s;
                p->Handle.s = this.Handle.s + this.Handle.lnth;
                p->Handle.lnth -= charsToClip;
            }
        }
        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
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;
    return this = rhs2;
}


// Destructor
void ^?{}(string_res &s) with(s) {
    // much delegated to implied ^VbyteSM

    // sever s from its share-edit peers, if any (four no-ops when already solo)
    s.shareEditSet_prev->shareEditSet_next = s.shareEditSet_next;
    s.shareEditSet_next->shareEditSet_prev = s.shareEditSet_prev;
    // s.shareEditSet_next = &s;
    // s.shareEditSet_prev = &s;

    if (shareEditSet_owns_ulink && s.shareEditSet_next == &s) { // last one out
        delete( s.Handle.ulink );
    }
}


// Returns the character at the given index
// With unicode support, this may be different from just the byte at the given
// offset from the start of the string.
char ?[?](const string_res &s, size_t index) with(s) {
    //TODO: Check if index is valid (no exceptions yet)
    return Handle.s[index];
}

void assignAt(const string_res &s, size_t index, char val) {
    string_res editZone = { s, SHARE_EDITS, index, index+1 };
    assign(editZone, &val, 1);
}


///////////////////////////////////////////////////////////////////
// Concatenation

void append(string_res &str1, const char * buffer, size_t bsize) {
    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 + 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 * 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
        memcpy( str1.Handle.s + str1.Handle.lnth, buffer, bsize );
    } // if
    str1.Handle.lnth = clnth;
}

void ?+=?(string_res &str1, const string_res &str2) {
    append( str1, str2.Handle.s, str2.Handle.lnth );
}

void ?+=?(string_res &s, char other) {
    append( s, &other, 1 );
}





//////////////////////////////////////////////////////////
// Comparisons


bool ?==?(const string_res &s1, const string_res &s2) {
    return ByteCmp( s1.Handle.s, 0, s1.Handle.lnth, s2.Handle.s, 0, s2.Handle.lnth) == 0;
}

bool ?!=?(const string_res &s1, const string_res &s2) {
    return !(s1 == s2);
}
bool ?==?(const string_res &s, const char* other) {
    string_res sother = other;
    return s == sother;
}
bool ?!=?(const string_res &s, const char* other) {
    return !(s == other);
}


//////////////////////////////////////////////////////////
// Search

bool contains(const string_res &s, char ch) {
    for (i; size(s)) {
        if (s[i] == ch) return true;
    }
    return false;
}

int find(const string_res &s, char search) {
    return findFrom(s, 0, search);
}

int findFrom(const string_res &s, size_t fromPos, char search) {
    // FIXME: This paricular overload (find of single char) is optimized to use memchr.
    // The general overload (find of string, memchr applying to its first character) and `contains` should be adjusted to match.
    char * searchFrom = s.Handle.s + fromPos;
    size_t searchLnth = s.Handle.lnth - fromPos;
    int searchVal = search;
    char * foundAt = (char *) memchr(searchFrom, searchVal, searchLnth);
    if (foundAt == 0p) return s.Handle.lnth;
    else return foundAt - s.Handle.s;
}

int find(const string_res &s, const string_res &search) {
    return findFrom(s, 0, search);
}

int findFrom(const string_res &s, size_t fromPos, const string_res &search) {
    return findFrom(s, fromPos, search.Handle.s, search.Handle.lnth);
}

int find(const string_res &s, const char* search) {
    return findFrom(s, 0, search);
}
int findFrom(const string_res &s, size_t fromPos, const char* search) {
    return findFrom(s, fromPos, search, strlen(search));
}

int find(const string_res &s, const char* search, size_t searchsize) {
    return findFrom(s, 0, search, searchsize);
}

int findFrom(const string_res &s, size_t fromPos, const char* search, size_t searchsize) {

    /* Remaining implementations essentially ported from Sunjay's work */


    // FIXME: This is a naive algorithm. We probably want to switch to someting
    // like Boyer-Moore in the future.
    // https://en.wikipedia.org/wiki/String_searching_algorithm

    // Always find the empty string
    if (searchsize == 0) {
        return 0;
    }

    for (size_t i = fromPos; i < s.Handle.lnth; i++) {
        size_t remaining = s.Handle.lnth - i;
        // Never going to find the search string if the remaining string is
        // smaller than search
        if (remaining < searchsize) {
            break;
        }

        bool matched = true;
        for (size_t j = 0; j < searchsize; j++) {
            if (search[j] != s.Handle.s[i + j]) {
                matched = false;
                break;
            }
        }
        if (matched) {
            return i;
        }
    }

    return s.Handle.lnth;
}

bool includes(const string_res &s, const string_res &search) {
    return includes(s, search.Handle.s, search.Handle.lnth);
}

bool includes(const string_res &s, const char* search) {
    return includes(s, search, strlen(search));
}

bool includes(const string_res &s, const char* search, size_t searchsize) {
    return find(s, search, searchsize) < s.Handle.lnth;
}

bool startsWith(const string_res &s, const string_res &prefix) {
    return startsWith(s, prefix.Handle.s, prefix.Handle.lnth);
}

bool startsWith(const string_res &s, const char* prefix) {
    return startsWith(s, prefix, strlen(prefix));
}

bool startsWith(const string_res &s, const char* prefix, size_t prefixsize) {
    if (s.Handle.lnth < prefixsize) {
        return false;
    }
    return memcmp(s.Handle.s, prefix, prefixsize) == 0;
}

bool endsWith(const string_res &s, const string_res &suffix) {
    return endsWith(s, suffix.Handle.s, suffix.Handle.lnth);
}

bool endsWith(const string_res &s, const char* suffix) {
    return endsWith(s, suffix, strlen(suffix));
}

bool endsWith(const string_res &s, const char* suffix, size_t suffixsize) {
    if (s.Handle.lnth < suffixsize) {
        return false;
    }
    // Amount to offset the bytes pointer so that we are comparing the end of s
    // to suffix. s.bytes + offset should be the first byte to compare against suffix
    size_t offset = s.Handle.lnth - suffixsize;
    return memcmp(s.Handle.s + offset, suffix, suffixsize) == 0;
}

    /* Back to Mike's work */


///////////////////////////////////////////////////////////////////////////
// charclass, include, exclude

void ?{}( charclass_res & this, const string_res & chars) {
    (this){ chars.Handle.s, chars.Handle.lnth };
}

void ?{}( charclass_res & this, const char * chars ) {
    (this){ chars, strlen(chars) };
}

void ?{}( charclass_res & this, const char * chars, size_t charssize ) {
    (this.chars){ chars, charssize };
    // now sort it ?
}

void ^?{}( charclass_res & this ) {
    ^(this.chars){};
}

static bool test( const charclass_res & mask, char c ) {
    // instead, use sorted char list?
    return contains( mask.chars, c );
}

int exclude(const string_res &s, const charclass_res &mask) {
    for (int i = 0; i < size(s); i++) {
        if ( test(mask, s[i]) ) return i;
    }
    return size(s);
}

int include(const string_res &s, const charclass_res &mask) {
    for (int i = 0; i < size(s); i++) {
        if ( ! test(mask, s[i]) ) return i;
    }
    return size(s);
}

//######################### VbyteHeap "implementation" #########################


// Add a new HandleNode node n after the current HandleNode node.

static void AddThisAfter( HandleNode & this, HandleNode & n ) with(this) {
#ifdef VbyteDebug
    serr | "enter:AddThisAfter, this:" | &this | " n:" | &n;
#endif // VbyteDebug
    // Performance note: we are on the critical path here. MB has ensured that the verifies don't contribute to runtime (are compiled away, like they're supposed to be).
    verify( n.ulink != 0p );
    verify( this.ulink == n.ulink );
    flink = n.flink;
    blink = &n;
    n.flink->blink = &this;
    n.flink = &this;
#ifdef VbyteDebug
    {
                serr | "HandleList:";
                serr | nlOff;
                for ( HandleNode *ni = HeaderPtr->flink; ni != HeaderPtr; ni = ni->flink ) {
                        serr | "\tnode:" | ni | " lnth:" | ni->lnth | " s:" | (void *)ni->s | ",\"";
                        for ( int i = 0; i < ni->lnth; i += 1 ) {
                                serr | ni->s[i];
                        } // for
                        serr | "\" flink:" | ni->flink | " blink:" | ni->blink | nl;
                } // for
                serr | nlOn;
    }
    serr | "exit:AddThisAfter";
#endif // VbyteDebug
} // AddThisAfter


// Delete the current HandleNode node.

static void DeleteNode( HandleNode & this ) with(this) {
#ifdef VbyteDebug
    serr | "enter:DeleteNode, this:" | &this;
#endif // VbyteDebug
    flink->blink = blink;
    blink->flink = flink;
#ifdef VbyteDebug
    serr | "exit:DeleteNode";
#endif // VbyteDebug
} //  DeleteNode



// 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.

static char * VbyteAlloc( VbyteHeap & this, int size ) with(this) {
#ifdef VbyteDebug
    serr | "enter:VbyteAlloc, size:" | size;
#endif // VbyteDebug
    uintptr_t NoBytes;
    char *r;

    NoBytes = ( uintptr_t )EndVbyte + size;
    if ( NoBytes > ( uintptr_t )ExtVbyte ) {            // enough room for new byte-string ?
                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;
    EndVbyte += size;
#ifdef VbyteDebug
    serr | "exit:VbyteAlloc, r:" | (void *)r | " EndVbyte:" | (void *)EndVbyte | " ExtVbyte:" | ExtVbyte;
#endif // VbyteDebug
    return r;
} // VbyteAlloc


// 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 = TEMP_ALLOC(char, 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 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 );
                verify( 0 && "VbyteSM: Error - Cannot move byte strings as requested and keep handles in ascending order");
    } // if

    HandleNode *i;
    for ( i = h.flink; i->s != 0 && s > ( i->s ); i = i->flink ); // find the position for this node after h
    if ( & this != i->blink ) {
                DeleteNode( this );
                AddThisAfter( this, *i->blink );
    } // if
#ifdef VbyteDebug
    {
        serr | "HandleList:";
        serr | nlOff;
        for ( HandleNode *n = HeaderPtr->flink; n != HeaderPtr; n = n->flink ) {
            serr | "\tnode:" | n | " lnth:" | n->lnth | " s:" | (void *)n->s | ",\"";
            for ( int i = 0; i < n->lnth; i += 1 ) {
                serr | n->s[i];
            } // for
            serr | "\" flink:" | n->flink | " blink:" | n->blink | nl;
        } // for
        serr | nlOn;
    }
    serr | "exit:MoveThisAfter";
#endif // VbyteDebug
} // MoveThisAfter





//######################### VbyteHeap #########################

// Compare two byte strings in the byte-string area. The routine returns the following values:
//
// 1 => Src1-byte-string > Src2-byte-string
// 0 => Src1-byte-string = Src2-byte-string
// -1 => Src1-byte-string < Src2-byte-string

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;
#endif // VbyteDebug
    int cmp;

    CharZip: for ( int i = 0; ; i += 1 ) {
        if ( i == Src2Lnth - 1 ) {
            for ( ; ; i += 1 ) {
                if ( i == Src1Lnth - 1 ) {
                    cmp = 0;
                    break CharZip;
                } // exit
                if ( Src1[Src1Start + i] != ' ') {
                        // SUSPECTED BUG:  this could be be why Peter got the bug report about == " "  (why is this case here at all?)
                    cmp = 1;
                    break CharZip;
                } // exit
            } // for
        } // exit
        if ( i == Src1Lnth - 1 ) {
            for ( ; ; i += 1 ) {
                if ( i == Src2Lnth - 1 ) {
                    cmp = 0;
                    break CharZip;
                } // exit
                if ( Src2[Src2Start + i] != ' ') {
                    cmp = -1;
                    break CharZip;
                } // exit
            } // for
        } // exit
      if ( Src2[Src2Start + i] != Src1[Src1Start+ i]) {
            cmp = Src1[Src1Start + i] > Src2[Src2Start + i] ? 1 : -1;
            break CharZip;
        } // exit
    } // for
#ifdef VbyteDebug
    serr | "exit:ByteCmp, cmp:" | cmp;
#endif // VbyteDebug
    return cmp;
} // ByteCmp


// The compaction moves all of the byte strings currently in use to the beginning of the byte-string area and modifies
// the handles to reflect the new positions of the byte strings. Compaction assumes that the handle list is in ascending
// order by pointers into the byte-string area.  The strings associated with substrings do not have to be moved because
// the containing string has been moved. Hence, they only require that their string pointers be adjusted.

void compaction(VbyteHeap & this) with(this) {
    HandleNode *h;
    char *obase, *nbase, *limit;
    
    NoOfCompactions += 1;
    EndVbyte = StartVbyte;
    h = Header.flink;                                   // ignore header node
    for (;;) {
                memmove( EndVbyte, h->s, h->lnth );
                obase = h->s;
                h->s = EndVbyte;
                nbase = h->s;
                EndVbyte += h->lnth;
                limit = obase + h->lnth;
                h = h->flink;
                
                // check if any substrings are allocated within a string
                
                for (;;) {
                        if ( h == &Header ) break;                      // end of header list ?
                        if ( h->s >= limit ) break;                     // outside of current string ?
                        h->s = nbase + (( uintptr_t )h->s - ( uintptr_t )obase );
                        h = h->flink;
                } // for
                if ( h == &Header ) break;                      // end of header list ?
    } // for
} // compaction


static double heap_expansion_freespace_threshold = 0.1;  // default inherited from prior work: expand heap when less than 10% "free" (i.e. garbage)
                                                         // probably an unreasonable default, but need to assess early-round tests on changing it

void TUNING_set_string_heap_liveness_threshold( double val ) {
    heap_expansion_freespace_threshold = 1.0 - val;
}


// Garbage determines the amount of free space left in the heap and then reduces, leave the same, or extends the size of
// the heap.  The heap is then compacted in the existing heap or into the newly allocated heap.

void garbage(VbyteHeap & this, int minreq ) with(this) {
#ifdef VbyteDebug
    serr | "enter:garbage";
    {
                serr | "HandleList:";
                for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) {
                        serr | nlOff;
                        serr | "\tnode:" | n | " lnth:" | n->lnth | " s:" | (void *)n->s | ",\"";
                        for ( int i = 0; i < n->lnth; i += 1 ) {
                                serr | n->s[i];
                        } // for
                        serr | nlOn;
                        serr | "\" flink:" | n->flink | " blink:" | n->blink;
                } // for
    }
#endif // VbyteDebug
    int AmountUsed, AmountFree;

    AmountUsed = 0;
    for ( HandleNode *i = Header.flink; i != &Header; i = i->flink ) { // calculate amount of byte area used
                AmountUsed += i->lnth;
    } // for
    AmountFree = ( uintptr_t )ExtVbyte - ( uintptr_t )StartVbyte - AmountUsed;
    
    if ( ( double ) AmountFree < ( CurrSize * heap_expansion_freespace_threshold ) || AmountFree < minreq ) {   // free space less than threshold 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."
                        //  } else if ( AmountFree > CurrSize / 2 ) {           // free space greater than 3 times the initial allocation ? 
                        //              reduce(( AmountFree / CurrSize - 3 ) * CurrSize ); // reduce the memory

        // `extend` implies a `compaction` during the copy

    } else {
        compaction(this);                                       // in-place
    }// if
#ifdef VbyteDebug
    {
                serr | "HandleList:";
                for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) {
                        serr | nlOff;
                        serr | "\tnode:" | n | " lnth:" | n->lnth | " s:" | (void *)n->s | ",\"";
                        for ( int i = 0; i < n->lnth; i += 1 ) {
                                serr | n->s[i];
                        } // for
                        serr | nlOn;
                        serr | "\" flink:" | n->flink | " blink:" | n->blink;
                } // for
    }
    serr | "exit:garbage";
#endif // VbyteDebug
} // garbage

#undef VbyteDebug



// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string
// area is deleted.

void extend( VbyteHeap & this, int size ) with (this) {
#ifdef VbyteDebug
    serr | "enter:extend, size:" | size;
#endif // VbyteDebug
    char *OldStartVbyte;

    NoOfExtensions += 1;
    OldStartVbyte = StartVbyte;                         // save previous byte area
    
    CurrSize += size > InitSize ? size : InitSize;      // minimum extension, initial size
    StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize);
    ExtVbyte = (void *)( StartVbyte + CurrSize );
    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;
#endif // VbyteDebug
} // 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
// area is deleted.

void VbyteHeap::reduce( int size ) {
#ifdef VbyteDebug
    serr | "enter:reduce, size:" | size;
#endif // VbyteDebug
    char *OldStartVbyte;

    NoOfReductions += 1;
    OldStartVbyte = StartVbyte;                         // save previous byte area
    
    CurrSize -= size;
    StartVbyte = EndVbyte = new char[CurrSize];
    ExtVbyte = (void *)( StartVbyte + CurrSize );
    compaction();                                       // copy from old heap to new & adjust pointers to new heap
    delete  OldStartVbyte;                              // release old heap
#ifdef VbyteDebug
    serr | "exit:reduce, CurrSize:" | CurrSize;
#endif // VbyteDebug
} // reduce


#endif