tools/deep_memory_profiler/lib/range_dict.py

   1 # Copyright 2013 The Chromium Authors. All rights reserved.
   2 # Use of this source code is governed by a BSD-style license that can be
   3 # found in the LICENSE file.
   4
   5 import os
   6 import sys
   7
   8 _BASE_PATH = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
   9 _BINTREES_PATH = os.path.join(
  10     _BASE_PATH, os.pardir, os.pardir, 'third_party', 'bintrees')
  11 sys.path.insert(0, _BINTREES_PATH)
  12
  13 from bintrees import FastRBTree  # pylint: disable=F0401
  14
  15
  16 class ExclusiveRangeDict(object):
  17   """A class like dict whose key is a range [begin, end) of integers.
  18
  19   It has an attribute for each range of integers, for example:
  20   [10, 20) => Attribute(0),
  21   [20, 40) => Attribute(1),
  22   [40, 50) => Attribute(2),
  23   ...
  24
  25   An instance of this class is accessed only via iter_range(begin, end).
  26   The instance is accessed as follows:
  27
  28   1) If the given range [begin, end) is not covered by the instance,
  29   the range is newly created and iterated.
  30
  31   2) If the given range [begin, end) exactly covers ranges in the instance,
  32   the ranges are iterated.
  33   (See test_set() in tests/range_dict_tests.py.)
  34
  35   3) If the given range [begin, end) starts at and/or ends at a mid-point of
  36   an existing range, the existing range is split by the given range, and
  37   ranges in the given range are iterated.  For example, consider a case that
  38   [25, 45) is given to an instance of [20, 30), [30, 40), [40, 50).  In this
  39   case, [20, 30) is split into [20, 25) and [25, 30), and [40, 50) into
  40   [40, 45) and [45, 50).  Then, [25, 30), [30, 40), [40, 45) are iterated.
  41   (See test_split() in tests/range_dict_tests.py.)
  42
  43   4) If the given range [begin, end) includes non-existing ranges in an
  44   instance, the gaps are filled with new ranges, and all ranges are iterated.
  45   For example, consider a case that [25, 50) is given to an instance of
  46   [30, 35) and [40, 45).  In this case, [25, 30), [35, 40) and [45, 50) are
  47   created in the instance, and then [25, 30), [30, 35), [35, 40), [40, 45)
  48   and [45, 50) are iterated.
  49   (See test_fill() in tests/range_dict_tests.py.)
  50   """
  51   class RangeAttribute(object):
  52     def __init__(self):
  53       pass
  54
  55     def __str__(self):
  56       return '<RangeAttribute>'
  57
  58     def __repr__(self):
  59       return '<RangeAttribute>'
  60
  61     def copy(self):  # pylint: disable=R0201
  62       return ExclusiveRangeDict.RangeAttribute()
  63
  64   def __init__(self, attr=RangeAttribute):
  65     self._tree = FastRBTree()
  66     self._attr = attr
  67
  68   def iter_range(self, begin=None, end=None):
  69     if not begin:
  70       begin = self._tree.min_key()
  71     if not end:
  72       end = self._tree.max_item()[1][0]
  73
  74     # Assume that self._tree has at least one element.
  75     if self._tree.is_empty():
  76       self._tree[begin] = (end, self._attr())
  77
  78     # Create a beginning range (border)
  79     try:
  80       bound_begin, bound_value = self._tree.floor_item(begin)
  81       bound_end = bound_value[0]
  82       if begin >= bound_end:
  83         # Create a blank range.
  84         try:
  85           new_end, _ = self._tree.succ_item(bound_begin)
  86         except KeyError:
  87           new_end = end
  88         self._tree[begin] = (min(end, new_end), self._attr())
  89       elif bound_begin < begin and begin < bound_end:
  90         # Split the existing range.
  91         new_end = bound_value[0]
  92         new_value = bound_value[1]
  93         self._tree[bound_begin] = (begin, new_value.copy())
  94         self._tree[begin] = (new_end, new_value.copy())
  95       else:  # bound_begin == begin
  96         # Do nothing (just saying it clearly since this part is confusing)
  97         pass
  98     except KeyError:  # begin is less than the smallest element.
  99       # Create a blank range.
 100       # Note that we can assume self._tree has at least one element.
 101       self._tree[begin] = (min(end, self._tree.min_key()), self._attr())
 102
 103     # Create an ending range (border)
 104     try:
 105       bound_begin, bound_value = self._tree.floor_item(end)
 106       bound_end = bound_value[0]
 107       if end > bound_end:
 108         # Create a blank range.
 109         new_begin = bound_end
 110         self._tree[new_begin] = (end, self._attr())
 111       elif bound_begin < end and end < bound_end:
 112         # Split the existing range.
 113         new_end = bound_value[0]
 114         new_value = bound_value[1]
 115         self._tree[bound_begin] = (end, new_value.copy())
 116         self._tree[end] = (new_end, new_value.copy())
 117       else:  # bound_begin == begin
 118         # Do nothing (just saying it clearly since this part is confusing)
 119         pass
 120     except KeyError:  # end is less than the smallest element.
 121       # It must not happen.  A blank range [begin,end) has already been created
 122       # even if [begin,end) is less than the smallest range.
 123       # Do nothing (just saying it clearly since this part is confusing)
 124       raise
 125
 126     missing_ranges = []
 127
 128     prev_end = None
 129     for range_begin, range_value in self._tree.itemslice(begin, end):
 130       range_end = range_value[0]
 131       # Note that we can assume that we have a range beginning with |begin|
 132       # and a range ending with |end| (they may be the same range).
 133       if prev_end and prev_end != range_begin:
 134         missing_ranges.append((prev_end, range_begin))
 135       prev_end = range_end
 136
 137     for missing_begin, missing_end in missing_ranges:
 138       self._tree[missing_begin] = (missing_end, self._attr())
 139
 140     for range_begin, range_value in self._tree.itemslice(begin, end):
 141       yield range_begin, range_value[0], range_value[1]
 142
 143   def __str__(self):
 144     return str(self._tree)