Changeset a78c3ff


Ignore:
Timestamp:
Dec 3, 2020, 3:32:44 PM (10 months ago)
Author:
Colby Alexander Parsons <caparsons@…>
Branches:
arm-eh, jacob/cs343-translation, master, new-ast-unique-expr
Children:
aeb31b1
Parents:
636d3715
Message:

switched queue and sequence to use references

Location:
libcfa/src/bits
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • libcfa/src/bits/queue.hfa

    r636d3715 ra78c3ff  
    1111        inline {
    1212                // wrappers to make Collection have T
    13                 T * head( Queue(T) & q ) with( q ) {
    14                         return (T *)head( (Collection &)q );
     13                T & head( Queue(T) & q ) with( q ) {
     14                        return *(T *)head( (Collection &)q );
    1515                } // post: empty() & head() == 0 | !empty() & head() in *q
    1616
     
    2323                } // post: empty()
    2424
    25                 T * tail( Queue(T) & q ) with( q ) {
    26                         return last;
     25                T & tail( Queue(T) & q ) with( q ) {
     26                        return *last;
    2727                }
    2828
    29                 T * succ( Queue(T) & q, T * n ) with( q ) {             // pre: *n in *q
     29                T & succ( Queue(T) & q, T & n ) with( q ) {             // pre: *n in *q
    3030#ifdef __CFA_DEBUG__
    31                         if ( ! listed( n ) ) abort( "(Queue &)%p.succ( %p ) : Node is not on a list.", &q, n );
     31                        if ( ! listed( &n ) ) abort( "(Queue &)%p.succ( %p ) : Node is not on a list.", &q, &n );
    3232#endif // __CFA_DEBUG__
    33                         return (Next( n ) == n) ? 0p : Next( n );
     33                        return (Next( &n ) == &n) ? *0p : *Next( &n );
    3434                } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *q
    3535
    36                 void addHead( Queue(T) & q, T * n ) with( q ) {
     36                void addHead( Queue(T) & q, T & n ) with( q ) {
    3737#ifdef __CFA_DEBUG__
    38                         if ( listed( n ) ) abort( "(Queue &)%p.addHead( %p ) : Node is already on another list.", &q, n );
     38                        if ( listed( &n ) ) abort( "(Queue &)%p.addHead( %p ) : Node is already on another list.", &q, &n );
    3939#endif // __CFA_DEBUG__
    4040                        if ( last ) {
    41                                 Next( n ) = head( q );
    42                                 q.root = n;
     41                                Next( &n ) = &head( q );
     42                                q.root = &n;
    4343                        } else {
    44                                 root = last = n;
    45                                 Next( n ) = n;                                                  // last node points to itself
     44                                root = last = &n;
     45                                Next( &n ) = &n;                                                        // last node points to itself
    4646                        }
    4747                }
    4848
    49                 void addTail( Queue(T) & q, T * n ) with( q ) {
     49                void addTail( Queue(T) & q, T & n ) with( q ) {
    5050#ifdef __CFA_DEBUG__
    51                         if ( listed( n ) ) abort( "(Queue &)%p.addTail( %p ) : Node is already on another list.", &q, n );
     51                        if ( listed( &n ) ) abort( "(Queue &)%p.addTail( %p ) : Node is already on another list.", &q, &n );
    5252#endif // __CFA_DEBUG__
    53                         if ( last ) Next( last ) = n;
    54                         else root = n;
    55                         last = n;
    56                         Next( n ) = n;                                                          // last node points to itself
     53                        if ( last ) Next( last ) = &n;
     54                        else root = &n;
     55                        last = &n;
     56                        Next( &n ) = &n;                                                                // last node points to itself
    5757                }
    5858
    59                 void add( Queue(T) & q, T * n ) with( q ) {
     59                void add( Queue(T) & q, T & n ) with( q ) {
    6060                        addTail( q, n );
    6161                }
    6262
    63                 T * dropHead( Queue(T) & q ) with( q ) {
    64                         T * t = head( q );
     63                T & dropHead( Queue(T) & q ) with( q ) {
     64                        T * t = &head( q );
    6565                        if ( root ) {
    6666                                root = Next( root );
    67                                 if ( head( q ) == t ) {
     67                                if ( &head( q ) == t ) {
    6868                                        root = last = 0p;                                       // only one element
    6969                                }
    7070                                Next( t ) = 0p;
    7171                        }
    72                         return t;
     72                        return *t;
    7373                }
    7474
    75                 T * drop( Queue(T) & q ) with( q ) {
     75                T & drop( Queue(T) & q ) with( q ) {
    7676                        return dropHead( q );
    7777                }
    7878
    79                 void remove( Queue(T) & q, T * n ) with( q ) {  // O(n)
     79                void remove( Queue(T) & q, T & n ) with( q ) {  // O(n)
    8080#ifdef __CFA_DEBUG__
    81                         if ( ! listed( (Colable &)(*n) ) ) abort( "(Queue &)%p.remove( %p ) : Node is not on a list.", &q, n );
     81                        if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.remove( %p ) : Node is not on a list.", &q, &n );
    8282#endif // __CFA_DEBUG__
    8383                        T * prev = 0;
    8484                        T * curr = (T *)root;
    8585                        for ( ;; ) {
    86                                 if (n == curr) {                                                // found => remove
    87                                         if ((T *)root == n) {
     86                                if (&n == curr) {                                               // found => remove
     87                                        if ((T *)root == &n) {
    8888                                                dropHead( q );
    89                                         } else if (last == n) {
     89                                        } else if (last == &n) {
    9090                                                last = prev;
    9191                                                Next( last ) = last;
     
    9393                                                Next( prev ) = Next( curr );
    9494                                        }
    95                                         Next( n ) = 0p;
     95                                        Next( &n ) = 0p;
    9696                                        break;
    9797                                }
    9898#ifdef __CFA_DEBUG__
    9999                                // not found => error
    100                                 if (curr == last) abort( "(Queue &)%p.remove( %p ) : Node is not in list.", &q, n );
     100                                if (curr == last) abort( "(Queue &)%p.remove( %p ) : Node is not in list.", &q, &n );
    101101#endif // __CFA_DEBUG__
    102102                                prev = curr;
     
    105105                } // post: ! listed( n )
    106106
    107                 T * dropTail( Queue(T) & q ) with( q ) { // O(n)
    108                         T * n = tail( q );
    109                         return n ? remove( q, n ), n : 0p;
     107                T & dropTail( Queue(T) & q ) with( q ) { // O(n)
     108                        T & n = tail( q );
     109                        return &n ? remove( q, n ), n : *0p;
    110110                }
    111111
     
    116116                                root = from.root;
    117117                        } else {                                                                        // "to" list not empty
    118                                 Next( last ) = head( from );
     118                                Next( last ) = &head( from );
    119119                        }
    120120                        last = from.last;
     
    124124                // Transfer the "from" list up to node "n" to the end of queue list; the "from" list becomes the list after node "n".
    125125                // Node "n" must be in the "from" list.
    126                 void split( Queue(T) & q, Queue(T) & from, T * n ) with( q ) {
     126                void split( Queue(T) & q, Queue(T) & from, T & n ) with( q ) {
    127127#ifdef __CFA_DEBUG__
    128                         if ( ! listed( (Colable &)(*n) ) ) abort( "(Queue &)%p.split( %p ) : Node is not on a list.", &q, n );
     128                        if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.split( %p ) : Node is not on a list.", &q, &n );
    129129#endif // __CFA_DEBUG__
    130130                        Queue(T) to;
    131131                        to.root = from.root;                                            // start of "to" list
    132                         to.last = n;                                                            // end of "to" list
    133                         from.root = Next( n );                                          // start of "from" list
    134                         if ( n == head( from ) ) {                                      // last node in list ?
     132                        to.last = &n;                                                           // end of "to" list
     133                        from.root = Next( &n );                                         // start of "from" list
     134                        if ( &n == &head( from ) ) {                                    // last node in list ?
    135135                                from.root = from.last = 0p;                             // mark "from" list empty
    136136                        } else {
    137                                 Next( n ) = n;                                                  // fix end of "to" list
     137                                Next( &n ) = &n;                                                        // fix end of "to" list
    138138                        }
    139139                        transfer( q, to );
     
    154154                // create an iterator active in Queue q
    155155                void ?{}( QueueIter(T) & qi, Queue(T) & q ) with( qi ) {
    156                         curr = head( q );
     156                        curr = &head( q );
    157157                } // post: curr = {e in q}
    158158
    159                 void ?{}( QueueIter(T) & qi, T * start ) with( qi ) {
    160                         curr = start;
     159                void ?{}( QueueIter(T) & qi, T & start ) with( qi ) {
     160                        curr = &start;
    161161                } // post: curr = {e in q}
    162162
    163163                // make existing iterator active in Queue q
    164164                void over( QueueIter(T) & qi, Queue(T) & q ) with( qi ) {
    165                         curr = head( q );
     165                        curr = &head( q );
    166166                } // post: curr = {e in q}
    167167
  • libcfa/src/bits/queue_example.cfa

    r636d3715 ra78c3ff  
    2727       
    2828        for ( i; 10 ) {
    29                 add( fred, new( 2 * i ) );
     29                add( fred, *new( 2 * i ) );
    3030        }
    3131
     
    3636
    3737        for ( i; 9 ) {
    38                 delete( drop( fred ) );
     38                delete( &drop( fred ) );
    3939        }
    4040
     
    4545       
    4646        for ( i; 10 ) {
    47                 add( fred, new( 2 * i + 1 ) );
     47                add( fred, *new( 2 * i + 1 ) );
    4848        }
    4949        for ( over( fredIter, fred ); fredIter >> f; ) {
     
    7878       
    7979        for ( i; 10 ) {
    80                 add( mary, new( 2 * i ) );
     80                add( mary, *new( 2 * i ) );
    8181        }
    8282
     
    8787       
    8888        for ( i; 9 ) {
    89                 delete( drop( mary ) );
     89                delete( &drop( mary ) );
    9090        }
    9191
     
    9696       
    9797        for ( i; 10 ) {
    98                 add( mary, new( 2 * i + 1 ) );
     98                add( mary, *new( 2 * i + 1 ) );
    9999        }
    100100        for ( over( maryIter, mary ); maryIter >> m; ) {
  • libcfa/src/bits/sequence.hfa

    r636d3715 ra78c3ff  
    22
    33#include "collection.hfa"
     4#include <stdlib.hfa>
     5#include <stdio.h>
    46
    57struct Seqable {
     
    1416        } // post: ! listed()
    1517
    16         Seqable * getBack( Seqable & sq ) with( sq ) {
    17                 return back;
     18        Seqable & getBack( Seqable & sq ) with( sq ) {
     19                return *back;
    1820        }
    1921
     
    3032        inline {
    3133                // wrappers to make Collection have T
    32                 T * head( Sequence(T) & s ) with( s ) {
    33                         return (T *)head( (Collection &)s );
     34                T & head( Sequence(T) & s ) with( s ) {
     35                        return *(T *)head( (Collection &)s );
    3436                } // post: empty() & head() == 0 | !empty() & head() in *s
    3537
     
    4749                // Return a pointer to the last sequence element, without removing it. 
    4850                T & tail( Sequence(T) & s ) with( s ) {
    49                         return root ? (T &)Back( head( s ) ) : *0p;     // needs cast?
    50                 }       // post: empty() & tail() == 0 | !empty() & tail() in *s
     51                        return root ? (T &)*Back( &head( s ) ) : *0p;
     52                }       // post: empty() & tail() == 0 | !empty() & tail() in *s\
    5153
    5254                // Return a pointer to the element after *n, or 0p if there isn't one.
    53                 T * succ( Sequence(T) & s, T * n ) with( s ) {  // pre: *n in *s
    54 #ifdef __CFA_DEBUG__
    55                         if ( ! listed( n ) ) abort( "(Sequence &)%p.succ( %p ) : Node is not on a list.", &s, n );
    56 #endif // __CFA_DEBUG__
    57                         return Next( n ) == head( s ) ? 0p : Next( n );
     55                T & succ( Sequence(T) & s, T & n ) with( s ) {  // pre: *n in *s
     56#ifdef __CFA_DEBUG__
     57                        if ( ! listed( &n ) ) abort( "(Sequence &)%p.succ( %p ) : Node is not on a list.", &s, &n );
     58#endif // __CFA_DEBUG__
     59                        return Next( &n ) == &head( s ) ? *0p : *Next( &n );
    5860                }       // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *s
    5961
    6062                // Return a pointer to the element before *n, or 0p if there isn't one.
    61                 T * pred( Sequence(T) & s, T * n ) with( s ) {  // pre: *n in *s
    62 #ifdef __CFA_DEBUG__
    63                         if ( ! listed( n ) ) abort( "(Sequence &)%p.pred( %p ) : Node is not on a list.", &s, n );
    64 #endif // __CFA_DEBUG__
    65                         return n == head( s ) ? 0p : Back( n );
     63                T & pred( Sequence(T) & s, T & n ) with( s ) {  // pre: *n in *s
     64#ifdef __CFA_DEBUG__
     65                        if ( ! listed( &n ) ) abort( "(Sequence &)%p.pred( %p ) : Node is not on a list.", &s, &n );
     66#endif // __CFA_DEBUG__
     67                        return &n == &head( s ) ? *0p : *Back( &n );
    6668                }       // post: n == head() & head(n) == 0 | n != head() & *pred(n) in *s
    6769
     
    7274                        if ( listed( &n ) ) abort( "(Sequence &)%p.insertBef( %p, %p ) : Node is already on another list.", &s, n, &bef );
    7375#endif // __CFA_DEBUG__
    74                         if ( &bef == head( s ) ) {                                      // must change root
     76                        if ( &bef == &head( s ) ) {                                     // must change root
    7577                                if ( root ) {
    76                                         Next( &n ) = head( s );
    77                                         Back( &n ) = Back( head( s ) );
     78                                        Next( &n ) = &head( s );
     79                                        Back( &n ) = Back( &head( s ) );
    7880                                        // inserted node must be consistent before it is seen
    7981                                        asm( "" : : : "memory" );                       // prevent code movement across barrier
    80                                         Back( head( s ) ) = &n;
     82                                        Back( &head( s ) ) = &n;
    8183                                        Next( Back( &n ) ) = &n;
    8284                                } else {
     
    8890                                root = &n;
    8991                        } else {
    90                                 if ( ! &bef ) &bef = head( s );
     92                                if ( ! &bef ) &bef = &head( s );
    9193                                Next( &n ) = &bef;
    9294                                Back( &n ) = Back( &bef );
     
    106108                        if ( ! &aft ) {                                                         // must change root
    107109                                if ( root ) {
    108                                         Next( &n ) = head( s );
    109                                         Back( &n ) = Back( head( s ) );
     110                                        Next( &n ) = &head( s );
     111                                        Back( &n ) = Back( &head( s ) );
    110112                                        // inserted node must be consistent before it is seen
    111113                                        asm( "" : : : "memory" );                       // prevent code movement across barrier
    112                                         Back( head( s ) ) = &n;
     114                                        Back( &head( s ) ) = &n;
    113115                                        Next( Back( &n ) ) = &n;
    114116                                } else {
     
    133135                        if ( ! listed( &n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s, &n );
    134136#endif // __CFA_DEBUG__
    135                         if ( &n == head( s ) ) {
    136                                 if ( Next( head( s ) ) == head( s ) ) root = 0p;
    137                                 else root = Next( head(s ) );
     137                        if ( &n == &head( s ) ) {
     138                                if ( Next( &head( s ) ) == &head( s ) ) root = 0p;
     139                                else root = Next( &head(s ) );
    138140                        } // if
    139141                        Back( Next( &n ) ) = Back( &n );
     
    156158                // Remove and return the head element in the sequence.
    157159                T & dropHead( Sequence(T) & s ) {
    158                         T * n = head( s );
    159                         return n ? remove( s, *n ), *n : *0p;
     160                        T & n = head( s );
     161                        return &n ? remove( s, n ), n : *0p;
    160162                }
    161163                // Remove and return the head element in the sequence.
     
    175177                                root = from.root;
    176178                        } else {                                                                        // "to" list not empty
    177                                 T * toEnd = Back( head( s ) );
    178                                 T * fromEnd = Back( head( from ) );
     179                                T * toEnd = Back( &head( s ) );
     180                                T * fromEnd = Back( &head( from ) );
    179181                                Back( root ) = fromEnd;
    180                                 Next( fromEnd ) = head( s );
     182                                Next( fromEnd ) = &head( s );
    181183                                Back( from.root ) = toEnd;
    182                                 Next( toEnd ) = head( from );
     184                                Next( toEnd ) = &head( from );
    183185                        } // if
    184186                        from.root = 0p;                                                         // mark "from" list empty
     
    187189                // Transfer the "from" list up to node "n" to the end of s list; the "from" list becomes the sequence after node "n".
    188190                // Node "n" must be in the "from" list.
    189                 void split( Sequence(T) & s, Sequence(T) & from, T * n ) with( s ) {
    190 #ifdef __CFA_DEBUG__
    191                         if ( ! listed( n ) ) abort( "(Sequence &)%p.split( %p ) : Node is not on a list.", &s, n );
     191                void split( Sequence(T) & s, Sequence(T) & from, T & n ) with( s ) {
     192#ifdef __CFA_DEBUG__
     193                        if ( ! listed( &n ) ) abort( "(Sequence &)%p.split( %p ) : Node is not on a list.", &s, &n );
    192194#endif // __CFA_DEBUG__
    193195                        Sequence(T) to;
    194196                        to.root = from.root;                                            // start of "to" list
    195                         from.root = Next( n );                                          // start of "from" list
     197                        from.root = Next( &n );                                         // start of "from" list
    196198                        if ( to.root == from.root ) {                           // last node in list ?
    197199                                from.root = 0p;                                                 // mark "from" list empty
    198200                        } else {
    199                                 Back( head( from ) ) = Back( head( to ) ); // fix "from" list
    200                                 Next( Back( head( to ) ) ) = head( from );
    201                                 Next( n ) = head( to );                                 // fix "to" list
    202                                 Back( head( to ) ) = n;
     201                                Back( &head( from ) ) = Back( &head( to ) ); // fix "from" list
     202                                Next( Back( &head( to ) ) ) = &head( from );
     203                                Next( &n ) = &head( to );                                       // fix "to" list
     204                                Back( &head( to ) ) = &n;
    203205                        } // if
    204206                        transfer( s, to );
     
    223225                        ((ColIter &) si){};
    224226                        seq = &s;
    225                         curr = head( s );
     227                        curr = &head( s );
    226228                } // post: elts = null.
    227229               
    228230                void over( SeqIter(T) & si, Sequence(T) & s ) with( si ) {
    229231                        seq = &s;
    230                         curr = head( s );
     232                        curr = &head( s );
    231233                } // post: elts = {e in s}.
    232234
     
    234236                        if ( curr ) {
    235237                                &tp = Curr( si );
    236                                 T * n = succ( *seq, Curr( si ) );
    237                                 curr = n == head( *seq ) ? 0p : n;
     238                                T * n = &succ( *seq, *Curr( si ) );
     239                                curr = n == &head( *seq ) ? 0p : n;
    238240                        } else &tp = 0p;
    239241                        return &tp != 0p;
     
    268270                        if ( curr ) {
    269271                                &tp = Curr( si );
    270                                 T * n = pred( *seq, Curr( si ) );
     272                                T * n = &pred( *seq, *Curr( si ) );
    271273                                curr = n == &tail( *seq ) ? 0p : n;
    272274                        } else &tp = 0p;
Note: See TracChangeset for help on using the changeset viewer.