Summary:
The `glog/logging.h` header is a bit expensive here considering its size, and how frequently `Range.h` is used.

Replace the `DCHECK_${comparison}` macro usage with macros defined in this file.

Reviewed By: yfeldblum

Differential Revision: D8473303

fbshipit-source-id: cc2a7e9eabab2c1f83a377de5191f708f1c9f317

Summary: Adjust the growth factor based on the StaticMetaBase::head_::elementsCapacity

Reviewed By: yfeldblum

Differential Revision: D8409650

fbshipit-source-id: 189b839e19a1d3f2f1ac8e4b35a2f11a4d319ad7

Summary:
- Use the hazard pointer library under folly/synchronization.
  - NodeT derived from hazptr_obj_base_linked.
  - Bucket heads are hazptr_root-s with dtor that automatically unlinks nodes
  - Provides support for uncertain removal of NodeT-s both from NodeT and Buckets
  - As intended, hazptr_cleanup reclaims all unprotected removed objects even if they have not been determined to be retirable at the start of cleanup.

Fixes the following:
- The pattern of calling h.get_protected(node->next_), when hazptr_holder h is protecting node is unsafe because try_protect (inside get_protected) may fail and we end protecting neither node nor next. This diff uses a different hazptr_holder to protect the next node. A correct pattern is to call h2.get_protected(node->next_) then h.swap(h2); h2.reset();
- The pattern of calling h2.reset(node) then h1.reset() to continue protecting a node already protected by h1 is unsafe because h2's protection may be too late after node was retired. A correct pattern is h2.swap(h1).

Reviewed By: djwatson

Differential Revision: D7708325

fbshipit-source-id: 617dcfe19410071888abafa32f0e1ada9d123983

Summary: [Folly] `bool_constant` (C++17 backport) and `index_constant`.

Reviewed By: aary

Differential Revision: D8440131

fbshipit-source-id: 2bc4fae1e2d1f404d4060c209ee325beebe2a415

Summary:
A comment to `FutureAlreadyContinued` to explain to readers in what circumstance it is thrown.

(Note: this ignores all push blocking failures!)

Reviewed By: yfeldblum

Differential Revision: D8460097

fbshipit-source-id: 49657e030efe72c026c1c3eea3612952746bb0e1

Summary: Add `explicit` to `MoveCtorOnly::MoveCtorOnly(int)` in FutureTest.cpp

Reviewed By: yfeldblum

Differential Revision: D8439496

fbshipit-source-id: 51217f186aa9b79d342a7be7f460d0a9c3f070c1

Summary:
When passing elements of a set or map through a bulk API that understands
arrays, it is a useful optimization to be able to iterator or visit
contiguous ranges rather than individual elements.  This diff adds
visitContiguousRanges to F14 maps and sets, which repeatedly passes a
contiguous range to the visitor.  The range is identified with a begin
and end value_type const*.  Each value_type of the table will be included
in exactly one of the passed ranges, and the number of ranges will be
minimized whenever possible.

Reviewed By: yfeldblum

Differential Revision: D8332897

fbshipit-source-id: a7cd5d670b14faeeef97497cccd4cb0a3b07dd50

Summary:
vshrn_n_u16 can be used to efficiently get a bit of information
from every byte in a 16-byte vector into an 8-byte vector, which is better
than the previous NEON sequence used during tag matching.  The resulting
code is faster and smaller on aarch64.  x86_64 code is refactored but
should compile to the same assembly.

Reviewed By: shixiao

Differential Revision: D8420917

fbshipit-source-id: 21a9f920f55ffc479b20fee6882a5987b626c89a

Summary: Add rvalue-qualified overloads of Future::get() and get(dur) which invalidate their this-object.

Reviewed By: yfeldblum

Differential Revision: D8242442

fbshipit-source-id: 4dea8a41878d59f6088504df2b8b3e686d581c89

Summary:
Codemod non-pointer expressions:
   - expr.get() ==> std::move(expr).get()
   - expr.get(dur) ==> std::move(expr).get(dur)
