source: libcfa/src/collections/list.hfa@ 1eea589f

Last change on this file since 1eea589f was 7806f91, checked in by Mike Brooks <mlbrooks@…>, 3 months ago

Add code for reproducing performance numbers in thesis draft of 16a843
  • Property mode set to 100644
File size: 13.9 KB
RevLine 
[6091b88a]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
[8a97248]11// Last Modified By : Peter A. Buhr
[6b33e89]12// Last Modified On : Thu Apr 24 18:12:59 2025
13// Update Count : 72
[6091b88a]14//
15
[e857743]16#pragma once
17
[6091b88a]18#include <assert.h>
19
[69914cbc]20forall( Decorator &, T & )
21struct tytagref {
[9dd1dd6]22 inline T &;
[6091b88a]23};
24
[8a97248]25forall( tOuter &, tMid &, tInner & )
26trait embedded {
[9dd1dd6]27 tytagref( tMid, tInner ) ?`inner( tOuter & );
[69914cbc]28};
[6091b88a]29
[69914cbc]30// embedded is reflexive, with no info (void) as the type tag
[0eacfd4]31forall( T & )
[69914cbc]32static inline tytagref(void, T) ?`inner ( T & this ) { tytagref( void, T ) ret = {this}; return ret; }
33
[1fd3d85]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 {
[9dd1dd6]39// int a, b, c;
40// inline (bar);
[1fd3d85]41// };
42// P9_EMBEDDED( foo, bar )
43//
44
45// usual version, for structs that are top-level declarations
[9dd1dd6]46#define P9_EMBEDDED( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, static ) P9_EMBEDDED_BDY_( immedBase )
[1fd3d85]47
48// special version, for structs that are declared in functions
[9dd1dd6]49#define P9_EMBEDDED_INFUNC( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, ) P9_EMBEDDED_BDY_( immedBase )
[1fd3d85]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
[9dd1dd6]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, ) ;
[1fd3d85]55
56// private helpers
57#define P9_EMBEDDED_DECL_( derived, immedBase, STORAGE ) \
[9dd1dd6]58 forall( Tbase &, TdiscardPath & | { tytagref( TdiscardPath, Tbase ) ?`inner( immedBase & ); } ) \
[65b0402]59 STORAGE inline tytagref( immedBase, Tbase ) ?`inner( derived & this )
[9dd1dd6]60
[1fd3d85]61#define P9_EMBEDDED_BDY_( immedBase ) { \
[9dd1dd6]62 immedBase & ib = this; \
63 Tbase & b = ib`inner; \
[65b0402]64 tytagref( immedBase, Tbase ) result = { b }; \
[9dd1dd6]65 return result; \
66 }
[69914cbc]67
[65b0402]68#define EMBEDDED_VIA( OUTER, MID, INNER ) (struct { tytagref( MID, INNER ) ( * ?`inner ) ( OUTER & ); }){ ?`inner }
[0eacfd4]69
[65b0402]70#define DLINK_VIA( TE, TLINK ) EMBEDDED_VIA( TE, TLINK, dlink( TE ) )
[0eacfd4]71
72
73// The origin is the position encountered at the start of iteration, signifying, "need to advance to the first element,"
[6b33e89]74// and at the end of iteration, signifying, "no more elements." Normal comsumption of an iterator runs "advance" as
75// the first step, and uses the return of "advance" as a guard, before dereferencing the iterator. So normal
[0eacfd4]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
[69914cbc]80// part), by failing fast.
81
[7806f91]82#ifdef __EXPERIMENTAL_DISABLE_OTAG__ // Perf experimention alt mode
83
84 // With origin tagging disabled, iteration never reports "no more elements."
85 // In this mode, the list API is buggy.
86 // This mode is used to quantify the cost of the normal tagging scheme.
87
88 #define ORIGIN_TAG_SET(p) (p)
89 #define ORIGIN_TAG_CLEAR(p) (p)
90 #define ORIGIN_TAG_QUERY(p) 0
91 #define ORIGIN_TAG_ASGN(p, v) (p)
92 #define ORIGIN_TAG_EITHER(p, v) (p)
93 #define ORIGIN_TAG_NEQ(v1, v2) 0
94
95#else // Normal
96
97 #if defined( __x86_64 )
98 // Preferred case: tag in the most-significant bit. Dereference
99 // has been shown to segfault consistently. Maintenance should
100 // list more architectures as "ok" here, to let them use the
101 // preferred case, when valid.
102 #define ORIGIN_TAG_BITNO ( 8 * sizeof( size_t ) - 1 )
103 #else
104 // Fallback case: tag in the least-significant bit. Dereference
105 // will often give an alignment error, but may not, e.g. if
106 // accessing a char-typed member. 32-bit x86 uses the most-
107 // significant bit for real room on the heap.
108 #define ORIGIN_TAG_BITNO 0
109 #endif
110
111 #define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO)
112
113 #define ORIGIN_TAG_SET(p) ((p) | ORIGIN_TAG_MASK)
114 #define ORIGIN_TAG_CLEAR(p) ((p) & ~ORIGIN_TAG_MASK)
115 #define ORIGIN_TAG_QUERY(p) ((p) & ORIGIN_TAG_MASK)
116
117 #define ORIGIN_TAG_ASGN(p, v) ( \
118 verify( ! ORIGIN_TAG_QUERY(p) && "p had no tagbit" ), \
119 ORIGIN_TAG_EITHER((p), (v)) \
120 )
121
122 #define ORIGIN_TAG_EITHER(p, v) ( \
123 verify( ! ORIGIN_TAG_CLEAR(v) && "v is a pure tagbit" ), \
124 ( (p) | (v) ) \
125 )
126
127 #define ORIGIN_TAG_NEQ(v1, v2) ( \
128 verify( ! ORIGIN_TAG_CLEAR(v1) && "v1 is a pure tagbit" ), \
129 verify( ! ORIGIN_TAG_CLEAR(v2) && "v2 is a pure tagbit" ), \
130 ( (v1) ^ (v2) ) \
131 )
132
133#endif
134
135
136
137#ifdef __EXPERIMENTAL_LOOSE_SINGLES__ // Perf experimention alt mode
138
139 // In loose-singles mode, the ability to answer an "is listed" query is disabled, as is "to insert an element,
140 // it must not be listed already" checking. The user must know separately whether an element is listed.
141 // Other than inserting it, any list-api action on an unlisted element is undefined. Notably, list iteration
142 // starting from an unlisted element is not defined to respond "no more elements," and may instead continue
143 // iterating from a formerly occupied list position. This mode matches LQ usage.
144
145 #define NOLOOSE(...)
146 #define LOOSEONLY(...) __VA_ARGS__
147
148#else // Normal
149
150 #define NOLOOSE(...) __VA_ARGS__
151 #define LOOSEONLY(...)
152
[69914cbc]153#endif
154
[7806f91]155
156
157
[6091b88a]158
[69914cbc]159forall( tE & ) {
[9dd1dd6]160 struct dlink{
[0eacfd4]161 tE * next;
162 tE * prev;
[9dd1dd6]163 };
164
[65b0402]165 static inline void ?{}( dlink( tE ) & this ) {
[7806f91]166 NOLOOSE(
[0eacfd4]167 this.next = this.prev = 0p;
[7806f91]168 )
[9dd1dd6]169 }
170
[65b0402]171 forall( tLinks & = dlink( tE ) )
[9dd1dd6]172 struct dlist {
[65b0402]173 inline dlink( tE );
[9dd1dd6]174 };
175
[65b0402]176 forall( tLinks & | embedded( tE, tLinks, dlink( tE ) ) ) {
177 static inline tE * $get_list_origin_addr( dlist( tE, tLinks ) & list ) {
178 dlink( tE ) & link_from_null = (*(tE *)0p)`inner;
179 ptrdiff_t link_offset = (ptrdiff_t)&link_from_null;
180 size_t origin_addr = ((size_t)&list) - link_offset;
[9dd1dd6]181 size_t preResult = ORIGIN_TAG_SET( origin_addr );
182 return (tE *)preResult;
183 }
184
[65b0402]185 static inline void ?{}( dlist( tE, tLinks ) & this ) {
[9dd1dd6]186 tE * listOrigin = $get_list_origin_addr( this );
[65b0402]187 ((dlink( tE ) &)this){ listOrigin, listOrigin };
[9dd1dd6]188 }
189 }
[69914cbc]190}
[4d741e9]191
192
[65b0402]193static inline forall( tE &, tLinks & | embedded( tE, tLinks, dlink( tE ) ) ) {
[6b33e89]194 bool isListed( tE & node ) {
[7806f91]195 NOLOOSE(
[6b33e89]196 verify( &node != 0p );
197 dlink( tE ) & node_links = node`inner;
198 return (node_links.prev != 0p) || (node_links.next != 0p);
[7806f91]199 )
200 LOOSEONLY(
201 verify(false && "isListed is undefined");
202 return true;
203 )
[6b33e89]204 }
205
206 bool isEmpty( dlist( tE, tLinks ) & list ) {
207 tE * firstPtr = list.next;
208 if ( ORIGIN_TAG_QUERY(( size_t)firstPtr) ) firstPtr = 0p;
209 return firstPtr == 0p;
210 }
211
212 tE & first( dlist( tE, tLinks ) & list ) {
213 tE * firstPtr = list.next;
214 if ( ORIGIN_TAG_QUERY( (size_t)firstPtr ) ) firstPtr = 0p;
215 return *firstPtr;
216 }
217
218 tE & last( dlist( tE, tLinks ) & list ) {
219 tE * lastPtr = list.prev;
220 if ( ORIGIN_TAG_QUERY( (size_t)lastPtr) ) lastPtr = 0p;
221 return *lastPtr;
222 }
223
[65b0402]224 tE & insert_before( tE & before, tE & node ) {
225 verify( &before != 0p );
226 verify( &node != 0p );
[4d741e9]227
[65b0402]228 dlink( tE ) & linkToInsert = node`inner;
[7806f91]229 NOLOOSE(
[0eacfd4]230 verify( linkToInsert.next == 0p );
[65b0402]231 verify( linkToInsert.prev == 0p );
[7806f91]232 )
[0eacfd4]233
[65b0402]234 tE & list_pos_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&before );
235 dlink( tE ) & list_pos_links = list_pos_elem`inner;
[9dd1dd6]236 asm( "" : : : "memory" );
[65b0402]237 tE & before_raw = *list_pos_links.prev;
238 tE & before_elem = *(tE *) ORIGIN_TAG_CLEAR( (size_t)&before_raw );
239 linkToInsert.next = &before;
240 linkToInsert.prev = &before_raw;
241 dlink( tE ) & beforeLinks = before_elem`inner;
242 beforeLinks.next = &node;
243 list_pos_links.prev = &node;
[9dd1dd6]244 asm( "" : : : "memory" );
[65b0402]245 return node;
[0eacfd4]246 }
247
[65b0402]248 tE & insert_after( tE & after, tE & node ) {
249 verify( &after != 0p );
250 verify( &node != 0p );
[6091b88a]251
[65b0402]252 dlink( tE ) & linkToInsert = node`inner;
[7806f91]253 NOLOOSE(
[0eacfd4]254 verify( linkToInsert.prev == 0p );
[65b0402]255 verify( linkToInsert.next == 0p );
[7806f91]256 )
[0eacfd4]257
[65b0402]258 tE & list_pos_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&after );
259 dlink( tE ) & list_pos_links = list_pos_elem`inner;
[9dd1dd6]260 asm( "" : : : "memory" );
[65b0402]261 tE & after_raw = *list_pos_links.next;
262 tE & after_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&after_raw );
263 linkToInsert.prev = &after;
264 linkToInsert.next = &after_raw;
265 dlink( tE ) & afterLinks = after_elem`inner;
266 afterLinks.prev = &node;
267 list_pos_links.next = &node;
[9dd1dd6]268 asm( "" : : : "memory" );
[65b0402]269 return node;
[6091b88a]270 }
271
[65b0402]272 tE & remove( tE & node ) {
273 verify( &node != 0p );
274 verify( ! ORIGIN_TAG_QUERY( (size_t)&node) );
275
276 dlink( tE ) & list_pos_links = node`inner;
277 tE & before_raw = *list_pos_links.prev;
278 tE & before_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&before_raw );
279 dlink( tE ) & before_links = before_elem`inner;
280 tE & after_raw = *list_pos_links.next;
281 tE & after_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&after_raw );
282 dlink( tE ) & after_links = after_elem`inner;
[9dd1dd6]283 before_links.next = &after_raw;
284 after_links.prev = &before_raw;
[7806f91]285
286 NOLOOSE(
[9dd1dd6]287 asm( "" : : : "memory" );
[69914cbc]288 list_pos_links.prev = 0p;
289 list_pos_links.next = 0p;
[9dd1dd6]290 asm( "" : : : "memory" );
[7806f91]291 )
[65b0402]292 return node;
[9dd1dd6]293 }
[65b0402]294
[6b33e89]295 tE & iter( dlist( tE, tLinks ) & list ) {
[65b0402]296 tE * origin = $get_list_origin_addr( list );
[9dd1dd6]297 return *origin;
298 }
299
[6b33e89]300 bool recede( tE && refx ) {
[9dd1dd6]301 tE && ref_inner = refx;
[65b0402]302 tE & oldReferent = *(tE*)ORIGIN_TAG_CLEAR( (size_t)&ref_inner );
[6b33e89]303 &ref_inner = oldReferent`inner.prev;
[65b0402]304 return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t)&ref_inner );
[0eacfd4]305 }
[9dd1dd6]306
[6b33e89]307 bool advance( tE && refx ) {
[9dd1dd6]308 tE && ref_inner = refx;
[65b0402]309 tE & oldReferent = *(tE*)ORIGIN_TAG_CLEAR( (size_t)&ref_inner );
[6b33e89]310 &ref_inner = oldReferent`inner.next;
[65b0402]311 return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t)&ref_inner );
[0eacfd4]312 }
[9dd1dd6]313
[6b33e89]314 bool isFirst( tE & node ) {
315 return recede( node );
316 }
[9dd1dd6]317
[6b33e89]318 bool isLast( tE & node ) {
319 return advance( node );
320 }
[9dd1dd6]321
[6b33e89]322 tE & prev( tE & node ) {
323 if ( recede( node ) ) return node;
[0eacfd4]324 return *0p;
[9dd1dd6]325 }
326
[6b33e89]327 tE & next( tE & node ) {
328 if ( advance( node ) ) return node;
[0eacfd4]329 return *0p;
[9dd1dd6]330 }
331
[65b0402]332 tE & insert_first( dlist( tE, tLinks ) & list, tE & node ) {
[6b33e89]333 insert_after( iter( list ), node );
[65b0402]334 return node;
[9dd1dd6]335 }
336
[65b0402]337 tE & insert_last( dlist( tE, tLinks ) & list, tE & node ) {
[6b33e89]338 insert_before( iter( list ), node );
[65b0402]339 return node;
340 }
[6b33e89]341 tE & insert( dlist( tE, tLinks ) & list, tE & node ) { // synonym for insert_last
[65b0402]342 insert_last( list, node );
343 return node;
[0eacfd4]344 }
[65b0402]345
346 tE & remove_first( dlist( tE, tLinks ) & list ) {
[6b33e89]347 tE & first_node = first( list );
348 if ( &first_node ) return remove( first_node );
349 return first_node;
[65b0402]350 }
351
352 tE & remove_last( dlist( tE, tLinks ) & list ) {
[6b33e89]353 tE & last_node = last( list );
354 if ( &last_node ) return remove( last_node );
355 return last_node;
[9dd1dd6]356 }
357
[65b0402]358 // Transfer the "from" list to the end of this sequence; the "from" list is empty after the transfer.
359// void transfer( dlist( tE, tLinks ) & to, dlist( tE, tLinks ) & from ) {
360// if ( isEmpty( from ) ) return; // "from" list empty ?
361// if ( isEmpty( to ) ) { // "to" list empty ?
362// root = from.root;
363// } else { // "to" list not empty
364// T * toEnd = (T *)uBack( root );
365// T * fromEnd = (T *)from.uBack( from.root );
366// uBack( root ) = fromEnd;
367// from.uNext( fromEnd ) = root;
368// from.uBack( from.root ) = toEnd;
369// uNext( toEnd ) = from.root;
370// } // if
371// from.root = nullptr; // mark "from" list empty
372// }
373
374 // Transfer the "from" list up to node "n" to the end of this list; the "from" list becomes the sequence after node "n".
375 // Node "n" must be in the "from" list.
376// void split( dlist( tE, tLinks ) & to, dlist( tE, tLinks ) & from, tE & node ) {
377// #ifdef __U_DEBUG__
378// if ( ! n->listed() ) abort( "(uSequence &)%p.split( %p ) : Node is not on a list.", this, n );
379// #endif // __U_DEBUG__
380// uSequence<T> to;
381// to.root = from.root; // start of "to" list
382// from.root = (T *)uNext( n ); // start of "from" list
383// if ( to.root == from.root ) { // last node in list ?
384// from.root = nullptr; // mark "from" list empty
385// } else {
386// uBack( from.root ) = (T *)uBack( to.root ); // fix "from" list
387// uNext( uBack( to.root ) ) = from.root;
388// uNext( n ) = to.root; // fix "to" list
389// uBack( to.root ) = n;
390// } // if
391// transfer( to );
392// }
393
[0eacfd4]394 #if ! defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
[65b0402]395 bool $validate_fwd( dlist( tE, tLinks ) & this ) {
[6b33e89]396 if ( ! & first( this ) ) return &last( this ) == 0p;
[69914cbc]397
[9dd1dd6]398 tE & lagElem = *0p;
[6b33e89]399 while ( tE & it = iter( this ); advance( it ) ) {
400 if ( & lagElem == 0p && &it != & first( this ) ) return false;
[0eacfd4]401 &lagElem = &it;
[9dd1dd6]402 }
[69914cbc]403
[6b33e89]404 if ( &lagElem != &last( this ) ) return false;
[69914cbc]405
[6b33e89]406 // TODO: verify that it is back at iter( this );
[9dd1dd6]407 return true;
[6091b88a]408 }
409
[65b0402]410 bool $validate_rev( dlist( tE, tLinks ) & this ) {
[6b33e89]411 if ( ! & last( this ) ) return &first( this ) == 0p;
[f2d05e9]412
[0eacfd4]413 tE & lagElem = *0p;
[6b33e89]414 while ( tE & it = iter( this ); recede( it ) ) {
415 if ( &lagElem == 0p && &it != & last( this ) ) return false;
[0eacfd4]416 &lagElem = &it;
[9dd1dd6]417 }
[f2d05e9]418
[6b33e89]419 if ( &lagElem != &first( this ) ) return false;
[f2d05e9]420
[6b33e89]421 // TODO: verify that it is back at iter( this );
[9dd1dd6]422 return true;
[69914cbc]423 }
[0eacfd4]424
[65b0402]425 bool validate( dlist( tE, tLinks ) & this ) {
426 return $validate_fwd( this ) && $validate_rev( this );
[f2d05e9]427 }
[0eacfd4]428 #endif
[6091b88a]429}
430
[0eacfd4]431// TEMPORARY, until foreach statement created.
[6b33e89]432#define FOREACH( list, index ) for ( typeof(iter( list )) & (index) = iter( list ); advance( index ); )
433#define FOREACH_REV( list, index ) for ( typeof(iter( list )) & (index) = iter( list ); recede( index ); )
434#define FOREACH_COND( list, index, expr ) for ( typeof(iter( list )) & (index) = iter( list ); advance( index ) && !(expr); )
435#define FOREACH_REV_COND( list, index, expr ) for ( typeof(iter( list )) & (index) = iter( list ); recede( index ) && !(expr); )
Note: See TracBrowser for help on using the repository browser.