So here we are back again to C generics: a little late 
but better late than never 
.
but better late than never .So last time, it was about going generic about data types and we started out with stack. To start from the basics, we took up the int-specific stack and then move on to its generic avatar.
Looking back, last week we realized that we needed the following functions to access our stack
void StackNew(stk *s);void StackDispose(stk *s);void StackPush(stk *s,int data);int StackPop(stk *s);void StackDisplay(stk *s);
**I guess StackDisplay wasn’t mentionedbut for obvious reasons we do need a function to display the contentsof our stack.
Furthermore, the implementation ofStackNew() had been discussed:
void StackNew(stk *s){s->elems = (int*)malloc(s->alloclen*sizeof(int));assert(s->elems != NULL);s->loglen = 0;s->alloclen = 4;}
So moving on to our next function –StackDispose() :
void StackDispose(stk *s){free(s->elems);}
All that we did was release the memory that was reserved for us through the malloc() call. Thus we pass the pointer to the memory that was earlier assigned for our work –which we no longer need – to be released back to the system.
Simple eh? Well of course, taken for granted that free() releases the memory at s->elems. But whys->elems?? Shouldn’t it be ‘s’ itself?? We are disposing off the whole stack ??.
Well, that isn’t so. From the programming perspective, we only use free() to release that portion of memory that is allocated for us by malloc. By this rule, ‘s’definitely does not qualify to be passed to free().
StackPush() :
This is the our function of the day . It is supposed to perform the push operation on our stack. As most of us would have heard, stack is a data structure where insertion and deletion takes place only from one end – and inserting an element in a stack is said to be the act of ‘pushing’. Hence the name ‘push’operation.
. It is supposed to perform the push operation on our stack. As most of us would have heard, stack is a data structure where insertion and deletion takes place only from one end – and inserting an element in a stack is said to be the act of ‘pushing’. Hence the name ‘push’operation.This StackPush(), in addition to pushing an element to a stack, is supposed to consider the memory overflow condition, i.e. the condition when we do not have enough space to maintain our stack. In cases where the system cannot hold the data in the current location, then StackPush() should be able to find a new memory location where the new requirements are met and copy the data to that place. Finally, the old memory location must be freed. These three steps of data transfer can be carried by another function called realloc().
void* realloc(void* oldpointer,intnewsize);
Thus, on the whole, the code forStackPush() looks like this :
//————————————————————————————–
void StackPush(stk *s,int data){if(s->loglen == s->alloclen){s->alloclen += 10;s->elems = (int*)realloc(s->elems,s->alloclen*sizeof(int));assert(s->elems != NULL);}s->elems[s->loglen] = data;++(s->loglen);}
//———————————————————————————————
Precisely, the first six lines take care of the overflow condition.
if(s->loglen == s->alloclen){s->alloclen += 10;s->elems = (int*)realloc(s->elems,s->alloclen*sizeof(int));assert(s->elems != NULL);}
-
First a check is made if s->loglen is equal to s->alloclen. This is because, according to our design, alloclen know how many elements can be stored in the stack. If the count exceeds, we need a new place in the memory, which is taken care of in the second step.
-
When the amount of data exceeds the capacity, relocate our stack to a bigger memory space if the current space cannot hold our data.
-
If relocating is not possible, then display an error message.
‘s->loglen’ holds the logical length of the stack i.e. the number elements present in the stack. Say, we have 3 elements in the stack. The last element is present in elems[2]. Thus the new element has to enter elems[3] – which is why ‘data’ is assigned to s->elems[s->loglen].
Once an element is pushed in, loglen has to be updated as the stack now carries one element more.
StackPop() :int StackPop(stk *s){assert(s->loglen > 0);return (s->elems[--(s->loglen)]);}
This function pops a value from the stack. However, first a check is made to see if the given stack is already empty. Then, loglen is decremented and s->[s->loglen]is returned as it is the last element in the stack.
StackDisplay()void StackDisplay(stk *s){int i;printf(“Stack Elements :\n”);for(i = 0; i < s->loglen; ++i){printf(“%d\t”,s->elems[i]);}}
This function, as it is obvious, simply displays the members of the stack.
//————————————— code————————————————————- //
#include <stdio.h>#include <stdlib.h>#include <time.h>#include <malloc.h>#include <assert.h>typedef struct{int *elems;int loglen;int alloclen;} stk;void StackNew(stk *s);void StackDispose(stk *s);void StackPush(stk *s,int data);int StackPop(stk *s);void StackDisplay(stk *s);int main(){int i;stk s;srand(time(NULL));StackNew(&s);printf(“Generating and pushingrandom number…”);for( i = 0; i < 15; ++i)StackPush(&s,rand()%100);StackDisplay(&s);printf(“\nPoppingelements…\n”);for( i = 0; i < 15; ++i)printf(“%d\n”,StackPop(&s));StackDispose(&s);printf(“\n”);return 0;}void StackNew(stk *s){s->loglen = 0;s->alloclen = 4;s->elems = (int*)malloc(s->alloclen*sizeof(int));assert(s->elems != NULL);}void StackDispose(stk *s){free(s->elems);}void StackPush(stk *s,int data){if(s->loglen == s->alloclen){s->alloclen += 10;s->elems = (int*)realloc(s->elems,s->alloclen*sizeof(int));assert(s->elems != NULL);}s->elems[s->loglen] = data;++(s->loglen);}int StackPop(stk *s){assert(s->loglen > 0);return (s->elems[--(s->loglen)]);}void StackDisplay(stk *s){int i;printf(“\nStack Elements :\n”);for(i = 0; i < s->loglen; ++i){printf(“%d\t”,s->elems[i]);}}
Output looks sort of like this :
Moving on to generics, lets analyze the issues.
So lets think it over. What did we lose?
-
We lost the integer pointer arithmetic as we do not know what data we’d be handling.
-
We lost the size of the data we are handling.
-
Assignment operator cannot be used as void* cannot be de-referenced to give values which can be assigned to something.
-
The display function : we have to write separate functions for the different data types we use.
To tackle, pointer arithmetic we type-cast the void* to char* and then apply appropriate pointer arithmetic (which we will be seeing shortly).
The second issue is taken on by seeking and storing the size of the data beforehand.
The assignment operator is replace it by memcpy() now.
And for today’s code, we use IntStackDisplay() to output the values.
Thus, the structure now looks something like this :
typedef struct{int loglen;int alloclen;int elemsz;void *elems;} stk;
The members loglen and alloclen areobvious now that we have seen the int specific Stack. The changes we see are ‘int elemsz’ and ‘void *elems’.
void *elems, being in the sixth week of this series of C programming, you must have guessed that it will beholding the address of the data of type unknown to our structure.’int elemsz ‘ holds the size of the data type.
Looking at the function prototypes again :
void StackNew(stk *s,int sz);void StackDispose(stk *s);void StackPush(stk *s,void *val);void StackPop(stk *s,void *data);void IntStackDisplay(stk *s);
Lets see them one-by-one.
StackNew()
//——————— code———————–//
void StackNew(stk *s,int sz){s->elemsz = sz;s->loglen = 0;s->alloclen = 4;s->elems =malloc(sz*(s->alloclen));assert(s->elems != NULL);}
StackNew() essentially does the same work. Additionally it has to initialize its new data member ‘elemsz’.Note the argument ‘sz*s->alloclen’ passed to malloc. As we know,malloc takes the number of bytes to be allocated. This number is nothing but the size of the data type (‘sz’) multiplied by the number of elements the stack can store (‘alloclen’).
StackDispose()
// ———– code ——————//
void StackDispose(stk *){free(s->elems);}
This function remains the same and theres nothing more to say.
StackPush()
// ————– code ————–//
void StackPush(stk *s,void *val){void *addr;if(s->loglen == s->alloclen){s->alloclen *= 2;s->elems =realloc(s->elems,(s->elemsz*s->alloclen));assert(s->elems != NULL);}addr = (char*) s->elems +(s->loglen)*(s->elemsz);memcpy(addr,val,s->elemsz);++(s->loglen);}
Changes we see are in the calculation of the number of bytes just like we saw in StackNew(). Furthermore,we have an additional task – calculating the address where we push the value. Previously, in the int-specific case, this was taken careof by the index operator ‘[]‘. This has to be done manually now.
addr = (char*) s->elems +(s->loglen)*(s->elemsz)
In an array, containing say 5 elements(forget the entire size of the array for now), the last block happens to be four blocks away. Thus coincidentally the new element has to be inserted at the 5th block. Hence to insert the new element we need to reach the fifth block from the base address. In general,to insert the nth block we move to the nth block from the base address. ‘(s->loglen)*(s->elemsz)’ precisely calculates the fifth block. Size of one block is s->elemsz. Multiplied by the number of elements already present in the stack (which is held ins->loglen) gives the desired address.
Note that s->elems is cast to char*to enable pointer arithmetic. Reason being that pointer arithmetic cannot be done on a void* which has been repeatedly told here.
StackPop()
// ——- code ——- //
void StackPop(stk *s,void *data)
{
void *addr;
assert(s->loglen > 0);
addr = (char*) s->elems +(s->loglen-1)*(s->elemsz);
memcpy(data,addr,s->elemsz);
–(s->loglen);
}
‘addr’ is meant to temporarily hold the address we calculate – which will become clear in a moment. Then make sure than s->loglen is greater than zero : else deletion not possible.
Next comes determining the address of the last element in the stack. To reach the last element, i.e. the loglenth element, we have to move loglen-1 blocks away from the base address. This is why the product’(s->loglen-1)*(s->elemsz)’ is added to ‘s->elems’. Having calculated this, we copy the contents to ‘data’ which is later accessed in the main() to see what value is popped. Copying is achieved by memcpy(). Finally loglen is decremented. This prevents any further access to the last element. Thus the last element is as good as deleted.
IntStackDisplay() is self-explanatory –it is nothing but simple array access done using the index.
Thus, the overall code looks like this:
//—————————————————————————————————————–//
/*
Program to demonstrate a generic data type.
*/
//———————————————————– //
/*************** Header files***************************/
#include <assert.h>#include <stdio.h>#include <time.h>#include <malloc.h>#include <string.h>/*************** The generic data type*****************/typedef struct{int loglen;int alloclen;int elemsz;void *elems;} stk;
/************** Prototypes*****************************/
void StackNew(stk *s,int sz);void StackDispose(stk *s);void StackPush(stk *s,void *val);void StackPop(stk *s,void *data);void IntStackDisplay(stk *s);
/**** main() ****/
int main(){int i,val,rnd_num;stk s;srand(time(NULL)); //Initializing the random number generator.StackNew(&s,sizeof(int));printf(“Generating and pushingrandom number…”);for( i = 0; i < 15; ++i){rnd_num = rand() % 100;StackPush(&s,&rnd_num);}printf(“\n”);IntStackDisplay(&s);printf(“\nPoppingelements…\n”);for( i = 0; i < 15; ++i){StackPop(&s,&val);printf(“%d\n”,val);}StackDispose(&s);printf(“\n”);return 0;}
/****************** Functiondefinitions ******************/
void StackNew(stk *s,int sz){s->elemsz = sz;s->loglen = 0;s->alloclen = 4;s->elems =malloc(sz*(s->alloclen));assert(s->elems != NULL);}void StackDispose(stk *s){free(s->elems);}void StackPush(stk *s,void *val){void *addr;if(s->loglen == s->alloclen){s->alloclen *= 2;s->elems =realloc(s->elems,(s->elemsz*s->alloclen));assert(s->elems != NULL);}addr = (char*) s->elems +(s->loglen)*(s->elemsz);memcpy(addr,val,s->elemsz);++(s->loglen);}void StackPop(stk *s,void *data){void *addr;assert(s->loglen > 0);addr = (char*) s->elems +(s->loglen-1)*(s->elemsz);memcpy(data,addr,s->elemsz);–(s->loglen);}void IntStackDisplay(stk *s){int i;printf(“\nStack Elements :\n”);for(i = 0; i < s->loglen; ++i){printf(“%d\t”,*((int*)s->elems+ i));}}
//—————————————- end of code——————————————————//
And the output :
Next week, we’ll use this genericstack, but, to store a collection of strings. This can be a littletricky as we would handling char**. There’s more coming so stay withus. Have a great weekend.
