Frozen Fish 1: Amiga/FrozenFish-Apr94.iso/bbs/gnu/libg++-2.5.3-bin.lha/info/libg++.info-2

GNU Info File | 1994-02-27 | 50KB | 912 lines

This is Info file libg++.info, produced by Makeinfo-1.55 from the input
file ./libg++.texi.
START-INFO-DIR-ENTRY
* Libg++::                      The g++ class library.
END-INFO-DIR-ENTRY
   This file documents the features and implementation of The GNU C++
library
   Copyright (C) 1988, 1991, 1992 Free Software Foundation, Inc.
   Permission is granted to make and distribute verbatim copies of this
manual provided the copyright notice and this permission notice are
preserved on all copies.
   Permission is granted to copy and distribute modified versions of
this manual under the conditions for verbatim copying, provided also
that the section entitled "GNU Library General Public License" is
included exactly as in the original, and provided that the entire
resulting derived work is distributed under the terms of a permission
notice identical to this one.
   Permission is granted to copy and distribute translations of this
manual into another language, under the above conditions for modified
versions, except that the section entitled "GNU Library General Public
License" and this permission notice may be included in translations
approved by the Free Software Foundation instead of in the original
English.
File: libg++.info,  Node: Proto,  Next: Representations,  Prev: OK,  Up: Top
Introduction to container class prototypes
******************************************
   As a temporary mechanism enabling the support of generic classes,
