ezdsl.doc

Eazy Data Structures library for Delphi.

1) if the first is greater than the second. The Compare function is
used only by sorted containers to maintain the internal sorted
sequence, or by unsorted containers that implement a Search method. In
the latter case, the Compare method is just used as an equal or not-
equal test. Unsorted containers that do not have a Search method do
not use the Compare property, and so in these cases it does not have
to be set.

The exception to this rule is the hash table. Here data objects are
stored in a 'sequence' that enables them to be retrieved very quickly,
and yet this sequence has nothing to do with Compare. In fact, the
Compare property is not used with hash tables so it's pointless to set
it.

Once you accept that certain containers maintain data objects in an
ordered sequence, you have to consider the problem of duplicate data
objects. Two data objects are defined as duplicate if the container's
Compare function returns zero when called with them as parameters.
Well, EZDSL enforces a strict rule: sorted containers cannot contain
duplicate data objects. All sorted containers will raise an exception
(with string code edsInsertDup) if you attempt to insert a data object
that compares equal to an already inserted data object.

You might have decided that this is a somewhat harsh restriction.
Well, yes and no. Some containers just cannot be used with duplicate
data objects (the skip list is the main example; if you try to, some
very weird effects will occur).  Some containers will internally
reorganize themselves, and will destroy any arrival sequence that
duplicate data objects could have been inserted with (the red-black
binary search tree is the main example here). Rather than document
that some containers will accept duplicate items and some won't and if
they did what kind of weird effects could happen on deletion and
insertion, I decided to restrict all sorted containers in the same
manner: they will not accept duplicate data objects.

What to do? Suppose you had the kind of use for a skip list that
absolutely had to accept duplicate data objects? Firstly I would ask
you to redesign your data object so that duplicates could not occur
and secondly recode your Compare function so that maybe another field
of the data object could be used in the comparison to remove the
ambiguity.

If all fails, one solution could be to declare a sequence long integer
in your container descendant class. Set this to zero in your
constructor. Make sure that your data objects have a sequence field,
and that your Compare function checks this after your main comparison.
Override the Insert method of the container to increment the
container's sequence field and set the data object's sequence field to
it, and then call the inherited insert method.  This algorithm is
shown in the example program EXINSDUP.

As always with rules, there is one exception to the 'no duplicates'
rule:  the priority queue. This container will accept duplicate data
objects.  However duplicate data objects will *not* be popped off in
arrival sequence or, reverse arrival sequence, or any other
deterministic sequence; as far as the priority queue is concerned
duplicate data objects are exactly that, it cannot distinguish between
them in any way. Again if this matters to you, you'll have to redefine
your data object and Compare function to remove the anomaly.

A new feature of version 3 of EZDSL is the ability of containers to
sort themselves when you supply an new Compare function. If the
container is sorted and you set the Compare property to a new compare
function, then the container will reorder its data objects according
to that new function. It does this in the most efficient manner
possible by reusing the internal nodes and minimizing the amount of
extra heap space for the job. This ability is not available for the
sorted collection.



Nodes and Node Stores
----------------------------------------------------------------------
We all know that these classical data structures are generally
implemented with nodes. For a doubly linked list a node is usually
represented by a record structure of the form: 

    PMyNode = ^TMyNode;
    TMyNode = record
      Next : PMyNode;     {Link to next node in the chain}
      Prev : PMyNode;     {Link to previous node in the chain}
      Data : SomeRecord;
    end;

When writing the unit I wanted to get away from the dependence of
knowing about this typical node structure: I wanted to insert, append,
push, examine, delete, erase or pop data objects without having to be
continually reminded of the underlying algorithm. Also, I didn't want
to have to descend my data objects from a TNode object - I would be
forced to always use TNode descendants and couldn't use PStrings or
something along those lines. Also, by divorcing myself from knowing
about (worrying about) the node structure, I was able to make numerous
economies in data storage and speed.

However, some of these data structures cry out for being able to
navigate through the structure. The navigation is performed by the
container class' methods. Sometimes where you are in the structure is
stored internally in the container object (an internal cursor),
sometimes you have explicit 'cursors' to help you move around the
container (external cursors). All containers have methods to move
these internal and external cursors around the object. Of course
stacks and queues and similar structures do not, you can only
reference the topmost object (they are inherently non-navigable).

Also because, the node structure is hidden I was able to implement a
node suballocator scheme (called a TNodeStore; see the source) to help
me and the containers manage blocks of nodes, rather than just one at
a time.  Because the nodes are generally all the same size for a given
container type, we can take advantage of this and speed up allocations
and deallocations of nodes, compared with using the heap. So if you
look at the TNodeStore code you'll see things like node reuse, several
containers using the same node store and so on.

In 32-bit land, the TNodeStore class is fully thread-safe. Hence, just
like the normal Delphi heap, you can use several different containers
in different threads and know that their node allocation method is
perfectly safe, despite the fact that they all use the same node
store.



