source: fedd/deter/ip_allocator.py @ 044dd20

compt_changesinfo-ops
Last change on this file since 044dd20 was 044dd20, checked in by Ted Faber <faber@…>, 12 years ago

Move ip_addr and ip_allocator out

  • Property mode set to 100644
File size: 2.6 KB
Line 
1#!/usr/local/bin/python
2
3class 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
Note: See TracBrowser for help on using the repository browser.