find_unused.py

diff --git a/find_unused.py b/find_unused.py
new file mode 100755 (executable)
index 0000000..3546498
--- /dev/null
+++ b/find_unused.py
@@ -0,0 +1,118 @@
+#!/usr/bin/python
+#
+
+import random
+
+class table:
+       
+       def __init__(self, lowest_id, max_count, max_random):
+               self.lowest_id = lowest_id
+               self.max_count = max_count
+               if max_random is None:
+                       max_random = (max_count / 1000) + 1
+               self.max_random = max_random
+               self.db = {}
+
+       def range_idx(self, id, max_count, ranges=10):
+               range_size = max_count / (ranges - 1)
+               idx = id / range_size
+
+               return idx
+
+       def range_size(self, idx, max_count, ranges=10):
+               if idx == ranges - 1:
+                       range_size = max_count % (ranges - 1)
+               else:
+                       range_size = max_count / (ranges - 1)
+               return range_size
+
+       def range_ofs(self, idx, max_count, ranges=10):
+               range_ofs = 0
+               for i in range(1, idx):
+                       range_ofs += self.range_size(i, max_count,
+                                       ranges=ranges)
+               return range_ofs
+
+       def find_free(self, lowest_id=None, max_count=None):
+               if lowest_id is None:
+                       lowest_id = self.lowest_id
+               if max_count is None:
+                       max_count = self.max_count
+
+               if len(self.db) >= self.max_count:
+                       return None
+
+               max_random = min(self.max_random, max_count)
+
+               for i in range(0, max_random):
+                       ran_id = random.randint(0, max_count)
+
+                       id = lowest_id + ran_id
+
+                       if id in self.db:
+                               continue
+
+                       self.db[id] = id
+                       return id
+
+               #return None
+               #raise
+
+#              for i in range(0, max_count):
+#                      fix_id = i
+#
+#                      id = lowest_id + fix_id
+#
+#                      if id in self.db:
+#                              continue
+#
+#                      self.db[id] = id
+#                      return id
+#
+#              raise
+
+               ranges = {}
+               for i in range(0, 10):
+                       ranges[i] = 0
+
+               for id, idv in self.db.items():
+                       range_idx = self.range_idx(id-self.lowest_id, self.max_count)
+                       #print "%08X: %08X range[%d]" % (i, id, range_idx)
+                       ranges[range_idx] += 1
+
+               for i in range(0, 10):
+                       range_size = self.range_size(i, self.max_count)
+                       if (ranges[i] < range_size):
+                               range_ofs = self.range_ofs(i, self.max_count)
+                               return self.find_free(lowest_id=lowest_id+range_ofs,
+                                                     max_count=range_size)
+                       #print "range[%d] = 0x%04X exp[0x%04X]" % (i, ranges[i], range_size)
+
+               #print "count[0x%04X] max_count[0x%04X]" % (len(self.db), self.max_count)
+               #raise
+               return None
+
+       def run(self):
+               ranges = {}
+               for i in range(0, 10):
+                       ranges[i] = 0
+
+               for i in range(0, self.max_count*2):
+                       id = self.find_free()
+                       if id is None:
+                               print "%08X: None" % (i)
+                               break
+                       range_idx = self.range_idx(id-self.lowest_id, self.max_count)
+                       print "%08X: %08X range[%d]" % (i, id, range_idx)
+                       ranges[range_idx] += 1
+
+               for i in range(0, 10):
+                       range_size = self.range_size(i, self.max_count)
+                       print "range[%d] = 0x%04X exp[0x%04X]" % (i, ranges[i], range_size)
+
+               print "count[0x%04X] max_count[0x%04X]" % (len(self.db), self.max_count)
+
+t = table(1, 0xfff-1, None)
+print "%s" % (t)
+t.run()
+