From 0f76f71438bf11bb0867da65079e70a527a9de24 Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Fri, 8 May 2020 19:25:39 +0200 Subject: [PATCH] list: Update documentation. MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Reported by Marc Nieper-Wißkirchen in . * doc/containers.texi (Container data types): Document the new list operations and their complexity. --- ChangeLog | 8 +++++++ doc/containers.texi | 54 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 62 insertions(+) diff --git a/ChangeLog b/ChangeLog index 6f154d5137..12955aea19 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,11 @@ +2020-05-08 Bruno Haible + + list: Update documentation. + Reported by Marc Nieper-Wißkirchen in + . + * doc/containers.texi (Container data types): Document the new list + operations and their complexity. + 2020-05-08 Bruno Haible ignore-value tests: Use module 'attribute'. diff --git a/doc/containers.texi b/doc/containers.texi index b3f154db45..dd9252948f 100644 --- 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)} -- 2.39.5