struct WAVLTreeBestNodeObserver

WAVLTreeBestNodeObserver

Definition of a WAVLTreeObserver which helps to automate the process of

maintaining a "best value in this subtree" invariant inside of a WAVL tree.

For example, consider a set of objects, each of which has an "Priority" and

an "Awesomeness" property. If a user is maintaining a collection of these

objects indexed by "Priority", they may want to be able to easily answer

questions about the maximum "Awesomeness" of sets of objects partitioned by

priority. If every member in the tree also maintained a "maximum Awesomeness

for my subtree" value, then the following questions can be easily answered.

1) What is the maximum awesomeness across all members of the tree? This is

the maximum subtree awesomeness of the root node of the tree.

2) What is the maximum awesomeness across all members of the tree with a

priority > X? This is the maximum subtree awesomeness of

tree.upper_bound(X) (if such a node exists).

WAVLTreeBestNodeObserver implements all of the observer hooks needed to

maintain such an invariant based on a set of Traits defined by the user which

allow the WAVLTreeBestNodeObserver to know when one node has a "better" value

than another node, and to access the per-node storage which holds the "best"

value for a subtree.

Traits implementations should contain the following definitions:

struct Traits {

// TODO(johngro): When we are allowed to use C++20, make this a more formal

// concept definition.

// Returns a node's value. In the example above, this is the node's "awesomeness".

static ValueType GetValue(const Object

&

node) { ... }

// Returns the current "best" value of the subtree rooted at node.

static ValueType GetSubtreeBest(const Object

&

node) { ... }

// Compares two values, and returns true if |a| is "better" than |b|. Otherwise false.

static bool Compare(ValueType a, ValueType b) { ... }

// Assigns the value |val| to the node's subtree-best storage.

static void AssignBest(Object

&

node, ValueType val) { ... }

// Resets the value node's subtree-best storage. Called when nodes are

// being removed from their tree. Note that users don't _have_ to make use

// of this hook if they do not care about stale values being stored in their

// subtree-best storage.

static void ResetBest(Object

&

target) { ... }

};

The Traits used for the "awesomness" example given above might look like the

following if "awesomeness" was expressed as a strictly positive uint32_t:

struct AwesomeObj {

// ...

constexpr uint32_t kInvalidAwesomeness = 0;

uint32_t priority;

uint32_t awesomeness;

uint32_t subtree_best{kInvalidAwesomeness};

};

struct MaxAwesomeTraits {

static uint32_t GetValue(const AwesomeObj

&

node) { return node.awesomness; }

static uint32_t GetSubtreeBest(const AwesomeObj

&

node) { return node.subtree_best; }

static bool Compare(uint32_t a, uint32_t b) { return a > b; }

static void AssignBest(AwesomeObj

&

node, uint32_t val) { node.subtree_best = val; }

static void ResetBest(AwesomeObj

&

target) {

node.subtree_best = AwesomeObj::kInvalidAwesomeness;

}

};

using MaxAwesomeObserver = fbl::WAVLReeBestNodeObserver

<MaxAwesomeTraits

>;

In addition to the traits which define the "best" value to maintain,

WAVLTreeBestNodeObserver has two more boolean template parameters which can

be used to control behavior. They are:

AllowInsertOrFindCollision

AllowInsertOrReplaceCollision

By default, both of these values are |true|. If a collision happens during

either an insert_or_find or an insert_or_replace operation, the "best value"

invariant will be maintained. On the other hand, if a user knows that they

will never encounter collisions as a result of one or the other (or both) of

these operations, they may set the appropriate Allow template argument to

false, causing the WAVLTreeBestNodeObserver to fail a ZX_DEBUG_ASSERT in the

case that associated collision is ever encountered during operation.