/breezy/trunk

To get this branch, use:
bzr branch https://code.breezy-vcs.org/breezy/trunk

« back to all changes in this revision

Viewing changes to breezy/_simple_set_pyx.pyx

  • Committer: Jelmer Vernooij
  • Date: 2017-07-23 22:06:41 UTC
  • mfrom: (6738 trunk)
  • mto: This revision was merged to the branch mainline in revision 6739.
  • Revision ID: jelmer@jelmer.uk-20170723220641-69eczax9bmv8d6kk
Merge trunk, address review comments.

Show diffs side-by-side

added added

removed removed

Lines of Context:
18
18
 
19
19
from __future__ import absolute_import
20
20
 
21
 
cdef extern from "python-compat.h":
22
 
    pass
23
 
 
24
 
cdef extern from "Python.h":
25
 
    ctypedef unsigned long size_t
26
 
    ctypedef long (*hashfunc)(PyObject*) except -1
27
 
    ctypedef object (*richcmpfunc)(PyObject *, PyObject *, int)
28
 
    ctypedef int (*visitproc)(PyObject *, void *)
29
 
    ctypedef int (*traverseproc)(PyObject *, visitproc, void *)
30
 
    int Py_EQ
31
 
    void Py_INCREF(PyObject *)
32
 
    void Py_DECREF(PyObject *)
33
 
    ctypedef struct PyTypeObject:
34
 
        hashfunc tp_hash
35
 
        richcmpfunc tp_richcompare
36
 
        traverseproc tp_traverse
37
 
 
38
 
    PyTypeObject *Py_TYPE(PyObject *)
39
 
    # Note: *Don't* use hash(), Pyrex 0.9.8.5 thinks it returns an 'int', and
40
 
    #       thus silently truncates to 32-bits on 64-bit machines.
41
 
    long PyObject_Hash(PyObject *) except -1
42
 
        
43
 
    void *PyMem_Malloc(size_t nbytes)
44
 
    void PyMem_Free(void *)
45
 
    void memset(void *, int, size_t)
 
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
46
40
 
47
41
 
48
42
# Dummy is an object used to mark nodes that have been deleted. Since
61
55
_NotImplemented = NotImplemented
62
56
 
63
57
 
64
 
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:
65
59
    cdef long other_hash
66
60
 
67
 
    if this == other:
68
 
        return 1
69
61
    other_hash = PyObject_Hash(other)
70
62
    if other_hash != this_hash:
71
63
        return 0
204
196
        """
205
197
        cdef size_t i, n_lookup
206
198
        cdef long the_hash
207
 
        cdef PyObject **table, **slot
 
199
        cdef PyObject **table
 
200
        cdef PyObject **slot
208
201
        cdef Py_ssize_t mask
209
202
 
210
203
        mask = self._mask
211
204
        table = self._table
212
205
 
213
 
        the_hash = PyObject_Hash(key)
 
206
        the_hash = PyObject_Hash(<object>key)
214
207
        i = the_hash
215
208
        for n_lookup from 0 <= n_lookup <= <size_t>mask: # Don't loop forever
216
209
            slot = &table[i & mask]
236
229
        :return: The new size of the internal table
237
230
        """
238
231
        cdef Py_ssize_t new_size, n_bytes, remaining
239
 
        cdef PyObject **new_table, **old_table, **slot
 
232
        cdef PyObject **new_table
 
233
        cdef PyObject **old_table
 
234
        cdef PyObject **slot
240
235
 
241
236
        new_size = DEFAULT_SIZE
242
237
        while new_size <= min_used and new_size > 0:
269
264
        slot = old_table
270
265
        while remaining > 0:
271
266
            if slot[0] == NULL: # unused slot
272
 
                pass 
 
267
                pass
273
268
            elif slot[0] == _dummy: # dummy slot
274
269
                remaining = remaining - 1
275
270
            else: # active slot
279
274
        PyMem_Free(old_table)
280
275
        return new_size
281
276
 
282
 
    def add(self, key):
 
277
    cpdef object add(self, key):
283
278
        """Similar to set.add(), start tracking this key.
284
 
        
 
279
 
285
280
        There is one small difference, which is that we return the object that
286
281
        is stored at the given location. (which is closer to the
287
282
        dict.setdefault() functionality.)
288
283
        """
289
 
        return self._add(key)
290
 
 
291
 
    cdef object _add(self, key):
