Functions as Data

Consider the following bubble sort:

#include <stdio.h>

#define TRUE 1
#define FALSE 0

void bubble1 (int *pArray, int count)
{
  int bExchange = TRUE;
  int indx;
  int temp;

  while (bExchange)
  {
    bExchange = FALSE;

    for (indx = 0; indx < count - 1; indx++)
    {
      if (*(pArray + indx) > *(pArray + indx + 1))
      {
        temp = *(pArray + indx);
        *(pArray + indx) = *(pArray + indx + 1);
        *(pArray + indx + 1) = temp;
        bExchange = TRUE;
      }
    }
  }
 }

Let's say we wanted to make the above sorting routine generic.

Q#1: Can we make the sorting routine generic in the following way:

a) void bubble (void *arry, int count);

b) void bubble (void *arry, int count, int elementsize);

Note1: Given b) we can calculate an arbitrary element of arry[k] as follows:

(void *) ((char *) arry + k * elementsize)

Note2: Address arithmetic cannot be performed on type void *


 void bubble2 (void *pArray, int count, int elementSize)
 {
   int bExchange = TRUE;
   int indx;
   void *pTemp = malloc (elementSize);

   while (bExchange)
   {
     bExchange = FALSE;
     for (indx = 0; indx < count - 1; indx++)
     {
       if (memcmp((void *)((char *) pArray + indx * elementSize),
                  ((void *)((char *) pArray + (indx + 1) * elementSize)),
                  elementSize) > 0)
       {
         memcpy (pTemp, (void *)((char *) pArray + indx * elementSize), elementSize);
         memcpy ((void *)((char *) pArray + indx * elementSize), 
         (void *)((char *) pArray + (indx + 1) * elementSize), elementSize);
         memcpy ((void *)((char *) pArray + (indx + 1) * elementSize), pTemp, elementSize);

         bExchange = TRUE;
       }
     }
   }
   free (pTemp);
 }
   
 int main ()
 {
   int numbersInt[] = {5, 4, 3, 2, 1};
   char numbersChar[] = {'E', 'D', 'C', 'B', 'A'};
   float numbersFloat[] = {5.0, 4.0, 3.0, 2.0, 1.0};
   int i;

   bubble1 (numbersInt, 5);
   bubble2 (numbersChar, 5, sizeof (char));
   bubble2 (numbersFloat, 5, sizeof (float));

   for (i = 0; i < 5; i++)
   {
     printf("%d\n", numbersInt[i]);
   }

   for (i = 0; i < 5; i++)
   {
     printf("%c\n", numbersChar[i]);
   }

   for (i = 0; i < 5; i++)
   {
     printf("%f\n", numbersFloat[i]);
   }

Results

   1
   2
   3
   4
   5
   A
   B
   C
   D
   E
   2.000000
   3.000000
   1.000000
   4.000000
   5.000000
   Press any key to continue

Why do you think the floating point numbers are not sorted correctly?

Passing Functions as Arguments

#include <stdio.h>

#define TRUE 1
#define FALSE 0
#define DEBUG 0

// Step 1: Define the prototype of the compare function

typedef int (*cmpFnT) (const void *p1, const void *p2);

// Step 2: Implement each compare function

int IntCmpFn (const void *p1, const void *p2)
{
  int v1, v2;
  char ch;

  v1 = *((int *) p1);
  v2 = *((int *) p2);
  if (DEBUG)
  {
    printf ("v1 = %d v2 = %d\n", v1, v2);
    ch = getchar ();
  }
  if (v1 == v2) 
  {
    return (0);
  }
  return ((v1 < v2) ? -1 : 1);
}

int FloatCmpFn (const void *p1, const void *p2)
{
  float v1, v2;
  char ch;

  v1 = *((float *) p1);
  v2 = *((float *) p2);
  if (DEBUG)
  {
    printf ("v1 = %f v2 = %f\n", v1, v2);
    ch = getchar ();
  }
  if (v1 == v2) 
  {
    return (0);
  }
  return ((v1 < v2) ? -1 : 1);
}

// Step 3: Implement the generic function (e.g. sorting function)

void bubble (void *arry, int count, int elementsize, cmpFnT cmpFn)
{
  int xchg = FALSE;
  int indx = 0;
  void *temp = (void *) malloc (elementsize);

  while (!xchg)
  {
    while ((indx < count - 1))
    {
      if (cmpFn((arry + (indx * elementsize)), 
                (arry + (indx + 1) * elementsize)) > 0)
      {
         // Swap elements
         xchg = TRUE;
      }
      indx++;
    }
    if (!xchg)
    {
      return;
    }

    indx = 0;
    xchg = FALSE;
  }
  free (temp);
}

// Step 4: Write driver to test

int main ()
{
  int a[] = {5,4,3,2,1};
  float b[] = {5,4,3,2,1};
  int i;

  bubble (a, 5, sizeof (int), IntCmpFn);
  bubble (b, 5, sizeof (int), FloatCmpFn);
}

Problem: Write a generic function that accepts an integer or float array and prints out the contents of the array. You will go through the same steps we discussed above.