sparsemap/sparsemap.c

/*
 * Copyright (c) 2024 Gregory Burd <greg@burd.me>.  All rights reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

#include <sys/types.h>

#include <errno.h>
#include <popcount.h>
#include <sparsemap.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifdef SPARSEMAP_DIAGNOSTIC
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpedantic"
#pragma GCC diagnostic ignored "-Wvariadic-macros"
#define __sm_diag(format, ...) __sm_diag_(__FILE__, __LINE__, __func__, format, ##__VA_ARGS__)
#pragma GCC diagnostic pop
void __attribute__((format(printf, 4, 5))) __sm_diag_(const char *file, int line, const char *func, const char *format, ...)
{
  va_list args = { 0 };
  fprintf(stderr, "%s:%d:%s(): ", file, line, func);
  va_start(args, format);
  vfprintf(stderr, format, args);
  va_end(args);
}

#define __sm_assert(expr) \
  if (!(expr))            \
  fprintf(stderr, "%s:%d:%s(): assertion failed! %s\n", __FILE__, __LINE__, __func__, #expr)

#define __sm_when_diag(expr) \
  if (1)                     \
  expr
#else
#define __sm_diag(file, line, func, format, ...) ((void)0)
#define __sm_assert(expr) ((void)0)
#define __sm_when_diag(expr) \
  if (0)                     \
  expr
#endif

#define IS_8_BYTE_ALIGNED(addr) (((uintptr_t)(addr)&0x7) == 0)

typedef uint64_t __sm_bitvec_t;
typedef uint32_t __sm_idx_t;

typedef struct {
  __sm_bitvec_t *m_data;
} __sm_chunk_t;

typedef struct {
  size_t rem;
  size_t pos;
} __sm_chunk_rank_t;

// NOTE: When using in production feel free to remove this section of test code.
#ifdef SPARSEMAP_TESTING
#include <inttypes.h>
char *QCC_showSparsemap(void *value, int len);
char *QCC_showChunk(void *value, int len);
static char *_qcc_format_chunk(__sm_idx_t start, __sm_chunk_t *chunk, bool none);

static void __attribute__((format(printf, 2, 3)))
__sm_diag_map(sparsemap_t *map, const char *fmt, ...)
{
  va_list args = { 0 };
  va_start(args, fmt);
  vfprintf(stdout, fmt, args);
  va_end(args);
  char *s = QCC_showSparsemap(map, 0);
  fprintf(stdout, "\n%s\n", s);
  free(s);
}

static void
__sm_diag_chunk(const char *msg, __sm_chunk_t *chunk)
{
  char *s = QCC_showChunk(chunk, 0);
  fprintf(stdout, "%s\n%s\n", msg, s);
  free(s);
}
#endif

enum __SM_CHUNK_INFO {
  /* metadata overhead: 4 bytes for __sm_chunk_t count */
  SM_SIZEOF_OVERHEAD = sizeof(__sm_idx_t),

  /* number of bits that can be stored in a __sm_bitvec_t */
  SM_BITS_PER_VECTOR = (sizeof(__sm_bitvec_t) * 8),

  /* number of flags that can be stored in a single index byte */
  SM_FLAGS_PER_INDEX_BYTE = 4,

  /* number of flags that can be stored in the index */
  SM_FLAGS_PER_INDEX = (sizeof(__sm_bitvec_t) * SM_FLAGS_PER_INDEX_BYTE),

  /* maximum capacity of a __sm_chunk_t (in bits) */
  SM_CHUNK_MAX_CAPACITY = (SM_BITS_PER_VECTOR * SM_FLAGS_PER_INDEX),

  /* maximum capacity of a __sm_chunk_t (31 bits of the RLE) */
  SM_CHUNK_RLE_MAX_CAPACITY = 0x7FFFFFFF,

  /* minimum capacity of a __sm_chunk_t (in bits) */
  SM_CHUNK_MIN_CAPACITY = (SM_BITS_PER_VECTOR - 2),

  /* maximum length of a __sm_chunk_t (31 bits of the RLE) */
  SM_CHUNK_RLE_MAX_LENGTH = 0x7FFFFFFF,

  /* __sm_bitvec_t payload is all zeros (2#00) */
  SM_PAYLOAD_ZEROS = 0,

  /* __sm_bitvec_t payload is all ones (2#11) */
  SM_PAYLOAD_ONES = 3,

  /* __sm_bitvec_t payload is mixed (2#10) */
  SM_PAYLOAD_MIXED = 2,

  /* __sm_bitvec_t is not used (2#01) */
  SM_PAYLOAD_NONE = 1,

  /* a mask for checking flags (2 bits, 2#11) */
  SM_FLAG_MASK = 3,

  /* return code for set(): ok, no further action required */
  SM_OK = 0,

  /* return code for set(): needs to grow this __sm_chunk_t */
  SM_NEEDS_TO_GROW = 1,

  /* return code for set(): needs to shrink this __sm_chunk_t */
  SM_NEEDS_TO_SHRINK = 2
};

/* Used when separating a RLE chunk into 2-3 chunks */
typedef struct {
  struct {
    uint8_t *p;          // pointer into m_data
    size_t offset;       // offset in m_data
    __sm_chunk_t *chunk; // chunk to be split
    __sm_idx_t start;    // start of chunk
    size_t length;       // initial length of chunk
    size_t capacity;     // the capacity of this RLE chunk
  } target;

  struct {
    uint8_t *p;          // location in buf
    sparsemap_idx_t idx; // chunk-aligned to idx
    size_t size;         // byte size of this chunk
  } pivot;

  struct {
    sparsemap_idx_t start;
    sparsemap_idx_t end;
    uint8_t *p;
    size_t size;
    __sm_chunk_t c;
  } ex[2]; // 0 is "on the left", 1 is "on the right"

  uint8_t buf[(SM_SIZEOF_OVERHEAD * 3) + (sizeof(__sm_bitvec_t) * 6)];
  size_t expand_by;
  size_t count;
} __sm_chunk_sep_t;

#define SM_ENOUGH_SPACE(need)                          \
  do {                                                 \
    if (map->m_data_used + (need) > map->m_capacity) { \
      errno = ENOSPC;                                  \
      return SPARSEMAP_IDX_MAX;                        \
    }                                                  \
  } while (0)

#define SM_CHUNK_GET_FLAGS(data, at) ((((data)) & ((__sm_bitvec_t)SM_FLAG_MASK << ((at)*2))) >> ((at)*2))
#define SM_CHUNK_SET_FLAGS(data, at, to) (data) = ((data) & ~((__sm_bitvec_t)SM_FLAG_MASK << ((at)*2))) | ((__sm_bitvec_t)(to) << ((at)*2))
#define SM_IS_CHUNK_RLE(chunk) \
  (((*((__sm_bitvec_t *)(chunk)->m_data) & (((__sm_bitvec_t)0x3) << (SM_BITS_PER_VECTOR - 2))) >> (SM_BITS_PER_VECTOR - 2)) == SM_PAYLOAD_NONE)

#define SM_RLE_FLAGS 0x4000000000000000
#define SM_RLE_FLAGS_MASK 0xC000000000000000
#define SM_RLE_CAPACITY_MASK 0x3FFFFFFF80000000
#define SM_RLE_LENGTH_MASK 0x7FFFFFFF

/** @brief Determines if the chunk is RLE encoded.
 *
 * @param[in] chunk The chunk to test.
 * @return true when the chunk is run-length encoded (RLE), otherwise false.
 */
static inline bool
__sm_chunk_is_rle(__sm_chunk_t *chunk)
{
  __sm_bitvec_t w = chunk->m_data[0];
  return (w & SM_RLE_FLAGS_MASK) == SM_RLE_FLAGS;
}

/** @brief Changes the chunk to be flagged as RLE encoded.
 *
 * This doesn't change any other bits in the chunk's descriptor.
 *
 * @param[in] chunk The chunk to modify.
 */
static inline void
__sm_chunk_set_rle(__sm_chunk_t *chunk)
{
  __sm_bitvec_t w = chunk->m_data[0];
  w &= ~SM_RLE_FLAGS_MASK;
  w |= ((((__sm_bitvec_t)1) << (SM_BITS_PER_VECTOR - 2)) & SM_RLE_FLAGS_MASK);
  chunk->m_data[0] = w;
}

/** @brief Get the capacity of an RLE chunk.
 *
 * This only returns a meaningful value when chunk is RLE encoded.  This will
 * return garbage when called referencing a sparse chunk.
 *
 * @param[in] chunk The chunk in question.
 * @return The capacity of the RLE chunk, at most SM_CHUNK_RLE_MAX_CAPACITY.
 */
static inline size_t
__sm_chunk_rle_get_capacity(__sm_chunk_t *chunk)
{
  __sm_bitvec_t w = chunk->m_data[0] & (__sm_bitvec_t)SM_RLE_CAPACITY_MASK;
  w >>= 31;
  return w;
}

/** @brief Sets the capacity of the RLE chunk.
 *
 * This does not check the chunk type, if the chunk isn't RLE then this function
 * will overwrite flags data in a sparse chunk.
 *
 * @param[in] chunk The chunk in question.
 * @param[in] capacity The new capacity, at most SM_CHUNK_RLE_MAX_CAPACITY.
 */
static inline void
__sm_chunk_rle_set_capacity(__sm_chunk_t *chunk, size_t capacity)
{
  __sm_assert(capacity <= SM_CHUNK_RLE_MAX_CAPACITY);
  __sm_bitvec_t w = chunk->m_data[0];
  w &= ~SM_RLE_CAPACITY_MASK;
  w |= (capacity << 31) & SM_RLE_CAPACITY_MASK;
  chunk->m_data[0] = w;
}

/** @brief Get the current length of an RLE chunk.
 *
 * This only returns a meaningful value when chunk is RLE encoded.  This will
 * return garbage when called referencing a sparse chunk.
 *
 * @param[in] chunk The chunk in question.
 * @reutrn The current length of the run of adjacent ones encoded in this RLE
 * chunk, at most SM_CHUNK_RLE_MAX_CAPACITY.
 */
static inline size_t
__sm_chunk_rle_get_length(__sm_chunk_t *chunk)
{
  __sm_bitvec_t w = chunk->m_data[0] & (__sm_bitvec_t)SM_RLE_LENGTH_MASK;
  return w;
}

/** @brief Sets the length of the RLE chunk.
 *
 * This does not check the chunk type, if the chunk isn't RLE then this function
 * will overwrite flags data in a sparse chunk.
 *
 * @param[in] chunk The chunk in question.
 * @param[in] length The new capacity, at most SM_CHUNK_RLE_MAX_LENGTH.
 */
static inline void
__sm_chunk_rle_set_length(__sm_chunk_t *chunk, size_t length)
{
  __sm_assert(length <= SM_CHUNK_RLE_MAX_LENGTH);
  __sm_bitvec_t w = chunk->m_data[0];
  w &= ~SM_RLE_LENGTH_MASK;
  w |= length & SM_RLE_LENGTH_MASK;
  chunk->m_data[0] = w;
}

/** @brief Returns the length of a run of adjacent ones in this chunk.
 *
 * A "run" is a set of adjacent ones that starts at the 0th bit of this
 * chunk. For an RLE chunk that's encoded in the descriptor.  For a sparse chunk
 * we must see how many flags are SM_PAYLOAD_ONES and then if we find a
 * SM_PAYLOAD_MIXED count the additional adjacent ones if they exist.
 */
static size_t
__sm_chunk_get_run_length(__sm_chunk_t *chunk)
{
  size_t length = 0;

  if (__sm_chunk_is_rle(chunk)) {
    length = __sm_chunk_rle_get_length(chunk);
  } else {
    size_t count = 0;
    int j = SM_FLAGS_PER_INDEX, k = SM_BITS_PER_VECTOR;
    __sm_bitvec_t w = chunk->m_data[0], v = chunk->m_data[1];

    switch (w) {
    case 0:
      return 0;
    case ~(__sm_bitvec_t)0:
      return SM_CHUNK_MAX_CAPACITY;
    default:
      while (j && (w & SM_PAYLOAD_ONES) == SM_PAYLOAD_ONES) {
        count++;
        w >>= 2;
        j--;
      }
      if (count) {
        count *= SM_BITS_PER_VECTOR;
        if ((w & SM_PAYLOAD_MIXED) == SM_PAYLOAD_MIXED) {
          w >>= 2;
          j--;
          while (k && ((v & 1) == 1)) {
            count++;
            v >>= 1;
            k--;
          }
          while (k && ((v & 1) == 0)) {
            v >>= 1;
            k--;
          }
          if (k) {
            return 0;
          }
        }
        while (j--) {
          switch (w & 0x3) {
          case SM_PAYLOAD_NONE:
          case SM_PAYLOAD_ZEROS:
            w >>= 2;
            break;
          default:
            return 0;
          }
        }
        __sm_assert(count < SM_CHUNK_MAX_CAPACITY);
        length = count;
      }
    }
  }
  return length;
}

struct __attribute__((aligned(8))) sparsemap {
  size_t m_capacity;  /* The total size of m_data */
  size_t m_data_used; /* The used size of m_data */
  uint8_t *m_data;    /* The serialized bitmap data */
};

/** @brief Calculates the additional vectors required based on \b b.
 *
 * This function uses a precomputed lookup table to efficiently determine the
 * number of vectors required based on the value of the input byte \b b.
 *
 * Each entry in the lookup table represents a possible combination of 4 2-bit
 * values (00, 01, 10, 11).  The value at each index corresponds to the count of
 * "10" patterns in that 4-bit combination.  For example, lookup[10] is 2
 * because the binary representation of 10 (0000 1010) contains the "01" pattern
 * twice.
 *
 * @param[in] b The input byte used for the calculation.
 * @return The calculated number of vectors.
 * @see bin/gen_chunk_vector_size_table.py
 */
static size_t
__sm_chunk_calc_vector_size(uint8_t b)
{
  // clang-format off
  static int lookup[] = {
    0,  0,  1,  0,  0,  0,  1,  0,  1,  1,  2,  1,  0,  0,  1,  0,
    0,  0,  1,  0,  0,  0,  1,  0,  1,  1,  2,  1,  0,  0,  1,  0,
    1,  1,  2,  1,  1,  1,  2,  1,  2,  2,  3,  2,  1,  1,  2,  1,
    0,  0,  1,  0,  0,  0,  1,  0,  1,  1,  2,  1,  0,  0,  1,  0,
    0,  0,  1,  0,  0,  0,  1,  0,  1,  1,  2,  1,  0,  0,  1,  0,
    0,  0,  1,  0,  0,  0,  1,  0,  1,  1,  2,  1,  0,  0,  1,  0,
    1,  1,  2,  1,  1,  1,  2,  1,  2,  2,  3,  2,  1,  1,  2,  1,
    0,  0,  1,  0,  0,  0,  1,  0,  1,  1,  2,  1,  0,  0,  1,  0,
    1,  1,  2,  1,  1,  1,  2,  1,  2,  2,  3,  2,  1,  1,  2,  1,
    1,  1,  2,  1,  1,  1,  2,  1,  2,  2,  3,  2,  1,  1,  2,  1,
    2,  2,  3,  2,  2,  2,  3,  2,  3,  3,  4,  3,  2,  2,  3,  2,
    1,  1,  2,  1,  1,  1,  2,  1,  2,  2,  3,  2,  1,  1,  2,  1,
    0,  0,  1,  0,  0,  0,  1,  0,  1,  1,  2,  1,  0,  0,  1,  0,
    0,  0,  1,  0,  0,  0,  1,  0,  1,  1,  2,  1,  0,  0,  1,  0,
    1,  1,  2,  1,  1,  1,  2,  1,  2,  2,  3,  2,  1,  1,  2,  1,
    0,  0,  1,  0,  0,  0,  1,  0,  1,  1,  2,  1,  0,  0,  1,  0
  };
  // clang-format on
  return (size_t)lookup[b];
}

/** @brief Calculates the offset into set set of vectors within a chunk for a
 * given index.
 *
 * This function determines the array index into m_data of the requested
 * position.  The code examines the flags within the descriptor and calculates
 * the index within the chunk's data.
 *
 * @param[in] chunk Pointer to the chunk.
 * @param[in] bv Index within the descriptor (0-based).
 * @return Array index of the vector within the chunk's data iff the descriptor
 * was SM_PAYLOAD_MIXED, otherwise meaningless.
 */
static size_t
__sm_chunk_get_position(__sm_chunk_t *chunk, size_t bv)
{
  /* Handle 4 indices (1 byte) at a time. */
  size_t num_bytes;
  size_t position = 0;
  register uint8_t *p = (uint8_t *)chunk->m_data;

  /* Handle RLE by examining the first byte. */
  if (!__sm_chunk_is_rle(chunk)) {
    num_bytes = bv / ((size_t)SM_FLAGS_PER_INDEX_BYTE * SM_BITS_PER_VECTOR);
    for (size_t i = 0; i < num_bytes; i++, p++) {
      position += __sm_chunk_calc_vector_size(*p);
    }

    bv -= num_bytes * SM_FLAGS_PER_INDEX_BYTE;
    for (size_t i = 0; i < bv; i++) {
      size_t flags = SM_CHUNK_GET_FLAGS(*chunk->m_data, i);
      if (flags == SM_PAYLOAD_MIXED) {
        position++;
      }
    }
  }

  return position;
}

/** @brief Initializes a chunk structure with raw data.
 *
 * This function casts the provided raw data pointer to a `__sm_bitvec_t`
 * pointer and stores it in the `m_data` member of the `__sm_chunk_t` structure.
 *
 * @param chunk Pointer to the chunk structure to initialize.
 * @param data Pointer to the raw data to be used by the chunk.
 */
static inline void
__sm_chunk_init(__sm_chunk_t *chunk, uint8_t *data)
{
  chunk->m_data = (__sm_bitvec_t *)data;
}

/** @brief Calculates the capacity of a chunk in bits.
 *
 * Determines the maximum number of bit available for storing data within the
 * chunk.  The capacity is typically `SM_CHUNK_MAX_CAPACITY` bits, but it can
 * be reduced if the chunk contains flags indicating an unused portion of the
 * chunk or larger than max capacity when this chunk represents RLE-encoded
 * data.
 *
 * @param[in] map The sparsemap that contains this chunk.
 * @param[in] chunk Pointer to the chunk to examine.
 * @param[in] start The starting offset of this chunk.
 * @return The maximum usable capacity of the chunk in bits.
 */
static size_t
__sm_chunk_get_capacity(__sm_chunk_t *chunk)
{
  /* Handle RLE which encodes the capacity in the vector. */
  if (__sm_chunk_is_rle(chunk)) {
    return __sm_chunk_rle_get_capacity(chunk);
  }

  size_t capacity = SM_CHUNK_MAX_CAPACITY;
  register uint8_t *p = (uint8_t *)chunk->m_data;

  for (size_t i = 0; i < sizeof(__sm_bitvec_t); i++, p++) {
    if (!*p || *p == 0xff) {
      continue;
    }
    for (int j = 0; j < SM_FLAGS_PER_INDEX_BYTE; j++) {
      size_t flags = SM_CHUNK_GET_FLAGS(*p, j);
      if (flags == SM_PAYLOAD_NONE) {
        capacity -= SM_BITS_PER_VECTOR;
      }
    }
  }
  return capacity;
}

static void
__sm_chunk_increase_capacity(__sm_chunk_t *chunk, size_t capacity)
{
  __sm_assert(capacity % SM_BITS_PER_VECTOR == 0);
  __sm_assert(capacity <= SM_CHUNK_MAX_CAPACITY);
  __sm_assert(capacity > __sm_chunk_get_capacity(chunk));

  size_t initial_capacity = __sm_chunk_get_capacity(chunk);
  if (capacity <= initial_capacity || capacity > SM_CHUNK_MAX_CAPACITY) {
    return;
  }

  size_t increased = 0;
  register uint8_t *p = (uint8_t *)chunk->m_data;
  for (size_t i = 0; i < sizeof(__sm_bitvec_t); i++, p++) {
    if (!*p || *p == 0xff) {
      continue;
    }
    for (int j = 0; j < SM_FLAGS_PER_INDEX_BYTE; j++) {
      size_t flags = SM_CHUNK_GET_FLAGS(*p, j);
      if (flags == SM_PAYLOAD_NONE) {
        *p &= ~((__sm_bitvec_t)SM_PAYLOAD_ONES << (j * 2));
        *p |= ((__sm_bitvec_t)SM_PAYLOAD_ZEROS << (j * 2));
        increased += SM_BITS_PER_VECTOR;
        if (increased + initial_capacity == capacity) {
          __sm_assert(__sm_chunk_get_capacity(chunk) == capacity);
          return;
        }
      }
    }
  }
  __sm_assert(__sm_chunk_get_capacity(chunk) == capacity);
}

/** @brief Examines the chunk to determine if it is empty.
 *
 * @param[in] chunk The chunk in question.
 * @returns true if this __sm_chunk_t is empty
 */
static bool
__sm_chunk_is_empty(__sm_chunk_t *chunk)
{
  if (chunk->m_data[0] != 0) {
    /* A chunk is considered empty if all flags are SM_PAYLOAD_ZERO or _NONE. */
    register uint8_t *p = (uint8_t *)chunk->m_data;
    for (size_t i = 0; i < sizeof(__sm_bitvec_t); i++, p++) {
      if (*p) {
        for (int j = 0; j < SM_FLAGS_PER_INDEX_BYTE; j++) {
          size_t flags = SM_CHUNK_GET_FLAGS(*p, j);
          if (flags != SM_PAYLOAD_NONE && flags != SM_PAYLOAD_ZEROS) {
            return false;
          }
        }
      }
    }
  }
  /* The __sm_chunk_t is empty if all flags (in m_data[0]) are zero. */
  return true;
}

/** @brief Examines the chunk to determine its size.
 *
 * @param[in] chunk The chunk in question.
 * @returns the size of the data buffer, in bytes.
 */
static size_t
__sm_chunk_get_size(__sm_chunk_t *chunk)
{
  /* At least one __sm_bitvec_t is required for the flags (m_data[0]) */
  size_t size = sizeof(__sm_bitvec_t);
  if (!__sm_chunk_is_rle(chunk)) {
    /* Use a lookup table for each byte of the flags */
    register uint8_t *p = (uint8_t *)chunk->m_data;
    for (size_t i = 0; i < sizeof(__sm_bitvec_t); i++, p++) {
      size += sizeof(__sm_bitvec_t) * __sm_chunk_calc_vector_size(*p);
    }
  }
  return size;
}

/** @brief Examines the chunk at \b idx to determine that bit's state (set,
 * or unset).
 *
 * @param[in] chunk The chunk in question.
 * @param[in] idx The 0-based index into this chunk to examine.
 * @returns the value of a bit at index \b idx
 */
static bool
__sm_chunk_is_set(__sm_chunk_t *chunk, size_t idx)
{
  if (__sm_chunk_is_rle(chunk)) {
    if (idx <= __sm_chunk_rle_get_length(chunk)) {
      return true;
    }
    return false;
  } else {
    /* in which __sm_bitvec_t is |idx| stored? */
    size_t bv = idx / SM_BITS_PER_VECTOR;
    __sm_assert(bv < SM_FLAGS_PER_INDEX);

    /* now retrieve the flags of that __sm_bitvec_t */
    size_t flags = SM_CHUNK_GET_FLAGS(*chunk->m_data, bv);
    switch (flags) {
    case SM_PAYLOAD_ZEROS:
    case SM_PAYLOAD_NONE:
      return false;
    case SM_PAYLOAD_ONES:
      return true;
    default:
      __sm_assert(flags == SM_PAYLOAD_MIXED);
      /* FALLTHROUGH */
    }

    /* get the __sm_bitvec_t at |bv| */
    __sm_bitvec_t w = chunk->m_data[1 + __sm_chunk_get_position(chunk, bv)];
    /* and finally check the bit in that __sm_bitvec_t */
    return (w & ((__sm_bitvec_t)1 << (idx % SM_BITS_PER_VECTOR))) > 0;
  }
}

/** @brief Clears bit at the chunk-relative idx.
 *
 * @param[in] chunk The chunk in question.
 * @param[in] idx The chunk-relative 0-based index to clear.
 * @param[in,out] pos When non-zero there is a vector available for MIXED
 * mutations, no need to "grow".  When zero then set to the position in the
 * buffer where there needs to be a new vector to grow into.
 * @return SM_OK, GROW, or SHRINK; grow indicates the need for an additional
 * vector (transitioning from ZEROS or ONES to MIXED), shrink that the
 * additional mixed vector isn't needed anymore (transitioning from MIXED to
 * ZEROS or ONES).
 */
static int
__sm_chunk_clr_bit(__sm_chunk_t *chunk, sparsemap_idx_t idx, size_t *pos)
{
  __sm_bitvec_t w;
  size_t bv = idx / SM_BITS_PER_VECTOR;

  __sm_assert(bv < SM_FLAGS_PER_INDEX);

  switch (SM_CHUNK_GET_FLAGS(*chunk->m_data, bv)) {
  case SM_PAYLOAD_ZEROS:
    /* The bit is already clear, no-op. */
    *pos = 0;
    return SM_OK;
    break;
  case SM_PAYLOAD_ONES:
    /* What was all ones transitions to mixed, which requires another vector. */
    if (*pos == 0) {
      *pos = (size_t)1 + __sm_chunk_get_position(chunk, bv);
      return SM_NEEDS_TO_GROW;
    }
    SM_CHUNK_SET_FLAGS(*chunk->m_data, bv, SM_PAYLOAD_MIXED);
    w = chunk->m_data[*pos];
    w &= ~((__sm_bitvec_t)1 << (idx % SM_BITS_PER_VECTOR));
    /* Update the mixed vector. */
    chunk->m_data[*pos] = w;
    return SM_OK;
    break;
  case SM_PAYLOAD_MIXED:
    *pos = 1 + __sm_chunk_get_position(chunk, bv);
    w = chunk->m_data[*pos];
    w &= ~((__sm_bitvec_t)1 << (idx % SM_BITS_PER_VECTOR));
    /* Did the vector transition from mixed to all zeros? If so, remove it. */
    if (w == 0) {
      SM_CHUNK_SET_FLAGS(*chunk->m_data, bv, SM_PAYLOAD_ZEROS);
      return SM_NEEDS_TO_SHRINK;
    }
    /* Update the mixed vector. */
    chunk->m_data[*pos] = w;
    break;
  case SM_PAYLOAD_NONE:
    /* FALLTHROUGH */
  default:
    __sm_assert(!"shouldn't be here");
#ifdef DEBUG
    abort();
#endif
    break;
  }
  return SM_OK;
}

/** @brief Sets a bit at the chunk-relative idx.
 *
 * @param[in] chunk The chunk in question.
 * @param[in] idx The chunk-relative 0-based index to set.
 * @param[in,out] pos When non-zero there is a vector available for MIXED
 * mutations, no need to "grow".  When zero then set to the position in the
 * buffer where there needs to be a new vector to grow into.
 * @return SM_OK, GROW, or SHRINK; grow indicates the need for an additional
 * vector (transitioning from ZEROS or ONES to MIXED), shrink that the
 * additional mixed vector isn't needed anymore (transitioning from MIXED to
 * ZEROS or ONES).
 */
static int
__sm_chunk_set_bit(__sm_chunk_t *chunk, sparsemap_idx_t idx, size_t *pos)
{
  /* Where in the descriptor does this idx fall, which flag should we examine? */
  size_t bv = idx / SM_BITS_PER_VECTOR;
  __sm_assert(bv < SM_FLAGS_PER_INDEX);
  __sm_assert(__sm_chunk_is_rle(chunk) == false);

  switch (SM_CHUNK_GET_FLAGS(*chunk->m_data, bv)) {
  case SM_PAYLOAD_ONES:
    /* The bit is already set, no-op. */
    *pos = 0;
    return SM_OK;
    break;
  case SM_PAYLOAD_ZEROS:
    /* What was all zeros transitions to mixed, which requires another vector. */
    if (*pos == 0) {
      *pos = (size_t)1 + __sm_chunk_get_position(chunk, bv);
      return SM_NEEDS_TO_GROW;
    }
    SM_CHUNK_SET_FLAGS(*chunk->m_data, bv, SM_PAYLOAD_MIXED);
    /* FALLTHROUGH */
  case SM_PAYLOAD_MIXED:
    *pos = 1 + __sm_chunk_get_position(chunk, bv);
    __sm_bitvec_t w = chunk->m_data[*pos];
    w |= (__sm_bitvec_t)1 << (idx % SM_BITS_PER_VECTOR);
    /* Did the vector transition from mixed to all ones? If so, remove it. */
    if (w == ~(__sm_bitvec_t)0) {
      SM_CHUNK_SET_FLAGS(*chunk->m_data, bv, SM_PAYLOAD_ONES);
      return SM_NEEDS_TO_SHRINK;
    }
    /* Update the mixed vector. */
    chunk->m_data[*pos] = w;
    break;
  case SM_PAYLOAD_NONE:
    /* FALLTHROUGH */
  default:
    // __sm_when_diag({ fprintf(stdout, "\n%s\n", _qcc_format_chunk(0, chunk, true)); })
#ifdef DEBUG
    abort();
#endif
    break;
  }
  return SM_OK;
}

/** @brief Finds the index of the \b n'th bit after \b offset bits with \b
 * value.
 *
 * Scans the \b chunk until after \b offset bits (of any value) have
 * passed and then begins counting the bits that match \b value looking
 * for the \b n'th bit.  It may not be in this chunk, when it is offset is set.
 *
 * @param[in] chunk The chunk in question.
 * @param[in] value Informs what we're seeking, a set or unset bit's position.
 * @param offset[in,out] Sets \b offset to n if the n'th bit was found
 * in this __sm_chunk_t, or reduced value of \b n bits observed the search up
 * to a maximum of SM_BITS_PER_VECTOR.
 * @returns the 0-based index of the n'th set bit when found, otherwise
 * SM_BITS_PER_VECTOR
 */
static size_t
__sm_chunk_select(__sm_chunk_t *chunk, ssize_t n, ssize_t *offset, bool value)
{
  size_t ret = 0;
  register uint8_t *p;

  p = (uint8_t *)chunk->m_data;
  for (size_t i = 0; i < sizeof(__sm_bitvec_t); i++, p++) {
    if (*p == 0 && value) {
      ret += (size_t)SM_FLAGS_PER_INDEX_BYTE * SM_BITS_PER_VECTOR;
      continue;
    }

    for (int j = 0; j < SM_FLAGS_PER_INDEX_BYTE; j++) {
      size_t flags = SM_CHUNK_GET_FLAGS(*p, j);
      if (flags == SM_PAYLOAD_NONE) {
        continue;
      }
      if (flags == SM_PAYLOAD_ZEROS) {
        if (value == true) {
          ret += SM_BITS_PER_VECTOR;
          continue;
        } else {
          if (n > SM_BITS_PER_VECTOR) {
            n -= SM_BITS_PER_VECTOR;
            ret += SM_BITS_PER_VECTOR;
            continue;
          }
          *offset = -1;
          return ret + n;
        }
      }
      if (flags == SM_PAYLOAD_ONES) {
        if (value == true) {
          if (n > SM_BITS_PER_VECTOR) {
            n -= SM_BITS_PER_VECTOR;
            ret += SM_BITS_PER_VECTOR;
            continue;
          }
          *offset = -1;
          return ret + n;
        } else {
          ret += SM_BITS_PER_VECTOR;
          continue;
        }
      }
      if (flags == SM_PAYLOAD_MIXED) {
        __sm_bitvec_t w = chunk->m_data[1 + __sm_chunk_get_position(chunk, i * SM_FLAGS_PER_INDEX_BYTE + j)];
        for (int k = 0; k < SM_BITS_PER_VECTOR; k++) {
          if (value) {
            if (w & ((__sm_bitvec_t)1 << k)) {
              if (n == 0) {
                *offset = -1;
                return ret;
              }
              n--;
            }
            ret++;
          } else {
            if (!(w & ((__sm_bitvec_t)1 << k))) {
              if (n == 0) {
                *offset = -1;
                return ret;
              }
              n--;
            }
            ret++;
          }
        }
      }
    }
  }
  *offset = n;
  return ret;
}

/**
 * @brief Ranks bits within the range [from, to].
 *
 * Scans the \b chunk until after \b from bits (of any value) have passed and
 * then begins counting the bits that match \b value. The result should never be
 * greater than \b to + 1.  The range is inclusive and indexes are
 * 0-based. Calling this function with `from = 0` and `to = 0`, which is the
 * range [0, 0], will compare 1 bit at the position 0 against value. The range
 * [0, 9] will examine 10 bits, starting with the 0th and ending with the 9th and
 * return at most a count of 10.
 *
 * @param[out] rank Additional results, remaining bits and last position.
 * @param[in] state The state of bits, set or unset, to rank.
 * @param[in] chunk The chunk to examine.
 * @param[in] from The start of the range, 0-indexed and inclusive.
 * @param[in] to The end of the range, 0-indexed and inclusive.
 * @return the sum of the set bits in the range [from, to], 0 if none.
 */
