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

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

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

extern  void    l3split(), highsplit(), adjust();
extern  void    grread(), maininsert(), fmove(), lmove(), l2write();
extern  void    l2read(), l3read(), wl2write(), wl2read();
extern  void    keymove();

 /***************************************************************
 *      insert(key, recpos)                                     *
 *              inserts new key into index                      *
 *              returns offset or error = -1                    *
 *              errno elsewhere                                 *
 ***************************************************************/

long    insert(key, recpos)
long    recpos;
char    *key;
{

   int     i;
   char    *start, *end, *mid;
   unsigned len;

   /* set error recovery point */

   if(i_errno = setjmp(_ienv))
       return(_lm1);

   /* check to see if index is empty and process as special case */

   if(!cm_ent) {
       cama = bm_ptr;
       keymove(cama->key, key);
       l2_group = l2_cur = cama->offset = l2alloc();
       cama->group = 1;
       cm_ent++;
       cal2 = bl2_ptr;
       keymove(cal2->key, key);
       l3_cur = cal2->offset = l3alloc();
       l2_ent = 1;
       cal2->group = 1;
       cal3 = bl3_ptr;
       keymove(cal3->l3key, key);
       m_drty = l2_drty = l3_drty = TRUE;
       keymove(lp_key, key);
       lowlink = highlink = 0;
       return(cal3->offset = recpos == _lm1 ? dalloc() : recpos);
   }   /* end of if(!cm_ent) */

   /* if index is not empty, locate key position in index by
      calling match(). if the exact key is found (i == 0) and
      no dups are allowed, return error code DUPKEY */

   if((i = match(key)) == 0 && (NODUP)) {
       i_errno = DUPKEY;
       return(_lm1);
   }   /* end of if((i = match */

   /* if match returns end-of-file, set _eof to TRUE and set
      index to end-of-file */

   if(_eof = i < 0)
       set_eof();

   /* _bof is set TRUE if at beginning-of-file */

   _bof = cal3 == bl3_ptr && cal2 == bl2_ptr && cama == bm_ptr &&
       !lowlink;

   /* if current l3 block is full */

   if(cal2->group == l3_max) {

       /* l3 block is full, check if l2 block not full */

       if(l2_ent != l2_max) {

           /* l3 block full, l2 block not full, check if bottom
              of l3 block and not bottom of l2 block and next
              lower l3 is not full */

           if((cal3 == bl3_ptr) && (cal2 != bl2_ptr) &&
               (((L2_ELEM)calpl2(-1, cal2))->group < l3_max)) {

               /* l3 block full, l2 block not full, bottom of current l3 block
                  and not at bottom of l2 block and next lower l3 block not
                  full, insert current key at top of next lower l3 block
                  and adjust key in next lower l2 element and cal2 and cal3 */

               cal2 = (L2_ELEM)calpl2(-1, cal2);
               l3read(cal2->offset);
               keymove(cal2->key, key);
               cal3 = (L3_ELEM)calpl3(cal2->group, bl3_ptr);
           } else {    /* else for if ((cal3 == bl3 */

               /* l3 block full, l2 block not full, but cannot insert at
                  top of next lower l3 block. current l3 block is split */

               l3split(key);   /* l2 insert */

               /* if at eof then main's key must be adjusted */

               if(_eof)
                   keymove(cama->key, key);
           } /* end of if((cal3 == bl3 */

       } else {    /* else for if(l2_ent != l2_max */

           /* l3 block full, l2 block full */

           /* if highlink then read highlink */

           if(highlink)
               wl2read(highlink);

           /* check if highlink and it is not full */

           if(highlink && wl2_ent < l2_max) {

               /* highlink not full, split l3 block and move overflow l2
                  element into lowest element of highlink. adjust cal2,
                  cal3 and highlink's lowkey, leaving the proper l2 and
                  l3 blocks in memory */

               l3split(key);   /* with overflow */

               /* working l3 and working l2 blocks are a union in
                  memory; therefore, a reread of highlink is needed */

               wl2read(highlink);
               l2_ent--;
               start = calpl2(wl2_ent, wbl2_ptr) - 1;
               end = start + l2elem;
               len = start + 1 - (char *)wbl2_ptr;
               lmove(start, end, len);
               fmove(calpl2(l2_max, bl2_ptr), wbl2_ptr,
                   l2elem);
               wl2_ent++;
               keymove(wl2_lowkey, ((L2_ELEM)
                   calpl2(l2_ent - 1, bl2_ptr))->key);
               wl2_lowlink = l2_cur;

               /* determine if current added key in highlink or current l2 */

               if((char*)cal2 == calpl2(l2_max, bl2_ptr)) {
                   l2write(l2_cur);
                   l2_cur = highlink;
                   fmove(ws_ptr, l2s_ptr, l2bytes);
                       cal2 = bl2_ptr;
               } else { /* else for if(cal2 == calp */
                   wl2write(highlink);
               } /* end of if(cal2 == calp */

           } else { /* else for if (highlink && l2_ent */

               /* either no highlink or highlink is full */

               /* if lowlink */
               if(lowlink) {
                   wl2read(lowlink);

                   /* if lowlink not full */
                   if(wl2_ent < l2_max) {

                       /* split l3 block moving lowest l2 element to
                          highest lowlink element and slide current
                          l2 down one element (overflow becomes highest
                          current l2 element). adjust all keys and set
                          cal2 and cal3 correctly. */

                       l3split(key);   /* with overflow */

                       /* if at eof adjust cama->key */
                       if(_eof)
                           keymove(cama->key, key);
                       wl2read(lowlink);
                       fmove(bl2_ptr, calpl2(wl2_ent,
                           wbl2_ptr), l2elem);
                       keymove(lowkey, bl2_ptr->key);
                       wl2_ent++;
                       l2_ent--;
                       start = calpl2(1, bl2_ptr);
                       end = (char *)bl2_ptr;
                       len = l2_max * l2elem;
                       fmove(start, end, len);

                       /* keep correct l2 and l3 blocks */

                       if(cal2 == bl2_ptr) {
                           l2write(l2_cur);
                           l2_cur = lowlink;
                           fmove(ws_ptr, l2s_ptr,
                               l2bytes);
                           cal2 = (L2_ELEM)calpl2(
                               l2_ent - 1,
                           bl2_ptr);
                       } else { /* else if(cal2 == bl2 */
                           wl2write(lowlink);
                           cal2 = (L2_ELEM)calpl2(
                               -1, cal2);
                       }
                   } else { /* else for if(wl2_ent */

                       /* no highlink or highlink full and lowlink is full */
                       /* split to highlink side and do side link adjusts */

                       highsplit(key);
                       adjust();
                   } /* end of if(wl2_ent */

               } else { /* else of if(lowlink) */

                   /* no highlink or highlink full and no lowlink */

                   /* if highlink is full and no lowlink */

                   if(highlink) {

                       /* split l2 and adjust side links */

                       highsplit(key);
                       adjust();

                   } else {    /* else of if(highlink) */
                       /* no highlink or lowlink */
                       /* check if main is full */

                       if(cm_ent == m_max) {
                           /* main is full with no side links on current l2 */
                           /* split l2 with no adjust */

                           highsplit(key);

                       } else { /* else of if(cm_ent == m_max */
                           /* main is not full and no side links */
                           /* check if at beginning of file or end of file */

                           if(_bof || _eof) {

                               /* add a new l3 and l2 at correct end */

                               l2write(l2_cur);
                               l3write(l3_cur);
                               l3_cur = l3alloc();
                               l2_cur = l2alloc();
                               cal3 = bl3_ptr;
                               cal2 = bl2_ptr;
                               cal2->group = 0;
                               cal2->offset = l3_cur;
                               keymove(cal2->key,key);
                               highlink = lowlink = 0;
                               l2_ent = 1;

                               /* add to end of file or beginning */

                               if (_eof)
                                   cama = (M_ELEM)calpl2(1,cama);
                               else
                                   maininsert();

                               l2_group = cama->offset = l2_cur;
                               keymove(cama->key,key);
                               cama->group = 1;

                           } else { /* else of if(_bof || _eof */
                               /* main is not full and not eof or bof */
                               /* split l2 and l3 and insert into main */

                               l3split(key);   /* with overflow */
                               mid = calpl2((l2_max + 1) / 2, bl2_ptr);
                               fmove(mid, wbl2_ptr,
                                   calpl2(l2_max + 1, bl2_ptr) - mid );
                               wl2_ent = l2_ent - ((l2_max + 1) / 2);
                               l2_ent = (l2_max + 1) / 2;
                               wl2_highlink = wl2_lowlink = 0;
                               maininsert();
                               ((M_ELEM)calpl2(1, cama))->offset =
                                   l2alloc();
                               cama->group = 1;
                               cama->offset = l2_cur;
                               keymove(cama->key, ((L2_ELEM)
                                   calpl2(l2_ent - 1, bl2_ptr))->key);
                               if((char *)cal2 >= mid) {
                                   l2write(l2_cur);
                                   cama = (M_ELEM)calpl2(1, cama);
                                   l2_group = l2_cur = cama->offset;
                                   fmove(ws_ptr, l2s_ptr, l2bytes);
                                   cal2 = (L2_ELEM)(((char *)cal2 - mid)
                                       + (char *)bl2_ptr);
                               } else /* else for if (cal2 >= mid */
                                   wl2write(((M_ELEM)calpl2(1, cama))
                                       ->offset);

                           } /* end of if(_bof || _eof */

                           /* increase main element entries by added entry */

                           cm_ent++;

                       } /* end of if(cm_ent == m_max */
                   } /* end of if(highlink */
               } /* end of if(lowlink) */
           } /* end of if(highlink && */
       } /* end of if(l_ent != l2_max */

   } else /* else of if(cal2->group == l3_max (indent correct) */

   /* l3 block was not full */

   if(_eof) {

       /* if at eof then point to empty l3 pointer and adjust main
          and l2 keys */

       cal3 = (L3_ELEM)calpl3(1, cal3);
       keymove(cal2->key, key);
       keymove(cama->key, key);
   }   /* end of if(_eof) */
   /* end of if(cal2-> group */

   /* this code is always used to insert the l3 element into the
      setup empty slot. (cal3) only an empty index or illegal dup
      condition will not reach this code */

   /* check if current l3 is not empty and not at end-of-file */

   if(cal2->group && !_eof) {
       /* make room for an l3 element at cal3 */

       start = calpl3(cal2->group, bl3_ptr) - 1;
       end = start + l3elem;
       len = start - (char *)cal3 + 1;
       lmove(start, end, len);

   }   /* end of if(cal2 -> group */

   keymove(cal3->l3key, key);      /* move key to l3 */
   cal2->group++;                  /* up l3 group */
   m_drty = l2_drty = l3_drty = TRUE;  /* mark buffers dirty */
   keymove(lp_key, key);           /* move key into lp_key */

   /* set cal3->offset and return it based upon recpos. if recpos
      is equal to minus one, a new data allocation is used, otherwise
      the allocation passed is used (swa) */

   return(cal3->offset = recpos == _lm1 ? dalloc() : recpos);

}