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