1 /*
2 * Copyright (C) 2018 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #ifndef SRC_PROFILING_COMMON_INTERNER_H_
18 #define SRC_PROFILING_COMMON_INTERNER_H_
19
20 #include <stddef.h>
21 #include <stdint.h>
22 #include <functional>
23 #include <unordered_set>
24
25 #include "perfetto/base/logging.h"
26
27 namespace perfetto {
28 namespace profiling {
29
30 using InternID = uint32_t;
31
32 // Interner that hands out refcounted references.
33 template <typename T>
34 class Interner {
35 private:
36 struct Entry {
37 template <typename... U>
EntryEntry38 Entry(Interner<T>* in, InternID i, U... args)
39 : data(std::forward<U...>(args...)), id(i), interner(in) {}
40
41 bool operator<(const Entry& other) const { return data < other.data; }
42 bool operator==(const Entry& other) const { return data == other.data; }
43
44 struct Hash {
operatorEntry::Hash45 size_t operator()(const Entry& e) const noexcept {
46 return std::hash<T>{}(e.data);
47 }
48 };
49
50 const T data;
51 InternID id;
52 size_t ref_count = 0;
53 Interner<T>* interner;
54 };
55
56 public:
57 class Interned {
58 public:
59 friend class Interner<T>;
Interned(Entry * entry)60 explicit Interned(Entry* entry) : entry_(entry) {}
Interned(const Interned & other)61 Interned(const Interned& other) : entry_(other.entry_) {
62 if (entry_ != nullptr)
63 entry_->ref_count++;
64 }
65
Interned(Interned && other)66 Interned(Interned&& other) noexcept : entry_(other.entry_) {
67 other.entry_ = nullptr;
68 }
69
70 Interned& operator=(Interned other) noexcept {
71 using std::swap;
72 swap(*this, other);
73 return *this;
74 }
75
data()76 const T& data() const { return entry_->data; }
77
id()78 InternID id() const { return entry_->id; }
79
~Interned()80 ~Interned() {
81 if (entry_ != nullptr)
82 entry_->interner->Return(entry_);
83 }
84
85 bool operator<(const Interned& other) const {
86 return entry_ < other.entry_;
87 }
88
89 bool operator==(const Interned& other) const {
90 return entry_ == other.entry_;
91 }
92
93 const T* operator->() const { return &entry_->data; }
94
95 private:
96 Interner::Entry* entry_;
97 };
98
99 template <typename... U>
Intern(U...args)100 Interned Intern(U... args) {
101 Entry item(this, next_id, std::forward<U...>(args...));
102 auto it = entries_.find(item);
103 if (it == entries_.cend()) {
104 // This does not invalidate pointers to entries we hold in Interned. See
105 // https://timsong-cpp.github.io/cppwp/n3337/unord.req#8
106 auto it_and_inserted = entries_.emplace(std::move(item));
107 next_id++;
108 it = it_and_inserted.first;
109 PERFETTO_DCHECK(it_and_inserted.second);
110 }
111 Entry& entry = const_cast<Entry&>(*it);
112 entry.ref_count++;
113 return Interned(&entry);
114 }
115
~Interner()116 ~Interner() { PERFETTO_DCHECK(entries_.empty()); }
117
entry_count_for_testing()118 size_t entry_count_for_testing() { return entries_.size(); }
119
120 private:
Return(Entry * entry)121 void Return(Entry* entry) {
122 if (--entry->ref_count == 0)
123 entries_.erase(*entry);
124 }
125
126 InternID next_id = 1;
127 std::unordered_set<Entry, typename Entry::Hash> entries_;
128 static_assert(sizeof(Interned) == sizeof(void*),
129 "interned things should be small");
130 };
131
132 template <typename T>
swap(typename Interner<T>::Interned a,typename Interner<T>::Interned b)133 void swap(typename Interner<T>::Interned a, typename Interner<T>::Interned b) {
134 std::swap(a.entry_, b.entry_);
135 }
136
137 template <typename T>
138 using Interned = typename Interner<T>::Interned;
139
140 } // namespace profiling
141 } // namespace perfetto
142
143 #endif // SRC_PROFILING_COMMON_INTERNER_H_
144