home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c023 / 1.img / PROGRAMS / CHKBTREE.C < prev    next >
Encoding:
C/C++ Source or Header  |  1988-01-06  |  7.0 KB  |  225 lines
  1. /* (C) Copyright 1984,85,86,87 Walter L. Peacock   All Rights Reserved   */
  2. /* THIS PROGRAM BELONGS TO WALTER L. PEACOCK.  IT IS CONSIDERED A TRADE */
  3. /* SECRET AND IS NOT TO BE DIVULGED OR USED BY PARTIES WHO HAVE NOT   */
  4. /* RECEIVED WRITTEN AUTHORIZATION FROM THE OWNER.                  */
  5.  
  6. /*-----------------------------------------------------------------------
  7. The utility ckbtree performs integrity checks on the specified b+tree
  8. index file.  It verifies that all index nodes and data nodes are properly
  9. linked and sequenced.  It also checks the order of keys within each node.
  10. -------------------------------------------------------------------------*/
  11. /* 09/11/87  C K B T R E E . C   check btree pointers and keys       */
  12.  
  13. #include <stdio.h>
  14. #include "cbtree.h"
  15. /* btfio.h *must* be included when bt_open() is used */
  16. #include "btfio.h"
  17.  
  18. #if CI | DC
  19. #else
  20. #include <ctype.h>
  21. #endif
  22.  
  23. long keyicnt, idxdcnt, idxtcnt;
  24. int ckkeyans;
  25. char *lastkey;
  26.  
  27. void main(argc, argv)
  28. int argc;
  29. char **argv;
  30. {
  31.    extern char *strcpy(), *calloc(), *strcat();
  32.    extern int   strlen(), exit(), atoi(), cklvlptr();
  33.    extern void free();
  34.    extern long getroot();
  35.    long rootptr, savlvlpt, savlvl, depth;
  36.    struct btcommo btstruct;
  37.    BTIDXBLK *idxblk;
  38.    int fdidx;
  39.    register int i;
  40.  
  41.    wopen("CON:0/0/640/200/Ckbtree");
  42.  
  43.    scr_clr();   /* clear the screen */
  44.    scr_curs(1,24);
  45.    printf("CHECK B+TREE STRUCTURE");
  46.    scr_curs(3, 3);
  47.    printf("o   Reads each index block and verifies that internal pointers");
  48.    scr_curs(4, 3);
  49.    printf("o   are consistent.  Also verifies that keys are in proper sequence");
  50.    scr_curs(5, 3);
  51.    printf("o   and accumulates the total key count at the leaf node.");
  52.  
  53.    getbname(argc, argv, &btstruct);
  54.  
  55.    scr_curs(9, 3);
  56.    printf("    Beginning check of index page pointers. ");
  57.  
  58.    ckkeyans = 1;     /* check key sequences */
  59.  
  60.       /* open btstruct.idx file   */
  61.    if( (fdidx = bt_open(btstruct.idxname, O_RDONLY) ) == ERR)
  62.       ckerror(- CK_OPEN, "ckbtree");
  63.  
  64.    i = sizeof(BTIDXBLK) + btstruct.btcells * sizeof(BTIDX);
  65.    if( !(idxblk = (BTIDXBLK *) calloc(i, SZCHAR) ))
  66.       ckerror(- CK_NOMEM, "cbtrseq: idxblk");
  67.  
  68.    if( !(lastkey = (char *) calloc(btstruct.btkeylen + 1, 1) ))
  69.       ckerror(- CK_NOMEM, "ckbtree: lastkey");
  70.  
  71.    keyicnt = idxdcnt = idxtcnt = 0L;
  72.    depth = 1L;
  73.    idxblk->blkalloc = 0;
  74.  
  75.    rootptr = getroot(fdidx, btstruct.findroot);  /* get ptr to idx root node */
  76.    
  77.    getidxr(fdidx, rootptr, idxblk, btstruct.btidxlen, btstruct.btkeylen);
  78.    savlvl = idxblk->btpage[0].btptr;
  79.  
  80.    scr_curs(11, 16);
  81.    printf("Depth    Node     Key Count", rootptr);
  82.    scr_curs(12, 16);
  83.    printf("%3ld  %7ld             ", depth++, rootptr);
  84.  
  85.    strcpy(lastkey, "");   /* initialize at each level */
  86.  
  87.    if (cklvlptr(fdidx, rootptr, idxblk, btstruct.btidxlen, btstruct.btkeylen,ckkeyans) < 1){
  88.       printf("\nB+tree error detected!!!  Rebuild index before continuing.");
  89.       goto ckb_0exit;
  90.    }
  91.  
  92.    while(!idxblk->blktype && savlvl){  /* until data block type = 1 located  */
  93.       getidxr(fdidx, savlvl, idxblk, btstruct.btidxlen, btstruct.btkeylen);
  94.       savlvlpt = idxblk->btpage[0].btptr;
  95.  
  96.       scr_curs(12, 16);
  97.       printf("%3ld  %7ld ", depth++, savlvl);
  98.  
  99.       strcpy(lastkey, "");   /* initialize at each level */
  100.  
  101.       if (cklvlptr(fdidx, savlvl, idxblk, btstruct.btidxlen, btstruct.btkeylen,ckkeyans) < 1){
  102.          printf("\nB+tree error detected!!!  Rebuild index before continuing.");
  103.          goto ckb_0exit;
  104.       }
  105.       savlvl = savlvlpt;
  106.    }
  107.  
  108.    /* keyicnt includes the null cell 7F */
  109.    printf("\n\n%s checks out O.K.",btstruct.btname);
  110.    printf("\nKey count = %ld", keyicnt-1);
  111.    printf("\nData nodes = %ld   Index nodes = %ld   Total nodes in tree = %ld ",
  112.          idxdcnt, idxtcnt - idxdcnt, idxtcnt);
  113.    printf("\nPercent full data nodes = %u %%",  (100 * keyicnt)/(idxdcnt * btstruct.btcells) );
  114.    printf("\nAverage cells per node = %u ", keyicnt/idxdcnt);
  115.    printf("\tMaximum cells per node = %u\n", btstruct.btcells);
  116.  
  117.    /************************
  118.    printf("\n\nPercent full entire tree= %4.2f;  Average cells per node = %6.2f; ",
  119.       (double) ((double) (keyicnt/idxtcnt)/btstruct.btcells) * 100, (double) (keyicnt/idxtcnt));
  120.    *********************/
  121.  
  122. ckb_0exit:
  123.    FREE(lastkey);
  124.    freekeys(idxblk);
  125.    FREE(idxblk);
  126.    close(fdidx);
  127.    btrterm(&btstruct);
  128.    wclose();   /* close Amiga window */
  129. }
  130.  
  131. /* check each node for proper forward and backward pointers */
  132.  
  133. int cklvlptr(fd, idxptr, idxblk, idxlen, keylen, ckkeyfl) 
  134. int fd, ckkeyfl;
  135. long idxptr;
  136. unsigned idxlen, keylen;
  137. struct btidxblk *idxblk;
  138. {
  139.    int moreidx = 1, ckkeys();
  140.    long savcurpt, savfwdpt;
  141.  
  142.    savcurpt = idxptr;
  143.     idxtcnt++;
  144.  
  145.    if(idxblk->bwdpage > 1L){   /* the bwdpage for the first node should be 0 */
  146.       printf("\nFirst backward pointer is invalid.");
  147.       return(-1);
  148.    }
  149.  
  150.    keyicnt = idxdcnt = 0L;
  151.  
  152.    while(moreidx){
  153.       if(idxblk->blktype){      /* count keys on leaf node */
  154.          idxdcnt++;                  /* count leaf nodes */
  155.          keyicnt += idxblk->cellicnt;    /* accumulate key count    */
  156.          scr_curs(12, 30);
  157.          printf("%8ld", keyicnt - 1);
  158.       }
  159.  
  160.       if(ckkeyfl)         /* check keys within index block */
  161.          if (ckkeys(idxblk, keylen) < 1)   
  162.             return(-1);
  163.  
  164.       if( (savfwdpt = idxblk->fwdpage) > 1L)
  165.       {
  166.          getidxr(fd, idxblk->fwdpage, idxblk, idxlen, keylen);
  167.  
  168.          scr_curs(12, 21);
  169.          printf("%7ld", idxblk->fwdpage);
  170.  
  171.             idxtcnt++;
  172.  
  173.          if(idxblk->bwdpage != savcurpt){   /* doesn't point back */
  174.             printf("\nBackward pointer is invalid.");
  175.             return(-1);
  176.          }
  177.  
  178.          savcurpt = savfwdpt;      /* save the new current position */
  179.       }
  180.       else
  181.          moreidx = 0;
  182.    }
  183.  
  184.    return(1);
  185. }
  186.  
  187. /* check index block keys for proper sequence */
  188.  
  189. int ckkeys(idxblk, keylen)
  190. struct btidxblk *idxblk;
  191. unsigned int keylen;
  192. {
  193.    extern char *strcpy();
  194.    register int m;
  195.  
  196.    if (strcmp(lastkey,idxblk->btpage[0].skeynme) > 0){
  197.       printf("\nKeys out of sequence between index pages.");
  198.       return(-1);      /* keys out of sequence between index pages */
  199.    }
  200.  
  201.    if (strlen(idxblk->btpage[0].skeynme) > keylen){
  202.       printf("\nKey is not properly null terminated.");
  203.       return(-1);      /* key is not properly null terminated */
  204.    }
  205.  
  206.    for(m = 1; m < idxblk->cellicnt; m++){
  207.       if (strcmp(idxblk->btpage[m-1].skeynme,idxblk->btpage[m].skeynme) > 0){
  208.          printf("\nKeys out of sequence between index pages.");
  209.          return(-1);         /* keys out of sequence    */
  210.       }
  211.  
  212.       if (strlen(idxblk->btpage[m].skeynme) > keylen){
  213.          printf("\nKey is not properly null terminated.");
  214.          return(-1);      /* key is not properly null terminated */
  215.       }
  216.    }
  217.  
  218.    strcpy(lastkey, idxblk->btpage[idxblk->cellicnt - 1].skeynme);
  219.  
  220.     scr_curs(14, 28);
  221.     printf("%-12.12s ", lastkey);
  222.  
  223.    return(1);
  224. }
  225.