Reviewing 'C' - Part 4

This part considers data structures, their use with pointers, and the definition of derived data types.  This part ends with a brief review of dynamic memory allocation.

Enumeration Types

enum states {Start, Running, Stopped, Error};

With the type declared, the following is valid and declares a variable of that type and provides an initial value.

enum states MyState = Start;

The keywords of that type can be used in code, as in the following test.

if (MyState == Error) {
  printf("System error, please reset\n");
}

Struct Types

The keyword 'struct' allows us to define a structure that collects related items in a fashion that acts like a single object.  As an example, we define a structure for time, using integers to represent hours, minutes, and seconds. 

struct MyTime
{
   int hrs;
   int min;
   int sec;
};

The following function is used to report the current date.  The point of this exercise is to emphasize, while such a structure contains many parts, its handled as one object.  A useful analogy is taking wires, bundling and wrapping them with tape.  One bundle is easier to handle than three wires. 

// Report the time in hours:minutes:seconds format
void PrintTx(struct MyTime Now)
{
  printf("Time is %.2d:%.2d:%.2d\n", Now.hrs, Now.min, Now.sec);
}

A struct data structure is handled as a single object, hence the return keyword is used to return one such entity.  In the following program, the function IncTime() increments the time by one second and returns the updated time. 

/***********************************************************
 * TimeInc.c
 * An example program using a sturct
 **********************************************************/
#include 

struct MyTime
{
   int hrs;
   int min;
   int sec;
};

void   PrintTime(char mesg[], struct MyTime Now);
struct MyTime IncTime(struct MyTime Now);

int main()
{
  struct MyTime valx, valy;

  printf("Enter time in hours, minutes, and seconds\n");
  scanf("%d, %d, %d", &valx.hrs, &valx.min, &valx.sec);
  
  valy = IncTime(valx);

  PrintTime("Intial time:",valx);
  PrintTime("Next time..:",valy);
  return 0;
}


// Report the time in hours:minutes:seconds format
void PrintTime(char mesg[], struct MyTime X)
{
  printf("%s %.2d:%.2d:%.2d\n", mesg, X.hrs, X.min, X.sec);
}


// Increment the time by one second
struct MyTime IncTime(struct MyTime Now)
{
  // Increment the seconds
  Now.sec++;
  while (Now.sec > 59) {
    Now.sec -= 60;
    Now.min++;
  }

  // check the minutes
  while (Now.min > 59) {
    Now.min -= 60;
    Now.hrs++;
  }

  // check the hours
  while (Now.hrs > 23) {
    Now.hrs -= 24;
  }
  return Now;
}

The following is the program output.

$ TimeInc
Enter time in hours, minutes, and seconds
12,23,59
Intial time: 12:23:59
Next time..: 12:24:00

Please bear in mind that each module is compiled separately and that things like enumeration types must be declared before being used. Such things are conveniently declared in a header file. 

Single Entity Handling

The return statement in TimeInc.c serves to illustrate how the instance of a struct is handled as a single object.  In the following example a character string is encapsulated in a struct.  A character string is an array, but because this one is in a struct means that a simple assignment copies the string.

/**********************************************
 * StrStruct.c
 * Show that a struct instance is an object
 *********************************************/
struct MESG_STRING  /* define a struct */
{
  char mesg[20];    /* it contains a string */
  int  x, y;        /* and some numbers     */
};

int main()
{ /* allocate things */
  struct MESG_STRING X = {"Hello There?",5,6};
  struct MESG_STRING Y;

  Y = X;      /* this copies a whole struct */

  printf("X message: %s\n", X.mesg);
  Y.mesg[5] = '!';
  Y.mesg[6] = '\0';
  printf("X message: %s\n", X.mesg);
  printf("Y message: %s\n", Y.mesg);
}

The following is the corresponding program output.  The string in Y is changed but the string in X is not changed. 

$ StrStruct
X message: Hello There?
X message: Hello There?
Y message: Hello!

To repeat one last time, a struct is like a container in that it may contain several data entities, but acts like a single object.

Unions

A union allows for the reuse of memory for different data.  For example, is we need to define a single object named X that can store a four character string, a single floating point number, or an long integer, start by defining a union.  In this example the union is named mixed.

union mixed
{
  char  c[4];
  float f;
  long  i;
};

The following example program provides an example use of a union. 

/***************************************
 * mixed.c
 * An example use of a union
 **************************************/
#include <stdio.h>
#include <string.h>

