Context Navigation

string_res.cfa@ b28ce93

Visit:

Last change on this file since b28ce93 was ae0c1c3, checked in by Andrew Beach <ajbeach@…>, 5 months ago
Rewrote the iostream traits to have a single assertion each, a table containing function pointers. This is just an experiment right now. It seems that it does cause significant speed up of assertion resolution, but for some reason also seems to add a flat overhead that mostly eats up that saving.
Property mode set to `100644`
File size: 41.0 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 : Mon Apr 14 20:45:39 2025
13	// Update Count : 130
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	// Output operator
195	forall( ostype & \| basic_ostream( ostype ) )
196	ostype & ?\|?( ostype & out, const string_res & s ) {
197	// CFA string is NOT null terminated, so print exactly lnth characters in a minimum width of 0.
198	return out \| wd( 0, s.Handle.lnth, s.Handle.s ) \| nonl;
199	}
200
201	forall( ostype & \| basic_ostream( ostype ) )
202	void ?\|?( ostype & out, const string_res & s ) {
203	(ostype &)(out \| s);
204	basic_ostream_table.ends( out );
205	}
206
207	// Input operator
208	forall( istype & \| basic_istream( istype ) )
209	istype & ?\|?( istype & in, string_res & s ) {
210	// Reading into a temp before assigning to s is near zero overhead in typical cases because of sharing.
211	// If s is a substring of something larger, simple assignment takes care of that case correctly.
212	// But directly reading a variable amount of text into the middle of a larger context is not practical.
213	string_res temp;
214
215	// Read in chunks. Often, one chunk is enough. Keep the string that accumulates chunks last in the heap,
216	// so available room is rest of heap. When a chunk fills the heap, force growth then take the next chunk.
217	for (bool cont = true; cont; ) {
218	cont = false;
219
220	// Append dummy content to temp, forcing expansion when applicable (occurs always on subsequent loops)
221	// length 2 ensures room for at least one real char, plus scanf/pipe-cstr's null terminator
222	temp += "--";
223	assert( temp.Handle.ulink->EndVbyte == temp.Handle.s + temp.Handle.lnth ); // last in heap
224
225	// reset, to overwrite the appended "--"
226	temp.Handle.lnth -= 2;
227	temp.Handle.ulink->EndVbyte -= 2;
228
229	// rest of heap is available to read into
230	int lenReadable = (char *)temp.Handle.ulink->ExtVbyte - temp.Handle.ulink->EndVbyte;
231	assert (lenReadable >= 2);
232
233	// get bytes
234	try {
235	*(temp.Handle.ulink->EndVbyte) = '\0'; // pre-assign empty cstring
236	in \| wdi( lenReadable, temp.Handle.ulink->EndVbyte );
237	} catch (cstring_length *) {
238	cont = true;
239	}
240	int lenWasRead = strlen(temp.Handle.ulink->EndVbyte);
241
242	// update metadata
243	temp.Handle.lnth += lenWasRead;
244	temp.Handle.ulink->EndVbyte += lenWasRead;
245	}
246
247	if ( temp.Handle.lnth > 0 ) s = temp;
248	return in;
249	}
250
251	forall( istype & \| basic_istream( istype ) )
252	istype & ?\|?( istype & is, _Istream_Rquote f ) with( basic_istream_table, f.rstr ) {
253	if ( eof( is ) ) throwResume ExceptionInst( end_of_file );
254	int args;
255	fini: {
256	char rfmt[5] = { ' ', delimiters[0], '%', 'n', '\0' };
257	int l = -1; // may not be set in fmt
258	args = fmt( is, rfmt, &l ); // remove leading whitespace and quote
259	if ( eof( is ) \|\| l == -1 ) break fini;
260
261	// Change the remainder of the read into a getline by reseting the closing delimiter.
262	if ( delimiters[1] != '\0' ) {
263	delimiters[0] = delimiters[1];
264	delimiters[1] = '\0';
265	} // if
266	flags.delimiter = true;
267	return is \| (_Istream_Rstr )&f;
268	} // fini
269	// read failed => no pattern match => set string to null
270	if ( ! flags.ignore && s != 0p && args == 0 ) s[0] = '\0';
271	if ( args == 1 && eof( is ) ) { // data but scan ended at EOF
272	clearerr( is ); // => reset EOF => detect again on next read
273	} // if
274	return is;
275	}
276
277	forall( istype & \| basic_istream( istype ) )
278	istype & ?\|?( istype & 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
319	void ?{}(string_res & s) with(s) {
320	if( ambient_string_sharectx->activeHeap ) {
321	(Handle){ * ambient_string_sharectx->activeHeap };
322	(shareSet_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	(shareSet_owns_ulink){ true };
327	Handle.s = Handle.ulink->StartVbyte;
328	verify( Handle.lnth == 0 );
329	}
330	s.shareSet_prev = &s;
331	s.shareSet_next = &s;
332	}
333
334	static 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	(shareSet_owns_ulink){ false };
338	} else {
339	(Handle){ * new( rhslnth ) };
340	(shareSet_owns_ulink){ true };
341	}
342	Handle.s = VbyteAlloc(*Handle.ulink, rhslnth);
343	Handle.lnth = rhslnth;
344	memmove( Handle.s, rhs, rhslnth );
345	s.shareSet_prev = &s;
346	s.shareSet_next = &s;
347	}
348
349	// Constructor from a raw buffer and size
350	void ?{}(string_res & s, const char * rhs, size_t rhslnth) with(s) {
351	eagerCopyCtorHelper(s, rhs, rhslnth);
352	}
353
354	void ?{}( string_res & s, ssize_t rhs ) {
355	char buf[64];
356	int l;
357	snprintf( buf, sizeof(buf)-1, "%zd%n", rhs, &l );
358	( s ){ buf, l };
359	}
360	void ?{}( string_res & s, size_t rhs ) {
361	char buf[64];
362	int l;
363	snprintf( buf, sizeof(buf)-1, "%zu%n", rhs, &l );
364	( s ){ buf, l };
365	}
366	void ?{}( string_res & s, double rhs ) {
367	char buf[64];
368	int l;
369	snprintf( buf, sizeof(buf)-1, "%g%n", rhs, &l );
370	( s ){ buf, l };
371	}
372	void ?{}( string_res & s, long double rhs ) {
373	char buf[64];
374	int l;
375	snprintf( buf, sizeof(buf)-1, "%Lg%n", rhs, &l );
376	( s ){ buf, l };
377	}
378	void ?{}( string_res & s, double _Complex rhs ) {
379	char buf[64];
380	int l;
381	snprintf( buf, sizeof(buf)-1, "%g+%gi%n", creal( rhs ), cimag( rhs ), &l );
382	( s ){ buf, l };
383	}
384	void ?{}( string_res & s, long double _Complex rhs ) {
385	char buf[64];
386	int l;
387	snprintf( buf, sizeof(buf)-1, "%Lg+%Lgi%n", creall( rhs ), cimagl( rhs ), &l );
388	( s ){ buf, l };
389	}
390
391	// private ctor (not in header): use specified heap (ignore ambient) and copy chars in
392	void ?{}( 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.shareSet_owns_ulink){ false };
397	memmove( Handle.s, rhs, rhslnth );
398	s.shareSet_prev = &s;
399	s.shareSet_next = &s;
400	}
401
402
403	// General copy constructor
404	void ?{}(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.shareSet_prev == &s);
412	verify(s.shareSet_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.shareSet_owns_ulink){ false };
427
428	// make s alone in its shareSet
429	s.shareSet_prev = &s;
430	s.shareSet_next = &s;
431	} else {
432	verify( mode == SHARE_EDITS );
433	// sharing edits with source forces same heap as source (ignore context)
434
435	(s.shareSet_owns_ulink){ s2.shareSet_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 shareSet
441	s.shareSet_next = s2mod.shareSet_next;
442	s.shareSet_prev = &s2mod;
443	s.shareSet_next->shareSet_prev = &s;
444	s.shareSet_prev->shareSet_next = &s;
445	}
446	}
447	}
448
449	static void assignEditSet(string_res & s, string_res * shareSetStartPeer, string_res * shareSetEndPeer,
450	char * resultSesStart,
451	size_t resultSesLnth,
452	HandleNode * resultPadPosition, size_t bsize ) {
453
454	char * beforeBegin = shareSetStartPeer->Handle.s;
455	size_t beforeLen = s.Handle.s - beforeBegin;
456
457	char * afterBegin = s.Handle.s + s.Handle.lnth;
458	size_t afterLen = shareSetEndPeer->Handle.s + shareSetEndPeer->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.shareSet_next; p != &s; p = p->shareSet_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
523	static void locateInShareSet( string_res & s, string_res & shareSetStartPeer, string_res & shareSetEndPeer ) {
524	shareSetStartPeer = & s;
525	shareSetEndPeer = & s;
526	for (string_res * editPeer = s.shareSet_next; editPeer != &s; editPeer = editPeer->shareSet_next) {
527	if ( editPeer->Handle.s < shareSetStartPeer->Handle.s ) {
528	shareSetStartPeer = editPeer;
529	}
530	if ( shareSetEndPeer->Handle.s + shareSetEndPeer->Handle.lnth < editPeer->Handle.s + editPeer->Handle.lnth) {
531	shareSetEndPeer = editPeer;
532	}
533	}
534	}
535
536	static string_res & assign_(string_res & s, const char * buffer, size_t bsize, const string_res & valSrc) {
537	string_res * shareSetStartPeer;
538	string_res * shareSetEndPeer;
539	locateInShareSet( s, shareSetStartPeer, shareSetEndPeer );
540
541	verify( shareSetEndPeer->Handle.s >= shareSetStartPeer->Handle.s );
542	size_t origEditSetLength = shareSetEndPeer->Handle.s + shareSetEndPeer->Handle.lnth - shareSetStartPeer->Handle.s;
543	verify( origEditSetLength >= s.Handle.lnth );
544
545	if ( s.shareSet_owns_ulink ) { // assigning to private context
546	// ok to overwrite old value within LHS
547	char * prefixStartOrig = shareSetStartPeer->Handle.s;
548	int prefixLen = s.Handle.s - prefixStartOrig;
549	char * suffixStartOrig = s.Handle.s + s.Handle.lnth;
550	int suffixLen = shareSetEndPeer->Handle.s + shareSetEndPeer->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, shareSetStartPeer, shareSetEndPeer,
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, shareSetStartPeer, shareSetEndPeer,
570	shareSetStartPeer->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, shareSetStartPeer, shareSetEndPeer,
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 shareSetStartPeer thru end of shareSetEndPeer
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	shareSetStartPeer->Handle.s, // start of SES
597	s.Handle.s - shareSetStartPeer->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	shareSetEndPeer->Handle.s + shareSetEndPeer->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, shareSetStartPeer, shareSetEndPeer,
611	pasting.Handle.s,
612	pasting.Handle.lnth,
613	&pasting.Handle, bsize);
614	}
615
616	return s;
617	}
618
619	string_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
623	string_res & assign(string_res & s, const char * buffer, size_t bsize) {
624	return assign_(s, buffer, bsize, *0p);
625	}
626
627	string_res & ?=?(string_res & s, char c) {
628	return assign(s, &c, 1);
629	}
630
631	string_res & ?=?( string_res & s, ssize_t rhs ) {
632	string_res rhs2 = rhs;
633	s = rhs2;
634	return s;
635	}
636	string_res & ?=?( string_res & s, size_t rhs ) {
637	string_res rhs2 = rhs;
638	s = rhs2;
639	return s;
640	}
641	string_res & ?=?( string_res & s, double rhs ) {
642	string_res rhs2 = rhs;
643	s = rhs2;
644	return s;
645	}
646	string_res & ?=?( string_res & s, long double rhs ) {
647	string_res rhs2 = rhs;
648	s = rhs2;
649	return s;
650	}
651	string_res & ?=?( string_res & s, double _Complex rhs ) {
652	string_res rhs2 = rhs;
653	s = rhs2;
654	return s;
655	}
656	string_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
663	string_res & ?=?(string_res & s, const string_res & rhs) with( s ) {
664	return assign_(s, rhs.Handle.s, rhs.Handle.lnth, rhs);
665	}
666
667	string_res & ?=?(string_res & s, string_res & rhs) with( s ) {
668	const string_res & rhs2 = rhs;
669	return s = rhs2;
670	}
671
672
673	// Destructor
674	void ^?{}(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.shareSet_prev->shareSet_next = s.shareSet_next;
679	s.shareSet_next->shareSet_prev = s.shareSet_prev;
680	// s.shareSet_next = &s;
681	// s.shareSet_prev = &s;
682
683	if (shareSet_owns_ulink && s.shareSet_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.
692	char ?[?](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
697	void 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
709	void 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
727	void append( string_res & s, const string_res & s2, size_t maxlen ) {
728	append( s, s2.Handle.s, min( s2.Handle.lnth, maxlen ) );
729	}
730
731	///////////////////////////////////////////////////////////////////
732	// Repetition
733
734	void ?*=?(string_res & s, size_t factor) {
735	string_res s2 = { s, COPY_VALUE };
736	s = "";
737	for (factor) s += s2;
738	}
739
740	//////////////////////////////////////////////////////////
741	// Comparisons
742
743	int strcmp$( const char * s1, size_t l1, const char * s2, size_t l2 ) {
744	int ret = memcmp( s1, s2, min( l1, l2 ) );
745	if ( ret != 0 ) return ret;
746	return l1 - l2;
747	}
748
749	//////////////////////////////////////////////////////////
750	// Search
751
752	bool contains(const string_res & s, char ch) {
753	for ( i; len(s) ) {
754	if (s[i] == ch) return true;
755	}
756	return false;
757	}
758
759	// int find$( const string_res & s, ssize_t start, ssize_t len, const string_res & k, ssize_t kstart, ssize_t klen ) {
760	// if ( start < 0 ) start = s.Handle.lnth + start; // adjust negative starting locations
761	// if ( kstart < 0 ) kstart = k.Handle.lnth + kstart;
762
763	// if ( start + len > s.Handle.lnth ) return start + 1; // cannot be there
764	// if ( kstart + len > k.Handle.lnth ) return start + 1;
765	// if ( klen > len ) return start + 1;
766
767	// int i, r;
768
769	// for ( i = max( start, 1 ); ; i += 1 ) {
770	// if ( i > s.Handle.lnth - k.Handle.lnth + 1 ) {
771	// r = s.Handle.lnth + 1;
772	// break;
773	// } // exit
774	// if ( HeapArea->ByteCmp( s.Handle.s, i, k.Handle.lnth, k.Handle.s, 1, k.Handle.lnth ) == 0 ) {
775	// r = i;
776	// break;
777	// } // exit
778	// } // for
779	// return r;
780	// }
781
782	int find( const string_res & s, char search ) {
783	return findFrom(s, 0, search);
784	}
785
786	int findFrom( const string_res & s, size_t fromPos, char search ) {
787	// FIXME: This paricular overload (find of single char) is optimized to use memchr.
788	// The general overload (find of string, memchr applying to its first character) and `contains` should be adjusted to match.
789	char * searchFrom = s.Handle.s + fromPos;
790	size_t searchLnth = s.Handle.lnth - fromPos;
791	int searchVal = search;
792	char * foundAt = (char *) memchr(searchFrom, searchVal, searchLnth);
793	if (foundAt == 0p) return s.Handle.lnth;
794	else return foundAt - s.Handle.s;
795	}
796
797	int find(const string_res & s, const string_res & search) {
798	return findFrom(s, 0, search);
799	}
800
801	int findFrom(const string_res & s, size_t fromPos, const string_res & search) {
802	return findFrom(s, fromPos, search.Handle.s, search.Handle.lnth);
803	}
804
805	int find(const string_res & s, const char * search) {
806	return findFrom(s, 0, search);
807	}
808	int findFrom(const string_res & s, size_t fromPos, const char * search) {
809	return findFrom(s, fromPos, search, strlen(search));
810	}
811
812	int find(const string_res & s, const char * search, size_t searchsize) {
813	return findFrom(s, 0, search, searchsize);
814	}
815
816	int findFrom(const string_res & s, size_t fromPos, const char * search, size_t searchsize) {
817	/* Remaining implementations essentially ported from Sunjay's work */
818
819	// FIXME: This is a naive algorithm. We probably want to switch to someting
820	// like Boyer-Moore in the future.
821	// https://en.wikipedia.org/wiki/String_searching_algorithm
822
823	// Always find the empty string
824	if (searchsize == 0) {
825	return 0;
826	}
827
828	for ( i; fromPos ~ s.Handle.lnth ) {
829	size_t remaining = s.Handle.lnth - i;
830	// Never going to find the search string if the remaining string is
831	// smaller than search
832	if (remaining < searchsize) {
833	break;
834	}
835
836	bool matched = true;
837	for ( j; searchsize ) {
838	if (search[j] != s.Handle.s[i + j]) {
839	matched = false;
840	break;
841	}
842	}
843	if (matched) {
844	return i;
845	}
846	}
847	return s.Handle.lnth;
848	}
849
850	bool includes(const string_res & s, const string_res & search) {
851	return includes(s, search.Handle.s, search.Handle.lnth);
852	}
853
854	bool includes(const string_res & s, const char * search) {
855	return includes(s, search, strlen(search));
856	}
857
858	bool includes(const string_res & s, const char * search, size_t searchsize) {
859	return find(s, search, searchsize) < s.Handle.lnth;
860	}
861
862	bool startsWith(const string_res & s, const string_res & prefix) {
863	return startsWith(s, prefix.Handle.s, prefix.Handle.lnth);
864	}
865
866	bool startsWith(const string_res & s, const char * prefix) {
867	return startsWith(s, prefix, strlen(prefix));
868	}
869
870	bool startsWith(const string_res & s, const char * prefix, size_t prefixsize) {
871	if (s.Handle.lnth < prefixsize) {
872	return false;
873	}
874	return memcmp(s.Handle.s, prefix, prefixsize) == 0;
875	}
876
877	bool endsWith(const string_res & s, const string_res & suffix) {
878	return endsWith(s, suffix.Handle.s, suffix.Handle.lnth);
879	}
880
881	bool endsWith(const string_res & s, const char * suffix) {
882	return endsWith(s, suffix, strlen(suffix));
883	}
884
885	bool endsWith(const string_res & s, const char * suffix, size_t suffixsize) {
886	if (s.Handle.lnth < suffixsize) {
887	return false;
888	}
889	// Amount to offset the bytes pointer so that we are comparing the end of s
890	// to suffix. s.bytes + offset should be the first byte to compare against suffix
891	size_t offset = s.Handle.lnth - suffixsize;
892	return memcmp(s.Handle.s + offset, suffix, suffixsize) == 0;
893	}
894
895	/* Back to Mike's work */
896
897	///////////////////////////////////////////////////////////////////////////
898	// charclass, include, exclude
899
900	void ?{}( charclass_res & s, const string_res & chars) {
901	(s){ chars.Handle.s, chars.Handle.lnth };
902	}
903
904	void ?{}( charclass_res & s, const char * chars ) {
905	(s){ chars, strlen(chars) };
906	}
907
908	void ?{}( charclass_res & s, const char * chars, size_t charssize ) {
909	(s.chars){ chars, charssize };
910	// now sort it ?
911	}
912
913	void ^?{}( charclass_res & s ) {
914	^(s.chars){};
915	}
916
917	static bool test( const charclass_res & mask, char c ) {
918	// instead, use sorted char list?
919	return contains( mask.chars, c );
920	}
921
922	int exclude(const string_res & s, const charclass_res & mask) {
923	for ( i; len(s) ) {
924	if ( test(mask, s[i]) ) return i;
925	}
926	return len(s);
927	}
928
929	int include(const string_res & s, const charclass_res & mask) {
930	for ( i; len(s) ) {
931	if ( ! test(mask, s[i]) ) return i;
932	}
933	return len(s);
934	}
935
936	//######################### VbyteHeap "implementation" #########################
937
938
939	// Add a new HandleNode node n after the current HandleNode node.
940
941	static void AddThisAfter( HandleNode & s, HandleNode & n ) with(s) {
942	#ifdef VbyteDebug
943	serr \| "enter:AddThisAfter, s:" \| &s \| " n:" \| &n;
944	#endif // VbyteDebug
945	// 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).
946	verify( n.ulink != 0p );
947	verify( s.ulink == n.ulink );
948	flink = n.flink;
949	blink = &n;
950	n.flink->blink = &s;
951	n.flink = &s;
952	#ifdef VbyteDebug
953	{
954	serr \| "HandleList:";
955	serr \| nlOff;
956	for ( HandleNode *ni = HeaderPtr->flink; ni != HeaderPtr; ni = ni->flink ) {
957	serr \| "\tnode:" \| ni \| " lnth:" \| ni->lnth \| " s:" \| (void *)ni->s \| ",\"";
958	for ( i; ni->lnth ) {
959	serr \| ni->s[i];
960	} // for
961	serr \| "\" flink:" \| ni->flink \| " blink:" \| ni->blink \| nl;
962	} // for
963	serr \| nlOn;
964	}
965	serr \| "exit:AddThisAfter";
966	#endif // VbyteDebug
967	} // AddThisAfter
968
969
970	// Delete the current HandleNode node.
971
972	static void DeleteNode( HandleNode & s ) with(s) {
973	#ifdef VbyteDebug
974	serr \| "enter:DeleteNode, s:" \| &s;
975	#endif // VbyteDebug
976	flink->blink = blink;
977	blink->flink = flink;
978	#ifdef VbyteDebug
979	serr \| "exit:DeleteNode";
980	#endif // VbyteDebug
981	} // DeleteNode
982
983
984	// Allocates specified storage for a string from byte-string area. If not enough space remains to perform the
985	// allocation, the garbage collection routine is called.
986
987	static char * VbyteAlloc( VbyteHeap & s, int size ) with(s) {
988	#ifdef VbyteDebug
989	serr \| "enter:VbyteAlloc, size:" \| size;
990	#endif // VbyteDebug
991	uintptr_t NoBytes;
992	char *r;
993
994	NoBytes = ( uintptr_t )EndVbyte + size;
995	if ( NoBytes > ( uintptr_t )ExtVbyte ) { // enough room for new byte-string ?
996	garbage( s, size ); // firer up the garbage collector
997	verify( (( uintptr_t )EndVbyte + size) <= ( uintptr_t )ExtVbyte && "garbage run did not free up required space" );
998	} // if
999	r = EndVbyte;
1000	EndVbyte += size;
1001	#ifdef VbyteDebug
1002	serr \| "exit:VbyteAlloc, r:" \| (void )r \| " EndVbyte:" \| (void )EndVbyte \| " ExtVbyte:" \| ExtVbyte;
1003	#endif // VbyteDebug
1004	return r;
1005	} // VbyteAlloc
1006
1007
1008	// Adjusts the last allocation in this heap by delta bytes, or resets this heap to be able to offer
1009	// new allocations of its original size + delta bytes. Positive delta means bigger;
1010	// negative means smaller. A null return indicates that the original heap location has room for
1011	// the requested growth. A non-null return indicates that copying to a new location is required
1012	// but has not been done; the returned value is the old heap storage location; `this` heap is
1013	// modified to reference the new location. In the copy-requred case, the caller should use
1014	// VbyteAlloc to claim the new space, while doing optimal copying from old to new, then free old.
1015
1016	static char * VbyteTryAdjustLast( VbyteHeap & s, int delta ) with(s) {
1017	if ( ( uintptr_t )EndVbyte + delta <= ( uintptr_t )ExtVbyte ) {
1018	// room available
1019	EndVbyte += delta;
1020	return 0p;
1021	}
1022
1023	char *oldBytes = StartVbyte;
1024
1025	NoOfExtensions += 1;
1026	CurrSize *= 2;
1027	StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize);
1028	ExtVbyte = StartVbyte + CurrSize;
1029
1030	return oldBytes;
1031	}
1032
1033
1034	// Move an existing HandleNode node h somewhere after the current HandleNode node so that it is in ascending order by
1035	// the address in the byte string area.
1036
1037	static void MoveThisAfter( HandleNode & s, const HandleNode & h ) with(s) {
1038	#ifdef VbyteDebug
1039	serr \| "enter:MoveThisAfter, s:" \| & s \| " h:" \| & h;
1040	#endif // VbyteDebug
1041	verify( h.ulink != 0p );
1042	verify( s.ulink == h.ulink );
1043	if ( s < h.s ) { // check argument values
1044	// serr \| "VbyteSM: Error - Cannot move byte string starting at:" \| s \| " after byte string starting at:"
1045	// \| ( h->s ) \| " and keep handles in ascending order";
1046	// exit(-1 );
1047	verify( 0 && "VbyteSM: Error - Cannot move byte strings as requested and keep handles in ascending order");
1048	} // if
1049
1050	HandleNode *i;
1051	for ( i = h.flink; i->s != 0 && s > ( i->s ); i = i->flink ); // find the position for this node after h
1052	if ( & s != i->blink ) {
1053	DeleteNode( s );
1054	AddThisAfter( s, *i->blink );
1055	} // if
1056	#ifdef VbyteDebug
1057	{
1058	serr \| "HandleList:";
1059	serr \| nlOff;
1060	for ( HandleNode *n = HeaderPtr->flink; n != HeaderPtr; n = n->flink ) {
1061	serr \| "\tnode:" \| n \| " lnth:" \| n->lnth \| " s:" \| (void *)n->s \| ",\"";
1062	for ( i; n->lnth ) {
1063	serr \| n->s[i];
1064	} // for
1065	serr \| "\" flink:" \| n->flink \| " blink:" \| n->blink \| nl;
1066	} // for
1067	serr \| nlOn;
1068	}
1069	serr \| "exit:MoveThisAfter";
1070	#endif // VbyteDebug
1071	} // MoveThisAfter
1072
1073
1074	//######################### VbyteHeap #########################
1075
1076	// Compare two byte strings in the byte-string area. The routine returns the following values:
1077	//
1078	// 1 => Src1-byte-string > Src2-byte-string
1079	// 0 => Src1-byte-string = Src2-byte-string
1080	// -1 => Src1-byte-string < Src2-byte-string
1081
1082	int ByteCmp( char Src1, int Src1Start, int Src1Lnth, char Src2, int Src2Start, int Src2Lnth ) {
1083	#ifdef VbyteDebug
1084	serr \| "enter:ByteCmp, Src1Start:" \| Src1Start \| " Src1Lnth:" \| Src1Lnth \| " Src2Start:" \| Src2Start \| " Src2Lnth:" \| Src2Lnth;
1085	#endif // VbyteDebug
1086	int cmp;
1087
1088	CharZip: for ( int i = 0; ; i += 1 ) {
1089	if ( i == Src2Lnth - 1 ) {
1090	for ( ; ; i += 1 ) {
1091	if ( i == Src1Lnth - 1 ) {
1092	cmp = 0;
1093	break CharZip;
1094	} // exit
1095	if ( Src1[Src1Start + i] != ' ') {
1096	// SUSPECTED BUG: this could be be why Peter got the bug report about == " " (why is this case here at all?)
1097	cmp = 1;
1098	break CharZip;
1099	} // exit
1100	} // for
1101	} // exit
1102	if ( i == Src1Lnth - 1 ) {
1103	for ( ; ; i += 1 ) {
1104	if ( i == Src2Lnth - 1 ) {
1105	cmp = 0;
1106	break CharZip;
1107	} // exit
1108	if ( Src2[Src2Start + i] != ' ') {
1109	cmp = -1;
1110	break CharZip;
1111	} // exit
1112	} // for
1113	} // exit
1114	if ( Src2[Src2Start + i] != Src1[Src1Start+ i]) {
1115	cmp = Src1[Src1Start + i] > Src2[Src2Start + i] ? 1 : -1;
1116	break CharZip;
1117	} // exit
1118	} // for
1119	#ifdef VbyteDebug
1120	serr \| "exit:ByteCmp, cmp:" \| cmp;
1121	#endif // VbyteDebug
1122	return cmp;
1123	} // ByteCmp
1124
1125
1126	// The compaction moves all of the byte strings currently in use to the beginning of the byte-string area and modifies
1127	// the handles to reflect the new positions of the byte strings. Compaction assumes that the handle list is in ascending
1128	// order by pointers into the byte-string area. The strings associated with substrings do not have to be moved because
1129	// the containing string has been moved. Hence, they only require that their string pointers be adjusted.
1130
1131	void compaction(VbyteHeap & s) with(s) {
1132	HandleNode *h;
1133	char obase, nbase, *limit;
1134
1135	NoOfCompactions += 1;
1136	EndVbyte = StartVbyte;
1137	h = Header.flink; // ignore header node
1138	for () {
1139	memmove( EndVbyte, h->s, h->lnth );
1140	obase = h->s;
1141	h->s = EndVbyte;
1142	nbase = h->s;
1143	EndVbyte += h->lnth;
1144	limit = obase + h->lnth;
1145	h = h->flink;
1146
1147	// check if any substrings are allocated within a string
1148
1149	for () {
1150	if ( h == &Header ) break; // end of header list ?
1151	if ( h->s >= limit ) break; // outside of current string ?
1152	h->s = nbase + (( uintptr_t )h->s - ( uintptr_t )obase );
1153	h = h->flink;
1154	} // for
1155	if ( h == &Header ) break; // end of header list ?
1156	} // for
1157	} // compaction
1158
1159
1160	static double heap_expansion_freespace_threshold = 0.1; // default inherited from prior work: expand heap when less than 10% "free" (i.e. garbage)
1161	// probably an unreasonable default, but need to assess early-round tests on changing it
1162
1163	void TUNING_set_string_heap_liveness_threshold( double val ) {
1164	heap_expansion_freespace_threshold = 1.0 - val;
1165	}
1166
1167
1168	// Garbage determines the amount of free space left in the heap and then reduces, leave the same, or extends the size of
1169	// the heap. The heap is then compacted in the existing heap or into the newly allocated heap.
1170
1171	void garbage(VbyteHeap & s, int minreq ) with(s) {
1172	#ifdef VbyteDebug
1173	serr \| "enter:garbage";
1174	{
1175	serr \| "HandleList:";
1176	for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) {
1177	serr \| nlOff;
1178	serr \| "\tnode:" \| n \| " lnth:" \| n->lnth \| " s:" \| (void *)n->s \| ",\"";
1179	for ( i; n->lnth ) {
1180	serr \| n->s[i];
1181	} // for
1182	serr \| nlOn;
1183	serr \| "\" flink:" \| n->flink \| " blink:" \| n->blink;
1184	} // for
1185	}
1186	#endif // VbyteDebug
1187	int AmountUsed, AmountFree;
1188
1189	AmountUsed = 0;
1190	for ( HandleNode *i = Header.flink; i != &Header; i = i->flink ) { // calculate amount of byte area used
1191	AmountUsed += i->lnth;
1192	} // for
1193	AmountFree = ( uintptr_t )ExtVbyte - ( uintptr_t )StartVbyte - AmountUsed;
1194
1195	if ( ( double ) AmountFree < ( CurrSize * heap_expansion_freespace_threshold ) \|\| AmountFree < minreq ) { // free space less than threshold or not enough to serve cur request
1196
1197	extend( s, max( CurrSize, minreq ) ); // extend the heap
1198
1199	// Peter says, "This needs work before it should be used."
1200	// } else if ( AmountFree > CurrSize / 2 ) { // free space greater than 3 times the initial allocation ?
1201	// reduce(( AmountFree / CurrSize - 3 ) * CurrSize ); // reduce the memory
1202
1203	// `extend` implies a `compaction` during the copy
1204
1205	} else {
1206	compaction(s); // in-place
1207	}// if
1208	#ifdef VbyteDebug
1209	{
1210	serr \| "HandleList:";
1211	for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) {
1212	serr \| nlOff;
1213	serr \| "\tnode:" \| n \| " lnth:" \| n->lnth \| " s:" \| (void *)n->s \| ",\"";
1214	for ( i; n->lnth ) {
1215	serr \| n->s[i];
1216	} // for
1217	serr \| nlOn;
1218	serr \| "\" flink:" \| n->flink \| " blink:" \| n->blink;
1219	} // for
1220	}
1221	serr \| "exit:garbage";
1222	#endif // VbyteDebug
1223	} // garbage
1224
1225	#undef VbyteDebug
1226
1227
1228
1229	// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string
1230	// area is deleted.
1231
1232	void extend( VbyteHeap & s, int size ) with (s) {
1233	#ifdef VbyteDebug
1234	serr \| "enter:extend, size:" \| size;
1235	#endif // VbyteDebug
1236	char *OldStartVbyte;
1237
1238	NoOfExtensions += 1;
1239	OldStartVbyte = StartVbyte; // save previous byte area
1240
1241	CurrSize += size > InitSize ? size : InitSize; // minimum extension, initial size
1242	StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize);
1243	ExtVbyte = (void *)( StartVbyte + CurrSize );
1244	compaction(s); // copy from old heap to new & adjust pointers to new heap
1245	free( OldStartVbyte ); // release old heap
1246	#ifdef VbyteDebug
1247	serr \| "exit:extend, CurrSize:" \| CurrSize;
1248	#endif // VbyteDebug
1249	} // extend
1250
1251	//WIP
1252	#if 0
1253
1254	// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string
1255	// area is deleted.
1256
1257	void VbyteHeap::reduce( int size ) {
1258	#ifdef VbyteDebug
1259	serr \| "enter:reduce, size:" \| size;
1260	#endif // VbyteDebug
1261	char *OldStartVbyte;
1262
1263	NoOfReductions += 1;
1264	OldStartVbyte = StartVbyte; // save previous byte area
1265
1266	CurrSize -= size;
1267	StartVbyte = EndVbyte = new char[CurrSize];
1268	ExtVbyte = (void *)( StartVbyte + CurrSize );
1269	compaction(); // copy from old heap to new & adjust pointers to new heap
1270	delete OldStartVbyte; // release old heap
1271	#ifdef VbyteDebug
1272	!serr \| "exit:reduce, CurrSize:" \| CurrSize;
1273	#endif // VbyteDebug
1274	} // reduce
1275
1276
1277	#endif

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

Download in other formats:

Original Format