On Mon, Mar 01, 2004 at 12:14:41PM -0000, Ted Harding wrote:
On 01-Mar-04 Chris Green wrote:
I have a little 68000 assembler project I'm doing for someone (paid!) and basically it consists of replacing a 'built on the fly' look-up table with a ready made one which is uploaded with the code. [...] 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.
As a general rule, btree indexing gives efficient look-up; but your description suggests this may be "messy" to set up.
I have another idea, which I need to look into the properties of before deciding whether it's a good idea or a bad one for your application.
That's really (reading below as well) a sort of hash table isn't it, using the first byte of the IP address as the hash key.
[snip]
The issue I need to look into is how much space would be required to store this tree (and also how efficient and/or messy it would be to implement it). Given that the number of actual entries you need to store is about 400, you should not need anything like the superficially apparent 2^32 nodes in total. Only the 400 would lead all the way down to level-4, and all the others would run into a dead end at a higher level. Probably you only need a thousand or two nodes in all to store the tree for 400 level-4 nodes.
As I say, I'll try to look into what this leads to for 400. But you may be interested in the idea.
It's certainly a possibility.
Isn't the worst case where every possible first byte value is present, this gives 256 top level (first byte) pointers (not really possible as some first byte values aren't allowed) so there are 256 * 256 * 4 bytes at the second level. Even that sounds a bit big without going any further. It would also need code to generate it as one certainly isn't going to upload it in that format.
The advantage of a binary chop is that it is quite possible to generate the table in assembler, it's just a matter of finding some way to sort it, preferably pre-assembler.