From 62194c3e5dff8141813f9f63993516de98dd367f Mon Sep 17 00:00:00 2001
From: ruki <waruqi@gmail.com>
Date: Sun, 7 Apr 2024 23:07:41 +0800
Subject: improve dlist

---
 tests/modules/dlist/test.lua | 120 +++++++++++++++++++++++++++++++++++++++++++
 tests/modules/table/test.lua |   4 +-
 2 files changed, 122 insertions(+), 2 deletions(-)
 create mode 100644 tests/modules/dlist/test.lua

(limited to 'tests/modules')

diff --git a/tests/modules/dlist/test.lua b/tests/modules/dlist/test.lua
new file mode 100644
index 000000000..31f939aa2
--- /dev/null
+++ b/tests/modules/dlist/test.lua
@@ -0,0 +1,120 @@
+import("core.base.dlist")
+
+function test_push(t)
+    local d = dlist.new()
+    d:push({v = 1})
+    d:push({v = 2})
+    d:push({v = 3})
+    d:push({v = 4})
+    d:push({v = 5})
+    t:are_equal(d:first().v, 1)
+    t:are_equal(d:last().v, 5)
+    local idx = 1
+    for item in d:items() do
+        t:are_equal(item.v, idx)
+        idx = idx + 1
+    end
+end
+
+function test_insert(t)
+    local d = dlist.new()
+    local v3 = {v = 3}
+    d:insert({v = 1})
+    d:insert({v = 2})
+    d:insert(v3)
+    d:insert({v = 5})
+    d:insert({v = 4}, v3)
+    t:are_equal(d:first().v, 1)
+    t:are_equal(d:last().v, 5)
+    local idx = 1
+    for item in d:items() do
+        t:are_equal(item.v, idx)
+        idx = idx + 1
+    end
+end
+
+function test_remove(t)
+    local d = dlist.new()
+    local v3 = {v = 3}
+    d:insert({v = 1})
+    d:insert({v = 2})
+    d:insert(v3)
+    d:insert({v = 3})
+    d:insert({v = 4})
+    d:insert({v = 5})
+    d:remove(v3)
+    t:are_equal(d:first().v, 1)
+    t:are_equal(d:last().v, 5)
+    local idx = 1
+    for item in d:items() do
+        t:are_equal(item.v, idx)
+        idx = idx + 1
+    end
+end
+
+function test_remove_first(t)
+    local d = dlist.new()
+    d:push({v = 1})
+    d:push({v = 2})
+    d:push({v = 3})
+    d:push({v = 4})
+    d:push({v = 5})
+    d:remove_first()
+    t:are_equal(d:first().v, 2)
+    t:are_equal(d:last().v, 5)
+    local idx = 2
+    for item in d:items() do
+        t:are_equal(item.v, idx)
+        idx = idx + 1
+    end
+end
+
+function test_remove_last(t)
+    local d = dlist.new()
+    d:push({v = 1})
+    d:push({v = 2})
+    d:push({v = 3})
+    d:push({v = 4})
+    d:push({v = 5})
+    d:remove_last()
+    t:are_equal(d:first().v, 1)
+    t:are_equal(d:last().v, 4)
+    local idx = 1
+    for item in d:items() do
+        t:are_equal(item.v, idx)
+        idx = idx + 1
+    end
+end
+
+function test_insert_head(t)
+    local d = dlist.new()
+    d:push({v = 2})
+    d:push({v = 3})
+    d:push({v = 4})
+    d:push({v = 5})
+    d:insert_head({v = 1})
+    t:are_equal(d:first().v, 1)
+    t:are_equal(d:last().v, 5)
+    local idx = 1
+    for item in d:items() do
+        t:are_equal(item.v, idx)
+        idx = idx + 1
+    end
+end
+
+function test_insert_tail(t)
+    local d = dlist.new()
+    d:push({v = 1})
+    d:push({v = 2})
+    d:push({v = 3})
+    d:push({v = 4})
+    d:insert_tail({v = 5})
+    t:are_equal(d:first().v, 1)
+    t:are_equal(d:last().v, 5)
+    local idx = 1
+    for item in d:items() do
+        t:are_equal(item.v, idx)
+        idx = idx + 1
+    end
+end
+
diff --git a/tests/modules/table/test.lua b/tests/modules/table/test.lua
index 2b586e7a4..306d07eac 100644
--- a/tests/modules/table/test.lua
+++ b/tests/modules/table/test.lua
@@ -31,7 +31,7 @@ function test_unwrap(t)
 end
 
 function test_orderkeys(t)
