En réponse à Michael Phipps <mphipps1@xxxxxxxxxxxxxxxx>: > > [snip] > Trees and skiplists (both of which I considered) are *way* too big, > memory and code wise, for kernel work. > Think about it - skip lists with 2-10 (or more) pointers per node? Where > a node is a single socket/file handle? > Trees are possible, but they still have issues (O(log 2 N)) with > performance, they have to be rebalanced, and they are painful to code. > Not to mention the 2 pointers per node. I think that the solution for > these things *has* to be space and code efficient. I am thinking that > maybe allocating a structure like this: > struct fewFileHandles{ > fileHandle small[4]; > struct manyFileHandles *more; > } > I see I had similar ideas :) > Where manyFileHandles is exactly the same, but with, maybe 25 > fileHandles and a pointer to another of the same would be a good > approach. > In fact, that sort of thing solves both of these issues. Leaping through > the list, 25 at a time, is not too bad, for file handles and sockets. > Maybe 50 pages at a time for VM... Or even: > struct vmPages { > page *pages[50]; > a100Pages *somePages; > a1000Pages *lotsOfPages; > } > > Where one or both of the pointers will be null... > Hmm - I will have to think about that... > IIRC the Ext2 filesystem uses this kind o approach for storing files... there are direct, indirect and double indirect blocks... François.