| 1 | #!/usr/local/bin/python |
|---|
| 2 | |
|---|
| 3 | class ip_allocator: |
|---|
| 4 | def __init__(self, base=0, size=4294967296, min_alloc=256): |
|---|
| 5 | |
|---|
| 6 | self.base = base |
|---|
| 7 | self.size = size |
|---|
| 8 | self.min_alloc = min_alloc |
|---|
| 9 | |
|---|
| 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() |
|---|
| 19 | |
|---|
| 20 | def split(self, base, size): |
|---|
| 21 | return ( base, base + size) |
|---|
| 22 | |
|---|
| 23 | def make_chunk(self, size): |
|---|
| 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) |
|---|
| 32 | |
|---|
| 33 | for b in self.split(base, size): |
|---|
| 34 | self.free[size].add(b) |
|---|
| 35 | return True |
|---|
| 36 | |
|---|
| 37 | def allocate(self, size): |
|---|
| 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 |
|---|
| 49 | |
|---|
| 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 |
|---|
| 57 | |
|---|
| 58 | def deallocate(self, base, size): |
|---|
| 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 |
|---|
| 80 | |
|---|
| 81 | def __str__(self): |
|---|
| 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 |
|---|
