When you incremet and decrement a pointer it adjust based on the data type pointed to by the pointer. In the previous examples the data type pointed to was a char - which is a byte (8 bits) in terms of strorage. So p++ (where char *p) increments by obe byte of 8 bits. But what happens if the pointer p points to a structure?

/*
File: pointers.c

Description: Creates an array of struct types. Initialises and computes
on an array of structs. The code is written to study the address of
pointers and to look at what happens when pointers are incremented
and decremented.

Input: None

Output: Prints various contents of pointers to the display
*/

#include <stdio.h>

#define NUMPEOPLE  100

  // Note the struct array in a little different from one defined in
  // leture 6. Here the array definitions for name and address are
  // pointers to characters. Note, we use typedef to define the structure
  // type. Saves use using the name struct when defining instances of
  // this type.

typedef struct _person {
     char *name;
     char *addr;
     int age;
} person;

// How big is person struct?

person people[NUMPEOPLE];
person *p;
int age;

char *myname = "Andrew T. Campbell";
char *myadr =  "People’s Republic of Norwich";

int main() {

  // intiatlise p to the address of the people array
  // of struct person (which is the tag)

  p = (person *)&people;

  int i;

  // how much storage is needed for a pointer?
  // how much storage is needed for a struct of person?

  printf("pointer needs %ld bytes, struct people 0x%x (HEX)
         bytes\n", sizeof(p), (unsigned int)sizeof(person));

  // how much storage for the array of people?
  // what is the address in memory of the p and people variables?

  printf("The address of p is %p, it’s contes are (i.e.,
         it points to) %p\n",(void *)&p,(void *)p);

  printf("The address of people is %p\n", (void *)&people);

  // increment to next person in the table

  p++;

  printf("after incrementing p its value is %p\n", (void *)p);

  // decrement to the previous person

  p--;

  printf("after incrementing p its value is %p\n", (void *)p);

  // Let’s initialise our array

  for (i=0; i < NUMPEOPLE; i++) {
     people[i].age = 21;
     people[i].name = myname;
     people[i].addr = myadr;
  }

  // Let’s reset p (even though it points to people already)

  p = (person *)&people;

  // Let’s compute the total age for people.
  // NOTE, that we use the pointer p and incremet p to move through
  // the array of structs. Importantly we use the "->" symbol to
  // index elements in the struct.

  for (i=0; i < NUMPEOPLE; i++) {
     age += p->age;  // note the -> not . is used
     p++;
  }

  p = (person *)&people;

  printf("%s is %d years old (again) and lives
         in %s\n", p->name, p->age, p->addr);

  printf("The accumulative age of all people is %d years\n", age);

  return 0;

}

If you compile and run pointers then you get the following. Look closely at the pointer values and the address of the people array of structs and the various sizes of data types including a pointer and the size of the person struct.

[atc@dhcp-210-161 l8] ./pointers
pointer needs 4 bytes, struct people 0xc (HEX) bytes
The address of p is 0x2070, it’s contes are (i.e., it points to) 0x2080
The address of people is 0x2080
after incrementing p its value is 0x208c
after incrementing p its value is 0x2080
Andrew T. Campbell is 21 years old (again) and lives in People’s Republic of Norwich
The accumulative age of all people is 2100 years

Sorting an array of values

A frequently required operation is to sort an array of, say, integers or characters. The standard C library provides a generic function named qsort() to help with this, but we must write a pointer-based function to perform the comparison of the arrays elements:

  #include <stdlib.h>

  #define N 100

  int compare(const int *ip, const int *jp) {

      return(*i - *j);

  }

  int main(int argc, char *argv[]) {

    int i;
    int values[N];

    srandom( getpid() );

    for(i=0 ; i<N ; i++)
        values[i] = random();

    qsort((void *)values, (size_t)N,sizeof(values[0]), compare);
    ....

    return(0);
  }

Dynamic memory allocation

The function malloc() returns a requested number of bytes from the operating systems heap. If insufficient memory is available malloc returns NULL. When we are finished using the space returned by malloc(), our program should be returned to the heap with a call to free(). If a process continues to malloc() memory and fails to deallocate it using free(), the process will quickly run out of memory and terminate ungracefully.

The dynamic memory management functions are supported by the standard C library and their detailed function protypes are found in stdlib.h. Memor allocation functions allow programmers to dynamically allocate memory from the heap for variables, arrays, and structures; rather that statically allocating space on the stack. Many times it is not possible to know in advance of run time of a program what the memory demands for the program are. People that use static allocation somewhat have to second guess what the worst case memory needs are and statically allocation that at compile time. This is not a good programming principle. Better to make your program general and capable of dealing with a wide variety of demands - the message, but the smarts into the program and don’t second guess.

Note:Unlike Java, C has no garbage collection of heap objects, and so programs must be very careful about deallocating memory that is no longer required.

The memory management functions use “pointer to void” (void *) which allows the programmer to assign the returned pointer to memory to any struct, array, variable without casting. This is a very good example of the use of pointer to void.

Consider the following example which allocates space for a new copy of a given string. This is very similar to the standard function named strdup():

  char *newstr(const char *s) {

      void *malloc(unsigned int nbytes);
      char *p;

      if( (p=malloc(strlen(s)+1)) == NULL ) {
          fprintf(stderr,"out of memory!\n");
          exit(1);
      }

      strcpy(p,s);
      return(p);

    }

  #define NEW(t) malloc(sizeof(t))

  struct l {
      char *line;
      struct l *next;
};

struct l *hd = malloc( sizeof(struct l) );

fgets(buf, MAX, fp);

while( !feof(fp) ) {
    p =NEW(struct l);
    p->line = newstr(buf);
    p->next = hd;
    hd = p;
    fgets(buf,MAX,fp);

}

The program below uses calloc to dynamically create an array of integers based on the user input n. The program allocates the memory, fills it with random integers scaled between 18 and -9, displays the array and frees the memory. It does this forever.

/*

File: memory.c

Description: Uses calloc to dynamically create an array of n ints. The
user enters n. The program allocates the memory, fills it with random integers
scaled between 18 and -9, displays the array and frees the memory. It does
this forever

Input: User enters size of the array.

Output: Displays the contents of the full array and sums up all the elements.

This problem is adapted from A Book on C (Kelly, Pohl) pg. 261

*/

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

// prototypes

void initArray(int *, int );
int  sumArray(int *, int );
void displayArray(int *, int );

int main (void) {

  int *a, n;

  srand(time(NULL));

  printf("\n%s\n",
"This program does the following repeatedly:\n"
"\n"
"     1) Create space for an array of size n\n"
"     2) Fill the array with randomly distributed digits\n"
"     3) Prints the array and the sum of its elements\n"
"     4) Frees the allocated memory\n");

  for ( ; ; ) { // do forever

    printf("Input the size of array you want created. n: ");
    if (scanf("%d", &n) !=1 || n < 1) {
      printf("Usage: n has to be > 0\n\n");
      continue;
    }
    putchar(’\n’);
    if ((a = calloc(n, sizeof(int))) == NULL) {
      printf("Error calloc failed to allocate");
      break;
    }
    initArray(a, n);
    displayArray(a, n);
    printf("Sum = %d\n\n", sumArray(a, n));
    free(a);
  }
  printf("\nLater!\n\n");
  return 0;
}

void initArray(int *a, int n) {

  int i;

  for (i = 0; i < n; i++)
    a[i] = rand()%19 - 9; // scales between 18 and - 9

}

int sumArray(int *a, int n) {

  int i, sum =0;

  for (i = 0; i < n; i++)
    sum += a[i];

  return(sum);

}

void displayArray(int *a, int n) {

  int i;

  printf("a = [");

  for (i = 0; i < n; i++)
    printf("%d%s", a[i], ((i < n - 1) ? ", " : "]\n"));

}

CS 23 Software Design and Implementation

Lecture 9

A Little more on Pointers and Dynamic Memory Allocation

Goals

Pointer Arithmetic on Structs

Sorting an array of values

Dynamic memory allocation