source: libcfa/src/containers/list2.hfa @ 9e2341b4

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

Baseline commit of new linked-list implementation and test.

Using a separate header with intention to port old uses first, then rename.
  • Property mode set to 100644
File size: 9.8 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
42
43#define ORIGIN_TAG_BITNO 63
44#define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO)
45
46#define ORIGIN_TAG_SET(p)   ((p) |  ORIGIN_TAG_MASK)
47#define ORIGIN_TAG_CLEAR(p) ((p) & ~ORIGIN_TAG_MASK)
48#define ORIGIN_TAG_QUERY(p) ((p) &  ORIGIN_TAG_MASK)
49
50// #define ORIGIN_TAG_SET(p)   (p)
51// #define ORIGIN_TAG_CLEAR(p) (p)
52// #define ORIGIN_TAG_QUERY(p) (0)
53
54
55forall( tE & ) {
56
57    struct dlink{
58        tE *next;
59        tE *prev;
60    };
61
62    static inline void ?{}( dlink(tE) & this ) {
63        this.next = 0p;
64        this.prev = 0p;
65    }
66
67    forall( tLinks & = tE ) {
68
69        struct dlist {
70            inline dlink(tE);
71        };
72
73        struct diref {
74            inline tE &;
75        };
76    }
77
78    forall( tLinks & = tE | embedded( tE, tLinks ) | embedded( tLinks, dlink(tE) ) ) {
79        static inline tE * $get_list_origin_addr( dlist(tE, tLinks) & lst ) {
80            dlink(tE) & link_from_null = ( * (tE *) 0p )`inner`inner;
81            ptrdiff_t link_offset = (ptrdiff_t) & link_from_null;
82            size_t origin_addr = ((size_t) & lst) - link_offset;
83            size_t preResult = ORIGIN_TAG_SET( origin_addr );
84            return (tE *)preResult;
85        }
86
87        static inline void ?{}( dlist(tE, tLinks) & this ) {
88            tE * listOrigin = $get_list_origin_addr( this );
89            ( ( dlink(tE) & ) this ){ listOrigin, listOrigin } ;
90        }
91
92        // redundant
93        // void ?{}( diref(tE, tLinks) & this, tE & target ) {
94        //     tE && ref = this;
95        //     &ref = &target;
96        // }
97    }
98
99}
100
101
102forall( tE &, tLinks & | embedded( tE, tLinks ) | embedded( tLinks, dlink(tE) ) ) {
103
104        static inline void insert_after(diref(tE, tLinks) list_pos, tE &to_insert) {
105                verify (&list_pos != 0p);
106                verify (&to_insert != 0p);
107        dlink(tE) & linkToInsert = to_insert`inner`inner;
108                verify(linkToInsert.prev == 0p);
109                verify(linkToInsert.next == 0p);
110        tE & list_pos_raw = list_pos;
111        tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos_raw );
112        tE & after_raw = * (list_pos_elem`inner`inner).next;
113        tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
114                linkToInsert.prev = & list_pos_raw;
115                linkToInsert.next = & after_raw;
116        (after_elem`inner`inner).prev = &to_insert;
117                (list_pos_elem`inner`inner).next = &to_insert;
118        }
119
120        static inline void insert_before(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.next == 0p);
125                verify(linkToInsert.prev == 0p);
126        tE & list_pos_raw = list_pos;
127        tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos_raw );
128        tE & before_raw = * (list_pos_elem`inner`inner).prev;
129        tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
130                linkToInsert.next = & list_pos_raw;
131                linkToInsert.prev = & before_raw;
132        (before_elem`inner`inner).next = &to_insert;
133                (list_pos_elem`inner`inner).prev = &to_insert;
134        }
135
136    static inline void doRemove(
137        dlink(tE) & this_links, dlink(tE) & before_links, dlink(tE) & after_links,
138        tE & before_target, tE & after_target ) {
139
140        before_links.next = &after_target;
141        after_links.prev = &before_target;
142
143        asm( "" : : : "memory" );
144
145                this_links.prev = 0p;
146                this_links.next = 0p;
147    }
148
149        static inline tE & remove(diref(tE, tLinks) list_pos) {
150                verify (&list_pos != 0p);
151        tE & list_pos_elem = list_pos;
152        verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos_elem) );
153        dlink(tE) & list_pos_links = list_pos_elem`inner`inner;
154        tE & before_raw = * list_pos_links.prev;
155        tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
156        dlink(tE) & before_links = before_elem`inner`inner;
157        tE & after_raw = * list_pos_links.next;
158        tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
159        dlink(tE) & after_links = after_elem`inner`inner;
160
161        doRemove(list_pos_links, before_links, after_links, before_raw, after_raw);
162
163        return list_pos_elem;
164        }
165/*   
166        static inline tE & remove(diref(tE, tLinks) list_pos) {
167                verify (&list_pos != 0p);
168        tE & list_pos_elem = list_pos;
169        verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos_elem) );
170        dlink(tE) & list_pos_links = list_pos_elem`inner`inner;
171        tE & before_raw = * list_pos_links.prev;
172        tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
173        dlink(tE) & before_links = before_elem`inner`inner;
174        tE & after_raw = * list_pos_links.next;
175        tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
176        dlink(tE) & after_links = after_elem`inner`inner;
177        before_links.next = &after_raw;
178        after_links.prev = &before_raw;
179asm( "" : : : "memory" );
180                list_pos_links.prev = 0p;
181                list_pos_links.next = 0p;
182        return list_pos_elem;
183        }
184*/
185    static inline diref(tE, tLinks) ?`first( dlist(tE, tLinks) &lst ) {
186        tE * firstPtr = lst.next;
187        if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
188        diref(tE, tLinks) ret = { *firstPtr };
189        return ret;
190    }
191    static inline diref(tE, tLinks) ?`last ( dlist(tE, tLinks) &lst ) {
192        tE * lastPtr = lst.prev;
193        if (ORIGIN_TAG_QUERY((size_t)lastPtr)) lastPtr = 0p;
194        diref(tE, tLinks) ret = { *lastPtr };
195        return ret;
196    }
197
198    static inline int ?!=?( const diref(tE, tLinks) & list_pos, zero_t ) {
199        tE & list_pos_elem = list_pos;
200        if (ORIGIN_TAG_QUERY((size_t) & list_pos_elem)) return 0;
201        return & list_pos_elem != 0p;
202    }
203
204    static inline int DUMB_COMPARE( diref(tE, tLinks) list_pos, tE * elem ) {
205        tE & signifiedLhs = list_pos;
206        return &signifiedLhs == elem;
207    }
208
209    static inline diref(tE, tLinks) ?`from( tE & elem ) {
210        diref(tE, tLinks) ret = { elem };
211        return ret;
212    }
213
214    static inline diref(tE, tLinks) ?`elems( dlist(tE, tLinks) & lst ) {
215        tE * origin = $get_list_origin_addr( lst );
216        diref(tE, tLinks) ret = { *origin };
217        return ret;
218    }
219
220    static inline bool ?`moveNext( diref(tE, tLinks) & refx ) {
221        tE && ref_inner = refx;
222        tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
223        &ref_inner = oldReferent`inner`inner.next;
224        return &ref_inner != 0p  &&
225            ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
226    }
227
228    static inline bool ?`movePrev( diref(tE, tLinks) & refx ) {
229        tE && ref_inner = refx;
230        tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
231        &ref_inner = oldReferent`inner`inner.prev;
232        return &ref_inner != 0p  &&
233            ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
234    }
235
236    static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) {
237        insert_after(lst`elems, e);
238    }
239
240    static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) {
241        insert_before(lst`elems, e);
242    }
243
244
245  #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
246        static bool $validate_fwd( dlist(tE, tLinks) & this ) {
247        if ( ! & this`first ) return ( (& this`last) == 0p);
248
249        tE & lagElem = *0p;
250
251        while ( diref(tE, tLinks) it = this`elems; it`moveNext ) {
252            if (& lagElem == 0p &&  &it != & this`first ) return false;
253            & lagElem = & it;
254        }
255
256        if (& lagElem != & this`last) return false;
257
258        // TODO: verify that it is back at this`elems;
259        return true;
260        }
261        static bool $validate_rev( dlist(tE, tLinks) & this ) {
262        if ( ! & this`last ) return ( (& this`first) == 0p);
263
264        tE & lagElem = *0p;
265
266        while ( diref(tE, tLinks) it = this`elems; it`movePrev ) {
267            if (& lagElem == 0p &&  &it != & this`last ) return false;
268            & lagElem = & it;
269        }
270
271        if (& lagElem != & this`first) return false;
272
273        // TODO: verify that it is back at this`elems;
274        return true;
275        }
276        static bool validate( dlist(tE, tLinks) & this ) {
277                return $validate_fwd(this) && $validate_rev(this);
278        }
279  #endif
280
281}
282
283forall( tE & | embedded( tE, dlink(tE) ) ) {
284        static inline void insert_after(tE & list_pos, tE &to_insert ) {
285        diref(tE, tE) list_pos_ref = list_pos`from;
286        insert_after( list_pos_ref, to_insert );
287    }
288        static inline void insert_before(tE & list_pos, tE &to_insert ) {
289        diref(tE, tE) list_pos_ref = list_pos`from;
290        insert_before( list_pos_ref, to_insert );
291    }
292        static inline tE & remove(tE & list_pos ) {
293        diref(tE, tE) list_pos_ref = list_pos`from;
294        return remove( list_pos_ref );
295    }
296    static inline bool ?`moveNext( tE && ref ) {
297        diref(tE, tE) & ref_dird = (diref(tE, tE) &) & ref;
298        return ref_dird`moveNext;
299    }
300    static inline bool ?`movePrev( tE && ref ) {
301        diref(tE, tE) & ref_dird = (diref(tE, tE) &) & ref;
302        return ref_dird`movePrev;
303    }
304
305}
Note: See TracBrowser for help on using the repository browser.