/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 bzrlib/_simple_set_pyx.pyx

  • Committer: Marius Kruger
  • Date: 2010-07-10 21:28:56 UTC
  • mto: (5384.1.1 integration)
  • mto: This revision was merged to the branch mainline in revision 5385.
  • Revision ID: marius.kruger@enerweb.co.za-20100710212856-uq4ji3go0u5se7hx
* Update documentation
* add NEWS

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_simple_set_pyx.pyx
16
16
 
17
17
"""Definition of a class that is similar to Set with some small changes."""
18
18
 
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
 
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)
40
44
 
41
45
 
42
46
# Dummy is an object used to mark nodes that have been deleted. Since
55
59
_NotImplemented = NotImplemented
56
60
 
57
61
 
58
 
cdef int _is_equal(object this, long this_hash, object other) except -1:
 
62
cdef int _is_equal(PyObject *this, long this_hash, PyObject *other) except -1:
59
63
    cdef long other_hash
60
64
 
 
65
    if this == other:
 
66
        return 1
61
67
    other_hash = PyObject_Hash(other)
62
68
    if other_hash != this_hash:
63
69
        return 0
109
115
            raise MemoryError()
110
116
        memset(self._table, 0, n_bytes)
111
117
 
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
 
 
126
118
    def __dealloc__(self):
127
119
        if self._table != NULL:
128
120
            PyMem_Free(self._table)
196
188
        """
197
189
        cdef size_t i, n_lookup
198
190
        cdef long the_hash
199
 
        cdef PyObject **table
200
 
        cdef PyObject **slot
 
191
        cdef PyObject **table, **slot
201
192
        cdef Py_ssize_t mask
202
193
 
203
194
        mask = self._mask
204
195
        table = self._table
205
196
 
206
 
        the_hash = PyObject_Hash(<object>key)
 
197
        the_hash = PyObject_Hash(key)
207
198
        i = the_hash
208
199
        for n_lookup from 0 <= n_lookup <= <size_t>mask: # Don't loop forever
209
200
            slot = &table[i & mask]
229
220
        :return: The new size of the internal table
230
221
        """
231
222
        cdef Py_ssize_t new_size, n_bytes, remaining
232
 
        cdef PyObject **new_table
233
 
        cdef PyObject **old_table
234
 
        cdef PyObject **slot
 
223
        cdef PyObject **new_table, **old_table, **slot
235
224
 
236
225
        new_size = DEFAULT_SIZE
237
226
        while new_size <= min_used and new_size > 0:
264
253
        slot = old_table
265
254
        while remaining > 0:
266
255
            if slot[0] == NULL: # unused slot
267
 
                pass
 
256
                pass 
268
257
            elif slot[0] == _dummy: # dummy slot
269
258
                remaining = remaining - 1
270
259
            else: # active slot
274
263
        PyMem_Free(old_table)
275
264
        return new_size
276
265
 
277
 
    cpdef object add(self, key):
 
266
    def add(self, key):
278
267
        """Similar to set.add(), start tracking this key.
279
 
 
 
268
        
280
269
        There is one small difference, which is that we return the object that
281
270
        is stored at the given location. (which is closer to the
282
271
        dict.setdefault() functionality.)
283
272
        """
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):
 
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):
289
282
            raise TypeError('Types added to SimpleSet must implement'
290
283
                            ' both tp_richcompare and tp_hash')
291
284
        added = 0
293
286
        assert self._used < self._mask
294
287
        slot = _lookup(self, key)
295
288
        if (slot[0] == NULL):
296
 
            Py_INCREF(key)
 
289
            Py_INCREF(py_key)
297
290
            self._fill = self._fill + 1
298
291
            self._used = self._used + 1
299
 
            slot[0] = <PyObject *>key
 
292
            slot[0] = py_key
300
293
            added = 1
301
294
        elif (slot[0] == _dummy):
302
 
            Py_INCREF(key)
 
295
            Py_INCREF(py_key)
303
296
            self._used = self._used + 1
304
 
            slot[0] = <PyObject *>key
 
297
            slot[0] = py_key
305
298
            added = 1
306
299
        # No else: clause. If _lookup returns a pointer to
307
300
        # a live object, then we already have a value at this location.
315
308
        # so we can still return it
316
309
        return retval
317
310
 
318
 
    cpdef bint discard(self, key) except -1:
 
311
    def discard(self, key):
319
312
        """Remove key from the set, whether it exists or not.
320
313
 
321
314
        :return: False if the item did not exist, True if it did
322
315
        """
323
 
        cdef PyObject **slot
 
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
324
322
 
325
323
        slot = _lookup(self, key)
326
324
        if slot[0] == NULL or slot[0] == _dummy:
327
325
            return 0
328
326
        self._used = self._used - 1
329
 
        Py_DECREF(<object>slot[0])
 
327
        Py_DECREF(slot[0])
330
328
        slot[0] = _dummy
331
329
        # PySet uses the heuristic: If more than 1/5 are dummies, then resize
332
330
        #                           them away
385
383
        if self.set is not None and self._used == self.set._used:
386
384
            return self.len
387
385
        return 0
 
386
    
388
387
 
389
388
 
390
389
cdef api SimpleSet SimpleSet_New():
446
445
    cdef size_t i, n_lookup
447
446
    cdef Py_ssize_t mask
448
447
    cdef long key_hash
449
 
    cdef PyObject **table
450
 
    cdef PyObject **slot
451
 
    cdef PyObject *cur
452
 
    cdef PyObject **free_slot
 
448
    cdef PyObject **table, **slot, *cur, **free_slot, *py_key
453
449
 
454
 
    key_hash = PyObject_Hash(key)
 
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)
455
454
    i = <size_t>key_hash
456
455
    mask = self._mask
457
456
    table = self._table
466
465
                return free_slot
467
466
            else:
468
467
                return slot
469
 
        if cur == <PyObject *>key:
 
468
        if cur == py_key:
470
469
            # Found an exact pointer to the key
471
470
            return slot
472
471
        if cur == _dummy:
473
472
            if free_slot == NULL:
474
473
                free_slot = slot
475
 
        elif _is_equal(key, key_hash, <object>cur):
 
474
        elif _is_equal(py_key, key_hash, cur):
476
475
            # Both py_key and cur belong in this slot, return it
477
476
            return slot
478
477
        i = i + 1 + n_lookup
504
503
        This may be the same object, or it may be an equivalent object.
505
504
        (consider dict.setdefault(key, key))
506
505
    """
507
 
    return _check_self(self).add(key)
508
 
 
 
506
    return _check_self(self)._add(key)
 
507
    
509
508
 
510
509
cdef api int SimpleSet_Contains(object self, object key) except -1:
511
510
    """Is key present in self?"""
520
519
    :return: 1 if there was an object present, 0 if there was not, and -1 on
521
520
        error.
522
521
    """
523
 
    return _check_self(self).discard(key)
 
522
    return _check_self(self)._discard(key)
524
523
 
525
524
 
526
525
cdef api PyObject *SimpleSet_Get(SimpleSet self, object key) except? NULL: