4 * This file contains code that manages the B-tree representation
5 * of text for the text buffer and implements character and
6 * toggle segment types.
8 * Copyright (c) 1992-1994 The Regents of the University of California.
9 * Copyright (c) 1994-1995 Sun Microsystems, Inc.
10 * Copyright (c) 2000 Red Hat, Inc.
11 * Tk -> Gtk port by Havoc Pennington <hp@redhat.com>
13 * This software is copyrighted by the Regents of the University of
14 * California, Sun Microsystems, Inc., and other parties. The
15 * following terms apply to all files associated with the software
16 * unless explicitly disclaimed in individual files.
18 * The authors hereby grant permission to use, copy, modify,
19 * distribute, and license this software and its documentation for any
20 * purpose, provided that existing copyright notices are retained in
21 * all copies and that this notice is included verbatim in any
22 * distributions. No written agreement, license, or royalty fee is
23 * required for any of the authorized uses. Modifications to this
24 * software may be copyrighted by their authors and need not follow
25 * the licensing terms described here, provided that the new terms are
26 * clearly indicated on the first page of each file where they apply.
28 * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY
29 * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
30 * DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION,
31 * OR ANY DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED
32 * OF THE POSSIBILITY OF SUCH DAMAGE.
34 * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
35 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
36 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND
37 * NON-INFRINGEMENT. THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS,
38 * AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE
39 * MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
41 * GOVERNMENT USE: If you are acquiring this software on behalf of the
42 * U.S. government, the Government shall have only "Restricted Rights"
43 * in the software and related documentation as defined in the Federal
44 * Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2). If you
45 * are acquiring the software on behalf of the Department of Defense,
46 * the software shall be classified as "Commercial Computer Software"
47 * and the Government shall have only "Restricted Rights" as defined
48 * in Clause 252.227-7013 (c) (1) of DFARs. Notwithstanding the
49 * foregoing, the authors grant the U.S. Government and others acting
50 * in its behalf permission to use and distribute the software in
51 * accordance with the terms specified in this license.
55 #include "gtktextbtree.h"
60 #include "gtksignal.h"
61 #include "gtktexttag.h"
62 #include "gtktexttagtable.h"
63 #include "gtktextlayout.h"
64 #include "gtktextiterprivate.h"
66 #include "gtktextmarkprivate.h"
74 * The structure below is used to pass information between
75 * gtk_text_btree_get_tags and inc_count:
78 typedef struct TagInfo {
79 int numTags; /* Number of tags for which there
80 * is currently information in
82 int arraySize; /* Number of entries allocated for
84 GtkTextTag **tags; /* Array of tags seen so far.
86 int *counts; /* Toggle count (so far) for each
87 * entry in tags. Malloc-ed. */
92 * This is used to store per-view width/height info at the tree nodes.
95 typedef struct _NodeData NodeData;
101 /* Height and width of this node */
105 /* boolean indicating whether the height/width need to be recomputed */
111 * The data structure below keeps summary information about one tag as part
112 * of the tag information in a node.
115 typedef struct Summary {
116 GtkTextTagInfo *info; /* Handle for tag. */
117 int toggle_count; /* Number of transitions into or
118 * out of this tag that occur in
119 * the subtree rooted at this node. */
120 struct Summary *next; /* Next in list of all tags for same
121 * node, or NULL if at end of list. */
125 * The data structure below defines a node in the B-tree.
128 struct _GtkTextBTreeNode {
129 GtkTextBTreeNode *parent; /* Pointer to parent node, or NULL if
130 * this is the root. */
131 GtkTextBTreeNode *next; /* Next in list of siblings with the
132 * same parent node, or NULL for end
134 Summary *summary; /* First in malloc-ed list of info
135 * about tags in this subtree (NULL if
136 * no tag info in the subtree). */
137 int level; /* Level of this node in the B-tree.
138 * 0 refers to the bottom of the tree
139 * (children are lines, not nodes). */
140 union { /* First in linked list of children. */
141 struct _GtkTextBTreeNode *node; /* Used if level > 0. */
142 GtkTextLine *line; /* Used if level == 0. */
144 int num_children; /* Number of children of this node. */
145 int num_lines; /* Total number of lines (leaves) in
146 * the subtree rooted here. */
147 int num_chars; /* Number of chars below here */
154 * Used to store the list of views in our btree
157 typedef struct _BTreeView BTreeView;
161 GtkTextLayout *layout;
167 * And the tree itself
170 struct _GtkTextBTree {
171 GtkTextBTreeNode *root_node; /* Pointer to root of B-tree. */
172 GtkTextTagTable *table;
173 GHashTable *mark_table;
175 GtkTextMark *insert_mark;
176 GtkTextMark *selection_bound_mark;
177 GtkTextBuffer *buffer;
180 guint tag_changed_handler;
181 guint tag_removed_handler;
182 /* Incremented when a segment with a byte size > 0
183 is added to or removed from the tree (i.e. the
184 length of a line may have changed, and lines may
185 have been added or removed). This invalidates
186 all outstanding iterators.
188 guint chars_changed_stamp;
189 /* Incremented when any segments are added or deleted;
190 this makes outstanding iterators recalculate their
191 pointed-to segment and segment offset.
193 guint segments_changed_stamp;
195 GtkTextLine *end_iter_line;
197 guint end_iter_line_stamp;
202 * Upper and lower bounds on how many children a node may have:
203 * rebalance when either of these limits is exceeded. MAX_CHILDREN
204 * should be twice MIN_CHILDREN and MIN_CHILDREN must be >= 2.
207 /* Tk used MAX of 12 and MIN of 6. This makes the tree wide and
208 shallow. It appears to be faster to locate a particular line number
209 if the tree is narrow and deep, since it is more finely sorted. I
210 guess this may increase memory use though, and make it slower to
211 walk the tree in order, or locate a particular byte index (which
212 is done by walking the tree in order).
214 There's basically a tradeoff here. However I'm thinking we want to
215 add pixels, byte counts, and char counts to the tree nodes,
216 at that point narrow and deep should speed up all operations,
217 not just the line number searches.
221 #define MAX_CHILDREN 12
222 #define MIN_CHILDREN 6
224 #define MAX_CHILDREN 6
225 #define MIN_CHILDREN 3
232 static BTreeView *gtk_text_btree_get_view (GtkTextBTree *tree,
234 static void gtk_text_btree_rebalance (GtkTextBTree *tree,
235 GtkTextBTreeNode *node);
236 static GtkTextLine * get_last_line (GtkTextBTree *tree);
237 static void post_insert_fixup (GtkTextBTree *tree,
238 GtkTextLine *insert_line,
239 gint char_count_delta,
240 gint line_count_delta);
241 static void gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
242 GtkTextTagInfo *info,
244 static gboolean gtk_text_btree_node_has_tag (GtkTextBTreeNode *node,
247 static void segments_changed (GtkTextBTree *tree);
248 static void chars_changed (GtkTextBTree *tree);
249 static void summary_list_destroy (Summary *summary);
250 static GtkTextLine *gtk_text_line_new (void);
251 static void gtk_text_line_destroy (GtkTextBTree *tree,
253 static void gtk_text_line_set_parent (GtkTextLine *line,
254 GtkTextBTreeNode *node);
255 static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
259 static NodeData *node_data_new (gpointer view_id);
260 static void node_data_destroy (NodeData *nd);
261 static void node_data_list_destroy (NodeData *nd);
262 static NodeData *node_data_find (NodeData *nd,
265 static GtkTextBTreeNode *gtk_text_btree_node_new (void);
266 static void gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node);
267 static void gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node,
269 static NodeData * gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
271 static NodeData * gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
273 static void gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
276 static void gtk_text_btree_node_remove_view (BTreeView *view,
277 GtkTextBTreeNode *node,
279 static void gtk_text_btree_node_destroy (GtkTextBTree *tree,
280 GtkTextBTreeNode *node);
281 static NodeData * gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node,
283 static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
285 static void gtk_text_btree_node_get_size (GtkTextBTreeNode *node,
289 static GtkTextBTreeNode * gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
290 GtkTextBTreeNode *node2);
291 static void get_tree_bounds (GtkTextBTree *tree,
294 static void tag_changed_cb (GtkTextTagTable *table,
296 gboolean size_changed,
298 static void tag_removed_cb (GtkTextTagTable *table,
301 static void cleanup_line (GtkTextLine *line);
302 static void recompute_node_counts (GtkTextBTree *tree,
303 GtkTextBTreeNode *node);
304 static void inc_count (GtkTextTag *tag,
306 TagInfo *tagInfoPtr);
308 static void summary_destroy (Summary *summary);
310 static void gtk_text_btree_link_segment (GtkTextLineSegment *seg,
311 const GtkTextIter *iter);
312 static void gtk_text_btree_unlink_segment (GtkTextBTree *tree,
313 GtkTextLineSegment *seg,
317 static GtkTextTagInfo *gtk_text_btree_get_tag_info (GtkTextBTree *tree,
319 static GtkTextTagInfo *gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
321 static void gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
324 static void redisplay_region (GtkTextBTree *tree,
325 const GtkTextIter *start,
326 const GtkTextIter *end);
328 /* Inline thingies */
331 segments_changed(GtkTextBTree *tree)
333 tree->segments_changed_stamp += 1;
337 chars_changed(GtkTextBTree *tree)
339 tree->chars_changed_stamp += 1;
347 gtk_text_btree_new (GtkTextTagTable *table,
348 GtkTextBuffer *buffer)
351 GtkTextBTreeNode *root_node;
352 GtkTextLine *line, *line2;
354 g_return_val_if_fail(GTK_IS_TEXT_TAG_TABLE(table), NULL);
355 g_return_val_if_fail(GTK_IS_TEXT_BUFFER(buffer), NULL);
358 * The tree will initially have two empty lines. The second line
359 * isn't actually part of the tree's contents, but its presence
360 * makes several operations easier. The tree will have one GtkTextBTreeNode,
361 * which is also the root of the tree.
364 /* Create the root node. */
366 root_node = gtk_text_btree_node_new();
368 line = gtk_text_line_new();
369 line2 = gtk_text_line_new();
371 root_node->parent = NULL;
372 root_node->next = NULL;
373 root_node->summary = NULL;
374 root_node->level = 0;
375 root_node->children.line = line;
376 root_node->num_children = 2;
377 root_node->num_lines = 2;
378 root_node->num_chars = 2;
380 line->parent = root_node;
383 line->segments = _gtk_char_segment_new("\n", 1);
385 line2->parent = root_node;
387 line2->segments = _gtk_char_segment_new("\n", 1);
389 /* Create the tree itself */
391 tree = g_new0(GtkTextBTree, 1);
392 tree->root_node = root_node;
396 /* Set these to values that are unlikely to be found
397 * in random memory garbage, and also avoid
398 * duplicates between tree instances.
400 tree->chars_changed_stamp = g_random_int ();
401 tree->segments_changed_stamp = g_random_int ();
403 tree->end_iter_line_stamp = tree->chars_changed_stamp - 1;
404 tree->end_iter_line = NULL;
406 gtk_object_ref(GTK_OBJECT(tree->table));
407 gtk_object_sink(GTK_OBJECT(tree->table));
409 tree->tag_changed_handler = gtk_signal_connect(GTK_OBJECT(tree->table),
411 GTK_SIGNAL_FUNC(tag_changed_cb),
414 tree->tag_removed_handler = gtk_signal_connect(GTK_OBJECT(tree->table),
416 GTK_SIGNAL_FUNC(tag_removed_cb),
419 tree->mark_table = g_hash_table_new(g_str_hash, g_str_equal);
421 /* We don't ref the buffer, since the buffer owns us;
422 * we'd have some circularity issues. The buffer always
423 * lasts longer than the BTree
425 tree->buffer = buffer;
429 GtkTextLineSegment *seg;
431 gtk_text_btree_get_iter_at_line_char(tree, &start, 0, 0);
434 tree->insert_mark = gtk_text_btree_set_mark (tree,
441 seg = tree->insert_mark->segment;
443 seg->body.mark.not_deleteable = TRUE;
444 seg->body.mark.visible = TRUE;
446 tree->selection_bound_mark = gtk_text_btree_set_mark (tree,
453 seg = tree->selection_bound_mark->segment;
455 seg->body.mark.not_deleteable = TRUE;
457 g_object_ref (G_OBJECT (tree->insert_mark));
458 g_object_ref (G_OBJECT (tree->selection_bound_mark));
467 gtk_text_btree_ref (GtkTextBTree *tree)
469 g_return_if_fail(tree != NULL);
470 g_return_if_fail(tree->refcount > 0);
476 mark_destroy_foreach (gpointer key, gpointer value, gpointer user_data)
478 GtkTextLineSegment *seg = value;
480 g_return_if_fail (seg->body.mark.tree == NULL);
482 g_object_unref (G_OBJECT (seg->body.mark.obj));
486 gtk_text_btree_unref (GtkTextBTree *tree)
488 g_return_if_fail(tree != NULL);
489 g_return_if_fail(tree->refcount > 0);
493 if (tree->refcount == 0)
495 gtk_text_btree_node_destroy (tree, tree->root_node);
497 g_hash_table_foreach (tree->mark_table,
498 mark_destroy_foreach,
500 g_hash_table_destroy (tree->mark_table);
502 g_object_unref (G_OBJECT (tree->insert_mark));
503 g_object_unref (G_OBJECT (tree->selection_bound_mark));
505 gtk_signal_disconnect (GTK_OBJECT(tree->table),
506 tree->tag_changed_handler);
508 gtk_signal_disconnect (GTK_OBJECT(tree->table),
509 tree->tag_removed_handler);
511 gtk_object_unref (GTK_OBJECT(tree->table));
518 gtk_text_btree_get_buffer (GtkTextBTree *tree)
524 gtk_text_btree_get_chars_changed_stamp (GtkTextBTree *tree)
526 return tree->chars_changed_stamp;
530 gtk_text_btree_get_segments_changed_stamp (GtkTextBTree *tree)
532 return tree->segments_changed_stamp;
536 gtk_text_btree_segments_changed (GtkTextBTree *tree)
538 g_return_if_fail(tree != NULL);
539 segments_changed(tree);
543 * Indexable segment mutation
547 gtk_text_btree_delete (GtkTextIter *start,
550 GtkTextLineSegment *prev_seg; /* The segment just before the start
551 * of the deletion range. */
552 GtkTextLineSegment *last_seg; /* The segment just after the end
553 * of the deletion range. */
554 GtkTextLineSegment *seg, *next;
555 GtkTextLine *curline;
556 GtkTextBTreeNode *curnode, *node;
558 GtkTextLine *start_line;
559 GtkTextLine *end_line;
560 GtkTextLine *deleted_lines = NULL; /* List of lines we've deleted */
561 gint start_byte_offset;
563 g_return_if_fail(start != NULL);
564 g_return_if_fail(end != NULL);
565 g_return_if_fail(gtk_text_iter_get_btree(start) ==
566 gtk_text_iter_get_btree(end));
568 gtk_text_iter_reorder(start, end);
570 tree = gtk_text_iter_get_btree(start);
574 * The code below is ugly, but it's needed to make sure there
575 * is always a dummy empty line at the end of the text. If the
576 * final newline of the file (just before the dummy line) is being
577 * deleted, then back up index to just before the newline. If
578 * there is a newline just before the first character being deleted,
579 * then back up the first index too, so that an even number of lines
580 * gets deleted. Furthermore, remove any tags that are present on
581 * the newline that isn't going to be deleted after all (this simulates
582 * deleting the newline and then adding a "clean" one back again).
588 line1 = gtk_text_iter_get_line(start);
589 line2 = gtk_text_iter_get_line(end);
591 if (line2 == gtk_text_btree_line_count(tree))
595 GtkTextIter orig_end;
598 gtk_text_iter_prev_char(end);
602 if (gtk_text_iter_get_line_offset(start) == 0 &&
605 gtk_text_iter_prev_char(start);
609 tags = gtk_text_btree_get_tags(end,
617 while (i < array_size)
619 gtk_text_btree_tag(end, &orig_end, tags[i], FALSE);
629 /* Broadcast the need for redisplay before we break the iterators */
630 gtk_text_btree_invalidate_region(tree, start, end);
632 /* Save the byte offset so we can reset the iterators */
633 start_byte_offset = gtk_text_iter_get_line_index(start);
635 start_line = gtk_text_iter_get_text_line(start);
636 end_line = gtk_text_iter_get_text_line(end);
639 * Split the start and end segments, so we have a place
640 * to insert our new text.
642 * Tricky point: split at end first; otherwise the split
643 * at end may invalidate seg and/or prev_seg. This allows
644 * us to avoid invalidating segments for start.
647 last_seg = gtk_text_line_segment_split(end);
648 if (last_seg != NULL)
649 last_seg = last_seg->next;
651 last_seg = end_line->segments;
653 prev_seg = gtk_text_line_segment_split(start);
654 if (prev_seg != NULL)
656 seg = prev_seg->next;
657 prev_seg->next = last_seg;
661 seg = start_line->segments;
662 start_line->segments = last_seg;
665 /* notify iterators that their segments need recomputation,
666 just for robustness. */
667 segments_changed(tree);
670 * Delete all of the segments between prev_seg and last_seg.
673 curline = start_line;
674 curnode = curline->parent;
675 while (seg != last_seg)
681 GtkTextLine *nextline;
684 * We just ran off the end of a line. First find the
685 * next line, then go back to the old line and delete it
686 * (unless it's the starting line for the range).
689 nextline = gtk_text_line_next(curline);
690 if (curline != start_line)
692 if (curnode == start_line->parent)
693 start_line->next = curline->next;
695 curnode->children.line = curline->next;
697 for (node = curnode; node != NULL;
700 node->num_lines -= 1;
703 curnode->num_children -= 1;
704 curline->next = deleted_lines;
705 deleted_lines = curline;
709 seg = curline->segments;
712 * If the GtkTextBTreeNode is empty then delete it and its parents,
713 * recursively upwards until a non-empty GtkTextBTreeNode is found.
716 while (curnode->num_children == 0)
718 GtkTextBTreeNode *parent;
720 parent = curnode->parent;
721 if (parent->children.node == curnode)
723 parent->children.node = curnode->next;
727 GtkTextBTreeNode *prevnode = parent->children.node;
728 while (prevnode->next != curnode)
730 prevnode = prevnode->next;
732 prevnode->next = curnode->next;
734 parent->num_children--;
738 curnode = curline->parent;
743 char_count = seg->char_count;
745 if ((*seg->type->deleteFunc)(seg, curline, 0) != 0)
748 * This segment refuses to die. Move it to prev_seg and
749 * advance prev_seg if the segment has left gravity.
752 if (prev_seg == NULL)
754 seg->next = start_line->segments;
755 start_line->segments = seg;
759 seg->next = prev_seg->next;
760 prev_seg->next = seg;
762 if (seg->type->leftGravity)
769 /* Segment is gone. Decrement the char count of the node and
771 for (node = curnode; node != NULL;
774 node->num_chars -= char_count;
782 * If the beginning and end of the deletion range are in different
783 * lines, join the two lines together and discard the ending line.
786 if (start_line != end_line)
789 GtkTextBTreeNode *ancestor_node;
791 GtkTextLine *prevline;
793 for (seg = last_seg; seg != NULL;
796 if (seg->type->lineChangeFunc != NULL)
798 (*seg->type->lineChangeFunc)(seg, end_line);
801 curnode = end_line->parent;
802 for (node = curnode; node != NULL;
807 curnode->num_children--;
808 prevline = curnode->children.line;
809 if (prevline == end_line)
811 curnode->children.line = end_line->next;
815 while (prevline->next != end_line)
817 prevline = prevline->next;
819 prevline->next = end_line->next;
821 end_line->next = deleted_lines;
822 deleted_lines = end_line;
824 /* We now fix up the per-view aggregates. We add all the height and
825 * width for the deleted lines to the start line, so that when revalidation
826 * occurs, the correct change in size is seen.
828 ancestor_node = gtk_text_btree_node_common_parent (curnode, start_line->parent);
835 gint deleted_width = 0;
836 gint deleted_height = 0;
838 line = deleted_lines;
841 GtkTextLine *next_line = line->next;
842 ld = gtk_text_line_get_data (line, view->view_id);
846 deleted_width = MAX (deleted_width, ld->width);
847 deleted_height += ld->height;
851 gtk_text_line_destroy(tree, line);
856 if (deleted_width > 0 || deleted_height > 0)
858 ld = gtk_text_line_get_data (start_line, view->view_id);
860 /* FIXME: ld is _NOT_ necessarily non-null here, but there is currently
861 * no way to add ld without also validating the node, which would
862 * be improper at this point.
864 /* This assertion does actually fail sometimes, must
865 fix before stable release -hp */
868 ld->width = MAX (deleted_width, ld->width);
869 ld->height += deleted_height;
873 gtk_text_btree_node_check_valid_downward (ancestor_node, view->view_id);
874 if (ancestor_node->parent)
875 gtk_text_btree_node_check_valid_upward (ancestor_node->parent, view->view_id);
880 gtk_text_btree_rebalance(tree, curnode);
884 * Cleanup the segments in the new line.
887 cleanup_line(start_line);
890 * Lastly, rebalance the first GtkTextBTreeNode of the range.
893 gtk_text_btree_rebalance(tree, start_line->parent);
895 /* Notify outstanding iterators that they
898 segments_changed(tree);
900 if (gtk_debug_flags & GTK_DEBUG_TEXT)
901 gtk_text_btree_check(tree);
903 /* Re-initialize our iterators */
904 gtk_text_btree_get_iter_at_line(tree, start, start_line, start_byte_offset);
909 gtk_text_btree_insert (GtkTextIter *iter,
913 GtkTextLineSegment *prev_seg; /* The segment just before the first
914 * new segment (NULL means new segment
915 * is at beginning of line). */
916 GtkTextLineSegment *cur_seg; /* Current segment; new characters
917 * are inserted just after this one.
918 * NULL means insert at beginning of
920 GtkTextLine *line; /* Current line (new segments are
921 * added to this line). */
922 GtkTextLineSegment *seg;
923 GtkTextLine *newline;
924 int chunkSize; /* # characters in current chunk. */
925 guint sol; /* start of line */
926 guint eol; /* Pointer to character just after last
927 * one in current chunk. */
928 int line_count_delta; /* Counts change to total number of
931 int char_count_delta; /* change to number of chars */
933 gint start_byte_index;
934 GtkTextLine *start_line;
936 g_return_if_fail(text != NULL);
937 g_return_if_fail(iter != NULL);
942 /* extract iterator info */
943 tree = gtk_text_iter_get_btree(iter);
944 line = gtk_text_iter_get_text_line(iter);
946 start_byte_index = gtk_text_iter_get_line_index(iter);
948 /* Get our insertion segment split */
949 prev_seg = gtk_text_line_segment_split(iter);
952 /* Invalidate all iterators */
954 segments_changed(tree);
957 * Chop the text up into lines and create a new segment for
958 * each line, plus a new line for the leftovers from the
964 line_count_delta = 0;
965 char_count_delta = 0;
968 for (; eol < len; eol++)
970 if (text[eol] == '\n')
976 chunkSize = eol - sol;
978 seg = _gtk_char_segment_new (&text[sol], chunkSize);
980 char_count_delta += seg->char_count;
984 seg->next = line->segments;
985 line->segments = seg;
989 seg->next = cur_seg->next;
993 if (text[eol-1] != '\n')
999 * The chunk ended with a newline, so create a new GtkTextLine
1000 * and move the remainder of the old line to it.
1003 newline = gtk_text_line_new();
1004 gtk_text_line_set_parent(newline, line->parent);
1005 newline->next = line->next;
1006 line->next = newline;
1007 newline->segments = seg->next;
1017 * Cleanup the starting line for the insertion, plus the ending
1018 * line if it's different.
1021 cleanup_line(start_line);
1022 if (line != start_line)
1027 post_insert_fixup(tree, line, line_count_delta, char_count_delta);
1029 /* Invalidate our region, and reset the iterator the user
1030 passed in to point to the end of the inserted text. */
1036 gtk_text_btree_get_iter_at_line(tree,
1042 /* We could almost certainly be more efficient here
1043 by saving the information from the insertion loop
1045 gtk_text_iter_forward_chars(&end, char_count_delta);
1047 gtk_text_btree_invalidate_region(tree,
1051 /* Convenience for the user */
1057 gtk_text_btree_insert_pixbuf (GtkTextIter *iter,
1060 GtkTextLineSegment *seg;
1062 GtkTextLineSegment *prevPtr;
1065 gint start_byte_offset;
1067 line = gtk_text_iter_get_text_line(iter);
1068 tree = gtk_text_iter_get_btree(iter);
1069 start_byte_offset = gtk_text_iter_get_line_index(iter);
1071 seg = _gtk_pixbuf_segment_new (pixbuf);
1073 prevPtr = gtk_text_line_segment_split(iter);
1074 if (prevPtr == NULL)
1076 seg->next = line->segments;
1077 line->segments = seg;
1081 seg->next = prevPtr->next;
1082 prevPtr->next = seg;
1085 post_insert_fixup(tree, line, 0, seg->char_count);
1087 chars_changed(tree);
1088 segments_changed(tree);
1090 /* reset *iter for the user, and invalidate tree nodes */
1092 gtk_text_btree_get_iter_at_line(tree, &start, line, start_byte_offset);
1095 gtk_text_iter_next_char(iter); /* skip forward past the pixmap */
1097 gtk_text_btree_invalidate_region(tree, &start, iter);
1106 find_line_by_y(GtkTextBTree *tree, BTreeView *view,
1107 GtkTextBTreeNode *node, gint y, gint *line_top,
1108 GtkTextLine *last_line)
1112 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1113 gtk_text_btree_check(tree);
1115 if (node->level == 0)
1119 line = node->children.line;
1121 while (line != NULL && line != last_line)
1123 GtkTextLineData *ld;
1125 ld = gtk_text_line_get_data (line, view->view_id);
1129 if (y < (current_y + (ld ? ld->height : 0)))
1132 current_y += ld->height;
1133 *line_top += ld->height;
1142 GtkTextBTreeNode *child;
1144 child = node->children.node;
1146 while (child != NULL)
1151 gtk_text_btree_node_get_size(child, view->view_id,
1154 if (y < (current_y + height))
1155 return find_line_by_y(tree, view, child,
1156 y - current_y, line_top,
1159 current_y += height;
1160 *line_top += height;
1162 child = child->next;
1170 gtk_text_btree_find_line_by_y (GtkTextBTree *tree,
1177 GtkTextLine *last_line;
1180 view = gtk_text_btree_get_view (tree, view_id);
1181 g_return_val_if_fail (view != NULL, NULL);
1183 last_line = get_last_line (tree);
1185 line = find_line_by_y (tree, view, tree->root_node, ypixel, &line_top,
1189 *line_top_out = line_top;
1195 find_line_top_in_line_list(GtkTextBTree *tree,
1198 GtkTextLine *target_line,
1201 while (line != NULL)
1203 GtkTextLineData *ld;
1205 if (line == target_line)
1208 ld = gtk_text_line_get_data (line, view->view_id);
1215 g_assert_not_reached(); /* If we get here, our
1216 target line didn't exist
1217 under its parent node */
1222 gtk_text_btree_find_line_top (GtkTextBTree *tree,
1223 GtkTextLine *target_line,
1230 GtkTextBTreeNode *node;
1232 view = gtk_text_btree_get_view(tree, view_id);
1234 g_return_val_if_fail(view != NULL, 0);
1237 node = target_line->parent;
1238 while (node != NULL)
1240 nodes = g_slist_prepend(nodes, node);
1241 node = node->parent;
1245 while (iter != NULL)
1249 if (node->level == 0)
1251 g_slist_free(nodes);
1252 return find_line_top_in_line_list(tree, view,
1253 node->children.line,
1258 GtkTextBTreeNode *child;
1259 GtkTextBTreeNode *target_node;
1261 g_assert(iter->next != NULL); /* not at level 0 */
1262 target_node = iter->next->data;
1264 child = node->children.node;
1266 while (child != NULL)
1271 if (child == target_node)
1275 gtk_text_btree_node_get_size(child, view->view_id,
1279 child = child->next;
1281 g_assert(child != NULL); /* should have broken out before we
1285 iter = g_slist_next(iter);
1288 g_assert_not_reached(); /* we return when we find the target line */
1293 gtk_text_btree_add_view (GtkTextBTree *tree,
1294 GtkTextLayout *layout)
1297 GtkTextLine *last_line;
1298 GtkTextLineData *line_data;
1300 g_return_if_fail(tree != NULL);
1302 view = g_new(BTreeView, 1);
1304 view->view_id = layout;
1305 view->layout = layout;
1307 view->next = tree->views;
1312 /* The last line in the buffer has identity values for the per-view
1313 * data so that we can avoid special case checks for it in a large
1316 last_line = get_last_line (tree);
1318 line_data = g_new (GtkTextLineData, 1);
1319 line_data->view_id = layout;
1320 line_data->next = NULL;
1321 line_data->width = 0;
1322 line_data->height = 0;
1323 line_data->valid = TRUE;
1325 gtk_text_line_add_data (last_line, line_data);
1329 gtk_text_btree_remove_view (GtkTextBTree *tree,
1333 GtkTextLine *last_line;
1334 GtkTextLineData *line_data;
1336 g_return_if_fail(tree != NULL);
1340 while (view != NULL)
1342 if (view->view_id == view_id)
1348 g_return_if_fail(view != NULL);
1351 view->next->prev = view->prev;
1354 view->prev->next = view->next;
1356 if (view == tree->views)
1357 tree->views = view->next;
1359 /* Remove the line data for the last line which we added ourselves.
1360 * (Do this first, so that we don't try to call the view's line data destructor on it.)
1362 last_line = get_last_line (tree);
1363 line_data = gtk_text_line_remove_data (last_line, view_id);
1366 gtk_text_btree_node_remove_view(view, tree->root_node, view_id);
1372 gtk_text_btree_invalidate_region (GtkTextBTree *tree,
1373 const GtkTextIter *start,
1374 const GtkTextIter *end)
1380 while (view != NULL)
1382 gtk_text_layout_invalidate(view->layout, start, end);
1389 gtk_text_btree_get_view_size (GtkTextBTree *tree,
1394 g_return_if_fail(tree != NULL);
1395 g_return_if_fail(view_id != NULL);
1397 gtk_text_btree_node_get_size (tree->root_node, view_id,
1412 iter_stack_new(void)
1415 stack = g_new(IterStack, 1);
1416 stack->iters = NULL;
1423 iter_stack_push(IterStack *stack, const GtkTextIter *iter)
1426 if (stack->count > stack->alloced)
1428 stack->alloced = stack->count*2;
1429 stack->iters = g_realloc(stack->iters,
1430 stack->alloced*sizeof(GtkTextIter));
1432 stack->iters[stack->count-1] = *iter;
1436 iter_stack_pop(IterStack *stack, GtkTextIter *iter)
1438 if (stack->count == 0)
1443 *iter = stack->iters[stack->count];
1449 iter_stack_free(IterStack *stack)
1451 g_free(stack->iters);
1456 iter_stack_invert(IterStack *stack)
1458 if (stack->count > 0)
1461 guint j = stack->count - 1;
1466 tmp = stack->iters[i];
1467 stack->iters[i] = stack->iters[j];
1468 stack->iters[j] = tmp;
1477 queue_tag_redisplay (GtkTextBTree *tree,
1479 const GtkTextIter *start,
1480 const GtkTextIter *end)
1482 if (gtk_text_tag_affects_size (tag))
1484 gtk_text_btree_invalidate_region (tree, start, end);
1487 else if (gtk_text_tag_affects_nonsize_appearance (tag))
1489 /* We only need to queue a redraw, not a relayout */
1490 redisplay_region (tree, start, end);
1493 /* We don't need to do anything if the tag doesn't affect display */
1497 gtk_text_btree_tag (const GtkTextIter *start_orig,
1498 const GtkTextIter *end_orig,
1502 GtkTextLineSegment *seg, *prev;
1503 GtkTextLine *cleanupline;
1504 gboolean toggled_on;
1505 GtkTextLine *start_line;
1506 GtkTextLine *end_line;
1508 GtkTextIter start, end;
1511 GtkTextTagInfo *info;
1513 g_return_if_fail(start_orig != NULL);
1514 g_return_if_fail(end_orig != NULL);
1515 g_return_if_fail(GTK_IS_TEXT_TAG(tag));
1516 g_return_if_fail(gtk_text_iter_get_btree(start_orig) ==
1517 gtk_text_iter_get_btree(end_orig));
1520 printf("%s tag %s from %d to %d\n",
1521 add ? "Adding" : "Removing",
1523 gtk_text_buffer_get_offset(start_orig),
1524 gtk_text_buffer_get_offset(end_orig));
1527 if (gtk_text_iter_equal(start_orig, end_orig))
1530 start = *start_orig;
1533 gtk_text_iter_reorder(&start, &end);
1535 tree = gtk_text_iter_get_btree(&start);
1537 queue_tag_redisplay (tree, tag, &start, &end);
1539 info = gtk_text_btree_get_tag_info(tree, tag);
1541 start_line = gtk_text_iter_get_text_line(&start);
1542 end_line = gtk_text_iter_get_text_line(&end);
1544 /* Find all tag toggles in the region; we are going to delete them.
1545 We need to find them in advance, because
1546 forward_find_tag_toggle() won't work once we start playing around
1548 stack = iter_stack_new();
1550 /* We don't want to delete a toggle that's at the start iterator. */
1551 gtk_text_iter_next_char(&iter);
1552 while (gtk_text_iter_forward_to_tag_toggle(&iter, tag))
1554 if (gtk_text_iter_compare(&iter, &end) >= 0)
1557 iter_stack_push(stack, &iter);
1560 /* We need to traverse the toggles in order. */
1561 iter_stack_invert(stack);
1564 * See whether the tag is present at the start of the range. If
1565 * the state doesn't already match what we want then add a toggle
1569 toggled_on = gtk_text_iter_has_tag(&start, tag);
1570 if ( (add && !toggled_on) ||
1571 (!add && toggled_on) )
1573 /* This could create a second toggle at the start position;
1574 cleanup_line() will remove it if so. */
1575 seg = _gtk_toggle_segment_new(info, add);
1577 prev = gtk_text_line_segment_split(&start);
1580 seg->next = start_line->segments;
1581 start_line->segments = seg;
1585 seg->next = prev->next;
1589 /* cleanup_line adds the new toggle to the node counts. */
1591 printf("added toggle at start\n");
1593 /* we should probably call segments_changed, but in theory
1594 any still-cached segments in the iters we are about to
1595 use are still valid, since they're in front
1601 * Scan the range of characters and delete any internal tag
1602 * transitions. Keep track of what the old state was at the end
1603 * of the range, and add a toggle there if it's needed.
1607 cleanupline = start_line;
1608 while (iter_stack_pop(stack, &iter))
1610 GtkTextLineSegment *indexable_seg;
1613 line = gtk_text_iter_get_text_line(&iter);
1614 seg = gtk_text_iter_get_any_segment(&iter);
1615 indexable_seg = gtk_text_iter_get_indexable_segment(&iter);
1617 g_assert(seg != NULL);
1618 g_assert(indexable_seg != NULL);
1619 g_assert(seg != indexable_seg);
1621 prev = line->segments;
1623 /* Find the segment that actually toggles this tag. */
1624 while (seg != indexable_seg)
1626 g_assert(seg != NULL);
1627 g_assert(indexable_seg != NULL);
1628 g_assert(seg != indexable_seg);
1630 if ( (seg->type == >k_text_toggle_on_type ||
1631 seg->type == >k_text_toggle_off_type) &&
1632 (seg->body.toggle.info == info) )
1638 g_assert(seg != NULL);
1639 g_assert(indexable_seg != NULL);
1641 g_assert(seg != indexable_seg); /* If this happens, then
1642 forward_to_tag_toggle was
1644 g_assert(seg->body.toggle.info->tag == tag);
1646 /* If this happens, when previously tagging we didn't merge
1647 overlapping tags. */
1648 g_assert( (toggled_on && seg->type == >k_text_toggle_off_type) ||
1649 (!toggled_on && seg->type == >k_text_toggle_on_type) );
1651 toggled_on = !toggled_on;
1654 printf("deleting %s toggle\n",
1655 seg->type == >k_text_toggle_on_type ? "on" : "off");
1657 /* Remove toggle segment from the list. */
1660 line->segments = seg->next;
1664 while (prev->next != seg)
1668 prev->next = seg->next;
1671 /* Inform iterators we've hosed them. This actually reflects a
1672 bit of inefficiency; if you have the same tag toggled on and
1673 off a lot in a single line, we keep having the rescan from
1674 the front of the line. Of course we have to do that to get
1675 "prev" anyway, but here we are doing it an additional
1677 segments_changed(tree);
1679 /* Update node counts */
1680 if (seg->body.toggle.inNodeCounts)
1682 _gtk_change_node_toggle_count(line->parent,
1684 seg->body.toggle.inNodeCounts = FALSE;
1689 /* We only clean up lines when we're done with them, saves some
1690 gratuitous line-segment-traversals */
1692 if (cleanupline != line)
1694 cleanup_line(cleanupline);
1699 iter_stack_free(stack);
1701 /* toggled_on now reflects the toggle state _just before_ the
1702 end iterator. The end iterator could already have a toggle
1703 on or a toggle off. */
1704 if ( (add && !toggled_on) ||
1705 (!add && toggled_on) )
1707 /* This could create a second toggle at the start position;
1708 cleanup_line() will remove it if so. */
1710 seg = _gtk_toggle_segment_new(info, !add);
1712 prev = gtk_text_line_segment_split(&end);
1715 seg->next = end_line->segments;
1716 end_line->segments = seg;
1720 seg->next = prev->next;
1723 /* cleanup_line adds the new toggle to the node counts. */
1724 g_assert(seg->body.toggle.inNodeCounts == FALSE);
1726 printf("added toggle at end\n");
1731 * Cleanup cleanupline and the last line of the range, if
1732 * these are different.
1735 cleanup_line(cleanupline);
1736 if (cleanupline != end_line)
1738 cleanup_line(end_line);
1741 segments_changed(tree);
1743 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1744 gtk_text_btree_check(tree);
1753 gtk_text_btree_get_line (GtkTextBTree *tree,
1755 gint *real_line_number)
1757 GtkTextBTreeNode *node;
1762 line_count = gtk_text_btree_line_count(tree);
1764 if (line_number < 0)
1766 line_number = line_count;
1768 else if (line_number > line_count)
1770 line_number = line_count;
1773 if (real_line_number)
1774 *real_line_number = line_number;
1776 node = tree->root_node;
1777 lines_left = line_number;
1780 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1784 while (node->level != 0)
1786 for (node = node->children.node;
1787 node->num_lines <= lines_left;
1793 g_error("gtk_text_btree_find_line ran out of GtkTextBTreeNodes");
1796 lines_left -= node->num_lines;
1801 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1804 for (line = node->children.line; lines_left > 0;
1810 g_error("gtk_text_btree_find_line ran out of lines");
1819 gtk_text_btree_get_line_at_char(GtkTextBTree *tree,
1821 gint *line_start_index,
1822 gint *real_char_index)
1824 GtkTextBTreeNode *node;
1826 GtkTextLineSegment *seg;
1831 node = tree->root_node;
1833 /* Clamp to valid indexes (-1 is magic for "highest index") */
1834 if (char_index < 0 || char_index >= node->num_chars)
1836 char_index = node->num_chars - 1;
1839 *real_char_index = char_index;
1842 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1846 chars_left = char_index;
1847 while (node->level != 0)
1849 for (node = node->children.node;
1850 chars_left >= node->num_chars;
1853 chars_left -= node->num_chars;
1855 g_assert(chars_left >= 0);
1859 if (chars_left == 0)
1861 /* Start of a line */
1863 *line_start_index = char_index;
1864 return node->children.line;
1868 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1874 for (line = node->children.line; line != NULL; line = line->next)
1876 seg = line->segments;
1879 if (chars_in_line + seg->char_count > chars_left)
1880 goto found; /* found our line/segment */
1882 chars_in_line += seg->char_count;
1887 chars_left -= chars_in_line;
1895 g_assert(line != NULL); /* hosage, ran out of lines */
1896 g_assert(seg != NULL);
1898 *line_start_index = char_index - chars_left;
1903 gtk_text_btree_get_tags (const GtkTextIter *iter,
1906 GtkTextBTreeNode *node;
1907 GtkTextLine *siblingline;
1908 GtkTextLineSegment *seg;
1909 int src, dst, index;
1915 #define NUM_TAG_INFOS 10
1917 line = gtk_text_iter_get_text_line(iter);
1918 tree = gtk_text_iter_get_btree(iter);
1919 byte_index = gtk_text_iter_get_line_index(iter);
1921 tagInfo.numTags = 0;
1922 tagInfo.arraySize = NUM_TAG_INFOS;
1923 tagInfo.tags = g_new(GtkTextTag*, NUM_TAG_INFOS);
1924 tagInfo.counts = g_new(int, NUM_TAG_INFOS);
1927 * Record tag toggles within the line of indexPtr but preceding
1928 * indexPtr. Note that if this loop segfaults, your
1929 * byte_index probably points past the sum of all
1930 * seg->byte_count */
1932 for (index = 0, seg = line->segments;
1933 (index + seg->byte_count) <= byte_index;
1934 index += seg->byte_count, seg = seg->next)
1936 if ((seg->type == >k_text_toggle_on_type)
1937 || (seg->type == >k_text_toggle_off_type))
1939 inc_count(seg->body.toggle.info->tag, 1, &tagInfo);
1944 * Record toggles for tags in lines that are predecessors of
1945 * line but under the same level-0 GtkTextBTreeNode.
1948 for (siblingline = line->parent->children.line;
1949 siblingline != line;
1950 siblingline = siblingline->next)
1952 for (seg = siblingline->segments; seg != NULL;
1955 if ((seg->type == >k_text_toggle_on_type)
1956 || (seg->type == >k_text_toggle_off_type))
1958 inc_count(seg->body.toggle.info->tag, 1, &tagInfo);
1964 * For each GtkTextBTreeNode in the ancestry of this line, record tag
1965 * toggles for all siblings that precede that GtkTextBTreeNode.
1968 for (node = line->parent; node->parent != NULL;
1969 node = node->parent)
1971 GtkTextBTreeNode *siblingPtr;
1974 for (siblingPtr = node->parent->children.node;
1975 siblingPtr != node; siblingPtr = siblingPtr->next)
1977 for (summary = siblingPtr->summary; summary != NULL;
1978 summary = summary->next)
1980 if (summary->toggle_count & 1)
1982 inc_count(summary->info->tag, summary->toggle_count,
1990 * Go through the tag information and squash out all of the tags
1991 * that have even toggle counts (these tags exist before the point
1992 * of interest, but not at the desired character itself).
1995 for (src = 0, dst = 0; src < tagInfo.numTags; src++)
1997 if (tagInfo.counts[src] & 1)
1999 g_assert(GTK_IS_TEXT_TAG(tagInfo.tags[src]));
2000 tagInfo.tags[dst] = tagInfo.tags[src];
2006 g_free(tagInfo.counts);
2009 g_free(tagInfo.tags);
2012 return tagInfo.tags;
2016 copy_segment(GString *string,
2017 gboolean include_hidden,
2018 gboolean include_nonchars,
2019 const GtkTextIter *start,
2020 const GtkTextIter *end)
2022 GtkTextLineSegment *end_seg;
2023 GtkTextLineSegment *seg;
2025 if (gtk_text_iter_equal(start, end))
2028 seg = gtk_text_iter_get_indexable_segment(start);
2029 end_seg = gtk_text_iter_get_indexable_segment(end);
2031 if (seg->type == >k_text_char_type)
2033 gboolean copy = TRUE;
2034 gint copy_bytes = 0;
2035 gint copy_start = 0;
2037 /* Don't copy if we're invisible; segments are invisible/not
2038 as a whole, no need to check each char */
2039 if (!include_hidden &&
2040 gtk_text_btree_char_is_invisible(start))
2043 /* printf(" <invisible>\n"); */
2046 copy_start = gtk_text_iter_get_segment_byte(start);
2050 /* End is in the same segment; need to copy fewer bytes. */
2051 gint end_byte = gtk_text_iter_get_segment_byte(end);
2053 copy_bytes = end_byte - copy_start;
2056 copy_bytes = seg->byte_count - copy_start;
2058 g_assert(copy_bytes != 0); /* Due to iter equality check at
2059 front of this function. */
2063 g_assert((copy_start + copy_bytes) <= seg->byte_count);
2065 g_string_append_len(string,
2066 seg->body.chars + copy_start,
2070 /* printf(" :%s\n", string->str); */
2072 else if (seg->type == >k_text_pixbuf_type)
2074 gboolean copy = TRUE;
2076 if (!include_nonchars)
2080 else if (!include_hidden &&
2081 gtk_text_btree_char_is_invisible(start))
2088 g_string_append_len(string,
2089 gtk_text_unknown_char_utf8,
2097 gtk_text_btree_get_text (const GtkTextIter *start_orig,
2098 const GtkTextIter *end_orig,
2099 gboolean include_hidden,
2100 gboolean include_nonchars)
2102 GtkTextLineSegment *seg;
2103 GtkTextLineSegment *end_seg;
2111 g_return_val_if_fail(start_orig != NULL, NULL);
2112 g_return_val_if_fail(end_orig != NULL, NULL);
2113 g_return_val_if_fail(gtk_text_iter_get_btree(start_orig) ==
2114 gtk_text_iter_get_btree(end_orig), NULL);
2116 start = *start_orig;
2119 gtk_text_iter_reorder(&start, &end);
2121 retval = g_string_new("");
2123 tree = gtk_text_iter_get_btree(&start);
2125 end_seg = gtk_text_iter_get_indexable_segment(&end);
2127 seg = gtk_text_iter_get_indexable_segment(&iter);
2128 while (seg != end_seg)
2130 copy_segment(retval, include_hidden, include_nonchars,
2133 gtk_text_iter_forward_indexable_segment(&iter);
2135 seg = gtk_text_iter_get_indexable_segment(&iter);
2138 copy_segment(retval, include_hidden, include_nonchars, &iter, &end);
2141 g_string_free(retval, FALSE);
2146 gtk_text_btree_line_count (GtkTextBTree *tree)
2148 /* Subtract bogus line at the end; we return a count
2150 return tree->root_node->num_lines - 1;
2154 gtk_text_btree_char_count (GtkTextBTree *tree)
2156 /* Exclude newline in bogus last line */
2157 return tree->root_node->num_chars - 1;
2160 #define LOTSA_TAGS 1000
2162 gtk_text_btree_char_is_invisible (const GtkTextIter *iter)
2164 gboolean invisible = FALSE; /* if nobody says otherwise, it's visible */
2166 int deftagCnts[LOTSA_TAGS];
2167 int *tagCnts = deftagCnts;
2168 GtkTextTag *deftags[LOTSA_TAGS];
2169 GtkTextTag **tags = deftags;
2171 GtkTextBTreeNode *node;
2172 GtkTextLine *siblingline;
2173 GtkTextLineSegment *seg;
2180 line = gtk_text_iter_get_text_line(iter);
2181 tree = gtk_text_iter_get_btree(iter);
2182 byte_index = gtk_text_iter_get_line_index(iter);
2184 numTags = gtk_text_tag_table_size(tree->table);
2186 /* almost always avoid malloc, so stay out of system calls */
2187 if (LOTSA_TAGS < numTags)
2189 tagCnts = g_new(int, numTags);
2190 tags = g_new(GtkTextTag*, numTags);
2193 for (i=0; i<numTags; i++)
2199 * Record tag toggles within the line of indexPtr but preceding
2203 for (index = 0, seg = line->segments;
2204 (index + seg->byte_count) <= byte_index; /* segfault here means invalid index */
2205 index += seg->byte_count, seg = seg->next)
2207 if ((seg->type == >k_text_toggle_on_type)
2208 || (seg->type == >k_text_toggle_off_type))
2210 tag = seg->body.toggle.info->tag;
2211 if (tag->invisible_set && tag->values->invisible)
2213 tags[tag->priority] = tag;
2214 tagCnts[tag->priority]++;
2220 * Record toggles for tags in lines that are predecessors of
2221 * line but under the same level-0 GtkTextBTreeNode.
2224 for (siblingline = line->parent->children.line;
2225 siblingline != line;
2226 siblingline = siblingline->next)
2228 for (seg = siblingline->segments; seg != NULL;
2231 if ((seg->type == >k_text_toggle_on_type)
2232 || (seg->type == >k_text_toggle_off_type))
2234 tag = seg->body.toggle.info->tag;
2235 if (tag->invisible_set && tag->values->invisible)
2237 tags[tag->priority] = tag;
2238 tagCnts[tag->priority]++;
2245 * For each GtkTextBTreeNode in the ancestry of this line, record tag toggles
2246 * for all siblings that precede that GtkTextBTreeNode.
2249 for (node = line->parent; node->parent != NULL;
2250 node = node->parent)
2252 GtkTextBTreeNode *siblingPtr;
2255 for (siblingPtr = node->parent->children.node;
2256 siblingPtr != node; siblingPtr = siblingPtr->next)
2258 for (summary = siblingPtr->summary; summary != NULL;
2259 summary = summary->next)
2261 if (summary->toggle_count & 1)
2263 tag = summary->info->tag;
2264 if (tag->invisible_set && tag->values->invisible)
2266 tags[tag->priority] = tag;
2267 tagCnts[tag->priority] += summary->toggle_count;
2275 * Now traverse from highest priority to lowest,
2276 * take invisible value from first odd count (= on)
2279 for (i = numTags-1; i >=0; i--)
2283 /* FIXME not sure this should be if 0 */
2285 #ifndef ALWAYS_SHOW_SELECTION
2286 /* who would make the selection invisible? */
2287 if ((tag == tkxt->seltag)
2288 && !(tkxt->flags & GOT_FOCUS))
2294 invisible = tags[i]->values->invisible;
2299 if (LOTSA_TAGS < numTags)
2314 redisplay_region (GtkTextBTree *tree,
2315 const GtkTextIter *start,
2316 const GtkTextIter *end)
2319 GtkTextLine *start_line, *end_line;
2321 if (gtk_text_iter_compare (start, end) > 0)
2323 const GtkTextIter *tmp = start;
2328 start_line = gtk_text_iter_get_text_line (start);
2329 end_line = gtk_text_iter_get_text_line (end);
2332 while (view != NULL)
2334 gint start_y, end_y;
2335 GtkTextLineData *ld;
2337 start_y = gtk_text_btree_find_line_top (tree, start_line, view->view_id);
2339 if (end_line == start_line)
2342 end_y = gtk_text_btree_find_line_top (tree, end_line, view->view_id);
2344 ld = gtk_text_line_get_data (end_line, view->view_id);
2346 end_y += ld->height;
2348 gtk_text_layout_changed (view->layout, start_y,
2357 redisplay_mark (GtkTextLineSegment *mark)
2362 gtk_text_btree_get_iter_at_mark(mark->body.mark.tree,
2364 mark->body.mark.obj);
2367 gtk_text_iter_next_char(&end);
2369 gtk_text_btree_invalidate_region(mark->body.mark.tree,
2374 redisplay_mark_if_visible(GtkTextLineSegment *mark)
2376 if (!mark->body.mark.visible)
2379 redisplay_mark(mark);
2383 ensure_not_off_end(GtkTextBTree *tree,
2384 GtkTextLineSegment *mark,
2387 if (gtk_text_iter_get_line(iter) ==
2388 gtk_text_btree_line_count(tree))
2389 gtk_text_iter_prev_char(iter);
2392 static GtkTextLineSegment*
2393 real_set_mark(GtkTextBTree *tree,
2394 GtkTextMark *existing_mark,
2396 gboolean left_gravity,
2397 const GtkTextIter *where,
2398 gboolean should_exist,
2399 gboolean redraw_selections)
2401 GtkTextLineSegment *mark;
2404 g_return_val_if_fail(tree != NULL, NULL);
2405 g_return_val_if_fail(where != NULL, NULL);
2406 g_return_val_if_fail(gtk_text_iter_get_btree(where) == tree, NULL);
2409 mark = existing_mark->segment;
2410 else if (name != NULL)
2411 mark = g_hash_table_lookup (tree->mark_table,
2416 if (should_exist && mark == NULL)
2418 g_warning("No mark `%s' exists!", name);
2422 /* OK if !should_exist and it does already exist, in that case
2429 if (redraw_selections &&
2430 (mark == tree->insert_mark->segment ||
2431 mark == tree->selection_bound_mark->segment))
2433 GtkTextIter old_pos;
2435 gtk_text_btree_get_iter_at_mark (tree, &old_pos,
2436 mark->body.mark.obj);
2437 redisplay_region (tree, &old_pos, where);
2441 * don't let visible marks be after the final newline of the
2445 if (mark->body.mark.visible)
2447 ensure_not_off_end(tree, mark, &iter);
2450 /* Redraw the mark's old location. */
2451 redisplay_mark_if_visible (mark);
2453 /* Unlink mark from its current location.
2454 This could hose our iterator... */
2455 gtk_text_btree_unlink_segment(tree, mark,
2456 mark->body.mark.line);
2457 mark->body.mark.line = gtk_text_iter_get_text_line(&iter);
2458 g_assert(mark->body.mark.line == gtk_text_iter_get_text_line(&iter));
2460 segments_changed(tree); /* make sure the iterator recomputes its
2465 mark = _gtk_mark_segment_new (tree,
2469 mark->body.mark.line = gtk_text_iter_get_text_line(&iter);
2471 if (mark->body.mark.name)
2472 g_hash_table_insert (tree->mark_table,
2473 mark->body.mark.name,
2477 /* Link mark into new location */
2478 gtk_text_btree_link_segment (mark, &iter);
2480 /* Invalidate some iterators. */
2481 segments_changed (tree);
2484 * update the screen at the mark's new location.
2487 redisplay_mark_if_visible (mark);
2494 gtk_text_btree_set_mark (GtkTextBTree *tree,
2495 GtkTextMark *existing_mark,
2497 gboolean left_gravity,
2498 const GtkTextIter *iter,
2499 gboolean should_exist)
2501 GtkTextLineSegment *seg;
2503 seg = real_set_mark(tree, existing_mark,
2504 name, left_gravity, iter, should_exist,
2507 return seg ? seg->body.mark.obj : NULL;
2511 gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2515 GtkTextIter tmp_start, tmp_end;
2517 gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2519 gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2520 tree->selection_bound_mark);
2522 if (gtk_text_iter_equal(&tmp_start, &tmp_end))
2534 gtk_text_iter_reorder(&tmp_start, &tmp_end);
2547 gtk_text_btree_place_cursor(GtkTextBTree *tree,
2548 const GtkTextIter *iter)
2550 GtkTextIter start, end;
2552 if (gtk_text_btree_get_selection_bounds (tree, &start, &end))
2553 redisplay_region(tree, &start, &end);
2555 /* Move insert AND selection_bound before we redisplay */
2556 real_set_mark (tree, tree->insert_mark,
2557 "insert", FALSE, iter, TRUE, FALSE);
2558 real_set_mark (tree, tree->selection_bound_mark,
2559 "selection_bound", FALSE, iter, TRUE, FALSE);
2563 gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2568 g_return_if_fail(tree != NULL);
2569 g_return_if_fail(name != NULL);
2571 mark = g_hash_table_lookup(tree->mark_table,
2574 gtk_text_btree_remove_mark(tree, mark);
2578 gtk_text_btree_remove_mark (GtkTextBTree *tree,
2581 GtkTextLineSegment *segment;
2583 g_return_if_fail (mark != NULL);
2584 g_return_if_fail (tree != NULL);
2586 segment = mark->segment;
2588 if (segment->body.mark.not_deleteable)
2590 g_warning("Can't delete special mark `%s'", segment->body.mark.name);
2594 /* This calls cleanup_line and segments_changed */
2595 gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2597 if (segment->body.mark.name)
2598 g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2600 /* Remove the ref on the mark that belonged to the segment. */
2601 g_object_unref (G_OBJECT (mark));
2603 segment->body.mark.tree = NULL;
2604 segment->body.mark.line = NULL;
2608 gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2609 GtkTextMark *segment)
2611 return segment == tree->insert_mark;
2615 gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2616 GtkTextMark *segment)
2618 return segment == tree->selection_bound_mark;
2622 gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2625 GtkTextLineSegment *seg;
2627 g_return_val_if_fail(tree != NULL, NULL);
2628 g_return_val_if_fail(name != NULL, NULL);
2630 seg = g_hash_table_lookup (tree->mark_table, name);
2632 return seg ? seg->body.mark.obj : NULL;
2636 gtk_text_mark_set_visible (GtkTextMark *mark,
2639 GtkTextLineSegment *seg;
2641 g_return_if_fail(mark != NULL);
2643 seg = mark->segment;
2645 if (seg->body.mark.visible == setting)
2649 seg->body.mark.visible = setting;
2651 redisplay_mark (seg);
2656 gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
2659 GtkTextBTreeNode *node;
2660 GtkTextTagInfo *info;
2662 g_return_val_if_fail(tree != NULL, NULL);
2666 info = gtk_text_btree_get_existing_tag_info(tree, tag);
2671 if (info->tag_root == NULL)
2674 node = info->tag_root;
2676 /* We know the tag root has instances of the given
2679 continue_outer_loop:
2680 g_assert(node != NULL);
2681 while (node->level > 0)
2683 g_assert(node != NULL); /* Failure probably means bad tag summaries. */
2684 node = node->children.node;
2685 while (node != NULL)
2687 if (gtk_text_btree_node_has_tag(node, tag))
2688 goto continue_outer_loop;
2692 g_assert(node != NULL);
2695 g_assert(node != NULL); /* The tag summaries said some node had
2698 g_assert(node->level == 0);
2700 return node->children.line;
2704 /* Looking for any tag at all (tag == NULL).
2705 Unfortunately this can't be done in a simple and efficient way
2706 right now; so I'm just going to return the
2707 first line in the btree. FIXME */
2708 return gtk_text_btree_get_line (tree, 0, NULL);
2713 gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
2716 GtkTextBTreeNode *node;
2717 GtkTextBTreeNode *last_node;
2719 GtkTextTagInfo *info;
2721 g_return_val_if_fail(tree != NULL, NULL);
2725 info = gtk_text_btree_get_existing_tag_info(tree, tag);
2727 if (info->tag_root == NULL)
2730 node = info->tag_root;
2731 /* We know the tag root has instances of the given
2734 while (node->level > 0)
2736 g_assert(node != NULL); /* Failure probably means bad tag summaries. */
2738 node = node->children.node;
2739 while (node != NULL)
2741 if (gtk_text_btree_node_has_tag(node, tag))
2749 g_assert(node != NULL); /* The tag summaries said some node had
2752 g_assert(node->level == 0);
2754 /* Find the last line in this node */
2755 line = node->children.line;
2756 while (line->next != NULL)
2763 /* This search can't be done efficiently at the moment,
2764 at least not without complexity.
2765 So, we just return the last line.
2767 return gtk_text_btree_get_line (tree, -1, NULL);
2777 gtk_text_line_get_number (GtkTextLine *line)
2780 GtkTextBTreeNode *node, *parent, *node2;
2784 * First count how many lines precede this one in its level-0
2788 node = line->parent;
2790 for (line2 = node->children.line; line2 != line;
2791 line2 = line2->next)
2795 g_error("gtk_text_btree_line_number couldn't find line");
2801 * Now work up through the levels of the tree one at a time,
2802 * counting how many lines are in GtkTextBTreeNodes preceding the current
2806 for (parent = node->parent ; parent != NULL;
2807 node = parent, parent = parent->parent)
2809 for (node2 = parent->children.node; node2 != node;
2810 node2 = node2->next)
2814 g_error("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
2816 index += node2->num_lines;
2822 static GtkTextLineSegment*
2823 find_toggle_segment_before_char(GtkTextLine *line,
2827 GtkTextLineSegment *seg;
2828 GtkTextLineSegment *toggle_seg;
2833 seg = line->segments;
2834 while ( (index + seg->char_count) <= char_in_line )
2836 if (((seg->type == >k_text_toggle_on_type)
2837 || (seg->type == >k_text_toggle_off_type))
2838 && (seg->body.toggle.info->tag == tag))
2841 index += seg->char_count;
2848 static GtkTextLineSegment*
2849 find_toggle_segment_before_byte(GtkTextLine *line,
2853 GtkTextLineSegment *seg;
2854 GtkTextLineSegment *toggle_seg;
2859 seg = line->segments;
2860 while ( (index + seg->byte_count) <= byte_in_line )
2862 if (((seg->type == >k_text_toggle_on_type)
2863 || (seg->type == >k_text_toggle_off_type))
2864 && (seg->body.toggle.info->tag == tag))
2867 index += seg->byte_count;
2875 find_toggle_outside_current_line(GtkTextLine *line,
2879 GtkTextBTreeNode *node;
2880 GtkTextLine *sibling_line;
2881 GtkTextLineSegment *seg;
2882 GtkTextLineSegment *toggle_seg;
2884 GtkTextTagInfo *info = NULL;
2887 * No toggle in this line. Look for toggles for the tag in lines
2888 * that are predecessors of line but under the same
2889 * level-0 GtkTextBTreeNode.
2892 sibling_line = line->parent->children.line;
2893 while (sibling_line != line)
2895 seg = sibling_line->segments;
2898 if (((seg->type == >k_text_toggle_on_type)
2899 || (seg->type == >k_text_toggle_off_type))
2900 && (seg->body.toggle.info->tag == tag))
2906 sibling_line = sibling_line->next;
2909 if (toggle_seg != NULL)
2910 return (toggle_seg->type == >k_text_toggle_on_type);
2913 * No toggle in this GtkTextBTreeNode. Scan upwards through the ancestors of
2914 * this GtkTextBTreeNode, counting the number of toggles of the given tag in
2915 * siblings that precede that GtkTextBTreeNode.
2918 info = gtk_text_btree_get_existing_tag_info(tree, tag);
2924 node = line->parent;
2925 while (node->parent != NULL)
2927 GtkTextBTreeNode *sibling_node;
2929 sibling_node = node->parent->children.node;
2930 while (sibling_node != node)
2934 summary = sibling_node->summary;
2935 while (summary != NULL)
2937 if (summary->info == info)
2938 toggles += summary->toggle_count;
2940 summary = summary->next;
2943 sibling_node = sibling_node->next;
2946 if (node == info->tag_root)
2949 node = node->parent;
2953 * An odd number of toggles means that the tag is present at the
2957 return (toggles & 1) != 0;
2960 /* FIXME this function is far too slow, for no good reason. */
2962 gtk_text_line_char_has_tag (GtkTextLine *line,
2967 GtkTextLineSegment *toggle_seg;
2969 g_return_val_if_fail(line != NULL, FALSE);
2972 * Check for toggles for the tag in the line but before
2973 * the char. If there is one, its type indicates whether or
2974 * not the character is tagged.
2977 toggle_seg = find_toggle_segment_before_char(line, char_in_line, tag);
2979 if (toggle_seg != NULL)
2980 return (toggle_seg->type == >k_text_toggle_on_type);
2982 return find_toggle_outside_current_line(line, tree, tag);
2986 gtk_text_line_byte_has_tag (GtkTextLine *line,
2991 GtkTextLineSegment *toggle_seg;
2993 g_return_val_if_fail(line != NULL, FALSE);
2996 * Check for toggles for the tag in the line but before
2997 * the char. If there is one, its type indicates whether or
2998 * not the character is tagged.
3001 toggle_seg = find_toggle_segment_before_byte(line, byte_in_line, tag);
3003 if (toggle_seg != NULL)
3004 return (toggle_seg->type == >k_text_toggle_on_type);
3006 return find_toggle_outside_current_line(line, tree, tag);
3010 gtk_text_line_is_last (GtkTextLine *line,
3013 return line == get_last_line (tree);
3017 gtk_text_line_next (GtkTextLine *line)
3019 GtkTextBTreeNode *node;
3021 if (line->next != NULL)
3026 * This was the last line associated with the particular parent
3027 * GtkTextBTreeNode. Search up the tree for the next GtkTextBTreeNode,
3028 * then search down from that GtkTextBTreeNode to find the first
3032 node = line->parent;
3033 while (node != NULL && node->next == NULL)
3034 node = node->parent;
3040 while (node->level > 0)
3042 node = node->children.node;
3045 g_assert(node->children.line != line);
3047 return node->children.line;
3052 gtk_text_line_previous (GtkTextLine *line)
3054 GtkTextBTreeNode *node;
3055 GtkTextBTreeNode *node2;
3059 * Find the line under this GtkTextBTreeNode just before the starting line.
3061 prev = line->parent->children.line; /* First line at leaf */
3062 while (prev != line)
3064 if (prev->next == line)
3070 g_error("gtk_text_btree_previous_line ran out of lines");
3074 * This was the first line associated with the particular parent
3075 * GtkTextBTreeNode. Search up the tree for the previous GtkTextBTreeNode,
3076 * then search down from that GtkTextBTreeNode to find its last line.
3078 for (node = line->parent; ; node = node->parent)
3080 if (node == NULL || node->parent == NULL)
3082 else if (node != node->parent->children.node)
3086 for (node2 = node->parent->children.node; ;
3087 node2 = node2->children.node)
3089 while (node2->next != node)
3090 node2 = node2->next;
3092 if (node2->level == 0)
3098 for (prev = node2->children.line ; ; prev = prev->next)
3100 if (prev->next == NULL)
3104 g_assert_not_reached ();
3109 gtk_text_line_add_data (GtkTextLine *line,
3110 GtkTextLineData *data)
3112 g_return_if_fail(line != NULL);
3113 g_return_if_fail(data != NULL);
3114 g_return_if_fail(data->view_id != NULL);
3118 data->next = line->views;
3128 gtk_text_line_remove_data (GtkTextLine *line,
3131 GtkTextLineData *prev;
3132 GtkTextLineData *iter;
3134 g_return_val_if_fail(line != NULL, NULL);
3135 g_return_val_if_fail(view_id != NULL, NULL);
3139 while (iter != NULL)
3141 if (iter->view_id == view_id)
3150 prev->next = iter->next;
3152 line->views = iter->next;
3161 gtk_text_line_get_data (GtkTextLine *line,
3164 GtkTextLineData *iter;
3166 g_return_val_if_fail(line != NULL, NULL);
3167 g_return_val_if_fail(view_id != NULL, NULL);
3170 while (iter != NULL)
3172 if (iter->view_id == view_id)
3181 gtk_text_line_invalidate_wrap (GtkTextLine *line,
3182 GtkTextLineData *ld)
3184 /* For now this is totally unoptimized. FIXME?
3186 We could probably optimize the case where the width removed
3187 is less than the max width for the parent node,
3188 and the case where the height is unchanged when we re-wrap.
3191 g_return_if_fail(ld != NULL);
3194 gtk_text_btree_node_invalidate_upward(line->parent, ld->view_id);
3198 gtk_text_line_char_count (GtkTextLine *line)
3200 GtkTextLineSegment *seg;
3204 seg = line->segments;
3207 size += seg->char_count;
3214 gtk_text_line_byte_count (GtkTextLine *line)
3216 GtkTextLineSegment *seg;
3220 seg = line->segments;
3223 size += seg->byte_count;
3231 gtk_text_line_char_index (GtkTextLine *target_line)
3233 GSList *node_stack = NULL;
3234 GtkTextBTreeNode *iter;
3238 /* Push all our parent nodes onto a stack */
3239 iter = target_line->parent;
3241 g_assert(iter != NULL);
3243 while (iter != NULL)
3245 node_stack = g_slist_prepend(node_stack, iter);
3247 iter = iter->parent;
3250 /* Check that we have the root node on top of the stack. */
3251 g_assert(node_stack != NULL &&
3252 node_stack->data != NULL &&
3253 ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3255 /* Add up chars in all nodes before the nodes in our stack.
3259 iter = node_stack->data;
3260 while (iter != NULL)
3262 GtkTextBTreeNode *child_iter;
3263 GtkTextBTreeNode *next_node;
3265 next_node = node_stack->next ?
3266 node_stack->next->data : NULL;
3267 node_stack = g_slist_remove(node_stack, node_stack->data);
3269 if (iter->level == 0)
3271 /* stack should be empty when we're on the last node */
3272 g_assert(node_stack == NULL);
3273 break; /* Our children are now lines */
3276 g_assert(next_node != NULL);
3277 g_assert(iter != NULL);
3278 g_assert(next_node->parent == iter);
3280 /* Add up chars before us in the tree */
3281 child_iter = iter->children.node;
3282 while (child_iter != next_node)
3284 g_assert(child_iter != NULL);
3286 num_chars += child_iter->num_chars;
3288 child_iter = child_iter->next;
3294 g_assert(iter != NULL);
3295 g_assert(iter == target_line->parent);
3297 /* Since we don't store char counts in lines, only in segments, we
3298 have to iterate over the lines adding up segment char counts
3299 until we find our line. */
3300 line = iter->children.line;
3301 while (line != target_line)
3303 g_assert(line != NULL);
3305 num_chars += gtk_text_line_char_count(line);
3310 g_assert(line == target_line);
3316 gtk_text_line_byte_to_segment (GtkTextLine *line,
3320 GtkTextLineSegment *seg;
3323 g_return_val_if_fail(line != NULL, NULL);
3325 offset = byte_offset;
3326 seg = line->segments;
3328 while (offset >= seg->byte_count)
3330 g_assert(seg != NULL); /* means an invalid byte index */
3331 offset -= seg->byte_count;
3336 *seg_offset = offset;
3342 gtk_text_line_char_to_segment (GtkTextLine *line,
3346 GtkTextLineSegment *seg;
3349 g_return_val_if_fail(line != NULL, NULL);
3351 offset = char_offset;
3352 seg = line->segments;
3354 while (offset >= seg->char_count)
3356 g_assert(seg != NULL); /* means an invalid char index */
3357 offset -= seg->char_count;
3362 *seg_offset = offset;
3368 gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3372 GtkTextLineSegment *seg;
3375 g_return_val_if_fail(line != NULL, NULL);
3377 offset = byte_offset;
3378 seg = line->segments;
3380 while (offset > 0 && offset >= seg->byte_count)
3382 g_assert(seg != NULL); /* means an invalid byte index */
3383 offset -= seg->byte_count;
3388 *seg_offset = offset;
3394 gtk_text_line_char_to_any_segment (GtkTextLine *line,
3398 GtkTextLineSegment *seg;
3401 g_return_val_if_fail(line != NULL, NULL);
3403 offset = char_offset;
3404 seg = line->segments;
3406 while (offset > 0 && offset >= seg->char_count)
3408 g_assert(seg != NULL); /* means an invalid byte index */
3409 offset -= seg->char_count;
3414 *seg_offset = offset;
3420 gtk_text_line_byte_to_char (GtkTextLine *line,
3424 GtkTextLineSegment *seg;
3426 g_return_val_if_fail(line != NULL, 0);
3427 g_return_val_if_fail(byte_offset >= 0, 0);
3430 seg = line->segments;
3431 while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3432 the next segment) */
3434 g_assert(seg != NULL); /* our byte_index was bogus if this happens */
3436 byte_offset -= seg->byte_count;
3437 char_offset += seg->char_count;
3442 g_assert(seg != NULL);
3444 /* Now byte_offset is the offset into the current segment,
3445 and char_offset is the start of the current segment.
3446 Optimize the case where no chars use > 1 byte */
3447 if (seg->byte_count == seg->char_count)
3448 return char_offset + byte_offset;
3451 if (seg->type == >k_text_char_type)
3452 return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3455 g_assert(seg->char_count == 1);
3456 g_assert(byte_offset == 0);
3464 gtk_text_line_char_to_byte (GtkTextLine *line,
3467 g_warning("FIXME not implemented");
3472 /* FIXME sync with char_locate (or figure out a clean
3473 way to merge the two functions) */
3475 gtk_text_line_byte_locate (GtkTextLine *line,
3477 GtkTextLineSegment **segment,
3478 GtkTextLineSegment **any_segment,
3479 gint *seg_byte_offset,
3480 gint *line_byte_offset)
3482 GtkTextLineSegment *seg;
3483 GtkTextLineSegment *after_prev_indexable;
3484 GtkTextLineSegment *after_last_indexable;
3485 GtkTextLineSegment *last_indexable;
3489 g_return_if_fail(line != NULL);
3491 if (byte_offset < 0)
3493 /* -1 means end of line; we here assume no line is
3494 longer than 1 bazillion bytes, of course we assumed
3495 that anyway since we'd wrap around... */
3497 byte_offset = G_MAXINT;
3501 *any_segment = NULL;
3504 offset = byte_offset;
3506 last_indexable = NULL;
3507 after_last_indexable = line->segments;
3508 after_prev_indexable = line->segments;
3509 seg = line->segments;
3511 /* The loop ends when we're inside a segment;
3512 last_indexable refers to the last segment
3513 we passed entirely. */
3514 while (seg && offset >= seg->byte_count)
3516 if (seg->char_count > 0)
3518 offset -= seg->byte_count;
3519 bytes_in_line += seg->byte_count;
3520 last_indexable = seg;
3521 after_prev_indexable = after_last_indexable;
3522 after_last_indexable = last_indexable->next;
3530 /* We went off the end of the line */
3531 *segment = last_indexable;
3532 *any_segment = after_prev_indexable;
3533 /* subtracting 1 is OK, we know it's a newline at the end. */
3534 offset = (*segment)->byte_count - 1;
3535 bytes_in_line -= (*segment)->byte_count;
3540 if (after_last_indexable != NULL)
3541 *any_segment = after_last_indexable;
3543 *any_segment = *segment;
3546 /* Override any_segment if we're in the middle of a segment. */
3548 *any_segment = *segment;
3550 *seg_byte_offset = offset;
3552 g_assert(*segment != NULL);
3553 g_assert(*any_segment != NULL);
3554 g_assert(*seg_byte_offset < (*segment)->byte_count);
3556 *line_byte_offset = bytes_in_line + *seg_byte_offset;
3559 /* FIXME sync with byte_locate (or figure out a clean
3560 way to merge the two functions) */
3562 gtk_text_line_char_locate (GtkTextLine *line,
3564 GtkTextLineSegment **segment,
3565 GtkTextLineSegment **any_segment,
3566 gint *seg_char_offset,
3567 gint *line_char_offset)
3569 GtkTextLineSegment *seg;
3570 GtkTextLineSegment *after_prev_indexable;
3571 GtkTextLineSegment *after_last_indexable;
3572 GtkTextLineSegment *last_indexable;
3576 g_return_if_fail(line != NULL);
3578 if (char_offset < 0)
3580 /* -1 means end of line; we here assume no line is
3581 longer than 1 bazillion chars, of course we assumed
3582 that anyway since we'd wrap around... */
3584 char_offset = G_MAXINT;
3588 *any_segment = NULL;
3591 offset = char_offset;
3593 last_indexable = NULL;
3594 after_last_indexable = line->segments;
3595 after_prev_indexable = line->segments;
3596 seg = line->segments;
3598 /* The loop ends when we're inside a segment;
3599 last_indexable refers to the last segment
3600 we passed entirely. */
3601 while (seg && offset >= seg->char_count)
3603 if (seg->char_count > 0)
3605 offset -= seg->char_count;
3606 chars_in_line += seg->char_count;
3607 last_indexable = seg;
3608 after_prev_indexable = after_last_indexable;
3609 after_last_indexable = last_indexable->next;
3617 /* We went off the end of the line */
3618 *segment = last_indexable;
3619 *any_segment = after_prev_indexable;
3620 /* subtracting 1 is OK, we know it's a newline at the end. */
3621 offset = (*segment)->char_count - 1;
3622 chars_in_line -= (*segment)->char_count;
3627 if (after_last_indexable != NULL)
3628 *any_segment = after_last_indexable;
3630 *any_segment = *segment;
3633 /* Override any_segment if we're in the middle of a segment. */
3635 *any_segment = *segment;
3637 *seg_char_offset = offset;
3639 g_assert(*segment != NULL);
3640 g_assert(*any_segment != NULL);
3641 g_assert(*seg_char_offset < (*segment)->char_count);
3643 *line_char_offset = chars_in_line + *seg_char_offset;
3647 gtk_text_line_byte_to_char_offsets(GtkTextLine *line,
3649 gint *line_char_offset,
3650 gint *seg_char_offset)
3652 GtkTextLineSegment *seg;
3655 g_return_if_fail(line != NULL);
3656 g_return_if_fail(byte_offset >= 0);
3658 *line_char_offset = 0;
3660 offset = byte_offset;
3661 seg = line->segments;
3663 while (offset >= seg->byte_count)
3665 offset -= seg->byte_count;
3666 *line_char_offset += seg->char_count;
3668 g_assert(seg != NULL); /* means an invalid char offset */
3671 g_assert(seg->char_count > 0); /* indexable. */
3673 /* offset is now the number of bytes into the current segment we
3674 want to go. Count chars into the current segment. */
3676 if (seg->type == >k_text_char_type)
3678 *seg_char_offset = g_utf8_strlen(seg->body.chars, offset);
3680 g_assert(*seg_char_offset < seg->char_count);
3682 *line_char_offset += *seg_char_offset;
3686 g_assert(offset == 0);
3687 *seg_char_offset = 0;
3692 gtk_text_line_char_to_byte_offsets(GtkTextLine *line,
3694 gint *line_byte_offset,
3695 gint *seg_byte_offset)
3697 GtkTextLineSegment *seg;
3700 g_return_if_fail(line != NULL);
3701 g_return_if_fail(char_offset >= 0);
3703 *line_byte_offset = 0;
3705 offset = char_offset;
3706 seg = line->segments;
3708 while (offset >= seg->char_count)
3710 offset -= seg->char_count;
3711 *line_byte_offset += seg->byte_count;
3713 g_assert(seg != NULL); /* means an invalid char offset */
3716 g_assert(seg->char_count > 0); /* indexable. */
3718 /* offset is now the number of chars into the current segment we
3719 want to go. Count bytes into the current segment. */
3721 if (seg->type == >k_text_char_type)
3723 *seg_byte_offset = 0;
3727 const char * start = seg->body.chars + *seg_byte_offset;
3729 bytes = g_utf8_next_char (start) - start;
3730 *seg_byte_offset += bytes;
3734 g_assert(*seg_byte_offset < seg->byte_count);
3736 *line_byte_offset += *seg_byte_offset;
3740 g_assert(offset == 0);
3741 *seg_byte_offset = 0;
3746 node_compare (GtkTextBTreeNode *lhs,
3747 GtkTextBTreeNode *rhs)
3749 GtkTextBTreeNode *iter;
3750 GtkTextBTreeNode *node;
3751 GtkTextBTreeNode *common_parent;
3752 GtkTextBTreeNode *parent_of_lower;
3753 GtkTextBTreeNode *parent_of_higher;
3754 gboolean lhs_is_lower;
3755 GtkTextBTreeNode *lower;
3756 GtkTextBTreeNode *higher;
3758 /* This function assumes that lhs and rhs are not underneath each
3765 if (lhs->level < rhs->level)
3767 lhs_is_lower = TRUE;
3773 lhs_is_lower = FALSE;
3778 /* Algorithm: find common parent of lhs/rhs. Save the child nodes
3779 * of the common parent we used to reach the common parent; the
3780 * ordering of these child nodes in the child list is the ordering
3784 /* Get on the same level (may be on same level already) */
3786 while (node->level < higher->level)
3787 node = node->parent;
3789 g_assert (node->level == higher->level);
3791 g_assert (node != higher); /* Happens if lower is underneath higher */
3793 /* Go up until we have two children with a common parent.
3795 parent_of_lower = node;
3796 parent_of_higher = higher;
3798 while (parent_of_lower->parent != parent_of_higher->parent)
3800 parent_of_lower = parent_of_lower->parent;
3801 parent_of_higher = parent_of_higher->parent;
3804 g_assert (parent_of_lower->parent == parent_of_higher->parent);
3806 common_parent = parent_of_lower->parent;
3808 g_assert (common_parent != NULL);
3810 /* See which is first in the list of common_parent's children */
3811 iter = common_parent->children.node;
3812 while (iter != NULL)
3814 if (iter == parent_of_higher)
3816 /* higher is less than lower */
3819 return 1; /* lhs > rhs */
3823 else if (iter == parent_of_lower)
3825 /* lower is less than higher */
3828 return -1; /* lhs < rhs */
3836 g_assert_not_reached ();
3840 /* remember that tag == NULL means "any tag" */
3842 gtk_text_line_next_could_contain_tag(GtkTextLine *line,
3846 GtkTextBTreeNode *node;
3847 GtkTextTagInfo *info;
3848 gboolean below_tag_root;
3850 g_return_val_if_fail(line != NULL, NULL);
3852 if (gtk_debug_flags & GTK_DEBUG_TEXT)
3853 gtk_text_btree_check (tree);
3857 /* Right now we can only offer linear-search if the user wants
3858 * to know about any tag toggle at all.
3860 return gtk_text_line_next (line);
3863 /* Our tag summaries only have node precision, not line
3864 precision. This means that if any line under a node could contain a
3865 tag, then any of the others could also contain a tag.
3867 In the future we could have some mechanism to keep track of how
3868 many toggles we've found under a node so far, since we have a
3869 count of toggles under the node. But for now I'm going with KISS.
3872 /* return same-node line, if any. */
3876 info = gtk_text_btree_get_existing_tag_info(tree, tag);
3880 if (info->tag_root == NULL)
3883 if (info->tag_root == line->parent)
3884 return NULL; /* we were at the last line under the tag root */
3886 /* We need to go up out of this node, and on to the next one with
3887 toggles for the target tag. If we're below the tag root, we need to
3888 find the next node below the tag root that has tag summaries. If
3889 we're not below the tag root, we need to see if the tag root is
3890 after us in the tree, and if so, return the first line underneath
3893 node = line->parent;
3894 below_tag_root = FALSE;
3895 while (node != NULL)
3897 if (node == info->tag_root)
3899 below_tag_root = TRUE;
3903 node = node->parent;
3908 node = line->parent;
3909 while (node != info->tag_root)
3911 if (node->next == NULL)
3912 node = node->parent;
3917 if (gtk_text_btree_node_has_tag(node, tag))
3927 ordering = node_compare (line->parent, info->tag_root);
3931 /* Tag root is ahead of us, so search there. */
3932 node = info->tag_root;
3937 /* Tag root is after us, so no more lines that
3938 * could contain the tag.
3943 g_assert_not_reached ();
3948 g_assert(node != NULL);
3950 /* We have to find the first sub-node of this node that contains
3954 while (node->level > 0)
3956 g_assert (node != NULL); /* If this fails, it likely means an
3957 incorrect tag summary led us on a
3958 wild goose chase down this branch of
3960 node = node->children.node;
3961 while (node != NULL)
3963 if (gtk_text_btree_node_has_tag (node, tag))
3969 g_assert (node != NULL);
3970 g_assert (node->level == 0);
3972 return node->children.line;
3976 prev_line_under_node (GtkTextBTreeNode *node,
3981 prev = node->children.line;
3987 while (prev->next != line)
3997 gtk_text_line_previous_could_contain_tag (GtkTextLine *line,
4001 GtkTextBTreeNode *node;
4002 GtkTextBTreeNode *found_node = NULL;
4003 GtkTextTagInfo *info;
4004 gboolean below_tag_root;
4006 GtkTextBTreeNode *line_ancestor;
4007 GtkTextBTreeNode *line_ancestor_parent;
4009 /* See next_could_contain_tag() for more extensive comments
4010 * on what's going on here.
4013 g_return_val_if_fail(line != NULL, NULL);
4015 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4016 gtk_text_btree_check (tree);
4020 /* Right now we can only offer linear-search if the user wants
4021 * to know about any tag toggle at all.
4023 return gtk_text_line_previous (line);
4026 /* Return same-node line, if any. */
4027 prev = prev_line_under_node (line->parent, line);
4031 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4035 if (info->tag_root == NULL)
4038 if (info->tag_root == line->parent)
4039 return NULL; /* we were at the first line under the tag root */
4041 /* Are we below the tag root */
4042 node = line->parent;
4043 below_tag_root = FALSE;
4044 while (node != NULL)
4046 if (node == info->tag_root)
4048 below_tag_root = TRUE;
4052 node = node->parent;
4057 /* Look for a previous node under this tag root that has our
4061 /* this assertion holds because line->parent is not the
4062 * tag root, we are below the tag root, and the tag
4065 g_assert (line->parent->parent != NULL);
4067 line_ancestor = line->parent;
4068 line_ancestor_parent = line->parent->parent;
4070 node = line_ancestor_parent->children.node;
4071 while (node != line_ancestor &&
4072 line_ancestor != info->tag_root)
4074 GSList *child_nodes = NULL;
4077 /* Create reverse-order list of nodes before
4080 while (node != line_ancestor
4083 child_nodes = g_slist_prepend (child_nodes, node);
4088 /* Try to find a node with our tag on it in the list */
4092 GtkTextBTreeNode *this_node = tmp->data;
4094 g_assert (this_node != line_ancestor);
4096 if (gtk_text_btree_node_has_tag (this_node, tag))
4098 found_node = this_node;
4099 g_slist_free (child_nodes);
4103 tmp = g_slist_next (tmp);
4106 g_slist_free (child_nodes);
4108 /* Didn't find anything on this level; go up one level. */
4109 line_ancestor = line_ancestor_parent;
4110 line_ancestor_parent = line_ancestor->parent;
4112 node = line_ancestor_parent->children.node;
4122 ordering = node_compare (line->parent, info->tag_root);
4126 /* Tag root is ahead of us, so no more lines
4133 /* Tag root is after us, so grab last tagged
4134 * line underneath the tag root.
4136 found_node = info->tag_root;
4140 g_assert_not_reached ();
4145 g_assert (found_node != NULL);
4147 /* We have to find the last sub-node of this node that contains
4152 while (node->level > 0)
4154 GSList *child_nodes = NULL;
4156 g_assert (node != NULL); /* If this fails, it likely means an
4157 incorrect tag summary led us on a
4158 wild goose chase down this branch of
4161 node = node->children.node;
4162 while (node != NULL)
4164 child_nodes = g_slist_prepend (child_nodes, node);
4168 node = NULL; /* detect failure to find a child node. */
4171 while (iter != NULL)
4173 if (gtk_text_btree_node_has_tag (iter->data, tag))
4175 /* recurse into this node. */
4180 iter = g_slist_next (iter);
4183 g_slist_free (child_nodes);
4185 g_assert (node != NULL);
4188 g_assert (node != NULL);
4189 g_assert (node->level == 0);
4191 /* this assertion is correct, but slow. */
4192 /* g_assert (node_compare (node, line->parent) < 0); */
4194 /* Return last line in this node. */
4196 prev = node->children.line;
4204 * Non-public function implementations
4208 summary_list_destroy(Summary *summary)
4211 while (summary != NULL)
4213 next = summary->next;
4214 summary_destroy (summary);
4220 get_last_line(GtkTextBTree *tree)
4222 if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
4228 n_lines = gtk_text_btree_line_count(tree);
4230 g_assert(n_lines >= 1); /* num_lines doesn't return bogus last line. */
4232 line = gtk_text_btree_get_line(tree, n_lines, &real_line);
4234 tree->end_iter_line_stamp = tree->chars_changed_stamp;
4235 tree->end_iter_line = line;
4238 return tree->end_iter_line;
4246 gtk_text_line_new(void)
4250 line = g_new0(GtkTextLine, 1);
4256 gtk_text_line_destroy(GtkTextBTree *tree, GtkTextLine *line)
4258 GtkTextLineData *ld;
4259 GtkTextLineData *next;
4261 g_return_if_fail(line != NULL);
4268 view = gtk_text_btree_get_view (tree, ld->view_id);
4270 g_assert(view != NULL);
4273 gtk_text_layout_free_line_data (view->layout, line, ld);
4282 gtk_text_line_set_parent(GtkTextLine *line,
4283 GtkTextBTreeNode *node)
4285 if (line->parent == node)
4287 line->parent = node;
4288 gtk_text_btree_node_invalidate_upward(node, NULL);
4292 cleanup_line(GtkTextLine *line)
4294 GtkTextLineSegment *seg, **prev_p;
4298 * Make a pass over all of the segments in the line, giving each
4299 * a chance to clean itself up. This could potentially change
4300 * the structure of the line, e.g. by merging two segments
4301 * together or having two segments cancel themselves; if so,
4302 * then repeat the whole process again, since the first structure
4303 * change might make other structure changes possible. Repeat
4304 * until eventually there are no changes.
4311 for (prev_p = &line->segments, seg = *prev_p;
4313 prev_p = &(*prev_p)->next, seg = *prev_p)
4315 if (seg->type->cleanupFunc != NULL)
4317 *prev_p = (*seg->type->cleanupFunc)(seg, line);
4330 node_data_new(gpointer view_id)
4334 nd = g_new(NodeData, 1);
4336 nd->view_id = view_id;
4346 node_data_destroy(NodeData *nd)
4353 node_data_list_destroy(NodeData *nd)
4359 while (iter != NULL)
4362 node_data_destroy(iter);
4368 node_data_find(NodeData *nd, gpointer view_id)
4372 if (nd->view_id == view_id)
4380 summary_destroy (Summary *summary)
4382 /* Fill with error-triggering garbage */
4383 summary->info = (void*)0x1;
4384 summary->toggle_count = 567;
4385 summary->next = (void*)0x1;
4389 static GtkTextBTreeNode*
4390 gtk_text_btree_node_new(void)
4392 GtkTextBTreeNode *node;
4394 node = g_new(GtkTextBTreeNode, 1);
4396 node->node_data = NULL;
4402 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
4403 GtkTextTagInfo *info,
4408 summary = node->summary;
4409 while (summary != NULL)
4411 if (summary->info == info)
4413 summary->toggle_count += adjust;
4417 summary = summary->next;
4420 if (summary == NULL)
4422 /* didn't find a summary for our tag. */
4423 g_return_if_fail(adjust > 0);
4424 summary = g_new(Summary, 1);
4425 summary->info = info;
4426 summary->toggle_count = adjust;
4427 summary->next = node->summary;
4428 node->summary = summary;
4432 /* Note that the tag root and above do not have summaries
4433 for the tag; only nodes below the tag root have
4436 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4440 summary = node->summary;
4441 while (summary != NULL)
4444 summary->info->tag == tag)
4447 summary = summary->next;
4453 /* Add node and all children to the damage region. */
4455 gtk_text_btree_node_invalidate_downward(GtkTextBTreeNode *node)
4459 nd = node->node_data;
4466 if (node->level == 0)
4470 line = node->children.line;
4471 while (line != NULL)
4473 GtkTextLineData *ld;
4487 GtkTextBTreeNode *child;
4489 child = node->children.node;
4491 while (child != NULL)
4493 gtk_text_btree_node_invalidate_downward(child);
4495 child = child->next;
4501 gtk_text_btree_node_invalidate_upward(GtkTextBTreeNode *node, gpointer view_id)
4503 GtkTextBTreeNode *iter;
4506 while (iter != NULL)
4512 nd = node_data_find (iter->node_data, view_id);
4514 if (nd == NULL || !nd->valid)
4515 break; /* Once a node is invalid, we know its parents are as well. */
4521 gboolean should_continue = FALSE;
4523 nd = iter->node_data;
4528 should_continue = TRUE;
4535 if (!should_continue)
4536 break; /* This node was totally invalidated, so are its
4540 iter = iter->parent;
4546 * gtk_text_btree_is_valid:
4547 * @tree: a #GtkTextBTree
4548 * @view_id: ID for the view
4550 * Check to see if the entire #GtkTextBTree is valid or not for
4553 * Return value: %TRUE if the entire #GtkTextBTree is valid
4556 gtk_text_btree_is_valid (GtkTextBTree *tree,
4560 g_return_val_if_fail (tree != NULL, FALSE);
4562 nd = node_data_find (tree->root_node->node_data, view_id);
4563 return (nd && nd->valid);
4566 typedef struct _ValidateState ValidateState;
4568 struct _ValidateState
4570 gint remaining_pixels;
4571 gboolean in_validation;
4578 gtk_text_btree_node_validate (BTreeView *view,
4579 GtkTextBTreeNode *node,
4581 ValidateState *state)
4583 gint node_valid = TRUE;
4584 gint node_width = 0;
4585 gint node_height = 0;
4587 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4588 g_return_if_fail (!nd->valid);
4590 if (node->level == 0)
4592 GtkTextLine *line = node->children.line;
4593 GtkTextLineData *ld;
4595 /* Iterate over leading valid lines */
4596 while (line != NULL)
4598 ld = gtk_text_line_get_data (line, view_id);
4600 if (!ld || !ld->valid)
4602 else if (state->in_validation)
4604 state->in_validation = FALSE;
4609 state->y += ld->height;
4610 node_width = MAX (ld->width, node_width);
4611 node_height += ld->height;
4617 state->in_validation = TRUE;
4619 /* Iterate over invalid lines */
4620 while (line != NULL)
4622 ld = gtk_text_line_get_data (line, view_id);
4624 if (ld && ld->valid)
4629 state->old_height += ld->height;
4630 ld = gtk_text_layout_wrap (view->layout, line, ld);
4631 state->new_height += ld->height;
4633 node_width = MAX (ld->width, node_width);
4634 node_height += ld->height;
4636 state->remaining_pixels -= ld->height;
4637 if (state->remaining_pixels <= 0)
4647 /* Iterate over the remaining lines */
4648 while (line != NULL)
4650 ld = gtk_text_line_get_data (line, view_id);
4651 state->in_validation = FALSE;
4653 if (!ld || !ld->valid)
4658 node_width = MAX (ld->width, node_width);
4659 node_height += ld->height;
4667 GtkTextBTreeNode *child;
4670 child = node->children.node;
4672 /* Iterate over leading valid nodes */
4675 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4677 if (!child_nd->valid)
4679 else if (state->in_validation)
4681 state->in_validation = FALSE;
4686 state->y += child_nd->height;
4687 node_width = MAX (node_width, child_nd->width);
4688 node_height += child_nd->height;
4691 child = child->next;
4694 /* Iterate over invalid nodes */
4697 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4699 if (child_nd->valid)
4703 gtk_text_btree_node_validate (view, child, view_id, state);
4705 if (!child_nd->valid)
4707 node_width = MAX (node_width, child_nd->width);
4708 node_height += child_nd->height;
4710 if (!state->in_validation || state->remaining_pixels <= 0)
4712 child = child->next;
4717 child = child->next;
4720 /* Iterate over the remaining lines */
4723 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4724 state->in_validation = FALSE;
4726 if (!child_nd->valid)
4729 node_width = MAX (child_nd->width, node_width);
4730 node_height += child_nd->height;
4732 child = child->next;
4736 nd->width = node_width;
4737 nd->height = node_height;
4738 nd->valid = node_valid;
4742 * gtk_text_btree_validate:
4743 * @tree: a #GtkTextBTree
4745 * @max_pixels: the maximum number of pixels to validate. (No more
4746 * than one paragraph beyond this limit will be validated)
4747 * @y: location to store starting y coordinate of validated region
4748 * @old_height: location to store old height of validated region
4749 * @new_height: location to store new height of validated region
4751 * Validate a single contiguous invalid region of a #GtkTextBTree for
4754 * Return value: %TRUE if a region has been validated, %FALSE if the
4755 * entire tree was already valid.
4758 gtk_text_btree_validate (GtkTextBTree *tree,
4767 g_return_val_if_fail (tree != NULL, FALSE);
4769 view = gtk_text_btree_get_view (tree, view_id);
4770 g_return_val_if_fail (view != NULL, FALSE);
4772 if (!gtk_text_btree_is_valid (tree, view_id))
4774 ValidateState state;
4776 state.remaining_pixels = max_pixels;
4777 state.in_validation = FALSE;
4779 state.old_height = 0;
4780 state.new_height = 0;
4782 gtk_text_btree_node_validate (view,
4789 *old_height = state.old_height;
4791 *new_height = state.new_height;
4793 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4794 gtk_text_btree_check(tree);
4803 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
4807 gboolean *valid_out)
4811 gboolean valid = TRUE;
4813 if (node->level == 0)
4815 GtkTextLine *line = node->children.line;
4817 while (line != NULL)
4819 GtkTextLineData *ld = gtk_text_line_get_data (line, view_id);
4821 if (!ld || !ld->valid)
4826 width = MAX (ld->width, width);
4827 height += ld->height;
4835 GtkTextBTreeNode *child = node->children.node;
4839 NodeData *child_nd = node_data_find (child->node_data, view_id);
4841 if (!child_nd || !child_nd->valid)
4846 width = MAX (child_nd->width, width);
4847 height += child_nd->height;
4850 child = child->next;
4855 *height_out = height;
4860 /* Recompute the validity and size of the view data for a given
4861 * view at this node from the immediate children of the node
4864 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
4867 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4872 gtk_text_btree_node_compute_view_aggregates (node, view_id,
4873 &width, &height, &valid);
4875 nd->height = height;
4882 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
4887 gtk_text_btree_node_check_valid (node, view_id);
4888 node = node->parent;
4893 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
4896 if (node->level == 0)
4898 return gtk_text_btree_node_check_valid (node, view_id);
4902 GtkTextBTreeNode *child = node->children.node;
4904 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4912 NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
4914 if (!child_nd->valid)
4916 nd->width = MAX (child_nd->width, nd->width);
4917 nd->height += child_nd->height;
4919 child = child->next;
4928 * gtk_text_btree_validate_line:
4929 * @tree: a #GtkTextBTree
4930 * @line: line to validate
4931 * @view_id: view ID for the view to validate
4933 * Revalidate a single line of the btree for the given view, propagate
4934 * results up through the entire tree.
4937 gtk_text_btree_validate_line (GtkTextBTree *tree,
4941 GtkTextLineData *ld;
4942 GtkTextLine *last_line;
4945 g_return_if_fail (tree != NULL);
4946 g_return_if_fail (line != NULL);
4948 view = gtk_text_btree_get_view (tree, view_id);
4949 g_return_if_fail (view != NULL);
4951 ld = gtk_text_line_get_data(line, view_id);
4952 if (!ld || !ld->valid)
4954 ld = gtk_text_layout_wrap (view->layout, line, ld);
4955 last_line = get_last_line (tree);
4957 gtk_text_btree_node_check_valid_upward (line->parent, view_id);
4962 gtk_text_btree_node_remove_view(BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
4964 if (node->level == 0)
4968 line = node->children.line;
4969 while (line != NULL)
4971 GtkTextLineData *ld;
4973 ld = gtk_text_line_remove_data(line, view_id);
4976 gtk_text_layout_free_line_data (view->layout, line, ld);
4983 GtkTextBTreeNode *child;
4985 child = node->children.node;
4987 while (child != NULL)
4990 gtk_text_btree_node_remove_view(view, child, view_id);
4992 child = child->next;
4996 gtk_text_btree_node_remove_data(node, view_id);
5000 gtk_text_btree_node_destroy(GtkTextBTree *tree, GtkTextBTreeNode *node)
5002 if (node->level == 0)
5005 GtkTextLineSegment *seg;
5007 while (node->children.line != NULL)
5009 line = node->children.line;
5010 node->children.line = line->next;
5011 while (line->segments != NULL)
5013 seg = line->segments;
5014 line->segments = seg->next;
5016 if (GTK_IS_TEXT_MARK_SEGMENT (seg))
5018 /* Set the mark as deleted */
5019 seg->body.mark.tree = NULL;
5020 seg->body.mark.line = NULL;
5023 (*seg->type->deleteFunc) (seg, line, 1);
5025 gtk_text_line_destroy(tree, line);
5030 GtkTextBTreeNode *childPtr;
5032 while (node->children.node != NULL)
5034 childPtr = node->children.node;
5035 node->children.node = childPtr->next;
5036 gtk_text_btree_node_destroy (tree, childPtr);
5040 summary_list_destroy (node->summary);
5041 node_data_list_destroy (node->node_data);
5046 gtk_text_btree_node_ensure_data(GtkTextBTreeNode *node, gpointer view_id)
5050 nd = node->node_data;
5053 if (nd->view_id == view_id)
5060 nd = node_data_new(view_id);
5062 if (node->node_data)
5063 nd->next = node->node_data;
5065 node->node_data = nd;
5072 gtk_text_btree_node_remove_data(GtkTextBTreeNode *node, gpointer view_id)
5078 nd = node->node_data;
5081 if (nd->view_id == view_id)
5092 prev->next = nd->next;
5094 if (node->node_data == nd)
5095 node->node_data = nd->next;
5099 node_data_destroy(nd);
5103 gtk_text_btree_node_get_size(GtkTextBTreeNode *node, gpointer view_id,
5104 gint *width, gint *height)
5108 g_return_if_fail(width != NULL);
5109 g_return_if_fail(height != NULL);
5111 nd = gtk_text_btree_node_ensure_data(node, view_id);
5116 *height = nd->height;
5119 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5120 * here isn't quite right, since for a lot of operations we want to
5121 * know which children of the common parent correspond to the two nodes
5122 * (e.g., when computing the order of two iters)
5124 static GtkTextBTreeNode *
5125 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5126 GtkTextBTreeNode *node2)
5128 while (node1->level < node2->level)
5129 node1 = node1->parent;
5130 while (node2->level < node1->level)
5131 node2 = node2->parent;
5132 while (node1 != node2)
5134 node1 = node1->parent;
5135 node2 = node2->parent;
5146 gtk_text_btree_get_view(GtkTextBTree *tree, gpointer view_id)
5151 while (view != NULL)
5153 if (view->view_id == view_id)
5162 get_tree_bounds(GtkTextBTree *tree,
5166 gtk_text_btree_get_iter_at_line_char(tree, start, 0, 0);
5167 gtk_text_btree_get_last_iter(tree, end);
5171 tag_changed_cb (GtkTextTagTable *table,
5173 gboolean size_changed,
5178 /* We need to queue a relayout on all regions that are tagged with
5185 if (gtk_text_btree_get_iter_at_first_toggle(tree, &start, tag))
5187 /* Must be a last toggle if there was a first one. */
5188 gtk_text_btree_get_iter_at_last_toggle (tree, &end, tag);
5189 gtk_text_btree_invalidate_region (tree,
5196 /* We only need to queue a redraw, not a relayout */
5201 while (view != NULL)
5205 gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5206 gtk_text_layout_changed (view->layout, 0, height, height);
5214 tag_removed_cb(GtkTextTagTable *table,
5218 /* Remove the tag from the tree */
5223 get_tree_bounds(tree, &start, &end);
5225 gtk_text_btree_tag(&start, &end, tag, FALSE);
5226 gtk_text_btree_remove_tag_info (tree, tag);
5230 /* Rebalance the out-of-whack node "node" */
5232 gtk_text_btree_rebalance(GtkTextBTree *tree,
5233 GtkTextBTreeNode *node)
5236 * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5237 * up through the tree one GtkTextBTreeNode at a time until the root
5238 * GtkTextBTreeNode has been processed.
5241 while (node != NULL)
5243 GtkTextBTreeNode *new_node, *child;
5248 * Check to see if the GtkTextBTreeNode has too many children. If it does,
5249 * then split off all but the first MIN_CHILDREN into a separate
5250 * GtkTextBTreeNode following the original one. Then repeat until the
5251 * GtkTextBTreeNode has a decent size.
5254 if (node->num_children > MAX_CHILDREN)
5259 * If the GtkTextBTreeNode being split is the root
5260 * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5264 if (node->parent == NULL)
5266 new_node = gtk_text_btree_node_new();
5267 new_node->parent = NULL;
5268 new_node->next = NULL;
5269 new_node->summary = NULL;
5270 new_node->level = node->level + 1;
5271 new_node->children.node = node;
5272 recompute_node_counts(tree, new_node);
5273 tree->root_node = new_node;
5275 new_node = gtk_text_btree_node_new();
5276 new_node->parent = node->parent;
5277 new_node->next = node->next;
5278 node->next = new_node;
5279 new_node->summary = NULL;
5280 new_node->level = node->level;
5281 new_node->num_children = node->num_children - MIN_CHILDREN;
5282 if (node->level == 0)
5284 for (i = MIN_CHILDREN-1,
5285 line = node->children.line;
5286 i > 0; i--, line = line->next)
5288 /* Empty loop body. */
5290 new_node->children.line = line->next;
5295 for (i = MIN_CHILDREN-1,
5296 child = node->children.node;
5297 i > 0; i--, child = child->next)
5299 /* Empty loop body. */
5301 new_node->children.node = child->next;
5304 recompute_node_counts(tree, node);
5305 node->parent->num_children++;
5307 if (node->num_children <= MAX_CHILDREN)
5309 recompute_node_counts(tree, node);
5315 while (node->num_children < MIN_CHILDREN)
5317 GtkTextBTreeNode *other;
5318 GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5319 GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5320 int total_children, first_children, i;
5323 * Too few children for this GtkTextBTreeNode. If this is the root then,
5324 * it's OK for it to have less than MIN_CHILDREN children
5325 * as long as it's got at least two. If it has only one
5326 * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5327 * the tree and use its child as the new root.
5330 if (node->parent == NULL)
5332 if ((node->num_children == 1) && (node->level > 0))
5334 tree->root_node = node->children.node;
5335 tree->root_node->parent = NULL;
5336 summary_list_destroy(node->summary);
5343 * Not the root. Make sure that there are siblings to
5347 if (node->parent->num_children < 2)
5349 gtk_text_btree_rebalance(tree, node->parent);
5354 * Find a sibling neighbor to borrow from, and arrange for
5355 * node to be the earlier of the pair.
5358 if (node->next == NULL)
5360 for (other = node->parent->children.node;
5361 other->next != node;
5362 other = other->next)
5364 /* Empty loop body. */
5371 * We're going to either merge the two siblings together
5372 * into one GtkTextBTreeNode or redivide the children among them to
5373 * balance their loads. As preparation, join their two
5374 * child lists into a single list and remember the half-way
5375 * point in the list.
5378 total_children = node->num_children + other->num_children;
5379 first_children = total_children/2;
5380 if (node->children.node == NULL)
5382 node->children = other->children;
5383 other->children.node = NULL;
5384 other->children.line = NULL;
5386 if (node->level == 0)
5390 for (line = node->children.line, i = 1;
5392 line = line->next, i++)
5394 if (i == first_children)
5399 line->next = other->children.line;
5400 while (i <= first_children)
5409 GtkTextBTreeNode *child;
5411 for (child = node->children.node, i = 1;
5412 child->next != NULL;
5413 child = child->next, i++)
5415 if (i <= first_children)
5417 if (i == first_children)
5419 halfwaynode = child;
5423 child->next = other->children.node;
5424 while (i <= first_children)
5426 halfwaynode = child;
5427 child = child->next;
5433 * If the two siblings can simply be merged together, do it.
5436 if (total_children <= MAX_CHILDREN)
5438 recompute_node_counts(tree, node);
5439 node->next = other->next;
5440 node->parent->num_children--;
5441 summary_list_destroy(other->summary);
5447 * The siblings can't be merged, so just divide their
5448 * children evenly between them.
5451 if (node->level == 0)
5453 other->children.line = halfwayline->next;
5454 halfwayline->next = NULL;
5458 other->children.node = halfwaynode->next;
5459 halfwaynode->next = NULL;
5462 recompute_node_counts(tree, node);
5463 recompute_node_counts(tree, other);
5466 node = node->parent;
5471 post_insert_fixup(GtkTextBTree *tree,
5473 gint line_count_delta,
5474 gint char_count_delta)
5477 GtkTextBTreeNode *node;
5480 * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5481 * point, then rebalance the tree if necessary.
5484 for (node = line->parent ; node != NULL;
5485 node = node->parent)
5487 node->num_lines += line_count_delta;
5488 node->num_chars += char_count_delta;
5490 node = line->parent;
5491 node->num_children += line_count_delta;
5493 if (node->num_children > MAX_CHILDREN)
5495 gtk_text_btree_rebalance(tree, node);
5498 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5499 gtk_text_btree_check(tree);
5502 static GtkTextTagInfo*
5503 gtk_text_btree_get_existing_tag_info(GtkTextBTree *tree,
5506 GtkTextTagInfo *info;
5510 list = tree->tag_infos;
5511 while (list != NULL)
5514 if (info->tag == tag)
5517 list = g_slist_next(list);
5523 static GtkTextTagInfo*
5524 gtk_text_btree_get_tag_info(GtkTextBTree *tree,
5527 GtkTextTagInfo *info;
5529 info = gtk_text_btree_get_existing_tag_info(tree, tag);
5533 /* didn't find it, create. */
5535 info = g_new(GtkTextTagInfo, 1);
5538 gtk_object_ref(GTK_OBJECT(tag));
5539 info->tag_root = NULL;
5540 info->toggle_count = 0;
5542 tree->tag_infos = g_slist_prepend(tree->tag_infos, info);
5549 gtk_text_btree_remove_tag_info(GtkTextBTree *tree,
5552 GtkTextTagInfo *info;
5557 list = tree->tag_infos;
5558 while (list != NULL)
5561 if (info->tag == tag)
5565 prev->next = list->next;
5569 tree->tag_infos = list->next;
5574 gtk_object_unref(GTK_OBJECT(info->tag));
5580 list = g_slist_next(list);
5583 g_assert_not_reached();
5588 recompute_level_zero_counts(GtkTextBTreeNode *node)
5591 GtkTextLineSegment *seg;
5593 g_assert(node->level == 0);
5595 line = node->children.line;
5596 while (line != NULL)
5598 node->num_children++;
5601 if (line->parent != node)
5602 gtk_text_line_set_parent(line, node);
5604 seg = line->segments;
5608 node->num_chars += seg->char_count;
5610 if (((seg->type != >k_text_toggle_on_type)
5611 && (seg->type != >k_text_toggle_off_type))
5612 || !(seg->body.toggle.inNodeCounts))
5618 GtkTextTagInfo *info;
5620 info = seg->body.toggle.info;
5622 gtk_text_btree_node_adjust_toggle_count(node, info, 1);
5633 recompute_level_nonzero_counts(GtkTextBTreeNode *node)
5636 GtkTextBTreeNode *child;
5638 g_assert(node->level > 0);
5640 child = node->children.node;
5641 while (child != NULL)
5643 node->num_children += 1;
5644 node->num_lines += child->num_lines;
5645 node->num_chars += child->num_chars;
5647 if (child->parent != node)
5649 child->parent = node;
5650 gtk_text_btree_node_invalidate_upward(node, NULL);
5653 summary = child->summary;
5654 while (summary != NULL)
5656 gtk_text_btree_node_adjust_toggle_count(node,
5658 summary->toggle_count);
5660 summary = summary->next;
5663 child = child->next;
5668 *----------------------------------------------------------------------
5670 * recompute_node_counts --
5672 * This procedure is called to recompute all the counts in a GtkTextBTreeNode
5673 * (tags, child information, etc.) by scanning the information in
5674 * its descendants. This procedure is called during rebalancing
5675 * when a GtkTextBTreeNode's child structure has changed.
5681 * The tag counts for node are modified to reflect its current
5682 * child structure, as are its num_children, num_lines, num_chars fields.
5683 * Also, all of the childrens' parent fields are made to point
5686 *----------------------------------------------------------------------
5690 recompute_node_counts(GtkTextBTree *tree, GtkTextBTreeNode *node)
5693 Summary *summary, *summary2;
5696 * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
5697 * the existing Summary records (most of them will probably be reused).
5700 summary = node->summary;
5701 while (summary != NULL)
5703 summary->toggle_count = 0;
5704 summary = summary->next;
5707 node->num_children = 0;
5708 node->num_lines = 0;
5709 node->num_chars = 0;
5712 * Scan through the children, adding the childrens' tag counts into
5713 * the GtkTextBTreeNode's tag counts and adding new Summary structures if
5717 if (node->level == 0)
5718 recompute_level_zero_counts(node);
5720 recompute_level_nonzero_counts(node);
5725 gtk_text_btree_node_check_valid (node, view->view_id);
5730 * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
5731 * records that still have a zero count, or that have all the toggles.
5732 * The GtkTextBTreeNode with the children that account for all the tags toggles
5733 * have no summary information, and they become the tag_root for the tag.
5737 for (summary = node->summary; summary != NULL; )
5739 if (summary->toggle_count > 0 &&
5740 summary->toggle_count < summary->info->toggle_count)
5742 if (node->level == summary->info->tag_root->level)
5745 * The tag's root GtkTextBTreeNode split and some toggles left.
5746 * The tag root must move up a level.
5748 summary->info->tag_root = node->parent;
5751 summary = summary->next;
5754 if (summary->toggle_count == summary->info->toggle_count)
5757 * A GtkTextBTreeNode merge has collected all the toggles under
5758 * one GtkTextBTreeNode. Push the root down to this level.
5760 summary->info->tag_root = node;
5762 if (summary2 != NULL)
5764 summary2->next = summary->next;
5765 summary_destroy (summary);
5766 summary = summary2->next;
5770 node->summary = summary->next;
5771 summary_destroy (summary);
5772 summary = node->summary;
5778 _gtk_change_node_toggle_count(GtkTextBTreeNode *node,
5779 GtkTextTagInfo *info,
5780 gint delta) /* may be negative */
5782 Summary *summary, *prevPtr;
5783 GtkTextBTreeNode *node2Ptr;
5784 int rootLevel; /* Level of original tag root */
5786 info->toggle_count += delta;
5788 if (info->tag_root == (GtkTextBTreeNode *) NULL)
5790 info->tag_root = node;
5795 * Note the level of the existing root for the tag so we can detect
5796 * if it needs to be moved because of the toggle count change.
5799 rootLevel = info->tag_root->level;
5802 * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
5803 * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
5807 for ( ; node != info->tag_root; node = node->parent)
5810 * See if there's already an entry for this tag for this GtkTextBTreeNode. If so,
5811 * perhaps all we have to do is adjust its count.
5814 for (prevPtr = NULL, summary = node->summary;
5816 prevPtr = summary, summary = summary->next)
5818 if (summary->info == info)
5823 if (summary != NULL)
5825 summary->toggle_count += delta;
5826 if (summary->toggle_count > 0 &&
5827 summary->toggle_count < info->toggle_count)
5831 if (summary->toggle_count != 0)
5834 * Should never find a GtkTextBTreeNode with max toggle count at this
5835 * point (there shouldn't have been a summary entry in the
5839 g_error("%s: bad toggle count (%d) max (%d)",
5840 G_STRLOC, summary->toggle_count, info->toggle_count);
5844 * Zero toggle count; must remove this tag from the list.
5847 if (prevPtr == NULL)
5849 node->summary = summary->next;
5853 prevPtr->next = summary->next;
5855 summary_destroy (summary);
5860 * This tag isn't currently in the summary information list.
5863 if (rootLevel == node->level)
5867 * The old tag root is at the same level in the tree as this
5868 * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode. Move the tag root up
5869 * a level, in the hopes that it will now cover this GtkTextBTreeNode
5870 * as well as the old root (if not, we'll move it up again
5871 * the next time through the loop). To push it up one level
5872 * we copy the original toggle count into the summary
5873 * information at the old root and change the root to its
5874 * parent GtkTextBTreeNode.
5877 GtkTextBTreeNode *rootnode = info->tag_root;
5878 summary = (Summary *) g_malloc(sizeof(Summary));
5879 summary->info = info;
5880 summary->toggle_count = info->toggle_count - delta;
5881 summary->next = rootnode->summary;
5882 rootnode->summary = summary;
5883 rootnode = rootnode->parent;
5884 rootLevel = rootnode->level;
5885 info->tag_root = rootnode;
5887 summary = (Summary *) g_malloc(sizeof(Summary));
5888 summary->info = info;
5889 summary->toggle_count = delta;
5890 summary->next = node->summary;
5891 node->summary = summary;
5896 * If we've decremented the toggle count, then it may be necessary
5897 * to push the tag root down one or more levels.
5904 if (info->toggle_count == 0)
5906 info->tag_root = (GtkTextBTreeNode *) NULL;
5909 node = info->tag_root;
5910 while (node->level > 0)
5913 * See if a single child GtkTextBTreeNode accounts for all of the tag's
5914 * toggles. If so, push the root down one level.
5917 for (node2Ptr = node->children.node;
5918 node2Ptr != (GtkTextBTreeNode *)NULL ;
5919 node2Ptr = node2Ptr->next)
5921 for (prevPtr = NULL, summary = node2Ptr->summary;
5923 prevPtr = summary, summary = summary->next)
5925 if (summary->info == info)
5930 if (summary == NULL)
5934 if (summary->toggle_count != info->toggle_count)
5937 * No GtkTextBTreeNode has all toggles, so the root is still valid.
5944 * This GtkTextBTreeNode has all the toggles, so push down the root.
5947 if (prevPtr == NULL)
5949 node2Ptr->summary = summary->next;
5953 prevPtr->next = summary->next;
5955 summary_destroy (summary);
5956 info->tag_root = node2Ptr;
5959 node = info->tag_root;
5964 *----------------------------------------------------------------------
5968 * This is a utility procedure used by gtk_text_btree_get_tags. It
5969 * increments the count for a particular tag, adding a new
5970 * entry for that tag if there wasn't one previously.
5976 * The information at *tagInfoPtr may be modified, and the arrays
5977 * may be reallocated to make them larger.
5979 *----------------------------------------------------------------------
5983 inc_count(GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
5988 for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
5989 count > 0; tag_p++, count--)
5993 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
5999 * There isn't currently an entry for this tag, so we have to
6000 * make a new one. If the arrays are full, then enlarge the
6004 if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
6006 GtkTextTag **newTags;
6007 int *newCounts, newSize;
6009 newSize = 2*tagInfoPtr->arraySize;
6010 newTags = (GtkTextTag **) g_malloc((unsigned)
6011 (newSize*sizeof(GtkTextTag *)));
6012 memcpy((void *) newTags, (void *) tagInfoPtr->tags,
6013 tagInfoPtr->arraySize *sizeof(GtkTextTag *));
6014 g_free((char *) tagInfoPtr->tags);
6015 tagInfoPtr->tags = newTags;
6016 newCounts = (int *) g_malloc((unsigned) (newSize*sizeof(int)));
6017 memcpy((void *) newCounts, (void *) tagInfoPtr->counts,
6018 tagInfoPtr->arraySize *sizeof(int));
6019 g_free((char *) tagInfoPtr->counts);
6020 tagInfoPtr->counts = newCounts;
6021 tagInfoPtr->arraySize = newSize;
6024 tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
6025 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
6026 tagInfoPtr->numTags++;
6030 gtk_text_btree_link_segment(GtkTextLineSegment *seg,
6031 const GtkTextIter *iter)
6033 GtkTextLineSegment *prev;
6037 line = gtk_text_iter_get_text_line(iter);
6038 tree = gtk_text_iter_get_btree(iter);
6040 prev = gtk_text_line_segment_split(iter);
6043 seg->next = line->segments;
6044 line->segments = seg;
6048 seg->next = prev->next;
6052 segments_changed(tree);
6054 if (gtk_debug_flags & GTK_DEBUG_TEXT)
6055 gtk_text_btree_check(tree);
6059 gtk_text_btree_unlink_segment(GtkTextBTree *tree,
6060 GtkTextLineSegment *seg,
6063 GtkTextLineSegment *prev;
6065 if (line->segments == seg)
6067 line->segments = seg->next;
6071 for (prev = line->segments; prev->next != seg;
6074 /* Empty loop body. */
6076 prev->next = seg->next;
6079 segments_changed(tree);
6083 * This is here because it requires BTree internals, it logically
6084 * belongs in gtktextsegment.c
6089 *--------------------------------------------------------------
6091 * _gtk_toggle_segment_check_func --
6093 * This procedure is invoked to perform consistency checks
6094 * on toggle segments.
6100 * If a consistency problem is found the procedure g_errors.
6102 *--------------------------------------------------------------
6106 _gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6112 if (segPtr->byte_count != 0)
6114 g_error("toggle_segment_check_func: segment had non-zero size");
6116 if (!segPtr->body.toggle.inNodeCounts)
6118 g_error("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6120 needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6121 for (summary = line->parent->summary; ;
6122 summary = summary->next)
6124 if (summary == NULL)
6128 g_error("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6135 if (summary->info == segPtr->body.toggle.info)
6139 g_error("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6151 gtk_text_btree_node_view_check_consistency (GtkTextBTreeNode *node,
6158 gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6159 &width, &height, &valid);
6160 if (nd->width != width ||
6161 nd->height != height ||
6162 !nd->valid != !valid)
6164 g_error ("Node aggregates for view %p are invalid:\n"
6165 "Are (%d,%d,%s), should be (%d,%d,%s)",
6167 nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6168 width, height, valid ? "TRUE" : "FALSE");
6173 gtk_text_btree_node_check_consistency(GtkTextBTreeNode *node)
6175 GtkTextBTreeNode *childnode;
6176 Summary *summary, *summary2;
6178 GtkTextLineSegment *segPtr;
6179 int num_children, num_lines, num_chars, toggle_count, min_children;
6180 GtkTextLineData *ld;
6183 if (node->parent != NULL)
6185 min_children = MIN_CHILDREN;
6187 else if (node->level > 0)
6194 if ((node->num_children < min_children)
6195 || (node->num_children > MAX_CHILDREN))
6197 g_error("gtk_text_btree_node_check_consistency: bad child count (%d)",
6198 node->num_children);
6201 nd = node->node_data;
6204 gtk_text_btree_node_view_check_consistency (node, nd);
6211 if (node->level == 0)
6213 for (line = node->children.line; line != NULL;
6216 if (line->parent != node)
6218 g_error("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6220 if (line->segments == NULL)
6222 g_error("gtk_text_btree_node_check_consistency: line has no segments");
6228 /* Just ensuring we don't segv while doing this loop */
6233 for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6235 if (segPtr->type->checkFunc != NULL)
6237 (*segPtr->type->checkFunc)(segPtr, line);
6239 if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6240 && (segPtr->next != NULL)
6241 && (segPtr->next->byte_count == 0)
6242 && (segPtr->next->type->leftGravity))
6244 g_error("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6246 if ((segPtr->next == NULL)
6247 && (segPtr->type != >k_text_char_type))
6249 g_error("gtk_text_btree_node_check_consistency: line ended with wrong type");
6252 num_chars += segPtr->char_count;
6261 for (childnode = node->children.node; childnode != NULL;
6262 childnode = childnode->next)
6264 if (childnode->parent != node)
6266 g_error("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6268 if (childnode->level != (node->level-1))
6270 g_error("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6271 node->level, childnode->level);
6273 gtk_text_btree_node_check_consistency (childnode);
6274 for (summary = childnode->summary; summary != NULL;
6275 summary = summary->next)
6277 for (summary2 = node->summary; ;
6278 summary2 = summary2->next)
6280 if (summary2 == NULL)
6282 if (summary->info->tag_root == node)
6286 g_error("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6287 summary->info->tag->name,
6288 "present in parent summaries");
6290 if (summary->info == summary2->info)
6297 num_lines += childnode->num_lines;
6298 num_chars += childnode->num_chars;
6301 if (num_children != node->num_children)
6303 g_error("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6304 num_children, node->num_children);
6306 if (num_lines != node->num_lines)
6308 g_error("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6309 num_lines, node->num_lines);
6311 if (num_chars != node->num_chars)
6313 g_error("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6314 num_chars, node->num_chars);
6317 for (summary = node->summary; summary != NULL;
6318 summary = summary->next)
6320 if (summary->info->toggle_count == summary->toggle_count)
6322 g_error("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6323 summary->info->tag->name);
6326 if (node->level == 0)
6328 for (line = node->children.line; line != NULL;
6331 for (segPtr = line->segments; segPtr != NULL;
6332 segPtr = segPtr->next)
6334 if ((segPtr->type != >k_text_toggle_on_type)
6335 && (segPtr->type != >k_text_toggle_off_type))
6339 if (segPtr->body.toggle.info == summary->info)
6341 if (!segPtr->body.toggle.inNodeCounts)
6342 g_error ("Toggle segment not in the node counts");
6351 for (childnode = node->children.node;
6353 childnode = childnode->next)
6355 for (summary2 = childnode->summary;
6357 summary2 = summary2->next)
6359 if (summary2->info == summary->info)
6361 toggle_count += summary2->toggle_count;
6366 if (toggle_count != summary->toggle_count)
6368 g_error("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6369 toggle_count, summary->toggle_count);
6371 for (summary2 = summary->next; summary2 != NULL;
6372 summary2 = summary2->next)
6374 if (summary2->info == summary->info)
6376 g_error("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6377 summary->info->tag->name);
6384 listify_foreach(GtkTextTag *tag, gpointer user_data)
6386 GSList** listp = user_data;
6388 *listp = g_slist_prepend(*listp, tag);
6392 list_of_tags(GtkTextTagTable *table)
6394 GSList *list = NULL;
6396 gtk_text_tag_table_foreach(table, listify_foreach, &list);
6402 gtk_text_btree_check (GtkTextBTree *tree)
6405 GtkTextBTreeNode *node;
6407 GtkTextLineSegment *seg;
6409 GSList *taglist = NULL;
6411 GtkTextTagInfo *info;
6414 * Make sure that the tag toggle counts and the tag root pointers are OK.
6416 for (taglist = list_of_tags(tree->table);
6417 taglist != NULL ; taglist = taglist->next)
6419 tag = taglist->data;
6420 info = gtk_text_btree_get_existing_tag_info(tree, tag);
6423 node = info->tag_root;
6426 if (info->toggle_count != 0)
6428 g_error("gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6429 tag->name, info->toggle_count);
6431 continue; /* no ranges for the tag */
6433 else if (info->toggle_count == 0)
6435 g_error("gtk_text_btree_check found root for \"%s\" with no toggles",
6438 else if (info->toggle_count & 1)
6440 g_error("gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6441 tag->name, info->toggle_count);
6443 for (summary = node->summary; summary != NULL;
6444 summary = summary->next)
6446 if (summary->info->tag == tag)
6448 g_error("gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6452 if (node->level > 0)
6454 for (node = node->children.node ; node != NULL ;
6457 for (summary = node->summary; summary != NULL;
6458 summary = summary->next)
6460 if (summary->info->tag == tag)
6462 count += summary->toggle_count;
6469 GtkTextLineSegmentClass * last = NULL;
6471 for (line = node->children.line ; line != NULL ;
6474 for (seg = line->segments; seg != NULL;
6477 if ((seg->type == >k_text_toggle_on_type ||
6478 seg->type == >k_text_toggle_off_type) &&
6479 seg->body.toggle.info->tag == tag)
6481 if (last == seg->type)
6482 g_error ("Two consecutive toggles on or off weren't merged");
6483 if (!seg->body.toggle.inNodeCounts)
6484 g_error ("Toggle segment not in the node counts");
6493 if (count != info->toggle_count)
6495 g_error("gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
6496 info->toggle_count, tag->name, count);
6501 g_slist_free(taglist);
6505 * Call a recursive procedure to do the main body of checks.
6508 node = tree->root_node;
6509 gtk_text_btree_node_check_consistency(tree->root_node);
6512 * Make sure that there are at least two lines in the text and
6513 * that the last line has no characters except a newline.
6516 if (node->num_lines < 2)
6518 g_error("gtk_text_btree_check: less than 2 lines in tree");
6520 if (node->num_chars < 2)
6522 g_error("gtk_text_btree_check: less than 2 chars in tree");
6524 while (node->level > 0)
6526 node = node->children.node;
6527 while (node->next != NULL)
6532 line = node->children.line;
6533 while (line->next != NULL)
6537 seg = line->segments;
6538 while ((seg->type == >k_text_toggle_off_type)
6539 || (seg->type == >k_text_right_mark_type)
6540 || (seg->type == >k_text_left_mark_type))
6543 * It's OK to toggle a tag off in the last line, but
6544 * not to start a new range. It's also OK to have marks
6550 if (seg->type != >k_text_char_type)
6552 g_error("gtk_text_btree_check: last line has bogus segment type");
6554 if (seg->next != NULL)
6556 g_error("gtk_text_btree_check: last line has too many segments");
6558 if (seg->byte_count != 1)
6560 g_error("gtk_text_btree_check: last line has wrong # characters: %d",
6563 if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
6565 g_error("gtk_text_btree_check: last line had bad value: %s",
6570 void gtk_text_btree_spew_line(GtkTextBTree* tree, GtkTextLine* line);
6571 void gtk_text_btree_spew_segment(GtkTextBTree* tree, GtkTextLineSegment* seg);
6572 void gtk_text_btree_spew_node(GtkTextBTreeNode *node, int indent);
6573 void gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
6576 gtk_text_btree_spew (GtkTextBTree *tree)
6581 printf("%d lines in tree %p\n",
6582 gtk_text_btree_line_count(tree), tree);
6584 line = gtk_text_btree_get_line(tree, 0, &real_line);
6586 while (line != NULL)
6588 gtk_text_btree_spew_line(tree, line);
6589 line = gtk_text_line_next(line);
6592 printf("=================== Tag information\n");
6597 list = tree->tag_infos;
6599 while (list != NULL)
6601 GtkTextTagInfo *info;
6605 printf (" tag `%s': root at %p, toggle count %d\n",
6606 info->tag->name, info->tag_root, info->toggle_count);
6608 list = g_slist_next (list);
6611 if (tree->tag_infos == NULL)
6613 printf (" (no tags in the tree)\n");
6617 printf("=================== Tree nodes\n");
6620 gtk_text_btree_spew_node (tree->root_node, 0);
6625 gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
6628 GtkTextLineSegment *seg;
6630 spaces = g_strnfill (indent, ' ');
6632 printf ("%sline %p chars %d bytes %d\n",
6634 gtk_text_line_char_count (line),
6635 gtk_text_line_byte_count (line));
6637 seg = line->segments;
6640 if (seg->type == >k_text_char_type)
6642 gchar* str = g_strndup(seg->body.chars, MIN (seg->byte_count, 10));
6651 printf("%s chars `%s'...\n", spaces, str);
6654 else if (seg->type == >k_text_right_mark_type)
6656 printf("%s right mark `%s' visible: %d\n",
6658 seg->body.mark.name,
6659 seg->body.mark.visible);
6661 else if (seg->type == >k_text_left_mark_type)
6663 printf("%s left mark `%s' visible: %d\n",
6665 seg->body.mark.name,
6666 seg->body.mark.visible);
6668 else if (seg->type == >k_text_toggle_on_type ||
6669 seg->type == >k_text_toggle_off_type)
6671 printf("%s tag `%s' %s\n",
6672 spaces, seg->body.toggle.info->tag->name,
6673 seg->type == >k_text_toggle_off_type ? "off" : "on");
6683 gtk_text_btree_spew_node(GtkTextBTreeNode *node, int indent)
6686 GtkTextBTreeNode *iter;
6689 spaces = g_strnfill (indent, ' ');
6691 printf ("%snode %p level %d children %d lines %d chars %d\n",
6692 spaces, node, node->level,
6693 node->num_children, node->num_lines, node->num_chars);
6698 printf ("%s %d toggles of `%s' below this node\n",
6699 spaces, s->toggle_count, s->info->tag->name);
6705 if (node->level > 0)
6707 iter = node->children.node;
6708 while (iter != NULL)
6710 gtk_text_btree_spew_node (iter, indent + 2);
6717 GtkTextLine *line = node->children.line;
6718 while (line != NULL)
6720 gtk_text_btree_spew_line_short (line, indent + 2);
6728 gtk_text_btree_spew_line(GtkTextBTree* tree, GtkTextLine* line)
6730 GtkTextLineSegment * seg;
6732 printf("%4d| line: %p parent: %p next: %p\n",
6733 gtk_text_line_get_number(line), line, line->parent, line->next);
6735 seg = line->segments;
6739 gtk_text_btree_spew_segment(tree, seg);
6745 gtk_text_btree_spew_segment(GtkTextBTree* tree, GtkTextLineSegment * seg)
6747 printf(" segment: %p type: %s bytes: %d chars: %d\n",
6748 seg, seg->type->name, seg->byte_count, seg->char_count);
6750 if (seg->type == >k_text_char_type)
6752 gchar* str = g_strndup(seg->body.chars, seg->byte_count);
6753 printf(" `%s'\n", str);
6756 else if (seg->type == >k_text_right_mark_type)
6758 printf(" right mark `%s' visible: %d not_deleteable: %d\n",
6759 seg->body.mark.name,
6760 seg->body.mark.visible,
6761 seg->body.mark.not_deleteable);
6763 else if (seg->type == >k_text_left_mark_type)
6765 printf(" left mark `%s' visible: %d not_deleteable: %d\n",
6766 seg->body.mark.name,
6767 seg->body.mark.visible,
6768 seg->body.mark.not_deleteable);
6770 else if (seg->type == >k_text_toggle_on_type ||
6771 seg->type == >k_text_toggle_off_type)
6773 printf(" tag `%s' priority %d\n",
6774 seg->body.toggle.info->tag->name,
6775 seg->body.toggle.info->tag->priority);