Context Navigation

string_res.cfa@ 218096f

Visit:

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

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

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

Download in other formats:

Original Format