1 /* This file implements an efficient interval data-structure.
2
3 Copyright (C) 2017-2023 Free Software Foundation, Inc.
4
5 This file is part of GNU Emacs.
6
7 GNU Emacs is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or (at
10 your option) any later version.
11
12 GNU Emacs is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GNU Emacs. If not, see <https://www.gnu.org/licenses/>. */
19
20 #ifndef ITREE_H
21 #define ITREE_H
22 #include <config.h>
23 #include <stddef.h>
24 #include <inttypes.h>
25
26 #include "lisp.h"
27
28 INLINE_HEADER_BEGIN
29
30 /* The tree and node structs are mainly here, so they can be
31 allocated.
32
33 NOTE: The only time where it is safe to modify node.begin and
34 node.end directly, is while the node is not part of any tree.
35
36 NOTE: It is safe to read node.begin and node.end directly, if the
37 node came from an iterator, because it validates the nodes it
38 returns as a side-effect. See ITREE_FOREACH.
39 */
40
41 struct itree_node
42 {
43 /* The normal parent, left and right links found in binary trees.
44 See also `red`, below, which completes the Red-Black tree
45 representation. */
46 struct itree_node *parent;
47 struct itree_node *left;
48 struct itree_node *right;
49
50 /* The following five fields comprise the interval abstraction.
51
52 BEGIN, END are buffer positions describing the range. When a
53 node is in a tree these fields are read only, written only by
54 itree functions.
55
56 The LIMIT, OFFSET and OTICK fields should be considered internal
57 to itree.c and used only by itree functions.
58
59 LIMIT is a buffer position, the maximum of END of this node and
60 its children. See itree.c for its use.
61
62 OFFSET is in buffer position units, and will be non-zero only
63 when the node is dirty.
64
65 OTICK determines whether BEGIN, END, LIMIT and OFFSET are
66 considered dirty. A node is clean when its OTICK is equal to the
67 OTICK of its tree (see struct itree_tree). Otherwise, it is
68 dirty.
69
70 In a clean node, BEGIN, END and LIMIT are correct buffer
71 positions, and OFFSET is zero. The parent of a clean node is
72 also clean, recursively.
73
74 In a dirty node, the node's OTICK won't equal its tree's OTICK,
75 and its OFFSET may be non-zero. At all times the descendents of
76 a dirty node are also dirty. BEGIN, END and LIMIT require
77 adjustment before use as buffer positions.
78
79 NOTE: BEGIN and END must not be modified while the node is part
80 of a tree. Use itree_insert_gap and itree_delete_gap instead.
81
82 NOTE: The interval iterators ensure nodes are clean before
83 yielding them, so BEGIN and END may be safely used as buffer
84 positions then. */
85
86 ptrdiff_t begin; /* The beginning of this interval. */
87 ptrdiff_t end; /* The end of the interval. */
88 ptrdiff_t limit; /* The maximum end in this subtree. */
89 ptrdiff_t offset; /* The amount of shift to apply to this subtree. */
90 uintmax_t otick; /* offset modified tick */
91 Lisp_Object data; /* Exclusively used by the client. */
92 bool_bf red : 1;
93 bool_bf rear_advance : 1; /* Same as for marker and overlays. */
94 bool_bf front_advance : 1; /* Same as for marker and overlays. */
95 };
96
97 struct itree_tree
98 {
99 struct itree_node *root;
100 uintmax_t otick; /* offset tick, compared with node's otick. */
101 intmax_t size; /* Number of nodes in the tree. */
102 };
103
104 enum itree_order
105 {
106 ITREE_ASCENDING,
107 ITREE_DESCENDING,
108 ITREE_PRE_ORDER,
109 ITREE_POST_ORDER,
110 };
111
112 extern void itree_node_init (struct itree_node *, bool, bool, Lisp_Object);
113 extern ptrdiff_t itree_node_begin (struct itree_tree *, struct itree_node *);
114 extern ptrdiff_t itree_node_end (struct itree_tree *, struct itree_node *);
115 extern void itree_node_set_region (struct itree_tree *, struct itree_node *,
116 ptrdiff_t, ptrdiff_t);
117 extern struct itree_tree *itree_create (void);
118 extern void itree_destroy (struct itree_tree *);
119 INLINE bool
120 itree_empty_p (struct itree_tree *tree)
121 {
122 return !tree || !tree->root;
123 }
124 extern intmax_t itree_size (struct itree_tree *);
125 extern void itree_clear (struct itree_tree *);
126 extern void itree_insert (struct itree_tree *, struct itree_node *,
127 ptrdiff_t, ptrdiff_t);
128 extern struct itree_node *itree_remove (struct itree_tree *,
129 struct itree_node *);
130 extern void itree_insert_gap (struct itree_tree *, ptrdiff_t, ptrdiff_t, bool);
131 extern void itree_delete_gap (struct itree_tree *, ptrdiff_t, ptrdiff_t);
132
133 /* Iteration functions. Almost all code should use ITREE_FOREACH
134 instead. */
135 extern struct itree_iterator *itree_iterator_start (struct itree_iterator *,
136 struct itree_tree *,
137 ptrdiff_t,
138 ptrdiff_t,
139 enum itree_order);
140 extern void itree_iterator_narrow (struct itree_iterator *, ptrdiff_t,
141 ptrdiff_t);
142 extern struct itree_node *itree_iterator_next (struct itree_iterator *);
143
144 /* State used when iterating interval. */
145 struct itree_iterator
146 {
147 struct itree_node *node;
148 ptrdiff_t begin;
149 ptrdiff_t end;
150 uintmax_t otick; /* A copy of the tree's `otick`. */
151 enum itree_order order;
152 };
153
154 /* Iterate over the intervals between BEG and END in the tree T.
155 N will hold successive nodes. ORDER can be one of : `ASCENDING`,
156 `DESCENDING`, `POST_ORDER`, or `PRE_ORDER`.
157 It should be used as:
158
159 ITREE_FOREACH (n, t, beg, end, order)
160 {
161 .. do the thing with n ..
162 }
163
164 BEWARE:
165 - The expression T may be evaluated more than once, so make sure
166 it is cheap and pure.
167 - Don't modify the tree during the iteration.
168 */
169 #define ITREE_FOREACH(n, t, beg, end, order) \
170 /* FIXME: We'd want to declare `n` right here, but I can't figure out
171 how to make that work here: the `for` syntax only allows a single
172 clause for the var declarations where we need 2 different types.
173 We could use the `struct {foo x; bar y; } p;` trick to declare two
174 vars `p.x` and `p.y` of unrelated types, but then none of the names
175 of the vars matches the `n` we receive :-(. */ \
176 if (!t) \
177 { } \
178 else \
179 for (struct itree_iterator itree_local_iter_, \
180 *itree_iter_ \
181 = itree_iterator_start (&itree_local_iter_, \
182 t, beg, end, ITREE_##order); \
183 ((n = itree_iterator_next (itree_iter_)));)
184
185 #define ITREE_FOREACH_NARROW(beg, end) \
186 itree_iterator_narrow (itree_iter_, beg, end)
187
188 INLINE_HEADER_END
189
190 #endif