Context Navigation

string_res.cfa @ 7b0e8b7

ADTast-experimentalenumpthread-emulationqualifiedEnum

Last change on this file since 7b0e8b7 was 7b0e8b7, checked in by Michael Brooks <mlbrooks@…>, 3 years ago
String heap growth implemented
Property mode set to `100644`
File size: 35.0 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
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	// General copy constructor
261	void ?{}(string_res &s, const string_res & s2, StrResInitMode mode, size_t start, size_t end ) {
262
263	verify( start <= end && end <= s2.Handle.lnth );
264
265	if (s2.Handle.ulink == ambient_string_sharectx->activeHeap) {
266	// same heap: allow overlap
267	(s.Handle){};
268	s.Handle.s = s2.Handle.s + start;
269	s.Handle.lnth = end - start;
270	s.Handle.ulink = ambient_string_sharectx->activeHeap;
271	(s.shareEditSet_owns_ulink){ false };
272	AddThisAfter(s.Handle, s2.Handle ); // insert this handle after rhs handle
273	// ^ bug? skip others at early point in string
274
275	if (mode == COPY_VALUE) {
276	// make s alone in its shareEditSet
277	s.shareEditSet_prev = &s;
278	s.shareEditSet_next = &s;
279	} else {
280	verify( mode == SHARE_EDITS );
281
282	// s2 is logically const but not implementation const
283	string_res & s2mod = (string_res &) s2;
284
285	// insert s after s2 on shareEditSet
286	s.shareEditSet_next = s2mod.shareEditSet_next;
287	s.shareEditSet_prev = &s2mod;
288	s.shareEditSet_next->shareEditSet_prev = &s;
289	s.shareEditSet_prev->shareEditSet_next = &s;
290	}
291	} else {
292	// crossing heaps: eager copy
293	assert( mode == COPY_VALUE && "need to solidify context-crossing rules for requesting shared edits");
294	eagerCopyCtorHelper(s, s2.Handle.s + start, end - start);
295	verify(s.shareEditSet_prev == &s);
296	verify(s.shareEditSet_next == &s);
297	}
298	}
299
300	static void assignEditSet(string_res & this, string_res * shareEditSetStartPeer, string_res * shareEditSetEndPeer,
301	char * resultSesStart,
302	size_t resultSesLnth,
303	HandleNode * resultPadPosition, size_t bsize ) {
304
305	char * beforeBegin = shareEditSetStartPeer->Handle.s;
306	size_t beforeLen = this.Handle.s - beforeBegin;
307
308	char * afterBegin = this.Handle.s + this.Handle.lnth;
309	size_t afterLen = shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - afterBegin;
310
311	size_t oldLnth = this.Handle.lnth;
312
313	this.Handle.s = resultSesStart + beforeLen;
314	this.Handle.lnth = bsize;
315	MoveThisAfter( this.Handle, *resultPadPosition );
316
317	// adjust all substring string and handle locations, and check if any substring strings are outside the new base string
318	char *limit = resultSesStart + resultSesLnth;
319	for (string_res * p = this.shareEditSet_next; p != &this; p = p->shareEditSet_next) {
320	verify (p->Handle.s >= beforeBegin);
321	if ( p->Handle.s >= afterBegin ) {
322	verify ( p->Handle.s <= afterBegin + afterLen );
323	verify ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen );
324	// p starts after the edit
325	// take start and end as end-anchored
326	size_t startOffsetFromEnd = afterBegin + afterLen - p->Handle.s;
327	p->Handle.s = limit - startOffsetFromEnd;
328	// p->Handle.lnth unaffected
329	} else if ( p->Handle.s <= beforeBegin + beforeLen ) {
330	// p starts before, or at the start of, the edit
331	if ( p->Handle.s + p->Handle.lnth <= beforeBegin + beforeLen ) {
332	// p ends before the edit
333	// take end as start-anchored too
334	// p->Handle.lnth unaffected
335	} else if ( p->Handle.s + p->Handle.lnth < afterBegin ) {
336	// p ends during the edit; p does not include the last character replaced
337	// clip end of p to end at start of edit
338	p->Handle.lnth = beforeLen - ( p->Handle.s - beforeBegin );
339	} else {
340	// p ends after the edit
341	verify ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen );
342	// take end as end-anchored
343	// stretch-shrink p according to the edit
344	p->Handle.lnth += this.Handle.lnth;
345	p->Handle.lnth -= oldLnth;
346	}
347	// take start as start-anchored
348	size_t startOffsetFromStart = p->Handle.s - beforeBegin;
349	p->Handle.s = resultSesStart + startOffsetFromStart;
350	} else {
351	verify ( p->Handle.s < afterBegin );
352	// p starts during the edit
353	verify( p->Handle.s + p->Handle.lnth >= beforeBegin + beforeLen );
354	if ( p->Handle.s + p->Handle.lnth < afterBegin ) {
355	// p ends during the edit; p does not include the last character replaced
356	// set p to empty string at start of edit
357	p->Handle.s = this.Handle.s;
358	p->Handle.lnth = 0;
359	} else {
360	// p includes the end of the edit
361	// clip start of p to start at end of edit
362	int charsToClip = afterBegin - p->Handle.s;
363	p->Handle.s = this.Handle.s + this.Handle.lnth;
364	p->Handle.lnth -= charsToClip;
365	}
366	}
367	MoveThisAfter( p->Handle, *resultPadPosition ); // move substring handle to maintain sorted order by string position
368	}
369	}
370
371	static void assign_(string_res &this, const char* buffer, size_t bsize, const string_res & valSrc) {
372
373	// traverse the incumbent share-edit set (SES) to recover the range of a base string to which `this` belongs
374	string_res * shareEditSetStartPeer = & this;
375	string_res * shareEditSetEndPeer = & this;
376	for (string_res * editPeer = this.shareEditSet_next; editPeer != &this; editPeer = editPeer->shareEditSet_next) {
377	if ( editPeer->Handle.s < shareEditSetStartPeer->Handle.s ) {
378	shareEditSetStartPeer = editPeer;
379	}
380	if ( shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth < editPeer->Handle.s + editPeer->Handle.lnth) {
381	shareEditSetEndPeer = editPeer;
382	}
383	}
384
385	verify( shareEditSetEndPeer->Handle.s >= shareEditSetStartPeer->Handle.s );
386	size_t editSetLength = shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - shareEditSetStartPeer->Handle.s;
387	verify( editSetLength >= this.Handle.lnth );
388
389
390	if ( this.Handle.lnth == editSetLength // the entire run of the share-edit set is being overwritten: SES's result will only use characters from the source string
391	&& & valSrc // sourcing from a managed string
392	&& valSrc.Handle.ulink == this.Handle.ulink ) { // sourcing from same heap
393
394	assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer,
395	valSrc.Handle.s,
396	valSrc.Handle.lnth,
397	&((string_res&)valSrc).Handle, bsize);
398
399	} else {
400
401	// full string is from start of shareEditSetStartPeer thru end of shareEditSetEndPeer
402	// `this` occurs in the middle of it, to be replaced
403	// build up the new text in `pasting`
404
405	// super private string ctor: ignore ambient context
406	void ?{}( string_res &s, VbyteHeap & heap, const char* rhs, size_t rhslnth ) with(s) {
407	(Handle){ heap };
408	Handle.s = VbyteAlloc(*Handle.ulink, rhslnth);
409	Handle.lnth = rhslnth;
410	(s.shareEditSet_owns_ulink){ false };
411	for ( int i = 0; i < rhslnth; i += 1 ) { // copy characters
412	Handle.s[i] = rhs[i];
413	} // for
414	s.shareEditSet_prev = &s;
415	s.shareEditSet_next = &s;
416	}
417
418	// we are only overwriting a proper substring of some string: need to mash characters from old and new together
419	// OR we are importing characters: need to copy eagerly
420	string_res pasting = {
421	* this.Handle.ulink, // maintain same heap, regardless of context
422	shareEditSetStartPeer->Handle.s, // start of SES
423	this.Handle.s - shareEditSetStartPeer->Handle.s }; // length of SES, before this
424	append( pasting,
425	buffer, // start of replacement for this
426	bsize ); // length of replacement for this
427	append( pasting,
428	this.Handle.s + this.Handle.lnth, // start of SES after this
429	shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth -
430	(this.Handle.s + this.Handle.lnth) ); // length of SES, after this
431
432	// The above string building can trigger compaction.
433	// The reference points (that are arguments of the string building) may move during that building.
434	// From this point on, they are stable.
435
436	assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer,
437	pasting.Handle.s,
438	pasting.Handle.lnth,
439	&pasting.Handle, bsize);
440	}
441
442	// So now, capture their values for use in the overlap cases, below.
443	// Do not factor these definitions with the arguments used in string building above.
444
445	}
446
447	void assign(string_res &this, const char* buffer, size_t bsize) {
448	assign_(this, buffer, bsize, *0p);
449	}
450
451	void ?=?(string_res &s, const char* other) {
452	assign(s, other, strlen(other));
453	}
454
455	void ?=?(string_res &s, char other) {
456	assign(s, &other, 1);
457	}
458
459	// Copy assignment operator
460	void ?=?(string_res & this, const string_res & rhs) with( this ) {
461	assign_(this, rhs.Handle.s, rhs.Handle.lnth, rhs);
462	}
463
464	void ?=?(string_res & this, string_res & rhs) with( this ) {
465	const string_res & rhs2 = rhs;
466	this = rhs2;
467	}
468
469
470	// Destructor
471	void ^?{}(string_res &s) with(s) {
472	// much delegated to implied ^VbyteSM
473
474	// sever s from its share-edit peers, if any (four no-ops when already solo)
475	s.shareEditSet_prev->shareEditSet_next = s.shareEditSet_next;
476	s.shareEditSet_next->shareEditSet_prev = s.shareEditSet_prev;
477	// s.shareEditSet_next = &s;
478	// s.shareEditSet_prev = &s;
479
480	if (shareEditSet_owns_ulink && s.shareEditSet_next == &s) { // last one out
481	delete( s.Handle.ulink );
482	}
483	}
484
485
486	// Returns the character at the given index
487	// With unicode support, this may be different from just the byte at the given
488	// offset from the start of the string.
489	char ?[?](const string_res &s, size_t index) with(s) {
490	//TODO: Check if index is valid (no exceptions yet)
491	return Handle.s[index];
492	}
493
494	void assignAt(const string_res &s, size_t index, char val) {
495	string_res editZone = { s, SHARE_EDITS, index, index+1 };
496	assign(editZone, &val, 1);
497	}
498
499
500	///////////////////////////////////////////////////////////////////
501	// Concatenation
502
503	void append(string_res &str1, const char * buffer, size_t bsize) {
504	size_t clnth = size(str1) + bsize;
505	if ( str1.Handle.s + size(str1) == buffer ) { // already juxtapose ?
506	// no-op
507	} else { // must copy some text
508	if ( str1.Handle.s + size(str1) == VbyteAlloc(*str1.Handle.ulink, 0) ) { // str1 at end of string area ?
509	VbyteAlloc( *str1.Handle.ulink, bsize ); // create room for 2nd part at the end of string area
510	} else { // copy the two parts
511	char * str1oldBuf = str1.Handle.s;
512	str1.Handle.s = VbyteAlloc( *str1.Handle.ulink, clnth );
513	ByteCopy( str1.Handle.s, 0, str1.Handle.lnth, str1oldBuf, 0, str1.Handle.lnth);
514	} // if
515	ByteCopy( str1.Handle.s, str1.Handle.lnth, bsize, (char*)buffer, 0, (int)bsize);
516	// VbyteHeap & this, char Dst, int DstStart, int DstLnth, char Src, int SrcStart, int SrcLnth
517	} // if
518	str1.Handle.lnth = clnth;
519	}
520
521	void ?+=?(string_res &str1, const string_res &str2) {
522	append( str1, str2.Handle.s, str2.Handle.lnth );
523	}
524
525	void ?+=?(string_res &s, char other) {
526	append( s, &other, 1 );
527	}
528
529	void ?+=?(string_res &s, const char* other) {
530	append( s, other, strlen(other) );
531	}
532
533
534
535
536	//////////////////////////////////////////////////////////
537	// Comparisons
538
539
540	bool ?==?(const string_res &s1, const string_res &s2) {
541	return ByteCmp( s1.Handle.s, 0, s1.Handle.lnth, s2.Handle.s, 0, s2.Handle.lnth) == 0;
542	}
543
544	bool ?!=?(const string_res &s1, const string_res &s2) {
545	return !(s1 == s2);
546	}
547	bool ?==?(const string_res &s, const char* other) {
548	string_res sother = other;
549	return s == sother;
550	}
551	bool ?!=?(const string_res &s, const char* other) {
552	return !(s == other);
553	}
554
555
556	//////////////////////////////////////////////////////////
557	// Search
558
559	bool contains(const string_res &s, char ch) {
560	for (i; size(s)) {
561	if (s[i] == ch) return true;
562	}
563	return false;
564	}
565
566	int find(const string_res &s, char search) {
567	for (i; size(s)) {
568	if (s[i] == search) return i;
569	}
570	return size(s);
571	}
572
573	/* Remaining implementations essentially ported from Sunjay's work */
574
575	int find(const string_res &s, const string_res &search) {
576	return find(s, search.Handle.s, search.Handle.lnth);
577	}
578
579	int find(const string_res &s, const char* search) {
580	return find(s, search, strlen(search));
581	}
582
583	int find(const string_res &s, const char* search, size_t searchsize) {
584	// FIXME: This is a naive algorithm. We probably want to switch to someting
585	// like Boyer-Moore in the future.
586	// https://en.wikipedia.org/wiki/String_searching_algorithm
587
588	// Always find the empty string
589	if (searchsize == 0) {
590	return 0;
591	}
592
593	for (size_t i = 0; i < s.Handle.lnth; i++) {
594	size_t remaining = s.Handle.lnth - i;
595	// Never going to find the search string if the remaining string is
596	// smaller than search
597	if (remaining < searchsize) {
598	break;
599	}
600
601	bool matched = true;
602	for (size_t j = 0; j < searchsize; j++) {
603	if (search[j] != s.Handle.s[i + j]) {
604	matched = false;
605	break;
606	}
607	}
608	if (matched) {
609	return i;
610	}
611	}
612
613	return s.Handle.lnth;
614	}
615
616	bool includes(const string_res &s, const string_res &search) {
617	return includes(s, search.Handle.s, search.Handle.lnth);
618	}
619
620	bool includes(const string_res &s, const char* search) {
621	return includes(s, search, strlen(search));
622	}
623
624	bool includes(const string_res &s, const char* search, size_t searchsize) {
625	return find(s, search, searchsize) < s.Handle.lnth;
626	}
627
628	bool startsWith(const string_res &s, const string_res &prefix) {
629	return startsWith(s, prefix.Handle.s, prefix.Handle.lnth);
630	}
631
632	bool startsWith(const string_res &s, const char* prefix) {
633	return startsWith(s, prefix, strlen(prefix));
634	}
635
636	bool startsWith(const string_res &s, const char* prefix, size_t prefixsize) {
637	if (s.Handle.lnth < prefixsize) {
638	return false;
639	}
640	return memcmp(s.Handle.s, prefix, prefixsize) == 0;
641	}
642
643	bool endsWith(const string_res &s, const string_res &suffix) {
644	return endsWith(s, suffix.Handle.s, suffix.Handle.lnth);
645	}
646
647	bool endsWith(const string_res &s, const char* suffix) {
648	return endsWith(s, suffix, strlen(suffix));
649	}
650
651	bool endsWith(const string_res &s, const char* suffix, size_t suffixsize) {
652	if (s.Handle.lnth < suffixsize) {
653	return false;
654	}
655	// Amount to offset the bytes pointer so that we are comparing the end of s
656	// to suffix. s.bytes + offset should be the first byte to compare against suffix
657	size_t offset = s.Handle.lnth - suffixsize;
658	return memcmp(s.Handle.s + offset, suffix, suffixsize) == 0;
659	}
660
661	/* Back to Mike's work */
662
663
664	///////////////////////////////////////////////////////////////////////////
665	// charclass, include, exclude
666
667	void ?{}( charclass_res & this, const string_res & chars) {
668	(this){ chars.Handle.s, chars.Handle.lnth };
669	}
670
671	void ?{}( charclass_res & this, const char * chars ) {
672	(this){ chars, strlen(chars) };
673	}
674
675	void ?{}( charclass_res & this, const char * chars, size_t charssize ) {
676	(this.chars){ chars, charssize };
677	// now sort it ?
678	}
679
680	void ^?{}( charclass_res & this ) {
681	^(this.chars){};
682	}
683
684	static bool test( const charclass_res & mask, char c ) {
685	// instead, use sorted char list?
686	return contains( mask.chars, c );
687	}
688
689	int exclude(const string_res &s, const charclass_res &mask) {
690	for (int i = 0; i < size(s); i++) {
691	if ( test(mask, s[i]) ) return i;
692	}
693	return size(s);
694	}
695
696	int include(const string_res &s, const charclass_res &mask) {
697	for (int i = 0; i < size(s); i++) {
698	if ( ! test(mask, s[i]) ) return i;
699	}
700	return size(s);
701	}
702
703	//######################### VbyteHeap "implementation" #########################
704
705
706	// Add a new HandleNode node n after the current HandleNode node.
707
708	static inline void AddThisAfter( HandleNode & this, HandleNode & n ) with(this) {
709	#ifdef VbyteDebug
710	serr \| "enter:AddThisAfter, this:" \| &this \| " n:" \| &n;
711	#endif // VbyteDebug
712	verify( n.ulink != 0p );
713	verify( this.ulink == n.ulink );
714	flink = n.flink;
715	blink = &n;
716	n.flink->blink = &this;
717	n.flink = &this;
718	#ifdef VbyteDebug
719	{
720	serr \| "HandleList:";
721	serr \| nlOff;
722	for ( HandleNode *ni = HeaderPtr->flink; ni != HeaderPtr; ni = ni->flink ) {
723	serr \| "\tnode:" \| ni \| " lnth:" \| ni->lnth \| " s:" \| (void *)ni->s \| ",\"";
724	for ( int i = 0; i < ni->lnth; i += 1 ) {
725	serr \| ni->s[i];
726	} // for
727	serr \| "\" flink:" \| ni->flink \| " blink:" \| ni->blink \| nl;
728	} // for
729	serr \| nlOn;
730	}
731	serr \| "exit:AddThisAfter";
732	#endif // VbyteDebug
733	} // AddThisAfter
734
735
736	// Delete the current HandleNode node.
737
738	static inline void DeleteNode( HandleNode & this ) with(this) {
739	#ifdef VbyteDebug
740	serr \| "enter:DeleteNode, this:" \| &this;
741	#endif // VbyteDebug
742	flink->blink = blink;
743	blink->flink = flink;
744	#ifdef VbyteDebug
745	serr \| "exit:DeleteNode";
746	#endif // VbyteDebug
747	} // DeleteNode
748
749
750
751	// Allocates specified storage for a string from byte-string area. If not enough space remains to perform the
752	// allocation, the garbage collection routine is called and a second attempt is made to allocate the space. If the
753	// second attempt fails, a further attempt is made to create a new, larger byte-string area.
754
755	static inline char * VbyteAlloc( VbyteHeap & this, int size ) with(this) {
756	#ifdef VbyteDebug
757	serr \| "enter:VbyteAlloc, size:" \| size;
758	#endif // VbyteDebug
759	uintptr_t NoBytes;
760	char *r;
761
762	NoBytes = ( uintptr_t )EndVbyte + size;
763	if ( NoBytes > ( uintptr_t )ExtVbyte ) { // enough room for new byte-string ?
764	garbage( this, size ); // firer up the garbage collector
765	NoBytes = ( uintptr_t )EndVbyte + size; // try again
766	if ( NoBytes > ( uintptr_t )ExtVbyte ) { // enough room for new byte-string ?
767	assert( 0 && "garbage run did not free up required space" );
768	} // if
769	} // if
770	r = EndVbyte;
771	EndVbyte += size;
772	#ifdef VbyteDebug
773	serr \| "exit:VbyteAlloc, r:" \| (void )r \| " EndVbyte:" \| (void )EndVbyte \| " ExtVbyte:" \| ExtVbyte;
774	#endif // VbyteDebug
775	return r;
776	} // VbyteAlloc
777
778
779	// Move an existing HandleNode node h somewhere after the current HandleNode node so that it is in ascending order by
780	// the address in the byte string area.
781
782	static inline void MoveThisAfter( HandleNode & this, const HandleNode & h ) with(this) {
783	#ifdef VbyteDebug
784	serr \| "enter:MoveThisAfter, this:" \| & this \| " h:" \| & h;
785	#endif // VbyteDebug
786	verify( h.ulink != 0p );
787	verify( this.ulink == h.ulink );
788	if ( s < h.s ) { // check argument values
789	// serr \| "VbyteSM: Error - Cannot move byte string starting at:" \| s \| " after byte string starting at:"
790	// \| ( h->s ) \| " and keep handles in ascending order";
791	// exit(-1 );
792	verify( 0 && "VbyteSM: Error - Cannot move byte strings as requested and keep handles in ascending order");
793	} // if
794
795	HandleNode *i;
796	for ( i = h.flink; i->s != 0 && s > ( i->s ); i = i->flink ); // find the position for this node after h
797	if ( & this != i->blink ) {
798	DeleteNode( this );
799	AddThisAfter( this, *i->blink );
800	} // if
801	#ifdef VbyteDebug
802	{
803	serr \| "HandleList:";
804	serr \| nlOff;
805	for ( HandleNode *n = HeaderPtr->flink; n != HeaderPtr; n = n->flink ) {
806	serr \| "\tnode:" \| n \| " lnth:" \| n->lnth \| " s:" \| (void *)n->s \| ",\"";
807	for ( int i = 0; i < n->lnth; i += 1 ) {
808	serr \| n->s[i];
809	} // for
810	serr \| "\" flink:" \| n->flink \| " blink:" \| n->blink \| nl;
811	} // for
812	serr \| nlOn;
813	}
814	serr \| "exit:MoveThisAfter";
815	#endif // VbyteDebug
816	} // MoveThisAfter
817
818
819
820
821
822	//######################### VbyteHeap #########################
823
824	// Move characters from one location in the byte-string area to another. The routine handles the following situations:
825	//
826	// if the \|Src\| > \|Dst\| => truncate
827	// if the \|Dst\| > \|Src\| => pad Dst with blanks
828
829	void ByteCopy( char Dst, int DstStart, int DstLnth, char Src, int SrcStart, int SrcLnth ) {
830	for ( int i = 0; i < DstLnth; i += 1 ) {
831	if ( i == SrcLnth ) { // \|Dst\| > \|Src\|
832	for ( ; i < DstLnth; i += 1 ) { // pad Dst with blanks
833	Dst[DstStart + i] = ' ';
834	} // for
835	break;
836	} // exit
837	Dst[DstStart + i] = Src[SrcStart + i];
838	} // for
839	} // ByteCopy
840
841	// Compare two byte strings in the byte-string area. The routine returns the following values:
842	//
843	// 1 => Src1-byte-string > Src2-byte-string
844	// 0 => Src1-byte-string = Src2-byte-string
845	// -1 => Src1-byte-string < Src2-byte-string
846
847	int ByteCmp( char Src1, int Src1Start, int Src1Lnth, char Src2, int Src2Start, int Src2Lnth ) {
848	#ifdef VbyteDebug
849	serr \| "enter:ByteCmp, Src1Start:" \| Src1Start \| " Src1Lnth:" \| Src1Lnth \| " Src2Start:" \| Src2Start \| " Src2Lnth:" \| Src2Lnth;
850	#endif // VbyteDebug
851	int cmp;
852
853	CharZip: for ( int i = 0; ; i += 1 ) {
854	if ( i == Src2Lnth - 1 ) {
855	for ( ; ; i += 1 ) {
856	if ( i == Src1Lnth - 1 ) {
857	cmp = 0;
858	break CharZip;
859	} // exit
860	if ( Src1[Src1Start + i] != ' ') {
861	// SUSPECTED BUG: this could be be why Peter got the bug report about == " " (why is this case here at all?)
862	cmp = 1;
863	break CharZip;
864	} // exit
865	} // for
866	} // exit
867	if ( i == Src1Lnth - 1 ) {
868	for ( ; ; i += 1 ) {
869	if ( i == Src2Lnth - 1 ) {
870	cmp = 0;
871	break CharZip;
872	} // exit
873	if ( Src2[Src2Start + i] != ' ') {
874	cmp = -1;
875	break CharZip;
876	} // exit
877	} // for
878	} // exit
879	if ( Src2[Src2Start + i] != Src1[Src1Start+ i]) {
880	cmp = Src1[Src1Start + i] > Src2[Src2Start + i] ? 1 : -1;
881	break CharZip;
882	} // exit
883	} // for
884	#ifdef VbyteDebug
885	serr \| "exit:ByteCmp, cmp:" \| cmp;
886	#endif // VbyteDebug
887	return cmp;
888	} // ByteCmp
889
890
891	// The compaction moves all of the byte strings currently in use to the beginning of the byte-string area and modifies
892	// the handles to reflect the new positions of the byte strings. Compaction assumes that the handle list is in ascending
893	// order by pointers into the byte-string area. The strings associated with substrings do not have to be moved because
894	// the containing string has been moved. Hence, they only require that their string pointers be adjusted.
895
896	void compaction(VbyteHeap & this) with(this) {
897	HandleNode *h;
898	char obase, nbase, *limit;
899
900	NoOfCompactions += 1;
901	EndVbyte = StartVbyte;
902	h = Header.flink; // ignore header node
903	for (;;) {
904	ByteCopy( EndVbyte, 0, h->lnth, h->s, 0, h->lnth );
905	obase = h->s;
906	h->s = EndVbyte;
907	nbase = h->s;
908	EndVbyte += h->lnth;
909	limit = obase + h->lnth;
910	h = h->flink;
911
912	// check if any substrings are allocated within a string
913
914	for (;;) {
915	if ( h == &Header ) break; // end of header list ?
916	if ( h->s >= limit ) break; // outside of current string ?
917	h->s = nbase + (( uintptr_t )h->s - ( uintptr_t )obase );
918	h = h->flink;
919	} // for
920	if ( h == &Header ) break; // end of header list ?
921	} // for
922	} // compaction
923
924
925	// Garbage determines the amount of free space left in the heap and then reduces, leave the same, or extends the size of
926	// the heap. The heap is then compacted in the existing heap or into the newly allocated heap.
927
928	void garbage(VbyteHeap & this, int minreq ) with(this) {
929	#ifdef VbyteDebug
930	serr \| "enter:garbage";
931	{
932	serr \| "HandleList:";
933	for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) {
934	serr \| nlOff;
935	serr \| "\tnode:" \| n \| " lnth:" \| n->lnth \| " s:" \| (void *)n->s \| ",\"";
936	for ( int i = 0; i < n->lnth; i += 1 ) {
937	serr \| n->s[i];
938	} // for
939	serr \| nlOn;
940	serr \| "\" flink:" \| n->flink \| " blink:" \| n->blink;
941	} // for
942	}
943	#endif // VbyteDebug
944	int AmountUsed, AmountFree;
945
946	AmountUsed = 0;
947	for ( HandleNode *i = Header.flink; i != &Header; i = i->flink ) { // calculate amount of byte area used
948	AmountUsed += i->lnth;
949	} // for
950	AmountFree = ( uintptr_t )ExtVbyte - ( uintptr_t )StartVbyte - AmountUsed;
951
952	if ( ( double ) AmountFree < ( CurrSize * 0.1 ) \|\| AmountFree < minreq ) { // free space less than 10% or not enough to serve cur request
953
954	extend( this, max( CurrSize, minreq ) ); // extend the heap
955
956	// Peter says, "This needs work before it should be used."
957	// } else if ( AmountFree > CurrSize / 2 ) { // free space greater than 3 times the initial allocation ?
958	// reduce(( AmountFree / CurrSize - 3 ) * CurrSize ); // reduce the memory
959
960	} // if
961	compaction(this); // compact the byte area, in the same or new heap area
962	#ifdef VbyteDebug
963	{
964	serr \| "HandleList:";
965	for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) {
966	serr \| nlOff;
967	serr \| "\tnode:" \| n \| " lnth:" \| n->lnth \| " s:" \| (void *)n->s \| ",\"";
968	for ( int i = 0; i < n->lnth; i += 1 ) {
969	serr \| n->s[i];
970	} // for
971	serr \| nlOn;
972	serr \| "\" flink:" \| n->flink \| " blink:" \| n->blink;
973	} // for
974	}
975	serr \| "exit:garbage";
976	#endif // VbyteDebug
977	} // garbage
978
979	#undef VbyteDebug
980
981
982
983	// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string
984	// area is deleted.
985
986	void extend( VbyteHeap & this, int size ) with (this) {
987	#ifdef VbyteDebug
988	serr \| "enter:extend, size:" \| size;
989	#endif // VbyteDebug
990	char *OldStartVbyte;
991
992	NoOfExtensions += 1;
993	OldStartVbyte = StartVbyte; // save previous byte area
994
995	CurrSize += size > InitSize ? size : InitSize; // minimum extension, initial size
996	StartVbyte = EndVbyte = alloc(CurrSize);
997	ExtVbyte = (void *)( StartVbyte + CurrSize );
998	compaction(this); // copy from old heap to new & adjust pointers to new heap
999	free( OldStartVbyte ); // release old heap
1000	#ifdef VbyteDebug
1001	serr \| "exit:extend, CurrSize:" \| CurrSize;
1002	#endif // VbyteDebug
1003	} // extend
1004
1005	//WIP
1006	#if 0
1007
1008	// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string
1009	// area is deleted.
1010
1011	void VbyteHeap::reduce( int size ) {
1012	#ifdef VbyteDebug
1013	serr \| "enter:reduce, size:" \| size;
1014	#endif // VbyteDebug
1015	char *OldStartVbyte;
1016
1017	NoOfReductions += 1;
1018	OldStartVbyte = StartVbyte; // save previous byte area
1019
1020	CurrSize -= size;
1021	StartVbyte = EndVbyte = new char[CurrSize];
1022	ExtVbyte = (void *)( StartVbyte + CurrSize );
1023	compaction(); // copy from old heap to new & adjust pointers to new heap
1024	delete OldStartVbyte; // release old heap
1025	#ifdef VbyteDebug
1026	serr \| "exit:reduce, CurrSize:" \| CurrSize;
1027	#endif // VbyteDebug
1028	} // reduce
1029
1030
1031	#endif

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

Download in other formats:

Original Format