#! /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')