static size_t
__sm_chunk_rank(__sm_chunk_rank_t *rank, bool state, __sm_chunk_t *chunk, size_t from, size_t to)
{
  size_t amt = 0;
  size_t cap = __sm_chunk_get_capacity(chunk);

  __sm_assert(to >= from);
  rank->rem = cap;
  rank->pos = 0;

  if (from >= cap) {
    rank->pos = cap;
    rank->rem = 0;
    return amt;
  }

  if (SM_IS_CHUNK_RLE(chunk)) {
    /* This is a run-length (RLE) encoded chunk. */
    size_t end = __sm_chunk_rle_get_length(chunk) - 1;
    rank->rem = 0;
    if (state) {
      if (from <= end) {
        amt = to - from + 1;
        rank->pos = to;
        if (to > end) {
          amt -= to - end;
        }
      } else {
        rank->pos = end;
      }
    } else {
      if (to < cap) {
        if (to > end) {
          amt = to - end - 1;
        }
        rank->pos = to + 1;
      } else {
        amt = (cap - (end + 1)) - 1;
        rank->pos = cap;
      }
    }
  } else {
    /* This chunk has sparse encoding. */

    uint8_t *vec = (uint8_t *)chunk->m_data;
    __sm_bitvec_t w, mw;
    uint64_t mask, to_mask, from_mask;
    size_t pc;

    for (size_t i = 0; i < sizeof(__sm_bitvec_t); i++, vec++) {
      for (int j = 0; j < SM_FLAGS_PER_INDEX_BYTE; j++) {
        size_t flags = SM_CHUNK_GET_FLAGS(*vec, j);

        switch (flags) {

        case SM_PAYLOAD_ZEROS:
          rank->rem = 0;
          if (to >= SM_BITS_PER_VECTOR) {
            rank->pos += SM_BITS_PER_VECTOR;
            to -= SM_BITS_PER_VECTOR;
            if (from >= SM_BITS_PER_VECTOR) {
              from = from - SM_BITS_PER_VECTOR;
            } else {
              if (!state) {
                amt += SM_BITS_PER_VECTOR - from;
              }
              from = 0;
            }
          } else {
            rank->pos += to + 1;
            if (!state) {
              if (from > to) {
                from -= to;
              } else {
                amt += to + 1 - from;
                from = 0;
                goto done;
              }
            } else {
              goto done;
            }
          }
          break;

        case SM_PAYLOAD_ONES:
          rank->rem = UINT64_MAX;
          if (to >= SM_BITS_PER_VECTOR) {
            rank->pos += SM_BITS_PER_VECTOR;
            to -= SM_BITS_PER_VECTOR;
            if (from >= SM_BITS_PER_VECTOR) {
              from = from - SM_BITS_PER_VECTOR;
            } else {
              if (state) {
                amt += SM_BITS_PER_VECTOR - from;
              }
              from = 0;
            }
          } else {
            rank->pos += to + 1;
            if (state) {
              if (from > to) {
                from = from - to;
              } else {
                amt += to + 1 - from;
                from = 0;
                goto done;
              }
            } else {
              goto done;
            }
          }
          break;

        case SM_PAYLOAD_MIXED:
          w = chunk->m_data[1 + __sm_chunk_get_position(chunk, i * SM_FLAGS_PER_INDEX_BYTE + j)];
          if (to >= SM_BITS_PER_VECTOR) {
            rank->pos += SM_BITS_PER_VECTOR;
            to -= SM_BITS_PER_VECTOR;
            mask = from == 0 ? UINT64_MAX : ~(UINT64_MAX >> (SM_BITS_PER_VECTOR - (from >= 64 ? 64 : from)));
            mw = (state ? w : ~w) & mask;
            pc = popcountll(mw);
            amt += pc;
            from = (from > SM_BITS_PER_VECTOR) ? from - SM_BITS_PER_VECTOR : 0;
          } else {
            rank->pos += to + 1;
            to_mask = (to == 63) ? UINT64_MAX : ((uint64_t)1 << (to + 1)) - 1;
            from_mask = from == 0 ? UINT64_MAX : ~(UINT64_MAX >> (SM_BITS_PER_VECTOR - (from >= 64 ? 64 : from)));
            /* Create a mask for the range [from, to] and use popcount. */
            mask = to_mask & from_mask;
            mw = (state ? w : ~w) & mask;
            pc = popcountll(mw);
            amt += pc;
            rank->rem = mw >> ((from > 63) ? 63 : from);
            from = from > to ? from - to + 1 : 0;
            goto done;
          }
          break;

        case SM_PAYLOAD_NONE:
        default:
          continue;
        }
      }
    }
  }
done:;
  return amt;
}

/** @brief Calls \b scanner with sm_bitmap_t for each vector in this chunk.
 *
 * Decompresses the whole chunk into separate bitmaps then calls visitor's
 * \b #operator() function for all bits that are set.
 *
 * @param[in] chunk The chunk in question.
 * @param[in] start Starting offset
 * @param[in] scanner Callback function which receives an array of indices (with
 * bits set to 1), the size of the array and an auxiliary pointer provided by
 * the caller.
 * @param[in] skip The number of bits to skip in the beginning.
 * @returns the number of (set) bits that were passed to the scanner
 */
static size_t
__sm_chunk_scan(__sm_chunk_t *chunk, __sm_idx_t start, void (*scanner)(uint32_t[], size_t, void *aux), size_t skip, void *aux)
{
  size_t ret = 0;
  register uint8_t *p = (uint8_t *)chunk->m_data;
  uint32_t buffer[SM_BITS_PER_VECTOR];
  for (size_t i = 0; i < sizeof(__sm_bitvec_t); i++, p++) {
    if (*p == 0) {
      /* Skip chunks that are all zeroes. */
      skip -= skip > SM_BITS_PER_VECTOR ? SM_BITS_PER_VECTOR : skip;
      continue;
    }

    for (int j = 0; j < SM_FLAGS_PER_INDEX_BYTE; j++) {
      size_t flags = SM_CHUNK_GET_FLAGS(*p, j);
      if (flags == SM_PAYLOAD_NONE || flags == SM_PAYLOAD_ZEROS) {
        /* Skip when all zeroes. */
        skip -= skip > SM_BITS_PER_VECTOR ? SM_BITS_PER_VECTOR : skip;
      } else if (flags == SM_PAYLOAD_ONES) {
        if (skip) {
          if (skip >= SM_BITS_PER_VECTOR) {
            skip -= SM_BITS_PER_VECTOR;
            ret += SM_BITS_PER_VECTOR;
            continue;
          }
          size_t n = 0;
          for (size_t b = 0; b < SM_BITS_PER_VECTOR; b++) {
            buffer[n++] = start + ret + b;
          }
          scanner(&buffer[0], n, aux);
          ret += n;
          skip = 0;
        } else {
          for (size_t b = 0; b < SM_BITS_PER_VECTOR; b++) {
            buffer[b] = start + ret + b;
          }
          scanner(&buffer[0], SM_BITS_PER_VECTOR, aux);
          ret += SM_BITS_PER_VECTOR;
        }
      } else if (flags == SM_PAYLOAD_MIXED) {
        __sm_bitvec_t w = chunk->m_data[1 + __sm_chunk_get_position(chunk, i * SM_FLAGS_PER_INDEX_BYTE + j)];
        size_t n = 0;
        if (skip) {
          if (skip >= SM_BITS_PER_VECTOR) {
            skip -= SM_BITS_PER_VECTOR;
            ret += SM_BITS_PER_VECTOR;
            continue;
          }
          for (int b = 0; b < SM_BITS_PER_VECTOR; b++) {
            if (skip > 0) {
              skip--;
              continue;
            }
            if (w & ((__sm_bitvec_t)1 << b)) {
              buffer[n++] = start + ret + b;
              ret++;
            }
          }
        } else {
          for (int b = 0; b < SM_BITS_PER_VECTOR; b++) {
            if (w & ((__sm_bitvec_t)1 << b)) {
              buffer[n++] = start + ret + b;
            }
          }
          ret += n;
        }
        __sm_assert(n > 0);
        scanner(&buffer[0], n, aux);
      }
    }
  }
  return ret;
}

/** @brief Provides the number of chunks currently in the map.
 *
 * @param[in] chunk  The sparsemap_t in question.
 * @returns the number of chunks in the sparsemap
 */
static size_t
__sm_get_chunk_count(sparsemap_t *map)
{
  return *(uint32_t *)&map->m_data[0];
}

/** @brief Encapsulates the method to find the starting address of a chunk's
 * data.
 *
 * @param[in] map The sparsemap_t in question.
 * @param[in] offset The offset in bytes for the desired chunk.
 * @returns the data for the specified \b offset
 */
static inline uint8_t *
__sm_get_chunk_data(sparsemap_t *map, size_t offset)
{
  return &map->m_data[SM_SIZEOF_OVERHEAD + offset];
}

/** @brief Either max capacity or limited by next chunk.
 *
 * Use this function to determine the available room (capacity) in bits between
 * the end of an RLE chunk and the beginning of the next chunk (if one exists).
 * This function will assume that \b offset is the location of an RLE chunk and
 * then using that probe for the start of the next chunk.
 *
 * @param[in] map The map containing the RLE chunk.
 * @param[in] start The starting index of the RLE chunk.
 * @param[in] offset The offset in m_data of the RLE chunk.
 * @return a value between [0, SM_CHUNK_RLE_MAX_CAPACITY] based on the
 * position/existence of the next chunk in the map.
 */
static size_t
__sm_chunk_rle_capacity_limit(sparsemap_t *map, __sm_idx_t start, size_t offset)
{
  size_t next_offset = offset + SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t);
  if (next_offset < map->m_data_used - (SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t))) {
    uint8_t *p = __sm_get_chunk_data(map, next_offset);
    __sm_idx_t next_start = *(__sm_idx_t *)p;
    return next_start - start;
  }
  return SM_CHUNK_RLE_MAX_CAPACITY;
}

/** @brief Encapsulates the method to find the address of the first unused byte
 * in \b m_data.
 *
 * @param[in] map The sparsemap_t in question.
 * @returns a pointer after the end of the used data
 */
static uint8_t *
__sm_get_chunk_end(sparsemap_t *map)
{
  uint8_t *p = __sm_get_chunk_data(map, 0);
  size_t count = __sm_get_chunk_count(map);
  for (size_t i = 0; i < count; i++) {
    p += SM_SIZEOF_OVERHEAD;
    __sm_chunk_t chunk;
    __sm_chunk_init(&chunk, p);
    p += __sm_chunk_get_size(&chunk);
  }
  return p;
}

/** @brief Aligns to SM_CHUNK_CAPACITY a given index \b idx.
 *
 * Due to integer division discarding the remainder, the final return value is
 * always rounded down to the nearest multiple of SM_CHUNK_MAX_CAPACITY.
 *
 * @param[in] idx The index to align.
 * @returns the aligned offset (aligned to __sm_chunk_t capacity)
 */
static __sm_idx_t
__sm_get_chunk_aligned_offset(size_t idx)
{
  const size_t capacity = SM_CHUNK_MAX_CAPACITY;
  return (idx / capacity) * capacity;
}

/** @brief Provides the byte size amount of \b m_data consumed.
 *
 * @param[in] map The sparsemap_t in question.
 * @returns the used size in the data buffer
 */
static size_t
__sm_get_size_impl(sparsemap_t *map)
{
  uint8_t *start = __sm_get_chunk_data(map, 0);
  uint8_t *p = start;

  size_t count = __sm_get_chunk_count(map);
  for (size_t i = 0; i < count; i++) {
    p += SM_SIZEOF_OVERHEAD;
    __sm_chunk_t chunk;
    __sm_chunk_init(&chunk, p);
    p += __sm_chunk_get_size(&chunk);
  }
  return SM_SIZEOF_OVERHEAD + p - start;
}

/** @brief Provides the byte offset of the chunk containing the bit at \b idx.
 *
 * Chunks live within the m_data buffer space, this function will find the
 * 0-based offset into that buffer of the chunk containing idx if one exists.
 * If the index falls outside of all chunks it returns the offset of the chunk
 * before the idx, if there are no chunks in the map it returns -1.
 *
 * @param[in] map A sparsemap_t.
 * @param[in] idx Seeking the offset of a chunk for this index.
 * @returns the offset of the chunk in m_data that contains idx, or -1 if there
 * are no chunks.
 */
static ssize_t
__sm_get_chunk_offset(sparsemap_t *map, sparsemap_idx_t idx)
{
  size_t count = __sm_get_chunk_count(map);

  if (count == 0) {
    return -1;
  }

  uint8_t *start = __sm_get_chunk_data(map, 0);
  uint8_t *p = start;

  for (size_t i = 0; i < count - 1; i++) {
    __sm_idx_t s = *(__sm_idx_t *)p;
    __sm_chunk_t chunk;
    __sm_chunk_init(&chunk, p + SM_SIZEOF_OVERHEAD);
    __sm_assert(s == __sm_get_chunk_aligned_offset(s));
    if (s >= idx || idx < s + __sm_chunk_get_capacity(&chunk)) {
      break;
    }
    p += SM_SIZEOF_OVERHEAD + __sm_chunk_get_size(&chunk);
  }

  return (ssize_t)(p - start);
}

/** @brief Sets the number of __sm_chunk_t's.
 *
 * @param[in] map The sparsemap_t in question.
 * @param[in] new_count The new number of chunks in the map.
 */
static void
__sm_set_chunk_count(sparsemap_t *map, size_t new_count)
{
  *(uint32_t *)&map->m_data[0] = (uint32_t)new_count;
}

/** @brief Appends raw data at the end of used portion of \b m_data.
 *
 * @param[in] map The sparsemap_t in question.
 * @param[in] buffer The bytes to copy into \b m_data.
 * @param[in] buffer_size The size of the byte array \b buffer to copy.
 */
static void
__sm_append_data(sparsemap_t *map, uint8_t *buffer, size_t buffer_size)
{
  __sm_assert(map->m_data_used + buffer_size <= map->m_capacity);

  memcpy(&map->m_data[map->m_data_used], buffer, buffer_size);
  map->m_data_used += buffer_size;
}

/** @brief Inserts data at \b offset in the middle of \b m_data.
 *
 * @param[in] map The sparsemap_t in question.
 * @param[in] offset The offset in bytes into \b m_data to place the buffer.
 * @param[in] buffer The bytes to copy into \b m_data.
 * @param[in] buffer_size The size of the byte array \b buffer to copy.
 */
void
__sm_insert_data(sparsemap_t *map, size_t offset, uint8_t *buffer, size_t buffer_size)
{
  __sm_assert(map->m_data_used + buffer_size <= map->m_capacity);

  uint8_t *p = __sm_get_chunk_data(map, offset);
  memmove(p + buffer_size, p, map->m_data_used - offset);
  memcpy(p, buffer, buffer_size);
  map->m_data_used += buffer_size;
}

/** @brief Removes data from \b m_data.
 *
 * @param[in] map The sparsemap_t in question.
 * @param[in] offset The offset in bytes into \b m_data at which to excise data.
 * @param[in] gap_size The size of the excision.
 */
static void
__sm_remove_data(sparsemap_t *map, size_t offset, size_t gap_size)
{
  __sm_assert(map->m_data_used >= gap_size);
  uint8_t *p = __sm_get_chunk_data(map, offset);
  memmove(p, p + gap_size, map->m_data_used - offset - gap_size);
  map->m_data_used -= gap_size;
}

/** @brief Coalesces chunks adjacent when they form or extend a run.
 *
 * This is called from __sm_chunk_set/unset/merge/split functions when a
 * there is a chance that chunks should combine into runs so as to use less
 * space in the map.
 *
 * The provided chunk may have two adjacent chunks, this function first
 * processes the chunk to the left and then the one to the right.
 *
 * In the case that there is a chunk to the left (with a lower starting index)
 * we examine it's type and ending offset as well as it's run length.  Either
 * type of chunk (sparse and RLE) can have a run.  In the case of an RLE chunk
 * that's all it can express.  With a sparse chunk a run is defined as adjacent
 * set bits starting at the 0th index of the chunk and extending up to at most
 * the maximum size of a chunk without gaps ([1..SM_CHUNK_MAX_CAPACITY] in
 * length).  When the left chunk's run ends at the starting index of this chunk
 * we can combine them. Combining these two will always result in a RLE chunk.
 *
 * Once that is finished... we may have something to the right as well.  We look
 * for an adjacent chunk, then determine if it has a run with a starting point
 * adjacent to the end of a run in this chunk.  At this point we may have
 * mutated and coalesced the left into the center chunk which we further mutate
 * and combine with the right.  At most we can combine three chunks into one in
 * these two phases.
 *
 * @returns the number of chunks to be removed from the map
 */
