doc for generic containers

[Bruno Haible]

Here I'm adding basic documentation for the five generic container data types.


2019-01-06  Bruno Haible  <address@hidden>

        doc: Add documentation about container data types.
        * doc/containers.texi: New file.
        * doc/gnulib.texi (Particular Modules): Include it.

diff --git a/doc/containers.texi b/doc/containers.texi
new file mode 100644
index 0000000..c4ccb9f
--- /dev/null
+++ b/doc/containers.texi
@@ -0,0 +1,510 @@
address@hidden Container data types
address@hidden Container data types
+
address@hidden Copyright (C) 2019 Free Software Foundation, Inc.
+
address@hidden Permission is granted to copy, distribute and/or modify this 
document
address@hidden under the terms of the GNU Free Documentation License, Version 
1.3 or
address@hidden any later version published by the Free Software Foundation; 
with no
address@hidden Invariant Sections, no Front-Cover Texts, and no Back-Cover
address@hidden Texts.  A copy of the license is included in the ``GNU Free
address@hidden Documentation License'' file as part of this distribution.
+
address@hidden Written by Bruno Haible.
+
address@hidden This macro expands to \log in TeX mode, but just 'log' in HTML 
and info
address@hidden modes.
address@hidden
address@hidden log
+log
address@hidden macro
address@hidden ifnottex
+
address@hidden This macro expands to \mathopsup in TeX mode, to a superscript 
in HTML
address@hidden mode, and to ^ without braces in info mode.
address@hidden
address@hidden mathopsup {EXP}
address@hidden
address@hidden macro
address@hidden ifhtml
address@hidden
address@hidden mathopsup {EXP}
+^\EXP\
address@hidden macro
address@hidden ifinfo
+
+Gnulib provides several generic container data types.  They can be used
+to organize collections of application-defined objects.
+
address@hidden @columnfractions .15 .5 .1 .1 .15
address@hidden Data type
address@hidden Details
address@hidden Module
address@hidden Main include file
address@hidden Include file for operations with out-of-memory checking
address@hidden Sequential list
address@hidden Can contain any number of objects in any given order.
+     Duplicates are allowed, but can optionally be forbidden.
address@hidden @code{list}
address@hidden @code{"gl_list.h"}
address@hidden @code{"gl_xlist.h"}
address@hidden Set
address@hidden Can contain any number of objects; the order does not matter.
+     Duplicates (in the sense of the comparator) are forbidden.
address@hidden @code{set}
address@hidden @code{"gl_set.h"}
address@hidden @code{"gl_xset.h"}
address@hidden Ordered set
address@hidden Can contain any number of objects in the order of a given 
comparator
+     function.
+     Duplicates (in the sense of the comparator) are forbidden.
address@hidden @code{oset}
address@hidden @code{"gl_oset.h"}
address@hidden @code{"gl_xoset.h"}
address@hidden Map
address@hidden Can contain any number of (key, value) pairs, where keys and 
values
+     are objects;
+     there are no (key, value1) and (key, value2) pairs with the same key
+     (in the sense of a given comparator function).
address@hidden @code{map}
address@hidden @code{"gl_map.h"}
address@hidden @code{"gl_xmap.h"}
address@hidden Ordered map
address@hidden Can contain any number of (key, value) pairs, where keys and 
values
+     are objects;
+     the (key, value) pairs are ordered by the key, in the order of a given
+     comparator function;
+     there are no (key, value1) and (key, value2) pairs with the same key
+     (in the sense of the comparator function).
address@hidden @code{omap}
address@hidden @code{"gl_omap.h"}
address@hidden @code{"gl_xomap.h"}
address@hidden multitable
+
+Operations without out-of-memory checking (suitable for use in libraries) are
+declared in the ``main include file''.  Whereas operations with out-of-memory
+checking (suitable only in programs) are declared in the ``include file for
+operations with out-of-memory checking''.
+
+For each of the data types, several implementations are available, with
+different performance profiles with respect to the available operations.
+This enables you to start with the simplest implementation (ARRAY) initially,
+and switch to a more suitable implementation after profiling your application.
+The implementation of each container instance is specified in a single place
+only: in the invocation of the function @code{gl_*_create_empty} that creates
+the instance.
+
+The implementations and the guaranteed average performace for the operations
+for the ``sequential list'' data type are:
+
address@hidden @columnfractions 0.2 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
address@hidden Operation
address@hidden ARRAY
address@hidden CARRAY
address@hidden LINKED
address@hidden TREE
address@hidden LINKEDHASH with duplicates
address@hidden LINKEDHASH without duplicates
address@hidden TREEHASH with duplicates
address@hidden TREEHASH without duplicates
address@hidden @code{gl_list_size}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @code{gl_list_node_value}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @code{gl_list_node_set_value}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O((@log n)@mathopsup{2})}
address@hidden @math{O(1)}
address@hidden @code{gl_list_next_node}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(@log n)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(@log n)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_list_previous_node}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(@log n)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(@log n)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_list_get_at}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_list_set_at}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O((@log n)@mathopsup{2})}
address@hidden @math{O(@log n)}
address@hidden @code{gl_list_search}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(1)}
address@hidden @math{O(@log n)}
address@hidden @math{O(1)}
address@hidden @code{gl_list_search_from}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(1)}
address@hidden @math{O((@log n)@mathopsup{2})}
address@hidden @math{O(@log n)}
address@hidden @code{gl_list_search_from_to}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(1)}
address@hidden @math{O((@log n)@mathopsup{2})}
address@hidden @math{O(@log n)}
address@hidden @code{gl_list_indexof}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_list_indexof_from}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O((@log n)@mathopsup{2})}
address@hidden @math{O(@log n)}
address@hidden @code{gl_list_indexof_from_to}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O((@log n)@mathopsup{2})}
address@hidden @math{O(@log n)}
address@hidden @code{gl_list_add_first}
address@hidden @math{O(n)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(@log n)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O((@log n)@mathopsup{2})}
address@hidden @math{O(@log n)}
address@hidden @code{gl_list_add_last}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(@log n)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O((@log n)@mathopsup{2})}
address@hidden @math{O(@log n)}
address@hidden @code{gl_list_add_before}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(1)}
address@hidden @math{O(@log n)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O((@log n)@mathopsup{2})}
address@hidden @math{O(@log n)}
address@hidden @code{gl_list_add_after}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(1)}
address@hidden @math{O(@log n)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O((@log n)@mathopsup{2})}
address@hidden @math{O(@log n)}
address@hidden @code{gl_list_add_at}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O((@log n)@mathopsup{2})}
address@hidden @math{O(@log n)}
address@hidden @code{gl_list_remove_node}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(1)}
address@hidden @math{O(@log n)}
address@hidden @math{O(n)}
address@hidden @math{O(1)}
address@hidden @math{O((@log n)@mathopsup{2})}
address@hidden @math{O(@log n)}
address@hidden @code{gl_list_remove_at}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O((@log n)@mathopsup{2})}
address@hidden @math{O(@log n)}
address@hidden @code{gl_list_remove}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(1)}
address@hidden @math{O((@log n)@mathopsup{2})}
address@hidden @math{O(@log n)}
address@hidden @code{gl_list_iterator}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(@log n)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(@log n)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_list_iterator_from_to}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_list_iterator_next}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(@log n)}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @math{O(@log n)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_sortedlist_search}
address@hidden @math{O(@log n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_sortedlist_search_from}
address@hidden @math{O(@log n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_sortedlist_indexof}
address@hidden @math{O(@log n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_sortedlist_indexof_from}
address@hidden @math{O(@log n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_sortedlist_add}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O((@log n)@mathopsup{2})}
address@hidden @math{O(@log n)}
address@hidden @code{gl_sortedlist_remove}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @math{O(n)}
address@hidden @math{O(n)}
address@hidden @math{O((@log n)@mathopsup{2})}
address@hidden @math{O(@log n)}
address@hidden multitable
+
+The implementations and the guaranteed average performace for the operations
+for the ``set'' data type are:
+
address@hidden @columnfractions 0.4 0.2 0.4
address@hidden Operation
address@hidden ARRAY
address@hidden LINKEDHASH, HASH
address@hidden @code{gl_set_size}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @code{gl_set_add}
address@hidden @math{O(n)}
address@hidden @math{O(1)}
address@hidden @code{gl_set_remove}
address@hidden @math{O(n)}
address@hidden @math{O(1)}
address@hidden @code{gl_set_search}
address@hidden @math{O(n)}
address@hidden @math{O(1)}
address@hidden @code{gl_set_iterator}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @code{gl_set_iterator_next}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden multitable
+
+The implementations and the guaranteed average performace for the operations
+for the ``ordered set'' data type are:
+
address@hidden @columnfractions 0.5 0.25 0.25
address@hidden Operation
address@hidden ARRAY
address@hidden TREE
address@hidden @code{gl_oset_size}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @code{gl_oset_add}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_oset_remove}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_oset_search}
address@hidden @math{O(@log n)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_oset_search_atleast}
address@hidden @math{O(@log n)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_oset_iterator}
address@hidden @math{O(1)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_oset_iterator_next}
address@hidden @math{O(1)}
address@hidden @math{O(@log n)}
address@hidden multitable
+
+The implementations and the guaranteed average performace for the operations
+for the ``map'' data type are:
+
address@hidden @columnfractions 0.4 0.2 0.4
address@hidden Operation
address@hidden ARRAY
address@hidden LINKEDHASH, HASH
address@hidden @code{gl_map_size}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @code{gl_map_get}
address@hidden @math{O(n)}
address@hidden @math{O(1)}
address@hidden @code{gl_map_put}
address@hidden @math{O(n)}
address@hidden @math{O(1)}
address@hidden @code{gl_map_remove}
address@hidden @math{O(n)}
address@hidden @math{O(1)}
address@hidden @code{gl_map_search}
address@hidden @math{O(n)}
address@hidden @math{O(1)}
address@hidden @code{gl_map_iterator}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @code{gl_map_iterator_next}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden multitable
+
+The implementations and the guaranteed average performace for the operations
+for the ``ordered map'' data type are:
+
address@hidden @columnfractions 0.5 0.25 0.25
address@hidden Operation
address@hidden ARRAY
address@hidden TREE
address@hidden @code{gl_omap_size}
address@hidden @math{O(1)}
address@hidden @math{O(1)}
address@hidden @code{gl_omap_get}
address@hidden @math{O(@log n)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_omap_put}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_omap_remove}
address@hidden @math{O(n)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_omap_search}
address@hidden @math{O(@log n)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_omap_search_atleast}
address@hidden @math{O(@log n)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_omap_iterator}
address@hidden @math{O(1)}
address@hidden @math{O(@log n)}
address@hidden @code{gl_omap_iterator_next}
address@hidden @math{O(1)}
address@hidden @math{O(@log n)}
address@hidden multitable
+
address@hidden
address@hidden log
address@hidden ifnottex
address@hidden
address@hidden mathopsup
address@hidden ifhtml
address@hidden
address@hidden mathopsup
address@hidden ifinfo
diff --git a/doc/gnulib.texi b/doc/gnulib.texi
index 4378668..f7709c9 100644
--- a/doc/gnulib.texi
+++ b/doc/gnulib.texi
@@ -6366,6 +6366,7 @@ to POSIX that it can be treated like any other Unix-like 
platform.
 * Integer Properties::
 * extern inline::
 * Closed standard fds::
+* Container data types::
 * String Functions in C Locale::
 * Quoting::
 * progname and getprogname::
@@ -6397,6 +6398,8 @@ to POSIX that it can be treated like any other Unix-like 
platform.
 
 @include xstdopen.texi
 
address@hidden containers.texi
+
 @include c-locale.texi
 
 @include quote.texi