Now that I've been slogging through the machanical translation of QuickJS structs/types and utility functions for a month or so, I've actually begun to hit the more interesting parts of the code. The last week I've been going through some the JSAtom related code, and how it's handled in the JSRuntime. This post is mostly to serve as notes to myself disecting the JSRuntime->atom_array related functions.

Here's the documentation about atoms:

4.3.3 Atoms

Object property names and some strings are stored as Atoms (unique strings) to save memory and allow fast comparison. Atoms are represented as a 32 bit integer. Half of the atom range is reserved for immediate integer literals from 0 to 2^{31}-1.

And, for reference, here's the relavent parts os JSRuntime that I'm looking at:

struct JSRuntime {
    int atom_hash_size; /* power of two */
    int atom_count;
    int atom_size;
    int atom_count_resize; /* resize hash table at this count */
    uint32_t *atom_hash;
    JSAtomStruct **atom_array;
    int atom_free_index; /* 0 = none */
}

I've been looking over the __JS_NewAtom and __JS_FindAtom functions to understand how all the variables work together, and as the names suggest, I can tell it's implementing some sort of hash table. However, as the documentation mentions, atoms will also store integer literals, which makes the code slightly more complicated than a standard hash table.

Looking at how the variables are used, it seems that atom_array is the values being stored in the table, and the index of the hash in atom_hash corresponds to the index into the atom_array such that:

i = atom_hash[ HASH(key) ]
atom_values = atom_array[i]

If there are collisions for a hash, atom_array is a linked list that the key can be compared to.

It is all pretty standard hash-table stuff, but since I don't think I've ever actually implemented a hashtable from hand before, I find it quite interesting code.

These are how the variables are used, given a quick read over the code:

• atom_hash_size: number of entries in atom_hash, always a power of 2. Is also used as a mask for the hash-key to prevent out-of-bounds addressing
• atom_count: number of entries in the hash table (including collisions)
• atom_size: array size of atom_array (entries minus collisions)
• atom_count_resize: Number of entries to resize at
• atom_hash: array of ints. The ints are the index into atom_array
• atom_array: array of linked lists that store the "values" of the hash table
• atom_free_index: The index into atom_hash that is free for an entry (where new entries can be made)

Next post, I'll go more into detail of how the hashing works with resizing. I think I'll also attempt to translate just the hash table part into Rust to get a better understanding by implementing it