source: libcfa/src/containers/list.hfa@ 726b748

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since 726b748 was e857743, checked in by Thierry Delisle <tdelisle@…>, 5 years ago

Forgot to commit the missing 'pragma once' in list.hfa
  • Property mode set to 100644
File size: 10.5 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( 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 };
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 forall ( otype tInit | { void ?{}( $mgd_link(tE) &, tInit); } )
86 static inline void ?=?( $mgd_link(tE) &this, tInit i ) {
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 };
97 static inline void ?{}( $dlinks(tE) &this ) {
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 &);
122
123 Telem& ?`next(Tnode &);
124 Telem& ?`prev(Tnode &);
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
139 static inline void ?{}( dlist(Tnode, Telem) & this ) {
140 $mgd_link(Telem) selfRef = (void *) &this;
141 ( this.$links ) { selfRef, selfRef };
142 }
143
144 static inline Telem & ?`first( dlist(Tnode, Telem) &l ) {
145 return * l.$links.next.elem;
146 }
147
148 static inline Telem & ?`last( dlist(Tnode, Telem) &l ) {
149 return * l.$links.prev.elem;
150 }
151
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
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);
189 $next_link(singleton_to_insert) = $next_link(list_pos);
190 if ($next_link(list_pos).is_terminator) {
191 dlist(Tnode, Telem) *list = ( dlist(Tnode, Telem) * ) $next_link(list_pos).terminator;
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);
212 $prev_link(singleton_to_insert) = $prev_link(list_pos);
213 if ($prev_link(list_pos).is_terminator) {
214 dlist(Tnode, Telem) *list = ( dlist(Tnode, Telem) * ) $prev_link(list_pos).terminator;
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 ) {
279 dlist(Tnode, Telem) * tgt_before = ( dlist(Tnode, Telem) * ) $prev_link(list_pos).terminator;
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 ) {
289 dlist(Tnode, Telem) * tgt_after = ( dlist(Tnode, Telem) * ) $next_link(list_pos).terminator;
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 }
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
345}
346
Note: See TracBrowser for help on using the repository browser.