#ifndef _NTRTL_H

typedef struct _RTL_SPLAY_LINKS
{
    struct _RTL_SPLAY_LINKS *Parent;
    struct _RTL_SPLAY_LINKS *LeftChild;
    struct _RTL_SPLAY_LINKS *RightChild;
} RTL_SPLAY_LINKS, *PRTL_SPLAY_LINKS;

#endif
View code on GitHub

// ntddk.h

typedef struct _RTL_SPLAY_LINKS {
  struct _RTL_SPLAY_LINKS *Parent;
  struct _RTL_SPLAY_LINKS *LeftChild;
  struct _RTL_SPLAY_LINKS *RightChild;
} RTL_SPLAY_LINKS;
View the official Windows Driver Kit DDI reference

NtDoc

This structure is documented in Windows Driver Kit.

Edit description on GitHub

Windows Driver Kit DDI reference (ns-ntddk-_rtl_splay_links)

_RTL_SPLAY_LINKS structure

Description

The RTL_SPLAY_LINKS structure is an opaque structure and is used by the system to represent a splay link tree node.

Members

`Parent`

An opaque pointer to the parent node for this node. If only one node in the splay link tree exists, the value of this member is NULL.

`LeftChild`

An opaque pointer to the left child node for this node. If no left-child node exists, the value of this member is NULL.

`RightChild`

An opaque pointer to the right child node for this node. If no right-child node exists, the value of this member is NULL.

Remarks

Typically, each node of a splay link tree consists of a user-defined structure. Each such user-defined node must contain an initialized RTL_SPLAY_LINKS structure. To initialize a RTL_SPLAY_LINKS structure, call the RtlInitializeSplayLinks macro. (Pass the address of the RTL_SPLAY_LINKS member that is contained within the user-defined structure.)

For a splay link tree with one or more nodes, a new node is generally initialized as follows:

Use RtlLeftChild and/or RtlRightChild to find the insertion point for the new node. That is, obtain the correct address of the parent node for the new node. (The new node will be attached either to the left of the parent node or to the right.)
Use RtlInitializeSplayLinks to initialize the new node with the address of the parent node that is found in the previous step.
Insert the new node into the splay tree by using either RtlInsertAsLeftChild or RtlInsertAsRightChild, as appropriate.
Call RtlSplay with the address of the new node. (The new node becomes the root of the splay tree.)

Callers of the RtlXxx splay tree routines are responsible for synchronizing access to the splay tree. For more information about how to synchronize access to the splay tree, see Locks, Deadlocks, and Synchronization and Managing Hardware Priorities.

RTL_SPLAY_LINKS - NtDoc