| 1 | // varray.hpp, created on 04.11.2008 by Sebastian Mies
|
---|
| 2 | //
|
---|
| 3 | // [The FreeBSD Licence]
|
---|
| 4 | // Copyright (c) 2008
|
---|
| 5 | // Sebastian Mies, Institute of Telematics, UniversitÀt Karlsruhe
|
---|
| 6 | // All rights reserved.
|
---|
| 7 | //
|
---|
| 8 | // Redistribution and use in source and binary forms, with or without
|
---|
| 9 | // modification, are permitted provided that the following conditions are
|
---|
| 10 | // met:
|
---|
| 11 | //
|
---|
| 12 | // * Redistributions of source code must retain the above copyright notice,
|
---|
| 13 | // this list of conditions and the following disclaimer.
|
---|
| 14 | // * Redistributions in binary form must reproduce the above copyright
|
---|
| 15 | // notice, this list of conditions and the following disclaimer in the
|
---|
| 16 | // documentation and/or other materials provided with the distribution.
|
---|
| 17 | // * Neither the name of the author nor the names of its contributors may be
|
---|
| 18 | // used to endorse or promote products derived from this software without
|
---|
| 19 | // specific prior written permission.
|
---|
| 20 | //
|
---|
| 21 | // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
|
---|
| 22 | // IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
|
---|
| 23 | // THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
|
---|
| 24 | // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
|
---|
| 25 | // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
|
---|
| 26 | // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
|
---|
| 27 | // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
|
---|
| 28 | // OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
|
---|
| 29 | // WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
|
---|
| 30 | // OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
|
---|
| 31 | // ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
---|
| 32 | //
|
---|
| 33 | #ifndef VARRAY_HPP_
|
---|
| 34 | #define VARRAY_HPP_
|
---|
| 35 |
|
---|
| 36 | #include "detail/helper.hpp"
|
---|
| 37 |
|
---|
| 38 | #include <memory.h>
|
---|
| 39 |
|
---|
| 40 | #include <boost/mpl/if.hpp>
|
---|
| 41 | #include <boost/mpl/placeholders.hpp>
|
---|
| 42 |
|
---|
| 43 | /**
|
---|
| 44 | * This class implements a variable or static sized bit container.
|
---|
| 45 | * The difference to other array classes is that this class morphs between
|
---|
| 46 | * static and dynamic object allocation.
|
---|
| 47 | *
|
---|
| 48 | * @author Sebastian Mies
|
---|
| 49 | */
|
---|
| 50 | template<class item_type, size_t _size = 0, typename size_type = size_t>
|
---|
| 51 | class varray {
|
---|
| 52 | private:
|
---|
| 53 | typedef varray<item_type, _size, size_type> _varray;
|
---|
| 54 |
|
---|
| 55 | /* dynamic array */
|
---|
| 56 | class dynamic_array {
|
---|
| 57 | private:
|
---|
| 58 | /* array structure */
|
---|
| 59 | typedef struct __array {
|
---|
| 60 | size_type size;
|
---|
| 61 | item_type arr[];
|
---|
| 62 | } __array;
|
---|
| 63 | __array *arr;
|
---|
| 64 |
|
---|
| 65 | /* returns the underlaying array size from a given length */
|
---|
| 66 | finline size_t array_size(size_t new_size) const {
|
---|
| 67 | return (new_size / (sizeof(item_type) * 8)) + (((new_size
|
---|
| 68 | % (sizeof(item_type) * 8)) == 0) ? 0 : 1);
|
---|
| 69 | }
|
---|
| 70 |
|
---|
| 71 | public:
|
---|
| 72 | finline dynamic_array() {
|
---|
| 73 | arr = 0;
|
---|
| 74 | }
|
---|
| 75 |
|
---|
| 76 | finline ~dynamic_array() {
|
---|
| 77 | if (arr != 0) free(arr);
|
---|
| 78 | }
|
---|
| 79 |
|
---|
| 80 | /* return size in bits */
|
---|
| 81 | finline size_type size() const {
|
---|
| 82 | return (arr == 0) ? 0 : arr->size;
|
---|
| 83 | }
|
---|
| 84 |
|
---|
| 85 | /* returns the underlaying array size */
|
---|
| 86 | finline size_t array_size() const {
|
---|
| 87 | return array_size(size());
|
---|
| 88 | }
|
---|
| 89 |
|
---|
| 90 | /* set size in bits */
|
---|
| 91 | finline void resize(size_type new_size) {
|
---|
| 92 | size_t old_arr_size = array_size();
|
---|
| 93 | size_t new_arr_size = array_size(new_size);
|
---|
| 94 | if (old_arr_size != new_arr_size) {
|
---|
| 95 | size_t nbsize = sizeof(__array ) + new_arr_size
|
---|
| 96 | * sizeof(item_type);
|
---|
| 97 | size_t obsize = sizeof(__array ) + old_arr_size
|
---|
| 98 | * sizeof(item_type);
|
---|
| 99 | __array *new_array = (__array *) malloc(nbsize);
|
---|
| 100 | if (arr != 0) {
|
---|
| 101 | size_t csize = std::min(nbsize, obsize);
|
---|
| 102 | memcpy(new_array, arr, csize);
|
---|
| 103 | if (nbsize > obsize) memset(
|
---|
| 104 | ((uint8_t*) new_array) + obsize, 0, nbsize
|
---|
| 105 | - obsize);
|
---|
| 106 | free(arr);
|
---|
| 107 | }
|
---|
| 108 | arr = new_array;
|
---|
| 109 | }
|
---|
| 110 | arr->size = new_size;
|
---|
| 111 | }
|
---|
| 112 |
|
---|
| 113 | /* return the array */
|
---|
| 114 | finline item_type* array() const {
|
---|
| 115 | return (item_type*) &arr->arr;
|
---|
| 116 | }
|
---|
| 117 |
|
---|
| 118 | finline int get_memory_consumption() const {
|
---|
| 119 | return array_size() * sizeof(item_type) + sizeof(__array) +
|
---|
| 120 | sizeof(void*);
|
---|
| 121 | }
|
---|
| 122 | };
|
---|
| 123 |
|
---|
| 124 | /* static array */
|
---|
| 125 | class static_array {
|
---|
| 126 | private:
|
---|
| 127 | static const size_t _array_size = (_size / (sizeof(item_type) * 8))
|
---|
| 128 | + (((_size % (sizeof(item_type) * 8)) == 0) ? 0 : 1);
|
---|
| 129 | item_type arr[_array_size];
|
---|
| 130 |
|
---|
| 131 | public:
|
---|
| 132 | /* returns the number of bits in this array */
|
---|
| 133 | finline size_type size() const {
|
---|
| 134 | return _size;
|
---|
| 135 | }
|
---|
| 136 |
|
---|
| 137 | /* returns the underlaying array size */
|
---|
| 138 | finline size_t array_size() const {
|
---|
| 139 | return _array_size;
|
---|
| 140 | }
|
---|
| 141 |
|
---|
| 142 | /* resizes the array */
|
---|
| 143 | finline void resize(size_type new_size) {
|
---|
| 144 | }
|
---|
| 145 |
|
---|
| 146 | /* return the array */
|
---|
| 147 | finline item_type* array() const {
|
---|
| 148 | return (item_type*) &arr;
|
---|
| 149 | }
|
---|
| 150 |
|
---|
| 151 | finline int get_memory_consumption() const {
|
---|
| 152 | return _array_size * sizeof(item_type);
|
---|
| 153 | }
|
---|
| 154 | };
|
---|
| 155 |
|
---|
| 156 | /* selection of static or dynamic array */
|
---|
| 157 | typename boost::mpl::if_<boost::mpl::bool_<_size == 0>,
|
---|
| 158 | dynamic_array, static_array>::type _array;
|
---|
| 159 |
|
---|
| 160 | public:
|
---|
| 161 | finline bool is_static() const {
|
---|
| 162 | return (_size != 0);
|
---|
| 163 | }
|
---|
| 164 |
|
---|
| 165 | finline bool is_dynamic() const {
|
---|
| 166 | return !is_static();
|
---|
| 167 | }
|
---|
| 168 |
|
---|
| 169 | finline size_type size() const {
|
---|
| 170 | return _array.size();
|
---|
| 171 | }
|
---|
| 172 |
|
---|
| 173 | finline size_t array_size() const {
|
---|
| 174 | return _array.array_size();
|
---|
| 175 | }
|
---|
| 176 |
|
---|
| 177 | finline void resize(size_type newSize) {
|
---|
| 178 | _array.resize(newSize);
|
---|
| 179 | }
|
---|
| 180 |
|
---|
| 181 | finline item_type* array() {
|
---|
| 182 | return _array.array();
|
---|
| 183 | }
|
---|
| 184 |
|
---|
| 185 | finline const item_type* array_const() const {
|
---|
| 186 | return _array.array();
|
---|
| 187 | }
|
---|
| 188 |
|
---|
| 189 | finline operator item_type*() {
|
---|
| 190 | return _array();
|
---|
| 191 | }
|
---|
| 192 |
|
---|
| 193 | finline int get_memory_consumption() const {
|
---|
| 194 | return _array.get_memory_consumption();
|
---|
| 195 | }
|
---|
| 196 |
|
---|
| 197 | finline item_type& operator[] ( size_type index ) {
|
---|
| 198 | return array()[index];
|
---|
| 199 | }
|
---|
| 200 | };
|
---|
| 201 |
|
---|
| 202 | #endif /* VARRAY_HPP_ */
|
---|