when expr is not already an xvalue.

Reviewed By: yfeldblum

Differential Revision: D8430137

fbshipit-source-id: 20da463f9cceb5cb1e71a7226f3b11d1e8007011

Summary: When hazptr_priv dtor pushes objects to the domain and that happens to trigger (either due to timed cleanup or reaching the bulk reclaim threshold) bulk reclamation that retires objects. These newly retired objects should be pushed to the domain and not into the hazptr_priv.

Reviewed By: djwatson

Differential Revision: D8410795

fbshipit-source-id: c7af01cc41a1d82896bd3700fa072f698c0aa77b

Summary: Currently the implementation just relies on futures::sleep. Ideally it should be able to use Executor's timer if available.

Reviewed By: yfeldblum

Differential Revision: D8404592

fbshipit-source-id: e952a0cc3d99bc528ea14ff5c68835d63a71e685

Summary:
[Folly] Optimize Futures Core state-dependent fields, controlling when they are constructed and destructed.

* Reduces layout size by removing the `Optional` wrapper for the result.
* Reduces code size by removing checks and destructions in assignment operators which are not in constructors for `Optional`, `Try`, `Function`, and `shared_ptr`.

Reviewed By: andriigrynenko

Differential Revision: D8346365

fbshipit-source-id: 83ac164dc36934065f2fcfb112440869d023b674

Reviewed By: aary

Differential Revision: D8393345

fbshipit-source-id: 5fc9bbfb3fa1dc63077cd406f4335c2a7967a53d

Summary:
This diff extends heterogeneous key handling (when the hasher and
key equality functor are transparent) to mutating operations.  If a key
of type K was previously eligible for heterogeneous find and key_type can
be constructed from the key, then that construction can be deferred until
after it is verified that the key is not previously in the table when
using any of the operations that may insert a new element.  If the key was
already present then this avoids the construction of key_type entirely.
Heterogeneous erase is also added in the obvious fashion.

Construction of key_type from K can be accomplished without key_type's
cooperation by the use of an explicit conversion operator, such as the
explicit operator std::string recently added to StringPiece.  That means
that a F14 map or set with std::string key and transparent StringPiece
hash and equality can now use StringPiece natively as a key.

Destructuring is applied whenever possible, so the heterogeneous key
type K may be found as the first element of a pair (for map insert or
emplace) or even inside the first tuple when using map emplace with
std::piecewise_construct.

This diff adds heterogeneous key support to

    Map::insert
    Map::insert_or_assign
    Map::emplace
    Map::try_emplace
    Map::operator[]
    Set::insert
    Set::emplace

Reviewed By: yfeldblum

Differential Revision: D8301887

fbshipit-source-id: 1a45e13739c550f094afe09123839a3c9cd892ff

Summary:
[Folly] In Futures Core, destroy context when destroying callback since they basically go together.

Also removes expectations in an Eden FS test case which affirm the old behavior, along with a TODO to remove the expectations once the affirmed behavior is fixed.

Reviewed By: marshallcline

Differential Revision: D8347040

fbshipit-source-id: ed9fec932ad1e0aa1e40675cf70081d19bbe4325

Summary:
[Folly] Use a simpler atomic state in Futures `Core` v.s. `FSM` which abstracts an atomic state plus a spin-lock.

The `FSM` abstraction can be useful in more complex cases, but is not needed in the current case. All that is needed is a single barrier state, which is `Done` - setting callback and result happen before state transitions to `Done`, while invoking callback with result happens after state transitions to `Done`.

Reviewed By: marshallcline

Differential Revision: D8083703

fbshipit-source-id: 42d96b41cbdac5e7c42f3f8a661d5db3113655db

Summary:
[Folly] Use `terminate_with` in Futures `Core` invalid transitions.

Both `Promise` and `Future` check state validity before calling the `Core` transition methods and throws in invalid state. So `Core` no longer needs to throw and may terminate instead.

