Context Navigation

string_res.cfa@ 49b3389

Visit:

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

Last change on this file since 49b3389 was f450f2f, checked in by Michael Brooks <mlbrooks@…>, 4 years ago
Baseline of the string implementation.
Property mode set to `100644`
File size: 28.4 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 ?=?(string_res &s, const char* other) {
226	string_res sother = other;
227	const string_res & sother_ref = sother;
228	s = sother_ref; // `s = sother` calls autogen ?=?
229	}
230
231	void ?=?(string_res &s, char other) {
232	char otherCstr[2] = {other, 0};
233	s = otherCstr;
234	}
235
236	// Copy assignment operator
237	void ?=?(string_res & this, const string_res & rhs) with( this ) {
238
239	char * afterBegin = this.Handle.s + this.Handle.lnth;
240
241	char * shareEditSetStart = this.Handle.s;
242	char * shareEditSetEnd = afterBegin;
243	for (string_res * editPeer = this.shareEditSet_next; editPeer != &this; editPeer = editPeer->shareEditSet_next) {
244	shareEditSetStart = min( shareEditSetStart, editPeer->Handle.s );
245	shareEditSetEnd = max( shareEditSetStart, editPeer->Handle.s + editPeer->Handle.lnth);
246	}
247
248	char * beforeBegin = shareEditSetStart;
249	size_t beforeLen = this.Handle.s - shareEditSetStart;
250	size_t afterLen = shareEditSetEnd - afterBegin;
251
252	string_res pasting = { beforeBegin, beforeLen };
253	pasting += rhs;
254	string_res after = { afterBegin, afterLen }; // juxtaposed with in-progress pasting
255	pasting += after; // optimized case
256
257	size_t oldLnth = this.Handle.lnth;
258
259	this.Handle.s = pasting.Handle.s + beforeLen;
260	this.Handle.lnth = rhs.Handle.lnth;
261	MoveThisAfter( this.Handle, pasting.Handle );
262
263	// adjust all substring string and handle locations, and check if any substring strings are outside the new base string
264	char *limit = pasting.Handle.s + pasting.Handle.lnth;
265	for (string_res * p = this.shareEditSet_next; p != &this; p = p->shareEditSet_next) {
266	assert (p->Handle.s >= beforeBegin);
267	if ( p->Handle.s < beforeBegin + beforeLen ) {
268	// p starts before the edit
269	if ( p->Handle.s + p->Handle.lnth < beforeBegin + beforeLen ) {
270	// p ends before the edit
271	// take end as start-anchored too
272	// p->Handle.lnth unaffected
273	} else if ( p->Handle.s + p->Handle.lnth < afterBegin ) {
274	// p ends during the edit
275	// clip end of p to end at start of edit
276	p->Handle.lnth = beforeLen - ( p->Handle.s - beforeBegin );
277	} else {
278	// p ends after the edit
279	assert ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen );
280	// take end as end-anchored
281	// stretch-shrink p according to the edit
282	p->Handle.lnth += this.Handle.lnth;
283	p->Handle.lnth -= oldLnth;
284	}
285	// take start as start-anchored
286	size_t startOffsetFromStart = p->Handle.s - beforeBegin;
287	p->Handle.s = pasting.Handle.s + startOffsetFromStart;
288	} else if ( p->Handle.s < afterBegin ) {
289	// p starts during the edit
290	assert( p->Handle.s + p->Handle.lnth >= beforeBegin + beforeLen );
291	if ( p->Handle.s + p->Handle.lnth < afterBegin ) {
292	// p ends during the edit
293	// set p to empty string at start of edit
294	p->Handle.s = this.Handle.s;
295	p->Handle.lnth = 0;
296	} else {
297	// p ends after the edit
298	// clip start of p to start at end of edit
299	p->Handle.s = this.Handle.s + this.Handle.lnth;
300	p->Handle.lnth += this.Handle.lnth;
301	p->Handle.lnth -= oldLnth;
302	}
303	} else {
304	assert ( p->Handle.s <= afterBegin + afterLen );
305	assert ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen );
306	// p starts after the edit
307	// take start and end as end-anchored
308	size_t startOffsetFromEnd = afterBegin + afterLen - p->Handle.s;
309	p->Handle.s = limit - startOffsetFromEnd;
310	// p->Handle.lnth unaffected
311	}
312	MoveThisAfter( p->Handle, pasting.Handle ); // move substring handle to maintain sorted order by string position
313	}
314	}
315
316	void ?=?(string_res & this, string_res & rhs) with( this ) {
317	const string_res & rhs2 = rhs;
318	this = rhs2;
319	}
320
321
322	// Destructor
323	void ^?{}(string_res &s) with(s) {
324	// much delegated to implied ^VbyteSM
325
326	// sever s from its share-edit peers, if any (four no-ops when already solo)
327	s.shareEditSet_prev->shareEditSet_next = s.shareEditSet_next;
328	s.shareEditSet_next->shareEditSet_prev = s.shareEditSet_prev;
329	s.shareEditSet_next = &s;
330	s.shareEditSet_prev = &s;
331	}
332
333
334	// Returns the character at the given index
335	// With unicode support, this may be different from just the byte at the given
336	// offset from the start of the string.
337	char ?[?](const string_res &s, size_t index) with(s) {
338	//TODO: Check if index is valid (no exceptions yet)
339	return Handle.s[index];
340	}
341
342	///////////////////////////////////////////////////////////////////
343	// Slice-Concatenate helper
344
345	void append(string_res &str1, const string_res & str_src, size_t start, size_t end) {
346	size_t clnth = size(str1) + end - start;
347	if ( str1.Handle.s + size(str1) == str_src.Handle.s && start == 0) { // already juxtapose ?
348	} else { // must copy some text
349	if ( str1.Handle.s + size(str1) == VbyteAlloc(HeapArea, 0) ) { // str1 at end of string area ?
350	VbyteAlloc(HeapArea, end - start); // create room for 2nd part at the end of string area
351	} else { // copy the two parts
352	char * str1oldBuf = str1.Handle.s;
353	str1.Handle.s = VbyteAlloc( HeapArea, clnth );
354	ByteCopy( HeapArea, str1.Handle.s, 0, str1.Handle.lnth, str1oldBuf, 0, str1.Handle.lnth);
355	} // if
356	ByteCopy( HeapArea, str1.Handle.s, str1.Handle.lnth, str_src.Handle.lnth, str_src.Handle.s, start, end);
357	// VbyteHeap & this, char Dst, int DstStart, int DstLnth, char Src, int SrcStart, int SrcLnth
358	} // if
359	str1.Handle.lnth = clnth;
360	}
361
362
363
364	///////////////////////////////////////////////////////////////////
365	// Concatenation
366
367	void ?+=?(string_res &str1, const string_res &str2) {
368	append( str1, str2, 0, size(str2) );
369	}
370
371	void ?+=?(string_res &s, char other) {
372	string_res other_s = { &other, 1 };
373	s += other_s;
374	}
375
376	void ?+=?(string_res &s, const char* other) {
377	string_res other_s = other;
378	s += other_s;
379	}
380
381
382
383
384	//////////////////////////////////////////////////////////
385	// Comparisons
386
387
388	bool ?==?(const string_res &s1, const string_res &s2) {
389	return ByteCmp( HeapArea, s1.Handle.s, 0, s1.Handle.lnth, s2.Handle.s, 0, s2.Handle.lnth) == 0;
390	}
391
392	bool ?!=?(const string_res &s1, const string_res &s2) {
393	return !(s1 == s2);
394	}
395	bool ?==?(const string_res &s, const char* other) {
396	string_res sother = other;
397	return s == sother;
398	}
399	bool ?!=?(const string_res &s, const char* other) {
400	return !(s == other);
401	}
402
403
404	//////////////////////////////////////////////////////////
405	// Search
406
407	bool contains(const string_res &s, char ch) {
408	for (i; size(s)) {
409	if (s[i] == ch) return true;
410	}
411	return false;
412	}
413
414	int find(const string_res &s, char search) {
415	for (i; size(s)) {
416	if (s[i] == search) return i;
417	}
418	return size(s);
419	}
420
421	/* Remaining implementations essentially ported from Sunjay's work */
422
423	int find(const string_res &s, const string_res &search) {
424	return find(s, search.Handle.s, search.Handle.lnth);
425	}
426
427	int find(const string_res &s, const char* search) {
428	return find(s, search, strlen(search));
429	}
430
431	int find(const string_res &s, const char* search, size_t searchsize) {
432	// FIXME: This is a naive algorithm. We probably want to switch to someting
433	// like Boyer-Moore in the future.
434	// https://en.wikipedia.org/wiki/String_searching_algorithm
435
436	// Always find the empty string
437	if (searchsize == 0) {
438	return 0;
439	}
440
441	for (size_t i = 0; i < s.Handle.lnth; i++) {
442	size_t remaining = s.Handle.lnth - i;
443	// Never going to find the search string if the remaining string is
444	// smaller than search
445	if (remaining < searchsize) {
446	break;
447	}
448
449	bool matched = true;
450	for (size_t j = 0; j < searchsize; j++) {
451	if (search[j] != s.Handle.s[i + j]) {
452	matched = false;
453	break;
454	}
455	}
456	if (matched) {
457	return i;
458	}
459	}
460
461	return s.Handle.lnth;
462	}
463
464	bool includes(const string_res &s, const string_res &search) {
465	return includes(s, search.Handle.s, search.Handle.lnth);
466	}
467
468	bool includes(const string_res &s, const char* search) {
469	return includes(s, search, strlen(search));
470	}
471
472	bool includes(const string_res &s, const char* search, size_t searchsize) {
473	return find(s, search, searchsize) < s.Handle.lnth;
474	}
475
476	bool startsWith(const string_res &s, const string_res &prefix) {
477	return startsWith(s, prefix.Handle.s, prefix.Handle.lnth);
478	}
479
480	bool startsWith(const string_res &s, const char* prefix) {
481	return startsWith(s, prefix, strlen(prefix));
482	}
483
484	bool startsWith(const string_res &s, const char* prefix, size_t prefixsize) {
485	if (s.Handle.lnth < prefixsize) {
486	return false;
487	}
488	return memcmp(s.Handle.s, prefix, prefixsize) == 0;
489	}
490
491	bool endsWith(const string_res &s, const string_res &suffix) {
492	return endsWith(s, suffix.Handle.s, suffix.Handle.lnth);
493	}
494
495	bool endsWith(const string_res &s, const char* suffix) {
496	return endsWith(s, suffix, strlen(suffix));
497	}
498
499	bool endsWith(const string_res &s, const char* suffix, size_t suffixsize) {
500	if (s.Handle.lnth < suffixsize) {
501	return false;
502	}
503	// Amount to offset the bytes pointer so that we are comparing the end of s
504	// to suffix. s.bytes + offset should be the first byte to compare against suffix
505	size_t offset = s.Handle.lnth - suffixsize;
506	return memcmp(s.Handle.s + offset, suffix, suffixsize) == 0;
507	}
508
509	/* Back to Mike's work */
510
511
512	///////////////////////////////////////////////////////////////////////////
513	// charclass, include, exclude
514
515	void ?{}( charclass_res & this, const string_res & chars) {
516	(this){ chars.Handle.s, chars.Handle.lnth };
517	}
518
519	void ?{}( charclass_res & this, const char * chars ) {
520	(this){ chars, strlen(chars) };
521	}
522
523	void ?{}( charclass_res & this, const char * chars, size_t charssize ) {
524	(this.chars){ chars, charssize };
525	// now sort it ?
526	}
527
528	void ^?{}( charclass_res & this ) {
529	^(this.chars){};
530	}
531
532	static bool test( const charclass_res & mask, char c ) {
533	// instead, use sorted char list?
534	return contains( mask.chars, c );
535	}
536
537	int exclude(const string_res &s, const charclass_res &mask) {
538	for (int i = 0; i < size(s); i++) {
539	if ( test(mask, s[i]) ) return i;
540	}
541	return size(s);
542	}
543
544	int include(const string_res &s, const charclass_res &mask) {
545	for (int i = 0; i < size(s); i++) {
546	if ( ! test(mask, s[i]) ) return i;
547	}
548	return size(s);
549	}
550
551	//######################### VbyteHeap "implementation" #########################
552
553
554	// Add a new HandleNode node n after the current HandleNode node.
555
556	static inline void AddThisAfter( HandleNode & this, HandleNode & n ) with(this) {
557	#ifdef VbyteDebug
558	serr \| "enter:AddThisAfter, this:" \| &this \| " n:" \| &n;
559	#endif // VbyteDebug
560	flink = n.flink;
561	blink = &n;
562	n.flink->blink = &this;
563	n.flink = &this;
564	#ifdef VbyteDebug
565	{
566	serr \| "HandleList:";
567	serr \| nlOff;
568	for ( HandleNode *ni = HeaderPtr->flink; ni != HeaderPtr; ni = ni->flink ) {
569	serr \| "\tnode:" \| ni \| " lnth:" \| ni->lnth \| " s:" \| (void *)ni->s \| ",\"";
570	for ( int i = 0; i < ni->lnth; i += 1 ) {
571	serr \| ni->s[i];
572	} // for
573	serr \| "\" flink:" \| ni->flink \| " blink:" \| ni->blink \| nl;
574	} // for
575	serr \| nlOn;
576	}
577	serr \| "exit:AddThisAfter";
578	#endif // VbyteDebug
579	} // AddThisAfter
580
581
582	// Delete the current HandleNode node.
583
584	static inline void DeleteNode( HandleNode & this ) with(this) {
585	#ifdef VbyteDebug
586	serr \| "enter:DeleteNode, this:" \| &this;
587	#endif // VbyteDebug
588	flink->blink = blink;
589	blink->flink = flink;
590	#ifdef VbyteDebug
591	serr \| "exit:DeleteNode";
592	#endif // VbyteDebug
593	} // DeleteNode
594
595
596
597	// Allocates specified storage for a string from byte-string area. If not enough space remains to perform the
598	// allocation, the garbage collection routine is called and a second attempt is made to allocate the space. If the
599	// second attempt fails, a further attempt is made to create a new, larger byte-string area.
600
601	static inline char * VbyteAlloc( VbyteHeap & this, int size ) with(this) {
602	#ifdef VbyteDebug
603	serr \| "enter:VbyteAlloc, size:" \| size;
604	#endif // VbyteDebug
605	uintptr_t NoBytes;
606	char *r;
607
608	NoBytes = ( uintptr_t )EndVbyte + size;
609	if ( NoBytes > ( uintptr_t )ExtVbyte ) { // enough room for new byte-string ?
610	garbage( this ); // firer up the garbage collector
611	NoBytes = ( uintptr_t )EndVbyte + size; // try again
612	if ( NoBytes > ( uintptr_t )ExtVbyte ) { // enough room for new byte-string ?
613	assert( 0 && "need to implement actual growth" );
614	// extend( size ); // extend the byte-string area
615	} // if
616	} // if
617	r = EndVbyte;
618	EndVbyte += size;
619	#ifdef VbyteDebug
620	serr \| "exit:VbyteAlloc, r:" \| (void )r \| " EndVbyte:" \| (void )EndVbyte \| " ExtVbyte:" \| ExtVbyte;
621	#endif // VbyteDebug
622	return r;
623	} // VbyteAlloc
624
625
626	// Move an existing HandleNode node h somewhere after the current HandleNode node so that it is in ascending order by
627	// the address in the byte string area.
628
629	static inline void MoveThisAfter( HandleNode & this, const HandleNode & h ) with(this) {
630	#ifdef VbyteDebug
631	serr \| "enter:MoveThisAfter, this:" \| & this \| " h:" \| & h;
632	#endif // VbyteDebug
633	if ( s < h.s ) { // check argument values
634	// serr \| "VbyteSM: Error - Cannot move byte string starting at:" \| s \| " after byte string starting at:"
635	// \| ( h->s ) \| " and keep handles in ascending order";
636	// exit(-1 );
637	assert( 0 && "VbyteSM: Error - Cannot move byte strings as requested and keep handles in ascending order");
638	} // if
639
640	HandleNode *i;
641	for ( i = h.flink; i->s != 0 && s > ( i->s ); i = i->flink ); // find the position for this node after h
642	if ( & this != i->blink ) {
643	DeleteNode( this );
644	AddThisAfter( this, *i->blink );
645	} // if
646	#ifdef VbyteDebug
647	serr \| "exit:MoveThisAfter";
648	{
649	serr \| "HandleList:";
650	serr \| nlOff;
651	for ( HandleNode *n = HeaderPtr->flink; n != HeaderPtr; n = n->flink ) {
652	serr \| "\tnode:" \| n \| " lnth:" \| n->lnth \| " s:" \| (void *)n->s \| ",\"";
653	for ( int i = 0; i < n->lnth; i += 1 ) {
654	serr \| n->s[i];
655	} // for
656	serr \| "\" flink:" \| n->flink \| " blink:" \| n->blink;
657	} // for
658	serr \| nlOn;
659	}
660	#endif // VbyteDebug
661	} // MoveThisAfter
662
663
664
665
666
667	//######################### VbyteHeap #########################
668
669	#ifdef VbyteDebug
670	HandleNode *HeaderPtr = 0p;
671	#endif // VbyteDebug
672
673	// Move characters from one location in the byte-string area to another. The routine handles the following situations:
674	//
675	// if the \|Src\| > \|Dst\| => truncate
676	// if the \|Dst\| > \|Src\| => pad Dst with blanks
677
678	void ByteCopy( VbyteHeap & this, char Dst, int DstStart, int DstLnth, char Src, int SrcStart, int SrcLnth ) {
679	for ( int i = 0; i < DstLnth; i += 1 ) {
680	if ( i == SrcLnth ) { // \|Dst\| > \|Src\|
681	for ( ; i < DstLnth; i += 1 ) { // pad Dst with blanks
682	Dst[DstStart + i] = ' ';
683	} // for
684	break;
685	} // exit
686	Dst[DstStart + i] = Src[SrcStart + i];
687	} // for
688	} // ByteCopy
689
690	// Compare two byte strings in the byte-string area. The routine returns the following values:
691	//
692	// 1 => Src1-byte-string > Src2-byte-string
693	// 0 => Src1-byte-string = Src2-byte-string
694	// -1 => Src1-byte-string < Src2-byte-string
695
696	int ByteCmp( VbyteHeap & this, char Src1, int Src1Start, int Src1Lnth, char Src2, int Src2Start, int Src2Lnth ) with(this) {
697	#ifdef VbyteDebug
698	serr \| "enter:ByteCmp, Src1Start:" \| Src1Start \| " Src1Lnth:" \| Src1Lnth \| " Src2Start:" \| Src2Start \| " Src2Lnth:" \| Src2Lnth;
699	#endif // VbyteDebug
700	int cmp;
701
702	CharZip: for ( int i = 0; ; i += 1 ) {
703	if ( i == Src2Lnth - 1 ) {
704	for ( ; ; i += 1 ) {
705	if ( i == Src1Lnth - 1 ) {
706	cmp = 0;
707	break CharZip;
708	} // exit
709	if ( Src1[Src1Start + i] != ' ') {
710	// SUSPECTED BUG: this could be be why Peter got the bug report about == " " (why is this case here at all?)
711	cmp = 1;
712	break CharZip;
713	} // exit
714	} // for
715	} // exit
716	if ( i == Src1Lnth - 1 ) {
717	for ( ; ; i += 1 ) {
718	if ( i == Src2Lnth - 1 ) {
719	cmp = 0;
720	break CharZip;
721	} // exit
722	if ( Src2[Src2Start + i] != ' ') {
723	cmp = -1;
724	break CharZip;
725	} // exit
726	} // for
727	} // exit
728	if ( Src2[Src2Start + i] != Src1[Src1Start+ i]) {
729	cmp = Src1[Src1Start + i] > Src2[Src2Start + i] ? 1 : -1;
730	break CharZip;
731	} // exit
732	} // for
733	#ifdef VbyteDebug
734	serr \| "exit:ByteCmp, cmp:" \| cmp;
735	#endif // VbyteDebug
736	return cmp;
737	} // ByteCmp
738
739
740	// The compaction moves all of the byte strings currently in use to the beginning of the byte-string area and modifies
741	// the handles to reflect the new positions of the byte strings. Compaction assumes that the handle list is in ascending
742	// order by pointers into the byte-string area. The strings associated with substrings do not have to be moved because
743	// the containing string has been moved. Hence, they only require that their string pointers be adjusted.
744
745	void compaction(VbyteHeap & this) with(this) {
746	HandleNode *h;
747	char obase, nbase, *limit;
748
749	NoOfCompactions += 1;
750	EndVbyte = StartVbyte;
751	h = Header.flink; // ignore header node
752	for (;;) {
753	ByteCopy( this, EndVbyte, 0, h->lnth, h->s, 0, h->lnth );
754	obase = h->s;
755	h->s = EndVbyte;
756	nbase = h->s;
757	EndVbyte += h->lnth;
758	limit = obase + h->lnth;
759	h = h->flink;
760
761	// check if any substrings are allocated within a string
762
763	for (;;) {
764	if ( h == &Header ) break; // end of header list ?
765	if ( h->s >= limit ) break; // outside of current string ?
766	h->s = nbase + (( uintptr_t )h->s - ( uintptr_t )obase );
767	h = h->flink;
768	} // for
769	if ( h == &Header ) break; // end of header list ?
770	} // for
771	} // compaction
772
773
774	// Garbage determines the amount of free space left in the heap and then reduces, leave the same, or extends the size of
775	// the heap. The heap is then compacted in the existing heap or into the newly allocated heap.
776
777	void garbage(VbyteHeap & this ) with(this) {
778	#ifdef VbyteDebug
779	serr \| "enter:garbage";
780	{
781	serr \| "HandleList:";
782	for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) {
783	serr \| nlOff;
784	serr \| "\tnode:" \| n \| " lnth:" \| n->lnth \| " s:" \| (void *)n->s \| ",\"";
785	for ( int i = 0; i < n->lnth; i += 1 ) {
786	serr \| n->s[i];
787	} // for
788	serr \| nlOn;
789	serr \| "\" flink:" \| n->flink \| " blink:" \| n->blink;
790	} // for
791	}
792	#endif // VbyteDebug
793	int AmountUsed, AmountFree;
794
795	AmountUsed = 0;
796	for ( HandleNode *i = Header.flink; i != &Header; i = i->flink ) { // calculate amount of byte area used
797	AmountUsed += i->lnth;
798	} // for
799	AmountFree = ( uintptr_t )ExtVbyte - ( uintptr_t )StartVbyte - AmountUsed;
800
801	if ( AmountFree < ( int )( CurrSize * 0.1 )) { // free space less than 10% ?
802
803	assert( 0 && "need to implement actual growth" );
804	// extend( CurrSize ); // extend the heap
805
806	// Peter says, "This needs work before it should be used."
807	// } else if ( AmountFree > CurrSize / 2 ) { // free space greater than 3 times the initial allocation ?
808	// reduce(( AmountFree / CurrSize - 3 ) * CurrSize ); // reduce the memory
809
810	} // if
811	compaction(this); // compact the byte area, in the same or new heap area
812	#ifdef VbyteDebug
813	{
814	serr \| "HandleList:";
815	for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) {
816	serr \| nlOff;
817	serr \| "\tnode:" \| n \| " lnth:" \| n->lnth \| " s:" \| (void *)n->s \| ",\"";
818	for ( int i = 0; i < n->lnth; i += 1 ) {
819	serr \| n->s[i];
820	} // for
821	serr \| nlOn;
822	serr \| "\" flink:" \| n->flink \| " blink:" \| n->blink;
823	} // for
824	}
825	serr \| "exit:garbage";
826	#endif // VbyteDebug
827	} // garbage
828
829	#undef VbyteDebug
830
831	//WIP
832	#if 0
833
834
835	// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string
836	// area is deleted.
837
838	void VbyteHeap::extend( int size ) {
839	#ifdef VbyteDebug
840	serr \| "enter:extend, size:" \| size;
841	#endif // VbyteDebug
842	char *OldStartVbyte;
843
844	NoOfExtensions += 1;
845	OldStartVbyte = StartVbyte; // save previous byte area
846
847	CurrSize += size > InitSize ? size : InitSize; // minimum extension, initial size
848	StartVbyte = EndVbyte = new char[CurrSize];
849	ExtVbyte = (void *)( StartVbyte + CurrSize );
850	compaction(); // copy from old heap to new & adjust pointers to new heap
851	delete OldStartVbyte; // release old heap
852	#ifdef VbyteDebug
853	serr \| "exit:extend, CurrSize:" \| CurrSize;
854	#endif // VbyteDebug
855	} // extend
856
857
858	// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string
859	// area is deleted.
860
861	void VbyteHeap::reduce( int size ) {
862	#ifdef VbyteDebug
863	serr \| "enter:reduce, size:" \| size;
864	#endif // VbyteDebug
865	char *OldStartVbyte;
866
867	NoOfReductions += 1;
868	OldStartVbyte = StartVbyte; // save previous byte area
869
870	CurrSize -= size;
871	StartVbyte = EndVbyte = new char[CurrSize];
872	ExtVbyte = (void *)( StartVbyte + CurrSize );
873	compaction(); // copy from old heap to new & adjust pointers to new heap
874	delete OldStartVbyte; // release old heap
875	#ifdef VbyteDebug
876	serr \| "exit:reduce, CurrSize:" \| CurrSize;
877	#endif // VbyteDebug
878	} // reduce
879
880
881	#endif

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

Download in other formats:

Original Format