source: libcfa/src/collections/string_res.cfa@ 5ecaeca

Last change on this file since 5ecaeca was 681e12f, checked in by Peter A. Buhr <pabuhr@…>, 2 years ago

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