ezdsl.doc

Eazy Data Structures library for Delphi.

   Create separate thread-safe container classes

Let's discuss them in turn. The first option is the safest: every
method uses the following methodology:

   Acquire exclusive access to the container
   try
     do whatever the method is supposed to do
   finally
     Release exclusive access to the container
   end;

Basically, what happens here is that only one thread can get exclusive
access at one time (all other threads are blocked) and this ensures
that what the method is supposed to do is done safely. The one big
problem with this way that I didn't like is that, if you were not
using multithreaded programming at all, or if you were using different
containers in difference threads, you'd be locking and unlocking the
containers all the time, without reason to. Although the resource
locking code uses Win32's critical sections, and hence is fairly fast,
it still slows down the code unnecessarily for those who don't use it.

Another small variation on this theme is to use a boolean field
(called BeThreadSafe or something) to say whether to lock or not. If
the boolean was false, no locking would occur, if true, locking would
be done. I rejected this as well, since the try..finally block would
still have to be there and this consumes cycles unnecessarily. Also
it's too easy to set the boolean to true whilst a method is being
executed. This results is an unlock being performed, even though a
lock has not taken place. Adding code to counteract this is messy and
unnecessary given that there are better solutions.

The second option requires you, the programmer, to make sure that you
acquire access to the container before using it, and to release it
afterwards. Basically your code looks like this:

   MyStack.AcquireAccess;
   try
     ..do something with MyStack..
   finally
     MyStack.ReleaseAccess;
   end

The reason I rejected this option is that it's too easy to forget. For
example, moving the cursor in a single linked list will rearrange the
links in the list: you must protect the linked list before calling
Next or Prev. Forgetting this kind of gotcha is too easy. Another one
is Iterate: you must protect the container before navigating through
it, otherwise you'd have a complete disaster on your hands if thread 1
was navigating at the same time that thread 2 was adding data objects.

The option I finally went for was to have special thread-safe
containers. You use them like this:

   var
     MyThreadSafeStack : TThreadsafeStack;
     MyStack : TStack;
   begin
     MyThreadSafeStack := TThreadsafeStack.Create(false);
     ...
     {get the embedded stack}
     MyStack := MyThreadSafeStack.AcquireAccess;
     try
       ..use MyStack methods..
     finally
       MyThreadSafeStack.ReleaseAccess;
     end;
     {you no longer have access to the embedded stack}

Here the code is explicit: you acquire access to the stack and in
return you get a stack variable to use. Once you release access you no
longer have access to that variable. To get a stack variable to use,
you must call the AcquireAccess method of the special protected
object. You can't forget.

So this means you have the best of both worlds. Unprotected, fast
container classes for normal use, or for unshared containers in a
multithreaded program; fully protected classes for shared containers
over multiple threads.



Debugging and Errors and Exceptions
----------------------------------------------------------------------
When I started writing this library 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 Delphi these kind of preprocessor macros are not
available, at least not until Delphi 3. This release of the Delphi
compiler came with a proper Assert routine: compile it one way with a
compiler define set and assertion checks are performed, compile it
another way and the check 'disappears'. Unfortunately, with my goal of
supporting all the Delphis, I could not use this nifty language
feature. Instead, 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}
     EZAssert(not IsEmpty, ascEmptyPop);
     {$ENDIF}
     Node := stHead^.Link;
     stHead^.Link := Node^.Link;
     Result := Node^.Data;
     acDisposeNode(Node);
   end;

As you see, if the DEBUG compiler define is set the EZAssert procedure
is called, and this checks whether the stack is non-empty first. If
the assertion is true, the Pop method continues and executes the code
that pops the data object off the stack. If the stack is empty an
EEZAssertionError exception is raised inside the EZAssert procedure
(the constant ascEmptyPop is a string code for a string in 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 or an access violation. 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 (for example, to 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 you'll find 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. You
can change any other compiler options 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 is
another compiler define 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. 

SuppressWarnings is a 32-bit Delphi 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 compiler
warnings to be a mixed blessing: they are great at finding those silly
but simple mistakes we all make (e.g. forgetting to set a function
result) but they can be fooled by moderately complex code. There are a
few 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.

In Delphi 3, the EZDSL3a3 package is compiled with the DEBUG define
off. In other words, if you are using the run-time EZDSL package you
will be using code without assertion checks.



Of Compilers and Caveats
----------------------------------------------------------------------
I have tested the EZDSL units with Borland Delphi versions 1, 2, 3, 4,
5, and 6. In each case, I used the version of the compiler with all
patches applied.

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 on 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 EZDSL library, check out the example units and
test programs in the same archive file. Each example program has a
header comment that describes the particular feature that's being
shown or tested.

There are a set of test programs (called something of the form
DTstXxx) that exercise the full set of features for each container
class. They are all console programs, and not only output their
reports to the console (to fast for the eye to read!), but also create
a log file called TEST.LOG that you can read at your leisure.



======================================================================



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 also be beneficial at this point 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