| |
|
|
|
2 USER'S GUIDE
2.1 OVERVIEW
The purpose of the FND Foundation Class Library is to provide generic classes for data handling, that can be used for the development of any C++ application, independently from the specific requirements of the VLT Project.
For this reason the FND Library has no dependency on any other VLT Software component, with the exception of what concerns the fulfillment of all VLT Software development standards and the usage of VLT standard development tools, like the VLT Makefile.
The library can be divided in two parts:
· The fndOBJECT and the container classes
This is the core of the library. It provides the basic fndOBJECT class and the whole hierarchy of containers that implement the most commonly used data handling structures and algorithms.
· Other classes and functions
These classes are not related with the fndOBJECT class or the container classes, but provide the implementation for other concepts of very general use for C++ programmers, and have then be placed inside this library as the more convenient place to collect general programming tools.
2.2 USAGE OF FND FOUNDATION CLASS LIBRARY
Applications using the FND Foundation Class Library library, must have the extension ".C" (capital C), which indicates for the GCC compiler that the file is C++ code and should be compiled as such. Extensions of include files remain the same (".h") of standard C code. Inline code should be put in include files separated from the definition header files (and included by them), and having the extension ".icc".
The library makes usage of basic C++ libraries, so the following libraries must be linked to code using fnd: fnd, stdc++, g++, iberty.
2.3 THE fndOBJECT AND THE CONTAINER CLASSES
2.3.1 Basic concepts
Most applications have the need of handling collections of objects, like arrays, lists stacks or even more complex data structures like dictionaries and hash table.
It is then reasonable to provide generic classes that implement these data structures and the corresponding data handling algorithms, so that the programmer does not need to write the code implementing, say, a stack, every time he needs one.
The main problem is to provide an implementation generic enough to allow reuse of the data handling classes no regard of the complexity of the data to be handled.
This means that a class to handle a stack must be able to handle stacks of very different and possibly very complicated objects.
In C++ this objective has been addressed following two strategies (see 2.5 for details):
The fnd Foundation Class Library is based on the first technique:
· A set of CONTAINER classes, all derived by the fndCONTAINER class, implements the data structures and algorithms for stack, array, list and as many other container classes are needed.
· These CONTAINERS can be used to contain, collect and manipulate any kind of objects, provided that they are of a subclass of the fndOBJECT base class.
From the implementation point of view, this architecture is very convenient since it does not rely on any language specific feature, but only on general Object Oriented concepts and can then be implemented in any Object Oriented language.
From the user point of view, the main advantage consists on the fact that this makes it very easy to create and handle complex hierarchies of objects, since containers can be nested (an fndCONTAINER is also and fndOBJECT) and mixed together.
On the other hand, the main disadvantage consists of the need of having every class derived from fndOBJECT, so that already existing classes and data structures must be at least enclosed in an fndOBJECT wrapper class.
2.3.2 Overview of the classes provided by fnd
The fnd library provides the following classes, grouped by function:
fndOBJECT
Root of the tree hierarchy and base class for every object that can be handled by the container classes and by the association class
fndCONTAINER
Is the base class for all the containers.
A container is a repository of objects and the class provides methods to see how many objects are in the container and to execute some action on all the objects in the container. The object put in any container must be subclasses of fndOBJECT but do not need to be all of the same class.
The following are subclasses of fndCONTAINER:
fndCOLLECTION
A collection is a searchable container. It provides methods to add and delete elements.
The following are subclasses of fndCOLLECTION:
fndARRAY
Dynamic array. The size of the array is not determined when the object is created, but can grow dynamically (in an optimized way). The class provides methods to add, delete, access and search elements in the array.
fndBAG
A bag is an unstructured collection of elements. It can contain multiple copies of the same object.
fndDICTIONARY
Collection of associations. It is possible to add elements in the dictionary and to retrieve a definition given its key. Uses hash tables.
fndHASH_TABLE
Class to handle an hash table of objects. The objects inserted must be subclasses of fndOBJECT and provide a suitable implementation if the HashValue() method.
fndLIST
Double linked list. Provides methods to add, delete, search elements in the list and to navigate the list using iterators.
fndPOS_ARRAY
Dynamical array where objects are kept packed and in relative position. If an object is deleted, the array is packed and the hole filled. If an object is inserted at a certain position, space for it is created moving the other objects.
fndSET
A set is an unstructured collection of elements. Unlike the bag it can contain only one copy of the same object.
fndSORT_ARRAY
Dynamical array where objects are automatically kept in the right order. The inserted objects must of subclasses of fndSORTABLE.
fndDEQUE
Double queue. Element can be put in the queue from left and right and peeked from both sides of the queue.
fndASSOCIATION
An association is a couple of objects: a key and a value. A typical example of association is a dictionary entry, where the key is the search key in the dictionary and value is the definition
fndSORTABLE
Base class for objects that have the property of being sortable. It provides methods to compare two sortable objects and to put them in the right order.
fndSTRING
Class used to handle strings. Memory allocation is dynamic. Can be transparently used whenever a char* string is used.
Notice that the last mentioned classes (fndPOINTER, fndFLOAT, fndINT and fndSTRING) are mainly wrappers around native C types, to be able to use them inside containers.
2.3.3 The fndOBJECT class
The fndOBJECT class is the core of the whole fnd class library and all objects handled by containers must be of a subclass of the fndOBJECT.
This is due to the fact that the fndOBJECT provides a set of basic services that are used by container classes in order to properly manipulate and recognize the handled items.
Some of these methods can in general just be inherited from the base class, but some of them need to be implemented in every subclass. For this reason some convenience macros are provided and section 2.3.4 gives a detailed description of the steps necessary to create a new fndOBJECT subclass.
Some of the methods could seem not to have sense in the fndOBJECT class, but in reality they provide a basic interface that is used by container classes and have to be implemented in the subclasses.
The include file fndOBJECT.h, also defines some macros and typedefs used all over the fnd class library.
In the following sub-sections the most important methods will be described grouping them in categories.
2.3.3.1 Constructors and destructors
The fndOBJECT class provides 2 constructors and one destructor:
The constructor with no parameters should always be provided for subclasses and it is compulsory to provide its implementation when the standard fndStdObject...() macros (see 2.3.4) are used.
More over, as a general C++ programming rule, the copy constructor should always be implemented in the subclasses (but this is not compulsory). This is very important when the object construction requires dynamic memory allocations.
In addition, any fndOBJECT subclass MUST provide an implementation for the static factory method1 (see later on for a description of factory methods):
and the related "class type definition", by using the following standard syntax:
With this #define, the pointer to (i.e. the address of) the static factory method is assigned to a convenience name and hidden to the user behind a more intuitive representation. Since this address is unique for all instances of the class, it is used as a class identifier, without requiring a specific compiler support, i.e. it allows the implementation of the IsA() and IsSubclass() methods: it. is returned by the "who am i" method IsA() or taken as a parameter by the method IsSubclassOf(), as described in section 2.3.3.2.
The type classType is a seen by the user as a type identifying the class of an object, but it is in reality a pointer to a static method of the class.
Since anyway the body of this method is "standardized", it is automatically created when the macros fndStdObjectDef() and fndStdObjectSource() are used to create sub-classes (see 2.3.4).
2.3.3.2 "Who am I" methods
A set of methods has the purpose of identifying the object and its class and of telling to other classes, and in particular to fndCONTAINER classes, what features it makes available.
First of all there are the class identification methods, that return the object's class or check if an object is of a specified class or subclass (they are created automatically by the macros):
Then there are the "property" methods. Since some operations can be performed only on fndSORTABLE objects or on fndASSOCIATION objects, a couple of methods are used by fndCONTAINER classes to ask to an object if it is able to satisfy the requirements (the creator of sub-classes should not have any need of touching these methods):
The hashing calculation method:
has to provide an implementation of an algorithm to generate hash values for the class instances.
The default implementation just returns the object's address. This is clearly not an efficient hash value (but it works) and sub-classes should always provide a better specific implementation. All basic fnd classes provide a better implementation, but this is not compulsory for sub-classes.
Then there is the comparison method:
that compares the object with another one. The default implementation just compares the addresses of the two objects, returning true only if they are identical. Some sub-classes could have the need of implementing a specific behaviour.
The last method of this category:
is just defined to make easier debugging and testing and provides a standard interface to generate a log of object's contents and state, used by containers to generate logs of complex hierarchical container data structures.
2.3.3.3 "Iteration" methods
This category includes three methods used in and by fndCONTAINER classes to iterate on the members of a container and to apply some action to all methods in a hierarchical structure of containers:
2.3.3.4 The NOOBJECT
The NOOBJECT is a symbolic name to identify the very important fndOBJECT::ZERO static instance of the fndOBJECT class.
This object, as the name says, identifies NO OBJECT, i.e. a not valid or not existing object, and is somehow the object counterpart of a NULL pointer, when a reference to an object has to be returned or passed instead of a pointer.
For example, when a search for an object in a container fails, the Search() method of fndCONTAINER classes returns a reference to NOOBJECT.
2.3.4 Deriving new classes from fndOBJECT
In order to provide a complete and working implementation for a subclass of fndOBJECT, it is necessary to write a proper implementation for some compulsory methods (typically by using the provided convenience macros), and to follow carefully some basic rules.
To make these rules clear, we describe in this section the implementation of the basic fndINT class, that can be used as a template for the implementation of other classes. The same applies for the implementation of fndCONTAINER or fndCOLLECTION subclasses, where some more methods have to be implemented.
Once the general rules for the fndOBJECT class have been understood, they can be easily extended to the more complex container classes just looking at the documentation for the base classes.
2.3.4.1 The fndINT.h include file
The fndINT class, is not just an fndOBJECT, but it is more precisely an fndSORTABLE, so this last one is the base class:
The first step, consist in providing a "class type definition", by using the following standard syntax, as described in 2.3.3.1 (notice that fndINT_CLASS is just a pointer to a method. No method is really called when the symbol is used):
The fndINT_CLASS define can be then used to name the class and can be retrieved/passed for example to the IsA() or IsSubclassOf() methods.
Then the class can be actually defined:
From the class definition, it is clear that the class will provide a specific implementation of a number of methods and some new methods that are specific of the nature of an objects representing an "integer".
The standard methods fon an fndOBJECT are:
· fndINT( const int anInt=0 ) - A contructor with NO parameters (in this case obtained by defaulting the only parametr).
One standard method is required by the fndSORTABLE base class:
It is very important to notice the line:
This is a call to a special macro that provides a convenient way of implementing automatically a set of standard compulsory methods, along with the counterpart fndStdObjectSource(). One provides method prototypes, the other one method implementations.
2.3.4.2 The fndINT.C source file
Also the source code file is very simple.
The first part just take care of the proper include files:
Then it comes the very important call to the fndStdObjectSource() macro, counterpart of fndStdObjectDef().
· must be called in the class source file at any place (outside other methods definitions), better just after the include files.
2.3.5 Using generic fndCONTAINERS and fndCOLLECTIONS
2.3.5.1 General considerations
The fndCONTAINER and fndCOLLECTION classes provide a basic and generic interface for handling of collections of objects: methods to add and remove objects from a container and to search for objects in collections.
If only this standard interface is used, it does not matter what specific container or collection is actually used, allowing to chose one at any time based, for example, on performance considerations.
On the other hand, specific containers implement also access methods that are unique for the container type and implement specific access algorithms, like Push() and Pop() for a stack.
At the basis of the fndCONTAINER classes are a couple of important architecture considerations to be kept always in mind:
· Every fndCONTAINER can handle any kind of fndOBJECT instance, also other containers, allowing to build complex hierachies of containers.
· Objects inside an fndCONTAINER are NOT required to be of the same class, but can as well be of many different classes.
The last point is a very important one.
It means that when an fndOBJECT is added to a container, the container takes a reference to the object and stores it:
This architecture has many strong points, but the user must pay attention when deleting objects: before deleting an object it must first always detach it from all the containers where it has been added. If this is not done, the container will have dead pointers and the behaviour will be unpredictable.
so that there is no risk of having around dead pointers because objects allocated on the stack exit from scope.
To make easier memory allocation/deallocation in containers in the very common case objects are really logically "owned" by the container, i.e. they are always added to one and only one container, it is possible to force the container to delete automatically all contained objects when it is deleted and to delete objects when they are detached. For this purpose the fndCONTAINER class defines the DelItemsOnDelete() and Destroy() methods.
2.3.5.2 Generic container interface
This section contains a step by step example on the usage of the most common methods of the fndCOLLECTION interface. More examples are in section 5.
1. The first step consists always in the allocation of the chosen container. In this example we allocate dynamically an instance of fndBAG. Notice that we assign this object to a generic pointer of class fndCOLLECTION, since we will use only the generic interface. In this way we will be able at a later time to replace the fndBAG with an fndARRAY, an fndLIST or any other collection with no impact on the rest of the code:
3. As a next step we can now add some objects to the container. As a good practice, we only add dynamically allocated objects:
8. If I delete now the fndCONTAINER, the contained elements are not deleted as well. But I can explicitly empty the fndCONTAINER first, asking for deletion of the elements at the same time:
9. Or, better, I can tell the object that he is the owner of the contained items and that he is responsible for deleting them on deletion:
2.3.5.3 A specific container: the fndSTACK
This section contains a step by step example on the usage of the fndSTACK container, just to give the feeling of how a specific fndCONTAINER can be used. More examples for the other basic fndCONTAINERS (like fndARRAY, fndLIST and fndHASH_TABLE) are in section 5.
2.3.6 Using the fndDICTIONARY class
The fndDICTIONARY is a very useful container, since it allows to create and handle simple databases and data tables. Other container class libraries call this class "map".
The basic idea behind the fndDICTIONARY is to provide associations between a key and a definition, where both key and definition can be any kind of fndOBJECT, from a simple fndIND or fndSTRING up to any complex data structure.
The key is then used as a search keyword to efficiently retrieve the corresponding definition from the database.
We examine here how to build a simple english/italian and italian/english dictionary (please remember that this example has been written to be as small and as simple as possible, so error handling is very limited).
We need first of all to define a class for our two way dictionary.
This class will have as private data members two fndDICTIONARY instances, one for english/italian and one for italian/english.
The public interface provides one method to add entries in the two way dictionary and two search methods, one for the english to italian translation and one for the opposite translation.
The entries are stored in the fndDICTIONARY as fndSTRING (they must be of a subclass of fndOBJECT), but to keep the example simple, the public methods accept const char*.
The constructor configures the dictionaries so that they delete all the contained items when they are themselves deleted, to ensure that no memory is leaked.
The Add() method takes the two const char* parameters and copies them in newly dynamically allocated fndSTRING objects, a pair for every dictionary.
The fndSTRING objects are added to both the dictionaries.
Memory could have been saved allocating only one fndSTRING per entry, but would have made necessary to have the two dictionaries asymmetrical: only one should have had the ownership of the entries. This solution is not optimal but cleaner.
The SearchXX() methods then get a const char* key, convert it into a fndSTRING and finally search inside the proper dictionary for the definition.
If the key is not found, the fndDICTIONARY::Lookup() method returns NOOBJETC.
What follows if finally a small example of the usage of this class:
2.4 OTHER CLASSES AND FUNCTIONS IN FND
A part from the fndOBJECT class hierarchy, the fnd library provides also some other classes of general use.
Among these, the most important are:
fndAUTO_PTR<> - The fndAUTO_PTR template class implements the concept of "automatic pointer", i.e. of a pointer that automatically deletes its contained object when it exits the scope where it was created.
The class is very handy if the user want to be sure that an object is deleted when its pointer exits the scope, and is in particular essential when there is no explicit control over the return point of a function, for example when using exceptions.
For an example, see section 4.4.
fndNAME_MAP - The fndNAME_MAP class provides an easy way to build and query maps of index/name couples, where the index is an unsigned integer.
This is very useful when enumerations have a double representation: a numerical index and a conventional name in the form of a string (for example, an application state is handled internally to an application by using an index, but is if reported to client applications in the form of a readable string).
For an example, see section 4.15.
2.5 FND, STL AND OTHER CONTAINER CLASS LIBRARIES
The fnd foundation class library provides the implementation for a set of container classes very similar to the ones provided by many other similar libraries.
It is based on the "root object class" concept, like for example the SmallTalk or the Java container libraries and unlike the STL library (part of the C++ Draft ANSI Standard[3]), that is based on templates.
The main advantage of a template implementation consists of the fact that the items put in a container are not required to be all instances of subclasses of the base "object" class. This means that it is possible with just a few lines of code to put any object, also of already existing classes, in a container, without having to define fndOBJECT wrappers around already existing classes.
On the other hand, a template implementation requires instantiation of the code of all the template instances, causing a big object code growth with respect to the other solution. Experience in the last couple of years has shown that the usage of the STL library can generate unexpected and uncontrolled growth in executable code and unexpected decrease in performances.
At the same time, the STL library has not been yet officially standardized and the available implementations are quite unstable, in part because they heavily stress compilers uncovering bugs and problems. For this reason experience has shown that it is often better to use the more simple and portable fnd library.
Another difference between fnd and stl consist in the fact that stl containers always get their own private copy of the inserted items, while fnd containers only take a reference to the inserted items and they are not owners of the items themselves. This allows to put the same items in more than one container. This aspect must be always taken into account (sometimes it is an advantage, sometimes a disadvantage), in particular with regard to memory management.
2.6 CAVEATS
This section will contain solutions to common problems encountered when using FND library.
It will be extended taking into account SPRs and frequently asked questions
1A factory method is a static method of a class whose purpose is to create a new instance of the class. With respect to using the new operator, a factory method has the advantage that it is possible to store and handle it as a pointer to a method, i.e. in a normal C++variable. This allows to manupulate factory methods, store them in tables and them to functions. This is the basic feature to be able to create instances of classes without knowing in advance their type, i.e. of creating classes whose type is defined dynamically and not at compile time (using the new operator, the type of an object is decided at compile time.). This is a very usefull feature, essential for example to create persistent class. Factory methods are described in details on many C++ and generic Object Oriented books.
2The macros expands as a set of methods declarations, with their own scope declarations. Putting it in the middle of a scope block, would silently modify the scope of the following declarations.
 Quadralay Corporation http://www.webworks.com Voice: (512) 719-3399 Fax: (512) 719-3606 sales@webworks.com |
| |
|
|
|