← Back to branch summary

~bzr/ubuntu/lucid/bzr/beta-ppa

« back to all changes in this revision

Viewing changes to bzrlib/_simple_set_pyx.pxd

  • Committer: Martin Pool
  • Date: 2010-07-02 07:29:40 UTC
  • mfrom: (129.1.7 packaging-karmic)
  • Revision ID: mbp@sourcefrog.net-20100702072940-hpzq5elg8wjve8rh
http://bugs.debian.org/452024
http://bugs.debian.org/464688
http://bugs.debian.org/523595
http://bugs.debian.org/526233
http://bugs.debian.org/537708
http://bugs.debian.org/555336
http://bugs.debian.org/555343
https://launchpad.net/bugs/249452
https://launchpad.net/bugs/385074
* PPA rebuild.
* PPA rebuild for Karmic.
* PPA rebuild for Jaunty.
* PPA rebuild for Hardy.
* From postinst, actually remove the example bash completion scripts.
  (LP: #249452)
* New upstream release.
* New upstream release.
* New upstream release.
* Revert change to Build-depends: Dapper does not have python-central.
  Should be python-support..
* Target ppa..
* Target ppa..
* Target ppa..
* Target ppa..
* New upstream release.
* Switch to dpkg-source 3.0 (quilt) format.
* Bump standards version to 3.8.4.
* Remove embedded copy of python-configobj. Closes: #555336
* Remove embedded copy of python-elementtree. Closes: #555343
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* debian/control: Fix obsolete-relation-form-in-source
  lintian warning. 
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Split out docs into bzr-doc package.
* New upstream release.
* Added John Francesco Ferlito to Uploaders.
* Fix install path to quick-reference guide
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to doc paths changing
* New upstream release.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to doc paths changing
* New upstream release.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to doc paths changing
* New upstream release.
* Fix FTBFS due to path changes, again, again.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to path changes.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Bump standards version to 3.8.3.
* Remove unused patch system.
* New upstream release.
* New upstream release.
* New upstream release.
* Fix copy and paste tab error in .install file
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
 + Fixes compatibility with Python 2.4. Closes: #537708
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream version.
* Bump standards version to 3.8.2.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Add python-pyrex to build-deps to ensure C extensions are always build.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Split documentation into bzr-doc package. ((LP: #385074)
* Multiple packaging changes to make us more linitan clean.
* New upstream release.
* Split documentation into bzr-doc package. ((LP: #385074)
* Multiple packaging changes to make us more linitan clean.
* New upstream release.
* Split documentation into bzr-doc package. ((LP: #385074)
* Multiple packaging changes to make us more linitan clean.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Fix API compatibility version. (Closes: #526233)
* New upstream release.
  + Fixes default format for upgrade command. (Closes: #464688)
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Add missing dependency on zlib development library. (Closes:
  #523595)
* Add zlib build-depends.
* Add zlib build-depends.
* Add zlib build-depends.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Move to section vcs.
* Bump standards version to 3.8.1.
* New upstream release.
* Remove temporary patch for missing .c files from distribution
* New upstream release.
* Remove temporary patch for missing .c files from distribution
* New upstream release.
* Remove temporary patch for missing .c files from distribution
* Add temporary patch for missing .c files from distribution
* Add temporary patch for missing .c files from distribution
* Add temporary patch for missing .c files from distribution
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Recommend ca-certificates. (Closes: #452024)
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Update watch file. bazaar now uses launchpad to host its sources.
* Remove patch for inventory root revision copy, applied upstream.
* New upstream release.
* New upstream release.
* New upstream release
* Force removal of files installed in error to /etc/bash_completion.d/
  (LP: #249452)
* New upstream release.
* New upstream release
* New upstream release.
* Bump standards version.
* Include patch for inventory root revision copy, required for bzr-svn.
* New upstream release.
* Remove unused lintian overrides.
* Correct the package version not to be native.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Final 1.5 release.
* New upstream release.
* New upstream release.
* New upstream release.
* Add myself as a co-maintainer.
* Add a Dm-Upload-Allowed: yes header.
* New upstream bugfix release.
* New upstream release.
* Final 1.3 release.
* New upstream release.
* First release candidate of the upcoming 1.3 release.
* Rebuild to fix the problem caused by a build with a broken python-central.
* New upstream release.
* Rebuild for dapper PPA.
* Apply Lamont's patches to fix build-dependencies on dapper.
  (See: https://bugs.launchpad.net/bzr/+bug/189915)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_simple_set_pyx.pxd
 
1
# Copyright (C) 2009, 2010 Canonical Ltd
 
2
#
 
3
# This program is free software; you can redistribute it and/or modify
 
4
# it under the terms of the GNU General Public License as published by
 
5
# the Free Software Foundation; either version 2 of the License, or
 
6
# (at your option) any later version.
 
7
#
 
8
# This program is distributed in the hope that it will be useful,
 
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
# GNU General Public License for more details.
 
12
#
 
13
# You should have received a copy of the GNU General Public License
 
14
# along with this program; if not, write to the Free Software
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
16
 
 
17
"""Interface definition of a class like PySet but without caching the hash.
 
18
 
 
19
This is generally useful when you want to 'intern' objects, etc. Note that this
 
20
differs from Set in that we:
 
21
  1) Don't have all of the .intersection, .difference, etc functions
 
22
  2) Do return the object from the set via queries
 
23
     eg. SimpleSet.add(key) => saved_key and SimpleSet[key] => saved_key
 
24
"""
 
25
 
 
26
cdef extern from "Python.h":
 
27
    ctypedef struct PyObject:
 
28
        pass
 
29
 
 
30
 
 
31
cdef public api class SimpleSet [object SimpleSetObject, type SimpleSet_Type]:
 
32
    """A class similar to PySet, but with simpler implementation.
 
33
 
 
34
    The main advantage is that this class uses only 2N memory to store N
 
35
    objects rather than 4N memory. The main trade-off is that we do not cache
 
36
    the hash value of saved objects. As such, it is assumed that computing the
 
37
    hash will be cheap (such as strings or tuples of strings, etc.)
 
38
 
 
39
    This also differs in that you can get back the objects that are stored
 
40
    (like a dict), but we also don't implement the complete list of 'set'
 
41
    operations (difference, intersection, etc).
 
42
    """
 
43
    # Data structure definition:
 
44
    #   This is a basic hash table using open addressing.
 
45
    #       http://en.wikipedia.org/wiki/Open_addressing
 
46
    #   Basically that means we keep an array of pointers to Python objects
 
47
    #   (called a table). Each location in the array is called a 'slot'.
 
48
    #
 
49
    #   An empty slot holds a NULL pointer, a slot where there was an item
 
50
    #   which was then deleted will hold a pointer to _dummy, and a filled slot
 
51
    #   points at the actual object which fills that slot.
 
52
    #
 
53
    #   The table is always a power of two, and the default location where an
 
54
    #   object is inserted is at hash(object) & (table_size - 1)
 
55
    #
 
56
    #   If there is a collision, then we search for another location. The
 
57
    #   specific algorithm is in _lookup. We search until we:
 
58
    #       find the object
 
59
    #       find an equivalent object (by tp_richcompare(obj1, obj2, Py_EQ))
 
60
    #       find a NULL slot
 
61
    #
 
62
    #   When an object is deleted, we set its slot to _dummy. this way we don't
 
63
    #   have to track whether there was a collision, and find the corresponding
 
64
    #   keys. (The collision resolution algorithm makes that nearly impossible
 
65
    #   anyway, because it depends on the upper bits of the hash.)
 
66
    #   The main effect of this, is that if we find _dummy, then we can insert
 
67
    #   an object there, but we have to keep searching until we find NULL to
 
68
    #   know that the object is not present elsewhere.
 
69
 
 
70
    cdef Py_ssize_t _used   # active
 
71
    cdef Py_ssize_t _fill   # active + dummy
 
72
    cdef Py_ssize_t _mask   # Table contains (mask+1) slots, a power of 2
 
73
    cdef PyObject **_table  # Pyrex/Cython doesn't support arrays to 'object'
 
74
                            # so we manage it manually
 
75
 
 
76
    cdef PyObject *_get(self, object key) except? NULL
 
77
    cdef object _add(self, key)
 
78
    cdef int _discard(self, key) except -1
 
79
    cdef int _insert_clean(self, PyObject *key) except -1
 
80
    cdef Py_ssize_t _resize(self, Py_ssize_t min_unused) except -1
 
81
 
 
82
 
 
83
# TODO: might want to export the C api here, though it is all available from
 
84
#       the class object...
 
85
cdef api SimpleSet SimpleSet_New()
 
86
cdef api object SimpleSet_Add(object self, object key)
 
87
cdef api int SimpleSet_Contains(object self, object key) except -1
 
88
cdef api int SimpleSet_Discard(object self, object key) except -1
 
89
cdef api PyObject *SimpleSet_Get(SimpleSet self, object key) except? NULL
 
90
cdef api Py_ssize_t SimpleSet_Size(object self) except -1
 
91
cdef api int SimpleSet_Next(object self, Py_ssize_t *pos, PyObject **key) except -1