memory.h 16.9 KB
Newer Older
Kenton Varda's avatar
Kenton Varda committed
1 2
// Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors
// Licensed under the MIT License:
3
//
Kenton Varda's avatar
Kenton Varda committed
4 5 6 7 8 9
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
10
//
Kenton Varda's avatar
Kenton Varda committed
11 12
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
13
//
Kenton Varda's avatar
Kenton Varda committed
14 15 16 17 18 19 20
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
21

22
#pragma once
23

24 25 26 27
#if defined(__GNUC__) && !KJ_HEADER_WARNINGS
#pragma GCC system_header
#endif

28 29 30 31
#include "common.h"

namespace kj {

32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
namespace _ {  // private

template <typename T> struct RefOrVoid_ { typedef T& Type; };
template <> struct RefOrVoid_<void> { typedef void Type; };
template <> struct RefOrVoid_<const void> { typedef void Type; };

template <typename T>
using RefOrVoid = typename RefOrVoid_<T>::Type;
// Evaluates to T&, unless T is `void`, in which case evaluates to `void`.
//
// This is a hack needed to avoid defining Own<void> as a totally separate class.

template <typename T, bool isPolymorphic = __is_polymorphic(T)>
struct CastToVoid_;

template <typename T>
struct CastToVoid_<T, false> {
  static void* apply(T* ptr) {
    return static_cast<void*>(ptr);
  }
  static const void* applyConst(T* ptr) {
    const T* cptr = ptr;
    return static_cast<const void*>(cptr);
  }
};

template <typename T>
struct CastToVoid_<T, true> {
  static void* apply(T* ptr) {
    return dynamic_cast<void*>(ptr);
  }
  static const void* applyConst(T* ptr) {
    const T* cptr = ptr;
    return dynamic_cast<const void*>(cptr);
  }
};

template <typename T>
void* castToVoid(T* ptr) {
  return CastToVoid_<T>::apply(ptr);
}

template <typename T>
75
const void* castToConstVoid(T* ptr) {
76 77 78 79 80
  return CastToVoid_<T>::applyConst(ptr);
}

}  // namespace _ (private)

81
// =======================================================================================
Kenton Varda's avatar
Kenton Varda committed
82
// Disposer -- Implementation details.
83 84

class Disposer {
Kenton Varda's avatar
Kenton Varda committed
85 86 87 88 89 90
  // Abstract interface for a thing that "disposes" of objects, where "disposing" usually means
  // calling the destructor followed by freeing the underlying memory.  `Own<T>` encapsulates an
  // object pointer with corresponding Disposer.
  //
  // Few developers will ever touch this interface.  It is primarily useful for those implementing
  // custom memory allocators.
91 92

protected:
93 94
  // Do not declare a destructor, as doing so will force a global initializer for each HeapDisposer
  // instance.  Eww!
95

Kenton Varda's avatar
Kenton Varda committed
96 97 98 99 100 101
  virtual void disposeImpl(void* pointer) const = 0;
  // Disposes of the object, given a pointer to the beginning of the object.  If the object is
  // polymorphic, this pointer is determined by dynamic_cast<void*>().  For non-polymorphic types,
  // Own<T> does not allow any casting, so the pointer exactly matches the original one given to
  // Own<T>.

102
public:
Kenton Varda's avatar
Kenton Varda committed
103 104 105 106

  template <typename T>
  void dispose(T* object) const;
  // Helper wrapper around disposeImpl().
107
  //
Kenton Varda's avatar
Kenton Varda committed
108
  // If T is polymorphic, calls `disposeImpl(dynamic_cast<void*>(object))`, otherwise calls
109
  // `disposeImpl(implicitCast<void*>(object))`.
110
  //
Kenton Varda's avatar
Kenton Varda committed
111 112 113 114 115 116
  // Callers must not call dispose() on the same pointer twice, even if the first call throws
  // an exception.

private:
  template <typename T, bool polymorphic = __is_polymorphic(T)>
  struct Dispose_;
117 118
};

119 120 121 122 123 124 125 126 127 128 129 130 131 132 133
template <typename T>
class DestructorOnlyDisposer: public Disposer {
  // A disposer that merely calls the type's destructor and nothing else.

public:
  static const DestructorOnlyDisposer instance;

