Linear Search with Generics

void * lserach(void * key, void * base, int n, int elemsize, int(*cmpfn)(void*, void*) )
{
 
  for(int i = 0; i < n; i++) {
      void * elemAddr = (char *) base + i * elemSize;
      if( cmpfn(key, elemAddr) == 0 )
          return elemAddr;
  }
 
  return NULL;
 
}

The linear serach takes five parameters.  Key is a pointer to a searched for item, base is a pointer to the base of the array, n is the number of elements in the array, elemsize is the size of an element in the array, and cmpfn is a function pointer to a compare function.  We loop through the array one element at a time.  The cmpfn returns zero if the elements are equal, and lsearch returns a pointer to that element.  If nothing is found, NULL is returned.

Implementing lsearch with ints

int array {} = {4, 2, 3, 7, 11, 7, 6};
int size = 6;
int number = 7;
 
int * found = lserach(&number, array, 6, sizeof(int), intcmp);
     if(found == NULL) :(
     else                     :)

When calling lsearch above, the address of 'array' doesn't have to be passed because when one sends in 'array,' it implicitly passes in the address of the zero(th) element.  The 'intcmp' function that is passed into lsearch needs to be coded for the above to work.

int IntCmp(void * elem1, void * elem2) {
   int * ip1 = elem1;
   int * ip2 = elem2;
 
  return *ip1 - *ip2;
}

The compare function returns a negative value if ip1 is less than ip2, zero if the elements are equal, or a positive value if ip1 is greater than ip2.  Because it is known that the elemnts we wish to search for are of type int, we can make the compare function passed to lserach an specific type of compare ala int. 

There are definetely better ways to implement generics in other languages.  These languages have learned from the mistakes in C.  C has been in existence for 35 years which is pretty old in computer time.

Implementing lsearch with CStrings

On this example, an array of CStrings is searched.  The array is searched for the string 'EFlat'.  All the character elements are NULL terminated ('\0′).  This example is tricky because we are working with type char star star (char **) or double pointers.

char * notes[] = { "AFlat", "FSharp", "B", "GFlat", "D" };
char * favoriteNote = "EFlat"
 
char ** found = lsearch(&favoriteNote, notes, 5, sizeof(char *), StrCmp);
 
int StrCmp(void * vp1, void * vp2)
{
   char * s1 = * (char **) vp1;
   char * s2 = * (char **) vp2;
 
   return strcmp(s1, s2);
}

Vp1 and vp2 are cast to the types they really are which are double pointers.  After that, the value of vp1 and Vp2 are derefereced to s1 and s2.   Vp1 is of type void * so it can't be deferenced as a void * so it must be cast as what it is which is a char **.  A C standard library function can then be used to compare s1 and s2 which takes two char pointers.

The difference between functions and methods

The difference between functions and methods.  Funtions are independent of Objects.  Methods are functions that exist inside Objects.  Methods have invisible (this) pointers lying around, where functions actually have to have everything passed to it.

Generic Data Structures (Stacks)

We are going to implement a stack using ints first before a generic version will be attempted.

stack.h

typedef struct {
   int * elems;
   int logicallen;
   int alloclenth;
} stack;
 
void StackNew(stack * s);
void StackDispose(stack * s);
void StackPush(stack * s, int value);
void StackPop(stack * s);
 
stack s;

This allocates a block of memory for stack, but doesn't actually initialize the data.

StackNew(&s);

A call to StackNew receives the address of the previously allocated stack s.  StackNew initializes the actual elements in stack s.  

for(int i = 0; i < 5; i++)
{
    StackPush(&s, i); 
}

The above call pushes the numbers zero through 4 onto the stack.

StackDispose(&s); 

And finally, the stack is disposed of.  Other details need to be implemented as well, but those details were not provided in this lecture.  For example, initially the elems pointer only pointed to an array of size 4.  This array, however, gets filled up after the number '3′ is pushed onto the stack.  More memory then has to be allocated to fit the number 4.  

void StackNew(stack * s)
{
 
    s->logicallen = 0;
    s->;alloclen = 4;
    s->elems = malloc(4 * sizeof(int));
 
   assert(s->elems != NULL);
 
}

In C, malloc goes out to the heap, finds a block of memory that is 4 * sizeof(int) wide (or 16 bytes) and returns the address of that block of memory to elems.   The assert function, if evaluated to false, declares an assertion at that call (ends the program) and tells you at what line the program ended.  If malloc isn't able to find the memory on the heap, it will return NULL and the assert will be triggered.  If not caught, a segmentation fault is called, but you don't know where it was called.

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.