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.