Modules: implement zig-zag scanning in autoMemoryFreed().

Most of the time to check the last element is the way to go, however
there are patterns where the contrary is the best choice. Zig-zag
scanning implemented in this commmit always checks the obvious element
first (the last added -- think at a loop where the last element
allocated gets freed again and again), and continues checking one
element in the head and one in the tail.

Thanks to @dvisrky that fixed the original implementation of the
function and proposed zig zag scanning.

1 files changed, 20 insertions, 16 deletions

diff --git a/src/module.c b/src/module.c
index ed178cecc..d77a8f956 100644
--- a/src/module.c
+++ b/src/module.c
@@ -610,23 +610,27 @@ void autoMemoryAdd(RedisModuleCtx *ctx, int type, void *ptr) {
 void autoMemoryFreed(RedisModuleCtx *ctx, int type, void *ptr) {
     if (!(ctx->flags & REDISMODULE_CTX_AUTO_MEMORY)) return;
 
-    int j;
-    for (j = ctx->amqueue_used - 1; j >= 0; j--) {
-        if (ctx->amqueue[j].type == type &&
-            ctx->amqueue[j].ptr == ptr)
-        {
-            ctx->amqueue[j].type = REDISMODULE_AM_FREED;
-            
-            /* Switch the freed element and the top element, to avoid growing
-             * the queue unnecessarily if we allocate/free in a loop */
-            if (j != ctx->amqueue_used-1) {
-                ctx->amqueue[j] = ctx->amqueue[ctx->amqueue_used-1];
-            }
-            /* Reduce the size of the queue because we either moved the top
-             * element elsewhere or freed it */ 
-            ctx->amqueue_used--;
+    int count = (ctx->amqueue_used+1)/2;
+    for (int j = 0; j < count; j++) {
+        for (int side = 0; side < 2; side++) {
+            /* For side = 0 check right side of the array, for
+             * side = 1 check the left side instead (zig-zag scanning). */
+            int i = (side == 0) ? (ctx->amqueue_used - 1 - j) : j;
+            if (ctx->amqueue[i].type == type &&
+                ctx->amqueue[i].ptr == ptr)
+            {
+                ctx->amqueue[i].type = REDISMODULE_AM_FREED;
 
-            break;
+                /* Switch the freed element and the top element, to avoid growing
+                 * the queue unnecessarily if we allocate/free in a loop */
+                if (i != ctx->amqueue_used-1) {
+                    ctx->amqueue[i] = ctx->amqueue[ctx->amqueue_used-1];
+                }
+                /* Reduce the size of the queue because we either moved the top
+                 * element elsewhere or freed it */
+                ctx->amqueue_used--;
+                return;
+            }
         }
     }
 }