TEST threaded_executor_test SOURCES ThreadedExecutorTest.cpp
TEST unbounded_blocking_queue_test SOURCES UnboundedBlockingQueueTest.cpp
+ DIRECTORY container/test/
+ TEST enumerate_test SOURCES EnumerateTest.cpp
+ TEST evicting_cache_map_test SOURCES EvictingCacheMapTest.cpp
+ TEST foreach_test SOURCES ForeachTest.cpp
+ TEST merge_test SOURCES MergeTest.cpp
+ TEST sparse_byte_set_test SOURCES SparseByteSetTest.cpp
+
DIRECTORY experimental/test/
TEST autotimer_test SOURCES AutoTimerTest.cpp
TEST bits_test_2 SOURCES BitsTest.cpp
TEST dynamic_converter_test SOURCES DynamicConverterTest.cpp
TEST dynamic_other_test SOURCES DynamicOtherTest.cpp
TEST endian_test SOURCES EndianTest.cpp
- TEST enumerate_test SOURCES EnumerateTest.cpp
- TEST evicting_cache_map_test SOURCES EvictingCacheMapTest.cpp
TEST exception_test SOURCES ExceptionTest.cpp
TEST exception_wrapper_test SOURCES ExceptionWrapperTest.cpp
TEST expected_test SOURCES ExpectedTest.cpp
TEST file_util_test HANGING
SOURCES FileUtilTest.cpp
TEST fingerprint_test SOURCES FingerprintTest.cpp
- TEST foreach_test SOURCES ForeachTest.cpp
TEST format_other_test SOURCES FormatOtherTest.cpp
TEST format_test SOURCES FormatTest.cpp
TEST function_scheduler_test SOURCES FunctionSchedulerTest.cpp
TEST memcpy_test SOURCES MemcpyTest.cpp
TEST memory_idler_test SOURCES MemoryIdlerTest.cpp
TEST memory_test SOURCES MemoryTest.cpp
- TEST merge SOURCES MergeTest.cpp
TEST move_wrapper_test SOURCES MoveWrapperTest.cpp
TEST mpmc_pipeline_test SOURCES MPMCPipelineTest.cpp
TEST mpmc_queue_test SLOW
TEST singletonvault_c_test SOURCES SingletonVaultCTest.cpp
TEST small_vector_test SOURCES small_vector_test.cpp
TEST sorted_vector_types_test SOURCES sorted_vector_test.cpp
- TEST sparse_byte_set_test SOURCES SparseByteSetTest.cpp
TEST string_test SOURCES StringTest.cpp
TEST synchronized_test SOURCES SynchronizedTest.cpp
TEST thread_cached_int_test SOURCES ThreadCachedIntTest.cpp
#include <stdexcept>
#include <folly/AtomicHashArray.h>
-#include <folly/Foreach.h>
#include <folly/Hash.h>
#include <folly/Likely.h>
#include <folly/ThreadCachedInt.h>
+#include <folly/container/Foreach.h>
namespace folly {
#include <boost/regex.hpp>
-#include <folly/Foreach.h>
#include <folly/MapUtil.h>
#include <folly/String.h>
+#include <folly/container/Foreach.h>
#include <folly/json.h>
using namespace std;
+++ /dev/null
-/*
- * Copyright 2017 Facebook, Inc.
- *
- * 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
- *
- * http://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.
- */
-
-#pragma once
-
-#include <iterator>
-#include <memory>
-
-#include <folly/portability/SysTypes.h>
-
-/**
- * Similar to Python's enumerate(), folly::enumerate() can be used to
- * iterate a range with a for-range loop, and it also allows to
- * retrieve the count of iterations so far.
- *
- * For example:
- *
- * for (auto it : folly::enumerate(vec)) {
- * // *it is a reference to the current element. Const if vec is const.
- * // it->member can be used as well.
- * // it.index contains the iteration count.
- * }
- *
- * If the iteration variable is const, the reference is too.
- *
- * for (const auto it : folly::enumerate(vec)) {
- * // *it is always a const reference.
- * }
- *
- * @author Giuseppe Ottaviano <ott@fb.com>
- */
-
-namespace folly {
-
-namespace detail {
-
-template <class T>
-struct MakeConst {
- using type = const T;
-};
-template <class T>
-struct MakeConst<T&> {
- using type = const T&;
-};
-template <class T>
-struct MakeConst<T*> {
- using type = const T*;
-};
-
-// Raw pointers don't have an operator->() member function, so the
-// second overload will be SFINAEd out in that case. Otherwise, the
-// second is preferred in the partial order for getPointer(_, 0).
-template <class Iterator>
-auto getPointer(const Iterator& it, long) -> decltype(std::addressof(*it)) {
- return std::addressof(*it);
-}
-template <class Iterator>
-auto getPointer(const Iterator& it, int) -> decltype(it.operator->()) {
- return it.operator->();
-}
-
-template <class Iterator>
-class Enumerator {
- public:
- explicit Enumerator(Iterator it) : it_(std::move(it)) {}
-
- class Proxy {
- public:
- using difference_type = ssize_t;
- using value_type = typename std::iterator_traits<Iterator>::value_type;
- using reference = typename std::iterator_traits<Iterator>::reference;
- using pointer = typename std::iterator_traits<Iterator>::pointer;
- using iterator_category = std::input_iterator_tag;
-
- explicit Proxy(const Enumerator* e) : it_(e->it_), index(e->idx_) {}
-
- // Non-const Proxy: Forward constness from Iterator.
- reference operator*() {
- return *it_;
- }
- pointer operator->() {
- return getPointer(it_, 0);
- }
-
- // Const Proxy: Force const references.
- typename MakeConst<reference>::type operator*() const {
- return *it_;
- }
- typename MakeConst<pointer>::type operator->() const {
- return getPointer(it_, 0);
- }
-
- private:
- const Iterator& it_;
-
- public:
- const size_t index;
- };
-
- Proxy operator*() const {
- return Proxy(this);
- }
-
- Enumerator& operator++() {
- ++it_;
- ++idx_;
- return *this;
- }
-
- template <typename OtherIterator>
- bool operator==(const Enumerator<OtherIterator>& rhs) {
- return it_ == rhs.it_;
- }
-
- template <typename OtherIterator>
- bool operator!=(const Enumerator<OtherIterator>& rhs) {
- return !(*this == rhs);
- }
-
- private:
- template <typename OtherIterator>
- friend class Enumerator;
-
- Iterator it_;
- size_t idx_ = 0;
-};
-
-template <class Range>
-class RangeEnumerator {
- Range r_;
- using BeginIteratorType = decltype(std::declval<Range>().begin());
- using EndIteratorType = decltype(std::declval<Range>().end());
-
- public:
- explicit RangeEnumerator(Range&& r) : r_(std::forward<Range>(r)) {}
-
- Enumerator<BeginIteratorType> begin() {
- return Enumerator<BeginIteratorType>(r_.begin());
- }
- Enumerator<EndIteratorType> end() {
- return Enumerator<EndIteratorType>(r_.end());
- }
-};
-
-} // namespace detail
-
-template <class Range>
-detail::RangeEnumerator<Range> enumerate(Range&& r) {
- return detail::RangeEnumerator<Range>(std::forward<Range>(r));
-}
-
-} // namespace folly
+++ /dev/null
-/*
- * Copyright 2017 Facebook, Inc.
- *
- * 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
- *
- * http://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.
- */
-
-#pragma once
-
-#include <algorithm>
-#include <exception>
-#include <functional>
-
-#include <boost/intrusive/list.hpp>
-#include <boost/intrusive/unordered_set.hpp>
-#include <boost/iterator/iterator_adaptor.hpp>
-#include <boost/utility.hpp>
-
-#include <folly/portability/BitsFunctexcept.h>
-
-namespace folly {
-
-/**
- * A general purpose LRU evicting cache. Designed to support constant time
- * set/get operations. It maintains a doubly linked list of items that are
- * threaded through an index (a hash map). The access ordered is maintained
- * on the list by moving an element to the front of list on a get. New elements
- * are added to the front of the list. The index size is set to half the
- * capacity (setting capacity to 0 is a special case. see notes at the end of
- * this section). So assuming uniform distribution of keys, set/get are both
- * constant time operations.
- *
- * On reaching capacity limit, clearSize_ LRU items are evicted at a time. If
- * a callback is specified with setPruneHook, it is invoked for each eviction.
- *
- * This is NOT a thread-safe implementation.
- *
- * Configurability: capacity of the cache, number of items to evict, eviction
- * callback and the hasher to hash the keys can all be supplied by the caller.
- *
- * If at a given state, N1 - N6 are the nodes in MRU to LRU order and hashing
- * to index keys as {(N1,N5)->H1, (N4,N5,N5)->H2, N3->Hi}, the datastructure
- * layout is as below. N1 .. N6 is a list threaded through the hash.
- * Assuming, each the number of nodes hashed to each index key is bounded, the
- * following operations run in constant time.
- * i) get computes the index key, walks the list of elements hashed to
- * the key and moves it to the front of the list, if found.
- * ii) set inserts a new node into the list and places the same node on to the
- * list of elements hashing to the corresponding index key.
- * ii) prune deletes nodes from the end of the list as well from the index.
- *
- * +----+ +----+ +----+
- * | H1 | <-> | N1 | <-> | N5 |
- * +----+ +----+ +----+
- * ^ ^ ^
- * | ___/ \
- * | / \
- * |_ /________ \___
- * / | \
- * / | \
- * v v v
- * +----+ +----+ +----+ +----+
- * | H2 | <-> | N4 | <-> | N2 | <-> | N6 |
- * +----+ +----+ +----+ +----+
- * . ^ ^
- * . | |
- * . | |
- * . | _____|
- * . | /
- * v v
- * +----+ +----+
- * | Hi | <-> | N3 |
- * +----+ +----+
- *
- * N.B 1 : Changing the capacity with setMaxSize does not change the index size
- * and it could end up in too many elements indexed to the same slot in index.
- * The set/get performance will get worse in this case. So it is best to avoid
- * resizing.
- *
- * N.B 2 : Setting capacity to 0, using setMaxSize or initialization, turns off
- * evictions based on sizeof the cache making it an INFINITE size cache
- * unless evictions of LRU items are triggered by calling prune() by clients
- * (using their own eviction criteria).
- */
-template <class TKey, class TValue, class THash = std::hash<TKey>>
-class EvictingCacheMap {
- private:
- // typedefs for brevity
- struct Node;
- typedef boost::intrusive::link_mode<boost::intrusive::safe_link> link_mode;
- typedef boost::intrusive::unordered_set<Node> NodeMap;
- typedef boost::intrusive::list<Node> NodeList;
- typedef std::pair<const TKey, TValue> TPair;
-
- public:
- typedef std::function<void(TKey, TValue&&)> PruneHookCall;
-
- // iterator base : returns TPair on dereference
- template <typename Value, typename TIterator>
- class iterator_base
- : public boost::iterator_adaptor<iterator_base<Value, TIterator>,
- TIterator,
- Value,
- boost::bidirectional_traversal_tag > {
- public:
- iterator_base() {
- }
- explicit iterator_base(TIterator it)
- : iterator_base::iterator_adaptor_(it) {
- }
- Value& dereference() const {
- return this->base_reference()->pr;
- }
- };
-
- // iterators
- typedef iterator_base<
- TPair, typename NodeList::iterator> iterator;
- typedef iterator_base<
- const TPair, typename NodeList::const_iterator> const_iterator;
- typedef iterator_base<
- TPair, typename NodeList::reverse_iterator> reverse_iterator;
- typedef iterator_base<
- const TPair,
- typename NodeList::const_reverse_iterator> const_reverse_iterator;
-
- /**
- * Construct a EvictingCacheMap
- * @param maxSize maximum size of the cache map. Once the map size exceeds
- * maxSize, the map will begin to evict.
- * @param clearSize the number of elements to clear at a time when the
- * eviction size is reached.
- */
- explicit EvictingCacheMap(std::size_t maxSize, std::size_t clearSize = 1)
- : nIndexBuckets_(std::max(maxSize / 2, std::size_t(kMinNumIndexBuckets))),
- indexBuckets_(new typename NodeMap::bucket_type[nIndexBuckets_]),
- indexTraits_(indexBuckets_.get(), nIndexBuckets_),
- index_(indexTraits_),
- maxSize_(maxSize),
- clearSize_(clearSize) { }
-
- EvictingCacheMap(const EvictingCacheMap&) = delete;
- EvictingCacheMap& operator=(const EvictingCacheMap&) = delete;
- EvictingCacheMap(EvictingCacheMap&&) = default;
- EvictingCacheMap& operator=(EvictingCacheMap&&) = default;
-
- ~EvictingCacheMap() {
- setPruneHook(nullptr);
- // ignore any potential exceptions from pruneHook_
- pruneWithFailSafeOption(size(), nullptr, true);
- }
-
- /**
- * Adjust the max size of EvictingCacheMap. Note that this does not update
- * nIndexBuckets_ accordingly. This API can cause performance to get very
- * bad, e.g., the nIndexBuckets_ is still 100 after maxSize is updated to 1M.
- *
- * Calling this function with an arugment of 0 removes the limit on the cache
- * size and elements are not evicted unless clients explictly call prune.
- *
- * If you intend to resize dynamically using this, then picking an index size
- * that works well and initializing with corresponding maxSize is the only
- * reasonable option.
- *
- * @param maxSize new maximum size of the cache map.
- * @param pruneHook callback to use on eviction.
- */
- void setMaxSize(size_t maxSize, PruneHookCall pruneHook = nullptr) {
- if (maxSize != 0 && maxSize < size()) {
- // Prune the excess elements with our new constraints.
- prune(std::max(size() - maxSize, clearSize_), pruneHook);
- }
- maxSize_ = maxSize;
- }
-
- size_t getMaxSize() const {
- return maxSize_;
- }
-
- void setClearSize(size_t clearSize) {
- clearSize_ = clearSize;
- }
-
- /**
- * Check for existence of a specific key in the map. This operation has
- * no effect on LRU order.
- * @param key key to search for
- * @return true if exists, false otherwise
- */
- bool exists(const TKey& key) const {
- return findInIndex(key) != index_.end();
- }
-
- /**
- * Get the value associated with a specific key. This function always
- * promotes a found value to the head of the LRU.
- * @param key key associated with the value
- * @return the value if it exists
- * @throw std::out_of_range exception of the key does not exist
- */
- TValue& get(const TKey& key) {
- auto it = find(key);
- if (it == end()) {
- std::__throw_out_of_range("Key does not exist");
- }
- return it->second;
- }
-
- /**
- * Get the iterator associated with a specific key. This function always
- * promotes a found value to the head of the LRU.
- * @param key key to associate with value
- * @return the iterator of the object (a std::pair of const TKey, TValue) or
- * end() if it does not exist
- */
- iterator find(const TKey& key) {
- auto it = findInIndex(key);
- if (it == index_.end()) {
- return end();
- }
- lru_.erase(lru_.iterator_to(*it));
- lru_.push_front(*it);
- return iterator(lru_.iterator_to(*it));
- }
-
- /**
- * Get the value associated with a specific key. This function never
- * promotes a found value to the head of the LRU.
- * @param key key associated with the value
- * @return the value if it exists
- * @throw std::out_of_range exception of the key does not exist
- */
- const TValue& getWithoutPromotion(const TKey& key) const {
- auto it = findWithoutPromotion(key);
- if (it == end()) {
- std::__throw_out_of_range("Key does not exist");
- }
- return it->second;
- }
-
- TValue& getWithoutPromotion(const TKey& key) {
- auto const& cThis = *this;
- return const_cast<TValue&>(cThis.getWithoutPromotion(key));
- }
-
- /**
- * Get the iterator associated with a specific key. This function never
- * promotes a found value to the head of the LRU.
- * @param key key to associate with value
- * @return the iterator of the object (a std::pair of const TKey, TValue) or
- * end() if it does not exist
- */
- const_iterator findWithoutPromotion(const TKey& key) const {
- auto it = findInIndex(key);
- return (it == index_.end()) ? end() : const_iterator(lru_.iterator_to(*it));
- }
-
- iterator findWithoutPromotion(const TKey& key) {
- auto it = findInIndex(key);
- return (it == index_.end()) ? end() : iterator(lru_.iterator_to(*it));
- }
-
- /**
- * Erase the key-value pair associated with key if it exists.
- * @param key key associated with the value
- * @return true if the key existed and was erased, else false
- */
- bool erase(const TKey& key) {
- auto it = findInIndex(key);
- if (it == index_.end()) {
- return false;
- }
- auto node = &(*it);
- std::unique_ptr<Node> nptr(node);
- lru_.erase(lru_.iterator_to(*node));
- index_.erase(it);
- return true;
- }
-
- /**
- * Set a key-value pair in the dictionary
- * @param key key to associate with value
- * @param value value to associate with the key
- * @param promote boolean flag indicating whether or not to move something
- * to the front of an LRU. This only really matters if you're setting
- * a value that already exists.
- * @param pruneHook callback to use on eviction (if it occurs).
- */
- void set(const TKey& key,
- TValue value,
- bool promote = true,
- PruneHookCall pruneHook = nullptr) {
- auto it = findInIndex(key);
- if (it != index_.end()) {
- it->pr.second = std::move(value);
- if (promote) {
- lru_.erase(lru_.iterator_to(*it));
- lru_.push_front(*it);
- }
- } else {
- auto node = new Node(key, std::move(value));
- index_.insert(*node);
- lru_.push_front(*node);
-
- // no evictions if maxSize_ is 0 i.e. unlimited capacity
- if (maxSize_ > 0 && size() > maxSize_) {
- prune(clearSize_, pruneHook);
- }
- }
- }
-
- /**
- * Get the number of elements in the dictionary
- * @return the size of the dictionary
- */
- std::size_t size() const {
- return index_.size();
- }
-
- /**
- * Typical empty function
- * @return true if empty, false otherwise
- */
- bool empty() const {
- return index_.empty();
- }
-
- void clear(PruneHookCall pruneHook = nullptr) {
- prune(size(), pruneHook);
- }
-
- /**
- * Set the prune hook, which is the function invoked on the key and value
- * on each eviction. Will throw If the pruneHook throws, unless the
- * EvictingCacheMap object is being destroyed in which case it will
- * be ignored.
- * @param pruneHook new callback to use on eviction.
- * @param promote boolean flag indicating whether or not to move something
- * to the front of an LRU.
- * @return the iterator of the object (a std::pair of const TKey, TValue) or
- * end() if it does not exist
- */
- void setPruneHook(PruneHookCall pruneHook) {
- pruneHook_ = pruneHook;
- }
-
-
- /**
- * Prune the minimum of pruneSize and size() from the back of the LRU.
- * Will throw if pruneHook throws.
- * @param pruneSize minimum number of elements to prune
- * @param pruneHook a custom pruneHook function
- */
- void prune(std::size_t pruneSize, PruneHookCall pruneHook = nullptr) {
- // do not swallow exceptions for prunes not triggered from destructor
- pruneWithFailSafeOption(pruneSize, pruneHook, false);
- }
-
- // Iterators and such
- iterator begin() {
- return iterator(lru_.begin());
- }
- iterator end() {
- return iterator(lru_.end());
- }
- const_iterator begin() const {
- return const_iterator(lru_.begin());
- }
- const_iterator end() const {
- return const_iterator(lru_.end());
- }
-
- const_iterator cbegin() const {
- return const_iterator(lru_.cbegin());
- }
- const_iterator cend() const {
- return const_iterator(lru_.cend());
- }
-
- reverse_iterator rbegin() {
- return reverse_iterator(lru_.rbegin());
- }
- reverse_iterator rend() {
- return reverse_iterator(lru_.rend());
- }
-
- const_reverse_iterator rbegin() const {
- return const_reverse_iterator(lru_.rbegin());
- }
- const_reverse_iterator rend() const {
- return const_reverse_iterator(lru_.rend());
- }
-
- const_reverse_iterator crbegin() const {
- return const_reverse_iterator(lru_.crbegin());
- }
- const_reverse_iterator crend() const {
- return const_reverse_iterator(lru_.crend());
- }
-
- private:
- struct Node
- : public boost::intrusive::unordered_set_base_hook<link_mode>,
- public boost::intrusive::list_base_hook<link_mode> {
- Node(const TKey& key, TValue&& value)
- : pr(std::make_pair(key, std::move(value))) {
- }
- TPair pr;
- friend bool operator==(const Node& lhs, const Node& rhs) {
- return lhs.pr.first == rhs.pr.first;
- }
- friend std::size_t hash_value(const Node& node) {
- return THash()(node.pr.first);
- }
- };
-
- struct KeyHasher {
- std::size_t operator()(const Node& node) {
- return THash()(node.pr.first);
- }
- std::size_t operator()(const TKey& key) {
- return THash()(key);
- }
- };
-
- struct KeyValueEqual {
- bool operator()(const TKey& lhs, const Node& rhs) {
- return lhs == rhs.pr.first;
- }
- bool operator()(const Node& lhs, const TKey& rhs) {
- return lhs.pr.first == rhs;
- }
- };
-
- /**
- * Get the iterator in in the index associated with a specific key. This is
- * merely a search in the index and does not promote the object.
- * @param key key to associate with value
- * @return the NodeMap::iterator to the Node containing the object
- * (a std::pair of const TKey, TValue) or index_.end() if it does not exist
- */
- typename NodeMap::iterator findInIndex(const TKey& key) {
- return index_.find(key, KeyHasher(), KeyValueEqual());
- }
-
- typename NodeMap::const_iterator findInIndex(const TKey& key) const {
- return index_.find(key, KeyHasher(), KeyValueEqual());
- }
-
- /**
- * Prune the minimum of pruneSize and size() from the back of the LRU.
- * @param pruneSize minimum number of elements to prune
- * @param pruneHook a custom pruneHook function
- * @param failSafe true if exceptions are to ignored, false by default
- */
- void pruneWithFailSafeOption(std::size_t pruneSize,
- PruneHookCall pruneHook, bool failSafe) {
- auto& ph = (nullptr == pruneHook) ? pruneHook_ : pruneHook;
-
- for (std::size_t i = 0; i < pruneSize && !lru_.empty(); i++) {
- auto *node = &(*lru_.rbegin());
- std::unique_ptr<Node> nptr(node);
-
- lru_.erase(lru_.iterator_to(*node));
- index_.erase(index_.iterator_to(*node));
- if (ph) {
- try {
- ph(node->pr.first, std::move(node->pr.second));
- } catch (...) {
- if (!failSafe) {
- throw;
- }
- }
- }
- }
- }
-
- static const std::size_t kMinNumIndexBuckets = 100;
- PruneHookCall pruneHook_;
- std::size_t nIndexBuckets_;
- std::unique_ptr<typename NodeMap::bucket_type[]> indexBuckets_;
- typename NodeMap::bucket_traits indexTraits_;
- NodeMap index_;
- NodeList lru_;
- std::size_t maxSize_;
- std::size_t clearSize_;
-};
-
-} // namespace folly
+++ /dev/null
-/*
- * Copyright 2017-present Facebook, Inc.
- *
- * 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
- *
- * http://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 <cassert>
-#include <cstdint>
-#include <initializer_list>
-#include <iterator>
-#include <tuple>
-#include <type_traits>
-#include <utility>
-
-#include <folly/Portability.h>
-#include <folly/Traits.h>
-
-namespace folly {
-
-namespace for_each_detail {
-
-namespace adl {
-
-/* using override */
-using std::begin;
-/* using override */
-using std::end;
-/* using override */
-using std::get;
-
-/**
- * The adl_ functions below lookup the function name in the namespace of the
- * type of the object being passed into the function. If no function with
- * that name exists for the passed object then the default std:: versions are
- * going to be called
- */
-template <std::size_t Index, typename Type>
-auto adl_get(Type&& instance) -> decltype(get<Index>(std::declval<Type>())) {
- return get<Index>(std::forward<Type>(instance));
-}
-template <typename Type>
-auto adl_begin(Type&& instance) -> decltype(begin(instance)) {
- return begin(instance);
-}
-template <typename Type>
-auto adl_end(Type&& instance) -> decltype(end(instance)) {
- return end(instance);
-}
-
-} // namespace adl
-
-/**
- * Enable if the range supports fetching via non member get<>()
- */
-template <typename T>
-using EnableIfNonMemberGetFound =
- void_t<decltype(adl::adl_get<0>(std::declval<T>()))>;
-/**
- * Enable if the range supports fetching via a member get<>()
- */
-template <typename T>
-using EnableIfMemberGetFound =
- void_t<decltype(std::declval<T>().template get<0>())>;
-
-/**
- * A get that tries ADL get<> first and if that is not found tries to execute
- * a member function get<> on the instance, just as proposed by the structured
- * bindings proposal here 11.5.3
- * http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4659.pdf
- */
-template <std::size_t Index, typename Type, typename = void>
-struct Get {
- template <typename T>
- static auto impl(T&& instance)
- -> decltype(adl::adl_get<Index>(std::declval<T>())) {
- return adl::adl_get<Index>(std::forward<T>(instance));
- }
-};
-template <std::size_t Index, typename Type>
-struct Get<Index, Type, EnableIfMemberGetFound<Type>> {
- template <typename T>
- static auto impl(T&& instance)
- -> decltype(std::declval<T>().template get<Index>()) {
- return std::forward<T>(instance).template get<Index>();
- }
-};
-
-/**
- * Concepts-ish
- */
-/**
- * Check if the range is a tuple or a range
- */
-template <typename Type, typename T = typename std::decay<Type>::type>
-using EnableIfTuple = void_t<
- decltype(Get<0, T>::impl(std::declval<T>())),
- decltype(std::tuple_size<T>::value)>;
-
-/**
- * Check if the range is a range
- */
-template <typename Type, typename T = typename std::decay<Type>::type>
-using EnableIfRange = void_t<
- decltype(adl::adl_begin(std::declval<T>())),
- decltype(adl::adl_end(std::declval<T>()))>;
-
-/**
- * Forwards the return value of the first element of the range, used to
- * determine the type of the first element in the range in SFINAE use cases
- */
-template <typename Sequence, typename = void>
-struct DeclvalSequence {
- using type = decltype(*(adl::adl_begin(std::declval<Sequence>())));
-};
-
-template <typename Sequence>
-struct DeclvalSequence<Sequence, EnableIfTuple<Sequence>> {
- using type = decltype(Get<0, Sequence>::impl(std::declval<Sequence>()));
-};
-
-/**
- * Check if the functor accepts one or two arguments, one of the first element
- * in the range, assuming that all the other elements can also be passed to the
- * functor, and the second being an instantiation of std::integral_constant,
- * and the third being an instantiation of LoopControl, to provide
- * breakability to the loop
- */
-template <typename Sequence, typename Func>
-using EnableIfAcceptsOneArgument = void_t<decltype(std::declval<Func>()(
- std::declval<typename DeclvalSequence<Sequence>::type>()))>;
-template <typename Sequence, typename Func>
-using EnableIfAcceptsTwoArguments = void_t<decltype(std::declval<Func>()(
- std::declval<typename DeclvalSequence<Sequence>::type>(),
- std::integral_constant<std::size_t, 0>{}))>;
-template <typename Sequence, typename Func>
-using EnableIfAcceptsThreeArguments = void_t<decltype(std::declval<Func>()(
- std::declval<typename DeclvalSequence<Sequence>::type>(),
- std::integral_constant<std::size_t, 0>{},
- adl::adl_begin(std::declval<Sequence>())))>;
-template <typename Sequence, typename Func>
-using EnableIfBreaksRange = std::enable_if_t<std::is_same<
- typename std::decay<decltype(std::declval<Func>()(
- std::declval<typename DeclvalSequence<Sequence>::type>(),
- std::size_t{0},
- adl::adl_begin(std::declval<Sequence>())))>::type,
- LoopControl>::value>;
-template <typename Sequence, typename Func>
-using EnableIfBreaksTuple = std::enable_if_t<std::is_same<
- typename std::decay<decltype(std::declval<Func>()(
- std::declval<typename DeclvalSequence<Sequence>::type>(),
- std::integral_constant<std::size_t, 0>{}))>::type,
- LoopControl>::value>;
-/**
- * Enables if the sequence has random access iterators
- */
-template <typename Sequence>
-using EnableIfRandomAccessIterators = std::enable_if_t<std::is_same<
- typename std::iterator_traits<typename std::decay<decltype(
- adl::adl_begin(std::declval<Sequence>()))>::type>::iterator_category,
- std::random_access_iterator_tag>::value>;
-template <typename Sequence, typename Index>
-using EnableIfHasIndexingOperator =
- void_t<decltype(std::declval<Sequence>()[std::declval<Index>()])>;
-
-/**
- * Implementation for the range iteration, this provides specializations in
- * the case where the function returns a break or continue.
- */
-template <typename Seq, typename F, typename = void>
-struct ForEachRange {
- template <typename Sequence, typename Func>
- static void impl(Sequence&& range, Func& func) {
- auto first = adl::adl_begin(range);
- auto last = adl::adl_end(range);
- for (auto index = std::size_t{0}; first != last; ++index) {
- auto next = std::next(first);
- func(*first, index, first);
- first = next;
- }
- }
-};
-
-template <typename Seq, typename F>
-struct ForEachRange<Seq, F, EnableIfBreaksRange<Seq, F>> {
- template <typename Sequence, typename Func>
- static void impl(Sequence&& range, Func& func) {
- auto first = adl::adl_begin(range);
- auto last = adl::adl_end(range);
- for (auto index = std::size_t{0}; first != last; ++index) {
- auto next = std::next(first);
- if (loop_break == func(*first, index, first)) {
- break;
- }
- first = next;
- }
- }
-};
-
-/**
- * Implementations for the runtime function
- */
-template <
- typename Sequence,
- typename Func,
- EnableIfAcceptsThreeArguments<Sequence, Func>* = nullptr>
-void for_each_range_impl(Sequence&& range, Func& func) {
- ForEachRange<Sequence, Func>::impl(std::forward<Sequence>(range), func);
-}
-template <
- typename Sequence,
- typename Func,
- EnableIfAcceptsTwoArguments<Sequence, Func>* = nullptr>
-void for_each_range_impl(Sequence&& range, Func& func) {
- // make a three arg adaptor for the function passed in so that the main
- // implementation function can be used
- auto three_arg_adaptor = [&func](
- auto&& ele, auto index, auto) -> decltype(auto) {
- return func(std::forward<decltype(ele)>(ele), index);
- };
- for_each_range_impl(std::forward<Sequence>(range), three_arg_adaptor);
-}
-
-template <
- typename Sequence,
- typename Func,
- EnableIfAcceptsOneArgument<Sequence, Func>* = nullptr>
-void for_each_range_impl(Sequence&& range, Func& func) {
- // make a three argument adaptor for the function passed in that just ignores
- // the second and third argument
- auto three_arg_adaptor = [&func](auto&& ele, auto, auto) -> decltype(auto) {
- return func(std::forward<decltype(ele)>(ele));
- };
- for_each_range_impl(std::forward<Sequence>(range), three_arg_adaptor);
-}
-
-/**
- * Handlers for iteration
- */
-/**
- * The class provides a way to tell whether the function passed in to the
- * algorithm returns an instance of LoopControl, if it does then the break-able
- * implementation will be used. If the function provided to the algorithm
- * does not use the break API, then the basic no break, 0 overhead
- * implementation will be used
- */
-template <typename Seq, typename F, typename = void>
-struct ForEachTupleImpl {
- template <typename Sequence, typename Func, std::size_t... Indices>
- static void
- impl(Sequence&& seq, Func& func, std::index_sequence<Indices...>) {
- // unroll the loop in an initializer list construction parameter expansion
- // pack
- static_cast<void>(std::initializer_list<int>{
- (func(
- Get<Indices, Sequence>::impl(std::forward<Sequence>(seq)),
- std::integral_constant<std::size_t, Indices>{}),
- 0)...});
- }
-};
-template <typename Seq, typename F>
-struct ForEachTupleImpl<Seq, F, EnableIfBreaksTuple<Seq, F>> {
- template <typename Sequence, typename Func, std::size_t... Indices>
- static void
- impl(Sequence&& seq, Func& func, std::index_sequence<Indices...>) {
- // unroll the loop in an initializer list construction parameter expansion
- // pack
- LoopControl break_or_not = LoopControl::CONTINUE;
-
- // cast to void to ignore the result, use the initialzer list constructor
- // to do the loop execution, the ternary conditional will decide whether
- // or not to evaluate the result
- static_cast<void>(std::initializer_list<int>{
- (((break_or_not == loop_continue)
- ? (break_or_not = func(
- Get<Indices, Sequence>::impl(std::forward<Sequence>(seq)),
- std::integral_constant<std::size_t, Indices>{}))
- : (loop_continue)),
- 0)...});
- }
-};
-
-/**
- * The two top level compile time loop iteration functions handle the dispatch
- * based on the number of arguments the passed in function can be passed, if 2
- * arguments can be passed then the implementation dispatches work further to
- * the implementation classes above. If not then an adaptor is constructed
- * which is passed on to the 2 argument specialization, which then in turn
- * forwards implementation to the implementation classes above
- */
-template <
- typename Sequence,
- typename Func,
- EnableIfAcceptsTwoArguments<Sequence, Func>* = nullptr>
-void for_each_tuple_impl(Sequence&& seq, Func& func) {
- // pass the length as an index sequence to the implementation as an
- // optimization over manual template "tail recursion" unrolling
- constexpr auto length =
- std::tuple_size<typename std::decay<Sequence>::type>::value;
- ForEachTupleImpl<Sequence, Func>::impl(
- std::forward<Sequence>(seq), func, std::make_index_sequence<length>{});
-}
-template <
- typename Sequence,
- typename Func,
- EnableIfAcceptsOneArgument<Sequence, Func>* = nullptr>
-void for_each_tuple_impl(Sequence&& seq, Func& func) {
- // make an adaptor for the function passed in, in case it can only be passed
- // on argument
- auto two_arg_adaptor = [&func](auto&& ele, auto) -> decltype(auto) {
- return func(std::forward<decltype(ele)>(ele));
- };
- for_each_tuple_impl(std::forward<Sequence>(seq), two_arg_adaptor);
-}
-
-/**
- * Top level handlers for the for_each loop, the basic specialization handles
- * ranges and the specialized version handles compile time ranges (tuple like)
- *
- * This implies that if a range is a compile time range, its compile time
- * get<> API (whether through a member function or through a ADL looked up
- * method) will be used in preference over iterators
- */
-template <typename R, typename = void>
-struct ForEachImpl {
- template <typename Sequence, typename Func>
- static void impl(Sequence&& range, Func& func) {
- for_each_tuple_impl(std::forward<Sequence>(range), func);
- }
-};
-template <typename R>
-struct ForEachImpl<R, EnableIfRange<R>> {
- template <typename Sequence, typename Func>
- static void impl(Sequence&& range, Func& func) {
- for_each_range_impl(std::forward<Sequence>(range), func);
- }
-};
-
-template <typename S, typename I, typename = void>
-struct FetchIteratorIndexImpl {
- template <typename Sequence, typename Index>
- static decltype(auto) impl(Sequence&& sequence, Index&& index) {
- return std::forward<Sequence>(sequence)[std::forward<Index>(index)];
- }
-};
-template <typename S, typename I>
-struct FetchIteratorIndexImpl<S, I, EnableIfRandomAccessIterators<S>> {
- template <typename Sequence, typename Index>
- static decltype(auto) impl(Sequence&& sequence, Index index) {
- return *(adl::adl_begin(std::forward<Sequence>(sequence)) + index);
- }
-};
-template <typename S, typename = void>
-struct FetchImpl {
- template <typename Sequence, typename Index>
- static decltype(auto) impl(Sequence&& sequence, Index index) {
- return Get<static_cast<std::size_t>(index), Sequence>::impl(
- std::forward<Sequence>(sequence));
- }
-};
-template <typename S>
-struct FetchImpl<S, EnableIfRange<S>> {
- template <typename Sequence, typename Index>
- static decltype(auto) impl(Sequence&& sequence, Index&& index) {
- return FetchIteratorIndexImpl<Sequence, Index>::impl(
- std::forward<Sequence>(sequence), std::forward<Index>(index));
- }
-};
-
-} // namespace for_each_detail
-
-template <typename Sequence, typename Func>
-FOLLY_CPP14_CONSTEXPR Func for_each(Sequence&& range, Func func) {
- for_each_detail::ForEachImpl<typename std::decay<Sequence>::type>::impl(
- std::forward<Sequence>(range), func);
- return func;
-}
-
-template <typename Sequence, typename Index>
-FOLLY_CPP14_CONSTEXPR decltype(auto) fetch(Sequence&& sequence, Index&& index) {
- return for_each_detail::FetchImpl<Sequence>::impl(
- std::forward<Sequence>(sequence), std::forward<Index>(index));
-}
-
-} // namespace folly
+++ /dev/null
-/*
- * Copyright 2017 Facebook, Inc.
- *
- * 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
- *
- * http://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.
- */
-
-#pragma once
-
-#include <folly/Portability.h>
-#include <folly/Preprocessor.h>
-
-#include <type_traits>
-
-namespace folly {
-
-/**
- * @function for_each
- *
- * folly::for_each is a generalized iteration algorithm. Example:
- *
- * auto one = std::make_tuple(1, 2, 3);
- * auto two = std::vector<int>{1, 2, 3};
- * auto func = [](auto element, auto index) {
- * cout << index << " : " << element << endl;
- * };
- * folly::for_each(one, func);
- * folly::for_each(two, func);
- *
- * The for_each function allows iteration through sequences, these
- * can either be runtime sequences (i.e. entities for which std::begin and
- * std::end work) or compile time sequences (as deemed by the presence of
- * std::tuple_length<>, get<> (ADL resolved) functions)
- *
- * The function is made to provide a convenient library based alternative to
- * the proposal p0589r0, which aims to generalize the range based for loop
- * even further to work with compile time sequences.
- *
- * A drawback of using range based for loops is that sometimes you do not have
- * access to the index within the range. This provides easy access to that,
- * even with compile time sequences.
- *
- * And breaking out is easy
- *
- * auto range_one = std::vector<int>{1, 2, 3};
- * auto range_two = std::make_tuple(1, 2, 3);
- * auto func = [](auto ele, auto index) {
- * cout << "Element at index " << index << " : " << ele;
- * if (index == 1) {
- * return folly::loop_break;
- * }
- * return folly::loop_continue;
- * };
- * folly_for_each(range_one, func);
- * folly_for_each(range_two, func);
- *
- * A simple use case would be when using futures, if the user was doing calls
- * to n servers then they would accept the callback with the futures like this
- *
- * auto vec = std::vector<std::future<int>>{request_one(), ...};
- * when_all(vec.begin(), vec.end()).then([](auto futures) {
- * folly::for_each(futures, [](auto& fut) { ... });
- * });
- *
- * Now when this code switches to use tuples instead of the runtime
- * std::vector, then the loop does not need to change, the code will still
- * work just fine
- *
- * when_all(future_one, future_two, future_three).then([](auto futures) {
- * folly::for_each(futures, [](auto& fut) { ... });
- * });
- */
-template <typename Range, typename Func>
-FOLLY_CPP14_CONSTEXPR Func for_each(Range&& range, Func func);
-
-/**
- * The user should return loop_break and loop_continue if they want to iterate
- * in such a way that they can preemptively stop the loop and break out when
- * certain conditions are met
- */
-namespace for_each_detail {
-enum class LoopControl : bool { BREAK, CONTINUE };
-} // namespace for_each_detail
-
-constexpr auto loop_break = for_each_detail::LoopControl::BREAK;
-constexpr auto loop_continue = for_each_detail::LoopControl::CONTINUE;
-
-/**
- * Utility method to help access elements of a sequence with one uniform
- * interface
- *
- * This can be useful for example when you are looping through a sequence and
- * want to modify another sequence based on the information in the current
- * sequence
- *
- * auto range_one = std::make_tuple(1, 2, 3);
- * auto range_two = std::make_tuple(4, 5, 6);
- * folly::for_each(range_one, [&range_two](auto ele, auto index) {
- * folly::fetch(range_two, index) = ele;
- * });
- *
- * For non-tuple like ranges, this works by first trying to use the iterator
- * class if the iterator has been marked to be a random access iterator. This
- * should be inspectable via the std::iterator_traits traits class. If the
- * iterator class is not present or is not a random access iterator then the
- * implementation falls back to trying to use the indexing operator
- * (operator[]) to fetch the required element
- */
-template <typename Sequence, typename Index>
-FOLLY_CPP14_CONSTEXPR decltype(auto) fetch(Sequence&& sequence, Index&& index);
-
-} // namespace folly
-
-/**
- * Everything below this is deprecated. Use the folly::for_each algorithm above
- * instead
- */
-/*
- * Form a local variable name from "FOR_EACH_" x __LINE__, so that
- * FOR_EACH can be nested without creating shadowed declarations.
- */
-#define _FE_ANON(x) FB_CONCATENATE(FOR_EACH_, FB_CONCATENATE(x, __LINE__))
-
-/*
- * If you just want the element values, please use:
- *
- * for (auto&& element : collection)
- *
- * If you need access to the iterators please write an explicit iterator loop
- */
-#define FOR_EACH(i, c) \
- if (bool _FE_ANON(s1_) = false) {} else \
- for (auto && _FE_ANON(s2_) = (c); \
- !_FE_ANON(s1_); _FE_ANON(s1_) = true) \
- for (auto i = _FE_ANON(s2_).begin(); \
- i != _FE_ANON(s2_).end(); ++i)
-
-/*
- * If you just want the element values, please use this (ranges-v3) construct:
- *
- * for (auto&& element : collection | view::reverse)
- *
- * If you need access to the iterators please write an explicit iterator loop
- */
-#define FOR_EACH_R(i, c) \
- if (bool _FE_ANON(s1_) = false) {} else \
- for (auto && _FE_ANON(s2_) = (c); \
- !_FE_ANON(s1_); _FE_ANON(s1_) = true) \
- for (auto i = _FE_ANON(s2_).rbegin(); \
- i != _FE_ANON(s2_).rend(); ++i)
-
-/*
- * If you just want the element values, please use this (ranges-v3) construct:
- *
- * for (auto&& element : collection | view::zip(view::ints))
- *
- * If you need access to the iterators please write an explicit iterator loop
- * and use a counter variable
- */
-#define FOR_EACH_ENUMERATE(count, i, c) \
- if (bool _FE_ANON(s1_) = false) {} else \
- for (auto && FOR_EACH_state2 = (c); \
- !_FE_ANON(s1_); _FE_ANON(s1_) = true) \
- if (size_t _FE_ANON(n1_) = 0) {} else \
- if (const size_t& count = _FE_ANON(n1_)) {} else \
- for (auto i = FOR_EACH_state2.begin(); \
- i != FOR_EACH_state2.end(); ++_FE_ANON(n1_), ++i)
-/**
- * If you just want the keys, please use this (ranges-v3) construct:
- *
- * for (auto&& element : collection | view::keys)
- *
- * If you just want the values, please use this (ranges-v3) construct:
- *
- * for (auto&& element : collection | view::values)
- *
- * If you need to see both, use:
- *
- * for (auto&& element : collection) {
- * auto const& key = element.first;
- * auto& value = element.second;
- * ......
- * }
- *
- */
-#define FOR_EACH_KV(k, v, c) \
- if (unsigned int _FE_ANON(s1_) = 0) {} else \
- for (auto && _FE_ANON(s2_) = (c); \
- !_FE_ANON(s1_); _FE_ANON(s1_) = 1) \
- for (auto _FE_ANON(s3_) = _FE_ANON(s2_).begin(); \
- _FE_ANON(s3_) != _FE_ANON(s2_).end(); \
- _FE_ANON(s1_) == 2 \
- ? ((_FE_ANON(s1_) = 0), ++_FE_ANON(s3_)) \
- : (_FE_ANON(s3_) = _FE_ANON(s2_).end())) \
- for (auto &k = _FE_ANON(s3_)->first; \
- !_FE_ANON(s1_); ++_FE_ANON(s1_)) \
- for (auto &v = _FE_ANON(s3_)->second; \
- !_FE_ANON(s1_); ++_FE_ANON(s1_))
-
-namespace folly { namespace detail {
-
-// Boost 1.48 lacks has_less, we emulate a subset of it here.
-template <typename T, typename U>
-class HasLess {
- struct BiggerThanChar { char unused[2]; };
- template <typename C, typename D> static char test(decltype(C() < D())*);
- template <typename, typename> static BiggerThanChar test(...);
-
- public:
- enum { value = sizeof(test<T, U>(nullptr)) == 1 };
-};
-
-/**
- * notThereYet helps the FOR_EACH_RANGE macro by opportunistically
- * using "<" instead of "!=" whenever available when checking for loop
- * termination. This makes e.g. examples such as FOR_EACH_RANGE (i,
- * 10, 5) execute zero iterations instead of looping virtually
- * forever. At the same time, some iterator types define "!=" but not
- * "<". The notThereYet function will dispatch differently for those.
- *
- * Below is the correct implementation of notThereYet. It is disabled
- * because of a bug in Boost 1.46: The filesystem::path::iterator
- * defines operator< (via boost::iterator_facade), but that in turn
- * uses distance_to which is undefined for that particular
- * iterator. So HasLess (defined above) identifies
- * boost::filesystem::path as properly comparable with <, but in fact
- * attempting to do so will yield a compile-time error.
- *
- * The else branch (active) contains a conservative
- * implementation.
- */
-
-#if 0
-
-template <class T, class U>
-typename std::enable_if<HasLess<T, U>::value, bool>::type
-notThereYet(T& iter, const U& end) {
- return iter < end;
-}
-
-template <class T, class U>
-typename std::enable_if<!HasLess<T, U>::value, bool>::type
-notThereYet(T& iter, const U& end) {
- return iter != end;
-}
-
-#else
-
-template <class T, class U>
-typename std::enable_if<
- (std::is_arithmetic<T>::value && std::is_arithmetic<U>::value) ||
- (std::is_pointer<T>::value && std::is_pointer<U>::value),
- bool>::type
-notThereYet(T& iter, const U& end) {
- return iter < end;
-}
-
-template <class T, class U>
-typename std::enable_if<
- !(
- (std::is_arithmetic<T>::value && std::is_arithmetic<U>::value) ||
- (std::is_pointer<T>::value && std::is_pointer<U>::value)
- ),
- bool>::type
-notThereYet(T& iter, const U& end) {
- return iter != end;
-}
-
-#endif
-
-
-/**
- * downTo is similar to notThereYet, but in reverse - it helps the
- * FOR_EACH_RANGE_R macro.
- */
-template <class T, class U>
-typename std::enable_if<HasLess<U, T>::value, bool>::type
-downTo(T& iter, const U& begin) {
- return begin < iter--;
-}
-
-template <class T, class U>
-typename std::enable_if<!HasLess<U, T>::value, bool>::type
-downTo(T& iter, const U& begin) {
- if (iter == begin) {
- return false;
- }
- --iter;
- return true;
-}
-
-} }
-
-/*
- * Look at the Ranges-v3 views and you'll probably find an easier way to build
- * the view you want but the equivalent is roughly:
- *
- * for (auto& element : make_iterator_range(begin, end))
- */
-#define FOR_EACH_RANGE(i, begin, end) \
- for (auto i = (true ? (begin) : (end)); \
- ::folly::detail::notThereYet(i, (end)); \
- ++i)
-
-/*
- * Look at the Ranges-v3 views and you'll probably find an easier way to build
- * the view you want but the equivalent is roughly:
- *
- * for (auto& element : make_iterator_range(begin, end) | view::reverse)
- */
-#define FOR_EACH_RANGE_R(i, begin, end) \
- for (auto i = (false ? (begin) : (end)); ::folly::detail::downTo(i, (begin));)
-
-#include <folly/Foreach-inl.h>
+++ /dev/null
-/*
- * Copyright 2017 Facebook, Inc.
- *
- * 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
- *
- * http://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.
- */
-
-#pragma once
-
-#include <functional>
-#include <iterator>
-#include <memory>
-#include <tuple>
-#include <type_traits>
-#include <utility>
-
-#include <folly/Functional.h>
-
-namespace folly {
-
-/**
- * Argument tuple for variadic emplace/constructor calls. Stores arguments by
- * (decayed) value. Restores original argument types with reference qualifiers
- * and adornments at unpack time to emulate perfect forwarding.
- *
- * Uses inheritance instead of a type alias to std::tuple so that emplace
- * iterators with implicit unpacking disabled can distinguish between
- * emplace_args and std::tuple parameters.
- *
- * @seealso folly::make_emplace_args
- * @seealso folly::get_emplace_arg
- */
-template <typename... Args>
-struct emplace_args : public std::tuple<std::decay_t<Args>...> {
- using storage_type = std::tuple<std::decay_t<Args>...>;
- using storage_type::storage_type;
-};
-
-/**
- * Pack arguments in a tuple for assignment to a folly::emplace_iterator,
- * folly::front_emplace_iterator, or folly::back_emplace_iterator. The
- * iterator's operator= will unpack the tuple and pass the unpacked arguments
- * to the container's emplace function, which in turn forwards the arguments to
- * the (multi-argument) constructor of the target class.
- *
- * Argument tuples generated with folly::make_emplace_args will be unpacked
- * before being passed to the container's emplace function, even for iterators
- * where implicit_unpack is set to false (so they will not implicitly unpack
- * std::pair or std::tuple arguments to operator=).
- *
- * Arguments are copied (lvalues) or moved (rvalues). To avoid copies and moves,
- * wrap references using std::ref(), std::cref(), and folly::rref(). Beware of
- * dangling references, especially references to temporary objects created with
- * folly::rref().
- *
- * Note that an argument pack created with folly::make_emplace_args is different
- * from an argument pack created with std::make_pair or std::make_tuple.
- * Specifically, passing a std::pair&& or std::tuple&& to an emplace iterator's
- * operator= will pass rvalue references to all fields of that tuple to the
- * container's emplace function, while passing an emplace_args&& to operator=
- * will cast those field references to the exact argument types as passed to
- * folly::make_emplace_args previously. If all arguments have been wrapped by
- * std::reference_wrappers or folly::rvalue_reference_wrappers, the result will
- * be the same as if the container's emplace function had been called directly
- * (perfect forwarding), with no temporary copies of the arguments.
- *
- * @seealso folly::rref
- *
- * @example
- * class Widget { Widget(int, int); };
- * std::vector<Widget> makeWidgets(const std::vector<int>& in) {
- * std::vector<Widget> out;
- * std::transform(
- * in.begin(),
- * in.end(),
- * folly::back_emplacer(out),
- * [](int i) { return folly::make_emplace_args(i, i); });
- * return out;
- * }
- */
-template <typename... Args>
-emplace_args<Args...> make_emplace_args(Args&&... args) noexcept(
- noexcept(emplace_args<Args...>(std::forward<Args>(args)...))) {
- return emplace_args<Args...>(std::forward<Args>(args)...);
-}
-
-namespace detail {
-template <typename Arg>
-decltype(auto) unwrap_emplace_arg(Arg&& arg) noexcept {
- return std::forward<Arg>(arg);
-}
-template <typename Arg>
-decltype(auto) unwrap_emplace_arg(std::reference_wrapper<Arg> arg) noexcept {
- return arg.get();
-}
-template <typename Arg>
-decltype(auto) unwrap_emplace_arg(
- folly::rvalue_reference_wrapper<Arg> arg) noexcept {
- return std::move(arg).get();
-}
-}
-
-/**
- * Getter function for unpacking a single emplace argument.
- *
- * Calling get_emplace_arg on an emplace_args rvalue reference results in
- * perfect forwarding of the original input types. A special case are
- * std::reference_wrapper and folly::rvalue_reference_wrapper objects within
- * folly::emplace_args. These are also unwrapped so that the bare reference is
- * returned.
- *
- * std::get is not a customization point in the standard library, so the
- * cleanest solution was to define our own getter function.
- */
-template <size_t I, typename... Args>
-decltype(auto) get_emplace_arg(emplace_args<Args...>&& args) noexcept {
- using Out = std::tuple<Args...>;
- return detail::unwrap_emplace_arg(
- std::forward<std::tuple_element_t<I, Out>>(std::get<I>(args)));
-}
-template <size_t I, typename... Args>
-decltype(auto) get_emplace_arg(emplace_args<Args...>& args) noexcept {
- return detail::unwrap_emplace_arg(std::get<I>(args));
-}
-template <size_t I, typename... Args>
-decltype(auto) get_emplace_arg(const emplace_args<Args...>& args) noexcept {
- return detail::unwrap_emplace_arg(std::get<I>(args));
-}
-template <size_t I, typename Args>
-decltype(auto) get_emplace_arg(Args&& args) noexcept {
- return std::get<I>(std::move(args));
-}
-template <size_t I, typename Args>
-decltype(auto) get_emplace_arg(Args& args) noexcept {
- return std::get<I>(args);
-}
-template <size_t I, typename Args>
-decltype(auto) get_emplace_arg(const Args& args) noexcept {
- return std::get<I>(args);
-}
-
-namespace detail {
-/**
- * Emplace implementation class for folly::emplace_iterator.
- */
-template <typename Container>
-struct Emplace {
- Emplace(Container& c, typename Container::iterator i)
- : container(std::addressof(c)), iter(std::move(i)) {}
- template <typename... Args>
- void emplace(Args&&... args) {
- iter = container->emplace(iter, std::forward<Args>(args)...);
- ++iter;
- }
- Container* container;
- typename Container::iterator iter;
-};
-
-/**
- * Emplace implementation class for folly::hint_emplace_iterator.
- */
-template <typename Container>
-struct EmplaceHint {
- EmplaceHint(Container& c, typename Container::iterator i)
- : container(std::addressof(c)), iter(std::move(i)) {}
- template <typename... Args>
- void emplace(Args&&... args) {
- iter = container->emplace_hint(iter, std::forward<Args>(args)...);
- ++iter;
- }
- Container* container;
- typename Container::iterator iter;
-};
-
-/**
- * Emplace implementation class for folly::front_emplace_iterator.
- */
-template <typename Container>
-struct EmplaceFront {
- explicit EmplaceFront(Container& c) : container(std::addressof(c)) {}
- template <typename... Args>
- void emplace(Args&&... args) {
- container->emplace_front(std::forward<Args>(args)...);
- }
- Container* container;
-};
-
-/**
- * Emplace implementation class for folly::back_emplace_iterator.
- */
-template <typename Container>
-struct EmplaceBack {
- explicit EmplaceBack(Container& c) : container(std::addressof(c)) {}
- template <typename... Args>
- void emplace(Args&&... args) {
- container->emplace_back(std::forward<Args>(args)...);
- }
- Container* container;
-};
-
-/**
- * Generic base class and implementation of all emplace iterator classes.
- *
- * Uses the curiously recurring template pattern (CRTP) to cast `this*` to
- * `Derived*`; i.e., to implement covariant return types in a generic manner.
- */
-template <typename Derived, typename EmplaceImpl, bool implicit_unpack>
-class emplace_iterator_base;
-
-/**
- * Partial specialization of emplace_iterator_base with implicit unpacking
- * disabled.
- */
-template <typename Derived, typename EmplaceImpl>
-class emplace_iterator_base<Derived, EmplaceImpl, false>
- : protected EmplaceImpl /* protected implementation inheritance */ {
- public:
- // Iterator traits.
- using iterator_category = std::output_iterator_tag;
- using value_type = void;
- using difference_type = void;
- using pointer = void;
- using reference = void;
- using container_type =
- std::remove_reference_t<decltype(*EmplaceImpl::container)>;
-
- using EmplaceImpl::EmplaceImpl;
-
- /**
- * Canonical output operator. Forwards single argument straight to container's
- * emplace function.
- */
- template <typename T>
- Derived& operator=(T&& arg) {
- this->emplace(std::forward<T>(arg));
- return static_cast<Derived&>(*this);
- }
-
- /**
- * Special output operator for packed arguments. Unpacks args and performs
- * variadic call to container's emplace function.
- */
- template <typename... Args>
- Derived& operator=(emplace_args<Args...>& args) {
- return unpackAndEmplace(args, std::index_sequence_for<Args...>{});
- }
- template <typename... Args>
- Derived& operator=(const emplace_args<Args...>& args) {
- return unpackAndEmplace(args, std::index_sequence_for<Args...>{});
- }
- template <typename... Args>
- Derived& operator=(emplace_args<Args...>&& args) {
- return unpackAndEmplace(
- std::move(args), std::index_sequence_for<Args...>{});
- }
-
- // No-ops.
- Derived& operator*() {
- return static_cast<Derived&>(*this);
- }
- Derived& operator++() {
- return static_cast<Derived&>(*this);
- }
- Derived& operator++(int) {
- return static_cast<Derived&>(*this);
- }
-
- // We need all of these explicit defaults because the custom operator=
- // overloads disable implicit generation of these functions.
- emplace_iterator_base(const emplace_iterator_base&) = default;
- emplace_iterator_base(emplace_iterator_base&&) noexcept = default;
- emplace_iterator_base& operator=(emplace_iterator_base&) = default;
- emplace_iterator_base& operator=(const emplace_iterator_base&) = default;
- emplace_iterator_base& operator=(emplace_iterator_base&&) noexcept = default;
-
- protected:
- template <typename Args, std::size_t... I>
- Derived& unpackAndEmplace(Args& args, std::index_sequence<I...>) {
- this->emplace(get_emplace_arg<I>(args)...);
- return static_cast<Derived&>(*this);
- }
- template <typename Args, std::size_t... I>
- Derived& unpackAndEmplace(const Args& args, std::index_sequence<I...>) {
- this->emplace(get_emplace_arg<I>(args)...);
- return static_cast<Derived&>(*this);
- }
- template <typename Args, std::size_t... I>
- Derived& unpackAndEmplace(Args&& args, std::index_sequence<I...>) {
- this->emplace(get_emplace_arg<I>(std::move(args))...);
- return static_cast<Derived&>(*this);
- }
-};
-
-/**
- * Partial specialization of emplace_iterator_base with implicit unpacking
- * enabled.
- *
- * Uses inheritance rather than SFINAE. operator= requires a single argument,
- * which makes it very tricky to use std::enable_if or similar.
- */
-template <typename Derived, typename EmplaceImpl>
-class emplace_iterator_base<Derived, EmplaceImpl, true>
- : public emplace_iterator_base<Derived, EmplaceImpl, false> {
- private:
- using Base = emplace_iterator_base<Derived, EmplaceImpl, false>;
-
- public:
- using Base::Base;
- using Base::operator=;
-
- /**
- * Special output operator for arguments packed into a std::pair. Unpacks
- * the pair and performs variadic call to container's emplace function.
- */
- template <typename... Args>
- Derived& operator=(std::pair<Args...>& args) {
- return this->unpackAndEmplace(args, std::index_sequence_for<Args...>{});
- }
- template <typename... Args>
- Derived& operator=(const std::pair<Args...>& args) {
- return this->unpackAndEmplace(args, std::index_sequence_for<Args...>{});
- }
- template <typename... Args>
- Derived& operator=(std::pair<Args...>&& args) {
- return this->unpackAndEmplace(
- std::move(args), std::index_sequence_for<Args...>{});
- }
-
- /**
- * Special output operator for arguments packed into a std::tuple. Unpacks
- * the tuple and performs variadic call to container's emplace function.
- */
- template <typename... Args>
- Derived& operator=(std::tuple<Args...>& args) {
- return this->unpackAndEmplace(args, std::index_sequence_for<Args...>{});
- }
- template <typename... Args>
- Derived& operator=(const std::tuple<Args...>& args) {
- return this->unpackAndEmplace(args, std::index_sequence_for<Args...>{});
- }
- template <typename... Args>
- Derived& operator=(std::tuple<Args...>&& args) {
- return this->unpackAndEmplace(
- std::move(args), std::index_sequence_for<Args...>{});
- }
-
- // We need all of these explicit defaults because the custom operator=
- // overloads disable implicit generation of these functions.
- emplace_iterator_base(const emplace_iterator_base&) = default;
- emplace_iterator_base(emplace_iterator_base&&) noexcept = default;
- emplace_iterator_base& operator=(emplace_iterator_base&) = default;
- emplace_iterator_base& operator=(const emplace_iterator_base&) = default;
- emplace_iterator_base& operator=(emplace_iterator_base&&) noexcept = default;
-};
-
-/**
- * Concrete instantiation of emplace_iterator_base. All emplace iterator
- * classes; folly::emplace_iterator, folly::hint_emplace_iterator,
- * folly::front_emplace_iterator, and folly::back_emplace_iterator; are just
- * type aliases of this class.
- *
- * It is not possible to alias emplace_iterator_base directly, because type
- * aliases cannot be used for CRTP.
- */
-template <
- template <typename> class EmplaceImplT,
- typename Container,
- bool implicit_unpack>
-class emplace_iterator_impl
- : public emplace_iterator_base<
- emplace_iterator_impl<EmplaceImplT, Container, implicit_unpack>,
- EmplaceImplT<Container>,
- implicit_unpack> {
- private:
- using Base = emplace_iterator_base<
- emplace_iterator_impl,
- EmplaceImplT<Container>,
- implicit_unpack>;
-
- public:
- using Base::Base;
- using Base::operator=;
-
- // We need all of these explicit defaults because the custom operator=
- // overloads disable implicit generation of these functions.
- emplace_iterator_impl(const emplace_iterator_impl&) = default;
- emplace_iterator_impl(emplace_iterator_impl&&) noexcept = default;
- emplace_iterator_impl& operator=(emplace_iterator_impl&) = default;
- emplace_iterator_impl& operator=(const emplace_iterator_impl&) = default;
- emplace_iterator_impl& operator=(emplace_iterator_impl&&) noexcept = default;
-};
-} // namespace detail
-
-/**
- * Behaves just like std::insert_iterator except that it calls emplace()
- * instead of insert(). Uses perfect forwarding.
- */
-template <typename Container, bool implicit_unpack = true>
-using emplace_iterator =
- detail::emplace_iterator_impl<detail::Emplace, Container, implicit_unpack>;
-
-/**
- * Behaves just like std::insert_iterator except that it calls emplace_hint()
- * instead of insert(). Uses perfect forwarding.
- */
-template <typename Container, bool implicit_unpack = true>
-using hint_emplace_iterator = detail::
- emplace_iterator_impl<detail::EmplaceHint, Container, implicit_unpack>;
-
-/**
- * Behaves just like std::front_insert_iterator except that it calls
- * emplace_front() instead of insert(). Uses perfect forwarding.
- */
-template <typename Container, bool implicit_unpack = true>
-using front_emplace_iterator = detail::
- emplace_iterator_impl<detail::EmplaceFront, Container, implicit_unpack>;
-
-/**
- * Behaves just like std::back_insert_iterator except that it calls
- * emplace_back() instead of insert(). Uses perfect forwarding.
- */
-template <typename Container, bool implicit_unpack = true>
-using back_emplace_iterator = detail::
- emplace_iterator_impl<detail::EmplaceBack, Container, implicit_unpack>;
-
-/**
- * Convenience function to construct a folly::emplace_iterator, analogous to
- * std::inserter().
- *
- * Setting implicit_unpack to false will disable implicit unpacking of
- * single std::pair and std::tuple arguments to the iterator's operator=. That
- * may be desirable in case of constructors that expect a std::pair or
- * std::tuple argument.
- */
-template <bool implicit_unpack = true, typename Container>
-emplace_iterator<Container, implicit_unpack> emplacer(
- Container& c,
- typename Container::iterator i) {
- return emplace_iterator<Container, implicit_unpack>(c, std::move(i));
-}
-
-/**
- * Convenience function to construct a folly::hint_emplace_iterator, analogous
- * to std::inserter().
- *
- * Setting implicit_unpack to false will disable implicit unpacking of
- * single std::pair and std::tuple arguments to the iterator's operator=. That
- * may be desirable in case of constructors that expect a std::pair or
- * std::tuple argument.
- */
-template <bool implicit_unpack = true, typename Container>
-hint_emplace_iterator<Container, implicit_unpack> hint_emplacer(
- Container& c,
- typename Container::iterator i) {
- return hint_emplace_iterator<Container, implicit_unpack>(c, std::move(i));
-}
-
-/**
- * Convenience function to construct a folly::front_emplace_iterator, analogous
- * to std::front_inserter().
- *
- * Setting implicit_unpack to false will disable implicit unpacking of
- * single std::pair and std::tuple arguments to the iterator's operator=. That
- * may be desirable in case of constructors that expect a std::pair or
- * std::tuple argument.
- */
-template <bool implicit_unpack = true, typename Container>
-front_emplace_iterator<Container, implicit_unpack> front_emplacer(
- Container& c) {
- return front_emplace_iterator<Container, implicit_unpack>(c);
-}
-
-/**
- * Convenience function to construct a folly::back_emplace_iterator, analogous
- * to std::back_inserter().
- *
- * Setting implicit_unpack to false will disable implicit unpacking of
- * single std::pair and std::tuple arguments to the iterator's operator=. That
- * may be desirable in case of constructors that expect a std::pair or
- * std::tuple argument.
- */
-template <bool implicit_unpack = true, typename Container>
-back_emplace_iterator<Container, implicit_unpack> back_emplacer(Container& c) {
- return back_emplace_iterator<Container, implicit_unpack>(c);
-}
-}
concurrency/ConcurrentHashMap.h \
concurrency/CoreCachedSharedPtr.h \
concurrency/detail/ConcurrentHashMap-detail.h \
+ container/Iterator.h \
+ container/Enumerate.h \
+ container/EvictingCacheMap.h \
+ container/Foreach.h \
+ container/Foreach-inl.h \
+ container/SparseByteSet.h \
ConstexprMath.h \
detail/AtomicHashUtils.h \
detail/AtomicUnorderedMapUtils.h \
DynamicConverter.h \
dynamic.h \
dynamic-inl.h \
- Enumerate.h \
- EvictingCacheMap.h \
Exception.h \
ExceptionString.h \
ExceptionWrapper.h \
Fingerprint.h \
FixedString.h \
folly-config.h \
- Foreach.h \
- Foreach-inl.h \
FormatArg.h \
FormatTraits.h \
Format.h \
io/async/test/TimeUtil.h \
io/async/test/UndelayedDestruction.h \
io/async/test/Util.h \
- Iterator.h \
json.h \
Launder.h \
Lazy.h \
small_vector.h \
SocketAddress.h \
sorted_vector_types.h \
- SparseByteSet.h \
SpinLock.h \
ssl/Init.h \
ssl/OpenSSLCertUtils.h \
+++ /dev/null
-/*
- * Copyright 2017 Facebook, Inc.
- *
- * 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
- *
- * http://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.
- */
-
-#pragma once
-
-#include <cstdint>
-
-#include <glog/logging.h>
-
-namespace folly {
-
-/***
- * SparseByteSet
- *
- * A special-purpose data structure representing an insert-only set of bytes.
- * May have better performance than std::bitset<256>, depending on workload.
- *
- * Operations:
- * - add(byte)
- * - contains(byte)
- *
- * Performance:
- * - The entire capacity of the set is inline; the set never allocates.
- * - The constructor zeros only the first two bytes of the object.
- * - add and contains both run in constant time w.r.t. the size of the set.
- * Constant time - not amortized constant - and with small constant factor.
- *
- * This data structure is ideal for on-stack use.
- *
- * Aho, Hopcroft, and Ullman refer to this trick in "The Design and Analysis
- * of Computer Algorithms" (1974), but the best description is here:
- * http://research.swtch.com/sparse
- * http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.7319
- */
-class SparseByteSet {
- public:
- // There are this many possible values:
- static constexpr uint16_t kCapacity = 256;
-
- // No init of byte-arrays required!
- SparseByteSet() : size_(0) { }
-
- /***
- * add(byte)
- *
- * O(1), non-amortized.
- */
- inline bool add(uint8_t i) {
- bool r = !contains(i);
- if (r) {
- DCHECK_LT(size_, kCapacity);
- dense_[size_] = i;
- sparse_[i] = uint8_t(size_);
- size_++;
- }
- return r;
- }
-
- /***
- * contains(byte)
- *
- * O(1), non-amortized.
- */
- inline bool contains(uint8_t i) const {
- return sparse_[i] < size_ && dense_[sparse_[i]] == i;
- }
-
- private:
- uint16_t size_; // can't use uint8_t because it would overflow if all
- // possible values were inserted.
- uint8_t sparse_[kCapacity];
- uint8_t dense_[kCapacity];
-};
-
-}
+++ /dev/null
-/*
- * Copyright 2017 Facebook, Inc.
- *
- * 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
- *
- * http://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.
- */
-
-/*
- * folly::merge() is an implementation of std::merge with one additonal
- * guarantee: if the input ranges overlap, the order that values *from the two
- * different ranges* appear in the output is well defined (std::merge only
- * guarantees relative ordering is maintained within a single input range).
- * This semantic is very useful when the output container removes duplicates
- * (such as std::map) to guarantee that elements from b override elements from
- * a.
- *
- * ex. Let's say we have two vector<pair<int, int>> as input, and we are
- * merging into a vector<pair<int, int>>. The comparator is returns true if the
- * first argument has a lesser 'first' value in the pair.
- *
- * a = {{1, 1}, {2, 2}, {3, 3}};
- * b = {{1, 2}, {2, 3}};
- *
- * folly::merge<...>(a.begin(), a.end(), b.begin(), b.end(), outputIter) is
- * guaranteed to produce {{1, 1}, {1, 2}, {2, 2}, {2, 3}, {3, 3}}. That is,
- * if comp(it_a, it_b) == comp(it_b, it_a) == false, we first insert the element
- * from a.
- */
-
-#pragma once
-
-#include <algorithm>
-
-namespace folly {
-
-template <class InputIt1, class InputIt2, class OutputIt, class Compare>
-OutputIt merge(InputIt1 first1, InputIt1 last1,
- InputIt2 first2, InputIt2 last2,
- OutputIt d_first, Compare comp) {
- for (; first1 != last1; ++d_first) {
- if (first2 == last2) {
- return std::copy(first1, last1, d_first);
- }
- if (comp(*first2, *first1)) {
- *d_first = *first2;
- ++first2;
- } else {
- *d_first = *first1;
- ++first1;
- }
- }
- return std::copy(first2, last2, d_first);
-}
-
-template <class InputIt1, class InputIt2, class OutputIt>
-OutputIt merge(InputIt1 first1, InputIt1 last1,
- InputIt2 first2, InputIt2 last2,
- OutputIt d_first) {
- for (; first1 != last1; ++d_first) {
- if (first2 == last2) {
- return std::copy(first1, last1, d_first);
- }
- if (*first2 < *first1) {
- *d_first = *first2;
- ++first2;
- } else {
- *d_first = *first1;
- ++first1;
- }
- }
- return std::copy(first2, last2, d_first);
-}
-
-}
+++ /dev/null
-/*
- * Copyright 2017 Facebook, Inc.
- *
- * 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
- *
- * http://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 <folly/algorithm/Merge.h>
-
-#include <map>
-#include <vector>
-
-#include <folly/portability/GTest.h>
-
-TEST(MergeTest, NonOverlapping) {
- std::vector<int> a = {0, 2, 4, 6};
- std::vector<int> b = {1, 3, 5, 7};
- std::vector<int> c;
-
- folly::merge(a.begin(), a.end(),
- b.begin(), b.end(),
- std::back_inserter(c));
- EXPECT_EQ(8, c.size());
- for (size_t i = 0; i < 8; ++i) {
- EXPECT_EQ(i, c[i]);
- }
-}
-
-TEST(MergeTest, OverlappingInSingleInputRange) {
- std::vector<std::pair<int, int>> a = {{0, 0}, {0, 1}};
- std::vector<std::pair<int, int>> b = {{2, 2}, {3, 3}};
- std::map<int, int> c;
-
- folly::merge(a.begin(), a.end(),
- b.begin(), b.end(),
- std::inserter(c, c.begin()));
- EXPECT_EQ(3, c.size());
-
- // First value is inserted, second is not
- EXPECT_EQ(c[0], 0);
-
- EXPECT_EQ(c[2], 2);
- EXPECT_EQ(c[3], 3);
-}
-
-TEST(MergeTest, OverlappingInDifferentInputRange) {
- std::vector<std::pair<int, int>> a = {{0, 0}, {1, 1}};
- std::vector<std::pair<int, int>> b = {{0, 2}, {3, 3}};
- std::map<int, int> c;
-
- folly::merge(a.begin(), a.end(),
- b.begin(), b.end(),
- std::inserter(c, c.begin()));
- EXPECT_EQ(3, c.size());
-
- // Value from a is inserted, value from b is not.
- EXPECT_EQ(c[0], 0);
-
- EXPECT_EQ(c[1], 1);
- EXPECT_EQ(c[3], 3);
-}
#include <array>
#include <memory>
-#include <folly/Enumerate.h>
#include <folly/concurrency/AtomicSharedPtr.h>
#include <folly/concurrency/CacheLocality.h>
+#include <folly/container/Enumerate.h>
#include <folly/experimental/hazptr/hazptr.h>
namespace folly {
--- /dev/null
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * 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
+ *
+ * http://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.
+ */
+
+#pragma once
+
+#include <iterator>
+#include <memory>
+
+#include <folly/portability/SysTypes.h>
+
+/**
+ * Similar to Python's enumerate(), folly::enumerate() can be used to
+ * iterate a range with a for-range loop, and it also allows to
+ * retrieve the count of iterations so far.
+ *
+ * For example:
+ *
+ * for (auto it : folly::enumerate(vec)) {
+ * // *it is a reference to the current element. Const if vec is const.
+ * // it->member can be used as well.
+ * // it.index contains the iteration count.
+ * }
+ *
+ * If the iteration variable is const, the reference is too.
+ *
+ * for (const auto it : folly::enumerate(vec)) {
+ * // *it is always a const reference.
+ * }
+ *
+ * @author Giuseppe Ottaviano <ott@fb.com>
+ */
+
+namespace folly {
+
+namespace detail {
+
+template <class T>
+struct MakeConst {
+ using type = const T;
+};
+template <class T>
+struct MakeConst<T&> {
+ using type = const T&;
+};
+template <class T>
+struct MakeConst<T*> {
+ using type = const T*;
+};
+
+// Raw pointers don't have an operator->() member function, so the
+// second overload will be SFINAEd out in that case. Otherwise, the
+// second is preferred in the partial order for getPointer(_, 0).
+template <class Iterator>
+auto getPointer(const Iterator& it, long) -> decltype(std::addressof(*it)) {
+ return std::addressof(*it);
+}
+template <class Iterator>
+auto getPointer(const Iterator& it, int) -> decltype(it.operator->()) {
+ return it.operator->();
+}
+
+template <class Iterator>
+class Enumerator {
+ public:
+ explicit Enumerator(Iterator it) : it_(std::move(it)) {}
+
+ class Proxy {
+ public:
+ using difference_type = ssize_t;
+ using value_type = typename std::iterator_traits<Iterator>::value_type;
+ using reference = typename std::iterator_traits<Iterator>::reference;
+ using pointer = typename std::iterator_traits<Iterator>::pointer;
+ using iterator_category = std::input_iterator_tag;
+
+ explicit Proxy(const Enumerator* e) : it_(e->it_), index(e->idx_) {}
+
+ // Non-const Proxy: Forward constness from Iterator.
+ reference operator*() {
+ return *it_;
+ }
+ pointer operator->() {
+ return getPointer(it_, 0);
+ }
+
+ // Const Proxy: Force const references.
+ typename MakeConst<reference>::type operator*() const {
+ return *it_;
+ }
+ typename MakeConst<pointer>::type operator->() const {
+ return getPointer(it_, 0);
+ }
+
+ private:
+ const Iterator& it_;
+
+ public:
+ const size_t index;
+ };
+
+ Proxy operator*() const {
+ return Proxy(this);
+ }
+
+ Enumerator& operator++() {
+ ++it_;
+ ++idx_;
+ return *this;
+ }
+
+ template <typename OtherIterator>
+ bool operator==(const Enumerator<OtherIterator>& rhs) {
+ return it_ == rhs.it_;
+ }
+
+ template <typename OtherIterator>
+ bool operator!=(const Enumerator<OtherIterator>& rhs) {
+ return !(*this == rhs);
+ }
+
+ private:
+ template <typename OtherIterator>
+ friend class Enumerator;
+
+ Iterator it_;
+ size_t idx_ = 0;
+};
+
+template <class Range>
+class RangeEnumerator {
+ Range r_;
+ using BeginIteratorType = decltype(std::declval<Range>().begin());
+ using EndIteratorType = decltype(std::declval<Range>().end());
+
+ public:
+ explicit RangeEnumerator(Range&& r) : r_(std::forward<Range>(r)) {}
+
+ Enumerator<BeginIteratorType> begin() {
+ return Enumerator<BeginIteratorType>(r_.begin());
+ }
+ Enumerator<EndIteratorType> end() {
+ return Enumerator<EndIteratorType>(r_.end());
+ }
+};
+
+} // namespace detail
+
+template <class Range>
+detail::RangeEnumerator<Range> enumerate(Range&& r) {
+ return detail::RangeEnumerator<Range>(std::forward<Range>(r));
+}
+
+} // namespace folly
--- /dev/null
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * 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
+ *
+ * http://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.
+ */
+
+#pragma once
+
+#include <algorithm>
+#include <exception>
+#include <functional>
+
+#include <boost/intrusive/list.hpp>
+#include <boost/intrusive/unordered_set.hpp>
+#include <boost/iterator/iterator_adaptor.hpp>
+#include <boost/utility.hpp>
+
+#include <folly/portability/BitsFunctexcept.h>
+
+namespace folly {
+
+/**
+ * A general purpose LRU evicting cache. Designed to support constant time
+ * set/get operations. It maintains a doubly linked list of items that are
+ * threaded through an index (a hash map). The access ordered is maintained
+ * on the list by moving an element to the front of list on a get. New elements
+ * are added to the front of the list. The index size is set to half the
+ * capacity (setting capacity to 0 is a special case. see notes at the end of
+ * this section). So assuming uniform distribution of keys, set/get are both
+ * constant time operations.
+ *
+ * On reaching capacity limit, clearSize_ LRU items are evicted at a time. If
+ * a callback is specified with setPruneHook, it is invoked for each eviction.
+ *
+ * This is NOT a thread-safe implementation.
+ *
+ * Configurability: capacity of the cache, number of items to evict, eviction
+ * callback and the hasher to hash the keys can all be supplied by the caller.
+ *
+ * If at a given state, N1 - N6 are the nodes in MRU to LRU order and hashing
+ * to index keys as {(N1,N5)->H1, (N4,N5,N5)->H2, N3->Hi}, the datastructure
+ * layout is as below. N1 .. N6 is a list threaded through the hash.
+ * Assuming, each the number of nodes hashed to each index key is bounded, the
+ * following operations run in constant time.
+ * i) get computes the index key, walks the list of elements hashed to
+ * the key and moves it to the front of the list, if found.
+ * ii) set inserts a new node into the list and places the same node on to the
+ * list of elements hashing to the corresponding index key.
+ * ii) prune deletes nodes from the end of the list as well from the index.
+ *
+ * +----+ +----+ +----+
+ * | H1 | <-> | N1 | <-> | N5 |
+ * +----+ +----+ +----+
+ * ^ ^ ^
+ * | ___/ \
+ * | / \
+ * |_ /________ \___
+ * / | \
+ * / | \
+ * v v v
+ * +----+ +----+ +----+ +----+
+ * | H2 | <-> | N4 | <-> | N2 | <-> | N6 |
+ * +----+ +----+ +----+ +----+
+ * . ^ ^
+ * . | |
+ * . | |
+ * . | _____|
+ * . | /
+ * v v
+ * +----+ +----+
+ * | Hi | <-> | N3 |
+ * +----+ +----+
+ *
+ * N.B 1 : Changing the capacity with setMaxSize does not change the index size
+ * and it could end up in too many elements indexed to the same slot in index.
+ * The set/get performance will get worse in this case. So it is best to avoid
+ * resizing.
+ *
+ * N.B 2 : Setting capacity to 0, using setMaxSize or initialization, turns off
+ * evictions based on sizeof the cache making it an INFINITE size cache
+ * unless evictions of LRU items are triggered by calling prune() by clients
+ * (using their own eviction criteria).
+ */
+template <class TKey, class TValue, class THash = std::hash<TKey>>
+class EvictingCacheMap {
+ private:
+ // typedefs for brevity
+ struct Node;
+ typedef boost::intrusive::link_mode<boost::intrusive::safe_link> link_mode;
+ typedef boost::intrusive::unordered_set<Node> NodeMap;
+ typedef boost::intrusive::list<Node> NodeList;
+ typedef std::pair<const TKey, TValue> TPair;
+
+ public:
+ typedef std::function<void(TKey, TValue&&)> PruneHookCall;
+
+ // iterator base : returns TPair on dereference
+ template <typename Value, typename TIterator>
+ class iterator_base
+ : public boost::iterator_adaptor<iterator_base<Value, TIterator>,
+ TIterator,
+ Value,
+ boost::bidirectional_traversal_tag > {
+ public:
+ iterator_base() {
+ }
+ explicit iterator_base(TIterator it)
+ : iterator_base::iterator_adaptor_(it) {
+ }
+ Value& dereference() const {
+ return this->base_reference()->pr;
+ }
+ };
+
+ // iterators
+ typedef iterator_base<
+ TPair, typename NodeList::iterator> iterator;
+ typedef iterator_base<
+ const TPair, typename NodeList::const_iterator> const_iterator;
+ typedef iterator_base<
+ TPair, typename NodeList::reverse_iterator> reverse_iterator;
+ typedef iterator_base<
+ const TPair,
+ typename NodeList::const_reverse_iterator> const_reverse_iterator;
+
+ /**
+ * Construct a EvictingCacheMap
+ * @param maxSize maximum size of the cache map. Once the map size exceeds
+ * maxSize, the map will begin to evict.
+ * @param clearSize the number of elements to clear at a time when the
+ * eviction size is reached.
+ */
+ explicit EvictingCacheMap(std::size_t maxSize, std::size_t clearSize = 1)
+ : nIndexBuckets_(std::max(maxSize / 2, std::size_t(kMinNumIndexBuckets))),
+ indexBuckets_(new typename NodeMap::bucket_type[nIndexBuckets_]),
+ indexTraits_(indexBuckets_.get(), nIndexBuckets_),
+ index_(indexTraits_),
+ maxSize_(maxSize),
+ clearSize_(clearSize) { }
+
+ EvictingCacheMap(const EvictingCacheMap&) = delete;
+ EvictingCacheMap& operator=(const EvictingCacheMap&) = delete;
+ EvictingCacheMap(EvictingCacheMap&&) = default;
+ EvictingCacheMap& operator=(EvictingCacheMap&&) = default;
+
+ ~EvictingCacheMap() {
+ setPruneHook(nullptr);
+ // ignore any potential exceptions from pruneHook_
+ pruneWithFailSafeOption(size(), nullptr, true);
+ }
+
+ /**
+ * Adjust the max size of EvictingCacheMap. Note that this does not update
+ * nIndexBuckets_ accordingly. This API can cause performance to get very
+ * bad, e.g., the nIndexBuckets_ is still 100 after maxSize is updated to 1M.
+ *
+ * Calling this function with an arugment of 0 removes the limit on the cache
+ * size and elements are not evicted unless clients explictly call prune.
+ *
+ * If you intend to resize dynamically using this, then picking an index size
+ * that works well and initializing with corresponding maxSize is the only
+ * reasonable option.
+ *
+ * @param maxSize new maximum size of the cache map.
+ * @param pruneHook callback to use on eviction.
+ */
+ void setMaxSize(size_t maxSize, PruneHookCall pruneHook = nullptr) {
+ if (maxSize != 0 && maxSize < size()) {
+ // Prune the excess elements with our new constraints.
+ prune(std::max(size() - maxSize, clearSize_), pruneHook);
+ }
+ maxSize_ = maxSize;
+ }
+
+ size_t getMaxSize() const {
+ return maxSize_;
+ }
+
+ void setClearSize(size_t clearSize) {
+ clearSize_ = clearSize;
+ }
+
+ /**
+ * Check for existence of a specific key in the map. This operation has
+ * no effect on LRU order.
+ * @param key key to search for
+ * @return true if exists, false otherwise
+ */
+ bool exists(const TKey& key) const {
+ return findInIndex(key) != index_.end();
+ }
+
+ /**
+ * Get the value associated with a specific key. This function always
+ * promotes a found value to the head of the LRU.
+ * @param key key associated with the value
+ * @return the value if it exists
+ * @throw std::out_of_range exception of the key does not exist
+ */
+ TValue& get(const TKey& key) {
+ auto it = find(key);
+ if (it == end()) {
+ std::__throw_out_of_range("Key does not exist");
+ }
+ return it->second;
+ }
+
+ /**
+ * Get the iterator associated with a specific key. This function always
+ * promotes a found value to the head of the LRU.
+ * @param key key to associate with value
+ * @return the iterator of the object (a std::pair of const TKey, TValue) or
+ * end() if it does not exist
+ */
+ iterator find(const TKey& key) {
+ auto it = findInIndex(key);
+ if (it == index_.end()) {
+ return end();
+ }
+ lru_.erase(lru_.iterator_to(*it));
+ lru_.push_front(*it);
+ return iterator(lru_.iterator_to(*it));
+ }
+
+ /**
+ * Get the value associated with a specific key. This function never
+ * promotes a found value to the head of the LRU.
+ * @param key key associated with the value
+ * @return the value if it exists
+ * @throw std::out_of_range exception of the key does not exist
+ */
+ const TValue& getWithoutPromotion(const TKey& key) const {
+ auto it = findWithoutPromotion(key);
+ if (it == end()) {
+ std::__throw_out_of_range("Key does not exist");
+ }
+ return it->second;
+ }
+
+ TValue& getWithoutPromotion(const TKey& key) {
+ auto const& cThis = *this;
+ return const_cast<TValue&>(cThis.getWithoutPromotion(key));
+ }
+
+ /**
+ * Get the iterator associated with a specific key. This function never
+ * promotes a found value to the head of the LRU.
+ * @param key key to associate with value
+ * @return the iterator of the object (a std::pair of const TKey, TValue) or
+ * end() if it does not exist
+ */
+ const_iterator findWithoutPromotion(const TKey& key) const {
+ auto it = findInIndex(key);
+ return (it == index_.end()) ? end() : const_iterator(lru_.iterator_to(*it));
+ }
+
+ iterator findWithoutPromotion(const TKey& key) {
+ auto it = findInIndex(key);
+ return (it == index_.end()) ? end() : iterator(lru_.iterator_to(*it));
+ }
+
+ /**
+ * Erase the key-value pair associated with key if it exists.
+ * @param key key associated with the value
+ * @return true if the key existed and was erased, else false
+ */
+ bool erase(const TKey& key) {
+ auto it = findInIndex(key);
+ if (it == index_.end()) {
+ return false;
+ }
+ auto node = &(*it);
+ std::unique_ptr<Node> nptr(node);
+ lru_.erase(lru_.iterator_to(*node));
+ index_.erase(it);
+ return true;
+ }
+
+ /**
+ * Set a key-value pair in the dictionary
+ * @param key key to associate with value
+ * @param value value to associate with the key
+ * @param promote boolean flag indicating whether or not to move something
+ * to the front of an LRU. This only really matters if you're setting
+ * a value that already exists.
+ * @param pruneHook callback to use on eviction (if it occurs).
+ */
+ void set(const TKey& key,
+ TValue value,
+ bool promote = true,
+ PruneHookCall pruneHook = nullptr) {
+ auto it = findInIndex(key);
+ if (it != index_.end()) {
+ it->pr.second = std::move(value);
+ if (promote) {
+ lru_.erase(lru_.iterator_to(*it));
+ lru_.push_front(*it);
+ }
+ } else {
+ auto node = new Node(key, std::move(value));
+ index_.insert(*node);
+ lru_.push_front(*node);
+
+ // no evictions if maxSize_ is 0 i.e. unlimited capacity
+ if (maxSize_ > 0 && size() > maxSize_) {
+ prune(clearSize_, pruneHook);
+ }
+ }
+ }
+
+ /**
+ * Get the number of elements in the dictionary
+ * @return the size of the dictionary
+ */
+ std::size_t size() const {
+ return index_.size();
+ }
+
+ /**
+ * Typical empty function
+ * @return true if empty, false otherwise
+ */
+ bool empty() const {
+ return index_.empty();
+ }
+
+ void clear(PruneHookCall pruneHook = nullptr) {
+ prune(size(), pruneHook);
+ }
+
+ /**
+ * Set the prune hook, which is the function invoked on the key and value
+ * on each eviction. Will throw If the pruneHook throws, unless the
+ * EvictingCacheMap object is being destroyed in which case it will
+ * be ignored.
+ * @param pruneHook new callback to use on eviction.
+ * @param promote boolean flag indicating whether or not to move something
+ * to the front of an LRU.
+ * @return the iterator of the object (a std::pair of const TKey, TValue) or
+ * end() if it does not exist
+ */
+ void setPruneHook(PruneHookCall pruneHook) {
+ pruneHook_ = pruneHook;
+ }
+
+
+ /**
+ * Prune the minimum of pruneSize and size() from the back of the LRU.
+ * Will throw if pruneHook throws.
+ * @param pruneSize minimum number of elements to prune
+ * @param pruneHook a custom pruneHook function
+ */
+ void prune(std::size_t pruneSize, PruneHookCall pruneHook = nullptr) {
+ // do not swallow exceptions for prunes not triggered from destructor
+ pruneWithFailSafeOption(pruneSize, pruneHook, false);
+ }
+
+ // Iterators and such
+ iterator begin() {
+ return iterator(lru_.begin());
+ }
+ iterator end() {
+ return iterator(lru_.end());
+ }
+ const_iterator begin() const {
+ return const_iterator(lru_.begin());
+ }
+ const_iterator end() const {
+ return const_iterator(lru_.end());
+ }
+
+ const_iterator cbegin() const {
+ return const_iterator(lru_.cbegin());
+ }
+ const_iterator cend() const {
+ return const_iterator(lru_.cend());
+ }
+
+ reverse_iterator rbegin() {
+ return reverse_iterator(lru_.rbegin());
+ }
+ reverse_iterator rend() {
+ return reverse_iterator(lru_.rend());
+ }
+
+ const_reverse_iterator rbegin() const {
+ return const_reverse_iterator(lru_.rbegin());
+ }
+ const_reverse_iterator rend() const {
+ return const_reverse_iterator(lru_.rend());
+ }
+
+ const_reverse_iterator crbegin() const {
+ return const_reverse_iterator(lru_.crbegin());
+ }
+ const_reverse_iterator crend() const {
+ return const_reverse_iterator(lru_.crend());
+ }
+
+ private:
+ struct Node
+ : public boost::intrusive::unordered_set_base_hook<link_mode>,
+ public boost::intrusive::list_base_hook<link_mode> {
+ Node(const TKey& key, TValue&& value)
+ : pr(std::make_pair(key, std::move(value))) {
+ }
+ TPair pr;
+ friend bool operator==(const Node& lhs, const Node& rhs) {
+ return lhs.pr.first == rhs.pr.first;
+ }
+ friend std::size_t hash_value(const Node& node) {
+ return THash()(node.pr.first);
+ }
+ };
+
+ struct KeyHasher {
+ std::size_t operator()(const Node& node) {
+ return THash()(node.pr.first);
+ }
+ std::size_t operator()(const TKey& key) {
+ return THash()(key);
+ }
+ };
+
+ struct KeyValueEqual {
+ bool operator()(const TKey& lhs, const Node& rhs) {
+ return lhs == rhs.pr.first;
+ }
+ bool operator()(const Node& lhs, const TKey& rhs) {
+ return lhs.pr.first == rhs;
+ }
+ };
+
+ /**
+ * Get the iterator in in the index associated with a specific key. This is
+ * merely a search in the index and does not promote the object.
+ * @param key key to associate with value
+ * @return the NodeMap::iterator to the Node containing the object
+ * (a std::pair of const TKey, TValue) or index_.end() if it does not exist
+ */
+ typename NodeMap::iterator findInIndex(const TKey& key) {
+ return index_.find(key, KeyHasher(), KeyValueEqual());
+ }
+
+ typename NodeMap::const_iterator findInIndex(const TKey& key) const {
+ return index_.find(key, KeyHasher(), KeyValueEqual());
+ }
+
+ /**
+ * Prune the minimum of pruneSize and size() from the back of the LRU.
+ * @param pruneSize minimum number of elements to prune
+ * @param pruneHook a custom pruneHook function
+ * @param failSafe true if exceptions are to ignored, false by default
+ */
+ void pruneWithFailSafeOption(std::size_t pruneSize,
+ PruneHookCall pruneHook, bool failSafe) {
+ auto& ph = (nullptr == pruneHook) ? pruneHook_ : pruneHook;
+
+ for (std::size_t i = 0; i < pruneSize && !lru_.empty(); i++) {
+ auto *node = &(*lru_.rbegin());
+ std::unique_ptr<Node> nptr(node);
+
+ lru_.erase(lru_.iterator_to(*node));
+ index_.erase(index_.iterator_to(*node));
+ if (ph) {
+ try {
+ ph(node->pr.first, std::move(node->pr.second));
+ } catch (...) {
+ if (!failSafe) {
+ throw;
+ }
+ }
+ }
+ }
+ }
+
+ static const std::size_t kMinNumIndexBuckets = 100;
+ PruneHookCall pruneHook_;
+ std::size_t nIndexBuckets_;
+ std::unique_ptr<typename NodeMap::bucket_type[]> indexBuckets_;
+ typename NodeMap::bucket_traits indexTraits_;
+ NodeMap index_;
+ NodeList lru_;
+ std::size_t maxSize_;
+ std::size_t clearSize_;
+};
+
+} // namespace folly
--- /dev/null
+/*
+ * Copyright 2017-present Facebook, Inc.
+ *
+ * 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
+ *
+ * http://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 <cassert>
+#include <cstdint>
+#include <initializer_list>
+#include <iterator>
+#include <tuple>
+#include <type_traits>
+#include <utility>
+
+#include <folly/Portability.h>
+#include <folly/Traits.h>
+
+namespace folly {
+
+namespace for_each_detail {
+
+namespace adl {
+
+/* using override */
+using std::begin;
+/* using override */
+using std::end;
+/* using override */
+using std::get;
+
+/**
+ * The adl_ functions below lookup the function name in the namespace of the
+ * type of the object being passed into the function. If no function with
+ * that name exists for the passed object then the default std:: versions are
+ * going to be called
+ */
+template <std::size_t Index, typename Type>
+auto adl_get(Type&& instance) -> decltype(get<Index>(std::declval<Type>())) {
+ return get<Index>(std::forward<Type>(instance));
+}
+template <typename Type>
+auto adl_begin(Type&& instance) -> decltype(begin(instance)) {
+ return begin(instance);
+}
+template <typename Type>
+auto adl_end(Type&& instance) -> decltype(end(instance)) {
+ return end(instance);
+}
+
+} // namespace adl
+
+/**
+ * Enable if the range supports fetching via non member get<>()
+ */
+template <typename T>
+using EnableIfNonMemberGetFound =
+ void_t<decltype(adl::adl_get<0>(std::declval<T>()))>;
+/**
+ * Enable if the range supports fetching via a member get<>()
+ */
+template <typename T>
+using EnableIfMemberGetFound =
+ void_t<decltype(std::declval<T>().template get<0>())>;
+
+/**
+ * A get that tries ADL get<> first and if that is not found tries to execute
+ * a member function get<> on the instance, just as proposed by the structured
+ * bindings proposal here 11.5.3
+ * http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4659.pdf
+ */
+template <std::size_t Index, typename Type, typename = void>
+struct Get {
+ template <typename T>
+ static auto impl(T&& instance)
+ -> decltype(adl::adl_get<Index>(std::declval<T>())) {
+ return adl::adl_get<Index>(std::forward<T>(instance));
+ }
+};
+template <std::size_t Index, typename Type>
+struct Get<Index, Type, EnableIfMemberGetFound<Type>> {
+ template <typename T>
+ static auto impl(T&& instance)
+ -> decltype(std::declval<T>().template get<Index>()) {
+ return std::forward<T>(instance).template get<Index>();
+ }
+};
+
+/**
+ * Concepts-ish
+ */
+/**
+ * Check if the range is a tuple or a range
+ */
+template <typename Type, typename T = typename std::decay<Type>::type>
+using EnableIfTuple = void_t<
+ decltype(Get<0, T>::impl(std::declval<T>())),
+ decltype(std::tuple_size<T>::value)>;
+
+/**
+ * Check if the range is a range
+ */
+template <typename Type, typename T = typename std::decay<Type>::type>
+using EnableIfRange = void_t<
+ decltype(adl::adl_begin(std::declval<T>())),
+ decltype(adl::adl_end(std::declval<T>()))>;
+
+/**
+ * Forwards the return value of the first element of the range, used to
+ * determine the type of the first element in the range in SFINAE use cases
+ */
+template <typename Sequence, typename = void>
+struct DeclvalSequence {
+ using type = decltype(*(adl::adl_begin(std::declval<Sequence>())));
+};
+
+template <typename Sequence>
+struct DeclvalSequence<Sequence, EnableIfTuple<Sequence>> {
+ using type = decltype(Get<0, Sequence>::impl(std::declval<Sequence>()));
+};
+
+/**
+ * Check if the functor accepts one or two arguments, one of the first element
+ * in the range, assuming that all the other elements can also be passed to the
+ * functor, and the second being an instantiation of std::integral_constant,
+ * and the third being an instantiation of LoopControl, to provide
+ * breakability to the loop
+ */
+template <typename Sequence, typename Func>
+using EnableIfAcceptsOneArgument = void_t<decltype(std::declval<Func>()(
+ std::declval<typename DeclvalSequence<Sequence>::type>()))>;
+template <typename Sequence, typename Func>
+using EnableIfAcceptsTwoArguments = void_t<decltype(std::declval<Func>()(
+ std::declval<typename DeclvalSequence<Sequence>::type>(),
+ std::integral_constant<std::size_t, 0>{}))>;
+template <typename Sequence, typename Func>
+using EnableIfAcceptsThreeArguments = void_t<decltype(std::declval<Func>()(
+ std::declval<typename DeclvalSequence<Sequence>::type>(),
+ std::integral_constant<std::size_t, 0>{},
+ adl::adl_begin(std::declval<Sequence>())))>;
+template <typename Sequence, typename Func>
+using EnableIfBreaksRange = std::enable_if_t<std::is_same<
+ typename std::decay<decltype(std::declval<Func>()(
+ std::declval<typename DeclvalSequence<Sequence>::type>(),
+ std::size_t{0},
+ adl::adl_begin(std::declval<Sequence>())))>::type,
+ LoopControl>::value>;
+template <typename Sequence, typename Func>
+using EnableIfBreaksTuple = std::enable_if_t<std::is_same<
+ typename std::decay<decltype(std::declval<Func>()(
+ std::declval<typename DeclvalSequence<Sequence>::type>(),
+ std::integral_constant<std::size_t, 0>{}))>::type,
+ LoopControl>::value>;
+/**
+ * Enables if the sequence has random access iterators
+ */
+template <typename Sequence>
+using EnableIfRandomAccessIterators = std::enable_if_t<std::is_same<
+ typename std::iterator_traits<typename std::decay<decltype(
+ adl::adl_begin(std::declval<Sequence>()))>::type>::iterator_category,
+ std::random_access_iterator_tag>::value>;
+template <typename Sequence, typename Index>
+using EnableIfHasIndexingOperator =
+ void_t<decltype(std::declval<Sequence>()[std::declval<Index>()])>;
+
+/**
+ * Implementation for the range iteration, this provides specializations in
+ * the case where the function returns a break or continue.
+ */
+template <typename Seq, typename F, typename = void>
+struct ForEachRange {
+ template <typename Sequence, typename Func>
+ static void impl(Sequence&& range, Func& func) {
+ auto first = adl::adl_begin(range);
+ auto last = adl::adl_end(range);
+ for (auto index = std::size_t{0}; first != last; ++index) {
+ auto next = std::next(first);
+ func(*first, index, first);
+ first = next;
+ }
+ }
+};
+
+template <typename Seq, typename F>
+struct ForEachRange<Seq, F, EnableIfBreaksRange<Seq, F>> {
+ template <typename Sequence, typename Func>
+ static void impl(Sequence&& range, Func& func) {
+ auto first = adl::adl_begin(range);
+ auto last = adl::adl_end(range);
+ for (auto index = std::size_t{0}; first != last; ++index) {
+ auto next = std::next(first);
+ if (loop_break == func(*first, index, first)) {
+ break;
+ }
+ first = next;
+ }
+ }
+};
+
+/**
+ * Implementations for the runtime function
+ */
+template <
+ typename Sequence,
+ typename Func,
+ EnableIfAcceptsThreeArguments<Sequence, Func>* = nullptr>
+void for_each_range_impl(Sequence&& range, Func& func) {
+ ForEachRange<Sequence, Func>::impl(std::forward<Sequence>(range), func);
+}
+template <
+ typename Sequence,
+ typename Func,
+ EnableIfAcceptsTwoArguments<Sequence, Func>* = nullptr>
+void for_each_range_impl(Sequence&& range, Func& func) {
+ // make a three arg adaptor for the function passed in so that the main
+ // implementation function can be used
+ auto three_arg_adaptor = [&func](
+ auto&& ele, auto index, auto) -> decltype(auto) {
+ return func(std::forward<decltype(ele)>(ele), index);
+ };
+ for_each_range_impl(std::forward<Sequence>(range), three_arg_adaptor);
+}
+
+template <
+ typename Sequence,
+ typename Func,
+ EnableIfAcceptsOneArgument<Sequence, Func>* = nullptr>
+void for_each_range_impl(Sequence&& range, Func& func) {
+ // make a three argument adaptor for the function passed in that just ignores
+ // the second and third argument
+ auto three_arg_adaptor = [&func](auto&& ele, auto, auto) -> decltype(auto) {
+ return func(std::forward<decltype(ele)>(ele));
+ };
+ for_each_range_impl(std::forward<Sequence>(range), three_arg_adaptor);
+}
+
+/**
+ * Handlers for iteration
+ */
+/**
+ * The class provides a way to tell whether the function passed in to the
+ * algorithm returns an instance of LoopControl, if it does then the break-able
+ * implementation will be used. If the function provided to the algorithm
+ * does not use the break API, then the basic no break, 0 overhead
+ * implementation will be used
+ */
+template <typename Seq, typename F, typename = void>
+struct ForEachTupleImpl {
+ template <typename Sequence, typename Func, std::size_t... Indices>
+ static void
+ impl(Sequence&& seq, Func& func, std::index_sequence<Indices...>) {
+ // unroll the loop in an initializer list construction parameter expansion
+ // pack
+ static_cast<void>(std::initializer_list<int>{
+ (func(
+ Get<Indices, Sequence>::impl(std::forward<Sequence>(seq)),
+ std::integral_constant<std::size_t, Indices>{}),
+ 0)...});
+ }
+};
+template <typename Seq, typename F>
+struct ForEachTupleImpl<Seq, F, EnableIfBreaksTuple<Seq, F>> {
+ template <typename Sequence, typename Func, std::size_t... Indices>
+ static void
+ impl(Sequence&& seq, Func& func, std::index_sequence<Indices...>) {
+ // unroll the loop in an initializer list construction parameter expansion
+ // pack
+ LoopControl break_or_not = LoopControl::CONTINUE;
+
+ // cast to void to ignore the result, use the initialzer list constructor
+ // to do the loop execution, the ternary conditional will decide whether
+ // or not to evaluate the result
+ static_cast<void>(std::initializer_list<int>{
+ (((break_or_not == loop_continue)
+ ? (break_or_not = func(
+ Get<Indices, Sequence>::impl(std::forward<Sequence>(seq)),
+ std::integral_constant<std::size_t, Indices>{}))
+ : (loop_continue)),
+ 0)...});
+ }
+};
+
+/**
+ * The two top level compile time loop iteration functions handle the dispatch
+ * based on the number of arguments the passed in function can be passed, if 2
+ * arguments can be passed then the implementation dispatches work further to
+ * the implementation classes above. If not then an adaptor is constructed
+ * which is passed on to the 2 argument specialization, which then in turn
+ * forwards implementation to the implementation classes above
+ */
+template <
+ typename Sequence,
+ typename Func,
+ EnableIfAcceptsTwoArguments<Sequence, Func>* = nullptr>
+void for_each_tuple_impl(Sequence&& seq, Func& func) {
+ // pass the length as an index sequence to the implementation as an
+ // optimization over manual template "tail recursion" unrolling
+ constexpr auto length =
+ std::tuple_size<typename std::decay<Sequence>::type>::value;
+ ForEachTupleImpl<Sequence, Func>::impl(
+ std::forward<Sequence>(seq), func, std::make_index_sequence<length>{});
+}
+template <
+ typename Sequence,
+ typename Func,
+ EnableIfAcceptsOneArgument<Sequence, Func>* = nullptr>
+void for_each_tuple_impl(Sequence&& seq, Func& func) {
+ // make an adaptor for the function passed in, in case it can only be passed
+ // on argument
+ auto two_arg_adaptor = [&func](auto&& ele, auto) -> decltype(auto) {
+ return func(std::forward<decltype(ele)>(ele));
+ };
+ for_each_tuple_impl(std::forward<Sequence>(seq), two_arg_adaptor);
+}
+
+/**
+ * Top level handlers for the for_each loop, the basic specialization handles
+ * ranges and the specialized version handles compile time ranges (tuple like)
+ *
+ * This implies that if a range is a compile time range, its compile time
+ * get<> API (whether through a member function or through a ADL looked up
+ * method) will be used in preference over iterators
+ */
+template <typename R, typename = void>
+struct ForEachImpl {
+ template <typename Sequence, typename Func>
+ static void impl(Sequence&& range, Func& func) {
+ for_each_tuple_impl(std::forward<Sequence>(range), func);
+ }
+};
+template <typename R>
+struct ForEachImpl<R, EnableIfRange<R>> {
+ template <typename Sequence, typename Func>
+ static void impl(Sequence&& range, Func& func) {
+ for_each_range_impl(std::forward<Sequence>(range), func);
+ }
+};
+
+template <typename S, typename I, typename = void>
+struct FetchIteratorIndexImpl {
+ template <typename Sequence, typename Index>
+ static decltype(auto) impl(Sequence&& sequence, Index&& index) {
+ return std::forward<Sequence>(sequence)[std::forward<Index>(index)];
+ }
+};
+template <typename S, typename I>
+struct FetchIteratorIndexImpl<S, I, EnableIfRandomAccessIterators<S>> {
+ template <typename Sequence, typename Index>
+ static decltype(auto) impl(Sequence&& sequence, Index index) {
+ return *(adl::adl_begin(std::forward<Sequence>(sequence)) + index);
+ }
+};
+template <typename S, typename = void>
+struct FetchImpl {
+ template <typename Sequence, typename Index>
+ static decltype(auto) impl(Sequence&& sequence, Index index) {
+ return Get<static_cast<std::size_t>(index), Sequence>::impl(
+ std::forward<Sequence>(sequence));
+ }
+};
+template <typename S>
+struct FetchImpl<S, EnableIfRange<S>> {
+ template <typename Sequence, typename Index>
+ static decltype(auto) impl(Sequence&& sequence, Index&& index) {
+ return FetchIteratorIndexImpl<Sequence, Index>::impl(
+ std::forward<Sequence>(sequence), std::forward<Index>(index));
+ }
+};
+
+} // namespace for_each_detail
+
+template <typename Sequence, typename Func>
+FOLLY_CPP14_CONSTEXPR Func for_each(Sequence&& range, Func func) {
+ for_each_detail::ForEachImpl<typename std::decay<Sequence>::type>::impl(
+ std::forward<Sequence>(range), func);
+ return func;
+}
+
+template <typename Sequence, typename Index>
+FOLLY_CPP14_CONSTEXPR decltype(auto) fetch(Sequence&& sequence, Index&& index) {
+ return for_each_detail::FetchImpl<Sequence>::impl(
+ std::forward<Sequence>(sequence), std::forward<Index>(index));
+}
+
+} // namespace folly
--- /dev/null
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * 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
+ *
+ * http://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.
+ */
+
+#pragma once
+
+#include <folly/Portability.h>
+#include <folly/Preprocessor.h>
+
+#include <type_traits>
+
+namespace folly {
+
+/**
+ * @function for_each
+ *
+ * folly::for_each is a generalized iteration algorithm. Example:
+ *
+ * auto one = std::make_tuple(1, 2, 3);
+ * auto two = std::vector<int>{1, 2, 3};
+ * auto func = [](auto element, auto index) {
+ * cout << index << " : " << element << endl;
+ * };
+ * folly::for_each(one, func);
+ * folly::for_each(two, func);
+ *
+ * The for_each function allows iteration through sequences, these
+ * can either be runtime sequences (i.e. entities for which std::begin and
+ * std::end work) or compile time sequences (as deemed by the presence of
+ * std::tuple_length<>, get<> (ADL resolved) functions)
+ *
+ * The function is made to provide a convenient library based alternative to
+ * the proposal p0589r0, which aims to generalize the range based for loop
+ * even further to work with compile time sequences.
+ *
+ * A drawback of using range based for loops is that sometimes you do not have
+ * access to the index within the range. This provides easy access to that,
+ * even with compile time sequences.
+ *
+ * And breaking out is easy
+ *
+ * auto range_one = std::vector<int>{1, 2, 3};
+ * auto range_two = std::make_tuple(1, 2, 3);
+ * auto func = [](auto ele, auto index) {
+ * cout << "Element at index " << index << " : " << ele;
+ * if (index == 1) {
+ * return folly::loop_break;
+ * }
+ * return folly::loop_continue;
+ * };
+ * folly_for_each(range_one, func);
+ * folly_for_each(range_two, func);
+ *
+ * A simple use case would be when using futures, if the user was doing calls
+ * to n servers then they would accept the callback with the futures like this
+ *
+ * auto vec = std::vector<std::future<int>>{request_one(), ...};
+ * when_all(vec.begin(), vec.end()).then([](auto futures) {
+ * folly::for_each(futures, [](auto& fut) { ... });
+ * });
+ *
+ * Now when this code switches to use tuples instead of the runtime
+ * std::vector, then the loop does not need to change, the code will still
+ * work just fine
+ *
+ * when_all(future_one, future_two, future_three).then([](auto futures) {
+ * folly::for_each(futures, [](auto& fut) { ... });
+ * });
+ */
+template <typename Range, typename Func>
+FOLLY_CPP14_CONSTEXPR Func for_each(Range&& range, Func func);
+
+/**
+ * The user should return loop_break and loop_continue if they want to iterate
+ * in such a way that they can preemptively stop the loop and break out when
+ * certain conditions are met
+ */
+namespace for_each_detail {
+enum class LoopControl : bool { BREAK, CONTINUE };
+} // namespace for_each_detail
+
+constexpr auto loop_break = for_each_detail::LoopControl::BREAK;
+constexpr auto loop_continue = for_each_detail::LoopControl::CONTINUE;
+
+/**
+ * Utility method to help access elements of a sequence with one uniform
+ * interface
+ *
+ * This can be useful for example when you are looping through a sequence and
+ * want to modify another sequence based on the information in the current
+ * sequence
+ *
+ * auto range_one = std::make_tuple(1, 2, 3);
+ * auto range_two = std::make_tuple(4, 5, 6);
+ * folly::for_each(range_one, [&range_two](auto ele, auto index) {
+ * folly::fetch(range_two, index) = ele;
+ * });
+ *
+ * For non-tuple like ranges, this works by first trying to use the iterator
+ * class if the iterator has been marked to be a random access iterator. This
+ * should be inspectable via the std::iterator_traits traits class. If the
+ * iterator class is not present or is not a random access iterator then the
+ * implementation falls back to trying to use the indexing operator
+ * (operator[]) to fetch the required element
+ */
+template <typename Sequence, typename Index>
+FOLLY_CPP14_CONSTEXPR decltype(auto) fetch(Sequence&& sequence, Index&& index);
+
+} // namespace folly
+
+/**
+ * Everything below this is deprecated. Use the folly::for_each algorithm above
+ * instead
+ */
+/*
+ * Form a local variable name from "FOR_EACH_" x __LINE__, so that
+ * FOR_EACH can be nested without creating shadowed declarations.
+ */
+#define _FE_ANON(x) FB_CONCATENATE(FOR_EACH_, FB_CONCATENATE(x, __LINE__))
+
+/*
+ * If you just want the element values, please use:
+ *
+ * for (auto&& element : collection)
+ *
+ * If you need access to the iterators please write an explicit iterator loop
+ */
+#define FOR_EACH(i, c) \
+ if (bool _FE_ANON(s1_) = false) {} else \
+ for (auto && _FE_ANON(s2_) = (c); \
+ !_FE_ANON(s1_); _FE_ANON(s1_) = true) \
+ for (auto i = _FE_ANON(s2_).begin(); \
+ i != _FE_ANON(s2_).end(); ++i)
+
+/*
+ * If you just want the element values, please use this (ranges-v3) construct:
+ *
+ * for (auto&& element : collection | view::reverse)
+ *
+ * If you need access to the iterators please write an explicit iterator loop
+ */
+#define FOR_EACH_R(i, c) \
+ if (bool _FE_ANON(s1_) = false) {} else \
+ for (auto && _FE_ANON(s2_) = (c); \
+ !_FE_ANON(s1_); _FE_ANON(s1_) = true) \
+ for (auto i = _FE_ANON(s2_).rbegin(); \
+ i != _FE_ANON(s2_).rend(); ++i)
+
+/*
+ * If you just want the element values, please use this (ranges-v3) construct:
+ *
+ * for (auto&& element : collection | view::zip(view::ints))
+ *
+ * If you need access to the iterators please write an explicit iterator loop
+ * and use a counter variable
+ */
+#define FOR_EACH_ENUMERATE(count, i, c) \
+ if (bool _FE_ANON(s1_) = false) {} else \
+ for (auto && FOR_EACH_state2 = (c); \
+ !_FE_ANON(s1_); _FE_ANON(s1_) = true) \
+ if (size_t _FE_ANON(n1_) = 0) {} else \
+ if (const size_t& count = _FE_ANON(n1_)) {} else \
+ for (auto i = FOR_EACH_state2.begin(); \
+ i != FOR_EACH_state2.end(); ++_FE_ANON(n1_), ++i)
+/**
+ * If you just want the keys, please use this (ranges-v3) construct:
+ *
+ * for (auto&& element : collection | view::keys)
+ *
+ * If you just want the values, please use this (ranges-v3) construct:
+ *
+ * for (auto&& element : collection | view::values)
+ *
+ * If you need to see both, use:
+ *
+ * for (auto&& element : collection) {
+ * auto const& key = element.first;
+ * auto& value = element.second;
+ * ......
+ * }
+ *
+ */
+#define FOR_EACH_KV(k, v, c) \
+ if (unsigned int _FE_ANON(s1_) = 0) {} else \
+ for (auto && _FE_ANON(s2_) = (c); \
+ !_FE_ANON(s1_); _FE_ANON(s1_) = 1) \
+ for (auto _FE_ANON(s3_) = _FE_ANON(s2_).begin(); \
+ _FE_ANON(s3_) != _FE_ANON(s2_).end(); \
+ _FE_ANON(s1_) == 2 \
+ ? ((_FE_ANON(s1_) = 0), ++_FE_ANON(s3_)) \
+ : (_FE_ANON(s3_) = _FE_ANON(s2_).end())) \
+ for (auto &k = _FE_ANON(s3_)->first; \
+ !_FE_ANON(s1_); ++_FE_ANON(s1_)) \
+ for (auto &v = _FE_ANON(s3_)->second; \
+ !_FE_ANON(s1_); ++_FE_ANON(s1_))
+
+namespace folly { namespace detail {
+
+// Boost 1.48 lacks has_less, we emulate a subset of it here.
+template <typename T, typename U>
+class HasLess {
+ struct BiggerThanChar { char unused[2]; };
+ template <typename C, typename D> static char test(decltype(C() < D())*);
+ template <typename, typename> static BiggerThanChar test(...);
+
+ public:
+ enum { value = sizeof(test<T, U>(nullptr)) == 1 };
+};
+
+/**
+ * notThereYet helps the FOR_EACH_RANGE macro by opportunistically
+ * using "<" instead of "!=" whenever available when checking for loop
+ * termination. This makes e.g. examples such as FOR_EACH_RANGE (i,
+ * 10, 5) execute zero iterations instead of looping virtually
+ * forever. At the same time, some iterator types define "!=" but not
+ * "<". The notThereYet function will dispatch differently for those.
+ *
+ * Below is the correct implementation of notThereYet. It is disabled
+ * because of a bug in Boost 1.46: The filesystem::path::iterator
+ * defines operator< (via boost::iterator_facade), but that in turn
+ * uses distance_to which is undefined for that particular
+ * iterator. So HasLess (defined above) identifies
+ * boost::filesystem::path as properly comparable with <, but in fact
+ * attempting to do so will yield a compile-time error.
+ *
+ * The else branch (active) contains a conservative
+ * implementation.
+ */
+
+#if 0
+
+template <class T, class U>
+typename std::enable_if<HasLess<T, U>::value, bool>::type
+notThereYet(T& iter, const U& end) {
+ return iter < end;
+}
+
+template <class T, class U>
+typename std::enable_if<!HasLess<T, U>::value, bool>::type
+notThereYet(T& iter, const U& end) {
+ return iter != end;
+}
+
+#else
+
+template <class T, class U>
+typename std::enable_if<
+ (std::is_arithmetic<T>::value && std::is_arithmetic<U>::value) ||
+ (std::is_pointer<T>::value && std::is_pointer<U>::value),
+ bool>::type
+notThereYet(T& iter, const U& end) {
+ return iter < end;
+}
+
+template <class T, class U>
+typename std::enable_if<
+ !(
+ (std::is_arithmetic<T>::value && std::is_arithmetic<U>::value) ||
+ (std::is_pointer<T>::value && std::is_pointer<U>::value)
+ ),
+ bool>::type
+notThereYet(T& iter, const U& end) {
+ return iter != end;
+}
+
+#endif
+
+
+/**
+ * downTo is similar to notThereYet, but in reverse - it helps the
+ * FOR_EACH_RANGE_R macro.
+ */
+template <class T, class U>
+typename std::enable_if<HasLess<U, T>::value, bool>::type
+downTo(T& iter, const U& begin) {
+ return begin < iter--;
+}
+
+template <class T, class U>
+typename std::enable_if<!HasLess<U, T>::value, bool>::type
+downTo(T& iter, const U& begin) {
+ if (iter == begin) {
+ return false;
+ }
+ --iter;
+ return true;
+}
+
+} }
+
+/*
+ * Look at the Ranges-v3 views and you'll probably find an easier way to build
+ * the view you want but the equivalent is roughly:
+ *
+ * for (auto& element : make_iterator_range(begin, end))
+ */
+#define FOR_EACH_RANGE(i, begin, end) \
+ for (auto i = (true ? (begin) : (end)); \
+ ::folly::detail::notThereYet(i, (end)); \
+ ++i)
+
+/*
+ * Look at the Ranges-v3 views and you'll probably find an easier way to build
+ * the view you want but the equivalent is roughly:
+ *
+ * for (auto& element : make_iterator_range(begin, end) | view::reverse)
+ */
+#define FOR_EACH_RANGE_R(i, begin, end) \
+ for (auto i = (false ? (begin) : (end)); ::folly::detail::downTo(i, (begin));)
+
+#include <folly/container/Foreach-inl.h>
--- /dev/null
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * 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
+ *
+ * http://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.
+ */
+
+#pragma once
+
+#include <functional>
+#include <iterator>
+#include <memory>
+#include <tuple>
+#include <type_traits>
+#include <utility>
+
+#include <folly/Functional.h>
+
+namespace folly {
+
+/**
+ * Argument tuple for variadic emplace/constructor calls. Stores arguments by
+ * (decayed) value. Restores original argument types with reference qualifiers
+ * and adornments at unpack time to emulate perfect forwarding.
+ *
+ * Uses inheritance instead of a type alias to std::tuple so that emplace
+ * iterators with implicit unpacking disabled can distinguish between
+ * emplace_args and std::tuple parameters.
+ *
+ * @seealso folly::make_emplace_args
+ * @seealso folly::get_emplace_arg
+ */
+template <typename... Args>
+struct emplace_args : public std::tuple<std::decay_t<Args>...> {
+ using storage_type = std::tuple<std::decay_t<Args>...>;
+ using storage_type::storage_type;
+};
+
+/**
+ * Pack arguments in a tuple for assignment to a folly::emplace_iterator,
+ * folly::front_emplace_iterator, or folly::back_emplace_iterator. The
+ * iterator's operator= will unpack the tuple and pass the unpacked arguments
+ * to the container's emplace function, which in turn forwards the arguments to
+ * the (multi-argument) constructor of the target class.
+ *
+ * Argument tuples generated with folly::make_emplace_args will be unpacked
+ * before being passed to the container's emplace function, even for iterators
+ * where implicit_unpack is set to false (so they will not implicitly unpack
+ * std::pair or std::tuple arguments to operator=).
+ *
+ * Arguments are copied (lvalues) or moved (rvalues). To avoid copies and moves,
+ * wrap references using std::ref(), std::cref(), and folly::rref(). Beware of
+ * dangling references, especially references to temporary objects created with
+ * folly::rref().
+ *
+ * Note that an argument pack created with folly::make_emplace_args is different
+ * from an argument pack created with std::make_pair or std::make_tuple.
+ * Specifically, passing a std::pair&& or std::tuple&& to an emplace iterator's
+ * operator= will pass rvalue references to all fields of that tuple to the
+ * container's emplace function, while passing an emplace_args&& to operator=
+ * will cast those field references to the exact argument types as passed to
+ * folly::make_emplace_args previously. If all arguments have been wrapped by
+ * std::reference_wrappers or folly::rvalue_reference_wrappers, the result will
+ * be the same as if the container's emplace function had been called directly
+ * (perfect forwarding), with no temporary copies of the arguments.
+ *
+ * @seealso folly::rref
+ *
+ * @example
+ * class Widget { Widget(int, int); };
+ * std::vector<Widget> makeWidgets(const std::vector<int>& in) {
+ * std::vector<Widget> out;
+ * std::transform(
+ * in.begin(),
+ * in.end(),
+ * folly::back_emplacer(out),
+ * [](int i) { return folly::make_emplace_args(i, i); });
+ * return out;
+ * }
+ */
+template <typename... Args>
+emplace_args<Args...> make_emplace_args(Args&&... args) noexcept(
+ noexcept(emplace_args<Args...>(std::forward<Args>(args)...))) {
+ return emplace_args<Args...>(std::forward<Args>(args)...);
+}
+
+namespace detail {
+template <typename Arg>
+decltype(auto) unwrap_emplace_arg(Arg&& arg) noexcept {
+ return std::forward<Arg>(arg);
+}
+template <typename Arg>
+decltype(auto) unwrap_emplace_arg(std::reference_wrapper<Arg> arg) noexcept {
+ return arg.get();
+}
+template <typename Arg>
+decltype(auto) unwrap_emplace_arg(
+ folly::rvalue_reference_wrapper<Arg> arg) noexcept {
+ return std::move(arg).get();
+}
+}
+
+/**
+ * Getter function for unpacking a single emplace argument.
+ *
+ * Calling get_emplace_arg on an emplace_args rvalue reference results in
+ * perfect forwarding of the original input types. A special case are
+ * std::reference_wrapper and folly::rvalue_reference_wrapper objects within
+ * folly::emplace_args. These are also unwrapped so that the bare reference is
+ * returned.
+ *
+ * std::get is not a customization point in the standard library, so the
+ * cleanest solution was to define our own getter function.
+ */
+template <size_t I, typename... Args>
+decltype(auto) get_emplace_arg(emplace_args<Args...>&& args) noexcept {
+ using Out = std::tuple<Args...>;
+ return detail::unwrap_emplace_arg(
+ std::forward<std::tuple_element_t<I, Out>>(std::get<I>(args)));
+}
+template <size_t I, typename... Args>
+decltype(auto) get_emplace_arg(emplace_args<Args...>& args) noexcept {
+ return detail::unwrap_emplace_arg(std::get<I>(args));
+}
+template <size_t I, typename... Args>
+decltype(auto) get_emplace_arg(const emplace_args<Args...>& args) noexcept {
+ return detail::unwrap_emplace_arg(std::get<I>(args));
+}
+template <size_t I, typename Args>
+decltype(auto) get_emplace_arg(Args&& args) noexcept {
+ return std::get<I>(std::move(args));
+}
+template <size_t I, typename Args>
+decltype(auto) get_emplace_arg(Args& args) noexcept {
+ return std::get<I>(args);
+}
+template <size_t I, typename Args>
+decltype(auto) get_emplace_arg(const Args& args) noexcept {
+ return std::get<I>(args);
+}
+
+namespace detail {
+/**
+ * Emplace implementation class for folly::emplace_iterator.
+ */
+template <typename Container>
+struct Emplace {
+ Emplace(Container& c, typename Container::iterator i)
+ : container(std::addressof(c)), iter(std::move(i)) {}
+ template <typename... Args>
+ void emplace(Args&&... args) {
+ iter = container->emplace(iter, std::forward<Args>(args)...);
+ ++iter;
+ }
+ Container* container;
+ typename Container::iterator iter;
+};
+
+/**
+ * Emplace implementation class for folly::hint_emplace_iterator.
+ */
+template <typename Container>
+struct EmplaceHint {
+ EmplaceHint(Container& c, typename Container::iterator i)
+ : container(std::addressof(c)), iter(std::move(i)) {}
+ template <typename... Args>
+ void emplace(Args&&... args) {
+ iter = container->emplace_hint(iter, std::forward<Args>(args)...);
+ ++iter;
+ }
+ Container* container;
+ typename Container::iterator iter;
+};
+
+/**
+ * Emplace implementation class for folly::front_emplace_iterator.
+ */
+template <typename Container>
+struct EmplaceFront {
+ explicit EmplaceFront(Container& c) : container(std::addressof(c)) {}
+ template <typename... Args>
+ void emplace(Args&&... args) {
+ container->emplace_front(std::forward<Args>(args)...);
+ }
+ Container* container;
+};
+
+/**
+ * Emplace implementation class for folly::back_emplace_iterator.
+ */
+template <typename Container>
+struct EmplaceBack {
+ explicit EmplaceBack(Container& c) : container(std::addressof(c)) {}
+ template <typename... Args>
+ void emplace(Args&&... args) {
+ container->emplace_back(std::forward<Args>(args)...);
+ }
+ Container* container;
+};
+
+/**
+ * Generic base class and implementation of all emplace iterator classes.
+ *
+ * Uses the curiously recurring template pattern (CRTP) to cast `this*` to
+ * `Derived*`; i.e., to implement covariant return types in a generic manner.
+ */
+template <typename Derived, typename EmplaceImpl, bool implicit_unpack>
+class emplace_iterator_base;
+
+/**
+ * Partial specialization of emplace_iterator_base with implicit unpacking
+ * disabled.
+ */
+template <typename Derived, typename EmplaceImpl>
+class emplace_iterator_base<Derived, EmplaceImpl, false>
+ : protected EmplaceImpl /* protected implementation inheritance */ {
+ public:
+ // Iterator traits.
+ using iterator_category = std::output_iterator_tag;
+ using value_type = void;
+ using difference_type = void;
+ using pointer = void;
+ using reference = void;
+ using container_type =
+ std::remove_reference_t<decltype(*EmplaceImpl::container)>;
+
+ using EmplaceImpl::EmplaceImpl;
+
+ /**
+ * Canonical output operator. Forwards single argument straight to container's
+ * emplace function.
+ */
+ template <typename T>
+ Derived& operator=(T&& arg) {
+ this->emplace(std::forward<T>(arg));
+ return static_cast<Derived&>(*this);
+ }
+
+ /**
+ * Special output operator for packed arguments. Unpacks args and performs
+ * variadic call to container's emplace function.
+ */
+ template <typename... Args>
+ Derived& operator=(emplace_args<Args...>& args) {
+ return unpackAndEmplace(args, std::index_sequence_for<Args...>{});
+ }
+ template <typename... Args>
+ Derived& operator=(const emplace_args<Args...>& args) {
+ return unpackAndEmplace(args, std::index_sequence_for<Args...>{});
+ }
+ template <typename... Args>
+ Derived& operator=(emplace_args<Args...>&& args) {
+ return unpackAndEmplace(
+ std::move(args), std::index_sequence_for<Args...>{});
+ }
+
+ // No-ops.
+ Derived& operator*() {
+ return static_cast<Derived&>(*this);
+ }
+ Derived& operator++() {
+ return static_cast<Derived&>(*this);
+ }
+ Derived& operator++(int) {
+ return static_cast<Derived&>(*this);
+ }
+
+ // We need all of these explicit defaults because the custom operator=
+ // overloads disable implicit generation of these functions.
+ emplace_iterator_base(const emplace_iterator_base&) = default;
+ emplace_iterator_base(emplace_iterator_base&&) noexcept = default;
+ emplace_iterator_base& operator=(emplace_iterator_base&) = default;
+ emplace_iterator_base& operator=(const emplace_iterator_base&) = default;
+ emplace_iterator_base& operator=(emplace_iterator_base&&) noexcept = default;
+
+ protected:
+ template <typename Args, std::size_t... I>
+ Derived& unpackAndEmplace(Args& args, std::index_sequence<I...>) {
+ this->emplace(get_emplace_arg<I>(args)...);
+ return static_cast<Derived&>(*this);
+ }
+ template <typename Args, std::size_t... I>
+ Derived& unpackAndEmplace(const Args& args, std::index_sequence<I...>) {
+ this->emplace(get_emplace_arg<I>(args)...);
+ return static_cast<Derived&>(*this);
+ }
+ template <typename Args, std::size_t... I>
+ Derived& unpackAndEmplace(Args&& args, std::index_sequence<I...>) {
+ this->emplace(get_emplace_arg<I>(std::move(args))...);
+ return static_cast<Derived&>(*this);
+ }
+};
+
+/**
+ * Partial specialization of emplace_iterator_base with implicit unpacking
+ * enabled.
+ *
+ * Uses inheritance rather than SFINAE. operator= requires a single argument,
+ * which makes it very tricky to use std::enable_if or similar.
+ */
+template <typename Derived, typename EmplaceImpl>
+class emplace_iterator_base<Derived, EmplaceImpl, true>
+ : public emplace_iterator_base<Derived, EmplaceImpl, false> {
+ private:
+ using Base = emplace_iterator_base<Derived, EmplaceImpl, false>;
+
+ public:
+ using Base::Base;
+ using Base::operator=;
+
+ /**
+ * Special output operator for arguments packed into a std::pair. Unpacks
+ * the pair and performs variadic call to container's emplace function.
+ */
+ template <typename... Args>
+ Derived& operator=(std::pair<Args...>& args) {
+ return this->unpackAndEmplace(args, std::index_sequence_for<Args...>{});
+ }
+ template <typename... Args>
+ Derived& operator=(const std::pair<Args...>& args) {
+ return this->unpackAndEmplace(args, std::index_sequence_for<Args...>{});
+ }
+ template <typename... Args>
+ Derived& operator=(std::pair<Args...>&& args) {
+ return this->unpackAndEmplace(
+ std::move(args), std::index_sequence_for<Args...>{});
+ }
+
+ /**
+ * Special output operator for arguments packed into a std::tuple. Unpacks
+ * the tuple and performs variadic call to container's emplace function.
+ */
+ template <typename... Args>
+ Derived& operator=(std::tuple<Args...>& args) {
+ return this->unpackAndEmplace(args, std::index_sequence_for<Args...>{});
+ }
+ template <typename... Args>
+ Derived& operator=(const std::tuple<Args...>& args) {
+ return this->unpackAndEmplace(args, std::index_sequence_for<Args...>{});
+ }
+ template <typename... Args>
+ Derived& operator=(std::tuple<Args...>&& args) {
+ return this->unpackAndEmplace(
+ std::move(args), std::index_sequence_for<Args...>{});
+ }
+
+ // We need all of these explicit defaults because the custom operator=
+ // overloads disable implicit generation of these functions.
+ emplace_iterator_base(const emplace_iterator_base&) = default;
+ emplace_iterator_base(emplace_iterator_base&&) noexcept = default;
+ emplace_iterator_base& operator=(emplace_iterator_base&) = default;
+ emplace_iterator_base& operator=(const emplace_iterator_base&) = default;
+ emplace_iterator_base& operator=(emplace_iterator_base&&) noexcept = default;
+};
+
+/**
+ * Concrete instantiation of emplace_iterator_base. All emplace iterator
+ * classes; folly::emplace_iterator, folly::hint_emplace_iterator,
+ * folly::front_emplace_iterator, and folly::back_emplace_iterator; are just
+ * type aliases of this class.
+ *
+ * It is not possible to alias emplace_iterator_base directly, because type
+ * aliases cannot be used for CRTP.
+ */
+template <
+ template <typename> class EmplaceImplT,
+ typename Container,
+ bool implicit_unpack>
+class emplace_iterator_impl
+ : public emplace_iterator_base<
+ emplace_iterator_impl<EmplaceImplT, Container, implicit_unpack>,
+ EmplaceImplT<Container>,
+ implicit_unpack> {
+ private:
+ using Base = emplace_iterator_base<
+ emplace_iterator_impl,
+ EmplaceImplT<Container>,
+ implicit_unpack>;
+
+ public:
+ using Base::Base;
+ using Base::operator=;
+
+ // We need all of these explicit defaults because the custom operator=
+ // overloads disable implicit generation of these functions.
+ emplace_iterator_impl(const emplace_iterator_impl&) = default;
+ emplace_iterator_impl(emplace_iterator_impl&&) noexcept = default;
+ emplace_iterator_impl& operator=(emplace_iterator_impl&) = default;
+ emplace_iterator_impl& operator=(const emplace_iterator_impl&) = default;
+ emplace_iterator_impl& operator=(emplace_iterator_impl&&) noexcept = default;
+};
+} // namespace detail
+
+/**
+ * Behaves just like std::insert_iterator except that it calls emplace()
+ * instead of insert(). Uses perfect forwarding.
+ */
+template <typename Container, bool implicit_unpack = true>
+using emplace_iterator =
+ detail::emplace_iterator_impl<detail::Emplace, Container, implicit_unpack>;
+
+/**
+ * Behaves just like std::insert_iterator except that it calls emplace_hint()
+ * instead of insert(). Uses perfect forwarding.
+ */
+template <typename Container, bool implicit_unpack = true>
+using hint_emplace_iterator = detail::
+ emplace_iterator_impl<detail::EmplaceHint, Container, implicit_unpack>;
+
+/**
+ * Behaves just like std::front_insert_iterator except that it calls
+ * emplace_front() instead of insert(). Uses perfect forwarding.
+ */
+template <typename Container, bool implicit_unpack = true>
+using front_emplace_iterator = detail::
+ emplace_iterator_impl<detail::EmplaceFront, Container, implicit_unpack>;
+
+/**
+ * Behaves just like std::back_insert_iterator except that it calls
+ * emplace_back() instead of insert(). Uses perfect forwarding.
+ */
+template <typename Container, bool implicit_unpack = true>
+using back_emplace_iterator = detail::
+ emplace_iterator_impl<detail::EmplaceBack, Container, implicit_unpack>;
+
+/**
+ * Convenience function to construct a folly::emplace_iterator, analogous to
+ * std::inserter().
+ *
+ * Setting implicit_unpack to false will disable implicit unpacking of
+ * single std::pair and std::tuple arguments to the iterator's operator=. That
+ * may be desirable in case of constructors that expect a std::pair or
+ * std::tuple argument.
+ */
+template <bool implicit_unpack = true, typename Container>
+emplace_iterator<Container, implicit_unpack> emplacer(
+ Container& c,
+ typename Container::iterator i) {
+ return emplace_iterator<Container, implicit_unpack>(c, std::move(i));
+}
+
+/**
+ * Convenience function to construct a folly::hint_emplace_iterator, analogous
+ * to std::inserter().
+ *
+ * Setting implicit_unpack to false will disable implicit unpacking of
+ * single std::pair and std::tuple arguments to the iterator's operator=. That
+ * may be desirable in case of constructors that expect a std::pair or
+ * std::tuple argument.
+ */
+template <bool implicit_unpack = true, typename Container>
+hint_emplace_iterator<Container, implicit_unpack> hint_emplacer(
+ Container& c,
+ typename Container::iterator i) {
+ return hint_emplace_iterator<Container, implicit_unpack>(c, std::move(i));
+}
+
+/**
+ * Convenience function to construct a folly::front_emplace_iterator, analogous
+ * to std::front_inserter().
+ *
+ * Setting implicit_unpack to false will disable implicit unpacking of
+ * single std::pair and std::tuple arguments to the iterator's operator=. That
+ * may be desirable in case of constructors that expect a std::pair or
+ * std::tuple argument.
+ */
+template <bool implicit_unpack = true, typename Container>
+front_emplace_iterator<Container, implicit_unpack> front_emplacer(
+ Container& c) {
+ return front_emplace_iterator<Container, implicit_unpack>(c);
+}
+
+/**
+ * Convenience function to construct a folly::back_emplace_iterator, analogous
+ * to std::back_inserter().
+ *
+ * Setting implicit_unpack to false will disable implicit unpacking of
+ * single std::pair and std::tuple arguments to the iterator's operator=. That
+ * may be desirable in case of constructors that expect a std::pair or
+ * std::tuple argument.
+ */
+template <bool implicit_unpack = true, typename Container>
+back_emplace_iterator<Container, implicit_unpack> back_emplacer(Container& c) {
+ return back_emplace_iterator<Container, implicit_unpack>(c);
+}
+}
--- /dev/null
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * 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
+ *
+ * http://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.
+ */
+
+/*
+ * folly::merge() is an implementation of std::merge with one additonal
+ * guarantee: if the input ranges overlap, the order that values *from the two
+ * different ranges* appear in the output is well defined (std::merge only
+ * guarantees relative ordering is maintained within a single input range).
+ * This semantic is very useful when the output container removes duplicates
+ * (such as std::map) to guarantee that elements from b override elements from
+ * a.
+ *
+ * ex. Let's say we have two vector<pair<int, int>> as input, and we are
+ * merging into a vector<pair<int, int>>. The comparator is returns true if the
+ * first argument has a lesser 'first' value in the pair.
+ *
+ * a = {{1, 1}, {2, 2}, {3, 3}};
+ * b = {{1, 2}, {2, 3}};
+ *
+ * folly::merge<...>(a.begin(), a.end(), b.begin(), b.end(), outputIter) is
+ * guaranteed to produce {{1, 1}, {1, 2}, {2, 2}, {2, 3}, {3, 3}}. That is,
+ * if comp(it_a, it_b) == comp(it_b, it_a) == false, we first insert the element
+ * from a.
+ */
+
+#pragma once
+
+#include <algorithm>
+
+namespace folly {
+
+template <class InputIt1, class InputIt2, class OutputIt, class Compare>
+OutputIt merge(InputIt1 first1, InputIt1 last1,
+ InputIt2 first2, InputIt2 last2,
+ OutputIt d_first, Compare comp) {
+ for (; first1 != last1; ++d_first) {
+ if (first2 == last2) {
+ return std::copy(first1, last1, d_first);
+ }
+ if (comp(*first2, *first1)) {
+ *d_first = *first2;
+ ++first2;
+ } else {
+ *d_first = *first1;
+ ++first1;
+ }
+ }
+ return std::copy(first2, last2, d_first);
+}
+
+template <class InputIt1, class InputIt2, class OutputIt>
+OutputIt merge(InputIt1 first1, InputIt1 last1,
+ InputIt2 first2, InputIt2 last2,
+ OutputIt d_first) {
+ for (; first1 != last1; ++d_first) {
+ if (first2 == last2) {
+ return std::copy(first1, last1, d_first);
+ }
+ if (*first2 < *first1) {
+ *d_first = *first2;
+ ++first2;
+ } else {
+ *d_first = *first1;
+ ++first1;
+ }
+ }
+ return std::copy(first2, last2, d_first);
+}
+
+}
--- /dev/null
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * 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
+ *
+ * http://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.
+ */
+
+#pragma once
+
+#include <cstdint>
+
+#include <glog/logging.h>
+
+namespace folly {
+
+/***
+ * SparseByteSet
+ *
+ * A special-purpose data structure representing an insert-only set of bytes.
+ * May have better performance than std::bitset<256>, depending on workload.
+ *
+ * Operations:
+ * - add(byte)
+ * - contains(byte)
+ *
+ * Performance:
+ * - The entire capacity of the set is inline; the set never allocates.
+ * - The constructor zeros only the first two bytes of the object.
+ * - add and contains both run in constant time w.r.t. the size of the set.
+ * Constant time - not amortized constant - and with small constant factor.
+ *
+ * This data structure is ideal for on-stack use.
+ *
+ * Aho, Hopcroft, and Ullman refer to this trick in "The Design and Analysis
+ * of Computer Algorithms" (1974), but the best description is here:
+ * http://research.swtch.com/sparse
+ * http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.7319
+ */
+class SparseByteSet {
+ public:
+ // There are this many possible values:
+ static constexpr uint16_t kCapacity = 256;
+
+ // No init of byte-arrays required!
+ SparseByteSet() : size_(0) { }
+
+ /***
+ * add(byte)
+ *
+ * O(1), non-amortized.
+ */
+ inline bool add(uint8_t i) {
+ bool r = !contains(i);
+ if (r) {
+ DCHECK_LT(size_, kCapacity);
+ dense_[size_] = i;
+ sparse_[i] = uint8_t(size_);
+ size_++;
+ }
+ return r;
+ }
+
+ /***
+ * contains(byte)
+ *
+ * O(1), non-amortized.
+ */
+ inline bool contains(uint8_t i) const {
+ return sparse_[i] < size_ && dense_[sparse_[i]] == i;
+ }
+
+ private:
+ uint16_t size_; // can't use uint8_t because it would overflow if all
+ // possible values were inserted.
+ uint8_t sparse_[kCapacity];
+ uint8_t dense_[kCapacity];
+};
+
+}
--- /dev/null
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * 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
+ *
+ * http://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 <array>
+#include <string>
+#include <vector>
+
+#include <folly/Range.h>
+#include <folly/container/Enumerate.h>
+#include <folly/portability/GTest.h>
+
+TEST(Enumerate, Basic) {
+ std::vector<std::string> v = {"abc", "a", "ab"};
+ size_t i = 0;
+ for (auto it : folly::enumerate(v)) {
+ EXPECT_EQ(it.index, i);
+ EXPECT_EQ(*it, v[i]);
+ EXPECT_EQ(it->size(), v[i].size());
+
+ // Test mutability.
+ std::string newValue = "x";
+ *it = newValue;
+ EXPECT_EQ(newValue, v[i]);
+
+ ++i;
+ }
+
+ EXPECT_EQ(i, v.size());
+}
+
+TEST(Enumerate, Temporary) {
+ std::vector<std::string> v = {"abc", "a", "ab"};
+ size_t i = 0;
+ for (auto it : folly::enumerate(decltype(v)(v))) { // Copy v.
+ EXPECT_EQ(it.index, i);
+ EXPECT_EQ(*it, v[i]);
+ EXPECT_EQ(it->size(), v[i].size());
+ ++i;
+ }
+
+ EXPECT_EQ(i, v.size());
+};
+
+namespace {
+
+template <class T>
+struct IsConstReference {
+ constexpr static bool value = false;
+};
+template <class T>
+struct IsConstReference<const T&> {
+ constexpr static bool value = true;
+};
+
+} // namespace
+
+TEST(Enumerate, BasicConstArg) {
+ const std::vector<std::string> v = {"abc", "a", "ab"};
+ size_t i = 0;
+ for (auto it : folly::enumerate(v)) {
+ static_assert(
+ IsConstReference<decltype(*it)>::value, "Enumerating a const vector");
+ EXPECT_EQ(it.index, i);
+ EXPECT_EQ(*it, v[i]);
+ EXPECT_EQ(it->size(), v[i].size());
+ ++i;
+ }
+
+ EXPECT_EQ(i, v.size());
+}
+
+TEST(Enumerate, BasicConstEnumerate) {
+ std::vector<std::string> v = {"abc", "a", "ab"};
+ size_t i = 0;
+ for (const auto it : folly::enumerate(v)) {
+ static_assert(IsConstReference<decltype(*it)>::value, "Const enumeration");
+ EXPECT_EQ(it.index, i);
+ EXPECT_EQ(*it, v[i]);
+ EXPECT_EQ(it->size(), v[i].size());
+ ++i;
+ }
+
+ EXPECT_EQ(i, v.size());
+}
+
+TEST(Enumerate, TemporaryConstEnumerate) {
+ std::vector<std::string> v = {"abc", "a", "ab"};
+ size_t i = 0;
+ for (const auto it : folly::enumerate(decltype(v)(v))) { // Copy v.
+ static_assert(IsConstReference<decltype(*it)>::value, "Const enumeration");
+ EXPECT_EQ(it.index, i);
+ EXPECT_EQ(*it, v[i]);
+ EXPECT_EQ(it->size(), v[i].size());
+ ++i;
+ }
+
+ EXPECT_EQ(i, v.size());
+}
+
+TEST(Enumerate, RangeSupport) {
+ std::vector<std::string> v = {"abc", "a", "ab"};
+ size_t i = 0;
+ for (const auto it : folly::enumerate(folly::range(v))) {
+ EXPECT_EQ(it.index, i);
+ EXPECT_EQ(*it, v[i]);
+ EXPECT_EQ(it->size(), v[i].size());
+ ++i;
+ }
+
+ EXPECT_EQ(i, v.size());
+}
+
+TEST(Enumerate, EmptyRange) {
+ std::vector<std::string> v;
+ for (auto it : folly::enumerate(v)) {
+ (void)it; // Silence warnings.
+ ADD_FAILURE();
+ }
+}
+
+class CStringRange {
+ const char* cstr;
+
+ public:
+ struct Sentinel {};
+
+ explicit CStringRange(const char* cstr) : cstr(cstr) {}
+
+ const char* begin() const {
+ return cstr;
+ }
+ Sentinel end() const {
+ return Sentinel{};
+ }
+};
+
+bool operator==(const char* c, CStringRange::Sentinel) {
+ return *c == 0;
+}
+
+TEST(Enumerate, Cpp17Support) {
+ std::array<char, 5> test = {"test"};
+ // Can't use range based for loop until C++17, so test manually
+ // Equivalent to:
+ // for (const auto it : folly::enumerate(CStringRange{test.data()})) { ... }
+ {
+ auto&& enumerate = folly::enumerate(CStringRange{test.data()});
+ auto begin = enumerate.begin();
+ auto end = enumerate.end();
+ for (; begin != end; ++begin) {
+ const auto it = *begin;
+
+ ASSERT_LT(it.index, test.size());
+ EXPECT_EQ(*it, test[it.index]);
+ }
+ }
+}
--- /dev/null
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * 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
+ *
+ * http://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 <set>
+
+#include <folly/container/EvictingCacheMap.h>
+#include <folly/portability/GTest.h>
+
+using namespace folly;
+
+TEST(EvictingCacheMap, SanityTest) {
+ EvictingCacheMap<int, int> map(0);
+
+ EXPECT_EQ(0, map.size());
+ EXPECT_TRUE(map.empty());
+ EXPECT_FALSE(map.exists(1));
+ map.set(1, 1);
+ EXPECT_EQ(1, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_EQ(1, map.get(1));
+ EXPECT_TRUE(map.exists(1));
+ map.set(1, 2);
+ EXPECT_EQ(1, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_EQ(2, map.get(1));
+ EXPECT_TRUE(map.exists(1));
+ map.erase(1);
+ EXPECT_EQ(0, map.size());
+ EXPECT_TRUE(map.empty());
+ EXPECT_FALSE(map.exists(1));
+
+ EXPECT_EQ(0, map.size());
+ EXPECT_TRUE(map.empty());
+ EXPECT_FALSE(map.exists(1));
+ map.set(1, 1);
+ EXPECT_EQ(1, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_EQ(1, map.get(1));
+ EXPECT_TRUE(map.exists(1));
+ map.set(1, 2);
+ EXPECT_EQ(1, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_EQ(2, map.get(1));
+ EXPECT_TRUE(map.exists(1));
+
+ EXPECT_FALSE(map.exists(2));
+ map.set(2, 1);
+ EXPECT_TRUE(map.exists(2));
+ EXPECT_EQ(2, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_EQ(1, map.get(2));
+ map.set(2, 2);
+ EXPECT_EQ(2, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_EQ(2, map.get(2));
+ EXPECT_TRUE(map.exists(2));
+ map.erase(2);
+ EXPECT_EQ(1, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_FALSE(map.exists(2));
+ map.erase(1);
+ EXPECT_EQ(0, map.size());
+ EXPECT_TRUE(map.empty());
+ EXPECT_FALSE(map.exists(1));
+}
+
+
+TEST(EvictingCacheMap, PruneTest) {
+ EvictingCacheMap<int, int> map(0);
+ EXPECT_EQ(0, map.size());
+ EXPECT_TRUE(map.empty());
+ for (int i = 0; i < 100; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+
+ for (int i = 0; i < 100; i++) {
+ map.set(i, i);
+ EXPECT_EQ(i + 1, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_TRUE(map.exists(i));
+ EXPECT_EQ(i, map.get(i));
+ }
+
+ map.prune(1000000);
+ EXPECT_EQ(0, map.size());
+ EXPECT_TRUE(map.empty());
+ for (int i = 0; i < 100; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+
+ for (int i = 0; i < 100; i++) {
+ map.set(i, i);
+ EXPECT_EQ(i + 1, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_TRUE(map.exists(i));
+ EXPECT_EQ(i, map.get(i));
+ }
+
+ map.prune(100);
+ EXPECT_EQ(0, map.size());
+ EXPECT_TRUE(map.empty());
+ for (int i = 0; i < 100; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+
+ for (int i = 0; i < 100; i++) {
+ map.set(i, i);
+ EXPECT_EQ(i + 1, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_TRUE(map.exists(i));
+ EXPECT_EQ(i, map.get(i));
+ }
+
+ map.prune(99);
+ EXPECT_EQ(1, map.size());
+ EXPECT_FALSE(map.empty());
+ for (int i = 0; i < 99; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+ EXPECT_TRUE(map.exists(99));
+ EXPECT_EQ(99, map.get(99));
+
+ map.prune(100);
+ EXPECT_EQ(0, map.size());
+ EXPECT_TRUE(map.empty());
+ for (int i = 0; i < 100; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+
+ for (int i = 0; i < 100; i++) {
+ map.set(i, i);
+ EXPECT_EQ(i + 1, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_TRUE(map.exists(i));
+ EXPECT_EQ(i, map.get(i));
+ }
+
+ map.prune(90);
+ EXPECT_EQ(10, map.size());
+ EXPECT_FALSE(map.empty());
+ for (int i = 0; i < 90; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+ for (int i = 90; i < 100; i++) {
+ EXPECT_TRUE(map.exists(i));
+ EXPECT_EQ(i, map.get(i));
+ }
+}
+
+TEST(EvictingCacheMap, PruneHookTest) {
+ EvictingCacheMap<int, int> map(0);
+ EXPECT_EQ(0, map.size());
+ EXPECT_TRUE(map.empty());
+ for (int i = 0; i < 100; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+
+ int sum = 0;
+ auto pruneCb = [&](int&& k, int&& v) {
+ EXPECT_EQ(k, v);
+ sum += k;
+ };
+
+ map.setPruneHook(pruneCb);
+
+ for (int i = 0; i < 100; i++) {
+ map.set(i, i);
+ EXPECT_EQ(i + 1, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_TRUE(map.exists(i));
+ EXPECT_EQ(i, map.get(i));
+ }
+
+ map.prune(1000000);
+ EXPECT_EQ(0, map.size());
+ EXPECT_TRUE(map.empty());
+ for (int i = 0; i < 100; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+ EXPECT_EQ((99 * 100) / 2, sum);
+ sum = 0;
+
+ for (int i = 0; i < 100; i++) {
+ map.set(i, i);
+ EXPECT_EQ(i + 1, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_TRUE(map.exists(i));
+ EXPECT_EQ(i, map.get(i));
+ }
+
+ map.prune(100);
+ EXPECT_EQ(0, map.size());
+ EXPECT_TRUE(map.empty());
+ for (int i = 0; i < 100; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+ EXPECT_EQ((99 * 100) / 2, sum);
+ sum = 0;
+
+ for (int i = 0; i < 100; i++) {
+ map.set(i, i);
+ EXPECT_EQ(i + 1, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_TRUE(map.exists(i));
+ EXPECT_EQ(i, map.get(i));
+ }
+
+ map.prune(99);
+ EXPECT_EQ(1, map.size());
+ EXPECT_FALSE(map.empty());
+ for (int i = 0; i < 99; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+ EXPECT_TRUE(map.exists(99));
+ EXPECT_EQ(99, map.get(99));
+
+ EXPECT_EQ((98 * 99) / 2, sum);
+ sum = 0;
+
+ map.prune(100);
+ EXPECT_EQ(0, map.size());
+ EXPECT_TRUE(map.empty());
+ for (int i = 0; i < 100; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+
+ EXPECT_EQ(99, sum);
+ sum = 0;
+
+ for (int i = 0; i < 100; i++) {
+ map.set(i, i);
+ EXPECT_EQ(i + 1, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_TRUE(map.exists(i));
+ EXPECT_EQ(i, map.get(i));
+ }
+
+ map.prune(90);
+ EXPECT_EQ(10, map.size());
+ EXPECT_FALSE(map.empty());
+ for (int i = 0; i < 90; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+ for (int i = 90; i < 100; i++) {
+ EXPECT_TRUE(map.exists(i));
+ EXPECT_EQ(i, map.get(i));
+ }
+ EXPECT_EQ((89 * 90) / 2, sum);
+ sum = 0;
+}
+
+TEST(EvictingCacheMap, SetMaxSize) {
+ EvictingCacheMap<int, int> map(100, 20);
+ for (int i = 0; i < 90; i++) {
+ map.set(i, i);
+ EXPECT_TRUE(map.exists(i));
+ }
+
+ EXPECT_EQ(90, map.size());
+ map.setMaxSize(50);
+ EXPECT_EQ(map.size(), 50);
+
+ for (int i = 0; i < 90; i++) {
+ map.set(i, i);
+ EXPECT_TRUE(map.exists(i));
+ }
+ EXPECT_EQ(40, map.size());
+ map.setMaxSize(0);
+ EXPECT_EQ(40, map.size());
+ map.setMaxSize(10);
+ EXPECT_EQ(10, map.size());
+}
+
+TEST(EvictingCacheMap, SetClearSize) {
+ EvictingCacheMap<int, int> map(100, 20);
+ for (int i = 0; i < 90; i++) {
+ map.set(i, i);
+ EXPECT_TRUE(map.exists(i));
+ }
+
+ EXPECT_EQ(90, map.size());
+ map.setClearSize(40);
+ map.setMaxSize(50);
+ EXPECT_EQ(map.size(), 50);
+
+ for (int i = 0; i < 90; i++) {
+ map.set(i, i);
+ EXPECT_TRUE(map.exists(i));
+ }
+ EXPECT_EQ(20, map.size());
+ map.setMaxSize(0);
+ EXPECT_EQ(20, map.size());
+ map.setMaxSize(10);
+ EXPECT_EQ(0, map.size());
+}
+
+TEST(EvictingCacheMap, DestructorInvocationTest) {
+ struct SumInt {
+ SumInt(int val, int* ref) : val(val), ref(ref) { }
+ ~SumInt() {
+ *ref += val;
+ }
+ int val;
+ int* ref;
+ };
+
+ int sum;
+ EvictingCacheMap<int, SumInt> map(0);
+
+ EXPECT_EQ(0, map.size());
+ EXPECT_TRUE(map.empty());
+ for (int i = 0; i < 100; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+
+ for (int i = 0; i < 100; i++) {
+ map.set(i, SumInt(i, &sum));
+ EXPECT_EQ(i + 1, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_TRUE(map.exists(i));
+ EXPECT_EQ(i, map.get(i).val);
+ }
+
+ sum = 0;
+ map.prune(1000000);
+ EXPECT_EQ(0, map.size());
+ EXPECT_TRUE(map.empty());
+ for (int i = 0; i < 100; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+ EXPECT_EQ((99 * 100) / 2, sum);
+
+ for (int i = 0; i < 100; i++) {
+ map.set(i, SumInt(i, &sum));
+ EXPECT_EQ(i + 1, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_TRUE(map.exists(i));
+ EXPECT_EQ(i, map.get(i).val);
+ }
+
+ sum = 0;
+ map.prune(100);
+ EXPECT_EQ(0, map.size());
+ EXPECT_TRUE(map.empty());
+ for (int i = 0; i < 100; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+ EXPECT_EQ((99 * 100) / 2, sum);
+
+ for (int i = 0; i < 100; i++) {
+ map.set(i, SumInt(i, &sum));
+ EXPECT_EQ(i + 1, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_TRUE(map.exists(i));
+ EXPECT_EQ(i, map.get(i).val);
+ }
+
+ sum = 0;
+ map.prune(99);
+ EXPECT_EQ(1, map.size());
+ EXPECT_FALSE(map.empty());
+ for (int i = 0; i < 99; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+ EXPECT_TRUE(map.exists(99));
+ EXPECT_EQ(99, map.get(99).val);
+
+ EXPECT_EQ((98 * 99) / 2, sum);
+
+ sum = 0;
+ map.prune(100);
+ EXPECT_EQ(0, map.size());
+ EXPECT_TRUE(map.empty());
+ for (int i = 0; i < 100; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+
+ EXPECT_EQ(99, sum);
+ for (int i = 0; i < 100; i++) {
+ map.set(i, SumInt(i, &sum));
+ EXPECT_EQ(i + 1, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_TRUE(map.exists(i));
+ EXPECT_EQ(i, map.get(i).val);
+ }
+
+ sum = 0;
+ map.prune(90);
+ EXPECT_EQ(10, map.size());
+ EXPECT_FALSE(map.empty());
+ for (int i = 0; i < 90; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+ for (int i = 90; i < 100; i++) {
+ EXPECT_TRUE(map.exists(i));
+ EXPECT_EQ(i, map.get(i).val);
+ }
+ EXPECT_EQ((89 * 90) / 2, sum);
+ sum = 0;
+}
+
+TEST(EvictingCacheMap, LruSanityTest) {
+ EvictingCacheMap<int, int> map(10);
+ EXPECT_EQ(0, map.size());
+ EXPECT_TRUE(map.empty());
+ for (int i = 0; i < 100; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+
+ for (int i = 0; i < 100; i++) {
+ map.set(i, i);
+ EXPECT_GE(10, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_TRUE(map.exists(i));
+ EXPECT_EQ(i, map.get(i));
+ }
+
+ EXPECT_EQ(10, map.size());
+ EXPECT_FALSE(map.empty());
+ for (int i = 0; i < 90; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+ for (int i = 90; i < 100; i++) {
+ EXPECT_TRUE(map.exists(i));
+ }
+}
+
+TEST(EvictingCacheMap, LruPromotionTest) {
+ EvictingCacheMap<int, int> map(10);
+ EXPECT_EQ(0, map.size());
+ EXPECT_TRUE(map.empty());
+ for (int i = 0; i < 100; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+
+ for (int i = 0; i < 100; i++) {
+ map.set(i, i);
+ EXPECT_GE(10, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_TRUE(map.exists(i));
+ EXPECT_EQ(i, map.get(i));
+ for (int j = 0; j < std::min(i + 1, 9); j++) {
+ EXPECT_TRUE(map.exists(j));
+ EXPECT_EQ(j, map.get(j));
+ }
+ }
+
+ EXPECT_EQ(10, map.size());
+ EXPECT_FALSE(map.empty());
+ for (int i = 0; i < 9; i++) {
+ EXPECT_TRUE(map.exists(i));
+ }
+ EXPECT_TRUE(map.exists(99));
+ for (int i = 10; i < 99; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+}
+
+TEST(EvictingCacheMap, LruNoPromotionTest) {
+ EvictingCacheMap<int, int> map(10);
+ EXPECT_EQ(0, map.size());
+ EXPECT_TRUE(map.empty());
+ for (int i = 0; i < 100; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+
+ for (int i = 0; i < 100; i++) {
+ map.set(i, i);
+ EXPECT_GE(10, map.size());
+ EXPECT_FALSE(map.empty());
+ EXPECT_TRUE(map.exists(i));
+ EXPECT_EQ(i, map.get(i));
+ for (int j = 0; j < std::min(i + 1, 9); j++) {
+ if (map.exists(j)) {
+ EXPECT_EQ(j, map.getWithoutPromotion(j));
+ }
+ }
+ }
+
+ EXPECT_EQ(10, map.size());
+ EXPECT_FALSE(map.empty());
+ for (int i = 0; i < 90; i++) {
+ EXPECT_FALSE(map.exists(i));
+ }
+ for (int i = 90; i < 100; i++) {
+ EXPECT_TRUE(map.exists(i));
+ }
+}
+
+TEST(EvictingCacheMap, IteratorSanityTest) {
+ const int nItems = 1000;
+ EvictingCacheMap<int, int> map(nItems);
+ EXPECT_TRUE(map.begin() == map.end());
+ for (int i = 0; i < nItems; i++) {
+ EXPECT_FALSE(map.exists(i));
+ map.set(i, i * 2);
+ EXPECT_TRUE(map.exists(i));
+ EXPECT_EQ(i * 2, map.get(i));
+ }
+
+ std::set<int> seen;
+ for (auto& it : map) {
+ EXPECT_EQ(0, seen.count(it.first));
+ seen.insert(it.first);
+ EXPECT_EQ(it.first * 2, it.second);
+ }
+ EXPECT_EQ(nItems, seen.size());
+}
+
+TEST(EvictingCacheMap, FindTest) {
+ const int nItems = 1000;
+ EvictingCacheMap<int, int> map(nItems);
+ for (int i = 0; i < nItems; i++) {
+ map.set(i * 2, i * 2);
+ EXPECT_TRUE(map.exists(i * 2));
+ EXPECT_EQ(i * 2, map.get(i * 2));
+ }
+ for (int i = 0; i < nItems * 2; i++) {
+ if (i % 2 == 0) {
+ auto it = map.find(i);
+ EXPECT_FALSE(it == map.end());
+ EXPECT_EQ(i, it->first);
+ EXPECT_EQ(i, it->second);
+ } else {
+ EXPECT_TRUE( map.find(i) == map.end());
+ }
+ }
+ for (int i = nItems * 2 - 1; i >= 0; i--) {
+ if (i % 2 == 0) {
+ auto it = map.find(i);
+ EXPECT_FALSE(it == map.end());
+ EXPECT_EQ(i, it->first);
+ EXPECT_EQ(i, it->second);
+ } else {
+ EXPECT_TRUE(map.find(i) == map.end());
+ }
+ }
+ EXPECT_EQ(0, map.begin()->first);
+}
+
+TEST(EvictingCacheMap, FindWithoutPromotionTest) {
+ const int nItems = 1000;
+ EvictingCacheMap<int, int> map(nItems);
+ for (int i = 0; i < nItems; i++) {
+ map.set(i * 2, i * 2);
+ EXPECT_TRUE(map.exists(i * 2));
+ EXPECT_EQ(i * 2, map.get(i * 2));
+ }
+ for (int i = nItems * 2 - 1; i >= 0; i--) {
+ if (i % 2 == 0) {
+ auto it = map.findWithoutPromotion(i);
+ EXPECT_FALSE(it == map.end());
+ EXPECT_EQ(i, it->first);
+ EXPECT_EQ(i, it->second);
+ } else {
+ EXPECT_TRUE(map.findWithoutPromotion(i) == map.end());
+ }
+ }
+ EXPECT_EQ((nItems - 1) * 2, map.begin()->first);
+}
+
+TEST(EvictingCacheMap, IteratorOrderingTest) {
+ const int nItems = 1000;
+ EvictingCacheMap<int, int> map(nItems);
+ for (int i = 0; i < nItems; i++) {
+ map.set(i, i);
+ EXPECT_TRUE(map.exists(i));
+ EXPECT_EQ(i, map.get(i));
+ }
+
+ int expected = nItems - 1;
+ for (auto it = map.begin(); it != map.end(); ++it) {
+ EXPECT_EQ(expected, it->first);
+ expected--;
+ }
+
+ expected = 0;
+ for (auto it = map.rbegin(); it != map.rend(); ++it) {
+ EXPECT_EQ(expected, it->first);
+ expected++;
+ }
+
+ {
+ auto it = map.end();
+ expected = 0;
+ EXPECT_TRUE(it != map.begin());
+ do {
+ --it;
+ EXPECT_EQ(expected, it->first);
+ expected++;
+ } while (it != map.begin());
+ EXPECT_EQ(nItems, expected);
+ }
+
+ {
+ auto it = map.rend();
+ expected = nItems - 1;
+ do {
+ --it;
+ EXPECT_EQ(expected, it->first);
+ expected--;
+ } while (it != map.rbegin());
+ EXPECT_EQ(-1, expected);
+ }
+}
+
+TEST(EvictingCacheMap, MoveTest) {
+ const int nItems = 1000;
+ EvictingCacheMap<int, int> map(nItems);
+ for (int i = 0; i < nItems; i++) {
+ map.set(i, i);
+ EXPECT_TRUE(map.exists(i));
+ EXPECT_EQ(i, map.get(i));
+ }
+
+ EvictingCacheMap<int, int> map2 = std::move(map);
+ EXPECT_TRUE(map.empty());
+ for (int i = 0; i < nItems; i++) {
+ EXPECT_TRUE(map2.exists(i));
+ EXPECT_EQ(i, map2.get(i));
+ }
+}
--- /dev/null
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * 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
+ *
+ * http://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 <folly/container/Foreach.h>
+
+#include <folly/Benchmark.h>
+#include <folly/portability/GTest.h>
+
+#include <map>
+
+using namespace folly;
+using namespace folly::detail;
+
+// Benchmarks:
+// 1. Benchmark iterating through the man with FOR_EACH, and also assign
+// iter->first and iter->second to local vars inside the FOR_EACH loop.
+// 2. Benchmark iterating through the man with FOR_EACH, but use iter->first and
+// iter->second as is, without assigning to local variables.
+// 3. Use FOR_EACH_KV loop to iterate through the map.
+
+std::map<int, std::string> bmMap; // For use in benchmarks below.
+std::vector<int> vec_one;
+std::vector<int> vec_two;
+
+void setupBenchmark(size_t iters) {
+ bmMap.clear();
+ for (size_t i = 0; i < iters; ++i) {
+ bmMap[i] = "teststring";
+ }
+
+ vec_one.clear();
+ vec_two.clear();
+ vec_one.resize(iters);
+ vec_two.resize(iters);
+}
+
+BENCHMARK(ForEachFunctionNoAssign, iters) {
+ BenchmarkSuspender suspender;
+
+ int sumKeys = 0;
+ std::string sumValues;
+ setupBenchmark(iters);
+
+ suspender.dismissing([&]() {
+ folly::for_each(bmMap, [&](auto& key_val_pair) {
+ sumKeys += key_val_pair.first;
+ sumValues += key_val_pair.second;
+ });
+ doNotOptimizeAway(sumKeys);
+ });
+}
+
+BENCHMARK(StdForEachFunctionNoAssign, iters) {
+ BenchmarkSuspender suspender;
+
+ int sumKeys = 0;
+ std::string sumValues;
+ setupBenchmark(iters);
+
+ suspender.dismissing([&]() {
+ std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
+ sumKeys += key_val_pair.first;
+ sumValues += key_val_pair.second;
+ });
+ doNotOptimizeAway(sumKeys);
+ });
+}
+
+BENCHMARK(RangeBasedForLoopNoAssign, iters) {
+ BenchmarkSuspender suspender;
+ int sumKeys = 0;
+ std::string sumValues;
+ setupBenchmark(iters);
+
+ suspender.dismissing([&]() {
+ for (auto& key_val_pair : bmMap) {
+ sumKeys += key_val_pair.first;
+ sumValues += key_val_pair.second;
+ }
+ doNotOptimizeAway(sumKeys);
+ });
+}
+
+BENCHMARK(ManualLoopNoAssign, iters) {
+ BenchmarkSuspender suspender;
+
+ int sumKeys = 0;
+ std::string sumValues;
+ setupBenchmark(iters);
+
+ suspender.dismissing([&]() {
+ for (auto iter = bmMap.begin(); iter != bmMap.end(); ++iter) {
+ sumKeys += iter->first;
+ sumValues += iter->second;
+ }
+ doNotOptimizeAway(sumKeys);
+ });
+}
+
+BENCHMARK(ForEachFunctionAssign, iters) {
+ BenchmarkSuspender suspender;
+
+ int sumKeys = 0;
+ std::string sumValues;
+ setupBenchmark(iters);
+
+ suspender.dismissing([&]() {
+ folly::for_each(bmMap, [&](auto& key_val_pair) {
+ const int k = key_val_pair.first;
+ const std::string v = key_val_pair.second;
+ sumKeys += k;
+ sumValues += v;
+ });
+ });
+}
+
+BENCHMARK(StdForEachFunctionAssign, iters) {
+ BenchmarkSuspender suspender;
+
+ int sumKeys = 0;
+ std::string sumValues;
+ setupBenchmark(iters);
+
+ suspender.dismissing([&]() {
+ std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
+ const int k = key_val_pair.first;
+ const std::string v = key_val_pair.second;
+ sumKeys += k;
+ sumValues += v;
+ });
+ });
+}
+
+BENCHMARK(RangeBasedForLoopAssign, iters) {
+ BenchmarkSuspender suspender;
+
+ int sumKeys = 0;
+ std::string sumValues;
+ setupBenchmark(iters);
+
+ suspender.dismissing([&]() {
+ for (auto& key_val_pair : bmMap) {
+ const int k = key_val_pair.first;
+ const std::string v = key_val_pair.second;
+ sumKeys += k;
+ sumValues += v;
+ }
+ });
+}
+
+BENCHMARK(ManualLoopAssign, iters) {
+ BenchmarkSuspender suspender;
+
+ int sumKeys = 0;
+ std::string sumValues;
+ setupBenchmark(iters);
+
+ suspender.dismissing([&]() {
+ for (auto iter = bmMap.begin(); iter != bmMap.end(); ++iter) {
+ const int k = iter->first;
+ const std::string v = iter->second;
+ sumKeys += k;
+ sumValues += v;
+ }
+ });
+}
+
+BENCHMARK(ForEachFunctionNoAssignWithIndexManipulation, iters) {
+ BenchmarkSuspender suspender;
+
+ int sumKeys = 0;
+ std::string sumValues;
+ setupBenchmark(iters);
+
+ suspender.dismissing([&]() {
+ folly::for_each(bmMap, [&](auto& key_val_pair, auto index) {
+ sumKeys += key_val_pair.first;
+ sumValues += key_val_pair.second;
+ sumValues += index;
+ });
+ });
+}
+
+BENCHMARK(StdForEachFunctionNoAssignWithIndexManipulation, iters) {
+ BenchmarkSuspender suspender;
+
+ int sumKeys = 0;
+ std::string sumValues;
+ setupBenchmark(iters);
+
+ suspender.dismissing([&]() {
+ auto index = std::size_t{0};
+ std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
+ sumKeys += key_val_pair.first;
+ sumValues += key_val_pair.second;
+ sumValues += index;
+ ++index;
+ });
+ });
+}
+
+BENCHMARK(RangeBasedForLoopNoAssignWithIndexManipulation, iters) {
+ BenchmarkSuspender suspender;
+
+ int sumKeys = 0;
+ std::string sumValues;
+ setupBenchmark(iters);
+
+ suspender.dismissing([&]() {
+ auto index = std::size_t{0};
+ for (auto& key_val_pair : bmMap) {
+ sumKeys += key_val_pair.first;
+ sumValues += key_val_pair.second;
+ sumValues += index;
+ }
+ });
+}
+
+BENCHMARK(ForEachFunctionFetch, iters) {
+ BenchmarkSuspender suspender;
+ setupBenchmark(iters);
+
+ suspender.dismissing([&]() {
+ folly::for_each(bmMap, [&](auto& key_val_pair, auto index) {
+ folly::fetch(vec_one, index) = key_val_pair.first;
+ });
+ });
+}
+
+BENCHMARK(StdForEachFunctionFetch, iters) {
+ BenchmarkSuspender suspender;
+ setupBenchmark(iters);
+
+ suspender.dismissing([&]() {
+ auto index = std::size_t{0};
+ std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
+ *(vec_one.begin() + index++) = key_val_pair.first;
+ });
+ });
+}
+
+BENCHMARK(ForLoopFetch, iters) {
+ BenchmarkSuspender suspender;
+ setupBenchmark(iters);
+
+ suspender.dismissing([&]() {
+ auto index = std::size_t{0};
+ for (auto& key_val_pair : bmMap) {
+ *(vec_one.begin() + index++) = key_val_pair.first;
+ }
+ });
+}
+
+BENCHMARK(ForEachKVNoMacroAssign, iters) {
+ int sumKeys = 0;
+ std::string sumValues;
+
+ BENCHMARK_SUSPEND { setupBenchmark(iters); }
+
+ FOR_EACH(iter, bmMap) {
+ const int k = iter->first;
+ const std::string v = iter->second;
+ sumKeys += k;
+ sumValues += v;
+ }
+}
+
+BENCHMARK(ForEachKVNoMacroNoAssign, iters) {
+ int sumKeys = 0;
+ std::string sumValues;
+
+ BENCHMARK_SUSPEND { setupBenchmark(iters); }
+
+ FOR_EACH(iter, bmMap) {
+ sumKeys += iter->first;
+ sumValues += iter->second;
+ }
+}
+
+BENCHMARK(ForEachKVMacro, iters) {
+ int sumKeys = 0;
+ std::string sumValues;
+
+ BENCHMARK_SUSPEND { setupBenchmark(iters); }
+
+ FOR_EACH_KV(k, v, bmMap) {
+ sumKeys += k;
+ sumValues += v;
+ }
+}
+
+BENCHMARK(ForEachManual, iters) {
+ int sum = 1;
+ for (size_t i = 1; i < iters; ++i) {
+ sum *= i;
+ }
+ doNotOptimizeAway(sum);
+}
+
+BENCHMARK(ForEachRange, iters) {
+ int sum = 1;
+ FOR_EACH_RANGE(i, 1, iters) { sum *= i; }
+ doNotOptimizeAway(sum);
+}
+
+BENCHMARK(ForEachDescendingManual, iters) {
+ int sum = 1;
+ for (size_t i = iters; i-- > 1;) {
+ sum *= i;
+ }
+ doNotOptimizeAway(sum);
+}
+
+BENCHMARK(ForEachRangeR, iters) {
+ int sum = 1;
+ FOR_EACH_RANGE_R(i, 1U, iters) { sum *= i; }
+ doNotOptimizeAway(sum);
+}
+
+int main(int argc, char** argv) {
+ testing::InitGoogleTest(&argc, argv);
+ gflags::ParseCommandLineFlags(&argc, &argv, true);
+ auto r = RUN_ALL_TESTS();
+ if (r) {
+ return r;
+ }
+ runBenchmarks();
+ return 0;
+}
--- /dev/null
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * 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
+ *
+ * http://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 <folly/container/Foreach.h>
+
+#include <array>
+#include <initializer_list>
+#include <iterator>
+#include <list>
+#include <map>
+#include <string>
+#include <tuple>
+#include <vector>
+
+#include <folly/portability/GTest.h>
+
+using namespace folly;
+using namespace folly::detail;
+
+namespace folly {
+namespace test {
+
+class TestRValueConstruct {
+ public:
+ TestRValueConstruct() = default;
+ TestRValueConstruct(TestRValueConstruct&&) noexcept {
+ this->constructed_from_rvalue = true;
+ }
+ TestRValueConstruct(const TestRValueConstruct&) {
+ this->constructed_from_rvalue = false;
+ }
+ TestRValueConstruct& operator=(const TestRValueConstruct&) = delete;
+ TestRValueConstruct& operator=(TestRValueConstruct&&) = delete;
+
+ bool constructed_from_rvalue{false};
+};
+
+class TestAdlIterable {
+ public:
+ std::vector<int> vec{0, 1, 2, 3};
+};
+
+auto begin(TestAdlIterable& instance) {
+ return instance.vec.begin();
+}
+auto begin(const TestAdlIterable& instance) {
+ return instance.vec.begin();
+}
+auto end(TestAdlIterable& instance) {
+ return instance.vec.end();
+}
+auto end(const TestAdlIterable& instance) {
+ return instance.vec.end();
+}
+
+class TestBothIndexingAndIter {
+ public:
+ class Iterator {
+ public:
+ using difference_type = std::size_t;
+ using value_type = int;
+ using pointer = int*;
+ using reference = int&;
+ using iterator_category = std::random_access_iterator_tag;
+ int& operator*() {
+ return this->val;
+ }
+ Iterator operator+(int) {
+ return *this;
+ }
+ explicit Iterator(int& val_in) : val{val_in} {}
+ int& val;
+ };
+ auto begin() {
+ this->called_begin = true;
+ return Iterator{val};
+ }
+ auto end() {
+ return Iterator{val};
+ }
+ int& operator[](int) {
+ return this->val;
+ }
+
+ int val{0};
+ bool called_begin = false;
+};
+} // namespace test
+} // namespace folly
+
+TEST(Foreach, ForEachFunctionBasic) {
+ auto range = std::make_tuple(1, 2, 3);
+ auto result_range = std::vector<int>{};
+ auto correct_result_range = std::vector<int>{1, 2, 3};
+
+ folly::for_each(range, [&](auto ele) { result_range.push_back(ele); });
+
+ EXPECT_TRUE(std::equal(
+ result_range.begin(), result_range.end(), correct_result_range.begin()));
+}
+
+TEST(Foreach, ForEachFunctionBasicRuntimeOneArg) {
+ auto range = std::vector<int>{1, 2, 3};
+ auto current = 0;
+ folly::for_each(range, [&](auto ele) {
+ if (current == 0) {
+ EXPECT_EQ(ele, 1);
+ } else if (current == 1) {
+ EXPECT_EQ(ele, 2);
+ } else {
+ EXPECT_EQ(ele, 3);
+ }
+ ++current;
+ });
+}
+
+TEST(Foreach, ForEachFunctionBasicRuntimeTwoArg) {
+ auto range = std::vector<int>{1, 2, 3};
+ folly::for_each(range, [](auto ele, auto index) {
+ EXPECT_TRUE(index < 3);
+ if (index == 0) {
+ EXPECT_EQ(ele, 1);
+ } else if (index == 1) {
+ EXPECT_EQ(ele, 2);
+ } else if (index == 2) {
+ EXPECT_EQ(ele, 3);
+ }
+ });
+}
+
+TEST(Foreach, ForEachFunctionBasicRuntimeThreeArg) {
+ auto range = std::list<int>{1, 2, 3};
+ auto result_range = std::list<int>{1, 3};
+ folly::for_each(range, [&](auto ele, auto, auto iter) {
+ if (ele == 2) {
+ range.erase(iter);
+ }
+ });
+ EXPECT_TRUE(std::equal(range.begin(), range.end(), result_range.begin()));
+}
+
+TEST(Foreach, ForEachFunctionBasicTupleOneArg) {
+ auto range = std::make_tuple(1, 2, 3);
+ auto current = 0;
+ folly::for_each(range, [&](auto ele) {
+ if (current == 0) {
+ EXPECT_EQ(ele, 1);
+ } else if (current == 1) {
+ EXPECT_EQ(ele, 2);
+ } else {
+ EXPECT_EQ(ele, 3);
+ }
+ ++current;
+ });
+}
+
+TEST(Foreach, ForEachFunctionBasicTupleTwoArg) {
+ auto range = std::make_tuple(1, 2, 3);
+ folly::for_each(range, [](auto ele, auto index) {
+ EXPECT_TRUE(index < 3);
+ if (index == 0) {
+ EXPECT_EQ(ele, 1);
+ } else if (index == 1) {
+ EXPECT_EQ(ele, 2);
+ } else if (index == 2) {
+ EXPECT_EQ(ele, 3);
+ }
+ });
+}
+
+TEST(Foreach, ForEachFunctionBreakRuntimeOneArg) {
+ auto range = std::vector<int>{1, 2, 3};
+ auto iterations = 0;
+ folly::for_each(range, [&](auto) {
+ ++iterations;
+ if (iterations == 1) {
+ return folly::loop_break;
+ }
+ return folly::loop_continue;
+ });
+ EXPECT_EQ(iterations, 1);
+}
+
+TEST(Foreach, ForEachFunctionBreakRuntimeTwoArg) {
+ auto range = std::vector<int>{1, 2, 3};
+ auto iterations = 0;
+ folly::for_each(range, [&](auto, auto index) {
+ ++iterations;
+ if (index == 1) {
+ return folly::loop_break;
+ }
+ return folly::loop_continue;
+ });
+ EXPECT_EQ(iterations, 2);
+}
+
+TEST(Foreach, ForEachFunctionBreakRuntimeThreeArg) {
+ auto range = std::vector<int>{1, 2, 3};
+ auto iterations = 0;
+ folly::for_each(range, [&](auto, auto index, auto) {
+ ++iterations;
+ if (index == 1) {
+ return folly::loop_break;
+ }
+ return folly::loop_continue;
+ });
+ EXPECT_EQ(iterations, 2);
+}
+
+TEST(Foreach, ForEachFunctionBreakTupleOneArg) {
+ auto range = std::vector<int>{1, 2, 3};
+ auto iterations = 0;
+ folly::for_each(range, [&](auto) {
+ ++iterations;
+ if (iterations == 1) {
+ return folly::loop_break;
+ }
+ return folly::loop_continue;
+ });
+ EXPECT_EQ(iterations, 1);
+}
+
+TEST(Foreach, ForEachFunctionBreakTupleTwoArg) {
+ auto range = std::vector<int>{1, 2, 3};
+ auto iterations = 0;
+ folly::for_each(range, [&](auto, auto index) {
+ ++iterations;
+ if (index == 1) {
+ return folly::loop_break;
+ }
+ return folly::loop_continue;
+ });
+ EXPECT_EQ(iterations, 2);
+}
+
+TEST(Foreach, ForEachFunctionArray) {
+ auto range = std::array<int, 3>{{1, 2, 3}};
+ auto iterations = 0;
+ folly::for_each(range, [&](auto, auto index) {
+ ++iterations;
+ if (index == 1) {
+ return folly::loop_break;
+ }
+ return folly::loop_continue;
+ });
+ EXPECT_EQ(iterations, 2);
+}
+
+TEST(Foreach, ForEachFunctionInitializerListBasic) {
+ folly::for_each(std::initializer_list<int>{1, 2, 3}, [](auto ele) { ++ele; });
+}
+
+TEST(Foreach, ForEachFunctionTestForward) {
+ using folly::test::TestRValueConstruct;
+ auto range_one = std::vector<TestRValueConstruct>{};
+ range_one.resize(3);
+
+ folly::for_each(std::move(range_one), [](auto ele) {
+ EXPECT_FALSE(ele.constructed_from_rvalue);
+ });
+
+ folly::for_each(
+ std::make_tuple(TestRValueConstruct{}, TestRValueConstruct{}),
+ [](auto ele) { EXPECT_TRUE(ele.constructed_from_rvalue); });
+}
+
+TEST(Foreach, ForEachFunctionAdlIterable) {
+ auto range = test::TestAdlIterable{};
+ auto iterations = 0;
+ folly::for_each(range, [&](auto ele, auto index) {
+ ++iterations;
+ EXPECT_EQ(ele, index);
+ });
+ EXPECT_EQ(iterations, 4);
+}
+
+TEST(ForEach, FetchRandomAccessIterator) {
+ auto vec = std::vector<int>{1, 2, 3};
+ auto& second = folly::fetch(vec, 1);
+ EXPECT_EQ(second, 2);
+ second = 3;
+ EXPECT_EQ(second, 3);
+}
+
+TEST(ForEach, FetchIndexing) {
+ auto mp = std::map<int, int>{{1, 2}};
+ auto& ele = folly::fetch(mp, 1);
+ EXPECT_EQ(ele, 2);
+ ele = 3;
+ EXPECT_EQ(ele, 3);
+}
+
+TEST(ForEach, FetchTuple) {
+ auto mp = std::make_tuple(1, 2, 3);
+ auto& ele = folly::fetch(mp, std::integral_constant<int, 1>{});
+ EXPECT_EQ(ele, 2);
+ ele = 3;
+ EXPECT_EQ(ele, 3);
+}
+
+TEST(ForEach, FetchTestPreferIterator) {
+ auto range = test::TestBothIndexingAndIter{};
+ auto& ele = folly::fetch(range, 0);
+ EXPECT_TRUE(range.called_begin);
+ EXPECT_EQ(ele, 0);
+ ele = 2;
+ EXPECT_EQ(folly::fetch(range, 0), 2);
+}
+
+TEST(Foreach, ForEachRvalue) {
+ const char* const hello = "hello";
+ int n = 0;
+ FOR_EACH(it, std::string(hello)) {
+ ++n;
+ }
+ EXPECT_EQ(strlen(hello), n);
+ FOR_EACH_R(it, std::string(hello)) {
+ --n;
+ EXPECT_EQ(hello[n], *it);
+ }
+ EXPECT_EQ(0, n);
+}
+
+TEST(Foreach, ForEachNested) {
+ const std::string hello = "hello";
+ size_t n = 0;
+ FOR_EACH(i, hello) {
+ FOR_EACH(j, hello) {
+ ++n;
+ }
+ }
+ auto len = hello.size();
+ EXPECT_EQ(len * len, n);
+}
+
+TEST(Foreach, ForEachKV) {
+ std::map<std::string, int> testMap;
+ testMap["abc"] = 1;
+ testMap["def"] = 2;
+ std::string keys = "";
+ int values = 0;
+ int numEntries = 0;
+ FOR_EACH_KV (key, value, testMap) {
+ keys += key;
+ values += value;
+ ++numEntries;
+ }
+ EXPECT_EQ("abcdef", keys);
+ EXPECT_EQ(3, values);
+ EXPECT_EQ(2, numEntries);
+}
+
+TEST(Foreach, ForEachKVBreak) {
+ std::map<std::string, int> testMap;
+ testMap["abc"] = 1;
+ testMap["def"] = 2;
+ std::string keys = "";
+ int values = 0;
+ int numEntries = 0;
+ FOR_EACH_KV (key, value, testMap) {
+ keys += key;
+ values += value;
+ ++numEntries;
+ break;
+ }
+ EXPECT_EQ("abc", keys);
+ EXPECT_EQ(1, values);
+ EXPECT_EQ(1, numEntries);
+}
+
+TEST(Foreach, ForEachKvWithMultiMap) {
+ std::multimap<std::string, int> testMap;
+ testMap.insert(std::make_pair("abc", 1));
+ testMap.insert(std::make_pair("abc", 2));
+ testMap.insert(std::make_pair("def", 3));
+ std::string keys = "";
+ int values = 0;
+ int numEntries = 0;
+ FOR_EACH_KV (key, value, testMap) {
+ keys += key;
+ values += value;
+ ++numEntries;
+ }
+ EXPECT_EQ("abcabcdef", keys);
+ EXPECT_EQ(6, values);
+ EXPECT_EQ(3, numEntries);
+}
+
+TEST(Foreach, ForEachEnumerate) {
+ std::vector<int> vv;
+ int sumAA = 0;
+ int sumIter = 0;
+ int numIterations = 0;
+ FOR_EACH_ENUMERATE(aa, iter, vv) {
+ sumAA += aa;
+ sumIter += *iter;
+ ++numIterations;
+ }
+ EXPECT_EQ(sumAA, 0);
+ EXPECT_EQ(sumIter, 0);
+ EXPECT_EQ(numIterations, 0);
+
+ vv.push_back(1);
+ vv.push_back(3);
+ vv.push_back(5);
+ FOR_EACH_ENUMERATE(aa, iter, vv) {
+ sumAA += aa;
+ sumIter += *iter;
+ ++numIterations;
+ }
+ EXPECT_EQ(sumAA, 3); // 0 + 1 + 2
+ EXPECT_EQ(sumIter, 9); // 1 + 3 + 5
+ EXPECT_EQ(numIterations, 3);
+}
+
+TEST(Foreach, ForEachEnumerateBreak) {
+ std::vector<int> vv;
+ int sumAA = 0;
+ int sumIter = 0;
+ int numIterations = 0;
+ vv.push_back(1);
+ vv.push_back(2);
+ vv.push_back(4);
+ vv.push_back(8);
+ FOR_EACH_ENUMERATE(aa, iter, vv) {
+ sumAA += aa;
+ sumIter += *iter;
+ ++numIterations;
+ if (aa == 1) {
+ break;
+ }
+ }
+ EXPECT_EQ(sumAA, 1); // 0 + 1
+ EXPECT_EQ(sumIter, 3); // 1 + 2
+ EXPECT_EQ(numIterations, 2);
+}
+
+TEST(Foreach, ForEachRangeR) {
+ int sum = 0;
+
+ FOR_EACH_RANGE_R (i, 0, 0) {
+ sum += i;
+ }
+ EXPECT_EQ(0, sum);
+
+ FOR_EACH_RANGE_R (i, 0, -1) {
+ sum += i;
+ }
+ EXPECT_EQ(0, sum);
+
+ FOR_EACH_RANGE_R (i, 0, 5) {
+ sum += i;
+ }
+ EXPECT_EQ(10, sum);
+
+ std::list<int> lst = { 0, 1, 2, 3, 4 };
+ sum = 0;
+ FOR_EACH_RANGE_R (i, lst.begin(), lst.end()) {
+ sum += *i;
+ }
+ EXPECT_EQ(10, sum);
+}
--- /dev/null
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * 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
+ *
+ * http://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 <algorithm>
+#include <cassert>
+#include <cstddef>
+#include <deque>
+#include <functional>
+#include <map>
+#include <set>
+#include <tuple>
+#include <type_traits>
+#include <utility>
+#include <vector>
+
+#include <folly/container/Iterator.h>
+#include <folly/portability/GTest.h>
+
+namespace {
+/**
+ * Container type used for unit tests.
+ */
+template <typename T>
+using Container = std::deque<T>;
+
+// Constructor and assignment operator call counters for struct Object.
+std::size_t gDefaultCtrCnt;
+std::size_t gCopyCtrCnt;
+std::size_t gMoveCtrCnt;
+std::size_t gExplicitCtrCnt;
+std::size_t gMultiargCtrCnt;
+std::size_t gCopyOpCnt;
+std::size_t gMoveOpCnt;
+std::size_t gConvertOpCnt;
+
+/**
+ * Class that increases various counters to keep track of how objects have
+ * been constructed or assigned to, to verify iterator behavior.
+ */
+struct Object {
+ Object() {
+ ++gDefaultCtrCnt;
+ }
+ Object(const Object&) {
+ ++gCopyCtrCnt;
+ }
+ Object(Object&&) noexcept {
+ ++gMoveCtrCnt;
+ }
+ explicit Object(int) {
+ ++gExplicitCtrCnt;
+ }
+ explicit Object(int, int) {
+ ++gMultiargCtrCnt;
+ }
+ Object& operator=(const Object&) {
+ ++gCopyOpCnt;
+ return *this;
+ }
+ Object& operator=(Object&&) noexcept {
+ ++gMoveOpCnt;
+ return *this;
+ }
+ Object& operator=(int) noexcept {
+ ++gConvertOpCnt;
+ return *this;
+ }
+};
+
+/**
+ * Reset all call counters to 0.
+ */
+void init_counters() {
+ gDefaultCtrCnt = gCopyCtrCnt = gMoveCtrCnt = gExplicitCtrCnt =
+ gMultiargCtrCnt = gCopyOpCnt = gMoveOpCnt = gConvertOpCnt = 0;
+}
+
+/**
+ * Test for iterator copy and move.
+ */
+template <typename Iterator>
+void copy_and_move_test(Container<int>& q, Iterator it) {
+ assert(q.empty());
+ const auto it2(it); // copy construct
+ it = it2; // copy assign from const
+ it = it; // self assign
+ auto it3(std::move(it)); // move construct
+ it = std::move(it3); // move assign
+ // Make sure iterator still works.
+ it = 4711; // emplace
+ EXPECT_EQ(q, Container<int>{4711});
+}
+
+/**
+ * Test for emplacement with perfect forwarding.
+ */
+template <typename Iterator>
+void emplace_test(Container<Object>& q, Iterator it) {
+ using folly::make_emplace_args;
+ assert(q.empty());
+ init_counters();
+ it = Object{}; // default construct + move construct
+ Object obj; // default construct
+ it = obj; // copy construct
+ it = std::move(obj); // move construct
+ const Object obj2; // default construct
+ it = obj2; // copy construct from const
+ it = std::move(obj2); // copy construct (const defeats move)
+ it = 0; // explicit construct
+ it = make_emplace_args(0, 0); // explicit multiarg construct
+ it = std::make_pair(0, 0); // implicit multiarg construct
+ it = std::make_tuple(0, 0); // implicit multiarg construct
+ auto args = make_emplace_args(Object{}); // default construct + move construct
+ it = args; // copy construct
+ it = const_cast<const decltype(args)&>(args); // copy construct from const
+ it = std::move(args); // move construct
+ auto args2 = std::make_tuple(Object{}); // default construct + move construct
+ it = args2; // (implicit multiarg) copy construct
+ it = std::move(args2); // (implicit multiarg) move construct
+ auto args3 = std::make_pair(0, 0);
+ it = args3; // implicit multiarg construct
+ it = std::move(args3); // implicit multiarg construct
+ ASSERT_EQ(q.size(), 16);
+ EXPECT_EQ(gDefaultCtrCnt, 5);
+ EXPECT_EQ(gCopyCtrCnt, 6);
+ EXPECT_EQ(gMoveCtrCnt, 6);
+ EXPECT_EQ(gExplicitCtrCnt, 1);
+ EXPECT_EQ(gMultiargCtrCnt, 5);
+ EXPECT_EQ(gCopyOpCnt, 0);
+ EXPECT_EQ(gMoveOpCnt, 0);
+ EXPECT_EQ(gConvertOpCnt, 0);
+}
+}
+
+using namespace folly;
+
+/**
+ * Basic tests for folly::emplace_iterator.
+ */
+TEST(EmplaceIterator, EmplacerTest) {
+ {
+ Container<int> q;
+ copy_and_move_test(q, emplacer(q, q.begin()));
+ }
+ {
+ Container<Object> q;
+ emplace_test(q, emplacer(q, q.begin()));
+ }
+ {
+ Container<int> q;
+ auto it = emplacer(q, q.begin());
+ it = 0;
+ it = 1;
+ it = 2;
+ it = emplacer(q, q.begin());
+ it = 3;
+ it = 4;
+ EXPECT_EQ(q, Container<int>({3, 4, 0, 1, 2}));
+ }
+}
+
+/**
+ * Basic tests for folly::front_emplace_iterator.
+ */
+TEST(EmplaceIterator, FrontEmplacerTest) {
+ {
+ Container<int> q;
+ copy_and_move_test(q, front_emplacer(q));
+ }
+ {
+ Container<Object> q;
+ emplace_test(q, front_emplacer(q));
+ }
+ {
+ Container<int> q;
+ auto it = front_emplacer(q);
+ it = 0;
+ it = 1;
+ it = 2;
+ it = front_emplacer(q);
+ it = 3;
+ it = 4;
+ EXPECT_EQ(q, Container<int>({4, 3, 2, 1, 0}));
+ }
+}
+
+/**
+ * Basic tests for folly::back_emplace_iterator.
+ */
+TEST(EmplaceIterator, BackEmplacerTest) {
+ {
+ Container<int> q;
+ copy_and_move_test(q, back_emplacer(q));
+ }
+ {
+ Container<Object> q;
+ emplace_test(q, back_emplacer(q));
+ }
+ {
+ Container<int> q;
+ auto it = back_emplacer(q);
+ it = 0;
+ it = 1;
+ it = 2;
+ it = back_emplacer(q);
+ it = 3;
+ it = 4;
+ EXPECT_EQ(q, Container<int>({0, 1, 2, 3, 4}));
+ }
+}
+
+/**
+ * Basic tests for folly::hint_emplace_iterator.
+ */
+TEST(EmplaceIterator, HintEmplacerTest) {
+ {
+ init_counters();
+ std::map<int, Object> m;
+ auto it = hint_emplacer(m, m.end());
+ it = make_emplace_args(
+ std::piecewise_construct,
+ std::forward_as_tuple(0),
+ std::forward_as_tuple(0));
+ it = make_emplace_args(
+ std::piecewise_construct,
+ std::forward_as_tuple(1),
+ std::forward_as_tuple(0, 0));
+ it = make_emplace_args(
+ std::piecewise_construct,
+ std::forward_as_tuple(2),
+ std::forward_as_tuple(Object{}));
+ ASSERT_EQ(m.size(), 3);
+ EXPECT_EQ(gDefaultCtrCnt, 1);
+ EXPECT_EQ(gCopyCtrCnt, 0);
+ EXPECT_EQ(gMoveCtrCnt, 1);
+ EXPECT_EQ(gExplicitCtrCnt, 1);
+ EXPECT_EQ(gMultiargCtrCnt, 1);
+ EXPECT_EQ(gCopyOpCnt, 0);
+ EXPECT_EQ(gMoveOpCnt, 0);
+ EXPECT_EQ(gConvertOpCnt, 0);
+ }
+ {
+ struct O {
+ explicit O(int i) : i(i) {}
+ bool operator<(const O& other) const {
+ return i < other.i;
+ }
+ bool operator==(const O& other) const {
+ return i == other.i;
+ }
+ int i;
+ };
+ std::vector<int> v1 = {0, 1, 2, 3, 4};
+ std::vector<int> v2 = {0, 2, 4};
+ std::set<O> diff;
+ std::set_difference(
+ v1.begin(),
+ v1.end(),
+ v2.begin(),
+ v2.end(),
+ hint_emplacer(diff, diff.end()));
+ ASSERT_EQ(diff, std::set<O>({O(1), O(3)}));
+ }
+}
+
+/**
+ * Test std::copy() with explicit conversion. This would not compile with a
+ * std::back_insert_iterator, because the constructor of Object that takes a
+ * single int is explicit.
+ */
+TEST(EmplaceIterator, Copy) {
+ init_counters();
+ Container<int> in({0, 1, 2});
+ Container<Object> out;
+ std::copy(in.begin(), in.end(), back_emplacer(out));
+ EXPECT_EQ(3, out.size());
+ EXPECT_EQ(gDefaultCtrCnt, 0);
+ EXPECT_EQ(gCopyCtrCnt, 0);
+ EXPECT_EQ(gMoveCtrCnt, 0);
+ EXPECT_EQ(gExplicitCtrCnt, 3);
+ EXPECT_EQ(gMultiargCtrCnt, 0);
+ EXPECT_EQ(gCopyOpCnt, 0);
+ EXPECT_EQ(gMoveOpCnt, 0);
+ EXPECT_EQ(gConvertOpCnt, 0);
+}
+
+/**
+ * Test std::transform() with multi-argument constructors. This would require
+ * a temporary Object with std::back_insert_iterator.
+ */
+TEST(EmplaceIterator, Transform) {
+ init_counters();
+ Container<int> in({0, 1, 2});
+ Container<Object> out;
+ std::transform(in.begin(), in.end(), back_emplacer(out), [](int i) {
+ return make_emplace_args(i, i);
+ });
+ EXPECT_EQ(3, out.size());
+ EXPECT_EQ(gDefaultCtrCnt, 0);
+ EXPECT_EQ(gCopyCtrCnt, 0);
+ EXPECT_EQ(gMoveCtrCnt, 0);
+ EXPECT_EQ(gExplicitCtrCnt, 0);
+ EXPECT_EQ(gMultiargCtrCnt, 3);
+ EXPECT_EQ(gCopyOpCnt, 0);
+ EXPECT_EQ(gMoveOpCnt, 0);
+ EXPECT_EQ(gConvertOpCnt, 0);
+}
+
+/**
+ * Test multi-argument store and forward.
+ */
+TEST(EmplaceIterator, EmplaceArgs) {
+ Object o1;
+ const Object o2;
+ Object& o3 = o1;
+ const Object& o4 = o3;
+ Object o5;
+
+ {
+ // Test copy construction.
+ auto args = make_emplace_args(0, o1, o2, o3, o4, Object{}, std::cref(o2));
+ init_counters();
+ auto args2 = args;
+ EXPECT_EQ(gDefaultCtrCnt, 0);
+ EXPECT_EQ(gCopyCtrCnt, 5);
+ EXPECT_EQ(gMoveCtrCnt, 0);
+ EXPECT_EQ(gExplicitCtrCnt, 0);
+ EXPECT_EQ(gMultiargCtrCnt, 0);
+ EXPECT_EQ(gCopyOpCnt, 0);
+ EXPECT_EQ(gMoveOpCnt, 0);
+ EXPECT_EQ(gConvertOpCnt, 0);
+
+ // Test copy assignment.
+ init_counters();
+ args = args2;
+ EXPECT_EQ(gDefaultCtrCnt, 0);
+ EXPECT_EQ(gCopyCtrCnt, 0);
+ EXPECT_EQ(gMoveCtrCnt, 0);
+ EXPECT_EQ(gExplicitCtrCnt, 0);
+ EXPECT_EQ(gMultiargCtrCnt, 0);
+ EXPECT_EQ(gCopyOpCnt, 5);
+ EXPECT_EQ(gMoveOpCnt, 0);
+ EXPECT_EQ(gConvertOpCnt, 0);
+ }
+
+ {
+ // Test RVO.
+ init_counters();
+ auto args = make_emplace_args(
+ 0, o1, o2, o3, o4, Object{}, std::cref(o2), rref(std::move(o5)));
+ EXPECT_EQ(gDefaultCtrCnt, 1);
+ EXPECT_EQ(gCopyCtrCnt, 4);
+ EXPECT_EQ(gMoveCtrCnt, 1);
+ EXPECT_EQ(gExplicitCtrCnt, 0);
+ EXPECT_EQ(gMultiargCtrCnt, 0);
+ EXPECT_EQ(gCopyOpCnt, 0);
+ EXPECT_EQ(gMoveOpCnt, 0);
+ EXPECT_EQ(gConvertOpCnt, 0);
+
+ // Test move construction.
+ init_counters();
+ auto args2 = std::move(args);
+ EXPECT_EQ(gDefaultCtrCnt, 0);
+ EXPECT_EQ(gCopyCtrCnt, 0);
+ EXPECT_EQ(gMoveCtrCnt, 5);
+ EXPECT_EQ(gExplicitCtrCnt, 0);
+ EXPECT_EQ(gMultiargCtrCnt, 0);
+ EXPECT_EQ(gCopyOpCnt, 0);
+ EXPECT_EQ(gMoveOpCnt, 0);
+ EXPECT_EQ(gConvertOpCnt, 0);
+
+ // Test move assignment.
+ init_counters();
+ args = std::move(args2);
+ EXPECT_EQ(gDefaultCtrCnt, 0);
+ EXPECT_EQ(gCopyCtrCnt, 0);
+ EXPECT_EQ(gMoveCtrCnt, 0);
+ EXPECT_EQ(gExplicitCtrCnt, 0);
+ EXPECT_EQ(gMultiargCtrCnt, 0);
+ EXPECT_EQ(gCopyOpCnt, 0);
+ EXPECT_EQ(gMoveOpCnt, 5);
+ EXPECT_EQ(gConvertOpCnt, 0);
+
+ // Make sure arguments are stored correctly. lvalues by reference, rvalues
+ // by (moved) copy. Rvalues cannot be stored by reference because they may
+ // refer to an expired temporary by the time they are accessed.
+ static_assert(
+ std::is_same<
+ int,
+ std::tuple_element_t<0, decltype(args)::storage_type>>::value,
+ "");
+ static_assert(
+ std::is_same<
+ Object,
+ std::tuple_element_t<1, decltype(args)::storage_type>>::value,
+ "");
+ static_assert(
+ std::is_same<
+ Object,
+ std::tuple_element_t<2, decltype(args)::storage_type>>::value,
+ "");
+ static_assert(
+ std::is_same<
+ Object,
+ std::tuple_element_t<3, decltype(args)::storage_type>>::value,
+ "");
+ static_assert(
+ std::is_same<
+ Object,
+ std::tuple_element_t<4, decltype(args)::storage_type>>::value,
+ "");
+ static_assert(
+ std::is_same<
+ Object,
+ std::tuple_element_t<5, decltype(args)::storage_type>>::value,
+ "");
+ static_assert(
+ std::is_same<
+ std::reference_wrapper<const Object>,
+ std::tuple_element_t<6, decltype(args)::storage_type>>::value,
+ "");
+ static_assert(
+ std::is_same<
+ rvalue_reference_wrapper<Object>,
+ std::tuple_element_t<7, decltype(args)::storage_type>>::value,
+ "");
+
+ // Check whether args.get() restores the original argument type for
+ // rvalue references to emplace_args.
+ static_assert(
+ std::is_same<int&&, decltype(get_emplace_arg<0>(std::move(args)))>::
+ value,
+ "");
+ static_assert(
+ std::is_same<Object&, decltype(get_emplace_arg<1>(std::move(args)))>::
+ value,
+ "");
+ static_assert(
+ std::is_same<
+ const Object&,
+ decltype(get_emplace_arg<2>(std::move(args)))>::value,
+ "");
+ static_assert(
+ std::is_same<Object&, decltype(get_emplace_arg<3>(std::move(args)))>::
+ value,
+ "");
+ static_assert(
+ std::is_same<
+ const Object&,
+ decltype(get_emplace_arg<4>(std::move(args)))>::value,
+ "");
+ static_assert(
+ std::is_same<Object&&, decltype(get_emplace_arg<5>(std::move(args)))>::
+ value,
+ "");
+ static_assert(
+ std::is_same<
+ const Object&,
+ decltype(get_emplace_arg<6>(std::move(args)))>::value,
+ "");
+ static_assert(
+ std::is_same<Object&&, decltype(get_emplace_arg<7>(std::move(args)))>::
+ value,
+ "");
+
+ // lvalue references to emplace_args should behave mostly like std::tuples.
+ // Note that get_emplace_arg<7>(args) does not compile, because
+ // folly::rvalue_reference_wrappers can only be unwrapped through an rvalue
+ // reference.
+ static_assert(
+ std::is_same<int&, decltype(get_emplace_arg<0>(args))>::value, "");
+ static_assert(
+ std::is_same<Object&, decltype(get_emplace_arg<1>(args))>::value, "");
+ static_assert(
+ std::is_same<Object&, decltype(get_emplace_arg<2>(args))>::value, "");
+ static_assert(
+ std::is_same<Object&, decltype(get_emplace_arg<3>(args))>::value, "");
+ static_assert(
+ std::is_same<Object&, decltype(get_emplace_arg<4>(args))>::value, "");
+ static_assert(
+ std::is_same<Object&, decltype(get_emplace_arg<5>(args))>::value, "");
+ static_assert(
+ std::is_same<const Object&, decltype(get_emplace_arg<6>(args))>::value,
+ "");
+ }
+}
+
+/**
+ * Test implicit unpacking.
+ */
+TEST(EmplaceIterator, ImplicitUnpack) {
+ static std::size_t multiCtrCnt;
+ static std::size_t pairCtrCnt;
+ static std::size_t tupleCtrCnt;
+
+ struct Object2 {
+ Object2(int, int) {
+ ++multiCtrCnt;
+ }
+ explicit Object2(const std::pair<int, int>&) {
+ ++pairCtrCnt;
+ }
+ explicit Object2(const std::tuple<int, int>&) {
+ ++tupleCtrCnt;
+ }
+ };
+
+ auto test = [](auto&& it, bool expectUnpack) {
+ multiCtrCnt = pairCtrCnt = tupleCtrCnt = 0;
+ it = std::make_pair(0, 0);
+ it = std::make_tuple(0, 0);
+ if (expectUnpack) {
+ EXPECT_EQ(multiCtrCnt, 2);
+ EXPECT_EQ(pairCtrCnt, 0);
+ EXPECT_EQ(tupleCtrCnt, 0);
+ } else {
+ EXPECT_EQ(multiCtrCnt, 0);
+ EXPECT_EQ(pairCtrCnt, 1);
+ EXPECT_EQ(tupleCtrCnt, 1);
+ }
+ };
+
+ Container<Object2> q;
+
+ test(emplacer(q, q.begin()), true);
+ test(emplacer<false>(q, q.begin()), false);
+ test(front_emplacer(q), true);
+ test(front_emplacer<false>(q), false);
+ test(back_emplacer(q), true);
+ test(back_emplacer<false>(q), false);
+}
--- /dev/null
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * 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
+ *
+ * http://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 <folly/container/Merge.h>
+
+#include <map>
+#include <vector>
+
+#include <folly/portability/GTest.h>
+
+TEST(MergeTest, NonOverlapping) {
+ std::vector<int> a = {0, 2, 4, 6};
+ std::vector<int> b = {1, 3, 5, 7};
+ std::vector<int> c;
+
+ folly::merge(a.begin(), a.end(),
+ b.begin(), b.end(),
+ std::back_inserter(c));
+ EXPECT_EQ(8, c.size());
+ for (size_t i = 0; i < 8; ++i) {
+ EXPECT_EQ(i, c[i]);
+ }
+}
+
+TEST(MergeTest, OverlappingInSingleInputRange) {
+ std::vector<std::pair<int, int>> a = {{0, 0}, {0, 1}};
+ std::vector<std::pair<int, int>> b = {{2, 2}, {3, 3}};
+ std::map<int, int> c;
+
+ folly::merge(a.begin(), a.end(),
+ b.begin(), b.end(),
+ std::inserter(c, c.begin()));
+ EXPECT_EQ(3, c.size());
+
+ // First value is inserted, second is not
+ EXPECT_EQ(c[0], 0);
+
+ EXPECT_EQ(c[2], 2);
+ EXPECT_EQ(c[3], 3);
+}
+
+TEST(MergeTest, OverlappingInDifferentInputRange) {
+ std::vector<std::pair<int, int>> a = {{0, 0}, {1, 1}};
+ std::vector<std::pair<int, int>> b = {{0, 2}, {3, 3}};
+ std::map<int, int> c;
+
+ folly::merge(a.begin(), a.end(),
+ b.begin(), b.end(),
+ std::inserter(c, c.begin()));
+ EXPECT_EQ(3, c.size());
+
+ // Value from a is inserted, value from b is not.
+ EXPECT_EQ(c[0], 0);
+
+ EXPECT_EQ(c[1], 1);
+ EXPECT_EQ(c[3], 3);
+}
--- /dev/null
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * 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
+ *
+ * http://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.
+ */
+
+/***
+ * A benchmark comparing SparseByteSet to bitset<256> and bool[256].
+ */
+
+#include <folly/Benchmark.h>
+#include <folly/Format.h>
+#include <folly/container/SparseByteSet.h>
+#include <folly/portability/GFlags.h>
+#include <bitset>
+#include <random>
+#include <vector>
+
+using namespace std;
+using namespace folly;
+
+namespace {
+
+// Interface-identical to SparseByteSet. So that we can do compile-time
+// polymorphism.
+class BitSetWrapper {
+ public:
+ inline bool add(uint8_t i) {
+ auto r = !contains(i);
+ if (r) {
+ rep_[i] = true;
+ }
+ return r;
+ }
+ inline bool contains(uint8_t i) {
+ return rep_[i];
+ }
+ private:
+ bitset<256> rep_;
+};
+class BoolArraySet {
+ public:
+ BoolArraySet() {
+ memset(rep_, 0, sizeof(rep_));
+ }
+ inline bool add(uint8_t i) {
+ auto r = !contains(i);
+ if (r) {
+ rep_[i] = true;
+ }
+ return r;
+ }
+ inline bool contains(uint8_t i) {
+ return rep_[i];
+ }
+ private:
+ bool rep_[256];
+};
+
+template <typename Coll>
+void rand_bench(int iters, size_t size_add, size_t size_contains) {
+ BenchmarkSuspender braces;
+ vector<uint8_t> seq_add;
+ vector<uint8_t> seq_contains;
+ mt19937 rng;
+ uniform_int_distribution<uint8_t> dist;
+ for (size_t i = 0; i < size_add; ++i) {
+ seq_add.push_back(dist(rng));
+ }
+ for (size_t i = 0; i < size_contains; ++i) {
+ seq_contains.push_back(dist(rng));
+ }
+ braces.dismissing([&] {
+ while (iters--) {
+ Coll coll;
+ for (auto b : seq_add) {
+ coll.add(b);
+ }
+ bool q {};
+ for (auto b : seq_contains) {
+ q ^= coll.contains(b);
+ }
+ doNotOptimizeAway(q);
+ }
+ });
+}
+
+void setup_rand_bench() {
+ vector<pair<size_t, size_t>> rand_bench_params = {
+ {4, 4},
+ {4, 16},
+ {4, 64},
+ {4, 256},
+ {16, 4},
+ {16, 16},
+ {16, 64},
+ {16, 256},
+ {64, 4},
+ {64, 16},
+ {64, 64},
+ {64, 256},
+ {256, 4},
+ {256, 16},
+ {256, 64},
+ {256, 256},
+ };
+ for (auto kvp : rand_bench_params) {
+ size_t size_add, size_contains;
+ tie(size_add, size_contains) = kvp;
+ addBenchmark(
+ __FILE__,
+ sformat("bitset_rand_bench({}, {})",
+ size_add, size_contains).c_str(),
+ [=](int iters) {
+ rand_bench<BitSetWrapper>(iters, size_add, size_contains);
+ return iters;
+ });
+ addBenchmark(
+ __FILE__,
+ sformat("%bool_array_set_rand_bench({}, {})",
+ size_add, size_contains).c_str(),
+ [=](int iters) {
+ rand_bench<BoolArraySet>(iters, size_add, size_contains);
+ return iters;
+ });
+ addBenchmark(
+ __FILE__,
+ sformat("%sparse_byte_set_rand_bench({}, {})",
+ size_add, size_contains).c_str(),
+ [=](int iters) {
+ rand_bench<SparseByteSet>(iters, size_add, size_contains);
+ return iters;
+ });
+ addBenchmark(
+ __FILE__,
+ "-",
+ [](int) { return 0; });
+ }
+}
+
+}
+
+int main(int argc, char** argv) {
+ gflags::ParseCommandLineFlags(&argc, &argv, true);
+ setup_rand_bench();
+ runBenchmarks();
+ return 0;
+}
--- /dev/null
+/*
+ * Copyright 2017 Facebook, Inc.
+ *
+ * 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
+ *
+ * http://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 <folly/container/SparseByteSet.h>
+
+#include <cstdint>
+#include <limits>
+#include <random>
+#include <set>
+
+#include <folly/portability/GTest.h>
+
+using namespace std;
+using namespace folly;
+
+namespace {
+
+class SparseByteSetTest : public testing::Test {
+ protected:
+ using lims = numeric_limits<uint8_t>;
+ SparseByteSet s;
+};
+
+}
+
+TEST_F(SparseByteSetTest, empty) {
+ for (auto c = lims::min(); c < lims::max(); ++c) {
+ EXPECT_FALSE(s.contains(c));
+ }
+}
+
+TEST_F(SparseByteSetTest, each) {
+ for (auto c = lims::min(); c < lims::max(); ++c) {
+ EXPECT_TRUE(s.add(c));
+ EXPECT_TRUE(s.contains(c));
+ }
+ for (auto c = lims::min(); c < lims::max(); ++c) {
+ EXPECT_FALSE(s.add(c));
+ EXPECT_TRUE(s.contains(c));
+ }
+}
+
+TEST_F(SparseByteSetTest, each_random) {
+ mt19937 rng;
+ uniform_int_distribution<uint16_t> dist{lims::min(), lims::max()};
+ set<uint8_t> added;
+ while (added.size() <= lims::max()) {
+ auto c = uint8_t(dist(rng));
+ EXPECT_EQ(added.count(c), s.contains(c));
+ EXPECT_EQ(!added.count(c), s.add(c));
+ added.insert(c);
+ EXPECT_TRUE(added.count(c)); // sanity
+ EXPECT_TRUE(s.contains(c));
+ }
+}
#include <bitset>
-#include <folly/SparseByteSet.h>
+#include <folly/container/SparseByteSet.h>
namespace folly {
#include <glog/logging.h>
#include <folly/Exception.h>
-#include <folly/Foreach.h>
#include <folly/Function.h>
#include <folly/MicroSpinLock.h>
#include <folly/Portability.h>
#include <folly/ScopeGuard.h>
#include <folly/SharedMutex.h>
+#include <folly/container/Foreach.h>
#include <folly/memory/Malloc.h>
#include <folly/portability/PThread.h>
``` Cpp
#include <folly/Benchmark.h>
- #include <folly/Foreach.h>
+ #include <folly/container/Foreach.h>
#include <vector>
using namespace std;
using namespace folly;
``` Cpp
#include <folly/Benchmark.h>
- #include <folly/Foreach.h>
+ #include <folly/container/Foreach.h>
#include <vector>
using namespace std;
using namespace folly;
``` Cpp
#include <folly/Benchmark.h>
- #include <folly/Foreach.h>
+ #include <folly/container/Foreach.h>
#include <vector>
using namespace std;
using namespace folly;
#include <glog/logging.h>
#include <folly/Benchmark.h>
-#include <folly/Foreach.h>
#include <folly/String.h>
+#include <folly/container/Foreach.h>
#include <folly/gen/Base.h>
#include <folly/gen/String.h>
#include <folly/stats/Histogram.h>
#include <folly/Benchmark.h>
-#include <folly/Foreach.h>
+#include <folly/container/Foreach.h>
#include <folly/portability/GFlags.h>
using folly::Histogram;
#include <glog/logging.h>
-#include <folly/Foreach.h>
+#include <folly/container/Foreach.h>
#include <folly/portability/GTest.h>
using std::chrono::seconds;
*/
#include <folly/Benchmark.h>
-#include <folly/Foreach.h>
#include <folly/String.h>
+#include <folly/container/Foreach.h>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <glog/logging.h>
-#include <folly/Foreach.h>
#include <folly/Memory.h>
#include <folly/String.h>
+#include <folly/container/Foreach.h>
#include <folly/memory/Arena.h>
#include <folly/portability/GFlags.h>
#include <folly/portability/GTest.h>
#include <folly/Benchmark.h>
#include <folly/CppAttributes.h>
-#include <folly/Foreach.h>
+#include <folly/container/Foreach.h>
#include <array>
#include <limits>
#include <boost/lexical_cast.hpp>
#include <folly/Conv.h>
-#include <folly/Foreach.h>
+#include <folly/container/Foreach.h>
#include <folly/portability/GTest.h>
#include <algorithm>
+++ /dev/null
-/*
- * Copyright 2017 Facebook, Inc.
- *
- * 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
- *
- * http://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 <array>
-#include <string>
-#include <vector>
-
-#include <folly/Enumerate.h>
-#include <folly/Range.h>
-#include <folly/portability/GTest.h>
-
-TEST(Enumerate, Basic) {
- std::vector<std::string> v = {"abc", "a", "ab"};
- size_t i = 0;
- for (auto it : folly::enumerate(v)) {
- EXPECT_EQ(it.index, i);
- EXPECT_EQ(*it, v[i]);
- EXPECT_EQ(it->size(), v[i].size());
-
- // Test mutability.
- std::string newValue = "x";
- *it = newValue;
- EXPECT_EQ(newValue, v[i]);
-
- ++i;
- }
-
- EXPECT_EQ(i, v.size());
-}
-
-TEST(Enumerate, Temporary) {
- std::vector<std::string> v = {"abc", "a", "ab"};
- size_t i = 0;
- for (auto it : folly::enumerate(decltype(v)(v))) { // Copy v.
- EXPECT_EQ(it.index, i);
- EXPECT_EQ(*it, v[i]);
- EXPECT_EQ(it->size(), v[i].size());
- ++i;
- }
-
- EXPECT_EQ(i, v.size());
-};
-
-namespace {
-
-template <class T>
-struct IsConstReference {
- constexpr static bool value = false;
-};
-template <class T>
-struct IsConstReference<const T&> {
- constexpr static bool value = true;
-};
-
-} // namespace
-
-TEST(Enumerate, BasicConstArg) {
- const std::vector<std::string> v = {"abc", "a", "ab"};
- size_t i = 0;
- for (auto it : folly::enumerate(v)) {
- static_assert(
- IsConstReference<decltype(*it)>::value, "Enumerating a const vector");
- EXPECT_EQ(it.index, i);
- EXPECT_EQ(*it, v[i]);
- EXPECT_EQ(it->size(), v[i].size());
- ++i;
- }
-
- EXPECT_EQ(i, v.size());
-}
-
-TEST(Enumerate, BasicConstEnumerate) {
- std::vector<std::string> v = {"abc", "a", "ab"};
- size_t i = 0;
- for (const auto it : folly::enumerate(v)) {
- static_assert(IsConstReference<decltype(*it)>::value, "Const enumeration");
- EXPECT_EQ(it.index, i);
- EXPECT_EQ(*it, v[i]);
- EXPECT_EQ(it->size(), v[i].size());
- ++i;
- }
-
- EXPECT_EQ(i, v.size());
-}
-
-TEST(Enumerate, TemporaryConstEnumerate) {
- std::vector<std::string> v = {"abc", "a", "ab"};
- size_t i = 0;
- for (const auto it : folly::enumerate(decltype(v)(v))) { // Copy v.
- static_assert(IsConstReference<decltype(*it)>::value, "Const enumeration");
- EXPECT_EQ(it.index, i);
- EXPECT_EQ(*it, v[i]);
- EXPECT_EQ(it->size(), v[i].size());
- ++i;
- }
-
- EXPECT_EQ(i, v.size());
-}
-
-TEST(Enumerate, RangeSupport) {
- std::vector<std::string> v = {"abc", "a", "ab"};
- size_t i = 0;
- for (const auto it : folly::enumerate(folly::range(v))) {
- EXPECT_EQ(it.index, i);
- EXPECT_EQ(*it, v[i]);
- EXPECT_EQ(it->size(), v[i].size());
- ++i;
- }
-
- EXPECT_EQ(i, v.size());
-}
-
-TEST(Enumerate, EmptyRange) {
- std::vector<std::string> v;
- for (auto it : folly::enumerate(v)) {
- (void)it; // Silence warnings.
- ADD_FAILURE();
- }
-}
-
-class CStringRange {
- const char* cstr;
-
- public:
- struct Sentinel {};
-
- explicit CStringRange(const char* cstr) : cstr(cstr) {}
-
- const char* begin() const {
- return cstr;
- }
- Sentinel end() const {
- return Sentinel{};
- }
-};
-
-bool operator==(const char* c, CStringRange::Sentinel) {
- return *c == 0;
-}
-
-TEST(Enumerate, Cpp17Support) {
- std::array<char, 5> test = {"test"};
- // Can't use range based for loop until C++17, so test manually
- // Equivalent to:
- // for (const auto it : folly::enumerate(CStringRange{test.data()})) { ... }
- {
- auto&& enumerate = folly::enumerate(CStringRange{test.data()});
- auto begin = enumerate.begin();
- auto end = enumerate.end();
- for (; begin != end; ++begin) {
- const auto it = *begin;
-
- ASSERT_LT(it.index, test.size());
- EXPECT_EQ(*it, test[it.index]);
- }
- }
-}
+++ /dev/null
-/*
- * Copyright 2017 Facebook, Inc.
- *
- * 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
- *
- * http://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 <set>
-
-#include <folly/EvictingCacheMap.h>
-#include <folly/portability/GTest.h>
-
-using namespace folly;
-
-TEST(EvictingCacheMap, SanityTest) {
- EvictingCacheMap<int, int> map(0);
-
- EXPECT_EQ(0, map.size());
- EXPECT_TRUE(map.empty());
- EXPECT_FALSE(map.exists(1));
- map.set(1, 1);
- EXPECT_EQ(1, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_EQ(1, map.get(1));
- EXPECT_TRUE(map.exists(1));
- map.set(1, 2);
- EXPECT_EQ(1, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_EQ(2, map.get(1));
- EXPECT_TRUE(map.exists(1));
- map.erase(1);
- EXPECT_EQ(0, map.size());
- EXPECT_TRUE(map.empty());
- EXPECT_FALSE(map.exists(1));
-
- EXPECT_EQ(0, map.size());
- EXPECT_TRUE(map.empty());
- EXPECT_FALSE(map.exists(1));
- map.set(1, 1);
- EXPECT_EQ(1, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_EQ(1, map.get(1));
- EXPECT_TRUE(map.exists(1));
- map.set(1, 2);
- EXPECT_EQ(1, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_EQ(2, map.get(1));
- EXPECT_TRUE(map.exists(1));
-
- EXPECT_FALSE(map.exists(2));
- map.set(2, 1);
- EXPECT_TRUE(map.exists(2));
- EXPECT_EQ(2, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_EQ(1, map.get(2));
- map.set(2, 2);
- EXPECT_EQ(2, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_EQ(2, map.get(2));
- EXPECT_TRUE(map.exists(2));
- map.erase(2);
- EXPECT_EQ(1, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_FALSE(map.exists(2));
- map.erase(1);
- EXPECT_EQ(0, map.size());
- EXPECT_TRUE(map.empty());
- EXPECT_FALSE(map.exists(1));
-}
-
-
-TEST(EvictingCacheMap, PruneTest) {
- EvictingCacheMap<int, int> map(0);
- EXPECT_EQ(0, map.size());
- EXPECT_TRUE(map.empty());
- for (int i = 0; i < 100; i++) {
- EXPECT_FALSE(map.exists(i));
- }
-
- for (int i = 0; i < 100; i++) {
- map.set(i, i);
- EXPECT_EQ(i + 1, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_TRUE(map.exists(i));
- EXPECT_EQ(i, map.get(i));
- }
-
- map.prune(1000000);
- EXPECT_EQ(0, map.size());
- EXPECT_TRUE(map.empty());
- for (int i = 0; i < 100; i++) {
- EXPECT_FALSE(map.exists(i));
- }
-
- for (int i = 0; i < 100; i++) {
- map.set(i, i);
- EXPECT_EQ(i + 1, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_TRUE(map.exists(i));
- EXPECT_EQ(i, map.get(i));
- }
-
- map.prune(100);
- EXPECT_EQ(0, map.size());
- EXPECT_TRUE(map.empty());
- for (int i = 0; i < 100; i++) {
- EXPECT_FALSE(map.exists(i));
- }
-
- for (int i = 0; i < 100; i++) {
- map.set(i, i);
- EXPECT_EQ(i + 1, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_TRUE(map.exists(i));
- EXPECT_EQ(i, map.get(i));
- }
-
- map.prune(99);
- EXPECT_EQ(1, map.size());
- EXPECT_FALSE(map.empty());
- for (int i = 0; i < 99; i++) {
- EXPECT_FALSE(map.exists(i));
- }
- EXPECT_TRUE(map.exists(99));
- EXPECT_EQ(99, map.get(99));
-
- map.prune(100);
- EXPECT_EQ(0, map.size());
- EXPECT_TRUE(map.empty());
- for (int i = 0; i < 100; i++) {
- EXPECT_FALSE(map.exists(i));
- }
-
- for (int i = 0; i < 100; i++) {
- map.set(i, i);
- EXPECT_EQ(i + 1, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_TRUE(map.exists(i));
- EXPECT_EQ(i, map.get(i));
- }
-
- map.prune(90);
- EXPECT_EQ(10, map.size());
- EXPECT_FALSE(map.empty());
- for (int i = 0; i < 90; i++) {
- EXPECT_FALSE(map.exists(i));
- }
- for (int i = 90; i < 100; i++) {
- EXPECT_TRUE(map.exists(i));
- EXPECT_EQ(i, map.get(i));
- }
-}
-
-TEST(EvictingCacheMap, PruneHookTest) {
- EvictingCacheMap<int, int> map(0);
- EXPECT_EQ(0, map.size());
- EXPECT_TRUE(map.empty());
- for (int i = 0; i < 100; i++) {
- EXPECT_FALSE(map.exists(i));
- }
-
- int sum = 0;
- auto pruneCb = [&](int&& k, int&& v) {
- EXPECT_EQ(k, v);
- sum += k;
- };
-
- map.setPruneHook(pruneCb);
-
- for (int i = 0; i < 100; i++) {
- map.set(i, i);
- EXPECT_EQ(i + 1, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_TRUE(map.exists(i));
- EXPECT_EQ(i, map.get(i));
- }
-
- map.prune(1000000);
- EXPECT_EQ(0, map.size());
- EXPECT_TRUE(map.empty());
- for (int i = 0; i < 100; i++) {
- EXPECT_FALSE(map.exists(i));
- }
- EXPECT_EQ((99 * 100) / 2, sum);
- sum = 0;
-
- for (int i = 0; i < 100; i++) {
- map.set(i, i);
- EXPECT_EQ(i + 1, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_TRUE(map.exists(i));
- EXPECT_EQ(i, map.get(i));
- }
-
- map.prune(100);
- EXPECT_EQ(0, map.size());
- EXPECT_TRUE(map.empty());
- for (int i = 0; i < 100; i++) {
- EXPECT_FALSE(map.exists(i));
- }
- EXPECT_EQ((99 * 100) / 2, sum);
- sum = 0;
-
- for (int i = 0; i < 100; i++) {
- map.set(i, i);
- EXPECT_EQ(i + 1, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_TRUE(map.exists(i));
- EXPECT_EQ(i, map.get(i));
- }
-
- map.prune(99);
- EXPECT_EQ(1, map.size());
- EXPECT_FALSE(map.empty());
- for (int i = 0; i < 99; i++) {
- EXPECT_FALSE(map.exists(i));
- }
- EXPECT_TRUE(map.exists(99));
- EXPECT_EQ(99, map.get(99));
-
- EXPECT_EQ((98 * 99) / 2, sum);
- sum = 0;
-
- map.prune(100);
- EXPECT_EQ(0, map.size());
- EXPECT_TRUE(map.empty());
- for (int i = 0; i < 100; i++) {
- EXPECT_FALSE(map.exists(i));
- }
-
- EXPECT_EQ(99, sum);
- sum = 0;
-
- for (int i = 0; i < 100; i++) {
- map.set(i, i);
- EXPECT_EQ(i + 1, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_TRUE(map.exists(i));
- EXPECT_EQ(i, map.get(i));
- }
-
- map.prune(90);
- EXPECT_EQ(10, map.size());
- EXPECT_FALSE(map.empty());
- for (int i = 0; i < 90; i++) {
- EXPECT_FALSE(map.exists(i));
- }
- for (int i = 90; i < 100; i++) {
- EXPECT_TRUE(map.exists(i));
- EXPECT_EQ(i, map.get(i));
- }
- EXPECT_EQ((89 * 90) / 2, sum);
- sum = 0;
-}
-
-TEST(EvictingCacheMap, SetMaxSize) {
- EvictingCacheMap<int, int> map(100, 20);
- for (int i = 0; i < 90; i++) {
- map.set(i, i);
- EXPECT_TRUE(map.exists(i));
- }
-
- EXPECT_EQ(90, map.size());
- map.setMaxSize(50);
- EXPECT_EQ(map.size(), 50);
-
- for (int i = 0; i < 90; i++) {
- map.set(i, i);
- EXPECT_TRUE(map.exists(i));
- }
- EXPECT_EQ(40, map.size());
- map.setMaxSize(0);
- EXPECT_EQ(40, map.size());
- map.setMaxSize(10);
- EXPECT_EQ(10, map.size());
-}
-
-TEST(EvictingCacheMap, SetClearSize) {
- EvictingCacheMap<int, int> map(100, 20);
- for (int i = 0; i < 90; i++) {
- map.set(i, i);
- EXPECT_TRUE(map.exists(i));
- }
-
- EXPECT_EQ(90, map.size());
- map.setClearSize(40);
- map.setMaxSize(50);
- EXPECT_EQ(map.size(), 50);
-
- for (int i = 0; i < 90; i++) {
- map.set(i, i);
- EXPECT_TRUE(map.exists(i));
- }
- EXPECT_EQ(20, map.size());
- map.setMaxSize(0);
- EXPECT_EQ(20, map.size());
- map.setMaxSize(10);
- EXPECT_EQ(0, map.size());
-}
-
-TEST(EvictingCacheMap, DestructorInvocationTest) {
- struct SumInt {
- SumInt(int val, int* ref) : val(val), ref(ref) { }
- ~SumInt() {
- *ref += val;
- }
- int val;
- int* ref;
- };
-
- int sum;
- EvictingCacheMap<int, SumInt> map(0);
-
- EXPECT_EQ(0, map.size());
- EXPECT_TRUE(map.empty());
- for (int i = 0; i < 100; i++) {
- EXPECT_FALSE(map.exists(i));
- }
-
- for (int i = 0; i < 100; i++) {
- map.set(i, SumInt(i, &sum));
- EXPECT_EQ(i + 1, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_TRUE(map.exists(i));
- EXPECT_EQ(i, map.get(i).val);
- }
-
- sum = 0;
- map.prune(1000000);
- EXPECT_EQ(0, map.size());
- EXPECT_TRUE(map.empty());
- for (int i = 0; i < 100; i++) {
- EXPECT_FALSE(map.exists(i));
- }
- EXPECT_EQ((99 * 100) / 2, sum);
-
- for (int i = 0; i < 100; i++) {
- map.set(i, SumInt(i, &sum));
- EXPECT_EQ(i + 1, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_TRUE(map.exists(i));
- EXPECT_EQ(i, map.get(i).val);
- }
-
- sum = 0;
- map.prune(100);
- EXPECT_EQ(0, map.size());
- EXPECT_TRUE(map.empty());
- for (int i = 0; i < 100; i++) {
- EXPECT_FALSE(map.exists(i));
- }
- EXPECT_EQ((99 * 100) / 2, sum);
-
- for (int i = 0; i < 100; i++) {
- map.set(i, SumInt(i, &sum));
- EXPECT_EQ(i + 1, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_TRUE(map.exists(i));
- EXPECT_EQ(i, map.get(i).val);
- }
-
- sum = 0;
- map.prune(99);
- EXPECT_EQ(1, map.size());
- EXPECT_FALSE(map.empty());
- for (int i = 0; i < 99; i++) {
- EXPECT_FALSE(map.exists(i));
- }
- EXPECT_TRUE(map.exists(99));
- EXPECT_EQ(99, map.get(99).val);
-
- EXPECT_EQ((98 * 99) / 2, sum);
-
- sum = 0;
- map.prune(100);
- EXPECT_EQ(0, map.size());
- EXPECT_TRUE(map.empty());
- for (int i = 0; i < 100; i++) {
- EXPECT_FALSE(map.exists(i));
- }
-
- EXPECT_EQ(99, sum);
- for (int i = 0; i < 100; i++) {
- map.set(i, SumInt(i, &sum));
- EXPECT_EQ(i + 1, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_TRUE(map.exists(i));
- EXPECT_EQ(i, map.get(i).val);
- }
-
- sum = 0;
- map.prune(90);
- EXPECT_EQ(10, map.size());
- EXPECT_FALSE(map.empty());
- for (int i = 0; i < 90; i++) {
- EXPECT_FALSE(map.exists(i));
- }
- for (int i = 90; i < 100; i++) {
- EXPECT_TRUE(map.exists(i));
- EXPECT_EQ(i, map.get(i).val);
- }
- EXPECT_EQ((89 * 90) / 2, sum);
- sum = 0;
-}
-
-TEST(EvictingCacheMap, LruSanityTest) {
- EvictingCacheMap<int, int> map(10);
- EXPECT_EQ(0, map.size());
- EXPECT_TRUE(map.empty());
- for (int i = 0; i < 100; i++) {
- EXPECT_FALSE(map.exists(i));
- }
-
- for (int i = 0; i < 100; i++) {
- map.set(i, i);
- EXPECT_GE(10, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_TRUE(map.exists(i));
- EXPECT_EQ(i, map.get(i));
- }
-
- EXPECT_EQ(10, map.size());
- EXPECT_FALSE(map.empty());
- for (int i = 0; i < 90; i++) {
- EXPECT_FALSE(map.exists(i));
- }
- for (int i = 90; i < 100; i++) {
- EXPECT_TRUE(map.exists(i));
- }
-}
-
-TEST(EvictingCacheMap, LruPromotionTest) {
- EvictingCacheMap<int, int> map(10);
- EXPECT_EQ(0, map.size());
- EXPECT_TRUE(map.empty());
- for (int i = 0; i < 100; i++) {
- EXPECT_FALSE(map.exists(i));
- }
-
- for (int i = 0; i < 100; i++) {
- map.set(i, i);
- EXPECT_GE(10, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_TRUE(map.exists(i));
- EXPECT_EQ(i, map.get(i));
- for (int j = 0; j < std::min(i + 1, 9); j++) {
- EXPECT_TRUE(map.exists(j));
- EXPECT_EQ(j, map.get(j));
- }
- }
-
- EXPECT_EQ(10, map.size());
- EXPECT_FALSE(map.empty());
- for (int i = 0; i < 9; i++) {
- EXPECT_TRUE(map.exists(i));
- }
- EXPECT_TRUE(map.exists(99));
- for (int i = 10; i < 99; i++) {
- EXPECT_FALSE(map.exists(i));
- }
-}
-
-TEST(EvictingCacheMap, LruNoPromotionTest) {
- EvictingCacheMap<int, int> map(10);
- EXPECT_EQ(0, map.size());
- EXPECT_TRUE(map.empty());
- for (int i = 0; i < 100; i++) {
- EXPECT_FALSE(map.exists(i));
- }
-
- for (int i = 0; i < 100; i++) {
- map.set(i, i);
- EXPECT_GE(10, map.size());
- EXPECT_FALSE(map.empty());
- EXPECT_TRUE(map.exists(i));
- EXPECT_EQ(i, map.get(i));
- for (int j = 0; j < std::min(i + 1, 9); j++) {
- if (map.exists(j)) {
- EXPECT_EQ(j, map.getWithoutPromotion(j));
- }
- }
- }
-
- EXPECT_EQ(10, map.size());
- EXPECT_FALSE(map.empty());
- for (int i = 0; i < 90; i++) {
- EXPECT_FALSE(map.exists(i));
- }
- for (int i = 90; i < 100; i++) {
- EXPECT_TRUE(map.exists(i));
- }
-}
-
-TEST(EvictingCacheMap, IteratorSanityTest) {
- const int nItems = 1000;
- EvictingCacheMap<int, int> map(nItems);
- EXPECT_TRUE(map.begin() == map.end());
- for (int i = 0; i < nItems; i++) {
- EXPECT_FALSE(map.exists(i));
- map.set(i, i * 2);
- EXPECT_TRUE(map.exists(i));
- EXPECT_EQ(i * 2, map.get(i));
- }
-
- std::set<int> seen;
- for (auto& it : map) {
- EXPECT_EQ(0, seen.count(it.first));
- seen.insert(it.first);
- EXPECT_EQ(it.first * 2, it.second);
- }
- EXPECT_EQ(nItems, seen.size());
-}
-
-TEST(EvictingCacheMap, FindTest) {
- const int nItems = 1000;
- EvictingCacheMap<int, int> map(nItems);
- for (int i = 0; i < nItems; i++) {
- map.set(i * 2, i * 2);
- EXPECT_TRUE(map.exists(i * 2));
- EXPECT_EQ(i * 2, map.get(i * 2));
- }
- for (int i = 0; i < nItems * 2; i++) {
- if (i % 2 == 0) {
- auto it = map.find(i);
- EXPECT_FALSE(it == map.end());
- EXPECT_EQ(i, it->first);
- EXPECT_EQ(i, it->second);
- } else {
- EXPECT_TRUE( map.find(i) == map.end());
- }
- }
- for (int i = nItems * 2 - 1; i >= 0; i--) {
- if (i % 2 == 0) {
- auto it = map.find(i);
- EXPECT_FALSE(it == map.end());
- EXPECT_EQ(i, it->first);
- EXPECT_EQ(i, it->second);
- } else {
- EXPECT_TRUE(map.find(i) == map.end());
- }
- }
- EXPECT_EQ(0, map.begin()->first);
-}
-
-TEST(EvictingCacheMap, FindWithoutPromotionTest) {
- const int nItems = 1000;
- EvictingCacheMap<int, int> map(nItems);
- for (int i = 0; i < nItems; i++) {
- map.set(i * 2, i * 2);
- EXPECT_TRUE(map.exists(i * 2));
- EXPECT_EQ(i * 2, map.get(i * 2));
- }
- for (int i = nItems * 2 - 1; i >= 0; i--) {
- if (i % 2 == 0) {
- auto it = map.findWithoutPromotion(i);
- EXPECT_FALSE(it == map.end());
- EXPECT_EQ(i, it->first);
- EXPECT_EQ(i, it->second);
- } else {
- EXPECT_TRUE(map.findWithoutPromotion(i) == map.end());
- }
- }
- EXPECT_EQ((nItems - 1) * 2, map.begin()->first);
-}
-
-TEST(EvictingCacheMap, IteratorOrderingTest) {
- const int nItems = 1000;
- EvictingCacheMap<int, int> map(nItems);
- for (int i = 0; i < nItems; i++) {
- map.set(i, i);
- EXPECT_TRUE(map.exists(i));
- EXPECT_EQ(i, map.get(i));
- }
-
- int expected = nItems - 1;
- for (auto it = map.begin(); it != map.end(); ++it) {
- EXPECT_EQ(expected, it->first);
- expected--;
- }
-
- expected = 0;
- for (auto it = map.rbegin(); it != map.rend(); ++it) {
- EXPECT_EQ(expected, it->first);
- expected++;
- }
-
- {
- auto it = map.end();
- expected = 0;
- EXPECT_TRUE(it != map.begin());
- do {
- --it;
- EXPECT_EQ(expected, it->first);
- expected++;
- } while (it != map.begin());
- EXPECT_EQ(nItems, expected);
- }
-
- {
- auto it = map.rend();
- expected = nItems - 1;
- do {
- --it;
- EXPECT_EQ(expected, it->first);
- expected--;
- } while (it != map.rbegin());
- EXPECT_EQ(-1, expected);
- }
-}
-
-TEST(EvictingCacheMap, MoveTest) {
- const int nItems = 1000;
- EvictingCacheMap<int, int> map(nItems);
- for (int i = 0; i < nItems; i++) {
- map.set(i, i);
- EXPECT_TRUE(map.exists(i));
- EXPECT_EQ(i, map.get(i));
- }
-
- EvictingCacheMap<int, int> map2 = std::move(map);
- EXPECT_TRUE(map.empty());
- for (int i = 0; i < nItems; i++) {
- EXPECT_TRUE(map2.exists(i));
- EXPECT_EQ(i, map2.get(i));
- }
-}
#include <boost/random.hpp>
#include <folly/Benchmark.h>
-#include <folly/Foreach.h>
#include <folly/Random.h>
+#include <folly/container/Foreach.h>
#include <folly/portability/GFlags.h>
using namespace std;
#include <boost/random.hpp>
#include <folly/Conv.h>
-#include <folly/Foreach.h>
#include <folly/Portability.h>
#include <folly/Random.h>
+#include <folly/container/Foreach.h>
#include <folly/portability/GTest.h>
using namespace std;
#include <folly/Benchmark.h>
#include <folly/FBString.h>
#include <folly/FBVector.h>
-#include <folly/Foreach.h>
#include <folly/Random.h>
#include <folly/Traits.h>
+#include <folly/container/Foreach.h>
#include <folly/portability/GFlags.h>
#include <folly/portability/GTest.h>
#include <boost/random.hpp>
#include <folly/FBString.h>
-#include <folly/Foreach.h>
#include <folly/Random.h>
#include <folly/Traits.h>
+#include <folly/container/Foreach.h>
#include <folly/portability/GTest.h>
using namespace std;
+++ /dev/null
-/*
- * Copyright 2017 Facebook, Inc.
- *
- * 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
- *
- * http://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 <folly/Foreach.h>
-
-#include <folly/Benchmark.h>
-#include <folly/portability/GTest.h>
-
-#include <map>
-
-using namespace folly;
-using namespace folly::detail;
-
-// Benchmarks:
-// 1. Benchmark iterating through the man with FOR_EACH, and also assign
-// iter->first and iter->second to local vars inside the FOR_EACH loop.
-// 2. Benchmark iterating through the man with FOR_EACH, but use iter->first and
-// iter->second as is, without assigning to local variables.
-// 3. Use FOR_EACH_KV loop to iterate through the map.
-
-std::map<int, std::string> bmMap; // For use in benchmarks below.
-std::vector<int> vec_one;
-std::vector<int> vec_two;
-
-void setupBenchmark(size_t iters) {
- bmMap.clear();
- for (size_t i = 0; i < iters; ++i) {
- bmMap[i] = "teststring";
- }
-
- vec_one.clear();
- vec_two.clear();
- vec_one.resize(iters);
- vec_two.resize(iters);
-}
-
-BENCHMARK(ForEachFunctionNoAssign, iters) {
- BenchmarkSuspender suspender;
-
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
-
- suspender.dismissing([&]() {
- folly::for_each(bmMap, [&](auto& key_val_pair) {
- sumKeys += key_val_pair.first;
- sumValues += key_val_pair.second;
- });
- doNotOptimizeAway(sumKeys);
- });
-}
-
-BENCHMARK(StdForEachFunctionNoAssign, iters) {
- BenchmarkSuspender suspender;
-
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
-
- suspender.dismissing([&]() {
- std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
- sumKeys += key_val_pair.first;
- sumValues += key_val_pair.second;
- });
- doNotOptimizeAway(sumKeys);
- });
-}
-
-BENCHMARK(RangeBasedForLoopNoAssign, iters) {
- BenchmarkSuspender suspender;
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
-
- suspender.dismissing([&]() {
- for (auto& key_val_pair : bmMap) {
- sumKeys += key_val_pair.first;
- sumValues += key_val_pair.second;
- }
- doNotOptimizeAway(sumKeys);
- });
-}
-
-BENCHMARK(ManualLoopNoAssign, iters) {
- BenchmarkSuspender suspender;
-
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
-
- suspender.dismissing([&]() {
- for (auto iter = bmMap.begin(); iter != bmMap.end(); ++iter) {
- sumKeys += iter->first;
- sumValues += iter->second;
- }
- doNotOptimizeAway(sumKeys);
- });
-}
-
-BENCHMARK(ForEachFunctionAssign, iters) {
- BenchmarkSuspender suspender;
-
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
-
- suspender.dismissing([&]() {
- folly::for_each(bmMap, [&](auto& key_val_pair) {
- const int k = key_val_pair.first;
- const std::string v = key_val_pair.second;
- sumKeys += k;
- sumValues += v;
- });
- });
-}
-
-BENCHMARK(StdForEachFunctionAssign, iters) {
- BenchmarkSuspender suspender;
-
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
-
- suspender.dismissing([&]() {
- std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
- const int k = key_val_pair.first;
- const std::string v = key_val_pair.second;
- sumKeys += k;
- sumValues += v;
- });
- });
-}
-
-BENCHMARK(RangeBasedForLoopAssign, iters) {
- BenchmarkSuspender suspender;
-
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
-
- suspender.dismissing([&]() {
- for (auto& key_val_pair : bmMap) {
- const int k = key_val_pair.first;
- const std::string v = key_val_pair.second;
- sumKeys += k;
- sumValues += v;
- }
- });
-}
-
-BENCHMARK(ManualLoopAssign, iters) {
- BenchmarkSuspender suspender;
-
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
-
- suspender.dismissing([&]() {
- for (auto iter = bmMap.begin(); iter != bmMap.end(); ++iter) {
- const int k = iter->first;
- const std::string v = iter->second;
- sumKeys += k;
- sumValues += v;
- }
- });
-}
-
-BENCHMARK(ForEachFunctionNoAssignWithIndexManipulation, iters) {
- BenchmarkSuspender suspender;
-
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
-
- suspender.dismissing([&]() {
- folly::for_each(bmMap, [&](auto& key_val_pair, auto index) {
- sumKeys += key_val_pair.first;
- sumValues += key_val_pair.second;
- sumValues += index;
- });
- });
-}
-
-BENCHMARK(StdForEachFunctionNoAssignWithIndexManipulation, iters) {
- BenchmarkSuspender suspender;
-
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
-
- suspender.dismissing([&]() {
- auto index = std::size_t{0};
- std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
- sumKeys += key_val_pair.first;
- sumValues += key_val_pair.second;
- sumValues += index;
- ++index;
- });
- });
-}
-
-BENCHMARK(RangeBasedForLoopNoAssignWithIndexManipulation, iters) {
- BenchmarkSuspender suspender;
-
- int sumKeys = 0;
- std::string sumValues;
- setupBenchmark(iters);
-
- suspender.dismissing([&]() {
- auto index = std::size_t{0};
- for (auto& key_val_pair : bmMap) {
- sumKeys += key_val_pair.first;
- sumValues += key_val_pair.second;
- sumValues += index;
- }
- });
-}
-
-BENCHMARK(ForEachFunctionFetch, iters) {
- BenchmarkSuspender suspender;
- setupBenchmark(iters);
-
- suspender.dismissing([&]() {
- folly::for_each(bmMap, [&](auto& key_val_pair, auto index) {
- folly::fetch(vec_one, index) = key_val_pair.first;
- });
- });
-}
-
-BENCHMARK(StdForEachFunctionFetch, iters) {
- BenchmarkSuspender suspender;
- setupBenchmark(iters);
-
- suspender.dismissing([&]() {
- auto index = std::size_t{0};
- std::for_each(bmMap.begin(), bmMap.end(), [&](auto& key_val_pair) {
- *(vec_one.begin() + index++) = key_val_pair.first;
- });
- });
-}
-
-BENCHMARK(ForLoopFetch, iters) {
- BenchmarkSuspender suspender;
- setupBenchmark(iters);
-
- suspender.dismissing([&]() {
- auto index = std::size_t{0};
- for (auto& key_val_pair : bmMap) {
- *(vec_one.begin() + index++) = key_val_pair.first;
- }
- });
-}
-
-BENCHMARK(ForEachKVNoMacroAssign, iters) {
- int sumKeys = 0;
- std::string sumValues;
-
- BENCHMARK_SUSPEND { setupBenchmark(iters); }
-
- FOR_EACH(iter, bmMap) {
- const int k = iter->first;
- const std::string v = iter->second;
- sumKeys += k;
- sumValues += v;
- }
-}
-
-BENCHMARK(ForEachKVNoMacroNoAssign, iters) {
- int sumKeys = 0;
- std::string sumValues;
-
- BENCHMARK_SUSPEND { setupBenchmark(iters); }
-
- FOR_EACH(iter, bmMap) {
- sumKeys += iter->first;
- sumValues += iter->second;
- }
-}
-
-BENCHMARK(ForEachKVMacro, iters) {
- int sumKeys = 0;
- std::string sumValues;
-
- BENCHMARK_SUSPEND { setupBenchmark(iters); }
-
- FOR_EACH_KV(k, v, bmMap) {
- sumKeys += k;
- sumValues += v;
- }
-}
-
-BENCHMARK(ForEachManual, iters) {
- int sum = 1;
- for (size_t i = 1; i < iters; ++i) {
- sum *= i;
- }
- doNotOptimizeAway(sum);
-}
-
-BENCHMARK(ForEachRange, iters) {
- int sum = 1;
- FOR_EACH_RANGE(i, 1, iters) { sum *= i; }
- doNotOptimizeAway(sum);
-}
-
-BENCHMARK(ForEachDescendingManual, iters) {
- int sum = 1;
- for (size_t i = iters; i-- > 1;) {
- sum *= i;
- }
- doNotOptimizeAway(sum);
-}
-
-BENCHMARK(ForEachRangeR, iters) {
- int sum = 1;
- FOR_EACH_RANGE_R(i, 1U, iters) { sum *= i; }
- doNotOptimizeAway(sum);
-}
-
-int main(int argc, char** argv) {
- testing::InitGoogleTest(&argc, argv);
- gflags::ParseCommandLineFlags(&argc, &argv, true);
- auto r = RUN_ALL_TESTS();
- if (r) {
- return r;
- }
- runBenchmarks();
- return 0;
-}
+++ /dev/null
-/*
- * Copyright 2017 Facebook, Inc.
- *
- * 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
- *
- * http://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 <folly/Foreach.h>
-
-#include <array>
-#include <initializer_list>
-#include <iterator>
-#include <list>
-#include <map>
-#include <string>
-#include <tuple>
-#include <vector>
-
-#include <folly/portability/GTest.h>
-
-using namespace folly;
-using namespace folly::detail;
-
-namespace folly {
-namespace test {
-
-class TestRValueConstruct {
- public:
- TestRValueConstruct() = default;
- TestRValueConstruct(TestRValueConstruct&&) noexcept {
- this->constructed_from_rvalue = true;
- }
- TestRValueConstruct(const TestRValueConstruct&) {
- this->constructed_from_rvalue = false;
- }
- TestRValueConstruct& operator=(const TestRValueConstruct&) = delete;
- TestRValueConstruct& operator=(TestRValueConstruct&&) = delete;
-
- bool constructed_from_rvalue{false};
-};
-
-class TestAdlIterable {
- public:
- std::vector<int> vec{0, 1, 2, 3};
-};
-
-auto begin(TestAdlIterable& instance) {
- return instance.vec.begin();
-}
-auto begin(const TestAdlIterable& instance) {
- return instance.vec.begin();
-}
-auto end(TestAdlIterable& instance) {
- return instance.vec.end();
-}
-auto end(const TestAdlIterable& instance) {
- return instance.vec.end();
-}
-
-class TestBothIndexingAndIter {
- public:
- class Iterator {
- public:
- using difference_type = std::size_t;
- using value_type = int;
- using pointer = int*;
- using reference = int&;
- using iterator_category = std::random_access_iterator_tag;
- int& operator*() {
- return this->val;
- }
- Iterator operator+(int) {
- return *this;
- }
- explicit Iterator(int& val_in) : val{val_in} {}
- int& val;
- };
- auto begin() {
- this->called_begin = true;
- return Iterator{val};
- }
- auto end() {
- return Iterator{val};
- }
- int& operator[](int) {
- return this->val;
- }
-
- int val{0};
- bool called_begin = false;
-};
-} // namespace test
-} // namespace folly
-
-TEST(Foreach, ForEachFunctionBasic) {
- auto range = std::make_tuple(1, 2, 3);
- auto result_range = std::vector<int>{};
- auto correct_result_range = std::vector<int>{1, 2, 3};
-
- folly::for_each(range, [&](auto ele) { result_range.push_back(ele); });
-
- EXPECT_TRUE(std::equal(
- result_range.begin(), result_range.end(), correct_result_range.begin()));
-}
-
-TEST(Foreach, ForEachFunctionBasicRuntimeOneArg) {
- auto range = std::vector<int>{1, 2, 3};
- auto current = 0;
- folly::for_each(range, [&](auto ele) {
- if (current == 0) {
- EXPECT_EQ(ele, 1);
- } else if (current == 1) {
- EXPECT_EQ(ele, 2);
- } else {
- EXPECT_EQ(ele, 3);
- }
- ++current;
- });
-}
-
-TEST(Foreach, ForEachFunctionBasicRuntimeTwoArg) {
- auto range = std::vector<int>{1, 2, 3};
- folly::for_each(range, [](auto ele, auto index) {
- EXPECT_TRUE(index < 3);
- if (index == 0) {
- EXPECT_EQ(ele, 1);
- } else if (index == 1) {
- EXPECT_EQ(ele, 2);
- } else if (index == 2) {
- EXPECT_EQ(ele, 3);
- }
- });
-}
-
-TEST(Foreach, ForEachFunctionBasicRuntimeThreeArg) {
- auto range = std::list<int>{1, 2, 3};
- auto result_range = std::list<int>{1, 3};
- folly::for_each(range, [&](auto ele, auto, auto iter) {
- if (ele == 2) {
- range.erase(iter);
- }
- });
- EXPECT_TRUE(std::equal(range.begin(), range.end(), result_range.begin()));
-}
-
-TEST(Foreach, ForEachFunctionBasicTupleOneArg) {
- auto range = std::make_tuple(1, 2, 3);
- auto current = 0;
- folly::for_each(range, [&](auto ele) {
- if (current == 0) {
- EXPECT_EQ(ele, 1);
- } else if (current == 1) {
- EXPECT_EQ(ele, 2);
- } else {
- EXPECT_EQ(ele, 3);
- }
- ++current;
- });
-}
-
-TEST(Foreach, ForEachFunctionBasicTupleTwoArg) {
- auto range = std::make_tuple(1, 2, 3);
- folly::for_each(range, [](auto ele, auto index) {
- EXPECT_TRUE(index < 3);
- if (index == 0) {
- EXPECT_EQ(ele, 1);
- } else if (index == 1) {
- EXPECT_EQ(ele, 2);
- } else if (index == 2) {
- EXPECT_EQ(ele, 3);
- }
- });
-}
-
-TEST(Foreach, ForEachFunctionBreakRuntimeOneArg) {
- auto range = std::vector<int>{1, 2, 3};
- auto iterations = 0;
- folly::for_each(range, [&](auto) {
- ++iterations;
- if (iterations == 1) {
- return folly::loop_break;
- }
- return folly::loop_continue;
- });
- EXPECT_EQ(iterations, 1);
-}
-
-TEST(Foreach, ForEachFunctionBreakRuntimeTwoArg) {
- auto range = std::vector<int>{1, 2, 3};
- auto iterations = 0;
- folly::for_each(range, [&](auto, auto index) {
- ++iterations;
- if (index == 1) {
- return folly::loop_break;
- }
- return folly::loop_continue;
- });
- EXPECT_EQ(iterations, 2);
-}
-
-TEST(Foreach, ForEachFunctionBreakRuntimeThreeArg) {
- auto range = std::vector<int>{1, 2, 3};
- auto iterations = 0;
- folly::for_each(range, [&](auto, auto index, auto) {
- ++iterations;
- if (index == 1) {
- return folly::loop_break;
- }
- return folly::loop_continue;
- });
- EXPECT_EQ(iterations, 2);
-}
-
-TEST(Foreach, ForEachFunctionBreakTupleOneArg) {
- auto range = std::vector<int>{1, 2, 3};
- auto iterations = 0;
- folly::for_each(range, [&](auto) {
- ++iterations;
- if (iterations == 1) {
- return folly::loop_break;
- }
- return folly::loop_continue;
- });
- EXPECT_EQ(iterations, 1);
-}
-
-TEST(Foreach, ForEachFunctionBreakTupleTwoArg) {
- auto range = std::vector<int>{1, 2, 3};
- auto iterations = 0;
- folly::for_each(range, [&](auto, auto index) {
- ++iterations;
- if (index == 1) {
- return folly::loop_break;
- }
- return folly::loop_continue;
- });
- EXPECT_EQ(iterations, 2);
-}
-
-TEST(Foreach, ForEachFunctionArray) {
- auto range = std::array<int, 3>{{1, 2, 3}};
- auto iterations = 0;
- folly::for_each(range, [&](auto, auto index) {
- ++iterations;
- if (index == 1) {
- return folly::loop_break;
- }
- return folly::loop_continue;
- });
- EXPECT_EQ(iterations, 2);
-}
-
-TEST(Foreach, ForEachFunctionInitializerListBasic) {
- folly::for_each(std::initializer_list<int>{1, 2, 3}, [](auto ele) { ++ele; });
-}
-
-TEST(Foreach, ForEachFunctionTestForward) {
- using folly::test::TestRValueConstruct;
- auto range_one = std::vector<TestRValueConstruct>{};
- range_one.resize(3);
-
- folly::for_each(std::move(range_one), [](auto ele) {
- EXPECT_FALSE(ele.constructed_from_rvalue);
- });
-
- folly::for_each(
- std::make_tuple(TestRValueConstruct{}, TestRValueConstruct{}),
- [](auto ele) { EXPECT_TRUE(ele.constructed_from_rvalue); });
-}
-
-TEST(Foreach, ForEachFunctionAdlIterable) {
- auto range = test::TestAdlIterable{};
- auto iterations = 0;
- folly::for_each(range, [&](auto ele, auto index) {
- ++iterations;
- EXPECT_EQ(ele, index);
- });
- EXPECT_EQ(iterations, 4);
-}
-
-TEST(ForEach, FetchRandomAccessIterator) {
- auto vec = std::vector<int>{1, 2, 3};
- auto& second = folly::fetch(vec, 1);
- EXPECT_EQ(second, 2);
- second = 3;
- EXPECT_EQ(second, 3);
-}
-
-TEST(ForEach, FetchIndexing) {
- auto mp = std::map<int, int>{{1, 2}};
- auto& ele = folly::fetch(mp, 1);
- EXPECT_EQ(ele, 2);
- ele = 3;
- EXPECT_EQ(ele, 3);
-}
-
-TEST(ForEach, FetchTuple) {
- auto mp = std::make_tuple(1, 2, 3);
- auto& ele = folly::fetch(mp, std::integral_constant<int, 1>{});
- EXPECT_EQ(ele, 2);
- ele = 3;
- EXPECT_EQ(ele, 3);
-}
-
-TEST(ForEach, FetchTestPreferIterator) {
- auto range = test::TestBothIndexingAndIter{};
- auto& ele = folly::fetch(range, 0);
- EXPECT_TRUE(range.called_begin);
- EXPECT_EQ(ele, 0);
- ele = 2;
- EXPECT_EQ(folly::fetch(range, 0), 2);
-}
-
-TEST(Foreach, ForEachRvalue) {
- const char* const hello = "hello";
- int n = 0;
- FOR_EACH(it, std::string(hello)) {
- ++n;
- }
- EXPECT_EQ(strlen(hello), n);
- FOR_EACH_R(it, std::string(hello)) {
- --n;
- EXPECT_EQ(hello[n], *it);
- }
- EXPECT_EQ(0, n);
-}
-
-TEST(Foreach, ForEachNested) {
- const std::string hello = "hello";
- size_t n = 0;
- FOR_EACH(i, hello) {
- FOR_EACH(j, hello) {
- ++n;
- }
- }
- auto len = hello.size();
- EXPECT_EQ(len * len, n);
-}
-
-TEST(Foreach, ForEachKV) {
- std::map<std::string, int> testMap;
- testMap["abc"] = 1;
- testMap["def"] = 2;
- std::string keys = "";
- int values = 0;
- int numEntries = 0;
- FOR_EACH_KV (key, value, testMap) {
- keys += key;
- values += value;
- ++numEntries;
- }
- EXPECT_EQ("abcdef", keys);
- EXPECT_EQ(3, values);
- EXPECT_EQ(2, numEntries);
-}
-
-TEST(Foreach, ForEachKVBreak) {
- std::map<std::string, int> testMap;
- testMap["abc"] = 1;
- testMap["def"] = 2;
- std::string keys = "";
- int values = 0;
- int numEntries = 0;
- FOR_EACH_KV (key, value, testMap) {
- keys += key;
- values += value;
- ++numEntries;
- break;
- }
- EXPECT_EQ("abc", keys);
- EXPECT_EQ(1, values);
- EXPECT_EQ(1, numEntries);
-}
-
-TEST(Foreach, ForEachKvWithMultiMap) {
- std::multimap<std::string, int> testMap;
- testMap.insert(std::make_pair("abc", 1));
- testMap.insert(std::make_pair("abc", 2));
- testMap.insert(std::make_pair("def", 3));
- std::string keys = "";
- int values = 0;
- int numEntries = 0;
- FOR_EACH_KV (key, value, testMap) {
- keys += key;
- values += value;
- ++numEntries;
- }
- EXPECT_EQ("abcabcdef", keys);
- EXPECT_EQ(6, values);
- EXPECT_EQ(3, numEntries);
-}
-
-TEST(Foreach, ForEachEnumerate) {
- std::vector<int> vv;
- int sumAA = 0;
- int sumIter = 0;
- int numIterations = 0;
- FOR_EACH_ENUMERATE(aa, iter, vv) {
- sumAA += aa;
- sumIter += *iter;
- ++numIterations;
- }
- EXPECT_EQ(sumAA, 0);
- EXPECT_EQ(sumIter, 0);
- EXPECT_EQ(numIterations, 0);
-
- vv.push_back(1);
- vv.push_back(3);
- vv.push_back(5);
- FOR_EACH_ENUMERATE(aa, iter, vv) {
- sumAA += aa;
- sumIter += *iter;
- ++numIterations;
- }
- EXPECT_EQ(sumAA, 3); // 0 + 1 + 2
- EXPECT_EQ(sumIter, 9); // 1 + 3 + 5
- EXPECT_EQ(numIterations, 3);
-}
-
-TEST(Foreach, ForEachEnumerateBreak) {
- std::vector<int> vv;
- int sumAA = 0;
- int sumIter = 0;
- int numIterations = 0;
- vv.push_back(1);
- vv.push_back(2);
- vv.push_back(4);
- vv.push_back(8);
- FOR_EACH_ENUMERATE(aa, iter, vv) {
- sumAA += aa;
- sumIter += *iter;
- ++numIterations;
- if (aa == 1) {
- break;
- }
- }
- EXPECT_EQ(sumAA, 1); // 0 + 1
- EXPECT_EQ(sumIter, 3); // 1 + 2
- EXPECT_EQ(numIterations, 2);
-}
-
-TEST(Foreach, ForEachRangeR) {
- int sum = 0;
-
- FOR_EACH_RANGE_R (i, 0, 0) {
- sum += i;
- }
- EXPECT_EQ(0, sum);
-
- FOR_EACH_RANGE_R (i, 0, -1) {
- sum += i;
- }
- EXPECT_EQ(0, sum);
-
- FOR_EACH_RANGE_R (i, 0, 5) {
- sum += i;
- }
- EXPECT_EQ(10, sum);
-
- std::list<int> lst = { 0, 1, 2, 3, 4 };
- sum = 0;
- FOR_EACH_RANGE_R (i, lst.begin(), lst.end()) {
- sum += *i;
- }
- EXPECT_EQ(10, sum);
-}
+++ /dev/null
-/*
- * Copyright 2017 Facebook, Inc.
- *
- * 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
- *
- * http://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 <algorithm>
-#include <cassert>
-#include <cstddef>
-#include <deque>
-#include <functional>
-#include <map>
-#include <set>
-#include <tuple>
-#include <type_traits>
-#include <utility>
-#include <vector>
-
-#include <folly/Iterator.h>
-#include <folly/portability/GTest.h>
-
-namespace {
-/**
- * Container type used for unit tests.
- */
-template <typename T>
-using Container = std::deque<T>;
-
-// Constructor and assignment operator call counters for struct Object.
-std::size_t gDefaultCtrCnt;
-std::size_t gCopyCtrCnt;
-std::size_t gMoveCtrCnt;
-std::size_t gExplicitCtrCnt;
-std::size_t gMultiargCtrCnt;
-std::size_t gCopyOpCnt;
-std::size_t gMoveOpCnt;
-std::size_t gConvertOpCnt;
-
-/**
- * Class that increases various counters to keep track of how objects have
- * been constructed or assigned to, to verify iterator behavior.
- */
-struct Object {
- Object() {
- ++gDefaultCtrCnt;
- }
- Object(const Object&) {
- ++gCopyCtrCnt;
- }
- Object(Object&&) noexcept {
- ++gMoveCtrCnt;
- }
- explicit Object(int) {
- ++gExplicitCtrCnt;
- }
- explicit Object(int, int) {
- ++gMultiargCtrCnt;
- }
- Object& operator=(const Object&) {
- ++gCopyOpCnt;
- return *this;
- }
- Object& operator=(Object&&) noexcept {
- ++gMoveOpCnt;
- return *this;
- }
- Object& operator=(int) noexcept {
- ++gConvertOpCnt;
- return *this;
- }
-};
-
-/**
- * Reset all call counters to 0.
- */
-void init_counters() {
- gDefaultCtrCnt = gCopyCtrCnt = gMoveCtrCnt = gExplicitCtrCnt =
- gMultiargCtrCnt = gCopyOpCnt = gMoveOpCnt = gConvertOpCnt = 0;
-}
-
-/**
- * Test for iterator copy and move.
- */
-template <typename Iterator>
-void copy_and_move_test(Container<int>& q, Iterator it) {
- assert(q.empty());
- const auto it2(it); // copy construct
- it = it2; // copy assign from const
- it = it; // self assign
- auto it3(std::move(it)); // move construct
- it = std::move(it3); // move assign
- // Make sure iterator still works.
- it = 4711; // emplace
- EXPECT_EQ(q, Container<int>{4711});
-}
-
-/**
- * Test for emplacement with perfect forwarding.
- */
-template <typename Iterator>
-void emplace_test(Container<Object>& q, Iterator it) {
- using folly::make_emplace_args;
- assert(q.empty());
- init_counters();
- it = Object{}; // default construct + move construct
- Object obj; // default construct
- it = obj; // copy construct
- it = std::move(obj); // move construct
- const Object obj2; // default construct
- it = obj2; // copy construct from const
- it = std::move(obj2); // copy construct (const defeats move)
- it = 0; // explicit construct
- it = make_emplace_args(0, 0); // explicit multiarg construct
- it = std::make_pair(0, 0); // implicit multiarg construct
- it = std::make_tuple(0, 0); // implicit multiarg construct
- auto args = make_emplace_args(Object{}); // default construct + move construct
- it = args; // copy construct
- it = const_cast<const decltype(args)&>(args); // copy construct from const
- it = std::move(args); // move construct
- auto args2 = std::make_tuple(Object{}); // default construct + move construct
- it = args2; // (implicit multiarg) copy construct
- it = std::move(args2); // (implicit multiarg) move construct
- auto args3 = std::make_pair(0, 0);
- it = args3; // implicit multiarg construct
- it = std::move(args3); // implicit multiarg construct
- ASSERT_EQ(q.size(), 16);
- EXPECT_EQ(gDefaultCtrCnt, 5);
- EXPECT_EQ(gCopyCtrCnt, 6);
- EXPECT_EQ(gMoveCtrCnt, 6);
- EXPECT_EQ(gExplicitCtrCnt, 1);
- EXPECT_EQ(gMultiargCtrCnt, 5);
- EXPECT_EQ(gCopyOpCnt, 0);
- EXPECT_EQ(gMoveOpCnt, 0);
- EXPECT_EQ(gConvertOpCnt, 0);
-}
-}
-
-using namespace folly;
-
-/**
- * Basic tests for folly::emplace_iterator.
- */
-TEST(EmplaceIterator, EmplacerTest) {
- {
- Container<int> q;
- copy_and_move_test(q, emplacer(q, q.begin()));
- }
- {
- Container<Object> q;
- emplace_test(q, emplacer(q, q.begin()));
- }
- {
- Container<int> q;
- auto it = emplacer(q, q.begin());
- it = 0;
- it = 1;
- it = 2;
- it = emplacer(q, q.begin());
- it = 3;
- it = 4;
- EXPECT_EQ(q, Container<int>({3, 4, 0, 1, 2}));
- }
-}
-
-/**
- * Basic tests for folly::front_emplace_iterator.
- */
-TEST(EmplaceIterator, FrontEmplacerTest) {
- {
- Container<int> q;
- copy_and_move_test(q, front_emplacer(q));
- }
- {
- Container<Object> q;
- emplace_test(q, front_emplacer(q));
- }
- {
- Container<int> q;
- auto it = front_emplacer(q);
- it = 0;
- it = 1;
- it = 2;
- it = front_emplacer(q);
- it = 3;
- it = 4;
- EXPECT_EQ(q, Container<int>({4, 3, 2, 1, 0}));
- }
-}
-
-/**
- * Basic tests for folly::back_emplace_iterator.
- */
-TEST(EmplaceIterator, BackEmplacerTest) {
- {
- Container<int> q;
- copy_and_move_test(q, back_emplacer(q));
- }
- {
- Container<Object> q;
- emplace_test(q, back_emplacer(q));
- }
- {
- Container<int> q;
- auto it = back_emplacer(q);
- it = 0;
- it = 1;
- it = 2;
- it = back_emplacer(q);
- it = 3;
- it = 4;
- EXPECT_EQ(q, Container<int>({0, 1, 2, 3, 4}));
- }
-}
-
-/**
- * Basic tests for folly::hint_emplace_iterator.
- */
-TEST(EmplaceIterator, HintEmplacerTest) {
- {
- init_counters();
- std::map<int, Object> m;
- auto it = hint_emplacer(m, m.end());
- it = make_emplace_args(
- std::piecewise_construct,
- std::forward_as_tuple(0),
- std::forward_as_tuple(0));
- it = make_emplace_args(
- std::piecewise_construct,
- std::forward_as_tuple(1),
- std::forward_as_tuple(0, 0));
- it = make_emplace_args(
- std::piecewise_construct,
- std::forward_as_tuple(2),
- std::forward_as_tuple(Object{}));
- ASSERT_EQ(m.size(), 3);
- EXPECT_EQ(gDefaultCtrCnt, 1);
- EXPECT_EQ(gCopyCtrCnt, 0);
- EXPECT_EQ(gMoveCtrCnt, 1);
- EXPECT_EQ(gExplicitCtrCnt, 1);
- EXPECT_EQ(gMultiargCtrCnt, 1);
- EXPECT_EQ(gCopyOpCnt, 0);
- EXPECT_EQ(gMoveOpCnt, 0);
- EXPECT_EQ(gConvertOpCnt, 0);
- }
- {
- struct O {
- explicit O(int i) : i(i) {}
- bool operator<(const O& other) const {
- return i < other.i;
- }
- bool operator==(const O& other) const {
- return i == other.i;
- }
- int i;
- };
- std::vector<int> v1 = {0, 1, 2, 3, 4};
- std::vector<int> v2 = {0, 2, 4};
- std::set<O> diff;
- std::set_difference(
- v1.begin(),
- v1.end(),
- v2.begin(),
- v2.end(),
- hint_emplacer(diff, diff.end()));
- ASSERT_EQ(diff, std::set<O>({O(1), O(3)}));
- }
-}
-
-/**
- * Test std::copy() with explicit conversion. This would not compile with a
- * std::back_insert_iterator, because the constructor of Object that takes a
- * single int is explicit.
- */
-TEST(EmplaceIterator, Copy) {
- init_counters();
- Container<int> in({0, 1, 2});
- Container<Object> out;
- std::copy(in.begin(), in.end(), back_emplacer(out));
- EXPECT_EQ(3, out.size());
- EXPECT_EQ(gDefaultCtrCnt, 0);
- EXPECT_EQ(gCopyCtrCnt, 0);
- EXPECT_EQ(gMoveCtrCnt, 0);
- EXPECT_EQ(gExplicitCtrCnt, 3);
- EXPECT_EQ(gMultiargCtrCnt, 0);
- EXPECT_EQ(gCopyOpCnt, 0);
- EXPECT_EQ(gMoveOpCnt, 0);
- EXPECT_EQ(gConvertOpCnt, 0);
-}
-
-/**
- * Test std::transform() with multi-argument constructors. This would require
- * a temporary Object with std::back_insert_iterator.
- */
-TEST(EmplaceIterator, Transform) {
- init_counters();
- Container<int> in({0, 1, 2});
- Container<Object> out;
- std::transform(in.begin(), in.end(), back_emplacer(out), [](int i) {
- return make_emplace_args(i, i);
- });
- EXPECT_EQ(3, out.size());
- EXPECT_EQ(gDefaultCtrCnt, 0);
- EXPECT_EQ(gCopyCtrCnt, 0);
- EXPECT_EQ(gMoveCtrCnt, 0);
- EXPECT_EQ(gExplicitCtrCnt, 0);
- EXPECT_EQ(gMultiargCtrCnt, 3);
- EXPECT_EQ(gCopyOpCnt, 0);
- EXPECT_EQ(gMoveOpCnt, 0);
- EXPECT_EQ(gConvertOpCnt, 0);
-}
-
-/**
- * Test multi-argument store and forward.
- */
-TEST(EmplaceIterator, EmplaceArgs) {
- Object o1;
- const Object o2;
- Object& o3 = o1;
- const Object& o4 = o3;
- Object o5;
-
- {
- // Test copy construction.
- auto args = make_emplace_args(0, o1, o2, o3, o4, Object{}, std::cref(o2));
- init_counters();
- auto args2 = args;
- EXPECT_EQ(gDefaultCtrCnt, 0);
- EXPECT_EQ(gCopyCtrCnt, 5);
- EXPECT_EQ(gMoveCtrCnt, 0);
- EXPECT_EQ(gExplicitCtrCnt, 0);
- EXPECT_EQ(gMultiargCtrCnt, 0);
- EXPECT_EQ(gCopyOpCnt, 0);
- EXPECT_EQ(gMoveOpCnt, 0);
- EXPECT_EQ(gConvertOpCnt, 0);
-
- // Test copy assignment.
- init_counters();
- args = args2;
- EXPECT_EQ(gDefaultCtrCnt, 0);
- EXPECT_EQ(gCopyCtrCnt, 0);
- EXPECT_EQ(gMoveCtrCnt, 0);
- EXPECT_EQ(gExplicitCtrCnt, 0);
- EXPECT_EQ(gMultiargCtrCnt, 0);
- EXPECT_EQ(gCopyOpCnt, 5);
- EXPECT_EQ(gMoveOpCnt, 0);
- EXPECT_EQ(gConvertOpCnt, 0);
- }
-
- {
- // Test RVO.
- init_counters();
- auto args = make_emplace_args(
- 0, o1, o2, o3, o4, Object{}, std::cref(o2), rref(std::move(o5)));
- EXPECT_EQ(gDefaultCtrCnt, 1);
- EXPECT_EQ(gCopyCtrCnt, 4);
- EXPECT_EQ(gMoveCtrCnt, 1);
- EXPECT_EQ(gExplicitCtrCnt, 0);
- EXPECT_EQ(gMultiargCtrCnt, 0);
- EXPECT_EQ(gCopyOpCnt, 0);
- EXPECT_EQ(gMoveOpCnt, 0);
- EXPECT_EQ(gConvertOpCnt, 0);
-
- // Test move construction.
- init_counters();
- auto args2 = std::move(args);
- EXPECT_EQ(gDefaultCtrCnt, 0);
- EXPECT_EQ(gCopyCtrCnt, 0);
- EXPECT_EQ(gMoveCtrCnt, 5);
- EXPECT_EQ(gExplicitCtrCnt, 0);
- EXPECT_EQ(gMultiargCtrCnt, 0);
- EXPECT_EQ(gCopyOpCnt, 0);
- EXPECT_EQ(gMoveOpCnt, 0);
- EXPECT_EQ(gConvertOpCnt, 0);
-
- // Test move assignment.
- init_counters();
- args = std::move(args2);
- EXPECT_EQ(gDefaultCtrCnt, 0);
- EXPECT_EQ(gCopyCtrCnt, 0);
- EXPECT_EQ(gMoveCtrCnt, 0);
- EXPECT_EQ(gExplicitCtrCnt, 0);
- EXPECT_EQ(gMultiargCtrCnt, 0);
- EXPECT_EQ(gCopyOpCnt, 0);
- EXPECT_EQ(gMoveOpCnt, 5);
- EXPECT_EQ(gConvertOpCnt, 0);
-
- // Make sure arguments are stored correctly. lvalues by reference, rvalues
- // by (moved) copy. Rvalues cannot be stored by reference because they may
- // refer to an expired temporary by the time they are accessed.
- static_assert(
- std::is_same<
- int,
- std::tuple_element_t<0, decltype(args)::storage_type>>::value,
- "");
- static_assert(
- std::is_same<
- Object,
- std::tuple_element_t<1, decltype(args)::storage_type>>::value,
- "");
- static_assert(
- std::is_same<
- Object,
- std::tuple_element_t<2, decltype(args)::storage_type>>::value,
- "");
- static_assert(
- std::is_same<
- Object,
- std::tuple_element_t<3, decltype(args)::storage_type>>::value,
- "");
- static_assert(
- std::is_same<
- Object,
- std::tuple_element_t<4, decltype(args)::storage_type>>::value,
- "");
- static_assert(
- std::is_same<
- Object,
- std::tuple_element_t<5, decltype(args)::storage_type>>::value,
- "");
- static_assert(
- std::is_same<
- std::reference_wrapper<const Object>,
- std::tuple_element_t<6, decltype(args)::storage_type>>::value,
- "");
- static_assert(
- std::is_same<
- rvalue_reference_wrapper<Object>,
- std::tuple_element_t<7, decltype(args)::storage_type>>::value,
- "");
-
- // Check whether args.get() restores the original argument type for
- // rvalue references to emplace_args.
- static_assert(
- std::is_same<int&&, decltype(get_emplace_arg<0>(std::move(args)))>::
- value,
- "");
- static_assert(
- std::is_same<Object&, decltype(get_emplace_arg<1>(std::move(args)))>::
- value,
- "");
- static_assert(
- std::is_same<
- const Object&,
- decltype(get_emplace_arg<2>(std::move(args)))>::value,
- "");
- static_assert(
- std::is_same<Object&, decltype(get_emplace_arg<3>(std::move(args)))>::
- value,
- "");
- static_assert(
- std::is_same<
- const Object&,
- decltype(get_emplace_arg<4>(std::move(args)))>::value,
- "");
- static_assert(
- std::is_same<Object&&, decltype(get_emplace_arg<5>(std::move(args)))>::
- value,
- "");
- static_assert(
- std::is_same<
- const Object&,
- decltype(get_emplace_arg<6>(std::move(args)))>::value,
- "");
- static_assert(
- std::is_same<Object&&, decltype(get_emplace_arg<7>(std::move(args)))>::
- value,
- "");
-
- // lvalue references to emplace_args should behave mostly like std::tuples.
- // Note that get_emplace_arg<7>(args) does not compile, because
- // folly::rvalue_reference_wrappers can only be unwrapped through an rvalue
- // reference.
- static_assert(
- std::is_same<int&, decltype(get_emplace_arg<0>(args))>::value, "");
- static_assert(
- std::is_same<Object&, decltype(get_emplace_arg<1>(args))>::value, "");
- static_assert(
- std::is_same<Object&, decltype(get_emplace_arg<2>(args))>::value, "");
- static_assert(
- std::is_same<Object&, decltype(get_emplace_arg<3>(args))>::value, "");
- static_assert(
- std::is_same<Object&, decltype(get_emplace_arg<4>(args))>::value, "");
- static_assert(
- std::is_same<Object&, decltype(get_emplace_arg<5>(args))>::value, "");
- static_assert(
- std::is_same<const Object&, decltype(get_emplace_arg<6>(args))>::value,
- "");
- }
-}
-
-/**
- * Test implicit unpacking.
- */
-TEST(EmplaceIterator, ImplicitUnpack) {
- static std::size_t multiCtrCnt;
- static std::size_t pairCtrCnt;
- static std::size_t tupleCtrCnt;
-
- struct Object2 {
- Object2(int, int) {
- ++multiCtrCnt;
- }
- explicit Object2(const std::pair<int, int>&) {
- ++pairCtrCnt;
- }
- explicit Object2(const std::tuple<int, int>&) {
- ++tupleCtrCnt;
- }
- };
-
- auto test = [](auto&& it, bool expectUnpack) {
- multiCtrCnt = pairCtrCnt = tupleCtrCnt = 0;
- it = std::make_pair(0, 0);
- it = std::make_tuple(0, 0);
- if (expectUnpack) {
- EXPECT_EQ(multiCtrCnt, 2);
- EXPECT_EQ(pairCtrCnt, 0);
- EXPECT_EQ(tupleCtrCnt, 0);
- } else {
- EXPECT_EQ(multiCtrCnt, 0);
- EXPECT_EQ(pairCtrCnt, 1);
- EXPECT_EQ(tupleCtrCnt, 1);
- }
- };
-
- Container<Object2> q;
-
- test(emplacer(q, q.begin()), true);
- test(emplacer<false>(q, q.begin()), false);
- test(front_emplacer(q), true);
- test(front_emplacer<false>(q), false);
- test(back_emplacer(q), true);
- test(back_emplacer<false>(q), false);
-}
sorted_vector_types_test_LDADD = libfollytestmain.la
-foreach_test_SOURCES = ForeachTest.cpp
+foreach_test_SOURCES = ../container/test/ForeachTest.cpp
foreach_test_LDADD = libfollytestmain.la
-foreach_benchmark_SOURCES = ForeachBenchmark.cpp
+foreach_benchmark_SOURCES = ../container/test/ForeachBenchmark.cpp
foreach_benchmark_LDADD = libfollytestmain.la $(top_builddir)/libfollybenchmark.la
check_PROGRAMS += foreach_benchmark
#include <glog/logging.h>
#include <folly/Benchmark.h>
-#include <folly/Foreach.h>
+#include <folly/container/Foreach.h>
#if FOLLY_HAVE_EXTRANDOM_SFMT19937
#include <ext/random>
#include <string>
#include <folly/Benchmark.h>
-#include <folly/Foreach.h>
+#include <folly/container/Foreach.h>
using namespace folly;
using namespace std;
+++ /dev/null
-/*
- * Copyright 2017 Facebook, Inc.
- *
- * 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
- *
- * http://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.
- */
-
-/***
- * A benchmark comparing SparseByteSet to bitset<256> and bool[256].
- */
-
-#include <folly/Benchmark.h>
-#include <folly/Format.h>
-#include <folly/SparseByteSet.h>
-#include <folly/portability/GFlags.h>
-#include <bitset>
-#include <random>
-#include <vector>
-
-using namespace std;
-using namespace folly;
-
-namespace {
-
-// Interface-identical to SparseByteSet. So that we can do compile-time
-// polymorphism.
-class BitSetWrapper {
- public:
- inline bool add(uint8_t i) {
- auto r = !contains(i);
- if (r) {
- rep_[i] = true;
- }
- return r;
- }
- inline bool contains(uint8_t i) {
- return rep_[i];
- }
- private:
- bitset<256> rep_;
-};
-class BoolArraySet {
- public:
- BoolArraySet() {
- memset(rep_, 0, sizeof(rep_));
- }
- inline bool add(uint8_t i) {
- auto r = !contains(i);
- if (r) {
- rep_[i] = true;
- }
- return r;
- }
- inline bool contains(uint8_t i) {
- return rep_[i];
- }
- private:
- bool rep_[256];
-};
-
-template <typename Coll>
-void rand_bench(int iters, size_t size_add, size_t size_contains) {
- BenchmarkSuspender braces;
- vector<uint8_t> seq_add;
- vector<uint8_t> seq_contains;
- mt19937 rng;
- uniform_int_distribution<uint8_t> dist;
- for (size_t i = 0; i < size_add; ++i) {
- seq_add.push_back(dist(rng));
- }
- for (size_t i = 0; i < size_contains; ++i) {
- seq_contains.push_back(dist(rng));
- }
- braces.dismissing([&] {
- while (iters--) {
- Coll coll;
- for (auto b : seq_add) {
- coll.add(b);
- }
- bool q {};
- for (auto b : seq_contains) {
- q ^= coll.contains(b);
- }
- doNotOptimizeAway(q);
- }
- });
-}
-
-void setup_rand_bench() {
- vector<pair<size_t, size_t>> rand_bench_params = {
- {4, 4},
- {4, 16},
- {4, 64},
- {4, 256},
- {16, 4},
- {16, 16},
- {16, 64},
- {16, 256},
- {64, 4},
- {64, 16},
- {64, 64},
- {64, 256},
- {256, 4},
- {256, 16},
- {256, 64},
- {256, 256},
- };
- for (auto kvp : rand_bench_params) {
- size_t size_add, size_contains;
- tie(size_add, size_contains) = kvp;
- addBenchmark(
- __FILE__,
- sformat("bitset_rand_bench({}, {})",
- size_add, size_contains).c_str(),
- [=](int iters) {
- rand_bench<BitSetWrapper>(iters, size_add, size_contains);
- return iters;
- });
- addBenchmark(
- __FILE__,
- sformat("%bool_array_set_rand_bench({}, {})",
- size_add, size_contains).c_str(),
- [=](int iters) {
- rand_bench<BoolArraySet>(iters, size_add, size_contains);
- return iters;
- });
- addBenchmark(
- __FILE__,
- sformat("%sparse_byte_set_rand_bench({}, {})",
- size_add, size_contains).c_str(),
- [=](int iters) {
- rand_bench<SparseByteSet>(iters, size_add, size_contains);
- return iters;
- });
- addBenchmark(
- __FILE__,
- "-",
- [](int) { return 0; });
- }
-}
-
-}
-
-int main(int argc, char** argv) {
- gflags::ParseCommandLineFlags(&argc, &argv, true);
- setup_rand_bench();
- runBenchmarks();
- return 0;
-}
+++ /dev/null
-/*
- * Copyright 2017 Facebook, Inc.
- *
- * 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
- *
- * http://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 <folly/SparseByteSet.h>
-
-#include <cstdint>
-#include <limits>
-#include <random>
-#include <set>
-
-#include <folly/portability/GTest.h>
-
-using namespace std;
-using namespace folly;
-
-namespace {
-
-class SparseByteSetTest : public testing::Test {
- protected:
- using lims = numeric_limits<uint8_t>;
- SparseByteSet s;
-};
-
-}
-
-TEST_F(SparseByteSetTest, empty) {
- for (auto c = lims::min(); c < lims::max(); ++c) {
- EXPECT_FALSE(s.contains(c));
- }
-}
-
-TEST_F(SparseByteSetTest, each) {
- for (auto c = lims::min(); c < lims::max(); ++c) {
- EXPECT_TRUE(s.add(c));
- EXPECT_TRUE(s.contains(c));
- }
- for (auto c = lims::min(); c < lims::max(); ++c) {
- EXPECT_FALSE(s.add(c));
- EXPECT_TRUE(s.contains(c));
- }
-}
-
-TEST_F(SparseByteSetTest, each_random) {
- mt19937 rng;
- uniform_int_distribution<uint16_t> dist{lims::min(), lims::max()};
- set<uint8_t> added;
- while (added.size() <= lims::max()) {
- auto c = uint8_t(dist(rng));
- EXPECT_EQ(added.count(c), s.contains(c));
- EXPECT_EQ(!added.count(c), s.add(c));
- added.insert(c);
- EXPECT_TRUE(added.count(c)); // sanity
- EXPECT_TRUE(s.contains(c));
- }
-}
#pragma once
-#include <folly/Foreach.h>
#include <folly/Random.h>
#include <folly/Synchronized.h>
+#include <folly/container/Foreach.h>
#include <folly/portability/GTest.h>
#include <glog/logging.h>
#include <algorithm>
projects / folly.git / commitdiff