CMS 3D CMS Logo

OtherHashMaps.h
Go to the documentation of this file.
1 #ifndef TrackingTools_TrajectoryCleaning_src_OtherHashMaps
2 #define TrackingTools_TrajectoryCleaning_src_OtherHashMaps
3 
4 #include <functional>
5 #include <iostream>
6 #include <iterator>
7 #include <list>
8 #include <map>
9 #include <memory>
10 #include <type_traits>
11 #include <vector>
12 
13 namespace cmsutil {
14 
15  /*** The concept is the same of std::map<K, std::vector<V>>, but the implementation is much different (and the interface is not really compatible)
16  * It works only for K and V objects with trivial destructors (primitive types and bare pointers are fine)
17  * The main implementation difference w.r.t. unordered_map<K, std::vector<V>> is that this map is optimized to do very few memory allocations
18  * (in particular, clear does not redeme memory so if you just clear the map instead of deleting it you won't call malloc each time you fill it)
19  * The map doesn't rehash, so you should set a reasonable number of buckets (that you can change also when clearing the map)
20  * Note that too many buckets will make your map slow to clear (and possibly more prone to cache misses).
21  * Although it can take an allocator as template argument, it has been tested only with std::allocator.
22  * When used in the TrajectoryCleanerBySharedHits it works and it does improve the performance. Any other usecase was not checked at all.
23  * */
24  template <typename K,
25  typename V,
26  typename Hasher = std::hash<K>,
27  typename Equals = std::equal_to<K>,
28  typename Alloc = std::allocator<V> >
30  // taking Alloc definition from http://www.codeproject.com/KB/cpp/allocator.aspx
31  static_assert(std::conjunction<std::is_trivially_destructible<K>, std::is_trivially_destructible<V> >::value);
32 
33  public:
34  typedef Hasher hasher;
36  typedef typename std::conditional<std::is_pointer<V>::value, V, V const &>::type
37  value_ref; // otherwise we get problems with 'const' if V is a pointer
38 
39  SimpleAllocHashMultiMap(size_t buckets, size_t keyRowSize, size_t valueRowSize, size_t maxRows = 50);
40 
42 
43  void clear(size_t newBucketSize = 0) {
44  if (newBucketSize != 0) {
45  if (newBucketSize > bucketCapacity_) {
46  ptrAlloc_.deallocate(buckets_, bucketCapacity_);
47  bucketCapacity_ = newBucketSize;
49  }
50  bucketSize_ = newBucketSize;
51  }
52  memset(buckets_, 0, bucketSize_ * sizeof(KeyItem *));
53  currentKeyRow_ = keyRows_.begin();
54  nextKeyItem_ = keyRows_.front();
56  currentValueRow_ = valueRows_.begin();
57  nextValueItem_ = valueRows_.front();
59  if ((keyRows_.size() > maxRows_) || (valueRows_.size() > maxRows_))
60  freeRows();
61  }
62  void freeRows();
63 
64  bool empty() const { return nextKeyItem_ == keyRows_.front(); }
65 
66  void insert(K const &key, value_ref value);
67 
68  struct ValueItem {
69  ValueItem(ValueItem *next1, value_ref val) : next(next1), value(val) {}
72  typedef V value_type;
73  const value_type &operator()() const { return value; }
74  };
75 
76  struct KeyItem {
77  KeyItem(KeyItem *next1, K const &key1, ValueItem *val1) : key(key1), next(next1), value(val1) {}
78  K key;
82  const value_type &operator()() const { return *this; }
83  };
84 
85  template <typename Item>
86  class item_iterator {
87  public:
88  typedef ::std::forward_iterator_tag iterator_category;
89  typedef const typename Item::value_type value_type;
90  typedef const value_type &reference;
91  typedef const value_type *pointer;
92  typedef ptrdiff_t difference_type;
94 
95  item_iterator() : it_(nullptr) {}
96  item_iterator(const Item *it) : it_(it) {}
97  const value_type &operator*() const { return (*it_)(); }
98  const value_type *operator->() const { return &(*it_)(); }
100  if (it_ != nullptr)
101  it_ = it_->next;
102  return *this;
103  }
104  bool operator==(const self_type &other) const { return it_ == other.it_; }
105  bool operator!=(const self_type &other) const { return it_ != other.it_; }
106  bool good() const { return (it_ != nullptr); }
107 
108  private:
109  const Item *it_;
110  };
112 
113  value_iterator values(K const &key);
114 
115  private:
116  using AllocTraits = std::allocator_traits<Alloc>;
117  using KeyItemAllocator = typename AllocTraits::template rebind_alloc<KeyItem>;
118  using KeyItemPtrAllocator = typename AllocTraits::template rebind_alloc<KeyItem *>;
119  using ValueItemAllocator = typename AllocTraits::template rebind_alloc<ValueItem>;
120 
121  // --- buckets ---
124  // --- keys ---
125  size_t keyRowSize_;
126  std::list<KeyItem *> keyRows_;
127  typename std::list<KeyItem *>::iterator
128  currentKeyRow_; // last row that is currently in use. nextItem_ and the last valid item are both on this row. it is never rows_.end()
130  // --- values ---
132  std::list<ValueItem *> valueRows_;
133  typename std::list<ValueItem *>::iterator
134  currentValueRow_; // last row that is currently in use. nextItem_ and the last valid item are both on this row. it is never rows_.end()
136  // --- other ---
137  size_t maxRows_;
138  Hasher hasher_;
139  Equals eq_;
143 
144  KeyItem *push_back_(K const &key, KeyItem *next);
146  KeyItem &find_or_insert_(K const &key);
147 
148  public:
149  void dump() {
150  std::cout << "Dumping HASH MULTIMAP" << std::endl;
151  std::cout << " Key items: "
153  << std::endl;
154  std::cout << " Value items: "
157  << std::endl;
158  size_t row = 0;
159  std::cout << " Buckets (size " << bucketSize_ << ", capacity " << bucketCapacity_ << ")";
160  for (KeyItem **p = buckets_; p != buckets_ + bucketSize_; ++p, ++row) {
161  std::cout << " [" << row << "] " << *p << std::endl;
162  }
163  row = 0;
164  std::cout << " Key Items " << std::endl;
165  for (typename std::list<KeyItem *>::iterator it = keyRows_.begin(), last = keyRows_.end(); it != last;
166  ++it, ++row) {
167  KeyItem *lastI = *it + keyRowSize_;
168  std::cout << " Key Row " << row << " (of size " << keyRowSize_ << ")" << std::endl;
169  for (KeyItem *p = *it; p != lastI; ++p) {
170  std::cout << " @ " << p << " [" << p->key << ", @" << p->value << "], next = " << p->next << std::endl;
171  if ((it == currentKeyRow_) && (p == nextKeyItem_ - 1)) {
172  std::cout << " ^^^ this was the last valid item." << std::endl;
173  last = 0;
174  break;
175  }
176  }
177  if (lastI == 0)
178  break;
179  }
180  row = 0;
181  std::cout << " Value Items " << std::endl;
182  for (typename std::list<ValueItem *>::iterator it = valueRows_.begin(), last = valueRows_.end(); it != last;
183  ++it, ++row) {
184  ValueItem *lastI = *it + valueRowSize_;
185  std::cout << " Value Row " << row << " (of size " << valueRowSize_ << ")" << std::endl;
186  for (ValueItem *p = *it; p != lastI; ++p) {
187  std::cout << " @ " << p << " [" << p->value << "], next = " << p->next << std::endl;
188  if ((it == currentValueRow_) && (p == nextValueItem_ - 1)) {
189  std::cout << " ^^^ this was the last valid item." << std::endl;
190  last = 0;
191  break;
192  }
193  }
194  if (lastI == 0)
195  break;
196  }
197  std::cout << " End of dump" << std::endl;
198  }
199  };
200 
201  template <typename K, typename V, typename Hasher, typename Equals, typename Alloc>
203  size_t keyRowSize,
204  size_t valueRowSize,
205  size_t maxRows)
206  : bucketSize_(buckets),
207  bucketCapacity_(bucketSize_),
208  keyRowSize_(keyRowSize),
209  valueRowSize_(valueRowSize),
210  maxRows_(maxRows) {
211  buckets_ = ptrAlloc_.allocate(bucketCapacity_);
212  keyRows_.push_back(keyAlloc_.allocate(keyRowSize_));
213  valueRows_.push_back(valueAlloc_.allocate(valueRowSize_));
214  clear();
215  }
216  template <typename K, typename V, typename Hasher, typename Equals, typename Alloc>
218  for (typename std::list<KeyItem *>::iterator it = keyRows_.begin(), last = keyRows_.end(); it != last; ++it) {
219  keyAlloc_.deallocate(*it, keyRowSize_);
220  }
221  for (typename std::list<ValueItem *>::iterator it = valueRows_.begin(), last = valueRows_.end(); it != last; ++it) {
222  valueAlloc_.deallocate(*it, valueRowSize_);
223  }
224  ptrAlloc_.deallocate(buckets_, bucketCapacity_);
225  }
226 
227  template <typename K, typename V, typename Hasher, typename Equals, typename Alloc>
229  if (keyRows_.size() > maxRows_) {
230  //std::cerr << "Freeing key rows, current size is " << keyRows_.size() << std::endl;
231  typename std::list<KeyItem *>::iterator it = keyRows_.begin(), last = keyRows_.end();
232  for (std::advance(it, maxRows_); it != last; ++it) {
233  keyAlloc_.deallocate(*it, keyRowSize_);
234  }
235  keyRows_.resize(maxRows_);
236  }
237  if (valueRows_.size() > maxRows_) {
238  //std::cerr << "Freeing value rows, current size is " << valueRows_.size() << std::endl;
239  typename std::list<ValueItem *>::iterator it = valueRows_.begin(), last = valueRows_.end();
240  for (std::advance(it, maxRows_); it != last; ++it) {
241  valueAlloc_.deallocate(*it, valueRowSize_);
242  }
243  valueRows_.resize(maxRows_);
244  }
245  }
246 
247  template <typename K, typename V, typename Hasher, typename Equals, typename Alloc>
250  if (nextKeyItem_ == keyEndMarker_) {
251  ++currentKeyRow_;
252  if (currentKeyRow_ == keyRows_.end()) {
253  keyRows_.push_back(keyAlloc_.allocate(keyRowSize_));
254  currentKeyRow_ = keyRows_.end();
255  --currentKeyRow_; // end - 1 doesn't work!
256  }
257  nextKeyItem_ = *currentKeyRow_;
258  keyEndMarker_ = nextKeyItem_ + keyRowSize_;
259  }
260  std::allocator_traits<KeyItemAllocator>::construct(keyAlloc_, nextKeyItem_, KeyItem(next, key, nullptr));
261  nextKeyItem_++;
262  return (nextKeyItem_ - 1);
263  }
264  template <typename K, typename V, typename Hasher, typename Equals, typename Alloc>
267  if (nextValueItem_ == valueEndMarker_) {
268  ++currentValueRow_;
269  if (currentValueRow_ == valueRows_.end()) {
270  valueRows_.push_back(valueAlloc_.allocate(valueRowSize_));
271  currentValueRow_ = valueRows_.end();
272  --currentValueRow_; // end - 1 doesn't work!
273  }
274  nextValueItem_ = *currentValueRow_;
275  valueEndMarker_ = nextValueItem_ + valueRowSize_;
276  }
278  nextValueItem_++;
279  return (nextValueItem_ - 1);
280  }
281 
282  template <typename K, typename V, typename Hasher, typename Equals, typename Alloc>
285  //std::cout << "Find or insert for key " << key << std::endl;
286  size_t hash = hasher_(key);
287  KeyItem *&buck = buckets_[hash % bucketSize_];
288  KeyItem *curr = buck;
289  while (curr) {
290  if (eq_(curr->key, key)) {
291  //std::cout << " Key " << key << " was found." << std::endl;
292  return *curr;
293  }
294  curr = curr->next;
295  }
296  buck = push_back_(key, buck);
297  return *buck;
298  }
299 
300  template <typename K, typename V, typename Hasher, typename Equals, typename Alloc>
302  //std::cout << "Pushing back value " << value << " for key " << key << std::endl;
303  KeyItem &k = find_or_insert_(key);
304  //std::cout << "Key " << (k.value ? "exists" : " is new") << std::endl;
305  k.value = push_back_(value, k.value);
306  }
307 
308  template <typename K, typename V, typename Hasher, typename Equals, typename Alloc>
311  //std::cout << "Gettinv values for key " << key << std::endl;
312  size_t hash = hasher_(key);
313  for (KeyItem *curr = buckets_[hash % bucketSize_]; curr; curr = curr->next) {
314  if (eq_(curr->key, key))
315  return value_iterator(curr->value);
316  }
317  return value_iterator();
318  }
319 
320  /*** Very very simple map implementation
321  * It's just a std::vector<pair<key,value>>, and the operator[] does a linear search to find the key (it's O(N) time, both if the key exists and if it doesn't)
322  * Anyway, if your map is very small and if you clear it often, it performs better than more complex variants
323  * Semantics is as std::map, except that only very few methods are implemented.
324  * */
325  template <typename K, typename V>
327  public:
328  typedef std::pair<K, V> value_type;
329  typedef typename std::vector<value_type>::const_iterator const_iterator;
330  typedef typename std::vector<value_type>::iterator iterator; // but please don't mutate the keys
331 
332  void clear() { data_.clear(); }
333  bool empty() const { return data_.empty(); }
334  const_iterator begin() const { return data_.begin(); }
335  const_iterator end() const { return data_.end(); }
336  iterator begin() { return data_.begin(); }
337  iterator end() { return data_.end(); }
338 
339  V &operator[](const K &k) {
340  for (typename std::vector<value_type>::iterator it = data_.begin(), ed = data_.end(); it != ed; ++it) {
341  if (it->first == k)
342  return it->second;
343  }
344  data_.push_back(value_type(k, V()));
345  return data_.back().second;
346  }
347 
349 
350  private:
351  std::vector<value_type> data_;
352  };
353 
354 } // namespace cmsutil
355 
356 #endif
typename AllocTraits::template rebind_alloc< KeyItem > KeyItemAllocator
item_iterator< ValueItem > value_iterator
std::conditional< std::is_pointer< V >::value, V, V const & >::type value_ref
Definition: OtherHashMaps.h:37
std::list< ValueItem * > valueRows_
std::allocator_traits< Alloc > AllocTraits
KeyItem & find_or_insert_(K const &key)
const_iterator end() const
uint32_t T const *__restrict__ uint32_t const *__restrict__ int32_t int Histo::index_type cudaStream_t V
bool operator!=(const self_type &other) const
SimpleAllocHashMultiMap< K, V, Hasher, Equals, Alloc > map_type
Definition: OtherHashMaps.h:35
typename AllocTraits::template rebind_alloc< KeyItem * > KeyItemPtrAllocator
::std::forward_iterator_tag iterator_category
Definition: OtherHashMaps.h:88
std::list< ValueItem * >::iterator currentValueRow_
KeyItem * push_back_(K const &key, KeyItem *next)
ValueItem(ValueItem *next1, value_ref val)
Definition: OtherHashMaps.h:69
key
prepare the HTCondor submission files and eventually submit them
def template(fileName, svg, replaceme="REPLACEME")
Definition: svgfig.py:521
bool operator==(const self_type &other) const
void insert(K const &key, value_ref value)
const value_type & operator()() const
Definition: OtherHashMaps.h:73
Definition: value.py:1
value_iterator values(K const &key)
std::vector< value_type >::const_iterator const_iterator
std::vector< value_type > data_
std::vector< value_type >::iterator iterator
const value_type & operator()() const
Definition: OtherHashMaps.h:82
const_iterator begin() const
void clear(size_t newBucketSize=0)
Definition: OtherHashMaps.h:43
std::unique_ptr< GeometricDet > construct(DDCompactView const &cpv, std::vector< int > const &detidShifts)
std::list< KeyItem * > keyRows_
KeyItem(KeyItem *next1, K const &key1, ValueItem *val1)
Definition: OtherHashMaps.h:77
SimpleAllocHashMultiMap(size_t buckets, size_t keyRowSize, size_t valueRowSize, size_t maxRows=50)
typename AllocTraits::template rebind_alloc< ValueItem > ValueItemAllocator
std::list< KeyItem * >::iterator currentKeyRow_