Context Navigation

string_res.cfa@ 2f16569

Visit:

Last change on this file since 2f16569 was 2f16569, checked in by Peter A. Buhr <pabuhr@…>, 21 hours ago
remove string 'contains' function and replace with 'includes', make string 'includes' inline
Property mode set to `100644`
File size: 40.9 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 : Thu May 7 13:14:45 2026
13	// Update Count : 135
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	// int find$( const string_res & s, ssize_t start, ssize_t len, const string_res & k, ssize_t kstart, ssize_t klen ) {
753	// if ( start < 0 ) start = s.Handle.lnth + start; // adjust negative starting locations
754	// if ( kstart < 0 ) kstart = k.Handle.lnth + kstart;
755
756	// if ( start + len > s.Handle.lnth ) return start + 1; // cannot be there
757	// if ( kstart + len > k.Handle.lnth ) return start + 1;
758	// if ( klen > len ) return start + 1;
759
760	// int i, r;
761
762	// for ( i = max( start, 1 ); ; i += 1 ) {
763	// if ( i > s.Handle.lnth - k.Handle.lnth + 1 ) {
764	// r = s.Handle.lnth + 1;
765	// break;
766	// } // exit
767	// if ( HeapArea->ByteCmp( s.Handle.s, i, k.Handle.lnth, k.Handle.s, 1, k.Handle.lnth ) == 0 ) {
768	// r = i;
769	// break;
770	// } // exit
771	// } // for
772	// return r;
773	// }
774
775	int find( const string_res & s, char search ) {
776	return findFrom(s, 0, search);
777	}
778
779	int findFrom( const string_res & s, size_t fromPos, char search ) {
780	// FIXME: This paricular overload (find of single char) is optimized to use memchr.
781	// The general overload (find of string, memchr applying to its first character) and `contains` should be adjusted to match.
782	char * searchFrom = s.Handle.s + fromPos;
783	size_t searchLnth = s.Handle.lnth - fromPos;
784	int searchVal = search;
785	char * foundAt = (char *) memchr(searchFrom, searchVal, searchLnth);
786	if (foundAt == 0p) return s.Handle.lnth;
787	else return foundAt - s.Handle.s;
788	}
789
790	int find(const string_res & s, const string_res & search) {
791	return findFrom(s, 0, search);
792	}
793
794	int findFrom(const string_res & s, size_t fromPos, const string_res & search) {
795	return findFrom(s, fromPos, search.Handle.s, search.Handle.lnth);
796	}
797
798	int find(const string_res & s, const char * search) {
799	return findFrom(s, 0, search);
800	}
801	int findFrom(const string_res & s, size_t fromPos, const char * search) {
802	return findFrom(s, fromPos, search, strlen(search));
803	}
804
805	int find(const string_res & s, const char * search, size_t searchsize) {
806	return findFrom(s, 0, search, searchsize);
807	}
808
809	int findFrom(const string_res & s, size_t fromPos, const char * search, size_t searchsize) {
810	/* Remaining implementations essentially ported from Sunjay's work */
811
812	// FIXME: This is a naive algorithm. We probably want to switch to someting
813	// like Boyer-Moore in the future.
814	// https://en.wikipedia.org/wiki/String_searching_algorithm
815
816	// Always find the empty string
817	if (searchsize == 0) {
818	return 0;
819	}
820
821	for ( i; fromPos ~ s.Handle.lnth ) {
822	size_t remaining = s.Handle.lnth - i;
823	// Never going to find the search string if the remaining string is
824	// smaller than search
825	if (remaining < searchsize) {
826	break;
827	}
828
829	bool matched = true;
830	for ( j; searchsize ) {
831	if (search[j] != s.Handle.s[i + j]) {
832	matched = false;
833	break;
834	}
835	}
836	if (matched) {
837	return i;
838	}
839	}
840	return s.Handle.lnth;
841	}
842
843	bool includes(const string_res & s, const string_res & search) {
844	return includes(s, search.Handle.s, search.Handle.lnth);
845	}
846
847	bool includes(const string_res & s, const char * search) {
848	return includes(s, search, strlen(search));
849	}
850
851	bool includes(const string_res & s, const char * search, size_t searchsize) {
852	return find(s, search, searchsize) < s.Handle.lnth;
853	}
854
855	bool startsWith(const string_res & s, const string_res & prefix) {
856	return startsWith(s, prefix.Handle.s, prefix.Handle.lnth);
857	}
858
859	bool startsWith(const string_res & s, const char * prefix) {
860	return startsWith(s, prefix, strlen(prefix));
861	}
862
863	bool startsWith(const string_res & s, const char * prefix, size_t prefixsize) {
864	if (s.Handle.lnth < prefixsize) {
865	return false;
866	}
867	return memcmp(s.Handle.s, prefix, prefixsize) == 0;
868	}
869
870	bool endsWith(const string_res & s, const string_res & suffix) {
871	return endsWith(s, suffix.Handle.s, suffix.Handle.lnth);
872	}
873
874	bool endsWith(const string_res & s, const char * suffix) {
875	return endsWith(s, suffix, strlen(suffix));
876	}
877
878	bool endsWith(const string_res & s, const char * suffix, size_t suffixsize) {
879	if (s.Handle.lnth < suffixsize) {
880	return false;
881	}
882	// Amount to offset the bytes pointer so that we are comparing the end of s
883	// to suffix. s.bytes + offset should be the first byte to compare against suffix
884	size_t offset = s.Handle.lnth - suffixsize;
885	return memcmp(s.Handle.s + offset, suffix, suffixsize) == 0;
886	}
887
888	/* Back to Mike's work */
889
890	///////////////////////////////////////////////////////////////////////////
891	// charclass, include, exclude
892
893	void ?{}( charclass_res & s, const string_res & chars) {
894	(s){ chars.Handle.s, chars.Handle.lnth };
895	}
896
897	void ?{}( charclass_res & s, const char * chars ) {
898	(s){ chars, strlen(chars) };
899	}
900
901	void ?{}( charclass_res & s, const char * chars, size_t charssize ) {
902	(s.chars){ chars, charssize };
903	// now sort it ?
904	}
905
906	void ^?{}( charclass_res & s ) {
907	^(s.chars){};
908	}
909
910	static bool test( const charclass_res & mask, char c ) {
911	// instead, use sorted char list?
912	for ( i; len(mask.chars) ) {
913	if (mask.chars[i] == c) return true;
914	}
915	return false;
916	// return contains( mask.chars, c );
917	}
918
919	int exclude(const string_res & s, const charclass_res & mask) {
920	for ( i; len(s) ) {
921	if ( test(mask, s[i]) ) return i;
922	}
923	return len(s);
924	}
925
926	int include(const string_res & s, const charclass_res & mask) {
927	for ( i; len(s) ) {
928	if ( ! test(mask, s[i]) ) return i;
929	}
930	return len(s);
931	}
932
933	//######################### VbyteHeap "implementation" #########################
934
935
936	// Add a new HandleNode node n after the current HandleNode node.
937
938	static void AddThisAfter( HandleNode & s, HandleNode & n ) with(s) {
939	#ifdef VbyteDebug
940	serr \| "enter:AddThisAfter, s:" \| &s \| " n:" \| &n;
941	#endif // VbyteDebug
942	// 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).
943	verify( n.ulink != 0p );
944	verify( s.ulink == n.ulink );
945	flink = n.flink;
946	blink = &n;
947	n.flink->blink = &s;
948	n.flink = &s;
949	#ifdef VbyteDebug
950	{
951	serr \| "HandleList:";
952	serr \| nlOff;
953	for ( HandleNode *ni = HeaderPtr->flink; ni != HeaderPtr; ni = ni->flink ) {
954	serr \| "\tnode:" \| ni \| " lnth:" \| ni->lnth \| " s:" \| (void *)ni->s \| ",\"";
955	for ( i; ni->lnth ) {
956	serr \| ni->s[i];
957	} // for
958	serr \| "\" flink:" \| ni->flink \| " blink:" \| ni->blink \| nl;
959	} // for
960	serr \| nlOn;
961	}
962	serr \| "exit:AddThisAfter";
963	#endif // VbyteDebug
964	} // AddThisAfter
965
966
967	// Delete the current HandleNode node.
968
969	static void DeleteNode( HandleNode & s ) with(s) {
970	#ifdef VbyteDebug
971	serr \| "enter:DeleteNode, s:" \| &s;
972	#endif // VbyteDebug
973	flink->blink = blink;
974	blink->flink = flink;
975	#ifdef VbyteDebug
976	serr \| "exit:DeleteNode";
977	#endif // VbyteDebug
978	} // DeleteNode
979
980
981	// Allocates specified storage for a string from byte-string area. If not enough space remains to perform the
982	// allocation, the garbage collection routine is called.
983
984	static char * VbyteAlloc( VbyteHeap & s, int size ) with(s) {
985	#ifdef VbyteDebug
986	serr \| "enter:VbyteAlloc, size:" \| size;
987	#endif // VbyteDebug
988	uintptr_t NoBytes;
989	char *r;
990
991	NoBytes = ( uintptr_t )EndVbyte + size;
992	if ( NoBytes > ( uintptr_t )ExtVbyte ) { // enough room for new byte-string ?
993	garbage( s, size ); // firer up the garbage collector
994	verify( (( uintptr_t )EndVbyte + size) <= ( uintptr_t )ExtVbyte && "garbage run did not free up required space" );
995	} // if
996	r = EndVbyte;
997	EndVbyte += size;
998	#ifdef VbyteDebug
999	serr \| "exit:VbyteAlloc, r:" \| (void )r \| " EndVbyte:" \| (void )EndVbyte \| " ExtVbyte:" \| ExtVbyte;
1000	#endif // VbyteDebug
1001	return r;
1002	} // VbyteAlloc
1003
1004
1005	// Adjusts the last allocation in this heap by delta bytes, or resets this heap to be able to offer
1006	// new allocations of its original size + delta bytes. Positive delta means bigger;
1007	// negative means smaller. A null return indicates that the original heap location has room for
1008	// the requested growth. A non-null return indicates that copying to a new location is required
1009	// but has not been done; the returned value is the old heap storage location; `this` heap is
1010	// modified to reference the new location. In the copy-requred case, the caller should use
1011	// VbyteAlloc to claim the new space, while doing optimal copying from old to new, then free old.
1012
1013	static char * VbyteTryAdjustLast( VbyteHeap & s, int delta ) with(s) {
1014	if ( ( uintptr_t )EndVbyte + delta <= ( uintptr_t )ExtVbyte ) {
1015	// room available
1016	EndVbyte += delta;
1017	return 0p;
1018	}
1019
1020	char *oldBytes = StartVbyte;
1021
1022	NoOfExtensions += 1;
1023	CurrSize *= 2;
1024	StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize);
1025	ExtVbyte = StartVbyte + CurrSize;
1026
1027	return oldBytes;
1028	}
1029
1030
1031	// Move an existing HandleNode node h somewhere after the current HandleNode node so that it is in ascending order by
1032	// the address in the byte string area.
1033
1034	static void MoveThisAfter( HandleNode & s, const HandleNode & h ) with(s) {
1035	#ifdef VbyteDebug
1036	serr \| "enter:MoveThisAfter, s:" \| & s \| " h:" \| & h;
1037	#endif // VbyteDebug
1038	verify( h.ulink != 0p );
1039	verify( s.ulink == h.ulink );
1040	if ( s < h.s ) { // check argument values
1041	// serr \| "VbyteSM: Error - Cannot move byte string starting at:" \| s \| " after byte string starting at:"
1042	// \| ( h->s ) \| " and keep handles in ascending order";
1043	// exit(-1 );
1044	verify( 0 && "VbyteSM: Error - Cannot move byte strings as requested and keep handles in ascending order");
1045	} // if
1046
1047	HandleNode *i;
1048	for ( i = h.flink; i->s != 0 && s > ( i->s ); i = i->flink ); // find the position for this node after h
1049	if ( & s != i->blink ) {
1050	DeleteNode( s );
1051	AddThisAfter( s, *i->blink );
1052	} // if
1053	#ifdef VbyteDebug
1054	{
1055	serr \| "HandleList:";
1056	serr \| nlOff;
1057	for ( HandleNode *n = HeaderPtr->flink; n != HeaderPtr; n = n->flink ) {
1058	serr \| "\tnode:" \| n \| " lnth:" \| n->lnth \| " s:" \| (void *)n->s \| ",\"";
1059	for ( i; n->lnth ) {
1060	serr \| n->s[i];
1061	} // for
1062	serr \| "\" flink:" \| n->flink \| " blink:" \| n->blink \| nl;
1063	} // for
1064	serr \| nlOn;
1065	}
1066	serr \| "exit:MoveThisAfter";
1067	#endif // VbyteDebug
1068	} // MoveThisAfter
1069
1070
1071	//######################### VbyteHeap #########################
1072
1073	// Compare two byte strings in the byte-string area. The routine returns the following values:
1074	//
1075	// 1 => Src1-byte-string > Src2-byte-string
1076	// 0 => Src1-byte-string = Src2-byte-string
1077	// -1 => Src1-byte-string < Src2-byte-string
1078
1079	int ByteCmp( char Src1, int Src1Start, int Src1Lnth, char Src2, int Src2Start, int Src2Lnth ) {
1080	#ifdef VbyteDebug
1081	serr \| "enter:ByteCmp, Src1Start:" \| Src1Start \| " Src1Lnth:" \| Src1Lnth \| " Src2Start:" \| Src2Start \| " Src2Lnth:" \| Src2Lnth;
1082	#endif // VbyteDebug
1083	int cmp;
1084
1085	CharZip: for ( int i = 0; ; i += 1 ) {
1086	if ( i == Src2Lnth - 1 ) {
1087	for ( ; ; i += 1 ) {
1088	if ( i == Src1Lnth - 1 ) {
1089	cmp = 0;
1090	break CharZip;
1091	} // exit
1092	if ( Src1[Src1Start + i] != ' ') {
1093	// SUSPECTED BUG: this could be be why Peter got the bug report about == " " (why is this case here at all?)
1094	cmp = 1;
1095	break CharZip;
1096	} // exit
1097	} // for
1098	} // exit
1099	if ( i == Src1Lnth - 1 ) {
1100	for ( ; ; i += 1 ) {
1101	if ( i == Src2Lnth - 1 ) {
1102	cmp = 0;
1103	break CharZip;
1104	} // exit
1105	if ( Src2[Src2Start + i] != ' ') {
1106	cmp = -1;
1107	break CharZip;
1108	} // exit
1109	} // for
1110	} // exit
1111	if ( Src2[Src2Start + i] != Src1[Src1Start+ i]) {
1112	cmp = Src1[Src1Start + i] > Src2[Src2Start + i] ? 1 : -1;
1113	break CharZip;
1114	} // exit
1115	} // for
1116	#ifdef VbyteDebug
1117	serr \| "exit:ByteCmp, cmp:" \| cmp;
1118	#endif // VbyteDebug
1119	return cmp;
1120	} // ByteCmp
1121
1122
1123	// The compaction moves all of the byte strings currently in use to the beginning of the byte-string area and modifies
1124	// the handles to reflect the new positions of the byte strings. Compaction assumes that the handle list is in ascending
1125	// order by pointers into the byte-string area. The strings associated with substrings do not have to be moved because
1126	// the containing string has been moved. Hence, they only require that their string pointers be adjusted.
1127
1128	void compaction(VbyteHeap & s) with(s) {
1129	HandleNode *h;
1130	char obase, nbase, *limit;
1131
1132	NoOfCompactions += 1;
1133	EndVbyte = StartVbyte;
1134	h = Header.flink; // ignore header node
1135	for () {
1136	memmove( EndVbyte, h->s, h->lnth );
1137	obase = h->s;
1138	h->s = EndVbyte;
1139	nbase = h->s;
1140	EndVbyte += h->lnth;
1141	limit = obase + h->lnth;
1142	h = h->flink;
1143
1144	// check if any substrings are allocated within a string
1145
1146	for () {
1147	if ( h == &Header ) break; // end of header list ?
1148	if ( h->s >= limit ) break; // outside of current string ?
1149	h->s = nbase + (( uintptr_t )h->s - ( uintptr_t )obase );
1150	h = h->flink;
1151	} // for
1152	if ( h == &Header ) break; // end of header list ?
1153	} // for
1154	} // compaction
1155
1156
1157	static double heap_expansion_freespace_threshold = 0.1; // default inherited from prior work: expand heap when less than 10% "free" (i.e. garbage)
1158	// probably an unreasonable default, but need to assess early-round tests on changing it
1159
1160	void TUNING_set_string_heap_liveness_threshold( double val ) {
1161	heap_expansion_freespace_threshold = 1.0 - val;
1162	}
1163
1164
1165	// Garbage determines the amount of free space left in the heap and then reduces, leave the same, or extends the size of
1166	// the heap. The heap is then compacted in the existing heap or into the newly allocated heap.
1167
1168	void garbage(VbyteHeap & s, int minreq ) with(s) {
1169	#ifdef VbyteDebug
1170	serr \| "enter:garbage";
1171	{
1172	serr \| "HandleList:";
1173	for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) {
1174	serr \| nlOff;
1175	serr \| "\tnode:" \| n \| " lnth:" \| n->lnth \| " s:" \| (void *)n->s \| ",\"";
1176	for ( i; n->lnth ) {
1177	serr \| n->s[i];
1178	} // for
1179	serr \| nlOn;
1180	serr \| "\" flink:" \| n->flink \| " blink:" \| n->blink;
1181	} // for
1182	}
1183	#endif // VbyteDebug
1184	int AmountUsed, AmountFree;
1185
1186	AmountUsed = 0;
1187	for ( HandleNode *i = Header.flink; i != &Header; i = i->flink ) { // calculate amount of byte area used
1188	AmountUsed += i->lnth;
1189	} // for
1190	AmountFree = ( uintptr_t )ExtVbyte - ( uintptr_t )StartVbyte - AmountUsed;
1191
1192	if ( ( double ) AmountFree < ( CurrSize * heap_expansion_freespace_threshold ) \|\| AmountFree < minreq ) { // free space less than threshold or not enough to serve cur request
1193
1194	extend( s, max( CurrSize, minreq ) ); // extend the heap
1195
1196	// Peter says, "This needs work before it should be used."
1197	// } else if ( AmountFree > CurrSize / 2 ) { // free space greater than 3 times the initial allocation ?
1198	// reduce(( AmountFree / CurrSize - 3 ) * CurrSize ); // reduce the memory
1199
1200	// `extend` implies a `compaction` during the copy
1201
1202	} else {
1203	compaction(s); // in-place
1204	}// if
1205	#ifdef VbyteDebug
1206	{
1207	serr \| "HandleList:";
1208	for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) {
1209	serr \| nlOff;
1210	serr \| "\tnode:" \| n \| " lnth:" \| n->lnth \| " s:" \| (void *)n->s \| ",\"";
1211	for ( i; n->lnth ) {
1212	serr \| n->s[i];
1213	} // for
1214	serr \| nlOn;
1215	serr \| "\" flink:" \| n->flink \| " blink:" \| n->blink;
1216	} // for
1217	}
1218	serr \| "exit:garbage";
1219	#endif // VbyteDebug
1220	} // garbage
1221
1222	#undef VbyteDebug
1223
1224
1225
1226	// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string
1227	// area is deleted.
1228
1229	void extend( VbyteHeap & s, int size ) with (s) {
1230	#ifdef VbyteDebug
1231	serr \| "enter:extend, size:" \| size;
1232	#endif // VbyteDebug
1233	char *OldStartVbyte;
1234
1235	NoOfExtensions += 1;
1236	OldStartVbyte = StartVbyte; // save previous byte area
1237
1238	CurrSize += size > InitSize ? size : InitSize; // minimum extension, initial size
1239	StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize);
1240	ExtVbyte = (void *)( StartVbyte + CurrSize );
1241	compaction(s); // copy from old heap to new & adjust pointers to new heap
1242	free( OldStartVbyte ); // release old heap
1243	#ifdef VbyteDebug
1244	serr \| "exit:extend, CurrSize:" \| CurrSize;
1245	#endif // VbyteDebug
1246	} // extend
1247
1248	//WIP
1249	#if 0
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 VbyteHeap::reduce( int size ) {
1255	#ifdef VbyteDebug
1256	serr \| "enter:reduce, size:" \| size;
1257	#endif // VbyteDebug
1258	char *OldStartVbyte;
1259
1260	NoOfReductions += 1;
1261	OldStartVbyte = StartVbyte; // save previous byte area
1262
1263	CurrSize -= size;
1264	StartVbyte = EndVbyte = new char[CurrSize];
1265	ExtVbyte = (void *)( StartVbyte + CurrSize );
1266	compaction(); // copy from old heap to new & adjust pointers to new heap
1267	delete OldStartVbyte; // release old heap
1268	#ifdef VbyteDebug
1269	!serr \| "exit:reduce, CurrSize:" \| CurrSize;
1270	#endif // VbyteDebug
1271	} // reduce
1272
1273
1274	#endif

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

Download in other formats:

Original Format