/src/freeimage-svn/FreeImage/trunk/Source/MapIntrospector.h
Line | Count | Source (jump to first uncovered line) |
1 | | // ========================================================== |
2 | | // STL MapIntrospector class |
3 | | // |
4 | | // Design and implementation by |
5 | | // - Carsten Klein (cklein05@users.sourceforge.net) |
6 | | // |
7 | | // This file is part of FreeImage 3 |
8 | | // |
9 | | // COVERED CODE IS PROVIDED UNDER THIS LICENSE ON AN "AS IS" BASIS, WITHOUT WARRANTY |
10 | | // OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, WITHOUT LIMITATION, WARRANTIES |
11 | | // THAT THE COVERED CODE IS FREE OF DEFECTS, MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE |
12 | | // OR NON-INFRINGING. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE COVERED |
13 | | // CODE IS WITH YOU. SHOULD ANY COVERED CODE PROVE DEFECTIVE IN ANY RESPECT, YOU (NOT |
14 | | // THE INITIAL DEVELOPER OR ANY OTHER CONTRIBUTOR) ASSUME THE COST OF ANY NECESSARY |
15 | | // SERVICING, REPAIR OR CORRECTION. THIS DISCLAIMER OF WARRANTY CONSTITUTES AN ESSENTIAL |
16 | | // PART OF THIS LICENSE. NO USE OF ANY COVERED CODE IS AUTHORIZED HEREUNDER EXCEPT UNDER |
17 | | // THIS DISCLAIMER. |
18 | | // |
19 | | // Use at your own risk! |
20 | | // ========================================================== |
21 | | |
22 | | #ifndef FREEIMAGE_MAPINTROSPECTOR_H_ |
23 | | #define FREEIMAGE_MAPINTROSPECTOR_H_ |
24 | | |
25 | | // we need at least one C++ header included, |
26 | | // that defines the C++ Standard Library's version macro, |
27 | | // that is used below to identify the library. |
28 | | #include <cstdlib> |
29 | | |
30 | | /** |
31 | | Class MapIntrospector - STL std::map Introspector |
32 | | |
33 | | The MapIntrospector is a helper class used to calculate or estimate part |
34 | | of the internal memory footprint of a std::map, that is the memory used |
35 | | by N entries, where N is provided as an argument. This class is used by |
36 | | function FreeImage_GetMemorySize, which aims to get the total memory |
37 | | usage for a FreeImage bitmap. |
38 | | |
39 | | The type argument _Maptype must take the type of the std::map to be |
40 | | introspected. |
41 | | |
42 | | This class accounts for 'internal' memory per entry only, that is, the |
43 | | size returned does neither include the actual size of the std::map class |
44 | | itself, nor does it include the size of referenced keys and values (also |
45 | | the actual bytes required for std::string type keys or values are not |
46 | | counted). For example, the total memory usage should be something like: |
47 | | |
48 | | typedef std::map<std::string, double> DBLMAP |
49 | | DBLMAP MyMap; |
50 | | |
51 | | int total_size = sizeof(DBLMAP) + MapIntrospector<DBLMAP>::GetNodesMemorySize(MyMap.size()) |
52 | | for (DBLMAP::iterator i = MyMap->begin(); i != MyMap->end(); i++) { |
53 | | std::string key = i->first; |
54 | | total_size += key.capacity(); |
55 | | } |
56 | | |
57 | | So, basically, this class' task is to get the (constant) number of bytes |
58 | | per entry, which is multiplied by N (parameter node_count) and returned |
59 | | in method GetNodesMemorySize. Since this heavily depends on the actually |
60 | | used C++ Standard Library, this class must be implemented specifically |
61 | | for each C++ Standard Library. |
62 | | |
63 | | At current, there is an implementation available for these C++ Standard |
64 | | Libraries: |
65 | | |
66 | | - Microsoft C++ Standard Library |
67 | | - GNU Standard C++ Library v3, libstdc++-v3 |
68 | | - LLVM "libc++" C++ Standard Library (untested) |
69 | | - Unknown C++ Standard Library |
70 | | |
71 | | Volunteers for testing as well as for providing support for other/new |
72 | | libraries are welcome. |
73 | | |
74 | | The 'Unknown C++ Standard Library' case is used if no other known C++ |
75 | | Standard Library was detected. It uses a typical _Node structure to |
76 | | declare an estimated memory consumption for a node. |
77 | | */ |
78 | | |
79 | | #if defined(_CPPLIB_VER) // Microsoft C++ Standard Library |
80 | | /** |
81 | | The Microsoft C++ Standard Library uses the protected structure _Node |
82 | | of class std::_Tree_nod to represent a node. This class is used by |
83 | | std::_Tree, the base class of std::map. So, since std::map is derived |
84 | | from std::_Tree (and _Node is protected), we can get access to this |
85 | | structure by deriving from std::map. |
86 | | |
87 | | Additionally, the Microsoft C++ Standard Library uses a separately |
88 | | allocated end node for its balanced red-black tree so, actually, there |
89 | | are size() + 1 nodes present in memory. |
90 | | |
91 | | With all that in place, the total memory for all nodes in std::map |
92 | | is simply (node_count + 1) * sizeof(_Node). |
93 | | */ |
94 | | template<class _Maptype> |
95 | | class MapIntrospector: private _Maptype { |
96 | | public: |
97 | | static size_t GetNodesMemorySize(size_t node_count) { |
98 | | return (node_count + 1) * sizeof(_Node); |
99 | | } |
100 | | }; |
101 | | |
102 | | #elif defined(__GLIBCXX__) // GNU Standard C++ Library v3, libstdc++-v3 |
103 | | /** |
104 | | The GNU Standard C++ Library v3 uses structure std::_Rb_tree_node<_Val>, |
105 | | which is publicly declared in the standard namespace. Its value type |
106 | | _Val is actually the map's value_type std::map::value_type. |
107 | | |
108 | | So, the total memory for all nodes in std::map is simply |
109 | | node_count * sizeof(std::_Rb_tree_node<_Val>), _Val being the map's |
110 | | value_type. |
111 | | */ |
112 | | template<class _Maptype> |
113 | | class MapIntrospector { |
114 | | private: |
115 | | typedef typename _Maptype::value_type _Val; |
116 | | |
117 | | public: |
118 | | static size_t GetNodesMemorySize(size_t node_count) { |
119 | | return node_count * sizeof(std::_Rb_tree_node<_Val>); |
120 | | } |
121 | | }; |
122 | | |
123 | | #elif defined(_LIBCPP_VERSION) // "libc++" C++ Standard Library (LLVM) |
124 | | /* |
125 | | The "libc++" C++ Standard Library uses structure |
126 | | std::__tree_node<_Val, void*> for regular nodes and one instance of |
127 | | structure std::__tree_end_node<void*> for end nodes, which both are |
128 | | publicly declared in the standard namespace. Its value type _Val is |
129 | | actually the map's value_type std::map::value_type. |
130 | | |
131 | | So, the total memory for all nodes in std::map is simply |
132 | | node_count * sizeof(std::__tree_node<_Val, void*>) |
133 | | + sizeof(std::__tree_end_node<void*>). |
134 | | |
135 | | REMARK: this implementation is not yet tested! |
136 | | */ |
137 | | template<class _Maptype> |
138 | | class MapIntrospector { |
139 | | private: |
140 | | typedef typename _Maptype::value_type _Val; |
141 | | |
142 | | public: |
143 | 0 | static size_t GetNodesMemorySize(size_t node_count) { |
144 | 0 | return node_count * sizeof(std::__tree_node<_Val, void*>) + sizeof(std::__tree_end_node<void*>); |
145 | 0 | } Unexecuted instantiation: MapIntrospector<std::__1::map<int, std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, FITAG*, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, FITAG*> > >*, std::__1::less<int>, std::__1::allocator<std::__1::pair<int const, std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, FITAG*, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, FITAG*> > >*> > > >::GetNodesMemorySize(unsigned long) Unexecuted instantiation: MapIntrospector<std::__1::map<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >, FITAG*, std::__1::less<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > >, std::__1::allocator<std::__1::pair<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const, FITAG*> > > >::GetNodesMemorySize(unsigned long) |
146 | | }; |
147 | | |
148 | | //#elif defined(_ADD_YOUR_CPP_STD_LIBRARY_HERE_) |
149 | | |
150 | | #else // Unknown C++ Standard Library |
151 | | /** |
152 | | If we do not know the actual C++ Standard Library and so, have no |
153 | | access to any internal types, we can just make some assumptions about |
154 | | the implementation and memory usage. |
155 | | |
156 | | However, all implementations will probably be based on a balanced |
157 | | red-black tree, will also store the map's value_type in each node and |
158 | | need some extra information like the node's color. For a binary tree, |
159 | | at least two pointers, one for left and one for right are required. |
160 | | Since it is handy, many implementations also have a parent pointer. |
161 | | |
162 | | We let the compiler calculate the size of the above mentioned items by |
163 | | using a fake structure. By using a real structure (in contrast to just |
164 | | adding numbers/bytes) we'll get correct pointer sizes as well as any |
165 | | padding applied for free. |
166 | | */ |
167 | | template<class _Maptype> |
168 | | class MapIntrospector { |
169 | | private: |
170 | | /* Define some handy typedefs to build up the structure. */ |
171 | | |
172 | | /** |
173 | | Each node will likely store the value_type of the mapping, |
174 | | that is a std::pair<_Key, _Value>. |
175 | | */ |
176 | | typedef typename _Maptype::value_type _Val; |
177 | | |
178 | | /** |
179 | | We will need some pointers, since std::map is likely implemented |
180 | | as a balanced red-black tree. |
181 | | */ |
182 | | typedef void* _Ptr; |
183 | | |
184 | | /** |
185 | | Space for some extra information (like the node's color). |
186 | | An int should be sufficient. |
187 | | */ |
188 | | typedef int _Ext; |
189 | | |
190 | | /* The memory required for each node will likely look like this |
191 | | structure. We will just multiply sizeof(_Node) by the number |
192 | | of nodes to get the total memory of all nodes. By using the |
193 | | size of the structure, we will also take care of the compiler's |
194 | | default padding. |
195 | | */ |
196 | | typedef struct { |
197 | | _Ptr _parent_node; |
198 | | _Ptr _left_node; |
199 | | _Ptr _right_node; |
200 | | _Val _value; |
201 | | _Ext _extra_info; |
202 | | } _Node; |
203 | | |
204 | | public: |
205 | | static size_t GetNodesMemorySize(size_t node_count) { |
206 | | return node_count * sizeof(_Node); |
207 | | } |
208 | | }; |
209 | | |
210 | | #endif // Standard C++ Library |
211 | | |
212 | | #endif // FREEIMAGE_MAPINTROSPECTOR_H_ |
213 | | |