home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c006 / 1.ddi / BTRGETS.C / CBTREE / LIBRARY / BTRGETS.C
Encoding:
C/C++ Source or Header  |  1987-12-02  |  16.9 KB  |  499 lines
  1. /* (C) Copyright 1984,85,86,87 Walter L. Peacock   All Rights Reserved    */
  2. /* b t r g e t s . c :    9/02/84:  retrieve function for get calls */
  3. /*---------------------------------------------------------------------------- 
  4.  * btrgets() processes the retrieval type CBTREE calls:    GETREC, GETPAR, 
  5.  * GETALL, GETNXT, GETPRV, GETSEQ, GETKEYS, GETLY, GETLE, GETGT and GETGE.
  6.  *  (Note:   GETFRST and GETLAST are handled by cbtree() ).
  7.  *---------------------------------------------------------------------------*/
  8.  
  9. #include "cbtree.h"
  10.  
  11. char *strcpy();
  12. char *strnncpy();
  13.  
  14. int btrgets(fdidx, idxblk, hdrloc, sl, dupflg, btparmst)  /* return error code */
  15.  
  16. int               fdidx; /* index-file file descriptor */
  17. struct btidxblk *idxblk;   /* index block semi-image */
  18. int               hdrloc; /* .btpage index for matched key */
  19. unsigned   sl; /* string length of search key */
  20. unsigned  *dupflg;   /* TRUE if duplicate keys exist */
  21. struct btcommo *btparmst;    /* from user */
  22. {
  23.    extern int strcmp();
  24.    extern int strncmp();
  25.    extern void free_svkey();
  26.    extern void free();
  27.    extern int mtch_loc();
  28.    extern int wrap_hdr();
  29.    struct btidx **btidxpp;     /* where to put btidx pointer */
  30.    register int i;
  31.    long savbtptr = 0L;
  32.    char *savskey, *calloc();
  33.    long *lp;
  34.    int match;
  35.    char *keyp; /* general use key pointer */
  36.    int   comp;
  37.  
  38.    if ((btparmst->btoptype == GETSEQ   ||
  39.       btparmst->btoptype == GETALL    ||
  40.       btparmst->btoptype == NEWLOC    ||
  41.       btparmst->btoptype == GETKEYS) &&
  42.       btparmst->btrecnum == (long *)NULL)
  43.    {
  44.       if ((btparmst->btrecnum = (long *)calloc(btparmst->btmax + 1,
  45.                                              sizeof(long) )) == (long *)NULL)
  46.          ckerror(- CK_NOMEM, "78");
  47.    }
  48.  
  49.    switch (btparmst->btoptype)
  50.    {
  51.  
  52.    case GETREC:   /* GETREC only returns BTCALLOK if an EXACT match occurs. */
  53.                   /* Use GETALL or GETPAR to search on partial key matches. */
  54.  
  55.       if (strcmp(btparmst->btkey, idxblk->btpage[hdrloc].skeynme) == 0)
  56.       {
  57.          btparmst->btloc = idxblk->btpage[hdrloc].btptr;
  58.          strcpy(btparmst->btkey, idxblk->btpage[hdrloc].skeynme);
  59.          return(BTCALLOK);
  60.       }
  61.       else
  62.          return(BTNOTFND);
  63.  
  64.  
  65.    case GETGT :   /* return FIRST key which is greater than, */
  66.    case GETGE :   /* greater than or equal to, */
  67.    case GETLT :   /* less than, or */
  68.    case GETLE :   /* less than or equal to the supplied PARTIAL key. */
  69.  
  70.       match = (
  71.          strncmp(btparmst->btkey, idxblk->btpage[hdrloc].skeynme, sl) == 0);
  72.  
  73.       if (btparmst->btoptype == GETGT &&    match)    /* return NEXT */
  74.       {
  75.          /***    skip ahead to next unique key   ***/
  76.          repeat
  77.          {
  78.             if ((hdrloc = wrap_hdr(hdrloc + 1, idxblk, fdidx, btparmst))
  79.                                                                == BTNOTFND)
  80.                return (BTNOTFND);
  81.          }
  82.          while(strncmp(btparmst->btkey, idxblk->btpage[hdrloc].skeynme, sl) == 0);
  83.       }
  84.  
  85.       else if ((btparmst->btoptype == GETLE && !match) ||  /* PREVIOUS */
  86.                (btparmst->btoptype == GETLT))
  87.       {
  88.          if ((hdrloc = wrap_hdr(hdrloc-1, idxblk, fdidx, btparmst))
  89.                                                                == BTNOTFND)
  90.             return (BTNOTFND);
  91.       }
  92.  
  93.       if (idxblk->btpage[hdrloc].btptr == 0L) /* end of index file */
  94.             return (BTNOTFND);
  95.  
  96.       strcpy(btparmst->btkey, idxblk->btpage[hdrloc].skeynme);
  97.       btparmst->btloc = idxblk->btpage[hdrloc].btptr;
  98.       return (BTCALLOK);
  99.  
  100.  
  101.    case GETALL:
  102.       if(!*dupflg)   /*  no duplicate keys, so return located record */
  103.       {
  104.          btparmst->btloc = btparmst->btrecnum[0] = idxblk->btpage[hdrloc].btptr;
  105.          btparmst->btrecnum[1] = 0L;
  106.          strcpy(btparmst->btkey, idxblk->btpage[hdrloc].skeynme);
  107.          free_svkey(btparmst);   /* in case this is not the first pass */
  108.          return(BTCALLOK);
  109.       }
  110.  
  111.       /* duplicates exist, find all of them: Return up to */
  112.       /* btparmst->btmax record locations */
  113.  
  114.       /* match on btloc if not zero */
  115.       if (btparmst->btloc > 0)   /* we've already matched on one key */
  116.       {                            /* find continuation point   */
  117.          if ((hdrloc = mtch_loc(hdrloc,idxblk,fdidx,btparmst)) == BTNOTFND)
  118.          {
  119.             free_svkey(btparmst);
  120.             return (BTNOTFND);
  121.          }
  122.  
  123.          /* now position hdrloc just AFTER matching record entry */
  124.          if ((hdrloc = wrap_hdr(hdrloc + 1,idxblk,fdidx,btparmst)) == BTNOTFND)
  125.          {
  126.             free_svkey(btparmst);
  127.             return (BTNOTFND);
  128.          }
  129.       }
  130.  
  131.       i = btparmst->btmax;  /* # of records to actually give back */
  132.       lp = btparmst->btrecnum;   /* long pointer: where to put them */
  133.       while ((comp =
  134.          strncmp(btparmst->btkey, idxblk->btpage[hdrloc].skeynme, sl)) == 0)
  135.       {
  136.          if (i-- == 0 || (*lp = idxblk->btpage[hdrloc].btptr) == 0L)
  137.             break;                                       /* we done */
  138.          ++lp;                    /* ready for next record */
  139.  
  140.          /* check next entry ... */
  141.          if (hdrloc + 1 >= idxblk->cellicnt)   /* end of this index blk */
  142.          {
  143.             if (idxblk->fwdpage < 2)            /* no more index blocks */
  144.                break;
  145.  
  146.             if (!savbtptr) /* only allocate once. */
  147.                if ( !(savskey = calloc(btparmst->btkeylen+1, 1)))
  148.                   ckerror(- CK_NOMEM, "25");
  149.  
  150.             savbtptr = idxblk->btpage[hdrloc].btptr;    /* remember it */
  151.             strcpy(savskey, idxblk->btpage[hdrloc].skeynme);
  152.  
  153.             getidxr(fdidx, idxblk->fwdpage,idxblk,btparmst->btidxlen,
  154.                                                          btparmst->btkeylen);
  155.             hdrloc = 0;
  156.          }
  157.          else
  158.             ++hdrloc;                                    /* end-of-tree */
  159.       }    /* end while (strncmp()) */
  160.       *lp = 0L;         /* end marker: place last record into btstruct */
  161.  
  162.       if (lp == btparmst->btrecnum)  /* none */
  163.       {
  164.          free_svkey(btparmst);
  165.          return (BTNOTFND);
  166.       }
  167.  
  168.       if ((comp == 0 && i == -1) ||   /* search NOT yet exhausted */
  169.           (comp != 0 && i == 0))   /* Search exhausted Block FULL */
  170.       {
  171.          if (btparmst->btsvkey == NULL)
  172.             if ((btparmst->btsvkey =
  173.                calloc(btparmst->btkeylen + 1, 1)) == NULL)
  174.                ckerror(- CK_NOMEM, "77");
  175.          keyp = btparmst->btsvkey;    /* where to put copy of key */
  176.       }
  177.       else   /* Search exhausted Block NOT full */
  178.       {
  179.          free_svkey(btparmst);
  180.          keyp = btparmst->btkey;   /* give user last key matched */
  181.       }
  182.  
  183.       if (hdrloc > 0)  /* remember where we are now */
  184.       {
  185.          btparmst->btloc = idxblk->btpage[hdrloc - 1].btptr;
  186.          strcpy(keyp, idxblk->btpage[hdrloc - 1].skeynme);
  187.       }
  188.       else    /* hdrloc == 0 */
  189.       {
  190.          if (savbtptr == 0L)    /* this will happen on a zero-length idx */
  191.          {
  192.             free_svkey(btparmst);
  193.             return (BTNOTFND);
  194.          }
  195.          btparmst->btloc = savbtptr;         /* last key was at the end */
  196.          strcpy(keyp, savskey);    /* of the previous node.    */
  197.       }
  198.       if (savbtptr)
  199.          FREE(savskey);
  200.  
  201.       return(BTCALLOK);
  202.  
  203.  
  204.    case GETKEYS:    /* Return all partially matching KEYS and RECORD LOCATIONS */
  205.  
  206.       if (btparmst->btloc > 0)   /* we've already matched on one key */
  207.       {                            /* find continuation point   */
  208.          if ((hdrloc = mtch_loc(hdrloc,idxblk,fdidx,btparmst)) == BTNOTFND)
  209.          {
  210.             free_svkey(btparmst);
  211.             return (BTNOTFND);
  212.          }
  213.  
  214.          /* now position hdrloc just AFTER matching record entry */
  215.          if ((hdrloc = wrap_hdr(hdrloc + 1,idxblk,fdidx,btparmst)) == BTNOTFND)
  216.          {
  217.             free_svkey(btparmst);
  218.             return (BTNOTFND);
  219.          }
  220.       }
  221.  
  222.       i = btparmst->btmax;                    /* # pointers to give back */
  223.       btidxpp = (struct btidx **)btparmst->btrecnum;    /* where to put them */
  224.       while ((comp =
  225.          strncmp(btparmst->btkey, idxblk->btpage[hdrloc].skeynme, sl)) == 0)
  226.       {
  227.          if (i-- == 0  || idxblk->btpage[hdrloc].btptr == 0L)
  228.             break;
  229.          if ((*btidxpp = (struct btidx *)calloc(sizeof(struct btidx), 1))
  230.                                                    == (struct btidx *)NULL)
  231.             ckerror(- CK_NOMEM, "75");
  232.          (*btidxpp)->btptr = idxblk->btpage[hdrloc].btptr;
  233.          if (((*btidxpp)->skeynme = calloc(btparmst->btkeylen + 1, 1))
  234.                                                                      == NULL)
  235.             ckerror(- CK_NOMEM, "76");
  236.          strnncpy((*btidxpp)->skeynme, idxblk->btpage[hdrloc].skeynme,
  237.                                                          btparmst->btkeylen);
  238.          btidxpp++;                                        /* next pointer */
  239.          if ((hdrloc = wrap_hdr(hdrloc+1, idxblk, fdidx, btparmst))
  240.                                                                == BTNOTFND)
  241.             break;                                       /* end of index */
  242.       }       /* end while (i--) */
  243.  
  244.       *btidxpp = (struct btidx *)NULL;   /* end of list marker */
  245.  
  246.       if ((long *)btidxpp == btparmst->btrecnum)  /* none */
  247.       {
  248.          free_svkey(btparmst);
  249.          return (BTNOTFND);
  250.       }
  251.  
  252.       if ((comp == 0 && i == -1) ||   /* search NOT yet exhausted */
  253.           (comp != 0 && i == 0))   /* Search exhausted Block FULL */
  254.       {
  255.          if (btparmst->btsvkey == NULL)
  256.             if ((btparmst->btsvkey =
  257.                   calloc(btparmst->btkeylen + 1, 1)) == NULL)
  258.                ckerror(- CK_NOMEM, "18");
  259.          keyp = btparmst->btsvkey;    /* where to put copy of key */
  260.       }
  261.       else                         /* no more left in this search */
  262.       {
  263.          free_svkey(btparmst);
  264.          keyp = btparmst->btkey; /* give user last key matched */
  265.       }
  266.  
  267.       /* now remember where we are so we can pick up from here next time */
  268.       if (hdrloc > 0)
  269.       {
  270.          btparmst->btloc = idxblk->btpage[hdrloc - 1].btptr;
  271.          strcpy(keyp, idxblk->btpage[hdrloc - 1].skeynme);
  272.       }
  273.       else
  274.       {
  275.          btparmst->btloc = (*(btidxpp - 1))->btptr;  /* last key was at end  */
  276.          strcpy(keyp, (*(btidxpp - 1))->skeynme);    /* of the previous node. */
  277.       }
  278.       return(BTCALLOK);
  279.  
  280.    }    /* end switch() */
  281.  
  282.          /*****************************************/
  283.          /*                                */
  284.       /*        I N T E R L U D E             */
  285.       /*                                      */
  286.       /*  The following functions check for    */
  287.       /*  a match between btloc and hdrloc   */
  288.    /*                                      */
  289.    /*****************************************/
  290.    if (btparmst->btloc > 0)
  291.    {
  292.       if ((hdrloc = mtch_loc(hdrloc,idxblk,fdidx,btparmst)) == BTNOTFND)
  293.          return (BTNOTFND);
  294.  
  295.       /* now do a little twiddling */
  296.       if (btparmst->btoptype == GETNXT || btparmst->btoptype == GETSEQ)
  297.       {
  298.          /* position hdrloc just AFTER matching record entry */
  299.          if ((hdrloc = wrap_hdr(hdrloc +1,idxblk,fdidx,btparmst)) == BTNOTFND)
  300.             return (BTNOTFND);
  301.       }
  302.    }
  303.  
  304.  
  305.    switch (btparmst->btoptype)   /* back on the road again... */
  306.    {
  307.  
  308.    default:
  309.       return(BTCOMMO);    /* btcommo structure error */
  310.  
  311.  
  312.    case GETPAR:   /* get record matching the partial key */
  313.  
  314.       if (strncmp(btparmst->btkey, idxblk->btpage[hdrloc].skeynme, sl) == 0)
  315.       {
  316.          if((savbtptr = idxblk->btpage[hdrloc].btptr) == 0)
  317.             return(BTNOTFND);
  318.          btparmst->btloc = savbtptr;
  319.          strcpy(btparmst->btkey, idxblk->btpage[hdrloc].skeynme);
  320.          return(BTCALLOK);
  321.       }
  322.       else
  323.          return(BTNOTFND);
  324.  
  325.  
  326.    case GETNXT:
  327.  
  328.       if ((savbtptr = idxblk->btpage[hdrloc].btptr) == 0L)
  329.          return(BTNOTFND);
  330.       btparmst->btloc = savbtptr;
  331.       strcpy(btparmst->btkey, idxblk->btpage[hdrloc].skeynme);
  332.       return(BTCALLOK);
  333.  
  334.  
  335.    case GETSEQ:   /* return a block of index-sequential record numbers */
  336.  
  337.       i    = btparmst->btmax;             /* # records max to give back */
  338.       lp = btparmst->btrecnum;         /* where to put them */
  339.       while (i-- != 0)
  340.       {
  341.          if ((*lp = idxblk->btpage[hdrloc].btptr) == 0L)
  342.             break;
  343.  
  344.          ++lp;              /* bump these AFTER the assignment */
  345.  
  346.          if (hdrloc + 1 >= idxblk->cellicnt)
  347.          {
  348.             if (idxblk->fwdpage < 2)
  349.                break;
  350.  
  351.             if (savbtptr == 0L)
  352.                if ((savskey = calloc(btparmst->btkeylen+1, 1)) == NULL)
  353.                   ckerror(- CK_NOMEM, "26");
  354.  
  355.             savbtptr = idxblk->btpage[hdrloc].btptr;
  356.             strcpy(savskey, idxblk->btpage[hdrloc].skeynme);
  357.  
  358.             getidxr(fdidx, idxblk->fwdpage, idxblk, btparmst->btidxlen,
  359.                                                          btparmst->btkeylen);
  360.             hdrloc = 0;
  361.          }
  362.          else
  363.             ++hdrloc;
  364.       }    /* end while (i...) */
  365.  
  366.       *lp = 0L;                     /* place last record into btstruct */
  367.       if (lp == btparmst->btrecnum)  /* none */
  368.          return (BTNOTFND);
  369.       if (hdrloc > 0)
  370.       {
  371.          btparmst->btloc = idxblk->btpage[hdrloc - 1].btptr;
  372.          strcpy(btparmst->btkey, idxblk->btpage[hdrloc - 1].skeynme);
  373.       }
  374.       else
  375.       {
  376.          if (savbtptr == 0L)    /* this will happen on a zero-length idx */
  377.             return (BTNOTFND);
  378.          btparmst->btloc = savbtptr;         /* last key was at end    */
  379.          strcpy(btparmst->btkey, savskey);  /* of the previous node. */
  380.       }
  381.       if (savbtptr)
  382.          FREE(savskey);
  383.  
  384.       return(BTCALLOK);
  385.  
  386.  
  387.    case GETPRV:   /* return index-previous KEY and RECORD NUMBER */
  388.  
  389.       /* position hdrloc just BEFORE   matching record entry */
  390.       if ((hdrloc = wrap_hdr(hdrloc-1, idxblk, fdidx, btparmst)) == BTNOTFND)
  391.             return (BTNOTFND);
  392.  
  393.       strcpy(btparmst->btkey, idxblk->btpage[hdrloc].skeynme);
  394.       btparmst->btloc = idxblk->btpage[hdrloc].btptr;
  395.       return(BTCALLOK);
  396.  
  397.    }    /* end second switch() */
  398. #if TC
  399. #else
  400.    return(BTCOMMO);  /* should never get here */
  401. #endif
  402. }
  403.  
  404. /********************************************/
  405.  
  406. int mtch_loc(hdrloc, idxblk, fdidx, btparmst)   /* match btloc to hdrloc */
  407.  
  408. int               hdrloc; /* .btpage index for matched key */
  409. struct btidxblk *idxblk;   /* index block semi-image */
  410. int               fdidx;   /* index-file file descriptor */
  411. struct btcommo *btparmst;    /* from user */
  412. {
  413.    extern int wrap_hdr();
  414.  
  415.    while (btparmst->btloc != idxblk->btpage[hdrloc].btptr)
  416.    {
  417.       if ((hdrloc = wrap_hdr(hdrloc + 1,idxblk,fdidx,btparmst)) == BTNOTFND)
  418.          return (BTNOTFND);
  419.    }
  420.    return (hdrloc);
  421. }
  422.  
  423. /********************************************/
  424.  
  425. int wrap_hdr(hdrloc, idxblk, fdidx, btparmst)   /* wrap hdrloc to next block */
  426.  
  427. int               hdrloc; /* .btpage index for matched key */
  428. struct btidxblk *idxblk;   /* index block semi-image */
  429. int               fdidx;   /* index-file file descriptor */
  430. struct btcommo *btparmst;    /* from user */
  431. {
  432.    if (hdrloc < 0) /* yes, this IS needed */
  433.    {
  434.       while (hdrloc < 0)
  435.       {
  436.          if (idxblk->bwdpage > 1)
  437.          {
  438.             getidxr(fdidx, idxblk->bwdpage, idxblk, btparmst->btidxlen,
  439.                                                          btparmst->btkeylen);
  440.             hdrloc = idxblk->cellicnt + hdrloc; /* proper place in new blk */
  441.          }
  442.          else
  443.             return(BTNOTFND);
  444.       }
  445.       return (hdrloc);
  446.    }
  447.  
  448.    if (hdrloc >= idxblk->cellicnt)       /* we're off the edge */
  449.    {
  450.       if (idxblk->fwdpage > 1)   /* are there further records */
  451.       {
  452.          getidxr(fdidx, idxblk->fwdpage, idxblk, /* get next */
  453.                                     btparmst->btidxlen, btparmst->btkeylen);
  454.          return(0);                /* now we're at beginning of next block */
  455.       }
  456.       else    /* no more further records: continuation not found. */
  457.       {
  458.          btparmst->btrecnum[0] = 0L;   /* tell the human */
  459.          return(BTNOTFND);
  460.       }
  461.    }
  462.    return (hdrloc);
  463. }
  464.  
  465. /************************/
  466.  
  467. void free_svkey(btparmst)
  468.  
  469. struct btcommo *btparmst;
  470. {
  471.    extern void free();
  472.  
  473.    if (btparmst->btsvkey != NULL)
  474.    {
  475.       FREE(btparmst->btsvkey);
  476.    }
  477. }
  478.  
  479. /************************/
  480.  
  481. void free_gtkey(btparmst)    /* free get key array */
  482.  
  483. struct btcommo *btparmst;
  484. {
  485.    extern void free();
  486.    struct btidx **btidxpp;
  487.    unsigned i = btparmst->btmax;
  488.  
  489.    btidxpp = (struct btidx **)btparmst->btrecnum;
  490.  
  491.    while (i-- != 0 &&   *btidxpp != (struct btidx *)NULL)
  492.    {
  493.       FREE((*btidxpp)->skeynme);
  494.       FREE(*btidxpp);
  495.       ++btidxpp;
  496.    }
  497. }
  498.  
  499.