[svn] commit: r3471 - in /branches/trac408/src/lib/nsas: hash_table.h tests/hash_table_unittest.cc
BIND 10 source code commits
bind10-changes at lists.isc.org
Fri Nov 5 18:12:48 UTC 2010
Author: vorner
Date: Fri Nov 5 18:12:46 2010
New Revision: 3471
Log:
Add atomic getOrAdd to hash table
Modified:
branches/trac408/src/lib/nsas/hash_table.h
branches/trac408/src/lib/nsas/tests/hash_table_unittest.cc
Modified: branches/trac408/src/lib/nsas/hash_table.h
==============================================================================
--- branches/trac408/src/lib/nsas/hash_table.h (original)
+++ branches/trac408/src/lib/nsas/hash_table.h Fri Nov 5 18:12:46 2010
@@ -151,8 +151,12 @@
/// \param key Name of the object (and class). The hash of this is
/// calculated and used to index the table.
///
- /// \return Shared pointer to the object.
- virtual boost::shared_ptr<T> get(const HashKey& key);
+ /// \return Shared pointer to the object or NULL if it is not there.
+ virtual boost::shared_ptr<T> get(const HashKey& key) {
+ uint32_t index = hash_(key);
+ scoped_lock lock(table_[index].mutex_);
+ return getInternal(key, index);
+ }
/// \brief Remove Entry
///
@@ -181,7 +185,40 @@
// the addition fails and a status is returned.
/// \return true if the object was successfully added, false otherwise.
virtual bool add(boost::shared_ptr<T>& object, const HashKey& key,
- bool replace = false);
+ bool replace = false)
+ {
+ uint32_t index = hash_(key);
+ scoped_lock lock(table_[index].mutex_);
+ return addInternal(object, key, index, replace);
+ }
+
+ /// \brief Attomicly lookup an entry or add a new one if it does not exist.
+ ///
+ /// Looks up an entry specified by key in the table. If it is not there,
+ /// it calls generator() and adds its result to the table under given key.
+ /// It is performed attomically to prevent race conditions.
+ ///
+ /// \param key The entry to lookup.
+ /// \param generator will be called when the item is not there. Its result
+ /// will be added and returned.
+ /// \return The boolean part of pair tells if the value was added (true
+ /// means new value, false looked up one). The other part is the
+ /// object, either found or created.
+ template<class Generator>
+ std::pair<bool, boost::shared_ptr<T> > getOrAdd(const HashKey& key,
+ const Generator& generator)
+ {
+ uint32_t index = hash_(key);
+ scoped_lock lock(table_[index].mutex_);
+ boost::shared_ptr<T> result(getInternal(key, index));
+ if (result) {
+ return (std::pair<bool, boost::shared_ptr<T> >(true, result));
+ } else {
+ result = generator();
+ addInternal(result, key, index);
+ return (std::pair<bool, boost::shared_ptr<T> >(false, result));
+ }
+ }
/// \brief Returns Size of Hash Table
///
@@ -189,6 +226,13 @@
virtual uint32_t tableSize() const {
return table_.size();
}
+
+protected:
+ // Internal parts, expect to be already locked
+ virtual boost::shared_ptr<T> getInternal(const HashKey& key,
+ uint32_t index);
+ virtual bool addInternal(boost::shared_ptr<T>& object, const HashKey& key,
+ uint32_t index, bool replace = false);
private:
Hash hash_; ///< Hashing function
@@ -205,15 +249,9 @@
// Lookup an object in the table
template <typename T>
-boost::shared_ptr<T> HashTable<T>::get(const HashKey& key) {
-
- // Calculate the hash value
- uint32_t index = hash_(key);
-
- // Take out a read lock on this hash slot. The lock is released when this
- // object goes out of scope.
- sharable_lock lock(table_[index].mutex_);
-
+boost::shared_ptr<T> HashTable<T>::getInternal(const HashKey& key,
+ uint32_t index)
+{
// Locate the object.
typename HashTableSlot<T>::iterator i;
for (i = table_[index].list_.begin(); i != table_[index].list_.end(); ++i) {
@@ -258,17 +296,10 @@
// Add an entry to the hash table
template <typename T>
-bool HashTable<T>::add(boost::shared_ptr<T>& object, const HashKey& key,
- bool replace)
+bool HashTable<T>::addInternal(boost::shared_ptr<T>& object,
+ const HashKey& key, uint32_t index, bool replace)
{
-
- // Calculate the hash value
- uint32_t index = hash_(key);
-
- // Access to the elements of this hash slot are accessed under a mutex.
- scoped_lock lock(table_[index].mutex_);
-
- // Now search this list to see if the element already exists.
+ // Search this list to see if the element already exists.
typename HashTableSlot<T>::iterator i;
for (i = table_[index].list_.begin(); i != table_[index].list_.end(); ++i) {
if ((*compare_)(i->get(), key)) {
Modified: branches/trac408/src/lib/nsas/tests/hash_table_unittest.cc
==============================================================================
--- branches/trac408/src/lib/nsas/tests/hash_table_unittest.cc (original)
+++ branches/trac408/src/lib/nsas/tests/hash_table_unittest.cc Fri Nov 5 18:12:46 2010
@@ -16,6 +16,7 @@
#include <gtest/gtest.h>
#include <boost/shared_ptr.hpp>
+#include <boost/bind.hpp>
#include <string.h>
#include <iostream>
@@ -27,6 +28,7 @@
#include "nsas_test.h"
using namespace std;
+using boost::shared_ptr;
namespace isc {
namespace nsas {
@@ -175,6 +177,30 @@
EXPECT_TRUE(value.get() == NULL);
}
+shared_ptr<TestEntry>
+pass(shared_ptr<TestEntry> value) {
+ return (value);
+}
+
+TEST_F(HashTableTest, GetOrAddTest) {
+ // Add one entry
+ EXPECT_TRUE(table_.add(dummy1_, dummy1_->hashKey()));
+
+ // Check it looks it up
+ std::pair<bool, shared_ptr<TestEntry> > result = table_.getOrAdd(
+ dummy1_->hashKey(), boost::bind(pass, dummy3_));
+ EXPECT_TRUE(result.first);
+ EXPECT_EQ(dummy1_.get(), result.second.get());
+
+ // Check it says it adds the value
+ result = table_.getOrAdd(dummy3_->hashKey(), boost::bind(pass, dummy3_));
+ EXPECT_FALSE(result.first);
+ EXPECT_EQ(dummy3_.get(), result.second.get());
+
+ // Check it really did add it
+ EXPECT_EQ(dummy3_.get(), table_.get(dummy3_->hashKey()).get());
+}
+
// Test that objects with the same name and different classes are distinct.
TEST_F(HashTableTest, ClassTest) {
More information about the bind10-changes
mailing list