[go: up one dir, main page]
Scribd
Upload
51 views11 pages

Generic Functions, Generic Data Structures

This document discusses generic functions and data structures in C. It covers function pointers, generic sorting and searching routines like qsort and bsearch, comparator functions for different data types, useful memory functions like memcmp, memcpy and memmove, and an example of a generic stack implementation with functions to initialize, free, check if empty, and push to and pop from the stack. It notes some implementation details and things to be careful of like pointers within stack elements.

Uploaded by

SuyashBhutada
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
51 views11 pages

Generic Functions, Generic Data Structures

This document discusses generic functions and data structures in C. It covers function pointers, generic sorting and searching routines like qsort and bsearch, comparator functions for different data types, useful memory functions like memcmp, memcpy and memmove, and an example of a generic stack implementation with functions to initialize, free, check if empty, and push to and pop from the stack. It notes some implementation details and things to be careful of like pointers within stack elements.

Uploaded by

SuyashBhutada
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 11

Generic functions, generic data structures

Data and File Structures Laboratory

http://www.isical.ac.in/~dfslab/2018/index.html

DFS Lab (ISI) Generic functions, generic data structures 1 / 10


Function pointers

Declaring function pointers


<return type> (* <function name>) ( <parameter list> )

These brackets are important!


Example:
int *aFunction(int), *(*aFunctionPointer)(int);

Using function pointers


(*f)(...)

Setting function pointer variables / passing function pointers as


arguments: simply use the name of the function
Example:
aFunctionPointer = aFunction;

DFS Lab (ISI) Generic functions, generic data structures 2 / 10


Generic sort/search routines

#include <stdlib.h>

Sorting
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));

Searching
void *bsearch(const void *key, const void *base,
size_t nmemb, size_t size,
int (*compar)(const void *, const void *));

DFS Lab (ISI) Generic functions, generic data structures 3 / 10


Comparator routine: examples

int compare_int (void *elem1, void *elem2)


{
int *ip1 = elem1;
int *ip2 = elem2;
/* Or more explicitly:
int *ip1 = *((int *) elem1);
int *ip2 = *((int *) elem2);
*/
return *ip1 - *ip2;
}

int compare_strings (void *elem1, void *elem2)


{
char **s1 = elem1; // or *((char **) elem1);
char **s2 = elem2;
return strcmp (*s1, *s2);
}

DFS Lab (ISI) Generic functions, generic data structures 4 / 10


Generics: useful functions

#include <string.h>

int memcmp(const void *s1, const void *s2, size_t n);


void *memcpy(void *dest, const void *src, size_t n);
void *memmove(void *dest, const void *src, size_t n);

memcmp(): compares the first n bytes (each interpreted as


unsigned char) of the memory areas s1 and s2
memcpy(): copies n bytes from src to dest (memory areas must not
overlap)
memmove(): copies n bytes from src to dest (memory areas may
overlap)

DFS Lab (ISI) Generic functions, generic data structures 5 / 10


Generic stacks

1 #ifndef _GSTACK_
2 #define _GSTACK_
3
4 typedef struct {
5 void *elements;
6 size_t element_size, num_elements, max_elements;
7 } STACK;
8
9 STACK newStack(int element_size);
10 // OR
11 void initStack (STACK *s, int element_size);
12 void freeStack(STACK *s);
13 bool isEmpty(const STACK *s);
14 void push(STACK *s, const void *eptr);
15 void pop(STACK *s, void *eptr);
16
17 #endif // _GSTACK_

DFS Lab (ISI) Generic functions, generic data structures 6 / 10


Implementation notes

Choose a default stack size initially (max elements);


realloc() to double the current size as needed
Use memcpy() for push() and pop()
Example:
stackElementAddress = (char *) s->elements + s->num_elements *
s->element_size;
memcpy(stackElementAddress, argument, s->element_size); // for
push()
memcpy(argument, stackElementAddress, s->element_size); // for
pop()

DFS Lab (ISI) Generic functions, generic data structures 7 / 10


Things to be careful about

What if the stack element contains pointers?

DFS Lab (ISI) Generic functions, generic data structures 8 / 10


Things to be careful about

What if the stack element contains pointers?


Use indices instead of pointers to array elements if the array may
be reallocated

DFS Lab (ISI) Generic functions, generic data structures 8 / 10


Review question

Compile and run function-pointers.c. Explain the output.

DFS Lab (ISI) Generic functions, generic data structures 9 / 10


Programming question

Complete the implementation of the functions in the header file. Test it


using different types (e.g., int, float and strings).

DFS Lab (ISI) Generic functions, generic data structures 10 / 10

You might also like