static int
__sm_coalesce_chunk(sparsemap_t *map, __sm_chunk_t *chunk, size_t offset, __sm_idx_t start, uint8_t *p)
{
  size_t num_removed = 0, run_length = __sm_chunk_get_run_length(chunk);
  /* Did this chunk become all ones, can we compact it with adjacent chunks? */
  if (run_length > 0) {
    __sm_chunk_t adj;

    /* Is there a previous chunk? */
    if (offset > 0) {
      size_t adj_offset = (size_t)__sm_get_chunk_offset(map, start - 1);
      if (adj_offset < offset) {
        uint8_t *adj_p = __sm_get_chunk_data(map, adj_offset);
        __sm_idx_t adj_start = *(__sm_idx_t *)adj_p;
        __sm_chunk_init(&adj, adj_p + SM_SIZEOF_OVERHEAD);
        /* Is the adjacent chunk on the left RLE or a sparse chunk of all ones? */
        if (__sm_chunk_is_rle(&adj) || adj.m_data[0] == ~(__sm_bitvec_t)0) {
          /* Does it align with this full sparse chunk? */
          size_t adj_length = __sm_chunk_get_run_length(&adj);
          if (adj_start + adj_length == start) {
            if (SM_CHUNK_MAX_CAPACITY + run_length < SM_CHUNK_RLE_MAX_LENGTH) {
              /* The stars have aligned, transform to RLE and combine them! */
              // __sm_when_diag({ fprintf(stdout, "\n%s\n", QCC_showChunk(adj_p, 0)); });
              // __sm_when_diag({ fprintf(stdout, "\n%s\n", QCC_showChunk(p, 0)); });
              __sm_chunk_set_rle(&adj);
              __sm_chunk_rle_set_length(&adj, adj_length + run_length);
              __sm_remove_data(map, offset, SM_SIZEOF_OVERHEAD + __sm_chunk_get_size(chunk));
              __sm_chunk_rle_set_capacity(&adj, __sm_chunk_rle_capacity_limit(map, adj_start, adj_offset));
              __sm_set_chunk_count(map, __sm_get_chunk_count(map) - 1);
              // __sm_when_diag({ fprintf(stdout, "\n%s\n", QCC_showChunk(adj_p, 0)); });

              /* Now chunk is shifted to the left, it becomes the adjacent chunk. */
              p = adj_p;
              offset = adj_offset;
              start = adj_start;
              __sm_chunk_init(chunk, p + SM_SIZEOF_OVERHEAD);
              num_removed += 1;
            }
          }
        }
      }
    }

    /* Is there a next chunk? */
    if (__sm_chunk_is_rle(chunk) || chunk->m_data[0] == ~(__sm_bitvec_t)0) {
      size_t adj_offset = offset + SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t);
      if (adj_offset < map->m_data_used - (SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t))) {
        uint8_t *adj_p = __sm_get_chunk_data(map, adj_offset);
        __sm_idx_t adj_start = *(__sm_idx_t *)adj_p;
        __sm_chunk_init(&adj, adj_p + SM_SIZEOF_OVERHEAD);
        /* Is the adjacent right chunk RLE or a sparse with a run of ones? */
        size_t adj_length = __sm_chunk_get_run_length(&adj);
        if (adj_length) {
          /* Does it align with this full sparse chunk? */
          size_t length = __sm_chunk_get_run_length(chunk);
          if (start + length == adj_start) {
            if (adj_length + length < SM_CHUNK_RLE_MAX_LENGTH) {
              /* The stars have aligned, transform to RLE and combine them! */
              // __sm_when_diag({ fprintf(stdout, "\n%s\n", QCC_showChunk(p, 0)); });
              // __sm_when_diag({ fprintf(stdout, "\n%s\n", QCC_showChunk(adj_p, 0)); });
              __sm_chunk_rle_set_length(chunk, length + adj_length);
              __sm_remove_data(map, adj_offset, SM_SIZEOF_OVERHEAD + __sm_chunk_get_size(&adj));
              __sm_chunk_set_rle(chunk);
              __sm_chunk_rle_set_capacity(chunk, __sm_chunk_rle_capacity_limit(map, start, offset));
              __sm_set_chunk_count(map, __sm_get_chunk_count(map) - 1);
              // __sm_when_diag({ fprintf(stdout, "\n%s\n", QCC_showChunk(p, 0)); });
              num_removed += 1;
            }
          }
        }
      }
    }
  }

  return num_removed;
}

/**
 * TODO
 *
 * @returns the number of chunks to be removed from the map
 */
size_t
__sm_coalesce_map(sparsemap_t *map)
{
  __sm_chunk_t chunk;
  size_t n = 0, offset = 0, count = __sm_get_chunk_count(map);
  uint8_t *p = __sm_get_chunk_data(map, offset);
  __sm_idx_t start;

  while (count > 1) {
    start = *(__sm_idx_t *)p;
    __sm_chunk_init(&chunk, p + SM_SIZEOF_OVERHEAD);
    size_t amt = __sm_coalesce_chunk(map, &chunk, offset, start, p);
    if (amt > 0) {
      n += amt;
      count = __sm_get_chunk_count(map);
    } else {
      p += SM_SIZEOF_OVERHEAD + __sm_chunk_get_size(&chunk);
      count--;
    }
  }

  return n;
}

/** @brief Separates an RLE chunk into new chunks when necessary.
 *
 * This is called from __sm_chunk_set/unset/merge/split functions when a
 * run-length encoded (RLE) chunk must be mutated into one or more new chunks.
 *
 * This function expects that the separation information is complete and that
 * the pivot chunk has yet to be created.  The target will always be RLE and the
 * piviot will always be a new sparse chunk.  The hard part is where the pivot
 * lies in relation to the target.
 *
 * - left aligned
 * - right aligned
 * - centrally aligned
 *
 * When left aligned the chunk-aligned starting index of the pivot matches the
 * starting index of the target. This results in two chunks, one new (the pivot)
 * on the left, and one shortened RLE on the right.
 *
 * When right aligned there are two cases, the second more common one is when
 * the chunk-aligned starting index of the pivot plus its length extends beyond
 * the end of the run length of the target RLE chunk but is still within the
 * capacity of the RLE chunk. This again results in two chunks, one on the left
 * for the remainder of the run and one to the right.  In rare cases the end of
 * the pivot chunk perfectly aligns with the end of the target's length.
 *
 * The last case is when the chunk-aligned starting index is somewhere within
 * the body of the target.  This results in three chunks; left, right, and pivot
 * (or center).
 *
 * In all three cases the new chunks (left and right) may be either RLE or
 * sparse encoded, that's TBD based on their sizes after the pivot area is
 * removed from the body of the run.
 *
 * @param map[in] The sparsemap containing this chunk.
 * @param sep[in,out] An struct with information necessary for this operation.
 * @param idx[in] The map-relative 0-based index of the bit to be mutated.
 * @param state[in] The ending state of idx; set/1, unset/0, or unmodified/-1.
 * @return non-zero on failure, and errno to ENOSPC when the map can't fit the mutations
 */
static int
__sm_separate_rle_chunk(sparsemap_t *map, __sm_chunk_sep_t *sep, sparsemap_idx_t idx, int state)
{
  __sm_chunk_t pivot_chunk;
  size_t aligned_idx;
  __sm_chunk_t lrc;

  __sm_assert(state == 0 || state == 1 || state == -1);
  __sm_assert(SM_IS_CHUNK_RLE(sep->target.chunk));
  if (state == 1) {
    /* setting a bit */
    __sm_assert(idx < sep->target.capacity);
    __sm_assert(idx > sep->target.length + sep->target.start);
  } else if (state == 0) {
    /* clearing a bit */
    __sm_assert(idx >= sep->target.start);
    __sm_assert(idx < sep->target.length + sep->target.start);
  } else if (state == -1) {
    /* If `state == -1` we are splitting at idx but leaving map unmodified. */
  }

  memset(sep->buf, 0, (SM_SIZEOF_OVERHEAD * 3) + (sizeof(__sm_bitvec_t) * 6));

  /* Find the starting offset for our pivot chunk ... */
  aligned_idx = __sm_get_chunk_aligned_offset(idx);
  __sm_assert(idx >= aligned_idx && idx < (aligned_idx + SM_CHUNK_MAX_CAPACITY));
  /* avoid changing the map->m_data and for now work in our buf ... */
  sep->pivot.p = sep->buf;
  *(__sm_idx_t *)sep->pivot.p = aligned_idx;
  __sm_chunk_init(&pivot_chunk, sep->pivot.p + SM_SIZEOF_OVERHEAD);

  /* The pivot, extracted from a run, starts off as all 1s. */
  pivot_chunk.m_data[0] = ~(__sm_bitvec_t)0;

  if (state == 0) {
    /* To unset, change the flag at the position of the idx to "mixed" ... */
    SM_CHUNK_SET_FLAGS(pivot_chunk.m_data[0], idx / SM_BITS_PER_VECTOR, SM_PAYLOAD_MIXED);
    /* and clear only the bit at that index in this chunk. */
    pivot_chunk.m_data[1] = ~(__sm_bitvec_t)0 & ~((__sm_bitvec_t)1 << (idx % SM_BITS_PER_VECTOR));
    sep->pivot.size = SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) * 2;
  } else if (state == 1) {
    if (idx >= sep->target.start && idx < sep->target.start + sep->target.length) {
      /* It's a no-op to set a bit in a range of bits already set. */
      return 0;
    }
    sep->pivot.size = SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) * 2;
  } else if (state == -1) {
    /* Unmodified */
    sep->pivot.size = SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t);
  }

  /* Where did the pivot chunk fall within the original chunk? */
  do {
    if (aligned_idx == sep->target.start) {
      /* The pivot is left aligned, there will be two chunks in total. */
      sep->count = 2;
      sep->ex[1].start = aligned_idx + SM_CHUNK_MAX_CAPACITY;
      sep->ex[1].end = aligned_idx + sep->target.length - 1;
      sep->ex[1].p = (uint8_t *)((uintptr_t)sep->buf + sep->pivot.size);
      __sm_assert(sep->ex[1].start <= sep->ex[1].end);
      __sm_assert(sep->ex[0].p == 0);
      break;
    }

    if (aligned_idx + SM_CHUNK_MAX_CAPACITY >= sep->target.start + sep->target.length) {
      /* The pivot is right aligned, there will be two chunks in total. */
      sep->count = 2;
      /* Does our pivot extends beyond the end of the run. */
      int amt_over = (int)((aligned_idx + SM_CHUNK_MAX_CAPACITY) - (sep->target.start + sep->target.length));
      if (amt_over > 0) {
        /* The index of the first 0 bit. */
        size_t first_zero = SM_CHUNK_MAX_CAPACITY - amt_over, bv = first_zero / SM_BITS_PER_VECTOR;
        /* Shorten the pivot chunk because it extends beyond the end of the run ... */
        if (amt_over > SM_BITS_PER_VECTOR) {
          pivot_chunk.m_data[0] &= ~(__sm_bitvec_t)0 >> ((amt_over / SM_BITS_PER_VECTOR) * 2);
        }
        if (amt_over % SM_BITS_PER_VECTOR) {
          /* Change only the flag at the position of the last index to "mixed" ... */
          SM_CHUNK_SET_FLAGS(pivot_chunk.m_data[0], bv, SM_PAYLOAD_MIXED);
          /* and unset the bits beyond that. */
          pivot_chunk.m_data[1] = ~(~(__sm_bitvec_t)0 << (first_zero % SM_BITS_PER_VECTOR));
          if (state == -1) {
            sep->pivot.size += sizeof(__sm_bitvec_t);
          }
        }
      }

      /* Are we setting a bit beyond the length where we partially overlap? */
      if (state == 1 && idx > sep->target.start + sep->target.length) {
        /* Change only the flag at the position of the index to "mixed" ... */
        SM_CHUNK_SET_FLAGS(pivot_chunk.m_data[0], idx / SM_BITS_PER_VECTOR, SM_PAYLOAD_MIXED);
        /* and set the bit at that index in this chunk. */
        pivot_chunk.m_data[1] |= (__sm_bitvec_t)1 << (idx % SM_BITS_PER_VECTOR);
      }

      /* Move the pivot chunk over to make room for the new left chunk. */
      memmove((uint8_t *)((uintptr_t)sep->buf + SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) * 2), sep->buf, sep->pivot.size);
      memset(sep->buf, 0, SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) * 2);
      sep->pivot.p += SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) * 2;
      /* Record information necessary to construct the left chunk. */
      sep->ex[0].start = sep->target.start;
      sep->ex[0].end = aligned_idx - 1;
      sep->ex[0].p = sep->buf;
      __sm_assert(sep->ex[0].start <= sep->ex[0].end);
      __sm_assert(sep->ex[1].p == 0);
      break;
    }

    if (aligned_idx >= sep->target.start + sep->target.length) {
      /* The pivot is beyond the run but within the capacity, two chunks. */
      sep->count = 2;
      /* Ensure the aligned chunk is fully in the range (length, capacity). */
      if (aligned_idx + SM_CHUNK_MAX_CAPACITY < sep->target.capacity) {
        pivot_chunk.m_data[0] = (__sm_bitvec_t)0;
        if (state == 1) {
          /* Change only the flag at the position of the index to "mixed" ... */
          SM_CHUNK_SET_FLAGS(pivot_chunk.m_data[0], idx / SM_BITS_PER_VECTOR, SM_PAYLOAD_MIXED);
          /* and set the bit at that index in this chunk. */
          pivot_chunk.m_data[1] |= (__sm_bitvec_t)1 << (idx % SM_BITS_PER_VECTOR);
        }
        /* Move the pivot chunk over to make room for the new left chunk. */
        memmove((uint8_t *)((uintptr_t)sep->buf + SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) * 2), sep->buf, sep->pivot.size);
        memset(sep->buf, 0, SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) * 2);
        sep->pivot.p += SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) * 2;
        /* Record information necessary to construct the left chunk. */
        sep->ex[0].start = sep->target.start;
        sep->ex[0].end = sep->target.start + sep->target.length - 1;
        sep->ex[0].p = sep->buf;
        break;
      } else {
        // TODO: we can't fit a pivot in this space, yikes! punt, for now...
        return 0;
      }
    }

    /* The pivot's range is central, there will be three chunks in total. */
    sep->count = 3;
    /* Move the pivot chunk over to make room for the new left chunk. */
    memmove((uint8_t *)((uintptr_t)sep->buf + SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) * 2), sep->buf, sep->pivot.size);
    memset(sep->buf, 0, SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) * 2);
    sep->pivot.p += SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) * 2;
    /* Record information necessary to construct the left & right chunks. */
    sep->ex[0].start = sep->target.start;
    sep->ex[0].end = aligned_idx - 1;
    sep->ex[0].p = sep->buf;
    sep->ex[1].start = aligned_idx + SM_CHUNK_MAX_CAPACITY;
    sep->ex[1].end = sep->target.length - 1;
    sep->ex[1].p = (uint8_t *)((uintptr_t)sep->buf + (SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) * 2) + sep->pivot.size);
    __sm_assert(sep->ex[0].start < sep->ex[0].end);
    __sm_assert(sep->ex[1].start < sep->ex[1].end);
  } while (0);

  for (int i = 0; i < 2; i++) {
    if (sep->ex[i].p) {
      /* First assign the starting offset ... */
      *(__sm_idx_t *)sep->ex[i].p = sep->ex[i].start;
      /* ... then, construct a chunk ... */
      __sm_chunk_init(&lrc, sep->ex[i].p + SM_SIZEOF_OVERHEAD);
      /* ... determine the type of chunk required ... */
      if (sep->ex[i].end - sep->ex[i].start + 1 > SM_CHUNK_MAX_CAPACITY) {
        /* ... we need a run-length encoding (RLE), chunk ... */
        __sm_chunk_set_rle(&lrc);
        /* ... now assign the length ... */
        __sm_chunk_rle_set_length(&lrc, sep->ex[i].end - sep->ex[i].start + 1);
        /* ... a few things differ left to right ... */
        if (i == 0) {
          /* ... left: extend capacity to the start of the pivot chunk ... */
          __sm_chunk_rle_set_capacity(&lrc, aligned_idx - sep->ex[i].start);
          /* ... and shift the pivot chunk and start of lr[1] left one vector ... */
          memmove((uint8_t *)((uintptr_t)sep->buf + SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t)), sep->pivot.p, sep->pivot.size);
          memset((uint8_t *)((uintptr_t)sep->buf + SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) + sep->pivot.size), 0, sizeof(__sm_bitvec_t));
          if (sep->ex[1].p) {
            sep->ex[1].p = (uint8_t *)((uintptr_t)sep->ex[1].p - sizeof(__sm_bitvec_t));
          }
        } else {
          /* ... right: extend capacity to max or the start of next chunk */
          size_t right_offset = sep->target.offset + SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t);
          __sm_chunk_rle_set_capacity(&lrc, __sm_chunk_rle_capacity_limit(map, aligned_idx, right_offset));
        }
        /* ... and record our chunk size. */
        sep->ex[i].size = SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t);
      } else {
        /* ... we need a new sparse chunk, how long should it be? ... */
        size_t lrl = sep->ex[i].end - sep->ex[i].start + 1;
        /* ... how many flags can we mark as all ones? ... */
        if (lrl > SM_BITS_PER_VECTOR) {
          lrc.m_data[0] = ~(__sm_bitvec_t)0 >> ((SM_FLAGS_PER_INDEX - (lrl / SM_BITS_PER_VECTOR)) * 2);
        }
        /* ... do we have a mixed flag to create and vector to assign? ... */
        if (lrl % SM_BITS_PER_VECTOR) {
          SM_CHUNK_SET_FLAGS(lrc.m_data[0], (aligned_idx + lrl) / SM_BITS_PER_VECTOR, SM_PAYLOAD_MIXED);
          lrc.m_data[1] |= ~(__sm_bitvec_t)0 >> (SM_BITS_PER_VECTOR - (lrl % SM_BITS_PER_VECTOR));
          /* ... record our chunk size ... */
          sep->ex[i].size = SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) * 2;
        } else {
          /* ... earlier size estimates were all pessimistic, adjust them ... */
          if (i == 0) {
            /* ... and shift the pivot chunk and start of lr[1] left one vector ... */
            memmove((uint8_t *)((uintptr_t)sep->buf + SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t)), sep->pivot.p, sep->pivot.size);
            memset((uint8_t *)((uintptr_t)sep->buf + SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) + sep->pivot.size), 0, sizeof(__sm_bitvec_t));
            if (sep->ex[1].p) {
              sep->ex[1].p = (uint8_t *)((uintptr_t)sep->ex[1].p - sizeof(__sm_bitvec_t));
            }
          }
          /* ... record our chunk size ... */
          sep->ex[i].size = SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t);
        }
      }
      // __sm_when_diag({ /* Sanity check the chunk */ // fprintf(stdout, "\n%s\n", QCC_showChunk(lr[i], 0)); });
    }
  }

  /* Determine if we have room for this construct. */
  sep->expand_by = sep->pivot.size + sep->ex[0].size + sep->ex[1].size - SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t);
  if (map->m_data_used + sep->expand_by > map->m_capacity) {
    errno = ENOSPC;
    return -1;
  }

  /* Let's knit this into place within the map. */
  __sm_insert_data(map, sep->target.offset + SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t), sep->buf + SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t), sep->expand_by);
  memcpy(sep->target.p, sep->buf, sep->expand_by + SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t));
  __sm_set_chunk_count(map, __sm_get_chunk_count(map) + (sep->count - 1));

  return 0;
}

