[issue31265] Remove doubly-linked list from C OrderedDict

[INADA Naoki]

INADA Naoki added the comment:

> Original Raymond's design didn't preserve ordering during deletion.

Original Raymond's pure Python implementation rebuilds index table.
Without it, proving can be very long or infinite loop.
See L89-92 in http://code.activestate.com/recipes/578375/
Strictly speaking, it's worst case is O(n) too.

Raymond's compact dict allocates entry table and index table separately.
I want to allocate them at once, as one memory block.
It makes better cache hit ratio on small dict.

That's why I choose "preserve insertion order" over "compaction".
Since index table and entry table grow at same time, rebuilding
index table and entry table at once makes sense to me.

Anyway, "namespace is ordered" is Python's language spec now.

class C:
    a = 1
    b = 2
    c = 3
    del a

In this case, C's namespace should {"b": 2, "c": 3}, not {"c": 3, "b": 2}.

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue31265>
_______________________________________