home *** CD-ROM | disk | FTP | other *** search
/ Frozen Fish 1: Amiga / FrozenFish-Apr94.iso / bbs / alib / d0xx / d034 / btree.lha / Btree / btree.test.c < prev    next >
Encoding:
C/C++ Source or Header  |  1986-09-03  |  21.5 KB  |  1,019 lines
  1. /***************************************************************************
  2. *
  3. * Module Name:        btree.test.c
  4. * ============
  5. *
  6. * Function:        BTREE TEST PROGRAM
  7. * =========
  8. *
  9. * Description:
  10. * ============
  11. *    -see main routine
  12. *    Libraries
  13. *    ----------
  14. *    stdio.h
  15. *    btree.c (--> btree.h)
  16. *    btree.test.h
  17. *    btree.prt.h
  18. *
  19. ******************************************************************************/
  20.  
  21. static char btree_tests[] = "@(#)btree.test.c    1.1 7/16/86";
  22.  
  23.  
  24. /*****************************************************************************
  25. * INCLUDES and TEST PROGRAM PARAMETERS
  26. *****************************************************************************/
  27.  
  28. #include "btree.c"
  29. #include "btree.test.h"
  30. #include "btree.prt.h"
  31.  
  32.     /*
  33.     Number of key values to be used
  34.     */
  35. #define MAXKEYS    1500    
  36.  
  37.     /*
  38.     Values used by flag table (below)
  39.     */
  40. #define IN_TREE        1
  41. #define NOT_IN_TREE     0
  42.  
  43.     /* 
  44.     Seed for random number generator
  45.     */
  46. static int    seed;
  47.     /* 
  48.     This array will contain boolean values -
  49.     if flag[i]=NOT_IN_TREE then key i is currently not in the tree
  50.     if flag[i]=IN_TREE     then key i is currently in the tree.
  51.     */
  52. static int    flag[MAXKEYS];    
  53.  
  54. static int    keytotal;
  55.  
  56. BTREE     tree;    /* Tree to be used */
  57.  
  58. /******************************************************************************
  59. * MAIN TEST PROGRAM
  60. ******************************************************************************/
  61.  
  62. /*
  63. ** MAIN TEST PROGRAM
  64. ** =================
  65. **
  66. ** Purpose:    Test the B-tree routines
  67. **
  68. ** Parameters:    argv[1]        = "" or a seed for the random tests
  69. **
  70. ** Returns:    A continuous set of diagnostic messages is sent to stdout
  71. **        This continues until the tests are successfully completed or
  72. **        until the first error occurs
  73. ** 
  74. ** Description:    There are 3 sets of tests performed
  75. **        (1) Random tests - a large number of random inserts, deletes
  76. **            and searches is performed.
  77. **        (2) All keys are inserted into the tree in ascending order
  78. **            then deleted in ascending order.
  79. **        (3) All keys are inserted into the tree in descending order
  80. **            then deleted in descending order.
  81. **        For the purposes of this test a limited range of keys is used
  82. **        - these are numbered 0 to MAXKEYS-1 (where MAXKEYS is #defined
  83. **        above) and a function getkey() returns the actual key value of
  84. **        a given key number - currently keys are integers so 
  85. **        getkey(i) = i.
  86. */
  87.  
  88. main(argc,argv)
  89. int    argc;
  90. char    *argv[];
  91. {
  92.     int statuscode;
  93.     int randomtest(), ascendingtest(), descendingtest();
  94.  
  95.     /* 
  96.     First thing to do is to check for a seed parameter
  97.     */
  98.     if (argc != 0)
  99.         sscanf(argv[1],"%d",&seed);
  100.     else
  101.         seed = 0;
  102.     srandom(seed);
  103.  
  104.     /*
  105.     Random test
  106.     */
  107.     statuscode = randomtest();
  108.     if (statuscode != SUCCESS)
  109.         error(statuscode);
  110.     
  111.     /*
  112.     Ascending test
  113.     */
  114.     statuscode = ascendingtest();
  115.     if (statuscode != SUCCESS)
  116.         error(statuscode);
  117.  
  118.     /*
  119.     Descending test
  120.     */
  121.     statuscode = descendingtest();
  122.     if (statuscode != SUCCESS)
  123.         error(statuscode);
  124.     
  125.     /*
  126.     Given message to say that it all worked
  127.     */
  128.     printf("\n\n----> TESTS SUCCEEDED <----\n\n\n");
  129.     exit(1);
  130. }
  131.  
  132.  
  133. /****************************************************************************
  134. * RANDOM INSERT/DELETE/SEARCH TEST
  135. ****************************************************************************/
  136.  
  137.     /*
  138.     Number of inserts + deletes + searches for random tests.
  139.     */
  140. #define PASSES        2000
  141.  
  142.     /* 
  143.     Number of actions available to random test and the codes associated 
  144.     with them.
  145.     */
  146. #define ACTIONS        3
  147. #define SEARCH        0
  148. #define INSERT        1
  149. #define DELETE        2
  150.  
  151.  
  152.  
  153. /*
  154. ** RANDOMTEST
  155. ** ==========
  156. ** Purpose:    Perform the random tests
  157. **
  158. ** Parameters:    None
  159. **
  160. ** Returns:    Diagnostic messages are continuously fed to stdout
  161. **        and upon completion/error a success/error code is returned
  162. **        SUCCESS:    Everything went okay
  163. **        others :    see routines     testsearch(),
  164. **                        testinsert(),
  165. **                        testdelete().
  166. **
  167. ** Description: For a given number of iterations (PASSES), generate a random
  168. **        key number and randomly select an insert, a delete or a search
  169. **        to do on the key corresponding to the key number. 
  170. */
  171.  
  172. int randomtest()
  173. {
  174.     int     keynumber;
  175.     int     pass,
  176.         status;
  177.     int    randrange();
  178.  
  179.     /*
  180.     Set up tree for new test
  181.     */
  182.     inittree();
  183.  
  184.     /*
  185.     Send start-of-test-banner
  186.     */
  187.     printf("**************** RANDOM TESTS *****************\n\n");
  188.  
  189.     /*
  190.     Now repeat the following process PASSES times:
  191.     1) Generate a random key value
  192.     2) Generate a random number to determine what action to perform
  193.        on that key
  194.     3) Perform the action and check the resulting tree.
  195.     */
  196.  
  197.     for (pass=1; pass<PASSES; pass++)
  198.     {
  199.         keynumber = randrange(MAXKEYS);
  200.         switch (randrange(ACTIONS))
  201.         {
  202.         case SEARCH:
  203.             status = testsearch(keynumber);
  204.             break;
  205.         case INSERT:
  206.             status = testinsert(keynumber);
  207.             break;
  208.         case DELETE:
  209.             status = testdelete(keynumber);
  210.             break;
  211.         }
  212.         if (status != SUCCESS)
  213.             return status;
  214.     }
  215.     return SUCCESS;
  216. }
  217.  
  218.  
  219. /*
  220. ** RANDRANGE
  221. ** =========
  222. **
  223. ** Purpose:    Generate a random integer within a given range
  224. **
  225. ** Parameters:    number_of_values    = range of random int to be generated
  226. **
  227. ** Returns:    a random in in the range 0..(number_of_values-1)
  228. **
  229. ** Description: Very simple - most of work done by a system routine.
  230. */
  231.  
  232. int randrange(number_of_values)
  233. int number_of_values;
  234. /* 
  235. Routine to generate a random number in a given range
  236. */
  237. {
  238.     long    random();
  239.  
  240.     return    (random() % number_of_values);
  241. }
  242.  
  243.  
  244. /*****************************************************************************
  245. * ASCENDING KEY TEST
  246. *****************************************************************************/
  247.  
  248. /*
  249. ** ASCENDINGTEST
  250. ** =============
  251. **
  252. ** Purpose:    Performs ascending key value test
  253. **
  254. ** Parameters:    None
  255. **
  256. ** Returns:    Sends continuous diagnostic stream to stdout
  257. **        Returns a success/error code at end of tests or if an error
  258. **        occurs.
  259. **
  260. ** Description: Clear the tree, fill it with keys by adding them in ascending 
  261. **        order, then delete them all in ascending key order.
  262. */
  263.  
  264. int ascendingtest()
  265. {
  266.     int    i;
  267.     int    status;
  268.  
  269.     /*
  270.     Set up tree for new test
  271.     */
  272.     inittree();
  273.  
  274.     /*
  275.     Print start-of-test banner
  276.     */
  277.     printf("*************** ASCENDING TESTS ******************\n\n");
  278.  
  279.     /*
  280.     Insert keys in order
  281.     */
  282.     for (i=0; i<MAXKEYS; i++)
  283.     {
  284.         status = testinsert(i);
  285.         if (status != SUCCESS)
  286.             return(status);
  287.     }
  288.  
  289.     /*
  290.     Delete keys in order
  291.     */
  292.     for (i=0; i<MAXKEYS; i++)
  293.     {
  294.         status = testdelete(i);
  295.         if (status != SUCCESS)
  296.             return(status);
  297.     }
  298.     return SUCCESS;
  299. }
  300.  
  301.  
  302. /*****************************************************************************
  303. * DESCENDING KEY TEST
  304. *****************************************************************************/
  305.  
  306. /*
  307. ** DESCENDINGTEST
  308. ** ==============
  309. **
  310. ** Purpose:    Performs descending key value test
  311. **
  312. ** Parameters:    None
  313. **
  314. ** Returns:    Sends continuous diagnostic stream to stdout
  315. **        Returns a success/error code at end of tests or if an error
  316. **        occurs.
  317. **
  318. ** Description: Clear the tree, fill it with keys by adding them in descending 
  319. **        order, then delete them all in descending key order.
  320. */
  321.  
  322. descendingtest()
  323. {
  324.     int    i;
  325.     int    status;
  326.  
  327.     /*
  328.     Set up tree for new test
  329.     */
  330.     inittree();
  331.     /*
  332.     Print start-of-test banner
  333.     */
  334.     printf("*************** DESCENDING TESTS ******************\n\n");
  335.  
  336.     /*
  337.     Insert keys in order
  338.     */
  339.     for (i=MAXKEYS-1; i>=0; --i)
  340.     {
  341.         status = testinsert(i);
  342.         if (status != SUCCESS)
  343.             return(status);
  344.     }
  345.  
  346.     /*
  347.     Delete keys in order
  348.     */
  349.     for (i=MAXKEYS-1; i>=0; --i)
  350.     {
  351.         status = testdelete(i);
  352.         if (status != SUCCESS)
  353.             return(status);
  354.     }
  355.     return SUCCESS;
  356. }
  357.  
  358.  
  359. /*****************************************************************************
  360. * TREE INITIALISATION
  361. *****************************************************************************/
  362.  
  363. /*
  364. ** INITTREE
  365. ** ========
  366. **
  367. ** Purpose:    Set up tree & lookup tables ready for a new test
  368. **
  369. ** Parameters:    none.
  370. **
  371. ** Returns:    none.
  372. **
  373. ** Description:    trivial.
  374. */
  375.  
  376. inittree()
  377. {
  378.     int i;
  379.  
  380.     tree = (BTREE)NULL;
  381.     for (i=0; i<MAXKEYS; i++)
  382.         flag[i] = NOT_IN_TREE;
  383.     keytotal = 0;
  384. }
  385.  
  386.  
  387. /***********************************************************************
  388. * TEST ROUTINES FOR SEARCH/INSERT/DELETE
  389. ***********************************************************************/
  390.  
  391. /*
  392. ** TESTSEARCH
  393. ** ==========
  394. ** 
  395. ** Purpose:    Test a search for a given key
  396. **
  397. ** Parameters:    keynumber    = number of key to be located
  398. **
  399. ** Returns:    A diagnostic message is sent to stdout and upon completion
  400. **        an error/success code is returned:
  401. **            SUCCESS    - everything worked
  402. **            FOUND_NON_EXISTANT_KEY
  403. **                - error - located a key when it wasn't in
  404. **                  the tree
  405. **            NOT_FOUND_EXISTING_KEY
  406. **                - error - could locate a key which should be
  407. **                  in the tree.
  408. **
  409. ** Description:    Basically, do the search and compare the result with the
  410. **        flag lookup table - also, if found successfully, check that
  411. **        the routine has returned a pointer to the correct keyed DATUM.
  412. */
  413.  
  414. int testsearch(keynumber)
  415. int keynumber;
  416. /*
  417. Routine to test the search for a key within a tree
  418. */
  419. {
  420.     KEY     getkey();
  421.     KEY     key;
  422.     DATUM     dtm;
  423.     int    i = 0;
  424.     int     status;
  425.  
  426.     /*
  427.     Translate a key number into a key value
  428.     */
  429.     key = getkey(keynumber);
  430.  
  431.     /*
  432.     Send message to log file
  433.     */
  434.     printf("Search\t");
  435.     printkey(key);
  436.  
  437.     
  438.     /*
  439.     Now attempt the search itself
  440.     */
  441.     status = Search(tree,key,&dtm);
  442.     
  443.     /*
  444.     Print out result of search
  445.     */
  446.     if (status==SUCCESS)
  447.         printf("found       \t");
  448.     else
  449.         printf("not found   \t");
  450.  
  451.     /*
  452.     We can get 2 sorts of error:
  453.     (1) A non-existant key was found
  454.     (2) An existing key could not be found
  455.     (3) 'dtm' doesn't point to the right key
  456.     */
  457.     if ((status==SUCCESS) && (flag[i]==NOT_IN_TREE))
  458.         return FOUND_NON_EXISTANT_KEY;
  459.     if ((status==KEY_NOT_FOUND_ERROR) && (flag[i]==IN_TREE))
  460.         return NOT_FOUND_EXISTING_KEY;
  461.     if ((status==SUCCESS) && (dtm.key != key))
  462.         return FOUND_WRONG_KEY;
  463.  
  464.     /*
  465.     Send final diagnostic message then exit successfully
  466.     */
  467.     printf("CORRECT\n");
  468.     return SUCCESS;
  469. }
  470.  
  471.  
  472. /*
  473. ** TESTINSERT
  474. ** ==========
  475. ** 
  476. ** Purpose:    Test the insertion of a given key
  477. **
  478. ** Parameters:    keynumber    = number of key to be inserted
  479. **
  480. ** Returns:    A diagnostic message is sent to stdout and upon completion
  481. **        an error/success code is returned:
  482. **            SUCCESS    - everything worked
  483. **            INSERTED_EXISTING_KEY
  484. **                - error - successfully inserted a key which was
  485. **                  already in the tree
  486. **            CANNOT_INSERT_KEY
  487. **                - error - could insert the key although it 
  488. **                  shouldn't be in the tree.
  489. **            also can get various errors from check_consistency()
  490. **
  491. ** Description:    Basically, do the insert, compare the result with the
  492. **        flag lookup table - if everything seems to be okay then
  493. **        update the lookup table and check the consistency of the
  494. **        new B-tree
  495. */
  496.  
  497. int testinsert(keynumber)
  498. int keynumber;
  499. {
  500.     DATUM    dtm;
  501.     int     status;
  502.  
  503.     /*
  504.     Translate key index number into a key value
  505.     */
  506.     dtm.key = getkey(keynumber);
  507.     
  508.     /*
  509.     Send message to log file
  510.     */
  511.     printf("Insert\t");
  512.     printkey(dtm.key);
  513.  
  514.     /*
  515.     Now do the insert itself - can get two main errors:
  516.     (1) Successfully inserted a key which was already there
  517.     (2) Couldn't insert a key even though it wasn't there
  518.     */
  519.     status = Insert(&tree,dtm);
  520.  
  521.     /*
  522.     Now print out result of insert 
  523.     */
  524.     if (status==SUCCESS)
  525.         printf("inserted    \t");
  526.     else
  527.         printf("not inserted\t");
  528.  
  529.     /*
  530.     Check for error
  531.     */
  532.     if ((status==SUCCESS) && (flag[keynumber]==IN_TREE))
  533.         return INSERTED_EXISTING_KEY;
  534.     if ((status==KEY_EXISTS_ERROR) && (flag[keynumber]==NOT_IN_TREE))
  535.         return CANNOT_INSERT_KEY;
  536.  
  537.     /*
  538.     Update lookup table
  539.     */
  540.     if (status==SUCCESS)
  541.     {
  542.         keytotal++;
  543.         flag[keynumber] = IN_TREE;
  544.     }
  545.  
  546.     /*
  547.     Print 'no errors' message
  548.     */
  549.     printf("CORRECT\t");
  550.  
  551.     /*
  552.     Now check consistency of tree 
  553.     */
  554.     status = check_consistency();
  555.     if (status==SUCCESS)
  556.         printf("tree still okay\n");
  557.     return status;
  558. }
  559.  
  560.  
  561. /*
  562. ** TESTDELETE
  563. ** ==========
  564. ** 
  565. ** Purpose:    Test the deletion of a given key
  566. **
  567. ** Parameters:    keynumber    = number of key to be deleted
  568. **
  569. ** Returns:    A diagnostic message is sent to stdout and upon completion
  570. **        an error/success code is returned:
  571. **            SUCCESS    - everything worked
  572. **            TREE_CORRUPTED_ERROR
  573. **                - this is an error generated by Delete()
  574. **                  itself when it thinks the tree has become
  575. **                  corrupted
  576. **            DELETED_NON_EXISTANT_KEY
  577. **                - error - successfully deleted a key which
  578. **                  should have been there in the first place
  579. **            CANNOT_DELETE_KEY
  580. **                - error - could delete a key which should have
  581. **                  been in the tree
  582. **            also can get various errors from check_consistency()
  583. **
  584. ** Description:    Basically, do the delete, compare the result with the
  585. **        flag lookup table - if everything seems to be okay then
  586. **        update the lookup table and check the consistency of the
  587. **        new B-tree
  588. */
  589.  
  590. int testdelete(keynumber)
  591. int keynumber;
  592. {
  593.     KEY    key;
  594.     int     status;
  595.  
  596.     /*
  597.     Translate key index number into a key value
  598.     */
  599.     key = getkey(keynumber);
  600.     
  601.     /*
  602.     Send message to log file
  603.     */
  604.     printf("Delete\t");
  605.     printkey(key);
  606.  
  607.     /*
  608.     Now do the delete itself - can get three main errors:
  609.     (1) Successfully deleted a key which wasn't there
  610.     (2) Couldn't delete a key even though it was there
  611.     (3) Delete detected a corrupted tree
  612.     */
  613.     status = Delete(&tree,key);
  614.  
  615.     /*
  616.     Print result of delete 
  617.     */
  618.     if (status==SUCCESS)
  619.         printf("deleted     \t");
  620.     else
  621.         printf("not deleted \t");
  622.  
  623.     /*
  624.     Check for errors
  625.     */
  626.     if (status == TREE_CORRUPTED_ERROR)
  627.         return status;
  628.     if ((status==SUCCESS) && (flag[keynumber]==NOT_IN_TREE))
  629.         return DELETED_NON_EXISTANT_KEY;
  630.     if ((status==KEY_NOT_FOUND_ERROR) && (flag[keynumber]==IN_TREE))
  631.         return CANNOT_DELETE_KEY;
  632.  
  633.     /*
  634.     Update lookup table
  635.     */
  636.     if (status==SUCCESS)
  637.     {
  638.         flag[keynumber] = NOT_IN_TREE;
  639.         --keytotal;
  640.     }
  641.  
  642.     /*
  643.     Print acknowledgement of success
  644.     */
  645.     printf("CORRECT\t");
  646.     /*
  647.     Now check consistency of tree 
  648.     */
  649.     status = check_consistency();
  650.     if (status==SUCCESS)
  651.         printf("tree still okay\n");
  652.     return status;
  653. }
  654.  
  655.  
  656. /*********************************************************************
  657. * CONSISTENCY CHECK ROUTINES
  658. *********************************************************************/
  659.  
  660.     /*
  661.     Total of number of keys found so far
  662.     */
  663. static int     total;
  664.  
  665.     /*
  666.     Depth of tree
  667.     */
  668. static int    treedepth;
  669.  
  670.  
  671. /*
  672. ** CHECKCONSISTENCY
  673. ** ================
  674. **
  675. ** Purpose:    Routine to check that a tree is in a consistent state
  676. **
  677. ** Parameters:    None
  678. **
  679. ** Returns:    One of the following error/success codes
  680. **        SUCCESS - all okay
  681. **        NODE_NOT_HALF_FULL
  682. **            - a node was found which was not half full and it
  683. **              wasn't the root.
  684. **        WRONG_KEY_IN_NODE
  685. **            - a node was found with a key value outside its
  686. **              specified range
  687. **        TREE_DEPTH_INCONSISTENT
  688. **            - the depth of the tree is not constant throughout
  689. **        KEY_TOTAL_MISMATCH
  690. **            - an external count of keys in the tree does not
  691. **              tally with a scan of the tree.
  692. **
  693. ** Description:    This routine fires off the 'performcheck' routine which
  694. **        is a recursive affair - upon return, any error from
  695. **        'performcheck' is returned to the calling routine
  696. **        - otherwise the total number of keys in the tree is checked
  697. **        and this determines the final return code.
  698. */
  699.  
  700. int check_consistency()
  701. {
  702.     KEY getkey();
  703.     int status;
  704.     
  705.     /*
  706.     Set up initial total number of keys and depth of tree
  707.     */
  708.     total = 0;
  709.     treedepth = 0;
  710.  
  711.     /*
  712.     Now do the real consistency check
  713.     */
  714.     status = performcheck(tree, 0, getkey(-1), getkey(MAXKEYS));
  715.     
  716.     /*
  717.     if this gives any sort of error, return the error code
  718.     */
  719.     if (status != SUCCESS)
  720.         return status;
  721.  
  722.     /*
  723.     The only remaining check is the number of keys in the tree
  724.     - compare the test program running total (keytotal) with the
  725.     total from this tree scan (total)
  726.     */
  727.     if (total != keytotal)
  728.         return KEY_TOTAL_MISMATCH;
  729.     return SUCCESS;
  730. }
  731.  
  732.  
  733. /*
  734. ** PERFORMCHECK
  735. ** ============
  736. **
  737. ** Purpose:    The main routine for checking consistency of a tree
  738. **
  739. ** Parameters:    tree    = pointer to (sub-)tree to be checked
  740. **        thisdepth 
  741. **            = depth of parent node (for root this is 0)
  742. **        lowkey    = lower bound on range of key values in
  743. **              current top-level node
  744. **        highkey    = upper bound on range of key values in
  745. **              current top-level node
  746. **
  747. ** Returns:    An error / success code
  748. **            SUCCESS - all okay
  749. **            TREE_DEPTH_INCONSISTENT
  750. **                - tree isn't of constant depth
  751. **            NODE_NOT_HALF_FULL
  752. **                - current top level node is not the root
  753. **                  and is not 1/2 full
  754. **            WRONG_KEY_IN_NODE
  755. **                - a key (or keys) in this node does not
  756. **                  lie in the correct key value range
  757. **            KEYS_NOT_IN_ORDER
  758. **                - at least 1 key of a node is not in order
  759. **
  760. ** Description:    This routine is a pretty complex affair and recursive to boot
  761. **        - the basic algorithm is:
  762. **        if we're at a root
  763. **        then check that depth agrees with system total
  764. **        else check size of node, range of keys in it and
  765. **        if these are okay, try all subtrees below here
  766. */
  767.  
  768. int performcheck(tree, thisdepth, lowkey, highkey)
  769. BTREE     tree;
  770. int    thisdepth;
  771. KEY    lowkey,
  772.     highkey;
  773. {
  774.     int     i;
  775.     int     keys_in_node;
  776.     KEY    lo,
  777.         hi,
  778.         upper;
  779.     int     status;
  780.  
  781.     /*
  782.     Update record of dpeth of current node
  783.     */
  784.     thisdepth++;
  785.  
  786.     /*
  787.     If current tree is null we've hit a leaf
  788.     - only check that can be performed is whether the depth is correct
  789.     */
  790.     if (tree==(BTREE)NULL)
  791.     {
  792.         /*
  793.         Check the depth we've reached
  794.         */
  795.         if (treedepth == 0)
  796.         {
  797.             /*
  798.             If overall depth is 0 then this is the first
  799.             leaf we've reached so no error
  800.             */
  801.             treedepth = thisdepth;
  802.             return SUCCESS;
  803.         }
  804.         if (treedepth != thisdepth)
  805.             /* 
  806.             if overall depth differs from current depth then
  807.             generate an error
  808.             */
  809.             return TREE_DEPTH_INCONSISTENT;
  810.         return SUCCESS;
  811.     }
  812.  
  813.     keys_in_node = tree->t_active;
  814.     /*
  815.     If not at a leaf, check whether this node is at least 1/2 full
  816.     - which is a prerequisite of all non-root nodes
  817.     */
  818.     if ((keys_in_node<M) && (thisdepth != 1))
  819.         return NODE_NOT_HALF_FULL;
  820.  
  821.     /*
  822.     Now update running total of keys found so far
  823.     */
  824.     total += keys_in_node;
  825.  
  826.     /*
  827.     Now check whether the keys in this node are between lowkey and
  828.     highkey - this only checks the left- and right- hand keys of the
  829.     node - a check for the order of keys in a node is done later.
  830.     */
  831.     if ((KeyCmp(tree->t_dat[0].key, lowkey)<=0) || 
  832.         (KeyCmp(tree->t_dat[keys_in_node-1].key, highkey)>=0))
  833.         return WRONG_KEY_IN_NODE;
  834.     
  835.     /*
  836.     If all's okay so far, go into the guts of the test - a recursive
  837.     consistency check of all nodes below here
  838.     */
  839.     for (i=0; i<=keys_in_node; i++)
  840.     {
  841.         /*
  842.         Establish 3 quantities:
  843.             lo    = lower bound on t_dat[i] and keys under t_ptr[i]
  844.             hi    = upper bound on values in t_ptr[i]
  845.             upper = upper bound on t_dat[i]
  846.         */
  847.         if (i==0)
  848.             lo = lowkey;
  849.         else
  850.             lo = tree->t_dat[i-1].key;
  851.  
  852.         if (i==keys_in_node)
  853.             hi = highkey;
  854.         else
  855.         {
  856.             hi = tree->t_dat[i].key;
  857.             
  858.             /*
  859.             The quantity 'upper' is only needed here 
  860.             (where i<keys_in_node)
  861.             */
  862.             if (i==(keys_in_node-1))
  863.                 upper = highkey;
  864.             else
  865.                 upper = tree->t_dat[i+1].key;
  866.             
  867.             /*
  868.             Now check that t_dat[i] lies between 'lo' and 'upper'
  869.             */
  870.                 if ((KeyCmp(tree->t_dat[i].key,lo)<=0) ||
  871.                 (KeyCmp(tree->t_dat[i].key,upper)>=0))
  872.                 return KEYS_NOT_IN_ORDER;
  873.         }
  874.  
  875.         /*
  876.         Do consistency check of subtree t_ptr[i]
  877.         */
  878.         status = performcheck(tree->t_ptr[i],thisdepth,lo,hi);
  879.  
  880.         /*
  881.         If a check of the subtree gave an error then bail out now
  882.         */
  883.         if (status != SUCCESS)
  884.             break;
  885.     }
  886.     return status;
  887. }
  888.         
  889.  
  890. /*************************************************************************
  891. * VARIOUS MISCELLANEOUS ROUTINES
  892. *************************************************************************/
  893.  
  894. /*
  895. ** GETKEY
  896. ** ======
  897. **
  898. ** Purpose:    Routine to translate a key number into a key value
  899. **
  900. ** Parameters:    keynumber    = number of key to be obtained
  901. **
  902. ** Returns:    Returns a key value
  903. **
  904. ** Description:    This routine is key dependent - it just returns a key value
  905. **        coresponding to a key number.
  906. **        Note that the routine must return keys with key values
  907. **        -1 ... MAXKEYS - where the 2 extremes are used in consistency
  908. **        checks for bounds on the key values in a tree.
  909. */
  910.  
  911. KEY getkey(keynumber)
  912. int keynumber;
  913. {
  914.     return keynumber;
  915. }
  916.  
  917.  
  918. /*
  919. ** PRINTKEY
  920. ** ========
  921. **
  922. ** Purpose:    Routine to print a key value
  923. **
  924. ** Parameters:    key    = key value to be printed
  925. **
  926. ** Returns:    None
  927. **
  928. ** Description:    Mind-numbingly simple
  929. */
  930.  
  931. printkey(key)
  932. KEY key;
  933. {
  934.     printf("%d\t",key);
  935. }
  936.  
  937.  
  938.  
  939. /*
  940. ** ERROR
  941. ** =====
  942. **
  943. ** Purpose:    Routine to convert an error number into an error message
  944. **
  945. ** Parameters:    errno    = error number
  946. **
  947. ** Returns:    none.
  948. **
  949. ** Description:    Nothing particularly taxing about this one
  950. */
  951.  
  952. error(errno)
  953. int errno;
  954. {
  955.     printf("\n");
  956.     switch (errno)
  957.     {
  958.     case FOUND_NON_EXISTANT_KEY:
  959.         printf("!!! SEARCH found a key which should be in the tree\n");
  960.         break;
  961.     case NOT_FOUND_EXISTING_KEY:
  962.         printf("!!! SEARCH failed to find a key which should be in the tree\n");
  963.         break;
  964.     case FOUND_WRONG_KEY:
  965.         printf("!!! SEARCH located the wrong key\n");
  966.         break;
  967.     case INSERTED_EXISTING_KEY:
  968.         printf("!!! INSERT inserted a key into the tree when it was already there\n");
  969.         break;
  970.     case CANNOT_INSERT_KEY:
  971.         printf("!!! INSERT claimed that a key was already in the tree when it wasn't\n");
  972.         break;
  973.     case DELETED_NON_EXISTANT_KEY:
  974.         printf("!!! DELETE managed to delete a key which wasn't in the tree");
  975.         break;
  976.     case CANNOT_DELETE_KEY:
  977.         printf("!!! DELETE claimed that a key wasn't in the tree when it was\n");
  978.         break;
  979.     case TREE_CORRUPTED_ERROR:
  980.         printf("!!! TREE CORRUPTED\n");
  981.         break;
  982.     case NODE_NOT_HALF_FULL:
  983.         printf("!!! CONSISTENCY ERROR - a node was found to be less than half full\n");
  984.         break;
  985.     case WRONG_KEY_IN_NODE:
  986.         printf("!!! CONSISTENCY ERROR - a key was found in the wrong node\n"); 
  987.         break;
  988.     case TREE_DEPTH_INCONSISTENT:
  989.         printf("!!! CONSISTENCY ERROR - the tree is not of constant depth\n");
  990.         break;
  991.     case KEYS_NOT_IN_ORDER:
  992.         printf("!!! CONSISTENCY ERROR - the keys within a node are not in ascending order\n");
  993.         break;
  994.     case KEY_TOTAL_MISMATCH:
  995.         printf("!!! CONSISTENCY ERROR - the total number of keys in the tree is wrong\n");
  996.         break;
  997.     }
  998.     printf("\nThe tree is :-\n");
  999.     ShowTree(tree,0);
  1000.     printf("\n\n ----> TEST ABORTED <----\n\n\n");
  1001.     exit(0);
  1002. }
  1003.  
  1004. #ifdef AMIGA    /* Quick hack for random number stuff (fnf) */
  1005.  
  1006. srandom (seed)
  1007. int seed;
  1008. {
  1009.     srand (seed);
  1010. }
  1011.  
  1012. long random ()
  1013. {
  1014.     extern int rand ();
  1015.  
  1016.     return (rand ());
  1017. }
  1018. #endif
  1019.