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 995911F4B4 for ; Mon, 5 Apr 2021 10:21:06 +0000 (UTC) Received: from localhost ([::1]:57268 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lTMLx-0007O9-91 for normalperson@yhbt.net; Mon, 05 Apr 2021 06:21:05 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:58804) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lTMLv-0007ND-0Y for bug-gnulib@gnu.org; Mon, 05 Apr 2021 06:21:03 -0400 Received: from mail-pj1-x1031.google.com ([2607:f8b0:4864:20::1031]:54256) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1lTMLt-0003JJ-4E for bug-gnulib@gnu.org; Mon, 05 Apr 2021 06:21:02 -0400 Received: by mail-pj1-x1031.google.com with SMTP id t23so2601144pjy.3 for ; Mon, 05 Apr 2021 03:20:59 -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=Xvlze5RDEnprta86u2tN+ONRfXLk5Jpxh7DWkx1bdNc=; b=hxuiIDwLyPFgX95SQRHVvs5CGIh+Xzgpa/Ee8l6+weMAn5q6X46HiK8LxiQ7Ha8gYT NrXP6lF1oplnPfVDJdngtQ6Jql0jrnIVWTH8sEIIvYL35pNpOU2PH06b0rPut+AjMGVO 1HFAFxlR219O1USoINHLcksAmZtuSlJsDKasfzTWAmzw17WEiRxmn+LQgsR2mtRKqCMW VrpLySmbizMxiT1t1h/sPoPrnyYw/C06BlVrzydxIutN1JGLdrvpCZTmN9NkRe2bHjm6 hd9GMMp5plkbYKNLV1W30g0V0mSt5LifmPugfS8WkKqzc5Hgz3na1zgHCLEHf53NzcOH R5yA== 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=Xvlze5RDEnprta86u2tN+ONRfXLk5Jpxh7DWkx1bdNc=; b=PBBv/913flS2tb2Pt6LtPoLNxjNRYcaZ+4w2ZmH64gIhFC4eEF2x7oRHLJTYSoQCQX NgTgXMf5GsrN4+Hi0Kwso93lenkd+3UdrTSORj3/GIQ4AcmrKkL4G2Qk8eK/f/jeIIoV S2q0zs0NnHEhaVbivrs3SHN5GI2IY5gVB5YMMdEQF67dmaeuFd67G7+HhBTaZeXBzG5j IxvjCcTzjomF+d1dVYA+EyeVFvFnGc6lcpA8MCpLxFGjQIKHz9uedFr+1lmhpfN7K/Hu GX7ybU0KK7mTHnBYT6lqtTPCWzkezRpjeP/31wqlY17DGFwsVsCfCaq9RU/6k2rQQU56 h0FQ== X-Gm-Message-State: AOAM530nCUch6aFnKFYUAbNDtvaL1rutkxRscNwcJ5dtMAaFqf43MDis evyk8xxdZN3KJ+vXhq4apX1QcE2YhpcvyJdCyOw= X-Google-Smtp-Source: ABdhPJz2QH2598djg75Hr8ZgafSfKvK+9xxNhmv18JQO4zhe6qsoVSp8VzUCquTCYYAzndlhSc03A/r2TecY/Q+CZl0= X-Received: by 2002:a17:90a:5884:: with SMTP id j4mr27037044pji.33.1617618058302; Mon, 05 Apr 2021 03:20:58 -0700 (PDT) MIME-Version: 1.0 References: <1800839.ENYuhlJxWL@omega> <2792583.fiM0EhyeSA@omega> In-Reply-To: <2792583.fiM0EhyeSA@omega> From: =?UTF-8?Q?Marc_Nieper=2DWi=C3=9Fkirchen?= Date: Mon, 5 Apr 2021 12:20:47 +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="000000000000bf594a05bf370dd1" Received-SPF: pass client-ip=2607:f8b0:4864:20::1031; envelope-from=marc.nieper@gmail.com; helo=mail-pj1-x1031.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 List" Errors-To: bug-gnulib-bounces+normalperson=yhbt.net@gnu.org Sender: "bug-gnulib" --000000000000bf594a05bf370dd1 Content-Type: text/plain; charset="UTF-8" Hi Bruno, Am Mo., 5. Apr. 2021 um 04:45 Uhr schrieb Bruno Haible : > [Adding back bug-gnulib in CC.] > Thanks! > > 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]. > I think there is a conceptual difference between preserving a single node and preserving an arbitrary number of nodes. The point is that gl_list_add_before and gl_list_add_after, which also mutate the list, return a single node from where the algorithm can continue (as the loop above shows). So it is one thing to ask for gl_list_remove_node to return a single valid node from where an iteration can proceed but quite a different thing to ask it to preserve an arbitrary number of nodes. Instead of the THEN node being arbitrary, it could also make sense to force it to be the node before or after, i.e. to have gl_list_remove_node_next and gl_list_remove_node_previous. Marc --000000000000bf594a05bf370dd1 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Brun= o,

Am Mo., 5. Apr. 2021 um 04:45=C2=A0Uhr schrieb Bru= no Haible <bruno@clisp.org>:
[Adding back bug-= gnulib in CC.]

Thanks!
=C2=A0
> Is there a fundamental reason why a list walking algorithm that both > inserts and removes items is not possible with an arbitrary Gnulib lis= t
> container? Obviously, the current API doesn't allow it. If it is j= ust 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.=C2=A0 The precondition is, of = course,
> that THEN !=3D NODE.=C2=A0 Furthermore, if THEN is NULL, NULL is retur= ned.
>
> A typical pattern would be:
>
> for (gl_list_node_t i =3D gl_list_first_node (list); i !=3D NULL;)
>=C2=A0 =C2=A0{
>=C2=A0 =C2=A0 =C2=A0Fruit fruit;
>=C2=A0 =C2=A0 =C2=A0if (is_apple (fruit))
>=C2=A0 =C2=A0 =C2=A0 =C2=A0node =3D gl_list_next_node (list, gl_list_ne= xt_node (list,
> gl_list_add_before (list, node, make_pear ())));
>=C2=A0 =C2=A0 =C2=A0else if (is_peach (fruit))
>=C2=A0 =C2=A0 =C2=A0 =C2=A0node =3D gl_list_next_node (gl_list_add_afte= r (list, node,
> make_strawberry ()));
>=C2=A0 =C2=A0 =C2=A0else if (is_banana (fruit))
>=C2=A0 =C2=A0 =C2=A0 =C2=A0node =3D gl_list_remove_node_then (list, nod= e, gl_list_next_node
> (list));
>=C2=A0 =C2=A0}
> (This is just a silly example for an algorithm that may want to replac= e
> 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, b= ut
several at once? One could generalize the function to

=C2=A0 void gl_list_remove_preserving_nodes (gl_list_t list, gl_list_node_t= victim,
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 size_t c= ount, gl_list_node_t *to_preserve);

which would preserve the nodes to_preserve[0 .. count-1].
<= div>
I think there is a conceptual difference between preserving a single n= ode and preserving an arbitrary number of nodes. The point is that gl_list_= add_before and gl_list_add_after, which also mutate the list, return a sing= le node from where the algorithm can continue (as the loop above shows). So= it is one thing to ask for gl_list_remove_node to return a single valid no= de from where an iteration can proceed but quite a different thing to ask i= t to preserve an arbitrary number of nodes.

Instead of the THEN node bei= ng arbitrary, it could also make sense to force it to be the node before or= after, i.e. to have gl_list_remove_node_next and gl_list_remove_node_previ= ous.
=
Marc
--000000000000bf594a05bf370dd1--