  void disposeImpl(void* pointer) const override {
    reinterpret_cast<T*>(pointer)->~T();
  }
};

template <typename T>
const DestructorOnlyDisposer<T> DestructorOnlyDisposer<T>::instance = DestructorOnlyDisposer<T>();

134 135 136 137 138 139 140 141 142
class NullDisposer: public Disposer {
  // A disposer that does nothing.

public:
  static const NullDisposer instance;

  void disposeImpl(void* pointer) const override {}
};

143 144 145 146 147 148 149 150 151 152 153 154
// =======================================================================================
// Own<T> -- An owned pointer.

template <typename T>
class Own {
  // A transferrable title to a T.  When an Own<T> goes out of scope, the object's Disposer is
  // called to dispose of it.  An Own<T> can be efficiently passed by move, without relocating the
  // underlying object; this transfers ownership.
  //
  // This is much like std::unique_ptr, except:
  // - You cannot release().  An owned object is not necessarily allocated with new (see next
  //   point), so it would be hard to use release() correctly.
Kenton Varda's avatar
Kenton Varda committed
155 156 157 158 159 160
  // - The deleter is made polymorphic by virtual call rather than by template.  This is much
  //   more powerful -- it allows the use of custom allocators, freelists, etc.  This could
  //   _almost_ be accomplished with unique_ptr by forcing everyone to use something like
  //   std::unique_ptr<T, kj::Deleter>, except that things get hairy in the presence of multiple
  //   inheritance and upcasting, and anyway if you force everyone to use a custom deleter
  //   then you've lost any benefit to interoperating with the "standard" unique_ptr.
161 162

public:
163 164
  KJ_DISALLOW_COPY(Own);
  inline Own(): disposer(nullptr), ptr(nullptr) {}
165 166
  inline Own(Own&& other) noexcept
      : disposer(other.disposer), ptr(other.ptr) { other.ptr = nullptr; }
167
  inline Own(Own<RemoveConstOrDisable<T>>&& other) noexcept
168
      : disposer(other.disposer), ptr(other.ptr) { other.ptr = nullptr; }
169
  template <typename U, typename = EnableIf<canConvert<U*, T*>()>>
170
  inline Own(Own<U>&& other) noexcept
171
      : disposer(other.disposer), ptr(cast(other.ptr)) {
Kenton Varda's avatar
Kenton Varda committed
172 173 174
    other.ptr = nullptr;
  }
  inline Own(T* ptr, const Disposer& disposer) noexcept: disposer(&disposer), ptr(ptr) {}
175

176
  ~Own() noexcept(false) { dispose(); }
177 178