/** @brief Merges into the chunk at \b offset all set bits from \b src.
 *
 * @param[in] map The map the chunk belongs too.
 * @param[in] offset The offset of the first bit in the chunk to be merged.
 * @todo merge at the vector level not offset
 */
void
__sm_merge_chunk(sparsemap_t *map, sparsemap_idx_t src_start, sparsemap_idx_t dst_start, sparsemap_idx_t capacity, __sm_chunk_t *dst_chunk,
  __sm_chunk_t *src_chunk)
{
  __sm_bitvec_t fill = 0;
  ssize_t delta = src_start - dst_start;
  for (sparsemap_idx_t j = 0; j < capacity; j++) {
    ssize_t offset = __sm_get_chunk_offset(map, src_start + j);
    if (__sm_chunk_is_set(src_chunk, j) && !__sm_chunk_is_set(dst_chunk, j + delta)) {
      size_t position = 0;
      switch (__sm_chunk_set_bit(dst_chunk, j + delta, &position)) {
      case SM_NEEDS_TO_GROW:
        offset += SM_SIZEOF_OVERHEAD + position * sizeof(__sm_bitvec_t);
        __sm_insert_data(map, offset, (uint8_t *)&fill, sizeof(__sm_bitvec_t));
        __sm_chunk_set_bit(dst_chunk, j + delta, &position);
        break;
      case SM_NEEDS_TO_SHRINK:
        if (__sm_chunk_is_empty(src_chunk)) {
          __sm_assert(position == 1);
          __sm_remove_data(map, offset, SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) * 2);
          __sm_set_chunk_count(map, __sm_get_chunk_count(map) - 1);
        } else {
          offset += SM_SIZEOF_OVERHEAD + position * sizeof(__sm_bitvec_t);
          __sm_remove_data(map, offset, sizeof(__sm_bitvec_t));
        }
        break;
      case SM_OK:
      default:
        break;
      }
    }
  }
}

void
sparsemap_clear(sparsemap_t *map)
{
  if (map == NULL) {
    return;
  }
  memset(map->m_data, 0, map->m_capacity);
  map->m_data_used = SM_SIZEOF_OVERHEAD;
  __sm_set_chunk_count(map, 0);
}

sparsemap_t *
sparsemap(size_t size)
{
  if (size == 0) {
    size = 1024;
  }

  size_t data_size = (size * sizeof(uint8_t));

  /* Ensure that m_data is 8-byte aligned. */
  size_t total_size = sizeof(sparsemap_t) + data_size;
  size_t padding = total_size % 8 == 0 ? 0 : 8 - (total_size % 8);
  total_size += padding;

  sparsemap_t *map = (sparsemap_t *)calloc(1, total_size);
  if (map) {
    uint8_t *data = (uint8_t *)(((uintptr_t)map + sizeof(sparsemap_t)) & ~(uintptr_t)7);
    sparsemap_init(map, data, size);
    __sm_when_diag({ __sm_assert(IS_8_BYTE_ALIGNED(map->m_data)); });
  }
  return map;
}

sparsemap_t *
sparsemap_copy(sparsemap_t *other)
{
  size_t cap = sparsemap_get_capacity(other);
  sparsemap_t *map = sparsemap(cap);
  if (map) {
    map->m_capacity = other->m_capacity;
    map->m_data_used = other->m_data_used;
    memcpy(map->m_data, other->m_data, cap);
  }
  return map;
}

sparsemap_t *
sparsemap_wrap(uint8_t *data, size_t size)
{
  sparsemap_t *map = (sparsemap_t *)calloc(1, sizeof(sparsemap_t));
  if (map) {
    map->m_data = data;
    map->m_data_used = 0;
    map->m_capacity = size;
  }
  return map;
}

void
sparsemap_init(sparsemap_t *map, uint8_t *data, size_t size)
{
  map->m_data = data;
  map->m_data_used = 0;
  map->m_capacity = size;
  sparsemap_clear(map);
}

void
sparsemap_open(sparsemap_t *map, uint8_t *data, size_t size)
{
  map->m_data = data;
  map->m_data_used = __sm_get_size_impl(map);
  map->m_capacity = size;
}

sparsemap_t *
sparsemap_set_data_size(sparsemap_t *map, uint8_t *data, size_t size)
{
  size_t data_size = (size * sizeof(uint8_t));

  /*
   * If this sparsemap was allocated by the sparsemap() API and we're not handed
   * a new data, it's up to us to resize it.
   */
  if (data == NULL && (uintptr_t)map->m_data == (uintptr_t)map + sizeof(sparsemap_t) && size > map->m_capacity) {

    /* Ensure that m_data is 8-byte aligned. */
    size_t total_size = sizeof(sparsemap_t) + data_size;
    size_t padding = total_size % 8 == 0 ? 0 : 8 - (total_size % 8);
    total_size += padding;

    sparsemap_t *m = (sparsemap_t *)realloc(map, total_size);
    if (!m) {
      return NULL;
    }
    memset(((uint8_t *)m) + sizeof(sparsemap_t) + (m->m_capacity * sizeof(uint8_t)), 0, size - m->m_capacity + padding);
    m->m_capacity = data_size;
    m->m_data = (uint8_t *)(((uintptr_t)m + sizeof(sparsemap_t)) & ~(uintptr_t)7);
    __sm_when_diag({ __sm_assert(IS_8_BYTE_ALIGNED(m->m_data)); }) return m;
  } else {
    /*
     * NOTE: It is up to the caller to realloc their buffer and provide it here
     * for reassignment.
     */
    if (data != NULL && data != map->m_data) {
      map->m_data = data;
    }
    map->m_capacity = size;
    return map;
  }
}

double
sparsemap_capacity_remaining(sparsemap_t *map)
{
  if (map->m_data_used >= map->m_capacity) {
    return 0;
  }
  if (map->m_capacity == 0) {
    return 100.0;
  }
  return 100 - (((double)map->m_data_used / (double)map->m_capacity) * 100);
}

size_t
sparsemap_get_capacity(sparsemap_t *map)
{
  return map->m_capacity;
}

bool
sparsemap_is_set(sparsemap_t *map, sparsemap_idx_t idx)
{
  __sm_assert(sparsemap_get_size(map) >= SM_SIZEOF_OVERHEAD);

  /* Get the __sm_chunk_t which manages this index */
  ssize_t offset = __sm_get_chunk_offset(map, idx);

  /* No __sm_chunk_t's available -> the bit is not set */
  if (offset == -1) {
    return false;
  }

  /* Otherwise load the __sm_chunk_t */
  uint8_t *p = __sm_get_chunk_data(map, offset);
  __sm_idx_t start = *(__sm_idx_t *)p;
  __sm_chunk_t chunk;
  __sm_chunk_init(&chunk, p + SM_SIZEOF_OVERHEAD);

  /*
   * Determine if the bit is out of bounds of the __sm_chunk_t; if yes then
   * the bit is not set.
   */
  if (idx < start || (__sm_idx_t)idx - start >= __sm_chunk_get_capacity(&chunk)) {
    return false;
  }

  /* Otherwise ask the __sm_chunk_t whether the bit is set. */
  return __sm_chunk_is_set(&chunk, idx - start);
}

sparsemap_idx_t
__sm_map_unset(sparsemap_t *map, sparsemap_idx_t idx, bool coalesce)
{
  sparsemap_idx_t ret_idx = idx;
  __sm_assert(sparsemap_get_size(map) >= SM_SIZEOF_OVERHEAD);

  /* Clearing a bit could require an additional vector, let's ensure we have that
   * space available in the buffer first, or ENOMEM now. */
  SM_ENOUGH_SPACE(SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t));

  /* Determine if there is a chunk that could contain this index. */
  size_t offset = (size_t)__sm_get_chunk_offset(map, idx);

  if ((ssize_t)offset == -1) {
    /* There are no chunks in the map, there is nothing to clear, this is a
     * no-op. */
    goto done;
  }

  /*
   * Try to locate a chunk for this idx.  We could find that:
   * - the first chunk's offset is greater than the index, or
   * - the index is beyond the end of the last chunk, or
   * - we found a chunk that can contain this index.
   */
  uint8_t *p = __sm_get_chunk_data(map, offset);
  __sm_idx_t start = *(__sm_idx_t *)p;
  __sm_assert(start == __sm_get_chunk_aligned_offset(start));

  if (idx < start) {
    /* Our search resulted in the first chunk that starts after the index but
     * that means there is no chunk that contains this index, so again this is
     * a no-op. */
    goto done;
  }

  __sm_chunk_t chunk;
  __sm_chunk_init(&chunk, p + SM_SIZEOF_OVERHEAD);
  size_t capacity = __sm_chunk_get_capacity(&chunk);

  if (idx - start >= capacity) {
    /*
     * Our search resulted in a chunk however it's capacity doesn't encompass
     * this index, so again a no-op.
     */
    goto done;
  }

  if (__sm_chunk_is_rle(&chunk)) {
    /*
     * Our search resulted in a chunk that is run-length encoded (RLE).  There
     * are three possibilities at this point: 1) the index is at the end of the
     * run, so we just shorten then length; 2) the index is between start and
     * end [start, end) so we have to split this chunk up; 3) the index is
     * beyond the length but within the capacity, then clearing it is a no-op.
     * If the chunk length shrinks to the max capacity of sparse encoding we
     * have to transition its encoding.
     */

    /* Is the 0-based index beyond the run length? */
    size_t length = __sm_chunk_rle_get_length(&chunk);
    if (idx >= start + length) {
      goto done;
    }

    /* Is the 0-based index referencing the last bit in the run? */
    if (idx - start + 1 == length) {
      /* Should the run-length chunk transition into a sparse chunk? */
      if (length - 1 == SM_CHUNK_MAX_CAPACITY) {
        chunk.m_data[0] = ~(__sm_bitvec_t)0;
      } else {
        __sm_chunk_rle_set_length(&chunk, length - 1);
      }
      goto done;
    }

    /*
     * Now that we've addressed (1) and (3) we have to work on (2) where the
     * index is within the body of this RLE chunk. Chunks must have an aligned
     * starting offset, so let's first find what we'll call the "pivot" chunk
     * wherein we'll find the index we need to clear. That chunk will be sparse.
     */
    __sm_chunk_sep_t sep = { .target = { .p = p, .offset = offset, .chunk = &chunk, .start = start, .length = length, .capacity = capacity } };
    SM_ENOUGH_SPACE(__sm_separate_rle_chunk(map, &sep, idx, 0));
    goto done;
  }

  size_t pos = 0;
  __sm_bitvec_t vec = ~(__sm_bitvec_t)0;
  switch (__sm_chunk_clr_bit(&chunk, idx - start, &pos)) {
  case SM_OK:
    break;
  case SM_NEEDS_TO_GROW:
    offset += (SM_SIZEOF_OVERHEAD + pos * sizeof(__sm_bitvec_t));
    __sm_insert_data(map, offset, (uint8_t *)&vec, sizeof(__sm_bitvec_t));
    __sm_chunk_clr_bit(&chunk, idx - start, &pos);
    break;
  case SM_NEEDS_TO_SHRINK:
    /* The vector is empty, perhaps the entire chunk is empty? */
    if (__sm_chunk_is_empty(&chunk)) {
      __sm_remove_data(map, offset, SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) * 2);
      __sm_set_chunk_count(map, __sm_get_chunk_count(map) - 1);
    } else {
      offset += (SM_SIZEOF_OVERHEAD + pos * sizeof(__sm_bitvec_t));
      __sm_remove_data(map, offset, sizeof(__sm_bitvec_t));
    }
    break;
  default:
    __sm_assert(!"shouldn't be here");
#ifdef DEBUG
    abort();
#endif
    break;
  }

done:;
  if (coalesce && offset != SPARSEMAP_IDX_MAX) {
    __sm_coalesce_chunk(map, &chunk, offset, start, p);
  }
#if 0
  __sm_when_diag({
    char *s = QCC_showSparsemap(map, 0);
    fprintf(stdout, "\n++++++++++++++++++++++++++++++ unset: %lu\n%s\n", idx, s);
    free(s);
  });
#endif
  return ret_idx;
}

sparsemap_idx_t
sparsemap_unset(sparsemap_t *map, sparsemap_idx_t idx)
{
  return __sm_map_unset(map, idx, true);
}

/*
 * When v is non-NULL we've just added a new chunk and we knew in advance that a
 * new chunk will result in a SM_PAYLOAD_MIXED which in turn requires space to
 * store the bit pattern, so given that we allocated the space ahead of time and
 * don't need to allocate it now.
 */
static sparsemap_idx_t
__sparsemap_set(sparsemap_t *map, sparsemap_idx_t idx, uint8_t *p, size_t offset, __sm_bitvec_t *v)
{
  size_t pos = v ? -1 : 0;
  __sm_chunk_t chunk;
  __sm_idx_t start = *(__sm_idx_t *)p;

  __sm_chunk_init(&chunk, p + SM_SIZEOF_OVERHEAD);
  __sm_assert(__sm_chunk_is_rle(&chunk) == false);

  switch (__sm_chunk_set_bit(&chunk, idx - start, &pos)) {
  case SM_OK:
    break;
  case SM_NEEDS_TO_GROW:
    if (!v) {
      __sm_bitvec_t vec = 0;
      offset += (SM_SIZEOF_OVERHEAD + pos * sizeof(__sm_bitvec_t));
      __sm_insert_data(map, offset, (uint8_t *)&vec, sizeof(__sm_bitvec_t));
      pos = -1;
    }
    __sm_chunk_set_bit(&chunk, idx - start, &pos);
    break;
  case SM_NEEDS_TO_SHRINK:
    /* The vector is empty, perhaps the entire chunk is empty? */
    if (__sm_chunk_is_empty(&chunk)) {
      __sm_remove_data(map, offset, SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) * 2);
      __sm_set_chunk_count(map, __sm_get_chunk_count(map) - 1);
    } else {
      offset += (SM_SIZEOF_OVERHEAD + pos * sizeof(__sm_bitvec_t));
      __sm_remove_data(map, offset, sizeof(__sm_bitvec_t));
    }
    break;
  default:
    __sm_assert(!"shouldn't be here");
#ifdef DEBUG
    abort();
#endif
    break;
  }

  return idx;
}