Reviewed By: marshallcline

Differential Revision: D8346113

fbshipit-source-id: 9ff158673149096789b29544453262797b06d441

Summary: [Folly] `folly::terminate_with`, to terminate as if by forwarding to `folly::throw_exception` but in a `noexcept` context.

Reviewed By: marshallcline

Differential Revision: D8345962

fbshipit-source-id: bc5cf5d3a3e1f085dd2989c940a6ea753a520cbf

Summary:
[Folly] Let Future check before adding a continuation whether a continuation has already been added.

Requires making wait behave more like timed-wait; alternatively, it would be possible to add a reverse state transition, but there seems not to be a need.

Reviewed By: marshallcline

Differential Revision: D8344923

fbshipit-source-id: f077fb4b83b92c96af9a83e1b1479c4cb41b048a

Summary:
[Folly] `Range` explicit conversion to any target type, with overloads enabled only for target types which are explicitly constructible from two iterators.

Also changes `Range::to` to do similar, but permits additional arguments to be forwarded as trailing arguments to the target type constructor.

For example, this makes `std::string`, `folly::fbstring`, `std::vector<char>`, and all variants with default-constructible custom allocators, to be constructible from (but not convertible from) `folly::StringPiece`.

Reviewed By: nbronson

Differential Revision: D8386240

fbshipit-source-id: 2426191d1c8ac71cd5832f784e83bbe09b8716e7

Summary:
There were two TODOs that I knew of in fbcode about this, so I decided to file
a task so we can track it.

Reviewed By: simpkins

Differential Revision: D8176921

fbshipit-source-id: 0ca45620050639659ac038dbed43acf4634f7a1d

Summary:
Added `FutureBase::delayedImplementation`. Kept the existing semantics of
`Future::delayed` and `Future::delayedUnsafe`. `SemiFuture::delayed` uses
the inline executor which means we could execute our trivial lambda on
the `Timekeeper` thread. However we ultimately return a `SemiFuture`,
so we're not necessarily on the hook to execute an arbitrarily complex
continuation.

NOTE: This is still possible if the user explicitly specifies
`.via(inline_executor)`. Perhaps we should consider disallowing, or maybe linting for this.

Reviewed By: yfeldblum

Differential Revision: D8372515

fbshipit-source-id: e660dbf2a2bb084e11c5e57d1badacf09425f939

Summary:
To implement tdigest aggregation in scuba, we need to be able to deserialize and serialize the digests.
I added a getter for the centroids so that we can serialize the tdigest, and added a constructor to create one from the list of centroids.

