source: libcfa/src/containers/list.hfa@ c1ee231

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since c1ee231 was d6d1f80, checked in by Michael Brooks <mlbrooks@…>, 5 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
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 static inline void ?{}( $mgd_link(tE) &this, tE* elem ) {
74 (this.elem){ elem };
75 (this.terminator){ 0p };
76 (this.is_terminator){ 0 };
77 }
78 static 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 static inline 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 static 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 Telem& ?`next(Tnode &);
122 Telem& ?`prev(Tnode &);
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
137 static inline void ?{}( dlist(Tnode, Telem) & this ) {
138 $mgd_link(Telem) selfRef = (void *) &this;
139 ( this.$links ) { selfRef, selfRef };
140 }
141
142 static inline Telem & ?`first( dlist(Tnode, Telem) &l ) {
143 return * l.$links.next.elem;
144 }
145
146 static inline Telem & ?`last( dlist(Tnode, Telem) &l ) {
147 return * l.$links.prev.elem;
148 }
149
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
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);
187 $next_link(singleton_to_insert) = $next_link(list_pos);
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);
210 $prev_link(singleton_to_insert) = $prev_link(list_pos);
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 }
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
343}
344
Note: See TracBrowser for help on using the repository browser.