From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/8967 Path: news.gmane.org!not-for-mail From: Ed Schouten Newsgroups: gmane.linux.lib.musl.general Subject: Re: AVL tree: storing balances instead of heights Date: Mon, 7 Dec 2015 14:19:58 +0100 Message-ID: References: <20151207130344.GZ23362@port70.net> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 X-Trace: ger.gmane.org 1449494420 11782 80.91.229.3 (7 Dec 2015 13:20:20 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 7 Dec 2015 13:20:20 +0000 (UTC) To: Ed Schouten , musl@lists.openwall.com Original-X-From: musl-return-8980-gllmg-musl=m.gmane.org@lists.openwall.com Mon Dec 07 14:20:20 2015 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1a5viE-0008Dm-5I for gllmg-musl@m.gmane.org; Mon, 07 Dec 2015 14:20:18 +0100 Original-Received: (qmail 14291 invoked by uid 550); 7 Dec 2015 13:20:16 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 14206 invoked from network); 7 Dec 2015 13:20:10 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=nuxi-nl.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=WXHbHKWBxpwXc7vPb8BkeqEW0SuVdzzZEzMcc4k9jjE=; b=GJUTR13042I4mbiaXgDMnCvR4hmwYrQyvGJYmDwRFcMmvFsUgEYAuye1ib78w97kOw 6vmDcv8FCebsH4i38lDYEG7m3BLafF8JLH0EuojxPFaA25dx+5/i9qKC7l3alfQn1mHf 4dAM7mZbbcZLX2j/lYFe5rj6UYCeHGhGD09LhiqDJrpv70NzkRomQtdjqvtET3pUxtSd gyCP2koS0dV9ETf0+LPeMpopW56g1uBUUR4FkGfN897DqmLSOim8ISEHUc6tqQcgiXbm 3hdV+uwelnnjauszF+KXqk6A5+VW8CIg9o9Mm+D89aAREwRpYPSb5tEg3yCXABHWrp0D FJ9g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:content-type; bh=WXHbHKWBxpwXc7vPb8BkeqEW0SuVdzzZEzMcc4k9jjE=; b=PCSov31zZA5BgPnnxBbKghDR664IS5T5WvWGG4U8IlPzL0q6c+opoRMx3R+Y+1uhxT AismwFAU9RZHDZNOfYB3rw8nBr19ytXm9ni/uh7ps8X8up+TlENzq+EVT8lg5KwpUxam FKMchZ8i75Mg+bhDsLWYgVWFlF/lxs/OvPTJD7gFTfJ+l9SO+D37QeDNILMXM2IqMR2X Ge7QyLukAwIEWRS5npqQHQm1nbYH3cEmCwU6qLw5Sg/3duuCz4/7tZuNOzbMNqX37wJK EtLkBEMqTxUraTyWaAnak9nyhcGACOi7f5vNs/si+WohRspuPbtNQIhdPACl9wdLJ3Fm ykBg== X-Gm-Message-State: ALoCoQldjJbuld2EaeR7TbRfLyg7GvpZsMjYwMX4zp9+niW5QkrJ8LYTleYJKGdDqLstA67Lr2aH X-Received: by 10.13.255.70 with SMTP id p67mr22294000ywf.31.1449494398512; Mon, 07 Dec 2015 05:19:58 -0800 (PST) In-Reply-To: <20151207130344.GZ23362@port70.net> Xref: news.gmane.org gmane.linux.lib.musl.general:8967 Archived-At: Hi Szabolcs, 2015-12-07 14:03 GMT+01:00 Szabolcs Nagy : > i think the macro definitions for inlining twalk and tfind > are not justified. I personally think it is justified in this case. In trivial cases it may even mean that the compare function is inlined into the body of twalk()/tfind(). I haven't measured this for twalk() and tfind() explicitly, but my observation for bsearch() was that a separate compare function and an invocation of bsearch() is about the same size as inlining the bsearch() routine. > you got the rootp==0 case wrong too (posix requires that to > return 0). That already happens, right? tdelete() sets it to (void *)1, but tdelete_recurse() then sets it to NULL immediately. > and the (T**) cast is invalid in > > void *tdelete(const void *restrict key, void **restrict rootp, > int (*compar)(const void *, const void *)) { > void *result = (void *)1; > tdelete_recurse(key, (struct __tnode **)rootp, compar, &result); > return result; > } Could you please elaborate this a bit further? > posix specifies to return a pointer to a node, not to an element > pointer, i think that's a bug in posix (otherwise the api would > be useless). Yes. On lines 40 and 44 the result pointer is set to the parent object. As __key is the first member of the structure, I could have written *n instead of &(*n)->__key, but this implementation does not strongly enforce it. I could put __key anywhere in the node structure and it would always return a pointer to a pointer to a key. -- Ed Schouten Nuxi, 's-Hertogenbosch, the Netherlands KvK-nr.: 62051717