find_unused

diff --git a/find_unused.py b/find_unused.py
index 3546498e23ec70d0644b94ead2d1af9906e49ff7..610aac19c87a68207790fad3b4950939f778237d 100755 (executable)
--- a/find_unused.py
+++ b/find_unused.py
@@ -2,47 +2,63 @@
 #
 
 import random
+import math
 
 class table:
        
-       def __init__(self, lowest_id, max_count, max_random):
+       def __init__(self, lowest_id, max_count):
                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
+               print "max[0x%08X] log[0x%08X] log10[0x%08X]" % (max_count, math.log(max_count),math.log10(max_count))
 
-               return idx
+       def range_count(self, max_count):
+               log2 = math.log(1 + max_count,2)
+               log10 = math.log(1 + max_count,10)
+
+               ranges = (max_count / (1000  * int(log10)))
+               #ranges = int(log2) * 10
+
+               ranges = max(ranges, 2)
+
+               ranges = min(ranges, max_count)
+               return ranges
+
+       def range_size(self, idx, max_count):
+               ranges = self.range_count(max_count)
 
-       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):
+       def range_idx(self, id, max_count):
+               ranges = self.range_count(max_count)
+
+               if ranges < 2:
+                       return 0
+
+               range_size = max_count / (ranges - 1)
+               idx = id / range_size
+
+               return idx
+
+       def range_ofs(self, idx, max_count):
+               ranges = self.range_count(max_count)
+
                range_ofs = 0
                for i in range(1, idx):
-                       range_ofs += self.range_size(i, max_count,
-                                       ranges=ranges)
+                       range_ofs += self.range_size(i, max_count)
+
                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
+       def _find_free_random(self, lowest_id, max_count):
 
-               if len(self.db) >= self.max_count:
-                       return None
-
-               max_random = min(self.max_random, max_count)
+               log2 = math.log(2+max_count,2)
+               max_random = int(log2) * 10
 
                for i in range(0, max_random):
                        ran_id = random.randint(0, max_count)
@@ -52,67 +68,113 @@ class table:
                        if id in self.db:
                                continue
 
-                       self.db[id] = id
                        return id
 
-               #return None
-               #raise
+               return None
 
-#              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
+       def _find_free_loop(self, lowest_id, max_count):
+
+               for i in range(0, max_count):
+                       id = lowest_id + i
 
+                       if id in self.db:
+                               continue
+
+                       return id
+
+               return None
+
+       def find_free(self):
+               if len(self.db) >= self.max_count:
+                       return None
+
+               lowest_id = self.lowest_id
+               max_count = self.max_count
+
+               id = self._find_free_random(lowest_id, max_count)
+               if id is not None:
+                       self.db[id] = id
+                       return id
+
+               num_ranges = self.range_count(max_count)
                ranges = {}
-               for i in range(0, 10):
+               for i in range(0, num_ranges):
                        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)
+                       range_idx = self.range_idx(id-lowest_id, max_count)
+                       #print "%08X: %08X range[%04d/%04d]" % (i, id, range_idx,num_ranges)
                        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)
+               mostfree = 0
+               mostfree_idx = 0
 
-               #print "count[0x%04X] max_count[0x%04X]" % (len(self.db), self.max_count)
-               #raise
+               for i in range(0, num_ranges-1):
+                       range_size = self.range_size(i, max_count)
+                       assert ranges[i] <= range_size
+                       free = range_size - ranges[i]
+                       if free > mostfree:
+                               mostfree = free
+                               mostfree_idx = i
+
+               range_ofs = self.range_ofs(mostfree_idx, max_count)
+               range_size = self.range_size(mostfree_idx, max_count)
+               range_free = mostfree
+
+               lowest_id=lowest_id+range_ofs
+               max_count=range_size
+
+               id = self._find_free_random(lowest_id, max_count)
+               if id is not None:
+                       self.db[id] = id
+                       return id
+
+               id = self._find_free_loop(lowest_id, max_count)
+               if id is not None:
+                       self.db[id] = id
+                       return id
+
+               raise
                return None
 
        def run(self):
+               num_ranges = self.range_count(self.max_count)
                ranges = {}
-               for i in range(0, 10):
+               for i in range(0, num_ranges):
                        ranges[i] = 0
 
-               for i in range(0, self.max_count*2):
+               for i in range(self.lowest_id, self.lowest_id+ (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)
+                       print "%08X: %08X range[%04d/%04d]" % (i, id, range_idx, num_ranges)
                        ranges[range_idx] += 1
 
-               for i in range(0, 10):
+               for i in range(0, num_ranges):
                        range_size = self.range_size(i, self.max_count)
-                       print "range[%d] = 0x%04X exp[0x%04X]" % (i, ranges[i], range_size)
+                       #print "range[%04d/%04d] = 0x%04X exp[0x%04X]" % (i, num_ranges, ranges[i], range_size)
 
-               print "count[0x%04X] max_count[0x%04X]" % (len(self.db), self.max_count)
+               #print "count[0x%04X] max_count[0x%04X]" % (len(self.db), self.max_count)
 
-t = table(1, 0xfff-1, None)
+t = table(1, 0xFFFF)
+
+#for i in range(1, 0xFFFF):
+#      mi = i * 0xFFFF
+#      rc = t.range_count(mi)
+#      rm = t.range_size(0, mi)
+#      ru = rm * 999 / 1000
+#      mu = ru * (rc - 1) + t.range_size(rc - 1, mi)
+#      print "mi[%11d/0x%08X] mu[%11d/0x%08X] rc[%8d/0x%04X] rm[%8d/0x%04X] rm[%8d/0x%04X]" % \
+#      (mi, mi, mu, mu, rc, rc, rm, rm, ru, ru)
+
+#max_count = 0x3d
+#num_ranges = t.range_count(max_count)
+#for i in range(0, max_count):
+#      range_idx = t.range_idx(i, max_count)
+#      print "count[0x%04X/0x%04X] range[%04d/%04d]" % (i, max_count, range_idx, num_ranges)
+#
 print "%s" % (t)
 t.run()