← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_simple_set_pyx.pyx

Fix up _simple_set_pyx.pyx to be compatible with pyrex again.

Surprisingly not as easy as I expected, but things seem to be working.
Found an actual bug in the dealloc code...

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_simple_set_pyx.pyx
41
41
_dummy = <PyObject *>_dummy_obj
42
42
 
43
43
 
44
 
cdef inline int _is_equal(PyObject *this, long this_hash, PyObject *other):
 
44
cdef int _is_equal(PyObject *this, long this_hash, PyObject *other):
45
45
    cdef long other_hash
46
46
    cdef PyObject *res
47
47
 
86
86
        cdef Py_ssize_t size, n_bytes
87
87
 
88
88
        size = DEFAULT_SIZE
89
 
        self.mask = size - 1
90
 
        self.used = 0
91
 
        self.fill = 0
 
89
        self._mask = size - 1
 
90
        self._used = 0
 
91
        self._fill = 0
92
92
        n_bytes = sizeof(PyObject*) * size;
93
 
        self.table = <PyObject **>PyMem_Malloc(n_bytes)
94
 
        if self.table == NULL:
 
93
        self._table = <PyObject **>PyMem_Malloc(n_bytes)
 
94
        if self._table == NULL:
95
95
            raise MemoryError()
96
 
        memset(self.table, 0, n_bytes)
 
96
        memset(self._table, 0, n_bytes)
97
97
 
98
98
    def __dealloc__(self):
99
 
        if self.table != NULL:
100
 
            PyMem_Free(self.table)
101
 
            self.table = NULL
 
99
        if self._table != NULL:
 
100
            PyMem_Free(self._table)
 
101
            self._table = NULL
 
102
 
 
103
    property used:
 
104
        def __get__(self):
 
105
            return self._used
 
106
 
 
107
    property fill:
 
108
        def __get__(self):
 
109
            return self._fill
 
110
 
 
111
    property mask:
 
112
        def __get__(self):
 
113
            return self._mask
102
114
 
103
115
    def __len__(self):
104
 
        return self.used
 
116
        return self._used
105
117
 
106
118
    def _test_lookup(self, key):
107
119
        cdef PyObject **slot
113
125
            res = '<dummy>'
114
126
        else:
115
127
            res = <object>slot[0]
116
 
        return <int>(slot - self.table), res
 
128
        return <int>(slot - self._table), res
117
129
 
118
130
    def __contains__(self, key):
119
131
        """Is key present in this SimpleSet."""
154
166
        cdef long the_hash
155
167
        cdef PyObject **table, **entry
156
168
 
157
 
        mask = self.mask
158
 
        table = self.table
 
169
        mask = self._mask
 
170
        table = self._table
159
171
 
160
172
        the_hash = Py_TYPE(key).tp_hash(key)
161
173
        i = the_hash & mask
169
181
            entry = &table[i & mask]
170
182
            perturb >>= PERTURB_SHIFT
171
183
        entry[0] = key
172
 
        self.fill += 1
173
 
        self.used += 1
174
 
 
175
 
    cpdef Py_ssize_t _resize(self, Py_ssize_t min_used) except -1:
 
184
        self._fill += 1
 
185
        self._used += 1
 
186
 
 
187
    def _py_resize(self, min_used):
 
188
        """Do not use this directly, it is only exposed for testing."""
 
189
        return self._resize(min_used)
 
190
 
 
191
    cdef Py_ssize_t _resize(self, Py_ssize_t min_used) except -1:
