~bzr-pqm/bzr/bzr.dev

4763.2.4 by John Arbash Meinel
merge bzr.2.1 in preparation for NEWS entry.
1
/* Copyright (C) 2009, 2010 Canonical Ltd
4679.3.1 by John Arbash Meinel
Start working on a Keys type.
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
4679.3.5 by John Arbash Meinel
Have a pure-python implementation that works as tuples of tuples of strings,
16
 */
4679.3.1 by John Arbash Meinel
Start working on a Keys type.
17
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
18
/* Must be defined before importing _static_tuple_c.h so that we get the right
19
 * linkage.
20
 */
21
#define STATIC_TUPLE_MODULE
22
4736.1.1 by John Arbash Meinel
Py_ssize_t and its associated function typedefs are not available w/ python 2.4
23
#include <Python.h>
24
#include "python-compat.h"
25
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
26
#include "_static_tuple_c.h"
27
#include "_export_c_api.h"
4679.5.11 by John Arbash Meinel
add a hack-around to handle differences between pyrex 0.9.6 and 0.9.8
28
29
/* Pyrex 0.9.6.4 exports _simple_set_pyx_api as
30
 * import__simple_set_pyx(), while Pyrex 0.9.8.5 and Cython 0.11.3 export them
31
 * as import_bzrlib___simple_set_pyx(). As such, we just #define one to be
32
 * equivalent to the other in our internal code.
33
 */
34
#define import__simple_set_pyx import_bzrlib___simple_set_pyx
4679.3.76 by John Arbash Meinel
Rename StaticTupleInterner => SimpleSet.
35
#include "_simple_set_pyx_api.h"
4679.3.1 by John Arbash Meinel
Start working on a Keys type.
36
37
#if defined(__GNUC__)
38
#   define inline __inline__
39
#elif defined(_MSC_VER)
40
#   define inline __inline
41
#else
42
#   define inline
43
#endif
44
45
4679.3.44 by John Arbash Meinel
Special case the empty tuple as a singleton.
46
/* The one and only StaticTuple with no values */
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
47
static StaticTuple *_empty_tuple = NULL;
4679.3.51 by John Arbash Meinel
Add a _static_tuple_c.pxd file to define the C api to pyrex code.
48
static PyObject *_interned_tuples = NULL;
4679.3.29 by John Arbash Meinel
Start work on implementing a Key.intern() function.
49
50
4679.3.33 by John Arbash Meinel
Change Key away from being a PyVarObject.
51
static inline int
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
52
_StaticTuple_is_interned(StaticTuple *self)
4679.3.35 by John Arbash Meinel
Work on making intern() not generate immortal Key objects.
53
{
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
54
    return self->flags & STATIC_TUPLE_INTERNED_FLAG;
4679.3.35 by John Arbash Meinel
Work on making intern() not generate immortal Key objects.
55
}
56
4679.3.1 by John Arbash Meinel
Start working on a Keys type.
57
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
58
59
static PyObject *
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
60
StaticTuple_as_tuple(StaticTuple *self)
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
61
{
62
    PyObject *tpl = NULL, *obj = NULL;
4679.3.33 by John Arbash Meinel
Change Key away from being a PyVarObject.
63
    int i, len;
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
64
4679.3.37 by John Arbash Meinel
Change the Key header a bit. It is simpler if you use unsigned char
65
    len = self->size;
4679.3.33 by John Arbash Meinel
Change Key away from being a PyVarObject.
66
    tpl = PyTuple_New(len);
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
67
    if (!tpl) {
68
        /* Malloc failure */
69
        return NULL;
70
    }
4679.3.33 by John Arbash Meinel
Change Key away from being a PyVarObject.
71
    for (i = 0; i < len; ++i) {
4679.3.51 by John Arbash Meinel
Add a _static_tuple_c.pxd file to define the C api to pyrex code.
72
        obj = (PyObject *)self->items[i];
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
73
        Py_INCREF(obj);
74
        PyTuple_SET_ITEM(tpl, i, obj);
75
    }
76
    return tpl;
77
}
78
4679.3.29 by John Arbash Meinel
Start work on implementing a Key.intern() function.
79
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
80
static char StaticTuple_as_tuple_doc[] = "as_tuple() => tuple";
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
81
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
82
static StaticTuple *
83
StaticTuple_Intern(StaticTuple *self)
4679.3.29 by John Arbash Meinel
Start work on implementing a Key.intern() function.
84
{
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
85
    PyObject *canonical_tuple = NULL;
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
86
4679.3.81 by John Arbash Meinel
Fix up _simple_set_pyx.pyx to be compatible with pyrex again.
87
    if (_interned_tuples == NULL || _StaticTuple_is_interned(self)) {
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
88
        Py_INCREF(self);
89
        return self;
90
    }
4679.3.76 by John Arbash Meinel
Rename StaticTupleInterner => SimpleSet.
91
    /* SimpleSet_Add returns whatever object is present at self
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
92
     * or the new object if it needs to add it.
93
     */
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
94
    canonical_tuple = SimpleSet_Add(_interned_tuples, (PyObject *)self);
95
    if (!canonical_tuple) {
96
        // Some sort of exception, propogate it.
97
        return NULL;
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
98
    }
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
99
    if (canonical_tuple != (PyObject *)self) {
100
        // There was already a tuple with that value
101
        return (StaticTuple *)canonical_tuple;
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
102
    }
103
    self->flags |= STATIC_TUPLE_INTERNED_FLAG;
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
104
    // The two references in the dict do not count, so that the StaticTuple
105
    // object does not become immortal just because it was interned.
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
106
    Py_REFCNT(self) -= 1;
107
    return self;
4679.3.29 by John Arbash Meinel
Start work on implementing a Key.intern() function.
108
}
109
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
110
static char StaticTuple_Intern_doc[] = "intern() => unique StaticTuple\n"
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
111
    "Return a 'canonical' StaticTuple object.\n"
4679.3.29 by John Arbash Meinel
Start work on implementing a Key.intern() function.
112
    "Similar to intern() for strings, this makes sure there\n"
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
113
    "is only one StaticTuple object for a given value\n."
4679.3.29 by John Arbash Meinel
Start work on implementing a Key.intern() function.
114
    "Common usage is:\n"
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
115
    "  key = StaticTuple('foo', 'bar').intern()\n";
