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>

1 files changed, 16 insertions, 2 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;