sparsemap_idx_t
__sm_map_set(sparsemap_t *map, sparsemap_idx_t idx, bool coalesce)
{
  __sm_chunk_t chunk;
  sparsemap_idx_t ret_idx = idx;
  __sm_assert(sparsemap_get_size(map) >= SM_SIZEOF_OVERHEAD);

  /*
   * Setting a bit could require an additional vector, let's ensure we have that
   * space available in the buffer first, or ENOMEM now.
   */
  SM_ENOUGH_SPACE(SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t));

  /* Determine if there is a chunk that could contain this index. */
  size_t offset = (size_t)__sm_get_chunk_offset(map, idx);

  if ((ssize_t)offset == -1) {
    /*
     * No chunks exist, the map is empty, so we must append a new chunk to the
     * end of the buffer and initialize it so that it can contain this index.
     */
    uint8_t buf[SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) * 2] = { 0 };
    __sm_append_data(map, &buf[0], sizeof(buf));
    uint8_t *p = __sm_get_chunk_data(map, 0);
    *(__sm_idx_t *)p = __sm_get_chunk_aligned_offset(idx);
    __sm_set_chunk_count(map, 1);

    __sm_bitvec_t *v = (__sm_bitvec_t *)(uintptr_t)p + SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t);
    ret_idx = __sparsemap_set(map, idx, p, 0, v);

    __sm_chunk_init(&chunk, p + SM_SIZEOF_OVERHEAD);
    offset = 0;
    goto done;
  }

  /*
   * Try to locate a chunk for this idx.  We could find that:
   *  - the first chunk's offset is greater than the index, or
   *  - the index is beyond the end of the last chunk, or
   *  - we found a chunk that can contain this index.
   */
  uint8_t *p = __sm_get_chunk_data(map, offset);
  __sm_idx_t start = *(__sm_idx_t *)p;
  __sm_assert(start == __sm_get_chunk_aligned_offset(start));

  if (idx < start) {
    /*
     * Our search resulted in the first chunk that starts after the index but
     * that means there is no chunk that can contain this index, so we need to
     * insert a new chunk before this one and initialize it so that it can
     * contain this index.
     */
    uint8_t buf[SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) * 2] = { 0 };
    __sm_insert_data(map, offset, &buf[0], sizeof(buf));
    /* NOTE: insert moves the memory over meaning `p` is now the new chunk */
    *(__sm_idx_t *)p = __sm_get_chunk_aligned_offset(idx);
    __sm_set_chunk_count(map, __sm_get_chunk_count(map) + 1);

    __sm_bitvec_t *v = (__sm_bitvec_t *)(uintptr_t)p + SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t);
    ret_idx = __sparsemap_set(map, idx, p, offset, v);
    goto done;
  }

  __sm_chunk_init(&chunk, p + SM_SIZEOF_OVERHEAD);
  size_t capacity = __sm_chunk_get_capacity(&chunk);

  if (capacity < SM_CHUNK_MAX_CAPACITY && idx - start < SM_CHUNK_MAX_CAPACITY) {
    /*
     * Special case, we have a sparse chunk with one or more flags set to
     * SM_PAYLOAD_NONE which reduces the carrying capacity of the chunk. In
     * this case we should remove those flags and try again.
     */
    __sm_assert(__sm_chunk_is_rle(&chunk) == false);
    __sm_chunk_increase_capacity(&chunk, SM_CHUNK_MAX_CAPACITY);
    capacity = __sm_chunk_get_capacity(&chunk);
  }

  if (chunk.m_data[0] == ~(__sm_bitvec_t)0 && idx - start == SM_CHUNK_MAX_CAPACITY) {
    /*
     * Our search resulted in a chunk that is full of ones and this index is the
     * next one after the capacity, we have a run of ones longer than the
     * capacity of the sparse encoding, let's transition this chunk to
     * run-length encoding (RLE).
     *
     * NOTE: Keep in mind that idx is 0-based, so idx=2048 is the 2049th bit.
     * When a chunk is at maximum capacity it is storing indexes [0, 2048).
     *
     * ALSO: Keep in mind the RLE "length" is the current length of 1s in the
     * run, so in this case we transition from 2048 to a length of 2049.
     * in this run.
     */

    __sm_chunk_set_rle(&chunk);
    __sm_chunk_rle_set_length(&chunk, SM_CHUNK_MAX_CAPACITY + 1);
    __sm_chunk_rle_set_capacity(&chunk, __sm_chunk_rle_capacity_limit(map, start, offset));
    goto done;
  }

  /* Is this an RLE chunk */
  if (__sm_chunk_is_rle(&chunk)) {
    size_t length = __sm_chunk_rle_get_length(&chunk);

    /* Is the index within its range, or at the end? */
    if (idx >= start && idx - start < capacity) {
      /*
       * This RLE contains the bits in [start, start + length] so the index of
       * the last bit in this RLE chunk is `start + length - 1` which is why
       * we test index (0-based) against current length (1-based) below.
       */
      if ((idx - start) == length) {
        __sm_chunk_rle_set_length(&chunk, length + 1);
        __sm_assert(__sm_chunk_rle_get_length(&chunk) == length + 1);
        goto done;
      }
    }

    /*
     * We've been asked to set a bit that is within this RLE chunk's range but
     * not within its run.  That means this chunk's capacity must shrink, and
     * we need a new sparse chunk to hold this value.
     */
    __sm_chunk_sep_t sep = { .target = { .p = p, .offset = offset, .chunk = &chunk, .start = start, .length = length, .capacity = capacity } };
    SM_ENOUGH_SPACE(__sm_separate_rle_chunk(map, &sep, idx, 1));
    goto done;
  }

  if (idx - start >= capacity) {
    /*
     * Our search resulted in a chunk however it's capacity doesn't encompass
     * this index, so we need to insert a new chunk after this one and
     * initialize it so that it can contain this index.
     */
    uint8_t buf[SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) * 2] = { 0 };
    size_t size = __sm_chunk_get_size(&chunk);
    offset += (SM_SIZEOF_OVERHEAD + size);
    p += SM_SIZEOF_OVERHEAD + size;
    __sm_insert_data(map, offset, &buf[0], sizeof(buf));

    start += __sm_chunk_get_capacity(&chunk);
    if (start + SM_CHUNK_MAX_CAPACITY <= idx) {
      start = __sm_get_chunk_aligned_offset(idx);
    }
    *(__sm_idx_t *)p = start;
    __sm_assert(start == __sm_get_chunk_aligned_offset(start));
    __sm_set_chunk_count(map, __sm_get_chunk_count(map) + 1);

    __sm_bitvec_t *v = (__sm_bitvec_t *)(uintptr_t)p + SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t);
    ret_idx = __sparsemap_set(map, idx, p, offset, v);
    goto done;
  }

  ret_idx = __sparsemap_set(map, idx, p, offset, NULL);
  if (ret_idx != idx) {
    goto done;
  }

done:;
  if (coalesce) {
    __sm_coalesce_chunk(map, &chunk, offset, start, p);
  }
#if 0
  __sm_when_diag({
    char *s = QCC_showSparsemap(map, 0);
    fprintf(stdout, "\n++++++++++++++++++++++++++++++ set: %lu\n%s\n", idx, s);
    free(s);
  });
#endif
  return ret_idx;
}

sparsemap_idx_t
sparsemap_set(sparsemap_t *map, sparsemap_idx_t idx)
{
  return __sm_map_set(map, idx, true);
}

sparsemap_idx_t
sparsemap_assign(sparsemap_t *map, sparsemap_idx_t idx, bool value)
{
  if (value) {
    return sparsemap_set(map, idx);
  } else {
    return sparsemap_unset(map, idx);
  }
}

sparsemap_idx_t
sparsemap_get_starting_offset(sparsemap_t *map)
{
  sparsemap_idx_t offset = 0;
  size_t count = __sm_get_chunk_count(map);
  if (count == 0) {
    return 0;
  }
  uint8_t *p = __sm_get_chunk_data(map, 0);
  sparsemap_idx_t relative_position = *(__sm_idx_t *)p;
  p += SM_SIZEOF_OVERHEAD;
  __sm_chunk_t chunk;
  __sm_chunk_init(&chunk, p);
  if (__sm_chunk_is_rle(&chunk)) {
    offset = relative_position;
    goto done;
  }
  for (size_t m = 0; m < sizeof(__sm_bitvec_t); m++, p++) {
    for (int n = 0; n < SM_FLAGS_PER_INDEX_BYTE; n++) {
      size_t flags = SM_CHUNK_GET_FLAGS(*p, n);
      if (flags == SM_PAYLOAD_NONE) {
        continue;
      } else if (flags == SM_PAYLOAD_ZEROS) {
        relative_position += SM_BITS_PER_VECTOR;
      } else if (flags == SM_PAYLOAD_ONES) {
        offset = relative_position;
        goto done;
      } else if (flags == SM_PAYLOAD_MIXED) {
        __sm_bitvec_t w = chunk.m_data[1 + __sm_chunk_get_position(&chunk, m * SM_FLAGS_PER_INDEX_BYTE + n)];
        for (int k = 0; k < SM_BITS_PER_VECTOR; k++) {
          if (w & ((__sm_bitvec_t)1 << k)) {
            offset = relative_position + k;
            goto done;
          }
        }
        relative_position += SM_BITS_PER_VECTOR;
      }
    }
  }
done:;
  return offset;
}

sparsemap_idx_t
sparsemap_get_ending_offset(sparsemap_t *map)
{
  sparsemap_idx_t offset = 0;
  size_t count = __sm_get_chunk_count(map);
  if (count == 0) {
    return 0;
  }
  uint8_t *p = __sm_get_chunk_data(map, 0);
  for (size_t i = 0; i < count - 1; i++) {
    p += SM_SIZEOF_OVERHEAD;
    __sm_chunk_t chunk;
    __sm_chunk_init(&chunk, p);
    p += __sm_chunk_get_size(&chunk);
  }
  __sm_idx_t start = *(__sm_idx_t *)p;
  p += SM_SIZEOF_OVERHEAD;
  __sm_chunk_t chunk;
  __sm_chunk_init(&chunk, p);
  if (SM_IS_CHUNK_RLE(&chunk)) {
    return start + __sm_chunk_rle_get_length(&chunk) - 1;
  } else {
    sparsemap_idx_t relative_position = start;
    for (size_t m = 0; m < sizeof(__sm_bitvec_t); m++, p++) {
      for (int n = 0; n < SM_FLAGS_PER_INDEX_BYTE; n++) {
        size_t flags = SM_CHUNK_GET_FLAGS(*p, n);
        if (flags == SM_PAYLOAD_NONE) {
          continue;
        } else if (flags == SM_PAYLOAD_ZEROS) {
          relative_position += SM_BITS_PER_VECTOR;
        } else if (flags == SM_PAYLOAD_ONES) {
          relative_position += SM_BITS_PER_VECTOR;
          offset = relative_position;
        } else if (flags == SM_PAYLOAD_MIXED) {
          __sm_bitvec_t w = chunk.m_data[1 + __sm_chunk_get_position(&chunk, m * SM_FLAGS_PER_INDEX_BYTE + n)];
          int idx = 0;
          for (int k = 0; k < SM_BITS_PER_VECTOR; k++) {
            if (w & ((__sm_bitvec_t)1 << k)) {
              idx = k;
            }
          }
          offset = relative_position + idx;
          relative_position += SM_BITS_PER_VECTOR;
        }
      }
    }
    return offset;
  }
}

double
sparsemap_fill_factor(sparsemap_t *map)
{
  size_t rank = sparsemap_rank(map, 0, SPARSEMAP_IDX_MAX, true);
  sparsemap_idx_t end = sparsemap_get_ending_offset(map);
  return (double)rank / (double)end * 100.0;
}

void *
sparsemap_get_data(sparsemap_t *map)
{
  return map->m_data;
}

size_t
sparsemap_get_size(sparsemap_t *map)
{
  if (map->m_data_used) {
    size_t size = __sm_get_size_impl(map);
    if (size != map->m_data_used) {
      map->m_data_used = size;
    }
    __sm_when_diag({ __sm_assert(map->m_data_used == __sm_get_size_impl(map)); });
    return map->m_data_used;
  }
  return map->m_data_used = __sm_get_size_impl(map);
}

size_t
sparsemap_count(sparsemap_t *map)
{
  return sparsemap_rank(map, 0, SPARSEMAP_IDX_MAX, true);
}

void
sparsemap_scan(sparsemap_t *map, void (*scanner)(__sm_idx_t[], size_t, void *aux), size_t skip, void *aux)
{
  uint8_t *p = __sm_get_chunk_data(map, 0);
  size_t count = __sm_get_chunk_count(map);

  for (size_t i = 0; i < count; i++) {
    __sm_idx_t start = *(__sm_idx_t *)p;
    p += SM_SIZEOF_OVERHEAD;
    __sm_chunk_t chunk;
    __sm_chunk_init(&chunk, p);
    size_t skipped = __sm_chunk_scan(&chunk, start, scanner, skip, aux);
    if (skip) {
      __sm_assert(skip >= skipped);
      skip -= skipped;
    }
    p += __sm_chunk_get_size(&chunk);
  }
}

int
sparsemap_merge(sparsemap_t *destination, sparsemap_t *source)
{
  uint8_t *src, *dst;
  size_t src_count = __sm_get_chunk_count(source);
  sparsemap_idx_t dst_ending_offset = sparsemap_get_ending_offset(destination);

  if (src_count == 0) {
    return 0;
  }

  // TODO: rethink this method of estimating space... seems off to me now...
  ssize_t remaining_capacity = destination->m_capacity - destination->m_data_used -
    (source->m_data_used + src_count * (SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) * 2));

  /* Estimate worst-case overhead required for merge. */
  if (remaining_capacity <= 0) {
    errno = ENOSPC;
    return -remaining_capacity;
  }

  /*
   * Strategy here it to walk the ordered set of chunks in the source map
   * examining each one against the current destination chunk.  This is similar
   * to a merge sort with two cursors, one in src and one in dst.  Then there
   * are a number of cases to consider:
   * - src proceeds dst
   * - src follows dst
   * - src and dst overlap
   *   - perfect overlap
   *   - non-uniform overlap
   */
  src = __sm_get_chunk_data(source, 0);
  while (src_count) {
    __sm_idx_t src_start = *(__sm_idx_t *)src;
    __sm_chunk_t src_chunk;
    __sm_chunk_init(&src_chunk, src + SM_SIZEOF_OVERHEAD);
    bool src_is_rle = SM_IS_CHUNK_RLE(&src_chunk);
    size_t src_capacity = __sm_chunk_get_capacity(&src_chunk);
    ssize_t dst_offset = __sm_get_chunk_offset(destination, src_start);
    if (dst_offset >= 0) {
      dst = __sm_get_chunk_data(destination, dst_offset);
      __sm_idx_t dst_start = *(__sm_idx_t *)dst;
      __sm_chunk_t dst_chunk;
      __sm_chunk_init(&dst_chunk, dst + SM_SIZEOF_OVERHEAD);
      bool dst_is_rle = SM_IS_CHUNK_RLE(&dst_chunk);
      size_t dst_capacity = __sm_chunk_get_capacity(&dst_chunk);

      /* Try to expand the capacity if there's room before the start of the next chunk. */
      if (!(src_is_rle || dst_is_rle)) {
        if (src_start == dst_start && dst_capacity < src_capacity) {
          ssize_t nxt_offset = __sm_get_chunk_offset(destination, dst_start + dst_capacity + 1);
          uint8_t *nxt_dst = __sm_get_chunk_data(destination, nxt_offset);
          __sm_idx_t nxt_dst_start = *(__sm_idx_t *)nxt_dst;
          if (nxt_dst_start > dst_start + src_capacity) {
            __sm_chunk_increase_capacity(&dst_chunk, src_capacity);
            dst_capacity = __sm_chunk_get_capacity(&dst_chunk);
          }
        }
      }

      /* Source chunk (sparse/RLE) precedes next destination chunk. */
      if ((src_start + src_capacity) <= dst_start) {
        size_t src_size = __sm_chunk_get_size(&src_chunk);
        ssize_t offset = __sm_get_chunk_offset(destination, dst_start);
        /* Insert a copy of the src chunk in dst at the proper offset. */
        __sm_insert_data(destination, offset, src, SM_SIZEOF_OVERHEAD + src_size);
        /* Update the chunk count in dst. */
        __sm_set_chunk_count(destination, __sm_get_chunk_count(destination) + 1);

        /* Move to the next src chunk. */
        src_count--;
        src += SM_SIZEOF_OVERHEAD + __sm_chunk_get_size(&src_chunk);
        continue;
      }

      /* Source chunk (sparse/RLE) follows next destination chunk. */
      if (src_start >= (dst_start + dst_capacity)) {
        size_t src_size = __sm_chunk_get_size(&src_chunk);
        /* Insert or append a copy of the src chunk in dst. */
        if (dst_offset == __sm_get_chunk_offset(destination, SPARSEMAP_IDX_MAX)) {
          __sm_append_data(destination, src, SM_SIZEOF_OVERHEAD + src_size);
        } else {
          ssize_t offset = __sm_get_chunk_offset(destination, src_start);
          __sm_insert_data(destination, offset, src, SM_SIZEOF_OVERHEAD + src_size);
        }
        /* Update the chunk count and data_used. */
        __sm_set_chunk_count(destination, __sm_get_chunk_count(destination) + 1);

        /* Move to the next src chunk. */
        src_count--;
        src += SM_SIZEOF_OVERHEAD + __sm_chunk_get_size(&src_chunk);
        continue;
      }

      /* At this point we know that the dst chunk and src chunk overlap. */
      size_t src_length = __sm_chunk_rle_get_length(&src_chunk);
      size_t dst_length = __sm_chunk_rle_get_length(&dst_chunk);
      size_t src_capacity = __sm_chunk_get_capacity(&src_chunk);

      if (src_is_rle && dst_is_rle) {
        /* Both src and dst are RLE ... */
        __sm_chunk_rle_set_capacity(&dst_chunk, __sm_chunk_rle_capacity_limit(destination, src_start, dst_offset));
        if (src_length >= dst_length) {
          /* ... and src is larger than dst. */
          __sm_chunk_rle_set_length(&dst_chunk, __sm_chunk_rle_get_length(&src_chunk));
        }
        if (src_start <= dst_start) {
          /* ... and src starts before dst. */
          *(__sm_idx_t *)dst = src_start;
        }

        /* Move to the next src chunk. */
        src_count--;
        src += SM_SIZEOF_OVERHEAD + __sm_chunk_get_size(&src_chunk);
        continue;
      }

      /* Source and destination start at the same point. */
      if (src_start == dst_start && src_capacity == dst_capacity) {
        /* Source and destination and a perfect overlapping non-RLE pair. */
        __sm_merge_chunk(destination, src_start, dst_start, dst_capacity, &dst_chunk, &src_chunk);

        /* Move to the next src chunk. */
        src_count--;
        src += SM_SIZEOF_OVERHEAD + __sm_chunk_get_size(&src_chunk);
        continue;
      }

      /* Non-uniform overlapping chunks. */
      if (dst_start < src_start || (dst_start == src_start && dst_capacity != src_capacity)) {
        size_t src_end = src_start + src_capacity;
        size_t dst_end = dst_start + dst_capacity;
        size_t overlap = src_end > dst_end ? src_capacity - (src_end - dst_end) : src_capacity;
        __sm_merge_chunk(destination, src_start, dst_start, overlap, &dst_chunk, &src_chunk);
        for (size_t n = src_start + overlap; n <= src_end; n++) {
          if (sparsemap_is_set(source, n)) {
            sparsemap_set(destination, n);
          }
        }

        /* Move to the next src chunk. */
        src_count--;
        src += SM_SIZEOF_OVERHEAD + __sm_chunk_get_size(&src_chunk);
        continue;
      }

      abort();
    } else {
      /* A negative destination offset indicates an empty map. */

      if (src_start >= dst_ending_offset) {
        /* Starting offset is after destination chunks, so append data. */
        size_t src_size = __sm_chunk_get_size(&src_chunk);
        __sm_append_data(destination, src, SM_SIZEOF_OVERHEAD + src_size);

        /* Update the chunk count and data_used. */
        __sm_set_chunk_count(destination, __sm_get_chunk_count(destination) + 1);

        /* Move to the next src chunk. */
        src_count--;
        src += SM_SIZEOF_OVERHEAD + __sm_chunk_get_size(&src_chunk);
        continue;
      } else {
        /* Source chunk precedes next destination chunk. */
        size_t src_size = __sm_chunk_get_size(&src_chunk);
        ssize_t offset = __sm_get_chunk_offset(destination, src_start);
        __sm_insert_data(destination, offset, src, SM_SIZEOF_OVERHEAD + src_size);

        /* Update the chunk count and data_used. */
        __sm_set_chunk_count(destination, __sm_get_chunk_count(destination) + 1);

        /* Move to the next src chunk. */
        src_count--;
        src += SM_SIZEOF_OVERHEAD + __sm_chunk_get_size(&src_chunk);
        continue;
      }
    }
  }

  __sm_coalesce_map(destination);
  return 0;
}

