Line data    Source code

       1             : /*
       2             :    This program is free software: you can redistribute it and/or modify
       3             :    it under the terms of the GNU General Public License as published by
       4             :    the Free Software Foundation, either version 3 of the License, or
       5             :    (at your option) any later version.
       6             : 
       7             :    This program is distributed in the hope that it will be useful,
       8             :    but WITHOUT ANY WARRANTY; without even the implied warranty of
       9             :    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      10             :    GNU General Public License for more details.
      11             : 
      12             :    You should have received a copy of the GNU General Public License
      13             :    along with this program.  If not, see <http://www.gnu.org/licenses/>.
      14             :  */
      15             : 
      16             : /*
      17             :  * ExpandingArray class description
      18             :  *
      19             :  * ExpandingArrayGeneric implements most of the required functionality and is type agnostic allowing smaller overall code size
      20             :  * ExpandingArray<T> is the template and implements the small number of type specific methods
      21             :  *
      22             :  * Elements are organised into "chunks" with each chunk holding "chunk_size" elements
      23             :  * The "chunk_ptrs" array holds pointers to all allocated chunks
      24             :  *
      25             :  * The "expand" function allows expanding the array by a specified number of chunks
      26             :  * The "expand_to_hold" function expands the array (if necessary) to hold at least the specified number of elements
      27             :  *
      28             :  * When the array is expanded up to two memory allocations are required:
      29             :  *    1. if the chunk_ptrs array (which holds points to all allocated chunks) is full, this array will be re-allocated.
      30             :  *       During this operation a new copy of the chunk_ptr array will be created with "chunk_ptr_increment" more rows,
      31             :  *       the old array's data will be copied to the new array and finally the old array will be freed.
      32             :  *    2. a new chunk will be allocated and a pointer to this new chunk will be added to the chunk_ptrs array
      33             :  *
      34             :  * Warnings:
      35             :  *    1. memset, memcpy, memcmp cannot be used because the individual elements are not guaranteed to be next to each other in memory
      36             :  *    2. operator[] functions do not perform any range checking so max_items() should be used when necessary to avoid out-of-bound memory access
      37             :  *    3. elements_per_chunk (provided in constructor) should be a factor of 2 (i.e. 16, 32, 64) for best performance
      38             :  */
      39             : 
      40             : #pragma once
      41             : 
      42             : #include <AP_Common/AP_Common.h>
      43             : 
      44             : class AP_ExpandingArrayGeneric
      45             : {
      46             : public:
      47             : 
      48        2154 :     AP_ExpandingArrayGeneric(uint16_t element_size, uint16_t elements_per_chunk) :
      49        2154 :         elem_size(element_size),
      50        2154 :         chunk_size(elements_per_chunk)
      51        2154 :     {}
      52             : 
      53             :     ~AP_ExpandingArrayGeneric(void);
      54             : 
      55             :     /* Do not allow copies */
      56             :     CLASS_NO_COPY(AP_ExpandingArrayGeneric);
      57             : 
      58             :     // current maximum number of items (using expand may increase this)
      59         540 :     uint16_t max_items() const { return chunk_size * chunk_count; }
      60             : 
      61             :     // expand the array by specified number of chunks, returns true on success
      62             :     bool expand(uint16_t num_chunks = 1);
      63             : 
      64             :     // expand to hold at least num_items
      65             :     bool expand_to_hold(uint16_t num_items);
      66             : 
      67             : protected:
      68             : 
      69             :     const uint16_t elem_size;   // number of bytes for each element
      70             :     const uint16_t chunk_size;  // the number of T elements in each chunk
      71             :     const uint16_t chunk_ptr_increment = 32;    // chunk_ptrs array is grown by this many elements each time it fills
      72             : 
      73             :     typedef uint8_t* chunk_ptr_t;   // pointer to a chunk
      74             : 
      75             :     chunk_ptr_t *chunk_ptrs;    // array of pointers to allocated chunks
      76             :     uint16_t chunk_count_max;   // number of elements in chunk_ptrs array
      77             :     uint16_t chunk_count;       // number of allocated chunks
      78             : };
      79             : 
      80             : template <typename T>
      81             : class AP_ExpandingArray : public AP_ExpandingArrayGeneric
      82             : {
      83             : public:
      84             : 
      85        2154 :     AP_ExpandingArray(uint16_t elements_per_chunk) :
      86        2154 :         AP_ExpandingArrayGeneric(sizeof(T), elements_per_chunk)
      87        2154 :     {}
      88             : 
      89             :     /* Do not allow copies */
      90             :     CLASS_NO_COPY(AP_ExpandingArray);
      91             : 
      92             :     // allow use as an array for assigning to elements. no bounds checking is performed
      93        8251 :     T &operator[](uint16_t i)
      94             :     {
      95        8251 :         const uint16_t chunk_num = i / chunk_size;
      96        8251 :         const uint16_t chunk_index = (i % chunk_size);
      97             :         #pragma GCC diagnostic push
      98             :         #pragma GCC diagnostic ignored "-Wcast-align"
      99        8251 :         T *el_array = (T *)chunk_ptrs[chunk_num];
     100             :         #pragma GCC diagnostic pop
     101        8251 :         return el_array[chunk_index];
     102             :     }
     103             : 
     104             :     // allow use as an array for accessing elements. no bounds checking is performed
     105        3146 :     const T &operator[](uint16_t i) const
     106             :     {
     107        3146 :         const uint16_t chunk_num = i / chunk_size;
     108        3146 :         const uint16_t chunk_index = (i % chunk_size);
     109             :         #pragma GCC diagnostic push
     110             :         #pragma GCC diagnostic ignored "-Wcast-align"
     111        3146 :         const T *el_array = (const T *)chunk_ptrs[chunk_num];
     112             :         #pragma GCC diagnostic pop
     113        3146 :         return el_array[chunk_index];
     114             :     }
     115             : };