25 namespace _contiguous_map {
27 template<
typename K,
typename V>
29 NodeMeta(
const K& key,
const V& value):
30 pair(std::make_pair(key, value)) {}
32 std::pair<const K, V> pair;
34 bool is_black =
false;
38 int32_t equal_index_ = -1;
39 int32_t last_equal_index_ = -1;
41 int32_t parent_index_ = -1;
42 int32_t left_index_ = -1;
43 int32_t right_index_ = -1;
44 } __attribute__((aligned(8)));
51 enum Result : int8_t {
57 Result operator()(
const T& a,
const T& b)
const {
58 return (a < b) ? RESULT_LESS : (b < a) ? RESULT_GREATER : RESULT_EQUAL;
63 template<
typename K,
typename V,
typename Compare=ThreeWayCompare<K>>
76 current_node_ = map->leftmost_index_;
83 current_node_ = index;
86 auto current = _node(current_node_);
87 if(current->left_index_ > -1) {
88 previous_node_index_ = current->left_index_;
91 previous_node_index_ = -1;
99 return &map_->nodes_[index];
103 if(current_node_ < 0)
return;
105 auto current = _node(current_node_);
108 if(current->equal_index_ > -1 && list_head_index_ == -1) {
109 list_head_index_ = current_node_;
110 current_node_ = current->equal_index_;
112 }
else if(list_head_index_ > -1) {
114 current_node_ = current->equal_index_;
115 if(current_node_ == -1) {
117 current_node_ = list_head_index_;
118 list_head_index_ = -1;
119 current = _node(current_node_);
126 auto previous = current_node_;
128 if(current->right_index_ == -1) {
132 current_node_ = current->parent_index_;
133 while(current_node_ > -1) {
134 current = _node(current_node_);
135 if(previous == current->left_index_) {
139 previous = current_node_;
140 current_node_ = current->parent_index_;
145 current_node_ = current->right_index_;
146 if(current_node_ > -1) {
148 current = _node(current_node_);
149 while(current->left_index_ > -1) {
150 current_node_ = current->left_index_;
151 current = _node(current_node_);
156 previous_node_index_ = previous;
161 map_ == other.map_ &&
162 current_node_ == other.current_node_
166 int32_t current_node_ = -1;
171 int32_t list_head_index_ = -1;
172 int32_t previous_node_index_ = -1;
186 using iterator_category = std::forward_iterator_tag;
187 using value_type = std::pair<const K, V>;
188 using difference_type = uint32_t;
189 using pointer = std::pair<const K, V>*;
190 using reference = std::pair<const K, V>&;
201 bool operator==(
const iterator& other)
const {
202 return this->is_equal(other);
205 bool operator!=(
const iterator& other)
const {
206 return !this->is_equal(other);
209 reference operator*()
const {
210 return this->_node(this->current_node_)->pair;
213 pointer operator->()
const {
214 return &this->_node(this->current_node_)->pair;
230 using iterator_category = std::forward_iterator_tag;
231 using value_type = std::pair<const K, V>;
232 using difference_type = uint32_t;
233 using pointer =
const std::pair<const K, V>*;
234 using reference =
const std::pair<const K, V>&;
246 return this->is_equal(other);
250 return !this->is_equal(other);
253 reference operator*()
const {
254 return this->_node(this->current_node_)->pair;
257 pointer operator->()
const {
258 return &this->_node(this->current_node_)->pair;
266 leftmost_index_(-1) {
267 nodes_.reserve(reserve_count);
273 bool insert(
const K& key, V&& element) {
275 return _insert(std::move(k), std::move(element));
278 bool insert(
const K& key,
const V& element) {
281 return _insert(std::move(k), std::move(v));
287 leftmost_index_ = -1;
290 void shrink_to_fit() {
291 nodes_.shrink_to_fit();
294 std::size_t size()
const {
295 return nodes_.size();
298 void reserve(std::size_t size) {
299 nodes_.reserve(size);
303 return nodes_.empty();
306 iterator find(
const K& key) {
307 int32_t index = _find(key);
311 return iterator(
this, index);
314 const_iterator find(
const K &key)
const {
315 int32_t index = _find(key);
320 return const_iterator(
321 const_cast<ContiguousMultiMap*
>(
this),
326 const_iterator upper_bound(
const K& key)
const {
329 while(it != end() && it->first == key) {
337 return iterator(
this);
344 const_iterator begin()
const {
345 return const_iterator(
346 const_cast<ContiguousMultiMap*
>(
this)
350 const_iterator end()
const {
358 const K& path_key(
const std::string& path)
const {
359 const node_type* node = &nodes_[root_index_];
363 if(node->left_index_ == -1) {
364 throw std::logic_error(
"Hit end of branch");
366 node = &nodes_[node->left_index_];
367 }
else if(c ==
'R') {
368 if(node->right_index_ == -1) {
369 throw std::logic_error(
"Hit end of branch");
371 node = &nodes_[node->right_index_];
373 throw std::logic_error(
"Invalid path");
378 return node->pair.first;
381 friend class iterator_base;
383 iterator end_ = iterator(
this, -1);
384 const_iterator cend_ = const_iterator(
385 const_cast<ContiguousMultiMap*
>(
this), -1
388 int32_t _find(
const K& key)
const {
389 if(root_index_ == -1)
return -1;
391 int32_t current_index = root_index_;
392 const node_type* current = &nodes_[current_index];
395 auto order = compare_(key, current->pair.first);
397 if(order == ThreeWayCompare<K>::RESULT_EQUAL) {
398 return current_index;
399 }
else if(order == ThreeWayCompare<K>::RESULT_LESS) {
400 if(current->left_index_ != -1) {
401 current_index = current->left_index_;
402 current = &nodes_[current_index];
407 if(current->right_index_ != -1) {
408 current_index = current->right_index_;
409 current = &nodes_[current_index];
416 return current_index;
419 void _rotate_left(node_type* node, int32_t node_index, node_type* parent=
nullptr) {
420 int32_t nnew_index = node->right_index_;
421 assert(nnew_index != -1);
424 int32_t parent_index = node->parent_index_;
425 parent = (parent) ? parent : (parent_index == -1) ? nullptr : &nodes_[parent_index];
427 node_type* nnew = &nodes_[nnew_index];
429 node->right_index_ = nnew->left_index_;
430 nnew->left_index_ = node_index;
431 node->parent_index_ = nnew_index;
433 if(node->right_index_ != -1) {
434 nodes_[node->right_index_].parent_index_ = node_index;
438 if(node_index == parent->left_index_) {
439 parent->left_index_ = nnew_index;
440 }
else if(node_index == parent->right_index_) {
441 parent->right_index_ = nnew_index;
445 nnew->parent_index_ = parent_index;
448 void _rotate_right(node_type* node, int32_t node_index, node_type* parent=
nullptr) {
449 int32_t nnew_index = node->left_index_;
450 assert(nnew_index != -1);
453 int32_t parent_index = node->parent_index_;
454 parent = (parent) ? parent : (parent_index == -1) ? nullptr : &nodes_[parent_index];
456 node_type* nnew = &nodes_[nnew_index];
458 node->left_index_ = nnew->right_index_;
459 nnew->right_index_ = node_index;
460 node->parent_index_ = nnew_index;
462 if(node->left_index_ != -1) {
463 nodes_[node->left_index_].parent_index_ = node_index;
467 if(node_index == parent->left_index_) {
468 parent->left_index_ = nnew_index;
469 }
else if(node_index == parent->right_index_) {
470 parent->right_index_ = nnew_index;
474 nnew->parent_index_ = parent_index;
477 void _insert_repair_tree(node_type* node, int32_t node_index) {
480 if(node->parent_index_ == -1) {
481 node->is_black =
true;
485 assert(node->parent_index_ != -1);
486 node_type* parent = &nodes_[node->parent_index_];
489 if(parent->is_black) {
493 node_type* grandparent = (parent->parent_index_ == -1) ?
494 nullptr : &nodes_[parent->parent_index_];
496 int32_t parent_sibling_index = (!grandparent) ? -1 :
497 (grandparent->left_index_ == node->parent_index_) ?
498 grandparent->right_index_ : grandparent->left_index_;
500 node_type* parent_sibling = (parent_sibling_index == -1) ? nullptr : &nodes_[parent_sibling_index];
503 if(parent_sibling && !parent_sibling->is_black) {
505 parent->is_black =
true;
506 parent_sibling->is_black =
true;
507 grandparent->is_black =
false;
510 _insert_repair_tree(grandparent, parent->parent_index_);
513 if(node_index == parent->right_index_ && node->parent_index_ == grandparent->left_index_) {
514 _rotate_left(parent, node->parent_index_, grandparent);
516 node_index = node->left_index_;
517 node = &nodes_[node->left_index_];
519 assert(node->parent_index_ != -1);
520 parent = &nodes_[node->parent_index_];
522 assert(parent->parent_index_ != -1);
523 grandparent = &nodes_[parent->parent_index_];
525 }
else if(node_index == parent->left_index_ && node->parent_index_ == grandparent->right_index_) {
526 _rotate_right(parent, node->parent_index_, grandparent);
528 node_index = node->right_index_;
529 node = &nodes_[node->right_index_];
531 assert(node->parent_index_ != -1);
532 parent = &nodes_[node->parent_index_];
534 assert(parent->parent_index_ != -1);
535 grandparent = &nodes_[parent->parent_index_];
538 if(node_index == parent->left_index_) {
539 _rotate_right(grandparent, parent->parent_index_);
541 _rotate_left(grandparent, parent->parent_index_);
547 parent->is_black =
true;
548 grandparent->is_black =
false;
552 bool _insert(K&& key, V&& value) {
553 if(root_index_ == -1) {
555 leftmost_index_ = root_index_ = new_node(-1, std::move(key), std::move(value));
556 nodes_.back().is_black =
true;
562 bool is_black = _insert_recurse(
563 root_index_, std::move(key), std::move(value), &new_index
566 node_type* inserted = (new_index > -1) ? &nodes_[new_index] :
nullptr;
568 auto ret = new_index > 1;
569 if(new_index > -1 && !is_black) {
571 _insert_repair_tree(inserted, new_index);
574 if(inserted->parent_index_ == -1) {
575 root_index_ = new_index;
577 node_type* parent = inserted;
578 while(parent->parent_index_ != -1) {
579 node_type* next_parent = &nodes_[parent->parent_index_];
581 if(next_parent->parent_index_ == -1) {
582 root_index_ = parent->parent_index_;
586 parent = next_parent;
593 assert(leftmost_index_ > -1);
597 if(inserted && inserted->parent_index_ == leftmost_index_) {
598 node_type* p = &nodes_[inserted->parent_index_];
599 if(p && p->left_index_ == new_index) {
600 leftmost_index_ = new_index;
608 inline int32_t new_node(int32_t parent_index, K&& key, V&& value) {
609 auto ret = (int32_t) nodes_.size();
611 node_type n(key, value);
612 n.parent_index_ = parent_index;
613 nodes_.push_back(std::move(n));
618 bool _insert_recurse(int32_t root_index, K&& key, V&& value, int32_t* new_index) {
619 assert(root_index > -1);
621 node_type* root = &nodes_[root_index];
623 auto order = compare_(key, root->pair.first);
624 if(order == ThreeWayCompare<K>::RESULT_EQUAL) {
628 auto new_idx = new_node(-1, std::move(key), std::move(value));
629 root = &nodes_[root_index];
637 if(root->last_equal_index_ > -1) {
638 left = &nodes_[left->last_equal_index_];
641 left->equal_index_ = new_idx;
642 root->last_equal_index_ = new_idx;
649 *new_index = new_idx;
653 }
else if(order == ThreeWayCompare<K>::RESULT_LESS) {
654 if(root->left_index_ == -1) {
655 auto new_idx = new_node(root_index, std::move(key), std::move(value));
657 root = &nodes_[root_index];
658 root->left_index_ = new_idx;
661 *new_index = new_idx;
664 return root->is_black;
666 return _insert_recurse(
667 root->left_index_, std::move(key), std::move(value), new_index
671 if(root->right_index_ == -1) {
672 auto new_idx = new_node(root_index, std::move(key), std::move(value));
674 root = &nodes_[root_index];
675 root->right_index_ = new_idx;
678 *new_index = new_idx;
681 return root->is_black;
683 return _insert_recurse(
684 root->right_index_, std::move(key), std::move(value), new_index
690 std::vector<node_type> nodes_;
692 int32_t root_index_ = -1;
693 int32_t leftmost_index_ = -1;
699 template<
typename K,
typename V,
typename Compare=ThreeWayCompare<K>>
713 std::size_t size()
const {
717 bool insert(
const K& key, V&& element) {
718 if(map_.find(key) == map_.end()) {
719 map_.insert(key, std::move(element));
726 V& at(
const K& key) {
727 auto it = map_.find(key);
729 if(it == map_.end()) {
730 throw std::out_of_range(
"Key not found");
736 const V& at(
const K& key)
const {
737 auto it = map_.find(key);
739 if(it == map_.end()) {
740 throw std::out_of_range(
"Key not found");
746 bool insert(
const K& key,
const V& element) {
747 if(map_.find(key) == map_.end()) {
748 map_.insert(key, element);
755 void shrink_to_fit() {
756 map_.shrink_to_fit();
764 return map_.find(key);
768 return map_.find(key);