/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-05-24 00:42:36 UTC
  • mto: This revision was merged to the branch mainline in revision 7505.
  • Revision ID: jelmer@jelmer.uk-20200524004236-jdj6obo4k5lznqw2
Cleanup Windows functions.

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