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@1:d98987d1d67c, 2014-01-19 (annotated)
- Committer:
- johnb
- Date:
- Sun Jan 19 13:23:21 2014 +0000
- Revision:
- 1:d98987d1d67c
- Parent:
- 0:99d701354221
- Child:
- 2:16c77b601175
Add initial iterator support
Who changed what in which revision?
User | Revision | Line number | New contents of line |
---|---|---|---|
johnb | 0:99d701354221 | 1 | /** |
johnb | 0:99d701354221 | 2 | @file |
johnb | 0:99d701354221 | 3 | @brief Template class ( FixedLengthList ) to implement a list with |
johnb | 0:99d701354221 | 4 | a limited number of elements. |
johnb | 0:99d701354221 | 5 | |
johnb | 0:99d701354221 | 6 | @author John Bailey |
johnb | 0:99d701354221 | 7 | |
johnb | 0:99d701354221 | 8 | @copyright Copyright 2013 John Bailey |
johnb | 0:99d701354221 | 9 | |
johnb | 0:99d701354221 | 10 | @section LICENSE |
johnb | 0:99d701354221 | 11 | |
johnb | 0:99d701354221 | 12 | Licensed under the Apache License, Version 2.0 (the "License"); |
johnb | 0:99d701354221 | 13 | you may not use this file except in compliance with the License. |
johnb | 0:99d701354221 | 14 | You may obtain a copy of the License at |
johnb | 0:99d701354221 | 15 | |
johnb | 0:99d701354221 | 16 | http://www.apache.org/licenses/LICENSE-2.0 |
johnb | 0:99d701354221 | 17 | |
johnb | 0:99d701354221 | 18 | Unless required by applicable law or agreed to in writing, software |
johnb | 0:99d701354221 | 19 | distributed under the License is distributed on an "AS IS" BASIS, |
johnb | 0:99d701354221 | 20 | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
johnb | 0:99d701354221 | 21 | See the License for the specific language governing permissions and |
johnb | 0:99d701354221 | 22 | limitations under the License. |
johnb | 0:99d701354221 | 23 | |
johnb | 0:99d701354221 | 24 | */ |
johnb | 0:99d701354221 | 25 | |
johnb | 0:99d701354221 | 26 | #if !defined FIXEDLENGTHLIST_HPP |
johnb | 0:99d701354221 | 27 | #define FIXEDLENGTHLIST_HPP |
johnb | 0:99d701354221 | 28 | |
johnb | 0:99d701354221 | 29 | #include <cstddef> // for size_t, NULL |
johnb | 0:99d701354221 | 30 | #include <cstring> // For memset() |
johnb | 0:99d701354221 | 31 | #include <algorithm> // for min() |
johnb | 0:99d701354221 | 32 | |
johnb | 0:99d701354221 | 33 | #ifndef STATIC_ASSERT |
johnb | 0:99d701354221 | 34 | /** Emulation of C++11's static_assert */ |
johnb | 0:99d701354221 | 35 | #define STATIC_ASSERT( condition, name ) typedef char assert_failed_ ## name [ (condition) ? 1 : -1 ] |
johnb | 0:99d701354221 | 36 | #endif |
johnb | 0:99d701354221 | 37 | |
johnb | 1:d98987d1d67c | 38 | /* |
johnb | 1:d98987d1d67c | 39 | Each item in the FixedLengthList is wrapped in a |
johnb | 1:d98987d1d67c | 40 | FixedLengthListItem which provides the actual item and |
johnb | 1:d98987d1d67c | 41 | infrastructure support for the list */ |
johnb | 1:d98987d1d67c | 42 | template < class L > class FixedLengthListItem |
johnb | 1:d98987d1d67c | 43 | { |
johnb | 1:d98987d1d67c | 44 | public: |
johnb | 1:d98987d1d67c | 45 | /** Pointer to the next item in the list */ |
johnb | 1:d98987d1d67c | 46 | FixedLengthListItem<L>* m_forward; |
johnb | 1:d98987d1d67c | 47 | /** The content/value of the item itself */ |
johnb | 1:d98987d1d67c | 48 | L m_item; |
johnb | 1:d98987d1d67c | 49 | }; |
johnb | 1:d98987d1d67c | 50 | |
johnb | 1:d98987d1d67c | 51 | |
johnb | 1:d98987d1d67c | 52 | /** |
johnb | 1:d98987d1d67c | 53 | Iterator support class for FixedLengthList |
johnb | 1:d98987d1d67c | 54 | |
johnb | 1:d98987d1d67c | 55 | Example: |
johnb | 1:d98987d1d67c | 56 | \code |
johnb | 1:d98987d1d67c | 57 | #define LIST_LEN (20U) |
johnb | 1:d98987d1d67c | 58 | FixedLengthList<int, LIST_LEN > list; |
johnb | 1:d98987d1d67c | 59 | |
johnb | 1:d98987d1d67c | 60 | int main( void ) { |
johnb | 1:d98987d1d67c | 61 | // List is empty |
johnb | 1:d98987d1d67c | 62 | |
johnb | 1:d98987d1d67c | 63 | list.queue( 111 ); |
johnb | 1:d98987d1d67c | 64 | list.queue( 222 ); |
johnb | 1:d98987d1d67c | 65 | |
johnb | 1:d98987d1d67c | 66 | FixedLengthList<int, LIST_LEN>::iterator it = list.begin(); |
johnb | 1:d98987d1d67c | 67 | *it == 111; |
johnb | 1:d98987d1d67c | 68 | it++; |
johnb | 1:d98987d1d67c | 69 | *it == 222; |
johnb | 1:d98987d1d67c | 70 | it++; |
johnb | 1:d98987d1d67c | 71 | *it == list.end(); |
johnb | 1:d98987d1d67c | 72 | } |
johnb | 1:d98987d1d67c | 73 | \endcode |
johnb | 1:d98987d1d67c | 74 | */ |
johnb | 1:d98987d1d67c | 75 | template< class T, size_t queueMax > class FixedLengthListIter |
johnb | 1:d98987d1d67c | 76 | { |
johnb | 1:d98987d1d67c | 77 | protected: |
johnb | 1:d98987d1d67c | 78 | /** The iterator hooks into the used list within the FixedLengthList */ |
johnb | 1:d98987d1d67c | 79 | FixedLengthListItem<T>* m_item; |
johnb | 1:d98987d1d67c | 80 | public: |
johnb | 1:d98987d1d67c | 81 | /** Void constructor - iterator will be equal to T::end() */ |
johnb | 1:d98987d1d67c | 82 | FixedLengthListIter( void ); |
johnb | 1:d98987d1d67c | 83 | /** Construct an iterator which points to a list item within a |
johnb | 1:d98987d1d67c | 84 | FixedLengthList */ |
johnb | 1:d98987d1d67c | 85 | FixedLengthListIter( FixedLengthListItem<T>* p_item ); |
johnb | 1:d98987d1d67c | 86 | /** De-reference operator, yields the value of the list item */ |
johnb | 1:d98987d1d67c | 87 | T& operator*(); |
johnb | 1:d98987d1d67c | 88 | /** Inequality operator */ |
johnb | 1:d98987d1d67c | 89 | bool operator!=( const FixedLengthListIter& p_comp ) const; |
johnb | 1:d98987d1d67c | 90 | /** Equality operator */ |
johnb | 1:d98987d1d67c | 91 | bool operator==( const FixedLengthListIter& p_comp ) const; |
johnb | 1:d98987d1d67c | 92 | /** Move the iterator forward a specified number of list elements |
johnb | 1:d98987d1d67c | 93 | |
johnb | 1:d98987d1d67c | 94 | \param p_inc Number of items to traverse */ |
johnb | 1:d98987d1d67c | 95 | FixedLengthListIter& operator+=( const unsigned p_inc ); |
johnb | 1:d98987d1d67c | 96 | /** Post-increment operator */ |
johnb | 1:d98987d1d67c | 97 | FixedLengthListIter operator++( int p_int ); |
johnb | 1:d98987d1d67c | 98 | /** Pre-increment operator */ |
johnb | 1:d98987d1d67c | 99 | FixedLengthListIter& operator++( void ); |
johnb | 1:d98987d1d67c | 100 | }; |
johnb | 1:d98987d1d67c | 101 | |
johnb | 1:d98987d1d67c | 102 | |
johnb | 0:99d701354221 | 103 | /** |
johnb | 0:99d701354221 | 104 | Template class to implement a list with a fixed maximum |
johnb | 0:99d701354221 | 105 | number of elements (i.e. the number of elements in the list |
johnb | 0:99d701354221 | 106 | is variable but cannot exceed a defined maximum). |
johnb | 0:99d701354221 | 107 | |
johnb | 0:99d701354221 | 108 | While stl::list may be suitable for many |
johnb | 0:99d701354221 | 109 | occasions, it invariably makes use of dynamic memory |
johnb | 0:99d701354221 | 110 | allocation which can either be undesirable or overkill |
johnb | 0:99d701354221 | 111 | in some situations. Of course, the down side of this |
johnb | 0:99d701354221 | 112 | class is that the memory required to store all items |
johnb | 0:99d701354221 | 113 | in the list is allocated for the duration of the |
johnb | 0:99d701354221 | 114 | instantiation. |
johnb | 0:99d701354221 | 115 | |
johnb | 0:99d701354221 | 116 | The implementation is based around a singly linked list |
johnb | 0:99d701354221 | 117 | with a stack of free elements. Adding an item to the list |
johnb | 0:99d701354221 | 118 | causes one of the free elements to be popped, populated |
johnb | 0:99d701354221 | 119 | then inserted into the linked list of used elements. For |
johnb | 0:99d701354221 | 120 | convenience both a head and tail pointer of the used list |
johnb | 0:99d701354221 | 121 | are maintained. |
johnb | 0:99d701354221 | 122 | |
johnb | 0:99d701354221 | 123 | Note that the class currently is not thread safe. |
johnb | 0:99d701354221 | 124 | |
johnb | 0:99d701354221 | 125 | Example: |
johnb | 0:99d701354221 | 126 | \code |
johnb | 0:99d701354221 | 127 | #define LIST_LEN (20U) |
johnb | 0:99d701354221 | 128 | FixedLengthList<int, LIST_LEN > list; |
johnb | 0:99d701354221 | 129 | |
johnb | 0:99d701354221 | 130 | int main( void ) { |
johnb | 0:99d701354221 | 131 | int i; |
johnb | 0:99d701354221 | 132 | |
johnb | 0:99d701354221 | 133 | // List is empty |
johnb | 0:99d701354221 | 134 | |
johnb | 0:99d701354221 | 135 | list.queue( 111 ); |
johnb | 0:99d701354221 | 136 | // List now contains 111 |
johnb | 0:99d701354221 | 137 | |
johnb | 0:99d701354221 | 138 | list.queue( 222 ); |
johnb | 0:99d701354221 | 139 | // List now contains 111, 222 |
johnb | 0:99d701354221 | 140 | |
johnb | 0:99d701354221 | 141 | list.push( 333 ); |
johnb | 0:99d701354221 | 142 | // List now contains 333, 111, 222 |
johnb | 0:99d701354221 | 143 | |
johnb | 0:99d701354221 | 144 | list.pop( &i ); |
johnb | 0:99d701354221 | 145 | // i == 333 |
johnb | 0:99d701354221 | 146 | // List now contains 111, 222 |
johnb | 0:99d701354221 | 147 | |
johnb | 0:99d701354221 | 148 | return 0; |
johnb | 0:99d701354221 | 149 | } |
johnb | 0:99d701354221 | 150 | \endcode |
johnb | 0:99d701354221 | 151 | */ |
johnb | 0:99d701354221 | 152 | template < class T, size_t queueMax > class FixedLengthList |
johnb | 0:99d701354221 | 153 | { |
johnb | 0:99d701354221 | 154 | /* Pointless to have a queue with no space in it, so the various methods |
johnb | 0:99d701354221 | 155 | shouldn't have to deal with this situation */ |
johnb | 0:99d701354221 | 156 | STATIC_ASSERT( queueMax > 0, Queue_must_have_a_non_zero_length ); |
johnb | 0:99d701354221 | 157 | |
johnb | 0:99d701354221 | 158 | private: |
johnb | 0:99d701354221 | 159 | |
johnb | 0:99d701354221 | 160 | /** Pool of list items */ |
johnb | 0:99d701354221 | 161 | FixedLengthListItem<T> m_items[ queueMax ]; |
johnb | 0:99d701354221 | 162 | |
johnb | 1:d98987d1d67c | 163 | |
johnb | 0:99d701354221 | 164 | /** Pointer to the start of the queue of free list slots. Will be NULL |
johnb | 0:99d701354221 | 165 | in the case that there none are available */ |
johnb | 0:99d701354221 | 166 | FixedLengthListItem<T>* m_freeHead; |
johnb | 0:99d701354221 | 167 | |
johnb | 0:99d701354221 | 168 | /** Pointer to the first item in the list of utilised item slots. Will |
johnb | 0:99d701354221 | 169 | be NULL in the case that there are none */ |
johnb | 0:99d701354221 | 170 | FixedLengthListItem<T>* m_usedHead; |
johnb | 0:99d701354221 | 171 | |
johnb | 0:99d701354221 | 172 | /** Pointer to the last item in the list of utilised item slots. Will |
johnb | 0:99d701354221 | 173 | be NULL in the case that there are none */ |
johnb | 0:99d701354221 | 174 | FixedLengthListItem<T>* m_usedTail; |
johnb | 0:99d701354221 | 175 | |
johnb | 0:99d701354221 | 176 | /** Keep count of the number of used items on the list. Ranges between |
johnb | 0:99d701354221 | 177 | 0 and queueMax */ |
johnb | 0:99d701354221 | 178 | size_t m_usedCount; |
johnb | 0:99d701354221 | 179 | |
johnb | 0:99d701354221 | 180 | public: |
johnb | 0:99d701354221 | 181 | /** Constructor for FixedLengthList */ |
johnb | 0:99d701354221 | 182 | FixedLengthList( void ); |
johnb | 0:99d701354221 | 183 | |
johnb | 0:99d701354221 | 184 | /** Initialising constructor for FixedLengthList. Parameters will be |
johnb | 0:99d701354221 | 185 | used to initialise the list |
johnb | 0:99d701354221 | 186 | |
johnb | 0:99d701354221 | 187 | \param p_items An array of items used to initialise the list. They |
johnb | 0:99d701354221 | 188 | will be added in the order in which they appear in |
johnb | 0:99d701354221 | 189 | p_items |
johnb | 0:99d701354221 | 190 | \param p_count The number of items in p_items. Only up to queueMax |
johnb | 0:99d701354221 | 191 | items will be used - any additional items will be |
johnb | 0:99d701354221 | 192 | ignored */ |
johnb | 0:99d701354221 | 193 | FixedLengthList( const T* const p_items, size_t p_count ); |
johnb | 0:99d701354221 | 194 | |
johnb | 0:99d701354221 | 195 | /** |
johnb | 0:99d701354221 | 196 | push an item onto the front of the list |
johnb | 0:99d701354221 | 197 | |
johnb | 0:99d701354221 | 198 | \param p_item The item to be added to the list |
johnb | 0:99d701354221 | 199 | \returns true in the case that the item was added |
johnb | 0:99d701354221 | 200 | false in the case that the item was not added (no space) */ |
johnb | 0:99d701354221 | 201 | bool push( const T p_item ); |
johnb | 0:99d701354221 | 202 | |
johnb | 0:99d701354221 | 203 | /** |
johnb | 0:99d701354221 | 204 | pop an item from the front of the list (item is removed and returned |
johnb | 0:99d701354221 | 205 | |
johnb | 0:99d701354221 | 206 | \param p_item Pointer to be populated with the value of the item |
johnb | 0:99d701354221 | 207 | \returns true in the case that an item was returned |
johnb | 0:99d701354221 | 208 | false in the case that an item was not returned (list empty) |
johnb | 0:99d701354221 | 209 | */ |
johnb | 0:99d701354221 | 210 | bool pop( T* const p_item ); |
johnb | 0:99d701354221 | 211 | |
johnb | 0:99d701354221 | 212 | /** |
johnb | 0:99d701354221 | 213 | queue an item onto the end of the list |
johnb | 0:99d701354221 | 214 | |
johnb | 0:99d701354221 | 215 | \param p_item The item to be added to the list |
johnb | 0:99d701354221 | 216 | \returns true in the case that the item was added |
johnb | 0:99d701354221 | 217 | false in the case that the item was not added (no space) */ |
johnb | 0:99d701354221 | 218 | bool queue( const T p_item ); |
johnb | 0:99d701354221 | 219 | |
johnb | 0:99d701354221 | 220 | /** |
johnb | 0:99d701354221 | 221 | dequeue an item from the end of the list (item is removed and |
johnb | 0:99d701354221 | 222 | returned |
johnb | 0:99d701354221 | 223 | |
johnb | 0:99d701354221 | 224 | \param p_item Pointer to be populated with the value of the item |
johnb | 0:99d701354221 | 225 | \returns true in the case that an item was returned |
johnb | 0:99d701354221 | 226 | false in the case that an item was not returned (list empty) |
johnb | 0:99d701354221 | 227 | */ |
johnb | 0:99d701354221 | 228 | bool dequeue( T* const p_item ); |
johnb | 0:99d701354221 | 229 | |
johnb | 0:99d701354221 | 230 | /** Used to find out how many items are in the list |
johnb | 0:99d701354221 | 231 | |
johnb | 0:99d701354221 | 232 | \returns Number of used items, ranging from 0 to queueMax */ |
johnb | 0:99d701354221 | 233 | size_t used() const; |
johnb | 0:99d701354221 | 234 | |
johnb | 0:99d701354221 | 235 | /** Used to find out how many slots are still available in the list |
johnb | 0:99d701354221 | 236 | |
johnb | 0:99d701354221 | 237 | \returns Number of available slots, ranging from 0 to queueMax */ |
johnb | 0:99d701354221 | 238 | size_t available() const; |
johnb | 0:99d701354221 | 239 | |
johnb | 0:99d701354221 | 240 | /** Determine whether or not a particular item is in the list |
johnb | 0:99d701354221 | 241 | |
johnb | 0:99d701354221 | 242 | \param p_val Item to be matched against |
johnb | 0:99d701354221 | 243 | \returns true in the case that the item is found in the list |
johnb | 0:99d701354221 | 244 | false in the case that it is not found in the list |
johnb | 0:99d701354221 | 245 | */ |
johnb | 0:99d701354221 | 246 | bool inList( const T p_val ) const; |
johnb | 0:99d701354221 | 247 | |
johnb | 0:99d701354221 | 248 | /** Remove the entire contents of the list and return it back to |
johnb | 0:99d701354221 | 249 | an empty state */ |
johnb | 0:99d701354221 | 250 | void clear( void ); |
johnb | 1:d98987d1d67c | 251 | |
johnb | 1:d98987d1d67c | 252 | typedef FixedLengthListIter<T, queueMax> iterator; |
johnb | 1:d98987d1d67c | 253 | typedef T value_type; |
johnb | 1:d98987d1d67c | 254 | typedef T * pointer; |
johnb | 1:d98987d1d67c | 255 | typedef T & reference; |
johnb | 1:d98987d1d67c | 256 | |
johnb | 1:d98987d1d67c | 257 | iterator begin( void ); |
johnb | 1:d98987d1d67c | 258 | iterator end( void ); |
johnb | 0:99d701354221 | 259 | }; |
johnb | 0:99d701354221 | 260 | |
johnb | 1:d98987d1d67c | 261 | |
johnb | 0:99d701354221 | 262 | template < class T, size_t queueMax > |
johnb | 0:99d701354221 | 263 | FixedLengthList< T, queueMax >::FixedLengthList( void ) |
johnb | 0:99d701354221 | 264 | { |
johnb | 0:99d701354221 | 265 | clear(); |
johnb | 0:99d701354221 | 266 | } |
johnb | 0:99d701354221 | 267 | |
johnb | 0:99d701354221 | 268 | template < class T, size_t queueMax > |
johnb | 1:d98987d1d67c | 269 | FixedLengthList< T, queueMax >::FixedLengthList( const T* const p_items, size_t p_count ) |
johnb | 1:d98987d1d67c | 270 | { |
johnb | 0:99d701354221 | 271 | |
johnb | 0:99d701354221 | 272 | const T* src = p_items; |
johnb | 0:99d701354221 | 273 | |
johnb | 0:99d701354221 | 274 | /* Can only populate up to queueMax items */ |
johnb | 0:99d701354221 | 275 | size_t init_count = std::min( queueMax, p_count ); |
johnb | 0:99d701354221 | 276 | FixedLengthListItem<T>* prev = NULL; |
johnb | 0:99d701354221 | 277 | |
johnb | 0:99d701354221 | 278 | m_usedHead = NULL; |
johnb | 0:99d701354221 | 279 | m_usedTail = NULL; |
johnb | 0:99d701354221 | 280 | |
johnb | 0:99d701354221 | 281 | /* Initialise the list from p_items, building the forward links */ |
johnb | 0:99d701354221 | 282 | for( size_t i = 0; |
johnb | 0:99d701354221 | 283 | i < init_count; |
johnb | 0:99d701354221 | 284 | i++ ) |
johnb | 0:99d701354221 | 285 | { |
johnb | 0:99d701354221 | 286 | FixedLengthListItem<T>* current = &(m_items[i]); |
johnb | 0:99d701354221 | 287 | |
johnb | 0:99d701354221 | 288 | current->m_forward = NULL; |
johnb | 0:99d701354221 | 289 | current->m_item = *(src++); |
johnb | 0:99d701354221 | 290 | |
johnb | 0:99d701354221 | 291 | /* If there was a previous item in the list, set up its forward pointer, |
johnb | 0:99d701354221 | 292 | otherwise set up the list head */ |
johnb | 0:99d701354221 | 293 | if( prev != NULL ) { |
johnb | 0:99d701354221 | 294 | prev->m_forward = current; |
johnb | 0:99d701354221 | 295 | } else { |
johnb | 0:99d701354221 | 296 | m_usedHead = current; |
johnb | 0:99d701354221 | 297 | } |
johnb | 0:99d701354221 | 298 | |
johnb | 0:99d701354221 | 299 | m_usedTail = current; |
johnb | 0:99d701354221 | 300 | |
johnb | 0:99d701354221 | 301 | prev = current; |
johnb | 0:99d701354221 | 302 | } |
johnb | 0:99d701354221 | 303 | |
johnb | 0:99d701354221 | 304 | m_usedCount = init_count; |
johnb | 0:99d701354221 | 305 | |
johnb | 0:99d701354221 | 306 | m_freeHead = NULL; |
johnb | 0:99d701354221 | 307 | |
johnb | 0:99d701354221 | 308 | /* Any remaining items get moved into the free stack */ |
johnb | 0:99d701354221 | 309 | |
johnb | 0:99d701354221 | 310 | prev = NULL; |
johnb | 0:99d701354221 | 311 | for( size_t i = init_count; |
johnb | 0:99d701354221 | 312 | i < queueMax; |
johnb | 0:99d701354221 | 313 | i++ ) |
johnb | 0:99d701354221 | 314 | { |
johnb | 0:99d701354221 | 315 | FixedLengthListItem<T>* current = &(m_items[i]); |
johnb | 0:99d701354221 | 316 | current->m_forward = NULL; |
johnb | 0:99d701354221 | 317 | if( prev != NULL ) { |
johnb | 0:99d701354221 | 318 | prev->m_forward = current; |
johnb | 0:99d701354221 | 319 | } else { |
johnb | 0:99d701354221 | 320 | m_freeHead = current; |
johnb | 0:99d701354221 | 321 | } |
johnb | 0:99d701354221 | 322 | prev = current; |
johnb | 0:99d701354221 | 323 | } |
johnb | 0:99d701354221 | 324 | } |
johnb | 0:99d701354221 | 325 | |
johnb | 0:99d701354221 | 326 | template < class T, size_t queueMax > |
johnb | 0:99d701354221 | 327 | void FixedLengthList< T, queueMax >::clear( void ) |
johnb | 0:99d701354221 | 328 | { |
johnb | 0:99d701354221 | 329 | FixedLengthListItem<T>* p; |
johnb | 0:99d701354221 | 330 | size_t i; |
johnb | 0:99d701354221 | 331 | |
johnb | 0:99d701354221 | 332 | m_usedHead = NULL; |
johnb | 0:99d701354221 | 333 | m_usedTail = NULL; |
johnb | 0:99d701354221 | 334 | m_freeHead = m_items; |
johnb | 0:99d701354221 | 335 | |
johnb | 0:99d701354221 | 336 | /* Move all items into the free stack, setting up the forward links */ |
johnb | 0:99d701354221 | 337 | for( p = m_items, i = (queueMax-1); |
johnb | 0:99d701354221 | 338 | i > 0 ; |
johnb | 0:99d701354221 | 339 | i-- ) |
johnb | 0:99d701354221 | 340 | { |
johnb | 0:99d701354221 | 341 | FixedLengthListItem<T>* next = p+1; |
johnb | 0:99d701354221 | 342 | p->m_forward = next; |
johnb | 0:99d701354221 | 343 | p = next; |
johnb | 0:99d701354221 | 344 | } |
johnb | 0:99d701354221 | 345 | p->m_forward = NULL; |
johnb | 0:99d701354221 | 346 | m_usedCount = 0U; |
johnb | 0:99d701354221 | 347 | } |
johnb | 0:99d701354221 | 348 | |
johnb | 0:99d701354221 | 349 | template < class T, size_t queueMax > |
johnb | 0:99d701354221 | 350 | bool FixedLengthList< T, queueMax >::push( const T p_item ) |
johnb | 0:99d701354221 | 351 | { |
johnb | 0:99d701354221 | 352 | bool ret_val = false; |
johnb | 0:99d701354221 | 353 | |
johnb | 0:99d701354221 | 354 | /* Check that there's space in the list */ |
johnb | 0:99d701354221 | 355 | if( m_freeHead != NULL ) |
johnb | 0:99d701354221 | 356 | { |
johnb | 0:99d701354221 | 357 | FixedLengthListItem<T>* new_item = m_freeHead; |
johnb | 0:99d701354221 | 358 | |
johnb | 0:99d701354221 | 359 | /* Move the head pointer to the next free item in the list */ |
johnb | 0:99d701354221 | 360 | m_freeHead = new_item->m_forward; |
johnb | 0:99d701354221 | 361 | |
johnb | 0:99d701354221 | 362 | new_item->m_forward = m_usedHead; |
johnb | 0:99d701354221 | 363 | |
johnb | 0:99d701354221 | 364 | new_item->m_item = p_item; |
johnb | 0:99d701354221 | 365 | |
johnb | 0:99d701354221 | 366 | m_usedHead = new_item; |
johnb | 0:99d701354221 | 367 | |
johnb | 0:99d701354221 | 368 | if( m_usedTail == NULL ) |
johnb | 0:99d701354221 | 369 | { |
johnb | 0:99d701354221 | 370 | m_usedTail = new_item; |
johnb | 0:99d701354221 | 371 | } |
johnb | 0:99d701354221 | 372 | |
johnb | 0:99d701354221 | 373 | m_usedCount++; |
johnb | 0:99d701354221 | 374 | |
johnb | 0:99d701354221 | 375 | /* Indicate success */ |
johnb | 0:99d701354221 | 376 | ret_val = true; |
johnb | 0:99d701354221 | 377 | } |
johnb | 0:99d701354221 | 378 | |
johnb | 0:99d701354221 | 379 | return ret_val; |
johnb | 0:99d701354221 | 380 | } |
johnb | 0:99d701354221 | 381 | |
johnb | 0:99d701354221 | 382 | template < class T, size_t queueMax > |
johnb | 0:99d701354221 | 383 | bool FixedLengthList< T, queueMax >::queue( const T p_item ) |
johnb | 0:99d701354221 | 384 | { |
johnb | 0:99d701354221 | 385 | bool ret_val = false; |
johnb | 0:99d701354221 | 386 | |
johnb | 0:99d701354221 | 387 | /* Check that there's space in the list */ |
johnb | 0:99d701354221 | 388 | if( m_freeHead != NULL ) |
johnb | 0:99d701354221 | 389 | { |
johnb | 0:99d701354221 | 390 | /* Grab a free item */ |
johnb | 0:99d701354221 | 391 | FixedLengthListItem<T>* new_item = m_freeHead; |
johnb | 0:99d701354221 | 392 | |
johnb | 0:99d701354221 | 393 | /* Move the head pointer to the next free item in the list */ |
johnb | 0:99d701354221 | 394 | m_freeHead = m_freeHead->m_forward; |
johnb | 0:99d701354221 | 395 | |
johnb | 0:99d701354221 | 396 | /* Item is going at end of list - no forward link */ |
johnb | 0:99d701354221 | 397 | new_item->m_forward = NULL; |
johnb | 0:99d701354221 | 398 | |
johnb | 0:99d701354221 | 399 | new_item->m_item = p_item; |
johnb | 0:99d701354221 | 400 | |
johnb | 0:99d701354221 | 401 | /* Update the current tail item, if exists */ |
johnb | 0:99d701354221 | 402 | if( m_usedTail != NULL ) |
johnb | 0:99d701354221 | 403 | { |
johnb | 0:99d701354221 | 404 | m_usedTail->m_forward = new_item; |
johnb | 0:99d701354221 | 405 | } |
johnb | 0:99d701354221 | 406 | |
johnb | 0:99d701354221 | 407 | m_usedTail = new_item; |
johnb | 0:99d701354221 | 408 | |
johnb | 0:99d701354221 | 409 | if( m_usedHead == NULL ) |
johnb | 0:99d701354221 | 410 | { |
johnb | 0:99d701354221 | 411 | m_usedHead = new_item; |
johnb | 0:99d701354221 | 412 | } |
johnb | 0:99d701354221 | 413 | |
johnb | 0:99d701354221 | 414 | m_usedCount++; |
johnb | 0:99d701354221 | 415 | |
johnb | 0:99d701354221 | 416 | /* Indicate success */ |
johnb | 0:99d701354221 | 417 | ret_val = true; |
johnb | 0:99d701354221 | 418 | } |
johnb | 0:99d701354221 | 419 | |
johnb | 0:99d701354221 | 420 | return ret_val; |
johnb | 0:99d701354221 | 421 | } |
johnb | 0:99d701354221 | 422 | |
johnb | 0:99d701354221 | 423 | template < class T, size_t queueMax > |
johnb | 0:99d701354221 | 424 | bool FixedLengthList< T, queueMax >::pop( T* const p_item ) |
johnb | 0:99d701354221 | 425 | { |
johnb | 0:99d701354221 | 426 | bool ret_val = false; |
johnb | 0:99d701354221 | 427 | |
johnb | 0:99d701354221 | 428 | if( m_usedHead != NULL ) |
johnb | 0:99d701354221 | 429 | { |
johnb | 0:99d701354221 | 430 | FixedLengthListItem<T>* old_item = m_usedHead; |
johnb | 0:99d701354221 | 431 | |
johnb | 0:99d701354221 | 432 | *p_item = old_item->m_item; |
johnb | 0:99d701354221 | 433 | |
johnb | 0:99d701354221 | 434 | m_usedHead = old_item->m_forward; |
johnb | 0:99d701354221 | 435 | |
johnb | 0:99d701354221 | 436 | if( m_usedTail == old_item ) |
johnb | 0:99d701354221 | 437 | { |
johnb | 0:99d701354221 | 438 | m_usedTail = NULL; |
johnb | 0:99d701354221 | 439 | } |
johnb | 0:99d701354221 | 440 | |
johnb | 0:99d701354221 | 441 | old_item->m_forward = m_freeHead; |
johnb | 0:99d701354221 | 442 | |
johnb | 0:99d701354221 | 443 | m_freeHead = old_item; |
johnb | 0:99d701354221 | 444 | |
johnb | 0:99d701354221 | 445 | m_usedCount--; |
johnb | 0:99d701354221 | 446 | |
johnb | 0:99d701354221 | 447 | /* Indicate success */ |
johnb | 0:99d701354221 | 448 | ret_val = true; |
johnb | 0:99d701354221 | 449 | } |
johnb | 0:99d701354221 | 450 | |
johnb | 0:99d701354221 | 451 | return ret_val; |
johnb | 0:99d701354221 | 452 | } |
johnb | 0:99d701354221 | 453 | |
johnb | 0:99d701354221 | 454 | template < class T, size_t queueMax > |
johnb | 0:99d701354221 | 455 | bool FixedLengthList< T, queueMax >::dequeue( T* const p_item ) |
johnb | 0:99d701354221 | 456 | { |
johnb | 0:99d701354221 | 457 | bool ret_val = false; |
johnb | 0:99d701354221 | 458 | |
johnb | 0:99d701354221 | 459 | if( m_usedTail != NULL ) |
johnb | 0:99d701354221 | 460 | { |
johnb | 0:99d701354221 | 461 | FixedLengthListItem<T>* old_item = m_usedTail; |
johnb | 0:99d701354221 | 462 | |
johnb | 0:99d701354221 | 463 | *p_item = old_item->m_item; |
johnb | 0:99d701354221 | 464 | |
johnb | 0:99d701354221 | 465 | /* Item removed was only item in the list? */ |
johnb | 0:99d701354221 | 466 | if( m_usedHead == old_item ) |
johnb | 0:99d701354221 | 467 | { |
johnb | 0:99d701354221 | 468 | m_usedHead = NULL; |
johnb | 0:99d701354221 | 469 | m_usedTail = NULL; |
johnb | 0:99d701354221 | 470 | } else { |
johnb | 0:99d701354221 | 471 | FixedLengthListItem<T>* p = m_usedHead; |
johnb | 0:99d701354221 | 472 | |
johnb | 0:99d701354221 | 473 | /* Need to update the forward pointer of the |
johnb | 0:99d701354221 | 474 | item preceding the one which we've just removed. |
johnb | 0:99d701354221 | 475 | That item also becomes the new tail |
johnb | 0:99d701354221 | 476 | |
johnb | 0:99d701354221 | 477 | Iterate the list and find it */ |
johnb | 0:99d701354221 | 478 | while( p != NULL ) |
johnb | 0:99d701354221 | 479 | { |
johnb | 0:99d701354221 | 480 | if( p->m_forward == old_item ) |
johnb | 0:99d701354221 | 481 | { |
johnb | 0:99d701354221 | 482 | p->m_forward = NULL; |
johnb | 0:99d701354221 | 483 | m_usedTail = p; |
johnb | 0:99d701354221 | 484 | break; |
johnb | 0:99d701354221 | 485 | } else { |
johnb | 0:99d701354221 | 486 | p = p->m_forward; |
johnb | 0:99d701354221 | 487 | } |
johnb | 0:99d701354221 | 488 | } |
johnb | 0:99d701354221 | 489 | } |
johnb | 0:99d701354221 | 490 | |
johnb | 0:99d701354221 | 491 | /* Move item to free list */ |
johnb | 0:99d701354221 | 492 | old_item->m_forward = m_freeHead; |
johnb | 0:99d701354221 | 493 | m_freeHead = old_item; |
johnb | 0:99d701354221 | 494 | |
johnb | 0:99d701354221 | 495 | m_usedCount--; |
johnb | 0:99d701354221 | 496 | |
johnb | 0:99d701354221 | 497 | /* Indicate success */ |
johnb | 0:99d701354221 | 498 | ret_val = true; |
johnb | 0:99d701354221 | 499 | } |
johnb | 0:99d701354221 | 500 | |
johnb | 0:99d701354221 | 501 | return ret_val; |
johnb | 0:99d701354221 | 502 | } |
johnb | 0:99d701354221 | 503 | |
johnb | 0:99d701354221 | 504 | template < class T, size_t queueMax > |
johnb | 0:99d701354221 | 505 | size_t FixedLengthList< T, queueMax >::used() const |
johnb | 0:99d701354221 | 506 | { |
johnb | 0:99d701354221 | 507 | return m_usedCount; |
johnb | 0:99d701354221 | 508 | } |
johnb | 0:99d701354221 | 509 | |
johnb | 0:99d701354221 | 510 | template < class T, size_t queueMax > |
johnb | 0:99d701354221 | 511 | size_t FixedLengthList< T, queueMax >::available() const |
johnb | 0:99d701354221 | 512 | { |
johnb | 0:99d701354221 | 513 | return queueMax - m_usedCount; |
johnb | 0:99d701354221 | 514 | } |
johnb | 0:99d701354221 | 515 | |
johnb | 0:99d701354221 | 516 | template < class T, size_t queueMax > |
johnb | 0:99d701354221 | 517 | bool FixedLengthList< T, queueMax >::inList( const T p_val ) const |
johnb | 0:99d701354221 | 518 | { |
johnb | 0:99d701354221 | 519 | bool ret_val = false; |
johnb | 0:99d701354221 | 520 | FixedLengthListItem<T>* p = m_usedHead; |
johnb | 0:99d701354221 | 521 | |
johnb | 0:99d701354221 | 522 | /* Ordered iteration of the list checking for specified item */ |
johnb | 0:99d701354221 | 523 | while( p != NULL ) |
johnb | 0:99d701354221 | 524 | { |
johnb | 0:99d701354221 | 525 | if( p->m_item == p_val ) { |
johnb | 0:99d701354221 | 526 | /* Item found - flag and break out */ |
johnb | 0:99d701354221 | 527 | ret_val = true; |
johnb | 0:99d701354221 | 528 | break; |
johnb | 0:99d701354221 | 529 | } else { |
johnb | 0:99d701354221 | 530 | p = p->m_forward; |
johnb | 0:99d701354221 | 531 | } |
johnb | 0:99d701354221 | 532 | } |
johnb | 0:99d701354221 | 533 | |
johnb | 0:99d701354221 | 534 | return ret_val; |
johnb | 0:99d701354221 | 535 | } |
johnb | 0:99d701354221 | 536 | |
johnb | 1:d98987d1d67c | 537 | template < class T, size_t queueMax > |
johnb | 1:d98987d1d67c | 538 | FixedLengthListIter<T, queueMax> FixedLengthList< T,queueMax >::begin( void ) |
johnb | 1:d98987d1d67c | 539 | { |
johnb | 1:d98987d1d67c | 540 | return iterator( m_usedHead ); |
johnb | 1:d98987d1d67c | 541 | } |
johnb | 1:d98987d1d67c | 542 | |
johnb | 1:d98987d1d67c | 543 | template < class T, size_t queueMax > |
johnb | 1:d98987d1d67c | 544 | FixedLengthListIter<T, queueMax> FixedLengthList< T,queueMax >::end( void ) |
johnb | 1:d98987d1d67c | 545 | { |
johnb | 1:d98987d1d67c | 546 | return iterator( NULL ); |
johnb | 1:d98987d1d67c | 547 | } |
johnb | 1:d98987d1d67c | 548 | |
johnb | 1:d98987d1d67c | 549 | template < class T, size_t queueMax > |
johnb | 1:d98987d1d67c | 550 | FixedLengthListIter< T, queueMax >::FixedLengthListIter( void ) : m_item( NULL) |
johnb | 1:d98987d1d67c | 551 | { |
johnb | 1:d98987d1d67c | 552 | } |
johnb | 1:d98987d1d67c | 553 | |
johnb | 1:d98987d1d67c | 554 | template < class T, size_t queueMax > |
johnb | 1:d98987d1d67c | 555 | FixedLengthListIter< T, queueMax >::FixedLengthListIter( FixedLengthListItem<T>* p_item ) : m_item( p_item ) |
johnb | 1:d98987d1d67c | 556 | { |
johnb | 1:d98987d1d67c | 557 | } |
johnb | 1:d98987d1d67c | 558 | |
johnb | 1:d98987d1d67c | 559 | template < class T, size_t queueMax > |
johnb | 1:d98987d1d67c | 560 | T& FixedLengthListIter< T, queueMax >::operator*() |
johnb | 1:d98987d1d67c | 561 | { |
johnb | 1:d98987d1d67c | 562 | return m_item->m_item; |
johnb | 1:d98987d1d67c | 563 | } |
johnb | 1:d98987d1d67c | 564 | |
johnb | 1:d98987d1d67c | 565 | template < class T, size_t queueMax > |
johnb | 1:d98987d1d67c | 566 | FixedLengthListIter< T,queueMax > FixedLengthListIter< T,queueMax >::operator++( int p_int ) |
johnb | 1:d98987d1d67c | 567 | { |
johnb | 1:d98987d1d67c | 568 | FixedLengthListIter< T,queueMax > clone( *this ); |
johnb | 1:d98987d1d67c | 569 | m_item = m_item->m_forward; |
johnb | 1:d98987d1d67c | 570 | return clone; |
johnb | 1:d98987d1d67c | 571 | } |
johnb | 1:d98987d1d67c | 572 | |
johnb | 1:d98987d1d67c | 573 | template < class T, size_t queueMax > |
johnb | 1:d98987d1d67c | 574 | FixedLengthListIter< T,queueMax >& FixedLengthListIter< T,queueMax >::operator++( void ) |
johnb | 1:d98987d1d67c | 575 | { |
johnb | 1:d98987d1d67c | 576 | m_item = m_item->m_forward; |
johnb | 1:d98987d1d67c | 577 | return *this; |
johnb | 1:d98987d1d67c | 578 | } |
johnb | 1:d98987d1d67c | 579 | |
johnb | 1:d98987d1d67c | 580 | template < class T, size_t queueMax > |
johnb | 1:d98987d1d67c | 581 | FixedLengthListIter< T,queueMax >& FixedLengthListIter< T,queueMax >::operator+=( const unsigned p_inc ) { |
johnb | 1:d98987d1d67c | 582 | for(unsigned i = 0; |
johnb | 1:d98987d1d67c | 583 | i < p_inc; |
johnb | 1:d98987d1d67c | 584 | i++ ) |
johnb | 1:d98987d1d67c | 585 | { |
johnb | 1:d98987d1d67c | 586 | if( m_item == NULL ) { |
johnb | 1:d98987d1d67c | 587 | break; |
johnb | 1:d98987d1d67c | 588 | } else { |
johnb | 1:d98987d1d67c | 589 | m_item = m_item->m_forward; |
johnb | 1:d98987d1d67c | 590 | } |
johnb | 1:d98987d1d67c | 591 | } |
johnb | 1:d98987d1d67c | 592 | return *this; |
johnb | 1:d98987d1d67c | 593 | } |
johnb | 1:d98987d1d67c | 594 | |
johnb | 1:d98987d1d67c | 595 | template < class T, size_t queueMax > |
johnb | 1:d98987d1d67c | 596 | bool FixedLengthListIter< T,queueMax >::operator==( const FixedLengthListIter& p_comp ) const |
johnb | 1:d98987d1d67c | 597 | { |
johnb | 1:d98987d1d67c | 598 | return m_item == p_comp.m_item; |
johnb | 1:d98987d1d67c | 599 | } |
johnb | 1:d98987d1d67c | 600 | |
johnb | 1:d98987d1d67c | 601 | template < class T, size_t queueMax > |
johnb | 1:d98987d1d67c | 602 | bool FixedLengthListIter< T,queueMax >::operator!=( const FixedLengthListIter& p_comp ) const |
johnb | 1:d98987d1d67c | 603 | { |
johnb | 1:d98987d1d67c | 604 | return m_item != p_comp.m_item; |
johnb | 1:d98987d1d67c | 605 | } |
johnb | 1:d98987d1d67c | 606 | |
johnb | 1:d98987d1d67c | 607 | |
johnb | 1:d98987d1d67c | 608 | #endif |