Lecture 4

Review

Pointers
Void pointers
Function pointers

1
Review:Pointers

• pointers: int x; int∗ p=&x;

• pointers to pointer: int x; int∗ p=&x;int∗∗ pp=&p;
• Array of pointers: char∗ names[]={"abba","u2"};
• Multidimensional arrays: int x [20][20];

1
Review

Pointers
Void pointers
Function pointers

5
Void pointers

• C does not allow us to declare and use void variables.

• void can be used only as return type or parameter of a
function.
• C allows void pointers
• Question: What are some scenarios where you want to
pass void pointers?
• void pointers can be used to point to any data type
• int x; void∗ p=&x; /∗points to int ∗/
• float f ;void∗ p=&f; /∗points to float ∗/
• void pointers cannot be dereferenced. The pointers should
always be cast before dereferencing.
void∗ p; printf ("%d",∗p); /∗ invalid ∗/
void∗ p; int ∗px=(int∗)p; printf ("%d",∗px); /∗valid ∗/

5
Function pointers

• In some programming languages, functions are first class

variables (can be passed to functions, returned from
functions etc.).
• In C, function itself is not a variable. But it is possible to
declare pointer to functions.
• Question: What are some scenarios where you want to
pass pointers to functions?
• Declaration examples:
• int (∗fp )( int ) /∗notice the () ∗/
• int (∗fp )( void∗,void∗)
• Function pointers can be assigned, pass to and from
functions, placed in arrays etc.

6
Callbacks

Definition: Callback is a piece of executable code passed to

functions. In C, callbacks are implemented by passing function
pointers.
Example:
void qsort(void∗ arr, int num,int size, int (∗fp )( void∗ pa,void∗pb))
• qsort() function from the standard library can be sort an
array of any datatype.
• Question: How does it do that? callbacks.
• qsort() calls a function whenever a comparison needs to
be done.
• The function takes two arguments and returns (<0,0,>0)
depending on the relative order of the two items.

7
Callback (cont.)

int arr []={10 ,9 ,8 ,1 ,2 ,3 ,5};

/∗ callback ∗/
i n t asc ( void ∗ pa , void ∗ pb )
{
r e t u r n ( ∗ ( i n t ∗ ) pa − ∗ ( i n t ∗ ) pb ) ;
}
/∗ callback ∗/
i n t desc ( void ∗ pa , void ∗ pb )
{
r e t u r n ( ∗ ( i n t ∗ ) pb − ∗ ( i n t ∗ ) pa ) ;
}
/ ∗ s o r t i n ascending o r d e r ∗ /
q s o r t ( a r r , s i z e o f ( a r r ) / s i z e o f ( i n t ) , s i z e o f ( i n t ) , asc ) ;
/ ∗ s o r t i n descending o r d e r ∗ /
q s o r t ( a r r , s i z e o f ( a r r ) / s i z e o f ( i n t ) , s i z e o f ( i n t ) , desc ) ;

8
Callback (cont.)
Consider a linked list with nodes defined as follows:
s t r u c t node {
i n t data ;
s t r u c t node∗ n e x t ;
};
Also consider the function ’apply’ defined as follows:
void a p p l y ( s t r u c t node∗ phead ,
void ( ∗ f p ) ( void ∗ , void ∗ ) ,
void ∗ arg ) / ∗ o n l y f p has t o be named ∗ /
{
s t r u c t node∗ p=phead ;
while ( p ! =NULL )
{
f p ( p , arg ) ; / ∗ can a l s o use ( ∗ f p ) ( p , arg ) ∗ /
p=p−>n e x t ;
}
}
9
Callback (cont.)

Iterating:
s t r u c t node∗ phead ;
/ ∗ p o p u l a t e somewhere ∗ /
void p r i n t ( void ∗ p , void ∗ arg )
{
s t r u c t node∗ np =( s t r u c t node ∗ ) p ;
p r i n t f ( "%d " , np−>data ) ;
}
a p p l y ( phead , p r i n t , NULL ) ;

