home *** CD-ROM | disk | FTP | other *** search
/ Otherware / Otherware_1_SB_Development.iso / amiga / programm / language / gcc222.lha / info / libg++.info-2 < prev    next >
Encoding:
Text File  |  1992-07-19  |  46.5 KB  |  1,097 lines

  1. Info file libg++.info, produced by Makeinfo, -*- Text -*- from input
  2. file libg++.texinfo.
  3.  
  4. START-INFO-DIR-ENTRY
  5. * Libg++: (libg++).        The g++ library.
  6. END-INFO-DIR-ENTRY
  7.  
  8.    This file documents the features and implementation of The GNU C++
  9. library
  10.  
  11.    Copyright (C) 1988, 1991, 1992 Free Software Foundation, Inc.
  12.  
  13.    Permission is granted to make and distribute verbatim copies of
  14. this manual provided the copyright notice and this permission notice
  15. are preserved on all copies.
  16.  
  17.    Permission is granted to copy and distribute modified versions of
  18. this manual under the conditions for verbatim copying, provided also
  19. that the section entitled "GNU Library General Public License" is
  20. included exactly as in the original, and provided that the entire
  21. resulting derived work is distributed under the terms of a permission
  22. notice identical to this one.
  23.  
  24.    Permission is granted to copy and distribute translations of this
  25. manual into another language, under the above conditions for modified
  26. versions, except that the section entitled "GNU Library General Public
  27. License" and this permission notice may be included in translations
  28. approved by the Free Software Foundation instead of in the original
  29. English.
  30.  
  31. 
  32. File: libg++.info,  Node: Proto,  Next: Representations,  Prev: OK,  Up: Top
  33.  
  34. Introduction to container class prototypes
  35. ******************************************
  36.  
  37.    As a temporary mechanism enabling the support of generic classes,
  38. the GNU C++ Library distribution contains a directory (`g++-include')
  39. of files designed to serve as the basis for generating container
  40. classes of specified elements.  These files can be used to generate
  41. `.h' and `.cc' files in the current directory via a supplied shell
  42. script program that performs simple textual substitution to create
  43. specific classes.
  44.  
  45.    While these classes are generated independently, and thus share no
  46. code, it is possible to create versions that do share code among
  47. subclasses. For example, using `typedef void* ent', and then
  48. generating a `entList' class, other derived classes could be created
  49. using the `void*' coercion method described in Stroustrup, pp204-210.
  50.  
  51.    This very simple class-generation facility is useful enough to serve
  52. current purposes, but will be replaced with a more coherent mechanism
  53. for handling C++ generics in a way that minimally disrupts current
  54. usage.  Without knowing exactly when or how parametric classes might be
  55. added to the C++ language, provision of this simplest possible
  56. mechanism, textual substitution, appears to be the safest strategy,
  57. although it does require certain redundancies and awkward
  58. constructions.
  59.  
  60.    Specific classes may be generated via the `genclass' shell script
  61. program. This program has arguments specifying the kinds of base
  62. types(s) to be used. Specifying base types requires two arguments. The
  63. first is the name of the base type, which may be any named type, like
  64. `int' or `String'. Only named types are supported; things like `int*'
  65. are not accepted. However, pointers like this may be used by supplying
  66. the appropriate typedefs (e.g., editing the resulting files to include
  67. `typedef int* intp;'). The type name must be followed by one of the
  68. words `val' or `ref', to indicate whether the base elements should be
  69. passed to functions by-value or by-reference.
  70.  
  71.    You can specify basic container classes using `genclass base
  72. [val,ref] proto', where `proto' is the name of the class being
  73. generated.  Container classes like dictionaries and maps that require
  74. two types may be specified via `genclass -2 keytype [val, ref],
  75. basetype [val, ref] proto', where the key type is specified first and
  76. the contents type second.  The resulting classnames and filenames are
  77. generated by prepending the specified type names to the prototype
  78. names, and separating the filename parts with dots.  For example,
  79. `genclass int val List' generates class `intList' residing in files
  80. `int.List.h' and `int.List.cc'. `genclass -2 String ref int val VHMap'
  81. generates (the awkward, but unavoidable) class name `StringintVHMap'.
  82. Of course, programmers may use `typedef' or simple editing to create
  83. more appropriate names.  The existence of dot seperators in file names
  84. allows the use of GNU make to help automate configuration and
  85. recompilation. An example Makefile exploiting such capabilities may be
  86. found in the `libg++/proto-kit' directory.
  87.  
  88.    The `genclass' utility operates via simple text substitution using
  89. `sed'. All occurrences of the pseudo-types `<T>' and `<C>' (if there
  90. are two types) are replaced with the indicated type, and occurrences
  91. of `<T&>' and `<C&>' are replaced by just the types, if `val' is
  92. specified, or types followed by "&" if `ref' is specified.
  93.  
  94.    Programmers will frequently need to edit the `.h' file in order to
  95. insert additional `#include' directives or other modifications.  A
  96. simple utility, `prepend-header' to prepend other `.h' files to
  97. generated files is provided in the distribution.
  98.  
  99.    One dubious virtue of the prototyping mechanism is that, because
  100. sources files, not archived library classes, are generated, it is
  101. relatively simple for programmers to modify container classes in the
  102. common case where slight variations of standard container classes are
  103. required.
  104.  
  105.    It is often a good idea for programmers to archive (via `ar')
  106. generated classes into `.a' files so that only those class functions
  107. actually used in a given application will be loaded.  The test
  108. subdirectory of the distribution shows an example of this.
  109.  
  110.    Because of `#pragma interface' directives, the `.cc' files should
  111. be compiled with `-O' or `-DUSE_LIBGXX_INLINES' enabled.
  112.  
  113.    Many container classes require specifications over and above the
  114. base class type. For example, classes that maintain some kind of
  115. ordering of elements require specification of a comparison function
  116. upon which to base the ordering.  This is accomplished via a prototype
  117. file `defs.hP' that contains macros for these functions. While these
  118. macros default to perform reasonable actions, they can and should be
  119. changed in particular cases. Most prototypes require only one or a few
  120. of these. No harm is done if unused macros are defined to perform
  121. nonsensical actions. The macros are:
  122.  
  123. `DEFAULT_INITIAL_CAPACITY'
  124.      The intitial capacity for containers (e.g., hash tables) that
  125.      require an initial capacity argument for constructors.  Default:
  126.      100
  127.  
  128. `<T>EQ(a, b)'
  129.      return true if a is considered equal to b for the purposes of
  130.      locating, etc., an element in a container.  Default: (a == b)
  131.  
  132. `<T>LE(a, b)'
  133.      return true if a is less than or equal to b Default: (a <= b)
  134.  
  135. `<T>CMP(a, b)'
  136.      return an integer < 0 if a<b, 0 if a==b, or > 0 if a>b.  Default:
  137.      (a <= b)? (a==b)? 0 : -1 : 1
  138.  
  139. `<T>HASH(a)'
  140.      return an unsigned integer representing the hash of a.  Default:
  141.      hash(a) ; where extern unsigned int hash(<T&>).  (note: several
  142.      useful hash functions are declared in builtin.h and defined in
  143.      hash.cc)
  144.  
  145.    Nearly all prototypes container classes support container traversal
  146. via `Pix' pseudo indices, as described elsewhere.
  147.  
  148.    All object containers must perform either a `X::X(X&)' (or `X::X()'
  149. followed by `X::operator =(X&)') to copy objects into containers. 
  150. (The latter form is used for containers built from C++ arrays, like
  151. `VHSets'). When containers are destroyed, they invoke `X::~X()'.  Any
  152. objects used in containers must have well behaved constructors and
  153. destructors. If you want to create containers that merely reference
  154. (point to) objects that reside elsewhere, and are not copied or
  155. destroyed inside the container, you must use containers of pointers,
  156. not containers of objects.
  157.  
  158.    All prototypes are designed to generate *HOMOGENOUS* container
  159. classes.  There is no universally applicable method in C++ to support
  160. heterogenous object collections with elements of various subclasses of
  161. some specified base class. The only way to get heterogenous structures
  162. is to use collections of pointers-to-objects, not collections of
  163. objects (which also requires you to take responsibility for managing
  164. storage for the objects pointed to yourself).
  165.  
  166.    For example, the following usage illustrates a commonly encountered
  167. danger in trying to use container classes for heterogenous structures:
  168.  
  169.      class Base { int x; ...}
  170.      class Derived : public Base { int y; ... }
  171.      
  172.      BaseVHSet s; // class BaseVHSet generated via something like
  173.                   // `genclass Base ref VHSet'
  174.      
  175.      void f()
  176.      {
  177.        Base b;
  178.        s.add(b); // OK
  179.      
  180.        Derived d;
  181.        s.add(d);  // (CHOP!)
  182.      }
  183.  
  184.    At the line flagged with `(CHOP!)', a `Base::Base(Base&)' is called
  185. inside `Set::add(Base&)'--*not* `Derived::Derived(Derived&)'. 
  186. Actually, in `VHSet', a `Base::operator =(Base&)', is used instead to
  187. place the element in an array slot, but with the same effect.  So only
  188. the Base part is copied as a `VHSet' element (a so-called
  189. chopped-copy). In this case, it has an `x' part, but no `y' part; and
  190. a Base, not Derived, vtable. Objects formed via chopped copies are
  191. rarely sensible.
  192.  
  193.    To avoid this, you must resort to pointers:
  194.  
  195.      typedef Base* BasePtr;
  196.      
  197.      BasePtrVHSet s; // class BaseVHSet generated via something like
  198.                      // `genclass BasePtr val VHSet'
  199.      
  200.      void f()
  201.      {
  202.        Base* bp = new Base;
  203.        s.add(b);
  204.      
  205.        Base* dp = new Derived;
  206.        s.add(d);  // works fine.
  207.      
  208.        // Don't forget to delete bp and dp sometime.
  209.        // The VHSet won't do this for you.
  210.      }
  211.  
  212. Example
  213. =======
  214.  
  215.    The prototypes can be difficult to use on first attempt. Here is an
  216. example that may be helpful. The utilities in the `proto-kit' simplify
  217. much of the actions described, but are not used here.
  218.  
  219.    Suppose you create a class `Person', and want to make an Map that
  220. links the social security numbers associated with each person. You
  221. start off with a file `Person.h'
  222.  
  223.  
  224.      #include <String.h>
  225.      
  226.      class Person
  227.      {
  228.        String nm;
  229.        String addr;
  230.        //...
  231.      public:
  232.        const String& name() { return nm; }
  233.        const String& address() { return addr; }
  234.        void          print() { ... }
  235.        //...
  236.      }
  237.  
  238.    And in file `SSN.h',
  239.  
  240.      typedef unsigned int SSN;
  241.  
  242.    Your first decision is what storage/usage strategy to use. There are
  243. several reasonable alternatives here: You might create an "object
  244. collection" of Persons, a "pointer collection" of pointers-to-Persons,
  245. or even a simple String map, housing either copies of pointers to the
  246. names of Persons, since other fields are unused for purposes of the
  247. Map. In an object collection, instances of class Person "live" inside
  248. the Map, while in a pointer collection, the instances live elswhere.
  249. Also, as above, if instances of subclasses of Person are to be used
  250. inside the Map, you must use pointers. In a String Map, the same
  251. difference holds, but now only for the name fields. Any of these
  252. choices might make sense in particular applications.
  253.  
  254.    The second choice is the Map implementation strategy. Either a tree
  255. or a hash table might make sense. Suppose you want an AVL tree Map. 
  256. There are two things to now check. First, as an object collection, the
  257. AVLMap requires that the elsement class contain an `X(X&)'
  258. constructor. In C++, if you don't specify such a constructor, one is
  259. constructed for you, but it is a very good idea to always do this
  260. yourself, to avoid surprises. In this example, you'd use something like
  261.  
  262.      class Person
  263.      { ...;
  264.          Person(const Person& p) :nm(p.nm), addr(p.addr) {}
  265.      };
  266.  
  267.    Also, an AVLMap requires a comparison function for elements in order
  268. to maintain order. Rather than requiring you to write a particular
  269. comparison function, a `defs' file is consulted to determine how to
  270. compare items. You must create and edit such a file.
  271.  
  272.    Before creating `Person.defs.h', you must first make one additional
  273. decision. Should the Map member functions like `m.contains(p)' take
  274. arguments (`p') by reference (i.e., typed as `int Map::contains(const
  275. Person& p)' or by value (i.e., typed as `int Map::contains(const
  276. Person p)'. Generally, for user-defined classes, you want to pass by
  277. reference, and for builtins and pointers, to pass by value. SO you
  278. should pick by-reference.
  279.  
  280.    You can now create `Person.defs.h' via `genclass Person ref defs'. 
  281. This creates a simple skeleton that you must edit. First, add
  282. `#include "Person.h"' to the top. Second, edit the `<T>CMP(a,b)' macro
  283. to compare on name, via
  284.  
  285.      #define <T>CMP(a, b) ( compare(a.name(), b.name()) )
  286.  
  287. which invokes the `int compare(const String&, const String&)' function
  288. from `String.h'. Of course, you could define this in any other way as
  289. well. In fact, the default versions in the skelaton turn out to be OK
  290. (albeit inefficient) in this particular example.
  291.  
  292.    You may also want to create file `SSN.defs.h'. Here, choosing
  293. call-by-value makes sense, and since no other capabilities (like
  294. comparison functions) of the SSNs are used (and the defaults are OK
  295. anyway), you'd type
  296.  
  297.      genclass SSN val defs
  298.  
  299. and then edit to place `#include "SSN.h"' at the top.
  300.  
  301.    Finally, you can generate the classes. First, generate the base
  302. class for Maps via
  303.  
  304.      genclass -2 Person ref SSN val Map
  305.  
  306. This generates only the abstract class, not the implementation, in file
  307. `Person.SSN.Map.h' and `Person.SSN.Map.cc'.  To create the AVL
  308. implementation, type
  309.  
  310.      genclass -2 Person ref SSN val AVLMap
  311.  
  312. This creates the class `PersonSSNAVLMap', in `Person.SSN.AVLMap.h' and
  313. `Person.SSN.AVLMap.cc'.
  314.  
  315.    To use the AVL implementation, compile the two generated `.cc'
  316. files, and specify `#include "Person.SSN.AVLMap.h"' in the application
  317. program.  All other files are included in the right ways automatically.
  318.  
  319.    One last consideration, peculiar to Maps, is to pick a reasonable
  320. default contents when declaring an AVLMap. Zero might be appropriate
  321. here, so you might declare a Map,
  322.  
  323.      PersonSSNAVLMap m((SSN)0);
  324.  
  325.    Suppose you wanted a `VHMap' instead of an `AVLMap' Besides
  326. generating different implementations, there are two differences in how
  327. you should prepare the `defs' file. First, because a VHMap uses a C++
  328. array internally, and because C++ array slots are initialized
  329. differently than single elements, you must ensure that class Person
  330. contains (1) a no-argument constructor, and (2) an assigment operator. 
  331. You could arrange this via
  332.  
  333.      class Person
  334.      { ...;
  335.          Person() {}
  336.        void operator = (const Person& p) { nm = p.nm; addr = p.addr; }
  337.      };
  338.  
  339.    (The lack of action in the constructor is OK here because `Strings'
  340. posess usable no-argument constructors.)
  341.  
  342.    You also need to edit `Person.defs.h' to indicate a usable hash
  343. function and default capacity, via something like
  344.  
  345.      #include <builtin.h>
  346.      #define <T>HASH(x)  (hashpjw(x.name().chars()))
  347.      #define DEFAULT_INITIAL_CAPACITY 1000
  348.  
  349.    Since the `hashpjw' function from `builtin.h' is appropriate here.
  350. Changing the default capacity to a value expected to exceed the actual
  351. capacity helps to avoid "hidden" inefficiencies when a new VHMap is
  352. created without overriding the default, which is all too easy to do.
  353.  
  354.    Otherwise, everything is the same as above, substituting `VHMap'
  355. for `AVLMap'.
  356.  
  357. 
  358. File: libg++.info,  Node: Representations,  Next: Expressions,  Prev: Proto,  Up: Top
  359.  
  360. Variable-Sized Object Representation
  361. ************************************
  362.  
  363.    One of the first goals of the GNU C++ library is to enrich the
  364. kinds of basic classes that may be considered as (nearly) "built into"
  365. C++. A good deal of the inspiration for these efforts is derived from
  366. considering features of other type-rich languages, particularly Common
  367. Lisp and Scheme.  The general characteristics of most class and friend
  368. operators and functions supported by these classes has been heavily
  369. influenced by such languages.
  370.  
  371.    Four of these types, Strings, Integers, BitSets, and BitStrings (as
  372. well as associated and/or derived classes) require representations
  373. suitable for managing variable-sized objects on the free-store. The
  374. basic technique used for all of these is the same, although various
  375. details necessarily differ from class to class.
  376.  
  377.    The general strategy for representing such objects is to create
  378. chunks of memory that include both header information (e.g., the size
  379. of the object), as well as the variable-size data (an array of some
  380. sort) at the end of the chunk. Generally the maximum size of an object
  381. is limited to something less than all of addressable memory, as a
  382. safeguard. The minimum size is also limited so as not to waste
  383. allocations expanding very small chunks. Internally, chunks are
  384. allocated in blocks well-tuned to the performance of the `new'
  385. operator.
  386.  
  387.    Class elements themselves are merely pointers to these chunks. 
  388. Most class operations are performed via inline "translation" functions
  389. that perform the required operation on the corresponding
  390. representation. However, constructors and assignments operate by
  391. copying entire representations, not just pointers.
  392.  
  393.    No attempt is made to control temporary creation in expressions and
  394. functions involving these classes. Users of previous versions of the
  395. classes will note the disappearance of both "Tmp" classes and
  396. reference counting. These were dropped because, while they did improve
  397. performance in some cases, they obscure class mechanics, lead
  398. programmers into the false belief that they need not worry about such
  399. things, and occaisionally have paradoxical behavior.
  400.  
  401.    These variable-sized object classes are integrated as well as
  402. possible into C++. Most such classes possess converters that allow
  403. automatic coercion both from and to builtin basic types. (e.g., char*
  404. to and from String, long int to and from Integer, etc.). There are
  405. pro's and con's to circular converters, since they can sometimes lead
  406. to the conversion from a builtin type through to a class function and
  407. back to a builtin type without any special attention on the part of
  408. the programmer, both for better and worse.
  409.  
  410.    Most of these classes also provide special-case operators and
  411. functions mixing basic with class types, as a way to avoid
  412. constructors in cases where the operations do not rely on anything
  413. special about the representations.  For example, there is a special
  414. case concatenation operator for a String concatenated with a char,
  415. since building the result does not rely on anything about the String
  416. header. Again, there are arguments both for and against this approach.
  417. Supporting these cases adds a non-trivial degree of (mainly inline)
  418. function proliferation, but results in more efficient operations.
  419. Efficiency wins out over parsimony here, as part of the goal to
  420. produce classes that provide sufficient functionality and efficiency
  421. so that programmers are not tempted to try to manipulate or bypass the
  422. underlying representations.
  423.  
  424. 
  425. File: libg++.info,  Node: Expressions,  Next: Pix,  Prev: Representations,  Up: Top
  426.  
  427. Some guidelines for using expression-oriented classes
  428. *****************************************************
  429.  
  430.    The fact that C++ allows operators to be overloaded for user-defined
  431. classes can make programming with library classes like `Integer',
  432. `String', and so on very convenient. However, it is worth becoming
  433. familiar with some of the inherent limitations and problems associated
  434. with such operators.
  435.  
  436.    Many operators are *constructive*, i.e., create a new object based
  437. on some function of some arguments. Sometimes the creation of such
  438. objects is wasteful. Most library classes supporting expressions
  439. contain facilities that help you avoid such waste.
  440.  
  441.    For example, for `Integer a, b, c; ...;  c = a + b + a;', the plus
  442. operator is called to sum a and b, creating a new temporary object as
  443. its result. This temporary is then added with a, creating another
  444. temporary, which is finally copied into c, and the temporaries are then
  445. deleted. In other words, this code might have an effect similar to
  446. `Integer a, b, c; ...; Integer t1(a); t1 += b; Integer t2(t1); t2 +=
  447. a; c = t2;'.
  448.  
  449.    For small objects, simple operators, and/or non-time/space critical
  450. programs, creation of temporaries is not a big problem. However, often,
  451. when fine-tuning a program, it may be a good idea to rewrite such code
  452. in a less pleasant, but more efficient manner.
  453.  
  454.    For builtin types like ints, and floats, C and C++ compilers already
  455. know how to optimize such expressions to reduce the need for
  456. temporaries. Unfortunately, this is not true for C++ user defined
  457. types, for the simple (but very annoying, in this context) reason that
  458. nothing at all is guaranteed about the semantics of overloaded
  459. operators and their interrelations. For example, if the above
  460. expression just involved ints, not Integers, a compiler might
  461. internally convert the statement into something like ` c += a; c += b;
  462. c+= a; ', or perhaps something even more clever.  But since C++ does
  463. not know that Integer operator += has any relation to Integer operator
  464. +, A C++ compiler cannot do this kind of expression optimization
  465. itself.
  466.  
  467.    In many cases, you can avoid construction of temporaries simply by
  468. using the assignment versions of operators whenever possible, since
  469. these versions create no temporaries. However, for maximum flexibility,
  470. most classes provide a set of "embedded assembly code" procedures that
  471. you can use to fully control time, space, and evaluation strategies. 
  472. Most of these procedures are "three-address" procedures that take two
  473. `const' source arguments, and a destination argument. The procedures
  474. perform the appropriate actions, placing the results in the
  475. destination (which is may involve overwriting old contents). These
  476. procedures are designed to be fast and robust. In particular, aliasing
  477. is always handled correctly, so that, for example `add(x, x, x); ' is
  478. perfectly OK. (The names of these procedures are listed along with the
  479. classes.)
  480.  
  481.    For example, suppose you had an Integer expression ` a = (b - a) *
  482. -(d / c); '
  483.  
  484.    This would be compiled as if it were ` Integer t1=b-a; Integer
  485. t2=d/c; Integer t3=-t2; Integer t4=t1*t3; a=t4;'
  486.  
  487.    But, with some manual cleverness, you might yourself some up with `
  488. sub(a, b, a); mul(a, d, a); div(a, c, a); '
  489.  
  490.    A related phenomenon occurs when creating your own constructive
  491. functions returning instances of such types. Suppose you wanted to
  492. write function `Integer f(const Integer& a) { Integer r = a;  r += a;
  493. return r; }'
  494.  
  495.    This function, when called (as in ` a = f(a); ') demonstrates a
  496. similar kind of wasted copy. The returned value r must be copied out
  497. of the function before it can be used by the caller. In GNU C++, there
  498. is an alternative via the use of named return values.  Named return
  499. values allow you to manipulate the returned object directly, rather
  500. than requiring you to create a local inside a function and then copy
  501. it out as the returned value. In this example, this can be done via
  502. `Integer f(const Integer& a) return r(a) { r += a; return; }'
  503.  
  504.    A final guideline: The overloaded operators are very convenient, and
  505. much clearer to use than procedural code. It is almost always a good
  506. idea to make it right, *then* make it fast, by translating expression
  507. code into procedural code after it is known to be correct.
  508.  
  509. 
  510. File: libg++.info,  Node: Pix,  Next: Headers,  Prev: Expressions,  Up: Top
  511.  
  512. Pseudo-indexes
  513. **************
  514.  
  515.    Many useful classes operate as containers of elements. Techniques
  516. for accessing these elements from a container differ from class to
  517. class.  In the GNU C++ library, access methods have been partially
  518. standardized across different classes via the use of pseudo-indexes
  519. called `Pixes'.  A `Pix' acts in some ways like an index, and in some
  520. ways like a pointer. (Their underlying representations are just
  521. `void*' pointers). A `Pix' is a kind of "key" that is translated into
  522. an element access by the class.  In virtually all cases, `Pixes' are
  523. pointers to some kind internal storage cells. The containers use these
  524. pointers to extract items.
  525.  
  526.    `Pixes' support traversal and inspection of elements in a
  527. collection using analogs of array indexing. However, they are
  528. pointer-like in that `0' is treated as an invalid `Pix', and unsafe
  529. insofar as programmers can attempt to access nonexistent elements via
  530. dangling or otherwise invalid `Pixes' without first checking for their
  531. validity.
  532.  
  533.    In general it is a very bad idea to perform traversals in the the
  534. midst of destructive modifications to containers.
  535.  
  536.    Typical applications might include code using the idiom
  537.  
  538.      for (Pix i = a.first(); i != 0; a.next(i)) use(a(i));
  539.  
  540.    for some container `a' and function `use'.
  541.  
  542.    Classes supporting the use of `Pixes' always contain the following
  543. methods, assuming a container `a' of element types of `Base'.
  544.  
  545. `Pix i = a.first()'
  546.      Set i to index the first element of a or 0 if a is empty.
  547.  
  548. `a.next(i)'
  549.      advance i to the next element of a or 0 if there is no next
  550.      element;
  551.  
  552. `Base x = a(i); a(i) = x;'
  553.      a(i) returns a reference to the element indexed by i.
  554.  
  555. `int present = a.owns(i)'
  556.      returns true if Pix i is a valid Pix in a. This is often a
  557.      relatively slow operation, since the collection must usually
  558.      traverse through elements to see if any correspond to the Pix.
  559.  
  560.    Some container classes also support backwards traversal via
  561.  
  562. `Pix i = a.last()'
  563.      Set i to the last element of a or 0 if a is empty.
  564.  
  565. `a.prev(i)'
  566.      sets i to the previous element in a, or 0 if there is none.
  567.  
  568.    Collections supporting elements with an equality operation possess
  569.  
  570. `Pix j = a.seek(x)'
  571.      sets j to the index of the first occurrence of x, or 0 if x is
  572.      not contained in a.
  573.  
  574.    Bag classes possess
  575.  
  576. `Pix j = a.seek(x, Pix from = 0)'
  577.      sets j to the index of the next occurrence of x following i, or 0
  578.      if x is not contained in a. If i == 0, the first occurrence is
  579.      returned.
  580.  
  581.    Set, Bag, and PQ classes possess
  582.  
  583. `Pix j = a.add(x) (or a.enq(x) for priority queues)'
  584.      add x to the collection, returning its Pix. The Pix of an item
  585.      can change in collections where further additions and deletions
  586.      involve the actual movement of elements (currently in OXPSet,
  587.      OXPBag, XPPQ, VOHSet), but in all other cases, an item's Pix may
  588.      be considered a permanent key to its location.
  589.  
  590. 
  591. File: libg++.info,  Node: Headers,  Next: Builtin,  Prev: Pix,  Up: Top
  592.  
  593. Header files for interfacing C++ to C
  594. *************************************
  595.  
  596.    The following files are provided so that C++ programmers may invoke
  597. common C library and system calls. The names and contents of these
  598. files are subject to change in order to be compatible with the
  599. forthcoming GNU C library. Other files, not listed here, are simply
  600. C++-compatible interfaces to corresponding C library files.
  601.  
  602. `values.h'
  603.      A collection of constants defining the numbers of bits in builtin
  604.      types, minimum and maximum values, and the like. Most names are
  605.      the same as those found in `values.h' found on Sun systems.
  606.  
  607. `std.h'
  608.      A collection of common system calls and `libc.a' functions.  Only
  609.      those functions that can be declared without introducing new type
  610.      definitions (socket structures, for example) are provided. Common
  611.      `char*' functions (like `strcmp') are among the declarations. All
  612.      functions are declared along with their library names, so that
  613.      they may be safely overloaded.
  614.  
  615. `string.h'
  616.      This file merely includes `<std.h>', where string function
  617.      prototypes are declared. This is a workaround for the fact that
  618.      system `string.h' and `strings.h' files often differ in contents.
  619.  
  620. `osfcn.h'
  621.      This file merely includes `<std.h>', where system function
  622.      prototypes are declared.
  623.  
  624. `libc.h'
  625.      This file merely includes `<std.h>', where C library function
  626.      prototypes are declared.
  627.  
  628. `math.h'
  629.      A collection of prototypes for functions usually found in libm.a,
  630.      plus some `#define'd constants that appear to be consistent with
  631.      those provided in the AT&T version. The value of `HUGE' should be
  632.      checked before using. Declarations of all common math functions
  633.      are preceded with `overload' declarations, since these are
  634.      commonly overloaded.
  635.  
  636. `stdio.h'
  637.      Declaration of `FILE' (`_iobuf'), common macros (like `getc'),
  638.      and function prototypes for `libc.a' functions that operate on
  639.      `FILE*''s. The value `BUFSIZ' and the declaration of `_iobuf'
  640.      should be checked before using.
  641.  
  642. `assert.h'
  643.      C++ versions of assert macros.
  644.  
  645. `generic.h'
  646.      String concatenation macros useful in creating generic classes. 
  647.      They are similar in function to the AT&T CC versions.
  648.  
  649. `new.h'
  650.      Declarations of the default global operator new, the two-argument
  651.      placement version, and associated error handlers.
  652.  
  653. 
  654. File: libg++.info,  Node: Builtin,  Next: New,  Prev: Headers,  Up: Top
  655.  
  656. Utility functions for built in types
  657. ************************************
  658.  
  659.    Files `builtin.h' and corresponding `.cc' implementation files
  660. contain various convenient inline and non-inline utility functions.
  661. These include useful enumeration types, such as `TRUE', `FALSE' ,the
  662. type definition for pointers to libg++ error handling functions, and
  663. the following functions.
  664.  
  665. `long abs(long x); double abs(double x);'
  666.      inline versions of abs. Note that the standard libc.a version,
  667.      `int abs(int)' is *not* declared as inline.
  668.  
  669. `void clearbit(long& x, long b);'
  670.      clears the b'th bit of x (inline).
  671.  
  672. `void setbit(long& x, long b);'
  673.      sets the b'th bit of x (inline)
  674.  
  675. `int testbit(long x, long b);'
  676.      returns the b'th bit of x (inline).
  677.  
  678. `int even(long y);'
  679.      returns true if x is even (inline).
  680.  
  681. `int odd(long y);'
  682.      returns true is x is odd (inline).
  683.  
  684. `int sign(long x); int sign(double x);'
  685.      returns -1, 0, or 1, indicating whether x is less than, equal to,
  686.      or greater than zero (inline).
  687.  
  688. `long gcd(long x, long y);'
  689.      returns the greatest common divisor of x and y.
  690.  
  691. `long lcm(long x, long y);'
  692.      returns the least common multiple of x and y.
  693.  
  694. `long lg(long x);'
  695.      returns the floor of the base 2 log of x.
  696.  
  697. `long pow(long x, long y); double pow(double x, long y);'
  698.      returns x to the integer power y using via the iterative O(log y)
  699.      "Russian peasant" method.
  700.  
  701. `long sqr(long x); double sqr(double x);'
  702.      returns x squared (inline).
  703.  
  704. `long sqrt(long y);'
  705.      returns the floor of the square root of x.
  706.  
  707. `unsigned int hashpjw(const char* s);'
  708.      a hash function for null-terminated char* strings using the
  709.      method described in Aho, Sethi, & Ullman, p 436.
  710.  
  711. `unsigned int multiplicativehash(int x);'
  712.      a hash function for integers that returns the lower bits of
  713.      multiplying x by the golden ratio times pow(2, 32).  See Knuth,
  714.      Vol 3, p 508.
  715.  
  716. `unsigned int foldhash(double x);'
  717.      a hash function for doubles that exclusive-or's the first and
  718.      second words of x, returning the result as an integer.
  719.  
  720. `double start_timer()'
  721.      Starts a process timer.
  722.  
  723. `double return_elapsed_time(double last_time)'
  724.      Returns the process time since last_time.  If last_time == 0
  725.      returns the time since the last start_timer.  Returns -1 if
  726.      start_timer was not first called.
  727.  
  728.    File `Maxima.h' includes versions of `MAX, MIN' for builtin types.
  729.  
  730.    File `compare.h' includes versions of `compare(x, y)' for buitlin
  731. types. These return negative if the first argument is less than the
  732. second, zero for equal, and positive for greater.
  733.  
  734. 
  735. File: libg++.info,  Node: New,  Next: IOStream,  Prev: Builtin,  Up: Top
  736.  
  737. Library dynamic allocation primitives
  738. *************************************
  739.  
  740.    Libg++ contains versions of `malloc, free, realloc' that were
  741. designed to be well-tuned to C++ applications. The source file
  742. `malloc.c' contains some design and implementation details.  Here are
  743. the major user-visible differences from most system malloc routines:
  744.  
  745.   1. These routines *overwrite* storage of freed space. This means
  746.      that it is never permissible to use a `delete''d object in any
  747.      way. Doing so will either result in trapped fatal errors or
  748.      random aborts within malloc, free, or realloc.
  749.  
  750.   2. The routines tend to perform well when a large number of objects
  751.      of the same size are allocated and freed. You may find that it is
  752.      not worth it to create your own special allocation schemes in
  753.      such cases.
  754.  
  755.   3. The library sets top-level `operator new()' to call malloc and
  756.      `operator delete()' to call free. Of course, you may override
  757.      these definitions in C++ programs by creating your own operators
  758.      that will take precedence over the library versions. However, if
  759.      you do so, be sure to define *both* `operator new()' and `operator
  760.      delete()'.
  761.  
  762.   4. These routines do *not* support the odd convention, maintained by
  763.      some versions of malloc, that you may call `realloc' with a
  764.      pointer that has been `free''d.
  765.  
  766.   5. The routines automatically perform simple checks on `free''d
  767.      pointers that can often determine whether users have accidentally
  768.      written beyond the boundaries of allocated space, resulting in a
  769.      fatal error.
  770.  
  771.   6. The function `malloc_usable_size(void* p)' returns the number of
  772.      bytes actually allocated for `p'. For a valid pointer (i.e., one
  773.      that has been `malloc''d or `realloc''d but not yet `free''d)
  774.      this will return a number greater than or equal to the requested
  775.      size, else it will normally return 0. Unfortunately, a non-zero
  776.      return can not be an absolutely perfect indication of lack of
  777.      error. If a chunk has been `free''d but then re-allocated for a
  778.      different purpose somewhere elsewhere, then `malloc_usable_size'
  779.      will return non-zero. Despite this, the function can be very
  780.      valuable for performing run-time consistency checks.
  781.  
  782.   7. `malloc' requires 8 bytes of overhead per allocated chunk, plus a
  783.      mmaximum alignment adjustment of 8 bytes. The number of bytes of
  784.      usable space is exactly as requested, rounded to the nearest 8
  785.      byte boundary.
  786.  
  787.   8. The routines do *not* contain any synchronization support for
  788.      multiprocessing. If you perform global allocation on a shared
  789.      memory multiprocessor, you should disable compilation and use of
  790.      libg++ malloc in the distribution `Makefile' and use your system
  791.      version of malloc.
  792.  
  793. 
  794. File: libg++.info,  Node: IOStream,  Next: Stream,  Prev: New,  Up: Top
  795.  
  796. The new input/output classes
  797. ****************************
  798.  
  799.    The iostream classes implement most of the features of AT&T version
  800. 2.0 iostream library classes, and most of the features of the ANSI
  801. X3J16 library draft (which is based on the AT&T design).  The iostream
  802. classes replace all of the old stream classes in previous versions of
  803. libg++.  It is not totally compatible, so you will probably need to
  804. change your code in places.
  805.  
  806. The `streambuf' layer
  807. =====================
  808.  
  809.    The lower level abstraction is the `streambuf' layer.  A
  810. `streambuf' (or one of the classes derived from it) implements a
  811. character source and/or sink, usually with buffering.
  812.  
  813.    Classes derived from `streambuf' include:
  814.  
  815.    * A `filebuf' is used for reading and writing from files.
  816.  
  817.    * A `strstreambuf' can raed and write from a string in main memory. 
  818.      The string buffer will be re-allocated as needed it, unless it is
  819.      "frozen".
  820.  
  821.    * An `indirectbuf' just forwards all read/write requests to some
  822.      other buffer.
  823.  
  824.    * A `procbuf' can read from or write to a Unix process.
  825.  
  826.    * A `parsebuf' has some useful features for scanning text:  It
  827.      keeps track of line and column numbers, and it guarantees to
  828.      remember at least the current line (with the linefeeds at either
  829.      end), so you can arbitrarily backup within that time.  WARNING: 
  830.      The interface is likely to change.
  831.  
  832.    * An `edit_streambuf' reads and writes into a region of an
  833.      `edit_buffer' called an `edit_string'.  Emacs-like marks are
  834.      supported, and sub-strings are first-class functions.  WARNING:
  835.      The interface is almost certain to change.
  836.  
  837. The istream and ostream classes
  838. ===============================
  839.  
  840.    The stream layer provides an efficient, easy-to-use, and type-secure
  841. interface between C++ and an underlying `streambuf'.
  842.  
  843.    Most C++ textbooks will at least given an overview of the stream
  844. classes.  Some libg++ specifics:
  845.  
  846. `istream::get(char* s, int maxlength, char terminator='\n')'
  847.      Behaves as described by Stroustrup. It reads at most maxlength
  848.      characters into s, stopping when the terminator is read, and
  849.      pushing the terminator back into the input stream.
  850.  
  851. `istream::getline(char* s, int maxlength, char terminator = '\n')'
  852.      Behaves like get, except that the terminator is read (and not
  853.      pushed back), though it does not become part of the string.
  854.  
  855. `istream::gets(char** ss, char terminator = '\n')'
  856.      reads in a line (as in get) of unknown length, and places it in a
  857.      free-store allocated spot and attaches it to `ss'. The programmer
  858.      must take responsibility for deleting `*ss' when it is no longer
  859.      needed.
  860.  
  861. `ostream::form(const char* format...)'
  862.      outputs `printf'-formated data.
  863.  
  864. The SFile class
  865. ===============
  866.  
  867.    `SFile' (short for structure file) is provided both as a
  868. demonstration of how to build derived classes from `iostream', and as
  869. a useful class for processing files containing fixed-record-length
  870. binary data.  They are created with constructors with one additional
  871. argument declaring the size (in bytes, i.e., `sizeof' units) of the
  872. records.  `get', will input one record, `put' will output one, and the
  873. `[]' operator, as in `f[i]', will position to the i'th record. If the
  874. file is being used mainly for random access, it is often a good idea
  875. to eliminate internal buffering via `setbuf' or `raw'. Here is an
  876. example:
  877.  
  878.      class record
  879.      {
  880.        friend class SFile;
  881.        char c; int i; double d;     // or anything at all
  882.      };
  883.      
  884.      void demo()
  885.      {
  886.        record r;
  887.        SFile recfile("mydatafile", sizeof(record), ios::in|ios::out);
  888.        recfile.raw();
  889.        for (int i = 0; i < 10; ++i)  // ... write some out
  890.        {
  891.          r = something();
  892.          recfile.put(&r);            // use '&r' for proper coercion
  893.        }
  894.        for (i = 9; i >= 0; --i)      // now use them in reverse order
  895.        {
  896.          recfile[i].get(&r);
  897.          do_something_with(r);
  898.        }
  899.      }
  900.  
  901. The PlotFile Class
  902. ==================
  903.  
  904.    Class `PlotFile' is a simple derived class of `ofstream' that may
  905. be used to produce files in Unix plot format.  Public functions have
  906. names corresponding to those in the `plot(5)' manual entry.
  907.  
  908. C standard I/O
  909. ==============
  910.  
  911.    There is a complete implementation of the ANSI C stdio library that
  912. is built on *top* of the iostream facilities.  Specifically, the type
  913. `FILE' is the same as the `streambuff' class.  Also, the standard
  914. files are identical to the standard streams: `stdin == cin.rdbuf()'. 
  915. This means that you don't have to synchronize C++ output with C
  916. output.  It also means that C programs can use some of the specialized
  917. sub-classes of streambuf.
  918.  
  919.    The stdio library (`libstdio++')is not normally installed, because
  920. of some difficulties when used with the C libraries version of stdio. 
  921. The stdio library provides binary compatibility with traditional
  922. implementation.  Unfortunately, it takes a fair amount of care to avoid
  923. duplicate definitions when linking with both `libstdio++' and the C
  924. library.
  925.  
  926. 
  927. File: libg++.info,  Node: Stream,  Next: Obstack,  Prev: IOStream,  Up: Top
  928.  
  929. The old I/O library
  930. *******************
  931.  
  932.    WARNING: This chapter describes classes that are *obsolete*.  These
  933. classes are normally not available when libg++ is installed normally. 
  934. The sources are currently included in the distribution, and you can
  935. configure libg++ to use these classes instead of the new iostream
  936. classes.  This is only a temporary measure; you should convert your
  937. code to use iostreams as soon as possible.  The iostream classes
  938. provide some compatibility support, but it is very incomplete (there
  939. is no longer a `File' class).
  940.  
  941. File-based classes
  942. ==================
  943.  
  944.    The `File' class supports basic IO on Unix files.  Operations are
  945. based on common C stdio library functions.
  946.  
  947.    `File' serves as the base class for istreams, ostreams, and other
  948. derived classes. It contains the interface between the Unix stdio file
  949. library and these more structured classes.  Most operations are
  950. implemented as simple calls to stdio functions. `File' class
  951. operations are also fully compatible with raw system file reads and
  952. writes (like the system `read' and `lseek' calls) when buffering is
  953. disabled (see below).  The `FILE*' stdio file pointer is, however
  954. maintained as protected.  Classes derived from File may only use the
  955. IO operations provided by File, which encompass essentially all stdio
  956. capabilities.
  957.  
  958.    The class contains four general kinds of functions: methods for
  959. binding `File's to physical Unix files, basic IO methods, file and
  960. buffer control methods, and methods for maintaining logical and
  961. physical file status.
  962.  
  963.    Binding and related tasks are accomplished via `File' constructors
  964. and destructors, and member functions `open, close, remove, filedesc,
  965. name, setname'.
  966.  
  967.    If a file name is provided in a constructor or open, it is
  968. maintained as class variable `nm' and is accessible via `name'.  If no
  969. name is provided, then `nm' remains null, except that `Files' bound to
  970. the default files stdin, stdout, and stderr are automatically given
  971. the names `(stdin), (stdout), (stderr)' respectively.  The function
  972. `setname' may be used to change the internal name of the `File'. This
  973. does not change the name of the physical file bound to the File.
  974.  
  975.    The member function `close' closes a file.  The `~File' destructor
  976. closes a file if it is open, except that stdin, stdout, and stderr are
  977. flushed but left open for the system to close on program exit since
  978. some systems may require this, and on others it does not matter. 
  979. `remove' closes the file, and then deletes it if possible by calling
  980. the system function to delete the file with the name provided in the
  981. `nm' field.
  982.  
  983. Basic IO
  984. ========
  985.  
  986.    * `read' and `write' perform binary IO via stdio `fread' and
  987.      `fwrite'.
  988.  
  989.    * `get' and `put' for chars invoke stdio `getc' and `putc' macros.
  990.  
  991.    * `put(const char* s)' outputs a null-terminated string via stdio
  992.      `fputs'.
  993.  
  994.    * `unget' and `putback' are synonyms.  Both call stdio `ungetc'.
  995.  
  996. File Control
  997. ============
  998.  
  999.    `flush', `seek', `tell', and `tell' call the corresponding stdio
  1000. functions.
  1001.  
  1002.    `flush(char)' and `fill()' call stdio `_flsbuf' and `_filbuf'
  1003. respectively.
  1004.  
  1005.    `setbuf' is mainly useful to turn off buffering in cases where
  1006. nonsequential binary IO is being performed. `raw' is a synonym for
  1007. `setbuf(_IONBF)'.  After a `f.raw()', using the stdio functions
  1008. instead of the system `read, write', etc., calls entails very little
  1009. overhead.  Moreover, these become fully compatible with intermixed
  1010. system calls (e.g., `lseek(f.filedesc(), 0, 0)'). While intermixing
  1011. `File' and system IO calls is not at all recommended, this technique
  1012. does allow the `File' class to be used in conjunction with other
  1013. functions and libraries already set up to operate on file descriptors.
  1014. `setbuf' should be called at most once after a constructor or open,
  1015. but before any IO.
  1016.  
  1017. File Status
  1018. ===========
  1019.  
  1020.    File status is maintained in several ways.
  1021.  
  1022.    A `File' may be checked for accessibility via `is_open()', which
  1023. returns true if the File is bound to a usable physical file,
  1024. `readable()', which returns true if the File can be read from (opened
  1025. for reading, and not in a _fail state), or `writable()', which returns
  1026. true if the File can be written to.
  1027.  
  1028.    `File' operations return their status via two means: failure and
  1029. success are represented via the logical state. Also, the return values
  1030. of invoked stdio and system functions that return useful numeric
  1031. values (not just failure/success flags) are held in a class variable
  1032. accessible via `iocount'.  (This is useful, for example, in
  1033. determining the number of items actually read by the `read' function.)
  1034.  
  1035.    Like the AT&T i/o-stream classes, but unlike the description in the
  1036. Stroustrup book, p238, `rdstate()' returns the bitwise OR of `_eof',
  1037. `_fail' and `_bad', not necessarily distinct values. The functions
  1038. `eof()', `fail()', `bad()', and `good()' can be used to test for each
  1039. of these conditions independently.
  1040.  
  1041.    `_fail' becomes set for any input operation that could not read in
  1042. the desired data, and for other failed operations. As with all Unix
  1043. IO, `_eof' becomes true only when an input operations fails because of
  1044. an end of file. Therefore, `_eof' is not immediately true after the
  1045. last successful read of a file, but only after one final read attempt.
  1046. Thus, for input operations, `_fail' and `_eof' almost always become
  1047. true at the same time.  `bad' is set for unbound files, and may also
  1048. be set by applications in order to communicate input corruption.
  1049. Conversely, `_good' is defined as 0 and is returned by `rdstate()' if
  1050. all is well.
  1051.  
  1052.    The state may be modified via `clear(flag)', which, despite its
  1053. name, sets the corresponding state_value flag.  `clear()' with no
  1054. arguments resets the state to `_good'.  `failif(int cond)' sets the
  1055. state to `_fail' only if `cond' is true.
  1056.  
  1057.    Errors occuring during constructors and file opens also invoke the
  1058. function `error'.  `error' in turn calls a resetable error handling
  1059. function pointed to by the non-member global variable
  1060. `File_error_handler' only if a system error has been generated.  Since
  1061. `error' cannot tell if the current system error is actually
  1062. responsible for a failure, it may at times print out spurious messages. 
  1063. Three error handlers are provided. The default,
  1064. `verbose_File_error_handler' calls the system function `perror' to
  1065. print the corresponding error message on standard error, and then
  1066. returns to the caller.  `quiet_File_error_handler' does nothing, and
  1067. simply returns.  `fatal_File_error_handler' prints the error and then
  1068. aborts execution. These three handlers, or any other user-defined
  1069. error handlers can be selected via the non-member function
  1070. `set_File_error_handler'.
  1071.  
  1072.    All read and write operations communicate either logical or
  1073. physical failure by setting the `_fail' flag.  All further operations
  1074. are blocked if the state is in a `_fail' or`_bad' condition.
  1075. Programmers must explicitly use `clear()' to reset the state in order
  1076. to continue IO processing after either a logical or physical failure. 
  1077. C programmers who are unfamiliar with these conventions should note
  1078. that, unlike the stdio library, `File' functions indicate IO success,
  1079. status, or failure solely through the state, not via return values of
  1080. the functions.  The `void*' operator or `rdstate()' may be used to
  1081. test success.  In particular, according to c++ conversion rules, the
  1082. `void*' coercion is automatically applied whenever the `File&' return
  1083. value of any `File' function is tested in an `if' or `while'.  Thus,
  1084. for example, an easy way to copy all of stdin to stdout until eof (at
  1085. which point `get' fails) or some error is `char c; while(cin.get(c) &&
  1086. cout.put(c));'.
  1087.  
  1088.    The current version of istreams and ostreams differs significantly
  1089. from previous versions in order to obtain compatibility with AT&T 1.2
  1090. streams. Most code using previous versions should still work. However,
  1091. the following features of `File' are not incorporated in streams (they
  1092. are still present in `File'): `scan(const char* fmt...), remove(),
  1093. read(), write(), setbuf(), raw()'. Additionally, the feature of
  1094. previous streams that allowed free intermixing of stream and stdio
  1095. input and output is no longer guaranteed to always behave as desired.
  1096.  
  1097.