[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