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.7 required=3.0 tests=AWL,BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,HTML_MESSAGE,MAILING_LIST_MULTI, RCVD_IN_DNSWL_HI,RCVD_IN_MSPIKE_H4,RCVD_IN_MSPIKE_WL,SPF_HELO_PASS, SPF_PASS shortcircuit=no autolearn=ham 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 A96021F4B4 for ; Sat, 3 Apr 2021 16:46:44 +0000 (UTC) Received: from localhost ([::1]:47182 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lSjQ3-0004dF-EA for normalperson@yhbt.net; Sat, 03 Apr 2021 12:46:43 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:43680) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lSjPv-0004d4-QQ for bug-gnulib@gnu.org; Sat, 03 Apr 2021 12:46:36 -0400 Received: from mail-pg1-x52e.google.com ([2607:f8b0:4864:20::52e]:36444) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1lSjPq-00030i-6o for bug-gnulib@gnu.org; Sat, 03 Apr 2021 12:46:35 -0400 Received: by mail-pg1-x52e.google.com with SMTP id h25so5457319pgm.3 for ; Sat, 03 Apr 2021 09:46:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=AodpfxaqgL6F6LfOzyhxxP6CL5lso+i+IK2A8g2IBpE=; b=ZrBlMV5QAxE0jRtslOFBeqTB+08GSE7II9IqLfKvadubhyFFQYsmXtu4Np+4UJxS5P BPfCJ/SBu0JwURAALWKsfLxyoof+02tKz0GDpUEgNgBNHbLErlP9Z/DKjK1gFN9xGQH3 F4zu6+nyBketd8gVqLpAV8WPlWv2yb6PlCpPsrzOIfdmfslpu4GzvJ29FhgW6yHLTMy5 XNQPlMM8Z9dv9EjydtWaYho2tqfGIAuWwdABWbsvCoMxjxgLeG9fs4WYeRXrFVmzEqeQ 5RygtVht2k9dbaxo3m1hnPdoDMKzFH4qrtakHuNW4q+JjoCtPfoF2TxJBJHQhXNV4o9A PSSQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=AodpfxaqgL6F6LfOzyhxxP6CL5lso+i+IK2A8g2IBpE=; b=inrLwhmkQI3X711/VX7L/iRpqmYvWPLNF6YaEvcj24V3JauoXIp2Q8JzYv63m2WfRo 21wSFzHQe8vdMZMDnYIKpKyupSeeXqPIbnYM6PzQKL8knglGHF1dBOskO/BB0E+sFss4 2Erx/oqh2rYcSLS0uZMPpGIOOYO3LoNAfIsEir3h5TAAVD7vSAviD98iX+r6bEYBtTk2 nQN9lYExL09WyJuFxK9DceuwoLpBGg7ikqdQ3tsGVmqoAJW9WURLxsrrsEf9+dyY6n1x /q08mkAl/pXCuRhCRNmtr8bMyNgLwE/wZAQE15KhUHhro9FQ0Xk85e+Va20L7SAY9uFF lB8Q== X-Gm-Message-State: AOAM533BRhliaDPubd49xhgvkPjPGpJDgXyjOuNOU2swmdQHlKXKtbas Hr42KPdgZ+UfLOJjzzNUi9i+f8BZxiu2V+bG8VA= X-Google-Smtp-Source: ABdhPJw3RnpmE530aLOkV42dCMJnvafxdRkfqqGVNg5nZpzcqdD7h7jxVyNfjd7lYiDn3ojQuoDt28ace9KoHhsiD8g= X-Received: by 2002:a62:1e46:0:b029:1f3:ad4f:9c6b with SMTP id e67-20020a621e460000b02901f3ad4f9c6bmr17324702pfe.64.1617468385764; Sat, 03 Apr 2021 09:46:25 -0700 (PDT) MIME-Version: 1.0 References: <8340998.mUjTdehA91@omega> <1800839.ENYuhlJxWL@omega> In-Reply-To: <1800839.ENYuhlJxWL@omega> From: =?UTF-8?Q?Marc_Nieper=2DWi=C3=9Fkirchen?= Date: Sat, 3 Apr 2021 18:46:14 +0200 Message-ID: Subject: Re: Node to first or last element of a sequential list in module list/xlist To: Bruno Haible Content-Type: multipart/alternative; boundary="00000000000091aba805bf1434da" Received-SPF: pass client-ip=2607:f8b0:4864:20::52e; envelope-from=marc.nieper@gmail.com; helo=mail-pg1-x52e.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham 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: =?UTF-8?Q?Marc_Nieper=2DWi=C3=9Fkirchen?= , bug-gnulib@gnu.org Errors-To: bug-gnulib-bounces+normalperson=yhbt.net@gnu.org Sender: "bug-gnulib" --00000000000091aba805bf1434da Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Bruno, thank you very much! Am Sa., 3. Apr. 2021 um 18:28 Uhr schrieb Bruno Haible : > Marc Nieper-Wi=C3=9Fkirchen wrote: > > For example, given a list of fruits, insert "pear" after each "apple" a= nd > > "peach" before each "apple". This can be easily done through > > gl_list_add_before/gl_list_add_after/gl_list_next_node without using > > invalidated nodes. > > Now I see what you mean. Quasi companion functions to gl_list_next_node > and gl_list_previous_node: gl_list_first_node and gl_list_last_node, > respectively. > I'm sorry for any confusion. I should have expressed myself more clearly in my initial email. > > What I want to propose is to allow the NULL value in > > gl_next_node/gl_previous_node. In this case, gl_next_node shall return > the > > first node and gl_previous_node shall return the last node. > Yes, gl_list_first_node and gl_list_last_node are indeed much better. I was only worried about the size of the vtable. > I don't think this encourages robust programs. If a program passes a NULL > pointer to gl_list_next_node or gl_list_previous_node, the program should > better crash. > > > PS What can't be done (because gl_list_remove doesn't return a valid > > (next?) node) is list walking algorithms that both remove and insert > nodes. > > For removal, one has to use an iterator. > > 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. > Speaking of this, this is not always non-trivial if the dispose function is not NULL. Consider an algorithm that processes one list to produce a new one. In the end, the old list shall be removed but the items that have ended up in the new list shall not be disposed. I guess that the canonical way to achieve this is to use gl_list_set to overwrite the values in the old list with dummy values (e.g. NULL) so that they are not freed on eventual removal. -- Marc --00000000000091aba805bf1434da Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Brun= o,

