Impossible conditional statement-CodePudding

bool flag = ((idx == n) ? true : false);

if (C[idx]->n < t)
    fill(idx);

if (flag && idx > n)
    C[idx - 1]->deletion(k);

The above code snippet is part of the BTree implementation, I searched everywhere but I can't find will the second if-statement will ever be executed?

The flag will only be true when the idx == n, Right? and the if statement will execute only if idx > n and flag = true, which is impossible.

I think that the fill(idx) is changing value but I can't understand how? Someone explain

fill function

void BTreeNode::fill(int idx) {
  if (idx != 0 && C[idx - 1]->n >= t)
    borrowFromPrev(idx);

  else if (idx != n && C[idx   1]->n >= t)
    borrowFromNext(idx);

  else {
    if (idx != n)
      merge(idx);
    else
      merge(idx - 1);
  }
  return;
}

CodePudding user response：

After looking at the code from the link you provided, the variable idx is never changed. But, by going through fill(idx), n gets modified in certain cases (as it's an attribute, and as fill is a method that have access to n). So the second if statement can be triggered in some cases, when n is modified by fill or one of the methods called by fill.

The code:

fill(idx):

void BTreeNode::fill(int idx) {
  if (idx != 0 && C[idx - 1]->n >= t)
    borrowFromPrev(idx);

  else if (idx != n && C[idx   1]->n >= t)
    borrowFromNext(idx);

  else {
    if (idx != n)
      merge(idx);
    else
      merge(idx - 1);
  }
  return;
}

It can call borrowFromPrev, borrowFromNext or merge, which functions can change n in some cases:

// Borrow from previous
void BTreeNode::borrowFromPrev(int idx) {
  BTreeNode *child = C[idx];
  BTreeNode *sibling = C[idx - 1];

  for (int i = child->n - 1; i >= 0; --i)
    child->keys[i   1] = child->keys[i];

  if (!child->leaf) {
    for (int i = child->n; i >= 0; --i)
      child->C[i   1] = child->C[i];
  }

  child->keys[0] = keys[idx - 1];

  if (!child->leaf)
    child->C[0] = sibling->C[sibling->n];

  keys[idx - 1] = sibling->keys[sibling->n - 1];


  child->n  = 1; // here
  sibling->n -= 1; // here

  return;
}

// Borrow from the next
void BTreeNode::borrowFromNext(int idx) {
  BTreeNode *child = C[idx];
  BTreeNode *sibling = C[idx   1];

  child->keys[(child->n)] = keys[idx];

  if (!(child->leaf))
    child->C[(child->n)   1] = sibling->C[0];

  keys[idx] = sibling->keys[0];

  for (int i = 1; i < sibling->n;   i)
    sibling->keys[i - 1] = sibling->keys[i];

  if (!sibling->leaf) {
    for (int i = 1; i <= sibling->n;   i)
      sibling->C[i - 1] = sibling->C[i];
  }

  child->n  = 1; // here
  sibling->n -= 1; // here

  return;
}

// Merge
void BTreeNode::merge(int idx) {
  BTreeNode *child = C[idx];
  BTreeNode *sibling = C[idx   1];

  child->keys[t - 1] = keys[idx];

  for (int i = 0; i < sibling->n;   i)
    child->keys[i   t] = sibling->keys[i];

  if (!child->leaf) {
    for (int i = 0; i <= sibling->n;   i)
      child->C[i   t] = sibling->C[i];
  }

  for (int i = idx   1; i < n;   i)
    keys[i - 1] = keys[i];

  for (int i = idx   2; i <= n;   i)
    C[i - 1] = C[i];

  child->n  = sibling->n   1; // here
  n--; // here

  delete (sibling);
  return;
}