确定性句柄分配算法

分配不能超过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;

如果内存不是问题,那么您可以维护一个空闲句柄列表。当释放一个时,您将它添加回自由列表的末尾。

在开始时,您可以将所有ID添加到空闲列表中,但这样做效率很低。

您可以做的优化是维护一个可用的最小ID值以及空闲列表。因此,当列表为空时,您可以向自由列表添加一些ID(从维护的最小ID值开始),并更新最小ID值。

如果这个问题仅仅是“我如何快速、安全地计算出一个唯一的、目前没有使用过的数字”,那么一个小表格就会给出这个答案。

对于20万个唯一数字的顺序,200.000/8=需要的字节数=2.5万,这只需要25千字节的内存来跟踪。

当然,如果您需要在内存中跟踪与正在使用的句柄相关联的数据,那么您还需要其他东西。

另一个解决方案是保留一堆未使用的句柄,这可能会更快地获得一个新的句柄。每次你需要一个手柄,就从堆栈中弹出一个。

您可以用一个设定的数字为堆栈种子,但是算法也可以这样,如果您试图从空堆栈中弹出一个值,您只需通过增加一个不断增加的值来生成一个新的值。

既然您说在任何给定的时间内都将有大约20万个句柄处于活动状态,那么这个堆栈的大小永远不应该超过容纳那么多句柄的大小,所以您可以使用数组轻松地处理这个问题。一个200K的32位堆栈将消耗800.000字节,大约781KB的内存。