Branch data Line data Source code
1 : : // Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC")
2 : : //
3 : : // Permission to use, copy, modify, and/or distribute this software for any
4 : : // purpose with or without fee is hereby granted, provided that the above
5 : : // copyright notice and this permission notice appear in all copies.
6 : : //
7 : : // THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
8 : : // REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
9 : : // AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
10 : : // INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
11 : : // LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
12 : : // OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
13 : : // PERFORMANCE OF THIS SOFTWARE.
14 : :
15 : : #ifndef __HASH_TABLE_H
16 : : #define __HASH_TABLE_H
17 : :
18 : : #include <list>
19 : :
20 : : #include <boost/shared_ptr.hpp>
21 : :
22 : : #include <util/locks.h>
23 : :
24 : : #include "hash.h"
25 : : #include "hash_key.h"
26 : :
27 : : // Maximum key length if the maximum size of a DNS name
28 : : #define MAX_KEY_LENGTH 255
29 : :
30 : : namespace isc {
31 : : namespace nsas {
32 : :
33 : : /// \brief Hash Table Slot
34 : : ///
35 : : /// Describes the entry for the hash table. This is non-copyable (because
36 : : /// the mutex is non-copyable), but we need to be able to copy it to initialize
37 : : /// a vector of hash table slots. As the copy is only needed for
38 : : /// initialization, and as there is no need to copy state when this happens, we
39 : : /// cheat: the copy constructor constructs a newly initialized HashTableSlot and
40 : : /// does not copy its argument.
41 : : template <typename T>
42 : 1483463 : struct HashTableSlot {
43 : :
44 : : /// \brief Type definitions
45 : : ///
46 : : //@{
47 : :
48 : : typedef typename std::list<boost::shared_ptr<T> >::iterator iterator;
49 : : ///< Iterator over elements with same hash
50 : :
51 : : typedef isc::util::locks::upgradable_mutex mutex_type;
52 : : ///< Mutex protecting this slot
53 : : //@}
54 : :
55 : : /// \brief Default Constructor
56 : : HashTableSlot()
57 : 227 : {}
58 : :
59 : : /// \brief Copy Constructor
60 : : ///
61 : : /// ... which as noted in the class description does not copy.
62 : 1491256 : HashTableSlot(const HashTableSlot<T>&) : mutex_(), list_()
63 : 0 : { }
64 : :
65 : : public:
66 : : mutex_type mutex_; ///< Protection mutex
67 : : std::list<boost::shared_ptr<T> > list_; ///< List head
68 : : };
69 : :
70 : : /// \brief Comparison Object Class
71 : : ///
72 : : /// The base class for a comparison object; this object is used to compare
73 : : /// an object in the hash table with a key, and indicates whether the two
74 : : /// match. All objects used for comparison in hash tables should be derived
75 : : /// from this class.
76 : : template <typename T>
77 : : class HashTableCompare {
78 : : public:
79 : : /// \brief Constructor
80 : 228 : HashTableCompare(){}
81 : :
82 : : /// \brief virtual Destructor
83 : 224 : virtual ~HashTableCompare() {}
84 : :
85 : : /// \brief Comparison Function
86 : : ///
87 : : /// Compares an object against a name in the hash table and reports if the
88 : : /// object's name is the same.
89 : : ///
90 : : /// \param object Pointer to the object
91 : : /// \param key Key describing the object
92 : : ///
93 : : /// \return bool true of the name of the object is equal to the name given.
94 : : virtual bool operator()(T* object, const HashKey& key) const = 0;
95 : : };
96 : :
97 : :
98 : : /// \brief Hash Table
99 : : ///
100 : : /// This class is an implementation of a hash table in which the zones and
101 : : /// nameservers of the Nameserver Address Store are held.
102 : : ///
103 : : /// A special class has been written (rather than use an existing hash table
104 : : /// class) to improve concurrency. Rather than lock the entire hash table when
105 : : /// an object is added/removed/looked up, only the entry for a particular hash
106 : : /// value is locked. To do this, each entry in the hash table is a pair of
107 : : /// mutex/STL List; the mutex protects that particular list.
108 : : ///
109 : : /// \param T Class of object to be stored in the table.
110 : : template <typename T>
111 : : class HashTable {
112 : : public:
113 : :
114 : : /// \brief Type Definitions
115 : : ///
116 : : //@{
117 : : typedef typename
118 : : isc::util::locks::sharable_lock<typename HashTableSlot<T>::mutex_type>
119 : : sharable_lock; ///< Type for a scope-limited read-lock
120 : :
121 : : typedef typename
122 : : isc::util::locks::scoped_lock<typename HashTableSlot<T>::mutex_type>
123 : : scoped_lock; ///< Type for a scope-limited write-lock
124 : : //@}
125 : :
126 : : /// \brief Constructor
127 : : ///
128 : : /// Initialises the hash table.
129 : : ///
130 : : /// \param cmp Compare function (or object) used to compare an object with
131 : : /// to get the name to be used as a key in the table. The object should be
132 : : /// created via a "new" as ownership passes to the hash table. The hash
133 : : /// table will take the responsibility of deleting it.
134 : : /// \param size Size of the hash table. For best result, this should be a
135 : : /// prime although that is not checked. The default value is the size used
136 : : /// in BIND-9 for its address database.
137 : : HashTable(HashTableCompare<T>* cmp, uint32_t size = 1009);
138 : :
139 : : /// \brief Destructor
140 : : ///
141 [ + - ][ + - ]: 293 : virtual ~HashTable(){}
142 : :
143 : : /// \brief Get Entry
144 : : ///
145 : : /// 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
148 : : /// calculated and used to index the table.
149 : : ///
150 : : /// \return Shared pointer to the object or NULL if it is not there.
151 : 7 : boost::shared_ptr<T> get(const HashKey& key) {
152 [ + - + - ]: 348 : uint32_t index = hash_(key);
[ + - + - ]
153 : : sharable_lock lock(table_[index].mutex_);
154 [ + - ][ + - ]: 348 : return getInternal(key, index);
155 : : }
156 : :
157 : : /// \brief Remove Entry
158 : : ///
159 : : /// Remove the specified entry. The shared pointer to the object is
160 : : /// destroyed, so if this is the last pointer, the object itself is also
161 : : /// destroyed.
162 : : ///
163 : : /// \param key Name of the object (and class). The hash of this is
164 : : /// calculated and used to index the table.
165 : : ///
166 : : /// \return true if the object was deleted, false if it was not found.
167 : : bool remove(const HashKey& key);
168 : :
169 : : /// \brief Add Entry
170 : : ///
171 : : /// Adds the specified entry to the table. If there is an entry already
172 : : /// there, it is either replaced or the addition fails, depending on the
173 : : /// setting of the "replace" parameter.
174 : : ///
175 : : /// \param object Pointer to the object to be added. If the addition is
176 : : /// successful, this object will have a shared pointer pointing to it; it
177 : : /// should not be deleted by the caller.
178 : : /// \param key Key to use to calculate the hash.
179 : : /// \param replace If true, when an object is added and an object with the
180 : : /// same name already exists, the existing object is replaced. If false,
181 : : // the addition fails and a status is returned.
182 : : /// \return true if the object was successfully added, false otherwise.
183 : 15 : bool add(boost::shared_ptr<T>& object, const HashKey& key,
184 : : bool replace = false)
185 : : {
186 [ + - ][ + - ]: 220 : uint32_t index = hash_(key);
187 : : scoped_lock lock(table_[index].mutex_);
188 [ + - ]: 220 : return addInternal(object, key, index, replace);
189 : : }
190 : :
191 : : /**
192 : : * \brief Attomicly lookup an entry or add a new one if it does not exist.
193 : : *
194 : : * Looks up an entry specified by key in the table. If it is not there,
195 : : * it calls generator() and adds its result to the table under given key.
196 : : * It is performed attomically to prevent race conditions.
197 : : *
198 : : * \param key The entry to lookup.
199 : : * \param generator will be called when the item is not there. Its result
200 : : * will be added and returned. The generator should return as soon
201 : : * as possible, the slot is locked during its execution.
202 : : * \return The boolean part of pair tells if the value was added (true
203 : : * means new value, false looked up one). The other part is the
204 : : * object, either found or created.
205 : : * \todo This uses a scoped_lock, which does not allow sharing and is
206 : : * used a lot in the code. It might turn out in future that it is a
207 : : * problem and that most of the accesses is read only. In that case we
208 : : * could split it to fast-slow path - first try to find it with
209 : : * shared_lock. If it fails, lock by scoped_lock, try to find again (we
210 : : * unlocked it, so it might have appeared) and if it still isn't there,
211 : : * create it. Not implemented now as it might or might not help (it
212 : : * could even slow it down) and the code would get more complicated.
213 : : */
214 : : template<class Generator>
215 : 2019 : std::pair<bool, boost::shared_ptr<T> > getOrAdd(const HashKey& key,
216 : : const Generator& generator)
217 : : {
218 [ + - ]: 2047 : uint32_t index = hash_(key);
219 : : scoped_lock lock(table_[index].mutex_);
220 [ + - ]: 2047 : boost::shared_ptr<T> result(getInternal(key, index));
221 [ + + ]: 2047 : if (result) {
222 : : return (std::pair<bool, boost::shared_ptr<T> >(false, result));
223 : : } else {
224 [ + - ]: 20 : result = generator();
225 [ + - ]: 33 : addInternal(result, key, index);
226 : : return (std::pair<bool, boost::shared_ptr<T> >(true, result));
227 : : }
228 : : }
229 : :
230 : : /// \brief Returns Size of Hash Table
231 : : ///
232 : : /// \return Size of hash table
233 : : uint32_t tableSize() const {
234 : 16 : return table_.size();
235 : : }
236 : :
237 : : protected:
238 : : // Internal parts, expect to be already locked
239 : : boost::shared_ptr<T> getInternal(const HashKey& key,
240 : : uint32_t index);
241 : : bool addInternal(boost::shared_ptr<T>& object, const HashKey& key,
242 : : uint32_t index, bool replace = false);
243 : :
244 : : private:
245 : : Hash hash_; ///< Hashing function
246 : : std::vector<HashTableSlot<T> > table_; ///< The hash table itself
247 : : boost::shared_ptr<HashTableCompare<T> > compare_; ///< Compare object
248 : : };
249 : :
250 : :
251 : : // Constructor
252 : : template <typename T>
253 : 227 : HashTable<T>::HashTable(HashTableCompare<T>* compare, uint32_t size) :
254 [ # # ]: 227 : hash_(size, MAX_KEY_LENGTH), table_(size), compare_(compare)
255 : 227 : {}
256 : :
257 : : // Lookup an object in the table
258 : : template <typename T>
259 : 2395 : boost::shared_ptr<T> HashTable<T>::getInternal(const HashKey& key,
260 : : uint32_t index)
261 : : {
262 : : // Locate the object.
263 : : typename HashTableSlot<T>::iterator i;
264 [ + + ]: 2442 : for (i = table_[index].list_.begin(); i != table_[index].list_.end(); ++i) {
265 [ + + + ]: 2194 : if ((*compare_)(i->get(), key)) {
266 : :
267 : : // Found it, so return the shared pointer object
268 : 2147 : return (*i);
269 : : }
270 : : }
271 : :
272 : : // Did not find it, return an empty shared pointer object.
273 : : return boost::shared_ptr<T>();
274 : : }
275 : :
276 : : // Remove an entry from the hash table
277 : : template <typename T>
278 : 171 : bool HashTable<T>::remove(const HashKey& key) {
279 : :
280 : : // Calculate the hash value
281 : 173 : uint32_t index = hash_(key);
282 : :
283 : : // Access to the elements of this hash slot are accessed under a mutex.
284 : : // The mutex will be released when this object goes out of scope and is
285 : : // destroyed.
286 : : scoped_lock lock(table_[index].mutex_);
287 : :
288 : : // Now search this list to see if the element already exists.
289 : : typename HashTableSlot<T>::iterator i;
290 [ + + ][ + - ]: 348 : for (i = table_[index].list_.begin(); i != table_[index].list_.end(); ++i) {
291 [ + + + ]: 177 : if ((*compare_)(i->get(), key)) {
[ + - ]
292 : :
293 : : // Object found so delete it.
294 : 37 : table_[index].list_.erase(i);
295 : 170 : return true;;
296 : : }
297 : : }
298 : :
299 : : // When we get here, we know that there is no element with the key in the
300 : : // list, so tell the caller.
301 : : return false;
302 : : }
303 : :
304 : : // Add an entry to the hash table
305 : : template <typename T>
306 : 253 : bool HashTable<T>::addInternal(boost::shared_ptr<T>& object,
307 : : const HashKey& key, uint32_t index, bool replace)
308 : : {
309 : : // Search this list to see if the element already exists.
310 : : typename HashTableSlot<T>::iterator i;
311 [ + + ][ + + ]: 302 : for (i = table_[index].list_.begin(); i != table_[index].list_.end(); ++i) {
312 [ + + - ]: 75 : if ((*compare_)(i->get(), key)) {
[ - + ]
313 : :
314 : : // Object found. If we are not allowed to replace the element,
315 : : // return an error. Otherwise erase it from the list and exit the
316 : : // loop.
317 [ + + ][ # # ]: 26 : if (replace) {
318 : 25 : table_[index].list_.erase(i);
319 : 25 : break;
320 : : }
321 : : else {
322 : : return false;
323 : : }
324 : : }
325 : : }
326 : :
327 : : // When we get here, we know that there is no element with the key in the
328 : : // list - in which case, add the new object.
329 : 504 : table_[index].list_.push_back(object);
330 : :
331 : 253 : return true;
332 : : }
333 : :
334 : : } // namespace nsas
335 : : } // namespace isc
336 : :
337 : : #endif // __HASH_TABLE_H
|
