1 ////////////////////////////////////////////////////////////////////////////////
2 // $Id: map.h,v 1.10 2006/11/18 03:12:34 dmouldin Exp $
4 // Visual Leak Detector - Lightweight STL-like Map Template
5 // Copyright (c) 2006 Dan Moulding
7 // This library is free software; you can redistribute it and/or
8 // modify it under the terms of the GNU Lesser General Public
9 // License as published by the Free Software Foundation; either
10 // version 2.1 of the License, or (at your option) any later version.
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 // Lesser General Public License for more details.
17 // You should have received a copy of the GNU Lesser General Public
18 // License along with this library; if not, write to the Free Software
19 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
21 // See COPYING.txt for the full terms of the GNU Lesser General Public License.
23 ////////////////////////////////////////////////////////////////////////////////
29 "This header should only be included by Visual Leak Detector when building it from source. \
30 Applications should never include this header."
33 #include "tree.h" // Provides access to the Tree template class.
35 ////////////////////////////////////////////////////////////////////////////////
37 // The Pair Template Class
39 // This is a lightweight STL-like pair template, for use with the lightweight
40 // Map class template.
42 // Note that while this is a STL-like class, it is not a full STL-compliant
43 // implementation of the STL pair utility class. It provides just the bare
44 // minimum functionality required by the Visual Leak Detector Map template
47 template <typename Tf, typename Ts>
57 // Constructor with initializers.
58 Pair (const Tf &f, const Ts &s)
64 // Less-than operator - Compares this Pair with another Pair to determine
65 // if this Pair is less than the other Pair. The Pair with the smallest
66 // "first" value is the lesser Pair.
68 // - other (IN): The other pair to compare against.
72 // Returns true if this Pair is less than the other Pair. Otherwise
75 BOOL operator < (const Pair &other) const
77 return (first < other.first);
81 Tf first; // The first value of the pair.
82 Ts second; // The second value of the pair.
85 ////////////////////////////////////////////////////////////////////////////////
87 // The Map Template Class
89 // This is a lightweidht STL-like map template. It makes use of the Tree class
90 // template to enable fast insert, find, and erase operations.
92 // Note that while this is a STL-like class, it is not a full STL-compliant
93 // implementation of the STL map container. It contains just the bare minimum
94 // functionality required by Visual Leak Detector. Because of its "lightweight"
95 // nature, this map class has a noticeable performance advantage over some
96 // other standard STL map implementations.
98 template <typename Tk, typename Tv>
106 // Plainly constructed iterators don't reference anything.
111 // operator != - Inequality operator for Map Iterators. Two Map
112 // Iterators are considered equal if and only if they both reference
113 // the same key/value pair in the same Map.
115 // - other (IN): The other Map Iterator to compare against.
119 // Returns true if the specified Map Iterator is not equal to this
120 // Map Iterator; otherwise, returns false.
122 BOOL operator != (const Iterator &other) const
124 return ((m_tree != other.m_tree) || (m_node != other.m_node));
127 // operator * - Dereference operator for Map Iterators.
129 // Note: The reference returned by this function is "const", so the
130 // value referenced by the Iterator may not be modified through the
131 // Iterator. This is a departure from STL iterator behavior.
133 // Also, dereferencing an Iterator which does not reference a valid
134 // value in the Map is undefined and will almost certainly cause a
139 // Returns a const reference to the key/value pair in the Map
140 // referenced by the Iterator.
142 const Pair<Tk, Tv>& operator * () const
147 // operator ++ - Prefix increment operator for Map Iterators. Causes the
148 // Iterator to reference the in-oder successor of the key/value pair
149 // currently referenced by the Iterator. If the Iterator is currently
150 // referencing the largest key/value pair in the Map, then the
151 // resulting Iterator will reference the Map's end (the NULL pair).
153 // Note: Incrementing an Iterator which does not reference a valid
154 // key/value pair in the Map is undefined and will almost certainly
159 // Returns the Iterator after it has been incremented.
161 Iterator& operator ++ (int)
163 m_node = m_tree->next(m_node);
167 // operator ++ - Postfix increment operator for Map Iterators. Causes
168 // the Iterator to reference the in-order successor of the key/value
169 // pair currently referenced by the Iterator. If the Iterator is
170 // currently referencing the largest key/value pair in the Map, then
171 // the resulting Iterator will reference the Map's end (the NULL
174 // Note: Incrementing an Iterator which does not reference a valid
175 // key/value pair in the Map is undefined and will almost certainly
180 // Returns the Iterator before it has been incremented.
182 Iterator operator ++ ()
184 typename Tree<Pair<Tk, Tv> >::node_t *cur = m_node;
186 m_node = m_tree->next(m_node);
187 return Iterator(m_tree, cur);
190 // operator - - Subtraction operator for Map Iterators. Causes the
191 // the Iterator to reference a key/value pair that is an in-order
192 // predecessor of the currently refereced key/value pair.
194 // - num (IN): Number indicating the number of preceding key/value
195 // pairs to decrement the iterator.
199 // Returns an Iterator referencing the key/value pair that precedes
200 // the original Iterator by "num" pairs.
202 Iterator operator - (SIZE_T num) const
205 typename Tree<Pair<Tk, Tv> >::node_t *cur = m_node;
207 cur = m_tree->prev(m_node);
208 for (count = 0; count < num; count++) {
209 cur = m_tree->prev(m_node);
211 return Iterator(m_tree, NULL);
214 return Iterator(m_tree, cur);
217 // operator == - Equality operator for Map Iterators. Map Iterators are
218 // considered equal if and only if they both refernce the same
219 // key/value pair in the same Map.
221 // - other (IN): The other Map Iterator to compare against.
225 // Returns true if the specified Map Iterator is equal to this Map
226 // Iterator; otherwise returns false.
228 BOOL operator == (const Iterator &other) const
230 return ((m_tree == other.m_tree) && (m_node == other.m_node));
234 // Private constructor. Only the Map class itself may use this
235 // constructor. It is used for constructing Iterators which reference
236 // specific nodes in the internal tree's structure.
237 Iterator (const Tree<Pair<Tk, Tv> > *tree, typename Tree<Pair<Tk, Tv> >::node_t *node)
243 typename Tree<Pair<Tk, Tv> >::node_t *m_node; // Pointer to the node referenced by the Map Iterator.
244 const Tree<Pair<Tk, Tv> > *m_tree; // Pointer to the tree containing the referenced node.
246 // The Map class is a friend of Map Iterators.
247 friend class Map<Tk, Tv>;
250 // begin - Obtains an Iterator referencing the beginning of the Map (i.e.
251 // the lowest key/value pair currently stored in the Map).
255 // Returns an Iterator referencing the first key/value pair in the Map.
256 // If no key/value pairs are currenly stored in the map, returns the
259 Iterator begin () const
261 return Iterator(&m_tree, m_tree.begin());
264 // end - Obtains an Iterator referencing the end of the Map. The end of
265 // the map does not reference an actual key/value pair. Instead it
266 // represents a "null" key/value pair which signifies the end (i.e. just
267 // beyond largest key/value pair currently stored in the Map). Also
268 // known as the "NULL" Iterator.
272 // Returns the "NULL" Iterator, signifying the end of the Map.
274 Iterator end () const
276 return Iterator(&m_tree, NULL);
279 // erase - Erases a key/value pair from the map.
281 // - it (IN): Iterator referencing the key/value pair to be erased from
288 VOID erase (Iterator& it)
290 m_tree.erase(it.m_node);
293 // erase - Erases a key/value pair from the map.
295 // - key (IN): The key corresponding to the key/value pair to be erased
302 VOID erase (const Tk &key)
304 m_tree.erase(Pair<Tk, Tv>(key, Tv()));
307 // find - Finds a key/value pair in the map.
309 // - key (IN): The key corresponding to the key/value pair to be found.
313 // Returns an Iterator referencing the found key/value pair. If no
314 // key/value pair with the specified key could be found, then the "NULL"
315 // Iterator is returned.
317 Iterator find (const Tk &key) const
319 return Iterator(&m_tree, m_tree.find(Pair<Tk, Tv>(key, Tv())));
322 // insert - Inserts a key/value pair into the map.
324 // - key (IN): The key of the key/value pair to be inserted.
326 // - data (IN): The value of the key/value pair to be inserted.
330 // Returns an Iterator referencing the resulting key/value pair after
331 // if has been inserted into the map.
333 Iterator insert (const Tk &key, const Tv &data)
335 return Iterator(&m_tree, m_tree.insert(Pair<Tk, Tv>(key, data)));
338 // reserve - Sets the reserve size of the map. The reserve size is the
339 // number of key/value pairs for which space should be pre-allocated
340 // to avoid frequent heap hits when inserting new key/value pairs into
343 // - count (IN): The number of key/value pairs for which to reserve space
348 // Returns the reserve size previously in use by the map.
350 size_t reserve (size_t count)
352 return m_tree.reserve(count);
357 Tree<Pair<Tk, Tv> > m_tree; // The key/value pairs are actually stored in a tree.