/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to breezy/_simple_set_pyx.pyx

  • Committer: Jelmer Vernooij
  • Date: 2020-04-05 19:11:34 UTC
  • mto: (7490.7.16 work)
  • mto: This revision was merged to the branch mainline in revision 7501.
  • Revision ID: jelmer@jelmer.uk-20200405191134-0aebh8ikiwygxma5
Populate the .gitignore file.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/_simple_set_pyx.pyx
16
16
 
17
17
"""Definition of a class that is similar to Set with some small changes."""
18
18
 
19
 
cdef extern from "python-compat.h":
20
 
    pass
21
 
 
22
 
cdef extern from "Python.h":
23
 
    ctypedef unsigned long size_t
24
 
    ctypedef long (*hashfunc)(PyObject*) except -1
25
 
    ctypedef object (*richcmpfunc)(PyObject *, PyObject *, int)
26
 
    ctypedef int (*visitproc)(PyObject *, void *)
27
 
    ctypedef int (*traverseproc)(PyObject *, visitproc, void *)
28
 
    int Py_EQ
29
 
    void Py_INCREF(PyObject *)
30
 
    void Py_DECREF(PyObject *)
31
 
    ctypedef struct PyTypeObject:
32
 
        hashfunc tp_hash
33
 
        richcmpfunc tp_richcompare
34
 
        traverseproc tp_traverse
35
 
 
36
 
    PyTypeObject *Py_TYPE(PyObject *)
37
 
    # Note: *Don't* use hash(), Pyrex 0.9.8.5 thinks it returns an 'int', and
38
 
    #       thus silently truncates to 32-bits on 64-bit machines.
39
 
    long PyObject_Hash(PyObject *) except -1
40
 
        
41
 
    void *PyMem_Malloc(size_t nbytes)
42
 
    void PyMem_Free(void *)
43
 
    void memset(void *, int, size_t)
 
19
from __future__ import absolute_import
 
20
 
 
21
from cpython.object cimport (
 
22
    hashfunc,
 
23
    Py_EQ,
 
24
    PyObject_Hash,
 
25
    PyTypeObject,
 
26
    Py_TYPE,
 
27
    richcmpfunc,
 
28
    traverseproc,
 
29
    visitproc,
 
30
    )
 
31
from cpython.mem cimport (
 
32
    PyMem_Malloc,
 
33
    PyMem_Free,
 
34
    )
 
35
from cpython.ref cimport (
 
36
    Py_INCREF,
 
37
    Py_DECREF,
 
38
    )
 
39
from libc.string cimport memset
44
40
 
45
41
 
46
42
# Dummy is an object used to mark nodes that have been deleted. Since
59
55
_NotImplemented = NotImplemented
60
56
 
61
57
 
62
 
cdef int _is_equal(PyObject *this, long this_hash, PyObject *other) except -1:
 
58
cdef int _is_equal(object this, long this_hash, object other) except -1:
63
59
    cdef long other_hash
64
60
 
65
 
    if this == other:
66
 
        return 1
67
61
    other_hash = PyObject_Hash(other)
68
62
    if other_hash != this_hash:
69
63
        return 0
115
109
            raise MemoryError()
116
110
        memset(self._table, 0, n_bytes)
117
111
 
 
112
    def __sizeof__(self):
 
113
        # Note: Pyrex doesn't allow sizeof(class) so we re-implement it here.
 
114
        # Bits are:
 
115
        #   1: PyObject
 
116
        #   2: vtable *
 
117
        #   3: 3 Py_ssize_t
 
118
        #   4: PyObject**
 
119
        # Note that we might get alignment, etc, wrong, but at least this is
 
120
        # better than no estimate at all
 
121
        # return sizeof(SimpleSet) + (self._mask + 1) * (sizeof(PyObject*))
 
122
        return (sizeof(PyObject) + sizeof(void*)
 
123
                + 3*sizeof(Py_ssize_t) + sizeof(PyObject**)
 
124
                + (self._mask + 1) * sizeof(PyObject*))
 
125
 
118
126
    def __dealloc__(self):
119
127
        if self._table != NULL:
120
128
            PyMem_Free(self._table)
188
196
        """
189
197
        cdef size_t i, n_lookup
190
198
        cdef long the_hash
191
 
        cdef PyObject **table, **slot
 
199
        cdef PyObject **table
 
200
        cdef PyObject **slot
192
201
        cdef Py_ssize_t mask
193
202
 
194
203
        mask = self._mask
195
204
        table = self._table
196
205
 
197
 
        the_hash = PyObject_Hash(key)
 
206
        the_hash = PyObject_Hash(<object>key)
198
207
        i = the_hash
199
208
        for n_lookup from 0 <= n_lookup <= <size_t>mask: # Don't loop forever
200
209
            slot = &table[i & mask]
220
229
        :return: The new size of the internal table
221
230
        """
222
231
        cdef Py_ssize_t new_size, n_bytes, remaining
223
 
        cdef PyObject **new_table, **old_table, **slot
 
232
        cdef PyObject **new_table
 
233
        cdef PyObject **old_table
 
234
        cdef PyObject **slot
224
235
 
225
236
        new_size = DEFAULT_SIZE
226
237
        while new_size <= min_used and new_size > 0:
253
264
        slot = old_table
254
265
        while remaining > 0:
255
266
            if slot[0] == NULL: # unused slot
256
 
                pass 
 
267
                pass
257
268
            elif slot[0] == _dummy: # dummy slot
