Tuesday, April 17, 2018

Boost Intrusive Set lookup function doesn't accept search key as object?

Would it be easier if I change the intrusive list to intrusive set? Okay, my initial goal is to capture the files into the memory, which is an intrusive list for my case, and then search through the list for each input entry. The input entry might go up 1000 items in total. Now the problem here is I had never decide what algorithm to use for the searching part. Then I come across the intrusive set does provide the API for me to work with, code sample below is my experiment on this:
class FileNode3;
typedef boost::intrusive::set<FileNode3, compare<std::greater<FileNode3> >, constant_time_size<false> > BaseSet;


class FileNode3 : public set_base_hook<link_mode<safe_link> > {
public:
    boost::filesystem::path root;
    boost::filesystem::path name;
    char type; // f is file, d is directory

    BaseSet sibling;

    FileNode3() {}
    FileNode3(boost::filesystem::path name_) : name(name_) {}
    FileNode3(boost::filesystem::path name_, const char type_) : name(name_), type(type_) {}

public:
    void setName(boost::filesystem::path name) { this->name = name; }
    void setRoot(boost::filesystem::path root) { this->root = root; }
    void setType(char type) { this->type= type; }

    friend bool operator< (const FileNode3 &a, const FileNode3 &b)
        {  return a.name.compare(b.name) < 0;  }

    friend bool operator> (const FileNode3 &a, const FileNode3 &b)
        {  return a.name.compare(b.name) > 0;  }

    friend bool operator== (const FileNode3 &a, const FileNode3 &b)
        {  return a.name.compare(b.name) == 0;  }
};

BOOST_AUTO_TEST_CASE(TL_IntrusiveSet, *boost::unit_test::precondition(skipTest(false)))
{
    struct FileNodeEqual
    {
        bool operator()(const char *search, const FileNode3 &node) const
        {
            cout << "StrEqual arg1: " << search << " " << node.name.c_str() << endl;

            return strcmp(search, node.name.c_str()) == 0 ? false : true;
        }

        bool operator()(const FileNode3 &node, const char *search) const
        {
            cout << "StrEqual arg2: " << search << " " << node.name.c_str() << endl;

            return strcmp(node.name.c_str(), search) == 0 ? false : true;
        }
    };

    BaseSet s1;

    FileNode3 fn3;
    fn3.name = "fileB";
    fn3.type = 'f';

    FileNode3 fn1;
    fn1.name = "path_A";
    fn1.type = 'd';
    fn1.sibling.push_back(fn3);

    FileNode3 fn2;
    fn2.type = 'f';
    fn2.name = "fileA";

    s1.insert(fn1);
    s1.insert(fn2);

    FileNode3 f;
    f.name = "fileB";
    f.type = 'd';

    boost::intrusive::set<FileNode3>::iterator it = s1.find(f.name.c_str(), FileNodeEqual());

    FileNode3 *n = (&*it);

    if( it == s1.end() ) {
        cout << "record not found" << endl;
    }
    else {
        FileNode3 *n = (&*it);
        cout << "record found: " << n->name << endl;
    }

    if( fn1.sibling.size() > 0 ) {
        cout << "fn1 sibling has more child: " << fn1.sibling.size() << endl;

        boost::intrusive::set<FileNode3>::iterator it = fn1.sibling.find(fn3);

        if( it == s1.end() ) {
            cout << "record not found" << endl;
        }
        else {
            FileNode3 *n = (&*it);
            cout << "record found: " << n->name << endl;
        }
    }

    s1.remove_node(fn1);
    s1.remove_node(fn2);
    s1.remove_node(fn3);

    cout << "Test 1 end!" << endl;
}
But that is one problem with this code, I can only compare the name property of this object. How can I compare the rest of the properties of the object? Why don't I just pass down the whole object and then do the comparison? Then I modify the FileNodeEqual struct as follows, the search key has become an FileNode3 instead of char*:
struct FileNodeEqual
    {
        bool operator()(const FileNode3 &search, const FileNode3 &node) const
        {
            cout << "StrEqual arg1: " << search.name.c_str() << " " << node.name.c_str() << endl;

            return true;
        }

        bool operator()(const FileNode3 &node, const FileNode3 &search) const
        {
            cout << "StrEqual arg2: " << search.name.c_str() << " " << node.name.c_str() << endl;

            return true;
        }
    };
Then the compiler will complain following error to me:
error: 'bool testlab::TL_IntrusiveSet::test_method()::FileNodeEqual2::operator()(const testlab::FileNode3&, const testlab::FileNode3&) const' cannot be overloaded
         bool operator()(const FileNode3 &node, const FileNode3 &search) const
              ^~~~~~~~
error: with 'bool testlab::TL_IntrusiveSet::test_method()::FileNodeEqual2::operator()(const testlab::FileNode3&, const testlab::FileNode3&) const'
         bool operator()(const FileNode3 &search, const FileNode3 &node) const
              ^~~~~~~~
I have tested with other primitive data types are working fine. Not sure whether this is due to the performance penalty when calling those functions, thus it was design not allow to take any expensive object?

No comments: