folly/folly/container/FBVector.h

/*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * 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.
 */

/*
 * Nicholas Ormrod      (njormrod)
 * Andrei Alexandrescu  (aalexandre)
 *
 * FBVector is Facebook's drop-in implementation of std::vector. It has special
 * optimizations for use with relocatable types and jemalloc.
 */

#pragma once

//=============================================================================
// headers

#include <algorithm>
#include <cassert>
#include <iterator>
#include <memory>
#include <stdexcept>
#include <type_traits>
#include <utility>

#include <folly/FormatTraits.h>
#include <folly/Likely.h>
#include <folly/ScopeGuard.h>
#include <folly/Traits.h>
#include <folly/lang/CheckedMath.h>
#include <folly/lang/Exception.h>
#include <folly/lang/Hint.h>
#include <folly/memory/Malloc.h>

//=============================================================================
// forward declaration

namespace folly {
template <class T, class Allocator = std::allocator<T>>
class fbvector;
} // namespace folly

//=============================================================================
// unrolling

#define FOLLY_FBV_UNROLL_PTR(first, last, OP) …

//=============================================================================
///////////////////////////////////////////////////////////////////////////////
//                                                                           //
//                              fbvector class                               //
//                                                                           //
///////////////////////////////////////////////////////////////////////////////

namespace folly {

namespace detail {
inline void* thunk_return_nullptr() { … }
} // namespace detail

template <class T, class Allocator>
class fbvector { … }; // class fbvector

//=============================================================================
//-----------------------------------------------------------------------------
// specialized functions

template <class T, class A>
void swap(fbvector<T, A>& lhs, fbvector<T, A>& rhs) noexcept { … }

//=============================================================================
//-----------------------------------------------------------------------------
// other

namespace detail {

// Format support.
IndexableTraits<fbvector<T, A>>;

} // namespace detail

template <class T, class A>
void compactResize(fbvector<T, A>* v, size_t sz) { … }

// DANGER
//
// relinquish and attach are not a members function specifically so that it is
//  awkward to call them. It is very easy to shoot yourself in the foot with
//  these functions.
//
// If you call relinquish, then it is your responsibility to free the data
//  and the storage, both of which may have been generated in a non-standard
//  way through the fbvector's allocator.
//
// If you call attach, it is your responsibility to ensure that the fbvector
//  is fresh (size and capacity both zero), and that the supplied data is
//  capable of being manipulated by the allocator.
// It is acceptable to supply a stack pointer IF:
//  (1) The vector's data does not outlive the stack pointer. This includes
//      extension of the data's life through a move operation.
//  (2) The pointer has enough capacity that the vector will never be
//      relocated.
//  (3) Insert is not called on the vector; these functions have leeway to
//      relocate the vector even if there is enough capacity.
//  (4) A stack pointer is compatible with the fbvector's allocator.
//

template <class T, class A>
T* relinquish(fbvector<T, A>& v) { … }

template <class T, class A>
void attach(fbvector<T, A>& v, T* data, size_t sz, size_t cap) { … }

template <
    class InputIt,
    class Allocator =
        std::allocator<typename std::iterator_traits<InputIt>::value_type>>
fbvector(InputIt, InputIt, Allocator = Allocator())
    -> fbvector<typename std::iterator_traits<InputIt>::value_type, Allocator>;

template <class T, class A, class U>
void erase(fbvector<T, A>& v, U value) { … }

template <class T, class A, class Predicate>
void erase_if(fbvector<T, A>& v, Predicate predicate) { … }
} // namespace folly