ezdsl.doc

Delphi数据结构分析源码

TNodeStore code you'll see things like node reuse, several containers
using the same node store and so on.


Iterators
----------------------------------------------------------------------

For the navigable containers (ie those containers where a cursor is
defined) an iterator method is defined. This is called Iterate, and
takes over from the two iterators called ForEach and FirstThat from
olden days; the Iterate method does double duty as will be seen.

Each iterator takes three parameters: an Action routine, a direction
flag and a ExtraData pointer. The ExtraData pointer is simply to
enable you to pass any kind of record structure to the Action
routine: it negates the need for global variables or for a nested
Action routine (c.f.  Borland's TCollection in BP7). The direction
flag (called Backwards) enables you to iterate through the container
from either one of two directions: forwards or backwards.

The Action routine for a ForEach call has to be of the form:

  TIteratorProc = function (C : TAbstractContainer;
                            aData : pointer;
                            ExtraData : pointer) : boolean;

where C will be the container itself, aData is the current data
object and ExtraData is the same extra data pointer you passed to
ForEach. The function must return True to cause the Iterate routine
to continue iterating or False to cause the Iterate routine to stop
(and return the data object that cause the Action routine to return
False).  Remember that your Action procedure CANNOT be a nested
routine (in Delphi 1.0 it must be declared 'far'; in Delphi 2/3 it
must be declared as 'register' (ie the normal fastcall declaration)).

A quick example: suppose your data objects had an integer field called
Value and you wanted to find the sum of all the Value fields in a
list. Your Action procedure would look like:

  function SumValues(C : TAbstractContainer;
                     aData : pointer;
                     ExtraData : pointer) : boolean; far;
    var
      {ExtraData is a pointer to a longint: so typecast it}
      Sum :  ^longint absolute ExtraData;
    begin
      inc(Sum^, PMyObject(aData).Value);
      Result := true;
    end;

and you would call Iterate to do the summation as follows:

  var
    TotalValue : longint;
    MyList : TLinkList;
  begin
    {...}
    TotalValue := 0; {clear the total}
    MyList.Iterate(SumValues, false, @TotalValue);
    {...}
  end.

Notice that the SumValues procedure is explicitly declared 'far' in
Delphi 1.0 (in Delphi 2/3 this modifier is ignored). I have found this
method to be by far (!) the easiest method of ensuring that the Delphi
1.0 compiler will compile my source code without relying on the
current value of the $F compiler define.


Debugging and Errors and Exceptions
----------------------------------------------------------------------

When I started writing this unit I had several goals, but there were
two which seemed incompatible: it had to be fast and it had to have
lots of checks built in to trap any errors that might occur.

This second goal is further complicated because there are broadly two
types of error that could occur: an error due to a programming
mistake and errors due to some run-time problem. This is necessarily
a wishy-washy definition, but generally the run-time problems would
be things like running out of memory whilst adding a data object, and
the programming mistakes would be things like trying to pop a data
object from an empty stack. Another way to view this would be to
define programming mistakes as being those things which would apply
to every machine, whereas the run-time problems would vary from user
to user and from machine to machine. Normal testing should identify
programming mistakes, whereas the other type of error are exceptions
to the norm.

I thought about how I might trap programming mistakes and decided to
use assertion checks as in the C language. An assertion is a simple
debugging routine that checks whether something is true.  If this is
the case the program continues. If it is false, the program is
terminated immediately by writing out a string explaining why (we
shall however be raising an exception).  In C this is accomplished by
the Assert macro.  Compile your C program in one way during testing
and the Assert macro expands to this kind of check; compile it in
another way (for your production app) and the Assert macro 'expands'
to a null statement.  As you see, during testing you have the full
set of checks to aid in debugging (slow but safe), and once you have
fully tested the application you can turn them all off to obtain the
full speed.

Unfortunately in Pascal these kind of preprocessor macros are not
available. I worked round the problem by having a compiler define
called DEBUG which firstly automatically activates the $D+ and $L+
compiler options, and secondly causes a lot of methods to have a call
to Assert at the start of the routine to check that various entry
conditions are met.

An example should make this clear. The TStack object has a method
called Pop to remove the topmost data object from the stack. If the
stack is empty, I count calling Pop as a programming mistake: you
really should check for the stack being empty in your program prior
to calling Pop. Of course Pop could have an if statement within it
that did this check for you, but in the *majority* of cases the stack
won't be empty when Pop is called and in the *majority* of cases when
you use Pop, you'll have some kind of loop in your program which is
continually checking whether the stack is empty or not anyway. In my
mind having a check for an empty stack within Pop is safe but slow.
So, instead, Pop has a call to an Assert procedure at the start
(activated by the DEBUG compiler define) that checks to see whether
the stack is empty. Here is the code for Pop:

      function TStack.Pop : pointer;
        var
          Node : PNode;
        begin
          {$IFDEF DEBUG}
          Assert(not IsEmpty, ascEmptyPop);
          {$ENDIF}
          Node := Head^.Link;
          Head^.Link := Node^.Link;
          Pop := Node^.Data;
          acDisposeNode(Node);
        end;

As you see, if DEBUG is set the Assert procedure checks whether the
stack is empty first, if not it executes the code that pops the data
object off the stack. If the stack is empty an EEZAssertionError
exception is raised (the constant ascEmptyPop is a string code for a
stringtable resource).  If DEBUG is not set the code runs at full
speed.

In the method descriptions below, I will show when an assertion check
(activated with the DEBUG define) has been built into the method's
code. You may assume that if the DEBUG define is off and the
condition that the assertion check test for occurs, very bad things
will happen to your program. These could be as 'benign' as a memory
leak, or as dreadful as a memory overwrite. It is up to you to
thoroughly test your program with the DEBUG define set, before you
turn it off.

The other type of error (that which occurs infrequently and is due to
some 'at the limit' problem) will cause an EEZContainerError
exception to be raised. The strings that the exception class uses are
defined in a stringtable resource (EZDSLCTS.RES, string codes in
EZDSLCTS.PAS), so that you may alter them at will (eg translate them
into another language).

You can rest assured that when exceptions are raised, resources will
be conserved via try..finally blocks. If you also have EZSTRUCS you
might find it amazing how easy try..finally blocks make your code
easier to understand compared with the 'old' method involving flags
and checks for errors all over the place.


Compiler Defines
----------------------------------------------------------------------

At the beginning of every EZDSL source code file are the following
lines:

    {$I EZDSLDEF.INC}
    {---Place any compiler options you require here----------}


    {--------------------------------------------------------}
    {$I EZDSLOPT.INC}

The include file EZDSLDEF.INC contains the compiler defines for the
EZDSL library. These defines are described below. The include file
EZDSLOPT.INC contains the _unchangeable_ compiler options for the
EZDSL library; by unchangeable I mean that if you do change one or two
then EZDSL might still work, but on the other hand it might not. Any
other defines you can change at will, and EZDSL will compile and run.
These changeable options should be placed inside the indicated place.

The DEBUG compiler define has already been mentioned, but there are
also two other compiler defines from EZDSLDEF.INC to consider. Here is
the full list.

DEBUG defines whether the unit will be compiled with debug information
(if on it automatically sets $D+ and $L+, if off these options are set
off) and with assertion checks activated.  It is on by default.

UseTreeRecursion affects binary trees. If the define is activated (as
it is by default) then any binary tree routines that navigate through
the tree will use recursive algorithms to do it. If the define is
deactivated the routines will remove any navigation recursion by
using a TStack (this is known as unrolling the recursion). The pros
and cons are that recursive routines are simple and fast but can use
a lot of internal stack space (and could end up blowing the stack
should your $M directive be small enough in Delphi 1.0), whereas
unrolling the recursion is slower but does not require a lot of
internal stack space, relying instead on the Pascal heap via a TStack
container. It can also be difficult to estimate the amount of stack
space required for a recursive navigation process on a large binary
tree.

SuppressWarnings is a Delphi 2/3 only compiler define. When active (as
it is by default) all warnings that are generated for the code in
EZDSL are suppressed and you won't see them; when inactive the
warnings are shown as normal. I have found the Delphi 2/3 warnings to
be a mixed blessing: they are great at finding those silly but simple
mistakes we all make (eg forgetting to set a function result) but they
can be fooled by moderately complex code. There are several places in
EZDSL where the compiler generates a warning, but which can be shown
to be false. Maybe you'll have fun turning off the SuppressWarnings
define and working out why the compiler is wrong for the warnings that
are then shown.


Of Compilers and Caveats
----------------------------------------------------------------------

I have tested the EZDSL unit with Borland Delphi versions 1.02, 2.01
and 3.01.

The EZDSL library has grown out of both my own personal work and my
work at TurboPower. If you are familiar with TurboPower products you
may find echoes of TBigCollection in TEZCollection, and the iterator
idea is lifted from Orpheus' sparse array class.  In return the
container classes in TurboPower's SysTools (written by Kim Kokkonen)
take some of the ideas from EZDSL and move them further. You could say
EZDSL reflects my programming and coding practices, and is hence
somewhat Julian-centric!


Example programs
----------------------------------------------------------------------

To see how to use the EZSTRUCS unit, check out the example units and
test programs in the same archive file.


Programming Documentation
----------------------------------------------------------------------

The next section contains all the documented container classes and
their documented methods and fields. For the underlying undocumented
classes, fields, methods and algorithms see the source code (Use the
Source, Luke!).

It might be beneficial to review the naming convention for the methods
of these containers; it'll also provide a summary of the important
methods to know.

Create  creates a new instance of the container, and prepares it for
        use. You define whether the container is to 'own' its data
        objects or whether it is just holding a reference to them.

Destroy destroys an object instance, releasing all memory used by the
        container including that held by the remaining data objects
        in the container (providing of course that the container owns
        its objects).

Insert  inserts a data object into the container. For some containers
        there might also be other InsertXxxxx methods that insert data
        objects in certain other defined ways. For stacks and queues
        Insert is known as Push or Append.

Delete  unlinks a data object from a container but does not dispose of
        the memory held by the data object. For stacks and queues
        Delete is known as Pop.

Erase   unlinks a data object from a container and also disposes the
        memory held by the object (if the container owns its data
        objects, that is).

Examine returns the data object at the 'current position' of the
        container. Current position is defined in different ways for
        different containers: for a stack or queue it is the head of
        the stack or queue for example.

Empty   empties the container by calling Erase for all data objects.

IsEmpty returns true if there are no data objects in the container.

Iterate calls its action routine for each data object in the
        container.

Clone   creates an exact duplicate of a data container. All the data
        objects within the container are also duplicated if the new
        container is going to be a data owner, else only the pointers
        to the data objects are copied over. Note that an "exact
        lookalike" copy might not be created, a clone of a binary
        search tree might not look the same, even though all the nodes
        are in sorted InOrder sequence.

Join    adds all the data objects in one container to another (in a
        fashion that makes sense according to the container type). The
        emptied container is disposed of.

Split   splits a container into two, moving all the data objects from
        the split point to a newly created container of the same type
        as the first. In this version of EZDSL, Split has not been
        implemented for binary trees.

----------------------------------------------------------------------

Global Types, Constants and Variables