The following is a brief overview of Lecture 4 of the ‘Programming Paradigms,” a programming class taught at Standford University.  Screenshots and Code are included from the lecture.  The ‘Programming Paradigms’ lectures can be found in iTunes.  The link is on the Open Standford Website.  The following lecture covers implementation of Swap using Generics.

Implementation of Swap using Templates

void swap( void * vp1, void * vp2){
  void temp = *vp1;
  *vp1 = *vp2;
  *vp2 = temp;
}

The above Swap function takes a generic pointer type (void * ).  This means that it points to something that it doesn't have any type information about, so Vp1 and Vp2 are pointing to addresses in memory that it knows nothing about.  Furthermore, there is a problem with the above implementation.  One cannot declare temp or a variable to be of type void.  Also, one isn't allowed to dereference a void * variable because it doesn't know how to go out and embrace an unknown number of bytes.

void swap (void * vp1, void * vp2, int size){
 
  char buffer[size];
  memcpy(buffer, vp1, size);
  memcpy(vp1, vp2, size);
  memcpy(vp1, buffer, size);
 
}

int x = 17, y = 37;
swap(&x, &y, sizeof(int));

The offical way to perform a swap using generics is to expect a third argument to the swap function, size, where size is the explicit size of the bytes being swapped.  A character buffer of a dynamic size is first declared.  Memcpy is like strcpy, except it doesn't stop copying at '\0′  One has to specifically tell it how many bytes to copy.  Although the above example works, true ASCI C doesn't allow you to dynamically allocate an array.

double d = ∏, e = e;
swap(&d, &e, sizeof(double))

The problem with using generics, however, is that the compiler does very little checking.  You can pass in anything you want for a void * and the compiler will not yell at you.  It might not work very nicely, but it will compile.  When you use generics, you are making the compiler do less work for you, but you run more risk when you actually run the program.

int i = 44;
short s = 5;
swap(&i, &s, sizeof(short));

Say you need to swap an int and a short, but you accidentally pass the sizeof(short) to the swap function.  Vp1 and Vp2 just have the address itself, they don't know how big the variables i and s are that they point to.  They only access the first two bytes of each address because it is specifically told to Vp1 and Vp2 to access a short.  Five will be written in the first two bytes of the int.  The first two bytes of i will be written with 5.  So zero will be written to s, 5 and 44 to i.

char * husband = strdup("Fred");
char * wife = strdup("Wilma");
 
swap(&husband, &wife, sizeof(char *));

In the above code, the husband and wife char pointers above are going to be switched.  Husband will point to Wilma and Wife will point to Fred.  We want to exchange the two things are are held by the husband and the wife variables.  If you want to swap char *, that is, the actual pointer boxes, you pass sizeof(char *).  Vp1 and Vp2 point to the pointers husband and wife.  Fred and Wilma actually stay put, the pointers are just switched.  However if the following is passed to swap:

swap(husband, wife, sizeof(char *));

This will still compile and run.  Vp1 and Vp2 this time point to the raw text "Fred\0″ and "Wilma\0."  The swap function now has two address and thinks that it is supposed to swap 4 byte figures (char *'s are four bytes).  So it copies "Wilm" from Wilma and puts it in Fred's place "Wilm\0″ and copies "Fred" and adds it to the first four letters of "Wilma" for "Freda\0″

Implementation of LSearch in Generics

First the non-generic linear search.

int lsearch(int key, int array[], int size){
 for (int i  0; i < size; i++)   {
 if(array[i] == key)
    return i;
 }
}

The lsearch seraches from the front to back of an array of a certain size looking for a key passed into the function.  The function will return index of the array of where the key was found.  The generic version is best understood as a generic blob of memory.  In order to advance from element zero to element one, the size information will have to be passed into the function.  A comparison function will also have to be passed in so we know how to compare the key to to i(th) element in the array because double =='s can't be used very easily. So the address of the key is passed in, the address of the beginning of the blob of memory, the width of each element in the blog of memory, the number of elements, as well as a comparison function.

void * lsearch (void * key, void * base, int n, int elem_size){
   for(int i = 0; i < n; i++)  {
       void * elemAddress = (char *) base + i * elemSize;
       if(memcmp(key, elemAddress, elemSize) == 0) return elemAddress;
   }
 
  return NULL;
}
 
void * elemAddress = (char *) base + i * elemSize;

This lsearch that results uses the char * casting hack.  Because base is (void *), the compiler can't do pointer arithmetic on a (void *) element, therefore, casting fools it into thinking that its pointing to one-byte characters.   The above function works in a few cases, but doesn't work in cases like struct.  A function pointer to a comparison function must be used in that case as seen below.

void * lsearch (void * key, void * base, int n, int elem_size, int (*cmpfn)(void *, void *))

This function will be discussed in the next class.