optional.h

#pragma once

/** Define an "optional" value, where the first bit indicates
 * whether the value has been set and the remaining bits are used
 * for the actual value.
 *
 * The up-side of this definition is that it is equally space efficient
 * as simply storing an array of the underlying type.
 *
 * The down-side of this definition is that you lose a whole bit of possible
 * values. If it is important to be able to use the whole range of values, two
 * arrays (as in data_table.h) is more efficient (compared to using a larger
 * value type or relaxing the bit field width).
 *
 * An array of ints with an array for tracking which values have been set is
 *   sizeof (int) * N + N bytes
 *
 * An array of optional (int) is
 *
 *   sizeof (int) * N
 *
 * For, say, N = 1000, the first gives 5000 bytes, the second 4000.
 * Using optional (long) instead of int, however, would consume 8000 bytes,
 * more than doubling space usage compared to optional (int).
 */
#define optional(T)                             \
  struct {                                      \
    bool isset : 1;                             \
    T value : (sizeof (T) * 8 - 1);             \
  }