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

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

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

void gswap(void *aptr,void *bptr)

{

void tmp;

tmp = *aptr;

aptr = *bptr;

*bptr = tmp;

}

• 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!

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

}

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

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

struct fraction

{

int num;

int denom;

};

pi.num = 22;

pi.denom = 7;

Just assigning values. Now,

((struct fraction*)&(pi.denom)) -> num = 12;

Confused?! :D

Well what happens is as follows:

 address of pi.denom is sought

 &pi.denom which is an integer pointer, is type-cast to a fraction pointer.

 Now the num field of this pointer is assigned the 12. Question is where is this num field?

To explain this, we need to recollect what happened when a float pointer was converted to int, which is what we did last week. The contents of the memory remain the same. But the compiler thinks of the memory location as an int.Same thing happens here. The compiler thinks of &pi.denom to be the starting address of a structure (even if it really isn't).

Hence if we display pi.denom we get 12.

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

#include

struct fraction

{

int num;

int denom;

};

int main()

{

struct fraction pi;

pi.num = 22;

pi.denom = 7;

printf("Numerator : %d",pi.num);

printf("\nDenominator : %d",pi.denom);

((struct fraction*)&(pi.denom))->num = 12;

printf("\nAfter manipulating with memory...\n");

printf("Numerator : %d",pi.num);

printf("\nDenominator : %d",pi.denom);

return 0;

}

Moving on to the array of structures, consider the following structure;

struct Students

{

char *name;

char SUID[8];

int no_of_units;

};

Memory reserved when a variable is declared would look something like this :

Note that we read the contents in these sort of diagrams from left to right, bottom to top.

Array of such structures, in the memory would look like the following:

struct Student pupils[4];

Consider this:

pupils[0].no_of_units = 21;

This simply puts the value 21 in pupil[0] 's 'no_of_units' field.

Likewise,

pupils[2].name = strdup("Adam");

Here strdup() is a function defined in that it dynamically allocates the required memory

for the string and passes the pointer to the location where the memory was allocated. This pointer is stored in name field of pupils[0].

Things get tricky now:

pupils[3].name = pupils[0].SUID + 6;

This would pupils[3].name to point to the memory location 6 bytes away from

pupils[0].SUID. Thus,

strcpy(pupils[0].SUID,"1234567");

pupils[0].no_of_units = 0;

printf("%s",pupils[3].name);

Output : 7

Note that strcpy() does not do any kind of bounds-checking - it goes on copying bytes until it

encounters a '\0' character. Hence,

strcpy(pupils[0].SUID,"12345678");

pupils[0].no_of_units = 0;

printf("%s",pupils[3].name);

... simply displays 78. Note that pupils[0].no_of_units is assigned 0 so that it acts as

the '\0' character.( '\0' has a ASCII code of 0). Else there could be segmentation fault on

some systems with all sorts of junk values being displayed on the screen!

Extending this further,

strcpy(pupils[0].SUID,"12345678");

pupils[0].no_of_units = 65;

printf("%s",pupils[3].name);

would surprisingly display 78A.

// ---------------------------------- Complete Code ------------------------------------ //

#include

#include

struct Student

{

char *name;

char SUID[8];

int no_of_units;

};

int main()

{

struct Student pupils[4];

pupils[3].name = pupils[0].SUID + 6;

strcpy(pupils[0].SUID,"12345678");

pupils[0].no_of_units = 65;

printf("%s",pupils[3].name);

return 0;

}

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

It has become apt to make a small point about strings in C.

Consider the following code:

#include

int main()

{

char name[] = {"Free and Open Source Software"};

printf("%s",&name[5]);

return 0;

}

Thus printf() function was lead into believing that the string started from the letter 'a'. This code makes one point clear: all the functions that deal with strings treat the given char pointer as the base address of the first character of the string ( regardless of the the bytes before the specified address) and treat the rest of the memory till the null character '\0' as the string. This '\0' character is actually what distinguishes an array of characters from strings.

Having discussed all the memory mechanics of the various data types, we are now in a position to write generic functions. Generic functions are functions that can handle any data type(Just like a template does in C++). A detailed account generic functions are will be taken care of next week.

We start off with the swap() function to swap two integers and the code (as most of us would know) is

as below:

void swap(int *aptr,int *bptr)

{

int temp;

temp = *aptr;

*aptr = *bptr;

*bptr = temp;

}

We see this function handles with integer data-types ( thus being int specific). Our aim is to write avgeneric swap() function - a function that can swap values of two memory locations regardless of what the data-types are. First of all lets see what happens in this function.

This function basically swaps the memory contents using their addresses. This is mandatory as there is no way out. (At least at this level of programming!). Using the memory address, we manipulate the individual variables. Swapping thus happens in the following 3 steps;

• contents of memory location pointed by aptr ( which contains address of the first variable

passed) are copied to a temporary variable temp.

• memory location pointed by aptr are over written with contents of memory location pointed

by bptr;

• contents of memory pointed bptr are replaced with value of temp ( which originally had

contents of first memory location)

Thus using the memory addresses we swap the contents of the memory.

Using all this as the background, next week we see how a generic function will be written for this int specific swap() function. And not just this, but grab some fundamentals, the do-and-don'ts of generic functions. So stay tuned!