for the record, my ole32 binary tree search patch is correct

Yuriy Kaminskiy yumkam at
Tue Oct 27 22:06:13 CDT 2009

On 27.10.2009 22:50, Vincent Povirk wrote:
> I sent the following patch recently:
> commit ee6856d874d687c4504914e61bcde3e6b8823bca
> Author: Vincent Povirk <madewokherd at>
> Date:   Fri Oct 23 13:57:42 2009 -0500
>     ole32: Don't use IEnumSTATSTG to search for elements of storages.
>     We use it to do a linear search of a binary tree, which is overkill.
>     Replace it with a simple binary search.
> It was accepted and caused this bug:
> It actually turned out that the mistake was in a previous patch, but
> it didn't matter for reading files until we started to depend on the
> tree to be valid. Nonetheless, I've done a test to make sure we can
> really rely on the binary trees in storage files to be valid.
> This means that Windows does depend on the tree in a storage file to
> be correct, and Wine's behavior is now closer to Windows, even though
> it now fails in some cases when it used to succeed.

If I've not mistaken, that uses lstricmp internally for comparing keys.

Note, that wine lstr[i]cmp and ms windows lstr[i]cmp uses different sort order
(see last [disabled] test in dlls/kernel32/tests/locale.c).

So binary search using wine lstricmp on presored array (used windows lstricmp)
will certainly fail on some files.

PS looking at code one more time, current code seems already depends on
"lstricmp working same" [in updatePropertyChain()], so already broken. It's pure
luck that it is not failed already.

Disclaimer: I'm not expert in wine code, looked at code very quickly, and may be
misread something :-\

More information about the wine-devel mailing list