source: libcfa/src/containers/list.hfa @ 58fe85a

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since 58fe85a was e857743, checked in by Thierry Delisle <tdelisle@…>, 4 years ago

Forgot to commit the missing 'pragma once' in list.hfa
  • Property mode set to 100644
File size: 10.5 KB
RevLine 
[6091b88a]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
[e857743]16#pragma once
17
[6091b88a]18#include <assert.h>
19
20#define __DLISTED_MGD_COMMON(ELEM, NODE, LINKS_FLD) \
21static inline ELEM& $tempcv_n2e(NODE &node) { \
22        return node; \
23} \
24\
25static inline NODE& $tempcv_e2n(ELEM &node) { \
[b81fd95]26        return ( NODE & ) node; \
[6091b88a]27} \
28\
29static inline ELEM & ?`prev(NODE &node) { \
30    $dlinks(ELEM) & ls = node.LINKS_FLD; \
31        $mgd_link(ELEM) * l = &ls.prev; \
32        ELEM * e = l->elem; \
33        return *e; \
34} \
35\
36static inline ELEM & ?`next(NODE &node) { \
37    $dlinks(ELEM) & ls = node.LINKS_FLD; \
38        $mgd_link(ELEM) * l = &ls.next; \
39        ELEM * e = l->elem; \
40        return *e; \
41} \
42\
43static inline $mgd_link(ELEM) & $prev_link(NODE &node) { \
44    $dlinks(ELEM) & ls = node.LINKS_FLD; \
45        $mgd_link(ELEM) * l = &ls.prev; \
46        return *l; \
47} \
48\
49static inline $mgd_link(ELEM) & $next_link(NODE &node) { \
50    $dlinks(ELEM) & ls = node.LINKS_FLD; \
51        $mgd_link(ELEM) * l = &ls.next; \
52        return *l; \
53}
54
55#define __DLISTED_MGD_JUSTEXPL(STRUCT, IN_THELIST, STRUCT_IN_THELIST) \
56struct STRUCT_IN_THELIST { \
57        inline STRUCT; \
58}; \
59\
60void ?{}(STRUCT_IN_THELIST &) = void; \
61\
62static inline STRUCT_IN_THELIST& ?`IN_THELIST(STRUCT &this) { \
63        return (STRUCT_IN_THELIST&)this; \
64}
65
66#define __DLISTED_MGD_JUSTIMPL(STRUCT)
67
68forall( dtype tE ) {
69        struct $mgd_link {
70                tE *elem;
71                void *terminator;
72                _Bool is_terminator;
73                // will collapse to single pointer with tag bit
74        };
[4d741e9]75        static inline void ?{}( $mgd_link(tE) &this, tE* elem ) {
[6091b88a]76                (this.elem){ elem };
77                (this.terminator){ 0p };
78                (this.is_terminator){ 0 };
79        }
[4d741e9]80        static inline void ?{}( $mgd_link(tE) &this, void * terminator ) {
[6091b88a]81                (this.elem){ 0p };
82                (this.terminator){ terminator };
83                (this.is_terminator){ 1 };
84        }
85        forall ( otype tInit | { void ?{}( $mgd_link(tE) &, tInit); } )
[4d741e9]86        static inline void ?=?( $mgd_link(tE) &this, tInit i ) {
[6091b88a]87                ^?{}( this );
88                ?{}( this, i );
89        }
90        struct $dlinks {
91                // containing item is not listed
92                // iff
93                // links have (elem == 0p && terminator == 0p)
94                $mgd_link(tE) next;
95                $mgd_link(tE) prev;
96        };
[4d741e9]97        static inline void ?{}( $dlinks(tE) &this ) {
[6091b88a]98                (this.next){ (tE *)0p };
99                (this.prev){ (tE *)0p };
100        }
101}
102
103#define DLISTED_MGD_EXPL_IN(STRUCT, LIST_SUF) \
104  $dlinks(STRUCT) $links_ ## LIST_SUF;
105
106#define DLISTED_MGD_EXPL_OUT(STRUCT, LIST_SUF) \
107  __DLISTED_MGD_JUSTEXPL(STRUCT, in_##LIST_SUF, STRUCT ## _in_ ## LIST_SUF) \
108  __DLISTED_MGD_COMMON(STRUCT, STRUCT##_in_##LIST_SUF,  $links_ ## LIST_SUF)
109
110#define DLISTED_MGD_IMPL_IN(STRUCT) \
111  $dlinks(STRUCT) $links;
112
113#define DLISTED_MGD_IMPL_OUT(STRUCT) \
114  __DLISTED_MGD_JUSTIMPL(STRUCT) \
115  __DLISTED_MGD_COMMON(STRUCT, STRUCT, $links)
116
117trait $dlistable(dtype Tnode, dtype Telem) {
118        $mgd_link(Telem) & $prev_link(Tnode &);
119        $mgd_link(Telem) & $next_link(Tnode &);
120        Telem& $tempcv_n2e(Tnode &);
121        Tnode& $tempcv_e2n(Telem &);
[d6d1f80]122
123        Telem& ?`next(Tnode &);
124        Telem& ?`prev(Tnode &);
[6091b88a]125};
126
127forall (dtype Tnode, dtype Telem | $dlistable(Tnode, Telem)) {
128
129        // implemented as a sentinel item in an underlying cicrular list
130        // theList.$links.next is first
131        // theList.$links.prev is last
132        // note this allocation preserves prev-next composition as an identity
133        struct dlist {
134                $dlinks(Telem) $links;
135        };
136
137        // an empty dlist
138        // links refer to self, making a tight circle
[4d741e9]139        static inline void ?{}( dlist(Tnode, Telem) & this ) {
[6091b88a]140                $mgd_link(Telem) selfRef = (void *) &this;
141                ( this.$links ) { selfRef, selfRef };
142        }
143
[4d741e9]144        static inline Telem & ?`first( dlist(Tnode, Telem) &l ) {
[6091b88a]145                return * l.$links.next.elem;
146        }
147
[4d741e9]148        static inline Telem & ?`last( dlist(Tnode, Telem) &l ) {
[6091b88a]149                return * l.$links.prev.elem;
150        }
151
[4d741e9]152        #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
153        static bool $validate_fwd( dlist(Tnode, Telem) & this ) {
154                Tnode * it = & $tempcv_e2n( this`first );
155                if (!it) return (& this`last == 0p);
156
157                while( $next_link(*it).elem ) {
158                        it = & $tempcv_e2n( * $next_link(*it).elem );
159                }
160
161                return ( it == & $tempcv_e2n( this`last ) ) &&
162                           ( $next_link(*it).is_terminator ) &&
163                           ( ((dlist(Tnode, Telem)*)$next_link(*it).terminator) == &this );
164        }
165        static bool $validate_rev( dlist(Tnode, Telem) & this ) {
166                Tnode * it = & $tempcv_e2n( this`last );
167                if (!it) return (& this`first == 0p);
168
169                while( $prev_link(*it).elem ) {
170                        it = & $tempcv_e2n( * $prev_link(*it).elem );
171                }
172
173                return ( it == & $tempcv_e2n( this`first ) ) &&
174                           ( $prev_link(*it).is_terminator ) &&
175                           ( ((dlist(Tnode, Telem)*)$prev_link(*it).terminator) == &this );
176        }
177        static bool validate( dlist(Tnode, Telem) & this ) {
178                return $validate_fwd(this) && $validate_rev(this);
179        }
180        #endif
181
[6091b88a]182        static inline void insert_after(Tnode &list_pos, Telem &to_insert) {
183                assert (&list_pos != 0p);
184                assert (&to_insert != 0p);
185                Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
186                assert($prev_link(singleton_to_insert).elem == 0p);
187                assert($next_link(singleton_to_insert).elem == 0p);
188                $prev_link(singleton_to_insert) = & $tempcv_n2e(list_pos);
[4d741e9]189                $next_link(singleton_to_insert) = $next_link(list_pos);
[6091b88a]190                if ($next_link(list_pos).is_terminator) {
[b81fd95]191                        dlist(Tnode, Telem) *list = ( dlist(Tnode, Telem) * ) $next_link(list_pos).terminator;
[6091b88a]192                        $dlinks(Telem) *list_links = & list->$links;
193                        $mgd_link(Telem) *list_last = & list_links->prev;
194                        *list_last = &to_insert;
195                } else {
196                        Telem *list_pos_next = $next_link(list_pos).elem;
197                        if (list_pos_next) {
198                                Tnode & lpn_inlist = $tempcv_e2n(*list_pos_next);
199                                $prev_link(lpn_inlist) = &to_insert;
200                        }
201                }
202                $next_link(list_pos) = &to_insert;
203        }
204
205        static inline void insert_before(Tnode &list_pos, Telem &to_insert) {
206                assert (&list_pos != 0p);
207                assert (&to_insert != 0p);
208                Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
209                assert($prev_link(singleton_to_insert).elem == 0p);
210                assert($next_link(singleton_to_insert).elem == 0p);
211                $next_link(singleton_to_insert) = & $tempcv_n2e(list_pos);
[4d741e9]212                $prev_link(singleton_to_insert) = $prev_link(list_pos);
[6091b88a]213                if ($prev_link(list_pos).is_terminator) {
[b81fd95]214                        dlist(Tnode, Telem) *list = ( dlist(Tnode, Telem) * ) $prev_link(list_pos).terminator;
[6091b88a]215                        $dlinks(Telem) *list_links = & list->$links;
216                        $mgd_link(Telem) *list_first = & list_links->next;
217                        *list_first = &to_insert;
218                } else {
219                        Telem *list_pos_prev = $prev_link(list_pos).elem;
220                        if (list_pos_prev) {
221                                Tnode & lpp_inlist = $tempcv_e2n(*list_pos_prev);
222                                $next_link(lpp_inlist) = &to_insert;
223                        }
224                }
225                $prev_link(list_pos) = &to_insert;
226        }
227
228    static inline void insert_first(dlist(Tnode, Telem) &list, Telem &to_insert) {
229                assert (&list != 0p);
230                assert (&to_insert != 0p);
231                Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
232                assert($prev_link(singleton_to_insert).elem == 0p);
233                assert($next_link(singleton_to_insert).elem == 0p);
234
235                $prev_link(singleton_to_insert) = (void*) &list;
236                $next_link(singleton_to_insert) = list.$links.next;
237
238                $dlinks(Telem) *listLinks = & list.$links;
239                if (listLinks->next.is_terminator) {
240                        $mgd_link(Telem) * listPrevReference = & listLinks->prev;
241                        *listPrevReference = &to_insert;
242                } else {
243                        Tnode & next_inlist = $tempcv_e2n(*list.$links.next.elem);
244                        $prev_link(next_inlist) = &to_insert;
245                }
246                $mgd_link(Telem) * listNextReference = & listLinks->next;
247                *listNextReference = &to_insert;
248        }
249
250    static inline void insert_last(dlist(Tnode, Telem) &list, Telem &to_insert) {
251                assert (&list != 0p);
252                assert (&to_insert != 0p);
253                Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
254                assert($next_link(singleton_to_insert).elem == 0p);
255                assert($prev_link(singleton_to_insert).elem == 0p);
256
257                $next_link(singleton_to_insert) = (void*) &list;
258                $prev_link(singleton_to_insert) = list.$links.prev;
259
260                $dlinks(Telem) *listLinks = & list.$links;
261                if (listLinks->prev.is_terminator) {
262                        $mgd_link(Telem) * listNextReference = & listLinks->next;
263                        *listNextReference = &to_insert;
264                } else {
265                        Tnode & prev_inlist = $tempcv_e2n(*list.$links.prev.elem);
266                        $next_link(prev_inlist) = &to_insert;
267                }
268                $mgd_link(Telem) * listPrevReference = & listLinks->prev;
269                *listPrevReference = &to_insert;
270        }
271
272    static inline void remove(Tnode &list_pos) {
273                assert( &list_pos != 0p );
274
275                $mgd_link(Telem) &incoming_from_prev = *0p;
276                $mgd_link(Telem) &incoming_from_next = *0p;
277
278                if ( $prev_link(list_pos).is_terminator ) {
[b81fd95]279                        dlist(Tnode, Telem) * tgt_before = ( dlist(Tnode, Telem) * ) $prev_link(list_pos).terminator;
[6091b88a]280                        $dlinks(Telem) * links_before = & tgt_before->$links;
281                        &incoming_from_prev = & links_before->next;
282                } else if ($prev_link(list_pos).elem) {
283                        Telem * tgt_before = $prev_link(list_pos).elem;
284                        Tnode & list_pos_before = $tempcv_e2n(*tgt_before);
285                        &incoming_from_prev = & $next_link(list_pos_before);
286                }
287
288                if ( $next_link(list_pos).is_terminator ) {
[b81fd95]289                        dlist(Tnode, Telem) * tgt_after = ( dlist(Tnode, Telem) * ) $next_link(list_pos).terminator;
[6091b88a]290                        $dlinks(Telem) * links_after = & tgt_after->$links;
291                        &incoming_from_next = & links_after->prev;
292                } else if ($next_link(list_pos).elem) {
293                        Telem * tgt_after  = $next_link(list_pos).elem;
294                        Tnode & list_pos_after  = $tempcv_e2n(*tgt_after );
295                        &incoming_from_next = & $prev_link(list_pos_after );
296                }
297
298                if (& incoming_from_prev) {
299                        incoming_from_prev = $next_link(list_pos);
300                }
301                if (& incoming_from_next) {
302                        incoming_from_next = $prev_link(list_pos);
303                }
304
305                $next_link(list_pos) = (Telem*) 0p;
306                $prev_link(list_pos) = (Telem*) 0p;
307        }
[f2d05e9]308
309        static inline bool ?`is_empty(dlist(Tnode, Telem) &list) {
310                assert( &list != 0p );
311                $dlinks(Telem) *listLinks = & list.$links;
312                if (listLinks->next.is_terminator) {
313                        assert(listLinks->prev.is_terminator);
314                        assert(listLinks->next.terminator);
315                        assert(listLinks->prev.terminator);
316                        return true;
317                } else {
318                        assert(!listLinks->prev.is_terminator);
319                        assert(listLinks->next.elem);
320                        assert(listLinks->prev.elem);
321                        return false;
322                }
323        }
324
325        static inline Telem & pop_first(dlist(Tnode, Telem) &list) {
326                assert( &list != 0p );
327                assert( !list`is_empty );
328                $dlinks(Telem) *listLinks = & list.$links;
329                Telem & first = *listLinks->next.elem;
330                Tnode & list_pos_first  = $tempcv_e2n( first );
331                remove(list_pos_first);
332                return first;
333        }
334
335        static inline Telem & pop_last(dlist(Tnode, Telem) &list) {
336                assert( &list != 0p );
337                assert( !list`is_empty );
338                $dlinks(Telem) *listLinks = & list.$links;
339                Telem & last = *listLinks->prev.elem;
340                Tnode & list_pos_last  = $tempcv_e2n( last );
341                remove(list_pos_last);
342                return last;
343        }
344
[6091b88a]345}
346
Note: See TracBrowser for help on using the repository browser.