Re: file ID redesign proposal
Morten Welinder (terra@diku.dk)
Wed, 26 Nov 1997 20:01:26 +0100
> Isn't it possible to get away with close() being the only O(lg(n))
> operation? Suppose close() maintains an ordered list, through whatever
> method. You can arrange it so that allocation is O(1). You don't need to
> build the list initially, keep a high_water_mark which indicates the
> highest fd allocated so far. If the free list is empty, then just use
> high_water_mark.
This sounds do-able, but we don't really need a sorted list. We
need a data structure such that we can pull out the lowest
numbered file ID. In other words, we need a priority queue.
It should probably work with ranges, not with individual IDs;
this would also eliminate the need to keep high_water_mark
around.
Morten