On Fri, Aug 4, 2017 at 2:33 PM, Christopher Li <sparse@xxxxxxxxxxx> wrote: > 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? OK. I might have a way to make it work for insert case. Let me lay it out here. Has two bit mask, one for deleted entry. one for inserted entry, let's call it insert slot mask. The deleted entry is what Linus suggested. The inserted slot mask is marking which entry is new element insert into the list->list[]. When the list->list[] was shifted to make room for new ptr entry, the insert slot mask will need to be shift accordingly was well. (so does the delete slot mask). I was original thinking only track element insert in the middle of list->list[]. But then I realize for the reverse ptr loop case I need to track insert from the tail as well. Then the parent loop iterator will keep a copy of the insert mask and __nth_slot_ptr before execute the loop body. The inner loop might update the ptrlist and the insert slot mask. The parent can compare the cached version of the insert slot mask and the current list insert slot mask to find out which slot are inserted during the execution of the loop body. Then the parent can adjust __nth_slot_ptr accordingly. It is complicated, but it seems possible to make correct loop iterator when the inner loop modify insert element to the list. It is the first idea I have that does not involve with a link list of the previous modify log. I obvious need to think about it more. For now, I do think this can produce the correct behavior. The space cost of extra 32 bit slot is not too bad either. 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
