catalogue/directory: sorted set instead of vector

Hey Dennis,

I have come across a performance issue in DAR 2.3.9 
that occurs if you archive directories with a huge number of
files in them (and possibly do on-the-fly-isolate,
haven't yet tested wether this is required for the
problem to occur).

Specifically, after gprofing the issue, the problem
seems to happen in the directory class defined in
catalogue.hpp/cpp which uses the STL vector template
to store an unsorted list of nommes, and this
list is often linearily searched to find out if
a given name is already present in the list,
with the obvious consequences if the list becomes
large.

I've replaced that with the sorted STL set template + std::string
< operator, which has much nicer performance characteristics
in this case, but internally sorts the elements and thus
when reading out the members of a directory
the order of elements will no longe be the same as when
they were added to this data structure.

Could this cause problems with some of DAR's features?
More specifically, is the order of the elements in the directory class
relevant for at least one part of DAR? If not, would you be interested
in a patch? Any specific requirements for a patch (at the moment
I am simply replacing the implementation without any extra autoconf
or runtime options to control this feature)

In any case, the performance impact is fairly major if you archive
a single directory with a million empty files with the following config
(standard dar-2.3.9 --enable-debug --enable-profiling --enable-mode=64):

--create /tmp/dar_test
--on-fly-isolate /tmp/dar_test_iso
--fs-root DAR_Test/ # 1 million empty files (named 0 .. 999999)
--slice 500M

It takes about 6 minutes to run this with my patched version,
the unpatched version is still running (since about 2 days
now), I am letting it finish to see what the difference in memory
usage is.

Sure, having a million files in a directory, particularily in a Linux
ext3 directory, is not such a clever idea, but customers are well
customers ;)

    Thomas

------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day 
trial. Simplify your report design, integration and deployment - and focus on 
what you do best, core application coding. Discover what's new with 
Crystal Reports now.  http://p.sf.net/sfu/bobj-july