Iterators
----------------------------------------------------------------------
For the navigable containers (i.e. those containers where a cursor is
defined) an iterator method is defined. This method is called Iterate
and can be used to perform "first that" type processing (find the
first data object that meets a criterion) or "for all" type processing
(for all data objects in the container perform this action).

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 in
either direction: forwards or backwards.

The Action routine for a call to Iterate 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 Iterate.
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 caused 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 32-bit Delphi it must be
declared as 'register' (i.e. 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 32-bit Delphi 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.

There is one important point that you must be aware of when you are
using the Iterate method. It is simply put: do not add or delete data
objects from the container in your Action routine. The Iterate method
maintains some state information whilst you are navigating through the
container. If you add or delete an object, this state information
becomes invalid since the container may restructure itself internally
to accommodate that change. The state information that Iterate depends
upon will become out-of-date and may result in you seeing the same
data objects twice, not at all, or even worse, cause access violations
and so on. The proper thing to do is to make a note elsewhere of the
data objects you want to add or remove from the object (use another
container, e.g. a stack or queue), and once the Iterate method has
completed to perform the additions and removals.

The boolean array TBooleanArray has its own form of the iterator,
designed for iterating though either the true values in the array, or
the false ones, and in either direction. In this case, the Action
routine for a call to Iterate has to be of the form:

   TBooleanArrayIterator = function(C : TBooleanArray;
                                    aIndex : longint;
                                    ExtraData : pointer) : boolean;

where C will be the boolean array itself, aIndex is the element number
of the current boolean, and ExtraData is the same extra data pointer
you passed to Iterate. 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 index of the boolean value that caused
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 32-bit Delphi it must be declared as 'register'
(i.e. the normal fastcall declaration)).



Packages
----------------------------------------------------------------------
With the release of version 3.02, I have included an EZDSL run-time
package for each of Delphi 3, 4, 5, and 6.

The package names for version 3.02 are EZDSL3c3.DPL for Delphi 3,
EZDSL3c4.BPL for Delphi 4, EZDSL3c5.BPL for Delphi 5, and EZDSL3c6.BPL
for Delphi 6. The naming convention I am using is EZDSLnxc where n is
the major version number of EZDSL, x is the minor version number
expressed as a alphabetic character (.00=a, .01=b, etc), and c is the
Delphi compiler major version number. Hence EZDSL3a3.DPL is EZDSL
version 3.00 for Delphi 3. The Delphi 4 version of the package would
be EZDSL3a4.DPL.

I hereby reserve the rights to names of the form EZDSLnxc.DPL. If you
alter EZDSL and create a run-time package from your altered code,
please do not call it the same name as the official one. If you do so,
you may cause compatibility problems on someone else's machine if they
have an application already using the official EZDSL package.

The package is a run-time package, in other words it does not install
directly into the Delphi IDE. In fact, it would only be used if you
were creating a program that used run-time packages. If you do so,
it's best to copy the package to a directory on your path. Generally
you use \WINDOWS\SYSTEM or \WINNT\SYSTEM32; however, be warned that
Microsoft are deprecating changing the contents of the Windows system
directory.

Please refer to your Delphi documentation for more information on
packages.



Thread-safe programming in 32-bit
----------------------------------------------------------------------
32-bit Windows programming introduces a new concept (at least for
Windows programmers): multithreaded programming. You can define
sections of code that will run, for all intents and purposes, at the
same time as each other. The operating system will switch from thread
to thread in a round-robin fashion invisibly and out of your control
to give the illusion of many things happening at the same time. On
machines with multiple CPUs, each section of code (or thread) will run
on a different CPU, providing there's enough to go round, and the
threads will be executing at the same time.

This type of programming produces its own problems at the same time as
touting its benefits. The main one is called a race condition: two
different threads use and change the same variable at the same time.
Without some kind of synchronization control, the two threads will
trash the variable. For a classic example, let's assume that our two
threads are manipulating a single linked list (one of EZDSL's
TLinkList objects). Suppose that they both want to insert a new data
object into the linked list at the same time. The first thread gets
control, positions the linked list cursor and then calls InsertBefore.
Half way through the execution of the InsertBefore method, the second
thread gains control, and tries to position the cursor and call
InsertBefore itself. The problem is that InsertBefore breaks the
list's chain of pointers internally in order to insert the new data
object. If the thread doing the job loses control to another, the
linked list is in a precarious state: half broken. It is extremely
likely that the second thread doing its work will trash the linked
list permanently.

I won't go into pros and cons and synchronization of multithreaded
programs any further here, there are several books on the subject.

So what should we do? The simple answer is that we must synchronize
access to the container: a thread must be able to block all other
threads until it has finished doing its work, at which point it
relinquishes access so that another thread can do its stuff. When I
was designing the thread-safe support, I had the choice of several
paths to take:

   Add access locking and unlocking to every container method; 

   Add special routines to acquire and release locked access to the
     container;