union mixed
{
  char  c[4];
  float f;
  long  i;
};

int main()
{
  union mixed X;

  printf("Num Bytes: %d\n", sizeof(X));
  strcpy(X.c,"Hi!");
  printf("String...: %s\n",X.c);

  X.i = 73L;
  printf("Int.Val..: %d\n",X.i);

  X.f = 12.34;
  printf("Float Val: %f\n",X.f);
  return 0;
}

The lcc-32 compiler package was used to compile and produce the following output.  In general, the union object will be the size of the largest type included in the union definition.  We will find use of unions in embedded systems when dealing with peripheral registers.

Num Bytes: 4
String...: Hi!
Int.Val..: 73
Float Val: 12.340000

Pointers and Struct

Recall the MyTime struct defined earlier, the struct provides a convenient way to combine related information into one package. 

struct MyTime
{
  int hrs;
  int min;
  int sec;
};

Suppose I have an array of MyTime structs as well as a pointer to this struct type, as in the following. 

struct MyTime List[5];
struct MyTime *pDate;

pData = List+2;

We should like to be able to refer to any one of the parts of a struct that a pointer dereferences.  One way is to first use the * operator to dereference and then . operator.  Parenthesis are needed as . has higher precedence than *.

(*pData).hrs = 0;

The arrow operator is shorthand for the above operation.  Hopefully the meaning of the arrow will be intuitively obvious to you. 

pData->hrs = 0;

The typedef keyword

Types named int, float, double, and the like are predefined by the compiler.  The keyword typedef is used to assign a new name to a predefined type or a derived data type.  The general format of a typedef declaration is as follows.  The new type named type_name is defined by definition. 

typedef definition type_name;

'C' provides a capability to assign an alternate name to a data type.  The following defines an alternate name for type int.  With this declaration, variables can be defined to be of type COUNTER.

typedef int COUNTER;
COUNTER j, n;

In this example, the typedef is roughly equivalent to a #define statement. 

#define COUNTER int

However, since typedef declarations are handled by the 'C' compiler proper, not the 'C' preprocessor, typedef declarations can be more flexible than #define in assigning names to derived data types.  Consider a type derived from a struct type. 

typedef struct
  {
    float x;
    float y
  } POINT;

The type POINT is associated with a structure containing the floating point members x and y.  Variables can now be declared to be of type POINT, as in

static POINT origin = { 0.0, 0.0 };

Dynamic Memory Allocation

A collection of 'C' library functions are provided that allow a programmer to dynamically allocate memory on the fly.  Such functionality is particularly useful when the size of a problem is not known in advance.  The library function malloc() first allocates a block of memory, the size of which you specify, and returns a pointer of type void.  The calloc() library function is similar but clears the initialized memory and requires two arguments, the number of units to allocate, and the size of a single unit. 

In general terms, the functions malloc() and calloc() are not guaranteed to allocate memory.  In the odd case that memory cannot be allocated, a so called null-pointer is returned.  In using dynamic memory allocation, get into the habit of performing tests like that in the following snippets of code.  The keyword NULL is defined in stdlib.h header file.  Assume that px and py are pointers to type int. 

px = malloc(10 * sizeof(*px));
if (px == (int *)NULL)
  // do something

py = calloc(10,sizeof(*px));
if (py == (int *)NULL)
  // do something

Each test above is a sanity check that verifies that the requested memory is actually allocated.  Once allocated, the pointers px and py can each be used just like a int array.  The free() library function is used to release a previously allocated block, for use later.  The realloc() function is useful to resize a memory allocation. 

free(px);

The following program illustrates use of dynamically allocated memory.  Prime numbers may be generated by an algorithm known as the Sieve of Eratosthenes.  The version presented here finds all the prime numbers in the sequence 2, up to N which you specify at run-time. 

1. Define an array P of type int with N+1 elements, all cleared
2. Assign the value 2 to an integer B
3. Assign the value in B to integer X
4. If X is larger than N then the program terminates
5. If P[X] is zero then X is prime
6. Add B to X
7. If X higher than N then add 1 to B and return to step 3
8. Assign 1 to P[X] and return to step 6

In reviewing the above algorithm, you may be first tempted to resort to using goto statements to implement this.  However, in drawing the flowchart for the above algorithm the shape of the algorithm becomes clear.  After drawing the flowchart I produced the following program. 

/*****************************************************************
 * sieve.c  - Classic Code
 * Implements the famous Sieve of Eratosthenes
 ****************************************************************/