sparsemap_idx_t
sparsemap_split(sparsemap_t *map, sparsemap_idx_t idx, sparsemap_t *other)
{
  uint8_t *src, *dst, *prev;
  int moved = 0;
  size_t i, count = __sm_get_chunk_count(map);
  bool in_middle = false;

  __sm_assert(sparsemap_count(other) == 0);

  __sm_when_diag({ __sm_diag_map(map, "========== START: %lu", idx); });

  /*
   * According to the API when idx is SPARSEMAP_IDX_MAX the client is
   * requesting that we divide the bits in two equal portions, so we
   * calculate that index here.
   */
  if (idx == SPARSEMAP_IDX_MAX) {
    sparsemap_idx_t begin = sparsemap_get_starting_offset(map);
    sparsemap_idx_t end = sparsemap_get_ending_offset(map);
    if (begin != end) {
      size_t rank = sparsemap_rank(map, begin, end, true);
      idx = sparsemap_select(map, rank / 2, true);
    } else {
      return SPARSEMAP_IDX_MAX;
    }
  }

  /* Is the index beyond the last bit set in the source? */
  if (idx >= sparsemap_get_ending_offset(map)) {
    return idx;
  }

  /*
   * Here's how this is going to work, there are three phases.
   * 1) Skip over any chunks before the idx.
   * 2) If the idx falls within a chunk, ...
   *  2a) If that chunk is RLE, separate the RLE into two or three chunks
   *  2b) Recursively call sparsemap_split() because now we have a sparse chunk
   * 3) Split the sparse chunk
   * 4) Keep half in the src and insert the other half into the dst
   * 5) Move any remaining chunks to dst.
   */
  src = __sm_get_chunk_data(map, 0);
  dst = __sm_get_chunk_end(other);

  /* (1): skip over chunks that are entirely to the left. */
  prev = src;
  for (i = 0; i < count; i++) {
    __sm_idx_t start = *(__sm_idx_t *)src;
    if (start == idx) {
      break;
    }
    __sm_chunk_t chunk;
    __sm_chunk_init(&chunk, src + SM_SIZEOF_OVERHEAD);
    if (start + __sm_chunk_get_capacity(&chunk) > idx) {
      in_middle = true;
      break;
    }
    if (start > idx) {
      src = prev;
      i--;
      break;
    }

    prev = src;
    src += SM_SIZEOF_OVERHEAD + __sm_chunk_get_size(&chunk);
  }

  /* (2): The idx falls within a chunk then it has to be split. */
  if (in_middle) {
    __sm_chunk_t s_chunk, d_chunk;
    __sm_chunk_init(&s_chunk, src + SM_SIZEOF_OVERHEAD);
    __sm_chunk_init(&d_chunk, dst + SM_SIZEOF_OVERHEAD);
    __sm_idx_t src_start = *(__sm_idx_t *)src;

    /* (2a) Does the idx fall within the range of an RLE chunk? */
    if (SM_IS_CHUNK_RLE(&s_chunk)) {
      /*
       * There is a function that can split an RLE chunk at an index, but to use
       * it and not mutate anything we'll need to jump through a few hoops.
       * To perform this trick we need to first need a new static buffer
       * that we can use with a new "stunt" map. Once we have the chunk we need
       * to split in that new buffer wrapped into a new map we can call our API
       * that separates the RLE chunk at the index.
       */

      sparsemap_t stunt;
      __sm_chunk_t chunk;
      uint8_t buf[(SM_SIZEOF_OVERHEAD * 3) + (sizeof(__sm_bitvec_t) * 6)] = { 0 };

      /* Copy the source chunk into the buffer. */
      memcpy(buf + SM_SIZEOF_OVERHEAD, src, SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t));
      /* Set the number of chunks to 1 in our stunt map. */
      buf[0] = (uint32_t)1;
      /* And initialize the stunt double chunk we need to split. */
      sparsemap_open(&stunt, buf, (SM_SIZEOF_OVERHEAD * 3) + (sizeof(__sm_bitvec_t) * 6));
      __sm_chunk_init(&chunk, buf + SM_SIZEOF_OVERHEAD);

      /* Finally, let's separate the RLE chunk at index. */
      __sm_chunk_sep_t sep = { .target = { .p = buf + SM_SIZEOF_OVERHEAD,
                                 .offset = 0,
                                 .chunk = &chunk,
                                 .start = src_start,
                                 .length = __sm_chunk_rle_get_length(&s_chunk),
                                 .capacity = __sm_chunk_get_capacity(&s_chunk) } };
      __sm_separate_rle_chunk(&stunt, &sep, idx, -1);

      /*
       * (2b) Assuming we have the space we'll update the source map with the
       * separate, but equivalent chunks and then recurse confident that next time
       * our index will fall inside a sparse chunk (that we just made).
       */
      SM_ENOUGH_SPACE(sep.expand_by);
      __sm_insert_data(map, __sm_get_chunk_offset(map, idx) + SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t), sep.buf + SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t),
        sep.expand_by);
      memcpy(src, sep.buf, sep.expand_by + SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t));
      __sm_set_chunk_count(map, __sm_get_chunk_count(map) + (sep.count - 1));

      __sm_when_diag({ __sm_diag_map(map, "========== PREPARED:"); });
      return sparsemap_split(map, idx, other);
    }

    /*
     * (3) We're in the middle of a sparse chunk, let's split it.
     */

    /* Zero out the space we'll need at the proper location in dst. */
    uint8_t buf[SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t) * 2] = { 0 };
    memcpy(dst, &buf, sizeof(buf));

    /* And add a chunk to the other map. */
    __sm_set_chunk_count(other, __sm_get_chunk_count(other) + 1);
    if (other->m_data_used != 0) {
      other->m_data_used += SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t);
    }

    /* Copy the bits in the sparse chunk, at most SM_CHUNK_MAX_CAPACITY. */
    *(__sm_idx_t *)dst = src_start;
    for (size_t j = idx; j < src_start + SM_CHUNK_MAX_CAPACITY; j++) {
      if (sparsemap_is_set(map, j)) {
        __sm_map_set(other, j, false);
        __sm_map_unset(map, j, false);
      }
    }
    src += SM_SIZEOF_OVERHEAD + __sm_chunk_get_size(&s_chunk);
    dst += SM_SIZEOF_OVERHEAD + __sm_chunk_get_size(&d_chunk);
    i++;
  }

  /* Now continue with all remaining chunks. */
  for (; i < count; i++) {
    __sm_idx_t start = *(__sm_idx_t *)src;
    src += SM_SIZEOF_OVERHEAD;
    __sm_chunk_t chunk;
    __sm_chunk_init(&chunk, src);
    size_t s = __sm_chunk_get_size(&chunk);

    *(__sm_idx_t *)dst = start;
    dst += SM_SIZEOF_OVERHEAD;
    memcpy(dst, src, s);
    src += s;
    dst += s;

    moved++;
  }

  /* Force new calculation. */
  other->m_data_used = 0;
  map->m_data_used = 0;

  /* Update the Chunk counters. */
  __sm_set_chunk_count(map, __sm_get_chunk_count(map) - moved);
  __sm_set_chunk_count(other, __sm_get_chunk_count(other) + moved);

  __sm_assert(sparsemap_get_size(map) >= SM_SIZEOF_OVERHEAD);
  __sm_assert(sparsemap_get_size(other) > SM_SIZEOF_OVERHEAD);

  __sm_coalesce_map(map);
  __sm_coalesce_map(other);

  __sm_when_diag({
    __sm_diag_map(map, "SRC");
    __sm_diag_map(other, "DST");
  });

  return idx;
}

sparsemap_idx_t
sparsemap_select(sparsemap_t *map, sparsemap_idx_t n, bool value)
{
  __sm_assert(sparsemap_get_size(map) >= SM_SIZEOF_OVERHEAD);
  __sm_idx_t start;
  size_t count = __sm_get_chunk_count(map);

  if (count == 0 && value == false) {
    return n;
  }

  uint8_t *p = __sm_get_chunk_data(map, 0);

  for (size_t i = 0; i < count; i++) {
    start = *(__sm_idx_t *)p;
    /* Start of this chunk is greater than n meaning there are a set of 0s
     * before the first 1 sufficient to consume n. */
    if (value == false && i == 0 && start > n) {
      return n;
    }
    p += SM_SIZEOF_OVERHEAD;
    __sm_chunk_t chunk;
    __sm_chunk_init(&chunk, p);

    ssize_t new_n = n;
    size_t index = __sm_chunk_select(&chunk, n, &new_n, value);
    if (new_n == -1) {
      return start + index;
    }
    n = new_n;

    p += __sm_chunk_get_size(&chunk);
  }
  return SPARSEMAP_IDX_MAX;
}

static size_t
__sm_rank_vec(sparsemap_t *map, size_t begin, size_t end, bool value, __sm_bitvec_t *vec)
{
  __sm_assert(sparsemap_get_size(map) >= SM_SIZEOF_OVERHEAD);
  size_t amt, gap, pos = 0, result = 0, prev = 0, count, len = end - begin + 1;
  uint8_t *p;

  if (begin > end) {
    return 0;
  }

  if (begin == end) {
    return sparsemap_is_set(map, begin) == value ? 1 : 0;
  }

  count = __sm_get_chunk_count(map);

  if (count == 0) {
    if (value == false) {
      /* The count/rank of unset bits in an empty map is inf, so what you requested is the answer. */
      return len;
    }
  }

  p = __sm_get_chunk_data(map, 0);
  for (size_t i = 0; i < count; i++) {
    __sm_idx_t start = *(__sm_idx_t *)p;
    /* [prev, start + pos), prev is the last bit examined 0-based. */
    if (i == 0) {
      gap = start;
    } else {
      if (prev + SM_CHUNK_MAX_CAPACITY == start) {
        gap = 0;
      } else {
        gap = start - (prev + pos);
      }
    }
    /* Start of this chunk is greater than the end of the desired range. */
    if (start > end) {
      if (value == true) {
        /* We're counting set bits and this chunk starts after the range
         * [begin, end], we're done. */
        return result;
      } else {
        if (i == 0) {
          /* We're counting unset bits and the first chunk starts after the
           * range meaning everything proceeding this chunk was zero and should
           * be counted, also we're done. */
          result += (end - begin) + 1;
          return result;
        } else {
          /* We're counting unset bits and some chunk starts after the range, so
           * we've counted enough, we're done. */
          if (pos > end) {
            return result;
          } else {
            if (end - pos < gap) {
              result += end - pos;
              return result;
            } else {
              result += gap;
              return result;
            }
          }
        }
      }
    } else {
      /* The range and this chunk overlap. */
      if (value == false) {
        if (begin > gap) {
          begin -= gap;
        } else {
          result += gap - begin;
          begin = 0;
        }
      } else {
        if (begin >= gap) {
          begin -= gap;
        }
      }
    }
    prev = start;
    p += SM_SIZEOF_OVERHEAD;
    __sm_chunk_t chunk;
    __sm_chunk_init(&chunk, p);

    /* Count all the set/unset inside this chunk within the range. */
    __sm_chunk_rank_t rank;
    amt = __sm_chunk_rank(&rank, value, &chunk, begin, end - start);
    result += amt;
    pos = rank.pos;
    begin = rank.pos > begin ? 0 : begin - rank.pos;
    // vec = rank.rem;
    p += __sm_chunk_get_size(&chunk);
  }
  /* Count any additional unset bits that fall outside the last chunk but
   * within the range. */
  if (value == false) {
    size_t last = prev - 1 + pos;
    if (end > last) {
      result += end - last - begin;
    }
  }
  return result;
}

size_t
sparsemap_rank(sparsemap_t *map, sparsemap_idx_t begin, sparsemap_idx_t end, bool value)
{
  __sm_bitvec_t vec;
  return __sm_rank_vec(map, begin, end, value, &vec);
}

size_t
sparsemap_span(sparsemap_t *map, sparsemap_idx_t idx, size_t len, bool value)
{
  size_t rank, nth;
  __sm_bitvec_t vec = 0;
  sparsemap_idx_t offset;

  /* When skipping forward to `idx` offset in the map we can determine how
   * many selects we can avoid by taking the rank of the range and starting
   * at that bit. */
  nth = (idx == 0) ? 0 : sparsemap_rank(map, 0, idx - 1, value);
  if (SPARSEMAP_NOT_FOUND(nth)) {
    return nth;
  }
  /* Find the first bit that matches value, then... */
  offset = sparsemap_select(map, nth, value);
  do {
    /* See if the rank of the bits in the range starting at offset is equal
     * to the desired amount. */
    rank = (len == 1) ? 1 : __sm_rank_vec(map, offset, offset + len - 1, value, &vec);
    if (rank >= len) {
      /* We've found what we're looking for, return the index of the first
       * bit in the range. */
      break;
    }
    /* Now we try to jump forward as much as possible before we look for a
     * new match. We do this by counting the remaining bits in the returned
     * vec from the call to rank_vec(). */
    int amt = 1;
    if (vec > 0) {
      /* The returned vec had some set bits, let's move forward in the map as
       * much as possible (max: 64 bit positions). */
      int max = len > SM_BITS_PER_VECTOR ? SM_BITS_PER_VECTOR : len;
      while (amt < max && (vec & 1 << amt)) {
        amt++;
      }
    }
    nth += amt;
    offset = sparsemap_select(map, nth, value);
  } while (SPARSEMAP_FOUND(offset));

  return offset;
}

#ifdef SPARSEMAP_TESTING

#include <qc.h>

static double
_tst_pow(double base, int exponent)
{
  if (exponent == 0) {
    return 1.0; // 0^0 is 1
  } else if (base == 0.0) {
    return 0.0; // 0 raised to any positive exponent is 0 (except 0^0)
  } else if (base < 0.0 && (exponent & 1) != 0) {
    // negative base with odd exponent, results in a negative
    return -_tst_pow(-base, exponent);
  }

  double result = base;
  for (unsigned int i = 1; i < exponent; i++) {
    result *= base;
  }
  return result;
}

