source: libcfa/src/containers/list2.hfa@ 8cd5434

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since 8cd5434 was 7d51ef8, checked in by Michael Brooks <mlbrooks@…>, 4 years ago

Changing how the dlist API specifies which list direction you're working on.

New style is:
with( DLINK_VIA( request, request.priority ) ) remove( myItem );

This change eliminates the diref type from the public API. The diref type did not support intutive use of taking the address of its referent, as is needed to null-check or identity-compare a reference.
  • Property mode set to 100644
File size: 9.9 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 : Michael Brooks
12// Last Modified On : Wed Apr 22 18:00:00 2020
13// Update Count : 1
14//
15
16#pragma once
17
18#include <assert.h>
19
20forall( Decorator &, T & )
21struct tytagref {
22 inline T &;
23};
24
25trait embedded( tOuter &, tMid &, tInner & ) {
26 tytagref( tMid, tInner ) ?`inner( tOuter & );
27};
28
29// embedded is reflexive, with no info (void) as the type tag
30forall (T &)
31tytagref(void, T) ?`inner ( T & this ) { tytagref( void, T ) ret = {this}; return ret; }
32
33// use this on every case of plan-9 inheritance, to make embedded a closure of plan-9 inheritance
34#define P9_EMBEDDED( derived, immedBase ) \
35forall( Tbase &, TdiscardPath & | { tytagref( TdiscardPath, Tbase ) ?`inner( immedBase & ); } ) \
36 static inline tytagref(immedBase, Tbase) ?`inner( derived & this ) { \
37 immedBase & ib = this; \
38 Tbase & b = ib`inner; \
39 tytagref(immedBase, Tbase) result = { b }; \
40 return result; \
41 }
42
43#define EMBEDDED_VIA( OUTER, MID, INNER ) \
44 (struct { tytagref(MID, INNER) ( * ?`inner ) ( OUTER & ); }){ ?`inner }
45
46#define DLINK_VIA( TE, TLINK ) \
47 EMBEDDED_VIA( TE, TLINK, dlink(TE) )
48
49
50// The origin is the position encountered at the start of iteration,
51// signifying, "need to advance to the first element," and at the end
52// of iteration, signifying, "no more elements." Normal comsumption of
53// an iterator runs ?`moveNext as the first step, and uses the return
54// of ?`moveNext as a guard, before dereferencing the iterator. So
55// normal consumption of an iterator does not dereference an iterator
56// in origin position. The value of a pointer (underlying a refence)
57// that is exposed publicly as an iteraor, and also a pointer stored
58// internally in a link field, is tagged, to indicate "is the origin"
59// (internally, is the list-head sentinel node), or untagged, to indicate
60// "is a regular node." Intent is to help a user who dereferences an
61// iterator in origin position (which would be an API-use error on their
62// part), by failing fast.
63
64#if defined( __x86_64 )
65 // Preferred case: tag in the most-significant bit. Dereference
66 // has been shown to segfault consistently. Maintenance should
67 // list more architectures as "ok" here, to let them use the
68 // preferred case, when valid.
69 #define ORIGIN_TAG_BITNO ( 8 * sizeof( size_t ) - 1 )
70#else
71 // Fallback case: tag in the least-significant bit. Dereference
72 // will often give an alignment error, but may not, e.g. if
73 // accessing a char-typed member. 32-bit x86 uses the most-
74 // significant bit for real room on the heap.
75 #define ORIGIN_TAG_BITNO 0
76#endif
77#define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO)
78
79#define ORIGIN_TAG_SET(p) ((p) | ORIGIN_TAG_MASK)
80#define ORIGIN_TAG_CLEAR(p) ((p) & ~ORIGIN_TAG_MASK)
81#define ORIGIN_TAG_QUERY(p) ((p) & ORIGIN_TAG_MASK)
82
83
84forall( tE & ) {
85
86 struct dlink{
87 tE *next;
88 tE *prev;
89 };
90
91 static inline void ?{}( dlink(tE) & this ) {
92 this.next = 0p;
93 this.prev = 0p;
94 }
95
96 forall( tLinks & = dlink(tE) )
97 struct dlist {
98 inline dlink(tE);
99 };
100
101 forall( tLinks & | embedded( tE, tLinks, dlink(tE) ) ) {
102 static inline tE * $get_list_origin_addr( dlist(tE, tLinks) & lst ) {
103 dlink(tE) & link_from_null = ( * (tE *) 0p )`inner;
104 ptrdiff_t link_offset = (ptrdiff_t) & link_from_null;
105 size_t origin_addr = ((size_t) & lst) - link_offset;
106 size_t preResult = ORIGIN_TAG_SET( origin_addr );
107 return (tE *)preResult;
108 }
109
110 static inline void ?{}( dlist(tE, tLinks) & this ) {
111 tE * listOrigin = $get_list_origin_addr( this );
112 ( ( dlink(tE) & ) this ){ listOrigin, listOrigin } ;
113 }
114 }
115
116}
117
118
119forall( tE &, tLinks & | embedded( tE, tLinks, dlink(tE) ) ) {
120
121 static inline void insert_after(tE & list_pos, tE &to_insert) {
122 verify (&list_pos != 0p);
123 verify (&to_insert != 0p);
124 dlink(tE) & linkToInsert = to_insert`inner;
125 verify(linkToInsert.prev == 0p);
126 verify(linkToInsert.next == 0p);
127 tE & list_pos_raw = list_pos;
128 tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos_raw );
129 dlink(tE) & list_pos_links = list_pos_elem`inner;
130 asm( "" : : : "memory" );
131 tE & after_raw = * list_pos_links.next;
132 tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
133 linkToInsert.prev = & list_pos_raw;
134 linkToInsert.next = & after_raw;
135 dlink(tE) & afterLinks = after_elem`inner;
136 afterLinks.prev = &to_insert;
137 list_pos_links.next = &to_insert;
138 asm( "" : : : "memory" );
139 }
140
141 static inline void insert_before(tE & list_pos, tE &to_insert) {
142 verify (&list_pos != 0p);
143 verify (&to_insert != 0p);
144 dlink(tE) & linkToInsert = to_insert`inner;
145 verify(linkToInsert.next == 0p);
146 verify(linkToInsert.prev == 0p);
147 tE & list_pos_raw = list_pos;
148 tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos_raw );
149 dlink(tE) & list_pos_links = list_pos_elem`inner;
150 asm( "" : : : "memory" );
151 tE & before_raw = * (list_pos_links).prev;
152 tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
153 linkToInsert.next = & list_pos_raw;
154 linkToInsert.prev = & before_raw;
155 dlink(tE) & beforeLinks = before_elem`inner;
156 beforeLinks.next = &to_insert;
157 (list_pos_links).prev = &to_insert;
158 asm( "" : : : "memory" );
159 }
160
161 static inline tE & remove(tE & list_pos) {
162 verify (&list_pos != 0p);
163 tE & list_pos_elem = list_pos;
164 verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos_elem) );
165 dlink(tE) & list_pos_links = list_pos_elem`inner;
166 tE & before_raw = * list_pos_links.prev;
167 tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
168 dlink(tE) & before_links = before_elem`inner;
169 tE & after_raw = * list_pos_links.next;
170 tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
171 dlink(tE) & after_links = after_elem`inner;
172 before_links.next = &after_raw;
173 after_links.prev = &before_raw;
174 asm( "" : : : "memory" );
175 list_pos_links.prev = 0p;
176 list_pos_links.next = 0p;
177 asm( "" : : : "memory" );
178 return list_pos_elem;
179 }
180
181 static inline tE & ?`first( dlist(tE, tLinks) &lst ) {
182 tE * firstPtr = lst.next;
183 if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
184 return *firstPtr;
185 }
186 static inline tE & ?`last ( dlist(tE, tLinks) &lst ) {
187 tE * lastPtr = lst.prev;
188 if (ORIGIN_TAG_QUERY((size_t)lastPtr)) lastPtr = 0p;
189 return *lastPtr;
190 }
191
192 static inline bool ?`isEmpty( dlist(tE, tLinks) & lst ) {
193 tE * firstPtr = lst.next;
194 if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
195 return firstPtr == 0p;
196 }
197
198 static inline tE & ?`elems( dlist(tE, tLinks) & lst ) {
199 tE * origin = $get_list_origin_addr( lst );
200 return *origin;
201 }
202
203 static inline bool ?`moveNext( tE && refx ) {
204 tE && ref_inner = refx;
205 tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
206 &ref_inner = oldReferent`inner.next;
207 return &ref_inner != 0p &&
208 ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
209 }
210
211 static inline bool ?`movePrev( tE && refx ) {
212 tE && ref_inner = refx;
213 tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
214 &ref_inner = oldReferent`inner.prev;
215 return &ref_inner != 0p &&
216 ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
217 }
218
219 static inline bool ?`hasNext( tE & e ) {
220 return e`moveNext;
221 }
222
223 static inline bool ?`hasPrev( tE & e ) {
224 return e`movePrev;
225 }
226
227 static inline tE & ?`next( tE & e ) {
228 if( e`moveNext ) return e;
229 return * 0p;
230 }
231
232 static inline tE & ?`prev( tE & e ) {
233 if( e`movePrev ) return e;
234 return * 0p;
235 }
236
237 static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) {
238 insert_after(lst`elems, e);
239 }
240
241 static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) {
242 insert_before(lst`elems, e);
243 }
244
245 static inline tE & try_pop_front( dlist(tE, tLinks) &lst ) {
246 tE & first_inlist = lst`first;
247 tE & first_item = first_inlist;
248 if (&first_item) remove(first_inlist);
249 return first_item;
250 }
251
252 static inline tE & try_pop_back( dlist(tE, tLinks) &lst ) {
253 tE & last_inlist = lst`last;
254 tE & last_item = last_inlist;
255 if (&last_item) remove(last_inlist);
256 return last_item;
257 }
258
259
260 #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
261 static bool $validate_fwd( dlist(tE, tLinks) & this ) {
262 if ( ! & this`first ) return ( (& this`last) == 0p);
263
264 tE & lagElem = *0p;
265
266 while ( tE & it = this`elems; it`moveNext ) {
267 if (& lagElem == 0p && &it != & this`first ) return false;
268 & lagElem = & it;
269 }
270
271 if (& lagElem != & this`last) return false;
272
273 // TODO: verify that it is back at this`elems;
274 return true;
275 }
276 static bool $validate_rev( dlist(tE, tLinks) & this ) {
277 if ( ! & this`last ) return ( (& this`first) == 0p);
278
279 tE & lagElem = *0p;
280
281 while ( tE & it = this`elems; it`movePrev ) {
282 if (& lagElem == 0p && &it != & this`last ) return false;
283 & lagElem = & it;
284 }
285
286 if (& lagElem != & this`first) return false;
287
288 // TODO: verify that it is back at this`elems;
289 return true;
290 }
291 static bool validate( dlist(tE, tLinks) & this ) {
292 return $validate_fwd(this) && $validate_rev(this);
293 }
294 #endif
295
296}
297
Note: See TracBrowser for help on using the repository browser.