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;
199 GHashTable *child_anchor_table;
204 * Upper and lower bounds on how many children a node may have:
205 * rebalance when either of these limits is exceeded. MAX_CHILDREN
206 * should be twice MIN_CHILDREN and MIN_CHILDREN must be >= 2.
209 /* Tk used MAX of 12 and MIN of 6. This makes the tree wide and
210 shallow. It appears to be faster to locate a particular line number
211 if the tree is narrow and deep, since it is more finely sorted. I
212 guess this may increase memory use though, and make it slower to
213 walk the tree in order, or locate a particular byte index (which
214 is done by walking the tree in order).
216 There's basically a tradeoff here. However I'm thinking we want to
217 add pixels, byte counts, and char counts to the tree nodes,
218 at that point narrow and deep should speed up all operations,
219 not just the line number searches.
223 #define MAX_CHILDREN 12
224 #define MIN_CHILDREN 6
226 #define MAX_CHILDREN 6
227 #define MIN_CHILDREN 3
234 static BTreeView *gtk_text_btree_get_view (GtkTextBTree *tree,
236 static void gtk_text_btree_rebalance (GtkTextBTree *tree,
237 GtkTextBTreeNode *node);
238 static GtkTextLine * get_last_line (GtkTextBTree *tree);
239 static void post_insert_fixup (GtkTextBTree *tree,
240 GtkTextLine *insert_line,
241 gint char_count_delta,
242 gint line_count_delta);
243 static void gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
244 GtkTextTagInfo *info,
246 static gboolean gtk_text_btree_node_has_tag (GtkTextBTreeNode *node,
249 static void segments_changed (GtkTextBTree *tree);
250 static void chars_changed (GtkTextBTree *tree);
251 static void summary_list_destroy (Summary *summary);
252 static GtkTextLine *gtk_text_line_new (void);
253 static void gtk_text_line_destroy (GtkTextBTree *tree,
255 static void gtk_text_line_set_parent (GtkTextLine *line,
256 GtkTextBTreeNode *node);
257 static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
261 static NodeData *node_data_new (gpointer view_id);
262 static void node_data_destroy (NodeData *nd);
263 static void node_data_list_destroy (NodeData *nd);
264 static NodeData *node_data_find (NodeData *nd,
267 static GtkTextBTreeNode *gtk_text_btree_node_new (void);
268 static void gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node);
269 static void gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node,
271 static NodeData * gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
273 static NodeData * gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
275 static void gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
278 static void gtk_text_btree_node_remove_view (BTreeView *view,
279 GtkTextBTreeNode *node,
281 static void gtk_text_btree_node_destroy (GtkTextBTree *tree,
282 GtkTextBTreeNode *node);
283 static NodeData * gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node,
285 static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
287 static void gtk_text_btree_node_get_size (GtkTextBTreeNode *node,
291 static GtkTextBTreeNode * gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
292 GtkTextBTreeNode *node2);
293 static void get_tree_bounds (GtkTextBTree *tree,
296 static void tag_changed_cb (GtkTextTagTable *table,
298 gboolean size_changed,
300 static void tag_removed_cb (GtkTextTagTable *table,
303 static void cleanup_line (GtkTextLine *line);
304 static void recompute_node_counts (GtkTextBTree *tree,
305 GtkTextBTreeNode *node);
306 static void inc_count (GtkTextTag *tag,
308 TagInfo *tagInfoPtr);
310 static void summary_destroy (Summary *summary);
312 static void gtk_text_btree_link_segment (GtkTextLineSegment *seg,
313 const GtkTextIter *iter);
314 static void gtk_text_btree_unlink_segment (GtkTextBTree *tree,
315 GtkTextLineSegment *seg,
319 static GtkTextTagInfo *gtk_text_btree_get_tag_info (GtkTextBTree *tree,
321 static GtkTextTagInfo *gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
323 static void gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
326 static void redisplay_region (GtkTextBTree *tree,
327 const GtkTextIter *start,
328 const GtkTextIter *end);
330 /* Inline thingies */
333 segments_changed (GtkTextBTree *tree)
335 tree->segments_changed_stamp += 1;
339 chars_changed (GtkTextBTree *tree)
341 tree->chars_changed_stamp += 1;
349 _gtk_text_btree_new (GtkTextTagTable *table,
350 GtkTextBuffer *buffer)
353 GtkTextBTreeNode *root_node;
354 GtkTextLine *line, *line2;
356 g_return_val_if_fail (GTK_IS_TEXT_TAG_TABLE (table), NULL);
357 g_return_val_if_fail (GTK_IS_TEXT_BUFFER (buffer), NULL);
360 * The tree will initially have two empty lines. The second line
361 * isn't actually part of the tree's contents, but its presence
362 * makes several operations easier. The tree will have one GtkTextBTreeNode,
363 * which is also the root of the tree.
366 /* Create the root node. */
368 root_node = gtk_text_btree_node_new ();
370 line = gtk_text_line_new ();
371 line2 = gtk_text_line_new ();
373 root_node->parent = NULL;
374 root_node->next = NULL;
375 root_node->summary = NULL;
376 root_node->level = 0;
377 root_node->children.line = line;
378 root_node->num_children = 2;
379 root_node->num_lines = 2;
380 root_node->num_chars = 2;
382 line->parent = root_node;
385 line->segments = _gtk_char_segment_new ("\n", 1);
387 line2->parent = root_node;
389 line2->segments = _gtk_char_segment_new ("\n", 1);
391 /* Create the tree itself */
393 tree = g_new0(GtkTextBTree, 1);
394 tree->root_node = root_node;
398 /* Set these to values that are unlikely to be found
399 * in random memory garbage, and also avoid
400 * duplicates between tree instances.
402 tree->chars_changed_stamp = g_random_int ();
403 tree->segments_changed_stamp = g_random_int ();
405 tree->end_iter_line_stamp = tree->chars_changed_stamp - 1;
406 tree->end_iter_line = NULL;
408 g_object_ref (G_OBJECT (tree->table));
410 tree->tag_changed_handler = g_signal_connect_data (G_OBJECT (tree->table),
416 tree->tag_removed_handler = g_signal_connect_data (G_OBJECT (tree->table),
422 tree->mark_table = g_hash_table_new (g_str_hash, g_str_equal);
423 tree->child_anchor_table = NULL;
425 /* We don't ref the buffer, since the buffer owns us;
426 * we'd have some circularity issues. The buffer always
427 * lasts longer than the BTree
429 tree->buffer = buffer;
433 GtkTextLineSegment *seg;
435 _gtk_text_btree_get_iter_at_line_char (tree, &start, 0, 0);
438 tree->insert_mark = _gtk_text_btree_set_mark (tree,
445 seg = tree->insert_mark->segment;
447 seg->body.mark.not_deleteable = TRUE;
448 seg->body.mark.visible = TRUE;
450 tree->selection_bound_mark = _gtk_text_btree_set_mark (tree,
457 seg = tree->selection_bound_mark->segment;
459 seg->body.mark.not_deleteable = TRUE;
461 g_object_ref (G_OBJECT (tree->insert_mark));
462 g_object_ref (G_OBJECT (tree->selection_bound_mark));
471 _gtk_text_btree_ref (GtkTextBTree *tree)
473 g_return_if_fail (tree != NULL);
474 g_return_if_fail (tree->refcount > 0);
480 mark_destroy_foreach (gpointer key, gpointer value, gpointer user_data)
482 GtkTextLineSegment *seg = value;
484 g_return_if_fail (seg->body.mark.tree == NULL);
486 g_object_unref (G_OBJECT (seg->body.mark.obj));
490 _gtk_text_btree_unref (GtkTextBTree *tree)
492 g_return_if_fail (tree != NULL);
493 g_return_if_fail (tree->refcount > 0);
497 if (tree->refcount == 0)
499 gtk_text_btree_node_destroy (tree, tree->root_node);
501 g_hash_table_foreach (tree->mark_table,
502 mark_destroy_foreach,
504 g_hash_table_destroy (tree->mark_table);
506 g_object_unref (G_OBJECT (tree->insert_mark));
507 g_object_unref (G_OBJECT (tree->selection_bound_mark));
509 g_signal_handler_disconnect (G_OBJECT (tree->table),
510 tree->tag_changed_handler);
512 g_signal_handler_disconnect (G_OBJECT (tree->table),
513 tree->tag_removed_handler);
515 g_object_unref (G_OBJECT (tree->table));
522 _gtk_text_btree_get_buffer (GtkTextBTree *tree)
528 _gtk_text_btree_get_chars_changed_stamp (GtkTextBTree *tree)
530 return tree->chars_changed_stamp;
534 _gtk_text_btree_get_segments_changed_stamp (GtkTextBTree *tree)
536 return tree->segments_changed_stamp;
540 _gtk_text_btree_segments_changed (GtkTextBTree *tree)
542 g_return_if_fail (tree != NULL);
543 segments_changed (tree);
547 * Indexable segment mutation
551 _gtk_text_btree_delete (GtkTextIter *start,
554 GtkTextLineSegment *prev_seg; /* The segment just before the start
555 * of the deletion range. */
556 GtkTextLineSegment *last_seg; /* The segment just after the end
557 * of the deletion range. */
558 GtkTextLineSegment *seg, *next;
559 GtkTextLine *curline;
560 GtkTextBTreeNode *curnode, *node;
562 GtkTextLine *start_line;
563 GtkTextLine *end_line;
564 GtkTextLine *deleted_lines = NULL; /* List of lines we've deleted */
565 gint start_byte_offset;
567 g_return_if_fail (start != NULL);
568 g_return_if_fail (end != NULL);
569 g_return_if_fail (gtk_text_iter_get_btree (start) ==
570 gtk_text_iter_get_btree (end));
572 gtk_text_iter_reorder (start, end);
574 tree = gtk_text_iter_get_btree (start);
578 * The code below is ugly, but it's needed to make sure there
579 * is always a dummy empty line at the end of the text. If the
580 * final newline of the file (just before the dummy line) is being
581 * deleted, then back up index to just before the newline. If
582 * there is a newline just before the first character being deleted,
583 * then back up the first index too, so that an even number of lines
584 * gets deleted. Furthermore, remove any tags that are present on
585 * the newline that isn't going to be deleted after all (this simulates
586 * deleting the newline and then adding a "clean" one back again).
592 line1 = gtk_text_iter_get_line (start);
593 line2 = gtk_text_iter_get_line (end);
595 if (line2 == _gtk_text_btree_line_count (tree))
599 GtkTextIter orig_end;
602 gtk_text_iter_backward_char (end);
606 if (gtk_text_iter_get_line_offset (start) == 0 &&
609 gtk_text_iter_backward_char (start);
613 tags = _gtk_text_btree_get_tags (end,
621 while (i < array_size)
623 _gtk_text_btree_tag (end, &orig_end, tags[i], FALSE);
633 /* Broadcast the need for redisplay before we break the iterators */
634 _gtk_text_btree_invalidate_region (tree, start, end);
636 /* Save the byte offset so we can reset the iterators */
637 start_byte_offset = gtk_text_iter_get_line_index (start);
639 start_line = gtk_text_iter_get_text_line (start);
640 end_line = gtk_text_iter_get_text_line (end);
643 * Split the start and end segments, so we have a place
644 * to insert our new text.
646 * Tricky point: split at end first; otherwise the split
647 * at end may invalidate seg and/or prev_seg. This allows
648 * us to avoid invalidating segments for start.
651 last_seg = gtk_text_line_segment_split (end);
652 if (last_seg != NULL)
653 last_seg = last_seg->next;
655 last_seg = end_line->segments;
657 prev_seg = gtk_text_line_segment_split (start);
658 if (prev_seg != NULL)
660 seg = prev_seg->next;
661 prev_seg->next = last_seg;
665 seg = start_line->segments;
666 start_line->segments = last_seg;
669 /* notify iterators that their segments need recomputation,
670 just for robustness. */
671 segments_changed (tree);
674 * Delete all of the segments between prev_seg and last_seg.
677 curline = start_line;
678 curnode = curline->parent;
679 while (seg != last_seg)
685 GtkTextLine *nextline;
688 * We just ran off the end of a line. First find the
689 * next line, then go back to the old line and delete it
690 * (unless it's the starting line for the range).
693 nextline = _gtk_text_line_next (curline);
694 if (curline != start_line)
696 if (curnode == start_line->parent)
697 start_line->next = curline->next;
699 curnode->children.line = curline->next;
701 for (node = curnode; node != NULL;
704 node->num_lines -= 1;
707 curnode->num_children -= 1;
708 curline->next = deleted_lines;
709 deleted_lines = curline;
713 seg = curline->segments;
716 * If the GtkTextBTreeNode is empty then delete it and its parents,
717 * recursively upwards until a non-empty GtkTextBTreeNode is found.
720 while (curnode->num_children == 0)
722 GtkTextBTreeNode *parent;
724 parent = curnode->parent;
725 if (parent->children.node == curnode)
727 parent->children.node = curnode->next;
731 GtkTextBTreeNode *prevnode = parent->children.node;
732 while (prevnode->next != curnode)
734 prevnode = prevnode->next;
736 prevnode->next = curnode->next;
738 parent->num_children--;
742 curnode = curline->parent;
747 char_count = seg->char_count;
749 if ((*seg->type->deleteFunc)(seg, curline, 0) != 0)
752 * This segment refuses to die. Move it to prev_seg and
753 * advance prev_seg if the segment has left gravity.
756 if (prev_seg == NULL)
758 seg->next = start_line->segments;
759 start_line->segments = seg;
763 seg->next = prev_seg->next;
764 prev_seg->next = seg;
766 if (seg->type->leftGravity)
773 /* Segment is gone. Decrement the char count of the node and
775 for (node = curnode; node != NULL;
778 node->num_chars -= char_count;
786 * If the beginning and end of the deletion range are in different
787 * lines, join the two lines together and discard the ending line.
790 if (start_line != end_line)
793 GtkTextBTreeNode *ancestor_node;
795 GtkTextLine *prevline;
797 for (seg = last_seg; seg != NULL;
800 if (seg->type->lineChangeFunc != NULL)
802 (*seg->type->lineChangeFunc)(seg, end_line);
805 curnode = end_line->parent;
806 for (node = curnode; node != NULL;
811 curnode->num_children--;
812 prevline = curnode->children.line;
813 if (prevline == end_line)
815 curnode->children.line = end_line->next;
819 while (prevline->next != end_line)
821 prevline = prevline->next;
823 prevline->next = end_line->next;
825 end_line->next = deleted_lines;
826 deleted_lines = end_line;
828 /* We now fix up the per-view aggregates. We add all the height and
829 * width for the deleted lines to the start line, so that when revalidation
830 * occurs, the correct change in size is seen.
832 ancestor_node = gtk_text_btree_node_common_parent (curnode, start_line->parent);
839 gint deleted_width = 0;
840 gint deleted_height = 0;
842 line = deleted_lines;
845 GtkTextLine *next_line = line->next;
846 ld = _gtk_text_line_get_data (line, view->view_id);
850 deleted_width = MAX (deleted_width, ld->width);
851 deleted_height += ld->height;
855 gtk_text_line_destroy (tree, line);
860 if (deleted_width > 0 || deleted_height > 0)
862 ld = _gtk_text_line_get_data (start_line, view->view_id);
864 /* FIXME: ld is _NOT_ necessarily non-null here, but there is currently
865 * no way to add ld without also validating the node, which would
866 * be improper at this point.
868 /* This assertion does actually fail sometimes, must
869 fix before stable release -hp */
872 ld->width = MAX (deleted_width, ld->width);
873 ld->height += deleted_height;
877 gtk_text_btree_node_check_valid_downward (ancestor_node, view->view_id);
878 if (ancestor_node->parent)
879 gtk_text_btree_node_check_valid_upward (ancestor_node->parent, view->view_id);
884 gtk_text_btree_rebalance (tree, curnode);
888 * Cleanup the segments in the new line.
891 cleanup_line (start_line);
894 * Lastly, rebalance the first GtkTextBTreeNode of the range.
897 gtk_text_btree_rebalance (tree, start_line->parent);
899 /* Notify outstanding iterators that they
901 chars_changed (tree);
902 segments_changed (tree);
904 if (gtk_debug_flags & GTK_DEBUG_TEXT)
905 _gtk_text_btree_check (tree);
907 /* Re-initialize our iterators */
908 _gtk_text_btree_get_iter_at_line (tree, start, start_line, start_byte_offset);
913 _gtk_text_btree_insert (GtkTextIter *iter,
917 GtkTextLineSegment *prev_seg; /* The segment just before the first
918 * new segment (NULL means new segment
919 * is at beginning of line). */
920 GtkTextLineSegment *cur_seg; /* Current segment; new characters
921 * are inserted just after this one.
922 * NULL means insert at beginning of
924 GtkTextLine *line; /* Current line (new segments are
925 * added to this line). */
926 GtkTextLineSegment *seg;
927 GtkTextLine *newline;
928 int chunk_len; /* # characters in current chunk. */
929 gint sol; /* start of line */
930 gint eol; /* Pointer to character just after last
931 * one in current chunk.
933 gint delim; /* index of paragraph delimiter */
934 int line_count_delta; /* Counts change to total number of
938 int char_count_delta; /* change to number of chars */
940 gint start_byte_index;
941 GtkTextLine *start_line;
943 g_return_if_fail (text != NULL);
944 g_return_if_fail (iter != NULL);
949 /* extract iterator info */
950 tree = gtk_text_iter_get_btree (iter);
951 line = gtk_text_iter_get_text_line (iter);
953 start_byte_index = gtk_text_iter_get_line_index (iter);
955 /* Get our insertion segment split */
956 prev_seg = gtk_text_line_segment_split (iter);
959 /* Invalidate all iterators */
960 chars_changed (tree);
961 segments_changed (tree);
963 g_assert (g_utf8_validate (text, len, NULL));
966 * Chop the text up into lines and create a new segment for
967 * each line, plus a new line for the leftovers from the
973 line_count_delta = 0;
974 char_count_delta = 0;
979 pango_find_paragraph_boundary (text + sol,
984 /* make these relative to the start of the text */
988 g_assert (eol >= sol);
989 g_assert (delim >= sol);
990 g_assert (eol >= delim);
992 g_assert (eol <= len);
994 chunk_len = eol - sol;
996 g_assert (g_utf8_validate (&text[sol], chunk_len, NULL));
997 seg = _gtk_char_segment_new (&text[sol], chunk_len);
999 char_count_delta += seg->char_count;
1001 if (cur_seg == NULL)
1003 seg->next = line->segments;
1004 line->segments = seg;
1008 seg->next = cur_seg->next;
1009 cur_seg->next = seg;
1014 /* chunk didn't end with a paragraph separator */
1015 g_assert (eol == len);
1020 * The chunk ended with a newline, so create a new GtkTextLine
1021 * and move the remainder of the old line to it.
1024 newline = gtk_text_line_new ();
1025 gtk_text_line_set_parent (newline, line->parent);
1026 newline->next = line->next;
1027 line->next = newline;
1028 newline->segments = seg->next;
1036 * Cleanup the starting line for the insertion, plus the ending
1037 * line if it's different.
1040 cleanup_line (start_line);
1041 if (line != start_line)
1043 cleanup_line (line);
1046 post_insert_fixup (tree, line, line_count_delta, char_count_delta);
1048 /* Invalidate our region, and reset the iterator the user
1049 passed in to point to the end of the inserted text. */
1055 _gtk_text_btree_get_iter_at_line (tree,
1061 /* We could almost certainly be more efficient here
1062 by saving the information from the insertion loop
1064 gtk_text_iter_forward_chars (&end, char_count_delta);
1066 _gtk_text_btree_invalidate_region (tree,
1070 /* Convenience for the user */
1076 insert_pixbuf_or_widget_segment (GtkTextIter *iter,
1077 GtkTextLineSegment *seg)
1081 GtkTextLineSegment *prevPtr;
1084 gint start_byte_offset;
1086 line = gtk_text_iter_get_text_line (iter);
1087 tree = gtk_text_iter_get_btree (iter);
1088 start_byte_offset = gtk_text_iter_get_line_index (iter);
1090 prevPtr = gtk_text_line_segment_split (iter);
1091 if (prevPtr == NULL)
1093 seg->next = line->segments;
1094 line->segments = seg;
1098 seg->next = prevPtr->next;
1099 prevPtr->next = seg;
1102 post_insert_fixup (tree, line, 0, seg->char_count);
1104 chars_changed (tree);
1105 segments_changed (tree);
1107 /* reset *iter for the user, and invalidate tree nodes */
1109 _gtk_text_btree_get_iter_at_line (tree, &start, line, start_byte_offset);
1112 gtk_text_iter_forward_char (iter); /* skip forward past the segment */
1114 _gtk_text_btree_invalidate_region (tree, &start, iter);
1118 _gtk_text_btree_insert_pixbuf (GtkTextIter *iter,
1121 GtkTextLineSegment *seg;
1123 seg = _gtk_pixbuf_segment_new (pixbuf);
1125 insert_pixbuf_or_widget_segment (iter, seg);
1129 _gtk_text_btree_create_child_anchor (GtkTextIter *iter)
1131 GtkTextLineSegment *seg;
1134 seg = _gtk_widget_segment_new ();
1136 tree = seg->body.child.tree = gtk_text_iter_get_btree (iter);
1138 insert_pixbuf_or_widget_segment (iter, seg);
1140 if (tree->child_anchor_table == NULL)
1141 tree->child_anchor_table = g_hash_table_new (NULL, NULL);
1143 g_hash_table_insert (tree->child_anchor_table,
1144 seg->body.child.obj,
1145 seg->body.child.obj);
1147 return seg->body.child.obj;
1151 _gtk_text_btree_unregister_child_anchor (GtkTextChildAnchor *anchor)
1153 GtkTextLineSegment *seg;
1155 seg = anchor->segment;
1157 g_hash_table_remove (seg->body.child.tree->child_anchor_table,
1166 find_line_by_y (GtkTextBTree *tree, BTreeView *view,
1167 GtkTextBTreeNode *node, gint y, gint *line_top,
1168 GtkTextLine *last_line)
1172 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1173 _gtk_text_btree_check (tree);
1175 if (node->level == 0)
1179 line = node->children.line;
1181 while (line != NULL && line != last_line)
1183 GtkTextLineData *ld;
1185 ld = _gtk_text_line_get_data (line, view->view_id);
1189 if (y < (current_y + (ld ? ld->height : 0)))
1192 current_y += ld->height;
1193 *line_top += ld->height;
1202 GtkTextBTreeNode *child;
1204 child = node->children.node;
1206 while (child != NULL)
1211 gtk_text_btree_node_get_size (child, view->view_id,
1214 if (y < (current_y + height))
1215 return find_line_by_y (tree, view, child,
1216 y - current_y, line_top,
1219 current_y += height;
1220 *line_top += height;
1222 child = child->next;
1230 _gtk_text_btree_find_line_by_y (GtkTextBTree *tree,
1237 GtkTextLine *last_line;
1240 view = gtk_text_btree_get_view (tree, view_id);
1241 g_return_val_if_fail (view != NULL, NULL);
1243 last_line = get_last_line (tree);
1245 line = find_line_by_y (tree, view, tree->root_node, ypixel, &line_top,
1249 *line_top_out = line_top;
1255 find_line_top_in_line_list (GtkTextBTree *tree,
1258 GtkTextLine *target_line,
1261 while (line != NULL)
1263 GtkTextLineData *ld;
1265 if (line == target_line)
1268 ld = _gtk_text_line_get_data (line, view->view_id);
1275 g_assert_not_reached (); /* If we get here, our
1276 target line didn't exist
1277 under its parent node */
1282 _gtk_text_btree_find_line_top (GtkTextBTree *tree,
1283 GtkTextLine *target_line,
1290 GtkTextBTreeNode *node;
1292 view = gtk_text_btree_get_view (tree, view_id);
1294 g_return_val_if_fail (view != NULL, 0);
1297 node = target_line->parent;
1298 while (node != NULL)
1300 nodes = g_slist_prepend (nodes, node);
1301 node = node->parent;
1305 while (iter != NULL)
1309 if (node->level == 0)
1311 g_slist_free (nodes);
1312 return find_line_top_in_line_list (tree, view,
1313 node->children.line,
1318 GtkTextBTreeNode *child;
1319 GtkTextBTreeNode *target_node;
1321 g_assert (iter->next != NULL); /* not at level 0 */
1322 target_node = iter->next->data;
1324 child = node->children.node;
1326 while (child != NULL)
1331 if (child == target_node)
1335 gtk_text_btree_node_get_size (child, view->view_id,
1339 child = child->next;
1341 g_assert (child != NULL); /* should have broken out before we
1345 iter = g_slist_next (iter);
1348 g_assert_not_reached (); /* we return when we find the target line */
1353 _gtk_text_btree_add_view (GtkTextBTree *tree,
1354 GtkTextLayout *layout)
1357 GtkTextLine *last_line;
1358 GtkTextLineData *line_data;
1360 g_return_if_fail (tree != NULL);
1362 view = g_new (BTreeView, 1);
1364 view->view_id = layout;
1365 view->layout = layout;
1367 view->next = tree->views;
1372 /* The last line in the buffer has identity values for the per-view
1373 * data so that we can avoid special case checks for it in a large
1376 last_line = get_last_line (tree);
1378 line_data = g_new (GtkTextLineData, 1);
1379 line_data->view_id = layout;
1380 line_data->next = NULL;
1381 line_data->width = 0;
1382 line_data->height = 0;
1383 line_data->valid = TRUE;
1385 _gtk_text_line_add_data (last_line, line_data);
1389 _gtk_text_btree_remove_view (GtkTextBTree *tree,
1393 GtkTextLine *last_line;
1394 GtkTextLineData *line_data;
1396 g_return_if_fail (tree != NULL);
1400 while (view != NULL)
1402 if (view->view_id == view_id)
1408 g_return_if_fail (view != NULL);
1411 view->next->prev = view->prev;
1414 view->prev->next = view->next;
1416 if (view == tree->views)
1417 tree->views = view->next;
1419 /* Remove the line data for the last line which we added ourselves.
1420 * (Do this first, so that we don't try to call the view's line data destructor on it.)
1422 last_line = get_last_line (tree);
1423 line_data = _gtk_text_line_remove_data (last_line, view_id);
1426 gtk_text_btree_node_remove_view (view, tree->root_node, view_id);
1432 _gtk_text_btree_invalidate_region (GtkTextBTree *tree,
1433 const GtkTextIter *start,
1434 const GtkTextIter *end)
1440 while (view != NULL)
1442 gtk_text_layout_invalidate (view->layout, start, end);
1449 _gtk_text_btree_get_view_size (GtkTextBTree *tree,
1454 g_return_if_fail (tree != NULL);
1455 g_return_if_fail (view_id != NULL);
1457 gtk_text_btree_node_get_size (tree->root_node, view_id,
1472 iter_stack_new (void)
1475 stack = g_new (IterStack, 1);
1476 stack->iters = NULL;
1483 iter_stack_push (IterStack *stack, const GtkTextIter *iter)
1486 if (stack->count > stack->alloced)
1488 stack->alloced = stack->count*2;
1489 stack->iters = g_realloc (stack->iters,
1490 stack->alloced*sizeof (GtkTextIter));
1492 stack->iters[stack->count-1] = *iter;
1496 iter_stack_pop (IterStack *stack, GtkTextIter *iter)
1498 if (stack->count == 0)
1503 *iter = stack->iters[stack->count];
1509 iter_stack_free (IterStack *stack)
1511 g_free (stack->iters);
1516 iter_stack_invert (IterStack *stack)
1518 if (stack->count > 0)
1521 guint j = stack->count - 1;
1526 tmp = stack->iters[i];
1527 stack->iters[i] = stack->iters[j];
1528 stack->iters[j] = tmp;
1537 queue_tag_redisplay (GtkTextBTree *tree,
1539 const GtkTextIter *start,
1540 const GtkTextIter *end)
1542 if (gtk_text_tag_affects_size (tag))
1544 _gtk_text_btree_invalidate_region (tree, start, end);
1547 else if (gtk_text_tag_affects_nonsize_appearance (tag))
1549 /* We only need to queue a redraw, not a relayout */
1550 redisplay_region (tree, start, end);
1553 /* We don't need to do anything if the tag doesn't affect display */
1557 _gtk_text_btree_tag (const GtkTextIter *start_orig,
1558 const GtkTextIter *end_orig,
1562 GtkTextLineSegment *seg, *prev;
1563 GtkTextLine *cleanupline;
1564 gboolean toggled_on;
1565 GtkTextLine *start_line;
1566 GtkTextLine *end_line;
1568 GtkTextIter start, end;
1571 GtkTextTagInfo *info;
1573 g_return_if_fail (start_orig != NULL);
1574 g_return_if_fail (end_orig != NULL);
1575 g_return_if_fail (GTK_IS_TEXT_TAG (tag));
1576 g_return_if_fail (gtk_text_iter_get_btree (start_orig) ==
1577 gtk_text_iter_get_btree (end_orig));
1580 printf ("%s tag %s from %d to %d\n",
1581 add ? "Adding" : "Removing",
1583 gtk_text_buffer_get_offset (start_orig),
1584 gtk_text_buffer_get_offset (end_orig));
1587 if (gtk_text_iter_equal (start_orig, end_orig))
1590 start = *start_orig;
1593 gtk_text_iter_reorder (&start, &end);
1595 tree = gtk_text_iter_get_btree (&start);
1597 queue_tag_redisplay (tree, tag, &start, &end);
1599 info = gtk_text_btree_get_tag_info (tree, tag);
1601 start_line = gtk_text_iter_get_text_line (&start);
1602 end_line = gtk_text_iter_get_text_line (&end);
1604 /* Find all tag toggles in the region; we are going to delete them.
1605 We need to find them in advance, because
1606 forward_find_tag_toggle () won't work once we start playing around
1608 stack = iter_stack_new ();
1610 /* We don't want to delete a toggle that's at the start iterator. */
1611 gtk_text_iter_forward_char (&iter);
1612 while (gtk_text_iter_forward_to_tag_toggle (&iter, tag))
1614 if (gtk_text_iter_compare (&iter, &end) >= 0)
1617 iter_stack_push (stack, &iter);
1620 /* We need to traverse the toggles in order. */
1621 iter_stack_invert (stack);
1624 * See whether the tag is present at the start of the range. If
1625 * the state doesn't already match what we want then add a toggle
1629 toggled_on = gtk_text_iter_has_tag (&start, tag);
1630 if ( (add && !toggled_on) ||
1631 (!add && toggled_on) )
1633 /* This could create a second toggle at the start position;
1634 cleanup_line () will remove it if so. */
1635 seg = _gtk_toggle_segment_new (info, add);
1637 prev = gtk_text_line_segment_split (&start);
1640 seg->next = start_line->segments;
1641 start_line->segments = seg;
1645 seg->next = prev->next;
1649 /* cleanup_line adds the new toggle to the node counts. */
1651 printf ("added toggle at start\n");
1653 /* we should probably call segments_changed, but in theory
1654 any still-cached segments in the iters we are about to
1655 use are still valid, since they're in front
1661 * Scan the range of characters and delete any internal tag
1662 * transitions. Keep track of what the old state was at the end
1663 * of the range, and add a toggle there if it's needed.
1667 cleanupline = start_line;
1668 while (iter_stack_pop (stack, &iter))
1670 GtkTextLineSegment *indexable_seg;
1673 line = gtk_text_iter_get_text_line (&iter);
1674 seg = gtk_text_iter_get_any_segment (&iter);
1675 indexable_seg = gtk_text_iter_get_indexable_segment (&iter);
1677 g_assert (seg != NULL);
1678 g_assert (indexable_seg != NULL);
1679 g_assert (seg != indexable_seg);
1681 prev = line->segments;
1683 /* Find the segment that actually toggles this tag. */
1684 while (seg != indexable_seg)
1686 g_assert (seg != NULL);
1687 g_assert (indexable_seg != NULL);
1688 g_assert (seg != indexable_seg);
1690 if ( (seg->type == >k_text_toggle_on_type ||
1691 seg->type == >k_text_toggle_off_type) &&
1692 (seg->body.toggle.info == info) )
1698 g_assert (seg != NULL);
1699 g_assert (indexable_seg != NULL);
1701 g_assert (seg != indexable_seg); /* If this happens, then
1702 forward_to_tag_toggle was
1704 g_assert (seg->body.toggle.info->tag == tag);
1706 /* If this happens, when previously tagging we didn't merge
1707 overlapping tags. */
1708 g_assert ( (toggled_on && seg->type == >k_text_toggle_off_type) ||
1709 (!toggled_on && seg->type == >k_text_toggle_on_type) );
1711 toggled_on = !toggled_on;
1714 printf ("deleting %s toggle\n",
1715 seg->type == >k_text_toggle_on_type ? "on" : "off");
1717 /* Remove toggle segment from the list. */
1720 line->segments = seg->next;
1724 while (prev->next != seg)
1728 prev->next = seg->next;
1731 /* Inform iterators we've hosed them. This actually reflects a
1732 bit of inefficiency; if you have the same tag toggled on and
1733 off a lot in a single line, we keep having the rescan from
1734 the front of the line. Of course we have to do that to get
1735 "prev" anyway, but here we are doing it an additional
1737 segments_changed (tree);
1739 /* Update node counts */
1740 if (seg->body.toggle.inNodeCounts)
1742 _gtk_change_node_toggle_count (line->parent,
1744 seg->body.toggle.inNodeCounts = FALSE;
1749 /* We only clean up lines when we're done with them, saves some
1750 gratuitous line-segment-traversals */
1752 if (cleanupline != line)
1754 cleanup_line (cleanupline);
1759 iter_stack_free (stack);
1761 /* toggled_on now reflects the toggle state _just before_ the
1762 end iterator. The end iterator could already have a toggle
1763 on or a toggle off. */
1764 if ( (add && !toggled_on) ||
1765 (!add && toggled_on) )
1767 /* This could create a second toggle at the start position;
1768 cleanup_line () will remove it if so. */
1770 seg = _gtk_toggle_segment_new (info, !add);
1772 prev = gtk_text_line_segment_split (&end);
1775 seg->next = end_line->segments;
1776 end_line->segments = seg;
1780 seg->next = prev->next;
1783 /* cleanup_line adds the new toggle to the node counts. */
1784 g_assert (seg->body.toggle.inNodeCounts == FALSE);
1786 printf ("added toggle at end\n");
1791 * Cleanup cleanupline and the last line of the range, if
1792 * these are different.
1795 cleanup_line (cleanupline);
1796 if (cleanupline != end_line)
1798 cleanup_line (end_line);
1801 segments_changed (tree);
1803 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1804 _gtk_text_btree_check (tree);
1813 _gtk_text_btree_get_line (GtkTextBTree *tree,
1815 gint *real_line_number)
1817 GtkTextBTreeNode *node;
1822 line_count = _gtk_text_btree_line_count (tree);
1824 if (line_number < 0)
1826 line_number = line_count;
1828 else if (line_number > line_count)
1830 line_number = line_count;
1833 if (real_line_number)
1834 *real_line_number = line_number;
1836 node = tree->root_node;
1837 lines_left = line_number;
1840 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1844 while (node->level != 0)
1846 for (node = node->children.node;
1847 node->num_lines <= lines_left;
1853 g_error ("gtk_text_btree_find_line ran out of GtkTextBTreeNodes");
1856 lines_left -= node->num_lines;
1861 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1864 for (line = node->children.line; lines_left > 0;
1870 g_error ("gtk_text_btree_find_line ran out of lines");
1879 _gtk_text_btree_get_line_at_char (GtkTextBTree *tree,
1881 gint *line_start_index,
1882 gint *real_char_index)
1884 GtkTextBTreeNode *node;
1886 GtkTextLineSegment *seg;
1891 node = tree->root_node;
1893 /* Clamp to valid indexes (-1 is magic for "highest index") */
1894 if (char_index < 0 || char_index >= node->num_chars)
1896 char_index = node->num_chars - 1;
1899 *real_char_index = char_index;
1902 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1906 chars_left = char_index;
1907 while (node->level != 0)
1909 for (node = node->children.node;
1910 chars_left >= node->num_chars;
1913 chars_left -= node->num_chars;
1915 g_assert (chars_left >= 0);
1919 if (chars_left == 0)
1921 /* Start of a line */
1923 *line_start_index = char_index;
1924 return node->children.line;
1928 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1934 for (line = node->children.line; line != NULL; line = line->next)
1936 seg = line->segments;
1939 if (chars_in_line + seg->char_count > chars_left)
1940 goto found; /* found our line/segment */
1942 chars_in_line += seg->char_count;
1947 chars_left -= chars_in_line;
1955 g_assert (line != NULL); /* hosage, ran out of lines */
1956 g_assert (seg != NULL);
1958 *line_start_index = char_index - chars_left;
1963 _gtk_text_btree_get_tags (const GtkTextIter *iter,
1966 GtkTextBTreeNode *node;
1967 GtkTextLine *siblingline;
1968 GtkTextLineSegment *seg;
1969 int src, dst, index;
1975 #define NUM_TAG_INFOS 10
1977 line = gtk_text_iter_get_text_line (iter);
1978 tree = gtk_text_iter_get_btree (iter);
1979 byte_index = gtk_text_iter_get_line_index (iter);
1981 tagInfo.numTags = 0;
1982 tagInfo.arraySize = NUM_TAG_INFOS;
1983 tagInfo.tags = g_new (GtkTextTag*, NUM_TAG_INFOS);
1984 tagInfo.counts = g_new (int, NUM_TAG_INFOS);
1987 * Record tag toggles within the line of indexPtr but preceding
1988 * indexPtr. Note that if this loop segfaults, your
1989 * byte_index probably points past the sum of all
1990 * seg->byte_count */
1992 for (index = 0, seg = line->segments;
1993 (index + seg->byte_count) <= byte_index;
1994 index += seg->byte_count, seg = seg->next)
1996 if ((seg->type == >k_text_toggle_on_type)
1997 || (seg->type == >k_text_toggle_off_type))
1999 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2004 * Record toggles for tags in lines that are predecessors of
2005 * line but under the same level-0 GtkTextBTreeNode.
2008 for (siblingline = line->parent->children.line;
2009 siblingline != line;
2010 siblingline = siblingline->next)
2012 for (seg = siblingline->segments; seg != NULL;
2015 if ((seg->type == >k_text_toggle_on_type)
2016 || (seg->type == >k_text_toggle_off_type))
2018 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2024 * For each GtkTextBTreeNode in the ancestry of this line, record tag
2025 * toggles for all siblings that precede that GtkTextBTreeNode.
2028 for (node = line->parent; node->parent != NULL;
2029 node = node->parent)
2031 GtkTextBTreeNode *siblingPtr;
2034 for (siblingPtr = node->parent->children.node;
2035 siblingPtr != node; siblingPtr = siblingPtr->next)
2037 for (summary = siblingPtr->summary; summary != NULL;
2038 summary = summary->next)
2040 if (summary->toggle_count & 1)
2042 inc_count (summary->info->tag, summary->toggle_count,
2050 * Go through the tag information and squash out all of the tags
2051 * that have even toggle counts (these tags exist before the point
2052 * of interest, but not at the desired character itself).
2055 for (src = 0, dst = 0; src < tagInfo.numTags; src++)
2057 if (tagInfo.counts[src] & 1)
2059 g_assert (GTK_IS_TEXT_TAG (tagInfo.tags[src]));
2060 tagInfo.tags[dst] = tagInfo.tags[src];
2066 g_free (tagInfo.counts);
2069 g_free (tagInfo.tags);
2072 return tagInfo.tags;
2076 copy_segment (GString *string,
2077 gboolean include_hidden,
2078 gboolean include_nonchars,
2079 const GtkTextIter *start,
2080 const GtkTextIter *end)
2082 GtkTextLineSegment *end_seg;
2083 GtkTextLineSegment *seg;
2085 if (gtk_text_iter_equal (start, end))
2088 seg = gtk_text_iter_get_indexable_segment (start);
2089 end_seg = gtk_text_iter_get_indexable_segment (end);
2091 if (seg->type == >k_text_char_type)
2093 gboolean copy = TRUE;
2094 gint copy_bytes = 0;
2095 gint copy_start = 0;
2097 /* Don't copy if we're invisible; segments are invisible/not
2098 as a whole, no need to check each char */
2099 if (!include_hidden &&
2100 _gtk_text_btree_char_is_invisible (start))
2103 /* printf (" <invisible>\n"); */
2106 copy_start = gtk_text_iter_get_segment_byte (start);
2110 /* End is in the same segment; need to copy fewer bytes. */
2111 gint end_byte = gtk_text_iter_get_segment_byte (end);
2113 copy_bytes = end_byte - copy_start;
2116 copy_bytes = seg->byte_count - copy_start;
2118 g_assert (copy_bytes != 0); /* Due to iter equality check at
2119 front of this function. */
2123 g_assert ((copy_start + copy_bytes) <= seg->byte_count);
2125 g_string_append_len (string,
2126 seg->body.chars + copy_start,
2130 /* printf (" :%s\n", string->str); */
2132 else if (seg->type == >k_text_pixbuf_type ||
2133 seg->type == >k_text_child_type)
2135 gboolean copy = TRUE;
2137 if (!include_nonchars)
2141 else if (!include_hidden &&
2142 _gtk_text_btree_char_is_invisible (start))
2149 g_string_append_len (string,
2150 gtk_text_unknown_char_utf8,
2158 _gtk_text_btree_get_text (const GtkTextIter *start_orig,
2159 const GtkTextIter *end_orig,
2160 gboolean include_hidden,
2161 gboolean include_nonchars)
2163 GtkTextLineSegment *seg;
2164 GtkTextLineSegment *end_seg;
2172 g_return_val_if_fail (start_orig != NULL, NULL);
2173 g_return_val_if_fail (end_orig != NULL, NULL);
2174 g_return_val_if_fail (gtk_text_iter_get_btree (start_orig) ==
2175 gtk_text_iter_get_btree (end_orig), NULL);
2177 start = *start_orig;
2180 gtk_text_iter_reorder (&start, &end);
2182 retval = g_string_new ("");
2184 tree = gtk_text_iter_get_btree (&start);
2186 end_seg = gtk_text_iter_get_indexable_segment (&end);
2188 seg = gtk_text_iter_get_indexable_segment (&iter);
2189 while (seg != end_seg)
2191 copy_segment (retval, include_hidden, include_nonchars,
2194 gtk_text_iter_forward_indexable_segment (&iter);
2196 seg = gtk_text_iter_get_indexable_segment (&iter);
2199 copy_segment (retval, include_hidden, include_nonchars, &iter, &end);
2202 g_string_free (retval, FALSE);
2207 _gtk_text_btree_line_count (GtkTextBTree *tree)
2209 /* Subtract bogus line at the end; we return a count
2211 return tree->root_node->num_lines - 1;
2215 _gtk_text_btree_char_count (GtkTextBTree *tree)
2217 /* Exclude newline in bogus last line */
2218 return tree->root_node->num_chars - 1;
2221 #define LOTSA_TAGS 1000
2223 _gtk_text_btree_char_is_invisible (const GtkTextIter *iter)
2225 gboolean invisible = FALSE; /* if nobody says otherwise, it's visible */
2227 int deftagCnts[LOTSA_TAGS];
2228 int *tagCnts = deftagCnts;
2229 GtkTextTag *deftags[LOTSA_TAGS];
2230 GtkTextTag **tags = deftags;
2232 GtkTextBTreeNode *node;
2233 GtkTextLine *siblingline;
2234 GtkTextLineSegment *seg;
2241 line = gtk_text_iter_get_text_line (iter);
2242 tree = gtk_text_iter_get_btree (iter);
2243 byte_index = gtk_text_iter_get_line_index (iter);
2245 numTags = gtk_text_tag_table_size (tree->table);
2247 /* almost always avoid malloc, so stay out of system calls */
2248 if (LOTSA_TAGS < numTags)
2250 tagCnts = g_new (int, numTags);
2251 tags = g_new (GtkTextTag*, numTags);
2254 for (i=0; i<numTags; i++)
2260 * Record tag toggles within the line of indexPtr but preceding
2264 for (index = 0, seg = line->segments;
2265 (index + seg->byte_count) <= byte_index; /* segfault here means invalid index */
2266 index += seg->byte_count, seg = seg->next)
2268 if ((seg->type == >k_text_toggle_on_type)
2269 || (seg->type == >k_text_toggle_off_type))
2271 tag = seg->body.toggle.info->tag;
2272 if (tag->invisible_set && tag->values->invisible)
2274 tags[tag->priority] = tag;
2275 tagCnts[tag->priority]++;
2281 * Record toggles for tags in lines that are predecessors of
2282 * line but under the same level-0 GtkTextBTreeNode.
2285 for (siblingline = line->parent->children.line;
2286 siblingline != line;
2287 siblingline = siblingline->next)
2289 for (seg = siblingline->segments; seg != NULL;
2292 if ((seg->type == >k_text_toggle_on_type)
2293 || (seg->type == >k_text_toggle_off_type))
2295 tag = seg->body.toggle.info->tag;
2296 if (tag->invisible_set && tag->values->invisible)
2298 tags[tag->priority] = tag;
2299 tagCnts[tag->priority]++;
2306 * For each GtkTextBTreeNode in the ancestry of this line, record tag toggles
2307 * for all siblings that precede that GtkTextBTreeNode.
2310 for (node = line->parent; node->parent != NULL;
2311 node = node->parent)
2313 GtkTextBTreeNode *siblingPtr;
2316 for (siblingPtr = node->parent->children.node;
2317 siblingPtr != node; siblingPtr = siblingPtr->next)
2319 for (summary = siblingPtr->summary; summary != NULL;
2320 summary = summary->next)
2322 if (summary->toggle_count & 1)
2324 tag = summary->info->tag;
2325 if (tag->invisible_set && tag->values->invisible)
2327 tags[tag->priority] = tag;
2328 tagCnts[tag->priority] += summary->toggle_count;
2336 * Now traverse from highest priority to lowest,
2337 * take invisible value from first odd count (= on)
2340 for (i = numTags-1; i >=0; i--)
2344 /* FIXME not sure this should be if 0 */
2346 #ifndef ALWAYS_SHOW_SELECTION
2347 /* who would make the selection invisible? */
2348 if ((tag == tkxt->seltag)
2349 && !(tkxt->flags & GOT_FOCUS))
2355 invisible = tags[i]->values->invisible;
2360 if (LOTSA_TAGS < numTags)
2375 redisplay_region (GtkTextBTree *tree,
2376 const GtkTextIter *start,
2377 const GtkTextIter *end)
2380 GtkTextLine *start_line, *end_line;
2382 if (gtk_text_iter_compare (start, end) > 0)
2384 const GtkTextIter *tmp = start;
2389 start_line = gtk_text_iter_get_text_line (start);
2390 end_line = gtk_text_iter_get_text_line (end);
2393 while (view != NULL)
2395 gint start_y, end_y;
2396 GtkTextLineData *ld;
2398 start_y = _gtk_text_btree_find_line_top (tree, start_line, view->view_id);
2400 if (end_line == start_line)
2403 end_y = _gtk_text_btree_find_line_top (tree, end_line, view->view_id);
2405 ld = _gtk_text_line_get_data (end_line, view->view_id);
2407 end_y += ld->height;
2409 gtk_text_layout_changed (view->layout, start_y,
2418 redisplay_mark (GtkTextLineSegment *mark)
2423 _gtk_text_btree_get_iter_at_mark (mark->body.mark.tree,
2425 mark->body.mark.obj);
2428 gtk_text_iter_forward_char (&end);
2430 _gtk_text_btree_invalidate_region (mark->body.mark.tree,
2435 redisplay_mark_if_visible (GtkTextLineSegment *mark)
2437 if (!mark->body.mark.visible)
2440 redisplay_mark (mark);
2444 ensure_not_off_end (GtkTextBTree *tree,
2445 GtkTextLineSegment *mark,
2448 if (gtk_text_iter_get_line (iter) ==
2449 _gtk_text_btree_line_count (tree))
2450 gtk_text_iter_backward_char (iter);
2453 static GtkTextLineSegment*
2454 real_set_mark (GtkTextBTree *tree,
2455 GtkTextMark *existing_mark,
2457 gboolean left_gravity,
2458 const GtkTextIter *where,
2459 gboolean should_exist,
2460 gboolean redraw_selections)
2462 GtkTextLineSegment *mark;
2465 g_return_val_if_fail (tree != NULL, NULL);
2466 g_return_val_if_fail (where != NULL, NULL);
2467 g_return_val_if_fail (gtk_text_iter_get_btree (where) == tree, NULL);
2470 mark = existing_mark->segment;
2471 else if (name != NULL)
2472 mark = g_hash_table_lookup (tree->mark_table,
2477 if (should_exist && mark == NULL)
2479 g_warning ("No mark `%s' exists!", name);
2483 /* OK if !should_exist and it does already exist, in that case
2489 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2490 gtk_text_iter_check (&iter);
2494 if (redraw_selections &&
2495 (mark == tree->insert_mark->segment ||
2496 mark == tree->selection_bound_mark->segment))
2498 GtkTextIter old_pos;
2500 _gtk_text_btree_get_iter_at_mark (tree, &old_pos,
2501 mark->body.mark.obj);
2502 redisplay_region (tree, &old_pos, where);
2506 * don't let visible marks be after the final newline of the
2510 if (mark->body.mark.visible)
2512 ensure_not_off_end (tree, mark, &iter);
2515 /* Redraw the mark's old location. */
2516 redisplay_mark_if_visible (mark);
2518 /* Unlink mark from its current location.
2519 This could hose our iterator... */
2520 gtk_text_btree_unlink_segment (tree, mark,
2521 mark->body.mark.line);
2522 mark->body.mark.line = gtk_text_iter_get_text_line (&iter);
2523 g_assert (mark->body.mark.line == gtk_text_iter_get_text_line (&iter));
2525 segments_changed (tree); /* make sure the iterator recomputes its
2530 mark = _gtk_mark_segment_new (tree,
2534 mark->body.mark.line = gtk_text_iter_get_text_line (&iter);
2536 if (mark->body.mark.name)
2537 g_hash_table_insert (tree->mark_table,
2538 mark->body.mark.name,
2542 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2543 gtk_text_iter_check (&iter);
2545 /* Link mark into new location */
2546 gtk_text_btree_link_segment (mark, &iter);
2548 /* Invalidate some iterators. */
2549 segments_changed (tree);
2552 * update the screen at the mark's new location.
2555 redisplay_mark_if_visible (mark);
2557 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2558 gtk_text_iter_check (&iter);
2560 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2561 _gtk_text_btree_check (tree);
2568 _gtk_text_btree_set_mark (GtkTextBTree *tree,
2569 GtkTextMark *existing_mark,
2571 gboolean left_gravity,
2572 const GtkTextIter *iter,
2573 gboolean should_exist)
2575 GtkTextLineSegment *seg;
2577 seg = real_set_mark (tree, existing_mark,
2578 name, left_gravity, iter, should_exist,
2581 return seg ? seg->body.mark.obj : NULL;
2585 _gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2589 GtkTextIter tmp_start, tmp_end;
2591 _gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2593 _gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2594 tree->selection_bound_mark);
2596 if (gtk_text_iter_equal (&tmp_start, &tmp_end))
2608 gtk_text_iter_reorder (&tmp_start, &tmp_end);
2621 _gtk_text_btree_place_cursor (GtkTextBTree *tree,
2622 const GtkTextIter *iter)
2624 GtkTextIter start, end;
2626 if (_gtk_text_btree_get_selection_bounds (tree, &start, &end))
2627 redisplay_region (tree, &start, &end);
2629 /* Move insert AND selection_bound before we redisplay */
2630 real_set_mark (tree, tree->insert_mark,
2631 "insert", FALSE, iter, TRUE, FALSE);
2632 real_set_mark (tree, tree->selection_bound_mark,
2633 "selection_bound", FALSE, iter, TRUE, FALSE);
2637 _gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2642 g_return_if_fail (tree != NULL);
2643 g_return_if_fail (name != NULL);
2645 mark = g_hash_table_lookup (tree->mark_table,
2648 _gtk_text_btree_remove_mark (tree, mark);
2652 _gtk_text_btree_remove_mark (GtkTextBTree *tree,
2655 GtkTextLineSegment *segment;
2657 g_return_if_fail (mark != NULL);
2658 g_return_if_fail (tree != NULL);
2660 segment = mark->segment;
2662 if (segment->body.mark.not_deleteable)
2664 g_warning ("Can't delete special mark `%s'", segment->body.mark.name);
2668 /* This calls cleanup_line and segments_changed */
2669 gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2671 if (segment->body.mark.name)
2672 g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2674 /* Remove the ref on the mark that belonged to the segment. */
2675 g_object_unref (G_OBJECT (mark));
2677 segment->body.mark.tree = NULL;
2678 segment->body.mark.line = NULL;
2682 _gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2683 GtkTextMark *segment)
2685 return segment == tree->insert_mark;
2689 _gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2690 GtkTextMark *segment)
2692 return segment == tree->selection_bound_mark;
2696 _gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2699 GtkTextLineSegment *seg;
2701 g_return_val_if_fail (tree != NULL, NULL);
2702 g_return_val_if_fail (name != NULL, NULL);
2704 seg = g_hash_table_lookup (tree->mark_table, name);
2706 return seg ? seg->body.mark.obj : NULL;
2710 gtk_text_mark_set_visible (GtkTextMark *mark,
2713 GtkTextLineSegment *seg;
2715 g_return_if_fail (mark != NULL);
2717 seg = mark->segment;
2719 if (seg->body.mark.visible == setting)
2723 seg->body.mark.visible = setting;
2725 redisplay_mark (seg);
2730 _gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
2733 GtkTextBTreeNode *node;
2734 GtkTextTagInfo *info;
2736 g_return_val_if_fail (tree != NULL, NULL);
2740 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2745 if (info->tag_root == NULL)
2748 node = info->tag_root;
2750 /* We know the tag root has instances of the given
2753 continue_outer_loop:
2754 g_assert (node != NULL);
2755 while (node->level > 0)
2757 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2758 node = node->children.node;
2759 while (node != NULL)
2761 if (gtk_text_btree_node_has_tag (node, tag))
2762 goto continue_outer_loop;
2766 g_assert (node != NULL);
2769 g_assert (node != NULL); /* The tag summaries said some node had
2772 g_assert (node->level == 0);
2774 return node->children.line;
2778 /* Looking for any tag at all (tag == NULL).
2779 Unfortunately this can't be done in a simple and efficient way
2780 right now; so I'm just going to return the
2781 first line in the btree. FIXME */
2782 return _gtk_text_btree_get_line (tree, 0, NULL);
2787 _gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
2790 GtkTextBTreeNode *node;
2791 GtkTextBTreeNode *last_node;
2793 GtkTextTagInfo *info;
2795 g_return_val_if_fail (tree != NULL, NULL);
2799 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2801 if (info->tag_root == NULL)
2804 node = info->tag_root;
2805 /* We know the tag root has instances of the given
2808 while (node->level > 0)
2810 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2812 node = node->children.node;
2813 while (node != NULL)
2815 if (gtk_text_btree_node_has_tag (node, tag))
2823 g_assert (node != NULL); /* The tag summaries said some node had
2826 g_assert (node->level == 0);
2828 /* Find the last line in this node */
2829 line = node->children.line;
2830 while (line->next != NULL)
2837 /* This search can't be done efficiently at the moment,
2838 at least not without complexity.
2839 So, we just return the last line.
2841 return _gtk_text_btree_get_line (tree, -1, NULL);
2851 _gtk_text_line_get_number (GtkTextLine *line)
2854 GtkTextBTreeNode *node, *parent, *node2;
2858 * First count how many lines precede this one in its level-0
2862 node = line->parent;
2864 for (line2 = node->children.line; line2 != line;
2865 line2 = line2->next)
2869 g_error ("gtk_text_btree_line_number couldn't find line");
2875 * Now work up through the levels of the tree one at a time,
2876 * counting how many lines are in GtkTextBTreeNodes preceding the current
2880 for (parent = node->parent ; parent != NULL;
2881 node = parent, parent = parent->parent)
2883 for (node2 = parent->children.node; node2 != node;
2884 node2 = node2->next)
2888 g_error ("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
2890 index += node2->num_lines;
2896 static GtkTextLineSegment*
2897 find_toggle_segment_before_char (GtkTextLine *line,
2901 GtkTextLineSegment *seg;
2902 GtkTextLineSegment *toggle_seg;
2907 seg = line->segments;
2908 while ( (index + seg->char_count) <= char_in_line )
2910 if (((seg->type == >k_text_toggle_on_type)
2911 || (seg->type == >k_text_toggle_off_type))
2912 && (seg->body.toggle.info->tag == tag))
2915 index += seg->char_count;
2922 static GtkTextLineSegment*
2923 find_toggle_segment_before_byte (GtkTextLine *line,
2927 GtkTextLineSegment *seg;
2928 GtkTextLineSegment *toggle_seg;
2933 seg = line->segments;
2934 while ( (index + seg->byte_count) <= byte_in_line )
2936 if (((seg->type == >k_text_toggle_on_type)
2937 || (seg->type == >k_text_toggle_off_type))
2938 && (seg->body.toggle.info->tag == tag))
2941 index += seg->byte_count;
2949 find_toggle_outside_current_line (GtkTextLine *line,
2953 GtkTextBTreeNode *node;
2954 GtkTextLine *sibling_line;
2955 GtkTextLineSegment *seg;
2956 GtkTextLineSegment *toggle_seg;
2958 GtkTextTagInfo *info = NULL;
2961 * No toggle in this line. Look for toggles for the tag in lines
2962 * that are predecessors of line but under the same
2963 * level-0 GtkTextBTreeNode.
2966 sibling_line = line->parent->children.line;
2967 while (sibling_line != line)
2969 seg = sibling_line->segments;
2972 if (((seg->type == >k_text_toggle_on_type)
2973 || (seg->type == >k_text_toggle_off_type))
2974 && (seg->body.toggle.info->tag == tag))
2980 sibling_line = sibling_line->next;
2983 if (toggle_seg != NULL)
2984 return (toggle_seg->type == >k_text_toggle_on_type);
2987 * No toggle in this GtkTextBTreeNode. Scan upwards through the ancestors of
2988 * this GtkTextBTreeNode, counting the number of toggles of the given tag in
2989 * siblings that precede that GtkTextBTreeNode.
2992 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2998 node = line->parent;
2999 while (node->parent != NULL)
3001 GtkTextBTreeNode *sibling_node;
3003 sibling_node = node->parent->children.node;
3004 while (sibling_node != node)
3008 summary = sibling_node->summary;
3009 while (summary != NULL)
3011 if (summary->info == info)
3012 toggles += summary->toggle_count;
3014 summary = summary->next;
3017 sibling_node = sibling_node->next;
3020 if (node == info->tag_root)
3023 node = node->parent;
3027 * An odd number of toggles means that the tag is present at the
3031 return (toggles & 1) != 0;
3034 /* FIXME this function is far too slow, for no good reason. */
3036 _gtk_text_line_char_has_tag (GtkTextLine *line,
3041 GtkTextLineSegment *toggle_seg;
3043 g_return_val_if_fail (line != NULL, FALSE);
3046 * Check for toggles for the tag in the line but before
3047 * the char. If there is one, its type indicates whether or
3048 * not the character is tagged.
3051 toggle_seg = find_toggle_segment_before_char (line, char_in_line, tag);
3053 if (toggle_seg != NULL)
3054 return (toggle_seg->type == >k_text_toggle_on_type);
3056 return find_toggle_outside_current_line (line, tree, tag);
3060 _gtk_text_line_byte_has_tag (GtkTextLine *line,
3065 GtkTextLineSegment *toggle_seg;
3067 g_return_val_if_fail (line != NULL, FALSE);
3070 * Check for toggles for the tag in the line but before
3071 * the char. If there is one, its type indicates whether or
3072 * not the character is tagged.
3075 toggle_seg = find_toggle_segment_before_byte (line, byte_in_line, tag);
3077 if (toggle_seg != NULL)
3078 return (toggle_seg->type == >k_text_toggle_on_type);
3080 return find_toggle_outside_current_line (line, tree, tag);
3084 _gtk_text_line_is_last (GtkTextLine *line,
3087 return line == get_last_line (tree);
3091 _gtk_text_line_next (GtkTextLine *line)
3093 GtkTextBTreeNode *node;
3095 if (line->next != NULL)
3100 * This was the last line associated with the particular parent
3101 * GtkTextBTreeNode. Search up the tree for the next GtkTextBTreeNode,
3102 * then search down from that GtkTextBTreeNode to find the first
3106 node = line->parent;
3107 while (node != NULL && node->next == NULL)
3108 node = node->parent;
3114 while (node->level > 0)
3116 node = node->children.node;
3119 g_assert (node->children.line != line);
3121 return node->children.line;
3126 _gtk_text_line_previous (GtkTextLine *line)
3128 GtkTextBTreeNode *node;
3129 GtkTextBTreeNode *node2;
3133 * Find the line under this GtkTextBTreeNode just before the starting line.
3135 prev = line->parent->children.line; /* First line at leaf */
3136 while (prev != line)
3138 if (prev->next == line)
3144 g_error ("gtk_text_btree_previous_line ran out of lines");
3148 * This was the first line associated with the particular parent
3149 * GtkTextBTreeNode. Search up the tree for the previous GtkTextBTreeNode,
3150 * then search down from that GtkTextBTreeNode to find its last line.
3152 for (node = line->parent; ; node = node->parent)
3154 if (node == NULL || node->parent == NULL)
3156 else if (node != node->parent->children.node)
3160 for (node2 = node->parent->children.node; ;
3161 node2 = node2->children.node)
3163 while (node2->next != node)
3164 node2 = node2->next;
3166 if (node2->level == 0)
3172 for (prev = node2->children.line ; ; prev = prev->next)
3174 if (prev->next == NULL)
3178 g_assert_not_reached ();
3183 _gtk_text_line_add_data (GtkTextLine *line,
3184 GtkTextLineData *data)
3186 g_return_if_fail (line != NULL);
3187 g_return_if_fail (data != NULL);
3188 g_return_if_fail (data->view_id != NULL);
3192 data->next = line->views;
3202 _gtk_text_line_remove_data (GtkTextLine *line,
3205 GtkTextLineData *prev;
3206 GtkTextLineData *iter;
3208 g_return_val_if_fail (line != NULL, NULL);
3209 g_return_val_if_fail (view_id != NULL, NULL);
3213 while (iter != NULL)
3215 if (iter->view_id == view_id)
3224 prev->next = iter->next;
3226 line->views = iter->next;
3235 _gtk_text_line_get_data (GtkTextLine *line,
3238 GtkTextLineData *iter;
3240 g_return_val_if_fail (line != NULL, NULL);
3241 g_return_val_if_fail (view_id != NULL, NULL);
3244 while (iter != NULL)
3246 if (iter->view_id == view_id)
3255 _gtk_text_line_invalidate_wrap (GtkTextLine *line,
3256 GtkTextLineData *ld)
3258 /* For now this is totally unoptimized. FIXME?
3260 We could probably optimize the case where the width removed
3261 is less than the max width for the parent node,
3262 and the case where the height is unchanged when we re-wrap.
3265 g_return_if_fail (ld != NULL);
3268 gtk_text_btree_node_invalidate_upward (line->parent, ld->view_id);
3272 _gtk_text_line_char_count (GtkTextLine *line)
3274 GtkTextLineSegment *seg;
3278 seg = line->segments;
3281 size += seg->char_count;
3288 _gtk_text_line_byte_count (GtkTextLine *line)
3290 GtkTextLineSegment *seg;
3294 seg = line->segments;
3297 size += seg->byte_count;
3305 _gtk_text_line_char_index (GtkTextLine *target_line)
3307 GSList *node_stack = NULL;
3308 GtkTextBTreeNode *iter;
3312 /* Push all our parent nodes onto a stack */
3313 iter = target_line->parent;
3315 g_assert (iter != NULL);
3317 while (iter != NULL)
3319 node_stack = g_slist_prepend (node_stack, iter);
3321 iter = iter->parent;
3324 /* Check that we have the root node on top of the stack. */
3325 g_assert (node_stack != NULL &&
3326 node_stack->data != NULL &&
3327 ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3329 /* Add up chars in all nodes before the nodes in our stack.
3333 iter = node_stack->data;
3334 while (iter != NULL)
3336 GtkTextBTreeNode *child_iter;
3337 GtkTextBTreeNode *next_node;
3339 next_node = node_stack->next ?
3340 node_stack->next->data : NULL;
3341 node_stack = g_slist_remove (node_stack, node_stack->data);
3343 if (iter->level == 0)
3345 /* stack should be empty when we're on the last node */
3346 g_assert (node_stack == NULL);
3347 break; /* Our children are now lines */
3350 g_assert (next_node != NULL);
3351 g_assert (iter != NULL);
3352 g_assert (next_node->parent == iter);
3354 /* Add up chars before us in the tree */
3355 child_iter = iter->children.node;
3356 while (child_iter != next_node)
3358 g_assert (child_iter != NULL);
3360 num_chars += child_iter->num_chars;
3362 child_iter = child_iter->next;
3368 g_assert (iter != NULL);
3369 g_assert (iter == target_line->parent);
3371 /* Since we don't store char counts in lines, only in segments, we
3372 have to iterate over the lines adding up segment char counts
3373 until we find our line. */
3374 line = iter->children.line;
3375 while (line != target_line)
3377 g_assert (line != NULL);
3379 num_chars += _gtk_text_line_char_count (line);
3384 g_assert (line == target_line);
3390 _gtk_text_line_byte_to_segment (GtkTextLine *line,
3394 GtkTextLineSegment *seg;
3397 g_return_val_if_fail (line != NULL, NULL);
3399 offset = byte_offset;
3400 seg = line->segments;
3402 while (offset >= seg->byte_count)
3404 g_assert (seg != NULL); /* means an invalid byte index */
3405 offset -= seg->byte_count;
3410 *seg_offset = offset;
3416 _gtk_text_line_char_to_segment (GtkTextLine *line,
3420 GtkTextLineSegment *seg;
3423 g_return_val_if_fail (line != NULL, NULL);
3425 offset = char_offset;
3426 seg = line->segments;
3428 while (offset >= seg->char_count)
3430 g_assert (seg != NULL); /* means an invalid char index */
3431 offset -= seg->char_count;
3436 *seg_offset = offset;
3442 _gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3446 GtkTextLineSegment *seg;
3449 g_return_val_if_fail (line != NULL, NULL);
3451 offset = byte_offset;
3452 seg = line->segments;
3454 while (offset > 0 && offset >= seg->byte_count)
3456 g_assert (seg != NULL); /* means an invalid byte index */
3457 offset -= seg->byte_count;
3462 *seg_offset = offset;
3468 _gtk_text_line_char_to_any_segment (GtkTextLine *line,
3472 GtkTextLineSegment *seg;
3475 g_return_val_if_fail (line != NULL, NULL);
3477 offset = char_offset;
3478 seg = line->segments;
3480 while (offset > 0 && offset >= seg->char_count)
3482 g_assert (seg != NULL); /* means an invalid byte index */
3483 offset -= seg->char_count;
3488 *seg_offset = offset;
3494 _gtk_text_line_byte_to_char (GtkTextLine *line,
3498 GtkTextLineSegment *seg;
3500 g_return_val_if_fail (line != NULL, 0);
3501 g_return_val_if_fail (byte_offset >= 0, 0);
3504 seg = line->segments;
3505 while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3506 the next segment) */
3508 g_assert (seg != NULL); /* our byte_index was bogus if this happens */
3510 byte_offset -= seg->byte_count;
3511 char_offset += seg->char_count;
3516 g_assert (seg != NULL);
3518 /* Now byte_offset is the offset into the current segment,
3519 and char_offset is the start of the current segment.
3520 Optimize the case where no chars use > 1 byte */
3521 if (seg->byte_count == seg->char_count)
3522 return char_offset + byte_offset;
3525 if (seg->type == >k_text_char_type)
3526 return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3529 g_assert (seg->char_count == 1);
3530 g_assert (byte_offset == 0);
3538 _gtk_text_line_char_to_byte (GtkTextLine *line,
3541 g_warning ("FIXME not implemented");
3546 /* FIXME sync with char_locate (or figure out a clean
3547 way to merge the two functions) */
3549 _gtk_text_line_byte_locate (GtkTextLine *line,
3551 GtkTextLineSegment **segment,
3552 GtkTextLineSegment **any_segment,
3553 gint *seg_byte_offset,
3554 gint *line_byte_offset)
3556 GtkTextLineSegment *seg;
3557 GtkTextLineSegment *after_prev_indexable;
3558 GtkTextLineSegment *after_last_indexable;
3559 GtkTextLineSegment *last_indexable;
3563 g_return_val_if_fail (line != NULL, FALSE);
3564 g_return_val_if_fail (byte_offset >= 0, FALSE);
3567 *any_segment = NULL;
3570 offset = byte_offset;
3572 last_indexable = NULL;
3573 after_last_indexable = line->segments;
3574 after_prev_indexable = line->segments;
3575 seg = line->segments;
3577 /* The loop ends when we're inside a segment;
3578 last_indexable refers to the last segment
3579 we passed entirely. */
3580 while (seg && offset >= seg->byte_count)
3582 if (seg->char_count > 0)
3584 offset -= seg->byte_count;
3585 bytes_in_line += seg->byte_count;
3586 last_indexable = seg;
3587 after_prev_indexable = after_last_indexable;
3588 after_last_indexable = last_indexable->next;
3596 /* We went off the end of the line */
3598 g_warning ("%s: byte index off the end of the line", G_STRLOC);
3605 if (after_last_indexable != NULL)
3606 *any_segment = after_last_indexable;
3608 *any_segment = *segment;
3611 /* Override any_segment if we're in the middle of a segment. */
3613 *any_segment = *segment;
3615 *seg_byte_offset = offset;
3617 g_assert (*segment != NULL);
3618 g_assert (*any_segment != NULL);
3619 g_assert (*seg_byte_offset < (*segment)->byte_count);
3621 *line_byte_offset = bytes_in_line + *seg_byte_offset;
3626 /* FIXME sync with byte_locate (or figure out a clean
3627 way to merge the two functions) */
3629 _gtk_text_line_char_locate (GtkTextLine *line,
3631 GtkTextLineSegment **segment,
3632 GtkTextLineSegment **any_segment,
3633 gint *seg_char_offset,
3634 gint *line_char_offset)
3636 GtkTextLineSegment *seg;
3637 GtkTextLineSegment *after_prev_indexable;
3638 GtkTextLineSegment *after_last_indexable;
3639 GtkTextLineSegment *last_indexable;
3643 g_return_val_if_fail (line != NULL, FALSE);
3644 g_return_val_if_fail (char_offset >= 0, FALSE);
3647 *any_segment = NULL;
3650 offset = char_offset;
3652 last_indexable = NULL;
3653 after_last_indexable = line->segments;
3654 after_prev_indexable = line->segments;
3655 seg = line->segments;
3657 /* The loop ends when we're inside a segment;
3658 last_indexable refers to the last segment
3659 we passed entirely. */
3660 while (seg && offset >= seg->char_count)
3662 if (seg->char_count > 0)
3664 offset -= seg->char_count;
3665 chars_in_line += seg->char_count;
3666 last_indexable = seg;
3667 after_prev_indexable = after_last_indexable;
3668 after_last_indexable = last_indexable->next;
3676 /* end of the line */
3678 g_warning ("%s: char offset off the end of the line", G_STRLOC);
3685 if (after_last_indexable != NULL)
3686 *any_segment = after_last_indexable;
3688 *any_segment = *segment;
3691 /* Override any_segment if we're in the middle of a segment. */
3693 *any_segment = *segment;
3695 *seg_char_offset = offset;
3697 g_assert (*segment != NULL);
3698 g_assert (*any_segment != NULL);
3699 g_assert (*seg_char_offset < (*segment)->char_count);
3701 *line_char_offset = chars_in_line + *seg_char_offset;
3707 _gtk_text_line_byte_to_char_offsets (GtkTextLine *line,
3709 gint *line_char_offset,
3710 gint *seg_char_offset)
3712 GtkTextLineSegment *seg;
3715 g_return_if_fail (line != NULL);
3716 g_return_if_fail (byte_offset >= 0);
3718 *line_char_offset = 0;
3720 offset = byte_offset;
3721 seg = line->segments;
3723 while (offset >= seg->byte_count)
3725 offset -= seg->byte_count;
3726 *line_char_offset += seg->char_count;
3728 g_assert (seg != NULL); /* means an invalid char offset */
3731 g_assert (seg->char_count > 0); /* indexable. */
3733 /* offset is now the number of bytes into the current segment we
3734 * want to go. Count chars into the current segment.
3737 if (seg->type == >k_text_char_type)
3739 *seg_char_offset = g_utf8_strlen (seg->body.chars, offset);
3741 g_assert (*seg_char_offset < seg->char_count);
3743 *line_char_offset += *seg_char_offset;
3747 g_assert (offset == 0);
3748 *seg_char_offset = 0;
3753 _gtk_text_line_char_to_byte_offsets (GtkTextLine *line,
3755 gint *line_byte_offset,
3756 gint *seg_byte_offset)
3758 GtkTextLineSegment *seg;
3761 g_return_if_fail (line != NULL);
3762 g_return_if_fail (char_offset >= 0);
3764 *line_byte_offset = 0;
3766 offset = char_offset;
3767 seg = line->segments;
3769 while (offset >= seg->char_count)
3771 offset -= seg->char_count;
3772 *line_byte_offset += seg->byte_count;
3774 g_assert (seg != NULL); /* means an invalid char offset */
3777 g_assert (seg->char_count > 0); /* indexable. */
3779 /* offset is now the number of chars into the current segment we
3780 want to go. Count bytes into the current segment. */
3782 if (seg->type == >k_text_char_type)
3784 *seg_byte_offset = 0;
3788 const char * start = seg->body.chars + *seg_byte_offset;
3790 bytes = g_utf8_next_char (start) - start;
3791 *seg_byte_offset += bytes;
3795 g_assert (*seg_byte_offset < seg->byte_count);
3797 *line_byte_offset += *seg_byte_offset;
3801 g_assert (offset == 0);
3802 *seg_byte_offset = 0;
3807 node_compare (GtkTextBTreeNode *lhs,
3808 GtkTextBTreeNode *rhs)
3810 GtkTextBTreeNode *iter;
3811 GtkTextBTreeNode *node;
3812 GtkTextBTreeNode *common_parent;
3813 GtkTextBTreeNode *parent_of_lower;
3814 GtkTextBTreeNode *parent_of_higher;
3815 gboolean lhs_is_lower;
3816 GtkTextBTreeNode *lower;
3817 GtkTextBTreeNode *higher;
3819 /* This function assumes that lhs and rhs are not underneath each
3826 if (lhs->level < rhs->level)
3828 lhs_is_lower = TRUE;
3834 lhs_is_lower = FALSE;
3839 /* Algorithm: find common parent of lhs/rhs. Save the child nodes
3840 * of the common parent we used to reach the common parent; the
3841 * ordering of these child nodes in the child list is the ordering
3845 /* Get on the same level (may be on same level already) */
3847 while (node->level < higher->level)
3848 node = node->parent;
3850 g_assert (node->level == higher->level);
3852 g_assert (node != higher); /* Happens if lower is underneath higher */
3854 /* Go up until we have two children with a common parent.
3856 parent_of_lower = node;
3857 parent_of_higher = higher;
3859 while (parent_of_lower->parent != parent_of_higher->parent)
3861 parent_of_lower = parent_of_lower->parent;
3862 parent_of_higher = parent_of_higher->parent;
3865 g_assert (parent_of_lower->parent == parent_of_higher->parent);
3867 common_parent = parent_of_lower->parent;
3869 g_assert (common_parent != NULL);
3871 /* See which is first in the list of common_parent's children */
3872 iter = common_parent->children.node;
3873 while (iter != NULL)
3875 if (iter == parent_of_higher)
3877 /* higher is less than lower */
3880 return 1; /* lhs > rhs */
3884 else if (iter == parent_of_lower)
3886 /* lower is less than higher */
3889 return -1; /* lhs < rhs */
3897 g_assert_not_reached ();
3901 /* remember that tag == NULL means "any tag" */
3903 _gtk_text_line_next_could_contain_tag (GtkTextLine *line,
3907 GtkTextBTreeNode *node;
3908 GtkTextTagInfo *info;
3909 gboolean below_tag_root;
3911 g_return_val_if_fail (line != NULL, NULL);
3913 if (gtk_debug_flags & GTK_DEBUG_TEXT)
3914 _gtk_text_btree_check (tree);
3918 /* Right now we can only offer linear-search if the user wants
3919 * to know about any tag toggle at all.
3921 return _gtk_text_line_next (line);
3924 /* Our tag summaries only have node precision, not line
3925 precision. This means that if any line under a node could contain a
3926 tag, then any of the others could also contain a tag.
3928 In the future we could have some mechanism to keep track of how
3929 many toggles we've found under a node so far, since we have a
3930 count of toggles under the node. But for now I'm going with KISS.
3933 /* return same-node line, if any. */
3937 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3941 if (info->tag_root == NULL)
3944 if (info->tag_root == line->parent)
3945 return NULL; /* we were at the last line under the tag root */
3947 /* We need to go up out of this node, and on to the next one with
3948 toggles for the target tag. If we're below the tag root, we need to
3949 find the next node below the tag root that has tag summaries. If
3950 we're not below the tag root, we need to see if the tag root is
3951 after us in the tree, and if so, return the first line underneath
3954 node = line->parent;
3955 below_tag_root = FALSE;
3956 while (node != NULL)
3958 if (node == info->tag_root)
3960 below_tag_root = TRUE;
3964 node = node->parent;
3969 node = line->parent;
3970 while (node != info->tag_root)
3972 if (node->next == NULL)
3973 node = node->parent;
3978 if (gtk_text_btree_node_has_tag (node, tag))
3988 ordering = node_compare (line->parent, info->tag_root);
3992 /* Tag root is ahead of us, so search there. */
3993 node = info->tag_root;
3998 /* Tag root is after us, so no more lines that
3999 * could contain the tag.
4004 g_assert_not_reached ();
4009 g_assert (node != NULL);
4011 /* We have to find the first sub-node of this node that contains
4015 while (node->level > 0)
4017 g_assert (node != NULL); /* If this fails, it likely means an
4018 incorrect tag summary led us on a
4019 wild goose chase down this branch of
4021 node = node->children.node;
4022 while (node != NULL)
4024 if (gtk_text_btree_node_has_tag (node, tag))
4030 g_assert (node != NULL);
4031 g_assert (node->level == 0);
4033 return node->children.line;
4037 prev_line_under_node (GtkTextBTreeNode *node,
4042 prev = node->children.line;
4048 while (prev->next != line)
4058 _gtk_text_line_previous_could_contain_tag (GtkTextLine *line,
4062 GtkTextBTreeNode *node;
4063 GtkTextBTreeNode *found_node = NULL;
4064 GtkTextTagInfo *info;
4065 gboolean below_tag_root;
4067 GtkTextBTreeNode *line_ancestor;
4068 GtkTextBTreeNode *line_ancestor_parent;
4070 /* See next_could_contain_tag () for more extensive comments
4071 * on what's going on here.
4074 g_return_val_if_fail (line != NULL, NULL);
4076 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4077 _gtk_text_btree_check (tree);
4081 /* Right now we can only offer linear-search if the user wants
4082 * to know about any tag toggle at all.
4084 return _gtk_text_line_previous (line);
4087 /* Return same-node line, if any. */
4088 prev = prev_line_under_node (line->parent, line);
4092 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4096 if (info->tag_root == NULL)
4099 if (info->tag_root == line->parent)
4100 return NULL; /* we were at the first line under the tag root */
4102 /* Are we below the tag root */
4103 node = line->parent;
4104 below_tag_root = FALSE;
4105 while (node != NULL)
4107 if (node == info->tag_root)
4109 below_tag_root = TRUE;
4113 node = node->parent;
4118 /* Look for a previous node under this tag root that has our
4122 /* this assertion holds because line->parent is not the
4123 * tag root, we are below the tag root, and the tag
4126 g_assert (line->parent->parent != NULL);
4128 line_ancestor = line->parent;
4129 line_ancestor_parent = line->parent->parent;
4131 node = line_ancestor_parent->children.node;
4132 while (node != line_ancestor &&
4133 line_ancestor != info->tag_root)
4135 GSList *child_nodes = NULL;
4138 /* Create reverse-order list of nodes before
4141 while (node != line_ancestor
4144 child_nodes = g_slist_prepend (child_nodes, node);
4149 /* Try to find a node with our tag on it in the list */
4153 GtkTextBTreeNode *this_node = tmp->data;
4155 g_assert (this_node != line_ancestor);
4157 if (gtk_text_btree_node_has_tag (this_node, tag))
4159 found_node = this_node;
4160 g_slist_free (child_nodes);
4164 tmp = g_slist_next (tmp);
4167 g_slist_free (child_nodes);
4169 /* Didn't find anything on this level; go up one level. */
4170 line_ancestor = line_ancestor_parent;
4171 line_ancestor_parent = line_ancestor->parent;
4173 node = line_ancestor_parent->children.node;
4183 ordering = node_compare (line->parent, info->tag_root);
4187 /* Tag root is ahead of us, so no more lines
4194 /* Tag root is after us, so grab last tagged
4195 * line underneath the tag root.
4197 found_node = info->tag_root;
4201 g_assert_not_reached ();
4206 g_assert (found_node != NULL);
4208 /* We have to find the last sub-node of this node that contains
4213 while (node->level > 0)
4215 GSList *child_nodes = NULL;
4217 g_assert (node != NULL); /* If this fails, it likely means an
4218 incorrect tag summary led us on a
4219 wild goose chase down this branch of
4222 node = node->children.node;
4223 while (node != NULL)
4225 child_nodes = g_slist_prepend (child_nodes, node);
4229 node = NULL; /* detect failure to find a child node. */
4232 while (iter != NULL)
4234 if (gtk_text_btree_node_has_tag (iter->data, tag))
4236 /* recurse into this node. */
4241 iter = g_slist_next (iter);
4244 g_slist_free (child_nodes);
4246 g_assert (node != NULL);
4249 g_assert (node != NULL);
4250 g_assert (node->level == 0);
4252 /* this assertion is correct, but slow. */
4253 /* g_assert (node_compare (node, line->parent) < 0); */
4255 /* Return last line in this node. */
4257 prev = node->children.line;
4265 * Non-public function implementations
4269 summary_list_destroy (Summary *summary)
4272 while (summary != NULL)
4274 next = summary->next;
4275 summary_destroy (summary);
4281 get_last_line (GtkTextBTree *tree)
4283 if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
4289 n_lines = _gtk_text_btree_line_count (tree);
4291 g_assert (n_lines >= 1); /* num_lines doesn't return bogus last line. */
4293 line = _gtk_text_btree_get_line (tree, n_lines, &real_line);
4295 tree->end_iter_line_stamp = tree->chars_changed_stamp;
4296 tree->end_iter_line = line;
4299 return tree->end_iter_line;
4307 gtk_text_line_new (void)
4311 line = g_new0(GtkTextLine, 1);
4317 gtk_text_line_destroy (GtkTextBTree *tree, GtkTextLine *line)
4319 GtkTextLineData *ld;
4320 GtkTextLineData *next;
4322 g_return_if_fail (line != NULL);
4329 view = gtk_text_btree_get_view (tree, ld->view_id);
4331 g_assert (view != NULL);
4334 gtk_text_layout_free_line_data (view->layout, line, ld);
4343 gtk_text_line_set_parent (GtkTextLine *line,
4344 GtkTextBTreeNode *node)
4346 if (line->parent == node)
4348 line->parent = node;
4349 gtk_text_btree_node_invalidate_upward (node, NULL);
4353 cleanup_line (GtkTextLine *line)
4355 GtkTextLineSegment *seg, **prev_p;
4359 * Make a pass over all of the segments in the line, giving each
4360 * a chance to clean itself up. This could potentially change
4361 * the structure of the line, e.g. by merging two segments
4362 * together or having two segments cancel themselves; if so,
4363 * then repeat the whole process again, since the first structure
4364 * change might make other structure changes possible. Repeat
4365 * until eventually there are no changes.
4372 for (prev_p = &line->segments, seg = *prev_p;
4374 prev_p = &(*prev_p)->next, seg = *prev_p)
4376 if (seg->type->cleanupFunc != NULL)
4378 *prev_p = (*seg->type->cleanupFunc)(seg, line);
4391 node_data_new (gpointer view_id)
4395 nd = g_new (NodeData, 1);
4397 nd->view_id = view_id;
4407 node_data_destroy (NodeData *nd)
4414 node_data_list_destroy (NodeData *nd)
4420 while (iter != NULL)
4423 node_data_destroy (iter);
4429 node_data_find (NodeData *nd, gpointer view_id)
4433 if (nd->view_id == view_id)
4441 summary_destroy (Summary *summary)
4443 /* Fill with error-triggering garbage */
4444 summary->info = (void*)0x1;
4445 summary->toggle_count = 567;
4446 summary->next = (void*)0x1;
4450 static GtkTextBTreeNode*
4451 gtk_text_btree_node_new (void)
4453 GtkTextBTreeNode *node;
4455 node = g_new (GtkTextBTreeNode, 1);
4457 node->node_data = NULL;
4463 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
4464 GtkTextTagInfo *info,
4469 summary = node->summary;
4470 while (summary != NULL)
4472 if (summary->info == info)
4474 summary->toggle_count += adjust;
4478 summary = summary->next;
4481 if (summary == NULL)
4483 /* didn't find a summary for our tag. */
4484 g_return_if_fail (adjust > 0);
4485 summary = g_new (Summary, 1);
4486 summary->info = info;
4487 summary->toggle_count = adjust;
4488 summary->next = node->summary;
4489 node->summary = summary;
4493 /* Note that the tag root and above do not have summaries
4494 for the tag; only nodes below the tag root have
4497 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4501 summary = node->summary;
4502 while (summary != NULL)
4505 summary->info->tag == tag)
4508 summary = summary->next;
4514 /* Add node and all children to the damage region. */
4516 gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node)
4520 nd = node->node_data;
4527 if (node->level == 0)
4531 line = node->children.line;
4532 while (line != NULL)
4534 GtkTextLineData *ld;
4548 GtkTextBTreeNode *child;
4550 child = node->children.node;
4552 while (child != NULL)
4554 gtk_text_btree_node_invalidate_downward (child);
4556 child = child->next;
4562 gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node, gpointer view_id)
4564 GtkTextBTreeNode *iter;
4567 while (iter != NULL)
4573 nd = node_data_find (iter->node_data, view_id);
4575 if (nd == NULL || !nd->valid)
4576 break; /* Once a node is invalid, we know its parents are as well. */
4582 gboolean should_continue = FALSE;
4584 nd = iter->node_data;
4589 should_continue = TRUE;
4596 if (!should_continue)
4597 break; /* This node was totally invalidated, so are its
4601 iter = iter->parent;
4607 * _gtk_text_btree_is_valid:
4608 * @tree: a #GtkTextBTree
4609 * @view_id: ID for the view
4611 * Check to see if the entire #GtkTextBTree is valid or not for
4614 * Return value: %TRUE if the entire #GtkTextBTree is valid
4617 _gtk_text_btree_is_valid (GtkTextBTree *tree,
4621 g_return_val_if_fail (tree != NULL, FALSE);
4623 nd = node_data_find (tree->root_node->node_data, view_id);
4624 return (nd && nd->valid);
4627 typedef struct _ValidateState ValidateState;
4629 struct _ValidateState
4631 gint remaining_pixels;
4632 gboolean in_validation;
4639 gtk_text_btree_node_validate (BTreeView *view,
4640 GtkTextBTreeNode *node,
4642 ValidateState *state)
4644 gint node_valid = TRUE;
4645 gint node_width = 0;
4646 gint node_height = 0;
4648 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4649 g_return_if_fail (!nd->valid);
4651 if (node->level == 0)
4653 GtkTextLine *line = node->children.line;
4654 GtkTextLineData *ld;
4656 /* Iterate over leading valid lines */
4657 while (line != NULL)
4659 ld = _gtk_text_line_get_data (line, view_id);
4661 if (!ld || !ld->valid)
4663 else if (state->in_validation)
4665 state->in_validation = FALSE;
4670 state->y += ld->height;
4671 node_width = MAX (ld->width, node_width);
4672 node_height += ld->height;
4678 state->in_validation = TRUE;
4680 /* Iterate over invalid lines */
4681 while (line != NULL)
4683 ld = _gtk_text_line_get_data (line, view_id);
4685 if (ld && ld->valid)
4690 state->old_height += ld->height;
4691 ld = gtk_text_layout_wrap (view->layout, line, ld);
4692 state->new_height += ld->height;
4694 node_width = MAX (ld->width, node_width);
4695 node_height += ld->height;
4697 state->remaining_pixels -= ld->height;
4698 if (state->remaining_pixels <= 0)
4708 /* Iterate over the remaining lines */
4709 while (line != NULL)
4711 ld = _gtk_text_line_get_data (line, view_id);
4712 state->in_validation = FALSE;
4714 if (!ld || !ld->valid)
4719 node_width = MAX (ld->width, node_width);
4720 node_height += ld->height;
4728 GtkTextBTreeNode *child;
4731 child = node->children.node;
4733 /* Iterate over leading valid nodes */
4736 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4738 if (!child_nd->valid)
4740 else if (state->in_validation)
4742 state->in_validation = FALSE;
4747 state->y += child_nd->height;
4748 node_width = MAX (node_width, child_nd->width);
4749 node_height += child_nd->height;
4752 child = child->next;
4755 /* Iterate over invalid nodes */
4758 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4760 if (child_nd->valid)
4764 gtk_text_btree_node_validate (view, child, view_id, state);
4766 if (!child_nd->valid)
4768 node_width = MAX (node_width, child_nd->width);
4769 node_height += child_nd->height;
4771 if (!state->in_validation || state->remaining_pixels <= 0)
4773 child = child->next;
4778 child = child->next;
4781 /* Iterate over the remaining lines */
4784 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4785 state->in_validation = FALSE;
4787 if (!child_nd->valid)
4790 node_width = MAX (child_nd->width, node_width);
4791 node_height += child_nd->height;
4793 child = child->next;
4797 nd->width = node_width;
4798 nd->height = node_height;
4799 nd->valid = node_valid;
4803 * _gtk_text_btree_validate:
4804 * @tree: a #GtkTextBTree
4806 * @max_pixels: the maximum number of pixels to validate. (No more
4807 * than one paragraph beyond this limit will be validated)
4808 * @y: location to store starting y coordinate of validated region
4809 * @old_height: location to store old height of validated region
4810 * @new_height: location to store new height of validated region
4812 * Validate a single contiguous invalid region of a #GtkTextBTree for
4815 * Return value: %TRUE if a region has been validated, %FALSE if the
4816 * entire tree was already valid.
4819 _gtk_text_btree_validate (GtkTextBTree *tree,
4828 g_return_val_if_fail (tree != NULL, FALSE);
4830 view = gtk_text_btree_get_view (tree, view_id);
4831 g_return_val_if_fail (view != NULL, FALSE);
4833 if (!_gtk_text_btree_is_valid (tree, view_id))
4835 ValidateState state;
4837 state.remaining_pixels = max_pixels;
4838 state.in_validation = FALSE;
4840 state.old_height = 0;
4841 state.new_height = 0;
4843 gtk_text_btree_node_validate (view,
4850 *old_height = state.old_height;
4852 *new_height = state.new_height;
4854 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4855 _gtk_text_btree_check (tree);
4864 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
4868 gboolean *valid_out)
4872 gboolean valid = TRUE;
4874 if (node->level == 0)
4876 GtkTextLine *line = node->children.line;
4878 while (line != NULL)
4880 GtkTextLineData *ld = _gtk_text_line_get_data (line, view_id);
4882 if (!ld || !ld->valid)
4887 width = MAX (ld->width, width);
4888 height += ld->height;
4896 GtkTextBTreeNode *child = node->children.node;
4900 NodeData *child_nd = node_data_find (child->node_data, view_id);
4902 if (!child_nd || !child_nd->valid)
4907 width = MAX (child_nd->width, width);
4908 height += child_nd->height;
4911 child = child->next;
4916 *height_out = height;
4921 /* Recompute the validity and size of the view data for a given
4922 * view at this node from the immediate children of the node
4925 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
4928 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4933 gtk_text_btree_node_compute_view_aggregates (node, view_id,
4934 &width, &height, &valid);
4936 nd->height = height;
4943 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
4948 gtk_text_btree_node_check_valid (node, view_id);
4949 node = node->parent;
4954 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
4957 if (node->level == 0)
4959 return gtk_text_btree_node_check_valid (node, view_id);
4963 GtkTextBTreeNode *child = node->children.node;
4965 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4973 NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
4975 if (!child_nd->valid)
4977 nd->width = MAX (child_nd->width, nd->width);
4978 nd->height += child_nd->height;
4980 child = child->next;
4989 * _gtk_text_btree_validate_line:
4990 * @tree: a #GtkTextBTree
4991 * @line: line to validate
4992 * @view_id: view ID for the view to validate
4994 * Revalidate a single line of the btree for the given view, propagate
4995 * results up through the entire tree.
4998 _gtk_text_btree_validate_line (GtkTextBTree *tree,
5002 GtkTextLineData *ld;
5005 g_return_if_fail (tree != NULL);
5006 g_return_if_fail (line != NULL);
5008 view = gtk_text_btree_get_view (tree, view_id);
5009 g_return_if_fail (view != NULL);
5011 ld = _gtk_text_line_get_data (line, view_id);
5012 if (!ld || !ld->valid)
5014 ld = gtk_text_layout_wrap (view->layout, line, ld);
5016 gtk_text_btree_node_check_valid_upward (line->parent, view_id);
5021 gtk_text_btree_node_remove_view (BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
5023 if (node->level == 0)
5027 line = node->children.line;
5028 while (line != NULL)
5030 GtkTextLineData *ld;
5032 ld = _gtk_text_line_remove_data (line, view_id);
5035 gtk_text_layout_free_line_data (view->layout, line, ld);
5042 GtkTextBTreeNode *child;
5044 child = node->children.node;
5046 while (child != NULL)
5049 gtk_text_btree_node_remove_view (view, child, view_id);
5051 child = child->next;
5055 gtk_text_btree_node_remove_data (node, view_id);
5059 gtk_text_btree_node_destroy (GtkTextBTree *tree, GtkTextBTreeNode *node)
5061 if (node->level == 0)
5064 GtkTextLineSegment *seg;
5066 while (node->children.line != NULL)
5068 line = node->children.line;
5069 node->children.line = line->next;
5070 while (line->segments != NULL)
5072 seg = line->segments;
5073 line->segments = seg->next;
5075 if (GTK_IS_TEXT_MARK_SEGMENT (seg))
5077 /* Set the mark as deleted */
5078 seg->body.mark.tree = NULL;
5079 seg->body.mark.line = NULL;
5082 (*seg->type->deleteFunc) (seg, line, 1);
5084 gtk_text_line_destroy (tree, line);
5089 GtkTextBTreeNode *childPtr;
5091 while (node->children.node != NULL)
5093 childPtr = node->children.node;
5094 node->children.node = childPtr->next;
5095 gtk_text_btree_node_destroy (tree, childPtr);
5099 summary_list_destroy (node->summary);
5100 node_data_list_destroy (node->node_data);
5105 gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node, gpointer view_id)
5109 nd = node->node_data;
5112 if (nd->view_id == view_id)
5119 nd = node_data_new (view_id);
5121 if (node->node_data)
5122 nd->next = node->node_data;
5124 node->node_data = nd;
5131 gtk_text_btree_node_remove_data (GtkTextBTreeNode *node, gpointer view_id)
5137 nd = node->node_data;
5140 if (nd->view_id == view_id)
5151 prev->next = nd->next;
5153 if (node->node_data == nd)
5154 node->node_data = nd->next;
5158 node_data_destroy (nd);
5162 gtk_text_btree_node_get_size (GtkTextBTreeNode *node, gpointer view_id,
5163 gint *width, gint *height)
5167 g_return_if_fail (width != NULL);
5168 g_return_if_fail (height != NULL);
5170 nd = gtk_text_btree_node_ensure_data (node, view_id);
5175 *height = nd->height;
5178 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5179 * here isn't quite right, since for a lot of operations we want to
5180 * know which children of the common parent correspond to the two nodes
5181 * (e.g., when computing the order of two iters)
5183 static GtkTextBTreeNode *
5184 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5185 GtkTextBTreeNode *node2)
5187 while (node1->level < node2->level)
5188 node1 = node1->parent;
5189 while (node2->level < node1->level)
5190 node2 = node2->parent;
5191 while (node1 != node2)
5193 node1 = node1->parent;
5194 node2 = node2->parent;
5205 gtk_text_btree_get_view (GtkTextBTree *tree, gpointer view_id)
5210 while (view != NULL)
5212 if (view->view_id == view_id)
5221 get_tree_bounds (GtkTextBTree *tree,
5225 _gtk_text_btree_get_iter_at_line_char (tree, start, 0, 0);
5226 _gtk_text_btree_get_last_iter (tree, end);
5230 tag_changed_cb (GtkTextTagTable *table,
5232 gboolean size_changed,
5237 /* We need to queue a relayout on all regions that are tagged with
5244 if (_gtk_text_btree_get_iter_at_first_toggle (tree, &start, tag))
5246 /* Must be a last toggle if there was a first one. */
5247 _gtk_text_btree_get_iter_at_last_toggle (tree, &end, tag);
5248 _gtk_text_btree_invalidate_region (tree,
5255 /* We only need to queue a redraw, not a relayout */
5260 while (view != NULL)
5264 _gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5265 gtk_text_layout_changed (view->layout, 0, height, height);
5273 tag_removed_cb (GtkTextTagTable *table,
5277 /* Remove the tag from the tree */
5282 get_tree_bounds (tree, &start, &end);
5284 _gtk_text_btree_tag (&start, &end, tag, FALSE);
5285 gtk_text_btree_remove_tag_info (tree, tag);
5289 /* Rebalance the out-of-whack node "node" */
5291 gtk_text_btree_rebalance (GtkTextBTree *tree,
5292 GtkTextBTreeNode *node)
5295 * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5296 * up through the tree one GtkTextBTreeNode at a time until the root
5297 * GtkTextBTreeNode has been processed.
5300 while (node != NULL)
5302 GtkTextBTreeNode *new_node, *child;
5307 * Check to see if the GtkTextBTreeNode has too many children. If it does,
5308 * then split off all but the first MIN_CHILDREN into a separate
5309 * GtkTextBTreeNode following the original one. Then repeat until the
5310 * GtkTextBTreeNode has a decent size.
5313 if (node->num_children > MAX_CHILDREN)
5318 * If the GtkTextBTreeNode being split is the root
5319 * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5323 if (node->parent == NULL)
5325 new_node = gtk_text_btree_node_new ();
5326 new_node->parent = NULL;
5327 new_node->next = NULL;
5328 new_node->summary = NULL;
5329 new_node->level = node->level + 1;
5330 new_node->children.node = node;
5331 recompute_node_counts (tree, new_node);
5332 tree->root_node = new_node;
5334 new_node = gtk_text_btree_node_new ();
5335 new_node->parent = node->parent;
5336 new_node->next = node->next;
5337 node->next = new_node;
5338 new_node->summary = NULL;
5339 new_node->level = node->level;
5340 new_node->num_children = node->num_children - MIN_CHILDREN;
5341 if (node->level == 0)
5343 for (i = MIN_CHILDREN-1,
5344 line = node->children.line;
5345 i > 0; i--, line = line->next)
5347 /* Empty loop body. */
5349 new_node->children.line = line->next;
5354 for (i = MIN_CHILDREN-1,
5355 child = node->children.node;
5356 i > 0; i--, child = child->next)
5358 /* Empty loop body. */
5360 new_node->children.node = child->next;
5363 recompute_node_counts (tree, node);
5364 node->parent->num_children++;
5366 if (node->num_children <= MAX_CHILDREN)
5368 recompute_node_counts (tree, node);
5374 while (node->num_children < MIN_CHILDREN)
5376 GtkTextBTreeNode *other;
5377 GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5378 GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5379 int total_children, first_children, i;
5382 * Too few children for this GtkTextBTreeNode. If this is the root then,
5383 * it's OK for it to have less than MIN_CHILDREN children
5384 * as long as it's got at least two. If it has only one
5385 * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5386 * the tree and use its child as the new root.
5389 if (node->parent == NULL)
5391 if ((node->num_children == 1) && (node->level > 0))
5393 tree->root_node = node->children.node;
5394 tree->root_node->parent = NULL;
5395 summary_list_destroy (node->summary);
5402 * Not the root. Make sure that there are siblings to
5406 if (node->parent->num_children < 2)
5408 gtk_text_btree_rebalance (tree, node->parent);
5413 * Find a sibling neighbor to borrow from, and arrange for
5414 * node to be the earlier of the pair.
5417 if (node->next == NULL)
5419 for (other = node->parent->children.node;
5420 other->next != node;
5421 other = other->next)
5423 /* Empty loop body. */
5430 * We're going to either merge the two siblings together
5431 * into one GtkTextBTreeNode or redivide the children among them to
5432 * balance their loads. As preparation, join their two
5433 * child lists into a single list and remember the half-way
5434 * point in the list.
5437 total_children = node->num_children + other->num_children;
5438 first_children = total_children/2;
5439 if (node->children.node == NULL)
5441 node->children = other->children;
5442 other->children.node = NULL;
5443 other->children.line = NULL;
5445 if (node->level == 0)
5449 for (line = node->children.line, i = 1;
5451 line = line->next, i++)
5453 if (i == first_children)
5458 line->next = other->children.line;
5459 while (i <= first_children)
5468 GtkTextBTreeNode *child;
5470 for (child = node->children.node, i = 1;
5471 child->next != NULL;
5472 child = child->next, i++)
5474 if (i <= first_children)
5476 if (i == first_children)
5478 halfwaynode = child;
5482 child->next = other->children.node;
5483 while (i <= first_children)
5485 halfwaynode = child;
5486 child = child->next;
5492 * If the two siblings can simply be merged together, do it.
5495 if (total_children <= MAX_CHILDREN)
5497 recompute_node_counts (tree, node);
5498 node->next = other->next;
5499 node->parent->num_children--;
5500 summary_list_destroy (other->summary);
5506 * The siblings can't be merged, so just divide their
5507 * children evenly between them.
5510 if (node->level == 0)
5512 other->children.line = halfwayline->next;
5513 halfwayline->next = NULL;
5517 other->children.node = halfwaynode->next;
5518 halfwaynode->next = NULL;
5521 recompute_node_counts (tree, node);
5522 recompute_node_counts (tree, other);
5525 node = node->parent;
5530 post_insert_fixup (GtkTextBTree *tree,
5532 gint line_count_delta,
5533 gint char_count_delta)
5536 GtkTextBTreeNode *node;
5539 * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5540 * point, then rebalance the tree if necessary.
5543 for (node = line->parent ; node != NULL;
5544 node = node->parent)
5546 node->num_lines += line_count_delta;
5547 node->num_chars += char_count_delta;
5549 node = line->parent;
5550 node->num_children += line_count_delta;
5552 if (node->num_children > MAX_CHILDREN)
5554 gtk_text_btree_rebalance (tree, node);
5557 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5558 _gtk_text_btree_check (tree);
5561 static GtkTextTagInfo*
5562 gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
5565 GtkTextTagInfo *info;
5569 list = tree->tag_infos;
5570 while (list != NULL)
5573 if (info->tag == tag)
5576 list = g_slist_next (list);
5582 static GtkTextTagInfo*
5583 gtk_text_btree_get_tag_info (GtkTextBTree *tree,
5586 GtkTextTagInfo *info;
5588 info = gtk_text_btree_get_existing_tag_info (tree, tag);
5592 /* didn't find it, create. */
5594 info = g_new (GtkTextTagInfo, 1);
5597 g_object_ref (G_OBJECT (tag));
5598 info->tag_root = NULL;
5599 info->toggle_count = 0;
5601 tree->tag_infos = g_slist_prepend (tree->tag_infos, info);
5608 gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
5611 GtkTextTagInfo *info;
5616 list = tree->tag_infos;
5617 while (list != NULL)
5620 if (info->tag == tag)
5624 prev->next = list->next;
5628 tree->tag_infos = list->next;
5631 g_slist_free (list);
5633 g_object_unref (G_OBJECT (info->tag));
5639 list = g_slist_next (list);
5642 g_assert_not_reached ();
5647 recompute_level_zero_counts (GtkTextBTreeNode *node)
5650 GtkTextLineSegment *seg;
5652 g_assert (node->level == 0);
5654 line = node->children.line;
5655 while (line != NULL)
5657 node->num_children++;
5660 if (line->parent != node)
5661 gtk_text_line_set_parent (line, node);
5663 seg = line->segments;
5667 node->num_chars += seg->char_count;
5669 if (((seg->type != >k_text_toggle_on_type)
5670 && (seg->type != >k_text_toggle_off_type))
5671 || !(seg->body.toggle.inNodeCounts))
5677 GtkTextTagInfo *info;
5679 info = seg->body.toggle.info;
5681 gtk_text_btree_node_adjust_toggle_count (node, info, 1);
5692 recompute_level_nonzero_counts (GtkTextBTreeNode *node)
5695 GtkTextBTreeNode *child;
5697 g_assert (node->level > 0);
5699 child = node->children.node;
5700 while (child != NULL)
5702 node->num_children += 1;
5703 node->num_lines += child->num_lines;
5704 node->num_chars += child->num_chars;
5706 if (child->parent != node)
5708 child->parent = node;
5709 gtk_text_btree_node_invalidate_upward (node, NULL);
5712 summary = child->summary;
5713 while (summary != NULL)
5715 gtk_text_btree_node_adjust_toggle_count (node,
5717 summary->toggle_count);
5719 summary = summary->next;
5722 child = child->next;
5727 *----------------------------------------------------------------------
5729 * recompute_node_counts --
5731 * This procedure is called to recompute all the counts in a GtkTextBTreeNode
5732 * (tags, child information, etc.) by scanning the information in
5733 * its descendants. This procedure is called during rebalancing
5734 * when a GtkTextBTreeNode's child structure has changed.
5740 * The tag counts for node are modified to reflect its current
5741 * child structure, as are its num_children, num_lines, num_chars fields.
5742 * Also, all of the childrens' parent fields are made to point
5745 *----------------------------------------------------------------------
5749 recompute_node_counts (GtkTextBTree *tree, GtkTextBTreeNode *node)
5752 Summary *summary, *summary2;
5755 * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
5756 * the existing Summary records (most of them will probably be reused).
5759 summary = node->summary;
5760 while (summary != NULL)
5762 summary->toggle_count = 0;
5763 summary = summary->next;
5766 node->num_children = 0;
5767 node->num_lines = 0;
5768 node->num_chars = 0;
5771 * Scan through the children, adding the childrens' tag counts into
5772 * the GtkTextBTreeNode's tag counts and adding new Summary structures if
5776 if (node->level == 0)
5777 recompute_level_zero_counts (node);
5779 recompute_level_nonzero_counts (node);
5784 gtk_text_btree_node_check_valid (node, view->view_id);
5789 * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
5790 * records that still have a zero count, or that have all the toggles.
5791 * The GtkTextBTreeNode with the children that account for all the tags toggles
5792 * have no summary information, and they become the tag_root for the tag.
5796 for (summary = node->summary; summary != NULL; )
5798 if (summary->toggle_count > 0 &&
5799 summary->toggle_count < summary->info->toggle_count)
5801 if (node->level == summary->info->tag_root->level)
5804 * The tag's root GtkTextBTreeNode split and some toggles left.
5805 * The tag root must move up a level.
5807 summary->info->tag_root = node->parent;
5810 summary = summary->next;
5813 if (summary->toggle_count == summary->info->toggle_count)
5816 * A GtkTextBTreeNode merge has collected all the toggles under
5817 * one GtkTextBTreeNode. Push the root down to this level.
5819 summary->info->tag_root = node;
5821 if (summary2 != NULL)
5823 summary2->next = summary->next;
5824 summary_destroy (summary);
5825 summary = summary2->next;
5829 node->summary = summary->next;
5830 summary_destroy (summary);
5831 summary = node->summary;
5837 _gtk_change_node_toggle_count (GtkTextBTreeNode *node,
5838 GtkTextTagInfo *info,
5839 gint delta) /* may be negative */
5841 Summary *summary, *prevPtr;
5842 GtkTextBTreeNode *node2Ptr;
5843 int rootLevel; /* Level of original tag root */
5845 info->toggle_count += delta;
5847 if (info->tag_root == (GtkTextBTreeNode *) NULL)
5849 info->tag_root = node;
5854 * Note the level of the existing root for the tag so we can detect
5855 * if it needs to be moved because of the toggle count change.
5858 rootLevel = info->tag_root->level;
5861 * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
5862 * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
5866 for ( ; node != info->tag_root; node = node->parent)
5869 * See if there's already an entry for this tag for this GtkTextBTreeNode. If so,
5870 * perhaps all we have to do is adjust its count.
5873 for (prevPtr = NULL, summary = node->summary;
5875 prevPtr = summary, summary = summary->next)
5877 if (summary->info == info)
5882 if (summary != NULL)
5884 summary->toggle_count += delta;
5885 if (summary->toggle_count > 0 &&
5886 summary->toggle_count < info->toggle_count)
5890 if (summary->toggle_count != 0)
5893 * Should never find a GtkTextBTreeNode with max toggle count at this
5894 * point (there shouldn't have been a summary entry in the
5898 g_error ("%s: bad toggle count (%d) max (%d)",
5899 G_STRLOC, summary->toggle_count, info->toggle_count);
5903 * Zero toggle count; must remove this tag from the list.
5906 if (prevPtr == NULL)
5908 node->summary = summary->next;
5912 prevPtr->next = summary->next;
5914 summary_destroy (summary);
5919 * This tag isn't currently in the summary information list.
5922 if (rootLevel == node->level)
5926 * The old tag root is at the same level in the tree as this
5927 * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode. Move the tag root up
5928 * a level, in the hopes that it will now cover this GtkTextBTreeNode
5929 * as well as the old root (if not, we'll move it up again
5930 * the next time through the loop). To push it up one level
5931 * we copy the original toggle count into the summary
5932 * information at the old root and change the root to its
5933 * parent GtkTextBTreeNode.
5936 GtkTextBTreeNode *rootnode = info->tag_root;
5937 summary = (Summary *) g_malloc (sizeof (Summary));
5938 summary->info = info;
5939 summary->toggle_count = info->toggle_count - delta;
5940 summary->next = rootnode->summary;
5941 rootnode->summary = summary;
5942 rootnode = rootnode->parent;
5943 rootLevel = rootnode->level;
5944 info->tag_root = rootnode;
5946 summary = (Summary *) g_malloc (sizeof (Summary));
5947 summary->info = info;
5948 summary->toggle_count = delta;
5949 summary->next = node->summary;
5950 node->summary = summary;
5955 * If we've decremented the toggle count, then it may be necessary
5956 * to push the tag root down one or more levels.
5963 if (info->toggle_count == 0)
5965 info->tag_root = (GtkTextBTreeNode *) NULL;
5968 node = info->tag_root;
5969 while (node->level > 0)
5972 * See if a single child GtkTextBTreeNode accounts for all of the tag's
5973 * toggles. If so, push the root down one level.
5976 for (node2Ptr = node->children.node;
5977 node2Ptr != (GtkTextBTreeNode *)NULL ;
5978 node2Ptr = node2Ptr->next)
5980 for (prevPtr = NULL, summary = node2Ptr->summary;
5982 prevPtr = summary, summary = summary->next)
5984 if (summary->info == info)
5989 if (summary == NULL)
5993 if (summary->toggle_count != info->toggle_count)
5996 * No GtkTextBTreeNode has all toggles, so the root is still valid.
6003 * This GtkTextBTreeNode has all the toggles, so push down the root.
6006 if (prevPtr == NULL)
6008 node2Ptr->summary = summary->next;
6012 prevPtr->next = summary->next;
6014 summary_destroy (summary);
6015 info->tag_root = node2Ptr;
6018 node = info->tag_root;
6023 *----------------------------------------------------------------------
6027 * This is a utility procedure used by _gtk_text_btree_get_tags. It
6028 * increments the count for a particular tag, adding a new
6029 * entry for that tag if there wasn't one previously.
6035 * The information at *tagInfoPtr may be modified, and the arrays
6036 * may be reallocated to make them larger.
6038 *----------------------------------------------------------------------
6042 inc_count (GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
6047 for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
6048 count > 0; tag_p++, count--)
6052 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
6058 * There isn't currently an entry for this tag, so we have to
6059 * make a new one. If the arrays are full, then enlarge the
6063 if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
6065 GtkTextTag **newTags;
6066 int *newCounts, newSize;
6068 newSize = 2*tagInfoPtr->arraySize;
6069 newTags = (GtkTextTag **) g_malloc ((unsigned)
6070 (newSize*sizeof (GtkTextTag *)));
6071 memcpy ((void *) newTags, (void *) tagInfoPtr->tags,
6072 tagInfoPtr->arraySize *sizeof (GtkTextTag *));
6073 g_free ((char *) tagInfoPtr->tags);
6074 tagInfoPtr->tags = newTags;
6075 newCounts = (int *) g_malloc ((unsigned) (newSize*sizeof (int)));
6076 memcpy ((void *) newCounts, (void *) tagInfoPtr->counts,
6077 tagInfoPtr->arraySize *sizeof (int));
6078 g_free ((char *) tagInfoPtr->counts);
6079 tagInfoPtr->counts = newCounts;
6080 tagInfoPtr->arraySize = newSize;
6083 tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
6084 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
6085 tagInfoPtr->numTags++;
6089 gtk_text_btree_link_segment (GtkTextLineSegment *seg,
6090 const GtkTextIter *iter)
6092 GtkTextLineSegment *prev;
6096 line = gtk_text_iter_get_text_line (iter);
6097 tree = gtk_text_iter_get_btree (iter);
6099 prev = gtk_text_line_segment_split (iter);
6102 seg->next = line->segments;
6103 line->segments = seg;
6107 seg->next = prev->next;
6110 cleanup_line (line);
6111 segments_changed (tree);
6113 if (gtk_debug_flags & GTK_DEBUG_TEXT)
6114 _gtk_text_btree_check (tree);
6118 gtk_text_btree_unlink_segment (GtkTextBTree *tree,
6119 GtkTextLineSegment *seg,
6122 GtkTextLineSegment *prev;
6124 if (line->segments == seg)
6126 line->segments = seg->next;
6130 for (prev = line->segments; prev->next != seg;
6133 /* Empty loop body. */
6135 prev->next = seg->next;
6137 cleanup_line (line);
6138 segments_changed (tree);
6142 * This is here because it requires BTree internals, it logically
6143 * belongs in gtktextsegment.c
6148 *--------------------------------------------------------------
6150 * _gtk_toggle_segment_check_func --
6152 * This procedure is invoked to perform consistency checks
6153 * on toggle segments.
6159 * If a consistency problem is found the procedure g_errors.
6161 *--------------------------------------------------------------
6165 _gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6171 if (segPtr->byte_count != 0)
6173 g_error ("toggle_segment_check_func: segment had non-zero size");
6175 if (!segPtr->body.toggle.inNodeCounts)
6177 g_error ("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6179 needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6180 for (summary = line->parent->summary; ;
6181 summary = summary->next)
6183 if (summary == NULL)
6187 g_error ("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6194 if (summary->info == segPtr->body.toggle.info)
6198 g_error ("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6210 gtk_text_btree_node_view_check_consistency (GtkTextBTreeNode *node,
6217 gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6218 &width, &height, &valid);
6219 if (nd->width != width ||
6220 nd->height != height ||
6221 !nd->valid != !valid)
6223 g_error ("Node aggregates for view %p are invalid:\n"
6224 "Are (%d,%d,%s), should be (%d,%d,%s)",
6226 nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6227 width, height, valid ? "TRUE" : "FALSE");
6232 gtk_text_btree_node_check_consistency (GtkTextBTreeNode *node)
6234 GtkTextBTreeNode *childnode;
6235 Summary *summary, *summary2;
6237 GtkTextLineSegment *segPtr;
6238 int num_children, num_lines, num_chars, toggle_count, min_children;
6239 GtkTextLineData *ld;
6242 if (node->parent != NULL)
6244 min_children = MIN_CHILDREN;
6246 else if (node->level > 0)
6253 if ((node->num_children < min_children)
6254 || (node->num_children > MAX_CHILDREN))
6256 g_error ("gtk_text_btree_node_check_consistency: bad child count (%d)",
6257 node->num_children);
6260 nd = node->node_data;
6263 gtk_text_btree_node_view_check_consistency (node, nd);
6270 if (node->level == 0)
6272 for (line = node->children.line; line != NULL;
6275 if (line->parent != node)
6277 g_error ("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6279 if (line->segments == NULL)
6281 g_error ("gtk_text_btree_node_check_consistency: line has no segments");
6287 /* Just ensuring we don't segv while doing this loop */
6292 for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6294 if (segPtr->type->checkFunc != NULL)
6296 (*segPtr->type->checkFunc)(segPtr, line);
6298 if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6299 && (segPtr->next != NULL)
6300 && (segPtr->next->byte_count == 0)
6301 && (segPtr->next->type->leftGravity))
6303 g_error ("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6305 if ((segPtr->next == NULL)
6306 && (segPtr->type != >k_text_char_type))
6308 g_error ("gtk_text_btree_node_check_consistency: line ended with wrong type");
6311 num_chars += segPtr->char_count;
6320 for (childnode = node->children.node; childnode != NULL;
6321 childnode = childnode->next)
6323 if (childnode->parent != node)
6325 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6327 if (childnode->level != (node->level-1))
6329 g_error ("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6330 node->level, childnode->level);
6332 gtk_text_btree_node_check_consistency (childnode);
6333 for (summary = childnode->summary; summary != NULL;
6334 summary = summary->next)
6336 for (summary2 = node->summary; ;
6337 summary2 = summary2->next)
6339 if (summary2 == NULL)
6341 if (summary->info->tag_root == node)
6345 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6346 summary->info->tag->name,
6347 "present in parent summaries");
6349 if (summary->info == summary2->info)
6356 num_lines += childnode->num_lines;
6357 num_chars += childnode->num_chars;
6360 if (num_children != node->num_children)
6362 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6363 num_children, node->num_children);
6365 if (num_lines != node->num_lines)
6367 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6368 num_lines, node->num_lines);
6370 if (num_chars != node->num_chars)
6372 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6373 num_chars, node->num_chars);
6376 for (summary = node->summary; summary != NULL;
6377 summary = summary->next)
6379 if (summary->info->toggle_count == summary->toggle_count)
6381 g_error ("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6382 summary->info->tag->name);
6385 if (node->level == 0)
6387 for (line = node->children.line; line != NULL;
6390 for (segPtr = line->segments; segPtr != NULL;
6391 segPtr = segPtr->next)
6393 if ((segPtr->type != >k_text_toggle_on_type)
6394 && (segPtr->type != >k_text_toggle_off_type))
6398 if (segPtr->body.toggle.info == summary->info)
6400 if (!segPtr->body.toggle.inNodeCounts)
6401 g_error ("Toggle segment not in the node counts");
6410 for (childnode = node->children.node;
6412 childnode = childnode->next)
6414 for (summary2 = childnode->summary;
6416 summary2 = summary2->next)
6418 if (summary2->info == summary->info)
6420 toggle_count += summary2->toggle_count;
6425 if (toggle_count != summary->toggle_count)
6427 g_error ("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6428 toggle_count, summary->toggle_count);
6430 for (summary2 = summary->next; summary2 != NULL;
6431 summary2 = summary2->next)
6433 if (summary2->info == summary->info)
6435 g_error ("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6436 summary->info->tag->name);
6443 listify_foreach (GtkTextTag *tag, gpointer user_data)
6445 GSList** listp = user_data;
6447 *listp = g_slist_prepend (*listp, tag);
6451 list_of_tags (GtkTextTagTable *table)
6453 GSList *list = NULL;
6455 gtk_text_tag_table_foreach (table, listify_foreach, &list);
6461 _gtk_text_btree_check (GtkTextBTree *tree)
6464 GtkTextBTreeNode *node;
6466 GtkTextLineSegment *seg;
6468 GSList *taglist = NULL;
6470 GtkTextTagInfo *info;
6473 * Make sure that the tag toggle counts and the tag root pointers are OK.
6475 for (taglist = list_of_tags (tree->table);
6476 taglist != NULL ; taglist = taglist->next)
6478 tag = taglist->data;
6479 info = gtk_text_btree_get_existing_tag_info (tree, tag);
6482 node = info->tag_root;
6485 if (info->toggle_count != 0)
6487 g_error ("_gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6488 tag->name, info->toggle_count);
6490 continue; /* no ranges for the tag */
6492 else if (info->toggle_count == 0)
6494 g_error ("_gtk_text_btree_check found root for \"%s\" with no toggles",
6497 else if (info->toggle_count & 1)
6499 g_error ("_gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6500 tag->name, info->toggle_count);
6502 for (summary = node->summary; summary != NULL;
6503 summary = summary->next)
6505 if (summary->info->tag == tag)
6507 g_error ("_gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6511 if (node->level > 0)
6513 for (node = node->children.node ; node != NULL ;
6516 for (summary = node->summary; summary != NULL;
6517 summary = summary->next)
6519 if (summary->info->tag == tag)
6521 count += summary->toggle_count;
6528 GtkTextLineSegmentClass * last = NULL;
6530 for (line = node->children.line ; line != NULL ;
6533 for (seg = line->segments; seg != NULL;
6536 if ((seg->type == >k_text_toggle_on_type ||
6537 seg->type == >k_text_toggle_off_type) &&
6538 seg->body.toggle.info->tag == tag)
6540 if (last == seg->type)
6541 g_error ("Two consecutive toggles on or off weren't merged");
6542 if (!seg->body.toggle.inNodeCounts)
6543 g_error ("Toggle segment not in the node counts");
6552 if (count != info->toggle_count)
6554 g_error ("_gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
6555 info->toggle_count, tag->name, count);
6560 g_slist_free (taglist);
6564 * Call a recursive procedure to do the main body of checks.
6567 node = tree->root_node;
6568 gtk_text_btree_node_check_consistency (tree->root_node);
6571 * Make sure that there are at least two lines in the text and
6572 * that the last line has no characters except a newline.
6575 if (node->num_lines < 2)
6577 g_error ("_gtk_text_btree_check: less than 2 lines in tree");
6579 if (node->num_chars < 2)
6581 g_error ("_gtk_text_btree_check: less than 2 chars in tree");
6583 while (node->level > 0)
6585 node = node->children.node;
6586 while (node->next != NULL)
6591 line = node->children.line;
6592 while (line->next != NULL)
6596 seg = line->segments;
6597 while ((seg->type == >k_text_toggle_off_type)
6598 || (seg->type == >k_text_right_mark_type)
6599 || (seg->type == >k_text_left_mark_type))
6602 * It's OK to toggle a tag off in the last line, but
6603 * not to start a new range. It's also OK to have marks
6609 if (seg->type != >k_text_char_type)
6611 g_error ("_gtk_text_btree_check: last line has bogus segment type");
6613 if (seg->next != NULL)
6615 g_error ("_gtk_text_btree_check: last line has too many segments");
6617 if (seg->byte_count != 1)
6619 g_error ("_gtk_text_btree_check: last line has wrong # characters: %d",
6622 if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
6624 g_error ("_gtk_text_btree_check: last line had bad value: %s",
6629 void _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line);
6630 void _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment* seg);
6631 void _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent);
6632 void _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
6635 _gtk_text_btree_spew (GtkTextBTree *tree)
6640 printf ("%d lines in tree %p\n",
6641 _gtk_text_btree_line_count (tree), tree);
6643 line = _gtk_text_btree_get_line (tree, 0, &real_line);
6645 while (line != NULL)
6647 _gtk_text_btree_spew_line (tree, line);
6648 line = _gtk_text_line_next (line);
6651 printf ("=================== Tag information\n");
6656 list = tree->tag_infos;
6658 while (list != NULL)
6660 GtkTextTagInfo *info;
6664 printf (" tag `%s': root at %p, toggle count %d\n",
6665 info->tag->name, info->tag_root, info->toggle_count);
6667 list = g_slist_next (list);
6670 if (tree->tag_infos == NULL)
6672 printf (" (no tags in the tree)\n");
6676 printf ("=================== Tree nodes\n");
6679 _gtk_text_btree_spew_node (tree->root_node, 0);
6684 _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
6687 GtkTextLineSegment *seg;
6689 spaces = g_strnfill (indent, ' ');
6691 printf ("%sline %p chars %d bytes %d\n",
6693 _gtk_text_line_char_count (line),
6694 _gtk_text_line_byte_count (line));
6696 seg = line->segments;
6699 if (seg->type == >k_text_char_type)
6701 gchar* str = g_strndup (seg->body.chars, MIN (seg->byte_count, 10));
6706 if (*s == '\n' || *s == '\r')
6710 printf ("%s chars `%s'...\n", spaces, str);
6713 else if (seg->type == >k_text_right_mark_type)
6715 printf ("%s right mark `%s' visible: %d\n",
6717 seg->body.mark.name,
6718 seg->body.mark.visible);
6720 else if (seg->type == >k_text_left_mark_type)
6722 printf ("%s left mark `%s' visible: %d\n",
6724 seg->body.mark.name,
6725 seg->body.mark.visible);
6727 else if (seg->type == >k_text_toggle_on_type ||
6728 seg->type == >k_text_toggle_off_type)
6730 printf ("%s tag `%s' %s\n",
6731 spaces, seg->body.toggle.info->tag->name,
6732 seg->type == >k_text_toggle_off_type ? "off" : "on");
6742 _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent)
6745 GtkTextBTreeNode *iter;
6748 spaces = g_strnfill (indent, ' ');
6750 printf ("%snode %p level %d children %d lines %d chars %d\n",
6751 spaces, node, node->level,
6752 node->num_children, node->num_lines, node->num_chars);
6757 printf ("%s %d toggles of `%s' below this node\n",
6758 spaces, s->toggle_count, s->info->tag->name);
6764 if (node->level > 0)
6766 iter = node->children.node;
6767 while (iter != NULL)
6769 _gtk_text_btree_spew_node (iter, indent + 2);
6776 GtkTextLine *line = node->children.line;
6777 while (line != NULL)
6779 _gtk_text_btree_spew_line_short (line, indent + 2);
6787 _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line)
6789 GtkTextLineSegment * seg;
6791 printf ("%4d| line: %p parent: %p next: %p\n",
6792 _gtk_text_line_get_number (line), line, line->parent, line->next);
6794 seg = line->segments;
6798 _gtk_text_btree_spew_segment (tree, seg);
6804 _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment * seg)
6806 printf (" segment: %p type: %s bytes: %d chars: %d\n",
6807 seg, seg->type->name, seg->byte_count, seg->char_count);
6809 if (seg->type == >k_text_char_type)
6811 gchar* str = g_strndup (seg->body.chars, seg->byte_count);
6812 printf (" `%s'\n", str);
6815 else if (seg->type == >k_text_right_mark_type)
6817 printf (" right mark `%s' visible: %d not_deleteable: %d\n",
6818 seg->body.mark.name,
6819 seg->body.mark.visible,
6820 seg->body.mark.not_deleteable);
6822 else if (seg->type == >k_text_left_mark_type)
6824 printf (" left mark `%s' visible: %d not_deleteable: %d\n",
6825 seg->body.mark.name,
6826 seg->body.mark.visible,
6827 seg->body.mark.not_deleteable);
6829 else if (seg->type == >k_text_toggle_on_type ||
6830 seg->type == >k_text_toggle_off_type)
6832 printf (" tag `%s' priority %d\n",
6833 seg->body.toggle.info->tag->name,
6834 seg->body.toggle.info->tag->priority);