[Zodb-checkins] SVN: ZODB/branches/fdrake-64bits/src/BTrees/ use
PY_LONG_LONG for "I" keys and values
Fred L. Drake, Jr.
fdrake at gmail.com
Thu Apr 13 13:34:29 EDT 2006
Log message for revision 66936:
use PY_LONG_LONG for "I" keys and values
Changed:
U ZODB/branches/fdrake-64bits/src/BTrees/BTreeModuleTemplate.c
U ZODB/branches/fdrake-64bits/src/BTrees/SetOpTemplate.c
U ZODB/branches/fdrake-64bits/src/BTrees/intkeymacros.h
U ZODB/branches/fdrake-64bits/src/BTrees/intvaluemacros.h
U ZODB/branches/fdrake-64bits/src/BTrees/sorters.c
U ZODB/branches/fdrake-64bits/src/BTrees/tests/testBTrees.py
-=-
Modified: ZODB/branches/fdrake-64bits/src/BTrees/BTreeModuleTemplate.c
===================================================================
--- ZODB/branches/fdrake-64bits/src/BTrees/BTreeModuleTemplate.c 2006-04-13 17:31:23 UTC (rev 66935)
+++ ZODB/branches/fdrake-64bits/src/BTrees/BTreeModuleTemplate.c 2006-04-13 17:34:29 UTC (rev 66936)
@@ -66,6 +66,41 @@
#define ASSERT(C, S, R) if (! (C)) { \
PyErr_SetString(PyExc_AssertionError, (S)); return (R); }
+
+#ifdef NEED_LONG_LONG_SUPPORT
+/* Helper code used to support long long instead of int. */
+
+static int
+longlong_check(PyObject *ob)
+{
+ if (PyInt_Check(ob))
+ return 1;
+
+ if (PyLong_Check(ob)) {
+ /* check magnitude */
+ PY_LONG_LONG val = PyLong_AsLongLong(ob);
+
+ if (val == -1 && PyErr_Occurred())
+ return 0;
+ return 1;
+ }
+ return 0;
+}
+
+static PyObject *
+longlong_as_object(PY_LONG_LONG val)
+{
+ static PY_LONG_LONG maxint = 0;
+
+ if (maxint == 0)
+ maxint = PyInt_GetMax();
+ if ((val > maxint) || (val < (-maxint-1)))
+ return PyLong_FromLongLong(val);
+ return PyInt_FromLong((long)val);
+}
+#endif
+
+
/* Various kinds of BTree and Bucket structs are instances of
* "sized containers", and have a common initial layout:
* The stuff needed for all Python objects, or all Persistent objects.
Modified: ZODB/branches/fdrake-64bits/src/BTrees/SetOpTemplate.c
===================================================================
--- ZODB/branches/fdrake-64bits/src/BTrees/SetOpTemplate.c 2006-04-13 17:31:23 UTC (rev 66935)
+++ ZODB/branches/fdrake-64bits/src/BTrees/SetOpTemplate.c 2006-04-13 17:34:29 UTC (rev 66936)
@@ -543,7 +543,7 @@
*/
if (result->len > 0) {
size_t newlen; /* number of elements in final result set */
- newlen = sort_int4_nodups(result->keys, (size_t)result->len);
+ newlen = sort_int8_nodups(result->keys, (size_t)result->len);
result->len = (int)newlen;
}
return (PyObject *)result;
Modified: ZODB/branches/fdrake-64bits/src/BTrees/intkeymacros.h
===================================================================
--- ZODB/branches/fdrake-64bits/src/BTrees/intkeymacros.h 2006-04-13 17:31:23 UTC (rev 66935)
+++ ZODB/branches/fdrake-64bits/src/BTrees/intkeymacros.h 2006-04-13 17:34:29 UTC (rev 66936)
@@ -1,16 +1,23 @@
#define KEYMACROS_H "$Id$\n"
-#define KEY_TYPE int
+#define NEED_LONG_LONG_SUPPORT
+
+#define KEY_TYPE PY_LONG_LONG
#undef KEY_TYPE_IS_PYOBJECT
-#define KEY_CHECK PyInt_Check
+#define KEY_CHECK longlong_check
#define TEST_KEY_SET_OR(V, K, T) if ( ( (V) = (((K) < (T)) ? -1 : (((K) > (T)) ? 1: 0)) ) , 0 )
#define DECREF_KEY(KEY)
#define INCREF_KEY(k)
#define COPY_KEY(KEY, E) (KEY=(E))
-#define COPY_KEY_TO_OBJECT(O, K) O=PyInt_FromLong(K)
+#define COPY_KEY_TO_OBJECT(O, K) O=longlong_as_object(K)
#define COPY_KEY_FROM_ARG(TARGET, ARG, STATUS) \
- if (PyInt_Check(ARG)) TARGET=PyInt_AS_LONG(ARG); else { \
- PyErr_SetString(PyExc_TypeError, "expected integer key"); \
- (STATUS)=0; (TARGET)=0; }
+ if (PyInt_Check(ARG)) TARGET=PyInt_AS_LONG(ARG); else \
+ if (longlong_check(ARG)) TARGET=PyLong_AsLongLong(ARG); else \
+ if (PyLong_Check(ARG)) { \
+ PyErr_SetString(PyExc_ValueError, "long integer out of range"); \
+ (STATUS)=0; (TARGET)=0; } \
+ else { \
+ PyErr_SetString(PyExc_TypeError, "expected integer key"); \
+ (STATUS)=0; (TARGET)=0; }
#define MULTI_INT_UNION 1
Modified: ZODB/branches/fdrake-64bits/src/BTrees/intvaluemacros.h
===================================================================
--- ZODB/branches/fdrake-64bits/src/BTrees/intvaluemacros.h 2006-04-13 17:31:23 UTC (rev 66935)
+++ ZODB/branches/fdrake-64bits/src/BTrees/intvaluemacros.h 2006-04-13 17:34:29 UTC (rev 66936)
@@ -1,21 +1,28 @@
#define VALUEMACROS_H "$Id$\n"
-#define VALUE_TYPE int
+#define NEED_LONG_LONG_SUPPORT
+
+#define VALUE_TYPE PY_LONG_LONG
#undef VALUE_TYPE_IS_PYOBJECT
#define TEST_VALUE(K, T) (((K) < (T)) ? -1 : (((K) > (T)) ? 1: 0))
#define VALUE_SAME(VALUE, TARGET) ( (VALUE) == (TARGET) )
#define DECLARE_VALUE(NAME) VALUE_TYPE NAME
-#define VALUE_PARSE "i"
+#define VALUE_PARSE "L"
#define DECREF_VALUE(k)
#define INCREF_VALUE(k)
#define COPY_VALUE(V, E) (V=(E))
-#define COPY_VALUE_TO_OBJECT(O, K) O=PyInt_FromLong(K)
+#define COPY_VALUE_TO_OBJECT(O, K) O=longlong_as_object(K)
#define COPY_VALUE_FROM_ARG(TARGET, ARG, STATUS) \
- if (PyInt_Check(ARG)) TARGET=PyInt_AsLong(ARG); else { \
- PyErr_SetString(PyExc_TypeError, "expected integer value"); \
- (STATUS)=0; (TARGET)=0; }
-
+ if (PyInt_Check(ARG)) TARGET=PyInt_AS_LONG(ARG); else \
+ if (longlong_check(ARG)) TARGET=PyLong_AsLongLong(ARG); else \
+ if (PyLong_Check(ARG)) { \
+ PyErr_SetString(PyExc_ValueError, "long integer out of range"); \
+ (STATUS)=0; (TARGET)=0; } \
+ else { \
+ PyErr_SetString(PyExc_TypeError, "expected integer key"); \
+ (STATUS)=0; (TARGET)=0; }
+
#define NORMALIZE_VALUE(V, MIN) ((MIN) > 0) ? ((V)/=(MIN)) : 0
#define MERGE_DEFAULT 1
Modified: ZODB/branches/fdrake-64bits/src/BTrees/sorters.c
===================================================================
--- ZODB/branches/fdrake-64bits/src/BTrees/sorters.c 2006-04-13 17:31:23 UTC (rev 66935)
+++ ZODB/branches/fdrake-64bits/src/BTrees/sorters.c 2006-04-13 17:34:29 UTC (rev 66936)
@@ -15,22 +15,22 @@
/* Revision information: $Id$ */
/* The only routine here intended to be used outside the file is
- size_t sort_int4_nodups(int *p, size_t n)
+ size_t sort_int8_nodups(int *p, size_t n)
Sort the array of n ints pointed at by p, in place, and also remove
duplicates. Return the number of unique elements remaining, which occupy
a contiguous and monotonically increasing slice of the array starting at p.
- Example: If the input array is [3, 1, 2, 3, 1, 5, 2], sort_int4_nodups
+ Example: If the input array is [3, 1, 2, 3, 1, 5, 2], sort_int8_nodups
returns 4, and the first 4 elements of the array are changed to
[1, 2, 3, 5]. The content of the remaining array positions is not defined.
Notes:
- + This is specific to 4-byte signed ints, with endianness natural to the
+ + This is specific to 8-byte signed ints, with endianness natural to the
platform.
- + 4*n bytes of available heap memory are required for best speed.
+ + 8*n bytes of available heap memory are required for best speed.
*/
#include <stdlib.h>
@@ -45,7 +45,7 @@
the radix sort has to know everything about the type's internal
representation.
*/
-typedef int element_type;
+typedef PY_LONG_LONG element_type;
/* The radixsort is faster than the quicksort for large arrays, but radixsort
has high fixed overhead, making it a poor choice for small arrays. The
@@ -72,25 +72,25 @@
swaps are done internally, the final result may come back in 'in' or 'work';
and that pointer is returned.
- radixsort_int4 is specific to signed 4-byte ints, with natural machine
+ radixsort_int8 is specific to signed 8-byte ints, with natural machine
endianness.
*/
static element_type*
-radixsort_int4(element_type *in, element_type *work, size_t n)
+radixsort_int8(element_type *in, element_type *work, size_t n)
{
/* count[i][j] is the number of input elements that have byte value j
in byte position i, where byte position 0 is the LSB. Note that
holding i fixed, the sum of count[i][j] over all j in range(256)
is n.
*/
- size_t count[4][256];
+ size_t count[8][256];
size_t i;
int offset, offsetinc;
/* Which byte position are we working on now? 0=LSB, 1, 2, ... */
int bytenum;
- assert(sizeof(element_type) == 4);
+ assert(sizeof(element_type) == 8);
assert(in);
assert(work);
@@ -102,6 +102,10 @@
++count[1][(x >> 8) & 0xff];
++count[2][(x >> 16) & 0xff];
++count[3][(x >> 24) & 0xff];
+ ++count[4][(x >> 32) & 0xff];
+ ++count[5][(x >> 40) & 0xff];
+ ++count[6][(x >> 48) & 0xff];
+ ++count[7][(x >> 56) & 0xff];
}
/* For p an element_type* cast to char*, offset is how much farther we
@@ -111,7 +115,7 @@
from p+offset to get to the element's more-significant bytes.
*/
{
- int one = 1;
+ element_type one = 1;
if (*(char*)&one) {
/* Little endian. */
offset = 0;
@@ -498,12 +502,12 @@
/* Sort p and remove duplicates, as fast as we can. */
static size_t
-sort_int4_nodups(int *p, size_t n)
+sort_int8_nodups(PY_LONG_LONG *p, size_t n)
{
size_t nunique;
element_type *work;
- assert(sizeof(int) == sizeof(element_type));
+ assert(sizeof(PY_LONG_LONG) == sizeof(element_type));
assert(p);
/* Use quicksort if the array is small, OR if malloc can't find
@@ -514,7 +518,7 @@
work = (element_type *)malloc(n * sizeof(element_type));
if (work) {
- element_type *out = radixsort_int4(p, work, n);
+ element_type *out = radixsort_int8(p, work, n);
nunique = uniq(p, out, n);
free(work);
}
Modified: ZODB/branches/fdrake-64bits/src/BTrees/tests/testBTrees.py
===================================================================
--- ZODB/branches/fdrake-64bits/src/BTrees/tests/testBTrees.py 2006-04-13 17:31:23 UTC (rev 66935)
+++ ZODB/branches/fdrake-64bits/src/BTrees/tests/testBTrees.py 2006-04-13 17:34:29 UTC (rev 66936)
@@ -1145,6 +1145,102 @@
"changed size")
break
+
+LARGEST_32_BITS = 2147483647
+SMALLEST_32_BITS = -LARGEST_32_BITS - 1
+
+SMALLEST_POSITIVE_33_BITS = LARGEST_32_BITS + 1
+LARGEST_NEGATIVE_33_BITS = SMALLEST_32_BITS - 1
+
+LARGEST_64_BITS = 0x7fffffffffffffff
+SMALLEST_64_BITS = -LARGEST_64_BITS - 1
+
+SMALLEST_POSITIVE_65_BITS = LARGEST_64_BITS + 1
+LARGEST_NEGATIVE_65_BITS = SMALLEST_64_BITS - 1
+
+class TestLongIntSupport:
+
+ def getTwoValues(self):
+ """Return two distinct values; these must compare as un-equal.
+
+ These values must be usable as values.
+
+ """
+ return object(), object()
+
+ def getTwoKeys(self):
+ """Return two distinct values, these must compare as un-equal.
+
+ These values must be usable as keys.
+
+ """
+ return 0, 1
+
+ def _set_value(self, key, value):
+ self.t[key] = value
+
+class TestLongIntKeys(TestLongIntSupport):
+
+ def testLongIntKeysWork(self):
+ o1, o2 = self.getTwoValues()
+ assert o1 != o2
+
+ # Test some small key values first:
+ self.t[0L] = o1
+ self.assertEqual(self.t[0], o1)
+ self.t[0] = o2
+ self.assertEqual(self.t[0L], o2)
+ self.assertEqual(list(self.t.keys()), [0])
+
+ # Test some large key values too:
+ k1 = SMALLEST_POSITIVE_33_BITS
+ k2 = LARGEST_64_BITS
+ k3 = SMALLEST_64_BITS
+ self.t[k1] = o1
+ self.t[k2] = o2
+ self.t[k3] = o1
+ self.assertEqual(self.t[k1], o1)
+ self.assertEqual(self.t[k2], o2)
+ self.assertEqual(self.t[k3], o1)
+ self.assertEqual(list(self.t.keys()), [k3, 0, k1, k2])
+
+ def testLongIntKeysOutOfRange(self):
+ o1, o2 = self.getTwoValues()
+ self.assertRaises(
+ ValueError,
+ self._set_value, SMALLEST_POSITIVE_65_BITS, o1)
+ self.assertRaises(
+ ValueError,
+ self._set_value, LARGEST_NEGATIVE_65_BITS, o1)
+
+class TestLongIntValues(TestLongIntSupport):
+
+ def testLongIntValuesWork(self):
+ keys = list(self.getTwoKeys())
+ keys.sort()
+ k1, k2 = keys
+ assert k1 != k2
+
+ # This is the smallest positive integer that requires 33 bits:
+ v1 = SMALLEST_POSITIVE_33_BITS
+ v2 = v1 + 1
+
+ self.t[k1] = v1
+ self.t[k2] = v2
+ self.assertEqual(self.t[k1], v1)
+ self.assertEqual(self.t[k2], v2)
+ self.assertEqual(list(self.t.values()), [v1, v2])
+
+ def testLongIntValuesOutOfRange(self):
+ k1, k2 = self.getTwoKeys()
+ self.assertRaises(
+ ValueError,
+ self._set_value, k1, SMALLEST_POSITIVE_65_BITS)
+ self.assertRaises(
+ ValueError,
+ self._set_value, k1, LARGEST_NEGATIVE_65_BITS)
+
+
# tests of various type errors
class TypeTest(TestCase):
@@ -1499,18 +1595,24 @@
def setUp(self):
self.t = OOSet()
-class IIBTreeTest(BTreeTests):
+class IIBTreeTest(BTreeTests, TestLongIntKeys, TestLongIntValues):
def setUp(self):
self.t = IIBTree()
-class IFBTreeTest(BTreeTests):
+ def getTwoValues(self):
+ return 1, 2
+class IFBTreeTest(BTreeTests, TestLongIntKeys):
def setUp(self):
self.t = IFBTree()
-class IOBTreeTest(BTreeTests):
+ def getTwoValues(self):
+ return 0.5, 1.5
+class IOBTreeTest(BTreeTests, TestLongIntKeys):
def setUp(self):
self.t = IOBTree()
-class OIBTreeTest(BTreeTests):
+class OIBTreeTest(BTreeTests, TestLongIntValues):
def setUp(self):
self.t = OIBTree()
+ def getTwoKeys(self):
+ return object(), object()
class OOBTreeTest(BTreeTests):
def setUp(self):
self.t = OOBTree()
More information about the Zodb-checkins
mailing list