Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/containers/list.hfa

    rc2794b2 r7ee3c87  
    1818#include <assert.h>
    1919
    20 forall( Decorator &, T & )
    21 struct tytagref {
    22     inline T &;
     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 &);
    23130};
    24131
    25 trait embedded( tOuter &, tMid &, tInner & ) {
    26     tytagref( tMid, tInner ) ?`inner( tOuter & );
    27 };
    28 
    29 // embedded is reflexive, with no info (void) as the type tag
    30 forall (T &)
    31 static inline tytagref(void, T) ?`inner ( T & this ) { tytagref( void, T ) ret = {this}; return ret; }
    32 
    33 // use this on every case of plan-9 inheritance, to make embedded a closure of plan-9 inheritance
    34 #define P9_EMBEDDED( derived, immedBase ) \
    35 forall( Tbase &, TdiscardPath & | { tytagref( TdiscardPath, Tbase ) ?`inner( immedBase & ); } ) \
    36     static inline tytagref(immedBase, Tbase) ?`inner( derived & this ) { \
    37         immedBase & ib = this; \
    38         Tbase & b = ib`inner; \
    39         tytagref(immedBase, Tbase) result = { b }; \
    40         return result; \
    41     }
    42 
    43 #define EMBEDDED_VIA( OUTER, MID, INNER ) \
    44    (struct { tytagref(MID, INNER) ( * ?`inner ) ( OUTER & ); }){ ?`inner }
    45 
    46 #define DLINK_VIA( TE, TLINK ) \
    47    EMBEDDED_VIA( TE, TLINK, dlink(TE) )
    48 
    49 
    50 // The origin is the position encountered at the start of iteration,
    51 // signifying, "need to advance to the first element," and at the end
    52 // of iteration, signifying, "no more elements."  Normal comsumption of
    53 // an iterator runs ?`moveNext as the first step, and uses the return
    54 // of ?`moveNext as a guard, before dereferencing the iterator.  So
    55 // normal consumption of an iterator does not dereference an iterator
    56 // in origin position.  The value of a pointer (underlying a refence)
    57 // that is exposed publicly as an iteraor, and also a pointer stored
    58 // internally in a link field, is tagged, to indicate "is the origin"
    59 // (internally, is the list-head sentinel node), or untagged, to indicate
    60 // "is a regular node."  Intent is to help a user who dereferences an
    61 // iterator in origin position (which would be an API-use error on their
    62 // part), by failing fast.
    63 
    64 #if defined( __x86_64 )
    65     // Preferred case: tag in the most-significant bit.  Dereference
    66     // has been shown to segfault consistently.  Maintenance should
    67     // list more architectures as "ok" here, to let them use the
    68     // preferred case, when valid.
    69     #define ORIGIN_TAG_BITNO ( 8 * sizeof( size_t ) - 1 )
    70 #else
    71     // Fallback case: tag in the least-significant bit.  Dereference
    72     // will often give an alignment error, but may not, e.g. if
    73     // accessing a char-typed member.  32-bit x86 uses the most-
    74     // significant bit for real room on the heap.
    75     #define ORIGIN_TAG_BITNO 0
    76 #endif
    77 #define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO)
    78 
    79 #define ORIGIN_TAG_SET(p)   ((p) |  ORIGIN_TAG_MASK)
    80 #define ORIGIN_TAG_CLEAR(p) ((p) & ~ORIGIN_TAG_MASK)
    81 #define ORIGIN_TAG_QUERY(p) ((p) &  ORIGIN_TAG_MASK)
    82 
    83 
    84 forall( tE & ) {
    85 
    86     struct dlink{
    87         tE *next;
    88         tE *prev;
    89     };
    90 
    91     static inline void ?{}( dlink(tE) & this ) {
    92         this.next = 0p;
    93         this.prev = 0p;
    94     }
    95 
    96     forall( tLinks & = dlink(tE) )
    97     struct dlist {
    98         inline dlink(tE);
    99     };
    100 
    101     forall( tLinks & | embedded( tE, tLinks, dlink(tE) ) ) {
    102         static inline tE * $get_list_origin_addr( dlist(tE, tLinks) & lst ) {
    103             dlink(tE) & link_from_null = ( * (tE *) 0p )`inner;
    104             ptrdiff_t link_offset = (ptrdiff_t) & link_from_null;
    105             size_t origin_addr = ((size_t) & lst) - link_offset;
    106             size_t preResult = ORIGIN_TAG_SET( origin_addr );
    107             return (tE *)preResult;
    108         }
    109 
    110         static inline void ?{}( dlist(tE, tLinks) & this ) {
    111             tE * listOrigin = $get_list_origin_addr( this );
    112             ( ( dlink(tE) & ) this ){ listOrigin, listOrigin } ;
    113         }
    114     }
    115 
    116 }
    117 
    118 
    119 forall( tE &, tLinks & | embedded( tE, tLinks, dlink(tE) ) ) {
    120 
    121         static inline void insert_after(tE & list_pos, tE &to_insert) {
     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) {
    122188                verify (&list_pos != 0p);
    123189                verify (&to_insert != 0p);
    124         dlink(tE) & linkToInsert = to_insert`inner;
    125                 verify(linkToInsert.prev == 0p);
    126                 verify(linkToInsert.next == 0p);
    127         tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos );
    128         dlink(tE) & list_pos_links = list_pos_elem`inner;
    129         asm( "" : : : "memory" );
    130         tE & after_raw = * list_pos_links.next;
    131         tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
    132                 linkToInsert.prev = & list_pos;
    133                 linkToInsert.next = & after_raw;
    134         dlink(tE) & afterLinks = after_elem`inner;
    135         afterLinks.prev = &to_insert;
    136                 list_pos_links.next = &to_insert;
    137         asm( "" : : : "memory" );
    138         }
    139 
    140         static inline void insert_before(tE & list_pos, tE &to_insert) {
     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) {
    141211                verify (&list_pos != 0p);
    142212                verify (&to_insert != 0p);
    143         dlink(tE) & linkToInsert = to_insert`inner;
    144                 verify(linkToInsert.next == 0p);
    145                 verify(linkToInsert.prev == 0p);
    146         tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos );
    147         dlink(tE) & list_pos_links = list_pos_elem`inner;
    148         asm( "" : : : "memory" );
    149         tE & before_raw = * (list_pos_links).prev;
    150         tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
    151                 linkToInsert.next = & list_pos;
    152                 linkToInsert.prev = & before_raw;
    153         dlink(tE) & beforeLinks = before_elem`inner;
    154         beforeLinks.next = &to_insert;
    155                 (list_pos_links).prev = &to_insert;
    156         asm( "" : : : "memory" );
    157         }
    158 
    159         static inline tE & remove(tE & list_pos) {
    160                 verify (&list_pos != 0p);
    161         verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos) );
    162         dlink(tE) & list_pos_links = list_pos`inner;
    163         tE & before_raw = * list_pos_links.prev;
    164         tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
    165         dlink(tE) & before_links = before_elem`inner;
    166         tE & after_raw = * list_pos_links.next;
    167         tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
    168         dlink(tE) & after_links = after_elem`inner;
    169         before_links.next = &after_raw;
    170         after_links.prev = &before_raw;
    171         asm( "" : : : "memory" );
    172                 list_pos_links.prev = 0p;
    173                 list_pos_links.next = 0p;
    174         asm( "" : : : "memory" );
    175         return list_pos;
    176         }
    177 
    178     static inline tE & ?`first( dlist(tE, tLinks) &lst ) {
    179         tE * firstPtr = lst.next;
    180         if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
    181         return *firstPtr;
    182     }
    183     static inline tE & ?`last ( dlist(tE, tLinks) &lst ) {
    184         tE * lastPtr = lst.prev;
    185         if (ORIGIN_TAG_QUERY((size_t)lastPtr)) lastPtr = 0p;
    186         return *lastPtr;
    187     }
    188 
    189     static inline bool ?`isEmpty( dlist(tE, tLinks) & lst ) {
    190         tE * firstPtr = lst.next;
    191         if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
    192         return firstPtr == 0p;
    193     }
    194 
    195     static inline bool ?`isListed( tE & e ) {
    196                 verify (&e != 0p);
    197         dlink(tE) & e_links = e`inner;
    198                 return (e_links.prev != 0p) || (e_links.next != 0p);
    199     }
    200 
    201     static inline tE & ?`elems( dlist(tE, tLinks) & lst ) {
    202         tE * origin = $get_list_origin_addr( lst );
    203         return *origin;
    204     }
    205 
    206     static inline bool ?`moveNext( tE && refx ) {
    207         tE && ref_inner = refx;
    208         tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
    209         &ref_inner = oldReferent`inner.next;
    210         return &ref_inner != 0p  &&
    211             ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
    212     }
    213 
    214     static inline bool ?`movePrev( tE && refx ) {
    215         tE && ref_inner = refx;
    216         tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
    217         &ref_inner = oldReferent`inner.prev;
    218         return &ref_inner != 0p  &&
    219             ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
    220     }
    221 
    222     static inline bool ?`hasNext( tE & e ) {
    223         return e`moveNext;
    224     }
    225 
    226     static inline bool ?`hasPrev( tE & e ) {
    227         return e`movePrev;
    228     }
    229 
    230     static inline tE & ?`next( tE & e ) {
    231         if( e`moveNext ) return e;
    232         return * 0p;
    233     }
    234 
    235     static inline tE & ?`prev( tE & e ) {
    236         if( e`movePrev ) return e;
    237         return * 0p;
    238     }
    239 
    240     static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) {
    241         insert_after(lst`elems, e);
    242     }
    243 
    244     static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) {
    245         insert_before(lst`elems, e);
    246     }
    247 
    248     static inline tE & try_pop_front( dlist(tE, tLinks) &lst ) {
    249         tE & first_inlist = lst`first;
    250         tE & first_item = first_inlist;
    251         if (&first_item) remove(first_inlist);
    252         return first_item;
    253     }
    254 
    255     static inline tE & try_pop_back( dlist(tE, tLinks) &lst ) {
    256         tE & last_inlist = lst`last;
    257         tE & last_item = last_inlist;
    258         if (&last_item) remove(last_inlist);
    259         return last_item;
    260     }
    261 
    262 
    263   #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
    264         static bool $validate_fwd( dlist(tE, tLinks) & this ) {
    265         if ( ! & this`first ) return ( (& this`last) == 0p);
    266 
    267         tE & lagElem = *0p;
    268 
    269         while ( tE & it = this`elems; it`moveNext ) {
    270             if (& lagElem == 0p &&  &it != & this`first ) return false;
    271             & lagElem = & it;
    272         }
    273 
    274         if (& lagElem != & this`last) return false;
    275 
    276         // TODO: verify that it is back at this`elems;
    277         return true;
    278         }
    279         static bool $validate_rev( dlist(tE, tLinks) & this ) {
    280         if ( ! & this`last ) return ( (& this`first) == 0p);
    281 
    282         tE & lagElem = *0p;
    283 
    284         while ( tE & it = this`elems; it`movePrev ) {
    285             if (& lagElem == 0p &&  &it != & this`last ) return false;
    286             & lagElem = & it;
    287         }
    288 
    289         if (& lagElem != & this`first) return false;
    290 
    291         // TODO: verify that it is back at this`elems;
    292         return true;
    293         }
    294         static bool validate( dlist(tE, tLinks) & this ) {
    295                 return $validate_fwd(this) && $validate_rev(this);
    296         }
    297   #endif
     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        }
    298349
    299350}
Note: See TracChangeset for help on using the changeset viewer.