Chapter 35. Hierarchical container template

Index

Locks
Reader locks
Writer locks
Shortcuts
Key iterators
Output of the example program

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<T> where T is any class that can be used as an associative container key. The values are arranged in a hierarchical tree so, if for example the key is an int, 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:

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 : public x::obj {

public:
	booksObj() {}
	~booksObj() noexcept {}

	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;
}

Locks

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.

Note

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: