home *** CD-ROM | disk | FTP | other *** search
/ Piper's Pit BBS/FTP: ibm 0010 - 0019 / ibm0010-0019 / ibm0010.tar / ibm0010 / CODE4-1.ZIP / SOURCE.ZIP / B4.C next >
Encoding:
C/C++ Source or Header  |  1989-10-14  |  25.9 KB  |  959 lines
  1.  
  2. /*  Index File Block Routines
  3.     (c)Copyright Sequiter Software Inc., 1987, 1988, 1989.  All rights reserved. */
  4.  
  5. #include <string.h>
  6. #include <stdio.h>
  7. #ifndef UNIX
  8.    #include <io.h>
  9. #endif
  10. #include "d4base.h"
  11. #include "h4memory.h"
  12. #include "u4error.h"
  13.  
  14. extern INDEX  *v4index ;
  15. extern BLOCK  *v4block ;
  16. extern BASE   *v4base ;
  17. extern int     i4keycmp( int, char *, char * ), index_next(int) ;
  18. extern int     v4index_free, v4last_base ;
  19.  
  20. int  i4free( index_ref )
  21. int  index_ref ;
  22. {
  23.    INDEX  *index_ptr ;
  24.  
  25.    index_ptr =  v4index + index_ref ;
  26.  
  27.    /* Buffer Info. is no longer Valid */
  28.    while ( index_ptr->block_ref >= 0 )
  29.    {
  30.       if ( v4block[index_ptr->block_ref].wrt )
  31.          if ( b4write( index_ref, index_ptr->block_ref ) < 0 )  return -1 ;
  32.       index_ptr->block_ref =  h4free((char **) &v4block,index_ptr->block_ref);
  33.    }
  34.    while ( index_ptr->block_last >= 0 )
  35.    {
  36.       if ( v4block[index_ptr->block_last].wrt )
  37.      if ( b4write( index_ref, index_ptr->block_last) < 0 )  return -1 ;
  38.       index_ptr->block_last =  h4free((char **) &v4block,index_ptr->block_last);
  39.    }
  40.    index_ptr->block_first =  -1 ;
  41.    index_ptr->block_num =  0 ;
  42.  
  43.    return 0 ;
  44. }
  45.  
  46. index_next( i_ref )
  47. int  i_ref ;
  48. {
  49.    int  i_on, base_on ;
  50.  
  51.    i_on =  v4index[i_ref].prev ;
  52.    if ( i_on < 0 )
  53.    {
  54.       for ( base_on = v4base[v4index[i_ref].base_ref].prev ;;
  55.             base_on = v4base[base_on].prev)
  56.       {
  57.      if ( base_on < 0 )  base_on =  v4last_base ;
  58.  
  59.      i_on =  v4base[base_on].index_ref ;
  60.      if ( i_on >= 0 )  return( i_on ) ;
  61.       }
  62.    }
  63.  
  64.    return ( i_on ) ;
  65. }
  66.  
  67. b4get( index_ref )
  68. int  index_ref ;
  69. {
  70.    MEMORY  *mem_ptr ;
  71.    INDEX   *index_ptr ;
  72.    int      index_on, block_on ;
  73.  
  74.    mem_ptr =  (MEMORY *) v4block - 1 ;
  75.    index_ptr = v4index+ index_ref ;
  76.  
  77.    if ( mem_ptr->first_free >= mem_ptr->num_unit )
  78.    {
  79.       if ( v4index_free < 0)   v4index_free =  index_ref ;
  80.  
  81.       index_on =  v4index_free ;
  82.  
  83.       if ( v4index[index_on].block_num <= 0 )
  84.          for ( index_on = index_next(v4index_free);
  85.                v4index[index_on].block_num <= 0  && index_on != v4index_free;
  86.            index_on = index_next(index_on) )  ;
  87.  
  88.       v4index_free =  index_on ;
  89.  
  90.       if ( v4index[v4index_free].block_num > 0 )
  91.       {
  92.          /* Free saved buffer memory */
  93.      block_on =  v4index[v4index_free].block_first ;
  94.      if ( block_on < 0 )
  95.         u4error( E_INTERNAL, "b4get", (char *) 0 ) ;
  96.  
  97.      if ( v4block[block_on].wrt )  b4write( v4index_free, block_on ) ;
  98.      v4index[v4index_free].block_first = h4free( (char **) &v4block, block_on ) ;
  99.      if ( v4index[v4index_free].block_first < 0 )
  100.         v4index[v4index_free].block_last =  -1 ;
  101.      v4index[v4index_free].block_num-- ;
  102.  
  103.      if ( v4index[v4index_free].block_num < v4index[v4index_free].block_max )
  104.         v4index_free =  index_next(v4index_free) ;
  105.       }
  106.    }
  107.  
  108.    index_ptr->block_ref = h4get( (char **) &v4block, index_ptr->block_ref ) ;
  109.    if ( index_ptr->block_ref < 0 )  return -1 ;
  110.  
  111.    return( index_ptr->block_ref ) ;
  112. }
  113.  
  114.  
  115. #ifdef CLIPPER
  116.  
  117. static void b4insert(index_ref, key_ptr, position )
  118. int  index_ref ;
  119. KEY *key_ptr ;
  120. int  position ;
  121. {
  122.    BLOCK *block_ptr ;
  123.    int      swap_val ;
  124.  
  125.    block_ptr =    v4block +  v4index[index_ref].block_ref ;
  126.  
  127.    swap_val =  block_ptr->pointers[block_ptr->num_keys+1] ;
  128.    if ( swap_val+ v4index[index_ref].group_len >= BLOCK_SIZE)
  129.       u4error( E_INTERNAL, "b4insert", (char *) 0) ;
  130.  
  131.    memmove( block_ptr->pointers +  position +1,
  132.         block_ptr->pointers +  position,
  133.         (int) sizeof(int)* (block_ptr->num_keys +1 -position) ) ;
  134.    block_ptr->pointers[position] =  swap_val ;
  135.  
  136.    memmove( (char *)&block_ptr->num_keys + swap_val, (char *) key_ptr,
  137.               v4index[index_ref].group_len ) ;
  138.    block_ptr->num_keys++ ;
  139.    block_ptr->wrt =  1 ;
  140. }
  141.  
  142. /*  b4add.c
  143.  
  144.     Adds the 'key' to the current memory block.  Position of 'key_on' is
  145.     assumed to point to the key in the block just greater than the
  146.     key being added.
  147.  
  148.     Parameters
  149.  
  150.        Name        Type      Purpose
  151.  
  152.        index_ref    int       Specified the index file.
  153.        key_ptr        KEY *     A pointer to the key to be added.
  154.  
  155.  
  156.     Function Return
  157.  
  158.        0 -  Normal Return
  159.       -1 -  Error
  160. */
  161.  
  162. b4add( index_ref, key_ptr )
  163. int   index_ref ;
  164. KEY  *key_ptr    ;
  165. {
  166.    INDEX  *index_ptr ;
  167.    BLOCK  *block_ptr, *low_block_ptr ;
  168.    KEY      *save_key_ptr, *half_key_ptr ;
  169.  
  170.    char    save_key_data[MAX_KEY_SIZE+8] ;
  171.    int       i, swap_val, rc, i_half_key, insert_position, i_block, ref ;
  172.    int      *from, *to ;
  173.    long    save_file_block ;
  174.  
  175.  
  176.    index_ptr =    v4index + index_ref ;
  177.    if ( index_ptr->block_ref < 0 )  return( -1 )  ;
  178.  
  179.    block_ptr =    v4block +  index_ptr->block_ref ;
  180.  
  181.    if ( block_ptr->num_keys < index_ptr->keys_max )
  182.    {
  183.       b4insert(index_ref, key_ptr, block_ptr->key_on) ;
  184.       return 0 ;
  185.    }
  186.  
  187.    save_key_ptr =  (KEY *) save_key_data ;
  188.  
  189.    /* Create the Middle Key, Fill in the key to be added */
  190.    if ( block_ptr->key_on == index_ptr->keys_half )
  191.       memcpy( save_key_ptr, key_ptr, index_ptr->group_len ) ;
  192.    else
  193.    {
  194.       insert_position =  block_ptr->key_on ;
  195.       i_half_key =  index_ptr->keys_half ;
  196.  
  197.       if ( block_ptr->key_on < index_ptr->keys_half )
  198.      i_half_key-- ;
  199.       else
  200.      insert_position-- ;
  201.  
  202.       memcpy( save_key_ptr, ((char *)&block_ptr->num_keys) +
  203.          block_ptr->pointers[i_half_key],index_ptr->group_len);
  204.        /* Remove the Half Way Key */
  205.       block_ptr->key_on =  i_half_key ;
  206.       b4remove(index_ref) ;
  207.  
  208.       b4insert(index_ref, key_ptr, insert_position) ;
  209.    }
  210.  
  211.    /* Split the block */
  212.    if ( b4get( index_ref )  < 0 )  return -1 ;
  213.    low_block_ptr =  v4block +  index_ptr->block_ref ;
  214.    low_block_ptr->wrt =  1 ;
  215.  
  216.    /* 'block_ptr' may not be accurate because of 'b4get' call. */
  217.    block_ptr     =  v4block +  low_block_ptr->prev ;
  218.    block_ptr->wrt =  1 ;
  219.  
  220.    /* Copy old block data to new block */
  221.    memcpy( (char *)low_block_ptr + 2*sizeof(int),
  222.        (char *)block_ptr + 2*sizeof(int), sizeof(BLOCK)-2*sizeof(int));
  223.  
  224.    low_block_ptr->num_keys =  index_ptr->keys_half ;
  225.  
  226.    /* Add to the end of the file */
  227.    if ( index_ptr->eof == 0L )
  228.    {
  229.       /* Add to the End */
  230.       if ( index_ptr->virtual_eof == 0L )
  231.          index_ptr->virtual_eof =  lseek( index_ptr->dos_file, 0L, SEEK_END) ;
  232.  
  233.       low_block_ptr->file_block =  index_ptr->virtual_eof ;
  234.       index_ptr->virtual_eof +=  BLOCK_SIZE ;
  235.    }
  236.    else
  237.    {
  238.       low_block_ptr->file_block = index_ptr->eof ;
  239.  
  240.       /* Find new EOF */
  241.       lseek( index_ptr->dos_file, index_ptr->eof, 0) ;
  242.       rc =  read( index_ptr->dos_file, (char *) &index_ptr->eof,
  243.           (unsigned int) sizeof(index_ptr->eof) ) ;
  244.       if ( rc < 0 )
  245.       {
  246.      u4error( E_READ, index_ptr->name, (char *) 0 ) ;
  247.      return( -1 ) ;
  248.       }
  249.    }
  250.  
  251.    save_file_block =  save_key_ptr->file_block ;
  252.    save_key_ptr->file_block =  low_block_ptr->file_block ;
  253.  
  254.    low_block_ptr->key_on =   index_ptr->keys_half ;
  255.    half_key_ptr =   b4key(index_ref) ;
  256.    half_key_ptr->file_block =  save_file_block ;
  257.  
  258.    if (b4up( index_ref ) < 0)  u4error( E_INTERNAL, "b4add 2", (char *) 0 ) ;
  259.  
  260.    /* Modify 'block_ptr' (with the 'high' keys) */
  261.    if ( block_ptr->num_keys > index_ptr->keys_max )
  262.       u4error( E_INTERNAL, "b4add 3", (char *) 0 ) ;
  263.  
  264.    to    =  block_ptr->pointers ;
  265.    from =  to +  index_ptr->keys_half ;
  266.    for ( i= index_ptr->keys_half; i<= block_ptr->num_keys; i++ )
  267.    {
  268.       swap_val=  *to ;
  269.       *to++   =  *from ;
  270.       *from++ =   swap_val ;
  271.    }
  272.  
  273.    block_ptr->num_keys =  index_ptr->keys_half ;
  274.    if ( (rc = b4up(index_ref)) == -2 )    return -1 ;
  275.  
  276.    if ( rc >= 0)
  277.    {
  278.       /* Add the reference to the new block to the block just up */
  279.       rc = b4add( index_ref, save_key_ptr) ;
  280.       if ( rc < 0 ) return -1 ;
  281.       return 0 ;
  282.    }
  283.  
  284.    /*  We are on the root block and a recursive call will not work.
  285.        Do the following:
  286.       1.  Create a new root block
  287.       2.  Add block pointers to the new root block pointing to both
  288.           the new block and the old block.
  289.    */
  290.  
  291.    save_file_block =  block_ptr->file_block ;
  292.  
  293.    /* Get a new root block, flip the positions, and free the previous root block */
  294.    ref =  b4get( index_ref ) ;
  295.    index_ptr->block_ref =  h4remove( (char **) &v4block, ref ) ;
  296.    h4add( (char **) &v4block, index_ptr->block_ref, ref, 1 ) ;
  297.    if ( b4up(index_ref) < 0 )    u4error( E_INTERNAL, "b4add", (char *) 0 ) ;
  298.  
  299.    block_ptr =  v4block + ref ;
  300.  
  301.    i_block =  index_ptr->keys_max*2 + 4 ;
  302.    for (i=0; i<= index_ptr->keys_max; i++, i_block+= index_ptr->group_len)
  303.       block_ptr->pointers[i] =    i_block ;
  304.  
  305.    block_ptr->num_keys =  0 ;
  306.  
  307.    /* Specify New Root; Increment EOF value */
  308.    if ( index_ptr->eof == 0L )
  309.    {
  310.       if ( index_ptr->virtual_eof == 0L ) 
  311.          index_ptr->virtual_eof =  lseek( index_ptr->dos_file, 0L, SEEK_END) ;
  312.  
  313.       /* Add to the End */
  314.       index_ptr->root =  block_ptr->file_block =  index_ptr->virtual_eof ;
  315.       index_ptr->virtual_eof +=  BLOCK_SIZE ;
  316.    }
  317.    else
  318.    {
  319.       index_ptr->root =  block_ptr->file_block = index_ptr->eof ;
  320.       /* Find new EOF */
  321.       lseek( index_ptr->dos_file, index_ptr->eof, 0 ) ;
  322.       rc =  read( index_ptr->dos_file, (char *) &index_ptr->eof,
  323.           (unsigned int) sizeof(index_ptr->eof) ) ;
  324.       if ( rc < 0 )
  325.       {
  326.      u4error( E_READ, index_ptr->name, (char *) 0 ) ;
  327.      return( -1 ) ;
  328.       }
  329.    }
  330.    b4insert( index_ref, save_key_ptr, 0 ) ;
  331.    save_key_ptr->file_block =  save_file_block ;
  332.    b4insert( index_ref, save_key_ptr, 1 ) ;
  333.    block_ptr->num_keys =  1 ;
  334.    block_ptr->wrt      =  1 ;
  335.  
  336.    return 0 ;
  337. }
  338.  
  339. #else  /* dBASE */
  340.  
  341. b4add( index_ref, key_ptr )
  342. int   index_ref ;
  343. KEY  *key_ptr    ;
  344. {
  345.    INDEX  *index_ptr ;
  346.    BLOCK  *block_ptr, *new_block_ptr, *root_block_ptr ;
  347.    KEY       new_end_key ;
  348.  
  349.    char   *from, *to ;
  350.    int       num_reduce, block_on ;
  351.  
  352.    index_ptr =    v4index + index_ref ;
  353.    if ( index_ptr->block_ref < 0 )  return( -1 )  ;
  354.  
  355.    block_ptr =    v4block +  index_ptr->block_ref ;
  356.  
  357.    /* Is there room in the current block ? */
  358.    if ( block_ptr->num_keys >=    index_ptr->keys_max )
  359.    {
  360.       /* No, the block is full. */
  361.  
  362.       /* Start Creating the new block */
  363.       if ( b4get( index_ref )  < 0 )  return -1 ;
  364.       /* Warning:  Optimizing compiler likes to put 'index_ptr->block_ref'
  365.                    into a register. */
  366.       new_block_ptr =  v4block +  v4index[index_ref].block_ref ;
  367.       new_block_ptr->wrt =  1 ;
  368.  
  369.       /* 'block_ptr' may not be accurate because of 'b4get' call. */
  370.       block_ptr     =  v4block +  new_block_ptr->prev ;
  371.       block_ptr->wrt =  1 ;
  372.  
  373.       /* Copy old block data to new block */
  374.       memcpy( (char *)new_block_ptr + 2*sizeof(int),
  375.           (char *)block_ptr + 2*sizeof(int), sizeof(BLOCK)-2*sizeof(int));
  376.  
  377.       /* Reduce the old block data to 1/2 its size */
  378.       num_reduce       =  block_ptr->num_keys / 2 ;
  379.       block_ptr->num_keys -=  num_reduce ;
  380.       block_ptr->key_on   -=  num_reduce ;
  381.  
  382.       /* The old block data end key should be preserved */
  383.       to   =  (char *) &block_ptr->key ;
  384.       from =  to +  num_reduce * index_ptr->group_len ;
  385.       memmove( to, from, (int) (to+BLOCK_SIZE - from) ) ;
  386.  
  387.       /* New block data will be the rest */
  388.       new_block_ptr->num_keys -=  block_ptr->num_keys ;
  389.  
  390.       /* The new block data is added to the end */
  391.       new_block_ptr->file_block =  index_ptr->eof ;
  392.       index_ptr->eof++ ;
  393.  
  394.       /* Build a key to point to the new block;
  395.      this is the last key of the new block */
  396.       memmove( (char *) &new_end_key,
  397.           (char *) &new_block_ptr->key +
  398.               (new_block_ptr->num_keys-1) * index_ptr->group_len,
  399.           sizeof(KEY) ) ;
  400.  
  401.       new_end_key.rec_num   =  0 ;
  402.       new_end_key.file_block =    new_block_ptr->file_block ;
  403.  
  404.       /* Determine which block to add the key to */
  405.       if ( new_block_ptr->key_on <  new_block_ptr->num_keys )
  406.       {
  407.      if ( new_block_ptr->key.file_block > 0 )
  408.           new_block_ptr->num_keys -- ; /* Do not count the last block ptr */
  409.  
  410.      /* Add the key to the new block and free it */
  411.      b4add( index_ref,    key_ptr) ;
  412.      b4up( index_ref ) ;
  413.       }
  414.       else
  415.       {
  416.      if ( new_block_ptr->key.file_block > 0 )
  417.           new_block_ptr->num_keys -- ; /* Do not count the last block ptr */
  418.  
  419.      /* Free the new block */
  420.      b4up( index_ref ) ;
  421.  
  422.      /* Add the key to the old block */
  423.      b4add( index_ref,    key_ptr ) ;
  424.       }
  425.  
  426.       /* Check to see if the block is the root block */
  427.       if ( b4up( index_ref) >= 0)
  428.       {
  429.      /* Add the reference to the new block to the block just up */
  430.      b4add( index_ref, &new_end_key) ;
  431.       }
  432.       else
  433.       {
  434.      /*  We are on the root block and a recursive call will not work.
  435.          Do the following:
  436.         1.  Create a new root block
  437.         2.  Add block pointers to the root block pointing to both
  438.             the new block and the old block.
  439.      */
  440.  
  441.      /* Add a new root block */
  442.      if ( b4get( index_ref )  < 0 )  return -1 ;
  443.  
  444.      /* Flip the positions */
  445.      block_on =  index_ptr->block_ref ;
  446.      index_ptr->block_ref =  h4remove( (char **) &v4block, block_on ) ;
  447.      h4add( (char **) &v4block, index_ptr->block_ref, block_on, 1 ) ;
  448.  
  449.      root_block_ptr       =  v4block +  block_on ;
  450.      root_block_ptr->wrt  =  1 ;
  451.      block_ptr          =  v4block +  index_ptr->block_ref ;
  452.      block_ptr->wrt       =  1 ;
  453.  
  454.      /* Specify New Root; Increment EOF value */
  455.      index_ptr->root =  root_block_ptr->file_block =  index_ptr->eof++ ;
  456.      root_block_ptr->num_keys  =  1 ;
  457.  
  458.      /* Add the new key to the new root block */
  459.      memmove( (char *) &root_block_ptr->key,
  460.          (char *) &new_end_key,  index_ptr->group_len ) ;
  461.  
  462.      /* Add Pointer to the old root block */
  463.      new_end_key.file_block =  block_ptr->file_block ;
  464.      new_end_key.rec_num    =  0 ;
  465.  
  466.      memmove( (char *) &root_block_ptr->key + index_ptr->group_len,
  467.          (char *) &new_end_key,  2*sizeof(long) ) ;
  468.  
  469.      b4up( index_ref ) ;
  470.       }
  471.    }
  472.    else
  473.    {
  474.       /* There is Room in the Current Block */
  475.       block_ptr->num_keys ++ ;
  476.       block_ptr->wrt =  1 ;
  477.  
  478.       /* Make Room at Current Position */
  479.       from = (char *) b4key( index_ref ) ;
  480.       to   = from +  index_ptr->group_len ;
  481.       memmove( to, from, (int) ((char *) &block_ptr->num_keys +BLOCK_SIZE - to) ) ;
  482.  
  483.       /* Insert the Current Key */
  484.       memmove( from, (char *) key_ptr, index_ptr->group_len ) ;
  485.    }
  486.    return( 0) ;
  487. }
  488.  
  489. #endif
  490.  
  491.  
  492.  
  493. /* b4leaf.c   
  494.  
  495.    Returns TRUE iff the current block is a leaf in the B+ tree
  496. */
  497.  
  498. b4leaf( index_ref )
  499. int  index_ref ;
  500. {
  501.    BLOCK  *block_ptr ;
  502.  
  503.    #ifdef CLIPPER
  504.       KEY  *key_ptr ;
  505.       block_ptr =  v4block+  v4index[index_ref].block_ref ;
  506.       key_ptr= (KEY *) (((char *)&block_ptr->num_keys)+ block_ptr->pointers[0]);
  507.       return( key_ptr->file_block == 0L ) ;
  508.    #else
  509.       block_ptr = v4block+  v4index[index_ref].block_ref ;
  510.       return( block_ptr->key.file_block == 0L ) ;
  511.    #endif
  512. }
  513.  
  514.  
  515. /* b4down.c
  516.  
  517.    Reads the Specified Block into Memory.
  518.  
  519.    Returns
  520.        -2  error reading
  521.        -1  cannot move down
  522.       >=0  block reference number
  523.  
  524. */
  525.  
  526. b4down( index_ref, direction )
  527. int    index_ref, direction ;
  528. {
  529.    INDEX  *index_ptr  ;
  530.    BLOCK  *block_ptr  ;
  531.    long    file_block ;
  532.    int     block_on, block_new, from_disk ;
  533.    KEY      *key_ptr ;
  534.  
  535.    from_disk =  1 ;
  536.  
  537.    index_ptr =    v4index + index_ref ;
  538.    if ( index_ptr->block_ref < 0)
  539.       file_block =  index_ptr->root ;     /* read the root block */
  540.    else
  541.    {
  542.       key_ptr =  b4key(index_ref) ;
  543.       if ( key_ptr == (KEY *) 0 )  return -1 ;    /* No Records in Index File */
  544.  
  545.       file_block =  key_ptr->file_block ;
  546.       if ( file_block <= 0 )
  547.          return( -1 ) ;   /* We are on a leaf and we cannot go down further ! */
  548.    }
  549.  
  550.    /* Search for the block in memory */
  551.    for( block_on= index_ptr->block_last; block_on>= 0; block_on= block_ptr->prev)
  552.    {
  553.       block_ptr =  v4block+ block_on ;
  554.       if ( block_ptr->file_block == file_block )
  555.       {
  556.          /* Found, remove from one chain and add to another */
  557.          block_new = h4remove( (char **) &v4block, block_on);
  558.          index_ptr->block_num-- ;
  559.          if ( block_on == index_ptr->block_last )
  560.             index_ptr->block_last =  block_new ;
  561.          if ( index_ptr->block_first == block_on )
  562.             index_ptr->block_first =  block_new ;
  563.  
  564.          index_ptr->block_ref =
  565.                h4add( (char **) &v4block, index_ptr->block_ref, block_on, 0 ) ;
  566.  
  567.          from_disk =  0 ;
  568.      block_ptr =  v4block+  index_ptr->block_ref ;
  569.          break ;
  570.       } 
  571.    }
  572.  
  573.    if ( from_disk )
  574.    {
  575.       /* Was not located, allocate memory for the new block */
  576.       if ( b4get( index_ref )  < 0 )  return -3 ;
  577.       block_ptr =  v4block + index_ptr->block_ref ;
  578.  
  579.       #ifdef CLIPPER
  580.          lseek( index_ptr->dos_file, file_block, 0 ) ;
  581.          if ( read( index_ptr->dos_file, (char *) &block_ptr->num_keys, BLOCK_SIZE )
  582.           != BLOCK_SIZE )
  583.       #else
  584.          lseek( index_ptr->dos_file, (long) BLOCK_SIZE * file_block, 0 ) ;
  585.          if ( read( index_ptr->dos_file, (char *) &block_ptr->num_keys, BLOCK_SIZE )
  586.           != BLOCK_SIZE )
  587.       #endif
  588.       {
  589.          u4error( E_READ, index_ptr->name, (char *) 0 ) ;
  590.          return( -2 ) ;
  591.       }
  592.       block_ptr->file_block =  file_block ;
  593.    }
  594.  
  595.    if (direction < 0)
  596.       block_ptr->key_on  =  0 ;
  597.    else
  598.    {
  599.       block_ptr->key_on  =  block_ptr->num_keys ;
  600.       if ( b4leaf(index_ref) )
  601.      block_ptr->key_on -- ;  /* On a leaf block in the tree */
  602.    }
  603.  
  604.    return( index_ptr->block_ref ) ;
  605. }
  606.  
  607.  
  608. /*  b4key.c   
  609.  
  610.     Returns a (KEY *) pointer
  611. */
  612.  
  613. KEY * b4key( index_ref )
  614. int    index_ref ;
  615. {
  616.    INDEX *index_ptr ;
  617.    BLOCK *block_ptr ;
  618.    char  *ptr ;
  619.  
  620.    index_ptr =    v4index +  index_ref ;
  621.  
  622.    if ( index_ptr->block_ref >= 0 )
  623.    {
  624.       block_ptr =  v4block +  index_ptr->block_ref ;
  625.  
  626.       if ( block_ptr->key_on >= 0  && block_ptr->key_on <= block_ptr->num_keys)
  627.       {
  628.      #ifdef CLIPPER
  629.         ptr = ((char *) &block_ptr->num_keys) + block_ptr->pointers[block_ptr->key_on] ;
  630.      #else
  631.         ptr = ((char *) &block_ptr->key) + index_ptr->group_len*block_ptr->key_on ;
  632.      #endif
  633.      return( (KEY *) ptr ) ;
  634.       }
  635.    }
  636.    return( (KEY *) 0 ) ;
  637. }
  638.  
  639. /* b4remove.c */
  640. #ifdef CLIPPER
  641.    b4remove_blk( index_ref )
  642.    int    index_ref ;
  643.    {
  644.       INDEX *index_ptr ;
  645.       BLOCK *block_ptr ;
  646.       long  *long_ptr ;
  647.  
  648.       index_ptr =  v4index+ index_ref ;
  649.       block_ptr =  v4block+ index_ptr->block_ref ;
  650.  
  651.       long_ptr    =  (long *) &block_ptr->num_keys ;
  652.       *long_ptr =  v4index[index_ref].eof ;
  653.       v4index[index_ref].eof =    block_ptr->file_block ;
  654.  
  655.       if ( b4write( index_ref, index_ptr->block_ref) < 0 )  return -1 ;
  656.       index_ptr->block_ref = h4free((char **) &v4block, index_ptr->block_ref);
  657.  
  658.       return 0 ;
  659.    }
  660.  
  661.    b4remove( index_ref )
  662.    {
  663.       int    num_copy, old_ptr ;
  664.       int   *pointers, *from, *to ;
  665.       BLOCK *block_ptr ;
  666.       INDEX *index_ptr ;
  667.  
  668.       index_ptr =  v4index + index_ref ;
  669.       if ( index_ptr->block_ref < 0) return( -1 ) ;
  670.  
  671.       block_ptr =  v4block + index_ptr->block_ref ;
  672.       block_ptr->num_keys-- ;
  673.       block_ptr->wrt =  1 ;
  674.  
  675.       if ( block_ptr->key_on < 0  ||
  676.        block_ptr->key_on > index_ptr->keys_max  ||
  677.        block_ptr->num_keys < 0 )
  678.      u4error( E_INTERNAL, "b4remove", (char *) 0 ) ;
  679.  
  680.       pointers    =  block_ptr->pointers ;
  681.  
  682.       old_ptr    =  pointers[block_ptr->key_on] ;
  683.       num_copy    =  index_ptr->keys_max -  block_ptr->key_on ;
  684.       to    =  pointers +  block_ptr->key_on ;
  685.       from    =  to + 1 ;
  686.  
  687.       memmove( (char *) to, (char *) from, num_copy*sizeof(int) ) ;
  688.       pointers[index_ptr->keys_max] =  old_ptr ;
  689.  
  690.       if ( ((KEY *)((char *)&block_ptr->num_keys + old_ptr))->file_block == 0 )
  691.      return( block_ptr->num_keys )    ;
  692.       else
  693.      return( block_ptr->num_keys + 1 ) ;
  694.    }
  695. #else
  696.    b4remove( index_ref )
  697.    {
  698.       int    to_offset, num_copy ;
  699.       char  *to, *from ;
  700.       BLOCK *block_ptr ;
  701.       INDEX *index_ptr ;
  702.  
  703.       index_ptr =  v4index + index_ref ;
  704.       block_ptr =  v4block + index_ptr->block_ref ;
  705.       block_ptr->wrt =  1 ;
  706.  
  707.       if ( index_ptr->block_ref < 0) return( -1 ) ;
  708.  
  709.       if ( block_ptr->key_on < index_ptr->keys_max )
  710.       {
  711.      to_offset =  index_ptr->group_len*block_ptr->key_on ;
  712.      num_copy  =  508 - to_offset - index_ptr->group_len ;
  713.      to =    (char *) &block_ptr->key.file_block + to_offset ;
  714.      from = to + index_ptr->group_len ;
  715.      memmove( to, from, num_copy ) ;
  716.       }
  717.  
  718.       block_ptr->num_keys  -= 1 ;
  719.       if ( block_ptr->num_keys < 0 )  return( 0 ) ;
  720.       if ( block_ptr->key.file_block != 0 )
  721.      return( block_ptr->num_keys + 1 ) ;
  722.       else
  723.      return(  block_ptr->num_keys ) ;
  724.    }
  725. #endif
  726.  
  727. /*   b4search.c
  728.  
  729.      Locates a key string in the current block using a binary search.
  730.      Sets  key_on  in current the current block.
  731.  
  732.      Returns
  733.  
  734.     Function Return
  735.        0  -  Complete Match
  736.        1  -  Inexact  Match
  737.        2  -  After the specified key
  738.        3  -  After the Block
  739. */
  740.  
  741. b4search( index_ref, search_string )
  742. int   index_ref ;
  743. char *search_string ;
  744. {
  745.    INDEX  *index_ptr  ;
  746.    BLOCK  *block_ptr  ;
  747.    KEY      *key_ptr    ;
  748.    int       search_len, key_len, key_lower, key_upper, key_on, rc ;
  749.  
  750.    #ifndef CLIPPER
  751.       int  group_len ;
  752.    #endif
  753.  
  754.    index_ptr =    v4index+ index_ref ;
  755.  
  756.    /* Make sure a block exists !! */
  757.    if ( index_ptr->block_ref < 0 )
  758.    {
  759.       /* Read the Top Block */
  760.       if ( b4down( index_ref, -1 ) < 0)  return( -1) ;
  761.    }
  762.    block_ptr =    v4block +  index_ptr->block_ref ;
  763.  
  764.  
  765.    /* Prepare for the search */
  766.  
  767.    key_len    =  index_ptr->key_len   ;
  768.  
  769.    #ifdef CLIPPER
  770.       search_len =  strlen( search_string ) ;
  771.       if ( search_len > key_len )  search_len =  key_len ;
  772.    #else
  773.       /* For character searches, we can have a partial search */
  774.       if ( index_ptr->int_or_date )
  775.      search_len =  key_len ;
  776.       else
  777.       {
  778.      search_len =  strlen( search_string ) ;
  779.      if ( search_len > key_len )  search_len =  key_len ;
  780.       }
  781.       group_len = index_ptr->group_len ;
  782.    #endif
  783.  
  784.    /* key_on must be between  key_lower and  key_upper */
  785.    key_lower = -1 ;
  786.    key_upper =    block_ptr->num_keys ;
  787.  
  788.    if ( key_upper == 0 )
  789.    {
  790.       block_ptr->key_on  =  block_ptr->num_keys ;
  791.       return( 3 ) ;
  792.    }
  793.  
  794.    /*  Repeat until the key is found in the block */
  795.  
  796.    while( 1)
  797.    {
  798.       key_on  =  (key_upper + key_lower) / 2  ;
  799.       #ifdef CLIPPER
  800.      key_ptr =  (KEY *) (((char *)&block_ptr->num_keys) + block_ptr->pointers[key_on] ) ;
  801.      rc     =  memcmp( search_string, key_ptr->value, search_len ) ;
  802.       #else
  803.      key_ptr =  (KEY *) (((char *)&block_ptr->key) + key_on * group_len) ;
  804.      if ( index_ptr->int_or_date )
  805.         rc     =  i4keycmp( index_ref, search_string, key_ptr->value ) ;
  806.      else
  807.         rc     =  memcmp( search_string, key_ptr->value, search_len ) ;
  808.       #endif
  809.  
  810.       if ( rc == 0 )
  811.       {
  812.      if ( key_on <= key_lower+1 )
  813.      {
  814.         block_ptr->key_on  =  key_on ;
  815.         if ( key_len == search_len )
  816.          return( 0) ;  /* Complete Match */
  817.         else
  818.          return( 1) ;  /* Partial Match */
  819.      }
  820.  
  821.      /* Perhaps there is Another Match (we want the first match) */
  822.      key_upper =  key_on + 1 ;
  823.      continue ;
  824.       }
  825.       else
  826.       {
  827.      if ( rc < 0 )
  828.         key_upper =  key_on ;
  829.      else
  830.         key_lower =  key_on ;
  831.       }
  832.  
  833.       if ( key_lower >= (key_upper-1) )
  834.       {
  835.      /*  There is no Exact Match */
  836.      if ( key_lower >=  block_ptr->num_keys -1 )
  837.      {
  838.         block_ptr->key_on =  block_ptr->num_keys ;
  839.         return( 3 ) ;
  840.      }
  841.  
  842.      /* Located inside the block */
  843.      block_ptr->key_on =  key_upper ;
  844.      return( 2) ;
  845.       }
  846.    }
  847. }
  848.  
  849. /* b4skip.c    
  850.  
  851.    Skips keys in the  current block memory unit of the specified index file.
  852. */
  853.  
  854. long  b4skip( index_ref, n )
  855. int    index_ref ;
  856. long    n ;
  857. {
  858.    INDEX  *index_ptr ;
  859.    BLOCK  *block_ptr ;
  860.    long   num_left ;
  861.  
  862.    index_ptr =    v4index + index_ref ;
  863.    if ( index_ptr->block_ref < 0 ) return( -n ) ;
  864.  
  865.    block_ptr =    v4block + index_ptr->block_ref ;
  866.  
  867.    if ( n > 0 )
  868.    {
  869.       num_left = (long) (block_ptr->num_keys - block_ptr->key_on) ;
  870.       if ( b4leaf(index_ref) )
  871.      if ( num_left != 0 )
  872.         num_left -- ;
  873.    }
  874.    else
  875.       num_left =  (long) -block_ptr->key_on ;
  876.  
  877.    if ( ( n <= 0 ) ?  (num_left <= n)  :  (num_left >= n)  )
  878.    {
  879.       block_ptr->key_on += (int) n ;
  880.       return( n ) ;
  881.    }
  882.    else
  883.    {
  884.       block_ptr->key_on += (int) num_left ;
  885.       return( num_left ) ;
  886.    }
  887. }
  888.  
  889.  
  890. /* b4up.c   
  891.  
  892.    Frees the Current Block.
  893.  
  894.    Returns
  895.        -2  nothing on list
  896.        -1  on root block already
  897.       >=0  block reference number
  898.  
  899. */
  900.  
  901. b4up( index_ref )
  902. int   index_ref ;
  903. {
  904.    INDEX  *index_ptr  ;
  905.    int  block_ref ;
  906.  
  907.    index_ptr =    v4index + index_ref ;
  908.  
  909.    if ( index_ptr->block_ref < 0)
  910.       return( -2 ) ;
  911.  
  912.    if ( v4block[ index_ptr->block_ref].prev < 0 )
  913.       return( -1 ) ;
  914.  
  915.    block_ref =  index_ptr->block_ref ;
  916.    index_ptr->block_ref =  h4remove( (char **) &v4block, block_ref ) ;
  917.    index_ptr->block_last=  h4add( (char **) &v4block, index_ptr->block_last, block_ref, 0) ;
  918.    if ( index_ptr->block_first < 0 )
  919.          index_ptr->block_first = index_ptr->block_last ;
  920.    index_ptr->block_num++ ;
  921.  
  922.    return( index_ptr->block_ref ) ;
  923. }
  924.  
  925.  
  926. /* b4write.c   
  927.  
  928.    Writes the current block memory unit of the specified index file.
  929. */
  930.  
  931. b4write( index_ref, block_ref )
  932. int     index_ref, block_ref ;
  933. {
  934.    INDEX  *index_ptr ;
  935.    BLOCK  *block_ptr ;
  936.    int       rc ;
  937.  
  938.    index_ptr =    v4index + index_ref ;
  939.    block_ptr =    v4block + block_ref ;
  940.    block_ptr->wrt =  0 ;
  941.  
  942.    #ifdef CLIPPER
  943.       lseek( index_ptr->dos_file, (long) block_ptr->file_block, 0 ) ;
  944.       rc = write( index_ptr->dos_file, (char *) &block_ptr->num_keys, BLOCK_SIZE) ;
  945.    #else
  946.       lseek( index_ptr->dos_file, (long)BLOCK_SIZE* block_ptr->file_block, 0);
  947.       rc = write( index_ptr->dos_file, (char *) &block_ptr->num_keys, BLOCK_SIZE);
  948.    #endif
  949.    if ( rc != BLOCK_SIZE )
  950.    {
  951.       u4error( E_WRITE, index_ptr->name, (char *) 0 ) ;
  952.       return( -1 ) ;
  953.    }
  954.  
  955.    return( 0) ;
  956. }
  957.  
  958.  
  959.