  inline Own& operator=(Own&& other) {
179 180 181 182 183 184
    // Move-assingnment operator.

    // Careful, this might own `other`.  Therefore we have to transfer the pointers first, then
    // dispose.
    const Disposer* disposerCopy = disposer;
    T* ptrCopy = ptr;
185 186 187
    disposer = other.disposer;
    ptr = other.ptr;
    other.ptr = nullptr;
188 189 190
    if (ptrCopy != nullptr) {
      disposerCopy->dispose(const_cast<RemoveConst<T>*>(ptrCopy));
    }
191 192 193
    return *this;
  }

194 195 196 197 198
  inline Own& operator=(decltype(nullptr)) {
    dispose();
    return *this;
  }

199
  template <typename... Attachments>
200
  Own<T> attach(Attachments&&... attachments) KJ_WARN_UNUSED_RESULT;
201 202 203
  // Returns an Own<T> which points to the same object but which also ensures that all values
  // passed to `attachments` remain alive until after this object is destroyed. Normally
  // `attachments` are other Own<?>s pointing to objects that this one depends on.
204 205 206
  //
  // Note that attachments will eventually be destroyed in the order they are listed. Hence,
  // foo.attach(bar, baz) is equivalent to (but more efficient than) foo.attach(bar).attach(baz).
207

208 209 210 211 212 213 214 215 216 217 218 219 220 221 222
  template <typename U>
  Own<U> downcast() {
    // Downcast the pointer to Own<U>, destroying the original pointer.  If this pointer does not
    // actually point at an instance of U, the results are undefined (throws an exception in debug
    // mode if RTTI is enabled, otherwise you're on your own).

    Own<U> result;
    if (ptr != nullptr) {
      result.ptr = &kj::downcast<U>(*ptr);
      result.disposer = disposer;
      ptr = nullptr;
    }
    return result;
  }

223 224 225
#define NULLCHECK KJ_IREQUIRE(ptr != nullptr, "null Own<> dereference")
  inline T* operator->() { NULLCHECK; return ptr; }
  inline const T* operator->() const { NULLCHECK; return ptr; }
226 227
  inline _::RefOrVoid<T> operator*() { NULLCHECK; return *ptr; }
  inline _::RefOrVoid<const T> operator*() const { NULLCHECK; return *ptr; }
228
#undef NULLCHECK
229 230 231 232 233 234
  inline T* get() { return ptr; }
  inline const T* get() const { return ptr; }
  inline operator T*() { return ptr; }
  inline operator const T*() const { return ptr; }

private:
Kenton Varda's avatar
Kenton Varda committed
235
  const Disposer* disposer;  // Only valid if ptr != nullptr.
236 237
  T* ptr;

238
  inline explicit Own(decltype(nullptr)): disposer(nullptr), ptr(nullptr) {}
239

240 241 242 243
  inline bool operator==(decltype(nullptr)) { return ptr == nullptr; }
  inline bool operator!=(decltype(nullptr)) { return ptr != nullptr; }
  // Only called by Maybe<Own<T>>.

244 245 246
  inline void dispose() {
    // Make sure that if an exception is thrown, we are left with a null ptr, so we won't possibly
    // dispose again.
Kenton Varda's avatar
Kenton Varda committed
247
    T* ptrCopy = ptr;
248 249
    if (ptrCopy != nullptr) {
      ptr = nullptr;
250
      disposer->dispose(const_cast<RemoveConst<T>*>(ptrCopy));
251 252
    }
  }
253

254 255 256 257 258 259 260
  template <typename U>
  static inline T* cast(U* ptr) {
    static_assert(__is_polymorphic(T),
        "Casting owned pointers requires that the target type is polymorphic.");
    return ptr;
  }

261 262
  template <typename U>
  friend class Own;
263 264 265
  friend class Maybe<Own<T>>;
};

266
template <>
267 268 269
template <typename U>
inline void* Own<void>::cast(U* ptr) {
  return _::castToVoid(ptr);
270 271 272
}

template <>
273 274 275
template <typename U>
inline const void* Own<const void>::cast(U* ptr) {
  return _::castToConstVoid(ptr);
276 277
}

278
namespace _ {  // private
279 280

template <typename T>
281 282 283 284
class OwnOwn {
public:
  inline OwnOwn(Own<T>&& value) noexcept: value(kj::mv(value)) {}

Kenton Varda's avatar
Kenton Varda committed
285 286 287 288
  inline Own<T>& operator*() & { return value; }
  inline const Own<T>& operator*() const & { return value; }
  inline Own<T>&& operator*() && { return kj::mv(value); }
  inline const Own<T>&& operator*() const && { return kj::mv(value); }
289 290 291 292 293 294 295 296 297 298 299
  inline Own<T>* operator->() { return &value; }
  inline const Own<T>* operator->() const { return &value; }
  inline operator Own<T>*() { return value ? &value : nullptr; }
  inline operator const Own<T>*() const { return value ? &value : nullptr; }

private:
  Own<T> value;
};

template <typename T>
OwnOwn<T> readMaybe(Maybe<Own<T>>&& maybe) { return OwnOwn<T>(kj::mv(maybe.ptr)); }
300
template <typename T>
301
Own<T>* readMaybe(Maybe<Own<T>>& maybe) { return maybe.ptr ? &maybe.ptr : nullptr; }
302
template <typename T>
303
const Own<T>* readMaybe(const Maybe<Own<T>>& maybe) { return maybe.ptr ? &maybe.ptr : nullptr; }
304

305
}  // namespace _ (private)
306 307 308 309 310 311 312 313 314 315

template <typename T>
class Maybe<Own<T>> {
public:
  inline Maybe(): ptr(nullptr) {}
  inline Maybe(Own<T>&& t) noexcept: ptr(kj::mv(t)) {}
  inline Maybe(Maybe&& other) noexcept: ptr(kj::mv(other.ptr)) {}

