hash_table.h 11.8 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
// Copyright (C) 2010  Internet Systems Consortium, Inc. ("ISC")
//
// Permission to use, copy, modify, and/or distribute this software for any
// purpose with or without fee is hereby granted, provided that the above
// copyright notice and this permission notice appear in all copies.
//
// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
// AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
// PERFORMANCE OF THIS SOFTWARE.

#ifndef __HASH_TABLE_H
#define __HASH_TABLE_H

18
#include <list>
19

20 21
#include <boost/shared_ptr.hpp>

22
#include "locks.h"
23
#include "hash.h"
24
#include "hash_key.h"
25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

// Maximum key length if the maximum size of a DNS name
#define MAX_KEY_LENGTH 255

namespace isc {
namespace nsas {

/// \brief Hash Table Slot
///
/// Describes the entry for the hash table.  This is non-copyable (because
/// the mutex is non-copyable), but we need to be able to copy it to initialize
/// a vector of hash table slots.  As the copy is only needed for
/// initialization, and as there is no need to copy state when this happens, we
/// cheat: the copy constructor constructs a newly initialized HashTableSlot and
/// does not copy its argument.
template <typename T>
struct HashTableSlot {

43 44 45 46 47 48 49
    /// \brief Type definitions
    ///
    //@{

    typedef typename std::list<boost::shared_ptr<T> >::iterator  iterator;
                                    ///< Iterator over elements with same hash

50
    typedef isc::locks::upgradable_mutex mutex_type;
51 52
                                    ///< Mutex protecting this slot
    //@}
53 54 55 56 57 58 59

    /// \brief Default Constructor
    HashTableSlot()
    {}

    /// \brief Copy Constructor
    ///
Michal Vaner's avatar
Michal Vaner committed
60 61 62
    /// ... which as noted in the class description does not copy.
    HashTableSlot(const HashTableSlot<T>&)
    { }
63

64 65 66
public:
    mutex_type                          mutex_;     ///< Protection mutex
    std::list<boost::shared_ptr<T> >    list_;      ///< List head
67 68 69 70 71 72 73 74 75 76 77
};

/// \brief Comparison Object Class
///
/// The base class for a comparison object; this object is used to compare
/// an object in the hash table with a key, and indicates whether the two
/// match.  All objects used for comparison in hash tables should be derived
/// from this class.
template <typename T>
class HashTableCompare {
public:
78 79 80 81 82
    /// \brief Constructor
    HashTableCompare(){}

    /// \brief virtual Destructor
    virtual ~HashTableCompare() {}
83 84 85 86 87 88 89

    /// \brief Comparison Function
    ///
    /// Compares an object against a name in the hash table and reports if the
    /// object's name is the same.
    ///
    /// \param object Pointer to the object
90
    /// \param key Key describing the object
91 92
    ///
    /// \return bool true of the name of the object is equal to the name given.
93
    virtual bool operator()(T* object, const HashKey& key) const = 0;
94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112
};


/// \brief Hash Table
///
/// This class is an implementation of a hash table in which the zones and
/// nameservers of the Nameserver Address Store are held.
///
/// A special class has been written (rather than use an existing hash table
/// class) to improve concurrency.  Rather than lock the entire hash table when
/// an object is added/removed/looked up, only the entry for a particular hash
/// value is locked.  To do this, each entry in the hash table is a pair of
/// mutex/STL List; the mutex protects that particular list.
///
/// \param T Class of object to be stored in the table.
template <typename T>
class HashTable {
public:

113 114 115 116
    /// \brief Type Definitions
    ///
    //@{
    typedef typename
117
    isc::locks::sharable_lock<typename HashTableSlot<T>::mutex_type>
118 119 120
    sharable_lock;                  ///< Type for a scope-limited read-lock

    typedef typename
121
    isc::locks::scoped_lock<typename HashTableSlot<T>::mutex_type>
122 123
    scoped_lock;                    ///< Type for a scope-limited write-lock
    //@}
124

125 126 127 128 129 130 131 132 133 134 135 136 137
    /// \brief Constructor
    ///
    /// Initialises the hash table.
    ///
    /// \param CmpFn Compare function (or object) used to compare an object with
    /// to get the name to be used as a key in the table.  The object should be
    /// created via a "new" as ownership passes to the hash table.  The hash
    /// table will take the responsibility of deleting it.
    /// \param size Size of the hash table.  For best result, this should be a
    /// prime although that is not checked.  The default value is the size used
    /// in BIND-9 for its address database.
    HashTable(HashTableCompare<T>* cmp, uint32_t size = 1009);

138 139 140 141
    /// \brief Destructor
    ///
    virtual ~HashTable(){}

142 143 144 145
    /// \brief Get Entry
    ///
    /// Returns a shared_ptr object pointing to the table entry
    ///
146 147
    /// \param key Name of the object (and class).  The hash of this is
    /// calculated and used to index the table.
148
    ///
149
    /// \return Shared pointer to the object or NULL if it is not there.
Michal Vaner's avatar
Michal Vaner committed
150
    boost::shared_ptr<T> get(const HashKey& key) {
151
        uint32_t index = hash_(key);
Michal Vaner's avatar
Michal Vaner committed
152
        sharable_lock lock(table_[index].mutex_);
153 154
        return getInternal(key, index);
    }
155 156 157 158 159 160 161

    /// \brief Remove Entry
    ///
    /// Remove the specified entry.  The shared pointer to the object is
    /// destroyed, so if this is the last pointer, the object itself is also
    /// destroyed.
    ///
162 163
    /// \param key Name of the object (and class).  The hash of this is
    /// calculated and used to index the table.
164 165
    ///
    /// \return true if the object was deleted, false if it was not found.
Michal Vaner's avatar
Michal Vaner committed
166
    bool remove(const HashKey& key);
167 168 169 170 171 172 173 174 175 176 177 178 179 180 181

