FixedLengthList.hpp

00001 /**
00002    @file
00003    @brief Template class ( FixedLengthList ) to implement a list with
00004           a limited number of elements.
00005 
00006    @author John Bailey
00007 
00008    @copyright Copyright 2013 John Bailey
00009 
00010    @section LICENSE
00011 
00012 Licensed under the Apache License, Version 2.0 (the "License");
00013 you may not use this file except in compliance with the License.
00014 You may obtain a copy of the License at
00015 
00016     http://www.apache.org/licenses/LICENSE-2.0
00017 
00018 Unless required by applicable law or agreed to in writing, software
00019 distributed under the License is distributed on an "AS IS" BASIS,
00020 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00021 See the License for the specific language governing permissions and
00022 limitations under the License.
00023 
00024 */
00025 
00026 #if !defined FIXEDLENGTHLIST_HPP
00027 #define      FIXEDLENGTHLIST_HPP
00028 
00029 #include <cstddef> // for size_t, NULL
00030 #include <cstring> // For memset()
00031 #include <algorithm> // for min()
00032 
00033 #ifndef STATIC_ASSERT
00034 /** Emulation of C++11's static_assert */
00035 #define STATIC_ASSERT( condition, name ) typedef char assert_failed_ ## name [ (condition) ? 1 : -1 ]
00036 #endif
00037 
00038 /*
00039     Each item in the FixedLengthList is wrapped in a
00040     FixedLengthListItem which provides the actual item and
00041     infrastructure support for the list */
00042 template < class L > class FixedLengthListItem
00043 {
00044     public:
00045         /** Pointer to the next item in the list */
00046         FixedLengthListItem<L>* m_forward;
00047         /** The content/value of the item itself */
00048         L                       m_item;
00049 };
00050 
00051 
00052 /**
00053     Iterator support class for FixedLengthList
00054 
00055    Example:
00056    \code
00057           #define LIST_LEN (20U)
00058           FixedLengthList<int,  LIST_LEN > list;
00059 
00060           int main( void ) {
00061              // List is empty
00062 
00063              list.queue( 111 );
00064              list.queue( 222 );
00065 
00066              FixedLengthList<int, LIST_LEN>::iterator it = list.begin();
00067              *it == 111;
00068              it++;
00069              *it == 222;
00070              it++;
00071              *it == list.end();
00072           }
00073    \endcode
00074 */
00075 template< class T, size_t queueMax > class FixedLengthListIter
00076 {
00077     protected:
00078         /** The iterator hooks into the used list within the FixedLengthList */
00079         FixedLengthListItem<T>* m_item;
00080     public:
00081         /** Void constructor - iterator will be equal to T::end() */
00082         FixedLengthListIter( void );
00083         /** Construct an iterator which points to a list item within a
00084             FixedLengthList */
00085         FixedLengthListIter( FixedLengthListItem<T>* p_item );
00086         /** De-reference operator, yields the value of the list item */
00087         T& operator*();
00088         /** Inequality operator */
00089         bool operator!=( const FixedLengthListIter& p_comp ) const;
00090         /** Equality operator */
00091         bool operator==( const FixedLengthListIter& p_comp ) const;
00092         /** Move the iterator forward a specified number of list elements
00093  
00094             \param p_inc Number of items to traverse */
00095         FixedLengthListIter& operator+=( const unsigned p_inc );
00096         /** Post-increment operator */
00097         FixedLengthListIter operator++( int p_int );
00098         /** Pre-increment operator */
00099         FixedLengthListIter& operator++( void );
00100 };
00101 
00102 
00103 /**
00104    Template class to implement a list with a fixed maximum
00105    number of elements (i.e. the number of elements in the list
00106    is variable but cannot exceed a defined maximum).
00107 
00108    While stl::list may be suitable for many
00109    occasions, it invariably makes use of dynamic memory
00110    allocation which can either be undesirable or overkill
00111    in some situations.  Of course, the down side of this
00112    class is that the memory required to store all items
00113    in the list is allocated for the duration of the
00114    instantiation.
00115 
00116    The implementation is based around a singly linked list
00117    with a stack of free elements.  Adding an item to the list
00118    causes one of the free elements to be popped, populated
00119    then inserted into the linked list of used elements.  For
00120    convenience both a head and tail pointer of the used list
00121    are maintained.
00122 
00123    Note that the class currently is not thread safe.
00124 
00125    Example:
00126    \code
00127           #define LIST_LEN (20U)
00128           FixedLengthList<int,  LIST_LEN > list;
00129 
00130           int main( void ) {
00131              int i;
00132              
00133              // List is empty
00134              
00135              list.queue( 111 );
00136              // List now contains 111
00137              
00138              list.queue( 222 );
00139              // List now contains 111, 222
00140              
00141              list.push( 333 );
00142              // List now contains 333, 111, 222
00143           
00144              list.pop( &i );
00145              // i == 333
00146              // List now contains 111, 222
00147           
00148              return 0;    
00149           }
00150     \endcode
00151 */
00152 template < class T, size_t queueMax > class FixedLengthList
00153 {
00154     /* Pointless to have a queue with no space in it, so the various methods
00155        shouldn't have to deal with this situation */
00156     STATIC_ASSERT( queueMax > 0, Queue_must_have_a_non_zero_length );
00157 
00158     private:
00159 
00160         /** Pool of list items */
00161         FixedLengthListItem<T>  m_items[ queueMax ];
00162 
00163 
00164         /** Pointer to the start of the queue of free list slots.  Will be NULL
00165             in the case that there none are available */
00166         FixedLengthListItem<T>* m_freeHead;
00167 
00168         /** Pointer to the first item in the list of utilised item slots.  Will
00169             be NULL in the case that there are none */
00170         FixedLengthListItem<T>* m_usedHead;
00171 
00172         /** Pointer to the last item in the list of utilised item slots.  Will
00173             be NULL in the case that there are none */
00174         FixedLengthListItem<T>* m_usedTail;
00175 
00176         /** Keep count of the number of used items on the list.  Ranges between
00177             0 and queueMax */
00178         size_t                  m_usedCount;
00179 
00180         /** Remove the specified item from the list.
00181 
00182             \p_item Item to be removed.  Note that item must exist in the list
00183                     of used items
00184         */
00185         void remove_node( FixedLengthListItem<T>* p_item );
00186 
00187     public:
00188         /** Constructor for FixedLengthList */
00189         FixedLengthList( void );
00190 
00191         /** Initialising constructor for FixedLengthList.  Parameters will be
00192             used to initialise the list
00193 
00194             \param p_items An array of items used to initialise the list.  They
00195                            will be added in the order in which they appear in
00196                            p_items
00197             \param p_count The number of items in p_items.  Only up to queueMax
00198                            items will be used - any additional items will be
00199                            ignored */
00200         FixedLengthList( const T* const p_items, size_t p_count );
00201 
00202         /**
00203            push an item onto the front of the list
00204 
00205            \param p_item The item to be added to the list
00206            \returns true in the case that the item was added
00207                     false in the case that the item was not added (no space) */
00208         bool push( const T p_item );
00209 
00210         /**
00211            pop an item from the front of the list (item is removed and returned
00212 
00213            \param p_item Pointer to be populated with the value of the item
00214            \returns true in the case that an item was returned
00215                     false in the case that an item was not returned (list empty)
00216         */
00217         bool pop( T* const p_item );
00218 
00219         /**
00220            queue an item onto the end of the list
00221 
00222            \param p_item The item to be added to the list
00223            \returns true in the case that the item was added
00224                     false in the case that the item was not added (no space) */
00225         bool queue( const T p_item );
00226 
00227         /**
00228            dequeue an item from the end of the list (item is removed and
00229            returned
00230 
00231            \param p_item Pointer to be populated with the value of the item
00232            \returns true in the case that an item was returned
00233                     false in the case that an item was not returned (list empty)
00234         */
00235         bool dequeue( T* const p_item );
00236 
00237         /** Remove the first node matching p_item from the list.  In the case
00238             that there are multiple matches, only the first is removed.
00239 
00240             \param p_item Value to be removed
00241             \returns true in the case that an item was matched and remove
00242                      false in the case that no item could be matched
00243         */
00244         bool remove( const T p_item );
00245 
00246         /** Used to find out how many items are in the list
00247 
00248             \returns Number of used items, ranging from 0 to queueMax */
00249         size_t used() const;
00250 
00251         /** Used to find out how many slots are still available in the list
00252 
00253             \returns Number of available slots, ranging from 0 to queueMax */
00254         size_t available() const;
00255 
00256         /** Determine whether or not a particular item is in the list
00257 
00258             \param p_val Item to be matched against
00259             \returns true in the case that the item is found in the list
00260                      false in the case that it is not found in the list
00261         */
00262         bool inList( const T p_val ) const;
00263 
00264         /** Remove the entire contents of the list and return it back to
00265             an empty state */
00266         void clear( void );
00267 
00268         typedef FixedLengthListIter<T, queueMax> iterator;
00269         typedef T value_type;
00270         typedef T * pointer;
00271         typedef T & reference;
00272 
00273         iterator begin( void );
00274         iterator end( void );
00275 };
00276 
00277 
00278 template < class T, size_t queueMax > 
00279 FixedLengthList< T, queueMax >::FixedLengthList( void )
00280 {
00281     clear();
00282 }
00283  
00284 template < class T, size_t queueMax > 
00285 FixedLengthList< T, queueMax >::FixedLengthList( const T* const p_items, size_t p_count ) 
00286 {
00287 
00288     const T* src = p_items;
00289 
00290     /* Can only populate up to queueMax items */
00291     size_t init_count = std::min( queueMax, p_count );
00292     FixedLengthListItem<T>* prev = NULL;
00293 
00294     m_usedHead = NULL;
00295     m_usedTail = NULL;
00296 
00297     /* Initialise the list from p_items, building the forward links */
00298     for( size_t i = 0;
00299          i < init_count;
00300          i++ )
00301     {
00302         FixedLengthListItem<T>* current = &(m_items[i]);
00303 
00304         current->m_forward = NULL;
00305         current->m_item = *(src++);
00306 
00307         /* If there was a previous item in the list, set up its forward pointer,
00308            otherwise set up the list head */
00309         if( prev != NULL ) {
00310             prev->m_forward = current;
00311         } else {
00312             m_usedHead = current;
00313         }
00314 
00315         m_usedTail = current;
00316 
00317         prev = current;
00318     }
00319 
00320     m_usedCount = init_count;
00321 
00322     m_freeHead = NULL;
00323 
00324     /* Any remaining items get moved into the free stack */
00325     
00326     prev = NULL;
00327     for( size_t i = init_count;
00328          i < queueMax;
00329          i++ )
00330     {
00331         FixedLengthListItem<T>* current = &(m_items[i]);
00332         current->m_forward = NULL;
00333         if( prev != NULL ) {
00334             prev->m_forward = current;
00335         } else {
00336             m_freeHead = current;
00337         }
00338         prev = current;
00339     }
00340 }
00341 
00342 template < class T, size_t queueMax > 
00343 void FixedLengthList< T, queueMax >::clear( void )
00344 {
00345     FixedLengthListItem<T>* p;
00346     size_t i;
00347 
00348     m_usedHead = NULL;
00349     m_usedTail = NULL;
00350     m_freeHead = m_items;
00351     
00352     /* Move all items into the free stack, setting up the forward links */
00353     for( p = m_items, i = (queueMax-1);
00354          i > 0 ;
00355          i-- )
00356     {
00357         FixedLengthListItem<T>* next = p+1;
00358         p->m_forward = next;
00359         p = next;
00360     }
00361     p->m_forward = NULL;
00362     m_usedCount = 0U;
00363 }
00364 
00365 template < class T, size_t queueMax > 
00366 bool FixedLengthList< T, queueMax >::push( const T p_item )
00367 {
00368     bool ret_val = false;
00369     
00370     /* Check that there's space in the list */
00371     if( m_freeHead != NULL )
00372     {
00373         FixedLengthListItem<T>* new_item = m_freeHead;
00374 
00375         /* Move the head pointer to the next free item in the list */
00376         m_freeHead = new_item->m_forward;
00377 
00378         new_item->m_forward = m_usedHead;
00379 
00380         new_item->m_item = p_item;
00381 
00382         m_usedHead = new_item;
00383 
00384         if( m_usedTail == NULL )
00385         {
00386             m_usedTail = new_item;
00387         }
00388 
00389         m_usedCount++;
00390 
00391         /* Indicate success */
00392         ret_val = true;
00393     }
00394 
00395     return ret_val;
00396 }
00397 
00398 template < class T, size_t queueMax > 
00399 bool FixedLengthList< T, queueMax >::queue( const T p_item )
00400 {
00401     bool ret_val = false;
00402     
00403     /* Check that there's space in the list */
00404     if( m_freeHead != NULL )
00405     {
00406         /* Grab a free item */
00407         FixedLengthListItem<T>* new_item = m_freeHead;
00408 
00409         /* Move the head pointer to the next free item in the list */
00410         m_freeHead = m_freeHead->m_forward;
00411 
00412         /* Item is going at end of list - no forward link */
00413         new_item->m_forward = NULL;
00414 
00415         new_item->m_item = p_item;
00416 
00417         /* Update the current tail item, if exists */
00418         if( m_usedTail != NULL )
00419         {
00420             m_usedTail->m_forward = new_item;
00421         }
00422 
00423         m_usedTail = new_item;
00424 
00425         if( m_usedHead == NULL )
00426         {
00427             m_usedHead = new_item;
00428         }
00429 
00430         m_usedCount++;
00431 
00432         /* Indicate success */
00433         ret_val = true;
00434     }
00435 
00436     return ret_val;
00437 }
00438 
00439 template < class T, size_t queueMax > 
00440 bool FixedLengthList< T, queueMax >::pop( T* const p_item )
00441 {
00442     bool ret_val = false;
00443     
00444     if( m_usedHead != NULL )
00445     {
00446         FixedLengthListItem<T>* old_item = m_usedHead;
00447 
00448         *p_item = old_item->m_item;
00449 
00450         m_usedHead = old_item->m_forward;
00451         
00452         if( m_usedTail == old_item )
00453         {
00454             m_usedTail = NULL;
00455         }
00456 
00457         old_item->m_forward = m_freeHead;
00458 
00459         m_freeHead = old_item;
00460 
00461         m_usedCount--;
00462 
00463         /* Indicate success */
00464         ret_val = true;
00465     }
00466 
00467     return ret_val;
00468 }
00469 
00470 template < class T, size_t queueMax >
00471 bool FixedLengthList< T, queueMax >::dequeue( T* const p_item )
00472 {
00473     bool ret_val = false;
00474 
00475     if( m_usedTail != NULL )
00476     {
00477         FixedLengthListItem<T>* old_item = m_usedTail;
00478 
00479         *p_item = old_item->m_item;
00480 
00481         remove_node( old_item );
00482 
00483         /* Indicate success */
00484         ret_val = true;
00485     }
00486 
00487     return ret_val;
00488 }
00489         
00490 
00491 template < class T, size_t queueMax >
00492 void FixedLengthList< T, queueMax >::remove_node( FixedLengthListItem<T>* p_item )
00493 {
00494     /* Item removed was only item in the list? */
00495     if( m_usedHead == p_item )
00496     {
00497         m_usedHead = NULL;
00498         m_usedTail = NULL;
00499     } else {
00500         FixedLengthListItem<T>* p = m_usedHead;
00501 
00502         /* Need to update the forward pointer of the
00503            item preceding the one which we've just removed.
00504            That item also becomes the new tail
00505 
00506            Iterate the list and find it */
00507         while( p != NULL )
00508         {
00509             if( p->m_forward == p_item )
00510             {
00511                 p->m_forward = NULL;
00512                 m_usedTail = p;
00513                 break;
00514             }
00515             else
00516             {
00517                 p = p->m_forward;
00518             }
00519         }
00520     }
00521 
00522     /* Move item to free list */
00523     p_item->m_forward = m_freeHead;
00524     m_freeHead = p_item;
00525 
00526     m_usedCount--;
00527 }
00528 
00529 template < class T, size_t queueMax >
00530 bool FixedLengthList< T, queueMax >::remove( const T p_item )
00531 {
00532     bool ret_val = false;
00533     FixedLengthListItem<T>* last = NULL;
00534     FixedLengthListItem<T>* p = m_usedHead;
00535 
00536     /* Run through all the items in the used list */
00537     while( p != NULL )
00538     {
00539         /* Does the item match the one we're looking for? */
00540         if( p->m_item == p_item )
00541         {
00542             /* If there was no last item then this must be the head, so update
00543                the head pointer, otherwise update the forward pointer on the
00544                prevceding item in the list */
00545             if( last == NULL )
00546             {
00547                 m_usedHead = p->m_forward;
00548             }
00549             else
00550             {
00551                 last->m_forward = p->m_forward;
00552             }
00553 
00554             /* Is this item the tail?  If so, update! */
00555             if( m_usedTail == p )
00556             {
00557                 m_usedTail = last;
00558             }
00559  
00560             /* Move item to free list */
00561             p->m_forward = m_freeHead;
00562             m_freeHead = p;
00563 
00564             m_usedCount--;
00565 
00566             ret_val = true;
00567             break;
00568         }
00569         else
00570         {
00571             last = p;
00572             p = p->m_forward;
00573         }
00574     }
00575 
00576     return ret_val;
00577 }
00578 
00579 template < class T, size_t queueMax > 
00580 size_t FixedLengthList< T, queueMax >::used() const
00581 {
00582     return m_usedCount;
00583 }
00584 
00585 template < class T, size_t queueMax > 
00586 size_t FixedLengthList< T, queueMax >::available() const
00587 {
00588     return queueMax - m_usedCount;
00589 }
00590         
00591 template < class T, size_t queueMax > 
00592 bool FixedLengthList< T, queueMax >::inList( const T p_val ) const
00593 {
00594     bool ret_val = false;
00595     FixedLengthListItem<T>* p = m_usedHead;
00596 
00597     /* Ordered iteration of the list checking for specified item */
00598     while( p != NULL )
00599     {
00600         if( p->m_item == p_val ) {
00601             /* Item found - flag and break out */
00602             ret_val = true;
00603             break;
00604         } else {
00605             p = p->m_forward;
00606         }
00607     }
00608 
00609     return ret_val;
00610 }
00611 
00612 template < class T, size_t queueMax >
00613 FixedLengthListIter<T, queueMax> FixedLengthList< T,queueMax >::begin( void )
00614 {
00615     return iterator( m_usedHead );
00616 }
00617 
00618 template < class T, size_t queueMax >
00619 FixedLengthListIter<T, queueMax> FixedLengthList< T,queueMax >::end( void )
00620 {
00621     return iterator( NULL );
00622 }
00623 
00624 template < class T, size_t queueMax >
00625 FixedLengthListIter< T, queueMax >::FixedLengthListIter( void ) : m_item( NULL)
00626 {
00627 }
00628 
00629 template < class T, size_t queueMax >
00630 FixedLengthListIter< T, queueMax >::FixedLengthListIter( FixedLengthListItem<T>* p_item ) : m_item( p_item )
00631 {
00632 } 
00633 
00634 template < class T, size_t queueMax > 
00635 T& FixedLengthListIter< T, queueMax >::operator*()
00636 {
00637     return m_item->m_item;
00638 } 
00639 
00640 template < class T, size_t queueMax > 
00641 FixedLengthListIter< T,queueMax > FixedLengthListIter< T,queueMax >::operator++( int p_int )
00642 {
00643     FixedLengthListIter< T,queueMax > clone( *this );
00644     m_item = m_item->m_forward;
00645     return clone;
00646 } 
00647 
00648 template < class T, size_t queueMax > 
00649 FixedLengthListIter< T,queueMax >& FixedLengthListIter< T,queueMax >::operator++( void )
00650 {
00651     m_item = m_item->m_forward;
00652     return *this;
00653 } 
00654         
00655 template < class T, size_t queueMax > 
00656 FixedLengthListIter< T,queueMax >& FixedLengthListIter< T,queueMax >::operator+=( const unsigned p_inc ) {
00657     for(unsigned i = 0;
00658         i < p_inc;
00659         i++ )
00660     {
00661         if( m_item == NULL ) {
00662             break;
00663         } else {
00664             m_item = m_item->m_forward;
00665         }
00666     }
00667     return *this;
00668 }
00669 
00670 template < class T, size_t queueMax > 
00671 bool FixedLengthListIter< T,queueMax >::operator==( const FixedLengthListIter& p_comp ) const
00672 {
00673     return m_item == p_comp.m_item;
00674 }
00675 
00676 template < class T, size_t queueMax > 
00677 bool FixedLengthListIter< T,queueMax >::operator!=( const FixedLengthListIter& p_comp ) const
00678 {
00679     return m_item != p_comp.m_item;
00680 }
00681 
00682 
00683 #endif