source: libcfa/src/collections/vector2.hfa@ b28ce93

Last change on this file since b28ce93 was 6b33e89, checked in by Peter A. Buhr <pabuhr@…>, 5 months ago

change backquote call to regular call
  • Property mode set to 100644
File size: 10.8 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 : Peter A. Buhr
12// Last Modified On : Wed Apr 23 14:39:51 2025
13// Update Count : 6
14//
15
16// This libcfa header and the vector-demo test form a standalone POC.
17// The 'vector' is really a host for a style of iterator.
18// The iterators represent a style proposed to be part of "how CFA collections should do iterators."
19// The vector API is not built out, beyond what's needed to test the iterators.
20
21#pragma once
22
23#include <stdlib.hfa>
24#include "list.hfa"
25
26forall( T ) {
27 struct vector;
28
29 struct vector_transit {
30 vector(T) * col_$;
31 ptrdiff_t idx_$;
32 };
33
34 struct vector_exit {
35 vector(T) * invec_$;
36 T * item_$;
37 };
38
39 struct vector_permit {
40 vector(T) * invec_$;
41 T * item_$;
42 inline dlink(vector_permit(T));
43 };
44 P9_EMBEDDED(vector_permit(T), dlink(vector_permit(T)))
45
46 struct vector {
47 T * buffer_first_$;
48 T * buffer_end_$;
49 T * elems_first_$;
50 T * elems_end_$; // wrapped before storing, never == buffer_end_$
51 size_t exit_refcount_$;
52 dlist(vector_permit(T)) live_iters_$;
53 };
54}
55
56static inline
57forall( T ) {
58
59 // vector
60
61 void ?{}( vector( T ) &, size_t capacity );
62 void ^?{}( vector( T ) & );
63
64 void ?{}( vector( T ) & ) = void;
65 void ?{}( vector( T ) &, vector( T ) & ) = void;
66 vector( T ) & ?=?( vector( T ) &, vector( T ) & ) = void;
67
68 // transit
69
70 void ?{}( vector_transit(T) & ) = void;
71 void ?{}( vector_transit(T) &, vector_transit(T) & );
72 void ^?{}( vector_transit(T) & );
73
74 T ?`val( vector_transit(T) & src );
75 void ?=?( vector_transit(T) & dst, T val );
76
77 // exit
78
79 void ?{}( vector_exit(T) & ) = void;
80 void ?{}( vector_exit(T) &, vector(T) * ) = void;
81
82 void ?{}( vector_exit(T) &, vector_transit(T) & );
83 void ?{}( vector_exit(T) &, vector_exit(T) & );
84 void ^?{}( vector_exit(T) & );
85
86 T ?`val( vector_exit(T) & src );
87 void ?=?( vector_exit(T) & dst, T val );
88 void ?*=?( T & dst, vector_exit(T) & src ); // wish it were ?=?, but that's not working
89
90 bool ?`moveNext( vector_exit(T) & it );
91
92 // permit
93
94 void ?{}( vector_permit(T) & ) = void;
95
96 void ^?{}( vector_permit(T) & );
97 void ?{}( vector_permit(T) &, vector_transit(T) & );
98 void ?{}( vector_permit(T) &, vector_exit(T) & );
99 void ?{}( vector_permit(T) &, vector_permit(T) & ) = void;
100
101 T ?`val( vector_permit(T) & src );
102
103 // api
104
105 vector_transit(T) push_last( vector( T ) & col, T val );
106 vector_transit(T) ?[?]( vector( T ) &, ptrdiff_t );
107 vector_exit(T) ?`origin( vector( T ) & );
108 size_t ?`capacity( vector(T) & );
109 size_t ?`length( vector(T) & );
110
111 void insert_before( vector( T ) & col, ptrdiff_t idx, T val );
112
113}
114
115static inline
116forall( T ) {
117
118 // vector
119
120 void ?{}( vector( T ) & this, size_t capacity ) {
121 (this.buffer_first_$){ aalloc( capacity ) };
122 (this.buffer_end_$){ this.buffer_first_$ + capacity};
123 (this.elems_first_$){ 0p };
124 (this.elems_end_$){ this.buffer_first_$ };
125 (this.exit_refcount_$){ 0 };
126 (this.live_iters_$){};
127 }
128
129 void ^?{}( vector( T ) & this ) {
130 assert( this.exit_refcount_$ == 0 );
131 free( this.buffer_first_$ );
132 this.buffer_first_$ = 0p;
133 this.buffer_end_$ = 0p;
134 this.elems_first_$ = 0p;
135 this.elems_end_$ = 0p;
136 }
137
138 // transit
139
140 void ?{}( vector_transit(T) & this, vector_transit(T) & other ) {
141 // call autogen constructor deleted at end of hfa
142 (this){ other.col_$, other.idx_$ };
143 }
144
145 void ^?{}( vector_transit(T) & ) {}
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
177 void ?{}( vector_exit(T) & this, vector_exit(T) & src ){
178 ( this.invec_$ ){ src.invec_$ };
179 ( this.item_$ ){ src.item_$ };
180
181 this.invec_$->exit_refcount_$ ++;
182 }
183
184 void ^?{}( vector_exit(T) & it ) {
185 it.invec_$->exit_refcount_$ --;
186 }
187
188 T ?`val( vector_exit(T) & src ) {
189 return *src.item_$;
190 }
191
192 void ?=?( vector_exit(T) & dst, T val ) {
193 *dst.item_$ = val;
194 }
195
196 void ?*=?( T & dst, vector_exit(T) & src ) {
197 dst = *src.item_$;
198 }
199
200 bool ?`moveNext( vector_exit(T) & it ) {
201 if (it.invec_$->elems_first_$ == 0p) {
202 // vector is empty
203 assert ( it.item_$ == 0p ); // it was at origin
204 return false;
205 }
206 assert( it.invec_$->elems_first_$ < it.invec_$->elems_end_$ && "can't handle wraparound yet" ); // temporary: must implement
207 if( it.item_$ == 0p ) {
208 // moving from origin
209 it.item_$ = it.invec_$->elems_first_$;
210 } else {
211 it.item_$ += 1;
212 if( it.item_$ > it.invec_$->buffer_end_$ )
213 it.item_$ = it.invec_$->buffer_first_$;
214 }
215 if ( it.item_$ >= it.invec_$->elems_end_$ ) {
216 // moving to origin
217 it.item_$ = 0p;
218 return false;
219 } else {
220 return true;
221 }
222 }
223
224 // permit
225
226 void ^?{}( vector_permit(T) & this ) {
227 remove(this);
228 }
229
230 void ?{}( vector_permit(T) & this, vector_transit(T) & src ) {
231 ( this.invec_$ ){ src.col_$ };
232 ( this.item_$ ){ & findElemMem_$( *src.col_$, src.idx_$ ) };
233 insert_first( src.col_$->live_iters_$, this );
234 }
235
236 void ?{}( vector_permit(T) & this, vector_exit(T) & src ) {
237 ( this.invec_$ ){ src.invec_$ };
238 ( this.item_$ ){ src.item_$ };
239 insert_first( src.invec_$->live_iters_$, this );
240 }
241
242 T ?`val( vector_permit(T) & src ){
243 return *src.item_$;
244 }
245
246 // vec internals
247
248 void grow_$( vector( T ) & this ) {
249 size_t newCapacity = 2 * (this.buffer_end_$ - this.buffer_first_$);
250 T * newItems = aalloc( newCapacity );
251 size_t elemCount = this`length;
252 for ( ptrdiff_t pos = 0; pos < elemCount; pos += 1 ) {
253 newItems[pos] = findElemMem_$(this, pos);
254 }
255
256 while ( vector_permit(T) & liveIter = iter( this.live_iters_$ ); advance( liveIter ) ) {
257 liveIter.item_$ += (newItems - this.buffer_first_$);
258 }
259
260 free( this.buffer_first_$ );
261 this.buffer_first_$ = newItems;
262 this.buffer_end_$ = newItems + newCapacity;
263 this.elems_first_$ = this.buffer_first_$;
264 this.elems_end_$ = this.buffer_first_$ + elemCount;
265 assert (this.elems_end_$ < this.buffer_end_$);
266 }
267
268 bool inRange_$( T * query, T * from, T * to) {
269 if (from == to) return false;
270 if (from < to) return from <= query && query < to;
271 return query < to || from <= query;
272 }
273
274 // vec api
275
276 vector_transit(T) push_last( vector( T ) & col, T val ) {
277 assert (col.exit_refcount_$ == 0);
278 if (col`length >= col`capacity) {
279 assert (col`length == col`capacity);
280 grow_$(col);
281 }
282 // call autogen constructor deleted at end of hfa
283 vector_transit(T) ret = { & col, col`length };
284 *col.elems_end_$ = val;
285 if (col.elems_first_$ == 0p) col.elems_first_$ = col.elems_end_$;
286 col.elems_end_$ += 1;
287 if (col.elems_end_$ >= col.buffer_end_$) col.elems_end_$ = col.buffer_first_$;
288 return ret;
289 }
290
291 vector_transit(T) ?[?]( vector( T ) & vec, ptrdiff_t idx ) {
292 // call autogen constructor deleted at end of hfa
293 vector_transit(T) ret = { & vec, idx };
294 return ret;
295 }
296
297 vector_exit(T) ?`origin( vector( T ) & vec ) {
298
299 // private memberwise constructor, deleted from global namespace at end
300 // autogen constructor would not do the raii
301 void ?{}( vector_exit(T) & this, vector(T) * invec_$, T * item_$ ) {
302 ( this.invec_$ ){ invec_$ };
303 ( this.item_$ ){ item_$ };
304 this.invec_$->exit_refcount_$ ++;
305 }
306
307 vector_exit(T) ret = { &vec, 0p };
308 return ret;
309 }
310
311 size_t ?`capacity( vector(T) & v ) {
312 return v.buffer_end_$ - v.buffer_first_$;
313 }
314
315 size_t ?`length( vector(T) & v ) {
316 if (v.elems_first_$ == 0p) return 0;
317 if (v.elems_first_$ < v.elems_end_$ ) return v.elems_end_$ - v.elems_first_$;
318 return v.buffer_end_$ - v.elems_first_$ + v.elems_end_$ - v.buffer_first_$;
319 }
320
321 void insert_before( vector( T ) & col, ptrdiff_t idx, T val ) {
322 assert (col.exit_refcount_$ == 0);
323 if (col`length >= col`capacity) {
324 assert (col`length == col`capacity);
325 grow_$(col);
326 }
327
328 T & insertTargetR = findElemMem_$( col, idx );
329 T * insertTarget = & insertTargetR; // doesn't work in one line; must be a bug
330
331 // bubble toward back
332 if ( col.elems_end_$ < insertTarget ) {
333 // two phases of bubbling, to wrap around
334 for (T * tgt = col.elems_end_$; tgt > col.buffer_first_$; tgt--) {
335 *tgt = *(tgt-1);
336 }
337 *col.buffer_first_$ = *(col.buffer_end_$ - 1);
338 for (T * tgt = col.buffer_end_$ - 1; tgt > insertTarget; tgt--) {
339 *tgt = *(tgt-1);
340 }
341 } else {
342 for (T * tgt = col.elems_end_$; tgt > insertTarget; tgt--) {
343 *tgt = *(tgt-1);
344 }
345 }
346
347 col.elems_end_$ += 1;
348 if (col.elems_end_$ == col.buffer_end_$) col.elems_end_$ = col.buffer_first_$;
349
350 *insertTarget = val;
351
352 while ( vector_permit(T) & liveIter = iter( col.live_iters_$ ); advance( liveIter ) ) {
353 if ( inRange_$(liveIter.item_$, insertTarget, col.elems_end_$) ) {
354 liveIter.item_$ += 1;
355 if (liveIter.item_$ >= col.buffer_end_$) liveIter.item_$ = col.buffer_first_$;
356 }
357 }
358 }
359
360} // forall T
361
362forall( T ) {
363 void ?{}( vector_exit(T) &, vector(T) *, T * ) = void;
364 void ?{}( vector_transit(T) & this, vector( T ) * col, ptrdiff_t idx ) = void;
365}
Note: See TracBrowser for help on using the repository browser.