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

Last change on this file since d8d512e was d8d512e, checked in by Michael Brooks <mlbrooks@…>, 3 months ago

Reorganizing string constructor/assignment overload calls for better performance.

  • Property mode set to 100644
File size: 28.2 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 <stdlib.hfa>  // e.g. malloc
18#include <string.h>    // e.g. strlen
19
20//######################### VbyteHeap "header" #########################
21
22
23#ifdef VbyteDebug
24extern HandleNode *HeaderPtr;
25#endif // VbyteDebug
26
27struct VbyteHeap {
28
29    int NoOfCompactions;                                // number of compactions of the byte area
30    int NoOfExtensions;                                 // number of extensions in the size of the byte area
31    int NoOfReductions;                                 // number of reductions in the size of the byte area
32   
33    int InitSize;                                       // initial number of bytes in the byte-string area
34    int CurrSize;                                       // current number of bytes in the byte-string area
35    char *StartVbyte;                                   // pointer to the `st byte of the start of the byte-string area
36    char *EndVbyte;                                     // pointer to the next byte after the end of the currently used portion of byte-string area
37    void *ExtVbyte;                                     // pointer to the next byte after the end of the byte-string area
38
39    HandleNode Header;                                  // header node for handle list
40}; // VbyteHeap
41
42   
43static inline void compaction( VbyteHeap & );                           // compaction of the byte area
44static inline void garbage( VbyteHeap & );                              // garbage collect the byte area
45static inline void extend( VbyteHeap &, int );                  // extend the size of the byte area
46static inline void reduce( VbyteHeap &, int );                  // reduce the size of the byte area
47
48static inline void ?{}( VbyteHeap &, int = 1000 );
49static inline void ^?{}( VbyteHeap & );
50static inline void ByteCopy( VbyteHeap &, char *, int, int, char *, int, int ); // copy a block of bytes from one location in the heap to another
51static inline int ByteCmp( VbyteHeap &, char *, int, int, char *, int, int );   // compare 2 blocks of bytes
52static inline char *VbyteAlloc( VbyteHeap &, int );                     // allocate a block bytes in the heap
53
54
55static inline void AddThisAfter( HandleNode &, HandleNode & );
56static inline void DeleteNode( HandleNode & );
57static inline void MoveThisAfter( HandleNode &, const HandleNode & );           // move current handle after parameter handle
58
59
60// Allocate the storage for the variable sized area and intialize the heap variables.
61
62static inline void ?{}( VbyteHeap & this, int Size ) with(this) {
63#ifdef VbyteDebug
64    serr | "enter:VbyteHeap::VbyteHeap, this:" | &this | " Size:" | Size;
65#endif // VbyteDebug
66    NoOfCompactions = NoOfExtensions = NoOfReductions = 0;
67    InitSize = CurrSize = Size;
68    StartVbyte = EndVbyte = alloc(CurrSize);
69    ExtVbyte = (void *)( StartVbyte + CurrSize );
70    Header.flink = Header.blink = &Header;
71#ifdef VbyteDebug
72    HeaderPtr = &Header;
73    serr | "exit:VbyteHeap::VbyteHeap, this:" | &this;
74#endif // VbyteDebug
75} // VbyteHeap
76
77
78// Release the dynamically allocated storage for the byte area.
79
80static inline void ^?{}( VbyteHeap & this ) with(this) {
81    free( StartVbyte );
82} // ~VbyteHeap
83
84
85//######################### HandleNode #########################
86
87
88// Create a handle node. The handle is not linked into the handle list.  This is the responsibilitiy of the handle
89// creator.
90
91void ?{}( HandleNode & this ) with(this) {
92#ifdef VbyteDebug
93    serr | "enter:HandleNode::HandleNode, this:" | &this;
94#endif // VbyteDebug
95    s = 0;
96    lnth = 0;
97#ifdef VbyteDebug
98    serr | "exit:HandleNode::HandleNode, this:" | &this;
99#endif // VbyteDebug
100} // HandleNode
101
102// Create a handle node. The handle is linked into the handle list at the end. This means that this handle will NOT be
103// in order by string address, but this is not a problem because a string with length zero does nothing during garbage
104// collection.
105
106void ?{}( HandleNode & this, VbyteHeap & vh ) with(this) {
107#ifdef VbyteDebug
108    serr | "enter:HandleNode::HandleNode, this:" | &this;
109#endif // VbyteDebug
110    s = 0;
111    lnth = 0;
112    AddThisAfter( this, *vh.Header.blink );
113#ifdef VbyteDebug
114    serr | "exit:HandleNode::HandleNode, this:" | &this;
115#endif // VbyteDebug
116} // HandleNode
117
118
119// Delete a node from the handle list by unchaining it from the list. If the handle node was allocated dynamically, it
120// is the responsibility of the creator to destroy it.
121
122void ^?{}( HandleNode & this ) with(this) {
123#ifdef VbyteDebug
124    serr | "enter:HandleNode::~HandleNode, this:" | & this;
125    {
126        serr | nlOff;
127        serr | " lnth:" | lnth | " s:" | (void *)s | ",\"";
128        for ( int i = 0; i < lnth; i += 1 ) {
129            serr | s[i];
130        } // for
131        serr | "\" flink:" | flink | " blink:" | blink | nl;
132        serr | nlOn;
133    }
134#endif // VbyteDebug
135    DeleteNode( this );
136} // ~HandleNode
137
138//######################### String Resource #########################
139
140
141VbyteHeap HeapArea;
142
143// Returns the size of the string in bytes
144size_t size(const string_res &s) with(s) {
145    return Handle.lnth;
146}
147
148// Output operator
149ofstream & ?|?(ofstream &out, const string_res &s) {
150    // Store auto-newline state so it can be restored
151    bool anl = getANL$(out);
152    nlOff(out);
153    for (size_t i = 0; i < s.Handle.lnth; i++) {
154        out | s[i];
155    }
156    out | sep;
157    // Re-apply newlines after done, for chaining version
158    if (anl) nlOn(out);
159    return out;
160}
161
162void ?|?(ofstream &out, const string_res &s) {
163    // Store auto-newline state so it can be restored
164    bool anl = getANL$(out);
165    nlOff(out);
166    for (size_t i = 0; i < s.Handle.lnth; i++) {
167        // Need to re-apply on the last output operator, for whole-statement version
168        if (anl && i == s.Handle.lnth-1) nlOn(out);
169        out | s[i];
170    }
171    return out;
172}
173
174// Empty constructor
175void ?{}(string_res &s) with(s) {
176    (Handle){ HeapArea };
177    s.shareEditSet_prev = &s;
178    s.shareEditSet_next = &s;
179}
180
181// Constructor from a raw buffer and size
182void ?{}(string_res &s, const char* rhs, size_t rhslnth) with(s) {
183    (Handle){ HeapArea };
184    Handle.s = VbyteAlloc(HeapArea, rhslnth);
185    Handle.lnth = rhslnth;
186    for ( int i = 0; i < rhslnth; i += 1 ) {            // copy characters
187        Handle.s[i] = rhs[i];
188    } // for
189    s.shareEditSet_prev = &s;
190    s.shareEditSet_next = &s;
191}
192
193// String literal constructor
194void ?{}(string_res &s, const char* rhs) {
195    (s){ rhs, strlen(rhs) };
196}
197
198// General copy constructor
199void ?{}(string_res &s, const string_res & s2, StrResInitMode mode, size_t start, size_t end ) {
200
201    (s.Handle){ HeapArea };
202    s.Handle.s = s2.Handle.s + start;
203    s.Handle.lnth = end - start;
204    MoveThisAfter(s.Handle, s2.Handle );                        // insert this handle after rhs handle
205    // ^ bug?  skip others at early point in string
206   
207    if (mode == COPY_VALUE) {
208        // make s alone in its shareEditSet
209        s.shareEditSet_prev = &s;
210        s.shareEditSet_next = &s;
211    } else {
212        assert( mode == SHARE_EDITS );
213
214        // s2 is logically const but not implementation const
215        string_res & s2mod = (string_res &) s2;
216
217        // insert s after s2 on shareEditSet
218        s.shareEditSet_next = s2mod.shareEditSet_next;
219        s.shareEditSet_prev = &s2mod;
220        s.shareEditSet_next->shareEditSet_prev = &s;
221        s.shareEditSet_prev->shareEditSet_next = &s;
222    }
223}
224
225void assign(string_res &this, const char* buffer, size_t bsize) {
226
227    char * afterBegin = this.Handle.s + this.Handle.lnth;
228
229    char * shareEditSetStart = this.Handle.s;
230    char * shareEditSetEnd = afterBegin;
231    for (string_res * editPeer = this.shareEditSet_next; editPeer != &this; editPeer = editPeer->shareEditSet_next) {
232        shareEditSetStart = min( shareEditSetStart, editPeer->Handle.s );
233        shareEditSetEnd = max( shareEditSetStart, editPeer->Handle.s + editPeer->Handle.lnth);
234    }
235
236    char * beforeBegin = shareEditSetStart;
237    size_t beforeLen = this.Handle.s - shareEditSetStart;
238    size_t afterLen = shareEditSetEnd - afterBegin;
239
240    string_res pasting = { beforeBegin, beforeLen };
241    append(pasting, buffer, bsize);
242    string_res after = { afterBegin, afterLen }; // juxtaposed with in-progress pasting
243    pasting += after;                        // optimized case
244
245    size_t oldLnth = this.Handle.lnth;
246
247    this.Handle.s = pasting.Handle.s + beforeLen;
248    this.Handle.lnth = bsize;
249    MoveThisAfter( this.Handle, pasting.Handle );
250
251    // adjust all substring string and handle locations, and check if any substring strings are outside the new base string
252    char *limit = pasting.Handle.s + pasting.Handle.lnth;
253    for (string_res * p = this.shareEditSet_next; p != &this; p = p->shareEditSet_next) {
254        assert (p->Handle.s >= beforeBegin);
255        if ( p->Handle.s < beforeBegin + beforeLen ) {
256            // p starts before the edit
257            if ( p->Handle.s + p->Handle.lnth < beforeBegin + beforeLen ) {
258                // p ends before the edit
259                // take end as start-anchored too
260                // p->Handle.lnth unaffected
261            } else if ( p->Handle.s + p->Handle.lnth < afterBegin ) {
262                // p ends during the edit
263                // clip end of p to end at start of edit
264                p->Handle.lnth = beforeLen - ( p->Handle.s - beforeBegin );
265            } else {
266                // p ends after the edit
267                assert ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen );
268                // take end as end-anchored
269                // stretch-shrink p according to the edit
270                p->Handle.lnth += this.Handle.lnth;
271                p->Handle.lnth -= oldLnth;
272            }
273            // take start as start-anchored
274            size_t startOffsetFromStart = p->Handle.s - beforeBegin;
275            p->Handle.s = pasting.Handle.s + startOffsetFromStart;
276        } else if ( p->Handle.s < afterBegin ) {
277            // p starts during the edit
278            assert( p->Handle.s + p->Handle.lnth >= beforeBegin + beforeLen );
279            if ( p->Handle.s + p->Handle.lnth < afterBegin ) {
280                // p ends during the edit
281                // set p to empty string at start of edit
282                p->Handle.s = this.Handle.s;
283                p->Handle.lnth = 0;
284            } else {
285                // p ends after the edit
286                // clip start of p to start at end of edit
287                p->Handle.s = this.Handle.s + this.Handle.lnth;
288                p->Handle.lnth += this.Handle.lnth;
289                p->Handle.lnth -= oldLnth;
290            }
291        } else {
292            assert ( p->Handle.s <= afterBegin + afterLen );
293            assert ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen );
294            // p starts after the edit
295            // take start and end as end-anchored
296            size_t startOffsetFromEnd = afterBegin + afterLen - p->Handle.s;
297            p->Handle.s = limit - startOffsetFromEnd;
298            // p->Handle.lnth unaffected
299        }
300        MoveThisAfter( p->Handle, pasting.Handle );     // move substring handle to maintain sorted order by string position
301    }
302}
303
304void ?=?(string_res &s, const char* other) {
305    assign(s, other, strlen(other));
306}
307
308void ?=?(string_res &s, char other) {
309    assign(s, &other, 1);
310}
311
312// Copy assignment operator
313void ?=?(string_res & this, const string_res & rhs) with( this ) {
314    assign(this, rhs.Handle.s, rhs.Handle.lnth);
315}
316
317void ?=?(string_res & this, string_res & rhs) with( this ) {
318    const string_res & rhs2 = rhs;
319    this = rhs2;
320}
321
322
323// Destructor
324void ^?{}(string_res &s) with(s) {
325    // much delegated to implied ^VbyteSM
326
327    // sever s from its share-edit peers, if any (four no-ops when already solo)
328    s.shareEditSet_prev->shareEditSet_next = s.shareEditSet_next;
329    s.shareEditSet_next->shareEditSet_prev = s.shareEditSet_prev;
330    s.shareEditSet_next = &s;
331    s.shareEditSet_prev = &s;
332}
333
334
335// Returns the character at the given index
336// With unicode support, this may be different from just the byte at the given
337// offset from the start of the string.
338char ?[?](const string_res &s, size_t index) with(s) {
339    //TODO: Check if index is valid (no exceptions yet)
340    return Handle.s[index];
341}
342
343
344///////////////////////////////////////////////////////////////////
345// Concatenation
346
347void append(string_res &str1, const char * buffer, size_t bsize) {
348    size_t clnth = size(str1) + bsize;
349    if ( str1.Handle.s + size(str1) == buffer ) { // already juxtapose ?
350        // no-op
351    } else {                                            // must copy some text
352        if ( str1.Handle.s + size(str1) == VbyteAlloc(HeapArea, 0) ) { // str1 at end of string area ?
353            VbyteAlloc(HeapArea, bsize); // create room for 2nd part at the end of string area
354        } else {                                        // copy the two parts
355            char * str1oldBuf = str1.Handle.s;
356            str1.Handle.s = VbyteAlloc( HeapArea, clnth );
357            ByteCopy( HeapArea, str1.Handle.s, 0, str1.Handle.lnth, str1oldBuf, 0, str1.Handle.lnth);
358        } // if
359        ByteCopy( HeapArea, str1.Handle.s, str1.Handle.lnth, bsize, (char*)buffer, 0, (int)bsize);
360        //       VbyteHeap & this, char *Dst, int DstStart, int DstLnth, char *Src, int SrcStart, int SrcLnth
361    } // if
362    str1.Handle.lnth = clnth;
363}
364
365void ?+=?(string_res &str1, const string_res &str2) {
366    append( str1, str2.Handle.s, str2.Handle.lnth );
367}
368
369void ?+=?(string_res &s, char other) {
370    append( s, &other, 1 );
371}
372
373void ?+=?(string_res &s, const char* other) {
374    append( s, other, strlen(other) );
375}
376
377
378
379
380//////////////////////////////////////////////////////////
381// Comparisons
382
383
384bool ?==?(const string_res &s1, const string_res &s2) {
385    return ByteCmp( HeapArea, s1.Handle.s, 0, s1.Handle.lnth, s2.Handle.s, 0, s2.Handle.lnth) == 0;
386}
387
388bool ?!=?(const string_res &s1, const string_res &s2) {
389    return !(s1 == s2);
390}
391bool ?==?(const string_res &s, const char* other) {
392    string_res sother = other;
393    return s == sother;
394}
395bool ?!=?(const string_res &s, const char* other) {
396    return !(s == other);
397}
398
399
400//////////////////////////////////////////////////////////
401// Search
402
403bool contains(const string_res &s, char ch) {
404    for (i; size(s)) {
405        if (s[i] == ch) return true;
406    }
407    return false;
408}
409
410int find(const string_res &s, char search) {
411    for (i; size(s)) {
412        if (s[i] == search) return i;
413    }
414    return size(s);
415}
416
417    /* Remaining implementations essentially ported from Sunjay's work */
418
419int find(const string_res &s, const string_res &search) {
420    return find(s, search.Handle.s, search.Handle.lnth);
421}
422
423int find(const string_res &s, const char* search) {
424    return find(s, search, strlen(search));
425}
426
427int find(const string_res &s, const char* search, size_t searchsize) {
428    // FIXME: This is a naive algorithm. We probably want to switch to someting
429    // like Boyer-Moore in the future.
430    // https://en.wikipedia.org/wiki/String_searching_algorithm
431
432    // Always find the empty string
433    if (searchsize == 0) {
434        return 0;
435    }
436
437    for (size_t i = 0; i < s.Handle.lnth; i++) {
438        size_t remaining = s.Handle.lnth - i;
439        // Never going to find the search string if the remaining string is
440        // smaller than search
441        if (remaining < searchsize) {
442            break;
443        }
444
445        bool matched = true;
446        for (size_t j = 0; j < searchsize; j++) {
447            if (search[j] != s.Handle.s[i + j]) {
448                matched = false;
449                break;
450            }
451        }
452        if (matched) {
453            return i;
454        }
455    }
456
457    return s.Handle.lnth;
458}
459
460bool includes(const string_res &s, const string_res &search) {
461    return includes(s, search.Handle.s, search.Handle.lnth);
462}
463
464bool includes(const string_res &s, const char* search) {
465    return includes(s, search, strlen(search));
466}
467
468bool includes(const string_res &s, const char* search, size_t searchsize) {
469    return find(s, search, searchsize) < s.Handle.lnth;
470}
471
472bool startsWith(const string_res &s, const string_res &prefix) {
473    return startsWith(s, prefix.Handle.s, prefix.Handle.lnth);
474}
475
476bool startsWith(const string_res &s, const char* prefix) {
477    return startsWith(s, prefix, strlen(prefix));
478}
479
480bool startsWith(const string_res &s, const char* prefix, size_t prefixsize) {
481    if (s.Handle.lnth < prefixsize) {
482        return false;
483    }
484    return memcmp(s.Handle.s, prefix, prefixsize) == 0;
485}
486
487bool endsWith(const string_res &s, const string_res &suffix) {
488    return endsWith(s, suffix.Handle.s, suffix.Handle.lnth);
489}
490
491bool endsWith(const string_res &s, const char* suffix) {
492    return endsWith(s, suffix, strlen(suffix));
493}
494
495bool endsWith(const string_res &s, const char* suffix, size_t suffixsize) {
496    if (s.Handle.lnth < suffixsize) {
497        return false;
498    }
499    // Amount to offset the bytes pointer so that we are comparing the end of s
500    // to suffix. s.bytes + offset should be the first byte to compare against suffix
501    size_t offset = s.Handle.lnth - suffixsize;
502    return memcmp(s.Handle.s + offset, suffix, suffixsize) == 0;
503}
504
505    /* Back to Mike's work */
506
507
508///////////////////////////////////////////////////////////////////////////
509// charclass, include, exclude
510
511void ?{}( charclass_res & this, const string_res & chars) {
512    (this){ chars.Handle.s, chars.Handle.lnth };
513}
514
515void ?{}( charclass_res & this, const char * chars ) {
516    (this){ chars, strlen(chars) };
517}
518
519void ?{}( charclass_res & this, const char * chars, size_t charssize ) {
520    (this.chars){ chars, charssize };
521    // now sort it ?
522}
523
524void ^?{}( charclass_res & this ) {
525    ^(this.chars){};
526}
527
528static bool test( const charclass_res & mask, char c ) {
529    // instead, use sorted char list?
530    return contains( mask.chars, c );
531}
532
533int exclude(const string_res &s, const charclass_res &mask) {
534    for (int i = 0; i < size(s); i++) {
535        if ( test(mask, s[i]) ) return i;
536    }
537    return size(s);
538}
539
540int include(const string_res &s, const charclass_res &mask) {
541    for (int i = 0; i < size(s); i++) {
542        if ( ! test(mask, s[i]) ) return i;
543    }
544    return size(s);
545}
546
547//######################### VbyteHeap "implementation" #########################
548
549
550// Add a new HandleNode node n after the current HandleNode node.
551
552static inline void AddThisAfter( HandleNode & this, HandleNode & n ) with(this) {
553#ifdef VbyteDebug
554    serr | "enter:AddThisAfter, this:" | &this | " n:" | &n;
555#endif // VbyteDebug
556    flink = n.flink;
557    blink = &n;
558    n.flink->blink = &this;
559    n.flink = &this;
560#ifdef VbyteDebug
561    {
562                serr | "HandleList:";
563                serr | nlOff;
564                for ( HandleNode *ni = HeaderPtr->flink; ni != HeaderPtr; ni = ni->flink ) {
565                        serr | "\tnode:" | ni | " lnth:" | ni->lnth | " s:" | (void *)ni->s | ",\"";
566                        for ( int i = 0; i < ni->lnth; i += 1 ) {
567                                serr | ni->s[i];
568                        } // for
569                        serr | "\" flink:" | ni->flink | " blink:" | ni->blink | nl;
570                } // for
571                serr | nlOn;
572    }
573    serr | "exit:AddThisAfter";
574#endif // VbyteDebug
575} // AddThisAfter
576
577
578// Delete the current HandleNode node.
579
580static inline void DeleteNode( HandleNode & this ) with(this) {
581#ifdef VbyteDebug
582    serr | "enter:DeleteNode, this:" | &this;
583#endif // VbyteDebug
584    flink->blink = blink;
585    blink->flink = flink;
586#ifdef VbyteDebug
587    serr | "exit:DeleteNode";
588#endif // VbyteDebug
589} //  DeleteNode
590
591
592
593// Allocates specified storage for a string from byte-string area. If not enough space remains to perform the
594// allocation, the garbage collection routine is called and a second attempt is made to allocate the space. If the
595// second attempt fails, a further attempt is made to create a new, larger byte-string area.
596
597static inline char * VbyteAlloc( VbyteHeap & this, int size ) with(this) {
598#ifdef VbyteDebug
599    serr | "enter:VbyteAlloc, size:" | size;
600#endif // VbyteDebug
601    uintptr_t NoBytes;
602    char *r;
603
604    NoBytes = ( uintptr_t )EndVbyte + size;
605    if ( NoBytes > ( uintptr_t )ExtVbyte ) {            // enough room for new byte-string ?
606                garbage( this );                                        // firer up the garbage collector
607                NoBytes = ( uintptr_t )EndVbyte + size;         // try again
608                if ( NoBytes > ( uintptr_t )ExtVbyte ) {        // enough room for new byte-string ?
609assert( 0 && "need to implement actual growth" );
610                        // extend( size );                              // extend the byte-string area
611                } // if
612    } // if
613    r = EndVbyte;
614    EndVbyte += size;
615#ifdef VbyteDebug
616    serr | "exit:VbyteAlloc, r:" | (void *)r | " EndVbyte:" | (void *)EndVbyte | " ExtVbyte:" | ExtVbyte;
617#endif // VbyteDebug
618    return r;
619} // VbyteAlloc
620
621
622// Move an existing HandleNode node h somewhere after the current HandleNode node so that it is in ascending order by
623// the address in the byte string area.
624
625static inline void MoveThisAfter( HandleNode & this, const HandleNode  & h ) with(this) {
626#ifdef VbyteDebug
627    serr | "enter:MoveThisAfter, this:" | & this | " h:" | & h;
628#endif // VbyteDebug
629    if ( s < h.s ) {                                    // check argument values
630                // serr | "VbyteSM: Error - Cannot move byte string starting at:" | s | " after byte string starting at:"
631                //      | ( h->s ) | " and keep handles in ascending order";
632                // exit(-1 );
633                assert( 0 && "VbyteSM: Error - Cannot move byte strings as requested and keep handles in ascending order");
634    } // if
635
636    HandleNode *i;
637    for ( i = h.flink; i->s != 0 && s > ( i->s ); i = i->flink ); // find the position for this node after h
638    if ( & this != i->blink ) {
639                DeleteNode( this );
640                AddThisAfter( this, *i->blink );
641    } // if
642#ifdef VbyteDebug
643    serr | "exit:MoveThisAfter";
644    {
645        serr | "HandleList:";
646        serr | nlOff;
647        for ( HandleNode *n = HeaderPtr->flink; n != HeaderPtr; n = n->flink ) {
648            serr | "\tnode:" | n | " lnth:" | n->lnth | " s:" | (void *)n->s | ",\"";
649            for ( int i = 0; i < n->lnth; i += 1 ) {
650                serr | n->s[i];
651            } // for
652            serr | "\" flink:" | n->flink | " blink:" | n->blink;
653        } // for
654        serr | nlOn;
655    }
656#endif // VbyteDebug
657} // MoveThisAfter
658
659
660
661
662
663//######################### VbyteHeap #########################
664
665#ifdef VbyteDebug
666HandleNode *HeaderPtr = 0p;
667#endif // VbyteDebug
668
669// Move characters from one location in the byte-string area to another. The routine handles the following situations:
670//
671// if the |Src| > |Dst| => truncate
672// if the |Dst| > |Src| => pad Dst with blanks
673
674void ByteCopy( VbyteHeap & this, char *Dst, int DstStart, int DstLnth, char *Src, int SrcStart, int SrcLnth ) {
675    for ( int i = 0; i < DstLnth; i += 1 ) {
676      if ( i == SrcLnth ) {                             // |Dst| > |Src|
677            for ( ; i < DstLnth; i += 1 ) {             // pad Dst with blanks
678                Dst[DstStart + i] = ' ';
679            } // for
680            break;
681        } // exit
682        Dst[DstStart + i] = Src[SrcStart + i];
683    } // for
684} // ByteCopy
685
686// Compare two byte strings in the byte-string area. The routine returns the following values:
687//
688// 1 => Src1-byte-string > Src2-byte-string
689// 0 => Src1-byte-string = Src2-byte-string
690// -1 => Src1-byte-string < Src2-byte-string
691
692int ByteCmp( VbyteHeap & this, char *Src1, int Src1Start, int Src1Lnth, char *Src2, int Src2Start, int Src2Lnth )  with(this) {
693#ifdef VbyteDebug
694    serr | "enter:ByteCmp, Src1Start:" | Src1Start | " Src1Lnth:" | Src1Lnth | " Src2Start:" | Src2Start | " Src2Lnth:" | Src2Lnth;
695#endif // VbyteDebug
696    int cmp;
697
698    CharZip: for ( int i = 0; ; i += 1 ) {
699        if ( i == Src2Lnth - 1 ) {
700            for ( ; ; i += 1 ) {
701                if ( i == Src1Lnth - 1 ) {
702                    cmp = 0;
703                    break CharZip;
704                } // exit
705                if ( Src1[Src1Start + i] != ' ') {
706                        // SUSPECTED BUG:  this could be be why Peter got the bug report about == " "  (why is this case here at all?)
707                    cmp = 1;
708                    break CharZip;
709                } // exit
710            } // for
711        } // exit
712        if ( i == Src1Lnth - 1 ) {
713            for ( ; ; i += 1 ) {
714                if ( i == Src2Lnth - 1 ) {
715                    cmp = 0;
716                    break CharZip;
717                } // exit
718                if ( Src2[Src2Start + i] != ' ') {
719                    cmp = -1;
720                    break CharZip;
721                } // exit
722            } // for
723        } // exit
724      if ( Src2[Src2Start + i] != Src1[Src1Start+ i]) {
725            cmp = Src1[Src1Start + i] > Src2[Src2Start + i] ? 1 : -1;
726            break CharZip;
727        } // exit
728    } // for
729#ifdef VbyteDebug
730    serr | "exit:ByteCmp, cmp:" | cmp;
731#endif // VbyteDebug
732    return cmp;
733} // ByteCmp
734
735
736// The compaction moves all of the byte strings currently in use to the beginning of the byte-string area and modifies
737// the handles to reflect the new positions of the byte strings. Compaction assumes that the handle list is in ascending
738// order by pointers into the byte-string area.  The strings associated with substrings do not have to be moved because
739// the containing string has been moved. Hence, they only require that their string pointers be adjusted.
740
741void compaction(VbyteHeap & this) with(this) {
742    HandleNode *h;
743    char *obase, *nbase, *limit;
744   
745    NoOfCompactions += 1;
746    EndVbyte = StartVbyte;
747    h = Header.flink;                                   // ignore header node
748    for (;;) {
749                ByteCopy( this, EndVbyte, 0, h->lnth, h->s, 0, h->lnth );
750                obase = h->s;
751                h->s = EndVbyte;
752                nbase = h->s;
753                EndVbyte += h->lnth;
754                limit = obase + h->lnth;
755                h = h->flink;
756               
757                // check if any substrings are allocated within a string
758               
759                for (;;) {
760                        if ( h == &Header ) break;                      // end of header list ?
761                        if ( h->s >= limit ) break;                     // outside of current string ?
762                        h->s = nbase + (( uintptr_t )h->s - ( uintptr_t )obase );
763                        h = h->flink;
764                } // for
765                if ( h == &Header ) break;                      // end of header list ?
766    } // for
767} // compaction
768
769
770// Garbage determines the amount of free space left in the heap and then reduces, leave the same, or extends the size of
771// the heap.  The heap is then compacted in the existing heap or into the newly allocated heap.
772
773void garbage(VbyteHeap & this ) with(this) {
774#ifdef VbyteDebug
775    serr | "enter:garbage";
776    {
777                serr | "HandleList:";
778                for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) {
779                        serr | nlOff;
780                        serr | "\tnode:" | n | " lnth:" | n->lnth | " s:" | (void *)n->s | ",\"";
781                        for ( int i = 0; i < n->lnth; i += 1 ) {
782                                serr | n->s[i];
783                        } // for
784                        serr | nlOn;
785                        serr | "\" flink:" | n->flink | " blink:" | n->blink;
786                } // for
787    }
788#endif // VbyteDebug
789    int AmountUsed, AmountFree;
790
791    AmountUsed = 0;
792    for ( HandleNode *i = Header.flink; i != &Header; i = i->flink ) { // calculate amount of byte area used
793                AmountUsed += i->lnth;
794    } // for
795    AmountFree = ( uintptr_t )ExtVbyte - ( uintptr_t )StartVbyte - AmountUsed;
796   
797    if ( AmountFree < ( int )( CurrSize * 0.1 )) {      // free space less than 10% ?
798
799assert( 0 && "need to implement actual growth" );
800//              extend( CurrSize );                             // extend the heap
801
802                        //  Peter says, "This needs work before it should be used."
803                        //  } else if ( AmountFree > CurrSize / 2 ) {           // free space greater than 3 times the initial allocation ?
804                        //              reduce(( AmountFree / CurrSize - 3 ) * CurrSize ); // reduce the memory
805
806    } // if
807    compaction(this);                                   // compact the byte area, in the same or new heap area
808#ifdef VbyteDebug
809    {
810                serr | "HandleList:";
811                for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) {
812                        serr | nlOff;
813                        serr | "\tnode:" | n | " lnth:" | n->lnth | " s:" | (void *)n->s | ",\"";
814                        for ( int i = 0; i < n->lnth; i += 1 ) {
815                                serr | n->s[i];
816                        } // for
817                        serr | nlOn;
818                        serr | "\" flink:" | n->flink | " blink:" | n->blink;
819                } // for
820    }
821    serr | "exit:garbage";
822#endif // VbyteDebug
823} // garbage
824
825#undef VbyteDebug
826
827//WIP
828#if 0
829
830
831// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string
832// area is deleted.
833
834void VbyteHeap::extend( int size ) {
835#ifdef VbyteDebug
836    serr | "enter:extend, size:" | size;
837#endif // VbyteDebug
838    char *OldStartVbyte;
839
840    NoOfExtensions += 1;
841    OldStartVbyte = StartVbyte;                         // save previous byte area
842   
843    CurrSize += size > InitSize ? size : InitSize;      // minimum extension, initial size
844    StartVbyte = EndVbyte = new char[CurrSize];
845    ExtVbyte = (void *)( StartVbyte + CurrSize );
846    compaction();                                       // copy from old heap to new & adjust pointers to new heap
847    delete OldStartVbyte;                               // release old heap
848#ifdef VbyteDebug
849    serr | "exit:extend, CurrSize:" | CurrSize;
850#endif // VbyteDebug
851} // extend
852
853
854// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string
855// area is deleted.
856
857void VbyteHeap::reduce( int size ) {
858#ifdef VbyteDebug
859    serr | "enter:reduce, size:" | size;
860#endif // VbyteDebug
861    char *OldStartVbyte;
862
863    NoOfReductions += 1;
864    OldStartVbyte = StartVbyte;                         // save previous byte area
865   
866    CurrSize -= size;
867    StartVbyte = EndVbyte = new char[CurrSize];
868    ExtVbyte = (void *)( StartVbyte + CurrSize );
869    compaction();                                       // copy from old heap to new & adjust pointers to new heap
870    delete  OldStartVbyte;                              // release old heap
871#ifdef VbyteDebug
872    serr | "exit:reduce, CurrSize:" | CurrSize;
873#endif // VbyteDebug
874} // reduce
875
876
877#endif
Note: See TracBrowser for help on using the repository browser.