I'm doing a replacement for the venerable make
utility that will support, among other things, automatic cleaning. The utility figures out automatically what files and directories are targets, and then deletes those, if the user wishes to do a clean operation. However, a file may reside in an automatically created directory, meaning I should do a topological sort for the targets, where every file has an arc towards the parent directory, and every directory has an arc towards its parent. So, for example:
objhierarchy/obj/foo.o
has an arc towardsobjhierarchy/obj
objhierarchy/obj
has an arc towardsobjhierarchy
What complicates the things is that the files need to be deleted in the reverse order. So, in the example given, you need this order: (1) objhierarchy/obj/foo.o
, (2) objhierarchy/obj
, (3) objhierarchy
.
Topological sort seems like a good solution, but it gives the opposite order. So, a topological sort of the directory parent graph would yield (1) objhierarchy
, (2) objhierarchy/obj
, (3) objhierarchy/obj/foo.o
.
A solution could be a buffer of pointers that is reversed in-place (or just iterated in the reverse order), but I would like to avoid allocating extra memory.
What is the best way to get the files deleted in the reverse order? Can the topological sort algorithm based on depth first search be modified to call some callback function in a reverse order?