← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_static_tuple_interned_pyx.pyx

Implement resizing.

It can resize up or down, but right now we never shrink.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_static_tuple_interned_pyx.pyx
100
100
        self.fill = 0
101
101
        n_bytes = sizeof(PyObject*) * size;
102
102
        self.table = <PyObject **>PyMem_Malloc(n_bytes)
103
 
        # TODO: Raise MemoryError if malloc fails
 
103
        if self.table == NULL:
 
104
            raise MemoryError()
104
105
        memset(self.table, 0, n_bytes)
105
106
 
106
107
    def __dealloc__(self):
155
156
    #     assert key == value
156
157
    #     self._add(key)
157
158
 
 
159
    cdef int _insert_clean(self, PyObject *key) except -1:
 
160
        """Insert a key into self.table.
 
161
 
 
162
        This is only meant to be used during times like '_resize',
 
163
        as it makes a lot of assuptions about keys not already being present,
 
164
        and there being no dummy entries.
 
165
        """
 
166
        cdef size_t i, perturb, mask
 
167
        cdef long the_hash
 
168
        cdef PyObject **table, **entry
 
169
 
 
170
        mask = self.mask
 
171
        table = self.table
 
172
 
 
173
        the_hash = Py_TYPE(key).tp_hash(key)
 
174
        i = the_hash & mask
 
175
        entry = &table[i]
 
176
        perturb = the_hash
 
177
        # Because we know that we made all items unique before, we can just
 
178
        # iterate as long as the target location is not empty, we don't have to
 
179
        # do any comparison, etc.
 
180
        while entry[0] != NULL:
 
181
            i = (i << 2) + i + perturb + 1
 
182
            entry = &table[i & mask]
 
183
            perturb >>= PERTURB_SHIFT
 
184
        entry[0] = key
 
185
        self.fill += 1
 
186
        self.used += 1
 
187
 
 
188
    cpdef Py_ssize_t _resize(self, Py_ssize_t min_used) except -1:
 
189
        """Resize the internal table.
 
190
 
 
191
        The final table will be big enough to hold at least min_used entries.
 
192
        We will copy the data from the existing table over, leaving out dummy
 
193
        entries.
 
194
 
 
195
        :return: The new size of the internal table
 
196
        """
 
197
        cdef Py_ssize_t new_size, n_bytes, remaining
 
198
        cdef PyObject **new_table, **old_table, **entry
 
199
 
 
200
        new_size = DEFAULT_SIZE
 
201
        while new_size <= min_used and new_size > 0:
 
202
            new_size = new_size << 1
 
203
        # We rolled over our signed size field
 
204
        if new_size <= 0:
 
205
            raise MemoryError()
 
206
        if new_size == (self.mask + 1):
 
207
            # Nothing to do
 
208
            return new_size
 
209
        # TODO: Test this
 
210
        # if new_size < self.used:
 
211
        #     raise RuntimeError('cannot shrink StaticTupleInterner to something'
 
212
        #                        ' smaller than the number of used slots.')
 
213
        n_bytes = sizeof(PyObject*) * new_size;
 
214
        new_table = <PyObject **>PyMem_Malloc(n_bytes)
 
215
        if new_table == NULL:
 
216
            raise MemoryError()
 
217
 
 
218
        old_table = self.table
 
219
        self.table = new_table
 
220
        memset(self.table, 0, n_bytes)
 
221
        self.mask = new_size - 1
 
222
        self.used = 0
 
223
        remaining = self.fill
 
224
        self.fill = 0
 
225
 
 
226
        # Moving everything to the other table is refcount neutral, so we don't
 
227
        # worry about it.
 
228
        entry = old_table
 
229
        while remaining > 0:
 
230
            if entry[0] == NULL: # unused slot
 
231
                pass 
 
232
            elif entry[0] == _dummy: # dummy slot
 
233
                remaining -= 1
 
234
            else: # active slot
 
235
                remaining -= 1
 
236
                self._insert_clean(entry[0])
 
237
            entry += 1
 
238
        PyMem_Free(old_table)
 
239
        return new_size
 
240
 
158
241
    cpdef object add(self, key):
159
242
        """Similar to set.add(), start tracking this key.
160
243
        
163
246
        dict.setdefault() functionality.)
164
247
        """
165
248
        cdef PyObject **slot, *py_key
 
249
        cdef int added = 0
166
250
 
 
251
        # We need at least one empty slot
 
252
        assert self.used < self.mask
167
253
        slot = _lookup(self, key)
168
254
        py_key = <PyObject *>key
169
255
        if (slot[0] == NULL):
171
257
            self.fill += 1
172
258
            self.used += 1
173
259
            slot[0] = py_key
 
260
            added = 1
174
261
        elif (slot[0] == _dummy):
175
262
            Py_INCREF(py_key)
176
263
            self.used += 1
177
264
            slot[0] = py_key
 
265
            added = 1
178
266
        # No else: clause. If _lookup returns a pointer to
179
267
        # a live object, then we already have a value at this location.
180
 
        return <object>(slot[0])
 
268
        retval = <object>(slot[0])
 
269
        # PySet and PyDict use a 2-3rds full algorithm, we'll follow suit
 
270
        if added and (self.fill * 3) >= ((self.mask + 1) * 2):
 
271
            # However, we always work for a load factor of 2:1
 
272
            self._resize(self.used * 2)
 
273
        # Even if we resized and ended up moving retval into a different slot,
 
274
        # it is still the value that is held at the slot equivalent to 'key',
 
275
        # so we can still return it
 
276
        return retval
181
277
 
182
278
    cpdef int discard(self, key) except -1:
183
279
        """Remove key from the dict, whether it exists or not.