4679.3.29 by John Arbash Meinel
Start work on implementing a Key.intern() function.
116
117
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
118
static void
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
119
StaticTuple_dealloc(StaticTuple *self)
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
120
{
4679.3.33 by John Arbash Meinel
Change Key away from being a PyVarObject.
121
    int i, len;
4679.3.17 by John Arbash Meinel
Implement some of the sequence items.
122
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
123
    if (_StaticTuple_is_interned(self)) {
4679.3.81 by John Arbash Meinel
Fix up _simple_set_pyx.pyx to be compatible with pyrex again.
124
        /* revive dead object temporarily for Discard */
125
        Py_REFCNT(self) = 2;
4679.3.76 by John Arbash Meinel
Rename StaticTupleInterner => SimpleSet.
126
        if (SimpleSet_Discard(_interned_tuples, (PyObject*)self) != 1)
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
127
            Py_FatalError("deletion of interned StaticTuple failed");
4679.3.81 by John Arbash Meinel
Fix up _simple_set_pyx.pyx to be compatible with pyrex again.
128
        self->flags &= ~STATIC_TUPLE_INTERNED_FLAG;
4679.3.35 by John Arbash Meinel
Work on making intern() not generate immortal Key objects.
129
    }
4679.3.37 by John Arbash Meinel
Change the Key header a bit. It is simpler if you use unsigned char
130
    len = self->size;
4679.3.33 by John Arbash Meinel
Change Key away from being a PyVarObject.
131
    for (i = 0; i < len; ++i) {
4679.3.51 by John Arbash Meinel
Add a _static_tuple_c.pxd file to define the C api to pyrex code.
132
        Py_XDECREF(self->items[i]);
4679.3.17 by John Arbash Meinel
Implement some of the sequence items.
133
    }
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
134
    Py_TYPE(self)->tp_free((PyObject *)self);
135
}
136
137
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
138
/* Similar to PyTuple_New() */
139
static StaticTuple *
140
StaticTuple_New(Py_ssize_t size)
141
{
142
    StaticTuple *stuple;
143
4759.2.7 by John Arbash Meinel
Re-implement StaticTuple_add() inline, rather that thunking over to tuples.
144
    if (size < 0 || size > 255) {
145
        /* Too big or too small */
146
        PyErr_SetString(PyExc_ValueError, "StaticTuple(...)"
147
            " takes from 0 to 255 items");
148
        return NULL;
149
    }
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
150
    if (size == 0 && _empty_tuple != NULL) {
151
        Py_INCREF(_empty_tuple);
152
        return _empty_tuple;
153
    }
154
    /* Note that we use PyObject_NewVar because we want to allocate a variable
155
     * width entry. However we *aren't* truly a PyVarObject because we don't
156
     * use a long for ob_size. Instead we use a plain 'size' that is an int,
157
     * and will be overloaded with flags in the future.
158
     * As such we do the alloc, and then have to clean up anything it does
159
     * incorrectly.
160
     */
161
    stuple = PyObject_NewVar(StaticTuple, &StaticTuple_Type, size);
162
    if (stuple == NULL) {
163
        return NULL;
164
    }
165
    stuple->size = size;
166
    stuple->flags = 0;
167
    stuple->_unused0 = 0;
168
    stuple->_unused1 = 0;
169
    if (size > 0) {
170
        memset(stuple->items, 0, sizeof(PyObject *) * size);
171
    }
172
#if STATIC_TUPLE_HAS_HASH
173
    stuple->hash = -1;
174
#endif
175
    return stuple;
176
}
177
178
4739.4.1 by John Arbash Meinel
Implement StaticTuple.from_sequence()
179
static StaticTuple *
180
StaticTuple_FromSequence(PyObject *sequence)
181
{
4771.2.2 by John Arbash Meinel
Clean up the C code a bit, using a goto.
182
    StaticTuple *new = NULL;
4771.2.1 by Matt Nordhoff
_static_tuple_c.StaticTuple.from_sequence() now supports arbitrary iterables (by converting them to tuples first).
183
    PyObject *as_tuple = NULL;
4739.4.1 by John Arbash Meinel
Implement StaticTuple.from_sequence()
184
    PyObject *item;
185
    Py_ssize_t i, size;
186
187
    if (StaticTuple_CheckExact(sequence)) {
188
        Py_INCREF(sequence);
189
        return (StaticTuple *)sequence;
190
    }
191
    if (!PySequence_Check(sequence)) {
4771.2.1 by Matt Nordhoff
_static_tuple_c.StaticTuple.from_sequence() now supports arbitrary iterables (by converting them to tuples first).
192
        as_tuple = PySequence_Tuple(sequence);
4771.2.2 by John Arbash Meinel
Clean up the C code a bit, using a goto.
193
        if (as_tuple == NULL)
194
            goto done;
4771.2.1 by Matt Nordhoff
_static_tuple_c.StaticTuple.from_sequence() now supports arbitrary iterables (by converting them to tuples first).
195
        sequence = as_tuple;
4739.4.1 by John Arbash Meinel
Implement StaticTuple.from_sequence()
196
    }
197
    size = PySequence_Size(sequence);
4771.2.1 by Matt Nordhoff
_static_tuple_c.StaticTuple.from_sequence() now supports arbitrary iterables (by converting them to tuples first).
198
    if (size == -1) {
4771.2.2 by John Arbash Meinel
Clean up the C code a bit, using a goto.
199
        goto done;
4771.2.1 by Matt Nordhoff
_static_tuple_c.StaticTuple.from_sequence() now supports arbitrary iterables (by converting them to tuples first).
200
    }
4739.4.1 by John Arbash Meinel
Implement StaticTuple.from_sequence()
201
    new = StaticTuple_New(size);
202
    if (new == NULL) {
4771.2.2 by John Arbash Meinel
Clean up the C code a bit, using a goto.
203
        goto done;
4739.4.1 by John Arbash Meinel
Implement StaticTuple.from_sequence()
204
    }
205
    for (i = 0; i < size; ++i) {
206
        // This returns a new reference, which we then 'steal' with 
207
        // StaticTuple_SET_ITEM
208
        item = PySequence_GetItem(sequence, i);
209
        if (item == NULL) {
210
            Py_DECREF(new);
4771.2.2 by John Arbash Meinel
Clean up the C code a bit, using a goto.
211
            new = NULL;
212
            goto done;
4739.4.1 by John Arbash Meinel
Implement StaticTuple.from_sequence()
213
        }
214
        StaticTuple_SET_ITEM(new, i, item);
215
    }
4771.2.2 by John Arbash Meinel
Clean up the C code a bit, using a goto.
216
done:
4771.2.1 by Matt Nordhoff
_static_tuple_c.StaticTuple.from_sequence() now supports arbitrary iterables (by converting them to tuples first).
217
    Py_XDECREF(as_tuple);
4739.4.1 by John Arbash Meinel
Implement StaticTuple.from_sequence()
218
    return (StaticTuple *)new;
219
}
220
221
static StaticTuple *
222
StaticTuple_from_sequence(PyObject *self, PyObject *args, PyObject *kwargs)
223
{
224
    PyObject *sequence;
225
    if (!PyArg_ParseTuple(args, "O", &sequence))
226
        return NULL;
227
    return StaticTuple_FromSequence(sequence);
228
}
229
230
4759.2.6 by John Arbash Meinel
factor out the check of each internal item.
231
/* Check that all items we point to are 'valid' */
232
static int
233
StaticTuple_check_items(StaticTuple *self)
234
{
235
    int i;
236
    PyObject *obj;
237
238
    for (i = 0; i < self->size; ++i) {
239
        obj = self->items[i];
240
        if (obj == NULL) {
241
            PyErr_SetString(PyExc_RuntimeError, "StaticTuple(...)"
242
                " should not have a NULL entry.");
243
            return 0;
244
        }
4759.2.9 by John Arbash Meinel
Implement support for lots of types.
245
        if (PyString_CheckExact(obj)
246
            || StaticTuple_CheckExact(obj)
247
            || obj == Py_None
248
            || PyBool_Check(obj)
4759.2.11 by John Arbash Meinel
Review feedback from Andrew.
249
            || PyInt_CheckExact(obj)
250
            || PyLong_CheckExact(obj)
251
            || PyFloat_CheckExact(obj)
252
            || PyUnicode_CheckExact(obj)
4759.2.9 by John Arbash Meinel
Implement support for lots of types.
253
            ) continue;
254
        PyErr_Format(PyExc_TypeError, "StaticTuple(...)"
255
            " requires that all items are one of"
256
            " str, StaticTuple, None, bool, int, long, float, or unicode"
257
            " not %s.", Py_TYPE(obj)->tp_name);
258
        return 0;
4759.2.6 by John Arbash Meinel
factor out the check of each internal item.
259
    }
260
    return 1;
261
}
262
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
263
static PyObject *
4679.5.9 by John Arbash Meinel
NEWS entry for StaticTuple class.
264
StaticTuple_new_constructor(PyTypeObject *type, PyObject *args, PyObject *kwds)
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
265
{
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
266
    StaticTuple *self;
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
267
    PyObject *obj = NULL;
268
    Py_ssize_t i, len = 0;
269
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
270
    if (type != &StaticTuple_Type) {
271
        PyErr_SetString(PyExc_TypeError, "we only support creating StaticTuple");
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
272
        return NULL;
273
    }
274
    if (!PyTuple_CheckExact(args)) {
275
        PyErr_SetString(PyExc_TypeError, "args must be a tuple");
276
        return NULL;
277
    }
278
    len = PyTuple_GET_SIZE(args);
4763.2.3 by Matt Nordhoff
Make StaticTuple_New always raise a ValueError, and StaticTuple_new_constructor always raise a TypeError.
279
    if (len < 0 || len > 255) {
280
        /* Check the length here so we can raise a TypeError instead of
281
         * StaticTuple_New's ValueError.
282
         */
283
        PyErr_SetString(PyExc_TypeError, "StaticTuple(...)"
284
            " takes from 0 to 255 items");
285
        return NULL;
286
    }
4679.3.44 by John Arbash Meinel
Special case the empty tuple as a singleton.
287
    self = (StaticTuple *)StaticTuple_New(len);
4679.3.19 by John Arbash Meinel
implement slicing as a tuple thunk.
288
    if (self == NULL) {
289
        return NULL;
290
    }
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
291
    for (i = 0; i < len; ++i) {
292
        obj = PyTuple_GET_ITEM(args, i);
293
        Py_INCREF(obj);
4679.3.51 by John Arbash Meinel
Add a _static_tuple_c.pxd file to define the C api to pyrex code.
294
        self->items[i] = obj;
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
295
    }
4759.2.6 by John Arbash Meinel
factor out the check of each internal item.
296
    if (!StaticTuple_check_items(self)) {
297
        type->tp_dealloc((PyObject *)self);
298
        return NULL;
299
    }
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
300
    return (PyObject *)self;
301
}
302
4679.3.18 by John Arbash Meinel
Copy the hash and richcompare implementations, and add some tests.
303
static PyObject *
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
304
StaticTuple_repr(StaticTuple *self)
4679.3.18 by John Arbash Meinel
Copy the hash and richcompare implementations, and add some tests.
305
{
4679.3.79 by John Arbash Meinel
Change the repr to print out 'StaticTuple'
306
    PyObject *as_tuple, *tuple_repr, *result;
4679.3.18 by John Arbash Meinel
Copy the hash and richcompare implementations, and add some tests.
307
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
308
    as_tuple = StaticTuple_as_tuple(self);
4679.3.18 by John Arbash Meinel
Copy the hash and richcompare implementations, and add some tests.
309
    if (as_tuple == NULL) {
310
        return NULL;
311
    }
4679.3.79 by John Arbash Meinel
Change the repr to print out 'StaticTuple'
312
    tuple_repr = PyObject_Repr(as_tuple);
4679.3.18 by John Arbash Meinel
Copy the hash and richcompare implementations, and add some tests.
313
    Py_DECREF(as_tuple);
4679.3.79 by John Arbash Meinel
Change the repr to print out 'StaticTuple'
314
    if (tuple_repr == NULL) {
315
        return NULL;
316
    }
4759.2.14 by Matt Nordhoff
Hardcode "StaticTuple" in repr instead of using tp_name, since that includes the module now.
317
    result = PyString_FromFormat("StaticTuple%s",
318
                                 PyString_AsString(tuple_repr));
4679.3.18 by John Arbash Meinel
Copy the hash and richcompare implementations, and add some tests.
319
    return result;
320
}
321
322
static long
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
323
StaticTuple_hash(StaticTuple *self)
4679.3.18 by John Arbash Meinel
Copy the hash and richcompare implementations, and add some tests.
324
{
4679.3.22 by John Arbash Meinel
It seems that optimizing Keys_hash is not the way to go for 'bzr log' performance.
325
    /* adapted from tuplehash(), is the specific hash value considered
326
     * 'stable'?
327
     */
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
328
    register long x, y;
329
    Py_ssize_t len = self->size;
330
    PyObject **p;
331
    long mult = 1000003L;
4679.3.18 by John Arbash Meinel
Copy the hash and richcompare implementations, and add some tests.
332
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
333
#if STATIC_TUPLE_HAS_HASH
4679.3.22 by John Arbash Meinel
It seems that optimizing Keys_hash is not the way to go for 'bzr log' performance.
334
    if (self->hash != -1) {
335
        return self->hash;
4679.3.18 by John Arbash Meinel
Copy the hash and richcompare implementations, and add some tests.
336
    }
4679.3.28 by John Arbash Meinel
Add a KEY_HAS_HASH define.
337
#endif
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
338
    x = 0x345678L;
339
    p = self->items;
4679.3.77 by John Arbash Meinel
Some code cleanup passes.
340
    // TODO: We could set specific flags if we know that, for example, all the
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
341
    //       items are strings. I haven't seen a real-world benefit to that
342
    //       yet, though.
4679.3.77 by John Arbash Meinel
Some code cleanup passes.
343
    while (--len >= 0) {
344
        y = PyObject_Hash(*p++);
345
        if (y == -1) /* failure */
346
            return -1;
347
        x = (x ^ y) * mult;
348
        /* the cast might truncate len; that doesn't change hash stability */
349
        mult += (long)(82520L + len + len);
4679.3.46 by John Arbash Meinel
Play around a bit with changing the hash function.
350
    }
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
351
    x += 97531L;
352
    if (x == -1)
353
        x = -2;
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
354
#if STATIC_TUPLE_HAS_HASH
4679.3.22 by John Arbash Meinel
It seems that optimizing Keys_hash is not the way to go for 'bzr log' performance.
355
    self->hash = x;
4679.3.28 by John Arbash Meinel
Add a KEY_HAS_HASH define.
356
#endif
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
357
    return x;
4679.3.18 by John Arbash Meinel
Copy the hash and richcompare implementations, and add some tests.
358
}
359
360
static PyObject *
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
361
StaticTuple_richcompare_to_tuple(StaticTuple *v, PyObject *wt, int op)
4679.3.18 by John Arbash Meinel
Copy the hash and richcompare implementations, and add some tests.
362
{
4679.3.23 by John Arbash Meinel
A bit more testing shows that we are comparing Key to tuples fairly often.
363
    PyObject *vt;
4679.3.19 by John Arbash Meinel
implement slicing as a tuple thunk.
364
    PyObject *result = NULL;
4679.3.18 by John Arbash Meinel
Copy the hash and richcompare implementations, and add some tests.
365
    
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
366
    vt = StaticTuple_as_tuple((StaticTuple *)v);
4679.3.23 by John Arbash Meinel
A bit more testing shows that we are comparing Key to tuples fairly often.
367
    if (vt == NULL) {
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
368
        goto done;
4679.3.18 by John Arbash Meinel
Copy the hash and richcompare implementations, and add some tests.
369
    }
4679.3.23 by John Arbash Meinel
A bit more testing shows that we are comparing Key to tuples fairly often.
370
    if (!PyTuple_Check(wt)) {
371
        PyErr_BadInternalCall();
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
372
        goto done;
4679.3.18 by John Arbash Meinel
Copy the hash and richcompare implementations, and add some tests.
373
    }
374
    /* Now we have 2 tuples to compare, do it */
375
    result = PyTuple_Type.tp_richcompare(vt, wt, op);
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
376
done:
4679.3.23 by John Arbash Meinel
A bit more testing shows that we are comparing Key to tuples fairly often.
377
    Py_XDECREF(vt);
4679.3.18 by John Arbash Meinel
Copy the hash and richcompare implementations, and add some tests.
378
    return result;
379
}
380
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
381
/** Compare two objects to determine if they are equivalent.
382
 * The basic flow is as follows
383
 *  1) First make sure that both objects are StaticTuple instances. If they
384
 *     aren't then cast self to a tuple, and have the tuple do the comparison.
385
 *  2) Special case comparison to Py_None, because it happens to occur fairly
386
 *     often in the test suite.
387
 *  3) Special case when v and w are the same pointer. As we know the answer to
388
 *     all queries without walking individual items.
389
 *  4) For all operations, we then walk the items to find the first paired
390
 *     items that are not equal.
391
 *  5) If all items found are equal, we then check the length of self and
392
 *     other to determine equality.
393
 *  6) If an item differs, then we apply "op" to those last two items. (eg.
394
 *     StaticTuple(A, B) > StaticTuple(A, C) iff B > C)
395
 */
4679.3.21 by John Arbash Meinel
Implement Key_richcompare directly, rather than thunking to tuples.
396
397
static PyObject *
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
398
StaticTuple_richcompare(PyObject *v, PyObject *w, int op)
4679.3.21 by John Arbash Meinel
Implement Key_richcompare directly, rather than thunking to tuples.
399
{
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
400
    StaticTuple *v_st, *w_st;
4679.3.21 by John Arbash Meinel
Implement Key_richcompare directly, rather than thunking to tuples.
401
    Py_ssize_t vlen, wlen, min_len, i;
4679.3.42 by John Arbash Meinel
Implement comparison support when using nested StaticTuple objects.
402
    PyObject *v_obj, *w_obj;
4679.3.21 by John Arbash Meinel
Implement Key_richcompare directly, rather than thunking to tuples.
403
    richcmpfunc string_richcompare;
404
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
405
    if (!StaticTuple_CheckExact(v)) {
4679.3.42 by John Arbash Meinel
Implement comparison support when using nested StaticTuple objects.
406
        /* This has never triggered, according to python-dev it seems this
407
         * might trigger if '__op__' is defined but '__rop__' is not, sort of
408
         * case. Such as "None == StaticTuple()"
409
         */
4679.3.45 by John Arbash Meinel
Do some work to handle comparison to object that aren't tuples or strings.
410
        fprintf(stderr, "self is not StaticTuple\n");
4679.3.23 by John Arbash Meinel
A bit more testing shows that we are comparing Key to tuples fairly often.
411
        Py_INCREF(Py_NotImplemented);
412
        return Py_NotImplemented;
413
    }
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
414
    v_st = (StaticTuple *)v;
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
415
    if (StaticTuple_CheckExact(w)) {
4679.3.45 by John Arbash Meinel
Do some work to handle comparison to object that aren't tuples or strings.
416
        /* The most common case */
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
417
        w_st = (StaticTuple*)w;
4679.3.45 by John Arbash Meinel
Do some work to handle comparison to object that aren't tuples or strings.
418
    } else if (PyTuple_Check(w)) {
4679.3.21 by John Arbash Meinel
Implement Key_richcompare directly, rather than thunking to tuples.
419
        /* One of v or w is a tuple, so we go the 'slow' route and cast up to
420
         * tuples to compare.
421
         */
4679.3.23 by John Arbash Meinel
A bit more testing shows that we are comparing Key to tuples fairly often.
422
        /* TODO: This seems to be triggering more than I thought it would...
423
         *       We probably want to optimize comparing self to other when
424
         *       other is a tuple.
425
         */
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
426
        return StaticTuple_richcompare_to_tuple(v_st, w, op);
4679.3.45 by John Arbash Meinel
Do some work to handle comparison to object that aren't tuples or strings.
427
    } else if (w == Py_None) {
428
        // None is always less than the object
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
429
        switch (op) {
430
        case Py_NE:case Py_GT:case Py_GE:
4679.3.45 by John Arbash Meinel
Do some work to handle comparison to object that aren't tuples or strings.
431
            Py_INCREF(Py_True);
432
            return Py_True;
433
        case Py_EQ:case Py_LT:case Py_LE:
434
            Py_INCREF(Py_False);
435
            return Py_False;
4679.5.11 by John Arbash Meinel
add a hack-around to handle differences between pyrex 0.9.6 and 0.9.8
436
    default: // Should never happen
437
        return Py_NotImplemented;
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
438
        }
4679.3.45 by John Arbash Meinel
Do some work to handle comparison to object that aren't tuples or strings.
439
    } else {
440
        /* We don't special case this comparison, we just let python handle
441
         * it.
4679.3.21 by John Arbash Meinel
Implement Key_richcompare directly, rather than thunking to tuples.
442
         */
443
         Py_INCREF(Py_NotImplemented);
444
         return Py_NotImplemented;
445
    }
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
446
    /* Now we know that we have 2 StaticTuple objects, so let's compare them.
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
447
     * This code is inspired from tuplerichcompare, except we know our
4679.3.45 by John Arbash Meinel
Do some work to handle comparison to object that aren't tuples or strings.
448
     * objects are limited in scope, so we can inline some comparisons.
4679.3.21 by John Arbash Meinel
Implement Key_richcompare directly, rather than thunking to tuples.
449
     */
450
    if (v == w) {
451
        /* Identical pointers, we can shortcut this easily. */
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
452
        switch (op) {
453
        case Py_EQ:case Py_LE:case Py_GE:
4679.3.21 by John Arbash Meinel
Implement Key_richcompare directly, rather than thunking to tuples.
454
            Py_INCREF(Py_True);
455
            return Py_True;
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
456
        case Py_NE:case Py_LT:case Py_GT:
4679.3.21 by John Arbash Meinel
Implement Key_richcompare directly, rather than thunking to tuples.
457
            Py_INCREF(Py_False);
458
            return Py_False;
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
459
        }
4679.3.21 by John Arbash Meinel
Implement Key_richcompare directly, rather than thunking to tuples.
460
    }
4679.5.6 by John Arbash Meinel
Some comment cleanup, implement a special case for Py_EQ when both objects are intrened.
461
    if (op == Py_EQ
462
        && _StaticTuple_is_interned(v_st)
463
        && _StaticTuple_is_interned(w_st))
464
    {
465
        /* If both objects are interned, we know they are different if the
466
         * pointer is not the same, which would have been handled by the
467
         * previous if. No need to compare the entries.
468
         */
469
        Py_INCREF(Py_False);
470
        return Py_False;
471
    }
4679.3.21 by John Arbash Meinel
Implement Key_richcompare directly, rather than thunking to tuples.
472
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
473
    /* The only time we are likely to compare items of different lengths is in
474
     * something like the interned_keys set. However, the hash is good enough
475
     * that it is rare. Note that 'tuple_richcompare' also does not compare
476
     * lengths here.
4679.3.21 by John Arbash Meinel
Implement Key_richcompare directly, rather than thunking to tuples.
477
     */
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
478
    vlen = v_st->size;
479
    wlen = w_st->size;
480
    min_len = (vlen < wlen) ? vlen : wlen;
4679.3.21 by John Arbash Meinel
Implement Key_richcompare directly, rather than thunking to tuples.
481
    string_richcompare = PyString_Type.tp_richcompare;
482
    for (i = 0; i < min_len; i++) {
4679.3.42 by John Arbash Meinel
Implement comparison support when using nested StaticTuple objects.
483
        PyObject *result = NULL;
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
484
        v_obj = StaticTuple_GET_ITEM(v_st, i);
485
        w_obj = StaticTuple_GET_ITEM(w_st, i);
4679.5.7 by John Arbash Meinel
Add a quick shortcut when comparing item-by-item.
486
        if (v_obj == w_obj) {
487
            /* Shortcut case, these must be identical */
488
            continue;
489
        }
4679.3.42 by John Arbash Meinel
Implement comparison support when using nested StaticTuple objects.
490
        if (PyString_CheckExact(v_obj) && PyString_CheckExact(w_obj)) {
491
            result = string_richcompare(v_obj, w_obj, Py_EQ);
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
492
        } else if (StaticTuple_CheckExact(v_obj) &&
493
                   StaticTuple_CheckExact(w_obj))
4679.3.42 by John Arbash Meinel
Implement comparison support when using nested StaticTuple objects.
494
        {
495
            /* Both are StaticTuple types, so recurse */
496
            result = StaticTuple_richcompare(v_obj, w_obj, Py_EQ);
497
        } else {
4759.2.9 by John Arbash Meinel
Implement support for lots of types.
498
            /* Fall back to generic richcompare */
499
            result = PyObject_RichCompare(v_obj, w_obj, Py_EQ);
4679.3.42 by John Arbash Meinel
Implement comparison support when using nested StaticTuple objects.
500
        }
4679.3.21 by John Arbash Meinel
Implement Key_richcompare directly, rather than thunking to tuples.
501
        if (result == NULL) {
4679.3.42 by John Arbash Meinel
Implement comparison support when using nested StaticTuple objects.
502
            return NULL; /* There seems to be an error */
4679.3.21 by John Arbash Meinel
Implement Key_richcompare directly, rather than thunking to tuples.
503
        }
504
        if (result == Py_False) {
4759.2.9 by John Arbash Meinel
Implement support for lots of types.
505
            // This entry is not identical, Shortcut for Py_EQ
4679.3.21 by John Arbash Meinel
Implement Key_richcompare directly, rather than thunking to tuples.
506
            if (op == Py_EQ) {
507
                return result;
508
            }
509
            Py_DECREF(result);
510
            break;
511
        }
512
        if (result != Py_True) {
4679.3.42 by John Arbash Meinel
Implement comparison support when using nested StaticTuple objects.
513
            /* We don't know *what* richcompare is returning, but it
514
             * isn't something we recognize
4679.3.21 by John Arbash Meinel
Implement Key_richcompare directly, rather than thunking to tuples.
515
             */
516
            PyErr_BadInternalCall();
517
            Py_DECREF(result);
518
            return NULL;
519
        }
520
        Py_DECREF(result);
521
    }
4679.5.11 by John Arbash Meinel
add a hack-around to handle differences between pyrex 0.9.6 and 0.9.8
522
    if (i >= min_len) {
4679.3.42 by John Arbash Meinel
Implement comparison support when using nested StaticTuple objects.
523
        /* We walked off one of the lists, but everything compared equal so
524
         * far. Just compare the size.
525
         */
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
526
        int cmp;
527
        PyObject *res;
528
        switch (op) {
529
        case Py_LT: cmp = vlen <  wlen; break;
530
        case Py_LE: cmp = vlen <= wlen; break;
531
        case Py_EQ: cmp = vlen == wlen; break;
532
        case Py_NE: cmp = vlen != wlen; break;
533
        case Py_GT: cmp = vlen >  wlen; break;
534
        case Py_GE: cmp = vlen >= wlen; break;
535
        default: return NULL; /* cannot happen */
536
        }
537
        if (cmp)
538
            res = Py_True;
539
        else
540
            res = Py_False;
541
        Py_INCREF(res);
542
        return res;
543
    }
4679.3.21 by John Arbash Meinel
Implement Key_richcompare directly, rather than thunking to tuples.
544
    /* The last item differs, shortcut the Py_NE case */
545
    if (op == Py_NE) {
546
        Py_INCREF(Py_True);
547
        return Py_True;
548
    }
549
    /* It is some other comparison, go ahead and do the real check. */
4679.3.42 by John Arbash Meinel
Implement comparison support when using nested StaticTuple objects.
550
    if (PyString_CheckExact(v_obj) && PyString_CheckExact(w_obj))
551
    {
552
        return string_richcompare(v_obj, w_obj, op);
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
553
    } else if (StaticTuple_CheckExact(v_obj) &&
554
               StaticTuple_CheckExact(w_obj))
4679.3.42 by John Arbash Meinel
Implement comparison support when using nested StaticTuple objects.
555
    {
556
        /* Both are StaticTuple types, so recurse */
557
        return StaticTuple_richcompare(v_obj, w_obj, op);
558
    } else {
4759.2.9 by John Arbash Meinel
Implement support for lots of types.
559
        return PyObject_RichCompare(v_obj, w_obj, op);
4679.3.42 by John Arbash Meinel
Implement comparison support when using nested StaticTuple objects.
560
    }
4679.3.21 by John Arbash Meinel
Implement Key_richcompare directly, rather than thunking to tuples.
561
}
562
563
4679.3.17 by John Arbash Meinel
Implement some of the sequence items.
564
static Py_ssize_t
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
565
StaticTuple_length(StaticTuple *self)
4679.3.17 by John Arbash Meinel
Implement some of the sequence items.
566
{
4679.3.37 by John Arbash Meinel
Change the Key header a bit. It is simpler if you use unsigned char
567
    return self->size;
4679.3.35 by John Arbash Meinel
Work on making intern() not generate immortal Key objects.
568
}
569
570
571
static PyObject *
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
572
StaticTuple__is_interned(StaticTuple *self)
4679.3.35 by John Arbash Meinel
Work on making intern() not generate immortal Key objects.
573
{
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
574
    if (_StaticTuple_is_interned(self)) {
4679.3.35 by John Arbash Meinel
Work on making intern() not generate immortal Key objects.
575
        Py_INCREF(Py_True);
576
        return Py_True;
577
    }
578
    Py_INCREF(Py_False);
579
    return Py_False;
580
}
581
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
582
static char StaticTuple__is_interned_doc[] = "_is_interned() => True/False\n"
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
583
    "Check to see if this tuple has been interned.\n";
4679.3.35 by John Arbash Meinel
Work on making intern() not generate immortal Key objects.
584
4679.3.17 by John Arbash Meinel
Implement some of the sequence items.
585
4759.2.1 by Andrew Bennetts
Implement number.add and coerce to allow concatenation with tuples.
586
static PyObject *
4759.2.18 by Matt Nordhoff
Working C implemention.
587
StaticTuple_reduce(StaticTuple *self)
588
{
589
    PyObject *result = NULL, *as_tuple = NULL;
590
591
    result = PyTuple_New(2);
592
    if (!result) {
593
        return NULL;
594
    }
595
    as_tuple = StaticTuple_as_tuple(self);
596
    if (as_tuple == NULL) {
4759.2.19 by Matt Nordhoff
Throw in a Py_DECREF.
597
        Py_DECREF(result);
4759.2.18 by Matt Nordhoff
Working C implemention.
598
        return NULL;
599
    }
4759.2.20 by Matt Nordhoff
Review: Add a Py_INCREF, and test pickling a nested StaticTuple.
600
    Py_INCREF(&StaticTuple_Type);
4759.2.18 by Matt Nordhoff
Working C implemention.
601
    PyTuple_SET_ITEM(result, 0, (PyObject *)&StaticTuple_Type);
602
    PyTuple_SET_ITEM(result, 1, as_tuple);
603
    return result;
604
}
605
606
static char StaticTuple_reduce_doc[] = "__reduce__() => tuple\n";
607
608
609
static PyObject *
4759.2.1 by Andrew Bennetts
Implement number.add and coerce to allow concatenation with tuples.
610
StaticTuple_add(PyObject *v, PyObject *w)
611
{
4759.2.7 by John Arbash Meinel
Re-implement StaticTuple_add() inline, rather that thunking over to tuples.
612
    Py_ssize_t i, len_v, len_w;
613
    PyObject *item;
614
    StaticTuple *result;
4759.2.5 by John Arbash Meinel
Add a bit more tests.
615
     /* StaticTuples and plain tuples may be added (concatenated) to
616
      * StaticTuples.
617
      */
618
    if (StaticTuple_CheckExact(v)) {
4759.2.7 by John Arbash Meinel
Re-implement StaticTuple_add() inline, rather that thunking over to tuples.
619
        len_v = ((StaticTuple*)v)->size;
620
    } else if (PyTuple_Check(v)) {
621
        len_v = PyTuple_GET_SIZE(v);
622
    } else {
623
        Py_INCREF(Py_NotImplemented);
624
        return Py_NotImplemented;
625
    }
4759.2.5 by John Arbash Meinel
Add a bit more tests.
626
    if (StaticTuple_CheckExact(w)) {
4759.2.7 by John Arbash Meinel
Re-implement StaticTuple_add() inline, rather that thunking over to tuples.
627
        len_w = ((StaticTuple*)w)->size;
628
    } else if (PyTuple_Check(w)) {
629
        len_w = PyTuple_GET_SIZE(w);
630
    } else {
631
        Py_INCREF(Py_NotImplemented);
632
        return Py_NotImplemented;
633
    }
634
    result = StaticTuple_New(len_v + len_w);
635
    if (result == NULL)
636
        return NULL;
637
    for (i = 0; i < len_v; ++i) {
638
        // This returns a new reference, which we then 'steal' with 
639
        // StaticTuple_SET_ITEM
640
        item = PySequence_GetItem(v, i);
641
        if (item == NULL) {
642
            Py_DECREF(result);
643
            return NULL;
644
        }
645
        StaticTuple_SET_ITEM(result, i, item);
646
    }
647
    for (i = 0; i < len_w; ++i) {
648
        item = PySequence_GetItem(w, i);
649
        if (item == NULL) {
650
            Py_DECREF(result);
651
            return NULL;
652
        }
653
        StaticTuple_SET_ITEM(result, i+len_v, item);
654
    }
655
    if (!StaticTuple_check_items(result)) {
656
        Py_DECREF(result);
657
        return NULL;
658
    }
659
    return (PyObject *)result;
4759.2.1 by Andrew Bennetts
Implement number.add and coerce to allow concatenation with tuples.
660
}
661
4679.3.17 by John Arbash Meinel
Implement some of the sequence items.
662
static PyObject *
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
663
StaticTuple_item(StaticTuple *self, Py_ssize_t offset)
4679.3.17 by John Arbash Meinel
Implement some of the sequence items.
664
{
665
    PyObject *obj;
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
666
    /* We cast to (int) to avoid worrying about whether Py_ssize_t is a
667
     * long long, etc. offsets should never be >2**31 anyway.
668
     */
669
    if (offset < 0) {
670
        PyErr_Format(PyExc_IndexError, "StaticTuple_item does not support"
671
            " negative indices: %d\n", (int)offset);
672
    } else if (offset >= self->size) {
673
        PyErr_Format(PyExc_IndexError, "StaticTuple index out of range"
674
            " %d >= %d", (int)offset, (int)self->size);
4679.3.17 by John Arbash Meinel
Implement some of the sequence items.
675
        return NULL;
676
    }
4679.3.51 by John Arbash Meinel
Add a _static_tuple_c.pxd file to define the C api to pyrex code.
677
    obj = (PyObject *)self->items[offset];
4679.3.17 by John Arbash Meinel
Implement some of the sequence items.
678
    Py_INCREF(obj);
679
    return obj;
680
}
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
681
4679.3.19 by John Arbash Meinel
implement slicing as a tuple thunk.
682
static PyObject *
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
683
StaticTuple_slice(StaticTuple *self, Py_ssize_t ilow, Py_ssize_t ihigh)
4679.3.19 by John Arbash Meinel
implement slicing as a tuple thunk.
684
{
685
    PyObject *as_tuple, *result;
686
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
687
    as_tuple = StaticTuple_as_tuple(self);
4679.3.19 by John Arbash Meinel
implement slicing as a tuple thunk.
688
    if (as_tuple == NULL) {
689
        return NULL;
690
    }
691
    result = PyTuple_Type.tp_as_sequence->sq_slice(as_tuple, ilow, ihigh);
692
    Py_DECREF(as_tuple);
693
    return result;
694
}
695
4679.3.20 by John Arbash Meinel
Implement tp_traverse, and add a soft dependency on meliae to test it.
696
static int
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
697
StaticTuple_traverse(StaticTuple *self, visitproc visit, void *arg)
4679.3.20 by John Arbash Meinel
Implement tp_traverse, and add a soft dependency on meliae to test it.
698
{
699
    Py_ssize_t i;
4679.3.46 by John Arbash Meinel
Play around a bit with changing the hash function.
700
    for (i = self->size; --i >= 0;) {
4679.3.51 by John Arbash Meinel
Add a _static_tuple_c.pxd file to define the C api to pyrex code.
701
        Py_VISIT(self->items[i]);
4679.3.20 by John Arbash Meinel
Implement tp_traverse, and add a soft dependency on meliae to test it.
702
    }
703
    return 0;
704
}
705
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
706
static char StaticTuple_doc[] =
707
    "C implementation of a StaticTuple structure."
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
708
    "\n This is used as StaticTuple(item1, item2, item3)"
709
    "\n This is similar to tuple, less flexible in what it"
710
    "\n supports, but also lighter memory consumption."
711
    "\n Note that the constructor mimics the () form of tuples"
712
    "\n Rather than the 'tuple()' constructor."
713
    "\n  eg. StaticTuple(a, b) == (a, b) == tuple((a, b))";
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
714
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
715
static PyMethodDef StaticTuple_methods[] = {
716
    {"as_tuple", (PyCFunction)StaticTuple_as_tuple, METH_NOARGS, StaticTuple_as_tuple_doc},
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
717
    {"intern", (PyCFunction)StaticTuple_Intern, METH_NOARGS, StaticTuple_Intern_doc},
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
718
    {"_is_interned", (PyCFunction)StaticTuple__is_interned, METH_NOARGS,
719
     StaticTuple__is_interned_doc},
4739.4.1 by John Arbash Meinel
Implement StaticTuple.from_sequence()
720
    {"from_sequence", (PyCFunction)StaticTuple_from_sequence,
721
     METH_STATIC | METH_VARARGS,
722
     "Create a StaticTuple from a given sequence. This functions"
723
     " the same as the tuple() constructor."},
4759.2.18 by Matt Nordhoff
Working C implemention.
724
    {"__reduce__", (PyCFunction)StaticTuple_reduce, METH_NOARGS, StaticTuple_reduce_doc},
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
725
    {NULL, NULL} /* sentinel */
726
};
727
4759.2.1 by Andrew Bennetts
Implement number.add and coerce to allow concatenation with tuples.
728
729
static PyNumberMethods StaticTuple_as_number = {
4759.2.5 by John Arbash Meinel
Add a bit more tests.
730
    (binaryfunc) StaticTuple_add,   /* nb_add */
731
    0,                              /* nb_subtract */
732
    0,                              /* nb_multiply */
733
    0,                              /* nb_divide */
734
    0,                              /* nb_remainder */
735
    0,                              /* nb_divmod */
736
    0,                              /* nb_power */
737
    0,                              /* nb_negative */
738
    0,                              /* nb_positive */
739
    0,                              /* nb_absolute */
740
    0,                              /* nb_nonzero */
741
    0,                              /* nb_invert */
742
    0,                              /* nb_lshift */
743
    0,                              /* nb_rshift */
744
    0,                              /* nb_and */
745
    0,                              /* nb_xor */
746
    0,                              /* nb_or */
747
    0,                              /* nb_coerce */
4759.2.1 by Andrew Bennetts
Implement number.add and coerce to allow concatenation with tuples.
748
};
4759.2.5 by John Arbash Meinel
Add a bit more tests.
749
    
4759.2.1 by Andrew Bennetts
Implement number.add and coerce to allow concatenation with tuples.
750
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
751
static PySequenceMethods StaticTuple_as_sequence = {
752
    (lenfunc)StaticTuple_length,            /* sq_length */
4679.3.17 by John Arbash Meinel
Implement some of the sequence items.
753
    0,                              /* sq_concat */
754
    0,                              /* sq_repeat */
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
755
    (ssizeargfunc)StaticTuple_item,         /* sq_item */
756
    (ssizessizeargfunc)StaticTuple_slice,   /* sq_slice */
4679.3.17 by John Arbash Meinel
Implement some of the sequence items.
757
    0,                              /* sq_ass_item */
758
    0,                              /* sq_ass_slice */
759
    0,                              /* sq_contains */
760
};
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
761
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
762
/* TODO: Implement StaticTuple_as_mapping.
4679.5.6 by John Arbash Meinel
Some comment cleanup, implement a special case for Py_EQ when both objects are intrened.
763
 *       The only thing we really want to support from there is mp_subscript,
764
 *       so that we could support extended slicing (foo[::2]). Not worth it
765
 *       yet, though.
4679.5.5 by John Arbash Meinel
Review feedback from Andrew Bennetts.
766
 */
767
4679.4.1 by John Arbash Meinel
Handle some issues with static/etc to get things to build on babune.
768
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
769
PyTypeObject StaticTuple_Type = {
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
770
    PyObject_HEAD_INIT(NULL)
771
    0,                                           /* ob_size */
4759.2.13 by John Arbash Meinel
Include the module in tp_name.
772
    "bzrlib._static_tuple_c.StaticTuple",        /* tp_name */
4679.3.51 by John Arbash Meinel
Add a _static_tuple_c.pxd file to define the C api to pyrex code.
773
    sizeof(StaticTuple),                         /* tp_basicsize */
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
774
    sizeof(PyObject *),                          /* tp_itemsize */
4679.3.42 by John Arbash Meinel
Implement comparison support when using nested StaticTuple objects.
775
    (destructor)StaticTuple_dealloc,             /* tp_dealloc */
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
776
    0,                                           /* tp_print */
777
    0,                                           /* tp_getattr */
778
    0,                                           /* tp_setattr */
779
    0,                                           /* tp_compare */
4679.3.42 by John Arbash Meinel
Implement comparison support when using nested StaticTuple objects.
780
    (reprfunc)StaticTuple_repr,                  /* tp_repr */
4759.2.1 by Andrew Bennetts
Implement number.add and coerce to allow concatenation with tuples.
781
    &StaticTuple_as_number,                      /* tp_as_number */
4679.3.42 by John Arbash Meinel
Implement comparison support when using nested StaticTuple objects.
782
    &StaticTuple_as_sequence,                    /* tp_as_sequence */
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
783
    0,                                           /* tp_as_mapping */
4679.3.42 by John Arbash Meinel
Implement comparison support when using nested StaticTuple objects.
784
    (hashfunc)StaticTuple_hash,                  /* tp_hash */
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
785
    0,                                           /* tp_call */
786
    0,                                           /* tp_str */
4747.1.1 by John Arbash Meinel
On Windows w/ Python2.5 PyObject_GenericGetAttr is an external DLL function,
787
    0,                                           /* tp_getattro */
4679.3.16 by John Arbash Meinel
Initial work for a Key class.
788
    0,                                           /* tp_setattro */
789
    0,                                           /* tp_as_buffer */
4759.2.5 by John Arbash Meinel
Add a bit more tests.
790
    /* Py_TPFLAGS_CHECKTYPES tells the number operations that they shouldn't
791
     * try to 'coerce' but instead stuff like 'add' will check it arguments.
792
     */
793
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES,  /* tp_flags*/
4679.3.42 by John Arbash Meinel
Implement comparison support when using nested StaticTuple objects.
794
    StaticTuple_doc,                             /* tp_doc */
4679.3.20 by John Arbash Meinel
Implement tp_traverse, and add a soft dependency on meliae to test it.
795
    /* gc.get_referents checks the IS_GC flag before it calls tp_traverse
796
     * And we don't include this object in the garbage collector because we
797
     * know it doesn't create cycles. However, 'meliae' will follow
798
     * tp_traverse, even if the object isn't GC, and we want that.
799
     */
4679.3.42 by John Arbash Meinel
Implement comparison support when using nested StaticTuple objects.
800
    (traverseproc)StaticTuple_traverse,          /* tp_traverse */
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
801
    0,                                           /* tp_clear */
4679.3.42 by John Arbash Meinel
Implement comparison support when using nested StaticTuple objects.
802
    StaticTuple_richcompare,                     /* tp_richcompare */
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
803
    0,                                           /* tp_weaklistoffset */
4679.3.76 by John Arbash Meinel
Rename StaticTupleInterner => SimpleSet.
804
    // without implementing tp_iter, Python will fall back to PySequence*
805
    // which seems to work ok, we may need something faster/lighter in the
806
    // future.
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
807
    0,                                           /* tp_iter */
808
    0,                                           /* tp_iternext */
4679.3.42 by John Arbash Meinel
Implement comparison support when using nested StaticTuple objects.
809
    StaticTuple_methods,                         /* tp_methods */
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
810
    0,                                           /* tp_members */
811
    0,                                           /* tp_getset */
812
    0,                                           /* tp_base */
813
    0,                                           /* tp_dict */
814
    0,                                           /* tp_descr_get */
815
    0,                                           /* tp_descr_set */
816
    0,                                           /* tp_dictoffset */
817
    0,                                           /* tp_init */
818
    0,                                           /* tp_alloc */
4679.5.9 by John Arbash Meinel
NEWS entry for StaticTuple class.
819
    StaticTuple_new_constructor,                 /* tp_new */
4679.3.1 by John Arbash Meinel
Start working on a Keys type.
820
};
821
4679.3.29 by John Arbash Meinel
Start work on implementing a Key.intern() function.
822
4679.3.41 by John Arbash Meinel
Finish switching the naming to StaticTuple.
823
static PyMethodDef static_tuple_c_methods[] = {
4679.3.1 by John Arbash Meinel
Start working on a Keys type.
824
    {NULL, NULL}
825
};
826
827
4679.3.47 by John Arbash Meinel
Work out how to expose the C api using the Python PyCObject interface.
828
static void
4679.3.51 by John Arbash Meinel
Add a _static_tuple_c.pxd file to define the C api to pyrex code.
829
setup_interned_tuples(PyObject *m)
4679.3.1 by John Arbash Meinel
Start working on a Keys type.
830
{
4679.3.76 by John Arbash Meinel
Rename StaticTupleInterner => SimpleSet.
831
    _interned_tuples = (PyObject *)SimpleSet_New();
4679.3.51 by John Arbash Meinel
Add a _static_tuple_c.pxd file to define the C api to pyrex code.
832
    if (_interned_tuples != NULL) {
833
        Py_INCREF(_interned_tuples);
834
        PyModule_AddObject(m, "_interned_tuples", _interned_tuples);
4679.3.29 by John Arbash Meinel
Start work on implementing a Key.intern() function.
835
    }
4679.3.47 by John Arbash Meinel
Work out how to expose the C api using the Python PyCObject interface.
836
}
837
838
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
839
static void
840
setup_empty_tuple(PyObject *m)
841
{
842
    StaticTuple *stuple;
843
    if (_interned_tuples == NULL) {
844
        fprintf(stderr, "You need to call setup_interned_tuples() before"
845
                " setup_empty_tuple, because we intern it.\n");
846
    }
847
    // We need to create the empty tuple
848
    stuple = (StaticTuple *)StaticTuple_New(0);
849
    _empty_tuple = StaticTuple_Intern(stuple);
850
    assert(_empty_tuple == stuple);
851
    // At this point, refcnt is 2: 1 from New(), and 1 from the return from
852
    // intern(). We will keep 1 for the _empty_tuple global, and use the other
853
    // for the module reference.
854
    PyModule_AddObject(m, "_empty_tuple", (PyObject *)_empty_tuple);
855
}
856
857
static int
858
_StaticTuple_CheckExact(PyObject *obj)
859
{
860
    return StaticTuple_CheckExact(obj);
861
}
862
863
static void
864
setup_c_api(PyObject *m)
865
{
866
    _export_function(m, "StaticTuple_New", StaticTuple_New,
867
        "StaticTuple *(Py_ssize_t)");
868
    _export_function(m, "StaticTuple_Intern", StaticTuple_Intern,
869
        "StaticTuple *(StaticTuple *)");
4739.4.1 by John Arbash Meinel
Implement StaticTuple.from_sequence()
870
    _export_function(m, "StaticTuple_FromSequence", StaticTuple_FromSequence,
871
        "StaticTuple *(PyObject *)");
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
872
    _export_function(m, "_StaticTuple_CheckExact", _StaticTuple_CheckExact,
873
        "int(PyObject *)");
874
}
875
876
4679.5.11 by John Arbash Meinel
add a hack-around to handle differences between pyrex 0.9.6 and 0.9.8
877
static int
4736.1.1 by John Arbash Meinel
Py_ssize_t and its associated function typedefs are not available w/ python 2.4
878
_workaround_pyrex_096(void)
4679.5.11 by John Arbash Meinel
add a hack-around to handle differences between pyrex 0.9.6 and 0.9.8
879
{
880
    /* Work around an incompatibility in how pyrex 0.9.6 exports a module,
881
     * versus how pyrex 0.9.8 and cython 0.11 export it.
882
     * Namely 0.9.6 exports import__simple_set_pyx and tries to
883
     * "import _simple_set_pyx" but it is available only as
884
     * "import bzrlib._simple_set_pyx"
885
     * It is a shame to hack up sys.modules, but that is what we've got to do.
886
     */
887
    PyObject *sys_module = NULL, *modules = NULL, *set_module = NULL;
888
    int retval = -1;
889
890
    /* Clear out the current ImportError exception, and try again. */
891
    PyErr_Clear();
892
    /* Note that this only seems to work if somewhere else imports
893
     * bzrlib._simple_set_pyx before importing bzrlib._static_tuple_c
894
     */
895
    set_module = PyImport_ImportModule("bzrlib._simple_set_pyx");
896
    if (set_module == NULL) {
897
        goto end;
898
    }
899
    /* Add the _simple_set_pyx into sys.modules at the appropriate location. */
900
    sys_module = PyImport_ImportModule("sys");
901
    if (sys_module == NULL) {
902
        goto end;
903
    }
904
    modules = PyObject_GetAttrString(sys_module, "modules");
905
    if (modules == NULL || !PyDict_Check(modules)) {
906
        goto end;
907
    }
908
    PyDict_SetItemString(modules, "_simple_set_pyx", set_module);
909
    /* Now that we have hacked it in, try the import again. */
910
    retval = import_bzrlib___simple_set_pyx();
911
end:
912
    Py_XDECREF(set_module);
913
    Py_XDECREF(sys_module);
914
    Py_XDECREF(modules);
915
    return retval;
916
}
917
918
4679.3.47 by John Arbash Meinel
Work out how to expose the C api using the Python PyCObject interface.
919
PyMODINIT_FUNC
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
920
init_static_tuple_c(void)
4679.3.47 by John Arbash Meinel
Work out how to expose the C api using the Python PyCObject interface.
921
{
922
    PyObject* m;
923
4747.1.1 by John Arbash Meinel
On Windows w/ Python2.5 PyObject_GenericGetAttr is an external DLL function,
924
    StaticTuple_Type.tp_getattro = PyObject_GenericGetAttr;
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
925
    if (PyType_Ready(&StaticTuple_Type) < 0)
4679.3.47 by John Arbash Meinel
Work out how to expose the C api using the Python PyCObject interface.
926
        return;
927
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
928
    m = Py_InitModule3("_static_tuple_c", static_tuple_c_methods,
4679.3.47 by John Arbash Meinel
Work out how to expose the C api using the Python PyCObject interface.
929
                       "C implementation of a StaticTuple structure");
930
    if (m == NULL)
931
      return;
932
933
    Py_INCREF(&StaticTuple_Type);
934
    PyModule_AddObject(m, "StaticTuple", (PyObject *)&StaticTuple_Type);
4679.5.11 by John Arbash Meinel
add a hack-around to handle differences between pyrex 0.9.6 and 0.9.8
935
    if (import_bzrlib___simple_set_pyx() == -1
936
        && _workaround_pyrex_096() == -1)
937
    {
4679.3.81 by John Arbash Meinel
Fix up _simple_set_pyx.pyx to be compatible with pyrex again.
938
        return;
939
    }
4679.3.74 by John Arbash Meinel
Revert back to before I started trying to move to pyrex/cython code.
940
    setup_interned_tuples(m);
941
    setup_empty_tuple(m);
942
    setup_c_api(m);
4679.3.47 by John Arbash Meinel
Work out how to expose the C api using the Python PyCObject interface.
943
}
4759.2.5 by John Arbash Meinel
Add a bit more tests.
944
945
// vim: tabstop=4 sw=4 expandtab