176
192
        """Resize the internal table.
177
193
 
178
194
        The final table will be big enough to hold at least min_used entries.
190
206
        # We rolled over our signed size field
191
207
        if new_size <= 0:
192
208
            raise MemoryError()
193
 
        # Even if min_used == self.mask + 1, and we aren't changing the actual
 
209
        # Even if min_used == self._mask + 1, and we aren't changing the actual
194
210
        # size, we will still run the algorithm so that dummy entries are
195
211
        # removed
196
212
        # TODO: Test this
197
 
        # if new_size < self.used:
 
213
        # if new_size < self._used:
198
214
        #     raise RuntimeError('cannot shrink SimpleSet to something'
199
215
        #                        ' smaller than the number of used slots.')
200
216
        n_bytes = sizeof(PyObject*) * new_size;
202
218
        if new_table == NULL:
203
219
            raise MemoryError()
204
220
 
205
 
        old_table = self.table
206
 
        self.table = new_table
207
 
        memset(self.table, 0, n_bytes)
208
 
        self.mask = new_size - 1
209
 
        self.used = 0
210
 
        remaining = self.fill
211
 
        self.fill = 0
 
221
        old_table = self._table
 
222
        self._table = new_table
 
223
        memset(self._table, 0, n_bytes)
 
224
        self._mask = new_size - 1
 
225
        self._used = 0
 
226
        remaining = self._fill
 
227
        self._fill = 0
212
228
 
213
229
        # Moving everything to the other table is refcount neutral, so we don't
214
230
        # worry about it.
225
241
        PyMem_Free(old_table)
226
242
        return new_size
227
243
 
228
 
    cpdef object add(self, key):
 
244
    def add(self, key):
229
245
        """Similar to set.add(), start tracking this key.
230
246
        
231
247
        There is one small difference, which is that we return the object that
232
248
        is stored at the given location. (which is closer to the
233
249
        dict.setdefault() functionality.)
234
250
        """
 
251
        return self._add(key)
 
252
 
 
253
    cdef object _add(self, key):
235
254
        cdef PyObject **slot, *py_key
236
 
        cdef int added = 0
 
255
        cdef int added
237
256
 
 
257
        added = 0
238
258
        # We need at least one empty slot
239
 
        assert self.used < self.mask
 
259
        assert self._used < self._mask
240
260
        slot = _lookup(self, key)
241
261
        py_key = <PyObject *>key
242
262
        if (slot[0] == NULL):
243
263
            Py_INCREF(py_key)
244
 
            self.fill += 1
245
 
            self.used += 1
 
264
            self._fill += 1
 
265
            self._used += 1
246
266
            slot[0] = py_key
247
267
            added = 1
248
268
        elif (slot[0] == _dummy):
249
269
            Py_INCREF(py_key)
250
 
            self.used += 1
 
270
            self._used += 1
251
271
            slot[0] = py_key
252
272
            added = 1
253
273
        # No else: clause. If _lookup returns a pointer to
254
274
        # a live object, then we already have a value at this location.
255
275
        retval = <object>(slot[0])
256
276
        # PySet and PyDict use a 2-3rds full algorithm, we'll follow suit
257
 
        if added and (self.fill * 3) >= ((self.mask + 1) * 2):
 
277
        if added and (self._fill * 3) >= ((self._mask + 1) * 2):
258
278
            # However, we always work for a load factor of 2:1
259
 
            self._resize(self.used * 2)
 
279
            self._resize(self._used * 2)
260
280
        # Even if we resized and ended up moving retval into a different slot,
261
281
        # it is still the value that is held at the slot equivalent to 'key',
262
282
        # so we can still return it
263
283
        return retval
264
284
 
265
 
    cpdef int discard(self, key) except -1:
 
285
    def discard(self, key):
266
286
        """Remove key from the dict, whether it exists or not.
267
287
 
268
288
        :return: 0 if the item did not exist, 1 if it did
