[Zodb-checkins] SVN: ZODB/trunk/src/ Bugs Fixed
Jim Fulton
jim at zope.com
Thu Aug 27 16:46:39 EDT 2009
Log message for revision 103321:
Bugs Fixed
----------
- BTrees (and TreeSets) kept references to internal keys.
https://bugs.launchpad.net/zope3/+bug/294788
- BTree Sets and TreeSets don't support the standard set add method.
(Now either add or the original insert method can be used to add an
object to a BTree-based set.)
Changed:
U ZODB/trunk/src/BTrees/BTreeTemplate.c
U ZODB/trunk/src/BTrees/SetTemplate.c
U ZODB/trunk/src/BTrees/TreeSetTemplate.c
U ZODB/trunk/src/BTrees/tests/testBTrees.py
U ZODB/trunk/src/BTrees/tests/testConflict.py
U ZODB/trunk/src/CHANGES.txt
-=-
Modified: ZODB/trunk/src/BTrees/BTreeTemplate.c
===================================================================
--- ZODB/trunk/src/BTrees/BTreeTemplate.c 2009-08-27 20:17:28 UTC (rev 103320)
+++ ZODB/trunk/src/BTrees/BTreeTemplate.c 2009-08-27 20:46:38 UTC (rev 103321)
@@ -692,6 +692,37 @@
/* A bucket got smaller. This is much harder, and despite that we
* don't try to rebalance the tree.
*/
+
+ if (min && childlength)
+ { /* We removed a key. but the node child is non-empty. If the
+ deleted key is the node key, then update the node key using
+ the smallest key of the node child.
+
+ This doesn't apply to the 0th node, whos key is unused.
+ */
+ int _cmp = 1;
+ TEST_KEY_SET_OR(_cmp, key, d->key) goto Error;
+ if (_cmp == 0)
+ { /* Need to replace key with first key from child */
+ Bucket *bucket;
+
+ if (SameType_Check(self, d->child))
+ {
+ UNLESS(PER_USE(d->child)) goto Error;
+ bucket = BTREE(d->child)->firstbucket;
+ PER_UNUSE(d->child);
+ }
+ else
+ bucket = BUCKET(d->child);
+
+ UNLESS(PER_USE(bucket)) goto Error;
+ DECREF_KEY(d->key);
+ COPY_KEY(d->key, bucket->keys[0]);
+ INCREF_KEY(d->key);
+ PER_UNUSE(bucket);
+ }
+ }
+
if (status == 2) { /* this is the last reference to child status */
/* Two problems to solve: May have to adjust our own firstbucket,
* and the bucket that went away needs to get unlinked.
Modified: ZODB/trunk/src/BTrees/SetTemplate.c
===================================================================
--- ZODB/trunk/src/BTrees/SetTemplate.c 2009-08-27 20:17:28 UTC (rev 103320)
+++ ZODB/trunk/src/BTrees/SetTemplate.c 2009-08-27 20:46:38 UTC (rev 103321)
@@ -202,8 +202,11 @@
"_p_deactivate() -- Reinitialize from a newly created copy"},
#endif
+ {"add", (PyCFunction)Set_insert, METH_VARARGS,
+ "add(id) -- Add a key to the set"},
+
{"insert", (PyCFunction)Set_insert, METH_VARARGS,
- "insert(id,[ignored]) -- Add a key to the set"},
+ "insert(id) -- Add a key to the set"},
{"update", (PyCFunction)Set_update, METH_VARARGS,
"update(seq) -- Add the items from the given sequence to the set"},
Modified: ZODB/trunk/src/BTrees/TreeSetTemplate.c
===================================================================
--- ZODB/trunk/src/BTrees/TreeSetTemplate.c 2009-08-27 20:17:28 UTC (rev 103320)
+++ ZODB/trunk/src/BTrees/TreeSetTemplate.c 2009-08-27 20:46:38 UTC (rev 103321)
@@ -147,8 +147,11 @@
{"clear", (PyCFunction) BTree_clear, METH_NOARGS,
"clear()\n\nRemove all of the items from the BTree."},
+ {"add", (PyCFunction)TreeSet_insert, METH_VARARGS,
+ "add(id) -- Add an item to the set"},
+
{"insert", (PyCFunction)TreeSet_insert, METH_VARARGS,
- "insert(id,[ignored]) -- Add an id to the set"},
+ "insert(id) -- Add an item to the set"},
{"update", (PyCFunction)TreeSet_update, METH_VARARGS,
"update(collection)\n\n Add the items from the given collection."},
Modified: ZODB/trunk/src/BTrees/tests/testBTrees.py
===================================================================
--- ZODB/trunk/src/BTrees/tests/testBTrees.py 2009-08-27 20:17:28 UTC (rev 103320)
+++ ZODB/trunk/src/BTrees/tests/testBTrees.py 2009-08-27 20:46:38 UTC (rev 103321)
@@ -697,11 +697,13 @@
def testInsertReturnsValue(self):
t = self.t
self.assertEqual(t.insert(5) , 1)
+ self.assertEqual(t.add(4) , 1)
def testDuplicateInsert(self):
t = self.t
t.insert(5)
self.assertEqual(t.insert(5) , 0)
+ self.assertEqual(t.add(5) , 0)
def testInsert(self):
t = self.t
@@ -1089,7 +1091,8 @@
for x in delete_order:
try: del self.t[x]
except KeyError:
- if self.t.has_key(x): self.assertEqual(1,2,"failed to delete %s" % x)
+ if self.t.has_key(x):
+ self.assertEqual(1,2,"failed to delete %s" % x)
def testRangeSearchAfterSequentialInsert(self):
r = range(100)
@@ -1783,7 +1786,61 @@
self.failUnless(f1 is family)
self.failUnless(f2 is family)
+class InternalKeysMappingTest(TestCase):
+ """There must not be any internal keys not in the BTree
+ """
+ def add_key(self, tree, key):
+ tree[key] = key
+
+ def test_internal_keys_after_deletion(self):
+ """Make sure when a key's deleted, it's not an internal key
+
+ We'll leverage __getstate__ to introspect the internal structures.
+
+ We need to check BTrees with BTree children as well as BTrees
+ with bucket children.
+ """
+
+ tree = self.t_class()
+ i = 0
+
+ # Grow the btree until we have multiple buckets
+ while 1:
+ i += 1
+ self.add_key(tree, i)
+ data = tree.__getstate__()[0]
+ if len(data) >= 3:
+ break
+
+ # Now, delete the internal key and make sure it's really gone
+ key = data[1]
+ del tree[key]
+ data = tree.__getstate__()[0]
+ self.assert_(data[1] != key)
+
+ # Grow the btree until we have multiple levels
+ while 1:
+ i += 1
+ self.add_key(tree, i)
+ data = tree.__getstate__()[0]
+ if data[0].__class__ == tree.__class__:
+ assert len(data[2].__getstate__()[0]) >= 3
+ break
+
+ # Now, delete the internal key and make sure it's really gone
+ key = data[1]
+ del tree[key]
+ data = tree.__getstate__()[0]
+ self.assert_(data[1] != key)
+
+class InternalKeysSetTest:
+ """There must not be any internal keys not in the TreeSet
+ """
+
+ def add_key(self, tree, key):
+ tree.add(key)
+
def test_suite():
s = TestSuite()
@@ -1791,13 +1848,27 @@
'II', 'IO', 'OI', 'IF',
'LL', 'LO', 'OL', 'LF',
):
- for name, bases in (('Bucket', (MappingBase,)),
- ('TreeSet', (NormalSetTests,)),
- ('Set', (ExtendedSetTests,)),
- ):
+ for name, bases in (
+ ('BTree', (InternalKeysMappingTest,)),
+ ('TreeSet', (InternalKeysSetTest,)),
+ ):
+ klass = ClassType(kv + name + 'InternalKeyTest', bases,
+ dict(t_class=globals()[kv+name]))
+ s.addTest(makeSuite(klass))
+
+ for kv in ('OO',
+ 'II', 'IO', 'OI', 'IF',
+ 'LL', 'LO', 'OL', 'LF',
+ ):
+ for name, bases in (
+ ('Bucket', (MappingBase,)),
+ ('TreeSet', (NormalSetTests,)),
+ ('Set', (ExtendedSetTests,)),
+ ):
klass = ClassType(kv + name + 'Test', bases,
dict(t_class=globals()[kv+name]))
s.addTest(makeSuite(klass))
+
for kv, iface in (
('OO', BTrees.Interfaces.IObjectObjectBTreeModule),
('IO', BTrees.Interfaces.IIntegerObjectBTreeModule),
Modified: ZODB/trunk/src/BTrees/tests/testConflict.py
===================================================================
--- ZODB/trunk/src/BTrees/tests/testConflict.py 2009-08-27 20:17:28 UTC (rev 103320)
+++ ZODB/trunk/src/BTrees/tests/testConflict.py 2009-08-27 20:46:38 UTC (rev 103321)
@@ -502,7 +502,7 @@
# The next block is still verifying preconditions.
self.assertEqual(len(state) , 2)
self.assertEqual(len(state[0]), 5)
- self.assertEqual(state[0][1], 60)
+ self.assertEqual(state[0][1], 92)
self.assertEqual(state[0][3], 120)
tm1.commit()
Modified: ZODB/trunk/src/CHANGES.txt
===================================================================
--- ZODB/trunk/src/CHANGES.txt 2009-08-27 20:17:28 UTC (rev 103320)
+++ ZODB/trunk/src/CHANGES.txt 2009-08-27 20:46:38 UTC (rev 103321)
@@ -2,12 +2,25 @@
Change History
================
-3.9.0c1 (2009-08-??)
+3.9.0c2 (2009-08-??)
====================
Bugs Fixed
----------
+- BTrees (and TreeSets) kept references to internal keys.
+ https://bugs.launchpad.net/zope3/+bug/294788
+
+- BTree Sets and TreeSets don't support the standard set add method.
+ (Now either add or the original insert method can be used to add an
+ object to a BTree-based set.)
+
+3.9.0c1 (2009-08-26)
+====================
+
+Bugs Fixed
+----------
+
- The runzeo script didn't work without a configuration file.
(https://bugs.launchpad.net/zodb/+bug/410571)
More information about the Zodb-checkins
mailing list