Fix head and tail check with negative offset in _quicklistInsert (#9311)

Some background:
This fixes a problem that used to be dead code till now,
but became alive (only in the unit tests, not in redis) when #9113 got merged.
The problem it fixes doesn't actually cause any significant harm,
but that PR also added a test that fails verification because of that.
This test was merged with that problem due to human error, we didn't run it
on the last modified version before merging.
The fix in this PR existed in #8641 (closed because it's just dead code)
and #4674 (still pending but has other changes in it).

Now to the actual fix:
On quicklist insertion, if the insertion offset is -1 or `-(quicklist->count)`,
we can insert into the head of the next node rather than the tail of the
current node. this is especially important when the current node is full,
and adding anything to it will cause it to be split (or be over it's fill limit setting).

The bug was that the code attempted to determine that we're adding to
the tail of the current node by matching `offset == node->count` when in
fact it should have been `offset == node->count-1` (so it never entered that `if`).
and also that since we take negative offsets too, we can also match `-1`.
same applies for the head, i.e. `0` and `-count`.

The bug will cause the code to attempt inserting into the current node (thinking
we have to insert into the middle of the node rather than head or tail), and
in case the current node is full it'll have to be split (something that also
happens in valid cases).
On top of that, since it calls _quicklistSplitNode with an edge case, it'll actually
split the node in a way that all the entries fall into one split, and 0 into the other,
and then still insert the new entry into the first one, causing it to be populated
beyond it's intended fill limit.

This problem does not create any bug in redis, because the existing code does
not iterate from tail to head, and the offset never has a negative value when insert.

The other change this PR makes in the test code is just for some coverage,
insertion at index 0 is tested a lot, so it's nice to test some negative offsets too.

1 files changed, 3 insertions, 3 deletions

diff --git a/src/quicklist.c b/src/quicklist.c
index 42ed4ecd4..4874ecc05 100644
--- a/src/quicklist.c
+++ b/src/quicklist.c
@@ -866,7 +866,7 @@ REDIS_STATIC void _quicklistInsert(quicklist *quicklist, quicklistEntry *entry,
         full = 1;
     }
 
-    if (after && (entry->offset == node->count)) {
+    if (after && (entry->offset == node->count - 1 || entry->offset == -1)) {
         D("At Tail of current ziplist");
         at_tail = 1;
         if (_quicklistNodeAllowInsert(node->next, fill, sz)) {
@@ -875,7 +875,7 @@ REDIS_STATIC void _quicklistInsert(quicklist *quicklist, quicklistEntry *entry,
         }
     }
 
-    if (!after && (entry->offset == 0)) {
+    if (!after && (entry->offset == 0 || entry->offset == -(node->count))) {
         D("At Head");
         at_head = 1;
         if (_quicklistNodeAllowInsert(node->prev, fill, sz)) {
@@ -2014,7 +2014,7 @@ int quicklistTest(int argc, char *argv[], int accurate) {
                 quicklistPushTail(ql, genstr("hello", i), 6);
             quicklistSetFill(ql, -1);
             quicklistEntry entry;
-            quicklistIndex(ql, 0, &entry);
+            quicklistIndex(ql, -10, &entry);
             char buf[4096] = {0};
             quicklistInsertBefore(ql, &entry, buf, 4096);
             ql_verify(ql, 4, 11, 1, 2);