    /// \brief Add Entry
    ///
    /// Adds the specified entry to the table.  If there is an entry already
    /// there, it is either replaced or the addition fails, depending on the
    /// setting of the "replace" parameter.
    ///
    /// \param object Pointer to the object to be added.  If the addition is
    /// successful, this object will have a shared pointer pointing to it; it
    /// should not be deleted by the caller.
    /// \param key Key to use to calculate the hash.
    /// \param replace If true, when an object is added and an object with the
    /// same name already exists, the existing object is replaced.  If false,
    // the addition fails and a status is returned.
    /// \return true if the object was successfully added, false otherwise.
Michal Vaner's avatar
Michal Vaner committed
182
    bool add(boost::shared_ptr<T>& object, const HashKey& key,
183 184 185 186 187 188 189
        bool replace = false)
    {
        uint32_t index = hash_(key);
        scoped_lock lock(table_[index].mutex_);
        return addInternal(object, key, index, replace);
    }

Michal Vaner's avatar
Michal Vaner committed
190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212
    /**
     * \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. The generator should return as soon
     *     as possible, the slot is locked during its execution.
     * \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.
     * \todo This uses a scoped_lock, which does not allow sharing and is
     *     used a lot in the code. It might turn out in future that it is a
     *     problem and that most of the accesses is read only. In that case we
     *     could split it to fast-slow path - first try to find it with
     *     shared_lock. If it fails, lock by scoped_lock, try to find again (we
     *     unlocked it, so it might have appeared) and if it still isn't there,
     *     create it. Not implemented now as it might or might not help (it
     *     could even slow it down) and the code would get more complicated.
     */
213 214 215 216 217 218 219 220
    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) {
Michal Vaner's avatar
Michal Vaner committed
221
            return (std::pair<bool, boost::shared_ptr<T> >(false, result));
222 223 224
        } else {
            result = generator();
            addInternal(result, key, index);
Michal Vaner's avatar
Michal Vaner committed
225
            return (std::pair<bool, boost::shared_ptr<T> >(true, result));
226 227
        }
    }
228 229 230 231

    /// \brief Returns Size of Hash Table
    ///
    /// \return Size of hash table
Michal Vaner's avatar
Michal Vaner committed
232
    uint32_t tableSize() const {
233 234 235
        return table_.size();
    }

236 237
protected:
    // Internal parts, expect to be already locked
Michal Vaner's avatar
Michal Vaner committed
238
    boost::shared_ptr<T> getInternal(const HashKey& key,
239
        uint32_t index);
Michal Vaner's avatar
Michal Vaner committed
240
    bool addInternal(boost::shared_ptr<T>& object, const HashKey& key,
241 242
        uint32_t index, bool replace = false);

243
private:
244 245
    Hash                             hash_;  ///< Hashing function
    std::vector<HashTableSlot<T> >   table_; ///< The hash table itself
246 247 248 249 250 251 252 253 254 255 256 257
    boost::shared_ptr<HashTableCompare<T> > compare_;  ///< Compare object
};


// Constructor
template <typename T>
HashTable<T>::HashTable(HashTableCompare<T>* compare, uint32_t size) :
    hash_(size, MAX_KEY_LENGTH), table_(size), compare_(compare)
{}

// Lookup an object in the table
template <typename T>
258 259 260
boost::shared_ptr<T> HashTable<T>::getInternal(const HashKey& key,
    uint32_t index)
{
261 262 263
    // Locate the object.
    typename HashTableSlot<T>::iterator i;
    for (i = table_[index].list_.begin(); i != table_[index].list_.end(); ++i) {
264
        if ((*compare_)(i->get(), key)) {
265 266 267 268 269 270 271 272 273 274 275 276

            // Found it, so return the shared pointer object
            return (*i);
        }
    }

    // Did not find it, return an empty shared pointer object.
    return boost::shared_ptr<T>();
}

// Remove an entry from the hash table
template <typename T>
277
bool HashTable<T>::remove(const HashKey& key) {
278 279

    // Calculate the hash value
280
    uint32_t index = hash_(key);
281 282 283 284

    // Access to the elements of this hash slot are accessed under a mutex.
    // The mutex will be released when this object goes out of scope and is
    // destroyed.
285
    scoped_lock lock(table_[index].mutex_);
286 287 288 289

    // Now 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) {
290
        if ((*compare_)(i->get(), key)) {
291 292 293 294 295 296 297 298 299 300 301 302 303 304

            // Object found so delete it.
            table_[index].list_.erase(i);
            return true;;
        }
    }

    // When we get here, we know that there is no element with the key in the
    // list, so tell the caller.
    return false;
}

// Add an entry to the hash table
template <typename T>
305 306
bool HashTable<T>::addInternal(boost::shared_ptr<T>& object,
    const HashKey& key, uint32_t index, bool replace)
307
{
308
    // Search this list to see if the element already exists.
309 310
    typename HashTableSlot<T>::iterator i;
    for (i = table_[index].list_.begin(); i != table_[index].list_.end(); ++i) {
311
        if ((*compare_)(i->get(), key)) {
312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336

            // Object found.  If we are not allowed to replace the element,
            // return an error.  Otherwise erase it from the list and exit the
            // loop.
            if (replace) {
                table_[index].list_.erase(i);
                break;
            }
            else {
                return false;
            }
        }
    }

    // When we get here, we know that there is no element with the key in the
    // list - in which case, add the new object.
    table_[index].list_.push_back(object);

    return true;
}

}   // namespace nsas
}   // namespace isc

#endif // __HASH_TABLE_H