-    -- sort by modulo 2 then from the smallest to largest 
+    -- sort by modulo 2 then from the smallest to largest
     local f = function(a, b)
         if a % 2 == 0 and b % 2 ~= 0 then
             return true
@@ -40,7 +40,7 @@ function test_orderkeys(t)
         end
         return a < b
     end
-    
+
     t:are_equal(table.orderkeys({[2] = 2, [1] = 1, [4] = 4, [3] = 3}, f), {2, 4, 1, 3})
     t:are_equal(table.orderkeys({[1] = 1, [2] = 2, [3] = 3, [4] = 4}), {1, 2 , 3, 4})
 end
-- 
cgit v1.3.1


From 2a99fd133daea2808253ff1d8545d53c700709af Mon Sep 17 00:00:00 2001
From: ruki <waruqi@gmail.com>
Date: Sun, 7 Apr 2024 23:13:30 +0800
Subject: rename dlist to list

---
 tests/modules/dlist/test.lua                       | 120 -----------
 tests/modules/list/test.lua                        | 120 +++++++++++
 xmake/core/base/dlist.lua                          | 226 ---------------------
 xmake/core/base/list.lua                           | 226 +++++++++++++++++++++
 .../sandbox/modules/import/core/base/dlist.lua     |   2 +-
 .../core/sandbox/modules/import/core/base/list.lua |  22 ++
 xmake/core/ui/panel.lua                            |   4 +-
 xmake/modules/private/async/jobpool.lua            |   4 +-
 8 files changed, 373 insertions(+), 351 deletions(-)
 delete mode 100644 tests/modules/dlist/test.lua
 create mode 100644 tests/modules/list/test.lua
 delete mode 100644 xmake/core/base/dlist.lua
 create mode 100644 xmake/core/base/list.lua
 create mode 100644 xmake/core/sandbox/modules/import/core/base/list.lua

(limited to 'tests/modules')