thank you very much!

Am Sa., 3. Apr. 2021 = um 18:28=C2=A0Uhr schrieb Bruno Haible <bruno@clisp.org>:
Marc Nieper-Wi=C3=9Fkirchen wrote:
> For example, given a list of fruits, insert "pear" after eac= h "apple" and
> "peach" before each "apple". This can be easily do= ne through
> gl_list_add_before/gl_list_add_after/gl_list_next_node without using > invalidated nodes.

Now I see what you mean. Quasi companion functions to gl_list_next_node
and gl_list_previous_node: gl_list_first_node and gl_list_last_node,
respectively.

I'm sorry for any confusion. I shou= ld have expressed myself more clearly in my initial email.
<= div>=C2=A0
> What I want to propose is to allow the NULL value in
> gl_next_node/gl_previous_node. In this case, gl_next_node shall return= the
> first node and gl_previous_node shall return the last node.

Yes, gl_list_first_node and gl_list_last_node are indeed much b= etter. I was only worried about the size of the vtable.
=C2=A0
I don't think this encourages robust programs. If a program passes a NU= LL
pointer to gl_list_next_node or gl_list_previous_node, the program should better crash.

> PS What can't be done (because gl_list_remove doesn't return a= valid
> (next?) node) is list walking algorithms that both remove and insert n= odes.
> For removal, one has to use an iterator.

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.

Speaking of this, this= is not always non-trivial if the dispose function is not NULL. Consider an= algorithm that processes one list to produce a new one. In the end, the ol= d list shall be removed but the items that have ended up in the new list sh= all not be disposed. I guess that the canonical way to achieve this is to u= se gl_list_set to overwrite the values in the old list with dummy values (e= .g. NULL) so that they are not freed on eventual removal.

-- Marc
--00000000000091aba805bf1434da--