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: AS22989 209.51.188.0/24 X-Spam-Status: No, score=-3.0 required=3.0 tests=AWL,BAYES_00, DATE_IN_PAST_03_06,DKIM_INVALID,DKIM_SIGNED, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,NICE_REPLY_A, RCVD_IN_DNSWL_MED,RCVD_IN_MSPIKE_H4,RCVD_IN_MSPIKE_WL,SPF_HELO_PASS, SPF_PASS shortcircuit=no autolearn=no autolearn_force=no version=3.4.2 Received: from lists.gnu.org (lists.gnu.org [209.51.188.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 4375D1F4B4 for ; Mon, 5 Apr 2021 02:45:16 +0000 (UTC) Received: from localhost ([::1]:56084 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lTFEp-0003lb-5Q for normalperson@yhbt.net; Sun, 04 Apr 2021 22:45:15 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:53040) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lTFEl-0003lR-Mp for bug-gnulib@gnu.org; Sun, 04 Apr 2021 22:45:11 -0400 Received: from mo4-p00-ob.smtp.rzone.de ([85.215.255.22]:25871) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lTFEj-0005UY-Fa for bug-gnulib@gnu.org; Sun, 04 Apr 2021 22:45:11 -0400 ARC-Seal: i=1; a=rsa-sha256; t=1617590706; cv=none; d=strato.com; s=strato-dkim-0002; b=KIzy6VCS6VDzP0K1+AZ8FzfLsKXEeSlONlTL7TaHxkq7Kb25tGpAG3uFh3Lej8tOem gIgozfYucamNRaLqzPCXh4CXQotOVtsp4sSHAAI518PclHuzC9U7j9GzTskTDfPfzBqQ fxLHn6e/s8j9caXx8n6FauTnB4FtZkqmsArtFL24pdkipYoBAa+Zc5Kfyo7NE8YqaJif E4OzBWwQ6PxTpGHhBtZuQmD1jtKfwmjINACpWZNL/+4CLd2KRa6aW8CXQqBQuwaAUlnN ahQV+T451WVeP6DwdKidx8M02u7aabF1A+nUGIZuNKrndoTK+XYcAP63BlBg/vJEn44h YlKg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; t=1617590706; s=strato-dkim-0002; d=strato.com; h=References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Cc:Date: From:Subject:Sender; bh=R3AUAIgqjWuvNZk5Sjp5UVzN++YG/m35TJ690XfAKOY=; b=nYTDhN/cboJLyWEyJPgO/aZk9o4waZeIKmwoELhAcv4GDpo5iRiSpLgKWqwfXjoNGJ 1MgcRQRtHe0eSGhfOIOfNl/qjtbbvIA9+KP3WUJ8ILFyGKWCuBCsGuRKYPdjjMTS97ru c6+L84aTVbDpxXfUEN0CZMhzSRLj4g/lcJKjOSNrGVE5QEzLf4CBZiprDgzV21goF3Vu 8b54eb06Yifa4ojQrWBjLKlRdPC9KpUFaGpkSf0BfcSAkGrWkfP5FcpHbyt4//3um0ea Py6faFW5w33zKEwZZV8JYUdZIuITw80bYFJ5iBSwv54OPgyCz/KHoTWs/F9sNv4ziiFX fzHQ== ARC-Authentication-Results: i=1; strato.com; dkim=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; t=1617590706; s=strato-dkim-0002; d=clisp.org; h=References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Cc:Date: From:Subject:Sender; bh=R3AUAIgqjWuvNZk5Sjp5UVzN++YG/m35TJ690XfAKOY=; b=Q3QOGuaiAvlO50ROOo6Hed7U42c1ySDtspEA0HKuSf72w1RzAaJBzh3HW7oAiHijdp 3FxVImNtD88ZZD+M/yDy63nyAhwCzezbi33A5DfBemGP06Ob76gqJfMf4JLnSVFfizUC 1HxWfnOzBPlj2MNiS4qO9LqBpJhlm/Yg6GoEYTM5/7v9yS83UQtmnPzc7jb6CPbRLT+o j64MqE6Re56US9rh0MqOPht1AhIsg0pQxSv1Ajx9FghORFeM2YKNXadQaP27YaT4ncJI RoHPm4pX0I/pdqwZREMCfCeKffOnze0Tvqm8r07b+ab3qFFTQAZd6hfChnnZphbfVtdU oMHg== Authentication-Results: strato.com; dkim=none X-RZG-AUTH: ":Ln4Re0+Ic/6oZXR1YgKryK8brlshOcZlIWs+iCP5vnk6shH+AHjwLuWOHqf0y5JW" X-RZG-CLASS-ID: mo00 Received: from bruno.haible.de by smtp.strato.de (RZmta 47.23.1 DYNA|AUTH) with ESMTPSA id z01445x352j6dJU (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); Mon, 5 Apr 2021 04:45:06 +0200 (CEST) From: Bruno Haible To: Marc =?ISO-8859-1?Q?Nieper=2DWi=DFkirchen?= Subject: Re: Node to first or last element of a sequential list in module list/xlist Date: Mon, 05 Apr 2021 01:30:41 +0200 Message-ID: <2792583.fiM0EhyeSA@omega> User-Agent: KMail/5.1.3 (Linux/4.4.0-206-generic; KDE/5.18.0; x86_64; ; ) In-Reply-To: References: <1800839.ENYuhlJxWL@omega> MIME-Version: 1.0 Content-Transfer-Encoding: 7Bit Content-Type: text/plain; charset="us-ascii" Received-SPF: none client-ip=85.215.255.22; envelope-from=bruno@clisp.org; helo=mo4-p00-ob.smtp.rzone.de X-Spam_score_int: -4 X-Spam_score: -0.5 X-Spam_bar: / X-Spam_report: (-0.5 / 5.0 requ) BAYES_00=-1.9, DATE_IN_PAST_03_06=1.592, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, NICE_REPLY_A=-0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, SPF_HELO_PASS=-0.001, SPF_NONE=0.001 autolearn=no autolearn_force=no X-Spam_action: no action 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" [Adding back bug-gnulib in CC.] Hi Marc, > > Yes, some algorithms need a second, temporary list. Not all algorithms > > can be written to use the original list, be efficient in O() terms, and > > be implementation-independent. > > > > Is there a fundamental reason why a list walking algorithm that both > inserts and removes items is not possible with an arbitrary Gnulib list > container? Obviously, the current API doesn't allow it. If it is just the > limitation of an API that forces one to work with a second, temporary list, > > Would it be possible for all list types to provide a > > gl_list_node_t gl_list_remove_node_then (gl_list_t list, gl_list_node_t > node, gl_list_node_t then) > > that removes NODE from LIST and returns the node of that element > represented by THEN before the removal. The precondition is, of course, > that THEN != NODE. Furthermore, if THEN is NULL, NULL is returned. > > A typical pattern would be: > > for (gl_list_node_t i = gl_list_first_node (list); i != NULL;) > { > Fruit fruit; > if (is_apple (fruit)) > node = gl_list_next_node (list, gl_list_next_node (list, > gl_list_add_before (list, node, make_pear ()))); > else if (is_peach (fruit)) > node = gl_list_next_node (gl_list_add_after (list, node, > make_strawberry ())); > else if (is_banana (fruit)) > node = gl_list_remove_node_then (list, node, gl_list_next_node > (list)); > } > (This is just a silly example for an algorithm that may want to replace > elements by sublists (including sublists of length 0).) This example makes it clear what you mean. And what if the programmer wants to preserve not one 'then' node, but several at once? One could generalize the function to void gl_list_remove_preserving_nodes (gl_list_t list, gl_list_node_t victim, size_t count, gl_list_node_t *to_preserve); which would preserve the nodes to_preserve[0 .. count-1]. But for my feeling, programmers will not want to code like this. It is so much easier to allocate a new list and destroy the old one afterwards. Bruno