[Python-Dev] [issue13703] Hash collision security issue

[Stefan Behnel]

martin at v.loewis.de, 27.01.2012 09:55:
> So I found Ian Piumarta's AVL tree 1.0 from 2006. I trust Ian Piumarta
> to get it right (plus I reviewed the code a little). There are some
> API glitches (such as assuming a single comparison function, whereas
> it would better be rewritten to directly invoke rich comparison, or
> such as node removal not returning the node that was removed). It
> gets most API decisions right, in particular wrt. memory management.
> The license is in the style of the MIT license.

That sounds ok for internal use, and the implementation really looks short
enough to allow the adaptations you propose and generic enough to be
generally usable.

However, note that my comment on Glenn's question regarding a stdlib
addition of a tree type still applies - someone would have to write a
suitable CPython wrapper for it as well as a separate pure Python
implementation, and then offer both for inclusion and maintenance. I'm not
sure it's a good idea to have multiple C tree implementations in CPython,
i.e. one for internal use and one for the stdlib. Unless there's a serious
interest in maintaining both, that is. After all, writing a Python wrapper
for this may not be simpler than the work that went into one of the
existing (C)Python tree implementations already.

Stefan