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_H
16 : : #define __HASH_H
17 : :
18 : : #include <stdint.h>
19 : : #include <vector>
20 : :
21 : : #include <exceptions/exceptions.h>
22 : :
23 : : #include "hash_key.h"
24 : :
25 : : namespace isc {
26 : : namespace nsas {
27 : :
28 : : /// \brief Too Long Key Length
29 : : ///
30 : : /// Thrown if the expected maximum key length is too long for the data types
31 : : /// declared in the class.
32 : 0 : class KeyLengthTooLong : public isc::Exception {
33 : : public:
34 : : KeyLengthTooLong(const char* file, size_t line, const char* what) :
35 : 0 : isc::Exception(file, line, what)
36 : : {}
37 : : };
38 : :
39 : :
40 : : /// \brief Hash Calculation
41 : : ///
42 : : /// Class abstracting the mechanics of the hash calculation.
43 : : class Hash {
44 : : public:
45 : :
46 : : /// \brief Constructor
47 : : ///
48 : : /// Constructs the hash table and initialises all data structures needed
49 : : /// for the hashing.
50 : : ///
51 : : /// \param tablesize Size of the hash table. For best performance, this
52 : : /// should be a prime number.
53 : : /// \param maxkeylen Maximum length (in bytes) of a key to be hashed.
54 : : /// calculation will return a value between 0 and N-1. The default
55 : : /// value of 255 is the maximum size of a DNS name.
56 : : /// \param randomise If true (the default), the pseudo-random number
57 : : /// generator is seeded with the current time. Otherwise it is initialised
58 : : /// to a known sequence. This is principally for unit tests, where a random
59 : : /// sequence could lead to problems in checking results.
60 : : Hash(uint32_t tablesize, uint32_t maxkeylen = 255, bool randomise = true);
61 : :
62 : : /// \brief Virtual Destructor
63 : 229 : virtual ~Hash()
64 : 229 : {}
65 : :
66 : : /// \brief Return Size
67 : : ///
68 : : /// \return The hash table size with which this object was initialized
69 : 0 : virtual uint32_t tableSize() const {
70 : 0 : return tablesize_;
71 : : }
72 : :
73 : : /// \brief Return Key Length
74 : : ///
75 : : /// \return Maximum length of a key that this class can cope with.
76 : 0 : virtual uint32_t maxKeyLength() const {
77 : 0 : return maxkeylen_;
78 : : }
79 : :
80 : : /// \brief Hash Value
81 : : ///
82 : : /// \param key Parameters comprising the key to be hashed.
83 : : /// \param ignorecase true for case to be ignored when calculating the
84 : : /// hash value, false for it to be taken into account.
85 : : ///
86 : : /// \return Hash value, a number between 0 and N-1.
87 : : virtual uint32_t operator()(const HashKey& key,
88 : : bool ignorecase = true) const;
89 : :
90 : : /// \brief Map Lower Case to Upper Case
91 : : ///
92 : : /// Equivalent of tolower(), but using a table lookup instead of a
93 : : /// function call. This should make the mapping faster.
94 : : ///
95 : : /// \param inchar Input character
96 : : ///
97 : : /// \return Mapped character
98 : 37326 : virtual unsigned char mapLower(unsigned char inchar) const {
99 : 37326 : return casemap_[inchar];
100 : : }
101 : :
102 : : private:
103 : :
104 : : /// \name Local Typedefs
105 : : ///
106 : : /// Typedefs for use in the code. This makes it easier to compare the
107 : : /// hashing code with that in BIND-9.
108 : : //@{
109 : : typedef uint32_t hash_accum_t; ///< Accumulator
110 : : typedef uint16_t hash_random_t; ///< Random number used in hash
111 : : //@}
112 : :
113 : : uint32_t tablesize_; ///< Size of the hash table
114 : : uint32_t maxkeylen_; ///< Maximum key length
115 : : std::vector<unsigned char> casemap_; ///< Case mapping table
116 : : std::vector<hash_random_t> randvec_; ///< Vector of random numbers
117 : :
118 : : static const uint32_t prime32_ = 0xfffffffb; ///< 2^32 - 5
119 : : ///< Specifies range of hash output
120 : : };
121 : :
122 : : } // namspace nsas
123 : : } // namespace isc
124 : :
125 : : #endif // __HASH_H
|