10
Callback (cont.)
Counting nodes:

void d o t o t a l ( void ∗ p , void ∗ arg )

{
s t r u c t node∗ np =( s t r u c t node ∗ ) p ;
int ∗ ptotal =( i n t ∗ ) arg ;
∗ p t o t a l += np−>data ;
}
i n t t o t a l =0;
a p p l y ( phead , d o t o t a l ,& t o t a l ) ;

11
Array of function pointers
Example:Consider the case where different functions are called
based on a value.
enum TYPE{SQUARE, RECT, CIRCILE ,POLYGON } ;
s t r u c t shape {
f l o a t params [MAX ] ;
enum TYPE t y p e ;
};
void draw ( s t r u c t shape∗ ps )
{
switch ( ps−>t y p e )
{
case SQUARE:
draw_square ( ps ) ; break ;
case RECT:
d r a w _ r e c t ( ps ) ; break ;
...
}
}
12
Array of function pointers

The same can be done using an array of function pointers

instead.
void ( ∗ f p [ 4 ] ) ( s t r u c t shape∗ ps )=
{& draw_square ,& draw_rec ,& d r a w _ c i r c l e ,& draw_poly } ;
typedef void ( ∗ f p ) ( s t r u c t shape∗ ps ) drawfn ;
drawfn f p [ 4 ] =
{& draw_square ,& draw_rec ,& d r a w _ c i r c l e ,& draw_poly } ;
void draw ( s t r u c t shape∗ ps )
{
( ∗ f p [ ps−>t y p e ] ) ( ps ) ; / ∗ c a l l t h e c o r r e c t f u n c t i o n ∗ /
}

13
Review

Using External Libraries

Symbols and Linkage
Static vs. Dynamic Linkage
Linking External Libraries
Symbol Resolution Issues

Creating Libraries

1
Review: Void pointers

• Void pointer – points to any data type:

int x; void ∗ px = &x; /∗ implicit cast to (void ∗) ∗/
float f ; void ∗ pf = &f;
• Cannot be dereferenced directly; void pointers must be
cast prior to dereferencing:
p r i n t f ( "%d %f\n" , ∗ ( i n t ∗ ) px , ∗ ( f l o a t ∗ ) p f ) ;

1
Review: Function pointers

• Functions not variables, but also reside in memory (i.e.

have an address) – we can take a pointer to a function
• Function pointer declaration:
int (∗cmp)(void ∗, void ∗);
• Can be treated like any other pointer
• No need to use & operator (but you can)
• Similarly, no need to use * operator (but you can)

2
Review: Function pointers

i n t strcmp_wrapper ( void ∗ pa , void ∗ pb ) {

r e t u r n strcmp ( ( const char ∗ ) pa , ( const char ∗ ) pb ) ;
}

• Can assign to a function pointer:

int (∗fp )( void ∗, void ∗) = strcmp_wrapper; or
int (∗fp )( void ∗, void ∗) = &strcmp_wrapper;
• Can call from function pointer: (str1 and str2 are
strings)
int ret = fp( str1 , str2 ); or
int ret = (∗fp )( str1 , str2 );

3
Review

Using External Libraries

Symbols and Linkage
Static vs. Dynamic Linkage
Linking External Libraries
Symbol Resolution Issues

Creating Libraries

5
Symbols and libraries

• External libraries provide a wealth of functionality –

example: C standard library
• Programs access libraries’ functions and variables via
identifiers known as symbols
• Header file declarations/prototypes mapped to symbols at
compile time
• Symbols linked to definitions in external libraries during
linking
• Our own program produces symbols, too

5
Functions and variables as symbols

• Consider the simple hello world program written below:

# include < s t d i o . h>

const char msg [ ] = "Hello, world." ;

i n t main ( void ) {
p u t s ( msg ) ;
return 0;
}

• What variables and functions are declared globally?

6
Functions and variables as symbols

• Consider the simple hello world program written below:

# include < s t d i o . h>

const char msg [ ] = "Hello, world." ;

