HandleDatabase#

Fully qualified name: carb::extras::HandleDatabase

template<class Mapped, class Handle, class Allocator = std::allocator<Mapped>, size_t IndexBits = 32, size_t LifecycleBits = 32> class HandleDatabase#

Provides an OS-style mapping of a Handle to a Resource.

Essentially HandleDatabase is a fast thread-safe reference-counted associative container.

A given Handle value is typically never reused, however, it is possible for a handle value to be reused if billions of handles are requested.

Thread Safety: Unless otherwise mentioned, HandleDatabase functions may be called simultaneously from multiple threads.

The HandleDatabase can store at most (2^31)-1 items, or 2,147,483,647 items simultaneously, provided the memory exists to support it.

Implementation Details

HandleDatabase achieves its speed and thread-safety by having a fixed-size base array (m_bucket) where the first index is a initial size, and each subsequent entry doubles the previous entry. These base arrays are never freed, simplifying thread safety and allowing HandleDatabase to be mostly lockless. This array-of-arrays forms a non-contiguous indexable array where the base array and offset can be computed from an index value (see indexToBucketAndOffset).

See below for how the handle bits are used.

Handles and sharing

Handles are essentially a non-counted weak referencing system where only the number of strong references are known. The number of weak references are not tracked. Once the number of strong references drops to zero, the handle is destroyed and will no longer be able to be used to access a mapped object.

The number of strong references belonging to a handle or mapped object can be obtained with HandleDatabase::debugGetRefCount().

However, HandleDatabase is thread-safe. In a multi-threaded environment the number of references can be changed by other threads at any time. This makes the reference count stale by the time it is read by the calling thread. For this reason it is not advised to use the number of reference counts in a multithreaded environment.

It can still be useful to know what the shared-state of a handle is. To determine this, call HandleDatabase::getSharedState() which returns a bitwise value of SharedState. When created, handles are considered to be SharedState::eNotShared and have a strong reference count of one. Whenever the reference count is above one, HandleDatabase::getSharedState() will report SharedState::eReferenced. If the handle was ever used to increment the reference count, or if the handle is explicitly marked as ‘shared’ with HandleDatabase::markShared(), then HandleDatabase::getSharedState() will include the SharedState::eMarkedShared bit as well. This bit means that the handle is valid and in use, so the number of weak references is not known. The SharedState::eMarkedShared bit remains for the lifetime of the handle.

Bit allocation

HandleDatabase always uses a 64-bit type as a key and opaquely controls the bits within those keys. The bits are divided up into two contiguous categories: Index and Lifecycle. For type safety, it is recommended to use an opaque pointer or a CARB_STRONGTYPE as a key since the value of the key is meaningless outside of HandleDatabase.

The total number of bits between Index and Lifecycle may not exceed 64. However, a minimum of 16 bits can be used. In this case only the least-significant bits of the handle will be used and the unused bits will be ignored, allowing an application to use these bits for other purposes.

The Index is used as a random access locator, such as an array index. By default the IndexBits template parameter is 32, meaning that 32 bits are allocated for Index. The maximum number of items is given by 2 ^ IndexBits - 1 and is available by getMaxSize(). The minimum number of bits for Index is 8, and the maximum is 32.

The Lifecycle is used as a check on the ownership of a handle. Every time an index is reused, the Lifecycle is incremented by one. Whenever a mapped value is found via its handle, the Lifecycle of the handle is checked against the current index’s lifecycle value. If the value doesn’t match current, the handle is stale or invalid and cannot be used to access the current index. When the Lifecycle value rolls over, an internal bit is permanently set to 1 indicating that all handle values that refer to the given index were previously valid (which enables functionality for handleWasValid()). This rollover bit is taken from the bits allocated for Lifecycle, but is not present in the lifecycle bits of the handle returned to the user. When the rollover bit is set, this means that handle values can then be re-used. Re-using handles increases the possibility of a stale handle being used to access a current value. By default, 32 bits are allocated for Lifecycle, meaning that an index must be reused 2^31 times before a handle will be re-used. A lower number of bits increases the likelihood of reusing a handle. The minimum number of bits for Lifecycle is 8, and the maximum is 32.

The Index portion is in the least significant bits of the handle, and the Lifecycle portion in the more significant portion above that. The remaining most-significant bits (if any) may be used by the application.

