siosup.c

牛顿插值方法求解多项式的系数

/*
 * (c) Copyright 1992, 1993 by Panagiotis Tsirigotis
 * All rights reserved.  The file named COPYRIGHT specifies the terms 
 * and conditions for redistribution.
 */


#include "config.h"
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdlib.h>
#include <unistd.h>
#include <syslog.h>

#ifdef _APPLE_
#undef HAVE_MMAP
#endif

#include "impl.h"
#include "sio.h"

int __sio_n_descriptors = 0 ;
__sio_descriptor_t *__sio_descriptors = NULL ;

static sio_status_e setup_read_buffer( __sio_id_t *idp, unsigned buf_size );

#ifndef MAP_FAILED
#define MAP_FAILED ((void *)-1)
#endif

/*
 * Code for finalization
 */
#ifdef HAVE_FINALIZATION_FUNCTION
static int finalizer_installed ;

SIO_DEFINE_FIN( sio_cleanup )
{
   (void) Sflush( SIO_FLUSH_ALL ) ;
}
#endif /* HAVE_FINALIZATION_FUNCTION */



#ifdef HAVE_MMAP

#define CHAR_NULL            ((char *)0)

/*
 * PAGES_MAPPED gives the size of each map unit in pages
 */
#define PAGES_MAPPED            2

static size_t map_unit_size = 0 ;         /* bytes */
static size_t page_size = 0 ;               /* bytes */

static mapd_s *mmap_descriptors = NULL ;

#define MDP( fd )            ( mmap_descriptors + (fd) )


/*
 * NOTES ON MEMORY MAPPING:
 *
 *    1. Memory mapping works only for file descriptors opened for input
 *   2. Mapping an object to a part of the address space where another
 *   object is mapped will cause the old mapping to disappear (i.e. mmap
 *   will not fail)
 *
 * Memory mapping interface:
 *      SIO_MMAP : maps a file into a portion of the address space.
 *      SIO_MUNMAP: unmap a portion of the address space
 *      SIO_MNEED: indicate to the OS that we will need a portion of
 *                   our address space.
 *
 * The map_unit_size variable defines how much of the file is mapped at
 * a time. It is a multiple of the operating system page size. It is
 * not less than SIO_BUFFER_SIZE unless SIO_BUFFER_SIZE is not a
 * multiple of the page size (so the SIO_BUFFER_SIZE overrides
 * PAGES_MAPPED).
 *
 * NOTE: All memory mapping code is in this file only
 */


/*
 * Macros used by the memory mapping code
 */
#define FIRST_TIME( dp )      ( dp->buf == NULL )

/*
 * Functions to support memory mapping:
 *
 *         try_memory_mapping
 *         buffer_setup
 *         __sio_switch
 *         initial_map
 *         map_unit
 */

/*
 * try_memory_mapping attempts to setup the specified descriptor
 * for memory mapping. 
 * It returns FAILURE if it fails and SUCCESS if it is successful.
 * If HAVE_MMAP is not defined, the function is defined to be FAILURE.
 *
 * Sets fields:
 *      memory_mapped:          TRUE or FALSE
 *      
 * Also sets the following fields if memory_mapped is TRUE:
 *    file_offset, file_size, buffer_size
 *
 */
static sio_status_e try_memory_mapping( int fd, __sio_id_t *idp, const struct stat *stp )
{
   int access_f ;

   /*
    * Do not try memory mapping if:
    *      1) The file is not a regular file
    *      2) The file is a regular file but has zero-length
    *      3) The file pointer is not positioned at the beginning of the file
    *      4) The fcntl to obtain the file descriptor flags fails
    *      5) The access mode is not O_RDONLY or O_RDWR
    *
    * The operations are done in this order to avoid the system calls
    * if possible.
    */
   if ( ( ( stp->st_mode & S_IFMT ) != S_IFREG ) ||
        ( stp->st_size == 0 ) ||
        ( lseek( fd, (long)0, 1 ) != 0 ) ||
        ( ( access_f = fcntl( fd, F_GETFL, 0 ) ) == -1 ) ||
        ( ( access_f &= 0x3 ) != O_RDONLY && access_f != O_RDWR ) )
   {
      idp->memory_mapped = FALSE ;
      return( FAILURE ) ;
   }

   /*
    * Determine page_size and map_unit_size.
    * Note that the code works even if PAGES_MAPPED is 0.
    */
   if ( page_size == 0 )
   {
      page_size = getpagesize() ;
      map_unit_size = page_size * PAGES_MAPPED ;
      if ( map_unit_size < SIO_BUFFER_SIZE )
      {
         if ( map_unit_size != 0 && SIO_BUFFER_SIZE % map_unit_size == 0 )
            map_unit_size = SIO_BUFFER_SIZE ;
         else
            map_unit_size = page_size ;
      }
   }
   
   MDP(fd)->file_offset = 0 ;
   MDP(fd)->file_size = stp->st_size ;
   idp->buffer_size = map_unit_size ;
   idp->buf = CHAR_NULL ;
   idp->memory_mapped = TRUE ;

   return( SUCCESS ) ;
}


