Week 5 – Introduction to generic functions in C part 2

this is the header for our linear search

now lets get to the mystery argument we had left out on closer evaluation we see that the argument is actually a function with the aruments as two void * this arguments is used to compare two elements of any type and it returns 0 if they match or some other integer otherwise

if (cmpfn(key,elemaddr)==0)

return elemaddr;

now lets consider an example

int array[] ={4,2,3,7,11,6};

int size =6 ;

now if i have to search for a number say 7 i have to do the following

int number =7 ;

now i have to set aside space for the key element i am interested in as i have to pass that as the very first element to the function

array is represented in the following way

<----elemsize--->

4

2

3

7

11

6

↑ ↑

base address key address

now lets see how to call lsearch for this example

int *found = lsearch(&number,array,6,sizeof(int),int cmpfn);

if (found==NULL)

dint get number

else

number was found

we have to define the int cmpfn function before we can use it so lets write the cmpfn function

now the cmp function has to take two void * and return an integer (prototype) , this is the fifth parameter in our lsearch function

you may think cant i just write a fucntion taking two int * and returning an int ... the answer is you could since all pointers are of same size .. you would pass them as int * and they would be absorbed as void * ... but its better to write the comparison function to match that prototype exatly

my function take two pointers ... one is the key which always remains constant and the other is the element address which keeps changing unless a match is found

i also have to return a 0 or any other integer depending whether there is a match or not

now since im writing the code i know that the two void * are really int * .. therefore i can reinterpret them to be the int * they really are

int intcmp(void * elem1,void *elem2)

{

int *ip1 =elem1;

int *ip2=elem 2;

return (*ip1 -*ip2) /* returns the difference between element if zero ... its a match */

}

here is the full program :

#include

#include

#include

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

