From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-ASN: AS31976 209.132.180.0/23 X-Spam-Status: No, score=-4.1 required=3.0 tests=AWL,BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_EF,HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED,SPF_HELO_PASS,SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dcvr.yhbt.net (Postfix) with ESMTPS id E51831F461 for ; Tue, 14 May 2019 20:40:52 +0000 (UTC) DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:subject:to:references:from:message-id:date :mime-version:in-reply-to:content-type :content-transfer-encoding; q=dns; s=default; b=qUeb9+r+AGvdh/LA J/mHECalkX8wiLLFNy9A1wf0O2ixxCWG7WbepurNP0EFmhOKrmxFYuYFYnbYbYsg JQwQ1KzB5hbgH8aYXsXo+aRJ+3vBJHR/MRlqQ2DVbmINKvmYOkuVjB+oLr/I7TMq x4fpcrNSq7ebaa86B1Um2cZ7I58= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:subject:to:references:from:message-id:date :mime-version:in-reply-to:content-type :content-transfer-encoding; s=default; bh=ZP56qhonlmtBlfoV1FV/mE COZwM=; b=d9niNqO10iqbmZzrbn4aHHjKbf87pWHQqjVTaolqUQEJuAbk4wd/yG qeEIgo/p2+ZdRF2Lc+oI5DTWYRgMJH22DIez921mgcXe4s+oJcK0qqdFx+0a9Yon d8uDEBKd7NODFTCNfoOOf4szxygMotoDxQc03np2OnzXSG1gprQsM= Received: (qmail 88566 invoked by alias); 14 May 2019 20:40:44 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Received: (qmail 88496 invoked by uid 89); 14 May 2019 20:40:44 -0000 Authentication-Results: sourceware.org; auth=none X-HELO: mail-qt1-f172.google.com Subject: Re: I'm unhappy about twalk_r To: libc-alpha@sourceware.org, Florian Weimer References: <874l5x44tb.fsf@oldenburg2.str.redhat.com> From: Carlos O'Donell Message-ID: <7b5f1e26-99b7-c162-05c1-f3ee08109c75@redhat.com> Date: Tue, 14 May 2019 16:40:39 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.6.1 MIME-Version: 1.0 In-Reply-To: <874l5x44tb.fsf@oldenburg2.str.redhat.com> Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit On 5/14/19 8:08 AM, Florian Weimer wrote: > I have second thoughts about twalk_r. I think the twalk interface is > just broken because the internal tree structure is > implementation-defined (because there is so much flexibility in > balancing a binary tree). Or put differently, while the overall > iteration order is well-defined by the key ordering, it's mostly > unspecified which nodes are leaf nodes and which are internal nodes. > Exposing this information using the VISIT argument seems wrong to me. > > I still think the function is useful, but I think the interface should > look like this instead: > > int twalk_r (const void *root, > int (*action) (const void *nodep, void *closure), > void *closure); > > ACTION is invoked for every node in the tree, in increasing key order, > as long as ACTION returns zero. Otherwise, no further invocations > happen and twalk_r returns this non-zero value. If all calls to ACTION > return zero (and the entire tree is traversed), twalk_r returns zero. > > I think this is much more useful: It avoids pointless repeated calls to > ACTION, and it allows premature termination of the iteration. You identify two distinct issues: * For a given iteration the twalk API exposes the node placement via the VISIT argument, and this information is going to change as the tree is rebalanced after modification. It's not clear what use this information can have given that it changes dynamically. A quick look at the Java TreeMap API shows no "VISIT"-like information for the underlying tree. * There is no way to terminate the walk early with the exception of heavy weight operations like siglongjmp/longjmp/pthread_cancel. The alternative interfaces in other languages use iterators and therefore you can simply stop iterating if you've found the node of interest. My own position: - I agree with DJ, and I think twalk_r should match twalk as closely as possible even if we don't like the way twalk or twalk_r behave semantically as APIs. Having twalk_r be as straight-forward a solution as possible is important. I think twalk_r as you implemented it for glibc 2.30 is perfect and we should keep it (unless you want to suggest adding back level just for simplicity of conversion so users don't have to +/- their own level following preorder/endorder). - If we are going to discuss a new API we should look at the last decade of reference implementations in other languages, and see what would be a best fit for C. We should do our due diligence and think about the interfaces other languages provide and what we are missing. - In Java you have TreeMap, in C++ you have std::map, etc. would it be useful if glibc had a map structure? With iterators? etc. to replace the twalk* API? In summary: - Make twalk_r mirror twalk. - Discuss other APIs. -- Cheers, Carlos.