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@0:99d701354221, 2014-01-18 (annotated)
- Committer:
- johnb
- Date:
- Sat Jan 18 16:04:07 2014 +0000
- Revision:
- 0:99d701354221
- Child:
- 1:d98987d1d67c
Initial version - class working but missing various features such as random access & iterators
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 | 0:99d701354221 | 38 | /** |
johnb | 0:99d701354221 | 39 | Template class to implement a list with a fixed maximum |
johnb | 0:99d701354221 | 40 | number of elements (i.e. the number of elements in the list |
johnb | 0:99d701354221 | 41 | is variable but cannot exceed a defined maximum). |
johnb | 0:99d701354221 | 42 | |
johnb | 0:99d701354221 | 43 | While stl::list may be suitable for many |
johnb | 0:99d701354221 | 44 | occasions, it invariably makes use of dynamic memory |
johnb | 0:99d701354221 | 45 | allocation which can either be undesirable or overkill |
johnb | 0:99d701354221 | 46 | in some situations. Of course, the down side of this |
johnb | 0:99d701354221 | 47 | class is that the memory required to store all items |
johnb | 0:99d701354221 | 48 | in the list is allocated for the duration of the |
johnb | 0:99d701354221 | 49 | instantiation. |
johnb | 0:99d701354221 | 50 | |
johnb | 0:99d701354221 | 51 | The implementation is based around a singly linked list |
johnb | 0:99d701354221 | 52 | with a stack of free elements. Adding an item to the list |
johnb | 0:99d701354221 | 53 | causes one of the free elements to be popped, populated |
johnb | 0:99d701354221 | 54 | then inserted into the linked list of used elements. For |
johnb | 0:99d701354221 | 55 | convenience both a head and tail pointer of the used list |
johnb | 0:99d701354221 | 56 | are maintained. |
johnb | 0:99d701354221 | 57 | |
johnb | 0:99d701354221 | 58 | Note that the class currently is not thread safe. |
johnb | 0:99d701354221 | 59 | |
johnb | 0:99d701354221 | 60 | Example: |
johnb | 0:99d701354221 | 61 | \code |
johnb | 0:99d701354221 | 62 | #define LIST_LEN (20U) |
johnb | 0:99d701354221 | 63 | FixedLengthList<int, LIST_LEN > list; |
johnb | 0:99d701354221 | 64 | |
johnb | 0:99d701354221 | 65 | int main( void ) { |
johnb | 0:99d701354221 | 66 | int i; |
johnb | 0:99d701354221 | 67 | |
johnb | 0:99d701354221 | 68 | // List is empty |
johnb | 0:99d701354221 | 69 | |
johnb | 0:99d701354221 | 70 | list.queue( 111 ); |
johnb | 0:99d701354221 | 71 | // List now contains 111 |
johnb | 0:99d701354221 | 72 | |
johnb | 0:99d701354221 | 73 | list.queue( 222 ); |
johnb | 0:99d701354221 | 74 | // List now contains 111, 222 |
johnb | 0:99d701354221 | 75 | |
johnb | 0:99d701354221 | 76 | list.push( 333 ); |
johnb | 0:99d701354221 | 77 | // List now contains 333, 111, 222 |
johnb | 0:99d701354221 | 78 | |
johnb | 0:99d701354221 | 79 | list.pop( &i ); |
johnb | 0:99d701354221 | 80 | // i == 333 |
johnb | 0:99d701354221 | 81 | // List now contains 111, 222 |
johnb | 0:99d701354221 | 82 | |
johnb | 0:99d701354221 | 83 | return 0; |
johnb | 0:99d701354221 | 84 | } |
johnb | 0:99d701354221 | 85 | \endcode |
johnb | 0:99d701354221 | 86 | */ |
johnb | 0:99d701354221 | 87 | template < class T, size_t queueMax > class FixedLengthList |
johnb | 0:99d701354221 | 88 | { |
johnb | 0:99d701354221 | 89 | /* Pointless to have a queue with no space in it, so the various methods |
johnb | 0:99d701354221 | 90 | shouldn't have to deal with this situation */ |
johnb | 0:99d701354221 | 91 | STATIC_ASSERT( queueMax > 0, Queue_must_have_a_non_zero_length ); |
johnb | 0:99d701354221 | 92 | |
johnb | 0:99d701354221 | 93 | private: |
johnb | 0:99d701354221 | 94 | |
johnb | 0:99d701354221 | 95 | /** |
johnb | 0:99d701354221 | 96 | Each item in the FixedLengthList is wrapped in a |
johnb | 0:99d701354221 | 97 | FixedLengthListItem which provides the actual item and |
johnb | 0:99d701354221 | 98 | infrastructure support for the list */ |
johnb | 0:99d701354221 | 99 | template < class L > class FixedLengthListItem |
johnb | 0:99d701354221 | 100 | { |
johnb | 0:99d701354221 | 101 | public: |
johnb | 0:99d701354221 | 102 | /** Pointer to the next item in the list */ |
johnb | 0:99d701354221 | 103 | FixedLengthListItem<L>* m_forward; |
johnb | 0:99d701354221 | 104 | /** The content/value of the item itself */ |
johnb | 0:99d701354221 | 105 | L m_item; |
johnb | 0:99d701354221 | 106 | }; |
johnb | 0:99d701354221 | 107 | |
johnb | 0:99d701354221 | 108 | /** Pool of list items */ |
johnb | 0:99d701354221 | 109 | FixedLengthListItem<T> m_items[ queueMax ]; |
johnb | 0:99d701354221 | 110 | |
johnb | 0:99d701354221 | 111 | /** Pointer to the start of the queue of free list slots. Will be NULL |
johnb | 0:99d701354221 | 112 | in the case that there none are available */ |
johnb | 0:99d701354221 | 113 | FixedLengthListItem<T>* m_freeHead; |
johnb | 0:99d701354221 | 114 | |
johnb | 0:99d701354221 | 115 | /** Pointer to the first item in the list of utilised item slots. Will |
johnb | 0:99d701354221 | 116 | be NULL in the case that there are none */ |
johnb | 0:99d701354221 | 117 | FixedLengthListItem<T>* m_usedHead; |
johnb | 0:99d701354221 | 118 | |
johnb | 0:99d701354221 | 119 | /** Pointer to the last item in the list of utilised item slots. Will |
johnb | 0:99d701354221 | 120 | be NULL in the case that there are none */ |
johnb | 0:99d701354221 | 121 | FixedLengthListItem<T>* m_usedTail; |
johnb | 0:99d701354221 | 122 | |
johnb | 0:99d701354221 | 123 | /** Keep count of the number of used items on the list. Ranges between |
johnb | 0:99d701354221 | 124 | 0 and queueMax */ |
johnb | 0:99d701354221 | 125 | size_t m_usedCount; |
johnb | 0:99d701354221 | 126 | |
johnb | 0:99d701354221 | 127 | public: |
johnb | 0:99d701354221 | 128 | /** Constructor for FixedLengthList */ |
johnb | 0:99d701354221 | 129 | FixedLengthList( void ); |
johnb | 0:99d701354221 | 130 | |
johnb | 0:99d701354221 | 131 | /** Initialising constructor for FixedLengthList. Parameters will be |
johnb | 0:99d701354221 | 132 | used to initialise the list |
johnb | 0:99d701354221 | 133 | |
johnb | 0:99d701354221 | 134 | \param p_items An array of items used to initialise the list. They |
johnb | 0:99d701354221 | 135 | will be added in the order in which they appear in |
johnb | 0:99d701354221 | 136 | p_items |
johnb | 0:99d701354221 | 137 | \param p_count The number of items in p_items. Only up to queueMax |
johnb | 0:99d701354221 | 138 | items will be used - any additional items will be |
johnb | 0:99d701354221 | 139 | ignored */ |
johnb | 0:99d701354221 | 140 | FixedLengthList( const T* const p_items, size_t p_count ); |
johnb | 0:99d701354221 | 141 | |
johnb | 0:99d701354221 | 142 | /** |
johnb | 0:99d701354221 | 143 | push an item onto the front of the list |
johnb | 0:99d701354221 | 144 | |
johnb | 0:99d701354221 | 145 | \param p_item The item to be added to the list |
johnb | 0:99d701354221 | 146 | \returns true in the case that the item was added |
johnb | 0:99d701354221 | 147 | false in the case that the item was not added (no space) */ |
johnb | 0:99d701354221 | 148 | bool push( const T p_item ); |
johnb | 0:99d701354221 | 149 | |
johnb | 0:99d701354221 | 150 | /** |
johnb | 0:99d701354221 | 151 | pop an item from the front of the list (item is removed and returned |
johnb | 0:99d701354221 | 152 | |
johnb | 0:99d701354221 | 153 | \param p_item Pointer to be populated with the value of the item |
johnb | 0:99d701354221 | 154 | \returns true in the case that an item was returned |
johnb | 0:99d701354221 | 155 | false in the case that an item was not returned (list empty) |
johnb | 0:99d701354221 | 156 | */ |
johnb | 0:99d701354221 | 157 | bool pop( T* const p_item ); |
johnb | 0:99d701354221 | 158 | |
johnb | 0:99d701354221 | 159 | /** |
johnb | 0:99d701354221 | 160 | queue an item onto the end of the list |
johnb | 0:99d701354221 | 161 | |
johnb | 0:99d701354221 | 162 | \param p_item The item to be added to the list |
johnb | 0:99d701354221 | 163 | \returns true in the case that the item was added |
johnb | 0:99d701354221 | 164 | false in the case that the item was not added (no space) */ |
johnb | 0:99d701354221 | 165 | bool queue( const T p_item ); |
johnb | 0:99d701354221 | 166 | |
johnb | 0:99d701354221 | 167 | /** |
johnb | 0:99d701354221 | 168 | dequeue an item from the end of the list (item is removed and |
johnb | 0:99d701354221 | 169 | returned |
johnb | 0:99d701354221 | 170 | |
johnb | 0:99d701354221 | 171 | \param p_item Pointer to be populated with the value of the item |
johnb | 0:99d701354221 | 172 | \returns true in the case that an item was returned |
johnb | 0:99d701354221 | 173 | false in the case that an item was not returned (list empty) |
johnb | 0:99d701354221 | 174 | */ |
johnb | 0:99d701354221 | 175 | bool dequeue( T* const p_item ); |
johnb | 0:99d701354221 | 176 | |
johnb | 0:99d701354221 | 177 | /** Used to find out how many items are in the list |
johnb | 0:99d701354221 | 178 | |
johnb | 0:99d701354221 | 179 | \returns Number of used items, ranging from 0 to queueMax */ |
johnb | 0:99d701354221 | 180 | size_t used() const; |
johnb | 0:99d701354221 | 181 | |
johnb | 0:99d701354221 | 182 | /** Used to find out how many slots are still available in the list |
johnb | 0:99d701354221 | 183 | |
johnb | 0:99d701354221 | 184 | \returns Number of available slots, ranging from 0 to queueMax */ |
johnb | 0:99d701354221 | 185 | size_t available() const; |
johnb | 0:99d701354221 | 186 | |
johnb | 0:99d701354221 | 187 | /** Determine whether or not a particular item is in the list |
johnb | 0:99d701354221 | 188 | |
johnb | 0:99d701354221 | 189 | \param p_val Item to be matched against |
johnb | 0:99d701354221 | 190 | \returns true in the case that the item is found in the list |
johnb | 0:99d701354221 | 191 | false in the case that it is not found in the list |
johnb | 0:99d701354221 | 192 | */ |
johnb | 0:99d701354221 | 193 | bool inList( const T p_val ) const; |
johnb | 0:99d701354221 | 194 | |
johnb | 0:99d701354221 | 195 | /** Remove the entire contents of the list and return it back to |
johnb | 0:99d701354221 | 196 | an empty state */ |
johnb | 0:99d701354221 | 197 | void clear( void ); |
johnb | 0:99d701354221 | 198 | }; |
johnb | 0:99d701354221 | 199 | |
johnb | 0:99d701354221 | 200 | template < class T, size_t queueMax > |
johnb | 0:99d701354221 | 201 | FixedLengthList< T, queueMax >::FixedLengthList( void ) |
johnb | 0:99d701354221 | 202 | { |
johnb | 0:99d701354221 | 203 | clear(); |
johnb | 0:99d701354221 | 204 | } |
johnb | 0:99d701354221 | 205 | |
johnb | 0:99d701354221 | 206 | template < class T, size_t queueMax > |
johnb | 0:99d701354221 | 207 | FixedLengthList< T, queueMax >::FixedLengthList( const T* const p_items, size_t p_count ) { |
johnb | 0:99d701354221 | 208 | |
johnb | 0:99d701354221 | 209 | const T* src = p_items; |
johnb | 0:99d701354221 | 210 | |
johnb | 0:99d701354221 | 211 | /* Can only populate up to queueMax items */ |
johnb | 0:99d701354221 | 212 | size_t init_count = std::min( queueMax, p_count ); |
johnb | 0:99d701354221 | 213 | FixedLengthListItem<T>* prev = NULL; |
johnb | 0:99d701354221 | 214 | |
johnb | 0:99d701354221 | 215 | m_usedHead = NULL; |
johnb | 0:99d701354221 | 216 | m_usedTail = NULL; |
johnb | 0:99d701354221 | 217 | |
johnb | 0:99d701354221 | 218 | /* Initialise the list from p_items, building the forward links */ |
johnb | 0:99d701354221 | 219 | for( size_t i = 0; |
johnb | 0:99d701354221 | 220 | i < init_count; |
johnb | 0:99d701354221 | 221 | i++ ) |
johnb | 0:99d701354221 | 222 | { |
johnb | 0:99d701354221 | 223 | FixedLengthListItem<T>* current = &(m_items[i]); |
johnb | 0:99d701354221 | 224 | |
johnb | 0:99d701354221 | 225 | current->m_forward = NULL; |
johnb | 0:99d701354221 | 226 | current->m_item = *(src++); |
johnb | 0:99d701354221 | 227 | |
johnb | 0:99d701354221 | 228 | /* If there was a previous item in the list, set up its forward pointer, |
johnb | 0:99d701354221 | 229 | otherwise set up the list head */ |
johnb | 0:99d701354221 | 230 | if( prev != NULL ) { |
johnb | 0:99d701354221 | 231 | prev->m_forward = current; |
johnb | 0:99d701354221 | 232 | } else { |
johnb | 0:99d701354221 | 233 | m_usedHead = current; |
johnb | 0:99d701354221 | 234 | } |
johnb | 0:99d701354221 | 235 | |
johnb | 0:99d701354221 | 236 | m_usedTail = current; |
johnb | 0:99d701354221 | 237 | |
johnb | 0:99d701354221 | 238 | prev = current; |
johnb | 0:99d701354221 | 239 | } |
johnb | 0:99d701354221 | 240 | |
johnb | 0:99d701354221 | 241 | m_usedCount = init_count; |
johnb | 0:99d701354221 | 242 | |
johnb | 0:99d701354221 | 243 | m_freeHead = NULL; |
johnb | 0:99d701354221 | 244 | |
johnb | 0:99d701354221 | 245 | /* Any remaining items get moved into the free stack */ |
johnb | 0:99d701354221 | 246 | |
johnb | 0:99d701354221 | 247 | prev = NULL; |
johnb | 0:99d701354221 | 248 | for( size_t i = init_count; |
johnb | 0:99d701354221 | 249 | i < queueMax; |
johnb | 0:99d701354221 | 250 | i++ ) |
johnb | 0:99d701354221 | 251 | { |
johnb | 0:99d701354221 | 252 | FixedLengthListItem<T>* current = &(m_items[i]); |
johnb | 0:99d701354221 | 253 | current->m_forward = NULL; |
johnb | 0:99d701354221 | 254 | if( prev != NULL ) { |
johnb | 0:99d701354221 | 255 | prev->m_forward = current; |
johnb | 0:99d701354221 | 256 | } else { |
johnb | 0:99d701354221 | 257 | m_freeHead = current; |
johnb | 0:99d701354221 | 258 | } |
johnb | 0:99d701354221 | 259 | prev = current; |
johnb | 0:99d701354221 | 260 | } |
johnb | 0:99d701354221 | 261 | } |
johnb | 0:99d701354221 | 262 | |
johnb | 0:99d701354221 | 263 | template < class T, size_t queueMax > |
johnb | 0:99d701354221 | 264 | void FixedLengthList< T, queueMax >::clear( void ) |
johnb | 0:99d701354221 | 265 | { |
johnb | 0:99d701354221 | 266 | FixedLengthListItem<T>* p; |
johnb | 0:99d701354221 | 267 | size_t i; |
johnb | 0:99d701354221 | 268 | |
johnb | 0:99d701354221 | 269 | m_usedHead = NULL; |
johnb | 0:99d701354221 | 270 | m_usedTail = NULL; |
johnb | 0:99d701354221 | 271 | m_freeHead = m_items; |
johnb | 0:99d701354221 | 272 | |
johnb | 0:99d701354221 | 273 | /* Move all items into the free stack, setting up the forward links */ |
johnb | 0:99d701354221 | 274 | for( p = m_items, i = (queueMax-1); |
johnb | 0:99d701354221 | 275 | i > 0 ; |
johnb | 0:99d701354221 | 276 | i-- ) |
johnb | 0:99d701354221 | 277 | { |
johnb | 0:99d701354221 | 278 | FixedLengthListItem<T>* next = p+1; |
johnb | 0:99d701354221 | 279 | p->m_forward = next; |
johnb | 0:99d701354221 | 280 | p = next; |
johnb | 0:99d701354221 | 281 | } |
johnb | 0:99d701354221 | 282 | p->m_forward = NULL; |
johnb | 0:99d701354221 | 283 | m_usedCount = 0U; |
johnb | 0:99d701354221 | 284 | } |
johnb | 0:99d701354221 | 285 | |
johnb | 0:99d701354221 | 286 | template < class T, size_t queueMax > |
johnb | 0:99d701354221 | 287 | bool FixedLengthList< T, queueMax >::push( const T p_item ) |
johnb | 0:99d701354221 | 288 | { |
johnb | 0:99d701354221 | 289 | bool ret_val = false; |
johnb | 0:99d701354221 | 290 | |
johnb | 0:99d701354221 | 291 | /* Check that there's space in the list */ |
johnb | 0:99d701354221 | 292 | if( m_freeHead != NULL ) |
johnb | 0:99d701354221 | 293 | { |
johnb | 0:99d701354221 | 294 | FixedLengthListItem<T>* new_item = m_freeHead; |
johnb | 0:99d701354221 | 295 | |
johnb | 0:99d701354221 | 296 | /* Move the head pointer to the next free item in the list */ |
johnb | 0:99d701354221 | 297 | m_freeHead = new_item->m_forward; |
johnb | 0:99d701354221 | 298 | |
johnb | 0:99d701354221 | 299 | new_item->m_forward = m_usedHead; |
johnb | 0:99d701354221 | 300 | |
johnb | 0:99d701354221 | 301 | new_item->m_item = p_item; |
johnb | 0:99d701354221 | 302 | |
johnb | 0:99d701354221 | 303 | m_usedHead = new_item; |
johnb | 0:99d701354221 | 304 | |
johnb | 0:99d701354221 | 305 | if( m_usedTail == NULL ) |
johnb | 0:99d701354221 | 306 | { |
johnb | 0:99d701354221 | 307 | m_usedTail = new_item; |
johnb | 0:99d701354221 | 308 | } |
johnb | 0:99d701354221 | 309 | |
johnb | 0:99d701354221 | 310 | m_usedCount++; |
johnb | 0:99d701354221 | 311 | |
johnb | 0:99d701354221 | 312 | /* Indicate success */ |
johnb | 0:99d701354221 | 313 | ret_val = true; |
johnb | 0:99d701354221 | 314 | } |
johnb | 0:99d701354221 | 315 | |
johnb | 0:99d701354221 | 316 | return ret_val; |
johnb | 0:99d701354221 | 317 | } |
johnb | 0:99d701354221 | 318 | |
johnb | 0:99d701354221 | 319 | template < class T, size_t queueMax > |
johnb | 0:99d701354221 | 320 | bool FixedLengthList< T, queueMax >::queue( const T p_item ) |
johnb | 0:99d701354221 | 321 | { |
johnb | 0:99d701354221 | 322 | bool ret_val = false; |
johnb | 0:99d701354221 | 323 | |
johnb | 0:99d701354221 | 324 | /* Check that there's space in the list */ |
johnb | 0:99d701354221 | 325 | if( m_freeHead != NULL ) |
johnb | 0:99d701354221 | 326 | { |
johnb | 0:99d701354221 | 327 | /* Grab a free item */ |
johnb | 0:99d701354221 | 328 | FixedLengthListItem<T>* new_item = m_freeHead; |
johnb | 0:99d701354221 | 329 | |
johnb | 0:99d701354221 | 330 | /* Move the head pointer to the next free item in the list */ |
johnb | 0:99d701354221 | 331 | m_freeHead = m_freeHead->m_forward; |
johnb | 0:99d701354221 | 332 | |
johnb | 0:99d701354221 | 333 | /* Item is going at end of list - no forward link */ |
johnb | 0:99d701354221 | 334 | new_item->m_forward = NULL; |
johnb | 0:99d701354221 | 335 | |
johnb | 0:99d701354221 | 336 | new_item->m_item = p_item; |
johnb | 0:99d701354221 | 337 | |
johnb | 0:99d701354221 | 338 | /* Update the current tail item, if exists */ |
johnb | 0:99d701354221 | 339 | if( m_usedTail != NULL ) |
johnb | 0:99d701354221 | 340 | { |
johnb | 0:99d701354221 | 341 | m_usedTail->m_forward = new_item; |
johnb | 0:99d701354221 | 342 | } |
johnb | 0:99d701354221 | 343 | |
johnb | 0:99d701354221 | 344 | m_usedTail = new_item; |
johnb | 0:99d701354221 | 345 | |
johnb | 0:99d701354221 | 346 | if( m_usedHead == NULL ) |
johnb | 0:99d701354221 | 347 | { |
johnb | 0:99d701354221 | 348 | m_usedHead = new_item; |
johnb | 0:99d701354221 | 349 | } |
johnb | 0:99d701354221 | 350 | |
johnb | 0:99d701354221 | 351 | m_usedCount++; |
johnb | 0:99d701354221 | 352 | |
johnb | 0:99d701354221 | 353 | /* Indicate success */ |
johnb | 0:99d701354221 | 354 | ret_val = true; |
johnb | 0:99d701354221 | 355 | } |
johnb | 0:99d701354221 | 356 | |
johnb | 0:99d701354221 | 357 | return ret_val; |
johnb | 0:99d701354221 | 358 | } |
johnb | 0:99d701354221 | 359 | |
johnb | 0:99d701354221 | 360 | template < class T, size_t queueMax > |
johnb | 0:99d701354221 | 361 | bool FixedLengthList< T, queueMax >::pop( T* const p_item ) |
johnb | 0:99d701354221 | 362 | { |
johnb | 0:99d701354221 | 363 | bool ret_val = false; |
johnb | 0:99d701354221 | 364 | |
johnb | 0:99d701354221 | 365 | if( m_usedHead != NULL ) |
johnb | 0:99d701354221 | 366 | { |
johnb | 0:99d701354221 | 367 | FixedLengthListItem<T>* old_item = m_usedHead; |
johnb | 0:99d701354221 | 368 | |
johnb | 0:99d701354221 | 369 | *p_item = old_item->m_item; |
johnb | 0:99d701354221 | 370 | |
johnb | 0:99d701354221 | 371 | m_usedHead = old_item->m_forward; |
johnb | 0:99d701354221 | 372 | |
johnb | 0:99d701354221 | 373 | if( m_usedTail == old_item ) |
johnb | 0:99d701354221 | 374 | { |
johnb | 0:99d701354221 | 375 | m_usedTail = NULL; |
johnb | 0:99d701354221 | 376 | } |
johnb | 0:99d701354221 | 377 | |
johnb | 0:99d701354221 | 378 | old_item->m_forward = m_freeHead; |
johnb | 0:99d701354221 | 379 | |
johnb | 0:99d701354221 | 380 | m_freeHead = old_item; |
johnb | 0:99d701354221 | 381 | |
johnb | 0:99d701354221 | 382 | m_usedCount--; |
johnb | 0:99d701354221 | 383 | |
johnb | 0:99d701354221 | 384 | /* Indicate success */ |
johnb | 0:99d701354221 | 385 | ret_val = true; |
johnb | 0:99d701354221 | 386 | } |
johnb | 0:99d701354221 | 387 | |
johnb | 0:99d701354221 | 388 | return ret_val; |
johnb | 0:99d701354221 | 389 | } |
johnb | 0:99d701354221 | 390 | |
johnb | 0:99d701354221 | 391 | template < class T, size_t queueMax > |
johnb | 0:99d701354221 | 392 | bool FixedLengthList< T, queueMax >::dequeue( T* const p_item ) |
johnb | 0:99d701354221 | 393 | { |
johnb | 0:99d701354221 | 394 | bool ret_val = false; |
johnb | 0:99d701354221 | 395 | |
johnb | 0:99d701354221 | 396 | if( m_usedTail != NULL ) |
johnb | 0:99d701354221 | 397 | { |
johnb | 0:99d701354221 | 398 | FixedLengthListItem<T>* old_item = m_usedTail; |
johnb | 0:99d701354221 | 399 | |
johnb | 0:99d701354221 | 400 | *p_item = old_item->m_item; |
johnb | 0:99d701354221 | 401 | |
johnb | 0:99d701354221 | 402 | /* Item removed was only item in the list? */ |
johnb | 0:99d701354221 | 403 | if( m_usedHead == old_item ) |
johnb | 0:99d701354221 | 404 | { |
johnb | 0:99d701354221 | 405 | m_usedHead = NULL; |
johnb | 0:99d701354221 | 406 | m_usedTail = NULL; |
johnb | 0:99d701354221 | 407 | } else { |
johnb | 0:99d701354221 | 408 | FixedLengthListItem<T>* p = m_usedHead; |
johnb | 0:99d701354221 | 409 | |
johnb | 0:99d701354221 | 410 | /* Need to update the forward pointer of the |
johnb | 0:99d701354221 | 411 | item preceding the one which we've just removed. |
johnb | 0:99d701354221 | 412 | That item also becomes the new tail |
johnb | 0:99d701354221 | 413 | |
johnb | 0:99d701354221 | 414 | Iterate the list and find it */ |
johnb | 0:99d701354221 | 415 | while( p != NULL ) |
johnb | 0:99d701354221 | 416 | { |
johnb | 0:99d701354221 | 417 | if( p->m_forward == old_item ) |
johnb | 0:99d701354221 | 418 | { |
johnb | 0:99d701354221 | 419 | p->m_forward = NULL; |
johnb | 0:99d701354221 | 420 | m_usedTail = p; |
johnb | 0:99d701354221 | 421 | break; |
johnb | 0:99d701354221 | 422 | } else { |
johnb | 0:99d701354221 | 423 | p = p->m_forward; |
johnb | 0:99d701354221 | 424 | } |
johnb | 0:99d701354221 | 425 | } |
johnb | 0:99d701354221 | 426 | } |
johnb | 0:99d701354221 | 427 | |
johnb | 0:99d701354221 | 428 | /* Move item to free list */ |
johnb | 0:99d701354221 | 429 | old_item->m_forward = m_freeHead; |
johnb | 0:99d701354221 | 430 | m_freeHead = old_item; |
johnb | 0:99d701354221 | 431 | |
johnb | 0:99d701354221 | 432 | m_usedCount--; |
johnb | 0:99d701354221 | 433 | |
johnb | 0:99d701354221 | 434 | /* Indicate success */ |
johnb | 0:99d701354221 | 435 | ret_val = true; |
johnb | 0:99d701354221 | 436 | } |
johnb | 0:99d701354221 | 437 | |
johnb | 0:99d701354221 | 438 | return ret_val; |
johnb | 0:99d701354221 | 439 | } |
johnb | 0:99d701354221 | 440 | |
johnb | 0:99d701354221 | 441 | template < class T, size_t queueMax > |
johnb | 0:99d701354221 | 442 | size_t FixedLengthList< T, queueMax >::used() const |
johnb | 0:99d701354221 | 443 | { |
johnb | 0:99d701354221 | 444 | return m_usedCount; |
johnb | 0:99d701354221 | 445 | } |
johnb | 0:99d701354221 | 446 | |
johnb | 0:99d701354221 | 447 | template < class T, size_t queueMax > |
johnb | 0:99d701354221 | 448 | size_t FixedLengthList< T, queueMax >::available() const |
johnb | 0:99d701354221 | 449 | { |
johnb | 0:99d701354221 | 450 | return queueMax - m_usedCount; |
johnb | 0:99d701354221 | 451 | } |
johnb | 0:99d701354221 | 452 | |
johnb | 0:99d701354221 | 453 | template < class T, size_t queueMax > |
johnb | 0:99d701354221 | 454 | bool FixedLengthList< T, queueMax >::inList( const T p_val ) const |
johnb | 0:99d701354221 | 455 | { |
johnb | 0:99d701354221 | 456 | bool ret_val = false; |
johnb | 0:99d701354221 | 457 | FixedLengthListItem<T>* p = m_usedHead; |
johnb | 0:99d701354221 | 458 | |
johnb | 0:99d701354221 | 459 | /* Ordered iteration of the list checking for specified item */ |
johnb | 0:99d701354221 | 460 | while( p != NULL ) |
johnb | 0:99d701354221 | 461 | { |
johnb | 0:99d701354221 | 462 | if( p->m_item == p_val ) { |
johnb | 0:99d701354221 | 463 | /* Item found - flag and break out */ |
johnb | 0:99d701354221 | 464 | ret_val = true; |
johnb | 0:99d701354221 | 465 | break; |
johnb | 0:99d701354221 | 466 | } else { |
johnb | 0:99d701354221 | 467 | p = p->m_forward; |
johnb | 0:99d701354221 | 468 | } |
johnb | 0:99d701354221 | 469 | } |
johnb | 0:99d701354221 | 470 | |
johnb | 0:99d701354221 | 471 | return ret_val; |
johnb | 0:99d701354221 | 472 | } |
johnb | 0:99d701354221 | 473 | |
johnb | 0:99d701354221 | 474 | #endif |