• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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     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