[Caml-list] Hashing failure

[Thomas Braibant <thomas.braibant@gmail.com>]

Hi list,

I have a piece of code that looks like this.

let hkey = H.hash d in (* a custom hash function *)
let index = hkey mod (Array.length t.table) in
let bucket = t.table.(index) in (* 1 *)

the line marked with 1 was generating an index out of bounds
exception. It appeared that it was because index was negative, a
problem  I knew of when using mod ... So I added an abs around index

let hkey = H.hash d in
let index =  abs (hkey mod (Array.length t.table)) in
let bucket = t.table.(index) in (* 1 *)

But it yields the same exception...

This seemed completely unbelievable, till I realized that
- x mod y may return a negative value if x is less than 0
- abs x may return a negative value if x is min_int

So I tried to reproduce this behavior with the following code:

let t = Array.create 17 0;;
let hkey = min_int in
let index = (abs hkey) mod (Array.length t) in
t.(index);;

which yields an out of bound. Bingo. It turns out that some value of
the length of t will result in an error, and some will not (e.g., 16) ... My
question is : is there a safe way to bullet-proof my code against
these pathological cases, without too much hinderance (this is some
code whose efficiency is critical...)


Thomas