source: libcfa/src/containers/string_res.cfa @ 1733184

enumpthread-emulation
Last change on this file since 1733184 was 1733184, checked in by Michael Brooks <mlbrooks@…>, 9 months ago

Fixing LL API not allowing simple assignment.
Removing accidentally commited performance regression of attribute-no-inline.

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