258
269
                remaining = remaining - 1
259
270
            else: # active slot
263
274
        PyMem_Free(old_table)
264
275
        return new_size
265
276
 
266
 
    def add(self, key):
 
277
    cpdef object add(self, key):
267
278
        """Similar to set.add(), start tracking this key.
268
 
        
 
279
 
269
280
        There is one small difference, which is that we return the object that
270
281
        is stored at the given location. (which is closer to the
271
282
        dict.setdefault() functionality.)
272
283
        """
273
 
        return self._add(key)
274
 
 
275
 
    cdef object _add(self, key):
276
 
        cdef PyObject **slot, *py_key
277
 
        cdef int added
278
 
 
279
 
        py_key = <PyObject *>key
280
 
        if (Py_TYPE(py_key).tp_richcompare == NULL
281
 
            or Py_TYPE(py_key).tp_hash == NULL):
 
284
        cdef PyObject **slot
 
285
        cdef bint added
 
286
 
 
287
        if (Py_TYPE(key).tp_richcompare == NULL
 
288
            or Py_TYPE(key).tp_hash == NULL):
282
289
            raise TypeError('Types added to SimpleSet must implement'
283
290
                            ' both tp_richcompare and tp_hash')
284
291
        added = 0
286
293
        assert self._used < self._mask
287
294
        slot = _lookup(self, key)
288
295
        if (slot[0] == NULL):
289
 
            Py_INCREF(py_key)
 
296
            Py_INCREF(key)
290
297
            self._fill = self._fill + 1
291
298
            self._used = self._used + 1
292
 
            slot[0] = py_key
 
299
            slot[0] = <PyObject *>key
293
300
            added = 1
294
301
        elif (slot[0] == _dummy):
295
 
            Py_INCREF(py_key)
 
302
            Py_INCREF(key)
296
303
            self._used = self._used + 1
297
 
            slot[0] = py_key
 
304
            slot[0] = <PyObject *>key
298
305
            added = 1
299
306
        # No else: clause. If _lookup returns a pointer to
300
307
        # a live object, then we already have a value at this location.
308
315
        # so we can still return it
309
316
        return retval
310
317
 
311
 
    def discard(self, key):
 
318
    cpdef bint discard(self, key) except -1:
312
319
        """Remove key from the set, whether it exists or not.
313
320
 
314
321
        :return: False if the item did not exist, True if it did
315
322
        """
316
 
        if self._discard(key):
317
 
            return True
318
 
        return False
319
 
 
320
 
    cdef int _discard(self, key) except -1:
321
 
        cdef PyObject **slot, *py_key
 
323
        cdef PyObject **slot
322
324
 
323
325
        slot = _lookup(self, key)
324
326
        if slot[0] == NULL or slot[0] == _dummy:
325
327
            return 0
326
328
        self._used = self._used - 1
327
 
        Py_DECREF(slot[0])
 
329
        Py_DECREF(<object>slot[0])
328
330
        slot[0] = _dummy
329
331
        # PySet uses the heuristic: If more than 1/5 are dummies, then resize
330
332
        #                           them away
383
385
        if self.set is not None and self._used == self.set._used:
384
386
            return self.len
385
387
        return 0
386
 
    
387
388
 
388
389
 
389
390
cdef api SimpleSet SimpleSet_New():
445
446
    cdef size_t i, n_lookup
446
447
    cdef Py_ssize_t mask
447
448
    cdef long key_hash
448
 
    cdef PyObject **table, **slot, *cur, **free_slot, *py_key
 
449
    cdef PyObject **table
 
450
    cdef PyObject **slot
 
451
    cdef PyObject *cur
 
452
    cdef PyObject **free_slot
449
453
 
450
 
    py_key = <PyObject *>key
451
 
    # Note: avoid using hash(obj) because of a bug w/ pyrex 0.9.8.5 and 64-bit
452
 
    #       (it treats hash() as returning an 'int' rather than a 'long')
453
 
    key_hash = PyObject_Hash(py_key)
 
454
    key_hash = PyObject_Hash(key)
454
455
    i = <size_t>key_hash
455
456
    mask = self._mask
456
457
    table = self._table
465
466
                return free_slot
466
467
            else:
467
468
                return slot
468
 
        if cur == py_key:
 
469
        if cur == <PyObject *>key:
469
470
            # Found an exact pointer to the key
470
471
            return slot
471
472
        if cur == _dummy:
472
473
            if free_slot == NULL:
473
474
                free_slot = slot
474
 
        elif _is_equal(py_key, key_hash, cur):
 
475
        elif _is_equal(key, key_hash, <object>cur):
475
476
            # Both py_key and cur belong in this slot, return it
476
477
            return slot
477
478
        i = i + 1 + n_lookup
503
504
        This may be the same object, or it may be an equivalent object.
504
505
        (consider dict.setdefault(key, key))
505
506
    """
506
 
    return _check_self(self)._add(key)
507
 
    
 
507
    return _check_self(self).add(key)
 
508
 
508
509
 
509
510
cdef api int SimpleSet_Contains(object self, object key) except -1:
510
511
    """Is key present in self?"""
519
520
    :return: 1 if there was an object present, 0 if there was not, and -1 on
520
521
        error.
521
522
    """
522
 
    return _check_self(self)._discard(key)
 
523
    return _check_self(self).discard(key)
523
524
 
524
525
 
525
526
cdef api PyObject *SimpleSet_Get(SimpleSet self, object key) except? NULL: