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