source: libcfa/src/collections/list2.hfa@ 79ba50c

stuck-waitfor-destruct
Last change on this file since 79ba50c was 8f448e0, checked in by Michael Brooks <mlbrooks@…>, 6 months ago

Make dlist2 pass the original dlist test. Now, there is one common test for both.
  • Property mode set to 100644
File size: 24.4 KB
RevLine 
[7806f91]1// A revision of <collections/list.hfa>.
2// Supports headless (and headed) lists.
3// It's basically all good, and should become the official libcfa one, except:
4// - perf tests compare this one ("thesis's work") to libcfa ("old, before supporting headless")
5// - in libcfa, some uses of list.hfa make assumptions about list's private representation, which need fixing
6
7
8
9
10//
11// Cforall Version 1.0.0 Copyright (C) 2020 University of Waterloo
12//
13// The contents of this file are covered under the licence agreement in the
14// file "LICENCE" distributed with Cforall.
15//
16// list -- lets a user-defined stuct form intrusive linked lists
17//
18// Author : Michael Brooks
19// Created On : Wed Apr 22 18:00:00 2020
20// Last Modified By : Peter A. Buhr
21// Last Modified On : Thu Feb 2 11:32:26 2023
22// Update Count : 2
23//
24
25#pragma once
26
27#include <assert.h>
28
29forall( Decorator &, T & )
30struct tytagref {
31 inline T &;
32};
33
34forall( tOuter &, tMid &, tInner & )
35trait embedded {
36 tytagref( tMid, tInner ) ?`inner( tOuter & );
37};
38
39// embedded is reflexive, with no info (void) as the type tag
40forall (T &)
41static inline tytagref(void, T) ?`inner ( T & this ) { tytagref( void, T ) ret = {this}; return ret; }
42
43
44//
45// P9_EMBEDDED: Use on every case of plan-9 inheritance, to make "implements embedded" be a closure of plan-9 inheritance.
46//
47// struct foo {
48// int a, b, c;
49// inline (bar);
50// };
51// P9_EMBEDDED( foo, bar )
52//
53
54// usual version, for structs that are top-level declarations
55#define P9_EMBEDDED( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, static ) P9_EMBEDDED_BDY_( immedBase )
56
57// special version, for structs that are declared in functions
58#define P9_EMBEDDED_INFUNC( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, ) P9_EMBEDDED_BDY_( immedBase )
59
60// forward declarations of both the above; generally not needed
61// may help you control where the P9_EMBEEDED cruft goes, in case "right after the stuct" isn't where you want it
62#define P9_EMBEDDED_FWD( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, static ) ;
63#define P9_EMBEDDED_FWD_INFUNC( derived, immedBase ) auto P9_EMBEDDED_DECL_( derived, immedBase, ) ;
64
65// private helpers
66#define P9_EMBEDDED_DECL_( derived, immedBase, STORAGE ) \
67 forall( Tbase &, TdiscardPath & | { tytagref( TdiscardPath, Tbase ) ?`inner( immedBase & ); } ) \
68 STORAGE inline tytagref(immedBase, Tbase) ?`inner( derived & this )
69
70#define P9_EMBEDDED_BDY_( immedBase ) { \
71 immedBase & ib = this; \
72 Tbase & b = ib`inner; \
73 tytagref(immedBase, Tbase) result = { b }; \
74 return result; \
75 }
76
77#define EMBEDDED_VIA( OUTER, MID, INNER ) \
78 (struct { tytagref(MID, INNER) ( * ?`inner ) ( OUTER & ); }){ ?`inner }
79
80#define DLINK_VIA( TE, TLINK ) \
81 EMBEDDED_VIA( TE, TLINK, dlink(TE) )
82
83// The origin is the position encountered at the start of iteration,
84// signifying, "need to advance to the first element," and at the end
85// of iteration, signifying, "no more elements." Normal comsumption of
[6c58850]86// an iterator runs advance as the first step, and uses the return
87// of advance as a guard, before dereferencing the iterator. So
[7806f91]88// normal consumption of an iterator does not dereference an iterator
89// in origin position. The value of a pointer (underlying a refence)
90// that is exposed publicly as an iteraor, and also a pointer stored
91// internally in a link field, is tagged, to indicate "is the origin"
92// (internally, is the list-head sentinel node), or untagged, to indicate
93// "is a regular node." Intent is to help a user who dereferences an
94// iterator in origin position (which would be an API-use error on their
95// part), by failing fast.
96
97#ifdef __EXPERIMENTAL_DISABLE_OTAG__ // Perf experimention alt mode
98
99 // With origin tagging disabled, iteration never reports "no more elements."
100 // In this mode, the list API is buggy.
101 // This mode is used to quantify the cost of the normal tagging scheme.
102
103 #define ORIGIN_TAG_ENABL(p) (p)
104 #define ORIGIN_TAG_CLEAR(p) (p)
105 #define ORIGIN_TAG_QUERY(p) 0
106 #define ORIGIN_TAG_ASGN(p, v) (p)
107 #define ORIGIN_TAG_EITHER(p, v) (p)
108 #define ORIGIN_TAG_NEQ(v1, v2) 0
109
110#else // Normal
111
112 #if defined( __x86_64 )
113 // Preferred case: tag in the most-significant bit. Dereference
114 // has been shown to segfault consistently. Maintenance should
115 // list more architectures as "ok" here, to let them use the
116 // preferred case, when valid.
117 #define ORIGIN_TAG_BITNO ( 8 * sizeof( size_t ) - 1 )
118 #else
119 // Fallback case: tag in the least-significant bit. Dereference
120 // will often give an alignment error, but may not, e.g. if
121 // accessing a char-typed member. 32-bit x86 uses the most-
122 // significant bit for real room on the heap.
123 #define ORIGIN_TAG_BITNO 0
124 #endif
125
126 #define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO)
127
128 #define ORIGIN_TAG_ENABL(p) ((p) | ORIGIN_TAG_MASK)
129 #define ORIGIN_TAG_CLEAR(p) ((p) & ~ORIGIN_TAG_MASK)
130 #define ORIGIN_TAG_QUERY(p) ((p) & ORIGIN_TAG_MASK)
131
132 #define ORIGIN_TAG_ASGN(p, v) ( \
133 verify( ! ORIGIN_TAG_QUERY(p) && "p had no tagbit" ), \
134 ORIGIN_TAG_EITHER((p), (v)) \
135 )
136
137 #define ORIGIN_TAG_EITHER(p, v) ( \
138 verify( ! ORIGIN_TAG_CLEAR(v) && "v is a pure tagbit" ), \
139 ( (p) | (v) ) \
140 )
141
142 #define ORIGIN_TAG_NEQ(v1, v2) ( \
143 verify( ! ORIGIN_TAG_CLEAR(v1) && "v1 is a pure tagbit" ), \
144 verify( ! ORIGIN_TAG_CLEAR(v2) && "v2 is a pure tagbit" ), \
145 ( (v1) ^ (v2) ) \
146 )
147
148#endif
149
150
151
152
153
154
155#ifdef __EXPERIMENTAL_LOOSE_SINGLES__ // Perf experimention alt mode
156
157 // In loose-singles mode, the ability to answer an "is listed" query is disabled, as is "to insert an element,
158 // it must not be listed already" checking. The user must know separately whether an element is listed.
159 // Other than inserting it, any list-api action on an unlisted element is undefined. Notably, list iteration
160 // starting from an unlisted element is not defined to respond "no more elements," and may instead continue
161 // iterating from a formerly occupied list position. This mode matches LQ usage.
162
163 #define NOLOOSE(...)
164 #define LOOSEONLY(...) __VA_ARGS__
165
166#else // Normal
167
168 #define NOLOOSE(...) __VA_ARGS__
169 #define LOOSEONLY(...)
170
171#endif
172
173
174
175
176
177
178
179
180// struct workaround0_t {};
181
182forall( tE & ) {
183
184 struct dlink;
185
186 // do not use; presence of the field declaration unblocks ability to define dlink (#304)
187 struct __dlink_selfref_workaround_t {
188 dlink(tE) *ref_notSelfRef;
189 };
190
191 struct dlink {
192 dlink(tE) *next; // TODO: rename with $
193 dlink(tE) *prev;
194 };
195
196 static inline void ?{}( dlink(tE) & this ) {
197 NOLOOSE(
198 dlink(tE) * toSelf = & this;
199 size_t toSelfNum = (size_t) toSelf;
200 size_t toSelfNumTagged = ORIGIN_TAG_ENABL( toSelfNum );
201 dlink(tE) * toSelfPtrTagged = (dlink(tE) *) toSelfNumTagged;
202 toSelf = toSelfPtrTagged;
203 (this.next){ toSelf };
204 (this.prev){ toSelf };
205 )
206 }
207
208 // You can "copy" a dlink. But the result won't be linked.
209 // Lets you copy what you inline the dlink into.
210 static inline void ?{}( dlink(tE) & this, dlink(tE) ) {
211 this{};
212 }
213
214 forall( tLinks & = dlink(tE) | embedded(tE, tLinks, dlink(tE)) ) {
215 struct dlist {
216 inline dlink(tE);
217 };
218
219 static inline tE * $get_list_origin_addr( dlist(tE, tLinks) & lst ) {
220 dlink(tE) & link_from_null = ( * (tE *) 0p )`inner;
221 ptrdiff_t link_offset = (ptrdiff_t) & link_from_null;
222 size_t origin_addr = ((size_t) & lst) - link_offset;
223 size_t preResult = ORIGIN_TAG_ENABL( origin_addr );
224 return (tE *)preResult;
225 }
226
227 static inline void ?{}( dlist(tE, tLinks) & this ) {
228 NOLOOSE(
229 ( (dlink(tE) &) this ){};
230 )
231 LOOSEONLY(
232 dlink(tE) * listOrigin = (dlink(tE) *) $get_list_origin_addr( this );
233 dlink( tE ) & thisl = this;
234 (thisl.prev) = listOrigin;
235 (thisl.next) = listOrigin;
236 )
237 }
238 }
239}
240
[8f448e0]241forall( tE & ) {
242#ifdef __EXPERIMENTAL_DISABLE_OTAG__ // Perf experimention alt mode
243 static inline size_t origin_tag_query_arith$( tE & raw ) {
244 return 0;
245 }
246 static inline tE & nullif$( tE & val, size_t arith_ctrl ) {
247 verify( arith_ctrl == 0 ); (void) arith_ctrl;
248 return val;
249 }
250#else // Normal
251 // like ORIGIN_TAG_QUERY, but return is arithmetic number 0 or 1 (rather than 0 or non-0)
252 static inline size_t origin_tag_query_arith$( tE & raw ) {
253 size_t ret = (((size_t) & raw) >> ORIGIN_TAG_BITNO) & 1;
254 verify( ORIGIN_TAG_QUERY( (size_t) & raw ) ? ret == 1 : ret == 0 );
255 return ret;
256 }
257 // Requires arith_ctrl being 0 or 1.
258 // When 0, passes val through; when 1, returns null reference.
259 // Importantly, implemented without jumps or tests.
260 static inline tE & nullif$( tE & val, size_t arith_ctrl ) {
261 verify( ! ORIGIN_TAG_QUERY( (size_t) & val ) );
262 verify( arith_ctrl == 0 || arith_ctrl == 1 );
263 size_t mask_ctrl = ~ - arith_ctrl;
264 verify( arith_ctrl == 0 && mask_ctrl == -1 || arith_ctrl == 1 && mask_ctrl ==0 );
265 tE & ret = * (tE*) ( ((size_t) & val) & mask_ctrl);
266 verify( arith_ctrl == 0 && &ret == &val || arith_ctrl == 1 && &ret == 0p );
267 return ret;
268 }
269#endif
270}
[7806f91]271
272forall( tE &, tLinks & | embedded( tE, tLinks, dlink(tE) ) ) {
273
274 static inline void insert_after(tE & list_pos, tE &to_insert) {
275 size_t list_pos_tag = ORIGIN_TAG_QUERY((size_t) & list_pos); // a request to insert after the origin is fine
276 tE & list_pos_real = * (tE *) ORIGIN_TAG_CLEAR((size_t) & list_pos);
277 verify (&list_pos_real != 0p);
278
279 verify (&to_insert != 0p);
280 NOLOOSE(
281 verify(! ORIGIN_TAG_QUERY((size_t) & to_insert));
282 )
283 dlink(tE) & linkToInsert = to_insert`inner;
284 NOLOOSE(
285 verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.prev));
286 verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.next));
287 verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.prev) == (size_t)&linkToInsert);
288 verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.next) == (size_t)&linkToInsert);
289 )
290 dlink(tE) & list_pos_links = list_pos_real`inner;
291 asm( "" : : : "memory" );
292 size_t list_pos_links_num = (size_t)(& list_pos_links);
293 size_t to_insert_prev_num = ORIGIN_TAG_ASGN(list_pos_links_num, list_pos_tag);
294 dlink(tE) * to_insert_prev = (dlink(tE)*)to_insert_prev_num;
295 linkToInsert.prev = to_insert_prev;
296 linkToInsert.next = list_pos_links.next;
297 dlink(tE) & afterLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.next );
298 size_t afterLinks_prev_tag = ORIGIN_TAG_QUERY((size_t)afterLinks.prev);
299 size_t linkToInsert_num = (size_t)(& linkToInsert);
300 size_t afterLinks_prev_num = ORIGIN_TAG_ASGN(linkToInsert_num, ORIGIN_TAG_NEQ(list_pos_tag, afterLinks_prev_tag));
301 afterLinks.prev = (dlink(tE)*)(afterLinks_prev_num);
302 list_pos_links.next = &linkToInsert;
303 asm( "" : : : "memory" );
304 }
305
306 static inline void insert_before(tE & list_pos, tE &to_insert) {
307 size_t list_pos_tag = ORIGIN_TAG_QUERY((size_t) & list_pos); // a request to insert before the origin is fine
308 tE & list_pos_real = * (tE *) ORIGIN_TAG_CLEAR((size_t) & list_pos);
309 verify (&list_pos_real != 0p);
310
311 verify (&to_insert != 0p);
312 NOLOOSE(
313 verify(! ORIGIN_TAG_QUERY((size_t) & to_insert));
314 )
315 dlink(tE) & linkToInsert = to_insert`inner;
316 NOLOOSE(
317 verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.prev));
318 verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.next));
319 verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.prev) == (size_t)&linkToInsert);
320 verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.next) == (size_t)&linkToInsert);
321 )
322 dlink(tE) & list_pos_links = list_pos_real`inner;
323 asm( "" : : : "memory" );
324 size_t list_pos_links_num = (size_t)(& list_pos_links);
325 size_t to_insert_next_num = ORIGIN_TAG_ASGN(list_pos_links_num, list_pos_tag);
326 dlink(tE) * to_insert_next = (dlink(tE)*)to_insert_next_num;
327 linkToInsert.next = to_insert_next;
328 linkToInsert.prev = list_pos_links.prev;
329 dlink(tE) & beforeLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.prev );
330 size_t beforeLinks_next_tag = ORIGIN_TAG_QUERY((size_t)beforeLinks.next);
331 size_t linkToInsert_num = (size_t)(& linkToInsert);
332 size_t beforeLinks_next_num = ORIGIN_TAG_ASGN(linkToInsert_num, ORIGIN_TAG_NEQ(list_pos_tag, beforeLinks_next_tag));
333 beforeLinks.next = (dlink(tE)*)(beforeLinks_next_num);
334 list_pos_links.prev = &linkToInsert;
335 asm( "" : : : "memory" );
336 }
337
338 static inline tE & remove(tE & list_pos) {
339 verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos) );
340 verify (&list_pos != 0p);
341
342 dlink(tE) & list_pos_links = list_pos`inner;
343 dlink(tE) & before_raw = * list_pos_links.prev;
344 dlink(tE) & before_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
345 size_t before_links_next_tag = ORIGIN_TAG_QUERY( (size_t) (before_links.next) );
346
347 dlink(tE) & after_raw = * list_pos_links.next;
348 dlink(tE) & after_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
349 size_t after_links_prev_tag = ORIGIN_TAG_QUERY( (size_t) (after_links.prev) );
350
351 size_t before_links_next_rslt = ORIGIN_TAG_EITHER( ((size_t) & after_raw), before_links_next_tag );
352 size_t after_links_prev_rslt = ORIGIN_TAG_EITHER( ((size_t) & before_raw), after_links_prev_tag );
353 before_links.next = (dlink(tE) *) before_links_next_rslt;
354 after_links.prev = (dlink(tE) *) after_links_prev_rslt;
355
356 NOLOOSE(
357 asm( "" : : : "memory" );
358 size_t list_pos_links_num = (size_t) &list_pos_links;
359 size_t list_pos_links_tagged_num = ORIGIN_TAG_ENABL( list_pos_links_num );
360 list_pos_links.next = list_pos_links.prev = (dlink(tE)*) list_pos_links_tagged_num;
361 asm( "" : : : "memory" );
362 )
363 return list_pos;
364 }
365
366 static inline tE & downcast$( tytagref( tLinks, dlink(tE) ) ref ) {
367 dlink(tE) & lnk = ref;
368 dlink(tE) & link_from_null = ( * (tE *) 0p )`inner;
369 ptrdiff_t link_offset = (ptrdiff_t) & link_from_null;
370 size_t elm_addr = ((size_t) & lnk) - link_offset;
371 return * (tE*) elm_addr;
372 }
373
[6c58850]374 static inline tE & first( dlist(tE, tLinks) & lst ) {
[7806f91]375 verify (&lst != 0p);
376 dlink(tE) * firstLnk = lst.next;
377 if (ORIGIN_TAG_QUERY((size_t)firstLnk)) return * 0p;
378 tytagref( tLinks, dlink(tE) ) firstLnkTagged = {*firstLnk};
379 return downcast$( firstLnkTagged );
380 }
[6c58850]381 static inline tE & last ( dlist(tE, tLinks) & lst ) {
[7806f91]382 verify (&lst != 0p);
383 dlink(tE) * lastLnk = lst.prev;
384 if (ORIGIN_TAG_QUERY((size_t)lastLnk)) return * 0p;
385 tytagref( tLinks, dlink(tE) ) lastLnkTagged = {*lastLnk};
386 return downcast$( lastLnkTagged );
387 }
388
[6c58850]389 static inline bool isEmpty( dlist(tE, tLinks) & lst ) {
[7806f91]390 verify (&lst != 0p);
[6c58850]391 if ( & first(lst) == 0p || & last(lst) == 0p ) {
392 verify( & last(lst) == 0p && & last(lst) == 0p );
[7806f91]393 return true;
394 }
395 return false;
396 }
397
[6c58850]398 static inline bool isListed( tE & e ) {
[7806f91]399 NOLOOSE(
400 verify (&e != 0p);
401 verify(! ORIGIN_TAG_QUERY( (size_t) & e ));
402 dlink(tE) & e_links = e`inner;
403 dlink(tE) * lprev = (dlink(tE)*) ORIGIN_TAG_CLEAR((size_t) e_links.prev);
404 dlink(tE) * lnext = (dlink(tE)*) ORIGIN_TAG_CLEAR((size_t) e_links.next);
405 return ( lprev != &e_links ) || ( lnext != &e_links );
406 )
407 LOOSEONLY(
408 verify(false && "isListed is undefined");
409 return true;
410 )
411 }
412
[6c58850]413 static inline tE & iter( dlist(tE, tLinks) & lst ) {
[7806f91]414 tE * origin = $get_list_origin_addr( lst );
415 return *origin;
416 }
417
418
419 // todo: resolve the pun:
420 // tag as in proxy (tytagref)
421 // tag as in bit manipulation on a funny pointer
422
[6c58850]423 static inline bool advance( tE && refx ) {
[7806f91]424 tE && ref_inner = refx;
425 tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
426 verify (& oldReferent != 0p);
427 dlink(tE) * tgt = oldReferent`inner.next;
428 size_t tgt_tags = ORIGIN_TAG_QUERY( (size_t)tgt);
429 dlink(tE) * nextl = (dlink(tE) *)ORIGIN_TAG_CLEAR((size_t)tgt);
430 tytagref( tLinks, dlink(tE) ) nextLnkTagged = { * nextl };
431 tE & nexte = downcast$( nextLnkTagged );
432 size_t next_te_num = (size_t) & nexte;
433 size_t new_ref_inner_num = ORIGIN_TAG_ASGN(next_te_num, tgt_tags);
434 tE * new_ref_inner = (tE *) new_ref_inner_num;
435 &ref_inner = new_ref_inner;
436 return ! tgt_tags;
437 }
438
[6c58850]439 static inline bool recede( tE && refx ) {
[7806f91]440 tE && ref_inner = refx;
441 tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
442 verify (& oldReferent != 0p);
443 dlink(tE) * tgt = oldReferent`inner.prev;
444 size_t tgt_tags = ORIGIN_TAG_QUERY( (size_t)tgt);
445 dlink(tE) * prevl = (dlink(tE) *)ORIGIN_TAG_CLEAR((size_t)tgt);
446 tytagref( tLinks, dlink(tE) ) prevLnkTagged = { * prevl };
447 tE & preve = downcast$( prevLnkTagged );
448 size_t prev_te_num = (size_t) & preve;
449 size_t new_ref_inner_num = ORIGIN_TAG_ASGN(prev_te_num, tgt_tags);
450 tE * new_ref_inner = (tE *) new_ref_inner_num;
451 &ref_inner = new_ref_inner;
452 return ! tgt_tags;
453 }
454
[6c58850]455 bool isFirst( tE & node ) {
456 // Probable bug copied from master
457 // should be `! recede(node)`
458 // correct: "is first iff cannot recede"
459 // used backward in test suite too, probably victim of a grep rename
460 return recede( node );
[7806f91]461 }
462
[6c58850]463 bool isLast( tE & node ) {
464 // ditto, vice versa
465 return advance( node );
[7806f91]466 }
467
468 static inline tE & next( tE & e ) {
[6c58850]469 if( advance(e) ) return e;
[7806f91]470 return * 0p;
471 }
472
473 static inline tE & prev( tE & e ) {
[6c58850]474 if( recede(e) ) return e;
[7806f91]475 return * 0p;
476 }
477
478 // Next 4 headed operations:
479 // Manual inline of the equivalent headless operation, manually simplified.
480 // Applies knowledge of tag pattern around head (unknown to optimizer) to reduce runtime tag operations.
481
482 static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) {
483 dlink(tE) & linkToInsert = e`inner;
484 verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.prev));
485 verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.next));
486 verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.prev) == (size_t)&linkToInsert);
487 verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.next) == (size_t)&linkToInsert);
488 dlink(tE) & list_pos_links = lst;
489 asm( "" : : : "memory" );
490 size_t list_pos_links_num = (size_t)(& list_pos_links);
491 size_t to_insert_prev_num = ORIGIN_TAG_ENABL(list_pos_links_num);
492 dlink(tE) * to_insert_prev = (dlink(tE)*)to_insert_prev_num;
493 linkToInsert.prev = to_insert_prev;
494 linkToInsert.next = list_pos_links.next;
495 dlink(tE) & afterLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.next );
496 size_t linkToInsert_num = (size_t)(& linkToInsert);
497 size_t afterLinks_prev_num = linkToInsert_num;
498 afterLinks.prev = (dlink(tE)*)(afterLinks_prev_num);
499 list_pos_links.next = &linkToInsert;
500 asm( "" : : : "memory" );
501 }
502
503 static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) {
[6c58850]504 // insert_before(iter(lst), e);
[7806f91]505 dlink(tE) & linkToInsert = e`inner;
506 verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.next));
507 verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.prev));
508 verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.next) == (size_t)&linkToInsert);
509 verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.prev) == (size_t)&linkToInsert);
510 dlink(tE) & list_pos_links = lst;
511 asm( "" : : : "memory" );
512 size_t list_pos_links_num = (size_t)(& list_pos_links);
513 size_t to_insert_next_num = ORIGIN_TAG_ENABL(list_pos_links_num);
514 dlink(tE) * to_insert_next = (dlink(tE)*)to_insert_next_num;
515 linkToInsert.next = to_insert_next;
516 linkToInsert.prev = list_pos_links.prev;
517 dlink(tE) & beforeLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.prev );
518 size_t linkToInsert_num = (size_t)(& linkToInsert);
519 size_t beforeLinks_next_num = linkToInsert_num;
520 beforeLinks.next = (dlink(tE)*)(beforeLinks_next_num);
521 list_pos_links.prev = &linkToInsert;
522 asm( "" : : : "memory" );
523 }
524
525 static inline tE & remove_first( dlist(tE, tLinks) &lst ) {
526 verify (&lst != 0p);
[6c58850]527 dlink(tE) & list_links = lst;
[8f448e0]528 verify (! ORIGIN_TAG_QUERY( (size_t) (& list_links) ) );
529 // call is valid on empty list; when so, list_links.next and after_links.prev have otags set
[7806f91]530
[8f448e0]531 dlink(tE) & fst_raw = * list_links.next;
532 dlink(tE) & fst_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & fst_raw );
533 size_t fst_tagval = origin_tag_query_arith$( fst_raw );
[7806f91]534
[6c58850]535 dlink(tE) & after_raw = * fst_links.next;
[7806f91]536 dlink(tE) & after_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
537
538 size_t before_links_next_rslt = ((size_t) & after_raw);
[6c58850]539 size_t after_links_prev_rslt = ORIGIN_TAG_ENABL( (size_t) & list_links );
540 list_links.next = (dlink(tE) *) before_links_next_rslt;
[7806f91]541 after_links.prev = (dlink(tE) *) after_links_prev_rslt;
542
543 asm( "" : : : "memory" );
[6c58850]544 size_t list_pos_links_num = (size_t) &fst_links;
[7806f91]545 size_t list_pos_links_tagged_num = ORIGIN_TAG_ENABL( list_pos_links_num );
[6c58850]546 fst_links.next = fst_links.prev = (dlink(tE)*) list_pos_links_tagged_num;
[7806f91]547 asm( "" : : : "memory" );
548
[8f448e0]549 tytagref( tLinks, dlink(tE) ) retExt = { fst_links };
550 return nullif$( downcast$( retExt ), fst_tagval );
[7806f91]551 }
552
553 static inline tE & remove_last( dlist(tE, tLinks) &lst ) {
554 verify (&lst != 0p);
[6c58850]555 dlink(tE) & list_links = lst;
[8f448e0]556 // call is valid on empty list; when so, list_links.prev and before_links.next have otags set
[7806f91]557
[8f448e0]558 dlink(tE) & last_raw = * list_links.prev;
559 dlink(tE) & last_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & last_raw );
560 size_t last_tagval = origin_tag_query_arith$( last_raw );
[7806f91]561
[6c58850]562 dlink(tE) & before_raw = * last_links.prev;
[7806f91]563 dlink(tE) & before_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
564
565 size_t after_links_prev_rslt = ((size_t) & before_raw);
[6c58850]566 size_t before_links_next_rslt = ORIGIN_TAG_ENABL( (size_t) & list_links );
567 list_links.prev = (dlink(tE) *) after_links_prev_rslt;
[7806f91]568 before_links.next = (dlink(tE) *) before_links_next_rslt;
569
570 asm( "" : : : "memory" );
[6c58850]571 size_t list_pos_links_num = (size_t) &last_links;
[7806f91]572 size_t list_pos_links_tagged_num = ORIGIN_TAG_ENABL( list_pos_links_num );
[6c58850]573 last_links.prev = last_links.next = (dlink(tE)*) list_pos_links_tagged_num;
[7806f91]574 asm( "" : : : "memory" );
575
[8f448e0]576 tytagref( tLinks, dlink(tE) ) lpLnkTagged = { last_links };
577 return nullif$( downcast$( lpLnkTagged ), last_tagval );
[7806f91]578 }
579
[6c58850]580 static inline tE & try_pop_first( dlist(tE, tLinks) &lst ) {
581 tE & first_inlist = first(lst);
[7806f91]582 tE & first_item = first_inlist;
583 if (&first_item) remove(first_inlist); // TODO: should it use pop_front?
584 return first_item;
585 }
586
[6c58850]587 static inline tE & try_pop_last( dlist(tE, tLinks) &lst ) {
588 tE & last_inlist = last(lst);
[7806f91]589 tE & last_item = last_inlist;
590 if (&last_item) remove(last_inlist); // TODO: should it use pop_back?
591 return last_item;
592 }
593
594
595 #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
596 static bool $validate_fwd( dlist(tE, tLinks) & this ) {
597 tE & lagElem = *0p;
598
[6c58850]599 while ( tE & it = iter(this); advance(it) ) {
600 if (& lagElem == 0p && &it != & first(this) ) return false;
[7806f91]601 & lagElem = & it;
602 }
603
[6c58850]604 if (& lagElem != & last(this)) return false;
[7806f91]605
[6c58850]606 // TODO: verify that it is back at iter(this);
[7806f91]607 return true;
608 }
609 static bool $validate_rev( dlist(tE, tLinks) & this ) {
610 tE & lagElem = *0p;
611
[6c58850]612 while ( tE & it = iter(this); recede(it) ) {
613 if (& lagElem == 0p && &it != & last(this) ) return false;
[7806f91]614 & lagElem = & it;
615 }
616
[6c58850]617 if (& lagElem != & first(this)) return false;
[7806f91]618
[6c58850]619 // TODO: verify that it is back at iter(this);
[7806f91]620 return true;
621 }
622 static inline bool validate( dlist(tE, tLinks) & this ) {
[6c58850]623 bool reportsHavingFirst = ((& first(this)) == 0p);
624 bool reportsHavingLast = ((& last(this)) == 0p);
[7806f91]625 if ( reportsHavingFirst != reportsHavingLast ) return false;
626
627 return $validate_fwd(this) && $validate_rev(this);
628 }
629 #endif
630
631}
632
Note: See TracBrowser for help on using the repository browser.