source: libcfa/src/containers/list.hfa @ 6091b88a

arm-ehjacob/cs343-translationnew-astnew-ast-unique-expr
Last change on this file since 6091b88a was 6091b88a, checked in by Michael Brooks <mlbrooks@…>, 18 months ago

intrusive doubly linked list initial

  • Property mode set to 100644
File size: 8.3 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#include <assert.h>
17
18#define __DLISTED_MGD_COMMON(ELEM, NODE, LINKS_FLD) \
19static inline ELEM& $tempcv_n2e(NODE &node) { \
20        return node; \
21} \
22\
23static inline NODE& $tempcv_e2n(ELEM &node) { \
24        return node; \
25} \
26\
27static inline ELEM & ?`prev(NODE &node) { \
28    $dlinks(ELEM) & ls = node.LINKS_FLD; \
29        $mgd_link(ELEM) * l = &ls.prev; \
30        ELEM * e = l->elem; \
31        return *e; \
32} \
33\
34static inline ELEM & ?`next(NODE &node) { \
35    $dlinks(ELEM) & ls = node.LINKS_FLD; \
36        $mgd_link(ELEM) * l = &ls.next; \
37        ELEM * e = l->elem; \
38        return *e; \
39} \
40\
41static inline $mgd_link(ELEM) & $prev_link(NODE &node) { \
42    $dlinks(ELEM) & ls = node.LINKS_FLD; \
43        $mgd_link(ELEM) * l = &ls.prev; \
44        return *l; \
45} \
46\
47static inline $mgd_link(ELEM) & $next_link(NODE &node) { \
48    $dlinks(ELEM) & ls = node.LINKS_FLD; \
49        $mgd_link(ELEM) * l = &ls.next; \
50        return *l; \
51}
52
53#define __DLISTED_MGD_JUSTEXPL(STRUCT, IN_THELIST, STRUCT_IN_THELIST) \
54struct STRUCT_IN_THELIST { \
55        inline STRUCT; \
56}; \
57\
58void ?{}(STRUCT_IN_THELIST &) = void; \
59\
60static inline STRUCT_IN_THELIST& ?`IN_THELIST(STRUCT &this) { \
61        return (STRUCT_IN_THELIST&)this; \
62}
63
64#define __DLISTED_MGD_JUSTIMPL(STRUCT)
65
66forall( dtype tE ) {
67        struct $mgd_link {
68                tE *elem;
69                void *terminator;
70                _Bool is_terminator;
71                // will collapse to single pointer with tag bit
72        };
73        inline void ?{}( $mgd_link(tE) &this, tE* elem ) {
74                (this.elem){ elem };
75                (this.terminator){ 0p };
76                (this.is_terminator){ 0 };
77        }
78        inline void ?{}( $mgd_link(tE) &this, void * terminator ) {
79                (this.elem){ 0p };
80                (this.terminator){ terminator };
81                (this.is_terminator){ 1 };
82        }
83        forall ( otype tInit | { void ?{}( $mgd_link(tE) &, tInit); } )
84        void ?=?( $mgd_link(tE) &this, tInit i ) {
85                ^?{}( this );
86                ?{}( this, i );
87        }
88        struct $dlinks {
89                // containing item is not listed
90                // iff
91                // links have (elem == 0p && terminator == 0p)
92                $mgd_link(tE) next;
93                $mgd_link(tE) prev;
94        };
95        inline void ?{}( $dlinks(tE) &this ) {
96                (this.next){ (tE *)0p };
97                (this.prev){ (tE *)0p };
98        }
99}
100
101#define DLISTED_MGD_EXPL_IN(STRUCT, LIST_SUF) \
102  $dlinks(STRUCT) $links_ ## LIST_SUF;
103
104#define DLISTED_MGD_EXPL_OUT(STRUCT, LIST_SUF) \
105  __DLISTED_MGD_JUSTEXPL(STRUCT, in_##LIST_SUF, STRUCT ## _in_ ## LIST_SUF) \
106  __DLISTED_MGD_COMMON(STRUCT, STRUCT##_in_##LIST_SUF,  $links_ ## LIST_SUF)
107
108#define DLISTED_MGD_IMPL_IN(STRUCT) \
109  $dlinks(STRUCT) $links;
110
111#define DLISTED_MGD_IMPL_OUT(STRUCT) \
112  __DLISTED_MGD_JUSTIMPL(STRUCT) \
113  __DLISTED_MGD_COMMON(STRUCT, STRUCT, $links)
114
115trait $dlistable(dtype Tnode, dtype Telem) {
116        $mgd_link(Telem) & $prev_link(Tnode &);
117        $mgd_link(Telem) & $next_link(Tnode &);
118        Telem& $tempcv_n2e(Tnode &);
119        Tnode& $tempcv_e2n(Telem &);
120};
121
122forall (dtype Tnode, dtype Telem | $dlistable(Tnode, Telem)) {
123
124        // implemented as a sentinel item in an underlying cicrular list
125        // theList.$links.next is first
126        // theList.$links.prev is last
127        // note this allocation preserves prev-next composition as an identity
128        struct dlist {
129                $dlinks(Telem) $links;
130        };
131
132        // an empty dlist
133        // links refer to self, making a tight circle
134        void ?{}( dlist(Tnode, Telem) & this ) {
135                $mgd_link(Telem) selfRef = (void *) &this;
136                ( this.$links ) { selfRef, selfRef };
137        }
138
139        Telem & ?`first( dlist(Tnode, Telem) &l ) {
140                return * l.$links.next.elem;
141        }
142
143        Telem & ?`last( dlist(Tnode, Telem) &l ) {
144                return * l.$links.prev.elem;
145        }
146
147        static inline void insert_after(Tnode &list_pos, Telem &to_insert) {
148                assert (&list_pos != 0p);
149                assert (&to_insert != 0p);
150                Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
151                assert($prev_link(singleton_to_insert).elem == 0p);
152                assert($next_link(singleton_to_insert).elem == 0p);
153                $prev_link(singleton_to_insert) = & $tempcv_n2e(list_pos);
154                $next_link(singleton_to_insert) = $next_link(list_pos).elem;
155                if ($next_link(list_pos).is_terminator) {
156                        dlist(Tnode, Telem) *list = $next_link(list_pos).terminator;
157                        $dlinks(Telem) *list_links = & list->$links;
158                        $mgd_link(Telem) *list_last = & list_links->prev;
159                        *list_last = &to_insert;
160                } else {
161                        Telem *list_pos_next = $next_link(list_pos).elem;
162                        if (list_pos_next) {
163                                Tnode & lpn_inlist = $tempcv_e2n(*list_pos_next);
164                                $prev_link(lpn_inlist) = &to_insert;
165                        }
166                }
167                $next_link(list_pos) = &to_insert;
168        }
169
170        static inline void insert_before(Tnode &list_pos, Telem &to_insert) {
171                assert (&list_pos != 0p);
172                assert (&to_insert != 0p);
173                Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
174                assert($prev_link(singleton_to_insert).elem == 0p);
175                assert($next_link(singleton_to_insert).elem == 0p);
176                $next_link(singleton_to_insert) = & $tempcv_n2e(list_pos);
177                $prev_link(singleton_to_insert) = $prev_link(list_pos).elem;
178                if ($prev_link(list_pos).is_terminator) {
179                        dlist(Tnode, Telem) *list = $prev_link(list_pos).terminator;
180                        $dlinks(Telem) *list_links = & list->$links;
181                        $mgd_link(Telem) *list_first = & list_links->next;
182                        *list_first = &to_insert;
183                } else {
184                        Telem *list_pos_prev = $prev_link(list_pos).elem;
185                        if (list_pos_prev) {
186                                Tnode & lpp_inlist = $tempcv_e2n(*list_pos_prev);
187                                $next_link(lpp_inlist) = &to_insert;
188                        }
189                }
190                $prev_link(list_pos) = &to_insert;
191        }
192
193    static inline void insert_first(dlist(Tnode, Telem) &list, Telem &to_insert) {
194                assert (&list != 0p);
195                assert (&to_insert != 0p);
196                Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
197                assert($prev_link(singleton_to_insert).elem == 0p);
198                assert($next_link(singleton_to_insert).elem == 0p);
199
200                $prev_link(singleton_to_insert) = (void*) &list;
201                $next_link(singleton_to_insert) = list.$links.next;
202
203                $dlinks(Telem) *listLinks = & list.$links;
204                if (listLinks->next.is_terminator) {
205                        $mgd_link(Telem) * listPrevReference = & listLinks->prev;
206                        *listPrevReference = &to_insert;
207                } else {
208                        Tnode & next_inlist = $tempcv_e2n(*list.$links.next.elem);
209                        $prev_link(next_inlist) = &to_insert;
210                }
211                $mgd_link(Telem) * listNextReference = & listLinks->next;
212                *listNextReference = &to_insert;
213        }
214
215    static inline void insert_last(dlist(Tnode, Telem) &list, Telem &to_insert) {
216                assert (&list != 0p);
217                assert (&to_insert != 0p);
218                Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
219                assert($next_link(singleton_to_insert).elem == 0p);
220                assert($prev_link(singleton_to_insert).elem == 0p);
221
222                $next_link(singleton_to_insert) = (void*) &list;
223                $prev_link(singleton_to_insert) = list.$links.prev;
224
225                $dlinks(Telem) *listLinks = & list.$links;
226                if (listLinks->prev.is_terminator) {
227                        $mgd_link(Telem) * listNextReference = & listLinks->next;
228                        *listNextReference = &to_insert;
229                } else {
230                        Tnode & prev_inlist = $tempcv_e2n(*list.$links.prev.elem);
231                        $next_link(prev_inlist) = &to_insert;
232                }
233                $mgd_link(Telem) * listPrevReference = & listLinks->prev;
234                *listPrevReference = &to_insert;
235        }
236
237    static inline void remove(Tnode &list_pos) {
238                assert( &list_pos != 0p );
239
240                $mgd_link(Telem) &incoming_from_prev = *0p;
241                $mgd_link(Telem) &incoming_from_next = *0p;
242
243                if ( $prev_link(list_pos).is_terminator ) {
244                        dlist(Tnode, Telem) * tgt_before = $prev_link(list_pos).terminator;
245                        $dlinks(Telem) * links_before = & tgt_before->$links;
246                        &incoming_from_prev = & links_before->next;
247                } else if ($prev_link(list_pos).elem) {
248                        Telem * tgt_before = $prev_link(list_pos).elem;
249                        Tnode & list_pos_before = $tempcv_e2n(*tgt_before);
250                        &incoming_from_prev = & $next_link(list_pos_before);
251                }
252
253                if ( $next_link(list_pos).is_terminator ) {
254                        dlist(Tnode, Telem) * tgt_after = $next_link(list_pos).terminator;
255                        $dlinks(Telem) * links_after = & tgt_after->$links;
256                        &incoming_from_next = & links_after->prev;
257                } else if ($next_link(list_pos).elem) {
258                        Telem * tgt_after  = $next_link(list_pos).elem;
259                        Tnode & list_pos_after  = $tempcv_e2n(*tgt_after );
260                        &incoming_from_next = & $prev_link(list_pos_after );
261                }
262
263                if (& incoming_from_prev) {
264                        incoming_from_prev = $next_link(list_pos);
265                }
266                if (& incoming_from_next) {
267                        incoming_from_next = $prev_link(list_pos);
268                }
269
270                $next_link(list_pos) = (Telem*) 0p;
271                $prev_link(list_pos) = (Telem*) 0p;
272        }
273}
274
Note: See TracBrowser for help on using the repository browser.