1 /* 2 * Copyright (C) 2017 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_TRACING_CORE_ID_ALLOCATOR_H_ 18 #define SRC_TRACING_CORE_ID_ALLOCATOR_H_ 19 20 #include <stdint.h> 21 22 #include <cstddef> 23 #include <type_traits> 24 #include <vector> 25 26 namespace perfetto { 27 28 // Handles assigment of IDs (int types) from a fixed-size pool. 29 // Zero is not considered a valid ID. 30 // The base class takes always a uint32_t and the derived class casts and checks 31 // bounds at compile time. This is to avoid bloating code with different 32 // instances of the main class for each size. 33 class IdAllocatorGeneric { 34 public: 35 // |max_id| is inclusive. 36 explicit IdAllocatorGeneric(uint32_t max_id); 37 ~IdAllocatorGeneric(); 38 39 // Returns an ID in the range [1, max_id] or 0 if no more ids are available. 40 uint32_t AllocateGeneric(); 41 void FreeGeneric(uint32_t); 42 43 bool IsEmpty() const; 44 45 private: 46 IdAllocatorGeneric(const IdAllocatorGeneric&) = delete; 47 IdAllocatorGeneric& operator=(const IdAllocatorGeneric&) = delete; 48 49 const uint32_t max_id_; 50 uint32_t last_id_ = 0; 51 std::vector<bool> ids_; 52 }; 53 54 template <typename T = uint32_t> 55 class IdAllocator : public IdAllocatorGeneric { 56 public: IdAllocator(T end)57 explicit IdAllocator(T end) : IdAllocatorGeneric(end) { 58 static_assert(std::is_integral<T>::value && std::is_unsigned<T>::value, 59 "T must be an unsigned integer"); 60 static_assert(sizeof(T) <= sizeof(uint32_t), "T is too big"); 61 } 62 Allocate()63 T Allocate() { return static_cast<T>(AllocateGeneric()); } 64 65 // Tries to allocate `n` IDs. Returns a vector of `n` valid IDs or an empty 66 // vector, if not enough IDs are available. AllocateMultiple(size_t n)67 std::vector<T> AllocateMultiple(size_t n) { 68 std::vector<T> res; 69 res.reserve(n); 70 for (size_t i = 0; i < n; i++) { 71 T id = Allocate(); 72 if (id) { 73 res.push_back(id); 74 } else { 75 for (T free_id : res) { 76 Free(free_id); 77 } 78 return {}; 79 } 80 } 81 return res; 82 } 83 Free(T id)84 void Free(T id) { FreeGeneric(id); } 85 }; 86 87 } // namespace perfetto 88 89 #endif // SRC_TRACING_CORE_ID_ALLOCATOR_H_ 90