確定的ハンドル割り当てアルゴリズム

Question

32ビットハンドルを無期限に動作するような方法で割り当てる効率的な決定論的な方法を見つけようとしています。単純な増分カウンタは、最終的にループするため機能しません。 64ビットに拡張することはできません。値は、32ビット値を想定しているネットワークプロトコルで使用されるためです。

リアルタイムシステム用であるため、確定的で迅速でなければなりません。最終的にSQLiteデータベースになりますが、たとえばループ後の各キーを総当たりでテストすることはできません...

必要なのは、以前に割り当てられたすべてのハンドルについて知っているある種の範囲ツリーだと思います（起動時にこれを設定するのは問題ありません）。これはありふれた問題のようですが、ブーストやSTLによって解決される問題ではありません。

任意のポインター？

編集：いくつかの追加の説明。私はいつでもシステムに200kオーダのアクティブなハンドルを持っていることを探しています。ハンドルはランダムに削除されます。

Answer 1

2 ^ 32を超える割り当てはできません。ただし、使用済みのハンドルが解放された場合、再割り当てできます。問題は、空きハンドルを追跡することです。

ツリーは、空きハンドルを保存するための良い方法です。各ノードには最低と最高のハンドルがあり、左側のサブツリーには最低よりも小さいハンドルが含まれ、右側のサブツリーには最高よりも大きなハンドルが含まれています。

例：

            6-9
            / \
           2   15
          / \
         0   4

ハンドルがリリースされると、ツリーに保存されます。たとえば、10がリリースされた場合、ツリーは次のようになります。

            6-10
            / \
           2   15
          / \
         0   4

ハンドル5がリリースされた場合、4を5-10ノードにwelとして追加できるため、ツリーを最適化することを選択できます。

            5-10
            / \
           2   15
          / \
         0   4

宛先：

            4-10
            / \
           2   15
          / 
         0  

ハンドルの割り当て。1つのハンドルを持つリーフノードを検索し、ツリーから削除します。 1つのハンドルを持つリーフがない場合は、リーフを使用して、親に接続されていない側をデクリメントします。

         4-10
        /
      1-2

上記の例では、2を割り当てずに1を割り当てます。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;

Answer 2

メモリに問題がない場合は、空きハンドルのリストを維持できます。リリースされたら、それをフリーリストの最後に追加します。

最初は、すべてのIDをフリーリストに追加できますが、効率が悪くなります。

実行できる最適化は、利用可能な最小IDである値とフリーリストを維持することです。そのため、リストが空の場合、（維持している最小ID値から始まる）多数のIDをフリーリストに追加し、最小ID値を更新します。

Answer 3

この質問が＆quot;どうすれば迅速かつ安全に、現在使用されていないユニークな数を計算できますか？＆quot;である場合、ビットテーブルがそれを提供します。

200Kの一意の番号の場合、200.000 / 8 =必要なバイト数=25000。これは、追跡するための25KBのメモリをわずかに消費します。

もちろん、メモリ内で使用中のハンドルに関連付けられたデータを追跡する必要がある場合は、別のものが必要です。

別の解決策は、おそらく新しいハンドルをより迅速に取得するために、未使用のハンドルのスタックを保持することです。ハンドルが必要になるたびに、スタックからハンドルを1つポップします。

セット番号でスタックにシードすることもできますが、アルゴリズムでは、空のスタックから値をポップしようとすると、増加する値をインクリメントすることで新しい値を生成するだけです。

いつでも約200Kのハンドルがライブになると言うので、このスタックはその数のハンドルを保持するよりも大きくなることはないので、これを配列で簡単に処理できます。 200Kの32ビットスタックは800.000バイト、約781KBのメモリを消費します。