source: libcfa/src/containers/list.hfa @ 04b4a71

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

Adding an example of lists and exceptions collaborating on a hashtable. On dlist, added existing routines to the dlist trait (public interface).
  • Property mode set to 100644
File size: 10.4 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
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        };
[4d741e9]73        static inline void ?{}( $mgd_link(tE) &this, tE* elem ) {
[6091b88a]74                (this.elem){ elem };
75                (this.terminator){ 0p };
76                (this.is_terminator){ 0 };
77        }
[4d741e9]78        static inline void ?{}( $mgd_link(tE) &this, void * terminator ) {
[6091b88a]79                (this.elem){ 0p };
80                (this.terminator){ terminator };
81                (this.is_terminator){ 1 };
82        }
83        forall ( otype tInit | { void ?{}( $mgd_link(tE) &, tInit); } )
[4d741e9]84        static inline void ?=?( $mgd_link(tE) &this, tInit i ) {
[6091b88a]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        };
[4d741e9]95        static inline void ?{}( $dlinks(tE) &this ) {
[6091b88a]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 &);
[d6d1f80]120
121        Telem& ?`next(Tnode &);
122        Telem& ?`prev(Tnode &);
[6091b88a]123};
124
125forall (dtype Tnode, dtype Telem | $dlistable(Tnode, Telem)) {
126
127        // implemented as a sentinel item in an underlying cicrular list
128        // theList.$links.next is first
129        // theList.$links.prev is last
130        // note this allocation preserves prev-next composition as an identity
131        struct dlist {
132                $dlinks(Telem) $links;
133        };
134
135        // an empty dlist
136        // links refer to self, making a tight circle
[4d741e9]137        static inline void ?{}( dlist(Tnode, Telem) & this ) {
[6091b88a]138                $mgd_link(Telem) selfRef = (void *) &this;
139                ( this.$links ) { selfRef, selfRef };
140        }
141
[4d741e9]142        static inline Telem & ?`first( dlist(Tnode, Telem) &l ) {
[6091b88a]143                return * l.$links.next.elem;
144        }
145
[4d741e9]146        static inline Telem & ?`last( dlist(Tnode, Telem) &l ) {
[6091b88a]147                return * l.$links.prev.elem;
148        }
149
[4d741e9]150        #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
151        static bool $validate_fwd( dlist(Tnode, Telem) & this ) {
152                Tnode * it = & $tempcv_e2n( this`first );
153                if (!it) return (& this`last == 0p);
154
155                while( $next_link(*it).elem ) {
156                        it = & $tempcv_e2n( * $next_link(*it).elem );
157                }
158
159                return ( it == & $tempcv_e2n( this`last ) ) &&
160                           ( $next_link(*it).is_terminator ) &&
161                           ( ((dlist(Tnode, Telem)*)$next_link(*it).terminator) == &this );
162        }
163        static bool $validate_rev( dlist(Tnode, Telem) & this ) {
164                Tnode * it = & $tempcv_e2n( this`last );
165                if (!it) return (& this`first == 0p);
166
167                while( $prev_link(*it).elem ) {
168                        it = & $tempcv_e2n( * $prev_link(*it).elem );
169                }
170
171                return ( it == & $tempcv_e2n( this`first ) ) &&
172                           ( $prev_link(*it).is_terminator ) &&
173                           ( ((dlist(Tnode, Telem)*)$prev_link(*it).terminator) == &this );
174        }
175        static bool validate( dlist(Tnode, Telem) & this ) {
176                return $validate_fwd(this) && $validate_rev(this);
177        }
178        #endif
179
[6091b88a]180        static inline void insert_after(Tnode &list_pos, Telem &to_insert) {
181                assert (&list_pos != 0p);
182                assert (&to_insert != 0p);
183                Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
184                assert($prev_link(singleton_to_insert).elem == 0p);
185                assert($next_link(singleton_to_insert).elem == 0p);
186                $prev_link(singleton_to_insert) = & $tempcv_n2e(list_pos);
[4d741e9]187                $next_link(singleton_to_insert) = $next_link(list_pos);
[6091b88a]188                if ($next_link(list_pos).is_terminator) {
189                        dlist(Tnode, Telem) *list = $next_link(list_pos).terminator;
190                        $dlinks(Telem) *list_links = & list->$links;
191                        $mgd_link(Telem) *list_last = & list_links->prev;
192                        *list_last = &to_insert;
193                } else {
194                        Telem *list_pos_next = $next_link(list_pos).elem;
195                        if (list_pos_next) {
196                                Tnode & lpn_inlist = $tempcv_e2n(*list_pos_next);
197                                $prev_link(lpn_inlist) = &to_insert;
198                        }
199                }
200                $next_link(list_pos) = &to_insert;
201        }
202
203        static inline void insert_before(Tnode &list_pos, Telem &to_insert) {
204                assert (&list_pos != 0p);
205                assert (&to_insert != 0p);
206                Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
207                assert($prev_link(singleton_to_insert).elem == 0p);
208                assert($next_link(singleton_to_insert).elem == 0p);
209                $next_link(singleton_to_insert) = & $tempcv_n2e(list_pos);
[4d741e9]210                $prev_link(singleton_to_insert) = $prev_link(list_pos);
[6091b88a]211                if ($prev_link(list_pos).is_terminator) {
212                        dlist(Tnode, Telem) *list = $prev_link(list_pos).terminator;
213                        $dlinks(Telem) *list_links = & list->$links;
214                        $mgd_link(Telem) *list_first = & list_links->next;
215                        *list_first = &to_insert;
216                } else {
217                        Telem *list_pos_prev = $prev_link(list_pos).elem;
218                        if (list_pos_prev) {
219                                Tnode & lpp_inlist = $tempcv_e2n(*list_pos_prev);
220                                $next_link(lpp_inlist) = &to_insert;
221                        }
222                }
223                $prev_link(list_pos) = &to_insert;
224        }
225
226    static inline void insert_first(dlist(Tnode, Telem) &list, Telem &to_insert) {
227                assert (&list != 0p);
228                assert (&to_insert != 0p);
229                Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
230                assert($prev_link(singleton_to_insert).elem == 0p);
231                assert($next_link(singleton_to_insert).elem == 0p);
232
233                $prev_link(singleton_to_insert) = (void*) &list;
234                $next_link(singleton_to_insert) = list.$links.next;
235
236                $dlinks(Telem) *listLinks = & list.$links;
237                if (listLinks->next.is_terminator) {
238                        $mgd_link(Telem) * listPrevReference = & listLinks->prev;
239                        *listPrevReference = &to_insert;
240                } else {
241                        Tnode & next_inlist = $tempcv_e2n(*list.$links.next.elem);
242                        $prev_link(next_inlist) = &to_insert;
243                }
244                $mgd_link(Telem) * listNextReference = & listLinks->next;
245                *listNextReference = &to_insert;
246        }
247
248    static inline void insert_last(dlist(Tnode, Telem) &list, Telem &to_insert) {
249                assert (&list != 0p);
250                assert (&to_insert != 0p);
251                Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
252                assert($next_link(singleton_to_insert).elem == 0p);
253                assert($prev_link(singleton_to_insert).elem == 0p);
254
255                $next_link(singleton_to_insert) = (void*) &list;
256                $prev_link(singleton_to_insert) = list.$links.prev;
257
258                $dlinks(Telem) *listLinks = & list.$links;
259                if (listLinks->prev.is_terminator) {
260                        $mgd_link(Telem) * listNextReference = & listLinks->next;
261                        *listNextReference = &to_insert;
262                } else {
263                        Tnode & prev_inlist = $tempcv_e2n(*list.$links.prev.elem);
264                        $next_link(prev_inlist) = &to_insert;
265                }
266                $mgd_link(Telem) * listPrevReference = & listLinks->prev;
267                *listPrevReference = &to_insert;
268        }
269
270    static inline void remove(Tnode &list_pos) {
271                assert( &list_pos != 0p );
272
273                $mgd_link(Telem) &incoming_from_prev = *0p;
274                $mgd_link(Telem) &incoming_from_next = *0p;
275
276                if ( $prev_link(list_pos).is_terminator ) {
277                        dlist(Tnode, Telem) * tgt_before = $prev_link(list_pos).terminator;
278                        $dlinks(Telem) * links_before = & tgt_before->$links;
279                        &incoming_from_prev = & links_before->next;
280                } else if ($prev_link(list_pos).elem) {
281                        Telem * tgt_before = $prev_link(list_pos).elem;
282                        Tnode & list_pos_before = $tempcv_e2n(*tgt_before);
283                        &incoming_from_prev = & $next_link(list_pos_before);
284                }
285
286                if ( $next_link(list_pos).is_terminator ) {
287                        dlist(Tnode, Telem) * tgt_after = $next_link(list_pos).terminator;
288                        $dlinks(Telem) * links_after = & tgt_after->$links;
289                        &incoming_from_next = & links_after->prev;
290                } else if ($next_link(list_pos).elem) {
291                        Telem * tgt_after  = $next_link(list_pos).elem;
292                        Tnode & list_pos_after  = $tempcv_e2n(*tgt_after );
293                        &incoming_from_next = & $prev_link(list_pos_after );
294                }
295
296                if (& incoming_from_prev) {
297                        incoming_from_prev = $next_link(list_pos);
298                }
299                if (& incoming_from_next) {
300                        incoming_from_next = $prev_link(list_pos);
301                }
302
303                $next_link(list_pos) = (Telem*) 0p;
304                $prev_link(list_pos) = (Telem*) 0p;
305        }
[f2d05e9]306
307        static inline bool ?`is_empty(dlist(Tnode, Telem) &list) {
308                assert( &list != 0p );
309                $dlinks(Telem) *listLinks = & list.$links;
310                if (listLinks->next.is_terminator) {
311                        assert(listLinks->prev.is_terminator);
312                        assert(listLinks->next.terminator);
313                        assert(listLinks->prev.terminator);
314                        return true;
315                } else {
316                        assert(!listLinks->prev.is_terminator);
317                        assert(listLinks->next.elem);
318                        assert(listLinks->prev.elem);
319                        return false;
320                }
321        }
322
323        static inline Telem & pop_first(dlist(Tnode, Telem) &list) {
324                assert( &list != 0p );
325                assert( !list`is_empty );
326                $dlinks(Telem) *listLinks = & list.$links;
327                Telem & first = *listLinks->next.elem;
328                Tnode & list_pos_first  = $tempcv_e2n( first );
329                remove(list_pos_first);
330                return first;
331        }
332
333        static inline Telem & pop_last(dlist(Tnode, Telem) &list) {
334                assert( &list != 0p );
335                assert( !list`is_empty );
336                $dlinks(Telem) *listLinks = & list.$links;
337                Telem & last = *listLinks->prev.elem;
338                Tnode & list_pos_last  = $tempcv_e2n( last );
339                remove(list_pos_last);
340                return last;
341        }
342
[6091b88a]343}
344
Note: See TracBrowser for help on using the repository browser.