cdb(5)

💖 cdb(5) — the file format manual, bestie edition 💖

okay so this is cdb(5), from the File Formats Manual section. It's literally the blueprint for the Constant DataBase file format, and I'm gonna walk you through it like we're texting at 2am. 🦋

---

✨ NAME ✨

cdb — Constant DataBase file format. That's it, that's the whole vibe. 👑

---

🌸 DESCRIPTION 🌸

A cdb database is a single file that maps keys to values, and it does that by storing a bunch of (key,value) pair records. No cap. The file is made of 3 parts:

1. toc — the table of contents 🎀
2. data — the actual records 💖
3. index — the hash tables 🔥

🗂️ the toc section

Toc has a fixed length of 2048 bytes, and inside it there are 256 pointers pointing to hash tables inside the index section. Every single pointer is made of two things:

• the position of a hash table in bytes from the beginning of a file
• the size of a hash table in entries

Both of those are 4-byte (32 bits) unsigned integers in little-endian form. And lowkey important: a hash table length may be zero, which means that corresponding hash table is empty. It's giving "nothing to see here". 💀

📦 the data section

Right after the toc section, the data section follows without any alignment. It's just a series of records, and each record is:

• a key length
• a value (data) length
• the key
• the value

Again, key and value length are 4-byte unsigned integers. And each next record follows the previous one without any special alignment — they're just snuggled up next to each other, no personal space. 🫶

🔍 the index (hash tables) section

After the data section comes the index section. You must read it together with the toc section, because that's where each of the max 256 hash tables is defined. The index section is a series of hash tables, and their starting position and length are defined in the toc section.

Every hash table is a sequence of records, and each record holds two numbers:

• the key's hash value
• the record position inside the data section — that's the number of bytes from the beginning of a file to the first byte of the key length that starts the data record

If the record position is zero, then this is an empty hash table slot, pointed to nowhere. Not it. 🙈

🧮 the CDB hash function, periodt

The CDB hash function is literally this:

hv = ((hv << 5) + hv) ^ c

for every single c byte of a key, starting with hv = 5381. Slay. ✨

The toc section is indexed by (hv % 256), i.e. the hash value modulo 256 (which is the number of entries in the toc section).

🕵️ how to actually find a record

In order to find a record, one should do this, in order:

1. First, compute the hash value (hv) of a key.
2. Second, look to hash table number hv modulo 256. If it is empty, then there is no such key, exists no more, gone. If it is not empty, then…
3. Third, loop by slots inside that hash table, starting from the slot with number hv divided by 256 modulo the length of that table, or ((hv / 256) % htlen), searching for this hv in the hash table. Stop the search on an empty slot (if record position is zero) or when all slots have been probed.

⚠️ Note the search is cyclic — it jumps from the end back to the beginning of a table. Don't forget that part, bestie, it's a whole thing. 😭

When the hash value in question is found in the hash table, look to the key of the corresponding record and compare it with the key in question. If they're of the same length and equal to each other, then the record is found 🎉 — otherwise, repeat with the next hash table slot.

👑 And one more thing: there may be several records with the same key. Not a bug, just the format living its truth.

---

🌈 SEE ALSO 🌈

• cdb(1)
• cdb(3)

---

💜 AUTHOR 💜

The tinycdb package, written by Michael Tokarev <mjt+cdb@corpit.ru>, based on ideas and shares file format with the original cdb library by Dan Bernstein. Icons only, fr fr. 🫶

---

🎀 LICENSE 🎀

Tinycdb is licensed under the MIT license. 💅

---

And that's the whole page, bestie — this was cdb(5) from the tinycdb package, dated Apr, 2005. Go forth and hash responsibly. 🌸✨💖