Differential D9870 Diff 29387 src/radix.h

Changeset View

Standalone View

src/radix.h

	Show All 25 Lines
	*			*
	* Reads walk the tree using sequential atomic loads, and insertions are done			* Reads walk the tree using sequential atomic loads, and insertions are done
	* using CAS, which ensures both can be executed lock free. Removing any			* using CAS, which ensures both can be executed lock free. Removing any
	* elements from the tree can also be done using CAS, but requires waiting for			* elements from the tree can also be done using CAS, but requires waiting for
	* other readers before being destroyed. The tree uses RCU to track which thread			* other readers before being destroyed. The tree uses RCU to track which thread
	* is reading the tree, which allows deletion to wait for other readers to be up			* is reading the tree, which allows deletion to wait for other readers to be up
	* to speed before destroying anything. It is therefore crucial that the lock be			* to speed before destroying anything. It is therefore crucial that the lock be
	* taken before reading anything in the tree.			* taken before reading anything in the tree.
	*
	* It is not possible to delete anything from the tree at this time. The tree
	* itself cannot be destroyed and will leak memory instead of cleaning up after
	* itself. This obviously needs to be fixed in subsequent revisions.
	*/			*/
	template <typename T> struct RadixTree {			template <typename T> struct RadixTree {
	private:			private:
	static const int BITS = 4;			static const int BITS = 4;
	static const int MASK = (1 << BITS) - 1;			static const int MASK = (1 << BITS) - 1;
	static const size_t CHILD_PER_LEVEL = 1 << BITS;			static const size_t CHILD_PER_LEVEL = 1 << BITS;

	typedef typename std::remove_reference<decltype(			using K = typename std::remove_reference<decltype(
	std::declval<T &>().getId())>::type K;			std::declval<T &>().getId())>::type;
	static const size_t KEY_BITS = 8 * sizeof(K);			static const size_t KEY_BITS = 8 * sizeof(K);
	static const uint32_t TOP_LEVEL = (KEY_BITS - 1) / BITS;			static const uint32_t TOP_LEVEL = (KEY_BITS - 1) / BITS;

	struct RadixElement;			struct RadixElement;
	struct RadixNode;			struct RadixNode;

	std::atomic<RadixElement> root;			std::atomic<RadixElement> root;

	▲ Show 20 Lines • Show All 235 Lines • Show Last 20 Lines