bitmap-rle-union.c

struct tw_bitmap_rle *
tw_bitmap_rle_union(const struct tw_bitmap_rle *a,
                    const struct tw_bitmap_rle *b,
                          struct tw_bitmap_rle *dst)
{
  assert(a && b && dst);

  const uint32_t size = a->info.size;
  if (size != b->info.size && size != dst->info.size) {
    return NULL;
  }
  tw_bitmap_rle_zero(dst);

  const uint32_t a_pos = a->cur_word, b_pos = b->cur_word;
  uint32_t a_idx = 0, b_idx = 0;

  while (a_idx <= a_pos && b_idx <= b_pos) {
    struct tw_bitmap_rle_word a_word = a->data[a_idx], b_word = b->data[b_idx];

    /** Settle ordering between a and b. */
    uint32_t *min_idx = (a_word.pos <= b_word.pos) ? &a_idx : &b_idx;
    uint32_t *max_idx = (a_word.pos <= b_word.pos) ? &b_idx : &a_idx;
    struct tw_bitmap_rle_word *min_word =
      tw_bitmap_rle_word_first_ref(a_word, b_word);
    struct tw_bitmap_rle_word *max_word =
      tw_bitmap_rle_word_second_ref(a_word, b_word);

    const uint32_t start = min_word->pos;
          uint32_t end   = tw_bitmap_rle_word_end((*min_word));
    if (tw_bitmap_rle_words_intersect(a_word, b_word)) {
      /** advance embedded words until not contained. */
      while (tw_bitmap_rle_word_end((*max_word)) <
             tw_bitmap_rle_word_end((*min_word))) {
        ++(*max_idx);
      }
      /** max_word might still be overlap with min_word */
      if (tw_bitmap_rle_words_intersect((*min_word),(*max_word))) {
        end = tw_bitmap_rle_word_end((*max_word));
        ++(*max_idx);
      }
    }
    tw_bitmap_rle_set_range(dst, start, end);

    ++(*min_idx);
  }

  return dst;
}