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