Context Navigation

string_res.cfa@ 4e8df745

Visit:

ADT ast-experimental enum pthread-emulation qualifiedEnum

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

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

Download in other formats:

Original Format