1 | |
---|
2 | // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. |
---|
3 | // Copyright (C) 2005-2009 Daniel James |
---|
4 | // Distributed under the Boost Software License, Version 1.0. (See accompanying |
---|
5 | // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |
---|
6 | |
---|
7 | #ifndef BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED |
---|
8 | #define BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED |
---|
9 | |
---|
10 | #include <boost/config.hpp> |
---|
11 | #include <boost/assert.hpp> |
---|
12 | #include <boost/unordered/detail/node.hpp> |
---|
13 | #include <boost/unordered/detail/util.hpp> |
---|
14 | |
---|
15 | namespace boost { namespace unordered_detail { |
---|
16 | |
---|
17 | //////////////////////////////////////////////////////////////////////////// |
---|
18 | // Buckets |
---|
19 | |
---|
20 | template <class A, class G> |
---|
21 | inline std::size_t hash_buckets<A, G>::max_bucket_count() const { |
---|
22 | // -1 to account for the sentinel. |
---|
23 | return prev_prime(this->bucket_alloc().max_size() - 1); |
---|
24 | } |
---|
25 | |
---|
26 | template <class A, class G> |
---|
27 | inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::bucket_ptr |
---|
28 | hash_buckets<A, G>::get_bucket(std::size_t num) const |
---|
29 | { |
---|
30 | return buckets_ + static_cast<std::ptrdiff_t>(num); |
---|
31 | } |
---|
32 | |
---|
33 | template <class A, class G> |
---|
34 | inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::bucket_ptr |
---|
35 | hash_buckets<A, G>::bucket_ptr_from_hash(std::size_t hashed) const |
---|
36 | { |
---|
37 | return get_bucket(hashed % bucket_count_); |
---|
38 | } |
---|
39 | |
---|
40 | template <class A, class G> |
---|
41 | std::size_t hash_buckets<A, G>::bucket_size(std::size_t index) const |
---|
42 | { |
---|
43 | if(!buckets_) return 0; |
---|
44 | bucket_ptr ptr = get_bucket(index)->next_; |
---|
45 | std::size_t count = 0; |
---|
46 | while(ptr) { |
---|
47 | ++count; |
---|
48 | ptr = ptr->next_; |
---|
49 | } |
---|
50 | return count; |
---|
51 | } |
---|
52 | |
---|
53 | template <class A, class G> |
---|
54 | inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::node_ptr |
---|
55 | hash_buckets<A, G>::bucket_begin(std::size_t num) const |
---|
56 | { |
---|
57 | return buckets_ ? get_bucket(num)->next_ : node_ptr(); |
---|
58 | } |
---|
59 | |
---|
60 | //////////////////////////////////////////////////////////////////////////// |
---|
61 | // Delete |
---|
62 | |
---|
63 | template <class A, class G> |
---|
64 | inline void hash_buckets<A, G>::delete_node(node_ptr b) |
---|
65 | { |
---|
66 | node* raw_ptr = static_cast<node*>(&*b); |
---|
67 | boost::unordered_detail::destroy(&raw_ptr->value()); |
---|
68 | real_node_ptr n(node_alloc().address(*raw_ptr)); |
---|
69 | node_alloc().destroy(n); |
---|
70 | node_alloc().deallocate(n, 1); |
---|
71 | } |
---|
72 | |
---|
73 | template <class A, class G> |
---|
74 | inline void hash_buckets<A, G>::clear_bucket(bucket_ptr b) |
---|
75 | { |
---|
76 | node_ptr node_it = b->next_; |
---|
77 | b->next_ = node_ptr(); |
---|
78 | |
---|
79 | while(node_it) { |
---|
80 | node_ptr node_to_delete = node_it; |
---|
81 | node_it = node_it->next_; |
---|
82 | delete_node(node_to_delete); |
---|
83 | } |
---|
84 | } |
---|
85 | |
---|
86 | template <class A, class G> |
---|
87 | inline void hash_buckets<A, G>::delete_buckets() |
---|
88 | { |
---|
89 | bucket_ptr end = this->get_bucket(this->bucket_count_); |
---|
90 | |
---|
91 | for(bucket_ptr begin = this->buckets_; begin != end; ++begin) { |
---|
92 | clear_bucket(begin); |
---|
93 | } |
---|
94 | |
---|
95 | // Destroy the buckets (including the sentinel bucket). |
---|
96 | ++end; |
---|
97 | for(bucket_ptr begin = this->buckets_; begin != end; ++begin) { |
---|
98 | bucket_alloc().destroy(begin); |
---|
99 | } |
---|
100 | |
---|
101 | bucket_alloc().deallocate(this->buckets_, this->bucket_count_ + 1); |
---|
102 | |
---|
103 | this->buckets_ = bucket_ptr(); |
---|
104 | } |
---|
105 | |
---|
106 | template <class A, class G> |
---|
107 | inline std::size_t hash_buckets<A, G>::delete_nodes( |
---|
108 | node_ptr begin, node_ptr end) |
---|
109 | { |
---|
110 | std::size_t count = 0; |
---|
111 | while(begin != end) { |
---|
112 | node_ptr n = begin; |
---|
113 | begin = begin->next_; |
---|
114 | delete_node(n); |
---|
115 | ++count; |
---|
116 | } |
---|
117 | return count; |
---|
118 | } |
---|
119 | |
---|
120 | //////////////////////////////////////////////////////////////////////////// |
---|
121 | // Constructors and Destructors |
---|
122 | |
---|
123 | template <class A, class G> |
---|
124 | inline hash_buckets<A, G>::hash_buckets( |
---|
125 | node_allocator const& a, std::size_t bucket_count) |
---|
126 | : buckets_(), |
---|
127 | bucket_count_(bucket_count), |
---|
128 | allocators_(a,a) |
---|
129 | { |
---|
130 | } |
---|
131 | |
---|
132 | template <class A, class G> |
---|
133 | inline hash_buckets<A, G>::~hash_buckets() |
---|
134 | { |
---|
135 | if(this->buckets_) { this->delete_buckets(); } |
---|
136 | } |
---|
137 | |
---|
138 | template <class A, class G> |
---|
139 | inline void hash_buckets<A, G>::create_buckets() |
---|
140 | { |
---|
141 | // The array constructor will clean up in the event of an |
---|
142 | // exception. |
---|
143 | allocator_array_constructor<bucket_allocator> |
---|
144 | constructor(bucket_alloc()); |
---|
145 | |
---|
146 | // Creates an extra bucket to act as a sentinel. |
---|
147 | constructor.construct(bucket(), this->bucket_count_ + 1); |
---|
148 | |
---|
149 | // Set up the sentinel (node_ptr cast) |
---|
150 | bucket_ptr sentinel = constructor.get() + |
---|
151 | static_cast<std::ptrdiff_t>(this->bucket_count_); |
---|
152 | sentinel->next_ = sentinel; |
---|
153 | |
---|
154 | // Only release the buckets once everything is successfully |
---|
155 | // done. |
---|
156 | this->buckets_ = constructor.release(); |
---|
157 | } |
---|
158 | |
---|
159 | //////////////////////////////////////////////////////////////////////////// |
---|
160 | // Constructors and Destructors |
---|
161 | |
---|
162 | // no throw |
---|
163 | template <class A, class G> |
---|
164 | inline void hash_buckets<A, G>::move(hash_buckets& other) |
---|
165 | { |
---|
166 | BOOST_ASSERT(node_alloc() == other.node_alloc()); |
---|
167 | if(this->buckets_) { this->delete_buckets(); } |
---|
168 | this->buckets_ = other.buckets_; |
---|
169 | this->bucket_count_ = other.bucket_count_; |
---|
170 | other.buckets_ = bucket_ptr(); |
---|
171 | other.bucket_count_ = 0; |
---|
172 | } |
---|
173 | |
---|
174 | template <class A, class G> |
---|
175 | inline void hash_buckets<A, G>::swap(hash_buckets<A, G>& other) |
---|
176 | { |
---|
177 | BOOST_ASSERT(node_alloc() == other.node_alloc()); |
---|
178 | std::swap(buckets_, other.buckets_); |
---|
179 | std::swap(bucket_count_, other.bucket_count_); |
---|
180 | } |
---|
181 | }} |
---|
182 | |
---|
183 | #endif |
---|