Switch to FixedArray implementation from abseil.
This PR changes the implementation of the current fixed array to the
abseil one, which has proper allocator support.
Some minor changes are made to make the fixed array implementation
self-contained (no dependent to abseil):
- No address sanitizer support (red zones, etc.)
- Remove of noexecpt specified for copy and move constructor.
- Remove of 'at' function as Ceres does not use exceptions.
- Use std::tuple instead of absl::CompressedTuple as it uses the abseil
utility header which includes a whole bunch of other headers.
Change-Id: I43445b42c37f944509b5353a587d0efce74cbccf
diff --git a/include/ceres/autodiff_first_order_function.h b/include/ceres/autodiff_first_order_function.h
index b2c6800..65b7d0f 100644
--- a/include/ceres/autodiff_first_order_function.h
+++ b/include/ceres/autodiff_first_order_function.h
@@ -86,8 +86,8 @@
// first, and are passed as const pointers to arrays of T. The
// output is the last parameter.
//
-// Then given this class definition, the auto differentiated FirstOrderFunction for
-// it can be constructed as follows.
+// Then given this class definition, the auto differentiated FirstOrderFunction
+// for it can be constructed as follows.
//
// FirstOrderFunction* function =
// new AutoDiffFirstOrderFunction<QuadraticCostFunctor, 4>(
@@ -132,7 +132,7 @@
output.a = kImpossibleValue;
output.v.setConstant(kImpossibleValue);
- if (!(*functor_)(x.get(), &output)) {
+ if (!(*functor_)(x.data(), &output)) {
return false;
}
diff --git a/include/ceres/dynamic_cost_function_to_functor.h b/include/ceres/dynamic_cost_function_to_functor.h
index 7ae5291..8284dd2 100644
--- a/include/ceres/dynamic_cost_function_to_functor.h
+++ b/include/ceres/dynamic_cost_function_to_functor.h
@@ -130,8 +130,8 @@
// Build a set of arrays to get the residuals and jacobians from
// the CostFunction wrapped by this functor.
- double* parameter_ptr = parameters.get();
- double* jacobian_ptr = jacobians.get();
+ double* parameter_ptr = parameters.data();
+ double* jacobian_ptr = jacobians.data();
for (int i = 0; i < num_parameter_blocks; ++i) {
parameter_blocks[i] = parameter_ptr;
jacobian_blocks[i] = jacobian_ptr;
@@ -141,9 +141,9 @@
jacobian_ptr += num_residuals * parameter_block_sizes[i];
}
- if (!cost_function_->Evaluate(parameter_blocks.get(),
- residuals.get(),
- jacobian_blocks.get())) {
+ if (!cost_function_->Evaluate(parameter_blocks.data(),
+ residuals.data(),
+ jacobian_blocks.data())) {
return false;
}
diff --git a/include/ceres/internal/algorithm.h b/include/ceres/internal/algorithm.h
new file mode 100644
index 0000000..3872055
--- /dev/null
+++ b/include/ceres/internal/algorithm.h
@@ -0,0 +1,122 @@
+// Copyright 2017 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+// -----------------------------------------------------------------------------
+// File: algorithm.h
+// -----------------------------------------------------------------------------
+//
+// This header file contains Google extensions to the standard <algorithm> C++
+// header.
+
+#ifndef CERES_PUBLIC_INTERNAL_ALGORITHM_H_
+#define CERES_PUBLIC_INTERNAL_ALGORITHM_H_
+
+#include <algorithm>
+#include <iterator>
+#include <type_traits>
+
+namespace ceres {
+namespace internal {
+
+// Performs comparisons with operator==, similar to C++14's `std::equal_to<>`.
+struct EqualTo {
+ template <typename T, typename U>
+ bool operator()(const T& a, const U& b) const {
+ return a == b;
+ }
+};
+
+template <typename InputIter1, typename InputIter2, typename Pred>
+bool EqualImpl(InputIter1 first1,
+ InputIter1 last1,
+ InputIter2 first2,
+ InputIter2 last2,
+ Pred pred,
+ std::input_iterator_tag,
+ std::input_iterator_tag) {
+ while (true) {
+ if (first1 == last1) return first2 == last2;
+ if (first2 == last2) return false;
+ if (!pred(*first1, *first2)) return false;
+ ++first1;
+ ++first2;
+ }
+}
+
+template <typename InputIter1, typename InputIter2, typename Pred>
+bool EqualImpl(InputIter1 first1,
+ InputIter1 last1,
+ InputIter2 first2,
+ InputIter2 last2,
+ Pred&& pred,
+ std::random_access_iterator_tag,
+ std::random_access_iterator_tag) {
+ return (last1 - first1 == last2 - first2) &&
+ std::equal(first1, last1, first2, std::forward<Pred>(pred));
+}
+
+// When we are using our own internal predicate that just applies operator==, we
+// forward to the non-predicate form of std::equal. This enables an optimization
+// in libstdc++ that can result in std::memcmp being used for integer types.
+template <typename InputIter1, typename InputIter2>
+bool EqualImpl(InputIter1 first1,
+ InputIter1 last1,
+ InputIter2 first2,
+ InputIter2 last2,
+ internal::EqualTo /* unused */,
+ std::random_access_iterator_tag,
+ std::random_access_iterator_tag) {
+ return (last1 - first1 == last2 - first2) &&
+ std::equal(first1, last1, first2);
+}
+
+// Compares the equality of two ranges specified by pairs of iterators, using
+// the given predicate, returning true iff for each corresponding iterator i1
+// and i2 in the first and second range respectively, pred(*i1, *i2) == true
+//
+// This comparison takes at most min(`last1` - `first1`, `last2` - `first2`)
+// invocations of the predicate. Additionally, if InputIter1 and InputIter2 are
+// both random-access iterators, and `last1` - `first1` != `last2` - `first2`,
+// then the predicate is never invoked and the function returns false.
+//
+// This is a C++11-compatible implementation of C++14 `std::equal`. See
+// https://en.cppreference.com/w/cpp/algorithm/equal for more information.
+template <typename InputIter1, typename InputIter2, typename Pred>
+bool equal(InputIter1 first1,
+ InputIter1 last1,
+ InputIter2 first2,
+ InputIter2 last2,
+ Pred&& pred) {
+ return internal::EqualImpl(
+ first1,
+ last1,
+ first2,
+ last2,
+ std::forward<Pred>(pred),
+ typename std::iterator_traits<InputIter1>::iterator_category{},
+ typename std::iterator_traits<InputIter2>::iterator_category{});
+}
+
+// Performs comparison of two ranges specified by pairs of iterators using
+// operator==.
+template <typename InputIter1, typename InputIter2>
+bool equal(InputIter1 first1,
+ InputIter1 last1,
+ InputIter2 first2,
+ InputIter2 last2) {
+ return internal::equal(first1, last1, first2, last2, internal::EqualTo{});
+}
+} // namespace internal
+} // namespace ceres
+#endif // CERES_PUBLIC_INTERNAL_ALGORITHM_H_
\ No newline at end of file
diff --git a/include/ceres/internal/autodiff.h b/include/ceres/internal/autodiff.h
index ee8c59d..ef7cfea 100644
--- a/include/ceres/internal/autodiff.h
+++ b/include/ceres/internal/autodiff.h
@@ -289,8 +289,8 @@
// These are the positions of the respective jets in the fixed array x.
std::array<JetT*, ParameterDims::kNumParameterBlocks> unpacked_parameters =
- ParameterDims::GetUnpackedParameters(x.get());
- JetT* output = x.get() + ParameterDims::kNumParameters;
+ ParameterDims::GetUnpackedParameters(x.data());
+ JetT* output = x.data() + ParameterDims::kNumParameters;
// Invalidate the output Jets, so that we can detect if the user
// did not assign values to all of them.
@@ -299,7 +299,7 @@
output[i].v.setConstant(kImpossibleValue);
}
- Make1stOrderPerturbations<Parameters>::Apply(parameters, x.get());
+ Make1stOrderPerturbations<Parameters>::Apply(parameters, x.data());
if (!VariadicEvaluate<ParameterDims>(functor, unpacked_parameters.data(),
output)) {
diff --git a/include/ceres/internal/fixed_array.h b/include/ceres/internal/fixed_array.h
index dcb2ace..6e86e9d 100644
--- a/include/ceres/internal/fixed_array.h
+++ b/include/ceres/internal/fixed_array.h
@@ -1,189 +1,450 @@
-// Ceres Solver - A fast non-linear least squares minimizer
-// Copyright 2015 Google Inc. All rights reserved.
-// http://ceres-solver.org/
+// Copyright 2018 The Abseil Authors.
//
-// Redistribution and use in source and binary forms, with or without
-// modification, are permitted provided that the following conditions are met:
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
//
-// * Redistributions of source code must retain the above copyright notice,
-// this list of conditions and the following disclaimer.
-// * Redistributions in binary form must reproduce the above copyright notice,
-// this list of conditions and the following disclaimer in the documentation
-// and/or other materials provided with the distribution.
-// * Neither the name of Google Inc. nor the names of its contributors may be
-// used to endorse or promote products derived from this software without
-// specific prior written permission.
+// https://www.apache.org/licenses/LICENSE-2.0
//
-// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
-// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
-// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
-// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
-// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
-// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
-// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
-// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
-// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
-// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
-// POSSIBILITY OF SUCH DAMAGE.
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
//
-// Author: rennie@google.com (Jeffrey Rennie)
-// Author: sanjay@google.com (Sanjay Ghemawat) -- renamed to FixedArray
+// -----------------------------------------------------------------------------
+// File: fixed_array.h
+// -----------------------------------------------------------------------------
+//
+// A `FixedArray<T>` represents a non-resizable array of `T` where the length of
+// the array can be determined at run-time. It is a good replacement for
+// non-standard and deprecated uses of `alloca()` and variable length arrays
+// within the GCC extension. (See
+// https://gcc.gnu.org/onlinedocs/gcc/Variable-Length.html).
+//
+// `FixedArray` allocates small arrays inline, keeping performance fast by
+// avoiding heap operations. It also helps reduce the chances of
+// accidentally overflowing your stack if large input is passed to
+// your function.
#ifndef CERES_PUBLIC_INTERNAL_FIXED_ARRAY_H_
#define CERES_PUBLIC_INTERNAL_FIXED_ARRAY_H_
+#include <algorithm>
#include <cstddef>
-#include "Eigen/Core"
-#include "ceres/internal/manual_constructor.h"
+#include <memory>
+#include <tuple>
+#include <type_traits>
+
+#include "ceres/internal/algorithm.h"
+#include "ceres/internal/memory.h"
#include "glog/logging.h"
namespace ceres {
namespace internal {
-// A FixedArray<T> represents a non-resizable array of T where the
-// length of the array does not need to be a compile time constant.
-//
-// FixedArray allocates small arrays inline, and large arrays on
-// the heap. It is a good replacement for non-standard and deprecated
-// uses of alloca() and variable length arrays (a GCC extension).
-//
-// FixedArray keeps performance fast for small arrays, because it
-// avoids heap operations. It also helps reduce the chances of
-// accidentally overflowing your stack if large input is passed to
-// your function.
-//
-// Also, FixedArray is useful for writing portable code. Not all
-// compilers support arrays of dynamic size.
+constexpr static auto kFixedArrayUseDefault = static_cast<size_t>(-1);
-// Most users should not specify an inline_elements argument and let
-// FixedArray<> automatically determine the number of elements
-// to store inline based on sizeof(T).
+// -----------------------------------------------------------------------------
+// FixedArray
+// -----------------------------------------------------------------------------
//
-// If inline_elements is specified, the FixedArray<> implementation
-// will store arrays of length <= inline_elements inline.
+// A `FixedArray` provides a run-time fixed-size array, allocating a small array
+// inline for efficiency.
//
-// Finally note that unlike vector<T> FixedArray<T> will not zero-initialize
-// simple types like int, double, bool, etc.
+// Most users should not specify an `inline_elements` argument and let
+// `FixedArray` automatically determine the number of elements
+// to store inline based on `sizeof(T)`. If `inline_elements` is specified, the
+// `FixedArray` implementation will use inline storage for arrays with a
+// length <= `inline_elements`.
//
-// Non-POD types will be default-initialized just like regular vectors or
-// arrays.
-
-#if defined(_WIN64)
- typedef __int64 ssize_t;
-#elif defined(_WIN32)
- typedef __int32 ssize_t;
-#endif
-
-template <typename T, ssize_t inline_elements = -1>
+// Note that a `FixedArray` constructed with a `size_type` argument will
+// default-initialize its values by leaving trivially constructible types
+// uninitialized (e.g. int, int[4], double), and others default-constructed.
+// This matches the behavior of c-style arrays and `std::array`, but not
+// `std::vector`.
+//
+// Note that `FixedArray` does not provide a public allocator; if it requires a
+// heap allocation, it will do so with global `::operator new[]()` and
+// `::operator delete[]()`, even if T provides class-scope overrides for these
+// operators.
+template <typename T,
+ size_t N = kFixedArrayUseDefault,
+ typename A = std::allocator<T>>
class FixedArray {
- public:
- // For playing nicely with stl:
- typedef T value_type;
- typedef T* iterator;
- typedef T const* const_iterator;
- typedef T& reference;
- typedef T const& const_reference;
- typedef T* pointer;
- typedef std::ptrdiff_t difference_type;
- typedef size_t size_type;
+ static_assert(!std::is_array<T>::value || std::extent<T>::value > 0,
+ "Arrays with unknown bounds cannot be used with FixedArray.");
- // REQUIRES: n >= 0
- // Creates an array object that can store "n" elements.
- //
- // FixedArray<T> will not zero-initialize POD (simple) types like int,
- // double, bool, etc.
- // Non-POD types will be default-initialized just like regular vectors or
- // arrays.
- explicit FixedArray(size_type n);
+ static constexpr size_t kInlineBytesDefault = 256;
+
+ using AllocatorTraits = std::allocator_traits<A>;
+ // std::iterator_traits isn't guaranteed to be SFINAE-friendly until C++17,
+ // but this seems to be mostly pedantic.
+ template <typename Iterator>
+ using EnableIfForwardIterator = typename std::enable_if<std::is_convertible<
+ typename std::iterator_traits<Iterator>::iterator_category,
+ std::forward_iterator_tag>::value>::type;
+ static constexpr bool DefaultConstructorIsNonTrivial() {
+ return !std::is_trivially_default_constructible<StorageElement>::value;
+ }
+
+ public:
+ using allocator_type = typename AllocatorTraits::allocator_type;
+ using value_type = typename allocator_type::value_type;
+ using pointer = typename allocator_type::pointer;
+ using const_pointer = typename allocator_type::const_pointer;
+ using reference = typename allocator_type::reference;
+ using const_reference = typename allocator_type::const_reference;
+ using size_type = typename allocator_type::size_type;
+ using difference_type = typename allocator_type::difference_type;
+ using iterator = pointer;
+ using const_iterator = const_pointer;
+ using reverse_iterator = std::reverse_iterator<iterator>;
+ using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+
+ static constexpr size_type inline_elements =
+ (N == kFixedArrayUseDefault ? kInlineBytesDefault / sizeof(value_type)
+ : static_cast<size_type>(N));
+
+ FixedArray(const FixedArray& other,
+ const allocator_type& a = allocator_type())
+ : FixedArray(other.begin(), other.end(), a) {}
+
+ FixedArray(FixedArray&& other, const allocator_type& a = allocator_type())
+ : FixedArray(std::make_move_iterator(other.begin()),
+ std::make_move_iterator(other.end()),
+ a) {}
+
+ // Creates an array object that can store `n` elements.
+ // Note that trivially constructible elements will be uninitialized.
+ explicit FixedArray(size_type n, const allocator_type& a = allocator_type())
+ : storage_(n, a) {
+ if (DefaultConstructorIsNonTrivial()) {
+ ConstructRange(storage_.alloc(), storage_.begin(), storage_.end());
+ }
+ }
+
+ // Creates an array initialized with `n` copies of `val`.
+ FixedArray(size_type n,
+ const value_type& val,
+ const allocator_type& a = allocator_type())
+ : storage_(n, a) {
+ ConstructRange(storage_.alloc(), storage_.begin(), storage_.end(), val);
+ }
+
+ // Creates an array initialized with the size and contents of `init_list`.
+ FixedArray(std::initializer_list<value_type> init_list,
+ const allocator_type& a = allocator_type())
+ : FixedArray(init_list.begin(), init_list.end(), a) {}
+
+ // Creates an array initialized with the elements from the input
+ // range. The array's size will always be `std::distance(first, last)`.
+ // REQUIRES: Iterator must be a forward_iterator or better.
+ template <typename Iterator, EnableIfForwardIterator<Iterator>* = nullptr>
+ FixedArray(Iterator first,
+ Iterator last,
+ const allocator_type& a = allocator_type())
+ : storage_(std::distance(first, last), a) {
+ CopyRange(storage_.alloc(), storage_.begin(), first, last);
+ }
// Releases any resources.
- ~FixedArray();
-
- // Returns the length of the array.
- inline size_type size() const { return size_; }
-
- // Returns the memory size of the array in bytes.
- inline size_t memsize() const { return size_ * sizeof(T); }
-
- // Returns a pointer to the underlying element array.
- inline const T* get() const { return &array_[0].element; }
- inline T* get() { return &array_[0].element; }
-
- // REQUIRES: 0 <= i < size()
- // Returns a reference to the "i"th element.
- inline T& operator[](size_type i) {
- DCHECK_LT(i, size_);
- return array_[i].element;
+ ~FixedArray() {
+ for (auto* cur = storage_.begin(); cur != storage_.end(); ++cur) {
+ AllocatorTraits::destroy(storage_.alloc(), cur);
+ }
}
- // REQUIRES: 0 <= i < size()
- // Returns a reference to the "i"th element.
- inline const T& operator[](size_type i) const {
- DCHECK_LT(i, size_);
- return array_[i].element;
+ // Assignments are deleted because they break the invariant that the size of a
+ // `FixedArray` never changes.
+ void operator=(FixedArray&&) = delete;
+ void operator=(const FixedArray&) = delete;
+
+ // FixedArray::size()
+ //
+ // Returns the length of the fixed array.
+ size_type size() const { return storage_.size(); }
+
+ // FixedArray::max_size()
+ //
+ // Returns the largest possible value of `std::distance(begin(), end())` for a
+ // `FixedArray<T>`. This is equivalent to the most possible addressable bytes
+ // over the number of bytes taken by T.
+ constexpr size_type max_size() const {
+ return (std::numeric_limits<difference_type>::max)() / sizeof(value_type);
}
- inline iterator begin() { return &array_[0].element; }
- inline iterator end() { return &array_[size_].element; }
+ // FixedArray::empty()
+ //
+ // Returns whether or not the fixed array is empty.
+ bool empty() const { return size() == 0; }
- inline const_iterator begin() const { return &array_[0].element; }
- inline const_iterator end() const { return &array_[size_].element; }
+ // FixedArray::memsize()
+ //
+ // Returns the memory size of the fixed array in bytes.
+ size_t memsize() const { return size() * sizeof(value_type); }
+
+ // FixedArray::data()
+ //
+ // Returns a const T* pointer to elements of the `FixedArray`. This pointer
+ // can be used to access (but not modify) the contained elements.
+ const_pointer data() const { return AsValueType(storage_.begin()); }
+
+ // Overload of FixedArray::data() to return a T* pointer to elements of the
+ // fixed array. This pointer can be used to access and modify the contained
+ // elements.
+ pointer data() { return AsValueType(storage_.begin()); }
+
+ // FixedArray::operator[]
+ //
+ // Returns a reference the ith element of the fixed array.
+ // REQUIRES: 0 <= i < size()
+ reference operator[](size_type i) {
+ DCHECK_LT(i, size());
+ return data()[i];
+ }
+
+ // Overload of FixedArray::operator()[] to return a const reference to the
+ // ith element of the fixed array.
+ // REQUIRES: 0 <= i < size()
+ const_reference operator[](size_type i) const {
+ DCHECK_LT(i, size());
+ return data()[i];
+ }
+
+ // FixedArray::front()
+ //
+ // Returns a reference to the first element of the fixed array.
+ reference front() { return *begin(); }
+
+ // Overload of FixedArray::front() to return a reference to the first element
+ // of a fixed array of const values.
+ const_reference front() const { return *begin(); }
+
+ // FixedArray::back()
+ //
+ // Returns a reference to the last element of the fixed array.
+ reference back() { return *(end() - 1); }
+
+ // Overload of FixedArray::back() to return a reference to the last element
+ // of a fixed array of const values.
+ const_reference back() const { return *(end() - 1); }
+
+ // FixedArray::begin()
+ //
+ // Returns an iterator to the beginning of the fixed array.
+ iterator begin() { return data(); }
+
+ // Overload of FixedArray::begin() to return a const iterator to the
+ // beginning of the fixed array.
+ const_iterator begin() const { return data(); }
+
+ // FixedArray::cbegin()
+ //
+ // Returns a const iterator to the beginning of the fixed array.
+ const_iterator cbegin() const { return begin(); }
+
+ // FixedArray::end()
+ //
+ // Returns an iterator to the end of the fixed array.
+ iterator end() { return data() + size(); }
+
+ // Overload of FixedArray::end() to return a const iterator to the end of the
+ // fixed array.
+ const_iterator end() const { return data() + size(); }
+
+ // FixedArray::cend()
+ //
+ // Returns a const iterator to the end of the fixed array.
+ const_iterator cend() const { return end(); }
+
+ // FixedArray::rbegin()
+ //
+ // Returns a reverse iterator from the end of the fixed array.
+ reverse_iterator rbegin() { return reverse_iterator(end()); }
+
+ // Overload of FixedArray::rbegin() to return a const reverse iterator from
+ // the end of the fixed array.
+ const_reverse_iterator rbegin() const {
+ return const_reverse_iterator(end());
+ }
+
+ // FixedArray::crbegin()
+ //
+ // Returns a const reverse iterator from the end of the fixed array.
+ const_reverse_iterator crbegin() const { return rbegin(); }
+
+ // FixedArray::rend()
+ //
+ // Returns a reverse iterator from the beginning of the fixed array.
+ reverse_iterator rend() { return reverse_iterator(begin()); }
+
+ // Overload of FixedArray::rend() for returning a const reverse iterator
+ // from the beginning of the fixed array.
+ const_reverse_iterator rend() const {
+ return const_reverse_iterator(begin());
+ }
+
+ // FixedArray::crend()
+ //
+ // Returns a reverse iterator from the beginning of the fixed array.
+ const_reverse_iterator crend() const { return rend(); }
+
+ // FixedArray::fill()
+ //
+ // Assigns the given `value` to all elements in the fixed array.
+ void fill(const value_type& val) { std::fill(begin(), end(), val); }
+
+ // Relational operators. Equality operators are elementwise using
+ // `operator==`, while order operators order FixedArrays lexicographically.
+ friend bool operator==(const FixedArray& lhs, const FixedArray& rhs) {
+ return internal::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
+ }
+
+ friend bool operator!=(const FixedArray& lhs, const FixedArray& rhs) {
+ return !(lhs == rhs);
+ }
+
+ friend bool operator<(const FixedArray& lhs, const FixedArray& rhs) {
+ return std::lexicographical_compare(
+ lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
+ }
+
+ friend bool operator>(const FixedArray& lhs, const FixedArray& rhs) {
+ return rhs < lhs;
+ }
+
+ friend bool operator<=(const FixedArray& lhs, const FixedArray& rhs) {
+ return !(rhs < lhs);
+ }
+
+ friend bool operator>=(const FixedArray& lhs, const FixedArray& rhs) {
+ return !(lhs < rhs);
+ }
private:
- // Container to hold elements of type T. This is necessary to handle
- // the case where T is a (C-style) array. The size of InnerContainer
- // and T must be the same, otherwise callers' assumptions about use
- // of this code will be broken.
- struct InnerContainer {
- T element;
+ // StorageElement
+ //
+ // For FixedArrays with a C-style-array value_type, StorageElement is a POD
+ // wrapper struct called StorageElementWrapper that holds the value_type
+ // instance inside. This is needed for construction and destruction of the
+ // entire array regardless of how many dimensions it has. For all other cases,
+ // StorageElement is just an alias of value_type.
+ //
+ // Maintainer's Note: The simpler solution would be to simply wrap value_type
+ // in a struct whether it's an array or not. That causes some paranoid
+ // diagnostics to misfire, believing that 'data()' returns a pointer to a
+ // single element, rather than the packed array that it really is.
+ // e.g.:
+ //
+ // FixedArray<char> buf(1);
+ // sprintf(buf.data(), "foo");
+ //
+ // error: call to int __builtin___sprintf_chk(etc...)
+ // will always overflow destination buffer [-Werror]
+ //
+ template <typename OuterT = value_type,
+ typename InnerT = typename std::remove_extent<OuterT>::type,
+ size_t InnerN = std::extent<OuterT>::value>
+ struct StorageElementWrapper {
+ InnerT array[InnerN];
};
- // How many elements should we store inline?
- // a. If not specified, use a default of 256 bytes (256 bytes
- // seems small enough to not cause stack overflow or unnecessary
- // stack pollution, while still allowing stack allocation for
- // reasonably long character arrays.
- // b. Never use 0 length arrays (not ISO C++)
- static const size_type S1 = ((inline_elements < 0)
- ? (256/sizeof(T)) : inline_elements);
- static const size_type S2 = (S1 <= 0) ? 1 : S1;
- static const size_type kInlineElements = S2;
+ using StorageElement =
+ typename std::conditional<std::is_array<value_type>::value,
+ StorageElementWrapper<value_type>,
+ value_type>::type;
+ using StorageElementBuffer =
+ typename std::aligned_storage<sizeof(StorageElement),
+ alignof(StorageElement)>::type;
- size_type const size_;
- InnerContainer* const array_;
+ static pointer AsValueType(pointer ptr) { return ptr; }
+ static pointer AsValueType(StorageElementWrapper<value_type>* ptr) {
+ return std::addressof(ptr->array);
+ }
- // Allocate some space, not an array of elements of type T, so that we can
- // skip calling the T constructors and destructors for space we never use.
- ManualConstructor<InnerContainer> inline_space_[kInlineElements];
+ static_assert(sizeof(StorageElement) == sizeof(value_type), "");
+ static_assert(alignof(StorageElement) == alignof(value_type), "");
+
+ struct NonEmptyInlinedStorage {
+ StorageElement* data() {
+ return reinterpret_cast<StorageElement*>(inlined_storage_.data());
+ }
+
+ // #ifdef ADDRESS_SANITIZER
+ // void* RedzoneBegin() { return &redzone_begin_; }
+ // void* RedzoneEnd() { return &redzone_end_ + 1; }
+ // #endif // ADDRESS_SANITIZER
+
+ void AnnotateConstruct(size_type) {}
+ void AnnotateDestruct(size_type) {}
+
+ // ADDRESS_SANITIZER_REDZONE(redzone_begin_);
+ std::array<StorageElementBuffer, inline_elements> inlined_storage_;
+ // ADDRESS_SANITIZER_REDZONE(redzone_end_);
+ };
+
+ struct EmptyInlinedStorage {
+ StorageElement* data() { return nullptr; }
+ void AnnotateConstruct(size_type) {}
+ void AnnotateDestruct(size_type) {}
+ };
+
+ using InlinedStorage =
+ typename std::conditional<inline_elements == 0,
+ EmptyInlinedStorage,
+ NonEmptyInlinedStorage>::type;
+
+ // Storage
+ //
+ // An instance of Storage manages the inline and out-of-line memory for
+ // instances of FixedArray. This guarantees that even when construction of
+ // individual elements fails in the FixedArray constructor body, the
+ // destructor for Storage will still be called and out-of-line memory will be
+ // properly deallocated.
+ //
+ class Storage : public InlinedStorage {
+ public:
+ Storage(size_type n, const allocator_type& a)
+ : size_alloc_(n, a), data_(InitializeData()) {}
+
+ ~Storage() noexcept {
+ if (UsingInlinedStorage(size())) {
+ InlinedStorage::AnnotateDestruct(size());
+ } else {
+ AllocatorTraits::deallocate(alloc(), AsValueType(begin()), size());
+ }
+ }
+
+ size_type size() const { return std::get<0>(size_alloc_); }
+ StorageElement* begin() const { return data_; }
+ StorageElement* end() const { return begin() + size(); }
+ allocator_type& alloc() { return std::get<1>(size_alloc_); }
+
+ private:
+ static bool UsingInlinedStorage(size_type n) {
+ return n <= inline_elements;
+ }
+
+ StorageElement* InitializeData() {
+ if (UsingInlinedStorage(size())) {
+ InlinedStorage::AnnotateConstruct(size());
+ return InlinedStorage::data();
+ } else {
+ return reinterpret_cast<StorageElement*>(
+ AllocatorTraits::allocate(alloc(), size()));
+ }
+ }
+
+ // Using std::tuple and not absl::CompressedTuple, as it has a lot of
+ // dependencies to other absl headers.
+ std::tuple<size_type, allocator_type> size_alloc_;
+ StorageElement* data_;
+ };
+
+ Storage storage_;
};
-// Implementation details follow
-
-template <class T, ssize_t S>
-inline FixedArray<T, S>::FixedArray(typename FixedArray<T, S>::size_type n)
- : size_(n),
- array_((n <= kInlineElements
- ? reinterpret_cast<InnerContainer*>(inline_space_)
- : new InnerContainer[n])) {
- // Construct only the elements actually used.
- if (array_ == reinterpret_cast<InnerContainer*>(inline_space_)) {
- for (size_t i = 0; i != size_; ++i) {
- inline_space_[i].Init();
- }
- }
-}
-
-template <class T, ssize_t S>
-inline FixedArray<T, S>::~FixedArray() {
- if (array_ != reinterpret_cast<InnerContainer*>(inline_space_)) {
- delete[] array_;
- } else {
- for (size_t i = 0; i != size_; ++i) {
- inline_space_[i].Destroy();
- }
- }
-}
-
} // namespace internal
} // namespace ceres
diff --git a/include/ceres/internal/manual_constructor.h b/include/ceres/internal/manual_constructor.h
deleted file mode 100644
index 60f147a..0000000
--- a/include/ceres/internal/manual_constructor.h
+++ /dev/null
@@ -1,152 +0,0 @@
-// Ceres Solver - A fast non-linear least squares minimizer
-// Copyright 2015 Google Inc. All rights reserved.
-// http://ceres-solver.org/
-//
-// Redistribution and use in source and binary forms, with or without
-// modification, are permitted provided that the following conditions are met:
-//
-// * Redistributions of source code must retain the above copyright notice,
-// this list of conditions and the following disclaimer.
-// * Redistributions in binary form must reproduce the above copyright notice,
-// this list of conditions and the following disclaimer in the documentation
-// and/or other materials provided with the distribution.
-// * Neither the name of Google Inc. nor the names of its contributors may be
-// used to endorse or promote products derived from this software without
-// specific prior written permission.
-//
-// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
-// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
-// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
-// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
-// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
-// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
-// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
-// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
-// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
-// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
-// POSSIBILITY OF SUCH DAMAGE.
-//
-// Author: kenton@google.com (Kenton Varda)
-//
-// ManualConstructor statically-allocates space in which to store some
-// object, but does not initialize it. You can then call the constructor
-// and destructor for the object yourself as you see fit. This is useful
-// for memory management optimizations, where you want to initialize and
-// destroy an object multiple times but only allocate it once.
-//
-// (When I say ManualConstructor statically allocates space, I mean that
-// the ManualConstructor object itself is forced to be the right size.)
-
-#ifndef CERES_PUBLIC_INTERNAL_MANUAL_CONSTRUCTOR_H_
-#define CERES_PUBLIC_INTERNAL_MANUAL_CONSTRUCTOR_H_
-
-#include <new>
-#include <utility>
-
-namespace ceres {
-namespace internal {
-
-// ------- Define CERES_ALIGNED_CHAR_ARRAY --------------------------------
-
-// Platform independent macros to get aligned memory allocations.
-// For example
-//
-// MyFoo my_foo CERES_ALIGN_ATTRIBUTE(16);
-//
-// Gives us an instance of MyFoo which is aligned at a 16 byte
-// boundary.
-#if defined(_MSC_VER)
-#define CERES_ALIGN_ATTRIBUTE(n) __declspec(align(n))
-#define CERES_ALIGN_OF(T) __alignof(T)
-#elif defined(__GNUC__)
-#define CERES_ALIGN_ATTRIBUTE(n) __attribute__((aligned(n)))
-#define CERES_ALIGN_OF(T) __alignof(T)
-#endif
-
-#ifndef CERES_ALIGNED_CHAR_ARRAY
-
-// Because MSVC and older GCCs require that the argument to their alignment
-// construct to be a literal constant integer, we use a template instantiated
-// at all the possible powers of two.
-template<int alignment, int size> struct AlignType { };
-template<int size> struct AlignType<0, size> { typedef char result[size]; };
-
-#if !defined(CERES_ALIGN_ATTRIBUTE)
-#define CERES_ALIGNED_CHAR_ARRAY you_must_define_CERES_ALIGNED_CHAR_ARRAY_for_your_compiler
-#else // !defined(CERES_ALIGN_ATTRIBUTE)
-
-#define CERES_ALIGN_TYPE_TEMPLATE(X) \
- template<int size> struct AlignType<X, size> { \
- typedef CERES_ALIGN_ATTRIBUTE(X) char result[size]; \
- }
-
-CERES_ALIGN_TYPE_TEMPLATE(1);
-CERES_ALIGN_TYPE_TEMPLATE(2);
-CERES_ALIGN_TYPE_TEMPLATE(4);
-CERES_ALIGN_TYPE_TEMPLATE(8);
-CERES_ALIGN_TYPE_TEMPLATE(16);
-CERES_ALIGN_TYPE_TEMPLATE(32);
-CERES_ALIGN_TYPE_TEMPLATE(64);
-CERES_ALIGN_TYPE_TEMPLATE(128);
-CERES_ALIGN_TYPE_TEMPLATE(256);
-CERES_ALIGN_TYPE_TEMPLATE(512);
-CERES_ALIGN_TYPE_TEMPLATE(1024);
-CERES_ALIGN_TYPE_TEMPLATE(2048);
-CERES_ALIGN_TYPE_TEMPLATE(4096);
-CERES_ALIGN_TYPE_TEMPLATE(8192);
-// Any larger and MSVC++ will complain.
-
-#undef CERES_ALIGN_TYPE_TEMPLATE
-
-#define CERES_ALIGNED_CHAR_ARRAY(T, Size) \
- typename AlignType<CERES_ALIGN_OF(T), sizeof(T) * Size>::result
-
-#endif // !defined(CERES_ALIGN_ATTRIBUTE)
-
-#endif // CERES_ALIGNED_CHAR_ARRAY
-
-template <typename Type>
-class ManualConstructor {
- public:
- // No constructor or destructor because one of the most useful uses of
- // this class is as part of a union, and members of a union cannot have
- // constructors or destructors. And, anyway, the whole point of this
- // class is to bypass these.
-
- inline Type* get() {
- return reinterpret_cast<Type*>(space_);
- }
- inline const Type* get() const {
- return reinterpret_cast<const Type*>(space_);
- }
-
- inline Type* operator->() { return get(); }
- inline const Type* operator->() const { return get(); }
-
- inline Type& operator*() { return *get(); }
- inline const Type& operator*() const { return *get(); }
-
- // This is needed to get around the strict aliasing warning GCC generates.
- inline void* space() {
- return reinterpret_cast<void*>(space_);
- }
-
- template <typename... Ts>
- inline void Init(Ts&&... ps) {
- new(space()) Type(std::forward<Ts>(ps)...);
- }
-
- inline void Destroy() {
- get()->~Type();
- }
-
- private:
- CERES_ALIGNED_CHAR_ARRAY(Type, 1) space_;
-};
-
-#undef CERES_ALIGNED_CHAR_ARRAY
-
-} // namespace internal
-} // namespace ceres
-
-#endif // CERES_PUBLIC_INTERNAL_MANUAL_CONSTRUCTOR_H_
diff --git a/include/ceres/internal/memory.h b/include/ceres/internal/memory.h
new file mode 100644
index 0000000..45c5b67
--- /dev/null
+++ b/include/ceres/internal/memory.h
@@ -0,0 +1,90 @@
+// Copyright 2017 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+// -----------------------------------------------------------------------------
+// File: memory.h
+// -----------------------------------------------------------------------------
+//
+// This header file contains utility functions for managing the creation and
+// conversion of smart pointers. This file is an extension to the C++
+// standard <memory> library header file.
+
+#ifndef CERES_PUBLIC_INTERNAL_MEMORY_H_
+#define CERES_PUBLIC_INTERNAL_MEMORY_H_
+
+#include <memory>
+
+#ifdef CERES_HAVE_EXCEPTIONS
+#define CERES_INTERNAL_TRY try
+#define CERES_INTERNAL_CATCH_ANY catch (...)
+#define CERES_INTERNAL_RETHROW \
+ do { \
+ throw; \
+ } while (false)
+#else // CERES_HAVE_EXCEPTIONS
+#define CERES_INTERNAL_TRY if (true)
+#define CERES_INTERNAL_CATCH_ANY else if (false)
+#define CERES_INTERNAL_RETHROW \
+ do { \
+ } while (false)
+#endif // CERES_HAVE_EXCEPTIONS
+
+namespace ceres {
+namespace internal {
+
+template <typename Allocator, typename Iterator, typename... Args>
+void ConstructRange(Allocator& alloc,
+ Iterator first,
+ Iterator last,
+ const Args&... args) {
+ for (Iterator cur = first; cur != last; ++cur) {
+ CERES_INTERNAL_TRY {
+ std::allocator_traits<Allocator>::construct(
+ alloc, std::addressof(*cur), args...);
+ }
+ CERES_INTERNAL_CATCH_ANY {
+ while (cur != first) {
+ --cur;
+ std::allocator_traits<Allocator>::destroy(alloc, std::addressof(*cur));
+ }
+ CERES_INTERNAL_RETHROW;
+ }
+ }
+}
+
+template <typename Allocator, typename Iterator, typename InputIterator>
+void CopyRange(Allocator& alloc,
+ Iterator destination,
+ InputIterator first,
+ InputIterator last) {
+ for (Iterator cur = destination; first != last;
+ static_cast<void>(++cur), static_cast<void>(++first)) {
+ CERES_INTERNAL_TRY {
+ std::allocator_traits<Allocator>::construct(
+ alloc, std::addressof(*cur), *first);
+ }
+ CERES_INTERNAL_CATCH_ANY {
+ while (cur != destination) {
+ --cur;
+ std::allocator_traits<Allocator>::destroy(alloc, std::addressof(*cur));
+ }
+ CERES_INTERNAL_RETHROW;
+ }
+ }
+}
+
+} // namespace internal
+} // namespace ceres
+
+#endif // CERES_PUBLIC_INTERNAL_MEMORY_H_
diff --git a/include/ceres/internal/numeric_diff.h b/include/ceres/internal/numeric_diff.h
index 8851bc7..211fa82 100644
--- a/include/ceres/internal/numeric_diff.h
+++ b/include/ceres/internal/numeric_diff.h
@@ -125,7 +125,7 @@
// compute the derivative for that parameter.
FixedArray<double> temp_residual_array(num_residuals_internal);
FixedArray<double> residual_array(num_residuals_internal);
- Map<ResidualVector> residuals(residual_array.get(),
+ Map<ResidualVector> residuals(residual_array.data(),
num_residuals_internal);
for (int j = 0; j < parameter_block_size_internal; ++j) {
@@ -140,8 +140,8 @@
residuals_at_eval_point,
parameters,
x_plus_delta.data(),
- temp_residual_array.get(),
- residual_array.get())) {
+ temp_residual_array.data(),
+ residual_array.data())) {
return false;
}
} else {
@@ -152,8 +152,8 @@
residuals_at_eval_point,
parameters,
x_plus_delta.data(),
- temp_residual_array.get(),
- residual_array.get())) {
+ temp_residual_array.data(),
+ residual_array.data())) {
return false;
}
}
diff --git a/include/ceres/numeric_diff_cost_function.h b/include/ceres/numeric_diff_cost_function.h
index f6cd32a..8edf801 100644
--- a/include/ceres/numeric_diff_cost_function.h
+++ b/include/ceres/numeric_diff_cost_function.h
@@ -223,7 +223,7 @@
// Create a copy of the parameters which will get mutated.
FixedArray<double> parameters_copy(kNumParameters);
std::array<double*, kNumParameterBlocks> parameters_reference_copy =
- ParameterDims::GetUnpackedParameters(parameters_copy.get());
+ ParameterDims::GetUnpackedParameters(parameters_copy.data());
for (int block = 0; block < kNumParameterBlocks; ++block) {
memcpy(parameters_reference_copy[block], parameters[block],
diff --git a/internal/ceres/CMakeLists.txt b/internal/ceres/CMakeLists.txt
index 0bf02a2..281eede 100644
--- a/internal/ceres/CMakeLists.txt
+++ b/internal/ceres/CMakeLists.txt
@@ -390,6 +390,7 @@
${Ceres_SOURCE_DIR}/data)
endmacro (CERES_TEST)
+ ceres_test(algorithm)
ceres_test(array_utils)
ceres_test(autodiff)
ceres_test(autodiff_first_order_function)
@@ -422,6 +423,7 @@
ceres_test(dynamic_sparsity)
ceres_test(evaluation_callback)
ceres_test(evaluator)
+ ceres_test(fixed_array)
ceres_test(gradient_checker)
ceres_test(gradient_checking_cost_function)
ceres_test(gradient_problem)
diff --git a/internal/ceres/algorithm_test.cc b/internal/ceres/algorithm_test.cc
new file mode 100644
index 0000000..c131563
--- /dev/null
+++ b/internal/ceres/algorithm_test.cc
@@ -0,0 +1,173 @@
+// Copyright 2017 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "ceres/internal/algorithm.h"
+
+#include <algorithm>
+#include <list>
+#include <vector>
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace {
+
+TEST(EqualTest, DefaultComparisonRandomAccess) {
+ std::vector<int> v1{1, 2, 3};
+ std::vector<int> v2 = v1;
+ std::vector<int> v3 = {1, 2};
+ std::vector<int> v4 = {1, 2, 4};
+
+ EXPECT_TRUE(
+ ceres::internal::equal(v1.begin(), v1.end(), v2.begin(), v2.end()));
+ EXPECT_FALSE(
+ ceres::internal::equal(v1.begin(), v1.end(), v3.begin(), v3.end()));
+ EXPECT_FALSE(
+ ceres::internal::equal(v1.begin(), v1.end(), v4.begin(), v4.end()));
+}
+
+TEST(EqualTest, DefaultComparison) {
+ std::list<int> lst1{1, 2, 3};
+ std::list<int> lst2 = lst1;
+ std::list<int> lst3{1, 2};
+ std::list<int> lst4{1, 2, 4};
+
+ EXPECT_TRUE(ceres::internal::equal(
+ lst1.begin(), lst1.end(), lst2.begin(), lst2.end()));
+ EXPECT_FALSE(ceres::internal::equal(
+ lst1.begin(), lst1.end(), lst3.begin(), lst3.end()));
+ EXPECT_FALSE(ceres::internal::equal(
+ lst1.begin(), lst1.end(), lst4.begin(), lst4.end()));
+}
+
+TEST(EqualTest, EmptyRange) {
+ std::vector<int> v1{1, 2, 3};
+ std::vector<int> empty1;
+ std::vector<int> empty2;
+
+ EXPECT_FALSE(ceres::internal::equal(
+ v1.begin(), v1.end(), empty1.begin(), empty1.end()));
+ EXPECT_FALSE(ceres::internal::equal(
+ empty1.begin(), empty1.end(), v1.begin(), v1.end()));
+ EXPECT_TRUE(ceres::internal::equal(
+ empty1.begin(), empty1.end(), empty2.begin(), empty2.end()));
+}
+
+TEST(EqualTest, MixedIterTypes) {
+ std::vector<int> v1{1, 2, 3};
+ std::list<int> lst1{v1.begin(), v1.end()};
+ std::list<int> lst2{1, 2, 4};
+ std::list<int> lst3{1, 2};
+
+ EXPECT_TRUE(
+ ceres::internal::equal(v1.begin(), v1.end(), lst1.begin(), lst1.end()));
+ EXPECT_FALSE(
+ ceres::internal::equal(v1.begin(), v1.end(), lst2.begin(), lst2.end()));
+ EXPECT_FALSE(
+ ceres::internal::equal(v1.begin(), v1.end(), lst3.begin(), lst3.end()));
+}
+
+TEST(EqualTest, MixedValueTypes) {
+ std::vector<int> v1{1, 2, 3};
+ std::vector<char> v2{1, 2, 3};
+ std::vector<char> v3{1, 2};
+ std::vector<char> v4{1, 2, 4};
+
+ EXPECT_TRUE(
+ ceres::internal::equal(v1.begin(), v1.end(), v2.begin(), v2.end()));
+ EXPECT_FALSE(
+ ceres::internal::equal(v1.begin(), v1.end(), v3.begin(), v3.end()));
+ EXPECT_FALSE(
+ ceres::internal::equal(v1.begin(), v1.end(), v4.begin(), v4.end()));
+}
+
+TEST(EqualTest, WeirdIterators) {
+ std::vector<bool> v1{true, false};
+ std::vector<bool> v2 = v1;
+ std::vector<bool> v3{true};
+ std::vector<bool> v4{true, true, true};
+
+ EXPECT_TRUE(
+ ceres::internal::equal(v1.begin(), v1.end(), v2.begin(), v2.end()));
+ EXPECT_FALSE(
+ ceres::internal::equal(v1.begin(), v1.end(), v3.begin(), v3.end()));
+ EXPECT_FALSE(
+ ceres::internal::equal(v1.begin(), v1.end(), v4.begin(), v4.end()));
+}
+
+TEST(EqualTest, CustomComparison) {
+ int n[] = {1, 2, 3, 4};
+ std::vector<int*> v1{&n[0], &n[1], &n[2]};
+ std::vector<int*> v2 = v1;
+ std::vector<int*> v3{&n[0], &n[1], &n[3]};
+ std::vector<int*> v4{&n[0], &n[1]};
+
+ auto eq = [](int* a, int* b) { return *a == *b; };
+
+ EXPECT_TRUE(
+ ceres::internal::equal(v1.begin(), v1.end(), v2.begin(), v2.end(), eq));
+ EXPECT_FALSE(
+ ceres::internal::equal(v1.begin(), v1.end(), v3.begin(), v3.end(), eq));
+ EXPECT_FALSE(
+ ceres::internal::equal(v1.begin(), v1.end(), v4.begin(), v4.end(), eq));
+}
+
+TEST(EqualTest, MoveOnlyPredicate) {
+ std::vector<int> v1{1, 2, 3};
+ std::vector<int> v2{4, 5, 6};
+
+ // move-only equality predicate
+ struct Eq {
+ Eq() = default;
+ Eq(Eq&&) = default;
+ Eq(const Eq&) = delete;
+ Eq& operator=(const Eq&) = delete;
+ bool operator()(const int a, const int b) const { return a == b; }
+ };
+
+ EXPECT_TRUE(
+ ceres::internal::equal(v1.begin(), v1.end(), v1.begin(), v1.end(), Eq()));
+ EXPECT_FALSE(
+ ceres::internal::equal(v1.begin(), v1.end(), v2.begin(), v2.end(), Eq()));
+}
+
+struct CountingTrivialPred {
+ int* count;
+ bool operator()(int, int) const {
+ ++*count;
+ return true;
+ }
+};
+
+TEST(EqualTest, RandomAccessComplexity) {
+ std::vector<int> v1{1, 1, 3};
+ std::vector<int> v2 = v1;
+ std::vector<int> v3{1, 2};
+
+ do {
+ int count = 0;
+ ceres::internal::equal(v1.begin(),
+ v1.end(),
+ v2.begin(),
+ v2.end(),
+ CountingTrivialPred{&count});
+ EXPECT_LE(count, 3);
+ } while (std::next_permutation(v2.begin(), v2.end()));
+
+ int count = 0;
+ ceres::internal::equal(
+ v1.begin(), v1.end(), v3.begin(), v3.end(), CountingTrivialPred{&count});
+ EXPECT_EQ(count, 0);
+}
+} // namespace
diff --git a/internal/ceres/fixed_array_test.cc b/internal/ceres/fixed_array_test.cc
new file mode 100644
index 0000000..2909707
--- /dev/null
+++ b/internal/ceres/fixed_array_test.cc
@@ -0,0 +1,837 @@
+// Copyright 2017 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "ceres/internal/fixed_array.h"
+
+#include <stdio.h>
+#include <cstring>
+#include <list>
+#include <memory>
+#include <numeric>
+#include <scoped_allocator>
+#include <stdexcept>
+#include <string>
+#include <vector>
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+using ::testing::ElementsAreArray;
+
+namespace {
+
+// CERES_INTERNAL_ARRAYSIZE()
+//
+// Returns the number of elements in an array as a compile-time constant, which
+// can be used in defining new arrays. If you use this macro on a pointer by
+// mistake, you will get a compile-time error.
+#define CERES_INTERNAL_ARRAYSIZE(array) (sizeof(ArraySizeHelper(array)))
+
+// Note: this internal template function declaration is used by
+// CERES_INTERNAL_ARRAYSIZE. The function doesn't need a definition, as we only
+// use its type.
+template <typename T, size_t N>
+auto ArraySizeHelper(const T (&array)[N]) -> char (&)[N];
+
+// Helper routine to determine if a ceres::internal::FixedArray used stack
+// allocation.
+template <typename ArrayType>
+static bool IsOnStack(const ArrayType& a) {
+ return a.size() <= ArrayType::inline_elements;
+}
+
+class ConstructionTester {
+ public:
+ ConstructionTester() : self_ptr_(this), value_(0) { constructions++; }
+ ~ConstructionTester() {
+ assert(self_ptr_ == this);
+ self_ptr_ = nullptr;
+ destructions++;
+ }
+
+ // These are incremented as elements are constructed and destructed so we can
+ // be sure all elements are properly cleaned up.
+ static int constructions;
+ static int destructions;
+
+ void CheckConstructed() { assert(self_ptr_ == this); }
+
+ void set(int value) { value_ = value; }
+ int get() { return value_; }
+
+ private:
+ // self_ptr_ should always point to 'this' -- that's how we can be sure the
+ // constructor has been called.
+ ConstructionTester* self_ptr_;
+ int value_;
+};
+
+int ConstructionTester::constructions = 0;
+int ConstructionTester::destructions = 0;
+
+// ThreeInts will initialize its three ints to the value stored in
+// ThreeInts::counter. The constructor increments counter so that each object
+// in an array of ThreeInts will have different values.
+class ThreeInts {
+ public:
+ ThreeInts() {
+ x_ = counter;
+ y_ = counter;
+ z_ = counter;
+ ++counter;
+ }
+
+ static int counter;
+
+ int x_, y_, z_;
+};
+
+int ThreeInts::counter = 0;
+
+TEST(FixedArrayTest, CopyCtor) {
+ ceres::internal::FixedArray<int, 10> on_stack(5);
+ std::iota(on_stack.begin(), on_stack.end(), 0);
+ ceres::internal::FixedArray<int, 10> stack_copy = on_stack;
+ EXPECT_THAT(stack_copy, ElementsAreArray(on_stack));
+ EXPECT_TRUE(IsOnStack(stack_copy));
+
+ ceres::internal::FixedArray<int, 10> allocated(15);
+ std::iota(allocated.begin(), allocated.end(), 0);
+ ceres::internal::FixedArray<int, 10> alloced_copy = allocated;
+ EXPECT_THAT(alloced_copy, ElementsAreArray(allocated));
+ EXPECT_FALSE(IsOnStack(alloced_copy));
+}
+
+TEST(FixedArrayTest, MoveCtor) {
+ ceres::internal::FixedArray<std::unique_ptr<int>, 10> on_stack(5);
+ for (int i = 0; i < 5; ++i) {
+ on_stack[i] = std::unique_ptr<int>(new int(i));
+ }
+
+ ceres::internal::FixedArray<std::unique_ptr<int>, 10> stack_copy =
+ std::move(on_stack);
+ for (int i = 0; i < 5; ++i) EXPECT_EQ(*(stack_copy[i]), i);
+ EXPECT_EQ(stack_copy.size(), on_stack.size());
+
+ ceres::internal::FixedArray<std::unique_ptr<int>, 10> allocated(15);
+ for (int i = 0; i < 15; ++i) {
+ allocated[i] = std::unique_ptr<int>(new int(i));
+ }
+
+ ceres::internal::FixedArray<std::unique_ptr<int>, 10> alloced_copy =
+ std::move(allocated);
+ for (int i = 0; i < 15; ++i) EXPECT_EQ(*(alloced_copy[i]), i);
+ EXPECT_EQ(allocated.size(), alloced_copy.size());
+}
+
+TEST(FixedArrayTest, SmallObjects) {
+ // Small object arrays
+ {
+ // Short arrays should be on the stack
+ ceres::internal::FixedArray<int> array(4);
+ EXPECT_TRUE(IsOnStack(array));
+ }
+
+ {
+ // Large arrays should be on the heap
+ ceres::internal::FixedArray<int> array(1048576);
+ EXPECT_FALSE(IsOnStack(array));
+ }
+
+ {
+ // Arrays of <= default size should be on the stack
+ ceres::internal::FixedArray<int, 100> array(100);
+ EXPECT_TRUE(IsOnStack(array));
+ }
+
+ {
+ // Arrays of > default size should be on the heap
+ ceres::internal::FixedArray<int, 100> array(101);
+ EXPECT_FALSE(IsOnStack(array));
+ }
+
+ {
+ // Arrays with different size elements should use approximately
+ // same amount of stack space
+ ceres::internal::FixedArray<int> array1(0);
+ ceres::internal::FixedArray<char> array2(0);
+ EXPECT_LE(sizeof(array1), sizeof(array2) + 100);
+ EXPECT_LE(sizeof(array2), sizeof(array1) + 100);
+ }
+
+ {
+ // Ensure that vectors are properly constructed inside a fixed array.
+ ceres::internal::FixedArray<std::vector<int>> array(2);
+ EXPECT_EQ(0, array[0].size());
+ EXPECT_EQ(0, array[1].size());
+ }
+
+ {
+ // Regardless of ceres::internal::FixedArray implementation, check that a
+ // type with a low alignment requirement and a non power-of-two size is
+ // initialized correctly.
+ ThreeInts::counter = 1;
+ ceres::internal::FixedArray<ThreeInts> array(2);
+ EXPECT_EQ(1, array[0].x_);
+ EXPECT_EQ(1, array[0].y_);
+ EXPECT_EQ(1, array[0].z_);
+ EXPECT_EQ(2, array[1].x_);
+ EXPECT_EQ(2, array[1].y_);
+ EXPECT_EQ(2, array[1].z_);
+ }
+}
+
+TEST(FixedArrayRelationalsTest, EqualArrays) {
+ for (int i = 0; i < 10; ++i) {
+ ceres::internal::FixedArray<int, 5> a1(i);
+ std::iota(a1.begin(), a1.end(), 0);
+ ceres::internal::FixedArray<int, 5> a2(a1.begin(), a1.end());
+
+ EXPECT_TRUE(a1 == a2);
+ EXPECT_FALSE(a1 != a2);
+ EXPECT_TRUE(a2 == a1);
+ EXPECT_FALSE(a2 != a1);
+ EXPECT_FALSE(a1 < a2);
+ EXPECT_FALSE(a1 > a2);
+ EXPECT_FALSE(a2 < a1);
+ EXPECT_FALSE(a2 > a1);
+ EXPECT_TRUE(a1 <= a2);
+ EXPECT_TRUE(a1 >= a2);
+ EXPECT_TRUE(a2 <= a1);
+ EXPECT_TRUE(a2 >= a1);
+ }
+}
+
+TEST(FixedArrayRelationalsTest, UnequalArrays) {
+ for (int i = 1; i < 10; ++i) {
+ ceres::internal::FixedArray<int, 5> a1(i);
+ std::iota(a1.begin(), a1.end(), 0);
+ ceres::internal::FixedArray<int, 5> a2(a1.begin(), a1.end());
+ --a2[i / 2];
+
+ EXPECT_FALSE(a1 == a2);
+ EXPECT_TRUE(a1 != a2);
+ EXPECT_FALSE(a2 == a1);
+ EXPECT_TRUE(a2 != a1);
+ EXPECT_FALSE(a1 < a2);
+ EXPECT_TRUE(a1 > a2);
+ EXPECT_TRUE(a2 < a1);
+ EXPECT_FALSE(a2 > a1);
+ EXPECT_FALSE(a1 <= a2);
+ EXPECT_TRUE(a1 >= a2);
+ EXPECT_TRUE(a2 <= a1);
+ EXPECT_FALSE(a2 >= a1);
+ }
+}
+
+template <int stack_elements>
+static void TestArray(int n) {
+ SCOPED_TRACE(n);
+ SCOPED_TRACE(stack_elements);
+ ConstructionTester::constructions = 0;
+ ConstructionTester::destructions = 0;
+ {
+ ceres::internal::FixedArray<ConstructionTester, stack_elements> array(n);
+
+ EXPECT_THAT(array.size(), n);
+ EXPECT_THAT(array.memsize(), sizeof(ConstructionTester) * n);
+ EXPECT_THAT(array.begin() + n, array.end());
+
+ // Check that all elements were constructed
+ for (int i = 0; i < n; i++) {
+ array[i].CheckConstructed();
+ }
+ // Check that no other elements were constructed
+ EXPECT_THAT(ConstructionTester::constructions, n);
+
+ // Test operator[]
+ for (int i = 0; i < n; i++) {
+ array[i].set(i);
+ }
+ for (int i = 0; i < n; i++) {
+ EXPECT_THAT(array[i].get(), i);
+ EXPECT_THAT(array.data()[i].get(), i);
+ }
+
+ // Test data()
+ for (int i = 0; i < n; i++) {
+ array.data()[i].set(i + 1);
+ }
+ for (int i = 0; i < n; i++) {
+ EXPECT_THAT(array[i].get(), i + 1);
+ EXPECT_THAT(array.data()[i].get(), i + 1);
+ }
+ } // Close scope containing 'array'.
+
+ // Check that all constructed elements were destructed.
+ EXPECT_EQ(ConstructionTester::constructions,
+ ConstructionTester::destructions);
+}
+
+template <int elements_per_inner_array, int inline_elements>
+static void TestArrayOfArrays(int n) {
+ SCOPED_TRACE(n);
+ SCOPED_TRACE(inline_elements);
+ SCOPED_TRACE(elements_per_inner_array);
+ ConstructionTester::constructions = 0;
+ ConstructionTester::destructions = 0;
+ {
+ using InnerArray = ConstructionTester[elements_per_inner_array];
+ // Heap-allocate the FixedArray to avoid blowing the stack frame.
+ auto array_ptr = std::unique_ptr<
+ ceres::internal::FixedArray<InnerArray, inline_elements>>(
+ new ceres::internal::FixedArray<InnerArray, inline_elements>(n));
+ auto& array = *array_ptr;
+
+ ASSERT_EQ(array.size(), n);
+ ASSERT_EQ(array.memsize(),
+ sizeof(ConstructionTester) * elements_per_inner_array * n);
+ ASSERT_EQ(array.begin() + n, array.end());
+
+ // Check that all elements were constructed
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < elements_per_inner_array; j++) {
+ (array[i])[j].CheckConstructed();
+ }
+ }
+ // Check that no other elements were constructed
+ ASSERT_EQ(ConstructionTester::constructions, n * elements_per_inner_array);
+
+ // Test operator[]
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < elements_per_inner_array; j++) {
+ (array[i])[j].set(i * elements_per_inner_array + j);
+ }
+ }
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < elements_per_inner_array; j++) {
+ ASSERT_EQ((array[i])[j].get(), i * elements_per_inner_array + j);
+ ASSERT_EQ((array.data()[i])[j].get(), i * elements_per_inner_array + j);
+ }
+ }
+
+ // Test data()
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < elements_per_inner_array; j++) {
+ (array.data()[i])[j].set((i + 1) * elements_per_inner_array + j);
+ }
+ }
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < elements_per_inner_array; j++) {
+ ASSERT_EQ((array[i])[j].get(), (i + 1) * elements_per_inner_array + j);
+ ASSERT_EQ((array.data()[i])[j].get(),
+ (i + 1) * elements_per_inner_array + j);
+ }
+ }
+ } // Close scope containing 'array'.
+
+ // Check that all constructed elements were destructed.
+ EXPECT_EQ(ConstructionTester::constructions,
+ ConstructionTester::destructions);
+}
+
+TEST(IteratorConstructorTest, NonInline) {
+ int const kInput[] = {2, 3, 5, 7, 11, 13, 17};
+ ceres::internal::FixedArray<int, CERES_INTERNAL_ARRAYSIZE(kInput) - 1> const
+ fixed(kInput, kInput + CERES_INTERNAL_ARRAYSIZE(kInput));
+ ASSERT_EQ(CERES_INTERNAL_ARRAYSIZE(kInput), fixed.size());
+ for (size_t i = 0; i < CERES_INTERNAL_ARRAYSIZE(kInput); ++i) {
+ ASSERT_EQ(kInput[i], fixed[i]);
+ }
+}
+
+TEST(IteratorConstructorTest, Inline) {
+ int const kInput[] = {2, 3, 5, 7, 11, 13, 17};
+ ceres::internal::FixedArray<int, CERES_INTERNAL_ARRAYSIZE(kInput)> const
+ fixed(kInput, kInput + CERES_INTERNAL_ARRAYSIZE(kInput));
+ ASSERT_EQ(CERES_INTERNAL_ARRAYSIZE(kInput), fixed.size());
+ for (size_t i = 0; i < CERES_INTERNAL_ARRAYSIZE(kInput); ++i) {
+ ASSERT_EQ(kInput[i], fixed[i]);
+ }
+}
+
+TEST(IteratorConstructorTest, NonPod) {
+ char const* kInput[] = {
+ "red", "orange", "yellow", "green", "blue", "indigo", "violet"};
+ ceres::internal::FixedArray<std::string> const fixed(
+ kInput, kInput + CERES_INTERNAL_ARRAYSIZE(kInput));
+ ASSERT_EQ(CERES_INTERNAL_ARRAYSIZE(kInput), fixed.size());
+ for (size_t i = 0; i < CERES_INTERNAL_ARRAYSIZE(kInput); ++i) {
+ ASSERT_EQ(kInput[i], fixed[i]);
+ }
+}
+
+TEST(IteratorConstructorTest, FromEmptyVector) {
+ std::vector<int> const empty;
+ ceres::internal::FixedArray<int> const fixed(empty.begin(), empty.end());
+ EXPECT_EQ(0, fixed.size());
+ EXPECT_EQ(empty.size(), fixed.size());
+}
+
+TEST(IteratorConstructorTest, FromNonEmptyVector) {
+ int const kInput[] = {2, 3, 5, 7, 11, 13, 17};
+ std::vector<int> const items(kInput,
+ kInput + CERES_INTERNAL_ARRAYSIZE(kInput));
+ ceres::internal::FixedArray<int> const fixed(items.begin(), items.end());
+ ASSERT_EQ(items.size(), fixed.size());
+ for (size_t i = 0; i < items.size(); ++i) {
+ ASSERT_EQ(items[i], fixed[i]);
+ }
+}
+
+TEST(IteratorConstructorTest, FromBidirectionalIteratorRange) {
+ int const kInput[] = {2, 3, 5, 7, 11, 13, 17};
+ std::list<int> const items(kInput, kInput + CERES_INTERNAL_ARRAYSIZE(kInput));
+ ceres::internal::FixedArray<int> const fixed(items.begin(), items.end());
+ EXPECT_THAT(fixed, testing::ElementsAreArray(kInput));
+}
+
+TEST(InitListConstructorTest, InitListConstruction) {
+ ceres::internal::FixedArray<int> fixed = {1, 2, 3};
+ EXPECT_THAT(fixed, testing::ElementsAreArray({1, 2, 3}));
+}
+
+TEST(FillConstructorTest, NonEmptyArrays) {
+ ceres::internal::FixedArray<int> stack_array(4, 1);
+ EXPECT_THAT(stack_array, testing::ElementsAreArray({1, 1, 1, 1}));
+
+ ceres::internal::FixedArray<int, 0> heap_array(4, 1);
+ EXPECT_THAT(stack_array, testing::ElementsAreArray({1, 1, 1, 1}));
+}
+
+TEST(FillConstructorTest, EmptyArray) {
+ ceres::internal::FixedArray<int> empty_fill(0, 1);
+ ceres::internal::FixedArray<int> empty_size(0);
+ EXPECT_EQ(empty_fill, empty_size);
+}
+
+TEST(FillConstructorTest, NotTriviallyCopyable) {
+ std::string str = "abcd";
+ ceres::internal::FixedArray<std::string> strings = {str, str, str, str};
+
+ ceres::internal::FixedArray<std::string> array(4, str);
+ EXPECT_EQ(array, strings);
+}
+
+TEST(FillConstructorTest, Disambiguation) {
+ ceres::internal::FixedArray<size_t> a(1, 2);
+ EXPECT_THAT(a, testing::ElementsAre(2));
+}
+
+TEST(FixedArrayTest, ManySizedArrays) {
+ std::vector<int> sizes;
+ for (int i = 1; i < 100; i++) sizes.push_back(i);
+ for (int i = 100; i <= 1000; i += 100) sizes.push_back(i);
+ for (int n : sizes) {
+ TestArray<0>(n);
+ TestArray<1>(n);
+ TestArray<64>(n);
+ TestArray<1000>(n);
+ }
+}
+
+TEST(FixedArrayTest, ManySizedArraysOfArraysOf1) {
+ for (int n = 1; n < 1000; n++) {
+ ASSERT_NO_FATAL_FAILURE((TestArrayOfArrays<1, 0>(n)));
+ ASSERT_NO_FATAL_FAILURE((TestArrayOfArrays<1, 1>(n)));
+ ASSERT_NO_FATAL_FAILURE((TestArrayOfArrays<1, 64>(n)));
+ ASSERT_NO_FATAL_FAILURE((TestArrayOfArrays<1, 1000>(n)));
+ }
+}
+
+TEST(FixedArrayTest, ManySizedArraysOfArraysOf2) {
+ for (int n = 1; n < 1000; n++) {
+ TestArrayOfArrays<2, 0>(n);
+ TestArrayOfArrays<2, 1>(n);
+ TestArrayOfArrays<2, 64>(n);
+ TestArrayOfArrays<2, 1000>(n);
+ }
+}
+
+// If value_type is put inside of a struct container,
+// we might evoke this error in a hardened build unless data() is carefully
+// written, so check on that.
+// error: call to int __builtin___sprintf_chk(etc...)
+// will always overflow destination buffer [-Werror]
+TEST(FixedArrayTest, AvoidParanoidDiagnostics) {
+ ceres::internal::FixedArray<char, 32> buf(32);
+ sprintf(buf.data(), "foo"); // NOLINT(runtime/printf)
+}
+
+TEST(FixedArrayTest, TooBigInlinedSpace) {
+ struct TooBig {
+ char c[1 << 20];
+ }; // too big for even one on the stack
+
+ // Simulate the data members of ceres::internal::FixedArray, a pointer and a
+ // size_t.
+ struct Data {
+ TooBig* p;
+ size_t size;
+ };
+
+ // Make sure TooBig objects are not inlined for 0 or default size.
+ static_assert(
+ sizeof(ceres::internal::FixedArray<TooBig, 0>) == sizeof(Data),
+ "0-sized ceres::internal::FixedArray should have same size as Data.");
+ static_assert(
+ alignof(ceres::internal::FixedArray<TooBig, 0>) == alignof(Data),
+ "0-sized ceres::internal::FixedArray should have same alignment as "
+ "Data.");
+ static_assert(sizeof(ceres::internal::FixedArray<TooBig>) == sizeof(Data),
+ "default-sized ceres::internal::FixedArray should have same "
+ "size as Data");
+ static_assert(alignof(ceres::internal::FixedArray<TooBig>) == alignof(Data),
+ "default-sized ceres::internal::FixedArray should have same "
+ "alignment as Data.");
+}
+
+// PickyDelete EXPECTs its class-scope deallocation funcs are unused.
+struct PickyDelete {
+ PickyDelete() {}
+ ~PickyDelete() {}
+ void operator delete(void* p) {
+ EXPECT_TRUE(false) << __FUNCTION__;
+ ::operator delete(p);
+ }
+ void operator delete[](void* p) {
+ EXPECT_TRUE(false) << __FUNCTION__;
+ ::operator delete[](p);
+ }
+};
+
+TEST(FixedArrayTest, UsesGlobalAlloc) {
+ ceres::internal::FixedArray<PickyDelete, 0> a(5);
+}
+
+TEST(FixedArrayTest, Data) {
+ static const int kInput[] = {2, 3, 5, 7, 11, 13, 17};
+ ceres::internal::FixedArray<int> fa(std::begin(kInput), std::end(kInput));
+ EXPECT_EQ(fa.data(), &*fa.begin());
+ EXPECT_EQ(fa.data(), &fa[0]);
+
+ const ceres::internal::FixedArray<int>& cfa = fa;
+ EXPECT_EQ(cfa.data(), &*cfa.begin());
+ EXPECT_EQ(cfa.data(), &cfa[0]);
+}
+
+TEST(FixedArrayTest, Empty) {
+ ceres::internal::FixedArray<int> empty(0);
+ ceres::internal::FixedArray<int> inline_filled(1);
+ ceres::internal::FixedArray<int, 0> heap_filled(1);
+ EXPECT_TRUE(empty.empty());
+ EXPECT_FALSE(inline_filled.empty());
+ EXPECT_FALSE(heap_filled.empty());
+}
+
+TEST(FixedArrayTest, FrontAndBack) {
+ ceres::internal::FixedArray<int, 3 * sizeof(int)> inlined = {1, 2, 3};
+ EXPECT_EQ(inlined.front(), 1);
+ EXPECT_EQ(inlined.back(), 3);
+
+ ceres::internal::FixedArray<int, 0> allocated = {1, 2, 3};
+ EXPECT_EQ(allocated.front(), 1);
+ EXPECT_EQ(allocated.back(), 3);
+
+ ceres::internal::FixedArray<int> one_element = {1};
+ EXPECT_EQ(one_element.front(), one_element.back());
+}
+
+TEST(FixedArrayTest, ReverseIteratorInlined) {
+ ceres::internal::FixedArray<int, 5 * sizeof(int)> a = {0, 1, 2, 3, 4};
+
+ int counter = 5;
+ for (ceres::internal::FixedArray<int>::reverse_iterator iter = a.rbegin();
+ iter != a.rend();
+ ++iter) {
+ counter--;
+ EXPECT_EQ(counter, *iter);
+ }
+ EXPECT_EQ(counter, 0);
+
+ counter = 5;
+ for (ceres::internal::FixedArray<int>::const_reverse_iterator iter =
+ a.rbegin();
+ iter != a.rend();
+ ++iter) {
+ counter--;
+ EXPECT_EQ(counter, *iter);
+ }
+ EXPECT_EQ(counter, 0);
+
+ counter = 5;
+ for (auto iter = a.crbegin(); iter != a.crend(); ++iter) {
+ counter--;
+ EXPECT_EQ(counter, *iter);
+ }
+ EXPECT_EQ(counter, 0);
+}
+
+TEST(FixedArrayTest, ReverseIteratorAllocated) {
+ ceres::internal::FixedArray<int, 0> a = {0, 1, 2, 3, 4};
+
+ int counter = 5;
+ for (ceres::internal::FixedArray<int>::reverse_iterator iter = a.rbegin();
+ iter != a.rend();
+ ++iter) {
+ counter--;
+ EXPECT_EQ(counter, *iter);
+ }
+ EXPECT_EQ(counter, 0);
+
+ counter = 5;
+ for (ceres::internal::FixedArray<int>::const_reverse_iterator iter =
+ a.rbegin();
+ iter != a.rend();
+ ++iter) {
+ counter--;
+ EXPECT_EQ(counter, *iter);
+ }
+ EXPECT_EQ(counter, 0);
+
+ counter = 5;
+ for (auto iter = a.crbegin(); iter != a.crend(); ++iter) {
+ counter--;
+ EXPECT_EQ(counter, *iter);
+ }
+ EXPECT_EQ(counter, 0);
+}
+
+TEST(FixedArrayTest, Fill) {
+ ceres::internal::FixedArray<int, 5 * sizeof(int)> inlined(5);
+ int fill_val = 42;
+ inlined.fill(fill_val);
+ for (int i : inlined) EXPECT_EQ(i, fill_val);
+
+ ceres::internal::FixedArray<int, 0> allocated(5);
+ allocated.fill(fill_val);
+ for (int i : allocated) EXPECT_EQ(i, fill_val);
+
+ // It doesn't do anything, just make sure this compiles.
+ ceres::internal::FixedArray<int> empty(0);
+ empty.fill(fill_val);
+}
+
+// TODO(johnsoncj): Investigate InlinedStorage default initialization in GCC 4.x
+#ifndef __GNUC__
+TEST(FixedArrayTest, DefaultCtorDoesNotValueInit) {
+ using T = char;
+ constexpr auto capacity = 10;
+ using FixedArrType = ceres::internal::FixedArray<T, capacity>;
+ using FixedArrBuffType =
+ typename std::aligned_storage<sizeof(FixedArrType),
+ alignof(FixedArrType)>::type;
+ constexpr auto scrubbed_bits = 0x95;
+ constexpr auto length = capacity / 2;
+
+ FixedArrBuffType buff;
+ std::memset(std::addressof(buff), scrubbed_bits, sizeof(FixedArrBuffType));
+
+ FixedArrType* arr =
+ ::new (static_cast<void*>(std::addressof(buff))) FixedArrType(length);
+ EXPECT_THAT(*arr, testing::Each(scrubbed_bits));
+ arr->~FixedArrType();
+}
+#endif // __GNUC__
+
+// This is a stateful allocator, but the state lives outside of the
+// allocator (in whatever test is using the allocator). This is odd
+// but helps in tests where the allocator is propagated into nested
+// containers - that chain of allocators uses the same state and is
+// thus easier to query for aggregate allocation information.
+template <typename T>
+class CountingAllocator : public std::allocator<T> {
+ public:
+ using Alloc = std::allocator<T>;
+ using pointer = typename Alloc::pointer;
+ using size_type = typename Alloc::size_type;
+
+ CountingAllocator() : bytes_used_(nullptr), instance_count_(nullptr) {}
+ explicit CountingAllocator(int64_t* b)
+ : bytes_used_(b), instance_count_(nullptr) {}
+ CountingAllocator(int64_t* b, int64_t* a)
+ : bytes_used_(b), instance_count_(a) {}
+
+ template <typename U>
+ explicit CountingAllocator(const CountingAllocator<U>& x)
+ : Alloc(x),
+ bytes_used_(x.bytes_used_),
+ instance_count_(x.instance_count_) {}
+
+ pointer allocate(size_type n, const void* const hint = nullptr) {
+ assert(bytes_used_ != nullptr);
+ *bytes_used_ += n * sizeof(T);
+ return Alloc::allocate(n, hint);
+ }
+
+ void deallocate(pointer p, size_type n) {
+ Alloc::deallocate(p, n);
+ assert(bytes_used_ != nullptr);
+ *bytes_used_ -= n * sizeof(T);
+ }
+
+ template <typename... Args>
+ void construct(pointer p, Args&&... args) {
+ Alloc::construct(p, std::forward<Args>(args)...);
+ if (instance_count_) {
+ *instance_count_ += 1;
+ }
+ }
+
+ void destroy(pointer p) {
+ Alloc::destroy(p);
+ if (instance_count_) {
+ *instance_count_ -= 1;
+ }
+ }
+
+ template <typename U>
+ class rebind {
+ public:
+ using other = CountingAllocator<U>;
+ };
+
+ int64_t* bytes_used_;
+ int64_t* instance_count_;
+};
+
+TEST(AllocatorSupportTest, CountInlineAllocations) {
+ constexpr size_t inlined_size = 4;
+ using Alloc = CountingAllocator<int>;
+ using AllocFxdArr = ceres::internal::FixedArray<int, inlined_size, Alloc>;
+
+ int64_t allocated = 0;
+ int64_t active_instances = 0;
+
+ {
+ const int ia[] = {0, 1, 2, 3, 4, 5, 6, 7};
+
+ Alloc alloc(&allocated, &active_instances);
+
+ AllocFxdArr arr(ia, ia + inlined_size, alloc);
+ static_cast<void>(arr);
+ }
+
+ EXPECT_EQ(allocated, 0);
+ EXPECT_EQ(active_instances, 0);
+}
+
+TEST(AllocatorSupportTest, CountOutoflineAllocations) {
+ constexpr size_t inlined_size = 4;
+ using Alloc = CountingAllocator<int>;
+ using AllocFxdArr = ceres::internal::FixedArray<int, inlined_size, Alloc>;
+
+ int64_t allocated = 0;
+ int64_t active_instances = 0;
+
+ {
+ const int ia[] = {0, 1, 2, 3, 4, 5, 6, 7};
+ Alloc alloc(&allocated, &active_instances);
+
+ AllocFxdArr arr(ia, ia + CERES_INTERNAL_ARRAYSIZE(ia), alloc);
+
+ EXPECT_EQ(allocated, arr.size() * sizeof(int));
+ static_cast<void>(arr);
+ }
+
+ EXPECT_EQ(active_instances, 0);
+}
+
+TEST(AllocatorSupportTest, CountCopyInlineAllocations) {
+ constexpr size_t inlined_size = 4;
+ using Alloc = CountingAllocator<int>;
+ using AllocFxdArr = ceres::internal::FixedArray<int, inlined_size, Alloc>;
+
+ int64_t allocated1 = 0;
+ int64_t allocated2 = 0;
+ int64_t active_instances = 0;
+ Alloc alloc(&allocated1, &active_instances);
+ Alloc alloc2(&allocated2, &active_instances);
+
+ {
+ int initial_value = 1;
+
+ AllocFxdArr arr1(inlined_size / 2, initial_value, alloc);
+
+ EXPECT_EQ(allocated1, 0);
+
+ AllocFxdArr arr2(arr1, alloc2);
+
+ EXPECT_EQ(allocated2, 0);
+ static_cast<void>(arr1);
+ static_cast<void>(arr2);
+ }
+
+ EXPECT_EQ(active_instances, 0);
+}
+
+TEST(AllocatorSupportTest, CountCopyOutoflineAllocations) {
+ constexpr size_t inlined_size = 4;
+ using Alloc = CountingAllocator<int>;
+ using AllocFxdArr = ceres::internal::FixedArray<int, inlined_size, Alloc>;
+
+ int64_t allocated1 = 0;
+ int64_t allocated2 = 0;
+ int64_t active_instances = 0;
+ Alloc alloc(&allocated1, &active_instances);
+ Alloc alloc2(&allocated2, &active_instances);
+
+ {
+ int initial_value = 1;
+
+ AllocFxdArr arr1(inlined_size * 2, initial_value, alloc);
+
+ EXPECT_EQ(allocated1, arr1.size() * sizeof(int));
+
+ AllocFxdArr arr2(arr1, alloc2);
+
+ EXPECT_EQ(allocated2, inlined_size * 2 * sizeof(int));
+ static_cast<void>(arr1);
+ static_cast<void>(arr2);
+ }
+
+ EXPECT_EQ(active_instances, 0);
+}
+
+TEST(AllocatorSupportTest, SizeValAllocConstructor) {
+ using testing::AllOf;
+ using testing::Each;
+ using testing::SizeIs;
+
+ constexpr size_t inlined_size = 4;
+ using Alloc = CountingAllocator<int>;
+ using AllocFxdArr = ceres::internal::FixedArray<int, inlined_size, Alloc>;
+
+ {
+ auto len = inlined_size / 2;
+ auto val = 0;
+ int64_t allocated = 0;
+ AllocFxdArr arr(len, val, Alloc(&allocated));
+
+ EXPECT_EQ(allocated, 0);
+ EXPECT_THAT(arr, AllOf(SizeIs(len), Each(0)));
+ }
+
+ {
+ auto len = inlined_size * 2;
+ auto val = 0;
+ int64_t allocated = 0;
+ AllocFxdArr arr(len, val, Alloc(&allocated));
+
+ EXPECT_EQ(allocated, len * sizeof(int));
+ EXPECT_THAT(arr, AllOf(SizeIs(len), Each(0)));
+ }
+}
+
+} // namespace
diff --git a/internal/ceres/gradient_checker_test.cc b/internal/ceres/gradient_checker_test.cc
index 92d7b26..05648fd 100644
--- a/internal/ceres/gradient_checker_test.cc
+++ b/internal/ceres/gradient_checker_test.cc
@@ -219,9 +219,9 @@
// Test that Probe returns true for correct Jacobians.
GoodTestTerm good_term(num_parameters, parameter_sizes.data());
GradientChecker good_gradient_checker(&good_term, NULL, numeric_diff_options);
- EXPECT_TRUE(good_gradient_checker.Probe(parameters.get(), kTolerance, NULL));
+ EXPECT_TRUE(good_gradient_checker.Probe(parameters.data(), kTolerance, NULL));
EXPECT_TRUE(
- good_gradient_checker.Probe(parameters.get(), kTolerance, &results))
+ good_gradient_checker.Probe(parameters.data(), kTolerance, &results))
<< results.error_log;
// Check that results contain sensible data.
@@ -233,9 +233,10 @@
// Test that if the cost function return false, Probe should return false.
good_term.SetReturnValue(false);
- EXPECT_FALSE(good_gradient_checker.Probe(parameters.get(), kTolerance, NULL));
EXPECT_FALSE(
- good_gradient_checker.Probe(parameters.get(), kTolerance, &results))
+ good_gradient_checker.Probe(parameters.data(), kTolerance, NULL));
+ EXPECT_FALSE(
+ good_gradient_checker.Probe(parameters.data(), kTolerance, &results))
<< results.error_log;
// Check that results contain sensible data.
@@ -252,9 +253,9 @@
// Test that Probe returns false for incorrect Jacobians.
BadTestTerm bad_term(num_parameters, parameter_sizes.data());
GradientChecker bad_gradient_checker(&bad_term, NULL, numeric_diff_options);
- EXPECT_FALSE(bad_gradient_checker.Probe(parameters.get(), kTolerance, NULL));
+ EXPECT_FALSE(bad_gradient_checker.Probe(parameters.data(), kTolerance, NULL));
EXPECT_FALSE(
- bad_gradient_checker.Probe(parameters.get(), kTolerance, &results));
+ bad_gradient_checker.Probe(parameters.data(), kTolerance, &results));
// Check that results contain sensible data.
ASSERT_EQ(results.return_value, true);
@@ -264,7 +265,7 @@
EXPECT_FALSE(results.error_log.empty());
// Setting a high threshold should make the test pass.
- EXPECT_TRUE(bad_gradient_checker.Probe(parameters.get(), 1.0, &results));
+ EXPECT_TRUE(bad_gradient_checker.Probe(parameters.data(), 1.0, &results));
// Check that results contain sensible data.
ASSERT_EQ(results.return_value, true);
diff --git a/internal/ceres/local_parameterization.cc b/internal/ceres/local_parameterization.cc
index a7fe4a1..02ed4c9 100644
--- a/internal/ceres/local_parameterization.cc
+++ b/internal/ceres/local_parameterization.cc
@@ -368,11 +368,11 @@
const int local_size = param->LocalSize();
const int global_size = param->GlobalSize();
- if (!param->ComputeJacobian(x + x_cursor, buffer.get())) {
+ if (!param->ComputeJacobian(x + x_cursor, buffer.data())) {
return false;
}
jacobian.block(x_cursor, delta_cursor, global_size, local_size)
- = MatrixRef(buffer.get(), global_size, local_size);
+ = MatrixRef(buffer.data(), global_size, local_size);
delta_cursor += local_size;
x_cursor += global_size;
diff --git a/internal/ceres/residual_block.cc b/internal/ceres/residual_block.cc
index 7582e92..7bfcc29 100644
--- a/internal/ceres/residual_block.cc
+++ b/internal/ceres/residual_block.cc
@@ -35,13 +35,13 @@
#include <cstddef>
#include <vector>
#include "ceres/corrector.h"
-#include "ceres/parameter_block.h"
-#include "ceres/residual_block_utils.h"
#include "ceres/cost_function.h"
#include "ceres/internal/eigen.h"
#include "ceres/internal/fixed_array.h"
#include "ceres/local_parameterization.h"
#include "ceres/loss_function.h"
+#include "ceres/parameter_block.h"
+#include "ceres/residual_block_utils.h"
#include "ceres/small_blas.h"
using Eigen::Dynamic;
@@ -102,16 +102,17 @@
// Invalidate the evaluation buffers so that we can check them after
// the CostFunction::Evaluate call, to see if all the return values
// that were required were written to and that they are finite.
- double** eval_jacobians = (jacobians != NULL) ? global_jacobians.get() : NULL;
+ double** eval_jacobians =
+ (jacobians != NULL) ? global_jacobians.data() : NULL;
InvalidateEvaluation(*this, cost, residuals, eval_jacobians);
- if (!cost_function_->Evaluate(parameters.get(), residuals, eval_jacobians)) {
+ if (!cost_function_->Evaluate(parameters.data(), residuals, eval_jacobians)) {
return false;
}
if (!IsEvaluationValid(*this,
- parameters.get(),
+ parameters.data(),
cost,
residuals,
eval_jacobians)) {
@@ -122,7 +123,7 @@
"residual and jacobians that were requested or there was a non-finite value (nan/infinite)\n" // NOLINT
"generated during the or jacobian computation. \n\n" +
EvaluationToString(*this,
- parameters.get(),
+ parameters.data(),
cost,
residuals,
eval_jacobians);
diff --git a/internal/ceres/schur_eliminator_impl.h b/internal/ceres/schur_eliminator_impl.h
index d754d9d..5d65869 100644
--- a/internal/ceres/schur_eliminator_impl.h
+++ b/internal/ceres/schur_eliminator_impl.h
@@ -247,7 +247,8 @@
}
FixedArray<double, 8> g(e_block_size);
- typename EigenTypes<kEBlockSize>::VectorRef gref(g.get(), e_block_size);
+ typename EigenTypes<kEBlockSize>::VectorRef gref(g.data(),
+ e_block_size);
gref.setZero();
// We are going to be computing
@@ -263,7 +264,7 @@
// in this chunk (g) and add the outer product of the f_blocks to
// Schur complement (S += F'F).
ChunkDiagonalBlockAndGradient(
- chunk, A, b, chunk.start, &ete, g.get(), buffer, lhs);
+ chunk, A, b, chunk.start, &ete, g.data(), buffer, lhs);
// Normally one wouldn't compute the inverse explicitly, but
// e_block_size will typically be a small number like 3, in
@@ -284,9 +285,9 @@
inverse_ete.data(),
e_block_size,
e_block_size,
- g.get(),
- inverse_ete_g.get());
- UpdateRhs(chunk, A, b, chunk.start, inverse_ete_g.get(), rhs);
+ g.data(),
+ inverse_ete_g.data());
+ UpdateRhs(chunk, A, b, chunk.start, inverse_ete_g.data(), rhs);
}
// S -= F'E(E'E)^{-1}E'F
@@ -340,9 +341,9 @@
FixedArray<double, 8> sj(row.block.size);
- typename EigenTypes<kRowBlockSize>::VectorRef(sj.get(), row.block.size) =
- typename EigenTypes<kRowBlockSize>::ConstVectorRef
- (b + bs->rows[chunk.start + j].block.position, row.block.size);
+ typename EigenTypes<kRowBlockSize>::VectorRef(sj.data(), row.block.size) =
+ typename EigenTypes<kRowBlockSize>::ConstVectorRef(
+ b + bs->rows[chunk.start + j].block.position, row.block.size);
for (int c = 1; c < row.cells.size(); ++c) {
const int f_block_id = row.cells[c].block_id;
@@ -352,12 +353,12 @@
MatrixVectorMultiply<kRowBlockSize, kFBlockSize, -1>(
values + row.cells[c].position, row.block.size, f_block_size,
z + lhs_row_layout_[r_block],
- sj.get());
+ sj.data());
}
MatrixTransposeVectorMultiply<kRowBlockSize, kEBlockSize, 1>(
values + e_cell.position, row.block.size, e_block_size,
- sj.get(),
+ sj.data(),
y_ptr);
MatrixTransposeMatrixMultiply
