numalloc.py

#! /usr/bin/env python

"""
Integer number allocator.

Basically, these keep track of a set of allocatable values in
some range (you provide min and max) and let you allocate out of
the range and return values into the range.

You may pick a value using "next since last time", or "next
available after provided value".  Note that next-after will
wrap around as needed (modular arithmetic style).

The free lists are thread-locked so that this code can be used
with threads.

    >>> a = NumAlloc(5, 10) # note closed interval: 5..10 inclusive
    >>> a
    NumAlloc(5, 10)
    >>> a.avail
    [[5, 10]]
    >>> a.alloc()
    5
    >>> a.avail
    [[6, 10]]
    >>> a.alloc(8)
    8
    >>> a.avail
    [[6, 7], [9, 10]]
    >>> a.free(5)
    >>> a.avail
    [[5, 7], [9, 10]]
    >>> a.free(8)
    >>> a.avail
    [[5, 10]]

Attempting to free a value that is already free is an error:

    >>> a.free(5)
    Traceback (most recent call last):
       ...
    ValueError: free: 5 already available

You can, however, free a value that is outside the min/max
range.  You can also free multiple values at once:

    >>> a.free_multi([0, 1, 2, 4])
    >>> a.avail
    [[0, 2], [4, 10]]
    >>> a.free_multi([3, 12])
    >>> a.avail
    [[0, 10], [12, 12]]

Note that this changes the min/max values:

    >>> a
    NumAlloc(0, 12)

To prevent adding values outside the min/max range, create the
NumArray with autoextend=False, or set .autoextend=False at any
time:

    >>> a.autoextend = False
    >>> a
    NumAlloc(0, 12, autoextend=False)
    >>> a.free(13)
    Traceback (most recent call last):
       ...
    ValueError: free: 13 is outside range limit

You can create an empty range, which is really only useful once
you free values into it:

    >>> r = NumAlloc(0, -1)
    >>> r
    NumAlloc(0, -1)
    >>> r.alloc() is None
    True
    >>> r.free_multi(range(50))
    >>> r
    NumAlloc(0, 49)

Note that r.alloc() starts from where you last left off, even if
you've freed a value:

    >>> r.alloc()
    0
    >>> r.free(0)
    >>> r.alloc()
    1

Of course, in multithreaded code you can't really depend on this
since it will race other threads.  Still, it generally makes for
efficient allocation.  To force allocation to start from the
range's minimum, provide the minimum (e.g., r.min_val) as an
argument to r.alloc():

    >>> r.alloc()
    2
    >>> r.alloc(r.min_val)
    0

Providing a number to alloc() tries to allocate that number,
but wraps around to the next one if needed:

    >>> r.alloc(49)
    49
    >>> r.alloc(49)
    3
    >>> r.alloc(99999)
    4
    >>> r.avail
    [[5, 48]]

There is currently no way to find all allocated values, although
the obvious method (going through r.avail) will work.  Any iterator
would not be thread-safe.
"""

import threading

