1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the class library */ 4 /* SoPlex --- the Sequential object-oriented simPlex. */ 5 /* */ 6 /* Copyright (c) 1996-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SoPlex; see the file LICENSE. If not email to soplex@zib.de. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file dataarray.h 26 * @brief Save arrays of data objects. 27 */ 28 #ifndef _DATAARRAY_H_ 29 #define _DATAARRAY_H_ 30 31 #include <assert.h> 32 #include <stddef.h> 33 #include <string.h> 34 #include <iostream> 35 #include <type_traits> 36 37 #include "soplex/spxdefines.h" 38 #include "soplex/spxalloc.h" 39 #include "soplex/spxid.h" 40 41 namespace soplex 42 { 43 /**@brief Safe arrays of data objects. 44 @ingroup Elementary 45 46 Class DataArray provides safe arrays of \ref DataObjects. For general 47 C++ objects (in contrast to data objects) class Array is provided which 48 manages memory in a C++ compliant way. 49 50 The elements of an instance of DataArray can be accessed just like 51 ordinary C++ array elements by means of the index operator[](). Safety is 52 provided by 53 54 - automatic memory management in constructor and destructor 55 preventing memory leaks 56 - checking of array bounds when accessing elements with the 57 indexing operator[]() (only when compiled without \c -DNDEBUG). 58 59 Moreover, #DataArray%s may easily be extended by #insert%ing or #append%ing 60 elements to the DataArray or shrunken by \ref remove() "removing" elements. 61 Method reSize(int n) resets the DataArray%s length to \p n thereby possibly 62 appending elements or truncating the DataArray to the required size. 63 64 A DataArray may be used as arguments for standard C functions requiring 65 pointers through the use of get_ptr() and get_const_ptr(). 66 67 Internally, a DataArray object allocates a block of memory that fits up 68 to max() elements, only size() of them are used. This makes extension 69 and shrinking methods perform better. 70 71 @see Array, \ref DataObjects "Data Objects" 72 */ 73 template < class T > 74 class DataArray 75 { 76 static_assert(std::is_trivially_copyable<T>::value, 77 "Only trivially copyable types are allowed with DataArray, since it does memcopy"); 78 private: 79 int thesize; ///< number of used elements in array data 80 int themax; ///< the length of array data and 81 T* data; ///< the array of elements 82 83 protected: 84 /** When a DataArray is reSize()%d to more than max() elements, the 85 new value for max() is not just set to the new size but rather to 86 \p memFactor * \p size. This makes #reSize%ing perform better in codes 87 where a DataArray is extended often by a small number of elements 88 only. 89 */ 90 Real memFactor; ///< memory extension factor. 91 92 public: 93 94 /// reference \p n 'th element. 95 T& operator[](int n) 96 { 97 assert(n >= 0); 98 assert(n < thesize); 99 return data[n]; 100 } 101 /// reference \p n 'th const element. 102 const T& operator[](int n) const 103 { 104 assert(n >= 0); 105 assert(n < thesize); 106 return data[n]; 107 } 108 109 /// reference last element. 110 T& last() 111 { 112 assert(thesize > 0); 113 return data[thesize - 1]; 114 } 115 /// reference last const element. 116 const T& last() const 117 { 118 assert(thesize > 0); 119 return data[thesize - 1]; 120 } 121 122 /// get a C pointer to the data. 123 T* get_ptr() 124 { 125 return data; 126 } 127 /// get a const C pointer to the data. 128 const T* get_const_ptr() const 129 { 130 return data; 131 } 132 133 /// append element \p t. 134 void append(const T& t) 135 { 136 insert(thesize, 1, &t); 137 } 138 /// append \p n elements with value \p t. 139 void append(int n, const T& t) 140 { 141 insert(thesize, n, t); 142 } 143 /// append \p n elements from \p t. 144 void append(int n, const T t[]) 145 { 146 insert(thesize, n, t); 147 } 148 /// append all elements from \p t. 149 void append(const DataArray<T>& t) 150 { 151 insert(thesize, t); 152 } 153 154 /// insert \p n uninitialized elements before \p i 'th element. 155 void insert(int i, int n) 156 { 157 int j = thesize; 158 159 assert(i >= 0); 160 assert(n >= 0); 161 162 reSize(thesize + n); 163 164 /// move \p n elements in memory from insert position \p i to the back 165 if(j > i) 166 memmove(&(data[i + n]), &(data[i]), (unsigned int)(j - i) * sizeof(T)); 167 } 168 169 /// insert \p n elements with value \p t before \p i 'the element. 170 void insert(int i, int n, const T& t) 171 { 172 if(n > 0) 173 { 174 insert(i, n); 175 176 for(int j = 0; j < n; j++) 177 data[i + j] = t; 178 } 179 } 180 181 /// insert \p n elements from \p t before \p i 'the element. 182 void insert(int i, int n, const T t[]) 183 { 184 if(n > 0) 185 { 186 insert(i, n); 187 memcpy(&(data[i]), t, (unsigned int) n * sizeof(T)); 188 } 189 } 190 191 /// insert all elements from \p t before \p i 'th element. 192 void insert(int i, const DataArray<T>& t) 193 { 194 if(t.size()) 195 { 196 insert(i, t.size()); 197 memcpy(&(data[i]), t.data, (unsigned int)t.size() * sizeof(T)); 198 } 199 } 200 201 /// remove \p m elements starting at \p n. 202 void remove(int n = 0, int m = 1) 203 { 204 assert(n < size() && n >= 0); 205 206 /* use memmove instead of memcopy because the destination and the source might overlap */ 207 if(n + m < size()) 208 memmove(&(data[n]), &(data[n + m]), (unsigned int)(size() - (n + m)) * sizeof(T)); 209 else 210 m = size() - n; 211 212 thesize -= m; 213 } 214 /// remove \p m last elements. 215 void removeLast(int m = 1) 216 { 217 assert(m <= size() && m >= 0); 218 thesize -= m; 219 } 220 /// remove all elements. 221 void clear() 222 { 223 thesize = 0; 224 } 225 226 /// return nr. of elements. 227 int size() const 228 { 229 return thesize; 230 } 231 232 /// reset size to \p newsize. 233 /** Resizing a DataArray to less than the previous size, involves 234 discarding its last elements. Resizing to a larger value involves 235 adding uninitialized elements (similar to append()). If neccessary, 236 also memory will be reallocated. 237 @param newsize the new number of elements the array can hold. 238 */ 239 void reSize(int newsize) 240 { 241 assert(memFactor >= 1); 242 243 if(newsize > themax) 244 reMax(int(memFactor * newsize), newsize); 245 else if(newsize < 0) 246 thesize = 0; 247 else 248 thesize = newsize; 249 } 250 251 /// return maximum number of elements. 252 /** Even though the DataArray currently holds no more than size() 253 elements, up to max() elements could be added without need to 254 reallocated free store. 255 */ 256 int max() const 257 { 258 return themax; 259 } 260 261 /// reset maximum number of elements. 262 /** The value of max() is reset to \p newMax thereby setting size() 263 to \p newSize. However, if \p newSize has a value \c < \c 0 (as the 264 default argument does) size() remains unchanged and max() is set 265 to MIN(size(), newMax). Hence, calling reMax() without the 266 default arguments, will reduce the memory consumption to a minimum. 267 In no instance max() will be set to a value less than 1 (even if 268 specified). 269 270 */ 271 void reMax(int newMax = 1, int newSize = -1) 272 { 273 if(newSize >= 0) 274 thesize = newSize; 275 276 if(newMax < newSize) 277 newMax = newSize; 278 279 if(newMax < 1) 280 newMax = 1; 281 282 if(newMax == themax) 283 return; 284 285 themax = newMax; 286 287 if(thesize <= 0) 288 { 289 /* no data needs to be copied so do a clean free and alloc */ 290 spx_free(data); 291 spx_alloc(data, themax); 292 } 293 else 294 spx_realloc(data, themax); 295 } 296 /// assignment operator 297 DataArray& operator=(const DataArray& rhs) 298 { 299 if(this != &rhs) 300 { 301 reSize(rhs.size()); 302 memcpy(data, rhs.data, (unsigned int) size() * sizeof(T)); 303 304 assert(isConsistent()); 305 } 306 307 return *this; 308 } 309 310 /// consistency check 311 bool isConsistent() const 312 { 313 #ifdef ENABLE_CONSISTENCY_CHECKS 314 315 if((data == 0) 316 || (themax < 1) 317 || (themax < thesize) 318 || (thesize < 0) 319 || (memFactor < 1.0)) 320 return SPX_MSG_INCONSISTENT("DataArray"); 321 322 #endif 323 324 return true; 325 } 326 327 /// copy constructor 328 DataArray(const DataArray& old) 329 : thesize(old.thesize) 330 , themax(old.themax) 331 , data(0) 332 , memFactor(old.memFactor) 333 { 334 spx_alloc(data, max()); 335 336 assert(thesize >= 0); 337 338 if(thesize) 339 memcpy(data, old.data, (unsigned int)thesize * sizeof(T)); 340 341 assert(isConsistent()); 342 } 343 344 /// default constructor. 345 /** The constructor allocates an Array containing \p size uninitialized 346 elements. The internal array is allocated to have \p max nonzeros, 347 and the memory extension factor is set to \p fac. 348 349 @param p_size number of unitialised elements. 350 @param p_max maximum number of elements the array can hold. 351 @param p_fac value for memFactor. 352 */ 353 explicit DataArray(int p_size = 0, int p_max = 0, Real p_fac = 1.2) 354 : data(0) 355 , memFactor(p_fac) 356 { 357 thesize = (p_size < 0) ? 0 : p_size; 358 359 if(p_max > thesize) 360 themax = p_max; 361 else 362 themax = (thesize == 0) ? 1 : thesize; 363 364 spx_alloc(data, themax); 365 366 assert(isConsistent()); 367 } 368 369 /// destructor 370 ~DataArray() 371 { 372 if(data) 373 spx_free(data); 374 } 375 }; 376 377 } // namespace soplex 378 #endif // _DATAARRAY_H_ 379