Template Parameters:

Mapped – The “value” type that is associated with a Handle.
Handle – The “key” type. Must be an unsigned integer or pointer type and 64-bit. This is an opaque type that cannot be dereferenced.
Allocator – The allocator that will be used to allocate memory. Must be capable of allocating large contiguous blocks of memory.
IndexBits – The number of bits to use for indexing. Must be at least 8 and may not exceed 32. Default is 32.
LifecycleBits – The number of bits to use for handle lifecycle. Must be at least 8 and may not exceed 32. One of the bits allocated here is reserved as a rollover flag. Default is 32.

Public Types

using MappedType = Mapped #: An alias to Mapped; the mapped value type.

using HandleType = Handle #: An alias to Handle; the key type used to associate a mapped value type.

using AllocatorType = Allocator #: An alias to Allocator; the allocator used to allocate memory.

using HandleRefType = HandleRef<Mapped, Handle, Allocator, IndexBits, LifecycleBits>#: An alias to the HandleRef for this HandleDatabase.

using ConstHandleRefType = ConstHandleRef<Mapped, Handle, Allocator, IndexBits, LifecycleBits>#: An alias to the ConstHandleRef for this HandleDatabase.

using scoped_handle_ref_type = HandleRefType #: Deprecated: Use HandleRefType instead.

Public Functions

inline constexpr HandleDatabase() noexcept#

Constructor.

Thread Safety: The constructor must complete in a single thread before any other functions may be called on *this.

inline ~HandleDatabase()#

Destructor.

Thread Safety: All other functions on *this must be finished before the destructor can be called.

inline bool handleWasValid(Handle handle) const#

Checks to see if a handle is valid or was ever valid in the past.

Parameters:: handle – The Handle to check.
Returns:: true if a handle is currently valid or was valid in the past and has since been released; false otherwise.

inline bool handleIsValid(Handle handle) const#

Checks to see if a handle is currently valid.

Parameters:: handle – The Handle to check.
Returns:: true if a handle is currently valid; false otherwise.

template<class ...Args> inline std::pair<Handle, Mapped*> createHandle( Args&&... args, )#

Creates a new Mapped type with the given arguments.

Parameters:: args – The arguments to pass to the Mapped constructor.
Returns:: A std::pair of the Handle that can uniquely identify the new Mapped type, and a pointer to the newly constructed Mapped type.

inline Mapped *getValueFromHandle(Handle handle) const#

Attempts to find the Mapped type represented by handle.

Thread Safety: Not thread-safe as the Mapped type could be destroyed if another thread calls release().

Warning

This function should not be used unless the thread calling it holds a reference count. It is recommended instead to use makeScopedRef() to validate the handle and add a reference.

Parameters:: handle – A handle previously returned from createHandle(). Invalid or previously-valid handles will merely result in a nullptr result without an assert or any other side-effects.
Returns:: A pointer to a valid Mapped type if the handle was valid; nullptr otherwise.

inline Handle getHandleFromValue(const Mapped *mapped) const#

Retrieves the Handle representing mapped.

Parameters:: mapped – A pointer to the mapped type. If nullptr, mapped has been fully released, or mapped is not owned by *this, behavior is undefined.
Returns:: The Handle representing mapped.

inline Mapped *tryAddRef(Handle handle, size_t *outRefCount = nullptr)#

Atomically attempts to add a reference for the given Handle.

Note

This operation, if successful, implicitly marks a handle as shared as via markShared().

Parameters:

handle – A handle previously returned from createHandle(). Invalid or previously-valid handles will merely result in a nullptr result without an assert or any other side-effects.
outRefCount – (Optional) If non-nullptr, will receive the new reference count provided that the function returns a non-nullptr value. If the function returns nullptr, this value is unchanged. Note however that reference counts can be changed by other threads, so this value may be stale before it is read by the calling thread.

Returns:

A pointer to a valid Mapped type if a reference could be added; nullptr otherwise.

inline size_t addRef(Handle handle)#

Atomically adds a reference for the given Handle; fatal if handle is invalid.

Note

This operation implicitly marks a handle as shared as via markShared().

Parameters:: handle – A valid handle previously returned from createHandle(). Invalid or previously-valid handles will result in std::terminate() being called.
Returns:: The new reference count. Note however that reference counts can be changed by other threads, so this value may be stale before it is read by the calling thread.

