Optmize filter list in elemHide.js for memory usage

lib/elemHide.js

 /*
  * This file is part of Adblock Plus <http://adblockplus.org/>,
  * Copyright (C) 2006-2014 Eyeo GmbH
  *
  * Adblock Plus is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 3 as
  * published by the Free Software Foundation.
  *
  * Adblock Plus is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
@@ skipping 12 matching lines @@
 
 let {Utils} = require("utils");
 let {IO} = require("io");
 let {Prefs} = require("prefs");
 let {ElemHideException} = require("filterClasses");
 let {FilterNotifier} = require("filterNotifier");
 let {AboutHandler} = require("elemHideHitRegistration");
 let {TimeLine} = require("timeline");
 
 /**
- * Lookup table, filters by their associated key
+ * Array of filters, index as "key".
+ * @type Array
+ */
+let filters = [];
+/**
+ * Lookup table, keys of the filters by filter text.
+ * Can be null.
  * @type Object
  */
-let filterByKey = {__proto__: null};
-
-/**
- * Lookup table, keys of the filters by filter text
- * @type Object
- */
-let keyByFilter = {__proto__: null};
+let keyByFilter = new Map();
 
 /**
  * Lookup table, keys are known element hiding exceptions
  * @type Object
  */
 let knownExceptions = {__proto__: null};
 
 /**
  * Lookup table, lists of element hiding exceptions by selector
  * @type Object
  */
 let exceptions = {__proto__: null};
 
 /**
  * Currently applied stylesheet URL
  * @type nsIURI
  */
 let styleURL = null;
 
 /**
+ * Filters removed since last compact operation
+ * @type number
+ */
+let filtersRemoved = 0;
+
+/**
  * Element hiding component
  * @class
  */
 let ElemHide = exports.ElemHide =
 {
   /**
    * Indicates whether filters have been added or removed since the last apply() call.
    * @type Boolean
    */
   isDirty: false,
@@ skipping 28 matching lines @@
     TimeLine.log("done determining stylesheet URL");
 
     TimeLine.leave("ElemHide.init() done");
   },
 
   /**
    * Removes all known filters
    */
   clear: function()
   {
-    filterByKey = {__proto__: null};
-    keyByFilter = {__proto__: null};
+    dump("clear\n");
+    keyByFilter = null;
+    filters = [];
     knownExceptions = {__proto__: null};
     exceptions = {__proto__: null};
     ElemHide.isDirty = false;
     ElemHide.unapply();
   },
 
   /**
    * Add a new element hiding filter
    * @param {ElemHideFilter} filter
    */
   add: function(filter)
   {
     if (filter instanceof ElemHideException)
     {
       if (filter.text in knownExceptions)
         return;
 
       let selector = filter.selector;
       if (!(selector in exceptions))
         exceptions[selector] = [];
       exceptions[selector].push(filter);
       knownExceptions[filter.text] = true;
     }
     else
     {
-      if (filter.text in keyByFilter)
+      this._ensureFilterMap();
+
+      if (keyByFilter.has(filter.text))
         return;
 
-      let key;
-      do {
-        key = Math.random().toFixed(15).substr(5);
-      } while (key in filterByKey);
+      filters.push(filter);
+      keyByFilter.set(filter.text, filters.length - 1);
 
-      filterByKey[key] = filter;
-      keyByFilter[filter.text] = key;
       ElemHide.isDirty = true;
     }
   },
 
   /**
    * Removes an element hiding filter
    * @param {ElemHideFilter} filter
    */
   remove: function(filter)
   {
     if (filter instanceof ElemHideException)
     {
       if (!(filter.text in knownExceptions))
         return;
 
       let list = exceptions[filter.selector];
       let index = list.indexOf(filter);
       if (index >= 0)
         list.splice(index, 1);
       delete knownExceptions[filter.text];
     }
     else
     {
-      if (!(filter.text in keyByFilter))
+      this._ensureFilterMap();
+
+      let key = keyByFilter.get(filter.text);
+      if (key === undefined)
         return;
 
-      let key = keyByFilter[filter.text];
-      delete filterByKey[key];
-      delete keyByFilter[filter.text];
+      keyByFilter.delete(filter.text);
+      filters[key] = null;
       ElemHide.isDirty = true;
+      filtersRemoved += 1;
     }
   },
 
   /**
+   * Clean up and compact memory after filters
+   * are removed.
+   */
+  compact: function()
+  {
+    if (filtersRemoved == 0) {
+      return;
+    }
+
+    if (filtersRemoved == 1) {
+      for (let i = 0; i < filters; i++) {
+        if (filters[i] === null)
+          filters.splice(i, 1);
+      }
+    } else {
+      let newList = [];
+      for (let filter in filters) {
+        if (filter)
+          newList.push(filter);
+      }
+      filters = newList;
+    }
+
+    filtersRemoved = 0;
+  },
+
+  /**
+   * Ensure that we have a map of filter text to key.
+   * Might have to recreate it from the array of filters.
+   */
+  _ensureFilterMap: function()
+  {
+    if (keyByFilter)
+      return;
+
+    keyByFilter = new Map();
+    for (let i = 0; i < filters.length; i++)
+      keyByFilter.set(filters[i].text, i);
+  },
+
+  /**
    * Checks whether an exception rule is registered for a filter on a particular
    * domain.
    */
   getException: function(/**Filter*/ filter, /**String*/ docDomain) /**ElemHideException*/
   {
     let selector = filter.selector;
     if (!(filter.selector in exceptions))
       return null;
 
     let list = exceptions[filter.selector];
@@ skipping 104 matching lines @@
       TimeLine.leave("ElemHide.apply() write callback done");
     }.bind(this), "ElemHideWrite");
 
     this._applying = true;
 
     TimeLine.leave("ElemHide.apply() done", "ElemHideWrite");
   },
 
   _generateCSSContent: function()
   {
+    // We don't need keyByFilter anymore now, if we need it again,
+    // e.g. because of a subscription change, we will regenerate it.
+    keyByFilter = null;
+
     // Grouping selectors by domains
     TimeLine.log("start grouping selectors");
     let domains = {__proto__: null};
     let hasFilters = false;
-    for (let key in filterByKey)
+    for (let key = 0; key < filters.length; key++)
     {
-      let filter = filterByKey[key];
+      let filter = filters[key];
       let domain = filter.selectorDomain || "";
 
       let list;
       if (domain in domains)
         list = domains[domain];
       else
       {
         list = {__proto__: null};
         domains[domain] = list;
       }
@@ skipping 56 matching lines @@
    * Retrieves the currently applied stylesheet URL
    * @type String
    */
   get styleURL() ElemHide.applied ? styleURL.spec : null,
 
   /**
    * Retrieves an element hiding filter by the corresponding protocol key
    */
   getFilterByKey: function(/**String*/ key) /**Filter*/
   {
-    return (key in filterByKey ? filterByKey[key] : null);
+    return (key < filters.length ? filters[key] : null);
   },
 
   /**
    * Returns a list of all selectors active on a particular domain (currently
    * used only in Chrome).
    */
   getSelectorsForDomain: function(/**String*/ domain, /**Boolean*/ specificOnly)
   {
     let result = [];
-    for (let key in filterByKey)
+    for (let filter of filters)
     {
-      let filter = filterByKey[key];
+      if (!filter)
+        continue
+
       if (specificOnly && (!filter.domains || filter.domains[""]))
         continue;
 
       if (filter.isActiveOnDomain(domain) && !this.getException(filter, domain))
         result.push(filter.selector);
     }
     return result;
   }
 };