unofficial mirror of bug-gnu-emacs@gnu.org 
 help / color / mirror / code / Atom feed
blob 3ef9e76812aa4d711193752a4c3df3105c0bfdec 7347 bytes (raw)
name: src/itree.h 	 # note: path name is non-authoritative(*)

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
 
/* This file implements an efficient interval data-structure.

Copyright (C) 2017-2022  Free Software Foundation, Inc.

This file is part of GNU Emacs.

GNU Emacs is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or (at
your option) any later version.

GNU Emacs is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.  */

#ifndef ITREE_H
#define ITREE_H
#include <config.h>
#include <stddef.h>
#include <inttypes.h>

#include "lisp.h"

/* 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.

   NOTE: It is safe to read node.begin and node.end directly, if the
   node came from an iterator, because it validates the nodes it
   returns as a side-effect.  See ITREE_FOREACH.
 */

struct itree_node
{
  /* The normal parent, left and right links found in binary trees.
     See also `red`, below, which completes the Red-Black tree
     representation.  */
  struct itree_node *parent;
  struct itree_node *left;
  struct itree_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 itree_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 itree_insert_gap and itree_delete_gap instead.

     NOTE: The interval iterators 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. */
  ptrdiff_t offset;		/* The amount of shift to apply to this subtree. */
  uintmax_t otick;              /* offset modified tick */
  Lisp_Object data;             /* Exclusively used by the client. */
  bool_bf red : 1;
  bool_bf rear_advance : 1;     /* Same as for marker and overlays.  */
  bool_bf front_advance : 1;    /* Same as for marker and overlays.  */
};

struct itree_tree
{
  struct itree_node *root;
  uintmax_t otick;              /* offset tick, compared with node's otick. */
  intmax_t size;                /* Number of nodes in the tree. */
};

enum itree_order
  {
    ITREE_ASCENDING,
    ITREE_DESCENDING,
    ITREE_PRE_ORDER,
  };

extern void itree_node_init (struct itree_node *, bool, bool, Lisp_Object);
extern ptrdiff_t itree_node_begin (struct itree_tree *, struct itree_node *);
extern ptrdiff_t itree_node_end (struct itree_tree *, struct itree_node *);
extern void itree_node_set_region (struct itree_tree *, struct itree_node *,
				   ptrdiff_t, ptrdiff_t);
extern struct itree_tree *itree_create (void);
extern void itree_destroy (struct itree_tree *);
extern intmax_t itree_size (struct itree_tree *);
extern void itree_clear (struct itree_tree *);
extern void itree_insert (struct itree_tree *, struct itree_node *,
			  ptrdiff_t, ptrdiff_t);
extern struct itree_node *itree_remove (struct itree_tree *,
					struct itree_node *);
extern void itree_insert_gap (struct itree_tree *, ptrdiff_t,
			      ptrdiff_t, bool);
extern void itree_delete_gap (struct itree_tree *, ptrdiff_t, ptrdiff_t);

/* Iteration functions.  Almost all code should use ITREE_FOREACH
   instead.  */
extern bool itree_iterator_busy_p (void);
extern struct itree_iterator *itree_iterator_start (struct itree_tree *,
						    ptrdiff_t,
						    ptrdiff_t,
						    enum itree_order,
						    const char *, int);
extern void itree_iterator_narrow (struct itree_iterator *, ptrdiff_t,
				   ptrdiff_t);
extern void itree_iterator_finish (struct itree_iterator *);
extern struct itree_node *itree_iterator_next (struct itree_iterator *);

/* Iterate over the intervals between BEG and END in the tree T.
   N will hold successive nodes.  ORDER can be one of : `ASCENDING`,
   `DESCENDING`, or `PRE_ORDER`.
   It should be used as:

      ITREE_FOREACH (n, t, beg, end, order)
        {
          .. do the thing with n ..
        }

   BEWARE:
   - The expression T may be evaluated more than once, so make sure
     it is cheap a pure.
   - Only a single iteration can happen at a time, so make sure none of the
     code within the loop can start another tree iteration, i.e. it shouldn't
     be able to run ELisp code, nor GC since GC can run ELisp by way
     of `post-gc-hook`.
   - If you need to exit the loop early, you *have* to call `ITREE_ABORT`
     just before exiting (e.g. with `break` or `return`).
   - Non-local exits are not supported within the body of the loop.
   - Don't modify the tree during the iteration.
 */
#define ITREE_FOREACH(n, t, beg, end, order)                        \
  /* FIXME: We'd want to declare `x` right here, but I can't figure out
     how to make that work here: the `for` syntax only allows a single
     clause for the var declarations where we need 2 different types.
     We could use the `struct {foo x; bar y; } p;` trick to declare two
     vars `p.x` and `p.y` of unrelated types, but then none of the names
     of the vars matches the `n` we receive :-(.  */                \
  if (!t)                                                           \
    { }                                                             \
  else                                                              \
    for (struct itree_iterator *itree_iter_                         \
            = itree_iterator_start (t, beg, end, ITREE_##order,     \
                                        __FILE__, __LINE__);        \
          ((n = itree_iterator_next (itree_iter_))                  \
           || (itree_iterator_finish (itree_iter_), false));)

#define ITREE_FOREACH_ABORT() \
  itree_iterator_finish (itree_iter_)

#define ITREE_FOREACH_NARROW(beg, end) \
  itree_iterator_narrow (itree_iter_, beg, end)

#endif

debug log:

solving 3ef9e76812a ...
found 3ef9e76812a in https://yhetil.org/emacs-bugs/87o7tn49vl.fsf@rfc20.org/
found c6b68d36672 in https://git.savannah.gnu.org/cgit/emacs.git
preparing index
index prepared:
100644 c6b68d3667256d760b2e6322e1bdaef4da91945c	src/itree.h

applying [1/1] https://yhetil.org/emacs-bugs/87o7tn49vl.fsf@rfc20.org/
diff --git a/src/itree.h b/src/itree.h
index c6b68d36672..3ef9e76812a 100644

Checking patch src/itree.h...
Applied patch src/itree.h cleanly.

index at:
100644 3ef9e76812aa4d711193752a4c3df3105c0bfdec	src/itree.h

(*) Git path names are given by the tree(s) the blob belongs to.
    Blobs themselves have no identifier aside from the hash of its contents.^

Code repositories for project(s) associated with this public inbox

	https://git.savannah.gnu.org/cgit/emacs.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).