Changeset 44697
 Timestamp:
 Apr 21, 2008, 3:55:40 PM (10 years ago)
 Location:
 trunk/boost/unordered/detail
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

trunk/boost/unordered/detail/hash_table.hpp
r44614 r44697 51 51 static const std::size_t default_initial_bucket_count = 50; 52 52 static const float minimum_max_load_factor = 1e3f; 53 inline std::size_t next_prime(std::size_t n);54 53 55 54 template <class T> … … 102 101 return *bound; 103 102 } 103 104 // Controls how many buckets are allocated and which buckets hash 105 // values map to. Does not contain the buckets themselves, or ever 106 // deal with them directly. 107 108 struct bucket_manager { 109 std::size_t bucket_count_; 110 111 bucket_manager() 112 : bucket_count_(0) {} 113 114 explicit bucket_manager(std::size_t n) 115 : bucket_count_(next_prime(n)) {} 116 117 std::size_t bucket_count() const { 118 return bucket_count_; 119 } 120 121 std::size_t bucket_from_hash(std::size_t hashed) const { 122 return hashed % bucket_count_; 123 } 124 125 std::size_t max_bucket_count(std::size_t max_size) const { 126 return prev_prime(max_size); 127 } 128 }; 104 129 105 130 // pair_cast  used to convert between pair types. 
trunk/boost/unordered/detail/hash_table_impl.hpp
r44614 r44697 313 313 allocators allocators_; 314 314 bucket_ptr buckets_; 315 size_type bucket_count_;315 bucket_manager bucket_manager_; 316 316 bucket_ptr cached_begin_bucket_; 317 size_type size_; 317 size_type size_; 318 318 319 319 // Constructors/Deconstructor … … 321 321 BOOST_UNORDERED_TABLE_DATA(size_type n, value_allocator const& a) 322 322 : allocators_(a), 323 buckets_(), bucket_ count_(next_prime(n)),323 buckets_(), bucket_manager_(n), 324 324 cached_begin_bucket_(), size_(0) 325 325 { … … 330 330 BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA const& x, size_type n) 331 331 : allocators_(x.allocators_), 332 buckets_(), bucket_ count_(next_prime(n)),332 buckets_(), bucket_manager_(n), 333 333 cached_begin_bucket_(), size_(0) 334 334 { … … 339 339 BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA& x, move_tag) 340 340 : allocators_(x.allocators_), 341 buckets_(x.buckets_), bucket_ count_(x.bucket_count_),341 buckets_(x.buckets_), bucket_manager_(x.bucket_manager_), 342 342 cached_begin_bucket_(x.cached_begin_bucket_), size_(x.size_) 343 343 { … … 347 347 BOOST_UNORDERED_TABLE_DATA(BOOST_UNORDERED_TABLE_DATA& x, 348 348 value_allocator const& a, size_type n, move_tag) 349 : allocators_(a), buckets_(), bucket_ count_(),349 : allocators_(a), buckets_(), bucket_manager_(), 350 350 cached_begin_bucket_(), size_(0) 351 351 { 352 352 if(allocators_ == x.allocators_) { 353 353 buckets_ = x.buckets_; 354 bucket_ count_ = x.bucket_count_;354 bucket_manager_ = x.bucket_manager_; 355 355 cached_begin_bucket_ = x.cached_begin_bucket_; 356 356 size_ = x.size_; … … 359 359 else { 360 360 BOOST_UNORDERED_MSVC_RESET_PTR(buckets_); 361 bucket_ count_ = next_prime(n);361 bucket_manager_ = bucket_manager(n); 362 362 create_buckets(); 363 363 } … … 371 371 372 372 void create_buckets() { 373 size_type bucket_count = bucket_manager_.bucket_count(); 374 373 375 // The array constructor will clean up in the event of an 374 376 // exception. … … 377 379 378 380 // Creates an extra bucket to act as a sentinel. 379 constructor.construct(bucket(), bucket_count _+ 1);380 381 cached_begin_bucket_ = constructor.get() + static_cast<difference_type>(bucket_count _);381 constructor.construct(bucket(), bucket_count + 1); 382 383 cached_begin_bucket_ = constructor.get() + static_cast<difference_type>(bucket_count); 382 384 383 385 // Set up the sentinel. … … 405 407 allocators_.bucket_alloc_.destroy(begin); 406 408 407 allocators_.bucket_alloc_.deallocate(buckets_, bucket_count_ + 1); 409 allocators_.bucket_alloc_.deallocate(buckets_, 410 bucket_manager_.bucket_count() + 1); 408 411 } 409 412 } … … 420 423 { 421 424 std::swap(buckets_, other.buckets_); 422 std::swap(bucket_ count_, other.bucket_count_);425 std::swap(bucket_manager_, other.bucket_manager_); 423 426 std::swap(cached_begin_bucket_, other.cached_begin_bucket_); 424 427 std::swap(size_, other.size_); … … 431 434 buckets_ = other.buckets_; 432 435 unordered_detail::reset(other.buckets_); 433 bucket_ count_ = other.bucket_count_;436 bucket_manager_ = other.bucket_manager_; 434 437 cached_begin_bucket_ = other.cached_begin_bucket_; 435 438 size_ = other.size_; 436 439 } 437 440 441 // Return the bucket number for a hashed value. 442 // 443 // no throw 444 size_type bucket_from_hash(size_type hashed) const 445 { 446 return bucket_manager_.bucket_from_hash(hashed); 447 } 448 438 449 // Return the bucket for a hashed value. 439 450 // 440 451 // no throw 441 bucket_ptr bucket_from_hash(size_type hashed) const 442 { 443 return buckets_ + static_cast<difference_type>(hashed % bucket_count_); 452 bucket_ptr bucket_ptr_from_hash(size_type hashed) const 453 { 454 return buckets_ + static_cast<difference_type>( 455 bucket_manager_.bucket_from_hash(hashed)); 444 456 } 445 457 … … 450 462 bucket_ptr buckets_end() const 451 463 { 452 return buckets_ + static_cast<difference_type>(bucket_ count_);464 return buckets_ + static_cast<difference_type>(bucket_manager_.bucket_count()); 453 465 } 454 466 … … 1283 1295 { 1284 1296 // hash_function can throw: 1285 return hash_function()(k) % data_.bucket_count_;1297 return data_.bucket_from_hash(hash_function()(k)); 1286 1298 } 1287 1299 … … 1296 1308 size_type bucket_count() const 1297 1309 { 1298 return data_.bucket_ count_;1310 return data_.bucket_manager_.bucket_count(); 1299 1311 } 1300 1312 … … 1332 1344 // Only resize when size >= mlf_ * count 1333 1345 max_load_ = double_to_size_t(ceil( 1334 (double) mlf_ * data_.bucket_ count_));1346 (double) mlf_ * data_.bucket_manager_.bucket_count())); 1335 1347 } 1336 1348 … … 1384 1396 float load_factor() const 1385 1397 { 1386 BOOST_ASSERT(data_.bucket_ count_!= 0);1398 BOOST_ASSERT(data_.bucket_manager_.bucket_count() != 0); 1387 1399 return static_cast<float>(data_.size_) 1388 / static_cast<float>(data_.bucket_ count_);1400 / static_cast<float>(data_.bucket_manager_.bucket_count()); 1389 1401 } 1390 1402 … … 1466 1478 1467 1479 // This next line throws iff the hash function throws. 1468 bucket_ptr dst_bucket = dst.bucket_ from_hash(1480 bucket_ptr dst_bucket = dst.bucket_ptr_from_hash( 1469 1481 hf(extract_key(data::get_value(src_bucket>next_)))); 1470 1482 … … 1492 1504 BOOST_UNORDERED_BORLAND_BOOL(it); it = data::next_group(it)) { 1493 1505 // hash function can throw. 1494 bucket_ptr dst_bucket = dst.bucket_ from_hash(1506 bucket_ptr dst_bucket = dst.bucket_ptr_from_hash( 1495 1507 hf(extract_key(data::get_value(it)))); 1496 1508 // throws, strong … … 1517 1529 key_type const& k = extract_key(v); 1518 1530 size_type hash_value = hash_function()(k); 1519 bucket_ptr bucket = data_.bucket_ from_hash(hash_value);1531 bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value); 1520 1532 link_ptr position = find_iterator(bucket, k); 1521 1533 … … 1528 1540 // throws, strong otherwise. 1529 1541 if(reserve(size() + 1)) 1530 bucket = data_.bucket_ from_hash(hash_value);1542 bucket = data_.bucket_ptr_from_hash(hash_value); 1531 1543 1532 1544 // I'm relying on link_ptr not being invalidated by … … 1641 1653 1642 1654 size_type hash_value = hash_function()(k); 1643 bucket_ptr bucket = data_.bucket_ from_hash(hash_value);1655 bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value); 1644 1656 link_ptr pos = find_iterator(bucket, k); 1645 1657 … … 1658 1670 // throws, strong otherwise. 1659 1671 if(reserve(size() + 1)) 1660 bucket = data_.bucket_ from_hash(hash_value);1672 bucket = data_.bucket_ptr_from_hash(hash_value); 1661 1673 1662 1674 // Nothing after this point can throw. … … 1675 1687 key_type const& k = extract_key(v); 1676 1688 size_type hash_value = hash_function()(k); 1677 bucket_ptr bucket = data_.bucket_ from_hash(hash_value);1689 bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value); 1678 1690 link_ptr pos = find_iterator(bucket, k); 1679 1691 … … 1695 1707 // throws, strong otherwise. 1696 1708 if(reserve(size() + 1)) 1697 bucket = data_.bucket_ from_hash(hash_value);1709 bucket = data_.bucket_ptr_from_hash(hash_value); 1698 1710 1699 1711 // Nothing after this point can throw. … … 1750 1762 // No side effects in this initial code 1751 1763 size_type hash_value = hash_function()(extract_key(*i)); 1752 bucket_ptr bucket = data_.bucket_ from_hash(hash_value);1764 bucket_ptr bucket = data_.bucket_ptr_from_hash(hash_value); 1753 1765 link_ptr pos = find_iterator(bucket, extract_key(*i)); 1754 1766 … … 1765 1777 if(size() + 1 >= max_load_) { 1766 1778 reserve(size() + insert_size(i, j)); 1767 bucket = data_.bucket_ from_hash(hash_value);1779 bucket = data_.bucket_ptr_from_hash(hash_value); 1768 1780 } 1769 1781 … … 2043 2055 #undef BOOST_UNORDERED_LOCAL_ITERATOR 2044 2056 #undef BOOST_UNORDERED_CONST_LOCAL_ITERATOR 2045
Note: See TracChangeset
for help on using the changeset viewer.