zone-containers.h | Explore in Territory

// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_ZONE_ZONE_CONTAINERS_H_
#define V8_ZONE_ZONE_CONTAINERS_H_

#include <deque>
#include <forward_list>
#include <initializer_list>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>

#include "absl/container/flat_hash_map.h"
#include "absl/container/flat_hash_set.h"
#include "src/base/functional.h"
#include "src/base/intrusive-set.h"
#include "src/base/small-map.h"
#include "src/base/small-vector.h"
#include "src/zone/zone-allocator.h"

namespace v8 {
namespace internal {

// A drop-in replacement for std::vector that uses a Zone for its allocations,
// and (contrary to a std::vector subclass with custom allocator) gives us
// precise control over its implementation and performance characteristics.
//
// When working on this code, keep the following rules of thumb in mind:
// - Everything between {data_} and {end_} (exclusive) is a live instance of T.
//   When writing to these slots, use the {CopyingOverwrite} or
//   {MovingOverwrite} helpers.
// - Everything between {end_} (inclusive) and {capacity_} (exclusive) is
//   considered uninitialized memory. When writing to these slots, use the
//   {CopyToNewStorage} or {MoveToNewStorage} helpers. Obviously, also use
//   these helpers to initialize slots in newly allocated backing stores.
// - When shrinking, call ~T on all slots between the new and the old position
//   of {end_} to maintain the above invariant. Also call ~T on all slots in
//   discarded backing stores.
// - The interface offered by {ZoneVector} should be a subset of
//   {std::vector}'s API, so that calling code doesn't need to be aware of
//   ZoneVector's implementation details and can assume standard C++ behavior.
//   (It's okay if we don't support everything that std::vector supports; we
//   can fill such gaps when use cases arise.)
template <typename T>
class ZoneVector { … };

template <class T>
bool operator==(const ZoneVector<T>& lhs, const ZoneVector<T>& rhs) { … }

template <class T>
bool operator!=(const ZoneVector<T>& lhs, const ZoneVector<T>& rhs) { … }

template <class T>
bool operator<(const ZoneVector<T>& lhs, const ZoneVector<T>& rhs) { … }

template <class T, class GetIntrusiveSetIndex>
class ZoneIntrusiveSet
    : public base::IntrusiveSet<T, GetIntrusiveSetIndex, ZoneVector<T>> { … };
IntrusiveSetIndex;

// A wrapper subclass for std::deque to make it easy to construct one
// that uses a zone allocator.
template <typename T>
class ZoneDeque : public std::deque<T, RecyclingZoneAllocator<T>> { … };

// A wrapper subclass for std::list to make it easy to construct one
// that uses a zone allocator.
// TODO(all): This should be renamed to ZoneList once we got rid of our own
// home-grown ZoneList that actually is a ZoneVector.
template <typename T>
class ZoneLinkedList : public std::list<T, ZoneAllocator<T>> { … };

// A wrapper subclass for std::forward_list to make it easy to construct one
// that uses a zone allocator.
template <typename T>
class ZoneForwardList : public std::forward_list<T, ZoneAllocator<T>> { … };

// A wrapper subclass for std::priority_queue to make it easy to construct one
// that uses a zone allocator.
template <typename T, typename Compare = std::less<T>>
class ZonePriorityQueue
    : public std::priority_queue<T, ZoneVector<T>, Compare> {
 public:
  // Constructs an empty list.
  explicit ZonePriorityQueue(Zone* zone)
      : … { … }
};

// A wrapper subclass for std::queue to make it easy to construct one
// that uses a zone allocator.
template <typename T>
class ZoneQueue : public std::queue<T, ZoneDeque<T>> { … };

// A wrapper subclass for std::stack to make it easy to construct one that uses
// a zone allocator.
template <typename T>
class ZoneStack : public std::stack<T, ZoneDeque<T>> { … };

// A wrapper subclass for std::set to make it easy to construct one that uses
// a zone allocator.
template <typename K, typename Compare = std::less<K>>
class ZoneSet : public std::set<K, Compare, ZoneAllocator<K>> {
 public:
  // Constructs an empty set.
  explicit ZoneSet(Zone* zone)
      : … { … }
};

// A wrapper subclass for std::multiset to make it easy to construct one that
// uses a zone allocator.
template <typename K, typename Compare = std::less<K>>
class ZoneMultiset : public std::multiset<K, Compare, ZoneAllocator<K>> {
 public:
  // Constructs an empty multiset.
  explicit ZoneMultiset(Zone* zone)
      : … { … }
};

// A wrapper subclass for std::map to make it easy to construct one that uses
// a zone allocator.
template <typename K, typename V, typename Compare = std::less<K>>
class ZoneMap
    : public std::map<K, V, Compare, ZoneAllocator<std::pair<const K, V>>> {
 public:
  // Constructs an empty map.
  explicit ZoneMap(Zone* zone)
      : … { … }
};

// A wrapper subclass for std::unordered_map to make it easy to construct one
// that uses a zone allocator.
template <typename K, typename V, typename Hash = base::hash<K>,
          typename KeyEqual = std::equal_to<K>>
class ZoneUnorderedMap
    : public std::unordered_map<K, V, Hash, KeyEqual,
                                ZoneAllocator<std::pair<const K, V>>> {
 public:
  // Constructs an empty map.
  explicit ZoneUnorderedMap(Zone* zone, size_t bucket_count = 0)
      : … { … }
};

// A wrapper subclass for std::unordered_set to make it easy to construct one
// that uses a zone allocator.
template <typename K, typename Hash = base::hash<K>,
          typename KeyEqual = std::equal_to<K>>
class ZoneUnorderedSet
    : public std::unordered_set<K, Hash, KeyEqual, ZoneAllocator<K>> {
 public:
  // Constructs an empty set.
  explicit ZoneUnorderedSet(Zone* zone, size_t bucket_count = 0)
      : … { … }
};

// A wrapper subclass for std::multimap to make it easy to construct one that
// uses a zone allocator.
template <typename K, typename V, typename Compare = std::less<K>>
class ZoneMultimap
    : public std::multimap<K, V, Compare,
                           ZoneAllocator<std::pair<const K, V>>> {
 public:
  // Constructs an empty multimap.
  explicit ZoneMultimap(Zone* zone)
      : … { … }
};

// A wrapper subclass for base::SmallVector to make it easy to construct one
// that uses a zone allocator.
template <typename T, size_t kSize>
class SmallZoneVector : public base::SmallVector<T, kSize, ZoneAllocator<T>> { … };

// Used by SmallZoneMap below. Essentially a closure around placement-new of
// the "full" fallback ZoneMap. Called once SmallMap grows beyond kArraySize.
template <typename ZoneMap>
class ZoneMapInit { … };

// A wrapper subclass for base::SmallMap to make it easy to construct one that
// uses a zone-allocated std::map as the fallback once the SmallMap outgrows
// its inline storage.
template <typename K, typename V, size_t kArraySize,
          typename Compare = std::less<K>, typename KeyEqual = std::equal_to<K>>
class SmallZoneMap
    : public base::SmallMap<ZoneMap<K, V, Compare>, kArraySize, KeyEqual,
                            ZoneMapInit<ZoneMap<K, V, Compare>>> {
 public:
  explicit SmallZoneMap(Zone* zone)
      : … { … }
};

// A wrapper subclass for absl::flat_hash_map to make it easy to construct one
// that uses a zone allocator. If you want to use a user-defined type as key
// (K), you'll need to define a AbslHashValue function for it (see
// https://abseil.io/docs/cpp/guides/hash).
template <typename K, typename V,
          typename Hash = typename absl::flat_hash_map<K, V>::hasher,
          typename KeyEqual =
              typename absl::flat_hash_map<K, V, Hash>::key_equal>
class ZoneAbslFlatHashMap
    : public absl::flat_hash_map<K, V, Hash, KeyEqual,
                                 ZoneAllocator<std::pair<const K, V>>> { … };

// A wrapper subclass for absl::flat_hash_set to make it easy to construct one
// that uses a zone allocator. If you want to use a user-defined type as key
// (K), you'll need to define a AbslHashValue function for it (see
// https://abseil.io/docs/cpp/guides/hash).
template <typename K, typename Hash = typename absl::flat_hash_set<K>::hasher,
          typename KeyEqual = typename absl::flat_hash_set<K, Hash>::key_equal>
class ZoneAbslFlatHashSet
    : public absl::flat_hash_set<K, Hash, KeyEqual, ZoneAllocator<K>> { … };

// Typedefs to shorten commonly used vectors.
IntVector;

}  // namespace internal
}  // namespace v8

#endif  // V8_ZONE_ZONE_CONTAINERS_H_
chromium/v8/src/zone/zone-containers.h