diff --git a/tests/modules/dlist/test.lua b/tests/modules/dlist/test.lua
deleted file mode 100644
index 31f939aa2..000000000
--- a/tests/modules/dlist/test.lua
+++ /dev/null
@@ -1,120 +0,0 @@
-import("core.base.dlist")
-
-function test_push(t)
-    local d = dlist.new()
-    d:push({v = 1})
-    d:push({v = 2})
-    d:push({v = 3})
-    d:push({v = 4})
-    d:push({v = 5})
-    t:are_equal(d:first().v, 1)
-    t:are_equal(d:last().v, 5)
-    local idx = 1
-    for item in d:items() do
-        t:are_equal(item.v, idx)
-        idx = idx + 1
-    end
-end
-
-function test_insert(t)
-    local d = dlist.new()
-    local v3 = {v = 3}
-    d:insert({v = 1})
-    d:insert({v = 2})
-    d:insert(v3)
-    d:insert({v = 5})
-    d:insert({v = 4}, v3)
-    t:are_equal(d:first().v, 1)
-    t:are_equal(d:last().v, 5)
-    local idx = 1
-    for item in d:items() do
-        t:are_equal(item.v, idx)
-        idx = idx + 1
-    end
-end
-
-function test_remove(t)
-    local d = dlist.new()
-    local v3 = {v = 3}
-    d:insert({v = 1})
-    d:insert({v = 2})
-    d:insert(v3)
-    d:insert({v = 3})
-    d:insert({v = 4})
-    d:insert({v = 5})
-    d:remove(v3)
-    t:are_equal(d:first().v, 1)
-    t:are_equal(d:last().v, 5)
-    local idx = 1
-    for item in d:items() do
-        t:are_equal(item.v, idx)
-        idx = idx + 1
-    end
-end
-
-function test_remove_first(t)
-    local d = dlist.new()
-    d:push({v = 1})
-    d:push({v = 2})
-    d:push({v = 3})
-    d:push({v = 4})
-    d:push({v = 5})
-    d:remove_first()
-    t:are_equal(d:first().v, 2)
-    t:are_equal(d:last().v, 5)
-    local idx = 2
-    for item in d:items() do
-        t:are_equal(item.v, idx)
-        idx = idx + 1
-    end
-end
-
-function test_remove_last(t)
-    local d = dlist.new()
-    d:push({v = 1})
-    d:push({v = 2})
-    d:push({v = 3})
-    d:push({v = 4})
-    d:push({v = 5})
-    d:remove_last()
-    t:are_equal(d:first().v, 1)
-    t:are_equal(d:last().v, 4)
-    local idx = 1
-    for item in d:items() do
-        t:are_equal(item.v, idx)
-        idx = idx + 1
-    end
-end
-
-function test_insert_head(t)
-    local d = dlist.new()
-    d:push({v = 2})
-    d:push({v = 3})
-    d:push({v = 4})
-    d:push({v = 5})
-    d:insert_head({v = 1})
-    t:are_equal(d:first().v, 1)
-    t:are_equal(d:last().v, 5)
-    local idx = 1
-    for item in d:items() do
-        t:are_equal(item.v, idx)
-        idx = idx + 1
-    end
-end
-
-function test_insert_tail(t)
-    local d = dlist.new()
-    d:push({v = 1})
-    d:push({v = 2})
-    d:push({v = 3})
-    d:push({v = 4})
-    d:insert_tail({v = 5})
-    t:are_equal(d:first().v, 1)
-    t:are_equal(d:last().v, 5)
-    local idx = 1
-    for item in d:items() do
-        t:are_equal(item.v, idx)
-        idx = idx + 1
-    end
-end
-
diff --git a/tests/modules/list/test.lua b/tests/modules/list/test.lua
new file mode 100644
index 000000000..b1679a304
--- /dev/null
+++ b/tests/modules/list/test.lua
@@ -0,0 +1,120 @@
+import("core.base.list")
+
+function test_push(t)
+    local d = list.new()
+    d:push({v = 1})
+    d:push({v = 2})
+    d:push({v = 3})
+    d:push({v = 4})
+    d:push({v = 5})
+    t:are_equal(d:first().v, 1)
+    t:are_equal(d:last().v, 5)
+    local idx = 1
+    for item in d:items() do
+        t:are_equal(item.v, idx)
+        idx = idx + 1
+    end
+end
+
+function test_insert(t)
+    local d = list.new()
+    local v3 = {v = 3}
+    d:insert({v = 1})
+    d:insert({v = 2})
+    d:insert(v3)
+    d:insert({v = 5})
+    d:insert({v = 4}, v3)
+    t:are_equal(d:first().v, 1)
+    t:are_equal(d:last().v, 5)
+    local idx = 1
+    for item in d:items() do
+        t:are_equal(item.v, idx)
+        idx = idx + 1
+    end
+end
+
+function test_remove(t)
+    local d = list.new()
+    local v3 = {v = 3}
+    d:insert({v = 1})
+    d:insert({v = 2})
+    d:insert(v3)
+    d:insert({v = 3})
+    d:insert({v = 4})
+    d:insert({v = 5})
+    d:remove(v3)
+    t:are_equal(d:first().v, 1)
+    t:are_equal(d:last().v, 5)
+    local idx = 1
+    for item in d:items() do
+        t:are_equal(item.v, idx)
+        idx = idx + 1
+    end
+end
+
+function test_remove_first(t)
+    local d = list.new()
+    d:push({v = 1})
+    d:push({v = 2})
+    d:push({v = 3})
+    d:push({v = 4})
+    d:push({v = 5})
+    d:remove_first()
+    t:are_equal(d:first().v, 2)
+    t:are_equal(d:last().v, 5)
+    local idx = 2
+    for item in d:items() do
+        t:are_equal(item.v, idx)
+        idx = idx + 1
+    end
+end
+
+function test_remove_last(t)
+    local d = list.new()
+    d:push({v = 1})
+    d:push({v = 2})
+    d:push({v = 3})
+    d:push({v = 4})
+    d:push({v = 5})
+    d:remove_last()
+    t:are_equal(d:first().v, 1)
+    t:are_equal(d:last().v, 4)
+    local idx = 1
+    for item in d:items() do
+        t:are_equal(item.v, idx)
+        idx = idx + 1
+    end
+end
+
+function test_insert_first(t)
+    local d = list.new()
+    d:push({v = 2})
+    d:push({v = 3})
+    d:push({v = 4})
+    d:push({v = 5})
+    d:insert_first({v = 1})
+    t:are_equal(d:first().v, 1)
+    t:are_equal(d:last().v, 5)
+    local idx = 1
+    for item in d:items() do
+        t:are_equal(item.v, idx)
+        idx = idx + 1
+    end
+end
+
+function test_insert_last(t)
+    local d = list.new()
+    d:push({v = 1})
+    d:push({v = 2})
+    d:push({v = 3})
+    d:push({v = 4})
+    d:insert_last({v = 5})
+    t:are_equal(d:first().v, 1)
+    t:are_equal(d:last().v, 5)
+    local idx = 1
+    for item in d:items() do
+        t:are_equal(item.v, idx)
+        idx = idx + 1
+    end
+end
+
diff --git a/xmake/core/base/dlist.lua b/xmake/core/base/dlist.lua
deleted file mode 100644
index 3b893a622..000000000
--- a/xmake/core/base/dlist.lua
+++ /dev/null
@@ -1,226 +0,0 @@
---!A cross-platform build utility based on Lua
---
--- Licensed under the Apache License, Version 2.0 (the "License");
--- you may not use this file except in compliance with the License.
--- You may obtain a copy of the License at
---
---     http://www.apache.org/licenses/LICENSE-2.0
---
--- Unless required by applicable law or agreed to in writing, software
--- distributed under the License is distributed on an "AS IS" BASIS,
--- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
--- See the License for the specific language governing permissions and
--- limitations under the License.
---
--- Copyright (C) 2015-present, TBOOX Open Source Group.
---
--- @author      ruki
--- @file        dlist.lua
---
-
--- load modules
-local object = require("base/object")
-
--- define module
-local dlist = dlist or object { _init = {"_length"} } {0}
-
--- clear list
-function dlist:clear()
-    self._length = 0
-    self._first  = nil
-    self._last   = nil
-end
-
--- insert item after the given item
-function dlist:insert(t, after)
-    if not after then
-        return self:insert_tail(t)
-    end
-    assert(t ~= after)
-    if after._next then
-        after._next._prev = t
-        t._next = after._next
-    else
-        self._last = t
-    end
-    t._prev = after
-    after._next = t
-    self._length = self._length + 1
-end
-
--- insert item in head
-function dlist:insert_head(t)
-    if self._first then
-        self._first._prev = t
-        t._next = self._first
-        self._first = t
-    else
-        self._first = t
-        self._last = t
-    end
-    self._length = self._length + 1
-end
-
--- insert item in tail
-function dlist:insert_tail(t)
-    if self._last then
-        self._last._next = t
-        t._prev = self._last
-        self._last = t
-    else
-        self._first = t
-        self._last = t
-    end
-    self._length = self._length + 1
-end
-
--- remove item
-function dlist:remove(t)
-    if t._next then
-        if t._prev then
-            t._next._prev = t._prev
-            t._prev._next = t._next
-        else
-            assert(t == self._first)
-            t._next._prev = nil
-            self._first = t._next
-        end
-    elseif t._prev then
-        assert(t == self._last)
-        t._prev._next = nil
-        self._last = t._prev
-    else
-        assert(t == self._first and t == self._last)
-        self._first = nil
-        self._last = nil
-    end
-    t._next = nil
-    t._prev = nil
-    self._length = self._length - 1
-    return t
-end
-
--- remove the first item
-function dlist:remove_first()
-    if not self._first then
-        return
-    end
-    local t = self._first
-    if t._next then
-        t._next._prev = nil
-        self._first = t._next
-        t._next = nil
-    else
-        self._first = nil
-        self._last = nil
-    end
-    self._length = self._length - 1
-    return t
-end
-
--- remove last item
-function dlist:remove_last()
-    if not self._last then
-        return
-    end
-    local t = self._last
-    if t._prev then
-        t._prev._next = nil
-        self._last = t._prev
-        t._prev = nil
-    else
-        self._first = nil
-        self._last = nil
-    end
-    self._length = self._length - 1
-    return t
-end
-
--- push item to tail
-function dlist:push(t)
-    self:insert_tail(t)
-end
-
--- pop item from tail
-function dlist:pop()
-    self:remove_last()
-end
-
--- shift item: 1 2 3 <- 2 3
-function dlist:shift()
-    self:remove_first()
-end
-
--- unshift item: 1 2 -> t 1 2
-function dlist:unshift(t)
-    self:insert_head(t)
-end
-
--- get first item
-function dlist:first()
-    return self._first
-end
-
--- get last item
-function dlist:last()
-    return self._last
-end
-
--- get next item
-function dlist:next(last)
-    if last then
-        return last._next
-    else
-        return self._first
-    end
-end
-
--- get the previous item
-function dlist:prev(last)
-    if last then
-        return last._prev
-    else
-        return self._last
-    end
-end
-
--- get list size
-function dlist:size()
-    return self._length
-end
-
--- is empty?
-function dlist:empty()
-    return self:size() == 0
-end
-
--- get items
---
--- e.g.
---
--- for item in dlist:items() do
---     print(item)
--- end
---
-function dlist:items()
-    local iter = function (list, item)
-        return list:next(item)
-    end
-    return iter, self, nil
-end
-
--- get reverse items
-function dlist:ritems()
-    local iter = function (list, item)
-        return list:prev(item)
-    end
-    return iter, self, nil
-end
-
--- new dlist
-function dlist.new()
-    return dlist()
-end
-
--- return module: dlist
-return dlist
diff --git a/xmake/core/base/list.lua b/xmake/core/base/list.lua
new file mode 100644
index 000000000..e6958f74d
--- /dev/null
+++ b/xmake/core/base/list.lua
@@ -0,0 +1,226 @@
+--!A cross-platform build utility based on Lua
+--
+-- Licensed under the Apache License, Version 2.0 (the "License");
+-- you may not use this file except in compliance with the License.
+-- You may obtain a copy of the License at
+--
+--     http://www.apache.org/licenses/LICENSE-2.0
+--
+-- Unless required by applicable law or agreed to in writing, software
+-- distributed under the License is distributed on an "AS IS" BASIS,
+-- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+-- See the License for the specific language governing permissions and
+-- limitations under the License.
+--
+-- Copyright (C) 2015-present, TBOOX Open Source Group.
+--
+-- @author      ruki
+-- @file        list.lua
+--
+
+-- load modules
+local object = require("base/object")
+
+-- define module
+local list = list or object { _init = {"_length"} } {0}
+
+-- clear list
+function list:clear()
+    self._length = 0
+    self._first  = nil
+    self._last   = nil
+end
+
+-- insert item after the given item
+function list:insert(t, after)
+    if not after then
+        return self:insert_last(t)
+    end
+    assert(t ~= after)
+    if after._next then
+        after._next._prev = t
+        t._next = after._next
+    else
+        self._last = t
+    end
+    t._prev = after
+    after._next = t
+    self._length = self._length + 1
+end
+
+-- insert the first item in head
+function list:insert_first(t)
+    if self._first then
+        self._first._prev = t
+        t._next = self._first
+        self._first = t
+    else
+        self._first = t
+        self._last = t
+    end
+    self._length = self._length + 1
+end
+
+-- insert the last item in tail
+function list:insert_last(t)
+    if self._last then
+        self._last._next = t
+        t._prev = self._last
+        self._last = t
+    else
+        self._first = t
+        self._last = t
+    end
+    self._length = self._length + 1
+end
+
+-- remove item
+function list:remove(t)
+    if t._next then
+        if t._prev then
+            t._next._prev = t._prev
+            t._prev._next = t._next
+        else
+            assert(t == self._first)
+            t._next._prev = nil
+            self._first = t._next
+        end
+    elseif t._prev then
+        assert(t == self._last)
+        t._prev._next = nil
+        self._last = t._prev
+    else
+        assert(t == self._first and t == self._last)
+        self._first = nil
+        self._last = nil
+    end
+    t._next = nil
+    t._prev = nil
+    self._length = self._length - 1
+    return t
+end
+
+-- remove the first item
+function list:remove_first()
+    if not self._first then
+        return
+    end
+    local t = self._first
+    if t._next then
+        t._next._prev = nil
+        self._first = t._next
+        t._next = nil
+    else
+        self._first = nil
+        self._last = nil
+    end
+    self._length = self._length - 1
+    return t
+end
+
+-- remove last item
+function list:remove_last()
+    if not self._last then
+        return
+    end
+    local t = self._last
+    if t._prev then
+        t._prev._next = nil
+        self._last = t._prev
+        t._prev = nil
+    else
+        self._first = nil
+        self._last = nil
+    end
+    self._length = self._length - 1
+    return t
+end
+
+-- push item to tail
+function list:push(t)
+    self:insert_last(t)
+end
+
+-- pop item from tail
+function list:pop()
+    self:remove_last()
+end
+
+-- shift item: 1 2 3 <- 2 3
+function list:shift()
+    self:remove_first()
+end
+
+-- unshift item: 1 2 -> t 1 2
+function list:unshift(t)
+    self:insert_first(t)
+end
+
+-- get first item
+function list:first()
+    return self._first
+end
+
+-- get last item
+function list:last()
+    return self._last
+end
+
+-- get next item
+function list:next(last)
+    if last then
+        return last._next
+    else
+        return self._first
+    end
+end
+
+-- get the previous item
+function list:prev(last)
+    if last then
+        return last._prev
+    else
+        return self._last
+    end
+end
+
+-- get list size
+function list:size()
+    return self._length
+end
+
+-- is empty?
+function list:empty()
+    return self:size() == 0
+end
+
+-- get items
+--
+-- e.g.
+--
+-- for item in list:items() do
+--     print(item)
+-- end
+--
+function list:items()
+    local iter = function (list, item)
+        return list:next(item)
+    end
+    return iter, self, nil
+end
+
+-- get reverse items
+function list:ritems()
+    local iter = function (list, item)
+        return list:prev(item)
+    end
+    return iter, self, nil
+end
+
+-- new list
+function list.new()
+    return list()
+end
+
+-- return module: list
+return list
diff --git a/xmake/core/sandbox/modules/import/core/base/dlist.lua b/xmake/core/sandbox/modules/import/core/base/dlist.lua
index 25047206d..924d27ab1 100644
--- a/xmake/core/sandbox/modules/import/core/base/dlist.lua
+++ b/xmake/core/sandbox/modules/import/core/base/dlist.lua
@@ -19,4 +19,4 @@
 --
 
 -- return module
