Context Navigation

string_res.cfa@ fe18b46

Visit:

ADT ast-experimental enum pthread-emulation qualifiedEnum stuck-waitfor-destruct

Last change on this file since fe18b46 was fe18b46, checked in by Michael Brooks <mlbrooks@…>, 5 years ago
String hybrid testing and fixing no-share version through the api-coverage case
Property mode set to `100644`
File size: 37.7 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 <string.h> // e.g. strlen
21	#include <assert.h>
22
23	//######################### VbyteHeap "header" #########################
24
25	#ifdef VbyteDebug
26	HandleNode *HeaderPtr;
27	#endif // VbyteDebug
28
29	struct VbyteHeap {
30
31	int NoOfCompactions; // number of compactions of the byte area
32	int NoOfExtensions; // number of extensions in the size of the byte area
33	int NoOfReductions; // number of reductions in the size of the byte area
34
35	int InitSize; // initial number of bytes in the byte-string area
36	int CurrSize; // current number of bytes in the byte-string area
37	char *StartVbyte; // pointer to the `st byte of the start of the byte-string area
38	char *EndVbyte; // pointer to the next byte after the end of the currently used portion of byte-string area
39	void *ExtVbyte; // pointer to the next byte after the end of the byte-string area
40
41	HandleNode Header; // header node for handle list
42	}; // VbyteHeap
43
44
45	static inline void compaction( VbyteHeap & ); // compaction of the byte area
46	static inline void garbage( VbyteHeap &, int ); // garbage collect the byte area
47	static inline void extend( VbyteHeap &, int ); // extend the size of the byte area
48	static inline void reduce( VbyteHeap &, int ); // reduce the size of the byte area
49
50	static inline void ?{}( VbyteHeap &, size_t = 1000 );
51	static inline void ^?{}( VbyteHeap & );
52	static inline void ByteCopy( char , int, int, char , int, int ); // copy a block of bytes from one location in the heap to another
53	static inline int ByteCmp( char , int, int, char , int, int ); // compare 2 blocks of bytes
54	static inline char *VbyteAlloc( VbyteHeap &, int ); // allocate a block bytes in the heap
55	static inline char *VbyteTryAdjustLast( VbyteHeap &, int );
56
57	static inline void AddThisAfter( HandleNode &, HandleNode & );
58	static inline void DeleteNode( HandleNode & );
59	static inline void MoveThisAfter( HandleNode &, const HandleNode & ); // move current handle after parameter handle
60
61
62	// Allocate the storage for the variable sized area and intialize the heap variables.
63
64	static inline void ?{}( VbyteHeap & this, size_t Size ) with(this) {
65	#ifdef VbyteDebug
66	serr \| "enter:VbyteHeap::VbyteHeap, this:" \| &this \| " Size:" \| Size;
67	#endif // VbyteDebug
68	NoOfCompactions = NoOfExtensions = NoOfReductions = 0;
69	InitSize = CurrSize = Size;
70	StartVbyte = EndVbyte = alloc(CurrSize);
71	ExtVbyte = (void *)( StartVbyte + CurrSize );
72	Header.flink = Header.blink = &Header;
73	Header.ulink = & this;
74	#ifdef VbyteDebug
75	HeaderPtr = &Header;
76	serr \| "exit:VbyteHeap::VbyteHeap, this:" \| &this;
77	#endif // VbyteDebug
78	} // VbyteHeap
79
80
81	// Release the dynamically allocated storage for the byte area.
82
83	static inline void ^?{}( VbyteHeap & this ) with(this) {
84	free( StartVbyte );
85	} // ~VbyteHeap
86
87
88	//######################### HandleNode #########################
89
90
91	// Create a handle node. The handle is not linked into the handle list. This is the responsibilitiy of the handle
92	// creator.
93
94	static inline void ?{}( HandleNode & this ) with(this) {
95	#ifdef VbyteDebug
96	serr \| "enter:HandleNode::HandleNode, this:" \| &this;
97	#endif // VbyteDebug
98	s = 0;
99	lnth = 0;
100	#ifdef VbyteDebug
101	serr \| "exit:HandleNode::HandleNode, this:" \| &this;
102	#endif // VbyteDebug
103	} // HandleNode
104
105	// Create a handle node. The handle is linked into the handle list at the end. This means that this handle will NOT be
106	// in order by string address, but this is not a problem because a string with length zero does nothing during garbage
107	// collection.
108
109	static inline void ?{}( HandleNode & this, VbyteHeap & vh ) with(this) {
110	#ifdef VbyteDebug
111	serr \| "enter:HandleNode::HandleNode, this:" \| &this;
112	#endif // VbyteDebug
113	s = 0;
114	lnth = 0;
115	ulink = &vh;
116	AddThisAfter( this, *vh.Header.blink );
117	#ifdef VbyteDebug
118	serr \| "exit:HandleNode::HandleNode, this:" \| &this;
119	#endif // VbyteDebug
120	} // HandleNode
121
122
123	// Delete a node from the handle list by unchaining it from the list. If the handle node was allocated dynamically, it
124	// is the responsibility of the creator to destroy it.
125
126	static inline void ^?{}( HandleNode & this ) with(this) {
127	#ifdef VbyteDebug
128	serr \| "enter:HandleNode::~HandleNode, this:" \| & this;
129	{
130	serr \| nlOff;
131	serr \| " lnth:" \| lnth \| " s:" \| (void *)s \| ",\"";
132	for ( int i = 0; i < lnth; i += 1 ) {
133	serr \| s[i];
134	} // for
135	serr \| "\" flink:" \| flink \| " blink:" \| blink \| nl;
136	serr \| nlOn;
137	}
138	#endif // VbyteDebug
139	DeleteNode( this );
140	} // ~HandleNode
141
142
143	//######################### String Sharing Context #########################
144
145	static string_sharectx * ambient_string_sharectx; // fickle top of stack
146	static string_sharectx default_string_sharectx = {NEW_SHARING}; // stable bottom of stack
147
148	void ?{}( string_sharectx & this, StringSharectx_Mode mode ) with( this ) {
149	(older){ ambient_string_sharectx };
150	if ( mode == NEW_SHARING ) {
151	(activeHeap){ new( (size_t) 1000 ) };
152	} else {
153	verify( mode == NO_SHARING );
154	(activeHeap){ 0p };
155	}
156	ambient_string_sharectx = & this;
157	}
158
159	void ^?{}( string_sharectx & this ) with( this ) {
160	if ( activeHeap ) delete( activeHeap );
161
162	// unlink this from older-list starting from ambient_string_sharectx
163	// usually, this==ambient_string_sharectx and the loop runs zero times
164	string_sharectx *& c = ambient_string_sharectx;
165	while ( c != &this ) &c = &c->older; // find this
166	c = this.older; // unlink
167	}
168
169	//######################### String Resource #########################
170
171
172	VbyteHeap * DEBUG_string_heap() {
173	assert( ambient_string_sharectx->activeHeap && "No sharing context is active" );
174	return ambient_string_sharectx->activeHeap;
175	}
176
177	size_t DEBUG_string_bytes_avail_until_gc( VbyteHeap * heap ) {
178	return ((char*)heap->ExtVbyte) - heap->EndVbyte;
179	}
180
181	size_t DEBUG_string_bytes_in_heap( VbyteHeap * heap ) {
182	return heap->CurrSize;
183	}
184
185	const char * DEBUG_string_heap_start( VbyteHeap * heap ) {
186	return heap->StartVbyte;
187	}
188
189	// Returns the size of the string in bytes
190	size_t size(const string_res &s) with(s) {
191	return Handle.lnth;
192	}
193
194	// Output operator
195	ofstream & ?\|?(ofstream &out, const string_res &s) {
196	// Store auto-newline state so it can be restored
197	bool anl = getANL$(out);
198	nlOff(out);
199	for (size_t i = 0; i < s.Handle.lnth; i++) {
200	out \| s[i];
201	}
202	out \| sep;
203	// Re-apply newlines after done, for chaining version
204	if (anl) nlOn(out);
205	return out;
206	}
207
208	void ?\|?(ofstream &out, const string_res &s) {
209	// Store auto-newline state so it can be restored
210	bool anl = getANL$(out);
211	nlOff(out);
212	for (size_t i = 0; i < s.Handle.lnth; i++) {
213	// Need to re-apply on the last output operator, for whole-statement version
214	if (anl && i == s.Handle.lnth-1) nlOn(out);
215	out \| s[i];
216	}
217	return out;
218	}
219
220	// Empty constructor
221	void ?{}(string_res &s) with(s) {
222	if( ambient_string_sharectx->activeHeap ) {
223	(Handle){ * ambient_string_sharectx->activeHeap };
224	(shareEditSet_owns_ulink){ false };
225	} else {
226	(Handle){ * new( (size_t) 10 ) }; // TODO: can I lazily avoid allocating for empty string
227	(shareEditSet_owns_ulink){ true };
228	}
229	s.shareEditSet_prev = &s;
230	s.shareEditSet_next = &s;
231	}
232
233	static inline void eagerCopyCtorHelper(string_res &s, const char* rhs, size_t rhslnth) with(s) {
234	if( ambient_string_sharectx->activeHeap ) {
235	(Handle){ * ambient_string_sharectx->activeHeap };
236	(shareEditSet_owns_ulink){ false };
237	} else {
238	(Handle){ * new( rhslnth ) };
239	(shareEditSet_owns_ulink){ true };
240	}
241	Handle.s = VbyteAlloc(*Handle.ulink, rhslnth);
242	Handle.lnth = rhslnth;
243	for ( int i = 0; i < rhslnth; i += 1 ) { // copy characters
244	Handle.s[i] = rhs[i];
245	} // for
246	s.shareEditSet_prev = &s;
247	s.shareEditSet_next = &s;
248	}
249
250	// Constructor from a raw buffer and size
251	void ?{}(string_res &s, const char* rhs, size_t rhslnth) with(s) {
252	eagerCopyCtorHelper(s, rhs, rhslnth);
253	}
254
255	// String literal constructor
256	void ?{}(string_res &s, const char* rhs) {
257	(s){ rhs, strlen(rhs) };
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 editSetLength = shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - shareEditSetStartPeer->Handle.s;
408	verify( editSetLength >= 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, editSetLength );
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	editSetLength,
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	editSetLength,
437	0p, bsize);
438	}
439
440	} else if ( // assigning to shared context
441	this.Handle.lnth == editSetLength && // 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, const char* other) {
487	assign(s, other, strlen(other));
488	}
489
490	void ?=?(string_res &s, char other) {
491	assign(s, &other, 1);
492	}
493
494	// Copy assignment operator
495	void ?=?(string_res & this, const string_res & rhs) with( this ) {
496	assign_(this, rhs.Handle.s, rhs.Handle.lnth, rhs);
497	}
498
499	void ?=?(string_res & this, string_res & rhs) with( this ) {
500	const string_res & rhs2 = rhs;
501	this = rhs2;
502	}
503
504
505	// Destructor
506	void ^?{}(string_res &s) with(s) {
507	// much delegated to implied ^VbyteSM
508
509	// sever s from its share-edit peers, if any (four no-ops when already solo)
510	s.shareEditSet_prev->shareEditSet_next = s.shareEditSet_next;
511	s.shareEditSet_next->shareEditSet_prev = s.shareEditSet_prev;
512	// s.shareEditSet_next = &s;
513	// s.shareEditSet_prev = &s;
514
515	if (shareEditSet_owns_ulink && s.shareEditSet_next == &s) { // last one out
516	delete( s.Handle.ulink );
517	}
518	}
519
520
521	// Returns the character at the given index
522	// With unicode support, this may be different from just the byte at the given
523	// offset from the start of the string.
524	char ?[?](const string_res &s, size_t index) with(s) {
525	//TODO: Check if index is valid (no exceptions yet)
526	return Handle.s[index];
527	}
528
529	void assignAt(const string_res &s, size_t index, char val) {
530	string_res editZone = { s, SHARE_EDITS, index, index+1 };
531	assign(editZone, &val, 1);
532	}
533
534
535	///////////////////////////////////////////////////////////////////
536	// Concatenation
537
538	void append(string_res &str1, const char * buffer, size_t bsize) {
539	size_t clnth = size(str1) + bsize;
540	if ( str1.Handle.s + size(str1) == buffer ) { // already juxtapose ?
541	// no-op
542	} else { // must copy some text
543	if ( str1.Handle.s + size(str1) == VbyteAlloc(*str1.Handle.ulink, 0) ) { // str1 at end of string area ?
544	VbyteAlloc( *str1.Handle.ulink, bsize ); // create room for 2nd part at the end of string area
545	} else { // copy the two parts
546	char * str1newBuf = VbyteAlloc( *str1.Handle.ulink, clnth );
547	char * str1oldBuf = str1.Handle.s; // must read after VbyteAlloc call in case it gs's
548	str1.Handle.s = str1newBuf;
549	ByteCopy( str1.Handle.s, 0, str1.Handle.lnth, str1oldBuf, 0, str1.Handle.lnth);
550	} // if
551	ByteCopy( str1.Handle.s, str1.Handle.lnth, bsize, (char*)buffer, 0, (int)bsize);
552	// VbyteHeap & this, char Dst, int DstStart, int DstLnth, char Src, int SrcStart, int SrcLnth
553	} // if
554	str1.Handle.lnth = clnth;
555	}
556
557	void ?+=?(string_res &str1, const string_res &str2) {
558	append( str1, str2.Handle.s, str2.Handle.lnth );
559	}
560
561	void ?+=?(string_res &s, char other) {
562	append( s, &other, 1 );
563	}
564
565	void ?+=?(string_res &s, const char* other) {
566	append( s, other, strlen(other) );
567	}
568
569
570
571
572	//////////////////////////////////////////////////////////
573	// Comparisons
574
575
576	bool ?==?(const string_res &s1, const string_res &s2) {
577	return ByteCmp( s1.Handle.s, 0, s1.Handle.lnth, s2.Handle.s, 0, s2.Handle.lnth) == 0;
578	}
579
580	bool ?!=?(const string_res &s1, const string_res &s2) {
581	return !(s1 == s2);
582	}
583	bool ?==?(const string_res &s, const char* other) {
584	string_res sother = other;
585	return s == sother;
586	}
587	bool ?!=?(const string_res &s, const char* other) {
588	return !(s == other);
589	}
590
591
592	//////////////////////////////////////////////////////////
593	// Search
594
595	bool contains(const string_res &s, char ch) {
596	for (i; size(s)) {
597	if (s[i] == ch) return true;
598	}
599	return false;
600	}
601
602	int find(const string_res &s, char search) {
603	for (i; size(s)) {
604	if (s[i] == search) return i;
605	}
606	return size(s);
607	}
608
609	/* Remaining implementations essentially ported from Sunjay's work */
610
611	int find(const string_res &s, const string_res &search) {
612	return find(s, search.Handle.s, search.Handle.lnth);
613	}
614
615	int find(const string_res &s, const char* search) {
616	return find(s, search, strlen(search));
617	}
618
619	int find(const string_res &s, const char* search, size_t searchsize) {
620	// FIXME: This is a naive algorithm. We probably want to switch to someting
621	// like Boyer-Moore in the future.
622	// https://en.wikipedia.org/wiki/String_searching_algorithm
623
624	// Always find the empty string
625	if (searchsize == 0) {
626	return 0;
627	}
628
629	for (size_t i = 0; i < s.Handle.lnth; i++) {
630	size_t remaining = s.Handle.lnth - i;
631	// Never going to find the search string if the remaining string is
632	// smaller than search
633	if (remaining < searchsize) {
634	break;
635	}
636
637	bool matched = true;
638	for (size_t j = 0; j < searchsize; j++) {
639	if (search[j] != s.Handle.s[i + j]) {
640	matched = false;
641	break;
642	}
643	}
644	if (matched) {
645	return i;
646	}
647	}
648
649	return s.Handle.lnth;
650	}
651
652	bool includes(const string_res &s, const string_res &search) {
653	return includes(s, search.Handle.s, search.Handle.lnth);
654	}
655
656	bool includes(const string_res &s, const char* search) {
657	return includes(s, search, strlen(search));
658	}
659
660	bool includes(const string_res &s, const char* search, size_t searchsize) {
661	return find(s, search, searchsize) < s.Handle.lnth;
662	}
663
664	bool startsWith(const string_res &s, const string_res &prefix) {
665	return startsWith(s, prefix.Handle.s, prefix.Handle.lnth);
666	}
667
668	bool startsWith(const string_res &s, const char* prefix) {
669	return startsWith(s, prefix, strlen(prefix));
670	}
671
672	bool startsWith(const string_res &s, const char* prefix, size_t prefixsize) {
673	if (s.Handle.lnth < prefixsize) {
674	return false;
675	}
676	return memcmp(s.Handle.s, prefix, prefixsize) == 0;
677	}
678
679	bool endsWith(const string_res &s, const string_res &suffix) {
680	return endsWith(s, suffix.Handle.s, suffix.Handle.lnth);
681	}
682
683	bool endsWith(const string_res &s, const char* suffix) {
684	return endsWith(s, suffix, strlen(suffix));
685	}
686
687	bool endsWith(const string_res &s, const char* suffix, size_t suffixsize) {
688	if (s.Handle.lnth < suffixsize) {
689	return false;
690	}
691	// Amount to offset the bytes pointer so that we are comparing the end of s
692	// to suffix. s.bytes + offset should be the first byte to compare against suffix
693	size_t offset = s.Handle.lnth - suffixsize;
694	return memcmp(s.Handle.s + offset, suffix, suffixsize) == 0;
695	}
696
697	/* Back to Mike's work */
698
699
700	///////////////////////////////////////////////////////////////////////////
701	// charclass, include, exclude
702
703	void ?{}( charclass_res & this, const string_res & chars) {
704	(this){ chars.Handle.s, chars.Handle.lnth };
705	}
706
707	void ?{}( charclass_res & this, const char * chars ) {
708	(this){ chars, strlen(chars) };
709	}
710
711	void ?{}( charclass_res & this, const char * chars, size_t charssize ) {
712	(this.chars){ chars, charssize };
713	// now sort it ?
714	}
715
716	void ^?{}( charclass_res & this ) {
717	^(this.chars){};
718	}
719
720	static bool test( const charclass_res & mask, char c ) {
721	// instead, use sorted char list?
722	return contains( mask.chars, c );
723	}
724
725	int exclude(const string_res &s, const charclass_res &mask) {
726	for (int i = 0; i < size(s); i++) {
727	if ( test(mask, s[i]) ) return i;
728	}
729	return size(s);
730	}
731
732	int include(const string_res &s, const charclass_res &mask) {
733	for (int i = 0; i < size(s); i++) {
734	if ( ! test(mask, s[i]) ) return i;
735	}
736	return size(s);
737	}
738
739	//######################### VbyteHeap "implementation" #########################
740
741
742	// Add a new HandleNode node n after the current HandleNode node.
743
744	static inline void AddThisAfter( HandleNode & this, HandleNode & n ) with(this) {
745	#ifdef VbyteDebug
746	serr \| "enter:AddThisAfter, this:" \| &this \| " n:" \| &n;
747	#endif // VbyteDebug
748	verify( n.ulink != 0p );
749	verify( this.ulink == n.ulink );
750	flink = n.flink;
751	blink = &n;
752	n.flink->blink = &this;
753	n.flink = &this;
754	#ifdef VbyteDebug
755	{
756	serr \| "HandleList:";
757	serr \| nlOff;
758	for ( HandleNode *ni = HeaderPtr->flink; ni != HeaderPtr; ni = ni->flink ) {
759	serr \| "\tnode:" \| ni \| " lnth:" \| ni->lnth \| " s:" \| (void *)ni->s \| ",\"";
760	for ( int i = 0; i < ni->lnth; i += 1 ) {
761	serr \| ni->s[i];
762	} // for
763	serr \| "\" flink:" \| ni->flink \| " blink:" \| ni->blink \| nl;
764	} // for
765	serr \| nlOn;
766	}
767	serr \| "exit:AddThisAfter";
768	#endif // VbyteDebug
769	} // AddThisAfter
770
771
772	// Delete the current HandleNode node.
773
774	static inline void DeleteNode( HandleNode & this ) with(this) {
775	#ifdef VbyteDebug
776	serr \| "enter:DeleteNode, this:" \| &this;
777	#endif // VbyteDebug
778	flink->blink = blink;
779	blink->flink = flink;
780	#ifdef VbyteDebug
781	serr \| "exit:DeleteNode";
782	#endif // VbyteDebug
783	} // DeleteNode
784
785
786
787	// Allocates specified storage for a string from byte-string area. If not enough space remains to perform the
788	// allocation, the garbage collection routine is called.
789
790	static inline char * VbyteAlloc( VbyteHeap & this, int size ) with(this) {
791	#ifdef VbyteDebug
792	serr \| "enter:VbyteAlloc, size:" \| size;
793	#endif // VbyteDebug
794	uintptr_t NoBytes;
795	char *r;
796
797	NoBytes = ( uintptr_t )EndVbyte + size;
798	if ( NoBytes > ( uintptr_t )ExtVbyte ) { // enough room for new byte-string ?
799	garbage( this, size ); // firer up the garbage collector
800	NoBytes = ( uintptr_t )EndVbyte + size; // try again
801	if ( NoBytes > ( uintptr_t )ExtVbyte ) { // enough room for new byte-string ?
802	assert( 0 && "garbage run did not free up required space" );
803	} // if
804	} // if
805	r = EndVbyte;
806	EndVbyte += size;
807	#ifdef VbyteDebug
808	serr \| "exit:VbyteAlloc, r:" \| (void )r \| " EndVbyte:" \| (void )EndVbyte \| " ExtVbyte:" \| ExtVbyte;
809	#endif // VbyteDebug
810	return r;
811	} // VbyteAlloc
812
813
814	// Adjusts the last allocation in this heap by delta bytes, or resets this heap to be able to offer
815	// new allocations of its original size + delta bytes. Positive delta means bigger;
816	// negative means smaller. A null return indicates that the original heap location has room for
817	// the requested growth. A non-null return indicates that copying to a new location is required
818	// but has not been done; the returned value is the old heap storage location; `this` heap is
819	// modified to reference the new location. In the copy-requred case, the caller should use
820	// VbyteAlloc to claim the new space, while doing optimal copying from old to new, then free old.
821
822	static inline char * VbyteTryAdjustLast( VbyteHeap & this, int delta ) with(this) {
823
824	if ( ( uintptr_t )EndVbyte + delta <= ( uintptr_t )ExtVbyte ) {
825	// room available
826	EndVbyte += delta;
827	return 0p;
828	}
829
830	char *oldBytes = StartVbyte;
831
832	NoOfExtensions += 1;
833	CurrSize *= 2;
834	StartVbyte = EndVbyte = alloc(CurrSize);
835	ExtVbyte = StartVbyte + CurrSize;
836
837	return oldBytes;
838	}
839
840
841	// Move an existing HandleNode node h somewhere after the current HandleNode node so that it is in ascending order by
842	// the address in the byte string area.
843
844	static inline void MoveThisAfter( HandleNode & this, const HandleNode & h ) with(this) {
845	#ifdef VbyteDebug
846	serr \| "enter:MoveThisAfter, this:" \| & this \| " h:" \| & h;
847	#endif // VbyteDebug
848	verify( h.ulink != 0p );
849	verify( this.ulink == h.ulink );
850	if ( s < h.s ) { // check argument values
851	// serr \| "VbyteSM: Error - Cannot move byte string starting at:" \| s \| " after byte string starting at:"
852	// \| ( h->s ) \| " and keep handles in ascending order";
853	// exit(-1 );
854	verify( 0 && "VbyteSM: Error - Cannot move byte strings as requested and keep handles in ascending order");
855	} // if
856
857	HandleNode *i;
858	for ( i = h.flink; i->s != 0 && s > ( i->s ); i = i->flink ); // find the position for this node after h
859	if ( & this != i->blink ) {
860	DeleteNode( this );
861	AddThisAfter( this, *i->blink );
862	} // if
863	#ifdef VbyteDebug
864	{
865	serr \| "HandleList:";
866	serr \| nlOff;
867	for ( HandleNode *n = HeaderPtr->flink; n != HeaderPtr; n = n->flink ) {
868	serr \| "\tnode:" \| n \| " lnth:" \| n->lnth \| " s:" \| (void *)n->s \| ",\"";
869	for ( int i = 0; i < n->lnth; i += 1 ) {
870	serr \| n->s[i];
871	} // for
872	serr \| "\" flink:" \| n->flink \| " blink:" \| n->blink \| nl;
873	} // for
874	serr \| nlOn;
875	}
876	serr \| "exit:MoveThisAfter";
877	#endif // VbyteDebug
878	} // MoveThisAfter
879
880
881
882
883
884	//######################### VbyteHeap #########################
885
886	// Move characters from one location in the byte-string area to another. The routine handles the following situations:
887	//
888	// if the \|Src\| > \|Dst\| => truncate
889	// if the \|Dst\| > \|Src\| => pad Dst with blanks
890
891	void ByteCopy( char Dst, int DstStart, int DstLnth, char Src, int SrcStart, int SrcLnth ) {
892	for ( int i = 0; i < DstLnth; i += 1 ) {
893	if ( i == SrcLnth ) { // \|Dst\| > \|Src\|
894	for ( ; i < DstLnth; i += 1 ) { // pad Dst with blanks
895	Dst[DstStart + i] = ' ';
896	} // for
897	break;
898	} // exit
899	Dst[DstStart + i] = Src[SrcStart + i];
900	} // for
901	} // ByteCopy
902
903	// Compare two byte strings in the byte-string area. The routine returns the following values:
904	//
905	// 1 => Src1-byte-string > Src2-byte-string
906	// 0 => Src1-byte-string = Src2-byte-string
907	// -1 => Src1-byte-string < Src2-byte-string
908
909	int ByteCmp( char Src1, int Src1Start, int Src1Lnth, char Src2, int Src2Start, int Src2Lnth ) {
910	#ifdef VbyteDebug
911	serr \| "enter:ByteCmp, Src1Start:" \| Src1Start \| " Src1Lnth:" \| Src1Lnth \| " Src2Start:" \| Src2Start \| " Src2Lnth:" \| Src2Lnth;
912	#endif // VbyteDebug
913	int cmp;
914
915	CharZip: for ( int i = 0; ; i += 1 ) {
916	if ( i == Src2Lnth - 1 ) {
917	for ( ; ; i += 1 ) {
918	if ( i == Src1Lnth - 1 ) {
919	cmp = 0;
920	break CharZip;
921	} // exit
922	if ( Src1[Src1Start + i] != ' ') {
923	// SUSPECTED BUG: this could be be why Peter got the bug report about == " " (why is this case here at all?)
924	cmp = 1;
925	break CharZip;
926	} // exit
927	} // for
928	} // exit
929	if ( i == Src1Lnth - 1 ) {
930	for ( ; ; i += 1 ) {
931	if ( i == Src2Lnth - 1 ) {
932	cmp = 0;
933	break CharZip;
934	} // exit
935	if ( Src2[Src2Start + i] != ' ') {
936	cmp = -1;
937	break CharZip;
938	} // exit
939	} // for
940	} // exit
941	if ( Src2[Src2Start + i] != Src1[Src1Start+ i]) {
942	cmp = Src1[Src1Start + i] > Src2[Src2Start + i] ? 1 : -1;
943	break CharZip;
944	} // exit
945	} // for
946	#ifdef VbyteDebug
947	serr \| "exit:ByteCmp, cmp:" \| cmp;
948	#endif // VbyteDebug
949	return cmp;
950	} // ByteCmp
951
952
953	// The compaction moves all of the byte strings currently in use to the beginning of the byte-string area and modifies
954	// the handles to reflect the new positions of the byte strings. Compaction assumes that the handle list is in ascending
955	// order by pointers into the byte-string area. The strings associated with substrings do not have to be moved because
956	// the containing string has been moved. Hence, they only require that their string pointers be adjusted.
957
958	void compaction(VbyteHeap & this) with(this) {
959	HandleNode *h;
960	char obase, nbase, *limit;
961
962	NoOfCompactions += 1;
963	EndVbyte = StartVbyte;
964	h = Header.flink; // ignore header node
965	for (;;) {
966	ByteCopy( EndVbyte, 0, h->lnth, h->s, 0, h->lnth );
967	obase = h->s;
968	h->s = EndVbyte;
969	nbase = h->s;
970	EndVbyte += h->lnth;
971	limit = obase + h->lnth;
972	h = h->flink;
973
974	// check if any substrings are allocated within a string
975
976	for (;;) {
977	if ( h == &Header ) break; // end of header list ?
978	if ( h->s >= limit ) break; // outside of current string ?
979	h->s = nbase + (( uintptr_t )h->s - ( uintptr_t )obase );
980	h = h->flink;
981	} // for
982	if ( h == &Header ) break; // end of header list ?
983	} // for
984	} // compaction
985
986
987	// Garbage determines the amount of free space left in the heap and then reduces, leave the same, or extends the size of
988	// the heap. The heap is then compacted in the existing heap or into the newly allocated heap.
989
990	void garbage(VbyteHeap & this, int minreq ) with(this) {
991	#ifdef VbyteDebug
992	serr \| "enter:garbage";
993	{
994	serr \| "HandleList:";
995	for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) {
996	serr \| nlOff;
997	serr \| "\tnode:" \| n \| " lnth:" \| n->lnth \| " s:" \| (void *)n->s \| ",\"";
998	for ( int i = 0; i < n->lnth; i += 1 ) {
999	serr \| n->s[i];
1000	} // for
1001	serr \| nlOn;
1002	serr \| "\" flink:" \| n->flink \| " blink:" \| n->blink;
1003	} // for
1004	}
1005	#endif // VbyteDebug
1006	int AmountUsed, AmountFree;
1007
1008	AmountUsed = 0;
1009	for ( HandleNode *i = Header.flink; i != &Header; i = i->flink ) { // calculate amount of byte area used
1010	AmountUsed += i->lnth;
1011	} // for
1012	AmountFree = ( uintptr_t )ExtVbyte - ( uintptr_t )StartVbyte - AmountUsed;
1013
1014	if ( ( double ) AmountFree < ( CurrSize * 0.1 ) \|\| AmountFree < minreq ) { // free space less than 10% or not enough to serve cur request
1015
1016	extend( this, max( CurrSize, minreq ) ); // extend the heap
1017
1018	// Peter says, "This needs work before it should be used."
1019	// } else if ( AmountFree > CurrSize / 2 ) { // free space greater than 3 times the initial allocation ?
1020	// reduce(( AmountFree / CurrSize - 3 ) * CurrSize ); // reduce the memory
1021
1022	} // if
1023	compaction(this); // compact the byte area, in the same or new heap area
1024	#ifdef VbyteDebug
1025	{
1026	serr \| "HandleList:";
1027	for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) {
1028	serr \| nlOff;
1029	serr \| "\tnode:" \| n \| " lnth:" \| n->lnth \| " s:" \| (void *)n->s \| ",\"";
1030	for ( int i = 0; i < n->lnth; i += 1 ) {
1031	serr \| n->s[i];
1032	} // for
1033	serr \| nlOn;
1034	serr \| "\" flink:" \| n->flink \| " blink:" \| n->blink;
1035	} // for
1036	}
1037	serr \| "exit:garbage";
1038	#endif // VbyteDebug
1039	} // garbage
1040
1041	#undef VbyteDebug
1042
1043
1044
1045	// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string
1046	// area is deleted.
1047
1048	void extend( VbyteHeap & this, int size ) with (this) {
1049	#ifdef VbyteDebug
1050	serr \| "enter:extend, size:" \| size;
1051	#endif // VbyteDebug
1052	char *OldStartVbyte;
1053
1054	NoOfExtensions += 1;
1055	OldStartVbyte = StartVbyte; // save previous byte area
1056
1057	CurrSize += size > InitSize ? size : InitSize; // minimum extension, initial size
1058	StartVbyte = EndVbyte = alloc(CurrSize);
1059	ExtVbyte = (void *)( StartVbyte + CurrSize );
1060	compaction(this); // copy from old heap to new & adjust pointers to new heap
1061	free( OldStartVbyte ); // release old heap
1062	#ifdef VbyteDebug
1063	serr \| "exit:extend, CurrSize:" \| CurrSize;
1064	#endif // VbyteDebug
1065	} // extend
1066
1067	//WIP
1068	#if 0
1069
1070	// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string
1071	// area is deleted.
1072
1073	void VbyteHeap::reduce( int size ) {
1074	#ifdef VbyteDebug
1075	serr \| "enter:reduce, size:" \| size;
1076	#endif // VbyteDebug
1077	char *OldStartVbyte;
1078
1079	NoOfReductions += 1;
1080	OldStartVbyte = StartVbyte; // save previous byte area
1081
1082	CurrSize -= size;
1083	StartVbyte = EndVbyte = new char[CurrSize];
1084	ExtVbyte = (void *)( StartVbyte + CurrSize );
1085	compaction(); // copy from old heap to new & adjust pointers to new heap
1086	delete OldStartVbyte; // release old heap
1087	#ifdef VbyteDebug
1088	serr \| "exit:reduce, CurrSize:" \| CurrSize;
1089	#endif // VbyteDebug
1090	} // reduce
1091
1092
1093	#endif

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

Download in other formats:

Original Format