[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <CABh_MKkP+AC2wr=StEvtHXQarV7n1YzL+bb4UWimDDmPCHiygg@mail.gmail.com>
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.
