19
19
from __future__ import absolute_import
21
cdef extern from "python-compat.h":
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 *)
31
void Py_INCREF(PyObject *)
32
void Py_DECREF(PyObject *)
33
ctypedef struct PyTypeObject:
35
richcmpfunc tp_richcompare
36
traverseproc tp_traverse
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
43
void *PyMem_Malloc(size_t nbytes)
44
void PyMem_Free(void *)
45
void memset(void *, int, size_t)
21
from cpython.object cimport (
31
from cpython.mem cimport (
35
from cpython.ref cimport (
39
from libc.string cimport memset
48
42
# Dummy is an object used to mark nodes that have been deleted. Since
61
55
_NotImplemented = NotImplemented
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
69
61
other_hash = PyObject_Hash(other)
70
62
if other_hash != this_hash:
205
197
cdef size_t i, n_lookup
206
198
cdef long the_hash
207
cdef PyObject **table, **slot
199
cdef PyObject **table
208
201
cdef Py_ssize_t mask
210
203
mask = self._mask
211
204
table = self._table
213
the_hash = PyObject_Hash(key)
206
the_hash = PyObject_Hash(<object>key)
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
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
241
236
new_size = DEFAULT_SIZE
242
237
while new_size <= min_used and new_size > 0:
279
274
PyMem_Free(old_table)
277
cpdef object add(self, key):
283
278
"""Similar to set.add(), start tracking this key.
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.)
289
return self._add(key)
291
cdef object _add(self, key):
292
cdef PyObject **slot, *py_key
295
py_key = <PyObject *>key
296
if (Py_TYPE(py_key).tp_richcompare == NULL
297
or Py_TYPE(py_key).tp_hash == NULL):
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')
302
293
assert self._used < self._mask
303
294
slot = _lookup(self, key)
304
295
if (slot[0] == NULL):
306
297
self._fill = self._fill + 1
307
298
self._used = self._used + 1
299
slot[0] = <PyObject *>key
310
301
elif (slot[0] == _dummy):
312
303
self._used = self._used + 1
304
slot[0] = <PyObject *>key
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
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.
330
321
:return: False if the item did not exist, True if it did
332
if self._discard(key):
336
cdef int _discard(self, key) except -1:
337
cdef PyObject **slot, *py_key
339
325
slot = _lookup(self, key)
340
326
if slot[0] == NULL or slot[0] == _dummy:
342
328
self._used = self._used - 1
329
Py_DECREF(<object>slot[0])
345
331
# PySet uses the heuristic: If more than 1/5 are dummies, then resize
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
452
cdef PyObject **free_slot
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
469
if cur == <PyObject *>key:
485
470
# Found an exact pointer to the key
487
472
if cur == _dummy:
488
473
if free_slot == NULL:
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
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))
522
return _check_self(self)._add(key)
507
return _check_self(self).add(key)
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
538
return _check_self(self)._discard(key)
523
return _check_self(self).discard(key)
541
526
cdef api PyObject *SimpleSet_Get(SimpleSet self, object key) except? NULL:
added
removed
breezy/_simple_set_pyx.pyx