inline size_t addRef(Mapped *mapped)#

Atomically adds a reference for the Handle representing mapped.

Note

This operation does not mark the handle representing mapped as shared per markShared().

Parameters:: mapped – A pointer to the mapped type. If nullptr, mapped has been fully released, or mapped is not owned by *this, behavior is undefined.
Returns:: The new reference count. Note however that reference counts can be changed by other threads, so this value may be stale before it is read by the calling thread.

inline bool release(Handle handle)#

Atomically releases a reference for the given Handle, potentially freeing the associated Mapped type.

Parameters:: handle – A valid handle previously returned from createHandle(). Invalid or previously-valid handles will result in an assert in Debug builds, but return false with no side effects in Release builds.
Returns:: true if the last reference was released and handle is no longer valid; false if Handle is not valid or is previously-valid or a non-final reference was released.

inline bool release(Mapped *mapped)#

Atomically releases a reference for the Handle representing mapped.

Parameters:: mapped – A pointer to the mapped type. If nullptr, mapped has been fully released, or mapped is not owned by *this, behavior is undefined.
Returns:: true if the last reference was released and mapped is no longer valid; false if a reference other than the last reference was released.

inline bool releaseIfLastRef(Handle handle)#

Atomically releases a reference if and only if it’s the last reference.

Parameters:: handle – A valid handle previously returned from createHandle(). Invalid or previously-valid handles will result in an assert in Debug builds, but return false with no side effects in Release builds.
Returns:: true if the last reference was released and handle is no longer valid; false otherwise.

inline bool releaseIfLastRef(Mapped *mapped)#

Atomically releases a reference if and only if it’s the last reference.

Parameters:: mapped – A pointer to the mapped type. If nullptr, mapped has been fully released, or mapped is not owned by *this, behavior is undefined.
Returns:: true if the last reference was released and mapped is no longer valid; false otherwise.

inline HandleRefType makeScopedRef(Handle handle)#

Attempts to atomically add a reference to handle, and returns a HandleRef to handle.

Parameters:: handle – A handle previously returned from createHandle(). Invalid or previously-valid handles will merely result in an empty HandleRef result without an assert or any other side-effects.
Returns:: If tryAddRef() would return a valid Mapped type for handle, then a HandleRef that manages the reference is returned; otherwise an empty HandleRef is returned.

inline ConstHandleRefType makeScopedRef(Handle handle) const#

Attempts to atomically add a reference to handle, and returns a ConstHandleRef to handle.

Parameters:: handle – A handle previously returned from createHandle(). Invalid or previously-valid handles will merely result in an empty ConstHandleRef result without an assert or any other side-effects.
Returns:: If tryAddRef() would return a valid Mapped type for handle, then a ConstHandleRef that manages the reference is returned; otherwise an empty ConstHandleRef is returned.

template<class Func> inline void forEachHandle(Func &&f) const#

Calls the provided Func invocable object for each valid handle and its associated mapped type.

Thread Safety: The Mapped* passed to f is not safe to use if any other thread would be calling releaseIfLastRef() or release() to release the last reference of a Handle. In these situations it is instead recommended to try to add a reference to the Handle passed to f in order to assure validity.

Parameters:: f – An invocable object with signature void(Handle, Mapped*). Note that there also exists a version of forEachHandle that can accept bool(Handle, Mapped*) and can early out. Technically any non-bool return type is allowed but any return values are ignored. It is highly recommended to ignore the Mapped* unless it is guaranteed that no other threads may be modifying the HandleDatabase, in which case it is recommend to instead try to add a reference to the Handle in order to assure validity.

template<class Func> inline bool forEachHandle(Func &&f) const#

Calls the provided Func invocable object for each valid handle and its associated mapped type until the invocable object returns false.

Thread Safety: The Mapped* passed to f is not safe to use if any other thread would be calling releaseIfLastRef() or release() to release the last reference of a Handle. In these situations it is instead recommended to try to add a reference to the Handle passed to f in order to assure validity.

Parameters:: f – An invocable object with signature bool(Handle, Mapped*). If the invocable object returns false, iteration terminates immediately and returns false. It is highly recommended to ignore the Mapped* unless it is guaranteed that no other threads may be modifying the HandleDatabase, in which case it is recommend to instead try to add a reference to the Handle in order to assure validity.
Returns:: true if iteration completed over the entirety of *this; false if f returned false causing iteration to be aborted early.

