Implementation:Onnx Onnx Graph Node List

Knowledge Sources	Onnx_Onnx
Domains	Data Structures, Graph IR
Last Updated	2026-02-10 00:00 GMT

Overview

Concrete tool for providing intrusive doubly-linked list iteration over graph nodes provided by the ONNX library.

Description

The onnx/common/graph_node_list.h header implements intrusive doubly-linked lists with bidirectional iteration support, specifically designed for managing Node objects within ONNX Graph structures.

The design uses two pointers stored directly in each Node object (next_in_graph[2]), where index 0 is the forward link and index 1 is the backward link. This intrusive approach avoids separate allocation of list nodes and provides O(1) insertion and removal.

The header provides two main template classes:

generic_graph_node_list_iterator<T> is a bidirectional iterator that tracks a current node pointer and a direction flag. It supports increment (++), decrement (--), dereference (*), member access (->), and destroyCurrent() for safe deletion during iteration (the iterator moves to the previous element before destroying the current one). A reverse() method creates an iterator going in the opposite direction.

generic_graph_node_list<T> represents the list itself, holding a head sentinel pointer and a direction. It provides begin()/end(), rbegin()/rend(), and reverse() methods. The sentinel-based design eliminates edge cases for empty lists and ensures reverse iterators physically point to the element they logically represent, unlike standard library reverse iterators.

Type aliases are provided for convenience: graph_node_list and const_graph_node_list for Node and const Node respectively, along with corresponding iterator aliases. The header also provides equality/inequality comparison operators and a std::iterator_traits specialization for STL compatibility.

Usage

Use this list implementation for traversing and manipulating nodes in ONNX graph structures. The bidirectional iteration is essential for graph algorithms that need to process nodes in both topological and reverse topological order. Use destroyCurrent() when removing nodes during iteration to maintain iterator validity.

Code Reference

Source Location

• Repository: Onnx_Onnx
• File: onnx/common/graph_node_list.h

Signature

namespace ONNX_NAMESPACE {

static constexpr size_t kNextDirection = 0;
static constexpr size_t kPrevDirection = 1;

template <typename T>
struct generic_graph_node_list_iterator final {
  generic_graph_node_list_iterator();
  generic_graph_node_list_iterator(T* cur, size_t d);
  T* operator*() const;
  T* operator->() const;
  generic_graph_node_list_iterator& operator++();
  generic_graph_node_list_iterator operator++(int);
  generic_graph_node_list_iterator& operator--();
  generic_graph_node_list_iterator operator--(int);
  void destroyCurrent();
  generic_graph_node_list_iterator reverse();
};

template <typename T>
struct generic_graph_node_list final {
  using iterator = generic_graph_node_list_iterator<T>;
  using const_iterator = generic_graph_node_list_iterator<const T>;
  generic_graph_node_list_iterator<T> begin();
  generic_graph_node_list_iterator<T> end();
  generic_graph_node_list_iterator<T> rbegin();
  generic_graph_node_list_iterator<T> rend();
  generic_graph_node_list reverse();
  generic_graph_node_list(T* head, size_t d);
};

using graph_node_list = generic_graph_node_list<Node>;
using const_graph_node_list = generic_graph_node_list<const Node>;
using graph_node_list_iterator = generic_graph_node_list_iterator<Node>;
using const_graph_node_list_iterator = generic_graph_node_list_iterator<const Node>;

} // namespace ONNX_NAMESPACE

Import

#include "onnx/common/graph_node_list.h"

I/O Contract

Inputs

Name	Type	Required	Description
head	T*	Yes	Pointer to the sentinel node that anchors the list
d	size_t	Yes	Direction: kNextDirection (0) for forward, kPrevDirection (1) for backward

Outputs

Name	Type	Description
iterator	generic_graph_node_list_iterator<T>	Bidirectional iterator over the graph nodes
*iterator	T*	Pointer to the current Node in the list

Usage Examples

#include "onnx/common/graph_node_list.h"
using namespace ONNX_NAMESPACE;

// Forward iteration over graph nodes
graph_node_list nodes = graph->nodes();
for (auto it = nodes.begin(); it != nodes.end(); ++it) {
    Node* node = *it;
    // process node
}

// Range-based for loop
for (Node* node : graph->nodes()) {
    // process node in topological order
}

// Reverse iteration
for (Node* node : graph->nodes().reverse()) {
    // process node in reverse topological order
}

// Safe deletion during iteration
for (auto it = nodes.begin(); it != nodes.end();) {
    if (shouldRemove(*it)) {
        it.destroyCurrent();  // iterator moves to previous element
    } else {
        ++it;
    }
}

Related Pages

• Environment:Onnx_Onnx_Cpp_Build_Environment