ex1a3.c File Reference

Appfs Exercise 1: direct read input, split main into several functions. More...

#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <limits.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>
#include <assert.h>

Go to the source code of this file.

Macros
#define	MAX_NUMS   ((INT32_MAX >> 5) + 1)
	Maximum number of 32 bit ints we need to store bits. More...
#define	BUF_NUMS   4096
	read buffer size More...

Functions
static bool	is_little_endian (void)
	Check if the architecture is little endian. More...
static int32_t	reverse_int32 (int32_t val)
	Reverse the 4 bytes of an int between little and big endian. More...
static int	store_numbers (const char *filename, uint32_t *have_num, const unsigned int max_nums)
	Read numbers from file and set bits in provided array. More...
static void	output_numbers (FILE *fp, uint32_t *have_num, const unsigned int max_nums)
	Read through the marked bits and print out the numbers in ascending order. More...
int	main (int argc, char **argv)
	Program to read a file with binary positive 32 bit integers, sort the numbers and print them sorted. More...

Detailed Description

Author

Thorsten Koch

Date

24Oct2014

gcc -O3 -Wall -std=c99 -o ex1a3 ex1a3.c

Using direct read() for input Improvements to ex1a2: Split main into several functions.

Definition in file ex1a3.c.

Macro Definition Documentation

#define BUF_NUMS   4096

Definition at line 23 of file ex1a3.c.

#define MAX_NUMS   ((INT32_MAX >> 5) + 1)

Definition at line 22 of file ex1a3.c.

Function Documentation

static bool is_little_endian ( void  )

inlinestatic

This check is constant and can be optimized away by the compiler during compile time. All conditionals depending on it are then decided at compile time

Returns

true if the machine uses little endian, false otherwise.

Definition at line 30 of file ex1a3.c.

{
   union { uint32_t u; char c[sizeof(uint32_t)]; } bint = { 0x01020304 };

   return bint.c[0] == 4; 
}

int main	(	int	argc,
		char **	argv
	)

Actually, the numbers are not sorted. There is an array with one bit for each possible number. Upon reading the respective bit is set for the number recognized. At the end the array is scanned in order and the numbers present are printed.

Parameters

argv	[1] name of file to read

Definition at line 148 of file ex1a3.c.

{
   const char* usage = "usage: %s filename\n";

   /* made static, because otherwise, the stack size might be too small.
    */
   uint32_t* have_num;
   int       total_nums;
   
   /* Check arguments, we need a filename.
    */
   if (argc < 2)
   {
      fprintf(stderr, usage, argv[0]);
      exit(EXIT_FAILURE);
   }
   if (NULL == (have_num = calloc(MAX_NUMS, sizeof(*have_num))))
   {
      fprintf(stderr, "calloc of size %lu failed\n", MAX_NUMS * sizeof(*have_num));
      exit(EXIT_FAILURE);
   }

   if (0 > (total_nums = store_numbers(argv[1], have_num, MAX_NUMS)))
      exit(EXIT_FAILURE);
      
   fprintf(stderr, "Total numbers read = %d\n", total_nums);
   
   output_numbers(stdout, have_num, MAX_NUMS);

   free(have_num);
   
   return EXIT_SUCCESS;
}

static void output_numbers ( FILE *  fp, uint32_t *  have_num, const unsigned int  max_nums  )

static

Parameters

fp	output file pointer.
have_num	array of size #max_nums * sizeof(*have_num)
max_nums	maximum number of entries in have_num

Definition at line 125 of file ex1a3.c.

{
   assert(NULL != fp);
   assert(NULL != have_num);

   for(int i = 0; i < max_nums; i++)
      if (have_num[i])  // just for speed up
         for(int k = 0; k < 31; k++)
            if (have_num[i] & (1 << k))
               fprintf(fp, "%d\n", (i << 5) + k);
}

static int32_t reverse_int32 ( int32_t  val )

inlinestatic

Byte order 1 2 3 4 ist reversed to 4 3 2 1

Parameters

val	value to be reversed

Returns

reversed value

Definition at line 42 of file ex1a3.c.

{
    val = ((val << 8) & 0xFF00FF00) | ((val >> 8) & 0xFF00FF);
    
    return (val << 16) | ((val >> 16) & 0xFFFF);
}

static int store_numbers ( const char *  filename, uint32_t *  have_num, const unsigned int  max_nums  )

static

Returns

the total number of numbers read. Be aware that some of the numbers may have beend discarded.

Parameters

filename	Path/Name of file to read
have_num	array of size #max_nums * sizeof(*have_num)
max_nums	maximum number of entries in have_num

Definition at line 52 of file ex1a3.c.

{
   int32_t buf[BUF_NUMS];
   int     fd;
   int     n;
   int     total_nums = 0;

   assert(NULL != filename);
   assert(0    <  strlen(filename));
   assert(NULL != have_num);
   assert(0    <  max_nums);
   
   /* Open file
    */
   if (0 > (fd = open(filename, O_RDONLY)))
   {
      perror(filename);
      return -1;
   }

   /* Read from file until data exhausted
    */
   while(0 < (n = read(fd, buf, sizeof(buf))))
   {
      int nums_read = n / sizeof(buf[0]); 

      assert(nums_read <= BUF_NUMS);
      
      total_nums += nums_read;

      /* Run through buffer of read numbers and set mark bits
       */
      for(int i = 0; i < nums_read; i++)
      {
         int32_t num = buf[i];

         if (!is_little_endian())
            num = reverse_int32(num);
         
         // fprintf(stderr, "%d\n", num);

         /* Check input: really >= 0 ? Otherwise ignore
          */
         if (num >= 0)
         {
            int      idx = num >> 5;         // n / 32
            uint32_t msk = 1 << (num & 31);  // bit number n mod 32 

            assert(idx >= 0 && idx < max_nums);
            
            have_num[idx] |= msk;
         }
      }
   }
   /* man close(2):
    * Not  checking  the  return value of close() is a common but nevertheless serious programming error.
    * It is quite possible that errors on a previous write(2) operation are first reported at the
    * final close().  Not checking the return value when closing the file may lead to silent loss of data.
    * This can especially be observed with NFS and with disk quota.
    */
   if (close(fd))
   {
      perror("close: ");
      return -2;
   }
   return total_nums;
}