_MEMORY-MAPPED FILE I/O_
by Doug Huffman (Listings One-Four) 
_SORTING FILES WITH NT'S MEMORY-MAPPED FILE I/O_
by Eric Bergman-Terrell (Listings Five-Thirteen)

[LISTING ONE]

struct cust
{
  char name[40];      /* Both first and last names. */
  char address1[30];
  char address2[30];
  char address3[30];
  char address4[30];
  char phone1[20];
  char phone2[20];
}


[LISTING TWO]

#include <io.h>
#include <fcntl.h>
#include <structs.h>    /*      defines structure "cust"                */

struct cust *customer;  /*      pointer to customer.dat file    */
void *state;            /*      pointer to state.dat file       */
int c_handle,s_handle;

void *_cdecl _x32_mmfio_open(int fd,int size);

int map_files()
{
  if ((c_handle = open("customer.dat",O_RDWR)) == -1)
  {
    return -1;          /*      return failure if unable to open file   */
  }
  if ((s_handle = open("state.dat",O_RDWR)) == -1)
  {
    return -1;          /*      return failure if unable to open file   */
  }
/*      We will allow 150 megabytes of space for customer.dat even if the file
        is smaller than this.  This sets a maximum limit for the address space 
        available for accessing this file.  If the file is currently smaller 
        than 150 megabytes, this will allow the operating system to 
        automatically expand the file up to 150 megabytes if more customers 
        are added to the list.
*/
  if ((customer = _x32_mmfio_open(c_handle,150*1024*1024)) == 0)
  {
    return -1;          /*      return failure if unable to map file    */
  }

/*      State.dat is a fixed length file of 500 kilobytes       */
  if ((state = _x32_mmfio_open(s_handle,500*1024)) == 0)
  {
    return -1;          /*      return failure if unable to map file    */
  }

/*      The pointers customer and state have been successfully initialized, 
        return success.
*/
  return 0;
}


[LISTING THREE]

#include <io.h>
#include <structs.h>            /* defines structure "cust"       */

extern struct cust *customer;   /* pointer to customer.dat file    */

/*      This function uses printf to output a customers name specified by
the customer index number which is passed to the function. This character
string resides in a mmfio region and will automatically be read from the file
customer.dat if it does not already exist in memory.
*/ 

void prnt_name(int cust_num)
{
  printf("\nCustomer name: %s",customer[cust_num].name);
  return;
}



[LISTING FOUR]

int process_file(HANDLE file)
    {
    HANDLE fmap;
    char *file_array;
    int i;
/* create file mapping object -- use OpenFileMapping() if
   you need to use an existing fmo */
    fmap=CreateFileMapping(file,NULL,PAGE_READONLY,0,0,NULL);
    if (!fmap) return 0;

/* get pointer to entire file */
    file_array=MapViewOfFile(fmap,FILE_MAP_READ,0,0,0);
    if (!file_array) return 0;
/* process data here */
    process_data(file_array);
/* Unmap file from our address space */
    UnmapViewOfFile(file_array);
/* Close fmo */
    CloseHandle(fmap);
    return 1;  /* success */
    }
        

[LISTING FIVE]

#define FIELD_NAME_LEN     8

#define CMP_FCN_NAME_LEN  16
typedef struct
{
char         field_name[FIELD_NAME_LEN + 1],cmp_fcn_name[CMP_FCN_NAME_LEN + 1];
size_t       size, align_size, offset;
int          sort_order, alignment, count, ascending;
CMP_FCN_PTR  cmp_fcn;
} FIELD_INFO;
typedef struct
{
int         num_fields;
size_t      rec_size;
/* first num_keys entries are keys, in order */
FIELD_INFO  field_info[MAX_FIELDS];
} SORT_DEF;
void read_sort_def(const char *def_filename);
}

[LISTING SIX]