i n t main ( void ) {
p u t s ( msg ) ;
return 0;
}

• What variables and functions are declared globally?

msg, main(), puts(), others in stdio.h

6
Functions and variables as symbols

• Let’s look at the symbols in the compiled file hello.o:

1
athena% nm hello.o
• Output:
0000000000000000 T main
0000000000000000 R msg
U puts
• ’T’ – (text) code; ’R’ – read-only memory; ’U’ - undefined
symbol
• Addresses all zero before linking; symbols not allocated
memory yet
• Undefined symbols are defined externally, resolved during
linking
1
.

8
Functions and variables as symbols

• Why aren’t symbols listed for other declarations in

stdio.h?
• Compiler doesn’t bother creating symbols for unused
function prototypes (saves space)
• What happens when we link?
athena%1 gcc -Wall hello.o -o hello
• Memory allocated for defined symbols
• Undefined symbols located in external libraries (like libc
for C standard library)

9
Functions and variables as symbols

• Let’s look at the symbols now:

athena%1 nm hello
• Output:
(other default symbols)
..
.
0000000000400524 T main
000000000040062c R msg
U puts@@GLIBC_2.2.5
• Addresses for static (allocated at compile time) symbols
• Symbol puts located in shared library GLIBC_2.2.5 (GNU
C standard library)
• Shared symbol puts not assigned memory until run time
1

10
Static and dynamic linkage

• Functions, global variables must be allocated memory

before use
• Can allocate at compile time (static) or at run time (shared)
• Advantages/disadvantages to both
• Symbols in same file, other .o files, or static libraries
(archives, .a files) – static linkage
• Symbols in shared libraries (.so files) – dynamic linkage
• gcc links against shared libraries by default, can force
static linkage using -static flag

11
Static linkage

• What happens if we statically link against the library?

athena%1 gcc -Wall -static hello.o -o hello
• Our executable now contains the symbol puts:
..
.
00000000004014c0 W puts
..
.
0000000000400304 T main
..
.
000000000046cd04 R msg
..
.
• ’W’: linked to another defined symbol
1

12
Static linkage

• At link time, statically linked symbols added to executable

• Results in much larger executable file (static – 688K,
dynamic – 10K)
• Resulting executable does not depend on locating external
library files at run time
• To use newer version of library, have to recompile

13
Dynamic linkage

• Dynamic linkage occurs at run-time

• During compile, linker just looks for symbol in external
shared libraries
• Shared library symbols loaded as part of program startup
(before main())
• Requires external library to define symbol exactly as
expected from header file declaration
• changing function in shared library can break your program
• version information used to minimize this problem
• reason why common libraries like libc rarely modify or
remove functions, even broken ones like gets()

14
Linking external libraries

• Programs linked against C standard library by default

