title: Why does a GDB watchpoint stop on an irrelevant line when swapping binary tree nodes?
body: <p>I am trying to swap two nodes <code>A</code> and <code>B</code> in a binary tree so that the places they are actually stored in memory change but the tree topology is not changed.  I added special handling for swapping a node with its parent, but it still seems that it doesn't work.  I'm using Valgrind with vgdb so that I can catch memory errors and also get consistent addresses.  If I have a tree like</p>
  
  <pre><code>78
    \
     40
    /  \
  5c   c5
  </code></pre>
  
  <p>And then I try to swap <code>A=40</code> and <code>B=5c</code>, the links get messed up.  Specifically, <code>40-&gt;right</code>.  Setting a watchpoint on it (<code>watch -l</code>), I found that <code>40-&gt;right</code> is being set to <code>5c-&gt;right</code> (<code>NULL</code>) by <code>memcpy</code> as it should be, but then also that it is being changed to <code>A</code> later by <code>if(a_l.left == b){</code> which is clearly impossible.  I've had a watchpoint report the wrong line like this before when I was using <code>movq</code> instead of <code>movb</code> in assembly, but I'm pretty sure I have the sizes right this time because I didn't at first and it didn't make it through any swaps but I fixed it and now it makes it through around a dozen.  I sanity check the tree after every operation so the error is here.  Here is the simplest demonstration I could manage:</p>
  
  <pre><code>#include &lt;stdlib.h&gt;
  #include &lt;string.h&gt;
  #include &lt;assert.h&gt;
  
  typedef struct avl_node avl_node;
  struct avl_node{
      avl_node *left, *right, *parent;
      signed char balance;
      char data[];
  };
  
  avl_node *avl_root(avl_node *n){
      while(n &amp;&amp; n-&gt;parent){
          n = n-&gt;parent;
      }
      return n;
  }
  
  inline static int avl_check_links(avl_node *n){
      if(!n)return 1;
      if(n-&gt;left){
          if(n-&gt;left-&gt;parent != n){
              return 0;
          }
          if(!avl_check_links(n-&gt;left)){
              return 0;
          }
      }
      if(n-&gt;right){
          if(n-&gt;right-&gt;parent != n){
              return 0;
          }
          if(!avl_check_links(n-&gt;right)){
              return 0;
          }
      }
      return 1;
  }
  
  void avl_swap_nodes(avl_node *a, avl_node *b, size_t size){
      avl_node a_l = *a, b_l = *b;
      char tmp[sizeof(avl_node) + size];
      memcpy(tmp, a, sizeof(avl_node) + size);
      memcpy(a, b, sizeof(avl_node) + size);
      memcpy(b, tmp, sizeof(avl_node) + size);
      if(a_l.left){
          a_l.left-&gt;parent = b;
      }
      if(a_l.right){
          a_l.right-&gt;parent = b;
      }
      if(b_l.left){
          b_l.left-&gt;parent = a;
      }
      if(b_l.right){
          b_l.right-&gt;parent = a;
      }
      if(a_l.parent){
          if(a_l.parent-&gt;left == a){
              a_l.parent-&gt;left = b;
          }else{
              a_l.parent-&gt;right = b;
          }
      }
      if(b_l.parent){
          if(b_l.parent-&gt;left == b){
              b_l.parent-&gt;left = a;
          }else{
              b_l.parent-&gt;right = a;
          }
      }
      if(a_l.parent == b){
          if(b_l.left == a){
              b-&gt;left = a_l.left;
              a-&gt;left = b;
          }else{
              b-&gt;right = a_l.right;
              a-&gt;right = b;
          }
          a-&gt;parent = b_l.parent;
          b-&gt;parent = a;
      }else if(b_l.parent == a){//GDB stops here on a watch -l a-&gt;right
          if(a_l.left == b){
              a-&gt;left = b_l.left;
              b-&gt;left = a;
          }else{
              a-&gt;right = b_l.right;
              b-&gt;right = a;
          }
          b-&gt;parent = a_l.parent;
          a-&gt;parent = b;
      }
      assert(avl_check_links(avl_root(a)));
      assert(avl_check_links(avl_root(b)));
  }
  
  int main(void){
      avl_node a, b, c, d;
      a = (avl_node){.right=&amp;b};
      b = (avl_node){.left=&amp;c, .right=&amp;d, .parent=&amp;a};
      c = (avl_node){.parent=&amp;b};
      d = (avl_node){.parent=&amp;b};
      assert(avl_check_links(avl_root(&amp;a)));
      avl_swap_nodes(&amp;b, &amp;c, 0);
  }
  </code></pre>
  
  <p>Why does GDB stop on the wrong line?  I think it may have to do with the fact that I am using vgdb: it also skips some lines when I single step.  Also why is <code>a-&gt;right</code> changed a second time at all?  Thank you.</p>
  
  <p>You can get this file to run with reasonably recent versions of gcc, gdb, and valgrind by doing <code>gcc -g -o main main.c</code>, <code>valgrind --vgdb=yes --vgdb-error=0 ./main&amp;</code>, <code>gdb main</code>, <code>tar rem | vgdb</code>, <code>b avl_swap_nodes</code>, <code>c</code>, <code>watch -l a-&gt;right</code>, and then get rid of the vgdb process neatly by doing <code>c</code> repeatedly and then <code>Ctrl-d</code> or <code>kill</code> and then <code>Ctrl-d</code>.</p>