source: libcfa/src/containers/vector2.hfa@ efdd18c

ADT ast-experimental
Last change on this file since efdd18c was 5e4a830, checked in by Peter A. Buhr <pabuhr@…>, 3 years ago

add #pragma once to .h and .hfa files
  • 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 : 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
21forall( 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
51static inline
52forall( 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
111static inline
112forall( 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
354forall( T ) {
355 void ?{}( vector_exit(T) &, vector(T) *, T * ) = void;
356 void ?{}( vector_transit(T) & this, vector( T ) * col, ptrdiff_t idx ) = void;
357}
Note: See TracBrowser for help on using the repository browser.