hashed_index.hpp

来自「support vector clustering for vc++」· HPP 代码 · 共 1,076 行 · 第 1/3 页

    this->final_swap_(x.final());
  }

  /* observers */

  key_from_value key_extractor()const{return key;}
  hasher         hash_function()const{return hash;}
  key_equal      key_eq()const{return eq;}
  
  /* lookup */

  /* Internally, these ops rely on const_iterator being the same
   * type as iterator.
   */

  template<typename CompatibleKey>
  iterator find(const CompatibleKey& k)const
  {
    return find(k,hash,eq);
  }

  template<
    typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
  >
  iterator find(
    const CompatibleKey& k,
    const CompatibleHash& hash,const CompatiblePred& eq)const
  {
    std::size_t             buc=buckets.position(hash(k));
    hashed_index_node_impl* x=buckets.at(buc);
    hashed_index_node_impl* y=x->next();
    while(y!=x){
      if(eq(k,key(node_type::from_impl(y)->value()))){
        return make_iterator(node_type::from_impl(y));
      }
      y=y->next();
    }
    return end();
  }

  template<typename CompatibleKey>
  size_type count(const CompatibleKey& k)const
  {
    return count(k,hash,eq);
  }

  template<
    typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
  >
  size_type count(
    const CompatibleKey& k,
    const CompatibleHash& hash,const CompatiblePred& eq)const
  {
    size_type               res=0;
    std::size_t             buc=buckets.position(hash(k));
    hashed_index_node_impl* x=buckets.at(buc);
    hashed_index_node_impl* y=x->next();
    while(y!=x){
      if(eq(k,key(node_type::from_impl(y)->value()))){
        do{
          ++res;
          y=y->next();
        }while(y!=x&&eq(k,key(node_type::from_impl(y)->value())));
        break;
      }
      y=y->next();
    }
    return res;
  }

  template<typename CompatibleKey>
  std::pair<iterator,iterator> equal_range(const CompatibleKey& k)const
  {
    return equal_range(k,hash,eq);
  }

  template<
    typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
  >
  std::pair<iterator,iterator> equal_range(
    const CompatibleKey& k,
    const CompatibleHash& hash,const CompatiblePred& eq)const
  {
    std::size_t             buc=buckets.position(hash(k));
    hashed_index_node_impl* x=buckets.at(buc);
    hashed_index_node_impl* y=x->next();
    while(y!=x){
      if(eq(k,key(node_type::from_impl(y)->value()))){
        hashed_index_node_impl* y0=y;
        do{
          y=y->next();
        }while(y!=x&&eq(k,key(node_type::from_impl(y)->value())));
        if(y==x){
          do{
            ++y;
          }while(y==y->next());
          y=y->next();
        }
        return std::pair<iterator,iterator>(
          make_iterator(node_type::from_impl(y0)),
          make_iterator(node_type::from_impl(y)));
      }
      y=y->next();
    }
    return std::pair<iterator,iterator>(end(),end());
  }

  /* bucket interface */

  size_type bucket_count()const{return buckets.size();}
  size_type max_bucket_count()const{return static_cast<size_type>(-1);}

  size_type bucket_size(size_type n)const
  {
    size_type               res=0;
    hashed_index_node_impl* x=buckets.at(n);
    hashed_index_node_impl* y=x->next();
    while(y!=x){
      ++res;
      y=y->next();
    }
    return res;
  }

  size_type bucket(key_param_type k)const
  {
    return buckets.position(hash(k));
  }

  local_iterator begin(size_type n)
  {
    return const_cast<const hashed_index*>(this)->begin(n);
  }

  const_local_iterator begin(size_type n)const
  {
    hashed_index_node_impl* x=buckets.at(n);
    hashed_index_node_impl* y=x->next();
    if(y==x)return end();
    return make_iterator(node_type::from_impl(y));
  }

  local_iterator end(size_type n)
  {
    return const_cast<const hashed_index*>(this)->end(n);
  }

  const_local_iterator end(size_type n)const
  {
    hashed_index_node_impl* x=buckets.at(n);
    if(x==x->next())return end();
    do{
      ++x;
    }while(x==x->next());
    return make_iterator(node_type::from_impl(x->next()));
  }

  /* hash policy */

  float load_factor()const{return static_cast<float>(size())/bucket_count();}
  float max_load_factor()const{return mlf;}
  void  max_load_factor(float z){mlf=z;calculate_max_load();}

  void rehash(size_type n)
  {
    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
    if(size()<max_load&&n<=bucket_count())return;

    size_type bc =(std::numeric_limits<size_type>::max)();
    float     fbc=static_cast<float>(1+size()/mlf);
    if(bc>fbc){
      bc=static_cast<size_type>(fbc);
      if(bc<n)bc=n;
    }
    unchecked_rehash(bc);
  }

BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
  hashed_index(const ctor_args_list& args_list,const allocator_type& al):
    super(args_list.get_tail(),al),
    key(tuples::get<1>(args_list.get_head())),
    hash(tuples::get<2>(args_list.get_head())),
    eq(tuples::get<3>(args_list.get_head())),
    buckets(al,header()->impl(),tuples::get<0>(args_list.get_head())),
    mlf(1.0),
    first_bucket(buckets.size())
  {
    calculate_max_load();
  }

  hashed_index(
    const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x):
    super(x),

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
    safe_super(),
#endif

    key(x.key),
    hash(x.hash),
    eq(x.eq),
    buckets(x.get_allocator(),header()->impl(),x.buckets.size()),
    mlf(x.mlf),
    max_load(x.max_load),
    first_bucket(x.first_bucket)
  {
    /* Copy ctor just takes the internal configuration objects from x. The rest
     * is done in subsequent call to copy_().
     */
  }

  ~hashed_index()
  {
    /* the container is guaranteed to be empty by now */
  }

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
  iterator make_iterator(node_type* node)
  {
    return iterator(node,&buckets,this);
  }

  const_iterator make_iterator(node_type* node)const
  {
    return const_iterator(
      node,
      &const_cast<bucket_array_type&>(buckets),
      const_cast<hashed_index*>(this));
  }
#else
  iterator make_iterator(node_type* node)
  {
    return iterator(node,&buckets);
  }

  const_iterator make_iterator(node_type* node)const
  {
    return const_iterator(node,&const_cast<bucket_array_type&>(buckets));
  }
#endif

  void copy_(
    const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
    const copy_map_type& map)
  {
    for(hashed_index_node_impl* begin_org=x.buckets.begin(),
                              * begin_cpy=buckets.begin(),
                              * end_org=x.buckets.end();
        begin_org!=end_org;++begin_org,++begin_cpy){

      hashed_index_node_impl* next_org=begin_org->next();
      hashed_index_node_impl* cpy=begin_cpy;
      while(next_org!=begin_org){
        cpy->next()=
          static_cast<node_type*>(
            map.find(
              static_cast<final_node_type*>(
                node_type::from_impl(next_org))))->impl();
        next_org=next_org->next();
        cpy=cpy->next();
      }
      cpy->next()=begin_cpy;
    }

    super::copy_(x,map);
  }

  node_type* insert_(value_param_type v,node_type* x)
  {
    reserve(size()+1);

    std::size_t             buc=find_bucket(v);
    hashed_index_node_impl* pos=buckets.at(buc);
    if(!link_point(v,pos,Category()))return node_type::from_impl(pos);

    node_type* res=static_cast<node_type*>(super::insert_(v,x));
    if(res==x){
      link(x,pos);
      if(first_bucket>buc)first_bucket=buc;
    }
    return res;
  }

  node_type* insert_(value_param_type v,node_type* position,node_type* x)
  {
    reserve(size()+1);

    std::size_t             buc=find_bucket(v);
    hashed_index_node_impl* pos=buckets.at(buc);
    if(!link_point(v,pos,Category()))return node_type::from_impl(pos);

    node_type* res=static_cast<node_type*>(super::insert_(v,position,x));
    if(res==x){
      link(x,pos);
      if(first_bucket>buc)first_bucket=buc;
    }
    return res;
  }

  void erase_(node_type* x)
  {
    unlink(x);
    first_bucket=buckets.first_nonempty(first_bucket);
    super::erase_(x);

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
    detach_iterators(x);
#endif
  }

  void delete_all_nodes_()
  {
    for(hashed_index_node_impl* x=buckets.begin(),*x_end=buckets.end();
        x!=x_end;++x){
      hashed_index_node_impl* y=x->next();
      while(y!=x){
        hashed_index_node_impl* z=y->next();
        this->final_delete_node_(
          static_cast<final_node_type*>(node_type::from_impl(y)));
        y=z;
      }
    }
  }

  void clear_()
  {
    super::clear_();
    buckets.clear();
    first_bucket=buckets.size();

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
    safe_super::detach_dereferenceable_iterators();
#endif
  }

  void swap_(
    hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
  {
    std::swap(key,x.key);
    std::swap(hash,x.hash);
    std::swap(eq,x.eq);
    buckets.swap(x.buckets);
    std::swap(mlf,x.mlf);
    std::swap(max_load,x.max_load);
    std::swap(first_bucket,x.first_bucket);

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
    safe_super::swap(x);
#endif

    super::swap_(x);
  }

  bool replace_(value_param_type v,node_type* x)
  {
    if(eq(key(v),key(x->value()))){
      return super::replace_(v,x);
    }