Re: stop searching

On Sat, 24 Aug 2002, Gustavo Vieira Gonçalves Coelho Rios wrote:

> In a linear probing scheme, how may i determine is time to stop
> searching for a key?
> That's to say: a table with k slots size and all them fullfilled!

If you've searched all 'k' slots and not found the key, then it's not
there. :)

If you're referring specifically to cdb, http://cr.yp.to/cdb/cdb.txt
says:

  Probe that slot, the next higher slot, and so on, until
  you find the record or run into an empty slot.

So if there is a gap in the table, you know to stop searching. I don't
know if Dan also adds a sentinel slot at the end of the table that is
empty (since you already know the table size and can avoid exceeding
it). I'd have to look at the code to be sure.

-Peff