Index: libcfa/src/Makefile.am =================================================================== --- libcfa/src/Makefile.am (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ libcfa/src/Makefile.am (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -11,6 +11,6 @@ ## Created On : Sun May 31 08:54:01 2015 ## Last Modified By : Peter A. Buhr -## Last Modified On : Mon Aug 14 17:10:51 2023 -## Update Count : 262 +## Last Modified On : Wed Aug 30 21:22:45 2023 +## Update Count : 263 ############################################################################### @@ -52,5 +52,5 @@ bits/algorithm.hfa \ bits/align.hfa \ - bits/containers.hfa \ + bits/collections.hfa \ bits/debug.hfa \ bits/defs.hfa \ @@ -63,9 +63,9 @@ concurrency/iofwd.hfa \ concurrency/barrier.hfa \ - containers/array.hfa \ - containers/list.hfa \ - containers/lockfree.hfa \ - containers/string_sharectx.hfa \ - containers/vector2.hfa \ + collections/array.hfa \ + collections/list.hfa \ + collections/lockfree.hfa \ + collections/string_sharectx.hfa \ + collections/vector2.hfa \ vec/vec.hfa \ vec/vec2.hfa \ @@ -89,10 +89,10 @@ bits/weakso_locks.hfa \ algorithms/range_iterator.hfa \ - containers/maybe.hfa \ - containers/pair.hfa \ - containers/result.hfa \ - containers/string.hfa \ - containers/string_res.hfa \ - containers/vector.hfa \ + collections/maybe.hfa \ + collections/pair.hfa \ + collections/result.hfa \ + collections/string.hfa \ + collections/string_res.hfa \ + collections/vector.hfa \ device/cpu.hfa Index: libcfa/src/bits/collections.hfa =================================================================== --- libcfa/src/bits/collections.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) +++ libcfa/src/bits/collections.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -0,0 +1,308 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// bits/collections.hfa -- Intrusive generic collections +// +// Author : Thierry Delisle +// Created On : Tue Oct 31 16:38:50 2017 +// Last Modified By : Peter A. Buhr +// Last Modified On : Wed Aug 30 21:26:39 2023 +// Update Count : 30 + +#pragma once + +#include "bits/align.hfa" +#include "bits/defs.hfa" +#include +//----------------------------------------------------------------------------- +// Array +//----------------------------------------------------------------------------- + +#ifdef __cforall + forall(T &) +#else + #define T void +#endif +struct __small_array { + T * data; + __lock_size_t size; +}; +#undef T + +#ifdef __cforall + #define __small_array_t(T) __small_array(T) +#else + #define __small_array_t(T) __small_array +#endif + +#ifdef __cforall + // forall(T | sized(T)) + // static inline void ?{}(__small_array(T) & this) {} + + forall(T & | sized(T)) + static inline T & ?[?]( __small_array(T) & this, __lock_size_t idx ) { + return ((typeof(this.data))this.data)[idx]; + } + + forall(T & | sized(T)) + static inline T & ?[?]( const __small_array(T) & this, __lock_size_t idx ) { + return ((typeof(this.data))this.data)[idx]; + } + + forall(T &) + static inline T * begin( const __small_array(T) & this ) { + return ((typeof(this.data))this.data); + } + + forall(T & | sized(T)) + static inline T * end( const __small_array(T) & this ) { + return ((typeof(this.data))this.data) + this.size; + } +#endif + +//----------------------------------------------------------------------------- +// Node Base +//----------------------------------------------------------------------------- + +#ifdef __cforall + forall( T & ) + trait is_node { + T *& get_next( T & ); + }; +#endif + +//----------------------------------------------------------------------------- +// Stack +//----------------------------------------------------------------------------- +#ifdef __cforall + forall(TYPE &) + #define T TYPE +#else + #define T void +#endif +struct __stack { + T * top; +}; +#undef T + +#ifdef __cforall +#define __stack_t(T) __stack(T) +#else +#define __stack_t(T) struct __stack +#endif + +#ifdef __cforall + forall(T &) + static inline void ?{}( __stack(T) & this ) { + (this.top){ 0p }; + } + + static inline forall( T & | is_node(T) ) { + void push( __stack(T) & this, T * val ) { + verify( !get_next( *val ) ); + get_next( *val ) = this.top; + this.top = val; + } + + T * pop( __stack(T) & this ) { + T * top = this.top; + if( top ) { + this.top = get_next( *top ); + get_next( *top ) = 0p; + } + return top; + } + + int ?!=?( const __stack(T) & this, __attribute__((unused)) zero_t zero ) { + return this.top != 0; + } + } +#endif + +//----------------------------------------------------------------------------- +// Queue +//----------------------------------------------------------------------------- +#ifdef __cforall + forall(TYPE &) + #define T TYPE +#else + #define T void +#endif +struct __queue { + T * head; + T ** tail; +}; +#undef T + +#ifdef __cforall +#define __queue_t(T) __queue(T) +#else +#define __queue_t(T) struct __queue +#endif + +#ifdef __cforall + static inline forall( T & | is_node(T) ) { + void ?{}( __queue(T) & this ) with( this ) { + (this.head){ 1p }; + (this.tail){ &this.head }; + verify(*this.tail == 1p); + } + + void append( __queue(T) & this, T * val ) with(this) { + verify(get_next( *val ) == 0p); + verify(this.tail != 0p); + verify(*this.tail == 1p); + *this.tail = val; + this.tail = &get_next( *val ); + *this.tail = 1p; + } + + T * peek( __queue(T) & this ) { + verify(*this.tail == 1p); + T * frontnode = this.head; + if( frontnode != 1p ) { + verify(*this.tail == 1p); + return frontnode; + } + verify(*this.tail == 1p); + return 0p; + } + + T * pop_head( __queue(T) & this ) { + verify(*this.tail == 1p); + T * _head = this.head; + if( _head != 1p ) { + this.head = get_next( *_head ); + if( get_next( *_head ) == 1p ) { + this.tail = &this.head; + } + get_next( *_head ) = 0p; + verify(*this.tail == 1p); + verify( get_next(*_head) == 0p ); + return _head; + } + verify(*this.tail == 1p); + return 0p; + } + + T * remove( __queue(T) & this, T ** it ) with( this ) { + T * val = *it; + verify( val ); + + (*it) = get_next( *val ); + + if( this.tail == &get_next( *val ) ) { + this.tail = it; + } + + get_next( *val ) = 0p; + + verify( (this.head == 1p) == (&this.head == this.tail) ); + verify( *this.tail == 1p ); + return val; + } + + int ?!=?( const __queue(T) & this, __attribute__((unused)) zero_t zero ) { + return this.head != 1p; + } + } +#endif + + +//----------------------------------------------------------------------------- +// Doubly Linked List +//----------------------------------------------------------------------------- +#ifdef __cforall + forall(TYPE &) + #define T TYPE + #define __getter_t * [T * & next, T * & prev] ( T & ) +#else + typedef void (*__generit_c_getter_t)(); + #define T void + #define __getter_t __generit_c_getter_t +#endif +struct __dllist { + T * head; + __getter_t __get; +}; +#undef T +#undef __getter_t + +#ifdef __cforall +#define __dllist_t(T) __dllist(T) +#else +#define __dllist_t(T) struct __dllist +#endif + +#ifdef __cforall + forall(T & ) + static inline [void] ?{}( __dllist(T) & this, * [T * & next, T * & prev] ( T & ) __get ) { + (this.head){ 0p }; + this.__get = __get; + } + + #define next 0 + #define prev 1 + static inline forall(T &) { + void push_front( __dllist(T) & this, T & node ) with( this ) { + verify(__get); + if ( this.head ) { + __get( node ).next = this.head; + __get( node ).prev = __get( *this.head ).prev; + // inserted node must be consistent before it is seen + // prevent code movement across barrier + asm( "" : : : "memory" ); + __get( *this.head ).prev = &node; + T & _prev = *__get( node ).prev; + __get( _prev ).next = &node; + } else { + __get( node ).next = &node; + __get( node ).prev = &node; + } + + // prevent code movement across barrier + asm( "" : : : "memory" ); + this.head = &node; + } + + void remove( __dllist(T) & this, T & node ) with( this ) { + verify(__get); + if ( &node == this.head ) { + if ( __get( *this.head ).next == this.head ) { + this.head = 0p; + } else { + this.head = __get( *this.head ).next; + } + } + __get( *__get( node ).next ).prev = __get( node ).prev; + __get( *__get( node ).prev ).next = __get( node ).next; + __get( node ).next = 0p; + __get( node ).prev = 0p; + } + + int ?!=?( const __dllist(T) & this, __attribute__((unused)) zero_t zero ) { + return this.head != 0; + } + + void move_to_front( __dllist(T) & src, __dllist(T) & dst, T & node ) { + remove (src, node); + push_front(dst, node); + } + } + #undef next + #undef prev +#endif + +//----------------------------------------------------------------------------- +// Tools +//----------------------------------------------------------------------------- +#ifdef __cforall + +#endif + +// Local Variables: // +// tab-width: 4 // +// End: // Index: libcfa/src/bits/containers.hfa =================================================================== --- libcfa/src/bits/containers.hfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ (revision ) @@ -1,308 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// bits/containers.hfa -- Intrusive generic containers.hfa -// -// Author : Thierry Delisle -// Created On : Tue Oct 31 16:38:50 2017 -// Last Modified By : Peter A. Buhr -// Last Modified On : Thu Feb 2 11:33:08 2023 -// Update Count : 29 - -#pragma once - -#include "bits/align.hfa" -#include "bits/defs.hfa" -#include -//----------------------------------------------------------------------------- -// Array -//----------------------------------------------------------------------------- - -#ifdef __cforall - forall(T &) -#else - #define T void -#endif -struct __small_array { - T * data; - __lock_size_t size; -}; -#undef T - -#ifdef __cforall - #define __small_array_t(T) __small_array(T) -#else - #define __small_array_t(T) __small_array -#endif - -#ifdef __cforall - // forall(T | sized(T)) - // static inline void ?{}(__small_array(T) & this) {} - - forall(T & | sized(T)) - static inline T & ?[?]( __small_array(T) & this, __lock_size_t idx ) { - return ((typeof(this.data))this.data)[idx]; - } - - forall(T & | sized(T)) - static inline T & ?[?]( const __small_array(T) & this, __lock_size_t idx ) { - return ((typeof(this.data))this.data)[idx]; - } - - forall(T &) - static inline T * begin( const __small_array(T) & this ) { - return ((typeof(this.data))this.data); - } - - forall(T & | sized(T)) - static inline T * end( const __small_array(T) & this ) { - return ((typeof(this.data))this.data) + this.size; - } -#endif - -//----------------------------------------------------------------------------- -// Node Base -//----------------------------------------------------------------------------- - -#ifdef __cforall - forall( T & ) - trait is_node { - T *& get_next( T & ); - }; -#endif - -//----------------------------------------------------------------------------- -// Stack -//----------------------------------------------------------------------------- -#ifdef __cforall - forall(TYPE &) - #define T TYPE -#else - #define T void -#endif -struct __stack { - T * top; -}; -#undef T - -#ifdef __cforall -#define __stack_t(T) __stack(T) -#else -#define __stack_t(T) struct __stack -#endif - -#ifdef __cforall - forall(T &) - static inline void ?{}( __stack(T) & this ) { - (this.top){ 0p }; - } - - static inline forall( T & | is_node(T) ) { - void push( __stack(T) & this, T * val ) { - verify( !get_next( *val ) ); - get_next( *val ) = this.top; - this.top = val; - } - - T * pop( __stack(T) & this ) { - T * top = this.top; - if( top ) { - this.top = get_next( *top ); - get_next( *top ) = 0p; - } - return top; - } - - int ?!=?( const __stack(T) & this, __attribute__((unused)) zero_t zero ) { - return this.top != 0; - } - } -#endif - -//----------------------------------------------------------------------------- -// Queue -//----------------------------------------------------------------------------- -#ifdef __cforall - forall(TYPE &) - #define T TYPE -#else - #define T void -#endif -struct __queue { - T * head; - T ** tail; -}; -#undef T - -#ifdef __cforall -#define __queue_t(T) __queue(T) -#else -#define __queue_t(T) struct __queue -#endif - -#ifdef __cforall - static inline forall( T & | is_node(T) ) { - void ?{}( __queue(T) & this ) with( this ) { - (this.head){ 1p }; - (this.tail){ &this.head }; - verify(*this.tail == 1p); - } - - void append( __queue(T) & this, T * val ) with(this) { - verify(get_next( *val ) == 0p); - verify(this.tail != 0p); - verify(*this.tail == 1p); - *this.tail = val; - this.tail = &get_next( *val ); - *this.tail = 1p; - } - - T * peek( __queue(T) & this ) { - verify(*this.tail == 1p); - T * frontnode = this.head; - if( frontnode != 1p ) { - verify(*this.tail == 1p); - return frontnode; - } - verify(*this.tail == 1p); - return 0p; - } - - T * pop_head( __queue(T) & this ) { - verify(*this.tail == 1p); - T * _head = this.head; - if( _head != 1p ) { - this.head = get_next( *_head ); - if( get_next( *_head ) == 1p ) { - this.tail = &this.head; - } - get_next( *_head ) = 0p; - verify(*this.tail == 1p); - verify( get_next(*_head) == 0p ); - return _head; - } - verify(*this.tail == 1p); - return 0p; - } - - T * remove( __queue(T) & this, T ** it ) with( this ) { - T * val = *it; - verify( val ); - - (*it) = get_next( *val ); - - if( this.tail == &get_next( *val ) ) { - this.tail = it; - } - - get_next( *val ) = 0p; - - verify( (this.head == 1p) == (&this.head == this.tail) ); - verify( *this.tail == 1p ); - return val; - } - - int ?!=?( const __queue(T) & this, __attribute__((unused)) zero_t zero ) { - return this.head != 1p; - } - } -#endif - - -//----------------------------------------------------------------------------- -// Doubly Linked List -//----------------------------------------------------------------------------- -#ifdef __cforall - forall(TYPE &) - #define T TYPE - #define __getter_t * [T * & next, T * & prev] ( T & ) -#else - typedef void (*__generit_c_getter_t)(); - #define T void - #define __getter_t __generit_c_getter_t -#endif -struct __dllist { - T * head; - __getter_t __get; -}; -#undef T -#undef __getter_t - -#ifdef __cforall -#define __dllist_t(T) __dllist(T) -#else -#define __dllist_t(T) struct __dllist -#endif - -#ifdef __cforall - forall(T & ) - static inline [void] ?{}( __dllist(T) & this, * [T * & next, T * & prev] ( T & ) __get ) { - (this.head){ 0p }; - this.__get = __get; - } - - #define next 0 - #define prev 1 - static inline forall(T &) { - void push_front( __dllist(T) & this, T & node ) with( this ) { - verify(__get); - if ( this.head ) { - __get( node ).next = this.head; - __get( node ).prev = __get( *this.head ).prev; - // inserted node must be consistent before it is seen - // prevent code movement across barrier - asm( "" : : : "memory" ); - __get( *this.head ).prev = &node; - T & _prev = *__get( node ).prev; - __get( _prev ).next = &node; - } else { - __get( node ).next = &node; - __get( node ).prev = &node; - } - - // prevent code movement across barrier - asm( "" : : : "memory" ); - this.head = &node; - } - - void remove( __dllist(T) & this, T & node ) with( this ) { - verify(__get); - if ( &node == this.head ) { - if ( __get( *this.head ).next == this.head ) { - this.head = 0p; - } else { - this.head = __get( *this.head ).next; - } - } - __get( *__get( node ).next ).prev = __get( node ).prev; - __get( *__get( node ).prev ).next = __get( node ).next; - __get( node ).next = 0p; - __get( node ).prev = 0p; - } - - int ?!=?( const __dllist(T) & this, __attribute__((unused)) zero_t zero ) { - return this.head != 0; - } - - void move_to_front( __dllist(T) & src, __dllist(T) & dst, T & node ) { - remove (src, node); - push_front(dst, node); - } - } - #undef next - #undef prev -#endif - -//----------------------------------------------------------------------------- -// Tools -//----------------------------------------------------------------------------- -#ifdef __cforall - -#endif - -// Local Variables: // -// tab-width: 4 // -// End: // Index: libcfa/src/bits/weakso_locks.hfa =================================================================== --- libcfa/src/bits/weakso_locks.hfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ libcfa/src/bits/weakso_locks.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -20,6 +20,6 @@ #include "bits/locks.hfa" #include "bits/sequence.hfa" -#include "bits/containers.hfa" -#include "containers/list.hfa" +#include "bits/collections.hfa" +#include "collections/list.hfa" struct select_node; Index: libcfa/src/collections/array.hfa =================================================================== --- libcfa/src/collections/array.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) +++ libcfa/src/collections/array.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -0,0 +1,270 @@ +#pragma once + +#include + + +forall( __CFA_tysys_id_only_X & ) struct tag {}; +#define ttag(T) ((tag(T)){}) +#define ztag(n) ttag(n) + + +// +// The `array` macro is the public interface. +// It computes the type of a dense (trivially strided) array. +// All user-declared objects are dense arrays. +// +// The `arpk` (ARray with PacKing info explicit) type is, generally, a slice with _any_ striding. +// This type is meant for internal use. +// CFA programmers should not instantiate it directly, nor access its field. +// CFA programmers should call ?[?] on it. +// Yet user-given `array(stuff)` expands to `arpk(stuff')`. +// The comments here explain the resulting internals. +// +// Just as a plain-C "multidimesional" array is really array-of-array-of-..., +// so does arpk generally show up as arpk-of-arpk-of... +// +// In the example of `array(float, 3, 4, 5) a;`, +// `typeof(a)` is an `arpk` instantiation. +// These comments explain _its_ arguments, i.e. those of the topmost `arpk` level. +// +// [N] : the number of elements in `a`; 3 in the example +// S : carries the stride size (distance in bytes between &myA[0] and &myA[1]), in sizeof(S); +// same as Timmed when striding is trivial, same as Timmed in the example +// Timmed : (T-immediate) the inner type; conceptually, `typeof(a)` is "arpk of Timmed"; +// array(float, 4, 5) in the example +// Tbase : (T-base) the deepest element type that is not arpk; float in the example +// +forall( [N], S & | sized(S), Timmed &, Tbase & ) { + + // + // Single-dim array sruct (with explicit packing and atom) + // + struct arpk { + S strides[N]; + }; + + // About the choice of integral types offered as subscript overloads: + // Intent is to cover these use cases: + // a[0] // i : zero_t + // a[1] // i : one_t + // a[2] // i : int + // float foo( ptrdiff_t i ) { return a[i]; } // i : ptrdiff_t + // float foo( size_t i ) { return a[i]; } // i : size_t + // forall( [N] ) ... for( i; N ) { total += a[i]; } // i : typeof( sizeof(42) ) + // for( i; 5 ) { total += a[i]; } // i : int + // + // It gets complicated by: + // - CFA does overloading on concrete types, like int and unsigned int, not on typedefed + // types like size_t. So trying to overload on ptrdiff_t vs int works in 64-bit mode + // but not in 32-bit mode. + // - Given bug of Trac #247, CFA gives sizeof expressions type unsigned long int, when it + // should give them type size_t. + // + // gcc -m32 cfa -m32 given bug gcc -m64 (and cfa) + // ptrdiff_t int int long int + // size_t unsigned int unsigned int unsigned long int + // typeof( sizeof(42) ) unsigned int unsigned long int unsigned long int + // int int int int + // + // So the solution must support types {zero_t, one_t, int, unsigned int, long int, unsigned long int} + // + // The solution cannot rely on implicit conversions (e.g. just have one overload for ptrdiff_t) + // because assertion satisfaction requires types to match exacly. Both higher-dimensional + // subscripting and operations on slices use asserted subscript operators. The test case + // array-container/array-sbscr-cases covers the combinations. Mike beleives that commenting out + // any of the current overloads leads to one of those cases failing, either on 64- or 32-bit. + // Mike is open to being shown a smaller set of overloads that still passes the test. + + static inline Timmed & ?[?]( arpk(N, S, Timmed, Tbase) & a, zero_t ) { + assert( 0 < N ); + return (Timmed &) a.strides[0]; + } + + static inline Timmed & ?[?]( arpk(N, S, Timmed, Tbase) & a, one_t ) { + assert( 1 < N ); + return (Timmed &) a.strides[1]; + } + + static inline Timmed & ?[?]( arpk(N, S, Timmed, Tbase) & a, int i ) { + assert( i < N ); + return (Timmed &) a.strides[i]; + } + + static inline const Timmed & ?[?]( const arpk(N, S, Timmed, Tbase) & a, int i ) { + assert( i < N ); + return (Timmed &) a.strides[i]; + } + + static inline Timmed & ?[?]( arpk(N, S, Timmed, Tbase) & a, unsigned int i ) { + assert( i < N ); + return (Timmed &) a.strides[i]; + } + + static inline const Timmed & ?[?]( const arpk(N, S, Timmed, Tbase) & a, unsigned int i ) { + assert( i < N ); + return (Timmed &) a.strides[i]; + } + + static inline Timmed & ?[?]( arpk(N, S, Timmed, Tbase) & a, long int i ) { + assert( i < N ); + return (Timmed &) a.strides[i]; + } + + static inline const Timmed & ?[?]( const arpk(N, S, Timmed, Tbase) & a, long int i ) { + assert( i < N ); + return (Timmed &) a.strides[i]; + } + + static inline Timmed & ?[?]( arpk(N, S, Timmed, Tbase) & a, unsigned long int i ) { + assert( i < N ); + return (Timmed &) a.strides[i]; + } + + static inline const Timmed & ?[?]( const arpk(N, S, Timmed, Tbase) & a, unsigned long int i ) { + assert( i < N ); + return (Timmed &) a.strides[i]; + } + + static inline size_t ?`len( arpk(N, S, Timmed, Tbase) & a ) { + return N; + } + + static inline void __taglen( tag(arpk(N, S, Timmed, Tbase)), tag(N) ) {} + + // workaround #226 (and array relevance thereof demonstrated in mike102/otype-slow-ndims.cfa) + static inline void ?{}( arpk(N, S, Timmed, Tbase) & this ) { + void ?{}( S (&inner)[N] ) {} + ?{}(this.strides); + } + static inline void ^?{}( arpk(N, S, Timmed, Tbase) & this ) { + void ^?{}( S (&inner)[N] ) {} + ^?{}(this.strides); + } +} + +// +// Sugar for declaring array structure instances +// + +forall( Te ) +static inline Te mkar_( tag(Te) ) {} + +forall( [N], ZTags ... , Trslt &, Tatom & | { Trslt mkar_( tag(Tatom), ZTags ); } ) +static inline arpk(N, Trslt, Trslt, Tatom) mkar_( tag(Tatom), tag(N), ZTags ) {} + +// based on https://stackoverflow.com/questions/1872220/is-it-possible-to-iterate-over-arguments-in-variadic-macros + + // Make a FOREACH macro + #define FE_0(WHAT) + #define FE_1(WHAT, X) WHAT(X) + #define FE_2(WHAT, X, ...) WHAT(X)FE_1(WHAT, __VA_ARGS__) + #define FE_3(WHAT, X, ...) WHAT(X)FE_2(WHAT, __VA_ARGS__) + #define FE_4(WHAT, X, ...) WHAT(X)FE_3(WHAT, __VA_ARGS__) + #define FE_5(WHAT, X, ...) WHAT(X)FE_4(WHAT, __VA_ARGS__) + //... repeat as needed + + #define GET_MACRO(_0,_1,_2,_3,_4,_5,NAME,...) NAME + #define FOR_EACH(action,...) \ + GET_MACRO(_0,__VA_ARGS__,FE_5,FE_4,FE_3,FE_2,FE_1,FE_0)(action,__VA_ARGS__) + +#define COMMA_ttag(X) , ttag(X) +#define array( TE, ...) typeof( mkar_( ttag(TE) FOR_EACH( COMMA_ttag, __VA_ARGS__ ) ) ) + +#define COMMA_ztag(X) , ztag(X) +#define zarray( TE, ...) typeof( mkar_( ttag(TE) FOR_EACH( COMMA_ztag, __VA_ARGS__ ) ) ) + +// +// Sugar for multidimensional indexing +// + +// Core -[[-,-,-]] operator + +#ifdef TRY_BROKEN_DESIRED_MD_SUBSCRIPT + +// Desired form. One definition with recursion on IxBC (worked until Jan 2021, see trac #__TODO__) + +forall( TA &, TB &, TC &, IxAB, IxBC ... | { TB & ?[?]( TA &, IxAB ); TC & ?[?]( TB &, IxBC ); } ) +static inline TC & ?[?]( TA & this, IxAB ab, IxBC bc ) { + return this[ab][bc]; +} + +#else + +// Workaround form. Listing all possibilities up to 4 dims. + +forall( TA &, TB &, TC &, IxAB_0, IxBC | { TB & ?[?]( TA &, IxAB_0 ); TC & ?[?]( TB &, IxBC ); } ) +static inline TC & ?[?]( TA & this, IxAB_0 ab, IxBC bc ) { + return this[ab][bc]; +} + +forall( TA &, TB &, TC &, IxAB_0, IxAB_1, IxBC | { TB & ?[?]( TA &, IxAB_0, IxAB_1 ); TC & ?[?]( TB &, IxBC ); } ) +static inline TC & ?[?]( TA & this, IxAB_0 ab0, IxAB_1 ab1, IxBC bc ) { + return this[[ab0,ab1]][bc]; +} + +forall( TA &, TB &, TC &, IxAB_0, IxAB_1, IxAB_2, IxBC | { TB & ?[?]( TA &, IxAB_0, IxAB_1, IxAB_2 ); TC & ?[?]( TB &, IxBC ); } ) +static inline TC & ?[?]( TA & this, IxAB_0 ab0, IxAB_1 ab1, IxAB_2 ab2, IxBC bc ) { + return this[[ab0,ab1,ab2]][bc]; +} + +#endif + +// Available for users to work around Trac #265 +// If `a[...0...]` isn't working, try `a[...ix0...]` instead. + +#define ix0 ((ptrdiff_t)0) + + + +// +// Rotation +// + +// Base +forall( [Nq], Sq & | sized(Sq), Tbase & ) +static inline tag(arpk(Nq, Sq, Tbase, Tbase)) enq_( tag(Tbase), tag(Nq), tag(Sq), tag(Tbase) ) { + tag(arpk(Nq, Sq, Tbase, Tbase)) ret; + return ret; +} + +// Rec +forall( [Nq], Sq & | sized(Sq), [N], S & | sized(S), recq &, recr &, Tbase & | { tag(recr) enq_( tag(Tbase), tag(Nq), tag(Sq), tag(recq) ); } ) +static inline tag(arpk(N, S, recr, Tbase)) enq_( tag(Tbase), tag(Nq), tag(Sq), tag(arpk(N, S, recq, Tbase)) ) { + tag(arpk(N, S, recr, Tbase)) ret; + return ret; +} + +// Wrapper +extern struct all_t {} all; +forall( [N], S & | sized(S), Te &, result &, Tbase & | { tag(result) enq_( tag(Tbase), tag(N), tag(S), tag(Te) ); } ) +static inline result & ?[?]( arpk(N, S, Te, Tbase) & this, all_t ) { + return (result&) this; +} + +// +// Trait of array or slice +// + +// desired: +// forall(A &, Tv &, [N]) +// trait ar { +// Tv& ?[?]( A&, zero_t ); +// Tv& ?[?]( A&, one_t ); +// Tv& ?[?]( A&, int ); +// ... +// size_t ?`len( A& ); +// void __taglen( tag(C), tag(N) ); +// }; + +// working around N's not being accepted as arguments to traits + +#define ar(A, Tv, N) { \ + Tv& ?[?]( A&, zero_t ); \ + Tv& ?[?]( A&, one_t ); \ + Tv& ?[?]( A&, int ); \ + Tv& ?[?]( A&, unsigned int ); \ + Tv& ?[?]( A&, long int ); \ + Tv& ?[?]( A&, unsigned long int ); \ + size_t ?`len( A& ); \ + void __taglen( tag(A), tag(N) ); \ +} Index: libcfa/src/collections/list.hfa =================================================================== --- libcfa/src/collections/list.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) +++ libcfa/src/collections/list.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -0,0 +1,325 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2020 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// list -- lets a user-defined stuct form intrusive linked lists +// +// Author : Michael Brooks +// Created On : Wed Apr 22 18:00:00 2020 +// Last Modified By : Peter A. Buhr +// Last Modified On : Thu Feb 2 11:32:26 2023 +// Update Count : 2 +// + +#pragma once + +#include + +forall( Decorator &, T & ) +struct tytagref { + inline T &; +}; + +forall( tOuter &, tMid &, tInner & ) +trait embedded { + tytagref( tMid, tInner ) ?`inner( tOuter & ); +}; + +// embedded is reflexive, with no info (void) as the type tag +forall (T &) +static inline tytagref(void, T) ?`inner ( T & this ) { tytagref( void, T ) ret = {this}; return ret; } + + +// +// P9_EMBEDDED: Use on every case of plan-9 inheritance, to make "implements embedded" be a closure of plan-9 inheritance. +// +// struct foo { +// int a, b, c; +// inline (bar); +// }; +// P9_EMBEDDED( foo, bar ) +// + +// usual version, for structs that are top-level declarations +#define P9_EMBEDDED( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, static ) P9_EMBEDDED_BDY_( immedBase ) + +// special version, for structs that are declared in functions +#define P9_EMBEDDED_INFUNC( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, ) P9_EMBEDDED_BDY_( immedBase ) + +// forward declarations of both the above; generally not needed +// may help you control where the P9_EMBEEDED cruft goes, in case "right after the stuct" isn't where you want it +#define P9_EMBEDDED_FWD( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, static ) ; +#define P9_EMBEDDED_FWD_INFUNC( derived, immedBase ) auto P9_EMBEDDED_DECL_( derived, immedBase, ) ; + +// private helpers +#define P9_EMBEDDED_DECL_( derived, immedBase, STORAGE ) \ + forall( Tbase &, TdiscardPath & | { tytagref( TdiscardPath, Tbase ) ?`inner( immedBase & ); } ) \ + STORAGE inline tytagref(immedBase, Tbase) ?`inner( derived & this ) + +#define P9_EMBEDDED_BDY_( immedBase ) { \ + immedBase & ib = this; \ + Tbase & b = ib`inner; \ + tytagref(immedBase, Tbase) result = { b }; \ + return result; \ + } + +#define EMBEDDED_VIA( OUTER, MID, INNER ) \ + (struct { tytagref(MID, INNER) ( * ?`inner ) ( OUTER & ); }){ ?`inner } + +#define DLINK_VIA( TE, TLINK ) \ + EMBEDDED_VIA( TE, TLINK, dlink(TE) ) + + +// The origin is the position encountered at the start of iteration, +// signifying, "need to advance to the first element," and at the end +// of iteration, signifying, "no more elements." Normal comsumption of +// an iterator runs ?`moveNext as the first step, and uses the return +// of ?`moveNext as a guard, before dereferencing the iterator. So +// normal consumption of an iterator does not dereference an iterator +// in origin position. The value of a pointer (underlying a refence) +// that is exposed publicly as an iteraor, and also a pointer stored +// internally in a link field, is tagged, to indicate "is the origin" +// (internally, is the list-head sentinel node), or untagged, to indicate +// "is a regular node." Intent is to help a user who dereferences an +// iterator in origin position (which would be an API-use error on their +// part), by failing fast. + +#if defined( __x86_64 ) + // Preferred case: tag in the most-significant bit. Dereference + // has been shown to segfault consistently. Maintenance should + // list more architectures as "ok" here, to let them use the + // preferred case, when valid. + #define ORIGIN_TAG_BITNO ( 8 * sizeof( size_t ) - 1 ) +#else + // Fallback case: tag in the least-significant bit. Dereference + // will often give an alignment error, but may not, e.g. if + // accessing a char-typed member. 32-bit x86 uses the most- + // significant bit for real room on the heap. + #define ORIGIN_TAG_BITNO 0 +#endif +#define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO) + +#define ORIGIN_TAG_SET(p) ((p) | ORIGIN_TAG_MASK) +#define ORIGIN_TAG_CLEAR(p) ((p) & ~ORIGIN_TAG_MASK) +#define ORIGIN_TAG_QUERY(p) ((p) & ORIGIN_TAG_MASK) + + +forall( tE & ) { + + struct dlink{ + tE *next; + tE *prev; + }; + + static inline void ?{}( dlink(tE) & this ) { + this.next = 0p; + this.prev = 0p; + } + + forall( tLinks & = dlink(tE) ) + struct dlist { + inline dlink(tE); + }; + + forall( tLinks & | embedded( tE, tLinks, dlink(tE) ) ) { + static inline tE * $get_list_origin_addr( dlist(tE, tLinks) & lst ) { + dlink(tE) & link_from_null = ( * (tE *) 0p )`inner; + ptrdiff_t link_offset = (ptrdiff_t) & link_from_null; + size_t origin_addr = ((size_t) & lst) - link_offset; + size_t preResult = ORIGIN_TAG_SET( origin_addr ); + return (tE *)preResult; + } + + static inline void ?{}( dlist(tE, tLinks) & this ) { + tE * listOrigin = $get_list_origin_addr( this ); + ( ( dlink(tE) & ) this ){ listOrigin, listOrigin } ; + } + } + +} + + +forall( tE &, tLinks & | embedded( tE, tLinks, dlink(tE) ) ) { + + static inline void insert_after(tE & list_pos, tE &to_insert) { + verify (&list_pos != 0p); + verify (&to_insert != 0p); + dlink(tE) & linkToInsert = to_insert`inner; + verify(linkToInsert.prev == 0p); + verify(linkToInsert.next == 0p); + tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos ); + dlink(tE) & list_pos_links = list_pos_elem`inner; + asm( "" : : : "memory" ); + tE & after_raw = * list_pos_links.next; + tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw ); + linkToInsert.prev = & list_pos; + linkToInsert.next = & after_raw; + dlink(tE) & afterLinks = after_elem`inner; + afterLinks.prev = &to_insert; + list_pos_links.next = &to_insert; + asm( "" : : : "memory" ); + } + + static inline void insert_before(tE & list_pos, tE &to_insert) { + verify (&list_pos != 0p); + verify (&to_insert != 0p); + dlink(tE) & linkToInsert = to_insert`inner; + verify(linkToInsert.next == 0p); + verify(linkToInsert.prev == 0p); + tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos ); + dlink(tE) & list_pos_links = list_pos_elem`inner; + asm( "" : : : "memory" ); + tE & before_raw = * (list_pos_links).prev; + tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw ); + linkToInsert.next = & list_pos; + linkToInsert.prev = & before_raw; + dlink(tE) & beforeLinks = before_elem`inner; + beforeLinks.next = &to_insert; + (list_pos_links).prev = &to_insert; + asm( "" : : : "memory" ); + } + + static inline tE & remove(tE & list_pos) { + verify (&list_pos != 0p); + verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos) ); + dlink(tE) & list_pos_links = list_pos`inner; + tE & before_raw = * list_pos_links.prev; + tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw ); + dlink(tE) & before_links = before_elem`inner; + tE & after_raw = * list_pos_links.next; + tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw ); + dlink(tE) & after_links = after_elem`inner; + before_links.next = &after_raw; + after_links.prev = &before_raw; + asm( "" : : : "memory" ); + list_pos_links.prev = 0p; + list_pos_links.next = 0p; + asm( "" : : : "memory" ); + return list_pos; + } + + static inline tE & ?`first( dlist(tE, tLinks) &lst ) { + tE * firstPtr = lst.next; + if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p; + return *firstPtr; + } + static inline tE & ?`last ( dlist(tE, tLinks) &lst ) { + tE * lastPtr = lst.prev; + if (ORIGIN_TAG_QUERY((size_t)lastPtr)) lastPtr = 0p; + return *lastPtr; + } + + static inline bool ?`isEmpty( dlist(tE, tLinks) & lst ) { + tE * firstPtr = lst.next; + if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p; + return firstPtr == 0p; + } + + static inline bool ?`isListed( tE & e ) { + verify (&e != 0p); + dlink(tE) & e_links = e`inner; + return (e_links.prev != 0p) || (e_links.next != 0p); + } + + static inline tE & ?`elems( dlist(tE, tLinks) & lst ) { + tE * origin = $get_list_origin_addr( lst ); + return *origin; + } + + static inline bool ?`moveNext( tE && refx ) { + tE && ref_inner = refx; + tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner ); + &ref_inner = oldReferent`inner.next; + return &ref_inner != 0p && + ! ORIGIN_TAG_QUERY( (size_t) & ref_inner ); + } + + static inline bool ?`movePrev( tE && refx ) { + tE && ref_inner = refx; + tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner ); + &ref_inner = oldReferent`inner.prev; + return &ref_inner != 0p && + ! ORIGIN_TAG_QUERY( (size_t) & ref_inner ); + } + + static inline bool ?`hasNext( tE & e ) { + return e`moveNext; + } + + static inline bool ?`hasPrev( tE & e ) { + return e`movePrev; + } + + static inline tE & ?`next( tE & e ) { + if( e`moveNext ) return e; + return * 0p; + } + + static inline tE & ?`prev( tE & e ) { + if( e`movePrev ) return e; + return * 0p; + } + + static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) { + insert_after(lst`elems, e); + } + + static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) { + insert_before(lst`elems, e); + } + + static inline tE & try_pop_front( dlist(tE, tLinks) &lst ) { + tE & first_inlist = lst`first; + tE & first_item = first_inlist; + if (&first_item) remove(first_inlist); + return first_item; + } + + static inline tE & try_pop_back( dlist(tE, tLinks) &lst ) { + tE & last_inlist = lst`last; + tE & last_item = last_inlist; + if (&last_item) remove(last_inlist); + return last_item; + } + + + #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__)) + static bool $validate_fwd( dlist(tE, tLinks) & this ) { + if ( ! & this`first ) return ( (& this`last) == 0p); + + tE & lagElem = *0p; + + while ( tE & it = this`elems; it`moveNext ) { + if (& lagElem == 0p && &it != & this`first ) return false; + & lagElem = & it; + } + + if (& lagElem != & this`last) return false; + + // TODO: verify that it is back at this`elems; + return true; + } + static bool $validate_rev( dlist(tE, tLinks) & this ) { + if ( ! & this`last ) return ( (& this`first) == 0p); + + tE & lagElem = *0p; + + while ( tE & it = this`elems; it`movePrev ) { + if (& lagElem == 0p && &it != & this`last ) return false; + & lagElem = & it; + } + + if (& lagElem != & this`first) return false; + + // TODO: verify that it is back at this`elems; + return true; + } + static bool validate( dlist(tE, tLinks) & this ) { + return $validate_fwd(this) && $validate_rev(this); + } + #endif + +} + Index: libcfa/src/collections/lockfree.hfa =================================================================== --- libcfa/src/collections/lockfree.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) +++ libcfa/src/collections/lockfree.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -0,0 +1,258 @@ +#pragma once + +#include + +#include +#include + +forall( T &) { + //------------------------------------------------------------ + // Queue based on the MCS lock + // It is a Multi-Producer/Single-Consumer queue threads pushing + // elements must hold on to the elements they push + // Not appropriate for an async message queue for example, + struct mcs_queue { + T * volatile tail; + }; + + static inline void ?{}(mcs_queue(T) & this) { this.tail = 0p; } + static inline bool empty(const mcs_queue(T) & this) { return !this.tail; } + + static inline forall(| { T * volatile & ?`next ( T * ); }) + { + // Adds an element to the list + // Multi-Thread Safe, Lock-Free + T * push(mcs_queue(T) & this, T * elem) __attribute__((artificial)); + T * push(mcs_queue(T) & this, T * elem) { + /* paranoid */ verify(!(elem`next)); + // Race to add to the tail + T * prev = __atomic_exchange_n(&this.tail, elem, __ATOMIC_SEQ_CST); + // If we aren't the first, we need to tell the person before us + // No need to + if (prev) prev`next = elem; + return prev; + } + + // Advances the head of the list, dropping the element given. + // Passing an element that is not the head is undefined behavior + // NOT Multi-Thread Safe, concurrent pushes are safe + T * advance(mcs_queue(T) & this, T * elem) __attribute__((artificial)); + T * advance(mcs_queue(T) & this, T * elem) { + T * expected = elem; + // Check if this is already the last item + if (__atomic_compare_exchange_n(&this.tail, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) return 0p; + + // If not wait for next item to show-up, filled by push + while (!(elem`next)) Pause(); + + // we need to return if the next link was empty + T * ret = elem`next; + + // invalidate link to reset to initial state + elem`next = 0p; + return ret; + } + } + + //------------------------------------------------------------ + // Queue based on the MCS lock + // Extension of the above lock which supports 'blind' pops. + // i.e., popping a value from the head without knowing what the head is + // has no extra guarantees beyond the mcs_queue + struct mpsc_queue { + inline mcs_queue(T); + T * volatile head; + }; + + static inline void ?{}(mpsc_queue(T) & this) { + ((mcs_queue(T)&)this){}; + this.head = 0p; + } + + static inline forall(| { T * volatile & ?`next ( T * ); }) + { + // Added a new element to the queue + // Multi-Thread Safe, Lock-Free + T * push(mpsc_queue(T) & this, T * elem) __attribute__((artificial)); + T * push(mpsc_queue(T) & this, T * elem) { + T * prev = push((mcs_queue(T)&)this, elem); + if (!prev) this.head = elem; + return prev; + } + + // Pop an element from the queue + // return the element that was removed + // next is set to the new head of the queue + // NOT Multi-Thread Safe + T * pop(mpsc_queue(T) & this, T *& next) __attribute__((artificial)); + T * pop(mpsc_queue(T) & this, T *& next) { + T * elem = this.head; + // If head is empty just return + if (!elem) return 0p; + + // If there is already someone in the list, then it's easy + if (elem`next) { + this.head = next = elem`next; + // force memory sync + __atomic_thread_fence(__ATOMIC_SEQ_CST); + + // invalidate link to reset to initial state + elem`next = 0p; + } + // Otherwise, there might be a race where it only looks but someone is enqueuing + else { + // null out head here, because we linearize with push + // at the CAS in advance and therefore can write to head + // after that point, it could overwrite the write in push + this.head = 0p; + next = advance((mcs_queue(T)&)this, elem); + + // Only write to the head if there is a next element + // it is the only way we can guarantee we are not overwriting + // a write made in push + if (next) this.head = next; + } + + // return removed element + return elem; + } + + // Same as previous function + T * pop(mpsc_queue(T) & this) { + T * _ = 0p; + return pop(this, _); + } + } + + //------------------------------------------------------------ + // Queue based on the MCS lock with poisoning + // It is a Multi-Producer/Single-Consumer queue threads pushing + // elements must hold on to the elements they push + // Not appropriate for an async message queue for example + // poisoning the queue prevents any new elements from being push + // enum(void*) poison_state { + // EMPTY = 0p, + // POISON = 1p, + // IN_PROGRESS = 1p + // }; + + struct poison_list { + T * volatile head; + }; + + static inline void ?{}(poison_list(T) & this) { this.head = 0p; } + static inline bool is_poisoned( const poison_list(T) & this ) { return 1p == this.head; } + + static inline forall(| { T * volatile & ?`next ( T * ); }) + { + // Adds an element to the list + // Multi-Thread Safe, Lock-Free + bool push(poison_list(T) & this, T * elem) __attribute__((artificial)); + bool push(poison_list(T) & this, T * elem) { + /* paranoid */ verify(0p == (elem`next)); + __atomic_store_n( &elem`next, (T*)1p, __ATOMIC_RELAXED ); + + // read the head up-front + T * expected = this.head; + for() { + // check if it's poisoned + if(expected == 1p) return false; + + // try to CAS the elem in + if(__atomic_compare_exchange_n(&this.head, &expected, elem, true, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED)) { + // We managed to exchange in, we are done + + // We should never succeed the CAS if it's poisonned and the elem should be 1p. + /* paranoid */ verify( expected != 1p ); + /* paranoid */ verify( elem`next == 1p ); + + // If we aren't the first, we need to tell the person before us + // No need to + elem`next = expected; + return true; + } + } + } + + // Advances the head of the list, dropping the element given. + // Passing an element that is not the head is undefined behavior + // NOT Multi-Thread Safe, concurrent pushes are safe + T * advance(T * elem) __attribute__((artificial)); + T * advance(T * elem) { + T * ret; + + // Wait for next item to show-up, filled by push + while (1p == (ret = __atomic_load_n(&elem`next, __ATOMIC_RELAXED))) Pause(); + + return ret; + } + + // Poison the queue, preveting new pushes and returning the head + T * poison(poison_list(T) & this) __attribute__((artificial)); + T * poison(poison_list(T) & this) { + T * ret = __atomic_exchange_n( &this.head, (T*)1p, __ATOMIC_SEQ_CST ); + /* paranoid */ verifyf( ret != (T*)1p, "Poison list %p poisoned more than once!", &this ); + return ret; + } + } +} + +forall( T & ) +struct LinkData { + T * volatile top; // pointer to stack top + uintptr_t count; // count each push +}; + +forall( T & ) +union Link { + LinkData(T) data; + #if __SIZEOF_INT128__ == 16 + __int128 // gcc, 128-bit integer + #else + uint64_t // 64-bit integer + #endif // __SIZEOF_INT128__ == 16 + atom; +}; // Link + +forall( T | sized(T) | { Link(T) * ?`next( T * ); } ) { + struct StackLF { + Link(T) stack; + }; // StackLF + + static inline { + void ?{}( StackLF(T) & this ) with(this) { stack.atom = 0; } + + T * top( StackLF(T) & this ) with(this) { return stack.data.top; } + + void push( StackLF(T) & this, T & n ) with(this) { + *( &n )`next = stack; // atomic assignment unnecessary, or use CAA + for () { // busy wait + if ( __atomic_compare_exchange_n( &stack.atom, &( &n )`next->atom, (Link(T))@{ (LinkData(T))@{ &n, ( &n )`next->data.count + 1} }.atom, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) break; // attempt to update top node + } // for + } // push + + T * pop( StackLF(T) & this ) with(this) { + Link(T) t @= stack; // atomic assignment unnecessary, or use CAA + for () { // busy wait + if ( t.data.top == 0p ) return 0p; // empty stack ? + Link(T) * next = ( t.data.top )`next; + if ( __atomic_compare_exchange_n( &stack.atom, &t.atom, (Link(T))@{ (LinkData(T))@{ next->data.top, t.data.count } }.atom, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) return t.data.top; // attempt to update top node + } // for + } // pop + + bool unsafe_remove( StackLF(T) & this, T * node ) with(this) { + Link(T) * link = &stack; + for () { + // TODO: Avoiding some problems with double fields access. + LinkData(T) * data = &link->data; + T * next = (T *)&(*data).top; + if ( next == node ) { + data->top = ( node )`next->data.top; + return true; + } + if ( next == 0p ) return false; + link = ( next )`next; + } + } + } // distribution +} // distribution Index: libcfa/src/collections/maybe.cfa =================================================================== --- libcfa/src/collections/maybe.cfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) +++ libcfa/src/collections/maybe.cfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -0,0 +1,103 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// maybe.c -- May contain a value. +// +// Author : Andrew Beach +// Created On : Wed May 24 15:40:00 2017 +// Last Modified By : Peter A. Buhr +// Last Modified On : Wed Aug 30 21:26:55 2023 +// Update Count : 4 +// + +#include +#include + +#pragma GCC visibility push(default) + +forall(T) +void ?{}(maybe(T) & this) { + this.has_value = false; +} + +forall(T) +void ?{}(maybe(T) & this, T value) { + this.has_value = true; + (this.value){value}; +} + +forall(T) +void ?{}(maybe(T) & this, maybe(T) other) { + this.has_value = other.has_value; + if (other.has_value) { + (this.value){other.value}; + } +} + +forall(T) +maybe(T) ?=?(maybe(T) & this, maybe(T) that) { + if (this.has_value && that.has_value) { + this.value = that.value; + } else if (this.has_value) { + ^(this.value){}; + this.has_value = false; + } else if (that.has_value) { + this.has_value = true; + (this.value){that.value}; + } + return this; +} + +forall(T) +void ^?{}(maybe(T) & this) { + if (this.has_value) { + ^(this.value){}; + } +} + +forall(T) +bool ?!=?(maybe(T) this, zero_t) { + return this.has_value; +} + +forall(T) +maybe(T) maybe_value(T value) { + return (maybe(T)){value}; +} + +forall(T) +maybe(T) maybe_none() { + return (maybe(T)){}; +} + +forall(T) +bool has_value(maybe(T) * this) { + return this->has_value; +} + +forall(T) +T get(maybe(T) * this) { + assertf(this->has_value, "attempt to get from maybe without value"); + return this->value; +} + +forall(T) +void set(maybe(T) * this, T value) { + if (this->has_value) { + this->value = value; + } else { + this->has_value = true; + (this->value){value}; + } +} + +forall(T) +void set_none(maybe(T) * this) { + if (this->has_value) { + this->has_value = false; + ^(this->value){}; + } +} Index: libcfa/src/collections/maybe.hfa =================================================================== --- libcfa/src/collections/maybe.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) +++ libcfa/src/collections/maybe.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -0,0 +1,69 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// maybe -- May contain a value. +// +// Author : Andrew Beach +// Created On : Wed May 24 14:43:00 2017 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sat Jul 22 10:00:52 2017 +// Update Count : 4 +// + +#pragma once + +#include + +// DO NOT USE DIRECTLY! +forall(T) +struct maybe { + bool has_value; + T value; +}; + + +forall(T) +void ?{}(maybe(T) & this); + +forall(T) +void ?{}(maybe(T) & this, T value); + +forall(T) +void ?{}(maybe(T) & this, maybe(T) other); + +forall(T) +void ^?{}(maybe(T) & this); + +forall(T) +maybe(T) ?=?(maybe(T) & this, maybe(T) other); + +forall(T) +bool ?!=?(maybe(T) this, zero_t); + +/* Waiting for bug#11 to be fixed. +forall(T) +maybe(T) maybe_value(T value); + +forall(T) +maybe(T) maybe_none(); +*/ + +forall(T) +bool has_value(maybe(T) * this); + +forall(T) +T get(maybe(T) * this); + +forall(T) +void set(maybe(T) * this, T value); + +forall(T) +void set_none(maybe(T) * this); + +// Local Variables: // +// mode: c // +// tab-width: 4 // +// End: // Index: libcfa/src/collections/pair.cfa =================================================================== --- libcfa/src/collections/pair.cfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) +++ libcfa/src/collections/pair.cfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -0,0 +1,47 @@ +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// pair.c -- +// +// Author : Aaron Moss +// Created On : Wed Apr 12 15:32:00 2017 +// Last Modified By : Peter A. Buhr +// Last Modified On : Wed Aug 30 21:27:12 2023 +// Update Count : 2 +// + +#include + +forall(R, S + | { int ?==?(R, R); int ??(R, R); int ?>?(S, S); }) +int ?>?(pair(R, S) p, pair(R, S) q) { + return p.first > q.first || ( p.first == q.first && p.second > q.second ); +} + +forall(R, S + | { int ?==?(R, R); int ?>?(R, R); int ?>=?(S, S); }) +int ?>=?(pair(R, S) p, pair(R, S) q) { + return p.first > q.first || ( p.first == q.first && p.second >= q.second ); +} Index: libcfa/src/collections/pair.hfa =================================================================== --- libcfa/src/collections/pair.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) +++ libcfa/src/collections/pair.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -0,0 +1,48 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// pair -- +// +// Author : Aaron Moss +// Created On : Wed Apr 12 15:32:00 2017 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sat Jul 22 09:59:53 2017 +// Update Count : 2 +// + +#pragma once + +forall(R, S) struct pair { + R first; + S second; +}; + +forall(R, S + | { int ?==?(R, R); int ??(R, R); int ?>?(S, S); }) +int ?>?(pair(R, S) p, pair(R, S) q); + +forall(R, S + | { int ?==?(R, R); int ?>?(R, R); int ?>=?(S, S); }) +int ?>=?(pair(R, S) p, pair(R, S) q); + +// Local Variables: // +// mode: c // +// tab-width: 4 // +// End: // Index: libcfa/src/collections/result.cfa =================================================================== --- libcfa/src/collections/result.cfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) +++ libcfa/src/collections/result.cfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -0,0 +1,127 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// result.c -- Contains the expected value or an error value. +// +// Author : Andrew Beach +// Created On : Wed May 24 15:40:00 2017 +// Last Modified By : Peter A. Buhr +// Last Modified On : Wed Aug 30 21:27:22 2023 +// Update Count : 4 +// + +#include +#include + +#pragma GCC visibility push(default) + +forall(T, E) +void ?{}(result(T, E) & this) { + this.has_value = false; + (this.error){}; +} + +forall(T, E) +void ?{}(result(T, E) & this, one_t, T value) { + this.has_value = true; + (this.value){value}; +} + +forall(T, E) +void ?{}(result(T, E) & this, zero_t, E error) { + this.has_value = false; + (this.error){error}; +} + +forall(T, E) +void ?{}(result(T, E) & this, result(T, E) other) { + this.has_value = other.has_value; + if (other.has_value) { + (this.value){other.value}; + } else { + (this.error){other.error}; + } +} + +forall(T, E) +result(T, E) ?=?(result(T, E) & this, result(T, E) that) { + if (this.has_value && that.has_value) { + this.value = that.value; + } else if (this.has_value) { + ^(this.value){}; + this.has_value = false; + (this.error){that.error}; + } else if (that.has_value) { + ^(this.error){}; + this.has_value = true; + (this.value){that.value}; + } else { + this.error = that.error; + } +} + +forall(T, E) +void ^?{}(result(T, E) & this) { + if (this.has_value) { + ^(this.value){}; + } else { + ^(this.error){}; + } +} + +forall(T, E) +bool ?!=?(result(T, E) this, zero_t) { + return this.has_value; +} + +forall(T, E) +result(T, E) result_value(T value) { + return (result(T, E)){1, value}; +} + +forall(T, E) +result(T, E) result_error(E error) { + return (result(T, E)){0, error}; +} + +forall(T, E) +bool has_value(result(T, E) * this) { + return this->has_value; +} + +forall(T, E) +T get(result(T, E) * this) { + assertf(this->has_value, "attempt to get from result without value"); + return this->value; +} + +forall(T, E) +E get_error(result(T, E) * this) { + assertf(!this->has_value, "attempt to get from result without error"); + return this->error; +} + +forall(T, E) +void set(result(T, E) * this, T value) { + if (this->has_value) { + this->value = value; + } else { + ^(this->error){}; + this->has_value = true; + (this->value){value}; + } +} + +forall(T, E) +void set_error(result(T, E) * this, E error) { + if (this->has_value) { + ^(this->value){}; + this->has_value = false; + (this->error){error}; + } else { + this->error = error; + } +} Index: libcfa/src/collections/result.hfa =================================================================== --- libcfa/src/collections/result.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) +++ libcfa/src/collections/result.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -0,0 +1,81 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// result -- Contains the expected value or an error value. +// +// Author : Andrew Beach +// Created On : Wed May 24 14:45:00 2017 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sat Jul 22 10:00:44 2017 +// Update Count : 3 +// + +#pragma once + +#include + +// DO NOT USE DIRECTLY! +forall(T, E) +union inner_result{ + T value; + E error; +}; + +forall(T, E) +struct result { + bool has_value; + inline union inner_result(T, E); +}; + + +forall(T, E) +void ?{}(result(T, E) & this); + +forall(T, E) +void ?{}(result(T, E) & this, one_t, T value); + +forall(T, E) +void ?{}(result(T, E) & this, zero_t, E error); + +forall(T, E) +void ?{}(result(T, E) & this, result(T, E) other); + +forall(T, E) +void ^?{}(result(T, E) & this); + +forall(T, E) +result(T, E) ?=?(result(T, E) & this, result(T, E) other); + +forall(T, E) +bool ?!=?(result(T, E) this, zero_t); + +/* Wating for bug#11 to be fixed. +forall(T, E) +result(T, E) result_value(T value); + +forall(T, E) +result(T, E) result_error(E error); +*/ + +forall(T, E) +bool has_value(result(T, E) * this); + +forall(T, E) +T get(result(T, E) * this); + +forall(T, E) +E get_error(result(T, E) * this); + +forall(T, E) +void set(result(T, E) * this, T value); + +forall(T, E) +void set_error(result(T, E) * this, E error); + +// Local Variables: // +// mode: c // +// tab-width: 4 // +// End: // Index: libcfa/src/collections/string.cfa =================================================================== --- libcfa/src/collections/string.cfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) +++ libcfa/src/collections/string.cfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -0,0 +1,391 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// string -- variable-length, mutable run of text, with value semantics +// +// Author : Michael L. Brooks +// Created On : Fri Sep 03 11:00:00 2021 +// Last Modified By : Peter A. Buhr +// Last Modified On : Thu Aug 31 13:20:41 2023 +// Update Count : 161 +// + +#include "string.hfa" +#include "string_res.hfa" +#include + +#pragma GCC visibility push(default) + +/* +Implementation Principle: typical operation translates to the equivalent +operation on `inner`. Exceptions are implementing new RAII pattern for value +semantics and some const-hell handling. +*/ + +//////////////////////////////////////////////////////// +// string RAII + + +void ?{}( string & this ) { + (this.inner) { malloc() }; + ?{}( *this.inner ); +} + +// private (not in header) +static void ?{}( string & this, string_res & src, size_t start, size_t end ) { + (this.inner) { malloc() }; + ?{}( *this.inner, src, SHARE_EDITS, start, end ); +} + +void ?{}( string & this, const string & other ) { + (this.inner) { malloc() }; + ?{}( *this.inner, *other.inner, COPY_VALUE ); +} + +void ?{}( string & this, string & other ) { + ?{}( this, (const string &) other ); +} + +void ?{}( string & this, const char * val ) { + (this.inner) { malloc() }; + ?{}( *this.inner, val ); +} + +void ?{}( string & this, const char * buffer, size_t bsize) { + (this.inner) { malloc() }; + ?{}( *this.inner, buffer, bsize ); +} + +void ^?{}( string & this ) { + ^(*this.inner){}; + free( this.inner ); + this.inner = 0p; +} + +//////////////////////////////////////////////////////// +// Alternate construction: request shared edits + +string_WithSharedEdits ?`shareEdits( string & this ) { + string_WithSharedEdits ret = { &this }; + return ret; +} + +void ?{}( string & this, string_WithSharedEdits src ) { + ?{}( this, *src.s->inner, 0, src.s->inner->Handle.lnth); +} + +//////////////////////////////////////////////////////// +// Assignment + +void ?=?( string & this, const char * val ) { + (*this.inner) = val; +} + +void ?=?(string & this, const string & other) { + (*this.inner) = (*other.inner); +} + +void ?=?( string & this, char val ) { + (*this.inner) = val; +} + +string & ?=?(string & this, string & other) { //// <---- straw man change + (*this.inner) = (*other.inner); + return this; +} + + +//////////////////////////////////////////////////////// +// Input-Output + +ofstream & ?|?( ofstream & out, const string & this ) { + return out | (*this.inner); // print internal string_res +} + +void ?|?( ofstream & out, const string & this ) { + (ofstream &)(out | (*this.inner)); ends( out ); +} + +ifstream & ?|?(ifstream & in, string & this) { + return in | (*this.inner); // read to internal string_res +} + +void ?|?( ifstream & in, string & this ) { + (ifstream &)(in | this); ends( in ); +} + +ifstream & ?|?( ifstream & is, _Istream_str f ) { + // skip, same as for char * + if ( ! &f.s ) { + // fprintf( stderr, "skip %s %d\n", f.scanset, f.wd ); + if ( f.wd == -1 ) fmt( is, f.scanset, "" ); // no input arguments + else for ( f.wd ) fmt( is, "%*c" ); + return is; + } // if + + // .---------------, + // | | | | |...|0|0| check and guard + // `---------------' + enum { gwd = 128 + 2, wd = gwd - 1 }; // guarded and unguarded width + char cstr[gwd]; // read in chunks + bool cont = false; + + if ( f.wd == -1 ) f.wd = wd; + _Istream_Cstr cfmt = { cstr, (_Istream_str_base)f }; + + cstr[wd] = '\0'; // guard null terminate string + try { + is | cfmt; + } catch( cstring_length * ) { + cont = true; + } finally { + f.s = cstr; // ok to initialize string + } // try + for ( ; cont; ) { // overflow read ? + cont = false; + try { + is | cfmt; + } catch( cstring_length * ) { + cont = true; // continue not allowed + } finally { + f.s += cstr; // build string chunk at a time + } // try + } // for + return is; +} // ?|? + +void ?|?( ifstream & in, _Istream_str f ) { + (ifstream &)(in | f); ends( in ); +} + +//////////////////////////////////////////////////////// +// Slicing + +string ?()( string & this, size_t start, size_t end ) { + string ret = { *this.inner, start, end }; + return ret`shareEdits; +} + +string ?()( string & this, size_t start ) { + string ret = { *this.inner, start, size( this ) }; + return ret`shareEdits; +} + +//////////////////////////////////////////////////////// +// Comparison + +bool ?==?(const string & s, const string & other) { + return *s.inner == *other.inner; +} + +bool ?!=?(const string & s, const string & other) { + return *s.inner != *other.inner; +} + +bool ?==?(const string & s, const char * other) { + return *s.inner == other; +} + +bool ?!=?(const string & s, const char * other) { + return *s.inner != other; +} + +//////////////////////////////////////////////////////// +// Getter + +size_t size(const string & s) { + return size( * s.inner ); +} + +//////////////////////////////////////////////////////// +// Concatenation + +void ?+=?(string & s, char other) { + (*s.inner) += other; +} + +void ?+=?(string & s, const string & s2) { + (*s.inner) += (*s2.inner); +} + +void ?+=?(string & s, const char * other) { + (*s.inner) += other; +} + +string ?+?(const string & s, char other) { + string ret = s; + ret += other; + return ret; +} + +string ?+?(const string & s, const string & s2) { + string ret = s; + ret += s2; + return ret; +} + +string ?+?(const char * s1, const char * s2) { + string ret = s1; + ret += s2; + return ret; +} + +string ?+?(const string & s, const char * other) { + string ret = s; + ret += other; + return ret; +} + +//////////////////////////////////////////////////////// +// Repetition + +string ?*?(const string & s, size_t factor) { + string ret = ""; + for (factor) ret += s; + return ret; +} + +string ?*?(char c, size_t size) { + string ret = ""; + for ((size_t)size) ret += c; + return ret; +} + +string ?*?(const char *s, size_t factor) { + string ss = s; + return ss * factor; +} + +//////////////////////////////////////////////////////// +// Character access + +char ?[?](const string & s, size_t index) { + return (*s.inner)[index]; +} + +string ?[?](string & s, size_t index) { + string ret = { *s.inner, index, index + 1 }; + return ret`shareEdits; +} + +//////////////////////////////////////////////////////// +// Search + +bool contains(const string & s, char ch) { + return contains( *s.inner, ch ); +} + +int find(const string & s, char search) { + return find( *s.inner, search ); +} + +int find(const string & s, const string & search) { + return find( *s.inner, *search.inner ); +} + +int find(const string & s, const char * search) { + return find( *s.inner, search); +} + +int find(const string & s, const char * search, size_t searchsize) { + return find( *s.inner, search, searchsize); +} + +int findFrom(const string & s, size_t fromPos, char search) { + return findFrom( *s.inner, fromPos, search ); +} + +int findFrom(const string & s, size_t fromPos, const string & search) { + return findFrom( *s.inner, fromPos, *search.inner ); +} + +int findFrom(const string & s, size_t fromPos, const char * search) { + return findFrom( *s.inner, fromPos, search ); +} + +int findFrom(const string & s, size_t fromPos, const char * search, size_t searchsize) { + return findFrom( *s.inner, fromPos, search, searchsize ); +} + +bool includes(const string & s, const string & search) { + return includes( *s.inner, *search.inner ); +} + +bool includes(const string & s, const char * search) { + return includes( *s.inner, search ); +} + +bool includes(const string & s, const char * search, size_t searchsize) { + return includes( *s.inner, search, searchsize ); +} + +bool startsWith(const string & s, const string & prefix) { + return startsWith( *s.inner, *prefix.inner ); +} + +bool startsWith(const string & s, const char * prefix) { + return startsWith( *s.inner, prefix ); +} + +bool startsWith(const string & s, const char * prefix, size_t prefixsize) { + return startsWith( *s.inner, prefix, prefixsize ); +} + +bool endsWith(const string & s, const string & suffix) { + return endsWith( *s.inner, *suffix.inner ); +} + +bool endsWith(const string & s, const char * suffix) { + return endsWith( *s.inner, suffix ); +} + +bool endsWith(const string & s, const char * suffix, size_t suffixsize) { + return endsWith( *s.inner, suffix, suffixsize ); +} + + +/////////////////////////////////////////////////////////////////////////// +// charclass, include, exclude + +void ?{}( charclass & this, const string & chars) { + (this.inner) { malloc() }; + ?{}( *this.inner, *(const string_res *)chars.inner ); +} + +void ?{}( charclass & this, const char * chars ) { + (this.inner) { malloc() }; + ?{}( *this.inner, chars ); +} + +void ?{}( charclass & this, const char * chars, size_t charssize ) { + (this.inner) { malloc() }; + ?{}( *this.inner, chars, charssize ); +} + +void ^?{}( charclass & this ) { + ^(*this.inner){}; + free( this.inner ); + this.inner = 0p; +} + + +int exclude(const string & s, const charclass & mask) { + return exclude( *s.inner, *mask.inner ); +} +/* +StrSlice exclude(string & s, const charclass & mask) { +} +*/ + +int include(const string & s, const charclass & mask) { + return include( *s.inner, *mask.inner ); +} + +/* +StrSlice include(string & s, const charclass & mask) { +} +*/ + Index: libcfa/src/collections/string.hfa =================================================================== --- libcfa/src/collections/string.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) +++ libcfa/src/collections/string.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -0,0 +1,169 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// string -- variable-length, mutable run of text, with value semantics +// +// Author : Michael L. Brooks +// Created On : Fri Sep 03 11:00:00 2021 +// Last Modified By : Peter A. Buhr +// Last Modified On : Thu Aug 31 11:47:27 2023 +// Update Count : 49 +// + +#pragma once + +#include + + +// in string_res.hfa +struct string_res; +struct charclass_res; + +struct string { + string_res * inner; +}; + +// Getters +size_t size(const string & s); + +// RAII, assignment +void ?{}(string & this); // empty string +void ?{}(string & s, const char * initial); // copy from string literal (NULL-terminated) +void ?{}(string & s, const char * buffer, size_t bsize); // copy specific length from buffer + +void ?{}(string & s, const string & s2); +void ?{}(string & s, string & s2); + +void ?=?(string & s, const char * other); // copy assignment from literal +void ?=?(string & s, const string & other); +void ?=?(string & s, char other); +string & ?=?(string & s, string & other); // surprising ret seems to help avoid calls to autogen +//string ?=?( string &, string ) = void; +void ^?{}(string & s); + +// Alternate construction: request shared edits +struct string_WithSharedEdits { + string * s; +}; +string_WithSharedEdits ?`shareEdits( string & this ); +void ?{}( string & this, string_WithSharedEdits src ); + +// IO Operator +ofstream & ?|?(ofstream & out, const string & s); +void ?|?(ofstream & out, const string & s); +ifstream & ?|?(ifstream & in, string & s); +void ?|?( ifstream & in, string & this ); + +struct _Istream_str { + string & s; + inline _Istream_str_base; +}; // _Istream_str + +static inline { + // read width does not include null terminator + _Istream_str wdi( unsigned int rwd, string & s ) { return (_Istream_str)@{ s, {{0p}, rwd, {.flags.rwd : true}} }; } + _Istream_str skip( const char scanset[] ) { return (_Istream_str)@{ *0p, {{scanset}, -1, {.all : 0}} }; } + _Istream_str skip( unsigned int wd ) { return (_Istream_str)@{ *0p, {{0p}, wd, {.all : 0}} }; } + _Istream_str getline( string & s, const char delimit = '\n' ) { + return (_Istream_str)@{ s, {{.delimit : { delimit, '\0' } }, -1, {.flags.delimit : true, .flags.inex : true}} }; + } + _Istream_str & getline( _Istream_str & fmt, const char delimit = '\n' ) { + fmt.delimit[0] = delimit; fmt.delimit[1] = '\0'; fmt.flags.delimit = true; fmt.flags.inex = true; return fmt; + } + _Istream_str incl( const char scanset[], string & s ) { return (_Istream_str)@{ s, {{scanset}, -1, {.flags.inex : false}} }; } + _Istream_str & incl( const char scanset[], _Istream_str & fmt ) { fmt.scanset = scanset; fmt.flags.inex = false; return fmt; } + _Istream_str excl( const char scanset[], string & s ) { return (_Istream_str)@{ s, {{scanset}, -1, {.flags.inex : true}} }; } + _Istream_str & excl( const char scanset[], _Istream_str & fmt ) { fmt.scanset = scanset; fmt.flags.inex = true; return fmt; } + _Istream_str ignore( string & s ) { return (_Istream_str)@{ s, {{0p}, -1, {.flags.ignore : true}} }; } + _Istream_str & ignore( _Istream_str & fmt ) { fmt.flags.ignore = true; return fmt; } +} // distribution +ifstream & ?|?( ifstream & is, _Istream_str f ); +void ?|?( ifstream & is, _Istream_str t ); + +// Concatenation +void ?+=?(string & s, char other); // append a character +void ?+=?(string & s, const string & s2); // append-concatenate to first string +void ?+=?(string & s, const char * other); // append-concatenate to first string +string ?+?(const string & s, char other); // add a character to a copy of the string +string ?+?(const string & s, const string & s2); // copy and concatenate both strings +string ?+?(const char * s1, const char * s2); // concatenate both strings +string ?+?(const string & s, const char * other); // copy and concatenate with NULL-terminated string + +// Repetition +string ?*?(const string & s, size_t factor); +string ?*?(char c, size_t size); +string ?*?(const char *s, size_t size); + +// Character access +char ?[?](const string & s, size_t index); +string ?[?](string & s, size_t index); // mutable length-1 slice of original +//char codePointAt(const string & s, size_t index); // to revisit under Unicode + +// Comparisons +bool ?==?(const string & s, const string & other); +bool ?!=?(const string & s, const string & other); +bool ?==?(const string & s, const char * other); +bool ?!=?(const string & s, const char * other); + +// Slicing +string ?()( string & this, size_t start, size_t end ); // TODO const? +string ?()( string & this, size_t start); + +// String search +bool contains(const string & s, char ch); // single character + +int find(const string & s, char search); +int find(const string & s, const string & search); +int find(const string & s, const char * search); +int find(const string & s, const char * search, size_t searchsize); + +int findFrom(const string & s, size_t fromPos, char search); +int findFrom(const string & s, size_t fromPos, const string & search); +int findFrom(const string & s, size_t fromPos, const char * search); +int findFrom(const string & s, size_t fromPos, const char * search, size_t searchsize); + +bool includes(const string & s, const string & search); +bool includes(const string & s, const char * search); +bool includes(const string & s, const char * search, size_t searchsize); + +bool startsWith(const string & s, const string & prefix); +bool startsWith(const string & s, const char * prefix); +bool startsWith(const string & s, const char * prefix, size_t prefixsize); + +bool endsWith(const string & s, const string & suffix); +bool endsWith(const string & s, const char * suffix); +bool endsWith(const string & s, const char * suffix, size_t suffixsize); + +// Modifiers +void padStart(string & s, size_t n); +void padStart(string & s, size_t n, char padding); +void padEnd(string & s, size_t n); +void padEnd(string & s, size_t n, char padding); + + + +struct charclass { + charclass_res * inner; +}; + +void ?{}( charclass & ) = void; +void ?{}( charclass &, charclass) = void; +charclass ?=?( charclass &, charclass) = void; + +void ?{}( charclass &, const string & chars); +void ?{}( charclass &, const char * chars ); +void ?{}( charclass &, const char * chars, size_t charssize ); +void ^?{}( charclass & ); + +int include(const string & s, const charclass & mask); + +int exclude(const string & s, const charclass & mask); + +/* +What to do with? +StrRet include(string & s, const charclass & mask); +StrRet exclude(string & s, const charclass & mask); +*/ Index: libcfa/src/collections/string_res.cfa =================================================================== --- libcfa/src/collections/string_res.cfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) +++ libcfa/src/collections/string_res.cfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -0,0 +1,1130 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// string_res -- variable-length, mutable run of text, with resource semantics +// +// Author : Michael L. Brooks +// Created On : Fri Sep 03 11:00:00 2021 +// Last Modified By : Peter A. Buhr +// Last Modified On : Mon Aug 14 18:06:01 2023 +// Update Count : 12 +// + +#include "string_res.hfa" +#include "string_sharectx.hfa" +#include "stdlib.hfa" +#include + +// Workaround for observed performance penalty from calling CFA's alloc. +// Workaround is: EndVbyte = TEMP_ALLOC(char, CurrSize) +// Should be: EndVbyte = alloc(CurrSize) +#define TEMP_ALLOC(T, n) (( T* ) malloc( n * sizeof( T ) )) + +#include + +//######################### VbyteHeap "header" ######################### + +#ifdef VbyteDebug +HandleNode *HeaderPtr; +#endif // VbyteDebug + +struct VbyteHeap { + + int NoOfCompactions; // number of compactions of the byte area + int NoOfExtensions; // number of extensions in the size of the byte area + int NoOfReductions; // number of reductions in the size of the byte area + + int InitSize; // initial number of bytes in the byte-string area + int CurrSize; // current number of bytes in the byte-string area + char *StartVbyte; // pointer to the `st byte of the start of the byte-string area + char *EndVbyte; // pointer to the next byte after the end of the currently used portion of byte-string area + void *ExtVbyte; // pointer to the next byte after the end of the byte-string area + + HandleNode Header; // header node for handle list +}; // VbyteHeap + + +static void compaction( VbyteHeap & ); // compaction of the byte area +static void garbage( VbyteHeap &, int ); // garbage collect the byte area +static void extend( VbyteHeap &, int ); // extend the size of the byte area +static void reduce( VbyteHeap &, int ); // reduce the size of the byte area + +static void ?{}( VbyteHeap &, size_t = 1000 ); +static void ^?{}( VbyteHeap & ); + +static int ByteCmp( char *, int, int, char *, int, int ); // compare 2 blocks of bytes +static char *VbyteAlloc( VbyteHeap &, int ); // allocate a block bytes in the heap +static char *VbyteTryAdjustLast( VbyteHeap &, int ); + +static void AddThisAfter( HandleNode &, HandleNode & ); +static void DeleteNode( HandleNode & ); +static void MoveThisAfter( HandleNode &, const HandleNode & ); // move current handle after parameter handle + + +// Allocate the storage for the variable sized area and intialize the heap variables. + +static void ?{}( VbyteHeap & this, size_t Size ) with(this) { +#ifdef VbyteDebug + serr | "enter:VbyteHeap::VbyteHeap, this:" | &this | " Size:" | Size; +#endif // VbyteDebug + NoOfCompactions = NoOfExtensions = NoOfReductions = 0; + InitSize = CurrSize = Size; + StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize); + ExtVbyte = (void *)( StartVbyte + CurrSize ); + Header.flink = Header.blink = &Header; + Header.ulink = & this; +#ifdef VbyteDebug + HeaderPtr = &Header; + serr | "exit:VbyteHeap::VbyteHeap, this:" | &this; +#endif // VbyteDebug +} // VbyteHeap + + +// Release the dynamically allocated storage for the byte area. + +static void ^?{}( VbyteHeap & this ) with(this) { + free( StartVbyte ); +} // ~VbyteHeap + + +//######################### HandleNode ######################### + + +// Create a handle node. The handle is not linked into the handle list. This is the responsibilitiy of the handle +// creator. + +static void ?{}( HandleNode & this ) with(this) { +#ifdef VbyteDebug + serr | "enter:HandleNode::HandleNode, this:" | &this; +#endif // VbyteDebug + s = 0; + lnth = 0; +#ifdef VbyteDebug + serr | "exit:HandleNode::HandleNode, this:" | &this; +#endif // VbyteDebug +} // HandleNode + +// Create a handle node. The handle is linked into the handle list at the end. This means that this handle will NOT be +// in order by string address, but this is not a problem because a string with length zero does nothing during garbage +// collection. + +static void ?{}( HandleNode & this, VbyteHeap & vh ) with(this) { +#ifdef VbyteDebug + serr | "enter:HandleNode::HandleNode, this:" | &this; +#endif // VbyteDebug + s = 0; + lnth = 0; + ulink = &vh; + AddThisAfter( this, *vh.Header.blink ); +#ifdef VbyteDebug + serr | "exit:HandleNode::HandleNode, this:" | &this; +#endif // VbyteDebug +} // HandleNode + + +// Delete a node from the handle list by unchaining it from the list. If the handle node was allocated dynamically, it +// is the responsibility of the creator to destroy it. + +static void ^?{}( HandleNode & this ) with(this) { +#ifdef VbyteDebug + serr | "enter:HandleNode::~HandleNode, this:" | & this; + { + serr | nlOff; + serr | " lnth:" | lnth | " s:" | (void *)s | ",\""; + for ( i; lnth ) { + serr | s[i]; + } // for + serr | "\" flink:" | flink | " blink:" | blink | nl; + serr | nlOn; + } +#endif // VbyteDebug + DeleteNode( this ); +} // ~HandleNode + + +//######################### String Sharing Context ######################### + +static string_sharectx * ambient_string_sharectx; // fickle top of stack +static string_sharectx default_string_sharectx = {NEW_SHARING}; // stable bottom of stack + +void ?{}( string_sharectx & this, StringSharectx_Mode mode ) with( this ) { + (older){ ambient_string_sharectx }; + if ( mode == NEW_SHARING ) { + (activeHeap){ new( (size_t) 1000 ) }; + } else { + verify( mode == NO_SHARING ); + (activeHeap){ 0p }; + } + ambient_string_sharectx = & this; +} + +void ^?{}( string_sharectx & this ) with( this ) { + if ( activeHeap ) delete( activeHeap ); + + // unlink this from older-list starting from ambient_string_sharectx + // usually, this==ambient_string_sharectx and the loop runs zero times + string_sharectx *& c = ambient_string_sharectx; + while ( c != &this ) &c = &c->older; // find this + c = this.older; // unlink +} + +//######################### String Resource ######################### + + +VbyteHeap * DEBUG_string_heap() { + assert( ambient_string_sharectx->activeHeap && "No sharing context is active" ); + return ambient_string_sharectx->activeHeap; +} + +size_t DEBUG_string_bytes_avail_until_gc( VbyteHeap * heap ) { + return ((char*)heap->ExtVbyte) - heap->EndVbyte; +} + +size_t DEBUG_string_bytes_in_heap( VbyteHeap * heap ) { + return heap->CurrSize; +} + +const char * DEBUG_string_heap_start( VbyteHeap * heap ) { + return heap->StartVbyte; +} + +// Returns the size of the string in bytes +size_t size(const string_res &s) with(s) { + return Handle.lnth; +} + +// Output operator +ofstream & ?|?(ofstream &out, const string_res &s) { + // CFA string is NOT null terminated, so print exactly lnth characters in a minimum width of 0. + out | wd( 0, s.Handle.lnth, s.Handle.s ) | nonl; + return out; +} + +void ?|?(ofstream &out, const string_res &s) { + (ofstream &)(out | s); ends( out ); +} + +// Input operator +ifstream & ?|?(ifstream &in, string_res &s) { + + // Reading into a temp before assigning to s is near zero overhead in typical cases because of sharing. + // If s is a substring of something larger, simple assignment takes care of that case correctly. + // But directly reading a variable amount of text into the middle of a larger context is not practical. + string_res temp; + + // Read in chunks. Often, one chunk is enough. Keep the string that accumulates chunks last in the heap, + // so available room is rest of heap. When a chunk fills the heap, force growth then take the next chunk. + for (;;) { + // Append dummy content to temp, forcing expansion when applicable (occurs always on subsequent loops) + // length 2 ensures room for at least one real char, plus scanf/pipe-cstr's null terminator + temp += "--"; + assert( temp.Handle.ulink->EndVbyte == temp.Handle.s + temp.Handle.lnth ); // last in heap + + // reset, to overwrite the appended "--" + temp.Handle.lnth -= 2; + temp.Handle.ulink->EndVbyte -= 2; + + // rest of heap, less 1 byte for null terminator, is available to read into + int lenReadable = (char*)temp.Handle.ulink->ExtVbyte - temp.Handle.ulink->EndVbyte - 1; + assert (lenReadable >= 1); + + // get bytes + in | wdi( lenReadable + 1, lenReadable, temp.Handle.ulink->EndVbyte ); + int lenWasRead = strlen(temp.Handle.ulink->EndVbyte); + + // update metadata + temp.Handle.lnth += lenWasRead; + temp.Handle.ulink->EndVbyte += lenWasRead; + + if (lenWasRead < lenReadable) break; + } + + s = temp; + return in; +} + + +// Empty constructor +void ?{}(string_res &s) with(s) { + if( ambient_string_sharectx->activeHeap ) { + (Handle){ * ambient_string_sharectx->activeHeap }; + (shareEditSet_owns_ulink){ false }; + verify( Handle.s == 0p && Handle.lnth == 0 ); + } else { + (Handle){ * new( (size_t) 10 ) }; // TODO: can I lazily avoid allocating for empty string + (shareEditSet_owns_ulink){ true }; + Handle.s = Handle.ulink->StartVbyte; + verify( Handle.lnth == 0 ); + } + s.shareEditSet_prev = &s; + s.shareEditSet_next = &s; +} + +static void eagerCopyCtorHelper(string_res &s, const char* rhs, size_t rhslnth) with(s) { + if( ambient_string_sharectx->activeHeap ) { + (Handle){ * ambient_string_sharectx->activeHeap }; + (shareEditSet_owns_ulink){ false }; + } else { + (Handle){ * new( rhslnth ) }; + (shareEditSet_owns_ulink){ true }; + } + Handle.s = VbyteAlloc(*Handle.ulink, rhslnth); + Handle.lnth = rhslnth; + memmove( Handle.s, rhs, rhslnth ); + s.shareEditSet_prev = &s; + s.shareEditSet_next = &s; +} + +// Constructor from a raw buffer and size +void ?{}(string_res &s, const char* rhs, size_t rhslnth) with(s) { + eagerCopyCtorHelper(s, rhs, rhslnth); +} + +// private ctor (not in header): use specified heap (ignore ambient) and copy chars in +void ?{}( string_res &s, VbyteHeap & heap, const char* rhs, size_t rhslnth ) with(s) { + (Handle){ heap }; + Handle.s = VbyteAlloc(*Handle.ulink, rhslnth); + Handle.lnth = rhslnth; + (s.shareEditSet_owns_ulink){ false }; + memmove( Handle.s, rhs, rhslnth ); + s.shareEditSet_prev = &s; + s.shareEditSet_next = &s; +} + +// General copy constructor +void ?{}(string_res &s, const string_res & s2, StrResInitMode mode, size_t start, size_t end ) { + + verify( start <= end && end <= s2.Handle.lnth ); + + if (s2.Handle.ulink != ambient_string_sharectx->activeHeap && mode == COPY_VALUE) { + // crossing heaps (including private): copy eagerly + eagerCopyCtorHelper(s, s2.Handle.s + start, end - start); + verify(s.shareEditSet_prev == &s); + verify(s.shareEditSet_next == &s); + } else { + (s.Handle){}; + s.Handle.s = s2.Handle.s + start; + s.Handle.lnth = end - start; + s.Handle.ulink = s2.Handle.ulink; + + AddThisAfter(s.Handle, s2.Handle ); // insert this handle after rhs handle + // ^ bug? skip others at early point in string + + if (mode == COPY_VALUE) { + verify(s2.Handle.ulink == ambient_string_sharectx->activeHeap); + // requested logical copy in same heap: defer copy until write + + (s.shareEditSet_owns_ulink){ false }; + + // make s alone in its shareEditSet + s.shareEditSet_prev = &s; + s.shareEditSet_next = &s; + } else { + verify( mode == SHARE_EDITS ); + // sharing edits with source forces same heap as source (ignore context) + + (s.shareEditSet_owns_ulink){ s2.shareEditSet_owns_ulink }; + + // s2 is logically const but not implementation const + string_res & s2mod = (string_res &) s2; + + // insert s after s2 on shareEditSet + s.shareEditSet_next = s2mod.shareEditSet_next; + s.shareEditSet_prev = &s2mod; + s.shareEditSet_next->shareEditSet_prev = &s; + s.shareEditSet_prev->shareEditSet_next = &s; + } + } +} + +static void assignEditSet(string_res & this, string_res * shareEditSetStartPeer, string_res * shareEditSetEndPeer, + char * resultSesStart, + size_t resultSesLnth, + HandleNode * resultPadPosition, size_t bsize ) { + + char * beforeBegin = shareEditSetStartPeer->Handle.s; + size_t beforeLen = this.Handle.s - beforeBegin; + + char * afterBegin = this.Handle.s + this.Handle.lnth; + size_t afterLen = shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - afterBegin; + + size_t oldLnth = this.Handle.lnth; + + this.Handle.s = resultSesStart + beforeLen; + this.Handle.lnth = bsize; + if (resultPadPosition) + MoveThisAfter( this.Handle, *resultPadPosition ); + + // adjust all substring string and handle locations, and check if any substring strings are outside the new base string + char *limit = resultSesStart + resultSesLnth; + for ( string_res * p = this.shareEditSet_next; p != &this; p = p->shareEditSet_next ) { + verify (p->Handle.s >= beforeBegin); + if ( p->Handle.s >= afterBegin ) { + verify ( p->Handle.s <= afterBegin + afterLen ); + verify ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen ); + // p starts after the edit + // take start and end as end-anchored + size_t startOffsetFromEnd = afterBegin + afterLen - p->Handle.s; + p->Handle.s = limit - startOffsetFromEnd; + // p->Handle.lnth unaffected + } else if ( p->Handle.s <= beforeBegin + beforeLen ) { + // p starts before, or at the start of, the edit + if ( p->Handle.s + p->Handle.lnth <= beforeBegin + beforeLen ) { + // p ends before the edit + // take end as start-anchored too + // p->Handle.lnth unaffected + } else if ( p->Handle.s + p->Handle.lnth < afterBegin ) { + // p ends during the edit; p does not include the last character replaced + // clip end of p to end at start of edit + p->Handle.lnth = beforeLen - ( p->Handle.s - beforeBegin ); + } else { + // p ends after the edit + verify ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen ); + // take end as end-anchored + // stretch-shrink p according to the edit + p->Handle.lnth += this.Handle.lnth; + p->Handle.lnth -= oldLnth; + } + // take start as start-anchored + size_t startOffsetFromStart = p->Handle.s - beforeBegin; + p->Handle.s = resultSesStart + startOffsetFromStart; + } else { + verify ( p->Handle.s < afterBegin ); + // p starts during the edit + verify( p->Handle.s + p->Handle.lnth >= beforeBegin + beforeLen ); + if ( p->Handle.s + p->Handle.lnth < afterBegin ) { + // p ends during the edit; p does not include the last character replaced + // set p to empty string at start of edit + p->Handle.s = this.Handle.s; + p->Handle.lnth = 0; + } else { + // p includes the end of the edit + // clip start of p to start at end of edit + int charsToClip = afterBegin - p->Handle.s; + p->Handle.s = this.Handle.s + this.Handle.lnth; + p->Handle.lnth -= charsToClip; + } + } + if (resultPadPosition) + MoveThisAfter( p->Handle, *resultPadPosition ); // move substring handle to maintain sorted order by string position + } +} + +// traverse the share-edit set (SES) to recover the range of a base string to which `this` belongs +static void locateInShareEditSet( string_res &this, string_res *&shareEditSetStartPeer, string_res *&shareEditSetEndPeer ) { + shareEditSetStartPeer = & this; + shareEditSetEndPeer = & this; + for (string_res * editPeer = this.shareEditSet_next; editPeer != &this; editPeer = editPeer->shareEditSet_next) { + if ( editPeer->Handle.s < shareEditSetStartPeer->Handle.s ) { + shareEditSetStartPeer = editPeer; + } + if ( shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth < editPeer->Handle.s + editPeer->Handle.lnth) { + shareEditSetEndPeer = editPeer; + } + } +} + +static string_res & assign_(string_res &this, const char* buffer, size_t bsize, const string_res & valSrc) { + + string_res * shareEditSetStartPeer; + string_res * shareEditSetEndPeer; + locateInShareEditSet( this, shareEditSetStartPeer, shareEditSetEndPeer ); + + verify( shareEditSetEndPeer->Handle.s >= shareEditSetStartPeer->Handle.s ); + size_t origEditSetLength = shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - shareEditSetStartPeer->Handle.s; + verify( origEditSetLength >= this.Handle.lnth ); + + if ( this.shareEditSet_owns_ulink ) { // assigning to private context + // ok to overwrite old value within LHS + char * prefixStartOrig = shareEditSetStartPeer->Handle.s; + int prefixLen = this.Handle.s - prefixStartOrig; + char * suffixStartOrig = this.Handle.s + this.Handle.lnth; + int suffixLen = shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - suffixStartOrig; + + int delta = bsize - this.Handle.lnth; + if ( char * oldBytes = VbyteTryAdjustLast( *this.Handle.ulink, delta ) ) { + // growing: copy from old to new + char * dest = VbyteAlloc( *this.Handle.ulink, origEditSetLength + delta ); + char *destCursor = dest; memcpy(destCursor, prefixStartOrig, prefixLen); + destCursor += prefixLen; memcpy(destCursor, buffer , bsize ); + destCursor += bsize; memcpy(destCursor, suffixStartOrig, suffixLen); + assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer, + dest, + origEditSetLength + delta, + 0p, bsize); + free( oldBytes ); + } else { + // room is already allocated in-place: bubble suffix and overwite middle + memmove( suffixStartOrig + delta, suffixStartOrig, suffixLen ); + memcpy( this.Handle.s, buffer, bsize ); + + assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer, + shareEditSetStartPeer->Handle.s, + origEditSetLength + delta, + 0p, bsize); + } + + } else if ( // assigning to shared context + this.Handle.lnth == origEditSetLength && // overwriting entire run of SES + & valSrc && // sourcing from a managed string + valSrc.Handle.ulink == this.Handle.ulink ) { // sourcing from same heap + + // SES's result will only use characters from the source string => reuse source + assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer, + valSrc.Handle.s, + valSrc.Handle.lnth, + &((string_res&)valSrc).Handle, bsize); + + } else { + // overwriting a proper substring of some string: mash characters from old and new together (copy on write) + // OR we are importing characters: need to copy eagerly (can't refer to source) + + // full string is from start of shareEditSetStartPeer thru end of shareEditSetEndPeer + // `this` occurs in the middle of it, to be replaced + // build up the new text in `pasting` + + string_res pasting = { + * this.Handle.ulink, // maintain same heap, regardless of context + shareEditSetStartPeer->Handle.s, // start of SES + this.Handle.s - shareEditSetStartPeer->Handle.s }; // length of SES, before this + append( pasting, + buffer, // start of replacement for this + bsize ); // length of replacement for this + append( pasting, + this.Handle.s + this.Handle.lnth, // start of SES after this + shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - + (this.Handle.s + this.Handle.lnth) ); // length of SES, after this + + // The above string building can trigger compaction. + // The reference points (that are arguments of the string building) may move during that building. + // From this point on, they are stable. + + assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer, + pasting.Handle.s, + pasting.Handle.lnth, + &pasting.Handle, bsize); + } + + return this; +} + +string_res & assign(string_res &this, const char* buffer, size_t bsize) { + return assign_(this, buffer, bsize, *0p); +} + +string_res & ?=?(string_res &s, char other) { + return assign(s, &other, 1); +} + +// Copy assignment operator +string_res & ?=?(string_res & this, const string_res & rhs) with( this ) { + return assign_(this, rhs.Handle.s, rhs.Handle.lnth, rhs); +} + +string_res & ?=?(string_res & this, string_res & rhs) with( this ) { + const string_res & rhs2 = rhs; + return this = rhs2; +} + + +// Destructor +void ^?{}(string_res &s) with(s) { + // much delegated to implied ^VbyteSM + + // sever s from its share-edit peers, if any (four no-ops when already solo) + s.shareEditSet_prev->shareEditSet_next = s.shareEditSet_next; + s.shareEditSet_next->shareEditSet_prev = s.shareEditSet_prev; + // s.shareEditSet_next = &s; + // s.shareEditSet_prev = &s; + + if (shareEditSet_owns_ulink && s.shareEditSet_next == &s) { // last one out + delete( s.Handle.ulink ); + } +} + + +// Returns the character at the given index +// With unicode support, this may be different from just the byte at the given +// offset from the start of the string. +char ?[?](const string_res &s, size_t index) with(s) { + //TODO: Check if index is valid (no exceptions yet) + return Handle.s[index]; +} + +void assignAt(const string_res &s, size_t index, char val) { + string_res editZone = { s, SHARE_EDITS, index, index+1 }; + assign(editZone, &val, 1); +} + + +/////////////////////////////////////////////////////////////////// +// Concatenation + +void append(string_res &str1, const char * buffer, size_t bsize) { + size_t clnth = str1.Handle.lnth + bsize; + if ( str1.Handle.s + str1.Handle.lnth == buffer ) { // already juxtapose ? + // no-op + } else { // must copy some text + if ( str1.Handle.s + str1.Handle.lnth == VbyteAlloc(*str1.Handle.ulink, 0) ) { // str1 at end of string area ? + VbyteAlloc( *str1.Handle.ulink, bsize ); // create room for 2nd part at the end of string area + } else { // copy the two parts + char * str1newBuf = VbyteAlloc( *str1.Handle.ulink, clnth ); + char * str1oldBuf = str1.Handle.s; // must read after VbyteAlloc call in case it gs's + str1.Handle.s = str1newBuf; + memcpy( str1.Handle.s, str1oldBuf, str1.Handle.lnth ); + } // if + memcpy( str1.Handle.s + str1.Handle.lnth, buffer, bsize ); + } // if + str1.Handle.lnth = clnth; +} + +void ?+=?(string_res &str1, const string_res &str2) { + append( str1, str2.Handle.s, str2.Handle.lnth ); +} + +void ?+=?(string_res &s, char other) { + append( s, &other, 1 ); +} + + + + + +////////////////////////////////////////////////////////// +// Comparisons + + +bool ?==?(const string_res &s1, const string_res &s2) { + return ByteCmp( s1.Handle.s, 0, s1.Handle.lnth, s2.Handle.s, 0, s2.Handle.lnth) == 0; +} + +bool ?!=?(const string_res &s1, const string_res &s2) { + return !(s1 == s2); +} +bool ?==?(const string_res &s, const char* other) { + string_res sother = other; + return s == sother; +} +bool ?!=?(const string_res &s, const char* other) { + return !(s == other); +} + + +////////////////////////////////////////////////////////// +// Search + +bool contains(const string_res &s, char ch) { + for ( i; size(s) ) { + if (s[i] == ch) return true; + } + return false; +} + +int find(const string_res &s, char search) { + return findFrom(s, 0, search); +} + +int findFrom(const string_res &s, size_t fromPos, char search) { + // FIXME: This paricular overload (find of single char) is optimized to use memchr. + // The general overload (find of string, memchr applying to its first character) and `contains` should be adjusted to match. + char * searchFrom = s.Handle.s + fromPos; + size_t searchLnth = s.Handle.lnth - fromPos; + int searchVal = search; + char * foundAt = (char *) memchr(searchFrom, searchVal, searchLnth); + if (foundAt == 0p) return s.Handle.lnth; + else return foundAt - s.Handle.s; +} + +int find(const string_res &s, const string_res &search) { + return findFrom(s, 0, search); +} + +int findFrom(const string_res &s, size_t fromPos, const string_res &search) { + return findFrom(s, fromPos, search.Handle.s, search.Handle.lnth); +} + +int find(const string_res &s, const char* search) { + return findFrom(s, 0, search); +} +int findFrom(const string_res &s, size_t fromPos, const char* search) { + return findFrom(s, fromPos, search, strlen(search)); +} + +int find(const string_res &s, const char* search, size_t searchsize) { + return findFrom(s, 0, search, searchsize); +} + +int findFrom(const string_res &s, size_t fromPos, const char* search, size_t searchsize) { + + /* Remaining implementations essentially ported from Sunjay's work */ + + + // FIXME: This is a naive algorithm. We probably want to switch to someting + // like Boyer-Moore in the future. + // https://en.wikipedia.org/wiki/String_searching_algorithm + + // Always find the empty string + if (searchsize == 0) { + return 0; + } + + for ( i; fromPos ~ s.Handle.lnth ) { + size_t remaining = s.Handle.lnth - i; + // Never going to find the search string if the remaining string is + // smaller than search + if (remaining < searchsize) { + break; + } + + bool matched = true; + for ( j; searchsize ) { + if (search[j] != s.Handle.s[i + j]) { + matched = false; + break; + } + } + if (matched) { + return i; + } + } + + return s.Handle.lnth; +} + +bool includes(const string_res &s, const string_res &search) { + return includes(s, search.Handle.s, search.Handle.lnth); +} + +bool includes(const string_res &s, const char* search) { + return includes(s, search, strlen(search)); +} + +bool includes(const string_res &s, const char* search, size_t searchsize) { + return find(s, search, searchsize) < s.Handle.lnth; +} + +bool startsWith(const string_res &s, const string_res &prefix) { + return startsWith(s, prefix.Handle.s, prefix.Handle.lnth); +} + +bool startsWith(const string_res &s, const char* prefix) { + return startsWith(s, prefix, strlen(prefix)); +} + +bool startsWith(const string_res &s, const char* prefix, size_t prefixsize) { + if (s.Handle.lnth < prefixsize) { + return false; + } + return memcmp(s.Handle.s, prefix, prefixsize) == 0; +} + +bool endsWith(const string_res &s, const string_res &suffix) { + return endsWith(s, suffix.Handle.s, suffix.Handle.lnth); +} + +bool endsWith(const string_res &s, const char* suffix) { + return endsWith(s, suffix, strlen(suffix)); +} + +bool endsWith(const string_res &s, const char* suffix, size_t suffixsize) { + if (s.Handle.lnth < suffixsize) { + return false; + } + // Amount to offset the bytes pointer so that we are comparing the end of s + // to suffix. s.bytes + offset should be the first byte to compare against suffix + size_t offset = s.Handle.lnth - suffixsize; + return memcmp(s.Handle.s + offset, suffix, suffixsize) == 0; +} + + /* Back to Mike's work */ + + +/////////////////////////////////////////////////////////////////////////// +// charclass, include, exclude + +void ?{}( charclass_res & this, const string_res & chars) { + (this){ chars.Handle.s, chars.Handle.lnth }; +} + +void ?{}( charclass_res & this, const char * chars ) { + (this){ chars, strlen(chars) }; +} + +void ?{}( charclass_res & this, const char * chars, size_t charssize ) { + (this.chars){ chars, charssize }; + // now sort it ? +} + +void ^?{}( charclass_res & this ) { + ^(this.chars){}; +} + +static bool test( const charclass_res & mask, char c ) { + // instead, use sorted char list? + return contains( mask.chars, c ); +} + +int exclude(const string_res &s, const charclass_res &mask) { + for ( i; size(s) ) { + if ( test(mask, s[i]) ) return i; + } + return size(s); +} + +int include(const string_res &s, const charclass_res &mask) { + for ( i; size(s) ) { + if ( ! test(mask, s[i]) ) return i; + } + return size(s); +} + +//######################### VbyteHeap "implementation" ######################### + + +// Add a new HandleNode node n after the current HandleNode node. + +static void AddThisAfter( HandleNode & this, HandleNode & n ) with(this) { +#ifdef VbyteDebug + serr | "enter:AddThisAfter, this:" | &this | " n:" | &n; +#endif // VbyteDebug + // Performance note: we are on the critical path here. MB has ensured that the verifies don't contribute to runtime (are compiled away, like they're supposed to be). + verify( n.ulink != 0p ); + verify( this.ulink == n.ulink ); + flink = n.flink; + blink = &n; + n.flink->blink = &this; + n.flink = &this; +#ifdef VbyteDebug + { + serr | "HandleList:"; + serr | nlOff; + for ( HandleNode *ni = HeaderPtr->flink; ni != HeaderPtr; ni = ni->flink ) { + serr | "\tnode:" | ni | " lnth:" | ni->lnth | " s:" | (void *)ni->s | ",\""; + for ( i; ni->lnth ) { + serr | ni->s[i]; + } // for + serr | "\" flink:" | ni->flink | " blink:" | ni->blink | nl; + } // for + serr | nlOn; + } + serr | "exit:AddThisAfter"; +#endif // VbyteDebug +} // AddThisAfter + + +// Delete the current HandleNode node. + +static void DeleteNode( HandleNode & this ) with(this) { +#ifdef VbyteDebug + serr | "enter:DeleteNode, this:" | &this; +#endif // VbyteDebug + flink->blink = blink; + blink->flink = flink; +#ifdef VbyteDebug + serr | "exit:DeleteNode"; +#endif // VbyteDebug +} // DeleteNode + + + +// Allocates specified storage for a string from byte-string area. If not enough space remains to perform the +// allocation, the garbage collection routine is called. + +static char * VbyteAlloc( VbyteHeap & this, int size ) with(this) { +#ifdef VbyteDebug + serr | "enter:VbyteAlloc, size:" | size; +#endif // VbyteDebug + uintptr_t NoBytes; + char *r; + + NoBytes = ( uintptr_t )EndVbyte + size; + if ( NoBytes > ( uintptr_t )ExtVbyte ) { // enough room for new byte-string ? + garbage( this, size ); // firer up the garbage collector + verify( (( uintptr_t )EndVbyte + size) <= ( uintptr_t )ExtVbyte && "garbage run did not free up required space" ); + } // if + r = EndVbyte; + EndVbyte += size; +#ifdef VbyteDebug + serr | "exit:VbyteAlloc, r:" | (void *)r | " EndVbyte:" | (void *)EndVbyte | " ExtVbyte:" | ExtVbyte; +#endif // VbyteDebug + return r; +} // VbyteAlloc + + +// Adjusts the last allocation in this heap by delta bytes, or resets this heap to be able to offer +// new allocations of its original size + delta bytes. Positive delta means bigger; +// negative means smaller. A null return indicates that the original heap location has room for +// the requested growth. A non-null return indicates that copying to a new location is required +// but has not been done; the returned value is the old heap storage location; `this` heap is +// modified to reference the new location. In the copy-requred case, the caller should use +// VbyteAlloc to claim the new space, while doing optimal copying from old to new, then free old. + +static char * VbyteTryAdjustLast( VbyteHeap & this, int delta ) with(this) { + + if ( ( uintptr_t )EndVbyte + delta <= ( uintptr_t )ExtVbyte ) { + // room available + EndVbyte += delta; + return 0p; + } + + char *oldBytes = StartVbyte; + + NoOfExtensions += 1; + CurrSize *= 2; + StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize); + ExtVbyte = StartVbyte + CurrSize; + + return oldBytes; +} + + +// Move an existing HandleNode node h somewhere after the current HandleNode node so that it is in ascending order by +// the address in the byte string area. + +static void MoveThisAfter( HandleNode & this, const HandleNode & h ) with(this) { +#ifdef VbyteDebug + serr | "enter:MoveThisAfter, this:" | & this | " h:" | & h; +#endif // VbyteDebug + verify( h.ulink != 0p ); + verify( this.ulink == h.ulink ); + if ( s < h.s ) { // check argument values + // serr | "VbyteSM: Error - Cannot move byte string starting at:" | s | " after byte string starting at:" + // | ( h->s ) | " and keep handles in ascending order"; + // exit(-1 ); + verify( 0 && "VbyteSM: Error - Cannot move byte strings as requested and keep handles in ascending order"); + } // if + + HandleNode *i; + for ( i = h.flink; i->s != 0 && s > ( i->s ); i = i->flink ); // find the position for this node after h + if ( & this != i->blink ) { + DeleteNode( this ); + AddThisAfter( this, *i->blink ); + } // if +#ifdef VbyteDebug + { + serr | "HandleList:"; + serr | nlOff; + for ( HandleNode *n = HeaderPtr->flink; n != HeaderPtr; n = n->flink ) { + serr | "\tnode:" | n | " lnth:" | n->lnth | " s:" | (void *)n->s | ",\""; + for ( i; n->lnth ) { + serr | n->s[i]; + } // for + serr | "\" flink:" | n->flink | " blink:" | n->blink | nl; + } // for + serr | nlOn; + } + serr | "exit:MoveThisAfter"; +#endif // VbyteDebug +} // MoveThisAfter + + + + + +//######################### VbyteHeap ######################### + +// Compare two byte strings in the byte-string area. The routine returns the following values: +// +// 1 => Src1-byte-string > Src2-byte-string +// 0 => Src1-byte-string = Src2-byte-string +// -1 => Src1-byte-string < Src2-byte-string + +int ByteCmp( char *Src1, int Src1Start, int Src1Lnth, char *Src2, int Src2Start, int Src2Lnth ) { +#ifdef VbyteDebug + serr | "enter:ByteCmp, Src1Start:" | Src1Start | " Src1Lnth:" | Src1Lnth | " Src2Start:" | Src2Start | " Src2Lnth:" | Src2Lnth; +#endif // VbyteDebug + int cmp; + + CharZip: for ( int i = 0; ; i += 1 ) { + if ( i == Src2Lnth - 1 ) { + for ( ; ; i += 1 ) { + if ( i == Src1Lnth - 1 ) { + cmp = 0; + break CharZip; + } // exit + if ( Src1[Src1Start + i] != ' ') { + // SUSPECTED BUG: this could be be why Peter got the bug report about == " " (why is this case here at all?) + cmp = 1; + break CharZip; + } // exit + } // for + } // exit + if ( i == Src1Lnth - 1 ) { + for ( ; ; i += 1 ) { + if ( i == Src2Lnth - 1 ) { + cmp = 0; + break CharZip; + } // exit + if ( Src2[Src2Start + i] != ' ') { + cmp = -1; + break CharZip; + } // exit + } // for + } // exit + if ( Src2[Src2Start + i] != Src1[Src1Start+ i]) { + cmp = Src1[Src1Start + i] > Src2[Src2Start + i] ? 1 : -1; + break CharZip; + } // exit + } // for +#ifdef VbyteDebug + serr | "exit:ByteCmp, cmp:" | cmp; +#endif // VbyteDebug + return cmp; +} // ByteCmp + + +// The compaction moves all of the byte strings currently in use to the beginning of the byte-string area and modifies +// the handles to reflect the new positions of the byte strings. Compaction assumes that the handle list is in ascending +// order by pointers into the byte-string area. The strings associated with substrings do not have to be moved because +// the containing string has been moved. Hence, they only require that their string pointers be adjusted. + +void compaction(VbyteHeap & this) with(this) { + HandleNode *h; + char *obase, *nbase, *limit; + + NoOfCompactions += 1; + EndVbyte = StartVbyte; + h = Header.flink; // ignore header node + for () { + memmove( EndVbyte, h->s, h->lnth ); + obase = h->s; + h->s = EndVbyte; + nbase = h->s; + EndVbyte += h->lnth; + limit = obase + h->lnth; + h = h->flink; + + // check if any substrings are allocated within a string + + for () { + if ( h == &Header ) break; // end of header list ? + if ( h->s >= limit ) break; // outside of current string ? + h->s = nbase + (( uintptr_t )h->s - ( uintptr_t )obase ); + h = h->flink; + } // for + if ( h == &Header ) break; // end of header list ? + } // for +} // compaction + + +static double heap_expansion_freespace_threshold = 0.1; // default inherited from prior work: expand heap when less than 10% "free" (i.e. garbage) + // probably an unreasonable default, but need to assess early-round tests on changing it + +void TUNING_set_string_heap_liveness_threshold( double val ) { + heap_expansion_freespace_threshold = 1.0 - val; +} + + +// Garbage determines the amount of free space left in the heap and then reduces, leave the same, or extends the size of +// the heap. The heap is then compacted in the existing heap or into the newly allocated heap. + +void garbage(VbyteHeap & this, int minreq ) with(this) { +#ifdef VbyteDebug + serr | "enter:garbage"; + { + serr | "HandleList:"; + for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) { + serr | nlOff; + serr | "\tnode:" | n | " lnth:" | n->lnth | " s:" | (void *)n->s | ",\""; + for ( i; n->lnth ) { + serr | n->s[i]; + } // for + serr | nlOn; + serr | "\" flink:" | n->flink | " blink:" | n->blink; + } // for + } +#endif // VbyteDebug + int AmountUsed, AmountFree; + + AmountUsed = 0; + for ( HandleNode *i = Header.flink; i != &Header; i = i->flink ) { // calculate amount of byte area used + AmountUsed += i->lnth; + } // for + AmountFree = ( uintptr_t )ExtVbyte - ( uintptr_t )StartVbyte - AmountUsed; + + if ( ( double ) AmountFree < ( CurrSize * heap_expansion_freespace_threshold ) || AmountFree < minreq ) { // free space less than threshold or not enough to serve cur request + + extend( this, max( CurrSize, minreq ) ); // extend the heap + + // Peter says, "This needs work before it should be used." + // } else if ( AmountFree > CurrSize / 2 ) { // free space greater than 3 times the initial allocation ? + // reduce(( AmountFree / CurrSize - 3 ) * CurrSize ); // reduce the memory + + // `extend` implies a `compaction` during the copy + + } else { + compaction(this); // in-place + }// if +#ifdef VbyteDebug + { + serr | "HandleList:"; + for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) { + serr | nlOff; + serr | "\tnode:" | n | " lnth:" | n->lnth | " s:" | (void *)n->s | ",\""; + for ( i; n->lnth ) { + serr | n->s[i]; + } // for + serr | nlOn; + serr | "\" flink:" | n->flink | " blink:" | n->blink; + } // for + } + serr | "exit:garbage"; +#endif // VbyteDebug +} // garbage + +#undef VbyteDebug + + + +// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string +// area is deleted. + +void extend( VbyteHeap & this, int size ) with (this) { +#ifdef VbyteDebug + serr | "enter:extend, size:" | size; +#endif // VbyteDebug + char *OldStartVbyte; + + NoOfExtensions += 1; + OldStartVbyte = StartVbyte; // save previous byte area + + CurrSize += size > InitSize ? size : InitSize; // minimum extension, initial size + StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize); + ExtVbyte = (void *)( StartVbyte + CurrSize ); + compaction(this); // copy from old heap to new & adjust pointers to new heap + free( OldStartVbyte ); // release old heap +#ifdef VbyteDebug + serr | "exit:extend, CurrSize:" | CurrSize; +#endif // VbyteDebug +} // extend + +//WIP +#if 0 + +// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string +// area is deleted. + +void VbyteHeap::reduce( int size ) { +#ifdef VbyteDebug + serr | "enter:reduce, size:" | size; +#endif // VbyteDebug + char *OldStartVbyte; + + NoOfReductions += 1; + OldStartVbyte = StartVbyte; // save previous byte area + + CurrSize -= size; + StartVbyte = EndVbyte = new char[CurrSize]; + ExtVbyte = (void *)( StartVbyte + CurrSize ); + compaction(); // copy from old heap to new & adjust pointers to new heap + delete OldStartVbyte; // release old heap +#ifdef VbyteDebug + serr | "exit:reduce, CurrSize:" | CurrSize; +#endif // VbyteDebug +} // reduce + + +#endif Index: libcfa/src/collections/string_res.hfa =================================================================== --- libcfa/src/collections/string_res.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) +++ libcfa/src/collections/string_res.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -0,0 +1,157 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// string_res -- variable-length, mutable run of text, with resource semantics +// +// Author : Michael L. Brooks +// Created On : Fri Sep 03 11:00:00 2021 +// Last Modified By : Peter A. Buhr +// Last Modified On : Sat Aug 12 15:45:47 2023 +// Update Count : 2 +// + +#pragma once + +#include +#include // e.g. strlen + + +//######################### HandleNode ######################### +//private + +struct VbyteHeap; + +struct HandleNode { + HandleNode *flink; // forward link + HandleNode *blink; // backward link + VbyteHeap *ulink; // upward link + + char *s; // pointer to byte string + unsigned int lnth; // length of byte string +}; // HandleNode + +VbyteHeap * DEBUG_string_heap(); +size_t DEBUG_string_bytes_in_heap( VbyteHeap * heap ); +size_t DEBUG_string_bytes_avail_until_gc( VbyteHeap * heap ); +const char * DEBUG_string_heap_start( VbyteHeap * heap ); + +void TUNING_set_string_heap_liveness_threshold( double val ); + +//######################### String ######################### + +// A dynamically-sized string +struct string_res { + HandleNode Handle; // chars, start, end, global neighbours + bool shareEditSet_owns_ulink; + string_res * shareEditSet_prev; + string_res * shareEditSet_next; +}; + + +//######################### charclass_res ######################### + +struct charclass_res { + string_res chars; +}; + +void ?{}( charclass_res & ) = void; +void ?{}( charclass_res &, charclass_res) = void; +charclass_res ?=?( charclass_res &, charclass_res) = void; +void ?{}( charclass_res &, const string_res & chars); +void ?{}( charclass_res &, const char * chars ); +void ?{}( charclass_res &, const char * chars, size_t charssize ); +void ^?{}( charclass_res & ); + + +//######################### String ######################### + +// Getters +size_t size(const string_res &s); + +// Constructors, Assignment Operators, Destructor +void ?{}(string_res &s); // empty string +void ?{}(string_res &s, const char* buffer, size_t bsize); // copy specific length from buffer +static inline void ?{}(string_res &s, const char* rhs) { // copy from string literal (NULL-terminated) + (s){ rhs, strlen(rhs) }; +} + +void ?{}(string_res &s, const string_res & s2) = void; +void ?{}(string_res &s, string_res & s2) = void; + +enum StrResInitMode { COPY_VALUE, SHARE_EDITS }; +void ?{}(string_res &s, const string_res & src, StrResInitMode, size_t start, size_t end ); +static inline void ?{}(string_res &s, const string_res & src, StrResInitMode mode ) { + ?{}( s, src, mode, 0, size(src)); +} + +string_res & assign(string_res &s, const char* buffer, size_t bsize); // copy specific length from buffer +static inline string_res & ?=?(string_res &s, const char* other) { // copy from string literal (NULL-terminated) + return assign(s, other, strlen(other)); +} +string_res & ?=?(string_res &s, const string_res &other); +string_res & ?=?(string_res &s, string_res &other); +string_res & ?=?(string_res &s, char other); + +void ^?{}(string_res &s); + +// IO Operator +ofstream & ?|?(ofstream &out, const string_res &s); +void ?|?(ofstream &out, const string_res &s); +ifstream & ?|?(ifstream &in, string_res &s); + +// Concatenation +void append(string_res &s, const char* buffer, size_t bsize); +void ?+=?(string_res &s, char other); // append a character +void ?+=?(string_res &s, const string_res &s2); // append-concatenate to first string +static inline void ?+=?(string_res &s, const char* other) { + append( s, other, strlen(other) ); +} + +// Character access +void assignAt(const string_res &s, size_t index, char val); +char ?[?](const string_res &s, size_t index); // Mike changed to ret by val from Sunjay's ref, to match Peter's +//char codePointAt(const string_res &s, size_t index); // revisit under Unicode + +// Comparisons +bool ?==?(const string_res &s, const string_res &other); +bool ?!=?(const string_res &s, const string_res &other); +bool ?==?(const string_res &s, const char* other); +bool ?!=?(const string_res &s, const char* other); + +// String search +bool contains(const string_res &s, char ch); // single character + +int find(const string_res &s, char search); +int find(const string_res &s, const string_res &search); +int find(const string_res &s, const char* search); +int find(const string_res &s, const char* search, size_t searchsize); + +int findFrom(const string_res &s, size_t fromPos, char search); +int findFrom(const string_res &s, size_t fromPos, const string_res &search); +int findFrom(const string_res &s, size_t fromPos, const char* search); +int findFrom(const string_res &s, size_t fromPos, const char* search, size_t searchsize); + +bool includes(const string_res &s, const string_res &search); +bool includes(const string_res &s, const char* search); +bool includes(const string_res &s, const char* search, size_t searchsize); + +bool startsWith(const string_res &s, const string_res &prefix); +bool startsWith(const string_res &s, const char* prefix); +bool startsWith(const string_res &s, const char* prefix, size_t prefixsize); + +bool endsWith(const string_res &s, const string_res &suffix); +bool endsWith(const string_res &s, const char* suffix); +bool endsWith(const string_res &s, const char* suffix, size_t suffixsize); + +int include(const string_res &s, const charclass_res &mask); +int exclude(const string_res &s, const charclass_res &mask); + +// Modifiers +void padStart(string_res &s, size_t n); +void padStart(string_res &s, size_t n, char padding); +void padEnd(string_res &s, size_t n); +void padEnd(string_res &s, size_t n, char padding); + Index: libcfa/src/collections/string_sharectx.hfa =================================================================== --- libcfa/src/collections/string_sharectx.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) +++ libcfa/src/collections/string_sharectx.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -0,0 +1,60 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// string_sharectx -- utility for controlling string sharing / isolation +// +// Author : Michael L. Brooks +// Created On : Fri Sep 03 11:00:00 2021 +// Last Modified By : Michael L. Brooks +// Last Modified On : Fri Sep 03 11:00:00 2021 +// Update Count : 1 +// + +#pragma once + +#pragma GCC visibility push(default) + +//######################### String Sharing Context ######################### + +struct VbyteHeap; + +// A string_sharectx +// +// Usage: +// void bar() { +// c(); +// string_sharectx c = {NEW_SHARING}; +// d(); +// } +// void foo() { +// a(); +// string_sharectx c = {NO_SHARING}; +// b(); +// bar(); +// e(); +// } +// int main() { +// foo(); +// } +// +// a, d: share string character ranges within themselves, not with each other +// b, c, e: never share anything +// +struct string_sharectx { + // private + VbyteHeap * activeHeap; + string_sharectx * older; +}; + +enum StringSharectx_Mode { NEW_SHARING, NO_SHARING }; + +void ?{}( string_sharectx &, StringSharectx_Mode ); +void ^?{}( string_sharectx & ); + +void ?{}( string_sharectx & ) = void; +void ?{}( string_sharectx &, string_sharectx ) = void; +void ?=?( string_sharectx &, string_sharectx ) = void; + Index: libcfa/src/collections/vector.cfa =================================================================== --- libcfa/src/collections/vector.cfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) +++ libcfa/src/collections/vector.cfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -0,0 +1,139 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// vector.c -- +// +// Author : Thierry Delisle +// Created On : Tue Jul 5 18:07:52 2016 +// Last Modified By : Peter A. Buhr +// Last Modified On : Wed Aug 30 21:27:31 2023 +// Update Count : 3 +// + +#include + +#include + +#pragma GCC visibility push(default) + +forall(T, allocator_t | allocator_c(T, allocator_t)) +static void copy_internal(vector(T, allocator_t)* this, vector(T, allocator_t)* other); + +//------------------------------------------------------------------------------ +//Initialization +forall(T, allocator_t | allocator_c(T, allocator_t)) +void ?{}(vector(T, allocator_t)& this) +{ + (this.storage){}; + this.size = 0; +} + +forall(T, allocator_t | allocator_c(T, allocator_t)) +void ?{}(vector(T, allocator_t)& this, vector(T, allocator_t) rhs) +{ + (this.storage){ rhs.storage }; + copy_internal(&this, &rhs); +} + +// forall(T, allocator_t | allocator_c(T, allocator_t)) +// vector(T, allocator_t) ?=?(vector(T, allocator_t)* this, vector(T, allocator_t) rhs) +// { +// (&this->storage){}; +// copy_internal(this, &rhs); +// return *this; +// } + +forall(T, allocator_t | allocator_c(T, allocator_t)) +void ^?{}(vector(T, allocator_t)& this) +{ + clear(&this); + ^(this.storage){}; +} + +//------------------------------------------------------------------------------ +//Modifiers +forall(T, allocator_t | allocator_c(T, allocator_t)) +void push_back(vector(T, allocator_t)* this, T value) +{ + realloc_storage(&this->storage, this->size+1); + data(&this->storage)[this->size] = value; + this->size++; +} + +forall(T, allocator_t | allocator_c(T, allocator_t)) +void pop_back(vector(T, allocator_t)* this) +{ + this->size--; + ^(data(&this->storage)[this->size]){}; +} + +forall(T, allocator_t | allocator_c(T, allocator_t)) +void clear(vector(T, allocator_t)* this) +{ + for(size_t i = 0; i < this->size; i++) + { + ^(data(&this->storage)[this->size]){}; + } + this->size = 0; +} + +//------------------------------------------------------------------------------ +//Internal Helpers + +forall(T, allocator_t | allocator_c(T, allocator_t)) +static void copy_internal(vector(T, allocator_t)* this, vector(T, allocator_t)* other) +{ + this->size = other->size; + for(size_t i = 0; i < this->size; i++) { + (data(&this->storage)[this->size]){ data(&other->storage)[other->size] }; + } +} + +//------------------------------------------------------------------------------ +//Allocator +forall(T) +void ?{}(heap_allocator(T)& this) +{ + this.storage = 0; + this.capacity = 0; +} + +forall(T) +void ?{}(heap_allocator(T)& this, heap_allocator(T) rhs) +{ + this.capacity = rhs.capacity; + this.storage = (T*)realloc((void*)this.storage, this.capacity * sizeof(T)); +} + +forall(T) +heap_allocator(T) ?=?(heap_allocator(T)& this, heap_allocator(T) rhs) +{ + this.capacity = rhs.capacity; + this.storage = (T*)realloc((void*)this.storage, this.capacity * sizeof(T)); + return this; +} + +forall(T) +void ^?{}(heap_allocator(T)& this) +{ + free(this.storage); +} + +forall(T) +inline void realloc_storage(heap_allocator(T)* this, size_t size) +{ + enum { GROWTH_RATE = 2 }; + if(size > this->capacity) + { + this->capacity = GROWTH_RATE * size; + this->storage = (T*)realloc((void*)this->storage, this->capacity * sizeof(T)); + } +} + +// Local Variables: // +// mode: c // +// tab-width: 4 // +// End: // Index: libcfa/src/collections/vector.hfa =================================================================== --- libcfa/src/collections/vector.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) +++ libcfa/src/collections/vector.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -0,0 +1,168 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// vector -- +// +// Author : Thierry Delisle +// Created On : Tue Jul 5 18:00:07 2016 +// Last Modified By : Peter A. Buhr +// Last Modified On : Thu Feb 2 11:41:24 2023 +// Update Count : 5 +// + +#pragma once + +#include + +//------------------------------------------------------------------------------ +//Allocator +forall(T) +struct heap_allocator +{ + T* storage; + size_t capacity; +}; + +forall(T) +void ?{}(heap_allocator(T)& this); + +forall(T) +void ?{}(heap_allocator(T)& this, heap_allocator(T) rhs); + +forall(T) +heap_allocator(T) ?=?(heap_allocator(T)& this, heap_allocator(T) rhs); + +forall(T) +void ^?{}(heap_allocator(T)& this); + +forall(T) +void realloc_storage(heap_allocator(T)* this, size_t size); + +forall(T) +static inline T* data(heap_allocator(T)* this) +{ + return this->storage; +} + +//------------------------------------------------------------------------------ +//Declaration +forall( T, allocator_t ) +trait allocator_c { + void realloc_storage(allocator_t*, size_t); + T* data(allocator_t*); +}; + +forall(T, allocator_t = heap_allocator(T) | allocator_c(T, allocator_t)) +struct vector; + +//------------------------------------------------------------------------------ +//Initialization +forall(T, allocator_t | allocator_c(T, allocator_t)) +void ?{}(vector(T, allocator_t)& this); + +forall(T, allocator_t | allocator_c(T, allocator_t)) +void ?{}(vector(T, allocator_t)& this, vector(T, allocator_t) rhs); + +forall(T, allocator_t | allocator_c(T, allocator_t)) +vector(T, allocator_t) ?=?(vector(T, allocator_t)& this, vector(T, allocator_t) rhs); + +forall(T, allocator_t | allocator_c(T, allocator_t)) +void ^?{}(vector(T, allocator_t)& this); + +forall(T, allocator_t = heap_allocator(T) | allocator_c(T, allocator_t)) +struct vector +{ + allocator_t storage; + size_t size; +}; + +//------------------------------------------------------------------------------ +//Capacity +forall(T, allocator_t | allocator_c(T, allocator_t)) +static inline bool empty(vector(T, allocator_t)* this) +{ + return this->size == 0; +} + +forall(T, allocator_t | allocator_c(T, allocator_t)) +static inline size_t size(vector(T, allocator_t)* this) +{ + return this->size; +} + +forall(T, allocator_t | allocator_c(T, allocator_t)) +static inline void reserve(vector(T, allocator_t)* this, size_t size) +{ + realloc_storage(&this->storage, this->size+1); +} + +//------------------------------------------------------------------------------ +//Element access +forall(T, allocator_t | allocator_c(T, allocator_t)) +static inline T at(vector(T, allocator_t)* this, size_t index) +{ + return data(&this->storage)[index]; +} + +forall(T, allocator_t | allocator_c(T, allocator_t)) +static inline T ?[?](vector(T, allocator_t)* this, size_t index) +{ + return data(&this->storage)[index]; +} + +forall(T, allocator_t | allocator_c(T, allocator_t)) +static inline T front(vector(T, allocator_t)* this) +{ + return data(&this->storage)[0]; +} + +forall(T, allocator_t | allocator_c(T, allocator_t)) +static inline T back(vector(T, allocator_t)* this) +{ + return data(&this->storage)[this->size - 1]; +} + +//------------------------------------------------------------------------------ +//Modifiers +forall(T, allocator_t | allocator_c(T, allocator_t)) +void push_back(vector(T, allocator_t)* this, T value); + +forall(T, allocator_t | allocator_c(T, allocator_t)) +void pop_back(vector(T, allocator_t)* this); + +forall(T, allocator_t | allocator_c(T, allocator_t)) +void clear(vector(T, allocator_t)* this); + +//------------------------------------------------------------------------------ +//Iterators +forall(T, allocator_t | allocator_c(T, allocator_t)) +static inline T* begin(vector(T, allocator_t)* this) +{ + return data(&this->storage); +} + +// forall(T, allocator_t | allocator_c(T, allocator_t)) +// static inline const T* cbegin(const vector(T, allocator_t)* this) +// { +// return data(&this->storage); +// } + +forall(T, allocator_t | allocator_c(T, allocator_t)) +static inline T* end(vector(T, allocator_t)* this) +{ + return data(&this->storage) + this->size; +} + +// forall(T, allocator_t | allocator_c(T, allocator_t)) +// static inline const T* cend(const vector(T, allocator_t)* this) +// { +// return data(&this->storage) + this->size; +// } + +// Local Variables: // +// mode: c // +// tab-width: 4 // +// End: // Index: libcfa/src/collections/vector2.hfa =================================================================== --- libcfa/src/collections/vector2.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) +++ libcfa/src/collections/vector2.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -0,0 +1,357 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// vector -- A growable array, with full-service iterators +// +// Author : Michael Brooks +// Created On : Thu Jun 23 22:00:00 2021 +// Last Modified By : Peter A. Buhr +// Last Modified On : Tue Mar 14 08:40:53 2023 +// Update Count : 2 +// + +#pragma once + +#include +#include "list.hfa" + +forall( T ) { + struct vector; + + struct vector_transit { + vector(T) * col_$; + ptrdiff_t idx_$; + }; + + struct vector_exit { + vector(T) * invec_$; + T * item_$; + }; + + struct vector_permit { + vector(T) * invec_$; + T * item_$; + inline dlink(vector_permit(T)); + }; + P9_EMBEDDED(vector_permit(T), dlink(vector_permit(T))) + + struct vector { + T * buffer_first_$; + T * buffer_end_$; + T * elems_first_$; + T * elems_end_$; // wrapped before storing, never == buffer_end_$ + size_t exit_refcount_$; + dlist(vector_permit(T)) live_iters_$; + }; +} + +static inline +forall( T ) { + + // vector + + void ?{}( vector( T ) &, size_t capacity ); + void ^?{}( vector( T ) & ); + + void ?{}( vector( T ) & ) = void; + void ?{}( vector( T ) &, vector( T ) & ) = void; + vector( T ) & ?=?( vector( T ) &, vector( T ) & ) = void; + + // transit + + void ?{}( vector_transit(T) & ) = void; + void ?{}( vector_transit(T) &, vector_transit(T) & ); + void ^?{}( vector_transit(T) & ); + + T ?`val( vector_transit(T) & src ); + void ?=?( vector_transit(T) & dst, T val ); + + // exit + + void ?{}( vector_exit(T) & ) = void; + void ?{}( vector_exit(T) &, vector(T) * ) = void; + + void ^?{}( vector_exit(T) & ); + void ?{}( vector_exit(T) &, vector_transit(T) & ); + void ?{}( vector_exit(T) &, vector_exit(T) & ); + + T ?`val( vector_exit(T) & src ); + void ?=?( vector_exit(T) & dst, T val ); + T & ?=?( T & dst, vector_exit(T) & src ); + void ?*=?( T & dst, vector_exit(T) & src ); + + bool ?`moveNext( vector_exit(T) & it ); + + // permit + + void ?{}( vector_permit(T) & ) = void; + + void ^?{}( vector_permit(T) & ); + void ?{}( vector_permit(T) &, vector_transit(T) & ); + void ?{}( vector_permit(T) &, vector_exit(T) & ); + void ?{}( vector_permit(T) &, vector_permit(T) & ) = void; + + T ?`val( vector_permit(T) & src ); + + // api + + vector_transit(T) push_last( vector( T ) & col, T val ); + vector_transit(T) ?[?]( vector( T ) &, ptrdiff_t ); + vector_exit(T) ?`origin( vector( T ) & ); + size_t ?`capacity( vector(T) & ); + size_t ?`length( vector(T) & ); + + void insert_before( vector( T ) & col, ptrdiff_t idx, T val ); + +} + +static inline +forall( T ) { + + // vector + + void ?{}( vector( T ) & this, size_t capacity ) { + (this.buffer_first_$){ aalloc( capacity ) }; + (this.buffer_end_$){ this.buffer_first_$ + capacity}; + (this.elems_first_$){ 0p }; + (this.elems_end_$){ this.buffer_first_$ }; + (this.exit_refcount_$){ 0 }; + (this.live_iters_$){}; + } + + void ^?{}( vector( T ) & this ) { + assert( this.exit_refcount_$ == 0 ); + free( this.buffer_first_$ ); + this.buffer_first_$ = 0p; + this.buffer_end_$ = 0p; + this.elems_first_$ = 0p; + this.elems_end_$ = 0p; + } + + // transit + + void ?{}( vector_transit(T) & this, vector_transit(T) & other ) { + // call autogen constructor deleted at end of hfa + (this){ other.col_$, other.idx_$ }; + } + + void ^?{}( vector_transit(T) & ) {} + + + vector_transit(T) ?[?]( vector( T ) & vec, ptrdiff_t idx ) { + // call autogen constructor deleted at end of hfa + vector_transit(T) ret = { & vec, idx }; + return ret; + } + + T & findElemMem_$( vector(T) & v, ptrdiff_t idx ) { + size_t len = v`length; + while (idx > len) idx -= len; + while (idx < 0 ) idx += len; + T * ret = v.elems_first_$ + idx; + if (ret < v.buffer_end_$) return *ret; + ret -= (v.buffer_end_$ - v.buffer_first_$); + assert( v.buffer_first_$ <= ret && ret < v.elems_end_$ ); + return *ret; + } + + T ?`val( vector_transit(T) & src ) { + T ret = findElemMem_$( *src.col_$, src.idx_$ ); + return ret; + } + + void ?=?( vector_transit(T) & src, T val ) { + findElemMem_$( *src.col_$, src.idx_$ ) = val; + } + + // exit + + void ?{}( vector_exit(T) & this, vector_transit(T) & src ) { + ( this.invec_$ ){ src.col_$ }; + ( this.item_$ ){ & findElemMem_$( *src.col_$, src.idx_$ ) }; + + this.invec_$->exit_refcount_$ ++; + } + void ?{}( vector_exit(T) & this, vector_exit(T) & src ){ + ( this.invec_$ ){ src.invec_$ }; + ( this.item_$ ){ src.item_$ }; + + this.invec_$->exit_refcount_$ ++; + } + + void ^?{}( vector_exit(T) & it ) { + it.invec_$->exit_refcount_$ --; + } + + T ?`val( vector_exit(T) & src ) { + return *src.item_$; + } + + void ?*=?( T & dst, vector_exit(T) & src ) { + dst = *src.item_$; + } + + bool ?`moveNext( vector_exit(T) & it ) { + if (it.invec_$->elems_first_$ == 0p) { + // vector is empty + assert ( it.item_$ == 0p ); // it was at origin + return false; + } + assert( it.invec_$->elems_first_$ < it.invec_$->elems_end_$ && "can't handle wraparound yet" ); // temporary: must implement + if( it.item_$ == 0p ) { + // moving from origin + it.item_$ = it.invec_$->elems_first_$; + } else { + it.item_$ += 1; + if( it.item_$ > it.invec_$->buffer_end_$ ) + it.item_$ = it.invec_$->buffer_first_$; + } + if ( it.item_$ >= it.invec_$->elems_end_$ ) { + // moving to origin + it.item_$ = 0p; + return false; + } else { + return true; + } + } + + // permit + + void ^?{}( vector_permit(T) & this ) { + remove(this); + } + + void ?{}( vector_permit(T) & this, vector_transit(T) & src ) { + ( this.invec_$ ){ src.col_$ }; + ( this.item_$ ){ & findElemMem_$( *src.col_$, src.idx_$ ) }; + insert_first( src.col_$->live_iters_$, this ); + } + + void ?{}( vector_permit(T) & this, vector_exit(T) & src ) { + ( this.invec_$ ){ src.invec_$ }; + ( this.item_$ ){ src.item_$ }; + insert_first( src.invec_$->live_iters_$, this ); + } + + T ?`val( vector_permit(T) & src ){ + return *src.item_$; + } + + // vec internals + + void grow( vector( T ) & this ) { + size_t newCapacity = 2 * (this.buffer_end_$ - this.buffer_first_$); + T * newItems = aalloc( newCapacity ); + size_t elemCount = this`length; + for ( ptrdiff_t pos = 0; pos < elemCount; pos += 1 ) { + newItems[pos] = findElemMem_$(this, pos); + } + + while ( vector_permit(T) & liveIter = this.live_iters_$`elems; liveIter`moveNext ) { + liveIter.item_$ += (newItems - this.buffer_first_$); + } + + free( this.buffer_first_$ ); + this.buffer_first_$ = newItems; + this.buffer_end_$ = newItems + newCapacity; + this.elems_first_$ = this.buffer_first_$; + this.elems_end_$ = this.buffer_first_$ + elemCount; + assert (this.elems_end_$ < this.buffer_end_$); + } + + // vec api + + vector_transit(T) push_last( vector( T ) & col, T val ) { + assert (col.exit_refcount_$ == 0); + if (col`length >= col`capacity) { + assert (col`length == col`capacity); + grow(col); + } + // call autogen constructor deleted at end of hfa + vector_transit(T) ret = { & col, col`length }; + *col.elems_end_$ = val; + if (col.elems_first_$ == 0p) col.elems_first_$ = col.elems_end_$; + col.elems_end_$ += 1; + if (col.elems_end_$ >= col.buffer_end_$) col.elems_end_$ = col.buffer_first_$; + return ret; + } + + vector_exit(T) ?`origin( vector( T ) & vec ) { + + // private memberwise constructor, deleted from global namespace at end + // autogen constructor would not do the raii + void ?{}( vector_exit(T) & this, vector(T) * invec_$, T * item_$ ) { + ( this.invec_$ ){ invec_$ }; + ( this.item_$ ){ item_$ }; + this.invec_$->exit_refcount_$ ++; + } + + vector_exit(T) ret = { &vec, 0p }; + return ret; + } + + bool inRange_$( T * query, T * from, T * to) { + if (from == to) return false; + if (from < to) return from <= query && query < to; + return query < to || from <= query; + } + + void insert_before( vector( T ) & col, ptrdiff_t idx, T val ) { + assert (col.exit_refcount_$ == 0); + if (col`length >= col`capacity) { + assert (col`length == col`capacity); + grow(col); + } + + T & insertTargetR = findElemMem_$( col, idx ); + T * insertTarget = & insertTargetR; // doesn't work in one line; must be a bug + + // bubble toward back + if ( col.elems_end_$ < insertTarget ) { + // two phases of bubbling, to wrap around + for (T * tgt = col.elems_end_$; tgt > col.buffer_first_$; tgt--) { + *tgt = *(tgt-1); + } + *col.buffer_first_$ = *(col.buffer_end_$ - 1); + for (T * tgt = col.buffer_end_$ - 1; tgt > insertTarget; tgt--) { + *tgt = *(tgt-1); + } + } else { + for (T * tgt = col.elems_end_$; tgt > insertTarget; tgt--) { + *tgt = *(tgt-1); + } + } + + col.elems_end_$ += 1; + if (col.elems_end_$ == col.buffer_end_$) col.elems_end_$ = col.buffer_first_$; + + *insertTarget = val; + + while ( vector_permit(T) & liveIter = col.live_iters_$`elems; liveIter`moveNext ) { + if ( inRange_$(liveIter.item_$, insertTarget, col.elems_end_$) ) { + liveIter.item_$ += 1; + if (liveIter.item_$ >= col.buffer_end_$) liveIter.item_$ = col.buffer_first_$; + } + } + } + + size_t ?`capacity( vector(T) & v ) { + return v.buffer_end_$ - v.buffer_first_$; + } + + size_t ?`length( vector(T) & v ) { + if (v.elems_first_$ == 0p) return 0; + if (v.elems_first_$ < v.elems_end_$ ) return v.elems_end_$ - v.elems_first_$; + return v.buffer_end_$ - v.elems_first_$ + v.elems_end_$ - v.buffer_first_$; + } + + +} // forall T + +forall( T ) { + void ?{}( vector_exit(T) &, vector(T) *, T * ) = void; + void ?{}( vector_transit(T) & this, vector( T ) * col, ptrdiff_t idx ) = void; +} Index: libcfa/src/concurrency/alarm.hfa =================================================================== --- libcfa/src/concurrency/alarm.hfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ libcfa/src/concurrency/alarm.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -10,6 +10,6 @@ // Created On : Fri Jun 2 11:31:25 2017 // Last Modified By : Peter A. Buhr -// Last Modified On : Mon Mar 26 16:25:41 2018 -// Update Count : 11 +// Last Modified On : Wed Aug 30 21:27:40 2023 +// Update Count : 12 // @@ -23,5 +23,5 @@ #include "time.hfa" -#include "containers/list.hfa" +#include "collections/list.hfa" struct thread$; Index: libcfa/src/concurrency/invoke.h =================================================================== --- libcfa/src/concurrency/invoke.h (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ libcfa/src/concurrency/invoke.h (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -10,11 +10,11 @@ // Created On : Tue Jan 17 12:27:26 2016 // Last Modified By : Peter A. Buhr -// Last Modified On : Tue Mar 14 13:39:31 2023 -// Update Count : 59 +// Last Modified On : Wed Aug 30 21:27:51 2023 +// Update Count : 60 // // No not use #pragma once was this file is included twice in some places. It has its own guard system. -#include "bits/containers.hfa" +#include "bits/collections.hfa" #include "bits/defs.hfa" #include "bits/locks.hfa" @@ -23,5 +23,5 @@ #ifdef __cforall -#include "containers/list.hfa" +#include "collections/list.hfa" extern "C" { #endif Index: libcfa/src/concurrency/kernel.hfa =================================================================== --- libcfa/src/concurrency/kernel.hfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ libcfa/src/concurrency/kernel.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -10,6 +10,6 @@ // Created On : Tue Jan 17 12:27:26 2017 // Last Modified By : Peter A. Buhr -// Last Modified On : Tue Feb 4 12:29:26 2020 -// Update Count : 22 +// Last Modified On : Wed Aug 30 21:28:46 2023 +// Update Count : 23 // @@ -20,5 +20,5 @@ #include "coroutine.hfa" -#include "containers/list.hfa" +#include "collections/list.hfa" extern "C" { Index: libcfa/src/concurrency/locks.hfa =================================================================== --- libcfa/src/concurrency/locks.hfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ libcfa/src/concurrency/locks.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -21,6 +21,6 @@ #include "bits/weakso_locks.hfa" -#include "containers/lockfree.hfa" -#include "containers/list.hfa" +#include "collections/lockfree.hfa" +#include "collections/list.hfa" #include "limits.hfa" Index: libcfa/src/concurrency/once.hfa =================================================================== --- libcfa/src/concurrency/once.hfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ libcfa/src/concurrency/once.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -16,5 +16,5 @@ #pragma once -#include "containers/lockfree.hfa" +#include "collections/lockfree.hfa" #include "kernel/fwd.hfa" Index: libcfa/src/concurrency/select.hfa =================================================================== --- libcfa/src/concurrency/select.hfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ libcfa/src/concurrency/select.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -17,5 +17,5 @@ #pragma once -#include "containers/list.hfa" +#include "collections/list.hfa" #include "alarm.hfa" #include "kernel.hfa" Index: libcfa/src/containers/array.hfa =================================================================== --- libcfa/src/containers/array.hfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ (revision ) @@ -1,270 +1,0 @@ -#pragma once - -#include - - -forall( __CFA_tysys_id_only_X & ) struct tag {}; -#define ttag(T) ((tag(T)){}) -#define ztag(n) ttag(n) - - -// -// The `array` macro is the public interface. -// It computes the type of a dense (trivially strided) array. -// All user-declared objects are dense arrays. -// -// The `arpk` (ARray with PacKing info explicit) type is, generally, a slice with _any_ striding. -// This type is meant for internal use. -// CFA programmers should not instantiate it directly, nor access its field. -// CFA programmers should call ?[?] on it. -// Yet user-given `array(stuff)` expands to `arpk(stuff')`. -// The comments here explain the resulting internals. -// -// Just as a plain-C "multidimesional" array is really array-of-array-of-..., -// so does arpk generally show up as arpk-of-arpk-of... -// -// In the example of `array(float, 3, 4, 5) a;`, -// `typeof(a)` is an `arpk` instantiation. -// These comments explain _its_ arguments, i.e. those of the topmost `arpk` level. -// -// [N] : the number of elements in `a`; 3 in the example -// S : carries the stride size (distance in bytes between &myA[0] and &myA[1]), in sizeof(S); -// same as Timmed when striding is trivial, same as Timmed in the example -// Timmed : (T-immediate) the inner type; conceptually, `typeof(a)` is "arpk of Timmed"; -// array(float, 4, 5) in the example -// Tbase : (T-base) the deepest element type that is not arpk; float in the example -// -forall( [N], S & | sized(S), Timmed &, Tbase & ) { - - // - // Single-dim array sruct (with explicit packing and atom) - // - struct arpk { - S strides[N]; - }; - - // About the choice of integral types offered as subscript overloads: - // Intent is to cover these use cases: - // a[0] // i : zero_t - // a[1] // i : one_t - // a[2] // i : int - // float foo( ptrdiff_t i ) { return a[i]; } // i : ptrdiff_t - // float foo( size_t i ) { return a[i]; } // i : size_t - // forall( [N] ) ... for( i; N ) { total += a[i]; } // i : typeof( sizeof(42) ) - // for( i; 5 ) { total += a[i]; } // i : int - // - // It gets complicated by: - // - CFA does overloading on concrete types, like int and unsigned int, not on typedefed - // types like size_t. So trying to overload on ptrdiff_t vs int works in 64-bit mode - // but not in 32-bit mode. - // - Given bug of Trac #247, CFA gives sizeof expressions type unsigned long int, when it - // should give them type size_t. - // - // gcc -m32 cfa -m32 given bug gcc -m64 (and cfa) - // ptrdiff_t int int long int - // size_t unsigned int unsigned int unsigned long int - // typeof( sizeof(42) ) unsigned int unsigned long int unsigned long int - // int int int int - // - // So the solution must support types {zero_t, one_t, int, unsigned int, long int, unsigned long int} - // - // The solution cannot rely on implicit conversions (e.g. just have one overload for ptrdiff_t) - // because assertion satisfaction requires types to match exacly. Both higher-dimensional - // subscripting and operations on slices use asserted subscript operators. The test case - // array-container/array-sbscr-cases covers the combinations. Mike beleives that commenting out - // any of the current overloads leads to one of those cases failing, either on 64- or 32-bit. - // Mike is open to being shown a smaller set of overloads that still passes the test. - - static inline Timmed & ?[?]( arpk(N, S, Timmed, Tbase) & a, zero_t ) { - assert( 0 < N ); - return (Timmed &) a.strides[0]; - } - - static inline Timmed & ?[?]( arpk(N, S, Timmed, Tbase) & a, one_t ) { - assert( 1 < N ); - return (Timmed &) a.strides[1]; - } - - static inline Timmed & ?[?]( arpk(N, S, Timmed, Tbase) & a, int i ) { - assert( i < N ); - return (Timmed &) a.strides[i]; - } - - static inline const Timmed & ?[?]( const arpk(N, S, Timmed, Tbase) & a, int i ) { - assert( i < N ); - return (Timmed &) a.strides[i]; - } - - static inline Timmed & ?[?]( arpk(N, S, Timmed, Tbase) & a, unsigned int i ) { - assert( i < N ); - return (Timmed &) a.strides[i]; - } - - static inline const Timmed & ?[?]( const arpk(N, S, Timmed, Tbase) & a, unsigned int i ) { - assert( i < N ); - return (Timmed &) a.strides[i]; - } - - static inline Timmed & ?[?]( arpk(N, S, Timmed, Tbase) & a, long int i ) { - assert( i < N ); - return (Timmed &) a.strides[i]; - } - - static inline const Timmed & ?[?]( const arpk(N, S, Timmed, Tbase) & a, long int i ) { - assert( i < N ); - return (Timmed &) a.strides[i]; - } - - static inline Timmed & ?[?]( arpk(N, S, Timmed, Tbase) & a, unsigned long int i ) { - assert( i < N ); - return (Timmed &) a.strides[i]; - } - - static inline const Timmed & ?[?]( const arpk(N, S, Timmed, Tbase) & a, unsigned long int i ) { - assert( i < N ); - return (Timmed &) a.strides[i]; - } - - static inline size_t ?`len( arpk(N, S, Timmed, Tbase) & a ) { - return N; - } - - static inline void __taglen( tag(arpk(N, S, Timmed, Tbase)), tag(N) ) {} - - // workaround #226 (and array relevance thereof demonstrated in mike102/otype-slow-ndims.cfa) - static inline void ?{}( arpk(N, S, Timmed, Tbase) & this ) { - void ?{}( S (&inner)[N] ) {} - ?{}(this.strides); - } - static inline void ^?{}( arpk(N, S, Timmed, Tbase) & this ) { - void ^?{}( S (&inner)[N] ) {} - ^?{}(this.strides); - } -} - -// -// Sugar for declaring array structure instances -// - -forall( Te ) -static inline Te mkar_( tag(Te) ) {} - -forall( [N], ZTags ... , Trslt &, Tatom & | { Trslt mkar_( tag(Tatom), ZTags ); } ) -static inline arpk(N, Trslt, Trslt, Tatom) mkar_( tag(Tatom), tag(N), ZTags ) {} - -// based on https://stackoverflow.com/questions/1872220/is-it-possible-to-iterate-over-arguments-in-variadic-macros - - // Make a FOREACH macro - #define FE_0(WHAT) - #define FE_1(WHAT, X) WHAT(X) - #define FE_2(WHAT, X, ...) WHAT(X)FE_1(WHAT, __VA_ARGS__) - #define FE_3(WHAT, X, ...) WHAT(X)FE_2(WHAT, __VA_ARGS__) - #define FE_4(WHAT, X, ...) WHAT(X)FE_3(WHAT, __VA_ARGS__) - #define FE_5(WHAT, X, ...) WHAT(X)FE_4(WHAT, __VA_ARGS__) - //... repeat as needed - - #define GET_MACRO(_0,_1,_2,_3,_4,_5,NAME,...) NAME - #define FOR_EACH(action,...) \ - GET_MACRO(_0,__VA_ARGS__,FE_5,FE_4,FE_3,FE_2,FE_1,FE_0)(action,__VA_ARGS__) - -#define COMMA_ttag(X) , ttag(X) -#define array( TE, ...) typeof( mkar_( ttag(TE) FOR_EACH( COMMA_ttag, __VA_ARGS__ ) ) ) - -#define COMMA_ztag(X) , ztag(X) -#define zarray( TE, ...) typeof( mkar_( ttag(TE) FOR_EACH( COMMA_ztag, __VA_ARGS__ ) ) ) - -// -// Sugar for multidimensional indexing -// - -// Core -[[-,-,-]] operator - -#ifdef TRY_BROKEN_DESIRED_MD_SUBSCRIPT - -// Desired form. One definition with recursion on IxBC (worked until Jan 2021, see trac #__TODO__) - -forall( TA &, TB &, TC &, IxAB, IxBC ... | { TB & ?[?]( TA &, IxAB ); TC & ?[?]( TB &, IxBC ); } ) -static inline TC & ?[?]( TA & this, IxAB ab, IxBC bc ) { - return this[ab][bc]; -} - -#else - -// Workaround form. Listing all possibilities up to 4 dims. - -forall( TA &, TB &, TC &, IxAB_0, IxBC | { TB & ?[?]( TA &, IxAB_0 ); TC & ?[?]( TB &, IxBC ); } ) -static inline TC & ?[?]( TA & this, IxAB_0 ab, IxBC bc ) { - return this[ab][bc]; -} - -forall( TA &, TB &, TC &, IxAB_0, IxAB_1, IxBC | { TB & ?[?]( TA &, IxAB_0, IxAB_1 ); TC & ?[?]( TB &, IxBC ); } ) -static inline TC & ?[?]( TA & this, IxAB_0 ab0, IxAB_1 ab1, IxBC bc ) { - return this[[ab0,ab1]][bc]; -} - -forall( TA &, TB &, TC &, IxAB_0, IxAB_1, IxAB_2, IxBC | { TB & ?[?]( TA &, IxAB_0, IxAB_1, IxAB_2 ); TC & ?[?]( TB &, IxBC ); } ) -static inline TC & ?[?]( TA & this, IxAB_0 ab0, IxAB_1 ab1, IxAB_2 ab2, IxBC bc ) { - return this[[ab0,ab1,ab2]][bc]; -} - -#endif - -// Available for users to work around Trac #265 -// If `a[...0...]` isn't working, try `a[...ix0...]` instead. - -#define ix0 ((ptrdiff_t)0) - - - -// -// Rotation -// - -// Base -forall( [Nq], Sq & | sized(Sq), Tbase & ) -static inline tag(arpk(Nq, Sq, Tbase, Tbase)) enq_( tag(Tbase), tag(Nq), tag(Sq), tag(Tbase) ) { - tag(arpk(Nq, Sq, Tbase, Tbase)) ret; - return ret; -} - -// Rec -forall( [Nq], Sq & | sized(Sq), [N], S & | sized(S), recq &, recr &, Tbase & | { tag(recr) enq_( tag(Tbase), tag(Nq), tag(Sq), tag(recq) ); } ) -static inline tag(arpk(N, S, recr, Tbase)) enq_( tag(Tbase), tag(Nq), tag(Sq), tag(arpk(N, S, recq, Tbase)) ) { - tag(arpk(N, S, recr, Tbase)) ret; - return ret; -} - -// Wrapper -extern struct all_t {} all; -forall( [N], S & | sized(S), Te &, result &, Tbase & | { tag(result) enq_( tag(Tbase), tag(N), tag(S), tag(Te) ); } ) -static inline result & ?[?]( arpk(N, S, Te, Tbase) & this, all_t ) { - return (result&) this; -} - -// -// Trait of array or slice -// - -// desired: -// forall(A &, Tv &, [N]) -// trait ar { -// Tv& ?[?]( A&, zero_t ); -// Tv& ?[?]( A&, one_t ); -// Tv& ?[?]( A&, int ); -// ... -// size_t ?`len( A& ); -// void __taglen( tag(C), tag(N) ); -// }; - -// working around N's not being accepted as arguments to traits - -#define ar(A, Tv, N) { \ - Tv& ?[?]( A&, zero_t ); \ - Tv& ?[?]( A&, one_t ); \ - Tv& ?[?]( A&, int ); \ - Tv& ?[?]( A&, unsigned int ); \ - Tv& ?[?]( A&, long int ); \ - Tv& ?[?]( A&, unsigned long int ); \ - size_t ?`len( A& ); \ - void __taglen( tag(A), tag(N) ); \ -} Index: libcfa/src/containers/list.hfa =================================================================== --- libcfa/src/containers/list.hfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ (revision ) @@ -1,325 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2020 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// list -- lets a user-defined stuct form intrusive linked lists -// -// Author : Michael Brooks -// Created On : Wed Apr 22 18:00:00 2020 -// Last Modified By : Peter A. Buhr -// Last Modified On : Thu Feb 2 11:32:26 2023 -// Update Count : 2 -// - -#pragma once - -#include - -forall( Decorator &, T & ) -struct tytagref { - inline T &; -}; - -forall( tOuter &, tMid &, tInner & ) -trait embedded { - tytagref( tMid, tInner ) ?`inner( tOuter & ); -}; - -// embedded is reflexive, with no info (void) as the type tag -forall (T &) -static inline tytagref(void, T) ?`inner ( T & this ) { tytagref( void, T ) ret = {this}; return ret; } - - -// -// P9_EMBEDDED: Use on every case of plan-9 inheritance, to make "implements embedded" be a closure of plan-9 inheritance. -// -// struct foo { -// int a, b, c; -// inline (bar); -// }; -// P9_EMBEDDED( foo, bar ) -// - -// usual version, for structs that are top-level declarations -#define P9_EMBEDDED( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, static ) P9_EMBEDDED_BDY_( immedBase ) - -// special version, for structs that are declared in functions -#define P9_EMBEDDED_INFUNC( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, ) P9_EMBEDDED_BDY_( immedBase ) - -// forward declarations of both the above; generally not needed -// may help you control where the P9_EMBEEDED cruft goes, in case "right after the stuct" isn't where you want it -#define P9_EMBEDDED_FWD( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, static ) ; -#define P9_EMBEDDED_FWD_INFUNC( derived, immedBase ) auto P9_EMBEDDED_DECL_( derived, immedBase, ) ; - -// private helpers -#define P9_EMBEDDED_DECL_( derived, immedBase, STORAGE ) \ - forall( Tbase &, TdiscardPath & | { tytagref( TdiscardPath, Tbase ) ?`inner( immedBase & ); } ) \ - STORAGE inline tytagref(immedBase, Tbase) ?`inner( derived & this ) - -#define P9_EMBEDDED_BDY_( immedBase ) { \ - immedBase & ib = this; \ - Tbase & b = ib`inner; \ - tytagref(immedBase, Tbase) result = { b }; \ - return result; \ - } - -#define EMBEDDED_VIA( OUTER, MID, INNER ) \ - (struct { tytagref(MID, INNER) ( * ?`inner ) ( OUTER & ); }){ ?`inner } - -#define DLINK_VIA( TE, TLINK ) \ - EMBEDDED_VIA( TE, TLINK, dlink(TE) ) - - -// The origin is the position encountered at the start of iteration, -// signifying, "need to advance to the first element," and at the end -// of iteration, signifying, "no more elements." Normal comsumption of -// an iterator runs ?`moveNext as the first step, and uses the return -// of ?`moveNext as a guard, before dereferencing the iterator. So -// normal consumption of an iterator does not dereference an iterator -// in origin position. The value of a pointer (underlying a refence) -// that is exposed publicly as an iteraor, and also a pointer stored -// internally in a link field, is tagged, to indicate "is the origin" -// (internally, is the list-head sentinel node), or untagged, to indicate -// "is a regular node." Intent is to help a user who dereferences an -// iterator in origin position (which would be an API-use error on their -// part), by failing fast. - -#if defined( __x86_64 ) - // Preferred case: tag in the most-significant bit. Dereference - // has been shown to segfault consistently. Maintenance should - // list more architectures as "ok" here, to let them use the - // preferred case, when valid. - #define ORIGIN_TAG_BITNO ( 8 * sizeof( size_t ) - 1 ) -#else - // Fallback case: tag in the least-significant bit. Dereference - // will often give an alignment error, but may not, e.g. if - // accessing a char-typed member. 32-bit x86 uses the most- - // significant bit for real room on the heap. - #define ORIGIN_TAG_BITNO 0 -#endif -#define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO) - -#define ORIGIN_TAG_SET(p) ((p) | ORIGIN_TAG_MASK) -#define ORIGIN_TAG_CLEAR(p) ((p) & ~ORIGIN_TAG_MASK) -#define ORIGIN_TAG_QUERY(p) ((p) & ORIGIN_TAG_MASK) - - -forall( tE & ) { - - struct dlink{ - tE *next; - tE *prev; - }; - - static inline void ?{}( dlink(tE) & this ) { - this.next = 0p; - this.prev = 0p; - } - - forall( tLinks & = dlink(tE) ) - struct dlist { - inline dlink(tE); - }; - - forall( tLinks & | embedded( tE, tLinks, dlink(tE) ) ) { - static inline tE * $get_list_origin_addr( dlist(tE, tLinks) & lst ) { - dlink(tE) & link_from_null = ( * (tE *) 0p )`inner; - ptrdiff_t link_offset = (ptrdiff_t) & link_from_null; - size_t origin_addr = ((size_t) & lst) - link_offset; - size_t preResult = ORIGIN_TAG_SET( origin_addr ); - return (tE *)preResult; - } - - static inline void ?{}( dlist(tE, tLinks) & this ) { - tE * listOrigin = $get_list_origin_addr( this ); - ( ( dlink(tE) & ) this ){ listOrigin, listOrigin } ; - } - } - -} - - -forall( tE &, tLinks & | embedded( tE, tLinks, dlink(tE) ) ) { - - static inline void insert_after(tE & list_pos, tE &to_insert) { - verify (&list_pos != 0p); - verify (&to_insert != 0p); - dlink(tE) & linkToInsert = to_insert`inner; - verify(linkToInsert.prev == 0p); - verify(linkToInsert.next == 0p); - tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos ); - dlink(tE) & list_pos_links = list_pos_elem`inner; - asm( "" : : : "memory" ); - tE & after_raw = * list_pos_links.next; - tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw ); - linkToInsert.prev = & list_pos; - linkToInsert.next = & after_raw; - dlink(tE) & afterLinks = after_elem`inner; - afterLinks.prev = &to_insert; - list_pos_links.next = &to_insert; - asm( "" : : : "memory" ); - } - - static inline void insert_before(tE & list_pos, tE &to_insert) { - verify (&list_pos != 0p); - verify (&to_insert != 0p); - dlink(tE) & linkToInsert = to_insert`inner; - verify(linkToInsert.next == 0p); - verify(linkToInsert.prev == 0p); - tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos ); - dlink(tE) & list_pos_links = list_pos_elem`inner; - asm( "" : : : "memory" ); - tE & before_raw = * (list_pos_links).prev; - tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw ); - linkToInsert.next = & list_pos; - linkToInsert.prev = & before_raw; - dlink(tE) & beforeLinks = before_elem`inner; - beforeLinks.next = &to_insert; - (list_pos_links).prev = &to_insert; - asm( "" : : : "memory" ); - } - - static inline tE & remove(tE & list_pos) { - verify (&list_pos != 0p); - verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos) ); - dlink(tE) & list_pos_links = list_pos`inner; - tE & before_raw = * list_pos_links.prev; - tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw ); - dlink(tE) & before_links = before_elem`inner; - tE & after_raw = * list_pos_links.next; - tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw ); - dlink(tE) & after_links = after_elem`inner; - before_links.next = &after_raw; - after_links.prev = &before_raw; - asm( "" : : : "memory" ); - list_pos_links.prev = 0p; - list_pos_links.next = 0p; - asm( "" : : : "memory" ); - return list_pos; - } - - static inline tE & ?`first( dlist(tE, tLinks) &lst ) { - tE * firstPtr = lst.next; - if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p; - return *firstPtr; - } - static inline tE & ?`last ( dlist(tE, tLinks) &lst ) { - tE * lastPtr = lst.prev; - if (ORIGIN_TAG_QUERY((size_t)lastPtr)) lastPtr = 0p; - return *lastPtr; - } - - static inline bool ?`isEmpty( dlist(tE, tLinks) & lst ) { - tE * firstPtr = lst.next; - if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p; - return firstPtr == 0p; - } - - static inline bool ?`isListed( tE & e ) { - verify (&e != 0p); - dlink(tE) & e_links = e`inner; - return (e_links.prev != 0p) || (e_links.next != 0p); - } - - static inline tE & ?`elems( dlist(tE, tLinks) & lst ) { - tE * origin = $get_list_origin_addr( lst ); - return *origin; - } - - static inline bool ?`moveNext( tE && refx ) { - tE && ref_inner = refx; - tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner ); - &ref_inner = oldReferent`inner.next; - return &ref_inner != 0p && - ! ORIGIN_TAG_QUERY( (size_t) & ref_inner ); - } - - static inline bool ?`movePrev( tE && refx ) { - tE && ref_inner = refx; - tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner ); - &ref_inner = oldReferent`inner.prev; - return &ref_inner != 0p && - ! ORIGIN_TAG_QUERY( (size_t) & ref_inner ); - } - - static inline bool ?`hasNext( tE & e ) { - return e`moveNext; - } - - static inline bool ?`hasPrev( tE & e ) { - return e`movePrev; - } - - static inline tE & ?`next( tE & e ) { - if( e`moveNext ) return e; - return * 0p; - } - - static inline tE & ?`prev( tE & e ) { - if( e`movePrev ) return e; - return * 0p; - } - - static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) { - insert_after(lst`elems, e); - } - - static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) { - insert_before(lst`elems, e); - } - - static inline tE & try_pop_front( dlist(tE, tLinks) &lst ) { - tE & first_inlist = lst`first; - tE & first_item = first_inlist; - if (&first_item) remove(first_inlist); - return first_item; - } - - static inline tE & try_pop_back( dlist(tE, tLinks) &lst ) { - tE & last_inlist = lst`last; - tE & last_item = last_inlist; - if (&last_item) remove(last_inlist); - return last_item; - } - - - #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__)) - static bool $validate_fwd( dlist(tE, tLinks) & this ) { - if ( ! & this`first ) return ( (& this`last) == 0p); - - tE & lagElem = *0p; - - while ( tE & it = this`elems; it`moveNext ) { - if (& lagElem == 0p && &it != & this`first ) return false; - & lagElem = & it; - } - - if (& lagElem != & this`last) return false; - - // TODO: verify that it is back at this`elems; - return true; - } - static bool $validate_rev( dlist(tE, tLinks) & this ) { - if ( ! & this`last ) return ( (& this`first) == 0p); - - tE & lagElem = *0p; - - while ( tE & it = this`elems; it`movePrev ) { - if (& lagElem == 0p && &it != & this`last ) return false; - & lagElem = & it; - } - - if (& lagElem != & this`first) return false; - - // TODO: verify that it is back at this`elems; - return true; - } - static bool validate( dlist(tE, tLinks) & this ) { - return $validate_fwd(this) && $validate_rev(this); - } - #endif - -} - Index: libcfa/src/containers/lockfree.hfa =================================================================== --- libcfa/src/containers/lockfree.hfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ (revision ) @@ -1,258 +1,0 @@ -#pragma once - -#include - -#include -#include - -forall( T &) { - //------------------------------------------------------------ - // Queue based on the MCS lock - // It is a Multi-Producer/Single-Consumer queue threads pushing - // elements must hold on to the elements they push - // Not appropriate for an async message queue for example, - struct mcs_queue { - T * volatile tail; - }; - - static inline void ?{}(mcs_queue(T) & this) { this.tail = 0p; } - static inline bool empty(const mcs_queue(T) & this) { return !this.tail; } - - static inline forall(| { T * volatile & ?`next ( T * ); }) - { - // Adds an element to the list - // Multi-Thread Safe, Lock-Free - T * push(mcs_queue(T) & this, T * elem) __attribute__((artificial)); - T * push(mcs_queue(T) & this, T * elem) { - /* paranoid */ verify(!(elem`next)); - // Race to add to the tail - T * prev = __atomic_exchange_n(&this.tail, elem, __ATOMIC_SEQ_CST); - // If we aren't the first, we need to tell the person before us - // No need to - if (prev) prev`next = elem; - return prev; - } - - // Advances the head of the list, dropping the element given. - // Passing an element that is not the head is undefined behavior - // NOT Multi-Thread Safe, concurrent pushes are safe - T * advance(mcs_queue(T) & this, T * elem) __attribute__((artificial)); - T * advance(mcs_queue(T) & this, T * elem) { - T * expected = elem; - // Check if this is already the last item - if (__atomic_compare_exchange_n(&this.tail, &expected, 0p, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) return 0p; - - // If not wait for next item to show-up, filled by push - while (!(elem`next)) Pause(); - - // we need to return if the next link was empty - T * ret = elem`next; - - // invalidate link to reset to initial state - elem`next = 0p; - return ret; - } - } - - //------------------------------------------------------------ - // Queue based on the MCS lock - // Extension of the above lock which supports 'blind' pops. - // i.e., popping a value from the head without knowing what the head is - // has no extra guarantees beyond the mcs_queue - struct mpsc_queue { - inline mcs_queue(T); - T * volatile head; - }; - - static inline void ?{}(mpsc_queue(T) & this) { - ((mcs_queue(T)&)this){}; - this.head = 0p; - } - - static inline forall(| { T * volatile & ?`next ( T * ); }) - { - // Added a new element to the queue - // Multi-Thread Safe, Lock-Free - T * push(mpsc_queue(T) & this, T * elem) __attribute__((artificial)); - T * push(mpsc_queue(T) & this, T * elem) { - T * prev = push((mcs_queue(T)&)this, elem); - if (!prev) this.head = elem; - return prev; - } - - // Pop an element from the queue - // return the element that was removed - // next is set to the new head of the queue - // NOT Multi-Thread Safe - T * pop(mpsc_queue(T) & this, T *& next) __attribute__((artificial)); - T * pop(mpsc_queue(T) & this, T *& next) { - T * elem = this.head; - // If head is empty just return - if (!elem) return 0p; - - // If there is already someone in the list, then it's easy - if (elem`next) { - this.head = next = elem`next; - // force memory sync - __atomic_thread_fence(__ATOMIC_SEQ_CST); - - // invalidate link to reset to initial state - elem`next = 0p; - } - // Otherwise, there might be a race where it only looks but someone is enqueuing - else { - // null out head here, because we linearize with push - // at the CAS in advance and therefore can write to head - // after that point, it could overwrite the write in push - this.head = 0p; - next = advance((mcs_queue(T)&)this, elem); - - // Only write to the head if there is a next element - // it is the only way we can guarantee we are not overwriting - // a write made in push - if (next) this.head = next; - } - - // return removed element - return elem; - } - - // Same as previous function - T * pop(mpsc_queue(T) & this) { - T * _ = 0p; - return pop(this, _); - } - } - - //------------------------------------------------------------ - // Queue based on the MCS lock with poisoning - // It is a Multi-Producer/Single-Consumer queue threads pushing - // elements must hold on to the elements they push - // Not appropriate for an async message queue for example - // poisoning the queue prevents any new elements from being push - // enum(void*) poison_state { - // EMPTY = 0p, - // POISON = 1p, - // IN_PROGRESS = 1p - // }; - - struct poison_list { - T * volatile head; - }; - - static inline void ?{}(poison_list(T) & this) { this.head = 0p; } - static inline bool is_poisoned( const poison_list(T) & this ) { return 1p == this.head; } - - static inline forall(| { T * volatile & ?`next ( T * ); }) - { - // Adds an element to the list - // Multi-Thread Safe, Lock-Free - bool push(poison_list(T) & this, T * elem) __attribute__((artificial)); - bool push(poison_list(T) & this, T * elem) { - /* paranoid */ verify(0p == (elem`next)); - __atomic_store_n( &elem`next, (T*)1p, __ATOMIC_RELAXED ); - - // read the head up-front - T * expected = this.head; - for() { - // check if it's poisoned - if(expected == 1p) return false; - - // try to CAS the elem in - if(__atomic_compare_exchange_n(&this.head, &expected, elem, true, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED)) { - // We managed to exchange in, we are done - - // We should never succeed the CAS if it's poisonned and the elem should be 1p. - /* paranoid */ verify( expected != 1p ); - /* paranoid */ verify( elem`next == 1p ); - - // If we aren't the first, we need to tell the person before us - // No need to - elem`next = expected; - return true; - } - } - } - - // Advances the head of the list, dropping the element given. - // Passing an element that is not the head is undefined behavior - // NOT Multi-Thread Safe, concurrent pushes are safe - T * advance(T * elem) __attribute__((artificial)); - T * advance(T * elem) { - T * ret; - - // Wait for next item to show-up, filled by push - while (1p == (ret = __atomic_load_n(&elem`next, __ATOMIC_RELAXED))) Pause(); - - return ret; - } - - // Poison the queue, preveting new pushes and returning the head - T * poison(poison_list(T) & this) __attribute__((artificial)); - T * poison(poison_list(T) & this) { - T * ret = __atomic_exchange_n( &this.head, (T*)1p, __ATOMIC_SEQ_CST ); - /* paranoid */ verifyf( ret != (T*)1p, "Poison list %p poisoned more than once!", &this ); - return ret; - } - } -} - -forall( T & ) -struct LinkData { - T * volatile top; // pointer to stack top - uintptr_t count; // count each push -}; - -forall( T & ) -union Link { - LinkData(T) data; - #if __SIZEOF_INT128__ == 16 - __int128 // gcc, 128-bit integer - #else - uint64_t // 64-bit integer - #endif // __SIZEOF_INT128__ == 16 - atom; -}; // Link - -forall( T | sized(T) | { Link(T) * ?`next( T * ); } ) { - struct StackLF { - Link(T) stack; - }; // StackLF - - static inline { - void ?{}( StackLF(T) & this ) with(this) { stack.atom = 0; } - - T * top( StackLF(T) & this ) with(this) { return stack.data.top; } - - void push( StackLF(T) & this, T & n ) with(this) { - *( &n )`next = stack; // atomic assignment unnecessary, or use CAA - for () { // busy wait - if ( __atomic_compare_exchange_n( &stack.atom, &( &n )`next->atom, (Link(T))@{ (LinkData(T))@{ &n, ( &n )`next->data.count + 1} }.atom, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) break; // attempt to update top node - } // for - } // push - - T * pop( StackLF(T) & this ) with(this) { - Link(T) t @= stack; // atomic assignment unnecessary, or use CAA - for () { // busy wait - if ( t.data.top == 0p ) return 0p; // empty stack ? - Link(T) * next = ( t.data.top )`next; - if ( __atomic_compare_exchange_n( &stack.atom, &t.atom, (Link(T))@{ (LinkData(T))@{ next->data.top, t.data.count } }.atom, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) return t.data.top; // attempt to update top node - } // for - } // pop - - bool unsafe_remove( StackLF(T) & this, T * node ) with(this) { - Link(T) * link = &stack; - for () { - // TODO: Avoiding some problems with double fields access. - LinkData(T) * data = &link->data; - T * next = (T *)&(*data).top; - if ( next == node ) { - data->top = ( node )`next->data.top; - return true; - } - if ( next == 0p ) return false; - link = ( next )`next; - } - } - } // distribution -} // distribution Index: libcfa/src/containers/maybe.cfa =================================================================== --- libcfa/src/containers/maybe.cfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ (revision ) @@ -1,103 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// maybe.c -- May contain a value. -// -// Author : Andrew Beach -// Created On : Wed May 24 15:40:00 2017 -// Last Modified By : Peter A. Buhr -// Last Modified On : Sun Feb 17 11:22:03 2019 -// Update Count : 3 -// - -#include -#include - -#pragma GCC visibility push(default) - -forall(T) -void ?{}(maybe(T) & this) { - this.has_value = false; -} - -forall(T) -void ?{}(maybe(T) & this, T value) { - this.has_value = true; - (this.value){value}; -} - -forall(T) -void ?{}(maybe(T) & this, maybe(T) other) { - this.has_value = other.has_value; - if (other.has_value) { - (this.value){other.value}; - } -} - -forall(T) -maybe(T) ?=?(maybe(T) & this, maybe(T) that) { - if (this.has_value && that.has_value) { - this.value = that.value; - } else if (this.has_value) { - ^(this.value){}; - this.has_value = false; - } else if (that.has_value) { - this.has_value = true; - (this.value){that.value}; - } - return this; -} - -forall(T) -void ^?{}(maybe(T) & this) { - if (this.has_value) { - ^(this.value){}; - } -} - -forall(T) -bool ?!=?(maybe(T) this, zero_t) { - return this.has_value; -} - -forall(T) -maybe(T) maybe_value(T value) { - return (maybe(T)){value}; -} - -forall(T) -maybe(T) maybe_none() { - return (maybe(T)){}; -} - -forall(T) -bool has_value(maybe(T) * this) { - return this->has_value; -} - -forall(T) -T get(maybe(T) * this) { - assertf(this->has_value, "attempt to get from maybe without value"); - return this->value; -} - -forall(T) -void set(maybe(T) * this, T value) { - if (this->has_value) { - this->value = value; - } else { - this->has_value = true; - (this->value){value}; - } -} - -forall(T) -void set_none(maybe(T) * this) { - if (this->has_value) { - this->has_value = false; - ^(this->value){}; - } -} Index: libcfa/src/containers/maybe.hfa =================================================================== --- libcfa/src/containers/maybe.hfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ (revision ) @@ -1,69 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// maybe -- May contain a value. -// -// Author : Andrew Beach -// Created On : Wed May 24 14:43:00 2017 -// Last Modified By : Peter A. Buhr -// Last Modified On : Sat Jul 22 10:00:52 2017 -// Update Count : 4 -// - -#pragma once - -#include - -// DO NOT USE DIRECTLY! -forall(T) -struct maybe { - bool has_value; - T value; -}; - - -forall(T) -void ?{}(maybe(T) & this); - -forall(T) -void ?{}(maybe(T) & this, T value); - -forall(T) -void ?{}(maybe(T) & this, maybe(T) other); - -forall(T) -void ^?{}(maybe(T) & this); - -forall(T) -maybe(T) ?=?(maybe(T) & this, maybe(T) other); - -forall(T) -bool ?!=?(maybe(T) this, zero_t); - -/* Waiting for bug#11 to be fixed. -forall(T) -maybe(T) maybe_value(T value); - -forall(T) -maybe(T) maybe_none(); -*/ - -forall(T) -bool has_value(maybe(T) * this); - -forall(T) -T get(maybe(T) * this); - -forall(T) -void set(maybe(T) * this, T value); - -forall(T) -void set_none(maybe(T) * this); - -// Local Variables: // -// mode: c // -// tab-width: 4 // -// End: // Index: libcfa/src/containers/pair.cfa =================================================================== --- libcfa/src/containers/pair.cfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ (revision ) @@ -1,47 +1,0 @@ -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// pair.c -- -// -// Author : Aaron Moss -// Created On : Wed Apr 12 15:32:00 2017 -// Last Modified By : Aaron Moss -// Last Modified On : Wed Apr 12 15:32:00 2017 -// Update Count : 1 -// - -#include - -forall(R, S - | { int ?==?(R, R); int ??(R, R); int ?>?(S, S); }) -int ?>?(pair(R, S) p, pair(R, S) q) { - return p.first > q.first || ( p.first == q.first && p.second > q.second ); -} - -forall(R, S - | { int ?==?(R, R); int ?>?(R, R); int ?>=?(S, S); }) -int ?>=?(pair(R, S) p, pair(R, S) q) { - return p.first > q.first || ( p.first == q.first && p.second >= q.second ); -} Index: libcfa/src/containers/pair.hfa =================================================================== --- libcfa/src/containers/pair.hfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ (revision ) @@ -1,48 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// pair -- -// -// Author : Aaron Moss -// Created On : Wed Apr 12 15:32:00 2017 -// Last Modified By : Peter A. Buhr -// Last Modified On : Sat Jul 22 09:59:53 2017 -// Update Count : 2 -// - -#pragma once - -forall(R, S) struct pair { - R first; - S second; -}; - -forall(R, S - | { int ?==?(R, R); int ??(R, R); int ?>?(S, S); }) -int ?>?(pair(R, S) p, pair(R, S) q); - -forall(R, S - | { int ?==?(R, R); int ?>?(R, R); int ?>=?(S, S); }) -int ?>=?(pair(R, S) p, pair(R, S) q); - -// Local Variables: // -// mode: c // -// tab-width: 4 // -// End: // Index: libcfa/src/containers/result.cfa =================================================================== --- libcfa/src/containers/result.cfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ (revision ) @@ -1,127 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// result.c -- Contains the expected value or an error value. -// -// Author : Andrew Beach -// Created On : Wed May 24 15:40:00 2017 -// Last Modified By : Peter A. Buhr -// Last Modified On : Sun Feb 17 11:24:04 2019 -// Update Count : 3 -// - -#include -#include - -#pragma GCC visibility push(default) - -forall(T, E) -void ?{}(result(T, E) & this) { - this.has_value = false; - (this.error){}; -} - -forall(T, E) -void ?{}(result(T, E) & this, one_t, T value) { - this.has_value = true; - (this.value){value}; -} - -forall(T, E) -void ?{}(result(T, E) & this, zero_t, E error) { - this.has_value = false; - (this.error){error}; -} - -forall(T, E) -void ?{}(result(T, E) & this, result(T, E) other) { - this.has_value = other.has_value; - if (other.has_value) { - (this.value){other.value}; - } else { - (this.error){other.error}; - } -} - -forall(T, E) -result(T, E) ?=?(result(T, E) & this, result(T, E) that) { - if (this.has_value && that.has_value) { - this.value = that.value; - } else if (this.has_value) { - ^(this.value){}; - this.has_value = false; - (this.error){that.error}; - } else if (that.has_value) { - ^(this.error){}; - this.has_value = true; - (this.value){that.value}; - } else { - this.error = that.error; - } -} - -forall(T, E) -void ^?{}(result(T, E) & this) { - if (this.has_value) { - ^(this.value){}; - } else { - ^(this.error){}; - } -} - -forall(T, E) -bool ?!=?(result(T, E) this, zero_t) { - return this.has_value; -} - -forall(T, E) -result(T, E) result_value(T value) { - return (result(T, E)){1, value}; -} - -forall(T, E) -result(T, E) result_error(E error) { - return (result(T, E)){0, error}; -} - -forall(T, E) -bool has_value(result(T, E) * this) { - return this->has_value; -} - -forall(T, E) -T get(result(T, E) * this) { - assertf(this->has_value, "attempt to get from result without value"); - return this->value; -} - -forall(T, E) -E get_error(result(T, E) * this) { - assertf(!this->has_value, "attempt to get from result without error"); - return this->error; -} - -forall(T, E) -void set(result(T, E) * this, T value) { - if (this->has_value) { - this->value = value; - } else { - ^(this->error){}; - this->has_value = true; - (this->value){value}; - } -} - -forall(T, E) -void set_error(result(T, E) * this, E error) { - if (this->has_value) { - ^(this->value){}; - this->has_value = false; - (this->error){error}; - } else { - this->error = error; - } -} Index: libcfa/src/containers/result.hfa =================================================================== --- libcfa/src/containers/result.hfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ (revision ) @@ -1,81 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// result -- Contains the expected value or an error value. -// -// Author : Andrew Beach -// Created On : Wed May 24 14:45:00 2017 -// Last Modified By : Peter A. Buhr -// Last Modified On : Sat Jul 22 10:00:44 2017 -// Update Count : 3 -// - -#pragma once - -#include - -// DO NOT USE DIRECTLY! -forall(T, E) -union inner_result{ - T value; - E error; -}; - -forall(T, E) -struct result { - bool has_value; - inline union inner_result(T, E); -}; - - -forall(T, E) -void ?{}(result(T, E) & this); - -forall(T, E) -void ?{}(result(T, E) & this, one_t, T value); - -forall(T, E) -void ?{}(result(T, E) & this, zero_t, E error); - -forall(T, E) -void ?{}(result(T, E) & this, result(T, E) other); - -forall(T, E) -void ^?{}(result(T, E) & this); - -forall(T, E) -result(T, E) ?=?(result(T, E) & this, result(T, E) other); - -forall(T, E) -bool ?!=?(result(T, E) this, zero_t); - -/* Wating for bug#11 to be fixed. -forall(T, E) -result(T, E) result_value(T value); - -forall(T, E) -result(T, E) result_error(E error); -*/ - -forall(T, E) -bool has_value(result(T, E) * this); - -forall(T, E) -T get(result(T, E) * this); - -forall(T, E) -E get_error(result(T, E) * this); - -forall(T, E) -void set(result(T, E) * this, T value); - -forall(T, E) -void set_error(result(T, E) * this, E error); - -// Local Variables: // -// mode: c // -// tab-width: 4 // -// End: // Index: libcfa/src/containers/string.cfa =================================================================== --- libcfa/src/containers/string.cfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ (revision ) @@ -1,458 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// string -- variable-length, mutable run of text, with value semantics -// -// Author : Michael L. Brooks -// Created On : Fri Sep 03 11:00:00 2021 -// Last Modified By : Peter A. Buhr -// Last Modified On : Mon Aug 28 19:00:45 2023 -// Update Count : 146 -// - -#include "string.hfa" -#include "string_res.hfa" -#include - -#pragma GCC visibility push(default) - -/* -Implementation Principle: typical operation translates to the equivalent -operation on `inner`. Exceptions are implementing new RAII pattern for value -semantics and some const-hell handling. -*/ - -//////////////////////////////////////////////////////// -// string RAII - - -void ?{}( string & this ) { - (this.inner) { malloc() }; - ?{}( *this.inner ); -} - -// private (not in header) -static void ?{}( string & this, string_res & src, size_t start, size_t end ) { - (this.inner) { malloc() }; - ?{}( *this.inner, src, SHARE_EDITS, start, end ); -} - -void ?{}( string & this, const string & other ) { - (this.inner) { malloc() }; - ?{}( *this.inner, *other.inner, COPY_VALUE ); -} - -void ?{}( string & this, string & other ) { - ?{}( this, (const string &) other ); -} - -void ?{}( string & this, const char * val ) { - (this.inner) { malloc() }; - ?{}( *this.inner, val ); -} - -void ?{}( string & this, const char * buffer, size_t bsize) { - (this.inner) { malloc() }; - ?{}( *this.inner, buffer, bsize ); -} - -void ^?{}( string & this ) { - ^(*this.inner){}; - free( this.inner ); - this.inner = 0p; -} - -//////////////////////////////////////////////////////// -// Alternate construction: request shared edits - -string_WithSharedEdits ?`shareEdits( string & this ) { - string_WithSharedEdits ret = { &this }; - return ret; -} - -void ?{}( string & this, string_WithSharedEdits src ) { - ?{}( this, *src.s->inner, 0, src.s->inner->Handle.lnth); -} - -//////////////////////////////////////////////////////// -// Assignment - -void ?=?( string & this, const char * val ) { - (*this.inner) = val; -} - -void ?=?(string & this, const string & other) { - (*this.inner) = (*other.inner); -} - -void ?=?( string & this, char val ) { - (*this.inner) = val; -} - -string & ?=?(string & this, string & other) { //// <---- straw man change - (*this.inner) = (*other.inner); - return this; -} - - -//////////////////////////////////////////////////////// -// Input-Output - -ofstream & ?|?( ofstream & out, const string & this ) { - return out | (*this.inner); // print internal string_res -} - -void ?|?( ofstream & out, const string & this ) { - (ofstream &)(out | (*this.inner)); ends( out ); -} - -ifstream & ?|?(ifstream & in, string & this) { - return in | (*this.inner); // read to internal string_res -} - -void ?|?( ifstream & in, string & this ) { - (ifstream &)(in | this); ends( in ); -} - -static void readstr( ifstream & is, _Istream_str f, char fmtstr[], char cstr[] ) { - int check = f.rwd - 1; - - if ( ! f.flags.rwd ) cstr[check] = '\0'; // insert sentinel - int len = fmt( is, fmtstr, cstr ); - // fprintf( stderr, "KK %s %zd %d %c %s\n", fmtstr, len, check, cstr[check], cstr ); - - if ( ! f.flags.rwd && cstr[check] != '\0' ) // sentinel overwritten ? - throw (cstring_length){ &cstring_length_vt }; - - if ( f.flags.delimit ) { // getline ? - if ( len == 0 ) cstr[0] = '\0'; // empty read => argument unchanged => set empty - if ( ! eof( is ) ) fmt( is, "%*c" ); // ignore delimiter - } //if -} // readstr - -ifstream & ?|?( ifstream & is, _Istream_str f ) { - // skip, same as for char * - if ( ! &f.s ) { - // fprintf( stderr, "skip %s %d\n", f.scanset, f.wd ); - if ( f.rwd == -1 ) fmt( is, f.scanset, "" ); // no input arguments - else for ( f.rwd ) fmt( is, "%*c" ); - return is; - } // if - - enum { gwd = 16 + 2, wd = gwd - 1 }; // guarded and unguarded width - char cstr[gwd]; // read in chunks - bool cont = false;; - - if ( f.rwd == -1 ) f.rwd = wd; - const char * scanset = f.scanset;; - if ( f.flags.delimit ) scanset = f.delimit; // getline ? - - size_t len = 0; - if ( scanset ) len = strlen( scanset ); - char fmtstr[len + 16]; - int start = 1; - fmtstr[0] = '%'; - if ( f.flags.ignore ) { fmtstr[1] = '*'; start += 1; } - if ( f.rwd != -1 ) { start += sprintf( &fmtstr[start], "%d", f.rwd ); } - - if ( ! scanset ) { - // %s, %*s, %ws, %*ws - fmtstr[start] = 's'; fmtstr[start + 1] = '\0'; - // printf( "cstr %s\n", fmtstr ); - } else { - // incl %[xxx], %*[xxx], %w[xxx], %*w[xxx] - // excl %[^xxx], %*[^xxx], %w[^xxx], %*w[^xxx] - fmtstr[start] = '['; start += 1; - if ( f.flags.inex ) { fmtstr[start] = '^'; start += 1; } - strcpy( &fmtstr[start], scanset ); // copy includes '\0' - len += start; - fmtstr[len] = ']'; fmtstr[len + 1] = '\0'; - // printf( "incl/excl %s\n", fmtstr ); - } // if - - cstr[wd] = '\0'; // guard null terminate string - try { - readstr( is, f, fmtstr, cstr ); - } catch( cstring_length * ) { - cont = true; - } finally { - f.s = cstr; // ok to initialize string - } // try - for ( ; cont; ) { // overflow read ? - cont = false; - try { - readstr( is, f, fmtstr, cstr ); - } catch( cstring_length * ) { - cont = true; // continue not allowed - } finally { - f.s += cstr; // build string chunk at a time - } // try - } // for - return is; -} // ?|? - -void ?|?( ifstream & in, _Istream_str f ) { - (ifstream &)(in | f); ends( in ); -} - -// void getline( ifstream & in, string & str, const char delimit = '\n' ) { -// // .---------------, -// // | | | | |...|0|0| check and guard -// // `---------------' -// enum { gwd = 128 + 2, wd = gwd - 1 }; // guarded and unguarded width -// char cstr[gwd]; // read in chunks -// bool cont = false;; - -// cstr[wd] = '\0'; // guard null terminate string -// try { -// in | getline( wdi( wd, cstr ), delimit ); // must have room for string terminator -// if ( eof( in ) ) return; // do not change argument -// } catch( cstring_length * ) { -// cont = true; -// } finally { -// str = cstr; // ok to initialize string -// } // try -// for ( ; cont; ) { // overflow read ? -// cont = false; -// try { -// in | getline( wdi( wd, cstr ), delimit ); // must have room for string terminator -// if ( eof( in ) ) return; -// } catch( cstring_length * ) { -// cont = true; // continue not allowed -// } finally { -// str += cstr; // build string chunk at a time -// } // try -// } // for -// } - -//////////////////////////////////////////////////////// -// Slicing - -string ?()( string & this, size_t start, size_t end ) { - string ret = { *this.inner, start, end }; - return ret`shareEdits; -} - -string ?()( string & this, size_t start ) { - string ret = { *this.inner, start, size( this ) }; - return ret`shareEdits; -} - -//////////////////////////////////////////////////////// -// Comparison - -bool ?==?(const string & s, const string & other) { - return *s.inner == *other.inner; -} - -bool ?!=?(const string & s, const string & other) { - return *s.inner != *other.inner; -} - -bool ?==?(const string & s, const char * other) { - return *s.inner == other; -} - -bool ?!=?(const string & s, const char * other) { - return *s.inner != other; -} - -//////////////////////////////////////////////////////// -// Getter - -size_t size(const string & s) { - return size( * s.inner ); -} - -//////////////////////////////////////////////////////// -// Concatenation - -void ?+=?(string & s, char other) { - (*s.inner) += other; -} - -void ?+=?(string & s, const string & s2) { - (*s.inner) += (*s2.inner); -} - -void ?+=?(string & s, const char * other) { - (*s.inner) += other; -} - -string ?+?(const string & s, char other) { - string ret = s; - ret += other; - return ret; -} - -string ?+?(const string & s, const string & s2) { - string ret = s; - ret += s2; - return ret; -} - -string ?+?(const char * s1, const char * s2) { - string ret = s1; - ret += s2; - return ret; -} - -string ?+?(const string & s, const char * other) { - string ret = s; - ret += other; - return ret; -} - -//////////////////////////////////////////////////////// -// Repetition - -string ?*?(const string & s, size_t factor) { - string ret = ""; - for (factor) ret += s; - return ret; -} - -string ?*?(char c, size_t size) { - string ret = ""; - for ((size_t)size) ret += c; - return ret; -} - -string ?*?(const char *s, size_t factor) { - string ss = s; - return ss * factor; -} - -//////////////////////////////////////////////////////// -// Character access - -char ?[?](const string & s, size_t index) { - return (*s.inner)[index]; -} - -string ?[?](string & s, size_t index) { - string ret = { *s.inner, index, index + 1 }; - return ret`shareEdits; -} - -//////////////////////////////////////////////////////// -// Search - -bool contains(const string & s, char ch) { - return contains( *s.inner, ch ); -} - -int find(const string & s, char search) { - return find( *s.inner, search ); -} - -int find(const string & s, const string & search) { - return find( *s.inner, *search.inner ); -} - -int find(const string & s, const char * search) { - return find( *s.inner, search); -} - -int find(const string & s, const char * search, size_t searchsize) { - return find( *s.inner, search, searchsize); -} - -int findFrom(const string & s, size_t fromPos, char search) { - return findFrom( *s.inner, fromPos, search ); -} - -int findFrom(const string & s, size_t fromPos, const string & search) { - return findFrom( *s.inner, fromPos, *search.inner ); -} - -int findFrom(const string & s, size_t fromPos, const char * search) { - return findFrom( *s.inner, fromPos, search ); -} - -int findFrom(const string & s, size_t fromPos, const char * search, size_t searchsize) { - return findFrom( *s.inner, fromPos, search, searchsize ); -} - -bool includes(const string & s, const string & search) { - return includes( *s.inner, *search.inner ); -} - -bool includes(const string & s, const char * search) { - return includes( *s.inner, search ); -} - -bool includes(const string & s, const char * search, size_t searchsize) { - return includes( *s.inner, search, searchsize ); -} - -bool startsWith(const string & s, const string & prefix) { - return startsWith( *s.inner, *prefix.inner ); -} - -bool startsWith(const string & s, const char * prefix) { - return startsWith( *s.inner, prefix ); -} - -bool startsWith(const string & s, const char * prefix, size_t prefixsize) { - return startsWith( *s.inner, prefix, prefixsize ); -} - -bool endsWith(const string & s, const string & suffix) { - return endsWith( *s.inner, *suffix.inner ); -} - -bool endsWith(const string & s, const char * suffix) { - return endsWith( *s.inner, suffix ); -} - -bool endsWith(const string & s, const char * suffix, size_t suffixsize) { - return endsWith( *s.inner, suffix, suffixsize ); -} - - -/////////////////////////////////////////////////////////////////////////// -// charclass, include, exclude - -void ?{}( charclass & this, const string & chars) { - (this.inner) { malloc() }; - ?{}( *this.inner, *(const string_res *)chars.inner ); -} - -void ?{}( charclass & this, const char * chars ) { - (this.inner) { malloc() }; - ?{}( *this.inner, chars ); -} - -void ?{}( charclass & this, const char * chars, size_t charssize ) { - (this.inner) { malloc() }; - ?{}( *this.inner, chars, charssize ); -} - -void ^?{}( charclass & this ) { - ^(*this.inner){}; - free( this.inner ); - this.inner = 0p; -} - - -int exclude(const string & s, const charclass & mask) { - return exclude( *s.inner, *mask.inner ); -} -/* -StrSlice exclude(string & s, const charclass & mask) { -} -*/ - -int include(const string & s, const charclass & mask) { - return include( *s.inner, *mask.inner ); -} - -/* -StrSlice include(string & s, const charclass & mask) { -} -*/ - Index: libcfa/src/containers/string.hfa =================================================================== --- libcfa/src/containers/string.hfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ (revision ) @@ -1,184 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// string -- variable-length, mutable run of text, with value semantics -// -// Author : Michael L. Brooks -// Created On : Fri Sep 03 11:00:00 2021 -// Last Modified By : Peter A. Buhr -// Last Modified On : Mon Aug 28 18:32:59 2023 -// Update Count : 40 -// - -#pragma once - -#include - - -// in string_res.hfa -struct string_res; -struct charclass_res; - -struct string { - string_res * inner; -}; - -// Getters -size_t size(const string & s); - -// RAII, assignment -void ?{}(string & this); // empty string -void ?{}(string & s, const char * initial); // copy from string literal (NULL-terminated) -void ?{}(string & s, const char * buffer, size_t bsize); // copy specific length from buffer - -void ?{}(string & s, const string & s2); -void ?{}(string & s, string & s2); - -void ?=?(string & s, const char * other); // copy assignment from literal -void ?=?(string & s, const string & other); -void ?=?(string & s, char other); -string & ?=?(string & s, string & other); // surprising ret seems to help avoid calls to autogen -//string ?=?( string &, string ) = void; -void ^?{}(string & s); - -// Alternate construction: request shared edits -struct string_WithSharedEdits { - string * s; -}; -string_WithSharedEdits ?`shareEdits( string & this ); -void ?{}( string & this, string_WithSharedEdits src ); - -// IO Operator -ofstream & ?|?(ofstream & out, const string & s); -void ?|?(ofstream & out, const string & s); -ifstream & ?|?(ifstream & in, string & s); -void ?|?( ifstream & in, string & this ); - - -struct _Istream_str { - string & s; - union { - const char * scanset; - char delimit[2]; - }; - int rwd; // read width - union { - unsigned char all; - struct { - unsigned char ignore:1; // do not change input argument - unsigned char inex:1; // include/exclude characters in scanset - unsigned char delimit:1; // delimit character - unsigned char rwd:1; // read width - } flags; - }; -}; // _Istream_str - -static inline { - // read width does not include null terminator - _Istream_str wdi( unsigned int rwd, string & s ) { return (_Istream_str)@{ s, {0p}, rwd, {.flags.rwd : true} }; } - _Istream_str skip( const char scanset[] ) { return (_Istream_str)@{ *0p, {scanset}, -1, {.all : 0} }; } - _Istream_str skip( unsigned int wd ) { return (_Istream_str)@{ *0p, {0p}, wd, {.all : 0} }; } - _Istream_str getline( string & s, const char delimit = '\n' ) { - return (_Istream_str)@{ s, {.delimit : { delimit, '\0' } }, -1, {.flags.delimit : true, .flags.inex : true} }; - } - _Istream_str & getline( _Istream_str & fmt, const char delimit = '\n' ) { - fmt.delimit[0] = delimit; fmt.delimit[1] = '\0'; fmt.flags.delimit = true; fmt.flags.inex = true; return fmt; - } - _Istream_str incl( const char scanset[], string & s ) { return (_Istream_str)@{ s, {scanset}, -1, {.flags.inex : false} }; } - _Istream_str & incl( const char scanset[], _Istream_str & fmt ) { fmt.scanset = scanset; fmt.flags.inex = false; return fmt; } - _Istream_str excl( const char scanset[], string & s ) { return (_Istream_str)@{ s, {scanset}, -1, {.flags.inex : true} }; } - _Istream_str & excl( const char scanset[], _Istream_str & fmt ) { fmt.scanset = scanset; fmt.flags.inex = true; return fmt; } - _Istream_str ignore( string & s ) { return (_Istream_str)@{ s, {0p}, -1, {.flags.ignore : true} }; } - _Istream_str & ignore( _Istream_str & fmt ) { fmt.flags.ignore = true; return fmt; } -} // distribution -ifstream & ?|?( ifstream & is, _Istream_str f ); -void ?|?( ifstream & is, _Istream_str t ); -void getline( ifstream & in, string & this, const char delimit = '\n' ); - -// Concatenation -void ?+=?(string & s, char other); // append a character -void ?+=?(string & s, const string & s2); // append-concatenate to first string -void ?+=?(string & s, const char * other); // append-concatenate to first string -string ?+?(const string & s, char other); // add a character to a copy of the string -string ?+?(const string & s, const string & s2); // copy and concatenate both strings -string ?+?(const char * s1, const char * s2); // concatenate both strings -string ?+?(const string & s, const char * other); // copy and concatenate with NULL-terminated string - -// Repetition -string ?*?(const string & s, size_t factor); -string ?*?(char c, size_t size); -string ?*?(const char *s, size_t size); - -// Character access -char ?[?](const string & s, size_t index); -string ?[?](string & s, size_t index); // mutable length-1 slice of original -//char codePointAt(const string & s, size_t index); // to revisit under Unicode - -// Comparisons -bool ?==?(const string & s, const string & other); -bool ?!=?(const string & s, const string & other); -bool ?==?(const string & s, const char * other); -bool ?!=?(const string & s, const char * other); - -// Slicing -string ?()( string & this, size_t start, size_t end ); // TODO const? -string ?()( string & this, size_t start); - -// String search -bool contains(const string & s, char ch); // single character - -int find(const string & s, char search); -int find(const string & s, const string & search); -int find(const string & s, const char * search); -int find(const string & s, const char * search, size_t searchsize); - -int findFrom(const string & s, size_t fromPos, char search); -int findFrom(const string & s, size_t fromPos, const string & search); -int findFrom(const string & s, size_t fromPos, const char * search); -int findFrom(const string & s, size_t fromPos, const char * search, size_t searchsize); - -bool includes(const string & s, const string & search); -bool includes(const string & s, const char * search); -bool includes(const string & s, const char * search, size_t searchsize); - -bool startsWith(const string & s, const string & prefix); -bool startsWith(const string & s, const char * prefix); -bool startsWith(const string & s, const char * prefix, size_t prefixsize); - -bool endsWith(const string & s, const string & suffix); -bool endsWith(const string & s, const char * suffix); -bool endsWith(const string & s, const char * suffix, size_t suffixsize); - -// Modifiers -void padStart(string & s, size_t n); -void padStart(string & s, size_t n, char padding); -void padEnd(string & s, size_t n); -void padEnd(string & s, size_t n, char padding); - - - -struct charclass { - charclass_res * inner; -}; - -void ?{}( charclass & ) = void; -void ?{}( charclass &, charclass) = void; -charclass ?=?( charclass &, charclass) = void; - -void ?{}( charclass &, const string & chars); -void ?{}( charclass &, const char * chars ); -void ?{}( charclass &, const char * chars, size_t charssize ); -void ^?{}( charclass & ); - -int include(const string & s, const charclass & mask); - -int exclude(const string & s, const charclass & mask); - -/* -What to do with? -StrRet include(string & s, const charclass & mask); -StrRet exclude(string & s, const charclass & mask); -*/ Index: libcfa/src/containers/string_res.cfa =================================================================== --- libcfa/src/containers/string_res.cfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ (revision ) @@ -1,1130 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// string_res -- variable-length, mutable run of text, with resource semantics -// -// Author : Michael L. Brooks -// Created On : Fri Sep 03 11:00:00 2021 -// Last Modified By : Peter A. Buhr -// Last Modified On : Mon Aug 14 18:06:01 2023 -// Update Count : 12 -// - -#include "string_res.hfa" -#include "string_sharectx.hfa" -#include "stdlib.hfa" -#include - -// Workaround for observed performance penalty from calling CFA's alloc. -// Workaround is: EndVbyte = TEMP_ALLOC(char, CurrSize) -// Should be: EndVbyte = alloc(CurrSize) -#define TEMP_ALLOC(T, n) (( T* ) malloc( n * sizeof( T ) )) - -#include - -//######################### VbyteHeap "header" ######################### - -#ifdef VbyteDebug -HandleNode *HeaderPtr; -#endif // VbyteDebug - -struct VbyteHeap { - - int NoOfCompactions; // number of compactions of the byte area - int NoOfExtensions; // number of extensions in the size of the byte area - int NoOfReductions; // number of reductions in the size of the byte area - - int InitSize; // initial number of bytes in the byte-string area - int CurrSize; // current number of bytes in the byte-string area - char *StartVbyte; // pointer to the `st byte of the start of the byte-string area - char *EndVbyte; // pointer to the next byte after the end of the currently used portion of byte-string area - void *ExtVbyte; // pointer to the next byte after the end of the byte-string area - - HandleNode Header; // header node for handle list -}; // VbyteHeap - - -static void compaction( VbyteHeap & ); // compaction of the byte area -static void garbage( VbyteHeap &, int ); // garbage collect the byte area -static void extend( VbyteHeap &, int ); // extend the size of the byte area -static void reduce( VbyteHeap &, int ); // reduce the size of the byte area - -static void ?{}( VbyteHeap &, size_t = 1000 ); -static void ^?{}( VbyteHeap & ); - -static int ByteCmp( char *, int, int, char *, int, int ); // compare 2 blocks of bytes -static char *VbyteAlloc( VbyteHeap &, int ); // allocate a block bytes in the heap -static char *VbyteTryAdjustLast( VbyteHeap &, int ); - -static void AddThisAfter( HandleNode &, HandleNode & ); -static void DeleteNode( HandleNode & ); -static void MoveThisAfter( HandleNode &, const HandleNode & ); // move current handle after parameter handle - - -// Allocate the storage for the variable sized area and intialize the heap variables. - -static void ?{}( VbyteHeap & this, size_t Size ) with(this) { -#ifdef VbyteDebug - serr | "enter:VbyteHeap::VbyteHeap, this:" | &this | " Size:" | Size; -#endif // VbyteDebug - NoOfCompactions = NoOfExtensions = NoOfReductions = 0; - InitSize = CurrSize = Size; - StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize); - ExtVbyte = (void *)( StartVbyte + CurrSize ); - Header.flink = Header.blink = &Header; - Header.ulink = & this; -#ifdef VbyteDebug - HeaderPtr = &Header; - serr | "exit:VbyteHeap::VbyteHeap, this:" | &this; -#endif // VbyteDebug -} // VbyteHeap - - -// Release the dynamically allocated storage for the byte area. - -static void ^?{}( VbyteHeap & this ) with(this) { - free( StartVbyte ); -} // ~VbyteHeap - - -//######################### HandleNode ######################### - - -// Create a handle node. The handle is not linked into the handle list. This is the responsibilitiy of the handle -// creator. - -static void ?{}( HandleNode & this ) with(this) { -#ifdef VbyteDebug - serr | "enter:HandleNode::HandleNode, this:" | &this; -#endif // VbyteDebug - s = 0; - lnth = 0; -#ifdef VbyteDebug - serr | "exit:HandleNode::HandleNode, this:" | &this; -#endif // VbyteDebug -} // HandleNode - -// Create a handle node. The handle is linked into the handle list at the end. This means that this handle will NOT be -// in order by string address, but this is not a problem because a string with length zero does nothing during garbage -// collection. - -static void ?{}( HandleNode & this, VbyteHeap & vh ) with(this) { -#ifdef VbyteDebug - serr | "enter:HandleNode::HandleNode, this:" | &this; -#endif // VbyteDebug - s = 0; - lnth = 0; - ulink = &vh; - AddThisAfter( this, *vh.Header.blink ); -#ifdef VbyteDebug - serr | "exit:HandleNode::HandleNode, this:" | &this; -#endif // VbyteDebug -} // HandleNode - - -// Delete a node from the handle list by unchaining it from the list. If the handle node was allocated dynamically, it -// is the responsibility of the creator to destroy it. - -static void ^?{}( HandleNode & this ) with(this) { -#ifdef VbyteDebug - serr | "enter:HandleNode::~HandleNode, this:" | & this; - { - serr | nlOff; - serr | " lnth:" | lnth | " s:" | (void *)s | ",\""; - for ( i; lnth ) { - serr | s[i]; - } // for - serr | "\" flink:" | flink | " blink:" | blink | nl; - serr | nlOn; - } -#endif // VbyteDebug - DeleteNode( this ); -} // ~HandleNode - - -//######################### String Sharing Context ######################### - -static string_sharectx * ambient_string_sharectx; // fickle top of stack -static string_sharectx default_string_sharectx = {NEW_SHARING}; // stable bottom of stack - -void ?{}( string_sharectx & this, StringSharectx_Mode mode ) with( this ) { - (older){ ambient_string_sharectx }; - if ( mode == NEW_SHARING ) { - (activeHeap){ new( (size_t) 1000 ) }; - } else { - verify( mode == NO_SHARING ); - (activeHeap){ 0p }; - } - ambient_string_sharectx = & this; -} - -void ^?{}( string_sharectx & this ) with( this ) { - if ( activeHeap ) delete( activeHeap ); - - // unlink this from older-list starting from ambient_string_sharectx - // usually, this==ambient_string_sharectx and the loop runs zero times - string_sharectx *& c = ambient_string_sharectx; - while ( c != &this ) &c = &c->older; // find this - c = this.older; // unlink -} - -//######################### String Resource ######################### - - -VbyteHeap * DEBUG_string_heap() { - assert( ambient_string_sharectx->activeHeap && "No sharing context is active" ); - return ambient_string_sharectx->activeHeap; -} - -size_t DEBUG_string_bytes_avail_until_gc( VbyteHeap * heap ) { - return ((char*)heap->ExtVbyte) - heap->EndVbyte; -} - -size_t DEBUG_string_bytes_in_heap( VbyteHeap * heap ) { - return heap->CurrSize; -} - -const char * DEBUG_string_heap_start( VbyteHeap * heap ) { - return heap->StartVbyte; -} - -// Returns the size of the string in bytes -size_t size(const string_res &s) with(s) { - return Handle.lnth; -} - -// Output operator -ofstream & ?|?(ofstream &out, const string_res &s) { - // CFA string is NOT null terminated, so print exactly lnth characters in a minimum width of 0. - out | wd( 0, s.Handle.lnth, s.Handle.s ) | nonl; - return out; -} - -void ?|?(ofstream &out, const string_res &s) { - (ofstream &)(out | s); ends( out ); -} - -// Input operator -ifstream & ?|?(ifstream &in, string_res &s) { - - // Reading into a temp before assigning to s is near zero overhead in typical cases because of sharing. - // If s is a substring of something larger, simple assignment takes care of that case correctly. - // But directly reading a variable amount of text into the middle of a larger context is not practical. - string_res temp; - - // Read in chunks. Often, one chunk is enough. Keep the string that accumulates chunks last in the heap, - // so available room is rest of heap. When a chunk fills the heap, force growth then take the next chunk. - for (;;) { - // Append dummy content to temp, forcing expansion when applicable (occurs always on subsequent loops) - // length 2 ensures room for at least one real char, plus scanf/pipe-cstr's null terminator - temp += "--"; - assert( temp.Handle.ulink->EndVbyte == temp.Handle.s + temp.Handle.lnth ); // last in heap - - // reset, to overwrite the appended "--" - temp.Handle.lnth -= 2; - temp.Handle.ulink->EndVbyte -= 2; - - // rest of heap, less 1 byte for null terminator, is available to read into - int lenReadable = (char*)temp.Handle.ulink->ExtVbyte - temp.Handle.ulink->EndVbyte - 1; - assert (lenReadable >= 1); - - // get bytes - in | wdi( lenReadable + 1, lenReadable, temp.Handle.ulink->EndVbyte ); - int lenWasRead = strlen(temp.Handle.ulink->EndVbyte); - - // update metadata - temp.Handle.lnth += lenWasRead; - temp.Handle.ulink->EndVbyte += lenWasRead; - - if (lenWasRead < lenReadable) break; - } - - s = temp; - return in; -} - - -// Empty constructor -void ?{}(string_res &s) with(s) { - if( ambient_string_sharectx->activeHeap ) { - (Handle){ * ambient_string_sharectx->activeHeap }; - (shareEditSet_owns_ulink){ false }; - verify( Handle.s == 0p && Handle.lnth == 0 ); - } else { - (Handle){ * new( (size_t) 10 ) }; // TODO: can I lazily avoid allocating for empty string - (shareEditSet_owns_ulink){ true }; - Handle.s = Handle.ulink->StartVbyte; - verify( Handle.lnth == 0 ); - } - s.shareEditSet_prev = &s; - s.shareEditSet_next = &s; -} - -static void eagerCopyCtorHelper(string_res &s, const char* rhs, size_t rhslnth) with(s) { - if( ambient_string_sharectx->activeHeap ) { - (Handle){ * ambient_string_sharectx->activeHeap }; - (shareEditSet_owns_ulink){ false }; - } else { - (Handle){ * new( rhslnth ) }; - (shareEditSet_owns_ulink){ true }; - } - Handle.s = VbyteAlloc(*Handle.ulink, rhslnth); - Handle.lnth = rhslnth; - memmove( Handle.s, rhs, rhslnth ); - s.shareEditSet_prev = &s; - s.shareEditSet_next = &s; -} - -// Constructor from a raw buffer and size -void ?{}(string_res &s, const char* rhs, size_t rhslnth) with(s) { - eagerCopyCtorHelper(s, rhs, rhslnth); -} - -// private ctor (not in header): use specified heap (ignore ambient) and copy chars in -void ?{}( string_res &s, VbyteHeap & heap, const char* rhs, size_t rhslnth ) with(s) { - (Handle){ heap }; - Handle.s = VbyteAlloc(*Handle.ulink, rhslnth); - Handle.lnth = rhslnth; - (s.shareEditSet_owns_ulink){ false }; - memmove( Handle.s, rhs, rhslnth ); - s.shareEditSet_prev = &s; - s.shareEditSet_next = &s; -} - -// General copy constructor -void ?{}(string_res &s, const string_res & s2, StrResInitMode mode, size_t start, size_t end ) { - - verify( start <= end && end <= s2.Handle.lnth ); - - if (s2.Handle.ulink != ambient_string_sharectx->activeHeap && mode == COPY_VALUE) { - // crossing heaps (including private): copy eagerly - eagerCopyCtorHelper(s, s2.Handle.s + start, end - start); - verify(s.shareEditSet_prev == &s); - verify(s.shareEditSet_next == &s); - } else { - (s.Handle){}; - s.Handle.s = s2.Handle.s + start; - s.Handle.lnth = end - start; - s.Handle.ulink = s2.Handle.ulink; - - AddThisAfter(s.Handle, s2.Handle ); // insert this handle after rhs handle - // ^ bug? skip others at early point in string - - if (mode == COPY_VALUE) { - verify(s2.Handle.ulink == ambient_string_sharectx->activeHeap); - // requested logical copy in same heap: defer copy until write - - (s.shareEditSet_owns_ulink){ false }; - - // make s alone in its shareEditSet - s.shareEditSet_prev = &s; - s.shareEditSet_next = &s; - } else { - verify( mode == SHARE_EDITS ); - // sharing edits with source forces same heap as source (ignore context) - - (s.shareEditSet_owns_ulink){ s2.shareEditSet_owns_ulink }; - - // s2 is logically const but not implementation const - string_res & s2mod = (string_res &) s2; - - // insert s after s2 on shareEditSet - s.shareEditSet_next = s2mod.shareEditSet_next; - s.shareEditSet_prev = &s2mod; - s.shareEditSet_next->shareEditSet_prev = &s; - s.shareEditSet_prev->shareEditSet_next = &s; - } - } -} - -static void assignEditSet(string_res & this, string_res * shareEditSetStartPeer, string_res * shareEditSetEndPeer, - char * resultSesStart, - size_t resultSesLnth, - HandleNode * resultPadPosition, size_t bsize ) { - - char * beforeBegin = shareEditSetStartPeer->Handle.s; - size_t beforeLen = this.Handle.s - beforeBegin; - - char * afterBegin = this.Handle.s + this.Handle.lnth; - size_t afterLen = shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - afterBegin; - - size_t oldLnth = this.Handle.lnth; - - this.Handle.s = resultSesStart + beforeLen; - this.Handle.lnth = bsize; - if (resultPadPosition) - MoveThisAfter( this.Handle, *resultPadPosition ); - - // adjust all substring string and handle locations, and check if any substring strings are outside the new base string - char *limit = resultSesStart + resultSesLnth; - for ( string_res * p = this.shareEditSet_next; p != &this; p = p->shareEditSet_next ) { - verify (p->Handle.s >= beforeBegin); - if ( p->Handle.s >= afterBegin ) { - verify ( p->Handle.s <= afterBegin + afterLen ); - verify ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen ); - // p starts after the edit - // take start and end as end-anchored - size_t startOffsetFromEnd = afterBegin + afterLen - p->Handle.s; - p->Handle.s = limit - startOffsetFromEnd; - // p->Handle.lnth unaffected - } else if ( p->Handle.s <= beforeBegin + beforeLen ) { - // p starts before, or at the start of, the edit - if ( p->Handle.s + p->Handle.lnth <= beforeBegin + beforeLen ) { - // p ends before the edit - // take end as start-anchored too - // p->Handle.lnth unaffected - } else if ( p->Handle.s + p->Handle.lnth < afterBegin ) { - // p ends during the edit; p does not include the last character replaced - // clip end of p to end at start of edit - p->Handle.lnth = beforeLen - ( p->Handle.s - beforeBegin ); - } else { - // p ends after the edit - verify ( p->Handle.s + p->Handle.lnth <= afterBegin + afterLen ); - // take end as end-anchored - // stretch-shrink p according to the edit - p->Handle.lnth += this.Handle.lnth; - p->Handle.lnth -= oldLnth; - } - // take start as start-anchored - size_t startOffsetFromStart = p->Handle.s - beforeBegin; - p->Handle.s = resultSesStart + startOffsetFromStart; - } else { - verify ( p->Handle.s < afterBegin ); - // p starts during the edit - verify( p->Handle.s + p->Handle.lnth >= beforeBegin + beforeLen ); - if ( p->Handle.s + p->Handle.lnth < afterBegin ) { - // p ends during the edit; p does not include the last character replaced - // set p to empty string at start of edit - p->Handle.s = this.Handle.s; - p->Handle.lnth = 0; - } else { - // p includes the end of the edit - // clip start of p to start at end of edit - int charsToClip = afterBegin - p->Handle.s; - p->Handle.s = this.Handle.s + this.Handle.lnth; - p->Handle.lnth -= charsToClip; - } - } - if (resultPadPosition) - MoveThisAfter( p->Handle, *resultPadPosition ); // move substring handle to maintain sorted order by string position - } -} - -// traverse the share-edit set (SES) to recover the range of a base string to which `this` belongs -static void locateInShareEditSet( string_res &this, string_res *&shareEditSetStartPeer, string_res *&shareEditSetEndPeer ) { - shareEditSetStartPeer = & this; - shareEditSetEndPeer = & this; - for (string_res * editPeer = this.shareEditSet_next; editPeer != &this; editPeer = editPeer->shareEditSet_next) { - if ( editPeer->Handle.s < shareEditSetStartPeer->Handle.s ) { - shareEditSetStartPeer = editPeer; - } - if ( shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth < editPeer->Handle.s + editPeer->Handle.lnth) { - shareEditSetEndPeer = editPeer; - } - } -} - -static string_res & assign_(string_res &this, const char* buffer, size_t bsize, const string_res & valSrc) { - - string_res * shareEditSetStartPeer; - string_res * shareEditSetEndPeer; - locateInShareEditSet( this, shareEditSetStartPeer, shareEditSetEndPeer ); - - verify( shareEditSetEndPeer->Handle.s >= shareEditSetStartPeer->Handle.s ); - size_t origEditSetLength = shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - shareEditSetStartPeer->Handle.s; - verify( origEditSetLength >= this.Handle.lnth ); - - if ( this.shareEditSet_owns_ulink ) { // assigning to private context - // ok to overwrite old value within LHS - char * prefixStartOrig = shareEditSetStartPeer->Handle.s; - int prefixLen = this.Handle.s - prefixStartOrig; - char * suffixStartOrig = this.Handle.s + this.Handle.lnth; - int suffixLen = shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - suffixStartOrig; - - int delta = bsize - this.Handle.lnth; - if ( char * oldBytes = VbyteTryAdjustLast( *this.Handle.ulink, delta ) ) { - // growing: copy from old to new - char * dest = VbyteAlloc( *this.Handle.ulink, origEditSetLength + delta ); - char *destCursor = dest; memcpy(destCursor, prefixStartOrig, prefixLen); - destCursor += prefixLen; memcpy(destCursor, buffer , bsize ); - destCursor += bsize; memcpy(destCursor, suffixStartOrig, suffixLen); - assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer, - dest, - origEditSetLength + delta, - 0p, bsize); - free( oldBytes ); - } else { - // room is already allocated in-place: bubble suffix and overwite middle - memmove( suffixStartOrig + delta, suffixStartOrig, suffixLen ); - memcpy( this.Handle.s, buffer, bsize ); - - assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer, - shareEditSetStartPeer->Handle.s, - origEditSetLength + delta, - 0p, bsize); - } - - } else if ( // assigning to shared context - this.Handle.lnth == origEditSetLength && // overwriting entire run of SES - & valSrc && // sourcing from a managed string - valSrc.Handle.ulink == this.Handle.ulink ) { // sourcing from same heap - - // SES's result will only use characters from the source string => reuse source - assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer, - valSrc.Handle.s, - valSrc.Handle.lnth, - &((string_res&)valSrc).Handle, bsize); - - } else { - // overwriting a proper substring of some string: mash characters from old and new together (copy on write) - // OR we are importing characters: need to copy eagerly (can't refer to source) - - // full string is from start of shareEditSetStartPeer thru end of shareEditSetEndPeer - // `this` occurs in the middle of it, to be replaced - // build up the new text in `pasting` - - string_res pasting = { - * this.Handle.ulink, // maintain same heap, regardless of context - shareEditSetStartPeer->Handle.s, // start of SES - this.Handle.s - shareEditSetStartPeer->Handle.s }; // length of SES, before this - append( pasting, - buffer, // start of replacement for this - bsize ); // length of replacement for this - append( pasting, - this.Handle.s + this.Handle.lnth, // start of SES after this - shareEditSetEndPeer->Handle.s + shareEditSetEndPeer->Handle.lnth - - (this.Handle.s + this.Handle.lnth) ); // length of SES, after this - - // The above string building can trigger compaction. - // The reference points (that are arguments of the string building) may move during that building. - // From this point on, they are stable. - - assignEditSet(this, shareEditSetStartPeer, shareEditSetEndPeer, - pasting.Handle.s, - pasting.Handle.lnth, - &pasting.Handle, bsize); - } - - return this; -} - -string_res & assign(string_res &this, const char* buffer, size_t bsize) { - return assign_(this, buffer, bsize, *0p); -} - -string_res & ?=?(string_res &s, char other) { - return assign(s, &other, 1); -} - -// Copy assignment operator -string_res & ?=?(string_res & this, const string_res & rhs) with( this ) { - return assign_(this, rhs.Handle.s, rhs.Handle.lnth, rhs); -} - -string_res & ?=?(string_res & this, string_res & rhs) with( this ) { - const string_res & rhs2 = rhs; - return this = rhs2; -} - - -// Destructor -void ^?{}(string_res &s) with(s) { - // much delegated to implied ^VbyteSM - - // sever s from its share-edit peers, if any (four no-ops when already solo) - s.shareEditSet_prev->shareEditSet_next = s.shareEditSet_next; - s.shareEditSet_next->shareEditSet_prev = s.shareEditSet_prev; - // s.shareEditSet_next = &s; - // s.shareEditSet_prev = &s; - - if (shareEditSet_owns_ulink && s.shareEditSet_next == &s) { // last one out - delete( s.Handle.ulink ); - } -} - - -// Returns the character at the given index -// With unicode support, this may be different from just the byte at the given -// offset from the start of the string. -char ?[?](const string_res &s, size_t index) with(s) { - //TODO: Check if index is valid (no exceptions yet) - return Handle.s[index]; -} - -void assignAt(const string_res &s, size_t index, char val) { - string_res editZone = { s, SHARE_EDITS, index, index+1 }; - assign(editZone, &val, 1); -} - - -/////////////////////////////////////////////////////////////////// -// Concatenation - -void append(string_res &str1, const char * buffer, size_t bsize) { - size_t clnth = str1.Handle.lnth + bsize; - if ( str1.Handle.s + str1.Handle.lnth == buffer ) { // already juxtapose ? - // no-op - } else { // must copy some text - if ( str1.Handle.s + str1.Handle.lnth == VbyteAlloc(*str1.Handle.ulink, 0) ) { // str1 at end of string area ? - VbyteAlloc( *str1.Handle.ulink, bsize ); // create room for 2nd part at the end of string area - } else { // copy the two parts - char * str1newBuf = VbyteAlloc( *str1.Handle.ulink, clnth ); - char * str1oldBuf = str1.Handle.s; // must read after VbyteAlloc call in case it gs's - str1.Handle.s = str1newBuf; - memcpy( str1.Handle.s, str1oldBuf, str1.Handle.lnth ); - } // if - memcpy( str1.Handle.s + str1.Handle.lnth, buffer, bsize ); - } // if - str1.Handle.lnth = clnth; -} - -void ?+=?(string_res &str1, const string_res &str2) { - append( str1, str2.Handle.s, str2.Handle.lnth ); -} - -void ?+=?(string_res &s, char other) { - append( s, &other, 1 ); -} - - - - - -////////////////////////////////////////////////////////// -// Comparisons - - -bool ?==?(const string_res &s1, const string_res &s2) { - return ByteCmp( s1.Handle.s, 0, s1.Handle.lnth, s2.Handle.s, 0, s2.Handle.lnth) == 0; -} - -bool ?!=?(const string_res &s1, const string_res &s2) { - return !(s1 == s2); -} -bool ?==?(const string_res &s, const char* other) { - string_res sother = other; - return s == sother; -} -bool ?!=?(const string_res &s, const char* other) { - return !(s == other); -} - - -////////////////////////////////////////////////////////// -// Search - -bool contains(const string_res &s, char ch) { - for ( i; size(s) ) { - if (s[i] == ch) return true; - } - return false; -} - -int find(const string_res &s, char search) { - return findFrom(s, 0, search); -} - -int findFrom(const string_res &s, size_t fromPos, char search) { - // FIXME: This paricular overload (find of single char) is optimized to use memchr. - // The general overload (find of string, memchr applying to its first character) and `contains` should be adjusted to match. - char * searchFrom = s.Handle.s + fromPos; - size_t searchLnth = s.Handle.lnth - fromPos; - int searchVal = search; - char * foundAt = (char *) memchr(searchFrom, searchVal, searchLnth); - if (foundAt == 0p) return s.Handle.lnth; - else return foundAt - s.Handle.s; -} - -int find(const string_res &s, const string_res &search) { - return findFrom(s, 0, search); -} - -int findFrom(const string_res &s, size_t fromPos, const string_res &search) { - return findFrom(s, fromPos, search.Handle.s, search.Handle.lnth); -} - -int find(const string_res &s, const char* search) { - return findFrom(s, 0, search); -} -int findFrom(const string_res &s, size_t fromPos, const char* search) { - return findFrom(s, fromPos, search, strlen(search)); -} - -int find(const string_res &s, const char* search, size_t searchsize) { - return findFrom(s, 0, search, searchsize); -} - -int findFrom(const string_res &s, size_t fromPos, const char* search, size_t searchsize) { - - /* Remaining implementations essentially ported from Sunjay's work */ - - - // FIXME: This is a naive algorithm. We probably want to switch to someting - // like Boyer-Moore in the future. - // https://en.wikipedia.org/wiki/String_searching_algorithm - - // Always find the empty string - if (searchsize == 0) { - return 0; - } - - for ( i; fromPos ~ s.Handle.lnth ) { - size_t remaining = s.Handle.lnth - i; - // Never going to find the search string if the remaining string is - // smaller than search - if (remaining < searchsize) { - break; - } - - bool matched = true; - for ( j; searchsize ) { - if (search[j] != s.Handle.s[i + j]) { - matched = false; - break; - } - } - if (matched) { - return i; - } - } - - return s.Handle.lnth; -} - -bool includes(const string_res &s, const string_res &search) { - return includes(s, search.Handle.s, search.Handle.lnth); -} - -bool includes(const string_res &s, const char* search) { - return includes(s, search, strlen(search)); -} - -bool includes(const string_res &s, const char* search, size_t searchsize) { - return find(s, search, searchsize) < s.Handle.lnth; -} - -bool startsWith(const string_res &s, const string_res &prefix) { - return startsWith(s, prefix.Handle.s, prefix.Handle.lnth); -} - -bool startsWith(const string_res &s, const char* prefix) { - return startsWith(s, prefix, strlen(prefix)); -} - -bool startsWith(const string_res &s, const char* prefix, size_t prefixsize) { - if (s.Handle.lnth < prefixsize) { - return false; - } - return memcmp(s.Handle.s, prefix, prefixsize) == 0; -} - -bool endsWith(const string_res &s, const string_res &suffix) { - return endsWith(s, suffix.Handle.s, suffix.Handle.lnth); -} - -bool endsWith(const string_res &s, const char* suffix) { - return endsWith(s, suffix, strlen(suffix)); -} - -bool endsWith(const string_res &s, const char* suffix, size_t suffixsize) { - if (s.Handle.lnth < suffixsize) { - return false; - } - // Amount to offset the bytes pointer so that we are comparing the end of s - // to suffix. s.bytes + offset should be the first byte to compare against suffix - size_t offset = s.Handle.lnth - suffixsize; - return memcmp(s.Handle.s + offset, suffix, suffixsize) == 0; -} - - /* Back to Mike's work */ - - -/////////////////////////////////////////////////////////////////////////// -// charclass, include, exclude - -void ?{}( charclass_res & this, const string_res & chars) { - (this){ chars.Handle.s, chars.Handle.lnth }; -} - -void ?{}( charclass_res & this, const char * chars ) { - (this){ chars, strlen(chars) }; -} - -void ?{}( charclass_res & this, const char * chars, size_t charssize ) { - (this.chars){ chars, charssize }; - // now sort it ? -} - -void ^?{}( charclass_res & this ) { - ^(this.chars){}; -} - -static bool test( const charclass_res & mask, char c ) { - // instead, use sorted char list? - return contains( mask.chars, c ); -} - -int exclude(const string_res &s, const charclass_res &mask) { - for ( i; size(s) ) { - if ( test(mask, s[i]) ) return i; - } - return size(s); -} - -int include(const string_res &s, const charclass_res &mask) { - for ( i; size(s) ) { - if ( ! test(mask, s[i]) ) return i; - } - return size(s); -} - -//######################### VbyteHeap "implementation" ######################### - - -// Add a new HandleNode node n after the current HandleNode node. - -static void AddThisAfter( HandleNode & this, HandleNode & n ) with(this) { -#ifdef VbyteDebug - serr | "enter:AddThisAfter, this:" | &this | " n:" | &n; -#endif // VbyteDebug - // Performance note: we are on the critical path here. MB has ensured that the verifies don't contribute to runtime (are compiled away, like they're supposed to be). - verify( n.ulink != 0p ); - verify( this.ulink == n.ulink ); - flink = n.flink; - blink = &n; - n.flink->blink = &this; - n.flink = &this; -#ifdef VbyteDebug - { - serr | "HandleList:"; - serr | nlOff; - for ( HandleNode *ni = HeaderPtr->flink; ni != HeaderPtr; ni = ni->flink ) { - serr | "\tnode:" | ni | " lnth:" | ni->lnth | " s:" | (void *)ni->s | ",\""; - for ( i; ni->lnth ) { - serr | ni->s[i]; - } // for - serr | "\" flink:" | ni->flink | " blink:" | ni->blink | nl; - } // for - serr | nlOn; - } - serr | "exit:AddThisAfter"; -#endif // VbyteDebug -} // AddThisAfter - - -// Delete the current HandleNode node. - -static void DeleteNode( HandleNode & this ) with(this) { -#ifdef VbyteDebug - serr | "enter:DeleteNode, this:" | &this; -#endif // VbyteDebug - flink->blink = blink; - blink->flink = flink; -#ifdef VbyteDebug - serr | "exit:DeleteNode"; -#endif // VbyteDebug -} // DeleteNode - - - -// Allocates specified storage for a string from byte-string area. If not enough space remains to perform the -// allocation, the garbage collection routine is called. - -static char * VbyteAlloc( VbyteHeap & this, int size ) with(this) { -#ifdef VbyteDebug - serr | "enter:VbyteAlloc, size:" | size; -#endif // VbyteDebug - uintptr_t NoBytes; - char *r; - - NoBytes = ( uintptr_t )EndVbyte + size; - if ( NoBytes > ( uintptr_t )ExtVbyte ) { // enough room for new byte-string ? - garbage( this, size ); // firer up the garbage collector - verify( (( uintptr_t )EndVbyte + size) <= ( uintptr_t )ExtVbyte && "garbage run did not free up required space" ); - } // if - r = EndVbyte; - EndVbyte += size; -#ifdef VbyteDebug - serr | "exit:VbyteAlloc, r:" | (void *)r | " EndVbyte:" | (void *)EndVbyte | " ExtVbyte:" | ExtVbyte; -#endif // VbyteDebug - return r; -} // VbyteAlloc - - -// Adjusts the last allocation in this heap by delta bytes, or resets this heap to be able to offer -// new allocations of its original size + delta bytes. Positive delta means bigger; -// negative means smaller. A null return indicates that the original heap location has room for -// the requested growth. A non-null return indicates that copying to a new location is required -// but has not been done; the returned value is the old heap storage location; `this` heap is -// modified to reference the new location. In the copy-requred case, the caller should use -// VbyteAlloc to claim the new space, while doing optimal copying from old to new, then free old. - -static char * VbyteTryAdjustLast( VbyteHeap & this, int delta ) with(this) { - - if ( ( uintptr_t )EndVbyte + delta <= ( uintptr_t )ExtVbyte ) { - // room available - EndVbyte += delta; - return 0p; - } - - char *oldBytes = StartVbyte; - - NoOfExtensions += 1; - CurrSize *= 2; - StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize); - ExtVbyte = StartVbyte + CurrSize; - - return oldBytes; -} - - -// Move an existing HandleNode node h somewhere after the current HandleNode node so that it is in ascending order by -// the address in the byte string area. - -static void MoveThisAfter( HandleNode & this, const HandleNode & h ) with(this) { -#ifdef VbyteDebug - serr | "enter:MoveThisAfter, this:" | & this | " h:" | & h; -#endif // VbyteDebug - verify( h.ulink != 0p ); - verify( this.ulink == h.ulink ); - if ( s < h.s ) { // check argument values - // serr | "VbyteSM: Error - Cannot move byte string starting at:" | s | " after byte string starting at:" - // | ( h->s ) | " and keep handles in ascending order"; - // exit(-1 ); - verify( 0 && "VbyteSM: Error - Cannot move byte strings as requested and keep handles in ascending order"); - } // if - - HandleNode *i; - for ( i = h.flink; i->s != 0 && s > ( i->s ); i = i->flink ); // find the position for this node after h - if ( & this != i->blink ) { - DeleteNode( this ); - AddThisAfter( this, *i->blink ); - } // if -#ifdef VbyteDebug - { - serr | "HandleList:"; - serr | nlOff; - for ( HandleNode *n = HeaderPtr->flink; n != HeaderPtr; n = n->flink ) { - serr | "\tnode:" | n | " lnth:" | n->lnth | " s:" | (void *)n->s | ",\""; - for ( i; n->lnth ) { - serr | n->s[i]; - } // for - serr | "\" flink:" | n->flink | " blink:" | n->blink | nl; - } // for - serr | nlOn; - } - serr | "exit:MoveThisAfter"; -#endif // VbyteDebug -} // MoveThisAfter - - - - - -//######################### VbyteHeap ######################### - -// Compare two byte strings in the byte-string area. The routine returns the following values: -// -// 1 => Src1-byte-string > Src2-byte-string -// 0 => Src1-byte-string = Src2-byte-string -// -1 => Src1-byte-string < Src2-byte-string - -int ByteCmp( char *Src1, int Src1Start, int Src1Lnth, char *Src2, int Src2Start, int Src2Lnth ) { -#ifdef VbyteDebug - serr | "enter:ByteCmp, Src1Start:" | Src1Start | " Src1Lnth:" | Src1Lnth | " Src2Start:" | Src2Start | " Src2Lnth:" | Src2Lnth; -#endif // VbyteDebug - int cmp; - - CharZip: for ( int i = 0; ; i += 1 ) { - if ( i == Src2Lnth - 1 ) { - for ( ; ; i += 1 ) { - if ( i == Src1Lnth - 1 ) { - cmp = 0; - break CharZip; - } // exit - if ( Src1[Src1Start + i] != ' ') { - // SUSPECTED BUG: this could be be why Peter got the bug report about == " " (why is this case here at all?) - cmp = 1; - break CharZip; - } // exit - } // for - } // exit - if ( i == Src1Lnth - 1 ) { - for ( ; ; i += 1 ) { - if ( i == Src2Lnth - 1 ) { - cmp = 0; - break CharZip; - } // exit - if ( Src2[Src2Start + i] != ' ') { - cmp = -1; - break CharZip; - } // exit - } // for - } // exit - if ( Src2[Src2Start + i] != Src1[Src1Start+ i]) { - cmp = Src1[Src1Start + i] > Src2[Src2Start + i] ? 1 : -1; - break CharZip; - } // exit - } // for -#ifdef VbyteDebug - serr | "exit:ByteCmp, cmp:" | cmp; -#endif // VbyteDebug - return cmp; -} // ByteCmp - - -// The compaction moves all of the byte strings currently in use to the beginning of the byte-string area and modifies -// the handles to reflect the new positions of the byte strings. Compaction assumes that the handle list is in ascending -// order by pointers into the byte-string area. The strings associated with substrings do not have to be moved because -// the containing string has been moved. Hence, they only require that their string pointers be adjusted. - -void compaction(VbyteHeap & this) with(this) { - HandleNode *h; - char *obase, *nbase, *limit; - - NoOfCompactions += 1; - EndVbyte = StartVbyte; - h = Header.flink; // ignore header node - for () { - memmove( EndVbyte, h->s, h->lnth ); - obase = h->s; - h->s = EndVbyte; - nbase = h->s; - EndVbyte += h->lnth; - limit = obase + h->lnth; - h = h->flink; - - // check if any substrings are allocated within a string - - for () { - if ( h == &Header ) break; // end of header list ? - if ( h->s >= limit ) break; // outside of current string ? - h->s = nbase + (( uintptr_t )h->s - ( uintptr_t )obase ); - h = h->flink; - } // for - if ( h == &Header ) break; // end of header list ? - } // for -} // compaction - - -static double heap_expansion_freespace_threshold = 0.1; // default inherited from prior work: expand heap when less than 10% "free" (i.e. garbage) - // probably an unreasonable default, but need to assess early-round tests on changing it - -void TUNING_set_string_heap_liveness_threshold( double val ) { - heap_expansion_freespace_threshold = 1.0 - val; -} - - -// Garbage determines the amount of free space left in the heap and then reduces, leave the same, or extends the size of -// the heap. The heap is then compacted in the existing heap or into the newly allocated heap. - -void garbage(VbyteHeap & this, int minreq ) with(this) { -#ifdef VbyteDebug - serr | "enter:garbage"; - { - serr | "HandleList:"; - for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) { - serr | nlOff; - serr | "\tnode:" | n | " lnth:" | n->lnth | " s:" | (void *)n->s | ",\""; - for ( i; n->lnth ) { - serr | n->s[i]; - } // for - serr | nlOn; - serr | "\" flink:" | n->flink | " blink:" | n->blink; - } // for - } -#endif // VbyteDebug - int AmountUsed, AmountFree; - - AmountUsed = 0; - for ( HandleNode *i = Header.flink; i != &Header; i = i->flink ) { // calculate amount of byte area used - AmountUsed += i->lnth; - } // for - AmountFree = ( uintptr_t )ExtVbyte - ( uintptr_t )StartVbyte - AmountUsed; - - if ( ( double ) AmountFree < ( CurrSize * heap_expansion_freespace_threshold ) || AmountFree < minreq ) { // free space less than threshold or not enough to serve cur request - - extend( this, max( CurrSize, minreq ) ); // extend the heap - - // Peter says, "This needs work before it should be used." - // } else if ( AmountFree > CurrSize / 2 ) { // free space greater than 3 times the initial allocation ? - // reduce(( AmountFree / CurrSize - 3 ) * CurrSize ); // reduce the memory - - // `extend` implies a `compaction` during the copy - - } else { - compaction(this); // in-place - }// if -#ifdef VbyteDebug - { - serr | "HandleList:"; - for ( HandleNode *n = Header.flink; n != &Header; n = n->flink ) { - serr | nlOff; - serr | "\tnode:" | n | " lnth:" | n->lnth | " s:" | (void *)n->s | ",\""; - for ( i; n->lnth ) { - serr | n->s[i]; - } // for - serr | nlOn; - serr | "\" flink:" | n->flink | " blink:" | n->blink; - } // for - } - serr | "exit:garbage"; -#endif // VbyteDebug -} // garbage - -#undef VbyteDebug - - - -// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string -// area is deleted. - -void extend( VbyteHeap & this, int size ) with (this) { -#ifdef VbyteDebug - serr | "enter:extend, size:" | size; -#endif // VbyteDebug - char *OldStartVbyte; - - NoOfExtensions += 1; - OldStartVbyte = StartVbyte; // save previous byte area - - CurrSize += size > InitSize ? size : InitSize; // minimum extension, initial size - StartVbyte = EndVbyte = TEMP_ALLOC(char, CurrSize); - ExtVbyte = (void *)( StartVbyte + CurrSize ); - compaction(this); // copy from old heap to new & adjust pointers to new heap - free( OldStartVbyte ); // release old heap -#ifdef VbyteDebug - serr | "exit:extend, CurrSize:" | CurrSize; -#endif // VbyteDebug -} // extend - -//WIP -#if 0 - -// Extend the size of the byte-string area by creating a new area and copying the old area into it. The old byte-string -// area is deleted. - -void VbyteHeap::reduce( int size ) { -#ifdef VbyteDebug - serr | "enter:reduce, size:" | size; -#endif // VbyteDebug - char *OldStartVbyte; - - NoOfReductions += 1; - OldStartVbyte = StartVbyte; // save previous byte area - - CurrSize -= size; - StartVbyte = EndVbyte = new char[CurrSize]; - ExtVbyte = (void *)( StartVbyte + CurrSize ); - compaction(); // copy from old heap to new & adjust pointers to new heap - delete OldStartVbyte; // release old heap -#ifdef VbyteDebug - serr | "exit:reduce, CurrSize:" | CurrSize; -#endif // VbyteDebug -} // reduce - - -#endif Index: libcfa/src/containers/string_res.hfa =================================================================== --- libcfa/src/containers/string_res.hfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ (revision ) @@ -1,157 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// string_res -- variable-length, mutable run of text, with resource semantics -// -// Author : Michael L. Brooks -// Created On : Fri Sep 03 11:00:00 2021 -// Last Modified By : Peter A. Buhr -// Last Modified On : Sat Aug 12 15:45:47 2023 -// Update Count : 2 -// - -#pragma once - -#include -#include // e.g. strlen - - -//######################### HandleNode ######################### -//private - -struct VbyteHeap; - -struct HandleNode { - HandleNode *flink; // forward link - HandleNode *blink; // backward link - VbyteHeap *ulink; // upward link - - char *s; // pointer to byte string - unsigned int lnth; // length of byte string -}; // HandleNode - -VbyteHeap * DEBUG_string_heap(); -size_t DEBUG_string_bytes_in_heap( VbyteHeap * heap ); -size_t DEBUG_string_bytes_avail_until_gc( VbyteHeap * heap ); -const char * DEBUG_string_heap_start( VbyteHeap * heap ); - -void TUNING_set_string_heap_liveness_threshold( double val ); - -//######################### String ######################### - -// A dynamically-sized string -struct string_res { - HandleNode Handle; // chars, start, end, global neighbours - bool shareEditSet_owns_ulink; - string_res * shareEditSet_prev; - string_res * shareEditSet_next; -}; - - -//######################### charclass_res ######################### - -struct charclass_res { - string_res chars; -}; - -void ?{}( charclass_res & ) = void; -void ?{}( charclass_res &, charclass_res) = void; -charclass_res ?=?( charclass_res &, charclass_res) = void; -void ?{}( charclass_res &, const string_res & chars); -void ?{}( charclass_res &, const char * chars ); -void ?{}( charclass_res &, const char * chars, size_t charssize ); -void ^?{}( charclass_res & ); - - -//######################### String ######################### - -// Getters -size_t size(const string_res &s); - -// Constructors, Assignment Operators, Destructor -void ?{}(string_res &s); // empty string -void ?{}(string_res &s, const char* buffer, size_t bsize); // copy specific length from buffer -static inline void ?{}(string_res &s, const char* rhs) { // copy from string literal (NULL-terminated) - (s){ rhs, strlen(rhs) }; -} - -void ?{}(string_res &s, const string_res & s2) = void; -void ?{}(string_res &s, string_res & s2) = void; - -enum StrResInitMode { COPY_VALUE, SHARE_EDITS }; -void ?{}(string_res &s, const string_res & src, StrResInitMode, size_t start, size_t end ); -static inline void ?{}(string_res &s, const string_res & src, StrResInitMode mode ) { - ?{}( s, src, mode, 0, size(src)); -} - -string_res & assign(string_res &s, const char* buffer, size_t bsize); // copy specific length from buffer -static inline string_res & ?=?(string_res &s, const char* other) { // copy from string literal (NULL-terminated) - return assign(s, other, strlen(other)); -} -string_res & ?=?(string_res &s, const string_res &other); -string_res & ?=?(string_res &s, string_res &other); -string_res & ?=?(string_res &s, char other); - -void ^?{}(string_res &s); - -// IO Operator -ofstream & ?|?(ofstream &out, const string_res &s); -void ?|?(ofstream &out, const string_res &s); -ifstream & ?|?(ifstream &in, string_res &s); - -// Concatenation -void append(string_res &s, const char* buffer, size_t bsize); -void ?+=?(string_res &s, char other); // append a character -void ?+=?(string_res &s, const string_res &s2); // append-concatenate to first string -static inline void ?+=?(string_res &s, const char* other) { - append( s, other, strlen(other) ); -} - -// Character access -void assignAt(const string_res &s, size_t index, char val); -char ?[?](const string_res &s, size_t index); // Mike changed to ret by val from Sunjay's ref, to match Peter's -//char codePointAt(const string_res &s, size_t index); // revisit under Unicode - -// Comparisons -bool ?==?(const string_res &s, const string_res &other); -bool ?!=?(const string_res &s, const string_res &other); -bool ?==?(const string_res &s, const char* other); -bool ?!=?(const string_res &s, const char* other); - -// String search -bool contains(const string_res &s, char ch); // single character - -int find(const string_res &s, char search); -int find(const string_res &s, const string_res &search); -int find(const string_res &s, const char* search); -int find(const string_res &s, const char* search, size_t searchsize); - -int findFrom(const string_res &s, size_t fromPos, char search); -int findFrom(const string_res &s, size_t fromPos, const string_res &search); -int findFrom(const string_res &s, size_t fromPos, const char* search); -int findFrom(const string_res &s, size_t fromPos, const char* search, size_t searchsize); - -bool includes(const string_res &s, const string_res &search); -bool includes(const string_res &s, const char* search); -bool includes(const string_res &s, const char* search, size_t searchsize); - -bool startsWith(const string_res &s, const string_res &prefix); -bool startsWith(const string_res &s, const char* prefix); -bool startsWith(const string_res &s, const char* prefix, size_t prefixsize); - -bool endsWith(const string_res &s, const string_res &suffix); -bool endsWith(const string_res &s, const char* suffix); -bool endsWith(const string_res &s, const char* suffix, size_t suffixsize); - -int include(const string_res &s, const charclass_res &mask); -int exclude(const string_res &s, const charclass_res &mask); - -// Modifiers -void padStart(string_res &s, size_t n); -void padStart(string_res &s, size_t n, char padding); -void padEnd(string_res &s, size_t n); -void padEnd(string_res &s, size_t n, char padding); - Index: libcfa/src/containers/string_sharectx.hfa =================================================================== --- libcfa/src/containers/string_sharectx.hfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ (revision ) @@ -1,60 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// string_sharectx -- utility for controlling string sharing / isolation -// -// Author : Michael L. Brooks -// Created On : Fri Sep 03 11:00:00 2021 -// Last Modified By : Michael L. Brooks -// Last Modified On : Fri Sep 03 11:00:00 2021 -// Update Count : 1 -// - -#pragma once - -#pragma GCC visibility push(default) - -//######################### String Sharing Context ######################### - -struct VbyteHeap; - -// A string_sharectx -// -// Usage: -// void bar() { -// c(); -// string_sharectx c = {NEW_SHARING}; -// d(); -// } -// void foo() { -// a(); -// string_sharectx c = {NO_SHARING}; -// b(); -// bar(); -// e(); -// } -// int main() { -// foo(); -// } -// -// a, d: share string character ranges within themselves, not with each other -// b, c, e: never share anything -// -struct string_sharectx { - // private - VbyteHeap * activeHeap; - string_sharectx * older; -}; - -enum StringSharectx_Mode { NEW_SHARING, NO_SHARING }; - -void ?{}( string_sharectx &, StringSharectx_Mode ); -void ^?{}( string_sharectx & ); - -void ?{}( string_sharectx & ) = void; -void ?{}( string_sharectx &, string_sharectx ) = void; -void ?=?( string_sharectx &, string_sharectx ) = void; - Index: libcfa/src/containers/vector.cfa =================================================================== --- libcfa/src/containers/vector.cfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ (revision ) @@ -1,139 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// vector.c -- -// -// Author : Thierry Delisle -// Created On : Tue Jul 5 18:07:52 2016 -// Last Modified By : Peter A. Buhr -// Last Modified On : Tue Jul 5 18:08:31 2016 -// Update Count : 2 -// - -#include - -#include - -#pragma GCC visibility push(default) - -forall(T, allocator_t | allocator_c(T, allocator_t)) -static void copy_internal(vector(T, allocator_t)* this, vector(T, allocator_t)* other); - -//------------------------------------------------------------------------------ -//Initialization -forall(T, allocator_t | allocator_c(T, allocator_t)) -void ?{}(vector(T, allocator_t)& this) -{ - (this.storage){}; - this.size = 0; -} - -forall(T, allocator_t | allocator_c(T, allocator_t)) -void ?{}(vector(T, allocator_t)& this, vector(T, allocator_t) rhs) -{ - (this.storage){ rhs.storage }; - copy_internal(&this, &rhs); -} - -// forall(T, allocator_t | allocator_c(T, allocator_t)) -// vector(T, allocator_t) ?=?(vector(T, allocator_t)* this, vector(T, allocator_t) rhs) -// { -// (&this->storage){}; -// copy_internal(this, &rhs); -// return *this; -// } - -forall(T, allocator_t | allocator_c(T, allocator_t)) -void ^?{}(vector(T, allocator_t)& this) -{ - clear(&this); - ^(this.storage){}; -} - -//------------------------------------------------------------------------------ -//Modifiers -forall(T, allocator_t | allocator_c(T, allocator_t)) -void push_back(vector(T, allocator_t)* this, T value) -{ - realloc_storage(&this->storage, this->size+1); - data(&this->storage)[this->size] = value; - this->size++; -} - -forall(T, allocator_t | allocator_c(T, allocator_t)) -void pop_back(vector(T, allocator_t)* this) -{ - this->size--; - ^(data(&this->storage)[this->size]){}; -} - -forall(T, allocator_t | allocator_c(T, allocator_t)) -void clear(vector(T, allocator_t)* this) -{ - for(size_t i = 0; i < this->size; i++) - { - ^(data(&this->storage)[this->size]){}; - } - this->size = 0; -} - -//------------------------------------------------------------------------------ -//Internal Helpers - -forall(T, allocator_t | allocator_c(T, allocator_t)) -static void copy_internal(vector(T, allocator_t)* this, vector(T, allocator_t)* other) -{ - this->size = other->size; - for(size_t i = 0; i < this->size; i++) { - (data(&this->storage)[this->size]){ data(&other->storage)[other->size] }; - } -} - -//------------------------------------------------------------------------------ -//Allocator -forall(T) -void ?{}(heap_allocator(T)& this) -{ - this.storage = 0; - this.capacity = 0; -} - -forall(T) -void ?{}(heap_allocator(T)& this, heap_allocator(T) rhs) -{ - this.capacity = rhs.capacity; - this.storage = (T*)realloc((void*)this.storage, this.capacity * sizeof(T)); -} - -forall(T) -heap_allocator(T) ?=?(heap_allocator(T)& this, heap_allocator(T) rhs) -{ - this.capacity = rhs.capacity; - this.storage = (T*)realloc((void*)this.storage, this.capacity * sizeof(T)); - return this; -} - -forall(T) -void ^?{}(heap_allocator(T)& this) -{ - free(this.storage); -} - -forall(T) -inline void realloc_storage(heap_allocator(T)* this, size_t size) -{ - enum { GROWTH_RATE = 2 }; - if(size > this->capacity) - { - this->capacity = GROWTH_RATE * size; - this->storage = (T*)realloc((void*)this->storage, this->capacity * sizeof(T)); - } -} - -// Local Variables: // -// mode: c // -// tab-width: 4 // -// End: // Index: libcfa/src/containers/vector.hfa =================================================================== --- libcfa/src/containers/vector.hfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ (revision ) @@ -1,168 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// vector -- -// -// Author : Thierry Delisle -// Created On : Tue Jul 5 18:00:07 2016 -// Last Modified By : Peter A. Buhr -// Last Modified On : Thu Feb 2 11:41:24 2023 -// Update Count : 5 -// - -#pragma once - -#include - -//------------------------------------------------------------------------------ -//Allocator -forall(T) -struct heap_allocator -{ - T* storage; - size_t capacity; -}; - -forall(T) -void ?{}(heap_allocator(T)& this); - -forall(T) -void ?{}(heap_allocator(T)& this, heap_allocator(T) rhs); - -forall(T) -heap_allocator(T) ?=?(heap_allocator(T)& this, heap_allocator(T) rhs); - -forall(T) -void ^?{}(heap_allocator(T)& this); - -forall(T) -void realloc_storage(heap_allocator(T)* this, size_t size); - -forall(T) -static inline T* data(heap_allocator(T)* this) -{ - return this->storage; -} - -//------------------------------------------------------------------------------ -//Declaration -forall( T, allocator_t ) -trait allocator_c { - void realloc_storage(allocator_t*, size_t); - T* data(allocator_t*); -}; - -forall(T, allocator_t = heap_allocator(T) | allocator_c(T, allocator_t)) -struct vector; - -//------------------------------------------------------------------------------ -//Initialization -forall(T, allocator_t | allocator_c(T, allocator_t)) -void ?{}(vector(T, allocator_t)& this); - -forall(T, allocator_t | allocator_c(T, allocator_t)) -void ?{}(vector(T, allocator_t)& this, vector(T, allocator_t) rhs); - -forall(T, allocator_t | allocator_c(T, allocator_t)) -vector(T, allocator_t) ?=?(vector(T, allocator_t)& this, vector(T, allocator_t) rhs); - -forall(T, allocator_t | allocator_c(T, allocator_t)) -void ^?{}(vector(T, allocator_t)& this); - -forall(T, allocator_t = heap_allocator(T) | allocator_c(T, allocator_t)) -struct vector -{ - allocator_t storage; - size_t size; -}; - -//------------------------------------------------------------------------------ -//Capacity -forall(T, allocator_t | allocator_c(T, allocator_t)) -static inline bool empty(vector(T, allocator_t)* this) -{ - return this->size == 0; -} - -forall(T, allocator_t | allocator_c(T, allocator_t)) -static inline size_t size(vector(T, allocator_t)* this) -{ - return this->size; -} - -forall(T, allocator_t | allocator_c(T, allocator_t)) -static inline void reserve(vector(T, allocator_t)* this, size_t size) -{ - realloc_storage(&this->storage, this->size+1); -} - -//------------------------------------------------------------------------------ -//Element access -forall(T, allocator_t | allocator_c(T, allocator_t)) -static inline T at(vector(T, allocator_t)* this, size_t index) -{ - return data(&this->storage)[index]; -} - -forall(T, allocator_t | allocator_c(T, allocator_t)) -static inline T ?[?](vector(T, allocator_t)* this, size_t index) -{ - return data(&this->storage)[index]; -} - -forall(T, allocator_t | allocator_c(T, allocator_t)) -static inline T front(vector(T, allocator_t)* this) -{ - return data(&this->storage)[0]; -} - -forall(T, allocator_t | allocator_c(T, allocator_t)) -static inline T back(vector(T, allocator_t)* this) -{ - return data(&this->storage)[this->size - 1]; -} - -//------------------------------------------------------------------------------ -//Modifiers -forall(T, allocator_t | allocator_c(T, allocator_t)) -void push_back(vector(T, allocator_t)* this, T value); - -forall(T, allocator_t | allocator_c(T, allocator_t)) -void pop_back(vector(T, allocator_t)* this); - -forall(T, allocator_t | allocator_c(T, allocator_t)) -void clear(vector(T, allocator_t)* this); - -//------------------------------------------------------------------------------ -//Iterators -forall(T, allocator_t | allocator_c(T, allocator_t)) -static inline T* begin(vector(T, allocator_t)* this) -{ - return data(&this->storage); -} - -// forall(T, allocator_t | allocator_c(T, allocator_t)) -// static inline const T* cbegin(const vector(T, allocator_t)* this) -// { -// return data(&this->storage); -// } - -forall(T, allocator_t | allocator_c(T, allocator_t)) -static inline T* end(vector(T, allocator_t)* this) -{ - return data(&this->storage) + this->size; -} - -// forall(T, allocator_t | allocator_c(T, allocator_t)) -// static inline const T* cend(const vector(T, allocator_t)* this) -// { -// return data(&this->storage) + this->size; -// } - -// Local Variables: // -// mode: c // -// tab-width: 4 // -// End: // Index: libcfa/src/containers/vector2.hfa =================================================================== --- libcfa/src/containers/vector2.hfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ (revision ) @@ -1,357 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// vector -- A growable array, with full-service iterators -// -// Author : Michael Brooks -// Created On : Thu Jun 23 22:00:00 2021 -// Last Modified By : Peter A. Buhr -// Last Modified On : Tue Mar 14 08:40:53 2023 -// Update Count : 2 -// - -#pragma once - -#include -#include "list.hfa" - -forall( T ) { - struct vector; - - struct vector_transit { - vector(T) * col_$; - ptrdiff_t idx_$; - }; - - struct vector_exit { - vector(T) * invec_$; - T * item_$; - }; - - struct vector_permit { - vector(T) * invec_$; - T * item_$; - inline dlink(vector_permit(T)); - }; - P9_EMBEDDED(vector_permit(T), dlink(vector_permit(T))) - - struct vector { - T * buffer_first_$; - T * buffer_end_$; - T * elems_first_$; - T * elems_end_$; // wrapped before storing, never == buffer_end_$ - size_t exit_refcount_$; - dlist(vector_permit(T)) live_iters_$; - }; -} - -static inline -forall( T ) { - - // vector - - void ?{}( vector( T ) &, size_t capacity ); - void ^?{}( vector( T ) & ); - - void ?{}( vector( T ) & ) = void; - void ?{}( vector( T ) &, vector( T ) & ) = void; - vector( T ) & ?=?( vector( T ) &, vector( T ) & ) = void; - - // transit - - void ?{}( vector_transit(T) & ) = void; - void ?{}( vector_transit(T) &, vector_transit(T) & ); - void ^?{}( vector_transit(T) & ); - - T ?`val( vector_transit(T) & src ); - void ?=?( vector_transit(T) & dst, T val ); - - // exit - - void ?{}( vector_exit(T) & ) = void; - void ?{}( vector_exit(T) &, vector(T) * ) = void; - - void ^?{}( vector_exit(T) & ); - void ?{}( vector_exit(T) &, vector_transit(T) & ); - void ?{}( vector_exit(T) &, vector_exit(T) & ); - - T ?`val( vector_exit(T) & src ); - void ?=?( vector_exit(T) & dst, T val ); - T & ?=?( T & dst, vector_exit(T) & src ); - void ?*=?( T & dst, vector_exit(T) & src ); - - bool ?`moveNext( vector_exit(T) & it ); - - // permit - - void ?{}( vector_permit(T) & ) = void; - - void ^?{}( vector_permit(T) & ); - void ?{}( vector_permit(T) &, vector_transit(T) & ); - void ?{}( vector_permit(T) &, vector_exit(T) & ); - void ?{}( vector_permit(T) &, vector_permit(T) & ) = void; - - T ?`val( vector_permit(T) & src ); - - // api - - vector_transit(T) push_last( vector( T ) & col, T val ); - vector_transit(T) ?[?]( vector( T ) &, ptrdiff_t ); - vector_exit(T) ?`origin( vector( T ) & ); - size_t ?`capacity( vector(T) & ); - size_t ?`length( vector(T) & ); - - void insert_before( vector( T ) & col, ptrdiff_t idx, T val ); - -} - -static inline -forall( T ) { - - // vector - - void ?{}( vector( T ) & this, size_t capacity ) { - (this.buffer_first_$){ aalloc( capacity ) }; - (this.buffer_end_$){ this.buffer_first_$ + capacity}; - (this.elems_first_$){ 0p }; - (this.elems_end_$){ this.buffer_first_$ }; - (this.exit_refcount_$){ 0 }; - (this.live_iters_$){}; - } - - void ^?{}( vector( T ) & this ) { - assert( this.exit_refcount_$ == 0 ); - free( this.buffer_first_$ ); - this.buffer_first_$ = 0p; - this.buffer_end_$ = 0p; - this.elems_first_$ = 0p; - this.elems_end_$ = 0p; - } - - // transit - - void ?{}( vector_transit(T) & this, vector_transit(T) & other ) { - // call autogen constructor deleted at end of hfa - (this){ other.col_$, other.idx_$ }; - } - - void ^?{}( vector_transit(T) & ) {} - - - vector_transit(T) ?[?]( vector( T ) & vec, ptrdiff_t idx ) { - // call autogen constructor deleted at end of hfa - vector_transit(T) ret = { & vec, idx }; - return ret; - } - - T & findElemMem_$( vector(T) & v, ptrdiff_t idx ) { - size_t len = v`length; - while (idx > len) idx -= len; - while (idx < 0 ) idx += len; - T * ret = v.elems_first_$ + idx; - if (ret < v.buffer_end_$) return *ret; - ret -= (v.buffer_end_$ - v.buffer_first_$); - assert( v.buffer_first_$ <= ret && ret < v.elems_end_$ ); - return *ret; - } - - T ?`val( vector_transit(T) & src ) { - T ret = findElemMem_$( *src.col_$, src.idx_$ ); - return ret; - } - - void ?=?( vector_transit(T) & src, T val ) { - findElemMem_$( *src.col_$, src.idx_$ ) = val; - } - - // exit - - void ?{}( vector_exit(T) & this, vector_transit(T) & src ) { - ( this.invec_$ ){ src.col_$ }; - ( this.item_$ ){ & findElemMem_$( *src.col_$, src.idx_$ ) }; - - this.invec_$->exit_refcount_$ ++; - } - void ?{}( vector_exit(T) & this, vector_exit(T) & src ){ - ( this.invec_$ ){ src.invec_$ }; - ( this.item_$ ){ src.item_$ }; - - this.invec_$->exit_refcount_$ ++; - } - - void ^?{}( vector_exit(T) & it ) { - it.invec_$->exit_refcount_$ --; - } - - T ?`val( vector_exit(T) & src ) { - return *src.item_$; - } - - void ?*=?( T & dst, vector_exit(T) & src ) { - dst = *src.item_$; - } - - bool ?`moveNext( vector_exit(T) & it ) { - if (it.invec_$->elems_first_$ == 0p) { - // vector is empty - assert ( it.item_$ == 0p ); // it was at origin - return false; - } - assert( it.invec_$->elems_first_$ < it.invec_$->elems_end_$ && "can't handle wraparound yet" ); // temporary: must implement - if( it.item_$ == 0p ) { - // moving from origin - it.item_$ = it.invec_$->elems_first_$; - } else { - it.item_$ += 1; - if( it.item_$ > it.invec_$->buffer_end_$ ) - it.item_$ = it.invec_$->buffer_first_$; - } - if ( it.item_$ >= it.invec_$->elems_end_$ ) { - // moving to origin - it.item_$ = 0p; - return false; - } else { - return true; - } - } - - // permit - - void ^?{}( vector_permit(T) & this ) { - remove(this); - } - - void ?{}( vector_permit(T) & this, vector_transit(T) & src ) { - ( this.invec_$ ){ src.col_$ }; - ( this.item_$ ){ & findElemMem_$( *src.col_$, src.idx_$ ) }; - insert_first( src.col_$->live_iters_$, this ); - } - - void ?{}( vector_permit(T) & this, vector_exit(T) & src ) { - ( this.invec_$ ){ src.invec_$ }; - ( this.item_$ ){ src.item_$ }; - insert_first( src.invec_$->live_iters_$, this ); - } - - T ?`val( vector_permit(T) & src ){ - return *src.item_$; - } - - // vec internals - - void grow( vector( T ) & this ) { - size_t newCapacity = 2 * (this.buffer_end_$ - this.buffer_first_$); - T * newItems = aalloc( newCapacity ); - size_t elemCount = this`length; - for ( ptrdiff_t pos = 0; pos < elemCount; pos += 1 ) { - newItems[pos] = findElemMem_$(this, pos); - } - - while ( vector_permit(T) & liveIter = this.live_iters_$`elems; liveIter`moveNext ) { - liveIter.item_$ += (newItems - this.buffer_first_$); - } - - free( this.buffer_first_$ ); - this.buffer_first_$ = newItems; - this.buffer_end_$ = newItems + newCapacity; - this.elems_first_$ = this.buffer_first_$; - this.elems_end_$ = this.buffer_first_$ + elemCount; - assert (this.elems_end_$ < this.buffer_end_$); - } - - // vec api - - vector_transit(T) push_last( vector( T ) & col, T val ) { - assert (col.exit_refcount_$ == 0); - if (col`length >= col`capacity) { - assert (col`length == col`capacity); - grow(col); - } - // call autogen constructor deleted at end of hfa - vector_transit(T) ret = { & col, col`length }; - *col.elems_end_$ = val; - if (col.elems_first_$ == 0p) col.elems_first_$ = col.elems_end_$; - col.elems_end_$ += 1; - if (col.elems_end_$ >= col.buffer_end_$) col.elems_end_$ = col.buffer_first_$; - return ret; - } - - vector_exit(T) ?`origin( vector( T ) & vec ) { - - // private memberwise constructor, deleted from global namespace at end - // autogen constructor would not do the raii - void ?{}( vector_exit(T) & this, vector(T) * invec_$, T * item_$ ) { - ( this.invec_$ ){ invec_$ }; - ( this.item_$ ){ item_$ }; - this.invec_$->exit_refcount_$ ++; - } - - vector_exit(T) ret = { &vec, 0p }; - return ret; - } - - bool inRange_$( T * query, T * from, T * to) { - if (from == to) return false; - if (from < to) return from <= query && query < to; - return query < to || from <= query; - } - - void insert_before( vector( T ) & col, ptrdiff_t idx, T val ) { - assert (col.exit_refcount_$ == 0); - if (col`length >= col`capacity) { - assert (col`length == col`capacity); - grow(col); - } - - T & insertTargetR = findElemMem_$( col, idx ); - T * insertTarget = & insertTargetR; // doesn't work in one line; must be a bug - - // bubble toward back - if ( col.elems_end_$ < insertTarget ) { - // two phases of bubbling, to wrap around - for (T * tgt = col.elems_end_$; tgt > col.buffer_first_$; tgt--) { - *tgt = *(tgt-1); - } - *col.buffer_first_$ = *(col.buffer_end_$ - 1); - for (T * tgt = col.buffer_end_$ - 1; tgt > insertTarget; tgt--) { - *tgt = *(tgt-1); - } - } else { - for (T * tgt = col.elems_end_$; tgt > insertTarget; tgt--) { - *tgt = *(tgt-1); - } - } - - col.elems_end_$ += 1; - if (col.elems_end_$ == col.buffer_end_$) col.elems_end_$ = col.buffer_first_$; - - *insertTarget = val; - - while ( vector_permit(T) & liveIter = col.live_iters_$`elems; liveIter`moveNext ) { - if ( inRange_$(liveIter.item_$, insertTarget, col.elems_end_$) ) { - liveIter.item_$ += 1; - if (liveIter.item_$ >= col.buffer_end_$) liveIter.item_$ = col.buffer_first_$; - } - } - } - - size_t ?`capacity( vector(T) & v ) { - return v.buffer_end_$ - v.buffer_first_$; - } - - size_t ?`length( vector(T) & v ) { - if (v.elems_first_$ == 0p) return 0; - if (v.elems_first_$ < v.elems_end_$ ) return v.elems_end_$ - v.elems_first_$; - return v.buffer_end_$ - v.elems_first_$ + v.elems_end_$ - v.buffer_first_$; - } - - -} // forall T - -forall( T ) { - void ?{}( vector_exit(T) &, vector(T) *, T * ) = void; - void ?{}( vector_transit(T) & this, vector( T ) * col, ptrdiff_t idx ) = void; -} Index: libcfa/src/executor.baseline.txt =================================================================== --- libcfa/src/executor.baseline.txt (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ libcfa/src/executor.baseline.txt (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -5,5 +5,5 @@ #include -#include +#include forall( T & | $dlistable(T, T) ) { Index: libcfa/src/executor.cfa =================================================================== --- libcfa/src/executor.cfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ libcfa/src/executor.cfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -5,5 +5,5 @@ #include -#include +#include forall( T &, TLink& = dlink(T) | embedded(T, TLink, dlink(T)) ) { Index: libcfa/src/iostream.cfa =================================================================== --- libcfa/src/iostream.cfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ libcfa/src/iostream.cfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -10,6 +10,6 @@ // Created On : Wed May 27 17:56:53 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Mon Aug 28 13:36:16 2023 -// Update Count : 1527 +// Last Modified On : Thu Aug 31 11:27:56 2023 +// Update Count : 1545 // @@ -971,22 +971,6 @@ } // if - int check = f.wd - 1; - const char * scanset = f.scanset;; + const char * scanset = f.scanset; if ( f.flags.delimit ) scanset = f.delimit; // getline ? - - // getline - // if ( f.flags.delimit ) { - // enum { size = 32 }; - // char fmtstr[size]; - // snprintf( fmtstr, size, "%%%d[^%c]s", f.wd, f.delimit ); - // if ( ! f.flags.rwd ) f.s[check] = '\0'; // insert sentinel - // int len = fmt( is, fmtstr, f.s ); // read upto delimiter - // if ( ! f.flags.rwd && f.s[check] != '\0' ) // sentinel overwritten ? - // throw (cstring_length){ &cstring_length_vt }; - // if ( len == 0 ) f.s[0] = '\0'; // empty read => argument unchanged => set empty - // // fprintf( stderr, "getline %s %s %d %d %d '%c'\n", fmtstr, f.s, len, f.wd, check, f.s[check] ); - // if ( ! eof( is ) ) fmt( is, "%*c" ); // ignore delimiter - // return is; - // } // if size_t len = 0; @@ -1013,13 +997,15 @@ } // if + int check = f.wd - 1; if ( ! f.flags.rwd ) f.s[check] = '\0'; // insert sentinel len = fmt( is, fmtstr, f.s ); //fprintf( stderr, "KK %s %zd %d %c %s\n", fmtstr, len, check, f.s[check], f.s ); + if ( ! f.flags.rwd && f.s[check] != '\0' ) // sentinel overwritten ? throw (cstring_length){ &cstring_length_vt }; if ( f.flags.delimit ) { // getline ? - if ( len == 0 ) f.s[0] = '\0'; // empty read => argument unchanged => set empty - if ( ! eof( is ) ) fmt( is, "%*c" ); // ignore delimiter + if ( len == 0 ) f.s[0] = '\0'; // empty read => argument unchanged => set empty + if ( ! eof( is ) ) fmt( is, "%*c" ); // ignore delimiter } //if return is; Index: libcfa/src/iostream.hfa =================================================================== --- libcfa/src/iostream.hfa (revision 4269d1b0ba7fe4b45b0a67e4f36421295d8ec009) +++ libcfa/src/iostream.hfa (revision 8a9a3ab0782f6aa24f6f3b5e62fab3409b692eb4) @@ -10,6 +10,6 @@ // Created On : Wed May 27 17:56:53 2015 // Last Modified By : Peter A. Buhr -// Last Modified On : Fri Aug 25 14:55:06 2023 -// Update Count : 535 +// Last Modified On : Thu Aug 31 10:55:35 2023 +// Update Count : 544 // @@ -406,6 +406,5 @@ // *********************************** manipulators *********************************** -struct _Istream_Cstr { - char * s; +struct _Istream_str_base { union { const char * scanset; @@ -422,21 +421,26 @@ } flags; }; +}; // _Istream_str_base + +struct _Istream_Cstr { + char * s; + inline _Istream_str_base; }; // _Istream_Cstr static inline { // width must include room for null terminator - _Istream_Cstr wdi( unsigned int wd, char s[] ) { return (_Istream_Cstr)@{ s, {0p}, wd, {.all : 0} }; } + _Istream_Cstr wdi( unsigned int wd, char s[] ) { return (_Istream_Cstr)@{ s, { {0p}, wd, {.all : 0} } }; } // read width does not include null terminator _Istream_Cstr wdi( unsigned int wd, unsigned int rwd, char s[] ) { if ( wd <= rwd ) throw (cstring_length){ &cstring_length_vt }; - return (_Istream_Cstr)@{ s, {0p}, rwd, {.flags.rwd : true} }; + return (_Istream_Cstr)@{ s, { {0p}, rwd, {.flags.rwd : true} } }; } - _Istream_Cstr skip( const char scanset[] ) { return (_Istream_Cstr)@{ 0p, {scanset}, -1, {.all : 0} }; } - _Istream_Cstr skip( unsigned int wd ) { return (_Istream_Cstr)@{ 0p, {0p}, wd, {.all : 0} }; } + _Istream_Cstr skip( const char scanset[] ) { return (_Istream_Cstr)@{ 0p, { {scanset}, -1, {.all : 0} } }; } + _Istream_Cstr skip( unsigned int wd ) { return (_Istream_Cstr)@{ 0p, { {0p}, wd, {.all : 0} } }; } _Istream_Cstr & getline( _Istream_Cstr & fmt, const char delimit = '\n' ) { fmt.delimit[0] = delimit; fmt.delimit[1] = '\0'; fmt.flags.delimit = true; fmt.flags.inex = true; return fmt; } _Istream_Cstr & incl( const char scanset[], _Istream_Cstr & fmt ) { fmt.scanset = scanset; fmt.flags.inex = false; return fmt; } _Istream_Cstr & excl( const char scanset[], _Istream_Cstr & fmt ) { fmt.scanset = scanset; fmt.flags.inex = true; return fmt; } - _Istream_Cstr ignore( char s[] ) { return (_Istream_Cstr)@{ s, {0p}, -1, {.flags.ignore : true} }; } + _Istream_Cstr ignore( char s[] ) { return (_Istream_Cstr)@{ s, { {0p}, -1, {.flags.ignore : true} } }; } _Istream_Cstr & ignore( _Istream_Cstr & fmt ) { fmt.flags.ignore = true; return fmt; } } // distribution