On Tue, Mar 13, 2018 at 11:34:53AM +0800, Aaron Lu wrote: > I wish there is a data structure that has the flexibility of list while > at the same time we can locate the Nth element in the list without the > need to iterate. That's what I'm looking for when developing clustered > allocation for order 0 pages. In the end, I had to use another place to > record where the Nth element is. I hope to send out v2 of that RFC > series soon but I'm still collecting data for it. I would appreciate if > people could take a look then :-) Sorry, I missed this. There is such a data structure -- the IDR, or possibly a bare radix tree, or we can build a better data structure on top of the radix tree (I talked about one called the XQueue a while ago). The IDR will automatically grow to whatever needed size, it stores pointers, you can find out quickly where the last allocated index is, you can remove from the middle of the array. Disadvantage is that it requires memory allocation to store the array of pointers, *but* it can always hold at least one entry. So if you have no memory, you can always return the one element in your IDR to the free pool and allocate from that page.
