IdDictGroup::IdDictRegionTreeNode Struct Reference

Tree structure for fast unpacking. More...

Collaboration diagram for IdDictGroup::IdDictRegionTreeNode:

Public Types
using	ChildPair = std::pair< size_t, unsigned >
	References to child nodes. More...

Public Member Functions
	IdDictRegionTreeNode (const IdDictFieldImplementation &impl)
	Constructor, taking a reference to the implementation. More...
void	optimize ()
	Compress the vector of node indices, if they are all the same. More...

Public Attributes
const IdDictFieldImplementation &	m_impl
	Reference to the the implementation field. More...
std::unique_ptr< std::vector< const IdDictFieldImplementation * > >	m_other_impls
	Implementations for other field descriptions that this ored field of the identifier may contain. More...
std::variant< std::vector< unsigned >, ChildPair >	m_children

Static Public Attributes
static constexpr unsigned	END = static_cast<unsigned> (-1)
	Special value used to indicate that we've reached the end. More...

Detailed Description

Tree structure for fast unpacking.

A group is defined by a coherent list of regions; each region is a set of constrained fields. To unpack an Identifier into an ExpandedIdentifier, we notionally loop through the regions, try to match each in turn with the Identifier, filling in the ExpandedIdentifier, and then return it once we've matched all the fields. However, that entails a significant amount of redundant matching, and scales as O(nregions).

We can instead organize the regions into a tree structure, where we unpack each field exactly once, and use it's value to constrain the possibilities for the remaining fields. This removes the redundant unpacking, and scales as O(log(nregions)).

The tree is structured as vector of nodes. For each node in the tree, we save a reference to the IdDictFieldImplementation showing how to unpack that field. Then each node has a vector indexed by the index unpacked from the field giving the number of the next node to examine, or the special values END or 0. (To save a little memory, if all elements in this vector point at the same node, we can replace it with with a pair giving this value and the length of the vector.)

So, for example, suppose we have these regions:

3/1,3,5,6 -1,1/-4:4 0:31/0:31 0:63/0:63 3/1,3,5,6 -2,2/-4:4 0:7 /0:31 0:31/0:63 3/1,3,5,6 -2,2/-4:4 8:15/0:31 0:15/0:63

Notation: 3/1,3,5,6 - an enumerated field with possible values 1,3,5,6 that here must take value 3 (index 1). -2,2/-4:4 - a field that can store values from -4 to 4, that here must take values -2 or 2. 0:7 /0:31 - a field that can store values from 0 to 31, that here must take a value from 0 to 7.

We can represent these regions as a tree like this:

0 /1,3,5, 6 [0, 1, 0, 0] 1: /-4:4 [0, 0, 4, 2, 2, 4, 0 0] 2: /0:31 32*[3] 3: /0:63 64*[END] 4 /0:31 8*[5] + 8*[6] 5: /0:63 32*[END] 6: /0:63 16*[END]

The structure below defines the type of a node, and the nodes are stored in m_region_tree.

In addition, for a given identifier field, there may be multiple Range::field structures that it can contain. Normally this doesn't matter, but if we're unpacking to a string, then we need to find the proper field in order to get labels represented correctly. In most cases, though, there is only one field. So the m_impl field below references the first implementation that we see. If we encounter additional implementations with not-equivalent fields, we save these in m_other_impls.

Definition at line 166 of file IdDictGroup.h.

Member Typedef Documentation

ChildPair

using IdDictGroup::IdDictRegionTreeNode::ChildPair = std::pair<size_t, unsigned>

References to child nodes.

The special value 0 means that there there is no valid identifier on that path, and END means that we have some to the end of an identifier. This can be stored in two ways. First, simply as a vector of child node numbers, indexed by the unpacked field index. Or if all the node numbers are the same up to some point (and all 0's after that), we can store it as a pair of the number of non-zero values plus the value itself.

Definition at line 189 of file IdDictGroup.h.

Constructor & Destructor Documentation

IdDictRegionTreeNode()

IdDictGroup::IdDictRegionTreeNode::IdDictRegionTreeNode

(

const IdDictFieldImplementation &

impl

)

Constructor, taking a reference to the implementation.

Definition at line 201 of file IdDictGroup.cxx.

    : m_impl (impl),
      m_children  (std::in_place_index<0>,
                   impl.ored_field().get_indices(), 0)
{
}

Member Function Documentation

optimize()

void IdDictGroup::IdDictRegionTreeNode::optimize

(

)

Compress the vector of node indices, if they are all the same.

Definition at line 211 of file IdDictGroup.cxx.

{
  if (m_children.index() == 0) {
    uint64_t c = 0;
    auto& children = std::get<0> (m_children);
    size_t ipos = children.size();
    while (ipos > 0 && children[ipos-1] == 0) {
      --ipos;
    }
    if (ipos > 0) {
      c = children[ipos-1];
      size_t ipos2 = ipos;
      while (ipos2 > 0 && children[ipos2-1] == c) {
        --ipos2;
      }
      if (ipos2 > 0) return;
    }
    m_children.emplace<1> (ipos, c);
  }
}

Member Data Documentation

END

constexpr unsigned IdDictGroup::IdDictRegionTreeNode::END = static_cast<unsigned> (-1)

staticconstexpr

Special value used to indicate that we've reached the end.

Definition at line 194 of file IdDictGroup.h.

m_children

std::variant<std::vector<unsigned>, ChildPair> IdDictGroup::IdDictRegionTreeNode::m_children

Definition at line 190 of file IdDictGroup.h.

m_impl

const IdDictFieldImplementation& IdDictGroup::IdDictRegionTreeNode::m_impl

Reference to the the implementation field.

Definition at line 173 of file IdDictGroup.h.

m_other_impls

std::unique_ptr<std::vector<const IdDictFieldImplementation*> > IdDictGroup::IdDictRegionTreeNode::m_other_impls

Implementations for other field descriptions that this ored field of the identifier may contain.

This is usually empty, which is why we separate it from m_impl above and hold it via a unique_ptr.

Definition at line 179 of file IdDictGroup.h.

---

The documentation for this struct was generated from the following files:

• IdDictGroup.h
• IdDictGroup.cxx