Comparing Unordered Containers (P0809)

[ldionne]

Summary

This patch implements P0809 to add support for comparing unordered containers. It also fixes issues with the current implementations.

[zoecarver]

Maybe I should add some fail tests for pre-c++20?

include/unordered_map

1641 ↗

(On Diff #198960)

Was it ever necessary for the two maps to use the same allocator type (and is it now)? Furthermore, is it even necessary for them to have the same key/value type (I don't see anything in the standard that explicitly says they need to be)?

1690 ↗

(On Diff #198960)

I can add some tests for this. Wanted to make sure it is correct first.

[mclow.lists]

include/unordered_map

1641 ↗

(On Diff #198960)

All the container comparisons in the standard are defined in terms of comparing two containers of the same type. For allocator-aware containers, this includes the allocators. There is a proposal to relax that in flight (https://wg21.link/P0805), but I don't think that will be part of C++20.

My suggestion is to not support heterogenous comparisons at this time.
Note that this includes the hasher as well as the predicate and the allocator.

test/std/containers/unord/unord.map/comp_different_hash.pass.cpp

34 ↗

(On Diff #198960)

I don't think that this is what P0809 meant. "Hashes with different behavior", yes.
"Hashes of different types", no.

[mclow.lists]

include/unordered_map

1690 ↗

(On Diff #198960)

I like this implementation. It's straightforward, easy to read, and looks correct.
I'm still working through the complexity, though.

[mclow.lists]

include/unordered_map

1656 ↗

(On Diff #198960)

This can be simplified for unordered_map, because unordered_map requires unique keys.

You can just use __y.find instead of equal_range and a single (Still need equal_range etc for unordered_multimap, though)

include/unordered_set

968 ↗

(On Diff #198960)

Like the unordered_map code, this can be made much simpler because there are unique keys.

1006 ↗

(On Diff #198960)

No need for is_permutation, again.

[zoecarver]

include/unordered_map

1641 ↗

(On Diff #198960)

I will keep an eye on that paper. As per your below comment, I will get rid of this.

1656 ↗

(On Diff #198960)

Good idea! I will change this.

include/unordered_set

968 ↗

(On Diff #198960)

Good catch. Will update (same with plain unordered_set).

1006 ↗

(On Diff #198960)

The standard specifically says to use is_permutation (for both set and multiset, etc.).

test/std/containers/unord/unord.map/comp_different_hash.pass.cpp

34 ↗

(On Diff #198960)

While the paper doesn't explain it specifically, I think you are right. Because of the part that is removed which defines the behavior and not type. I can update it :P

[mclow.lists]

include/unordered_set

1006 ↗

(On Diff #198960)

Yeah, I see that. I'm reviewing that and the original papers. I'll get back to you.

[mclow.lists]

I (now) realize that I'm giving you inconsistent advice. (re is_permutation and the non-multi containers).
Sorry about that; I'll get back to you on that after some research.

[zoecarver]

• remove paper changes (until I re-implement them)
• use find instead of is_permutation

[zoecarver]

• use plain is_permutation
• fix template name

[zoecarver]

include/unordered_map

2274 ↗

(On Diff #199147)

From my tests, simply using is_permutation here is quite a bit faster than the previous method of comparison. I think that both bits of code are functionally equivalent (but let me know if that is not the case).

[zoecarver]

• remove all modification to unordered_{set,map}
• add tests

Thank you @mclow.lists for writing most of the tests below.

[mclow.lists]

I know that Louis and Eric disagree, but I'd rather have four tests, one for each of the unordered containers, rather than just one.
(unless someone wants to step up and re-do all the container tests, and I'm not hearing any enthusiasm for that).

test/std/containers/unord/comp_different_hash.pass.cpp

49 ↗

(On Diff #199353)

I don't think that this does what what you want anymore.

71 ↗

(On Diff #199353)

The first time through the loop you are dereferencing p2, which is equal to end.

[zoecarver]

I can do that so all the tests are "uniform".

test/std/containers/unord/comp_different_hash.pass.cpp

49 ↗

(On Diff #199353)

You meant I should use std::numeric_limits<T>::max()?

71 ↗

(On Diff #199353)

Good catch. Fixed.

[zoecarver]

• split up tests
• fix test issues

[zoecarver]

Updated status. Let's land this :)

[zoecarver]

Ping. This is a NFC.

[curdeius]

It would be cool to land it. I know that Arthur marked it as "Nothing To Do" already, but to the best of my knowledge there are no tests for that. And your tests seem exhaustive.

Nit: in the summary, the phrase "It also fixes issues with the current implementations." seems outdated.

libcxx/test/std/containers/unord/unord.set/comp_different_hash.pass.cpp

106 ↗

(On Diff #215799)

For completeness, you should test operator!= as well (here and in other tests).

[• Quuxplusone]

libcxx/test/std/containers/unord/unord.set/comp_different_hash.pass.cpp

64 ↗

(On Diff #215799)

FWIW, I'd rather see something simpler here. As simple as providing hash_mod_two { return val % 2; } and hash_mod_three { return val % 3; }. I don't think it buys anything to have 5 different hashes as opposed to 2, nor to have partial specializations for T* of which the only one that's used is T=char.
I don't even see any reason to test char*, so I'd remove all that; but if there's any value in keeping it, then there should be a reason for c_vals[2] to be "cde" and not just "c".

In fact I think the whole void test() could be just [WARNING: UNTESTED CODE]

using Hash = int(*)(T);
std::unordered_set<int, Hash> c1({1, 2, 3, 4, 6, 7, 8}, 0, +[](int x) { return x % 2; });
std::unordered_set<int, Hash> c2({1, 2, 3, 4, 6, 7, 8}, 0, +[](int x) { return x % 3; });
std::unordered_set<int, Hash> c3({1, 2, 3, 5, 6, 7, 8}, 0, +[](int x) { return x % 3; });
assert(!std::equal(c1.begin(), c1.end(), c2.begin(), c2.end()));
assert(std::is_permutation(c1.begin(), c1.end(), c2.begin(), c2.end()));
assert(c1 == c2);
assert(!(c1 != c2));
assert(!std::is_permutation(c1.begin(), c1.end(), c3.begin(), c3.end()));
assert(c1 != c3);
assert(!(c1 == c3));

followed by a test for non-default equivalence predicate:

struct EqualMod6 { bool operator(int x, int y) const { return x % 6 == y % 6; } };
using Hash = int(*)(T);
std::unordered_set<int, Hash, EqualMod6> c1({1, 2, 3, 4, 6}, 0, +[](int x) { return x % 2; });
std::unordered_set<int, Hash, EqualMod6> c2({1, 8, 9, 4, 6}, 0, +[](int x) { return x % 3; });
assert(!std::equal(c1.begin(), c1.end(), c2.begin(), c2.end()));
assert(!std::is_permutation(c1.begin(), c1.end(), c2.begin(), c2.end()));
assert(!std::equal(c1.begin(), c1.end(), c2.begin(), c2.end(), EqualMod6()));
assert(std::is_permutation(c1.begin(), c1.end(), c2.begin(), c2.end(), EqualMod6()));
assert(c1 == c2);
assert(!(c1 != c2));

( https://en.cppreference.com/w/cpp/container/unordered_set/operator_cmp is pretty ugly but I think it makes sense what it's saying.)

[ldionne]

Rebase and fix a few things.

[ldionne]

Fix >> issue in C++03 mode. Small consistency fixes.

[ldionne]

Poke CI.

[ldionne]

CI passed, but the Phab reporting is still broken.

libcxx/test/std/containers/unord/unord.map/eq.different_hash.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <unordered_map>
+
+// template <class Key, class T, class Hash, class Pred, class Alloc>
+// bool
+// operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
+//            const unordered_map<Key, T, Hash, Pred, Alloc>& y);
+//
+// template <class Key, class T, class Hash, class Pred, class Alloc>
+// bool
+// operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
+//            const unordered_map<Key, T, Hash, Pred, Alloc>& y);
+
+// Implements paper: http://wg21.link/p0809
+
+#include <unordered_map>
+#include <cstddef>
+#include <limits>
+#include <cassert>
+#include <functional>
+
+template <class T>
+std::size_t hash_identity(T val) {
+  return val;
+}
+template <class T>
+std::size_t hash_neg(T val) {
+  return std::numeric_limits<T>::max() - val;
+}
+template <class T>
+std::size_t hash_scale(T val) {
+  return val << 1;
+}
+template <class T>
+std::size_t hash_even(T val) {
+  return val & 1 ? 1 : 0;
+}
+template <class T>
+std::size_t hash_same(T /*val*/) {
+  return 1;
+}
+
+template <class T>
+std::size_t hash_identity(T* val) {
+  return *val;
+}
+template <class T>
+std::size_t hash_neg(T* val) {
+  return std::numeric_limits<T>::max() - *val;
+}
+template <class T>
+std::size_t hash_scale(T* val) {
+  return *val << 1;
+}
+template <class T>
+std::size_t hash_even(T* val) {
+  return *val & 1 ? 1 : 0;
+}
+
+template <class Map, class Ittr>
+void populate(Map& m, Ittr start, Ittr end) {
+  for (auto *p1 = start, *p2 = end - 1; p1 != end; ++p1, --p2) {
+    m.insert(std::make_pair(*p1, *p2));
+  }
+}
+
+template <class T, std::size_t N>
+void test(T (&vals)[N]) {
+  using Hash = std::size_t (*)(T);
+  using C    = std::unordered_map<T, T, Hash, std::equal_to<T> >;
+
+  C c1(0, hash_identity);
+  C c2(0, hash_neg);
+  C c3(0, hash_scale);
+  C c4(0, hash_even);
+  C c5(0, hash_same);
+
+  populate(c1, std::begin(vals), std::end(vals));
+  populate(c2, std::begin(vals), std::end(vals));
+  populate(c3, std::begin(vals), std::end(vals));
+  populate(c4, std::begin(vals), std::end(vals));
+  populate(c5, std::begin(vals), std::end(vals));
+
+  assert(c1 == c1);
+  assert(c1 == c2);
+  assert(c1 == c3);
+  assert(c1 == c4);
+  assert(c1 == c5);
+
+  assert(c2 == c1);
+  assert(c2 == c2);
+  assert(c2 == c3);
+  assert(c2 == c4);
+  assert(c2 == c5);
+
+  assert(c3 == c1);
+  assert(c3 == c2);
+  assert(c3 == c3);
+  assert(c3 == c4);
+  assert(c3 == c5);
+
+  assert(c4 == c1);
+  assert(c4 == c2);
+  assert(c4 == c3);
+  assert(c4 == c4);
+  assert(c4 == c5);
+
+  assert(c5 == c1);
+  assert(c5 == c2);
+  assert(c5 == c3);
+  assert(c5 == c4);
+  assert(c5 == c5);
+}
+
+int main(int, char**) {
+  {
+    std::size_t vals[] = {
+        // clang-format off
+        1,
+        2, 2,
+        3, 3, 3,
+        4, 4, 4, 4,
+        5, 5, 5, 5, 5,
+        6, 6, 6, 6, 6, 6,
+        7, 7, 7, 7, 7, 7, 7,
+        8, 8, 8, 8, 8, 8, 8, 8,
+        9, 9, 9, 9, 9, 9, 9, 9, 9,
+        10
+        // clang-format on
+    };
+    test(vals);
+  }
+
+  {
+    bool vals[] = {true, false};
+    test(vals);
+  }
+
+  {
+    char* vals[] = {(char*)("a"), (char*)("b"), (char*)("cde")};
+    test(vals);
+  }
+
+  return 0;
+}

libcxx/test/std/containers/unord/unord.multimap/eq.different_hash.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <unordered_map>
+
+// template <class Key, class T, class Hash, class Pred, class Alloc>
+// bool
+// operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
+//            const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
+//
+// template <class Key, class T, class Hash, class Pred, class Alloc>
+// bool
+// operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
+//            const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
+
+// Implements paper: http://wg21.link/p0809
+
+#include <unordered_map>
+#include <cassert>
+#include <limits>
+#include <cstddef>
+#include <utility>
+#include <functional>
+
+template <class T>
+std::size_t hash_identity(T val) {
+  return val;
+}
+template <class T>
+std::size_t hash_neg(T val) {
+  return std::numeric_limits<T>::max() - val;
+}
+template <class T>
+std::size_t hash_scale(T val) {
+  return val << 1;
+}
+template <class T>
+std::size_t hash_even(T val) {
+  return val & 1 ? 1 : 0;
+}
+template <class T>
+std::size_t hash_same(T /*val*/) {
+  return 1;
+}
+
+template <class T>
+std::size_t hash_identity(T* val) {
+  return *val;
+}
+template <class T>
+std::size_t hash_neg(T* val) {
+  return std::numeric_limits<T>::max() - *val;
+}
+template <class T>
+std::size_t hash_scale(T* val) {
+  return *val << 1;
+}
+template <class T>
+std::size_t hash_even(T* val) {
+  return *val & 1 ? 1 : 0;
+}
+
+template <class Map, class Ittr>
+void populate(Map& m, Ittr start, Ittr end) {
+  for (auto *p1 = start, *p2 = end - 1; p1 != end; ++p1, --p2) {
+    m.insert(std::make_pair(*p1, *p2));
+  }
+}
+
+template <class T, std::size_t N>
+void test(T (&vals)[N]) {
+  using Hash = std::size_t (*)(T);
+  using C    = std::unordered_multimap<T, T, Hash, std::equal_to<T> >;
+
+  C c1(0, hash_identity);
+  C c2(0, hash_neg);
+  C c3(0, hash_scale);
+  C c4(0, hash_even);
+  C c5(0, hash_same);
+
+  populate(c1, std::begin(vals), std::end(vals));
+  populate(c2, std::begin(vals), std::end(vals));
+  populate(c3, std::begin(vals), std::end(vals));
+  populate(c4, std::begin(vals), std::end(vals));
+  populate(c5, std::begin(vals), std::end(vals));
+
+  assert(c1 == c1);
+  assert(c1 == c2);
+  assert(c1 == c3);
+  assert(c1 == c4);
+  assert(c1 == c5);
+
+  assert(c2 == c1);
+  assert(c2 == c2);
+  assert(c2 == c3);
+  assert(c2 == c4);
+  assert(c2 == c5);
+
+  assert(c3 == c1);
+  assert(c3 == c2);
+  assert(c3 == c3);
+  assert(c3 == c4);
+  assert(c3 == c5);
+
+  assert(c4 == c1);
+  assert(c4 == c2);
+  assert(c4 == c3);
+  assert(c4 == c4);
+  assert(c4 == c5);
+
+  assert(c5 == c1);
+  assert(c5 == c2);
+  assert(c5 == c3);
+  assert(c5 == c4);
+  assert(c5 == c5);
+}
+
+int main(int, char**) {
+  {
+    std::size_t vals[] = {
+        // clang-format off
+        1,
+        2, 2,
+        3, 3, 3,
+        4, 4, 4, 4,
+        5, 5, 5, 5, 5,
+        6, 6, 6, 6, 6, 6,
+        7, 7, 7, 7, 7, 7, 7,
+        8, 8, 8, 8, 8, 8, 8, 8,
+        9, 9, 9, 9, 9, 9, 9, 9, 9,
+        10
+        // clang-format on
+    };
+    test(vals);
+  }
+  {
+    bool vals[] = {true, false};
+    test(vals);
+  }
+  {
+    char* vals[] = {(char*)("a"), (char*)("b"), (char*)("cde")};
+    test(vals);
+  }
+
+  return 0;
+}

libcxx/test/std/containers/unord/unord.multiset/eq.different_hash.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <unordered_set>
+
+// template <class Key, class T, class Hash, class Pred, class Alloc>
+// bool
+// operator==(const unordered_multiset<Key, T, Hash, Pred, Alloc>& x,
+//            const unordered_multiset<Key, T, Hash, Pred, Alloc>& y);
+//
+// template <class Key, class T, class Hash, class Pred, class Alloc>
+// bool
+// operator!=(const unordered_multiset<Key, T, Hash, Pred, Alloc>& x,
+//            const unordered_multiset<Key, T, Hash, Pred, Alloc>& y);
+
+// Implements paper: http://wg21.link/p0809
+
+#include <cassert>
+#include <cstddef>
+#include <functional>
+#include <limits>
+#include <unordered_set>
+
+template <class T>
+std::size_t hash_identity(T val) {
+  return val;
+}
+template <class T>
+std::size_t hash_neg(T val) {
+  return std::numeric_limits<T>::max() - val;
+}
+template <class T>
+std::size_t hash_scale(T val) {
+  return val << 1;
+}
+template <class T>
+std::size_t hash_even(T val) {
+  return val & 1 ? 1 : 0;
+}
+template <class T>
+std::size_t hash_same(T /*val*/) {
+  return 1;
+}
+
+template <class T>
+std::size_t hash_identity(T* val) {
+  return *val;
+}
+template <class T>
+std::size_t hash_neg(T* val) {
+  return std::numeric_limits<T>::max() - *val;
+}
+template <class T>
+std::size_t hash_scale(T* val) {
+  return *val << 1;
+}
+template <class T>
+std::size_t hash_even(T* val) {
+  return *val & 1 ? 1 : 0;
+}
+
+template <class T, std::size_t N>
+void test(T (&vals)[N]) {
+  using Hash = std::size_t (*)(T);
+  using C    = std::unordered_multiset<T, Hash, std::equal_to<T> >;
+
+  C c1(std::begin(vals), std::end(vals), 0, hash_identity);
+  C c2(std::begin(vals), std::end(vals), 0, hash_neg);
+  C c3(std::begin(vals), std::end(vals), 0, hash_scale);
+  C c4(std::begin(vals), std::end(vals), 0, hash_even);
+  C c5(std::begin(vals), std::end(vals), 0, hash_same);
+
+  assert(c1 == c1);
+  assert(c1 == c2);
+  assert(c1 == c3);
+  assert(c1 == c4);
+  assert(c1 == c5);
+
+  assert(c2 == c1);
+  assert(c2 == c2);
+  assert(c2 == c3);
+  assert(c2 == c4);
+  assert(c2 == c5);
+
+  assert(c3 == c1);
+  assert(c3 == c2);
+  assert(c3 == c3);
+  assert(c3 == c4);
+  assert(c3 == c5);
+
+  assert(c4 == c1);
+  assert(c4 == c2);
+  assert(c4 == c3);
+  assert(c4 == c4);
+  assert(c4 == c5);
+
+  assert(c5 == c1);
+  assert(c5 == c2);
+  assert(c5 == c3);
+  assert(c5 == c4);
+  assert(c5 == c5);
+}
+
+int main(int, char**) {
+  {
+    std::size_t vals[] = {
+        // clang-format off
+        1,
+        2, 2,
+        3, 3, 3,
+        4, 4, 4, 4,
+        5, 5, 5, 5, 5,
+        6, 6, 6, 6, 6, 6,
+        7, 7, 7, 7, 7, 7, 7,
+        8, 8, 8, 8, 8, 8, 8, 8,
+        9, 9, 9, 9, 9, 9, 9, 9, 9,
+        10
+        // clang-format on
+    };
+    test(vals);
+  }
+  {
+    bool vals[] = {true, false};
+    test(vals);
+  }
+  {
+    char* vals[] = {(char*)("a"), (char*)("b"), (char*)("cde")};
+    test(vals);
+  }
+
+  return 0;
+}

libcxx/test/std/containers/unord/unord.set/eq.different_hash.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <unordered_set>
+
+// template <class Key, class T, class Hash, class Pred, class Alloc>
+// bool
+// operator==(const unordered_set<Key, T, Hash, Pred, Alloc>& x,
+//            const unordered_set<Key, T, Hash, Pred, Alloc>& y);
+//
+// template <class Key, class T, class Hash, class Pred, class Alloc>
+// bool
+// operator!=(const unordered_set<Key, T, Hash, Pred, Alloc>& x,
+//            const unordered_set<Key, T, Hash, Pred, Alloc>& y);
+
+// Implements paper: http://wg21.link/p0809
+
+#include <unordered_set>
+#include <cstddef>
+#include <limits>
+#include <cassert>
+#include <functional>
+
+template <class T>
+std::size_t hash_identity(T val) {
+  return val;
+}
+template <class T>
+std::size_t hash_neg(T val) {
+  return std::numeric_limits<T>::max() - val;
+}
+template <class T>
+std::size_t hash_scale(T val) {
+  return val << 1;
+}
+template <class T>
+std::size_t hash_even(T val) {
+  return val & 1 ? 1 : 0;
+}
+template <class T>
+std::size_t hash_same(T /*val*/) {
+  return 1;
+}
+
+template <class T>
+std::size_t hash_identity(T* val) {
+  return *val;
+}
+template <class T>
+std::size_t hash_neg(T* val) {
+  return std::numeric_limits<T>::max() - *val;
+}
+template <class T>
+size_t hash_scale(T* val) {
+  return *val << 1;
+}
+template <class T>
+size_t hash_even(T* val) {
+  return *val & 1 ? 1 : 0;
+}
+
+template <class T, std::size_t N>
+void test(T (&vals)[N]) {
+  using Hash = std::size_t (*)(T);
+  using C    = std::unordered_set<T, Hash, std::equal_to<T> >;
+
+  C c1(std::begin(vals), std::end(vals), 0, hash_identity);
+  C c2(std::begin(vals), std::end(vals), 0, hash_neg);
+  C c3(std::begin(vals), std::end(vals), 0, hash_scale);
+  C c4(std::begin(vals), std::end(vals), 0, hash_even);
+  C c5(std::begin(vals), std::end(vals), 0, hash_same);
+
+  assert(c1 == c1);
+  assert(c1 == c2);
+  assert(c1 == c3);
+  assert(c1 == c4);
+  assert(c1 == c5);
+
+  assert(c2 == c1);
+  assert(c2 == c2);
+  assert(c2 == c3);
+  assert(c2 == c4);
+  assert(c2 == c5);
+
+  assert(c3 == c1);
+  assert(c3 == c2);
+  assert(c3 == c3);
+  assert(c3 == c4);
+  assert(c3 == c5);
+
+  assert(c4 == c1);
+  assert(c4 == c2);
+  assert(c4 == c3);
+  assert(c4 == c4);
+  assert(c4 == c5);
+
+  assert(c5 == c1);
+  assert(c5 == c2);
+  assert(c5 == c3);
+  assert(c5 == c4);
+  assert(c5 == c5);
+}
+
+int main(int, char**) {
+  {
+    std::size_t vals[] = {
+        // clang-format off
+        1,
+        2, 2,
+        3, 3, 3,
+        4, 4, 4, 4,
+        5, 5, 5, 5, 5,
+        6, 6, 6, 6, 6, 6,
+        7, 7, 7, 7, 7, 7, 7,
+        8, 8, 8, 8, 8, 8, 8, 8,
+        9, 9, 9, 9, 9, 9, 9, 9, 9,
+        10
+        // clang-format on
+    };
+    test(vals);
+  }
+
+  {
+    bool vals[] = {true, false};
+    test(vals);
+  }
+
+  {
+    char* vals[] = {(char*)("a"), (char*)("b"), (char*)("cde")};
+    test(vals);
+  }
+
+  return 0;
+}