Line data    Source code

       1             : //
       2             : // immer: immutable data structures for C++
       3             : // Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
       4             : //
       5             : // This software is distributed under the Boost Software License, Version 1.0.
       6             : // See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
       7             : //
       8             : 
       9             : #pragma once
      10             : 
      11             : #include <immer/detail/hamts/champ.hpp>
      12             : #include <immer/detail/iterator_facade.hpp>
      13             : 
      14             : namespace immer {
      15             : namespace detail {
      16             : namespace hamts {
      17             : 
      18             : template <typename T, typename Hash, typename Eq, typename MP, bits_t B>
      19             : struct champ_iterator
      20             :     : iterator_facade<champ_iterator<T, Hash, Eq, MP, B>,
      21             :                       std::forward_iterator_tag,
      22             :                       T,
      23             :                       const T&,
      24             :                       std::ptrdiff_t,
      25             :                       const T*>
      26             : {
      27             :     using tree_t = champ<T, Hash, Eq, MP, B>;
      28             :     using node_t = typename tree_t::node_t;
      29             : 
      30             :     struct end_t
      31             :     {};
      32             : 
      33       79356 :     champ_iterator(const tree_t& v)
      34       79356 :         : depth_{0}
      35             :     {
      36       79356 :         if (v.root->datamap()) {
      37       67168 :             cur_ = v.root->values();
      38       67168 :             end_ = v.root->values() + v.root->data_count();
      39             :         } else {
      40       12188 :             cur_ = end_ = nullptr;
      41             :         }
      42       79356 :         path_[0] = &v.root;
      43       79356 :         ensure_valid_();
      44       79356 :     }
      45             : 
      46       79356 :     champ_iterator(const tree_t& v, end_t)
      47             :         : cur_{nullptr}
      48             :         , end_{nullptr}
      49             :         , depth_{0}
      50             :     {
      51             :         path_[0] = &v.root;
      52             :     }
      53             : 
      54             :     champ_iterator(const champ_iterator& other)
      55             :         : cur_{other.cur_}
      56             :         , end_{other.end_}
      57             :         , depth_{other.depth_}
      58             :     {
      59             :         std::copy(other.path_, other.path_ + depth_ + 1, path_);
      60             :     }
      61             : 
      62             : private:
      63             :     friend iterator_core_access;
      64             : 
      65             :     T* cur_;
      66             :     T* end_;
      67             :     count_t depth_;
      68             :     node_t* const* path_[max_depth<B> + 1] = {
      69             :         0,
      70             :     };
      71             : 
      72      350082 :     void increment()
      73             :     {
      74      350082 :         ++cur_;
      75      350082 :         ensure_valid_();
      76             :     }
      77             : 
      78      114914 :     bool step_down()
      79             :     {
      80      114914 :         if (depth_ < max_depth<B>) {
      81      114914 :             auto parent = *path_[depth_];
      82      114914 :             assert(parent);
      83      114914 :             if (parent->nodemap()) {
      84       27422 :                 ++depth_;
      85       27422 :                 path_[depth_] = parent->children();
      86       27422 :                 auto child    = *path_[depth_];
      87       27422 :                 assert(child);
      88       27422 :                 if (depth_ < max_depth<B>) {
      89       27422 :                     if (child->datamap()) {
      90       27422 :                         cur_ = child->values();
      91       27422 :                         end_ = cur_ + child->data_count();
      92             :                     }
      93             :                 } else {
      94           0 :                     cur_ = child->collisions();
      95           0 :                     end_ = cur_ + child->collision_count();
      96             :                 }
      97       27422 :                 return true;
      98             :             }
      99             :         }
     100             :         return false;
     101             :     }
     102             : 
     103       87492 :     bool step_right()
     104             :     {
     105      114892 :         while (depth_ > 0) {
     106       35627 :             auto parent = *path_[depth_ - 1];
     107       35627 :             auto last   = parent->children() + parent->children_count();
     108       35627 :             auto next   = path_[depth_] + 1;
     109       35627 :             if (next < last) {
     110        8227 :                 path_[depth_] = next;
     111        8227 :                 auto child    = *path_[depth_];
     112        8227 :                 assert(child);
     113        8227 :                 if (depth_ < max_depth<B>) {
     114        8227 :                     if (child->datamap()) {
     115        7199 :                         cur_ = child->values();
     116        7199 :                         end_ = cur_ + child->data_count();
     117             :                     }
     118             :                 } else {
     119           0 :                     cur_ = child->collisions();
     120           0 :                     end_ = cur_ + child->collision_count();
     121             :                 }
     122        8227 :                 return true;
     123             :             }
     124       27400 :             --depth_;
     125             :         }
     126             :         return false;
     127             :     }
     128             : 
     129      429438 :     void ensure_valid_()
     130             :     {
     131      437665 :         while (cur_ == end_) {
     132      114914 :             while (step_down())
     133       27422 :                 if (cur_ != end_)
     134             :                     return;
     135       87492 :             if (!step_right()) {
     136             :                 // end of sequence
     137       79265 :                 assert(depth_ == 0);
     138       79265 :                 cur_ = end_ = nullptr;
     139       79265 :                 return;
     140             :             }
     141             :         }
     142             :     }
     143             : 
     144      429438 :     bool equal(const champ_iterator& other) const { return cur_ == other.cur_; }
     145             : 
     146      350173 :     const T& dereference() const { return *cur_; }
     147             : };
     148             : 
     149             : } // namespace hamts
     150             : } // namespace detail
     151             : } // namespace immer