1 // Ceres Solver - A fast non-linear least squares minimizer 2 // Copyright 2010, 2011, 2012 Google Inc. All rights reserved. 3 // http://code.google.com/p/ceres-solver/ 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 Google Inc. nor the names of its contributors may be 14 // used to endorse or promote products derived from this software without 15 // 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 OWNER 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 // Author: rennie (at) google.com (Jeffrey Rennie) 30 // Author: sanjay (at) google.com (Sanjay Ghemawat) -- renamed to FixedArray 31 32 #ifndef CERES_PUBLIC_INTERNAL_FIXED_ARRAY_H_ 33 #define CERES_PUBLIC_INTERNAL_FIXED_ARRAY_H_ 34 35 #include <cstddef> 36 #include "Eigen/Core" 37 #include "ceres/internal/macros.h" 38 #include "ceres/internal/manual_constructor.h" 39 #include "glog/logging.h" 40 41 namespace ceres { 42 namespace internal { 43 44 // A FixedArray<T> represents a non-resizable array of T where the 45 // length of the array does not need to be a compile time constant. 46 // 47 // FixedArray allocates small arrays inline, and large arrays on 48 // the heap. It is a good replacement for non-standard and deprecated 49 // uses of alloca() and variable length arrays (a GCC extension). 50 // 51 // FixedArray keeps performance fast for small arrays, because it 52 // avoids heap operations. It also helps reduce the chances of 53 // accidentally overflowing your stack if large input is passed to 54 // your function. 55 // 56 // Also, FixedArray is useful for writing portable code. Not all 57 // compilers support arrays of dynamic size. 58 59 // Most users should not specify an inline_elements argument and let 60 // FixedArray<> automatically determine the number of elements 61 // to store inline based on sizeof(T). 62 // 63 // If inline_elements is specified, the FixedArray<> implementation 64 // will store arrays of length <= inline_elements inline. 65 // 66 // Finally note that unlike vector<T> FixedArray<T> will not zero-initialize 67 // simple types like int, double, bool, etc. 68 // 69 // Non-POD types will be default-initialized just like regular vectors or 70 // arrays. 71 72 #if defined(_WIN64) 73 typedef __int64 ssize_t; 74 #elif defined(_WIN32) 75 typedef __int32 ssize_t; 76 #endif 77 78 template <typename T, ssize_t inline_elements = -1> 79 class FixedArray { 80 public: 81 // For playing nicely with stl: 82 typedef T value_type; 83 typedef T* iterator; 84 typedef T const* const_iterator; 85 typedef T& reference; 86 typedef T const& const_reference; 87 typedef T* pointer; 88 typedef std::ptrdiff_t difference_type; 89 typedef size_t size_type; 90 91 // REQUIRES: n >= 0 92 // Creates an array object that can store "n" elements. 93 // 94 // FixedArray<T> will not zero-initialiaze POD (simple) types like int, 95 // double, bool, etc. 96 // Non-POD types will be default-initialized just like regular vectors or 97 // arrays. 98 explicit FixedArray(size_type n); 99 100 // Releases any resources. 101 ~FixedArray(); 102 103 // Returns the length of the array. 104 inline size_type size() const { return size_; } 105 106 // Returns the memory size of the array in bytes. 107 inline size_t memsize() const { return size_ * sizeof(T); } 108 109 // Returns a pointer to the underlying element array. 110 inline const T* get() const { return &array_[0].element; } 111 inline T* get() { return &array_[0].element; } 112 113 // REQUIRES: 0 <= i < size() 114 // Returns a reference to the "i"th element. 115 inline T& operator[](size_type i) { 116 DCHECK_GE(i, 0); 117 DCHECK_LT(i, size_); 118 return array_[i].element; 119 } 120 121 // REQUIRES: 0 <= i < size() 122 // Returns a reference to the "i"th element. 123 inline const T& operator[](size_type i) const { 124 DCHECK_GE(i, 0); 125 DCHECK_LT(i, size_); 126 return array_[i].element; 127 } 128 129 inline iterator begin() { return &array_[0].element; } 130 inline iterator end() { return &array_[size_].element; } 131 132 inline const_iterator begin() const { return &array_[0].element; } 133 inline const_iterator end() const { return &array_[size_].element; } 134 135 private: 136 // Container to hold elements of type T. This is necessary to handle 137 // the case where T is a a (C-style) array. The size of InnerContainer 138 // and T must be the same, otherwise callers' assumptions about use 139 // of this code will be broken. 140 struct InnerContainer { 141 T element; 142 }; 143 144 // How many elements should we store inline? 145 // a. If not specified, use a default of 256 bytes (256 bytes 146 // seems small enough to not cause stack overflow or unnecessary 147 // stack pollution, while still allowing stack allocation for 148 // reasonably long character arrays. 149 // b. Never use 0 length arrays (not ISO C++) 150 static const size_type S1 = ((inline_elements < 0) 151 ? (256/sizeof(T)) : inline_elements); 152 static const size_type S2 = (S1 <= 0) ? 1 : S1; 153 static const size_type kInlineElements = S2; 154 155 size_type const size_; 156 InnerContainer* const array_; 157 158 // Allocate some space, not an array of elements of type T, so that we can 159 // skip calling the T constructors and destructors for space we never use. 160 ManualConstructor<InnerContainer> inline_space_[kInlineElements]; 161 }; 162 163 // Implementation details follow 164 165 template <class T, ssize_t S> 166 inline FixedArray<T, S>::FixedArray(typename FixedArray<T, S>::size_type n) 167 : size_(n), 168 array_((n <= kInlineElements 169 ? reinterpret_cast<InnerContainer*>(inline_space_) 170 : new InnerContainer[n])) { 171 DCHECK_GE(n, size_t(0)); 172 173 // Construct only the elements actually used. 174 if (array_ == reinterpret_cast<InnerContainer*>(inline_space_)) { 175 for (size_t i = 0; i != size_; ++i) { 176 inline_space_[i].Init(); 177 } 178 } 179 } 180 181 template <class T, ssize_t S> 182 inline FixedArray<T, S>::~FixedArray() { 183 if (array_ != reinterpret_cast<InnerContainer*>(inline_space_)) { 184 delete[] array_; 185 } else { 186 for (size_t i = 0; i != size_; ++i) { 187 inline_space_[i].Destroy(); 188 } 189 } 190 } 191 192 } // namespace internal 193 } // namespace ceres 194 195 #endif // CERES_PUBLIC_INTERNAL_FIXED_ARRAY_H_ 196
