source: NonGTP/Boost/boost/multi_index/hashed_index.hpp @ 857

Revision 857, 30.0 KB checked in by igarcia, 19 years ago (diff)
Line 
1/* Copyright 2003-2005 Joaquín M López Muñoz.
2 * Distributed under the Boost Software License, Version 1.0.
3 * (See accompanying file LICENSE_1_0.txt or copy at
4 * http://www.boost.org/LICENSE_1_0.txt)
5 *
6 * See http://www.boost.org/libs/multi_index for library home page.
7 */
8
9#ifndef BOOST_MULTI_INDEX_HASHED_INDEX_HPP
10#define BOOST_MULTI_INDEX_HASHED_INDEX_HPP
11
12#if defined(_MSC_VER)&&(_MSC_VER>=1200)
13#pragma once
14#endif
15
16#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
17#include <algorithm>
18#include <boost/call_traits.hpp>
19#include <boost/detail/allocator_utilities.hpp>
20#include <boost/detail/no_exceptions_support.hpp>
21#include <boost/detail/workaround.hpp>
22#include <boost/limits.hpp>
23#include <boost/mpl/push_front.hpp>
24#include <boost/multi_index/detail/access_specifier.hpp>
25#include <boost/multi_index/detail/auto_space.hpp>
26#include <boost/multi_index/detail/bucket_array.hpp>
27#include <boost/multi_index/detail/hash_index_iterator.hpp>
28#include <boost/multi_index/detail/modify_key_adaptor.hpp>
29#include <boost/multi_index/detail/safe_mode.hpp>
30#include <boost/multi_index/detail/scope_guard.hpp>
31#include <boost/multi_index/hashed_index_fwd.hpp>
32#include <boost/tuple/tuple.hpp>
33#include <cstddef>
34#include <functional>
35#include <utility>
36
37#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
38#include <boost/serialization/nvp.hpp>
39#endif
40
41#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
42#define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT                       \
43  detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)=                 \
44    detail::make_obj_guard(*this,&hashed_index::check_invariant_);           \
45  BOOST_JOIN(check_invariant_,__LINE__).touch();
46#else
47#define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT
48#endif
49
50namespace boost{
51
52namespace multi_index{
53
54namespace detail{
55
56/* hashed_index adds a layer of hashed indexing to a given Super */
57
58/* Most of the implementation of unique and non-unique indices is
59 * shared. We tell from one another on instantiation time by using
60 * these tags.
61 */
62
63struct hashed_unique_tag{};
64struct hashed_non_unique_tag{};
65
66template<
67  typename KeyFromValue,typename Hash,typename Pred,
68  typename SuperMeta,typename TagList,typename Category
69>
70
71#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
72#if BOOST_WORKAROUND(BOOST_MSVC,<1300)
73class hashed_index:
74  BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type,
75  public hashed_index_proxy<
76    hashed_index_node<SuperMeta::type::node_type>,
77    bucket_array<SuperMeta::type::final_allocator_type> >
78#else
79class hashed_index:
80  BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type,
81  public safe_container<
82    hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category> >
83#endif
84#else
85class hashed_index:
86  BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
87#endif
88
89{
90#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
91    BOOST_WORKAROUND(__MWERKS__,<=0x3003)
92/* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
93 * lifetime of const references bound to temporaries --precisely what
94 * scopeguards are.
95 */
96
97#pragma parse_mfunc_templ off
98#endif
99
100  typedef typename SuperMeta::type                   super;
101
102protected:
103  typedef hashed_index_node<
104    typename super::node_type>                       node_type;
105  typedef bucket_array<
106    typename super::final_allocator_type>            bucket_array_type;
107
108public:
109  /* types */
110
111  typedef typename KeyFromValue::result_type         key_type;
112  typedef typename node_type::value_type             value_type;
113  typedef KeyFromValue                               key_from_value;
114  typedef Hash                                       hasher;
115  typedef Pred                                       key_equal;
116  typedef tuple<std::size_t,
117    key_from_value,hasher,key_equal>                 ctor_args;
118  typedef typename super::final_allocator_type       allocator_type;
119  typedef typename allocator_type::pointer           pointer;
120  typedef typename allocator_type::const_pointer     const_pointer;
121  typedef typename allocator_type::reference         reference;
122  typedef typename allocator_type::const_reference   const_reference;
123  typedef std::size_t                                size_type;     
124  typedef std::ptrdiff_t                             difference_type;
125
126#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
127#if BOOST_WORKAROUND(BOOST_MSVC,<1300)
128  typedef hashed_index_iterator<
129    node_type,bucket_array_type>                     iterator;
130  typedef hashed_index_iterator<
131    node_type,bucket_array_type>                     const_iterator;
132#else
133  typedef hashed_index_iterator<
134    node_type,bucket_array_type,hashed_index>        iterator;
135  typedef hashed_index_iterator<
136    node_type,bucket_array_type,hashed_index>        const_iterator;
137#endif
138#else
139  typedef hashed_index_iterator<
140    node_type,bucket_array_type>                     iterator;
141  typedef hashed_index_iterator<
142    node_type,bucket_array_type>                     const_iterator;
143#endif
144
145  typedef iterator                                   local_iterator;
146  typedef const_iterator                             const_local_iterator;
147  typedef TagList                                    tag_list;
148
149protected:
150  typedef typename super::final_node_type     final_node_type;
151  typedef tuples::cons<
152    ctor_args,
153    typename super::ctor_args_list>           ctor_args_list;
154  typedef typename mpl::push_front<
155    typename super::index_type_list,
156    hashed_index>::type                       index_type_list;
157  typedef typename mpl::push_front<
158    typename super::iterator_type_list,
159    iterator>::type                           iterator_type_list;
160  typedef typename mpl::push_front<
161    typename super::const_iterator_type_list,
162    const_iterator>::type                     const_iterator_type_list;
163  typedef typename super::copy_map_type       copy_map_type;
164
165#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
166  typedef typename super::index_saver_type    index_saver_type;
167  typedef typename super::index_loader_type   index_loader_type;
168#endif
169
170private:
171#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
172#if BOOST_WORKAROUND(BOOST_MSVC,<1300)
173  typedef hashed_index_proxy<
174    node_type,bucket_array_type>          safe_super;
175#else
176  typedef safe_container<hashed_index>    safe_super;
177#endif
178#endif
179
180  typedef typename call_traits<value_type>::param_type value_param_type;
181  typedef typename call_traits<
182    key_type>::param_type                              key_param_type;
183
184public:
185
186  /* construct/destroy/copy
187   * Default and copy ctors are in the protected section as indices are
188   * not supposed to be created on their own. No range ctor either.
189   */
190
191  hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& operator=(
192    const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
193  {
194    this->final()=x.final();
195    return *this;
196  }
197
198  allocator_type get_allocator()const
199  {
200    return this->final().get_allocator();
201  }
202
203  /* size and capacity */
204
205  bool      empty()const{return this->final_empty_();}
206  size_type size()const{return this->final_size_();}
207  size_type max_size()const{return this->final_max_size_();}
208
209  /* iterators */
210
211  iterator begin()
212  {
213    return make_iterator(
214      node_type::from_impl(buckets.at(first_bucket)->next()));
215  }
216
217  const_iterator begin()const
218  {
219    return make_iterator(
220      node_type::from_impl(buckets.at(first_bucket)->next()));
221  }
222
223  iterator       end(){return make_iterator(header());}
224  const_iterator end()const{return make_iterator(header());}
225
226  /* modifiers */
227
228  std::pair<iterator,bool> insert(value_param_type x)
229  {
230    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
231    std::pair<final_node_type*,bool> p=this->final_insert_(x);
232    return std::pair<iterator,bool>(make_iterator(p.first),p.second);
233  }
234
235  iterator insert(iterator position,value_param_type x)
236  {
237    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
238    BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
239    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
240    std::pair<final_node_type*,bool> p=this->final_insert_(
241      x,static_cast<final_node_type*>(position.get_node()));
242    return make_iterator(p.first);
243  }
244   
245  template<typename InputIterator>
246  void insert(InputIterator first,InputIterator last)
247  {
248    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
249    iterator hint=end();
250    for(;first!=last;++first)hint=insert(hint,*first);
251  }
252
253  iterator erase(iterator position)
254  {
255    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
256    BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
257    BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
258    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
259    this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
260    return position;
261  }
262 
263  size_type erase(key_param_type x)
264  {
265    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
266
267    size_type s=0;
268    iterator it=find(x); /* caveat: relies on find() returning */
269    if(it!=end()){       /* the first element                  */
270      do{
271        it=erase(it);
272        ++s;
273      }while(it!=end()&&eq(x,key(*it)));
274    }
275
276    return s;
277  }
278
279  iterator erase(iterator first,iterator last)
280  {
281    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
282    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
283    BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
284    BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
285    BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
286    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
287    while(first!=last){
288      first=erase(first);
289    }
290    return first;
291  }
292
293  bool replace(iterator position,value_param_type x)
294  {
295    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
296    BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
297    BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
298    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
299    return this->final_replace_(
300      x,static_cast<final_node_type*>(position.get_node()));
301  }
302
303  template<typename Modifier>
304  bool modify(iterator position,Modifier mod)
305  {
306    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
307    BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
308    BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
309    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
310
311#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
312    /* MSVC++ 6.0 optimizer on safe mode code chokes if this
313     * this is not added. Left it for all compilers as it does no
314     * harm.
315     */
316
317    position.detach();
318#endif
319
320    return this->final_modify_(
321      mod,static_cast<final_node_type*>(position.get_node()));
322  }
323
324  template<typename Modifier>
325  bool modify_key(iterator position,Modifier mod)
326  {
327    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
328    BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
329    BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
330    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
331    return modify(
332      position,modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key));
333  }
334
335  void clear()
336  {
337    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
338    this->final_clear_();
339  }
340
341  void swap(hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
342  {
343    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
344    this->final_swap_(x.final());
345  }
346
347  /* observers */
348
349  key_from_value key_extractor()const{return key;}
350  hasher         hash_function()const{return hash;}
351  key_equal      key_eq()const{return eq;}
352 
353  /* lookup */
354
355  /* Internally, these ops rely on const_iterator being the same
356   * type as iterator.
357   */
358
359  template<typename CompatibleKey>
360  iterator find(const CompatibleKey& k)const
361  {
362    return find(k,hash,eq);
363  }
364
365  template<
366    typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
367  >
368  iterator find(
369    const CompatibleKey& k,
370    const CompatibleHash& hash,const CompatiblePred& eq)const
371  {
372    std::size_t             buc=buckets.position(hash(k));
373    hashed_index_node_impl* x=buckets.at(buc);
374    hashed_index_node_impl* y=x->next();
375    while(y!=x){
376      if(eq(k,key(node_type::from_impl(y)->value))){
377        return make_iterator(node_type::from_impl(y));
378      }
379      y=y->next();
380    }
381    return end();
382  }
383
384  template<typename CompatibleKey>
385  size_type count(const CompatibleKey& k)const
386  {
387    return count(k,hash,eq);
388  }
389
390  template<
391    typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
392  >
393  size_type count(
394    const CompatibleKey& k,
395    const CompatibleHash& hash,const CompatiblePred& eq)const
396  {
397    size_type               res=0;
398    std::size_t             buc=buckets.position(hash(k));
399    hashed_index_node_impl* x=buckets.at(buc);
400    hashed_index_node_impl* y=x->next();
401    while(y!=x){
402      if(eq(k,key(node_type::from_impl(y)->value))){
403        do{
404          ++res;
405          y=y->next();
406        }while(y!=x&&eq(k,key(node_type::from_impl(y)->value)));
407        break;
408      }
409      y=y->next();
410    }
411    return res;
412  }
413
414  template<typename CompatibleKey>
415  std::pair<iterator,iterator> equal_range(const CompatibleKey& k)const
416  {
417    return equal_range(k,hash,eq);
418  }
419
420  template<
421    typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
422  >
423  std::pair<iterator,iterator> equal_range(
424    const CompatibleKey& k,
425    const CompatibleHash& hash,const CompatiblePred& eq)const
426  {
427    std::size_t             buc=buckets.position(hash(k));
428    hashed_index_node_impl* x=buckets.at(buc);
429    hashed_index_node_impl* y=x->next();
430    while(y!=x){
431      if(eq(k,key(node_type::from_impl(y)->value))){
432        hashed_index_node_impl* y0=y;
433        do{
434          y=y->next();
435        }while(y!=x&&eq(k,key(node_type::from_impl(y)->value)));
436        if(y==x){
437          do{
438            ++y;
439          }while(y==y->next());
440          y=y->next();
441        }
442        return std::pair<iterator,iterator>(
443          make_iterator(node_type::from_impl(y0)),
444          make_iterator(node_type::from_impl(y)));
445      }
446      y=y->next();
447    }
448    return std::pair<iterator,iterator>(end(),end());
449  }
450
451  /* bucket interface */
452
453  size_type bucket_count()const{return buckets.size();}
454  size_type max_bucket_count()const{return static_cast<size_type>(-1);}
455
456  size_type bucket_size(size_type n)const
457  {
458    size_type               res=0;
459    hashed_index_node_impl* x=buckets.at(n);
460    hashed_index_node_impl* y=x->next();
461    while(y!=x){
462      ++res;
463      y=y->next();
464    }
465    return res;
466  }
467
468  size_type bucket(key_param_type k)const
469  {
470    return buckets.position(hash(k));
471  }
472
473  local_iterator begin(size_type n)
474  {
475    return const_cast<const hashed_index*>(this)->begin(n);
476  }
477
478  const_local_iterator begin(size_type n)const
479  {
480    hashed_index_node_impl* x=buckets.at(n);
481    hashed_index_node_impl* y=x->next();
482    if(y==x)return end();
483    return make_iterator(node_type::from_impl(y));
484  }
485
486  local_iterator end(size_type n)
487  {
488    return const_cast<const hashed_index*>(this)->end(n);
489  }
490
491  const_local_iterator end(size_type n)const
492  {
493    hashed_index_node_impl* x=buckets.at(n);
494    if(x==x->next())return end();
495    do{
496      ++x;
497    }while(x==x->next());
498    return make_iterator(node_type::from_impl(x->next()));
499  }
500
501  /* hash policy */
502
503  float load_factor()const{return static_cast<float>(size())/bucket_count();}
504  float max_load_factor()const{return mlf;}
505  void  max_load_factor(float z){mlf=z;calculate_max_load();}
506
507  void rehash(size_type n)
508  {
509    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
510    if(size()<max_load&&n<=bucket_count())return;
511
512    size_type bc =(std::numeric_limits<size_type>::max)();
513    float     fbc=static_cast<float>(1+size()/mlf);
514    if(bc>fbc){
515      bc=static_cast<size_type>(fbc);
516      if(bc<n)bc=n;
517    }
518    unchecked_rehash(bc);
519  }
520
521BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
522  hashed_index(const ctor_args_list& args_list,const allocator_type& al):
523    super(args_list.get_tail(),al),
524
525#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)&&\
526    BOOST_WORKAROUND(BOOST_MSVC,<1300)
527    safe_super(final_header(),buckets),
528#endif
529
530    key(tuples::get<1>(args_list.get_head())),
531    hash(tuples::get<2>(args_list.get_head())),
532    eq(tuples::get<3>(args_list.get_head())),
533    buckets(al,header()->impl(),tuples::get<0>(args_list.get_head())),
534    mlf(1.0),
535    first_bucket(buckets.size())
536  {
537    calculate_max_load();
538  }
539
540  hashed_index(
541    const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x):
542    super(x),
543
544#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)&&\
545    BOOST_WORKAROUND(BOOST_MSVC,<1300)
546    safe_super(final_header(),buckets),
547#endif
548
549    key(x.key),
550    hash(x.hash),
551    eq(x.eq),
552    buckets(x.get_allocator(),header()->impl(),x.buckets.size()),
553    mlf(x.mlf),
554    max_load(x.max_load),
555    first_bucket(x.first_bucket)
556  {
557    /* Copy ctor just takes the internal configuration objects from x. The rest
558     * is done in subsequent call to copy_().
559     */
560  }
561
562  ~hashed_index()
563  {
564    /* the container is guaranteed to be empty by now */
565  }
566
567#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
568  iterator make_iterator(node_type* node)
569  {
570    return iterator(node,buckets,this);
571  }
572
573  const_iterator make_iterator(node_type* node)const
574  {
575    return const_iterator(
576      node,
577      const_cast<bucket_array_type&>(buckets),
578      const_cast<hashed_index*>(this));
579  }
580#else
581  iterator make_iterator(node_type* node)
582  {
583    return iterator(node,buckets);
584  }
585
586  const_iterator make_iterator(node_type* node)const
587  {
588    return const_iterator(node,const_cast<bucket_array_type&>(buckets));
589  }
590#endif
591
592  void copy_(
593    const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
594    const copy_map_type& map)
595  {
596    for(hashed_index_node_impl* begin_org=x.buckets.begin(),
597                              * begin_cpy=buckets.begin(),
598                              * end_org=x.buckets.end();
599        begin_org!=end_org;++begin_org,++begin_cpy){
600
601      hashed_index_node_impl* next_org=begin_org->next();
602      hashed_index_node_impl* cpy=begin_cpy;
603      while(next_org!=begin_org){
604        cpy->next()=
605          static_cast<node_type*>(
606            map.find(
607              static_cast<final_node_type*>(
608                node_type::from_impl(next_org))))->impl();
609        next_org=next_org->next();
610        cpy=cpy->next();
611      }
612      cpy->next()=begin_cpy;
613    }
614
615    super::copy_(x,map);
616  }
617
618  node_type* insert_(value_param_type v,node_type* x)
619  {
620    reserve(size()+1);
621
622    std::size_t             buc=find_bucket(v);
623    hashed_index_node_impl* pos=buckets.at(buc);
624    if(!link_point(v,pos,Category()))return node_type::from_impl(pos);
625
626    node_type* res=static_cast<node_type*>(super::insert_(v,x));
627    if(res==x){
628      link(x,pos);
629      if(first_bucket>buc)first_bucket=buc;
630    }
631    return res;
632  }
633
634  node_type* insert_(value_param_type v,node_type* position,node_type* x)
635  {
636    reserve(size()+1);
637
638    std::size_t             buc=find_bucket(v);
639    hashed_index_node_impl* pos=buckets.at(buc);
640    if(!link_point(v,pos,Category()))return node_type::from_impl(pos);
641
642    node_type* res=static_cast<node_type*>(super::insert_(v,position,x));
643    if(res==x){
644      link(x,pos);
645      if(first_bucket>buc)first_bucket=buc;
646    }
647    return res;
648  }
649
650  void erase_(node_type* x)
651  {
652    unlink(x);
653    first_bucket=buckets.first_nonempty(first_bucket);
654    super::erase_(x);
655
656#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
657    detach_iterators(x);
658#endif
659  }
660
661  void delete_all_nodes_()
662  {
663    for(hashed_index_node_impl* x=buckets.begin(),*x_end=buckets.end();
664        x!=x_end;++x){
665      hashed_index_node_impl* y=x->next();
666      while(y!=x){
667        hashed_index_node_impl* z=y->next();
668        this->final_delete_node_(
669          static_cast<final_node_type*>(node_type::from_impl(y)));
670        y=z;
671      }
672    }
673  }
674
675  void clear_()
676  {
677    super::clear_();
678    buckets.clear();
679    first_bucket=buckets.size();
680
681#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
682    safe_super::detach_all_iterators();
683#endif
684  }
685
686  void swap_(
687    hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
688  {
689    std::swap(key,x.key);
690    std::swap(hash,x.hash);
691    std::swap(eq,x.eq);
692    buckets.swap(x.buckets);
693    std::swap(mlf,x.mlf);
694    std::swap(max_load,x.max_load);
695    std::swap(first_bucket,x.first_bucket);
696
697#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
698    safe_super::swap(x);
699#endif
700
701    super::swap_(x);
702  }
703
704  bool replace_(value_param_type v,node_type* x)
705  {
706    if(eq(key(v),key(x->value))){
707      return super::replace_(v,x);
708    }
709
710    hashed_index_node_impl* y=prev(x);
711    unlink_next(y);
712
713    BOOST_TRY{
714      std::size_t             buc=find_bucket(v);
715      hashed_index_node_impl* pos=buckets.at(buc);
716      if(link_point(v,pos,Category())&&super::replace_(v,x)){
717        link(x,pos);
718        if(first_bucket>buc){
719          first_bucket=buc;
720        }
721        else if(first_bucket<buc){
722          first_bucket=buckets.first_nonempty(first_bucket);
723        }
724        return true;
725      }
726      link(x,y);
727      return false;
728    }
729    BOOST_CATCH(...){
730      link(x,y);
731      BOOST_RETHROW;
732    }
733    BOOST_CATCH_END
734  }
735
736  bool modify_(node_type* x)
737  {
738    unlink(x);
739
740    std::size_t             buc;
741    hashed_index_node_impl* pos;
742    BOOST_TRY
743    {
744      buc=find_bucket(x->value);
745      pos=buckets.at(buc);
746      if(!link_point(x->value,pos,Category())){
747        first_bucket=buckets.first_nonempty(first_bucket);
748        super::erase_(x);
749
750#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
751        detach_iterators(x);
752#endif
753        return false;
754      }
755
756    }
757    BOOST_CATCH(...){
758      first_bucket=buckets.first_nonempty(first_bucket);
759      super::erase_(x);
760
761#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
762      detach_iterators(x);
763#endif
764
765      BOOST_RETHROW;
766    }
767    BOOST_CATCH_END
768
769    BOOST_TRY{
770      if(super::modify_(x)){
771        link(x,pos);
772        if(first_bucket>buc){
773          first_bucket=buc;
774        }
775        else if(first_bucket<buc){
776          first_bucket=buckets.first_nonempty(first_bucket);
777        }
778        return true;
779      }
780
781      first_bucket=buckets.first_nonempty(first_bucket);
782
783#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
784      detach_iterators(x);
785#endif
786      return false;
787    }
788    BOOST_CATCH(...){
789      first_bucket=buckets.first_nonempty(first_bucket);
790
791#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
792      detach_iterators(x);
793#endif
794
795      BOOST_RETHROW;
796    }
797    BOOST_CATCH_END
798  }
799
800#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
801  /* serialization */
802
803  template<typename Archive>
804  void save_(
805    Archive& ar,const unsigned int version,const index_saver_type& sm)const
806  {
807    ar<<serialization::make_nvp("position",buckets);
808    super::save_(ar,version,sm);
809  }
810
811  template<typename Archive>
812  void load_(Archive& ar,const unsigned int version,const index_loader_type& lm)
813  {
814    ar>>serialization::make_nvp("position",buckets);
815    super::load_(ar,version,lm);
816  }
817#endif
818
819#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
820  /* invariant stuff */
821
822  bool invariant_()const
823  {
824    if(size()==0||begin()==end()){
825      if(size()!=0||begin()!=end())return false;
826    }
827    else{
828      size_type s0=0;
829      for(const_iterator it=begin(),it_end=end();it!=it_end;++it,++s0){}
830      if(s0!=size())return false;
831
832      size_type s1=0;
833      for(size_type buc=0;buc<bucket_count();++buc){
834        size_type ss1=0;
835        for(const_local_iterator it=begin(buc),it_end=end(buc);
836            it!=it_end;++it,++ss1){
837          if(find_bucket(*it)!=buc)return false;
838        }
839        if(ss1!=bucket_size(buc))return false;
840        s1+=ss1;
841      }
842      if(s1!=size())return false;
843    }
844
845    if(first_bucket!=buckets.first_nonempty(0))return false;
846
847    return super::invariant_();
848  }
849
850  /* This forwarding function eases things for the boost::mem_fn construct
851   * in BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT. Actually,
852   * final_check_invariant is already an inherited member function of index.
853   */
854  void check_invariant_()const{this->final_check_invariant_();}
855#endif
856
857private:
858  node_type* header()const{return this->final_header();}
859
860  std::size_t find_bucket(value_param_type v)const
861  {
862    return bucket(key(v));
863  }
864
865  bool link_point(
866    value_param_type v,hashed_index_node_impl*& pos,hashed_unique_tag)
867  {
868    hashed_index_node_impl* x=pos->next();
869    while(x!=pos){
870      if(eq(key(v),key(node_type::from_impl(x)->value))){
871        pos=x;
872        return false;
873      }
874      x=x->next();
875    }
876    return true;
877  }
878
879  bool link_point(
880    value_param_type v,hashed_index_node_impl*& pos,hashed_non_unique_tag)
881  {
882    hashed_index_node_impl* prev=pos;
883    hashed_index_node_impl* x=pos->next();
884    while(x!=pos){
885      if(eq(key(v),key(node_type::from_impl(x)->value))){
886        pos=prev;
887        return true;
888      }
889      prev=x;
890      x=x->next();
891    }
892    return true;
893  }
894 
895  void link(node_type* x,hashed_index_node_impl* pos)
896  {
897    hashed_index_node_impl::link(x->impl(),pos);
898  };
899
900  void link(hashed_index_node_impl* x,hashed_index_node_impl* pos)
901  {
902    hashed_index_node_impl::link(x,pos);
903  };
904
905  void unlink(node_type* x)
906  {
907    hashed_index_node_impl::unlink(x->impl());
908  };
909
910  static hashed_index_node_impl* prev(node_type* x)
911  {
912    return hashed_index_node_impl::prev(x->impl());
913  }
914
915  static void unlink_next(hashed_index_node_impl* x)
916  {
917    hashed_index_node_impl::unlink_next(x);
918  }
919
920  void calculate_max_load()
921  {
922    float fml=static_cast<float>(mlf*bucket_count());
923    max_load=(std::numeric_limits<size_type>::max)();
924    if(max_load>fml)max_load=static_cast<size_type>(fml);
925  }
926
927  void reserve(size_type n)
928  {
929    if(n>max_load){
930      size_type bc =(std::numeric_limits<size_type>::max)();
931      float     fbc=static_cast<float>(1+n/mlf);
932      if(bc>fbc)bc =static_cast<size_type>(fbc);
933      unchecked_rehash(bc);
934    }
935  }
936
937  void unchecked_rehash(size_type n)
938  {
939    bucket_array_type buckets1(get_allocator(),header()->impl(),n);
940    auto_space<std::size_t,allocator_type> hashes(get_allocator(),size());
941
942    std::size_t i=0;
943    hashed_index_node_impl* x=buckets.begin();
944    hashed_index_node_impl* x_end=buckets.end();
945    for(;x!=x_end;++x){
946      hashed_index_node_impl* y=x->next();
947      while(y!=x){
948        hashes.data()[i++]=hash(key(node_type::from_impl(y)->value));
949        y=y->next();
950      }
951    }
952
953    i=0;
954    x=buckets.begin();
955    for(;x!=x_end;++x){
956      hashed_index_node_impl* y=x->next();
957      while(y!=x){
958        hashed_index_node_impl* z=y->next();
959        std::size_t             buc1=buckets1.position(hashes.data()[i++]);
960        hashed_index_node_impl* x1=buckets1.at(buc1);
961        link(y,x1);
962        y=z;
963      }
964    }
965
966    buckets.swap(buckets1);
967    calculate_max_load();
968    first_bucket=buckets.first_nonempty(0);
969  }
970
971#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
972  void detach_iterators(node_type* x)
973  {
974    iterator it=make_iterator(x);
975    safe_mode::detach_equivalent_iterators(it);
976  }
977#endif
978
979  key_from_value               key;
980  hasher                       hash;
981  key_equal                    eq;
982  bucket_array_type            buckets;
983  float                        mlf;
984  size_type                    max_load;
985  std::size_t                  first_bucket;
986     
987#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
988    BOOST_WORKAROUND(__MWERKS__,<=0x3003)
989#pragma parse_mfunc_templ reset
990#endif
991};
992
993/*  specialized algorithms */
994
995template<
996  typename KeyFromValue,typename Hash,typename Pred,
997  typename SuperMeta,typename TagList,typename Category
998>
999void swap(
1000  hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
1001  hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y)
1002{
1003  x.swap(y);
1004}
1005
1006} /* namespace multi_index::detail */
1007
1008/* sequenced index specifiers */
1009
1010template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
1011struct hashed_unique
1012{
1013  typedef typename detail::hashed_index_args<
1014    Arg1,Arg2,Arg3,Arg4>                           index_args;
1015  typedef typename index_args::tag_list_type::type tag_list_type;
1016  typedef typename index_args::key_from_value_type key_from_value_type;
1017  typedef typename index_args::hash_type           hash_type;
1018  typedef typename index_args::pred_type           pred_type;
1019
1020  template<typename Super>
1021  struct node_class
1022  {
1023    typedef detail::hashed_index_node<Super> type;
1024  };
1025
1026  template<typename SuperMeta>
1027  struct index_class
1028  {
1029    typedef detail::hashed_index<
1030      key_from_value_type,hash_type,pred_type,
1031      SuperMeta,tag_list_type,detail::hashed_unique_tag> type;
1032  };
1033};
1034
1035template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
1036struct hashed_non_unique
1037{
1038  typedef typename detail::hashed_index_args<
1039    Arg1,Arg2,Arg3,Arg4>                           index_args;
1040  typedef typename index_args::tag_list_type::type tag_list_type;
1041  typedef typename index_args::key_from_value_type key_from_value_type;
1042  typedef typename index_args::hash_type           hash_type;
1043  typedef typename index_args::pred_type           pred_type;
1044
1045  template<typename Super>
1046  struct node_class
1047  {
1048    typedef detail::hashed_index_node<Super> type;
1049  };
1050
1051  template<typename SuperMeta>
1052  struct index_class
1053  {
1054    typedef detail::hashed_index<
1055      key_from_value_type,hash_type,pred_type,
1056      SuperMeta,tag_list_type,detail::hashed_non_unique_tag> type;
1057  };
1058};
1059
1060} /* namespace multi_index */
1061
1062} /* namespace boost */
1063
1064#undef BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT
1065
1066#endif
Note: See TracBrowser for help on using the repository browser.