//--------------------------------------------------------------------------------------------------
//
//  @ CopyRight Roberti & Parau Enterprises, Inc.  2021-2023
//
//  This work is licensed under the Creative Commons Attribution 4.0 International License.
//  To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/
//   or send a letter to Creative Commons, PO Box 1866, Mountain View, CA 94042, USA.
//
//--------------------------------------------------------------------------------------------------
//
//  Driver to test and compare performance of the AVL.* macros
//  provided with the RISC-V module of DVASM, with avl.c code 
//  from SUN MIcrosystems
//
//  This program generates a set of null terminated strings each pointed
//  by an AVL tree node.  
//
//  All nodes are inserted in the tree and, optionally, half of 
//  them are removed.
//
//  The following definition are used to control compilation
//
//  #define     SIZE        number_of_strings
//
//      It must always be defined.  For example if
//
//  #define     SIZE        8
//
//      The number of strings will be 8
//
//  #define     STRSIZE     string_size
//
//      It must always be defined.  It specifies the length of
//      each string.  For example if
//
//  #define     STRSIZE     80
//
//      The length of each string will be 80 including the null terminator.
//
//  #deine      REMOVE
//
//      When specified each other node will be removed after
//      insertion
//
//  #define     REPEAT      number_of_repeat
//
//      It must always be defined.  It is used to test performance
//      For example:
//
//  #define     REPEAT      1000
//
//      will repeat the insert and remove (optional) 
//      of the same set of nodes 1000 times
//
//  #define     PRINT
//
//      When this definition is included the avl tree structure is printed
//      The output should be identical to the output, for the same setting,
//      of sunavlinsrem.c
//
#include    <stdio.h>
#include    <string.h>
#include    <stdlib.h>

//----------------------- Compilation definitions -----------------

#define     SIZE            (1 << 20)
#define     STRSIZE         (80)
#define     FUNCTION        dvasmsortstring
//#define     REMOVE
#define     REPEAT          1000

//#define     PRINT

//----------------------- End of compilation definitions ----------

typedef     struct  avlnode {
    struct  avlnode     *leftChild;
    struct  avlnode     *parent;
    struct  avlnode     *rightChild;
    char                *string;
} avlnode;

typedef     struct  avlheader  {
    avlnode             *rootNode;
} avlheader;

long        dvasmavlinsert(avlheader *header, avlnode *node);
avlnode     *dvasmavlfind(avlheader *header, char *s);
avlnode     *dvasmavlremove(avlheader *header, avlnode *node);

long        vv;

//
//  Node print function for debugging
//
void        dumpNode(avlnode *node) {

    long i= ((long) node - vv) / sizeof(avlnode);
    avlnode     *parent= (avlnode *) (((long) (node -> parent)) & ((long) -8));

    printf( "Node  %6d    ->  %s\n"
            "  Left child    ->  %s\n"
            "  Parent        ->  %s\n"
            "  Right child   ->  %s\n"
            "  Parent child  ->  %s\n"
            "  Balance       ->  %d\n",
            i,
            node -> string, 
            node -> leftChild == NULL ? "-- None --" : node -> leftChild -> string, 
            parent == NULL ? "-- None --" : parent -> string,
            node -> rightChild == NULL ? "-- None --" : node -> rightChild -> string, 
            parent == NULL ? "Root Node" :
                (((long) node -> parent) & ((long) 0b100) >> 2) == 0 ?
                "Right child" : "Left child",
            (((long) node -> parent) & 0b11)-1);
}

void    dumpTree(avlnode *node) {

    if (node -> leftChild != NULL)
        dumpTree((avlnode *) node -> leftChild);
    dumpNode(node);
    if (node -> rightChild != NULL)
        dumpTree((avlnode *) node -> rightChild);
} 

//
//  Main function
//

int     main(int argc, char **argv) {

    avlheader       header;

    //
    //  Allocate node vector and buffer
    //
    avlnode *v= (avlnode *) malloc(SIZE * sizeof(avlnode));
    vv= (long) v;
    char    *buff= (char *) malloc(SIZE * STRSIZE);
    
    //
    //  Seed the random number generator
    //
    srandom(17);

    //
    //  Generate random characters in strings
    //
    char *c= buff;
    for (int i= 0; i < SIZE * STRSIZE; i++) {
        *c= (random() % 75)+48;
        c++;
    }

    //
    //  Insert null character at the end of each string
    //  and set pointer for corresponding node
    //
    c= buff;
    for (int i= 0; i < SIZE; i++) {
        v[i].string= c;
        c[STRSIZE-1]= 0;
        c+= STRSIZE;
    }

    //
    //  start main loop
    //
    for (int k= 0; k < REPEAT; k++) {

        //
        //  Insert all nodes
        //
        for (int i= 0; i < SIZE; i++)
            dvasmavlinsert(&header, &v[i]);


        //
        //  Find and remove every even node
        //
#ifdef  REMOVE
        for (int i= 0; i < SIZE; i+= 2)
            dvasmavlremove(&header, &v[i]);
#endif

    }

    //
    //  Generate print code if PRINT is defined
    //
#ifdef  PRINT
    dumpTree(header.rootNode);
#endif

}