source: libcfa/src/containers/string_res.cfa @ 329487c

Last change on this file since 329487c was 329487c, checked in by Peter A. Buhr <pabuhr@…>, 11 months ago

change examples to use the new wdi manipulator for C-strings to specify string and read size
  • Property mode set to 100644
File size: 39.5 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// string_res -- variable-length, mutable run of text, with resource semantics
8//
9// Author           : Michael L. Brooks
10// Created On       : Fri Sep 03 11:00:00 2021
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Mon Aug 14 18:06:01 2023
13// Update Count     : 12
14//
15
16#include "string_res.hfa"
17#include "string_sharectx.hfa"
18#include "stdlib.hfa"
19#include <ctype.h>
20
21// Workaround for observed performance penalty from calling CFA's alloc.
22// Workaround is:  EndVbyte = TEMP_ALLOC(char, CurrSize)
23// Should be:      EndVbyte = alloc(CurrSize)
24#define TEMP_ALLOC(T, n) (( T* ) malloc( n * sizeof( T ) ))
25
26#include <assert.h>
27
28//######################### VbyteHeap "header" #########################
29
30#ifdef VbyteDebug
31HandleNode *HeaderPtr;
32#endif // VbyteDebug
33
34struct VbyteHeap {
35
36    int NoOfCompactions;                                // number of compactions of the byte area
37    int NoOfExtensions;                                 // number of extensions in the size of the byte area
38    int NoOfReductions;                                 // number of reductions in the size of the byte area
39   
40    int InitSize;                                       // initial number of bytes in the byte-string area
41    int CurrSize;                                       // current number of bytes in the byte-string area
42    char *StartVbyte;                                   // pointer to the `st byte of the start of the byte-string area
43    char *EndVbyte;                                     // pointer to the next byte after the end of the currently used portion of byte-string area
44    void *ExtVbyte;                                     // pointer to the next byte after the end of the byte-string area
45
46    HandleNode Header;                                  // header node for handle list
47}; // VbyteHeap
48
49   
50static void compaction( VbyteHeap & );                          // compaction of the byte area
51static void garbage( VbyteHeap &, int );                                // garbage collect the byte area
52static void extend( VbyteHeap &, int );                 // extend the size of the byte area
53static void reduce( VbyteHeap &, int );                 // reduce the size of the byte area
54
55static void ?{}( VbyteHeap &, size_t = 1000 );
56static void ^?{}( VbyteHeap & );
57
58static int ByteCmp( char *, int, int, char *, int, int );       // compare 2 blocks of bytes
59static char *VbyteAlloc( VbyteHeap &, int );                    // allocate a block bytes in the heap
60static char *VbyteTryAdjustLast( VbyteHeap &, int );
61
62static void AddThisAfter( HandleNode &, HandleNode & );
63static void DeleteNode( HandleNode & );
64static void MoveThisAfter( HandleNode &, const HandleNode & );          // move current handle after parameter handle
65
66
67// Allocate the storage for the variable sized area and intialize the heap variables.
68
69static void ?{}( VbyteHeap & this, size_t Size ) with(this) {
70#ifdef VbyteDebug
71    serr | "enter:VbyteHeap::VbyteHeap, this:" | &this | " Size:" | Size;
72#endif // VbyteDebug
73    NoOfCompactions = NoOfExtensions = NoOfReductions = 0;
74    InitSize = CurrSize = Size;
75    StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize);
76    ExtVbyte = (void *)( StartVbyte + CurrSize );
77    Header.flink = Header.blink = &Header;
78    Header.ulink = & this;
79#ifdef VbyteDebug
80    HeaderPtr = &Header;
81    serr | "exit:VbyteHeap::VbyteHeap, this:" | &this;
82#endif // VbyteDebug
83} // VbyteHeap
84
85
86// Release the dynamically allocated storage for the byte area.
87
88static void ^?{}( VbyteHeap & this ) with(this) {
89    free( StartVbyte );
90} // ~VbyteHeap
91
92
93//######################### HandleNode #########################
94
95
96// Create a handle node. The handle is not linked into the handle list.  This is the responsibilitiy of the handle
97// creator.
98
99static void ?{}( HandleNode & this ) with(this) {
100#ifdef VbyteDebug
101    serr | "enter:HandleNode::HandleNode, this:" | &this;
102#endif // VbyteDebug
103    s = 0;
104    lnth = 0;
105#ifdef VbyteDebug
106    serr | "exit:HandleNode::HandleNode, this:" | &this;
107#endif // VbyteDebug
108} // HandleNode
109
110// Create a handle node. The handle is linked into the handle list at the end. This means that this handle will NOT be
111// in order by string address, but this is not a problem because a string with length zero does nothing during garbage
112// collection.
113
114static void ?{}( HandleNode & this, VbyteHeap & vh ) with(this) {
115#ifdef VbyteDebug
116    serr | "enter:HandleNode::HandleNode, this:" | &this;
117#endif // VbyteDebug
118    s = 0;
119    lnth = 0;
120    ulink = &vh;
121    AddThisAfter( this, *vh.Header.blink );
122#ifdef VbyteDebug
123    serr | "exit:HandleNode::HandleNode, this:" | &this;
124#endif // VbyteDebug
125} // HandleNode
126
127
128// Delete a node from the handle list by unchaining it from the list. If the handle node was allocated dynamically, it
129// is the responsibility of the creator to destroy it.
130
131static void ^?{}( HandleNode & this ) with(this) {
132#ifdef VbyteDebug
133    serr | "enter:HandleNode::~HandleNode, this:" | & this;
134    {
135        serr | nlOff;
136        serr | " lnth:" | lnth | " s:" | (void *)s | ",\"";
137        for ( i; lnth ) {
138            serr | s[i];
139        } // for
140        serr | "\" flink:" | flink | " blink:" | blink | nl;
141        serr | nlOn;
142    }
143#endif // VbyteDebug
144    DeleteNode( this );
145} // ~HandleNode
146
147
148//######################### String Sharing Context #########################
149
150static string_sharectx * ambient_string_sharectx;               // fickle top of stack
151static string_sharectx default_string_sharectx = {NEW_SHARING}; // stable bottom of stack
152
153void ?{}( string_sharectx & this, StringSharectx_Mode mode ) with( this ) {
154    (older){ ambient_string_sharectx };
155    if ( mode == NEW_SHARING ) {
156        (activeHeap){ new( (size_t) 1000 ) };
157    } else {
158        verify( mode == NO_SHARING );
159        (activeHeap){ 0p };
160    }
161    ambient_string_sharectx = & this;
162}
163
164void ^?{}( string_sharectx & this ) with( this ) {
165    if ( activeHeap ) delete( activeHeap );
166
167    // unlink this from older-list starting from ambient_string_sharectx
168    // usually, this==ambient_string_sharectx and the loop runs zero times
169    string_sharectx *& c = ambient_string_sharectx;
170    while ( c != &this ) &c = &c->older;              // find this
171    c = this.older;                                   // unlink
172}
173
174//######################### String Resource #########################
175
176
177VbyteHeap * DEBUG_string_heap() {
178    assert( ambient_string_sharectx->activeHeap && "No sharing context is active" );
179    return ambient_string_sharectx->activeHeap;
180}
181
182size_t DEBUG_string_bytes_avail_until_gc( VbyteHeap * heap ) {
183    return ((char*)heap->ExtVbyte) - heap->EndVbyte;
184}
185
186size_t DEBUG_string_bytes_in_heap( VbyteHeap * heap ) {
187    return heap->CurrSize;
188}
189
190const char * DEBUG_string_heap_start( VbyteHeap * heap ) {
191    return heap->StartVbyte;
192}
193
194// Returns the size of the string in bytes
195size_t size(const string_res &s) with(s) {
196    return Handle.lnth;
197}
198
199// Output operator
200ofstream & ?|?(ofstream &out, const string_res &s) {
201        // CFA string is NOT null terminated, so print exactly lnth characters in a minimum width of 0.
202        out | wd( 0, s.Handle.lnth, s.Handle.s ) | nonl;
203    return out;
204}
205
206void ?|?(ofstream &out, const string_res &s) {
207        (ofstream &)(out | s); ends( out );
208}
209
210// Input operator
211ifstream & ?|?(ifstream &in, string_res &s) {
212
213    // Reading into a temp before assigning to s is near zero overhead in typical cases because of sharing.
214    // If s is a substring of something larger, simple assignment takes care of that case correctly.
215    // But directly reading a variable amount of text into the middle of a larger context is not practical.
216    string_res temp;
217
218    // Read in chunks.  Often, one chunk is enough.  Keep the string that accumulates chunks last in the heap,
219    // so available room is rest of heap.  When a chunk fills the heap, force growth then take the next chunk.
220    for (;;) {
221        // Append dummy content to temp, forcing expansion when applicable (occurs always on subsequent loops)
222        // length 2 ensures room for at least one real char, plus scanf/pipe-cstr's null terminator
223        temp += "--";
224        assert( temp.Handle.ulink->EndVbyte == temp.Handle.s + temp.Handle.lnth );    // last in heap
225
226        // reset, to overwrite the appended "--"
227        temp.Handle.lnth -= 2;
228        temp.Handle.ulink->EndVbyte -= 2;
229
230        // rest of heap, less 1 byte for null terminator, is available to read into
231        int lenReadable = (char*)temp.Handle.ulink->ExtVbyte - temp.Handle.ulink->EndVbyte - 1;
232        assert (lenReadable >= 1);
233
234        // get bytes
235        in | wdi( lenReadable + 1, lenReadable, temp.Handle.ulink->EndVbyte );
236        int lenWasRead = strlen(temp.Handle.ulink->EndVbyte);
237
238        // update metadata
239        temp.Handle.lnth += lenWasRead;
240        temp.Handle.ulink->EndVbyte += lenWasRead;
241
242      if (lenWasRead < lenReadable) break;
243    }
244
245    s = temp;
246    return in;
247}
248
249
250// Empty constructor
251void ?{}(string_res &s) with(s) {
252    if( ambient_string_sharectx->activeHeap ) {
253        (Handle){ * ambient_string_sharectx->activeHeap };
254        (shareEditSet_owns_ulink){ false };
255        verify( Handle.s == 0p && Handle.lnth == 0 );
256    } else {
257        (Handle){ * new( (size_t) 10 ) };  // TODO: can I lazily avoid allocating for empty string
258        (shareEditSet_owns_ulink){ true };
259        Handle.s = Handle.ulink->StartVbyte;
260        verify( Handle.lnth == 0 );
261    }
262    s.shareEditSet_prev = &s;
263    s.shareEditSet_next = &s;
264}
265
266static void eagerCopyCtorHelper(string_res &s, const char* rhs, size_t rhslnth) with(s) {
267    if( ambient_string_sharectx->activeHeap ) {
268        (Handle){ * ambient_string_sharectx->activeHeap };
269        (shareEditSet_owns_ulink){ false };
270    } else {
271        (Handle){ * new( rhslnth ) };
272        (shareEditSet_owns_ulink){ true };
273    }
274    Handle.s = VbyteAlloc(*Handle.ulink, rhslnth);
275    Handle.lnth = rhslnth;
276    memmove( Handle.s, rhs, rhslnth );
277    s.shareEditSet_prev = &s;
278    s.shareEditSet_next = &s;
279}
280
281// Constructor from a raw buffer and size
282void ?{}(string_res &s, const char* rhs, size_t rhslnth) with(s) {
283    eagerCopyCtorHelper(s, rhs, rhslnth);
284}
285
286// private ctor (not in header): use specified heap (ignore ambient) and copy chars in
287void ?{}( string_res &s, VbyteHeap & heap, const char* rhs, size_t rhslnth ) with(s) {
288    (Handle){ heap };
289    Handle.s = VbyteAlloc(*Handle.ulink, rhslnth);
290    Handle.lnth = rhslnth;
291    (s.shareEditSet_owns_ulink){ false };
292    memmove( Handle.s, rhs, rhslnth );
293    s.shareEditSet_prev = &s;
294    s.shareEditSet_next = &s;
295}
296
297// General copy constructor
298void ?{}(string_res &s, const string_res & s2, StrResInitMode mode, size_t start, size_t end ) {
299
300    verify( start <= end && end <= s2.Handle.lnth );
301
302    if (s2.Handle.ulink != ambient_string_sharectx->activeHeap && mode == COPY_VALUE) {
303        // crossing heaps (including private): copy eagerly
304        eagerCopyCtorHelper(s, s2.Handle.s + start, end - start);
305        verify(s.shareEditSet_prev == &s);
306        verify(s.shareEditSet_next == &s);
307    } else {
308        (s.Handle){};
309        s.Handle.s = s2.Handle.s + start;
310        s.Handle.lnth = end - start;
311        s.Handle.ulink = s2.Handle.ulink;
312
313        AddThisAfter(s.Handle, s2.Handle );                     // insert this handle after rhs handle
314        // ^ bug?  skip others at early point in string
315
316        if (mode == COPY_VALUE) {
317            verify(s2.Handle.ulink == ambient_string_sharectx->activeHeap);
318            // requested logical copy in same heap: defer copy until write
319
320            (s.shareEditSet_owns_ulink){ false };
321
322            // make s alone in its shareEditSet
323            s.shareEditSet_prev = &s;
324            s.shareEditSet_next = &s;
325        } else {
326            verify( mode == SHARE_EDITS );
327            // sharing edits with source forces same heap as source (ignore context)
328
329            (s.shareEditSet_owns_ulink){ s2.shareEditSet_owns_ulink };
330
331            // s2 is logically const but not implementation const
332            string_res & s2mod = (string_res &) s2;
333
334            // insert s after s2 on shareEditSet
335            s.shareEditSet_next = s2mod.shareEditSet_next;
336            s.shareEditSet_prev = &s2mod;
337            s.shareEditSet_next->shareEditSet_prev = &s;
338            s.shareEditSet_prev->shareEditSet_next = &s;
339        }
340    }
341}
342
343static void assignEditSet(string_res & this, string_res * shareEditSetStartPeer, string_res * shareEditSetEndPeer,
344    char * resultSesStart,
345    size_t resultSesLnth,
346    HandleNode * resultPadPosition, size_t bsize ) {
347
348    char * beforeBegin = shareEditSetStartPeer->Handle.s;
349    size_t beforeLen = this.Handle.s - beforeBegin;
350
351    char * afterBegin = this.Handle.s + this.Handle.lnth;
352    size_t afterLen = shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - afterBegin;
353
354    size_t oldLnth = this.Handle.lnth;
355
356    this.Handle.s = resultSesStart + beforeLen;
357    this.Handle.lnth = bsize;
358    if (resultPadPosition)
359        MoveThisAfter( this.Handle, *resultPadPosition );
360
361    // adjust all substring string and handle locations, and check if any substring strings are outside the new base string
362    char *limit = resultSesStart + resultSesLnth;
363    for ( string_res * p = this.shareEditSet_next; p != &this; p = p->shareEditSet_next ) {
364        verify (p->Handle.s >= beforeBegin);
365        if ( p->Handle.s >= afterBegin ) {
366            verify ( p->Handle.s <= afterBegin + afterLen );
367            verify ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen );
368            // p starts after the edit
369            // take start and end as end-anchored
370            size_t startOffsetFromEnd = afterBegin + afterLen - p->Handle.s;
371            p->Handle.s = limit - startOffsetFromEnd;
372            // p->Handle.lnth unaffected
373        } else if ( p->Handle.s <= beforeBegin + beforeLen ) {
374            // p starts before, or at the start of, the edit
375            if ( p->Handle.s + p->Handle.lnth <= beforeBegin + beforeLen ) {
376                // p ends before the edit
377                // take end as start-anchored too
378                // p->Handle.lnth unaffected
379            } else if ( p->Handle.s + p->Handle.lnth < afterBegin ) {
380                // p ends during the edit; p does not include the last character replaced
381                // clip end of p to end at start of edit
382                p->Handle.lnth = beforeLen - ( p->Handle.s - beforeBegin );
383            } else {
384                // p ends after the edit
385                verify ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen );
386                // take end as end-anchored
387                // stretch-shrink p according to the edit
388                p->Handle.lnth += this.Handle.lnth;
389                p->Handle.lnth -= oldLnth;
390            }
391            // take start as start-anchored
392            size_t startOffsetFromStart = p->Handle.s - beforeBegin;
393            p->Handle.s = resultSesStart + startOffsetFromStart;
394        } else {
395            verify ( p->Handle.s < afterBegin );
396            // p starts during the edit
397            verify( p->Handle.s + p->Handle.lnth >= beforeBegin + beforeLen );
398            if ( p->Handle.s + p->Handle.lnth < afterBegin ) {
399                // p ends during the edit; p does not include the last character replaced
400                // set p to empty string at start of edit
401                p->Handle.s = this.Handle.s;
402                p->Handle.lnth = 0;
403            } else {
404                // p includes the end of the edit
405                // clip start of p to start at end of edit
406                int charsToClip = afterBegin - p->Handle.s;
407                p->Handle.s = this.Handle.s + this.Handle.lnth;
408                p->Handle.lnth -= charsToClip;
409            }
410        }
411        if (resultPadPosition)
412            MoveThisAfter( p->Handle, *resultPadPosition );     // move substring handle to maintain sorted order by string position
413    }
414}
415
416// traverse the share-edit set (SES) to recover the range of a base string to which `this` belongs
417static void locateInShareEditSet( string_res &this, string_res *&shareEditSetStartPeer, string_res *&shareEditSetEndPeer ) {
418    shareEditSetStartPeer = & this;
419    shareEditSetEndPeer = & this;
420    for (string_res * editPeer = this.shareEditSet_next; editPeer != &this; editPeer = editPeer->shareEditSet_next) {
421        if ( editPeer->Handle.s < shareEditSetStartPeer->Handle.s ) {
422            shareEditSetStartPeer = editPeer;
423        }
424        if ( shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth < editPeer->Handle.s + editPeer->Handle.lnth) {
425            shareEditSetEndPeer = editPeer;
426        }
427    }
428}
429
430static string_res & assign_(string_res &this, const char* buffer, size_t bsize, const string_res & valSrc) {
431
432    string_res * shareEditSetStartPeer;
433    string_res * shareEditSetEndPeer;
434    locateInShareEditSet( this, shareEditSetStartPeer, shareEditSetEndPeer );
435
436    verify( shareEditSetEndPeer->Handle.s >= shareEditSetStartPeer->Handle.s );
437    size_t origEditSetLength = shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - shareEditSetStartPeer->Handle.s;
438    verify( origEditSetLength >= this.Handle.lnth );
439
440    if ( this.shareEditSet_owns_ulink ) {                 // assigning to private context
441        // ok to overwrite old value within LHS
442        char * prefixStartOrig = shareEditSetStartPeer->Handle.s;
443        int prefixLen = this.Handle.s - prefixStartOrig;
444        char * suffixStartOrig = this.Handle.s + this.Handle.lnth;
445        int suffixLen = shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - suffixStartOrig;
446
447        int delta = bsize - this.Handle.lnth;
448        if ( char * oldBytes = VbyteTryAdjustLast( *this.Handle.ulink, delta ) ) {
449            // growing: copy from old to new
450            char * dest = VbyteAlloc( *this.Handle.ulink, origEditSetLength + delta );
451            char *destCursor = dest;  memcpy(destCursor, prefixStartOrig, prefixLen);
452            destCursor += prefixLen;  memcpy(destCursor, buffer         , bsize    );
453            destCursor += bsize;      memcpy(destCursor, suffixStartOrig, suffixLen);
454            assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer,
455                dest,
456                origEditSetLength + delta,
457                0p, bsize);
458            free( oldBytes );
459        } else {
460            // room is already allocated in-place: bubble suffix and overwite middle
461            memmove( suffixStartOrig + delta, suffixStartOrig, suffixLen );
462            memcpy( this.Handle.s, buffer, bsize );
463
464            assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer,
465                shareEditSetStartPeer->Handle.s,
466                origEditSetLength + delta,
467                0p, bsize);
468        }
469
470    } else if (                                           // assigning to shared context
471        this.Handle.lnth == origEditSetLength &&          // overwriting entire run of SES
472        & valSrc &&                                       // sourcing from a managed string
473        valSrc.Handle.ulink == this.Handle.ulink  ) {     // sourcing from same heap
474
475        // SES's result will only use characters from the source string => reuse source
476        assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer,
477            valSrc.Handle.s,
478            valSrc.Handle.lnth,
479            &((string_res&)valSrc).Handle, bsize);
480       
481    } else {
482        // overwriting a proper substring of some string: mash characters from old and new together (copy on write)
483        // OR we are importing characters: need to copy eagerly (can't refer to source)
484
485        // full string is from start of shareEditSetStartPeer thru end of shareEditSetEndPeer
486        // `this` occurs in the middle of it, to be replaced
487        // build up the new text in `pasting`
488
489        string_res pasting = {
490            * this.Handle.ulink,                               // maintain same heap, regardless of context
491            shareEditSetStartPeer->Handle.s,                   // start of SES
492            this.Handle.s - shareEditSetStartPeer->Handle.s }; // length of SES, before this
493        append( pasting,
494            buffer,                                            // start of replacement for this
495            bsize );                                           // length of replacement for this
496        append( pasting,
497            this.Handle.s + this.Handle.lnth,                  // start of SES after this
498            shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth -
499            (this.Handle.s + this.Handle.lnth) );              // length of SES, after this
500
501        // The above string building can trigger compaction.
502        // The reference points (that are arguments of the string building) may move during that building.
503        // From this point on, they are stable.
504
505        assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer,
506            pasting.Handle.s,
507            pasting.Handle.lnth,
508            &pasting.Handle, bsize);
509    }
510
511    return this;
512}
513
514string_res & assign(string_res &this, const char* buffer, size_t bsize) {
515    return assign_(this, buffer, bsize, *0p);
516}
517
518string_res & ?=?(string_res &s, char other) {
519    return assign(s, &other, 1);
520}
521
522// Copy assignment operator
523string_res & ?=?(string_res & this, const string_res & rhs) with( this ) {
524    return assign_(this, rhs.Handle.s, rhs.Handle.lnth, rhs);
525}
526
527string_res & ?=?(string_res & this, string_res & rhs) with( this ) {
528    const string_res & rhs2 = rhs;
529    return this = rhs2;
530}
531
532
533// Destructor
534void ^?{}(string_res &s) with(s) {
535    // much delegated to implied ^VbyteSM
536
537    // sever s from its share-edit peers, if any (four no-ops when already solo)
538    s.shareEditSet_prev->shareEditSet_next = s.shareEditSet_next;
539    s.shareEditSet_next->shareEditSet_prev = s.shareEditSet_prev;
540    // s.shareEditSet_next = &s;
541    // s.shareEditSet_prev = &s;
542
543    if (shareEditSet_owns_ulink && s.shareEditSet_next == &s) { // last one out
544        delete( s.Handle.ulink );
545    }
546}
547
548
549// Returns the character at the given index
550// With unicode support, this may be different from just the byte at the given
551// offset from the start of the string.
552char ?[?](const string_res &s, size_t index) with(s) {
553    //TODO: Check if index is valid (no exceptions yet)
554    return Handle.s[index];
555}
556
557void assignAt(const string_res &s, size_t index, char val) {
558    string_res editZone = { s, SHARE_EDITS, index, index+1 };
559    assign(editZone, &val, 1);
560}
561
562
563///////////////////////////////////////////////////////////////////
564// Concatenation
565
566void append(string_res &str1, const char * buffer, size_t bsize) {
567    size_t clnth = str1.Handle.lnth + bsize;
568    if ( str1.Handle.s + str1.Handle.lnth == buffer ) { // already juxtapose ?
569        // no-op
570    } else {                                            // must copy some text
571        if ( str1.Handle.s + str1.Handle.lnth == VbyteAlloc(*str1.Handle.ulink, 0) ) { // str1 at end of string area ?
572            VbyteAlloc( *str1.Handle.ulink, bsize ); // create room for 2nd part at the end of string area
573        } else {                                        // copy the two parts
574            char * str1newBuf = VbyteAlloc( *str1.Handle.ulink, clnth );
575            char * str1oldBuf = str1.Handle.s;  // must read after VbyteAlloc call in case it gs's
576            str1.Handle.s = str1newBuf;
577            memcpy( str1.Handle.s, str1oldBuf,  str1.Handle.lnth );
578        } // if
579        memcpy( str1.Handle.s + str1.Handle.lnth, buffer, bsize );
580    } // if
581    str1.Handle.lnth = clnth;
582}
583
584void ?+=?(string_res &str1, const string_res &str2) {
585    append( str1, str2.Handle.s, str2.Handle.lnth );
586}
587
588void ?+=?(string_res &s, char other) {
589    append( s, &other, 1 );
590}
591
592
593
594
595
596//////////////////////////////////////////////////////////
597// Comparisons
598
599
600bool ?==?(const string_res &s1, const string_res &s2) {
601    return ByteCmp( s1.Handle.s, 0, s1.Handle.lnth, s2.Handle.s, 0, s2.Handle.lnth) == 0;
602}
603
604bool ?!=?(const string_res &s1, const string_res &s2) {
605    return !(s1 == s2);
606}
607bool ?==?(const string_res &s, const char* other) {
608    string_res sother = other;
609    return s == sother;
610}
611bool ?!=?(const string_res &s, const char* other) {
612    return !(s == other);
613}
614
615
616//////////////////////////////////////////////////////////
617// Search
618
619bool contains(const string_res &s, char ch) {
620    for ( i; size(s) ) {
621        if (s[i] == ch) return true;
622    }
623    return false;
624}
625
626int find(const string_res &s, char search) {
627    return findFrom(s, 0, search);
628}
629
630int findFrom(const string_res &s, size_t fromPos, char search) {
631    // FIXME: This paricular overload (find of single char) is optimized to use memchr.
632    // The general overload (find of string, memchr applying to its first character) and `contains` should be adjusted to match.
633    char * searchFrom = s.Handle.s + fromPos;
634    size_t searchLnth = s.Handle.lnth - fromPos;
635    int searchVal = search;
636    char * foundAt = (char *) memchr(searchFrom, searchVal, searchLnth);
637    if (foundAt == 0p) return s.Handle.lnth;
638    else return foundAt - s.Handle.s;
639}
640
641int find(const string_res &s, const string_res &search) {
642    return findFrom(s, 0, search);
643}
644
645int findFrom(const string_res &s, size_t fromPos, const string_res &search) {
646    return findFrom(s, fromPos, search.Handle.s, search.Handle.lnth);
647}
648
649int find(const string_res &s, const char* search) {
650    return findFrom(s, 0, search);
651}
652int findFrom(const string_res &s, size_t fromPos, const char* search) {
653    return findFrom(s, fromPos, search, strlen(search));
654}
655
656int find(const string_res &s, const char* search, size_t searchsize) {
657    return findFrom(s, 0, search, searchsize);
658}
659
660int findFrom(const string_res &s, size_t fromPos, const char* search, size_t searchsize) {
661
662    /* Remaining implementations essentially ported from Sunjay's work */
663
664
665    // FIXME: This is a naive algorithm. We probably want to switch to someting
666    // like Boyer-Moore in the future.
667    // https://en.wikipedia.org/wiki/String_searching_algorithm
668
669    // Always find the empty string
670    if (searchsize == 0) {
671        return 0;
672    }
673
674    for ( i; fromPos ~ s.Handle.lnth ) {
675        size_t remaining = s.Handle.lnth - i;
676        // Never going to find the search string if the remaining string is
677        // smaller than search
678        if (remaining < searchsize) {
679            break;
680        }
681
682        bool matched = true;
683        for ( j; searchsize ) {
684            if (search[j] != s.Handle.s[i + j]) {
685                matched = false;
686                break;
687            }
688        }
689        if (matched) {
690            return i;
691        }
692    }
693
694    return s.Handle.lnth;
695}
696
697bool includes(const string_res &s, const string_res &search) {
698    return includes(s, search.Handle.s, search.Handle.lnth);
699}
700
701bool includes(const string_res &s, const char* search) {
702    return includes(s, search, strlen(search));
703}
704
705bool includes(const string_res &s, const char* search, size_t searchsize) {
706    return find(s, search, searchsize) < s.Handle.lnth;
707}
708
709bool startsWith(const string_res &s, const string_res &prefix) {
710    return startsWith(s, prefix.Handle.s, prefix.Handle.lnth);
711}
712
713bool startsWith(const string_res &s, const char* prefix) {
714    return startsWith(s, prefix, strlen(prefix));
715}
716
717bool startsWith(const string_res &s, const char* prefix, size_t prefixsize) {
718    if (s.Handle.lnth < prefixsize) {
719        return false;
720    }
721    return memcmp(s.Handle.s, prefix, prefixsize) == 0;
722}
723
724bool endsWith(const string_res &s, const string_res &suffix) {
725    return endsWith(s, suffix.Handle.s, suffix.Handle.lnth);
726}
727
728bool endsWith(const string_res &s, const char* suffix) {
729    return endsWith(s, suffix, strlen(suffix));
730}
731
732bool endsWith(const string_res &s, const char* suffix, size_t suffixsize) {
733    if (s.Handle.lnth < suffixsize) {
734        return false;
735    }
736    // Amount to offset the bytes pointer so that we are comparing the end of s
737    // to suffix. s.bytes + offset should be the first byte to compare against suffix
738    size_t offset = s.Handle.lnth - suffixsize;
739    return memcmp(s.Handle.s + offset, suffix, suffixsize) == 0;
740}
741
742    /* Back to Mike's work */
743
744
745///////////////////////////////////////////////////////////////////////////
746// charclass, include, exclude
747
748void ?{}( charclass_res & this, const string_res & chars) {
749    (this){ chars.Handle.s, chars.Handle.lnth };
750}
751
752void ?{}( charclass_res & this, const char * chars ) {
753    (this){ chars, strlen(chars) };
754}
755
756void ?{}( charclass_res & this, const char * chars, size_t charssize ) {
757    (this.chars){ chars, charssize };
758    // now sort it ?
759}
760
761void ^?{}( charclass_res & this ) {
762    ^(this.chars){};
763}
764
765static bool test( const charclass_res & mask, char c ) {
766    // instead, use sorted char list?
767    return contains( mask.chars, c );
768}
769
770int exclude(const string_res &s, const charclass_res &mask) {
771    for ( i; size(s) ) {
772        if ( test(mask, s[i]) ) return i;
773    }
774    return size(s);
775}
776
777int include(const string_res &s, const charclass_res &mask) {
778    for ( i; size(s) ) {
779        if ( ! test(mask, s[i]) ) return i;
780    }
781    return size(s);
782}
783
784//######################### VbyteHeap "implementation" #########################
785
786
787// Add a new HandleNode node n after the current HandleNode node.
788
789static void AddThisAfter( HandleNode & this, HandleNode & n ) with(this) {
790#ifdef VbyteDebug
791    serr | "enter:AddThisAfter, this:" | &this | " n:" | &n;
792#endif // VbyteDebug
793    // 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).
794    verify( n.ulink != 0p );
795    verify( this.ulink == n.ulink );
796    flink = n.flink;
797    blink = &n;
798    n.flink->blink = &this;
799    n.flink = &this;
800#ifdef VbyteDebug
801    {
802                serr | "HandleList:";
803                serr | nlOff;
804                for ( HandleNode *ni = HeaderPtr->flink; ni != HeaderPtr; ni = ni->flink ) {
805                        serr | "\tnode:" | ni | " lnth:" | ni->lnth | " s:" | (void *)ni->s | ",\"";
806                        for ( i; ni->lnth ) {
807                                serr | ni->s[i];
808                        } // for
809                        serr | "\" flink:" | ni->flink | " blink:" | ni->blink | nl;
810                } // for
811                serr | nlOn;
812    }
813    serr | "exit:AddThisAfter";
814#endif // VbyteDebug
815} // AddThisAfter
816
817
818// Delete the current HandleNode node.
819
820static void DeleteNode( HandleNode & this ) with(this) {
821#ifdef VbyteDebug
822    serr | "enter:DeleteNode, this:" | &this;
823#endif // VbyteDebug
824    flink->blink = blink;
825    blink->flink = flink;
826#ifdef VbyteDebug
827    serr | "exit:DeleteNode";
828#endif // VbyteDebug
829} //  DeleteNode
830
831
832
833// Allocates specified storage for a string from byte-string area. If not enough space remains to perform the
834// allocation, the garbage collection routine is called.
835
836static char * VbyteAlloc( VbyteHeap & this, int size ) with(this) {
837#ifdef VbyteDebug
838    serr | "enter:VbyteAlloc, size:" | size;
839#endif // VbyteDebug
840    uintptr_t NoBytes;
841    char *r;
842
843    NoBytes = ( uintptr_t )EndVbyte + size;
844    if ( NoBytes > ( uintptr_t )ExtVbyte ) {            // enough room for new byte-string ?
845                garbage( this, size );                                  // firer up the garbage collector
846                verify( (( uintptr_t )EndVbyte + size) <= ( uintptr_t )ExtVbyte  && "garbage run did not free up required space" );
847    } // if
848    r = EndVbyte;
849    EndVbyte += size;
850#ifdef VbyteDebug
851    serr | "exit:VbyteAlloc, r:" | (void *)r | " EndVbyte:" | (void *)EndVbyte | " ExtVbyte:" | ExtVbyte;
852#endif // VbyteDebug
853    return r;
854} // VbyteAlloc
855
856
857// Adjusts the last allocation in this heap by delta bytes, or resets this heap to be able to offer
858// new allocations of its original size + delta bytes. Positive delta means bigger;
859// negative means smaller.  A null return indicates that the original heap location has room for
860// the requested growth.  A non-null return indicates that copying to a new location is required
861// but has not been done; the returned value is the old heap storage location; `this` heap is
862// modified to reference the new location.  In the copy-requred case, the caller should use
863// VbyteAlloc to claim the new space, while doing optimal copying from old to new, then free old.
864
865static char * VbyteTryAdjustLast( VbyteHeap & this, int delta ) with(this) {
866
867    if ( ( uintptr_t )EndVbyte + delta <= ( uintptr_t )ExtVbyte ) {
868        // room available
869        EndVbyte += delta;
870        return 0p;
871    }
872
873    char *oldBytes = StartVbyte;
874
875    NoOfExtensions += 1;
876    CurrSize *= 2;
877    StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize);
878    ExtVbyte = StartVbyte + CurrSize;
879
880    return oldBytes;
881}
882
883
884// Move an existing HandleNode node h somewhere after the current HandleNode node so that it is in ascending order by
885// the address in the byte string area.
886
887static void MoveThisAfter( HandleNode & this, const HandleNode  & h ) with(this) {
888#ifdef VbyteDebug
889    serr | "enter:MoveThisAfter, this:" | & this | " h:" | & h;
890#endif // VbyteDebug
891    verify( h.ulink != 0p );
892    verify( this.ulink == h.ulink );
893    if ( s < h.s ) {                                    // check argument values
894                // serr | "VbyteSM: Error - Cannot move byte string starting at:" | s | " after byte string starting at:"
895                //      | ( h->s ) | " and keep handles in ascending order";
896                // exit(-1 );
897                verify( 0 && "VbyteSM: Error - Cannot move byte strings as requested and keep handles in ascending order");
898    } // if
899
900    HandleNode *i;
901    for ( i = h.flink; i->s != 0 && s > ( i->s ); i = i->flink ); // find the position for this node after h
902    if ( & this != i->blink ) {
903                DeleteNode( this );
904                AddThisAfter( this, *i->blink );
905    } // if
906#ifdef VbyteDebug
907    {
908        serr | "HandleList:";
909        serr | nlOff;
910        for ( HandleNode *n = HeaderPtr->flink; n != HeaderPtr; n = n->flink ) {
911            serr | "\tnode:" | n | " lnth:" | n->lnth | " s:" | (void *)n->s | ",\"";
912            for ( i; n->lnth ) {
913                        serr | n->s[i];
914            } // for
915            serr | "\" flink:" | n->flink | " blink:" | n->blink | nl;
916        } // for
917        serr | nlOn;
918    }
919    serr | "exit:MoveThisAfter";
920#endif // VbyteDebug
921} // MoveThisAfter
922
923
924
925
926
927//######################### VbyteHeap #########################
928
929// Compare two byte strings in the byte-string area. The routine returns the following values:
930//
931// 1 => Src1-byte-string > Src2-byte-string
932// 0 => Src1-byte-string = Src2-byte-string
933// -1 => Src1-byte-string < Src2-byte-string
934
935int ByteCmp( char *Src1, int Src1Start, int Src1Lnth, char *Src2, int Src2Start, int Src2Lnth )  {
936#ifdef VbyteDebug
937    serr | "enter:ByteCmp, Src1Start:" | Src1Start | " Src1Lnth:" | Src1Lnth | " Src2Start:" | Src2Start | " Src2Lnth:" | Src2Lnth;
938#endif // VbyteDebug
939    int cmp;
940
941    CharZip: for ( int i = 0; ; i += 1 ) {
942        if ( i == Src2Lnth - 1 ) {
943            for ( ; ; i += 1 ) {
944                if ( i == Src1Lnth - 1 ) {
945                    cmp = 0;
946                    break CharZip;
947                } // exit
948                if ( Src1[Src1Start + i] != ' ') {
949                        // SUSPECTED BUG:  this could be be why Peter got the bug report about == " "  (why is this case here at all?)
950                    cmp = 1;
951                    break CharZip;
952                } // exit
953            } // for
954        } // exit
955        if ( i == Src1Lnth - 1 ) {
956            for ( ; ; i += 1 ) {
957                if ( i == Src2Lnth - 1 ) {
958                    cmp = 0;
959                    break CharZip;
960                } // exit
961                if ( Src2[Src2Start + i] != ' ') {
962                    cmp = -1;
963                    break CharZip;
964                } // exit
965            } // for
966        } // exit
967      if ( Src2[Src2Start + i] != Src1[Src1Start+ i]) {
968            cmp = Src1[Src1Start + i] > Src2[Src2Start + i] ? 1 : -1;
969            break CharZip;
970        } // exit
971    } // for
972#ifdef VbyteDebug
973    serr | "exit:ByteCmp, cmp:" | cmp;
974#endif // VbyteDebug
975    return cmp;
976} // ByteCmp
977
978
979// The compaction moves all of the byte strings currently in use to the beginning of the byte-string area and modifies
980// the handles to reflect the new positions of the byte strings. Compaction assumes that the handle list is in ascending
981// order by pointers into the byte-string area.  The strings associated with substrings do not have to be moved because
982// the containing string has been moved. Hence, they only require that their string pointers be adjusted.
983
984void compaction(VbyteHeap & this) with(this) {
985    HandleNode *h;
986    char *obase, *nbase, *limit;
987   
988    NoOfCompactions += 1;
989    EndVbyte = StartVbyte;
990    h = Header.flink;                                   // ignore header node
991    for () {
992                memmove( EndVbyte, h->s, h->lnth );
993                obase = h->s;
994                h->s = EndVbyte;
995                nbase = h->s;
996                EndVbyte += h->lnth;
997                limit = obase + h->lnth;
998                h = h->flink;
999               
1000                // check if any substrings are allocated within a string
1001               
1002                for () {
1003                        if ( h == &Header ) break;                      // end of header list ?
1004                        if ( h->s >= limit ) break;                     // outside of current string ?
1005                        h->s = nbase + (( uintptr_t )h->s - ( uintptr_t )obase );
1006                        h = h->flink;
1007                } // for
1008                if ( h == &Header ) break;                      // end of header list ?
1009    } // for
1010} // compaction
1011
1012
1013static double heap_expansion_freespace_threshold = 0.1;  // default inherited from prior work: expand heap when less than 10% "free" (i.e. garbage)
1014                                                         // probably an unreasonable default, but need to assess early-round tests on changing it
1015
1016void TUNING_set_string_heap_liveness_threshold( double val ) {
1017    heap_expansion_freespace_threshold = 1.0 - val;
1018}
1019
1020
1021// Garbage determines the amount of free space left in the heap and then reduces, leave the same, or extends the size of
1022// the heap.  The heap is then compacted in the existing heap or into the newly allocated heap.
1023
1024void garbage(VbyteHeap & this, int minreq ) with(this) {
1025#ifdef VbyteDebug
1026    serr | "enter:garbage";
1027    {
1028                serr | "HandleList:";
1029                for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) {
1030                        serr | nlOff;
1031                        serr | "\tnode:" | n | " lnth:" | n->lnth | " s:" | (void *)n->s | ",\"";
1032                        for ( i; n->lnth ) {
1033                                serr | n->s[i];
1034                        } // for
1035                        serr | nlOn;
1036                        serr | "\" flink:" | n->flink | " blink:" | n->blink;
1037                } // for
1038    }
1039#endif // VbyteDebug
1040    int AmountUsed, AmountFree;
1041
1042    AmountUsed = 0;
1043    for ( HandleNode *i = Header.flink; i != &Header; i = i->flink ) { // calculate amount of byte area used
1044                AmountUsed += i->lnth;
1045    } // for
1046    AmountFree = ( uintptr_t )ExtVbyte - ( uintptr_t )StartVbyte - AmountUsed;
1047   
1048    if ( ( double ) AmountFree < ( CurrSize * heap_expansion_freespace_threshold ) || AmountFree < minreq ) {   // free space less than threshold or not enough to serve cur request
1049
1050                extend( this, max( CurrSize, minreq ) );                                // extend the heap
1051
1052                        //  Peter says, "This needs work before it should be used."
1053                        //  } else if ( AmountFree > CurrSize / 2 ) {           // free space greater than 3 times the initial allocation ?
1054                        //              reduce(( AmountFree / CurrSize - 3 ) * CurrSize ); // reduce the memory
1055
1056        // `extend` implies a `compaction` during the copy
1057
1058    } else {
1059        compaction(this);                                       // in-place
1060    }// if
1061#ifdef VbyteDebug
1062    {
1063                serr | "HandleList:";
1064                for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) {
1065                        serr | nlOff;
1066                        serr | "\tnode:" | n | " lnth:" | n->lnth | " s:" | (void *)n->s | ",\"";
1067                        for ( i; n->lnth ) {
1068                                serr | n->s[i];
1069                        } // for
1070                        serr | nlOn;
1071                        serr | "\" flink:" | n->flink | " blink:" | n->blink;
1072                } // for
1073    }
1074    serr | "exit:garbage";
1075#endif // VbyteDebug
1076} // garbage
1077
1078#undef VbyteDebug
1079
1080
1081
1082// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string
1083// area is deleted.
1084
1085void extend( VbyteHeap & this, int size ) with (this) {
1086#ifdef VbyteDebug
1087    serr | "enter:extend, size:" | size;
1088#endif // VbyteDebug
1089    char *OldStartVbyte;
1090
1091    NoOfExtensions += 1;
1092    OldStartVbyte = StartVbyte;                         // save previous byte area
1093   
1094    CurrSize += size > InitSize ? size : InitSize;      // minimum extension, initial size
1095    StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize);
1096    ExtVbyte = (void *)( StartVbyte + CurrSize );
1097    compaction(this);                                   // copy from old heap to new & adjust pointers to new heap
1098    free( OldStartVbyte );                              // release old heap
1099#ifdef VbyteDebug
1100    serr | "exit:extend, CurrSize:" | CurrSize;
1101#endif // VbyteDebug
1102} // extend
1103
1104//WIP
1105#if 0
1106
1107// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string
1108// area is deleted.
1109
1110void VbyteHeap::reduce( int size ) {
1111#ifdef VbyteDebug
1112    serr | "enter:reduce, size:" | size;
1113#endif // VbyteDebug
1114    char *OldStartVbyte;
1115
1116    NoOfReductions += 1;
1117    OldStartVbyte = StartVbyte;                         // save previous byte area
1118   
1119    CurrSize -= size;
1120    StartVbyte = EndVbyte = new char[CurrSize];
1121    ExtVbyte = (void *)( StartVbyte + CurrSize );
1122    compaction();                                       // copy from old heap to new & adjust pointers to new heap
1123    delete  OldStartVbyte;                              // release old heap
1124#ifdef VbyteDebug
1125    serr | "exit:reduce, CurrSize:" | CurrSize;
1126#endif // VbyteDebug
1127} // reduce
1128
1129
1130#endif
Note: See TracBrowser for help on using the repository browser.