3
\$\begingroup\$

I want to fill an array of strings with the name of each directory item. The issue is allocating memory. I either need to count the items before, allocate memory, then go over them again, or I will have to reallocate each iteration of the while loop. Both of these options seem slow. Surely there's a better way.

Which is faster:

char **Names;
DIR *Dir = opendir("Some dir path");
struct dirent *Entry;
unsigned int Count = 0;
while ((Entry = readdir(Dir))) {
    Count++;
}
Names = malloc(Count*sizeof(char*));
closedir(Dir);
Dir = opendir("Some dir path"); //Also, is there a better way to reset it, other than closing it and reopening?
for (int i = 0; (Entry = readdir(Dir); i++) {
    unsigned short NamLen = strlen(Entry->d_name)+1;
    Names[i] = malloc(NameLen);
    memcpy(Names[i], entry->d_name, NameLen);
}

Or

char **Names;
DIR *Dir = opendir("Some dir path");
Dir = opendir("Some dir path");
struct dirent *Entry;
for (int i = 0; (Entry = readdir(Dir); i++) {
    Names = realloc(Names, i*sizeof(char*));
    unsigned short NamLen = strlen(Entry->d_name)+1;
    Names[i] = malloc(NameLen);
    memcpy(Names[i], entry->d_name, NameLen);
}
closedir(Dir);

Please help, I'm stuck. Both of these seem less efficient than optimal, so surely there's a better way. What's the fastest way to record all the names of items in a directory to a string array? Is there a faster option aside these two?

\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

Calling realloc in every iteration makes the code really slow. Algorithmically it is in \$\mathcal O(n^2)\$ since realloc already has complexity \$\mathcal O(n)\$. Plus, you are calling it interleaved with malloc for the name of the directory entries.

The performance of your program depends very much on the specific memory allocator. It might be very fast or very slow, probably somewhere between \$n\$ and \$n^2\$.

To fix this, you should use the well-known pattern of having a triplet (pointer, length, capacity) to represent the growing buffer of directory entries.

Ideally you define a separate struct for this, together with an append function. That way, the function that reads the directory entries doesn't have to fiddle with realloc directly.

\$\endgroup\$
2
\$\begingroup\$

the fastest way is to keep a counter of the number of entries allocated. then on the first call to realloc() just allocate for a single entry. Only call realloc() when all the current allocation is used. each time `realloc() is called, double the allocation count. I.E. 1, 2, 4, 8, 16, 32, etc.

Be sure to always assign the result of realloc() to a temp variable, check that variable to assure it is not NULL, before assigning to the target variable to avoid a unrecoverable memory leak when realloc() fails

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy