Deterministic handle allocation algorithm

Question

I'm trying to find an efficient deterministic way of allocating a 32-bit handle in such a way that it will operate indefinitely. A simple incrementing counter will not work because it will eventually loop around. Extending to 64-bits isn't possible because the values will be used in a network protocol which is expecting a 32-bit value.

It's for a real-time system so it has to be deterministic and quick. Though it'll end up in an SQLite database I can't just brute force test each key after loop around for example...

I think what I need is some sort of range tree that knows about all previously allocated handles (populating this on start up is fine). This seems to be a common(ish) sort of problem but it's not one that's solved by boost or the STL.

Any pointers?

Edit: Some additional clarification. I'm looking to have something of the order of 200k active handles in the system at any one time. Handles are deleted on a random basis.

Answer 1

You can't allocate more than 2^32. But you can reallocate used handles if they are released and the problem is to keep track of the free handles.

A tree is a good way to store the free handles. Each node has a lowest and a highest handle, the left subtree contains the handles that are lesser than the lowest and the right subtree contains the handles that are greater than the highest.

An example is:

            6-9
            / \
           2   15
          / \
         0   4

If a handle is released, it is stored in the tree. For example, if 10 is released, the tree looks like:

            6-10
            / \
           2   15
          / \
         0   4

If handle 5 is released, you can chose to optimize the tree because 4 can be added to the 5-10 node as wel:

            5-10
            / \
           2   15
          / \
         0   4

To:

            4-10
            / \
           2   15
          / 
         0  

The allocation of a handle, searches for a leaf node with 1 handle and removes it from the tree. If there are no leaves with 1 handle, just use a leaf and decrement the side that is not connected to the parent:

         4-10
        /
      1-2

In the above example we allocate 1 and not 2 because if 3 is released, you can combine it with 4 and you want to keep the number of nodes as low as possible.

Below is a pseudocode algorithm. Some parts are left for the reader:

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

If memory is not an issue, then you could maintain a list of free handles. When one is released, you add it back to the end of the free list.

At the beginning, you could add all the id to the free list, but it will be inefficient.

The optimization you could do is that you maintain a value that is the minimum id available, as well as the free list. So when the list is empty, you add a number of ids (starting from the minimum id value you are maintaining) to the free list and update the minimum id value.

Answer 3

If this question is just "how can I quickly, and safely, calculate a unique, not-currently-used, number", then a bit-table would give you that.

For the order of 200K unique numbers, 200.000 / 8 = number of bytes needed = 25000, which is just shy of 25KB of memory to keep track of.

Of course, if you need to keep track of data associated with in-use handles, in memory, then you need something else.

Another solution, that would probably be quicker to get a new handle through, would be to keep a stack of unused handles. Each time you need a handle, pop one off the stack.

You could seed the stack with a set number, but the algorithm would also be so that if you try to pop a value off the empty stack, you simply generate a new one by incrementing an ever-increasing value.

Since you say you will have around 200K handles live at any given time, this stack should never grow larger than holding that many number of handles, so you could easily handle this with an array. A 200K 32-bit stack would consume 800.000 bytes, around 781KB of memory.