c++ - 确定性句柄分配算法

Question

我正在尝试找到一种有效的确定性方法来分配 32 位句柄，使其可以无限期地运行。一个简单的递增计数器将不起作用，因为它最终会循环。扩展到 64 位是不可能的，因为这些值将在需要 32 位值的网络协议(protocol)中使用。

它适用于实时系统，因此必须具有确定性和快速性。虽然它最终会出现在 SQLite 数据库中，但我不能在循环后暴力测试每个键，例如......

我想我需要的是某种范围树，它知道所有以前分配的句柄(在启动时填充它很好)。这似乎是一种常见的问题，但不是 boost 或 STL 可以解决的问题。

有什么建议吗？

编辑:一些额外的说明。我希望在任何时候在系统中拥有大约 200k 个事件句柄。句柄是随机删除的。

Answer 1

您不能分配超过 2^32。但是如果已使用的句柄被释放，您可以重新分配它们，问题是要跟踪空闲句柄。

树是存储空闲句柄的好方法。每个节点都有一个最低和最高句柄，左子树包含小于最低句柄的句柄，右子树包含大于最高句柄的句柄。

一个例子是:

            6-9
            / \
           2   15
          / \
         0   4

如果一个句柄被释放，它被存储在树中。例如，如果释放 10，则树看起来像:

            6-10
            / \
           2   15
          / \
         0   4

如果句柄 5 被释放，您可以选择优化树，因为 4 也可以添加到 5-10 节点:

            5-10
            / \
           2   15
          / \
         0   4

收件人:

            4-10
            / \
           2   15
          / 
         0  

一个句柄的分配，搜索一个有1个句柄的叶节点并将其从树中移除。如果没有带 1 个句柄的叶子，只需使用一个叶子并递减未连接到父节点的一侧:

         4-10
        /
      1-2

在上面的示例中，我们分配了 1 而不是 2，因为如果释放 3，您可以将它与 4 合并，并且您希望保持尽可能少的节点数。

下面是一个伪代码算法。部分内容留给读者:

Node = ( int lowest, highest; [Node] left, right)


Node.Allocate() 
  if TryFindLonelyLeaf(handle)    return handle;
  else
    return FindLeafHandle(NULL);

Node.TryFindLonelyLeaf(handle)
  if (left == NULL & right == NULL) 
    if (lowest == highest)
      handle == lowest;
      return TRUE;
    else
      return FALSE;
  if (left != NULL & left.TryFindLonelyLeaf(handle))
    if (left.lowest == handle) 
      left == NULL; // Free node
    return TRUE;
  elsif (right != NULL & right.TryFindLonelyLeaf(handle))
    if (right.lowest == handle)
       right = NULL; // Free node
    return TRUE;
  else
    return FALSE;

Node.FindLeafHhandle(parent)
  if (left == NULL & right == NULL) 
    if (parent == NULL | parent.right == this) 
      handle = lowest;
      lowest++;
    else
      handle = highest;
      highest--;
    return handle;
  else if (left != NULL) 
    return left.FindLeafHandle();
  else // right != NULL
    return right.FindLeafHandle();

Node.DeAllocate(handle) 
  Assert(handle<lowest or handle>highest);
  if (handle == lowest-1)
    lowest = CompactLeft(handle);
  elsif (handle == lowest+1)
    highest = CompactRight(handle); 
  elsif (handle<lowest)          
    if (left == NULL)
      left = (handle, handle, NULL, NULL);
    else
      left.DeAllocate(handle);
  elsif (handle>highest)
    if (right == NULL)
      right = (handle, handle, NULL, NULL);
    else
      right.DeAllocate(handle);
  else ERROR           

Node.CompactLeft(handle)
  if (highest == handle-1) 
    handle = lowest;
    // deallocate node and replace with left subtree
    return handle;
  elsif (right != NULL) 
    return right.CompactLeft(handle)
  else
    return handle;

Node.CompactRight(handle)
  if (lowest == handle+1) 
    handle = highest;
    // deallocate node and replace with right subtree
    return handle;
  elsif (left != NULL) 
    return left.CompactRight(handle)
  else
    return handle;