Context Navigation

string_res.cfa@ 821c534

Visit:

ADT ast-experimental enum forall-pointer-decay pthread-emulation qualifiedEnum

Last change on this file since 821c534 was d8d512e, checked in by Michael Brooks <mlbrooks@…>, 4 years ago
Reorganizing string constructor/assignment overload calls for better performance.
Property mode set to `100644`
File size: 28.2 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 <stdlib.hfa> // e.g. malloc
18	#include <string.h> // e.g. strlen
19
20	//######################### VbyteHeap "header" #########################
21
22
23	#ifdef VbyteDebug
24	extern HandleNode *HeaderPtr;
25	#endif // VbyteDebug
26
27	struct VbyteHeap {
28
29	int NoOfCompactions; // number of compactions of the byte area
30	int NoOfExtensions; // number of extensions in the size of the byte area
31	int NoOfReductions; // number of reductions in the size of the byte area
32
33	int InitSize; // initial number of bytes in the byte-string area
34	int CurrSize; // current number of bytes in the byte-string area
35	char *StartVbyte; // pointer to the `st byte of the start of the byte-string area
36	char *EndVbyte; // pointer to the next byte after the end of the currently used portion of byte-string area
37	void *ExtVbyte; // pointer to the next byte after the end of the byte-string area
38
39	HandleNode Header; // header node for handle list
40	}; // VbyteHeap
41
42
43	static inline void compaction( VbyteHeap & ); // compaction of the byte area
44	static inline void garbage( VbyteHeap & ); // garbage collect the byte area
45	static inline void extend( VbyteHeap &, int ); // extend the size of the byte area
46	static inline void reduce( VbyteHeap &, int ); // reduce the size of the byte area
47
48	static inline void ?{}( VbyteHeap &, int = 1000 );
49	static inline void ^?{}( VbyteHeap & );
50	static inline void ByteCopy( VbyteHeap &, char , int, int, char , int, int ); // copy a block of bytes from one location in the heap to another
51	static inline int ByteCmp( VbyteHeap &, char , int, int, char , int, int ); // compare 2 blocks of bytes
52	static inline char *VbyteAlloc( VbyteHeap &, int ); // allocate a block bytes in the heap
53
54
55	static inline void AddThisAfter( HandleNode &, HandleNode & );
56	static inline void DeleteNode( HandleNode & );
57	static inline void MoveThisAfter( HandleNode &, const HandleNode & ); // move current handle after parameter handle
58
59
60	// Allocate the storage for the variable sized area and intialize the heap variables.
61
62	static inline void ?{}( VbyteHeap & this, int Size ) with(this) {
63	#ifdef VbyteDebug
64	serr \| "enter:VbyteHeap::VbyteHeap, this:" \| &this \| " Size:" \| Size;
65	#endif // VbyteDebug
66	NoOfCompactions = NoOfExtensions = NoOfReductions = 0;
67	InitSize = CurrSize = Size;
68	StartVbyte = EndVbyte = alloc(CurrSize);
69	ExtVbyte = (void *)( StartVbyte + CurrSize );
70	Header.flink = Header.blink = &Header;
71	#ifdef VbyteDebug
72	HeaderPtr = &Header;
73	serr \| "exit:VbyteHeap::VbyteHeap, this:" \| &this;
74	#endif // VbyteDebug
75	} // VbyteHeap
76
77
78	// Release the dynamically allocated storage for the byte area.
79
80	static inline void ^?{}( VbyteHeap & this ) with(this) {
81	free( StartVbyte );
82	} // ~VbyteHeap
83
84
85	//######################### HandleNode #########################
86
87
88	// Create a handle node. The handle is not linked into the handle list. This is the responsibilitiy of the handle
89	// creator.
90
91	void ?{}( HandleNode & this ) with(this) {
92	#ifdef VbyteDebug
93	serr \| "enter:HandleNode::HandleNode, this:" \| &this;
94	#endif // VbyteDebug
95	s = 0;
96	lnth = 0;
97	#ifdef VbyteDebug
98	serr \| "exit:HandleNode::HandleNode, this:" \| &this;
99	#endif // VbyteDebug
100	} // HandleNode
101
102	// Create a handle node. The handle is linked into the handle list at the end. This means that this handle will NOT be
103	// in order by string address, but this is not a problem because a string with length zero does nothing during garbage
104	// collection.
105
106	void ?{}( HandleNode & this, VbyteHeap & vh ) with(this) {
107	#ifdef VbyteDebug
108	serr \| "enter:HandleNode::HandleNode, this:" \| &this;
109	#endif // VbyteDebug
110	s = 0;
111	lnth = 0;
112	AddThisAfter( this, *vh.Header.blink );
113	#ifdef VbyteDebug
114	serr \| "exit:HandleNode::HandleNode, this:" \| &this;
115	#endif // VbyteDebug
116	} // HandleNode
117
118
119	// Delete a node from the handle list by unchaining it from the list. If the handle node was allocated dynamically, it
120	// is the responsibility of the creator to destroy it.
121
122	void ^?{}( HandleNode & this ) with(this) {
123	#ifdef VbyteDebug
124	serr \| "enter:HandleNode::~HandleNode, this:" \| & this;
125	{
126	serr \| nlOff;
127	serr \| " lnth:" \| lnth \| " s:" \| (void *)s \| ",\"";
128	for ( int i = 0; i < lnth; i += 1 ) {
129	serr \| s[i];
130	} // for
131	serr \| "\" flink:" \| flink \| " blink:" \| blink \| nl;
132	serr \| nlOn;
133	}
134	#endif // VbyteDebug
135	DeleteNode( this );
136	} // ~HandleNode
137
138	//######################### String Resource #########################
139
140
141	VbyteHeap HeapArea;
142
143	// Returns the size of the string in bytes
144	size_t size(const string_res &s) with(s) {
145	return Handle.lnth;
146	}
147
148	// Output operator
149	ofstream & ?\|?(ofstream &out, const string_res &s) {
150	// Store auto-newline state so it can be restored
151	bool anl = getANL$(out);
152	nlOff(out);
153	for (size_t i = 0; i < s.Handle.lnth; i++) {
154	out \| s[i];
155	}
156	out \| sep;
157	// Re-apply newlines after done, for chaining version
158	if (anl) nlOn(out);
159	return out;
160	}
161
162	void ?\|?(ofstream &out, const string_res &s) {
163	// Store auto-newline state so it can be restored
164	bool anl = getANL$(out);
165	nlOff(out);
166	for (size_t i = 0; i < s.Handle.lnth; i++) {
167	// Need to re-apply on the last output operator, for whole-statement version
168	if (anl && i == s.Handle.lnth-1) nlOn(out);
169	out \| s[i];
170	}
171	return out;
172	}
173
174	// Empty constructor
175	void ?{}(string_res &s) with(s) {
176	(Handle){ HeapArea };
177	s.shareEditSet_prev = &s;
178	s.shareEditSet_next = &s;
179	}
180
181	// Constructor from a raw buffer and size
182	void ?{}(string_res &s, const char* rhs, size_t rhslnth) with(s) {
183	(Handle){ HeapArea };
184	Handle.s = VbyteAlloc(HeapArea, rhslnth);
185	Handle.lnth = rhslnth;
186	for ( int i = 0; i < rhslnth; i += 1 ) { // copy characters
187	Handle.s[i] = rhs[i];
188	} // for
189	s.shareEditSet_prev = &s;
190	s.shareEditSet_next = &s;
191	}
192
193	// String literal constructor
194	void ?{}(string_res &s, const char* rhs) {
195	(s){ rhs, strlen(rhs) };
196	}
197
198	// General copy constructor
199	void ?{}(string_res &s, const string_res & s2, StrResInitMode mode, size_t start, size_t end ) {
200
201	(s.Handle){ HeapArea };
202	s.Handle.s = s2.Handle.s + start;
203	s.Handle.lnth = end - start;
204	MoveThisAfter(s.Handle, s2.Handle ); // insert this handle after rhs handle
205	// ^ bug? skip others at early point in string
206
207	if (mode == COPY_VALUE) {
208	// make s alone in its shareEditSet
209	s.shareEditSet_prev = &s;
210	s.shareEditSet_next = &s;
211	} else {
212	assert( mode == SHARE_EDITS );
213
214	// s2 is logically const but not implementation const
215	string_res & s2mod = (string_res &) s2;
216
217	// insert s after s2 on shareEditSet
218	s.shareEditSet_next = s2mod.shareEditSet_next;
219	s.shareEditSet_prev = &s2mod;
220	s.shareEditSet_next->shareEditSet_prev = &s;
221	s.shareEditSet_prev->shareEditSet_next = &s;
222	}
223	}
224
225	void assign(string_res &this, const char* buffer, size_t bsize) {
226
227	char * afterBegin = this.Handle.s + this.Handle.lnth;
228
229	char * shareEditSetStart = this.Handle.s;
230	char * shareEditSetEnd = afterBegin;
231	for (string_res * editPeer = this.shareEditSet_next; editPeer != &this; editPeer = editPeer->shareEditSet_next) {
232	shareEditSetStart = min( shareEditSetStart, editPeer->Handle.s );
233	shareEditSetEnd = max( shareEditSetStart, editPeer->Handle.s + editPeer->Handle.lnth);
234	}
235
236	char * beforeBegin = shareEditSetStart;
237	size_t beforeLen = this.Handle.s - shareEditSetStart;
238	size_t afterLen = shareEditSetEnd - afterBegin;
239
240	string_res pasting = { beforeBegin, beforeLen };
241	append(pasting, buffer, bsize);
242	string_res after = { afterBegin, afterLen }; // juxtaposed with in-progress pasting
243	pasting += after; // optimized case
244
245	size_t oldLnth = this.Handle.lnth;
246
247	this.Handle.s = pasting.Handle.s + beforeLen;
248	this.Handle.lnth = bsize;
249	MoveThisAfter( this.Handle, pasting.Handle );
250
251	// adjust all substring string and handle locations, and check if any substring strings are outside the new base string
252	char *limit = pasting.Handle.s + pasting.Handle.lnth;
253	for (string_res * p = this.shareEditSet_next; p != &this; p = p->shareEditSet_next) {
254	assert (p->Handle.s >= beforeBegin);
255	if ( p->Handle.s < beforeBegin + beforeLen ) {
256	// p starts before the edit
257	if ( p->Handle.s + p->Handle.lnth < beforeBegin + beforeLen ) {
258	// p ends before the edit
259	// take end as start-anchored too
260	// p->Handle.lnth unaffected
261	} else if ( p->Handle.s + p->Handle.lnth < afterBegin ) {
262	// p ends during the edit
263	// clip end of p to end at start of edit
264	p->Handle.lnth = beforeLen - ( p->Handle.s - beforeBegin );
265	} else {
266	// p ends after the edit
267	assert ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen );
268	// take end as end-anchored
269	// stretch-shrink p according to the edit
270	p->Handle.lnth += this.Handle.lnth;
271	p->Handle.lnth -= oldLnth;
272	}
273	// take start as start-anchored
274	size_t startOffsetFromStart = p->Handle.s - beforeBegin;
275	p->Handle.s = pasting.Handle.s + startOffsetFromStart;
276	} else if ( p->Handle.s < afterBegin ) {
277	// p starts during the edit
278	assert( p->Handle.s + p->Handle.lnth >= beforeBegin + beforeLen );
279	if ( p->Handle.s + p->Handle.lnth < afterBegin ) {
280	// p ends during the edit
281	// set p to empty string at start of edit
282	p->Handle.s = this.Handle.s;
283	p->Handle.lnth = 0;
284	} else {
285	// p ends after the edit
286	// clip start of p to start at end of edit
287	p->Handle.s = this.Handle.s + this.Handle.lnth;
288	p->Handle.lnth += this.Handle.lnth;
289	p->Handle.lnth -= oldLnth;
290	}
291	} else {
292	assert ( p->Handle.s <= afterBegin + afterLen );
293	assert ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen );
294	// p starts after the edit
295	// take start and end as end-anchored
296	size_t startOffsetFromEnd = afterBegin + afterLen - p->Handle.s;
297	p->Handle.s = limit - startOffsetFromEnd;
298	// p->Handle.lnth unaffected
299	}
300	MoveThisAfter( p->Handle, pasting.Handle ); // move substring handle to maintain sorted order by string position
301	}
302	}
303
304	void ?=?(string_res &s, const char* other) {
305	assign(s, other, strlen(other));
306	}
307
308	void ?=?(string_res &s, char other) {
309	assign(s, &other, 1);
310	}
311
312	// Copy assignment operator
313	void ?=?(string_res & this, const string_res & rhs) with( this ) {
314	assign(this, rhs.Handle.s, rhs.Handle.lnth);
315	}
316
317	void ?=?(string_res & this, string_res & rhs) with( this ) {
318	const string_res & rhs2 = rhs;
319	this = rhs2;
320	}
321
322
323	// Destructor
324	void ^?{}(string_res &s) with(s) {
325	// much delegated to implied ^VbyteSM
326
327	// sever s from its share-edit peers, if any (four no-ops when already solo)
328	s.shareEditSet_prev->shareEditSet_next = s.shareEditSet_next;
329	s.shareEditSet_next->shareEditSet_prev = s.shareEditSet_prev;
330	s.shareEditSet_next = &s;
331	s.shareEditSet_prev = &s;
332	}
333
334
335	// Returns the character at the given index
336	// With unicode support, this may be different from just the byte at the given
337	// offset from the start of the string.
338	char ?[?](const string_res &s, size_t index) with(s) {
339	//TODO: Check if index is valid (no exceptions yet)
340	return Handle.s[index];
341	}
342
343
344	///////////////////////////////////////////////////////////////////
345	// Concatenation
346
347	void append(string_res &str1, const char * buffer, size_t bsize) {
348	size_t clnth = size(str1) + bsize;
349	if ( str1.Handle.s + size(str1) == buffer ) { // already juxtapose ?
350	// no-op
351	} else { // must copy some text
352	if ( str1.Handle.s + size(str1) == VbyteAlloc(HeapArea, 0) ) { // str1 at end of string area ?
353	VbyteAlloc(HeapArea, bsize); // create room for 2nd part at the end of string area
354	} else { // copy the two parts
355	char * str1oldBuf = str1.Handle.s;
356	str1.Handle.s = VbyteAlloc( HeapArea, clnth );
357	ByteCopy( HeapArea, str1.Handle.s, 0, str1.Handle.lnth, str1oldBuf, 0, str1.Handle.lnth);
358	} // if
359	ByteCopy( HeapArea, str1.Handle.s, str1.Handle.lnth, bsize, (char*)buffer, 0, (int)bsize);
360	// VbyteHeap & this, char Dst, int DstStart, int DstLnth, char Src, int SrcStart, int SrcLnth
361	} // if
362	str1.Handle.lnth = clnth;
363	}
364
365	void ?+=?(string_res &str1, const string_res &str2) {
366	append( str1, str2.Handle.s, str2.Handle.lnth );
367	}
368
369	void ?+=?(string_res &s, char other) {
370	append( s, &other, 1 );
371	}
372
373	void ?+=?(string_res &s, const char* other) {
374	append( s, other, strlen(other) );
375	}
376
377
378
379
380	//////////////////////////////////////////////////////////
381	// Comparisons
382
383
384	bool ?==?(const string_res &s1, const string_res &s2) {
385	return ByteCmp( HeapArea, s1.Handle.s, 0, s1.Handle.lnth, s2.Handle.s, 0, s2.Handle.lnth) == 0;
386	}
387
388	bool ?!=?(const string_res &s1, const string_res &s2) {
389	return !(s1 == s2);
390	}
391	bool ?==?(const string_res &s, const char* other) {
392	string_res sother = other;
393	return s == sother;
394	}
395	bool ?!=?(const string_res &s, const char* other) {
396	return !(s == other);
397	}
398
399
400	//////////////////////////////////////////////////////////
401	// Search
402
403	bool contains(const string_res &s, char ch) {
404	for (i; size(s)) {
405	if (s[i] == ch) return true;
406	}
407	return false;
408	}
409
410	int find(const string_res &s, char search) {
411	for (i; size(s)) {
412	if (s[i] == search) return i;
413	}
414	return size(s);
415	}
416
417	/* Remaining implementations essentially ported from Sunjay's work */
418
419	int find(const string_res &s, const string_res &search) {
420	return find(s, search.Handle.s, search.Handle.lnth);
421	}
422
423	int find(const string_res &s, const char* search) {
424	return find(s, search, strlen(search));
425	}
426
427	int find(const string_res &s, const char* search, size_t searchsize) {
428	// FIXME: This is a naive algorithm. We probably want to switch to someting
429	// like Boyer-Moore in the future.
430	// https://en.wikipedia.org/wiki/String_searching_algorithm
431
432	// Always find the empty string
433	if (searchsize == 0) {
434	return 0;
435	}
436
437	for (size_t i = 0; i < s.Handle.lnth; i++) {
438	size_t remaining = s.Handle.lnth - i;
439	// Never going to find the search string if the remaining string is
440	// smaller than search
441	if (remaining < searchsize) {
442	break;
443	}
444
445	bool matched = true;
446	for (size_t j = 0; j < searchsize; j++) {
447	if (search[j] != s.Handle.s[i + j]) {
448	matched = false;
449	break;
450	}
451	}
452	if (matched) {
453	return i;
454	}
455	}
456
457	return s.Handle.lnth;
458	}
459
460	bool includes(const string_res &s, const string_res &search) {
461	return includes(s, search.Handle.s, search.Handle.lnth);
462	}
463
464	bool includes(const string_res &s, const char* search) {
465	return includes(s, search, strlen(search));
466	}
467
468	bool includes(const string_res &s, const char* search, size_t searchsize) {
469	return find(s, search, searchsize) < s.Handle.lnth;
470	}
471
472	bool startsWith(const string_res &s, const string_res &prefix) {
473	return startsWith(s, prefix.Handle.s, prefix.Handle.lnth);
474	}
475
476	bool startsWith(const string_res &s, const char* prefix) {
477	return startsWith(s, prefix, strlen(prefix));
478	}
479
480	bool startsWith(const string_res &s, const char* prefix, size_t prefixsize) {
481	if (s.Handle.lnth < prefixsize) {
482	return false;
483	}
484	return memcmp(s.Handle.s, prefix, prefixsize) == 0;
485	}
486
487	bool endsWith(const string_res &s, const string_res &suffix) {
488	return endsWith(s, suffix.Handle.s, suffix.Handle.lnth);
489	}
490
491	bool endsWith(const string_res &s, const char* suffix) {
492	return endsWith(s, suffix, strlen(suffix));
493	}
494
495	bool endsWith(const string_res &s, const char* suffix, size_t suffixsize) {
496	if (s.Handle.lnth < suffixsize) {
497	return false;
498	}
499	// Amount to offset the bytes pointer so that we are comparing the end of s
500	// to suffix. s.bytes + offset should be the first byte to compare against suffix
501	size_t offset = s.Handle.lnth - suffixsize;
502	return memcmp(s.Handle.s + offset, suffix, suffixsize) == 0;
503	}
504
505	/* Back to Mike's work */
506
507
508	///////////////////////////////////////////////////////////////////////////
509	// charclass, include, exclude
510
511	void ?{}( charclass_res & this, const string_res & chars) {
512	(this){ chars.Handle.s, chars.Handle.lnth };
513	}
514
515	void ?{}( charclass_res & this, const char * chars ) {
516	(this){ chars, strlen(chars) };
517	}
518
519	void ?{}( charclass_res & this, const char * chars, size_t charssize ) {
520	(this.chars){ chars, charssize };
521	// now sort it ?
522	}
523
524	void ^?{}( charclass_res & this ) {
525	^(this.chars){};
526	}
527
528	static bool test( const charclass_res & mask, char c ) {
529	// instead, use sorted char list?
530	return contains( mask.chars, c );
531	}
532
533	int exclude(const string_res &s, const charclass_res &mask) {
534	for (int i = 0; i < size(s); i++) {
535	if ( test(mask, s[i]) ) return i;
536	}
537	return size(s);
538	}
539
540	int include(const string_res &s, const charclass_res &mask) {
541	for (int i = 0; i < size(s); i++) {
542	if ( ! test(mask, s[i]) ) return i;
543	}
544	return size(s);
545	}
546
547	//######################### VbyteHeap "implementation" #########################
548
549
550	// Add a new HandleNode node n after the current HandleNode node.
551
552	static inline void AddThisAfter( HandleNode & this, HandleNode & n ) with(this) {
553	#ifdef VbyteDebug
554	serr \| "enter:AddThisAfter, this:" \| &this \| " n:" \| &n;
555	#endif // VbyteDebug
556	flink = n.flink;
557	blink = &n;
558	n.flink->blink = &this;
559	n.flink = &this;
560	#ifdef VbyteDebug
561	{
562	serr \| "HandleList:";
563	serr \| nlOff;
564	for ( HandleNode *ni = HeaderPtr->flink; ni != HeaderPtr; ni = ni->flink ) {
565	serr \| "\tnode:" \| ni \| " lnth:" \| ni->lnth \| " s:" \| (void *)ni->s \| ",\"";
566	for ( int i = 0; i < ni->lnth; i += 1 ) {
567	serr \| ni->s[i];
568	} // for
569	serr \| "\" flink:" \| ni->flink \| " blink:" \| ni->blink \| nl;
570	} // for
571	serr \| nlOn;
572	}
573	serr \| "exit:AddThisAfter";
574	#endif // VbyteDebug
575	} // AddThisAfter
576
577
578	// Delete the current HandleNode node.
579
580	static inline void DeleteNode( HandleNode & this ) with(this) {
581	#ifdef VbyteDebug
582	serr \| "enter:DeleteNode, this:" \| &this;
583	#endif // VbyteDebug
584	flink->blink = blink;
585	blink->flink = flink;
586	#ifdef VbyteDebug
587	serr \| "exit:DeleteNode";
588	#endif // VbyteDebug
589	} // DeleteNode
590
591
592
593	// Allocates specified storage for a string from byte-string area. If not enough space remains to perform the
594	// allocation, the garbage collection routine is called and a second attempt is made to allocate the space. If the
595	// second attempt fails, a further attempt is made to create a new, larger byte-string area.
596
597	static inline char * VbyteAlloc( VbyteHeap & this, int size ) with(this) {
598	#ifdef VbyteDebug
599	serr \| "enter:VbyteAlloc, size:" \| size;
600	#endif // VbyteDebug
601	uintptr_t NoBytes;
602	char *r;
603
604	NoBytes = ( uintptr_t )EndVbyte + size;
605	if ( NoBytes > ( uintptr_t )ExtVbyte ) { // enough room for new byte-string ?
606	garbage( this ); // firer up the garbage collector
607	NoBytes = ( uintptr_t )EndVbyte + size; // try again
608	if ( NoBytes > ( uintptr_t )ExtVbyte ) { // enough room for new byte-string ?
609	assert( 0 && "need to implement actual growth" );
610	// extend( size ); // extend the byte-string area
611	} // if
612	} // if
613	r = EndVbyte;
614	EndVbyte += size;
615	#ifdef VbyteDebug
616	serr \| "exit:VbyteAlloc, r:" \| (void )r \| " EndVbyte:" \| (void )EndVbyte \| " ExtVbyte:" \| ExtVbyte;
617	#endif // VbyteDebug
618	return r;
619	} // VbyteAlloc
620
621
622	// Move an existing HandleNode node h somewhere after the current HandleNode node so that it is in ascending order by
623	// the address in the byte string area.
624
625	static inline void MoveThisAfter( HandleNode & this, const HandleNode & h ) with(this) {
626	#ifdef VbyteDebug
627	serr \| "enter:MoveThisAfter, this:" \| & this \| " h:" \| & h;
628	#endif // VbyteDebug
629	if ( s < h.s ) { // check argument values
630	// serr \| "VbyteSM: Error - Cannot move byte string starting at:" \| s \| " after byte string starting at:"
631	// \| ( h->s ) \| " and keep handles in ascending order";
632	// exit(-1 );
633	assert( 0 && "VbyteSM: Error - Cannot move byte strings as requested and keep handles in ascending order");
634	} // if
635
636	HandleNode *i;
637	for ( i = h.flink; i->s != 0 && s > ( i->s ); i = i->flink ); // find the position for this node after h
638	if ( & this != i->blink ) {
639	DeleteNode( this );
640	AddThisAfter( this, *i->blink );
641	} // if
642	#ifdef VbyteDebug
643	serr \| "exit:MoveThisAfter";
644	{
645	serr \| "HandleList:";
646	serr \| nlOff;
647	for ( HandleNode *n = HeaderPtr->flink; n != HeaderPtr; n = n->flink ) {
648	serr \| "\tnode:" \| n \| " lnth:" \| n->lnth \| " s:" \| (void *)n->s \| ",\"";
649	for ( int i = 0; i < n->lnth; i += 1 ) {
650	serr \| n->s[i];
651	} // for
652	serr \| "\" flink:" \| n->flink \| " blink:" \| n->blink;
653	} // for
654	serr \| nlOn;
655	}
656	#endif // VbyteDebug
657	} // MoveThisAfter
658
659
660
661
662
663	//######################### VbyteHeap #########################
664
665	#ifdef VbyteDebug
666	HandleNode *HeaderPtr = 0p;
667	#endif // VbyteDebug
668
669	// Move characters from one location in the byte-string area to another. The routine handles the following situations:
670	//
671	// if the \|Src\| > \|Dst\| => truncate
672	// if the \|Dst\| > \|Src\| => pad Dst with blanks
673
674	void ByteCopy( VbyteHeap & this, char Dst, int DstStart, int DstLnth, char Src, int SrcStart, int SrcLnth ) {
675	for ( int i = 0; i < DstLnth; i += 1 ) {
676	if ( i == SrcLnth ) { // \|Dst\| > \|Src\|
677	for ( ; i < DstLnth; i += 1 ) { // pad Dst with blanks
678	Dst[DstStart + i] = ' ';
679	} // for
680	break;
681	} // exit
682	Dst[DstStart + i] = Src[SrcStart + i];
683	} // for
684	} // ByteCopy
685
686	// Compare two byte strings in the byte-string area. The routine returns the following values:
687	//
688	// 1 => Src1-byte-string > Src2-byte-string
689	// 0 => Src1-byte-string = Src2-byte-string
690	// -1 => Src1-byte-string < Src2-byte-string
691
692	int ByteCmp( VbyteHeap & this, char Src1, int Src1Start, int Src1Lnth, char Src2, int Src2Start, int Src2Lnth ) with(this) {
693	#ifdef VbyteDebug
694	serr \| "enter:ByteCmp, Src1Start:" \| Src1Start \| " Src1Lnth:" \| Src1Lnth \| " Src2Start:" \| Src2Start \| " Src2Lnth:" \| Src2Lnth;
695	#endif // VbyteDebug
696	int cmp;
697
698	CharZip: for ( int i = 0; ; i += 1 ) {
699	if ( i == Src2Lnth - 1 ) {
700	for ( ; ; i += 1 ) {
701	if ( i == Src1Lnth - 1 ) {
702	cmp = 0;
703	break CharZip;
704	} // exit
705	if ( Src1[Src1Start + i] != ' ') {
706	// SUSPECTED BUG: this could be be why Peter got the bug report about == " " (why is this case here at all?)
707	cmp = 1;
708	break CharZip;
709	} // exit
710	} // for
711	} // exit
712	if ( i == Src1Lnth - 1 ) {
713	for ( ; ; i += 1 ) {
714	if ( i == Src2Lnth - 1 ) {
715	cmp = 0;
716	break CharZip;
717	} // exit
718	if ( Src2[Src2Start + i] != ' ') {
719	cmp = -1;
720	break CharZip;
721	} // exit
722	} // for
723	} // exit
724	if ( Src2[Src2Start + i] != Src1[Src1Start+ i]) {
725	cmp = Src1[Src1Start + i] > Src2[Src2Start + i] ? 1 : -1;
726	break CharZip;
727	} // exit
728	} // for
729	#ifdef VbyteDebug
730	serr \| "exit:ByteCmp, cmp:" \| cmp;
731	#endif // VbyteDebug
732	return cmp;
733	} // ByteCmp
734
735
736	// The compaction moves all of the byte strings currently in use to the beginning of the byte-string area and modifies
737	// the handles to reflect the new positions of the byte strings. Compaction assumes that the handle list is in ascending
738	// order by pointers into the byte-string area. The strings associated with substrings do not have to be moved because
739	// the containing string has been moved. Hence, they only require that their string pointers be adjusted.
740
741	void compaction(VbyteHeap & this) with(this) {
742	HandleNode *h;
743	char obase, nbase, *limit;
744
745	NoOfCompactions += 1;
746	EndVbyte = StartVbyte;
747	h = Header.flink; // ignore header node
748	for (;;) {
749	ByteCopy( this, EndVbyte, 0, h->lnth, h->s, 0, h->lnth );
750	obase = h->s;
751	h->s = EndVbyte;
752	nbase = h->s;
753	EndVbyte += h->lnth;
754	limit = obase + h->lnth;
755	h = h->flink;
756
757	// check if any substrings are allocated within a string
758
759	for (;;) {
760	if ( h == &Header ) break; // end of header list ?
761	if ( h->s >= limit ) break; // outside of current string ?
762	h->s = nbase + (( uintptr_t )h->s - ( uintptr_t )obase );
763	h = h->flink;
764	} // for
765	if ( h == &Header ) break; // end of header list ?
766	} // for
767	} // compaction
768
769
770	// Garbage determines the amount of free space left in the heap and then reduces, leave the same, or extends the size of
771	// the heap. The heap is then compacted in the existing heap or into the newly allocated heap.
772
773	void garbage(VbyteHeap & this ) with(this) {
774	#ifdef VbyteDebug
775	serr \| "enter:garbage";
776	{
777	serr \| "HandleList:";
778	for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) {
779	serr \| nlOff;
780	serr \| "\tnode:" \| n \| " lnth:" \| n->lnth \| " s:" \| (void *)n->s \| ",\"";
781	for ( int i = 0; i < n->lnth; i += 1 ) {
782	serr \| n->s[i];
783	} // for
784	serr \| nlOn;
785	serr \| "\" flink:" \| n->flink \| " blink:" \| n->blink;
786	} // for
787	}
788	#endif // VbyteDebug
789	int AmountUsed, AmountFree;
790
791	AmountUsed = 0;
792	for ( HandleNode *i = Header.flink; i != &Header; i = i->flink ) { // calculate amount of byte area used
793	AmountUsed += i->lnth;
794	} // for
795	AmountFree = ( uintptr_t )ExtVbyte - ( uintptr_t )StartVbyte - AmountUsed;
796
797	if ( AmountFree < ( int )( CurrSize * 0.1 )) { // free space less than 10% ?
798
799	assert( 0 && "need to implement actual growth" );
800	// extend( CurrSize ); // extend the heap
801
802	// Peter says, "This needs work before it should be used."
803	// } else if ( AmountFree > CurrSize / 2 ) { // free space greater than 3 times the initial allocation ?
804	// reduce(( AmountFree / CurrSize - 3 ) * CurrSize ); // reduce the memory
805
806	} // if
807	compaction(this); // compact the byte area, in the same or new heap area
808	#ifdef VbyteDebug
809	{
810	serr \| "HandleList:";
811	for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) {
812	serr \| nlOff;
813	serr \| "\tnode:" \| n \| " lnth:" \| n->lnth \| " s:" \| (void *)n->s \| ",\"";
814	for ( int i = 0; i < n->lnth; i += 1 ) {
815	serr \| n->s[i];
816	} // for
817	serr \| nlOn;
818	serr \| "\" flink:" \| n->flink \| " blink:" \| n->blink;
819	} // for
820	}
821	serr \| "exit:garbage";
822	#endif // VbyteDebug
823	} // garbage
824
825	#undef VbyteDebug
826
827	//WIP
828	#if 0
829
830
831	// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string
832	// area is deleted.
833
834	void VbyteHeap::extend( int size ) {
835	#ifdef VbyteDebug
836	serr \| "enter:extend, size:" \| size;
837	#endif // VbyteDebug
838	char *OldStartVbyte;
839
840	NoOfExtensions += 1;
841	OldStartVbyte = StartVbyte; // save previous byte area
842
843	CurrSize += size > InitSize ? size : InitSize; // minimum extension, initial size
844	StartVbyte = EndVbyte = new char[CurrSize];
845	ExtVbyte = (void *)( StartVbyte + CurrSize );
846	compaction(); // copy from old heap to new & adjust pointers to new heap
847	delete OldStartVbyte; // release old heap
848	#ifdef VbyteDebug
849	serr \| "exit:extend, CurrSize:" \| CurrSize;
850	#endif // VbyteDebug
851	} // extend
852
853
854	// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string
855	// area is deleted.
856
857	void VbyteHeap::reduce( int size ) {
858	#ifdef VbyteDebug
859	serr \| "enter:reduce, size:" \| size;
860	#endif // VbyteDebug
861	char *OldStartVbyte;
862
863	NoOfReductions += 1;
864	OldStartVbyte = StartVbyte; // save previous byte area
865
866	CurrSize -= size;
867	StartVbyte = EndVbyte = new char[CurrSize];
868	ExtVbyte = (void *)( StartVbyte + CurrSize );
869	compaction(); // copy from old heap to new & adjust pointers to new heap
870	delete OldStartVbyte; // release old heap
871	#ifdef VbyteDebug
872	serr \| "exit:reduce, CurrSize:" \| CurrSize;
873	#endif // VbyteDebug
874	} // reduce
875
876
877	#endif

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

Download in other formats:

Original Format