Changeset View
Changeset View
Standalone View
Standalone View
contrib/lib9p/pytest/numalloc.py
- This file was added.
#! /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') |