Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Date: Sat, 5 Dec 2015 08:42:38 +0100
From: Ed Schouten <ed@...i.nl>
To: Ed Schouten <ed@...i.nl>, musl@...ts.openwall.com
Subject: Re: tdelete() may break the AVL tree balance property?

Hi Szabolcs,

2015-12-05 4:19 GMT+01:00 Szabolcs Nagy <nsz@...t70.net>:
> thanks for the report
> yes it's wrong (this code is from me)
> i attached a fix, but i'll have to
> look at it again tomorrow in case
> there is a better approach.

Though I haven't tested the patch personally, I think that is the
correct way to solve it indeed.

By the way, it should be possible to easily detect these kinds of
imbalances by looking at the value by delta(). It should always be
between [-2, +2]. I don't know what musl's policy on assertions is,
but it may be worth adding such a check to prevent this from
regressing.

Thanks,
-- 
Ed Schouten <ed@...i.nl>
Nuxi, 's-Hertogenbosch, the Netherlands
KvK-nr.: 62051717

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.