1 /*
2 * Frozen
3 * Copyright 2016 QuarksLab
4 *
5 * Licensed to the Apache Software Foundation (ASF) under one
6 * or more contributor license agreements. See the NOTICE file
7 * distributed with this work for additional information
8 * regarding copyright ownership. The ASF licenses this file
9 * to you under the Apache License, Version 2.0 (the
10 * "License"); you may not use this file except in compliance
11 * with the License. You may obtain a copy of the License at
12 *
13 * http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Unless required by applicable law or agreed to in writing,
16 * software distributed under the License is distributed on an
17 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
18 * KIND, either express or implied. See the License for the
19 * specific language governing permissions and limitations
20 * under the License.
21 */
22
23 #ifndef FROZEN_LETITGO_UNORDERED_SET_H
24 #define FROZEN_LETITGO_UNORDERED_SET_H
25
26 #include "frozen/bits/basic_types.h"
27 #include "frozen/bits/constexpr_assert.h"
28 #include "frozen/bits/elsa.h"
29 #include "frozen/bits/pmh.h"
30 #include "frozen/bits/version.h"
31 #include "frozen/random.h"
32
33 #include <utility>
34
35 namespace frozen {
36
37 namespace bits {
38
39 struct Get {
operatorGet40 template <class T> constexpr T const &operator()(T const &key) const {
41 return key;
42 }
43 };
44
45 } // namespace bits
46
47 template <class Key, std::size_t N, typename Hash = elsa<Key>,
48 class KeyEqual = std::equal_to<Key>>
49 class unordered_set {
50 static constexpr std::size_t storage_size =
51 bits::next_highest_power_of_two(N) * (N < 32 ? 2 : 1); // size adjustment to prevent high collision rate for small sets
52 using container_type = bits::carray<Key, N>;
53 using tables_type = bits::pmh_tables<storage_size, Hash>;
54
55 KeyEqual const equal_;
56 container_type keys_;
57 tables_type tables_;
58
59 public:
60 /* typedefs */
61 using key_type = Key;
62 using value_type = Key;
63 using size_type = typename container_type::size_type;
64 using difference_type = typename container_type::difference_type;
65 using hasher = Hash;
66 using key_equal = KeyEqual;
67 using const_reference = typename container_type::const_reference;
68 using reference = const_reference;
69 using const_pointer = typename container_type::const_pointer;
70 using pointer = const_pointer;
71 using const_iterator = const_pointer;
72 using iterator = const_iterator;
73
74 public:
75 /* constructors */
76 unordered_set(unordered_set const &) = default;
unordered_set(container_type keys,Hash const & hash,KeyEqual const & equal)77 constexpr unordered_set(container_type keys, Hash const &hash,
78 KeyEqual const &equal)
79 : equal_{equal}
80 , keys_{keys}
81 , tables_{bits::make_pmh_tables<storage_size>(
82 keys_, hash, bits::Get{}, default_prg_t{})} {}
unordered_set(container_type keys)83 explicit constexpr unordered_set(container_type keys)
84 : unordered_set{keys, Hash{}, KeyEqual{}} {}
85
unordered_set(std::initializer_list<Key> keys)86 constexpr unordered_set(std::initializer_list<Key> keys)
87 : unordered_set{keys, Hash{}, KeyEqual{}} {}
88
unordered_set(std::initializer_list<Key> keys,Hash const & hash,KeyEqual const & equal)89 constexpr unordered_set(std::initializer_list<Key> keys, Hash const & hash, KeyEqual const & equal)
90 : unordered_set{container_type{keys}, hash, equal} {
91 constexpr_assert(keys.size() == N, "Inconsistent initializer_list size and type size argument");
92 }
93
94 /* iterators */
begin()95 constexpr const_iterator begin() const { return keys_.begin(); }
end()96 constexpr const_iterator end() const { return keys_.end(); }
cbegin()97 constexpr const_iterator cbegin() const { return keys_.cbegin(); }
cend()98 constexpr const_iterator cend() const { return keys_.cend(); }
99
100 /* capacity */
empty()101 constexpr bool empty() const { return !N; }
size()102 constexpr size_type size() const { return N; }
max_size()103 constexpr size_type max_size() const { return N; }
104
105 /* lookup */
count(Key const & key)106 constexpr std::size_t count(Key const &key) const {
107 auto const k = lookup(key);
108 return equal_(k, key);
109 }
find(Key const & key)110 constexpr const_iterator find(Key const &key) const {
111 auto const &k = lookup(key);
112 if (equal_(k, key))
113 return &k;
114 else
115 return keys_.end();
116 }
117
equal_range(Key const & key)118 constexpr std::pair<const_iterator, const_iterator> equal_range(Key const &key) const {
119 auto const &k = lookup(key);
120 if (equal_(k, key))
121 return {&k, &k + 1};
122 else
123 return {keys_.end(), keys_.end()};
124 }
125
126 /* bucket interface */
bucket_count()127 constexpr std::size_t bucket_count() const { return storage_size; }
max_bucket_count()128 constexpr std::size_t max_bucket_count() const { return storage_size; }
129
130 /* observers*/
hash_function()131 constexpr hasher hash_function() const { return tables_.hash_; }
key_eq()132 constexpr key_equal key_eq() const { return equal_; }
133
134 private:
lookup(Key const & key)135 constexpr auto const &lookup(Key const &key) const {
136 return keys_[tables_.lookup(key)];
137 }
138 };
139
140 template <typename T, std::size_t N>
make_unordered_set(T const (& keys)[N])141 constexpr auto make_unordered_set(T const (&keys)[N]) {
142 return unordered_set<T, N>{keys};
143 }
144
145 template <typename T, std::size_t N>
make_unordered_set(std::array<T,N> const & keys)146 constexpr auto make_unordered_set(std::array<T, N> const &keys) {
147 return unordered_set<T, N>{keys};
148 }
149
150 } // namespace frozen
151
152 #endif
153