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 void gtk_text_btree_node_free_empty (GtkTextBTree *tree,
284 GtkTextBTreeNode *node);
285 static NodeData * gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node,
287 static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
289 static void gtk_text_btree_node_get_size (GtkTextBTreeNode *node,
293 static GtkTextBTreeNode * gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
294 GtkTextBTreeNode *node2);
295 static void get_tree_bounds (GtkTextBTree *tree,
298 static void tag_changed_cb (GtkTextTagTable *table,
300 gboolean size_changed,
302 static void tag_removed_cb (GtkTextTagTable *table,
305 static void cleanup_line (GtkTextLine *line);
306 static void recompute_node_counts (GtkTextBTree *tree,
307 GtkTextBTreeNode *node);
308 static void inc_count (GtkTextTag *tag,
310 TagInfo *tagInfoPtr);
312 static void summary_destroy (Summary *summary);
314 static void gtk_text_btree_link_segment (GtkTextLineSegment *seg,
315 const GtkTextIter *iter);
316 static void gtk_text_btree_unlink_segment (GtkTextBTree *tree,
317 GtkTextLineSegment *seg,
321 static GtkTextTagInfo *gtk_text_btree_get_tag_info (GtkTextBTree *tree,
323 static GtkTextTagInfo *gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
325 static void gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
328 static void redisplay_region (GtkTextBTree *tree,
329 const GtkTextIter *start,
330 const GtkTextIter *end);
332 /* Inline thingies */
335 segments_changed (GtkTextBTree *tree)
337 tree->segments_changed_stamp += 1;
341 chars_changed (GtkTextBTree *tree)
343 tree->chars_changed_stamp += 1;
351 _gtk_text_btree_new (GtkTextTagTable *table,
352 GtkTextBuffer *buffer)
355 GtkTextBTreeNode *root_node;
356 GtkTextLine *line, *line2;
358 g_return_val_if_fail (GTK_IS_TEXT_TAG_TABLE (table), NULL);
359 g_return_val_if_fail (GTK_IS_TEXT_BUFFER (buffer), NULL);
362 * The tree will initially have two empty lines. The second line
363 * isn't actually part of the tree's contents, but its presence
364 * makes several operations easier. The tree will have one GtkTextBTreeNode,
365 * which is also the root of the tree.
368 /* Create the root node. */
370 root_node = gtk_text_btree_node_new ();
372 line = gtk_text_line_new ();
373 line2 = gtk_text_line_new ();
375 root_node->parent = NULL;
376 root_node->next = NULL;
377 root_node->summary = NULL;
378 root_node->level = 0;
379 root_node->children.line = line;
380 root_node->num_children = 2;
381 root_node->num_lines = 2;
382 root_node->num_chars = 2;
384 line->parent = root_node;
387 line->segments = _gtk_char_segment_new ("\n", 1);
389 line2->parent = root_node;
391 line2->segments = _gtk_char_segment_new ("\n", 1);
393 /* Create the tree itself */
395 tree = g_new0(GtkTextBTree, 1);
396 tree->root_node = root_node;
400 /* Set these to values that are unlikely to be found
401 * in random memory garbage, and also avoid
402 * duplicates between tree instances.
404 tree->chars_changed_stamp = g_random_int ();
405 tree->segments_changed_stamp = g_random_int ();
407 tree->end_iter_line_stamp = tree->chars_changed_stamp - 1;
408 tree->end_iter_line = NULL;
410 g_object_ref (G_OBJECT (tree->table));
412 tree->tag_changed_handler = g_signal_connect (G_OBJECT (tree->table),
414 G_CALLBACK (tag_changed_cb),
417 tree->tag_removed_handler = g_signal_connect (G_OBJECT (tree->table),
419 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--;
739 gtk_text_btree_node_free_empty (tree, curnode);
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));
1580 g_return_if_fail (tag->table == _gtk_text_iter_get_btree (start_orig)->table);
1583 printf ("%s tag %s from %d to %d\n",
1584 add ? "Adding" : "Removing",
1586 gtk_text_buffer_get_offset (start_orig),
1587 gtk_text_buffer_get_offset (end_orig));
1590 if (gtk_text_iter_equal (start_orig, end_orig))
1593 start = *start_orig;
1596 gtk_text_iter_order (&start, &end);
1598 tree = _gtk_text_iter_get_btree (&start);
1600 queue_tag_redisplay (tree, tag, &start, &end);
1602 info = gtk_text_btree_get_tag_info (tree, tag);
1604 start_line = _gtk_text_iter_get_text_line (&start);
1605 end_line = _gtk_text_iter_get_text_line (&end);
1607 /* Find all tag toggles in the region; we are going to delete them.
1608 We need to find them in advance, because
1609 forward_find_tag_toggle () won't work once we start playing around
1611 stack = iter_stack_new ();
1614 /* forward_to_tag_toggle() skips a toggle at the start iterator,
1615 * which is deliberate - we don't want to delete a toggle at the
1618 while (gtk_text_iter_forward_to_tag_toggle (&iter, tag))
1620 if (gtk_text_iter_compare (&iter, &end) >= 0)
1623 iter_stack_push (stack, &iter);
1626 /* We need to traverse the toggles in order. */
1627 iter_stack_invert (stack);
1630 * See whether the tag is present at the start of the range. If
1631 * the state doesn't already match what we want then add a toggle
1635 toggled_on = gtk_text_iter_has_tag (&start, tag);
1636 if ( (add && !toggled_on) ||
1637 (!add && toggled_on) )
1639 /* This could create a second toggle at the start position;
1640 cleanup_line () will remove it if so. */
1641 seg = _gtk_toggle_segment_new (info, add);
1643 prev = gtk_text_line_segment_split (&start);
1646 seg->next = start_line->segments;
1647 start_line->segments = seg;
1651 seg->next = prev->next;
1655 /* cleanup_line adds the new toggle to the node counts. */
1657 printf ("added toggle at start\n");
1659 /* we should probably call segments_changed, but in theory
1660 any still-cached segments in the iters we are about to
1661 use are still valid, since they're in front
1667 * Scan the range of characters and delete any internal tag
1668 * transitions. Keep track of what the old state was at the end
1669 * of the range, and add a toggle there if it's needed.
1673 cleanupline = start_line;
1674 while (iter_stack_pop (stack, &iter))
1676 GtkTextLineSegment *indexable_seg;
1679 line = _gtk_text_iter_get_text_line (&iter);
1680 seg = _gtk_text_iter_get_any_segment (&iter);
1681 indexable_seg = _gtk_text_iter_get_indexable_segment (&iter);
1683 g_assert (seg != NULL);
1684 g_assert (indexable_seg != NULL);
1685 g_assert (seg != indexable_seg);
1687 prev = line->segments;
1689 /* Find the segment that actually toggles this tag. */
1690 while (seg != indexable_seg)
1692 g_assert (seg != NULL);
1693 g_assert (indexable_seg != NULL);
1694 g_assert (seg != indexable_seg);
1696 if ( (seg->type == >k_text_toggle_on_type ||
1697 seg->type == >k_text_toggle_off_type) &&
1698 (seg->body.toggle.info == info) )
1704 g_assert (seg != NULL);
1705 g_assert (indexable_seg != NULL);
1707 g_assert (seg != indexable_seg); /* If this happens, then
1708 forward_to_tag_toggle was
1710 g_assert (seg->body.toggle.info->tag == tag);
1712 /* If this happens, when previously tagging we didn't merge
1713 overlapping tags. */
1714 g_assert ( (toggled_on && seg->type == >k_text_toggle_off_type) ||
1715 (!toggled_on && seg->type == >k_text_toggle_on_type) );
1717 toggled_on = !toggled_on;
1720 printf ("deleting %s toggle\n",
1721 seg->type == >k_text_toggle_on_type ? "on" : "off");
1723 /* Remove toggle segment from the list. */
1726 line->segments = seg->next;
1730 while (prev->next != seg)
1734 prev->next = seg->next;
1737 /* Inform iterators we've hosed them. This actually reflects a
1738 bit of inefficiency; if you have the same tag toggled on and
1739 off a lot in a single line, we keep having the rescan from
1740 the front of the line. Of course we have to do that to get
1741 "prev" anyway, but here we are doing it an additional
1743 segments_changed (tree);
1745 /* Update node counts */
1746 if (seg->body.toggle.inNodeCounts)
1748 _gtk_change_node_toggle_count (line->parent,
1750 seg->body.toggle.inNodeCounts = FALSE;
1755 /* We only clean up lines when we're done with them, saves some
1756 gratuitous line-segment-traversals */
1758 if (cleanupline != line)
1760 cleanup_line (cleanupline);
1765 iter_stack_free (stack);
1767 /* toggled_on now reflects the toggle state _just before_ the
1768 end iterator. The end iterator could already have a toggle
1769 on or a toggle off. */
1770 if ( (add && !toggled_on) ||
1771 (!add && toggled_on) )
1773 /* This could create a second toggle at the start position;
1774 cleanup_line () will remove it if so. */
1776 seg = _gtk_toggle_segment_new (info, !add);
1778 prev = gtk_text_line_segment_split (&end);
1781 seg->next = end_line->segments;
1782 end_line->segments = seg;
1786 seg->next = prev->next;
1789 /* cleanup_line adds the new toggle to the node counts. */
1790 g_assert (seg->body.toggle.inNodeCounts == FALSE);
1792 printf ("added toggle at end\n");
1797 * Cleanup cleanupline and the last line of the range, if
1798 * these are different.
1801 cleanup_line (cleanupline);
1802 if (cleanupline != end_line)
1804 cleanup_line (end_line);
1807 segments_changed (tree);
1809 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1810 _gtk_text_btree_check (tree);
1819 _gtk_text_btree_get_line (GtkTextBTree *tree,
1821 gint *real_line_number)
1823 GtkTextBTreeNode *node;
1828 line_count = _gtk_text_btree_line_count (tree);
1830 if (line_number < 0)
1832 line_number = line_count;
1834 else if (line_number > line_count)
1836 line_number = line_count;
1839 if (real_line_number)
1840 *real_line_number = line_number;
1842 node = tree->root_node;
1843 lines_left = line_number;
1846 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1850 while (node->level != 0)
1852 for (node = node->children.node;
1853 node->num_lines <= lines_left;
1859 g_error ("gtk_text_btree_find_line ran out of GtkTextBTreeNodes");
1862 lines_left -= node->num_lines;
1867 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1870 for (line = node->children.line; lines_left > 0;
1876 g_error ("gtk_text_btree_find_line ran out of lines");
1885 _gtk_text_btree_get_line_at_char (GtkTextBTree *tree,
1887 gint *line_start_index,
1888 gint *real_char_index)
1890 GtkTextBTreeNode *node;
1892 GtkTextLineSegment *seg;
1897 node = tree->root_node;
1899 /* Clamp to valid indexes (-1 is magic for "highest index") */
1900 if (char_index < 0 || char_index >= node->num_chars)
1902 char_index = node->num_chars - 1;
1905 *real_char_index = char_index;
1908 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1912 chars_left = char_index;
1913 while (node->level != 0)
1915 for (node = node->children.node;
1916 chars_left >= node->num_chars;
1919 chars_left -= node->num_chars;
1921 g_assert (chars_left >= 0);
1925 if (chars_left == 0)
1927 /* Start of a line */
1929 *line_start_index = char_index;
1930 return node->children.line;
1934 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1940 for (line = node->children.line; line != NULL; line = line->next)
1942 seg = line->segments;
1945 if (chars_in_line + seg->char_count > chars_left)
1946 goto found; /* found our line/segment */
1948 chars_in_line += seg->char_count;
1953 chars_left -= chars_in_line;
1961 g_assert (line != NULL); /* hosage, ran out of lines */
1962 g_assert (seg != NULL);
1964 *line_start_index = char_index - chars_left;
1969 _gtk_text_btree_get_tags (const GtkTextIter *iter,
1972 GtkTextBTreeNode *node;
1973 GtkTextLine *siblingline;
1974 GtkTextLineSegment *seg;
1975 int src, dst, index;
1981 #define NUM_TAG_INFOS 10
1983 line = _gtk_text_iter_get_text_line (iter);
1984 tree = _gtk_text_iter_get_btree (iter);
1985 byte_index = gtk_text_iter_get_line_index (iter);
1987 tagInfo.numTags = 0;
1988 tagInfo.arraySize = NUM_TAG_INFOS;
1989 tagInfo.tags = g_new (GtkTextTag*, NUM_TAG_INFOS);
1990 tagInfo.counts = g_new (int, NUM_TAG_INFOS);
1993 * Record tag toggles within the line of indexPtr but preceding
1994 * indexPtr. Note that if this loop segfaults, your
1995 * byte_index probably points past the sum of all
1996 * seg->byte_count */
1998 for (index = 0, seg = line->segments;
1999 (index + seg->byte_count) <= byte_index;
2000 index += seg->byte_count, seg = seg->next)
2002 if ((seg->type == >k_text_toggle_on_type)
2003 || (seg->type == >k_text_toggle_off_type))
2005 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2010 * Record toggles for tags in lines that are predecessors of
2011 * line but under the same level-0 GtkTextBTreeNode.
2014 for (siblingline = line->parent->children.line;
2015 siblingline != line;
2016 siblingline = siblingline->next)
2018 for (seg = siblingline->segments; seg != NULL;
2021 if ((seg->type == >k_text_toggle_on_type)
2022 || (seg->type == >k_text_toggle_off_type))
2024 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2030 * For each GtkTextBTreeNode in the ancestry of this line, record tag
2031 * toggles for all siblings that precede that GtkTextBTreeNode.
2034 for (node = line->parent; node->parent != NULL;
2035 node = node->parent)
2037 GtkTextBTreeNode *siblingPtr;
2040 for (siblingPtr = node->parent->children.node;
2041 siblingPtr != node; siblingPtr = siblingPtr->next)
2043 for (summary = siblingPtr->summary; summary != NULL;
2044 summary = summary->next)
2046 if (summary->toggle_count & 1)
2048 inc_count (summary->info->tag, summary->toggle_count,
2056 * Go through the tag information and squash out all of the tags
2057 * that have even toggle counts (these tags exist before the point
2058 * of interest, but not at the desired character itself).
2061 for (src = 0, dst = 0; src < tagInfo.numTags; src++)
2063 if (tagInfo.counts[src] & 1)
2065 g_assert (GTK_IS_TEXT_TAG (tagInfo.tags[src]));
2066 tagInfo.tags[dst] = tagInfo.tags[src];
2072 g_free (tagInfo.counts);
2075 g_free (tagInfo.tags);
2078 return tagInfo.tags;
2082 copy_segment (GString *string,
2083 gboolean include_hidden,
2084 gboolean include_nonchars,
2085 const GtkTextIter *start,
2086 const GtkTextIter *end)
2088 GtkTextLineSegment *end_seg;
2089 GtkTextLineSegment *seg;
2091 if (gtk_text_iter_equal (start, end))
2094 seg = _gtk_text_iter_get_indexable_segment (start);
2095 end_seg = _gtk_text_iter_get_indexable_segment (end);
2097 if (seg->type == >k_text_char_type)
2099 gboolean copy = TRUE;
2100 gint copy_bytes = 0;
2101 gint copy_start = 0;
2103 /* Don't copy if we're invisible; segments are invisible/not
2104 as a whole, no need to check each char */
2105 if (!include_hidden &&
2106 _gtk_text_btree_char_is_invisible (start))
2109 /* printf (" <invisible>\n"); */
2112 copy_start = _gtk_text_iter_get_segment_byte (start);
2116 /* End is in the same segment; need to copy fewer bytes. */
2117 gint end_byte = _gtk_text_iter_get_segment_byte (end);
2119 copy_bytes = end_byte - copy_start;
2122 copy_bytes = seg->byte_count - copy_start;
2124 g_assert (copy_bytes != 0); /* Due to iter equality check at
2125 front of this function. */
2129 g_assert ((copy_start + copy_bytes) <= seg->byte_count);
2131 g_string_append_len (string,
2132 seg->body.chars + copy_start,
2136 /* printf (" :%s\n", string->str); */
2138 else if (seg->type == >k_text_pixbuf_type ||
2139 seg->type == >k_text_child_type)
2141 gboolean copy = TRUE;
2143 if (!include_nonchars)
2147 else if (!include_hidden &&
2148 _gtk_text_btree_char_is_invisible (start))
2155 g_string_append_len (string,
2156 gtk_text_unknown_char_utf8,
2164 _gtk_text_btree_get_text (const GtkTextIter *start_orig,
2165 const GtkTextIter *end_orig,
2166 gboolean include_hidden,
2167 gboolean include_nonchars)
2169 GtkTextLineSegment *seg;
2170 GtkTextLineSegment *end_seg;
2178 g_return_val_if_fail (start_orig != NULL, NULL);
2179 g_return_val_if_fail (end_orig != NULL, NULL);
2180 g_return_val_if_fail (_gtk_text_iter_get_btree (start_orig) ==
2181 _gtk_text_iter_get_btree (end_orig), NULL);
2183 start = *start_orig;
2186 gtk_text_iter_order (&start, &end);
2188 retval = g_string_new ("");
2190 tree = _gtk_text_iter_get_btree (&start);
2192 end_seg = _gtk_text_iter_get_indexable_segment (&end);
2194 seg = _gtk_text_iter_get_indexable_segment (&iter);
2195 while (seg != end_seg)
2197 copy_segment (retval, include_hidden, include_nonchars,
2200 _gtk_text_iter_forward_indexable_segment (&iter);
2202 seg = _gtk_text_iter_get_indexable_segment (&iter);
2205 copy_segment (retval, include_hidden, include_nonchars, &iter, &end);
2208 g_string_free (retval, FALSE);
2213 _gtk_text_btree_line_count (GtkTextBTree *tree)
2215 /* Subtract bogus line at the end; we return a count
2217 return tree->root_node->num_lines - 1;
2221 _gtk_text_btree_char_count (GtkTextBTree *tree)
2223 /* Exclude newline in bogus last line */
2224 return tree->root_node->num_chars - 1;
2227 #define LOTSA_TAGS 1000
2229 _gtk_text_btree_char_is_invisible (const GtkTextIter *iter)
2231 gboolean invisible = FALSE; /* if nobody says otherwise, it's visible */
2233 int deftagCnts[LOTSA_TAGS];
2234 int *tagCnts = deftagCnts;
2235 GtkTextTag *deftags[LOTSA_TAGS];
2236 GtkTextTag **tags = deftags;
2238 GtkTextBTreeNode *node;
2239 GtkTextLine *siblingline;
2240 GtkTextLineSegment *seg;
2247 line = _gtk_text_iter_get_text_line (iter);
2248 tree = _gtk_text_iter_get_btree (iter);
2249 byte_index = gtk_text_iter_get_line_index (iter);
2251 numTags = gtk_text_tag_table_get_size (tree->table);
2253 /* almost always avoid malloc, so stay out of system calls */
2254 if (LOTSA_TAGS < numTags)
2256 tagCnts = g_new (int, numTags);
2257 tags = g_new (GtkTextTag*, numTags);
2260 for (i=0; i<numTags; i++)
2266 * Record tag toggles within the line of indexPtr but preceding
2270 for (index = 0, seg = line->segments;
2271 (index + seg->byte_count) <= byte_index; /* segfault here means invalid index */
2272 index += seg->byte_count, seg = seg->next)
2274 if ((seg->type == >k_text_toggle_on_type)
2275 || (seg->type == >k_text_toggle_off_type))
2277 tag = seg->body.toggle.info->tag;
2278 if (tag->invisible_set && tag->values->invisible)
2280 tags[tag->priority] = tag;
2281 tagCnts[tag->priority]++;
2287 * Record toggles for tags in lines that are predecessors of
2288 * line but under the same level-0 GtkTextBTreeNode.
2291 for (siblingline = line->parent->children.line;
2292 siblingline != line;
2293 siblingline = siblingline->next)
2295 for (seg = siblingline->segments; seg != NULL;
2298 if ((seg->type == >k_text_toggle_on_type)
2299 || (seg->type == >k_text_toggle_off_type))
2301 tag = seg->body.toggle.info->tag;
2302 if (tag->invisible_set && tag->values->invisible)
2304 tags[tag->priority] = tag;
2305 tagCnts[tag->priority]++;
2312 * For each GtkTextBTreeNode in the ancestry of this line, record tag toggles
2313 * for all siblings that precede that GtkTextBTreeNode.
2316 for (node = line->parent; node->parent != NULL;
2317 node = node->parent)
2319 GtkTextBTreeNode *siblingPtr;
2322 for (siblingPtr = node->parent->children.node;
2323 siblingPtr != node; siblingPtr = siblingPtr->next)
2325 for (summary = siblingPtr->summary; summary != NULL;
2326 summary = summary->next)
2328 if (summary->toggle_count & 1)
2330 tag = summary->info->tag;
2331 if (tag->invisible_set && tag->values->invisible)
2333 tags[tag->priority] = tag;
2334 tagCnts[tag->priority] += summary->toggle_count;
2342 * Now traverse from highest priority to lowest,
2343 * take invisible value from first odd count (= on)
2346 for (i = numTags-1; i >=0; i--)
2350 /* FIXME not sure this should be if 0 */
2352 #ifndef ALWAYS_SHOW_SELECTION
2353 /* who would make the selection invisible? */
2354 if ((tag == tkxt->seltag)
2355 && !(tkxt->flags & GOT_FOCUS))
2361 invisible = tags[i]->values->invisible;
2366 if (LOTSA_TAGS < numTags)
2381 redisplay_region (GtkTextBTree *tree,
2382 const GtkTextIter *start,
2383 const GtkTextIter *end)
2386 GtkTextLine *start_line, *end_line;
2388 if (gtk_text_iter_compare (start, end) > 0)
2390 const GtkTextIter *tmp = start;
2395 start_line = _gtk_text_iter_get_text_line (start);
2396 end_line = _gtk_text_iter_get_text_line (end);
2399 while (view != NULL)
2401 gint start_y, end_y;
2402 GtkTextLineData *ld;
2404 start_y = _gtk_text_btree_find_line_top (tree, start_line, view->view_id);
2406 if (end_line == start_line)
2409 end_y = _gtk_text_btree_find_line_top (tree, end_line, view->view_id);
2411 ld = _gtk_text_line_get_data (end_line, view->view_id);
2413 end_y += ld->height;
2415 gtk_text_layout_changed (view->layout, start_y,
2424 redisplay_mark (GtkTextLineSegment *mark)
2429 _gtk_text_btree_get_iter_at_mark (mark->body.mark.tree,
2431 mark->body.mark.obj);
2434 gtk_text_iter_forward_char (&end);
2436 _gtk_text_btree_invalidate_region (mark->body.mark.tree,
2441 redisplay_mark_if_visible (GtkTextLineSegment *mark)
2443 if (!mark->body.mark.visible)
2446 redisplay_mark (mark);
2450 ensure_not_off_end (GtkTextBTree *tree,
2451 GtkTextLineSegment *mark,
2454 if (gtk_text_iter_get_line (iter) ==
2455 _gtk_text_btree_line_count (tree))
2456 gtk_text_iter_backward_char (iter);
2459 static GtkTextLineSegment*
2460 real_set_mark (GtkTextBTree *tree,
2461 GtkTextMark *existing_mark,
2463 gboolean left_gravity,
2464 const GtkTextIter *where,
2465 gboolean should_exist,
2466 gboolean redraw_selections)
2468 GtkTextLineSegment *mark;
2471 g_return_val_if_fail (tree != NULL, NULL);
2472 g_return_val_if_fail (where != NULL, NULL);
2473 g_return_val_if_fail (_gtk_text_iter_get_btree (where) == tree, NULL);
2476 mark = existing_mark->segment;
2477 else if (name != NULL)
2478 mark = g_hash_table_lookup (tree->mark_table,
2483 if (should_exist && mark == NULL)
2485 g_warning ("No mark `%s' exists!", name);
2489 /* OK if !should_exist and it does already exist, in that case
2495 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2496 _gtk_text_iter_check (&iter);
2500 if (redraw_selections &&
2501 (mark == tree->insert_mark->segment ||
2502 mark == tree->selection_bound_mark->segment))
2504 GtkTextIter old_pos;
2506 _gtk_text_btree_get_iter_at_mark (tree, &old_pos,
2507 mark->body.mark.obj);
2508 redisplay_region (tree, &old_pos, where);
2512 * don't let visible marks be after the final newline of the
2516 if (mark->body.mark.visible)
2518 ensure_not_off_end (tree, mark, &iter);
2521 /* Redraw the mark's old location. */
2522 redisplay_mark_if_visible (mark);
2524 /* Unlink mark from its current location.
2525 This could hose our iterator... */
2526 gtk_text_btree_unlink_segment (tree, mark,
2527 mark->body.mark.line);
2528 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2529 g_assert (mark->body.mark.line == _gtk_text_iter_get_text_line (&iter));
2531 segments_changed (tree); /* make sure the iterator recomputes its
2536 mark = _gtk_mark_segment_new (tree,
2540 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2542 if (mark->body.mark.name)
2543 g_hash_table_insert (tree->mark_table,
2544 mark->body.mark.name,
2548 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2549 _gtk_text_iter_check (&iter);
2551 /* Link mark into new location */
2552 gtk_text_btree_link_segment (mark, &iter);
2554 /* Invalidate some iterators. */
2555 segments_changed (tree);
2558 * update the screen at the mark's new location.
2561 redisplay_mark_if_visible (mark);
2563 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2564 _gtk_text_iter_check (&iter);
2566 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2567 _gtk_text_btree_check (tree);
2574 _gtk_text_btree_set_mark (GtkTextBTree *tree,
2575 GtkTextMark *existing_mark,
2577 gboolean left_gravity,
2578 const GtkTextIter *iter,
2579 gboolean should_exist)
2581 GtkTextLineSegment *seg;
2583 seg = real_set_mark (tree, existing_mark,
2584 name, left_gravity, iter, should_exist,
2587 return seg ? seg->body.mark.obj : NULL;
2591 _gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2595 GtkTextIter tmp_start, tmp_end;
2597 _gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2599 _gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2600 tree->selection_bound_mark);
2602 if (gtk_text_iter_equal (&tmp_start, &tmp_end))
2614 gtk_text_iter_order (&tmp_start, &tmp_end);
2627 _gtk_text_btree_place_cursor (GtkTextBTree *tree,
2628 const GtkTextIter *iter)
2630 GtkTextIter start, end;
2632 if (_gtk_text_btree_get_selection_bounds (tree, &start, &end))
2633 redisplay_region (tree, &start, &end);
2635 /* Move insert AND selection_bound before we redisplay */
2636 real_set_mark (tree, tree->insert_mark,
2637 "insert", FALSE, iter, TRUE, FALSE);
2638 real_set_mark (tree, tree->selection_bound_mark,
2639 "selection_bound", FALSE, iter, TRUE, FALSE);
2643 _gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2648 g_return_if_fail (tree != NULL);
2649 g_return_if_fail (name != NULL);
2651 mark = g_hash_table_lookup (tree->mark_table,
2654 _gtk_text_btree_remove_mark (tree, mark);
2658 _gtk_text_btree_remove_mark (GtkTextBTree *tree,
2661 GtkTextLineSegment *segment;
2663 g_return_if_fail (mark != NULL);
2664 g_return_if_fail (tree != NULL);
2666 segment = mark->segment;
2668 if (segment->body.mark.not_deleteable)
2670 g_warning ("Can't delete special mark `%s'", segment->body.mark.name);
2674 /* This calls cleanup_line and segments_changed */
2675 gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2677 if (segment->body.mark.name)
2678 g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2680 /* Remove the ref on the mark that belonged to the segment. */
2681 g_object_unref (G_OBJECT (mark));
2683 segment->body.mark.tree = NULL;
2684 segment->body.mark.line = NULL;
2688 _gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2689 GtkTextMark *segment)
2691 return segment == tree->insert_mark;
2695 _gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2696 GtkTextMark *segment)
2698 return segment == tree->selection_bound_mark;
2702 _gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2705 GtkTextLineSegment *seg;
2707 g_return_val_if_fail (tree != NULL, NULL);
2708 g_return_val_if_fail (name != NULL, NULL);
2710 seg = g_hash_table_lookup (tree->mark_table, name);
2712 return seg ? seg->body.mark.obj : NULL;
2716 * gtk_text_mark_set_visible:
2717 * @mark: a #GtkTextMark
2718 * @setting: visibility of mark
2720 * Sets the visibility of @mark; the insertion point is normally
2721 * visible, i.e. you can see it as a vertical bar. Also, the text
2722 * widget uses a visible mark to indicate where a drop will occur when
2723 * dragging-and-dropping text. Most other marks are not visible.
2724 * Marks are not visible by default.
2728 gtk_text_mark_set_visible (GtkTextMark *mark,
2731 GtkTextLineSegment *seg;
2733 g_return_if_fail (mark != NULL);
2735 seg = mark->segment;
2737 if (seg->body.mark.visible == setting)
2741 seg->body.mark.visible = setting;
2743 redisplay_mark (seg);
2748 _gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
2751 GtkTextBTreeNode *node;
2752 GtkTextTagInfo *info;
2754 g_return_val_if_fail (tree != NULL, NULL);
2758 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2763 if (info->tag_root == NULL)
2766 node = info->tag_root;
2768 /* We know the tag root has instances of the given
2771 continue_outer_loop:
2772 g_assert (node != NULL);
2773 while (node->level > 0)
2775 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2776 node = node->children.node;
2777 while (node != NULL)
2779 if (gtk_text_btree_node_has_tag (node, tag))
2780 goto continue_outer_loop;
2784 g_assert (node != NULL);
2787 g_assert (node != NULL); /* The tag summaries said some node had
2790 g_assert (node->level == 0);
2792 return node->children.line;
2796 /* Looking for any tag at all (tag == NULL).
2797 Unfortunately this can't be done in a simple and efficient way
2798 right now; so I'm just going to return the
2799 first line in the btree. FIXME */
2800 return _gtk_text_btree_get_line (tree, 0, NULL);
2805 _gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
2808 GtkTextBTreeNode *node;
2809 GtkTextBTreeNode *last_node;
2811 GtkTextTagInfo *info;
2813 g_return_val_if_fail (tree != NULL, NULL);
2817 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2819 if (info->tag_root == NULL)
2822 node = info->tag_root;
2823 /* We know the tag root has instances of the given
2826 while (node->level > 0)
2828 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2830 node = node->children.node;
2831 while (node != NULL)
2833 if (gtk_text_btree_node_has_tag (node, tag))
2841 g_assert (node != NULL); /* The tag summaries said some node had
2844 g_assert (node->level == 0);
2846 /* Find the last line in this node */
2847 line = node->children.line;
2848 while (line->next != NULL)
2855 /* This search can't be done efficiently at the moment,
2856 at least not without complexity.
2857 So, we just return the last line.
2859 return _gtk_text_btree_get_line (tree, -1, NULL);
2869 _gtk_text_line_get_number (GtkTextLine *line)
2872 GtkTextBTreeNode *node, *parent, *node2;
2876 * First count how many lines precede this one in its level-0
2880 node = line->parent;
2882 for (line2 = node->children.line; line2 != line;
2883 line2 = line2->next)
2887 g_error ("gtk_text_btree_line_number couldn't find line");
2893 * Now work up through the levels of the tree one at a time,
2894 * counting how many lines are in GtkTextBTreeNodes preceding the current
2898 for (parent = node->parent ; parent != NULL;
2899 node = parent, parent = parent->parent)
2901 for (node2 = parent->children.node; node2 != node;
2902 node2 = node2->next)
2906 g_error ("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
2908 index += node2->num_lines;
2914 static GtkTextLineSegment*
2915 find_toggle_segment_before_char (GtkTextLine *line,
2919 GtkTextLineSegment *seg;
2920 GtkTextLineSegment *toggle_seg;
2925 seg = line->segments;
2926 while ( (index + seg->char_count) <= char_in_line )
2928 if (((seg->type == >k_text_toggle_on_type)
2929 || (seg->type == >k_text_toggle_off_type))
2930 && (seg->body.toggle.info->tag == tag))
2933 index += seg->char_count;
2940 static GtkTextLineSegment*
2941 find_toggle_segment_before_byte (GtkTextLine *line,
2945 GtkTextLineSegment *seg;
2946 GtkTextLineSegment *toggle_seg;
2951 seg = line->segments;
2952 while ( (index + seg->byte_count) <= byte_in_line )
2954 if (((seg->type == >k_text_toggle_on_type)
2955 || (seg->type == >k_text_toggle_off_type))
2956 && (seg->body.toggle.info->tag == tag))
2959 index += seg->byte_count;
2967 find_toggle_outside_current_line (GtkTextLine *line,
2971 GtkTextBTreeNode *node;
2972 GtkTextLine *sibling_line;
2973 GtkTextLineSegment *seg;
2974 GtkTextLineSegment *toggle_seg;
2976 GtkTextTagInfo *info = NULL;
2979 * No toggle in this line. Look for toggles for the tag in lines
2980 * that are predecessors of line but under the same
2981 * level-0 GtkTextBTreeNode.
2984 sibling_line = line->parent->children.line;
2985 while (sibling_line != line)
2987 seg = sibling_line->segments;
2990 if (((seg->type == >k_text_toggle_on_type)
2991 || (seg->type == >k_text_toggle_off_type))
2992 && (seg->body.toggle.info->tag == tag))
2998 sibling_line = sibling_line->next;
3001 if (toggle_seg != NULL)
3002 return (toggle_seg->type == >k_text_toggle_on_type);
3005 * No toggle in this GtkTextBTreeNode. Scan upwards through the ancestors of
3006 * this GtkTextBTreeNode, counting the number of toggles of the given tag in
3007 * siblings that precede that GtkTextBTreeNode.
3010 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3016 node = line->parent;
3017 while (node->parent != NULL)
3019 GtkTextBTreeNode *sibling_node;
3021 sibling_node = node->parent->children.node;
3022 while (sibling_node != node)
3026 summary = sibling_node->summary;
3027 while (summary != NULL)
3029 if (summary->info == info)
3030 toggles += summary->toggle_count;
3032 summary = summary->next;
3035 sibling_node = sibling_node->next;
3038 if (node == info->tag_root)
3041 node = node->parent;
3045 * An odd number of toggles means that the tag is present at the
3049 return (toggles & 1) != 0;
3052 /* FIXME this function is far too slow, for no good reason. */
3054 _gtk_text_line_char_has_tag (GtkTextLine *line,
3059 GtkTextLineSegment *toggle_seg;
3061 g_return_val_if_fail (line != NULL, FALSE);
3064 * Check for toggles for the tag in the line but before
3065 * the char. If there is one, its type indicates whether or
3066 * not the character is tagged.
3069 toggle_seg = find_toggle_segment_before_char (line, char_in_line, tag);
3071 if (toggle_seg != NULL)
3072 return (toggle_seg->type == >k_text_toggle_on_type);
3074 return find_toggle_outside_current_line (line, tree, tag);
3078 _gtk_text_line_byte_has_tag (GtkTextLine *line,
3083 GtkTextLineSegment *toggle_seg;
3085 g_return_val_if_fail (line != NULL, FALSE);
3088 * Check for toggles for the tag in the line but before
3089 * the char. If there is one, its type indicates whether or
3090 * not the character is tagged.
3093 toggle_seg = find_toggle_segment_before_byte (line, byte_in_line, tag);
3095 if (toggle_seg != NULL)
3096 return (toggle_seg->type == >k_text_toggle_on_type);
3098 return find_toggle_outside_current_line (line, tree, tag);
3102 _gtk_text_line_is_last (GtkTextLine *line,
3105 return line == get_last_line (tree);
3109 _gtk_text_line_next (GtkTextLine *line)
3111 GtkTextBTreeNode *node;
3113 if (line->next != NULL)
3118 * This was the last line associated with the particular parent
3119 * GtkTextBTreeNode. Search up the tree for the next GtkTextBTreeNode,
3120 * then search down from that GtkTextBTreeNode to find the first
3124 node = line->parent;
3125 while (node != NULL && node->next == NULL)
3126 node = node->parent;
3132 while (node->level > 0)
3134 node = node->children.node;
3137 g_assert (node->children.line != line);
3139 return node->children.line;
3144 _gtk_text_line_previous (GtkTextLine *line)
3146 GtkTextBTreeNode *node;
3147 GtkTextBTreeNode *node2;
3151 * Find the line under this GtkTextBTreeNode just before the starting line.
3153 prev = line->parent->children.line; /* First line at leaf */
3154 while (prev != line)
3156 if (prev->next == line)
3162 g_error ("gtk_text_btree_previous_line ran out of lines");
3166 * This was the first line associated with the particular parent
3167 * GtkTextBTreeNode. Search up the tree for the previous GtkTextBTreeNode,
3168 * then search down from that GtkTextBTreeNode to find its last line.
3170 for (node = line->parent; ; node = node->parent)
3172 if (node == NULL || node->parent == NULL)
3174 else if (node != node->parent->children.node)
3178 for (node2 = node->parent->children.node; ;
3179 node2 = node2->children.node)
3181 while (node2->next != node)
3182 node2 = node2->next;
3184 if (node2->level == 0)
3190 for (prev = node2->children.line ; ; prev = prev->next)
3192 if (prev->next == NULL)
3196 g_assert_not_reached ();
3201 _gtk_text_line_add_data (GtkTextLine *line,
3202 GtkTextLineData *data)
3204 g_return_if_fail (line != NULL);
3205 g_return_if_fail (data != NULL);
3206 g_return_if_fail (data->view_id != NULL);
3210 data->next = line->views;
3220 _gtk_text_line_remove_data (GtkTextLine *line,
3223 GtkTextLineData *prev;
3224 GtkTextLineData *iter;
3226 g_return_val_if_fail (line != NULL, NULL);
3227 g_return_val_if_fail (view_id != NULL, NULL);
3231 while (iter != NULL)
3233 if (iter->view_id == view_id)
3242 prev->next = iter->next;
3244 line->views = iter->next;
3253 _gtk_text_line_get_data (GtkTextLine *line,
3256 GtkTextLineData *iter;
3258 g_return_val_if_fail (line != NULL, NULL);
3259 g_return_val_if_fail (view_id != NULL, NULL);
3262 while (iter != NULL)
3264 if (iter->view_id == view_id)
3273 _gtk_text_line_invalidate_wrap (GtkTextLine *line,
3274 GtkTextLineData *ld)
3276 /* For now this is totally unoptimized. FIXME?
3278 We could probably optimize the case where the width removed
3279 is less than the max width for the parent node,
3280 and the case where the height is unchanged when we re-wrap.
3283 g_return_if_fail (ld != NULL);
3286 gtk_text_btree_node_invalidate_upward (line->parent, ld->view_id);
3290 _gtk_text_line_char_count (GtkTextLine *line)
3292 GtkTextLineSegment *seg;
3296 seg = line->segments;
3299 size += seg->char_count;
3306 _gtk_text_line_byte_count (GtkTextLine *line)
3308 GtkTextLineSegment *seg;
3312 seg = line->segments;
3315 size += seg->byte_count;
3323 _gtk_text_line_char_index (GtkTextLine *target_line)
3325 GSList *node_stack = NULL;
3326 GtkTextBTreeNode *iter;
3330 /* Push all our parent nodes onto a stack */
3331 iter = target_line->parent;
3333 g_assert (iter != NULL);
3335 while (iter != NULL)
3337 node_stack = g_slist_prepend (node_stack, iter);
3339 iter = iter->parent;
3342 /* Check that we have the root node on top of the stack. */
3343 g_assert (node_stack != NULL &&
3344 node_stack->data != NULL &&
3345 ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3347 /* Add up chars in all nodes before the nodes in our stack.
3351 iter = node_stack->data;
3352 while (iter != NULL)
3354 GtkTextBTreeNode *child_iter;
3355 GtkTextBTreeNode *next_node;
3357 next_node = node_stack->next ?
3358 node_stack->next->data : NULL;
3359 node_stack = g_slist_remove (node_stack, node_stack->data);
3361 if (iter->level == 0)
3363 /* stack should be empty when we're on the last node */
3364 g_assert (node_stack == NULL);
3365 break; /* Our children are now lines */
3368 g_assert (next_node != NULL);
3369 g_assert (iter != NULL);
3370 g_assert (next_node->parent == iter);
3372 /* Add up chars before us in the tree */
3373 child_iter = iter->children.node;
3374 while (child_iter != next_node)
3376 g_assert (child_iter != NULL);
3378 num_chars += child_iter->num_chars;
3380 child_iter = child_iter->next;
3386 g_assert (iter != NULL);
3387 g_assert (iter == target_line->parent);
3389 /* Since we don't store char counts in lines, only in segments, we
3390 have to iterate over the lines adding up segment char counts
3391 until we find our line. */
3392 line = iter->children.line;
3393 while (line != target_line)
3395 g_assert (line != NULL);
3397 num_chars += _gtk_text_line_char_count (line);
3402 g_assert (line == target_line);
3408 _gtk_text_line_byte_to_segment (GtkTextLine *line,
3412 GtkTextLineSegment *seg;
3415 g_return_val_if_fail (line != NULL, NULL);
3417 offset = byte_offset;
3418 seg = line->segments;
3420 while (offset >= seg->byte_count)
3422 g_assert (seg != NULL); /* means an invalid byte index */
3423 offset -= seg->byte_count;
3428 *seg_offset = offset;
3434 _gtk_text_line_char_to_segment (GtkTextLine *line,
3438 GtkTextLineSegment *seg;
3441 g_return_val_if_fail (line != NULL, NULL);
3443 offset = char_offset;
3444 seg = line->segments;
3446 while (offset >= seg->char_count)
3448 g_assert (seg != NULL); /* means an invalid char index */
3449 offset -= seg->char_count;
3454 *seg_offset = offset;
3460 _gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3464 GtkTextLineSegment *seg;
3467 g_return_val_if_fail (line != NULL, NULL);
3469 offset = byte_offset;
3470 seg = line->segments;
3472 while (offset > 0 && offset >= seg->byte_count)
3474 g_assert (seg != NULL); /* means an invalid byte index */
3475 offset -= seg->byte_count;
3480 *seg_offset = offset;
3486 _gtk_text_line_char_to_any_segment (GtkTextLine *line,
3490 GtkTextLineSegment *seg;
3493 g_return_val_if_fail (line != NULL, NULL);
3495 offset = char_offset;
3496 seg = line->segments;
3498 while (offset > 0 && offset >= seg->char_count)
3500 g_assert (seg != NULL); /* means an invalid byte index */
3501 offset -= seg->char_count;
3506 *seg_offset = offset;
3512 _gtk_text_line_byte_to_char (GtkTextLine *line,
3516 GtkTextLineSegment *seg;
3518 g_return_val_if_fail (line != NULL, 0);
3519 g_return_val_if_fail (byte_offset >= 0, 0);
3522 seg = line->segments;
3523 while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3524 the next segment) */
3526 g_assert (seg != NULL); /* our byte_index was bogus if this happens */
3528 byte_offset -= seg->byte_count;
3529 char_offset += seg->char_count;
3534 g_assert (seg != NULL);
3536 /* Now byte_offset is the offset into the current segment,
3537 and char_offset is the start of the current segment.
3538 Optimize the case where no chars use > 1 byte */
3539 if (seg->byte_count == seg->char_count)
3540 return char_offset + byte_offset;
3543 if (seg->type == >k_text_char_type)
3544 return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3547 g_assert (seg->char_count == 1);
3548 g_assert (byte_offset == 0);
3556 _gtk_text_line_char_to_byte (GtkTextLine *line,
3559 g_warning ("FIXME not implemented");
3564 /* FIXME sync with char_locate (or figure out a clean
3565 way to merge the two functions) */
3567 _gtk_text_line_byte_locate (GtkTextLine *line,
3569 GtkTextLineSegment **segment,
3570 GtkTextLineSegment **any_segment,
3571 gint *seg_byte_offset,
3572 gint *line_byte_offset)
3574 GtkTextLineSegment *seg;
3575 GtkTextLineSegment *after_prev_indexable;
3576 GtkTextLineSegment *after_last_indexable;
3577 GtkTextLineSegment *last_indexable;
3581 g_return_val_if_fail (line != NULL, FALSE);
3582 g_return_val_if_fail (byte_offset >= 0, FALSE);
3585 *any_segment = NULL;
3588 offset = byte_offset;
3590 last_indexable = NULL;
3591 after_last_indexable = line->segments;
3592 after_prev_indexable = line->segments;
3593 seg = line->segments;
3595 /* The loop ends when we're inside a segment;
3596 last_indexable refers to the last segment
3597 we passed entirely. */
3598 while (seg && offset >= seg->byte_count)
3600 if (seg->char_count > 0)
3602 offset -= seg->byte_count;
3603 bytes_in_line += seg->byte_count;
3604 last_indexable = seg;
3605 after_prev_indexable = after_last_indexable;
3606 after_last_indexable = last_indexable->next;
3614 /* We went off the end of the line */
3616 g_warning ("%s: byte index off the end of the line", G_STRLOC);
3623 if (after_last_indexable != NULL)
3624 *any_segment = after_last_indexable;
3626 *any_segment = *segment;
3629 /* Override any_segment if we're in the middle of a segment. */
3631 *any_segment = *segment;
3633 *seg_byte_offset = offset;
3635 g_assert (*segment != NULL);
3636 g_assert (*any_segment != NULL);
3637 g_assert (*seg_byte_offset < (*segment)->byte_count);
3639 *line_byte_offset = bytes_in_line + *seg_byte_offset;
3644 /* FIXME sync with byte_locate (or figure out a clean
3645 way to merge the two functions) */
3647 _gtk_text_line_char_locate (GtkTextLine *line,
3649 GtkTextLineSegment **segment,
3650 GtkTextLineSegment **any_segment,
3651 gint *seg_char_offset,
3652 gint *line_char_offset)
3654 GtkTextLineSegment *seg;
3655 GtkTextLineSegment *after_prev_indexable;
3656 GtkTextLineSegment *after_last_indexable;
3657 GtkTextLineSegment *last_indexable;
3661 g_return_val_if_fail (line != NULL, FALSE);
3662 g_return_val_if_fail (char_offset >= 0, FALSE);
3665 *any_segment = NULL;
3668 offset = char_offset;
3670 last_indexable = NULL;
3671 after_last_indexable = line->segments;
3672 after_prev_indexable = line->segments;
3673 seg = line->segments;
3675 /* The loop ends when we're inside a segment;
3676 last_indexable refers to the last segment
3677 we passed entirely. */
3678 while (seg && offset >= seg->char_count)
3680 if (seg->char_count > 0)
3682 offset -= seg->char_count;
3683 chars_in_line += seg->char_count;
3684 last_indexable = seg;
3685 after_prev_indexable = after_last_indexable;
3686 after_last_indexable = last_indexable->next;
3694 /* end of the line */
3696 g_warning ("%s: char offset off the end of the line", G_STRLOC);
3703 if (after_last_indexable != NULL)
3704 *any_segment = after_last_indexable;
3706 *any_segment = *segment;
3709 /* Override any_segment if we're in the middle of a segment. */
3711 *any_segment = *segment;
3713 *seg_char_offset = offset;
3715 g_assert (*segment != NULL);
3716 g_assert (*any_segment != NULL);
3717 g_assert (*seg_char_offset < (*segment)->char_count);
3719 *line_char_offset = chars_in_line + *seg_char_offset;
3725 _gtk_text_line_byte_to_char_offsets (GtkTextLine *line,
3727 gint *line_char_offset,
3728 gint *seg_char_offset)
3730 GtkTextLineSegment *seg;
3733 g_return_if_fail (line != NULL);
3734 g_return_if_fail (byte_offset >= 0);
3736 *line_char_offset = 0;
3738 offset = byte_offset;
3739 seg = line->segments;
3741 while (offset >= seg->byte_count)
3743 offset -= seg->byte_count;
3744 *line_char_offset += seg->char_count;
3746 g_assert (seg != NULL); /* means an invalid char offset */
3749 g_assert (seg->char_count > 0); /* indexable. */
3751 /* offset is now the number of bytes into the current segment we
3752 * want to go. Count chars into the current segment.
3755 if (seg->type == >k_text_char_type)
3757 *seg_char_offset = g_utf8_strlen (seg->body.chars, offset);
3759 g_assert (*seg_char_offset < seg->char_count);
3761 *line_char_offset += *seg_char_offset;
3765 g_assert (offset == 0);
3766 *seg_char_offset = 0;
3771 _gtk_text_line_char_to_byte_offsets (GtkTextLine *line,
3773 gint *line_byte_offset,
3774 gint *seg_byte_offset)
3776 GtkTextLineSegment *seg;
3779 g_return_if_fail (line != NULL);
3780 g_return_if_fail (char_offset >= 0);
3782 *line_byte_offset = 0;
3784 offset = char_offset;
3785 seg = line->segments;
3787 while (offset >= seg->char_count)
3789 offset -= seg->char_count;
3790 *line_byte_offset += seg->byte_count;
3792 g_assert (seg != NULL); /* means an invalid char offset */
3795 g_assert (seg->char_count > 0); /* indexable. */
3797 /* offset is now the number of chars into the current segment we
3798 want to go. Count bytes into the current segment. */
3800 if (seg->type == >k_text_char_type)
3802 *seg_byte_offset = 0;
3806 const char * start = seg->body.chars + *seg_byte_offset;
3808 bytes = g_utf8_next_char (start) - start;
3809 *seg_byte_offset += bytes;
3813 g_assert (*seg_byte_offset < seg->byte_count);
3815 *line_byte_offset += *seg_byte_offset;
3819 g_assert (offset == 0);
3820 *seg_byte_offset = 0;
3825 node_compare (GtkTextBTreeNode *lhs,
3826 GtkTextBTreeNode *rhs)
3828 GtkTextBTreeNode *iter;
3829 GtkTextBTreeNode *node;
3830 GtkTextBTreeNode *common_parent;
3831 GtkTextBTreeNode *parent_of_lower;
3832 GtkTextBTreeNode *parent_of_higher;
3833 gboolean lhs_is_lower;
3834 GtkTextBTreeNode *lower;
3835 GtkTextBTreeNode *higher;
3837 /* This function assumes that lhs and rhs are not underneath each
3844 if (lhs->level < rhs->level)
3846 lhs_is_lower = TRUE;
3852 lhs_is_lower = FALSE;
3857 /* Algorithm: find common parent of lhs/rhs. Save the child nodes
3858 * of the common parent we used to reach the common parent; the
3859 * ordering of these child nodes in the child list is the ordering
3863 /* Get on the same level (may be on same level already) */
3865 while (node->level < higher->level)
3866 node = node->parent;
3868 g_assert (node->level == higher->level);
3870 g_assert (node != higher); /* Happens if lower is underneath higher */
3872 /* Go up until we have two children with a common parent.
3874 parent_of_lower = node;
3875 parent_of_higher = higher;
3877 while (parent_of_lower->parent != parent_of_higher->parent)
3879 parent_of_lower = parent_of_lower->parent;
3880 parent_of_higher = parent_of_higher->parent;
3883 g_assert (parent_of_lower->parent == parent_of_higher->parent);
3885 common_parent = parent_of_lower->parent;
3887 g_assert (common_parent != NULL);
3889 /* See which is first in the list of common_parent's children */
3890 iter = common_parent->children.node;
3891 while (iter != NULL)
3893 if (iter == parent_of_higher)
3895 /* higher is less than lower */
3898 return 1; /* lhs > rhs */
3902 else if (iter == parent_of_lower)
3904 /* lower is less than higher */
3907 return -1; /* lhs < rhs */
3915 g_assert_not_reached ();
3919 /* remember that tag == NULL means "any tag" */
3921 _gtk_text_line_next_could_contain_tag (GtkTextLine *line,
3925 GtkTextBTreeNode *node;
3926 GtkTextTagInfo *info;
3927 gboolean below_tag_root;
3929 g_return_val_if_fail (line != NULL, NULL);
3931 if (gtk_debug_flags & GTK_DEBUG_TEXT)
3932 _gtk_text_btree_check (tree);
3936 /* Right now we can only offer linear-search if the user wants
3937 * to know about any tag toggle at all.
3939 return _gtk_text_line_next (line);
3942 /* Our tag summaries only have node precision, not line
3943 precision. This means that if any line under a node could contain a
3944 tag, then any of the others could also contain a tag.
3946 In the future we could have some mechanism to keep track of how
3947 many toggles we've found under a node so far, since we have a
3948 count of toggles under the node. But for now I'm going with KISS.
3951 /* return same-node line, if any. */
3955 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3959 if (info->tag_root == NULL)
3962 if (info->tag_root == line->parent)
3963 return NULL; /* we were at the last line under the tag root */
3965 /* We need to go up out of this node, and on to the next one with
3966 toggles for the target tag. If we're below the tag root, we need to
3967 find the next node below the tag root that has tag summaries. If
3968 we're not below the tag root, we need to see if the tag root is
3969 after us in the tree, and if so, return the first line underneath
3972 node = line->parent;
3973 below_tag_root = FALSE;
3974 while (node != NULL)
3976 if (node == info->tag_root)
3978 below_tag_root = TRUE;
3982 node = node->parent;
3987 node = line->parent;
3988 while (node != info->tag_root)
3990 if (node->next == NULL)
3991 node = node->parent;
3996 if (gtk_text_btree_node_has_tag (node, tag))
4006 ordering = node_compare (line->parent, info->tag_root);
4010 /* Tag root is ahead of us, so search there. */
4011 node = info->tag_root;
4016 /* Tag root is after us, so no more lines that
4017 * could contain the tag.
4022 g_assert_not_reached ();
4027 g_assert (node != NULL);
4029 /* We have to find the first sub-node of this node that contains
4033 while (node->level > 0)
4035 g_assert (node != NULL); /* If this fails, it likely means an
4036 incorrect tag summary led us on a
4037 wild goose chase down this branch of
4039 node = node->children.node;
4040 while (node != NULL)
4042 if (gtk_text_btree_node_has_tag (node, tag))
4048 g_assert (node != NULL);
4049 g_assert (node->level == 0);
4051 return node->children.line;
4055 prev_line_under_node (GtkTextBTreeNode *node,
4060 prev = node->children.line;
4066 while (prev->next != line)
4076 _gtk_text_line_previous_could_contain_tag (GtkTextLine *line,
4080 GtkTextBTreeNode *node;
4081 GtkTextBTreeNode *found_node = NULL;
4082 GtkTextTagInfo *info;
4083 gboolean below_tag_root;
4085 GtkTextBTreeNode *line_ancestor;
4086 GtkTextBTreeNode *line_ancestor_parent;
4088 /* See next_could_contain_tag () for more extensive comments
4089 * on what's going on here.
4092 g_return_val_if_fail (line != NULL, NULL);
4094 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4095 _gtk_text_btree_check (tree);
4099 /* Right now we can only offer linear-search if the user wants
4100 * to know about any tag toggle at all.
4102 return _gtk_text_line_previous (line);
4105 /* Return same-node line, if any. */
4106 prev = prev_line_under_node (line->parent, line);
4110 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4114 if (info->tag_root == NULL)
4117 if (info->tag_root == line->parent)
4118 return NULL; /* we were at the first line under the tag root */
4120 /* Are we below the tag root */
4121 node = line->parent;
4122 below_tag_root = FALSE;
4123 while (node != NULL)
4125 if (node == info->tag_root)
4127 below_tag_root = TRUE;
4131 node = node->parent;
4136 /* Look for a previous node under this tag root that has our
4140 /* this assertion holds because line->parent is not the
4141 * tag root, we are below the tag root, and the tag
4144 g_assert (line->parent->parent != NULL);
4146 line_ancestor = line->parent;
4147 line_ancestor_parent = line->parent->parent;
4149 node = line_ancestor_parent->children.node;
4150 while (node != line_ancestor &&
4151 line_ancestor != info->tag_root)
4153 GSList *child_nodes = NULL;
4156 /* Create reverse-order list of nodes before
4159 while (node != line_ancestor
4162 child_nodes = g_slist_prepend (child_nodes, node);
4167 /* Try to find a node with our tag on it in the list */
4171 GtkTextBTreeNode *this_node = tmp->data;
4173 g_assert (this_node != line_ancestor);
4175 if (gtk_text_btree_node_has_tag (this_node, tag))
4177 found_node = this_node;
4178 g_slist_free (child_nodes);
4182 tmp = g_slist_next (tmp);
4185 g_slist_free (child_nodes);
4187 /* Didn't find anything on this level; go up one level. */
4188 line_ancestor = line_ancestor_parent;
4189 line_ancestor_parent = line_ancestor->parent;
4191 node = line_ancestor_parent->children.node;
4201 ordering = node_compare (line->parent, info->tag_root);
4205 /* Tag root is ahead of us, so no more lines
4212 /* Tag root is after us, so grab last tagged
4213 * line underneath the tag root.
4215 found_node = info->tag_root;
4219 g_assert_not_reached ();
4224 g_assert (found_node != NULL);
4226 /* We have to find the last sub-node of this node that contains
4231 while (node->level > 0)
4233 GSList *child_nodes = NULL;
4235 g_assert (node != NULL); /* If this fails, it likely means an
4236 incorrect tag summary led us on a
4237 wild goose chase down this branch of
4240 node = node->children.node;
4241 while (node != NULL)
4243 child_nodes = g_slist_prepend (child_nodes, node);
4247 node = NULL; /* detect failure to find a child node. */
4250 while (iter != NULL)
4252 if (gtk_text_btree_node_has_tag (iter->data, tag))
4254 /* recurse into this node. */
4259 iter = g_slist_next (iter);
4262 g_slist_free (child_nodes);
4264 g_assert (node != NULL);
4267 g_assert (node != NULL);
4268 g_assert (node->level == 0);
4270 /* this assertion is correct, but slow. */
4271 /* g_assert (node_compare (node, line->parent) < 0); */
4273 /* Return last line in this node. */
4275 prev = node->children.line;
4283 * Non-public function implementations
4287 summary_list_destroy (Summary *summary)
4290 while (summary != NULL)
4292 next = summary->next;
4293 summary_destroy (summary);
4299 get_last_line (GtkTextBTree *tree)
4301 if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
4307 n_lines = _gtk_text_btree_line_count (tree);
4309 g_assert (n_lines >= 1); /* num_lines doesn't return bogus last line. */
4311 line = _gtk_text_btree_get_line (tree, n_lines, &real_line);
4313 tree->end_iter_line_stamp = tree->chars_changed_stamp;
4314 tree->end_iter_line = line;
4317 return tree->end_iter_line;
4325 gtk_text_line_new (void)
4329 line = g_new0(GtkTextLine, 1);
4335 gtk_text_line_destroy (GtkTextBTree *tree, GtkTextLine *line)
4337 GtkTextLineData *ld;
4338 GtkTextLineData *next;
4340 g_return_if_fail (line != NULL);
4347 view = gtk_text_btree_get_view (tree, ld->view_id);
4349 g_assert (view != NULL);
4352 gtk_text_layout_free_line_data (view->layout, line, ld);
4361 gtk_text_line_set_parent (GtkTextLine *line,
4362 GtkTextBTreeNode *node)
4364 if (line->parent == node)
4366 line->parent = node;
4367 gtk_text_btree_node_invalidate_upward (node, NULL);
4371 cleanup_line (GtkTextLine *line)
4373 GtkTextLineSegment *seg, **prev_p;
4377 * Make a pass over all of the segments in the line, giving each
4378 * a chance to clean itself up. This could potentially change
4379 * the structure of the line, e.g. by merging two segments
4380 * together or having two segments cancel themselves; if so,
4381 * then repeat the whole process again, since the first structure
4382 * change might make other structure changes possible. Repeat
4383 * until eventually there are no changes.
4390 for (prev_p = &line->segments, seg = *prev_p;
4392 prev_p = &(*prev_p)->next, seg = *prev_p)
4394 if (seg->type->cleanupFunc != NULL)
4396 *prev_p = (*seg->type->cleanupFunc)(seg, line);
4409 node_data_new (gpointer view_id)
4413 nd = g_new (NodeData, 1);
4415 nd->view_id = view_id;
4425 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 gtk_text_btree_node_free_empty (tree, node);
5120 gtk_text_btree_node_free_empty (GtkTextBTree *tree,
5121 GtkTextBTreeNode *node)
5123 g_return_if_fail ((node->level > 0 && node->children.node == NULL) ||
5124 (node->level == 0 && node->children.line == NULL));
5126 summary_list_destroy (node->summary);
5127 node_data_list_destroy (node->node_data);
5132 gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node, gpointer view_id)
5136 nd = node->node_data;
5139 if (nd->view_id == view_id)
5147 nd = node_data_new (view_id);
5149 if (node->node_data)
5150 nd->next = node->node_data;
5152 node->node_data = nd;
5159 gtk_text_btree_node_remove_data (GtkTextBTreeNode *node, gpointer view_id)
5165 nd = node->node_data;
5168 if (nd->view_id == view_id)
5179 prev->next = nd->next;
5181 if (node->node_data == nd)
5182 node->node_data = nd->next;
5186 node_data_destroy (nd);
5190 gtk_text_btree_node_get_size (GtkTextBTreeNode *node, gpointer view_id,
5191 gint *width, gint *height)
5195 g_return_if_fail (width != NULL);
5196 g_return_if_fail (height != NULL);
5198 nd = gtk_text_btree_node_ensure_data (node, view_id);
5203 *height = nd->height;
5206 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5207 * here isn't quite right, since for a lot of operations we want to
5208 * know which children of the common parent correspond to the two nodes
5209 * (e.g., when computing the order of two iters)
5211 static GtkTextBTreeNode *
5212 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5213 GtkTextBTreeNode *node2)
5215 while (node1->level < node2->level)
5216 node1 = node1->parent;
5217 while (node2->level < node1->level)
5218 node2 = node2->parent;
5219 while (node1 != node2)
5221 node1 = node1->parent;
5222 node2 = node2->parent;
5233 gtk_text_btree_get_view (GtkTextBTree *tree, gpointer view_id)
5238 while (view != NULL)
5240 if (view->view_id == view_id)
5249 get_tree_bounds (GtkTextBTree *tree,
5253 _gtk_text_btree_get_iter_at_line_char (tree, start, 0, 0);
5254 _gtk_text_btree_get_end_iter (tree, end);
5258 tag_changed_cb (GtkTextTagTable *table,
5260 gboolean size_changed,
5265 /* We need to queue a relayout on all regions that are tagged with
5272 if (_gtk_text_btree_get_iter_at_first_toggle (tree, &start, tag))
5274 /* Must be a last toggle if there was a first one. */
5275 _gtk_text_btree_get_iter_at_last_toggle (tree, &end, tag);
5276 _gtk_text_btree_invalidate_region (tree,
5283 /* We only need to queue a redraw, not a relayout */
5288 while (view != NULL)
5292 _gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5293 gtk_text_layout_changed (view->layout, 0, height, height);
5301 tag_removed_cb (GtkTextTagTable *table,
5305 /* Remove the tag from the tree */
5310 get_tree_bounds (tree, &start, &end);
5312 _gtk_text_btree_tag (&start, &end, tag, FALSE);
5313 gtk_text_btree_remove_tag_info (tree, tag);
5317 /* Rebalance the out-of-whack node "node" */
5319 gtk_text_btree_rebalance (GtkTextBTree *tree,
5320 GtkTextBTreeNode *node)
5323 * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5324 * up through the tree one GtkTextBTreeNode at a time until the root
5325 * GtkTextBTreeNode has been processed.
5328 while (node != NULL)
5330 GtkTextBTreeNode *new_node, *child;
5335 * Check to see if the GtkTextBTreeNode has too many children. If it does,
5336 * then split off all but the first MIN_CHILDREN into a separate
5337 * GtkTextBTreeNode following the original one. Then repeat until the
5338 * GtkTextBTreeNode has a decent size.
5341 if (node->num_children > MAX_CHILDREN)
5346 * If the GtkTextBTreeNode being split is the root
5347 * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5351 if (node->parent == NULL)
5353 new_node = gtk_text_btree_node_new ();
5354 new_node->parent = NULL;
5355 new_node->next = NULL;
5356 new_node->summary = NULL;
5357 new_node->level = node->level + 1;
5358 new_node->children.node = node;
5359 recompute_node_counts (tree, new_node);
5360 tree->root_node = new_node;
5362 new_node = gtk_text_btree_node_new ();
5363 new_node->parent = node->parent;
5364 new_node->next = node->next;
5365 node->next = new_node;
5366 new_node->summary = NULL;
5367 new_node->level = node->level;
5368 new_node->num_children = node->num_children - MIN_CHILDREN;
5369 if (node->level == 0)
5371 for (i = MIN_CHILDREN-1,
5372 line = node->children.line;
5373 i > 0; i--, line = line->next)
5375 /* Empty loop body. */
5377 new_node->children.line = line->next;
5382 for (i = MIN_CHILDREN-1,
5383 child = node->children.node;
5384 i > 0; i--, child = child->next)
5386 /* Empty loop body. */
5388 new_node->children.node = child->next;
5391 recompute_node_counts (tree, node);
5392 node->parent->num_children++;
5394 if (node->num_children <= MAX_CHILDREN)
5396 recompute_node_counts (tree, node);
5402 while (node->num_children < MIN_CHILDREN)
5404 GtkTextBTreeNode *other;
5405 GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5406 GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5407 int total_children, first_children, i;
5410 * Too few children for this GtkTextBTreeNode. If this is the root then,
5411 * it's OK for it to have less than MIN_CHILDREN children
5412 * as long as it's got at least two. If it has only one
5413 * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5414 * the tree and use its child as the new root.
5417 if (node->parent == NULL)
5419 if ((node->num_children == 1) && (node->level > 0))
5421 tree->root_node = node->children.node;
5422 tree->root_node->parent = NULL;
5424 node->children.node = NULL;
5425 gtk_text_btree_node_free_empty (tree, node);
5431 * Not the root. Make sure that there are siblings to
5435 if (node->parent->num_children < 2)
5437 gtk_text_btree_rebalance (tree, node->parent);
5442 * Find a sibling neighbor to borrow from, and arrange for
5443 * node to be the earlier of the pair.
5446 if (node->next == NULL)
5448 for (other = node->parent->children.node;
5449 other->next != node;
5450 other = other->next)
5452 /* Empty loop body. */
5459 * We're going to either merge the two siblings together
5460 * into one GtkTextBTreeNode or redivide the children among them to
5461 * balance their loads. As preparation, join their two
5462 * child lists into a single list and remember the half-way
5463 * point in the list.
5466 total_children = node->num_children + other->num_children;
5467 first_children = total_children/2;
5468 if (node->children.node == NULL)
5470 node->children = other->children;
5471 other->children.node = NULL;
5472 other->children.line = NULL;
5474 if (node->level == 0)
5478 for (line = node->children.line, i = 1;
5480 line = line->next, i++)
5482 if (i == first_children)
5487 line->next = other->children.line;
5488 while (i <= first_children)
5497 GtkTextBTreeNode *child;
5499 for (child = node->children.node, i = 1;
5500 child->next != NULL;
5501 child = child->next, i++)
5503 if (i <= first_children)
5505 if (i == first_children)
5507 halfwaynode = child;
5511 child->next = other->children.node;
5512 while (i <= first_children)
5514 halfwaynode = child;
5515 child = child->next;
5521 * If the two siblings can simply be merged together, do it.
5524 if (total_children <= MAX_CHILDREN)
5526 recompute_node_counts (tree, node);
5527 node->next = other->next;
5528 node->parent->num_children--;
5530 other->children.node = NULL;
5531 other->children.line = NULL;
5532 gtk_text_btree_node_free_empty (tree, other);
5537 * The siblings can't be merged, so just divide their
5538 * children evenly between them.
5541 if (node->level == 0)
5543 other->children.line = halfwayline->next;
5544 halfwayline->next = NULL;
5548 other->children.node = halfwaynode->next;
5549 halfwaynode->next = NULL;
5552 recompute_node_counts (tree, node);
5553 recompute_node_counts (tree, other);
5556 node = node->parent;
5561 post_insert_fixup (GtkTextBTree *tree,
5563 gint line_count_delta,
5564 gint char_count_delta)
5567 GtkTextBTreeNode *node;
5570 * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5571 * point, then rebalance the tree if necessary.
5574 for (node = line->parent ; node != NULL;
5575 node = node->parent)
5577 node->num_lines += line_count_delta;
5578 node->num_chars += char_count_delta;
5580 node = line->parent;
5581 node->num_children += line_count_delta;
5583 if (node->num_children > MAX_CHILDREN)
5585 gtk_text_btree_rebalance (tree, node);
5588 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5589 _gtk_text_btree_check (tree);
5592 static GtkTextTagInfo*
5593 gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
5596 GtkTextTagInfo *info;
5600 list = tree->tag_infos;
5601 while (list != NULL)
5604 if (info->tag == tag)
5607 list = g_slist_next (list);
5613 static GtkTextTagInfo*
5614 gtk_text_btree_get_tag_info (GtkTextBTree *tree,
5617 GtkTextTagInfo *info;
5619 info = gtk_text_btree_get_existing_tag_info (tree, tag);
5623 /* didn't find it, create. */
5625 info = g_new (GtkTextTagInfo, 1);
5628 g_object_ref (G_OBJECT (tag));
5629 info->tag_root = NULL;
5630 info->toggle_count = 0;
5632 tree->tag_infos = g_slist_prepend (tree->tag_infos, info);
5639 gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
5642 GtkTextTagInfo *info;
5647 list = tree->tag_infos;
5648 while (list != NULL)
5651 if (info->tag == tag)
5655 prev->next = list->next;
5659 tree->tag_infos = list->next;
5662 g_slist_free (list);
5664 g_object_unref (G_OBJECT (info->tag));
5670 list = g_slist_next (list);
5673 g_assert_not_reached ();
5678 recompute_level_zero_counts (GtkTextBTreeNode *node)
5681 GtkTextLineSegment *seg;
5683 g_assert (node->level == 0);
5685 line = node->children.line;
5686 while (line != NULL)
5688 node->num_children++;
5691 if (line->parent != node)
5692 gtk_text_line_set_parent (line, node);
5694 seg = line->segments;
5698 node->num_chars += seg->char_count;
5700 if (((seg->type != >k_text_toggle_on_type)
5701 && (seg->type != >k_text_toggle_off_type))
5702 || !(seg->body.toggle.inNodeCounts))
5708 GtkTextTagInfo *info;
5710 info = seg->body.toggle.info;
5712 gtk_text_btree_node_adjust_toggle_count (node, info, 1);
5723 recompute_level_nonzero_counts (GtkTextBTreeNode *node)
5726 GtkTextBTreeNode *child;
5728 g_assert (node->level > 0);
5730 child = node->children.node;
5731 while (child != NULL)
5733 node->num_children += 1;
5734 node->num_lines += child->num_lines;
5735 node->num_chars += child->num_chars;
5737 if (child->parent != node)
5739 child->parent = node;
5740 gtk_text_btree_node_invalidate_upward (node, NULL);
5743 summary = child->summary;
5744 while (summary != NULL)
5746 gtk_text_btree_node_adjust_toggle_count (node,
5748 summary->toggle_count);
5750 summary = summary->next;
5753 child = child->next;
5758 *----------------------------------------------------------------------
5760 * recompute_node_counts --
5762 * This procedure is called to recompute all the counts in a GtkTextBTreeNode
5763 * (tags, child information, etc.) by scanning the information in
5764 * its descendants. This procedure is called during rebalancing
5765 * when a GtkTextBTreeNode's child structure has changed.
5771 * The tag counts for node are modified to reflect its current
5772 * child structure, as are its num_children, num_lines, num_chars fields.
5773 * Also, all of the childrens' parent fields are made to point
5776 *----------------------------------------------------------------------
5780 recompute_node_counts (GtkTextBTree *tree, GtkTextBTreeNode *node)
5783 Summary *summary, *summary2;
5786 * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
5787 * the existing Summary records (most of them will probably be reused).
5790 summary = node->summary;
5791 while (summary != NULL)
5793 summary->toggle_count = 0;
5794 summary = summary->next;
5797 node->num_children = 0;
5798 node->num_lines = 0;
5799 node->num_chars = 0;
5802 * Scan through the children, adding the childrens' tag counts into
5803 * the GtkTextBTreeNode's tag counts and adding new Summary structures if
5807 if (node->level == 0)
5808 recompute_level_zero_counts (node);
5810 recompute_level_nonzero_counts (node);
5815 gtk_text_btree_node_check_valid (node, view->view_id);
5820 * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
5821 * records that still have a zero count, or that have all the toggles.
5822 * The GtkTextBTreeNode with the children that account for all the tags toggles
5823 * have no summary information, and they become the tag_root for the tag.
5827 for (summary = node->summary; summary != NULL; )
5829 if (summary->toggle_count > 0 &&
5830 summary->toggle_count < summary->info->toggle_count)
5832 if (node->level == summary->info->tag_root->level)
5835 * The tag's root GtkTextBTreeNode split and some toggles left.
5836 * The tag root must move up a level.
5838 summary->info->tag_root = node->parent;
5841 summary = summary->next;
5844 if (summary->toggle_count == summary->info->toggle_count)
5847 * A GtkTextBTreeNode merge has collected all the toggles under
5848 * one GtkTextBTreeNode. Push the root down to this level.
5850 summary->info->tag_root = node;
5852 if (summary2 != NULL)
5854 summary2->next = summary->next;
5855 summary_destroy (summary);
5856 summary = summary2->next;
5860 node->summary = summary->next;
5861 summary_destroy (summary);
5862 summary = node->summary;
5868 _gtk_change_node_toggle_count (GtkTextBTreeNode *node,
5869 GtkTextTagInfo *info,
5870 gint delta) /* may be negative */
5872 Summary *summary, *prevPtr;
5873 GtkTextBTreeNode *node2Ptr;
5874 int rootLevel; /* Level of original tag root */
5876 info->toggle_count += delta;
5878 if (info->tag_root == (GtkTextBTreeNode *) NULL)
5880 info->tag_root = node;
5885 * Note the level of the existing root for the tag so we can detect
5886 * if it needs to be moved because of the toggle count change.
5889 rootLevel = info->tag_root->level;
5892 * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
5893 * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
5897 for ( ; node != info->tag_root; node = node->parent)
5900 * See if there's already an entry for this tag for this GtkTextBTreeNode. If so,
5901 * perhaps all we have to do is adjust its count.
5904 for (prevPtr = NULL, summary = node->summary;
5906 prevPtr = summary, summary = summary->next)
5908 if (summary->info == info)
5913 if (summary != NULL)
5915 summary->toggle_count += delta;
5916 if (summary->toggle_count > 0 &&
5917 summary->toggle_count < info->toggle_count)
5921 if (summary->toggle_count != 0)
5924 * Should never find a GtkTextBTreeNode with max toggle count at this
5925 * point (there shouldn't have been a summary entry in the
5929 g_error ("%s: bad toggle count (%d) max (%d)",
5930 G_STRLOC, summary->toggle_count, info->toggle_count);
5934 * Zero toggle count; must remove this tag from the list.
5937 if (prevPtr == NULL)
5939 node->summary = summary->next;
5943 prevPtr->next = summary->next;
5945 summary_destroy (summary);
5950 * This tag isn't currently in the summary information list.
5953 if (rootLevel == node->level)
5957 * The old tag root is at the same level in the tree as this
5958 * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode. Move the tag root up
5959 * a level, in the hopes that it will now cover this GtkTextBTreeNode
5960 * as well as the old root (if not, we'll move it up again
5961 * the next time through the loop). To push it up one level
5962 * we copy the original toggle count into the summary
5963 * information at the old root and change the root to its
5964 * parent GtkTextBTreeNode.
5967 GtkTextBTreeNode *rootnode = info->tag_root;
5968 summary = (Summary *) g_malloc (sizeof (Summary));
5969 summary->info = info;
5970 summary->toggle_count = info->toggle_count - delta;
5971 summary->next = rootnode->summary;
5972 rootnode->summary = summary;
5973 rootnode = rootnode->parent;
5974 rootLevel = rootnode->level;
5975 info->tag_root = rootnode;
5977 summary = (Summary *) g_malloc (sizeof (Summary));
5978 summary->info = info;
5979 summary->toggle_count = delta;
5980 summary->next = node->summary;
5981 node->summary = summary;
5986 * If we've decremented the toggle count, then it may be necessary
5987 * to push the tag root down one or more levels.
5994 if (info->toggle_count == 0)
5996 info->tag_root = (GtkTextBTreeNode *) NULL;
5999 node = info->tag_root;
6000 while (node->level > 0)
6003 * See if a single child GtkTextBTreeNode accounts for all of the tag's
6004 * toggles. If so, push the root down one level.
6007 for (node2Ptr = node->children.node;
6008 node2Ptr != (GtkTextBTreeNode *)NULL ;
6009 node2Ptr = node2Ptr->next)
6011 for (prevPtr = NULL, summary = node2Ptr->summary;
6013 prevPtr = summary, summary = summary->next)
6015 if (summary->info == info)
6020 if (summary == NULL)
6024 if (summary->toggle_count != info->toggle_count)
6027 * No GtkTextBTreeNode has all toggles, so the root is still valid.
6034 * This GtkTextBTreeNode has all the toggles, so push down the root.
6037 if (prevPtr == NULL)
6039 node2Ptr->summary = summary->next;
6043 prevPtr->next = summary->next;
6045 summary_destroy (summary);
6046 info->tag_root = node2Ptr;
6049 node = info->tag_root;
6054 *----------------------------------------------------------------------
6058 * This is a utility procedure used by _gtk_text_btree_get_tags. It
6059 * increments the count for a particular tag, adding a new
6060 * entry for that tag if there wasn't one previously.
6066 * The information at *tagInfoPtr may be modified, and the arrays
6067 * may be reallocated to make them larger.
6069 *----------------------------------------------------------------------
6073 inc_count (GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
6078 for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
6079 count > 0; tag_p++, count--)
6083 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
6089 * There isn't currently an entry for this tag, so we have to
6090 * make a new one. If the arrays are full, then enlarge the
6094 if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
6096 GtkTextTag **newTags;
6097 int *newCounts, newSize;
6099 newSize = 2*tagInfoPtr->arraySize;
6100 newTags = (GtkTextTag **) g_malloc ((unsigned)
6101 (newSize*sizeof (GtkTextTag *)));
6102 memcpy ((void *) newTags, (void *) tagInfoPtr->tags,
6103 tagInfoPtr->arraySize *sizeof (GtkTextTag *));
6104 g_free ((char *) tagInfoPtr->tags);
6105 tagInfoPtr->tags = newTags;
6106 newCounts = (int *) g_malloc ((unsigned) (newSize*sizeof (int)));
6107 memcpy ((void *) newCounts, (void *) tagInfoPtr->counts,
6108 tagInfoPtr->arraySize *sizeof (int));
6109 g_free ((char *) tagInfoPtr->counts);
6110 tagInfoPtr->counts = newCounts;
6111 tagInfoPtr->arraySize = newSize;
6114 tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
6115 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
6116 tagInfoPtr->numTags++;
6120 gtk_text_btree_link_segment (GtkTextLineSegment *seg,
6121 const GtkTextIter *iter)
6123 GtkTextLineSegment *prev;
6127 line = _gtk_text_iter_get_text_line (iter);
6128 tree = _gtk_text_iter_get_btree (iter);
6130 prev = gtk_text_line_segment_split (iter);
6133 seg->next = line->segments;
6134 line->segments = seg;
6138 seg->next = prev->next;
6141 cleanup_line (line);
6142 segments_changed (tree);
6144 if (gtk_debug_flags & GTK_DEBUG_TEXT)
6145 _gtk_text_btree_check (tree);
6149 gtk_text_btree_unlink_segment (GtkTextBTree *tree,
6150 GtkTextLineSegment *seg,
6153 GtkTextLineSegment *prev;
6155 if (line->segments == seg)
6157 line->segments = seg->next;
6161 for (prev = line->segments; prev->next != seg;
6164 /* Empty loop body. */
6166 prev->next = seg->next;
6168 cleanup_line (line);
6169 segments_changed (tree);
6173 * This is here because it requires BTree internals, it logically
6174 * belongs in gtktextsegment.c
6179 *--------------------------------------------------------------
6181 * _gtk_toggle_segment_check_func --
6183 * This procedure is invoked to perform consistency checks
6184 * on toggle segments.
6190 * If a consistency problem is found the procedure g_errors.
6192 *--------------------------------------------------------------
6196 _gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6202 if (segPtr->byte_count != 0)
6204 g_error ("toggle_segment_check_func: segment had non-zero size");
6206 if (!segPtr->body.toggle.inNodeCounts)
6208 g_error ("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6210 needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6211 for (summary = line->parent->summary; ;
6212 summary = summary->next)
6214 if (summary == NULL)
6218 g_error ("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6225 if (summary->info == segPtr->body.toggle.info)
6229 g_error ("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6241 gtk_text_btree_node_view_check_consistency (GtkTextBTree *tree,
6242 GtkTextBTreeNode *node,
6252 while (view != NULL)
6254 if (view->view_id == nd->view_id)
6261 g_error ("Node has data for a view %p no longer attached to the tree",
6264 gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6265 &width, &height, &valid);
6266 if (nd->width != width ||
6267 nd->height != height ||
6268 !nd->valid != !valid)
6270 g_error ("Node aggregates for view %p are invalid:\n"
6271 "Are (%d,%d,%s), should be (%d,%d,%s)",
6273 nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6274 width, height, valid ? "TRUE" : "FALSE");
6279 gtk_text_btree_node_check_consistency (GtkTextBTree *tree,
6280 GtkTextBTreeNode *node)
6282 GtkTextBTreeNode *childnode;
6283 Summary *summary, *summary2;
6285 GtkTextLineSegment *segPtr;
6286 int num_children, num_lines, num_chars, toggle_count, min_children;
6287 GtkTextLineData *ld;
6290 if (node->parent != NULL)
6292 min_children = MIN_CHILDREN;
6294 else if (node->level > 0)
6301 if ((node->num_children < min_children)
6302 || (node->num_children > MAX_CHILDREN))
6304 g_error ("gtk_text_btree_node_check_consistency: bad child count (%d)",
6305 node->num_children);
6308 nd = node->node_data;
6311 gtk_text_btree_node_view_check_consistency (tree, node, nd);
6318 if (node->level == 0)
6320 for (line = node->children.line; line != NULL;
6323 if (line->parent != node)
6325 g_error ("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6327 if (line->segments == NULL)
6329 g_error ("gtk_text_btree_node_check_consistency: line has no segments");
6335 /* Just ensuring we don't segv while doing this loop */
6340 for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6342 if (segPtr->type->checkFunc != NULL)
6344 (*segPtr->type->checkFunc)(segPtr, line);
6346 if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6347 && (segPtr->next != NULL)
6348 && (segPtr->next->byte_count == 0)
6349 && (segPtr->next->type->leftGravity))
6351 g_error ("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6353 if ((segPtr->next == NULL)
6354 && (segPtr->type != >k_text_char_type))
6356 g_error ("gtk_text_btree_node_check_consistency: line ended with wrong type");
6359 num_chars += segPtr->char_count;
6368 for (childnode = node->children.node; childnode != NULL;
6369 childnode = childnode->next)
6371 if (childnode->parent != node)
6373 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6375 if (childnode->level != (node->level-1))
6377 g_error ("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6378 node->level, childnode->level);
6380 gtk_text_btree_node_check_consistency (tree, childnode);
6381 for (summary = childnode->summary; summary != NULL;
6382 summary = summary->next)
6384 for (summary2 = node->summary; ;
6385 summary2 = summary2->next)
6387 if (summary2 == NULL)
6389 if (summary->info->tag_root == node)
6393 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6394 summary->info->tag->name,
6395 "present in parent summaries");
6397 if (summary->info == summary2->info)
6404 num_lines += childnode->num_lines;
6405 num_chars += childnode->num_chars;
6408 if (num_children != node->num_children)
6410 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6411 num_children, node->num_children);
6413 if (num_lines != node->num_lines)
6415 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6416 num_lines, node->num_lines);
6418 if (num_chars != node->num_chars)
6420 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6421 num_chars, node->num_chars);
6424 for (summary = node->summary; summary != NULL;
6425 summary = summary->next)
6427 if (summary->info->toggle_count == summary->toggle_count)
6429 g_error ("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6430 summary->info->tag->name);
6433 if (node->level == 0)
6435 for (line = node->children.line; line != NULL;
6438 for (segPtr = line->segments; segPtr != NULL;
6439 segPtr = segPtr->next)
6441 if ((segPtr->type != >k_text_toggle_on_type)
6442 && (segPtr->type != >k_text_toggle_off_type))
6446 if (segPtr->body.toggle.info == summary->info)
6448 if (!segPtr->body.toggle.inNodeCounts)
6449 g_error ("Toggle segment not in the node counts");
6458 for (childnode = node->children.node;
6460 childnode = childnode->next)
6462 for (summary2 = childnode->summary;
6464 summary2 = summary2->next)
6466 if (summary2->info == summary->info)
6468 toggle_count += summary2->toggle_count;
6473 if (toggle_count != summary->toggle_count)
6475 g_error ("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6476 toggle_count, summary->toggle_count);
6478 for (summary2 = summary->next; summary2 != NULL;
6479 summary2 = summary2->next)
6481 if (summary2->info == summary->info)
6483 g_error ("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6484 summary->info->tag->name);
6491 listify_foreach (GtkTextTag *tag, gpointer user_data)
6493 GSList** listp = user_data;
6495 *listp = g_slist_prepend (*listp, tag);
6499 list_of_tags (GtkTextTagTable *table)
6501 GSList *list = NULL;
6503 gtk_text_tag_table_foreach (table, listify_foreach, &list);
6509 _gtk_text_btree_check (GtkTextBTree *tree)
6512 GtkTextBTreeNode *node;
6514 GtkTextLineSegment *seg;
6516 GSList *taglist = NULL;
6518 GtkTextTagInfo *info;
6521 * Make sure that the tag toggle counts and the tag root pointers are OK.
6523 for (taglist = list_of_tags (tree->table);
6524 taglist != NULL ; taglist = taglist->next)
6526 tag = taglist->data;
6527 info = gtk_text_btree_get_existing_tag_info (tree, tag);
6530 node = info->tag_root;
6533 if (info->toggle_count != 0)
6535 g_error ("_gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6536 tag->name, info->toggle_count);
6538 continue; /* no ranges for the tag */
6540 else if (info->toggle_count == 0)
6542 g_error ("_gtk_text_btree_check found root for \"%s\" with no toggles",
6545 else if (info->toggle_count & 1)
6547 g_error ("_gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6548 tag->name, info->toggle_count);
6550 for (summary = node->summary; summary != NULL;
6551 summary = summary->next)
6553 if (summary->info->tag == tag)
6555 g_error ("_gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6559 if (node->level > 0)
6561 for (node = node->children.node ; node != NULL ;
6564 for (summary = node->summary; summary != NULL;
6565 summary = summary->next)
6567 if (summary->info->tag == tag)
6569 count += summary->toggle_count;
6576 GtkTextLineSegmentClass * last = NULL;
6578 for (line = node->children.line ; line != NULL ;
6581 for (seg = line->segments; seg != NULL;
6584 if ((seg->type == >k_text_toggle_on_type ||
6585 seg->type == >k_text_toggle_off_type) &&
6586 seg->body.toggle.info->tag == tag)
6588 if (last == seg->type)
6589 g_error ("Two consecutive toggles on or off weren't merged");
6590 if (!seg->body.toggle.inNodeCounts)
6591 g_error ("Toggle segment not in the node counts");
6600 if (count != info->toggle_count)
6602 g_error ("_gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
6603 info->toggle_count, tag->name, count);
6608 g_slist_free (taglist);
6612 * Call a recursive procedure to do the main body of checks.
6615 node = tree->root_node;
6616 gtk_text_btree_node_check_consistency (tree, tree->root_node);
6619 * Make sure that there are at least two lines in the text and
6620 * that the last line has no characters except a newline.
6623 if (node->num_lines < 2)
6625 g_error ("_gtk_text_btree_check: less than 2 lines in tree");
6627 if (node->num_chars < 2)
6629 g_error ("_gtk_text_btree_check: less than 2 chars in tree");
6631 while (node->level > 0)
6633 node = node->children.node;
6634 while (node->next != NULL)
6639 line = node->children.line;
6640 while (line->next != NULL)
6644 seg = line->segments;
6645 while ((seg->type == >k_text_toggle_off_type)
6646 || (seg->type == >k_text_right_mark_type)
6647 || (seg->type == >k_text_left_mark_type))
6650 * It's OK to toggle a tag off in the last line, but
6651 * not to start a new range. It's also OK to have marks
6657 if (seg->type != >k_text_char_type)
6659 g_error ("_gtk_text_btree_check: last line has bogus segment type");
6661 if (seg->next != NULL)
6663 g_error ("_gtk_text_btree_check: last line has too many segments");
6665 if (seg->byte_count != 1)
6667 g_error ("_gtk_text_btree_check: last line has wrong # characters: %d",
6670 if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
6672 g_error ("_gtk_text_btree_check: last line had bad value: %s",
6677 void _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line);
6678 void _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment* seg);
6679 void _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent);
6680 void _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
6683 _gtk_text_btree_spew (GtkTextBTree *tree)
6688 printf ("%d lines in tree %p\n",
6689 _gtk_text_btree_line_count (tree), tree);
6691 line = _gtk_text_btree_get_line (tree, 0, &real_line);
6693 while (line != NULL)
6695 _gtk_text_btree_spew_line (tree, line);
6696 line = _gtk_text_line_next (line);
6699 printf ("=================== Tag information\n");
6704 list = tree->tag_infos;
6706 while (list != NULL)
6708 GtkTextTagInfo *info;
6712 printf (" tag `%s': root at %p, toggle count %d\n",
6713 info->tag->name, info->tag_root, info->toggle_count);
6715 list = g_slist_next (list);
6718 if (tree->tag_infos == NULL)
6720 printf (" (no tags in the tree)\n");
6724 printf ("=================== Tree nodes\n");
6727 _gtk_text_btree_spew_node (tree->root_node, 0);
6732 _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
6735 GtkTextLineSegment *seg;
6737 spaces = g_strnfill (indent, ' ');
6739 printf ("%sline %p chars %d bytes %d\n",
6741 _gtk_text_line_char_count (line),
6742 _gtk_text_line_byte_count (line));
6744 seg = line->segments;
6747 if (seg->type == >k_text_char_type)
6749 gchar* str = g_strndup (seg->body.chars, MIN (seg->byte_count, 10));
6754 if (*s == '\n' || *s == '\r')
6758 printf ("%s chars `%s'...\n", spaces, str);
6761 else if (seg->type == >k_text_right_mark_type)
6763 printf ("%s right mark `%s' visible: %d\n",
6765 seg->body.mark.name,
6766 seg->body.mark.visible);
6768 else if (seg->type == >k_text_left_mark_type)
6770 printf ("%s left mark `%s' visible: %d\n",
6772 seg->body.mark.name,
6773 seg->body.mark.visible);
6775 else if (seg->type == >k_text_toggle_on_type ||
6776 seg->type == >k_text_toggle_off_type)
6778 printf ("%s tag `%s' %s\n",
6779 spaces, seg->body.toggle.info->tag->name,
6780 seg->type == >k_text_toggle_off_type ? "off" : "on");
6790 _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent)
6793 GtkTextBTreeNode *iter;
6796 spaces = g_strnfill (indent, ' ');
6798 printf ("%snode %p level %d children %d lines %d chars %d\n",
6799 spaces, node, node->level,
6800 node->num_children, node->num_lines, node->num_chars);
6805 printf ("%s %d toggles of `%s' below this node\n",
6806 spaces, s->toggle_count, s->info->tag->name);
6812 if (node->level > 0)
6814 iter = node->children.node;
6815 while (iter != NULL)
6817 _gtk_text_btree_spew_node (iter, indent + 2);
6824 GtkTextLine *line = node->children.line;
6825 while (line != NULL)
6827 _gtk_text_btree_spew_line_short (line, indent + 2);
6835 _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line)
6837 GtkTextLineSegment * seg;
6839 printf ("%4d| line: %p parent: %p next: %p\n",
6840 _gtk_text_line_get_number (line), line, line->parent, line->next);
6842 seg = line->segments;
6846 _gtk_text_btree_spew_segment (tree, seg);
6852 _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment * seg)
6854 printf (" segment: %p type: %s bytes: %d chars: %d\n",
6855 seg, seg->type->name, seg->byte_count, seg->char_count);
6857 if (seg->type == >k_text_char_type)
6859 gchar* str = g_strndup (seg->body.chars, seg->byte_count);
6860 printf (" `%s'\n", str);
6863 else if (seg->type == >k_text_right_mark_type)
6865 printf (" right mark `%s' visible: %d not_deleteable: %d\n",
6866 seg->body.mark.name,
6867 seg->body.mark.visible,
6868 seg->body.mark.not_deleteable);
6870 else if (seg->type == >k_text_left_mark_type)
6872 printf (" left mark `%s' visible: %d not_deleteable: %d\n",
6873 seg->body.mark.name,
6874 seg->body.mark.visible,
6875 seg->body.mark.not_deleteable);
6877 else if (seg->type == >k_text_toggle_on_type ||
6878 seg->type == >k_text_toggle_off_type)
6880 printf (" tag `%s' priority %d\n",
6881 seg->body.toggle.info->tag->name,
6882 seg->body.toggle.info->tag->priority);