source: libcfa/src/containers/list.hfa @ 7ee3c87

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

Dlist adjustments for performance and perf testability.

Replaced a polymorphic helper routine with two code-duplicated monomorphic routines.

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