Context Navigation

string_res.cfa@ cb0bcf1

Visit:

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

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

Download in other formats:

Original Format