/*
 * Copy the current_unit to the primary buffer
 *
 * Sets fields: start, end, nextb
 * Also sets the file pointer
 */
static void buffer_setup( __sio_id_t *idp, int fd, const struct map_unit *mu_cur, const struct map_unit *mu_next )
{
   off_t new_offset ;

   sio_memcopy( mu_cur->addr, idp->buf, mu_cur->valid_bytes ) ;
   idp->start = idp->buf ;
   idp->end = idp->buf + mu_cur->valid_bytes ;
   idp->nextb = idp->buf + ( idp->nextb - mu_cur->addr ) ;

   if ( mu_next->addr != CHAR_NULL )
      new_offset = MDP(fd)->file_offset - mu_next->valid_bytes ;
   else
      new_offset = MDP(fd)->file_offset ;
   (void) lseek( fd, new_offset, 0 ) ;
}

/*
 * Switch from memory mapping to buffered I/O
 * If any mapping has occurred, then the current unit is
 * copied into the buffer that is allocated.
 * Any data in the next unit is ignored.
 * We rely on idp->buf to identify the current unit (so it
 * better be equal to the address of one of the units).
 *
 * Sets fields:
 *         start, end, nextb
 */
sio_status_e __sio_switch( __sio_id_t *idp, int fd )
{
   mapd_s *mdp = MDP( fd ) ;
   struct map_unit *mu_cur, *mu_next ;
   unsigned buffer_size = idp->buffer_size ;
   char *buf_addr = idp->buf ;
   int first_time = FIRST_TIME( idp ) ;

   /*
    * Initialize stream for buffering
    */
   if ( setup_read_buffer( idp, buffer_size ) == FAILURE )
      return( FAILURE ) ;

   if ( ! first_time )
   {
      /*
       * Find current, next unit
       */
      if ( buf_addr == mdp->first_unit.addr )
      {
         mu_cur = &mdp->first_unit ;
         mu_next = &mdp->second_unit ;
      }
      else
      {
         mu_cur = &mdp->second_unit ;
         mu_next = &mdp->first_unit ;
      }

      buffer_setup( idp, fd, mu_cur, mu_next ) ;
      /*
       * Destroy all mappings
       */
      (void) SIO_MUNMAP( mu_cur->addr, mu_cur->mapped_bytes ) ;
      if ( mu_next->addr != NULL )
         (void) SIO_MUNMAP( mu_next->addr, mu_next->mapped_bytes ) ;
   }
   else
      idp->start = idp->end = idp->nextb = idp->buf ;

   idp->memory_mapped = FALSE ;
   return( SUCCESS ) ;
}


/*
 * initial_map does the first memory map on the file descriptor.
 * It attempts to map both units.
 * The mapping always starts at file offset 0.
 *
 * SETS FIELDS:
 *         first_unit.*, second_unit.*
 *         file_offset
 *
 * Returns: 
 *         number of bytes mapped in first_unit
 *    or
 *         0 to indicate that mmap failed.
 */
static int initial_map( mapd_s *mdp, int fd )
{
   caddr_t addr ;
   size_t requested_length = 2 * map_unit_size ;
   size_t mapped_length = MIN( (size_t)mdp->file_size, requested_length ) ;
   size_t bytes_left ;
   size_t bytes_in_unit ;

   addr = SIO_MMAP( CHAR_NULL, mapped_length, fd, 0 ) ;
   if ( addr == MAP_FAILED )
      return( 0 ) ;

   SIO_MNEED( addr, mapped_length ) ;

   /*
    * Map as much as possible in the first unit
    */
   bytes_in_unit = MIN( mapped_length, map_unit_size ) ;
   mdp->first_unit.addr          = addr ;
   mdp->first_unit.mapped_bytes    = bytes_in_unit ;
   mdp->first_unit.valid_bytes    = bytes_in_unit ;

   /*
    * If there is more, map it in the second unit.
    */
   bytes_left = mapped_length - bytes_in_unit ;
   if ( bytes_left != 0 )
   {
      mdp->second_unit.addr          = addr + bytes_in_unit ;
      mdp->second_unit.mapped_bytes = bytes_left ;
      mdp->second_unit.valid_bytes    = bytes_left ;
   }
   else
      mdp->second_unit.addr          = CHAR_NULL ;

   mdp->file_offset = mapped_length ;

   return( mdp->first_unit.valid_bytes ) ;
}