-return require("base/dlist")
+return require("base/list")
diff --git a/xmake/core/sandbox/modules/import/core/base/list.lua b/xmake/core/sandbox/modules/import/core/base/list.lua
new file mode 100644
index 000000000..852fd5231
--- /dev/null
+++ b/xmake/core/sandbox/modules/import/core/base/list.lua
@@ -0,0 +1,22 @@
+--!A cross-platform build utility based on Lua
+--
+-- Licensed under the Apache License, Version 2.0 (the "License");
+-- you may not use this file except in compliance with the License.
+-- You may obtain a copy of the License at
+--
+--     http://www.apache.org/licenses/LICENSE-2.0
+--
+-- Unless required by applicable law or agreed to in writing, software
+-- distributed under the License is distributed on an "AS IS" BASIS,
+-- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+-- See the License for the specific language governing permissions and
+-- limitations under the License.
+--
+-- Copyright (C) 2015-present, TBOOX Open Source Group.
+--
+-- @author      ruki
+-- @file        list.lua
+--
+
+-- return module
+return require("base/list")
diff --git a/xmake/core/ui/panel.lua b/xmake/core/ui/panel.lua
index 7baef5c3a..244aae073 100644
--- a/xmake/core/ui/panel.lua
+++ b/xmake/core/ui/panel.lua
@@ -26,7 +26,7 @@ local event  = require("ui/event")
 local point  = require("ui/point")
 local curses = require("ui/curses")
 local action = require("ui/action")
