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