From: Ingo Molnar <mingo@elte.hu>
On Tue, 16 Jan 2001, Felix von Leitner wrote:
> I don't know how Linux does it, but returning the first free file
> descriptor can be implemented as O(1) operation.
to put it more accurately: the requirement is to be able to open(), use
and close() an unlimited number of file descriptors with O(1) overhead,
under any allocation pattern, with only RAM limiting the number of files.
Both of my proposals attempt to provide this. It's possible to open() O(1)
but do a O(log(N)) close(), but that is of no practical value IMO.
Ingo
> Both of my proposals
I am afraid I have missed most earlier messages in this thread.
However, let me remark that the problem of assigning a
file descriptor is the one that is usually described by
"priority queue". The version of Peter van Emde Boas takes
time O(loglog N) for both open() and close().
Of course this is not meant to suggest that we use it.
Andries
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Tue Jan 23 2001 - 21:00:12 EST