3
\$\begingroup\$

This code has been developed with help on Stack Overflow. It is designed to compare two XML files and print the node for any differences (i.e if a entry appears in A.xml and not B.xml and vice versa).

#include "pugixml.hpp"

#include <iostream>
#include <unordered_map>

struct string_hasher
{
    unsigned int operator()(const char* str) const
    {
        // Jenkins one-at-a-time hash (http://en.wikipedia.org/wiki/Jenkins_hash_function#one-at-a-time)
        unsigned int result = 0;

        while (*str)
        {
            result += static_cast<unsigned int>(*str++);
            result += result << 10;
            result ^= result >> 6;
        }

        result += result << 3;
        result ^= result >> 11;
        result += result << 15;

        return result;
    }

    bool operator()(const char* lhs, const char* rhs) const
    {
        return strcmp(lhs, rhs) == 0;
    }
};

typedef std::unordered_map<const char*, pugi::xml_node, string_hasher, string_hasher> xml_node_map;

int main()
{
    pugi::xml_document doca, docb;
    xml_node_map mapa, mapb;

    if (!doca.load_file("a.xml") || !docb.load_file("b.xml"))
        return 1;

    for (auto& node: doca.child("site_entries").children("entry"))
        mapa[node.child_value("id")] = node;

    for (auto& node: docb.child("site_entries").children("entry"))
        mapb[node.child_value("id")] = node;

    for (auto& ea: mapa)
        if (mapb.count(ea.first) == 0)
        {
            std::cout << "Removed:" << std::endl;
            ea.second.print(std::cout);
        }

    for (auto& eb: mapb)
        if (mapa.count(eb.first) == 0)
        {
            std::cout << "Added:" << std::endl;
            eb.second.print(std::cout);
        }
}

I was wondering if I could get some feedback on how it is designed, most notably if this is the optimal approach in terms of performance, since this has to sort hundreds of thousands of entries.

Example XML file:

<entry> <id><![CDATA[90007316]]></id> <url>< [CDATA[http://www.site.co.uk/cgi-bin/tr.cgi?tid=70952276]]></url> <content><![CDATA[Giant Sport Offroad Bike]]></content> <title><![CDATA[Bike]]></title> <price><![CDATA[£100]]></price> <date><![CDATA[11-AUG-15]]></date> <display_reference><![CDATA[2146433-50142933_370647]]></display_reference> <location><![CDATA[City of London]]></location> <category><![CDATA[Bike]]></category> </entry>
\$\endgroup\$
4
\$\begingroup\$

Your code is somewhat simplistic in that all it is doing is ensuring that the same id values appear in each document. XML is a lot more complicated than that, though, and you may have problems when:

  1. you have multiple entries with the same id
  2. you have entries without an id
  3. the content in entries with the same ID in different documents is wildly different.

In terms of the algorithm, the code is clear, and so on. The string_hasher logic concerns me a bit simply because I am not that familiar with C++ (I am more familiar with XML)..... but, I have the following concerns there:

  1. Why return int for the hash? It is specified to return size_t.
  2. why have the struct at all?

If you convert the const char* ID to be a std::string then you can just make it a map of std::string and use the default values for the hashing and equalities in the template.

Funally, as a small optimization, you can probably save half your memory if you us a 'subtraction' type algorithm for comparing the document structures. Consider )note, I always use braces for code blocks, even if they have just one line):

for (auto& node: doca.child("site_entries").children("entry")) {
    mapa[node.child_value("id")] = node;
}

Then, in the next loop, do the following instead:

for (auto& node: docb.child("site_entries").children("entry")) {
    const char* nid = node.child_value("id");
    if (!mapa.erase(nid)) {
        mapb[nid] = node;
    }
}

Now, at this point, there is no need to perform an intersection on the maps... the values in mapa we know ae not in mapb, and visa versa. You can just print the contents of the two maps without any further processing...

Putting all these suggestions together, your code would look something like:

int main() {
    pugi::xml_document doca, docb;
    std::map<string, pugi::xml_node> mapa, mapb;

    if (!doca.load_file("a.xml") || !docb.load_file("b.xml"))
        return 1;

    for (auto& node: doca.child("site_entries").children("entry")) {
        const char* id = node.child_value("id");
        mapa[new std::string(id, strlen(id))] = node;
    }

    for (auto& node: docb.child("site_entries").children("entry"))
        const char* idcs = node.child_value("id");
        std::string id = new std::string(idcs, strlen(idcs));
        if (!mapa.erase(id)) {
            mapb[id] = node;
        }
    }

    for (auto& ea: mapa) {
        std::cout << "Removed:" << std::endl;
        ea.second.print(std::cout);
    }

    for (auto& eb: mapb) {
        std::cout << "Added:" << std::endl;
        eb.second.print(std::cout);
    }

}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you so much for your feedback. I'll build on this based on your advice \$\endgroup\$ – Jimmy Apr 15 '15 at 12:34
  • \$\begingroup\$ Sorry to be a pain, but I don't understand how to print the two maps after your suggestion, would you please be kind enough to give me a push in the right direction. \$\endgroup\$ – Jimmy Apr 15 '15 at 19:18
  • 1
    \$\begingroup\$ @Jimmy - after adding all the doca-nodes to mapa, you then iterate docb-nodes, and, if they exist in mapa, remove them, from mapa. If they do not exist in mapa, add them to mapb. At the end of that, all existing nodes in mapa are ones that are in doca-only, and all nodes in mapb are in docb only. So all you need do is iterate the keys of mapa, and print "Removed", and the keys of mapb, and print "Added". The same way you are currently doing it, but without the if-condition in the loop. \$\endgroup\$ – rolfl Apr 15 '15 at 19:24
  • 1
    \$\begingroup\$ See the edit, @Jimmy \$\endgroup\$ – rolfl Apr 15 '15 at 19:38
  • 1
    \$\begingroup\$ That's brilliant, completely negated the requirement for the string_hasher. Really good, I really appreciate it. \$\endgroup\$ – Jimmy Apr 15 '15 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.