home *** CD-ROM | disk | FTP | other *** search
/ Garbo / Garbo.cdr / pc / c / bplus11a.arc / bplus.c next >
Encoding:
C/C++ Source or Header  |  1989-02-22  |  25.3 KB  |  1,034 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.     int MSCbug;                 /* attempt to bypass bug in Microsoft C */
  555.     
  556.     pci = pix;
  557.     retrieve_block(pci->level, CB(pci->level));
  558.     if(CO(pci->level) == -1) address = block_ptr->p0;
  559.     else {
  560.         MSCbug = CO(pci->level);
  561.         address = ENT_ADR(block_ptr, MSCbug)->idxptr;
  562.     }
  563.     while (address != NULLREC)
  564.       {
  565.          retrieve_block(++(pci->level), address);
  566.          CO(pci->level) = -1;
  567.          address = block_ptr->p0;
  568.       }
  569.     next_entry(CO(pci->level));
  570.     if (CO(pci->level) == block_ptr->bend)
  571.       {
  572.         do
  573.           { if(pci->level == 0)
  574.               {
  575.                 last_key(pci);
  576.                 return (EOIX);
  577.               }
  578.             --(pci->level);
  579.             retrieve_block(pci->level, CB(pci->level));
  580.             next_entry(CO(pci->level));
  581.           } while (CO(pci->level) == block_ptr->bend);
  582.       }
  583.     copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  584.     return ( IX_OK );
  585.   } /* next_key */
  586.  
  587.  
  588. int cdecl 
  589. prev_key(pe, pix)
  590.   ENTRY *pe;
  591.   IX_DESC *pix;
  592.   {
  593.     RECPOS  address;
  594.     int MSCbug;                 /* get around bug in Microsoft C */
  595.     
  596.     pci = pix;
  597.     retrieve_block(pci->level, CB(pci->level));
  598.     prev_entry(CO(pci->level));
  599.     if (CO(pci->level) == -1)
  600.       address = block_ptr->p0;
  601.     else {
  602.       MSCbug = CO(pci->level);
  603.       address = ENT_ADR(block_ptr, MSCbug)->idxptr;
  604.     }
  605.     if (address != NULLREC)
  606.       { do
  607.           {
  608.             retrieve_block(++(pci->level), address);
  609.             address = ENT_ADR(block_ptr, last_entry())->idxptr;
  610.           } while (address != NULLREC);
  611.       }
  612.     if (CO(pci->level) == -1)
  613.       { do
  614.           {
  615.             if(pci->level == 0)
  616.               {
  617.                 first_key(pci);
  618.                 return (EOIX);
  619.               }
  620.             --(pci->level);
  621.           } while (CO(pci->level) == -1);
  622.         retrieve_block(pci->level, CB(pci->level));
  623.       }
  624.     copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  625.     return ( IX_OK );
  626.   } /* prev_key */
  627.  
  628.  
  629. /*  insert new entries into tree  */
  630.  
  631. static void pascal 
  632. split(l, pe, e)
  633.   int l;
  634.   ENTRY *pe;
  635.   ENTRY *e;
  636.   {
  637.     int  half, ins_pos, size;
  638.     ins_pos = CO(pci->level);
  639.     half = scan_blk(block_ptr->bend / 2 + sizeof(RECPOS));
  640.     if (half == ins_pos)
  641.       *e = *pe;
  642.     else
  643.       {
  644.          copy_entry(e, ENT_ADR(block_ptr, half));
  645.          size = ENT_SIZE(e);
  646.          movedown(block_ptr, half, size);
  647.          block_ptr->bend -= size;
  648.       }
  649.     spare_block = &BUFBLOCK(new_cache());
  650.     memcpy(spare_block->entries,
  651.            ENT_ADR(block_ptr,half),
  652.            block_ptr->bend - half);
  653.     spare_block->brec = get_free();
  654.     spare_block->bend = block_ptr->bend - half;
  655.     spare_block->p0 = e->idxptr;
  656.     block_ptr->bend = half;
  657.     e->idxptr = spare_block->brec;
  658.     if (ins_pos < half)
  659.       ins_block(block_ptr,pe,ins_pos);
  660.     else if (ins_pos > half)
  661.       {
  662.          ins_pos -= ENT_SIZE(e);
  663.          ins_block(spare_block,pe,ins_pos - half);
  664.          CB(l) = e->idxptr;
  665.          CO(l) = CO(l) - half;
  666.       }
  667.     write_if(pci->ixfile, spare_block->brec,
  668.              (char *) spare_block, sizeof(BLOCK));
  669.   } /* split */
  670.  
  671.  
  672. static void pascal 
  673. ins_level(l, e)
  674.   int l;
  675.   ENTRY *e;
  676.   {
  677.     int  i;
  678.     if ( l < 0)
  679.       {  for (i = 1; i < MAX_LEVELS; i++)
  680.            {  CO(MAX_LEVELS - i) = CO(MAX_LEVELS - i - 1);
  681.               CB(MAX_LEVELS - i) = CB(MAX_LEVELS - i - 1);
  682.            }
  683.          memcpy(spare_block, &(pci->root), sizeof(BLOCK));
  684.          spare_block->brec = get_free();
  685.          write_if(pci->ixfile, spare_block->brec,
  686.                   (char *) spare_block, sizeof(BLOCK));
  687.          pci->root.p0 = spare_block->brec;
  688.          copy_entry((ENTRY *) (pci->root.entries), e);
  689.          pci->root.bend = ENT_SIZE(e);
  690.          CO(0) = 0;
  691.          pci->level = 0;
  692.          (pci->dx.nl)++;
  693.       }
  694.     else ins_block(block_ptr,e,CO(l));
  695.   } /* ins_level */
  696.  
  697.  
  698. static int pascal 
  699. insert_ix(pe, pix)
  700.   ENTRY *pe;
  701.   IX_DESC *pix;
  702.   {
  703.     ENTRY    e, ee;
  704.     int h;
  705.     h = 0;
  706.     pci = pix;
  707.     ee = *pe;
  708.     do
  709.       {
  710.          if(CO(pci->level) >= 0)
  711.            CO(pci->level) +=
  712.                   ENT_SIZE(ENT_ADR(block_ptr, CO(pci->level)));
  713.          else
  714.            CO(pci->level) = 0;
  715.          update_block();
  716.          if( (block_ptr->bend + ENT_SIZE(&ee)) <= split_size)
  717.            {
  718.              ins_level(pci->level, &ee);
  719.              break;
  720.            }
  721.          else
  722.            {
  723.              h = 1;
  724.              split(pci->level,&ee, &e);
  725.               ee = e;
  726.               pci->level--;
  727.               if (pci->level < 0)
  728.                 {
  729.                   ins_level(pci->level, &e);
  730.                   break;
  731.                 }
  732.               retrieve_block(pci->level, CB(pci->level));
  733.            }
  734.       }
  735.     while (1);
  736.     if (h) find_ix(pe, pix, 0);
  737.     return ( IX_OK );
  738.   } /* insert_ix */
  739.  
  740.  
  741. /*  BPLUS find and add key functions  */
  742.  
  743. static int pascal 
  744. find_ix(pe, pix, find)
  745.   ENTRY *pe;
  746.   IX_DESC *pix;
  747.   int find;
  748.   {
  749.     int      level, off, ret;
  750.     RECPOS   ads;
  751.     ENTRY    found;
  752.     pci = pix;
  753.     ads = 0L;
  754.     level = ret = 0;
  755.     while (ads != NULLREC)
  756.       {  pci->level = level;
  757.          retrieve_block(level, ads);
  758.          if (find_block(pe, &off) == 0) ret = 1;
  759.          if (ret && find) break;
  760.          if (off == -1)
  761.            ads = block_ptr->p0;
  762.          else
  763.            ads = ENT_ADR(block_ptr, off)->idxptr;
  764.          CO(level++) = off;
  765.        }
  766.      return ( ret );
  767.    } /* find_ix */
  768.  
  769.  
  770. int cdecl 
  771. find_key(pe, pix)
  772.   ENTRY *pe;
  773.   IX_DESC *pix;
  774.   {
  775.     int ret;
  776.     ret = find_ix(pe, pix, 1);
  777.     if ( ret ) copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  778.     return ( ret );
  779.   } /* find_key */
  780.  
  781.  
  782. int cdecl 
  783. add_key(pe, pix)
  784.   ENTRY *pe;
  785.   IX_DESC *pix;
  786.   {
  787.     int ret;
  788.     ret = find_ix(pe, pix, 0);
  789.     if ( ret && (pci->duplicate == 0)) return ( IX_FAIL );
  790.     pe->idxptr = NULLREC;
  791.     return (insert_ix(pe, pix));
  792.   } /* add_key */
  793.  
  794.  
  795. int cdecl 
  796. locate_key(pe, pix)
  797.   ENTRY *pe;
  798.   IX_DESC *pix;
  799.   {
  800.     int ret;
  801.     ENTRY e;
  802.     ret = find_ix(pe, pix, 1);
  803.     if (ret) copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  804.     else if (next_key(pe,pix) == EOIX) ret = EOIX;
  805.     return ( ret );
  806.   } /* locate_key */
  807.  
  808.  
  809. int cdecl 
  810. find_exact(pe, pix)
  811.   ENTRY *pe;
  812.   IX_DESC * pix;
  813.   {
  814.     int  ret;
  815.     ENTRY e;
  816.     copy_entry(&e, pe);
  817.     ret = find_key(&e, pix);
  818.     if ( ret && pci->duplicate)
  819.       {
  820.         do
  821.           {
  822.             ret = (e.recptr == pe->recptr);
  823.             if( !ret )  ret = next_key(&e, pci);
  824.             if (ret) ret = (strcmp(e.key, pe->key) == 0);
  825.             if ( !ret ) return ( 0 );
  826.           } while ( !ret );
  827.       }
  828.     copy_entry(pe, &e);
  829.     return ( ret );
  830.   } /* find_exact */
  831.  
  832.  
  833. /* BPLUS delete key functions */
  834.  
  835. int cdecl 
  836. delete_key(pe, pix)
  837.   ENTRY *pe;
  838.   IX_DESC *pix;
  839.   {
  840.      ENTRY   e;
  841.      RECPOS  ads;
  842.      int     h, leveli, levelf;
  843.      if (!find_exact(pe, pix))  return( IX_FAIL );
  844.      h = 1;
  845.      if ((ads = pe->idxptr) != NULLREC)
  846.        {
  847.           leveli = pci->level;
  848.           do
  849.             {
  850.                retrieve_block(++(pci->level), ads);
  851.                CO(pci->level) = -1;
  852.             }
  853.           while ((ads = block_ptr->p0) != NULLREC);
  854.           CO(pci->level) = 0;
  855.           copy_entry(&e, ENT_ADR(block_ptr, CO(pci->level)));
  856.           levelf = pci->level;
  857.           pci->level = leveli;
  858.           replace_entry(&e);
  859.           pci->level = levelf;
  860.        }
  861.      while ( h )
  862.        {
  863.           retrieve_block(pci->level, CB(pci->level));
  864.           del_block(block_ptr, CO(pci->level));
  865.           update_block();
  866.           if ( (pci->level == 0) && (block_ptr->bend == 0))
  867.           /* tree was reduced in height */
  868.             {
  869.               if (pci->root.p0 != NULLREC)
  870.                 {
  871.                   retrieve_block(++pci->level, pci->root.p0);
  872.                   memcpy(&(pci->root), block_ptr, sizeof(BLOCK));
  873.                   (pci->dx.nl)--;
  874.                   write_free(block_ptr->brec, block_ptr);
  875.                   BUFDIRTY(cache_ptr) = 0;
  876.                   BUFHANDLE(cache_ptr) = 0;
  877.                 }
  878.               break;
  879.             }
  880.           h = (block_ptr->bend < comb_size) && (pci->level > 0);
  881.           if ( h )
  882.               h = combineblk(CB(pci->level), block_ptr->bend);
  883.        }
  884.     find_ix(pe,pix,0);
  885.     return( IX_OK );
  886.   } /* delete_key */
  887.  
  888.  
  889. static int pascal 
  890. combineblk(ads, size)
  891.   RECPOS ads;
  892.   int size;
  893.   {
  894.     ENTRY  e;
  895.     RECPOS address;
  896.     int MSCbug;                 /* fix bug in Microsoft C */
  897.     int    esize, off, ret, saveoff, ibuff;
  898.     
  899.     ret = 0;
  900.     saveoff = CO(--(pci->level));
  901.     retrieve_block(pci->level, CB(pci->level));
  902.     if ((off = next_entry( saveoff )) < block_ptr->bend)
  903.       /* combine with page on right */
  904.       {
  905.         if ( (ENT_SIZE(ENT_ADR(block_ptr, off)) + size) < split_size)
  906.           {
  907.             copy_entry(&e, ENT_ADR(block_ptr, off));
  908.             MSCbug =CO(pci->level);
  909.             address = ENT_ADR(block_ptr, MSCbug)->idxptr;
  910.             retrieve_block(++pci->level, address);
  911.             ibuff = cache_ptr;
  912.             spare_block = block_ptr;
  913.             retrieve_block(pci->level, ads);
  914.             esize = ENT_SIZE(&e);
  915.             if(((block_ptr->bend + spare_block->bend + esize) >= split_size)
  916.                  && (spare_block->bend <= block_ptr->bend + esize))
  917.                return( ret );
  918.             e.idxptr = spare_block->p0;
  919.             ins_block(block_ptr, &e, block_ptr->bend);
  920.             update_block();
  921.             if ((block_ptr->bend + spare_block->bend) < split_size)
  922.             /* combine the blocks */
  923.               {
  924.                 memcpy(ENT_ADR(block_ptr, block_ptr->bend),
  925.                        ENT_ADR(spare_block, 0),
  926.                        spare_block->bend);
  927.                 block_ptr->bend += spare_block->bend;
  928.                 write_free(spare_block->brec, spare_block);
  929.                 BUFDIRTY(ibuff) = 0;
  930.                 BUFHANDLE(ibuff) = 0;
  931.                 --pci->level;
  932.                 ret = 1;
  933.               }
  934.             else
  935.             /* move an entry up to replace the one moved */
  936.               {
  937.                 copy_entry(&e, ENT_ADR(spare_block, 0));
  938.                 esize = ENT_SIZE(&e);
  939.                 movedown(spare_block, 0, esize);
  940.                 spare_block->bend -= esize;
  941.                 spare_block->p0 = e.idxptr;
  942.                 BUFDIRTY(ibuff) = 1;
  943.                 --(pci->level);
  944.                 replace_entry(&e);
  945.               }
  946.           }
  947.       }
  948.     else
  949.       /* move from page on left */
  950.       {
  951.         if ( (ENT_SIZE(ENT_ADR(block_ptr, CO(pci->level))) + size)
  952.                  < split_size)
  953.           {
  954.             copy_entry(&e, ENT_ADR(block_ptr, saveoff));
  955.             off = prev_entry(saveoff);
  956.             if (CO(pci->level) == -1) address = block_ptr->p0;
  957.             else {
  958.               MSCbug = CO(pci->level);
  959.               address = ENT_ADR(block_ptr, MSCbug)->idxptr;
  960.             }
  961.             retrieve_block(++pci->level, address);
  962.             off = last_entry();
  963.             ibuff = cache_ptr;
  964.             spare_block = block_ptr;
  965.             retrieve_block(pci->level, ads);
  966.             esize = ENT_SIZE(&e);
  967.             if(((block_ptr->bend + spare_block->bend + esize) >= split_size)
  968.                  && (spare_block->bend <= block_ptr->bend + esize))
  969.                return( ret );
  970.             BUFDIRTY(ibuff) = 1;
  971.             CO(pci->level) = 0;
  972.             e.idxptr = block_ptr->p0;
  973.             ins_block(block_ptr, &e, 0);
  974.             if ((block_ptr->bend + spare_block->bend) < split_size)
  975.             /* combine the blocks */
  976.               {
  977.                 memcpy(ENT_ADR(spare_block, spare_block->bend),
  978.                        ENT_ADR(block_ptr, 0),
  979.                        block_ptr->bend);
  980.                 spare_block->bend += block_ptr->bend;
  981.                 write_free(block_ptr->brec, block_ptr);
  982.                 BUFDIRTY(cache_ptr) = 0;
  983.                 BUFHANDLE(cache_ptr) = 0;
  984.                 CO(--(pci->level)) = saveoff;
  985.                 ret = 1;
  986.               }
  987.             else
  988.             /* move an entry up to replace the one moved */
  989.               {
  990.                  block_ptr->p0 = ENT_ADR(spare_block,off)->idxptr;
  991.                  copy_entry(&e, ENT_ADR(spare_block, off));
  992.                  spare_block->bend = off;
  993.                  update_block();
  994.                  CO(--(pci->level)) = saveoff;
  995.                  replace_entry(&e);
  996.               }
  997.           }
  998.       }
  999.     return ( ret );
  1000.   } /* combineblk */
  1001.  
  1002.  
  1003. static void pascal 
  1004. replace_entry(pe)
  1005.   ENTRY *pe;
  1006.   {
  1007.     int MSCbug;                 /* fix bug in Microsoft C */
  1008.     retrieve_block(pci->level, CB(pci->level));
  1009.     MSCbug = CO(pci->level);
  1010.     pe->idxptr = ENT_ADR(block_ptr, MSCbug)->idxptr;
  1011.     del_block(block_ptr, CO(pci->level));
  1012.     prev_entry(CO(pci->level));
  1013.     insert_ix(pe, pci);
  1014.   } /* replace_entry */
  1015.  
  1016. /*****************************************************************
  1017.  |  clearkey - set a database key to zero before using
  1018.  |----------------------------------------------------------------
  1019.  |  Arguments:
  1020.  |   1) address of the ENTRY
  1021.  |  Returns: none
  1022.  ****************************************************************/
  1023.  
  1024. void
  1025. clearkey(eptr)
  1026. ENTRY *eptr;
  1027. {
  1028.     register char *cptr;
  1029.     register int n;
  1030.  
  1031.     for (n = MAXKEY, cptr = eptr->key; n--; )
  1032.         *(cptr++) = 0;
  1033. }
  1034.