| /* |
| * Copyright (C) 2019 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| #ifndef INCLUDE_PERFETTO_BASE_FLAT_SET_H_ |
| #define INCLUDE_PERFETTO_BASE_FLAT_SET_H_ |
| |
| #include <algorithm> |
| #include <vector> |
| |
| // A vector-based set::set-like container. |
| // It's more cache friendly than std::*set and performs for cases where: |
| // 1. A high number of dupes is expected (e.g. pid tracking in ftrace). |
| // 2. The working set is small (hundreds of elements). |
| |
| // Performance characteristics (for uniformly random insertion order): |
| // - For smaller insertions (up to ~500), it outperforms both std::set<int> and |
| // std::unordered_set<int> by ~3x. |
| // - Up until 4k insertions, it is always faster than std::set<int>. |
| // - unordered_set<int> is faster with more than 2k insertions. |
| // - unordered_set, however, it's less memory efficient and has more caveats |
| // (see chromium's base/containers/README.md). |
| // |
| // See flat_set_benchmark.cc and the charts in go/perfetto-int-set-benchmark. |
| |
| namespace perfetto { |
| namespace base { |
| |
| template <typename T> |
| class FlatSet { |
| public: |
| using value_type = T; |
| using const_pointer = const T*; |
| using iterator = typename std::vector<T>::iterator; |
| using const_iterator = typename std::vector<T>::const_iterator; |
| |
| FlatSet() = default; |
| |
| // Mainly for tests. Deliberately not marked as "explicit". |
| FlatSet(std::initializer_list<T> initial) : entries_(initial) { |
| std::sort(entries_.begin(), entries_.end()); |
| entries_.erase(std::unique(entries_.begin(), entries_.end()), |
| entries_.end()); |
| } |
| |
| const_iterator find(T value) const { |
| auto entries_end = entries_.end(); |
| auto it = std::lower_bound(entries_.begin(), entries_end, value); |
| return (it != entries_end && *it == value) ? it : entries_end; |
| } |
| |
| size_t count(T value) const { return find(value) == entries_.end() ? 0 : 1; } |
| |
| std::pair<iterator, bool> insert(T value) { |
| auto entries_end = entries_.end(); |
| auto it = std::lower_bound(entries_.begin(), entries_end, value); |
| if (it != entries_end && *it == value) |
| return std::make_pair(it, false); |
| // If the value is not found |it| is either end() or the next item strictly |
| // greater than |value|. In both cases we want to insert just before that. |
| it = entries_.insert(it, std::move(value)); |
| return std::make_pair(it, true); |
| } |
| |
| size_t erase(T value) { |
| auto it = find(value); |
| if (it == entries_.end()) |
| return 0; |
| entries_.erase(it); |
| return 1; |
| } |
| |
| void clear() { entries_.clear(); } |
| |
| bool empty() const { return entries_.empty(); } |
| void reserve(size_t n) { entries_.reserve(n); } |
| size_t size() const { return entries_.size(); } |
| const_iterator begin() const { return entries_.begin(); } |
| const_iterator end() const { return entries_.end(); } |
| |
| private: |
| std::vector<T> entries_; |
| }; |
| |
| } // namespace base |
| } // namespace perfetto |
| |
| #endif // INCLUDE_PERFETTO_BASE_FLAT_SET_H_ |