# Re: search algorithm

On Jan 6, 10:54 pm, Richard Heathfield <r...@xxxxxxxxxxxxxxx> wrote:
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)

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

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@
"Usenet is a strange place" - dmr 29 July 1999

You are correct. In my haste I did not get the example right.

No idea what secondary analysis is... but problem X is how to simulate
a TCAM in software and do it in a manner that does not involve brute
force... i.e. a linear search of key/mask (or maybe data/mask is more
correct?) values applied to a specified key that returns some
associated data on a match. The real application here is IP flow
identification in an embedded system.

For example, the key is a 5-tuple (IP source addr, IP dest addr,
source port, dest port, protocol). Each member of the tuple has an
associated mask... but I believe I can assume the mask is contiguous
something like 0x0f0f0f0f). I'm starting to think the easiest way to
do this might be to break this problem up. Maybe use 5 different
databases where the lookup result of 1 returns another database...
until the last lookup returns my result data? In that case, I think
this is just a longest prefix match problem... but I would love to
hear other, better solutions.

.

## Relevant Pages

• Re: search algorithm
... associated mask. ... All bits that we "care" about in the key have a ... I'm guessing that you mean by this that any match for the search key ... But your indicated match has the pattern ...
(comp.programming)
• Re: Where can I find the color format of source surface in DrvCopyBits function?
... Why do you care about the source? ... EngCopyBits(Dest = TemporarySurface, Source = DeviceSurface) ... aren't you specifying them in DEVINFO::hpalDefault ... But could you please explain more how to get the mask ...
(microsoft.public.development.device.drivers)
• Re: search algorithm
... fenwayfool writes: ... key a bitstring. ... 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. ...
(comp.programming)
• Re: assembler help!
... The mask *is* an operand. ... We don't have to care, ... For IBM-MAIN subscribe / signoff / archive access instructions, ... send email to listserv@xxxxxxxxxxx with the message: GET IBM-MAIN INFO ...
(bit.listserv.ibm-main)