/*
 * ALGORITHM:
 *
 *      if ( there are more bytes in the file )
 *      {
 *         map them at the given unit
 *         update offset
 *         issue SIO_MNEED()
 *      }
 *      else
 *         unmap the unit
 */
static sio_status_e map_unit( mapd_s *mdp, int fd, struct map_unit *mup )
{
   size_t bytes_left = mdp->file_size - mdp->file_offset ;
   size_t bytes_to_map = MIN( bytes_left, map_unit_size ) ;

   if ( bytes_to_map != 0 )
   {
      if ( SIO_MMAP( mup->addr, bytes_to_map,
                                             fd, mdp->file_offset ) == MAP_FAILED )
         return( FAILURE ) ;         /* XXX: need to do more ? */
      
      mup->valid_bytes = bytes_to_map ;
      ASSERT( mup->valid_bytes <= mup->mapped_bytes ) ;
      mdp->file_offset += bytes_to_map ;
      SIO_MNEED( mup->addr, mup->valid_bytes ) ;
   }
   else
   {
      (void) SIO_MUNMAP( mup->addr, mup->mapped_bytes ) ;
      mup->addr = CHAR_NULL ;
   }
   return( SUCCESS ) ;
}

#else

#define try_memory_mapping( x, y, z )            FAILURE

#endif /* HAVE_MMAP */


static sio_status_e setup_read_buffer( __sio_id_t *idp, unsigned buf_size )
{
   char *buf ;

   /*
    * First allocate space for 2 buffers: primary and auxiliary
    */
   buf = malloc( buf_size * 2 ) ;
   if ( buf == NULL )
      return( FAILURE ) ;

   /*
    * The descriptor buf field should point to the start of the main buffer
    */
   idp->buf = buf + buf_size ;
   idp->buffer_size = buf_size ;
   return( SUCCESS ) ;
}


static sio_status_e init_input_stream( __sio_id_t *idp, int fd, const struct stat *stp )
{
   /*
    * First initialize the fields relevant to buffering: buf, buffer_size
    */
   if ( try_memory_mapping( fd, idp, stp ) == FAILURE )
   {
      /*
       * Try to use normal buffering
       */
      unsigned buf_size = (unsigned)
                     ( stp->st_blksize ? stp->st_blksize : SIO_BUFFER_SIZE ) ;
      
      if ( setup_read_buffer( idp, buf_size ) == FAILURE )
         return( FAILURE ) ;
   }

    /*
    * Initialize remaining descriptor fields
    */
   idp->max_line_length = 2 * idp->buffer_size - 1 ;
   idp->start = idp->end = idp->nextb = idp->buf ;
   idp->tied_fd = SIO_NO_TIED_FD ;

   return( SUCCESS ) ;
}


static sio_status_e init_output_stream( __sio_od_t *odp, int fd, 
	const struct stat *stp )
{
   unsigned buf_size ;
   char *buf ;

   buf_size = (unsigned)
                  ( stp->st_blksize ? stp->st_blksize : SIO_BUFFER_SIZE ) ;
   buf = malloc( buf_size ) ;
   if ( buf == NULL )
      return( FAILURE ) ;
   
   /*
    * Initialize buffering fields
    */
   odp->buf = buf ;
   odp->buffer_size = buf_size ;
   odp->buf_end = odp->buf + buf_size ;

   /*
    * Initialize remaining fields
    */
   odp->start = odp->nextb = odp->buf ;
   if ( isatty( fd ) )
      odp->buftype = SIO_LINEBUF ;

   if ( fd == 2 )
      odp->buftype = SIO_NOBUF ;

   return( SUCCESS ) ;
}


#ifndef HAVE_ISATTY

#ifdef HAVE_SYSVTTY

#include <termio.h>

static int isatty( int fd )
{
   struct termio t ;

   if ( ioctl( fd, TCGETA, &t ) == -1 && errno == ENOTTY )
      return( FALSE ) ;
   else
      return( TRUE ) ;
}
#endif   /* HAVE_SYSVTTY */

#ifdef HAVE_BSDTTY

#include <sgtty.h>

static int isatty( int fd )
{
   struct sgttyb s ;

   if ( ioctl( fd, TIOCGETP, &s ) == -1 && errno == ENOTTY )