Coverage Report

Created: 2023-12-08 06:53

/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