| 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) \
|
|---|
| 19 | static inline ELEM& $tempcv_n2e(NODE &node) { \
|
|---|
| 20 | return node; \
|
|---|
| 21 | } \
|
|---|
| 22 | \
|
|---|
| 23 | static inline NODE& $tempcv_e2n(ELEM &node) { \
|
|---|
| 24 | return node; \
|
|---|
| 25 | } \
|
|---|
| 26 | \
|
|---|
| 27 | static 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 | \
|
|---|
| 34 | static 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 | \
|
|---|
| 41 | static 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 | \
|
|---|
| 47 | static 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) \
|
|---|
| 54 | struct STRUCT_IN_THELIST { \
|
|---|
| 55 | inline STRUCT; \
|
|---|
| 56 | }; \
|
|---|
| 57 | \
|
|---|
| 58 | void ?{}(STRUCT_IN_THELIST &) = void; \
|
|---|
| 59 | \
|
|---|
| 60 | static inline STRUCT_IN_THELIST& ?`IN_THELIST(STRUCT &this) { \
|
|---|
| 61 | return (STRUCT_IN_THELIST&)this; \
|
|---|
| 62 | }
|
|---|
| 63 |
|
|---|
| 64 | #define __DLISTED_MGD_JUSTIMPL(STRUCT)
|
|---|
| 65 |
|
|---|
| 66 | forall( 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 | inline void ?{}( $mgd_link(tE) &this, tE* elem ) {
|
|---|
| 74 | (this.elem){ elem };
|
|---|
| 75 | (this.terminator){ 0p };
|
|---|
| 76 | (this.is_terminator){ 0 };
|
|---|
| 77 | }
|
|---|
| 78 | 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 | 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 | 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 |
|
|---|
| 115 | trait $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 |
|
|---|
| 122 | forall (dtype Tnode, dtype Telem | $dlistable(Tnode, Telem)) {
|
|---|
| 123 |
|
|---|
| 124 | // implemented as a sentinel item in an underlying cicrular list
|
|---|
| 125 | // theList.$links.next is first
|
|---|
| 126 | // theList.$links.prev is last
|
|---|
| 127 | // note this allocation preserves prev-next composition as an identity
|
|---|
| 128 | struct dlist {
|
|---|
| 129 | $dlinks(Telem) $links;
|
|---|
| 130 | };
|
|---|
| 131 |
|
|---|
| 132 | // an empty dlist
|
|---|
| 133 | // links refer to self, making a tight circle
|
|---|
| 134 | void ?{}( dlist(Tnode, Telem) & this ) {
|
|---|
| 135 | $mgd_link(Telem) selfRef = (void *) &this;
|
|---|
| 136 | ( this.$links ) { selfRef, selfRef };
|
|---|
| 137 | }
|
|---|
| 138 |
|
|---|
| 139 | Telem & ?`first( dlist(Tnode, Telem) &l ) {
|
|---|
| 140 | return * l.$links.next.elem;
|
|---|
| 141 | }
|
|---|
| 142 |
|
|---|
| 143 | Telem & ?`last( dlist(Tnode, Telem) &l ) {
|
|---|
| 144 | return * l.$links.prev.elem;
|
|---|
| 145 | }
|
|---|
| 146 |
|
|---|
| 147 | static inline void insert_after(Tnode &list_pos, Telem &to_insert) {
|
|---|
| 148 | assert (&list_pos != 0p);
|
|---|
| 149 | assert (&to_insert != 0p);
|
|---|
| 150 | Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
|
|---|
| 151 | assert($prev_link(singleton_to_insert).elem == 0p);
|
|---|
| 152 | assert($next_link(singleton_to_insert).elem == 0p);
|
|---|
| 153 | $prev_link(singleton_to_insert) = & $tempcv_n2e(list_pos);
|
|---|
| 154 | $next_link(singleton_to_insert) = $next_link(list_pos).elem;
|
|---|
| 155 | if ($next_link(list_pos).is_terminator) {
|
|---|
| 156 | dlist(Tnode, Telem) *list = $next_link(list_pos).terminator;
|
|---|
| 157 | $dlinks(Telem) *list_links = & list->$links;
|
|---|
| 158 | $mgd_link(Telem) *list_last = & list_links->prev;
|
|---|
| 159 | *list_last = &to_insert;
|
|---|
| 160 | } else {
|
|---|
| 161 | Telem *list_pos_next = $next_link(list_pos).elem;
|
|---|
| 162 | if (list_pos_next) {
|
|---|
| 163 | Tnode & lpn_inlist = $tempcv_e2n(*list_pos_next);
|
|---|
| 164 | $prev_link(lpn_inlist) = &to_insert;
|
|---|
| 165 | }
|
|---|
| 166 | }
|
|---|
| 167 | $next_link(list_pos) = &to_insert;
|
|---|
| 168 | }
|
|---|
| 169 |
|
|---|
| 170 | static inline void insert_before(Tnode &list_pos, Telem &to_insert) {
|
|---|
| 171 | assert (&list_pos != 0p);
|
|---|
| 172 | assert (&to_insert != 0p);
|
|---|
| 173 | Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
|
|---|
| 174 | assert($prev_link(singleton_to_insert).elem == 0p);
|
|---|
| 175 | assert($next_link(singleton_to_insert).elem == 0p);
|
|---|
| 176 | $next_link(singleton_to_insert) = & $tempcv_n2e(list_pos);
|
|---|
| 177 | $prev_link(singleton_to_insert) = $prev_link(list_pos).elem;
|
|---|
| 178 | if ($prev_link(list_pos).is_terminator) {
|
|---|
| 179 | dlist(Tnode, Telem) *list = $prev_link(list_pos).terminator;
|
|---|
| 180 | $dlinks(Telem) *list_links = & list->$links;
|
|---|
| 181 | $mgd_link(Telem) *list_first = & list_links->next;
|
|---|
| 182 | *list_first = &to_insert;
|
|---|
| 183 | } else {
|
|---|
| 184 | Telem *list_pos_prev = $prev_link(list_pos).elem;
|
|---|
| 185 | if (list_pos_prev) {
|
|---|
| 186 | Tnode & lpp_inlist = $tempcv_e2n(*list_pos_prev);
|
|---|
| 187 | $next_link(lpp_inlist) = &to_insert;
|
|---|
| 188 | }
|
|---|
| 189 | }
|
|---|
| 190 | $prev_link(list_pos) = &to_insert;
|
|---|
| 191 | }
|
|---|
| 192 |
|
|---|
| 193 | static inline void insert_first(dlist(Tnode, Telem) &list, Telem &to_insert) {
|
|---|
| 194 | assert (&list != 0p);
|
|---|
| 195 | assert (&to_insert != 0p);
|
|---|
| 196 | Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
|
|---|
| 197 | assert($prev_link(singleton_to_insert).elem == 0p);
|
|---|
| 198 | assert($next_link(singleton_to_insert).elem == 0p);
|
|---|
| 199 |
|
|---|
| 200 | $prev_link(singleton_to_insert) = (void*) &list;
|
|---|
| 201 | $next_link(singleton_to_insert) = list.$links.next;
|
|---|
| 202 |
|
|---|
| 203 | $dlinks(Telem) *listLinks = & list.$links;
|
|---|
| 204 | if (listLinks->next.is_terminator) {
|
|---|
| 205 | $mgd_link(Telem) * listPrevReference = & listLinks->prev;
|
|---|
| 206 | *listPrevReference = &to_insert;
|
|---|
| 207 | } else {
|
|---|
| 208 | Tnode & next_inlist = $tempcv_e2n(*list.$links.next.elem);
|
|---|
| 209 | $prev_link(next_inlist) = &to_insert;
|
|---|
| 210 | }
|
|---|
| 211 | $mgd_link(Telem) * listNextReference = & listLinks->next;
|
|---|
| 212 | *listNextReference = &to_insert;
|
|---|
| 213 | }
|
|---|
| 214 |
|
|---|
| 215 | static inline void insert_last(dlist(Tnode, Telem) &list, Telem &to_insert) {
|
|---|
| 216 | assert (&list != 0p);
|
|---|
| 217 | assert (&to_insert != 0p);
|
|---|
| 218 | Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
|
|---|
| 219 | assert($next_link(singleton_to_insert).elem == 0p);
|
|---|
| 220 | assert($prev_link(singleton_to_insert).elem == 0p);
|
|---|
| 221 |
|
|---|
| 222 | $next_link(singleton_to_insert) = (void*) &list;
|
|---|
| 223 | $prev_link(singleton_to_insert) = list.$links.prev;
|
|---|
| 224 |
|
|---|
| 225 | $dlinks(Telem) *listLinks = & list.$links;
|
|---|
| 226 | if (listLinks->prev.is_terminator) {
|
|---|
| 227 | $mgd_link(Telem) * listNextReference = & listLinks->next;
|
|---|
| 228 | *listNextReference = &to_insert;
|
|---|
| 229 | } else {
|
|---|
| 230 | Tnode & prev_inlist = $tempcv_e2n(*list.$links.prev.elem);
|
|---|
| 231 | $next_link(prev_inlist) = &to_insert;
|
|---|
| 232 | }
|
|---|
| 233 | $mgd_link(Telem) * listPrevReference = & listLinks->prev;
|
|---|
| 234 | *listPrevReference = &to_insert;
|
|---|
| 235 | }
|
|---|
| 236 |
|
|---|
| 237 | static inline void remove(Tnode &list_pos) {
|
|---|
| 238 | assert( &list_pos != 0p );
|
|---|
| 239 |
|
|---|
| 240 | $mgd_link(Telem) &incoming_from_prev = *0p;
|
|---|
| 241 | $mgd_link(Telem) &incoming_from_next = *0p;
|
|---|
| 242 |
|
|---|
| 243 | if ( $prev_link(list_pos).is_terminator ) {
|
|---|
| 244 | dlist(Tnode, Telem) * tgt_before = $prev_link(list_pos).terminator;
|
|---|
| 245 | $dlinks(Telem) * links_before = & tgt_before->$links;
|
|---|
| 246 | &incoming_from_prev = & links_before->next;
|
|---|
| 247 | } else if ($prev_link(list_pos).elem) {
|
|---|
| 248 | Telem * tgt_before = $prev_link(list_pos).elem;
|
|---|
| 249 | Tnode & list_pos_before = $tempcv_e2n(*tgt_before);
|
|---|
| 250 | &incoming_from_prev = & $next_link(list_pos_before);
|
|---|
| 251 | }
|
|---|
| 252 |
|
|---|
| 253 | if ( $next_link(list_pos).is_terminator ) {
|
|---|
| 254 | dlist(Tnode, Telem) * tgt_after = $next_link(list_pos).terminator;
|
|---|
| 255 | $dlinks(Telem) * links_after = & tgt_after->$links;
|
|---|
| 256 | &incoming_from_next = & links_after->prev;
|
|---|
| 257 | } else if ($next_link(list_pos).elem) {
|
|---|
| 258 | Telem * tgt_after = $next_link(list_pos).elem;
|
|---|
| 259 | Tnode & list_pos_after = $tempcv_e2n(*tgt_after );
|
|---|
| 260 | &incoming_from_next = & $prev_link(list_pos_after );
|
|---|
| 261 | }
|
|---|
| 262 |
|
|---|
| 263 | if (& incoming_from_prev) {
|
|---|
| 264 | incoming_from_prev = $next_link(list_pos);
|
|---|
| 265 | }
|
|---|
| 266 | if (& incoming_from_next) {
|
|---|
| 267 | incoming_from_next = $prev_link(list_pos);
|
|---|
| 268 | }
|
|---|
| 269 |
|
|---|
| 270 | $next_link(list_pos) = (Telem*) 0p;
|
|---|
| 271 | $prev_link(list_pos) = (Telem*) 0p;
|
|---|
| 272 | }
|
|---|
| 273 | }
|
|---|
| 274 |
|
|---|
