source: libcfa/src/collections/string_res.cfa@ 0d41b2e1

Last change on this file since 0d41b2e1 was f842032, checked in by Peter A. Buhr <pabuhr@…>, 2 years ago

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