CDB over HTTP

hash.ts

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;
}

streaming.ts

/* 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);
    }
}