Comment 3 for bug 638618

Hm, how would you manage the dirindexes for the basenames then? I suppose instead of using direct integers you could make it a pointer to a dirindex entry in a struct of the dirname and dirindex with which you populate the b-tree.

Sample:

struct dnames {
    int dirindex;
    char *dirname;
    struct dnames *left;
    struct dnames *right;
};

and have dirindexes:

int *dirindexes;
dirindexes = malloc(sizeof(int *) * len_of_filelist);

This way you can at least build the b-tree and the basenames list and the dirindexes pointer list in 1 pass and just need a quick 2nd pass to generate the final dirnames list together with the correct dirindexes in the b-tree and then save the values of the pointers in dirindexes. And as the dirnames should be a lot smaller than the filelist the time overhead should be minimal.