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