source: libcfa/src/containers/list.hfa

Last change on this file was c2794b2, checked in by Michael Brooks <mlbrooks@…>, 14 months ago

Adding isListed accessor function to new linked list.

  • 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 &)
31static inline tytagref(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_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos );
128        dlink(tE) & list_pos_links = list_pos_elem`inner;
129        asm( "" : : : "memory" );
130        tE & after_raw = * list_pos_links.next;
131        tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
132                linkToInsert.prev = & list_pos;
133                linkToInsert.next = & after_raw;
134        dlink(tE) & afterLinks = after_elem`inner;
135        afterLinks.prev = &to_insert;
136                list_pos_links.next = &to_insert;
137        asm( "" : : : "memory" );
138        }
139
140        static inline void insert_before(tE & list_pos, tE &to_insert) {
141                verify (&list_pos != 0p);
142                verify (&to_insert != 0p);
143        dlink(tE) & linkToInsert = to_insert`inner;
144                verify(linkToInsert.next == 0p);
145                verify(linkToInsert.prev == 0p);
146        tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos );
147        dlink(tE) & list_pos_links = list_pos_elem`inner;
148        asm( "" : : : "memory" );
149        tE & before_raw = * (list_pos_links).prev;
150        tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
151                linkToInsert.next = & list_pos;
152                linkToInsert.prev = & before_raw;
153        dlink(tE) & beforeLinks = before_elem`inner;
154        beforeLinks.next = &to_insert;
155                (list_pos_links).prev = &to_insert;
156        asm( "" : : : "memory" );
157        }
158
159        static inline tE & remove(tE & list_pos) {
160                verify (&list_pos != 0p);
161        verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos) );
162        dlink(tE) & list_pos_links = list_pos`inner;
163        tE & before_raw = * list_pos_links.prev;
164        tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
165        dlink(tE) & before_links = before_elem`inner;
166        tE & after_raw = * list_pos_links.next;
167        tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
168        dlink(tE) & after_links = after_elem`inner;
169        before_links.next = &after_raw;
170        after_links.prev = &before_raw;
171        asm( "" : : : "memory" );
172                list_pos_links.prev = 0p;
173                list_pos_links.next = 0p;
174        asm( "" : : : "memory" );
175        return list_pos;
176        }
177
178    static inline tE & ?`first( dlist(tE, tLinks) &lst ) {
179        tE * firstPtr = lst.next;
180        if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
181        return *firstPtr;
182    }
183    static inline tE & ?`last ( dlist(tE, tLinks) &lst ) {
184        tE * lastPtr = lst.prev;
185        if (ORIGIN_TAG_QUERY((size_t)lastPtr)) lastPtr = 0p;
186        return *lastPtr;
187    }
188
189    static inline bool ?`isEmpty( dlist(tE, tLinks) & lst ) {
190        tE * firstPtr = lst.next;
191        if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
192        return firstPtr == 0p;
193    }
194
195    static inline bool ?`isListed( tE & e ) {
196                verify (&e != 0p);
197        dlink(tE) & e_links = e`inner;
198                return (e_links.prev != 0p) || (e_links.next != 0p);
199    }
200
201    static inline tE & ?`elems( dlist(tE, tLinks) & lst ) {
202        tE * origin = $get_list_origin_addr( lst );
203        return *origin;
204    }
205
206    static inline bool ?`moveNext( tE && refx ) {
207        tE && ref_inner = refx;
208        tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
209        &ref_inner = oldReferent`inner.next;
210        return &ref_inner != 0p  &&
211            ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
212    }
213
214    static inline bool ?`movePrev( tE && refx ) {
215        tE && ref_inner = refx;
216        tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
217        &ref_inner = oldReferent`inner.prev;
218        return &ref_inner != 0p  &&
219            ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
220    }
221
222    static inline bool ?`hasNext( tE & e ) {
223        return e`moveNext;
224    }
225
226    static inline bool ?`hasPrev( tE & e ) {
227        return e`movePrev;
228    }
229
230    static inline tE & ?`next( tE & e ) {
231        if( e`moveNext ) return e;
232        return * 0p;
233    }
234
235    static inline tE & ?`prev( tE & e ) {
236        if( e`movePrev ) return e;
237        return * 0p;
238    }
239
240    static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) {
241        insert_after(lst`elems, e);
242    }
243
244    static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) {
245        insert_before(lst`elems, e);
246    }
247
248    static inline tE & try_pop_front( dlist(tE, tLinks) &lst ) {
249        tE & first_inlist = lst`first;
250        tE & first_item = first_inlist;
251        if (&first_item) remove(first_inlist);
252        return first_item;
253    }
254
255    static inline tE & try_pop_back( dlist(tE, tLinks) &lst ) {
256        tE & last_inlist = lst`last;
257        tE & last_item = last_inlist;
258        if (&last_item) remove(last_inlist);
259        return last_item;
260    }
261
262
263  #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
264        static bool $validate_fwd( dlist(tE, tLinks) & this ) {
265        if ( ! & this`first ) return ( (& this`last) == 0p);
266
267        tE & lagElem = *0p;
268
269        while ( tE & it = this`elems; it`moveNext ) {
270            if (& lagElem == 0p &&  &it != & this`first ) return false;
271            & lagElem = & it;
272        }
273
274        if (& lagElem != & this`last) return false;
275
276        // TODO: verify that it is back at this`elems;
277        return true;
278        }
279        static bool $validate_rev( dlist(tE, tLinks) & this ) {
280        if ( ! & this`last ) return ( (& this`first) == 0p);
281
282        tE & lagElem = *0p;
283
284        while ( tE & it = this`elems; it`movePrev ) {
285            if (& lagElem == 0p &&  &it != & this`last ) return false;
286            & lagElem = & it;
287        }
288
289        if (& lagElem != & this`first) return false;
290
291        // TODO: verify that it is back at this`elems;
292        return true;
293        }
294        static bool validate( dlist(tE, tLinks) & this ) {
295                return $validate_fwd(this) && $validate_rev(this);
296        }
297  #endif
298
299}
300
Note: See TracBrowser for help on using the repository browser.