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