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 "Eigen/Core"
37#include "ceres/internal/macros.h"
38#include "ceres/internal/manual_constructor.h"
39#include "glog/logging.h"
40
41namespace ceres {
42namespace 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
78template <typename T, ssize_t inline_elements = -1>
79class 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_LT(i, size_);
117    return array_[i].element;
118  }
119
120  // REQUIRES: 0 <= i < size()
121  // Returns a reference to the "i"th element.
122  inline const T& operator[](size_type i) const {
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    T element;
140  };
141
142  // How many elements should we store inline?
143  //   a. If not specified, use a default of 256 bytes (256 bytes
144  //      seems small enough to not cause stack overflow or unnecessary
145  //      stack pollution, while still allowing stack allocation for
146  //      reasonably long character arrays.
147  //   b. Never use 0 length arrays (not ISO C++)
148  static const size_type S1 = ((inline_elements < 0)
149                               ? (256/sizeof(T)) : inline_elements);
150  static const size_type S2 = (S1 <= 0) ? 1 : S1;
151  static const size_type kInlineElements = S2;
152
153  size_type const       size_;
154  InnerContainer* const array_;
155
156  // Allocate some space, not an array of elements of type T, so that we can
157  // skip calling the T constructors and destructors for space we never use.
158  ManualConstructor<InnerContainer> inline_space_[kInlineElements];
159};
160
161// Implementation details follow
162
163template <class T, ssize_t S>
164inline FixedArray<T, S>::FixedArray(typename FixedArray<T, S>::size_type n)
165    : size_(n),
166      array_((n <= kInlineElements
167              ? reinterpret_cast<InnerContainer*>(inline_space_)
168              : new InnerContainer[n])) {
169  // Construct only the elements actually used.
170  if (array_ == reinterpret_cast<InnerContainer*>(inline_space_)) {
171    for (size_t i = 0; i != size_; ++i) {
172      inline_space_[i].Init();
173    }
174  }
175}
176
177template <class T, ssize_t S>
178inline FixedArray<T, S>::~FixedArray() {
179  if (array_ != reinterpret_cast<InnerContainer*>(inline_space_)) {
180    delete[] array_;
181  } else {
182    for (size_t i = 0; i != size_; ++i) {
183      inline_space_[i].Destroy();
184    }
185  }
186}
187
188}  // namespace internal
189}  // namespace ceres
190
191#endif  // CERES_PUBLIC_INTERNAL_FIXED_ARRAY_H_
192