From 0fcd6de93b998a03f7e7c086522e803602974150 Mon Sep 17 00:00:00 2001 From: Matt Armstrong Date: Thu, 6 Oct 2022 13:05:19 -0700 Subject: [PATCH] ; * src/itree.h (struct interval_node): document field invariants. --- src/itree.h | 47 +++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 45 insertions(+), 2 deletions(-) diff --git a/src/itree.h b/src/itree.h index 9b79551f77c..9e40b87cc4f 100644 --- a/src/itree.h +++ b/src/itree.h @@ -25,7 +25,8 @@ along with GNU Emacs. If not, see . */ #include "lisp.h" -/* The tree and node structs are mainly here, so they can be allocated. +/* The tree and node structs are mainly here, so they can be + allocated. NOTE: The only time where it is safe to modify node.begin and node.end directly, is while the node is not part of any tree. @@ -33,14 +34,56 @@ along with GNU Emacs. If not, see . */ NOTE: It is safe to read node.begin and node.end directly, if the node came from a generator, because it validates the nodes it returns as a side-effect. -*/ + */ struct interval_node; struct interval_node { + /* The normal parent, left and right links found in binary trees. + See also `red`, below, which completes the Red-Black tree + representation. */ struct interval_node *parent; struct interval_node *left; struct interval_node *right; + + /* The following five fields comprise the interval abstraction. + + BEGIN, END are buffer positions describing the range. When a + node is in a tree these fields are read only, written only by + itree functions. + + The LIMIT, OFFSET and OTICK fields should be considered internal + to itree.c and used only by itree functions. + + LIMIT is a buffer position, the maximum of END of this node and + its children. See itree.c for its use. + + OFFSET is in buffer position units, and will be non-zero only + when the node is dirty. + + OTICK determines whether BEGIN, END, LIMIT and OFFSET are + considered dirty. A node is clean when its OTICK is equal to the + OTICK of its tree (see struct interval_tree). Otherwise, it is + dirty. + + In a clean node, BEGIN, END and LIMIT are correct buffer + positions, and OFFSET is zero. The parent of a clean node is + also clean, recursively. + + In a dirty node, the node's OTICK won't equal its tree's OTICK, + and its OFFSET may be non-zero. At all times the descendents of + a dirty node are also dirty. BEGIN, END and LIMIT require + adjustment before use as buffer positions. + + NOTE: BEGIN and END must not be modified while the node is part + of a tree. Use interval_tree_insert_gap and + interval_tree_delete_gap instead. + + NOTE: The interval generators ensure nodes are clean before + yielding them, so BEGIN and END may be safely used as buffer + positions then. + */ + ptrdiff_t begin; /* The beginning of this interval. */ ptrdiff_t end; /* The end of the interval. */ ptrdiff_t limit; /* The maximum end in this subtree. */ -- 2.39.2