1 # This file is part of python-rwhoisd
3 # Copyright (C) 2003, David E. Blacka
5 # $Id: MemIndex.py,v 1.2 2003/04/28 16:43:19 davidb Exp $
7 # This program is free software; you can redistribute it and/or modify
8 # it under the terms of the GNU General Public License as published by
9 # the Free Software Foundation; either version 2 of the License, or
10 # (at your option) any later version.
12 # This program is distributed in the hope that it will be useful, but
13 # WITHOUT ANY WARRANTY; without even the implied warranty of
14 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 # General Public License for more details.
17 # You should have received a copy of the GNU General Public License
18 # along with this program; if not, write to the Free Software
19 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
26 """This class implements a simple in-memory key-value map. This
27 index supports efficient prefix matching (as well as pretty
28 efficient exact matching). Internally, it is implemented as a
29 sorted list supporting binary searches."""
31 # NOTE: This implementation is probably far from as efficient as
32 # it could be. Ideally, we should avoid the use of custom
33 # comparison functions, so that list.sort() will use built-in
34 # comparitors. This would mean storing raw key tuples in index as
35 # opposed to element objects. Also, it would mean avoiding the
36 # use of objects (like Cidr) as keys in favor of a primitive type.
37 # In the Cidr case, we would either have to use longs or strings,
38 # as Python doesn't seem to have an unsigned 32-bit integer type.
44 def add(self, key, value=None):
45 """Add a key-value pair to the map. If the map is already in
46 the prepared state, this operation will preserve it, so don't
47 use this if many elements are to be added at once. The 'key'
48 argument may be a 2 element tuple, in which case 'value' is
51 if isinstance(key, types.TupleType):
52 el = element(key[0], key[1])
54 el = element(key, value)
57 i = bisect.bisect_left(self.index, el)
58 while i < len(self.index):
59 if self.index[i].total_equals(el):
61 if self.index[i] != el:
62 self.index.insert(i, el)
70 def addlist(self, list):
71 """Add the entire list of elements to the map. The elements
72 of 'list' may be 2 element tuples or actual 'element' objects.
73 Use this method to add many elements at once."""
77 if isinstance(i, types.TupleType):
78 self.index.append(element(i[0], i[1]))
79 elif isinstance(i, element):
83 """Put the map in a prepared state, if necessary."""
93 if not self.index[i].total_equals(last):
94 self.index[lasti] = last = self.index[i]
100 def _find(self, key):
101 """Return the (search_element, index) tuple. Used internally
105 search_el = element(key, None)
106 i = bisect.bisect_left(self.index, search_el)
107 if i > len(self.index) or i < 0:
108 print "warning: bisect.bisect_left returned something " + \
109 "unexpected:", i, len(self.index)
110 return (search_el, i)
112 def find(self, key, prefix_match=False, max=0):
113 """Return a list of values whose keys string match 'key'. If
114 prefix_match is True, then keys will match if 'key' is a
115 prefix of the element key."""
117 search_el, i = self._find(key)
119 while i < len(self.index):
120 if max and len(res) == max: break
121 if search_el.equals(self.index[i], prefix_match):
122 res.append(self.index[i].value)
128 class CidrMemIndex(MemIndex):
129 """This is an in-memory map that has been extended to support CIDR
130 searching semantics."""
132 # NOTE: this structure lends to fairly efficient exact searches
133 # (O[log2N]), efficient subnet searches (also O[log2N]), but not
134 # terribly efficient supernet searches (O[32 * log2N]), because we
135 # have to potentially do 32 exact matches. If we want efficient
136 # supernet searches, we will probably have to use some sort of
137 # general (i.e., not binary) search tree datastructure, as there
138 # is no sorted ordering that will efficiently give supernets that
141 def add(self, key, value=None):
142 if isinstance(key, types.TupleType):
143 MemIndex.add(self, (Cidr.valid_cidr(key[0]), key[1]), value)
145 MemIndex.add(self, Cidr.valid_cidr(key), value)
148 def addlist(self, list):
150 # make sure the keys are Cidr objects
152 if isinstance(i, types.TupleType):
153 i = (Cidr.valid_cidr(el[0]), el[1])
154 elif isinstance(el, element):
155 i.key = Cidr.valid_cidr(i.key)
157 MemIndex.addlist(self, list)
160 def find_exact(self, key, max = 0):
162 key = Cidr.valid_cidr(key)
163 search_el, i = self._find(key)
165 while i < len(self.index) and self.index[i].key == key:
166 res.append(self.index[i].value)
167 if max and len(res) == max: break
171 def find_subnets(self, key, max = 0):
172 """Return all values that are subnets of 'key', including any
173 that match 'key' itself."""
175 key = Cidr.valid_cidr(key)
176 search_el, i = self._find(key)
179 while i < len(self.index) and self.index[i].key.is_subnet(key):
180 if max and len(res) == max: break
181 res.append(self.index[i].value)
185 def find_supernets(self, key, max = 0):
186 """Return all values that are supernets of 'key', including
187 any that match 'key' itself."""
189 key = Cidr.valid_cidr(key)
194 res += self.find_exact(k, max)
195 if max and len(res) >= max:
202 def find(self, key, prefix_match=0, max=0):
203 """Return either the exact match of 'key', or the closest
204 supernet of 'key'. If prefix_match is True, then find all
205 supernets of 'key'"""
207 key = Cidr.valid_cidr(key)
208 if prefix_match == 0:
209 res = self.find_exact(key, max)
212 # now do a modified supernet search that stops after
213 # the first proper supernet, but gets all values
214 # matching that supernet key
217 while not res and k.netlen >= 0:
219 res = self.find_exact(k, max)
223 # for now, a prefix match means all supernets
224 return self.find_supernets(key, max)
227 """This is an in-memory map that contains both a normal string
228 index and a CIDR index. Valid CIDR values we be applied against
229 the CIDR index. Other values will be applied against the normal
233 self.normal_index = MemIndex()
234 self.cidr_index = CidrMemIndex()
236 def add(self, key, value = None):
237 """Add a key,value pair to the correct map. See MemIndex for
238 the behavior of this method"""
240 if isinstance(key, types.TupleType):
244 c = Cidr.valid_cidr(key)
246 self.cidr_index.add(key, value)
248 self.normal_index.add(key, value)
251 def addlist(self, list):
252 """Add a list of elements or key, value tuples to the
259 if isinstance(i, element):
260 k, v = i.key, i.value
261 elif isinstance(i, types.TupleType):
264 c = Cidr.valid_cidr(k)
266 cidr_list.append((c, v))
268 normal_list.append((k, v))
271 self.cidr_index.addlist(cidr_list)
273 self.normal_index.addlist(normal_list)
277 """Prepare the internally held maps for searching."""
279 self.cidr_index.prepare()
280 self.normal_index.prepare()
282 def find(self, key, prefix_match=False, max=0):
283 """Return a list of values whose keys match 'key'."""
285 c = Cidr.valid_cidr(key)
287 return self.cidr_index.find(c, prefix_match, max)
288 return self.normal_index.find(key, prefix_match, max)
290 def find_exact(self, key, max = 0):
291 """Return a list of values whose keys match 'key'. if 'key'
292 is not a CIDR value, then this is the same as find()."""
294 c = Cidr.valid_cidr(key)
296 return self.cidr_index.find_exact(c, max)
297 return self.normal_index.find(key, False, max)
299 def find_subnets(self, key, max = 0):
300 """If 'key' is a CIDR value (either a Cidr object or a valid
301 CIDR string representation, do a find_subnets on the internal
302 CidrMemIndex, otherwise return None."""
304 c = Cidr.valid_cidr(key)
305 if c: return self.cidr_index.find_subnets(key, max)
308 def find_supernets(self, key, max = 0):
309 """If 'key' is a CIDR value (either a Cidr object or a valid
310 CIDR string representation, do a find_supernets on the internal
311 CidrMemIndex, otherwise return None."""
313 c = Cidr.valid_cidr(key)
314 if c: return self.cidr_index.find_supernets(key, max)
318 """This is the base element class. It basically exists to
321 def __init__(self, key, value):
325 def __cmp__(self, other):
326 """Compare only on the key."""
328 if not type(self.key) == type(other.key):
329 print "other is incompatible type?", repr(other.key), other.key
330 if self.key < other.key:
332 if self.key == other.key:
337 return "<" + str(self.key) + ", " + str(self.value) + ">"
340 return "element" + str(self)
343 return self.key.__hash__()
345 def equals(self, other, prefix_match=0):
347 return self.key == other.key[:len(self.key)]
348 return self.key == other.key
350 def total_equals(self, other):
351 if not isinstance(other, type(self)): return False
352 return self.key == other.key and self.value == other.value
354 if __name__ == "__main__":
356 source = [ ("foo", "foo-id"), ("bar", "bar-id"), ("baz", "baz-id"),
357 ("foobar", "foo-id-2"), ("barnone", "bar-id-2"),
363 print "finding foobar:"
364 res = mi.find("foobar")
367 print "finding foo*:"
368 res = mi.find("foo", 1)
376 mi.add("bork", "bork-id")
379 res = mi.find("b", 1)
384 ci.add(Cidr.Cidr("127.0.0.1/24"), "net-local-1");
385 ci.add(Cidr.Cidr("127.0.0.1/32"), "net-local-2");
386 ci.add(Cidr.Cidr("216.168.224.0", 22), "net-vrsn-1")
387 ci.add(Cidr.Cidr("216.168.252.1", 32), "net-vrsn-2")
388 ci.add(Cidr.Cidr("24.36.191.0/24"), "net-foo-c")
389 ci.add(Cidr.Cidr("24.36.191.32/27"), "net-foo-sub-c")
390 ci.add(Cidr.Cidr("24.36/16"), "net-foo-b")
392 print "finding exactly 127.0.0.0/24"
393 res = ci.find(Cidr.Cidr("127.0.0.0/24"))
396 print "finding exactly 127.0.0.16/32"
397 res = ci.find(Cidr.Cidr("127.0.0.16/32"))
400 print "finding supernets of 127.0.0.16/32"
401 res = ci.find_supernets(Cidr.Cidr("127.0.0.16/32"))
404 print "finding supernets of 24.36.191.32/27"
405 res = ci.find(Cidr.Cidr("24.36.191.32/27"), 1)
408 print "finding supernets of 24.36.191.33/27"
409 res = ci.find_supernets(Cidr.Cidr("24.36.191.33/27"))
412 print "finding supernets of 24.36.191.64/27"
413 res = ci.find_supernets(Cidr.Cidr("24.36.191.64/27"))
416 print "finding subnets of 127.0/16"
417 res = ci.find_subnets(Cidr.Cidr("127.0/16"))