static char *
_qcc_format_chunk(__sm_idx_t start, __sm_chunk_t *chunk, bool none)
{
  size_t amt = sizeof(wchar_t) * ((SM_FLAGS_PER_INDEX * 16) + (SM_BITS_PER_VECTOR * 64) + 16) * 2;
  char *buf = (char *)malloc(sizeof(wchar_t) * ((SM_FLAGS_PER_INDEX * 16) + (SM_BITS_PER_VECTOR * 64) + 16) * 2);

  __sm_bitvec_t desc = chunk->m_data[0];

  if (!__sm_chunk_is_rle(chunk)) {
    char desc_str[((2 * SM_FLAGS_PER_INDEX) + 1) * sizeof(wchar_t)] = { 0 };
    char *str = desc_str;
    int mixed = 0;
    // for (int i = SM_FLAGS_PER_INDEX - 1; i >= 0; i--) {
    for (int i = 1; i <= SM_FLAGS_PER_INDEX; i++) {
      uint8_t flag = SM_CHUNK_GET_FLAGS(desc, i);
      switch (flag) {
      case SM_PAYLOAD_NONE:
        if (!none)
          __sm_assert(flag == SM_PAYLOAD_NONE);
        str += sprintf(str, "_"); // ∘
        break;
      case SM_PAYLOAD_ONES:
        str += sprintf(str, "1");
        break;
      case SM_PAYLOAD_ZEROS:
        str += sprintf(str, "0");
        break;
      case SM_PAYLOAD_MIXED:
        str += sprintf(str, "X"); // ①
        mixed++;
        break;
      }
      if (i % 8 == 0 && i < 32)
        str += sprintf(str, " ");
    }
    str = buf + sprintf(buf, "%.10u\t|%s|%s", start, desc_str, mixed ? " :: " : "");
    for (int i = 0; i < mixed; i++) {
      // str += sprintf(str, "0x%0lX%s", chunk->m_data[1 + i], i + 1 < mixed ? " " : "");
      size_t n = snprintf(str, amt - 1, "%#018" PRIx64 "%s", chunk->m_data[1 + i], i + 1 < mixed ? " " : "");
      str += n;
      amt -= n;
    }
  } else {
    // sprintf(buf, "%.10u\t1»%zu of %zu", start, __sm_chunk_rle_get_length(chunk), __sm_chunk_rle_get_capacity(chunk));
    size_t len = __sm_chunk_rle_get_length(chunk);
    size_t cap = __sm_chunk_rle_get_capacity(chunk);
    sprintf(buf, "%.10u\t[%u, %zu) %zu of %zu", start, start, start + len - 1, len, cap);
  }
  return buf;
}

char *
QCC_showChunk(void *value, int len)
{
  __sm_idx_t start = *(__sm_idx_t *)value;
  __sm_chunk_t chunk;
  __sm_chunk_init(&chunk, value + SM_SIZEOF_OVERHEAD);

  return _qcc_format_chunk(start, &chunk, false);
}

char *
QCC_showSparsemap(void *value, int len)
{
  sparsemap_t *map = (sparsemap_t *)value;
  size_t off = 0, count = __sm_get_chunk_count(map);
  char *str, *buf = NULL;

  if (count > 0) {
    uint8_t *s, *p = __sm_get_chunk_data(map, 0);
    for (size_t i = 0; i < count; i++) {
      __sm_chunk_t chunk;
      __sm_idx_t start = *(__sm_idx_t *)p;
      __sm_chunk_init(&chunk, p + SM_SIZEOF_OVERHEAD);
      char *c = _qcc_format_chunk(start, &chunk, true);
      if (buf) {
        char *new = realloc(buf, strlen(buf) + strlen(c) + 24);
        if (new) {
          buf = new;
          str += sprintf(str, "\n%s", c);
        }
      } else {
        buf = c;
        str = buf + strlen(c);
      }
      p += SM_SIZEOF_OVERHEAD + __sm_chunk_get_size(&chunk);
      off = p - s;
    }
  }

  return buf;
}

static void
QCC_freeChunkValue(void *value)
{
  free(value);
}

static void
QCC_freeSparsemapValue(void *value)
{
  free(value);
}

QCC_GenValue *
QCC_genChunk()
{
  if (((double)random() / (double)RAND_MAX) > 0.5) {
    // Generate a run-length encoded (RLE) chunk:
    sparsemap_idx_t from = 1, to = SM_CHUNK_RLE_MAX_LENGTH;
    unsigned int len = ((unsigned int)random() % (to - from)) + from;
    // First allocate enough room for the chunk data ...
    uint8_t *p = malloc(SM_SIZEOF_OVERHEAD + sizeof(__sm_chunk_t) + (sizeof(__sm_bitvec_t) * 2));
    __sm_chunk_t *chunk;
    // ... then set the offset to the length so we can test for that later ...
    *(__sm_idx_t *)p = len;
    // ... next is the chunk begins after the offset ...
    chunk = (__sm_chunk_t *)((uintptr_t)p + SM_SIZEOF_OVERHEAD);
    // ... this contains a single vector ...
    chunk->m_data = (__sm_bitvec_t *)((uintptr_t)chunk + sizeof(__sm_chunk_t));
    chunk->m_data[0] = 0;
    // ... set the flags on this vector to indicate that is it RLE ...
    __sm_chunk_set_rle(chunk);
    // ... set the RLE chunk's initial capacity ...
    __sm_chunk_rle_set_capacity(chunk, SM_CHUNK_RLE_MAX_CAPACITY);
    // ... and set the RLE chunk's length of 1s to len.
    __sm_chunk_rle_set_length(chunk, len);
    // Now, test what we've generated to ensure it's correct.
    __sm_assert(*(__sm_idx_t *)p == len);
    __sm_assert(__sm_chunk_is_rle(chunk));
    __sm_assert(__sm_chunk_rle_get_capacity(chunk) == SM_CHUNK_RLE_MAX_CAPACITY);
    __sm_assert(__sm_chunk_rle_get_length(chunk) == len);
    return QCC_initGenValue(p, 1, QCC_showChunk, QCC_freeChunkValue);
  } else {
    // Generate a chunk with the offset equal to the number of additional
    // vectors (len) and a descriptor that matches that with random data.
    unsigned int from = 0, to = SM_FLAGS_PER_INDEX;
    unsigned int len = ((unsigned int)random() % (to - from)) + from;
    unsigned int cut = ((unsigned int)random() % ((SM_FLAGS_PER_INDEX - len) - from)) + from;
    // First allocate enough room for the chunk data ...
    uint8_t *p = malloc(SM_SIZEOF_OVERHEAD + sizeof(__sm_chunk_t) + (sizeof(__sm_bitvec_t) * (len + 1)));
    __sm_chunk_t *chunk;
    // ... then set the offset to the capacity ...
    *(__sm_idx_t *)p = SM_CHUNK_MAX_CAPACITY - (cut * SM_BITS_PER_VECTOR);
    // ... next is the chunk begins after the offset ...
    chunk = (__sm_chunk_t *)((uintptr_t)p + SM_SIZEOF_OVERHEAD);
    // ... this contains a len + 1 vectors ...
    chunk->m_data = (__sm_bitvec_t *)((uintptr_t)chunk + sizeof(__sm_chunk_t));
    // ... the first is the descriptor with the flags ...
    __sm_bitvec_t *desc = chunk->m_data;
    *desc = 0;
    // ... ensure that exactly `len` flags are set to SM_PAYLOAD_MIXED ...
    for (size_t i = 0; i < len; i++) {
      SM_CHUNK_SET_FLAGS(*desc, i, SM_PAYLOAD_MIXED);
      chunk->m_data[1 + i] = (uintptr_t)chunk + i;
    }
    // ... and, on average, 50% of the rest are SM_PAYLOAD_ONES ...
    for (size_t i = len; i < SM_FLAGS_PER_INDEX - cut; i++) {
      double coin = (double)random() / (double)RAND_MAX;
      if (SM_CHUNK_GET_FLAGS(*desc, i) != SM_PAYLOAD_MIXED && coin >= 0.5) {
        SM_CHUNK_SET_FLAGS(*desc, i, SM_PAYLOAD_ONES);
      }
    }
    // ... shuffle those around ...
    for (size_t i = 0; i < SM_FLAGS_PER_INDEX - cut - 1; i++) {
      size_t j = ((size_t)random() % ((SM_FLAGS_PER_INDEX - cut) - i)) + i;
      int flags = SM_CHUNK_GET_FLAGS(*desc, j);
      SM_CHUNK_SET_FLAGS(*desc, j, SM_CHUNK_GET_FLAGS(*desc, i));
      SM_CHUNK_SET_FLAGS(*desc, i, flags);
    }
    // ... reduce the capacity by setting trailing flags to SM_PAYLOAD_NONE ...
    *desc <<= (cut * 2);
    for (int i = 0; i < cut; i++) {
      SM_CHUNK_SET_FLAGS(*desc, i, SM_PAYLOAD_NONE);
    }
    // fprintf(stdout, "\n%s\n", QCC_showChunk(p, 0));
    // ... and check that our franken-chunk appears to be correct.
    __sm_assert(__sm_chunk_is_rle(chunk) == false);
    return QCC_initGenValue(p, 1, QCC_showChunk, QCC_freeChunkValue);
  }
}

extern void populate_map(sparsemap_t *map, int size, int max_value);

QCC_GenValue *
QCC_genSparsemap()
{
  sparsemap_t *map = sparsemap(1024);
  return QCC_initGenValue(map, 1, QCC_showSparsemap, QCC_freeSparsemapValue);
}

static size_t
_tst_sm_chunk_calc_vector_size(uint8_t b)
{
  int count = 0;

  for (int i = 0; i < 4; i++) {
    if (((b >> (i * 2)) & 0x03) == 0x02) {
      count++;
    }
  }

  return count;
}

QCC_TestStatus
_tst_chunk_calc_vector_size_equality(QCC_GenValue **vals, int len, QCC_Stamp **stamp)
{
  unsigned int a = *QCC_getValue(vals, 0, unsigned int *) % 256;
  if (_tst_sm_chunk_calc_vector_size(a) != __sm_chunk_calc_vector_size(a)) {
    return QCC_FAIL;
  }
  return QCC_OK;
}

QCC_TestStatus
_tst_chunk_get_position(QCC_GenValue **vals, int len, QCC_Stamp **stamp)
{
  uint8_t *p = (uint8_t *)QCC_getValue(vals, 0, void *);
  __sm_idx_t start = *(__sm_idx_t *)p;
  __sm_chunk_t *chunk = (__sm_chunk_t *)((uintptr_t)p + SM_SIZEOF_OVERHEAD);
  size_t pos;

  if (__sm_chunk_is_rle(chunk)) {
    for (size_t i = 0; i < SM_FLAGS_PER_INDEX; i++) {
      pos = __sm_chunk_get_position(chunk, i);
      if (pos != 0) {
        return QCC_FAIL;
      }
    }
  } else {
    size_t mixed = 0;
    for (size_t i = 0; i < SM_FLAGS_PER_INDEX; i++) {
      uint8_t flag = SM_CHUNK_GET_FLAGS(*chunk->m_data, i);
      switch (flag) {
      case SM_PAYLOAD_MIXED:
        pos = __sm_chunk_get_position(chunk, i);
        if (chunk->m_data[1 + pos] != (uintptr_t)chunk + pos) {
          return QCC_FAIL;
        }
        mixed++;
        break;
      case SM_PAYLOAD_ONES:
      case SM_PAYLOAD_ZEROS:
        pos = __sm_chunk_get_position(chunk, i);
        if (pos != mixed) {
          return QCC_FAIL;
        }
        break;
      case SM_PAYLOAD_NONE:
      default:
        break;
      }
    }
  }
  return QCC_OK;
}

QCC_TestStatus
_tst_chunk_get_capacity(QCC_GenValue **vals, int len, QCC_Stamp **stamp)
{
  uint8_t *p = (uint8_t *)QCC_getValue(vals, 0, void *);
  __sm_idx_t start = *(__sm_idx_t *)p;
  __sm_chunk_t *chunk = (__sm_chunk_t *)((uintptr_t)p + SM_SIZEOF_OVERHEAD);

  if (__sm_chunk_is_rle(chunk)) {
    if (__sm_chunk_rle_get_length(chunk) != start) {
      return QCC_FAIL;
    }
  } else {
    if (__sm_chunk_get_capacity(chunk) != start) {
      return QCC_FAIL;
    }
  }
  return QCC_OK;
}

QCC_TestStatus
_tst_get_chunk_offset(QCC_GenValue **vals, int len, QCC_Stamp **stamp)
{
  unsigned int idx = *QCC_getValue(vals, 0, unsigned int *);
  sparsemap_t *map = QCC_getValue(vals, 1, sparsemap_t *);
  unsigned int max_offset = ((SM_FLAGS_PER_INDEX - 1) * sizeof(__sm_bitvec_t));
  unsigned int rnd_offset = (idx % max_offset) - ((idx % max_offset) % sizeof(__sm_bitvec_t));
  unsigned int rnd_nvec = rnd_offset / sizeof(__sm_bitvec_t);
  __sm_idx_t offset = __sm_get_chunk_aligned_offset(idx);

  // An empty map should return -1 (no chunks present, so offset of -1).
  for (unsigned int i = offset; i < SM_CHUNK_MAX_CAPACITY + offset; i++) {
    if (__sm_get_chunk_offset(map, idx) != -1) {
      return QCC_FAIL;
    }
  }

  // By setting the first bit in each of rnd_nvec chunks we create one chunk
  // per and with exactly one additional bitvec per so we should observe...
  for (int i = 0; i < rnd_nvec; i++) {
    sparsemap_idx_t l = offset + (i * SM_CHUNK_MAX_CAPACITY);
    sparsemap_set(map, l);
  }
  for (int i = 0; i < rnd_nvec; i++) {
    size_t expected_offset = __sm_get_chunk_offset(map, offset + (i * SM_CHUNK_MAX_CAPACITY));
    size_t calculated_offset = i * (SM_SIZEOF_OVERHEAD + (sizeof(__sm_bitvec_t) * 2));
    if (calculated_offset != expected_offset) {
      return QCC_FAIL;
    }
  }

  // Now for RLE, first let's clear and check a full chunk.
  sparsemap_clear(map);
  for (int i = 0; i < SM_CHUNK_MAX_CAPACITY; i++) {
    sparsemap_set(map, i);
  }
  for (int i = 0; i < SM_CHUNK_MAX_CAPACITY; i++) {
    if (__sm_get_chunk_offset(map, i) != 0) {
      return QCC_FAIL;
    }
  }
  if (__sm_get_chunk_offset(map, SM_CHUNK_MAX_CAPACITY) != 0) {
    return QCC_FAIL;
  }

  // This should trigger the transformation of the 0th chunk into RLE.
  sparsemap_set(map, SM_CHUNK_MAX_CAPACITY);
  if (__sm_get_chunk_offset(map, SM_CHUNK_MAX_CAPACITY) != 0) {
    return QCC_FAIL;
  }
  // This should trigger the transformation of the 0th chunk back to sparse.
  sparsemap_unset(map, SM_CHUNK_MAX_CAPACITY);
  if (__sm_get_chunk_offset(map, SM_CHUNK_MAX_CAPACITY) != 0) {
    return QCC_FAIL;
  }

  // This should trigger the transformation of the 0th chunk into RLE again.
  for (int i = 0; i < 3000; i++) {
    sparsemap_set(map, SM_CHUNK_MAX_CAPACITY + i);
  }
  // This should trigger the transformation of the 0th chunk back to sparse,
  // but also create a second and third sparse chunks.
  sparsemap_unset(map, 0);
  if (__sm_get_chunk_offset(map, 0) != 0) {
    return QCC_FAIL;
  }
  sparsemap_set(map, 0);

  // This will split the chunk into two chunks; sparse, RLE.
  sparsemap_unset(map, 129);
  if (__sm_get_chunk_offset(map, 129) != 0) {
    return QCC_FAIL;
  }
  sparsemap_set(map, 129);

  // This will split the chunk into three chunks; sparse, sparse, RLE.
  sparsemap_unset(map, 2050);
  if (__sm_get_chunk_offset(map, 0) != 0) {
    return QCC_FAIL;
  }
  if (__sm_get_chunk_offset(map, 2050) != SM_SIZEOF_OVERHEAD + sizeof(__sm_bitvec_t)) {
    return QCC_FAIL;
  }
  if (__sm_get_chunk_offset(map, 2050 + SM_CHUNK_MAX_CAPACITY) != 2 * SM_SIZEOF_OVERHEAD + 3 * sizeof(__sm_bitvec_t)) {
    return QCC_FAIL;
  }
  sparsemap_set(map, 2050);

  // This won't split the chunk, it just shrinks the RLE by one.
  sparsemap_unset(map, 5047);
  if (__sm_get_chunk_offset(map, 5046) != 0) {
    return QCC_FAIL;
  }

  // This will split the chunk, the index is outside the range but inside the capacity.
  sparsemap_set(map, 5048);
  if (__sm_get_chunk_offset(map, 4090) != 0) {
    return QCC_FAIL;
  }
  if (__sm_get_chunk_offset(map, 5046) != 12) {
    return QCC_FAIL;
  }

  sparsemap_unset(map, 5048);
  if (__sm_get_chunk_offset(map, 5046) != 0) {
    return QCC_FAIL;
  }

  return QCC_OK;
}

#endif