Bitcoin ABC  0.26.3
P2P Digital Currency
shortidprocessor.h
Go to the documentation of this file.
1 // Copyright (c) 2022 The Bitcoin developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
5 #ifndef BITCOIN_SHORTIDPROCESSOR_H
6 #define BITCOIN_SHORTIDPROCESSOR_H
7 
8 #include <cassert>
9 #include <cstddef>
10 #include <cstdint>
11 #include <limits>
12 #include <unordered_map>
13 #include <utility>
14 #include <vector>
15 
16 template <typename PrefilledItemType, typename Adapter, typename ItemCompare>
17 class ShortIdProcessor : Adapter, ItemCompare {
18  using ItemType = typename std::remove_reference<
19  decltype(std::declval<Adapter &>().getItem(
20  std::declval<PrefilledItemType &>()))>::type;
21 
22  bool evenlyDistributed = true;
23  bool shortIdCollision = false;
24  bool outOfBoundIndex = false;
25 
26  std::vector<ItemType> itemsAvailable;
27  std::vector<bool> haveItem;
28  std::unordered_map<uint64_t, uint32_t> shortIdIndexMap;
29 
30  int addItem(uint32_t index, const ItemType &item) {
31  if (index >= itemsAvailable.size()) {
32  outOfBoundIndex = true;
33  return 0;
34  }
35 
36  if (!haveItem[index]) {
37  haveItem[index] = true;
38  itemsAvailable[index] = item;
39  return 1;
40  }
41 
42  // If we find two items that collides for the same index, just request
43  // this index. This should be rare enough that the extra bandwidth
44  // doesn't matter. Due to the way the compact messages are encoded, this
45  // can only occur in the event of a shortid collision.
46  if (itemsAvailable[index] && !(*this)(itemsAvailable[index], item)) {
47  itemsAvailable[index] = ItemType();
48  return -1;
49  }
50 
51  return 0;
52  }
53 
54 public:
55  ShortIdProcessor(const std::vector<PrefilledItemType> &prefilledItems,
56  const std::vector<uint64_t> &shortids,
57  size_t maxShortIdPerBucket)
58  : itemsAvailable(prefilledItems.size() + shortids.size()),
59  haveItem(prefilledItems.size() + shortids.size()),
60  shortIdIndexMap(shortids.size()) {
61  for (const auto &prefilledItem : prefilledItems) {
62  addItem(Adapter::getIndex(prefilledItem),
63  Adapter::getItem(prefilledItem));
64  }
65 
66  uint32_t index_offset = 0;
67  for (size_t i = 0; i < shortids.size(); i++) {
68  while (itemsAvailable[i + index_offset]) {
69  index_offset++;
70  }
71 
72  shortIdIndexMap[shortids[i]] = i + index_offset;
73 
74  // Because well-formed compact messages will have a (relatively)
75  // uniform distribution of short IDs, any highly-uneven distribution
76  // of elements can be safely treated as an error.
77  if (shortIdIndexMap.bucket_size(shortIdIndexMap.bucket(
78  shortids[i])) > maxShortIdPerBucket) {
79  evenlyDistributed = false;
80  }
81  }
82 
83  shortIdCollision = shortIdIndexMap.size() != shortids.size();
84  }
85 
87  bool isEvenlyDistributed() const { return evenlyDistributed; }
88  bool hasShortIdCollision() const { return shortIdCollision; }
89  bool hasOutOfBoundIndex() const { return outOfBoundIndex; }
90 
92  size_t getItemCount() const { return itemsAvailable.size(); }
94  size_t getShortIdCount() const { return shortIdIndexMap.size(); }
95 
109  int matchKnownItem(uint64_t shortid, const ItemType &item) {
110  auto idit = shortIdIndexMap.find(shortid);
111  if (idit == shortIdIndexMap.end()) {
112  return 0;
113  }
114 
115  return addItem(idit->second, item);
116  }
117 
118  const ItemType &getItem(size_t index) const {
119  assert(index < itemsAvailable.size());
120 
121  return itemsAvailable[index];
122  }
123 };
124 
125 #endif // BITCOIN_SHORTIDPROCESSOR_H
int addItem(uint32_t index, const ItemType &item)
const ItemType & getItem(size_t index) const
bool isEvenlyDistributed() const
Status accessors.
typename std::remove_reference< decltype(std::declval< Adapter & >().getItem(std::declval< PrefilledItemType & >()))>::type ItemType
size_t getItemCount() const
Total item count.
int matchKnownItem(uint64_t shortid, const ItemType &item)
Attempts to add a known item by matching its shortid with the supplied ones.
std::unordered_map< uint64_t, uint32_t > shortIdIndexMap
ShortIdProcessor(const std::vector< PrefilledItemType > &prefilledItems, const std::vector< uint64_t > &shortids, size_t maxShortIdPerBucket)
size_t getShortIdCount() const
Unique shortid count.
std::vector< ItemType > itemsAvailable
bool hasShortIdCollision() const
std::vector< bool > haveItem
bool hasOutOfBoundIndex() const
assert(!tx.IsCoinBase())