WIP - Dictionary types implementation

lib/typedObjects/dictionaryTypes.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
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+"use strict";
+
+const LOAD_FACTOR = 0.75;
+
+let {calculateHash} = require("typedObjects/hash");
+let {ilog2, nextPow2, alloc, dealloc, addBuffer, removeBuffer} = require("typedObjects/utils");
+
+function defaultDictionaryConstructor()
+{
+  this.dictionaryBufferIndex = -1;
+};
+
+function defaultDictionaryDestructor()
+{
+  this.buckets = 0;
+};
+
+function lookup(key, groups, view, offset)
+{
+  let bucketCount = groups << 5;
+  let bucket = calculateHash(key) & (bucketCount - 1);
+  let group = bucket >>> 5;
+  let bit = 1 << (bucket & 0x1F);
+
+}
+
+function createCombinedConstructor(customConstructor)
+{
+  return function()
+  {
+    defaultDictionaryConstructor.apply(this);
+    customConstructor.apply(this, arguments);
+  }
+}
+
+function createCombinedDestructor(customDestructor)
+{
+  return function()
+  {
+    try
+    {
+      customDestructor.apply(this);
+    }
+    finally
+    {
+      defaultDictionaryDestructor.apply(this);
+    }
+  }
+}
+
+function capacityWatcher(newCapacity)
+{
+  newCapacity = newCapacity | 0;
+  let newBuckets = Math.ceil(newCapacity / LOAD_FACTOR) | 0;
+  if (newBuckets > this.buckets)
+    this.buckets = newBuckets;
+
+  return (this.buckets * LOAD_FACTOR) | 0;
+}
+
+function createBucketsWatcher(bucketSize, bufferSize, buffers, viewTypes, views, firstFree)
+{
+  bufferSize = bufferSize | 0;
+  return function bucketsWatcher(newBuckets)
+  {
+    newBuckets = newBuckets | 0;
+    if (newBuckets < 0)
+      newBuckets = 0;
+    newBuckets = nextPow2(newBuckets);
+
+    let buckets = this.buckets;
+    if (buckets != newBuckets)
+    {
+      let origBufferIndex = this.dictionaryBufferIndex;
+      let origByteOffset = this.dictionaryByteOffset;
+      if (newBuckets > 0)
+      {
+        // Allocate new buffer
+        let bufferIndex, byteOffset;
+        let reference = firstFree[newGroups];
+        if (typeof reference != "undefined")
+        {
+          [bufferIndex, byteOffset] = alloc(reference,
+              bucketSize * newBuckets, (bufferSize / newBuckets) | 0,
+              buffers, viewTypes, views);
+        }
+        else
+        {
+          // This dictionary is too large, it needs an individual buffer
+          bufferIndex = addBuffer(bucketSize * newBuckets, buffers, viewTypes, views);
+          byteOffset = 0;
+        }
+
+        if (buckets > 0)
+        {
+          // TODO: Copy data
+        }
+
+        this.dictionaryBufferIndex = bufferIndex;
+        this.dictionaryByteOffset = byteOffset;
+      }
+      else
+        this.dictionaryBufferIndex = -1;
+
+      if (buckets > 0)
+      {
+        // TODO: Release values
+
+        // Release old buffer
+        let reference = firstFree[buckets];
+        if (typeof reference != "undefined")
+          dealloc(reference, origBufferIndex, origByteOffset);
+        else
+          removeBuffer(origBufferIndex, buffers, views);
+      }
+    }
+
+    return newBuckets;
+  }
+}
+
+function createDictionaryType(elementType, typeDescriptor, meta)
+{
+  if (typeof meta != "object" || meta == null)
+    meta = {};
+
+  let {int16, uint32} = require("typedObjects/primitiveTypes");
+  let {string} = require("typedObjects/stringType");
+  let {Reference, TypedReference} = require("typedObjects/references");
+
+  let groupSize = (elementType.referenceLength + string.referenceLength) * SLOTS_PER_GROUP + uint32.byteLength * 2;
+  groupSize = Math.max(groupSize, TypedReference.byteLength);
+  let bufferSize = ("dictionaryBufferSize" in meta ? meta.dictionaryBufferSize | 0 : 128);
+  bufferSize = nextPow2(Math.max(bufferSize, 2)) | 0;
+
+  let buffers = [];
+  let viewTypes = elementType.viewTypes.slice();
+  let views = [];
+  for (let i = 0, l = viewTypes.length | 0; i < l; i++)
+    views.push([]);
+
+  let elementGetter = elementType.createGetter.apply(elementType, [0].concat(views));
+  let elementSetter = elementType.createSetter.apply(elementType, [0].concat(views));
+
+  let typedReferenceTypes = TypedReference.viewTypes;
+  let typedReferenceViews = [];
+  for (let i = 0, l = typedReferenceTypes.length | 0; i < l; i++)
+  {
+    let type = typedReferenceTypes[i];
+    let index = viewTypes.indexOf(type);
+    if (index < 0)
+    {
+      viewTypes.push(type);
+      views.push([]);
+      index = viewTypes.length - 1;
+    }
+    typedReferenceViews.push(views[index]);
+  }
+
+  let firstFree = [];
+  for (let i = 2; i < bufferSize; i <<= 1)
+    firstFree[i] = new TypedReference(-1, typedReferenceViews);
+
+  // Ensure there is a view for uint32
+  let uint32Index = viewTypes.indexOf(uint32.viewTypes[0]);
+  if (uint32Index < 0)
+  {
+    viewTypes.push(uint32.viewTypes[0]);
+    views.push([]);
+    uint32Index = viewTypes.length - 1;
+  }
+
+  let keyGetter = string.createSetter(0)
+  let occupancyGetter = uint32.createGetter(
+    (elementType.referenceLength + string.referenceLength) * SLOTS_PER_GROUP,
+    views[uint32Index]
+  );
+  let deletedGetter = uint32.createGetter(
+    (elementType.referenceLength + string.referenceLength) * SLOTS_PER_GROUP + uint32.byteLength,
+    views[uint32Index]
+  );
+
+  typeDescriptor = Object.create(typeDescriptor || {});
+  typeDescriptor.dictionaryBufferIndex = int16;
+  typeDescriptor.dictionaryByteOffset = uint32;
+  typeDescriptor.getDictionaryBuffer = function()
+  {
+    return this.dictionaryBufferIndex >= 0 ? buffers[this.dictionaryBufferIndex] : null;
+  };
+  typeDescriptor.groups = uint32;
+  typeDescriptor.capacity = uint32;
+
+//  typeDescriptor.get = createGetter(elementGetter);
+//  typeDescriptor.set = createSetter(elementSetter);
+
+  if (meta.hasOwnProperty("constructor") && typeof meta.constructor == "function")
+    meta.constructor = createCombinedConstructor(meta.constructor);
+  else
+    meta.constructor = defaultDictionaryConstructor;
+
+  if (meta.hasOwnProperty("destructor") && typeof meta.destructor == "function")
+    meta.destructor = createCombinedDestructor(meta.destructor);
+  else
+    meta.destructor = defaultDictionaryDestructor;
+
+  if (!meta.watch || typeof meta.watch != "object")
+    meta.watch = {};
+
+  meta.watch.groups = createGroupsWatcher(groupSize, bufferSize, buffers, viewTypes, views, firstFree);
+  meta.watch.capacity = capacityWatcher;
+
+  let {ObjectBase} = require("typedObjects/objectTypes");
+  return ObjectBase.extend(typeDescriptor, meta);
+}
+
+exports.createDictionaryType = createDictionaryType;