source: libcfa/src/containers/list2.hfa @ a5db488

arm-ehenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since a5db488 was a5db488, checked in by Michael Brooks <mlbrooks@…>, 19 months ago

Fixing two bugs in new linked list, which last night's build failure revealed.

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