On Thu, Apr 16, 2015 at 08:12:17AM +0300, Mikhail Maltsev wrote: > 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.
First a general comment where something has both a header and a .c file it probably makes sense to mention both. > > === 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) I wonder if that doesn't fit better in the category of gcc specific things. > gcc/ggc-page.c - size-class based allocator (used by garbage collector). > (?? isn't it the same as "slab allocator") I guess its basically a slab allocator, but its pretty tied in with the rest of ggc currently. > gcc/hash-table.h - contains some simple allocator templates I'm not particularly convinced those are useful, and actually pretty tempted to remove them when I get around to it. afaik nobody actually uses an allocator other than the one that calls xmalloc, and they don't help you work with ggc as the ggc support in hash_table shows. > 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 "objet stack" doesn't seem very descriptive to me. "bump allocator pool" or something might be a better description? > 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 This is another that doesn't seem very useful now, and I'll probably remove when I get around to it. > === 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 most of this is also deprecated gcc requires the system have 64 bit integer types now, but there's still a bunch of old code to remove. Trev > 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