the GNU C++ Library distribution contains a directory (`g++-include')
of files designed to serve as the basis for generating container
classes of specified elements.  These files can be used to generate
`.h' and `.cc' files in the current directory via a supplied shell
script program that performs simple textual substitution to create
specific classes.
   While these classes are generated independently, and thus share no
code, it is possible to create versions that do share code among
subclasses. For example, using `typedef void* ent', and then generating
a `entList' class, other derived classes could be created using the
`void*' coercion method described in Stroustrup, pp204-210.
   This very simple class-generation facility is useful enough to serve
current purposes, but will be replaced with a more coherent mechanism
for handling C++ generics in a way that minimally disrupts current
usage.  Without knowing exactly when or how parametric classes might be
added to the C++ language, provision of this simplest possible
mechanism, textual substitution, appears to be the safest strategy,
although it does require certain redundancies and awkward constructions.
   Specific classes may be generated via the `genclass' shell script
program. This program has arguments specifying the kinds of base
types(s) to be used. Specifying base types requires two arguments. The
first is the name of the base type, which may be any named type, like
`int' or `String'. Only named types are supported; things like `int*'
are not accepted. However, pointers like this may be used by supplying
the appropriate typedefs (e.g., editing the resulting files to include
`typedef int* intp;'). The type name must be followed by one of the
words `val' or `ref', to indicate whether the base elements should be
passed to functions by-value or by-reference.
   You can specify basic container classes using `genclass base
[val,ref] proto', where `proto' is the name of the class being
generated.  Container classes like dictionaries and maps that require
two types may be specified via `genclass -2 keytype [val, ref],
basetype [val, ref] proto', where the key type is specified first and
the contents type second.  The resulting classnames and filenames are
generated by prepending the specified type names to the prototype names,
and separating the filename parts with dots.  For example, `genclass
int val List' generates class `intList' residing in files `int.List.h'
and `int.List.cc'. `genclass -2 String ref int val VHMap' generates
(the awkward, but unavoidable) class name `StringintVHMap'. Of course,
programmers may use `typedef' or simple editing to create more
appropriate names.  The existence of dot seperators in file names
allows the use of GNU make to help automate configuration and
recompilation. An example Makefile exploiting such capabilities may be
found in the `libg++/proto-kit' directory.
   The `genclass' utility operates via simple text substitution using
`sed'. All occurrences of the pseudo-types `<T>' and `<C>' (if there
are two types) are replaced with the indicated type, and occurrences of
`<T&>' and `<C&>' are replaced by just the types, if `val' is
specified, or types followed by "&" if `ref' is specified.
   Programmers will frequently need to edit the `.h' file in order to
insert additional `#include' directives or other modifications.  A
simple utility, `prepend-header' to prepend other `.h' files to
generated files is provided in the distribution.
   One dubious virtue of the prototyping mechanism is that, because
sources files, not archived library classes, are generated, it is
relatively simple for programmers to modify container classes in the
common case where slight variations of standard container classes are
required.
   It is often a good idea for programmers to archive (via `ar')
generated classes into `.a' files so that only those class functions
actually used in a given application will be loaded.  The test
subdirectory of the distribution shows an example of this.
   Because of `#pragma interface' directives, the `.cc' files should be
compiled with `-O' or `-DUSE_LIBGXX_INLINES' enabled.
   Many container classes require specifications over and above the base
class type. For example, classes that maintain some kind of ordering of
elements require specification of a comparison function upon which to
base the ordering.  This is accomplished via a prototype file `defs.hP'
that contains macros for these functions. While these macros default to
perform reasonable actions, they can and should be changed in
particular cases. Most prototypes require only one or a few of these.
No harm is done if unused macros are defined to perform nonsensical
actions. The macros are:
`DEFAULT_INITIAL_CAPACITY'
     The initial capacity for containers (e.g., hash tables) that
     require an initial capacity argument for constructors.  Default:
     100
`<T>EQ(a, b)'
     return true if a is considered equal to b for the purposes of
     locating, etc., an element in a container.  Default: (a == b)
`<T>LE(a, b)'
     return true if a is less than or equal to b Default: (a <= b)
`<T>CMP(a, b)'
     return an integer < 0 if a<b, 0 if a==b, or > 0 if a>b.  Default:
     (a <= b)? (a==b)? 0 : -1 : 1
`<T>HASH(a)'
     return an unsigned integer representing the hash of a.  Default:
     hash(a) ; where extern unsigned int hash(<T&>).  (note: several
     useful hash functions are declared in builtin.h and defined in
     hash.cc)
   Nearly all prototypes container classes support container traversal
via `Pix' pseudo indices, as described elsewhere.
   All object containers must perform either a `X::X(X&)' (or `X::X()'
followed by `X::operator =(X&)') to copy objects into containers.  (The
latter form is used for containers built from C++ arrays, like
`VHSets'). When containers are destroyed, they invoke `X::~X()'.  Any
objects used in containers must have well behaved constructors and
destructors. If you want to create containers that merely reference
(point to) objects that reside elsewhere, and are not copied or
destroyed inside the container, you must use containers of pointers,
not containers of objects.
   All prototypes are designed to generate *HOMOGENOUS* container
classes.  There is no universally applicable method in C++ to support
heterogenous object collections with elements of various subclasses of
some specified base class. The only way to get heterogenous structures
is to use collections of pointers-to-objects, not collections of objects
(which also requires you to take responsibility for managing storage for
the objects pointed to yourself).
   For example, the following usage illustrates a commonly encountered
danger in trying to use container classes for heterogenous structures:
     class Base { int x; ...}
     class Derived : public Base { int y; ... }

     BaseVHSet s; // class BaseVHSet generated via something like
                  // `genclass Base ref VHSet'

     void f()
     {
       Base b;
       s.add(b); // OK

       Derived d;
       s.add(d);  // (CHOP!)
     }
   At the line flagged with `(CHOP!)', a `Base::Base(Base&)' is called
inside `Set::add(Base&)'--*not* `Derived::Derived(Derived&)'.
Actually, in `VHSet', a `Base::operator =(Base&)', is used instead to
place the element in an array slot, but with the same effect.  So only
the Base part is copied as a `VHSet' element (a so-called
chopped-copy). In this case, it has an `x' part, but no `y' part; and a
Base, not Derived, vtable. Objects formed via chopped copies are rarely
sensible.
   To avoid this, you must resort to pointers:
     typedef Base* BasePtr;

     BasePtrVHSet s; // class BaseVHSet generated via something like
                     // `genclass BasePtr val VHSet'

     void f()
     {
       Base* bp = new Base;
       s.add(b);

       Base* dp = new Derived;
       s.add(d);  // works fine.

       // Don't forget to delete bp and dp sometime.
       // The VHSet won't do this for you.
     }
Example
=======
   The prototypes can be difficult to use on first attempt. Here is an
example that may be helpful. The utilities in the `proto-kit' simplify
much of the actions described, but are not used here.
   Suppose you create a class `Person', and want to make an Map that
links the social security numbers associated with each person. You start
off with a file `Person.h'
     #include <String.h>

     class Person
     {
       String nm;
       String addr;
       //...
     public:
       const String& name() { return nm; }
       const String& address() { return addr; }
       void          print() { ... }
       //...
     }
   And in file `SSN.h',
     typedef unsigned int SSN;
   Your first decision is what storage/usage strategy to use. There are
several reasonable alternatives here: You might create an "object
collection" of Persons, a "pointer collection" of pointers-to-Persons,
or even a simple String map, housing either copies of pointers to the
names of Persons, since other fields are unused for purposes of the
Map. In an object collection, instances of class Person "live" inside
the Map, while in a pointer collection, the instances live elsewhere.
Also, as above, if instances of subclasses of Person are to be used
inside the Map, you must use pointers. In a String Map, the same
difference holds, but now only for the name fields. Any of these
choices might make sense in particular applications.
   The second choice is the Map implementation strategy. Either a tree
or a hash table might make sense. Suppose you want an AVL tree Map.
There are two things to now check. First, as an object collection, the
AVLMap requires that the elsement class contain an `X(X&)' constructor.
In C++, if you don't specify such a constructor, one is constructed for
you, but it is a very good idea to always do this yourself, to avoid
surprises. In this example, you'd use something like
     class Person
     { ...;
         Person(const Person& p) :nm(p.nm), addr(p.addr) {}
     };
   Also, an AVLMap requires a comparison function for elements in order
to maintain order. Rather than requiring you to write a particular
comparison function, a `defs' file is consulted to determine how to
compare items. You must create and edit such a file.
   Before creating `Person.defs.h', you must first make one additional
decision. Should the Map member functions like `m.contains(p)' take
arguments (`p') by reference (i.e., typed as `int Map::contains(const
Person& p)' or by value (i.e., typed as `int Map::contains(const Person
p)'. Generally, for user-defined classes, you want to pass by
reference, and for builtins and pointers, to pass by value. SO you
should pick by-reference.
   You can now create `Person.defs.h' via `genclass Person ref defs'.
This creates a simple skeleton that you must edit. First, add `#include
"Person.h"' to the top. Second, edit the `<T>CMP(a,b)' macro to compare
on name, via
     #define <T>CMP(a, b) ( compare(a.name(), b.name()) )
which invokes the `int compare(const String&, const String&)' function
from `String.h'. Of course, you could define this in any other way as
well. In fact, the default versions in the skeleton turn out to be OK
(albeit inefficient) in this particular example.
   You may also want to create file `SSN.defs.h'. Here, choosing
call-by-value makes sense, and since no other capabilities (like
comparison functions) of the SSNs are used (and the defaults are OK
anyway), you'd type
     genclass SSN val defs
and then edit to place `#include "SSN.h"' at the top.
   Finally, you can generate the classes. First, generate the base
class for Maps via
     genclass -2 Person ref SSN val Map
This generates only the abstract class, not the implementation, in file
`Person.SSN.Map.h' and `Person.SSN.Map.cc'.  To create the AVL
implementation, type
     genclass -2 Person ref SSN val AVLMap
This creates the class `PersonSSNAVLMap', in `Person.SSN.AVLMap.h' and
`Person.SSN.AVLMap.cc'.
   To use the AVL implementation, compile the two generated `.cc'
files, and specify `#include "Person.SSN.AVLMap.h"' in the application
program.  All other files are included in the right ways automatically.
   One last consideration, peculiar to Maps, is to pick a reasonable
default contents when declaring an AVLMap. Zero might be appropriate
here, so you might declare a Map,
     PersonSSNAVLMap m((SSN)0);
   Suppose you wanted a `VHMap' instead of an `AVLMap' Besides
generating different implementations, there are two differences in how
you should prepare the `defs' file. First, because a VHMap uses a C++
array internally, and because C++ array slots are initialized
differently than single elements, you must ensure that class Person
contains (1) a no-argument constructor, and (2) an assignment operator.
You could arrange this via
     class Person
     { ...;
         Person() {}
       void operator = (const Person& p) { nm = p.nm; addr = p.addr; }
     };
   (The lack of action in the constructor is OK here because `Strings'
possess usable no-argument constructors.)
   You also need to edit `Person.defs.h' to indicate a usable hash
function and default capacity, via something like
     #include <builtin.h>
     #define <T>HASH(x)  (hashpjw(x.name().chars()))
     #define DEFAULT_INITIAL_CAPACITY 1000
   Since the `hashpjw' function from `builtin.h' is appropriate here.
Changing the default capacity to a value expected to exceed the actual
capacity helps to avoid "hidden" inefficiencies when a new VHMap is
created without overriding the default, which is all too easy to do.
   Otherwise, everything is the same as above, substituting `VHMap' for
`AVLMap'.
File: libg++.info,  Node: Representations,  Next: Expressions,  Prev: Proto,  Up: Top
Variable-Sized Object Representation
************************************
   One of the first goals of the GNU C++ library is to enrich the kinds
of basic classes that may be considered as (nearly) "built into" C++. A
good deal of the inspiration for these efforts is derived from
considering features of other type-rich languages, particularly Common
Lisp and Scheme.  The general characteristics of most class and friend
operators and functions supported by these classes has been heavily
influenced by such languages.
   Four of these types, Strings, Integers, BitSets, and BitStrings (as
well as associated and/or derived classes) require representations
suitable for managing variable-sized objects on the free-store. The
basic technique used for all of these is the same, although various
details necessarily differ from class to class.
   The general strategy for representing such objects is to create
chunks of memory that include both header information (e.g., the size
of the object), as well as the variable-size data (an array of some
sort) at the end of the chunk. Generally the maximum size of an object
is limited to something less than all of addressable memory, as a
safeguard. The minimum size is also limited so as not to waste
allocations expanding very small chunks. Internally, chunks are
allocated in blocks well-tuned to the performance of the `new' operator.
   Class elements themselves are merely pointers to these chunks.  Most
class operations are performed via inline "translation" functions that
perform the required operation on the corresponding representation.
However, constructors and assignments operate by copying entire
representations, not just pointers.
   No attempt is made to control temporary creation in expressions and
functions involving these classes. Users of previous versions of the
classes will note the disappearance of both "Tmp" classes and reference
counting. These were dropped because, while they did improve
performance in some cases, they obscure class mechanics, lead
programmers into the false belief that they need not worry about such
things, and occasionally have paradoxical behavior.
   These variable-sized object classes are integrated as well as
possible into C++. Most such classes possess converters that allow
automatic coercion both from and to builtin basic types. (e.g., char*
to and from String, long int to and from Integer, etc.). There are
pro's and con's to circular converters, since they can sometimes lead
to the conversion from a builtin type through to a class function and
back to a builtin type without any special attention on the part of the
programmer, both for better and worse.
   Most of these classes also provide special-case operators and
functions mixing basic with class types, as a way to avoid constructors
in cases where the operations do not rely on anything special about the
representations.  For example, there is a special case concatenation
operator for a String concatenated with a char, since building the
result does not rely on anything about the String header. Again, there
are arguments both for and against this approach. Supporting these cases
adds a non-trivial degree of (mainly inline) function proliferation, but
results in more efficient operations. Efficiency wins out over parsimony
here, as part of the goal to produce classes that provide sufficient
functionality and efficiency so that programmers are not tempted to try
to manipulate or bypass the underlying representations.
File: libg++.info,  Node: Expressions,  Next: Pix,  Prev: Representations,  Up: Top
Some guidelines for using expression-oriented classes
*****************************************************
   The fact that C++ allows operators to be overloaded for user-defined
classes can make programming with library classes like `Integer',
`String', and so on very convenient. However, it is worth becoming
familiar with some of the inherent limitations and problems associated
with such operators.
   Many operators are *constructive*, i.e., create a new object based
on some function of some arguments. Sometimes the creation of such
objects is wasteful. Most library classes supporting expressions
contain facilities that help you avoid such waste.
   For example, for `Integer a, b, c; ...;  c = a + b + a;', the plus
operator is called to sum a and b, creating a new temporary object as
its result. This temporary is then added with a, creating another
temporary, which is finally copied into c, and the temporaries are then
deleted. In other words, this code might have an effect similar to
`Integer a, b, c; ...; Integer t1(a); t1 += b; Integer t2(t1); t2 += a;
c = t2;'.
   For small objects, simple operators, and/or non-time/space critical
programs, creation of temporaries is not a big problem. However, often,
when fine-tuning a program, it may be a good idea to rewrite such code
in a less pleasant, but more efficient manner.
   For builtin types like ints, and floats, C and C++ compilers already
know how to optimize such expressions to reduce the need for
temporaries. Unfortunately, this is not true for C++ user defined
types, for the simple (but very annoying, in this context) reason that
nothing at all is guaranteed about the semantics of overloaded operators
and their interrelations. For example, if the above expression just
involved ints, not Integers, a compiler might internally convert the
statement into something like ` c += a; c += b; c+= a; ', or perhaps
something even more clever.  But since C++ does not know that Integer
operator += has any relation to Integer operator +, A C++ compiler
cannot do this kind of expression optimization itself.
   In many cases, you can avoid construction of temporaries simply by
using the assignment versions of operators whenever possible, since
these versions create no temporaries. However, for maximum flexibility,
most classes provide a set of "embedded assembly code" procedures that
you can use to fully control time, space, and evaluation strategies.
Most of these procedures are "three-address" procedures that take two
`const' source arguments, and a destination argument. The procedures
perform the appropriate actions, placing the results in the destination
(which is may involve overwriting old contents). These procedures are
designed to be fast and robust. In particular, aliasing is always
handled correctly, so that, for example `add(x, x, x); ' is perfectly
OK. (The names of these procedures are listed along with the classes.)
   For example, suppose you had an Integer expression ` a = (b - a) *
-(d / c); '
   This would be compiled as if it were ` Integer t1=b-a; Integer
t2=d/c; Integer t3=-t2; Integer t4=t1*t3; a=t4;'
   But, with some manual cleverness, you might yourself some up with `
sub(a, b, a); mul(a, d, a); div(a, c, a); '
   A related phenomenon occurs when creating your own constructive
functions returning instances of such types. Suppose you wanted to
write function `Integer f(const Integer& a) { Integer r = a;  r += a;
return r; }'
   This function, when called (as in ` a = f(a); ') demonstrates a
similar kind of wasted copy. The returned value r must be copied out of
the function before it can be used by the caller. In GNU C++, there is
an alternative via the use of named return values.  Named return values
allow you to manipulate the returned object directly, rather than
requiring you to create a local inside a function and then copy it out
as the returned value. In this example, this can be done via `Integer
f(const Integer& a) return r(a) { r += a; return; }'
   A final guideline: The overloaded operators are very convenient, and
much clearer to use than procedural code. It is almost always a good
idea to make it right, *then* make it fast, by translating expression
code into procedural code after it is known to be correct.
File: libg++.info,  Node: Pix,  Next: Headers,  Prev: Expressions,  Up: Top
Pseudo-indexes
**************
   Many useful classes operate as containers of elements. Techniques for
accessing these elements from a container differ from class to class.
In the GNU C++ library, access methods have been partially standardized
across different classes via the use of pseudo-indexes called `Pixes'.
A `Pix' acts in some ways like an index, and in some ways like a
pointer. (Their underlying representations are just `void*' pointers).
A `Pix' is a kind of "key" that is translated into an element access by
the class.  In virtually all cases, `Pixes' are pointers to some kind
internal storage cells. The containers use these pointers to extract
items.
   `Pixes' support traversal and inspection of elements in a collection
using analogs of array indexing. However, they are pointer-like in that
`0' is treated as an invalid `Pix', and unsafe insofar as programmers
can attempt to access nonexistent elements via dangling or otherwise
invalid `Pixes' without first checking for their validity.
   In general it is a very bad idea to perform traversals in the the
midst of destructive modifications to containers.
   Typical applications might include code using the idiom
     for (Pix i = a.first(); i != 0; a.next(i)) use(a(i));
   for some container `a' and function `use'.
   Classes supporting the use of `Pixes' always contain the following
methods, assuming a container `a' of element types of `Base'.
`Pix i = a.first()'
     Set i to index the first element of a or 0 if a is empty.
`a.next(i)'
     advance i to the next element of a or 0 if there is no next
     element;
`Base x = a(i); a(i) = x;'
     a(i) returns a reference to the element indexed by i.
`int present = a.owns(i)'
     returns true if Pix i is a valid Pix in a. This is often a
     relatively slow operation, since the collection must usually
     traverse through elements to see if any correspond to the Pix.
   Some container classes also support backwards traversal via
`Pix i = a.last()'
     Set i to the last element of a or 0 if a is empty.
`a.prev(i)'
     sets i to the previous element in a, or 0 if there is none.
   Collections supporting elements with an equality operation possess
`Pix j = a.seek(x)'
     sets j to the index of the first occurrence of x, or 0 if x is not
     contained in a.
   Bag classes possess
`Pix j = a.seek(x, Pix from = 0)'
     sets j to the index of the next occurrence of x following i, or 0
     if x is not contained in a. If i == 0, the first occurrence is
     returned.
   Set, Bag, and PQ classes possess
`Pix j = a.add(x) (or a.enq(x) for priority queues)'
     add x to the collection, returning its Pix. The Pix of an item can
     change in collections where further additions and deletions
     involve the actual movement of elements (currently in OXPSet,
     OXPBag, XPPQ, VOHSet), but in all other cases, an item's Pix may
     be considered a permanent key to its location.
File: libg++.info,  Node: Headers,  Next: Builtin,  Prev: Pix,  Up: Top
Header files for interfacing C++ to C
*************************************
   The following files are provided so that C++ programmers may invoke
common C library and system calls. The names and contents of these
files are subject to change in order to be compatible with the
forthcoming GNU C library. Other files, not listed here, are simply
C++-compatible interfaces to corresponding C library files.
`values.h'
     A collection of constants defining the numbers of bits in builtin
     types, minimum and maximum values, and the like. Most names are
     the same as those found in `values.h' found on Sun systems.
`std.h'
     A collection of common system calls and `libc.a' functions.  Only
     those functions that can be declared without introducing new type
     definitions (socket structures, for example) are provided. Common
     `char*' functions (like `strcmp') are among the declarations. All
     functions are declared along with their library names, so that
     they may be safely overloaded.
`string.h'
     This file merely includes `<std.h>', where string function
     prototypes are declared. This is a workaround for the fact that
     system `string.h' and `strings.h' files often differ in contents.
`osfcn.h'
     This file merely includes `<std.h>', where system function
     prototypes are declared.
`libc.h'
     This file merely includes `<std.h>', where C library function
     prototypes are declared.
`math.h'
     A collection of prototypes for functions usually found in libm.a,
     plus some `#define'd constants that appear to be consistent with
     those provided in the AT&T version. The value of `HUGE' should be
     checked before using. Declarations of all common math functions
     are preceded with `overload' declarations, since these are
     commonly overloaded.
`stdio.h'
     Declaration of `FILE' (`_iobuf'), common macros (like `getc'), and
     function prototypes for `libc.a' functions that operate on
     `FILE*''s. The value `BUFSIZ' and the declaration of `_iobuf'
     should be checked before using.
`assert.h'
     C++ versions of assert macros.
`generic.h'
     String concatenation macros useful in creating generic classes.
     They are similar in function to the AT&T CC versions.
`new.h'
     Declarations of the default global operator new, the two-argument
     placement version, and associated error handlers.
File: libg++.info,  Node: Builtin,  Next: New,  Prev: Headers,  Up: Top
Utility functions for built in types
************************************
   Files `builtin.h' and corresponding `.cc' implementation files
contain various convenient inline and non-inline utility functions.
These include useful enumeration types, such as `TRUE', `FALSE' ,the
type definition for pointers to libg++ error handling functions, and
the following functions.
`long abs(long x); double abs(double x);'
     inline versions of abs. Note that the standard libc.a version,
     `int abs(int)' is *not* declared as inline.
`void clearbit(long& x, long b);'
     clears the b'th bit of x (inline).
`void setbit(long& x, long b);'
     sets the b'th bit of x (inline)
`int testbit(long x, long b);'
     returns the b'th bit of x (inline).
`int even(long y);'
     returns true if x is even (inline).
`int odd(long y);'
     returns true is x is odd (inline).
`int sign(long x); int sign(double x);'
     returns -1, 0, or 1, indicating whether x is less than, equal to,
     or greater than zero (inline).
`long gcd(long x, long y);'
     returns the greatest common divisor of x and y.
`long lcm(long x, long y);'
     returns the least common multiple of x and y.
`long lg(long x);'
     returns the floor of the base 2 log of x.
`long pow(long x, long y); double pow(double x, long y);'
     returns x to the integer power y using via the iterative O(log y)
     "Russian peasant" method.
`long sqr(long x); double sqr(double x);'
     returns x squared (inline).
`long sqrt(long y);'
     returns the floor of the square root of x.
`unsigned int hashpjw(const char* s);'
     a hash function for null-terminated char* strings using the method
     described in Aho, Sethi, & Ullman, p 436.
`unsigned int multiplicativehash(int x);'
     a hash function for integers that returns the lower bits of
     multiplying x by the golden ratio times pow(2, 32).  See Knuth,
     Vol 3, p 508.
`unsigned int foldhash(double x);'
     a hash function for doubles that exclusive-or's the first and
     second words of x, returning the result as an integer.
`double start_timer()'
     Starts a process timer.
`double return_elapsed_time(double last_time)'
     Returns the process time since last_time.  If last_time == 0
     returns the time since the last start_timer.  Returns -1 if
     start_timer was not first called.
   File `Maxima.h' includes versions of `MAX, MIN' for builtin types.
   File `compare.h' includes versions of `compare(x, y)' for builtin
types. These return negative if the first argument is less than the
second, zero for equal, and positive for greater.
File: libg++.info,  Node: New,  Next: Stream,  Prev: Builtin,  Up: Top
Library dynamic allocation primitives
*************************************
   Libg++ contains versions of `malloc, free, realloc' that were
designed to be well-tuned to C++ applications. The source file
`malloc.c' contains some design and implementation details.  Here are
the major user-visible differences from most system malloc routines:
  1. These routines *overwrite* storage of freed space. This means that
     it is never permissible to use a `delete''d object in any way.
     Doing so will either result in trapped fatal errors or random
     aborts within malloc, free, or realloc.
  2. The routines tend to perform well when a large number of objects
     of the same size are allocated and freed. You may find that it is
     not worth it to create your own special allocation schemes in such
     cases.
  3. The library sets top-level `operator new()' to call malloc and
     `operator delete()' to call free. Of course, you may override these
     definitions in C++ programs by creating your own operators that
     will take precedence over the library versions. However, if you do
     so, be sure to define *both* `operator new()' and `operator
     delete()'.
  4. These routines do *not* support the odd convention, maintained by
     some versions of malloc, that you may call `realloc' with a pointer
     that has been `free''d.
  5. The routines automatically perform simple checks on `free''d
     pointers that can often determine whether users have accidentally
     written beyond the boundaries of allocated space, resulting in a
     fatal error.
  6. The function `malloc_usable_size(void* p)' returns the number of
     bytes actually allocated for `p'. For a valid pointer (i.e., one
     that has been `malloc''d or `realloc''d but not yet `free''d) this
     will return a number greater than or equal to the requested size,
     else it will normally return 0. Unfortunately, a non-zero return
     can not be an absolutely perfect indication of lack of error. If a
     chunk has been `free''d but then re-allocated for a different
     purpose somewhere elsewhere, then `malloc_usable_size' will return
     non-zero. Despite this, the function can be very valuable for
     performing run-time consistency checks.
  7. `malloc' requires 8 bytes of overhead per allocated chunk, plus a
     mmaximum alignment adjustment of 8 bytes. The number of bytes of
     usable space is exactly as requested, rounded to the nearest 8
     byte boundary.
  8. The routines do *not* contain any synchronization support for
     multiprocessing. If you perform global allocation on a shared
     memory multiprocessor, you should disable compilation and use of
     libg++ malloc in the distribution `Makefile' and use your system
     version of malloc.
File: libg++.info,  Node: Stream,  Next: Obstack,  Prev: New,  Up: Top
The old I/O library
*******************
   WARNING: This chapter describes classes that are *obsolete*.  These
classes are normally not available when libg++ is installed normally.
The sources are currently included in the distribution, and you can
configure libg++ to use these classes instead of the new iostream
classes.  This is only a temporary measure; you should convert your
code to use iostreams as soon as possible.  The iostream classes
provide some compatibility support, but it is very incomplete (there is
no longer a `File' class).
File-based classes
==================
   The `File' class supports basic IO on Unix files.  Operations are
based on common C stdio library functions.
   `File' serves as the base class for istreams, ostreams, and other
derived classes. It contains the interface between the Unix stdio file
library and these more structured classes.  Most operations are
implemented as simple calls to stdio functions. `File' class operations
are also fully compatible with raw system file reads and writes (like
the system `read' and `lseek' calls) when buffering is disabled (see
below).  The `FILE*' stdio file pointer is, however maintained as
protected.  Classes derived from File may only use the IO operations
provided by File, which encompass essentially all stdio capabilities.
   The class contains four general kinds of functions: methods for
binding `File's to physical Unix files, basic IO methods, file and
buffer control methods, and methods for maintaining logical and
physical file status.
   Binding and related tasks are accomplished via `File' constructors
and destructors, and member functions `open, close, remove, filedesc,
name, setname'.
   If a file name is provided in a constructor or open, it is
maintained as class variable `nm' and is accessible via `name'.  If no
name is provided, then `nm' remains null, except that `Files' bound to
the default files stdin, stdout, and stderr are automatically given the
names `(stdin), (stdout), (stderr)' respectively.  The function
`setname' may be used to change the internal name of the `File'. This
does not change the name of the physical file bound to the File.
   The member function `close' closes a file.  The `~File' destructor
closes a file if it is open, except that stdin, stdout, and stderr are
flushed but left open for the system to close on program exit since
some systems may require this, and on others it does not matter.
`remove' closes the file, and then deletes it if possible by calling the
system function to delete the file with the name provided in the `nm'
field.
Basic IO
========
   * `read' and `write' perform binary IO via stdio `fread' and
     `fwrite'.
   * `get' and `put' for chars invoke stdio `getc' and `putc' macros.
   * `put(const char* s)' outputs a null-terminated string via stdio
     `fputs'.
   * `unget' and `putback' are synonyms.  Both call stdio `ungetc'.
File Control
============
   `flush', `seek', `tell', and `tell' call the corresponding stdio
functions.
   `flush(char)' and `fill()' call stdio `_flsbuf' and `_filbuf'
respectively.
   `setbuf' is mainly useful to turn off buffering in cases where
nonsequential binary IO is being performed. `raw' is a synonym for
`setbuf(_IONBF)'.  After a `f.raw()', using the stdio functions instead
of the system `read, write', etc., calls entails very little overhead.
Moreover, these become fully compatible with intermixed system calls
(e.g., `lseek(f.filedesc(), 0, 0)'). While intermixing `File' and
system IO calls is not at all recommended, this technique does allow
the `File' class to be used in conjunction with other functions and
libraries already set up to operate on file descriptors. `setbuf'
should be called at most once after a constructor or open, but before
any IO.
File Status
===========
   File status is maintained in several ways.
   A `File' may be checked for accessibility via `is_open()', which
returns true if the File is bound to a usable physical file,
`readable()', which returns true if the File can be read from (opened
for reading, and not in a _fail state), or `writable()', which returns
true if the File can be written to.
   `File' operations return their status via two means: failure and
success are represented via the logical state. Also, the return values
of invoked stdio and system functions that return useful numeric values
(not just failure/success flags) are held in a class variable
accessible via `iocount'.  (This is useful, for example, in determining
the number of items actually read by the `read' function.)
   Like the AT&T i/o-stream classes, but unlike the description in the
Stroustrup book, p238, `rdstate()' returns the bitwise OR of `_eof',
`_fail' and `_bad', not necessarily distinct values. The functions
`eof()', `fail()', `bad()', and `good()' can be used to test for each of
these conditions independently.
   `_fail' becomes set for any input operation that could not read in
the desired data, and for other failed operations. As with all Unix IO,
`_eof' becomes true only when an input operations fails because of an
end of file. Therefore, `_eof' is not immediately true after the last
successful read of a file, but only after one final read attempt. Thus,
for input operations, `_fail' and `_eof' almost always become true at
the same time.  `bad' is set for unbound files, and may also be set by
applications in order to communicate input corruption. Conversely,
`_good' is defined as 0 and is returned by `rdstate()' if all is well.
   The state may be modified via `clear(flag)', which, despite its
name, sets the corresponding state_value flag.  `clear()' with no
arguments resets the state to `_good'.  `failif(int cond)' sets the
state to `_fail' only if `cond' is true.
   Errors occuring during constructors and file opens also invoke the
function `error'.  `error' in turn calls a resetable error handling
function pointed to by the non-member global variable
`File_error_handler' only if a system error has been generated.  Since
`error' cannot tell if the current system error is actually responsible
for a failure, it may at times print out spurious messages.  Three
error handlers are provided. The default, `verbose_File_error_handler'
calls the system function `perror' to print the corresponding error
message on standard error, and then returns to the caller.
`quiet_File_error_handler' does nothing, and simply returns.
`fatal_File_error_handler' prints the error and then aborts execution.
These three handlers, or any other user-defined error handlers can be
selected via the non-member function `set_File_error_handler'.
   All read and write operations communicate either logical or physical
failure by setting the `_fail' flag.  All further operations are
blocked if the state is in a `_fail' or`_bad' condition. Programmers
must explicitly use `clear()' to reset the state in order to continue
IO processing after either a logical or physical failure.  C
programmers who are unfamiliar with these conventions should note that,
unlike the stdio library, `File' functions indicate IO success, status,
or failure solely through the state, not via return values of the
functions.  The `void*' operator or `rdstate()' may be used to test
success.  In particular, according to c++ conversion rules, the `void*'
coercion is automatically applied whenever the `File&' return value of
any `File' function is tested in an `if' or `while'.  Thus, for
example, an easy way to copy all of stdin to stdout until eof (at which
point `get' fails) or some error is `char c; while(cin.get(c) &&
cout.put(c));'.
   The current version of istreams and ostreams differs significantly
from previous versions in order to obtain compatibility with AT&T 1.2
streams. Most code using previous versions should still work. However,
the following features of `File' are not incorporated in streams (they
are still present in `File'): `scan(const char* fmt...), remove(),
read(), write(), setbuf(), raw()'. Additionally, the feature of
previous streams that allowed free intermixing of stream and stdio
input and output is no longer guaranteed to always behave as desired.
File: libg++.info,  Node: Obstack,  Next: AllocRing,  Prev: Stream,  Up: Top
The Obstack class
*****************
   The `Obstack' class is a simple rewrite of the C obstack macros and
functions provided in the GNU CC compiler source distribution.
   Obstacks provide a simple method of creating and maintaining a string
table, optimized for the very frequent task of building strings
character-by-character, and sometimes keeping them, and sometimes not.
They seem especially useful in any parsing application. One of the test
files demonstrates usage.
   A brief summary:
`grow'
     places something on the obstack without committing to wrap it up
     as a single entity yet.
`finish'
     wraps up a constructed object as a single entity, and returns the
     pointer to its start address.
`copy'
     places things on the obstack, and *does* wrap them up.  `copy' is
     always equivalent to first grow, then finish.
`free'
     deletes something, and anything else put on the obstack since its
     creation.
   The other functions are less commonly needed:
`blank'
     is like grow, except it just grows the space by size units without
     placing anything into this space
`alloc'
     is like `blank', but it wraps up the object and returns its
     starting address.
`chunk_size, base, next_free, alignment_mask, size, room'
     returns the appropriate class variables.
`grow_fast'
     places a character on the obstack without checking if there is
     enough room.
`blank_fast'
     like `blank', but without checking if there is enough room.
`shrink(int n)'
     shrink the current chunk by n bytes.
`contains(void* addr)'
     returns true if the Obstack holds the address addr.
   Here is a lightly edited version of the original C documentation:
   These functions operate a stack of objects.  Each object starts life
small, and may grow to maturity.  (Consider building a word syllable by
syllable.)  An object can move while it is growing.  Once it has been
"finished" it never changes address again.  So the "top of the stack"
is typically an immature growing object, while the rest of the stack is
of mature, fixed size and fixed address objects.
   These routines grab large chunks of memory, using the GNU C++ `new'
operator.  On occasion, they free chunks, via `delete'.
   Each independent stack is represented by a Obstack.
   One motivation for this package is the problem of growing char
strings in symbol tables.  Unless you are a "fascist pig with a
read-only mind" [Gosper's immortal quote from HAKMEM item 154, out of
context] you would not like to put any arbitrary upper limit on the
length of your symbols.
   In practice this often means you will build many short symbols and a
few long symbols.  At the time you are reading a symbol you don't know
how long it is.  One traditional method is to read a symbol into a
buffer, `realloc()'ating the buffer every time you try to read a symbol
that is longer than the buffer.  This is beaut, but you still will want
to copy the symbol from the buffer to a more permanent symbol-table
entry say about half the time.
   With obstacks, you can work differently.  Use one obstack for all
symbol names.  As you read a symbol, grow the name in the obstack
gradually.  When the name is complete, finalize it.  Then, if the
symbol exists already, free the newly read name.
   The way we do this is to take a large chunk, allocating memory from
low addresses.  When you want to build a symbol in the chunk you just
add chars above the current "high water mark" in the chunk.  When you
have finished adding chars, because you got to the end of the symbol,
you know how long the chars are, and you can create a new object.
Mostly the chars will not burst over the highest address of the chunk,
because you would typically expect a chunk to be (say) 100 times as
long as an average object.
   In case that isn't clear, when we have enough chars to make up the
object, *they are already contiguous in the chunk* (guaranteed) so we
just point to it where it lies.  No moving of chars is needed and this
is the second win: potentially long strings need never be explicitly
shuffled. Once an object is formed, it does not change its address
during its lifetime.
   When the chars burst over a chunk boundary, we allocate a larger
chunk, and then copy the partly formed object from the end of the old
chunk to the beginning of the new larger chunk.  We then carry on
accreting characters to the end of the object as we normally would.
   A special version of grow is provided to add a single char at a time
to a growing object.
   Summary:
   * We allocate large chunks.
   * We carve out one object at a time from the current chunk.
   * Once carved, an object never moves.
   * We are free to append data of any size to the currently growing
     object.
   * Exactly one object is growing in an obstack at any one time.
   * You can run one obstack per control block.
   * You may have as many control blocks as you dare.
   * Because of the way we do it, you can `unwind' a obstack back to a
     previous state. (You may remove objects much as you would with a
     stack.)
   The obstack data structure is used in many places in the GNU C++
compiler.
   Differences from the the GNU C version
  1. The obvious differences stemming from the use of classes and
     inline functions instead of structs and macros. The C `init' and
     `begin' macros are replaced by constructors.
  2. Overloaded function names are used for grow (and others), rather
     than the C `grow', `grow0', etc.
  3. All dynamic allocation uses the the built-in `new' operator.  This
     restricts flexibility by a little, but maintains compatibility
     with usual C++ conventions.
  4. There are now two versions of finish:
       1. finish() behaves like the C version.
       2. finish(char terminator) adds `terminator', and then calls
          `finish()'.  This enables the normal invocation of
          `finish(0)' to wrap up a string being grown
          character-by-character.
  5. There are special versions of grow(const char* s) and copy(const
     char* s) that add the null-terminated string `s' after computing
     its length.
  6. The shrink and contains functions are provided.
File: libg++.info,  Node: AllocRing,  Next: String,  Prev: Obstack,  Up: Top
The AllocRing class
*******************
   An AllocRing is a bounded ring (circular list), each of whose
elements contains a pointer to some space allocated via `new
char[some_size]'. The entries are used cyclicly.  The size, n, of the
ring is fixed at construction. After that, every nth use of the ring
will reuse (or reallocate) the same space. AllocRings are needed in
order to temporarily hold chunks of space that are needed transiently,
but across constructor-destructor scopes. They mainly useful for storing
strings containing formatted characters to print across various
functions and coercions. These strings are needed across routines, so
may not be deleted in any one of them, but should be recovered at some
point. In other words, an AllocRing is an extremely simple minded
garbage collection mechanism. The GNU C++ library used to use one
AllocRing for such formatting purposes, but it is being phased out, and
is now only used by obsolete functions.  These days, AllocRings are
probably not very useful.
   Support includes:
`AllocRing a(int n)'
     constructs an Alloc ring with n entries, all null.
`void* mem = a.alloc(sz)'
     moves the ring pointer to the next entry, and reuses the space if
     their is enough, also allocates space via new char[sz].
`int present = a.contains(void* ptr)'
     returns true if ptr is held in one of the ring entries.
`a.clear()'
     deletes all space pointed to in any entry. This is called
     automatically upon destruction.
`a.free(void* ptr)'
     If ptr is one of the entries, calls delete of the pointer, and
     resets to entry pointer to null.