Hi,
Thank you for the detailed explanation! Your explanation helped me understand the design much better.
I hope my understanding is now on the right track.
I tested v3 both approaches:
1. Ilia's proposal with corrected increment and <= condition:
if (was_count1 && j <= firstcount1)
firstcount1++;
2. The original patch with while loop:
while (use_hash && firstcount1 < track_cnt &&
track[firstcount1].count > 1)
firstcount1++;
I verified the following cases and both approaches produced correct
track array values after the loop completed:
Case 1: c1_cursor == match_index
c1_cursor points to a singleton, that singleton is matched again,
bubble-up occurs, then a new value arrives triggering eviction.
Case 2: c1_cursor < match_index
c1_cursor is in the earlier part of the singleton region,
and a singleton further back is matched.
Case 3: c1_cursor > match_index
c1_cursor has advanced past match_index due to previous evictions,
and an earlier singleton is matched.
Both approaches seem to work correctly. The code reduction from 1 is minimal, so either approach should be fine.
I believe the while loop exists to handle potential edge cases,
though in typical scenarios firstcount1 would only increment once per match (since one singleton is promoted at a time).
Overall, the patch looks good to me.
Regards,
Tatsuya Kawata
