← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_simple_set_pyx.pyx

Rename StaticTupleInterner => SimpleSet.

This is a bit more appropriate, because the internal data type is not
specialized into StaticTuple objects only. Partially because I didn't
see a specific memory/speed tradeoff to caching the hash, and
that accessing said hash was siginficantly faster than just
calling PyObject_Hash().

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_simple_set_pyx.pyx
14
14
# along with this program; if not, write to the Free Software
15
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
 
"""Definition of a class that is used to intern StaticTuple objects."""
 
17
"""Definition of a class that is similar to Set with some small changes."""
18
18
 
19
19
cdef extern from "Python.h":
20
20
    ctypedef unsigned long size_t
54
54
    if res == Py_True:
55
55
        Py_DECREF(res)
56
56
        return 1
57
 
    # Only handled for now because we are testing with stuff like tuples versus
58
 
    # StaticTuple objects. If we decide to limit StaticTupleInterner to
59
 
    # strictly only allowing StaticTuple objects, then this is no longer
60
 
    # required, and Py_NotImplemented => not equal
61
57
    if res == Py_NotImplemented:
62
58
        Py_DECREF(res)
63
59
        res = Py_TYPE(other).tp_richcompare(other, this, Py_EQ)
68
64
    return 0
69
65
 
70
66
 
71
 
cdef public api class StaticTupleInterner [object StaticTupleInternerObject,
72
 
                                           type StaticTupleInterner_type]:
73
 
    """This class tracks the canonical forms for StaticTuples.
 
67
cdef public api class SimpleSet [object SimpleSetObject, type SimpleSet_Type]:
 
68
    """This class can be used to track canonical forms for objects.
74
69
 
75
70
    It is similar in function to the interned dictionary that is used by
76
71
    strings. However:
87
82
    DEF DEFAULT_SIZE=1024
88
83
    DEF PERTURB_SHIFT=5
89
84
 
90
 
    # Note that most of the members on this class are just thunks over to the C
91
 
    # api. However, this provides a nice Python/Pyrex api, as well as making it
92
 
    # easy to test the C api from pure python.
93
 
 
94
85
    def __init__(self):
95
86
        cdef Py_ssize_t size, n_bytes
96
87
 
125
116
        return <int>(slot - self.table), res
126
117
 
127
118
    def __contains__(self, key):
128
 
        """Is key present in this StaticTupleInterner."""
 
119
        """Is key present in this SimpleSet."""
129
120
        cdef PyObject **slot
130
121
 
131
122
        slot = _lookup(self, key)
152
143
        val = <object>(py_val)
153
144
        return val
154
145
 
155
 
    # def __setitem__(self, key, value):
156
 
    #     assert key == value
157
 
    #     self._add(key)
158
 
 
159
146
    cdef int _insert_clean(self, PyObject *key) except -1:
160
147
        """Insert a key into self.table.
161
148
 
208
195
        # removed
209
196
        # TODO: Test this
210
197
        # if new_size < self.used:
211
 
        #     raise RuntimeError('cannot shrink StaticTupleInterner to something'
 
198
        #     raise RuntimeError('cannot shrink SimpleSet to something'
212
199
        #                        ' smaller than the number of used slots.')
213
200
        n_bytes = sizeof(PyObject*) * new_size;
214
201
        new_table = <PyObject **>PyMem_Malloc(n_bytes)
313
300
            raise KeyError('Key %s not present' % (key,))
314
301
 
315
302
    def __iter__(self):
316
 
        return _StaticTupleInterner_iterator(self)
317
 
 
318
 
 
319
 
cdef class _StaticTupleInterner_iterator:
320
 
    """Iterator over the StaticTupleInterner structure."""
 
303
        return _SimpleSet_iterator(self)
 
304
 
 
305
 
 
306
cdef class _SimpleSet_iterator:
 
307
    """Iterator over the SimpleSet structure."""
321
308
 
322
309
    cdef Py_ssize_t pos
323
 
    cdef StaticTupleInterner table
 
310
    cdef SimpleSet set
324
311
    cdef Py_ssize_t used # track if things have been mutated while iterating
325
312
    cdef Py_ssize_t len # number of entries left
326
313
 
327
314
    def __init__(self, obj):
328
 
        self.table = obj
 
315
        self.set = obj
329
316
        self.pos = 0
330
 
        self.used = self.table.used
331
 
        self.len = self.table.used
 
317
        self.used = self.set.used
 
318
        self.len = self.set.used
332
319
 
333
320
    def __iter__(self):
334
321
        return self
337
324
        cdef Py_ssize_t mask, i
338
325
        cdef PyObject **table
339
326
 
340
 
        if self.table is None:
 
327
        if self.set is None:
341
328
            raise StopIteration
342
 
        if self.table.used != self.used:
 
329
        if self.set.used != self.used:
343
330
            # Force this exception to continue to be raised
344
331
            self.used = -1
345
332
            raise RuntimeError("Set size changed during iteration")
346
333
        i = self.pos
347
 
        mask = self.table.mask
348
 
        table = self.table.table
 
334
        mask = self.set.mask
 
335
        table = self.set.table
349
336
        assert i >= 0
350
337
        while i <= mask and (table[i] == NULL or table[i] == _dummy):
351
338
            i += 1
352
339
        self.pos = i + 1
353
340
        if i > mask:
354
341
            # we walked to the end
355
 
            self.table = None
 
342
            self.set = None
356
343
            raise StopIteration
357
344
        # We must have found one
358
345
        key = <object>(table[i])
360
347
        return key
361
348
 
362
349
    def __length_hint__(self):
363
 
        if self.table is not None and self.used == self.table.used:
 
350
        if self.set is not None and self.used == self.set.used:
364
351
            return self.len
365
352
        return 0
366
353
    
367
354
 
368
355
 
369
 
cdef api StaticTupleInterner StaticTupleInterner_New():
370
 
    """Create a new StaticTupleInterner object."""
371
 
    return StaticTupleInterner()
 
356
cdef api SimpleSet SimpleSet_New():
 
357
    """Create a new SimpleSet object."""
 
358
    return SimpleSet()
372
359
 
373
360
 
374
361
cdef inline int _check_self_not_none(object self) except -1:
383
370
        raise TypeError('self must not be None')
384
371
 
385
372
 
386
 
cdef inline PyObject **_lookup(StaticTupleInterner self,
 
373
cdef inline PyObject **_lookup(SimpleSet self,
387
374
                               object key) except NULL:
388
375
    """Find the slot where 'key' would fit.
389
376
 
439
426
    raise AssertionError('should never get here')
440
427
 
441
428
 
442
 
cdef api PyObject **_StaticTupleInterner_Lookup(object self,
 
429
cdef api PyObject **_SimpleSet_Lookup(object self,
443
430
                                                object key) except NULL:
444
431
    """Find the slot where 'key' would fit.
445
432
 
456
443
    return _lookup(self, key)
457
444
 
458
445
 
459
 
cdef api object StaticTupleInterner_Add(object self, object key):
460
 
    """Add a key to the StaticTupleInterner (set).
 
446
cdef api object SimpleSet_Add(object self, object key):
 
447
    """Add a key to the SimpleSet (set).
461
448
 
462
 
    :param self: The StaticTupleInterner to add the key to.
 
449
    :param self: The SimpleSet to add the key to.
463
450
    :param key: The key to be added. If the key is already present,
464
451
        self will not be modified
465
452
    :return: The current key stored at the location defined by 'key'.
466
453
        This may be the same object, or it may be an equivalent object.
467
454
        (consider dict.setdefault(key, key))
468
455
    """
469
 
    cdef StaticTupleInterner true_self
 
456
    cdef SimpleSet true_self
470
457
    _check_self_not_none(self)
471
458
    true_self = self
472
459
    return true_self.add(key)
473
460
    
474
461
 
475
 
cdef api bint StaticTupleInterner_Contains(object self, object key) except -1:
 
462
cdef api bint SimpleSet_Contains(object self, object key) except -1:
476
463
    """Is key present in self?"""
477
 
    cdef StaticTupleInterner true_self
 
464
    cdef SimpleSet true_self
478
465
    _check_self_not_none(self)
479
466
    true_self = self
480
467
    return key in true_self
481
468
 
482
469
 
483
 
cdef api int StaticTupleInterner_Discard(object self, object key) except -1:
 
470
cdef api int SimpleSet_Discard(object self, object key) except -1:
484
471
    """Remove the object referenced at location 'key'.
485
472
 
486
 
    :param self: The StaticTupleInterner being modified
 
473
    :param self: The SimpleSet being modified
487
474
    :param key: The key we are checking on
488
475
    :return: 1 if there was an object present, 0 if there was not, and -1 on
489
476
        error.
490
477
    """
491
 
    cdef StaticTupleInterner true_self
 
478
    cdef SimpleSet true_self
492
479
    _check_self_not_none(self)
493
480
    true_self = self
494
481
    return true_self.discard(key)
495
482
 
496
483
 
497
 
cdef api PyObject *StaticTupleInterner_Get(StaticTupleInterner self,
 
484
cdef api PyObject *SimpleSet_Get(SimpleSet self,
498
485
                                           object key) except? NULL:
499
486
    """Get a pointer to the object present at location 'key'.
500
487
 
505
492
    :param key: The value we are looking for
506
493
    :return: The object present at that location
507
494
    """
508
 
    cdef StaticTupleInterner true_self
 
495
    cdef SimpleSet true_self
509
496
    _check_self_not_none(self)
510
497
    true_self = self
511
498
    return true_self._get(key)
512
499
 
513
500
 
514
 
cdef api Py_ssize_t StaticTupleInterner_Size(object self) except -1:
 
501
cdef api Py_ssize_t SimpleSet_Size(object self) except -1:
515
502
    """Get the number of active entries in 'self'"""
516
 
    cdef StaticTupleInterner true_self = self
 
503
    cdef SimpleSet true_self = self
517
504
    _check_self_not_none(self)
518
505
    return true_self.used
519
506
 
520
507
 
521
508
# TODO: this should probably have direct tests, since it isn't used by __iter__
522
 
cdef api int StaticTupleInterner_Next(object self, Py_ssize_t *pos,
 
509
cdef api int SimpleSet_Next(object self, Py_ssize_t *pos,
523
510
                                      PyObject **key):
524
 
    """Walk over items in a StaticTupleInterner.
 
511
    """Walk over items in a SimpleSet.
525
512
 
526
513
    :param pos: should be initialized to 0 by the caller, and will be updated
527
514
        by this function
529
516
    :return: 0 if nothing left, 1 if we are returning a new value
530
517
    """
531
518
    cdef Py_ssize_t i, mask
532
 
    cdef StaticTupleInterner true_self = self
 
519
    cdef SimpleSet true_self = self
533
520
    cdef PyObject **table
534
521
    _check_self_not_none(self)
535
522
    i = pos[0]