Quicksort Example: Directory Listings
In a hierarchical file system, files are typically organized conceptually into directories. For any directory, we may want to see a list of the files and subdirectories the directory contains. In Unix, we do this with the ls command, for example. At the command prompt in Windows, we do this with the dir command.
This section presents a function called
directls, which implements the same basic
functionality that ls provides. It
uses the system call readdir to create a listing
of the directory specified in path (see
Examples Example 12.3 and Example 12.4). Just as ls does in the default case,
directls sorts the listing by name. Because we
allocate the listing using realloc as we build
it, it is the responsibility of the caller to free it with
free once it is no longer needed.
The runtime complexity of directls is O (n lg n), where n is the number of entries in the directory being listed. This is because retrieving n directory entries is an operation that runs in O (n) time overall, while the subsequent call to qksort sorts the entries in O (n lg n) time.
/*****************************************************************************
* *
* ------------------------------ directls.h ------------------------------ *
* *
*****************************************************************************/
#ifndef DIRECTLS_H
#define DIRECTLS_H
#include <dirent.h>
/*****************************************************************************
* *
* Define a structure for directory entries. *
* *
*****************************************************************************/
typedef struct Directory_ {
char name[MAXNAMLEN + 1];
} Directory;
/*****************************************************************************
* *
* --------------------------- Public Interface --------------------------- *
* *
*****************************************************************************/
int directory(const char *path, Directory **dir);
#endif/***************************************************************************** * * * ------------------------------ directls.c ------------------------------ * * * *****************************************************************************/ #include <dirent.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include "directls.h" #include "sort.h" /***************************************************************************** * * * ------------------------------ compare_dir ----------------------------- * * * *****************************************************************************/ static int compare_dir(const void *key1, const void *key2) { int retval; if ((retval = strcmp(((const Directory *)key1)->name, ((const Directory *) key2)->name)) > 0) return 1; else if (retval < 0) return -1; else return 0; } /***************************************************************************** * * * ------------------------------- directls ------------------------------ * * * *****************************************************************************/ int directls(const char *path, Directory **dir) { DIR *dirptr; Directory *temp; struct dirent *curdir; int count, i; /***************************************************************************** * * * Open the directory. * * * *****************************************************************************/ if ((dirptr = opendir(path)) == NULL) return -1; /***************************************************************************** * * * Get the directory entries. * * * *****************************************************************************/ *dir = NULL; count = 0; while ((curdir = readdir(dirptr)) != NULL) { count++; if ((temp = (Directory *)realloc(*dir, count * sizeof(Directory))) == NULL) { free(*dir); return -1; } else { *dir = temp; } strcpy(((*dir)[count - 1]).name, curdir->d_name); } closedir(dirptr); /***************************************************************************** * * * Sort the directory entries by name. * * * *****************************************************************************/ if (qksort(*dir, count, sizeof(Directory), 0, count - 1, compare_dir) != 0) return -1; /***************************************************************************** * * * Return the number of directory entries. * * * *****************************************************************************/ return count; }