1 ////////////////////////////////////////////////////////////////////////////////
3 // Visual Leak Detector - Lightweight STL-like Map Template
4 // Copyright (c) 2006 Dan Moulding
6 // This library is free software; you can redistribute it and/or
7 // modify it under the terms of the GNU Lesser General Public
8 // License as published by the Free Software Foundation; either
9 // version 2.1 of the License, or (at your option) any later version.
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // Lesser General Public License for more details.
16 // You should have received a copy of the GNU Lesser General Public
17 // License along with this library; if not, write to the Free Software
18 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 // See COPYING.txt for the full terms of the GNU Lesser General Public License.
22 ////////////////////////////////////////////////////////////////////////////////
28 "This header should only be included by Visual Leak Detector when building it from source. \
29 Applications should never include this header."
32 #include "tree.h" // Provides access to the Tree template class.
34 ////////////////////////////////////////////////////////////////////////////////
36 // The Pair Template Class
38 // This is a lightweight STL-like pair template, for use with the lightweight
39 // Map class template.
41 // Note that while this is a STL-like class, it is not a full STL-compliant
42 // implementation of the STL pair utility class. It provides just the bare
43 // minimum functionality required by the Visual Leak Detector Map template
46 template <typename Tf, typename Ts>
56 // Constructor with initializers.
57 Pair (const Tf &f, const Ts &s)
63 // Less-than operator - Compares this Pair with another Pair to determine
64 // if this Pair is less than the other Pair. The Pair with the smallest
65 // "first" value is the lesser Pair.
67 // - other (IN): The other pair to compare against.
71 // Returns true if this Pair is less than the other Pair. Otherwise
74 BOOL operator < (const Pair &other) const
76 return (first < other.first);
80 Tf first; // The first value of the pair.
81 Ts second; // The second value of the pair.
84 ////////////////////////////////////////////////////////////////////////////////
86 // The Map Template Class
88 // This is a lightweidht STL-like map template. It makes use of the Tree class
89 // template to enable fast insert, find, and erase operations.
91 // Note that while this is a STL-like class, it is not a full STL-compliant
92 // implementation of the STL map container. It contains just the bare minimum
93 // functionality required by Visual Leak Detector. Because of its "lightweight"
94 // nature, this map class has a noticeable performance advantage over some
95 // other standard STL map implementations.
97 template <typename Tk, typename Tv>
105 // Plainly constructed iterators don't reference anything.
110 // operator != - Inequality operator for Map Iterators. Two Map
111 // Iterators are considered equal if and only if they both reference
112 // the same key/value pair in the same Map.
114 // - other (IN): The other Map Iterator to compare against.
118 // Returns true if the specified Map Iterator is not equal to this
119 // Map Iterator; otherwise, returns false.
121 BOOL operator != (const Iterator &other) const
123 return ((m_tree != other.m_tree) || (m_node != other.m_node));
126 // operator * - Dereference operator for Map Iterators.
128 // Note: The reference returned by this function is "const", so the
129 // value referenced by the Iterator may not be modified through the
130 // Iterator. This is a departure from STL iterator behavior.
132 // Also, dereferencing an Iterator which does not reference a valid
133 // value in the Map is undefined and will almost certainly cause a
138 // Returns a const reference to the key/value pair in the Map
139 // referenced by the Iterator.
141 const Pair<Tk, Tv>& operator * () const
146 // operator ++ - Prefix increment operator for Map Iterators. Causes the
147 // Iterator to reference the in-oder successor of the key/value pair
148 // currently referenced by the Iterator. If the Iterator is currently
149 // referencing the largest key/value pair in the Map, then the
150 // resulting Iterator will reference the Map's end (the NULL pair).
152 // Note: Incrementing an Iterator which does not reference a valid
153 // key/value pair in the Map is undefined and will almost certainly
158 // Returns the Iterator after it has been incremented.
160 Iterator& operator ++ (int)
162 m_node = m_tree->next(m_node);
166 // operator ++ - Postfix increment operator for Map Iterators. Causes
167 // the Iterator to reference the in-order successor of the key/value
168 // pair currently referenced by the Iterator. If the Iterator is
169 // currently referencing the largest key/value pair in the Map, then
170 // the resulting Iterator will reference the Map's end (the NULL
173 // Note: Incrementing an Iterator which does not reference a valid
174 // key/value pair in the Map is undefined and will almost certainly
179 // Returns the Iterator before it has been incremented.
181 Iterator operator ++ ()
183 typename Tree<Pair<Tk, Tv> >::node_t *cur = m_node;
185 m_node = m_tree->next(m_node);
186 return Iterator(m_tree, cur);
189 // operator - - Subtraction operator for Map Iterators. Causes the
190 // the Iterator to reference a key/value pair that is an in-order
191 // predecessor of the currently refereced key/value pair.
193 // - num (IN): Number indicating the number of preceding key/value
194 // pairs to decrement the iterator.
198 // Returns an Iterator referencing the key/value pair that precedes
199 // the original Iterator by "num" pairs.
201 Iterator operator - (SIZE_T num) const
204 typename Tree<Pair<Tk, Tv> >::node_t *cur = m_node;
206 cur = m_tree->prev(m_node);
207 for (count = 0; count < num; count++) {
208 cur = m_tree->prev(m_node);
210 return Iterator(m_tree, NULL);
213 return Iterator(m_tree, cur);
216 // operator == - Equality operator for Map Iterators. Map Iterators are
217 // considered equal if and only if they both refernce the same
218 // key/value pair in the same Map.
220 // - other (IN): The other Map Iterator to compare against.
224 // Returns true if the specified Map Iterator is equal to this Map
225 // Iterator; otherwise returns false.
227 BOOL operator == (const Iterator &other) const
229 return ((m_tree == other.m_tree) && (m_node == other.m_node));
233 // Private constructor. Only the Map class itself may use this
234 // constructor. It is used for constructing Iterators which reference
235 // specific nodes in the internal tree's structure.
236 Iterator (const Tree<Pair<Tk, Tv> > *tree, typename Tree<Pair<Tk, Tv> >::node_t *node)
242 typename Tree<Pair<Tk, Tv> >::node_t *m_node; // Pointer to the node referenced by the Map Iterator.
243 const Tree<Pair<Tk, Tv> > *m_tree; // Pointer to the tree containing the referenced node.
245 // The Map class is a friend of Map Iterators.
246 friend class Map<Tk, Tv>;
249 // begin - Obtains an Iterator referencing the beginning of the Map (i.e.
250 // the lowest key/value pair currently stored in the Map).
254 // Returns an Iterator referencing the first key/value pair in the Map.
255 // If no key/value pairs are currenly stored in the map, returns the
258 Iterator begin () const
260 return Iterator(&m_tree, m_tree.begin());
263 // end - Obtains an Iterator referencing the end of the Map. The end of
264 // the map does not reference an actual key/value pair. Instead it
265 // represents a "null" key/value pair which signifies the end (i.e. just
266 // beyond largest key/value pair currently stored in the Map). Also
267 // known as the "NULL" Iterator.
271 // Returns the "NULL" Iterator, signifying the end of the Map.
273 Iterator end () const
275 return Iterator(&m_tree, NULL);
278 // erase - Erases a key/value pair from the map.
280 // - it (IN): Iterator referencing the key/value pair to be erased from
287 VOID erase (Iterator& it)
289 m_tree.erase(it.m_node);
292 // erase - Erases a key/value pair from the map.
294 // - key (IN): The key corresponding to the key/value pair to be erased
301 VOID erase (const Tk &key)
303 m_tree.erase(Pair<Tk, Tv>(key, Tv()));
306 // find - Finds a key/value pair in the map.
308 // - key (IN): The key corresponding to the key/value pair to be found.
312 // Returns an Iterator referencing the found key/value pair. If no
313 // key/value pair with the specified key could be found, then the "NULL"
314 // Iterator is returned.
316 Iterator find (const Tk &key) const
318 return Iterator(&m_tree, m_tree.find(Pair<Tk, Tv>(key, Tv())));
321 // insert - Inserts a key/value pair into the map.
323 // - key (IN): The key of the key/value pair to be inserted.
325 // - data (IN): The value of the key/value pair to be inserted.
329 // Returns an Iterator referencing the resulting key/value pair after
330 // if has been inserted into the map.
332 Iterator insert (const Tk &key, const Tv &data)
334 return Iterator(&m_tree, m_tree.insert(Pair<Tk, Tv>(key, data)));
337 // reserve - Sets the reserve size of the map. The reserve size is the
338 // number of key/value pairs for which space should be pre-allocated
339 // to avoid frequent heap hits when inserting new key/value pairs into
342 // - count (IN): The number of key/value pairs for which to reserve space
347 // Returns the reserve size previously in use by the map.
349 size_t reserve (size_t count)
351 return m_tree.reserve(count);
356 Tree<Pair<Tk, Tv> > m_tree; // The key/value pairs are actually stored in a tree.