[Bug-tar] --exclude-from/no-wildcards speedup?

[Florian Sager]

Hello,

 

this is a feature request:

 

in Names.c the gnulib function  bool excluded_file_name (struct exclude const *ex, char const *f) is called to check if f is contained in ex.

 

If the tar option --no-wildcards is set, the gnulib method fnmatch_no_wildcards is used for this in http://cvs.savannah.gnu.org/viewvc/gnulib/lib/exclude.c?revision=1.32&root=gnulib&view=markup

 

This method checks f in O(n*m) --> see FIXME comment:

---

Walk through a copy of F, seeing whether P matches any prefix
	 of F.

	 FIXME: This is an O(N**2) algorithm; it should be O(N).
	 Also, the copy should not be necessary.  However, fixing this
	 will probably involve a change to the mbs* API.

---

 

In my view this could be even done in O(log n) in a tree structure, but I cannot determine the implications of changing the exclude struct from a list to a tree.

 

Would you start this transformation inside tar or inside gnulib?

 

Best regards,

Florian Sager