-local dlist  = require("base/dlist")
+local list   = require("base/list")
 
 -- define module
 local panel = panel or view()
@@ -44,7 +44,7 @@ function panel:init(name, bounds)
     self:option_set("selectable", true)
 
     -- init child views
-    self._VIEWS = dlist.new()
+    self._VIEWS = list.new()
 
     -- init views cache
     self._VIEWS_CACHE = {}
diff --git a/xmake/modules/private/async/jobpool.lua b/xmake/modules/private/async/jobpool.lua
index 653be2328..342cc096f 100644
--- a/xmake/modules/private/async/jobpool.lua
+++ b/xmake/modules/private/async/jobpool.lua
@@ -20,7 +20,7 @@
 
 -- imports
 import("core.base.object")
-import("core.base.dlist")
+import("core.base.list")
 import("core.base.hashset")
 
 -- define module
@@ -235,5 +235,5 @@ end
 
 -- new a jobpool
 function new()
-    return jobpool {0, {name = "root"}, dlist.new(), {}}
+    return jobpool {0, {name = "root"}, list.new(), {}}
 end
-- 
cgit v1.3.1


From 14f497e354aa9ec61f54e201d4db211da4d2086f Mon Sep 17 00:00:00 2001
From: ruki <waruqi@gmail.com>
Date: Mon, 8 Apr 2024 23:06:48 +0800
Subject: improve jobpool

