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_INVALID, DKIM_SIGNED,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, RCVD_IN_DNSWL_MED,RCVD_IN_MSPIKE_H2,SPF_HELO_NONE,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 A9D8F1F8C1 for ; Fri, 8 May 2020 17:28:35 +0000 (UTC) Received: from localhost ([::1]:39142 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1jX6na-0005J6-SO for normalperson@yhbt.net; Fri, 08 May 2020 13:28:34 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:46974) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1jX6nW-0005Fc-WC for bug-gnulib@gnu.org; Fri, 08 May 2020 13:28:31 -0400 Received: from mo6-p00-ob.smtp.rzone.de ([2a01:238:20a:202:5300::12]:19793) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1jX6nU-0001f5-FZ for bug-gnulib@gnu.org; Fri, 08 May 2020 13:28:30 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; t=1588958905; 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=bwQP7rTBH/NLU2goMffrC/jwgna601LNDYpZiucy6EI=; b=kXgIxw6FucW2md5b0N9lSZ+pnJYTh7y/yUbfJpNNANSk8uStx3uyOt9dKXOSRn0Uo8 xAcw+wqdY1Oem45PXm5cXiTBihlD056I04NJA6Vm8VSPaGlw4dESOIv9LmJGRhUTWuuO KhPIB31oFShaRxzrrx4Sum+Ntk7XBQgwr/bdLwAT5YRS2RVeoeUUR3TAitoDIyE0fsmR q6CdPLIT1e2QCbVEtVwQZu909FpoM39Fe2Y2NE7ECmd6ydDyLdv7Yp7uUg3WlnuCjxkM hiYEOMCLAxJBA2Pd8Z5MJNETSYGkQnRg8ZC/Hc+joWvxaIid2ZO51Oz6A+RUjKgoTjVs yfuA== 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 j093d3w48HSOK6r (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); Fri, 8 May 2020 19:28:24 +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: Fri, 08 May 2020 19:28:23 +0200 Message-ID: <2280007.J6dQ8KOkbd@omega> User-Agent: KMail/5.1.3 (Linux/4.4.0-177-generic; KDE/5.18.0; x86_64; ; ) In-Reply-To: References: <4261612.ILBSuMgyWs@omega> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="iso-8859-1" Received-SPF: none client-ip=2a01:238:20a:202:5300::12; envelope-from=bruno@clisp.org; helo=mo6-p00-ob.smtp.rzone.de X-detected-operating-system: by eggs.gnu.org: No matching host in p0f cache. That's all we know. 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, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_PASS=-0.001, URIBL_BLOCKED=0.001 autolearn=_AUTOLEARN 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" Hi Marc, > Just one note: The documentation needs to be updated in section 14.8 > as well ([1]). Right. Thank you for the reminder. Done through the patch below. Note that it can take a couple of months until the doc on www.gnu.org is updated; we don't push a doc update that frequently. 2020-05-08 Bruno Haible list: Update documentation. Reported by Marc Nieper-Wi=DFkirchen in . * doc/containers.texi (Container data types): Document the new list operations and their complexity. diff --git a/doc/containers.texi b/doc/containers.texi index b3f154d..dd92529 100644 =2D-- a/doc/containers.texi +++ b/doc/containers.texi @@ -160,6 +160,24 @@ for the ``sequential list'' data type are: @tab @math{O(n)} @tab @math{O(@log n)} @tab @math{O(@log n)} +@item @code{gl_list_get_first} +@tab @math{O(1)} +@tab @math{O(1)} +@tab @math{O(1)} +@tab @math{O(@log n)} +@tab @math{O(1)} +@tab @math{O(1)} +@tab @math{O(@log n)} +@tab @math{O(@log n)} +@item @code{gl_list_get_last} +@tab @math{O(1)} +@tab @math{O(1)} +@tab @math{O(1)} +@tab @math{O(@log n)} +@tab @math{O(1)} +@tab @math{O(1)} +@tab @math{O(@log n)} +@tab @math{O(@log n)} @item @code{gl_list_set_at} @tab @math{O(1)} @tab @math{O(1)} @@ -169,6 +187,24 @@ for the ``sequential list'' data type are: @tab @math{O(n)} @tab @math{O((@log n)@mathopsup{2})} @tab @math{O(@log n)} +@item @code{gl_list_set_first} +@tab @math{O(1)} +@tab @math{O(1)} +@tab @math{O(1)} +@tab @math{O(@log n)} +@tab @math{O(n)} +@tab @math{O(1)} +@tab @math{O((@log n)@mathopsup{2})} +@tab @math{O(@log n)} +@item @code{gl_list_set_last} +@tab @math{O(1)} +@tab @math{O(1)} +@tab @math{O(1)} +@tab @math{O(@log n)} +@tab @math{O(n)} +@tab @math{O(1)} +@tab @math{O((@log n)@mathopsup{2})} +@tab @math{O(@log n)} @item @code{gl_list_search} @tab @math{O(n)} @tab @math{O(n)} @@ -286,6 +322,24 @@ for the ``sequential list'' data type are: @tab @math{O(n)} @tab @math{O((@log n)@mathopsup{2})} @tab @math{O(@log n)} +@item @code{gl_list_remove_first} +@tab @math{O(n)} +@tab @math{O(1)} +@tab @math{O(1)} +@tab @math{O(@log n)} +@tab @math{O(n)} +@tab @math{O(1)} +@tab @math{O((@log n)@mathopsup{2})} +@tab @math{O(@log n)} +@item @code{gl_list_remove_last} +@tab @math{O(1)} +@tab @math{O(1)} +@tab @math{O(1)} +@tab @math{O(@log n)} +@tab @math{O(n)} +@tab @math{O(1)} +@tab @math{O((@log n)@mathopsup{2})} +@tab @math{O(@log n)} @item @code{gl_list_remove} @tab @math{O(n)} @tab @math{O(n)}