#include <stdlib.h>
#include <stdio.h>
int main()
{
  int B, X, N, *P;
  char response[80];
  
  // Request a limit value
  printf("Set the upper limit for the primes search\n: ");
  scanf("%d", &N);
  
  // An obvious sanity check
  if (N < 0) {
    printf("I'm not prepared to handle a limit value of %d\n",N);
    exit(0);
  }
  
  // Attempt to allocate memory
  P = calloc(N+1, sizeof(*P));
  if (P == (int *)NULL) {
    printf("I'm not able to allocate an array of size %d\n",N);
    exit(0);
  }
  
  // The outer loop, pick a base number
  B = 2;
  for (X = B; X <= N; X = ++B) {
    
    // Test if the flag says prime
    if (P[X] == 0)
      printf("%4d\n",X);
    
    // Mark multiples of the base as not prime
    for (X += B; X <= N; X += B)
      P[X] = 1;
  }
  
  // All done
  free(P);
  printf("Done!\n");
  return 0;
}

The following is example output from the program:

$ sieve
Set the upper limit for the primes search
: 10
   2
   3
   5
   7
Done!

While it is certainly useful to be able to allocate memory on the fly, this capability must be used with extreme care.  Excessive use of dynamic memory may lead to a condition known as internal fragmentation where only small blocks of memory are available.  In using dynamically allocated memory, it must not be lost sight of.  Doing otherwise leads to an undesirable phenomenon called a memory leak which slowly starves a system of its memory resources.  Likewise, the free() function must not release memory that has already been released. 

There is no single memory use scheme, but many 'C' compilers assume a memory model like the following.  In this arrangement, there is a block of unused memory between the heap and the stack. 

• Low memory contains executable code
• Data memory is just above the executable code
• The stack is at high memory
• Dynamically allocated memory comes from an area called the heap that is just above data memory. 

Homework Problems - Part 4

1. Copy the example TimeInc.c to TimeInc2.c.  Replace the MyTime structure with a new type named TIME, derived from the data structure.  For homework submit the new source code and example output. 

2. Consider the struct defined in StrStruct.c.  Write new struct named PDATA that contains the following items:

   • A character string 'name' that is 32 bytes long
   • An integer named 'years'
   • A float named 'height'
   • A float named 'weight'

3. Modify the example sieve.c to produce the produce sieve2.c 

   • Rather using an int array, form a char array
   • The NULL character is '\0', make the substitution
   • Rather than using 1 to mark elements, use a non-null character of your choice
   Produce a program listing and sample output from your program for N = 21

4. This problem and the next are related to use of the Matrix struct defined below.  To make it easier to access an element in such an array, we use the Mx() macro, which is also defined below. 

   #define Mx(arg,r,c) ((arg).pX[r][c])
   
   struct Matrix
   {
     int      rows;
     int      cols;
     double **pX;
   };
   

   Given a Matrix struct, the following function provides a means to print the contents of the matrix. 

   void MatPrint(struct Matrix M, char messg[])
   {
     int r, c;
     // Print the message
     printf("%s\n",messg);
   
     // print the matrix
     for (r = 0; r < M.rows; r++) {
       for (c = 0; c < M.cols; c++) {
         printf("%7.3lf ", Mx(M,r,c));
       } printf("\n");
     }
   }
   

   Write a function MatAlloc() that accepts two arguments, representing the number of rows and columns and returns a properly configured matrix structure.

   • Use malloc() twice, once to allocate an array of pointers and a second time in a loop to allocate a 2-D array of doubles. 
   • Assign the appropriate value to a Matrix struct.

   Write a program that uses MatAlloc to make an array, next assign the values listed below to the array, and then calls MatPrint() to report the contents of the array.  The program immediately exits, so that it is not necessary here to call free().  Produce a program listing and the program output. 

   | 1 2 |
   | 3 5 |
   

5. Write a function MatFree() that accepts a Matrix struct as an argument sets values in row and cols to zero and performs the necessary work to release all memory allocated to the matrix.  This listing may be hand written or computer generated. 

6. Write a function MatAdd() that accepts a matrix A as well as a matrix B and adds the contents of matrix B to matrix A.  If the dimensions of the matrices is different, the function produces an error message and causes the program to exit. 

7. Write a file matlib.h that includes all the macros and struct definitions from the above problems.  Insert a useful comment at the top of the file.

Please Let me know that you read my web pages.