Template class to implement a list with a fixed maximum number of elements (i.e. number of elements in the list is dynamic but cannot exceed the initially defined value)
Dependents: FixedLengthListTest XBeeApi
FixedLengthList.hpp
- Committer:
- johnb
- Date:
- 2014-01-18
- Revision:
- 0:99d701354221
- Child:
- 1:d98987d1d67c
File content as of revision 0:99d701354221:
/** @file @brief Template class ( FixedLengthList ) to implement a list with a limited number of elements. @author John Bailey @copyright Copyright 2013 John Bailey @section LICENSE Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. */ #if !defined FIXEDLENGTHLIST_HPP #define FIXEDLENGTHLIST_HPP #include <cstddef> // for size_t, NULL #include <cstring> // For memset() #include <algorithm> // for min() #ifndef STATIC_ASSERT /** Emulation of C++11's static_assert */ #define STATIC_ASSERT( condition, name ) typedef char assert_failed_ ## name [ (condition) ? 1 : -1 ] #endif /** Template class to implement a list with a fixed maximum number of elements (i.e. the number of elements in the list is variable but cannot exceed a defined maximum). While stl::list may be suitable for many occasions, it invariably makes use of dynamic memory allocation which can either be undesirable or overkill in some situations. Of course, the down side of this class is that the memory required to store all items in the list is allocated for the duration of the instantiation. The implementation is based around a singly linked list with a stack of free elements. Adding an item to the list causes one of the free elements to be popped, populated then inserted into the linked list of used elements. For convenience both a head and tail pointer of the used list are maintained. Note that the class currently is not thread safe. Example: \code #define LIST_LEN (20U) FixedLengthList<int, LIST_LEN > list; int main( void ) { int i; // List is empty list.queue( 111 ); // List now contains 111 list.queue( 222 ); // List now contains 111, 222 list.push( 333 ); // List now contains 333, 111, 222 list.pop( &i ); // i == 333 // List now contains 111, 222 return 0; } \endcode */ template < class T, size_t queueMax > class FixedLengthList { /* Pointless to have a queue with no space in it, so the various methods shouldn't have to deal with this situation */ STATIC_ASSERT( queueMax > 0, Queue_must_have_a_non_zero_length ); private: /** Each item in the FixedLengthList is wrapped in a FixedLengthListItem which provides the actual item and infrastructure support for the list */ template < class L > class FixedLengthListItem { public: /** Pointer to the next item in the list */ FixedLengthListItem<L>* m_forward; /** The content/value of the item itself */ L m_item; }; /** Pool of list items */ FixedLengthListItem<T> m_items[ queueMax ]; /** Pointer to the start of the queue of free list slots. Will be NULL in the case that there none are available */ FixedLengthListItem<T>* m_freeHead; /** Pointer to the first item in the list of utilised item slots. Will be NULL in the case that there are none */ FixedLengthListItem<T>* m_usedHead; /** Pointer to the last item in the list of utilised item slots. Will be NULL in the case that there are none */ FixedLengthListItem<T>* m_usedTail; /** Keep count of the number of used items on the list. Ranges between 0 and queueMax */ size_t m_usedCount; public: /** Constructor for FixedLengthList */ FixedLengthList( void ); /** Initialising constructor for FixedLengthList. Parameters will be used to initialise the list \param p_items An array of items used to initialise the list. They will be added in the order in which they appear in p_items \param p_count The number of items in p_items. Only up to queueMax items will be used - any additional items will be ignored */ FixedLengthList( const T* const p_items, size_t p_count ); /** push an item onto the front of the list \param p_item The item to be added to the list \returns true in the case that the item was added false in the case that the item was not added (no space) */ bool push( const T p_item ); /** pop an item from the front of the list (item is removed and returned \param p_item Pointer to be populated with the value of the item \returns true in the case that an item was returned false in the case that an item was not returned (list empty) */ bool pop( T* const p_item ); /** queue an item onto the end of the list \param p_item The item to be added to the list \returns true in the case that the item was added false in the case that the item was not added (no space) */ bool queue( const T p_item ); /** dequeue an item from the end of the list (item is removed and returned \param p_item Pointer to be populated with the value of the item \returns true in the case that an item was returned false in the case that an item was not returned (list empty) */ bool dequeue( T* const p_item ); /** Used to find out how many items are in the list \returns Number of used items, ranging from 0 to queueMax */ size_t used() const; /** Used to find out how many slots are still available in the list \returns Number of available slots, ranging from 0 to queueMax */ size_t available() const; /** Determine whether or not a particular item is in the list \param p_val Item to be matched against \returns true in the case that the item is found in the list false in the case that it is not found in the list */ bool inList( const T p_val ) const; /** Remove the entire contents of the list and return it back to an empty state */ void clear( void ); }; template < class T, size_t queueMax > FixedLengthList< T, queueMax >::FixedLengthList( void ) { clear(); } template < class T, size_t queueMax > FixedLengthList< T, queueMax >::FixedLengthList( const T* const p_items, size_t p_count ) { const T* src = p_items; /* Can only populate up to queueMax items */ size_t init_count = std::min( queueMax, p_count ); FixedLengthListItem<T>* prev = NULL; m_usedHead = NULL; m_usedTail = NULL; /* Initialise the list from p_items, building the forward links */ for( size_t i = 0; i < init_count; i++ ) { FixedLengthListItem<T>* current = &(m_items[i]); current->m_forward = NULL; current->m_item = *(src++); /* If there was a previous item in the list, set up its forward pointer, otherwise set up the list head */ if( prev != NULL ) { prev->m_forward = current; } else { m_usedHead = current; } m_usedTail = current; prev = current; } m_usedCount = init_count; m_freeHead = NULL; /* Any remaining items get moved into the free stack */ prev = NULL; for( size_t i = init_count; i < queueMax; i++ ) { FixedLengthListItem<T>* current = &(m_items[i]); current->m_forward = NULL; if( prev != NULL ) { prev->m_forward = current; } else { m_freeHead = current; } prev = current; } } template < class T, size_t queueMax > void FixedLengthList< T, queueMax >::clear( void ) { FixedLengthListItem<T>* p; size_t i; m_usedHead = NULL; m_usedTail = NULL; m_freeHead = m_items; /* Move all items into the free stack, setting up the forward links */ for( p = m_items, i = (queueMax-1); i > 0 ; i-- ) { FixedLengthListItem<T>* next = p+1; p->m_forward = next; p = next; } p->m_forward = NULL; m_usedCount = 0U; } template < class T, size_t queueMax > bool FixedLengthList< T, queueMax >::push( const T p_item ) { bool ret_val = false; /* Check that there's space in the list */ if( m_freeHead != NULL ) { FixedLengthListItem<T>* new_item = m_freeHead; /* Move the head pointer to the next free item in the list */ m_freeHead = new_item->m_forward; new_item->m_forward = m_usedHead; new_item->m_item = p_item; m_usedHead = new_item; if( m_usedTail == NULL ) { m_usedTail = new_item; } m_usedCount++; /* Indicate success */ ret_val = true; } return ret_val; } template < class T, size_t queueMax > bool FixedLengthList< T, queueMax >::queue( const T p_item ) { bool ret_val = false; /* Check that there's space in the list */ if( m_freeHead != NULL ) { /* Grab a free item */ FixedLengthListItem<T>* new_item = m_freeHead; /* Move the head pointer to the next free item in the list */ m_freeHead = m_freeHead->m_forward; /* Item is going at end of list - no forward link */ new_item->m_forward = NULL; new_item->m_item = p_item; /* Update the current tail item, if exists */ if( m_usedTail != NULL ) { m_usedTail->m_forward = new_item; } m_usedTail = new_item; if( m_usedHead == NULL ) { m_usedHead = new_item; } m_usedCount++; /* Indicate success */ ret_val = true; } return ret_val; } template < class T, size_t queueMax > bool FixedLengthList< T, queueMax >::pop( T* const p_item ) { bool ret_val = false; if( m_usedHead != NULL ) { FixedLengthListItem<T>* old_item = m_usedHead; *p_item = old_item->m_item; m_usedHead = old_item->m_forward; if( m_usedTail == old_item ) { m_usedTail = NULL; } old_item->m_forward = m_freeHead; m_freeHead = old_item; m_usedCount--; /* Indicate success */ ret_val = true; } return ret_val; } template < class T, size_t queueMax > bool FixedLengthList< T, queueMax >::dequeue( T* const p_item ) { bool ret_val = false; if( m_usedTail != NULL ) { FixedLengthListItem<T>* old_item = m_usedTail; *p_item = old_item->m_item; /* Item removed was only item in the list? */ if( m_usedHead == old_item ) { m_usedHead = NULL; m_usedTail = NULL; } else { FixedLengthListItem<T>* p = m_usedHead; /* Need to update the forward pointer of the item preceding the one which we've just removed. That item also becomes the new tail Iterate the list and find it */ while( p != NULL ) { if( p->m_forward == old_item ) { p->m_forward = NULL; m_usedTail = p; break; } else { p = p->m_forward; } } } /* Move item to free list */ old_item->m_forward = m_freeHead; m_freeHead = old_item; m_usedCount--; /* Indicate success */ ret_val = true; } return ret_val; } template < class T, size_t queueMax > size_t FixedLengthList< T, queueMax >::used() const { return m_usedCount; } template < class T, size_t queueMax > size_t FixedLengthList< T, queueMax >::available() const { return queueMax - m_usedCount; } template < class T, size_t queueMax > bool FixedLengthList< T, queueMax >::inList( const T p_val ) const { bool ret_val = false; FixedLengthListItem<T>* p = m_usedHead; /* Ordered iteration of the list checking for specified item */ while( p != NULL ) { if( p->m_item == p_val ) { /* Item found - flag and break out */ ret_val = true; break; } else { p = p->m_forward; } } return ret_val; } #endif