#include <stdlib.h>
#include <string.h>
#include "compare.h"
#include "sort_def.h"
#include "error.h"
#include "globvars.h"

int sort_def_cmp(const void *a, const void *b)

/* Compare the sort order fields of the SORT_DEF records. */
{

return ((FIELD_INFO *) a)->sort_order - 
       ((FIELD_INFO *) b)->sort_order;
}
void read_sort_def(const char *def_filename)
/* Read the contents of the sort definition file and store them in Sort_def. */
{
FILE        *input;
char        line[1024], *ptr;
int         i, line_nbr = 0, max_alignment = 0;
FIELD_INFO  *cur;
const char  *delims = " \n\t";
size_t      offset = 0;
if ((input = fopen(def_filename, "r")) == (FILE *) NULL)
  fatal_err("read_sort_def: cannot open file %s", def_filename);
Sort_def.num_fields = Sort_def.rec_size = 0;
cur = Sort_def.field_info;
/* Get fields from sort definition file. */
while (fgets(line, sizeof(line), input) != (char *) NULL)
  {
  /* Discard comment lines. */
  if (line[0] == '#')
    continue;
  line_nbr++;
  if (Sort_def.num_fields >= MAX_FIELDS)
    fatal_err("read_sort_def: too many entries in sort definition file");
  /* Get field name. */
  if ((ptr = strtok(line, delims)) == (char *) NULL)
    fatal_err("error in field name on line %d of sort def. file", line_nbr);
  memset(cur->field_name, '\0', sizeof(cur->field_name));
  strncpy(cur->field_name, ptr, sizeof(cur->field_name) - 1);
  /* Get sort order. */
  if ((ptr = strtok(NULL, delims)) == (char *) NULL)
    fatal_err("error in sort order on line %d of sort def. file", line_nbr);
  cur->sort_order = atoi(ptr);
  /* Get size. */
  if ((ptr = strtok(NULL, delims)) == (char *) NULL)
    fatal_err("error in size on line %d of sort def. file", line_nbr);
  if ((cur->size = atoi(ptr)) <= 0)
    fatal_err("invalid size on line %d of sort def. file", line_nbr);
  /* Get alignment. */
  if ((ptr = strtok(NULL, delims)) == (char *) NULL)
    fatal_err("error in alignment on line %d of sort def. file", line_nbr);
  if ((cur->alignment = atoi(ptr)) < 0)
    fatal_err("invalid alignment on line %d of sort def. file", line_nbr);
  /* Keep track of maximum alignment. */
  if (cur->alignment > max_alignment)
    max_alignment = cur->alignment;
  /* Get count. */
  if ((ptr = strtok(NULL, delims)) == (char *) NULL)
    fatal_err("error in count on line %d of sort def. file", line_nbr);
  if ((cur->count = atoi(ptr)) <= 0)
    fatal_err("invalid count on line %d of sort def. file", line_nbr);
  /* Get ascending/descending flag. */
  if ((ptr = strtok(NULL, delims)) == (char *) NULL)
    fatal_err("error in a/d flag on line %d of sort def. file", line_nbr);
  *ptr = toupper(*ptr);
  if (*ptr != 'A' && *ptr != 'D')
    fatal_err("invalid a/d flag on line %d of sort def. file", line_nbr);
  cur->ascending = (*ptr == 'A');
  /* Get comparison function. */
  if ((ptr = strtok(NULL, delims)) != (char *) NULL)
    {  
    memset(cur->cmp_fcn_name, '\0', sizeof(cur->cmp_fcn_name));
    strncpy(cur->cmp_fcn_name, ptr, sizeof(cur->cmp_fcn_name) - 1);
    cur->cmp_fcn = get_cmp_fcn_ptr(ptr);
    }
  else
    {
    /* This field will not be compared. */
    strcpy(cur->cmp_fcn_name, "none");
    cur->cmp_fcn = (CMP_FCN_PTR) NULL;
    }
  while (offset % cur->alignment != 0)
    offset++;
  cur->offset = offset;
  cur->align_size = cur->size;
  while (cur->align_size % cur->alignment != 0)
    cur->align_size++;

  Sort_def.num_fields++;
  offset += cur->count * cur->align_size;
  cur++;
  }
Sort_def.rec_size = offset;
/* Entire record must be padded to maximum alignment. */
while (Sort_def.rec_size % max_alignment != 0)
  Sort_def.rec_size++;
/* Print out contents of sort definition file. */
printf("%-*.*s  Order   Size    Offset  Alignment  Count  A/D   "
       "Cmp. Fcn.\n\n",
       FIELD_NAME_LEN, FIELD_NAME_LEN, "Field");
for (i = 0, cur = Sort_def.field_info; i < Sort_def.num_fields; i++, cur++)
  printf("%-*.*s %6d %6d    %6d     %6d %6d  %s  %s\n",
         FIELD_NAME_LEN, FIELD_NAME_LEN, cur->field_name,
         (int) cur->sort_order, (int) cur->size, (int) cur->offset, 
         (int) cur->alignment, 
         (int) cur->count, cur->ascending ? "asc " : "desc",
         cur->cmp_fcn_name);
printf("\nRecord Size: %d bytes\n\n", (int) Sort_def.rec_size);
/* Sort the fields based on the user-specified sort order. */
qsort(Sort_def.field_info,Sort_def.num_fields,sizeof(FIELD_INFO),sort_def_cmp);
fclose(input);
}
}


