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@2:16c77b601175, 2014-01-29 (annotated)

Committer:
johnb
Date:
Wed Jan 29 23:01:01 2014 +0000
Revision:
2:16c77b601175
Parent:
1:d98987d1d67c 
Add remove() method

Who changed what in which revision?

UserRevisionLine numberNew contents of line
johnb 0:99d701354221 1 /**
johnb 0:99d701354221 2 @file
johnb 2:16c77b601175 3 @brief Template class ( FixedLengthList ) to implement a list with
johnb 0:99d701354221 4 a limited number of elements.
johnb 0:99d701354221 5
johnb 2:16c77b601175 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 2:16c77b601175 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 2:16c77b601175 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 2:16c77b601175 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 2:16c77b601175 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 2:16c77b601175 180 /** Remove the specified item from the list.
johnb 2:16c77b601175 181
johnb 2:16c77b601175 182 \p_item Item to be removed. Note that item must exist in the list
johnb 2:16c77b601175 183 of used items
johnb 2:16c77b601175 184 */
johnb 2:16c77b601175 185 void remove_node( FixedLengthListItem<T>* p_item );
johnb 2:16c77b601175 186
johnb 0:99d701354221 187 public:
johnb 0:99d701354221 188 /** Constructor for FixedLengthList */
johnb 0:99d701354221 189 FixedLengthList( void );
johnb 0:99d701354221 190
johnb 0:99d701354221 191 /** Initialising constructor for FixedLengthList. Parameters will be
johnb 0:99d701354221 192 used to initialise the list
johnb 2:16c77b601175 193
johnb 0:99d701354221 194 \param p_items An array of items used to initialise the list. They
johnb 0:99d701354221 195 will be added in the order in which they appear in
johnb 0:99d701354221 196 p_items
johnb 0:99d701354221 197 \param p_count The number of items in p_items. Only up to queueMax
johnb 0:99d701354221 198 items will be used - any additional items will be
johnb 0:99d701354221 199 ignored */
johnb 0:99d701354221 200 FixedLengthList( const T* const p_items, size_t p_count );
johnb 0:99d701354221 201
johnb 0:99d701354221 202 /**
johnb 0:99d701354221 203 push an item onto the front of the list
johnb 0:99d701354221 204
johnb 0:99d701354221 205 \param p_item The item to be added to the list
johnb 0:99d701354221 206 \returns true in the case that the item was added
johnb 0:99d701354221 207 false in the case that the item was not added (no space) */
johnb 0:99d701354221 208 bool push( const T p_item );
johnb 0:99d701354221 209
johnb 0:99d701354221 210 /**
johnb 0:99d701354221 211 pop an item from the front of the list (item is removed and returned
johnb 0:99d701354221 212
johnb 0:99d701354221 213 \param p_item Pointer to be populated with the value of the item
johnb 0:99d701354221 214 \returns true in the case that an item was returned
johnb 0:99d701354221 215 false in the case that an item was not returned (list empty)
johnb 0:99d701354221 216 */
johnb 0:99d701354221 217 bool pop( T* const p_item );
johnb 0:99d701354221 218
johnb 0:99d701354221 219 /**
johnb 0:99d701354221 220 queue an item onto the end of the list
johnb 0:99d701354221 221
johnb 0:99d701354221 222 \param p_item The item to be added to the list
johnb 0:99d701354221 223 \returns true in the case that the item was added
johnb 0:99d701354221 224 false in the case that the item was not added (no space) */
johnb 0:99d701354221 225 bool queue( const T p_item );
johnb 0:99d701354221 226
johnb 0:99d701354221 227 /**
johnb 0:99d701354221 228 dequeue an item from the end of the list (item is removed and
johnb 0:99d701354221 229 returned
johnb 0:99d701354221 230
johnb 0:99d701354221 231 \param p_item Pointer to be populated with the value of the item
johnb 0:99d701354221 232 \returns true in the case that an item was returned
johnb 0:99d701354221 233 false in the case that an item was not returned (list empty)
johnb 0:99d701354221 234 */
johnb 0:99d701354221 235 bool dequeue( T* const p_item );
johnb 0:99d701354221 236
johnb 2:16c77b601175 237 /** Remove the first node matching p_item from the list. In the case
johnb 2:16c77b601175 238 that there are multiple matches, only the first is removed.
johnb 2:16c77b601175 239
johnb 2:16c77b601175 240 \param p_item Value to be removed
johnb 2:16c77b601175 241 \returns true in the case that an item was matched and remove
johnb 2:16c77b601175 242 false in the case that no item could be matched
johnb 2:16c77b601175 243 */
johnb 2:16c77b601175 244 bool remove( const T p_item );
johnb 2:16c77b601175 245
johnb 0:99d701354221 246 /** Used to find out how many items are in the list
johnb 0:99d701354221 247
johnb 0:99d701354221 248 \returns Number of used items, ranging from 0 to queueMax */
johnb 0:99d701354221 249 size_t used() const;
johnb 0:99d701354221 250
johnb 0:99d701354221 251 /** Used to find out how many slots are still available in the list
johnb 0:99d701354221 252
johnb 0:99d701354221 253 \returns Number of available slots, ranging from 0 to queueMax */
johnb 0:99d701354221 254 size_t available() const;
johnb 0:99d701354221 255
johnb 0:99d701354221 256 /** Determine whether or not a particular item is in the list
johnb 0:99d701354221 257
johnb 0:99d701354221 258 \param p_val Item to be matched against
johnb 0:99d701354221 259 \returns true in the case that the item is found in the list
johnb 0:99d701354221 260 false in the case that it is not found in the list
johnb 0:99d701354221 261 */
johnb 0:99d701354221 262 bool inList( const T p_val ) const;
johnb 0:99d701354221 263
johnb 0:99d701354221 264 /** Remove the entire contents of the list and return it back to
johnb 0:99d701354221 265 an empty state */
johnb 0:99d701354221 266 void clear( void );
johnb 1:d98987d1d67c 267
johnb 1:d98987d1d67c 268 typedef FixedLengthListIter<T, queueMax> iterator;
johnb 1:d98987d1d67c 269 typedef T value_type;
johnb 1:d98987d1d67c 270 typedef T * pointer;
johnb 1:d98987d1d67c 271 typedef T & reference;
johnb 1:d98987d1d67c 272
johnb 1:d98987d1d67c 273 iterator begin( void );
johnb 1:d98987d1d67c 274 iterator end( void );
johnb 0:99d701354221 275 };
johnb 0:99d701354221 276
johnb 1:d98987d1d67c 277
johnb 0:99d701354221 278 template < class T, size_t queueMax >
johnb 0:99d701354221 279 FixedLengthList< T, queueMax >::FixedLengthList( void )
johnb 0:99d701354221 280 {
johnb 0:99d701354221 281 clear();
johnb 0:99d701354221 282 }
johnb 0:99d701354221 283
johnb 0:99d701354221 284 template < class T, size_t queueMax >
johnb 1:d98987d1d67c 285 FixedLengthList< T, queueMax >::FixedLengthList( const T* const p_items, size_t p_count )
johnb 1:d98987d1d67c 286 {
johnb 0:99d701354221 287
johnb 0:99d701354221 288 const T* src = p_items;
johnb 0:99d701354221 289
johnb 0:99d701354221 290 /* Can only populate up to queueMax items */
johnb 0:99d701354221 291 size_t init_count = std::min( queueMax, p_count );
johnb 0:99d701354221 292 FixedLengthListItem<T>* prev = NULL;
johnb 0:99d701354221 293
johnb 0:99d701354221 294 m_usedHead = NULL;
johnb 0:99d701354221 295 m_usedTail = NULL;
johnb 0:99d701354221 296
johnb 0:99d701354221 297 /* Initialise the list from p_items, building the forward links */
johnb 0:99d701354221 298 for( size_t i = 0;
johnb 0:99d701354221 299 i < init_count;
johnb 0:99d701354221 300 i++ )
johnb 0:99d701354221 301 {
johnb 0:99d701354221 302 FixedLengthListItem<T>* current = &(m_items[i]);
johnb 0:99d701354221 303
johnb 0:99d701354221 304 current->m_forward = NULL;
johnb 0:99d701354221 305 current->m_item = *(src++);
johnb 0:99d701354221 306
johnb 0:99d701354221 307 /* If there was a previous item in the list, set up its forward pointer,
johnb 0:99d701354221 308 otherwise set up the list head */
johnb 0:99d701354221 309 if( prev != NULL ) {
johnb 0:99d701354221 310 prev->m_forward = current;
johnb 0:99d701354221 311 } else {
johnb 0:99d701354221 312 m_usedHead = current;
johnb 0:99d701354221 313 }
johnb 0:99d701354221 314
johnb 0:99d701354221 315 m_usedTail = current;
johnb 0:99d701354221 316
johnb 0:99d701354221 317 prev = current;
johnb 0:99d701354221 318 }
johnb 0:99d701354221 319
johnb 0:99d701354221 320 m_usedCount = init_count;
johnb 0:99d701354221 321
johnb 0:99d701354221 322 m_freeHead = NULL;
johnb 0:99d701354221 323
johnb 0:99d701354221 324 /* Any remaining items get moved into the free stack */
johnb 0:99d701354221 325
johnb 0:99d701354221 326 prev = NULL;
johnb 0:99d701354221 327 for( size_t i = init_count;
johnb 0:99d701354221 328 i < queueMax;
johnb 0:99d701354221 329 i++ )
johnb 0:99d701354221 330 {
johnb 0:99d701354221 331 FixedLengthListItem<T>* current = &(m_items[i]);
johnb 0:99d701354221 332 current->m_forward = NULL;
johnb 0:99d701354221 333 if( prev != NULL ) {
johnb 0:99d701354221 334 prev->m_forward = current;
johnb 0:99d701354221 335 } else {
johnb 0:99d701354221 336 m_freeHead = current;
johnb 0:99d701354221 337 }
johnb 0:99d701354221 338 prev = current;
johnb 0:99d701354221 339 }
johnb 0:99d701354221 340 }
johnb 0:99d701354221 341
johnb 0:99d701354221 342 template < class T, size_t queueMax >
johnb 0:99d701354221 343 void FixedLengthList< T, queueMax >::clear( void )
johnb 0:99d701354221 344 {
johnb 0:99d701354221 345 FixedLengthListItem<T>* p;
johnb 0:99d701354221 346 size_t i;
johnb 0:99d701354221 347
johnb 0:99d701354221 348 m_usedHead = NULL;
johnb 0:99d701354221 349 m_usedTail = NULL;
johnb 0:99d701354221 350 m_freeHead = m_items;
johnb 0:99d701354221 351
johnb 0:99d701354221 352 /* Move all items into the free stack, setting up the forward links */
johnb 0:99d701354221 353 for( p = m_items, i = (queueMax-1);
johnb 0:99d701354221 354 i > 0 ;
johnb 0:99d701354221 355 i-- )
johnb 0:99d701354221 356 {
johnb 0:99d701354221 357 FixedLengthListItem<T>* next = p+1;
johnb 0:99d701354221 358 p->m_forward = next;
johnb 0:99d701354221 359 p = next;
johnb 0:99d701354221 360 }
johnb 0:99d701354221 361 p->m_forward = NULL;
johnb 0:99d701354221 362 m_usedCount = 0U;
johnb 0:99d701354221 363 }
johnb 0:99d701354221 364
johnb 0:99d701354221 365 template < class T, size_t queueMax >
johnb 0:99d701354221 366 bool FixedLengthList< T, queueMax >::push( const T p_item )
johnb 0:99d701354221 367 {
johnb 0:99d701354221 368 bool ret_val = false;
johnb 0:99d701354221 369
johnb 0:99d701354221 370 /* Check that there's space in the list */
johnb 0:99d701354221 371 if( m_freeHead != NULL )
johnb 0:99d701354221 372 {
johnb 0:99d701354221 373 FixedLengthListItem<T>* new_item = m_freeHead;
johnb 0:99d701354221 374
johnb 0:99d701354221 375 /* Move the head pointer to the next free item in the list */
johnb 0:99d701354221 376 m_freeHead = new_item->m_forward;
johnb 0:99d701354221 377
johnb 0:99d701354221 378 new_item->m_forward = m_usedHead;
johnb 0:99d701354221 379
johnb 0:99d701354221 380 new_item->m_item = p_item;
johnb 0:99d701354221 381
johnb 0:99d701354221 382 m_usedHead = new_item;
johnb 0:99d701354221 383
johnb 0:99d701354221 384 if( m_usedTail == NULL )
johnb 0:99d701354221 385 {
johnb 0:99d701354221 386 m_usedTail = new_item;
johnb 0:99d701354221 387 }
johnb 0:99d701354221 388
johnb 0:99d701354221 389 m_usedCount++;
johnb 0:99d701354221 390
johnb 0:99d701354221 391 /* Indicate success */
johnb 0:99d701354221 392 ret_val = true;
johnb 0:99d701354221 393 }
johnb 0:99d701354221 394
johnb 0:99d701354221 395 return ret_val;
johnb 0:99d701354221 396 }
johnb 0:99d701354221 397
johnb 0:99d701354221 398 template < class T, size_t queueMax >
johnb 0:99d701354221 399 bool FixedLengthList< T, queueMax >::queue( const T p_item )
johnb 0:99d701354221 400 {
johnb 0:99d701354221 401 bool ret_val = false;
johnb 0:99d701354221 402
johnb 0:99d701354221 403 /* Check that there's space in the list */
johnb 0:99d701354221 404 if( m_freeHead != NULL )
johnb 0:99d701354221 405 {
johnb 0:99d701354221 406 /* Grab a free item */
johnb 0:99d701354221 407 FixedLengthListItem<T>* new_item = m_freeHead;
johnb 0:99d701354221 408
johnb 0:99d701354221 409 /* Move the head pointer to the next free item in the list */
johnb 0:99d701354221 410 m_freeHead = m_freeHead->m_forward;
johnb 0:99d701354221 411
johnb 0:99d701354221 412 /* Item is going at end of list - no forward link */
johnb 0:99d701354221 413 new_item->m_forward = NULL;
johnb 0:99d701354221 414
johnb 0:99d701354221 415 new_item->m_item = p_item;
johnb 0:99d701354221 416
johnb 0:99d701354221 417 /* Update the current tail item, if exists */
johnb 0:99d701354221 418 if( m_usedTail != NULL )
johnb 0:99d701354221 419 {
johnb 0:99d701354221 420 m_usedTail->m_forward = new_item;
johnb 0:99d701354221 421 }
johnb 0:99d701354221 422
johnb 0:99d701354221 423 m_usedTail = new_item;
johnb 0:99d701354221 424
johnb 0:99d701354221 425 if( m_usedHead == NULL )
johnb 0:99d701354221 426 {
johnb 0:99d701354221 427 m_usedHead = new_item;
johnb 0:99d701354221 428 }
johnb 0:99d701354221 429
johnb 0:99d701354221 430 m_usedCount++;
johnb 0:99d701354221 431
johnb 0:99d701354221 432 /* Indicate success */
johnb 0:99d701354221 433 ret_val = true;
johnb 0:99d701354221 434 }
johnb 0:99d701354221 435
johnb 0:99d701354221 436 return ret_val;
johnb 0:99d701354221 437 }
johnb 0:99d701354221 438
johnb 0:99d701354221 439 template < class T, size_t queueMax >
johnb 0:99d701354221 440 bool FixedLengthList< T, queueMax >::pop( T* const p_item )
johnb 0:99d701354221 441 {
johnb 0:99d701354221 442 bool ret_val = false;
johnb 0:99d701354221 443
johnb 0:99d701354221 444 if( m_usedHead != NULL )
johnb 0:99d701354221 445 {
johnb 0:99d701354221 446 FixedLengthListItem<T>* old_item = m_usedHead;
johnb 0:99d701354221 447
johnb 0:99d701354221 448 *p_item = old_item->m_item;
johnb 0:99d701354221 449
johnb 0:99d701354221 450 m_usedHead = old_item->m_forward;
johnb 0:99d701354221 451
johnb 0:99d701354221 452 if( m_usedTail == old_item )
johnb 0:99d701354221 453 {
johnb 0:99d701354221 454 m_usedTail = NULL;
johnb 0:99d701354221 455 }
johnb 0:99d701354221 456
johnb 0:99d701354221 457 old_item->m_forward = m_freeHead;
johnb 0:99d701354221 458
johnb 0:99d701354221 459 m_freeHead = old_item;
johnb 0:99d701354221 460
johnb 0:99d701354221 461 m_usedCount--;
johnb 0:99d701354221 462
johnb 0:99d701354221 463 /* Indicate success */
johnb 0:99d701354221 464 ret_val = true;
johnb 0:99d701354221 465 }
johnb 0:99d701354221 466
johnb 0:99d701354221 467 return ret_val;
johnb 0:99d701354221 468 }
johnb 0:99d701354221 469
johnb 0:99d701354221 470 template < class T, size_t queueMax >
johnb 0:99d701354221 471 bool FixedLengthList< T, queueMax >::dequeue( T* const p_item )
johnb 0:99d701354221 472 {
johnb 0:99d701354221 473 bool ret_val = false;
johnb 2:16c77b601175 474
johnb 0:99d701354221 475 if( m_usedTail != NULL )
johnb 0:99d701354221 476 {
johnb 0:99d701354221 477 FixedLengthListItem<T>* old_item = m_usedTail;
johnb 0:99d701354221 478
johnb 0:99d701354221 479 *p_item = old_item->m_item;
johnb 0:99d701354221 480
johnb 2:16c77b601175 481 remove_node( old_item );
johnb 0:99d701354221 482
johnb 0:99d701354221 483 /* Indicate success */
johnb 0:99d701354221 484 ret_val = true;
johnb 0:99d701354221 485 }
johnb 0:99d701354221 486
johnb 0:99d701354221 487 return ret_val;
johnb 0:99d701354221 488 }
johnb 2:16c77b601175 489
johnb 2:16c77b601175 490
johnb 2:16c77b601175 491 template < class T, size_t queueMax >
johnb 2:16c77b601175 492 void FixedLengthList< T, queueMax >::remove_node( FixedLengthListItem<T>* p_item )
johnb 2:16c77b601175 493 {
johnb 2:16c77b601175 494 /* Item removed was only item in the list? */
johnb 2:16c77b601175 495 if( m_usedHead == p_item )
johnb 2:16c77b601175 496 {
johnb 2:16c77b601175 497 m_usedHead = NULL;
johnb 2:16c77b601175 498 m_usedTail = NULL;
johnb 2:16c77b601175 499 } else {
johnb 2:16c77b601175 500 FixedLengthListItem<T>* p = m_usedHead;
johnb 2:16c77b601175 501
johnb 2:16c77b601175 502 /* Need to update the forward pointer of the
johnb 2:16c77b601175 503 item preceding the one which we've just removed.
johnb 2:16c77b601175 504 That item also becomes the new tail
johnb 2:16c77b601175 505
johnb 2:16c77b601175 506 Iterate the list and find it */
johnb 2:16c77b601175 507 while( p != NULL )
johnb 2:16c77b601175 508 {
johnb 2:16c77b601175 509 if( p->m_forward == p_item )
johnb 2:16c77b601175 510 {
johnb 2:16c77b601175 511 p->m_forward = NULL;
johnb 2:16c77b601175 512 m_usedTail = p;
johnb 2:16c77b601175 513 break;
johnb 2:16c77b601175 514 }
johnb 2:16c77b601175 515 else
johnb 2:16c77b601175 516 {
johnb 2:16c77b601175 517 p = p->m_forward;
johnb 2:16c77b601175 518 }
johnb 2:16c77b601175 519 }
johnb 2:16c77b601175 520 }
johnb 2:16c77b601175 521
johnb 2:16c77b601175 522 /* Move item to free list */
johnb 2:16c77b601175 523 p_item->m_forward = m_freeHead;
johnb 2:16c77b601175 524 m_freeHead = p_item;
johnb 2:16c77b601175 525
johnb 2:16c77b601175 526 m_usedCount--;
johnb 2:16c77b601175 527 }
johnb 2:16c77b601175 528
johnb 2:16c77b601175 529 template < class T, size_t queueMax >
johnb 2:16c77b601175 530 bool FixedLengthList< T, queueMax >::remove( const T p_item )
johnb 2:16c77b601175 531 {
johnb 2:16c77b601175 532 bool ret_val = false;
johnb 2:16c77b601175 533 FixedLengthListItem<T>* last = NULL;
johnb 2:16c77b601175 534 FixedLengthListItem<T>* p = m_usedHead;
johnb 2:16c77b601175 535
johnb 2:16c77b601175 536 /* Run through all the items in the used list */
johnb 2:16c77b601175 537 while( p != NULL )
johnb 2:16c77b601175 538 {
johnb 2:16c77b601175 539 /* Does the item match the one we're looking for? */
johnb 2:16c77b601175 540 if( p->m_item == p_item )
johnb 2:16c77b601175 541 {
johnb 2:16c77b601175 542 /* If there was no last item then this must be the head, so update
johnb 2:16c77b601175 543 the head pointer, otherwise update the forward pointer on the
johnb 2:16c77b601175 544 prevceding item in the list */
johnb 2:16c77b601175 545 if( last == NULL )
johnb 2:16c77b601175 546 {
johnb 2:16c77b601175 547 m_usedHead = p->m_forward;
johnb 2:16c77b601175 548 }
johnb 2:16c77b601175 549 else
johnb 2:16c77b601175 550 {
johnb 2:16c77b601175 551 last->m_forward = p->m_forward;
johnb 2:16c77b601175 552 }
johnb 2:16c77b601175 553
johnb 2:16c77b601175 554 /* Is this item the tail? If so, update! */
johnb 2:16c77b601175 555 if( m_usedTail == p )
johnb 2:16c77b601175 556 {
johnb 2:16c77b601175 557 m_usedTail = last;
johnb 2:16c77b601175 558 }
johnb 2:16c77b601175 559
johnb 2:16c77b601175 560 /* Move item to free list */
johnb 2:16c77b601175 561 p->m_forward = m_freeHead;
johnb 2:16c77b601175 562 m_freeHead = p;
johnb 2:16c77b601175 563
johnb 2:16c77b601175 564 m_usedCount--;
johnb 2:16c77b601175 565
johnb 2:16c77b601175 566 ret_val = true;
johnb 2:16c77b601175 567 break;
johnb 2:16c77b601175 568 }
johnb 2:16c77b601175 569 else
johnb 2:16c77b601175 570 {
johnb 2:16c77b601175 571 last = p;
johnb 2:16c77b601175 572 p = p->m_forward;
johnb 2:16c77b601175 573 }
johnb 2:16c77b601175 574 }
johnb 2:16c77b601175 575
johnb 2:16c77b601175 576 return ret_val;
johnb 2:16c77b601175 577 }
johnb 0:99d701354221 578
johnb 0:99d701354221 579 template < class T, size_t queueMax >
johnb 0:99d701354221 580 size_t FixedLengthList< T, queueMax >::used() const
johnb 0:99d701354221 581 {
johnb 0:99d701354221 582 return m_usedCount;
johnb 0:99d701354221 583 }
johnb 0:99d701354221 584
johnb 0:99d701354221 585 template < class T, size_t queueMax >
johnb 0:99d701354221 586 size_t FixedLengthList< T, queueMax >::available() const
johnb 0:99d701354221 587 {
johnb 0:99d701354221 588 return queueMax - m_usedCount;
johnb 0:99d701354221 589 }
johnb 0:99d701354221 590
johnb 0:99d701354221 591 template < class T, size_t queueMax >
johnb 0:99d701354221 592 bool FixedLengthList< T, queueMax >::inList( const T p_val ) const
johnb 0:99d701354221 593 {
johnb 0:99d701354221 594 bool ret_val = false;
johnb 0:99d701354221 595 FixedLengthListItem<T>* p = m_usedHead;
johnb 0:99d701354221 596
johnb 0:99d701354221 597 /* Ordered iteration of the list checking for specified item */
johnb 0:99d701354221 598 while( p != NULL )
johnb 0:99d701354221 599 {
johnb 0:99d701354221 600 if( p->m_item == p_val ) {
johnb 0:99d701354221 601 /* Item found - flag and break out */
johnb 0:99d701354221 602 ret_val = true;
johnb 0:99d701354221 603 break;
johnb 0:99d701354221 604 } else {
johnb 0:99d701354221 605 p = p->m_forward;
johnb 0:99d701354221 606 }
johnb 0:99d701354221 607 }
johnb 0:99d701354221 608
johnb 0:99d701354221 609 return ret_val;
johnb 0:99d701354221 610 }
johnb 0:99d701354221 611
johnb 1:d98987d1d67c 612 template < class T, size_t queueMax >
johnb 1:d98987d1d67c 613 FixedLengthListIter<T, queueMax> FixedLengthList< T,queueMax >::begin( void )
johnb 1:d98987d1d67c 614 {
johnb 1:d98987d1d67c 615 return iterator( m_usedHead );
johnb 1:d98987d1d67c 616 }
johnb 1:d98987d1d67c 617
johnb 1:d98987d1d67c 618 template < class T, size_t queueMax >
johnb 1:d98987d1d67c 619 FixedLengthListIter<T, queueMax> FixedLengthList< T,queueMax >::end( void )
johnb 1:d98987d1d67c 620 {
johnb 1:d98987d1d67c 621 return iterator( NULL );
johnb 1:d98987d1d67c 622 }
johnb 1:d98987d1d67c 623
johnb 1:d98987d1d67c 624 template < class T, size_t queueMax >
johnb 1:d98987d1d67c 625 FixedLengthListIter< T, queueMax >::FixedLengthListIter( void ) : m_item( NULL)
johnb 1:d98987d1d67c 626 {
johnb 1:d98987d1d67c 627 }
johnb 1:d98987d1d67c 628
johnb 1:d98987d1d67c 629 template < class T, size_t queueMax >
johnb 1:d98987d1d67c 630 FixedLengthListIter< T, queueMax >::FixedLengthListIter( FixedLengthListItem<T>* p_item ) : m_item( p_item )
johnb 1:d98987d1d67c 631 {
johnb 1:d98987d1d67c 632 }
johnb 1:d98987d1d67c 633
johnb 1:d98987d1d67c 634 template < class T, size_t queueMax >
johnb 1:d98987d1d67c 635 T& FixedLengthListIter< T, queueMax >::operator*()
johnb 1:d98987d1d67c 636 {
johnb 1:d98987d1d67c 637 return m_item->m_item;
johnb 1:d98987d1d67c 638 }
johnb 1:d98987d1d67c 639
johnb 1:d98987d1d67c 640 template < class T, size_t queueMax >
johnb 1:d98987d1d67c 641 FixedLengthListIter< T,queueMax > FixedLengthListIter< T,queueMax >::operator++( int p_int )
johnb 1:d98987d1d67c 642 {
johnb 1:d98987d1d67c 643 FixedLengthListIter< T,queueMax > clone( *this );
johnb 1:d98987d1d67c 644 m_item = m_item->m_forward;
johnb 1:d98987d1d67c 645 return clone;
johnb 1:d98987d1d67c 646 }
johnb 1:d98987d1d67c 647
johnb 1:d98987d1d67c 648 template < class T, size_t queueMax >
johnb 1:d98987d1d67c 649 FixedLengthListIter< T,queueMax >& FixedLengthListIter< T,queueMax >::operator++( void )
johnb 1:d98987d1d67c 650 {
johnb 1:d98987d1d67c 651 m_item = m_item->m_forward;
johnb 1:d98987d1d67c 652 return *this;
johnb 1:d98987d1d67c 653 }
johnb 1:d98987d1d67c 654
johnb 1:d98987d1d67c 655 template < class T, size_t queueMax >
johnb 1:d98987d1d67c 656 FixedLengthListIter< T,queueMax >& FixedLengthListIter< T,queueMax >::operator+=( const unsigned p_inc ) {
johnb 1:d98987d1d67c 657 for(unsigned i = 0;
johnb 1:d98987d1d67c 658 i < p_inc;
johnb 1:d98987d1d67c 659 i++ )
johnb 1:d98987d1d67c 660 {
johnb 1:d98987d1d67c 661 if( m_item == NULL ) {
johnb 1:d98987d1d67c 662 break;
johnb 1:d98987d1d67c 663 } else {
johnb 1:d98987d1d67c 664 m_item = m_item->m_forward;
johnb 1:d98987d1d67c 665 }
johnb 1:d98987d1d67c 666 }
johnb 1:d98987d1d67c 667 return *this;
johnb 1:d98987d1d67c 668 }
johnb 1:d98987d1d67c 669
johnb 1:d98987d1d67c 670 template < class T, size_t queueMax >
johnb 1:d98987d1d67c 671 bool FixedLengthListIter< T,queueMax >::operator==( const FixedLengthListIter& p_comp ) const
johnb 1:d98987d1d67c 672 {
johnb 1:d98987d1d67c 673 return m_item == p_comp.m_item;
johnb 1:d98987d1d67c 674 }
johnb 1:d98987d1d67c 675
johnb 1:d98987d1d67c 676 template < class T, size_t queueMax >
johnb 1:d98987d1d67c 677 bool FixedLengthListIter< T,queueMax >::operator!=( const FixedLengthListIter& p_comp ) const
johnb 1:d98987d1d67c 678 {
johnb 1:d98987d1d67c 679 return m_item != p_comp.m_item;
johnb 1:d98987d1d67c 680 }
johnb 1:d98987d1d67c 681
johnb 1:d98987d1d67c 682
johnb 2:16c77b601175 683 #endif