Re: search algorithm



fenwayfool <peterson.russell@xxxxxxxxx> writes:

On Jan 6, 7:02 pm, Patricia Shanahan <p...@xxxxxxx> wrote:
fenwayfool wrote:
Anyone ever do something similar to the following (in C++ or some
other language)...

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.

Basically I want to simulate the operation of a ternary CAM in
software in a semi efficient manner.  I have a few other databases I
use a hash_map<> for which works just fine... but the introduction of
a "don't care" mask eliminates this as a possibility.

Is the mask fixed for a given item in the database, or subject to change
from search to search?

Patricia

The mask is fixed for any given database entry... but each entry may
have a different mask.

And what about the queries?

--
__Pascal Bourguignon__
.



Relevant Pages

  • Re: search algorithm
    ... I need to create a database that has a fairly long key. ... mask. ... '1' while the don't care bits are marked with a zero. ... A search solution that returns more than 1 match is possible.... ...
    (comp.programming)
  • Re: search algorithm
    ... I need to create a database that has a fairly long key. ... 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)
  • search algorithm
    ... I need to create a database that has a fairly long key. ... 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. ... A search solution that returns more than 1 match is possible.... ...
    (comp.programming)
  • Re: search algorithm
    ... I need to create a database that has a fairly long key. ... mask. ... '1' while the don't care bits are marked with a zero. ... There are database systems that have bit indexes: ...
    (comp.programming)
  • [PATCH 3/4] dnotify: do not bother to lock entry->lock when reading mask
    ... manipulating it. ... In dnotify_should_send_eventwe don't care if we get an ... old or a new mask value out of this entry so there is no point it taking ...
    (Linux-Kernel)