[403a5ba] | 1 | #!/usr/local/bin/python |
---|
[1fda364] | 2 | |
---|
| 3 | class ip_allocator: |
---|
| 4 | def __init__(self, base=0, size=4294967296, min_alloc=256): |
---|
| 5 | |
---|
[c410e3a4] | 6 | self.base = base |
---|
| 7 | self.size = size |
---|
| 8 | self.min_alloc = min_alloc |
---|
[1fda364] | 9 | |
---|
[c410e3a4] | 10 | i = self.min_alloc |
---|
| 11 | self.free = { } |
---|
| 12 | self.allocated = { } |
---|
| 13 | while i < self.size: |
---|
| 14 | self.free[i] = set() |
---|
| 15 | self.allocated[i] = set() |
---|
| 16 | i *= 2 |
---|
| 17 | self.free[self.size] = set([self.base]) |
---|
| 18 | self.allocated[self.size] = set() |
---|
[1fda364] | 19 | |
---|
| 20 | def split(self, base, size): |
---|
[c410e3a4] | 21 | return ( base, base + size) |
---|
[1fda364] | 22 | |
---|
| 23 | def make_chunk(self, size): |
---|
[c410e3a4] | 24 | if not self.free[size * 2]: |
---|
| 25 | if size < self.size: |
---|
| 26 | if not self.make_chunk(size * 2): |
---|
| 27 | return False |
---|
| 28 | else: |
---|
| 29 | return False |
---|
| 30 | base = min(self.free[size*2]) |
---|
| 31 | self.free[size*2].discard(base) |
---|
[1fda364] | 32 | |
---|
[c410e3a4] | 33 | for b in self.split(base, size): |
---|
| 34 | self.free[size].add(b) |
---|
| 35 | return True |
---|
[1fda364] | 36 | |
---|
| 37 | def allocate(self, size): |
---|
[c410e3a4] | 38 | # Make sure size is a power of 2 at least as big as minalloc |
---|
| 39 | ns = self.min_alloc |
---|
| 40 | while ns < self.size: |
---|
| 41 | if ns == size: |
---|
| 42 | break |
---|
| 43 | if ns > size: |
---|
| 44 | size = ns |
---|
| 45 | break |
---|
| 46 | ns *= 2 |
---|
| 47 | else: |
---|
| 48 | size = self.size |
---|
[1fda364] | 49 | |
---|
[c410e3a4] | 50 | if self.free[size] or self.make_chunk(size): |
---|
| 51 | rv = min(self.free[size]) |
---|
| 52 | self.free[size].discard(rv) |
---|
| 53 | self.allocated[size].add(rv) |
---|
| 54 | return (rv, size) |
---|
| 55 | else: |
---|
| 56 | return None |
---|
[1fda364] | 57 | |
---|
| 58 | def deallocate(self, base, size): |
---|
[c410e3a4] | 59 | if base not in self.allocated[size]: |
---|
| 60 | raise KeyError("Not allocated") |
---|
| 61 | if base % (size * 2) == 0: |
---|
| 62 | if base + size in self.free[size]: |
---|
| 63 | self.allocated[size].discard(base) |
---|
| 64 | self.allocated[size * 2].add(base) |
---|
| 65 | self.free[size].discard(base+size) |
---|
| 66 | self.deallocate(base, size *2) |
---|
| 67 | else: |
---|
| 68 | self.allocated[size].discard(base) |
---|
| 69 | self.free[size].add(base) |
---|
| 70 | else: |
---|
| 71 | if base - size in self.free[size]: |
---|
| 72 | self.allocated[size].discard(base) |
---|
| 73 | self.allocated[size * 2].add(base - size) |
---|
| 74 | self.free[size].discard(base - size) |
---|
| 75 | self.deallocate(base-size, size * 2) |
---|
| 76 | else: |
---|
| 77 | self.allocated[size].discard(base) |
---|
| 78 | self.free[size].add(base) |
---|
| 79 | return True |
---|
[1fda364] | 80 | |
---|
| 81 | def __str__(self): |
---|
[c410e3a4] | 82 | rv = "" |
---|
| 83 | i=self.size |
---|
| 84 | while i >= self.min_alloc: |
---|
| 85 | rv += "%d: %s\n" % (i, self.free[i]) |
---|
| 86 | i /= 2 |
---|
| 87 | return rv |
---|