dfx::Utils::RecyclableIdAllocator< T > Class Template Reference

ID allocator that can recycle released identifiers. More...

#include <dfx-utilities/RecyclableIdAllocator.hpp>

Public Types
using	value_type = T
	Type used for allocated identifiers.

Public Member Functions
value_type	next () noexcept
	Allocate and return an identifier.
void	release (value_type id)
	Release an identifier back to the allocator.
void	reserve (value_type id)
	Mark an identifier as in-use without returning it from next().
void	reset () noexcept
	Reset the allocator to its initial state.

Detailed Description

template<std::integral T>
class dfx::Utils::RecyclableIdAllocator< T >

ID allocator that can recycle released identifiers.

RecyclableIdAllocator hands out integral identifiers and supports releasing them back to the allocator so they can be reused later.

Allocation strategy

• If there are released IDs available, next() returns the smallest released ID first (min-heap behavior).
• Otherwise, next() returns the current end-of-sequence ID and increments it.

Release strategy

• Releasing the most recently allocated end-of-sequence ID may "shrink" the _nextId counter (cheap, no heap usage).
• Releasing an older ID inserts it into an internal min-heap so it can be reused later.

Automatic full reset

When the allocator observes that all allocated/reserved IDs have been released (tracked via an internal active counter), it automatically resets itself back to the initial state. This keeps memory usage bounded and avoids retaining large free-lists after bursty allocations.

Template Parameters

T	Integral type used for identifiers (e.g. uint32_t, uint64_t).

Note

This class is not thread-safe. Concurrent calls to next(), release(), reserve() or reset() require external synchronization.

Warning

No overflow protection is provided. If the counter overflows, identifiers wrap around and uniqueness is lost.

release() is intentionally forgiving and will silently ignore invalid frees and double frees. This is convenient for some workflows, but it also means that bugs may go unnoticed. If you want strict behavior, change those early returns to assertions/exceptions in your project.

Complexity

• next() is O(1) when no recycling occurs, otherwise O(log n).
• release() is O(1) for end-of-sequence IDs, otherwise O(log n).
• reserve() is:
  • O(k log n) when reserving beyond the current range (fills a gap of size k),
  • O(n) when removing an ID from the heap (heap rebuild) for an existing free ID.

Example

dfx::Utils::RecyclableIdAllocator<uint32_t> ids;
 
auto a = ids.next();   // 0
auto b = ids.next();   // 1
ids.release(a);        // 0 becomes available again
 
auto c = ids.next();   // 0 (recycled smallest free)

Member Typedef Documentation

value_type

template<std::integral T>

using dfx::Utils::RecyclableIdAllocator< T >::value_type = T

Type used for allocated identifiers.

Member Function Documentation

next()

template<std::integral T>

value_type dfx::Utils::RecyclableIdAllocator< T >::next ( )

inlinenoexcept

Allocate and return an identifier.

If there are released IDs, returns the smallest available released ID. Otherwise returns the next fresh ID from the end-of-sequence counter.

Returns

A currently unused identifier.

Note

This function does not fail and is noexcept.

release()

template<std::integral T>

void dfx::Utils::RecyclableIdAllocator< T >::release ( value_type id )

inline

Release an identifier back to the allocator.

After release(id), the allocator may return id again in a future call to next().

Behavior details:

• If id was never allocated/reserved by this allocator (i.e. id >= _nextId), the call is ignored.
• If id has already been released (double-free), the call is ignored.
• If this release makes the active count reach zero, the allocator performs a full reset() (drops all internal state).
• If id is the last end-of-sequence ID (i.e. _nextId == id + 1), the allocator shrinks _nextId instead of inserting into the heap.

Parameters

id	Identifier to release.

Note

This function is not noexcept because it may use the heap (push into the priority queue / unordered_set).

reserve()

template<std::integral T>

void dfx::Utils::RecyclableIdAllocator< T >::reserve ( value_type id )

inline

Mark an identifier as in-use without returning it from next().

This is useful when you need to "skip" or "pin" a specific ID because it is already used externally (e.g. restoring from persisted state, importing objects with fixed IDs, or reserving a well-known ID).

Two cases:

• If id is beyond the current allocation range (id >= _nextId), the allocator:
  • adds every ID in [_nextId, id) to the free lists,
  • advances _nextId to id + 1,
  • and counts id as active (reserved).
• If id is within range (id < _nextId), then id must currently be free (previously released). In that case it is removed from the free lists.

Parameters

id	Identifier to reserve.

Exceptions

Whatever

B_ASSERT throws/aborts with if id < _nextId but the ID is not actually free.

Note

Removing an existing free ID from the heap is O(n) because std::priority_queue does not support erase; the heap is rebuilt.

reset()

template<std::integral T>

void dfx::Utils::RecyclableIdAllocator< T >::reset ( )

inlinenoexcept

Reset the allocator to its initial state.

After reset(), the next call to next() returns 0.

This clears:

• the end-of-sequence counter,
• the active allocation/reservation count,
• and all recycled ID tracking structures.

Note

This can make previously issued IDs appear again. Only call reset() when you can guarantee no outstanding IDs are still in use.

---

The documentation for this class was generated from the following file:

• lib/dfx-utilities/RecyclableIdAllocator.hpp