aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Makefile2
-rw-r--r--immutables/_map.c65
-rw-r--r--immutables/_map.h1
-rw-r--r--tests/test_map.py27
4 files changed, 92 insertions, 3 deletions
diff --git a/Makefile b/Makefile
index 68f4b1e..f698d35 100644
--- a/Makefile
+++ b/Makefile
@@ -8,5 +8,7 @@ test:
python setup.py test -v
rtest:
+ ~/dev/venvs/36-debug/bin/python setup.py build_ext --inplace
+
env PYTHONPATH=. \
~/dev/venvs/36-debug/bin/python -m test.regrtest -R3:3 --testdir tests/
diff --git a/immutables/_map.c b/immutables/_map.c
index 6f76318..445b713 100644
--- a/immutables/_map.c
+++ b/immutables/_map.c
@@ -2453,6 +2453,8 @@ map_alloc(void)
return NULL;
}
o->h_weakreflist = NULL;
+ o->h_hash = -1;
+ o->h_count = 0;
PyObject_GC_Track(o);
return o;
}
@@ -2478,8 +2480,6 @@ map_new(void)
return NULL;
}
- o->h_count = 0;
-
if (_empty_map == NULL) {
Py_INCREF(o);
_empty_map = o;
@@ -2942,6 +2942,65 @@ error:
}
+static Py_uhash_t
+_shuffle_bits(Py_uhash_t h)
+{
+ return ((h ^ 89869747UL) ^ (h << 16)) * 3644798167UL;
+}
+
+
+static Py_hash_t
+map_py_hash(MapObject *self)
+{
+ /* Adapted version of frozenset.__hash__: it's important
+ that Map.__hash__ is independant of key/values order.
+
+ Optimization idea: compute and memoize intermediate
+ hash values for HAMT nodes.
+ */
+
+ if (self->h_hash != -1) {
+ return self->h_hash;
+ }
+
+ Py_uhash_t hash = 0;
+
+ MapIteratorState iter;
+ map_iter_t iter_res;
+ map_iterator_init(&iter, self->h_root);
+ do {
+ PyObject *v_key;
+ PyObject *v_val;
+
+ iter_res = map_iterator_next(&iter, &v_key, &v_val);
+ if (iter_res == I_ITEM) {
+ Py_hash_t vh = PyObject_Hash(v_key);
+ if (vh == -1) {
+ return -1;
+ }
+ hash ^= _shuffle_bits((Py_uhash_t)vh);
+
+ vh = PyObject_Hash(v_val);
+ if (vh == -1) {
+ return -1;
+ }
+ hash ^= _shuffle_bits((Py_uhash_t)vh);
+ }
+ } while (iter_res != I_END);
+
+ hash ^= ((Py_uhash_t)self->h_count * 2 + 1) * 1927868237UL;
+
+ hash ^= (hash >> 11) ^ (hash >> 25);
+ hash = hash * 69069U + 907133923UL;
+
+ self->h_hash = (Py_hash_t)hash;
+ if (self->h_hash == -1) {
+ self->h_hash = 1;
+ }
+ return self->h_hash;
+}
+
+
static PyMethodDef Map_methods[] = {
{"set", (PyCFunction)map_py_set, METH_VARARGS, NULL},
{"get", (PyCFunction)map_py_get, METH_VARARGS, NULL},
@@ -2987,7 +3046,7 @@ PyTypeObject _Map_Type = {
.tp_clear = (inquiry)map_tp_clear,
.tp_new = map_tp_new,
.tp_weaklistoffset = offsetof(MapObject, h_weakreflist),
- .tp_hash = PyObject_HashNotImplemented,
+ .tp_hash = (hashfunc)map_py_hash,
.tp_repr = (reprfunc)map_py_repr,
};
diff --git a/immutables/_map.h b/immutables/_map.h
index 41cfa13..6e87c4b 100644
--- a/immutables/_map.h
+++ b/immutables/_map.h
@@ -22,6 +22,7 @@ typedef struct {
MapNode *h_root;
PyObject *h_weakreflist;
Py_ssize_t h_count;
+ Py_hash_t h_hash;
} MapObject;
diff --git a/tests/test_map.py b/tests/test_map.py
index 06c82b9..91050a2 100644
--- a/tests/test_map.py
+++ b/tests/test_map.py
@@ -757,6 +757,33 @@ class MapTest(unittest.TestCase):
self.assertTrue(repr(h).startswith(
'<immutables.Map({{...}: 1}) at 0x'))
+ def test_hash_1(self):
+ h = Map()
+ self.assertNotEqual(hash(h), -1)
+ self.assertEqual(hash(h), hash(h))
+
+ h = h.set(1, 2).set('a', 'b')
+ self.assertNotEqual(hash(h), -1)
+ self.assertEqual(hash(h), hash(h))
+
+ self.assertEqual(
+ hash(h.set(1, 2).set('a', 'b')),
+ hash(h.set('a', 'b').set(1, 2)))
+
+ def test_hash_2(self):
+ h = Map()
+ A = HashKey(100, 'A')
+
+ m = h.set(1, 2).set(A, 3).set(3, 4)
+ with self.assertRaises(HashingError):
+ with HaskKeyCrasher(error_on_hash=True):
+ hash(m)
+
+ m = h.set(1, 2).set(2, A).set(3, 4)
+ with self.assertRaises(HashingError):
+ with HaskKeyCrasher(error_on_hash=True):
+ hash(m)
+
if __name__ == "__main__":
unittest.main()