269
289
        """
 
290
        return self._discard(key)
 
291
 
 
292
    cdef int _discard(self, key) except -1:
270
293
        cdef PyObject **slot, *py_key
271
294
 
272
295
        slot = _lookup(self, key)
273
296
        if slot[0] == NULL or slot[0] == _dummy:
274
297
            return 0
275
 
        self.used -= 1
 
298
        self._used -= 1
276
299
        Py_DECREF(slot[0])
277
300
        slot[0] = _dummy
278
301
        # PySet uses the heuristic: If more than 1/5 are dummies, then resize
279
302
        #                           them away
280
 
        #   if ((so->fill - so->used) * 5 < so->mask)
 
303
        #   if ((so->_fill - so->_used) * 5 < so->mask)
281
304
        # However, we are planning on using this as an interning structure, in
282
305
        # which we will be putting a lot of objects. And we expect that large
283
306
        # groups of them are going to have the same lifetime.
285
308
        # searching, but resizing is also rather expensive
286
309
        # For now, we'll just use their algorithm, but we may want to revisit
287
310
        # it
288
 
        if ((self.fill - self.used) * 5 > self.mask):
289
 
            self._resize(self.used * 2)
 
311
        if ((self._fill - self._used) * 5 > self._mask):
 
312
            self._resize(self._used * 2)
290
313
        return 1
291
314
 
292
315
    def __delitem__(self, key):
295
318
        Raise a KeyError if the key was not present.
296
319
        """
297
320
        cdef int exists
298
 
        exists = self.discard(key)
 
321
        exists = self._discard(key)
299
322
        if not exists:
300
323
            raise KeyError('Key %s not present' % (key,))
301
324
 
308
331
 
309
332
    cdef Py_ssize_t pos
310
333
    cdef SimpleSet set
311
 
    cdef Py_ssize_t used # track if things have been mutated while iterating
 
334
    cdef Py_ssize_t _used # track if things have been mutated while iterating
312
335
    cdef Py_ssize_t len # number of entries left
313
336
 
314
337
    def __init__(self, obj):
315
338
        self.set = obj
316
339
        self.pos = 0
317
 
        self.used = self.set.used
318
 
        self.len = self.set.used
 
340
        self._used = self.set._used
 
341
        self.len = self.set._used
319
342
 
320
343
    def __iter__(self):
321
344
        return self
326
349
 
327
350
        if self.set is None:
328
351
            raise StopIteration
329
 
        if self.set.used != self.used:
 
352
        if self.set._used != self._used:
330
353
            # Force this exception to continue to be raised
331
 
            self.used = -1
 
354
            self._used = -1
332
355
            raise RuntimeError("Set size changed during iteration")
333
356
        i = self.pos
334
 
        mask = self.set.mask
335
 
        table = self.set.table
 
357
        mask = self.set._mask
 
358
        table = self.set._table
336
359
        assert i >= 0
337
360
        while i <= mask and (table[i] == NULL or table[i] == _dummy):
338
361
            i += 1
347
370
        return key
348
371
 
349
372
    def __length_hint__(self):
350
 
        if self.set is not None and self.used == self.set.used:
 
373
        if self.set is not None and self._used == self.set._used:
351
374
            return self.len
352
375
        return 0
353
376
    
358
381
    return SimpleSet()
359
382
 
360
383
 
361
 
cdef inline int _check_self_not_none(object self) except -1:
 
384
cdef SimpleSet _check_self(object self):
362
385
    """Check that the parameter is not None.
363
386
 
364
387
    Pyrex/Cython will do type checking, but only to ensure that an object is
366
389
    python functions, but not for C functions.
367
390
    So this is just a helper for all the apis that need to do the check.
368
391
    """
 
392
    cdef SimpleSet true_self
369
393
    if self is None:
370
394
        raise TypeError('self must not be None')
371
 
 
372
 
 
373
 
cdef inline PyObject **_lookup(SimpleSet self,
374
 
                               object key) except NULL:
 
395
    true_self = self
 
396
    return true_self
 
