[RFC] Documenting support functions and data structures

[Mikhail Maltsev <maltsevm at gmail dot com>]

Hi, all!

I think GCC documentation is missing a description of commonly used data
structures and support functions. For example, "GCC internals" document
contains information about, say, GIMPLE IR and functions for
manipulating it. But it does not describe general data structures, such
as hash maps or vectors.
In fact, these structures are documented rather well in the source code,
but I could not find a list of them.
I mean something like this:
http://llvm.org/docs/ProgrammersManual.html#important-and-useful-llvm-apis

So, I want to create a similar page in GCC's internal docs, but I don't
know what should be included (i.e. did I miss something important, or
did I include something obsolete), so I ask for some assistance.

Here is a draft (a list of relevant files from ./gcc, ./include and
./libiberty directories). This list does not yet include functions for
interacting with host OS (it's a separate issue) and does not include
compiler-specific structures (like, say, control flow graph or varpool)
and algorithms. Ordering is somewhat random.

=== Memory management ===
gcc/alloc-pool.c - pool allocator
gcc/ggc* - mark-and-sweep garbage collector (includes sources of
gengtype, a program which generates traversal routines from
annotated C++ code)
gcc/ggc-page.c - size-class based allocator (used by garbage collector).
(?? isn't it the same as "slab allocator")
gcc/hash-table.h - contains some simple allocator templates
libiberty/xmalloc.c - wrappers for malloc and friends with checking

=== Data structures ===
gcc/bitmap.c - sparse integer set (based on linked lists of chunks)
gcc/sbitmap.c - "simple bitmap" - vector-based bitmap
gcc/et-forest.c - ET-forest data structure (used for efficient solution
of dynamic least common ancestor problem)
gcc/fibonacci_heap.h (header-only) - mergeable priority queues
gcc/graphds.c - graph representation and manipulation functions
gcc/hash-table.c - hash table implementation (base for hash-set and
hash-map)
gcc/hash-map.h (header-only) - hash map
gcc/hash-set.h (header-only) - hash set
gcc/sparse-set.c - another sparse set implementation (I think, I'll make
a table, with comparison of different
implementations w.r.t. size, available operations and their run time)
gcc/vec.c - vector template, implements several different memory
allocation strategies
include/obstack.h - object stack
libiberty/splay-tree.c - splay tree

=== RTTI, type manipulation ===
gcc/is-a.h (header-only) - customizable low-overhead RTTI and dynamic casts
gcc/system.h (header-only) - several implementations of const_cast

=== Algorithms ===
libiberty/md5.c, sha1.c - corresponding hash functions
libiberty/crc32.c - CRC32 checksum (BTW, why is bitwise implementation
from tree.c used everywhere instead of table algorithm?)
gcc/inchash.c - incremental hashing
libiberty/bsearch.c - binary search (and other stuff reimplementing libc
functions - is this a workaround for broken system libc?)

=== Multiprecision arithmetics ===
gcc/hwint.c - "host wide int" - macros for representing host system's
int64_t/uint64_t in a portable way and some related functions
gcc/wide-int.cc, namespace hw - generic finite precision integers
(including variable-precision and target-dependent precision integers
+ traits)
gcc/double-int.c - 128-bit fixed precision integer type
gcc/fixed-value.c - fixed precision real arithmetics, uses
target-dependent representation
gcc/real.c - floating-point arithmetics, including target-dependent
representation
gcc/mpfr.c - conversion routines from GCC internal float representation
to MPFR
gcc/sreal.c - simple software floating-point arithmetics

=== Debugging, statistics ===
gcc/dbgcnt.c - debug counters
gcc/errors.c - diagnostics for internal use (in generator programs)
gcc/statistics.c - arbitrary statistics counters and histograms
gcc/timevar.c - timing variables and timing stacks
gcc/system.h (header) - assertions, static_assert

=== Text manipulation ===
gcc/pretty-print.c - text formatting and output
libiberty/concat.c - multiple string concatenation
libiberty/regex.c - regular expressions

=== Serialization ===
gcc/data-streamer*.c - general marshalling routines
gcc/ggc* - marshalling routines, which use code generated by gengtype;
used for precompiled headers

I'm asking for advice on correct categorization, missing stuff, etc.

-- 
Regards,
    Mikhail Maltsev