source: libcfa/src/containers/list2.hfa@ f55d54d

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast-unique-expr pthread-emulation qualifiedEnum stuck-waitfor-destruct
Last change on this file since f55d54d was 9e2341b4, checked in by Michael Brooks <mlbrooks@…>, 5 years ago

Baseline commit of new linked-list implementation and test.

Using a separate header with intention to port old uses first, then rename.
  • Property mode set to 100644
File size: 9.8 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
20forall( T & ) struct tag {};
21#define ttag(T) ((tag(T)){})
22#define ztag(n) ttag(Z(n))
23
24extern "C" {
25 void * memset ( void * ptr, int value, size_t num );
26}
27
28trait embedded( tOuter &, tInner & ) {
29 tInner & ?`inner( tOuter & );
30};
31
32// embedded is reflexive
33forall( tX & )
34static inline tX & ?`inner( tX & this ) { return this; }
35
36// use this on every case of plan-9 inheritance, to make embedded a closure of plan-9 inheritance
37#define P9_EMBEDDED( tOuter, tInner ) \
38 static inline tInner & ?`inner( tOuter & this ) { return this; }
39
40
41
42
43#define ORIGIN_TAG_BITNO 63
44#define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO)
45
46#define ORIGIN_TAG_SET(p) ((p) | ORIGIN_TAG_MASK)
47#define ORIGIN_TAG_CLEAR(p) ((p) & ~ORIGIN_TAG_MASK)
48#define ORIGIN_TAG_QUERY(p) ((p) & ORIGIN_TAG_MASK)
49
50// #define ORIGIN_TAG_SET(p) (p)
51// #define ORIGIN_TAG_CLEAR(p) (p)
52// #define ORIGIN_TAG_QUERY(p) (0)
53
54
55forall( tE & ) {
56
57 struct dlink{
58 tE *next;
59 tE *prev;
60 };
61
62 static inline void ?{}( dlink(tE) & this ) {
63 this.next = 0p;
64 this.prev = 0p;
65 }
66
67 forall( tLinks & = tE ) {
68
69 struct dlist {
70 inline dlink(tE);
71 };
72
73 struct diref {
74 inline tE &;
75 };
76 }
77
78 forall( tLinks & = tE | embedded( tE, tLinks ) | embedded( tLinks, dlink(tE) ) ) {
79 static inline tE * $get_list_origin_addr( dlist(tE, tLinks) & lst ) {
80 dlink(tE) & link_from_null = ( * (tE *) 0p )`inner`inner;
81 ptrdiff_t link_offset = (ptrdiff_t) & link_from_null;
82 size_t origin_addr = ((size_t) & lst) - link_offset;
83 size_t preResult = ORIGIN_TAG_SET( origin_addr );
84 return (tE *)preResult;
85 }
86
87 static inline void ?{}( dlist(tE, tLinks) & this ) {
88 tE * listOrigin = $get_list_origin_addr( this );
89 ( ( dlink(tE) & ) this ){ listOrigin, listOrigin } ;
90 }
91
92 // redundant
93 // void ?{}( diref(tE, tLinks) & this, tE & target ) {
94 // tE && ref = this;
95 // &ref = &target;
96 // }
97 }
98
99}
100
101
102forall( tE &, tLinks & | embedded( tE, tLinks ) | embedded( tLinks, dlink(tE) ) ) {
103
104 static inline void insert_after(diref(tE, tLinks) list_pos, tE &to_insert) {
105 verify (&list_pos != 0p);
106 verify (&to_insert != 0p);
107 dlink(tE) & linkToInsert = to_insert`inner`inner;
108 verify(linkToInsert.prev == 0p);
109 verify(linkToInsert.next == 0p);
110 tE & list_pos_raw = list_pos;
111 tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos_raw );
112 tE & after_raw = * (list_pos_elem`inner`inner).next;
113 tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
114 linkToInsert.prev = & list_pos_raw;
115 linkToInsert.next = & after_raw;
116 (after_elem`inner`inner).prev = &to_insert;
117 (list_pos_elem`inner`inner).next = &to_insert;
118 }
119
120 static inline void insert_before(diref(tE, tLinks) list_pos, tE &to_insert) {
121 verify (&list_pos != 0p);
122 verify (&to_insert != 0p);
123 dlink(tE) & linkToInsert = to_insert`inner`inner;
124 verify(linkToInsert.next == 0p);
125 verify(linkToInsert.prev == 0p);
126 tE & list_pos_raw = list_pos;
127 tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos_raw );
128 tE & before_raw = * (list_pos_elem`inner`inner).prev;
129 tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
130 linkToInsert.next = & list_pos_raw;
131 linkToInsert.prev = & before_raw;
132 (before_elem`inner`inner).next = &to_insert;
133 (list_pos_elem`inner`inner).prev = &to_insert;
134 }
135
136 static inline void doRemove(
137 dlink(tE) & this_links, dlink(tE) & before_links, dlink(tE) & after_links,
138 tE & before_target, tE & after_target ) {
139
140 before_links.next = &after_target;
141 after_links.prev = &before_target;
142
143 asm( "" : : : "memory" );
144
145 this_links.prev = 0p;
146 this_links.next = 0p;
147 }
148
149 static inline tE & remove(diref(tE, tLinks) list_pos) {
150 verify (&list_pos != 0p);
151 tE & list_pos_elem = list_pos;
152 verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos_elem) );
153 dlink(tE) & list_pos_links = list_pos_elem`inner`inner;
154 tE & before_raw = * list_pos_links.prev;
155 tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
156 dlink(tE) & before_links = before_elem`inner`inner;
157 tE & after_raw = * list_pos_links.next;
158 tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
159 dlink(tE) & after_links = after_elem`inner`inner;
160
161 doRemove(list_pos_links, before_links, after_links, before_raw, after_raw);
162
163 return list_pos_elem;
164 }
165/*
166 static inline tE & remove(diref(tE, tLinks) list_pos) {
167 verify (&list_pos != 0p);
168 tE & list_pos_elem = list_pos;
169 verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos_elem) );
170 dlink(tE) & list_pos_links = list_pos_elem`inner`inner;
171 tE & before_raw = * list_pos_links.prev;
172 tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
173 dlink(tE) & before_links = before_elem`inner`inner;
174 tE & after_raw = * list_pos_links.next;
175 tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
176 dlink(tE) & after_links = after_elem`inner`inner;
177 before_links.next = &after_raw;
178 after_links.prev = &before_raw;
179asm( "" : : : "memory" );
180 list_pos_links.prev = 0p;
181 list_pos_links.next = 0p;
182 return list_pos_elem;
183 }
184*/
185 static inline diref(tE, tLinks) ?`first( dlist(tE, tLinks) &lst ) {
186 tE * firstPtr = lst.next;
187 if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
188 diref(tE, tLinks) ret = { *firstPtr };
189 return ret;
190 }
191 static inline diref(tE, tLinks) ?`last ( dlist(tE, tLinks) &lst ) {
192 tE * lastPtr = lst.prev;
193 if (ORIGIN_TAG_QUERY((size_t)lastPtr)) lastPtr = 0p;
194 diref(tE, tLinks) ret = { *lastPtr };
195 return ret;
196 }
197
198 static inline int ?!=?( const diref(tE, tLinks) & list_pos, zero_t ) {
199 tE & list_pos_elem = list_pos;
200 if (ORIGIN_TAG_QUERY((size_t) & list_pos_elem)) return 0;
201 return & list_pos_elem != 0p;
202 }
203
204 static inline int DUMB_COMPARE( diref(tE, tLinks) list_pos, tE * elem ) {
205 tE & signifiedLhs = list_pos;
206 return &signifiedLhs == elem;
207 }
208
209 static inline diref(tE, tLinks) ?`from( tE & elem ) {
210 diref(tE, tLinks) ret = { elem };
211 return ret;
212 }
213
214 static inline diref(tE, tLinks) ?`elems( dlist(tE, tLinks) & lst ) {
215 tE * origin = $get_list_origin_addr( lst );
216 diref(tE, tLinks) ret = { *origin };
217 return ret;
218 }
219
220 static inline bool ?`moveNext( diref(tE, tLinks) & refx ) {
221 tE && ref_inner = refx;
222 tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
223 &ref_inner = oldReferent`inner`inner.next;
224 return &ref_inner != 0p &&
225 ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
226 }
227
228 static inline bool ?`movePrev( diref(tE, tLinks) & refx ) {
229 tE && ref_inner = refx;
230 tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
231 &ref_inner = oldReferent`inner`inner.prev;
232 return &ref_inner != 0p &&
233 ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
234 }
235
236 static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) {
237 insert_after(lst`elems, e);
238 }
239
240 static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) {
241 insert_before(lst`elems, e);
242 }
243
244
245 #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
246 static bool $validate_fwd( dlist(tE, tLinks) & this ) {
247 if ( ! & this`first ) return ( (& this`last) == 0p);
248
249 tE & lagElem = *0p;
250
251 while ( diref(tE, tLinks) it = this`elems; it`moveNext ) {
252 if (& lagElem == 0p && &it != & this`first ) return false;
253 & lagElem = & it;
254 }
255
256 if (& lagElem != & this`last) return false;
257
258 // TODO: verify that it is back at this`elems;
259 return true;
260 }
261 static bool $validate_rev( dlist(tE, tLinks) & this ) {
262 if ( ! & this`last ) return ( (& this`first) == 0p);
263
264 tE & lagElem = *0p;
265
266 while ( diref(tE, tLinks) it = this`elems; it`movePrev ) {
267 if (& lagElem == 0p && &it != & this`last ) return false;
268 & lagElem = & it;
269 }
270
271 if (& lagElem != & this`first) return false;
272
273 // TODO: verify that it is back at this`elems;
274 return true;
275 }
276 static bool validate( dlist(tE, tLinks) & this ) {
277 return $validate_fwd(this) && $validate_rev(this);
278 }
279 #endif
280
281}
282
283forall( tE & | embedded( tE, dlink(tE) ) ) {
284 static inline void insert_after(tE & list_pos, tE &to_insert ) {
285 diref(tE, tE) list_pos_ref = list_pos`from;
286 insert_after( list_pos_ref, to_insert );
287 }
288 static inline void insert_before(tE & list_pos, tE &to_insert ) {
289 diref(tE, tE) list_pos_ref = list_pos`from;
290 insert_before( list_pos_ref, to_insert );
291 }
292 static inline tE & remove(tE & list_pos ) {
293 diref(tE, tE) list_pos_ref = list_pos`from;
294 return remove( list_pos_ref );
295 }
296 static inline bool ?`moveNext( tE && ref ) {
297 diref(tE, tE) & ref_dird = (diref(tE, tE) &) & ref;
298 return ref_dird`moveNext;
299 }
300 static inline bool ?`movePrev( tE && ref ) {
301 diref(tE, tE) & ref_dird = (diref(tE, tE) &) & ref;
302 return ref_dird`movePrev;
303 }
304
305}
Note: See TracBrowser for help on using the repository browser.