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_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, 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 644BC1F8C1 for ; Sat, 2 May 2020 12:49:47 +0000 (UTC) Received: from localhost ([::1]:49784 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1jUraU-0008Sy-5g for normalperson@yhbt.net; Sat, 02 May 2020 08:49:46 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:35860) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1jUraQ-0008Sc-HZ for bug-gnulib@gnu.org; Sat, 02 May 2020 08:49:42 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.90_1) (envelope-from ) id 1jUraP-0007x9-Sx for bug-gnulib@gnu.org; Sat, 02 May 2020 08:49:42 -0400 Received: from mail-pf1-x444.google.com ([2607:f8b0:4864:20::444]:46937) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1jUraP-0007x0-EH for bug-gnulib@gnu.org; Sat, 02 May 2020 08:49:41 -0400 Received: by mail-pf1-x444.google.com with SMTP id 145so2932834pfw.13 for ; Sat, 02 May 2020 05:49:41 -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=qtrHqrgAQGFdrTtsZjDj7ucBBs8cqX9XLAb7e6PJcMA=; b=I1aNAJX6VIxrv4QcFIRaMwFikZxyFRSub1Wm1OGS15MmfIogxNOZZmYDMr9MpmZHC+ WQZXoRbwKtJo0Ltfapbx/y+TKp9QXjCXItOLqfo4QAqDc+TKj3uBFIvOqHSv3Y/vBlvQ lPnDoAG4T7yTToN8iXeKCmjhn1m7wrq4GwKlJafVWefHvpjz83orJ8BG+nMxWVvHIdKj M79HE2RnUFngFY0IFPsQCkf3PyVopeDQIDmj0RfGAKccmW1/me2ocZW9963G7MNKZbK6 0WWG1ConcEBfo6pvLnVm+AUiFU9LRfE7GcIWovQGJNPdA2xpbTfj5b/M9bidJ8Co8HKH np5A== 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=qtrHqrgAQGFdrTtsZjDj7ucBBs8cqX9XLAb7e6PJcMA=; b=FwL60fwCx9L/mipYFzhJqKDyudr4EiCVIkIawabdOhuKmE0Q1VuZDqDPXhGcbwCWor l3uHrsjCW45svCQKyhoekKQRxcjghovId5SrungB9yTOA0MX1Anv+cnSXHBGSdIQTjLk S5fmvYujwLxE5bLYopK6gPSXWrP3OOsHTJQ5R8e4btTTXwPuIQNtfAbwfEO1lK3BADgd utGQjiDoMfjhV8FHFRr7AhhbrYv5boJpLdXMdRV1+2izcDKdHxH+BX9UmSTgjbkJEpO2 /Wh5CECaa5RS0qX/lomSM/ZUUsQWrSeHGiJ/VnNTC1zVfPEIbeqObRwAEUESq/74M8g3 0o8Q== X-Gm-Message-State: AGi0PuYIB9BZm430AHM5JxYOjvMXYDbeAA/tUk2qSbNZ66DAAVvBxoyL LB/7tm5XrUjidhdSJi2b+AYLJIeXwXO8kks7w2Q= X-Google-Smtp-Source: APiQypISr9mIuMIYkc4foHzbEc7L5a+4DqVXKcNl9qXWx/mU2yr3Dfm7mB7+u3fOkLsKnGn/5MrJgvsRivP8A3NpNS4= X-Received: by 2002:aa7:9689:: with SMTP id f9mr7709905pfk.24.1588423779599; Sat, 02 May 2020 05:49:39 -0700 (PDT) MIME-Version: 1.0 References: <5110345.JM7xtn9l3k@omega> <5387499.3lU0nRZGG1@omega> In-Reply-To: <5387499.3lU0nRZGG1@omega> From: =?UTF-8?Q?Marc_Nieper=2DWi=C3=9Fkirchen?= Date: Sat, 2 May 2020 14:49:28 +0200 Message-ID: Subject: Re: Add gl_list_remove_last to list/xlist To: Bruno Haible Content-Type: text/plain; charset="UTF-8" Received-SPF: pass client-ip=2607:f8b0:4864:20::444; envelope-from=marc.nieper@gmail.com; helo=mail-pf1-x444.google.com 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: 2607:f8b0:4864:20::444 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" Hi Bruno, [...] > 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! That's a fair point of view. [...] > > 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.). Okay; I agree that a separate stack or FIFO module can make more sense; in particular when it only has to deal with a single implementation of an underlying data structure. At the moment I do have other work to finish first, but maybe I will find some time in the near future for a stack module. [...] > > 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. When the functions can be defined globally, that's better than adding six functions to each vtable. Partly, it is just a documentation issue. I don't see, however, to implement the function dealing with end of the list in O(1) behavior when the underlying data structure is a linked list. Don't we need to expose an implementation-dependent gl_list_get_last_node (gl_list_first_node for symmetry)? The rest should then be implementable easily. Marc