Last diff was reverted because of a build error :(
We were seeing an error only in opt mode because it's an error in gcc but not in clang.

Differential Revision: D8381617

fbshipit-source-id: 768a12795aeb02737eb9b060f80d01608685c91d

Summary: title

Reviewed By: yfeldblum, andriigrynenko

Differential Revision: D8386575

fbshipit-source-id: c900c8692b10004f2d9fbd95fa8ca96b3b8517d2

Summary:
[Folly] Skip trivial-copyability `Expected` expectations under gcc49.

The focus is on gcc5+; all that is needed for now is to keep code compiling with gcc49, but not necessarily to ensure optimal trivial-copyability behavior.

Reviewed By: Orvid

Differential Revision: D8364392

fbshipit-source-id: b0062193c844509b6bf26ed632dd8e5d4bdf77d2

Summary: Assume, when UBSAN is used, it is always used on top of ASAN.

Reviewed By: luciang

Differential Revision: D8360231

fbshipit-source-id: 3106cfa53567b18f199e9303ea4c14a464ff03cc

Summary: Makes a spec for libsodium.

Reviewed By: knekritz

Differential Revision: D8228801

fbshipit-source-id: 18f623bce0bbc07f711129b15b78d56b6c852bf7

Summary: [Folly] A cache for `InlineExecutor` singleton, which can be inlined into callers with little extra code compared to calling the backing function directly.

Reviewed By: marshallcline

Differential Revision: D8339793

fbshipit-source-id: d2be0128e617cfefe66809eb44ce40e1a8ae2dfb

Summary: [Folly] Write `Promise::setException` in terms of `Promise::setTry`.

Reviewed By: marshallcline

Differential Revision: D8344928

fbshipit-source-id: 90e21219f054329eca7ae1a6c2ca731a16328b6f

Revert D8360404: [folly] Support constructing TDigest from centroids and getting centroids from TDigest

Differential Revision:
D8360404

Original commit changeset: b0f42e892f66

fbshipit-source-id: 985ba55bb443aafe7c324f15caeca0abb34d200a

Summary: Before this diff, since `ctx->memo_` starts out in the `OnlyResult` state, the first reduce (and therefore all subsequent reduces) are run immediately inside the lock.

Reviewed By: yfeldblum

Differential Revision: D8319067

fbshipit-source-id: 5ed08885beefb42c6efb61768fcbc36e0a08a46b

Summary:
To implement tdigest aggregation in scuba, we need to be able to deserialize and serialize the digests.
I added a getter for the centroids so that we can serialize the tdigest, and added a constructor to create one from the list of centroids.

Differential Revision: D8360404

fbshipit-source-id: b0f42e892f666e787e06198c7e8ff65dd8799dcc

Summary:
In folly::small_vector, we were (mistakenly) relying on a default constructor
for non-trivially constructible types.

The problem got worse on gcc 4.9, because for that compiler version, we set
folly::is_trivially_copyable to be std::is_trivial. This is mostly okay, as
std::is_trivial implies std::is_trivially_copyable. The problem is that
std::is_trivial also implies std::is_default_constructuble, which which was
breaking folly::small_vector

Reviewed By: yfeldblum

Differential Revision: D8346780

fbshipit-source-id: 9c8a9dab21ea2d4fd34f636458324915c30e10a2

Summary:
See https://gitlab.kitware.com/cmake/cmake/issues/16686

This patch was originally contributed to MacPorts by mohd-akram in https://github.com/macports/macports-ports/pull/1933.
Closes https://github.com/facebook/folly/pull/862

Reviewed By: Orvid

Differential Revision: D8346974

Pulled By: yfeldblum

fbshipit-source-id: 2673e1f414dd86bf91bb2183c2f6d9f7e72251f8

Summary:
[Folly] A shorter name for executor local variable in `Future` methods. Reads more nicely, with less awkward formatting.

When the scope of a local variable's use is just a few lines, long names are not quite so critical.

Reviewed By: marshallcline

Differential Revision: D8339451

fbshipit-source-id: 5d50cf0ce3473c1a79afeeddb9e1257cccf73e31

Summary: [Folly] No need for qualifying `InlineExecutor` in `Futures` - they are both in `namespace folly` already.

Reviewed By: marshallcline

Differential Revision: D8307058

fbshipit-source-id: 17a0ecde1e57f1c0c88cbac09bbd1bb3daf7a24e

Summary:
[Folly] Use `InlineExecutor` singleton in `Future` wait v.s. letting the executor be `nullptr`.

The effect is the same, but just more explicit.

Reviewed By: marshallcline

Differential Revision: D8306902

fbshipit-source-id: fc90704de670b1ca9956253383fadad3be297847

Summary:
Executor adaptor which allows joining only tasks scheduled through this VirtualExecutor instance without joining all other tasks in a wrapped Executor.
This is very similar to VirtualEventBase, but works for any Executor.

Reviewed By: yfeldblum, aary

Differential Revision: D8342064

fbshipit-source-id: 420b6390e2da88c4826e6d22bc8f3b3585525214

Summary: [Folly] Ensure sleep duration in logging `RateLimiter` test to make sure that there is no chance of waking up from the sleep too early.

Reviewed By: Orvid

Differential Revision: D8330018

fbshipit-source-id: f1222e1da50f8360267f9e1c5e0f24897b7b8f47