Author: Maciej Fijalkowski <fij...@gmail.com>
Branch: rdict-experiments-2
Changeset: r59816:290adf4d1f44
Date: 2013-01-06 22:14 +0200
http://bitbucket.org/pypy/pypy/changeset/290adf4d1f44/
Log: finish tests
diff --git a/pypy/rpython/lltypesystem/llmemory.py
b/pypy/rpython/lltypesystem/llmemory.py
--- a/pypy/rpython/lltypesystem/llmemory.py
+++ b/pypy/rpython/lltypesystem/llmemory.py
@@ -90,6 +90,7 @@
try:
endmarker = _end_markers[parent]
except KeyError:
+ xxx
endmarker = _endmarker_struct(A, parent=parent,
parentindex=index)
_end_markers[parent] = endmarker
diff --git a/pypy/rpython/lltypesystem/rdict.py
b/pypy/rpython/lltypesystem/rdict.py
--- a/pypy/rpython/lltypesystem/rdict.py
+++ b/pypy/rpython/lltypesystem/rdict.py
@@ -3,6 +3,7 @@
from pypy.rpython.rdict import (AbstractDictRepr, AbstractDictIteratorRepr,
rtype_newdict)
from pypy.rpython.lltypesystem import lltype
+from pypy.rpython.lltypesystem.lloperation import llop
from pypy.rlib import objectmodel, jit, rgc
from pypy.rlib.debug import ll_assert
from pypy.rlib.rarithmetic import r_uint, intmask, LONG_BIT
@@ -154,6 +155,8 @@
ll_hash_function=self.key_repr.get_ll_hash_function(),
ll_eq_function=self.key_repr.get_ll_eq_function(),
get_custom_eq_hash=self.custom_eq_hash)
+ if self.custom_eq_hash is not None:
+ self.r_rdict_eqfn, self.r_rdict_hashfn = self.custom_eq_hash()
def convert_const(self, dictobj):
from pypy.rpython.lltypesystem import llmemory
@@ -366,7 +369,8 @@
def ll_dict_setitem(d, key, value):
hash = d.keyhash(key)
i = ll_dict_lookup(d, key, hash)
- return _ll_dict_setitem_lookup_done(d, key, value, hash, i)
+ res = _ll_dict_setitem_lookup_done(d, key, value, hash, i)
+ return res
def _look_inside_setitem(d, key, value, hash, i):
return jit.isvirtual(d) and jit.isconstant(key)
@@ -392,6 +396,7 @@
entry = d.entries[index]
rc = d.resize_counter - 1
ll_assert(rc > 0, "ll_dict_resize failed?")
+ ll_assert(index < len(d.entries), "invalid insert")
d.resize_counter = rc
d.indexes[i] = index
entry.value = value
@@ -419,14 +424,13 @@
@jit.look_inside_iff(lambda d, i: jit.isvirtual(d) and jit.isconstant(i))
def _ll_dict_del(d, i):
index = d.indexes[i]
- d.indexes[i] = DELETED
- d.num_items -= 1
ENTRIES = lltype.typeOf(d.entries).TO
ENTRY = ENTRIES.OF
- if index != d.num_items:
- old_entry = d.entries[d.num_items]
+ if index != d.num_items - 1:
+ old_entry = d.entries[d.num_items - 1]
key = old_entry.key
to_insert_i = ll_dict_lookup(d, key, d.keyhash(key))
+ ll_assert(not to_insert_i & HIGHEST_BIT, "invalid entry")
d.indexes[to_insert_i] = index
# copy the value
new_entry = d.entries[index]
@@ -435,6 +439,8 @@
if hasattr(ENTRY, 'f_hash'):
new_entry.f_hash = old_entry.f_hash
# clear the key and the value if they are GC pointers
+ d.indexes[i] = DELETED
+ d.num_items -= 1
entry = d.entries[d.num_items]
if ENTRIES.must_clear_key:
entry.key = lltype.nullptr(ENTRY.key.TO)
@@ -471,8 +477,7 @@
new_item_size = new_size // 3 * 2 + 1
d.entries = lltype.typeOf(old_entries).TO.allocate(new_item_size)
d.indexes = lltype.typeOf(d).TO.indexes.TO.allocate(new_size)
- d.num_items = len(old_entries) - 1
- d.resize_counter = new_item_size
+ d.resize_counter = new_item_size - d.num_items
i = 0
indexes = d.indexes
while i < old_size:
@@ -480,7 +485,8 @@
if index >= 0:
indexes[ll_dict_lookup_clean(d, old_entries.hash(index))] = index
i += 1
- rgc.ll_arraycopy(old_entries, d.entries, 0, 0, len(old_entries))
+ rgc.ll_arraycopy(old_entries, d.entries, 0, 0, min(len(old_entries),
+ len(d.entries)))
ll_dict_resize.oopspec = 'dict.resize(d)'
# ------- a port of CPython's dictobject.c's lookdict implementation -------
@@ -535,7 +541,7 @@
elif index >= 0:
checkingkey = entries[index].key
if checkingkey == key:
- return index
+ return i
if d.keyeq is not None and entries.hash(index) == hash:
# correct hash, maybe the key is e.g. a different pointer to
# an equal object
@@ -710,24 +716,17 @@
return default
def ll_copy(dict):
- xxx
DICT = lltype.typeOf(dict).TO
dictsize = len(dict.entries)
d = DICT.allocate()
- d.entries = DICT.entries.TO.allocate(dictsize)
+ d.entries = lltype.malloc(DICT.entries.TO, dictsize)
+ d.indexes = DICT.indexes.TO.allocate(len(dict.indexes))
d.num_items = dict.num_items
d.resize_counter = dict.resize_counter
if hasattr(DICT, 'fnkeyeq'): d.fnkeyeq = dict.fnkeyeq
if hasattr(DICT, 'fnkeyhash'): d.fnkeyhash = dict.fnkeyhash
- i = 0
- while i < dictsize:
- d_entry = d.entries[i]
- entry = dict.entries[i]
- ENTRY = lltype.typeOf(d.entries).TO.OF
- d_entry.key = entry.key
- d_entry.value = entry.value
- if hasattr(ENTRY, 'f_hash'): d_entry.f_hash = entry.f_hash
- i += 1
+ rgc.ll_arraycopy(dict.indexes, d.indexes, 0, 0, len(dict.indexes))
+ rgc.ll_arraycopy(dict.entries, d.entries, 0, 0, len(dict.entries))
return d
ll_copy.oopspec = 'dict.copy(dict)'
@@ -743,17 +742,15 @@
ll_clear.oopspec = 'dict.clear(d)'
def ll_update(dic1, dic2):
- xxx
entries = dic2.entries
- d2len = len(entries)
+ d2len = dic2.num_items
i = 0
while i < d2len:
- if entries.valid(i):
- entry = entries[i]
- hash = entries.hash(i)
- key = entry.key
- j = ll_dict_lookup(dic1, key, hash)
- _ll_dict_setitem_lookup_done(dic1, key, entry.value, hash, j)
+ entry = entries[i]
+ hash = entries.hash(i)
+ key = entry.key
+ j = ll_dict_lookup(dic1, key, hash)
+ _ll_dict_setitem_lookup_done(dic1, key, entry.value, hash, j)
i += 1
ll_update.oopspec = 'dict.update(dic1, dic2)'
@@ -772,27 +769,23 @@
def ll_kvi(LIST, dic):
res = LIST.ll_newlist(dic.num_items)
entries = dic.entries
- dlen = len(entries)
+ dlen = dic.num_items
items = res.ll_items()
i = 0
- p = 0
while i < dlen:
- if entries.valid(i):
- ELEM = lltype.typeOf(items).TO.OF
- if ELEM is not lltype.Void:
- entry = entries[i]
- if kind == 'items':
- r = lltype.malloc(ELEM.TO)
- r.item0 = recast(ELEM.TO.item0, entry.key)
- r.item1 = recast(ELEM.TO.item1, entry.value)
- items[p] = r
- elif kind == 'keys':
- items[p] = recast(ELEM, entry.key)
- elif kind == 'values':
- items[p] = recast(ELEM, entry.value)
- p += 1
+ ELEM = lltype.typeOf(items).TO.OF
+ if ELEM is not lltype.Void:
+ entry = entries[i]
+ if kind == 'items':
+ r = lltype.malloc(ELEM.TO)
+ r.item0 = recast(ELEM.TO.item0, entry.key)
+ r.item1 = recast(ELEM.TO.item1, entry.value)
+ items[i] = r
+ elif kind == 'keys':
+ items[i] = recast(ELEM, entry.key)
+ elif kind == 'values':
+ items[i] = recast(ELEM, entry.value)
i += 1
- assert p == res.ll_length()
return res
ll_kvi.oopspec = 'dict.%s(dic)' % kind
return ll_kvi
@@ -805,40 +798,14 @@
i = ll_dict_lookup(d, key, d.keyhash(key))
return not i & HIGHEST_BIT
-POPITEMINDEX = lltype.Struct('PopItemIndex', ('nextindex', lltype.Signed))
-global_popitem_index = lltype.malloc(POPITEMINDEX, zero=True, immortal=True)
-
-def _ll_getnextitem(dic):
- entries = dic.entries
- ENTRY = lltype.typeOf(entries).TO.OF
- dmask = len(entries) - 1
- if hasattr(ENTRY, 'f_hash'):
- if entries.valid(0):
- return 0
- base = entries[0].f_hash
- else:
- base = global_popitem_index.nextindex
- counter = 0
- while counter <= dmask:
- i = (base + counter) & dmask
- counter += 1
- if entries.valid(i):
- break
- else:
+def ll_popitem(ELEM, dic):
+ if dic.num_items == 0:
raise KeyError
- if hasattr(ENTRY, 'f_hash'):
- entries[0].f_hash = base + counter
- else:
- global_popitem_index.nextindex = base + counter
- return i
-
-def ll_popitem(ELEM, dic):
- i = _ll_getnextitem(dic)
- entry = dic.entries[i]
+ entry = dic.entries[dic.num_items - 1]
r = lltype.malloc(ELEM.TO)
r.item0 = recast(ELEM.TO.item0, entry.key)
r.item1 = recast(ELEM.TO.item1, entry.value)
- _ll_dict_del(dic, i)
+ ll_dict_delitem(dic, entry.key)
return r
def ll_pop(dic, key):
diff --git a/pypy/rpython/test/test_rdict.py b/pypy/rpython/test/test_rdict.py
--- a/pypy/rpython/test/test_rdict.py
+++ b/pypy/rpython/test/test_rdict.py
@@ -91,6 +91,33 @@
assert hlstr(next) == "j"
py.test.raises(StopIteration, ll_iterkeys, lltype.Signed, ll_iter)
+ def test_popitem(self):
+ DICT = self._get_str_dict()
+ ll_d = rdict.ll_newdict(DICT)
+ rdict.ll_dict_setitem(ll_d, llstr("k"), 1)
+ rdict.ll_dict_setitem(ll_d, llstr("j"), 2)
+ ll_elem = rdict.ll_popitem(lltype.Ptr(
+ lltype.GcStruct('x', ('item0', lltype.Ptr(rstr.STR)),
+ ('item1', lltype.Signed))), ll_d)
+ assert hlstr(ll_elem.item0) == "j"
+ assert ll_elem.item1 == 2
+
+ def test_direct_enter_and_del(self):
+ def eq(a, b):
+ return a == b
+
+ DICT = rdict.get_ll_dict(lltype.Signed, lltype.Signed,
+ ll_fasthash_function=intmask,
+ ll_hash_function=intmask,
+ ll_eq_function=eq)
+ ll_d = rdict.ll_newdict(DICT)
+ numbers = [i * rdict.DICT_INITSIZE + 1 for i in range(8)]
+ for num in numbers:
+ rdict.ll_dict_setitem(ll_d, num, 1)
+ rdict.ll_dict_delitem(ll_d, num)
+ for k in ll_d.indexes:
+ assert k < 0
+
class BaseTestRdict(BaseRtypingTest):
def test_dict_creation(self):
@@ -258,12 +285,12 @@
res = self.interpret(f, ())
assert res == 2
- def f():
+ def f2():
d = {}
d.setdefault('a', 2)
x = d.setdefault('a', -3)
return x
- res = self.interpret(f, ())
+ res = self.interpret(f2, ())
assert res == 2
def test_dict_copy(self):
@@ -802,8 +829,7 @@
return d
res = self.interpret(func2, [ord(x), ord(y)])
- for i in range(len(res.entries)):
- assert not (res.entries.everused(i) and not res.entries.valid(i))
+ assert len([i for i in res.indexes if i >= 0]) == 2
def func3(c0, c1, c2, c3, c4, c5, c6, c7):
d = {}
@@ -822,8 +848,8 @@
res = self.interpret(func3, [ord(char_by_hash[i][0])
for i in range(rdict.DICT_INITSIZE)])
count_frees = 0
- for i in range(len(res.entries)):
- if not res.entries.everused(i):
+ for i in res.indexes:
+ if i == -1:
count_frees += 1
assert count_frees >= 3
@@ -844,9 +870,9 @@
del d[chr(ord('A') - i)]
return d
res = self.interpret(func, [0])
- assert len(res.entries) > rdict.DICT_INITSIZE
+ assert len(res.indexes) > rdict.DICT_INITSIZE
res = self.interpret(func, [1])
- assert len(res.entries) == rdict.DICT_INITSIZE
+ assert len(res.indexes) == rdict.DICT_INITSIZE
def test_dict_valid_resize(self):
# see if we find our keys after resize
@@ -864,87 +890,6 @@
# ____________________________________________________________
- def test_opt_nullkeymarker(self):
- def f():
- d = {"hello": None}
- d["world"] = None
- return "hello" in d, d
- res = self.interpret(f, [])
- assert res.item0 == True
- DICT = lltype.typeOf(res.item1).TO
- assert not hasattr(DICT.entries.TO.OF, 'f_everused')# non-None string
keys
- assert not hasattr(DICT.entries.TO.OF, 'f_valid') # strings have a
dummy
-
- def test_opt_nullvaluemarker(self):
- def f(n):
- d = {-5: "abcd"}
- d[123] = "def"
- return len(d[n]), d
- res = self.interpret(f, [-5])
- assert res.item0 == 4
- DICT = lltype.typeOf(res.item1).TO
- assert not hasattr(DICT.entries.TO.OF, 'f_everused')# non-None str
values
- assert not hasattr(DICT.entries.TO.OF, 'f_valid') # strs have a dummy
-
- def test_opt_nonullmarker(self):
- class A:
- pass
- def f(n):
- if n > 5:
- a = A()
- else:
- a = None
- d = {a: -5441}
- d[A()] = n+9872
- return d[a], d
- res = self.interpret(f, [-5])
- assert res.item0 == -5441
- DICT = lltype.typeOf(res.item1).TO
- assert hasattr(DICT.entries.TO.OF, 'f_everused') # can-be-None A
instances
- assert not hasattr(DICT.entries.TO.OF, 'f_valid')# with a dummy A
instance
-
- res = self.interpret(f, [6])
- assert res.item0 == -5441
-
- def test_opt_nonnegint_dummy(self):
- def f(n):
- d = {n: 12}
- d[-87] = 24
- del d[n]
- return len(d.copy()), d[-87], d
- res = self.interpret(f, [5])
- assert res.item0 == 1
- assert res.item1 == 24
- DICT = lltype.typeOf(res.item2).TO
- assert hasattr(DICT.entries.TO.OF, 'f_everused') # all ints can be zero
- assert not hasattr(DICT.entries.TO.OF, 'f_valid')# nonneg int: dummy -1
-
- def test_opt_no_dummy(self):
- def f(n):
- d = {n: 12}
- d[-87] = -24
- del d[n]
- return len(d.copy()), d[-87], d
- res = self.interpret(f, [5])
- assert res.item0 == 1
- assert res.item1 == -24
- DICT = lltype.typeOf(res.item2).TO
- assert hasattr(DICT.entries.TO.OF, 'f_everused') # all ints can be zero
- assert hasattr(DICT.entries.TO.OF, 'f_valid') # no dummy available
-
- def test_opt_boolean_has_no_dummy(self):
- def f(n):
- d = {n: True}
- d[-87] = True
- del d[n]
- return len(d.copy()), d[-87], d
- res = self.interpret(f, [5])
- assert res.item0 == 1
- assert res.item1 is True
- DICT = lltype.typeOf(res.item2).TO
- assert hasattr(DICT.entries.TO.OF, 'f_everused') # all ints can be zero
- assert hasattr(DICT.entries.TO.OF, 'f_valid') # no dummy available
-
def test_opt_multiple_identical_dicts(self):
def f(n):
s = "x" * n
@@ -1159,7 +1104,7 @@
DictValue(None, annmodel.SomeString(value_can_be_none)))
dictrepr.setup()
print dictrepr.lowleveltype
- for key, value in dictrepr.DICTENTRY._adtmeths.items():
+ for key, value in dictrepr.DICT.entries.TO._adtmeths.items():
print ' %s = %s' % (key, value)
l_dict = rdict.ll_newdict(dictrepr.DICT)
referencetable = [None] * 400
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
http://mail.python.org/mailman/listinfo/pypy-commit