397
 
 
398
 
 
399
cdef PyObject **_lookup(SimpleSet self, object key) except NULL:
375
400
    """Find the slot where 'key' would fit.
376
401
 
377
402
    This is the same as a dicts 'lookup' function.
390
415
    cdef PyObject **table, **cur, **free_slot, *py_key
391
416
 
392
417
    key_hash = hash(key)
393
 
    mask = self.mask
394
 
    table = self.table
 
418
    mask = self._mask
 
419
    table = self._table
395
420
    i = key_hash & mask
396
421
    cur = &table[i]
397
422
    py_key = <PyObject *>key
436
461
 
437
462
    :param key: An object we are looking up
438
463
    :param hash: The hash for key
439
 
    :return: The location in self.table where key should be put
 
464
    :return: The location in self._table where key should be put
440
465
        should never be NULL, but may reference a NULL (PyObject*)
441
466
    """
442
 
    _check_self_not_none(self)
443
 
    return _lookup(self, key)
 
467
    return _lookup(_check_self(self), key)
444
468
 
445
469
 
446
470
cdef api object SimpleSet_Add(object self, object key):
453
477
        This may be the same object, or it may be an equivalent object.
454
478
        (consider dict.setdefault(key, key))
455
479
    """
456
 
    cdef SimpleSet true_self
457
 
    _check_self_not_none(self)
458
 
    true_self = self
459
 
    return true_self.add(key)
 
480
    return _check_self(self)._add(key)
460
481
    
461
482
 
462
 
cdef api bint SimpleSet_Contains(object self, object key) except -1:
 
483
cdef api int SimpleSet_Contains(object self, object key) except -1:
463
484
    """Is key present in self?"""
464
 
    cdef SimpleSet true_self
465
 
    _check_self_not_none(self)
466
 
    true_self = self
467
 
    return key in true_self
 
485
    return (key in _check_self(self))
468
486
 
469
487
 
470
488
cdef api int SimpleSet_Discard(object self, object key) except -1:
475
493
    :return: 1 if there was an object present, 0 if there was not, and -1 on
476
494
        error.
477
495
    """
478
 
    cdef SimpleSet true_self
479
 
    _check_self_not_none(self)
480
 
    true_self = self
481
 
    return true_self.discard(key)
482
 
 
483
 
 
484
 
cdef api PyObject *SimpleSet_Get(SimpleSet self,
485
 
                                           object key) except? NULL:
 
496
    return _check_self(self)._discard(key)
 
497
 
 
498
 
 
499
cdef api PyObject *SimpleSet_Get(SimpleSet self, object key) except? NULL:
486
500
    """Get a pointer to the object present at location 'key'.
487
501
 
488
502
    This returns an object which is equal to key which was previously added to
492
506
    :param key: The value we are looking for
493
507
    :return: The object present at that location
494
508
    """
495
 
    cdef SimpleSet true_self
496
 
    _check_self_not_none(self)
497
 
    true_self = self
498
 
    return true_self._get(key)
 
509
    return _check_self(self)._get(key)
499
510
 
500
511
 
501
512
cdef api Py_ssize_t SimpleSet_Size(object self) except -1:
502
513
    """Get the number of active entries in 'self'"""
503
 
    cdef SimpleSet true_self = self
504
 
    _check_self_not_none(self)
505
 
    return true_self.used
 
514
    return _check_self(self)._used
506
515
 
507
516
 
508
517
# TODO: this should probably have direct tests, since it isn't used by __iter__
516
525
    :return: 0 if nothing left, 1 if we are returning a new value
517
526
    """
518
527
    cdef Py_ssize_t i, mask
519
 
    cdef SimpleSet true_self = self
 
528
    cdef SimpleSet true_self
520
529
    cdef PyObject **table
521
 
    _check_self_not_none(self)
 
530
    true_self = _check_self(self)
522
531
    i = pos[0]
523
532
    if (i < 0):
524
533
        return 0
525
 
    mask = true_self.mask
526
 
    table= true_self.table
 
534
    mask = true_self._mask
 
535
    table= true_self._table
527
536
    while (i <= mask and (table[i] == NULL or table[i] == _dummy)):
528
537
        i += 1
529
538
    pos[0] = i + 1