Context Navigation

libcfa-fork-list.hfa

Visit:

Last change on this file was 6c58850, checked in by Michael Brooks <mlbrooks@…>, 8 weeks ago

Revise data in linked-list plots with streamlined harness and data from runs on swift.

No change to text discussing the plots, so some of that discussion is now stale.

Harness changes allow more ifdef feature disabling and eliminate side-array usage, keeping all per-node harness state inside the list nodes.

Completely disable the interleaving experiment, which was not giving discernable data.

Property mode set to 100644

File size: 22.8 KB

Line
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
29	forall( Decorator &, T & )
30	struct tytagref {
31	inline T &;
32	};
33
34	forall( tOuter &, tMid &, tInner & )
35	trait embedded {
36	tytagref( tMid, tInner ) ?`inner( tOuter & );
37	};
38
39	// embedded is reflexive, with no info (void) as the type tag
40	forall (T &)
41	static 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
86	// an iterator runs advance as the first step, and uses the return
87	// of advance as a guard, before dereferencing the iterator. So
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
182	forall( 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
241
242	forall( tE &, tLinks & \| embedded( tE, tLinks, dlink(tE) ) ) {
243
244	static inline void insert_after(tE & list_pos, tE &to_insert) {
245	size_t list_pos_tag = ORIGIN_TAG_QUERY((size_t) & list_pos); // a request to insert after the origin is fine
246	tE & list_pos_real = * (tE *) ORIGIN_TAG_CLEAR((size_t) & list_pos);
247	verify (&list_pos_real != 0p);
248
249	verify (&to_insert != 0p);
250	NOLOOSE(
251	verify(! ORIGIN_TAG_QUERY((size_t) & to_insert));
252	)
253	dlink(tE) & linkToInsert = to_insert`inner;
254	NOLOOSE(
255	verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.prev));
256	verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.next));
257	verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.prev) == (size_t)&linkToInsert);
258	verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.next) == (size_t)&linkToInsert);
259	)
260	dlink(tE) & list_pos_links = list_pos_real`inner;
261	asm( "" : : : "memory" );
262	size_t list_pos_links_num = (size_t)(& list_pos_links);
263	size_t to_insert_prev_num = ORIGIN_TAG_ASGN(list_pos_links_num, list_pos_tag);
264	dlink(tE) * to_insert_prev = (dlink(tE)*)to_insert_prev_num;
265	linkToInsert.prev = to_insert_prev;
266	linkToInsert.next = list_pos_links.next;
267	dlink(tE) & afterLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.next );
268	size_t afterLinks_prev_tag = ORIGIN_TAG_QUERY((size_t)afterLinks.prev);
269	size_t linkToInsert_num = (size_t)(& linkToInsert);
270	size_t afterLinks_prev_num = ORIGIN_TAG_ASGN(linkToInsert_num, ORIGIN_TAG_NEQ(list_pos_tag, afterLinks_prev_tag));
271	afterLinks.prev = (dlink(tE)*)(afterLinks_prev_num);
272	list_pos_links.next = &linkToInsert;
273	asm( "" : : : "memory" );
274	}
275
276	static inline void insert_before(tE & list_pos, tE &to_insert) {
277	size_t list_pos_tag = ORIGIN_TAG_QUERY((size_t) & list_pos); // a request to insert before the origin is fine
278	tE & list_pos_real = * (tE *) ORIGIN_TAG_CLEAR((size_t) & list_pos);
279	verify (&list_pos_real != 0p);
280
281	verify (&to_insert != 0p);
282	NOLOOSE(
283	verify(! ORIGIN_TAG_QUERY((size_t) & to_insert));
284	)
285	dlink(tE) & linkToInsert = to_insert`inner;
286	NOLOOSE(
287	verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.prev));
288	verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.next));
289	verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.prev) == (size_t)&linkToInsert);
290	verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.next) == (size_t)&linkToInsert);
291	)
292	dlink(tE) & list_pos_links = list_pos_real`inner;
293	asm( "" : : : "memory" );
294	size_t list_pos_links_num = (size_t)(& list_pos_links);
295	size_t to_insert_next_num = ORIGIN_TAG_ASGN(list_pos_links_num, list_pos_tag);
296	dlink(tE) * to_insert_next = (dlink(tE)*)to_insert_next_num;
297	linkToInsert.next = to_insert_next;
298	linkToInsert.prev = list_pos_links.prev;
299	dlink(tE) & beforeLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.prev );
300	size_t beforeLinks_next_tag = ORIGIN_TAG_QUERY((size_t)beforeLinks.next);
301	size_t linkToInsert_num = (size_t)(& linkToInsert);
302	size_t beforeLinks_next_num = ORIGIN_TAG_ASGN(linkToInsert_num, ORIGIN_TAG_NEQ(list_pos_tag, beforeLinks_next_tag));
303	beforeLinks.next = (dlink(tE)*)(beforeLinks_next_num);
304	list_pos_links.prev = &linkToInsert;
305	asm( "" : : : "memory" );
306	}
307
308	static inline tE & remove(tE & list_pos) {
309	verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos) );
310	verify (&list_pos != 0p);
311
312	dlink(tE) & list_pos_links = list_pos`inner;
313	dlink(tE) & before_raw = * list_pos_links.prev;
314	dlink(tE) & before_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
315	size_t before_links_next_tag = ORIGIN_TAG_QUERY( (size_t) (before_links.next) );
316
317	dlink(tE) & after_raw = * list_pos_links.next;
318	dlink(tE) & after_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
319	size_t after_links_prev_tag = ORIGIN_TAG_QUERY( (size_t) (after_links.prev) );
320
321	size_t before_links_next_rslt = ORIGIN_TAG_EITHER( ((size_t) & after_raw), before_links_next_tag );
322	size_t after_links_prev_rslt = ORIGIN_TAG_EITHER( ((size_t) & before_raw), after_links_prev_tag );
323	before_links.next = (dlink(tE) *) before_links_next_rslt;
324	after_links.prev = (dlink(tE) *) after_links_prev_rslt;
325
326	NOLOOSE(
327	asm( "" : : : "memory" );
328	size_t list_pos_links_num = (size_t) &list_pos_links;
329	size_t list_pos_links_tagged_num = ORIGIN_TAG_ENABL( list_pos_links_num );
330	list_pos_links.next = list_pos_links.prev = (dlink(tE)*) list_pos_links_tagged_num;
331	asm( "" : : : "memory" );
332	)
333	return list_pos;
334	}
335
336	static inline tE & downcast$( tytagref( tLinks, dlink(tE) ) ref ) {
337	dlink(tE) & lnk = ref;
338	dlink(tE) & link_from_null = ( * (tE *) 0p )`inner;
339	ptrdiff_t link_offset = (ptrdiff_t) & link_from_null;
340	size_t elm_addr = ((size_t) & lnk) - link_offset;
341	return * (tE*) elm_addr;
342	}
343
344	static inline tE & first( dlist(tE, tLinks) & lst ) {
345	verify (&lst != 0p);
346	dlink(tE) * firstLnk = lst.next;
347	if (ORIGIN_TAG_QUERY((size_t)firstLnk)) return * 0p;
348	tytagref( tLinks, dlink(tE) ) firstLnkTagged = {*firstLnk};
349	return downcast$( firstLnkTagged );
350	}
351	static inline tE & last ( dlist(tE, tLinks) & lst ) {
352	verify (&lst != 0p);
353	dlink(tE) * lastLnk = lst.prev;
354	if (ORIGIN_TAG_QUERY((size_t)lastLnk)) return * 0p;
355	tytagref( tLinks, dlink(tE) ) lastLnkTagged = {*lastLnk};
356	return downcast$( lastLnkTagged );
357	}
358
359	static inline bool isEmpty( dlist(tE, tLinks) & lst ) {
360	verify (&lst != 0p);
361	if ( & first(lst) == 0p \|\| & last(lst) == 0p ) {
362	verify( & last(lst) == 0p && & last(lst) == 0p );
363	return true;
364	}
365	return false;
366	}
367
368	static inline bool isListed( tE & e ) {
369	NOLOOSE(
370	verify (&e != 0p);
371	verify(! ORIGIN_TAG_QUERY( (size_t) & e ));
372	dlink(tE) & e_links = e`inner;
373	dlink(tE) * lprev = (dlink(tE)*) ORIGIN_TAG_CLEAR((size_t) e_links.prev);
374	dlink(tE) * lnext = (dlink(tE)*) ORIGIN_TAG_CLEAR((size_t) e_links.next);
375	return ( lprev != &e_links ) \|\| ( lnext != &e_links );
376	)
377	LOOSEONLY(
378	verify(false && "isListed is undefined");
379	return true;
380	)
381	}
382
383	static inline tE & iter( dlist(tE, tLinks) & lst ) {
384	tE * origin = $get_list_origin_addr( lst );
385	return *origin;
386	}
387
388
389	// todo: resolve the pun:
390	// tag as in proxy (tytagref)
391	// tag as in bit manipulation on a funny pointer
392
393	static inline bool advance( tE && refx ) {
394	tE && ref_inner = refx;
395	tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
396	verify (& oldReferent != 0p);
397	dlink(tE) * tgt = oldReferent`inner.next;
398	size_t tgt_tags = ORIGIN_TAG_QUERY( (size_t)tgt);
399	dlink(tE) * nextl = (dlink(tE) *)ORIGIN_TAG_CLEAR((size_t)tgt);
400	tytagref( tLinks, dlink(tE) ) nextLnkTagged = { * nextl };
401	tE & nexte = downcast$( nextLnkTagged );
402	size_t next_te_num = (size_t) & nexte;
403	size_t new_ref_inner_num = ORIGIN_TAG_ASGN(next_te_num, tgt_tags);
404	tE * new_ref_inner = (tE *) new_ref_inner_num;
405	&ref_inner = new_ref_inner;
406	return ! tgt_tags;
407	}
408
409	static inline bool recede( tE && refx ) {
410	tE && ref_inner = refx;
411	tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
412	verify (& oldReferent != 0p);
413	dlink(tE) * tgt = oldReferent`inner.prev;
414	size_t tgt_tags = ORIGIN_TAG_QUERY( (size_t)tgt);
415	dlink(tE) * prevl = (dlink(tE) *)ORIGIN_TAG_CLEAR((size_t)tgt);
416	tytagref( tLinks, dlink(tE) ) prevLnkTagged = { * prevl };
417	tE & preve = downcast$( prevLnkTagged );
418	size_t prev_te_num = (size_t) & preve;
419	size_t new_ref_inner_num = ORIGIN_TAG_ASGN(prev_te_num, tgt_tags);
420	tE * new_ref_inner = (tE *) new_ref_inner_num;
421	&ref_inner = new_ref_inner;
422	return ! tgt_tags;
423	}
424
425	bool isFirst( tE & node ) {
426	// Probable bug copied from master
427	// should be `! recede(node)`
428	// correct: "is first iff cannot recede"
429	// used backward in test suite too, probably victim of a grep rename
430	return recede( node );
431	}
432
433	bool isLast( tE & node ) {
434	// ditto, vice versa
435	return advance( node );
436	}
437
438	static inline tE & next( tE & e ) {
439	if( advance(e) ) return e;
440	return * 0p;
441	}
442
443	static inline tE & prev( tE & e ) {
444	if( recede(e) ) return e;
445	return * 0p;
446	}
447
448	// Next 4 headed operations:
449	// Manual inline of the equivalent headless operation, manually simplified.
450	// Applies knowledge of tag pattern around head (unknown to optimizer) to reduce runtime tag operations.
451
452	static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) {
453	dlink(tE) & linkToInsert = e`inner;
454	verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.prev));
455	verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.next));
456	verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.prev) == (size_t)&linkToInsert);
457	verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.next) == (size_t)&linkToInsert);
458	dlink(tE) & list_pos_links = lst;
459	asm( "" : : : "memory" );
460	size_t list_pos_links_num = (size_t)(& list_pos_links);
461	size_t to_insert_prev_num = ORIGIN_TAG_ENABL(list_pos_links_num);
462	dlink(tE) * to_insert_prev = (dlink(tE)*)to_insert_prev_num;
463	linkToInsert.prev = to_insert_prev;
464	linkToInsert.next = list_pos_links.next;
465	dlink(tE) & afterLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.next );
466	size_t linkToInsert_num = (size_t)(& linkToInsert);
467	size_t afterLinks_prev_num = linkToInsert_num;
468	afterLinks.prev = (dlink(tE)*)(afterLinks_prev_num);
469	list_pos_links.next = &linkToInsert;
470	asm( "" : : : "memory" );
471	}
472
473	static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) {
474	// insert_before(iter(lst), e);
475	dlink(tE) & linkToInsert = e`inner;
476	verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.next));
477	verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.prev));
478	verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.next) == (size_t)&linkToInsert);
479	verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.prev) == (size_t)&linkToInsert);
480	dlink(tE) & list_pos_links = lst;
481	asm( "" : : : "memory" );
482	size_t list_pos_links_num = (size_t)(& list_pos_links);
483	size_t to_insert_next_num = ORIGIN_TAG_ENABL(list_pos_links_num);
484	dlink(tE) * to_insert_next = (dlink(tE)*)to_insert_next_num;
485	linkToInsert.next = to_insert_next;
486	linkToInsert.prev = list_pos_links.prev;
487	dlink(tE) & beforeLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.prev );
488	size_t linkToInsert_num = (size_t)(& linkToInsert);
489	size_t beforeLinks_next_num = linkToInsert_num;
490	beforeLinks.next = (dlink(tE)*)(beforeLinks_next_num);
491	list_pos_links.prev = &linkToInsert;
492	asm( "" : : : "memory" );
493	}
494
495	static inline tE & remove_first( dlist(tE, tLinks) &lst ) {
496	verify (&lst != 0p);
497	dlink(tE) & list_links = lst;
498	verify (! ORIGIN_TAG_QUERY( (size_t) (list_links.next) ) );
499
500	dlink(tE) & fst_links = * list_links.next;
501
502	dlink(tE) & after_raw = * fst_links.next;
503	dlink(tE) & after_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
504	verify( ! ORIGIN_TAG_QUERY( (size_t) (after_links.prev) ) );
505
506	size_t before_links_next_rslt = ((size_t) & after_raw);
507	size_t after_links_prev_rslt = ORIGIN_TAG_ENABL( (size_t) & list_links );
508	list_links.next = (dlink(tE) *) before_links_next_rslt;
509	after_links.prev = (dlink(tE) *) after_links_prev_rslt;
510
511	asm( "" : : : "memory" );
512	size_t list_pos_links_num = (size_t) &fst_links;
513	size_t list_pos_links_tagged_num = ORIGIN_TAG_ENABL( list_pos_links_num );
514	fst_links.next = fst_links.prev = (dlink(tE)*) list_pos_links_tagged_num;
515	asm( "" : : : "memory" );
516
517	tytagref( tLinks, dlink(tE) ) lpLnkTagged = {fst_links};
518	return downcast$( lpLnkTagged );
519	}
520
521	static inline tE & remove_last( dlist(tE, tLinks) &lst ) {
522	verify (&lst != 0p);
523	dlink(tE) & list_links = lst;
524	verify (! ORIGIN_TAG_QUERY( (size_t) (list_links.prev) ) );
525
526	dlink(tE) & last_links = * list_links.prev;
527
528	dlink(tE) & before_raw = * last_links.prev;
529	dlink(tE) & before_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
530	verify( ! ORIGIN_TAG_QUERY( (size_t) (before_links.next) ) );
531
532	size_t after_links_prev_rslt = ((size_t) & before_raw);
533	size_t before_links_next_rslt = ORIGIN_TAG_ENABL( (size_t) & list_links );
534	list_links.prev = (dlink(tE) *) after_links_prev_rslt;
535	before_links.next = (dlink(tE) *) before_links_next_rslt;
536
537	asm( "" : : : "memory" );
538	size_t list_pos_links_num = (size_t) &last_links;
539	size_t list_pos_links_tagged_num = ORIGIN_TAG_ENABL( list_pos_links_num );
540	last_links.prev = last_links.next = (dlink(tE)*) list_pos_links_tagged_num;
541	asm( "" : : : "memory" );
542
543	tytagref( tLinks, dlink(tE) ) lpLnkTagged = {last_links};
544	return downcast$( lpLnkTagged );
545	}
546
547	static inline tE & try_pop_first( dlist(tE, tLinks) &lst ) {
548	tE & first_inlist = first(lst);
549	tE & first_item = first_inlist;
550	if (&first_item) remove(first_inlist); // TODO: should it use pop_front?
551	return first_item;
552	}
553
554	static inline tE & try_pop_last( dlist(tE, tLinks) &lst ) {
555	tE & last_inlist = last(lst);
556	tE & last_item = last_inlist;
557	if (&last_item) remove(last_inlist); // TODO: should it use pop_back?
558	return last_item;
559	}
560
561
562	#if !defined(NDEBUG) && (defined(__CFA_DEBUG__) \|\| defined(__CFA_VERIFY__))
563	static bool $validate_fwd( dlist(tE, tLinks) & this ) {
564	tE & lagElem = *0p;
565
566	while ( tE & it = iter(this); advance(it) ) {
567	if (& lagElem == 0p && &it != & first(this) ) return false;
568	& lagElem = & it;
569	}
570
571	if (& lagElem != & last(this)) return false;
572
573	// TODO: verify that it is back at iter(this);
574	return true;
575	}
576	static bool $validate_rev( dlist(tE, tLinks) & this ) {
577	tE & lagElem = *0p;
578
579	while ( tE & it = iter(this); recede(it) ) {
580	if (& lagElem == 0p && &it != & last(this) ) return false;
581	& lagElem = & it;
582	}
583
584	if (& lagElem != & first(this)) return false;
585
586	// TODO: verify that it is back at iter(this);
587	return true;
588	}
589	static inline bool validate( dlist(tE, tLinks) & this ) {
590	bool reportsHavingFirst = ((& first(this)) == 0p);
591	bool reportsHavingLast = ((& last(this)) == 0p);
592	if ( reportsHavingFirst != reportsHavingLast ) return false;
593
594	return $validate_fwd(this) && $validate_rev(this);
595	}
596	#endif
597
598	}
599

Note: See TracBrowser for help on using the repository browser.

Download in other formats:

Original Format