多态对象的模板
注册并高效访问多态对象。
引言
通常希望使用整数标识符来访问对象。例如，如果一个状态机为每个状态、事件和事件处理程序定义了一个标识符，那么给定指向其当前状态的指针和一个要处理的事件，它可以如下调用适当的事件处理程序：
handlers_[states_[currState->id].handlerIds_[event->id]](…);
本文介绍了 Registry 模板，它是一个将整数标识符映射到对象的容器。因为它使用数组，所以与使用树的 std::map 相比，它占用的内存更少，并且插入和查找速度更快。我经常使用 Registry，但在以下情况下会回退到 map：
- 对象标识符不是整数，或者
- 数组是稀疏的，或者
- 模板需要存储实际对象而不是指向它们的指针，而
Registry就是这样做的。
有时，我甚至会为没有固定标识符的对象使用该模板；然后，模板会为每个对象分配第一个可用槽的标识符。如果注册的对象随后显示在控制台上，则可以使用它们的标识符在 CLI 命令中引用它们。
背景
Registry 模板取自 Robust Services Core (RSC)，这是一个用于开发健壮 C++ 应用程序的开源框架。RSC 包含该模板的许多实例，它们通常用于一个或多个以下目的：
- 查找和显示文档或其他信息
- 显示系统功能
- 跟踪或显示系统资源
- 访问 flyweight 提供的属性
- 访问负责创建应用程序特定对象的抽象工厂
RSC 的框架部分由目录 nb (namespace NodeBase)、nw (namespace NetworkBase) 和 sb (namespace SessionBase) 定义。下表列出了在这些目录中定义 Registry 的所有类。
| 注册表 | 注册者 | 使用示例 |
AlarmRegistry | Alarm | 显示警报文档 |
CliIncrement | CliCommand | 显示 CLI increments 中所有可用的命令 |
CliRegistry | CliIncrement | 显示 CLI 中所有可用的 increments |
CliText | CliParm | 显示 CLI 命令的参数 |
CliTextParm | CliText | 显示 CLI 命令的字符串选项 |
DaemonRegistry | Daemon | 重新创建被强制退出的线程 |
LogGroup | Log | 显示日志文档 |
LogGroupRegistry | LogGroup | 显示日志组文档 |
ModuleRegistry | 模块 | 显示所有静态库 |
MutexRegistry | SysMutex | 显示所有互斥锁 |
ObjectPoolRegistry | ObjectPool | 显示所有对象池 |
PosixSignalRegistry | PosixSignal | 访问 POSIX 信号的属性 |
StatisticsRegistry | 统计 | 跟踪所有统计数据 |
StatisticsRegistry | StatisticsGroup | 显示一组相关的统计数据 |
ToolRegistry | 工具 | 显示所有工具 |
IpServiceRegistry | IpService | 显示所有 IP 服务 |
FactoryRegistry | Factory | 访问用于创建消息和状态机的工厂 |
InvokerPool | InvokerThread | 跟踪运行应用程序的线程 |
InvokerPoolRegistry | InvokerPool | 跟踪运行应用程序的线程池 |
协议 | 参数 | 访问参数的属性 |
协议 | 信号 | 访问信号的属性 |
ProtocolRegistry | 协议 | 访问协议的属性 |
Service | EventHandler | 访问应用程序的事件处理程序 |
Service | 状态 | 访问应用程序的状态 |
Service | 触发器 | 访问应用程序的可观察事件 |
ServiceRegistry | Service | 访问系统的一个应用程序 |
Using the Code
本文中的代码已编辑，移除了与模板核心目的无关的内容（函数跟踪和内存类型）。这些内容出现在附件 .zip 文件中完整代码版本里，因此如果您不使用 RSC，可以将其删除。
首先，让我们为对象标识符定义一个类型和空值。我选择 0 作为空值，因为
- 它是一个合法的数组索引（以防万一它被用作数组索引），并且
- 它始终具有相同的位模式，即使它被截断为小于
uint32_t的类型。
typedef uint32_t id_t; // identifier for an object in a Registry
constexpr id_t NIL_ID = 0; // nil identifier
存储在 Registry 中的对象通常提供一个 RegCell 成员，它有两种用途：
- 在对象注册到模板实例之前，它将其
RegCell成员设置为其固定标识符。然后，模板会根据该标识符注册它。 - 如果对象没有固定标识符，它只需注册。模板会为其分配第一个可用标识符，并相应地更新其
RegCell成员。
// Tracks the index at which an object was added to a registry's array. An
// object that resides in a registry usually includes this as a member and
// implements a CellDiff function that returns the distance between the top
// of the object and its RegCell member. However, Registry also supports
// registrants without RegCell members.
//
class RegCell
{
template<class T> friend class Registry;
public:
// Until an object is registered, it has a nil identifier and has not
// been bound to the registry.
//
RegCell() : id(NIL_ID), bound(false) { }
// Before an object is destroyed, it should have been removed from the
// registry.
//
~RegCell() { if(bound) Debug::SwLog("item is still registered", id); }
// Deleted to prohibit copying.
//
RegCell(const RegCell& that) = delete;
RegCell& operator=(const RegCell& that) = delete;
// Before an object is registered, this function allow its index within
// the registry (and therefore its identifier) to be specified. This is
// important for an object whose identifier must be fixed (because it is
// included in an interprocessor protocol, for example).
//
void SetId(id_t cid)
{
if(bound)
Debug::SwLog("item already registered", pack2(id, cid));
else
id = cid;
}
// Returns the object's index (identifier) within the registry.
//
id_t GetId() const { return id; }
// Returns a string for displaying the cell.
//
std::string to_str() const
{
auto str = std::to_string(id);
if(!bound) str += " (not bound)";
return str;
}
private:
// The object's index (identifier) within the registry's array.
//
id_t id;
// Set when the object is added to the registry. Cleared when the
// object is deregistered.
//
bool bound;
};
现在我们可以看看 Registry 模板本身，首先是它的数据和特殊成员函数。
// A registry tracks objects derived from a common base class. It uses
// an array to save a pointer to each object that has been added to the
// registry. The array index at which an object is registered also acts
// as an identifier for the object. The first entry in the array is not
// used and corresponds to NIL_ID (a nil object or nullptr).
//
template<class T> class Registry
{
public:
// Creates an empty registry.
//
Registry() : size_(0), capacity_(0), max_(0),
diff_(NilDiff), delete_(false), registry_(nullptr) { }
// Deletes the objects in the registry (unless this action was not
// desired) and the deletes the registry's array.
//
~Registry()
{
if((delete_) && (capacity_ > 0)) Purge();
Memory::Free(registry_);
registry_ = nullptr;
}
// Deleted to prohibit copying.
//
Registry(const Registry& that) = delete;
Registry& operator=(const Registry& that) = delete;
private:
// For initializing diff_.
//
static const ptrdiff_t NilDiff = -1;
// The number of items currently in the registry.
//
id_t size_;
// The current size of the registry.
//
id_t capacity_;
// The maximum size allowed for the registry.
//
id_t max_;
// The distance from a pointer to an item in the registry and its RegCell
// member.
//
ptrdiff_t diff_;
// Set if items in the registry should be deleted when overwritten or
// when the registry itself is deleted.
//
bool delete_;
// The registry, which is a dynamic array of pointers to registered items.
//
T** registry_;
};
在使用 Registry 之前，必须调用其 Init 函数来设置一些属性。
// Allocates memory for the registry's array. MAX is the maximum number
// of objects that can register. All objects must derive from the same
// base class, with DIFF being the distance from the top of that base
// class to the RegCell member that tracks an object's location in the
// registry. DEL is true if objects should be deleted when the registry
// is deleted. This is typical but would be prevented, for example, if
// the objects were also added to another registry. In such a case, the
// objects would require one RegCell member per registry. Alternatively,
// the second version of the Insert function could be used, as it does
// not require a RegCell member.
//
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;
}
为了操作对象的 RegCell 成员，Registry 需要知道它在哪里。这就是 diff_ 的作用，它是从对象开始到其 RegCell 成员的距离（以字节为单位）。注册表中的所有对象都必须使用相同的偏移量，因此它们的共同基类必须定义该偏移量。
diff_ 的值由一个粗糙的函数返回，RSC 类总是将其命名为 CellDiff。例如，RSC 的 Parameter 类被子类化，为可能出现在 TLV 编码消息中的每个参数定义一个 flyweight。因此，它需要一个 RegCell 成员和一个 CellDiff 函数，允许 Protocol 类初始化一个 Registry，协议的参数将在其中注册。因此，大纲（省略其他成员）如下所示：
隐藏 复制代码
class Parameter : public Immutable
{
public:
static const id_t MaxId = 63;
static ptrdiff_t CellDiff() const;
protected:
Parameter(id_t prid, id_t pid); // protocol and parameter identifiers
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()); // in Protocol's constructor
调用 Init 后，Registry 函数 Cell 可以找到每个元素的 RegCell 的位置。此函数仅用于内部，因此它是 private 的。
// Returns ELEM's cell location.
//
RegCell* Cell(const T& item) const
{
// Ensure that the registry has been initialized with a RegCell offset.
//
if(diff_ <= 0)
{
Debug::SwLog("no cell offset", 0);
return nullptr;
}
// Ensure that ITEM is valid.
//
if(&item == nullptr)
{
Debug::SwLog("invalid item", 0);
return nullptr;
}
return (RegCell*) getptr2(&item, diff_); // adds diff_ to &item
}
隐藏 复制代码
Registry 所有者提供用于将项添加到注册表或从中删除的函数。这些函数（在 RSC 类中命名为 Bind… 和 Unbind…）调用 Registry 提供的 Insert 和 Erase 函数。
// Adds ITEM, which contains a RegCell member, to the registry.
//
bool Insert(T& item)
{
// Ensure that ITEM has not already been registered.
//
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 the item has a nil identifier, assign it to any available slot.
// If no slots remain, extend the size of the array.
//
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 the item has a fixed identifier, assign it to that slot. The
// array may first have to be extended. If the slot is currently
// occupied, generate a log and delete the occupant unless this is
// a re-registration.
//
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;
}
// Removes ITEM, which contains a RegCell member, from the registry.
//
bool Erase(T& item)
{
// If ITEM has been registered, remove it from the registry.
//
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;
}
对于不定义 RegCell 成员的注册者，Insert 和 Erase 都有第二个版本。当 Registry 包含此类项时，在调用 Init 时将 diff 设置为 0，并使用备用函数添加和删除注册者。
// Adds ITEM to the registry in the slot specified by ID. This
// function is used with ITEM does not contain a RegCell member.
//
bool Insert(T& item, id_t id);
// Removes ITEM from the slot specified by ID. This function is
// used when ITEM does not contain a RegCell member.
//
bool Erase(const T& item, id_t id);
Registry 还提供用于访问、迭代和计数项的典型容器函数。迭代通常采用以下形式：
for(auto item = reg_.First(); item != nullptr; reg_.Next(item))…
这些函数很简单，因此此处仅显示其签名。
// Returns the item registered against ID.
//
T* At(id_t id) const;
// Returns the first item in the registry.
//
T* First() const;
// Returns the first item at ID or higher.
//
T* First(id_t& id) const;
// Updates ITEM to the next item in the registry.
//
void Next(T*& item) const;
// Returns the first item that follows ITEM.
//
T* Next(const T& item) const;
// Returns the first item that follows the slot identified by ID.
//
T* Next(id_t& id) const;
// Returns the last item in the registry.
//
T* Last() const;
// Updates ITEM to the previous item in the registry.
//
void Prev(T*& item) const;
// Returns the first item that precedes ITEM.
//
T* Prev(const T& item) const;
// Returns the number of items in the registry.
//
id_t Size() const;
// Returns true if the registry is empty.
//
bool Empty() const;
最后，有一个等同于 clear 的功能。
void Purge()
{
for(id_t i = capacity_ - 1; i > 0; --i)
{
// Clear the RegCell's bound flag so that its destructor won't
// generate a log.
//
auto& item = registry_[i];
if(item != nullptr)
{
if(diff_ > 0)
{
auto cell = (RegCell*) getptr2(item, diff_);
cell->bound = false;
}
delete item;
item = nullptr;
--size_;
}
}
}
历史
- 2020 年 6 月 18 日：初始版本