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