timers: optimize linkedlist

Now uses a new L.create() factory to create access-optimized linkedlist
objects.

PR-URL: https://github.com/nodejs/node/pull/6436
Reviewed-By: Benjamin Gruenbaum <benjamingr@gmail.com>
Reviewed-By: Jeremiah Senkpiel <fishrock123@rocketmail.com>

3 files changed, 23 insertions, 6 deletions

diff --git a/lib/internal/linkedlist.js b/lib/internal/linkedlist.js
index 02186cfedc..33ada550ef 100644
--- a/lib/internal/linkedlist.js
+++ b/lib/internal/linkedlist.js
@@ -6,6 +6,13 @@ function init(list) {
 }
 exports.init = init;
 
+// create a new linked list
+function create() {
+  var list = { _idleNext: null, _idlePrev: null };
+  init(list);
+  return list;
+}
+exports.create = create;
 
 // show the most idle item
 function peek(list) {
@@ -42,10 +49,17 @@ exports.remove = remove;
 
 // remove a item from its list and place at the end.
 function append(list, item) {
-  remove(item);
+  if (item._idleNext || item._idlePrev) {
+    remove(item);
+  }
+
+  // items are linked  with _idleNext -> (older) and _idlePrev -> (newer)
+  // TODO: swap the linkage to match the intuitive older items at "prev"
   item._idleNext = list._idleNext;
-  list._idleNext._idlePrev = item;
   item._idlePrev = list;
+
+  // the list _idleNext points to tail (newest) and _idlePrev to head (oldest)
+  list._idleNext._idlePrev = item;
   list._idleNext = item;
 }
 exports.append = append;
diff --git a/lib/timers.js b/lib/timers.js
index dc2506e01e..7ae25f6a32 100644
--- a/lib/timers.js
+++ b/lib/timers.js
@@ -502,16 +502,14 @@ Timeout.prototype.close = function() {
 };
 
 
-var immediateQueue = {};
-L.init(immediateQueue);
+var immediateQueue = L.create();
 
 
 function processImmediate() {
   var queue = immediateQueue;
   var domain, immediate;
 
-  immediateQueue = {};
-  L.init(immediateQueue);
+  immediateQueue = L.create();
 
   while (L.isEmpty(queue) === false) {
     immediate = L.shift(queue);
diff --git a/test/parallel/test-timers-linked-list.js b/test/parallel/test-timers-linked-list.js
index b5ff9f56bf..cdae64d344 100644
--- a/test/parallel/test-timers-linked-list.js
+++ b/test/parallel/test-timers-linked-list.js
@@ -103,3 +103,8 @@ assert.equal(C, L.shift(list));
 // list
 assert.ok(L.isEmpty(list));
 
+var list2 = L.create();
+var list3 = L.create();
+assert.ok(L.isEmpty(list2));
+assert.ok(L.isEmpty(list3));
+assert.ok(list2 != list3);