Changeset 9751280 in mainline
 Timestamp:
 20180705T21:41:22Z (2 years ago)
 Branches:
 master
 Children:
 6b18e43
 Parents:
 65dde99
 gitauthor:
 Dzejrou <dzejrou@…> (20180428 16:24:26)
 gitcommitter:
 Dzejrou <dzejrou@…> (20180705 21:41:22)
 Location:
 uspace/lib/cpp/include/internal
 Files:

 5 added
 1 edited
Legend:
 Unmodified
 Added
 Removed

uspace/lib/cpp/include/internal/hash_table.hpp
r65dde99 r9751280 32 32 #include <cstdlib> 33 33 #include <internal/list.hpp> 34 #include <internal/key_extractors.hpp> 35 #include <internal/hash_table_iterators.hpp> 36 #include <internal/hash_table_policies.hpp> 34 37 #include <iterator> 35 38 #include <limits> … … 47 50 * and two proxies that either use plain Key type or a pair 48 51 * of a key and a value. 52 * Additionally, we will use policies to represent both single 53 * and multi variants of these containers at once. 49 54 * Note: I am aware the naming is very unimaginative here, 50 55 * not my strong side :) 51 56 */ 52 53 template<class Key, class Value>54 struct key_value_key_extractor55 {56 const Key& operator()(const pair<const Key, Value>& p) const noexcept57 {58 return p.first;59 }60 };61 62 template<class Key>63 struct key_no_value_key_extractor64 {65 Key& operator()(Key& k) const noexcept66 {67 return k;68 }69 70 const Key& operator()(const Key& k) const noexcept71 {72 return k;73 }74 };75 76 template<class Value, class Size>77 struct hash_table_bucket78 {79 /**80 * Note: We use a doubly linked list because81 * we need to use hints, which point to the82 * element after the hinted spot.83 */84 85 list_node<Value>* head;86 87 hash_table_bucket()88 : head{}89 { /* DUMMY BODY */ }90 91 Size size() const noexcept92 {93 auto current = head;94 Size res{};95 96 do97 {98 ++res;99 current = current>next;100 }101 while (current != head);102 103 return res;104 }105 106 void append(list_node<Value>* node)107 {108 if (!head)109 head = node;110 else111 head>append(node);112 }113 114 void prepend(list_node<Value>* node)115 {116 if (!head)117 head = node;118 else119 head>prepend(node);120 }121 122 void clear()123 {124 if (!head)125 return;126 127 auto current = head;128 do129 {130 auto tmp = current;131 current = current>next;132 delete tmp;133 }134 while (current != head);135 136 head = nullptr;137 }138 139 ~hash_table_bucket()140 {141 clear();142 }143 };144 145 struct hash_single_policy146 {147 template<class Table, class Key>148 static typename Table::size_type count(const Table& table, const Key& key)149 {150 return table.find(key) == table.end() ? 0 : 1;151 }152 153 template<class Table, class Key>154 static typename Table::place_type find_insertion_spot(const Table& table, const Key& key)155 {156 auto idx = table.get_bucket_idx_(key);157 return make_tuple(158 &table.table_[idx],159 table.table_[idx].head,160 idx161 );162 }163 164 template<class Table, class Key>165 static typename Table::size_type erase(Table& table, const Key& key)166 {167 auto idx = table.get_bucket_idx_(key);168 auto head = table.table_[idx].head;169 auto current = head;170 171 do172 {173 if (table.keys_equal(key, current>value))174 {175 table.size_;176 177 if (current == head)178 {179 if (current>next != head)180 table.table_[idx].head = current>next;181 else182 table.table_[idx].head = nullptr;183 }184 185 current>unlink();186 delete current;187 188 return 1;189 }190 else191 current = current>next;192 }193 while (current != head);194 195 return 0;196 }197 198 template<class Table, class Key>199 static pair<200 typename Table::iterator,201 typename Table::iterator202 > equal_range(Table& table, const Key& key)203 {204 auto it = table.find(key);205 return make_pair(it, ++it);206 }207 208 template<class Table, class Key>209 static pair<210 typename Table::const_iterator,211 typename Table::const_iterator212 > equal_range_const(const Table& table, const Key& key)213 { // Note: We cannot overload by return type, so we use a different name.214 auto it = table.find(key);215 return make_pair(it, ++it);216 }217 218 /**219 * Note: We have to duplicate code for emplace, insert(const&)220 * and insert(&&) here, because the node (which makes distinction221 * between the arguments) is only created if the value isn't222 * in the table already.223 */224 225 template<class Table, class... Args>226 static pair<227 typename Table::iterator, bool228 > emplace(Table& table, Args&&... args)229 {230 using value_type = typename Table::value_type;231 using node_type = typename Table::node_type;232 using iterator = typename Table::iterator;233 234 table.increment_size();235 236 auto val = value_type{forward<Args>(args)...};237 const auto& key = table.get_key(val);238 auto [bucket, target, idx] = table.find_insertion_spot(key);239 240 if (!bucket)241 return make_pair(table.end(), false);242 243 if (target && table.keys_equal(key, target>value))244 {245 table.decrement_size();246 247 return make_pair(248 iterator{249 table.table(), idx, table.bucket_count(),250 target251 },252 false253 );254 }255 else256 {257 auto node = new node_type{move(val)};258 bucket>prepend(node);259 260 return make_pair(iterator{261 table.table(), idx,262 table.bucket_count(),263 node264 }, true);265 }266 }267 268 template<class Table, class Value>269 static pair<270 typename Table::iterator, bool271 > insert(Table& table, const Value& val)272 {273 using node_type = typename Table::node_type;274 using iterator = typename Table::iterator;275 276 table.increment_size();277 278 const auto& key = table.get_key(val);279 auto [bucket, target, idx] = table.find_insertion_spot(key);280 281 if (!bucket)282 return make_pair(table.end(), false);283 284 if (target && table.keys_equal(key, target>value))285 {286 table.decrement_size();287 288 return make_pair(289 iterator{290 table.table(), idx, table.bucket_count(),291 target292 },293 false294 );295 }296 else297 {298 auto node = new node_type{val};299 bucket>prepend(node);300 301 return make_pair(iterator{302 table.table(), idx,303 table.bucket_count(),304 node305 }, true);306 }307 }308 309 template<class Table, class Value>310 static pair<311 typename Table::iterator, bool312 > insert(Table& table, Value&& val)313 {314 using value_type = typename Table::value_type;315 using node_type = typename Table::node_type;316 using iterator = typename Table::iterator;317 318 table.increment_size();319 320 const auto& key = table.get_key(val);321 auto [bucket, target, idx] = table.find_insertion_spot(key);322 323 if (!bucket)324 return make_pair(table.end(), false);325 326 if (target && table.keys_equal(key, target>value))327 {328 table.decrement_size();329 330 return make_pair(331 iterator{332 table.table(), idx, table.bucket_count(),333 target334 },335 false336 );337 }338 else339 {340 auto node = new node_type{forward<value_type>(val)};341 bucket>prepend(node);342 343 return make_pair(iterator{344 table.table(), idx,345 table.bucket_count(),346 node347 }, true);348 }349 }350 };351 352 struct hash_multi_policy353 {354 template<class Table, class Key>355 static typename Table::size_type count(const Table& table, const Key& key)356 {357 auto head = table.table_[get_bucket_idx_(key)].head;358 if (!head)359 return 0;360 361 auto current = head;362 typename Table::size_type res = 0;363 do364 {365 if (table.keys_equal(key, current>value))366 ++res;367 368 current = current>next;369 }370 while (current != head);371 372 return res;373 }374 375 template<class Table, class Key>376 static typename Table::place_type find_insertion_spot(const Table& table, const Key& key)377 {378 auto idx = table.get_bucket_idx_(key);379 auto head = table.table_[idx].head;380 381 if (head)382 {383 auto current = head;384 do385 {386 if (table.keys_equal(key, current>value))387 {388 return make_tuple(389 &table.table_[idx],390 current,391 idx392 );393 }394 395 current = current>next;396 } while (current != head);397 }398 399 return make_tuple(400 &table.table_[idx],401 table.table_[idx].head,402 idx403 );404 }405 406 template<class Table, class Key>407 static typename Table::size_type erase(Table& table, const Key& key)408 {409 auto idx = table.get_bucket_idx_(key);410 auto it = table.begin(it);411 typename Table::size_type res{};412 413 while (it != table.end(it))414 {415 if (table.keys_equal(key, *it))416 {417 while (table.keys_equal(key, *it))418 {419 auto node = it.node();420 ++it;421 ++res;422 423 node.unlink();424 delete node;425 table.size_;426 }427 428 // Elements with equal keys are next to each other.429 return res;430 }431 432 ++it;433 }434 435 return res;436 }437 438 template<class Table, class Key>439 static pair<440 typename Table::iterator,441 typename Table::iterator442 > equal_range(Table& table, const Key& key)443 {444 auto first = table.find(key);445 if (first == table.end())446 return make_pair(table.end(), table.end());447 448 auto last = first;449 do450 {451 ++last;452 } while (table.keys_equal(key, *last));453 454 return make_pair(first, last);455 }456 457 template<class Table, class Key>458 static pair<459 typename Table::const_iterator,460 typename Table::const_iterator461 > equal_range_const(const Table& table, const Key& key)462 {463 auto first = table.find(key);464 if (first == table.end())465 return make_pair(table.end(), table.end());466 467 auto last = first;468 do469 {470 ++last;471 } while (table.keys_equal(key, *last));472 473 return make_pair(first, last);474 }475 476 template<class Table, class... Args>477 static pair<478 typename Table::iterator, bool479 > emplace(Table& table, Args&&... args)480 {481 using node_type = typename Table::node_type;482 483 auto node = new node_type{forward<Args>(args)...};484 485 return insert(table, node);486 }487 488 template<class Table, class Value>489 static pair<490 typename Table::iterator, bool491 > insert(Table& table, const Value& val)492 {493 using node_type = typename Table::node_type;494 495 auto node = new node_type{val};496 497 return insert(table, node);498 }499 500 template<class Table, class Value>501 static pair<502 typename Table::iterator, bool503 > insert(Table& table, Value&& val)504 {505 using value_type = typename Table::value_type;506 using node_type = typename Table::node_type;507 508 auto node = new node_type{forward<value_type>(val)};509 510 return insert(table, node);511 }512 513 template<class Table>514 static pair<515 typename Table::iterator, bool516 > insert(Table& table, typename Table::node_type* node)517 {518 using iterator = typename Table::iterator;519 520 table.increment_size();521 522 const auto& key = table.get_key(node>value);523 auto [bucket, target, idx] = table.find_insertion_spot(key);524 525 if (!bucket)526 return make_pair(table.end(), false);527 528 if (target && table.keys_equal(key, target>value))529 target>append(node);530 else531 bucket>prepend(node);532 533 return make_pair(iterator{534 table.table(), idx,535 table.bucket_count(),536 node537 }, true);538 }539 };540 541 template<class Value, class ConstReference, class ConstPointer, class Size>542 class hash_table_const_iterator543 {544 public:545 using value_type = Value;546 using size_type = Size;547 using const_reference = ConstReference;548 using const_pointer = ConstPointer;549 using difference_type = ptrdiff_t;550 551 using iterator_category = forward_iterator_tag;552 553 hash_table_const_iterator(const hash_table_bucket<value_type, size_type>* table = nullptr,554 size_type idx = size_type{}, size_type max_idx = size_type{},555 const list_node<value_type>* current = nullptr)556 : table_{table}, idx_{idx}, max_idx_{max_idx}, current_{current}557 { /* DUMMY BODY */ }558 559 hash_table_const_iterator(const hash_table_const_iterator&) = default;560 hash_table_const_iterator& operator=(const hash_table_const_iterator&) = default;561 562 const_reference operator*() const563 {564 return current_>value;565 }566 567 const_pointer operator>() const568 {569 return ¤t_>value;570 }571 572 hash_table_const_iterator& operator++()573 {574 current_ = current_>next;575 if (current_ == table_[idx_].head)576 {577 if (idx_ < max_idx_)578 {579 while (!table_[++idx_].head && idx_ < max_idx_)580 { /* DUMMY BODY */ }581 582 if (idx_ < max_idx_)583 current_ = table_[idx_].head;584 else585 current_ = nullptr;586 }587 else588 current_ = nullptr;589 }590 591 return *this;592 }593 594 hash_table_const_iterator operator++(int)595 {596 auto tmp_current = current_;597 auto tmp_idx = idx_;598 599 current_ = current_>next;600 if (current_ == table_[idx_].head)601 {602 if (idx_ < max_idx_)603 {604 while (!table_[++idx_].head && idx_ < max_idx_)605 { /* DUMMY BODY */ }606 607 if (idx_ < max_idx_)608 current_ = table_[idx_].head;609 else610 current_ = nullptr;611 }612 else613 current_ = nullptr;614 }615 616 return hash_table_const_iterator{617 table_, tmp_idx, max_idx_, tmp_current618 };619 }620 621 list_node<value_type>* node()622 {623 return const_cast<list_node<value_type>*>(current_);624 }625 626 const list_node<value_type>* node() const627 {628 return current_;629 }630 631 size_type idx() const632 {633 return idx_;634 }635 636 private:637 const hash_table_bucket<value_type, size_type>* table_;638 size_type idx_;639 size_type max_idx_;640 const list_node<value_type>* current_;641 };642 643 template<class Value, class ConstRef, class ConstPtr, class Size>644 bool operator==(const hash_table_const_iterator<Value, ConstRef, ConstPtr, Size>& lhs,645 const hash_table_const_iterator<Value, ConstRef, ConstPtr, Size>& rhs)646 {647 return lhs.node() == rhs.node();648 }649 650 template<class Value, class ConstRef, class ConstPtr, class Size>651 bool operator!=(const hash_table_const_iterator<Value, ConstRef, ConstPtr, Size>& lhs,652 const hash_table_const_iterator<Value, ConstRef, ConstPtr, Size>& rhs)653 {654 return !(lhs == rhs);655 }656 657 template<class Value, class Reference, class Pointer, class Size>658 class hash_table_iterator659 {660 public:661 using value_type = Value;662 using size_type = Size;663 using reference = Reference;664 using pointer = Pointer;665 using difference_type = ptrdiff_t;666 667 using iterator_category = forward_iterator_tag;668 669 hash_table_iterator(hash_table_bucket<value_type, size_type>* table = nullptr,670 size_type idx = size_type{}, size_type max_idx = size_type{},671 list_node<value_type>* current = nullptr)672 : table_{table}, idx_{idx}, max_idx_{max_idx}, current_{current}673 { /* DUMMY BODY */ }674 675 hash_table_iterator(const hash_table_iterator&) = default;676 hash_table_iterator& operator=(const hash_table_iterator&) = default;677 678 reference operator*()679 {680 return current_>value;681 }682 683 pointer operator>()684 {685 return ¤t_>value;686 }687 688 hash_table_iterator& operator++()689 {690 current_ = current_>next;691 if (current_ == table_[idx_].head)692 {693 if (idx_ < max_idx_)694 {695 while (!table_[++idx_].head && idx_ < max_idx_)696 { /* DUMMY BODY */ }697 698 if (idx_ < max_idx_)699 current_ = table_[idx_].head;700 else701 current_ = nullptr;702 }703 else704 current_ = nullptr;705 }706 707 return *this;708 }709 710 hash_table_iterator operator++(int)711 {712 auto tmp_current = current_;713 auto tmp_idx = idx_;714 715 current_ = current_>next;716 if (current_ == table_[idx_].head)717 {718 if (idx_ < max_idx_)719 {720 while (!table_[++idx_].head && idx_ < max_idx_)721 { /* DUMMY BODY */ }722 723 if (idx_ < max_idx_)724 current_ = table_[idx_].head;725 else726 current_ = nullptr;727 }728 else729 current_ = nullptr;730 }731 732 return hash_table_iterator{733 table_, tmp_idx, max_idx_, tmp_current734 };735 }736 737 list_node<value_type>* node()738 {739 return current_;740 }741 742 const list_node<value_type>* node() const743 {744 return current_;745 }746 747 size_type idx() const748 {749 return idx_;750 }751 752 template<class ConstRef, class ConstPtr>753 operator hash_table_const_iterator<754 Value, ConstRef, ConstPtr, Size755 >() const756 {757 return hash_table_const_iterator<value_type, ConstRef, ConstPtr, size_type>{758 table_, idx_, max_idx_, current_759 };760 }761 762 private:763 hash_table_bucket<value_type, size_type>* table_;764 size_type idx_;765 size_type max_idx_;766 list_node<value_type>* current_;767 };768 769 template<class Value, class Ref, class Ptr, class Size>770 bool operator==(const hash_table_iterator<Value, Ref, Ptr, Size>& lhs,771 const hash_table_iterator<Value, Ref, Ptr, Size>& rhs)772 {773 return lhs.node() == rhs.node();774 }775 776 template<class Value, class Ref, class Ptr, class Size>777 bool operator!=(const hash_table_iterator<Value, Ref, Ptr, Size>& lhs,778 const hash_table_iterator<Value, Ref, Ptr, Size>& rhs)779 {780 return !(lhs == rhs);781 }782 783 template<class Value, class ConstReference, class ConstPointer>784 class hash_table_const_local_iterator785 {786 public:787 using value_type = Value;788 using const_reference = ConstReference;789 using const_pointer = ConstPointer;790 using difference_type = ptrdiff_t;791 792 using iterator_category = forward_iterator_tag;793 794 // TODO: requirement for forward iterator is default constructibility, fix others!795 hash_table_const_local_iterator(const list_node<value_type>* head = nullptr,796 const list_node<value_type>* current = nullptr)797 : head_{head}, current_{current}798 { /* DUMMY BODY */ }799 800 hash_table_const_local_iterator(const hash_table_const_local_iterator&) = default;801 hash_table_const_local_iterator& operator=(const hash_table_const_local_iterator&) = default;802 803 const_reference operator*() const804 {805 return current_>value;806 }807 808 const_pointer operator>() const809 {810 return ¤t_>value;811 }812 813 hash_table_const_local_iterator& operator++()814 {815 current_ = current_>next;816 if (current_ == head_)817 current_ = nullptr;818 819 return *this;820 }821 822 hash_table_const_local_iterator operator++(int)823 {824 auto tmp = current_;825 current_ = current_>next;826 if (current_ == head_)827 current_ = nullptr;828 829 return hash_table_const_local_iterator{head_, tmp};830 }831 832 833 list_node<value_type>* node()834 {835 return const_cast<list_node<value_type>*>(current_);836 }837 838 const list_node<value_type>* node() const839 {840 return current_;841 }842 843 private:844 const list_node<value_type>* head_;845 const list_node<value_type>* current_;846 };847 848 template<class Value, class ConstRef, class ConstPtr>849 bool operator==(const hash_table_const_local_iterator<Value, ConstRef, ConstPtr>& lhs,850 const hash_table_const_local_iterator<Value, ConstRef, ConstPtr>& rhs)851 {852 return lhs.node() == rhs.node();853 }854 855 template<class Value, class ConstRef, class ConstPtr>856 bool operator!=(const hash_table_const_local_iterator<Value, ConstRef, ConstPtr>& lhs,857 const hash_table_const_local_iterator<Value, ConstRef, ConstPtr>& rhs)858 {859 return !(lhs == rhs);860 }861 862 template<class Value, class Reference, class Pointer>863 class hash_table_local_iterator864 {865 public:866 using value_type = Value;867 using reference = Reference;868 using pointer = Pointer;869 using difference_type = ptrdiff_t;870 871 using iterator_category = forward_iterator_tag;872 873 hash_table_local_iterator(list_node<value_type>* head = nullptr,874 list_node<value_type>* current = nullptr)875 : head_{head}, current_{current}876 { /* DUMMY BODY */ }877 878 hash_table_local_iterator(const hash_table_local_iterator&) = default;879 hash_table_local_iterator& operator=(const hash_table_local_iterator&) = default;880 881 reference operator*()882 {883 return current_>value;884 }885 886 pointer operator>()887 {888 return ¤t_>value;889 }890 891 hash_table_local_iterator& operator++()892 {893 current_ = current_>next;894 if (current_ == head_)895 current_ = nullptr;896 897 return *this;898 }899 900 hash_table_local_iterator operator++(int)901 {902 auto tmp = current_;903 current_ = current_>next;904 if (current_ == head_)905 current_ = nullptr;906 907 return hash_table_local_iterator{head_, tmp};908 }909 910 list_node<value_type>* node()911 {912 return current_;913 }914 915 const list_node<value_type>* node() const916 {917 return current_;918 }919 920 template<class ConstRef, class ConstPtr>921 operator hash_table_const_local_iterator<922 Value, ConstRef, ConstPtr923 >() const924 {925 return hash_table_const_local_iterator<926 value_type, ConstRef, ConstPtr927 >{head_, current_};928 }929 930 private:931 list_node<value_type>* head_;932 list_node<value_type>* current_;933 };934 935 template<class Value, class Ref, class Ptr>936 bool operator==(const hash_table_local_iterator<Value, Ref, Ptr>& lhs,937 const hash_table_local_iterator<Value, Ref, Ptr>& rhs)938 {939 return lhs.node() == rhs.node();940 }941 942 template<class Value, class Ref, class Ptr>943 bool operator!=(const hash_table_local_iterator<Value, Ref, Ptr>& lhs,944 const hash_table_local_iterator<Value, Ref, Ptr>& rhs)945 {946 return !(lhs == rhs);947 }948 57 949 58 template<
Note: See TracChangeset
for help on using the changeset viewer.