Context Navigation

string_res.cfa @ 14755e5

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats:

Original Format