On Fri, Aug 4, 2017 at 12:54 PM, Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx> wrote: > > I think what might be a good idea is to simply replace the "nr" in > "ptr_list" with a bitmap of entries instead. That is one interesting idea. > > We already limit each ptr_list[] to 29 entries, so making it an > "unsigned int" bitmap instead wouldn't be hard. So it would be just a > single-bit "tag" whether an entry is present or not. Sure. I think Luc has a patch to make it 13 entries now. > > And that allows easy deletion, easy insertion and easy to iterate over too. I have to think about the insert and ptrlist node split more. > > The insertion is admittedly a *bit* awkward, since you have to find a > free bit, but it's either a fairly simple loop or on newer CPU's you > can use the "find first bit" instruction. So for the nested loop insert case, the parent loop iterator will keep track of __nth_valid_ptr as the slot indicator instead of __nr. If the insert happen before the __nth_valid_ptr, That still doesn't work, because the list->list[] will still get shifted. If the insert only happen after __nth_valid_ptr, that might be able to work. For node spiting, We just need to carry over the __nth_valid_ptr to the next splinted node, still not work if the insert position is before the carry over part of the __nth_valid_ptr. Again I need to think about it more. Or do you see a way to make insert into any slot position work with parent holding pointer to the slot number? Yes, the bit mask seems better than the mark ptr entry as NULL or tag it. Chris -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
