1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 // <unordered_map>
10
11 // template <class Key, class T, class Hash, class Pred, class Alloc>
12 // bool
13 // operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
14 // const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
15 //
16 // template <class Key, class T, class Hash, class Pred, class Alloc>
17 // bool
18 // operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
19 // const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
20
21 // Implements paper: http://wg21.link/p0809
22
23 #include <unordered_map>
24 #include <cassert>
25 #include <limits>
26 #include <cstddef>
27 #include <utility>
28 #include <functional>
29
30 template <class T>
hash_identity(T val)31 std::size_t hash_identity(T val) {
32 return val;
33 }
34 template <class T>
hash_neg(T val)35 std::size_t hash_neg(T val) {
36 return std::numeric_limits<T>::max() - val;
37 }
38 template <class T>
hash_scale(T val)39 std::size_t hash_scale(T val) {
40 return static_cast<std::size_t>(val << 1);
41 }
42 template <class T>
hash_even(T val)43 std::size_t hash_even(T val) {
44 return val & 1 ? 1 : 0;
45 }
46 template <class T>
hash_same(T)47 std::size_t hash_same(T /*val*/) {
48 return 1;
49 }
50
51 template <class T>
hash_identity(T * val)52 std::size_t hash_identity(T* val) {
53 return *val;
54 }
55 template <class T>
hash_neg(T * val)56 std::size_t hash_neg(T* val) {
57 return std::numeric_limits<T>::max() - *val;
58 }
59 template <class T>
hash_scale(T * val)60 std::size_t hash_scale(T* val) {
61 return static_cast<std::size_t>(*val << 1);
62 }
63 template <class T>
hash_even(T * val)64 std::size_t hash_even(T* val) {
65 return *val & 1 ? 1 : 0;
66 }
67
68 template <class Map, class Ittr>
populate(Map & m,Ittr start,Ittr end)69 void populate(Map& m, Ittr start, Ittr end) {
70 for (auto *p1 = start, *p2 = end - 1; p1 != end; ++p1, --p2) {
71 m.insert(std::make_pair(*p1, *p2));
72 }
73 }
74
75 template <class T, std::size_t N>
test(T (& vals)[N])76 void test(T (&vals)[N]) {
77 using Hash = std::size_t (*)(T);
78 using C = std::unordered_multimap<T, T, Hash, std::equal_to<T> >;
79
80 C c1(0, hash_identity);
81 C c2(0, hash_neg);
82 C c3(0, hash_scale);
83 C c4(0, hash_even);
84 C c5(0, hash_same);
85
86 populate(c1, std::begin(vals), std::end(vals));
87 populate(c2, std::begin(vals), std::end(vals));
88 populate(c3, std::begin(vals), std::end(vals));
89 populate(c4, std::begin(vals), std::end(vals));
90 populate(c5, std::begin(vals), std::end(vals));
91
92 assert(c1 == c1);
93 assert(c1 == c2);
94 assert(c1 == c3);
95 assert(c1 == c4);
96 assert(c1 == c5);
97
98 assert(c2 == c1);
99 assert(c2 == c2);
100 assert(c2 == c3);
101 assert(c2 == c4);
102 assert(c2 == c5);
103
104 assert(c3 == c1);
105 assert(c3 == c2);
106 assert(c3 == c3);
107 assert(c3 == c4);
108 assert(c3 == c5);
109
110 assert(c4 == c1);
111 assert(c4 == c2);
112 assert(c4 == c3);
113 assert(c4 == c4);
114 assert(c4 == c5);
115
116 assert(c5 == c1);
117 assert(c5 == c2);
118 assert(c5 == c3);
119 assert(c5 == c4);
120 assert(c5 == c5);
121 }
122
main(int,char **)123 int main(int, char**) {
124 {
125 std::size_t vals[] = {
126 // clang-format off
127 1,
128 2, 2,
129 3, 3, 3,
130 4, 4, 4, 4,
131 5, 5, 5, 5, 5,
132 6, 6, 6, 6, 6, 6,
133 7, 7, 7, 7, 7, 7, 7,
134 8, 8, 8, 8, 8, 8, 8, 8,
135 9, 9, 9, 9, 9, 9, 9, 9, 9,
136 10
137 // clang-format on
138 };
139 test(vals);
140 }
141 {
142 bool vals[] = {true, false};
143 test(vals);
144 }
145 {
146 char* vals[] = {(char*)("a"), (char*)("b"), (char*)("cde")};
147 test(vals);
148 }
149
150 return 0;
151 }
152