Author: Armin Rigo <ar...@tunes.org>
Branch: rpython-hash
Changeset: r89794:eaa33d328249
Date: 2017-01-26 22:05 +0100
http://bitbucket.org/pypy/pypy/changeset/eaa33d328249/
Log: Tweaks, possibly fix a bug
diff --git a/rpython/rtyper/lltypesystem/rordereddict.py
b/rpython/rtyper/lltypesystem/rordereddict.py
--- a/rpython/rtyper/lltypesystem/rordereddict.py
+++ b/rpython/rtyper/lltypesystem/rordereddict.py
@@ -642,19 +642,17 @@
except:
ll_remove_index(d)
raise
- rc = d.resize_counter - 3
- if rc <= 0:
+ if d.resize_counter <= 3:
try:
ll_dict_resize(d)
reindexed = True
except:
ll_remove_index(d)
raise
- rc = d.resize_counter - 3
- ll_assert(rc > 0, "ll_dict_resize failed?")
if reindexed:
ll_call_insert_clean_function(d, hash, d.num_ever_used_items)
- #
+ rc = d.resize_counter - 3
+ ll_assert(rc > 0, "ll_dict_resize failed?")
d.resize_counter = rc
entry = d.entries[d.num_ever_used_items]
entry.key = key
@@ -799,7 +797,7 @@
# then maybe it is a better idea to keep it instead of reallocating
# an identical index very soon. In this case we update the index now.
if bool(d.indexes):
- new_estimate = d.num_live_items * 2
+ new_estimate = d.num_live_items * 2
new_size = DICT_INITSIZE
while new_size <= new_estimate:
new_size *= 2
@@ -842,12 +840,13 @@
# also possible that there are more dead items immediately behind the
# last one, we reclaim all the dead items at the end of the ordereditem
# at the same point.
- i = d.num_ever_used_items - 2
- while i >= 0 and not d.entries.valid(i):
+ i = index
+ while True:
i -= 1
- j = i + 1
- assert j >= 0
- d.num_ever_used_items = j
+ assert i >= 0
+ if d.entries.valid(i): # must be at least one
+ break
+ d.num_ever_used_items = i + 1
# If the dictionary is more than 75% dead items, then clean up the
# deleted items and remove the index.
@@ -1065,7 +1064,6 @@
ll_remove_index(d)
d.num_live_items = 0
d.num_ever_used_items = 0
- d.resize_counter = DICT_INITSIZE * 2
return d
OrderedDictRepr.ll_newdict = staticmethod(ll_newdict)
@@ -1232,7 +1230,6 @@
ll_remove_index(d)
d.num_live_items = 0
d.num_ever_used_items = 0
- d.resize_counter = DICT_INITSIZE * 2
# old_entries.delete() XXX
ll_dict_clear.oopspec = 'odict.clear(d)'
diff --git a/rpython/rtyper/test/test_rdict.py
b/rpython/rtyper/test/test_rdict.py
--- a/rpython/rtyper/test/test_rdict.py
+++ b/rpython/rtyper/test/test_rdict.py
@@ -1170,6 +1170,7 @@
self.reference = self.new_reference()
self.ll_key = r_key.convert_const
self.ll_value = r_value.convert_const
+ self.removed_keys = []
r_tuple = TupleRepr(rtyper, [r_key, r_value])
self.TUPLE = r_tuple.lowleveltype
@@ -1185,6 +1186,7 @@
self.ll_delitem(self.l_dict, ll_key)
del self.reference[key]
assert not self.ll_contains(self.l_dict, ll_key)
+ self.removed_keys.append(key)
def copydict(self):
self.l_dict = self.ll_copy(self.l_dict)
@@ -1192,6 +1194,8 @@
def cleardict(self):
self.ll_clear(self.l_dict)
+ for key in self.reference:
+ self.removed_keys.append(key)
self.reference.clear()
assert self.ll_len(self.l_dict) == 0
@@ -1207,15 +1211,27 @@
if self.ll_key(key) == ll_key:
assert self.ll_value(value) == ll_value
del self.reference[key]
+ self.removed_keys.append(key)
break
else:
raise AssertionError("popitem() returned unexpected key")
+ def removeindex(self):
+ pass # overridden in test_rordereddict
+
def fullcheck(self):
assert self.ll_len(self.l_dict) == len(self.reference)
for key, value in self.reference.iteritems():
assert (self.ll_getitem(self.l_dict, self.ll_key(key)) ==
self.ll_value(value))
+ for key in self.removed_keys:
+ if key not in self.reference:
+ try:
+ self.ll_getitem(self.l_dict, self.ll_key(key))
+ except KeyError:
+ pass
+ else:
+ raise AssertionError("removed key still shows up")
class MappingSM(GenericStateMachine):
def __init__(self):
@@ -1238,7 +1254,7 @@
if not self.space:
return builds(Action, just('setup'), tuples(st_keys, st_values))
global_actions = [Action('copydict', ()), Action('cleardict', ()),
- Action('popitem', ())]
+ Action('popitem', ()), Action('removeindex', ())]
if self.space.reference:
return (
self.st_setitem() | sampled_from(global_actions) |
diff --git a/rpython/rtyper/test/test_rordereddict.py
b/rpython/rtyper/test/test_rordereddict.py
--- a/rpython/rtyper/test/test_rordereddict.py
+++ b/rpython/rtyper/test/test_rordereddict.py
@@ -202,14 +202,17 @@
assert ll_d.num_ever_used_items == 0
assert ll_d.lookup_function_no == rordereddict.FUNC_BYTE # reset
- def test_direct_enter_and_del(self):
+ def _get_int_dict(self):
def eq(a, b):
return a == b
- DICT = rordereddict.get_ll_dict(lltype.Signed, lltype.Signed,
+ return rordereddict.get_ll_dict(lltype.Signed, lltype.Signed,
ll_fasthash_function=intmask,
ll_hash_function=intmask,
ll_eq_function=eq)
+
+ def test_direct_enter_and_del(self):
+ DICT = self._get_int_dict()
ll_d = rordereddict.ll_newdict(DICT)
numbers = [i * rordereddict.DICT_INITSIZE + 1 for i in range(8)]
for num in numbers:
@@ -303,6 +306,38 @@
rordereddict.ll_prepare_dict_update(ll_d, 7)
# used to get UninitializedMemoryAccess
+ def test_bug_resize_counter(self):
+ DICT = self._get_int_dict()
+ ll_d = rordereddict.ll_newdict(DICT)
+ rordereddict.ll_dict_setitem(ll_d, 0, 0)
+ rordereddict.ll_dict_delitem(ll_d, 0)
+ rordereddict.ll_dict_setitem(ll_d, 0, 0)
+ rordereddict.ll_dict_delitem(ll_d, 0)
+ rordereddict.ll_dict_setitem(ll_d, 0, 0)
+ rordereddict.ll_dict_delitem(ll_d, 0)
+ rordereddict.ll_dict_setitem(ll_d, 0, 0)
+ rordereddict.ll_dict_delitem(ll_d, 0)
+ rordereddict.ll_dict_setitem(ll_d, 1, 0)
+ rordereddict.ll_dict_setitem(ll_d, 0, 0)
+ rordereddict.ll_dict_setitem(ll_d, 2, 0)
+ rordereddict.ll_dict_delitem(ll_d, 1)
+ rordereddict.ll_dict_delitem(ll_d, 0)
+ rordereddict.ll_dict_delitem(ll_d, 2)
+ rordereddict.ll_dict_setitem(ll_d, 0, 0)
+ rordereddict.ll_dict_delitem(ll_d, 0)
+ rordereddict.ll_dict_setitem(ll_d, 0, 0)
+ rordereddict.ll_dict_delitem(ll_d, 0)
+ rordereddict.ll_dict_setitem(ll_d, 0, 0)
+ rordereddict.ll_dict_setitem(ll_d, 1, 0)
+ d = ll_d
+ idx = d.indexes._obj.container
+ num_nonfrees = 0
+ for i in range(idx.getlength()):
+ got = idx.getitem(i) # 0: unused; 1: deleted
+ num_nonfrees += (got > 0)
+ assert d.resize_counter <= idx.getlength() * 2 - num_nonfrees * 3
+
+
class TestRDictDirectDummyKey(TestRDictDirect):
class dummykeyobj:
ll_dummy_value = llstr("dupa")
@@ -377,6 +412,12 @@
key, value = self.reference.popitem()
assert self.ll_key(key) == ll_key
assert self.ll_value(value) == ll_value
+ self.removed_keys.append(key)
+
+ def removeindex(self):
+ # remove the index, as done e.g. during translation for prebuilt
+ # dicts
+ rodct.ll_remove_index(self.l_dict)
def fullcheck(self):
# overridden to also check key order
@@ -387,6 +428,35 @@
assert self.ll_key(key) == ll_key
assert (self.ll_getitem(self.l_dict, self.ll_key(key)) ==
self.ll_value(self.reference[key]))
+ for key in self.removed_keys:
+ if key not in self.reference:
+ try:
+ self.ll_getitem(self.l_dict, self.ll_key(key))
+ except KeyError:
+ pass
+ else:
+ raise AssertionError("removed key still shows up")
+ # check some internal invariants
+ d = self.l_dict
+ num_lives = 0
+ for i in range(d.num_ever_used_items):
+ if d.entries.valid(i):
+ num_lives += 1
+ assert num_lives == d.num_live_items
+ fun = d.lookup_function_no & rordereddict.FUNC_MASK
+ if fun == rordereddict.FUNC_NO_INDEX:
+ assert not d.indexes
+ else:
+ assert d.indexes
+ idx = d.indexes._obj.container
+ num_lives = 0
+ num_nonfrees = 0
+ for i in range(idx.getlength()):
+ got = idx.getitem(i) # 0: unused; 1: deleted
+ num_nonfrees += (got > 0)
+ num_lives += (got > 1)
+ assert num_lives == d.num_live_items
+ assert 0 < d.resize_counter <= idx.getlength()*2 - num_nonfrees*3
class ODictSM(MappingSM):
@@ -394,4 +464,4 @@
def test_hypothesis():
run_state_machine_as_test(
- ODictSM, settings(max_examples=50000, stateful_step_count=100))
+ ODictSM, settings(max_examples=500, stateful_step_count=100))
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
