1 // 2 // Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2021 3 // 4 // Distributed under the Boost Software License, Version 1.0. (See accompanying 5 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 6 // 7 #pragma once 8 9 #include "td/utils/common.h" 10 11 #include <limits> 12 13 namespace td { 14 15 // 1. Allocates all objects in vector. (but vector never shrinks) 16 // 2. Id is safe way to reach this object. 17 // 3. All ids are unique. 18 // 4. All ids are non-zero. 19 template <class DataT> 20 class Container { 21 public: 22 using Id = uint64; get(Id id)23 DataT *get(Id id) { 24 int32 slot_id = decode_id(id); 25 if (slot_id == -1) { 26 return nullptr; 27 } 28 return &slots_[slot_id].data; 29 } 30 erase(Id id)31 void erase(Id id) { 32 int32 slot_id = decode_id(id); 33 if (slot_id == -1) { 34 return; 35 } 36 release(slot_id); 37 } 38 extract(Id id)39 DataT extract(Id id) { 40 int32 slot_id = decode_id(id); 41 CHECK(slot_id != -1); 42 auto res = std::move(slots_[slot_id].data); 43 release(slot_id); 44 return res; 45 } 46 47 Id create(DataT &&data = DataT(), uint8 type = 0) { 48 int32 id = store(std::move(data), type); 49 return encode_id(id); 50 } 51 reset_id(Id id)52 Id reset_id(Id id) { 53 int32 slot_id = decode_id(id); 54 CHECK(slot_id != -1); 55 inc_generation(slot_id); 56 return encode_id(slot_id); 57 } 58 type_from_id(Id id)59 static uint8 type_from_id(Id id) { 60 return static_cast<uint8>(id); 61 } 62 ids()63 vector<Id> ids() { 64 vector<bool> is_bad(slots_.size(), false); 65 for (auto id : empty_slots_) { 66 is_bad[id] = true; 67 } 68 vector<Id> res; 69 for (size_t i = 0, n = slots_.size(); i < n; i++) { 70 if (!is_bad[i]) { 71 res.push_back(encode_id(static_cast<int32>(i))); 72 } 73 } 74 return res; 75 } 76 template <class F> for_each(const F & f)77 void for_each(const F &f) { 78 auto ids = this->ids(); 79 for (auto id : ids) { 80 f(id, *get(id)); 81 } 82 } size()83 size_t size() const { 84 CHECK(empty_slots_.size() <= slots_.size()); 85 return slots_.size() - empty_slots_.size(); 86 } empty()87 bool empty() const { 88 return size() == 0; 89 } clear()90 void clear() { 91 *this = Container<DataT>(); 92 } 93 94 private: 95 static constexpr uint32 GENERATION_STEP = 1 << 8; 96 static constexpr uint32 TYPE_MASK = (1 << 8) - 1; 97 struct Slot { 98 uint32 generation; 99 DataT data; 100 }; 101 vector<Slot> slots_; 102 vector<int32> empty_slots_; 103 encode_id(int32 id)104 Id encode_id(int32 id) const { 105 return (static_cast<uint64>(id) << 32) | slots_[id].generation; 106 } 107 decode_id(Id id)108 int32 decode_id(Id id) const { 109 auto slot_id = static_cast<int32>(id >> 32); 110 auto generation = static_cast<uint32>(id); 111 if (slot_id < 0 || slot_id >= static_cast<int32>(slots_.size())) { 112 return -1; 113 } 114 if (generation != slots_[slot_id].generation) { 115 return -1; 116 } 117 return slot_id; 118 } 119 store(DataT && data,uint8 type)120 int32 store(DataT &&data, uint8 type) { 121 int32 pos; 122 if (!empty_slots_.empty()) { 123 pos = empty_slots_.back(); 124 empty_slots_.pop_back(); 125 slots_[pos].data = std::move(data); 126 slots_[pos].generation ^= (slots_[pos].generation & TYPE_MASK) ^ type; 127 } else { 128 CHECK(slots_.size() <= static_cast<size_t>(std::numeric_limits<int32>::max())); 129 pos = static_cast<int32>(slots_.size()); 130 slots_.push_back(Slot{GENERATION_STEP + type, std::move(data)}); 131 } 132 return pos; 133 } 134 release(int32 id)135 void release(int32 id) { 136 inc_generation(id); 137 slots_[id].data = DataT(); 138 if (slots_[id].generation & ~TYPE_MASK) { // generation overflow. Can't use this id anymore 139 empty_slots_.push_back(id); 140 } 141 } 142 inc_generation(int32 id)143 void inc_generation(int32 id) { 144 slots_[id].generation += GENERATION_STEP; 145 } 146 }; 147 148 } // namespace td 149