The x::hier
template implements a container that uses a hierarchical key.
This means that, in general, a value's key in the container
is a std::list<
where T>Tint, then a key of
“{1,3}” might have inferior or child keys of
“{1,3,6}” or “{1,3,0}”; and it itself would be
the inferior to “{1}”. The distinguishing characteristics
of this container are:
Values for intermediate keys do not have to exist. The container can have a value for a key of “{1,3,6}” without having a value for the keys “{1,3}” or “{1}”.
If the container does not have a value for a particular key, there's an option to find the closest parent key with a value. If the container does not have a value for the key of “{1,3,6}”, the search finds the “{1,3}” key, if it has a value.
The container is thread-safe, with a readers/writer locking design pattern.
The x::hier
template defines an x::ref
to a reference-counted container object, together with the definitions for
x::hierptr,
x::const_hier, and
x::const_hierptr, according to the usual naming
convention.
The first template parameter specifies the hierarchical key element,
from which the container key gets constructed.
The container's key becomes
std::list<key>. The second template must be
an x::ref to a reference-counted object, which becomes the value stored in
the container. The values in the container must be x::refs.
The key element class can be any type that can be used for a key of an
associative container. The following example uses an
int for the key element, resulting in a
std::list<int> container key.
The values stored in the container are small reference-counted objects
with a std::set<std::string>:
#include <x/hier.H> #include <x/strtok.H> #include <iostream> #include <algorithm> #include <string> #include <sstream> #include <list> class booksObj : virtual public x::obj { public: booksObj() {} ~booksObj() {} std::set<std::string> names; }; typedef x::ref<booksObj> books; typedef x::hier<int, books> classindex; bool insert_book(const classindex &catalog, const std::list<int> &number, const std::string &name) { bool updated=true; catalog->insert([&] { auto newbooks=books::create(); newbooks->names.insert(name); return newbooks; }, number, [&] (books && existing_books) { updated=existing_books ->names.insert(name).second; return false; }); return updated; } std::list<int> tokey(const std::string &word) { std::list<std::string> words; x::strtok_str(word, " ./\t\r", words); std::list<int> key; for (const std::string &word:words) { std::istringstream i(word); int n=0; if ((i >> n).fail()) { key.clear(); break; } key.push_back(n); } if (key.empty()) std::cerr << "Invalid number" << std::endl; return key; } std::string fromkey(const std::list<int> &key) { std::ostringstream o; const char *sep=""; for (int n:key) { o << sep << n; sep="."; } return o.str(); } int main() { auto decimal_system=classindex::create(); std::string line; while ((std::cout << "> " << std::flush), !std::getline(std::cin, line).eof()) { std::list<std::string> words; x::strtok_str(line, " \t\r", words); if (words.empty()) continue; std::string cmd=words.front(); words.pop_front(); if (cmd == "add" && !words.empty()) { std::list<int> key=tokey(words.front()); if (key.empty()) continue; std::cout << "Title: " << std::flush; if (std::getline(std::cin, line).eof()) break; if (!insert_book(decimal_system, key, line)) std::cerr << "Already exists" << std::endl; continue; } if (cmd == "get" && !words.empty()) { std::list<int> key=tokey(words.front()); classindex::base::readlock lock= decimal_system->create_readlock(); if (!lock->to_child(key, true)) { std::cerr << "Not found" << std::endl; continue; } std::cout << "Found: " << fromkey(lock->name()) << std::endl; for (const auto &name:lock->entry()->names) { std::cout << " " << name << std::endl; } continue; } if (cmd == "del" && !words.empty()) { std::list<int> key=tokey(words.front()); if (key.empty()) continue; classindex::base::writelock lock= decimal_system->create_writelock(); if (!lock->to_child(key, false)) { std::cerr << "Not found" << std::endl; continue; } std::cout << "Found: " << fromkey(lock->name()) << std::endl; for (const auto &name:lock->entry()->names) { std::cout << " " << name << std::endl; } std::cout << "Delete? " << std::flush; if (std::getline(std::cin, line).eof()) break; words.clear(); x::strtok_str(line, " \t\r", words); if (words.empty()) continue; if (words.front().substr(0, 1) == "y") { lock->erase(); std::cout << "Removed" << std::endl; } continue; } if (cmd == "list") { for (const std::list<int> &key: *decimal_system) { std::cout << " " << fromkey(key) << std::endl; } continue; } } return 0; }
The two main methods of x::hier are
create_readlock() and
create_writelock(), that instantiate a
x::hier<key, value>::base::readlock and
x::hier<key, value>::base::writelock,
respectively. Other methods are generally convenience shortcuts that
instantiate the appropriate lock, perform the requested operation, and
release the lock. The previous example invokes
insert() which instantiates a writer lock,
invokes the lock's insert() method, then releases
the lock. These methods have a detailed description later.
Multiple reader locks can exist concurrently. They allow reading the
contents of the container. Only one writer lock can exist at a time,
blocking all other writer and reader locks. The writer lock does
everything that a reader lock does (except for
clone()),
and also implements methods that modify the container.
A writer lock is convertible to a reader lock, except that the resulting
reader lock also cannot do a clone() since it's
still an underlying writer lock.
The reader and writer locks are reference-counted objects, that can be freely passed around. The locks remain in existence as long as a reference to the lock remains. Although these locking constructs implement thread-safe container access, the locks themselves are not thread safe. Different threads use different locks to access the hierarchical container in a thread-safe manner, but only one thread can access an individual reader or a writer lock, at a time.
The scope of the reader and writer locks' thread safety is limited, of course, to thread-safe access to the values in the container. Since the values in the hierarchical container are reference-counted objects, a reference to a value in the container can remain in scope after the corresponding reader or a writer lock, used to access the value, goes out of scope. Any subsequent access to the container value is not protected by any lock, and must be done in a thread-safe manner.
In the example above, all access to the existing values in the container is protected by one of the locks.
Here's a typical output from running the above example program. The
key elements are ints, and the example program
contructs them from a dot-delimited string, forming a tree-like
hierarchy where, for example, “1.1” and
“1.2” keys would be inferior, child elements of
“1”. Note that the value for “1” does not have
to exist in the hierarchical container, in order for its inferior elements
to exist: