[Tarantool-patches] [PATCH 1/9] rlist: move rlist to a new module

[Vladislav Shpilevoy via Tarantool-patches <tarantool-patches@dev.tarantool.org>]

Rlist in storage/init.lua implemented a container similar to rlist
in libsmall in Tarantool core. Doubly-linked list.

It does not depend on anything in storage/init.lua, and should
have been done in a separate module from the beginning.

Now init.lua is going to grow even more in scope of map-reduce
feature, beyond 3k lines if nothing would be moved out. It was
decided (by me) that it crosses the border of when it is time to
split init.lua into separate modules.

The patch takes the low hanging fruit by moving rlist into its
own module.
---
 test/unit/rebalancer.result   |  99 -----------------------------
 test/unit/rebalancer.test.lua |  27 --------
 test/unit/rlist.result        | 114 ++++++++++++++++++++++++++++++++++
 test/unit/rlist.test.lua      |  33 ++++++++++
 vshard/rlist.lua              |  53 ++++++++++++++++
 vshard/storage/init.lua       |  68 +++-----------------
 6 files changed, 208 insertions(+), 186 deletions(-)
 create mode 100644 test/unit/rlist.result
 create mode 100644 test/unit/rlist.test.lua
 create mode 100644 vshard/rlist.lua

diff --git a/test/unit/rebalancer.result b/test/unit/rebalancer.result
index 2fb30e2..19aa480 100644
--- a/test/unit/rebalancer.result
+++ b/test/unit/rebalancer.result
@@ -1008,105 +1008,6 @@ build_routes(replicasets)
 -- the latter is a dispenser. It is a structure which hands out
 -- destination UUIDs in a round-robin manner to worker fibers.
 --
-list = rlist.new()
----
-...
-list
----
-- count: 0
-...
-obj1 = {i = 1}
----
-...
-rlist.remove(list, obj1)
----
-...
-list
----
-- count: 0
-...
-rlist.add_tail(list, obj1)
----
-...
-list
----
-- count: 1
-  last: &0
-    i: 1
-  first: *0
-...
-rlist.remove(list, obj1)
----
-...
-list
----
-- count: 0
-...
-obj1
----
-- i: 1
-...
-rlist.add_tail(list, obj1)
----
-...
-obj2 = {i = 2}
----
-...
-rlist.add_tail(list, obj2)
----
-...
-list
----
-- count: 2
-  last: &0
-    i: 2
-    prev: &1
-      i: 1
-      next: *0
-  first: *1
-...
-obj3 = {i = 3}
----
-...
-rlist.add_tail(list, obj3)
----
-...
-list
----
-- count: 3
-  last: &0
-    i: 3
-    prev: &1
-      i: 2
-      next: *0
-      prev: &2
-        i: 1
-        next: *1
-  first: *2
-...
-rlist.remove(list, obj2)
----
-...
-list
----
-- count: 2
-  last: &0
-    i: 3
-    prev: &1
-      i: 1
-      next: *0
-  first: *1
-...
-rlist.remove(list, obj1)
----
-...
-list
----
-- count: 1
-  last: &0
-    i: 3
-  first: *0
-...
 d = dispenser.create({uuid = 15})
 ---
 ...
diff --git a/test/unit/rebalancer.test.lua b/test/unit/rebalancer.test.lua
index a4e18c1..8087d42 100644
--- a/test/unit/rebalancer.test.lua
+++ b/test/unit/rebalancer.test.lua
@@ -246,33 +246,6 @@ build_routes(replicasets)
 -- the latter is a dispenser. It is a structure which hands out
 -- destination UUIDs in a round-robin manner to worker fibers.
 --
-list = rlist.new()
-list
-
-obj1 = {i = 1}
-rlist.remove(list, obj1)
-list
-
-rlist.add_tail(list, obj1)
-list
-
-rlist.remove(list, obj1)
-list
-obj1
-
-rlist.add_tail(list, obj1)
-obj2 = {i = 2}
-rlist.add_tail(list, obj2)
-list
-obj3 = {i = 3}
-rlist.add_tail(list, obj3)
-list
-
-rlist.remove(list, obj2)
-list
-rlist.remove(list, obj1)
-list
-
 d = dispenser.create({uuid = 15})
 dispenser.pop(d)
 for i = 1, 14 do assert(dispenser.pop(d) == 'uuid', i) end
diff --git a/test/unit/rlist.result b/test/unit/rlist.result
new file mode 100644
index 0000000..c8aabc0
--- /dev/null
+++ b/test/unit/rlist.result
@@ -0,0 +1,114 @@
+-- test-run result file version 2
+--
+-- gh-161: parallel rebalancer. One of the most important part of the latter is
+-- a dispenser. It is a structure which hands out destination UUIDs in a
+-- round-robin manner to worker fibers. It uses rlist data structure.
+--
+rlist = require('vshard.rlist')
+ | ---
+ | ...
+
+list = rlist.new()
+ | ---
+ | ...
+list
+ | ---
+ | - count: 0
+ | ...
+
+obj1 = {i = 1}
+ | ---
+ | ...
+list:remove(obj1)
+ | ---
+ | ...
+list
+ | ---
+ | - count: 0
+ | ...
+
+list:add_tail(obj1)
+ | ---
+ | ...
+list
+ | ---
+ | - count: 1
+ |   last: &0
+ |     i: 1
+ |   first: *0
+ | ...
+
+list:remove(obj1)
+ | ---
+ | ...
+list
+ | ---
+ | - count: 0
+ | ...
+obj1
+ | ---
+ | - i: 1
+ | ...
+
+list:add_tail(obj1)
+ | ---
+ | ...
+obj2 = {i = 2}
+ | ---
+ | ...
+list:add_tail(obj2)
+ | ---
+ | ...
+list
+ | ---
+ | - count: 2
+ |   last: &0
+ |     i: 2
+ |     prev: &1
+ |       i: 1
+ |       next: *0
+ |   first: *1
+ | ...
+obj3 = {i = 3}
+ | ---
+ | ...
+list:add_tail(obj3)
+ | ---
+ | ...
+list
+ | ---
+ | - count: 3
+ |   last: &0
+ |     i: 3
+ |     prev: &1
+ |       i: 2
+ |       next: *0
+ |       prev: &2
+ |         i: 1
+ |         next: *1
+ |   first: *2
+ | ...
+
+list:remove(obj2)
+ | ---
+ | ...
+list
+ | ---
+ | - count: 2
+ |   last: &0
+ |     i: 3
+ |     prev: &1
+ |       i: 1
+ |       next: *0
+ |   first: *1
+ | ...
+list:remove(obj1)
+ | ---
+ | ...
+list
+ | ---
+ | - count: 1
+ |   last: &0
+ |     i: 3
+ |   first: *0
+ | ...
diff --git a/test/unit/rlist.test.lua b/test/unit/rlist.test.lua
new file mode 100644
index 0000000..db52955
--- /dev/null
+++ b/test/unit/rlist.test.lua
@@ -0,0 +1,33 @@
+--
+-- gh-161: parallel rebalancer. One of the most important part of the latter is
+-- a dispenser. It is a structure which hands out destination UUIDs in a
+-- round-robin manner to worker fibers. It uses rlist data structure.
+--
+rlist = require('vshard.rlist')
+
+list = rlist.new()
+list
+
+obj1 = {i = 1}
+list:remove(obj1)
+list
+
+list:add_tail(obj1)
+list
+
+list:remove(obj1)
+list
+obj1
+
+list:add_tail(obj1)
+obj2 = {i = 2}
+list:add_tail(obj2)
+list
+obj3 = {i = 3}
+list:add_tail(obj3)
+list
+
+list:remove(obj2)
+list
+list:remove(obj1)
+list
diff --git a/vshard/rlist.lua b/vshard/rlist.lua
new file mode 100644
index 0000000..4be5382
--- /dev/null
+++ b/vshard/rlist.lua
@@ -0,0 +1,53 @@
+--
+-- A subset of rlist methods from the main repository. Rlist is a
+-- doubly linked list, and is used here to implement a queue of
+-- routes in the parallel rebalancer.
+--
+local rlist_mt = {}
+
+function rlist_mt.add_tail(rlist, object)
+    local last = rlist.last
+    if last then
+        last.next = object
+        object.prev = last
+    else
+        rlist.first = object
+    end
+    rlist.last = object
+    rlist.count = rlist.count + 1
+end
+
+function rlist_mt.remove(rlist, object)
+    local prev = object.prev
+    local next = object.next
+    local belongs_to_list = false
+    if prev then
+        belongs_to_list = true
+        prev.next = next
+    end
+    if next then
+        belongs_to_list = true
+        next.prev = prev
+    end
+    object.prev = nil
+    object.next = nil
+    if rlist.last == object then
+        belongs_to_list = true
+        rlist.last = prev
+    end
+    if rlist.first == object then
+        belongs_to_list = true
+        rlist.first = next
+    end
+    if belongs_to_list then
+        rlist.count = rlist.count - 1
+    end
+end
+
+local function rlist_new()
+    return setmetatable({count = 0}, {__index = rlist_mt})
+end
+
+return {
+    new = rlist_new,
+}
diff --git a/vshard/storage/init.lua b/vshard/storage/init.lua
index 5464824..1b48bf1 100644
--- a/vshard/storage/init.lua
+++ b/vshard/storage/init.lua
@@ -13,12 +13,13 @@ if rawget(_G, MODULE_INTERNALS) then
         'vshard.consts', 'vshard.error', 'vshard.cfg',
         'vshard.replicaset', 'vshard.util',
         'vshard.storage.reload_evolution',
-        'vshard.lua_gc',
+        'vshard.lua_gc', 'vshard.rlist'
     }
     for _, module in pairs(vshard_modules) do
         package.loaded[module] = nil
     end
 end
+local rlist = require('vshard.rlist')
 local consts = require('vshard.consts')
 local lerror = require('vshard.error')
 local lcfg = require('vshard.cfg')
@@ -1786,54 +1787,6 @@ local function rebalancer_build_routes(replicasets)
     return bucket_routes
 end
 
---
--- A subset of rlist methods from the main repository. Rlist is a
--- doubly linked list, and is used here to implement a queue of
--- routes in the parallel rebalancer.
---
-local function rlist_new()
-    return {count = 0}
-end
-
-local function rlist_add_tail(rlist, object)
-    local last = rlist.last
-    if last then
-        last.next = object
-        object.prev = last
-    else
-        rlist.first = object
-    end
-    rlist.last = object
-    rlist.count = rlist.count + 1
-end
-
-local function rlist_remove(rlist, object)
-    local prev = object.prev
-    local next = object.next
-    local belongs_to_list = false
-    if prev then
-        belongs_to_list = true
-        prev.next = next
-    end
-    if next then
-        belongs_to_list = true
-        next.prev = prev
-    end
-    object.prev = nil
-    object.next = nil
-    if rlist.last == object then
-        belongs_to_list = true
-        rlist.last = prev
-    end
-    if rlist.first == object then
-        belongs_to_list = true
-        rlist.first = next
-    end
-    if belongs_to_list then
-        rlist.count = rlist.count - 1
-    end
-end
-
 --
 -- Dispenser is a container of routes received from the
 -- rebalancer. Its task is to hand out the routes to worker fibers
@@ -1842,7 +1795,7 @@ end
 -- receiver nodes.
 --
 local function route_dispenser_create(routes)
-    local rlist = rlist_new()
+    local rlist = rlist.new()
     local map = {}
     for uuid, bucket_count in pairs(routes) do
         local new = {
@@ -1873,7 +1826,7 @@ local function route_dispenser_create(routes)
         --    the main applier fiber does some analysis on the
         --    destinations.
         map[uuid] = new
-        rlist_add_tail(rlist, new)
+        rlist:add_tail(new)
     end
     return {
         rlist = rlist,
@@ -1892,7 +1845,7 @@ local function route_dispenser_put(dispenser, uuid)
         local bucket_count = dst.bucket_count + 1
         dst.bucket_count = bucket_count
         if bucket_count == 1 then
-            rlist_add_tail(dispenser.rlist, dst)
+            dispenser.rlist:add_tail(dst)
         end
     end
 end
@@ -1909,7 +1862,7 @@ local function route_dispenser_skip(dispenser, uuid)
     local dst = map[uuid]
     if dst then
         map[uuid] = nil
-        rlist_remove(dispenser.rlist, dst)
+        dispenser.rlist:remove(dst)
     end
 end
 
@@ -1952,9 +1905,9 @@ local function route_dispenser_pop(dispenser)
     if dst then
         local bucket_count = dst.bucket_count - 1
         dst.bucket_count = bucket_count
-        rlist_remove(rlist, dst)
+        rlist:remove(dst)
         if bucket_count > 0 then
-            rlist_add_tail(rlist, dst)
+            rlist:add_tail(dst)
         end
         return dst.uuid
     end
@@ -2742,11 +2695,6 @@ M.route_dispenser = {
     pop = route_dispenser_pop,
     sent = route_dispenser_sent,
 }
-M.rlist = {
-    new = rlist_new,
-    add_tail = rlist_add_tail,
-    remove = rlist_remove,
-}
 M.schema_latest_version = schema_latest_version
 M.schema_current_version = schema_current_version
 M.schema_upgrade_master = schema_upgrade_master
-- 
2.24.3 (Apple Git-128)