Skip to content

Instantly share code, notes, and snippets.

@chocolatkey
Created February 4, 2023 10:52
Show Gist options
  • Save chocolatkey/5e0cd4445d24e8885bef065b0b68d568 to your computer and use it in GitHub Desktop.
Save chocolatkey/5e0cd4445d24e8885bef065b0b68d568 to your computer and use it in GitHub Desktop.
CDB over HTTP
const STARTING_HASH = 5381;
export default function cdbHash(key: string) {
let hash = STARTING_HASH;
const length = key.length;
for (let i = 0; i < length; i++) {
hash = ((((hash << 5) >>> 0) + hash) ^ key.charCodeAt(i)) >>> 0;
}
return hash;
}
/* eslint-disable @typescript-eslint/no-non-null-assertion */
import cdbHash from "./hash";
const HEADER_SIZE = 2048;
const TABLE_SIZE = 256;
export default class StreamingCDB {
private readonly file: string;
private readonly header: Array<{ position: number, slotCount: number }>;
private cachedSlots: Uint32Array | null;
private destroyed = false;
constructor(fileURL: string) {
this.file = fileURL;
this.header = new Array(TABLE_SIZE);
this.cachedSlots = null;
}
destroy() {
this.destroyed = true;
this.cachedSlots = null;
}
async open(): Promise<void> {
if (this.destroyed) return;
let r = await fetch(this.file, {
headers: {
"range": `bytes=0-${HEADER_SIZE - 1}`
}
});
if (this.destroyed) return;
const rawHeaderUints = new Uint32Array(await r.arrayBuffer());
// Fill table
let bufferPosition = 0;
for (let i = 0; i < TABLE_SIZE; i++) {
const position = rawHeaderUints[bufferPosition];
const slotCount = rawHeaderUints[bufferPosition + 1];
this.header[i] = {
position: position,
slotCount: slotCount
};
bufferPosition += 2;
}
r = await fetch(this.file, {
headers: {
"range": `bytes=${this.header[0].position}-`
}
});
if (this.destroyed) return;
this.cachedSlots = new Uint32Array(await r.arrayBuffer());
}
async get(key: string): Promise<Uint8Array | null> {
const hash = cdbHash(key),
hashtableIndex = hash & 255,
hashtable = this.header[hashtableIndex],
position = hashtable.position,
slotCount = hashtable.slotCount,
trueKeyLength = key.length;
let slot = (hash >>> 8) % slotCount;
let recordPosition: number;
let keyLength: number;
if (slotCount === 0 || this.cachedSlots === null) {
return null;
}
const readSlot = async (slot: number): Promise<Uint8Array | null> => {
const hashPosition = position - this.header[0].position + ((slot % slotCount) * 8);
const hashPositionUint32 = hashPosition / 4;
const recordHash = this.cachedSlots![hashPositionUint32];
recordPosition = this.cachedSlots![hashPositionUint32 + 1];
if (recordHash === hash) {
const r = await fetch(this.file, {
headers: {
"range": `bytes=${recordPosition}-${recordPosition + 7}`
}
});
if (this.destroyed) return null;
const buff = await r.arrayBuffer();
return await readKey(new Uint32Array(buff));
} else if (recordHash === 0) {
return null;
} else {
return await readSlot(++slot);
}
}
const readKey = async (buffer: Uint32Array): Promise<Uint8Array | null> => {
keyLength = buffer[0];
const dataLength = buffer[1];
// In the rare case that there is a hash collision, check the key size
// to prevent reading in a key that will definitely not match.
if (keyLength !== trueKeyLength) {
return await readSlot(++slot);
}
const start = recordPosition + 8;
const r = await fetch(this.file, {
headers: {
"range": `bytes=${start}-${start + keyLength + dataLength - 1}`
}
});
if (this.destroyed) return null;
return await process(await r.arrayBuffer());
}
const process = async (buffer: ArrayBuffer): Promise<Uint8Array | null> => {
const buffString = (new TextDecoder()).decode(buffer.slice(0, keyLength));
if (buffString === key) {
return new Uint8Array(buffer.slice(keyLength));
} else {
return await readSlot(++slot);
}
}
return await readSlot(slot);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment