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