← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_static_tuple_interned_pyx.pyx

Start working on more of the C api for StaticTupleInterner.

It is really nice to have the except -1 clauses, as suddenly you don't have
to manually check the return values of all of your functions. \o/

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_static_tuple_interned_pyx.pyx
56
56
    if res == Py_True:
57
57
        Py_DECREF(res)
58
58
        return 1
 
59
    # Only handled for now because we are testing with stuff like tuples versus
 
60
    # StaticTuple objects. If we decide to limit StaticTupleInterner to
 
61
    # strictly only allowing StaticTuple objects, then this is no longer
 
62
    # required, and Py_NotImplemented => not equal
59
63
    if res == Py_NotImplemented:
60
64
        Py_DECREF(res)
61
65
        res = other.ob_type.tp_richcompare(other, this, Py_EQ)
66
70
    return 0
67
71
 
68
72
 
69
 
cdef class StaticTupleInterner:
 
73
cdef public api class StaticTupleInterner [object StaticTupleInternerObject,
 
74
                                           type StaticTupleInterner_type]:
70
75
    """This class tracks the canonical forms for StaticTuples.
71
76
 
72
77
    It is similar in function to the interned dictionary that is used by
111
116
    def __len__(self):
112
117
        return self.used
113
118
 
114
 
    cdef PyObject **_lookup(self, key, long hash) except NULL:
115
 
        """Find the slot where 'key' would fit.
116
 
 
117
 
        This is the same as a dicts 'lookup' function
118
 
 
119
 
        :param key: An object we are looking up
120
 
        :param hash: The hash for key
121
 
        :return: The location in self.table where key should be put
122
 
            should never be NULL, but may reference a NULL (PyObject*)
123
 
        """
124
 
        cdef size_t i, perturb
125
 
        cdef Py_ssize_t mask
126
 
        cdef long this_hash
127
 
        cdef PyObject **table, **cur, **free_slot, *py_key
128
 
 
129
 
        mask = self.mask
130
 
        table = self.table
131
 
        i = hash & mask
132
 
        cur = &table[i]
133
 
        py_key = <PyObject *>key
134
 
        if cur[0] == NULL:
135
 
            # Found a blank spot, or found the exact key
136
 
            return cur
137
 
        if cur[0] == py_key:
138
 
            return cur
139
 
        if cur[0] == _dummy:
140
 
            free_slot = cur
141
 
        else:
142
 
            if _is_equal(py_key, hash, cur[0]):
143
 
                # Both py_key and cur[0] belong in this slot, return it
144
 
                return cur
145
 
            free_slot = NULL
146
 
        # size_t is unsigned, hash is signed...
147
 
        perturb = hash
148
 
        while True:
149
 
            i = (i << 2) + i + perturb + 1
150
 
            cur = &table[i & mask]
151
 
            if cur[0] == NULL: # Found an empty spot
152
 
                if free_slot: # Did we find a _dummy earlier?
153
 
                    return free_slot
154
 
                else:
155
 
                    return cur
156
 
            if (cur[0] == py_key # exact match
157
 
                or _is_equal(py_key, hash, cur[0])): # Equivalent match
158
 
                return cur
159
 
            if (cur[0] == _dummy and free_slot == NULL):
160
 
                free_slot = cur
161
 
            perturb >>= PERTURB_SHIFT
162
 
        raise AssertionError('should never get here')
163
 
 
164
119
    def _test_lookup(self, key):
165
120
        cdef PyObject **slot
166
121
 
167
 
        slot = self._lookup(key, hash(key))
 
122
        slot = _StaticTupleInterner_Lookup(self, key, hash(key))
168
123
        if slot[0] == NULL:
169
124
            res = '<null>'
170
125
        elif slot[0] == _dummy:
176
131
    def __contains__(self, key):
177
132
        cdef PyObject **slot
178
133
 
179
 
        slot = self._lookup(key, hash(key))
 
134
        slot = _StaticTupleInterner_Lookup(self, key, hash(key))
180
135
        if slot[0] == NULL or slot[0] == _dummy:
181
136
            return False
182
137
        return True
183
138
 
184
139
    def __getitem__(self, key):
 
140
        """Return a stored item that is equivalent to key."""
185
141
        cdef PyObject **slot
186
 
        slot = self._lookup(key, hash(key))
 
142
        slot = _StaticTupleInterner_Lookup(self, key, hash(key))
187
143
        if slot[0] == NULL or slot[0] == _dummy:
188
144
            raise KeyError("Key %s is not present" % key)
189
145
        val = <object>(slot[0])
190
146
        return val
191
147
 
192
 
    def __setitem__(self, key, value):
193
 
        cdef PyObject **slot, *py_key
194
 
        assert key == value
195
 
 
196
 
        slot = self._lookup(key, hash(key))
197
 
        if (slot[0] == NULL or slot[0] == _dummy):
198
 
            py_key = <PyObject *>key
199
 
            Py_INCREF(py_key)
200
 
            slot[0] = py_key
 
148
    # def __setitem__(self, key, value):
 
149
    #     assert key == value
 
150
    #     self._add(key)
 
151
 
 
152
    def add(self, key):
 
153
        """Similar to set.add(), start tracking this key.
 
154
        
 
155
        There is one small difference, which is that we return the object that
 
156
        is stored at the given location. (which is closer to the
 
157
        dict.setdefault() functionality.)
 
