[Python-checkins] CVS: python/dist/src/Objects methodobject.c,2.26,2.27 object.c,2.73,2.74 floatobject.c,2.57,2.58 complexobject.c,2.24,2.25 classobject.c,2.91,2.92 funcobject.c,2.22,2.23
Fred L. Drake
python-dev@python.org
Thu, 29 Jun 2000 12:17:07 -0700
Update of /cvsroot/python/python/dist/src/Objects
In directory slayer.i.sourceforge.net:/tmp/cvs-serv3837/Objects
Modified Files:
methodobject.c object.c floatobject.c complexobject.c
classobject.c funcobject.c
Log Message:
This patch addresses two main issues: (1) There exist some non-fatal
errors in some of the hash algorithms. For exmaple, in float_hash and
complex_hash a certain part of the value is not included in the hash
calculation. See Tim's, Guido's, and my discussion of this on
python-dev in May under the title "fix float_hash and complex_hash for
64-bit *nix"
(2) The hash algorithms that use pointers (e.g. func_hash, code_hash)
are universally not correct on Win64 (they assume that sizeof(long) ==
sizeof(void*))
As well, this patch significantly cleans up the hash code. It adds the
two function _Py_HashDouble and _PyHash_VoidPtr that the various
hashing routine are changed to use.
These help maintain the hash function invariant: (a==b) =>
(hash(a)==hash(b))) I have added Lib/test/test_hash.py and
Lib/test/output/test_hash to test this for some cases.
Index: methodobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/methodobject.c,v
retrieving revision 2.26
retrieving revision 2.27
diff -C2 -r2.26 -r2.27
*** methodobject.c 2000/05/03 23:44:35 2.26
--- methodobject.c 2000/06/29 19:17:04 2.27
***************
*** 173,177 ****
PyCFunctionObject *a;
{
! long x;
if (a->m_self == NULL)
x = 0;
--- 173,177 ----
PyCFunctionObject *a;
{
! long x,y;
if (a->m_self == NULL)
x = 0;
***************
*** 181,185 ****
return -1;
}
! return x ^ (long) a->m_ml->ml_meth;
}
--- 181,191 ----
return -1;
}
! y = _Py_HashPointer(a->m_ml->ml_meth);
! if (y == -1)
! return -1;
! x ^= y;
! if (x == -1)
! x = -2;
! return x;
}
Index: object.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/object.c,v
retrieving revision 2.73
retrieving revision 2.74
diff -C2 -r2.73 -r2.74
*** object.c 2000/06/28 21:57:18 2.73
--- object.c 2000/06/29 19:17:04 2.74
***************
*** 34,37 ****
--- 34,39 ----
#include "Python.h"
+ #include "mymath.h"
+
/* just for trashcan: */
#include "compile.h"
***************
*** 508,512 ****
--- 510,570 ----
}
+
+ /* Set of hash utility functions to help maintaining the invariant that
+ iff a==b then hash(a)==hash(b)
+
+ All the utility functions (_Py_Hash*()) return "-1" to signify an error.
+ */
+
+ long
+ _Py_HashDouble(v)
+ double v;
+ {
+ /* Use frexp to get at the bits in the double.
+ * Since the VAX D double format has 56 mantissa bits, which is the
+ * most of any double format in use, each of these parts may have as
+ * many as (but no more than) 56 significant bits.
+ * So, assuming sizeof(long) >= 4, each part can be broken into two longs;
+ * frexp and multiplication are used to do that.
+ * Also, since the Cray double format has 15 exponent bits, which is the
+ * most of any double format in use, shifting the exponent field left by
+ * 15 won't overflow a long (again assuming sizeof(long) >= 4).
+ */
+ int expo;
+ long hipart;
+
+ v = frexp(v, &expo);
+ v = v * 2147483648.0; /* 2**31 */
+ hipart = (long)v; /* Take the top 32 bits */
+ v = (v - (double)hipart) * 2147483648.0; /* Get the next 32 bits */
+
+ return hipart + (long)v + (expo << 15); /* Combine everything */
+ }
+
long
+ _Py_HashPointer(p)
+ void *p;
+ {
+ #if SIZEOF_LONG >= SIZEOF_VOID_P
+ return (long)p;
+ #else
+ /* convert to a Python long and hash that */
+ PyObject* longobj;
+ long x;
+
+ if ((longobj = PyLong_FromVoidPtr(p)) == NULL) {
+ x = -1;
+ goto finally;
+ }
+ x = PyObject_Hash(longobj);
+
+ finally:
+ Py_XDECREF(longobj);
+ return x;
+ #endif
+ }
+
+
+ long
PyObject_Hash(v)
PyObject *v;
***************
*** 515,520 ****
if (tp->tp_hash != NULL)
return (*tp->tp_hash)(v);
! if (tp->tp_compare == NULL)
! return (long) v; /* Use address as hash value */
/* If there's a cmp but no hash defined, the object can't be hashed */
PyErr_SetString(PyExc_TypeError, "unhashable type");
--- 573,579 ----
if (tp->tp_hash != NULL)
return (*tp->tp_hash)(v);
! if (tp->tp_compare == NULL) {
! return _Py_HashPointer(v); /* Use address as hash value */
! }
/* If there's a cmp but no hash defined, the object can't be hashed */
PyErr_SetString(PyExc_TypeError, "unhashable type");
Index: floatobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/floatobject.c,v
retrieving revision 2.57
retrieving revision 2.58
diff -C2 -r2.57 -r2.58
*** floatobject.c 2000/05/03 23:44:34 2.57
--- floatobject.c 2000/06/29 19:17:04 2.58
***************
*** 60,64 ****
--- 60,70 ----
#ifndef LONG_MAX
+ #if SIZEOF_LONG == 4
#define LONG_MAX 0X7FFFFFFFL
+ #elif SIZEOF_LONG == 8
+ #define LONG_MAX 0X7FFFFFFFFFFFFFFFL
+ #else
+ #error "could not set LONG_MAX"
+ #endif
#endif
***************
*** 358,361 ****
--- 364,368 ----
}
+
static long
float_hash(v)
***************
*** 363,367 ****
{
double intpart, fractpart;
- int expo;
long x;
/* This is designed so that Python numbers with the same
--- 370,373 ----
***************
*** 380,384 ****
if (fractpart == 0.0) {
! if (intpart > 0x7fffffffL || -intpart > 0x7fffffffL) {
/* Convert to long int and use its hash... */
PyObject *w = PyLong_FromDouble(v->ob_fval);
--- 386,390 ----
if (fractpart == 0.0) {
! if (intpart > LONG_MAX || -intpart > LONG_MAX) {
/* Convert to long int and use its hash... */
PyObject *w = PyLong_FromDouble(v->ob_fval);
***************
*** 394,405 ****
/* Note -- if you change this code, also change the copy
in complexobject.c */
! long hipart;
! fractpart = frexp(fractpart, &expo);
! fractpart = fractpart * 2147483648.0; /* 2**31 */
! hipart = (long)fractpart; /* Take the top 32 bits */
! fractpart = (fractpart - (double)hipart) * 2147483648.0;
! /* Get the next 32 bits */
! x = hipart + (long)fractpart + (long)intpart + (expo << 15);
! /* Combine everything */
}
if (x == -1)
--- 400,406 ----
/* Note -- if you change this code, also change the copy
in complexobject.c */
! x = _Py_HashDouble(v->ob_fval);
! if (x == -1)
! return -1;
}
if (x == -1)
Index: complexobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/complexobject.c,v
retrieving revision 2.24
retrieving revision 2.25
diff -C2 -r2.24 -r2.25
*** complexobject.c 2000/05/03 23:44:34 2.24
--- complexobject.c 2000/06/29 19:17:04 2.25
***************
*** 286,291 ****
{
double intpart, fractpart;
! int expo;
! long hipart, x;
/* This is designed so that Python numbers with the same
value hash to the same value, otherwise comparisons
--- 286,290 ----
{
double intpart, fractpart;
! long x;
/* This is designed so that Python numbers with the same
value hash to the same value, otherwise comparisons
***************
*** 303,307 ****
if (fractpart == 0.0 && v->cval.imag == 0.0) {
! if (intpart > 0x7fffffffL || -intpart > 0x7fffffffL) {
/* Convert to long int and use its hash... */
PyObject *w = PyLong_FromDouble(v->cval.real);
--- 302,306 ----
if (fractpart == 0.0 && v->cval.imag == 0.0) {
! if (intpart > LONG_MAX || -intpart > LONG_MAX) {
/* Convert to long int and use its hash... */
PyObject *w = PyLong_FromDouble(v->cval.real);
***************
*** 315,325 ****
}
else {
! fractpart = frexp(fractpart, &expo);
! fractpart = fractpart * 2147483648.0; /* 2**31 */
! hipart = (long)fractpart; /* Take the top 32 bits */
! fractpart = (fractpart - (double)hipart) * 2147483648.0;
! /* Get the next 32 bits */
! x = hipart + (long)fractpart + (long)intpart + (expo << 15);
! /* Combine everything */
if (v->cval.imag != 0.0) { /* Hash the imaginary part */
--- 314,320 ----
}
else {
! x = _Py_HashDouble(v->cval.real);
! if (x == -1)
! return -1;
if (v->cval.imag != 0.0) { /* Hash the imaginary part */
***************
*** 327,348 ****
to the same value as complex(y, x).
Still better than it used to be :-) */
! #ifdef MPW
! {
! extended e;
! fractpart = modf(v->cval.imag, &e);
! intpart = e;
! }
! #else
! fractpart = modf(v->cval.imag, &intpart);
! #endif
! fractpart = frexp(fractpart, &expo);
! fractpart = fractpart * 2147483648.0; /* 2**31 */
! hipart = (long)fractpart; /* Take the top 32 bits */
! fractpart =
! (fractpart - (double)hipart) * 2147483648.0;
! /* Get the next 32 bits */
! x ^= hipart + (long)fractpart +
! (long)intpart + (expo << 15);
! /* Combine everything */
}
}
--- 322,329 ----
to the same value as complex(y, x).
Still better than it used to be :-) */
! long y = _Py_HashDouble(v->cval.imag);
! if (y == -1)
! return -1;
! x += y;
}
}
Index: classobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/classobject.c,v
retrieving revision 2.91
retrieving revision 2.92
diff -C2 -r2.91 -r2.92
*** classobject.c 2000/06/28 23:46:07 2.91
--- classobject.c 2000/06/29 19:17:04 2.92
***************
*** 865,872 ****
if (func == NULL) {
PyErr_Clear();
! outcome = (long)inst;
! if (outcome == -1)
! outcome = -2;
! return outcome;
}
PyErr_SetString(PyExc_TypeError, "unhashable instance");
--- 865,869 ----
if (func == NULL) {
PyErr_Clear();
! return _Py_HashPointer(inst);
}
PyErr_SetString(PyExc_TypeError, "unhashable instance");
Index: funcobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/funcobject.c,v
retrieving revision 2.22
retrieving revision 2.23
diff -C2 -r2.22 -r2.23
*** funcobject.c 2000/06/23 19:37:01 2.22
--- funcobject.c 2000/06/29 19:17:04 2.23
***************
*** 232,239 ****
PyFunctionObject *f;
{
! long h;
h = PyObject_Hash(f->func_code);
if (h == -1) return h;
! h = h ^ (long)f->func_globals;
if (h == -1) h = -2;
return h;
--- 232,241 ----
PyFunctionObject *f;
{
! long h,x;
h = PyObject_Hash(f->func_code);
if (h == -1) return h;
! x = _Py_HashPointer(f->func_globals);
! if (x == -1) return x;
! h ^= x;
if (h == -1) h = -2;
return h;