class NumAlloc(object):
    """
    Number allocator object.
    """
    def __init__(self, min_val, max_val, autoextend=True):
        self.min_val = min_val
        self.max_val = max_val
        if min_val <= max_val:
            self.avail = [[min_val, max_val]]
        else:
            self.avail = []
        self.autoextend = autoextend
        self.last = None
        self.lock = threading.Lock()

    def __repr__(self):
        myname = self.__class__.__name__
        if self.autoextend:
            ae = ''
        else:
            ae = ', autoextend=False'
        return '{0}({1}, {2}{3})'.format(myname, self.min_val, self.max_val, ae)

    def _find_block(self, val):
        """
        Find the block that contains val, or that should contain val.
        Remember that self.avail is a list of avaliable ranges of
        the form [[min1, max1], [min2, max2], ..., [minN, maxN]]
        where max1 < min2, max2 < min3, ..., < minN.

        The input value either falls into one of the available
        blocks, or falls into a gap between two available blocks.
        We want to know which block it goes in, or if it goes
        between two, which block it comes before.

        We can do a binary search to find this block.  When we
        find it, return its index and its values.

        If we find that val is not in a block, return the position
        where the value should go, were it to be put into a new
        block by itself.  E.g., suppose val is 17, and there is a
        block [14,16] and a block [18,20]. We would make this
        [14,16],[17,17],[18,20] by inserting [17,17] between them.
        (Afterward, we will want to fuse all three blocks to make
        [14,18].  However, if we insert as block 0, e.g., if the
        list starts with [18,20] and we insert to get
        [17,17][18,20], we really end up just modifying block 0 to
        [17,20].  Or, if we insert as the new final block, we
        might end up modifying the last block.)
        """
        low = 0
        high = len(self.avail) - 1
        while low <= high:
            mid = low + ((high - low) // 2)
            pair = self.avail[mid]
            if val < pair[0]:
                # must go before block mid
                high = mid - 1
            elif val > pair[1]:
                # must go after block mid
                low = mid + 1
            else:
                # val >= first and val <= last, so we found it
                return mid, pair
        # Low > high: no block actually contains val, or
        # there are no blocks at all.  If there are no blocks,
        # return block #0 and None.  Otherwise return the
        return low, None

    def alloc(self, val=None):
        """
        Get new available value.

        If val is None, we start from the most recently
        allocated value, plus 1.

        If val is a numeric value, we start from that value.
        Hence, since the range is min_val..max_val, you can
        provide min_val to take the first available value.

        This may return None, if no values are still available.
        """
        with self.lock:
            if val is None:
                val = self.last + 1 if self.last is not None else self.min_val
            if val is None or val > self.max_val or val < self.min_val:
                val = self.min_val
            i, pair = self._find_block(val)
            if pair is None:
                # Value is is not available.  The next
                # available value that is greater than val
                # is in the block right after block i.
                # If there is no block after i, the next
                # available value is in block 0.  If there
                # is no block 0, there are no available
                # values.
                nblocks = len(self.avail)
                i += 1
                if i >= nblocks:
                    if nblocks == 0:
                        return None
                    i = 0
                pair = self.avail[i]
                val = pair[0]
            # Value val is available - take it.
            #
            # There are four special cases to handle.
            #
            # 1. pair[0] < val < pair[1]: split the pair.
            # 2. pair[0] == val < pair[1]: increase pair[0].
            # 3. pair[0] == val == pair[1]: delete the pair
            # 4. pair[0] < val == pair[1]: decrease pair[1].
            assert pair[0] <= val <= pair[1]
            if pair[0] == val:
                # case 2 or 3: Take the left edge or delete the pair.
                if val == pair[1]:
                    del self.avail[i]
                else:
                    pair[0] = val + 1
            else:
                # case 1 or 4: split the pair or take the right edge.
                if val == pair[1]:
                    pair[1] = val - 1
                else:
                    newpair = [val + 1, pair[1]]
                    pair[1] = val - 1
                    self.avail.insert(i + 1, newpair)
            self.last = val
            return val

    def free(self, val):
        "Free one value"
        self._free_multi('free', [val])

    def free_multi(self, values):
        "Free many values (provide any iterable)"
        values = list(values)
        values.sort()
        self._free_multi('free_multi', values)

    def _free_multi(self, how, values):
        """
        Free a (sorted) list of values.
        """
        if len(values) == 0:
            return
        with self.lock:
            while values:
                # Take highest value, and any contiguous lower values.
                # Note that it can be significantly faster this way
                # since coalesced ranges make for shorter copies.
                highval = values.pop()
                val = highval
                while len(values) and values[-1] == val - 1:
                    val = values.pop()
                self._free_range(how, val, highval)

    def _maybe_increase_max(self, how, val):
        """
        If needed, widen our range to include new high val -- i.e.,
        possibly increase self.max_val.  Do nothing if this is not a
        new all time high; fail if we have autoextend disabled.
        """
        if val <= self.max_val:
            return
        if self.autoextend:
            self.max_val = val
            return
        raise ValueError('{0}: {1} is outside range limit'.format(how, val))

    def _maybe_decrease_min(self, how, val):
        """
        If needed, widen our range to include new low val -- i.e.,
        possibly decrease self.min_val.  Do nothing if this is not a
        new all time low; fail if we have autoextend disabled.
        """
        if val >= self.min_val:
            return
        if self.autoextend:
            self.min_val = val
            return
        raise ValueError('{0}: {1} is outside range limit'.format(how, val))

    def _free_range(self, how, val, highval):
        """
        Free the range [val..highval].  Note, val==highval it's just
        a one-element range.

        The lock is already held.
        """
        # Find the place to store the lower value.
        # We should never find an actual pair here.
        i, pair = self._find_block(val)
        if pair:
            raise ValueError('{0}: {1} already available'.format(how, val))
        # If we're freeing a range, check that the high val
        # does not span into the *next* range, either.
        if highval > val and i < len(self.avail):
            if self.avail[i][0] <= highval:
                raise ValueError('{0}: {2} (from {{1}..{2}) already '
                                 'available'.format(how, val, highval))

        # We'll need to insert a block and perhaps fuse it
        # with blocks before and/or after.  First, check
        # whether there *is* a before and/or after, and find
        # their corresponding edges and whether we abut them.
        if i > 0:
            abuts_below = self.avail[i - 1][1] + 1 == val
        else:
            abuts_below = False
        if i < len(self.avail):
            abuts_above = self.avail[i][0] - 1 == highval
        else:
            abuts_above = False
        # Now there are these four cases:
        # 1. abuts below and above: fuse the two blocks.
        # 2. abuts below only: adjust previous (i-1'th) block
        # 3. abuts above only: adjust next (i'th) block
        # 4. doesn't abut: insert new block
        if abuts_below:
            if abuts_above:
                # case 1
                self.avail[i - 1][1] = self.avail[i][1]
                del self.avail[i]
            else:
                # case 2
                self._maybe_increase_max(how, highval)
                self.avail[i - 1][1] = highval
        else:
            if abuts_above:
                # case 3
                self._maybe_decrease_min(how, val)
                self.avail[i][0] = val
            else:
                # case 4
                self._maybe_decrease_min(how, val)
                self._maybe_increase_max(how, highval)
                newblock = [val, highval]
                self.avail.insert(i, newblock)

if __name__ == '__main__':
    import doctest
    import sys

    doctest.testmod()
    if sys.version_info[0] >= 3:
        xrange = range
    # run some worst case tests
    # NB: coalesce is terribly slow when done bottom up
    r = NumAlloc(0, 2**16 - 1)
    for i in xrange(r.min_val, r.max_val, 2):
        r.alloc(i)
    print('worst case alloc: len(r.avail) = {0}'.format(len(r.avail)))
    for i in xrange(r.max_val - 1, r.min_val, -2):
        r.free(i)
    print('free again; len(r.avail) should be 1; is {0}'.format(len(r.avail)))
    if len(r.avail) != 1:
        sys.exit('failure')