AVL Tree Source Code Test Program

Article

Organization

Home » Linoleum Source Code » AVL Tree » Source Code Test Program

Scope

This is the source code of the AVL Tree Test Program, testing the AVL Tree library, implemented in the Linoleum programming language.

Author

Herbert Glarner

Usage

This test program tests functionality and measures performance of the AVL library.

Make sure you have the library named avl.txt in the same folder as this test program before assembling the latter.

Run the assembled exe.

Source Code

(Test application, using the AVL Library Routines "AVL.txt".)

(*****************************************************************************)
"libraries"

    (=========================================================================)
    (AVL Tree)
    (-------------------------------------------------------------------------)
    (The library which is tested with this test program.)
    (-------------------------------------------------------------------------)
        AVL;                            
    (=========================================================================)

    (=========================================================================)
    (Random Number Generator)
    (-------------------------------------------------------------------------)
    (We feed the AVL tree with a high number of nodes, having random keys.
    To use random keys, we need to generate random numbers. RNG is a very fast 
    Random Number Generator implementation by me, using the Mersenne Twister 
    algorithm from Takuji Nishimura and Makoto Matsumoto. The Linoleum source 
    can be found at following link.
        http://herbert.wikispaces.com/MT19937+Library   
    Copy the source and save as 'RNG.txt' in the same folder as this library 
    before compiling. Note that you find also a test program for the RNG
    there, if you want to explore the RNG separately.)
    (-------------------------------------------------------------------------)
        RNG;                            
    (=========================================================================)
        

(*****************************************************************************)
"directors"
        program name = { AVL Test };
        unit = 32;
        
(*****************************************************************************)
"constants"                             (Convention: "AVL ...", UPPER CASE)

    (=========================================================================)
    (Number of AVL Entries to manage)
    (-------------------------------------------------------------------------)
    (Requires 6 units per node, with 10 million nodes thus 60MB RAM.

    Adding 10 million nodes require approx. 51 seconds on a 1328 MHz Pentium 4,
    including generation of 10 million random numbers as per RNG library.
    However, generation of randoms are practically negiglible, as the RNG
    library creates 29.4 million per second on the same machine, reducing
    the test scenario by a mere 1/3 second. Thus, performance on this machine
    is approx. 197,400 nodes per second for a total of 10 million insertions,
    somewhat faster for less nodes, e.g. 229,000/s for a total of 5 million
    insertions; somewhat slower for more nodes, e.g. 173,400 nodes/s for a
    total of 20 million nodes.)
    
    (Retrieving nodes by an arbitrary random key, in the same random sequence
    as used to build the tree, depends on the number of existing nodes.
    With 5 million nodes we retrieve approx. 227,300 nodes/second,
    With 10 million nodes we retrieve approx. 204,100 nodes/second,
    With 20 million nodes we retrieve approx. 185,200 nodes/second.)
    
    (Deletions come at a speed of 833,300 nodes/second for a total of 10 million
    nodes and still 714,300/s for a total of 20 million nodes.)

    (For a more realistic number of 1 million nodes, creating a tree with
    1 million nodes, retrieving 1 million nodes and removing all nodes, we
    need 7 seconds, including twice the generation of 1 million random
    numbers. With this quantity, lookups are done with approx. 333,300 nodes/s.)
    
    (Note, that insertions and deletions operate on increasing and decreasing
    trees, but lookups on a constant number of nodes.)
    (-------------------------------------------------------------------------)
    (Set to 10 000 000 if you want to compare above data on your own machine,
    if you have 240 MB of free RAM: each node requires 6 units = 24 bytes.
    Jump over the loop for removing nodes, when you want to test only
    insertions of nodes.)
        AVL ENTRIES = 1 000 000;        (Inserts/Finds/Removes so many nodes)
    (=========================================================================)

(*****************************************************************************)
"variables"                             (Convention: "avl ...", lower case)

    (=========================================================================)
    (Saved old RAM pointer before memory allocation)
    (-------------------------------------------------------------------------)
        avl test old ram = 0;
    (=========================================================================)

    (=========================================================================)
    (Some variables to measure the time.)
    (-------------------------------------------------------------------------)
        avl test time start = 0;
        avl test time total = 0;
        avl test time per measurement = 0;
    (=========================================================================)

(*****************************************************************************)
"workspace"                             (Convention: "avl ...", lower case)

    (=========================================================================)
    (Random Number Generator)
    (-------------------------------------------------------------------------)
        rng init key = 4;               
    (=========================================================================)