{

int i;

for(i=0;i

{

void *elemaddr=(char*)base+i*elemsize;

if(cmpfn(key,elemaddr)==0)

return elemaddr;

}}

int cmpfn(void *elem1,void *elem2)

{

int *ip1=elem1;

int *ip2=elem2;

return(*ip1-*ip2);

}

main()

{

int array[]={4,2,3,7,11,6};

int size=6;

int number =7;

int *found=lsearch(&number,array,6,sizeof(int),cmpfn);

if(found==NULL)

printf("we dint get the number\n");

else

printf("we found the number\n");

}

But there are some plus points like this method is very fast, you use one copy of lsearch to do all your searching .. the template approach you get one instance of that lsearch algorithm for every datatype you search for

this method isnt that difficult to understand while searching for integers but its starts to get a lot more complicated when we start lsearching an array of c strings so you will have an array of char * and well have to search for a specific char * to see whether you have a match or not

consider the following code

char *letters [] ={“a”,”f”,”b”,”g”,”d”};

char *favletter =”e”;

lsearch(&favletter,letters,5,sizeof(char*),StrCmp);

this is array is represents in the memory as follows

↓ ↓ ↓ ↓ ↓ ↓

base pointin to a pointing to f pointing to b pointing to g pointing to d

address

in the function we pass the address of the favletter , we pass the letters array which is the base address of the first element ,no of elements ,size of elements which is char * (why char *) .. so that we know the space between the elements,and StrCmp .. the compare function which we have to write

the reason we are passing the address of favletter rather than the value its self .. is that we want the key to be of the same type as of as all the pointers that are computed manually in the lsearch

this is beacause though elemenst are passed as char * we know that they are acutally char** that is they are two hops away from the element .. and it would make our life easier if we passed the key as char** so that there will be some symmetry in the code

now lets write the StrCmp function

int StrCmp(void*vp1,void *vp2)

{

char * s1= * (char **)vp1;

char * s2= * (char **)vp2;

return strcmp(s1,s2);

}

the first argument is &favletter and the other argument is the function to which it has to be compared with ...now the function body look really very confusing the first time you see it..but if you examine it carefully youll find that we are casting vp1 and vp2 to be the type we know they are ..

they are two hops away from going to charecters (that is why we use char** instead of char*) after that we dereference them once so that the address of the key and the present element are sitting in s1 and s2 ... we do this because there a function in c library which compares character arrays by passing the address of the pointer to the first character this function returns a zero for match otherwise the difference between the ascii key values

lets consider the same function and if we forget to pass &favletter and instead pass favletter

our compare function still interprets its as a char** not char* it would set theit address of 'e' to be char** instead of char*

it would still derefrence it but would now represent 'e' to be a char * which actually is a char ,and it would pass that to strcmp which will not be good as it will jump to the 'e' mystery address and assume there are characters there

now suppose u dont want to deal with a double dereference when u dont need to .you can wanna pass just favletter as your argument

the body of the function gets changed

char * s1= (char *)vp1;

char * s2= * (char **)vp2;

return strcmp(s1,s2);

we can recognise that the first argument is 1 hop away from the characters and the second one is two hops away

the way the function was written first is the way its usually written due to the symmetry of dealing with the same incoming datatype

we can write it anyway .. both methods work

this is the full program :

#include

#include

#include

int StrCmp(void *vp1,void *vp2)

{

char *s1=*(char**)vp1;

char *s2=*(char**)vp2;

return (strcmp(s1,s2));

}

void lsearch(void *key,void*base,int n,int elemsize,int(StrCmp)(void*,void*))

{

int i;

for(i=0;i

{

void *elemaddr=(char*)base+i*elemsize;

if(StrCmp(key,elemaddr)==0)

{

printf("element has a match\n");

break ;

}

}

printf("element has no match\n");

}

main()

{

char *letters[]={"a","f","b","g","d"};

char *favletter="e";

lsearch(&favletter,letters,5,sizeof(char*),StrCmp);

}

now that we have a pretty good idea about genric code ... lets turn our attention to implementing a stack datastructure

well start by making it int specify just so that we have a clear idea how the generic should be implemented

well be implementing everything in int so there is no void* business yet

well try to imitate the way we use stacks in c++ as we are more use to it

as there is no class keyword in C well be using struct

and we have to public and no private

well try to come as close as we can to implementing a class using C code

typedef struct{

int *elems;

int logicallen;

int alloclength;

}stacks;

since we are trying to implement it as a class ... lets not manipulate the element inside stacks diresctly

well try using function to manipulate them

we want to write a constructor function, destructor function, and then we want to write an is empty function, a pop function, a push function, things like that.

So here’s the prototype of the first thing I’m interested in:

void stacknew (stack *s);

void stackdispose(stack *s);

void stackpush(stack *s,int value);

int stackpop(stack *s);

♠in stack new all we are gonna do is pass in or expect the address of some stack that’s already been allocated.

♠we also have this function stack dispose. we want to identify the address of the stack structure that should be disposed. This is gonna be a dynamically allocated array that’s not perfectly sized. So we want to keep track of how much space I have (logicallen) and how much of it I’m using (alloclengh)

♠stackpush and stackpop is used to push and pop elements

lets see a picture of what happens when we declare a element of stack

stack s ;

?

?

?

That means that this, as a picture, is gonna be set aside. And you know, based on what we’ve talked about in the past, that it’s 12 bytes

if the elems field is at the bottom, and that the two integers are stacked on top of it. But as far as the declaration is concerned, it doesn’t actually clear these out, or zero them out like Java does, it just inherits whatever bits happen to reside in the 12 bytes that are

overlaid by this new variable.

stacknew(&s) It’s when we call stack new that we pass in the address of this. Why does that work, and why

do we know it can work?

Because we identify the location of my question-mark-holding

stack pass into a block of code that we’re gonna allow to actually manipulate these three

fields. And I’m going to logically do the following:

I’m gonna take the raw space, that’s set up this way. I’m gonna set it’s length to be zero.

I’m gonna make space for four elements. And I’m gonna store the address of a

dynamically allocated array of integers, where these question marks are right here, and

initialize the things. That means that that number can be used not only to store

the effective depth of the stack, but it can also identify the index where I’d like to place

the next integer to be pushed.

So because I’m pre-allocating space for four elements, that means that this is a function.

It’s gonna be able to run very, very quickly for the very first calls. And it’s only when I

actually push a fifth element, that I detect that allocated space has been saturated, that I

have to recover and panic a little bit and say, oh, I have to put these things somewhere

else. That it’ll actually go and allocate another array that’s twice as big, and move

everything over, and then carry on as if the array were of length 8 instead of 4 all along.

You can imagine that when we go generic this is still gonna be an array, just like the

arrays passed to lsearch are, but we’re gonna have to manually compute the

insertion index to house the next push call, or to accommodate the next push call, and do

the same thing for pop. we do this

stacknew(&s)

{

for(int i=o;i<5;i++)

stackpush(&s,i);

}

So what has to happen is that on the very last iteration here I have

to do that little panic thing, where I say, I don’t have space for the 4. So I have to go and

allocate space for everything.

So I’m gonna use this doubling strategy, where I’ve gotta set aside space for eight

elements. I copy over all the data that was already here. I free this. Get this to point to this

space as if it were the original figure I’ve allocated. Forget about that smaller house, I’ve

moved into a bigger house and I hated the older house. And then I can finally put down

the 4 and make this a 5 and make this an 8. So that’s the generic algorithm we’re gonna

be following for this code

I want to implement stack new. So take a stack address, just like that, recognize that s is a

local variable. It has to make the assumption that it’s pointing to this 12-byte figure

Void stacknew(stack *s)

{

s->logicallen=0;

s->allocelem=4;

s->elems=malloc(4*size0f(int));

assert(s->elems !=num);

So what I want to do is I want to go in. I want to s arrow logical n = zero. I want to do s

arrow alloc len = 4, and allocate dynamic memeory using malloc for elems

There is this function called assert. It’s actually

not a function it’s actually a macro. There’s this thing you can invoke called assert in the

code, which takes a boolean value, takes something that functions as a test. It effectively

becomes a no op if this test is true, but if this is false assert actually ends the program and

tells you what line the program ended at. It tells you the file number containing and the

line number of the assert that broke.

The idea here is that you want to assert the truth of some condition, or assert that some

condition is being met, before you carry forward. Because if I don’t put this here and

malloc failed, it couldn’t find 16 bytes (That wouldn’t happen but just assume it could)

and it returned null, you don’t want to allow the program to run for 44 more seconds for

it to crash because you de-referenced a null pointer somewhere.

So when we come back next sunday we'll finish the rest of the three functions and then we will go

generic

First of all Download firefox 8 from this link
which is a tar-ball.

Now I have a tricky way of installing this on my system. ( There are a lot of better ways, this is ONLY one way of them ).

Extract the tar ball in your home directory ( or others if you wish ).
Open a terminal and type,

cd /path/to/your/firefoxdirecory

for eg:

cd /home/linuxcandy/firefox

then make the firefox executable by giving this command:

sudo chmod +x firefox

open the folder and you can see "firefox" executable there.
Now click on that executable. There you go.. you have new firefox.







Ever wonder whats new in ff8 ?

• Add-ons installed by third party programs are now disabled by default
• Added a one-time add-on selection dialog to manage previously installed add-ons
• Added Twitter to the search bar for select locales. Additional locale support will be added in the future
• Added a preference to load tabs on demand, improving start-up time when windows are restored
• Improved performance and memory handling when using <audio> and <video> elements
• Added CORS support for cross-domain textures in WebGL
• Added support for HTML5 context menus
• Added support for insertAdjacentHTML
• Improved CSS hyphen support for many languages
• Improved WebSocket support
• Fixed several stability issues
• Fixed several security issues

Previously we had seen the implementation of swap function, which however was specific to int data
type. Today we make a few points on that on introduce ourselves to generic functions in C. Generic
functions, which we'll be writing shortly, are analogous to the templates that we see in C++. We'll also
chalk out the major differences, pros and cons of generic functions.

We are quite familiar with the following code:

void swap(int* aptr,int* bptr)
{
int tmp;
tmp = *aptr;
aptr = *bptr;
*bptr = tmp;
}

Needless to say, the function swap(), swaps the contents of the two variables passed. This is done by
passing the addresses of the two variables and assigning each others' values by the usual swapping
algorithm using the temporary 'tmp' variable.

So to make an attempt to write a generic swap(), we need to understand this : swap() must work for any
type of data we pass. For this purpose, we use void pointers.
Void pointers (void*) are pointers that can point to any addresses of data type.

Thus,

int a;
float b;
double c;
void *vptr = &a;
vptr = &b;
vptr = &c;

... are all perfectly legal statements.
The versatility of void* makes it useful in writing generic functions.
So coming back to writing the generic swap() function...


Attempting to write the generic swap(), a natural tendency would be...

void gswap(void *aptr,void *bptr)

{

void tmp;

tmp = *aptr;

aptr = *bptr;

*bptr = tmp;

}

However, this code simply wouldn't work for two reasons – one obvious and one subtle.

• The obvious reason would be that no variable can be declared as void.
• The other, more subtle, reason is that void pointers cannot be deference!

Lets go one by one.
Our first problem of storing the unknown data type : To solve this, we ask for the size of the data type.
Knowing the size of the data type, we can ask for that many bytes of memory from the heap. So the question is which data type do we use to store the unknown data? The best answer would be char. This is because char just take one byte in the memory and thus its pointers arithmetic are much simpler than any other data type. So how do we store the unknown variable using char which can only hold one byte of data? We don't use just one char variable but an array of char. The number of elements of the array would depend on the size of the unknown data.
Our second problem of differencing the void pointer : Well, in the first place, we wont be doing the usual assignment using ' = ' .This is because the tmp variable, as we discussed, would be an array we simply cannot do an assignment to an array. Hence, we use the memcpy() function from string.h

Sticking to our topic, it is enough to know that the function can take two void* and an integer. (An integer could be passed in place ofsize_t). Note that memcpy() doesn't look for any special character that would mark the end of array (like strcpy() does). It simply copies the number of bytes specified in numfrom
source to destination.

Hence our gswap() looks like (including the complete code) : -

//------------------------------------- Code--------------------------------------------------- //

#include <stdio.h>
#include <malloc.h>
#include <string.h>

void swap(void *a,void *b,int sz);

int main()

{

int a = 44;

int b = 5;

int *aptr = &a;

int *bptr = &b;

printf(”Beforeswapping...\na = %d\nb = %d”,a,b);swap(aptr,bptr,sizeof(int));

printf(”\nAfterswapping...\na = %d\nb = %d”,a,b);

return 0;

}

void swap(void *a,void *b,int sz)

{

char *buf =(char*)malloc(sz);

memcpy(buf,a,sz);

memcpy(a,b,sz);

memcpy(b,buf,sz);

}

//---------------------------------------------------------------------------------------------------------//

The advantage generic C functions have over C++ templates is seen during compilation of the code.
In C++, when templates are compiled, various copies of function are created depending upon the number of data types using the template. Each copy differs from the other only in the aspect of handling the data – the code more or less remains the same.
To put it simply, consider that we used a template to handle anint, float and a double in our C++ code. The compiler would create a duplicate copy of the function, each for int, float and double. The copy handling int would only differ in handling the data – rest of the code doesn't change.
This wouldn't matter much when its just a matter of few data types. However, in a huge a code-base having 30-40 data types (structures,classes etc. ) the issue can get serious as the size of the executable would simply magnify.


Shortcomings of generic function are that generic functions are run-time error prone. Its is possible that while compiling the code may not show any errors but the output isn't the desired result.Generic functions can lead to buggy codes if care is not taken.

#include<stdio.h>

#include<string.h>

voidswap(void *a,void *b,int sz)

{

char*buf = (char*)malloc(sz);

memcpy(buf,a,sz);

memcpy(a,b,sz);

memcpy(b,buf,sz);

}

intmain()

{

char*husband = strdup("Fred");

char*wife = strdup("Wilma");

printf("Before swapping...\n");

printf("Husband : %s\n",husband);

printf("Wife : %s\n",wife);

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

printf("After swapping...\n");

printf("Husband : %s\n",husband);

printf("Wife : %s\n",wife);

return 0;

}

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

//---------------------------------------Code -----------------------------------//

#include<malloc.h>

#include<stdio.h>

#include<string.h>

intlsearch(void *arr,int n,void *ele,int Dsz)

{

inti;

for(i= 0; i < n; ++i)

{

void *addr = (char*)arr+(i*Dsz);

if(memcmp(addr,ele,Dsz) == 0 )

{

return i;

}

}

return-1;

}

intmain()

{

intno,i,pos;

float*Arr = NULL,key;

printf("Enter the number of elements youwant : ");

scanf("%d",&no);

Arr= (float*) malloc(sizeof(float)*no);

printf("Enter the %d elements : \n",no);

for(i= 0; i < no; ++i)

{

printf("Element %d : ",i);

scanf("%f",&Arr[i]);

}

printf("Enter the number element tosearched : ");

scanf("%f",&key);

pos= lsearch(Arr,no,&key,sizeof(float));

if(pos!= -1)

printf("Element %f found at position(starting from zero) %d",key,pos);

else

printf("Element not found!");

printf("\n");

return0;

}

Theprimitive linear search algorithm used to look like this:

for(i=0;i<n;++i)

{

if(arr[i]== ele)

returni;

}

return-1;

}

int memcmp ( const void * ptr1, const void * ptr2, size_t num );

address= (char*)arr + Dsz*i;