source: libcfa/src/bits/queue.hfa @ c407434e

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since c407434e was c407434e, checked in by Thierry Delisle <tdelisle@…>, 3 years ago

Fixed missing static

  • Property mode set to 100644
File size: 5.5 KB
RevLine 
[5e82d56]1#pragma once
2
[7d4ce2a]3#include "bits/collection.hfa"
[5e82d56]4
[9536761]5// A Queue(T) is a Collection(T) defining the ordering that nodes are returned by drop() in the same order from those
6// added by add(). T must be a public descendant of uColable.
7
8// The implementation is a typical singly-linked list, except the next field of the last element points to itself
9// instead of being null.
10
[fd54fef]11forall( T & | { T *& Next ( T * ); } ) {
[5e82d56]12        struct Queue {
13                inline Collection;                                                              // Plan 9 inheritance
14                T * last;                                                                               // last element, or 0 if queue is empty.
15        };
16
[c407434e]17        static inline {
[5e82d56]18                // wrappers to make Collection have T
[a78c3ff]19                T & head( Queue(T) & q ) with( q ) {
20                        return *(T *)head( (Collection &)q );
[5e82d56]21                } // post: empty() & head() == 0 | !empty() & head() in *q
22
23                void ?{}( Queue(T) &, const Queue(T) & ) = void; // no copy
24                Queue(T) & ?=?( const Queue(T) & ) = void;              // no assignment
25
26                void ?{}( Queue(T) & q ) with( q ) {
27                        ((Collection &)q){};
28                        last = 0p;
29                } // post: empty()
30
[a78c3ff]31                T & tail( Queue(T) & q ) with( q ) {
32                        return *last;
[5e82d56]33                }
34
[a5a67ab8]35                T * succ( Queue(T) & q, T * n ) with( q ) {             // pre: *n in *q
[7c1144b]36                        #ifdef __CFA_DEBUG__
[a5a67ab8]37                        if ( ! listed( n ) ) abort( "(Queue &)%p.succ( %p ) : Node is not on a list.", &q, n );
[7c1144b]38                        #endif // __CFA_DEBUG__
[58870e6b]39                        return (Next( n ) == n) ? 0p : Next( n );
[5e82d56]40                } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *q
41
[a3a76ea]42                T & addHead( Queue(T) & q, T & n ) with( q ) {
[7c1144b]43                        #ifdef __CFA_DEBUG__
[a78c3ff]44                        if ( listed( &n ) ) abort( "(Queue &)%p.addHead( %p ) : Node is already on another list.", &q, &n );
[7c1144b]45                        #endif // __CFA_DEBUG__
[5e82d56]46                        if ( last ) {
[58870e6b]47                                Next( &n ) = &head( q );
[a78c3ff]48                                q.root = &n;
[5e82d56]49                        } else {
[a78c3ff]50                                root = last = &n;
[58870e6b]51                                Next( &n ) = &n;                                                // last node points to itself
[5e82d56]52                        }
[a3a76ea]53                        return n;
[5e82d56]54                }
55
[a3a76ea]56                T & addTail( Queue(T) & q, T & n ) with( q ) {
[7c1144b]57                        #ifdef __CFA_DEBUG__
[a78c3ff]58                        if ( listed( &n ) ) abort( "(Queue &)%p.addTail( %p ) : Node is already on another list.", &q, &n );
[7c1144b]59                        #endif // __CFA_DEBUG__
[58870e6b]60                        if ( last ) Next( last ) = &n;
[a78c3ff]61                        else root = &n;
62                        last = &n;
[58870e6b]63                        Next( &n ) = &n;                                                        // last node points to itself
[a3a76ea]64                        return n;
[5e82d56]65                }
66
[a3a76ea]67                T & add( Queue(T) & q, T & n ) with( q ) {
68                        return addTail( q, n );
[5e82d56]69                }
70
[a78c3ff]71                T & dropHead( Queue(T) & q ) with( q ) {
[a5a67ab8]72                        T & t = head( q );
[5e82d56]73                        if ( root ) {
[accc5dbb]74                                root = Next( (T *)root );
[a5a67ab8]75                                if ( &head( q ) == &t ) {
[5e82d56]76                                        root = last = 0p;                                       // only one element
77                                }
[58870e6b]78                                Next( &t ) = 0p;
[5e82d56]79                        }
[a5a67ab8]80                        return t;
[5e82d56]81                }
82
[a78c3ff]83                T & drop( Queue(T) & q ) with( q ) {
[5e82d56]84                        return dropHead( q );
85                }
86
[a3a76ea]87                T & remove( Queue(T) & q, T & n ) with( q ) {   // O(n)
[7c1144b]88                        #ifdef __CFA_DEBUG__
[a78c3ff]89                        if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.remove( %p ) : Node is not on a list.", &q, &n );
[7c1144b]90                        #endif // __CFA_DEBUG__
[58870e6b]91                        T * prev = 0p;
92                        T * curr = (T *)root;
[5e82d56]93                        for ( ;; ) {
[58870e6b]94                                if ( &n == curr ) {                                             // found => remove
[a5a67ab8]95                                        if ( (T *)root == &n ) {
[5e82d56]96                                                dropHead( q );
[a5a67ab8]97                                        } else if ( last == &n ) {
[58870e6b]98                                                last = prev;
99                                                Next( last ) = last;
[5e82d56]100                                        } else {
101                                                Next( prev ) = Next( curr );
102                                        }
[58870e6b]103                                        Next( &n ) = 0p;
[5e82d56]104                                        break;
105                                }
106                                // not found => error
[7c1144b]107                                #ifdef __CFA_DEBUG__
[58870e6b]108                                if ( curr == last ) abort( "(Queue &)%p.remove( %p ) : Node is not in list.", &q, &n );
[7c1144b]109                                #endif // __CFA_DEBUG__
[58870e6b]110                                prev = curr;
111                                curr = Next( curr );
[5e82d56]112                        }
[a3a76ea]113                        return n;
[5e82d56]114                } // post: ! listed( n )
115
[9536761]116                T & dropTail( Queue(T) & q ) with( q ) {                // O(n)
[a78c3ff]117                        T & n = tail( q );
118                        return &n ? remove( q, n ), n : *0p;
[5e82d56]119                }
120
121                // Transfer the "from" list to the end of queue sequence; the "from" list is empty after the transfer.
122                void transfer( Queue(T) & q, Queue(T) & from ) with( q ) {
123                        if ( empty( from ) ) return;                            // "from" list empty ?
124                        if ( empty( q ) ) {                                                     // "to" list empty ?
125                                root = from.root;
126                        } else {                                                                        // "to" list not empty
[58870e6b]127                                Next( last ) = &head( from );
[5e82d56]128                        }
129                        last = from.last;
130                        from.root = from.last = 0p;                                     // mark "from" list empty
131                }
132
133                // Transfer the "from" list up to node "n" to the end of queue list; the "from" list becomes the list after node "n".
134                // Node "n" must be in the "from" list.
[a78c3ff]135                void split( Queue(T) & q, Queue(T) & from, T & n ) with( q ) {
[7c1144b]136                        #ifdef __CFA_DEBUG__
[a78c3ff]137                        if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.split( %p ) : Node is not on a list.", &q, &n );
[7c1144b]138                        #endif // __CFA_DEBUG__
[5e82d56]139                        Queue(T) to;
140                        to.root = from.root;                                            // start of "to" list
[a78c3ff]141                        to.last = &n;                                                           // end of "to" list
[58870e6b]142                        from.root = Next( &n );                                         // start of "from" list
[a5a67ab8]143                        if ( &n == &head( from ) ) {                            // last node in list ?
[5e82d56]144                                from.root = from.last = 0p;                             // mark "from" list empty
145                        } else {
[58870e6b]146                                Next( &n ) = &n;                                                // fix end of "to" list
[5e82d56]147                        }
148                        transfer( q, to );
149                }
150        } // distribution
151} // distribution
152
[fd54fef]153forall( T & | { T *& Next ( T * ); } ) {
[5e82d56]154        struct QueueIter {
155                inline ColIter;                                                                 // Plan 9 inheritance
[c407434e]156        };
[5e82d56]157
[c407434e]158        static inline {
[5e82d56]159                void ?{}( QueueIter(T) & qi ) with( qi ) {
160                        ((ColIter &)qi){};
161                } // post: curr == 0p
162
[9536761]163                // create an iterator active in queue q
[5e82d56]164                void ?{}( QueueIter(T) & qi, Queue(T) & q ) with( qi ) {
[a78c3ff]165                        curr = &head( q );
[5e82d56]166                } // post: curr = {e in q}
167
[a78c3ff]168                void ?{}( QueueIter(T) & qi, T & start ) with( qi ) {
169                        curr = &start;
[5e82d56]170                } // post: curr = {e in q}
171
[9536761]172                // make existing iterator active in queue q
[5e82d56]173                void over( QueueIter(T) & qi, Queue(T) & q ) with( qi ) {
[a78c3ff]174                        curr = &head( q );
[5e82d56]175                } // post: curr = {e in q}
176
[9536761]177                bool ?|?( QueueIter(T) & qi, T && tp ) with( qi ) {
[5e82d56]178                        if ( curr ) {
[3d0560d]179                                &tp = Curr( qi );
[58870e6b]180                                T * n = Next( Curr( qi ) );
[5e82d56]181                                curr = (n == Curr( qi ) ) ? 0p : n;
[3d0560d]182                        } else &tp = 0p;
183                        return &tp != 0p;
[5e82d56]184                }
[9536761]185                // post: elts == null & !operator|(tp) | elts != null & *tp' in elts & elts' == elts - *tp & operator|(tp)
[5e82d56]186        } // distribution
187} // distribution
Note: See TracBrowser for help on using the repository browser.