KiCad PCB EDA Suite
hashtables.h
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
5  * Copyright (C) 2012 KiCad Developers, see CHANGELOG.TXT for contributors.
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, you may find one here:
19  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20  * or you may search the http://www.gnu.org website for the version 2 license,
21  * or you may write to the Free Software Foundation, Inc.,
22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23  */
24 
25 #ifndef HASHTABLES_H_
26 #define HASHTABLES_H_
27 
28 #include <base_struct.h>
29 #include <wx/string.h>
30 
31 // Two competing strategies for providing portable hashtables are given:
32 // std C++ and boost.
33 
34 // First some utility classes and functions common to both strategies..
35 
37 struct iequal_to : std::binary_function< const char*, const char*, bool >
38 {
39  bool operator()( const char* x, const char* y ) const
40  {
41  return !strcmp( x, y );
42  }
43 };
44 
45 
49 struct fnv_1a
50 {
51  /* not used, std::string is too slow:
52  std::size_t operator()( std::string const& text ) const
53  {
54  std::size_t hash = 2166136261u;
55 
56  for( std::string::const_iterator it = text.begin(), end = text.end();
57  it != end; ++it )
58  {
59  hash ^= *it;
60  hash *= 16777619;
61  }
62  return hash;
63  }
64  */
65 
66  std::size_t operator()( const char* it ) const
67  {
68  std::size_t hash = 2166136261u;
69 
70  for( ; *it; ++it )
71  {
72  hash ^= (unsigned char) *it;
73  hash *= 16777619;
74  }
75  return hash;
76  }
77 };
78 
79 
81 struct WXSTRING_HASH : std::unary_function<wxString, std::size_t>
82 {
83  std::size_t operator()( const wxString& aString ) const
84  {
85  std::size_t hash = 2166136261u;
86 
87  for( wxString::const_iterator it = aString.begin(); it != aString.end(); ++it )
88  {
89  unsigned ch = static_cast<unsigned>( *it );
90  hash ^= ch;
91  hash *= 16777619;
92  }
93  return hash;
94  }
95 };
96 
97 
98 class NETINFO_ITEM;
99 
100 
101 #if 1 // C++ std::unordered_map, trying it now
102 
103 #include <unordered_map>
104 
105 
106 #ifdef SWIG
107 #define DECL_HASH_FOR_SWIG(TypeName, KeyType, ValueType) namespace std { %template(TypeName) unordered_map<KeyType, ValueType>; } typedef std::unordered_map<KeyType, ValueType> TypeName;
109 #else
110 #define DECL_HASH_FOR_SWIG(TypeName, KeyType, ValueType) typedef std::unordered_map<KeyType, ValueType> TypeName;
112 #endif
113 
114 
115 
132 typedef std::unordered_map< const char*, int, fnv_1a, iequal_to > KEYWORD_MAP;
133 
136 typedef std::unordered_map< std::string, EDA_RECT > RECT_MAP;
137 
138 
139 #elif 1 // boost::unordered_map
140 
141 // fix a compile bug at line 97 of boost/detail/container_fwd.hpp
142 #define BOOST_DETAIL_TEST_FORCE_CONTAINER_FWD
143 
144 #include <boost/unordered_map.hpp>
145 
146 // see http://www.boost.org/doc/libs/1_49_0/doc/html/boost/unordered_map.html
147 
148 
165 typedef boost::unordered_map< const char*, int, fnv_1a, iequal_to > KEYWORD_MAP;
166 
167 
170 typedef boost::unordered_map< std::string, EDA_RECT > RECT_MAP;
171 
172 typedef boost::unordered_map< const wxString, NETINFO_ITEM*, WXSTRING_HASH > NETNAMES_MAP;
173 typedef boost::unordered_map< const int, NETINFO_ITEM* > NETCODES_MAP;
174 
175 #endif
176 
177 #endif // HASHTABLES_H_
std::size_t operator()(const wxString &aString) const
Definition: hashtables.h:83
Equality test for "const char*" type used in very specialized KEYWORD_MAP below.
Definition: hashtables.h:37
std::unordered_map< const char *, int, fnv_1a, iequal_to > KEYWORD_MAP
Type KEYWORD_MAP is a hashtable made of a const char* and an int.
Definition: hashtables.h:132
Class NETINFO_ITEM handles the data for a net.
Definition: class_netinfo.h:69
std::size_t operator()(const char *it) const
Definition: hashtables.h:66
bool operator()(const char *x, const char *y) const
Definition: hashtables.h:39
Hash function for wxString, counterpart of std::string hash.
Definition: hashtables.h:81
Basic classes for most KiCad items.
Very fast and efficient hash function for "const char*" type, used in specialized KEYWORD_MAP below...
Definition: hashtables.h:49
std::unordered_map< std::string, EDA_RECT > RECT_MAP
Map a C string to an EDA_RECT.
Definition: hashtables.h:136