improve dlist

6 files changed, 211 insertions, 86 deletions

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
diff --git a/xmake/core/base/dlist.lua b/xmake/core/base/dlist.lua
index 7967d2afe..3b893a622 100644
--- a/xmake/core/base/dlist.lua
+++ b/xmake/core/base/dlist.lua
@@ -31,25 +31,10 @@ function dlist:clear()
     self._last   = nil
 end
 
--- push item to tail
-function dlist:push(t)
-    assert(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
-
 -- insert item after the given item
 function dlist:insert(t, after)
-    assert(t)
     if not after then
-        return self:push(t)
+        return self:insert_tail(t)
     end
     assert(t ~= after)
     if after._next then
@@ -63,41 +48,8 @@ function dlist:insert(t, after)
     self._length = self._length + 1
 end
 
--- pop item from tail
-function dlist:pop()
-    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
-
--- shift item: 1 2 3 <- 2 3
-function dlist:shift()
-    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
-
--- unshift item: 1 2 -> t 1 2
-function dlist:unshift(t)
-    assert(t)
+-- insert item in head
+function dlist:insert_head(t)
     if self._first then
         self._first._prev = t
         t._next = self._first
@@ -109,9 +61,21 @@ function dlist:unshift(t)
     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)
-    assert(t)
     if t._next then
         if t._prev then
             t._next._prev = t._prev
@@ -136,6 +100,62 @@ function dlist:remove(t)
     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
@@ -183,25 +203,17 @@ end
 -- end
 --
 function dlist:items()
-
-    -- init iterator
     local iter = function (list, item)
         return list:next(item)
     end
-
-    -- return iterator and initialized state
     return iter, self, nil
 end
 
 -- get reverse items
 function dlist:ritems()
-
-    -- init iterator
     local iter = function (list, item)
         return list:prev(item)
     end
-
-    -- return iterator and initialized state
     return iter, self, nil
 end
 
diff --git a/xmake/modules/async/runjobs.lua b/xmake/modules/async/runjobs.lua
index 299b868df..6d19efe17 100644
--- a/xmake/modules/async/runjobs.lua
+++ b/xmake/modules/async/runjobs.lua
@@ -154,8 +154,6 @@ function main(name, jobs, opt)
     -- run jobs
     local index = 0
     local count = 0
-    local priority_prev = 0
-    local priority_curr = 0
     local job_pending = nil
     local abort = false
     local abort_errors
@@ -194,26 +192,17 @@ function main(name, jobs, opt)
                 local distccjob = false
                 if not jobs_cb then
 
-                    -- get job priority
-                    local job, priority
+                    -- get job
+                    local job
                     if job_pending then
                         job = job_pending
-                        priority = priority_prev
                     else
-                        job, priority = jobs:pop()
+                        job = jobs:pop()
                     end
                     if not job then
                         break
                     end
 
-                    -- priority changed? we need to wait all running jobs exited
-                    priority_curr = priority or priority_prev
-                    assert(priority_curr >= priority_prev, "runjobs: invalid priority(%d < %d)!", priority_curr, priority_prev)
-                    if priority_curr > priority_prev then
-                        job_pending = job
-                        break
-                    end
-
                     -- 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
@@ -254,6 +243,7 @@ function main(name, jobs, opt)
                                 end
                                 count = count + 1
                                 jobfunc(i, total, {progress = progress_wrapper})
+                                print("finished", jobname)
                             end
                             running_jobs_indices[i] = nil
                         end,
@@ -299,7 +289,6 @@ function main(name, jobs, opt)
         else
             -- need to wait all running jobs exited first if be different priority
             scheduler.co_group_wait(group_name)
-            priority_prev = priority_curr
         end
     end
 
diff --git a/xmake/modules/private/action/require/impl/package.lua b/xmake/modules/private/action/require/impl/package.lua
index 6a860d99a..d8a5af7be 100644
--- a/xmake/modules/private/action/require/impl/package.lua
+++ b/xmake/modules/private/action/require/impl/package.lua
@@ -942,6 +942,7 @@ function _load_package(packagename, requireinfo, opt)
 
     -- get package key
     local packagekey = _get_packagekey(packagename, requireinfo, version)
+    print("packagekey", packagekey)
 
     -- get package from cache first
     local package_cached = _memcache():get2("packages", packagekey)
diff --git a/xmake/modules/private/async/jobpool.lua b/xmake/modules/private/async/jobpool.lua
index 7f9067343..653be2328 100644
--- a/xmake/modules/private/async/jobpool.lua
+++ b/xmake/modules/private/async/jobpool.lua
@@ -20,6 +20,7 @@
 
 -- imports
 import("core.base.object")
+import("core.base.dlist")
 import("core.base.hashset")
 
 -- define module
@@ -111,14 +112,13 @@ function jobpool:pop()
     end
 
     -- pop a job from the leaf jobs
-    if #leafjobs > 0 then
+    if not leafjobs:empty() then
 
         -- get job
-        local job = leafjobs[#leafjobs]
-        table.remove(leafjobs, #leafjobs)
+        local job = leafjobs:last()
+        leafjobs:remove(job)
 
-        -- get priority and parents node
-        local priority = job._priority or 0
+        -- get parents node
         local parents = assert(job._parents, "invalid job without parents node!")
 
         -- update all parents nodes
@@ -126,7 +126,6 @@ function jobpool:pop()
             -- we need to avoid adding it to leafjobs repeatly, it will cause dead-loop when poping group job
             -- @see https://github.com/xmake-io/xmake/issues/2740
             if not p._leaf then
-                p._priority = math.max(p._priority or 0, priority + 1)
                 p._deps:remove(job)
                 if p._deps:empty() and self._size > 0 then
                     p._leaf = true
@@ -145,11 +144,15 @@ function jobpool:pop()
             -- pop this job
             self._size = self._size - 1
             poprefs[jobkey] = true
-            return job, priority
+            return job
         end
     end
 end
 
+-- get free jobs
+function jobpool:freejobs()
+end
+
 -- enter group
 --
 -- @param name      the group name
@@ -191,7 +194,7 @@ function jobpool:_genleafjobs(job, leafjobs, refs)
         end
     else
         job._leaf = true
-        table.insert(leafjobs, job)
+        leafjobs:push(job)
     end
 end
 
@@ -232,5 +235,5 @@ end
 
 -- new a jobpool
 function new()
-    return jobpool {0, {name = "root"}, {}, {}}
+    return jobpool {0, {name = "root"}, dlist.new(), {}}
 end