1 ////////////////////////////////////////////////////////////////////////////////
3 // Visual Leak Detector - Lightweight STL-like Set 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 Set Template Class
38 // This is a lightweight STL-like set template. It makes use of the Tree class
39 // template to enable fast insert, find, and erase operations.
41 // Note that while this is a STL-like class, it is not a full STL-compliant
42 // implementation of the STL set container. It contains just the bare minimum
43 // functionality required by Visual Leak Detector. Because of its "lightweight"
44 // nature, this set class has a noticeable performance advantage over some
45 // other standard STL set implementations.
47 template <typename Tk>
55 // Plainly constructed iterators don't reference anything.
60 // operator != - Inequality operator for Set Iterators. Two Set
61 // Iterators are considered equal if and only if they both reference
62 // the same key in the same Set.
64 // - other (IN): The other Set Iterator to compare against.
68 // Returns true if the specified Set Iterator is not equal to this
69 // Set Iterator; otherwise, returns false.
71 BOOL operator != (const Iterator &other) const
73 return ((m_tree != other.m_tree) || (m_node != other.m_node));
76 // operator * - Dereference operator for Set Iterators.
78 // Note: The reference returned by this function is "const", so the
79 // value referenced by the Iterator may not be modified through the
80 // Iterator. This is a departure from STL iterator behavior.
82 // Also, dereferencing an Iterator which does not reference a valid
83 // value in the Set is undefined and will almost certainly cause a
88 // Returns a const reference to the key in the Map referenced by the
91 const Tk& operator * () const
96 // operator ++ - Prefix increment operator for Set Iterators. Causes the
97 // Iterator to reference the in-oder successor of the key currently
98 // referenced by the Iterator. If the Iterator is currently
99 // referencing the largest key in the Map, then the resulting Iterator
100 // will reference the Set's end (the NULL pair).
102 // Note: Incrementing an Iterator which does not reference a valid
103 // key in the Set is undefined and will almost certainly cause a
108 // Returns the Iterator after it has been incremented.
110 Iterator& operator ++ (int)
112 m_node = m_tree->next(m_node);
116 // operator ++ - Postfix increment operator for Map Iterators. Causes
117 // the Iterator to reference the in-order successor of the key/value
118 // pair currently referenced by the Iterator. If the Iterator is
119 // currently referencing the largest key/value pair in the Map, then
120 // the resulting Iterator will reference the Map's end (the NULL
123 // Note: Incrementing an Iterator which does not reference a valid
124 // key/value pair in the Map is undefined and will almost certainly
129 // Returns the Iterator before it has been incremented.
131 Iterator operator ++ ()
133 typename Tree<Tk>::node_t *cur = m_node;
135 m_node = m_tree->next(m_node);
136 return Iterator(m_tree, cur);
139 // operator - - Subtraction operator for Set Iterators. Causes the
140 // the Iterator to reference a key that is an in-order predecessor of
141 // the currently refereced key.
143 // - num (IN): Number indicating the number of preceding keys to
144 // decrement the iterator.
148 // Returns an Iterator referencing the key that precedes the original
149 // Iterator by "num" keys.
151 Iterator operator - (SIZE_T num) const
154 typename Tree<Tk>::node_t *cur = m_node;
156 cur = m_tree->prev(m_node);
157 for (count = 0; count < num; count++) {
158 cur = m_tree->prev(m_node);
160 return Iterator(m_tree, NULL);
163 return Iterator(m_tree, cur);
166 // operator == - Equality operator for Set Iterators. Set Iterators are
167 // considered equal if and only if they both refernce the same
168 // key in the same Set.
170 // - other (IN): The other Set Iterator to compare against.
174 // Returns true if the specified Set Iterator is equal to this Set
175 // Iterator; otherwise returns false.
177 BOOL operator == (const Iterator &other) const
179 return ((m_tree == other.m_tree) && (m_node == other.m_node));
183 // Private constructor. Only the Set class itself may use this
184 // constructor. It is used for constructing Iterators which reference
185 // specific nodes in the internal tree's structure.
186 Iterator (const Tree<Tk> *tree, typename Tree<Tk>::node_t *node)
193 typename Tree<Tk>::node_t *m_node; // Pointer to the node referenced by the Set Iterator.
194 const Tree<Tk> *m_tree; // Pointer to the tree containing the referenced node.
196 // The Set class is a friend of Set Iterators.
197 friend class Set<Tk>;
200 // Muterator class - This class provides a mutable Iterator (the regular
201 // Iterators are const Iterators). By dereferencing a Muterator, you get
202 // a modifiable element.
204 // Caution: Modifing an element in a way that changes its sorting value
205 // will corrupt the Set container. Muterators should only be used when
206 // you are absolutely certain you will not be using it to make a
207 // modification that changes the sort order of the referenced element.
209 class Muterator : public Iterator
212 // operator = - Assignment operator for Set Muterators. Can be used to
213 // copy a Muterator from an existing Iterator, such that the Muterator
214 // references the same element referenced by the Iterator.
215 Muterator& operator = (const Iterator& other) {
216 *(Iterator*)this = other;
220 // operator * - Dereference operator for Set Muterators.
222 // Note: Dereferencing a Muterator which does not reference a valid
223 // value in the Set is undefined and will almost certainly cause a
228 // Returns a reference to the key in the Map referenced by the
237 // begin - Obtains an Iterator referencing the beginning of the Set (i.e.
238 // the lowest key currently stored in the Set).
242 // Returns an Iterator referencing the first key in the Set. If no keys
243 // are currenly stored in the Set, returns the "NULL" Iterator.
245 Iterator begin () const
247 return Iterator(&m_tree, m_tree.begin());
250 // end - Obtains an Iterator referencing the end of the Set. The end of
251 // the Set does not reference an actual key. Instead it represents a
252 // "null" key which signifies the end (i.e. just beyond largest key
253 // currently stored in the Set). Also known as the "NULL" Iterator.
257 // Returns the "NULL" Iterator, signifying the end of the Set.
259 Iterator end () const
261 return Iterator(&m_tree, NULL);
264 // erase - Erases a key from the Set.
266 // - it (IN): Iterator referencing the key to be erased from the Set.
272 VOID erase (Iterator& it)
274 m_tree.erase(it.m_node);
277 // erase - Erases a key from the Set.
279 // - key (IN): The key to be erased from the Set.
285 VOID erase (const Tk &key)
290 // find - Finds a key in the Set.
292 // - key (IN): The key to be found.
296 // Returns an Iterator referencing the found key. If the key could not
297 // be found, then the "NULL" Iterator is returned.
299 Iterator find (const Tk &key) const
301 return Iterator(&m_tree, m_tree.find(key));
304 // insert - Inserts a key into the Set.
306 // - key (IN): The key to be inserted.
310 // Returns an Iterator referencing the key after it has been inserted
311 // into the Set. If an element with an identical key value already exists
312 // in the Set, then the NULL Iterator is returned.
314 Iterator insert (const Tk &key)
316 return Iterator(&m_tree, m_tree.insert(key));
319 // reserve - Sets the reserve size of the Set. The reserve size is the
320 // number of keys for which space should be pre-allocated to avoid
321 // frequent heap hits when inserting new keys into the Set.
323 // - count (IN): The number of keys for which to reserve space in advance.
327 // Returns the reserve size previously in use by the Set.
329 size_t reserve (size_t count)
331 return m_tree.reserve(count);
336 Tree<Tk> m_tree; // The keys are actually stored in a tree.