OLD | NEW |
1 /* | 1 /* |
2 * This file is part of Adblock Plus <https://adblockplus.org/>, | 2 * This file is part of Adblock Plus <https://adblockplus.org/>, |
3 * Copyright (C) 2006-present eyeo GmbH | 3 * Copyright (C) 2006-present eyeo GmbH |
4 * | 4 * |
5 * Adblock Plus is free software: you can redistribute it and/or modify | 5 * Adblock Plus is free software: you can redistribute it and/or modify |
6 * it under the terms of the GNU General Public License version 3 as | 6 * it under the terms of the GNU General Public License version 3 as |
7 * published by the Free Software Foundation. | 7 * published by the Free Software Foundation. |
8 * | 8 * |
9 * Adblock Plus is distributed in the hope that it will be useful, | 9 * Adblock Plus is distributed in the hope that it will be useful, |
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of | 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
12 * GNU General Public License for more details. | 12 * GNU General Public License for more details. |
13 * | 13 * |
14 * You should have received a copy of the GNU General Public License | 14 * You should have received a copy of the GNU General Public License |
15 * along with Adblock Plus. If not, see <http://www.gnu.org/licenses/>. | 15 * along with Adblock Plus. If not, see <http://www.gnu.org/licenses/>. |
16 */ | 16 */ |
17 | 17 |
18 #pragma once | 18 #pragma once |
19 | 19 |
20 #include <cstddef> | 20 #include <cstddef> |
21 | 21 |
22 #include "Map.h" | 22 #include "Map.h" |
23 #include "String.h" | 23 #include "String.h" |
24 | 24 |
| 25 namespace { |
| 26 size_t stringHash(const String& key) |
| 27 { |
| 28 // FNV-1a hash function |
| 29 size_t result = 2166136261; |
| 30 for (size_t i = 0; i < key.length(); i++) |
| 31 result = (result ^ key[i]) * 16777619; |
| 32 return result; |
| 33 } |
| 34 } |
| 35 |
| 36 struct StringHash |
| 37 { |
| 38 size_t operator()(const String& key) const |
| 39 { |
| 40 return stringHash(key); |
| 41 } |
| 42 }; |
| 43 |
25 namespace StringMap_internal | 44 namespace StringMap_internal |
26 { | 45 { |
27 template<typename Key, | 46 template<typename Key, |
28 class = typename std::enable_if<std::is_base_of<String, Key>::value>::type> | 47 class = typename std::enable_if<std::is_base_of<String, Key>::value>::type> |
29 struct StringSetEntry | 48 struct StringSetEntry |
30 { | 49 { |
31 typedef Key key_type; | 50 typedef Key key_type; |
32 typedef const String& key_type_cref; | 51 typedef const String& key_type_cref; |
33 typedef size_t size_type; | 52 typedef size_t size_type; |
34 | 53 |
(...skipping 20 matching lines...) Expand all Loading... |
55 return first.is_deleted(); | 74 return first.is_deleted(); |
56 } | 75 } |
57 | 76 |
58 void erase() | 77 void erase() |
59 { | 78 { |
60 first.erase(); | 79 first.erase(); |
61 } | 80 } |
62 | 81 |
63 static size_type hash(key_type_cref key) | 82 static size_type hash(key_type_cref key) |
64 { | 83 { |
65 // FNV-1a hash function | 84 return stringHash(key); |
66 size_type result = 2166136261; | |
67 for (String::size_type i = 0; i < key.length(); i++) | |
68 result = (result ^ key[i]) * 16777619; | |
69 return result; | |
70 } | 85 } |
71 }; | 86 }; |
72 | 87 |
73 template<typename Key, typename Value> | 88 template<typename Key, typename Value> |
74 struct StringMapEntry : StringSetEntry<Key> | 89 struct StringMapEntry : StringSetEntry<Key> |
75 { | 90 { |
76 typedef StringSetEntry<Key> super; | 91 typedef StringSetEntry<Key> super; |
77 typedef Value value_type; | 92 typedef Value value_type; |
78 | 93 |
79 value_type second; | 94 value_type second; |
(...skipping 11 matching lines...) Expand all Loading... |
91 } | 106 } |
92 }; | 107 }; |
93 } | 108 } |
94 | 109 |
95 using StringSet = Set<StringMap_internal::StringSetEntry<DependentString>>; | 110 using StringSet = Set<StringMap_internal::StringSetEntry<DependentString>>; |
96 | 111 |
97 template<typename Value> | 112 template<typename Value> |
98 using StringMap = Map<StringMap_internal::StringMapEntry<DependentString, Value>
>; | 113 using StringMap = Map<StringMap_internal::StringMapEntry<DependentString, Value>
>; |
99 template<typename Value> | 114 template<typename Value> |
100 using OwnedStringMap = Map<StringMap_internal::StringMapEntry<OwnedString, Value
>>; | 115 using OwnedStringMap = Map<StringMap_internal::StringMapEntry<OwnedString, Value
>>; |
OLD | NEW |