Thursday, March 5, 2009

What sorting algorithm does Makefile use?

Most of us know what a makefile is.
It has instructions for creating the a.out file.

If you're new to makefiles, you might want to read this before proceeding further.
So, let me get to the point here.
We write rules on how to compile the programs of the form

target : dependencies
commands

If we see the whole story, the make file produces the target based on dependencies, IN ORDER.
Can you relate this to any algorithm?
Think... What algorithm relates events to happen in a definite sequence to produce the output?

Answer: Topological sort
Think about it. The dependencies are compiled in order.
Lets look at an example.
out : main.o sort.o
gcc -o out main.o sort.o

main.o : main.c
gcc -c main.c

sort.o : sort.h sort.c
gcc -c sort.c

the rule main.o has to be dealt with.
This in turn will compile main.c if:
1: main.o didn't exist.
2: main.c was modified after creation of the previous main.o

Similarly, sort.o will have to be dealt with to produce sort.o
Then, both the main.o and sort.o files will be combined to produce out which can be run using ./out

No comments:

Post a Comment