---
 tests/modules/list/test.lua             |  42 +++++++++++
 xmake/modules/async/runjobs.lua         |  25 +++----
 xmake/modules/private/async/jobpool.lua | 123 ++++++++++++++++++++++++--------
 3 files changed, 145 insertions(+), 45 deletions(-)

(limited to 'tests/modules')

diff --git a/tests/modules/list/test.lua b/tests/modules/list/test.lua
index b1679a304..4a4e81fd0 100644
--- a/tests/modules/list/test.lua
+++ b/tests/modules/list/test.lua
@@ -86,6 +86,48 @@ function test_remove_last(t)
     end
 end
 
+function test_for_remove(t)
+    local d = list.new()
+    d:push({v = 1})
+    d:push({v = 2})
+    d:push({v = 3})
+    d:push({v = 4})
+    d:push({v = 5})
+    t:are_equal(d:first().v, 1)
+    t:are_equal(d:last().v, 5)
+    local idx = 1
+    local item = d:first()
+    while item ~= nil do
+        local next = d:next(item)
+        t:are_equal(item.v, idx)
+        d:remove(item)
+        item = next
+        idx = idx + 1
+    end
+    t:require(d:empty())
+end
+
+function test_rfor_remove(t)
+    local d = list.new()
+    d:push({v = 1})
+    d:push({v = 2})
+    d:push({v = 3})
+    d:push({v = 4})
+    d:push({v = 5})
+    t:are_equal(d:first().v, 1)
+    t:are_equal(d:last().v, 5)
+    local idx = 5
+    local item = d:last()
+    while item ~= nil do
+        local prev = d:prev(item)
+        t:are_equal(item.v, idx)
+        d:remove(item)
+        item = prev
+        idx = idx - 1
+    end
+    t:require(d:empty())
+end
+
 function test_insert_first(t)
     local d = list.new()
     d:push({v = 2})
diff --git a/xmake/modules/async/runjobs.lua b/xmake/modules/async/runjobs.lua
index 6d19efe17..1508a71d8 100644
--- a/xmake/modules/async/runjobs.lua
+++ b/xmake/modules/async/runjobs.lua
@@ -154,7 +154,6 @@ function main(name, jobs, opt)
     -- run jobs
     local index = 0
     local count = 0
-    local job_pending = nil
     local abort = false
     local abort_errors
     local progress_wrapper = {}
@@ -188,21 +187,18 @@ function main(name, jobs, opt)
             while index < total_max do
 
                 -- uses job pool?
+                local job
                 local jobname
                 local distccjob = false
                 if not jobs_cb then
 
-                    -- get job
-                    local job
-                    if job_pending then
-                        job = job_pending
-                    else
-                        job = jobs:pop()
-                    end
+                    -- get free job
+                    job = jobs:getfree()
                     if not job then
                         break
                     end
 
+                    -- TODO
                     -- we can only continue to run the job with distcc if local jobs are full
                     if distcc and index >= local_max then
                         if job.distcc then
@@ -216,7 +212,6 @@ function main(name, jobs, opt)
                     -- get run function
                     jobfunc = job.run
                     jobname = job.name
-                    job_pending = nil
                 else
                     jobname = tostring(index)
                 end
@@ -243,6 +238,9 @@ function main(name, jobs, opt)
                                 end
                                 count = count + 1
                                 jobfunc(i, total, {progress = progress_wrapper})
+                                if job then
+                                    jobs:remove(job)
+                                end
                                 print("finished", jobname)
                             end
                             running_jobs_indices[i] = nil
@@ -283,13 +281,8 @@ function main(name, jobs, opt)
             end
         end)
 
-        -- only need one job exited if be same priority
-        if priority_curr == priority_prev then
-            scheduler.co_group_wait(group_name, {limit = 1})
-        else
-            -- need to wait all running jobs exited first if be different priority
-            scheduler.co_group_wait(group_name)
-        end
+        -- wait for free jobs
+        scheduler.co_group_wait(group_name, {limit = 1})
     end
 
     -- wait all jobs exited
diff --git a/xmake/modules/private/async/jobpool.lua b/xmake/modules/private/async/jobpool.lua
index 10fe90bbe..51c76847f 100644
--- a/xmake/modules/private/async/jobpool.lua
+++ b/xmake/modules/private/async/jobpool.lua
@@ -24,7 +24,12 @@ import("core.base.list")
 import("core.base.hashset")
 
 -- define module
-local jobpool = jobpool or object {_init = {"_size", "_rootjob", "_leafjobs", "_poprefs"}}
+local jobpool = jobpool or object {_init = {"_size", "_rootjob", "_leafjobs"}}
+
+-- the job status
+local JOB_STATUS_FREE     = 1
+local JOB_STATUS_PENDING  = 2
+local JOB_STATUS_FINISHED = 3
 
 -- get jobs size
 function jobpool:size()
@@ -46,7 +51,7 @@ end
 --
 function jobpool:newjob(name, run, opt)
     opt = opt or {}
-    return {name = name, run = run, distcc = opt.distcc}
+    return {name = name, run = run, distcc = opt.distcc, status = JOB_STATUS_FREE}
 end
 
 -- add run job to the given job node
@@ -61,7 +66,7 @@ end
 --
 function jobpool:addjob(name, run, opt)
     opt = opt or {}
-    return self:add({name = name, run = run, distcc = opt.distcc}, opt.rootjob)
+    return self:add({name = name, run = run, distcc = opt.distcc, status = JOB_STATUS_FREE}, opt.rootjob)
 end
 
 -- add job to the given job node
@@ -96,27 +101,80 @@ function jobpool:add(job, rootjob)
     return job
 end
 
--- pop job without deps at leaf node
-function jobpool:pop()
+-- has free jobs?
+function jobpool:hasfree()
+    if self:size() == 0 then
+        return
+    end
+
+    -- peak a free job from the leaf jobs
+    local leafjobs = self:_getleafjobs()
+    if not leafjobs:empty() then
+        if self._nextfree then
+            return true
+        end
+        local job = leafjobs:last()
+        while job ~= nil do
+            local prevjob = leafjobs:prev(job)
+            if self:_isfree(job) then
+                self._nextfree = job
+                return true
+            elseif job.group or job.status == JOB_STATUS_FINISHED then
+                self:remove(job)
+            end
+            job = prevjob
+        end
+    end
+end
 
-    -- no jobs?
+-- get a free job from the leaf jobs
+function jobpool:getfree()
     if self:size() == 0 then
         return
     end
 
-    -- init leaf jobs first
-    local leafjobs = self._leafjobs
-    if leafjobs:empty() then
-        local refs = {}
-        self:_genleafjobs(self:rootjob(), leafjobs, refs)
+    -- get a free job from the leaf jobs
+    local leafjobs = self:_getleafjobs()
+    if not leafjobs:empty() then
+        if self._nextfree then
+            local job = self._nextfree
+            local nextfree = leafjobs:prev(job)
+            if nextfree ~= job and self:_isfree(nextfree) then
+                self._nextfree = nextfree
+            else
+                self._nextfree = nil
+            end
+            job.status = JOB_STATUS_PENDING
+            return job
+        end
+        local job = leafjobs:last()
+        while job ~= nil do
+            local prevjob = leafjobs:prev(job)
+            if self:_isfree(job) then
+                local nextfree = prevjob
+                if nextfree ~= job and self:_isfree(nextfree) then
+                    self._nextfree = nextfree
+                end
+                job.status = JOB_STATUS_PENDING
+                return job
+            elseif job.group or job.status == JOB_STATUS_FINISHED then
+                self:remove(job)
+            end
+            job = prevjob
+        end
     end
+end
 
-    -- pop a job from the leaf jobs
+-- remove the given job from the leaf jobs
+function jobpool:remove(job)
+    assert(self:size() > 0)
+    local leafjobs = self:_getleafjobs()
     if not leafjobs:empty() then
+        assert(job ~= self._nextfree)
 
-        -- get job
-        local job = leafjobs:last()
-        leafjobs:remove_last()
+        -- remove this job from leaf jobs
+        job.status = JOB_STATUS_FINISHED
+        leafjobs:remove(job)
 
         -- get parents node
         local parents = assert(job._parents, "invalid job without parents node!")
@@ -133,19 +191,6 @@ function jobpool:pop()
                 end
             end
         end
-
-        -- is group node or referenced node (it has been popped once) ?
-        local poprefs = self._poprefs
-        local jobkey = tostring(job)
-        if job.group or poprefs[jobkey] then
-            -- pop the next real job
-            return self:pop()
-        else
-            -- pop this job
-            self._size = self._size - 1
-            poprefs[jobkey] = true
-            return job
-        end
     end
 end
 
@@ -177,6 +222,26 @@ function jobpool:group_leave()
     end
 end
 
+-- is free job?
+-- we need to ignore group node (empty job) and referenced node (finished job)
+function jobpool:_isfree(job)
+    if job and job.status == JOB_STATUS_FREE and not job.group then
+        return true
+    end
+end
+
+-- get leaf jobs
+function jobpool:_getleafjobs()
+    local leafjobs = self._leafjobs
+    if leafjobs == nil then
+        leafjobs = list.new()
+        local refs = {}
+        self:_genleafjobs(self:rootjob(), leafjobs, refs)
+        self._leafjobs = leafjobs
+    end
+    return leafjobs
+end
+
 -- generate all leaf jobs from the given job
 function jobpool:_genleafjobs(job, leafjobs, refs)
     local deps = job._deps
@@ -231,5 +296,5 @@ end
 
 -- new a jobpool
 function new()
-    return jobpool {0, {name = "root"}, list.new(), {}}
+    return jobpool {0, {name = "root"}, nil}
 end
-- 
cgit v1.3.1