Changeset 2b4daf2 for libcfa/src/bits/sequence.hfa

Timestamp:

Jan 7, 2021, 5:06:22 PM (5 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

5ad381b

Parents:

42f6e07 (diff), 58fe85a (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:

• libcfa/src/bits/sequence.hfa (modified) (16 diffs)

libcfa/src/bits/sequence.hfa

@@ -2 +2 @@
 
 #include "bits/collection.hfa"
+#include "bits/defs.hfa"
 
 struct Seqable {
-        inline Colable;
-        Seqable * back;                                                                         // pointer to previous node in the list
+        __cfa_anonymous_object(Colable);
+        struct Seqable * back;                                                                          // pointer to previous node in the list
 };
 
-inline {
+#ifdef __cforall
+static inline {
         // PUBLIC
 
@@ -26 +28 @@
         }
 
-        // wrappers to make Collection have T
-        forall( dtype T ) {
-                T *& Back( T * n ) {
-                        return (T *)Back( (Seqable *)n );
-                }
-        } // distribution
+        // // wrappers to make Collection have T
+        // forall( dtype T ) {
+        //      T *& Back( T * n ) {
+        //              return (T *)Back( (Seqable *)n );
+        //      }
+        // } // distribution
 } // distribution
 
-forall( dtype T ) {
+
+// A Sequence(T) is a Collection(T) defining the ordering of a uStack and uQueue, and to insert and remove elements
+// anywhere in the sequence. T must be a public descendant of uSeqable.
+
+// The implementation is a typical doubly-linked list, except the next field of the last node points at the first node
+// and the back field of the last node points at the first node (circular).
+
+forall( dtype T | { T *& Back ( T * ); T *& Next ( T * ); } ) {
         struct Sequence {
                 inline Collection;                                                              // Plan 9 inheritance
         };
 
-        inline {
+        static inline {
                 // wrappers to make Collection have T
                 T & head( Sequence(T) & s ) with( s ) {
@@ -50 +59 @@
                 void ?{}( Sequence(T) & s ) with( s ) { 
                         ((Collection &)s){};
-                }       // post: isEmpty().
-
-                // Return a pointer to the last sequence element, without removing it.  
+                }       // post: isEmpty()
+
+                // Return a pointer to the last sequence element, without removing it.
                 T & tail( Sequence(T) & s ) with( s ) {
                         return root ? (T &)*Back( &head( s ) ) : *0p;
@@ -65 +74 @@
                 } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *s
 
-                // Return a pointer to the element before *n, or 0p if there isn't one.
+                // Return a pointer to the element before *n, or 0p if list empty.
                 T * pred( Sequence(T) & s, T * n ) with( s ) {  // pre: *n in *s
                         #ifdef __CFA_DEBUG__
@@ -71 +80 @@
                         #endif // __CFA_DEBUG__
                         return n == &head( s ) ? 0p : Back( n );
-                }       // post: n == head() & head(n) == 0 | n != head() & *pred(n) in *s
-
-
-                // Insert *n into the sequence before *bef, or at the end if bef == 0.
-                void insertBef( Sequence(T) & s, T & n, T & bef ) with( s ) { // pre: !n->listed() & *bef in *s
+                } // post: n == head() & head(n) == 0 | n != head() & *pred(n) in *s
+
+
+                // Insert *n into the sequence before *bef, or at the end if bef == 0p.
+                T & insertBef( Sequence(T) & s, T & n, T & bef ) with( s ) { // pre: !n->listed() & *bef in *s
                         #ifdef __CFA_DEBUG__
                         if ( listed( &n ) ) abort( "(Sequence &)%p.insertBef( %p, %p ) : Node is already on another list.", &s, n, &bef );
@@ -103 +112 @@
                                 Next( Back( &n ) ) = &n;
                         } // if
+                        return n;
                 }       // post: n->listed() & *n in *s & succ(n) == bef
 
 
                 // Insert *n into the sequence after *aft, or at the beginning if aft == 0.
-                void insertAft( Sequence(T) & s, T & aft, T & n ) with( s ) {   // pre: !n->listed() & *aft in *s
+                T & insertAft( Sequence(T) & s, T & aft, T & n ) with( s ) {    // pre: !n->listed() & *aft in *s
                         #ifdef __CFA_DEBUG__
                         if ( listed( &n ) ) abort( "(Sequence &)%p.insertAft( %p, %p ) : Node is already on another list.", &s, &aft, &n );
@@ -133 +143 @@
                                 Next( &aft ) = &n;
                         } // if
-                }         // post: n->listed() & *n in *s & succ(n) == bef
+                        return n;
+                } // post: n->listed() & *n in *s & succ(n) == bef
                 
                 // pre: n->listed() & *n in *s
-                void remove( Sequence(T) & s, T & n ) with( s ) { // O(1)
+                T & remove( Sequence(T) & s, T & n ) with( s ) { // O(1)
                         #ifdef __CFA_DEBUG__
                         if ( ! listed( &n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s, &n );
@@ -147 +158 @@
                         Next( Back( &n ) ) = Next( &n );
                         Next( &n ) = Back( &n ) = 0p;
-                }                                                       // post: !n->listed().
+                        return n;
+                } // post: !n->listed()
 
                 // Add an element to the head of the sequence.
-                void addHead( Sequence(T) & s, T & n ) {                // pre: !n->listed(); post: n->listed() & head() == n
-                        insertAft( s, *0p, n );
-                }
+                T & addHead( Sequence(T) & s, T & n ) {                 // pre: !n->listed(); post: n->listed() & head() == n
+                        return insertAft( s, *0p, n );
+                }
+
                 // Add an element to the tail of the sequence.
-                void addTail( Sequence(T) & s, T & n ) {                // pre: !n->listed(); post: n->listed() & head() == n
-                        insertBef( s, n, *0p );
-                }
+                T & addTail( Sequence(T) & s, T & n ) {                 // pre: !n->listed(); post: n->listed() & head() == n
+                        return insertBef( s, n, *0p );
+                }
+
                 // Add an element to the tail of the sequence.
-                void add( Sequence(T) & s, T & n ) {                    // pre: !n->listed(); post: n->listed() & head() == n
-                        addTail( s, n );
-                }
+                T & add( Sequence(T) & s, T & n ) {                             // pre: !n->listed(); post: n->listed() & head() == n
+                        return addTail( s, n );
+                }
+
                 // Remove and return the head element in the sequence.
                 T & dropHead( Sequence(T) & s ) {
@@ -166 +181 @@
                         return &n ? remove( s, n ), n : *0p;
                 }
+
                 // Remove and return the head element in the sequence.
                 T & drop( Sequence(T) & s ) {
                         return dropHead( s );
                 }
+
                 // Remove and return the tail element in the sequence.
                 T & dropTail( Sequence(T) & s ) {
@@ -184 +201 @@
                                 T * toEnd = Back( &head( s ) );
                                 T * fromEnd = Back( &head( from ) );
-                                Back( root ) = fromEnd;
+                                Back( (T *)root ) = fromEnd;
                                 Next( fromEnd ) = &head( s );
-                                Back( from.root ) = toEnd;
+                                Back( (T *)from.root ) = toEnd;
                                 Next( toEnd ) = &head( from );
                         } // if
@@ -214 +231 @@
 } // distribution
 
-forall( dtype T ) {
+forall( dtype T | { T *& Back ( T * ); T *& Next ( T * ); } ) {
         // SeqIter(T) is used to iterate over a Sequence(T) in head-to-tail order.
         struct SeqIter {
@@ -224 +241 @@
         };
 
-        inline {
+        static inline {
                 void ?{}( SeqIter(T) & si ) with( si ) {
                         ((ColIter &)si){};
                         seq = 0p;
-                } // post: elts = null.
-
+                } // post: elts = null
+
+                // Create a iterator active in sequence s.
                 void ?{}( SeqIter(T) & si, Sequence(T) & s ) with( si ) {
                         ((ColIter &)si){};
                         seq = &s;
                         curr = &head( s );
-                } // post: elts = null.
+                } // post: elts = null
 
                 void ?{}( SeqIter(T) & si, Sequence(T) & s, T & start ) with( si ) {
@@ -240 +258 @@
                         seq = &s;
                         curr = &start;
-                } // post: elts = null.
-
+                } // post: elts = null
+
+                // Make the iterator active in sequence s.
                 void over( SeqIter(T) & si, Sequence(T) & s ) with( si ) {
                         seq = &s;
                         curr = &head( s );
-                } // post: elts = {e in s}.
-
-                bool ?>>?( SeqIter(T) & si, T && tp ) with( si ) {
+                } // post: elts = {e in s}
+
+                bool ?|?( SeqIter(T) & si, T && tp ) with( si ) {
                         if ( curr ) {
                                 &tp = Curr( si );
@@ -265 +284 @@
         };
 
-        inline {
+        static inline {
                 void ?{}( SeqIterRev(T) & si ) with( si ) {     
                         ((ColIter &)si){};
                         seq = 0p;
-                } // post: elts = null.
-
+                } // post: elts = null
+
+                // Create a iterator active in sequence s.
                 void ?{}( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) {    
                         ((ColIter &)si){};
                         seq = &s;
                         curr = &tail( s );
-                } // post: elts = null.
+                } // post: elts = null
 
                 void ?{}( SeqIterRev(T) & si, Sequence(T) & s, T & start ) with( si ) { 
@@ -281 +301 @@
                         seq = &s;
                         curr = &start;
-                } // post: elts = null.
-
+                } // post: elts = null
+
+                // Make the iterator active in sequence s.
                 void over( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) {
                         seq = &s;
                         curr = &tail( s );
-                } // post: elts = {e in s}.
-
-                bool ?>>?( SeqIterRev(T) & si, T && tp ) with( si ) {
+                } // post: elts = {e in s}
+
+                bool ?|?( SeqIterRev(T) & si, T && tp ) with( si ) {
                         if ( curr ) {
                                 &tp = Curr( si );
@@ -298 +319 @@
         } // distribution
 } // distribution
+
+#endif