tudocomp
– The TU Dortmund Compression Framework
DynamicSizeIPD.hpp
Go to the documentation of this file.
1 #pragma once
2 
3 #include <tudocomp/Algorithm.hpp>
6 
7 namespace tdc {namespace esp {
8  template<typename ipd_t>
9  class DynamicSizeIPD: public Algorithm {
10  template<typename X, size_t B>
11  struct SizeAdjust {
12  };
13 
14  template<size_t B>
15  struct SizeAdjust<size_t, B> {
16  using Type = uint_t<B>;
17 
18  inline static uint_t<B> cast_to(size_t val) {
19  return val;
20  }
21 
22  inline static size_t cast_from(uint_t<B> val) {
23  return val;
24  }
25  };
26 
27  template<size_t N, size_t B>
28  struct SizeAdjust<Array<N, size_t>, B> {
29  using Type = Array<N, uint_t<B>>;
30 
31  inline static Array<N, uint_t<B>> cast_to(Array<N, size_t> val) {
32  Array<N, uint_t<B>> ret;
33  for(size_t i = 0; i < ret.m_data.size(); i++) {
34  ret.m_data[i] = val.m_data[i];
35  }
36 
37  return ret;
38  }
39 
40  inline static Array<N, size_t> cast_from(Array<N, uint_t<B>> val) {
41  Array<N, size_t> ret;
42  for(size_t i = 0; i < ret.m_data.size(); i++) {
43  ret.m_data[i] = val.m_data[i];
44  }
45 
46  return ret;
47  }
48  };
49  public:
50  inline static Meta meta() {
51  Meta m("ipd", "dynamic_size");
52  m.option("ipd").templated<ipd_t>("ipd");
53  return m;
54  };
55 
57 
58  template<size_t N, typename K, typename V>
59  class IPDMap {
60  inline static K key_max(const Array<N, K>& ka) {
61  K val = 0;
62  for (auto x : ka.as_view()) {
63  val = std::max(val, x);
64  }
65  return val;
66  }
67 
68  struct DynamicMap {
69  using Updater = std::function<void(V&)>;
70  using ForEach = std::function<void(const Array<N, K>&, const V&)>;
71 
72  virtual ~DynamicMap() {}
73 
74  virtual V access(const Array<N, K>& key, Updater updater) = 0;
75  virtual size_t size() const = 0;
76  virtual void for_all(ForEach f) const = 0;
77  virtual bool can_fit_value(V new_val) const = 0;
78  virtual bool can_fit_key(const Array<N, K>& key) const = 0;
79  };
80  template<size_t BK, size_t BV>
81  struct DynamicMapOf: DynamicMap {
82  using Updater = typename DynamicMap::Updater;
83  using ForEach = typename DynamicMap::ForEach;
84  using MappedK = typename SizeAdjust<K, BK>::Type;
85  using MappedV = typename SizeAdjust<V, BV>::Type;
86 
87  Array<N, MappedK> m_empty;
88  typename ipd_t::template IPDMap<N, MappedK, MappedV> m_map;
89 
90  inline DynamicMapOf(size_t bucket_count, const Array<N, K>& empty):
91  m_empty(SizeAdjust<Array<N, K>, BK>::cast_to(empty)),
92  m_map(bucket_count, m_empty) {}
93 
94  inline virtual size_t size() const override final {
95  return m_map.size();
96  }
97 
98  inline virtual void for_all(ForEach f) const override final {
99  m_map.for_all([&](const auto& key, const auto& val) {
100  const auto& key2 = SizeAdjust<Array<N, K>, BK>::cast_from(key);
101  const auto& val2 = SizeAdjust<V, BK>::cast_from(val);
102 
103  f(key2.as_view(), val2);
104  });
105  }
106 
107  inline virtual bool can_fit_value(V val) const override final {
108  return bits_for(val) <= BV;
109  }
110 
111  inline virtual bool can_fit_key(const Array<N, K>& key) const override final {
112  if (SizeAdjust<Array<N, K>, BK>::cast_to(key) == m_empty) {
113  return false;
114  }
115 
116  size_t val = key_max(key);
117  return bits_for(val) <= BK;
118  }
119 
120  inline virtual V access(const Array<N, K>& key, Updater updater) override final {
121  auto actual_key = SizeAdjust<Array<N, K>, BK>::cast_to(key);
122  return m_map.access(actual_key, [&](MappedV& val) {
123  V val2 = SizeAdjust<V, BV>::cast_from(val);
124  updater(val2);
125  val = SizeAdjust<V, BV>::cast_to(val2);
126  });
127  }
128  };
129 
130  Array<N, K> m_empty;
131  size_t m_map_bits = 0;
132  std::unique_ptr<DynamicMap> m_map;
133 
134  const static size_t INITIAL_BITS = 8;
135 
136  template<size_t B>
137  std::unique_ptr<DynamicMap> new_map(size_t bucket_count, const Array<N, K>& empty) {
138  return std::make_unique<DynamicMapOf<B, B>>(bucket_count, empty);
139  }
140 
141  inline void resize(size_t bits) {
142  std::unique_ptr<DynamicMap> n_map;
143  size_t n_bits = 0;
144 
145  // TODO: Calc bucket count correctly
146  size_t s = m_map->size();
147 
148  if (false) {}
149  else if (bits <= 8) { n_map = new_map<8> (s, m_empty); n_bits = 8; }
150  else if (bits <= 16) { n_map = new_map<16>(s, m_empty); n_bits = 16; }
151  else if (bits <= 24) { n_map = new_map<24>(s, m_empty); n_bits = 24; }
152  else if (bits <= 32) { n_map = new_map<32>(s, m_empty); n_bits = 32; }
153  else if (bits <= 40) { n_map = new_map<40>(s, m_empty); n_bits = 40; }
154  else if (bits <= 48) { n_map = new_map<48>(s, m_empty); n_bits = 48; }
155  else if (bits <= 56) { n_map = new_map<56>(s, m_empty); n_bits = 56; }
156  else if (bits <= 64) { n_map = new_map<64>(s, m_empty); n_bits = 64; }
157 
158  m_map->for_all([&](const auto& key, const auto& val) {
159  n_map->access(key, [&](auto& v) {
160  v = val;
161  });
162  });
163 
164  DCHECK_EQ(m_map->size(), n_map->size());
165  m_map = std::move(n_map);
166  m_map_bits = n_bits;
167  }
168 
169  inline void resize_key(const Array<N, K>& max_key) {
170  auto max = key_max(max_key);
171  resize(std::max(size_t(bits_for(max)), m_map_bits + 1));
172  }
173  inline void resize_val(V max_val) {
174  auto max = max_val;
175  resize(std::max(size_t(bits_for(max)), m_map_bits + 1));
176  }
177  public:
178  inline IPDMap(size_t bucket_count, const Array<N, K>& empty) {
179  m_empty = empty;
180  m_map_bits = INITIAL_BITS;
181  m_map = new_map<INITIAL_BITS>(bucket_count, m_empty);
182  }
183 
184  template<typename Updater>
185  inline V access(const Array<N, K>& key, Updater updater) {
186  if (!m_map->can_fit_key(key)) {
187  resize_key(key);
188  }
189 
190  auto copy = V();
191  bool value_resize = false;
192 
193  V ret = m_map->access(key, [&](V& val) {
194  copy = val;
195  updater(copy);
196  if (m_map->can_fit_value(copy)) {
197  val = copy;
198  } else {
199  value_resize = true;
200  }
201  });
202 
203  if (value_resize) {
204  resize_val(copy);
205  ret = m_map->access(key, [&](V& val) {
206  val = copy;
207  });
208  }
209 
210  DCHECK_EQ(ret, copy);
211 
212  return copy;
213  }
214 
215  inline size_t size() const {
216  return m_map->size();
217  }
218 
219  template<typename F>
220  void for_all(F f) const {
221  m_map->for_all(f);
222  }
223  };
224  };
225 }}
Contains the text compression and encoding framework.
Definition: namespaces.hpp:11
constexpr uint_fast8_t bits_for(size_t n)
Computes the number of bits required to store the given integer value.
Provides meta information about an Algorithm.
Definition: Meta.hpp:34
in_t as_view() const
Definition: HashArray.hpp:29
V access(const Array< N, K > &key, Updater updater)
Algorithm(Algorithm const &)=default
typename uint_dispatch_t< N >::type uint_t
Definition: uint_t.hpp:165
std::array< T, N > m_data
Definition: HashArray.hpp:15
void templated(const std::string &accepted_type)
Declares that this option accepts values of the specified Algorithm type T.
Definition: Meta.hpp:93
IPDMap(size_t bucket_count, const Array< N, K > &empty)
OptionBuilder option(const std::string &name)
Declares an accepted option for this algorithm.
Definition: Meta.hpp:216
Interface for algorithms.
Definition: Algorithm.hpp:15