  template <typename U>
  inline Maybe(Maybe<Own<U>>&& other): ptr(mv(other.ptr)) {}
316 317
  template <typename U>
  inline Maybe(Own<U>&& other): ptr(mv(other)) {}
318 319 320 321 322 323 324 325 326 327 328

  inline Maybe(decltype(nullptr)) noexcept: ptr(nullptr) {}

  inline operator Maybe<T&>() { return ptr.get(); }
  inline operator Maybe<const T&>() const { return ptr.get(); }

  inline Maybe& operator=(Maybe&& other) { ptr = kj::mv(other.ptr); return *this; }

  inline bool operator==(decltype(nullptr)) const { return ptr == nullptr; }
  inline bool operator!=(decltype(nullptr)) const { return ptr != nullptr; }

329 330 331 332 333 334 335 336 337 338 339 340 341 342 343
  Own<T>& orDefault(Own<T>& defaultValue) {
    if (ptr == nullptr) {
      return defaultValue;
    } else {
      return ptr;
    }
  }
  const Own<T>& orDefault(const Own<T>& defaultValue) const {
    if (ptr == nullptr) {
      return defaultValue;
    } else {
      return ptr;
    }
  }

344
  template <typename Func>
345
  auto map(Func&& f) & -> Maybe<decltype(f(instance<Own<T>&>()))> {
346 347 348
    if (ptr == nullptr) {
      return nullptr;
    } else {
349
      return f(ptr);
350 351 352 353
    }
  }

  template <typename Func>
354
  auto map(Func&& f) const & -> Maybe<decltype(f(instance<const Own<T>&>()))> {
355 356 357
    if (ptr == nullptr) {
      return nullptr;
    } else {
358
      return f(ptr);
359 360 361
    }
  }

362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378
  template <typename Func>
  auto map(Func&& f) && -> Maybe<decltype(f(instance<Own<T>&&>()))> {
    if (ptr == nullptr) {
      return nullptr;
    } else {
      return f(kj::mv(ptr));
    }
  }

  template <typename Func>
  auto map(Func&& f) const && -> Maybe<decltype(f(instance<const Own<T>&&>()))> {
    if (ptr == nullptr) {
      return nullptr;
    } else {
      return f(kj::mv(ptr));
    }
  }
379 380 381 382 383 384 385

private:
  Own<T> ptr;

