summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorFlorian Dold <florian.dold@gmail.com>2017-06-08 12:15:45 +0200
committerFlorian Dold <florian.dold@gmail.com>2017-06-08 12:15:45 +0200
commitf93839558d528f600b10fbe816914e7ff91fca64 (patch)
treec7ff2154abef357a532e6ffc90e299ea598db670
parent673ecb01efa32e4dcecc9f8595a8e13699b842f4 (diff)
downloadwallet-core-dold/dev/memidb.tar.gz
wallet-core-dold/dev/memidb.tar.bz2
wallet-core-dold/dev/memidb.zip
-rw-r--r--src/memidb/aatree-test.ts84
-rw-r--r--src/memidb/aatree.ts388
-rw-r--r--src/memidb/memidb-test.ts (renamed from src/memidb-test.ts)0
-rw-r--r--src/memidb/memidb.ts (renamed from src/memidb.ts)143
-rw-r--r--tsconfig.json6
m---------web-common0
6 files changed, 485 insertions, 136 deletions
diff --git a/src/memidb/aatree-test.ts b/src/memidb/aatree-test.ts
new file mode 100644
index 00000000..21ae2617
--- /dev/null
+++ b/src/memidb/aatree-test.ts
@@ -0,0 +1,84 @@
+/*
+ This file is part of TALER
+ (C) 2017 Inria and GNUnet e.V.
+
+ TALER is free software; you can redistribute it and/or modify it under the
+ terms of the GNU General Public License as published by the Free Software
+ Foundation; either version 3, or (at your option) any later version.
+
+ TALER 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
+ TALER; see the file COPYING. If not, see <http://www.gnu.org/licenses/>
+ */
+
+
+import {test} from "ava";
+
+import * as aat from "./aatree";
+
+
+function shuffleArray(array: any[]): any[] {
+ for (let i = array.length - 1; i > 0; i--) {
+ const j = Math.floor(Math.random() * (i + 1));
+ const temp = array[i];
+ array[i] = array[j];
+ array[j] = temp;
+ }
+ return array;
+}
+
+
+function myCmp(a: any, b: any): number {
+ if (a < b) {
+ return -1;
+ }
+ if (a > b) {
+ return 1;
+ }
+ return 0;
+}
+
+
+test("insertion", (t) => {
+ let vs = [];
+ for (let i = 0; i < 1000; i++) {
+ vs.push(Math.floor(Math.random() * 500));
+ }
+
+ let tree = undefined;
+ t.true(aat.checkInvariants(tree));
+
+ for (let i = 0; i < 1000; i++) {
+ tree = aat.treeInsert(tree, vs[i], myCmp);
+ t.true(aat.checkInvariants(tree));
+ t.true(aat.treeFind(tree, vs[i], myCmp));
+ }
+
+ vs = Array.from(new Set(vs));
+
+ vs.sort((a, b) => a - b);
+ t.deepEqual(aat.treeToArray(tree), vs);
+});
+
+
+test("deletion", (t) => {
+ let vs = [];
+ let tree = undefined;
+ for (let i = 0; i < 1000; i++) {
+ vs.push(Math.floor(Math.random() * 500));
+ tree = aat.treeInsert(tree, vs[i], myCmp);
+ t.true(aat.checkInvariants(tree));
+ t.true(aat.treeFind(tree, vs[i], myCmp));
+ }
+
+ shuffleArray(vs);
+
+ for (let i = 0; i < 1000; i++) {
+ tree = aat.treeDelete(tree, vs[i], myCmp);
+ t.true(aat.checkInvariants(tree));
+ t.false(aat.treeFind(tree, vs[i], myCmp));
+ }
+});
diff --git a/src/memidb/aatree.ts b/src/memidb/aatree.ts
new file mode 100644
index 00000000..50c4f0aa
--- /dev/null
+++ b/src/memidb/aatree.ts
@@ -0,0 +1,388 @@
+/*
+ This file is part of TALER
+ (C) 2017 Inria and GNUnet e.V.
+
+ TALER is free software; you can redistribute it and/or modify it under the
+ terms of the GNU General Public License as published by the Free Software
+ Foundation; either version 3, or (at your option) any later version.
+
+ TALER 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
+ TALER; see the file COPYING. If not, see <http://www.gnu.org/licenses/>
+ */
+
+
+/**
+ * Implementation of AA trees (Arne Andersson, 1993) as a persistent data
+ * structure (Prabhakar Ragde, 2014).
+ *
+ * AA trees were chosen since they balance efficiency and a simple
+ * implementation.
+ */
+
+
+/**
+ * An AA tree, either a node or 'undefined' as sentinel element.
+ */
+export type AATree = AATreeNode | undefined;
+
+
+interface AATreeNode {
+ left: AATree;
+ right: AATree;
+ level: number;
+ key: any;
+}
+
+
+/**
+ * Check AA tree invariants. Useful for testing.
+ */
+export function checkInvariants(t: AATree): boolean {
+ // No invariants for the sentinel.
+ if (!t) {
+ return true;
+ }
+
+ // AA1: The left child of a node x has level one less than x.
+ if (level(t.left) != level(t) - 1) {
+ console.log("violated AA1");
+
+ console.log(JSON.stringify(t, undefined, 2));
+ return false;
+ }
+
+ // AA2: The right child of x has the same level (x is a "double" node) or one less (x is a "single" node).
+ if (!(level(t.right) === level(t) || level(t.right) === level(t) - 1)) {
+ console.log("violated AA2");
+ console.log("level(t.right)", level(t.right));
+ console.log("level(t)", level(t));
+ return false;
+ }
+
+ // AA3: The right child of the right child of x has level less than x.
+ if (t.right && t.right.right) {
+ if (level(t.right.right) >= level(t)) {
+ console.log("violated AA3");
+ console.log(JSON.stringify(t, undefined, 2));
+ return false;
+ }
+ }
+
+ // AA4: All internal nodes have two children.
+ // This invariant follows from how we defined "level"
+ return true;
+}
+
+
+/**
+ * Fix a violation of invariant AA1 by reversing a link.
+ *
+ * ```
+ * y <--- t => y ---> t
+ * / \ \ => / / \
+ * a b c => a b c
+ * ```
+ */
+function skew(t: AATreeNode) {
+ if (t.left && t.left.level === t.level) {
+ return { ...t.left, right: { ...t, left: t.left.right } };
+ }
+ return t;
+}
+
+
+/**
+ * Fix a violation of invariant AA3 by pulling up the middle node.
+ *
+ * ```
+ * => y
+ * => / \
+ * t --> y --> z => t z
+ * / / => / \
+ * a b => a b
+ * ```
+ */
+function split(t: AATreeNode) {
+ if (t.right && t.right.right &&
+ t.level === t.right.level &&
+ t.right.level === t.right.right.level) {
+ return {
+ level: t.level + 1,
+ key: t.right.key,
+ left: { ...t, right: t.right.left },
+ right: t.right.right,
+ }
+ }
+ return t;
+}
+
+
+/**
+ * Non-destructively insert a new key into an AA tree.
+ */
+export function treeInsert(t: AATree, k: any, cmpFn: (k1: any, k2: any) => number): AATreeNode {
+ if (!t) {
+ return {
+ level: 1,
+ key: k,
+ left: undefined,
+ right: undefined,
+ }
+ }
+ const cmp = cmpFn(k, t.key);
+ if (cmp === 0) {
+ return t;
+ } else if (cmp < 0) {
+ return split(skew({ ...t, left: treeInsert(t.left, k, cmpFn)}));
+ } else {
+ return split(skew({ ...t, right: treeInsert(t.right, k, cmpFn)}));
+ }
+}
+
+
+/**
+ * Level of an AA tree node, or zero if it's a sentinel.
+ */
+function level(t: AATree) {
+ if (!t) {
+ return 0;
+ }
+ return t.level;
+}
+
+
+/**
+ * Check if a node is single, i.e. doens't have a right child
+ * on the same level.
+ */
+function isSingle(t: AATree) {
+ if (t && t.right && t.right.level === t.level) {
+ return false;
+ }
+ return true;
+}
+
+
+/**
+ * Restore invariants that were broken by deleting a node.
+ *
+ * Assumes that invariants for t.left and t.right are already adjusted.
+ */
+function adjust(t: AATreeNode): AATreeNode {
+ // First check if left or right subtree are at the right level. Note that
+ // they can't be both at the wrong level, since only one node is deleted
+ // before calling adjust.
+ const leftOkay = level(t.left) === level(t) - 1;
+ const rightOkay = (level(t.right) === level(t) || level(t.right) === level(t) - 1);
+ if (leftOkay && rightOkay) {
+ return t;
+ }
+ if (!rightOkay) {
+ if (isSingle(t.left)) {
+ return skew({ ...t, level: t.level - 1 });
+ }
+ /*
+ * ( t ) => ( b )
+ * / \ => / \
+ * x -> b \ => x t
+ * / / \ \ => / \ / \
+ * a d e c => a d e c
+ */
+ const b = t.left!.right!;
+ return {
+ level: b.level + 1,
+ key: b.key,
+ left: { ...t.left, right: b.left },
+ right: { ...t, level: t.level - 1, left: b.right },
+ };
+ }
+ if (!leftOkay) {
+ if (isSingle(t)) {
+ return split({ ...t, level: t.level - 1 });
+ }
+ /*
+ * t -> ( r ) => ( a ) -> r
+ * / / \ => / / \
+ * / a -> d b => t d b
+ * / / => / \
+ * x c => l c
+ *
+ * t -> r => ( a )
+ * / / \ => / \
+ * / a b => t r -> b
+ * / / \ => / \ /
+ * x c d => l c d
+ *
+ * Only Level of r differs, depending on whether a is single or double.
+ * Node 'r' must be split, as node 'b' might be double.
+ */
+ const a = t.right!.left!;
+ const n = isSingle(a) ? a.level : a.level + 1;
+ return {
+ key: a.key,
+ left: { ...t, level: a.level, right: a.left },
+ level: a.level + 1,
+ right: split({
+ level: n,
+ left: a.right,
+ right: t.right!.right,
+ key: t.right!.key,
+ }),
+ };
+ }
+ throw Error("not reached");
+}
+
+
+function treeDeleteLargest(t: AATreeNode): { key: any, tree: AATree } {
+ if (!t.right) {
+ return { key: t.key, tree: t.left };
+ }
+ const d = treeDeleteLargest(t.right);
+ return {
+ key: d.key,
+ tree: adjust({ ...t, right: d.tree}),
+ };
+}
+
+
+/**
+ * Count the number of elements stored in the tree.
+ */
+export function treeSize(t: AATree): number {
+ if (!t) {
+ return 0;
+ }
+ return treeSize(t.left) + treeSize(t.right) + 1;
+}
+
+
+/**
+ * Get an array of (sorted) keys from an AA tree.
+ */
+export function treeToArray(t: AATree, accum: any[] = []) {
+ if (!t) {
+ return accum;
+ }
+ treeToArray(t.left, accum);
+ accum.push(t.key);
+ treeToArray(t.right, accum);
+ return accum;
+}
+
+
+/**
+ * Check if a key can be found in a tree.
+ */
+export function treeFind(t: AATree, k: any, cmpFn: (k1: any, k2: any) => number): boolean {
+ if (!t) {
+ return false;
+ }
+ const cmp = cmpFn(k, t.key);
+ if (cmp < 0) {
+ return treeFind(t.left, k, cmpFn);
+ }
+ if (cmp > 0) {
+ return treeFind(t.right, k, cmpFn);
+ }
+ return true;
+}
+
+
+/**
+ * Get the largest key in the tree.
+ */
+export function treeBiggest(t: AATree): any {
+ if (!t) {
+ return undefined;
+ }
+ if (!t.right) {
+ return t.key;
+ }
+ return treeBiggest(t);
+}
+
+
+/**
+ * Get the smallest key in the tree.
+ */
+export function treeSmallest(t: AATree): any {
+ if (!t) {
+ return undefined;
+ }
+ if (!t.left) {
+ return t.key;
+ }
+ return treeSmallest(t);
+}
+
+
+/**
+ * Get the smallest key from the tree that is larger than the given key.
+ * Returns 'undefined' if the given key is the largest key.
+ */
+export function treeNextKey(t: AATree, k: any, cmpFn: (k1: any, k2: any) => number): any {
+ if (!t) {
+ return undefined;
+ }
+ const cmp = cmpFn(k, t.key);
+ if (cmp === 0) {
+ return treeSmallest(t.right);
+ }
+ if (cmp < 0) {
+ const r = treeNextKey(t.left, k, cmpFn);
+ if (r) {
+ return r;
+ }
+ return t.key;
+ }
+ if (cmp < 0) {
+ return treeNextKey(t.right, k, cmpFn);
+ }
+}
+
+
+/**
+ * Get the largest tree from the tree that is smaller than the given key.
+ * Returns 'undefined' if the given key is the smallest key.
+ */
+export function treePreviousKey(t: AATree, k: any, cmpFn: (k1: any, k2: any) => number): any {
+ return treeNextKey(t, k, (k1, k2) => -cmpFn(k1, k2));
+}
+
+
+/**
+ * Returns a new tree without the given key.
+ */
+export function treeDelete(t: AATree, k: any, cmpFn: (k1: any, k2: any) => number): AATree {
+ if (!t) {
+ return t;
+ }
+ const cmp = cmpFn(k, t.key);
+ if (cmp === 0) {
+ if (!t.left) {
+ return t.right;
+ }
+ if (!t.right) {
+ return t.left;
+ }
+ const d = treeDeleteLargest(t.left);
+ return adjust({
+ key: d.key,
+ left: d.tree,
+ right: t.right,
+ level: t.level,
+ });
+ }
+ if (cmp < 0) {
+ return adjust({ ...t, left: treeDelete(t.left, k, cmpFn) });
+ }
+ if (cmp > 0) {
+ return adjust({ ...t, right: treeDelete(t.right, k, cmpFn) });
+ }
+ throw Error("not reached");
+}
diff --git a/src/memidb-test.ts b/src/memidb/memidb-test.ts
index 8f8498a6..8f8498a6 100644
--- a/src/memidb-test.ts
+++ b/src/memidb/memidb-test.ts
diff --git a/src/memidb.ts b/src/memidb/memidb.ts
index 3348d97a..4ad3a01b 100644
--- a/src/memidb.ts
+++ b/src/memidb/memidb.ts
@@ -86,133 +86,6 @@ class MyDomStringList extends Array<string> implements DOMStringList {
-interface AATreeNode {
- left?: AATreeNode;
- right?: AATreeNode;
- level: number;
- key: any;
-}
-
-export type AATree = AATreeNode | undefined;
-
-
-function skew(t: AATreeNode) {
- if (t.left && t.left.level == t.level) {
- return {
- left: t.left.left,
- right: t,
- key: t.left.key,
- level: t.level,
- };
- }
- return t;
-}
-
-
-function split(t: AATreeNode) {
- if (t.right && t.right.right &&
- t.level == t.right.level &&
- t.right.level == t.right.right.level) {
- return {
- level: t.level + 1,
- key: t.right.key,
- left: {
- level: t.level,
- key: t.key,
- left: t.left,
- right: t.right.left,
- },
- right: {
- key: t.right.right.key,
- left: t.right.right.left,
- level: t.level,
- right: t.right.right.right,
- },
- }
- }
- return t;
-}
-
-/**
- * Non-destructively insert a new key into an AA tree.
- */
-export function treeInsert(t: AATree, k: any): AATreeNode {
- if (!t) {
- return {
- level: 0,
- key: k,
- }
- }
- const cmp = compareKeys(k, t.key);
- if (cmp == 0) {
- return t;
- }
- let r = Object.assign({}, t);
- if (cmp == -1) {
- r.left = treeInsert(t.left, k);
- } else {
- r.right = treeInsert(t.right, k);
- }
- return split(skew(r));
-}
-
-
-/**
- * Check AA tree invariants. Useful for testing.
- */
-export function checkInvariants(t: AATree): boolean {
- if (!t) {
- return true;
- }
- throw Error("not implemented");
-}
-
-
-function adjust(t: AATreeNode): AATreeNode {
- throw Error("not implemented");
-}
-
-function treeDeleteLargest(t: AATreeNode): { key: any, tree: AATree } {
- if (!t.right) {
- return { key: t.key, tree: t.left };
- }
- const d = treeDeleteLargest(t.right);
- return {
- key: d.key,
- tree: adjust({
- level: t.level,
- key: t.key,
- left: t.left,
- right: d.tree,
- }),
- };
-}
-
-
-//function treeDelete(t: AATree, k: any): AATreeNode {
-// if (!t) {
-// return t;
-// }
-// const cmp = compareKeys(k, t.key);
-// if (cmp == 0) {
-// if (!t.left) {
-// return t.right;
-// }
-// if (!t.right) {
-// return t.left;
-// }
-// const d = treeDeleteLargest(t.left);
-// return adjust({
-// key: d.key,
-// left: d.tree,
-// right: t.right,
-// level: t.level,
-// });
-// } else {
-// }
-//}
-
-
class MyKeyRange implements IDBKeyRange {
static only(value: any): IDBKeyRange {
@@ -246,7 +119,7 @@ export function isKeyRange(obj: any): obj is IDBKeyRange {
}
-function compareKeys(a: any, b: any): -1|0|1 {
+export function compareKeys(a: any, b: any): -1|0|1 {
throw Error("not implemented")
}
@@ -305,6 +178,8 @@ class MyRequest implements IDBRequest {
done: boolean = false;
_result: any;
+ _source: (IDBObjectStore | IDBIndex | IDBCursor | null) = null;
+
constructor(public _transaction: Transaction, public runner: () => void) {
}
@@ -329,7 +204,7 @@ class MyRequest implements IDBRequest {
get source() {
// buggy type definitions don't allow null even though it's in
// the spec.
- return (null as any) as (IDBObjectStore | IDBIndex | IDBCursor);
+ return this._source as (IDBObjectStore | IDBIndex | IDBCursor);
}
get transaction() {
@@ -536,7 +411,7 @@ class MyObjectStore implements IDBObjectStore {
}
const req = new MyRequest(this.transaction, () => {
- req.source = this;
+ req._source = this;
store.objects[stringKey] = value;
});
return req;
@@ -563,8 +438,8 @@ class MyObjectStore implements IDBObjectStore {
const store = this.transaction.transactionDbData.stores[this.storeName];
const stringKey = stringifyKey(key);
const req = new MyRequest(this.transaction, () => {
- req.source = this;
- delete store.objects[stringifyKey];
+ req._source = this;
+ delete store.objects[stringKey];
});
return req;
}
@@ -582,8 +457,8 @@ class MyObjectStore implements IDBObjectStore {
const store = this.transaction.transactionDbData.stores[this.storeName];
const stringKey = stringifyKey(key);
const req = new MyRequest(this.transaction, () => {
- req.source = this;
- req.result = store.objects[stringKey];
+ req._source = this;
+ req._result = store.objects[stringKey];
});
return req;
}
diff --git a/tsconfig.json b/tsconfig.json
index 349b5969..876cd1cf 100644
--- a/tsconfig.json
+++ b/tsconfig.json
@@ -42,8 +42,10 @@
"src/libtoolVersion-test.ts",
"src/libtoolVersion.ts",
"src/logging.ts",
- "src/memidb-test.ts",
- "src/memidb.ts",
+ "src/memidb/aatree-test.ts",
+ "src/memidb/aatree.ts",
+ "src/memidb/memidb-test.ts",
+ "src/memidb/memidb.ts",
"src/query.ts",
"src/timer.ts",
"src/types-test.ts",
diff --git a/web-common b/web-common
-Subproject a8bff2e27b89feb3696cf0e3a49fc00155d92de
+Subproject ebf2b43fb00f057643d69abf34b54a1b6087dfc