Re: search algorithm



fenwayfool said:

I need to create a database that has a fairly long key. Consider
the key a bitstring. My problem is that this key also has an
associated mask. All bits that we "care" about in the key have a
mask value of '1' while the don't care bits are marked with a
zero.

[...]

For example let's assume the key/mask is 32 bits. If I have the
following in my database:


key: 0xA0A000001

(I'm guessing this was supposed to be 0xA0A00001)

mask: 0xFFFF000F


Should match a key such as 0xA0A00007 (the lookup does not specify
a key).

Here's your example in binary:

key: 1010 1010 0000 0000 0000 0000 0000 0001
mask: 1111 1111 1111 1111 0000 0000 0000 1111

I'm guessing that you mean by this that any match for the search key
must look like this:

1010 1010 0000 0000 xxxx xxxx xxxx 0001

where x indicates "any bit value will do for this position".

But your indicated match has the pattern

1010 1010 0000 0000 0000 0000 0000 0111

which does NOT match the required bit pattern (two mandatory bits
are different).

So I'm puzzled as to whether I have understood your requirements
correctly.

Anyway, this whole question smacks very much of secondary analysis.
"I have a problem X. Ah! I have thought of a solution Y. Oh! I have
a problem Z with solution Y. Hm! How can I solve Z?" whereas
perhaps you ought really to be asking "How can I best solve X?"

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
.