| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | * Copyright (c) 2000-2022 Inria | ||
| 3 | * All rights reserved. | ||
| 4 | * | ||
| 5 | * Redistribution and use in source and binary forms, with or without | ||
| 6 | * modification, are permitted provided that the following conditions are met: | ||
| 7 | * | ||
| 8 | * * Redistributions of source code must retain the above copyright notice, | ||
| 9 | * this list of conditions and the following disclaimer. | ||
| 10 | * * Redistributions in binary form must reproduce the above copyright notice, | ||
| 11 | * this list of conditions and the following disclaimer in the documentation | ||
| 12 | * and/or other materials provided with the distribution. | ||
| 13 | * * Neither the name of the ALICE Project-Team nor the names of its | ||
| 14 | * contributors may be used to endorse or promote products derived from this | ||
| 15 | * software without specific prior written permission. | ||
| 16 | * | ||
| 17 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" | ||
| 18 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | ||
| 19 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | ||
| 20 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE | ||
| 21 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | ||
| 22 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | ||
| 23 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | ||
| 24 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | ||
| 25 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | ||
| 26 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | ||
| 27 | * POSSIBILITY OF SUCH DAMAGE. | ||
| 28 | * | ||
| 29 | * Contact: Bruno Levy | ||
| 30 | * | ||
| 31 | * https://www.inria.fr/fr/bruno-levy | ||
| 32 | * | ||
| 33 | * Inria, | ||
| 34 | * Domaine de Voluceau, | ||
| 35 | * 78150 Le Chesnay - Rocquencourt | ||
| 36 | * FRANCE | ||
| 37 | * | ||
| 38 | */ | ||
| 39 | |||
| 40 | #include <geogram/basic/packed_arrays.h> | ||
| 41 | #include <geogram/basic/logger.h> | ||
| 42 | #include <geogram/basic/string.h> | ||
| 43 | |||
| 44 | namespace { | ||
| 45 | |||
| 46 | using namespace GEO; | ||
| 47 | |||
| 48 | /** | ||
| 49 | * \brief Computes a percentage of a reference value | ||
| 50 | * \param[in] num the value to compute the percentage of | ||
| 51 | * \param[in] denom the reference value | ||
| 52 | * \return a formatted string that contains the \p num and its percentage | ||
| 53 | * of \p denom | ||
| 54 | */ | ||
| 55 | ✗ | std::string percent_str(index_t num, index_t denom) { | |
| 56 | ✗ | if(denom == 0) { | |
| 57 | ✗ | return String::to_string(num); | |
| 58 | } | ||
| 59 | ✗ | double x = double(num) / double(denom) * 100.0; | |
| 60 | ✗ | return String::to_string(num) + "(" + String::to_string(x) + "%)"; | |
| 61 | } | ||
| 62 | } | ||
| 63 | |||
| 64 | namespace GEO { | ||
| 65 | |||
| 66 | 82 | PackedArrays::PackedArrays() { | |
| 67 | 82 | nb_arrays_ = 0; | |
| 68 | 82 | Z1_block_size_ = 0; | |
| 69 | 82 | Z1_stride_ = 0; | |
| 70 | 82 | Z1_ = nullptr; | |
| 71 | 82 | ZV_ = nullptr; | |
| 72 | 82 | thread_safe_ = false; | |
| 73 | 82 | } | |
| 74 | |||
| 75 | ✗ | void PackedArrays::show_stats() { | |
| 76 | ✗ | index_t nb_items_in_Z1 = 0; | |
| 77 | ✗ | index_t nb_items_in_ZV = 0; | |
| 78 | ✗ | index_t nb_arrays_in_ZV = 0; | |
| 79 | ✗ | index_t nb_items = 0; | |
| 80 | ✗ | for(index_t i = 0; i < nb_arrays_; i++) { | |
| 81 | ✗ | index_t sz = array_size(i); | |
| 82 | ✗ | nb_items += sz; | |
| 83 | ✗ | if(sz > Z1_block_size_) { | |
| 84 | ✗ | nb_items_in_ZV += (sz - Z1_block_size_); | |
| 85 | ✗ | nb_arrays_in_ZV++; | |
| 86 | } | ||
| 87 | ✗ | nb_items_in_Z1 += std::min(sz, Z1_block_size_); | |
| 88 | } | ||
| 89 | |||
| 90 | ✗ | Logger::out("PArrays") | |
| 91 | ✗ | << "stats (nb_arrays=" << nb_arrays_ | |
| 92 | ✗ | << ", Z1 block size=" << Z1_block_size_ << ") " | |
| 93 | ✗ | << (static_mode() ? "static" : "dynamic") | |
| 94 | ✗ | << std::endl; | |
| 95 | |||
| 96 | ✗ | index_t Z1_total = nb_arrays_ * Z1_block_size_; | |
| 97 | |||
| 98 | ✗ | Logger::out("PArrays") | |
| 99 | << "Z1 filling:" | ||
| 100 | ✗ | << percent_str(nb_items_in_Z1, Z1_total) << std::endl; | |
| 101 | |||
| 102 | ✗ | if(!static_mode()) { | |
| 103 | ✗ | Logger::out("PArrays") | |
| 104 | ✗ | << "arrays in ZV:" << percent_str(nb_arrays_in_ZV, nb_arrays_) | |
| 105 | ✗ | << std::endl; | |
| 106 | ✗ | Logger::out("PArrays") | |
| 107 | ✗ | << "items in Z1:" << percent_str(nb_items_in_Z1, nb_items) | |
| 108 | ✗ | << std::endl; | |
| 109 | ✗ | Logger::out("PArrays") | |
| 110 | ✗ | << "items in ZV:" << percent_str(nb_items_in_ZV, nb_items) | |
| 111 | ✗ | << std::endl; | |
| 112 | } | ||
| 113 | ✗ | } | |
| 114 | |||
| 115 | 82 | PackedArrays::~PackedArrays() { | |
| 116 | 82 | clear(); | |
| 117 | 82 | } | |
| 118 | |||
| 119 | 149 | void PackedArrays::clear() { | |
| 120 |
2/2✓ Branch 0 taken 67 times.
✓ Branch 1 taken 82 times.
|
149 | if(ZV_ != nullptr) { |
| 121 |
2/2✓ Branch 0 taken 99014 times.
✓ Branch 1 taken 67 times.
|
99081 | for(index_t i = 0; i < nb_arrays_; i++) { |
| 122 | 99014 | free(ZV_[i]); | |
| 123 | } | ||
| 124 | 67 | free(ZV_); | |
| 125 | 67 | ZV_ = nullptr; | |
| 126 | } | ||
| 127 | 149 | nb_arrays_ = 0; | |
| 128 | 149 | Z1_block_size_ = 0; | |
| 129 | 149 | Z1_stride_ = 0; | |
| 130 | 149 | free(Z1_); | |
| 131 | 149 | Z1_ = nullptr; | |
| 132 | 149 | } | |
| 133 | |||
| 134 | 68 | void PackedArrays::set_thread_safe(bool x) { | |
| 135 | 68 | thread_safe_ = x; | |
| 136 |
1/2✓ Branch 0 taken 68 times.
✗ Branch 1 not taken.
|
68 | if(x) { |
| 137 | 68 | Z1_spinlocks_.resize(nb_arrays_); | |
| 138 | } else { | ||
| 139 | ✗ | Z1_spinlocks_.clear(); | |
| 140 | } | ||
| 141 | 68 | } | |
| 142 | |||
| 143 | 67 | void PackedArrays::init( | |
| 144 | index_t nb_arrays, | ||
| 145 | index_t Z1_block_size, | ||
| 146 | bool static_mode | ||
| 147 | ) { | ||
| 148 | 67 | clear(); | |
| 149 | 67 | nb_arrays_ = nb_arrays; | |
| 150 | 67 | Z1_block_size_ = Z1_block_size; | |
| 151 | 67 | Z1_stride_ = Z1_block_size_ + 1; // +1 for storing array size. | |
| 152 | 67 | Z1_ = (index_t*) calloc( | |
| 153 | 67 | nb_arrays_, sizeof(index_t) * Z1_stride_ | |
| 154 | ); | ||
| 155 |
1/2✓ Branch 0 taken 67 times.
✗ Branch 1 not taken.
|
67 | if(!static_mode) { |
| 156 | 67 | ZV_ = (index_t**) calloc( | |
| 157 | 67 | nb_arrays_, sizeof(index_t*) | |
| 158 | ); | ||
| 159 | } | ||
| 160 |
1/2✓ Branch 0 taken 67 times.
✗ Branch 1 not taken.
|
67 | if(thread_safe_) { |
| 161 | 67 | Z1_spinlocks_.resize(nb_arrays_); | |
| 162 | } | ||
| 163 | 67 | } | |
| 164 | |||
| 165 | 10875459 | void PackedArrays::get_array( | |
| 166 | index_t array_index, index_t* array, bool lock | ||
| 167 | ) const { | ||
| 168 |
1/6✗ Branch 0 not taken.
✓ Branch 1 taken 10875459 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
|
10875459 | geo_debug_assert(array_index < nb_arrays_); |
| 169 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 10875459 times.
|
10875459 | if(lock) { |
| 170 | ✗ | lock_array(array_index); | |
| 171 | } | ||
| 172 | 10875459 | const index_t* array_base = Z1_ + array_index * Z1_stride_; | |
| 173 | 10875459 | index_t array_size = *array_base; | |
| 174 | 10875459 | index_t nb = array_size; | |
| 175 | 10875459 | array_base++; | |
| 176 | 10875459 | index_t nb_in_block = std::min(nb, Z1_block_size_); | |
| 177 | 10875459 | Memory::copy(array, array_base, sizeof(index_t) * nb_in_block); | |
| 178 |
2/2✓ Branch 0 taken 720796 times.
✓ Branch 1 taken 10154663 times.
|
10875459 | if(nb > nb_in_block) { |
| 179 | 720796 | nb -= nb_in_block; | |
| 180 | 720796 | array += nb_in_block; | |
| 181 | 720796 | array_base = ZV_[array_index]; | |
| 182 | 720796 | Memory::copy(array, array_base, sizeof(index_t) * nb); | |
| 183 | } | ||
| 184 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 10875459 times.
|
10875459 | if(lock) { |
| 185 | ✗ | unlock_array(array_index); | |
| 186 | } | ||
| 187 | 10875459 | } | |
| 188 | |||
| 189 | 1688236 | void PackedArrays::set_array( | |
| 190 | index_t array_index, | ||
| 191 | index_t array_size, const index_t* array, | ||
| 192 | bool lock | ||
| 193 | ) { | ||
| 194 |
1/6✗ Branch 0 not taken.
✓ Branch 1 taken 1688236 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
|
1688236 | geo_debug_assert(array_index < nb_arrays_); |
| 195 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1688236 times.
|
1688236 | if(lock) { |
| 196 | ✗ | lock_array(array_index); | |
| 197 | } | ||
| 198 | 1688236 | index_t* array_base = Z1_ + array_index * Z1_stride_; | |
| 199 | 1688236 | index_t old_array_size = *array_base; | |
| 200 | 1688236 | array_base++; | |
| 201 |
2/2✓ Branch 0 taken 33510 times.
✓ Branch 1 taken 1654726 times.
|
1688236 | if(array_size != old_array_size) { |
| 202 |
1/2✓ Branch 1 taken 33510 times.
✗ Branch 2 not taken.
|
33510 | resize_array(array_index, array_size, false); |
| 203 | } | ||
| 204 | 1688236 | index_t nb = array_size; | |
| 205 | 1688236 | index_t nb_in_block = std::min(nb, Z1_block_size_); | |
| 206 | 1688236 | Memory::copy(array_base, array, sizeof(index_t) * nb_in_block); | |
| 207 |
2/2✓ Branch 0 taken 72422 times.
✓ Branch 1 taken 1615814 times.
|
1688236 | if(nb > nb_in_block) { |
| 208 | 72422 | nb -= nb_in_block; | |
| 209 | 72422 | array += nb_in_block; | |
| 210 | 72422 | array_base = ZV_[array_index]; | |
| 211 | 72422 | Memory::copy(array_base, array, sizeof(index_t) * nb); | |
| 212 | } | ||
| 213 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1688236 times.
|
1688236 | if(lock) { |
| 214 | ✗ | unlock_array(array_index); | |
| 215 | } | ||
| 216 | 1688236 | } | |
| 217 | |||
| 218 | 132524 | void PackedArrays::resize_array( | |
| 219 | index_t array_index, index_t array_size, bool lock | ||
| 220 | ) { | ||
| 221 |
1/6✗ Branch 0 not taken.
✓ Branch 1 taken 132524 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
|
132524 | geo_debug_assert(array_index < nb_arrays_); |
| 222 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 132524 times.
|
132524 | if(lock) { |
| 223 | ✗ | lock_array(array_index); | |
| 224 | } | ||
| 225 | 132524 | index_t* array_base = Z1_ + array_index * Z1_stride_; | |
| 226 | 132524 | index_t old_array_size = *array_base; | |
| 227 |
1/2✓ Branch 0 taken 132524 times.
✗ Branch 1 not taken.
|
132524 | if(old_array_size != array_size) { |
| 228 | 132524 | *array_base = array_size; | |
| 229 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 132524 times.
|
132524 | if(static_mode()) { |
| 230 | ✗ | geo_assert(array_size <= Z1_block_size_); | |
| 231 | } else { | ||
| 232 | 99202 | index_t nb_in_ZV = | |
| 233 |
2/2✓ Branch 0 taken 33322 times.
✓ Branch 1 taken 99202 times.
|
132524 | (array_size > Z1_block_size_) ? |
| 234 | 33322 | array_size - Z1_block_size_ : 0; | |
| 235 | 132524 | ZV_[array_index] = (index_t*) realloc( | |
| 236 | 132524 | ZV_[array_index], sizeof(index_t) * nb_in_ZV | |
| 237 | ); | ||
| 238 | } | ||
| 239 | } | ||
| 240 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 132524 times.
|
132524 | if(lock) { |
| 241 | ✗ | unlock_array(array_index); | |
| 242 | } | ||
| 243 | 132524 | } | |
| 244 | } | ||
| 245 |