(*****************************************************************************)
"programme"                             (Convention: "Avl ...", Mixed case)

    (=========================================================================)
    (Test setup)
    (-------------------------------------------------------------------------)
    (Test Loop 1:   Add AVL ENTRIES new nodes with random key)
    (Do the following two loops multiple times in an outer loop)
    (Test Loop 2:   Delete AVL ENTRIES/4 nodes at random position)
    (Test Loop 3:   Add AVL ENTRIES/4 new nodes with random key)
    (=========================================================================)


    (=========================================================================)
    (Timing the time needed to time.)
    (=========================================================================)
        C = 100;                        (Measure 100 times)
    "Dic Test Measure Measurement"
        [TimerCommand] = READ COUNTS;
        isocall;
        [avl test time start] = [Counts];        
        [TimerCommand] = READ COUNTS;
        isocall;
        [avl test time start] - [Counts];
        [avl test time start] +-;
        [avl test time per measurement] + [avl test time start];
        C ^ Dic Test Measure Measurement;

    (Use rounded average)
        [avl test time per measurement] + 50;
        [avl test time per measurement] / 100;
    (=========================================================================)


    (=========================================================================)
    (Provide a memory area to hold the nodes. This can be dynamically allocated
    memory as below, or a workspace area. 6 units are needed per node: if there
    is not enough memory, the program terminates with B = 1234567890.)
    (-------------------------------------------------------------------------)
    (Define the boundaries of the memory area in which the AVL tree is held.)
        E = [RAM Top];                              (Low address of memory)
        D = E; 
        D + AVL ENTRIES mtp AVL NODE SIZE;          (Upper address of memory)
    (-------------------------------------------------------------------------)
    (Allocate RAM)
        [RAM Top] = D;                              (Upper address of memory)
        isocall;                                    (allocate new memory)
        ? ok -> Avl Test Memory Created;

    (Our error handling in this test setup is quite trivial. The register B
    will contain 1234567890 if the memory could not be allocated.)
        B = 1234567890;                             (Error 'code')
        -> Avl Test No Memory Allocated;            (Abort the test program)
    "Avl Test Memory Created"
        [avl test old ram] = E;                     (for reset in the end)
    (=========================================================================)


    (=========================================================================)
    (Initialize the AVL tree. Initialization consists merely of telling the
    library which memory area it may use.)
    (-------------------------------------------------------------------------)
        (D = D;)                            (Top of RAM)
        (E = E;)                            (Bottom of RAM)
        => Avl Init;                        (Sets initial pointers and flags)
        ? ok -> Avl Test Init Ok;
        B = [avl error];                    (Display error code in reg B)
        -> Avl Test Quit;
    "Avl Test Init Ok"
    (=========================================================================)


    (=========================================================================)
    (Initialize the Random Number Generator for the generation of random keys.
    In a real application using AVL, this would of course not be a random
    number, but some sort of ID, probably a hash function of a name or item.)
    (Source of the RNG library: http://herbert.wikispaces.com/MT19937+Library)
    (-------------------------------------------------------------------------)
        [rng init key plus 0] = 123h;
        [rng init key plus 1] = 234h;
        [rng init key plus 2] = 345h;
        [rng init key plus 3] = 456h;
        E = rng init key;                   (Address of init key)
        D = 4;                              (Length of init key)
        => Rng Init; 
    (Now each call to 'Rng Long' returns a random number in the range between
    0 and 2^32-1, both values inclusive.)
    (=========================================================================)

    
    (=========================================================================)
    (Test Loop 1: Adding AVL ENTRIES nodes with Random Numbers as the 
    entries' keys. In a practical application, the entries would not be 
    random, of course.)
    (-------------------------------------------------------------------------)
    (Test Loop I Header)
        A = AVL ENTRIES;                    (The number of 32 bit randoms)
        D = minus 1;                        ('Data' associated with each key)
        B = 0;                              (No error)
    (-------------------------------------------------------------------------)
    (Test Loop I Body)
    
    "Avl Test Add Node"
        => RNG Long;                        (Get a random long in E)

    (The only unallowed key is ffff ffffh: We can ensure that this won't be
    fed by providing 31 bit random numbers only.)
        E > 1;                              (Avoid -1 by feeding 31 bit numbers)

    (Testing might be more convenient with max 1024 nodes: smaller keys are
    easier to keep track of with pen and paper. However, realize that as soon
    as more than 1024 nodes are fed, the loop continues to search for another 
    still unused Random Number, which it never is able to find: in this case
    you successfully created a never-terminating endless loop: use Ctrl-Alt-Del
    in that situation.)
        (E > 21;)       (Additional to >1, 10 bit numbers for easier testing)

    (-------------------------------------------------------------------------)
    (Add the node with Key E to the AVL tree. If the key already exists, the
    error AVL ERR KEY EXISTS is returned in the variable [avl error], which we 
    silently ignore in this test setup. In a real application, appropriate 
    measures would be taken in the client: "Key already exists" etc. The data 
    associated with the key can be whatever content fitting in 32 bit: in a 
    real application this most likely would be an address to some memory. In 
    our test environment, the data is -1.)
        (E = E;)                            (Key of this node)
        (D = D;)                            (Data for the node with key E, -1)

(Activate if timing 'Add Node')
([TimerCommand] = READ COUNTS;
isocall;
[avl test time start] = [Counts];)
        => Avl Add Node;
        ? ok -> Avl Test Node Added;
    
    (Handling errors: if the 'key' is already existing, we fetch a new one, as
    explained above. This does not reduce the loop counter A.)
        ? [avl error] = AVL ERR KEY EXISTS -> Avl Test Add Node;

    (Any other error causes the end of the test environment, informing about 
    the occured error in register B.)
        B = [avl error];
        -> Avl Test Quit;
        
    "Avl Test Node Added"

(Activate if timing 'Add Node')
([TimerCommand] = READ COUNTS;
isocall;
[avl test time start] - [Counts];
[avl test time start] +-;
[avl test time start] - [avl test time per measurement];
[avl test time total] + [avl test time start];)

    (-------------------------------------------------------------------------)
    (Test Loop I footer)
        A ^ Avl Test Add Node; 
    (=========================================================================)



    (=========================================================================)
    (Activate if test run shall include only Insertions)
        (-> Avl Test Quit;)
    (=========================================================================)

(Activite if not interested in testing 'Avl Find Node')
-> Skip Find Nodes;        
    (=========================================================================)
    (Testing node access by key. E is loaded with the key, D contains the
    returned data. We test with the same random numbers as used for the
    production of the tree if we can find all inserted nodes.)
    (-------------------------------------------------------------------------)
    (Reinitialize the RNG with the same values to get the same random numbers
    once again.)
        [rng init key plus 0] = 123h;
        [rng init key plus 1] = 234h;
        [rng init key plus 2] = 345h;
        [rng init key plus 3] = 456h;
        E = rng init key;                   (Address of init key)
        D = 4;                              (Length of init key)
        => Rng Init; 
    (-------------------------------------------------------------------------)
        A = AVL ENTRIES;                    (The number of accesses)
    "Avl Test Find Node"
        => RNG Long;                        (Get a random long into E)      
        E > 1;                              (We used 31 bit keys)
    (Such a random like above we used as a key for a node when filling the
    tree. Thus, we must be able to find it. If not, we leave with an error.)

(Activate if timing 'Find Node')
([TimerCommand] = READ COUNTS;
isocall;
[avl test time start] = [Counts];)
    
        => Avl Find Node;                   (Node's data is returned in D)
        ? failed -> Avl Test Finding Error; (Unless we have an error of course)

(Activate if timing 'Find Node')
([TimerCommand] = READ COUNTS;
isocall;
[avl test time start] - [Counts];
[avl test time start] +-;
[avl test time start] - [avl test time per measurement];
[avl test time total] + [avl test time start];)

        A ^ Avl Test Find Node;             (Find next node)
        
        -> Avl Test All Found;              (All searched nodes found)
    (-------------------------------------------------------------------------)
    "Avl Test Finding Error"
        A = [avl error];    
        -> Avl Test No RAM into Regs;       (Report error code in A)
    (-------------------------------------------------------------------------) 
    "Avl Test All Found"
    (=========================================================================)
"Skip Find Nodes"


    (=========================================================================)
    (Activate if test run shall include only Insertions and Retrievals)
        (-> Avl Test Quit;)
    (=========================================================================)



-> Skip Deletion Of Roots; (Test this /or/ below)
    (=========================================================================)
    (Testing Delete Routine: We delete all nodes by deleting the current
    roots.)
    (-------------------------------------------------------------------------)
        A = AVL ENTRIES; 
    (-------------------------------------------------------------------------)
    "Avl Test Remove Node"
        E = [avl tree root];            (Remove the root: it always exists)
        E = [E plus AVL KEY];           (We remove by key)
        => Avl Remove Node; ? failed -> Removal error;
    (-------------------------------------------------------------------------)
        A ^ Avl Test Remove Node;
        
    (All removed. Status variable must have cleared AVL STATUS ROOT flag now.)
        ? [avl status] - AVL STATUS ROOT -> Avl Test All Removed;
        A = 88888888;                   (Error 'code' for existing root)
        B = [avl status];
        (-> Removal error;)
    (-------------------------------------------------------------------------)
    "Removal error"
        A = [avl error];

    (Follow the node to examine.)   
        B = [avl tree root];
    
    (Load some relevant data to facilitate error searching.)
        C = [B plus AVL KEY];
        D = [B plus AVL FLAGS]; D & 7h;
        E = [B plus AVL PARENT];
        -> Avl Test No RAM into Regs;
    
    "Avl Test All Removed"      
        (-> Avl Test Quit;)
    (=========================================================================) 
"Skip Deletion Of Roots"



(-> Skip Deletion Of Keys;) (Test this /or/ above)
    (=========================================================================)
    (Testing node deletion by random key. We test with the same random numbers 
    as used for the production of the tree.)
    (-------------------------------------------------------------------------)
    (Reinitialize the RNG with the same values to get the same random numbers
    once again.)
        [rng init key plus 0] = 123h;
        [rng init key plus 1] = 234h;
        [rng init key plus 2] = 345h;
        [rng init key plus 3] = 456h;
        E = rng init key;                   (Address of init key)
        D = 4;                              (Length of init key)
        => Rng Init; 
    (-------------------------------------------------------------------------)
        A = AVL ENTRIES;                    (The number of accesses)
    "Avl Test Remove By Key"
        => RNG Long;                        (Get a random long into E)      
        E > 1;                              (We used 31 bit keys)
    (Such a random like above we used as a key for a node when filling the
    tree. Thus, such a node exists and can be deleted. If not, we leave with 
    an error.)

(Activate if timing 'Remove Node')
[TimerCommand] = READ COUNTS;
isocall;
[avl test time start] = [Counts];

        => Avl Remove Node;                 
        ? failed -> Avl Test Remove By Key Error;

(Activate if timing 'Remove Node')
[TimerCommand] = READ COUNTS;
isocall;
[avl test time start] - [Counts];
[avl test time start] +-;
[avl test time start] - [avl test time per measurement];
[avl test time total] + [avl test time start];

        A ^ Avl Test Remove By Key;         (Find next node)
        
        -> Avl Test All Removed By Key;     (All searched nodes removed)
    (-------------------------------------------------------------------------)
    "Avl Test Remove By Key Error"
    (Any key may be generated multiple times by the RNG. The first time
    it occurs will remove the node, but after that we won't find the node 
    any longer. As was the case during insertions, we simply continue with
    the next random key. However, the loop counter A will not be decreased.)
        ? [avl error] = AVL ERR NO SUCH KEY -> Avl Test Remove By Key;
    
    (Other errors are reported and cause a break.)
        A = [avl error];    
        -> Avl Test No RAM into Regs;       (Report error code in A)
    (-------------------------------------------------------------------------) 
    "Avl Test All Removed By Key"
    (=========================================================================)
"Skip Deletion Of Keys"


    (=========================================================================)
    "Avl Test Quit"
    (-------------------------------------------------------------------------)
    (Reflecting the extentions of the memory variables)
        E = [avl tree bottom];              (Bottommost usable RAM)
        D = [avl tree top];                 (Topmost usable RAM)
        C = [avl tree extent];              (From top to here is in use)
    (If all nodes were used, C und E are identical, because exactly so much
    storage was allocated.)
    "Avl Test No RAM into Regs"
    (-------------------------------------------------------------------------)
    (Restoring the original memory) 
        [RAM Top] = [avl test old ram];     (Reset memory to original value)
        isocall;                            (deallocate memory)
    (-------------------------------------------------------------------------)
    "Avl Test No Memory Allocated"
    (Registers:
        A:   The actual loop counter, initially AVL ENTRIES, 0 = all done;
             if not 0, B has an error code.
        B:   Error code, 0 if no errors occured. 1234567890 indicates that
             this test environment could not allocate the required memory.
             Reduce the number in AVL ENTRIES to a value more adequate to
             your RAM. Numbers other than 0 or 1234567890 indicate a handling
             error as per AVL ERR XXX constants, given in the AVL library.
        C-E: Content of important variables of the AVL library. 
    )

A = [Counts Per Millisecond];
B = [avl test time total];

        show registers;                     (A = B = 0 if no errors)
    (=========================================================================)

(*****************************************************************************)

Linoleum Syntax Highlighting produced with LSH (© 2007 by Herbert Glarner)