source: libcfa/src/collections/string_res.cfa@ baad96e

Last change on this file since baad96e was 714e206, checked in by Peter A. Buhr <pabuhr@…>, 20 months ago

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