31struct OPENDHT_PUBLIC Prefix
36 , content_(h.begin(), h.end())
38 Prefix(
const Blob& d,
const Blob& f = {})
44 Prefix(
const Prefix& p,
size_t first)
45 : size_(std::min(first, p.content_.size() * 8))
46 , content_(
Blob(p.content_.begin(), p.content_.begin() + size_ / 8))
49 if (not p.flags_.empty()) {
50 flags_ =
Blob(p.flags_.begin(), p.flags_.begin() + size_ / 8);
52 flags_.push_back(p.flags_[size_ / 8] & (0xFF << (8 - rem)));
56 content_.push_back(p.content_[size_ / 8] & (0xFF << (8 - rem)));
73 if ((
size_t) std::abs(len) >= content_.size() * 8)
74 throw std::out_of_range(
"len larger than prefix size.");
78 return Prefix(*
this, len);
87 bool isFlagActive(
size_t pos)
const {
return flags_.empty() or isActiveBit(flags_, pos); }
94 Prefix getFullSize() {
return Prefix(*
this, content_.size() * 8); }
110 InfoHash hash()
const
113 copy.push_back(size_);
114 return InfoHash::get(copy);
124 static inline unsigned commonBits(
const Prefix& p1,
const Prefix& p2)
128 auto longest_prefix_size = std::min(p1.size_, p2.size_);
131 while (common < longest_prefix_size) {
159 auto csize = size_ - flags_.size() * 8;
161 flags_.push_back(0xFF);
167 flags_.push_back(0xFF << (8 - csize));
170 for (
auto i = flags_.size(); i < content_.size(); i++)
171 flags_.push_back(0xFF);
174 std::string toString()
const;
193 Blob addPadding(Blob toP,
size_t size)
196 for (
auto i = copy.size(); i < size; i++)
199 swapBit(copy, size_);
213 bool isActiveBit(
const Blob& b,
size_t pos)
const
215 if (pos >= content_.size() * 8)
216 throw std::out_of_range(
"Can't detect active bit at pos, pos larger than prefix size or empty prefix");
218 return ((b[pos / 8] >> (7 - (pos % 8))) & 1) == 1;
231 void swapBit(Blob& b,
size_t bit)
233 if (bit >= b.size() * 8)
234 throw std::out_of_range(
"bit larger than prefix size.");
238 b[bit / 8] ^= (1 << (7 - (bit % 8)));
266class OPENDHT_PUBLIC Pht
268 static constexpr const char* INVALID_KEY =
"Key does not match the PHT key spec.";
271 static constexpr const char* INDEX_PREFIX =
"index.pht.";
277 static constexpr const size_t MAX_NODE_ENTRY_COUNT {16};
280 using Key = std::map<std::string, Blob>;
284 using KeySpec = std::map<std::string, size_t>;
285 using LookupCallback = std::function<void(std::vector<std::shared_ptr<Value>>& values,
const Prefix& p)>;
287 typedef void (*LookupCallbackRaw)(std::vector<std::shared_ptr<Value>>* values,
Prefix* p,
void* user_data);
288 static LookupCallback bindLookupCb(LookupCallbackRaw raw_cb,
void* user_data)
292 return [=](std::vector<std::shared_ptr<Value>>& values,
const Prefix& p) {
293 raw_cb((std::vector<std::shared_ptr<Value>>*) &values, (
Prefix*) &p, user_data);
296 using LookupCallbackSimple = std::function<void(std::vector<std::shared_ptr<Value>>& values)>;
297 typedef void (*LookupCallbackSimpleRaw)(std::vector<std::shared_ptr<Value>>* values,
void* user_data);
298 static LookupCallbackSimple bindLookupCbSimple(LookupCallbackSimpleRaw raw_cb,
void* user_data)
302 return [=](std::vector<std::shared_ptr<Value>>& values) {
303 raw_cb((std::vector<std::shared_ptr<Value>>*) &values, user_data);
307 Pht(std::string name, KeySpec k_spec, std::shared_ptr<DhtRunner>
dht)
308 : name_(INDEX_PREFIX + name)
309 , canary_(name_ +
".canary")
319 void lookup(Key k, LookupCallback cb = {}, DoneCallbackSimple done_cb = {},
bool exact_match =
true);
320 void lookup(Key k, LookupCallbackSimple cb = {}, DoneCallbackSimple done_cb = {},
bool exact_match =
true)
324 [cb = std::move(cb)](std::vector<std::shared_ptr<Value>>& values, Prefix) { cb(values); },
336 void insert(Key k, Value v, DoneCallbackSimple done_cb = {})
340 auto lo = std::make_shared<int>(0);
341 auto hi = std::make_shared<int>(p.size_);
345 entry.prefix = p.content_;
348 Pht::insert(p, entry, lo, hi, clock::now(),
true, done_cb);
364 void insert(
const Prefix& kp,
366 std::shared_ptr<int> lo,
367 std::shared_ptr<int> hi,
370 DoneCallbackSimple done_cb = {});
379 void insert(
const Prefix& p);
389 int lookup(
const Prefix& p);
392 static constexpr const size_t MAX_ELEMENT {1024};
393 static constexpr const std::chrono::minutes NODE_EXPIRE_TIME {5};
397 time_point last_reply;
398 std::shared_ptr<Node> parent;
399 std::weak_ptr<Node> left_child;
400 std::weak_ptr<Node> right_child;
403 std::weak_ptr<Node> root_;
410 std::multimap<time_point, std::shared_ptr<Node>> leaves_;
414 using RealInsertCallback = std::function<void(
const Prefix& p, IndexEntry entry)>;
415 using LookupCallbackWrapper = std::function<void(std::vector<std::shared_ptr<IndexEntry>>& values,
const Prefix& p)>;
432 void lookupStep(Prefix k,
433 std::shared_ptr<int> lo,
434 std::shared_ptr<int> hi,
435 std::shared_ptr<std::vector<std::shared_ptr<IndexEntry>>> vals,
436 LookupCallbackWrapper cb,
437 DoneCallbackSimple done_cb,
438 std::shared_ptr<unsigned> max_common_prefix_len,
440 bool all_values =
false);
449 Prefix zcurve(
const std::vector<Prefix>& all_prefix)
const;
459 virtual Prefix linearize(Key k)
const;
469 void getRealPrefix(
const std::shared_ptr<Prefix>& p, IndexEntry entry, RealInsertCallback end_cb);
479 void checkPhtUpdate(Prefix p, IndexEntry entry, time_point time_p);
488 static size_t findSplitLocation(
const Prefix& compared,
const std::vector<std::shared_ptr<IndexEntry>>& vals)
490 for (
size_t i = 0; i < compared.content_.size() * 8 - 1; i++)
491 for (
auto const& v : vals)
492 if (Prefix(v->prefix).isContentBitActive(i) != compared.isContentBitActive(i))
494 return compared.content_.size() * 8 - 1;
505 void split(
const Prefix& insert,
506 const std::vector<std::shared_ptr<IndexEntry>>& vals,
508 RealInsertCallback end_cb);
513 bool validKey(
const Key& k)
const
515 return k.size() == keySpec_.size()
516 and std::equal(k.begin(),
519 [&](
const Key::value_type& key,
const KeySpec::value_type& key_spec) {
520 return key.first == key_spec.first and key.second.size() <= key_spec.second;
528 void updateCanary(Prefix p);
530 const std::string name_;
531 const std::string canary_;
532 const KeySpec keySpec_;
534 std::shared_ptr<DhtRunner> dht_;