[Python-Dev] [issue13703] Hash collision security issue (original) (raw)

Stefan Behnel stefan_ml at behnel.de
Fri Jan 27 10:49:08 CET 2012

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

More information about the Python-Dev mailing list