bloomish.cpp

struct BloomishSet {
    enum { TABLE_BITS = 4, COUNTER_BITS = 4, TEST_LIMIT = 8 };
    uint32_t size;
    uint64_t table[1 << TABLE_BITS];

    BloomishSet() : size(0) {
        memset(table, 0, sizeof table);
    }

#ifdef DEBUG
    ~BloomishSet() {
        assert(size == 0);
        uint64_t test[1 << TABLE_BITS] = {};
        assert(memcmp(table, test, sizeof table) == 0);
    }
#endif

    uint64_t tagAtom(JSAtom* atom) {
        // Create a COUNTER_BITS-bit counter in the bottom of the pointer, initially 1.
        uintptr_t p = (uintptr_t)atom;
        assert(p << COUNTER_BITS >> COUNTER_BITS == p);
        static_assert(sizeof(uintptr_t) <= sizeof(uint64_t));
        return (uint64_t)(p << COUNTER_BITS) | 1;
    }

    HashNumber hashAtom(JSAtom* atom) {
        // Fast hasher. Atoms don't move within the parser, so this is fine, right?
        // The non-determinstism is sad, though, and this at least needs some form
        // of HashString when JS_MORE_DETERMINISTIC is set.
        static_assert(sizeof(HashNumber) == 4);
        return ScrambleHashCode((HashNumber)(uintptr_t)atom) >> (32 - TABLE_BITS);
    }

    bool isDefinitelyIncluded(JSAtom* atom) {
        // As long as size <= 2^COUNTER_BITS, this test has no false positives
        // due to counter wrap-around.  The probability of a false negative,
        // which happens if the atom is included in the table but collides with
        // something else, is roughly exp(-tableSize / (size - 1)); if this is
        // large enough the test is not worth performing.  Thus we set TEST_LIMIT
        // a bit smaller than 2^COUNTER_BITS (8 taken out of thin air).
        return 0 < size && size <= TEST_LIMIT && table[hashAtom(atom)] == tagAtom(atom);
    }

    void remove(JSAtom* atom) {
        assert(size != 0);
        assert(size >= (1 << COUNTER_BITS) ||
            (table[hashAtom(atom)] & ((1 << COUNTER_BITS) - 1)) > 0);
        size--;
        table[hashAtom(atom)] -= tagAtom(atom);
    }

    void add(JSAtom* atom) {
        size++;
        assert(size != 0);
        table[hashAtom(atom)] += tagAtom(atom);
    }
};

// ...

ParseContext::maybeNoteUsedName(LifoAlloc& alloc, JSAtom* name) {
    if (!innermostFunctionBindingsSet.isDefinitelyIncluded(name))
        noteUsedName(alloc, name);
}
// add() when adding a new, unique binding, remove() when popping its scope