• To link against library libnamespec.so or
libnamespec.a, use compiler flag -lnamespec to link
against library
• Library must be in library path (standard library directories
+ directories specified using -L directory compiler flag
• Use -static for force static linkage
• This is enough for static linkage; library code will be added
to resulting executable

15
Loading shared libraries

• Shared library located during compile-time linkage, but

needs to be located again during run-time loading
• Shared libraries located at run-time using linker library
ld.so
• Whenever shared libraries on system change, need to run
ldconfig to update links seen by ld.so
• During loading, symbols in dynamic library are allocated
memory and loaded from shared library file

16
Loading shared libraries on demand

• In Linux, can load symbols from shared libraries on

demand using functions in dlfcn.h
• Open a shared library for loading:
void ∗ dlopen(const char ∗file, int mode);
values for mode: combination of RTLD_LAZY (lazy loading
of library), RTLD_NOW (load now), RTLD_GLOBAL (make
symbols in library available to other libraries yet to be
loaded), RTLD_LOCAL (symbols loaded are accessible
only to your code)

17
Loading shared libraries on demand

• Get the address of a symbol loaded from the library:

void ∗ dlsym(void ∗ handle, const char ∗ symbol_name);
handle from call to dlopen; returned address is pointer to
variable or function identified by symbol_name
• Need to close shared library file handle after done with
symbols in library:
int dlclose(void ∗ handle);
• These functions are not part of C standard library; need to
link against library libdl: -ldl compiler flag

18
Symbol resolution issues

• Symbols can be defined in multiple places

• Suppose we define our own puts() function
• But, puts() defined in C standard library
• When we call puts(), which one gets used?

19
Symbol resolution issues

• Symbols can be defined in multiple places

• Suppose we define our own puts() function
• But, puts() defined in C standard library
• When we call puts(), which one gets used?
• Our puts() gets used since ours is static, and puts() in
C standard library not resolved until run-time
• If statically linked against C standard library, linker finds
two puts() definitions and aborts (multiple definitions not
allowed)

19
Symbol resolution issues

• How about if we define puts() in a shared library and

attempt to use it within our programs?
• Symbols resolved in order they are loaded
• Suppose our library containing puts() is libhello.so,
located in a standard library directory (like /usr/lib),
and we compile our hello.c code against this library:
athena%1 gcc -g -Wall hello.c -lhello -o
hello.o
• Libraries specified using -l flag are loaded in order
specified, and before C standard library
• Which puts() gets used here?
athena% gcc -g -Wall hello.c -lc -lhello -o
hello.o
1

20
6.087 Lecture 9 – January 22, 2010

Review

Using External Libraries

Symbols and Linkage
Static vs. Dynamic Linkage
Linking External Libraries
Symbol Resolution Issues

Creating Libraries

Data Structures
B-trees
Priority Queues

21
Creating libraries

• Libraries contain C code like any other program

• Static or shared libraries compiled from (un-linked) object
files created using gcc
• Compiling a static library:
• compile, but do not link source files:
athena%1 gcc -g -Wall -c infile.c -o
outfile.o
• collect compiled (unlinked) files into an archive:
athena% ar -rcs libname.a outfile1.o
outfile2.o ...

21
Creating shared libraries

• Compile and do not link files using gcc:

1
athena% gcc -g -Wall -fPIC -c infile.c -o
outfile.o
• -fPIC option: create position-independent code, since
code will be repositioned during loading
• Link files using ld to create a shared object (.so) file:
athena% ld -shared -soname libname.so -o
libname.so.version -lc outfile1.o
outfile2.o ...
• If necessary, add directory to LD_LIBRARY_PATH
environment variable, so ld.so can find file when loading
at run-time
• Configure ld.so for new (or changed) library:
athena% ldconfig -v
1

22
Outline

Review

Standard Library
<stdio.h>
<ctype.h>
<stdlib.h>
<assert.h>
<stdarg.h>
<time.h>

1
Review

Standard Library
<stdio.h>
<ctype.h>
<stdlib.h>
<assert.h>
<stdarg.h>
<time.h>

2
Review: Libraries

• linking: binds symbols to addresses.

• static linkage: occurs at compile time (static libraries).
• dynamic linkage: occurs at run time (shared libraries).
• shared libraries:
• ld.so - locates shared libraries
• ldconfig - updates links seen by ld.so
• dlopen(),dlsym(),dlclose() - load shared libraries
on demand.
• compiling static libraries: gcc,ar
• compiling shared libraries: gcc,ldconfig

2
Review

Standard Library
<stdio.h>
<ctype.h>
<stdlib.h>
<assert.h>
<stdarg.h>
<time.h>

5
<stdio.h>: Opening, closing files
FILE∗ fopen(const char∗ filename,const char∗ mode)
• mode can be "r"(read),"w"(write),"a"(append).
• "b" can be appended for binary input/output (unnecessary
in *nx)
• returns NULL on error.
FILE∗ freopen(const char∗ filename,const char∗ mode,FILE∗ stream)

• redirects the stream to the file.

• returns NULL on error.
• Where can this be used? (redirecting stdin,stdout,stderr)
int fflush (FILE∗ stream)
• flushes any unwritten data.
• if stream is NULL flushes all outputs streams.
• returns EOF on error.
5
<stdio.h>: File operations

int remove(const char∗ filename)

• removes the file from the file system.
• retrn non-zero on error.
int rename(const char∗ oldname,const char∗ newname)
• renames file
• returns non-zero on error (reasons?: permission,
existence)

6
<stdio.h>:Temporary files

FILE∗ tmpfile(void)
• creates a temporary file with mode "wb+".
• the file is removed automatically when program
terminates.
char∗ tmpnam(char s[L_tmpnam])
• creates a string that is not the name of an existing file.
• return reference to internal static array if s is NULL.
Populate s otherwise.
• generates a new name every call.

7
<stdio.h>: Raw I/O

size_t fread(void∗ ptr , size_t size , size_t nobj,FILE∗ stream)

• reads at most nobj items of size size from stream into
ptr.
• returns the number of items read.
• feof and ferror must be used to test end of file.
size_t fwrite (const void∗ ptr,size_t size , size_t nobj,FILE∗ stream)

• write at most nobj items of size size from ptr onto

stream.
• returns number of objects written.

8
<stdio.h>: File position
int fseek(FILE∗ stream, long offset,int origin )
• sets file position in the stream. Subsequent read/write
begins at this location
• origin can be SEEK_SET, SEEK_CUR, SEEK_END.
• returns non-zero on error.
long ftell (FILE∗ stream)
• returns the current position within the file. (limitation? long
data type).
• returns -1L on error.

int rewind(FILE∗ stream)

• sets the file pointer at the beginning.
• equivalent to fseek(stream,0L,SEEK_SET);

9
<stdio.h>: File errors

void clearerr (FILE∗ stream)

• clears EOF and other error indicators on stream.
int feof (FILE∗ stream)
• return non-zero (TRUE) if end of file indicator is set for
stream.
• only way to test end of file for functions such as
fwrite(),fread()
int ferror (FILE∗ stream)
• returns non-zero (TRUE) if any error indicator is set for
stream.

10
<ctype.h>: Testing characters

isalnum(c) isalpha(c) || isdigit (c)

iscntrl (c) control characters
isdigit (c) 0-9
islower(c) ’a’-’z’
isprint (c) printable character (includes space)
ispunct(c) punctuation
isspace(c) space, tab or new line
isupper(c) ’A’-’Z’

11
<string.h>: Memory functions
void∗ memcpy(void∗ dst,const void∗ src,size_t n)
• copies n bytes from src to location dst
• returns a pointer to dst.
• src and dst cannot overlap.
void∗ memmove(void∗ dst,const void∗ src,size_t n)
• behaves same as memcpy() function.
• src and dst can overlap.
int memcmp(const void∗ cs,const void∗ ct,int n)
• compares first n bytes between cs and ct.
void∗ memset(void∗ dst,int c,int n)
• fills the first n bytes of dst with the value c.
• returns a pointer to dst

12
<stdlib.h>:Utility

double atof(const char∗ s)

int atoi (const char∗ s)
long atol(const char∗ s)
• converts character to float,integer and long respectively.

int rand()
• returns a pseduo-random numbers between 0 and
RAND_MAX
void srand(unsigned int seed)
• sets the seed for the pseudo-random generator!

13
<stdlib.h>: Exiting

void abort(void)
• causes the program to terminate abnormally.
void exit ( int status)
• causes normal program termination. The value status is
returned to the operating system.
• 0 EXIT_SUCCESS indicates successful termination. Any
other value indicates failure (EXIT_FAILURE)

14
<stdlib.h>:Exiting

void atexit (void (∗fcn )( void))

• registers a function fcn to be called when the program
terminates normally;
• returns non zero when registration cannot be made.
• After exit() is called, the functions are called in reverse
order of registration.
int system(const char∗ cmd)
• executes the command in string cmd.
• if cmd is not null, the program executes the command and
returns exit status returned by the command.

15
<stdlib.h>:Searchign and sorting
void ∗ bsearch ( const void ∗ key , const void ∗ base ,
s i z e _ t n , s i z e _ t size ,
i n t ( ∗ cmp ) ( const void ∗ keyval , const void ∗ datum ) ) ;

• searches base[0] through base[n-1] for *key.

• function cmp() is used to perform comparison.
• returns a pointer to the matching item if it exists and NULL
otherwise.

void q s o r t ( void ∗ base , s i z e _ t n ,

s i z e _ t sz ,
i n t ( ∗ cmp ) ( const void ∗ , const void ∗ ) ) !

• sorts base[0] through base[n-1] in

ascending/descending order.
• function cmp() is used to perform comparison.

16
<assert.h>:Diagnostics

void assert(int expression)

• used to check for invariants/code consistency during
debugging.
• does nothing when expression is true.
• prints an error message indicating, expression, filename
and line number.
Alternative ways to print filename and line number during
execution is to use: __FILE__,__LINE__ macros.

17
<stdarg.h>:Variable argument lists

Variable argument lists:

• functions can variable number of arguments.
• the data type of the argument can be different for each
argument.
• atleast one mandatory argument is required.
• Declaration:
int printf (char∗ fmt ,...); /∗fmt is last named argument∗/
va_list ap
• ap defines an iterator that will point to the variable
argument.
• before using, it has to be initialized using va_start.

18
<stdarg.h>:Variable argument list

va_start( va_list ap, lastarg )

• ap lastarg refers to the name of the last named argument.
• va_start is a macro.
va_arg(va_list ap, type)
• each call of va_arg points ap to the next argument.
• type has to be inferred from the fixed argument (e.g. printf)
or determined based on previous argument(s).
va_end(va_list ap)
• must be called before the function is exited.

19
<stdarg.h>:Variable argument list(cont.)

i n t sum ( i n t num , . . . )
{
v a _ l i s t ap ; i n t t o t a l =0;
v a _ s t a r t ( ap , num ) ;
while ( num>0)
{
t o t a l +=va_arg ( ap , i n t ) ;
num−−;
}
va_end ( ap ) ;
return t o t a l ;
}

i n t suma=sum ( 4 , 1 , 2 , 3 , 4 ) ; / ∗ c a l l e d w i t h f i v e args ∗ /
i n t sumb=sum ( 2 , 1 , 2 ) ; / ∗ c a l l e d w i t h t h r e e args ∗ /

20
<time.h>

time_t, clock_t , struct tm data types associated with time.

int tm_sec seconds
int tm_min minutes
int tm_hour hour since midnight (0,23)
int tm_mday day of the month (1,31)
struct tm: int tm_mon month
int tm_year years since 1900
int tm_wday day since sunday (0,6)
int tm_yday day since Jan 1 (0,365)
int tm_isdst DST flag

21
<time.h>

clock_t clock ()
• returns processor time used since beginning of program.
• divide by CLOCKS_PER_SEC to get time in seconds.
time_t time(time_t ∗ tp)
• returns current time (seconds since Jan 1 1970).
• if tp is not NULL, also populates tp.
double difftime(time_t t1 ,time_t t2)
• returns difference in seconds.
time_t mktime(struct tm∗ tp)
• converts the structure to a time_t object.
• returns -1 if conversion is not possible.

22
<time.h>

char∗ asctime(const struct tm∗ tp)

• returns string representation of the form "Sun Jan 3
15:14:13 1988".
• returns static reference (can be overwritten by other calls).
struct tm∗ localtime(const time_t ∗ tp)
• converts calendar time to local time".
char∗ ctime(const time_t ∗ tp)
• converts calendar time to string representation of local
time".
• equivalent to sctime(locltime(tp))!

23
<time.h>
size_t strftime (char∗ s,size_t smax,const char∗ fmt,const struct tm∗ tp)

• returns time in the desired format.

• does not write more than smax characters into the string s.

%a abbreviated weekday name

%A full weekday name
%b abbreviated month name
%B full month name
%d day of the month
%H hour (0-23)
%I hour (0-12)
%m month
%M minute
%p AM/PM
%S second

24