Week 5 – Introduction to generic functions in C part 2

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 */

}

#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);

int StrCmp(void*vp1,void *vp2)

{

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

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

return strcmp(s1,s2);

}

char * s1= (char *)vp1;

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

return strcmp(s1,s2);

#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;

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);