Context Navigation

string_res.cfa@ c5a2c96

Visit:

ADT ast-experimental

Last change on this file since c5a2c96 was 08ed947, checked in by Michael Brooks <mlbrooks@…>, 4 years ago

Roll up of string changes for performance testing/improvement, and a couple API features supporting them.

String API changes:
Defining a tuning knob to control the heap growth policy (relapaces former 10% hardcode, downgraded to a default)
Implementing findFrom (allowing find-non-first); leaving find as find-first.

String implementation perf improvements:
Calling C-malloc directly instead of via CFA-alloc.
Replacings loops that copy with memmove calls.
Replacings loops that search for a value with memchr calls.

String perf testing realized:
Makefile supporting several prog-*.cfa, chosen by OPERATION value (implies prog.cfa changes to support the adjusted protocol)
Adjusting the starter/accumulater declarations in PEQ and PTA to behave consistently in cfa v cpp.
Adding tests: allocation, find, normalize, pass-by-val, pass-by-x.
Adding helper shell scripts for: generating flame graphs, collecting/crunching allocation stats using Mubeen's malloc wrappers

Property mode set to 100644

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

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

Download in other formats:

Original Format