Changeset 9751280 in mainline


Ignore:
Timestamp:
2018-07-05T21:41:22Z (6 years ago)
Author:
Dzejrou <dzejrou@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
6b18e43
Parents:
65dde99
git-author:
Dzejrou <dzejrou@…> (2018-04-28 16:24:26)
git-committer:
Dzejrou <dzejrou@…> (2018-07-05 21:41:22)
Message:

cpp: divided the hash table sources to multiple headers for better readability and shareability with rbtree in the case of key extractors

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  
    3232#include <cstdlib>
    3333#include <internal/list.hpp>
     34#include <internal/key_extractors.hpp>
     35#include <internal/hash_table_iterators.hpp>
     36#include <internal/hash_table_policies.hpp>
    3437#include <iterator>
    3538#include <limits>
    … …  
    4750     * and two proxies that either use plain Key type or a pair
    4851     * 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.
    4954     * Note: I am aware the naming is very unimaginative here,
    5055     *       not my strong side :)
    5156     */
    52 
    53     template<class Key, class Value>
    54     struct key_value_key_extractor
    55     {
    56         const Key& operator()(const pair<const Key, Value>& p) const noexcept
    57         {
    58             return p.first;
    59         }
    60     };
    61 
    62     template<class Key>
    63     struct key_no_value_key_extractor
    64     {
    65         Key& operator()(Key& k) const noexcept
    66         {
    67             return k;
    68         }
    69 
    70         const Key& operator()(const Key& k) const noexcept
    71         {
    72             return k;
    73         }
    74     };
    75 
    76     template<class Value, class Size>
    77     struct hash_table_bucket
    78     {
    79         /**
    80          * Note: We use a doubly linked list because
    81          *       we need to use hints, which point to the
    82          *       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 noexcept
    92         {
    93             auto current = head;
    94             Size res{};
    95 
    96             do
    97             {
    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             else
    111                 head->append(node);
    112         }
    113 
    114         void prepend(list_node<Value>* node)
    115         {
    116             if (!head)
    117                 head = node;
    118             else
    119                 head->prepend(node);
    120         }
    121 
    122         void clear()
    123         {
    124             if (!head)
    125                 return;
    126 
    127             auto current = head;
    128             do
    129             {
    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_policy
    146     {
    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                 idx
    161             );
    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             do
    172             {
    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                         else
    182                             table.table_[idx].head = nullptr;
    183                     }
    184 
    185                     current->unlink();
    186                     delete current;
    187 
    188                     return 1;
    189                 }
    190                 else
    191                     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::iterator
    202         > 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_iterator
    212         > 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 distinction
    221          *       between the arguments) is only created if the value isn't
    222          *       in the table already.
    223          */
    224 
    225         template<class Table, class... Args>
    226         static pair<
    227             typename Table::iterator, bool
    228         > 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                         target
    251                     },
    252                     false
    253                 );
    254             }
    255             else
    256             {
    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                     node
    264                 }, true);
    265             }
    266         }
    267 
    268         template<class Table, class Value>
    269         static pair<
    270             typename Table::iterator, bool
    271         > 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                         target
    292                     },
    293                     false
    294                 );
    295             }
    296             else
    297             {
    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                     node
    305                 }, true);
    306             }
    307         }
    308 
    309         template<class Table, class Value>
    310         static pair<
    311             typename Table::iterator, bool
    312         > 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                         target
    334                     },
    335                     false
    336                 );
    337             }
    338             else
    339             {
    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                     node
    347                 }, true);
    348             }
    349         }
    350     };
    351 
    352     struct hash_multi_policy
    353     {
    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             do
    364             {
    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                 do
    385                 {
    386                     if (table.keys_equal(key, current->value))
    387                     {
    388                         return make_tuple(
    389                             &table.table_[idx],
    390                             current,
    391                             idx
    392                         );
    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                 idx
    403             );
    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::iterator
    442         > 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             do
    450             {
    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_iterator
    461         > 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             do
    469             {
    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, bool
    479         > 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, bool
    491         > 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, bool
    503         > 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, bool
    516         > 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             else
    531                 bucket->prepend(node);
    532 
    533             return make_pair(iterator{
    534                 table.table(), idx,
    535                 table.bucket_count(),
    536                 node
    537             }, true);
    538         }
    539     };
    540 
    541     template<class Value, class ConstReference, class ConstPointer, class Size>
    542     class hash_table_const_iterator
    543     {
    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*() const
    563             {
    564                 return current_->value;
    565             }
    566 
    567             const_pointer operator->() const
    568             {
    569                 return &current_->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                         else
    585                             current_ = nullptr;
    586                     }
    587                     else
    588                         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                         else
    610                             current_ = nullptr;
    611                     }
    612                     else
    613                         current_ = nullptr;
    614                 }
    615 
    616                 return hash_table_const_iterator{
    617                     table_, tmp_idx, max_idx_, tmp_current
    618                 };
    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() const
    627             {
    628                 return current_;
    629             }
    630 
    631             size_type idx() const
    632             {
    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_iterator
    659     {
    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 &current_->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                         else
    701                             current_ = nullptr;
    702                     }
    703                     else
    704                         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                         else
    726                             current_ = nullptr;
    727                     }
    728                     else
    729                         current_ = nullptr;
    730                 }
    731 
    732                 return hash_table_iterator{
    733                     table_, tmp_idx, max_idx_, tmp_current
    734                 };
    735             }
    736 
    737             list_node<value_type>* node()
    738             {
    739                 return current_;
    740             }
    741 
    742             const list_node<value_type>* node() const
    743             {
    744                 return current_;
    745             }
    746 
    747             size_type idx() const
    748             {
    749                 return idx_;
    750             }
    751 
    752             template<class ConstRef, class ConstPtr>
    753             operator hash_table_const_iterator<
    754                 Value, ConstRef, ConstPtr, Size
    755             >() const
    756             {
    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_iterator
    785     {
    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*() const
    804             {
    805                 return current_->value;
    806             }
    807 
    808             const_pointer operator->() const
    809             {
    810                 return &current_->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() const
    839             {
    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_iterator
    864     {
    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 &current_->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() const
    916             {
    917                 return current_;
    918             }
    919 
    920             template<class ConstRef, class ConstPtr>
    921             operator hash_table_const_local_iterator<
    922                 Value, ConstRef, ConstPtr
    923             >() const
    924             {
    925                 return hash_table_const_local_iterator<
    926                     value_type, ConstRef, ConstPtr
    927                 >{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     }
    94857
    94958    template<
Note: See TracChangeset for help on using the changeset viewer.