ArrayBoundsError for associative array operation

[xs0]

Egor Starostin wrote:
>> Most likely you forgot to implement a function or two:
> 
> Sorry that I oversimplified posted testcase (throwed away opEquals
> and opCmp).
> 
> In my working code I have the following functions in struct
> definition:
> ***
>         int opEquals(SKey* s) {
>             return ((dep == s.dep) && (hv == s.hv));
>         }
>         int opCmp(SKey* s) {
>             if (dep == s.dep) {
>                 return cmp(hv,s.hv);
>             } else {
>                 return dep - s.dep;
>             }
>         }
> ***
> 
> 
> --
> Egor

Yes, I think it's a bug.. The reason it happens is the following:

1) all the nodes happen to fall into the same bucket in the AA
2) when that is the case, entries get placed into a binary tree
3) the ordering in the binary tree is determined by hashcodes first, 
opCmp second (in this case, opCmp can be ignored, as it isn't called at all)
4) after that node is deleted, the tree looks like this:
      root.hash        =  315901071
      root->right.hash = 2716102924
5) and, finally, the bug: in aaA.d around line 319, the following takes 
place:

      c = key_hash - e.hash;
      // snip
      if (c < 0)
          e = e.left;
      else
          e = e.right;

    because those two hash values are too far apart, c becomes negative 
(-1894765443) and the left subtree is followed instead of the right 
subtree, causing the key to not be found.


xs0