Add range_dict.py to handle a range-based dict.

It uses third_party bintrees internally: http://crrev.com/186589.

BUG=174304
NOTRY=true


Review URL: https://chromiumcodereview.appspot.com/12974006

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@190811 0039d316-1c4b-4281-b951-d872f2087c98

2 files changed, 275 insertions, 0 deletions

diff --git a/tools/deep_memory_profiler/range_dict.py b/tools/deep_memory_profiler/range_dict.py
new file mode 100644
index 0000000..9acf8a6
--- /dev/null
+++ b/tools/deep_memory_profiler/range_dict.py
@@ -0,0 +1,144 @@
+# Copyright (c) 2013 The Chromium Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+
+import os
+import sys
+
+BASE_PATH = os.path.dirname(os.path.abspath(__file__))
+BINTREES_PATH = os.path.join(
+    BASE_PATH, os.pardir, os.pardir, 'third_party', 'bintrees')
+sys.path.insert(0, BINTREES_PATH)
+
+from bintrees import FastRBTree  # pylint: disable=F0401
+
+
+class ExclusiveRangeDict(object):
+  """A class like dict whose key is a range [begin, end) of integers.
+
+  It has an attribute for each range of integers, for example:
+  [10, 20) => Attribute(0),
+  [20, 40) => Attribute(1),
+  [40, 50) => Attribute(2),
+  ...
+
+  An instance of this class is accessed only via iter_range(begin, end).
+  The instance is accessed as follows:
+
+  1) If the given range [begin, end) is not covered by the instance,
+  the range is newly created and iterated.
+
+  2) If the given range [begin, end) exactly covers ranges in the instance,
+  the ranges are iterated.
+  (See test_set() in tests/range_dict_tests.py.)
+
+  3) If the given range [begin, end) starts at and/or ends at a mid-point of
+  an existing range, the existing range is split by the given range, and
+  ranges in the given range are iterated.  For example, consider a case that
+  [25, 45) is given to an instance of [20, 30), [30, 40), [40, 50).  In this
+  case, [20, 30) is split into [20, 25) and [25, 30), and [40, 50) into
+  [40, 45) and [45, 50).  Then, [25, 30), [30, 40), [40, 45) are iterated.
+  (See test_split() in tests/range_dict_tests.py.)
+
+  4) If the given range [begin, end) includes non-existing ranges in an
+  instance, the gaps are filled with new ranges, and all ranges are iterated.
+  For example, consider a case that [25, 50) is given to an instance of
+  [30, 35) and [40, 45).  In this case, [25, 30), [35, 40) and [45, 50) are
+  created in the instance, and then [25, 30), [30, 35), [35, 40), [40, 45)
+  and [45, 50) are iterated.
+  (See test_fill() in tests/range_dict_tests.py.)
+  """
+  class RangeAttribute(object):
+    def __init__(self):
+      pass
+
+    def __str__(self):
+      return '<RangeAttribute>'
+
+    def __repr__(self):
+      return '<RangeAttribute>'
+
+    def copy(self):  # pylint: disable=R0201
+      return ExclusiveRangeDict.RangeAttribute()
+
+  def __init__(self, attr=RangeAttribute):
+    self._tree = FastRBTree()
+    self._attr = attr
+
+  def iter_range(self, begin=None, end=None):
+    if not begin:
+      begin = self._tree.min_key()
+    if not end:
+      end = self._tree.max_item()[1][0]
+
+    # Assume that self._tree has at least one element.
+    if self._tree.is_empty():
+      self._tree[begin] = (end, self._attr())
+
+    # Create a beginning range (border)
+    try:
+      bound_begin, bound_value = self._tree.floor_item(begin)
+      bound_end = bound_value[0]
+      if begin >= bound_end:
+        # Create a blank range.
+        try:
+          new_end, _ = self._tree.succ_item(bound_begin)
+        except KeyError:
+          new_end = end
+        self._tree[begin] = (min(end, new_end), self._attr())
+      elif bound_begin < begin and begin < bound_end:
+        # Split the existing range.
+        new_end = bound_value[0]
+        new_value = bound_value[1]
+        self._tree[bound_begin] = (begin, new_value.copy())
+        self._tree[begin] = (new_end, new_value.copy())
+      else:  # bound_begin == begin
+        # Do nothing (just saying it clearly since this part is confusing)
+        pass
+    except KeyError:  # begin is less than the smallest element.
+      # Create a blank range.
+      # Note that we can assume self._tree has at least one element.
+      self._tree[begin] = (min(end, self._tree.min_key()), self._attr())
+
+    # Create an ending range (border)
+    try:
+      bound_begin, bound_value = self._tree.floor_item(end)
+      bound_end = bound_value[0]
+      if end > bound_end:
+        # Create a blank range.
+        new_begin = bound_end
+        self._tree[new_begin] = (end, self._attr())
+      elif bound_begin < end and end < bound_end:
+        # Split the existing range.
+        new_end = bound_value[0]
+        new_value = bound_value[1]
+        self._tree[bound_begin] = (end, new_value.copy())
+        self._tree[end] = (new_end, new_value.copy())
+      else:  # bound_begin == begin
+        # Do nothing (just saying it clearly since this part is confusing)
+        pass
+    except KeyError:  # end is less than the smallest element.
+      # It must not happen.  A blank range [begin,end) has already been created
+      # even if [begin,end) is less than the smallest range.
+      # Do nothing (just saying it clearly since this part is confusing)
+      raise
+
+    missing_ranges = []
+
+    prev_end = None
+    for range_begin, range_value in self._tree.itemslice(begin, end):
+      range_end = range_value[0]
+      # Note that we can assume that we have a range beginning with |begin|
+      # and a range ending with |end| (they may be the same range).
+      if prev_end and prev_end != range_begin:
+        missing_ranges.append((prev_end, range_begin))
+      prev_end = range_end
+
+    for missing_begin, missing_end in missing_ranges:
+      self._tree[missing_begin] = (missing_end, self._attr())
+
+    for range_begin, range_value in self._tree.itemslice(begin, end):
+      yield range_begin, range_value[0], range_value[1]
+
+  def __str__(self):
+    return str(self._tree)
diff --git a/tools/deep_memory_profiler/tests/range_dict_tests.py b/tools/deep_memory_profiler/tests/range_dict_tests.py
new file mode 100755
index 0000000..4c7e50b
--- /dev/null
+++ b/tools/deep_memory_profiler/tests/range_dict_tests.py
@@ -0,0 +1,131 @@
+#!/usr/bin/env python
+# Copyright (c) 2013 The Chromium Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+
+import logging
+import os
+import sys
+import unittest
+
+ROOT_DIR = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
+sys.path.insert(0, ROOT_DIR)
+
+import range_dict
+
+
+class ExclusiveRangeDictTest(unittest.TestCase):
+  class TestAttribute(range_dict.ExclusiveRangeDict.RangeAttribute):
+    def __init__(self):
+      super(ExclusiveRangeDictTest.TestAttribute, self).__init__()
+      self._value = 0
+
+    def __str__(self):
+      return str(self._value)
+
+    def __repr__(self):
+      return '<TestAttribute:%d>' % self._value
+
+    def get(self):
+      return self._value
+
+    def set(self, new_value):
+      self._value = new_value
+
+    def copy(self):  # pylint: disable=R0201
+      new_attr = ExclusiveRangeDictTest.TestAttribute()
+      new_attr.set(self._value)
+      return new_attr
+
+  def test_init(self):
+    ranges = range_dict.ExclusiveRangeDict(self.TestAttribute)
+
+    result = []
+    for begin, end, attr in ranges.iter_range(20, 40):
+      result.append({'begin': begin, 'end':end, 'attr':attr.get()})
+    expected = [
+        {'begin': 20, 'end': 40, 'attr': 0},
+        ]
+    self.assertEqual(expected, result)
+
+  def test_norange(self):
+    ranges = range_dict.ExclusiveRangeDict(self.TestAttribute)
+
+    result = []
+    for begin, end, attr in ranges.iter_range(20, 20):
+      result.append({'begin': begin, 'end':end, 'attr':attr.get()})
+    expected = []
+    self.assertEqual(expected, result)
+
+  def test_set(self):
+    ranges = range_dict.ExclusiveRangeDict(self.TestAttribute)
+    for begin, end, attr in ranges.iter_range(20, 30):
+      attr.set(12)
+    for begin, end, attr in ranges.iter_range(30, 40):
+      attr.set(52)
+
+    result = []
+    for begin, end, attr in ranges.iter_range(20, 40):
+      result.append({'begin': begin, 'end':end, 'attr':attr.get()})
+    expected = [
+        {'begin': 20, 'end': 30, 'attr': 12},
+        {'begin': 30, 'end': 40, 'attr': 52},
+        ]
+    self.assertEqual(expected, result)
+
+  def test_split(self):
+    ranges = range_dict.ExclusiveRangeDict(self.TestAttribute)
+    for begin, end, attr in ranges.iter_range(20, 30):
+      attr.set(1000)
+    for begin, end, attr in ranges.iter_range(30, 40):
+      attr.set(2345)
+    for begin, end, attr in ranges.iter_range(40, 50):
+      attr.set(3579)
+
+    result1 = []
+    for begin, end, attr in ranges.iter_range(25, 45):
+      result1.append({'begin': begin, 'end':end, 'attr':attr.get()})
+    expected1 = [
+        {'begin': 25, 'end': 30, 'attr': 1000},
+        {'begin': 30, 'end': 40, 'attr': 2345},
+        {'begin': 40, 'end': 45, 'attr': 3579},
+        ]
+    self.assertEqual(expected1, result1)
+
+    result2 = []
+    for begin, end, attr in ranges.iter_range(20, 50):
+      result2.append({'begin': begin, 'end':end, 'attr':attr.get()})
+    expected2 = [
+        {'begin': 20, 'end': 25, 'attr': 1000},
+        {'begin': 25, 'end': 30, 'attr': 1000},
+        {'begin': 30, 'end': 40, 'attr': 2345},
+        {'begin': 40, 'end': 45, 'attr': 3579},
+        {'begin': 45, 'end': 50, 'attr': 3579},
+        ]
+    self.assertEqual(expected2, result2)
+
+  def test_fill(self):
+    ranges = range_dict.ExclusiveRangeDict(self.TestAttribute)
+    for begin, end, attr in ranges.iter_range(30, 35):
+      attr.set(12345)
+    for begin, end, attr in ranges.iter_range(40, 45):
+      attr.set(97531)
+
+    result = []
+    for begin, end, attr in ranges.iter_range(25, 50):
+      result.append({'begin': begin, 'end':end, 'attr':attr.get()})
+    expected = [
+        {'begin': 25, 'end': 30, 'attr': 0},
+        {'begin': 30, 'end': 35, 'attr': 12345},
+        {'begin': 35, 'end': 40, 'attr': 0},
+        {'begin': 40, 'end': 45, 'attr': 97531},
+        {'begin': 45, 'end': 50, 'attr': 0},
+        ]
+    self.assertEqual(expected, result)
+
+
+if __name__ == '__main__':
+  logging.basicConfig(
+      level=logging.DEBUG if '-v' in sys.argv else logging.ERROR,
+      format='%(levelname)5s %(filename)15s(%(lineno)3d): %(message)s')
+  unittest.main()