On Mon, Mar 01, 2004 at 06:11:20PM +0000, Richard Kettlewell wrote:
Chris Green chris@areti.co.uk writes:
The existing code uses a rather messy hash look-up and one of the reasons for the re-write is to make it simpler and more reliable.
A linear search of the table probably isn't a good idea as it would mean that there would be significant differences in look-up time for entries at the beginning and end of the table.
I'm leaning towards a binary-chop search but wondered if anyone had any other ideas. Binary-chop is easy in principle but it's often quite difficult to implement in practice because one has to deal with messy boundary conditions. It's also a bit more difficult to create the sorted table necessary automatically and relying on the creator of the table to sort it might be a bit dodgy.
The table looks up ATM addresses (16 bit values) given an IP address (32 bit values), maximum size is of the order of 400 entries.
Do you have enough control over the build process to mechanically ensure the table is sorted? Failing that is there any reason you can't sort the table at startup?
What do you think are the 'messy boundary conditions'?
I think I can ensure the table is sorted, the code will probably be generated from a non-assembler source in some sort of format so that processing can sort it as well.
The 'messy boundary conditions' are handling things like what to do when finding the middle of a table with an odd number of entries etc.