This file is indexed.

/usr/lib/python2.7/dist-packages/larch/nodes.py is in python-larch 1.20151025-1.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
# Copyright 2010  Lars Wirzenius
# 
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
# 
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
# 
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.


import bisect

import larch


class FrozenNode(larch.Error):

    '''User tried to modify node that is frozen.'''

    def __init__(self, node):
        self.msg = 'Node %s is frozen against modifications' % node.id


class Node(object):

    '''Abstract base class for index and leaf nodes.
    
    A node may be initialized with a list of (key, value) pairs. For
    leaf nodes, the values are the actual values. For index nodes, they
    are references to other nodes.
    
    A node can be indexed using keys, and give the corresponding value.
    Setting key/value pairs cannot be done using indexing. However,
    ``key in node`` does work, as does iteration over a key's values.
    ``len(node)`` returns the number if keys.
    
    Two nodes compare equal if they have the same key/value pairs.
    The node ids do not need to match.
    
    Nodes can be modified, bt only if the ``frozen`` property is false.
    If it is set to true, any attempt at modifying the node causes
    the ``FrozenNode`` exception to be raised.
    
    '''

    def __init__(self, node_id, keys, values):
        self._keys = list(keys)
        self._values = list(values)
        self._dict = dict()
        for i in range(len(keys)):
            self._dict[keys[i]] = values[i]
        self.id = node_id
        self.size = None
        self.frozen = False

    def __getitem__(self, key):
        return self._dict[key]

    def __contains__(self, key):
        return key in self._dict

    def __eq__(self, other):
        return self._keys == other._keys and self._values == other._values

    def __iter__(self):
        for key in self._keys:
            yield key

    def __len__(self):
        return len(self._keys)

    def __nonzero__(self):
        return True

    def keys(self):
        '''Return keys in the node, sorted.'''
        return self._keys

    def values(self):
        '''Return value in the node, in same order as keys.'''
        return self._values

    def first_key(self):
        '''Return smallest key in the node.'''
        return self._keys[0]

    def find_potential_range(self, minkey, maxkey):
        '''Find pairs whose key is in desired range.

        ``minkey`` and ``maxkey`` are inclusive.

        We take into account that for index nodes, a child's key
        really represents a range of keys, from the key up to (but
        not including) the next child's key. The last child's key
        represents a range up to infinity.

        Thus we return the first child, if its key lies between
        ``minkey`` and ``maxkey``, and the last child, if its key is at most
        ``maxkey``.

        '''
        
        def helper(key, default):
            x = bisect.bisect_left(self._keys, key)
            if x < len(self._keys):
                if self._keys[x] > key:
                    if x == 0:
                        x = default
                    else:
                        x -= 1
            else:
                if x == 0:
                    x = None
                else:
                    x -= 1
            return x

        i = helper(minkey, 0)
        j = helper(maxkey, None)
        if j is None:
            i = None

        return i, j

    def _error_if_frozen(self):
        if self.frozen:
            raise FrozenNode(self)

    def add(self, key, value):
        '''Insert a key/value pair into the right place in a node.'''

        self._error_if_frozen()

        i = bisect.bisect_left(self._keys, key)
        if i < len(self._keys) and self._keys[i] == key:
            self._keys[i] = key
            self._values[i] = value
        else:
            self._keys.insert(i, key)
            self._values.insert(i, value)

        self._dict[key] = value
        self.size = None

    def remove(self, key):
        '''Remove a key from the node.
        
        Raise KeyError if key does not exist in node.
        
        '''
        
        self._error_if_frozen()

        i = bisect.bisect_left(self._keys, key)
        if i >= len(self._keys) or self._keys[i] != key:
            raise KeyError(key)
        del self._keys[i]
        del self._values[i]
        del self._dict[key]
        self.size = None
        
    def remove_index_range(self, lo, hi):
        '''Remove keys given a range of indexes into pairs.
        
        lo and hi are inclusive.
        
        '''
        
        self._error_if_frozen()

        del self._keys[lo:hi+1]
        del self._values[lo:hi+1]
        self.size = None


class LeafNode(Node):

    '''Leaf node in the tree.
    
    A leaf node contains key/value pairs (both strings), and has no children.
    
    '''

    def find_keys_in_range(self, minkey, maxkey):
        '''Find pairs whose key is in desired range.
        
        ``minkey`` and ``maxkey`` are inclusive.
        
        '''
        
        i = bisect.bisect_left(self._keys, minkey)
        j = bisect.bisect_left(self._keys, maxkey)
        if j < len(self._keys) and self._keys[j] == maxkey:
            j += 1
        return self._keys[i:j]


class IndexNode(Node):

    '''Index node in the tree.
    
    An index node contains pairs of keys and references to other nodes
    (node ids, which are integers).
    The other nodes may be either index nodes or leaf nodes.
    
    '''

    def find_key_for_child_containing(self, key):
        '''Return key for the child that contains ``key``.'''

        i = bisect.bisect_left(self._keys, key)
        if i < len(self._keys):
            if self._keys[i] == key:
                return key
            elif i:
                return self._keys[i-1]
        elif i:
            return self._keys[i-1]

    def find_children_in_range(self, minkey, maxkey):
        '''Find all children whose key is in the range.
        
        ``minkey`` and ``maxkey`` are inclusive. Note that a child might
        be returned even if not all of its keys are in the range,
        just some of them. Also, we consider potential keys here,
        not actual keys. We have no way to retrieve the children
        to check which keys they actually have, so instead we
        return which keys might have the desired keys, and the
        caller can go look at those.
        
        '''
        
        i, j = self.find_potential_range(minkey, maxkey)
        if i is not None and j is not None:
            return self._values[i:j+1]
        else:
            return []