BUG#30301356 - SOME EVENTS ARE DELAYED AFTER DROPPING EVENT

queues.c cleanup and refactoring.

Restore old version of _downhead() (from before cd483c55209)
that works well in an average case. Use it for queue_fix().

Move existing specialized version of _downhead() to queue_replace()
where it'll be handling the case it was specifically optimized for
(moving the element to the end of the queue).
And correct it to fix the heap not only down, but also up
(this fixes BUG#30301356).

Add unit tests.

Collateral cosmetic fixes.

2 files changed, 139 insertions, 1 deletions

diff --git a/unittest/mysys/CMakeLists.txt b/unittest/mysys/CMakeLists.txt
index de7efeaaaec..21be7e82cda 100644
--- a/unittest/mysys/CMakeLists.txt
+++ b/unittest/mysys/CMakeLists.txt
@@ -14,7 +14,7 @@
 # Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1335 USA
 
 MY_ADD_TESTS(bitmap base64 my_atomic my_rdtsc lf my_malloc my_getopt dynstring
-             LINK_LIBRARIES mysys)
+             queues LINK_LIBRARIES mysys)
 MY_ADD_TESTS(my_vsnprintf LINK_LIBRARIES strings mysys)
 
 IF(WIN32)
diff --git a/unittest/mysys/queues-t.c b/unittest/mysys/queues-t.c
new file mode 100644
index 00000000000..d12dd86a7f6
--- /dev/null
+++ b/unittest/mysys/queues-t.c
@@ -0,0 +1,138 @@
+/* Copyright (c) 2020, MariaDB Corporation
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */
+
+#include <my_global.h>
+#include <my_sys.h>
+#include <queues.h>
+#include "tap.h"
+
+int cmp(void *arg __attribute__((unused)), uchar *a, uchar *b)
+{
+  return *a < *b ? -1 : *a > *b;
+}
+
+#define rnd(R) ((uint)(my_rnd(R) * INT_MAX32))
+
+#define el(Q,I) ((uint)*queue_element(Q, I))
+
+my_bool verbose;
+
+my_bool check_queue(QUEUE *queue)
+{
+  char b[1024]={0}, *s, *e=b+sizeof(b)-2;
+  my_bool ok=1;
+  uint i;
+
+  s= b + my_snprintf(b, e-b, "%x", el(queue, 1));
+  for (i=2; i <= queue->elements; i++)
+  {
+    s+= my_snprintf(s, e-s, ", %x", el(queue, i));
+    ok &= el(queue, i) <= el(queue, i>>1);
+  }
+  if (!ok || verbose)
+    diag("%s", b);
+  return ok;
+}
+
+int main(int argc __attribute__((unused)), char *argv[])
+{
+  QUEUE q, *queue=&q;
+  MY_INIT(argv[0]);
+  plan(19);
+
+  verbose=1;
+
+  init_queue(queue, 256, 0, 1, cmp, NULL, 0, 0);
+  queue_insert(queue, (uchar*)"\x99");
+  queue_insert(queue, (uchar*)"\x19");
+  queue_insert(queue, (uchar*)"\x36");
+  queue_insert(queue, (uchar*)"\x17");
+  queue_insert(queue, (uchar*)"\x12");
+  queue_insert(queue, (uchar*)"\x05");
+  queue_insert(queue, (uchar*)"\x25");
+  queue_insert(queue, (uchar*)"\x09");
+  queue_insert(queue, (uchar*)"\x15");
+  queue_insert(queue, (uchar*)"\x06");
+  queue_insert(queue, (uchar*)"\x11");
+  queue_insert(queue, (uchar*)"\x01");
+  queue_insert(queue, (uchar*)"\x04");
+  queue_insert(queue, (uchar*)"\x13");
+  queue_insert(queue, (uchar*)"\x24");
+  ok(check_queue(queue), "after insert");
+  queue_remove(queue, 5);
+  ok(check_queue(queue), "after remove 5th");
+
+  queue_element(queue, 1) = (uchar*)"\x01";
+  queue_element(queue, 2) = (uchar*)"\x10";
+  queue_element(queue, 3) = (uchar*)"\x04";
+  queue_element(queue, 4) = (uchar*)"\x09";
+  queue_element(queue, 5) = (uchar*)"\x13";
+  queue_element(queue, 6) = (uchar*)"\x03";
+  queue_element(queue, 7) = (uchar*)"\x08";
+  queue_element(queue, 8) = (uchar*)"\x07";
+  queue_element(queue, 9) = (uchar*)"\x06";
+  queue_element(queue,10) = (uchar*)"\x12";
+  queue_element(queue,11) = (uchar*)"\x05";
+  queue_element(queue,12) = (uchar*)"\x02";
+  queue_element(queue,13) = (uchar*)"\x11";
+  queue->elements= 13;
+  ok(!check_queue(queue), "manually filled (queue property violated)");
+
+  queue_fix(queue);
+  ok(check_queue(queue), "fixed");
+
+  ok(*queue_remove_top(queue) == 0x13, "remove top 13");
+  ok(*queue_remove_top(queue) == 0x12, "remove top 12");
+  ok(*queue_remove_top(queue) == 0x11, "remove top 11");
+  ok(*queue_remove_top(queue) == 0x10, "remove top 10");
+  ok(*queue_remove_top(queue) == 0x09, "remove top 9");
+  ok(*queue_remove_top(queue) == 0x08, "remove top 8");
+  ok(*queue_remove_top(queue) == 0x07, "remove top 7");
+  ok(*queue_remove_top(queue) == 0x06, "remove top 6");
+  ok(*queue_remove_top(queue) == 0x05, "remove top 5");
+  ok(*queue_remove_top(queue) == 0x04, "remove top 4");
+  ok(*queue_remove_top(queue) == 0x03, "remove top 3");
+  ok(*queue_remove_top(queue) == 0x02, "remove top 2");
+  ok(*queue_remove_top(queue) == 0x01, "remove top 1");
+
+  /* random test */
+  {
+    int i, res;
+    struct my_rnd_struct rand;
+    my_rnd_init(&rand, (ulong)(intptr)&i, (ulong)(intptr)argv);
+    verbose=0;
+
+    for (res= i=1; i <= 250; i++)
+    {
+      uchar *s=alloca(2);
+      *s= rnd(&rand) % 251;
+      queue_insert(queue, s);
+      res &= check_queue(queue);
+    }
+    ok(res, "inserted 250");
+
+    while (queue->elements)
+    {
+      queue_remove(queue, (rnd(&rand) % queue->elements) + 1);
+      res &= check_queue(queue);
+    }
+    ok(res, "removed 250");
+  }
+
+  delete_queue(queue);
+  my_end(0);
+  return exit_status();
+}
+