1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
|
/*
* This program source code file is part of KiCad, a free EDA CAD application.
*
* Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
* Copyright (C) 2012 KiCad Developers, see CHANGELOG.TXT for contributors.
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, you may find one here:
* http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
* or you may search the http://www.gnu.org website for the version 2 license,
* or you may write to the Free Software Foundation, Inc.,
* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
*/
#ifndef HASHTABLES_H_
#define HASHTABLES_H_
#include <base_struct.h>
#include <wx/string.h>
// Two competing strategies for providing portable hashtables are given:
// std C++ and boost.
// First some utility classes and functions common to both strategies..
/// Equality test for "const char*" type used in very specialized KEYWORD_MAP below
struct iequal_to : std::binary_function< const char*, const char*, bool >
{
bool operator()( const char* x, const char* y ) const
{
return !strcmp( x, y );
}
};
/// Very fast and efficient hash function for "const char*" type, used in specialized
/// KEYWORD_MAP below.
/// taken from: http://www.boost.org/doc/libs/1_53_0/libs/unordered/examples/fnv1.hpp
struct fnv_1a
{
/* not used, std::string is too slow:
std::size_t operator()( std::string const& text ) const
{
std::size_t hash = 2166136261u;
for( std::string::const_iterator it = text.begin(), end = text.end();
it != end; ++it )
{
hash ^= *it;
hash *= 16777619;
}
return hash;
}
*/
std::size_t operator()( const char* it ) const
{
std::size_t hash = 2166136261u;
for( ; *it; ++it )
{
hash ^= (unsigned char) *it;
hash *= 16777619;
}
return hash;
}
};
/// Hash function for wxString, counterpart of std::string hash
struct WXSTRING_HASH : std::unary_function<wxString, std::size_t>
{
std::size_t operator()( const wxString& aString ) const
{
std::size_t hash = 2166136261u;
for( wxString::const_iterator it = aString.begin(); it != aString.end(); ++it )
{
unsigned ch = static_cast<unsigned>( *it );
hash ^= ch;
hash *= 16777619;
}
return hash;
}
};
class NETINFO_ITEM;
#if 1 // C++ std::unordered_map, trying it now
#include <unordered_map>
#ifdef SWIG
/// Declare a std::unordered_map and also the swig %template in unison
#define DECL_HASH_FOR_SWIG(TypeName, KeyType, ValueType) namespace std { %template(TypeName) unordered_map<KeyType, ValueType>; } typedef std::unordered_map<KeyType, ValueType> TypeName;
#else
/// Declare a std::unordered_map but no swig %template
#define DECL_HASH_FOR_SWIG(TypeName, KeyType, ValueType) typedef std::unordered_map<KeyType, ValueType> TypeName;
#endif
/**
* Type KEYWORD_MAP
* is a hashtable made of a const char* and an int. Note that use of this
* type outside very specific circumstances is foolish since there is no storage
* provided for the actual C string itself. This type assumes use with type KEYWORD
* that is created by CMake and that table creates *constant* storage for C strings
* (and pointers to those C strings). Here we are only interested in the C strings
* themselves and only the pointers are duplicated within the hashtable.
* If the strings were not constant and fixed, this type would not work.
* Also note that normally a hashtable (i.e. unordered_map) using a const char* key
* would simply compare the 32 bit or 64 bit pointers themselves, rather than
* the C strings which they are known to point to in this context.
* I force the latter behavior by supplying both "hash" and "equality" overloads
* to the hashtable (unordered_map) template.
* @author Dick Hollenbeck
*/
typedef std::unordered_map< const char*, int, fnv_1a, iequal_to > KEYWORD_MAP;
/// Map a C string to an EDA_RECT.
/// The key is the classname of the derived wxformbuilder dialog.
typedef std::unordered_map< std::string, EDA_RECT > RECT_MAP;
#elif 1 // boost::unordered_map
// fix a compile bug at line 97 of boost/detail/container_fwd.hpp
#define BOOST_DETAIL_TEST_FORCE_CONTAINER_FWD
#include <boost/unordered_map.hpp>
// see http://www.boost.org/doc/libs/1_49_0/doc/html/boost/unordered_map.html
/**
* Type KEYWORD_MAP
* is a hashtable made of a const char* and an int. Note that use of this
* type outside very specific circumstances is foolish since there is no storage
* provided for the actual C string itself. This type assumes use with type KEYWORD
* that is created by CMake and that table creates *constant* storage for C strings
* (and pointers to those C strings). Here we are only interested in the C strings
* themselves and only the pointers are duplicated within the hashtable.
* If the strings were not constant and fixed, this type would not work.
* Also note that normally a hashtable (i.e. unordered_map) using a const char* key
* would simply compare the 32 bit or 64 bit pointers themselves, rather than
* the C strings which they are known to point to in this context.
* I force the latter behavior by supplying both "hash" and "equality" overloads
* to the hashtable (unordered_map) template.
* @author Dick Hollenbeck
*/
typedef boost::unordered_map< const char*, int, fnv_1a, iequal_to > KEYWORD_MAP;
/// Map a std::string to an EDA_RECT.
/// The key is the classname of the derived wxformbuilder dialog.
typedef boost::unordered_map< std::string, EDA_RECT > RECT_MAP;
typedef boost::unordered_map< const wxString, NETINFO_ITEM*, WXSTRING_HASH > NETNAMES_MAP;
typedef boost::unordered_map< const int, NETINFO_ITEM* > NETCODES_MAP;
#endif
#endif // HASHTABLES_H_
|
