Context Navigation

source: vendor/nemo/current/NEMOGCM/EXTERNAL/XIOS/extern/boost/include/boost/unordered/detail/unique.hpp @ 44

Last change on this file since 44 was 44, checked in by cholod, 12 years ago
Load NEMO_TMP into vendor/nemo/current.
File size: 20.1 KB

Line
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_UNIQUE_HPP_INCLUDED
8	#define BOOST_UNORDERED_DETAIL_UNIQUE_HPP_INCLUDED
9
10	#include <boost/unordered/detail/table.hpp>
11	#include <boost/unordered/detail/extract_key.hpp>
12
13	namespace boost { namespace unordered_detail {
14
15	template <class T>
16	class hash_unique_table : public T::table
17	{
18	public:
19	typedef BOOST_DEDUCED_TYPENAME T::hasher hasher;
20	typedef BOOST_DEDUCED_TYPENAME T::key_equal key_equal;
21	typedef BOOST_DEDUCED_TYPENAME T::value_allocator value_allocator;
22	typedef BOOST_DEDUCED_TYPENAME T::key_type key_type;
23	typedef BOOST_DEDUCED_TYPENAME T::value_type value_type;
24	typedef BOOST_DEDUCED_TYPENAME T::table table;
25	typedef BOOST_DEDUCED_TYPENAME T::node_constructor node_constructor;
26
27	typedef BOOST_DEDUCED_TYPENAME T::node node;
28	typedef BOOST_DEDUCED_TYPENAME T::node_ptr node_ptr;
29	typedef BOOST_DEDUCED_TYPENAME T::bucket_ptr bucket_ptr;
30	typedef BOOST_DEDUCED_TYPENAME T::iterator_base iterator_base;
31	typedef BOOST_DEDUCED_TYPENAME T::extractor extractor;
32
33	typedef std::pair<iterator_base, bool> emplace_return;
34
35	// Constructors
36
37	hash_unique_table(std::size_t n, hasher const& hf, key_equal const& eq,
38	value_allocator const& a)
39	: table(n, hf, eq, a) {}
40	hash_unique_table(hash_unique_table const& x)
41	: table(x, x.node_alloc()) {}
42	hash_unique_table(hash_unique_table const& x, value_allocator const& a)
43	: table(x, a) {}
44	hash_unique_table(hash_unique_table& x, move_tag m)
45	: table(x, m) {}
46	hash_unique_table(hash_unique_table& x, value_allocator const& a,
47	move_tag m)
48	: table(x, a, m) {}
49	~hash_unique_table() {}
50
51	// Insert methods
52
53	emplace_return emplace_impl_with_node(node_constructor& a);
54	value_type& operator[](key_type const& k);
55
56	// equals
57
58	bool equals(hash_unique_table const&) const;
59
60	node_ptr add_node(node_constructor& a, bucket_ptr bucket);
61
62	#if defined(BOOST_UNORDERED_STD_FORWARD)
63
64	template<class... Args>
65	emplace_return emplace(Args&&... args);
66	template<class... Args>
67	emplace_return emplace_impl(key_type const& k, Args&&... args);
68	template<class... Args>
69	emplace_return emplace_impl(no_key, Args&&... args);
70	template<class... Args>
71	emplace_return emplace_empty_impl(Args&&... args);
72	#else
73
74	#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \
75	template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
76	emplace_return emplace( \
77	BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); \
78	template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
79	emplace_return emplace_impl(key_type const& k, \
80	BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); \
81	template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
82	emplace_return emplace_impl(no_key, \
83	BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); \
84	template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
85	emplace_return emplace_empty_impl( \
86	BOOST_UNORDERED_FUNCTION_PARAMS(z, n));
87
88	BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
89	BOOST_UNORDERED_INSERT_IMPL, _)
90
91	#undef BOOST_UNORDERED_INSERT_IMPL
92
93	#endif
94
95	// if hash function throws, or inserting > 1 element, basic exception
96	// safety strong otherwise
97	template <class InputIt>
98	void insert_range(InputIt i, InputIt j);
99	template <class InputIt>
100	void insert_range_impl(key_type const&, InputIt i, InputIt j);
101	template <class InputIt>
102	void insert_range_impl(no_key, InputIt i, InputIt j);
103	};
104
105	template <class H, class P, class A>
106	struct set : public types<
107	BOOST_DEDUCED_TYPENAME A::value_type,
108	BOOST_DEDUCED_TYPENAME A::value_type,
109	H, P, A,
110	set_extractor<BOOST_DEDUCED_TYPENAME A::value_type>,
111	ungrouped>
112	{
113	typedef hash_unique_table<set<H, P, A> > impl;
114	typedef hash_table<set<H, P, A> > table;
115	};
116
117	template <class K, class H, class P, class A>
118	struct map : public types<
119	K, BOOST_DEDUCED_TYPENAME A::value_type,
120	H, P, A,
121	map_extractor<K, BOOST_DEDUCED_TYPENAME A::value_type>,
122	ungrouped>
123	{
124	typedef hash_unique_table<map<K, H, P, A> > impl;
125	typedef hash_table<map<K, H, P, A> > table;
126	};
127
128	////////////////////////////////////////////////////////////////////////////
129	// Equality
130
131	template <class T>
132	bool hash_unique_table<T>
133	::equals(hash_unique_table<T> const& other) const
134	{
135	if(this->size_ != other.size_) return false;
136	if(!this->size_) return true;
137
138	bucket_ptr end = this->get_bucket(this->bucket_count_);
139	for(bucket_ptr i = this->cached_begin_bucket_; i != end; ++i)
140	{
141	node_ptr it1 = i->next_;
142	while(BOOST_UNORDERED_BORLAND_BOOL(it1))
143	{
144	node_ptr it2 = other.find_iterator(this->get_key_from_ptr(it1));
145	if(!BOOST_UNORDERED_BORLAND_BOOL(it2)) return false;
146	if(!extractor::compare_mapped(
147	node::get_value(it1), node::get_value(it2)))
148	return false;
149	it1 = it1->next_;
150	}
151	}
152
153	return true;
154	}
155
156	////////////////////////////////////////////////////////////////////////////
157	// A convenience method for adding nodes.
158
159	template <class T>
160	inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::node_ptr
161	hash_unique_table<T>::add_node(node_constructor& a,
162	bucket_ptr bucket)
163	{
164	node_ptr n = a.release();
165	node::add_to_bucket(n, *bucket);
166	++this->size_;
167	if(bucket < this->cached_begin_bucket_)
168	this->cached_begin_bucket_ = bucket;
169	return n;
170	}
171
172	////////////////////////////////////////////////////////////////////////////
173	// Insert methods
174
175	// if hash function throws, basic exception safety
176	// strong otherwise
177	template <class T>
178	BOOST_DEDUCED_TYPENAME hash_unique_table<T>::value_type&
179	hash_unique_table<T>::operator[](key_type const& k)
180	{
181	typedef BOOST_DEDUCED_TYPENAME value_type::second_type mapped_type;
182
183	std::size_t hash_value = this->hash_function()(k);
184	bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
185
186	if(!this->buckets_) {
187	node_constructor a(*this);
188	a.construct_pair(k, (mapped_type*) 0);
189	return *this->emplace_empty_impl_with_node(a, 1);
190	}
191
192	node_ptr pos = this->find_iterator(bucket, k);
193
194	if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
195	return node::get_value(pos);
196	}
197	else {
198	// Side effects only in this block.
199
200	// Create the node before rehashing in case it throws an
201	// exception (need strong safety in such a case).
202	node_constructor a(*this);
203	a.construct_pair(k, (mapped_type*) 0);
204
205	// reserve has basic exception safety if the hash function
206	// throws, strong otherwise.
207	if(this->reserve_for_insert(this->size_ + 1))
208	bucket = this->bucket_ptr_from_hash(hash_value);
209
210	// Nothing after this point can throw.
211
212	return node::get_value(add_node(a, bucket));
213	}
214	}
215
216	template <class T>
217	inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return
218	hash_unique_table<T>::emplace_impl_with_node(node_constructor& a)
219	{
220	// No side effects in this initial code
221	key_type const& k = this->get_key(a.value());
222	std::size_t hash_value = this->hash_function()(k);
223	bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
224	node_ptr pos = this->find_iterator(bucket, k);
225
226	if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
227	// Found an existing key, return it (no throw).
228	return emplace_return(iterator_base(bucket, pos), false);
229	} else {
230	// reserve has basic exception safety if the hash function
231	// throws, strong otherwise.
232	if(this->reserve_for_insert(this->size_ + 1))
233	bucket = this->bucket_ptr_from_hash(hash_value);
234
235	// Nothing after this point can throw.
236
237	return emplace_return(
238	iterator_base(bucket, add_node(a, bucket)),
239	true);
240	}
241	}
242
243	#if defined(BOOST_UNORDERED_STD_FORWARD)
244
245	template <class T>
246	template<class... Args>
247	inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return
248	hash_unique_table<T>::emplace_impl(key_type const& k,
249	Args&&... args)
250	{
251	// No side effects in this initial code
252	std::size_t hash_value = this->hash_function()(k);
253	bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
254	node_ptr pos = this->find_iterator(bucket, k);
255
256	if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
257	// Found an existing key, return it (no throw).
258	return emplace_return(iterator_base(bucket, pos), false);
259
260	} else {
261	// Doesn't already exist, add to bucket.
262	// Side effects only in this block.
263
264	// Create the node before rehashing in case it throws an
265	// exception (need strong safety in such a case).
266	node_constructor a(*this);
267	a.construct(std::forward<Args>(args)...);
268
269	// reserve has basic exception safety if the hash function
270	// throws, strong otherwise.
271	if(this->reserve_for_insert(this->size_ + 1))
272	bucket = this->bucket_ptr_from_hash(hash_value);
273
274	// Nothing after this point can throw.
275
276	return emplace_return(
277	iterator_base(bucket, add_node(a, bucket)),
278	true);
279	}
280	}
281
282	template <class T>
283	template<class... Args>
284	inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return
285	hash_unique_table<T>::emplace_impl(no_key, Args&&... args)
286	{
287	// Construct the node regardless - in order to get the key.
288	// It will be discarded if it isn't used
289	node_constructor a(*this);
290	a.construct(std::forward<Args>(args)...);
291	return emplace_impl_with_node(a);
292	}
293
294	template <class T>
295	template<class... Args>
296	inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return
297	hash_unique_table<T>::emplace_empty_impl(Args&&... args)
298	{
299	node_constructor a(*this);
300	a.construct(std::forward<Args>(args)...);
301	return emplace_return(this->emplace_empty_impl_with_node(a, 1), true);
302	}
303
304	#else
305
306	#define BOOST_UNORDERED_INSERT_IMPL(z, num_params, _) \
307	template <class T> \
308	template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
309	inline BOOST_DEDUCED_TYPENAME \
310	hash_unique_table<T>::emplace_return \
311	hash_unique_table<T>::emplace_impl( \
312	key_type const& k, \
313	BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
314	{ \
315	std::size_t hash_value = this->hash_function()(k); \
316	bucket_ptr bucket \
317	= this->bucket_ptr_from_hash(hash_value); \
318	node_ptr pos = this->find_iterator(bucket, k); \
319	\
320	if (BOOST_UNORDERED_BORLAND_BOOL(pos)) { \
321	return emplace_return(iterator_base(bucket, pos), false); \
322	} else { \
323	node_constructor a(*this); \
324	a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
325	\
326	if(this->reserve_for_insert(this->size_ + 1)) \
327	bucket = this->bucket_ptr_from_hash(hash_value); \
328	\
329	return emplace_return(iterator_base(bucket, \
330	add_node(a, bucket)), true); \
331	} \
332	} \
333	\
334	template <class T> \
335	template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
336	inline BOOST_DEDUCED_TYPENAME \
337	hash_unique_table<T>::emplace_return \
338	hash_unique_table<T>:: \
339	emplace_impl(no_key, \
340	BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
341	{ \
342	node_constructor a(*this); \
343	a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
344	return emplace_impl_with_node(a); \
345	} \
346	\
347	template <class T> \
348	template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
349	inline BOOST_DEDUCED_TYPENAME \
350	hash_unique_table<T>::emplace_return \
351	hash_unique_table<T>:: \
352	emplace_empty_impl( \
353	BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
354	{ \
355	node_constructor a(*this); \
356	a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
357	return emplace_return(this->emplace_empty_impl_with_node(a, 1), true); \
358	}
359
360	BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
361	BOOST_UNORDERED_INSERT_IMPL, _)
362
363	#undef BOOST_UNORDERED_INSERT_IMPL
364
365	#endif
366
367	#if defined(BOOST_UNORDERED_STD_FORWARD)
368
369	// Emplace (unique keys)
370	// (I'm using an overloaded emplace for both 'insert' and 'emplace')
371
372	// if hash function throws, basic exception safety
373	// strong otherwise
374
375	template <class T>
376	template<class... Args>
377	BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return
378	hash_unique_table<T>::emplace(Args&&... args)
379	{
380	return this->size_ ?
381	emplace_impl(
382	extractor::extract(std::forward<Args>(args)...),
383	std::forward<Args>(args)...) :
384	emplace_empty_impl(std::forward<Args>(args)...);
385	}
386
387	#else
388
389	template <class T>
390	template <class Arg0>
391	BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return
392	hash_unique_table<T>::emplace(Arg0 const& arg0)
393	{
394	return this->size_ ?
395	emplace_impl(extractor::extract(arg0), arg0) :
396	emplace_empty_impl(arg0);
397	}
398
399	#define BOOST_UNORDERED_INSERT_IMPL(z, num_params, _) \
400	template <class T> \
401	template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
402	BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return \
403	hash_unique_table<T>::emplace( \
404	BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
405	{ \
406	return this->size_ ? \
407	emplace_impl(extractor::extract(arg0, arg1), \
408	BOOST_UNORDERED_CALL_PARAMS(z, num_params)) : \
409	emplace_empty_impl( \
410	BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
411	}
412
413	BOOST_PP_REPEAT_FROM_TO(2, BOOST_UNORDERED_EMPLACE_LIMIT,
414	BOOST_UNORDERED_INSERT_IMPL, _)
415
416	#undef BOOST_UNORDERED_INSERT_IMPL
417
418	#endif
419
420	////////////////////////////////////////////////////////////////////////////
421	// Insert range methods
422
423	template <class T>
424	template <class InputIt>
425	inline void hash_unique_table<T>::insert_range_impl(
426	key_type const&, InputIt i, InputIt j)
427	{
428	node_constructor a(*this);
429
430	if(!this->size_) {
431	a.construct(*i);
432	this->emplace_empty_impl_with_node(a, 1);
433	++i;
434	if(i == j) return;
435	}
436
437	do {
438	// No side effects in this initial code
439	// Note: can't use get_key as '*i' might not be value_type - it
440	// could be a pair with first_types as key_type without const or a
441	// different second_type.
442	key_type const& k = extractor::extract(*i);
443	std::size_t hash_value = this->hash_function()(k);
444	bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
445	node_ptr pos = this->find_iterator(bucket, k);
446
447	if (!BOOST_UNORDERED_BORLAND_BOOL(pos)) {
448	// Doesn't already exist, add to bucket.
449	// Side effects only in this block.
450
451	// Create the node before rehashing in case it throws an
452	// exception (need strong safety in such a case).
453	a.construct(*i);
454
455	// reserve has basic exception safety if the hash function
456	// throws, strong otherwise.
457	if(this->size_ + 1 >= this->max_load_) {
458	this->reserve_for_insert(this->size_ + insert_size(i, j));
459	bucket = this->bucket_ptr_from_hash(hash_value);
460	}
461
462	// Nothing after this point can throw.
463	add_node(a, bucket);
464	}
465	} while(++i != j);
466	}
467
468	template <class T>
469	template <class InputIt>
470	inline void hash_unique_table<T>::insert_range_impl(
471	no_key, InputIt i, InputIt j)
472	{
473	node_constructor a(*this);
474
475	if(!this->size_) {
476	a.construct(*i);
477	this->emplace_empty_impl_with_node(a, 1);
478	++i;
479	if(i == j) return;
480	}
481
482	do {
483	// No side effects in this initial code
484	a.construct(*i);
485	emplace_impl_with_node(a);
486	} while(++i != j);
487	}
488
489	// if hash function throws, or inserting > 1 element, basic exception safety
490	// strong otherwise
491	template <class T>
492	template <class InputIt>
493	void hash_unique_table<T>::insert_range(InputIt i, InputIt j)
494	{
495	if(i != j)
496	return insert_range_impl(extractor::extract(*i), i, j);
497	}
498	}}
499
500	#endif

Note: See TracBrowser for help on using the repository browser.

Download in other formats: