/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to breezy/_static_tuple_c.c

  • Committer: Jelmer Vernooij
  • Date: 2020-03-22 01:35:14 UTC
  • mfrom: (7490.7.6 work)
  • mto: This revision was merged to the branch mainline in revision 7499.
  • Revision ID: jelmer@jelmer.uk-20200322013514-7vw1ntwho04rcuj3
merge lp:brz/3.1.

Show diffs side-by-side

added added

removed removed

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