ceph/src/include/cpp-btree/btree_map.h

   1 // Copyright 2018 The Abseil Authors.
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of the License at
   6 //
   7 //      https://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14 //
  15 // -----------------------------------------------------------------------------
  16 // File: btree_map.h
  17 // -----------------------------------------------------------------------------
  18 //
  19 // This header file defines B-tree maps: sorted associative containers mapping
  20 // keys to values.
  21 //
  22 //     * `btree::btree_map<>`
  23 //     * `btree::btree_multimap<>`
  24 //
  25 // These B-tree types are similar to the corresponding types in the STL
  26 // (`std::map` and `std::multimap`) and generally conform to the STL interfaces
  27 // of those types. However, because they are implemented using B-trees, they
  28 // are more efficient in most situations.
  29 //
  30 // Unlike `std::map` and `std::multimap`, which are commonly implemented using
  31 // red-black tree nodes, B-tree maps use more generic B-tree nodes able to hold
  32 // multiple values per node. Holding multiple values per node often makes
  33 // B-tree maps perform better than their `std::map` counterparts, because
  34 // multiple entries can be checked within the same cache hit.
  35 //
  36 // However, these types should not be considered drop-in replacements for
  37 // `std::map` and `std::multimap` as there are some API differences, which are
  38 // noted in this header file.
  39 //
  40 // Importantly, insertions and deletions may invalidate outstanding iterators,
  41 // pointers, and references to elements. Such invalidations are typically only
  42 // an issue if insertion and deletion operations are interleaved with the use of
  43 // more than one iterator, pointer, or reference simultaneously. For this
  44 // reason, `insert()` and `erase()` return a valid iterator at the current
  45 // position.
  46
  47 #pragma once
  48
  49 #include "btree.h"
  50 #include "btree_container.h"
  51
  52 namespace btree {
  53
  54 // btree::btree_map<>
  55 //
  56 // A `btree::btree_map<K, V>` is an ordered associative container of
  57 // unique keys and associated values designed to be a more efficient replacement
  58 // for `std::map` (in most cases).
  59 //
  60 // Keys are sorted using an (optional) comparison function, which defaults to
  61 // `std::less<K>`.
  62 //
  63 // A `btree::btree_map<K, V>` uses a default allocator of
  64 // `std::allocator<std::pair<const K, V>>` to allocate (and deallocate)
  65 // nodes, and construct and destruct values within those nodes. You may
  66 // instead specify a custom allocator `A` (which in turn requires specifying a
  67 // custom comparator `C`) as in `btree::btree_map<K, V, C, A>`.
  68 //
  69 template <typename Key, typename Value, typename Compare = std::less<Key>,
  70           typename Alloc = std::allocator<std::pair<const Key, Value>>>
  71 class btree_map
  72     : public internal::btree_map_container<
  73           internal::btree<internal::map_params<
  74               Key, Value, Compare, Alloc, /*TargetNodeSize=*/256,
  75               /*Multi=*/false>>> {
  76
  77   using Base = typename btree_map::btree_map_container;
  78
  79  public:
  80   // Default constructor.
  81   btree_map() = default;
  82   using Base::Base;
  83 };
  84
  85 // btree::swap(btree::btree_map<>, btree::btree_map<>)
  86 //
  87 // Swaps the contents of two `btree::btree_map` containers.
  88 template <typename K, typename V, typename C, typename A>
  89 void swap(btree_map<K, V, C, A> &x, btree_map<K, V, C, A> &y) {
  90   return x.swap(y);
  91 }
  92
  93 // btree::erase_if(btree::btree_map<>, Pred)
  94 //
  95 // Erases all elements that satisfy the predicate pred from the container.
  96 template <typename K, typename V, typename C, typename A, typename Pred>
  97 void erase_if(btree_map<K, V, C, A> &map, Pred pred) {
  98   for (auto it = map.begin(); it != map.end();) {
  99     if (pred(*it)) {
 100       it = map.erase(it);
 101     } else {
 102       ++it;
 103     }
 104   }
 105 }
 106
 107 // btree::btree_multimap
 108 //
 109 // A `btree::btree_multimap<K, V>` is an ordered associative container of
 110 // keys and associated values designed to be a more efficient replacement for
 111 // `std::multimap` (in most cases). Unlike `btree::btree_map`, a B-tree multimap
 112 // allows multiple elements with equivalent keys.
 113 //
 114 // Keys are sorted using an (optional) comparison function, which defaults to
 115 // `std::less<K>`.
 116 //
 117 // A `btree::btree_multimap<K, V>` uses a default allocator of
 118 // `std::allocator<std::pair<const K, V>>` to allocate (and deallocate)
 119 // nodes, and construct and destruct values within those nodes. You may
 120 // instead specify a custom allocator `A` (which in turn requires specifying a
 121 // custom comparator `C`) as in `btree::btree_multimap<K, V, C, A>`.
 122 //
 123 template <typename Key, typename Value, typename Compare = std::less<Key>,
 124           typename Alloc = std::allocator<std::pair<const Key, Value>>>
 125 class btree_multimap
 126     : public internal::btree_multimap_container<
 127           internal::btree<internal::map_params<
 128               Key, Value, Compare, Alloc, /*TargetNodeSize=*/256,
 129               /*Multi=*/true>>> {
 130   using Base = typename btree_multimap::btree_multimap_container;
 131
 132  public:
 133   btree_multimap() = default;
 134   using Base::Base;
 135 };
 136
 137 // btree::swap(btree::btree_multimap<>, btree::btree_multimap<>)
 138 //
 139 // Swaps the contents of two `btree::btree_multimap` containers.
 140 template <typename K, typename V, typename C, typename A>
 141 void swap(btree_multimap<K, V, C, A> &x, btree_multimap<K, V, C, A> &y) {
 142   return x.swap(y);
 143 }
 144
 145 // btree::erase_if(btree::btree_multimap<>, Pred)
 146 //
 147 // Erases all elements that satisfy the predicate pred from the container.
 148 template <typename K, typename V, typename C, typename A, typename Pred>
 149 void erase_if(btree_multimap<K, V, C, A> &map, Pred pred) {
 150   for (auto it = map.begin(); it != map.end();) {
 151     if (pred(*it)) {
 152       it = map.erase(it);
 153     } else {
 154       ++it;
 155     }
 156   }
 157 }
 158
 159 } // namespace btree