home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c004 / 1.ddi / CTKRNL.C < prev    next >
Encoding:
C/C++ Source or Header  |  1989-04-18  |  14.3 KB  |  632 lines
  1. /*
  2.  *    index file kernel
  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 ctio();
  30. #ifdef FPUTFGET
  31.     COUNT redhdr();
  32. #endif
  33.  
  34. /* --------------------------------------------------------------------
  35.    general purpose node search function. works with leaf and non-leaf nodes.
  36.    returns relative position in node of key value satisfying search request
  37.    as well as setting the global variable ct_elm to this value. also sets
  38.    the global variable ct_tky which indicates the sense of the comparison
  39.    between the target key value (pointed to by idxval) and the key values
  40.    actually in the index structure. if search is not satisfied, nodser
  41.    returns a value of -2. if idxval greater than high key, then nodser
  42.    returns a value of -1.
  43.  */
  44.  
  45. COUNT nodser(buffer,idxval,stratg)
  46. PFAST TREEBUFF *buffer; /*pointer to buffer containing node */
  47. TEXT *idxval;         /* pointer to target key value */
  48. TEXT stratg;         /* search strategy: E == eq  L == le  S == le (from
  49.              * leaf node)
  50.              */
  51. {
  52.     COUNT compar();
  53.     TEXT *valpnt(),*hghpnt();
  54.  
  55.     COUNT begser,endser,size,poff;
  56.     FAST KEYFILE *knum;
  57.  
  58.     knum = ct_key + buffer->keyid; /* determine key number pointer */
  59.  
  60.     begser  = 1;
  61.     endser  = buffer->nkv;
  62.     ct_tkp  = poff = 0;
  63.  
  64. /* high key comparison
  65. */
  66.     if ((buffer->leaf == LEAF && 
  67.         (compar(idxval,hghpnt(buffer),knum) > 0 ||
  68.         (stratg == 'S' && !endser && buffer->sucesr))) || 
  69.         (buffer->leaf == NOLEAF && !buffer->ktipe &&
  70.         compar(idxval,valpnt(buffer,endser),knum) > 0)) {
  71.         /* target exceeds high key value for node */
  72.         ct_tky = 1;
  73.         ct_elm = 0;
  74.         return(-1);
  75.     }
  76.  
  77. /* check for empty (leaf) node
  78. */
  79.     if (!endser) {
  80.         ct_elm = 0;
  81.         ct_tky = -1;
  82.         return(-2);
  83.     }
  84.  
  85. /* binary search of node if fixed length keys
  86. */        
  87.  
  88.     if (!buffer->ktipe) {
  89.         while ((size = endser - begser + 1) > 3) {
  90.         ct_elm = begser + size / 2;
  91.         ct_tky = compar(idxval,valpnt(buffer,ct_elm),knum);
  92.         if (ct_tky > 0)
  93.             begser = ct_elm + 1;
  94.         else if (!ct_tky)
  95.             return (ct_elm);
  96.         else
  97.             endser = ct_elm;
  98.         }
  99.         if (begser > endser) /* then corrupt node */
  100.         terr(207);
  101.     }
  102.  
  103. #ifdef VARLKEYS
  104.     else if (buffer->lstpos) {
  105.         if (buffer->confg & REGULAR)
  106.         poff = sizeof(POINTER);
  107.         ct_tkp = compar(idxval,buffer->keyexp + poff,knum);
  108.         ct_sfxctp = buffer->cursfx;
  109.         if (ct_tkp > 0)
  110.         begser = buffer->lstpos + 1;
  111.         else if (ct_tkp == 0) {
  112.         ct_tky       = 0;
  113.         ct_tkp       = -1;
  114.         return(ct_elm = buffer->lstpos);
  115.         } else
  116.         ct_tkp = 0;
  117.     }
  118. #endif
  119.  
  120. /* perform sequential search over remaining possibilities */
  121.  
  122.     for (ct_elm = begser; ct_elm <= endser; ct_elm++) {
  123.         ct_tky = compar(idxval,valpnt(buffer,ct_elm),knum);
  124.         if (ct_tky > 0) {
  125.             ct_tkp = ct_tky;
  126.             ct_sfxctp = buffer->cursfx;
  127.         } else if (ct_tky < 0 && stratg == 'E')
  128.             return(-2);
  129.         else
  130.             return(ct_elm);
  131.     }
  132.     if ((stratg == 'S' && buffer->sucesr) || (buffer->ktipe &&
  133.         buffer->leaf == NOLEAF)) {
  134.         ct_tky = 1;
  135.         ct_elm = 0;
  136.         return(-1);
  137.     } else {
  138.         ct_tky = ct_tkp;
  139.         ct_elm = buffer->nkv + 1;
  140.         return(-2);
  141.     }
  142. }
  143.  
  144. VOID setnul(s)
  145.  
  146. TEXT *s;
  147.  
  148. {
  149.     *s = '\0';
  150. }
  151.  
  152.  
  153. /* --------------------------------------------------------------------
  154.    getnod searches the buffer area for the requested b-tree node (specified
  155.    by node number and key number (pointer)). if found, it returns pointer to
  156.    buffer; else it pushes out the least recently used node and reads the
  157.    requested node into the vacated buffer, passing back a pointer to this 
  158.    buffer.
  159.  */
  160.  
  161. TREEBUFF *getnod(node,knum)
  162. LONG    node;     /* node number requested */
  163. KEYFILE *knum;     /* key number pointer */
  164. {
  165.     TREEBUFF *lrubuf();     /* function returning pointer to least
  166.                     recently used buffer */
  167.     COUNT rednod();     /* function to read node */
  168.     VOID inracs();         /* update buffer age & check for rollover */
  169.  
  170. #ifdef FPUTFGET
  171.     CTFILE          *ctnum;
  172. #endif
  173.     TREEBUFF      *getflg;
  174.     FAST TREEBUFF *fndbuf; 
  175.                         /* pointers to buffers */
  176.     FAST COUNT i; /* counter */
  177.     FAST UCOUNT lstusd; /* store for finding node (buffer) with lowest
  178.              node access number; ie lru buffer */ 
  179.  
  180.     if (node == NODEZERO)
  181.         terr(237);
  182.     getflg = fndbuf = ct_btree;
  183.     lstusd = fndbuf->nodacs;
  184.     for (i = 0; i++ < ct_mxbuf; fndbuf++) {
  185.         if (fndbuf->nodeid == node && fndbuf->keyid == knum->filnum) {
  186.  
  187. #ifdef FPUTFGET
  188.             if (fndbuf->update == 'y') 
  189.                 terr(208);
  190.             ctnum = knum - knum->kmem;
  191.             if ((ctnum->flmode & SHARED) &&
  192.                 rednod(fndbuf,node,knum))
  193.                 return(NULL);
  194. #endif
  195.  
  196.             inracs(fndbuf);            /* node found; update node
  197.                                access count and return
  198.                               pointer to buffer
  199.                             */
  200.             return(fndbuf);
  201.         }
  202.         if (fndbuf->nodacs < lstusd) /* set getflg to buffer pointer
  203.                          with lowest nodacs */
  204.             lstusd = (getflg = fndbuf)->nodacs;
  205.     }
  206.  
  207.  
  208. /* node not found in buffers. read node into lru buffer */
  209.  
  210.     if ((fndbuf = lrubuf(getflg)) == NULL) /* then error in lrubuf */
  211.         return(NULL);
  212.     if (rednod(fndbuf,node,knum))    /* then error in rednod */
  213.         return(NULL);
  214.     return(fndbuf);
  215. }
  216.  
  217.  
  218. /* --------------------------------------------------------------------
  219.    return pointer to buffer containing lru buffer. if lru buffer contains
  220.    an updated node, write out the node to appropriate index file
  221.  */
  222.   
  223. TREEBUFF *lrubuf(getflg)
  224. TREEBUFF *getflg; /* if non-zero, then pointer to buffer
  225.                    containing lru buffer; ie, the lru buffer
  226.                    has already been determined */
  227. {
  228.     COUNT wrtnod();        /* write updated node back to disk */
  229.     FAST COUNT i;        /* counter */
  230.     FAST TREEBUFF *fndbuf;     /* pointer to buffer */
  231.     FAST UCOUNT  lstusd;    /* store to determine buffer with lowest
  232.                    node access number */
  233.  
  234.     if (!getflg) {        /* lru buffer has not been determined yet */
  235.         getflg = fndbuf = ct_btree;
  236.         lstusd = fndbuf->nodacs;
  237.         for (i = 1, ++fndbuf; i++ < ct_mxbuf; fndbuf++)
  238.             if (fndbuf->nodacs < lstusd)
  239.                 lstusd = (getflg = fndbuf)->nodacs;
  240.     }
  241.  
  242. #ifdef CTSERVER
  243. #ifdef EXTRABFR
  244.     if (getflg->keyid != -1) { /* make sure buffer in use */
  245.         wrtxnod(getflg);
  246.         return(getflg);
  247.     }
  248. #endif
  249. #endif
  250.  
  251.     if (getflg->update == 'y')  /* lru node has been updated. write it */
  252.         if (wrtnod(getflg)) /* then write error */
  253.             return(NULL);
  254.     return(getflg);            /* return lru buffer ptr */
  255. }
  256.  
  257.  
  258. /* --------------------------------------------------------------------
  259.    increment buffer age & check for roll over
  260.  */
  261.  
  262. VOID inracs(buffer)
  263.  
  264. PFAST TREEBUFF *buffer;
  265.  
  266. {
  267.     FAST TREEBUFF *tmpbuf;
  268.     FAST COUNT i;
  269.     LOCAL UCOUNT minage;
  270.  
  271.     if (++ct_lacs)    /* then buffer age did not rollover */
  272.         buffer->nodacs = ct_lacs;
  273.     else {        /* buffer age rollover. must adjust all buffer ages */
  274.         tmpbuf = ct_btree;
  275.         minage = MAXAGE;
  276.         for (i = 0; i++ < ct_mxbuf; tmpbuf++)
  277.             if (tmpbuf->nodacs < minage && tmpbuf->nodacs)
  278.                 minage = tmpbuf->nodacs;
  279.         ct_lacs = MAXAGE - (--minage);
  280.         tmpbuf = ct_btree;
  281.         for (i = 0; i++ < ct_mxbuf; tmpbuf++)
  282.             if (tmpbuf->nodacs)
  283.                 tmpbuf->nodacs -= minage;
  284.         buffer->nodacs = ++ct_lacs;
  285.     }
  286. }
  287.  
  288.  
  289. /* --------------------------------------------------------------------
  290.    read b-tree node from the index file pointed to by knum into the
  291.    b-tree buffer. returns non-zero value if error.
  292.  */
  293.  
  294. COUNT rednod(buffer,node,knum)
  295. PFAST TREEBUFF *buffer;
  296. PFAST KEYFILE  *knum;
  297. LONG            node;
  298. {
  299.     CTFILE    *ctnum;
  300.  
  301.     VOID inracs();
  302.     COUNT uerr();
  303.  
  304. /* update buffer status information */
  305.  
  306.     buffer->nodeid = node;
  307.     buffer->keyid  = knum->filnum;
  308.     buffer->update = 'n';
  309.     buffer->klen   = knum->length;
  310.     buffer->ktipe  = knum->ktype & COL_BOTH;
  311.     buffer->lstpos = buffer->actlen = buffer->begbyt = 0;
  312.     inracs(buffer);
  313.  
  314. /* read node into buffer */
  315.  
  316.     if (knum->kmem > 0)
  317. #ifdef CTSERVER
  318.         ctnum = knum->hmem;
  319. #else
  320.         ctnum = knum - knum->kmem;
  321. #endif
  322.     else
  323.         ctnum = knum;
  324.  
  325. #ifdef CTSERVER
  326. #ifdef EXTRABFR
  327.     if(!redxnod(buffer,node,knum))
  328. #endif
  329. #endif
  330.     if (ctio(CTREAD,ctnum,node,buffer->nodorg,ctnum->recsiz))
  331.         return(uerr_cod);
  332.  
  333. /* move node status info to TREEBUFF area */
  334.  
  335.     cpybuf(&buffer->sucesr,buffer->nodorg,STATUS);
  336.  
  337. #ifdef UNIFRMAT
  338.     revbyt(&buffer->sucesr,6);
  339.     revwrd(&buffer->sucesr,2);
  340. #endif
  341.  
  342. /* check member number */
  343.  
  344.     if (buffer->bmem != knum->kmem)
  345.         terr(231);
  346.  
  347.     if (buffer->leaf == LEAF) {
  348.         buffer->maxkv = knum->maxkvl;
  349.         buffer->maxb  = knum->maxkbl;
  350.         if (knum->autodup == DUPKEY)
  351.             buffer->confg = DUPLEAF;
  352.         else
  353.             buffer->confg = REGULAR;
  354.     } else {
  355.         buffer->maxkv = knum->maxkvn;
  356.         buffer->maxb  = knum->maxkbn;
  357.         if (knum->autodup == DUPKEY)
  358.             buffer->confg = DUPNONL;
  359.         else
  360.             buffer->confg = REGULAR;
  361.     }
  362.  
  363.     return(NO_ERROR);
  364. }
  365.  
  366.  
  367. /* --------------------------------------------------------------------
  368.    return the number of entries in the index file pointed to by knum 
  369.  */
  370.  
  371. POINTER IDXENT(keyno)
  372. PFAST COUNT keyno;
  373. {
  374.     KEYFILE *tstfnm();
  375.     KEYFILE *knum;
  376. #ifdef FPUTFGET
  377.     CTFILE  *ctnum;
  378. #endif
  379.  
  380.     uerr_cod = 0;
  381.     if ((knum = tstfnm(keyno)) == NULL) /* then error condition */
  382.         return(DRNZERO);
  383.     else if (knum->clstyp == DAT_CLOSE) {
  384.         uerr_cod = FMOD_ERR;
  385.         return(DRNZERO);
  386.     }
  387.  
  388. #ifdef FPUTFGET
  389.     ctnum = knum - knum->kmem;
  390.     if ((ctnum->flmode & SHARED) &&
  391.         redhdr(knum - knum->kmem)) /* then error */
  392.         return(DRNZERO);
  393. #endif
  394.  
  395.     return(knum->nument);
  396. }
  397.  
  398.  
  399.  
  400. /* --------------------------------------------------------------------
  401.    return root node #
  402. */
  403.  
  404. LONG    gtroot(knum)
  405. PFAST KEYFILE *knum;
  406. {
  407. #ifdef FPUTFGET
  408.     CTFILE *ctnum;
  409.  
  410.     ctnum = knum - knum->kmem;
  411.     if ((ctnum->flmode & SHARED) && redhdr(knum - knum->kmem))
  412.         return(DRNZERO);
  413. #endif
  414.  
  415.     return(knum->root);
  416. }
  417.  
  418.  
  419. /* --------------------------------------------------------------------
  420.    return pointer to key value in designated position of buffer
  421.  */
  422.  
  423. TEXT *valpnt(buffer,ct_elm)
  424.  
  425. PFAST TREEBUFF *buffer;
  426. PFAST COUNT ct_elm;
  427.  
  428. {
  429. #ifdef VARLKEYS
  430.     TEXT *expval(); /* expval will determine where to put drn */
  431. #endif
  432.  
  433.     if (!buffer->ktipe) {
  434.         buffer->lstpos = ct_elm;
  435.         buffer->actlen = buffer->klen;
  436.         if (buffer->confg & REGULAR) {
  437.         buffer->actlen += sizeof(POINTER);
  438.         return(buffer->ct_kyval + (buffer->begbyt = 
  439.             (ct_elm-1) * buffer->actlen) + sizeof(POINTER));
  440.         } else
  441.         return(buffer->ct_kyval + (buffer->begbyt = (ct_elm-1) *
  442.             buffer->klen));
  443.     }
  444.  
  445. #ifdef VARLKEYS
  446.     else
  447.         return(expval(buffer,ct_elm));
  448. #else
  449.     else
  450.         terr(239);
  451. #endif
  452. }
  453.  
  454. TEXT *hghpnt(buffer)
  455. PFAST TREEBUFF *buffer;
  456. {
  457.     COUNT i;
  458.  
  459.     i = buffer->klen;
  460.  
  461. #ifdef VARLKEYS
  462.     if (buffer->ktipe & COL_PREFIX)
  463.         i++;
  464.     if (buffer->ktipe & COL_SUFFIX)
  465.         i++;
  466. #endif
  467.  
  468.     if (buffer->confg & REGULAR)
  469.         return(buffer->ct_kyval + (buffer->maxkv - 1) *
  470.             (i + sizeof(POINTER)) + sizeof(POINTER));
  471.     else
  472.         return(buffer->ct_kyval + (buffer->maxkv - 1) * i);
  473. }
  474.  
  475.  
  476. /* --------------------------------------------------------------------
  477.    return node pointer value
  478.  */
  479.  
  480. LONG    nodpnt(buffer,ct_elm)
  481.  
  482. TREEBUFF *buffer;
  483. PFAST COUNT ct_elm;
  484.  
  485. {
  486.     POINTER tp;
  487.  
  488.     if (buffer->confg == DUPLEAF)
  489.         terr(209);
  490.     cpybuf(&tp,valpnt(buffer,ct_elm) - sizeof(POINTER),sizeof(POINTER));
  491. #ifdef UNIFRMAT
  492.     revobj(&tp,sizeof(POINTER));
  493. #endif
  494.     return((LONG   ) tp);
  495. }
  496.     
  497. /* --------------------------------------------------------------------
  498.    return drn pointer value
  499.  */
  500.  
  501. #ifdef LOW_HIGH
  502.  
  503. POINTER drnpnt(buffer,ct_elm)
  504.  
  505. TREEBUFF *buffer;
  506. COUNT ct_elm;
  507.  
  508. {
  509.     FAST TEXT *tp,*pp;
  510.     FAST COUNT i;
  511.     POINTER    pntr;
  512.  
  513.     pp = (TEXT *) &pntr;
  514.     tp = valpnt(buffer,ct_elm);
  515.     if (buffer->confg & REGULAR)
  516.         cpybuf(pp,tp - sizeof(POINTER),sizeof(POINTER));
  517.     else {
  518.         tp += buffer->klen;
  519.         for (i = 0; i++ < sizeof(POINTER);)
  520.             *pp++ = *--tp;
  521.     }
  522.     return(pntr);
  523. }
  524.  
  525. #else
  526.  
  527. POINTER drnpnt(buffer,ct_elm)
  528.  
  529. PFAST TREEBUFF *buffer;
  530. PFAST COUNT     ct_elm;
  531.  
  532. {
  533.     FAST TEXT    *tp;
  534.     POINTER       pntr;
  535.  
  536.     tp = valpnt(buffer,ct_elm) - sizeof(POINTER);
  537.     if (buffer->confg == DUPLEAF)
  538.         tp += buffer->klen;
  539.     cpybuf(&pntr,tp,sizeof(POINTER));
  540. #ifdef UNIFRMAT
  541.     if (buffer->confg != DUPLEAF)
  542.         revobj(&pntr,sizeof(POINTER));    
  543. #endif
  544.     return(pntr);
  545. }
  546.  
  547. #endif
  548.  
  549. #ifdef VARLKEYS
  550.  
  551. TEXT *expval(bp,n)
  552. TREEBUFF    *bp;
  553. COUNT           n;
  554. {
  555.     COUNT      kl,kls; /* key length, - drp suffix */
  556.     COUNT       implen,colpfx,colpad,sfxcnt;
  557.     FAST TEXT *ip,*tp;
  558.     TEXT      *retval;
  559.  
  560.     if (n < 1 || n > (bp->nkv + 1))
  561.         terr(232);
  562.  
  563.     kl     = kls = bp->klen;
  564.     retval = bp->keyexp;
  565.     if (bp->confg & REGULAR) {
  566.         retval += sizeof(POINTER);
  567.         if (bp->confg == DUPNONL)
  568.             kls = kl - sizeof(POINTER);
  569.     } else
  570.         kls     = kl - sizeof(POINTER);
  571.  
  572.     if (n == bp->lstpos)
  573.         return(retval);
  574.     else
  575.         ip = bp->ct_kyval;
  576.  
  577.     colpfx = bp->ktipe & COL_PREFIX;
  578.     colpad = bp->ktipe & COL_SUFFIX;
  579.     
  580.     if (n > bp->lstpos) {
  581.         ip += (bp->begbyt + bp->actlen);
  582.         n  -= bp->lstpos;
  583.     } else
  584.         bp->lstpos = bp->actlen = bp->begbyt = 0;
  585.  
  586.     while (n > 0) {
  587.         tp = bp->keyexp;
  588.         bp->lstpos++;
  589.         n--;
  590.         bp->begbyt += bp->actlen;
  591.  
  592.         if (bp->confg & REGULAR) {
  593.             cpybuf(tp,ip,bp->actlen = sizeof(POINTER));
  594.             tp        += sizeof(POINTER);
  595.             ip        += sizeof(POINTER);
  596.         } else
  597.             bp->actlen = 0;
  598.  
  599.         implen = 0;
  600.         if (colpfx) {
  601.             bp->actlen++;
  602.             tp += (implen = (*ip++ & 0x00ff));
  603.         }
  604.         if (colpad) {
  605.             bp->actlen++;
  606.             implen += (bp->cursfx = sfxcnt = (*ip++ & 0x00ff));
  607.         } else
  608.             sfxcnt = 0;
  609.         if (implen > kls)
  610.             terr(233);
  611.  
  612.         if (implen < kls) {
  613.             bp->actlen += (implen = kls - implen);
  614.             cpybuf(tp,ip,implen);
  615.             tp += implen;
  616.             ip += implen;
  617.         }
  618.  
  619.         while (sfxcnt-- > 0)
  620.             *tp++ = PADDING;
  621.         if (kls < kl) {
  622.             cpybuf(tp,ip,sizeof(POINTER));
  623.             ip         += sizeof(POINTER);
  624.             bp->actlen += sizeof(POINTER);
  625.         }
  626.     }
  627.     return(retval);
  628. }
  629. #endif
  630.  
  631. /* end of ctkrnl.c */
  632.