source: libcfa/src/containers/vector2.hfa @ 9f99799

ADTast-experimentalpthread-emulation
Last change on this file since 9f99799 was 44856ed, checked in by Michael Brooks <mlbrooks@…>, 3 years ago

Baseline "new" vector, with iterators.

Implementation has not had thorough correctness testing, e.g. checking wraparound
behaviours, and at least one such case is commented as unimplemented.

Implementation has not been optimized at the instruction path level, though a basic
iteration performance check has it within 5% of c++ std::vector.

  • Property mode set to 100644
File size: 10.4 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// vector -- A growable array, with full-service iterators
8//
9// Author           : Michael Brooks
10// Created On       : Thu Jun 23 22:00:00 2021
11// Last Modified By : Michael Brooks
12// Last Modified On : Thu Jun 23 22:00:00 2021
13// Update Count     : 1
14//
15
16#include <stdlib.hfa>
17#include "list.hfa"
18
19forall( T ) {
20    struct vector;
21   
22    struct vector_transit {
23        vector(T) * col_$;
24        ptrdiff_t idx_$;
25    };
26
27    struct vector_exit {
28        vector(T) * invec_$;
29        T * item_$;
30    };
31
32    struct vector_permit {
33        vector(T) * invec_$;
34        T * item_$;
35        inline dlink(vector_permit(T));
36    };
37    P9_EMBEDDED(vector_permit(T), dlink(vector_permit(T)))
38
39    struct vector {
40        T * buffer_first_$;
41        T * buffer_end_$;
42        T * elems_first_$;
43        T * elems_end_$; // wrapped before storing, never == buffer_end_$
44        size_t exit_refcount_$;
45        dlist(vector_permit(T)) live_iters_$;
46    };
47}
48
49static inline
50forall( T ) {
51   
52    // vector
53
54    void ?{}( vector( T ) &, size_t capacity );
55    void ^?{}( vector( T ) & );
56
57    void ?{}( vector( T ) & ) = void;
58    void ?{}( vector( T ) &, vector( T ) & ) = void;
59    vector( T ) & ?=?( vector( T ) &, vector( T ) & ) = void;
60
61    // transit
62
63    void ?{}( vector_transit(T) & ) = void;
64    void ?{}( vector_transit(T) &, vector_transit(T) & );
65    void ^?{}( vector_transit(T) & );
66
67    T ?`val( vector_transit(T) & src );
68    void ?=?( vector_transit(T) & dst, T val );
69
70    // exit
71
72    void ?{}( vector_exit(T) & ) = void;
73    void ?{}( vector_exit(T) &, vector(T) * ) = void;
74
75    void ^?{}( vector_exit(T) & );
76    void ?{}( vector_exit(T) &, vector_transit(T) & );
77    void ?{}( vector_exit(T) &, vector_exit(T) & );
78
79    T ?`val( vector_exit(T) & src );
80    void ?=?( vector_exit(T) & dst, T val );
81    T & ?=?( T & dst, vector_exit(T) & src );
82    void ?*=?( T & dst, vector_exit(T) & src );
83
84    bool ?`moveNext( vector_exit(T) & it );
85
86    // permit
87
88    void ?{}( vector_permit(T) & ) = void;
89
90    void ^?{}( vector_permit(T) & );
91    void ?{}( vector_permit(T) &, vector_transit(T) & );
92    void ?{}( vector_permit(T) &, vector_exit(T) & );
93    void ?{}( vector_permit(T) &, vector_permit(T) & ) = void;
94
95    T ?`val( vector_permit(T) & src );
96
97    // api
98
99    vector_transit(T) push_last( vector( T ) & col, T val );
100    vector_transit(T) ?[?]( vector( T ) &, ptrdiff_t );
101    vector_exit(T) ?`origin( vector( T ) & );
102    size_t ?`capacity( vector(T) & );
103    size_t ?`length( vector(T) & );
104
105    void insert_before( vector( T ) & col, ptrdiff_t idx, T val );
106
107}
108
109static inline
110forall( T ) {
111
112    // vector
113
114    void ?{}( vector( T ) & this, size_t capacity ) {
115        (this.buffer_first_$){ aalloc( capacity ) };
116        (this.buffer_end_$){ this.buffer_first_$ + capacity};
117        (this.elems_first_$){ 0p };
118        (this.elems_end_$){ this.buffer_first_$ };
119        (this.exit_refcount_$){ 0 };
120        (this.live_iters_$){};
121    }
122
123    void ^?{}( vector( T ) & this ) {
124        assert( this.exit_refcount_$ == 0 );
125        free( this.buffer_first_$ );
126        this.buffer_first_$ = 0p;
127        this.buffer_end_$ = 0p;
128        this.elems_first_$ = 0p;
129        this.elems_end_$ = 0p;
130    }
131
132    // transit
133
134    void ?{}( vector_transit(T) & this, vector_transit(T) & other ) {
135        // call autogen constructor deleted at end of hfa
136        (this){ other.col_$, other.idx_$ };
137    }
138
139    void ^?{}( vector_transit(T) & ) {}
140
141
142    vector_transit(T) ?[?]( vector( T ) & vec, ptrdiff_t idx ) {
143        // call autogen constructor deleted at end of hfa
144        vector_transit(T) ret = { & vec, idx };
145        return ret;
146    }
147
148    T & findElemMem_$( vector(T) & v, ptrdiff_t idx ) {
149        size_t len = v`length;
150        while (idx > len) idx -= len;
151        while (idx < 0  ) idx += len;
152        T * ret = v.elems_first_$ + idx;
153        if (ret < v.buffer_end_$) return *ret;
154        ret -= (v.buffer_end_$ - v.buffer_first_$);
155        assert( v.buffer_first_$ <= ret && ret < v.elems_end_$ );
156        return *ret;
157    }
158
159    T ?`val( vector_transit(T) & src ) {
160        T ret = findElemMem_$( *src.col_$, src.idx_$ );
161        return ret;
162    }
163
164    void ?=?( vector_transit(T) & src, T val ) {
165        findElemMem_$( *src.col_$, src.idx_$ ) = val;
166    }
167
168    // exit
169
170    void ?{}( vector_exit(T) & this, vector_transit(T) & src ) {
171        ( this.invec_$ ){ src.col_$ };
172        ( this.item_$ ){ & findElemMem_$( *src.col_$, src.idx_$ ) };
173
174        this.invec_$->exit_refcount_$ ++;
175    }
176    void ?{}( vector_exit(T) & this, vector_exit(T) & src ){
177        ( this.invec_$ ){ src.invec_$ };
178        ( this.item_$ ){ src.item_$ };
179
180        this.invec_$->exit_refcount_$ ++;
181    }
182
183    void ^?{}( vector_exit(T) & it ) {
184        it.invec_$->exit_refcount_$ --;
185    }
186
187    T ?`val( vector_exit(T) & src ) {
188        return *src.item_$;
189    }
190
191    void ?*=?( T & dst, vector_exit(T) & src ) {
192        dst = *src.item_$;
193    }
194
195    bool ?`moveNext( vector_exit(T) & it ) {
196        if (it.invec_$->elems_first_$ == 0p) {
197            // vector is empty
198            assert ( it.item_$ == 0p ); // it was at origin
199            return false;
200        }
201        assert( it.invec_$->elems_first_$ < it.invec_$->elems_end_$ && "can't handle wraparound yet" ); // temporary: must implement
202        if( it.item_$ == 0p ) {
203            // moving from origin
204            it.item_$ = it.invec_$->elems_first_$;
205        } else {
206            it.item_$ += 1;
207            if( it.item_$ > it.invec_$->buffer_end_$ )
208                it.item_$ = it.invec_$->buffer_first_$;
209        }
210        if ( it.item_$ >= it.invec_$->elems_end_$ ) {
211            // moving to origin
212            it.item_$ = 0p;
213            return false;
214        } else {
215            return true;
216        }
217    }
218
219    // permit
220
221    void ^?{}( vector_permit(T) & this ) {
222        remove(this);
223    }
224
225    void ?{}( vector_permit(T) & this, vector_transit(T) & src ) {
226        ( this.invec_$ ){ src.col_$ };
227        ( this.item_$ ){ & findElemMem_$( *src.col_$, src.idx_$ ) };
228        insert_first( src.col_$->live_iters_$, this );
229    }
230
231    void ?{}( vector_permit(T) & this, vector_exit(T) & src ) {
232        ( this.invec_$ ){ src.invec_$ };
233        ( this.item_$ ){ src.item_$ };
234        insert_first( src.invec_$->live_iters_$, this );
235    }
236
237    T ?`val( vector_permit(T) & src ){
238        return *src.item_$;
239    }
240
241    // vec internals
242
243    void grow( vector( T ) & this ) {
244        size_t newCapacity = 2 * (this.buffer_end_$ - this.buffer_first_$);
245        T * newItems = aalloc( newCapacity );
246        size_t elemCount = this`length;
247        for ( ptrdiff_t pos = 0; pos < elemCount; pos += 1 ) {
248            newItems[pos] = findElemMem_$(this, pos);
249        }
250
251        while ( vector_permit(T) & liveIter = this.live_iters_$`elems; liveIter`moveNext ) {
252            liveIter.item_$ += (newItems - this.buffer_first_$);
253        }
254
255        free( this.buffer_first_$ );
256        this.buffer_first_$ = newItems;
257        this.buffer_end_$ = newItems + newCapacity;
258        this.elems_first_$ = this.buffer_first_$;
259        this.elems_end_$ = this.buffer_first_$ + elemCount;
260        assert (this.elems_end_$ < this.buffer_end_$);
261    }
262
263    // vec api
264
265    vector_transit(T) push_last( vector( T ) & col, T val ) {
266        assert (col.exit_refcount_$ == 0);
267        if (col`length >= col`capacity) {
268            assert (col`length == col`capacity);
269            grow(col);
270        }
271        // call autogen constructor deleted at end of hfa
272        vector_transit(T) ret = { & col, col`length };
273        *col.elems_end_$ = val;
274        if (col.elems_first_$ == 0p) col.elems_first_$ = col.elems_end_$;
275        col.elems_end_$ += 1;
276        if (col.elems_end_$ >= col.buffer_end_$) col.elems_end_$ = col.buffer_first_$;
277        return ret;
278    }
279
280    vector_exit(T) ?`origin( vector( T ) & vec ) {
281
282        // private memberwise constructor, deleted from global namespace at end
283        // autogen constructor would not do the raii
284        void ?{}( vector_exit(T) & this, vector(T) * invec_$, T * item_$ ) {
285            ( this.invec_$ ){ invec_$ };
286            ( this.item_$ ){ item_$ };
287            this.invec_$->exit_refcount_$ ++;
288        }
289
290        vector_exit(T) ret = { &vec, 0p };
291        return ret;
292    }
293
294    bool inRange_$( T * query, T * from, T * to) {
295        if (from == to) return false;
296        if (from < to) return from <= query && query < to;
297        return query < to || from <= query;
298    }
299
300    void insert_before( vector( T ) & col, ptrdiff_t idx, T val ) {
301        assert (col.exit_refcount_$ == 0);
302        if (col`length >= col`capacity) {
303            assert (col`length == col`capacity);
304            grow(col);
305        }
306       
307        T & insertTargetR = findElemMem_$( col, idx );
308        T * insertTarget = & insertTargetR; // doesn't work in one line; must be a bug
309
310        // bubble toward back
311        if ( col.elems_end_$ < insertTarget ) {
312            // two phases of bubbling, to wrap around
313            for (T * tgt = col.elems_end_$; tgt > col.buffer_first_$; tgt--) {
314                *tgt = *(tgt-1);
315            }
316            *col.buffer_first_$ = *(col.buffer_end_$ - 1);
317            for (T * tgt = col.buffer_end_$ - 1; tgt > insertTarget; tgt--) {
318                *tgt = *(tgt-1);
319            }
320        } else {
321            for (T * tgt = col.elems_end_$; tgt > insertTarget; tgt--) {
322                *tgt = *(tgt-1);
323            }
324        }
325
326        col.elems_end_$ += 1;
327        if (col.elems_end_$ == col.buffer_end_$) col.elems_end_$ = col.buffer_first_$;
328
329        *insertTarget = val;
330
331        while ( vector_permit(T) & liveIter = col.live_iters_$`elems; liveIter`moveNext ) {
332            if ( inRange_$(liveIter.item_$, insertTarget, col.elems_end_$) ) {
333                liveIter.item_$ += 1;
334                if (liveIter.item_$ >= col.buffer_end_$) liveIter.item_$ = col.buffer_first_$;
335            }
336        }
337    }
338
339    size_t ?`capacity( vector(T) & v ) {
340        return v.buffer_end_$ - v.buffer_first_$;
341    }
342
343    size_t ?`length( vector(T) & v ) {
344        if (v.elems_first_$ == 0p) return 0;
345        if (v.elems_first_$ < v.elems_end_$ ) return v.elems_end_$ - v.elems_first_$;
346        return v.buffer_end_$ - v.elems_first_$ + v.elems_end_$ - v.buffer_first_$;
347    }
348
349
350} // forall T
351
352forall( T ) {
353    void ?{}( vector_exit(T) &, vector(T) *, T * ) = void;
354    void ?{}( vector_transit(T) & this, vector( T ) * col, ptrdiff_t idx ) = void;
355}
Note: See TracBrowser for help on using the repository browser.