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),
412 G_CALLBACK (tag_changed_cb),
416 tree->tag_removed_handler = g_signal_connect_data (G_OBJECT (tree->table),
418 G_CALLBACK (tag_removed_cb),
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_order (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);
964 * Chop the text up into lines and create a new segment for
965 * each line, plus a new line for the leftovers from the
971 line_count_delta = 0;
972 char_count_delta = 0;
977 pango_find_paragraph_boundary (text + sol,
982 /* make these relative to the start of the text */
986 g_assert (eol >= sol);
987 g_assert (delim >= sol);
988 g_assert (eol >= delim);
990 g_assert (eol <= len);
992 chunk_len = eol - sol;
994 g_assert (g_utf8_validate (&text[sol], chunk_len, NULL));
995 seg = _gtk_char_segment_new (&text[sol], chunk_len);
997 char_count_delta += seg->char_count;
1001 seg->next = line->segments;
1002 line->segments = seg;
1006 seg->next = cur_seg->next;
1007 cur_seg->next = seg;
1012 /* chunk didn't end with a paragraph separator */
1013 g_assert (eol == len);
1018 * The chunk ended with a newline, so create a new GtkTextLine
1019 * and move the remainder of the old line to it.
1022 newline = gtk_text_line_new ();
1023 gtk_text_line_set_parent (newline, line->parent);
1024 newline->next = line->next;
1025 line->next = newline;
1026 newline->segments = seg->next;
1034 * Cleanup the starting line for the insertion, plus the ending
1035 * line if it's different.
1038 cleanup_line (start_line);
1039 if (line != start_line)
1041 cleanup_line (line);
1044 post_insert_fixup (tree, line, line_count_delta, char_count_delta);
1046 /* Invalidate our region, and reset the iterator the user
1047 passed in to point to the end of the inserted text. */
1053 _gtk_text_btree_get_iter_at_line (tree,
1059 /* We could almost certainly be more efficient here
1060 by saving the information from the insertion loop
1062 gtk_text_iter_forward_chars (&end, char_count_delta);
1064 _gtk_text_btree_invalidate_region (tree,
1068 /* Convenience for the user */
1074 insert_pixbuf_or_widget_segment (GtkTextIter *iter,
1075 GtkTextLineSegment *seg)
1079 GtkTextLineSegment *prevPtr;
1082 gint start_byte_offset;
1084 line = _gtk_text_iter_get_text_line (iter);
1085 tree = _gtk_text_iter_get_btree (iter);
1086 start_byte_offset = gtk_text_iter_get_line_index (iter);
1088 prevPtr = gtk_text_line_segment_split (iter);
1089 if (prevPtr == NULL)
1091 seg->next = line->segments;
1092 line->segments = seg;
1096 seg->next = prevPtr->next;
1097 prevPtr->next = seg;
1100 post_insert_fixup (tree, line, 0, seg->char_count);
1102 chars_changed (tree);
1103 segments_changed (tree);
1105 /* reset *iter for the user, and invalidate tree nodes */
1107 _gtk_text_btree_get_iter_at_line (tree, &start, line, start_byte_offset);
1110 gtk_text_iter_forward_char (iter); /* skip forward past the segment */
1112 _gtk_text_btree_invalidate_region (tree, &start, iter);
1116 _gtk_text_btree_insert_pixbuf (GtkTextIter *iter,
1119 GtkTextLineSegment *seg;
1121 seg = _gtk_pixbuf_segment_new (pixbuf);
1123 insert_pixbuf_or_widget_segment (iter, seg);
1127 _gtk_text_btree_insert_child_anchor (GtkTextIter *iter,
1128 GtkTextChildAnchor *anchor)
1130 GtkTextLineSegment *seg;
1133 if (anchor->segment != NULL)
1135 g_warning (G_STRLOC": Same child anchor can't be inserted twice");
1139 seg = _gtk_widget_segment_new (anchor);
1141 tree = seg->body.child.tree = _gtk_text_iter_get_btree (iter);
1143 insert_pixbuf_or_widget_segment (iter, seg);
1145 if (tree->child_anchor_table == NULL)
1146 tree->child_anchor_table = g_hash_table_new (NULL, NULL);
1148 g_hash_table_insert (tree->child_anchor_table,
1149 seg->body.child.obj,
1150 seg->body.child.obj);
1154 _gtk_text_btree_unregister_child_anchor (GtkTextChildAnchor *anchor)
1156 GtkTextLineSegment *seg;
1158 seg = anchor->segment;
1160 g_hash_table_remove (seg->body.child.tree->child_anchor_table,
1169 find_line_by_y (GtkTextBTree *tree, BTreeView *view,
1170 GtkTextBTreeNode *node, gint y, gint *line_top,
1171 GtkTextLine *last_line)
1175 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1176 _gtk_text_btree_check (tree);
1178 if (node->level == 0)
1182 line = node->children.line;
1184 while (line != NULL && line != last_line)
1186 GtkTextLineData *ld;
1188 ld = _gtk_text_line_get_data (line, view->view_id);
1192 if (y < (current_y + (ld ? ld->height : 0)))
1195 current_y += ld->height;
1196 *line_top += ld->height;
1205 GtkTextBTreeNode *child;
1207 child = node->children.node;
1209 while (child != NULL)
1214 gtk_text_btree_node_get_size (child, view->view_id,
1217 if (y < (current_y + height))
1218 return find_line_by_y (tree, view, child,
1219 y - current_y, line_top,
1222 current_y += height;
1223 *line_top += height;
1225 child = child->next;
1233 _gtk_text_btree_find_line_by_y (GtkTextBTree *tree,
1240 GtkTextLine *last_line;
1243 view = gtk_text_btree_get_view (tree, view_id);
1244 g_return_val_if_fail (view != NULL, NULL);
1246 last_line = get_last_line (tree);
1248 line = find_line_by_y (tree, view, tree->root_node, ypixel, &line_top,
1252 *line_top_out = line_top;
1258 find_line_top_in_line_list (GtkTextBTree *tree,
1261 GtkTextLine *target_line,
1264 while (line != NULL)
1266 GtkTextLineData *ld;
1268 if (line == target_line)
1271 ld = _gtk_text_line_get_data (line, view->view_id);
1278 g_assert_not_reached (); /* If we get here, our
1279 target line didn't exist
1280 under its parent node */
1285 _gtk_text_btree_find_line_top (GtkTextBTree *tree,
1286 GtkTextLine *target_line,
1293 GtkTextBTreeNode *node;
1295 view = gtk_text_btree_get_view (tree, view_id);
1297 g_return_val_if_fail (view != NULL, 0);
1300 node = target_line->parent;
1301 while (node != NULL)
1303 nodes = g_slist_prepend (nodes, node);
1304 node = node->parent;
1308 while (iter != NULL)
1312 if (node->level == 0)
1314 g_slist_free (nodes);
1315 return find_line_top_in_line_list (tree, view,
1316 node->children.line,
1321 GtkTextBTreeNode *child;
1322 GtkTextBTreeNode *target_node;
1324 g_assert (iter->next != NULL); /* not at level 0 */
1325 target_node = iter->next->data;
1327 child = node->children.node;
1329 while (child != NULL)
1334 if (child == target_node)
1338 gtk_text_btree_node_get_size (child, view->view_id,
1342 child = child->next;
1344 g_assert (child != NULL); /* should have broken out before we
1348 iter = g_slist_next (iter);
1351 g_assert_not_reached (); /* we return when we find the target line */
1356 _gtk_text_btree_add_view (GtkTextBTree *tree,
1357 GtkTextLayout *layout)
1360 GtkTextLine *last_line;
1361 GtkTextLineData *line_data;
1363 g_return_if_fail (tree != NULL);
1365 view = g_new (BTreeView, 1);
1367 view->view_id = layout;
1368 view->layout = layout;
1370 view->next = tree->views;
1375 /* The last line in the buffer has identity values for the per-view
1376 * data so that we can avoid special case checks for it in a large
1379 last_line = get_last_line (tree);
1381 line_data = g_new (GtkTextLineData, 1);
1382 line_data->view_id = layout;
1383 line_data->next = NULL;
1384 line_data->width = 0;
1385 line_data->height = 0;
1386 line_data->valid = TRUE;
1388 _gtk_text_line_add_data (last_line, line_data);
1392 _gtk_text_btree_remove_view (GtkTextBTree *tree,
1396 GtkTextLine *last_line;
1397 GtkTextLineData *line_data;
1399 g_return_if_fail (tree != NULL);
1403 while (view != NULL)
1405 if (view->view_id == view_id)
1411 g_return_if_fail (view != NULL);
1414 view->next->prev = view->prev;
1417 view->prev->next = view->next;
1419 if (view == tree->views)
1420 tree->views = view->next;
1422 /* Remove the line data for the last line which we added ourselves.
1423 * (Do this first, so that we don't try to call the view's line data destructor on it.)
1425 last_line = get_last_line (tree);
1426 line_data = _gtk_text_line_remove_data (last_line, view_id);
1429 gtk_text_btree_node_remove_view (view, tree->root_node, view_id);
1435 _gtk_text_btree_invalidate_region (GtkTextBTree *tree,
1436 const GtkTextIter *start,
1437 const GtkTextIter *end)
1443 while (view != NULL)
1445 gtk_text_layout_invalidate (view->layout, start, end);
1452 _gtk_text_btree_get_view_size (GtkTextBTree *tree,
1457 g_return_if_fail (tree != NULL);
1458 g_return_if_fail (view_id != NULL);
1460 gtk_text_btree_node_get_size (tree->root_node, view_id,
1475 iter_stack_new (void)
1478 stack = g_new (IterStack, 1);
1479 stack->iters = NULL;
1486 iter_stack_push (IterStack *stack, const GtkTextIter *iter)
1489 if (stack->count > stack->alloced)
1491 stack->alloced = stack->count*2;
1492 stack->iters = g_realloc (stack->iters,
1493 stack->alloced*sizeof (GtkTextIter));
1495 stack->iters[stack->count-1] = *iter;
1499 iter_stack_pop (IterStack *stack, GtkTextIter *iter)
1501 if (stack->count == 0)
1506 *iter = stack->iters[stack->count];
1512 iter_stack_free (IterStack *stack)
1514 g_free (stack->iters);
1519 iter_stack_invert (IterStack *stack)
1521 if (stack->count > 0)
1524 guint j = stack->count - 1;
1529 tmp = stack->iters[i];
1530 stack->iters[i] = stack->iters[j];
1531 stack->iters[j] = tmp;
1540 queue_tag_redisplay (GtkTextBTree *tree,
1542 const GtkTextIter *start,
1543 const GtkTextIter *end)
1545 if (_gtk_text_tag_affects_size (tag))
1547 _gtk_text_btree_invalidate_region (tree, start, end);
1549 else if (_gtk_text_tag_affects_nonsize_appearance (tag))
1551 /* We only need to queue a redraw, not a relayout */
1552 redisplay_region (tree, start, end);
1555 /* We don't need to do anything if the tag doesn't affect display */
1559 _gtk_text_btree_tag (const GtkTextIter *start_orig,
1560 const GtkTextIter *end_orig,
1564 GtkTextLineSegment *seg, *prev;
1565 GtkTextLine *cleanupline;
1566 gboolean toggled_on;
1567 GtkTextLine *start_line;
1568 GtkTextLine *end_line;
1570 GtkTextIter start, end;
1573 GtkTextTagInfo *info;
1575 g_return_if_fail (start_orig != NULL);
1576 g_return_if_fail (end_orig != NULL);
1577 g_return_if_fail (GTK_IS_TEXT_TAG (tag));
1578 g_return_if_fail (_gtk_text_iter_get_btree (start_orig) ==
1579 _gtk_text_iter_get_btree (end_orig));
1582 printf ("%s tag %s from %d to %d\n",
1583 add ? "Adding" : "Removing",
1585 gtk_text_buffer_get_offset (start_orig),
1586 gtk_text_buffer_get_offset (end_orig));
1589 if (gtk_text_iter_equal (start_orig, end_orig))
1592 start = *start_orig;
1595 gtk_text_iter_order (&start, &end);
1597 tree = _gtk_text_iter_get_btree (&start);
1599 queue_tag_redisplay (tree, tag, &start, &end);
1601 info = gtk_text_btree_get_tag_info (tree, tag);
1603 start_line = _gtk_text_iter_get_text_line (&start);
1604 end_line = _gtk_text_iter_get_text_line (&end);
1606 /* Find all tag toggles in the region; we are going to delete them.
1607 We need to find them in advance, because
1608 forward_find_tag_toggle () won't work once we start playing around
1610 stack = iter_stack_new ();
1613 /* forward_to_tag_toggle() skips a toggle at the start iterator,
1614 * which is deliberate - we don't want to delete a toggle at the
1617 while (gtk_text_iter_forward_to_tag_toggle (&iter, tag))
1619 if (gtk_text_iter_compare (&iter, &end) >= 0)
1622 iter_stack_push (stack, &iter);
1625 /* We need to traverse the toggles in order. */
1626 iter_stack_invert (stack);
1629 * See whether the tag is present at the start of the range. If
1630 * the state doesn't already match what we want then add a toggle
1634 toggled_on = gtk_text_iter_has_tag (&start, tag);
1635 if ( (add && !toggled_on) ||
1636 (!add && toggled_on) )
1638 /* This could create a second toggle at the start position;
1639 cleanup_line () will remove it if so. */
1640 seg = _gtk_toggle_segment_new (info, add);
1642 prev = gtk_text_line_segment_split (&start);
1645 seg->next = start_line->segments;
1646 start_line->segments = seg;
1650 seg->next = prev->next;
1654 /* cleanup_line adds the new toggle to the node counts. */
1656 printf ("added toggle at start\n");
1658 /* we should probably call segments_changed, but in theory
1659 any still-cached segments in the iters we are about to
1660 use are still valid, since they're in front
1666 * Scan the range of characters and delete any internal tag
1667 * transitions. Keep track of what the old state was at the end
1668 * of the range, and add a toggle there if it's needed.
1672 cleanupline = start_line;
1673 while (iter_stack_pop (stack, &iter))
1675 GtkTextLineSegment *indexable_seg;
1678 line = _gtk_text_iter_get_text_line (&iter);
1679 seg = _gtk_text_iter_get_any_segment (&iter);
1680 indexable_seg = _gtk_text_iter_get_indexable_segment (&iter);
1682 g_assert (seg != NULL);
1683 g_assert (indexable_seg != NULL);
1684 g_assert (seg != indexable_seg);
1686 prev = line->segments;
1688 /* Find the segment that actually toggles this tag. */
1689 while (seg != indexable_seg)
1691 g_assert (seg != NULL);
1692 g_assert (indexable_seg != NULL);
1693 g_assert (seg != indexable_seg);
1695 if ( (seg->type == >k_text_toggle_on_type ||
1696 seg->type == >k_text_toggle_off_type) &&
1697 (seg->body.toggle.info == info) )
1703 g_assert (seg != NULL);
1704 g_assert (indexable_seg != NULL);
1706 g_assert (seg != indexable_seg); /* If this happens, then
1707 forward_to_tag_toggle was
1709 g_assert (seg->body.toggle.info->tag == tag);
1711 /* If this happens, when previously tagging we didn't merge
1712 overlapping tags. */
1713 g_assert ( (toggled_on && seg->type == >k_text_toggle_off_type) ||
1714 (!toggled_on && seg->type == >k_text_toggle_on_type) );
1716 toggled_on = !toggled_on;
1719 printf ("deleting %s toggle\n",
1720 seg->type == >k_text_toggle_on_type ? "on" : "off");
1722 /* Remove toggle segment from the list. */
1725 line->segments = seg->next;
1729 while (prev->next != seg)
1733 prev->next = seg->next;
1736 /* Inform iterators we've hosed them. This actually reflects a
1737 bit of inefficiency; if you have the same tag toggled on and
1738 off a lot in a single line, we keep having the rescan from
1739 the front of the line. Of course we have to do that to get
1740 "prev" anyway, but here we are doing it an additional
1742 segments_changed (tree);
1744 /* Update node counts */
1745 if (seg->body.toggle.inNodeCounts)
1747 _gtk_change_node_toggle_count (line->parent,
1749 seg->body.toggle.inNodeCounts = FALSE;
1754 /* We only clean up lines when we're done with them, saves some
1755 gratuitous line-segment-traversals */
1757 if (cleanupline != line)
1759 cleanup_line (cleanupline);
1764 iter_stack_free (stack);
1766 /* toggled_on now reflects the toggle state _just before_ the
1767 end iterator. The end iterator could already have a toggle
1768 on or a toggle off. */
1769 if ( (add && !toggled_on) ||
1770 (!add && toggled_on) )
1772 /* This could create a second toggle at the start position;
1773 cleanup_line () will remove it if so. */
1775 seg = _gtk_toggle_segment_new (info, !add);
1777 prev = gtk_text_line_segment_split (&end);
1780 seg->next = end_line->segments;
1781 end_line->segments = seg;
1785 seg->next = prev->next;
1788 /* cleanup_line adds the new toggle to the node counts. */
1789 g_assert (seg->body.toggle.inNodeCounts == FALSE);
1791 printf ("added toggle at end\n");
1796 * Cleanup cleanupline and the last line of the range, if
1797 * these are different.
1800 cleanup_line (cleanupline);
1801 if (cleanupline != end_line)
1803 cleanup_line (end_line);
1806 segments_changed (tree);
1808 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1809 _gtk_text_btree_check (tree);
1818 _gtk_text_btree_get_line (GtkTextBTree *tree,
1820 gint *real_line_number)
1822 GtkTextBTreeNode *node;
1827 line_count = _gtk_text_btree_line_count (tree);
1829 if (line_number < 0)
1831 line_number = line_count;
1833 else if (line_number > line_count)
1835 line_number = line_count;
1838 if (real_line_number)
1839 *real_line_number = line_number;
1841 node = tree->root_node;
1842 lines_left = line_number;
1845 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1849 while (node->level != 0)
1851 for (node = node->children.node;
1852 node->num_lines <= lines_left;
1858 g_error ("gtk_text_btree_find_line ran out of GtkTextBTreeNodes");
1861 lines_left -= node->num_lines;
1866 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1869 for (line = node->children.line; lines_left > 0;
1875 g_error ("gtk_text_btree_find_line ran out of lines");
1884 _gtk_text_btree_get_line_at_char (GtkTextBTree *tree,
1886 gint *line_start_index,
1887 gint *real_char_index)
1889 GtkTextBTreeNode *node;
1891 GtkTextLineSegment *seg;
1896 node = tree->root_node;
1898 /* Clamp to valid indexes (-1 is magic for "highest index") */
1899 if (char_index < 0 || char_index >= node->num_chars)
1901 char_index = node->num_chars - 1;
1904 *real_char_index = char_index;
1907 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1911 chars_left = char_index;
1912 while (node->level != 0)
1914 for (node = node->children.node;
1915 chars_left >= node->num_chars;
1918 chars_left -= node->num_chars;
1920 g_assert (chars_left >= 0);
1924 if (chars_left == 0)
1926 /* Start of a line */
1928 *line_start_index = char_index;
1929 return node->children.line;
1933 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1939 for (line = node->children.line; line != NULL; line = line->next)
1941 seg = line->segments;
1944 if (chars_in_line + seg->char_count > chars_left)
1945 goto found; /* found our line/segment */
1947 chars_in_line += seg->char_count;
1952 chars_left -= chars_in_line;
1960 g_assert (line != NULL); /* hosage, ran out of lines */
1961 g_assert (seg != NULL);
1963 *line_start_index = char_index - chars_left;
1968 _gtk_text_btree_get_tags (const GtkTextIter *iter,
1971 GtkTextBTreeNode *node;
1972 GtkTextLine *siblingline;
1973 GtkTextLineSegment *seg;
1974 int src, dst, index;
1980 #define NUM_TAG_INFOS 10
1982 line = _gtk_text_iter_get_text_line (iter);
1983 tree = _gtk_text_iter_get_btree (iter);
1984 byte_index = gtk_text_iter_get_line_index (iter);
1986 tagInfo.numTags = 0;
1987 tagInfo.arraySize = NUM_TAG_INFOS;
1988 tagInfo.tags = g_new (GtkTextTag*, NUM_TAG_INFOS);
1989 tagInfo.counts = g_new (int, NUM_TAG_INFOS);
1992 * Record tag toggles within the line of indexPtr but preceding
1993 * indexPtr. Note that if this loop segfaults, your
1994 * byte_index probably points past the sum of all
1995 * seg->byte_count */
1997 for (index = 0, seg = line->segments;
1998 (index + seg->byte_count) <= byte_index;
1999 index += seg->byte_count, seg = seg->next)
2001 if ((seg->type == >k_text_toggle_on_type)
2002 || (seg->type == >k_text_toggle_off_type))
2004 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2009 * Record toggles for tags in lines that are predecessors of
2010 * line but under the same level-0 GtkTextBTreeNode.
2013 for (siblingline = line->parent->children.line;
2014 siblingline != line;
2015 siblingline = siblingline->next)
2017 for (seg = siblingline->segments; seg != NULL;
2020 if ((seg->type == >k_text_toggle_on_type)
2021 || (seg->type == >k_text_toggle_off_type))
2023 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2029 * For each GtkTextBTreeNode in the ancestry of this line, record tag
2030 * toggles for all siblings that precede that GtkTextBTreeNode.
2033 for (node = line->parent; node->parent != NULL;
2034 node = node->parent)
2036 GtkTextBTreeNode *siblingPtr;
2039 for (siblingPtr = node->parent->children.node;
2040 siblingPtr != node; siblingPtr = siblingPtr->next)
2042 for (summary = siblingPtr->summary; summary != NULL;
2043 summary = summary->next)
2045 if (summary->toggle_count & 1)
2047 inc_count (summary->info->tag, summary->toggle_count,
2055 * Go through the tag information and squash out all of the tags
2056 * that have even toggle counts (these tags exist before the point
2057 * of interest, but not at the desired character itself).
2060 for (src = 0, dst = 0; src < tagInfo.numTags; src++)
2062 if (tagInfo.counts[src] & 1)
2064 g_assert (GTK_IS_TEXT_TAG (tagInfo.tags[src]));
2065 tagInfo.tags[dst] = tagInfo.tags[src];
2071 g_free (tagInfo.counts);
2074 g_free (tagInfo.tags);
2077 return tagInfo.tags;
2081 copy_segment (GString *string,
2082 gboolean include_hidden,
2083 gboolean include_nonchars,
2084 const GtkTextIter *start,
2085 const GtkTextIter *end)
2087 GtkTextLineSegment *end_seg;
2088 GtkTextLineSegment *seg;
2090 if (gtk_text_iter_equal (start, end))
2093 seg = _gtk_text_iter_get_indexable_segment (start);
2094 end_seg = _gtk_text_iter_get_indexable_segment (end);
2096 if (seg->type == >k_text_char_type)
2098 gboolean copy = TRUE;
2099 gint copy_bytes = 0;
2100 gint copy_start = 0;
2102 /* Don't copy if we're invisible; segments are invisible/not
2103 as a whole, no need to check each char */
2104 if (!include_hidden &&
2105 _gtk_text_btree_char_is_invisible (start))
2108 /* printf (" <invisible>\n"); */
2111 copy_start = _gtk_text_iter_get_segment_byte (start);
2115 /* End is in the same segment; need to copy fewer bytes. */
2116 gint end_byte = _gtk_text_iter_get_segment_byte (end);
2118 copy_bytes = end_byte - copy_start;
2121 copy_bytes = seg->byte_count - copy_start;
2123 g_assert (copy_bytes != 0); /* Due to iter equality check at
2124 front of this function. */
2128 g_assert ((copy_start + copy_bytes) <= seg->byte_count);
2130 g_string_append_len (string,
2131 seg->body.chars + copy_start,
2135 /* printf (" :%s\n", string->str); */
2137 else if (seg->type == >k_text_pixbuf_type ||
2138 seg->type == >k_text_child_type)
2140 gboolean copy = TRUE;
2142 if (!include_nonchars)
2146 else if (!include_hidden &&
2147 _gtk_text_btree_char_is_invisible (start))
2154 g_string_append_len (string,
2155 gtk_text_unknown_char_utf8,
2163 _gtk_text_btree_get_text (const GtkTextIter *start_orig,
2164 const GtkTextIter *end_orig,
2165 gboolean include_hidden,
2166 gboolean include_nonchars)
2168 GtkTextLineSegment *seg;
2169 GtkTextLineSegment *end_seg;
2177 g_return_val_if_fail (start_orig != NULL, NULL);
2178 g_return_val_if_fail (end_orig != NULL, NULL);
2179 g_return_val_if_fail (_gtk_text_iter_get_btree (start_orig) ==
2180 _gtk_text_iter_get_btree (end_orig), NULL);
2182 start = *start_orig;
2185 gtk_text_iter_order (&start, &end);
2187 retval = g_string_new ("");
2189 tree = _gtk_text_iter_get_btree (&start);
2191 end_seg = _gtk_text_iter_get_indexable_segment (&end);
2193 seg = _gtk_text_iter_get_indexable_segment (&iter);
2194 while (seg != end_seg)
2196 copy_segment (retval, include_hidden, include_nonchars,
2199 _gtk_text_iter_forward_indexable_segment (&iter);
2201 seg = _gtk_text_iter_get_indexable_segment (&iter);
2204 copy_segment (retval, include_hidden, include_nonchars, &iter, &end);
2207 g_string_free (retval, FALSE);
2212 _gtk_text_btree_line_count (GtkTextBTree *tree)
2214 /* Subtract bogus line at the end; we return a count
2216 return tree->root_node->num_lines - 1;
2220 _gtk_text_btree_char_count (GtkTextBTree *tree)
2222 /* Exclude newline in bogus last line */
2223 return tree->root_node->num_chars - 1;
2226 #define LOTSA_TAGS 1000
2228 _gtk_text_btree_char_is_invisible (const GtkTextIter *iter)
2230 gboolean invisible = FALSE; /* if nobody says otherwise, it's visible */
2232 int deftagCnts[LOTSA_TAGS];
2233 int *tagCnts = deftagCnts;
2234 GtkTextTag *deftags[LOTSA_TAGS];
2235 GtkTextTag **tags = deftags;
2237 GtkTextBTreeNode *node;
2238 GtkTextLine *siblingline;
2239 GtkTextLineSegment *seg;
2246 line = _gtk_text_iter_get_text_line (iter);
2247 tree = _gtk_text_iter_get_btree (iter);
2248 byte_index = gtk_text_iter_get_line_index (iter);
2250 numTags = gtk_text_tag_table_size (tree->table);
2252 /* almost always avoid malloc, so stay out of system calls */
2253 if (LOTSA_TAGS < numTags)
2255 tagCnts = g_new (int, numTags);
2256 tags = g_new (GtkTextTag*, numTags);
2259 for (i=0; i<numTags; i++)
2265 * Record tag toggles within the line of indexPtr but preceding
2269 for (index = 0, seg = line->segments;
2270 (index + seg->byte_count) <= byte_index; /* segfault here means invalid index */
2271 index += seg->byte_count, seg = seg->next)
2273 if ((seg->type == >k_text_toggle_on_type)
2274 || (seg->type == >k_text_toggle_off_type))
2276 tag = seg->body.toggle.info->tag;
2277 if (tag->invisible_set && tag->values->invisible)
2279 tags[tag->priority] = tag;
2280 tagCnts[tag->priority]++;
2286 * Record toggles for tags in lines that are predecessors of
2287 * line but under the same level-0 GtkTextBTreeNode.
2290 for (siblingline = line->parent->children.line;
2291 siblingline != line;
2292 siblingline = siblingline->next)
2294 for (seg = siblingline->segments; seg != NULL;
2297 if ((seg->type == >k_text_toggle_on_type)
2298 || (seg->type == >k_text_toggle_off_type))
2300 tag = seg->body.toggle.info->tag;
2301 if (tag->invisible_set && tag->values->invisible)
2303 tags[tag->priority] = tag;
2304 tagCnts[tag->priority]++;
2311 * For each GtkTextBTreeNode in the ancestry of this line, record tag toggles
2312 * for all siblings that precede that GtkTextBTreeNode.
2315 for (node = line->parent; node->parent != NULL;
2316 node = node->parent)
2318 GtkTextBTreeNode *siblingPtr;
2321 for (siblingPtr = node->parent->children.node;
2322 siblingPtr != node; siblingPtr = siblingPtr->next)
2324 for (summary = siblingPtr->summary; summary != NULL;
2325 summary = summary->next)
2327 if (summary->toggle_count & 1)
2329 tag = summary->info->tag;
2330 if (tag->invisible_set && tag->values->invisible)
2332 tags[tag->priority] = tag;
2333 tagCnts[tag->priority] += summary->toggle_count;
2341 * Now traverse from highest priority to lowest,
2342 * take invisible value from first odd count (= on)
2345 for (i = numTags-1; i >=0; i--)
2349 /* FIXME not sure this should be if 0 */
2351 #ifndef ALWAYS_SHOW_SELECTION
2352 /* who would make the selection invisible? */
2353 if ((tag == tkxt->seltag)
2354 && !(tkxt->flags & GOT_FOCUS))
2360 invisible = tags[i]->values->invisible;
2365 if (LOTSA_TAGS < numTags)
2380 redisplay_region (GtkTextBTree *tree,
2381 const GtkTextIter *start,
2382 const GtkTextIter *end)
2385 GtkTextLine *start_line, *end_line;
2387 if (gtk_text_iter_compare (start, end) > 0)
2389 const GtkTextIter *tmp = start;
2394 start_line = _gtk_text_iter_get_text_line (start);
2395 end_line = _gtk_text_iter_get_text_line (end);
2398 while (view != NULL)
2400 gint start_y, end_y;
2401 GtkTextLineData *ld;
2403 start_y = _gtk_text_btree_find_line_top (tree, start_line, view->view_id);
2405 if (end_line == start_line)
2408 end_y = _gtk_text_btree_find_line_top (tree, end_line, view->view_id);
2410 ld = _gtk_text_line_get_data (end_line, view->view_id);
2412 end_y += ld->height;
2414 gtk_text_layout_changed (view->layout, start_y,
2423 redisplay_mark (GtkTextLineSegment *mark)
2428 _gtk_text_btree_get_iter_at_mark (mark->body.mark.tree,
2430 mark->body.mark.obj);
2433 gtk_text_iter_forward_char (&end);
2435 _gtk_text_btree_invalidate_region (mark->body.mark.tree,
2440 redisplay_mark_if_visible (GtkTextLineSegment *mark)
2442 if (!mark->body.mark.visible)
2445 redisplay_mark (mark);
2449 ensure_not_off_end (GtkTextBTree *tree,
2450 GtkTextLineSegment *mark,
2453 if (gtk_text_iter_get_line (iter) ==
2454 _gtk_text_btree_line_count (tree))
2455 gtk_text_iter_backward_char (iter);
2458 static GtkTextLineSegment*
2459 real_set_mark (GtkTextBTree *tree,
2460 GtkTextMark *existing_mark,
2462 gboolean left_gravity,
2463 const GtkTextIter *where,
2464 gboolean should_exist,
2465 gboolean redraw_selections)
2467 GtkTextLineSegment *mark;
2470 g_return_val_if_fail (tree != NULL, NULL);
2471 g_return_val_if_fail (where != NULL, NULL);
2472 g_return_val_if_fail (_gtk_text_iter_get_btree (where) == tree, NULL);
2475 mark = existing_mark->segment;
2476 else if (name != NULL)
2477 mark = g_hash_table_lookup (tree->mark_table,
2482 if (should_exist && mark == NULL)
2484 g_warning ("No mark `%s' exists!", name);
2488 /* OK if !should_exist and it does already exist, in that case
2494 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2495 _gtk_text_iter_check (&iter);
2499 if (redraw_selections &&
2500 (mark == tree->insert_mark->segment ||
2501 mark == tree->selection_bound_mark->segment))
2503 GtkTextIter old_pos;
2505 _gtk_text_btree_get_iter_at_mark (tree, &old_pos,
2506 mark->body.mark.obj);
2507 redisplay_region (tree, &old_pos, where);
2511 * don't let visible marks be after the final newline of the
2515 if (mark->body.mark.visible)
2517 ensure_not_off_end (tree, mark, &iter);
2520 /* Redraw the mark's old location. */
2521 redisplay_mark_if_visible (mark);
2523 /* Unlink mark from its current location.
2524 This could hose our iterator... */
2525 gtk_text_btree_unlink_segment (tree, mark,
2526 mark->body.mark.line);
2527 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2528 g_assert (mark->body.mark.line == _gtk_text_iter_get_text_line (&iter));
2530 segments_changed (tree); /* make sure the iterator recomputes its
2535 mark = _gtk_mark_segment_new (tree,
2539 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2541 if (mark->body.mark.name)
2542 g_hash_table_insert (tree->mark_table,
2543 mark->body.mark.name,
2547 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2548 _gtk_text_iter_check (&iter);
2550 /* Link mark into new location */
2551 gtk_text_btree_link_segment (mark, &iter);
2553 /* Invalidate some iterators. */
2554 segments_changed (tree);
2557 * update the screen at the mark's new location.
2560 redisplay_mark_if_visible (mark);
2562 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2563 _gtk_text_iter_check (&iter);
2565 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2566 _gtk_text_btree_check (tree);
2573 _gtk_text_btree_set_mark (GtkTextBTree *tree,
2574 GtkTextMark *existing_mark,
2576 gboolean left_gravity,
2577 const GtkTextIter *iter,
2578 gboolean should_exist)
2580 GtkTextLineSegment *seg;
2582 seg = real_set_mark (tree, existing_mark,
2583 name, left_gravity, iter, should_exist,
2586 return seg ? seg->body.mark.obj : NULL;
2590 _gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2594 GtkTextIter tmp_start, tmp_end;
2596 _gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2598 _gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2599 tree->selection_bound_mark);
2601 if (gtk_text_iter_equal (&tmp_start, &tmp_end))
2613 gtk_text_iter_order (&tmp_start, &tmp_end);
2626 _gtk_text_btree_place_cursor (GtkTextBTree *tree,
2627 const GtkTextIter *iter)
2629 GtkTextIter start, end;
2631 if (_gtk_text_btree_get_selection_bounds (tree, &start, &end))
2632 redisplay_region (tree, &start, &end);
2634 /* Move insert AND selection_bound before we redisplay */
2635 real_set_mark (tree, tree->insert_mark,
2636 "insert", FALSE, iter, TRUE, FALSE);
2637 real_set_mark (tree, tree->selection_bound_mark,
2638 "selection_bound", FALSE, iter, TRUE, FALSE);
2642 _gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2647 g_return_if_fail (tree != NULL);
2648 g_return_if_fail (name != NULL);
2650 mark = g_hash_table_lookup (tree->mark_table,
2653 _gtk_text_btree_remove_mark (tree, mark);
2657 _gtk_text_btree_remove_mark (GtkTextBTree *tree,
2660 GtkTextLineSegment *segment;
2662 g_return_if_fail (mark != NULL);
2663 g_return_if_fail (tree != NULL);
2665 segment = mark->segment;
2667 if (segment->body.mark.not_deleteable)
2669 g_warning ("Can't delete special mark `%s'", segment->body.mark.name);
2673 /* This calls cleanup_line and segments_changed */
2674 gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2676 if (segment->body.mark.name)
2677 g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2679 /* Remove the ref on the mark that belonged to the segment. */
2680 g_object_unref (G_OBJECT (mark));
2682 segment->body.mark.tree = NULL;
2683 segment->body.mark.line = NULL;
2687 _gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2688 GtkTextMark *segment)
2690 return segment == tree->insert_mark;
2694 _gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2695 GtkTextMark *segment)
2697 return segment == tree->selection_bound_mark;
2701 _gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2704 GtkTextLineSegment *seg;
2706 g_return_val_if_fail (tree != NULL, NULL);
2707 g_return_val_if_fail (name != NULL, NULL);
2709 seg = g_hash_table_lookup (tree->mark_table, name);
2711 return seg ? seg->body.mark.obj : NULL;
2715 * gtk_text_mark_set_visible:
2716 * @mark: a #GtkTextMark
2717 * @setting: visibility of mark
2719 * Sets the visibility of @mark; the insertion point is normally
2720 * visible, i.e. you can see it as a vertical bar. Also, the text
2721 * widget uses a visible mark to indicate where a drop will occur when
2722 * dragging-and-dropping text. Most other marks are not visible.
2723 * Marks are not visible by default.
2727 gtk_text_mark_set_visible (GtkTextMark *mark,
2730 GtkTextLineSegment *seg;
2732 g_return_if_fail (mark != NULL);
2734 seg = mark->segment;
2736 if (seg->body.mark.visible == setting)
2740 seg->body.mark.visible = setting;
2742 redisplay_mark (seg);
2747 _gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
2750 GtkTextBTreeNode *node;
2751 GtkTextTagInfo *info;
2753 g_return_val_if_fail (tree != NULL, NULL);
2757 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2762 if (info->tag_root == NULL)
2765 node = info->tag_root;
2767 /* We know the tag root has instances of the given
2770 continue_outer_loop:
2771 g_assert (node != NULL);
2772 while (node->level > 0)
2774 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2775 node = node->children.node;
2776 while (node != NULL)
2778 if (gtk_text_btree_node_has_tag (node, tag))
2779 goto continue_outer_loop;
2783 g_assert (node != NULL);
2786 g_assert (node != NULL); /* The tag summaries said some node had
2789 g_assert (node->level == 0);
2791 return node->children.line;
2795 /* Looking for any tag at all (tag == NULL).
2796 Unfortunately this can't be done in a simple and efficient way
2797 right now; so I'm just going to return the
2798 first line in the btree. FIXME */
2799 return _gtk_text_btree_get_line (tree, 0, NULL);
2804 _gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
2807 GtkTextBTreeNode *node;
2808 GtkTextBTreeNode *last_node;
2810 GtkTextTagInfo *info;
2812 g_return_val_if_fail (tree != NULL, NULL);
2816 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2818 if (info->tag_root == NULL)
2821 node = info->tag_root;
2822 /* We know the tag root has instances of the given
2825 while (node->level > 0)
2827 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2829 node = node->children.node;
2830 while (node != NULL)
2832 if (gtk_text_btree_node_has_tag (node, tag))
2840 g_assert (node != NULL); /* The tag summaries said some node had
2843 g_assert (node->level == 0);
2845 /* Find the last line in this node */
2846 line = node->children.line;
2847 while (line->next != NULL)
2854 /* This search can't be done efficiently at the moment,
2855 at least not without complexity.
2856 So, we just return the last line.
2858 return _gtk_text_btree_get_line (tree, -1, NULL);
2868 _gtk_text_line_get_number (GtkTextLine *line)
2871 GtkTextBTreeNode *node, *parent, *node2;
2875 * First count how many lines precede this one in its level-0
2879 node = line->parent;
2881 for (line2 = node->children.line; line2 != line;
2882 line2 = line2->next)
2886 g_error ("gtk_text_btree_line_number couldn't find line");
2892 * Now work up through the levels of the tree one at a time,
2893 * counting how many lines are in GtkTextBTreeNodes preceding the current
2897 for (parent = node->parent ; parent != NULL;
2898 node = parent, parent = parent->parent)
2900 for (node2 = parent->children.node; node2 != node;
2901 node2 = node2->next)
2905 g_error ("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
2907 index += node2->num_lines;
2913 static GtkTextLineSegment*
2914 find_toggle_segment_before_char (GtkTextLine *line,
2918 GtkTextLineSegment *seg;
2919 GtkTextLineSegment *toggle_seg;
2924 seg = line->segments;
2925 while ( (index + seg->char_count) <= char_in_line )
2927 if (((seg->type == >k_text_toggle_on_type)
2928 || (seg->type == >k_text_toggle_off_type))
2929 && (seg->body.toggle.info->tag == tag))
2932 index += seg->char_count;
2939 static GtkTextLineSegment*
2940 find_toggle_segment_before_byte (GtkTextLine *line,
2944 GtkTextLineSegment *seg;
2945 GtkTextLineSegment *toggle_seg;
2950 seg = line->segments;
2951 while ( (index + seg->byte_count) <= byte_in_line )
2953 if (((seg->type == >k_text_toggle_on_type)
2954 || (seg->type == >k_text_toggle_off_type))
2955 && (seg->body.toggle.info->tag == tag))
2958 index += seg->byte_count;
2966 find_toggle_outside_current_line (GtkTextLine *line,
2970 GtkTextBTreeNode *node;
2971 GtkTextLine *sibling_line;
2972 GtkTextLineSegment *seg;
2973 GtkTextLineSegment *toggle_seg;
2975 GtkTextTagInfo *info = NULL;
2978 * No toggle in this line. Look for toggles for the tag in lines
2979 * that are predecessors of line but under the same
2980 * level-0 GtkTextBTreeNode.
2983 sibling_line = line->parent->children.line;
2984 while (sibling_line != line)
2986 seg = sibling_line->segments;
2989 if (((seg->type == >k_text_toggle_on_type)
2990 || (seg->type == >k_text_toggle_off_type))
2991 && (seg->body.toggle.info->tag == tag))
2997 sibling_line = sibling_line->next;
3000 if (toggle_seg != NULL)
3001 return (toggle_seg->type == >k_text_toggle_on_type);
3004 * No toggle in this GtkTextBTreeNode. Scan upwards through the ancestors of
3005 * this GtkTextBTreeNode, counting the number of toggles of the given tag in
3006 * siblings that precede that GtkTextBTreeNode.
3009 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3015 node = line->parent;
3016 while (node->parent != NULL)
3018 GtkTextBTreeNode *sibling_node;
3020 sibling_node = node->parent->children.node;
3021 while (sibling_node != node)
3025 summary = sibling_node->summary;
3026 while (summary != NULL)
3028 if (summary->info == info)
3029 toggles += summary->toggle_count;
3031 summary = summary->next;
3034 sibling_node = sibling_node->next;
3037 if (node == info->tag_root)
3040 node = node->parent;
3044 * An odd number of toggles means that the tag is present at the
3048 return (toggles & 1) != 0;
3051 /* FIXME this function is far too slow, for no good reason. */
3053 _gtk_text_line_char_has_tag (GtkTextLine *line,
3058 GtkTextLineSegment *toggle_seg;
3060 g_return_val_if_fail (line != NULL, FALSE);
3063 * Check for toggles for the tag in the line but before
3064 * the char. If there is one, its type indicates whether or
3065 * not the character is tagged.
3068 toggle_seg = find_toggle_segment_before_char (line, char_in_line, tag);
3070 if (toggle_seg != NULL)
3071 return (toggle_seg->type == >k_text_toggle_on_type);
3073 return find_toggle_outside_current_line (line, tree, tag);
3077 _gtk_text_line_byte_has_tag (GtkTextLine *line,
3082 GtkTextLineSegment *toggle_seg;
3084 g_return_val_if_fail (line != NULL, FALSE);
3087 * Check for toggles for the tag in the line but before
3088 * the char. If there is one, its type indicates whether or
3089 * not the character is tagged.
3092 toggle_seg = find_toggle_segment_before_byte (line, byte_in_line, tag);
3094 if (toggle_seg != NULL)
3095 return (toggle_seg->type == >k_text_toggle_on_type);
3097 return find_toggle_outside_current_line (line, tree, tag);
3101 _gtk_text_line_is_last (GtkTextLine *line,
3104 return line == get_last_line (tree);
3108 _gtk_text_line_next (GtkTextLine *line)
3110 GtkTextBTreeNode *node;
3112 if (line->next != NULL)
3117 * This was the last line associated with the particular parent
3118 * GtkTextBTreeNode. Search up the tree for the next GtkTextBTreeNode,
3119 * then search down from that GtkTextBTreeNode to find the first
3123 node = line->parent;
3124 while (node != NULL && node->next == NULL)
3125 node = node->parent;
3131 while (node->level > 0)
3133 node = node->children.node;
3136 g_assert (node->children.line != line);
3138 return node->children.line;
3143 _gtk_text_line_previous (GtkTextLine *line)
3145 GtkTextBTreeNode *node;
3146 GtkTextBTreeNode *node2;
3150 * Find the line under this GtkTextBTreeNode just before the starting line.
3152 prev = line->parent->children.line; /* First line at leaf */
3153 while (prev != line)
3155 if (prev->next == line)
3161 g_error ("gtk_text_btree_previous_line ran out of lines");
3165 * This was the first line associated with the particular parent
3166 * GtkTextBTreeNode. Search up the tree for the previous GtkTextBTreeNode,
3167 * then search down from that GtkTextBTreeNode to find its last line.
3169 for (node = line->parent; ; node = node->parent)
3171 if (node == NULL || node->parent == NULL)
3173 else if (node != node->parent->children.node)
3177 for (node2 = node->parent->children.node; ;
3178 node2 = node2->children.node)
3180 while (node2->next != node)
3181 node2 = node2->next;
3183 if (node2->level == 0)
3189 for (prev = node2->children.line ; ; prev = prev->next)
3191 if (prev->next == NULL)
3195 g_assert_not_reached ();
3200 _gtk_text_line_add_data (GtkTextLine *line,
3201 GtkTextLineData *data)
3203 g_return_if_fail (line != NULL);
3204 g_return_if_fail (data != NULL);
3205 g_return_if_fail (data->view_id != NULL);
3209 data->next = line->views;
3219 _gtk_text_line_remove_data (GtkTextLine *line,
3222 GtkTextLineData *prev;
3223 GtkTextLineData *iter;
3225 g_return_val_if_fail (line != NULL, NULL);
3226 g_return_val_if_fail (view_id != NULL, NULL);
3230 while (iter != NULL)
3232 if (iter->view_id == view_id)
3241 prev->next = iter->next;
3243 line->views = iter->next;
3252 _gtk_text_line_get_data (GtkTextLine *line,
3255 GtkTextLineData *iter;
3257 g_return_val_if_fail (line != NULL, NULL);
3258 g_return_val_if_fail (view_id != NULL, NULL);
3261 while (iter != NULL)
3263 if (iter->view_id == view_id)
3272 _gtk_text_line_invalidate_wrap (GtkTextLine *line,
3273 GtkTextLineData *ld)
3275 /* For now this is totally unoptimized. FIXME?
3277 We could probably optimize the case where the width removed
3278 is less than the max width for the parent node,
3279 and the case where the height is unchanged when we re-wrap.
3282 g_return_if_fail (ld != NULL);
3285 gtk_text_btree_node_invalidate_upward (line->parent, ld->view_id);
3289 _gtk_text_line_char_count (GtkTextLine *line)
3291 GtkTextLineSegment *seg;
3295 seg = line->segments;
3298 size += seg->char_count;
3305 _gtk_text_line_byte_count (GtkTextLine *line)
3307 GtkTextLineSegment *seg;
3311 seg = line->segments;
3314 size += seg->byte_count;
3322 _gtk_text_line_char_index (GtkTextLine *target_line)
3324 GSList *node_stack = NULL;
3325 GtkTextBTreeNode *iter;
3329 /* Push all our parent nodes onto a stack */
3330 iter = target_line->parent;
3332 g_assert (iter != NULL);
3334 while (iter != NULL)
3336 node_stack = g_slist_prepend (node_stack, iter);
3338 iter = iter->parent;
3341 /* Check that we have the root node on top of the stack. */
3342 g_assert (node_stack != NULL &&
3343 node_stack->data != NULL &&
3344 ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3346 /* Add up chars in all nodes before the nodes in our stack.
3350 iter = node_stack->data;
3351 while (iter != NULL)
3353 GtkTextBTreeNode *child_iter;
3354 GtkTextBTreeNode *next_node;
3356 next_node = node_stack->next ?
3357 node_stack->next->data : NULL;
3358 node_stack = g_slist_remove (node_stack, node_stack->data);
3360 if (iter->level == 0)
3362 /* stack should be empty when we're on the last node */
3363 g_assert (node_stack == NULL);
3364 break; /* Our children are now lines */
3367 g_assert (next_node != NULL);
3368 g_assert (iter != NULL);
3369 g_assert (next_node->parent == iter);
3371 /* Add up chars before us in the tree */
3372 child_iter = iter->children.node;
3373 while (child_iter != next_node)
3375 g_assert (child_iter != NULL);
3377 num_chars += child_iter->num_chars;
3379 child_iter = child_iter->next;
3385 g_assert (iter != NULL);
3386 g_assert (iter == target_line->parent);
3388 /* Since we don't store char counts in lines, only in segments, we
3389 have to iterate over the lines adding up segment char counts
3390 until we find our line. */
3391 line = iter->children.line;
3392 while (line != target_line)
3394 g_assert (line != NULL);
3396 num_chars += _gtk_text_line_char_count (line);
3401 g_assert (line == target_line);
3407 _gtk_text_line_byte_to_segment (GtkTextLine *line,
3411 GtkTextLineSegment *seg;
3414 g_return_val_if_fail (line != NULL, NULL);
3416 offset = byte_offset;
3417 seg = line->segments;
3419 while (offset >= seg->byte_count)
3421 g_assert (seg != NULL); /* means an invalid byte index */
3422 offset -= seg->byte_count;
3427 *seg_offset = offset;
3433 _gtk_text_line_char_to_segment (GtkTextLine *line,
3437 GtkTextLineSegment *seg;
3440 g_return_val_if_fail (line != NULL, NULL);
3442 offset = char_offset;
3443 seg = line->segments;
3445 while (offset >= seg->char_count)
3447 g_assert (seg != NULL); /* means an invalid char index */
3448 offset -= seg->char_count;
3453 *seg_offset = offset;
3459 _gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3463 GtkTextLineSegment *seg;
3466 g_return_val_if_fail (line != NULL, NULL);
3468 offset = byte_offset;
3469 seg = line->segments;
3471 while (offset > 0 && offset >= seg->byte_count)
3473 g_assert (seg != NULL); /* means an invalid byte index */
3474 offset -= seg->byte_count;
3479 *seg_offset = offset;
3485 _gtk_text_line_char_to_any_segment (GtkTextLine *line,
3489 GtkTextLineSegment *seg;
3492 g_return_val_if_fail (line != NULL, NULL);
3494 offset = char_offset;
3495 seg = line->segments;
3497 while (offset > 0 && offset >= seg->char_count)
3499 g_assert (seg != NULL); /* means an invalid byte index */
3500 offset -= seg->char_count;
3505 *seg_offset = offset;
3511 _gtk_text_line_byte_to_char (GtkTextLine *line,
3515 GtkTextLineSegment *seg;
3517 g_return_val_if_fail (line != NULL, 0);
3518 g_return_val_if_fail (byte_offset >= 0, 0);
3521 seg = line->segments;
3522 while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3523 the next segment) */
3525 g_assert (seg != NULL); /* our byte_index was bogus if this happens */
3527 byte_offset -= seg->byte_count;
3528 char_offset += seg->char_count;
3533 g_assert (seg != NULL);
3535 /* Now byte_offset is the offset into the current segment,
3536 and char_offset is the start of the current segment.
3537 Optimize the case where no chars use > 1 byte */
3538 if (seg->byte_count == seg->char_count)
3539 return char_offset + byte_offset;
3542 if (seg->type == >k_text_char_type)
3543 return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3546 g_assert (seg->char_count == 1);
3547 g_assert (byte_offset == 0);
3555 _gtk_text_line_char_to_byte (GtkTextLine *line,
3558 g_warning ("FIXME not implemented");
3563 /* FIXME sync with char_locate (or figure out a clean
3564 way to merge the two functions) */
3566 _gtk_text_line_byte_locate (GtkTextLine *line,
3568 GtkTextLineSegment **segment,
3569 GtkTextLineSegment **any_segment,
3570 gint *seg_byte_offset,
3571 gint *line_byte_offset)
3573 GtkTextLineSegment *seg;
3574 GtkTextLineSegment *after_prev_indexable;
3575 GtkTextLineSegment *after_last_indexable;
3576 GtkTextLineSegment *last_indexable;
3580 g_return_val_if_fail (line != NULL, FALSE);
3581 g_return_val_if_fail (byte_offset >= 0, FALSE);
3584 *any_segment = NULL;
3587 offset = byte_offset;
3589 last_indexable = NULL;
3590 after_last_indexable = line->segments;
3591 after_prev_indexable = line->segments;
3592 seg = line->segments;
3594 /* The loop ends when we're inside a segment;
3595 last_indexable refers to the last segment
3596 we passed entirely. */
3597 while (seg && offset >= seg->byte_count)
3599 if (seg->char_count > 0)
3601 offset -= seg->byte_count;
3602 bytes_in_line += seg->byte_count;
3603 last_indexable = seg;
3604 after_prev_indexable = after_last_indexable;
3605 after_last_indexable = last_indexable->next;
3613 /* We went off the end of the line */
3615 g_warning ("%s: byte index off the end of the line", G_STRLOC);
3622 if (after_last_indexable != NULL)
3623 *any_segment = after_last_indexable;
3625 *any_segment = *segment;
3628 /* Override any_segment if we're in the middle of a segment. */
3630 *any_segment = *segment;
3632 *seg_byte_offset = offset;
3634 g_assert (*segment != NULL);
3635 g_assert (*any_segment != NULL);
3636 g_assert (*seg_byte_offset < (*segment)->byte_count);
3638 *line_byte_offset = bytes_in_line + *seg_byte_offset;
3643 /* FIXME sync with byte_locate (or figure out a clean
3644 way to merge the two functions) */
3646 _gtk_text_line_char_locate (GtkTextLine *line,
3648 GtkTextLineSegment **segment,
3649 GtkTextLineSegment **any_segment,
3650 gint *seg_char_offset,
3651 gint *line_char_offset)
3653 GtkTextLineSegment *seg;
3654 GtkTextLineSegment *after_prev_indexable;
3655 GtkTextLineSegment *after_last_indexable;
3656 GtkTextLineSegment *last_indexable;
3660 g_return_val_if_fail (line != NULL, FALSE);
3661 g_return_val_if_fail (char_offset >= 0, FALSE);
3664 *any_segment = NULL;
3667 offset = char_offset;
3669 last_indexable = NULL;
3670 after_last_indexable = line->segments;
3671 after_prev_indexable = line->segments;
3672 seg = line->segments;
3674 /* The loop ends when we're inside a segment;
3675 last_indexable refers to the last segment
3676 we passed entirely. */
3677 while (seg && offset >= seg->char_count)
3679 if (seg->char_count > 0)
3681 offset -= seg->char_count;
3682 chars_in_line += seg->char_count;
3683 last_indexable = seg;
3684 after_prev_indexable = after_last_indexable;
3685 after_last_indexable = last_indexable->next;
3693 /* end of the line */
3695 g_warning ("%s: char offset off the end of the line", G_STRLOC);
3702 if (after_last_indexable != NULL)
3703 *any_segment = after_last_indexable;
3705 *any_segment = *segment;
3708 /* Override any_segment if we're in the middle of a segment. */
3710 *any_segment = *segment;
3712 *seg_char_offset = offset;
3714 g_assert (*segment != NULL);
3715 g_assert (*any_segment != NULL);
3716 g_assert (*seg_char_offset < (*segment)->char_count);
3718 *line_char_offset = chars_in_line + *seg_char_offset;
3724 _gtk_text_line_byte_to_char_offsets (GtkTextLine *line,
3726 gint *line_char_offset,
3727 gint *seg_char_offset)
3729 GtkTextLineSegment *seg;
3732 g_return_if_fail (line != NULL);
3733 g_return_if_fail (byte_offset >= 0);
3735 *line_char_offset = 0;
3737 offset = byte_offset;
3738 seg = line->segments;
3740 while (offset >= seg->byte_count)
3742 offset -= seg->byte_count;
3743 *line_char_offset += seg->char_count;
3745 g_assert (seg != NULL); /* means an invalid char offset */
3748 g_assert (seg->char_count > 0); /* indexable. */
3750 /* offset is now the number of bytes into the current segment we
3751 * want to go. Count chars into the current segment.
3754 if (seg->type == >k_text_char_type)
3756 *seg_char_offset = g_utf8_strlen (seg->body.chars, offset);
3758 g_assert (*seg_char_offset < seg->char_count);
3760 *line_char_offset += *seg_char_offset;
3764 g_assert (offset == 0);
3765 *seg_char_offset = 0;
3770 _gtk_text_line_char_to_byte_offsets (GtkTextLine *line,
3772 gint *line_byte_offset,
3773 gint *seg_byte_offset)
3775 GtkTextLineSegment *seg;
3778 g_return_if_fail (line != NULL);
3779 g_return_if_fail (char_offset >= 0);
3781 *line_byte_offset = 0;
3783 offset = char_offset;
3784 seg = line->segments;
3786 while (offset >= seg->char_count)
3788 offset -= seg->char_count;
3789 *line_byte_offset += seg->byte_count;
3791 g_assert (seg != NULL); /* means an invalid char offset */
3794 g_assert (seg->char_count > 0); /* indexable. */
3796 /* offset is now the number of chars into the current segment we
3797 want to go. Count bytes into the current segment. */
3799 if (seg->type == >k_text_char_type)
3801 *seg_byte_offset = 0;
3805 const char * start = seg->body.chars + *seg_byte_offset;
3807 bytes = g_utf8_next_char (start) - start;
3808 *seg_byte_offset += bytes;
3812 g_assert (*seg_byte_offset < seg->byte_count);
3814 *line_byte_offset += *seg_byte_offset;
3818 g_assert (offset == 0);
3819 *seg_byte_offset = 0;
3824 node_compare (GtkTextBTreeNode *lhs,
3825 GtkTextBTreeNode *rhs)
3827 GtkTextBTreeNode *iter;
3828 GtkTextBTreeNode *node;
3829 GtkTextBTreeNode *common_parent;
3830 GtkTextBTreeNode *parent_of_lower;
3831 GtkTextBTreeNode *parent_of_higher;
3832 gboolean lhs_is_lower;
3833 GtkTextBTreeNode *lower;
3834 GtkTextBTreeNode *higher;
3836 /* This function assumes that lhs and rhs are not underneath each
3843 if (lhs->level < rhs->level)
3845 lhs_is_lower = TRUE;
3851 lhs_is_lower = FALSE;
3856 /* Algorithm: find common parent of lhs/rhs. Save the child nodes
3857 * of the common parent we used to reach the common parent; the
3858 * ordering of these child nodes in the child list is the ordering
3862 /* Get on the same level (may be on same level already) */
3864 while (node->level < higher->level)
3865 node = node->parent;
3867 g_assert (node->level == higher->level);
3869 g_assert (node != higher); /* Happens if lower is underneath higher */
3871 /* Go up until we have two children with a common parent.
3873 parent_of_lower = node;
3874 parent_of_higher = higher;
3876 while (parent_of_lower->parent != parent_of_higher->parent)
3878 parent_of_lower = parent_of_lower->parent;
3879 parent_of_higher = parent_of_higher->parent;
3882 g_assert (parent_of_lower->parent == parent_of_higher->parent);
3884 common_parent = parent_of_lower->parent;
3886 g_assert (common_parent != NULL);
3888 /* See which is first in the list of common_parent's children */
3889 iter = common_parent->children.node;
3890 while (iter != NULL)
3892 if (iter == parent_of_higher)
3894 /* higher is less than lower */
3897 return 1; /* lhs > rhs */
3901 else if (iter == parent_of_lower)
3903 /* lower is less than higher */
3906 return -1; /* lhs < rhs */
3914 g_assert_not_reached ();
3918 /* remember that tag == NULL means "any tag" */
3920 _gtk_text_line_next_could_contain_tag (GtkTextLine *line,
3924 GtkTextBTreeNode *node;
3925 GtkTextTagInfo *info;
3926 gboolean below_tag_root;
3928 g_return_val_if_fail (line != NULL, NULL);
3930 if (gtk_debug_flags & GTK_DEBUG_TEXT)
3931 _gtk_text_btree_check (tree);
3935 /* Right now we can only offer linear-search if the user wants
3936 * to know about any tag toggle at all.
3938 return _gtk_text_line_next (line);
3941 /* Our tag summaries only have node precision, not line
3942 precision. This means that if any line under a node could contain a
3943 tag, then any of the others could also contain a tag.
3945 In the future we could have some mechanism to keep track of how
3946 many toggles we've found under a node so far, since we have a
3947 count of toggles under the node. But for now I'm going with KISS.
3950 /* return same-node line, if any. */
3954 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3958 if (info->tag_root == NULL)
3961 if (info->tag_root == line->parent)
3962 return NULL; /* we were at the last line under the tag root */
3964 /* We need to go up out of this node, and on to the next one with
3965 toggles for the target tag. If we're below the tag root, we need to
3966 find the next node below the tag root that has tag summaries. If
3967 we're not below the tag root, we need to see if the tag root is
3968 after us in the tree, and if so, return the first line underneath
3971 node = line->parent;
3972 below_tag_root = FALSE;
3973 while (node != NULL)
3975 if (node == info->tag_root)
3977 below_tag_root = TRUE;
3981 node = node->parent;
3986 node = line->parent;
3987 while (node != info->tag_root)
3989 if (node->next == NULL)
3990 node = node->parent;
3995 if (gtk_text_btree_node_has_tag (node, tag))
4005 ordering = node_compare (line->parent, info->tag_root);
4009 /* Tag root is ahead of us, so search there. */
4010 node = info->tag_root;
4015 /* Tag root is after us, so no more lines that
4016 * could contain the tag.
4021 g_assert_not_reached ();
4026 g_assert (node != NULL);
4028 /* We have to find the first sub-node of this node that contains
4032 while (node->level > 0)
4034 g_assert (node != NULL); /* If this fails, it likely means an
4035 incorrect tag summary led us on a
4036 wild goose chase down this branch of
4038 node = node->children.node;
4039 while (node != NULL)
4041 if (gtk_text_btree_node_has_tag (node, tag))
4047 g_assert (node != NULL);
4048 g_assert (node->level == 0);
4050 return node->children.line;
4054 prev_line_under_node (GtkTextBTreeNode *node,
4059 prev = node->children.line;
4065 while (prev->next != line)
4075 _gtk_text_line_previous_could_contain_tag (GtkTextLine *line,
4079 GtkTextBTreeNode *node;
4080 GtkTextBTreeNode *found_node = NULL;
4081 GtkTextTagInfo *info;
4082 gboolean below_tag_root;
4084 GtkTextBTreeNode *line_ancestor;
4085 GtkTextBTreeNode *line_ancestor_parent;
4087 /* See next_could_contain_tag () for more extensive comments
4088 * on what's going on here.
4091 g_return_val_if_fail (line != NULL, NULL);
4093 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4094 _gtk_text_btree_check (tree);
4098 /* Right now we can only offer linear-search if the user wants
4099 * to know about any tag toggle at all.
4101 return _gtk_text_line_previous (line);
4104 /* Return same-node line, if any. */
4105 prev = prev_line_under_node (line->parent, line);
4109 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4113 if (info->tag_root == NULL)
4116 if (info->tag_root == line->parent)
4117 return NULL; /* we were at the first line under the tag root */
4119 /* Are we below the tag root */
4120 node = line->parent;
4121 below_tag_root = FALSE;
4122 while (node != NULL)
4124 if (node == info->tag_root)
4126 below_tag_root = TRUE;
4130 node = node->parent;
4135 /* Look for a previous node under this tag root that has our
4139 /* this assertion holds because line->parent is not the
4140 * tag root, we are below the tag root, and the tag
4143 g_assert (line->parent->parent != NULL);
4145 line_ancestor = line->parent;
4146 line_ancestor_parent = line->parent->parent;
4148 node = line_ancestor_parent->children.node;
4149 while (node != line_ancestor &&
4150 line_ancestor != info->tag_root)
4152 GSList *child_nodes = NULL;
4155 /* Create reverse-order list of nodes before
4158 while (node != line_ancestor
4161 child_nodes = g_slist_prepend (child_nodes, node);
4166 /* Try to find a node with our tag on it in the list */
4170 GtkTextBTreeNode *this_node = tmp->data;
4172 g_assert (this_node != line_ancestor);
4174 if (gtk_text_btree_node_has_tag (this_node, tag))
4176 found_node = this_node;
4177 g_slist_free (child_nodes);
4181 tmp = g_slist_next (tmp);
4184 g_slist_free (child_nodes);
4186 /* Didn't find anything on this level; go up one level. */
4187 line_ancestor = line_ancestor_parent;
4188 line_ancestor_parent = line_ancestor->parent;
4190 node = line_ancestor_parent->children.node;
4200 ordering = node_compare (line->parent, info->tag_root);
4204 /* Tag root is ahead of us, so no more lines
4211 /* Tag root is after us, so grab last tagged
4212 * line underneath the tag root.
4214 found_node = info->tag_root;
4218 g_assert_not_reached ();
4223 g_assert (found_node != NULL);
4225 /* We have to find the last sub-node of this node that contains
4230 while (node->level > 0)
4232 GSList *child_nodes = NULL;
4234 g_assert (node != NULL); /* If this fails, it likely means an
4235 incorrect tag summary led us on a
4236 wild goose chase down this branch of
4239 node = node->children.node;
4240 while (node != NULL)
4242 child_nodes = g_slist_prepend (child_nodes, node);
4246 node = NULL; /* detect failure to find a child node. */
4249 while (iter != NULL)
4251 if (gtk_text_btree_node_has_tag (iter->data, tag))
4253 /* recurse into this node. */
4258 iter = g_slist_next (iter);
4261 g_slist_free (child_nodes);
4263 g_assert (node != NULL);
4266 g_assert (node != NULL);
4267 g_assert (node->level == 0);
4269 /* this assertion is correct, but slow. */
4270 /* g_assert (node_compare (node, line->parent) < 0); */
4272 /* Return last line in this node. */
4274 prev = node->children.line;
4282 * Non-public function implementations
4286 summary_list_destroy (Summary *summary)
4289 while (summary != NULL)
4291 next = summary->next;
4292 summary_destroy (summary);
4298 get_last_line (GtkTextBTree *tree)
4300 if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
4306 n_lines = _gtk_text_btree_line_count (tree);
4308 g_assert (n_lines >= 1); /* num_lines doesn't return bogus last line. */
4310 line = _gtk_text_btree_get_line (tree, n_lines, &real_line);
4312 tree->end_iter_line_stamp = tree->chars_changed_stamp;
4313 tree->end_iter_line = line;
4316 return tree->end_iter_line;
4324 gtk_text_line_new (void)
4328 line = g_new0(GtkTextLine, 1);
4334 gtk_text_line_destroy (GtkTextBTree *tree, GtkTextLine *line)
4336 GtkTextLineData *ld;
4337 GtkTextLineData *next;
4339 g_return_if_fail (line != NULL);
4346 view = gtk_text_btree_get_view (tree, ld->view_id);
4348 g_assert (view != NULL);
4351 gtk_text_layout_free_line_data (view->layout, line, ld);
4360 gtk_text_line_set_parent (GtkTextLine *line,
4361 GtkTextBTreeNode *node)
4363 if (line->parent == node)
4365 line->parent = node;
4366 gtk_text_btree_node_invalidate_upward (node, NULL);
4370 cleanup_line (GtkTextLine *line)
4372 GtkTextLineSegment *seg, **prev_p;
4376 * Make a pass over all of the segments in the line, giving each
4377 * a chance to clean itself up. This could potentially change
4378 * the structure of the line, e.g. by merging two segments
4379 * together or having two segments cancel themselves; if so,
4380 * then repeat the whole process again, since the first structure
4381 * change might make other structure changes possible. Repeat
4382 * until eventually there are no changes.
4389 for (prev_p = &line->segments, seg = *prev_p;
4391 prev_p = &(*prev_p)->next, seg = *prev_p)
4393 if (seg->type->cleanupFunc != NULL)
4395 *prev_p = (*seg->type->cleanupFunc)(seg, line);
4408 node_data_new (gpointer view_id)
4412 nd = g_new (NodeData, 1);
4414 nd->view_id = view_id;
4424 node_data_destroy (NodeData *nd)
4431 node_data_list_destroy (NodeData *nd)
4437 while (iter != NULL)
4440 node_data_destroy (iter);
4446 node_data_find (NodeData *nd, gpointer view_id)
4450 if (nd->view_id == view_id)
4458 summary_destroy (Summary *summary)
4460 /* Fill with error-triggering garbage */
4461 summary->info = (void*)0x1;
4462 summary->toggle_count = 567;
4463 summary->next = (void*)0x1;
4467 static GtkTextBTreeNode*
4468 gtk_text_btree_node_new (void)
4470 GtkTextBTreeNode *node;
4472 node = g_new (GtkTextBTreeNode, 1);
4474 node->node_data = NULL;
4480 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
4481 GtkTextTagInfo *info,
4486 summary = node->summary;
4487 while (summary != NULL)
4489 if (summary->info == info)
4491 summary->toggle_count += adjust;
4495 summary = summary->next;
4498 if (summary == NULL)
4500 /* didn't find a summary for our tag. */
4501 g_return_if_fail (adjust > 0);
4502 summary = g_new (Summary, 1);
4503 summary->info = info;
4504 summary->toggle_count = adjust;
4505 summary->next = node->summary;
4506 node->summary = summary;
4510 /* Note that the tag root and above do not have summaries
4511 for the tag; only nodes below the tag root have
4514 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4518 summary = node->summary;
4519 while (summary != NULL)
4522 summary->info->tag == tag)
4525 summary = summary->next;
4531 /* Add node and all children to the damage region. */
4533 gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node)
4537 nd = node->node_data;
4544 if (node->level == 0)
4548 line = node->children.line;
4549 while (line != NULL)
4551 GtkTextLineData *ld;
4565 GtkTextBTreeNode *child;
4567 child = node->children.node;
4569 while (child != NULL)
4571 gtk_text_btree_node_invalidate_downward (child);
4573 child = child->next;
4579 gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node, gpointer view_id)
4581 GtkTextBTreeNode *iter;
4584 while (iter != NULL)
4590 nd = node_data_find (iter->node_data, view_id);
4592 if (nd == NULL || !nd->valid)
4593 break; /* Once a node is invalid, we know its parents are as well. */
4599 gboolean should_continue = FALSE;
4601 nd = iter->node_data;
4606 should_continue = TRUE;
4613 if (!should_continue)
4614 break; /* This node was totally invalidated, so are its
4618 iter = iter->parent;
4624 * _gtk_text_btree_is_valid:
4625 * @tree: a #GtkTextBTree
4626 * @view_id: ID for the view
4628 * Check to see if the entire #GtkTextBTree is valid or not for
4631 * Return value: %TRUE if the entire #GtkTextBTree is valid
4634 _gtk_text_btree_is_valid (GtkTextBTree *tree,
4638 g_return_val_if_fail (tree != NULL, FALSE);
4640 nd = node_data_find (tree->root_node->node_data, view_id);
4641 return (nd && nd->valid);
4644 typedef struct _ValidateState ValidateState;
4646 struct _ValidateState
4648 gint remaining_pixels;
4649 gboolean in_validation;
4656 gtk_text_btree_node_validate (BTreeView *view,
4657 GtkTextBTreeNode *node,
4659 ValidateState *state)
4661 gint node_valid = TRUE;
4662 gint node_width = 0;
4663 gint node_height = 0;
4665 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4666 g_return_if_fail (!nd->valid);
4668 if (node->level == 0)
4670 GtkTextLine *line = node->children.line;
4671 GtkTextLineData *ld;
4673 /* Iterate over leading valid lines */
4674 while (line != NULL)
4676 ld = _gtk_text_line_get_data (line, view_id);
4678 if (!ld || !ld->valid)
4680 else if (state->in_validation)
4682 state->in_validation = FALSE;
4687 state->y += ld->height;
4688 node_width = MAX (ld->width, node_width);
4689 node_height += ld->height;
4695 state->in_validation = TRUE;
4697 /* Iterate over invalid lines */
4698 while (line != NULL)
4700 ld = _gtk_text_line_get_data (line, view_id);
4702 if (ld && ld->valid)
4707 state->old_height += ld->height;
4708 ld = gtk_text_layout_wrap (view->layout, line, ld);
4709 state->new_height += ld->height;
4711 node_width = MAX (ld->width, node_width);
4712 node_height += ld->height;
4714 state->remaining_pixels -= ld->height;
4715 if (state->remaining_pixels <= 0)
4725 /* Iterate over the remaining lines */
4726 while (line != NULL)
4728 ld = _gtk_text_line_get_data (line, view_id);
4729 state->in_validation = FALSE;
4731 if (!ld || !ld->valid)
4736 node_width = MAX (ld->width, node_width);
4737 node_height += ld->height;
4745 GtkTextBTreeNode *child;
4748 child = node->children.node;
4750 /* Iterate over leading valid nodes */
4753 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4755 if (!child_nd->valid)
4757 else if (state->in_validation)
4759 state->in_validation = FALSE;
4764 state->y += child_nd->height;
4765 node_width = MAX (node_width, child_nd->width);
4766 node_height += child_nd->height;
4769 child = child->next;
4772 /* Iterate over invalid nodes */
4775 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4777 if (child_nd->valid)
4781 gtk_text_btree_node_validate (view, child, view_id, state);
4783 if (!child_nd->valid)
4785 node_width = MAX (node_width, child_nd->width);
4786 node_height += child_nd->height;
4788 if (!state->in_validation || state->remaining_pixels <= 0)
4790 child = child->next;
4795 child = child->next;
4798 /* Iterate over the remaining lines */
4801 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4802 state->in_validation = FALSE;
4804 if (!child_nd->valid)
4807 node_width = MAX (child_nd->width, node_width);
4808 node_height += child_nd->height;
4810 child = child->next;
4814 nd->width = node_width;
4815 nd->height = node_height;
4816 nd->valid = node_valid;
4820 * _gtk_text_btree_validate:
4821 * @tree: a #GtkTextBTree
4823 * @max_pixels: the maximum number of pixels to validate. (No more
4824 * than one paragraph beyond this limit will be validated)
4825 * @y: location to store starting y coordinate of validated region
4826 * @old_height: location to store old height of validated region
4827 * @new_height: location to store new height of validated region
4829 * Validate a single contiguous invalid region of a #GtkTextBTree for
4832 * Return value: %TRUE if a region has been validated, %FALSE if the
4833 * entire tree was already valid.
4836 _gtk_text_btree_validate (GtkTextBTree *tree,
4845 g_return_val_if_fail (tree != NULL, FALSE);
4847 view = gtk_text_btree_get_view (tree, view_id);
4848 g_return_val_if_fail (view != NULL, FALSE);
4850 if (!_gtk_text_btree_is_valid (tree, view_id))
4852 ValidateState state;
4854 state.remaining_pixels = max_pixels;
4855 state.in_validation = FALSE;
4857 state.old_height = 0;
4858 state.new_height = 0;
4860 gtk_text_btree_node_validate (view,
4867 *old_height = state.old_height;
4869 *new_height = state.new_height;
4871 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4872 _gtk_text_btree_check (tree);
4881 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
4885 gboolean *valid_out)
4889 gboolean valid = TRUE;
4891 if (node->level == 0)
4893 GtkTextLine *line = node->children.line;
4895 while (line != NULL)
4897 GtkTextLineData *ld = _gtk_text_line_get_data (line, view_id);
4899 if (!ld || !ld->valid)
4904 width = MAX (ld->width, width);
4905 height += ld->height;
4913 GtkTextBTreeNode *child = node->children.node;
4917 NodeData *child_nd = node_data_find (child->node_data, view_id);
4919 if (!child_nd || !child_nd->valid)
4924 width = MAX (child_nd->width, width);
4925 height += child_nd->height;
4928 child = child->next;
4933 *height_out = height;
4938 /* Recompute the validity and size of the view data for a given
4939 * view at this node from the immediate children of the node
4942 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
4945 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4950 gtk_text_btree_node_compute_view_aggregates (node, view_id,
4951 &width, &height, &valid);
4953 nd->height = height;
4960 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
4965 gtk_text_btree_node_check_valid (node, view_id);
4966 node = node->parent;
4971 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
4974 if (node->level == 0)
4976 return gtk_text_btree_node_check_valid (node, view_id);
4980 GtkTextBTreeNode *child = node->children.node;
4982 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4990 NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
4992 if (!child_nd->valid)
4994 nd->width = MAX (child_nd->width, nd->width);
4995 nd->height += child_nd->height;
4997 child = child->next;
5006 * _gtk_text_btree_validate_line:
5007 * @tree: a #GtkTextBTree
5008 * @line: line to validate
5009 * @view_id: view ID for the view to validate
5011 * Revalidate a single line of the btree for the given view, propagate
5012 * results up through the entire tree.
5015 _gtk_text_btree_validate_line (GtkTextBTree *tree,
5019 GtkTextLineData *ld;
5022 g_return_if_fail (tree != NULL);
5023 g_return_if_fail (line != NULL);
5025 view = gtk_text_btree_get_view (tree, view_id);
5026 g_return_if_fail (view != NULL);
5028 ld = _gtk_text_line_get_data (line, view_id);
5029 if (!ld || !ld->valid)
5031 ld = gtk_text_layout_wrap (view->layout, line, ld);
5033 gtk_text_btree_node_check_valid_upward (line->parent, view_id);
5038 gtk_text_btree_node_remove_view (BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
5040 if (node->level == 0)
5044 line = node->children.line;
5045 while (line != NULL)
5047 GtkTextLineData *ld;
5049 ld = _gtk_text_line_remove_data (line, view_id);
5052 gtk_text_layout_free_line_data (view->layout, line, ld);
5059 GtkTextBTreeNode *child;
5061 child = node->children.node;
5063 while (child != NULL)
5066 gtk_text_btree_node_remove_view (view, child, view_id);
5068 child = child->next;
5072 gtk_text_btree_node_remove_data (node, view_id);
5076 gtk_text_btree_node_destroy (GtkTextBTree *tree, GtkTextBTreeNode *node)
5078 if (node->level == 0)
5081 GtkTextLineSegment *seg;
5083 while (node->children.line != NULL)
5085 line = node->children.line;
5086 node->children.line = line->next;
5087 while (line->segments != NULL)
5089 seg = line->segments;
5090 line->segments = seg->next;
5092 if (GTK_IS_TEXT_MARK_SEGMENT (seg))
5094 /* Set the mark as deleted */
5095 seg->body.mark.tree = NULL;
5096 seg->body.mark.line = NULL;
5099 (*seg->type->deleteFunc) (seg, line, 1);
5101 gtk_text_line_destroy (tree, line);
5106 GtkTextBTreeNode *childPtr;
5108 while (node->children.node != NULL)
5110 childPtr = node->children.node;
5111 node->children.node = childPtr->next;
5112 gtk_text_btree_node_destroy (tree, childPtr);
5116 summary_list_destroy (node->summary);
5117 node_data_list_destroy (node->node_data);
5122 gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node, gpointer view_id)
5126 nd = node->node_data;
5129 if (nd->view_id == view_id)
5137 nd = node_data_new (view_id);
5139 if (node->node_data)
5140 nd->next = node->node_data;
5142 node->node_data = nd;
5149 gtk_text_btree_node_remove_data (GtkTextBTreeNode *node, gpointer view_id)
5155 nd = node->node_data;
5158 if (nd->view_id == view_id)
5169 prev->next = nd->next;
5171 if (node->node_data == nd)
5172 node->node_data = nd->next;
5176 node_data_destroy (nd);
5180 gtk_text_btree_node_get_size (GtkTextBTreeNode *node, gpointer view_id,
5181 gint *width, gint *height)
5185 g_return_if_fail (width != NULL);
5186 g_return_if_fail (height != NULL);
5188 nd = gtk_text_btree_node_ensure_data (node, view_id);
5193 *height = nd->height;
5196 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5197 * here isn't quite right, since for a lot of operations we want to
5198 * know which children of the common parent correspond to the two nodes
5199 * (e.g., when computing the order of two iters)
5201 static GtkTextBTreeNode *
5202 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5203 GtkTextBTreeNode *node2)
5205 while (node1->level < node2->level)
5206 node1 = node1->parent;
5207 while (node2->level < node1->level)
5208 node2 = node2->parent;
5209 while (node1 != node2)
5211 node1 = node1->parent;
5212 node2 = node2->parent;
5223 gtk_text_btree_get_view (GtkTextBTree *tree, gpointer view_id)
5228 while (view != NULL)
5230 if (view->view_id == view_id)
5239 get_tree_bounds (GtkTextBTree *tree,
5243 _gtk_text_btree_get_iter_at_line_char (tree, start, 0, 0);
5244 _gtk_text_btree_get_end_iter (tree, end);
5248 tag_changed_cb (GtkTextTagTable *table,
5250 gboolean size_changed,
5255 /* We need to queue a relayout on all regions that are tagged with
5262 if (_gtk_text_btree_get_iter_at_first_toggle (tree, &start, tag))
5264 /* Must be a last toggle if there was a first one. */
5265 _gtk_text_btree_get_iter_at_last_toggle (tree, &end, tag);
5266 _gtk_text_btree_invalidate_region (tree,
5273 /* We only need to queue a redraw, not a relayout */
5278 while (view != NULL)
5282 _gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5283 gtk_text_layout_changed (view->layout, 0, height, height);
5291 tag_removed_cb (GtkTextTagTable *table,
5295 /* Remove the tag from the tree */
5300 get_tree_bounds (tree, &start, &end);
5302 _gtk_text_btree_tag (&start, &end, tag, FALSE);
5303 gtk_text_btree_remove_tag_info (tree, tag);
5307 /* Rebalance the out-of-whack node "node" */
5309 gtk_text_btree_rebalance (GtkTextBTree *tree,
5310 GtkTextBTreeNode *node)
5313 * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5314 * up through the tree one GtkTextBTreeNode at a time until the root
5315 * GtkTextBTreeNode has been processed.
5318 while (node != NULL)
5320 GtkTextBTreeNode *new_node, *child;
5325 * Check to see if the GtkTextBTreeNode has too many children. If it does,
5326 * then split off all but the first MIN_CHILDREN into a separate
5327 * GtkTextBTreeNode following the original one. Then repeat until the
5328 * GtkTextBTreeNode has a decent size.
5331 if (node->num_children > MAX_CHILDREN)
5336 * If the GtkTextBTreeNode being split is the root
5337 * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5341 if (node->parent == NULL)
5343 new_node = gtk_text_btree_node_new ();
5344 new_node->parent = NULL;
5345 new_node->next = NULL;
5346 new_node->summary = NULL;
5347 new_node->level = node->level + 1;
5348 new_node->children.node = node;
5349 recompute_node_counts (tree, new_node);
5350 tree->root_node = new_node;
5352 new_node = gtk_text_btree_node_new ();
5353 new_node->parent = node->parent;
5354 new_node->next = node->next;
5355 node->next = new_node;
5356 new_node->summary = NULL;
5357 new_node->level = node->level;
5358 new_node->num_children = node->num_children - MIN_CHILDREN;
5359 if (node->level == 0)
5361 for (i = MIN_CHILDREN-1,
5362 line = node->children.line;
5363 i > 0; i--, line = line->next)
5365 /* Empty loop body. */
5367 new_node->children.line = line->next;
5372 for (i = MIN_CHILDREN-1,
5373 child = node->children.node;
5374 i > 0; i--, child = child->next)
5376 /* Empty loop body. */
5378 new_node->children.node = child->next;
5381 recompute_node_counts (tree, node);
5382 node->parent->num_children++;
5384 if (node->num_children <= MAX_CHILDREN)
5386 recompute_node_counts (tree, node);
5392 while (node->num_children < MIN_CHILDREN)
5394 GtkTextBTreeNode *other;
5395 GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5396 GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5397 int total_children, first_children, i;
5400 * Too few children for this GtkTextBTreeNode. If this is the root then,
5401 * it's OK for it to have less than MIN_CHILDREN children
5402 * as long as it's got at least two. If it has only one
5403 * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5404 * the tree and use its child as the new root.
5407 if (node->parent == NULL)
5409 if ((node->num_children == 1) && (node->level > 0))
5411 tree->root_node = node->children.node;
5412 tree->root_node->parent = NULL;
5413 summary_list_destroy (node->summary);
5420 * Not the root. Make sure that there are siblings to
5424 if (node->parent->num_children < 2)
5426 gtk_text_btree_rebalance (tree, node->parent);
5431 * Find a sibling neighbor to borrow from, and arrange for
5432 * node to be the earlier of the pair.
5435 if (node->next == NULL)
5437 for (other = node->parent->children.node;
5438 other->next != node;
5439 other = other->next)
5441 /* Empty loop body. */
5448 * We're going to either merge the two siblings together
5449 * into one GtkTextBTreeNode or redivide the children among them to
5450 * balance their loads. As preparation, join their two
5451 * child lists into a single list and remember the half-way
5452 * point in the list.
5455 total_children = node->num_children + other->num_children;
5456 first_children = total_children/2;
5457 if (node->children.node == NULL)
5459 node->children = other->children;
5460 other->children.node = NULL;
5461 other->children.line = NULL;
5463 if (node->level == 0)
5467 for (line = node->children.line, i = 1;
5469 line = line->next, i++)
5471 if (i == first_children)
5476 line->next = other->children.line;
5477 while (i <= first_children)
5486 GtkTextBTreeNode *child;
5488 for (child = node->children.node, i = 1;
5489 child->next != NULL;
5490 child = child->next, i++)
5492 if (i <= first_children)
5494 if (i == first_children)
5496 halfwaynode = child;
5500 child->next = other->children.node;
5501 while (i <= first_children)
5503 halfwaynode = child;
5504 child = child->next;
5510 * If the two siblings can simply be merged together, do it.
5513 if (total_children <= MAX_CHILDREN)
5515 recompute_node_counts (tree, node);
5516 node->next = other->next;
5517 node->parent->num_children--;
5518 summary_list_destroy (other->summary);
5524 * The siblings can't be merged, so just divide their
5525 * children evenly between them.
5528 if (node->level == 0)
5530 other->children.line = halfwayline->next;
5531 halfwayline->next = NULL;
5535 other->children.node = halfwaynode->next;
5536 halfwaynode->next = NULL;
5539 recompute_node_counts (tree, node);
5540 recompute_node_counts (tree, other);
5543 node = node->parent;
5548 post_insert_fixup (GtkTextBTree *tree,
5550 gint line_count_delta,
5551 gint char_count_delta)
5554 GtkTextBTreeNode *node;
5557 * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5558 * point, then rebalance the tree if necessary.
5561 for (node = line->parent ; node != NULL;
5562 node = node->parent)
5564 node->num_lines += line_count_delta;
5565 node->num_chars += char_count_delta;
5567 node = line->parent;
5568 node->num_children += line_count_delta;
5570 if (node->num_children > MAX_CHILDREN)
5572 gtk_text_btree_rebalance (tree, node);
5575 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5576 _gtk_text_btree_check (tree);
5579 static GtkTextTagInfo*
5580 gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
5583 GtkTextTagInfo *info;
5587 list = tree->tag_infos;
5588 while (list != NULL)
5591 if (info->tag == tag)
5594 list = g_slist_next (list);
5600 static GtkTextTagInfo*
5601 gtk_text_btree_get_tag_info (GtkTextBTree *tree,
5604 GtkTextTagInfo *info;
5606 info = gtk_text_btree_get_existing_tag_info (tree, tag);
5610 /* didn't find it, create. */
5612 info = g_new (GtkTextTagInfo, 1);
5615 g_object_ref (G_OBJECT (tag));
5616 info->tag_root = NULL;
5617 info->toggle_count = 0;
5619 tree->tag_infos = g_slist_prepend (tree->tag_infos, info);
5626 gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
5629 GtkTextTagInfo *info;
5634 list = tree->tag_infos;
5635 while (list != NULL)
5638 if (info->tag == tag)
5642 prev->next = list->next;
5646 tree->tag_infos = list->next;
5649 g_slist_free (list);
5651 g_object_unref (G_OBJECT (info->tag));
5657 list = g_slist_next (list);
5660 g_assert_not_reached ();
5665 recompute_level_zero_counts (GtkTextBTreeNode *node)
5668 GtkTextLineSegment *seg;
5670 g_assert (node->level == 0);
5672 line = node->children.line;
5673 while (line != NULL)
5675 node->num_children++;
5678 if (line->parent != node)
5679 gtk_text_line_set_parent (line, node);
5681 seg = line->segments;
5685 node->num_chars += seg->char_count;
5687 if (((seg->type != >k_text_toggle_on_type)
5688 && (seg->type != >k_text_toggle_off_type))
5689 || !(seg->body.toggle.inNodeCounts))
5695 GtkTextTagInfo *info;
5697 info = seg->body.toggle.info;
5699 gtk_text_btree_node_adjust_toggle_count (node, info, 1);
5710 recompute_level_nonzero_counts (GtkTextBTreeNode *node)
5713 GtkTextBTreeNode *child;
5715 g_assert (node->level > 0);
5717 child = node->children.node;
5718 while (child != NULL)
5720 node->num_children += 1;
5721 node->num_lines += child->num_lines;
5722 node->num_chars += child->num_chars;
5724 if (child->parent != node)
5726 child->parent = node;
5727 gtk_text_btree_node_invalidate_upward (node, NULL);
5730 summary = child->summary;
5731 while (summary != NULL)
5733 gtk_text_btree_node_adjust_toggle_count (node,
5735 summary->toggle_count);
5737 summary = summary->next;
5740 child = child->next;
5745 *----------------------------------------------------------------------
5747 * recompute_node_counts --
5749 * This procedure is called to recompute all the counts in a GtkTextBTreeNode
5750 * (tags, child information, etc.) by scanning the information in
5751 * its descendants. This procedure is called during rebalancing
5752 * when a GtkTextBTreeNode's child structure has changed.
5758 * The tag counts for node are modified to reflect its current
5759 * child structure, as are its num_children, num_lines, num_chars fields.
5760 * Also, all of the childrens' parent fields are made to point
5763 *----------------------------------------------------------------------
5767 recompute_node_counts (GtkTextBTree *tree, GtkTextBTreeNode *node)
5770 Summary *summary, *summary2;
5773 * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
5774 * the existing Summary records (most of them will probably be reused).
5777 summary = node->summary;
5778 while (summary != NULL)
5780 summary->toggle_count = 0;
5781 summary = summary->next;
5784 node->num_children = 0;
5785 node->num_lines = 0;
5786 node->num_chars = 0;
5789 * Scan through the children, adding the childrens' tag counts into
5790 * the GtkTextBTreeNode's tag counts and adding new Summary structures if
5794 if (node->level == 0)
5795 recompute_level_zero_counts (node);
5797 recompute_level_nonzero_counts (node);
5802 gtk_text_btree_node_check_valid (node, view->view_id);
5807 * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
5808 * records that still have a zero count, or that have all the toggles.
5809 * The GtkTextBTreeNode with the children that account for all the tags toggles
5810 * have no summary information, and they become the tag_root for the tag.
5814 for (summary = node->summary; summary != NULL; )
5816 if (summary->toggle_count > 0 &&
5817 summary->toggle_count < summary->info->toggle_count)
5819 if (node->level == summary->info->tag_root->level)
5822 * The tag's root GtkTextBTreeNode split and some toggles left.
5823 * The tag root must move up a level.
5825 summary->info->tag_root = node->parent;
5828 summary = summary->next;
5831 if (summary->toggle_count == summary->info->toggle_count)
5834 * A GtkTextBTreeNode merge has collected all the toggles under
5835 * one GtkTextBTreeNode. Push the root down to this level.
5837 summary->info->tag_root = node;
5839 if (summary2 != NULL)
5841 summary2->next = summary->next;
5842 summary_destroy (summary);
5843 summary = summary2->next;
5847 node->summary = summary->next;
5848 summary_destroy (summary);
5849 summary = node->summary;
5855 _gtk_change_node_toggle_count (GtkTextBTreeNode *node,
5856 GtkTextTagInfo *info,
5857 gint delta) /* may be negative */
5859 Summary *summary, *prevPtr;
5860 GtkTextBTreeNode *node2Ptr;
5861 int rootLevel; /* Level of original tag root */
5863 info->toggle_count += delta;
5865 if (info->tag_root == (GtkTextBTreeNode *) NULL)
5867 info->tag_root = node;
5872 * Note the level of the existing root for the tag so we can detect
5873 * if it needs to be moved because of the toggle count change.
5876 rootLevel = info->tag_root->level;
5879 * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
5880 * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
5884 for ( ; node != info->tag_root; node = node->parent)
5887 * See if there's already an entry for this tag for this GtkTextBTreeNode. If so,
5888 * perhaps all we have to do is adjust its count.
5891 for (prevPtr = NULL, summary = node->summary;
5893 prevPtr = summary, summary = summary->next)
5895 if (summary->info == info)
5900 if (summary != NULL)
5902 summary->toggle_count += delta;
5903 if (summary->toggle_count > 0 &&
5904 summary->toggle_count < info->toggle_count)
5908 if (summary->toggle_count != 0)
5911 * Should never find a GtkTextBTreeNode with max toggle count at this
5912 * point (there shouldn't have been a summary entry in the
5916 g_error ("%s: bad toggle count (%d) max (%d)",
5917 G_STRLOC, summary->toggle_count, info->toggle_count);
5921 * Zero toggle count; must remove this tag from the list.
5924 if (prevPtr == NULL)
5926 node->summary = summary->next;
5930 prevPtr->next = summary->next;
5932 summary_destroy (summary);
5937 * This tag isn't currently in the summary information list.
5940 if (rootLevel == node->level)
5944 * The old tag root is at the same level in the tree as this
5945 * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode. Move the tag root up
5946 * a level, in the hopes that it will now cover this GtkTextBTreeNode
5947 * as well as the old root (if not, we'll move it up again
5948 * the next time through the loop). To push it up one level
5949 * we copy the original toggle count into the summary
5950 * information at the old root and change the root to its
5951 * parent GtkTextBTreeNode.
5954 GtkTextBTreeNode *rootnode = info->tag_root;
5955 summary = (Summary *) g_malloc (sizeof (Summary));
5956 summary->info = info;
5957 summary->toggle_count = info->toggle_count - delta;
5958 summary->next = rootnode->summary;
5959 rootnode->summary = summary;
5960 rootnode = rootnode->parent;
5961 rootLevel = rootnode->level;
5962 info->tag_root = rootnode;
5964 summary = (Summary *) g_malloc (sizeof (Summary));
5965 summary->info = info;
5966 summary->toggle_count = delta;
5967 summary->next = node->summary;
5968 node->summary = summary;
5973 * If we've decremented the toggle count, then it may be necessary
5974 * to push the tag root down one or more levels.
5981 if (info->toggle_count == 0)
5983 info->tag_root = (GtkTextBTreeNode *) NULL;
5986 node = info->tag_root;
5987 while (node->level > 0)
5990 * See if a single child GtkTextBTreeNode accounts for all of the tag's
5991 * toggles. If so, push the root down one level.
5994 for (node2Ptr = node->children.node;
5995 node2Ptr != (GtkTextBTreeNode *)NULL ;
5996 node2Ptr = node2Ptr->next)
5998 for (prevPtr = NULL, summary = node2Ptr->summary;
6000 prevPtr = summary, summary = summary->next)
6002 if (summary->info == info)
6007 if (summary == NULL)
6011 if (summary->toggle_count != info->toggle_count)
6014 * No GtkTextBTreeNode has all toggles, so the root is still valid.
6021 * This GtkTextBTreeNode has all the toggles, so push down the root.
6024 if (prevPtr == NULL)
6026 node2Ptr->summary = summary->next;
6030 prevPtr->next = summary->next;
6032 summary_destroy (summary);
6033 info->tag_root = node2Ptr;
6036 node = info->tag_root;
6041 *----------------------------------------------------------------------
6045 * This is a utility procedure used by _gtk_text_btree_get_tags. It
6046 * increments the count for a particular tag, adding a new
6047 * entry for that tag if there wasn't one previously.
6053 * The information at *tagInfoPtr may be modified, and the arrays
6054 * may be reallocated to make them larger.
6056 *----------------------------------------------------------------------
6060 inc_count (GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
6065 for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
6066 count > 0; tag_p++, count--)
6070 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
6076 * There isn't currently an entry for this tag, so we have to
6077 * make a new one. If the arrays are full, then enlarge the
6081 if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
6083 GtkTextTag **newTags;
6084 int *newCounts, newSize;
6086 newSize = 2*tagInfoPtr->arraySize;
6087 newTags = (GtkTextTag **) g_malloc ((unsigned)
6088 (newSize*sizeof (GtkTextTag *)));
6089 memcpy ((void *) newTags, (void *) tagInfoPtr->tags,
6090 tagInfoPtr->arraySize *sizeof (GtkTextTag *));
6091 g_free ((char *) tagInfoPtr->tags);
6092 tagInfoPtr->tags = newTags;
6093 newCounts = (int *) g_malloc ((unsigned) (newSize*sizeof (int)));
6094 memcpy ((void *) newCounts, (void *) tagInfoPtr->counts,
6095 tagInfoPtr->arraySize *sizeof (int));
6096 g_free ((char *) tagInfoPtr->counts);
6097 tagInfoPtr->counts = newCounts;
6098 tagInfoPtr->arraySize = newSize;
6101 tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
6102 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
6103 tagInfoPtr->numTags++;
6107 gtk_text_btree_link_segment (GtkTextLineSegment *seg,
6108 const GtkTextIter *iter)
6110 GtkTextLineSegment *prev;
6114 line = _gtk_text_iter_get_text_line (iter);
6115 tree = _gtk_text_iter_get_btree (iter);
6117 prev = gtk_text_line_segment_split (iter);
6120 seg->next = line->segments;
6121 line->segments = seg;
6125 seg->next = prev->next;
6128 cleanup_line (line);
6129 segments_changed (tree);
6131 if (gtk_debug_flags & GTK_DEBUG_TEXT)
6132 _gtk_text_btree_check (tree);
6136 gtk_text_btree_unlink_segment (GtkTextBTree *tree,
6137 GtkTextLineSegment *seg,
6140 GtkTextLineSegment *prev;
6142 if (line->segments == seg)
6144 line->segments = seg->next;
6148 for (prev = line->segments; prev->next != seg;
6151 /* Empty loop body. */
6153 prev->next = seg->next;
6155 cleanup_line (line);
6156 segments_changed (tree);
6160 * This is here because it requires BTree internals, it logically
6161 * belongs in gtktextsegment.c
6166 *--------------------------------------------------------------
6168 * _gtk_toggle_segment_check_func --
6170 * This procedure is invoked to perform consistency checks
6171 * on toggle segments.
6177 * If a consistency problem is found the procedure g_errors.
6179 *--------------------------------------------------------------
6183 _gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6189 if (segPtr->byte_count != 0)
6191 g_error ("toggle_segment_check_func: segment had non-zero size");
6193 if (!segPtr->body.toggle.inNodeCounts)
6195 g_error ("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6197 needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6198 for (summary = line->parent->summary; ;
6199 summary = summary->next)
6201 if (summary == NULL)
6205 g_error ("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6212 if (summary->info == segPtr->body.toggle.info)
6216 g_error ("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6228 gtk_text_btree_node_view_check_consistency (GtkTextBTree *tree,
6229 GtkTextBTreeNode *node,
6239 while (view != NULL)
6241 if (view->view_id == nd->view_id)
6248 g_error ("Node has data for a view %p no longer attached to the tree",
6251 gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6252 &width, &height, &valid);
6253 if (nd->width != width ||
6254 nd->height != height ||
6255 !nd->valid != !valid)
6257 g_error ("Node aggregates for view %p are invalid:\n"
6258 "Are (%d,%d,%s), should be (%d,%d,%s)",
6260 nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6261 width, height, valid ? "TRUE" : "FALSE");
6266 gtk_text_btree_node_check_consistency (GtkTextBTree *tree,
6267 GtkTextBTreeNode *node)
6269 GtkTextBTreeNode *childnode;
6270 Summary *summary, *summary2;
6272 GtkTextLineSegment *segPtr;
6273 int num_children, num_lines, num_chars, toggle_count, min_children;
6274 GtkTextLineData *ld;
6277 if (node->parent != NULL)
6279 min_children = MIN_CHILDREN;
6281 else if (node->level > 0)
6288 if ((node->num_children < min_children)
6289 || (node->num_children > MAX_CHILDREN))
6291 g_error ("gtk_text_btree_node_check_consistency: bad child count (%d)",
6292 node->num_children);
6295 nd = node->node_data;
6298 gtk_text_btree_node_view_check_consistency (tree, node, nd);
6305 if (node->level == 0)
6307 for (line = node->children.line; line != NULL;
6310 if (line->parent != node)
6312 g_error ("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6314 if (line->segments == NULL)
6316 g_error ("gtk_text_btree_node_check_consistency: line has no segments");
6322 /* Just ensuring we don't segv while doing this loop */
6327 for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6329 if (segPtr->type->checkFunc != NULL)
6331 (*segPtr->type->checkFunc)(segPtr, line);
6333 if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6334 && (segPtr->next != NULL)
6335 && (segPtr->next->byte_count == 0)
6336 && (segPtr->next->type->leftGravity))
6338 g_error ("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6340 if ((segPtr->next == NULL)
6341 && (segPtr->type != >k_text_char_type))
6343 g_error ("gtk_text_btree_node_check_consistency: line ended with wrong type");
6346 num_chars += segPtr->char_count;
6355 for (childnode = node->children.node; childnode != NULL;
6356 childnode = childnode->next)
6358 if (childnode->parent != node)
6360 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6362 if (childnode->level != (node->level-1))
6364 g_error ("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6365 node->level, childnode->level);
6367 gtk_text_btree_node_check_consistency (tree, childnode);
6368 for (summary = childnode->summary; summary != NULL;
6369 summary = summary->next)
6371 for (summary2 = node->summary; ;
6372 summary2 = summary2->next)
6374 if (summary2 == NULL)
6376 if (summary->info->tag_root == node)
6380 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6381 summary->info->tag->name,
6382 "present in parent summaries");
6384 if (summary->info == summary2->info)
6391 num_lines += childnode->num_lines;
6392 num_chars += childnode->num_chars;
6395 if (num_children != node->num_children)
6397 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6398 num_children, node->num_children);
6400 if (num_lines != node->num_lines)
6402 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6403 num_lines, node->num_lines);
6405 if (num_chars != node->num_chars)
6407 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6408 num_chars, node->num_chars);
6411 for (summary = node->summary; summary != NULL;
6412 summary = summary->next)
6414 if (summary->info->toggle_count == summary->toggle_count)
6416 g_error ("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6417 summary->info->tag->name);
6420 if (node->level == 0)
6422 for (line = node->children.line; line != NULL;
6425 for (segPtr = line->segments; segPtr != NULL;
6426 segPtr = segPtr->next)
6428 if ((segPtr->type != >k_text_toggle_on_type)
6429 && (segPtr->type != >k_text_toggle_off_type))
6433 if (segPtr->body.toggle.info == summary->info)
6435 if (!segPtr->body.toggle.inNodeCounts)
6436 g_error ("Toggle segment not in the node counts");
6445 for (childnode = node->children.node;
6447 childnode = childnode->next)
6449 for (summary2 = childnode->summary;
6451 summary2 = summary2->next)
6453 if (summary2->info == summary->info)
6455 toggle_count += summary2->toggle_count;
6460 if (toggle_count != summary->toggle_count)
6462 g_error ("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6463 toggle_count, summary->toggle_count);
6465 for (summary2 = summary->next; summary2 != NULL;
6466 summary2 = summary2->next)
6468 if (summary2->info == summary->info)
6470 g_error ("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6471 summary->info->tag->name);
6478 listify_foreach (GtkTextTag *tag, gpointer user_data)
6480 GSList** listp = user_data;
6482 *listp = g_slist_prepend (*listp, tag);
6486 list_of_tags (GtkTextTagTable *table)
6488 GSList *list = NULL;
6490 gtk_text_tag_table_foreach (table, listify_foreach, &list);
6496 _gtk_text_btree_check (GtkTextBTree *tree)
6499 GtkTextBTreeNode *node;
6501 GtkTextLineSegment *seg;
6503 GSList *taglist = NULL;
6505 GtkTextTagInfo *info;
6508 * Make sure that the tag toggle counts and the tag root pointers are OK.
6510 for (taglist = list_of_tags (tree->table);
6511 taglist != NULL ; taglist = taglist->next)
6513 tag = taglist->data;
6514 info = gtk_text_btree_get_existing_tag_info (tree, tag);
6517 node = info->tag_root;
6520 if (info->toggle_count != 0)
6522 g_error ("_gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6523 tag->name, info->toggle_count);
6525 continue; /* no ranges for the tag */
6527 else if (info->toggle_count == 0)
6529 g_error ("_gtk_text_btree_check found root for \"%s\" with no toggles",
6532 else if (info->toggle_count & 1)
6534 g_error ("_gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6535 tag->name, info->toggle_count);
6537 for (summary = node->summary; summary != NULL;
6538 summary = summary->next)
6540 if (summary->info->tag == tag)
6542 g_error ("_gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6546 if (node->level > 0)
6548 for (node = node->children.node ; node != NULL ;
6551 for (summary = node->summary; summary != NULL;
6552 summary = summary->next)
6554 if (summary->info->tag == tag)
6556 count += summary->toggle_count;
6563 GtkTextLineSegmentClass * last = NULL;
6565 for (line = node->children.line ; line != NULL ;
6568 for (seg = line->segments; seg != NULL;
6571 if ((seg->type == >k_text_toggle_on_type ||
6572 seg->type == >k_text_toggle_off_type) &&
6573 seg->body.toggle.info->tag == tag)
6575 if (last == seg->type)
6576 g_error ("Two consecutive toggles on or off weren't merged");
6577 if (!seg->body.toggle.inNodeCounts)
6578 g_error ("Toggle segment not in the node counts");
6587 if (count != info->toggle_count)
6589 g_error ("_gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
6590 info->toggle_count, tag->name, count);
6595 g_slist_free (taglist);
6599 * Call a recursive procedure to do the main body of checks.
6602 node = tree->root_node;
6603 gtk_text_btree_node_check_consistency (tree, tree->root_node);
6606 * Make sure that there are at least two lines in the text and
6607 * that the last line has no characters except a newline.
6610 if (node->num_lines < 2)
6612 g_error ("_gtk_text_btree_check: less than 2 lines in tree");
6614 if (node->num_chars < 2)
6616 g_error ("_gtk_text_btree_check: less than 2 chars in tree");
6618 while (node->level > 0)
6620 node = node->children.node;
6621 while (node->next != NULL)
6626 line = node->children.line;
6627 while (line->next != NULL)
6631 seg = line->segments;
6632 while ((seg->type == >k_text_toggle_off_type)
6633 || (seg->type == >k_text_right_mark_type)
6634 || (seg->type == >k_text_left_mark_type))
6637 * It's OK to toggle a tag off in the last line, but
6638 * not to start a new range. It's also OK to have marks
6644 if (seg->type != >k_text_char_type)
6646 g_error ("_gtk_text_btree_check: last line has bogus segment type");
6648 if (seg->next != NULL)
6650 g_error ("_gtk_text_btree_check: last line has too many segments");
6652 if (seg->byte_count != 1)
6654 g_error ("_gtk_text_btree_check: last line has wrong # characters: %d",
6657 if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
6659 g_error ("_gtk_text_btree_check: last line had bad value: %s",
6664 void _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line);
6665 void _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment* seg);
6666 void _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent);
6667 void _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
6670 _gtk_text_btree_spew (GtkTextBTree *tree)
6675 printf ("%d lines in tree %p\n",
6676 _gtk_text_btree_line_count (tree), tree);
6678 line = _gtk_text_btree_get_line (tree, 0, &real_line);
6680 while (line != NULL)
6682 _gtk_text_btree_spew_line (tree, line);
6683 line = _gtk_text_line_next (line);
6686 printf ("=================== Tag information\n");
6691 list = tree->tag_infos;
6693 while (list != NULL)
6695 GtkTextTagInfo *info;
6699 printf (" tag `%s': root at %p, toggle count %d\n",
6700 info->tag->name, info->tag_root, info->toggle_count);
6702 list = g_slist_next (list);
6705 if (tree->tag_infos == NULL)
6707 printf (" (no tags in the tree)\n");
6711 printf ("=================== Tree nodes\n");
6714 _gtk_text_btree_spew_node (tree->root_node, 0);
6719 _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
6722 GtkTextLineSegment *seg;
6724 spaces = g_strnfill (indent, ' ');
6726 printf ("%sline %p chars %d bytes %d\n",
6728 _gtk_text_line_char_count (line),
6729 _gtk_text_line_byte_count (line));
6731 seg = line->segments;
6734 if (seg->type == >k_text_char_type)
6736 gchar* str = g_strndup (seg->body.chars, MIN (seg->byte_count, 10));
6741 if (*s == '\n' || *s == '\r')
6745 printf ("%s chars `%s'...\n", spaces, str);
6748 else if (seg->type == >k_text_right_mark_type)
6750 printf ("%s right mark `%s' visible: %d\n",
6752 seg->body.mark.name,
6753 seg->body.mark.visible);
6755 else if (seg->type == >k_text_left_mark_type)
6757 printf ("%s left mark `%s' visible: %d\n",
6759 seg->body.mark.name,
6760 seg->body.mark.visible);
6762 else if (seg->type == >k_text_toggle_on_type ||
6763 seg->type == >k_text_toggle_off_type)
6765 printf ("%s tag `%s' %s\n",
6766 spaces, seg->body.toggle.info->tag->name,
6767 seg->type == >k_text_toggle_off_type ? "off" : "on");
6777 _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent)
6780 GtkTextBTreeNode *iter;
6783 spaces = g_strnfill (indent, ' ');
6785 printf ("%snode %p level %d children %d lines %d chars %d\n",
6786 spaces, node, node->level,
6787 node->num_children, node->num_lines, node->num_chars);
6792 printf ("%s %d toggles of `%s' below this node\n",
6793 spaces, s->toggle_count, s->info->tag->name);
6799 if (node->level > 0)
6801 iter = node->children.node;
6802 while (iter != NULL)
6804 _gtk_text_btree_spew_node (iter, indent + 2);
6811 GtkTextLine *line = node->children.line;
6812 while (line != NULL)
6814 _gtk_text_btree_spew_line_short (line, indent + 2);
6822 _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line)
6824 GtkTextLineSegment * seg;
6826 printf ("%4d| line: %p parent: %p next: %p\n",
6827 _gtk_text_line_get_number (line), line, line->parent, line->next);
6829 seg = line->segments;
6833 _gtk_text_btree_spew_segment (tree, seg);
6839 _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment * seg)
6841 printf (" segment: %p type: %s bytes: %d chars: %d\n",
6842 seg, seg->type->name, seg->byte_count, seg->char_count);
6844 if (seg->type == >k_text_char_type)
6846 gchar* str = g_strndup (seg->body.chars, seg->byte_count);
6847 printf (" `%s'\n", str);
6850 else if (seg->type == >k_text_right_mark_type)
6852 printf (" right mark `%s' visible: %d not_deleteable: %d\n",
6853 seg->body.mark.name,
6854 seg->body.mark.visible,
6855 seg->body.mark.not_deleteable);
6857 else if (seg->type == >k_text_left_mark_type)
6859 printf (" left mark `%s' visible: %d not_deleteable: %d\n",
6860 seg->body.mark.name,
6861 seg->body.mark.visible,
6862 seg->body.mark.not_deleteable);
6864 else if (seg->type == >k_text_toggle_on_type ||
6865 seg->type == >k_text_toggle_off_type)
6867 printf (" tag `%s' priority %d\n",
6868 seg->body.toggle.info->tag->name,
6869 seg->body.toggle.info->tag->priority);