292
 
        cdef PyObject **slot, *py_key
293
 
        cdef int added
294
 
 
295
 
        py_key = <PyObject *>key
296
 
        if (Py_TYPE(py_key).tp_richcompare == NULL
297
 
            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):
298
289
            raise TypeError('Types added to SimpleSet must implement'
299
290
                            ' both tp_richcompare and tp_hash')
300
291
        added = 0
302
293
        assert self._used < self._mask
303
294
        slot = _lookup(self, key)
304
295
        if (slot[0] == NULL):
305
 
            Py_INCREF(py_key)
 
296
            Py_INCREF(key)
306
297
            self._fill = self._fill + 1
307
298
            self._used = self._used + 1
308
 
            slot[0] = py_key
 
299
            slot[0] = <PyObject *>key
309
300
            added = 1
310
301
        elif (slot[0] == _dummy):
311
 
            Py_INCREF(py_key)
 
302
            Py_INCREF(key)
312
303
            self._used = self._used + 1
313
 
            slot[0] = py_key
 
304
            slot[0] = <PyObject *>key
314
305
            added = 1
315
306
        # No else: clause. If _lookup returns a pointer to
316
307
        # a live object, then we already have a value at this location.
324
315
        # so we can still return it
325
316
        return retval
326
317
 
327
 
    def discard(self, key):
 
318
    cpdef bint discard(self, key) except -1:
328
319
        """Remove key from the set, whether it exists or not.
329
320
 
330
321
        :return: False if the item did not exist, True if it did
331
322
        """
332
 
        if self._discard(key):
333
 
            return True
334
 
        return False
335
 
 
336
 
    cdef int _discard(self, key) except -1:
337
 
        cdef PyObject **slot, *py_key
 
323
        cdef PyObject **slot
338
324
 
339
325
        slot = _lookup(self, key)
340
326
        if slot[0] == NULL or slot[0] == _dummy:
341
327
            return 0
342
328
        self._used = self._used - 1
343
 
        Py_DECREF(slot[0])
 
329
        Py_DECREF(<object>slot[0])
344
330
        slot[0] = _dummy
345
331
        # PySet uses the heuristic: If more than 1/5 are dummies, then resize
346
332
        #                           them away
399
385
        if self.set is not None and self._used == self.set._used:
400
386
            return self.len
401
387
        return 0
402
 
    
403
388
 
404
389
 
405
390
cdef api SimpleSet SimpleSet_New():
461
446
    cdef size_t i, n_lookup
462
447
    cdef Py_ssize_t mask
463
448
    cdef long key_hash
464
 
    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
465
453
 
466
 
    py_key = <PyObject *>key
467
 
    # Note: avoid using hash(obj) because of a bug w/ pyrex 0.9.8.5 and 64-bit
468
 
    #       (it treats hash() as returning an 'int' rather than a 'long')
469
 
    key_hash = PyObject_Hash(py_key)
 
454
    key_hash = PyObject_Hash(key)
470
455
    i = <size_t>key_hash
471
456
    mask = self._mask
472
457
    table = self._table
481
466
                return free_slot
482
467
            else:
483
468
                return slot
484
 
        if cur == py_key:
 
469
        if cur == <PyObject *>key:
485
470
            # Found an exact pointer to the key
486
471
            return slot
487
472
        if cur == _dummy:
488
473
            if free_slot == NULL:
489
474
                free_slot = slot
490
 
        elif _is_equal(py_key, key_hash, cur):
 
475
        elif _is_equal(key, key_hash, <object>cur):
491
476
            # Both py_key and cur belong in this slot, return it
492
477
            return slot
493
478
        i = i + 1 + n_lookup
519
504
        This may be the same object, or it may be an equivalent object.
520
505
        (consider dict.setdefault(key, key))
521
506
    """
522
 
    return _check_self(self)._add(key)
523
 
    
 
507
    return _check_self(self).add(key)
 
508
 
524
509
 
525
510
cdef api int SimpleSet_Contains(object self, object key) except -1:
526
511
    """Is key present in self?"""
535
520
    :return: 1 if there was an object present, 0 if there was not, and -1 on
536
521
        error.
537
522
    """
538
 
    return _check_self(self)._discard(key)
 
523
    return _check_self(self).discard(key)
539
524
 
540
525
 
541
526
cdef api PyObject *SimpleSet_Get(SimpleSet self, object key) except? NULL: