~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_static_tuple_c.c

  • Committer: Martin Pool
  • Date: 2005-05-17 06:56:16 UTC
  • Revision ID: mbp@sourcefrog.net-20050517065616-6f23381d6184a8aa
- add space for un-merged patches

Show diffs side-by-side

added added

removed removed

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