This article describes the Registry template, which is a container for registering and efficiently accessing objects that share a common base class.
Introduction
It is often desirable to access an object using an integral identifier. If a state machine, for example, defines an identifier for each state, event, and event handler, then given a pointer to its current state and an event to be processed, it can invoke the appropriate event handler as follows:
handlers_[states_[currState->id].handlerIds_[event->id]](…);
This article describes the Registry
template, a container that maps integral identifiers to objects. Because it uses an array, it requires less memory and provides faster insertions and lookups than std::map
, which uses a tree. I use Registry
often, falling back on map
when
- the object identifiers are not integers, or
- the array is sparse, or
- the template needs to store actual objects rather than pointers to them, which is what
Registry
does.
Sometimes, I even use the template for objects that don't have fixed identifiers; the template then assigns each object the identifier of the first available slot. If the registered objects are then displayed on the console, their identifiers can be used to refer to them in CLI commands.
Background
The Registry
template is taken from the Robust Services Core (RSC), an open-source framework for developing robust C++ applications. RSC contains many instances of this template, which typically serve one or more of the following purposes:
- to look up and display documentation or other information
- to display system capabilities
- to track or display system resources
- to access attributes provided by flyweights
- to access an abstract factory that is responsible for creating application-specific objects
The framework portions of RSC are defined by the directories nb (namespace
NodeBase
), nw (namespace
NetworkBase
), and sb (namespace
SessionBase
). The following table lists all of the classes that define a Registry
in those directories:
Registry | Registrants | Example of Use |
AlarmRegistry | Alarm | display the documentation for an alarm |
CliIncrement | CliCommand | display all commands available in a CLI increment |
CliRegistry | CliIncrement | display all increments available in the CLI |
CliText | CliParm | display the parameters for a CLI command |
CliTextParm | CliText | display the strings that are options for a CLI command |
DaemonRegistry | Daemon | recreate threads that were forced to exit |
LogGroup | Log | display the documentation for a log |
LogGroupRegistry | LogGroup | display the documentation for a log group |
ModuleRegistry | Module | display all static libraries |
MutexRegistry | SysMutex | display all mutexes |
ObjectPoolRegistry | ObjectPool | display all object pools |
PosixSignalRegistry | PosixSignal | access a POSIX signal's attributes |
StatisticsRegistry | Statistics | track all statistics |
StatisticsRegistry | StatisticsGroup | display a group of related statistics |
ToolRegistry | Tool | display all tools |
IpServiceRegistry | IpService | display all IP services |
FactoryRegistry | Factory | access a factory that creates messages and state machines |
InvokerPool | InvokerThread | track the threads that run an application |
InvokerPoolRegistry | InvokerPool | track the thread pools that run applications |
Protocol | Parameter | access a parameter's attributes |
Protocol | Signal | access a signal's attributes |
ProtocolRegistry | Protocol | access a protocol's attributes |
Service | EventHandler | access an application's event handlers |
Service | State | access an application's states |
Service | Trigger | access an application's observable events |
ServiceRegistry | Service | access one of the system's applications |
Using the Code
The code in this article has been edited to remove some things (function tracing and memory types) that are not relevant to the template's central purpose. These things appear in the full version of the code in the attached .zip file, so you can remove them if you're not using RSC.
Let's start by defining a type and null value for object identifiers. I chose 0
as the null value because
- it's a legal array index (just in case it happens to get used as such), and
- it always has the same bit pattern, even if it's truncated to a type that is smaller than
uint32_t
.
typedef uint32_t id_t; constexpr id_t NIL_ID = 0;
Objects stored in a Registry
usually provide a RegCell
member, which is used in two ways:
- Before the object registers with a template instance, it sets its
RegCell
member to its fixed identifier. The template then registers it against that identifier. - If the object does not have a fixed identifier, it simply registers. The template assigns it the first available identifier and updates its
RegCell
member accordingly.
class RegCell
{
template<class T> friend class Registry;
public:
RegCell() : id(NIL_ID), bound(false) { }
~RegCell() { if(bound) Debug::SwLog("item is still registered", id); }
RegCell(const RegCell& that) = delete;
RegCell& operator=(const RegCell& that) = delete;
void SetId(id_t cid)
{
if(bound)
Debug::SwLog("item already registered", pack2(id, cid));
else
id = cid;
}
id_t GetId() const { return id; }
std::string to_str() const
{
auto str = std::to_string(id);
if(!bound) str += " (not bound)";
return str;
}
private:
id_t id;
bool bound;
};
Now we can look at the Registry
template itself, starting with its data and special member functions:
template<class T> class Registry
{
public:
Registry() : size_(0), capacity_(0), max_(0),
diff_(NilDiff), delete_(false), registry_(nullptr) { }
~Registry()
{
if((delete_) && (capacity_ > 0)) Purge();
Memory::Free(registry_);
registry_ = nullptr;
}
Registry(const Registry& that) = delete;
Registry& operator=(const Registry& that) = delete;
private:
static const ptrdiff_t NilDiff = -1;
id_t size_;
id_t capacity_;
id_t max_;
ptrdiff_t diff_;
bool delete_;
T** registry_;
};
Before a Registry
can be used, its Init
function must be invoked to set a few attributes:
bool Init(id_t max, ptrdiff_t diff, bool del = true)
{
if(registry_ != nullptr)
{
Debug::SwLog("already initialized", max_);
return false;
}
if(diff < 0)
{
Debug::SwLog("no cell offset", diff);
return false;
}
max_ = (max == 0 ? 0 : max + 1);
diff_ = diff;
mem_ = mem;
delete_ = del;
if(max_ == 0) return true;
auto size = sizeof(T*) * ((max >> 3) + 2);
registry_ = (T**) Memory::Alloc(size);
capacity_ = (max >> 3) + 2;
for(id_t i = 0; i < capacity_; ++i) registry_[i] = nullptr;
return true;
}
To manipulate an object's RegCell
member, Registry
has to know where it is located. That is the purpose of diff_
, which is the distance (in bytes) from the beginning of the object to its RegCell
member. All the objects in the registry must use the same offset, so their common base class must define that offset.
The value of diff_
is returned by a grotty function that RSC classes always name CellDiff
. For example, RSC's Parameter
class is subclassed to define a flyweight for each parameter that can appear in a TLV-encoded message. It therefore needs a RegCell
member and a CellDiff
function that allows a Protocol
class to initialize a Registry
where the protocol's parameters will register. The outline (omitting other members) therefore looks like this:
Hide Copy Code
class Parameter : public Immutable
{
public:
static const id_t MaxId = 63;
static ptrdiff_t CellDiff() const;
protected:
Parameter(id_t prid, id_t pid); private:
RegCell pid_;
};
Parameter::Parameter(id_t prid, id_t pid)
{
pid_.SetId(pid);
auto reg = Singleton<ProtocolRegistry>::Instance();
auto pro = reg->GetProtocol(prid);
pro->BindParameter(*this);
}
ptrdiff_t Parameter::CellDiff()
{
uintptr_t local;
auto fake = reinterpret_cast<const Parameter*>(&local);
return ptrdiff(&fake->link_, fake);
}
class Protocol : public Immutable
{
public:
bool BindParameter(Parameter& parameter) { return parameters_.Insert(parameter); }
private:
Registry<Parameter> parameters_;
};
parameters_.Init(Parameter::MaxId, Parameter::CellDiff());
Once Init
has been invoked, the Registry
function Cell
can find the location of each element's RegCell
. This function is only used internally and is therefore private
:
RegCell* Cell(const T& item) const
{
if(diff_ <= 0)
{
Debug::SwLog("no cell offset", 0);
return nullptr;
}
if(&item == nullptr)
{
Debug::SwLog("invalid item", 0);
return nullptr;
}
return (RegCell*) getptr2(&item, diff_); }
Hide Copy Code
A Registry
owner provides functions for adding an item to, or removing it from, the registry. These functions (named Bind…
and Unbind…
by RSC classes) invoke the Insert
and Erase
functions provided by Registry
:
bool Insert(T& item)
{
auto cell = Cell(item);
if(cell == nullptr) return false;
if(cell->bound)
{
Debug::SwLog("already registered", cell->id);
if((cell->id == NIL_ID) || (cell->id >= capacity_)) return false;
return (registry_[cell->id] == &item);
}
if(cell->id == NIL_ID)
{
id_t start = 1;
if(size_ + 1 >= capacity_)
{
start = capacity_;
if(!Extend(capacity_)) return false;
}
for(auto i = start; i < capacity_; ++i)
{
if(registry_[i] == nullptr)
{
registry_[i] = &item;
cell->id = i;
cell->bound = true;
++size_;
return true;
}
}
return false;
}
if(cell->id >= capacity_)
{
if(!Extend(cell->id)) return false;
}
if(registry_[cell->id] != &item)
{
if(registry_[cell->id] != nullptr)
{
if(delete_)
{
Debug::SwLog("identifier in use", cell->id);
delete registry_[cell->id];
}
else
{
Erase(*registry_[cell->id]);
}
}
}
else
{
cell->bound = true;
return true;
}
registry_[cell->id] = &item;
cell->bound = true;
++size_;
return true;
}
bool Erase(T& item)
{
auto cell = Cell(item);
if(cell == nullptr) return false;
if(cell->id == NIL_ID) return false;
if(cell->id >= capacity_)
{
Debug::SwLog("invalid cell", cell->id);
return false;
}
if(registry_[cell->id] != &item)
{
Debug::SwLog("incorrect item", cell->id);
return false;
}
registry_[cell->id] = nullptr;
cell->id = NIL_ID;
cell->bound = false;
--size_;
return true;
}
Both Insert
and Erase
have a second version that is used when registrants do not define a RegCell
member. When a Registry
contains items of this type, diff
is set to 0
when invoking Init
, and registrants are added and removed using the alternate functions:
bool Insert(T& item, id_t id);
bool Erase(const T& item, id_t id);
Registry
also provides typical container functions for accessing, iterating through, and counting items. Iteration usually takes the form
for(auto item = reg_.First(); item != nullptr; reg_.Next(item))…
These functions are straightforward, so only their signatures are shown here:
T* At(id_t id) const;
T* First() const;
T* First(id_t& id) const;
void Next(T*& item) const;
T* Next(const T& item) const;
T* Next(id_t& id) const;
T* Last() const;
void Prev(T*& item) const;
T* Prev(const T& item) const;
id_t Size() const;
bool Empty() const;
Finally, there is the equivalent of clear
:
void Purge()
{
for(id_t i = capacity_ - 1; i > 0; --i)
{
auto& item = registry_[i];
if(item != nullptr)
{
if(diff_ > 0)
{
auto cell = (RegCell*) getptr2(item, diff_);
cell->bound = false;
}
delete item;
item = nullptr;
--size_;
}
}
}
History
- 18th June, 2020: Initial version