[issue16991] Add OrderedDict written in C

[Eric Snow]

Eric Snow added the comment:

Here's an updated patch.  I still have some ref-counting issues, but the patch is much closer to what I expect will be the final version.  At this point it passes all the main unit tests (segfaults in some of the supplemental Mapping tests).

One key thing is that for now the various iterators are faked using lists.  Once everything is sorted out I'll plug my implementation of the iterators back in (which I'd already mostly finished).

I see room for efficiency improvements in a couple spots.  As well, I plan on improving the subclass-ability of the type once it's otherwise happy.

Any feedback at the point would be helpful.  Regardless, I'm being careful to get this right and I'm no expert with the C-API, so it's taking a while.  :)

Some other considerations:

   * ensure that __init__() can reset and populate an existing dictionary:
             d=OrderedDict(); d[0]=1; d.__init__() # resets
   * avoid any reference cycles so that dicts can clean-up right-away when their ref-count drops to zero
     rather than waiting on GC.
   * possibly use the GIL to make the link updates atomic, trying to make the overall class thread safe.
   * methods like get() pop() or setdefault() shouldn't rely on __getitem__ raising KeyError
     because __missing__ may be present in a subclass

----------
Added file: http://bugs.python.org/file28956/odict.diff

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue16991>
_______________________________________