John Bailey / FixedLengthList

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?

UserRevisionLine numberNew 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