Motivating example</h1>

Say you want to write an integer hash-set implementation in C. You might start like this:</p>

/* a hash-set implemented with a flat open-addressed array with linear probing */
struct set {
    int *entries;
    size_t N;
};
void set_init(struct set *set, size_t initial) {
    /* make sure N is a power of 2, with enough capacity to minimize collisions */
    for (set->N = 8; set->N < initial * 2; set->N *= 2) ;
    set->entries = calloc(set->N, sizeof *set->entries);
}
unsigned inthash(unsigned x) { ... }
bool set_contains(struct set *set, int x) {
    int h = inthash(x) & (set->N - 1), i = h;
    do {
 ---->  if (entry i is empty)  <----
            return 0;
        else if (set->entries[i] == x)
            return 1;
        i = (i + 1) & (set->N - 1);
    } while (i != h);
    /* set is full, looped around */
    return 0;
}
void _set_grow(struct set *set) { ... } // omitted for brevity
void set_put(struct set *set, int x) {
    int h = inthash(x) & (set->N - 1), i = h;
    do {
 ---->  if (entry i is empty)  <----
            set->entries[i] = x;
        else if (set->entries[i] == x)
            return; /* nothing to do */
        i = (i + 1) & (set->N - 1);
    } while (i != h);
    /* full set, looped around */
    _set_grow(set);
    set_put(set, x);
}
</code></pre>
The problem is, if every array item can hold a key, how do you mark an entry as
empty?  There's two ways you can go about this:</p>

Out-of-band signaling, so you keep a separate array bool *hasentry</code> also of size N,
which for every index stores whether the corresponding entry is used or
empty. Initialized to zeroes and updated when new entries are added in
set_put</code>.  Instead of 1 byte per entry with a bool array, you can be more
efficient using a bit array.  This is the generalized approach that is useful
if the values the set is storing are truly arbitrary.</li>
In-band signaling, meaning you reserve a special sentinel value to
represent an empty entry. This places a restriction in the values your set can hold,
but very often this is fine. This technique is for this use case.</li>
</ul>
So the easy case is if your sentinel value is zero, then it's a matter of changing</p>
       if (entry i is empty)
</code></pre>
into</p>
       if (!set->entries[i])
</code></pre>
and adding a check like</p>
void set_put(struct set *set, int x) {
    assert(x != 0 && "illegal value");
    ...
}
</code></pre>
Note that in set_init</code> (and _set_grow</code>), the use of calloc</code> already zeroes
the whole array, marking it initially as all empty, exactly as we want.</p>
But in practice, very often the integers you might wanna store in the set are
not arbitrary (so you can use the sentinel technique), but zero is a value you
would like to be able to store, thus not a good sentinel. In this case you have
to fallback to a non-zero sentinel, for example</p>
#define _SET_EMPTY INT_MIN
void set_init(struct set *set, size_t initial) {
    ...
    set->entries = malloc(set->N);
    for (int i = 0; i < set->N; ++i) set->entries[i] = _SET_EMPTY;
}
bool set_contains(struct set *set, int x) {
  ...
        if (set->entries[i] == _SET_EMPTY)
            return 0;
  ...
}
void _set_grow(struct set *set) {
    int *old_entries = set->entries;
    size_t old_N = set->N;
    set->entries = malloc(set->N *= 2);
    for (int i = 0; i < set->N; ++i) set->entries[i] = _SET_EMPTY;
    ...
}
void set_put(struct set *set, int x) {
    assert(x != _SET_EMPTY && "illegal value");
  ...
        if (set->entries[i] == _SET_EMPTY)
            set->entries[i] = x;
  ...
}
</code></pre>
This works fine, but we lose the nicety of calloc</code>.</p>
My trick combines the benefits of the zero-sentinel (initialization for free)
and an arbitrary sentinel by simply storing the value XORed with the sentinel.</p>

We keep the calloc</code>s for zero initialization</li>
if (entry i is empty)</code> becomes if (!set->entries[i])</code></li>
We XOR the value with the sentinel before storing it and when getting it
out of an entry:</li>
</ul>
Thus:</p>
bool set_contains(struct set *set, int x) {
    int h = inthash(x) & (set->N - 1), i = h;
    do {
        if (!set->entries[i])
            return 0;
        else if ((set->entries[i] ^ _SET_EMPTY) == x)  // <--------
            return 1;
        i = (i + 1) & (set->N - 1);
    } while (i != h);
    /* set is full, looped around */
    return 0;
}
void set_put(struct set *set, int x) {
    int h = inthash(x) & (set->N - 1), i = h;
    assert(x != _SET_EMPTY && "illegal value");
    do {
        if (!set->entries[i])
            set->entries[i] = x ^ _SET_EMPTY;  // <--------
        else if ((set->entries[i] ^ _SET_EMPTY) == x) // <-------
            return; /* nothing to do */
        i = (i + 1) & (set->N - 1);
    } while (i != h);
    /* full set, looped around */
    _set_grow(set);
    set_put(set, x);
}
</code></pre>
This works because of the mathematical properties of bitwise XOR:</p>

x^y == 0</code> if and only if x == y</code>,</li>
If x^y = z</code> then z^y = x</code> and x^z = y</code> (XOR is reversible)</li>
</ul>
In situations where calloc</code> is more efficient than malloc</code> + manual
initialization, this is a potentially more efficient solution, especially if
the size of your set is unpredictable and could grow multiple times.</p>