source: libcfa/src/collections/list.hfa@ 65b0402

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

formatting and add return values
  • Property mode set to 100644
File size: 12.3 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2020 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// list -- lets a user-defined stuct form intrusive linked lists
8//
9// Author : Michael Brooks
10// Created On : Wed Apr 22 18:00:00 2020
11// Last Modified By : Peter A. Buhr
12// Last Modified On : Sun Apr 20 19:04:50 2025
13// Update Count : 51
14//
15
16#pragma once
17
18#include <assert.h>
19
20forall( Decorator &, T & )
21struct tytagref {
22 inline T &;
23};
24
25forall( tOuter &, tMid &, tInner & )
26trait embedded {
27 tytagref( tMid, tInner ) ?`inner( tOuter & );
28};
29
30// embedded is reflexive, with no info (void) as the type tag
31forall( T & )
32static inline tytagref(void, T) ?`inner ( T & this ) { tytagref( void, T ) ret = {this}; return ret; }
33
34
35//
36// P9_EMBEDDED: Use on every case of plan-9 inheritance, to make "implements embedded" be a closure of plan-9 inheritance.
37//
38// struct foo {
39// int a, b, c;
40// inline (bar);
41// };
42// P9_EMBEDDED( foo, bar )
43//
44
45// usual version, for structs that are top-level declarations
46#define P9_EMBEDDED( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, static ) P9_EMBEDDED_BDY_( immedBase )
47
48// special version, for structs that are declared in functions
49#define P9_EMBEDDED_INFUNC( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, ) P9_EMBEDDED_BDY_( immedBase )
50
51// forward declarations of both the above; generally not needed
52// may help you control where the P9_EMBEEDED cruft goes, in case "right after the stuct" isn't where you want it
53#define P9_EMBEDDED_FWD( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, static ) ;
54#define P9_EMBEDDED_FWD_INFUNC( derived, immedBase ) auto P9_EMBEDDED_DECL_( derived, immedBase, ) ;
55
56// private helpers
57#define P9_EMBEDDED_DECL_( derived, immedBase, STORAGE ) \
58 forall( Tbase &, TdiscardPath & | { tytagref( TdiscardPath, Tbase ) ?`inner( immedBase & ); } ) \
59 STORAGE inline tytagref( immedBase, Tbase ) ?`inner( derived & this )
60
61#define P9_EMBEDDED_BDY_( immedBase ) { \
62 immedBase & ib = this; \
63 Tbase & b = ib`inner; \
64 tytagref( immedBase, Tbase ) result = { b }; \
65 return result; \
66 }
67
68#define EMBEDDED_VIA( OUTER, MID, INNER ) (struct { tytagref( MID, INNER ) ( * ?`inner ) ( OUTER & ); }){ ?`inner }
69
70#define DLINK_VIA( TE, TLINK ) EMBEDDED_VIA( TE, TLINK, dlink( TE ) )
71
72
73// The origin is the position encountered at the start of iteration, signifying, "need to advance to the first element,"
74// and at the end of iteration, signifying, "no more elements." Normal comsumption of an iterator runs ?`moveNext as
75// the first step, and uses the return of ?`moveNext as a guard, before dereferencing the iterator. So normal
76// consumption of an iterator does not dereference an iterator in origin position. The value of a pointer (underlying a
77// refence) that is exposed publicly as an iteraor, and also a pointer stored internally in a link field, is tagged, to
78// indicate "is the origin" (internally, is the list-head sentinel node), or untagged, to indicate "is a regular node."
79// Intent is to help a user who dereferences an iterator in origin position (which would be an API-use error on their
80// part), by failing fast.
81
82#if defined( __x86_64 )
83 // Preferred case: tag in the most-significant bit. Dereference has been shown to segfault consistently.
84 // Maintenance should list more architectures as "ok" here, to let them use the preferred case, when valid.
85 #define ORIGIN_TAG_BITNO ( 8 * sizeof( size_t ) - 1 )
86#else
87 // Fallback case: tag in the least-significant bit. Dereference will often give an alignment error, but may not,
88 // e.g. if accessing a char-typed member. 32-bit x86 uses the most- significant bit for real room on the heap.
89 #define ORIGIN_TAG_BITNO 0
90#endif
91#define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO)
92
93#define ORIGIN_TAG_SET( p ) ((p) | ORIGIN_TAG_MASK)
94#define ORIGIN_TAG_CLEAR( p ) ((p) & ~ORIGIN_TAG_MASK)
95#define ORIGIN_TAG_QUERY( p ) ((p) & ORIGIN_TAG_MASK)
96
97forall( tE & ) {
98 struct dlink{
99 tE * next;
100 tE * prev;
101 };
102
103 static inline void ?{}( dlink( tE ) & this ) {
104 this.next = this.prev = 0p;
105 }
106
107 forall( tLinks & = dlink( tE ) )
108 struct dlist {
109 inline dlink( tE );
110 };
111
112 forall( tLinks & | embedded( tE, tLinks, dlink( tE ) ) ) {
113 static inline tE * $get_list_origin_addr( dlist( tE, tLinks ) & list ) {
114 dlink( tE ) & link_from_null = (*(tE *)0p)`inner;
115 ptrdiff_t link_offset = (ptrdiff_t)&link_from_null;
116 size_t origin_addr = ((size_t)&list) - link_offset;
117 size_t preResult = ORIGIN_TAG_SET( origin_addr );
118 return (tE *)preResult;
119 }
120
121 static inline void ?{}( dlist( tE, tLinks ) & this ) {
122 tE * listOrigin = $get_list_origin_addr( this );
123 ((dlink( tE ) &)this){ listOrigin, listOrigin };
124 }
125 }
126}
127
128
129static inline forall( tE &, tLinks & | embedded( tE, tLinks, dlink( tE ) ) ) {
130 tE & insert_before( tE & before, tE & node ) {
131 verify( &before != 0p );
132 verify( &node != 0p );
133
134 dlink( tE ) & linkToInsert = node`inner;
135
136 verify( linkToInsert.next == 0p );
137 verify( linkToInsert.prev == 0p );
138
139 tE & list_pos_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&before );
140 dlink( tE ) & list_pos_links = list_pos_elem`inner;
141 asm( "" : : : "memory" );
142 tE & before_raw = *list_pos_links.prev;
143 tE & before_elem = *(tE *) ORIGIN_TAG_CLEAR( (size_t)&before_raw );
144 linkToInsert.next = &before;
145 linkToInsert.prev = &before_raw;
146 dlink( tE ) & beforeLinks = before_elem`inner;
147 beforeLinks.next = &node;
148 list_pos_links.prev = &node;
149 asm( "" : : : "memory" );
150 return node;
151 }
152
153 tE & insert_after( tE & after, tE & node ) {
154 verify( &after != 0p );
155 verify( &node != 0p );
156
157 dlink( tE ) & linkToInsert = node`inner;
158
159 verify( linkToInsert.prev == 0p );
160 verify( linkToInsert.next == 0p );
161
162 tE & list_pos_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&after );
163 dlink( tE ) & list_pos_links = list_pos_elem`inner;
164 asm( "" : : : "memory" );
165 tE & after_raw = *list_pos_links.next;
166 tE & after_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&after_raw );
167 linkToInsert.prev = &after;
168 linkToInsert.next = &after_raw;
169 dlink( tE ) & afterLinks = after_elem`inner;
170 afterLinks.prev = &node;
171 list_pos_links.next = &node;
172 asm( "" : : : "memory" );
173 return node;
174 }
175
176 tE & remove( tE & node ) {
177 verify( &node != 0p );
178 verify( ! ORIGIN_TAG_QUERY( (size_t)&node) );
179
180 dlink( tE ) & list_pos_links = node`inner;
181 tE & before_raw = *list_pos_links.prev;
182 tE & before_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&before_raw );
183 dlink( tE ) & before_links = before_elem`inner;
184 tE & after_raw = *list_pos_links.next;
185 tE & after_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&after_raw );
186 dlink( tE ) & after_links = after_elem`inner;
187 before_links.next = &after_raw;
188 after_links.prev = &before_raw;
189 asm( "" : : : "memory" );
190 list_pos_links.prev = 0p;
191 list_pos_links.next = 0p;
192 asm( "" : : : "memory" );
193 return node;
194 }
195
196 tE & ?`first( dlist( tE, tLinks ) & list ) {
197 tE * firstPtr = list.next;
198 if ( ORIGIN_TAG_QUERY( (size_t)firstPtr ) ) firstPtr = 0p;
199 return *firstPtr;
200 }
201
202 tE & ?`last( dlist( tE, tLinks ) & list ) {
203 tE * lastPtr = list.prev;
204 if ( ORIGIN_TAG_QUERY( (size_t)lastPtr) ) lastPtr = 0p;
205 return *lastPtr;
206 }
207
208 bool ?`isEmpty( dlist( tE, tLinks ) & list ) {
209 tE * firstPtr = list.next;
210 if ( ORIGIN_TAG_QUERY(( size_t)firstPtr) ) firstPtr = 0p;
211 return firstPtr == 0p;
212 }
213
214 bool ?`isListed( tE & node ) {
215 verify( &node != 0p );
216 dlink( tE ) & node_links = node`inner;
217 return (node_links.prev != 0p) || (node_links.next != 0p);
218 }
219
220 tE & ?`elems( dlist( tE, tLinks ) & list ) {
221 tE * origin = $get_list_origin_addr( list );
222 return *origin;
223 }
224 tE & ?`head( dlist( tE, tLinks ) & list ) {
225 return list`elems;
226 }
227
228 bool ?`moveNext( tE && refx ) {
229 tE && ref_inner = refx;
230 tE & oldReferent = *(tE*)ORIGIN_TAG_CLEAR( (size_t)&ref_inner );
231 &ref_inner = oldReferent`inner.next;
232 return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t)&ref_inner );
233 }
234 bool ?`next( tE && refx ) { // alternate name
235 return refx`moveNext;
236 }
237
238 bool ?`movePrev( tE && refx ) {
239 tE && ref_inner = refx;
240 tE & oldReferent = *(tE*)ORIGIN_TAG_CLEAR( (size_t)&ref_inner );
241 &ref_inner = oldReferent`inner.prev;
242 return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t)&ref_inner );
243 }
244 bool ?`prev( tE && refx ) { // alternate name
245 return refx`movePrev;
246 }
247
248 bool ?`hasNext( tE & node ) {
249 return node`moveNext;
250 }
251
252 bool ?`hasPrev( tE & node ) {
253 return node`movePrev;
254 }
255
256 tE & ?`next( tE & node ) {
257 if ( node`moveNext ) return node;
258 return *0p;
259 }
260
261 tE & ?`prev( tE & node ) {
262 if ( node`movePrev ) return node;
263 return *0p;
264 }
265
266 tE & insert_first( dlist( tE, tLinks ) & list, tE & node ) {
267 insert_after( list`elems, node );
268 return node;
269 }
270
271 tE & insert_last( dlist( tE, tLinks ) & list, tE & node ) {
272 insert_before( list`elems, node );
273 return node;
274 }
275 tE & insert( dlist( tE, tLinks ) & list, tE & node ) { // alternate name
276 insert_last( list, node );
277 return node;
278 }
279
280 tE & remove_first( dlist( tE, tLinks ) & list ) {
281 return remove( list`first );
282 }
283
284 tE & remove_last( dlist( tE, tLinks ) & list ) {
285 return remove( list`last );
286 }
287
288 // Transfer the "from" list to the end of this sequence; the "from" list is empty after the transfer.
289// void transfer( dlist( tE, tLinks ) & to, dlist( tE, tLinks ) & from ) {
290// if ( isEmpty( from ) ) return; // "from" list empty ?
291// if ( isEmpty( to ) ) { // "to" list empty ?
292// root = from.root;
293// } else { // "to" list not empty
294// T * toEnd = (T *)uBack( root );
295// T * fromEnd = (T *)from.uBack( from.root );
296// uBack( root ) = fromEnd;
297// from.uNext( fromEnd ) = root;
298// from.uBack( from.root ) = toEnd;
299// uNext( toEnd ) = from.root;
300// } // if
301// from.root = nullptr; // mark "from" list empty
302// }
303
304 // Transfer the "from" list up to node "n" to the end of this list; the "from" list becomes the sequence after node "n".
305 // Node "n" must be in the "from" list.
306// void split( dlist( tE, tLinks ) & to, dlist( tE, tLinks ) & from, tE & node ) {
307// #ifdef __U_DEBUG__
308// if ( ! n->listed() ) abort( "(uSequence &)%p.split( %p ) : Node is not on a list.", this, n );
309// #endif // __U_DEBUG__
310// uSequence<T> to;
311// to.root = from.root; // start of "to" list
312// from.root = (T *)uNext( n ); // start of "from" list
313// if ( to.root == from.root ) { // last node in list ?
314// from.root = nullptr; // mark "from" list empty
315// } else {
316// uBack( from.root ) = (T *)uBack( to.root ); // fix "from" list
317// uNext( uBack( to.root ) ) = from.root;
318// uNext( n ) = to.root; // fix "to" list
319// uBack( to.root ) = n;
320// } // if
321// transfer( to );
322// }
323
324 tE & try_pop_front( dlist( tE, tLinks ) & list ) {
325 tE & first_inlist = list`first;
326 tE & first_item = first_inlist;
327 if ( &first_item ) remove( first_inlist );
328 return first_item;
329 }
330
331 tE & try_pop_back( dlist( tE, tLinks ) & list ) {
332 tE & last_inlist = list`last;
333 tE & last_item = last_inlist;
334 if ( &last_item ) remove( last_inlist );
335 return last_item;
336 }
337
338
339 #if ! defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
340 bool $validate_fwd( dlist( tE, tLinks ) & this ) {
341 if ( ! & this`first ) return &this`last == 0p;
342
343 tE & lagElem = *0p;
344 while ( tE & it = this`elems; it`moveNext ) {
345 if ( & lagElem == 0p && &it != & this`first ) return false;
346 &lagElem = &it;
347 }
348
349 if ( &lagElem != &this`last ) return false;
350
351 // TODO: verify that it is back at this`elems;
352 return true;
353 }
354
355 bool $validate_rev( dlist( tE, tLinks ) & this ) {
356 if ( ! & this`last ) return &this`first == 0p;
357
358 tE & lagElem = *0p;
359 while ( tE & it = this`elems; it`movePrev ) {
360 if ( &lagElem == 0p && &it != & this`last ) return false;
361 &lagElem = &it;
362 }
363
364 if ( &lagElem != &this`first ) return false;
365
366 // TODO: verify that it is back at this`elems;
367 return true;
368 }
369
370 bool validate( dlist( tE, tLinks ) & this ) {
371 return $validate_fwd( this ) && $validate_rev( this );
372 }
373 #endif
374}
375
376// TEMPORARY, until foreach statement created.
377#define FOREACH( list, index ) for ( typeof((list)`head) & (index) = (list)`head; (index)`next; )
378#define FOREACH_REV( list, index ) for ( typeof((list)`head) & (index) = (list)`head; (index)`prev; )
379#define FOREACH_COND( list, index, expr ) for ( typeof((list)`head) & (index) = (list)`head; (index)`next && !(expr); )
380#define FOREACH_REV_COND( list, index, expr ) for ( typeof((list)`head) & (index) = (list)`head; (index)`prev && !(expr); )
Note: See TracBrowser for help on using the repository browser.