1 // Copyright 2016 The Fuchsia Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #pragma once
6 
7 #include <fbl/intrusive_pointer_traits.h>
8 #include <fbl/type_support.h>
9 
10 namespace fbl {
11 
12 // DefaultKeyedObjectTraits defines a default implementation of traits used to
13 // manage objects stored in associative containers such as hash-tables and
14 // trees.
15 //
16 // At a minimum, a class or a struct which is to be used to define the
17 // traits of a keyed object must define the following public members.
18 //
19 // GetKey   : A static method which takes a constant reference to an object (the
20 //            type of which is infered from PtrType) and returns a KeyType
21 //            instance corresponding to the key for an object.
22 // LessThan : A static method which takes two keys (key1 and key2) and returns
23 //            true if-and-only-if key1 is considered to be less than key2 for
24 //            sorting purposes.
25 // EqualTo  : A static method which takes two keys (key1 and key2) and returns
26 //            true if-and-only-if key1 is considered to be equal to key2.
27 //
28 // Rules for keys:
29 // ++ The type of key returned by GetKey must be compatible with the key which
30 //    was specified for the container.
31 // ++ The key for an object must remain constant for as long as the object is
32 //    contained within a container.
33 // ++ When comparing keys, comparisons must obey basic transative and
34 //    commutative properties.  That is to say...
35 //    LessThan(A, B) and LessThan(B, C) implies LessThan(A, C)
36 //    EqualTo(A, B) and EqualTo(B, C) implies EqualTo(A, C)
37 //    EqualTo(A, B) if-and-only-if EqualTo(B, A)
38 //    LessThan(A, B) if-and-only-if EqualTo(B, A) or (not LessThan(B, A))
39 //
40 // DefaultKeyedObjectTraits is a helper class which allows an object to be
41 // treated as a keyed-object by implementing a const GetKey method which returns
42 // a key of the appropriate type.  The key type must be compatible with the
43 // container key type, and must have definitions of the < and == operators for
44 // the purpose of generating implementation of LessThan and EqualTo.
45 template <typename KeyType, typename ObjType>
46 struct DefaultKeyedObjectTraits {
GetKeyDefaultKeyedObjectTraits47     static KeyType GetKey(const ObjType& obj)                       { return obj.GetKey(); }
LessThanDefaultKeyedObjectTraits48     static bool LessThan(const KeyType& key1, const KeyType& key2)  { return key1 <  key2; }
EqualToDefaultKeyedObjectTraits49     static bool EqualTo (const KeyType& key1, const KeyType& key2)  { return key1 == key2; }
50 };
51 
52 }  // namespace fbl
53 
54 namespace fbl {
55 namespace internal {
56 
57 // DirectEraseUtils
58 //
59 // A utility class used by HashTable to implement an O(n) or O(k) direct erase
60 // operation depending on whether or not the HashTable's bucket type supports
61 // O(k) erase.
62 template <typename ContainerType, typename Enable = void>
63 struct DirectEraseUtils;
64 
65 template <typename ContainerType>
66 struct DirectEraseUtils<
67         ContainerType,
68         typename enable_if<ContainerType::SupportsConstantOrderErase == false, void>::type> {
69     using PtrTraits = typename ContainerType::PtrTraits;
70     using PtrType   = typename PtrTraits::PtrType;
71     using ValueType = typename PtrTraits::ValueType;
72 
73     static PtrType erase(ContainerType& container, ValueType& obj) {
74         return container.erase_if(
75             [&obj](const ValueType& other) -> bool {
76                 return &obj == &other;
77             });
78     }
79 };
80 
81 template <typename ContainerType>
82 struct DirectEraseUtils<
83         ContainerType,
84         typename enable_if<ContainerType::SupportsConstantOrderErase == true, void>::type> {
85     using PtrTraits = typename ContainerType::PtrTraits;
86     using PtrType   = typename PtrTraits::PtrType;
87     using ValueType = typename PtrTraits::ValueType;
88 
89     static PtrType erase(ContainerType& container, ValueType& obj) {
90         return container.erase(obj);
91     }
92 };
93 
94 // KeyEraseUtils
95 //
96 // A utility class used by HashTable to implement an O(n) or O(k) erase-by-key
97 // operation depending on whether or not the HashTable's bucket type is
98 // associative or not.
99 template <typename ContainerType, typename KeyTraits, typename Enable = void>
100 struct KeyEraseUtils;
101 
102 template <typename ContainerType, typename KeyTraits>
103 struct KeyEraseUtils<
104         ContainerType,
105         KeyTraits,
106         typename enable_if<ContainerType::IsAssociative == false, void>::type> {
107     using PtrTraits = typename ContainerType::PtrTraits;
108     using PtrType   = typename PtrTraits::PtrType;
109     using ValueType = typename PtrTraits::ValueType;
110 
111     template <typename KeyType>
112     static PtrType erase(ContainerType& container, const KeyType& key) {
113         return container.erase_if(
114             [key](const ValueType& other) -> bool {
115                 return KeyTraits::EqualTo(key, KeyTraits::GetKey(other));
116             });
117     }
118 };
119 
120 template <typename ContainerType, typename KeyTraits>
121 struct KeyEraseUtils<
122         ContainerType,
123         KeyTraits,
124         typename enable_if<ContainerType::IsAssociative == true, void>::type> {
125     using PtrTraits = typename ContainerType::PtrTraits;
126     using PtrType   = typename PtrTraits::PtrType;
127 
128     template <typename KeyType>
129     static PtrType erase(ContainerType& container, const KeyType& key) {
130         return container.erase(key);
131     }
132 };
133 
134 // Swaps two plain old data types with size no greater than 64 bits.
135 template <class T, class = typename enable_if<is_pod<T>::value && (sizeof(T) <= 8)>::type>
136 inline void Swap(T& a, T& b) noexcept {
137     T tmp = a;
138     a = b;
139     b = tmp;
140 }
141 
142 // Notes on container sentinels:
143 //
144 // Intrusive container implementations employ a slightly tricky pattern where
145 // sentinel values are used in place of nullptr in various places in the
146 // internal data structure in order to make some operations a bit easier.
147 // Generally speaking, a sentinel pointer is a pointer to a container with the
148 // sentinel bit set.  It is cast and stored in the container's data structure as
149 // a pointer to an element which the container contains, even though it is
150 // actually a slightly damaged pointer to the container itself.
151 //
152 // An example of where this is used is in the doubly linked list implementation.
153 // The final element in the list holds the container's sentinel value instead of
154 // nullptr or a pointer to the head of the list.  When an iterator hits the end
155 // of the list, it knows that it is at the end (because the sentinel bit is set)
156 // but can still get back to the list itself (by clearing the sentinel bit in
157 // the pointer) without needing to store an explicit pointer to the list itself.
158 //
159 // Care must be taken when using sentinel values.  They are *not* valid pointers
160 // and must never be dereferenced, recovered into an managed representation, or
161 // returned to a user.  In addition, it is essential that a legitimate pointer
162 // to a container never need to set the sentinel bit.  Currently, bit 0 is being
163 // used because it should never be possible to have a proper container instance
164 // which is odd-aligned.
165 constexpr uintptr_t kContainerSentinelBit = 1u;
166 
167 // Create a sentinel pointer from a raw pointer, converting it to the specified
168 // type in the process.
169 template <typename T, typename U, typename = typename enable_if<is_pointer<T>::value>::type>
170 constexpr T make_sentinel(U* ptr) {
171     return reinterpret_cast<T>(reinterpret_cast<uintptr_t>(ptr) |
172                                kContainerSentinelBit);
173 }
174 
175 template <typename T, typename = typename enable_if<is_pointer<T>::value>::type>
176 constexpr T make_sentinel(decltype(nullptr)) {
177     return reinterpret_cast<T>(kContainerSentinelBit);
178 }
179 
180 // Turn a sentinel pointer back into a normal pointer, automatically
181 // re-interpreting its type in the process.
182 template <typename T, typename U, typename = typename enable_if<is_pointer<T>::value>::type>
183 constexpr T unmake_sentinel(U* sentinel) {
184     return reinterpret_cast<T>(reinterpret_cast<uintptr_t>(sentinel) &
185                                ~kContainerSentinelBit);
186 }
187 
188 // Test to see if a pointer is a sentinel pointer.
189 template <typename T>
190 constexpr bool is_sentinel_ptr(const T* ptr) {
191     return (reinterpret_cast<uintptr_t>(ptr) & kContainerSentinelBit) != 0;
192 }
193 
194 // Test to see if a pointer (which may be a sentinel) is valid.  Valid in this
195 // context means that the pointer is not null, and is not a sentinel.
196 template <typename T>
197 constexpr bool valid_sentinel_ptr(const T* ptr) {
198     return ptr && !is_sentinel_ptr(ptr);
199 }
200 
201 }  // namespace internal
202 }  // namespace fbl
203