#include "stdio.h"
#include "setjmp.h"
#include "isamstr.h"
#include "isam.h"

 /* checked good 6-7-84 */

 /***************************************************************
 *                      File ISAM2.C                            *
 *      these are the function return type declarations         *
 ***************************************************************/

extern  long    l3alloc(), l2alloc();
extern  char    *calpl2(), *calpl3();
extern  int     keycmp();

extern  void    l3split();
extern  void    grread(), fmove(), lmove(), l2write();
extern  void    l2read(), l3write(), l3read(), wl2write(), wl2read();
extern  void    wl3write();
extern  void    keymove();
extern  M_ELEM  mbinsh();
extern  L2_ELEM l2binsh();
extern  L3_ELEM l3binsh();

static  int     _dir;

 /***************************************************************
 *      match                                                   *
 *         finds first key >= current key or returns eof        *
 *            returns:                                          *
 *               -1 on eof (all keys less than)                 *
 *               0 on found equal                               *
 *               1 on found only greater                        *
 ***************************************************************/

int    match(key)
char   *key;
{
   char *upper, *lower;

   _dir = 0;

   /* check if empty index, if so return end-of-file */

   if(!cm_ent)
       return(EOF);

   /* set upper and lower bounds for mbinsh() */

   upper = calpl2(cm_ent - 1, bm_ptr);
   lower = (char *)bm_ptr;

   /* see if at end-of-file and return EOF if true */

   if(keycmp(((M_ELEM)upper)->key, key) > 0){
       keymove(lp_key, ((M_ELEM)upper)->key);
       return(EOF);
   }

   /* position cama with mbinsh() */

   cama = mbinsh(upper, lower, key);

   /* group read l2 block */

   l2read(l2_group = cama->offset);

   /* while lowlink and key < lowkey read lowlink */

   while(lowlink)
       if(keycmp(lowkey, key) <= 0) {
           l2read(lowlink);
           _dir = -1;
       } else
           break;

   /* while highlink and key > highest element key read highlink */

   while(highlink)
       if(keycmp(((L2_ELEM)calpl2(l2_ent - 1, bl2_ptr))->key,
           key) > 0) {
           l2read(highlink);
           _dir = 1;
       } else
           break;

   /* set upper and lower bounds for l2binsh() */

   upper = calpl2(l2_ent - 1, bl2_ptr);
   lower = (char *)bl2_ptr;

   /* set cal2 from l2binsh() */

   cal2 = l2binsh(upper, lower, key);

   /* read l3 block */

   l3read(cal2->offset);

   /* set cal3 from l3binsh() */

   upper = calpl3(cal2->group - 1, bl3_ptr);
   cal3 = l3binsh(upper, bl3_ptr, key);

   /* move key to lp_key and return keycmp status */

   keymove(lp_key, cal3->l3key);
   return(keycmp(key, cal3->l3key));   /* must return >= 0 (not eof) */
}
/* 
 ****************************************************************
 *      read next gets next key after current position.         *
 *      returns -1 for eof, or next record position.            *
 ***************************************************************/

long   readnext()
{

   /* check if not at top of current l3 block */

   if((char *)cal3 < calpl3(cal2->group - 1, bl3_ptr)) {
       /* if true then increment cal3 to next l3 element */
       cal3 = (L3_ELEM)calpl3(1, cal3);

   } else {
       /* at top of current l3 block */
       /* check if top of current l2 block */
       if((char *)cal2 < calpl2(l2_ent - 1, bl2_ptr))
           /* if not increment cal2 to next l2 element */
           cal2 = (L2_ELEM)calpl2(1, cal2);
       else {
           /* top of l2 and l3 blocks */
           /* check for highlink */

           if(highlink) {
               /* if highlink read it */
               l2read(highlink);
           } else {
               /* no highlink */
               /* check if top of main */
               if((char *)cama < calpl2(cm_ent - 1, bm_ptr)) {
                   /* not at top of main. up cama to next
                      main element */
                   cama = (M_ELEM)calpl2(1, cama);
                   grread(cama->offset);
                   /* go to lowest link of new l2 */
                   while(lowlink) {
                       l2read(lowlink);
                   }
               } else {    /* top of main, return EOF */
                   return(EOF);
               }
       }
           /* l2 and l3 full. set cal2 to start of new block */
           cal2 = bl2_ptr;
       }

       /* l3 full, set cal3 to start of new block */
       l3read(cal2->offset);
       cal3 = bl3_ptr;
   }
   /* return data offset */
   return(cal3->offset);
}
/* 
 ****************************************************************
 *      splits an l3 block into an l2 block if necessary        *
 ***************************************************************/