[LISTING SEVEN]

typedef int (*CMP_FCN_PTR) 
  (const char *a, const char *b, size_t align_size, int count);
CMP_FCN_PTR get_cmp_fcn_ptr(const char *cmp_fcn_name);
}

[LISTING EIGHT]

#include <stdlib.h>
#include <string.h>
#include "compare.h"
#include "sort_def.h"
#include "error.h"
#include "globvars.h"

#define COMPARE(a, b) ((a > b) ? 1 : (a < b) ? -1 : 0)
int uns_chr_cmp(const char *a, const char *b, size_t align_size, int count)

/* unsigned comparison of characters */

{
int  i, cmp = 0;
for (i = 0; i < count && cmp == 0; i++, a += align_size, b += align_size)
  cmp = COMPARE(*(unsigned char *) a, *(unsigned char *) b);
return cmp;
}
int sig_chr_cmp(const char *a, const char *b, size_t align_size, int count)
/* signed comparison of characters */
{
int  i, cmp = 0;
for (i = 0; i < count && cmp == 0; i++, a += align_size, b += align_size)
  cmp = COMPARE(*(signed char *) a, *(signed char *) b);
return cmp;
}
int uns_shr_cmp(const char *a, const char *b, size_t align_size, int count)
/* unsigned comparison of short integers */
{
int  i, cmp = 0;
for (i = 0; i < count && cmp == 0; i++, a += align_size, b += align_size)
  cmp = COMPARE(*(unsigned short int *) a, *(unsigned short int *) b);
return cmp;
}
int sig_shr_cmp(const char *a, const char *b, size_t align_size, int count)
/* signed comparison of short integers */
{
int  i, cmp = 0;
for (i = 0; i < count && cmp == 0; i++, a += align_size, b += align_size)
  cmp = COMPARE(*(signed short int *) a, *(signed short int *) b);
return cmp;
}
int uns_lng_cmp(const char *a, const char *b, size_t align_size, int count)
/* unsigned comparison of long integers */
{
int  i, cmp = 0;
for (i = 0; i < count && cmp == 0; i++, a += align_size, b += align_size)
  cmp = COMPARE(*(unsigned long int *) a, *(unsigned long int *) b);
return cmp;
}
int sig_lng_cmp(const char *a, const char *b, size_t align_size, int count)
/* signed comparison of long integers */
{
int  i, cmp = 0;
for (i = 0; i < count && cmp == 0; i++, a += align_size, b += align_size)
  cmp = COMPARE(*(signed long int *) a, *(signed long int *) b);
return cmp;
}
int compare(const void *a, const void *b)
/* Compare all fields in order.  Return: -1 if a < b, 1 if a > b, 0 if a = b.*/
{
int                  i, result = 0;
FIELD_INFO           *cur;
const unsigned char  *aa = a, *bb = b;
for (i = 0, cur = Sort_def.field_info; i < Sort_def.num_fields; i++, cur++)
  {
  /* Make sure current field should be compared. */
  if (*cur->cmp_fcn != (CMP_FCN_PTR) NULL)
    {
    result = (*cur->cmp_fcn) ((char *) &aa[cur->offset],
                              (char *) &bb[cur->offset], 
                              cur->size, cur->count);
    /* Invert result if field is sorted in descending order. */
    if (!cur->ascending)
      result = -result;
    if (result != 0)
      return result;
    }
  }
return 0;
}
typedef struct 
{
char         *cmp_fcn_name;
CMP_FCN_PTR  cmp_fcn_ptr;
} CMP_FCN_INFO;
static const CMP_FCN_INFO cmp_fcn_info[] =
{
  {"uns_chr_cmp", uns_chr_cmp},
  {"sig_chr_cmp", sig_chr_cmp},
  {"uns_shr_cmp", uns_shr_cmp},
  {"sig_shr_cmp", sig_shr_cmp},
  {"uns_lng_cmp", uns_lng_cmp},
  {"sig_lng_cmp", sig_lng_cmp}
};
CMP_FCN_PTR get_cmp_fcn_ptr(const char *cmp_fcn_name)
/* Return a pointer to the named function. */
{
int  i;
for (i = 0; i < sizeof(cmp_fcn_info) / sizeof(cmp_fcn_info[0]); i++)
  if (stricmp(cmp_fcn_name, cmp_fcn_info[i].cmp_fcn_name) == 0)
    return cmp_fcn_info[i].cmp_fcn_ptr;
fatal_err("cannot find function %s", cmp_fcn_name);
}


