source: libcfa/src/collections/list.hfa @ 433e2c3

Last change on this file since 433e2c3 was 55b060d, checked in by Peter A. Buhr <pabuhr@…>, 15 months ago

rename directories containers to collections
  • Property mode set to 100644
File size: 10.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 : Peter A. Buhr
12// Last Modified On : Thu Feb  2 11:32:26 2023
13// Update Count     : 2
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 ) \
69   (struct { tytagref(MID, INNER) ( * ?`inner ) ( OUTER & ); }){ ?`inner }
70
71#define DLINK_VIA( TE, TLINK ) \
72   EMBEDDED_VIA( TE, TLINK, dlink(TE) )
73
74
75// The origin is the position encountered at the start of iteration,
76// signifying, "need to advance to the first element," and at the end
77// of iteration, signifying, "no more elements."  Normal comsumption of
78// an iterator runs ?`moveNext as the first step, and uses the return
79// of ?`moveNext as a guard, before dereferencing the iterator.  So
80// normal consumption of an iterator does not dereference an iterator
81// in origin position.  The value of a pointer (underlying a refence)
82// that is exposed publicly as an iteraor, and also a pointer stored
83// internally in a link field, is tagged, to indicate "is the origin"
84// (internally, is the list-head sentinel node), or untagged, to indicate
85// "is a regular node."  Intent is to help a user who dereferences an
86// iterator in origin position (which would be an API-use error on their
87// part), by failing fast.
88
89#if defined( __x86_64 )
90    // Preferred case: tag in the most-significant bit.  Dereference
91    // has been shown to segfault consistently.  Maintenance should
92    // list more architectures as "ok" here, to let them use the
93    // preferred case, when valid.
94    #define ORIGIN_TAG_BITNO ( 8 * sizeof( size_t ) - 1 )
95#else
96    // Fallback case: tag in the least-significant bit.  Dereference
97    // will often give an alignment error, but may not, e.g. if
98    // accessing a char-typed member.  32-bit x86 uses the most-
99    // significant bit for real room on the heap.
100    #define ORIGIN_TAG_BITNO 0
101#endif
102#define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO)
103
104#define ORIGIN_TAG_SET(p)   ((p) |  ORIGIN_TAG_MASK)
105#define ORIGIN_TAG_CLEAR(p) ((p) & ~ORIGIN_TAG_MASK)
106#define ORIGIN_TAG_QUERY(p) ((p) &  ORIGIN_TAG_MASK)
107
108
109forall( tE & ) {
110
111    struct dlink{
112        tE *next;
113        tE *prev;
114    };
115
116    static inline void ?{}( dlink(tE) & this ) {
117        this.next = 0p;
118        this.prev = 0p;
119    }
120
121    forall( tLinks & = dlink(tE) )
122    struct dlist {
123        inline dlink(tE);
124    };
125
126    forall( tLinks & | embedded( tE, tLinks, dlink(tE) ) ) {
127        static inline tE * $get_list_origin_addr( dlist(tE, tLinks) & lst ) {
128            dlink(tE) & link_from_null = ( * (tE *) 0p )`inner;
129            ptrdiff_t link_offset = (ptrdiff_t) & link_from_null;
130            size_t origin_addr = ((size_t) & lst) - link_offset;
131            size_t preResult = ORIGIN_TAG_SET( origin_addr );
132            return (tE *)preResult;
133        }
134
135        static inline void ?{}( dlist(tE, tLinks) & this ) {
136            tE * listOrigin = $get_list_origin_addr( this );
137            ( ( dlink(tE) & ) this ){ listOrigin, listOrigin } ;
138        }
139    }
140
141}
142
143
144forall( tE &, tLinks & | embedded( tE, tLinks, dlink(tE) ) ) {
145
146        static inline void insert_after(tE & list_pos, tE &to_insert) {
147                verify (&list_pos != 0p);
148                verify (&to_insert != 0p);
149        dlink(tE) & linkToInsert = to_insert`inner;
150                verify(linkToInsert.prev == 0p);
151                verify(linkToInsert.next == 0p);
152        tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos );
153        dlink(tE) & list_pos_links = list_pos_elem`inner;
154        asm( "" : : : "memory" );
155        tE & after_raw = * list_pos_links.next;
156        tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
157                linkToInsert.prev = & list_pos;
158                linkToInsert.next = & after_raw;
159        dlink(tE) & afterLinks = after_elem`inner;
160        afterLinks.prev = &to_insert;
161                list_pos_links.next = &to_insert;
162        asm( "" : : : "memory" );
163        }
164
165        static inline void insert_before(tE & list_pos, tE &to_insert) {
166                verify (&list_pos != 0p);
167                verify (&to_insert != 0p);
168        dlink(tE) & linkToInsert = to_insert`inner;
169                verify(linkToInsert.next == 0p);
170                verify(linkToInsert.prev == 0p);
171        tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos );
172        dlink(tE) & list_pos_links = list_pos_elem`inner;
173        asm( "" : : : "memory" );
174        tE & before_raw = * (list_pos_links).prev;
175        tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
176                linkToInsert.next = & list_pos;
177                linkToInsert.prev = & before_raw;
178        dlink(tE) & beforeLinks = before_elem`inner;
179        beforeLinks.next = &to_insert;
180                (list_pos_links).prev = &to_insert;
181        asm( "" : : : "memory" );
182        }
183
184        static inline tE & remove(tE & list_pos) {
185                verify (&list_pos != 0p);
186        verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos) );
187        dlink(tE) & list_pos_links = list_pos`inner;
188        tE & before_raw = * list_pos_links.prev;
189        tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
190        dlink(tE) & before_links = before_elem`inner;
191        tE & after_raw = * list_pos_links.next;
192        tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
193        dlink(tE) & after_links = after_elem`inner;
194        before_links.next = &after_raw;
195        after_links.prev = &before_raw;
196        asm( "" : : : "memory" );
197                list_pos_links.prev = 0p;
198                list_pos_links.next = 0p;
199        asm( "" : : : "memory" );
200        return list_pos;
201        }
202
203    static inline tE & ?`first( dlist(tE, tLinks) &lst ) {
204        tE * firstPtr = lst.next;
205        if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
206        return *firstPtr;
207    }
208    static inline tE & ?`last ( dlist(tE, tLinks) &lst ) {
209        tE * lastPtr = lst.prev;
210        if (ORIGIN_TAG_QUERY((size_t)lastPtr)) lastPtr = 0p;
211        return *lastPtr;
212    }
213
214    static inline bool ?`isEmpty( dlist(tE, tLinks) & lst ) {
215        tE * firstPtr = lst.next;
216        if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
217        return firstPtr == 0p;
218    }
219
220    static inline bool ?`isListed( tE & e ) {
221                verify (&e != 0p);
222        dlink(tE) & e_links = e`inner;
223                return (e_links.prev != 0p) || (e_links.next != 0p);
224    }
225
226    static inline tE & ?`elems( dlist(tE, tLinks) & lst ) {
227        tE * origin = $get_list_origin_addr( lst );
228        return *origin;
229    }
230
231    static inline bool ?`moveNext( tE && refx ) {
232        tE && ref_inner = refx;
233        tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
234        &ref_inner = oldReferent`inner.next;
235        return &ref_inner != 0p  &&
236            ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
237    }
238
239    static inline bool ?`movePrev( tE && refx ) {
240        tE && ref_inner = refx;
241        tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
242        &ref_inner = oldReferent`inner.prev;
243        return &ref_inner != 0p  &&
244            ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
245    }
246
247    static inline bool ?`hasNext( tE & e ) {
248        return e`moveNext;
249    }
250
251    static inline bool ?`hasPrev( tE & e ) {
252        return e`movePrev;
253    }
254
255    static inline tE & ?`next( tE & e ) {
256        if( e`moveNext ) return e;
257        return * 0p;
258    }
259
260    static inline tE & ?`prev( tE & e ) {
261        if( e`movePrev ) return e;
262        return * 0p;
263    }
264
265    static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) {
266        insert_after(lst`elems, e);
267    }
268
269    static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) {
270        insert_before(lst`elems, e);
271    }
272
273    static inline tE & try_pop_front( dlist(tE, tLinks) &lst ) {
274        tE & first_inlist = lst`first;
275        tE & first_item = first_inlist;
276        if (&first_item) remove(first_inlist);
277        return first_item;
278    }
279
280    static inline tE & try_pop_back( dlist(tE, tLinks) &lst ) {
281        tE & last_inlist = lst`last;
282        tE & last_item = last_inlist;
283        if (&last_item) remove(last_inlist);
284        return last_item;
285    }
286
287
288  #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
289        static bool $validate_fwd( dlist(tE, tLinks) & this ) {
290        if ( ! & this`first ) return ( (& this`last) == 0p);
291
292        tE & lagElem = *0p;
293
294        while ( tE & it = this`elems; it`moveNext ) {
295            if (& lagElem == 0p &&  &it != & this`first ) return false;
296            & lagElem = & it;
297        }
298
299        if (& lagElem != & this`last) return false;
300
301        // TODO: verify that it is back at this`elems;
302        return true;
303        }
304        static bool $validate_rev( dlist(tE, tLinks) & this ) {
305        if ( ! & this`last ) return ( (& this`first) == 0p);
306
307        tE & lagElem = *0p;
308
309        while ( tE & it = this`elems; it`movePrev ) {
310            if (& lagElem == 0p &&  &it != & this`last ) return false;
311            & lagElem = & it;
312        }
313
314        if (& lagElem != & this`first) return false;
315
316        // TODO: verify that it is back at this`elems;
317        return true;
318        }
319        static bool validate( dlist(tE, tLinks) & this ) {
320                return $validate_fwd(this) && $validate_rev(this);
321        }
322  #endif
323
324}
325
Note: See TracBrowser for help on using the repository browser.