[Python-checkins] r53818 - in python/trunk: Include/dictobject.h Lib/test/test_set.py Objects/dictobject.c Objects/setobject.c
raymond.hettinger
python-checkins at python.org
Mon Feb 19 03:03:23 CET 2007
Author: raymond.hettinger
Date: Mon Feb 19 03:03:19 2007
New Revision: 53818
Modified:
python/trunk/Include/dictobject.h
python/trunk/Lib/test/test_set.py
python/trunk/Objects/dictobject.c
python/trunk/Objects/setobject.c
Log:
Extend work on revision 52962: Eliminate redundant calls to PyObject_Hash().
Modified: python/trunk/Include/dictobject.h
==============================================================================
--- python/trunk/Include/dictobject.h (original)
+++ python/trunk/Include/dictobject.h Mon Feb 19 03:03:19 2007
@@ -100,12 +100,15 @@
PyAPI_FUNC(void) PyDict_Clear(PyObject *mp);
PyAPI_FUNC(int) PyDict_Next(
PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value);
+PyAPI_FUNC(int) _PyDict_Next(
+ PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value, long *hash);
PyAPI_FUNC(PyObject *) PyDict_Keys(PyObject *mp);
PyAPI_FUNC(PyObject *) PyDict_Values(PyObject *mp);
PyAPI_FUNC(PyObject *) PyDict_Items(PyObject *mp);
PyAPI_FUNC(Py_ssize_t) PyDict_Size(PyObject *mp);
PyAPI_FUNC(PyObject *) PyDict_Copy(PyObject *mp);
PyAPI_FUNC(int) PyDict_Contains(PyObject *mp, PyObject *key);
+PyAPI_FUNC(int) _PyDict_Contains(PyObject *mp, PyObject *key, long hash);
/* PyDict_Update(mp, other) is equivalent to PyDict_Merge(mp, other, 1). */
PyAPI_FUNC(int) PyDict_Update(PyObject *mp, PyObject *other);
Modified: python/trunk/Lib/test/test_set.py
==============================================================================
--- python/trunk/Lib/test/test_set.py (original)
+++ python/trunk/Lib/test/test_set.py Mon Feb 19 03:03:19 2007
@@ -26,6 +26,14 @@
def __repr__(self):
return repr(self.value)
+class HashCountingInt(int):
+ 'int-like object that counts the number of times __hash__ is called'
+ def __init__(self, *args):
+ self.hash_count = 0
+ def __hash__(self):
+ self.hash_count += 1
+ return int.__hash__(self)
+
class TestJointOps(unittest.TestCase):
# Tests common to both set and frozenset
@@ -270,6 +278,18 @@
fo.close()
os.remove(test_support.TESTFN)
+ def test_do_not_rehash_dict_keys(self):
+ n = 10
+ d = dict.fromkeys(map(HashCountingInt, xrange(n)))
+ self.assertEqual(sum(elem.hash_count for elem in d), n)
+ s = self.thetype(d)
+ self.assertEqual(sum(elem.hash_count for elem in d), n)
+ s.difference(d)
+ self.assertEqual(sum(elem.hash_count for elem in d), n)
+ if hasattr(s, 'symmetric_difference_update'):
+ s.symmetric_difference_update(d)
+ self.assertEqual(sum(elem.hash_count for elem in d), n)
+
class TestSet(TestJointOps):
thetype = set
Modified: python/trunk/Objects/dictobject.c
==============================================================================
--- python/trunk/Objects/dictobject.c (original)
+++ python/trunk/Objects/dictobject.c Mon Feb 19 03:03:19 2007
@@ -803,6 +803,34 @@
return 1;
}
+/* Internal version of PyDict_Next that returns a hash value in addition to the key and value.*/
+int
+_PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, PyObject **pvalue, long *phash)
+{
+ register Py_ssize_t i;
+ register Py_ssize_t mask;
+ register dictentry *ep;
+
+ if (!PyDict_Check(op))
+ return 0;
+ i = *ppos;
+ if (i < 0)
+ return 0;
+ ep = ((dictobject *)op)->ma_table;
+ mask = ((dictobject *)op)->ma_mask;
+ while (i <= mask && ep[i].me_value == NULL)
+ i++;
+ *ppos = i+1;
+ if (i > mask)
+ return 0;
+ *phash = (long)(ep[i].me_hash);
+ if (pkey)
+ *pkey = ep[i].me_key;
+ if (pvalue)
+ *pvalue = ep[i].me_value;
+ return 1;
+}
+
/* Methods */
static void
@@ -1987,6 +2015,17 @@
return ep == NULL ? -1 : (ep->me_value != NULL);
}
+/* Internal version of PyDict_Contains used when the hash value is already known */
+int
+_PyDict_Contains(PyObject *op, PyObject *key, long hash)
+{
+ dictobject *mp = (dictobject *)op;
+ dictentry *ep;
+
+ ep = (mp->ma_lookup)(mp, key, hash);
+ return ep == NULL ? -1 : (ep->me_value != NULL);
+}
+
/* Hack to implement "key in dict" */
static PySequenceMethods dict_as_sequence = {
0, /* sq_length */
Modified: python/trunk/Objects/setobject.c
==============================================================================
--- python/trunk/Objects/setobject.c (original)
+++ python/trunk/Objects/setobject.c Mon Feb 19 03:03:19 2007
@@ -918,8 +918,14 @@
if (PyDict_CheckExact(other)) {
PyObject *value;
Py_ssize_t pos = 0;
- while (PyDict_Next(other, &pos, &key, &value)) {
- if (set_add_key(so, key) == -1)
+ long hash;
+
+ while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
+ setentry an_entry;
+
+ an_entry.hash = hash;
+ an_entry.key = key;
+ if (set_add_entry(so, &an_entry) == -1)
return -1;
}
return 0;
@@ -1382,7 +1388,7 @@
setentry entrycopy;
entrycopy.hash = entry->hash;
entrycopy.key = entry->key;
- if (!PyDict_Contains(other, entry->key)) {
+ if (!_PyDict_Contains(other, entry->key, entry->hash)) {
if (set_add_entry((PySetObject *)result, &entrycopy) == -1) {
Py_DECREF(result);
return NULL;
@@ -1453,12 +1459,10 @@
if (PyDict_CheckExact(other)) {
PyObject *value;
int rv;
- while (PyDict_Next(other, &pos, &key, &value)) {
+ long hash;
+ while (_PyDict_Next(other, &pos, &key, &value, &hash)) {
setentry an_entry;
- long hash = PyObject_Hash(key);
- if (hash == -1)
- return NULL;
an_entry.hash = hash;
an_entry.key = key;
rv = set_discard_entry(so, &an_entry);
More information about the Python-checkins
mailing list