source: libcfa/src/collections/list.hfa@ 0eacfd4

stuck-waitfor-destruct
Last change on this file since 0eacfd4 was 0eacfd4, checked in by Peter A. Buhr <pabuhr@…>, 10 months ago

formatting and adding alternate-named list routines
  • Property mode set to 100644
File size: 10.7 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 : Sat Apr 19 16:24:09 2025
13// Update Count : 27
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) & lst ) {
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) & lst) - 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 void insert_after( tE & list_pos, tE & to_insert ) {
131 verify( &list_pos != 0p );
132 verify( &to_insert != 0p );
133
134 dlink(tE) & linkToInsert = to_insert`inner;
135
136 verify( linkToInsert.prev == 0p );
137 verify( linkToInsert.next == 0p );
138
139 tE & list_pos_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&list_pos );
140 dlink(tE) & list_pos_links = list_pos_elem`inner;
141 asm( "" : : : "memory" );
142 tE & after_raw = *list_pos_links.next;
143 tE & after_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&after_raw );
144 linkToInsert.prev = &list_pos;
145 linkToInsert.next = &after_raw;
146 dlink(tE) & afterLinks = after_elem`inner;
147 afterLinks.prev = &to_insert;
148 list_pos_links.next = &to_insert;
149 asm( "" : : : "memory" );
150 }
151 void insert( tE & list_pos, tE & to_insert ) { // alternate name
152 insert_after( list_pos, to_insert );
153 }
154
155 void insert_before( tE & list_pos, tE &to_insert ) {
156 verify( &list_pos != 0p );
157 verify( &to_insert != 0p );
158
159 dlink(tE) & linkToInsert = to_insert`inner;
160
161 verify( linkToInsert.next == 0p );
162 verify( linkToInsert.prev == 0p );
163
164 tE & list_pos_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&list_pos );
165 dlink(tE) & list_pos_links = list_pos_elem`inner;
166 asm( "" : : : "memory" );
167 tE & before_raw = *(list_pos_links).prev;
168 tE & before_elem = *(tE *) ORIGIN_TAG_CLEAR( (size_t)&before_raw );
169 linkToInsert.next = & list_pos;
170 linkToInsert.prev = & before_raw;
171 dlink(tE) & beforeLinks = before_elem`inner;
172 beforeLinks.next = &to_insert;
173 list_pos_links.prev = &to_insert;
174 asm( "" : : : "memory" );
175 }
176
177 tE & remove( tE & list_pos ) {
178 verify( &list_pos != 0p );
179 verify( ! ORIGIN_TAG_QUERY( (size_t)&list_pos) );
180
181 dlink(tE) & list_pos_links = list_pos`inner;
182 tE & before_raw = * list_pos_links.prev;
183 tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t)&before_raw );
184 dlink(tE) & before_links = before_elem`inner;
185 tE & after_raw = * list_pos_links.next;
186 tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t)&after_raw );
187 dlink(tE) & after_links = after_elem`inner;
188 before_links.next = &after_raw;
189 after_links.prev = &before_raw;
190 asm( "" : : : "memory" );
191 list_pos_links.prev = 0p;
192 list_pos_links.next = 0p;
193 asm( "" : : : "memory" );
194 return list_pos;
195 }
196 // forall( T &, List ... | { tE & remove( tE & ); } )
197 // void remove( tE & list_pos, List rest ) {
198 // remove( list_pos );
199 // remove( rest );
200 // }
201
202 tE & ?`first( dlist(tE, tLinks) &lst ) {
203 tE * firstPtr = lst.next;
204 if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
205 return *firstPtr;
206 }
207 tE & ?`last( dlist(tE, tLinks) &lst ) {
208 tE * lastPtr = lst.prev;
209 if (ORIGIN_TAG_QUERY((size_t)lastPtr)) lastPtr = 0p;
210 return *lastPtr;
211 }
212
213 bool ?`isEmpty( dlist(tE, tLinks) & lst ) {
214 tE * firstPtr = lst.next;
215 if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
216 return firstPtr == 0p;
217 }
218
219 bool ?`isListed( tE & e ) {
220 verify( &e != 0p);
221 dlink(tE) & e_links = e`inner;
222 return (e_links.prev != 0p) || (e_links.next != 0p);
223 }
224
225 tE & ?`elems( dlist(tE, tLinks) & lst ) {
226 tE * origin = $get_list_origin_addr( lst );
227 return *origin;
228 }
229 tE & ?`head( dlist(tE, tLinks) & lst ) {
230 return lst`elems;
231 }
232
233 bool ?`moveNext( tE && refx ) {
234 tE && ref_inner = refx;
235 tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
236 &ref_inner = oldReferent`inner.next;
237 return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
238 }
239 bool ?`next( tE && refx ) { // alternate name
240 return refx`moveNext;
241 }
242
243 bool ?`movePrev( tE && refx ) {
244 tE && ref_inner = refx;
245 tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
246 &ref_inner = oldReferent`inner.prev;
247 return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
248 }
249 bool ?`prev( tE && refx ) { // alternate name
250 return refx`movePrev;
251 }
252
253 bool ?`hasNext( tE & e ) {
254 return e`moveNext;
255 }
256
257 bool ?`hasPrev( tE & e ) {
258 return e`movePrev;
259 }
260
261 tE & ?`next( tE & e ) {
262 if ( e`moveNext ) return e;
263 return *0p;
264 }
265
266 tE & ?`prev( tE & e ) {
267 if ( e`movePrev ) return e;
268 return *0p;
269 }
270
271 void insert_first( dlist(tE, tLinks) &lst, tE & e ) {
272 insert_after( lst`elems, e );
273 }
274
275 void insert_last( dlist(tE, tLinks) &lst, tE & e ) {
276 insert_before( lst`elems, e );
277 }
278 void insert( dlist(tE, tLinks) &lst, tE & e ) { // alternate name
279 insert_last( lst, e );
280 }
281
282 tE & try_pop_front( dlist(tE, tLinks) &lst ) {
283 tE & first_inlist = lst`first;
284 tE & first_item = first_inlist;
285 if ( &first_item) remove( first_inlist );
286 return first_item;
287 }
288
289 tE & try_pop_back( dlist(tE, tLinks) &lst ) {
290 tE & last_inlist = lst`last;
291 tE & last_item = last_inlist;
292 if ( &last_item) remove( last_inlist );
293 return last_item;
294 }
295
296
297 #if ! defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
298 bool $validate_fwd( dlist(tE, tLinks) & this ) {
299 if ( ! & this`first ) return ( (&this`last) == 0p);
300
301 tE & lagElem = *0p;
302 while ( tE & it = this`elems; it`moveNext ) {
303 if ( & lagElem == 0p && &it != & this`first ) return false;
304 &lagElem = &it;
305 }
306
307 if ( &lagElem != &this`last ) return false;
308
309 // TODO: verify that it is back at this`elems;
310 return true;
311 }
312
313 bool $validate_rev( dlist(tE, tLinks) & this ) {
314 if ( ! & this`last ) return ( (&this`first) == 0p);
315
316 tE & lagElem = *0p;
317 while ( tE & it = this`elems; it`movePrev ) {
318 if ( &lagElem == 0p && &it != & this`last ) return false;
319 &lagElem = &it;
320 }
321
322 if ( &lagElem != &this`first) return false;
323
324 // TODO: verify that it is back at this`elems;
325 return true;
326 }
327
328 bool validate( dlist(tE, tLinks) & this ) {
329 return $validate_fwd(this) && $validate_rev(this);
330 }
331 #endif
332}
333
334// TEMPORARY, until foreach statement created.
335#define FOREACH( list, index ) for ( typeof((list)`head) & (index) = (list)`head; (index)`next; )
336#define FOREACH_COND( list, index, expr ) for ( typeof((list)`head) & (index) = (list)`head; (index)`next && (expr); )
337#define FOREACH_REV( list, index ) for ( typeof((list)`head) & (index) = (list)`head; (index)`prev; )
338#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.