source: libcfa/src/containers/list.hfa @ 858350a

ADTast-experimental
Last change on this file since 858350a was 8a97248, checked in by Peter A. Buhr <pabuhr@…>, 21 months ago

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