home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c004 / 1.ddi / CTDELK.C < prev    next >
Encoding:
C/C++ Source or Header  |  1989-04-18  |  10.6 KB  |  469 lines
  1. /*
  2.  *    delete key
  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 uerr(),putnod(),LOCK(),UNLOCK();
  30.  
  31. #ifndef FPUTFGET
  32. LOCAL COUNT ct_nelem[MAXLEV];
  33. COUNT ct_tight[MAXLEV];
  34. COUNT ct_melem[MAXLEV];
  35. #endif
  36.  
  37.  
  38. /* --------------------------------------------------------------------
  39.    routine to delete index entry checking that associated recbyt agrees
  40.    with recbyt
  41.  
  42.    if pointers agree, DELCHK returns a 0; if not, it returns a 3 and
  43.    no deletion is performed
  44.  
  45.    if the key value is not found, then a 4 is returned
  46.  */
  47.  
  48. COUNT DELCHK(keyno,target,recbyt)
  49.  
  50. COUNT   keyno;
  51. TEXT   *target;
  52. POINTER recbyt;
  53.  
  54. {
  55.     VOID prpdup();
  56.     COUNT DELKEY();
  57.     KEYFILE *tstfnm();
  58.  
  59.     FAST KEYFILE *knum;
  60.     TEXT *idxval;
  61.  
  62.     uerr_cod = 0;
  63.     if ((knum = tstfnm(keyno)) == NULL)
  64.         return(uerr_cod);
  65.  
  66.     cpybuf((idxval = ct_dupkey),target,knum->length);
  67.     if (knum->autodup == DUPKEY)
  68.         prpdup(idxval,knum,&recbyt);
  69.  
  70.     return(DELKEY(knum,idxval,recbyt));
  71. }
  72.     
  73. /* --------------------------------------------------------------------
  74.    routine to delete index entry "blind" (ie, without checking
  75.    associated pointer for agreement); and return the associated pointer
  76.    found in the index. cannot be used with DUPKEY.
  77.  
  78.    if error or no target is found, then return a zero
  79.  */
  80.  
  81. POINTER DELBLD(keyno,target)
  82.  
  83. COUNT keyno;
  84. TEXT *target;
  85.  
  86. {
  87.     LOCAL POINTER test;
  88.     POINTER fndkey();
  89.     COUNT DELKEY();
  90.     FAST KEYFILE *knum;
  91.     KEYFILE *tstfnm();
  92.  
  93.     uerr_cod = 0;
  94.     if ((knum = tstfnm(keyno)) == NULL)
  95.         return(0);
  96.     if (knum->autodup == DUPKEY) {
  97.         uerr(KBLD_ERR);
  98.         return(0);
  99.     }
  100.  
  101.     if (!(test = fndkey(knum,target,'E'))) {
  102.         uerr(KDEL_ERR);
  103.         return(0);
  104.     } else {
  105.         if (DELKEY(knum,target,test))
  106.             return(0);
  107.         return(test);
  108.     }
  109. }
  110.  
  111.  
  112. /* --------------------------------------------------------------------
  113.    utility routine to delete key value from leaf node.
  114.  
  115.    NOTE: THE FOLLOWING APPLIES WHEN FPUTFGET IS DEFINED IN CTOPTN.H
  116.  
  117.    To support concurrent node updates, underflowed nodes (i.e., nodes
  118.    less than half-full are not removed from the tree.  A node may even
  119.    become empty.  Such under utilized nodes will be reused when key
  120.    values from the same range of values are added back into the index.
  121.    If key values are systematically removed from one end of the index,
  122.    and replacements are added to the other end of the index; it will be
  123.    necessary to rebuild or compact the index periodically to avoid wasted
  124.    disk space. (See CTCMPC.C, the compaction utility.)
  125.  
  126.  */
  127.  
  128. COUNT DELKEY(knum,idxval,pntr)
  129. PFAST KEYFILE *knum;
  130. TEXT *idxval;
  131. POINTER pntr;
  132. {
  133.     COUNT npoint;
  134.     FAST TREEBUFF *buffer;
  135.     LONG    node;
  136.  
  137.     LONG    gtroot(),nodpnt();
  138.     POINTER drnpnt();
  139.     COUNT   nodser(),hdrupd(),tstupd();
  140.     TREEBUFF *getnod();
  141.     TREEBUFF *movrgt();
  142.     COUNT    delexp();
  143.  
  144. #ifndef FPUTFGET
  145.     LONG  pnode,snode;
  146.     COUNT cmpflg;
  147.     COUNT rtnode(),delupl(),delpbm();
  148.  
  149.     cmpflg = knum->ktype & COL_SUFFIX;
  150. #endif
  151.     uerr_cod = btlev = 0;
  152.     if (chkredf(knum))
  153.         return(uerr_cod);
  154.     if (!(node = gtroot(knum))) /* tree may be empty or gtroot err */
  155.         if (uerr_cod)
  156.             return(uerr_cod);
  157.         else
  158.             return(uerr(KDEL_ERR));
  159.  
  160.     while (node) {    /* walk down or across tree until leaf node found */
  161.         ct_lnode = node;
  162.         if ((buffer = getnod(node,knum)) == NULL)
  163.             return(uerr_cod);
  164.         if (buffer->leaf == LEAF)
  165.             break;
  166.  
  167.         if ((npoint = nodser(buffer,idxval,'L')) != -1) {
  168.             if (npoint == -2)
  169.                 terr(220);
  170. #ifndef FPUTFGET
  171.             ct_npath[++btlev] = node;
  172.             ct_nelem[btlev]   = npoint;
  173.             if (cmpflg) {
  174.                 ct_melem[btlev]   = buffer->nkv;
  175.                 ct_tight[btlev]   = (buffer->nkb + buffer->klen)
  176.                     > buffer->maxb ?  YES : NO;
  177.             }
  178. #endif
  179.             node = nodpnt(buffer,npoint);
  180.         } else
  181.             node = buffer->sucesr;
  182.     }
  183.  
  184.     if (!node)    /* then no leaf node found */
  185.         terr(221);
  186.  
  187. #ifdef FPUTFGET
  188.     if (LOCK(node,knum) ||
  189.         (buffer = movrgt(idxval,knum,getnod(node,knum))) == NULL)
  190. #else
  191.     if (LOCK(node,knum) ||
  192.         (buffer = movrgt(idxval,knum,buffer)) == NULL)
  193. #endif
  194.         return(uerr_cod);
  195.  
  196.     if (ct_tky) {
  197.         if (UNLOCK(buffer->nodeid,knum))
  198.             return(uerr_cod);
  199.         return(uerr(KDEL_ERR)); /* ct_key does not exist */
  200.     }
  201.  
  202.     if (drnpnt(buffer,ct_elm) != pntr) {
  203.         if (UNLOCK(buffer->nodeid,knum))
  204.             return(uerr_cod);
  205.         return(uerr(KMAT_ERR));
  206.     }
  207.  
  208.     if (tstupd(knum))
  209.         return(uerr_cod);
  210.         
  211.     delexp(buffer);
  212.  
  213.     node = buffer->nodeid; /* save for unlock */
  214.  
  215. #ifdef FPUTFGET
  216.     if (putnod(buffer,buffer->nkv) || UNLOCK(node,knum) ||
  217.         hdrupd(knum,(POINTER) -1))
  218.         return(uerr_cod);
  219. #else
  220.     pnode = buffer->predsr;
  221.     snode = buffer->sucesr;
  222.     if (buffer->nkv > 0 || snode == DRNZERO || (cmpflg && delpbm(btlev))) {
  223.         if (putnod(buffer,buffer->nkv) || UNLOCK(node,knum))
  224.         return(uerr_cod);
  225.     } else {
  226.         /* empty leaf node, but not last leaf */
  227.         if (btlev == 0) terr(242);
  228.         if (rtnode(node,knum) || UNLOCK(node,knum))
  229.         return(uerr_cod);
  230.         if (pnode) {
  231.         if ((buffer = getnod(pnode,knum)) == NULL)
  232.             return(uerr_cod);
  233.         buffer->sucesr = snode;
  234.         putnod(buffer,buffer->nkv);
  235.         }
  236.         if (delupl(snode,knum))
  237.         return(uerr_cod);
  238.         if ((buffer = getnod(snode,knum)) == NULL)
  239.         return(uerr_cod);
  240.         buffer->predsr = pnode;
  241.         putnod(buffer,buffer->nkv);
  242.     }
  243.     if (hdrupd(knum,(POINTER) -1))
  244.         return(uerr_cod);
  245. #endif
  246.     return(NO_ERROR);
  247. }
  248.  
  249. #ifndef FPUTFGET
  250. COUNT rtnode(node,knum)
  251. LONG         node;
  252. CTFILE         *knum;
  253. {
  254.     FAST TREEBUFF *buffer;
  255.     FAST CTFILE   *ctnum;
  256.  
  257.     TREEBUFF *getnod();
  258.  
  259.     if ((buffer = getnod(node,knum)) == NULL)
  260.         return(uerr_cod);
  261. #ifdef CTSERVER
  262.     ctnum = knum->hmem;
  263. #else
  264.     ctnum = knum - knum->kmem;
  265. #endif
  266.  
  267.     buffer->predsr = -1L;
  268.     buffer->sucesr = ctnum->delstk;
  269.     buffer->bmem   = 0;
  270.     buffer->keyid  = ctnum->filnum;
  271.     putnod(buffer,0);
  272.     ctnum->delstk   = node;
  273. #ifdef FPUTONLY
  274.     if (wrthdr(ctnum))
  275.         return(uerr_cod);
  276. #endif
  277.     return(NO_ERROR);
  278. }
  279.  
  280. static COUNT delpbm(lev)
  281. FAST COUNT lev;
  282. {
  283.     while (lev > 0) {
  284.         if (ct_tight[lev])
  285.             return(YES);
  286.         if (ct_nelem[lev] != ct_melem[lev])
  287.             break;
  288.         lev--;
  289.     }
  290.     return(NO);
  291. }
  292.  
  293. static COUNT updprd(node,knum,npoint,snode)
  294. LONG node;
  295. CTFILE *knum;
  296. COUNT npoint;
  297. LONG snode;
  298. {
  299.     TREEBUFF *getnod();
  300.     LONG      nodpnt();
  301.  
  302.     FAST TREEBUFF *buffer;
  303.     COUNT pass;
  304.  
  305.     pass  = 0;
  306.     while (btlev > 0 && npoint == 1) {
  307.         ++pass;
  308.         npoint = ct_nelem[btlev];
  309.         node  = ct_npath[btlev--];
  310.     }
  311.     btlev += pass++;
  312.  
  313.     if (npoint-- == 1)
  314.         return(NO_ERROR);
  315.  
  316.     if ((buffer = getnod(node,knum)) == NULL)
  317.         return(uerr_cod);
  318.     node = nodpnt(buffer,npoint);
  319.     while (pass-- != 0) {
  320.         if ((buffer = getnod(node,knum)) == NULL)
  321.             return(uerr_cod);
  322.         node = nodpnt(buffer,buffer->nkv);
  323.     }
  324.     buffer->sucesr = snode;
  325.     putnod(buffer,buffer->nkv);
  326.     return(NO_ERROR);
  327. }
  328.  
  329. static COUNT delupl(snode,knum)
  330. LONG            snode;
  331. CTFILE             *knum;
  332. {
  333.     LONG  node,prdnod;
  334.     COUNT npoint,lstdel,pass;
  335.     FAST TREEBUFF *buffer;
  336.     TREEBUFF      *prdbuf;
  337.     TEXT lstkey[MAXLEN];
  338.  
  339.     TREEBUFF *getnod(),*movrgt();
  340.     TEXT     *valpnt();
  341.     VOID      insexp();
  342.     COUNT      delexp();
  343.  
  344.     pass = 0;
  345.  
  346. del_loop:
  347.     if ((node = ct_npath[btlev]) == 0)
  348.         terr(241);
  349.     npoint = ct_nelem[btlev--];
  350.     if (pass++ && updprd(node,knum,npoint,snode))
  351.         return(uerr_cod);
  352.     if ((buffer = getnod(node,knum)) == NULL)
  353.         return(uerr_cod);
  354.     if (btlev == 0 && buffer->nkv < 3) {
  355.         if (npoint == 1) {
  356.             if ((knum->root = snode) == DRNZERO) terr(244);
  357.         } else
  358.             terr(243);
  359.         return(rtnode(node,knum));
  360.     }
  361.     valpnt(buffer,npoint);
  362.     lstdel = delexp(buffer); /* delexp does not handle DUPNONL ???? */
  363.     if (lstdel && npoint > 1)
  364.         cpybuf(lstkey,valpnt(buffer,npoint - 1),knum->length);
  365.     snode  = buffer->sucesr;
  366.     if (buffer->nkv == 0) {
  367.         if (rtnode(node,knum))
  368.             return(uerr_cod);
  369.         goto del_loop;
  370.     }
  371.     putnod(buffer,buffer->nkv);
  372.     /* check if last entry deleted */
  373.     /* if (!lstdel) return(NO_ERROR); */
  374.     snode = node;
  375.     while (lstdel && btlev > 0) {
  376.         if ((node = ct_npath[btlev]) == DRNZERO)
  377.             terr(245);
  378.         npoint = ct_nelem[btlev--];
  379.         if ((buffer = movrgt(lstkey,knum,getnod(node,knum))) == NULL)
  380.             return(uerr_cod);
  381.         insexp(buffer,lstkey,snode);
  382.         buffer->nkv++;
  383.         valpnt(buffer,npoint + 1);
  384.         lstdel = delexp(buffer);
  385.         if (buffer->nkb > buffer->maxb) terr(246);
  386.         putnod(buffer,buffer->nkv);
  387.         snode = node;
  388.     }
  389.  
  390.     return(NO_ERROR);
  391. }
  392. #endif
  393.  
  394. COUNT delexp(bp)
  395. PFAST TREEBUFF *bp;
  396. {
  397.     COUNT      expcnt,pfxcnt,pfxct2,sfxct2,sactlen,sbegbyt;
  398.     COUNT      colpfx,colpad,poff;
  399.     FAST TEXT *tp;
  400.  
  401.     TEXT      *valpnt();
  402.  
  403.     if (bp->lstpos == bp->nkv) {    /* deleting last entry */
  404.         bp->nkv--;
  405.         bp->nkb   -= bp->actlen;
  406.         bp->lstpos = bp->actlen = bp->begbyt = 0;
  407.         return(YES);
  408.     }
  409.  
  410.     colpfx = bp->ktipe & COL_PREFIX;
  411.     colpad = bp->ktipe & COL_SUFFIX;
  412.     tp     = bp->ct_kyval + bp->begbyt;
  413.     if (bp->confg & REGULAR)
  414.         poff = sizeof(POINTER);
  415.     else
  416.         poff = 0;
  417.  
  418. #ifdef VARLKEYS
  419.     if (colpfx) {
  420.         pfxcnt = *(tp + poff) & 0x00ff;
  421.         pfxct2 = *(tp + poff + bp->actlen) & 0x00ff;
  422.         if (colpad)
  423.             sfxct2 = *(tp + poff + bp->actlen + 1) & 0x00ff;
  424.     } else
  425.         pfxcnt = pfxct2 = 0;
  426. #else
  427.     pfxcnt = pfxct2 = 0;
  428. #endif
  429.  
  430.     sactlen = bp->actlen;
  431.     sbegbyt = bp->begbyt;
  432.     valpnt(bp,bp->lstpos + 1);
  433.  
  434.     if (pfxct2 <= pfxcnt) /* applies to no prefix case as well */
  435.         shflft(expcnt = sactlen,bp,sbegbyt+sactlen);
  436. #ifdef VARLKEYS
  437.     else { /* must expand some or all of pfxct2 bytes */
  438.         expcnt = sactlen - (pfxct2 - pfxcnt);
  439.         colpfx = 1;
  440.         if (colpad) {
  441.             *(tp + poff + 1) = sfxct2;
  442.             colpfx           = 2;
  443.         }
  444.         if (poff) {
  445.             *(tp + sactlen + poff) = pfxcnt;
  446.             cpybuf(tp,tp + sactlen,poff + colpfx);
  447.         }            
  448.         if (expcnt > 0)
  449.             shflft(expcnt,bp,sbegbyt + sactlen + poff + colpfx);
  450.         else { /* right shift required!!!! */
  451.             terr(238);
  452. /*
  453.             shfrgt(-expcnt,bp,sbegbyt + sactlen + poff + colpfx);
  454.             cpybuf(bp->ct_kyval + sbegbyt + poff + colpfx,
  455.                 bp->prvexp + poff + pfxcnt,pfxct2 - pfxcnt);
  456. */        }
  457.         bp->actlen += (pfxct2 - pfxcnt);
  458.     }
  459. #endif
  460.  
  461.     bp->nkb   -= expcnt;
  462.     bp->begbyt = sbegbyt;
  463.     bp->nkv--;
  464.     bp->lstpos--;
  465.     return(NO);
  466. }
  467.  
  468. /* end of ctdelk.c */
  469.