1 // TortoiseSVN - a Windows shell extension for easy version control
\r
3 // Copyright (C) 2007-2007 - TortoiseSVN
\r
5 // This program is free software; you can redistribute it and/or
\r
6 // modify it under the terms of the GNU General Public License
\r
7 // as published by the Free Software Foundation; either version 2
\r
8 // of the License, or (at your option) any later version.
\r
10 // This program is distributed in the hope that it will be useful,
\r
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
13 // GNU General Public License for more details.
\r
15 // You should have received a copy of the GNU General Public License
\r
16 // along with this program; if not, write to the Free Software Foundation,
\r
17 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
\r
21 ///////////////////////////////////////////////////////////////
\r
22 // necessary includes
\r
23 ///////////////////////////////////////////////////////////////
\r
25 #include "QuickHash.h"
\r
29 * A quick associative container that maps K (key) to V (value) instances.
\r
30 * K must implicitly convert to size_t.
\r
32 template<class K, class V>
\r
33 class quick_hash_map
\r
37 /// our actual data container
\r
43 element_type (K key, const V& value)
\r
44 : key (key), value (value)
\r
49 typedef std::vector<element_type> data_type;
\r
53 * A simple string hash function that satisfies quick_hash interface
\r
56 * NULL strings are supported and are mapped to index 0.
\r
57 * Hence, the dictionary must contain the empty string at index 0.
\r
63 /// the data container we index with the hash
\r
64 /// (used to map key -> (key, value))
\r
65 typedef typename quick_hash_map<K, V>::data_type data_type;
\r
70 // simple construction
\r
72 CHashFunction (data_type* map)
\r
77 // required typedefs and constants
\r
79 typedef K value_type;
\r
80 typedef size_t index_type;
\r
82 enum {NO_INDEX = LogCache::NO_INDEX};
\r
84 /// the actual hash function
\r
85 size_t operator() (value_type value) const
\r
90 /// dictionary lookup
\r
91 value_type value (index_type index) const
\r
93 return (*data)[index].key;
\r
96 /// lookup and comparison
\r
97 bool equal (value_type value, index_type index) const
\r
99 return value == (*data)[index].key;
\r
103 friend class CHashFunction;
\r
105 // hash index over this container
\r
107 quick_hash<CHashFunction> hash;
\r
111 // publicly available types
\r
113 typedef typename K key_type;
\r
114 typedef typename V value_type;
\r
116 class const_iterator
\r
120 typedef typename quick_hash_map<K,V>::data_type::const_iterator iterator;
\r
121 typedef typename quick_hash_map<K,V>::element_type value_type;
\r
129 const_iterator (iterator iter)
\r
134 // pointer-like behavior
\r
136 const V& operator*() const
\r
138 return iter->value;
\r
141 const value_type* operator->() const
\r
148 bool operator== (const const_iterator& rhs) const
\r
150 return iter == rhs.iter;
\r
153 bool operator!= (const const_iterator& rhs) const
\r
155 return iter != rhs.iter;
\r
160 const_iterator& operator++() // prefix
\r
166 const_iterator operator++(int) // postfix
\r
168 const_iterator result (*this);
\r
173 const_iterator& operator+= (size_t diff)
\r
179 const_iterator& operator-= (size_t diff)
\r
185 const_iterator operator+ (size_t diff) const
\r
187 return const_iterator (*this) += diff;
\r
190 const_iterator operator- (size_t diff) const
\r
192 return const_iterator (*this) -= diff;
\r
196 friend class const_iterator;
\r
199 // (default-implemented destruction works as desired)
\r
202 : hash (CHashFunction (&data))
\r
206 quick_hash_map (const quick_hash_map& rhs)
\r
207 : hash (CHashFunction (&data))
\r
214 quick_hash_map& operator= (const quick_hash_map& rhs)
\r
224 const_iterator begin() const
\r
226 return data.begin();
\r
229 const_iterator end() const
\r
234 const_iterator find (key_type key) const
\r
236 size_t index = hash.find (key);
\r
237 return index == LogCache::NO_INDEX
\r
242 // insert a new key, value pair
\r
244 void insert (key_type key, const value_type& value)
\r
246 assert (find (key) == end());
\r
248 data.push_back (element_type (key, value));
\r
249 hash.insert (key, data.size()-1);
\r
252 void reserve (size_t min_bucket_count)
\r
254 if (data.capacity() < min_bucket_count)
\r
256 data.reserve (min_bucket_count);
\r
257 hash.reserve (min_bucket_count);
\r
261 // get rid of all entries
\r