void   l3split(key)
char   *key;
{
   char    *start, *end, *mid;
   unsigned    len;

   /* if end-of-file up cal2 to next element */

   if(_eof)
       cal2 = (L2_ELEM)calpl2(1, cal2);
   else {
       /* if not eof then one element is inserted into the
          l2 block with overflow */

       start = calpl2(l2_ent, bl2_ptr) - 1;
       end = start + l2elem;
       len = start - (char *)cal2 + 1;
       lmove(start, end, len);
   }

   /* if beginning-of-file or end-of-file */

   if(_bof || _eof) {
       /* write current l3 block, and generate new empty l3 block */

       l3write(l3_cur);
       cal2->offset = l3alloc();
       cal2->group = 0;
       keymove(cal2->key, key);
       cal3 = bl3_ptr;
   } else {

       /* split the l3 block and leave the correct half in
          memory with cal2 and cal3 properly adjusted */

       mid = calpl3((l3_max) / 2, bl3_ptr);
       fmove(mid, wbl3_ptr, calpl3(l3_max, bl3_ptr) - mid);
       keymove(cal2->key, ((L3_ELEM)(mid - l3elem))->l3key);
       cal2->group = (l3_max) / 2;
       ((L2_ELEM)calpl2(1, cal2))->group -= cal2->group;
       cal2->offset = ((L2_ELEM)calpl2(1, cal2))->offset;
       ((L2_ELEM)calpl2(1, cal2))->offset = l3alloc();
       if((char *)cal3 < mid)
           wl3write(((L2_ELEM)calpl2(1, cal2))->offset);
       else {
           l3_drty = TRUE;
           l3write(cal2->offset);
           cal2 = (L2_ELEM)calpl2(1, cal2);
           fmove(wbl3_ptr, bl3_ptr, cal2->group * l3elem);
           cal3 = (L3_ELEM)((char *)bl3_ptr +
               ((char *)cal3 - mid));
       }
   }

   /* adjust administrative data */

   l3_cur = cal2->offset;
   l2_ent++;
   l2_drty = TRUE;
}
/* 
 ****************************************************************
 *      side splits to the high side an l2 block                *
 ***************************************************************/

void   highsplit(key)
char   *key;
{

   char    *start, *end;
   unsigned    len;
   long    l2_hold;

   /* mark l2 dirty */

   l2_drty = TRUE;

   /* if eof or bof */

   if(_eof || _bof) {
       /* check if eof */
       if(_eof) {
           /* if eof create an empty highlink */

           highlink = l2alloc();
           l2write(l2_cur);
           lowlink = l2_cur;
           l2_cur = highlink;
           highlink = 0;
           keymove(cama->key, key);
           keymove(lowkey, ((L2_ELEM)
               calpl2(l2_ent - 1, bl2_ptr))->key);
       } else {
           /* if bof create an empty lowlink */

           lowlink = l2alloc();
           keymove(lowkey, key);
           l2write(l2_cur);
           highlink = l2_cur;
           l2_cur = lowlink;
           lowlink = 0;
       }

       /* eof or bof, adjust pointers and create a new l3 block */

       cal2 = bl2_ptr;
       l3write(l3_cur);
       l3_cur = cal2->offset = l3alloc();
       keymove(cal2->key, key);
       cal2->group = 0;
       l2_ent = 1;
       cal3 = bl3_ptr;
       l2_drty = TRUE;
   } else {

       /* not eof or bof */
       /* split the l2 block, and keep the correct half in
          memory with all pointers adjusted */

       start = calpl2(l2_max / 2, bl2_ptr);
       end = (char *)wbl2_ptr;
       len = ((l2_max + 1) / 2) * l2elem;
       fmove(start, end, len);
       l2_ent = l2_max / 2;
       wl2_ent = l2_max - l2_ent;
       wl2_highlink = highlink;
       l2_hold = highlink = l2alloc();
       wl2_lowlink = l2_cur;
       keymove(wl2_lowkey, ((L2_ELEM)
           calpl2(l2_ent - 1, bl2_ptr))->key);
       if((char *)cal2 >= start) {
           l2write(l2_cur);
           l2_cur = highlink;
           cal2 = (L2_ELEM)calpl2(-l2_ent, cal2);
           fmove(ws_ptr, l2s_ptr, l2bytes);
       } else
           wl2write(highlink);
       if(wl2_highlink)
           lswrite(wl2_highlink, &l2_hold, sizeof(long));

       /* split the l3 block after room is made */

       l3split(key);   /* no overflow */
   }

   /* these are alternate methods of doing the same test

    *  if((cama ->group & 1) ? !_bof : _bof {

    *  if(_bof ? !(cama->group & 1) : (cama->group & 1)) {

   */

   /* adjust centering: maintain cama->group to the high side
      of center (even) or center (odd) of a group of l2 blocks */

   if((_bof || (_dir < 0)) ^ (cama->group & 1)) {
       l2_hold = l2_cur;
       l2read(cama->offset);
       l2_group = cama->offset = (_bof || (_dir < 0)) ? lowlink
           : highlink;
       l2read(l2_hold);
   }

   /* up l2 block count */

   cama->group++;
}