Quote:
Originally Posted by deadeyes
Currently I am using the readdir function to get file entries in a directory.
For each file I use stat to get the filesize.
|
As the
readdir man page states:
Quote:
|
Originally Posted by readdir(3)
The data returned by readdir() may be overwritten by subsequent calls to readdir() for the same directory stream.
|
In other words, temporary storage is allocated as part of the directory stream (
DIR *), and reused for each
readdir() call; the string is only valid up to the next
readdir() or
closedir() call referring to the same directory stream. (Actually, the temporary storage tends to be a bit larger, large enough to hold a few dozen directory entries at least.)
Personally, I'd use a C99 structure similar to the following:
Code:
struct fileinfo {
/* File properties would go here,
* except for your sort key, file size.
*/
/* File path and name */
size_t name;
size_t pathlen;
char path[];
};
/* Full path accessor function. Returns none if given an invalid pointer. */
static inline const char *fileinfo_path(const struct fileinfo *const info, const char *const none)
{
if (info && info->pathlen)
return (const char *)info->path;
else
return none;
}
/* File name accessor function. Returns none if given an invalid pointer.
*/
static inline const char *fileinfo_name(const struct fileinfo *const info, const char *const none)
{
if (info && info->pathlen)
return (const char *)info->path + info->name;
else
return none;
}
/* Free a fileinfo structure.
* Always returns NULL.
*/
struct fileinfo *fileinfo_free(struct fileinfo *const info)
{
if (info && info->pathlen) {
/* Poison the structure.
* This helps catch use-after-free,
* as the path is suddenly empty.
*/
info->pathlen = 0;
info->name = 0;
info->path[0] = '\0';
/* Free the dynamically allocated memory
* used by the structure. */
free(info);
}
return NULL;
}
/* Construct a fileinfo structure.
* Does NOT fill in the file properties (size et cetera)!
*/
struct fileinfo *fileinfo_create(const char *const path, const char *const name)
{
const size_t pathlen = (path) ? strlen(path) : 0;
const size_t namelen = (name) ? strlen(name) : 0;
const size_t padded = ((pathlen + namelen + 1) | 7) + 1;
size_t n;
struct fileinfo *info;
if (pathlen + namelen < (size_t)1) {
errno = EINVAL;
return NULL;
}
info = malloc(sizeof (struct fileinfo) + padded);
if (!info) {
errno = ENOMEM;
return NULL;
}
/* Make sure the path is terminated with an ASCII NUL. */
if (padded > 16)
memset(info->path + padded - 16, '\0', 16);
else
memset(info->path, '\0', padded);
/* Build the actual path. */
n = 0;
if (pathlen > 0) {
memcpy(info->path, path, pathlen);
n += pathlen;
if (info->path[n-1] != '/')
info->path[n++] = '/';
}
info->name = n;
if (namelen > 0) {
memcpy(info->path + n, name, namelen);
n += namelen;
}
info->pathlen = n;
return info;
}
To keep a fixed number of fileinfo structures, create an array of fileinfo pointers, and another array of file sizes (off_t type), with the same number of entries. The separation into two arrays makes sure your CPU does minimal memory accesses to check the file sizes.
For each new directory entry, obtain its file size, and compare against the initial entry in the file size array. If the new file is larger, discard the initial fileinfo structure, and create a new for the new directory entry. Also update the initial file size array entry to reflect the file size. Then, scan through the file size array to see if there is a smaller file size than the new initial entry. If so, swap the two, so that the entry corresponding to the smallest file is always first in the arrays.
Note: you do not need to do more than one swap, total. Scan the array first, then do one swap, if necessary. This is also why the sort key, file size, array is separate: so that it can be scanned with minimal CPU use. For small arrays (depends on CPU, but say up to a couple of dozen entries) this is the fastest option.
The above is reasonably fast for several dozen or even hundreds of entries, but it scales poorly when the arrays get much bigger. In other words, with enough entries in the array, it gets slow.
If you wanted to keep a lot of fileinfo structures, order the arrays as a binary min heap. Element at index
i has parent (with equal or smaller filesize) at index
(i-1)/2, and possibly childs (with equal or larger filesizes) at indices
2*i+1 and
2*i+2.
The entry corresponding to the smallest known file is at index 0, so most of the time, you'll be simply comparing against that one. When you replace it, you percolate the entry outwards, swapping with the smaller child, until the heap property (parent filesize <= filesize <= child filesize) is no longer violated. This is just
log₂N steps even in the worst case, so this is very fast even if the array size
N gets very large. (To append to the heap, you add the data at the end, then percolate down, swapping with the parent until the parent is smaller or equal in file size.)
