1 // Copyright 2020 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef V8_CRDTP_FIND_BY_FIRST_H_
6 #define V8_CRDTP_FIND_BY_FIRST_H_
7
8 #include <algorithm>
9 #include <cstdint>
10 #include <memory>
11 #include <vector>
12
13 #include "export.h"
14 #include "span.h"
15
16 namespace v8_crdtp {
17 // =============================================================================
18 // FindByFirst - Retrieval from a sorted vector that's keyed by span<uint8_t>.
19 // =============================================================================
20
21 // Given a vector of pairs sorted by the first element of each pair, find
22 // the corresponding value given a key to be compared to the first element.
23 // Together with std::inplace_merge and pre-sorting or std::sort, this can
24 // be used to implement a minimalistic equivalent of Chromium's flat_map.
25
26 // In this variant, the template parameter |T| is a value type and a
27 // |default_value| is provided.
28 template <typename T>
FindByFirst(const std::vector<std::pair<span<uint8_t>,T>> & sorted_by_first,span<uint8_t> key,T default_value)29 T FindByFirst(const std::vector<std::pair<span<uint8_t>, T>>& sorted_by_first,
30 span<uint8_t> key,
31 T default_value) {
32 auto it = std::lower_bound(
33 sorted_by_first.begin(), sorted_by_first.end(), key,
34 [](const std::pair<span<uint8_t>, T>& left, span<uint8_t> right) {
35 return SpanLessThan(left.first, right);
36 });
37 return (it != sorted_by_first.end() && SpanEquals(it->first, key))
38 ? it->second
39 : default_value;
40 }
41
42 // In this variant, the template parameter |T| is a class or struct that's
43 // instantiated in std::unique_ptr, and we return either a T* or a nullptr.
44 template <typename T>
FindByFirst(const std::vector<std::pair<span<uint8_t>,std::unique_ptr<T>>> & sorted_by_first,span<uint8_t> key)45 T* FindByFirst(const std::vector<std::pair<span<uint8_t>, std::unique_ptr<T>>>&
46 sorted_by_first,
47 span<uint8_t> key) {
48 auto it = std::lower_bound(
49 sorted_by_first.begin(), sorted_by_first.end(), key,
50 [](const std::pair<span<uint8_t>, std::unique_ptr<T>>& left,
51 span<uint8_t> right) { return SpanLessThan(left.first, right); });
52 return (it != sorted_by_first.end() && SpanEquals(it->first, key))
53 ? it->second.get()
54 : nullptr;
55 }
56 } // namespace v8_crdtp
57
58 #endif // V8_CRDTP_FIND_BY_FIRST_H_
59