int index_query::update_after_collision()

in src/index_query.h [214:321]

• 77 lines of code
• 12 McCabe index (conditional complexity)

int index_query::update_after_collision(file_stream &index, int new_num,
                                        const binary_sha1 &existing_sha1,
                                        int existing_num) const {
  // add subtrie(s) with full contents so far
  // TODO: add test that covers this.
  int first_mismatched_bit = in.sha1.get_mismatched_bit(existing_sha1);
  assert(first_mismatched_bit < 160);
  int num_bits_so_far = this->num_bits_so_far();
  assert(first_mismatched_bit >= num_bits_so_far - num_subtrie_bits);

  // Make new subtries.
  struct trie_update_stack {
    bool skip_bitmap_update = false;
    bitmap_ref bits;

    int entry_offset = 0;
    bool is_data = false;
    int num = 0;
  };

  if (index.seek_end())
    return error("could not seek to end to discover num subtries");
  int end_offset = index.tell();
  int next_subtrie =
      end_offset <= subtrie_indexes_offset
          ? 0
          : 1 + (end_offset - subtrie_indexes_offset - 1) / subtrie_index_size;

  // Update index in reverse, so that if this gets aborted early (or killed)
  // the output file has no semantic changes.
  trie_update_stack stack[160 / num_subtrie_bits + 2];
  trie_update_stack *top = stack;

  // Start with updating the existing trie that is pointing at the conflicting
  // commit.  Note that the bitmap is already set, we just need to make it
  // point at the right place.
  top->skip_bitmap_update = true;
  top->entry_offset = out.entry_offset;
  top->num = next_subtrie++;

  // Add some variables that need to last past the while loop.
  int subtrie_offset, bitmap_offset;
  int n, n_entry_offset;
  int f, f_entry_offset;
  while (true) {
    // Calculate the entries for the next subtrie.
    subtrie_offset = subtrie_indexes_offset + top->num * subtrie_index_size;
    bitmap_offset = subtrie_offset + subtrie_index_bitmap_offset;
    n = in.sha1.get_bits(num_bits_so_far, num_subtrie_bits);
    f = existing_sha1.get_bits(num_bits_so_far, num_subtrie_bits);
    n_entry_offset =
        subtrie_offset + subtrie_index_entries_offset + n * index_entry::size;
    f_entry_offset =
        subtrie_offset + subtrie_index_entries_offset + f * index_entry::size;

    if (n != f)
      break;

    // push another subtrie.
    num_bits_so_far += num_subtrie_bits;

    ++top;
    top->num = next_subtrie++;
    top->entry_offset = n_entry_offset;
    top->bits.initialize_and_set(bitmap_offset, n);
    assert(top->bits.byte);
  }

  // found a difference.  add commit entries to last subtrie.
  ++top;
  top->is_data = true;
  top->num = existing_num;
  top->entry_offset = f_entry_offset;
  top->bits.initialize_and_set(bitmap_offset, f);
  assert(top->bits.byte);

  ++top;
  top->is_data = true;
  top->num = new_num;
  top->entry_offset = n_entry_offset;
  top->bits.initialize_and_set(bitmap_offset, n);
  top->skip_bitmap_update = top[-1].bits.byte_offset == top->bits.byte_offset;
  assert(top->bits.byte);
  if (top->skip_bitmap_update)
    top[-1].bits.byte |= top->bits.byte;

  // Unwind the stack.  Be careful not to decrement top past the beginning.
  ++top;
  while (top != stack) {
    --top;

    // Update the index entry.
    index_entry entry(top->is_data, top->num);
    if (index.seek(top->entry_offset) ||
        index.write(entry.bytes, index_entry::size) != index_entry::size)
      return error("could not write index entry");

    if (top->skip_bitmap_update)
      continue;

    // Update the bitmap to point at the index entry.
    if (index.seek(top->bits.byte_offset) ||
        index.write(&top->bits.byte, 1) != 1)
      return error("could not write to index bitmap");
  }

  return 0;
}