On 6 Dec 99 at 12:10, Erez Zadok wrote:
> - a faster method than constant shifting of the bytes. This is a serious
> one. If you keep shifting bytes for each component, your complexity is
> O(n^2). You can make it 2*O(n) as follows:
> (1) first, scan the dentrys and their parents in reverse, cross mount
> points as needed.
> (2) sum up the total number of bytes needed, from the q_str structures.
> (3) allocate the correct number of bytes (or verify that the user passed
> enough space)
> (4) repeat the reverse traversal, but this time, copy the bytes into the
> output buffer directly at their offsets into the buffer (don't copy
> any terminating nulls so you won't trash the beginning of the
> component that followed).
I probably missed something important, but what's wrong with
approach d_path() is using now - returning pointer into middle of buffer?
Walking list twice is going to be nightmare if we ever make dcache
multithreaded. In most cases you want to copy path somewhere anyway, so
it is not important whether it ends in the middle of buffer or at the
beginning. Also, as sideeffect of current approach, you can get path
length quickly by simple doing
returned_path_pointer = d_path(dentry, buffer, buffer_length);
len = buffer + buffer_length - returned_path_pointer
Best regards,
Petr Vandrovec
[EMAIL PROTECTED]
