samedi 5 juin 2021

Boolean expression evaluator on struct members

Background

I have a struct:

struct event {
    uint16_t id;
    uint8_t type;
    std::string name;
    // many more fields (either string or integer types)
};

A boolean expression:

name = "xyz" and (id = 10 or type = 5)

I have a vector of event objects(thousands) std::vector<event> and want to check if they satisfy the boolean expression.

Things I have implemented so far

  • I implemented a tokenizer and a recursive descent parser to convert the boolean expressions to an AST.
  • Store the terminals as a std::pair<std::string, std::string>, where the first value is the struct field name and second is the value. For example, std::pair<"name", "acbd">
  • I walk through the tree and whenever it sees a terminal tree node:
bool match(const event& ev, const ast::node& node)
{
}

Questions

The struct contains 10 members. I want to avoid the unnecessary comparisons. In the worst case, an AST terminal node (for example, pair<"type", "5000">) might result in 10 comparisons.

I tried constructing this lookup map:

std::map<std::string, std::size_t> fields;

fields["name"] = offsetof(event, name);
fields["id"] = offsetof(event, id);
fields["type"] = offsetof(event, type);

Using this map, I can simplify match() to:

bool match(const event& ev, const ast::node& node) {
    const auto offset = fields[node.first];
    return ((ev + offset) == node.second); // DOESN'T WORK
}
  1. I can access the struct member at an offset using (eventObj + offset). How do I convert it to the correct data type for the comparison to work?

  2. For now, all the field values in AST terminal nodes are std::string. How do I convert it to the correct type during tokenizer or parsing step? I can store the AST node as std::pair<std::string, std::any> but still need the type information for std::any_cast.

Both of these can be solved if I can somehow store the type information in the fields map. I am not sure how.





Aucun commentaire:

Enregistrer un commentaire