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: AS3215 2.0.0.0/16 X-Spam-Status: No, score=-3.6 required=3.0 tests=AWL,BAYES_00,DKIM_INVALID, DKIM_SIGNED,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from lists.gnu.org (lists.gnu.org [IPv6:2001:470:142::17]) (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 3CB111F8C1 for ; Sat, 2 May 2020 12:08:18 +0000 (UTC) Received: from localhost ([::1]:56666 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1jUqwL-0005CA-2d for normalperson@yhbt.net; Sat, 02 May 2020 08:08:17 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:54892) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1jUqwC-0005Bk-Hp for bug-gnulib@gnu.org; Sat, 02 May 2020 08:08:08 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.90_1) (envelope-from ) id 1jUqwB-0004Xu-0j for bug-gnulib@gnu.org; Sat, 02 May 2020 08:08:08 -0400 Received: from mo6-p00-ob.smtp.rzone.de ([2a01:238:20a:202:5300::1]:14611) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1jUqw9-0004Xa-VW for bug-gnulib@gnu.org; Sat, 02 May 2020 08:08:06 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; t=1588421280; s=strato-dkim-0002; d=clisp.org; h=References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From: X-RZG-CLASS-ID:X-RZG-AUTH:From:Subject:Sender; bh=Pi0llJiTk4RjvDF+lTzpY30SZlRV7Pb1NRJtD8JZVaY=; b=qjzeqJEaaZ1RDNmvSCXPGPAvSG5mK3s3Y1Gxz0sQyoAmvj+839p3SGXeaQS9n7F/8F KLXz8bi6KHnZl/SmHXqB7np4UJ5nhc+zoM+n1++U4MFcZ+BQpxdnlTdqfjLcy17Lkmaf x7FQBzHb9EXbdwIviw2Uu9aPGfNbBiutwEwRF166sS+RYjOX24xdyOquFu2uQLYkYiam 8YhJiGz3NhcmPOetJyZvHBTjVMv2jgK/xQqW766hoDQSKKp39/sMKJOfc4ukcW4Hm1Mc 4/kpBTi/rGE3wSp05oxdOoy/FZvn8okrc4cqbppJ5ZdiotfUOgnkR9QKWFKMMhKTk5vv tqvg== X-RZG-AUTH: ":Ln4Re0+Ic/6oZXR1YgKryK8brlshOcZlIWs+iCP5vnk6shH+AHjwLuWOH6fzxfs=" X-RZG-CLASS-ID: mo00 Received: from bruno.haible.de by smtp.strato.de (RZmta 46.6.2 DYNA|AUTH) with ESMTPSA id j093d3w42C80nK2 (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (curve X9_62_prime256v1 with 256 ECDH bits, eq. 3072 bits RSA)) (Client did not present a certificate); Sat, 2 May 2020 14:08:00 +0200 (CEST) From: Bruno Haible To: Marc =?ISO-8859-1?Q?Nieper=2DWi=DFkirchen?= Subject: Re: Add gl_list_remove_last to list/xlist Date: Sat, 02 May 2020 14:07:58 +0200 Message-ID: <5387499.3lU0nRZGG1@omega> User-Agent: KMail/5.1.3 (Linux/4.4.0-177-generic; KDE/5.18.0; x86_64; ; ) In-Reply-To: References: <5110345.JM7xtn9l3k@omega> MIME-Version: 1.0 Content-Transfer-Encoding: 7Bit Content-Type: text/plain; charset="us-ascii" Received-SPF: none client-ip=2a01:238:20a:202:5300::1; envelope-from=bruno@clisp.org; helo=mo6-p00-ob.smtp.rzone.de X-detected-operating-system: by eggs.gnu.org: Error: [-] PROGRAM ABORT : Malformed IPv6 address (bad octet value). Location : parse_addr6(), p0f-client.c:67 X-Received-From: 2a01:238:20a:202:5300::1 X-BeenThere: bug-gnulib@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Gnulib discussion list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: bug-gnulib@gnu.org Errors-To: bug-gnulib-bounces+normalperson=yhbt.net@gnu.org Sender: "bug-gnulib" Hi Marc, > I didn't mean that gl_list_remove_last > should return the just deleted node but the node of the element that > is now the last one (the respectively first one for > gl_list_remove_first) after the removal. The gl_list_node_t type, in the 'list' interface so far, is used in operations that work on a single position. Except for the functions gl_list_next_node and gl_list_previous_node, which intentionally walk from one node to a neighbour node. Having a function that does an effect on the last element and returns the position of the second-to-last element would be an invitation to incorrect coding. Better keep the operations simple! Also, I don't see why your proposed operation would be important to have in a general API for lists. > The motivation behind my suggestion is to make it easy to implement a > stack (or a FIFO queue) with the gl_list interface. It is already easy to implement a stack or FIFO using the primitives. E.g. stack_pop = 1. gl_list_get_at (list, gl_list_size (list) - 1) 2. gl_list_remove_at (list, gl_list_size (list) - 1) or gl_list_remove_last (list). It would be a mistake to add semantics of stack or FIFO directly to the list interface, because a list *is* not a stack or a FIFO; a list *can be used to implement* a stack or a FIFO. It is an important concept that one interface can be used to implement another interface (-> layered software, hiding implementation details, etc.). See e.g. in Java: they have different interfaces for list [1], stack [2], and FIFO [2]. Initially, they defined Stack as a subclass of AbstractList, but realized later that it was a mistake. You are welcome to add a stack or FIFO module in gnulib. Most likely, each of the two will only have a single implementation. Why? Because - for stacks, the ARRAY and LINKED implementations would have the same O() complexity for each operation, and then ARRAY would be preferred because it is more efficient regarding use of memory and L1/L2 caches, - for FIFOs, the CARRAY and LINKED implementations would have the same O() complexity for each operation, and similarly CARRAY would be preferred because it is more efficient regarding use of memory and L1/L2 caches. > For this, > operations like gl_list_get_first and gl_list_get_last with guaranteed > O(1) behavior for a number of list implementations would also be nice. Hmm. I'm reluctant to introduce 4 new functions gl_list_get_first gl_list_get_last gl_list_set_first gl_list_set_last when the gl_list_get/gl_list_set operations with appropriate position argument already do the job. It appears to be more of a documentation issue, right? I.e. I should better revert yesterday's patch, and instead, in the table show the guaranteed average performance gl_list_get_first gl_list_get_last gl_list_set_first gl_list_set_last gl_list_remove_first gl_list_remove_last where these 6 functions are defined globally, not separately for each implementation. Bruno [1] https://docs.oracle.com/javase/8/docs/api/java/util/AbstractList.html [2] https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html