  template <typename U>
  friend class Maybe;
  template <typename U>
386
  friend _::OwnOwn<U> _::readMaybe(Maybe<Own<U>>&& maybe);
387
  template <typename U>
388
  friend Own<U>* _::readMaybe(Maybe<Own<U>>& maybe);
389
  template <typename U>
390
  friend const Own<U>* _::readMaybe(const Maybe<Own<U>>& maybe);
391 392
};

393
namespace _ {  // private
394 395

template <typename T>
Kenton Varda's avatar
Kenton Varda committed
396
class HeapDisposer final: public Disposer {
397
public:
Kenton Varda's avatar
Kenton Varda committed
398
  virtual void disposeImpl(void* pointer) const override { delete reinterpret_cast<T*>(pointer); }
399

Kenton Varda's avatar
Kenton Varda committed
400
  static const HeapDisposer instance;
401 402
};

Kenton Varda's avatar
Kenton Varda committed
403 404 405
template <typename T>
const HeapDisposer<T> HeapDisposer<T>::instance = HeapDisposer<T>();

406
}  // namespace _ (private)
407 408 409 410 411

template <typename T, typename... Params>
Own<T> heap(Params&&... params) {
  // heap<T>(...) allocates a T on the heap, forwarding the parameters to its constructor.  The
  // exact heap implementation is unspecified -- for now it is operator new, but you should not
Kenton Varda's avatar
Kenton Varda committed
412 413
  // assume this.  (Since we know the object size at delete time, we could actually implement an
  // allocator that is more efficient than operator new.)
414

415
  return Own<T>(new T(kj::fwd<Params>(params)...), _::HeapDisposer<T>::instance);
Kenton Varda's avatar
Kenton Varda committed
416 417
}

Kenton Varda's avatar
Kenton Varda committed
418 419 420 421 422 423 424 425
template <typename T>
Own<Decay<T>> heap(T&& orig) {
  // Allocate a copy (or move) of the argument on the heap.
  //
  // The purpose of this overload is to allow you to omit the template parameter as there is only
  // one argument and the purpose is to copy it.

  typedef Decay<T> T2;
426
  return Own<T2>(new T2(kj::fwd<T>(orig)), _::HeapDisposer<T2>::instance);
Kenton Varda's avatar
Kenton Varda committed
427 428
}

429 430 431 432 433 434 435 436 437 438
// =======================================================================================
// SpaceFor<T> -- assists in manual allocation

template <typename T>
class SpaceFor {
  // A class which has the same size and alignment as T but does not call its constructor or
  // destructor automatically.  Instead, call construct() to construct a T in the space, which
  // returns an Own<T> which will take care of calling T's destructor later.

public:
439 440 441
  inline SpaceFor() {}
  inline ~SpaceFor() {}

442 443 444 445 446 447 448 449 450 451 452 453
  template <typename... Params>
  Own<T> construct(Params&&... params) {
    ctor(value, kj::fwd<Params>(params)...);
    return Own<T>(&value, DestructorOnlyDisposer<T>::instance);
  }

private:
  union {
    T value;
  };
};

Kenton Varda's avatar
Kenton Varda committed
454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475
// =======================================================================================
// Inline implementation details

template <typename T>
struct Disposer::Dispose_<T, true> {
  static void dispose(T* object, const Disposer& disposer) {
    // Note that dynamic_cast<void*> does not require RTTI to be enabled, because the offset to
    // the top of the object is in the vtable -- as it obviously needs to be to correctly implement
    // operator delete.
    disposer.disposeImpl(dynamic_cast<void*>(object));
  }
};
template <typename T>
struct Disposer::Dispose_<T, false> {
  static void dispose(T* object, const Disposer& disposer) {
    disposer.disposeImpl(static_cast<void*>(object));
  }
};

template <typename T>
void Disposer::dispose(T* object) const {
  Dispose_<T>::dispose(object, *this);
476 477
}

478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497
namespace _ {  // private

template <typename... T>
struct OwnedBundle;

template <>
struct OwnedBundle<> {};

template <typename First, typename... Rest>
struct OwnedBundle<First, Rest...>: public OwnedBundle<Rest...> {
  OwnedBundle(First&& first, Rest&&... rest)
      : OwnedBundle<Rest...>(kj::fwd<Rest>(rest)...), first(kj::fwd<First>(first)) {}

  // Note that it's intentional that `first` is destroyed before `rest`. This way, doing
  // ptr.attach(foo, bar, baz) is equivalent to ptr.attach(foo).attach(bar).attach(baz) in terms
  // of destruction order (although the former does fewer allocations).
  Decay<First> first;
};

template <typename... T>
498
struct DisposableOwnedBundle final: public Disposer, public OwnedBundle<T...> {
499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521
  DisposableOwnedBundle(T&&... values): OwnedBundle<T...>(kj::fwd<T>(values)...) {}
  void disposeImpl(void* pointer) const override { delete this; }
};

}  // namespace _ (private)

template <typename T>
template <typename... Attachments>
Own<T> Own<T>::attach(Attachments&&... attachments) {
  T* ptrCopy = ptr;

  KJ_IREQUIRE(ptrCopy != nullptr, "cannot attach to null pointer");

  // HACK: If someone accidentally calls .attach() on a null pointer in opt mode, try our best to
  //   accomplish reasonable behavior: We turn the pointer non-null but still invalid, so that the
  //   disposer will still be called when the pointer goes out of scope.
  if (ptrCopy == nullptr) ptrCopy = reinterpret_cast<T*>(1);

  auto bundle = new _::DisposableOwnedBundle<Own<T>, Attachments...>(
      kj::mv(*this), kj::fwd<Attachments>(attachments)...);
  return Own<T>(ptrCopy, *bundle);
}

522
}  // namespace kj