source: libcfa/src/containers/list2.hfa @ 8d1ad36

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since 8d1ad36 was 8d1ad36, checked in by Michael Brooks <mlbrooks@…>, 3 years ago

Adding linked-list convenience functions and testing a corner case.

New API: isEmpty, hasPrev, `hasNext, try_pop_front, try_pop_back

Corner case: modifications near `elems (inserting in all n+1 interator states)

  • Property mode set to 100644
File size: 11.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
20extern "C" {
21    void * memset ( void * ptr, int value, size_t num );
22}
23
24trait embedded( tOuter &, tInner & ) {
25    tInner & ?`inner( tOuter & );
26};
27
28// embedded is reflexive
29forall( tX & )
30static inline tX & ?`inner( tX & this ) { return this; }
31
32// use this on every case of plan-9 inheritance, to make embedded a closure of plan-9 inheritance
33#define P9_EMBEDDED( tOuter, tInner ) \
34   static inline tInner & ?`inner( tOuter & this ) { return this; }
35
36
37// The origin is the position encountered at the start of iteration,
38// signifying, "need to advance to the first element," and at the end
39// of iteration, signifying, "no more elements."  Normal comsumption of
40// an iterator runs ?`moveNext as the first step, and uses the return
41// of ?`moveNext as a guard, before dereferencing the iterator.  So
42// normal consumption of an iterator does not dereference an iterator
43// in origin position.  The value of a pointer (underlying a refence)
44// that is exposed publicly as an iteraor, and also a pointer stored
45// internally in a link field, is tagged, to indicate "is the origin"
46// (internally, is the list-head sentinel node), or untagged, to indicate
47// "is a regular node."  Intent is to help a user who dereferences an
48// iterator in origin position (which would be an API-use error on their
49// part), by failing fast.
50
51#if defined( __x86_64 )
52    // Preferred case: tag in the most-significant bit.  Dereference
53    // has been shown to segfault consistently.  Maintenance should
54    // list more architectures as "ok" here, to let them use the
55    // preferred case, when valid.
56    #define ORIGIN_TAG_BITNO ( 8 * sizeof( size_t ) - 1 )
57#else
58    // Fallback case: tag in the least-significant bit.  Dereference
59    // will often give an alignment error, but may not, e.g. if
60    // accessing a char-typed member.  32-bit x86 uses the most-
61    // significant bit for real room on the heap.
62    #define ORIGIN_TAG_BITNO 0
63#endif
64#define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO)
65
66#define ORIGIN_TAG_SET(p)   ((p) |  ORIGIN_TAG_MASK)
67#define ORIGIN_TAG_CLEAR(p) ((p) & ~ORIGIN_TAG_MASK)
68#define ORIGIN_TAG_QUERY(p) ((p) &  ORIGIN_TAG_MASK)
69
70
71forall( tE & ) {
72
73    struct dlink{
74        tE *next;
75        tE *prev;
76    };
77
78    static inline void ?{}( dlink(tE) & this ) {
79        this.next = 0p;
80        this.prev = 0p;
81    }
82
83    forall( tLinks & = tE ) {
84
85        struct dlist {
86            inline dlink(tE);
87        };
88
89        struct diref {
90            inline tE &;
91        };
92    }
93
94    forall( tLinks & = tE | embedded( tE, tLinks ) | embedded( tLinks, dlink(tE) ) ) {
95        static inline tE * $get_list_origin_addr( dlist(tE, tLinks) & lst ) {
96            dlink(tE) & link_from_null = ( * (tE *) 0p )`inner`inner;
97            ptrdiff_t link_offset = (ptrdiff_t) & link_from_null;
98            size_t origin_addr = ((size_t) & lst) - link_offset;
99            size_t preResult = ORIGIN_TAG_SET( origin_addr );
100            return (tE *)preResult;
101        }
102
103        static inline void ?{}( dlist(tE, tLinks) & this ) {
104            tE * listOrigin = $get_list_origin_addr( this );
105            ( ( dlink(tE) & ) this ){ listOrigin, listOrigin } ;
106        }
107
108        // redundant
109        // void ?{}( diref(tE, tLinks) & this, tE & target ) {
110        //     tE && ref = this;
111        //     &ref = &target;
112        // }
113    }
114
115}
116
117
118forall( tE &, tLinks & | embedded( tE, tLinks ) | embedded( tLinks, dlink(tE) ) ) {
119
120        static inline void insert_after(diref(tE, tLinks) list_pos, tE &to_insert) {
121                verify (&list_pos != 0p);
122                verify (&to_insert != 0p);
123        dlink(tE) & linkToInsert = to_insert`inner`inner;
124                verify(linkToInsert.prev == 0p);
125                verify(linkToInsert.next == 0p);
126        tE & list_pos_raw = list_pos;
127        tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos_raw );
128        asm( "" : : : "memory" );
129        tE & after_raw = * (list_pos_elem`inner`inner).next;
130        tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
131                linkToInsert.prev = & list_pos_raw;
132                linkToInsert.next = & after_raw;
133        (after_elem`inner`inner).prev = &to_insert;
134                (list_pos_elem`inner`inner).next = &to_insert;
135        asm( "" : : : "memory" );
136        }
137
138        static inline void insert_before(diref(tE, tLinks) list_pos, tE &to_insert) {
139                verify (&list_pos != 0p);
140                verify (&to_insert != 0p);
141        dlink(tE) & linkToInsert = to_insert`inner`inner;
142                verify(linkToInsert.next == 0p);
143                verify(linkToInsert.prev == 0p);
144        tE & list_pos_raw = list_pos;
145        tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos_raw );
146        asm( "" : : : "memory" );
147        tE & before_raw = * (list_pos_elem`inner`inner).prev;
148        tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
149                linkToInsert.next = & list_pos_raw;
150                linkToInsert.prev = & before_raw;
151        (before_elem`inner`inner).next = &to_insert;
152                (list_pos_elem`inner`inner).prev = &to_insert;
153        asm( "" : : : "memory" );
154        }
155
156        static inline tE & remove(diref(tE, tLinks) list_pos) {
157                verify (&list_pos != 0p);
158        tE & list_pos_elem = list_pos;
159        verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos_elem) );
160        dlink(tE) & list_pos_links = list_pos_elem`inner`inner;
161        tE & before_raw = * list_pos_links.prev;
162        tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
163        dlink(tE) & before_links = before_elem`inner`inner;
164        tE & after_raw = * list_pos_links.next;
165        tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
166        dlink(tE) & after_links = after_elem`inner`inner;
167        before_links.next = &after_raw;
168        after_links.prev = &before_raw;
169        asm( "" : : : "memory" );
170                list_pos_links.prev = 0p;
171                list_pos_links.next = 0p;
172        asm( "" : : : "memory" );
173        return list_pos_elem;
174        }
175
176    static inline diref(tE, tLinks) ?`first( dlist(tE, tLinks) &lst ) {
177        tE * firstPtr = lst.next;
178        if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
179        diref(tE, tLinks) ret = { *firstPtr };
180        return ret;
181    }
182    static inline diref(tE, tLinks) ?`last ( dlist(tE, tLinks) &lst ) {
183        tE * lastPtr = lst.prev;
184        if (ORIGIN_TAG_QUERY((size_t)lastPtr)) lastPtr = 0p;
185        diref(tE, tLinks) ret = { *lastPtr };
186        return ret;
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 int ?!=?( const diref(tE, tLinks) & list_pos, zero_t ) {
196        tE & list_pos_elem = list_pos;
197        if (ORIGIN_TAG_QUERY((size_t) & list_pos_elem)) return 0;
198        return & list_pos_elem != 0p;
199    }
200
201    static inline int DUMB_COMPARE( diref(tE, tLinks) list_pos, tE * elem ) {
202        tE & signifiedLhs = list_pos;
203        return &signifiedLhs == elem;
204    }
205
206    static inline diref(tE, tLinks) ?`from( tE & elem ) {
207        diref(tE, tLinks) ret = { elem };
208        return ret;
209    }
210
211    static inline diref(tE, tLinks) ?`elems( dlist(tE, tLinks) & lst ) {
212        tE * origin = $get_list_origin_addr( lst );
213        diref(tE, tLinks) ret = { *origin };
214        return ret;
215    }
216
217    static inline bool ?`moveNext( diref(tE, tLinks) & refx ) {
218        tE && ref_inner = refx;
219        tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
220        &ref_inner = oldReferent`inner`inner.next;
221        return &ref_inner != 0p  &&
222            ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
223    }
224
225    static inline bool ?`movePrev( diref(tE, tLinks) & refx ) {
226        tE && ref_inner = refx;
227        tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
228        &ref_inner = oldReferent`inner`inner.prev;
229        return &ref_inner != 0p  &&
230            ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
231    }
232
233    static inline bool ?`hasNext( diref(tE, tLinks) refx ) {
234        return refx`moveNext;
235    }
236
237    static inline bool ?`hasPrev( diref(tE, tLinks) refx ) {
238        return refx`movePrev;
239    }
240
241    static inline diref(tE, tLinks) ?`next( diref(tE, tLinks) refx ) {
242        if( refx`moveNext ) return refx;
243        tE && ref_inner = refx;
244        & ref_inner = 0p;
245        return refx;
246    }
247
248    static inline diref(tE, tLinks) ?`prev( diref(tE, tLinks) refx ) {
249        if( refx`movePrev ) return refx;
250        tE && ref_inner = refx;
251        & ref_inner = 0p;
252        return refx;
253    }
254
255    static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) {
256        insert_after(lst`elems, e);
257    }
258
259    static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) {
260        insert_before(lst`elems, e);
261    }
262
263    static inline tE & try_pop_front( dlist(tE, tLinks) &lst ) {
264        diref(tE, tLinks) first_inlist = lst`first;
265        tE & first_item = first_inlist;
266        if (&first_item) remove(first_inlist);
267        return first_item;
268    }
269
270    static inline tE & try_pop_back( dlist(tE, tLinks) &lst ) {
271        diref(tE, tLinks) last_inlist = lst`last;
272        tE & last_item = last_inlist;
273        if (&last_item) remove(last_inlist);
274        return last_item;
275    }
276
277
278  #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
279        static bool $validate_fwd( dlist(tE, tLinks) & this ) {
280        if ( ! & this`first ) return ( (& this`last) == 0p);
281
282        tE & lagElem = *0p;
283
284        while ( diref(tE, tLinks) it = this`elems; it`moveNext ) {
285            if (& lagElem == 0p &&  &it != & this`first ) return false;
286            & lagElem = & it;
287        }
288
289        if (& lagElem != & this`last) return false;
290
291        // TODO: verify that it is back at this`elems;
292        return true;
293        }
294        static bool $validate_rev( dlist(tE, tLinks) & this ) {
295        if ( ! & this`last ) return ( (& this`first) == 0p);
296
297        tE & lagElem = *0p;
298
299        while ( diref(tE, tLinks) it = this`elems; it`movePrev ) {
300            if (& lagElem == 0p &&  &it != & this`last ) return false;
301            & lagElem = & it;
302        }
303
304        if (& lagElem != & this`first) return false;
305
306        // TODO: verify that it is back at this`elems;
307        return true;
308        }
309        static bool validate( dlist(tE, tLinks) & this ) {
310                return $validate_fwd(this) && $validate_rev(this);
311        }
312  #endif
313
314}
315
316forall( tE & | embedded( tE, dlink(tE) ) ) {
317        static inline void insert_after(tE & list_pos, tE &to_insert ) {
318        diref(tE, tE) list_pos_ref = list_pos`from;
319        insert_after( list_pos_ref, to_insert );
320    }
321        static inline void insert_before(tE & list_pos, tE &to_insert ) {
322        diref(tE, tE) list_pos_ref = list_pos`from;
323        insert_before( list_pos_ref, to_insert );
324    }
325        static inline tE & remove(tE & list_pos ) {
326        diref(tE, tE) list_pos_ref = list_pos`from;
327        return remove( list_pos_ref );
328    }
329    static inline bool ?`moveNext( tE && ref ) {
330        diref(tE, tE) & ref_dird = (diref(tE, tE) &) & ref;
331        return ref_dird`moveNext;
332    }
333    static inline bool ?`movePrev( tE && ref ) {
334        diref(tE, tE) & ref_dird = (diref(tE, tE) &) & ref;
335        return ref_dird`movePrev;
336    }
337    static inline bool ?`hasNext( tE & ref ) {
338        diref(tE, tE) ref_dird = { ref };
339        return ref_dird`hasNext;
340    }
341    static inline bool ?`hasPrev( tE & ref ) {
342        diref(tE, tE) ref_dird = { ref };
343        return ref_dird`hasPrev;
344    }
345    static inline tE & ?`next( tE & ref ) {
346        diref(tE, tE) ref_dird = { ref };
347        diref(tE, tE) rslt = ref_dird`next;
348        return rslt;
349    }
350    static inline tE & ?`prev( tE & ref ) {
351        diref(tE, tE) ref_dird = { ref };
352        diref(tE, tE) rslt = ref_dird`prev;
353        return rslt;
354    }
355}
Note: See TracBrowser for help on using the repository browser.