source: libcfa/src/bits/sequence.hfa @ d0502a3

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since d0502a3 was d0502a3, checked in by Michael Brooks <mlbrooks@…>, 3 years ago

Fixing function bodies in bits/containers and bits/sequence so they can coexist with declarations in vector Fixes #237?

libcfa/src/bits/* the fixes
libcfa/src/fstream.hfa adding the desired include, which wasn't possible under #237
tests/includes/* adding tests for these problematic combinations

  • Property mode set to 100644
File size: 10.6 KB
RevLine 
[ab1b971]1//
2// Cforall Version 1.0.0 Copyright (C) 2021 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// bits/sequence.hfa -- PUBLIC
8// Intrusive doubly-linked list
9//
10// Author           : Colby Alexander Parsons & Peter A. Buhr
11// Created On       : Thu Jan 21 19:46:50 2021
12// Last Modified By :
13// Last Modified On :
14// Update Count     :
15//
16
[5e82d56]17#pragma once
18
[7d4ce2a]19#include "bits/collection.hfa"
[e43aa14]20#include "bits/defs.hfa"
[5e82d56]21
22struct Seqable {
[e43aa14]23        __cfa_anonymous_object(Colable);
[ab1b971]24        // pointer to previous node in the list
25        struct Seqable * back;
[5e82d56]26};
27
[e43aa14]28#ifdef __cforall
29static inline {
[7c1144b]30        // PUBLIC
31
[d0502a3]32        void ?{}( Seqable & sq ) {
[58870e6b]33                ((Colable &)sq){};
[d0502a3]34                sq.back = 0p;
[5e82d56]35        } // post: ! listed()
36
[a78c3ff]37        Seqable & getBack( Seqable & sq ) with( sq ) {
38                return *back;
[5e82d56]39        }
40
[7c1144b]41        // PRIVATE
42
[5e82d56]43        Seqable *& Back( Seqable * sq ) {
44                return sq->back;
45        }
46} // distribution
47
[9536761]48
49// A Sequence(T) is a Collection(T) defining the ordering of a uStack and uQueue, and to insert and remove elements
50// anywhere in the sequence. T must be a public descendant of uSeqable.
51
52// The implementation is a typical doubly-linked list, except the next field of the last node points at the first node
53// and the back field of the last node points at the first node (circular).
54
[ab1b971]55forall( T & ) {
[5e82d56]56        struct Sequence {
[ab1b971]57                // Plan 9 inheritance
58                inline Collection;
[5e82d56]59        };
60
[e43aa14]61        static inline {
[5e82d56]62                void ?{}( Sequence(T) &, const Sequence(T) & ) = void; // no copy
63                Sequence(T) & ?=?( const Sequence(T) & ) = void; // no assignment
64
[ab1b971]65                void ?{}( Sequence(T) & s ) with( s ) {
[58870e6b]66                        ((Collection &)s){};
[9536761]67                }       // post: isEmpty()
[ab1b971]68        }
69
70        static inline forall(| { T *& Back ( T * ); T *& Next ( T * ); }) {
71                // wrappers to make Collection have T
72                T & head( Sequence(T) & s ) with( s ) {
73                        return *(T *)head( (Collection &)s );
74                } // post: empty() & head() == 0 | !empty() & head() in *s
[5e82d56]75
[9536761]76                // Return a pointer to the last sequence element, without removing it.
[b37515b]77                T & tail( Sequence(T) & s ) with( s ) {
[58870e6b]78                        return root ? (T &)*Back( &head( s ) ) : *0p;
[a5a67ab8]79                }       // post: empty() & tail() == 0 | !empty() & tail() in *s
[5e82d56]80
[7c1144b]81                // Return a pointer to the element after *n, or 0p if list empty.
[a5a67ab8]82                T * succ( Sequence(T) & s, T * n ) with( s ) {  // pre: *n in *s
[7c1144b]83                        #ifdef __CFA_DEBUG__
[a5a67ab8]84                        if ( ! listed( n ) ) abort( "(Sequence &)%p.succ( %p ) : Node is not on a list.", &s, n );
[7c1144b]85                        #endif // __CFA_DEBUG__
[58870e6b]86                        return Next( n ) == &head( s ) ? 0p : Next( n );
[a5a67ab8]87                } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *s
[5e82d56]88
[9536761]89                // Return a pointer to the element before *n, or 0p if list empty.
[a5a67ab8]90                T * pred( Sequence(T) & s, T * n ) with( s ) {  // pre: *n in *s
[7c1144b]91                        #ifdef __CFA_DEBUG__
[a5a67ab8]92                        if ( ! listed( n ) ) abort( "(Sequence &)%p.pred( %p ) : Node is not on a list.", &s, n );
[7c1144b]93                        #endif // __CFA_DEBUG__
[58870e6b]94                        return n == &head( s ) ? 0p : Back( n );
[9536761]95                } // post: n == head() & head(n) == 0 | n != head() & *pred(n) in *s
[5e82d56]96
97
[9536761]98                // Insert *n into the sequence before *bef, or at the end if bef == 0p.
[a3a76ea]99                T & insertBef( Sequence(T) & s, T & n, T & bef ) with( s ) { // pre: !n->listed() & *bef in *s
[7c1144b]100                        #ifdef __CFA_DEBUG__
[b37515b]101                        if ( listed( &n ) ) abort( "(Sequence &)%p.insertBef( %p, %p ) : Node is already on another list.", &s, n, &bef );
[7c1144b]102                        #endif // __CFA_DEBUG__
[a78c3ff]103                        if ( &bef == &head( s ) ) {                                     // must change root
[5e82d56]104                                if ( root ) {
[58870e6b]105                                        Next( &n ) = &head( s );
106                                        Back( &n ) = Back( &head( s ) );
[5e82d56]107                                        // inserted node must be consistent before it is seen
108                                        asm( "" : : : "memory" );                       // prevent code movement across barrier
[58870e6b]109                                        Back( &head( s ) ) = &n;
110                                        Next( Back( &n ) ) = &n;
[5e82d56]111                                } else {
[58870e6b]112                                        Next( &n ) = &n;
113                                        Back( &n ) = &n;
[5e82d56]114                                } // if
115                                // inserted node must be consistent before it is seen
116                                asm( "" : : : "memory" );                               // prevent code movement across barrier
[b37515b]117                                root = &n;
[5e82d56]118                        } else {
[a78c3ff]119                                if ( ! &bef ) &bef = &head( s );
[58870e6b]120                                Next( &n ) = &bef;
121                                Back( &n ) = Back( &bef );
[5e82d56]122                                // inserted node must be consistent before it is seen
123                                asm( "" : : : "memory" );                               // prevent code movement across barrier
[58870e6b]124                                Back( &bef ) = &n;
125                                Next( Back( &n ) ) = &n;
[5e82d56]126                        } // if
[a3a76ea]127                        return n;
[5e82d56]128                }       // post: n->listed() & *n in *s & succ(n) == bef
129
130
131                // Insert *n into the sequence after *aft, or at the beginning if aft == 0.
[a3a76ea]132                T & insertAft( Sequence(T) & s, T & aft, T & n ) with( s ) {    // pre: !n->listed() & *aft in *s
[7c1144b]133                        #ifdef __CFA_DEBUG__
[b37515b]134                        if ( listed( &n ) ) abort( "(Sequence &)%p.insertAft( %p, %p ) : Node is already on another list.", &s, &aft, &n );
[7c1144b]135                        #endif // __CFA_DEBUG__
[b37515b]136                        if ( ! &aft ) {                                                         // must change root
[5e82d56]137                                if ( root ) {
[58870e6b]138                                        Next( &n ) = &head( s );
139                                        Back( &n ) = Back( &head( s ) );
[5e82d56]140                                        // inserted node must be consistent before it is seen
141                                        asm( "" : : : "memory" );                       // prevent code movement across barrier
[58870e6b]142                                        Back( &head( s ) ) = &n;
143                                        Next( Back( &n ) ) = &n;
[5e82d56]144                                } else {
[58870e6b]145                                        Next( &n ) = &n;
146                                        Back( &n ) = &n;
[5e82d56]147                                } // if
148                                asm( "" : : : "memory" );                               // prevent code movement across barrier
[b37515b]149                                root = &n;
[5e82d56]150                        } else {
[58870e6b]151                                Next( &n ) = Next( &aft );
152                                Back( &n ) = &aft;
[5e82d56]153                                // inserted node must be consistent before it is seen
154                                asm( "" : : : "memory" );                               // prevent code movement across barrier
[58870e6b]155                                Back( Next( &n ) ) = &n;
156                                Next( &aft ) = &n;
[5e82d56]157                        } // if
[a3a76ea]158                        return n;
[9536761]159                } // post: n->listed() & *n in *s & succ(n) == bef
[ab1b971]160
[5e82d56]161                // pre: n->listed() & *n in *s
[a3a76ea]162                T & remove( Sequence(T) & s, T & n ) with( s ) { // O(1)
[7c1144b]163                        #ifdef __CFA_DEBUG__
[b37515b]164                        if ( ! listed( &n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s, &n );
[7c1144b]165                        #endif // __CFA_DEBUG__
[a78c3ff]166                        if ( &n == &head( s ) ) {
[58870e6b]167                                if ( Next( &head( s ) ) == &head( s ) ) root = 0p;
168                                else root = Next( &head( s ) );
[5e82d56]169                        } // if
[58870e6b]170                        Back( Next( &n ) ) = Back( &n );
171                        Next( Back( &n ) ) = Next( &n );
172                        Next( &n ) = Back( &n ) = 0p;
[a3a76ea]173                        return n;
[9536761]174                } // post: !n->listed()
[5e82d56]175
176                // Add an element to the head of the sequence.
[a3a76ea]177                T & addHead( Sequence(T) & s, T & n ) {                 // pre: !n->listed(); post: n->listed() & head() == n
178                        return insertAft( s, *0p, n );
[5e82d56]179                }
[9536761]180
[5e82d56]181                // Add an element to the tail of the sequence.
[a3a76ea]182                T & addTail( Sequence(T) & s, T & n ) {                 // pre: !n->listed(); post: n->listed() & head() == n
183                        return insertBef( s, n, *0p );
[5e82d56]184                }
[9536761]185
[5e82d56]186                // Add an element to the tail of the sequence.
[a3a76ea]187                T & add( Sequence(T) & s, T & n ) {                             // pre: !n->listed(); post: n->listed() & head() == n
188                        return addTail( s, n );
[5e82d56]189                }
[9536761]190
[5e82d56]191                // Remove and return the head element in the sequence.
[b37515b]192                T & dropHead( Sequence(T) & s ) {
[a78c3ff]193                        T & n = head( s );
194                        return &n ? remove( s, n ), n : *0p;
[5e82d56]195                }
[9536761]196
[5e82d56]197                // Remove and return the head element in the sequence.
[b37515b]198                T & drop( Sequence(T) & s ) {
[5e82d56]199                        return dropHead( s );
200                }
[9536761]201
[5e82d56]202                // Remove and return the tail element in the sequence.
[b37515b]203                T & dropTail( Sequence(T) & s ) {
204                        T & n = tail( s );
205                        return &n ? remove( s, n ), n : *0p;
[5e82d56]206                }
207
208                // Transfer the "from" list to the end of s sequence; the "from" list is empty after the transfer.
209                void transfer( Sequence(T) & s, Sequence(T) & from ) with( s ) {
210                        if ( empty( from ) ) return;                            // "from" list empty ?
211                        if ( empty( s ) ) {                                                     // "to" list empty ?
212                                root = from.root;
213                        } else {                                                                        // "to" list not empty
[58870e6b]214                                T * toEnd = Back( &head( s ) );
215                                T * fromEnd = Back( &head( from ) );
[e43aa14]216                                Back( (T *)root ) = fromEnd;
[58870e6b]217                                Next( fromEnd ) = &head( s );
[e43aa14]218                                Back( (T *)from.root ) = toEnd;
[58870e6b]219                                Next( toEnd ) = &head( from );
[5e82d56]220                        } // if
221                        from.root = 0p;                                                         // mark "from" list empty
222                }
223
224                // Transfer the "from" list up to node "n" to the end of s list; the "from" list becomes the sequence after node "n".
225                // Node "n" must be in the "from" list.
[a78c3ff]226                void split( Sequence(T) & s, Sequence(T) & from, T & n ) with( s ) {
[7c1144b]227                        #ifdef __CFA_DEBUG__
[a78c3ff]228                        if ( ! listed( &n ) ) abort( "(Sequence &)%p.split( %p ) : Node is not on a list.", &s, &n );
[7c1144b]229                        #endif // __CFA_DEBUG__
[5e82d56]230                        Sequence(T) to;
231                        to.root = from.root;                                            // start of "to" list
[58870e6b]232                        from.root = Next( &n );                                         // start of "from" list
[5e82d56]233                        if ( to.root == from.root ) {                           // last node in list ?
234                                from.root = 0p;                                                 // mark "from" list empty
235                        } else {
[58870e6b]236                                Back( &head( from ) ) = Back( &head( to ) ); // fix "from" list
237                                Next( Back( &head( to ) ) ) = &head( from );
238                                Next( &n ) = &head( to );                               // fix "to" list
239                                Back( &head( to ) ) = &n;
[5e82d56]240                        } // if
241                        transfer( s, to );
242                }
243        } // distribution
244} // distribution
245
[fd54fef]246forall( T & | { T *& Back ( T * ); T *& Next ( T * ); } ) {
[8a81b09]247        // SeqIter(T) is used to iterate over a Sequence(T) in head-to-tail order.
248        struct SeqIter {
249                inline ColIter;
250                // The Sequence must be passed to pred and succ to check for the end of the Sequence and return 0p. Without
251                // passing the sequence, traversing would require its length. Thus the iterator needs a pointer to the sequence
252                // to pass to succ/pred. Both stack and queue just encounter 0p since the lists are not circular.
253                Sequence(T) * seq;                                                              // FIX ME: cannot be reference
254        };
255
256        static inline {
257                void ?{}( SeqIter(T) & si ) with( si ) {
258                        ((ColIter &)si){};
259                        seq = 0p;
[9536761]260                } // post: elts = null
[8a81b09]261
[9536761]262                // Create a iterator active in sequence s.
[8a81b09]263                void ?{}( SeqIter(T) & si, Sequence(T) & s ) with( si ) {
264                        ((ColIter &)si){};
265                        seq = &s;
266                        curr = &head( s );
[9536761]267                } // post: elts = null
[8a81b09]268
269                void ?{}( SeqIter(T) & si, Sequence(T) & s, T & start ) with( si ) {
270                        ((ColIter &)si){};
271                        seq = &s;
272                        curr = &start;
[9536761]273                } // post: elts = null
[8a81b09]274
[9536761]275                // Make the iterator active in sequence s.
[8a81b09]276                void over( SeqIter(T) & si, Sequence(T) & s ) with( si ) {
277                        seq = &s;
278                        curr = &head( s );
[9536761]279                } // post: elts = {e in s}
[8a81b09]280
[9536761]281                bool ?|?( SeqIter(T) & si, T && tp ) with( si ) {
[8a81b09]282                        if ( curr ) {
283                                &tp = Curr( si );
284                                T * n = succ( *seq, Curr( si ) );
285                                curr = n == &head( *seq ) ? 0p : n;
286                        } else &tp = 0p;
287                        return &tp != 0p;
288                }
289        } // distribution
290
291
292        // A SeqIterRev(T) is used to iterate over a Sequence(T) in tail-to-head order.
293        struct SeqIterRev {
294                inline ColIter;
295                // See above for explanation.
296                Sequence(T) * seq;                                                              // FIX ME: cannot be reference
297        };
298
299        static inline {
[ab1b971]300                void ?{}( SeqIterRev(T) & si ) with( si ) {
[8a81b09]301                        ((ColIter &)si){};
302                        seq = 0p;
[9536761]303                } // post: elts = null
[8a81b09]304
[9536761]305                // Create a iterator active in sequence s.
[ab1b971]306                void ?{}( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) {
[8a81b09]307                        ((ColIter &)si){};
308                        seq = &s;
309                        curr = &tail( s );
[9536761]310                } // post: elts = null
[8a81b09]311
[ab1b971]312                void ?{}( SeqIterRev(T) & si, Sequence(T) & s, T & start ) with( si ) {
[8a81b09]313                        ((ColIter &)si){};
314                        seq = &s;
315                        curr = &start;
[9536761]316                } // post: elts = null
[8a81b09]317
[9536761]318                // Make the iterator active in sequence s.
[8a81b09]319                void over( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) {
320                        seq = &s;
321                        curr = &tail( s );
[9536761]322                } // post: elts = {e in s}
[8a81b09]323
[9536761]324                bool ?|?( SeqIterRev(T) & si, T && tp ) with( si ) {
[8a81b09]325                        if ( curr ) {
326                                &tp = Curr( si );
327                                T * n = pred( *seq, Curr( si ) );
328                                curr = n == &tail( *seq ) ? 0p : n;
329                        } else &tp = 0p;
330                        return &tp != 0p;
331                }
332        } // distribution
333} // distribution
[e43aa14]334
[a3a76ea]335#endif
Note: See TracBrowser for help on using the repository browser.