2f:Te73,class Tree { /** * @typedef {object} Node * @property {number} level * @property {Uint8Array} key * @property {Uint8Array} hash * * @typedef {object} Anchor * @property {void} key * @property {Uint8Array} hash * * @typedef {Node[]} Layer * * @typedef {[[Node], ...Layer[]]} Model * * @param {Model} [model] */ constructor( model = [ { level: 0, hash: digest({ key: new Uint8Array(), value: Uint8Array() }) } ] ) { this.model = model; } static root([[root]]) { return root; } static digestLayer(nodes) { const hash = Blake3.blake3.create(); for (const node of nodes) { hash.update(node.hash); } return hash.digest(); } static set(tree, key, value) { const root = Tree.root(tree); const hash = digest({ key, value }); // If this was an empty tree we simply use root as an anchor node // and add leaf next to it creating a leaf layer. Then we derive // the new root. if (root.level === 0) { const leaves = [root, { level: 0, key, hash }]; return [[{ level: 1, hash: Tree.digestLayer(leaves) }], leaves]; } else { const height = tree.length; const path = []; let level = 1; layer: while (level < height) { const layer = tree[level]; let width = layer.length; let offset = 1; node: while (offset < width) { const node = layer[offset]; switch (Tree.compareKeys(key, node.key)) { case BEFORE: path.push(offset - 1); continue layer; // leaf goes into previous node case SAME: // leaf goes into this node path.push(offset); continue layer; case AFTER: // leaf goes in one of the following branches break; } ++offset; } ++level; } return Tree.setNode(tree, root.level - 1, null, key, value); } } static setLeaf(tree, head, key, value) { const hash = digest({ key, value }); Tree.insert({ level: 0, key, value, hash }); const newSiblings = []; switch (Tree.compareKeys(head, key)) { case -1: { } } if (Tree.compareKeys(head, key) < 0) { if (Tree.isSplit(hash)) { newSiblings.push(key); return Tree.update(); } else if (Tree.compareKeys(head, key) === 0) { if (head == null || Tree.isSplit(key)) { return Tree.update(); } else { return Tree.delete(); } } else { throw new Error("Invalid tree"); } } } static limit = Number((1n << 32n) / 32n); /** * @param {Uint8Array} hash */ static isSplit(hash) { const view = new DataView(hash.buffer, hash.byteOffset, 4); return view.getUint32(0) < Tree.limit; } /** * @param {Uint8Array|null|undefined} self * @param {Uint8Array|null|undefined} self */ static compareKeys(self, other) { if (self == null) { return other == null ? 0 : -1; } else if (other == null) { return 1; } else { const count = Math.min(self.length, other.length); let offset = 0; while (offset < count) { const delta = self[offset] - other[offset]; if (delta < 0) { return -1; } else if (delta > 0) { return 1; } else { offset++; } } const delta = self.length - other.length; return delta < 0 ? -1 : delta > 0 ? 1 : 0; } } /** * @param {Uint8Array} key * @param {Uint8Array} value */ set(key, value) { const { root } = Tree.root(this.model); } }30:Tf01,class Branch { static digest({ children }) { const hash = Blake3.blake3.create(); for (const child of children) { hash.update(child.hash); } return hash.digest(); } constructor( { height, key, children } = { height: 1, key: new Uint8Array(), children: [] } ) { this.height = height; this.key = key; this.children = children; this.hash = Branch.digest(this); this.isBoundary = isBoundary(this.hash); } set(key, value = new Uint8Array(0)) { const nodes = Branch.insert(this, new Leaf({ key, value })); return nodes.length === 1 ? nodes[0] : Branch.build(nodes); } static insertLeafAt(tree, leaf, at) { if (leaf.isBoundary) { return [ new Branch({ height: tree.height, key: tree.key, children: tree.children.slice(0, at) }), new Branch({ height: tree.height, key: tree.key, children: [leaf, ...tree.childen.slice(at)] }) ]; } else { return [ new Branch({ height: tree.height, key: tree.key, children: [ ...tree.children.slice(0, at), leaf, ...tree.children.slice(at) ] }) ]; } } static insert(tree, leaf) { if (tree.children.length === 0) { return [ new Branch({ height: 1, key: leaf.key, children: [leaf] }) ]; } else if (tree.height === 1) { const children = tree.children; const width = children.length; let offset = 0; while (offset < width) { const child = children[offset]; const position = Tree.compareKeys(leaf.key, child.key); if (position === 0) { const order = Tree.compareKeys(leaf.hash, child.hash); if (order === 0) { // no-op move on return [tree]; } else { // if leaf goes before current child we split at previous child index // otherwise at this child index const at = order < 0 ? -1 : 0; return Branch.insertLeafAt(tree, leaf, at); } } else if (position < 0) { return Branch.insertLeafAt(tree, leaf, offset - 1); } offset++; } return Branch.insertLeafAt(tree, leaf, offset); } else { const children = tree.children; const width = nodes.length; const nodes = []; let offset = 0; while (offset < width) { const child = children[offset]; const position = Tree.compareKeys(leaf.key, child.key); if (position === 0) { nodes.push(...Branch.insert(child, leaf)); offset++; break; } else if (position < 0) { if (offset > 0) { nodes.pop(); nodes.push(...Branch.insert(children[offset - 1], leaf)); } else { nodes.push(...Branch.insert(child, leaf)); } offset++; break; } else { offset++; nodes.push(child); } } while (offset < width) { nodes.push(children[offset]); offset++; } return Branch.build(nodes); } } static build(nodes) { const branches = []; let start = 0; let offset = 1; while (offset < nodes.length) { const node = nodes[offset]; if (node.isBoundary || offset === node.length - 1) { const node = nodes[start]; branches.push( new Branch({ height: node.height + 1, key: node.key, children: nodes.slice(start, offset) }) ); start = offset; } offset++; } return branches.length === 1 ? branches[0] : Branch.build(branches); } }31:[] 2d:{"title":"Orka Prolly Tree","cells":[{"id":0,"value":"# [Orka](https://github.com/canvasxyz/okra-js) Prolly Tree","pinned":false,"hidden":false,"mode":"md"},{"id":5,"value":"MemoryTree = (await import(\"https://esm.sh/@canvas-js/okra-memory\")).MemoryTree","pinned":true,"hidden":false,"mode":"ojs"},{"id":190,"value":"import { varint } from \"@gozala/ipld\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":77,"value":"Blake3 = await import(\"https://esm.sh/@noble/hashes/blake3\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":13,"value":"tree = await MemoryTree.open()","pinned":true,"hidden":false,"mode":"ojs"},{"id":20,"value":"utf8 = new TextEncoder()","pinned":true,"hidden":false,"mode":"ojs"},{"id":22,"value":"key = (value) => utf8.encode(value)","pinned":false,"hidden":false,"mode":"ojs"},{"id":61,"value":"collect = async (source) => {\n const items = [];\n for await (const [key, value] of source) {\n items.push([decode(key), decode(value)]);\n }\n return items;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":28,"value":"encode = (text) => utf8.encode(text)","pinned":true,"hidden":false,"mode":"ojs"},{"id":67,"value":"decoder = new TextDecoder()","pinned":true,"hidden":false,"mode":"ojs"},{"id":68,"value":"decode = (bytes) => decoder.decode(bytes)","pinned":true,"hidden":false,"mode":"ojs"},{"id":101,"value":"print = async (tree) => {\n const chunks = [];\n for await (const chunk of tree.print()) {\n chunks.push(decode(chunk));\n }\n return html`

${chunks.join(\"\")}`;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":85,"value":"lengthBytes = new Uint8Array(4)","pinned":true,"hidden":false,"mode":"ojs"},{"id":83,"value":"lengthView = new DataView(lengthBytes.buffer)","pinned":true,"hidden":false,"mode":"ojs"},{"id":80,"value":"digest = ({ key, value }) => {\n  const buffer = new Uint8Array(4 + key.length + 4 + value.length);\n  let offset = 0;\n  lengthView.setUint32(0, key.length);\n\n  buffer.set(lengthBytes, offset);\n  offset += lengthBytes.length;\n\n  buffer.set(key, offset);\n  offset += key.length;\n\n  lengthView.setUint32(0, value.length);\n  buffer.set(lengthBytes, offset);\n  offset += lengthView.length;\n\n  buffer.set(value, offset);\n\n  return Blake3.blake3(buffer);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":15,"value":"tree.getRoot()","pinned":true,"hidden":false,"mode":"ojs"},{"id":26,"value":"tree.set(key(\"blog/idea/1\"), encode(\"Dear reader, I've got a great idea\"))","pinned":true,"hidden":false,"mode":"ojs"},{"id":31,"value":"tree.getRoot()","pinned":true,"hidden":false,"mode":"ojs"},{"id":33,"value":"tree.set(key(\"blog/idea/1\"), encode(\"I have another idea\"))","pinned":true,"hidden":false,"mode":"ojs"},{"id":37,"value":"tree.getChildren(1, null)","pinned":true,"hidden":false,"mode":"ojs"},{"id":55,"value":"tree.set(key(\"pictures/1\"), encode(\"\"))","pinned":true,"hidden":false,"mode":"ojs"},{"id":47,"value":"collect(tree.entries({ key: key(\"blog/idea/1\"), inclusive: true }))","pinned":true,"hidden":false,"mode":"ojs"},{"id":93,"value":"digest({ key: \"picture/1\", value: \"\" })","pinned":true,"hidden":false,"mode":"ojs"},{"id":97,"value":"tree.getChildren(1, null)","pinned":false,"hidden":false,"mode":"ojs"},{"id":158,"value":"BEFORE = -1","pinned":true,"hidden":false,"mode":"ojs"},{"id":159,"value":"AFTER = 1","pinned":true,"hidden":false,"mode":"ojs"},{"id":161,"value":"SAME = 0","pinned":true,"hidden":false,"mode":"ojs"},{"id":110,"value":"$2f","pinned":true,"hidden":false,"mode":"ojs"},{"id":231,"value":"Q = 32n","pinned":true,"hidden":false,"mode":"ojs"},{"id":229,"value":"LIMIT = Number((1n << 32n) / Q);","pinned":true,"hidden":false,"mode":"ojs"},{"id":284,"value":"isBoundary = (hash) => decodeUint32(hash) < Tree.limit","pinned":true,"hidden":false,"mode":"ojs"},{"id":256,"value":"Uint32 = new Uint32Array(1)","pinned":true,"hidden":false,"mode":"ojs"},{"id":262,"value":"Uint32Bytes = new Uint8Array(Uint32.buffer)","pinned":true,"hidden":false,"mode":"ojs"},{"id":260,"value":"encodeUint32 = (n) => {\n  Uint32[0] = n;\n  return Uint32Bytes;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":265,"value":"decodeUint32 = (bytes) => {\n  Uint32Bytes[0] = bytes[0];\n  Uint32Bytes[1] = bytes[1];\n  Uint32Bytes[2] = bytes[2];\n  Uint32Bytes[3] = bytes[3];\n  return Uint32[0];\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":244,"value":"readUInt32 = (bytes) =>\n  bytes[0] * 0x1000000 + ((bytes[1] << 16) | (bytes[2] << 8) | bytes[3])","pinned":true,"hidden":false,"mode":"ojs"},{"id":251,"value":"encodeUint32(5)","pinned":true,"hidden":false,"mode":"ojs"},{"id":253,"value":"decodeUint32([5, 5, 5, 5])","pinned":true,"hidden":false,"mode":"ojs"},{"id":169,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":183,"value":"class Leaf {\n  static digest({ key, value }) {\n    const hash = Blake3.blake3.create();\n    hash.update(encodeUint32(key.length));\n    hash.update(key);\n    hash.update(encodeUint32(value.length));\n    hash.update(value);\n\n    return hash.digest();\n  }\n  constructor({ key, value }) {\n    this.height = 0;\n    this.key = key;\n    this.value = value;\n    this.hash = Leaf.digest(this);\n    this.isBoundary = isBoundary(this.hash);\n  }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":224,"value":"t1 = new Branch()","pinned":true,"hidden":false,"mode":"ojs"},{"id":306,"value":"t2 = t1.set(key(\"a\"), key(\"\"))","pinned":true,"hidden":false,"mode":"ojs"},{"id":321,"value":"t2.set(key(\"b\")).set(key(\"c\")).set(key(\"a\"), key(\"a\"))","pinned":true,"hidden":false,"mode":"ojs"},{"id":130,"value":"\"b\".localeCompare(\"a\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":116,"value":"Blake3.blake3(\"\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":125,"value":"empty = await MemoryTree.open()","pinned":true,"hidden":false,"mode":"ojs"},{"id":127,"value":"empty.getRoot()","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}