home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c004 / 1.ddi / CTSRCH.C < prev    next >
Encoding:
C/C++ Source or Header  |  1989-04-18  |  10.8 KB  |  477 lines
  1. /*
  2.  *    index search routines
  3.  *
  4.  *    This program is the CONFIDENTIAL and PROPRIETARY property 
  5.  *    of FairCom(R) Corporation. Any unauthorized use, reproduction or
  6.  *    transfer of this program is strictly prohibited.
  7.  *
  8.  *      Copyright (c) 1984, 1985, 1986, 1987, 1988, 1989 FairCom Corporation
  9.  *    (Subject to limited distribution and
  10.  *     restricted disclosure only.)
  11.  *    *** ALL RIGHTS RESERVED ***
  12.  *
  13.  *    4006 West Broadway
  14.  *    Columbia, MO 65203
  15.  *
  16.  *
  17.  *    c-tree(R)    Version 4.3
  18.  *            Release C
  19.  *            February 7, 1989 17:30
  20.  *
  21.  */
  22.  
  23. #include "ctstdr.h"        /* standard i/o header         */
  24. #include "ctoptn.h"        /* c-tree configuration options */
  25. #include "cterrc.h"        /* c-tree error codes        */
  26. #include "ctstrc.h"        /* c-tree data structures    */
  27. #include "ctgvar.h"        /* c-tree global variables    */
  28.  
  29. COUNT compar();
  30.  
  31. /* --------------------------------------------------------------------
  32.    returns the "pointer" (ie, data record number or whatever) associated
  33.    with the key value pointed to by target for the index file specified by
  34.    keyno
  35.  */
  36.  
  37. POINTER EQLKEY(keyno,target)
  38.  
  39. PFAST COUNT keyno;
  40. TEXT *target;
  41.  
  42. {
  43.     FAST KEYFILE *knum;
  44.     LOCAL POINTER temp;
  45.     POINTER fndkey();
  46.     KEYFILE *tstfnm();
  47.  
  48.     uerr_cod = 0;
  49.     if ((knum = tstfnm(keyno)) == NULL)
  50.         return(DRNZERO);
  51.  
  52.     temp = fndkey(knum,target,'E');
  53.     knum->retelm = ct_elm;
  54.     knum->retnod = ct_fnode;
  55.     return(temp);
  56. }
  57.  
  58.  
  59. /* -------------------------------------------------------------------
  60.    returns the "pointer" associated with the first key value in the index
  61.    file specified by keyno which is equal to or greater than the key value
  62.    pointed to by target. if such an entry exists, then the variable pointed
  63.    to by idxval is set equal to the key value found in the index file
  64.  */
  65.  
  66. POINTER GTEKEY(keyno,target,idxval)
  67.  
  68. PFAST COUNT keyno;
  69. TEXT *target;
  70. TEXT *idxval;
  71.  
  72. {
  73.     FAST KEYFILE *knum;
  74.     LOCAL POINTER temp;
  75.     POINTER fndkey();
  76.     KEYFILE *tstfnm();
  77.  
  78.     uerr_cod = 0;
  79.     if ((knum = tstfnm(keyno)) == NULL)
  80.         return(DRNZERO);
  81.  
  82.     if (temp = fndkey(knum,target,'G')) {
  83.         knum->retelm = ct_elm;
  84.         knum->retnod = ct_fnode;
  85.         cpybuf(idxval,ct_indkey,knum->length);
  86.     } else {
  87.         knum->retelm = 0;
  88.         knum->retnod = NODEZERO;
  89.         setnul(idxval);
  90.     }
  91.     return(temp);
  92. }
  93.  
  94.  
  95. /* --------------------------------------------------------------------
  96.    returns the "pointer" associated with the next key value (in ascending
  97.    key value order) and sets the variable pointed to by idxval to this
  98.    key value. this function is used to access the key values (and their
  99.    associated "pointers" in ascending key value order.
  100.  */
  101.  
  102. POINTER NXTKEY(keyno,idxval)
  103.  
  104. COUNT keyno;
  105. TEXT *idxval;
  106.  
  107. {
  108.     FAST KEYFILE *knum;
  109.     FAST COUNT temp;
  110.     FAST TREEBUFF *ret;
  111.  
  112.     POINTER drnpnt();
  113.     TEXT *valpnt();
  114.     TREEBUFF *getnod();
  115.     KEYFILE *tstfnm();
  116.  
  117.     uerr_cod = 0;
  118.     if ((knum = tstfnm(keyno)) == NULL)
  119.         return(DRNZERO);
  120.  
  121. again:
  122.     if (!knum->retnod) {
  123.         setnul(idxval);
  124.         return(DRNZERO);
  125.     }
  126.     if ((ret = getnod(knum->retnod,knum)) == NULL) /* then error */
  127.         return(DRNZERO);
  128.     if ((temp = knum->retelm) < ret->nkv) {
  129.         cpybuf(idxval,valpnt(ret,++temp),knum->length);
  130.         knum->retelm = temp;
  131.         return(drnpnt(ret,temp));
  132.     } else {
  133.         knum->retnod = ret->sucesr;
  134.         knum->retelm = 0;
  135.         goto again;
  136.     }
  137. }
  138.  
  139.  
  140. /* --------------------------------------------------------------------
  141.    returns the "pointer" associated with the previous key value and sets 
  142.    the variable pointed to by idxval equal to this key value. this function
  143.    is used to access the key values (and their associated "pointers") in
  144.    descending key value order.
  145.  */
  146.  
  147. POINTER PRVKEY(keyno,idxval)
  148.  
  149. COUNT keyno;
  150. TEXT *idxval;
  151.  
  152. {
  153.     FAST TREEBUFF *ret;
  154.     FAST COUNT prdtst,temp;
  155.     FAST KEYFILE *knum;
  156.     LONG    oldnode;
  157.  
  158.     POINTER drnpnt();
  159.     TEXT *valpnt();
  160.     TREEBUFF *getnod();
  161.     KEYFILE *tstfnm();
  162.     COUNT uerr();
  163.  
  164.     uerr_cod = 0;
  165.     if ((knum = tstfnm(keyno)) == NULL)
  166.         return(DRNZERO);
  167.  
  168.     if(!knum->retnod) {
  169.         setnul(idxval);
  170.         return(DRNZERO);
  171.     }
  172.  
  173.     prdtst = PRDRPEAT;
  174.  
  175. split:
  176.     if ((ret = getnod((oldnode = knum->retnod),knum)) == NULL)
  177.         return(DRNZERO); /* then error */
  178. again2:
  179.     if ((temp = knum->retelm) > 1) {
  180.         cpybuf(idxval,valpnt(ret,--temp),knum->length);
  181.         knum->retelm = temp;
  182.         return(drnpnt(ret,temp));
  183.     } else if (knum->retnod = ret->predsr) {
  184.         if ((ret = getnod(knum->retnod,knum)) == NULL) /* then error */
  185.             return(DRNZERO);
  186.         if ((temp = ret->nkv) < 0)
  187.             terr(211);
  188.         if (oldnode != ret->sucesr) {
  189.             if (!(prdtst--)) {
  190.                 uerr(PRDS_ERR);
  191.                 return(DRNZERO);
  192.             }
  193.             knum->retnod = oldnode;
  194.             goto split;    /* node splitting at time of request */
  195.         }
  196.         knum->retelm = temp;
  197.         if (!temp) {
  198.             oldnode = knum->retnod;
  199.             goto again2;
  200.         }
  201.         cpybuf(idxval,valpnt(ret,temp),knum->length);
  202.         return(drnpnt(ret,temp));
  203.     } else {
  204.         setnul(idxval);
  205.         return(DRNZERO);
  206.     }
  207. }
  208.  
  209. /* --------------------------------------------------------------------
  210.    find first index entry.
  211.  */
  212.  
  213. POINTER FRSKEY(keyno,idxval)
  214.  
  215. PFAST COUNT keyno;
  216. TEXT *idxval;
  217.  
  218. {
  219.     LOCAL LONG    node;
  220.     FAST TREEBUFF *buffer;
  221.     FAST KEYFILE *knum;
  222.  
  223.     TREEBUFF *getnod();
  224.     COUNT uerr();
  225.     KEYFILE *tstfnm();
  226.     LONG    gtroot(),nodpnt();
  227.     TEXT *valpnt();
  228.     POINTER drnpnt();
  229.  
  230.     uerr_cod = 0;
  231.     if ((knum = tstfnm(keyno)) == NULL)
  232.         return(DRNZERO);
  233.  
  234.     if (!(node = gtroot(knum)))
  235.         goto empty;
  236.  
  237.     while (node) {    /* walk down tree until leaf node found */
  238.         if ((buffer = getnod(node,knum)) == NULL)
  239.             return(DRNZERO);
  240.         if (buffer->leaf == LEAF)
  241.             break;
  242.         node = nodpnt(buffer,1);
  243.     }
  244.     if (!node)    /* => no leaf node found */
  245.         terr(212);
  246.  
  247.     while (!buffer->nkv) /* walk across empty left most leaf nodes */
  248.         if (!(node = buffer->sucesr))
  249.             goto empty;
  250.         else if ((buffer = getnod(node,knum)) == NULL)
  251.             return(DRNZERO);
  252.  
  253.     knum->retnod = node;
  254.     knum->retelm = 1;
  255.     cpybuf(idxval,valpnt(buffer,1),knum->length);
  256.     return(drnpnt(buffer,1));
  257.  
  258. empty:
  259.     setnul(idxval);
  260.     knum->retelm = 0;
  261.     knum->retnod = NODEZERO;
  262.     return(DRNZERO);
  263.  
  264. }
  265.  
  266.  
  267. /* --------------------------------------------------------------------
  268.    find LAST index entry.
  269.  */
  270.  
  271. POINTER LSTKEY(keyno,idxval)
  272.  
  273. FAST COUNT keyno;
  274. TEXT *idxval;
  275.  
  276. {
  277.     LOCAL LONG    node;
  278.     FAST TREEBUFF *buffer;
  279.     FAST KEYFILE *knum;
  280.     FAST COUNT tmpsiz;
  281.  
  282.     TREEBUFF *getnod();
  283.     TEXT *valpnt();
  284.     KEYFILE *tstfnm();
  285.     LONG    gtroot(),nodpnt();
  286.     POINTER drnpnt();
  287.  
  288.     uerr_cod = 0;
  289.     if ((knum = tstfnm(keyno)) == NULL)
  290.         return(DRNZERO);
  291.  
  292.     if (!(node = gtroot(knum)))
  293.         goto empty2;
  294.  
  295.     while (node) {    /* walk down or across tree until leaf node found */
  296.         if ((buffer = getnod(node,knum)) == NULL)
  297.             return(DRNZERO);
  298.         if (buffer->leaf == LEAF)
  299.             break;
  300.         if (!(node = buffer->sucesr))
  301.             node = nodpnt(buffer,buffer->nkv);
  302.     }
  303.     if (!node)    /* => no leaf node found */
  304.         terr(213);
  305.  
  306.     while (!buffer->nkv) /* walk across empty rightmost leaf nodes */
  307.         if(!(node = buffer->predsr))
  308.             goto empty2;
  309.         else if ((buffer = getnod(node,knum)) == NULL)
  310.             return(DRNZERO);
  311.  
  312.     knum->retnod = node;
  313.     knum->retelm = tmpsiz = buffer->nkv;
  314.     cpybuf(idxval,valpnt(buffer,tmpsiz),knum->length);
  315.     return(drnpnt(buffer,tmpsiz));
  316.  
  317. empty2:
  318.     setnul(idxval);
  319.     knum->retelm = 0;
  320.     knum->retnod = NODEZERO;
  321.     return(DRNZERO);
  322. }
  323.  
  324. /* ---------------------------------------------------------------------
  325.    returns entry after target value
  326.  */
  327.  
  328. POINTER GTKEY(keyno,target,idxval)
  329.  
  330. PFAST COUNT keyno;
  331. TEXT *target;
  332. TEXT *idxval;
  333.  
  334.  
  335. {
  336.     POINTER GTEKEY(),NXTKEY();
  337.     POINTER temp;
  338.  
  339.     if ((temp = GTEKEY(keyno,target,idxval)) == DRNZERO || ct_tky) 
  340.         return(temp);
  341.     else
  342.         return(NXTKEY(keyno,idxval));
  343. }
  344.  
  345. /* ---------------------------------------------------------------------
  346.    returns entry immediately before target
  347.  */
  348.  
  349. POINTER LTKEY(keyno,target,idxval)
  350.  
  351. PFAST COUNT keyno;
  352. TEXT *target;
  353. TEXT *idxval;
  354.  
  355.  
  356. {
  357.     POINTER EQLKEY(),PRVKEY();
  358.  
  359.     EQLKEY(keyno,target);
  360.     return(PRVKEY(keyno,idxval));
  361. }    
  362.  
  363.  
  364. /* ---------------------------------------------------------------------
  365.    returns entry <= target
  366.  */
  367.  
  368. POINTER LTEKEY(keyno,target,idxval)
  369.  
  370. PFAST COUNT keyno;
  371. TEXT *target;
  372. TEXT *idxval;
  373.  
  374.  
  375. {
  376.     POINTER retval;
  377.  
  378.     POINTER EQLKEY(),PRVKEY();
  379.  
  380.     if (retval = EQLKEY(keyno,target)) {
  381.         cpybuf(idxval,target,(ct_key + keyno)->length);
  382.         return(retval);
  383.     } else
  384.         return(PRVKEY(keyno,idxval));
  385. }    
  386.  
  387.  
  388. /* --------------------------------------------------------------------
  389.  general purpose search routine. ordinarily not called by application
  390.    program; but called from other searches: rtriev, search, etc.
  391.  */
  392.  
  393. POINTER fndkey(knum,idxval,stratg)
  394.  
  395. PFAST KEYFILE *knum;     /* pointer to ct_key structure (used like a ct_key #) */
  396. TEXT *idxval;         /* pointer to target key value */
  397. TEXT stratg;         /* search strategy indicator 'E'== equality
  398.                'G' == greater than or equal to search */
  399.  
  400. {
  401.     TREEBUFF *getnod();
  402.     POINTER serlef();
  403.     LONG    gtroot(),nodpnt();
  404.     TEXT *valpnt();
  405.     COUNT nodser();
  406.  
  407.     LOCAL LONG    node;
  408.     LOCAL COUNT npoint;
  409.     FAST TREEBUFF *buffer;
  410.  
  411.  
  412.     ct_fnode = ct_lnode = 0;    /* global var tracking last node visited */
  413.     setnul(ct_indkey);        /* set return key value to null */
  414.     if (!(node = gtroot(knum))) {    /* tree may be empty or error */
  415.         ct_elm = 0;
  416.         return(DRNZERO);
  417.     }
  418.  
  419.     while (node) {    /* walk down or across tree until leaf node found */
  420.         ct_lnode = node;
  421.         if ((buffer = getnod(node,knum)) == NULL) /* then error */
  422.             return(DRNZERO);
  423.         if (buffer->leaf == LEAF) /* then found bottom level of tree */
  424.             break;
  425.         if ((npoint = nodser(buffer,idxval,'L')) != -1) {
  426.             if (npoint == -2) /* then corrupt tree */
  427.             terr(214);
  428.             /* get child node */
  429.             node = nodpnt(buffer,npoint);
  430.         } else
  431.             /* move right because of incomplete tree update */
  432.             node = buffer->sucesr;
  433.     }
  434.  
  435.     if (!node)    /* then no leaf node found */
  436.         terr(215);
  437.  
  438.     return(serlef(idxval,knum,buffer,stratg)); /* search leaf node */
  439. }
  440.  
  441.  
  442. /* --------------------------------------------------------------------
  443.    search leaf node 
  444.  */
  445.  
  446. POINTER serlef(idxval,knum,buffer,stratg)
  447.  
  448. TEXT *idxval;        /* pointer to target key value */
  449. PFAST KEYFILE *knum;     /* key number pointer */
  450. PFAST TREEBUFF *buffer; /* pointer to buffer containing leaf node */
  451. TEXT stratg;         /* 'E/G': see fndkey */
  452.  
  453. {
  454.     LOCAL COUNT temp;
  455.  
  456.     COUNT nodser();
  457.     POINTER drnpnt();
  458.     TEXT *valpnt();
  459.     TREEBUFF *getnod();
  460.  
  461. /* see if it is necessary to move right along leaf nodes */
  462.  
  463.     while ((temp = nodser(buffer,idxval,stratg == 'E' ? 'E' : 'S')) == -1)
  464.         if ((buffer = getnod((ct_lnode = buffer->sucesr),knum)) == NULL)
  465.             return(DRNZERO); /* error in getnod */
  466.  
  467.     ct_fnode = ct_lnode;
  468.     if (temp != -2) { /* then sucessful leaf search */
  469.         cpybuf(ct_indkey,valpnt(buffer,temp),
  470.             knum->length); /* copy key value found into ct_indkey. */
  471.         return(drnpnt(buffer,temp));
  472.     } else          /* target not found */
  473.         return(DRNZERO);
  474. }
  475.  
  476. /* end of ctsrch.c */
  477.