source: libcfa/src/containers/string_res.cfa @ 857081e

ADTast-experimental
Last change on this file since 857081e was 08ed947, checked in by Michael Brooks <mlbrooks@…>, 3 years ago

Roll up of string changes for performance testing/improvement, and a couple API features supporting them.

String API changes:
Defining a tuning knob to control the heap growth policy (relapaces former 10% hardcode, downgraded to a default)
Implementing findFrom (allowing find-non-first); leaving find as find-first.

String implementation perf improvements:
Calling C-malloc directly instead of via CFA-alloc.
Replacings loops that copy with memmove calls.
Replacings loops that search for a value with memchr calls.

String perf testing realized:
Makefile supporting several prog-*.cfa, chosen by OPERATION value (implies prog.cfa changes to support the adjusted protocol)
Adjusting the starter/accumulater declarations in PEQ and PTA to behave consistently in cfa v cpp.
Adding tests: allocation, find, normalize, pass-by-val, pass-by-x.
Adding helper shell scripts for: generating flame graphs, collecting/crunching allocation stats using Mubeen's malloc wrappers

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