Re: [DynInst_API:] Bugs in IBSTree.h?

[Bill Williams <bill@xxxxxxxxxxx>]

...you're not wrong; I guess we created begin()/end() and never used them.

Your fix is also incorrect; the loop should be while(x->dir) x=x->dir for both directions. Root should not be touched after b and e are initialized.

--bw

________________________________________
From: Dyninst-api <dyninst-api-bounces@xxxxxxxxxxx> on behalf of John Mellor-Crummey <johnmc@xxxxxxxx>
Sent: Saturday, November 25, 2017 4:52 PM
To: dyninst-api@xxxxxxxxxxx
Subject: [DynInst_API:] Bugs in IBSTree.h?

The code below comes from IBSTree.h in master (https://github.com/dyninst/dyninst/blob/master/common/h/IBSTree.h), though it is similar in the new-parallel-parsing branch.

I don’t see how it could be right. When an IBSTree is non-empty, root is non-null.

Problem 1: This code would blow up with an empty root as it would try to dereference root in the test for the while loop.

Problem 2: As I read it, the test for the while loops are not affected by the assignments in their loop bodies. How is the first while not an infinite loop if right->left is non-NULL? Similarly, how is the second while not an infinite loop if root->right is non-NULL.

const_iterator begin() const {
       iterator b = root;
       while(root->left) b = root->left;
       return b;
}
const_iterator end() const {
       iterator e = root;
       while(root->right) e = root->right;
       return e;
}

Shouldn’t the code read:

const_iterator begin() const {
       iterator b = root;
       while(b->left) b = root->left;
       return b;
}
const_iterator end() const {
       iterator e = root;
       while(e->right) e = root->right;
       return e;
}

--
John Mellor-Crummey Professor
Dept of Computer Science Rice University
email: johnmc@xxxxxxxx<mailto:johnmc@xxxxxxxx> phone: 713-348-5179