WPILibC++  2020.3.2-60-g3011ebe
FunctionExtras.h
Go to the documentation of this file.
1 //===- FunctionExtras.h - Function type erasure utilities -------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
31 //===----------------------------------------------------------------------===//
32 
33 #ifndef WPIUTIL_WPI_FUNCTION_EXTRAS_H
34 #define WPIUTIL_WPI_FUNCTION_EXTRAS_H
35 
36 #include "wpi/Compiler.h"
37 #include "wpi/PointerIntPair.h"
38 #include "wpi/PointerUnion.h"
39 #include <memory>
40 
41 namespace wpi {
42 
43 template <typename FunctionT> class unique_function;
44 
45 // GCC warns on OutOfLineStorage
46 #if defined(__GNUC__) && !defined(__clang__)
47 #pragma GCC diagnostic push
48 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
49 #endif
50 
51 template <typename ReturnT, typename... ParamTs>
52 class unique_function<ReturnT(ParamTs...)> {
53  static constexpr size_t InlineStorageSize = sizeof(void *) * 4;
54 
55  // MSVC has a bug and ICEs if we give it a particular dependent value
56  // expression as part of the `std::conditional` below. To work around this,
57  // we build that into a template struct's constexpr bool.
58  template <typename T> struct IsSizeLessThanThresholdT {
59  static constexpr bool value = sizeof(T) <= (2 * sizeof(void *));
60  };
61 
62  // Provide a type function to map parameters that won't observe extra copies
63  // or moves and which are small enough to likely pass in register to values
64  // and all other types to l-value reference types. We use this to compute the
65  // types used in our erased call utility to minimize copies and moves unless
66  // doing so would force things unnecessarily into memory.
67  //
68  // The heuristic used is related to common ABI register passing conventions.
69  // It doesn't have to be exact though, and in one way it is more strict
70  // because we want to still be able to observe either moves *or* copies.
71  template <typename T>
72  using AdjustedParamT = typename std::conditional<
73  !std::is_reference<T>::value &&
74  std::is_trivially_copy_constructible<T>::value &&
75  std::is_trivially_move_constructible<T>::value &&
76  IsSizeLessThanThresholdT<T>::value,
77  T, T &>::type;
78 
79  // The type of the erased function pointer we use as a callback to dispatch to
80  // the stored callable when it is trivial to move and destroy.
81  using CallPtrT = ReturnT (*)(void *CallableAddr,
82  AdjustedParamT<ParamTs>... Params);
83  using MovePtrT = void (*)(void *LHSCallableAddr, void *RHSCallableAddr);
84  using DestroyPtrT = void (*)(void *CallableAddr);
85 
88  struct alignas(8) TrivialCallback {
89  CallPtrT CallPtr;
90  };
91 
94  struct alignas(8) NonTrivialCallbacks {
95  CallPtrT CallPtr;
96  MovePtrT MovePtr;
97  DestroyPtrT DestroyPtr;
98  };
99 
100  // Create a pointer union between either a pointer to a static trivial call
101  // pointer in a struct or a pointer to a static struct of the call, move, and
102  // destroy pointers.
103  using CallbackPointerUnionT =
105 
106  // The main storage buffer. This will either have a pointer to out-of-line
107  // storage or an inline buffer storing the callable.
108  union StorageUnionT {
109  // For out-of-line storage we keep a pointer to the underlying storage and
110  // the size. This is enough to deallocate the memory.
111  struct OutOfLineStorageT {
112  void *StoragePtr;
113  size_t Size;
114  size_t Alignment;
115  } OutOfLineStorage;
116  static_assert(
117  sizeof(OutOfLineStorageT) <= InlineStorageSize,
118  "Should always use all of the out-of-line storage for inline storage!");
119 
120  // For in-line storage, we just provide an aligned character buffer. We
121  // provide four pointers worth of storage here.
122  typename std::aligned_storage<InlineStorageSize, alignof(void *)>::type
123  InlineStorage;
124  } StorageUnion;
125 
126  // A compressed pointer to either our dispatching callback or our table of
127  // dispatching callbacks and the flag for whether the callable itself is
128  // stored inline or not.
130 
131  bool isInlineStorage() const { return CallbackAndInlineFlag.getInt(); }
132 
133  bool isTrivialCallback() const {
134  return CallbackAndInlineFlag.getPointer().template is<TrivialCallback *>();
135  }
136 
137  CallPtrT getTrivialCallback() const {
138  return CallbackAndInlineFlag.getPointer().template get<TrivialCallback *>()->CallPtr;
139  }
140 
141  NonTrivialCallbacks *getNonTrivialCallbacks() const {
142  return CallbackAndInlineFlag.getPointer()
143  .template get<NonTrivialCallbacks *>();
144  }
145 
146  void *getInlineStorage() { return &StorageUnion.InlineStorage; }
147 
148  void *getOutOfLineStorage() {
149  return StorageUnion.OutOfLineStorage.StoragePtr;
150  }
151  size_t getOutOfLineStorageSize() const {
152  return StorageUnion.OutOfLineStorage.Size;
153  }
154  size_t getOutOfLineStorageAlignment() const {
155  return StorageUnion.OutOfLineStorage.Alignment;
156  }
157 
158  void setOutOfLineStorage(void *Ptr, size_t Size, size_t Alignment) {
159  StorageUnion.OutOfLineStorage = {Ptr, Size, Alignment};
160  }
161 
162  template <typename CallableT>
163  static ReturnT CallImpl(void *CallableAddr, AdjustedParamT<ParamTs>... Params) {
164  return (*reinterpret_cast<CallableT *>(CallableAddr))(
165  std::forward<ParamTs>(Params)...);
166  }
167 
168  template <typename CallableT>
169  static void MoveImpl(void *LHSCallableAddr, void *RHSCallableAddr) noexcept {
170  new (LHSCallableAddr)
171  CallableT(std::move(*reinterpret_cast<CallableT *>(RHSCallableAddr)));
172  }
173 
174  template <typename CallableT>
175  static void DestroyImpl(void *CallableAddr) noexcept {
176  reinterpret_cast<CallableT *>(CallableAddr)->~CallableT();
177  }
178 
179 public:
180  unique_function() = default;
181  unique_function(std::nullptr_t /*null_callable*/) {}
182 
183  ~unique_function() {
184  if (!CallbackAndInlineFlag.getPointer())
185  return;
186 
187  // Cache this value so we don't re-check it after type-erased operations.
188  bool IsInlineStorage = isInlineStorage();
189 
190  if (!isTrivialCallback())
191  getNonTrivialCallbacks()->DestroyPtr(
192  IsInlineStorage ? getInlineStorage() : getOutOfLineStorage());
193 
194  if (!IsInlineStorage)
195  deallocate_buffer(getOutOfLineStorage(), getOutOfLineStorageSize(),
196  getOutOfLineStorageAlignment());
197  }
198 
199  unique_function(unique_function &&RHS) noexcept {
200  // Copy the callback and inline flag.
201  CallbackAndInlineFlag = RHS.CallbackAndInlineFlag;
202 
203  // If the RHS is empty, just copying the above is sufficient.
204  if (!RHS)
205  return;
206 
207  if (!isInlineStorage()) {
208  // The out-of-line case is easiest to move.
209  StorageUnion.OutOfLineStorage = RHS.StorageUnion.OutOfLineStorage;
210  } else if (isTrivialCallback()) {
211  // Move is trivial, just memcpy the bytes across.
212  memcpy(getInlineStorage(), RHS.getInlineStorage(), InlineStorageSize);
213  } else {
214  // Non-trivial move, so dispatch to a type-erased implementation.
215  getNonTrivialCallbacks()->MovePtr(getInlineStorage(),
216  RHS.getInlineStorage());
217  }
218 
219  // Clear the old callback and inline flag to get back to as-if-null.
220  RHS.CallbackAndInlineFlag = {};
221 
222 #ifndef NDEBUG
223  // In debug builds, we also scribble across the rest of the storage.
224  memset(RHS.getInlineStorage(), 0xAD, InlineStorageSize);
225 #endif
226  }
227 
228  unique_function &operator=(unique_function &&RHS) noexcept {
229  if (this == &RHS)
230  return *this;
231 
232  // Because we don't try to provide any exception safety guarantees we can
233  // implement move assignment very simply by first destroying the current
234  // object and then move-constructing over top of it.
235  this->~unique_function();
236  new (this) unique_function(std::move(RHS));
237  return *this;
238  }
239 
240  template <typename CallableT> unique_function(CallableT Callable) {
241  bool IsInlineStorage = true;
242  void *CallableAddr = getInlineStorage();
243  if (sizeof(CallableT) > InlineStorageSize ||
244  alignof(CallableT) > alignof(decltype(StorageUnion.InlineStorage))) {
245  IsInlineStorage = false;
246  // Allocate out-of-line storage. FIXME: Use an explicit alignment
247  // parameter in C++17 mode.
248  auto Size = sizeof(CallableT);
249  auto Alignment = alignof(CallableT);
250  CallableAddr = allocate_buffer(Size, Alignment);
251  setOutOfLineStorage(CallableAddr, Size, Alignment);
252  }
253 
254  // Now move into the storage.
255  new (CallableAddr) CallableT(std::move(Callable));
256 
257  // See if we can create a trivial callback. We need the callable to be
258  // trivially moved and trivially destroyed so that we don't have to store
259  // type erased callbacks for those operations.
260  //
261  // FIXME: We should use constexpr if here and below to avoid instantiating
262  // the non-trivial static objects when unnecessary. While the linker should
263  // remove them, it is still wasteful.
264  if (std::is_trivially_move_constructible<CallableT>::value &&
265  std::is_trivially_destructible<CallableT>::value) {
266  // We need to create a nicely aligned object. We use a static variable
267  // for this because it is a trivial struct.
268  static TrivialCallback Callback = { &CallImpl<CallableT> };
269 
270  CallbackAndInlineFlag = {&Callback, IsInlineStorage};
271  return;
272  }
273 
274  // Otherwise, we need to point at an object that contains all the different
275  // type erased behaviors needed. Create a static instance of the struct type
276  // here and then use a pointer to that.
277  static NonTrivialCallbacks Callbacks = {
278  &CallImpl<CallableT>, &MoveImpl<CallableT>, &DestroyImpl<CallableT>};
279 
280  CallbackAndInlineFlag = {&Callbacks, IsInlineStorage};
281  }
282 
283  ReturnT operator()(ParamTs... Params) {
284  void *CallableAddr =
285  isInlineStorage() ? getInlineStorage() : getOutOfLineStorage();
286 
287  return (isTrivialCallback()
288  ? getTrivialCallback()
289  : getNonTrivialCallbacks()->CallPtr)(CallableAddr, Params...);
290  }
291 
292  explicit operator bool() const {
293  return (bool)CallbackAndInlineFlag.getPointer();
294  }
295 };
296 
297 #if defined(__GNUC__) && !defined(__clang__)
298 #pragma GCC diagnostic pop
299 #endif
300 
301 } // end namespace wpi
302 
303 #endif // WPIUTIL_WPI_FUNCTION_H
wpi::unique_function
Definition: FunctionExtras.h:43
wpi::allocate_buffer
void * allocate_buffer(size_t Size, size_t Alignment)
Allocate a buffer of memory with the given size and alignment.
Definition: Compiler.h:485
wpi::deallocate_buffer
void deallocate_buffer(void *Ptr, size_t Size, size_t Alignment)
Deallocate a buffer of memory with the given size and alignment.
Definition: Compiler.h:501
wpi
WPILib C++ utilities (wpiutil) namespace.
Definition: Endian.h:31
wpi::PointerUnion
A discriminated union of two pointer types, with the discriminator in the low bit of the pointer.
Definition: PointerUnion.h:87
wpi::PointerIntPair
PointerIntPair - This class implements a pair of a pointer and small integer.
Definition: PointerIntPair.h:44