[LISTING NINE]

fatal_err(const char *fmt,...);

[LISTING TEN]

#include <stdlib.h>
#include <stdarg.h>
#include "error.h"

void fatal_err(const char *fmt,...)
/* Give a fatal error message and exit. */
{
char            buffer[1024];
va_list         argptr;
va_start(argptr, fmt);
vsprintf(buffer, fmt, argptr);

va_end(argptr);
fprintf(stderr, "** FATAL ERROR ** %s\n", buffer);
exit(EXIT_FAILURE);
}


[LISTING ELEVEN]

SORT_DEF    Sort_def;


[LISTING TWELVE]

#include "compare.h"
#include "sort_def.h"
#include "globvars.h"

SORT_DEF  Sort_def;


LISTING THIRTEEN]

OBJS=mmf_sort.obj error.obj globvars.obj sort_def.obj compare.obj

all: mmf_sort.exe

mmf_sort.exe: $(OBJS)

.c.obj:
    $(cc) $(cflags) -Ge $(cvars) $*.c

mmf_sort.exe: $(OBJS)
    $(link) $(conflags) -out:mmf_sort.exe shell32.lib $(OBJS) $(conlibs)




[Example 1:]

(a)

typedef struct
{
char  chr[2];
long  lng;
} DATA;

(b)
# field-name sort-order size alignment count a/d optional-comparison-function
chr 1 1 1 2 a uns_chr_cmp
lng 2 4 4 1 a uns_lng_cmp



Figure 1:

(a)

chr       lng

ZX        100
AB        100
AT        200
AA        200


(b)

chr       lng

AA        200
AB        100
AT        200
ZX        100


(c)

chr       lng


AB        100
ZX        100
AA        200
AT        200