Line data Source code
1 : /*
2 : This file is part of cpp-ethereum.
3 :
4 : cpp-ethereum is free software: you can redistribute it and/or modify
5 : it under the terms of the GNU General Public License as published by
6 : the Free Software Foundation, either version 3 of the License, or
7 : (at your option) any later version.
8 :
9 : cpp-ethereum is distributed in the hope that it will be useful,
10 : but WITHOUT ANY WARRANTY; without even the implied warranty of
11 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 : GNU General Public License for more details.
13 :
14 : You should have received a copy of the GNU General Public License
15 : along with cpp-ethereum. If not, see <http://www.gnu.org/licenses/>.
16 : */
17 : /** @file CommonData.h
18 : * @author Gav Wood <i@gavwood.com>
19 : * @date 2014
20 : *
21 : * Shared algorithms and data types.
22 : */
23 :
24 : #pragma once
25 :
26 : #include <vector>
27 : #include <algorithm>
28 : #include <unordered_set>
29 : #include <type_traits>
30 : #include <cstring>
31 : #include <string>
32 : #include "Common.h"
33 :
34 : namespace dev {
35 :
36 : // String conversion functions, mainly to/from hex/nibble/byte representations.
37 :
38 : enum class WhenError {
39 : DontThrow = 0,
40 : Throw = 1,
41 : };
42 :
43 : template<class Iterator>
44 : std::string
45 776 : toHex(Iterator _it, Iterator _end, std::string _prefix)
46 : {
47 : typedef std::iterator_traits<Iterator> traits;
48 : static_assert(sizeof(typename traits::value_type) == 1, "toHex needs byte-sized element type");
49 :
50 : static char const* hexdigits = "0123456789abcdef";
51 776 : size_t off = _prefix.size();
52 776 : std::string hex(std::distance(_it, _end) * 2 + off, '0');
53 776 : hex.replace(0, off, _prefix);
54 16296 : for (; _it != _end; _it++) {
55 15520 : hex[off++] = hexdigits[(*_it >> 4) & 0x0f];
56 15520 : hex[off++] = hexdigits[*_it & 0x0f];
57 : }
58 776 : return hex;
59 0 : }
60 :
61 : /// Convert a series of bytes to the corresponding hex string.
62 : /// @example toHex("A\x69") == "4169"
63 : template<class T>
64 : std::string
65 776 : toHex(T const& _data)
66 : {
67 1552 : return toHex(_data.begin(), _data.end(), "");
68 : }
69 :
70 : /// Convert a series of bytes to the corresponding hex string with 0x prefix.
71 : /// @example toHexPrefixed("A\x69") == "0x4169"
72 : template<class T>
73 : std::string
74 : toHexPrefixed(T const& _data)
75 : {
76 : return toHex(_data.begin(), _data.end(), "0x");
77 : }
78 :
79 : /// Converts a (printable) ASCII hex string into the corresponding byte stream.
80 : /// @example fromHex("41626261") == asBytes("Abba")
81 : /// If _throw = ThrowType::DontThrow, it replaces bad hex characters with 0's, otherwise it will
82 : /// throw an exception.
83 : bytes fromHex(std::string const& _s, WhenError _throw = WhenError::DontThrow);
84 :
85 : /// @returns true if @a _s is a hex string.
86 : bool isHex(std::string const& _s) noexcept;
87 :
88 : /// @returns true if @a _hash is a hash conforming to FixedHash type @a T.
89 : template<class T>
90 : static bool
91 : isHash(std::string const& _hash)
92 : {
93 : return (_hash.size() == T::size * 2 || (_hash.size() == T::size * 2 + 2 && _hash.substr(0, 2) == "0x"))
94 : && isHex(_hash);
95 : }
96 :
97 : /// Converts byte array to a string containing the same (binary) data. Unless
98 : /// the byte array happens to contain ASCII data, this won't be printable.
99 : inline std::string
100 : asString(bytes const& _b)
101 : {
102 : return std::string((char const*) _b.data(), (char const*) (_b.data() + _b.size()));
103 : }
104 :
105 : /// Converts byte array ref to a string containing the same (binary) data. Unless
106 : /// the byte array happens to contain ASCII data, this won't be printable.
107 : inline std::string
108 : asString(bytesConstRef _b)
109 : {
110 : return std::string((char const*) _b.data(), (char const*) (_b.data() + _b.size()));
111 : }
112 :
113 : /// Converts a string to a byte array containing the string's (byte) data.
114 : inline bytes
115 0 : asBytes(std::string const& _b)
116 : {
117 0 : return bytes((uint8_t const*) _b.data(), (uint8_t const*) (_b.data() + _b.size()));
118 : }
119 :
120 : /// Converts a string into the big-endian base-16 stream of integers (NOT ASCII).
121 : /// @example asNibbles("A")[0] == 4 && asNibbles("A")[1] == 1
122 : bytes asNibbles(bytesConstRef const& _s);
123 :
124 : // Big-endian to/from host endian conversion functions.
125 :
126 : /// Converts a big-endian byte-stream represented on a templated collection to a templated integer
127 : /// value.
128 : /// @a _In will typically be either std::string or bytes.
129 : /// @a T will typically by unsigned, u160, u256 or bigint.
130 : template<class T, class _In>
131 : inline T
132 : fromBigEndian(_In const& _bytes)
133 : {
134 : T ret = (T) 0;
135 : for (auto i : _bytes)
136 : ret = (T) ((ret << 8) | (uint8_t) (typename std::make_unsigned<decltype(i)>::type) i);
137 : return ret;
138 : }
139 :
140 : inline bytes
141 : toCompactBigEndian(uint8_t _val, unsigned _min = 0)
142 : {
143 : return (_min || _val) ? bytes {_val} : bytes {};
144 : }
145 :
146 : // Algorithms for string and string-like collections.
147 :
148 : /// Determines the length of the common prefix of the two collections given.
149 : /// @returns the number of elements both @a _t and @a _u share, in order, at the beginning.
150 : /// @example commonPrefix("Hello world!", "Hello, world!") == 5
151 : template<class T, class _U>
152 : unsigned
153 : commonPrefix(T const& _t, _U const& _u)
154 : {
155 : unsigned s = std::min<unsigned>(_t.size(), _u.size());
156 : for (unsigned i = 0;; ++i)
157 : if (i == s || _t[i] != _u[i])
158 : return i;
159 : return s;
160 : }
161 :
162 : /// Trims a given number of elements from the front of a collection.
163 : /// Only works for POD element types.
164 : template<class T>
165 : void
166 : trimFront(T& _t, unsigned _elements)
167 : {
168 : static_assert(std::is_pod<typename T::value_type>::value, "");
169 : memmove(_t.data(), _t.data() + _elements, (_t.size() - _elements) * sizeof(_t[0]));
170 : _t.resize(_t.size() - _elements);
171 : }
172 :
173 : /// Pushes an element on to the front of a collection.
174 : /// Only works for POD element types.
175 : template<class T, class _U>
176 : void
177 : pushFront(T& _t, _U _e)
178 : {
179 : static_assert(std::is_pod<typename T::value_type>::value, "");
180 : _t.push_back(_e);
181 : memmove(_t.data() + 1, _t.data(), (_t.size() - 1) * sizeof(_e));
182 : _t[0] = _e;
183 : }
184 :
185 : /// Concatenate two vectors of elements of POD types.
186 : template<class T>
187 : inline std::vector<T>&
188 : operator+=(std::vector<typename std::enable_if<std::is_pod<T>::value, T>::type>& _a, std::vector<T> const& _b)
189 : {
190 : auto s = _a.size();
191 : _a.resize(_a.size() + _b.size());
192 : memcpy(_a.data() + s, _b.data(), _b.size() * sizeof(T));
193 : return _a;
194 : }
195 :
196 : /// Concatenate two vectors of elements.
197 : template<class T>
198 : inline std::vector<T>&
199 : operator+=(std::vector<typename std::enable_if<!std::is_pod<T>::value, T>::type>& _a, std::vector<T> const& _b)
200 : {
201 : _a.reserve(_a.size() + _b.size());
202 : for (auto& i : _b)
203 : _a.push_back(i);
204 : return _a;
205 : }
206 :
207 : /// Insert the contents of a container into a set
208 : template<class T, class U>
209 : std::set<T>&
210 : operator+=(std::set<T>& _a, U const& _b)
211 : {
212 : for (auto const& i : _b)
213 : _a.insert(i);
214 : return _a;
215 : }
216 :
217 : /// Insert the contents of a container into an unordered_set
218 : template<class T, class U>
219 : std::unordered_set<T>&
220 : operator+=(std::unordered_set<T>& _a, U const& _b)
221 : {
222 : for (auto const& i : _b)
223 : _a.insert(i);
224 : return _a;
225 : }
226 :
227 : /// Concatenate the contents of a container onto a vector
228 : template<class T, class U>
229 : std::vector<T>&
230 : operator+=(std::vector<T>& _a, U const& _b)
231 : {
232 : for (auto const& i : _b)
233 : _a.push_back(i);
234 : return _a;
235 : }
236 :
237 : /// Insert the contents of a container into a set
238 : template<class T, class U>
239 : std::set<T>
240 : operator+(std::set<T> _a, U const& _b)
241 : {
242 : return _a += _b;
243 : }
244 :
245 : /// Insert the contents of a container into an unordered_set
246 : template<class T, class U>
247 : std::unordered_set<T>
248 : operator+(std::unordered_set<T> _a, U const& _b)
249 : {
250 : return _a += _b;
251 : }
252 :
253 : /// Concatenate the contents of a container onto a vector
254 : template<class T, class U>
255 : std::vector<T>
256 : operator+(std::vector<T> _a, U const& _b)
257 : {
258 : return _a += _b;
259 : }
260 :
261 : /// Concatenate two vectors of elements.
262 : template<class T>
263 : inline std::vector<T>
264 : operator+(std::vector<T> const& _a, std::vector<T> const& _b)
265 : {
266 : std::vector<T> ret(_a);
267 : return ret += _b;
268 : }
269 :
270 : template<class T, class U>
271 : std::vector<T>
272 : keysOf(std::map<T, U> const& _m)
273 : {
274 : std::vector<T> ret;
275 : for (auto const& i : _m)
276 : ret.push_back(i.first);
277 : return ret;
278 : }
279 :
280 : template<class T, class U>
281 : std::vector<T>
282 : keysOf(std::unordered_map<T, U> const& _m)
283 : {
284 : std::vector<T> ret;
285 : for (auto const& i : _m)
286 : ret.push_back(i.first);
287 : return ret;
288 : }
289 :
290 : template<class T, class U>
291 : std::vector<U>
292 : valuesOf(std::map<T, U> const& _m)
293 : {
294 : std::vector<U> ret;
295 : ret.reserve(_m.size());
296 : for (auto const& i : _m)
297 : ret.push_back(i.second);
298 : return ret;
299 : }
300 :
301 : template<class T, class U>
302 : std::vector<U>
303 : valuesOf(std::unordered_map<T, U> const& _m)
304 : {
305 : std::vector<U> ret;
306 : ret.reserve(_m.size());
307 : for (auto const& i : _m)
308 : ret.push_back(i.second);
309 : return ret;
310 : }
311 :
312 : template<class T, class V>
313 : bool
314 : contains(T const& _t, V const& _v)
315 : {
316 : return std::end(_t) != std::find(std::begin(_t), std::end(_t), _v);
317 : }
318 :
319 : } // namespace dev
|
