home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 171.lha / BTree / BPLUS.C < prev    next >
Text File  |  1988-04-28  |  25KB  |  948 lines
  1. /********************************************************************/
  2. /*                                                                  */
  3. /*             BPLUS file indexing program - Version 1.1A           */
  4. /*                                                                  */
  5. /*                      A "shareware program"                       */
  6. /*                                                                  */
  7. /*                                                                  */
  8. /*                      Copyright (C) 1987 by                       */
  9. /*                                                                  */
  10. /*                      Hunter and Associates                       */
  11. /*                      7050 NW Zinfandel Lane                      */
  12. /*                      Corvallis, Oregon  97330                    */
  13. /*                      (503) 745 - 7186                            */
  14. /*                                                                  */
  15. /********************************************************************/
  16.  
  17.  
  18. #include <stdio.h>
  19. #include <fcntl.h>
  20. #include <io.h>
  21. #include <sys\types.h>            /*  delete this line for Turbo C  */
  22. #include <sys\stat.h>
  23. #include <string.h>
  24. #include "bplus.h"
  25.  
  26.  
  27. /*  macros, constants, data types  */
  28.  
  29. #define  NULLREC      (-1L)
  30. #define  FREE_BLOCK   (-2)
  31.  
  32. #define  ENT_ADR(pb,off)  ((ENTRY*)((char*)((pb)->entries) + off))
  33. #define  ENT_SIZE(pe)     strlen((pe)->key) + 1 + 2 * sizeof(RECPOS)
  34. #define  BUFDIRTY(j)      (mci->cache[j].dirty)
  35. #define  BUFHANDLE(j)     (mci->cache[j].handle)
  36. #define  BUFBLOCK(j)      (mci->cache[j].mb)
  37. #define  BUFCOUNT(j)      (mci->cache[j].count)
  38. #define  CB(j)            (pci->pos[j].cblock)
  39. #define  CO(j)            (pci->pos[j].coffset)
  40.  
  41.                                     /* BPLUS uses the library routine    */
  42.                                     /* memmove which must be used with   */
  43.                                     /* Turboc 1.5, Quick C and MS C 5.0  */
  44. /* #define memmove    memcpy */     /* Use this macro for Microsoft C4.0 */
  45.  
  46. /*  declare some global variables  */
  47.  
  48. IX_DESC      *pci;
  49. IX_BUFFER    bt_buffer;
  50. IX_BUFFER    *mci = &bt_buffer;
  51. BLOCK        *block_ptr;
  52. BLOCK        *spare_block;
  53. int          cache_ptr = 0;
  54. int          cache_init = 0;
  55. int          split_size = IXB_SPACE;
  56. int          comb_size  = (IXB_SPACE/2);
  57.  
  58. void pascal error(int, long);
  59. void pascal read_if(long, char *, int);
  60. void pascal write_if(int, long, char *, int);
  61. int  pascal creat_if(char *);
  62. int  pascal open_if(char *);
  63. void pascal close_if(int);
  64. void pascal update_block(void);
  65. void pascal init_cache(void);
  66. int  pascal find_cache(RECPOS);
  67. int  pascal new_cache(void);
  68. void pascal load_cache(RECPOS);
  69. void pascal get_cache(RECPOS);
  70. void pascal retrieve_block(int, RECPOS);
  71. int  pascal prev_entry(int);
  72. int  pascal next_entry(int);
  73. void pascal copy_entry(ENTRY *, ENTRY *);
  74. int  pascal scan_blk(int);
  75. int  pascal last_entry(void);
  76. void pascal write_free( RECPOS, BLOCK *);
  77. RECPOS pascal get_free(void);
  78. int  pascal find_block(ENTRY *, int *);
  79. void pascal movedown(BLOCK *, int, int);
  80. void pascal moveup(BLOCK *, int, int);
  81. void pascal ins_block(BLOCK *, ENTRY *, int);
  82. void pascal del_block(BLOCK *, int);
  83. void pascal split(int, ENTRY *, ENTRY *);
  84. void pascal ins_level(int, ENTRY *);
  85. int  pascal insert_ix(ENTRY *, IX_DESC *);
  86. int  pascal find_ix(ENTRY *, IX_DESC *, int);
  87. int  pascal combineblk(RECPOS, int);
  88. void pascal replace_entry(ENTRY *);
  89. void print_blk(BLOCK *);
  90.  
  91.  
  92. /*  file I/O for B-PLUS module  */
  93.  
  94. void pascal error(j, l)
  95.   int j;
  96.   long l;
  97.   {
  98.     static char *msg[3] = {"ERROR - CANNOT OPEN/CLOSE FILE",
  99.                            "ERROR WHILE READING FILE",
  100.                            "ERROR WHILE WRITING FILE"};
  101.     printf("\n  %s - Record Number %ld\n", msg[j], l);
  102.     exit(1);
  103.   } /* error */
  104.  
  105.  
  106. void pascal read_if(start, buf, nwrt)
  107.   long start;
  108.   char *buf;
  109.   int nwrt;
  110.   {
  111.     long err;
  112.     err = start - lseek(pci->ixfile, start, SEEK_SET);
  113.     if (err == 0) err = nwrt - read(pci->ixfile, buf, nwrt);
  114.     if (err != 0) error(1, start);
  115.   } /* read_if */
  116.  
  117.  
  118. void pascal write_if(handle, start, buf, nwrt)
  119.   int handle;
  120.   long start;
  121.   char *buf;
  122.   int nwrt;
  123.   {
  124.     long err;
  125.     err = start - lseek(handle, start, SEEK_SET);
  126.     if (err == 0) err = nwrt - write(handle, buf, nwrt);
  127.     if (err != 0) error(2, start);
  128.   } /* write_if */
  129.  
  130.  
  131. int pascal creat_if(fn)
  132.   char *fn;
  133.   {
  134.     int   ret;
  135.     ret = open(fn,O_RDWR|O_CREAT|O_TRUNC|O_BINARY,S_IWRITE);
  136.     if (ret  < 0) error(0,0L);
  137.     return (ret);
  138.   } /* creat_if */
  139.  
  140.  
  141. int pascal open_if(fn)
  142.   char *fn;
  143.   {
  144.     int  ret;
  145.     ret = open(fn,O_RDWR|O_BINARY);
  146.     if (ret < 1) error(0,0L);
  147.     return (ret);
  148.   } /* open_if */
  149.  
  150.  
  151. void pascal close_if(handle)
  152.   int handle;
  153.   {
  154.     if(close(handle) < 0)  error(2,0L);
  155.   } /*  close_if */
  156.  
  157.  
  158. int cdecl open_index(name, pix, dup)
  159.   char *name;
  160.   IX_DESC *pix;
  161.   int dup;
  162.   {
  163.     pci = pix;
  164.     pci->ixfile = open_if(name);
  165.     pci->duplicate = dup;
  166.     read_if(0L,(char *)&(pix->root), (sizeof(BLOCK) + sizeof(IX_DISK)));
  167.     if (!cache_init)
  168.       {
  169.         init_cache();
  170.         cache_init = 1;
  171.       }
  172.     first_key(pix);
  173.     return ( IX_OK );
  174.   } /* open_index */
  175.  
  176.  
  177. int cdecl close_index(pix)
  178.   IX_DESC *pix;
  179.   {
  180.     int i;
  181.     write_if(pix->ixfile, 0L,(char *)&(pix->root),
  182.                (sizeof(BLOCK) + sizeof(IX_DISK)));
  183.     for (i = 0; i < NUM_BUFS; i++)
  184.       if (BUFHANDLE(i) == pix->ixfile)
  185.         {
  186.           if (BUFDIRTY(i))
  187.             {
  188.               write_if(BUFHANDLE(i),
  189.                        BUFBLOCK(i).brec,
  190.                        (char *) &BUFBLOCK(i),
  191.                        sizeof(BLOCK));
  192.               BUFDIRTY(i) = 0;
  193.             }
  194.           BUFBLOCK(i).brec = NULLREC;
  195.       }
  196.     close_if(pix->ixfile);
  197.     return( IX_OK );
  198.   } /* close_index */
  199.  
  200.  
  201. int cdecl make_index(name, pix, dup)
  202.   char *name;
  203.   IX_DESC *pix;
  204.   int dup;
  205.   {
  206.     pci = pix;
  207.     pci->ixfile = creat_if(name);
  208.     pci->duplicate = dup;
  209.     pci->dx.nl = 1;
  210.     pci->dx.ff = NULLREC;
  211.     pci->level = 0;
  212.     CO(0) = -1;
  213.     CB(0) = 0L;
  214.     pci->root.brec = 0L;
  215.     pci->root.bend = 0;
  216.     pci->root.p0 = NULLREC;
  217.     write_if(pci->ixfile, 0L,(char *)&(pix->root),
  218.                (sizeof(BLOCK) + sizeof(IX_DISK)));
  219.     if (!cache_init)
  220.       {
  221.         init_cache();
  222.         cache_init = 1;
  223.       }
  224.     first_key(pix);
  225.     return ( IX_OK );
  226.   } /* make_index */
  227.  
  228.  
  229. /*  cache I/O for BPLUS  */
  230.  
  231. void pascal update_block()
  232.   {
  233.     if (block_ptr != &(pci->root))
  234.        BUFDIRTY(cache_ptr) = 1;
  235.   } /* update_block */
  236.  
  237.  
  238. void pascal init_cache()
  239.   {
  240.     register int  j;
  241.     for (j = 0; j < NUM_BUFS; j++)
  242.       {  BUFDIRTY(j) = 0;
  243.          BUFCOUNT(j) = 0;
  244.          BUFBLOCK(j).brec = NULLREC;
  245.       }
  246.   } /* init_cache */
  247.  
  248.  
  249. int pascal find_cache(r)
  250.   RECPOS r;
  251.   {
  252.     register int  j;
  253.     for (j = 0; j < NUM_BUFS; j++)
  254.       {
  255.         if((BUFBLOCK(j).brec == r) && (BUFHANDLE(j) == pci->ixfile))
  256.          {  cache_ptr = j;
  257.             return (1);
  258.       }  }
  259.     return (-1);
  260.   } /* find_cache */
  261.  
  262.  
  263. int pascal new_cache()
  264.   {
  265.     register int  i;
  266.     i = (cache_ptr + 1) % NUM_BUFS;
  267.     if (BUFDIRTY(i)) write_if(BUFHANDLE(i),
  268.                               BUFBLOCK(i).brec,
  269.                               (char *) &BUFBLOCK(i),
  270.                               sizeof(BLOCK));
  271.     BUFHANDLE(i) = pci->ixfile;
  272.     BUFDIRTY(i) = 0;
  273.     return (i);
  274.   } /* new_cache */
  275.  
  276.  
  277. void pascal load_cache(r)
  278.   RECPOS r;
  279.   {
  280.     cache_ptr = new_cache();
  281.     read_if(r, (char *)&BUFBLOCK(cache_ptr), sizeof(BLOCK));
  282.   } /* load_cache */
  283.  
  284.  
  285. void pascal get_cache(r)
  286.   RECPOS r;
  287.   {
  288.     if (find_cache(r) < 0)
  289.        load_cache(r);
  290.     block_ptr = &BUFBLOCK(cache_ptr);
  291.   } /* get_cache */
  292.  
  293.  
  294. void pascal retrieve_block(j, r)
  295.   int j;
  296.   RECPOS r;
  297.   {
  298.     if (j == 0)
  299.        block_ptr = &(pci->root);
  300.     else  get_cache(r);
  301.     CB(j) = block_ptr->brec;
  302.   } /* retrieve_block */
  303.  
  304.  
  305. /*  low level functions of BPLUS  */
  306.  
  307. int pascal prev_entry(off)
  308.   int off;
  309.   {
  310.      if (off <= 0)
  311.        {
  312.          off = -1;
  313.          CO(pci->level) = off;
  314.        }
  315.      else
  316.        off = scan_blk(off);
  317.      return(off);
  318.   } /* prev_entry */
  319.  
  320.  
  321. int pascal next_entry(off)
  322.   int off;
  323.   {
  324.      if (off == -1)
  325.        off = 0;
  326.      else
  327.        {
  328.          if (off < block_ptr->bend)
  329.             off += ENT_SIZE(ENT_ADR(block_ptr,off));
  330.        }
  331.      CO(pci->level) = off;
  332.      return (off);
  333.   } /* next_entry */
  334.  
  335.  
  336. void pascal copy_entry(to, from)
  337.   ENTRY *to;
  338.   ENTRY *from;
  339.   {
  340.     int me;
  341.     me = ENT_SIZE(from);
  342.     memmove(to, from, me);
  343.   } /* copy_entry */
  344.  
  345.  
  346. int pascal scan_blk(n)
  347.   int n;
  348.   {
  349.      register int off, last;
  350.      off = 0;
  351.      last = -1;
  352.      while (off < n )
  353.        {  last = off;
  354.           off += ENT_SIZE(ENT_ADR(block_ptr,off));
  355.        }
  356.      CO(pci->level) = last;
  357.      return (last);
  358.   } /* scan_blk */
  359.  
  360.  
  361. int pascal last_entry()
  362.   {
  363.      return( scan_blk(block_ptr->bend) );
  364.   } /* last_entry */
  365.  
  366.  
  367. /*  maintain list of free index blocks  */
  368.  
  369. void pascal write_free(r, pb)
  370.   RECPOS r;
  371.   BLOCK *pb;
  372.   {
  373.     pb->p0 = FREE_BLOCK;
  374.     pb->brec = pci->dx.ff;
  375.     write_if(pci->ixfile, r, (char *) pb, sizeof(BLOCK));
  376.     pci->dx.ff = r;
  377.   } /* write_free */
  378.  
  379.  
  380. RECPOS pascal get_free()
  381.   {
  382.     RECPOS  r, rt;
  383.  
  384.     r = pci->dx.ff;
  385.     if ( r != NULLREC )
  386.       {  read_if(r, (char *)&rt, sizeof( RECPOS ));
  387.          pci->dx.ff = rt;
  388.       }
  389.     else
  390.       r = filelength (pci->ixfile);
  391.     return (r);
  392.   } /* get_free */
  393.  
  394.  
  395. /*  general BPLUS block level functions  */
  396.  
  397. int pascal find_block(pe, poff)
  398.   ENTRY *pe;
  399.   int *poff;
  400.   {
  401.     register int pos, nextpos, ret;
  402.     pos = -1;
  403.     nextpos = 0;
  404.     ret = 1;
  405.     while ( nextpos < block_ptr->bend)
  406.       {
  407.         ret = strcmp((char *)(pe->key),
  408.                      (char *)(ENT_ADR(block_ptr, nextpos)->key));
  409.         if (ret <= 0)
  410.           {
  411.              if (ret == 0) pos = nextpos;
  412.              break;
  413.           }
  414.         pos = nextpos;
  415.         nextpos = next_entry(pos);
  416.       }
  417.     CO(pci->level) = pos;
  418.     *poff = pos;
  419.     return (ret);
  420.   } /* find_block */
  421.  
  422.  
  423. void pascal movedown(pb, off, n)
  424.   BLOCK *pb;
  425.   int off;
  426.   int n;
  427.   {
  428.     memmove(ENT_ADR(pb, off),
  429.            ENT_ADR(pb, off + n),
  430.            pb -> bend - (off + n));
  431.   } /* movedown */
  432.  
  433.  
  434. void pascal moveup(pb, off, n)
  435.   BLOCK *pb;
  436.   int off;
  437.   int n;
  438.   {
  439.     memmove(ENT_ADR(pb, off + n),
  440.             ENT_ADR(pb, off),
  441.             pb->bend - off);
  442.   } /* moveup */
  443.  
  444.  
  445. void pascal ins_block(pb, pe, off)
  446.   BLOCK *pb;
  447.   ENTRY *pe;
  448.   int off;
  449.   {
  450.     int size;
  451.     size = ENT_SIZE(pe);
  452.     moveup(pb,off,size);
  453.     copy_entry(ENT_ADR(pb,off),pe);
  454.     pb->bend += size;
  455.   } /* ins_block */
  456.  
  457.  
  458. void pascal del_block(pb, off)
  459.   BLOCK *pb;
  460.   int off;
  461.   {
  462.     int ne;
  463.     ne = ENT_SIZE(ENT_ADR(pb, off));
  464.     movedown(pb, off, ne);
  465.     pb->bend -= ne;
  466.   } /* del_block */
  467.  
  468.  
  469. /*  position at start/end of index  */
  470.  
  471. int cdecl first_key(pix)
  472.   IX_DESC *pix;
  473.   {
  474.     pci = pix;
  475.     block_ptr = &(pci->root);
  476.     CB(0) = 0L;
  477.     CO(0) = -1;
  478.     pci->level = 0;
  479.     while(block_ptr->p0 != NULLREC)
  480.       {
  481.         retrieve_block(++(pci->level), block_ptr->p0);
  482.         CO(pci->level) = -1;
  483.       }
  484.     return ( IX_OK );
  485.   } /* first_key */
  486.  
  487.  
  488. int cdecl last_key(pix)
  489.   IX_DESC *pix;
  490.   {
  491.     long  ads;
  492.     pci = pix;
  493.     block_ptr = &(pci->root);
  494.     CB(0) = 0L;
  495.     pci->level = 0;
  496.     if(last_entry() >= 0)
  497.       {
  498.         while ((ads = ENT_ADR(block_ptr,last_entry())->idxptr) != NULLREC)
  499.              retrieve_block(++(pci->level), ads);
  500.       }
  501.     CO(pci->level) = block_ptr->bend;
  502.     return ( IX_OK );
  503.   } /* last_key */
  504.  
  505.  
  506. /*  get next, previous entries  */
  507.  
  508. int cdecl next_key(pe, pix)
  509.   ENTRY *pe;
  510.   IX_DESC *pix;
  511.   {
  512.     RECPOS  address;
  513.     pci = pix;
  514.     retrieve_block(pci->level, CB(pci->level));
  515.     if(CO(pci->level) == -1) address = block_ptr->p0;
  516.     else
  517.      {
  518.        if (CO(pci->level) == block_ptr->bend) address = NULLREC;
  519.        else  address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  520.      }
  521.     while (address != NULLREC)
  522.       {
  523.          retrieve_block(++(pci->level), address);
  524.          CO(pci->level) = -1;
  525.          address = block_ptr->p0;
  526.       }
  527.     next_entry(CO(pci->level));
  528.     if (CO(pci->level) == block_ptr->bend)
  529.       {
  530.         do
  531.           { if(pci->level == 0)
  532.               {
  533.                 last_key(pci);
  534.                 return (EOIX);
  535.               }
  536.             --(pci->level);
  537.             retrieve_block(pci->level, CB(pci->level));
  538.             next_entry(CO(pci->level));
  539.           } while (CO(pci->level) == block_ptr->bend);
  540.       }
  541.     copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  542.     return ( IX_OK );
  543.   } /* next_key */
  544.  
  545.  
  546. int cdecl prev_key(pe, pix)
  547.   ENTRY *pe;
  548.   IX_DESC *pix;
  549.   {
  550.     RECPOS  address;
  551.     pci = pix;
  552.     retrieve_block(pci->level, CB(pci->level));
  553.     prev_entry(CO(pci->level));
  554.     if (CO(pci->level) == -1)
  555.       address = block_ptr->p0;
  556.     else
  557.       address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  558.     if (address != NULLREC)
  559.       { do
  560.           {
  561.             retrieve_block(++(pci->level), address);
  562.             address = ENT_ADR(block_ptr, last_entry())->idxptr;
  563.           } while (address != NULLREC);
  564.       }
  565.     if (CO(pci->level) == -1)
  566.       { do
  567.           {
  568.             if(pci->level == 0)
  569.               {
  570.                 first_key(pci);
  571.                 return (EOIX);
  572.               }
  573.             --(pci->level);
  574.           } while (CO(pci->level) == -1);
  575.         retrieve_block(pci->level, CB(pci->level));
  576.       }
  577.     copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  578.     return ( IX_OK );
  579.   } /* prev_key */
  580.  
  581.  
  582. /*  insert new entries into tree  */
  583.  
  584. void pascal split(l, pe, e)
  585.   int l;
  586.   ENTRY *pe;
  587.   ENTRY *e;
  588.   {
  589.     int  half, ins_pos, size;
  590.     ins_pos = CO(pci->level);
  591.     half = scan_blk(block_ptr->bend / 2 + sizeof(RECPOS));
  592.     if (half == ins_pos)
  593.       *e = *pe;
  594.     else
  595.       {
  596.          copy_entry(e, ENT_ADR(block_ptr, half));
  597.          size = ENT_SIZE(e);
  598.          movedown(block_ptr, half, size);
  599.          block_ptr->bend -= size;
  600.       }
  601.     spare_block = &BUFBLOCK(new_cache());
  602.     memmove(spare_block->entries,
  603.            ENT_ADR(block_ptr,half),
  604.            block_ptr->bend - half);
  605.     spare_block->brec = get_free();
  606.     spare_block->bend = block_ptr->bend - half;
  607.     spare_block->p0 = e->idxptr;
  608.     block_ptr->bend = half;
  609.     e->idxptr = spare_block->brec;
  610.     if (ins_pos < half)
  611.       ins_block(block_ptr,pe,ins_pos);
  612.     else if (ins_pos > half)
  613.       {
  614.          ins_pos -= ENT_SIZE(e);
  615.          ins_block(spare_block,pe,ins_pos - half);
  616.          CB(l) = e->idxptr;
  617.          CO(l) = CO(l) - half;
  618.       }
  619.     write_if(pci->ixfile, spare_block->brec,
  620.              (char *) spare_block, sizeof(BLOCK));
  621.   } /* split */
  622.  
  623.  
  624. void pascal ins_level(l, e)
  625.   int l;
  626.   ENTRY *e;
  627.   {
  628.     int  i;
  629.     if ( l < 0)
  630.       {  for (i = 1; i < MAX_LEVELS; i++)
  631.            {  CO(MAX_LEVELS - i) = CO(MAX_LEVELS - i - 1);
  632.               CB(MAX_LEVELS - i) = CB(MAX_LEVELS - i - 1);
  633.            }
  634.          memmove(spare_block, &(pci->root), sizeof(BLOCK));
  635.          spare_block->brec = get_free();
  636.          write_if(pci->ixfile, spare_block->brec,
  637.                   (char *) spare_block, sizeof(BLOCK));
  638.          pci->root.p0 = spare_block->brec;
  639.          copy_entry((ENTRY *) (pci->root.entries), e);
  640.          pci->root.bend = ENT_SIZE(e);
  641.          CO(0) = 0;
  642.          pci->level = 0;
  643.          (pci->dx.nl)++;
  644.       }
  645.     else ins_block(block_ptr,e,CO(l));
  646.   } /* ins_level */
  647.  
  648.  
  649. int pascal insert_ix(pe, pix)
  650.   ENTRY *pe;
  651.   IX_DESC *pix;
  652.   {
  653.     ENTRY    e, ee;
  654.     int h;
  655.     h = 0;
  656.     pci = pix;
  657.     ee = *pe;
  658.     do
  659.       {
  660.          if(CO(pci->level) >= 0)
  661.            CO(pci->level) +=
  662.                   ENT_SIZE(ENT_ADR(block_ptr, CO(pci->level)));
  663.          else
  664.            CO(pci->level) = 0;
  665.          update_block();
  666.          if( (block_ptr->bend + ENT_SIZE(&ee)) <= split_size)
  667.            {
  668.              ins_level(pci->level, &ee);
  669.              break;
  670.            }
  671.          else
  672.            {
  673.              h = 1;
  674.              split(pci->level,&ee, &e);
  675.               ee = e;
  676.               pci->level--;
  677.               if (pci->level < 0)
  678.                 {
  679.                   ins_level(pci->level, &e);
  680.                   break;
  681.                 }
  682.               retrieve_block(pci->level, CB(pci->level));
  683.            }
  684.       }
  685.     while (1);
  686.     if (h) find_ix(pe, pix, 0);
  687.     return ( IX_OK );
  688.   } /* insert_ix */
  689.  
  690.  
  691. /*  BPLUS find and add key functions  */
  692.  
  693. int pascal find_ix(pe, pix, find)
  694.   ENTRY *pe;
  695.   IX_DESC *pix;
  696.   int find;
  697.   {
  698.     int      level, off, ret;
  699.     RECPOS   ads;
  700.     pci = pix;
  701.     ads = 0L;
  702.     level = ret = 0;
  703.     while (ads != NULLREC)
  704.       {  pci->level = level;
  705.          retrieve_block(level, ads);
  706.          if (find_block(pe, &off) == 0) ret = 1;
  707.          if (ret && find) break;
  708.          if (off == -1)
  709.            ads = block_ptr->p0;
  710.          else
  711.            ads = ENT_ADR(block_ptr, off)->idxptr;
  712.          CO(level++) = off;
  713.        }
  714.      return ( ret );
  715.    } /* find_ix */
  716.  
  717.  
  718. int cdecl find_key(pe, pix)
  719.   ENTRY *pe;
  720.   IX_DESC *pix;
  721.   {
  722.     int ret;
  723.     ret = find_ix(pe, pix, 1);
  724.     if ( ret ) copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  725.     return ( ret );
  726.   } /* find_key */
  727.  
  728.  
  729. int cdecl add_key(pe, pix)
  730.   ENTRY *pe;
  731.   IX_DESC *pix;
  732.   {
  733.     int ret;
  734.     ret = find_ix(pe, pix, 0);
  735.     if ( ret && (pci->duplicate == 0)) return ( IX_FAIL );
  736.     pe->idxptr = NULLREC;
  737.     return (insert_ix(pe, pix));
  738.   } /* add_key */
  739.  
  740.  
  741. int cdecl locate_key(pe, pix)
  742.   ENTRY *pe;
  743.   IX_DESC *pix;
  744.   {
  745.     int ret;
  746.     ret = find_ix(pe, pix, 1);
  747.     if (ret) copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  748.     else if (next_key(pe,pix) == EOIX) ret = EOIX;
  749.     return ( ret );
  750.   } /* locate_key */
  751.  
  752.  
  753. int cdecl find_exact(pe, pix)
  754.   ENTRY *pe;
  755.   IX_DESC * pix;
  756.   {
  757.     int  ret;
  758.     ENTRY e;
  759.     copy_entry(&e, pe);
  760.     ret = find_key(&e, pix);
  761.     if ( ret && pci->duplicate)
  762.       {
  763.         do
  764.           {
  765.             ret = (e.recptr == pe->recptr);
  766.             if( !ret )  ret = next_key(&e, pci);
  767.             if (ret) ret = (strcmp(e.key, pe->key) == 0);
  768.             if ( !ret ) return ( 0 );
  769.           } while ( !ret );
  770.       }
  771.     copy_entry(pe, &e);
  772.     return ( ret );
  773.   } /* find_exact */
  774.  
  775.  
  776. /* BPLUS delete key functions */
  777.  
  778. int cdecl delete_key(pe, pix)
  779.   ENTRY *pe;
  780.   IX_DESC *pix;
  781.   {
  782.      ENTRY   e;
  783.      RECPOS  ads;
  784.      int     h, leveli, levelf;
  785.      if (!find_exact(pe, pix))  return( IX_FAIL );
  786.      h = 1;
  787.      if ((ads = pe->idxptr) != NULLREC)
  788.        {
  789.           leveli = pci->level;
  790.           do
  791.             {
  792.                retrieve_block(++(pci->level), ads);
  793.                CO(pci->level) = -1;
  794.             }
  795.           while ((ads = block_ptr->p0) != NULLREC);
  796.           CO(pci->level) = 0;
  797.           copy_entry(&e, ENT_ADR(block_ptr, CO(pci->level)));
  798.           levelf = pci->level;
  799.           pci->level = leveli;
  800.           replace_entry(&e);
  801.           pci->level = levelf;
  802.        }
  803.      while ( h )
  804.        {
  805.           retrieve_block(pci->level, CB(pci->level));
  806.           del_block(block_ptr, CO(pci->level));
  807.           update_block();
  808.           if ( (pci->level == 0) && (block_ptr->bend == 0))
  809.           /* tree was reduced in height */
  810.             {
  811.               if (pci->root.p0 != NULLREC)
  812.                 {
  813.                   retrieve_block(++pci->level, pci->root.p0);
  814.                   memmove(&(pci->root), block_ptr, sizeof(BLOCK));
  815.                   (pci->dx.nl)--;
  816.                   write_free(block_ptr->brec, block_ptr);
  817.                   BUFDIRTY(cache_ptr) = 0;
  818.                   BUFHANDLE(cache_ptr) = 0;
  819.                 }
  820.               break;
  821.             }
  822.           h = (block_ptr->bend < comb_size) && (pci->level > 0);
  823.           if ( h )
  824.               h = combineblk(CB(pci->level), block_ptr->bend);
  825.        }
  826.     find_ix(pe,pix,0);
  827.     return( IX_OK );
  828.   } /* delete_key */
  829.  
  830.  
  831. int pascal combineblk(ads, size)
  832.   RECPOS ads;
  833.   int size;
  834.   {
  835.     ENTRY  e;
  836.     RECPOS address;
  837.     int    esize, off, ret, saveoff, ibuff;
  838.     ret = 0;
  839.     saveoff = CO(--(pci->level));
  840.     retrieve_block(pci->level, CB(pci->level));
  841.     if ((off = next_entry( saveoff )) < block_ptr->bend)
  842.       /* combine with page on right */
  843.       {
  844.         if ( (ENT_SIZE(ENT_ADR(block_ptr, off)) + size) < split_size)
  845.           {
  846.             copy_entry(&e, ENT_ADR(block_ptr, off));
  847.             address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  848.             retrieve_block(++pci->level, address);
  849.             ibuff = cache_ptr;
  850.             spare_block = block_ptr;
  851.             retrieve_block(pci->level, ads);
  852.             esize = ENT_SIZE(&e);
  853.             if(((block_ptr->bend + spare_block->bend + esize) >= split_size)
  854.                  && (spare_block->bend <= block_ptr->bend + esize))
  855.                return( ret );
  856.             e.idxptr = spare_block->p0;
  857.             ins_block(block_ptr, &e, block_ptr->bend);
  858.             update_block();
  859.             if ((block_ptr->bend + spare_block->bend) < split_size)
  860.             /* combine the blocks */
  861.               {
  862.                 memmove(ENT_ADR(block_ptr, block_ptr->bend),
  863.                        ENT_ADR(spare_block, 0),
  864.                        spare_block->bend);
  865.                 block_ptr->bend += spare_block->bend;
  866.                 write_free(spare_block->brec, spare_block);
  867.                 BUFDIRTY(ibuff) = 0;
  868.                 BUFHANDLE(ibuff) = 0;
  869.                 --pci->level;
  870.                 ret = 1;
  871.               }
  872.             else
  873.             /* move an entry up to replace the one moved */
  874.               {
  875.                 copy_entry(&e, ENT_ADR(spare_block, 0));
  876.                 esize = ENT_SIZE(&e);
  877.                 movedown(spare_block, 0, esize);
  878.                 spare_block->bend -= esize;
  879.                 spare_block->p0 = e.idxptr;
  880.                 BUFDIRTY(ibuff) = 1;
  881.                 --(pci->level);
  882.                 replace_entry(&e);
  883.               }
  884.           }
  885.       }
  886.     else
  887.       /* move from page on left */
  888.       {
  889.         if ( (ENT_SIZE(ENT_ADR(block_ptr, CO(pci->level))) + size)
  890.                  < split_size)
  891.           {
  892.             copy_entry(&e, ENT_ADR(block_ptr, saveoff));
  893.             off = prev_entry(saveoff);
  894.             if (CO(pci->level) == -1) address = block_ptr->p0;
  895.             else address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  896.             retrieve_block(++pci->level, address);
  897.             off = last_entry();
  898.             ibuff = cache_ptr;
  899.             spare_block = block_ptr;
  900.             retrieve_block(pci->level, ads);
  901.             esize = ENT_SIZE(&e);
  902.             if(((block_ptr->bend + spare_block->bend + esize) >= split_size)
  903.                  && (spare_block->bend <= block_ptr->bend + esize))
  904.                return( ret );
  905.             BUFDIRTY(ibuff) = 1;
  906.             CO(pci->level) = 0;
  907.             e.idxptr = block_ptr->p0;
  908.             ins_block(block_ptr, &e, 0);
  909.             if ((block_ptr->bend + spare_block->bend) < split_size)
  910.             /* combine the blocks */
  911.               {
  912.                 memmove(ENT_ADR(spare_block, spare_block->bend),
  913.                        ENT_ADR(block_ptr, 0),
  914.                        block_ptr->bend);
  915.                 spare_block->bend += block_ptr->bend;
  916.                 write_free(block_ptr->brec, block_ptr);
  917.                 BUFDIRTY(cache_ptr) = 0;
  918.                 BUFHANDLE(cache_ptr) = 0;
  919.                 CO(--(pci->level)) = saveoff;
  920.                 ret = 1;
  921.               }
  922.             else
  923.             /* move an entry up to replace the one moved */
  924.               {
  925.                  block_ptr->p0 = ENT_ADR(spare_block,off)->idxptr;
  926.                  copy_entry(&e, ENT_ADR(spare_block, off));
  927.                  spare_block->bend = off;
  928.                  update_block();
  929.                  CO(--(pci->level)) = saveoff;
  930.                  replace_entry(&e);
  931.               }
  932.           }
  933.       }
  934.     return ( ret );
  935.   } /* combineblk */
  936.  
  937.  
  938. void pascal replace_entry(pe)
  939.   ENTRY *pe;
  940.   {
  941.     retrieve_block(pci->level, CB(pci->level));
  942.     pe->idxptr = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  943.     del_block(block_ptr, CO(pci->level));
  944.     prev_entry(CO(pci->level));
  945.     insert_ix(pe, pci);
  946.   } /* replace_entry */
  947.  
  948.