inline size_t clear()#

Iterates over all valid handles and sets their reference counts to zero, destroying the associated mapped type.

Thread Safety: This function is NOT safe to call if any other thread is calling ANY other HandleDatabase function except for clear() or handleWasValid().

Returns:: The number of handles that were released to zero.

inline void awaitFinalRelease(Handle h) const#

Causes the calling thread to wait until the given handle has been fully released.

Parameters:: h – The handle to wait for.

inline cpp::optional<size_t> debugGetRefCount( Handle handle, ) const noexcept#

Retrieves the reference count (debugging only).

Obtains the reference count observed by the calling thread at the time of function call. Since handles are effectively weak references, even a returned reference count of 1 does not guarantee that the object is owned only by the calling thread. To safely determine if an entry is shared, use getSharedState().

See also

getSharedState()

Warning

This function should be used for debugging only. Other threads may change the reference count by handle which makes the return value of this function possibly stale at the time the calling thread reads it.

Parameters:: handle – The handle.
Returns:: A cpp::optional containing the reference count observed. If handle is not valid, cpp::nullopt is returned.

inline size_t debugGetRefCount(const Mapped *mapped) const noexcept#

Retrieves the reference count (debugging only).

Obtains the reference count observed by the calling thread at the time of function call. Since handles are effectively weak references, even a returned reference count of 1 does not guarantee that the object is owned only by the calling thread. To safely determine if an entry is shared, use getSharedState().

See also

getSharedState()

Warning

This function should be used for debugging only. Other threads may change the reference count by handle which makes the return value of this function possibly stale at the time the calling thread reads it.

Parameters:: mapped – A pointer to the mapped type. If nullptr, mapped has been fully released, or mapped is not owned by *this, behavior is undefined.
Returns:: The reference count observed.

inline bool markShared( Handle handle, bool *previouslyShared = nullptr, ) noexcept#

Explicitly and atomically marks a handle as shared.

A shared handle means that it has been returned outside of the system that manages the handle and the reference count of the handle may be changed at any point by another thread. Once a handle is marked shared by this function, it will remain shared for its entire lifetime.

Parameters:

handle – The handle to validate and mark as shared.
previouslyShared – (Optional) If provided, receives the previous shared state.

Return values:

true – If *previouslyShared was false, the handle is valid and has been marked as shared. If *previouslyShared was true, handle appears to be valid at the time this function was called.
false – The handle is not valid. previouslyShared (if provided) is unchanged.

inline void markShared( Mapped *mapped, bool *previouslyShared = nullptr, ) noexcept#

Explicitly and atomically marks the handle referring to a mapped object as shared.

A shared handle means that it has been returned outside of the system that manages the handle and the reference count of the handle may be changed at any point by another thread. Once a handle is marked shared by this function, it will remain shared for its entire lifetime.

Parameters:

mapped – A pointer to the mapped type. If nullptr, mapped has been fully released, or mapped is not owned by *this, behavior is undefined.
previouslyShared – (Optional) If provided, receives the previous shared state.

inline cpp::optional<SharedState> getSharedState( Handle handle, ) const noexcept#

Tests a handle for validity and whether that handle is shared.

See also

markShared() SharedState

Parameters:: handle – The handle to validate and check.
Returns:: cpp::nullopt if the handle is not valid. Otherwise a SharedState value indicating how the handle is shared.

inline SharedState getSharedState( const Mapped *mapped, ) const noexcept#

Tests whether a mapped entry is shared.

See also

markShared() SharedState

Parameters:: mapped – A pointer to the mapped type. If nullptr, mapped has been fully released, or mapped is not owned by *this, behavior is undefined.
Returns:: A SharedState value indicating how the handle is shared.

inline constexpr size_t getMaxSize() const noexcept#

Returns the maximum number of items that can be contained in this HandleDatabase.

Returns:: The maximum number of items that can be contained in *this.

Public Static Attributes

static constexpr size_t kIndexBits = IndexBits #: The number of bits used for index and given by the class template parameter IndexBits.

static constexpr size_t kLifecycleBits = LifecycleBits #: The number of bits used for lifecycle and given by the class template parameter LifecycleBits.