« back to all changes in this revision
Viewing changes to bzrlib/_static_tuple_c.c
- browse files at revision 4679.8.5
- compare with another revision
- compare with revision 5814
- download diff
- download tarball
- view history from revision 4679.8.5
- Committer: John Arbash Meinel
- Date: 2009-10-12 20:12:32 UTC
- mfrom: (4736 +trunk)
- mto: This revision was merged to the branch mainline in revision 4749.
- Revision ID: john@arbash-meinel.com-20091012201232-ccnceqvk29u7v22u
Merge bzr.dev 4736
This includes the updates to StaticTuple, etc, to build using Pyrex 0.9.6.4
This includes the updates to StaticTuple, etc, to build using Pyrex 0.9.6.4
- files modified:
- NEWS
added
removed
bzrlib/_static_tuple_c.c
22
22
23
23
#include "_static_tuple_c.h"
24
24
#include "_export_c_api.h"
25
26
/* Pyrex 0.9.6.4 exports _simple_set_pyx_api as
27
* import__simple_set_pyx(), while Pyrex 0.9.8.5 and Cython 0.11.3 export them
28
* as import_bzrlib___simple_set_pyx(). As such, we just #define one to be
29
* equivalent to the other in our internal code.
30
*/
31
#define import__simple_set_pyx import_bzrlib___simple_set_pyx
25
32
#include "_simple_set_pyx_api.h"
26
33
27
34
#include "python-compat.h"
74
81
static StaticTuple *
75
82
StaticTuple_Intern(StaticTuple *self)
76
83
{
77
PyObject *unique_key = NULL;
84
PyObject *canonical_tuple = NULL;
78
85
79
86
if (_interned_tuples == NULL || _StaticTuple_is_interned(self)) {
80
87
Py_INCREF(self);
83
90
/* SimpleSet_Add returns whatever object is present at self
84
91
* or the new object if it needs to add it.
85
92
*/
86
unique_key = SimpleSet_Add(_interned_tuples, (PyObject *)self);
87
if (!unique_key) {
88
// Suppress any error and just return the object
89
PyErr_Clear();
90
Py_INCREF(self);
91
return self;
93
canonical_tuple = SimpleSet_Add(_interned_tuples, (PyObject *)self);
94
if (!canonical_tuple) {
95
// Some sort of exception, propogate it.
96
return NULL;
92
97
}
93
if (unique_key != (PyObject *)self) {
94
// There was already a key at that location
95
return (StaticTuple *)unique_key;
98
if (canonical_tuple != (PyObject *)self) {
99
// There was already a tuple with that value
100
return (StaticTuple *)canonical_tuple;
96
101
}
97
102
self->flags |= STATIC_TUPLE_INTERNED_FLAG;
98
// The two references in the dict do not count, so that the StaticTuple object
99
// does not become immortal just because it was interned.
103
// The two references in the dict do not count, so that the StaticTuple
104
// object does not become immortal just because it was interned.
100
105
Py_REFCNT(self) -= 1;
101
106
return self;
102
107
}
169
174
170
175
171
176
static PyObject *
172
StaticTuple_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
177
StaticTuple_new_constructor(PyTypeObject *type, PyObject *args, PyObject *kwds)
173
178
{
174
179
StaticTuple *self;
175
180
PyObject *obj = NULL;
187
192
if (len < 0 || len > 255) {
188
193
/* Too big or too small */
189
194
PyErr_SetString(PyExc_ValueError, "StaticTuple.__init__(...)"
190
" takes from 0 to 255 key bits");
195
" takes from 0 to 255 items");
191
196
return NULL;
192
197
}
193
198
self = (StaticTuple *)StaticTuple_New(len);
199
204
if (!PyString_CheckExact(obj)) {
200
205
if (!StaticTuple_CheckExact(obj)) {
201
206
PyErr_SetString(PyExc_TypeError, "StaticTuple.__init__(...)"
202
" requires that all key bits are strings or StaticTuple.");
203
/* TODO: What is the proper way to dealloc ? */
207
" requires that all items are strings or StaticTuple.");
204
208
type->tp_dealloc((PyObject *)self);
205
209
return NULL;
206
210
}
236
240
/* adapted from tuplehash(), is the specific hash value considered
237
241
* 'stable'?
238
242
*/
239
register long x, y;
240
Py_ssize_t len = self->size;
241
PyObject **p;
242
long mult = 1000003L;
243
register long x, y;
244
Py_ssize_t len = self->size;
245
PyObject **p;
246
long mult = 1000003L;
243
247
244
248
#if STATIC_TUPLE_HAS_HASH
245
249
if (self->hash != -1) {
246
250
return self->hash;
247
251
}
248
252
#endif
249
x = 0x345678L;
250
p = self->items;
253
x = 0x345678L;
254
p = self->items;
251
255
// TODO: We could set specific flags if we know that, for example, all the
252
// keys are strings. I haven't seen a real-world benefit to that yet,
253
// though.
256
// items are strings. I haven't seen a real-world benefit to that
257
// yet, though.
254
258
while (--len >= 0) {
255
259
y = PyObject_Hash(*p++);
256
260
if (y == -1) /* failure */
259
263
/* the cast might truncate len; that doesn't change hash stability */
260
264
mult += (long)(82520L + len + len);
261
265
}
262
x += 97531L;
263
if (x == -1)
264
x = -2;
266
x += 97531L;
267
if (x == -1)
268
x = -2;
265
269
#if STATIC_TUPLE_HAS_HASH
266
if (self->hash != -1) {
267
if (self->hash != x) {
268
fprintf(stderr, "hash changed: %d => %d\n", self->hash, x);
269
}
270
}
271
270
self->hash = x;
272
271
#endif
273
return x;
272
return x;
274
273
}
275
274
276
275
static PyObject *
281
280
282
281
vt = StaticTuple_as_tuple((StaticTuple *)v);
283
282
if (vt == NULL) {
284
goto Done;
283
goto done;
285
284
}
286
285
if (!PyTuple_Check(wt)) {
287
286
PyErr_BadInternalCall();
288
result = NULL;
289
goto Done;
287
goto done;
290
288
}
291
289
/* Now we have 2 tuples to compare, do it */
292
290
result = PyTuple_Type.tp_richcompare(vt, wt, op);
293
Done:
291
done:
294
292
Py_XDECREF(vt);
295
293
return result;
296
294
}
297
295
296
/** Compare two objects to determine if they are equivalent.
297
* The basic flow is as follows
298
* 1) First make sure that both objects are StaticTuple instances. If they
299
* aren't then cast self to a tuple, and have the tuple do the comparison.
300
* 2) Special case comparison to Py_None, because it happens to occur fairly
301
* often in the test suite.
302
* 3) Special case when v and w are the same pointer. As we know the answer to
303
* all queries without walking individual items.
304
* 4) For all operations, we then walk the items to find the first paired
305
* items that are not equal.
306
* 5) If all items found are equal, we then check the length of self and
307
* other to determine equality.
308
* 6) If an item differs, then we apply "op" to those last two items. (eg.
309
* StaticTuple(A, B) > StaticTuple(A, C) iff B > C)
310
*/
298
311
299
312
static PyObject *
300
313
StaticTuple_richcompare(PyObject *v, PyObject *w, int op)
301
314
{
302
StaticTuple *vk, *wk;
315
StaticTuple *v_st, *w_st;
303
316
Py_ssize_t vlen, wlen, min_len, i;
304
317
PyObject *v_obj, *w_obj;
305
318
richcmpfunc string_richcompare;
313
326
Py_INCREF(Py_NotImplemented);
314
327
return Py_NotImplemented;
315
328
}
316
vk = (StaticTuple *)v;
329
v_st = (StaticTuple *)v;
317
330
if (StaticTuple_CheckExact(w)) {
318
331
/* The most common case */
319
wk = (StaticTuple*)w;
332
w_st = (StaticTuple*)w;
320
333
} else if (PyTuple_Check(w)) {
321
334
/* One of v or w is a tuple, so we go the 'slow' route and cast up to
322
335
* tuples to compare.
325
338
* We probably want to optimize comparing self to other when
326
339
* other is a tuple.
327
340
*/
328
return StaticTuple_richcompare_to_tuple(vk, w, op);
341
return StaticTuple_richcompare_to_tuple(v_st, w, op);
329
342
} else if (w == Py_None) {
330
343
// None is always less than the object
331
switch (op) {
332
case Py_NE:case Py_GT:case Py_GE:
344
switch (op) {
345
case Py_NE:case Py_GT:case Py_GE:
333
346
Py_INCREF(Py_True);
334
347
return Py_True;
335
348
case Py_EQ:case Py_LT:case Py_LE:
336
349
Py_INCREF(Py_False);
337
350
return Py_False;
338
}
351
default: // Should never happen
352
return Py_NotImplemented;
353
}
339
354
} else {
340
355
/* We don't special case this comparison, we just let python handle
341
356
* it.
344
359
return Py_NotImplemented;
345
360
}
346
361
/* Now we know that we have 2 StaticTuple objects, so let's compare them.
347
* This code is somewhat borrowed from tuplerichcompare, except we know our
362
* This code is inspired from tuplerichcompare, except we know our
348
363
* objects are limited in scope, so we can inline some comparisons.
349
364
*/
350
365
if (v == w) {
351
366
/* Identical pointers, we can shortcut this easily. */
352
switch (op) {
353
case Py_EQ:case Py_LE:case Py_GE:
367
switch (op) {
368
case Py_EQ:case Py_LE:case Py_GE:
354
369
Py_INCREF(Py_True);
355
370
return Py_True;
356
case Py_NE:case Py_LT:case Py_GT:
371
case Py_NE:case Py_LT:case Py_GT:
357
372
Py_INCREF(Py_False);
358
373
return Py_False;
359
}
360
}
361
/* TODO: if STATIC_TUPLE_INTERNED_FLAG is set on both objects and they are
362
* not the same pointer, then we know they aren't the same object
363
* without having to do sub-by-sub comparison.
364
*/
374
}
375
}
376
if (op == Py_EQ
377
&& _StaticTuple_is_interned(v_st)
378
&& _StaticTuple_is_interned(w_st))
379
{
380
/* If both objects are interned, we know they are different if the
381
* pointer is not the same, which would have been handled by the
382
* previous if. No need to compare the entries.
383
*/
384
Py_INCREF(Py_False);
385
return Py_False;
386
}
365
387
366
/* It will be rare that we compare tuples of different lengths, so we don't
367
* start by optimizing the length comparision, same as the tuple code
368
* TODO: Interning may change this, because we'll be comparing lots of
369
* different StaticTuple objects in the intern dict
388
/* The only time we are likely to compare items of different lengths is in
389
* something like the interned_keys set. However, the hash is good enough
390
* that it is rare. Note that 'tuple_richcompare' also does not compare
391
* lengths here.
370
392
*/
371
vlen = vk->size;
372
wlen = wk->size;
373
min_len = (vlen < wlen) ? vlen : wlen;
393
vlen = v_st->size;
394
wlen = w_st->size;
395
min_len = (vlen < wlen) ? vlen : wlen;
374
396
string_richcompare = PyString_Type.tp_richcompare;
375
397
for (i = 0; i < min_len; i++) {
376
398
PyObject *result = NULL;
377
v_obj = StaticTuple_GET_ITEM(vk, i);
378
w_obj = StaticTuple_GET_ITEM(wk, i);
399
v_obj = StaticTuple_GET_ITEM(v_st, i);
400
w_obj = StaticTuple_GET_ITEM(w_st, i);
401
if (v_obj == w_obj) {
402
/* Shortcut case, these must be identical */
403
continue;
404
}
379
405
if (PyString_CheckExact(v_obj) && PyString_CheckExact(w_obj)) {
380
406
result = string_richcompare(v_obj, w_obj, Py_EQ);
381
407
} else if (StaticTuple_CheckExact(v_obj) &&
415
441
}
416
442
Py_DECREF(result);
417
443
}
418
if (i >= vlen || i >= wlen) {
444
if (i >= min_len) {
419
445
/* We walked off one of the lists, but everything compared equal so
420
446
* far. Just compare the size.
421
447
*/
422
int cmp;
423
PyObject *res;
424
switch (op) {
425
case Py_LT: cmp = vlen < wlen; break;
426
case Py_LE: cmp = vlen <= wlen; break;
427
case Py_EQ: cmp = vlen == wlen; break;
428
case Py_NE: cmp = vlen != wlen; break;
429
case Py_GT: cmp = vlen > wlen; break;
430
case Py_GE: cmp = vlen >= wlen; break;
431
default: return NULL; /* cannot happen */
432
}
433
if (cmp)
434
res = Py_True;
435
else
436
res = Py_False;
437
Py_INCREF(res);
438
return res;
439
}
448
int cmp;
449
PyObject *res;
450
switch (op) {
451
case Py_LT: cmp = vlen < wlen; break;
452
case Py_LE: cmp = vlen <= wlen; break;
453
case Py_EQ: cmp = vlen == wlen; break;
454
case Py_NE: cmp = vlen != wlen; break;
455
case Py_GT: cmp = vlen > wlen; break;
456
case Py_GE: cmp = vlen >= wlen; break;
457
default: return NULL; /* cannot happen */
458
}
459
if (cmp)
460
res = Py_True;
461
else
462
res = Py_False;
463
Py_INCREF(res);
464
return res;
465
}
440
466
/* The last item differs, shortcut the Py_NE case */
441
467
if (op == Py_NE) {
442
468
Py_INCREF(Py_True);
477
503
}
478
504
479
505
static char StaticTuple__is_interned_doc[] = "_is_interned() => True/False\n"
480
"Check to see if this key has been interned.\n";
506
"Check to see if this tuple has been interned.\n";
481
507
482
508
483
509
static PyObject *
484
510
StaticTuple_item(StaticTuple *self, Py_ssize_t offset)
485
511
{
486
512
PyObject *obj;
487
if (offset < 0 || offset >= self->size) {
488
PyErr_SetString(PyExc_IndexError, "StaticTuple index out of range");
513
/* We cast to (int) to avoid worrying about whether Py_ssize_t is a
514
* long long, etc. offsets should never be >2**31 anyway.
515
*/
516
if (offset < 0) {
517
PyErr_Format(PyExc_IndexError, "StaticTuple_item does not support"
518
" negative indices: %d\n", (int)offset);
519
} else if (offset >= self->size) {
520
PyErr_Format(PyExc_IndexError, "StaticTuple index out of range"
521
" %d >= %d", (int)offset, (int)self->size);
489
522
return NULL;
490
523
}
491
524
obj = (PyObject *)self->items[offset];
519
552
520
553
static char StaticTuple_doc[] =
521
554
"C implementation of a StaticTuple structure."
522
"\n This is used as StaticTuple(key_bit_1, key_bit_2, key_bit_3, ...)"
523
"\n This is similar to tuple, just less flexible in what it"
524
"\n supports, but also lighter memory consumption.";
555
"\n This is used as StaticTuple(item1, item2, item3)"
556
"\n This is similar to tuple, less flexible in what it"
557
"\n supports, but also lighter memory consumption."
558
"\n Note that the constructor mimics the () form of tuples"
559
"\n Rather than the 'tuple()' constructor."
560
"\n eg. StaticTuple(a, b) == (a, b) == tuple((a, b))";
525
561
526
562
static PyMethodDef StaticTuple_methods[] = {
527
563
{"as_tuple", (PyCFunction)StaticTuple_as_tuple, METH_NOARGS, StaticTuple_as_tuple_doc},
542
578
0, /* sq_contains */
543
579
};
544
580
581
/* TODO: Implement StaticTuple_as_mapping.
582
* The only thing we really want to support from there is mp_subscript,
583
* so that we could support extended slicing (foo[::2]). Not worth it
584
* yet, though.
585
*/
586
545
587
546
588
PyTypeObject StaticTuple_Type = {
547
589
PyObject_HEAD_INIT(NULL)
590
632
0, /* tp_dictoffset */
591
633
0, /* tp_init */
592
634
0, /* tp_alloc */
593
StaticTuple_new, /* tp_new */
635
StaticTuple_new_constructor, /* tp_new */
594
636
};
595
637
596
638
646
688
}
647
689
648
690
691
static int
692
_workaround_pyrex_096()
693
{
694
/* Work around an incompatibility in how pyrex 0.9.6 exports a module,
695
* versus how pyrex 0.9.8 and cython 0.11 export it.
696
* Namely 0.9.6 exports import__simple_set_pyx and tries to
697
* "import _simple_set_pyx" but it is available only as
698
* "import bzrlib._simple_set_pyx"
699
* It is a shame to hack up sys.modules, but that is what we've got to do.
700
*/
701
PyObject *sys_module = NULL, *modules = NULL, *set_module = NULL;
702
int retval = -1;
703
704
/* Clear out the current ImportError exception, and try again. */
705
PyErr_Clear();
706
/* Note that this only seems to work if somewhere else imports
707
* bzrlib._simple_set_pyx before importing bzrlib._static_tuple_c
708
*/
709
set_module = PyImport_ImportModule("bzrlib._simple_set_pyx");
710
if (set_module == NULL) {
711
// fprintf(stderr, "Failed to import bzrlib._simple_set_pyx\n");
712
goto end;
713
}
714
/* Add the _simple_set_pyx into sys.modules at the appropriate location. */
715
sys_module = PyImport_ImportModule("sys");
716
if (sys_module == NULL) {
717
// fprintf(stderr, "Failed to import sys\n");
718
goto end;
719
}
720
modules = PyObject_GetAttrString(sys_module, "modules");
721
if (modules == NULL || !PyDict_Check(modules)) {
722
// fprintf(stderr, "Failed to find sys.modules\n");
723
goto end;
724
}
725
PyDict_SetItemString(modules, "_simple_set_pyx", set_module);
726
/* Now that we have hacked it in, try the import again. */
727
retval = import_bzrlib___simple_set_pyx();
728
end:
729
Py_XDECREF(set_module);
730
Py_XDECREF(sys_module);
731
Py_XDECREF(modules);
732
return retval;
733
}
734
735
649
736
PyMODINIT_FUNC
650
737
init_static_tuple_c(void)
651
738
{
661
748
662
749
Py_INCREF(&StaticTuple_Type);
663
750
PyModule_AddObject(m, "StaticTuple", (PyObject *)&StaticTuple_Type);
664
if (import_bzrlib___simple_set_pyx() == -1) {
665
// We failed to set up, stop early
751
if (import_bzrlib___simple_set_pyx() == -1
752
&& _workaround_pyrex_096() == -1)
753
{
666
754
return;
667
755
}
668
756
setup_interned_tuples(m);
Loggerhead is a web-based interface for Breezy
Version: 2.0.1