source: tests/zombies/linked-list-perf/mike-old.hfa@ 389fbf5

Last change on this file since 389fbf5 was 69914cbc, checked in by Michael Brooks <mlbrooks@…>, 4 years ago

Replacing "Mike's old linked list" with "Mike's new linked list," including replatforming uses of the old one.

libcfa/src/containers/list.hfa ---[becomes]--> tests/zombies/linked-list-perf/mike-old.hfa
libcfa/src/containers/list2.hfa ---[becomes]--> libcfa/src/containers/list.hfa

There are no more multiple versions of "Mike's list" in libcfa, nor tests thereof.

The libcfa concurrency uses (alarm, kernel and ready_queue) are hereby ported to "Mike's new."

A best-effort port of executor, which was found not compiling with errors that seem unrelated to the linked list, is attempted too.
  • 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.