5 """This class implements a simple in-memory key-value map. This
6 index supports efficient prefix matching (as well as pretty
7 efficient exact matching). Internally, it is implemented as a
8 sorted list supporting binary searches."""
10 # NOTE: This implementation is probably far from as efficient as
11 # it could be. Ideally, we should avoid the use of custom
12 # comparison functions, so that list.sort() will use built-in
13 # comparitors. This would mean storing raw key tuples in index as
14 # opposed to element objects. Also, it would mean avoiding the
15 # use of objects (like Cidr) as keys in favor of a primitive type.
16 # In the Cidr case, we would either have to use longs or strings,
17 # as Python doesn't seem to have an unsigned 32-bit integer type.
23 def add(self, key, value=None):
24 """Add a key-value pair to the map. If the map is already in
25 the prepared state, this operation will preserve it, so don't
26 use this if many elements are to be added at once. The 'key'
27 argument may be a 2 element tuple, in which case 'value' is
30 if isinstance(key, types.TupleType):
31 el = element(key[0], key[1])
33 el = element(key, value)
36 i = bisect.bisect_left(self.index, el)
37 while i < len(self.index):
38 if self.index[i].total_equals(el):
40 if self.index[i] != el:
41 self.index.insert(i, el)
49 def addlist(self, list):
50 """Add the entire list of elements to the map. The elements
51 of 'list' may be 2 element tuples or actual 'element' objects.
52 Use this method to add many elements at once."""
56 if isinstance(i, types.TupleType):
57 self.index.append(element(i[0], i[1]))
58 elif isinstance(i, element):
62 """Put the map in a prepared state, if necessary."""
72 if not self.index[i].total_equals(last):
73 self.index[lasti] = last = self.index[i]
80 """Return the (search_element, index) tuple. Used internally
84 search_el = element(key, None)
85 i = bisect.bisect_left(self.index, search_el)
86 if i > len(self.index) or i < 0:
87 print "warning: bisect.bisect_left returned something " + \
88 "unexpected:", i, len(self.index)
91 def find(self, key, prefix_match=False, max=0):
92 """Return a list of values whose keys string match 'key'. If
93 prefix_match is True, then keys will match if 'key' is a
94 prefix of the element key."""
96 search_el, i = self._find(key)
98 while i < len(self.index):
99 if max and len(res) == max: break
100 if search_el.equals(self.index[i], prefix_match):
101 res.append(self.index[i].value)
107 class CidrMemIndex(MemIndex):
108 """This is an in-memory map that has been extended to support CIDR
109 searching semantics."""
111 # NOTE: this structure lends to fairly efficient exact searches
112 # (O[log2N]), effience subnet searches (also O[log2N]), but not
113 # terribly efficient supernet searches (O[32log2N]), because we
114 # have to potentially do 32 exact matches. If we want efficient
115 # supernet searches, we will probably have to use some sort of
116 # general (i.e., not binary) search tree datastructure, as there
117 # is no sorted ordering that will efficiently give supernets that
120 def add(self, key, value=None):
121 if isinstance(key, types.TupleType):
122 MemIndex.add(self, (Cidr.valid_cidr(key[0]), key[1]), value)
124 MemIndex.add(self, Cidr.valid_cidr(key), value)
127 def addlist(self, list):
129 # make sure the keys are Cidr objects
131 if isinstance(i, types.TupleType):
132 i = (Cidr.valid_cidr(el[0]), el[1])
133 elif isinstance(el, element):
134 i.key = Cidr.valid_cidr(i.key)
136 MemIndex.addlist(self, list)
139 def find_exact(self, key, max = 0):
141 key = Cidr.valid_cidr(key)
142 search_el, i = self._find(key)
144 while i < len(self.index) and self.index[i].key == key:
145 res.append(self.index[i].value)
146 if max and len(res) == max: break
150 def find_subnets(self, key, max = 0):
151 """Return all values that are subnets of 'key', including any
152 that match 'key' itself."""
154 key = Cidr.valid_cidr(key)
155 search_el, i = self._find(key)
158 while i < len(self.index) and self.index[i].key.is_subnet(key):
159 if max and len(res) == max: break
160 res.append(self.index[i].value)
164 def find_supernets(self, key, max = 0):
165 """Return all values that are supernets of 'key', including
166 any that match 'key' itself."""
168 key = Cidr.valid_cidr(key)
173 res += self.find_exact(k, max)
174 if max and len(res) >= max:
181 def find(self, key, prefix_match=0, max=0):
182 """Return either the exact match of 'key', or the closest
183 supernet of 'key'. If prefix_match is True, then find all
184 supernets of 'key'"""
186 key = Cidr.valid_cidr(key)
187 if prefix_match == 0:
188 res = self.find_exact(key, max)
191 # now do a modified supernet search that stops after
192 # the first proper supernet, but gets all values
193 # matching that supernet key
196 while not res and k.netlen >= 0:
198 res = self.find_exact(k, max)
202 # for now, a prefix match means all supernets
203 return self.find_supernets(key, max)
206 """This is an in-memory map that contains both a normal string
207 index and a CIDR index. Valid CIDR values we be applied against
208 the CIDR index. Other values will be applied against the normal
212 self.normal_index = MemIndex()
213 self.cidr_index = CidrMemIndex()
215 def add(self, key, value = None):
216 """Add a key,value pair to the correct map. See MemIndex for
217 the behavior of this method"""
219 if isinstance(key, types.TupleType):
223 c = Cidr.valid_cidr(key)
225 self.cidr_index.add(key, value)
227 self.normal_index.add(key, value)
230 def addlist(self, list):
231 """Add a list of elements or key, value tuples to the
238 if isinstance(i, element):
239 k, v = i.key, i.value
240 elif isinstance(i, types.TupleType):
243 c = Cidr.valid_cidr(k)
245 cidr_list.append((c, v))
247 normal_list.append((k, v))
250 self.cidr_index.addlist(cidr_list)
252 self.normal_index.addlist(normal_list)
256 """Prepare the internally held maps for searching."""
258 self.cidr_index.prepare()
259 self.normal_index.prepare()
261 def find(self, key, prefix_match=False, max=0):
262 """Return a list of values whose keys match 'key'."""
264 c = Cidr.valid_cidr(key)
266 return self.cidr_index.find(c, prefix_match, max)
267 return self.normal_index.find(key, prefix_match, max)
269 def find_exact(self, key, max = 0):
270 """Return a list of values whose keys match 'key'. if 'key'
271 is not a CIDR value, then this is the same as find()."""
273 c = Cidr.valid_cidr(key)
275 return self.cidr_index.find_exact(c, max)
276 return self.normal_index.find(key, False, max)
278 def find_subnets(self, key, max = 0):
279 """If 'key' is a CIDR value (either a Cidr object or a valid
280 CIDR string representation, do a find_subnets on the internal
281 CidrMemIndex, otherwise return None."""
283 c = Cidr.valid_cidr(key)
284 if c: return self.cidr_index.find_subnets(key, max)
287 def find_supernets(self, key, max = 0):
288 """If 'key' is a CIDR value (either a Cidr object or a valid
289 CIDR string representation, do a find_supernets on the internal
290 CidrMemIndex, otherwise return None."""
292 c = Cidr.valid_cidr(key)
293 if c: return self.cidr_index.find_supernets(key, max)
297 """This is the base element class. It basically exists to
300 def __init__(self, key, value):
304 def __cmp__(self, other):
305 """Compare only on the key."""
307 if not type(self.key) == type(other.key):
308 print "other is incompatible type?", repr(other.key), other.key
309 if self.key < other.key:
311 if self.key == other.key:
316 return "<" + str(self.key) + ", " + str(self.value) + ">"
319 return "element" + str(self)
322 return self.key.__hash__()
324 def equals(self, other, prefix_match=0):
326 return self.key == other.key[:len(self.key)]
327 return self.key == other.key
329 def total_equals(self, other):
330 if not isinstance(other, type(self)): return False
331 return self.key == other.key and self.value == other.value
333 if __name__ == "__main__":
335 source = [ ("foo", "foo-id"), ("bar", "bar-id"), ("baz", "baz-id"),
336 ("foobar", "foo-id-2"), ("barnone", "bar-id-2"),
342 print "finding foobar:"
343 res = mi.find("foobar")
346 print "finding foo*:"
347 res = mi.find("foo", 1)
355 mi.add("bork", "bork-id")
358 res = mi.find("b", 1)
363 ci.add(Cidr.Cidr("127.0.0.1/24"), "net-local-1");
364 ci.add(Cidr.Cidr("127.0.0.1/32"), "net-local-2");
365 ci.add(Cidr.Cidr("216.168.224.0", 22), "net-vrsn-1")
366 ci.add(Cidr.Cidr("216.168.252.1", 32), "net-vrsn-2")
367 ci.add(Cidr.Cidr("24.36.191.0/24"), "net-foo-c")
368 ci.add(Cidr.Cidr("24.36.191.32/27"), "net-foo-sub-c")
369 ci.add(Cidr.Cidr("24.36/16"), "net-foo-b")
371 print "finding exactly 127.0.0.0/24"
372 res = ci.find(Cidr.Cidr("127.0.0.0/24"))
375 print "finding exactly 127.0.0.16/32"
376 res = ci.find(Cidr.Cidr("127.0.0.16/32"))
379 print "finding supernets of 127.0.0.16/32"
380 res = ci.find_supernets(Cidr.Cidr("127.0.0.16/32"))
383 print "finding supernets of 24.36.191.32/27"
384 res = ci.find(Cidr.Cidr("24.36.191.32/27"), 1)
387 print "finding supernets of 24.36.191.33/27"
388 res = ci.find_supernets(Cidr.Cidr("24.36.191.33/27"))
391 print "finding supernets of 24.36.191.64/27"
392 res = ci.find_supernets(Cidr.Cidr("24.36.191.64/27"))
395 print "finding subnets of 127.0/16"
396 res = ci.find_subnets(Cidr.Cidr("127.0/16"))