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