[Python-Dev] a feature i'd like to see in python #1: better iteration control

["Martin v. Löwis"]

Brian Harring schrieb:
>> I think this is incorrect. The implementation could well support it,
>> putting a dummy object into the deleted key (which deletion needs
>> to do, anyway).
> 
> The implementation already uses a sentinel (NULL)-

That' not the full truth. The implementation has a separate object
(called the dummy object, see dictobject.c:140 in the trunk) to
fill put in for deleted objects. You can't use NULL here because
then the open addressing would break. NULL is used as a sentinel
for the open addressing; the dummy object indicates that you have
to continue searching.

> point was that it 
> does not support iteration over a dict that's being deleted from 
> *currently* though.

Yes, but I believe that's out of fear that you have to do resizing;
iteration cannot be supported in the presence of resizing. Deletion
does not involve resizing, instead, ma_fill won't decrease during
deletion, so the next addition may trigger resizing if the fill
level goes above 2/3.

> One thing to note; delitem is the easy case.  Allowing for mutating 
> the mapping as you're iterating via delitem implies that setitem 
> should work also; setitem however can trigger a resize.

So that implication is wrong, no?

Of course, setitem for an existing key could be allowed; that's
also a meaningful operation while you are iterating over a
dictionary.

> Finally, if dicts were ever modified to shrink based on load, the 
> resize there would be an issue.  Mind you I've not seen proposals of 
> that sort, just pointing out the potential.

You'd have to defer the resizing while the dictionary is locked.

> In my opinion, no point in doing the deltitem modification without a 
> matching setitem.  Not saying I think the modification is worth it 
> mind you, just that there should be symmetry ;)

IMO, it is clear that this symmetry is *not* necessary, for the
reason that we are discussing: if iterators where to support a
delete operation, then it would be possible to provide that for
dict iterators. It wouldn't be necessary to support any other updates;
it wouldn't even be necessary to support del d[k], even if k is
the key returned from the iterator's .next().

Regards,
Martin