158
        """
 
159
        return StaticTupleInterner_Add(self, key)
 
160
 
 
161
    def discard(self, key):
 
162
        """Remove key from the dict, whether it exists or not.
 
163
 
 
164
        :return: 0 if the item did not exist, 1 if it did
 
165
        """
 
166
        return StaticTupleInterner_Discard(self, key)
 
167
 
201
168
 
202
169
    def __delitem__(self, key):
203
 
        cdef PyObject **slot, *py_key
204
 
 
205
 
        slot = self._lookup(key, hash(key))
206
 
        if (slot[0] == NULL or slot[0] == _dummy):
207
 
            pass # Raise KeyError
208
 
            return
209
 
        # Found it
210
 
        # TODO: Check refcounts
211
 
        Py_DECREF(slot[0])
212
 
        slot[0] = _dummy
 
170
        """Remove the given item from the dict.
 
171
 
 
172
        Raise a KeyError if the key was not present.
 
173
        """
 
174
        cdef int exists
 
175
        exists = StaticTupleInterner_Discard(self, key)
 
176
        if not exists:
 
177
            raise KeyError('Key %s not present' % (key,))
 
178
 
 
179
 
 
180
cdef api inline PyObject **_StaticTupleInterner_Lookup(
 
181
            StaticTupleInterner self, key, long hash) except NULL:
 
182
    """Find the slot where 'key' would fit.
 
183
 
 
184
    This is the same as a dicts 'lookup' function.
 
185
 
 
186
    :param key: An object we are looking up
 
187
    :param hash: The hash for key
 
188
    :return: The location in self.table where key should be put
 
189
        should never be NULL, but may reference a NULL (PyObject*)
 
190
    """
 
191
    cdef size_t i, perturb
 
192
    cdef Py_ssize_t mask
 
193
    cdef long this_hash
 
194
    cdef PyObject **table, **cur, **free_slot, *py_key
 
195
 
 
196
    mask = self.mask
 
197
    table = self.table
 
198
    i = hash & mask
 
199
    cur = &table[i]
 
200
    py_key = <PyObject *>key
 
201
    if cur[0] == NULL:
 
202
        # Found a blank spot, or found the exact key
 
203
        return cur
 
204
    if cur[0] == py_key:
 
205
        return cur
 
206
    if cur[0] == _dummy:
 
207
        free_slot = cur
 
208
    else:
 
209
        if _is_equal(py_key, hash, cur[0]):
 
210
            # Both py_key and cur[0] belong in this slot, return it
 
211
            return cur
 
212
        free_slot = NULL
 
213
    # size_t is unsigned, hash is signed...
 
214
    perturb = hash
 
215
    while True:
 
216
        i = (i << 2) + i + perturb + 1
 
217
        cur = &table[i & mask]
 
218
        if cur[0] == NULL: # Found an empty spot
 
219
            if free_slot: # Did we find a _dummy earlier?
 
220
                return free_slot
 
221
            else:
 
222
                return cur
 
223
        if (cur[0] == py_key # exact match
 
224
            or _is_equal(py_key, hash, cur[0])): # Equivalent match
 
225
            return cur
 
226
        if (cur[0] == _dummy and free_slot == NULL):
 
227
            free_slot = cur
 
228
        perturb >>= PERTURB_SHIFT
 
229
    raise AssertionError('should never get here')
 
230
 
 
231
 
 
232
cdef api object StaticTupleInterner_Add(StaticTupleInterner self, object key):
 
233
    """Add a key to the StaticTupleInterner (set).
 
234
 
 
235
    :param self: The StaticTupleInterner to add the key to.
 
236
    :param key: The key to be added. If the key is already present,
 
237
        self will not be modified
 
238
    :return: The current key stored at the location defined by 'key'.
 
239
        This may be the same object, or it may be an equivalent object.
 
240
        (consider dict.setdefault(key, key))
 
241
    """
 
242
    cdef PyObject **slot, *py_key
 
243
 
 
244
    slot = _StaticTupleInterner_Lookup(self, key, hash(key))
 
245
    py_key = <PyObject *>key
 
246
    if (slot[0] == NULL):
 
247
        Py_INCREF(py_key)
 
248
        self.fill += 1
 
249
        self.used += 1
 
250
        slot[0] = py_key
 
251
    elif (slot[0] == _dummy):
 
252
        Py_INCREF(py_key)
 
253
        self.used += 1
 
254
        slot[0] = py_key
 
255
    # No else: clause. If _StaticTupleInterner_Lookup returns a pointer to
 
256
    # a live object, then we already have a value at this location.
 
257
    return <object>(slot[0])
 
258
 
 
259
 
 
260
cdef api int StaticTupleInterner_Discard(StaticTupleInterner self,
 
261
                                         object key) except -1:
 
262
    """Remove the object referenced at location 'key'.
 
263
 
 
264
    :param self: The StaticTupleInterner being modified
 
265
    :param key: The key we are checking on
 
266
    :return: 1 if there was an object present, 0 if there was not, and -1 on
 
267
        error.
 
268
    """
 
269
    cdef PyObject **slot, *py_key
 
270
 
 
271
    slot = _StaticTupleInterner_Lookup(self, key, hash(key))
 
272
    if slot[0] == NULL or slot[0] == _dummy:
 
273
        return 0
 
274
    self.used -= 1
 
275
    Py_DECREF(slot[0])
 
276
    slot[0] = _dummy
 
277
    return 1