Here is a sort of B+tree data structure:
class KeyValue {
constructor(key, value) {
this.key = key;
this.value = value;
}
}
class Node {
constructor(capacity) {
// Mimic fixed-size array (avoid accidentally growing it)
this.children = Object.seal(Array(capacity).fill(null));
this.childCount = 0; // Number of used slots in children array
this.treeSize = 0
// The algorithm relies on that fact that both KeyValue & Node have a key property:
this.key = null; // Here it is a property for supporting a search
// Maintain back-link to parent.
this.parent = null;
// Per level in the tree, maintain a doubly linked list
this.prev = this.next = null;
}
updateTreeSize(start, end, sign=1) {
let sum = 0;
if (this.isLeaf()) {
sum = end - start;
} else {
for (let i = start; i < end; i++) sum += this.children(i).treeSize;
}
if (!sum) return;
sum *= sign;
// Apply the sum change to this node and all its ancestors
for (let node = this; node; node = node.parent) {
node.treeSize += sum;
}
}
setCapacity(capacity) {
if (capacity < 1) return;
// Here we make a new array, and copy the data into it
let children = Object.seal(Array(capacity).fill(null));
for (let i = 0; i < this.childCount; i++) children(i) = this.children(i);
this.children = children;
}
isLeaf() {
return !(this.children(0) instanceof Node);
}
index() {
return this.parent.children.indexOf(this);
}
updateKey() {
for (let node = this; node; node = node.parent) {
node.key = node.children(0).key;
}
}
wipe(start, end) {
this.updateTreeSize(start, end, -1);
this.children.copyWithin(start, end, this.childCount);
for (let i = this.childCount - end + start; i < this.childCount; i++) {
this.children(i) = null;
}
this.childCount -= end - start;
// Reduce allocated size if possible
if (this.childCount * 2 <= this.children.length) this.setCapacity(this.children.length / 2);
// Update key if first item changed
if (start === 0 && this.childCount > 0) this.updateKey();
}
moveFrom(neighbor, target, start, count = 1) {
// Note: `start` can have two meanings:
// if neighbor is null, it is the value/Node to move to the target
// if neighbor is a Node, it is the index from where value(s) have to be moved to the target
// Make room in target node
if (this.childCount + count > this.children.length) this.setCapacity(this.children.length * 2);
this.children.copyWithin(target + count, target, Math.max(target + count, this.childCount));
this.childCount += count;
if (neighbor !== null) {
// Copy the children
for (let i = 0; i < count; i++) {
this.children(target + i) = neighbor.children(start + i);
}
// Remove the original references
neighbor.wipe(start, start + count);
} else {
this.children(target) = start; // start is value to insert
}
this.updateTreeSize(target, target + count, 1);
// Set parent link(s)
if (!this.isLeaf()) {
for (let i = 0; i < count; i++) {
this.children(target + i).parent = this;
}
}
// Update key if first item changed
if (target === 0) this.updateKey();
}
moveToNext(count) {
this.next.moveFrom(this, 0, this.childCount - count, count);
}
moveFromNext(count) {
this.moveFrom(this.next, this.childCount, 0, count);
}
basicRemove(index) {
if (!this.isLeaf()) {
// Take node out of the level's linked list
let prev = this.children(index).prev;
let next = this.children(index).next;
if (prev) prev.next = next;
if (next) next.prev = prev;
}
this.wipe(index, index + 1);
}
basicInsert(index, value) {
this.moveFrom(null, index, value);
if (value instanceof Node) {
// Insert node in the level's linked list
if (index > 0) {
value.prev = this.children(index - 1);
value.next = value.prev.next;
} else if (this.childCount > 1) {
value.next = this.children(1);
value.prev = value.next.prev;
}
if (value.prev) value.prev.next = value;
if (value.next) value.next.prev = value;
}
}
pairWithSmallest() {
return this.prev && (!this.next || this.next.childCount > this.prev.childCount) ?
(this.prev, this) : (this, this.next);
}
toString() {
return "(" + this.children.map(v => v ?? "-").join() + ")";
}
}
class Tree {
constructor(nodeCapacity = 32) {
this.nodeCapacity = nodeCapacity;
this.base = new Node(1);
this.first = this.base; // Head of doubly linked list at bottom level
}
locate(key) {
let node = this.base;
let low;
while (true) {
// Binary search among keys
low = 1;
let high = node.childCount;
while (low < high) {
let index = (low + high) >> 1;
if (key >= node.children(index).key) {
low = index + 1;
} else {
high = index;
}
}
low--;
if (node.isLeaf()) break;
node = node.children(low);
}
if (low < node.childCount && key > node.children(low).key) return (node, low + 1);
return (node, low);
}
get(key) {
let (node, index) = this.locate(key);
if (index < node.childCount) {
let keyValue = node.children(index);
if (keyValue.key === key) return keyValue.value;
}
}
set(key, value) {
let (node, index) = this.locate(key);
if (index < node.childCount && node.children(index).key === key) {
// already present: update the value
node.children(index).value = value;
return;
}
let item = new KeyValue(key, value); // item can be a KeyValue or a Node
while (node.childCount === this.nodeCapacity) { // No room here
if (index === 0 && node.prev && node.prev.childCount < this.nodeCapacity) {
return node.prev.basicInsert(node.prev.childCount, item);
}
// Check whether we can redistribute (to avoid a split)
if (node !== this.base) {
let (left, right) = node.pairWithSmallest();
let joinedIndex = left === node ? index : left.childCount + index;
let sumCount = left.childCount + right.childCount + 1;
if (sumCount <= 2 * this.nodeCapacity) { // redistribute
let childCount = sumCount >> 1;
if (node === right) { // redistribute to the left
let insertInLeft = joinedIndex < childCount;
left.moveFromNext(childCount - left.childCount - +insertInLeft);
} else { // redistribute to the right
let insertInRight = index >= sumCount - childCount;
left.moveToNext(childCount - right.childCount - +insertInRight);
}
if (joinedIndex > left.childCount ||
joinedIndex === left.childCount && left.childCount > right.childCount) {
right.basicInsert(joinedIndex - left.childCount, item);
} else {
left.basicInsert(joinedIndex, item);
}
return;
}
}
// Cannot redistribute: split node
let childCount = node.childCount >> 1;
// Create a new node that will later become the right sibling of this node
let sibling = new Node(childCount);
// Move half of node node's data to it
sibling.moveFrom(node, 0, childCount, childCount);
// Insert the item in either the current node or the new one
if (index > node.childCount) {
sibling.basicInsert(index - node.childCount, item);
} else {
node.basicInsert(index, item);
}
// Is this the base?
if (!node.parent) {
// ...then first create a parent, which is the new base
this.base = new Node(2);
this.base.basicInsert(0, node);
}
// Prepare for inserting the sibling node into the tree
index = node.index() + 1;
node = node.parent;
item = sibling; // item is now a Node
}
node.basicInsert(index, item);
}
remove(key) {
let (node, index) = this.locate(key);
if (index >= node.childCount || node.children(index).key !== key) return; // not found
while (true) {
node.basicRemove(index);
// Exit when node's fill ratio is fine
if (!node.parent || node.childCount * 2 > this.nodeCapacity) return;
// Node has potentially too few children, we should either merge or redistribute
let (left, right) = node.pairWithSmallest();
if (!left || !right) { // A node with no siblings? Must become the base!
this.base = node;
node.parent = null;
return;
}
let sumCount = left.childCount + right.childCount;
let childCount = sumCount >> 1;
// Check whether to merge or to redistribute
if (sumCount > this.nodeCapacity) { // redistribute
// Move some data from the bigger to the smaller node
let shift = childCount - node.childCount;
if (!shift) { // Boundary case: when a redistribution would bring no improvement
console.assert(node.childCount * 2 === this.nodeCapacity && sumCount === this.nodeCapacity + 1);
return;
}
if (node === left) { // move some children from right to left
left.moveFromNext(shift);
} else { // move some children from left to right
left.moveToNext(shift);
}
return;
}
// Merge:
// Move all data from the right to the left
left.moveFromNext(right.childCount);
// Prepare to delete right node
node = right.parent;
index = right.index();
}
}
}
module.exports = Tree
Tree.Node = Node
Tree.KeyValue = KeyValue
It has some initial tests like this:
const Tree = require('./keyValueTree')
const { Node, KeyValue } = Tree
/* Below this point: these methods are optional */
Tree.prototype(Symbol.iterator) = function*() { // Make tree iterable, yielding key/value pairs
for (let node = this.first; node; node = node.next) {
for (let i = 0; i < node.childCount; i++) yield (node.children(i).key, node.children(i).value);
}
}
Tree.prototype.verify = function() {
// Raise an error when the tree violates one of the required properties
if (!this.base || !this.base.childCount) return; // An empty tree is fine.
if (this.base.parent) throw "base should not have a parent";
// Perform a breadth first traversal
let q = (this.base);
while (q.length) {
if (q(0).isLeaf() && this.first !== q(0)) throw "this.first is not pointing to first leaf";
let level = ();
let last = null;
for (let parent of q) {
if (!(parent instanceof Node)) throw "parent is not instance of Node";
if (parent.children.length > this.nodeCapacity) throw "node's children array is too large";
if (parent.childCount > 0 && parent.childCount * 2 <= parent.children.length) throw "node's fill ratio is too low";
for (let i = parent.childCount; i < parent.children.length; i++) {
if (parent.children(i) !== null) throw "child beyond childCount should be null but is not";
}
if (parent.isLeaf()) {
if (parent.children(0).key !== parent.key) throw "key does not match with first child value";
for (let value of parent.children.slice(0, parent.childCount)) {
if (value === null) throw "leaf has a null as value";
if (!(value instanceof KeyValue)) throw "leaf has a non-KeyValue item";
}
} else {
if (parent.children(0).key !== parent.key) throw "key does not match with first child's key";
for (let node of parent.children.slice(0, parent.childCount)) {
if (node === null) throw "internal node has a null as value";
if (!(node instanceof Node)) throw "internal node has a non-Node as value";
if (node.parent !== parent) throw "wrong parent";
if (node.prev !== last) throw "prev link incorrect";
if (last && last.next !== node) throw "next link incorrect";
if (last && last.children.length + node.children.length <= this.nodeCapacity) {
throw "two consecutive siblings have a total number of children that is too small";
}
if (node.childCount * 2 < this.nodeCapacity) {
throw "internal node is too small: " + node;
}
level.push(node);
last = node;
}
}
}
if (last && last.next) throw "last node in level has a next reference";
q = level;
}
}
Tree.prototype.test = function(count=100) {
const isEqual = () =>
JSON.stringify((...map).sort((a,b) => a(0)-b(0))) === JSON.stringify((...this));
// Create Map to perform the same operations on it as on the tree
let map = new Map;
let max = count*2;
// Perform a series of insertions
for (let i = 0; i < count; i++) {
// Choose random key
let key = Math.floor(Math.random() * max);
let value = key*2;
// Perform same insertion in array and tree
map.set(key, value);
this.set(key, value);
// Verify tree consistency and properties
this.verify();
// Verify the order of key/values in the array is the same as in the tree
console.assert(isEqual(), "tree not same as array");
}
// Perform a series of retrievals and updates
for (let i = 0; i < count; i++) {
// Choose random key
let key = Math.floor(Math.random() * max);
// Perform same retrieval in array and tree
let value = map.get(key);
if (value !== this.get(key)) throw "get() returns inconsistent result";
if (value === undefined) { // value is not in tree
this.remove(key); // should not alter the tree
} else { // value is in tree: update it
map.set(key, value+10);
this.set(key, value+10);
}
// Verify tree consistency and properties
this.verify();
// Verify the order of key/values in the array is the same as in the tree
console.assert(isEqual(), "tree not same as array");
}
// Perform a series of deletions
for (let i = map.size; i > 0; i--) {
// Choose random deletion value
let j = Math.floor(Math.random() * i)
let key = (...map.keys())(j);
// Perform same deletion in array and tree
map.delete(key);
this.remove(key);
// Verify tree consistency and properties
this.verify();
// Verify the order of key/values in the array is the same as in the tree
console.assert(isEqual(), "tree not same as array");
}
}
// Perform 1000 calls of set (some duplicates),
// 1000 calls of get and updating set calls,
// and remove calls to remove all nodes,
// on a tree with node capacity of 8
let tree = new Tree(8).test(1000);
console.log("all tests completed");
However, I don’t feel very comfortable with having Math.random used in the tests and not being able to really see the expected output clearly, which is more of what I’m used to.
So I am starting to put together some new tests, which happen to use this allocate function:
const Tree = require('./keyValueTree')
module.exports = allocate
function allocate(bins, bits) {
if ((bits & (bits - 1)) != 0) {
throw "Parameter is not a power of 2";
}
if (bits < 32 || bits > 4194304) {
throw "Bits required out of range";
}
var startBinIndex = Math.log2(bits >> 5);
var lastBin = bins.length - 1;
for (var binIndex = startBinIndex; binIndex <= lastBin; binIndex++) {
var bin = bins(binIndex);
//
// We have found a bin that is not empty...
//
if (bin.base.treeSize != 0) {
//
// Calculate amount of memory this bin takes up
//
var thisBinMemorySize = (32 << binIndex);
var binBlock = bin.first.children(0);
var memoryAddress = binBlock.key;
//
// We are going to return this block
//
var allocatedMemoryBlock = memoryAddress
//
// Before we return the above block, we need to remove the block if count is 1 otherwise decrease count and adjust memory start pointer by bin size
//
if (binBlock.value == 1) {
bin.remove(binBlock.key)
} else {
binBlock.value--;
binBlock.key += thisBinMemorySize;
bin.first.updateKey()
}
//
// if we want 1024 bits and it takes it from bin 15, we simply subtract 1024 from 4194304 which gives us 4193280
// if we then populate bin 3 (1024 bits) onward, until bin 14, the exact number we end up populating those bins with is 4183280
//
var remainingUnsedMemory = thisBinMemorySize - bits;
var adjustmentSize = bits;
while (remainingUnsedMemory != 0) {
memoryAddress += adjustmentSize;
bins(startBinIndex).set(memoryAddress, 1)
startBinIndex++;
remainingUnsedMemory -= bits;
adjustmentSize = bits;
bits <<= 1;
}
return allocatedMemoryBlock;
}
}
return null; // out of memory...
}
Here are the tests for that:
const Tree = require('./keyValueTree')
const allocate = require('./allocate')
const assert = require('assert')
test('allocate blocks', () => {
const bins = createBaseBins()
var address = allocate(bins, 128)
assert.strictEqual(address, 0)
var address = allocate(bins, 256)
assert.strictEqual(address, 256)
var address = allocate(bins, 128)
assert.strictEqual(address, 128)
var address = allocate(bins, 256)
assert.strictEqual(address, 512)
var address = allocate(bins, 128)
assert.strictEqual(address, 768)
var address = allocate(bins, 4096)
assert.strictEqual(address, 4096)
// console.log(bins(15).first)
// assert.deepStrictEqual(bins, (
// (),
// (),
// ( { start: 896, count: 1 } ),
// (),
// (),
// ( { start: 1024, count: 1 } ),
// ( { start: 2048, count: 1 } ),
// (),
// ( { start: 8192, count: 1 } ),
// ( { start: 16384, count: 1 } ),
// ( { start: 32768, count: 1 } ),
// ( { start: 65536, count: 1 } ),
// ( { start: 131072, count: 1 } ),
// ( { start: 262144, count: 1 } ),
// ( { start: 524288, count: 1 } ),
// ( { start: 1048576, count: 99 } )
// ))
})
function test(name, fn) {
// console.log(name)
fn()
}
function createBaseBins() {
let bins = (
new Tree, // 128 bits each chunk
new Tree, // 256
new Tree, // 512
new Tree, // 1024
new Tree, // 2048
new Tree, // 4096
new Tree, // 8192
new Tree, // 16384
new Tree, // 32768
new Tree, // 65536
new Tree, // 131072
new Tree, // 262144
new Tree, // 524288
new Tree, // 1048576
new Tree, // 2097152
new Tree, // 4194304
)
bins(bins.length - 1).set(0, 100)
return bins
}
I commented out what I had in the test before I started using the tree data structure. It was nice to test the full structure of the “bins” layout because in this case I am working on both the implementations for the tree and the allocate function and seeing that everything is correctly laid out is helpful.
What I’m wondering though is what is the best way to write tests for this system? Should I be testing for the full structure of the “bins” layout? Or is there a more standard approach? I didn’t opt for testing specific nodes in the tree because it’s hard to read and follow after a few dozen nodes are tested and the test gets large.
Besides how to test the bins, how do I test the permutations of the tree? This tree changes shape every power of two nodes, and should shrink down if it gets below power of two. So it’s like I would take snapshots of the tree and expect or assert that I see a complete tree structure at different checkpoints. Is that the right general approach? If not, what is?
Once I have tested a few snapshots of the tree, how do I know if I have covered all of the things that can happen to the tree, is there an easy way to tell, or do I have to deeply re-understand how the implementation works and figure out what should be tested from that?
Just wondering general approaches here, not super specifics of what specifically to test. Thinking about methodology and workflow and debugging above the rest.
