4 * This file contains code that manages the B-tree representation
5 * of text for the text buffer and implements character and
6 * toggle segment types.
8 * Copyright (c) 1992-1994 The Regents of the University of California.
9 * Copyright (c) 1994-1995 Sun Microsystems, Inc.
10 * Copyright (c) 2000 Red Hat, Inc.
11 * Tk -> Gtk port by Havoc Pennington <hp@redhat.com>
13 * This software is copyrighted by the Regents of the University of
14 * California, Sun Microsystems, Inc., and other parties. The
15 * following terms apply to all files associated with the software
16 * unless explicitly disclaimed in individual files.
18 * The authors hereby grant permission to use, copy, modify,
19 * distribute, and license this software and its documentation for any
20 * purpose, provided that existing copyright notices are retained in
21 * all copies and that this notice is included verbatim in any
22 * distributions. No written agreement, license, or royalty fee is
23 * required for any of the authorized uses. Modifications to this
24 * software may be copyrighted by their authors and need not follow
25 * the licensing terms described here, provided that the new terms are
26 * clearly indicated on the first page of each file where they apply.
28 * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY
29 * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
30 * DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION,
31 * OR ANY DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED
32 * OF THE POSSIBILITY OF SUCH DAMAGE.
34 * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
35 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
36 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND
37 * NON-INFRINGEMENT. THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS,
38 * AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE
39 * MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
41 * GOVERNMENT USE: If you are acquiring this software on behalf of the
42 * U.S. government, the Government shall have only "Restricted Rights"
43 * in the software and related documentation as defined in the Federal
44 * Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2). If you
45 * are acquiring the software on behalf of the Department of Defense,
46 * the software shall be classified as "Commercial Computer Software"
47 * and the Government shall have only "Restricted Rights" as defined
48 * in Clause 252.227-7013 (c) (1) of DFARs. Notwithstanding the
49 * foregoing, the authors grant the U.S. Government and others acting
50 * in its behalf permission to use and distribute the software in
51 * accordance with the terms specified in this license.
55 #include "gtktextbtree.h"
60 #include "gtksignal.h"
61 #include "gtktexttag.h"
62 #include "gtktexttagtable.h"
63 #include "gtktextlayout.h"
64 #include "gtktextiterprivate.h"
66 #include "gtktextmarkprivate.h"
74 * The structure below is used to pass information between
75 * _gtk_text_btree_get_tags and inc_count:
78 typedef struct TagInfo {
79 int numTags; /* Number of tags for which there
80 * is currently information in
82 int arraySize; /* Number of entries allocated for
84 GtkTextTag **tags; /* Array of tags seen so far.
86 int *counts; /* Toggle count (so far) for each
87 * entry in tags. Malloc-ed. */
92 * This is used to store per-view width/height info at the tree nodes.
95 typedef struct _NodeData NodeData;
101 /* Height and width of this node */
105 /* boolean indicating whether the height/width need to be recomputed */
111 * The data structure below keeps summary information about one tag as part
112 * of the tag information in a node.
115 typedef struct Summary {
116 GtkTextTagInfo *info; /* Handle for tag. */
117 int toggle_count; /* Number of transitions into or
118 * out of this tag that occur in
119 * the subtree rooted at this node. */
120 struct Summary *next; /* Next in list of all tags for same
121 * node, or NULL if at end of list. */
125 * The data structure below defines a node in the B-tree.
128 struct _GtkTextBTreeNode {
129 GtkTextBTreeNode *parent; /* Pointer to parent node, or NULL if
130 * this is the root. */
131 GtkTextBTreeNode *next; /* Next in list of siblings with the
132 * same parent node, or NULL for end
134 Summary *summary; /* First in malloc-ed list of info
135 * about tags in this subtree (NULL if
136 * no tag info in the subtree). */
137 int level; /* Level of this node in the B-tree.
138 * 0 refers to the bottom of the tree
139 * (children are lines, not nodes). */
140 union { /* First in linked list of children. */
141 struct _GtkTextBTreeNode *node; /* Used if level > 0. */
142 GtkTextLine *line; /* Used if level == 0. */
144 int num_children; /* Number of children of this node. */
145 int num_lines; /* Total number of lines (leaves) in
146 * the subtree rooted here. */
147 int num_chars; /* Number of chars below here */
154 * Used to store the list of views in our btree
157 typedef struct _BTreeView BTreeView;
161 GtkTextLayout *layout;
167 * And the tree itself
170 struct _GtkTextBTree {
171 GtkTextBTreeNode *root_node; /* Pointer to root of B-tree. */
172 GtkTextTagTable *table;
173 GHashTable *mark_table;
175 GtkTextMark *insert_mark;
176 GtkTextMark *selection_bound_mark;
177 GtkTextBuffer *buffer;
180 guint tag_changed_handler;
181 guint tag_removed_handler;
182 /* Incremented when a segment with a byte size > 0
183 is added to or removed from the tree (i.e. the
184 length of a line may have changed, and lines may
185 have been added or removed). This invalidates
186 all outstanding iterators.
188 guint chars_changed_stamp;
189 /* Incremented when any segments are added or deleted;
190 this makes outstanding iterators recalculate their
191 pointed-to segment and segment offset.
193 guint segments_changed_stamp;
195 GtkTextLine *end_iter_line;
197 guint end_iter_line_stamp;
199 GHashTable *child_anchor_table;
204 * Upper and lower bounds on how many children a node may have:
205 * rebalance when either of these limits is exceeded. MAX_CHILDREN
206 * should be twice MIN_CHILDREN and MIN_CHILDREN must be >= 2.
209 /* Tk used MAX of 12 and MIN of 6. This makes the tree wide and
210 shallow. It appears to be faster to locate a particular line number
211 if the tree is narrow and deep, since it is more finely sorted. I
212 guess this may increase memory use though, and make it slower to
213 walk the tree in order, or locate a particular byte index (which
214 is done by walking the tree in order).
216 There's basically a tradeoff here. However I'm thinking we want to
217 add pixels, byte counts, and char counts to the tree nodes,
218 at that point narrow and deep should speed up all operations,
219 not just the line number searches.
223 #define MAX_CHILDREN 12
224 #define MIN_CHILDREN 6
226 #define MAX_CHILDREN 6
227 #define MIN_CHILDREN 3
234 static BTreeView *gtk_text_btree_get_view (GtkTextBTree *tree,
236 static void gtk_text_btree_rebalance (GtkTextBTree *tree,
237 GtkTextBTreeNode *node);
238 static GtkTextLine * get_last_line (GtkTextBTree *tree);
239 static void post_insert_fixup (GtkTextBTree *tree,
240 GtkTextLine *insert_line,
241 gint char_count_delta,
242 gint line_count_delta);
243 static void gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
244 GtkTextTagInfo *info,
246 static gboolean gtk_text_btree_node_has_tag (GtkTextBTreeNode *node,
249 static void segments_changed (GtkTextBTree *tree);
250 static void chars_changed (GtkTextBTree *tree);
251 static void summary_list_destroy (Summary *summary);
252 static GtkTextLine *gtk_text_line_new (void);
253 static void gtk_text_line_destroy (GtkTextBTree *tree,
255 static void gtk_text_line_set_parent (GtkTextLine *line,
256 GtkTextBTreeNode *node);
257 static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
261 static NodeData *node_data_new (gpointer view_id);
262 static void node_data_destroy (NodeData *nd);
263 static void node_data_list_destroy (NodeData *nd);
264 static NodeData *node_data_find (NodeData *nd,
267 static GtkTextBTreeNode *gtk_text_btree_node_new (void);
268 static void gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node);
269 static void gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node,
271 static NodeData * gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
273 static NodeData * gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
275 static void gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
278 static void gtk_text_btree_node_remove_view (BTreeView *view,
279 GtkTextBTreeNode *node,
281 static void gtk_text_btree_node_destroy (GtkTextBTree *tree,
282 GtkTextBTreeNode *node);
283 static NodeData * gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node,
285 static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
287 static void gtk_text_btree_node_get_size (GtkTextBTreeNode *node,
291 static GtkTextBTreeNode * gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
292 GtkTextBTreeNode *node2);
293 static void get_tree_bounds (GtkTextBTree *tree,
296 static void tag_changed_cb (GtkTextTagTable *table,
298 gboolean size_changed,
300 static void tag_removed_cb (GtkTextTagTable *table,
303 static void cleanup_line (GtkTextLine *line);
304 static void recompute_node_counts (GtkTextBTree *tree,
305 GtkTextBTreeNode *node);
306 static void inc_count (GtkTextTag *tag,
308 TagInfo *tagInfoPtr);
310 static void summary_destroy (Summary *summary);
312 static void gtk_text_btree_link_segment (GtkTextLineSegment *seg,
313 const GtkTextIter *iter);
314 static void gtk_text_btree_unlink_segment (GtkTextBTree *tree,
315 GtkTextLineSegment *seg,
319 static GtkTextTagInfo *gtk_text_btree_get_tag_info (GtkTextBTree *tree,
321 static GtkTextTagInfo *gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
323 static void gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
326 static void redisplay_region (GtkTextBTree *tree,
327 const GtkTextIter *start,
328 const GtkTextIter *end);
330 /* Inline thingies */
333 segments_changed (GtkTextBTree *tree)
335 tree->segments_changed_stamp += 1;
339 chars_changed (GtkTextBTree *tree)
341 tree->chars_changed_stamp += 1;
349 _gtk_text_btree_new (GtkTextTagTable *table,
350 GtkTextBuffer *buffer)
353 GtkTextBTreeNode *root_node;
354 GtkTextLine *line, *line2;
356 g_return_val_if_fail (GTK_IS_TEXT_TAG_TABLE (table), NULL);
357 g_return_val_if_fail (GTK_IS_TEXT_BUFFER (buffer), NULL);
360 * The tree will initially have two empty lines. The second line
361 * isn't actually part of the tree's contents, but its presence
362 * makes several operations easier. The tree will have one GtkTextBTreeNode,
363 * which is also the root of the tree.
366 /* Create the root node. */
368 root_node = gtk_text_btree_node_new ();
370 line = gtk_text_line_new ();
371 line2 = gtk_text_line_new ();
373 root_node->parent = NULL;
374 root_node->next = NULL;
375 root_node->summary = NULL;
376 root_node->level = 0;
377 root_node->children.line = line;
378 root_node->num_children = 2;
379 root_node->num_lines = 2;
380 root_node->num_chars = 2;
382 line->parent = root_node;
385 line->segments = _gtk_char_segment_new ("\n", 1);
387 line2->parent = root_node;
389 line2->segments = _gtk_char_segment_new ("\n", 1);
391 /* Create the tree itself */
393 tree = g_new0(GtkTextBTree, 1);
394 tree->root_node = root_node;
398 /* Set these to values that are unlikely to be found
399 * in random memory garbage, and also avoid
400 * duplicates between tree instances.
402 tree->chars_changed_stamp = g_random_int ();
403 tree->segments_changed_stamp = g_random_int ();
405 tree->end_iter_line_stamp = tree->chars_changed_stamp - 1;
406 tree->end_iter_line = NULL;
408 g_object_ref (G_OBJECT (tree->table));
410 tree->tag_changed_handler = g_signal_connect_data (G_OBJECT (tree->table),
416 tree->tag_removed_handler = g_signal_connect_data (G_OBJECT (tree->table),
422 tree->mark_table = g_hash_table_new (g_str_hash, g_str_equal);
423 tree->child_anchor_table = NULL;
425 /* We don't ref the buffer, since the buffer owns us;
426 * we'd have some circularity issues. The buffer always
427 * lasts longer than the BTree
429 tree->buffer = buffer;
433 GtkTextLineSegment *seg;
435 _gtk_text_btree_get_iter_at_line_char (tree, &start, 0, 0);
438 tree->insert_mark = _gtk_text_btree_set_mark (tree,
445 seg = tree->insert_mark->segment;
447 seg->body.mark.not_deleteable = TRUE;
448 seg->body.mark.visible = TRUE;
450 tree->selection_bound_mark = _gtk_text_btree_set_mark (tree,
457 seg = tree->selection_bound_mark->segment;
459 seg->body.mark.not_deleteable = TRUE;
461 g_object_ref (G_OBJECT (tree->insert_mark));
462 g_object_ref (G_OBJECT (tree->selection_bound_mark));
471 _gtk_text_btree_ref (GtkTextBTree *tree)
473 g_return_if_fail (tree != NULL);
474 g_return_if_fail (tree->refcount > 0);
480 mark_destroy_foreach (gpointer key, gpointer value, gpointer user_data)
482 GtkTextLineSegment *seg = value;
484 g_return_if_fail (seg->body.mark.tree == NULL);
486 g_object_unref (G_OBJECT (seg->body.mark.obj));
490 _gtk_text_btree_unref (GtkTextBTree *tree)
492 g_return_if_fail (tree != NULL);
493 g_return_if_fail (tree->refcount > 0);
497 if (tree->refcount == 0)
499 gtk_text_btree_node_destroy (tree, tree->root_node);
501 g_hash_table_foreach (tree->mark_table,
502 mark_destroy_foreach,
504 g_hash_table_destroy (tree->mark_table);
506 g_object_unref (G_OBJECT (tree->insert_mark));
507 g_object_unref (G_OBJECT (tree->selection_bound_mark));
509 g_signal_handler_disconnect (G_OBJECT (tree->table),
510 tree->tag_changed_handler);
512 g_signal_handler_disconnect (G_OBJECT (tree->table),
513 tree->tag_removed_handler);
515 g_object_unref (G_OBJECT (tree->table));
522 _gtk_text_btree_get_buffer (GtkTextBTree *tree)
528 _gtk_text_btree_get_chars_changed_stamp (GtkTextBTree *tree)
530 return tree->chars_changed_stamp;
534 _gtk_text_btree_get_segments_changed_stamp (GtkTextBTree *tree)
536 return tree->segments_changed_stamp;
540 _gtk_text_btree_segments_changed (GtkTextBTree *tree)
542 g_return_if_fail (tree != NULL);
543 segments_changed (tree);
547 * Indexable segment mutation
551 _gtk_text_btree_delete (GtkTextIter *start,
554 GtkTextLineSegment *prev_seg; /* The segment just before the start
555 * of the deletion range. */
556 GtkTextLineSegment *last_seg; /* The segment just after the end
557 * of the deletion range. */
558 GtkTextLineSegment *seg, *next;
559 GtkTextLine *curline;
560 GtkTextBTreeNode *curnode, *node;
562 GtkTextLine *start_line;
563 GtkTextLine *end_line;
564 GtkTextLine *deleted_lines = NULL; /* List of lines we've deleted */
565 gint start_byte_offset;
567 g_return_if_fail (start != NULL);
568 g_return_if_fail (end != NULL);
569 g_return_if_fail (gtk_text_iter_get_btree (start) ==
570 gtk_text_iter_get_btree (end));
572 gtk_text_iter_reorder (start, end);
574 tree = gtk_text_iter_get_btree (start);
578 * The code below is ugly, but it's needed to make sure there
579 * is always a dummy empty line at the end of the text. If the
580 * final newline of the file (just before the dummy line) is being
581 * deleted, then back up index to just before the newline. If
582 * there is a newline just before the first character being deleted,
583 * then back up the first index too, so that an even number of lines
584 * gets deleted. Furthermore, remove any tags that are present on
585 * the newline that isn't going to be deleted after all (this simulates
586 * deleting the newline and then adding a "clean" one back again).
592 line1 = gtk_text_iter_get_line (start);
593 line2 = gtk_text_iter_get_line (end);
595 if (line2 == _gtk_text_btree_line_count (tree))
599 GtkTextIter orig_end;
602 gtk_text_iter_backward_char (end);
606 if (gtk_text_iter_get_line_offset (start) == 0 &&
609 gtk_text_iter_backward_char (start);
613 tags = _gtk_text_btree_get_tags (end,
621 while (i < array_size)
623 _gtk_text_btree_tag (end, &orig_end, tags[i], FALSE);
633 /* Broadcast the need for redisplay before we break the iterators */
634 _gtk_text_btree_invalidate_region (tree, start, end);
636 /* Save the byte offset so we can reset the iterators */
637 start_byte_offset = gtk_text_iter_get_line_index (start);
639 start_line = gtk_text_iter_get_text_line (start);
640 end_line = gtk_text_iter_get_text_line (end);
643 * Split the start and end segments, so we have a place
644 * to insert our new text.
646 * Tricky point: split at end first; otherwise the split
647 * at end may invalidate seg and/or prev_seg. This allows
648 * us to avoid invalidating segments for start.
651 last_seg = gtk_text_line_segment_split (end);
652 if (last_seg != NULL)
653 last_seg = last_seg->next;
655 last_seg = end_line->segments;
657 prev_seg = gtk_text_line_segment_split (start);
658 if (prev_seg != NULL)
660 seg = prev_seg->next;
661 prev_seg->next = last_seg;
665 seg = start_line->segments;
666 start_line->segments = last_seg;
669 /* notify iterators that their segments need recomputation,
670 just for robustness. */
671 segments_changed (tree);
674 * Delete all of the segments between prev_seg and last_seg.
677 curline = start_line;
678 curnode = curline->parent;
679 while (seg != last_seg)
685 GtkTextLine *nextline;
688 * We just ran off the end of a line. First find the
689 * next line, then go back to the old line and delete it
690 * (unless it's the starting line for the range).
693 nextline = _gtk_text_line_next (curline);
694 if (curline != start_line)
696 if (curnode == start_line->parent)
697 start_line->next = curline->next;
699 curnode->children.line = curline->next;
701 for (node = curnode; node != NULL;
704 node->num_lines -= 1;
707 curnode->num_children -= 1;
708 curline->next = deleted_lines;
709 deleted_lines = curline;
713 seg = curline->segments;
716 * If the GtkTextBTreeNode is empty then delete it and its parents,
717 * recursively upwards until a non-empty GtkTextBTreeNode is found.
720 while (curnode->num_children == 0)
722 GtkTextBTreeNode *parent;
724 parent = curnode->parent;
725 if (parent->children.node == curnode)
727 parent->children.node = curnode->next;
731 GtkTextBTreeNode *prevnode = parent->children.node;
732 while (prevnode->next != curnode)
734 prevnode = prevnode->next;
736 prevnode->next = curnode->next;
738 parent->num_children--;
742 curnode = curline->parent;
747 char_count = seg->char_count;
749 if ((*seg->type->deleteFunc)(seg, curline, 0) != 0)
752 * This segment refuses to die. Move it to prev_seg and
753 * advance prev_seg if the segment has left gravity.
756 if (prev_seg == NULL)
758 seg->next = start_line->segments;
759 start_line->segments = seg;
763 seg->next = prev_seg->next;
764 prev_seg->next = seg;
766 if (seg->type->leftGravity)
773 /* Segment is gone. Decrement the char count of the node and
775 for (node = curnode; node != NULL;
778 node->num_chars -= char_count;
786 * If the beginning and end of the deletion range are in different
787 * lines, join the two lines together and discard the ending line.
790 if (start_line != end_line)
793 GtkTextBTreeNode *ancestor_node;
795 GtkTextLine *prevline;
797 for (seg = last_seg; seg != NULL;
800 if (seg->type->lineChangeFunc != NULL)
802 (*seg->type->lineChangeFunc)(seg, end_line);
805 curnode = end_line->parent;
806 for (node = curnode; node != NULL;
811 curnode->num_children--;
812 prevline = curnode->children.line;
813 if (prevline == end_line)
815 curnode->children.line = end_line->next;
819 while (prevline->next != end_line)
821 prevline = prevline->next;
823 prevline->next = end_line->next;
825 end_line->next = deleted_lines;
826 deleted_lines = end_line;
828 /* We now fix up the per-view aggregates. We add all the height and
829 * width for the deleted lines to the start line, so that when revalidation
830 * occurs, the correct change in size is seen.
832 ancestor_node = gtk_text_btree_node_common_parent (curnode, start_line->parent);
839 gint deleted_width = 0;
840 gint deleted_height = 0;
842 line = deleted_lines;
845 GtkTextLine *next_line = line->next;
846 ld = _gtk_text_line_get_data (line, view->view_id);
850 deleted_width = MAX (deleted_width, ld->width);
851 deleted_height += ld->height;
855 gtk_text_line_destroy (tree, line);
860 if (deleted_width > 0 || deleted_height > 0)
862 ld = _gtk_text_line_get_data (start_line, view->view_id);
864 /* FIXME: ld is _NOT_ necessarily non-null here, but there is currently
865 * no way to add ld without also validating the node, which would
866 * be improper at this point.
868 /* This assertion does actually fail sometimes, must
869 fix before stable release -hp */
872 ld->width = MAX (deleted_width, ld->width);
873 ld->height += deleted_height;
877 gtk_text_btree_node_check_valid_downward (ancestor_node, view->view_id);
878 if (ancestor_node->parent)
879 gtk_text_btree_node_check_valid_upward (ancestor_node->parent, view->view_id);
884 gtk_text_btree_rebalance (tree, curnode);
888 * Cleanup the segments in the new line.
891 cleanup_line (start_line);
894 * Lastly, rebalance the first GtkTextBTreeNode of the range.
897 gtk_text_btree_rebalance (tree, start_line->parent);
899 /* Notify outstanding iterators that they
901 chars_changed (tree);
902 segments_changed (tree);
904 if (gtk_debug_flags & GTK_DEBUG_TEXT)
905 _gtk_text_btree_check (tree);
907 /* Re-initialize our iterators */
908 _gtk_text_btree_get_iter_at_line (tree, start, start_line, start_byte_offset);
913 _gtk_text_btree_insert (GtkTextIter *iter,
917 GtkTextLineSegment *prev_seg; /* The segment just before the first
918 * new segment (NULL means new segment
919 * is at beginning of line). */
920 GtkTextLineSegment *cur_seg; /* Current segment; new characters
921 * are inserted just after this one.
922 * NULL means insert at beginning of
924 GtkTextLine *line; /* Current line (new segments are
925 * added to this line). */
926 GtkTextLineSegment *seg;
927 GtkTextLine *newline;
928 int chunk_len; /* # characters in current chunk. */
929 gint sol; /* start of line */
930 gint eol; /* Pointer to character just after last
931 * one in current chunk.
933 gint delim; /* index of paragraph delimiter */
934 int line_count_delta; /* Counts change to total number of
938 int char_count_delta; /* change to number of chars */
940 gint start_byte_index;
941 GtkTextLine *start_line;
943 g_return_if_fail (text != NULL);
944 g_return_if_fail (iter != NULL);
949 /* extract iterator info */
950 tree = gtk_text_iter_get_btree (iter);
951 line = gtk_text_iter_get_text_line (iter);
953 start_byte_index = gtk_text_iter_get_line_index (iter);
955 /* Get our insertion segment split */
956 prev_seg = gtk_text_line_segment_split (iter);
959 /* Invalidate all iterators */
960 chars_changed (tree);
961 segments_changed (tree);
963 g_assert (g_utf8_validate (text, len, NULL));
966 * Chop the text up into lines and create a new segment for
967 * each line, plus a new line for the leftovers from the
973 line_count_delta = 0;
974 char_count_delta = 0;
979 pango_find_paragraph_boundary (text + sol,
984 /* make these relative to the start of the text */
988 g_assert (eol >= sol);
989 g_assert (delim >= sol);
990 g_assert (eol >= delim);
992 g_assert (eol <= len);
994 chunk_len = eol - sol;
996 g_assert (g_utf8_validate (&text[sol], chunk_len, NULL));
997 seg = _gtk_char_segment_new (&text[sol], chunk_len);
999 char_count_delta += seg->char_count;
1001 if (cur_seg == NULL)
1003 seg->next = line->segments;
1004 line->segments = seg;
1008 seg->next = cur_seg->next;
1009 cur_seg->next = seg;
1014 /* chunk didn't end with a paragraph separator */
1015 g_assert (eol == len);
1020 * The chunk ended with a newline, so create a new GtkTextLine
1021 * and move the remainder of the old line to it.
1024 newline = gtk_text_line_new ();
1025 gtk_text_line_set_parent (newline, line->parent);
1026 newline->next = line->next;
1027 line->next = newline;
1028 newline->segments = seg->next;
1036 * Cleanup the starting line for the insertion, plus the ending
1037 * line if it's different.
1040 cleanup_line (start_line);
1041 if (line != start_line)
1043 cleanup_line (line);
1046 post_insert_fixup (tree, line, line_count_delta, char_count_delta);
1048 /* Invalidate our region, and reset the iterator the user
1049 passed in to point to the end of the inserted text. */
1055 _gtk_text_btree_get_iter_at_line (tree,
1061 /* We could almost certainly be more efficient here
1062 by saving the information from the insertion loop
1064 gtk_text_iter_forward_chars (&end, char_count_delta);
1066 _gtk_text_btree_invalidate_region (tree,
1070 /* Convenience for the user */
1076 insert_pixbuf_or_widget_segment (GtkTextIter *iter,
1077 GtkTextLineSegment *seg)
1081 GtkTextLineSegment *prevPtr;
1084 gint start_byte_offset;
1086 line = gtk_text_iter_get_text_line (iter);
1087 tree = gtk_text_iter_get_btree (iter);
1088 start_byte_offset = gtk_text_iter_get_line_index (iter);
1090 prevPtr = gtk_text_line_segment_split (iter);
1091 if (prevPtr == NULL)
1093 seg->next = line->segments;
1094 line->segments = seg;
1098 seg->next = prevPtr->next;
1099 prevPtr->next = seg;
1102 post_insert_fixup (tree, line, 0, seg->char_count);
1104 chars_changed (tree);
1105 segments_changed (tree);
1107 /* reset *iter for the user, and invalidate tree nodes */
1109 _gtk_text_btree_get_iter_at_line (tree, &start, line, start_byte_offset);
1112 gtk_text_iter_forward_char (iter); /* skip forward past the segment */
1114 _gtk_text_btree_invalidate_region (tree, &start, iter);
1118 _gtk_text_btree_insert_pixbuf (GtkTextIter *iter,
1121 GtkTextLineSegment *seg;
1123 seg = _gtk_pixbuf_segment_new (pixbuf);
1125 insert_pixbuf_or_widget_segment (iter, seg);
1129 _gtk_text_btree_create_child_anchor (GtkTextIter *iter)
1131 GtkTextLineSegment *seg;
1134 seg = _gtk_widget_segment_new ();
1136 tree = seg->body.child.tree = gtk_text_iter_get_btree (iter);
1138 insert_pixbuf_or_widget_segment (iter, seg);
1140 if (tree->child_anchor_table == NULL)
1141 tree->child_anchor_table = g_hash_table_new (NULL, NULL);
1143 g_hash_table_insert (tree->child_anchor_table,
1144 seg->body.child.obj,
1145 seg->body.child.obj);
1147 return seg->body.child.obj;
1151 _gtk_text_btree_unregister_child_anchor (GtkTextChildAnchor *anchor)
1153 GtkTextLineSegment *seg;
1155 seg = anchor->segment;
1157 g_hash_table_remove (seg->body.child.tree->child_anchor_table,
1166 find_line_by_y (GtkTextBTree *tree, BTreeView *view,
1167 GtkTextBTreeNode *node, gint y, gint *line_top,
1168 GtkTextLine *last_line)
1172 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1173 _gtk_text_btree_check (tree);
1175 if (node->level == 0)
1179 line = node->children.line;
1181 while (line != NULL && line != last_line)
1183 GtkTextLineData *ld;
1185 ld = _gtk_text_line_get_data (line, view->view_id);
1189 if (y < (current_y + (ld ? ld->height : 0)))
1192 current_y += ld->height;
1193 *line_top += ld->height;
1202 GtkTextBTreeNode *child;
1204 child = node->children.node;
1206 while (child != NULL)
1211 gtk_text_btree_node_get_size (child, view->view_id,
1214 if (y < (current_y + height))
1215 return find_line_by_y (tree, view, child,
1216 y - current_y, line_top,
1219 current_y += height;
1220 *line_top += height;
1222 child = child->next;
1230 _gtk_text_btree_find_line_by_y (GtkTextBTree *tree,
1237 GtkTextLine *last_line;
1240 view = gtk_text_btree_get_view (tree, view_id);
1241 g_return_val_if_fail (view != NULL, NULL);
1243 last_line = get_last_line (tree);
1245 line = find_line_by_y (tree, view, tree->root_node, ypixel, &line_top,
1249 *line_top_out = line_top;
1255 find_line_top_in_line_list (GtkTextBTree *tree,
1258 GtkTextLine *target_line,
1261 while (line != NULL)
1263 GtkTextLineData *ld;
1265 if (line == target_line)
1268 ld = _gtk_text_line_get_data (line, view->view_id);
1275 g_assert_not_reached (); /* If we get here, our
1276 target line didn't exist
1277 under its parent node */
1282 _gtk_text_btree_find_line_top (GtkTextBTree *tree,
1283 GtkTextLine *target_line,
1290 GtkTextBTreeNode *node;
1292 view = gtk_text_btree_get_view (tree, view_id);
1294 g_return_val_if_fail (view != NULL, 0);
1297 node = target_line->parent;
1298 while (node != NULL)
1300 nodes = g_slist_prepend (nodes, node);
1301 node = node->parent;
1305 while (iter != NULL)
1309 if (node->level == 0)
1311 g_slist_free (nodes);
1312 return find_line_top_in_line_list (tree, view,
1313 node->children.line,
1318 GtkTextBTreeNode *child;
1319 GtkTextBTreeNode *target_node;
1321 g_assert (iter->next != NULL); /* not at level 0 */
1322 target_node = iter->next->data;
1324 child = node->children.node;
1326 while (child != NULL)
1331 if (child == target_node)
1335 gtk_text_btree_node_get_size (child, view->view_id,
1339 child = child->next;
1341 g_assert (child != NULL); /* should have broken out before we
1345 iter = g_slist_next (iter);
1348 g_assert_not_reached (); /* we return when we find the target line */
1353 _gtk_text_btree_add_view (GtkTextBTree *tree,
1354 GtkTextLayout *layout)
1357 GtkTextLine *last_line;
1358 GtkTextLineData *line_data;
1360 g_return_if_fail (tree != NULL);
1362 view = g_new (BTreeView, 1);
1364 view->view_id = layout;
1365 view->layout = layout;
1367 view->next = tree->views;
1372 /* The last line in the buffer has identity values for the per-view
1373 * data so that we can avoid special case checks for it in a large
1376 last_line = get_last_line (tree);
1378 line_data = g_new (GtkTextLineData, 1);
1379 line_data->view_id = layout;
1380 line_data->next = NULL;
1381 line_data->width = 0;
1382 line_data->height = 0;
1383 line_data->valid = TRUE;
1385 _gtk_text_line_add_data (last_line, line_data);
1389 _gtk_text_btree_remove_view (GtkTextBTree *tree,
1393 GtkTextLine *last_line;
1394 GtkTextLineData *line_data;
1396 g_return_if_fail (tree != NULL);
1400 while (view != NULL)
1402 if (view->view_id == view_id)
1408 g_return_if_fail (view != NULL);
1411 view->next->prev = view->prev;
1414 view->prev->next = view->next;
1416 if (view == tree->views)
1417 tree->views = view->next;
1419 /* Remove the line data for the last line which we added ourselves.
1420 * (Do this first, so that we don't try to call the view's line data destructor on it.)
1422 last_line = get_last_line (tree);
1423 line_data = _gtk_text_line_remove_data (last_line, view_id);
1426 gtk_text_btree_node_remove_view (view, tree->root_node, view_id);
1432 _gtk_text_btree_invalidate_region (GtkTextBTree *tree,
1433 const GtkTextIter *start,
1434 const GtkTextIter *end)
1440 while (view != NULL)
1442 gtk_text_layout_invalidate (view->layout, start, end);
1449 _gtk_text_btree_get_view_size (GtkTextBTree *tree,
1454 g_return_if_fail (tree != NULL);
1455 g_return_if_fail (view_id != NULL);
1457 gtk_text_btree_node_get_size (tree->root_node, view_id,
1472 iter_stack_new (void)
1475 stack = g_new (IterStack, 1);
1476 stack->iters = NULL;
1483 iter_stack_push (IterStack *stack, const GtkTextIter *iter)
1486 if (stack->count > stack->alloced)
1488 stack->alloced = stack->count*2;
1489 stack->iters = g_realloc (stack->iters,
1490 stack->alloced*sizeof (GtkTextIter));
1492 stack->iters[stack->count-1] = *iter;
1496 iter_stack_pop (IterStack *stack, GtkTextIter *iter)
1498 if (stack->count == 0)
1503 *iter = stack->iters[stack->count];
1509 iter_stack_free (IterStack *stack)
1511 g_free (stack->iters);
1516 iter_stack_invert (IterStack *stack)
1518 if (stack->count > 0)
1521 guint j = stack->count - 1;
1526 tmp = stack->iters[i];
1527 stack->iters[i] = stack->iters[j];
1528 stack->iters[j] = tmp;
1537 queue_tag_redisplay (GtkTextBTree *tree,
1539 const GtkTextIter *start,
1540 const GtkTextIter *end)
1542 if (gtk_text_tag_affects_size (tag))
1544 _gtk_text_btree_invalidate_region (tree, start, end);
1547 else if (gtk_text_tag_affects_nonsize_appearance (tag))
1549 /* We only need to queue a redraw, not a relayout */
1550 redisplay_region (tree, start, end);
1553 /* We don't need to do anything if the tag doesn't affect display */
1557 _gtk_text_btree_tag (const GtkTextIter *start_orig,
1558 const GtkTextIter *end_orig,
1562 GtkTextLineSegment *seg, *prev;
1563 GtkTextLine *cleanupline;
1564 gboolean toggled_on;
1565 GtkTextLine *start_line;
1566 GtkTextLine *end_line;
1568 GtkTextIter start, end;
1571 GtkTextTagInfo *info;
1573 g_return_if_fail (start_orig != NULL);
1574 g_return_if_fail (end_orig != NULL);
1575 g_return_if_fail (GTK_IS_TEXT_TAG (tag));
1576 g_return_if_fail (gtk_text_iter_get_btree (start_orig) ==
1577 gtk_text_iter_get_btree (end_orig));
1580 printf ("%s tag %s from %d to %d\n",
1581 add ? "Adding" : "Removing",
1583 gtk_text_buffer_get_offset (start_orig),
1584 gtk_text_buffer_get_offset (end_orig));
1587 if (gtk_text_iter_equal (start_orig, end_orig))
1590 start = *start_orig;
1593 gtk_text_iter_reorder (&start, &end);
1595 tree = gtk_text_iter_get_btree (&start);
1597 queue_tag_redisplay (tree, tag, &start, &end);
1599 info = gtk_text_btree_get_tag_info (tree, tag);
1601 start_line = gtk_text_iter_get_text_line (&start);
1602 end_line = gtk_text_iter_get_text_line (&end);
1604 /* Find all tag toggles in the region; we are going to delete them.
1605 We need to find them in advance, because
1606 forward_find_tag_toggle () won't work once we start playing around
1608 stack = iter_stack_new ();
1610 /* We don't want to delete a toggle that's at the start iterator. */
1611 gtk_text_iter_forward_char (&iter);
1612 while (gtk_text_iter_forward_to_tag_toggle (&iter, tag))
1614 if (gtk_text_iter_compare (&iter, &end) >= 0)
1617 iter_stack_push (stack, &iter);
1620 /* We need to traverse the toggles in order. */
1621 iter_stack_invert (stack);
1624 * See whether the tag is present at the start of the range. If
1625 * the state doesn't already match what we want then add a toggle
1629 toggled_on = gtk_text_iter_has_tag (&start, tag);
1630 if ( (add && !toggled_on) ||
1631 (!add && toggled_on) )
1633 /* This could create a second toggle at the start position;
1634 cleanup_line () will remove it if so. */
1635 seg = _gtk_toggle_segment_new (info, add);
1637 prev = gtk_text_line_segment_split (&start);
1640 seg->next = start_line->segments;
1641 start_line->segments = seg;
1645 seg->next = prev->next;
1649 /* cleanup_line adds the new toggle to the node counts. */
1651 printf ("added toggle at start\n");
1653 /* we should probably call segments_changed, but in theory
1654 any still-cached segments in the iters we are about to
1655 use are still valid, since they're in front
1661 * Scan the range of characters and delete any internal tag
1662 * transitions. Keep track of what the old state was at the end
1663 * of the range, and add a toggle there if it's needed.
1667 cleanupline = start_line;
1668 while (iter_stack_pop (stack, &iter))
1670 GtkTextLineSegment *indexable_seg;
1673 line = gtk_text_iter_get_text_line (&iter);
1674 seg = gtk_text_iter_get_any_segment (&iter);
1675 indexable_seg = gtk_text_iter_get_indexable_segment (&iter);
1677 g_assert (seg != NULL);
1678 g_assert (indexable_seg != NULL);
1679 g_assert (seg != indexable_seg);
1681 prev = line->segments;
1683 /* Find the segment that actually toggles this tag. */
1684 while (seg != indexable_seg)
1686 g_assert (seg != NULL);
1687 g_assert (indexable_seg != NULL);
1688 g_assert (seg != indexable_seg);
1690 if ( (seg->type == >k_text_toggle_on_type ||
1691 seg->type == >k_text_toggle_off_type) &&
1692 (seg->body.toggle.info == info) )
1698 g_assert (seg != NULL);
1699 g_assert (indexable_seg != NULL);
1701 g_assert (seg != indexable_seg); /* If this happens, then
1702 forward_to_tag_toggle was
1704 g_assert (seg->body.toggle.info->tag == tag);
1706 /* If this happens, when previously tagging we didn't merge
1707 overlapping tags. */
1708 g_assert ( (toggled_on && seg->type == >k_text_toggle_off_type) ||
1709 (!toggled_on && seg->type == >k_text_toggle_on_type) );
1711 toggled_on = !toggled_on;
1714 printf ("deleting %s toggle\n",
1715 seg->type == >k_text_toggle_on_type ? "on" : "off");
1717 /* Remove toggle segment from the list. */
1720 line->segments = seg->next;
1724 while (prev->next != seg)
1728 prev->next = seg->next;
1731 /* Inform iterators we've hosed them. This actually reflects a
1732 bit of inefficiency; if you have the same tag toggled on and
1733 off a lot in a single line, we keep having the rescan from
1734 the front of the line. Of course we have to do that to get
1735 "prev" anyway, but here we are doing it an additional
1737 segments_changed (tree);
1739 /* Update node counts */
1740 if (seg->body.toggle.inNodeCounts)
1742 _gtk_change_node_toggle_count (line->parent,
1744 seg->body.toggle.inNodeCounts = FALSE;
1749 /* We only clean up lines when we're done with them, saves some
1750 gratuitous line-segment-traversals */
1752 if (cleanupline != line)
1754 cleanup_line (cleanupline);
1759 iter_stack_free (stack);
1761 /* toggled_on now reflects the toggle state _just before_ the
1762 end iterator. The end iterator could already have a toggle
1763 on or a toggle off. */
1764 if ( (add && !toggled_on) ||
1765 (!add && toggled_on) )
1767 /* This could create a second toggle at the start position;
1768 cleanup_line () will remove it if so. */
1770 seg = _gtk_toggle_segment_new (info, !add);
1772 prev = gtk_text_line_segment_split (&end);
1775 seg->next = end_line->segments;
1776 end_line->segments = seg;
1780 seg->next = prev->next;
1783 /* cleanup_line adds the new toggle to the node counts. */
1784 g_assert (seg->body.toggle.inNodeCounts == FALSE);
1786 printf ("added toggle at end\n");
1791 * Cleanup cleanupline and the last line of the range, if
1792 * these are different.
1795 cleanup_line (cleanupline);
1796 if (cleanupline != end_line)
1798 cleanup_line (end_line);
1801 segments_changed (tree);
1803 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1804 _gtk_text_btree_check (tree);
1813 _gtk_text_btree_get_line (GtkTextBTree *tree,
1815 gint *real_line_number)
1817 GtkTextBTreeNode *node;
1822 line_count = _gtk_text_btree_line_count (tree);
1824 if (line_number < 0)
1826 line_number = line_count;
1828 else if (line_number > line_count)
1830 line_number = line_count;
1833 if (real_line_number)
1834 *real_line_number = line_number;
1836 node = tree->root_node;
1837 lines_left = line_number;
1840 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1844 while (node->level != 0)
1846 for (node = node->children.node;
1847 node->num_lines <= lines_left;
1853 g_error ("gtk_text_btree_find_line ran out of GtkTextBTreeNodes");
1856 lines_left -= node->num_lines;
1861 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1864 for (line = node->children.line; lines_left > 0;
1870 g_error ("gtk_text_btree_find_line ran out of lines");
1879 _gtk_text_btree_get_line_at_char (GtkTextBTree *tree,
1881 gint *line_start_index,
1882 gint *real_char_index)
1884 GtkTextBTreeNode *node;
1886 GtkTextLineSegment *seg;
1891 node = tree->root_node;
1893 /* Clamp to valid indexes (-1 is magic for "highest index") */
1894 if (char_index < 0 || char_index >= node->num_chars)
1896 char_index = node->num_chars - 1;
1899 *real_char_index = char_index;
1902 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1906 chars_left = char_index;
1907 while (node->level != 0)
1909 for (node = node->children.node;
1910 chars_left >= node->num_chars;
1913 chars_left -= node->num_chars;
1915 g_assert (chars_left >= 0);
1919 if (chars_left == 0)
1921 /* Start of a line */
1923 *line_start_index = char_index;
1924 return node->children.line;
1928 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1934 for (line = node->children.line; line != NULL; line = line->next)
1936 seg = line->segments;
1939 if (chars_in_line + seg->char_count > chars_left)
1940 goto found; /* found our line/segment */
1942 chars_in_line += seg->char_count;
1947 chars_left -= chars_in_line;
1955 g_assert (line != NULL); /* hosage, ran out of lines */
1956 g_assert (seg != NULL);
1958 *line_start_index = char_index - chars_left;
1963 _gtk_text_btree_get_tags (const GtkTextIter *iter,
1966 GtkTextBTreeNode *node;
1967 GtkTextLine *siblingline;
1968 GtkTextLineSegment *seg;
1969 int src, dst, index;
1975 #define NUM_TAG_INFOS 10
1977 line = gtk_text_iter_get_text_line (iter);
1978 tree = gtk_text_iter_get_btree (iter);
1979 byte_index = gtk_text_iter_get_line_index (iter);
1981 tagInfo.numTags = 0;
1982 tagInfo.arraySize = NUM_TAG_INFOS;
1983 tagInfo.tags = g_new (GtkTextTag*, NUM_TAG_INFOS);
1984 tagInfo.counts = g_new (int, NUM_TAG_INFOS);
1987 * Record tag toggles within the line of indexPtr but preceding
1988 * indexPtr. Note that if this loop segfaults, your
1989 * byte_index probably points past the sum of all
1990 * seg->byte_count */
1992 for (index = 0, seg = line->segments;
1993 (index + seg->byte_count) <= byte_index;
1994 index += seg->byte_count, seg = seg->next)
1996 if ((seg->type == >k_text_toggle_on_type)
1997 || (seg->type == >k_text_toggle_off_type))
1999 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2004 * Record toggles for tags in lines that are predecessors of
2005 * line but under the same level-0 GtkTextBTreeNode.
2008 for (siblingline = line->parent->children.line;
2009 siblingline != line;
2010 siblingline = siblingline->next)
2012 for (seg = siblingline->segments; seg != NULL;
2015 if ((seg->type == >k_text_toggle_on_type)
2016 || (seg->type == >k_text_toggle_off_type))
2018 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2024 * For each GtkTextBTreeNode in the ancestry of this line, record tag
2025 * toggles for all siblings that precede that GtkTextBTreeNode.
2028 for (node = line->parent; node->parent != NULL;
2029 node = node->parent)
2031 GtkTextBTreeNode *siblingPtr;
2034 for (siblingPtr = node->parent->children.node;
2035 siblingPtr != node; siblingPtr = siblingPtr->next)
2037 for (summary = siblingPtr->summary; summary != NULL;
2038 summary = summary->next)
2040 if (summary->toggle_count & 1)
2042 inc_count (summary->info->tag, summary->toggle_count,
2050 * Go through the tag information and squash out all of the tags
2051 * that have even toggle counts (these tags exist before the point
2052 * of interest, but not at the desired character itself).
2055 for (src = 0, dst = 0; src < tagInfo.numTags; src++)
2057 if (tagInfo.counts[src] & 1)
2059 g_assert (GTK_IS_TEXT_TAG (tagInfo.tags[src]));
2060 tagInfo.tags[dst] = tagInfo.tags[src];
2066 g_free (tagInfo.counts);
2069 g_free (tagInfo.tags);
2072 return tagInfo.tags;
2076 copy_segment (GString *string,
2077 gboolean include_hidden,
2078 gboolean include_nonchars,
2079 const GtkTextIter *start,
2080 const GtkTextIter *end)
2082 GtkTextLineSegment *end_seg;
2083 GtkTextLineSegment *seg;
2085 if (gtk_text_iter_equal (start, end))
2088 seg = gtk_text_iter_get_indexable_segment (start);
2089 end_seg = gtk_text_iter_get_indexable_segment (end);
2091 if (seg->type == >k_text_char_type)
2093 gboolean copy = TRUE;
2094 gint copy_bytes = 0;
2095 gint copy_start = 0;
2097 /* Don't copy if we're invisible; segments are invisible/not
2098 as a whole, no need to check each char */
2099 if (!include_hidden &&
2100 _gtk_text_btree_char_is_invisible (start))
2103 /* printf (" <invisible>\n"); */
2106 copy_start = gtk_text_iter_get_segment_byte (start);
2110 /* End is in the same segment; need to copy fewer bytes. */
2111 gint end_byte = gtk_text_iter_get_segment_byte (end);
2113 copy_bytes = end_byte - copy_start;
2116 copy_bytes = seg->byte_count - copy_start;
2118 g_assert (copy_bytes != 0); /* Due to iter equality check at
2119 front of this function. */
2123 g_assert ((copy_start + copy_bytes) <= seg->byte_count);
2125 g_string_append_len (string,
2126 seg->body.chars + copy_start,
2130 /* printf (" :%s\n", string->str); */
2132 else if (seg->type == >k_text_pixbuf_type ||
2133 seg->type == >k_text_child_type)
2135 gboolean copy = TRUE;
2137 if (!include_nonchars)
2141 else if (!include_hidden &&
2142 _gtk_text_btree_char_is_invisible (start))
2149 g_string_append_len (string,
2150 gtk_text_unknown_char_utf8,
2158 _gtk_text_btree_get_text (const GtkTextIter *start_orig,
2159 const GtkTextIter *end_orig,
2160 gboolean include_hidden,
2161 gboolean include_nonchars)
2163 GtkTextLineSegment *seg;
2164 GtkTextLineSegment *end_seg;
2172 g_return_val_if_fail (start_orig != NULL, NULL);
2173 g_return_val_if_fail (end_orig != NULL, NULL);
2174 g_return_val_if_fail (gtk_text_iter_get_btree (start_orig) ==
2175 gtk_text_iter_get_btree (end_orig), NULL);
2177 start = *start_orig;
2180 gtk_text_iter_reorder (&start, &end);
2182 retval = g_string_new ("");
2184 tree = gtk_text_iter_get_btree (&start);
2186 end_seg = gtk_text_iter_get_indexable_segment (&end);
2188 seg = gtk_text_iter_get_indexable_segment (&iter);
2189 while (seg != end_seg)
2191 copy_segment (retval, include_hidden, include_nonchars,
2194 gtk_text_iter_forward_indexable_segment (&iter);
2196 seg = gtk_text_iter_get_indexable_segment (&iter);
2199 copy_segment (retval, include_hidden, include_nonchars, &iter, &end);
2202 g_string_free (retval, FALSE);
2207 _gtk_text_btree_line_count (GtkTextBTree *tree)
2209 /* Subtract bogus line at the end; we return a count
2211 return tree->root_node->num_lines - 1;
2215 _gtk_text_btree_char_count (GtkTextBTree *tree)
2217 /* Exclude newline in bogus last line */
2218 return tree->root_node->num_chars - 1;
2221 #define LOTSA_TAGS 1000
2223 _gtk_text_btree_char_is_invisible (const GtkTextIter *iter)
2225 gboolean invisible = FALSE; /* if nobody says otherwise, it's visible */
2227 int deftagCnts[LOTSA_TAGS];
2228 int *tagCnts = deftagCnts;
2229 GtkTextTag *deftags[LOTSA_TAGS];
2230 GtkTextTag **tags = deftags;
2232 GtkTextBTreeNode *node;
2233 GtkTextLine *siblingline;
2234 GtkTextLineSegment *seg;
2241 line = gtk_text_iter_get_text_line (iter);
2242 tree = gtk_text_iter_get_btree (iter);
2243 byte_index = gtk_text_iter_get_line_index (iter);
2245 numTags = gtk_text_tag_table_size (tree->table);
2247 /* almost always avoid malloc, so stay out of system calls */
2248 if (LOTSA_TAGS < numTags)
2250 tagCnts = g_new (int, numTags);
2251 tags = g_new (GtkTextTag*, numTags);
2254 for (i=0; i<numTags; i++)
2260 * Record tag toggles within the line of indexPtr but preceding
2264 for (index = 0, seg = line->segments;
2265 (index + seg->byte_count) <= byte_index; /* segfault here means invalid index */
2266 index += seg->byte_count, seg = seg->next)
2268 if ((seg->type == >k_text_toggle_on_type)
2269 || (seg->type == >k_text_toggle_off_type))
2271 tag = seg->body.toggle.info->tag;
2272 if (tag->invisible_set && tag->values->invisible)
2274 tags[tag->priority] = tag;
2275 tagCnts[tag->priority]++;
2281 * Record toggles for tags in lines that are predecessors of
2282 * line but under the same level-0 GtkTextBTreeNode.
2285 for (siblingline = line->parent->children.line;
2286 siblingline != line;
2287 siblingline = siblingline->next)
2289 for (seg = siblingline->segments; seg != NULL;
2292 if ((seg->type == >k_text_toggle_on_type)
2293 || (seg->type == >k_text_toggle_off_type))
2295 tag = seg->body.toggle.info->tag;
2296 if (tag->invisible_set && tag->values->invisible)
2298 tags[tag->priority] = tag;
2299 tagCnts[tag->priority]++;
2306 * For each GtkTextBTreeNode in the ancestry of this line, record tag toggles
2307 * for all siblings that precede that GtkTextBTreeNode.
2310 for (node = line->parent; node->parent != NULL;
2311 node = node->parent)
2313 GtkTextBTreeNode *siblingPtr;
2316 for (siblingPtr = node->parent->children.node;
2317 siblingPtr != node; siblingPtr = siblingPtr->next)
2319 for (summary = siblingPtr->summary; summary != NULL;
2320 summary = summary->next)
2322 if (summary->toggle_count & 1)
2324 tag = summary->info->tag;
2325 if (tag->invisible_set && tag->values->invisible)
2327 tags[tag->priority] = tag;
2328 tagCnts[tag->priority] += summary->toggle_count;
2336 * Now traverse from highest priority to lowest,
2337 * take invisible value from first odd count (= on)
2340 for (i = numTags-1; i >=0; i--)
2344 /* FIXME not sure this should be if 0 */
2346 #ifndef ALWAYS_SHOW_SELECTION
2347 /* who would make the selection invisible? */
2348 if ((tag == tkxt->seltag)
2349 && !(tkxt->flags & GOT_FOCUS))
2355 invisible = tags[i]->values->invisible;
2360 if (LOTSA_TAGS < numTags)
2375 redisplay_region (GtkTextBTree *tree,
2376 const GtkTextIter *start,
2377 const GtkTextIter *end)
2380 GtkTextLine *start_line, *end_line;
2382 if (gtk_text_iter_compare (start, end) > 0)
2384 const GtkTextIter *tmp = start;
2389 start_line = gtk_text_iter_get_text_line (start);
2390 end_line = gtk_text_iter_get_text_line (end);
2393 while (view != NULL)
2395 gint start_y, end_y;
2396 GtkTextLineData *ld;
2398 start_y = _gtk_text_btree_find_line_top (tree, start_line, view->view_id);
2400 if (end_line == start_line)
2403 end_y = _gtk_text_btree_find_line_top (tree, end_line, view->view_id);
2405 ld = _gtk_text_line_get_data (end_line, view->view_id);
2407 end_y += ld->height;
2409 gtk_text_layout_changed (view->layout, start_y,
2418 redisplay_mark (GtkTextLineSegment *mark)
2423 _gtk_text_btree_get_iter_at_mark (mark->body.mark.tree,
2425 mark->body.mark.obj);
2428 gtk_text_iter_forward_char (&end);
2430 _gtk_text_btree_invalidate_region (mark->body.mark.tree,
2435 redisplay_mark_if_visible (GtkTextLineSegment *mark)
2437 if (!mark->body.mark.visible)
2440 redisplay_mark (mark);
2444 ensure_not_off_end (GtkTextBTree *tree,
2445 GtkTextLineSegment *mark,
2448 if (gtk_text_iter_get_line (iter) ==
2449 _gtk_text_btree_line_count (tree))
2450 gtk_text_iter_backward_char (iter);
2453 static GtkTextLineSegment*
2454 real_set_mark (GtkTextBTree *tree,
2455 GtkTextMark *existing_mark,
2457 gboolean left_gravity,
2458 const GtkTextIter *where,
2459 gboolean should_exist,
2460 gboolean redraw_selections)
2462 GtkTextLineSegment *mark;
2465 g_return_val_if_fail (tree != NULL, NULL);
2466 g_return_val_if_fail (where != NULL, NULL);
2467 g_return_val_if_fail (gtk_text_iter_get_btree (where) == tree, NULL);
2470 mark = existing_mark->segment;
2471 else if (name != NULL)
2472 mark = g_hash_table_lookup (tree->mark_table,
2477 if (should_exist && mark == NULL)
2479 g_warning ("No mark `%s' exists!", name);
2483 /* OK if !should_exist and it does already exist, in that case
2489 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2490 gtk_text_iter_check (&iter);
2494 if (redraw_selections &&
2495 (mark == tree->insert_mark->segment ||
2496 mark == tree->selection_bound_mark->segment))
2498 GtkTextIter old_pos;
2500 _gtk_text_btree_get_iter_at_mark (tree, &old_pos,
2501 mark->body.mark.obj);
2502 redisplay_region (tree, &old_pos, where);
2506 * don't let visible marks be after the final newline of the
2510 if (mark->body.mark.visible)
2512 ensure_not_off_end (tree, mark, &iter);
2515 /* Redraw the mark's old location. */
2516 redisplay_mark_if_visible (mark);
2518 /* Unlink mark from its current location.
2519 This could hose our iterator... */
2520 gtk_text_btree_unlink_segment (tree, mark,
2521 mark->body.mark.line);
2522 mark->body.mark.line = gtk_text_iter_get_text_line (&iter);
2523 g_assert (mark->body.mark.line == gtk_text_iter_get_text_line (&iter));
2525 segments_changed (tree); /* make sure the iterator recomputes its
2530 mark = _gtk_mark_segment_new (tree,
2534 mark->body.mark.line = gtk_text_iter_get_text_line (&iter);
2536 if (mark->body.mark.name)
2537 g_hash_table_insert (tree->mark_table,
2538 mark->body.mark.name,
2542 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2543 gtk_text_iter_check (&iter);
2545 /* Link mark into new location */
2546 gtk_text_btree_link_segment (mark, &iter);
2548 /* Invalidate some iterators. */
2549 segments_changed (tree);
2552 * update the screen at the mark's new location.
2555 redisplay_mark_if_visible (mark);
2557 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2558 gtk_text_iter_check (&iter);
2560 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2561 _gtk_text_btree_check (tree);
2568 _gtk_text_btree_set_mark (GtkTextBTree *tree,
2569 GtkTextMark *existing_mark,
2571 gboolean left_gravity,
2572 const GtkTextIter *iter,
2573 gboolean should_exist)
2575 GtkTextLineSegment *seg;
2577 seg = real_set_mark (tree, existing_mark,
2578 name, left_gravity, iter, should_exist,
2581 return seg ? seg->body.mark.obj : NULL;
2585 _gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2589 GtkTextIter tmp_start, tmp_end;
2591 _gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2593 _gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2594 tree->selection_bound_mark);
2596 if (gtk_text_iter_equal (&tmp_start, &tmp_end))
2608 gtk_text_iter_reorder (&tmp_start, &tmp_end);
2621 _gtk_text_btree_place_cursor (GtkTextBTree *tree,
2622 const GtkTextIter *iter)
2624 GtkTextIter start, end;
2626 if (_gtk_text_btree_get_selection_bounds (tree, &start, &end))
2627 redisplay_region (tree, &start, &end);
2629 /* Move insert AND selection_bound before we redisplay */
2630 real_set_mark (tree, tree->insert_mark,
2631 "insert", FALSE, iter, TRUE, FALSE);
2632 real_set_mark (tree, tree->selection_bound_mark,
2633 "selection_bound", FALSE, iter, TRUE, FALSE);
2637 _gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2642 g_return_if_fail (tree != NULL);
2643 g_return_if_fail (name != NULL);
2645 mark = g_hash_table_lookup (tree->mark_table,
2648 _gtk_text_btree_remove_mark (tree, mark);
2652 _gtk_text_btree_remove_mark (GtkTextBTree *tree,
2655 GtkTextLineSegment *segment;
2657 g_return_if_fail (mark != NULL);
2658 g_return_if_fail (tree != NULL);
2660 segment = mark->segment;
2662 if (segment->body.mark.not_deleteable)
2664 g_warning ("Can't delete special mark `%s'", segment->body.mark.name);
2668 /* This calls cleanup_line and segments_changed */
2669 gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2671 if (segment->body.mark.name)
2672 g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2674 /* Remove the ref on the mark that belonged to the segment. */
2675 g_object_unref (G_OBJECT (mark));
2677 segment->body.mark.tree = NULL;
2678 segment->body.mark.line = NULL;
2682 _gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2683 GtkTextMark *segment)
2685 return segment == tree->insert_mark;
2689 _gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2690 GtkTextMark *segment)
2692 return segment == tree->selection_bound_mark;
2696 _gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2699 GtkTextLineSegment *seg;
2701 g_return_val_if_fail (tree != NULL, NULL);
2702 g_return_val_if_fail (name != NULL, NULL);
2704 seg = g_hash_table_lookup (tree->mark_table, name);
2706 return seg ? seg->body.mark.obj : NULL;
2710 gtk_text_mark_set_visible (GtkTextMark *mark,
2713 GtkTextLineSegment *seg;
2715 g_return_if_fail (mark != NULL);
2717 seg = mark->segment;
2719 if (seg->body.mark.visible == setting)
2723 seg->body.mark.visible = setting;
2725 redisplay_mark (seg);
2730 _gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
2733 GtkTextBTreeNode *node;
2734 GtkTextTagInfo *info;
2736 g_return_val_if_fail (tree != NULL, NULL);
2740 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2745 if (info->tag_root == NULL)
2748 node = info->tag_root;
2750 /* We know the tag root has instances of the given
2753 continue_outer_loop:
2754 g_assert (node != NULL);
2755 while (node->level > 0)
2757 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2758 node = node->children.node;
2759 while (node != NULL)
2761 if (gtk_text_btree_node_has_tag (node, tag))
2762 goto continue_outer_loop;
2766 g_assert (node != NULL);
2769 g_assert (node != NULL); /* The tag summaries said some node had
2772 g_assert (node->level == 0);
2774 return node->children.line;
2778 /* Looking for any tag at all (tag == NULL).
2779 Unfortunately this can't be done in a simple and efficient way
2780 right now; so I'm just going to return the
2781 first line in the btree. FIXME */
2782 return _gtk_text_btree_get_line (tree, 0, NULL);
2787 _gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
2790 GtkTextBTreeNode *node;
2791 GtkTextBTreeNode *last_node;
2793 GtkTextTagInfo *info;
2795 g_return_val_if_fail (tree != NULL, NULL);
2799 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2801 if (info->tag_root == NULL)
2804 node = info->tag_root;
2805 /* We know the tag root has instances of the given
2808 while (node->level > 0)
2810 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2812 node = node->children.node;
2813 while (node != NULL)
2815 if (gtk_text_btree_node_has_tag (node, tag))
2823 g_assert (node != NULL); /* The tag summaries said some node had
2826 g_assert (node->level == 0);
2828 /* Find the last line in this node */
2829 line = node->children.line;
2830 while (line->next != NULL)
2837 /* This search can't be done efficiently at the moment,
2838 at least not without complexity.
2839 So, we just return the last line.
2841 return _gtk_text_btree_get_line (tree, -1, NULL);
2851 _gtk_text_line_get_number (GtkTextLine *line)
2854 GtkTextBTreeNode *node, *parent, *node2;
2858 * First count how many lines precede this one in its level-0
2862 node = line->parent;
2864 for (line2 = node->children.line; line2 != line;
2865 line2 = line2->next)
2869 g_error ("gtk_text_btree_line_number couldn't find line");
2875 * Now work up through the levels of the tree one at a time,
2876 * counting how many lines are in GtkTextBTreeNodes preceding the current
2880 for (parent = node->parent ; parent != NULL;
2881 node = parent, parent = parent->parent)
2883 for (node2 = parent->children.node; node2 != node;
2884 node2 = node2->next)
2888 g_error ("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
2890 index += node2->num_lines;
2896 static GtkTextLineSegment*
2897 find_toggle_segment_before_char (GtkTextLine *line,
2901 GtkTextLineSegment *seg;
2902 GtkTextLineSegment *toggle_seg;
2907 seg = line->segments;
2908 while ( (index + seg->char_count) <= char_in_line )
2910 if (((seg->type == >k_text_toggle_on_type)
2911 || (seg->type == >k_text_toggle_off_type))
2912 && (seg->body.toggle.info->tag == tag))
2915 index += seg->char_count;
2922 static GtkTextLineSegment*
2923 find_toggle_segment_before_byte (GtkTextLine *line,
2927 GtkTextLineSegment *seg;
2928 GtkTextLineSegment *toggle_seg;
2933 seg = line->segments;
2934 while ( (index + seg->byte_count) <= byte_in_line )
2936 if (((seg->type == >k_text_toggle_on_type)
2937 || (seg->type == >k_text_toggle_off_type))
2938 && (seg->body.toggle.info->tag == tag))
2941 index += seg->byte_count;
2949 find_toggle_outside_current_line (GtkTextLine *line,
2953 GtkTextBTreeNode *node;
2954 GtkTextLine *sibling_line;
2955 GtkTextLineSegment *seg;
2956 GtkTextLineSegment *toggle_seg;
2958 GtkTextTagInfo *info = NULL;
2961 * No toggle in this line. Look for toggles for the tag in lines
2962 * that are predecessors of line but under the same
2963 * level-0 GtkTextBTreeNode.
2966 sibling_line = line->parent->children.line;
2967 while (sibling_line != line)
2969 seg = sibling_line->segments;
2972 if (((seg->type == >k_text_toggle_on_type)
2973 || (seg->type == >k_text_toggle_off_type))
2974 && (seg->body.toggle.info->tag == tag))
2980 sibling_line = sibling_line->next;
2983 if (toggle_seg != NULL)
2984 return (toggle_seg->type == >k_text_toggle_on_type);
2987 * No toggle in this GtkTextBTreeNode. Scan upwards through the ancestors of
2988 * this GtkTextBTreeNode, counting the number of toggles of the given tag in
2989 * siblings that precede that GtkTextBTreeNode.
2992 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2998 node = line->parent;
2999 while (node->parent != NULL)
3001 GtkTextBTreeNode *sibling_node;
3003 sibling_node = node->parent->children.node;
3004 while (sibling_node != node)
3008 summary = sibling_node->summary;
3009 while (summary != NULL)
3011 if (summary->info == info)
3012 toggles += summary->toggle_count;
3014 summary = summary->next;
3017 sibling_node = sibling_node->next;
3020 if (node == info->tag_root)
3023 node = node->parent;
3027 * An odd number of toggles means that the tag is present at the
3031 return (toggles & 1) != 0;
3034 /* FIXME this function is far too slow, for no good reason. */
3036 _gtk_text_line_char_has_tag (GtkTextLine *line,
3041 GtkTextLineSegment *toggle_seg;
3043 g_return_val_if_fail (line != NULL, FALSE);
3046 * Check for toggles for the tag in the line but before
3047 * the char. If there is one, its type indicates whether or
3048 * not the character is tagged.
3051 toggle_seg = find_toggle_segment_before_char (line, char_in_line, tag);
3053 if (toggle_seg != NULL)
3054 return (toggle_seg->type == >k_text_toggle_on_type);
3056 return find_toggle_outside_current_line (line, tree, tag);
3060 _gtk_text_line_byte_has_tag (GtkTextLine *line,
3065 GtkTextLineSegment *toggle_seg;
3067 g_return_val_if_fail (line != NULL, FALSE);
3070 * Check for toggles for the tag in the line but before
3071 * the char. If there is one, its type indicates whether or
3072 * not the character is tagged.
3075 toggle_seg = find_toggle_segment_before_byte (line, byte_in_line, tag);
3077 if (toggle_seg != NULL)
3078 return (toggle_seg->type == >k_text_toggle_on_type);
3080 return find_toggle_outside_current_line (line, tree, tag);
3084 _gtk_text_line_is_last (GtkTextLine *line,
3087 return line == get_last_line (tree);
3091 _gtk_text_line_next (GtkTextLine *line)
3093 GtkTextBTreeNode *node;
3095 if (line->next != NULL)
3100 * This was the last line associated with the particular parent
3101 * GtkTextBTreeNode. Search up the tree for the next GtkTextBTreeNode,
3102 * then search down from that GtkTextBTreeNode to find the first
3106 node = line->parent;
3107 while (node != NULL && node->next == NULL)
3108 node = node->parent;
3114 while (node->level > 0)
3116 node = node->children.node;
3119 g_assert (node->children.line != line);
3121 return node->children.line;
3126 _gtk_text_line_previous (GtkTextLine *line)
3128 GtkTextBTreeNode *node;
3129 GtkTextBTreeNode *node2;
3133 * Find the line under this GtkTextBTreeNode just before the starting line.
3135 prev = line->parent->children.line; /* First line at leaf */
3136 while (prev != line)
3138 if (prev->next == line)
3144 g_error ("gtk_text_btree_previous_line ran out of lines");
3148 * This was the first line associated with the particular parent
3149 * GtkTextBTreeNode. Search up the tree for the previous GtkTextBTreeNode,
3150 * then search down from that GtkTextBTreeNode to find its last line.
3152 for (node = line->parent; ; node = node->parent)
3154 if (node == NULL || node->parent == NULL)
3156 else if (node != node->parent->children.node)
3160 for (node2 = node->parent->children.node; ;
3161 node2 = node2->children.node)
3163 while (node2->next != node)
3164 node2 = node2->next;
3166 if (node2->level == 0)
3172 for (prev = node2->children.line ; ; prev = prev->next)
3174 if (prev->next == NULL)
3178 g_assert_not_reached ();
3183 _gtk_text_line_add_data (GtkTextLine *line,
3184 GtkTextLineData *data)
3186 g_return_if_fail (line != NULL);
3187 g_return_if_fail (data != NULL);
3188 g_return_if_fail (data->view_id != NULL);
3192 data->next = line->views;
3202 _gtk_text_line_remove_data (GtkTextLine *line,
3205 GtkTextLineData *prev;
3206 GtkTextLineData *iter;
3208 g_return_val_if_fail (line != NULL, NULL);
3209 g_return_val_if_fail (view_id != NULL, NULL);
3213 while (iter != NULL)
3215 if (iter->view_id == view_id)
3224 prev->next = iter->next;
3226 line->views = iter->next;
3235 _gtk_text_line_get_data (GtkTextLine *line,
3238 GtkTextLineData *iter;
3240 g_return_val_if_fail (line != NULL, NULL);
3241 g_return_val_if_fail (view_id != NULL, NULL);
3244 while (iter != NULL)
3246 if (iter->view_id == view_id)
3255 _gtk_text_line_invalidate_wrap (GtkTextLine *line,
3256 GtkTextLineData *ld)
3258 /* For now this is totally unoptimized. FIXME?
3260 We could probably optimize the case where the width removed
3261 is less than the max width for the parent node,
3262 and the case where the height is unchanged when we re-wrap.
3265 g_return_if_fail (ld != NULL);
3268 gtk_text_btree_node_invalidate_upward (line->parent, ld->view_id);
3272 _gtk_text_line_char_count (GtkTextLine *line)
3274 GtkTextLineSegment *seg;
3278 seg = line->segments;
3281 size += seg->char_count;
3288 _gtk_text_line_byte_count (GtkTextLine *line)
3290 GtkTextLineSegment *seg;
3294 seg = line->segments;
3297 size += seg->byte_count;
3305 _gtk_text_line_char_index (GtkTextLine *target_line)
3307 GSList *node_stack = NULL;
3308 GtkTextBTreeNode *iter;
3312 /* Push all our parent nodes onto a stack */
3313 iter = target_line->parent;
3315 g_assert (iter != NULL);
3317 while (iter != NULL)
3319 node_stack = g_slist_prepend (node_stack, iter);
3321 iter = iter->parent;
3324 /* Check that we have the root node on top of the stack. */
3325 g_assert (node_stack != NULL &&
3326 node_stack->data != NULL &&
3327 ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3329 /* Add up chars in all nodes before the nodes in our stack.
3333 iter = node_stack->data;
3334 while (iter != NULL)
3336 GtkTextBTreeNode *child_iter;
3337 GtkTextBTreeNode *next_node;
3339 next_node = node_stack->next ?
3340 node_stack->next->data : NULL;
3341 node_stack = g_slist_remove (node_stack, node_stack->data);
3343 if (iter->level == 0)
3345 /* stack should be empty when we're on the last node */
3346 g_assert (node_stack == NULL);
3347 break; /* Our children are now lines */
3350 g_assert (next_node != NULL);
3351 g_assert (iter != NULL);
3352 g_assert (next_node->parent == iter);
3354 /* Add up chars before us in the tree */
3355 child_iter = iter->children.node;
3356 while (child_iter != next_node)
3358 g_assert (child_iter != NULL);
3360 num_chars += child_iter->num_chars;
3362 child_iter = child_iter->next;
3368 g_assert (iter != NULL);
3369 g_assert (iter == target_line->parent);
3371 /* Since we don't store char counts in lines, only in segments, we
3372 have to iterate over the lines adding up segment char counts
3373 until we find our line. */
3374 line = iter->children.line;
3375 while (line != target_line)
3377 g_assert (line != NULL);
3379 num_chars += _gtk_text_line_char_count (line);
3384 g_assert (line == target_line);
3390 _gtk_text_line_byte_to_segment (GtkTextLine *line,
3394 GtkTextLineSegment *seg;
3397 g_return_val_if_fail (line != NULL, NULL);
3399 offset = byte_offset;
3400 seg = line->segments;
3402 while (offset >= seg->byte_count)
3404 g_assert (seg != NULL); /* means an invalid byte index */
3405 offset -= seg->byte_count;
3410 *seg_offset = offset;
3416 _gtk_text_line_char_to_segment (GtkTextLine *line,
3420 GtkTextLineSegment *seg;
3423 g_return_val_if_fail (line != NULL, NULL);
3425 offset = char_offset;
3426 seg = line->segments;
3428 while (offset >= seg->char_count)
3430 g_assert (seg != NULL); /* means an invalid char index */
3431 offset -= seg->char_count;
3436 *seg_offset = offset;
3442 _gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3446 GtkTextLineSegment *seg;
3449 g_return_val_if_fail (line != NULL, NULL);
3451 offset = byte_offset;
3452 seg = line->segments;
3454 while (offset > 0 && offset >= seg->byte_count)
3456 g_assert (seg != NULL); /* means an invalid byte index */
3457 offset -= seg->byte_count;
3462 *seg_offset = offset;
3468 _gtk_text_line_char_to_any_segment (GtkTextLine *line,
3472 GtkTextLineSegment *seg;
3475 g_return_val_if_fail (line != NULL, NULL);
3477 offset = char_offset;
3478 seg = line->segments;
3480 while (offset > 0 && offset >= seg->char_count)
3482 g_assert (seg != NULL); /* means an invalid byte index */
3483 offset -= seg->char_count;
3488 *seg_offset = offset;
3494 _gtk_text_line_byte_to_char (GtkTextLine *line,
3498 GtkTextLineSegment *seg;
3500 g_return_val_if_fail (line != NULL, 0);
3501 g_return_val_if_fail (byte_offset >= 0, 0);
3504 seg = line->segments;
3505 while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3506 the next segment) */
3508 g_assert (seg != NULL); /* our byte_index was bogus if this happens */
3510 byte_offset -= seg->byte_count;
3511 char_offset += seg->char_count;
3516 g_assert (seg != NULL);
3518 /* Now byte_offset is the offset into the current segment,
3519 and char_offset is the start of the current segment.
3520 Optimize the case where no chars use > 1 byte */
3521 if (seg->byte_count == seg->char_count)
3522 return char_offset + byte_offset;
3525 if (seg->type == >k_text_char_type)
3526 return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3529 g_assert (seg->char_count == 1);
3530 g_assert (byte_offset == 0);
3538 _gtk_text_line_char_to_byte (GtkTextLine *line,
3541 g_warning ("FIXME not implemented");
3546 /* FIXME sync with char_locate (or figure out a clean
3547 way to merge the two functions) */
3549 _gtk_text_line_byte_locate (GtkTextLine *line,
3551 GtkTextLineSegment **segment,
3552 GtkTextLineSegment **any_segment,
3553 gint *seg_byte_offset,
3554 gint *line_byte_offset)
3556 GtkTextLineSegment *seg;
3557 GtkTextLineSegment *after_prev_indexable;
3558 GtkTextLineSegment *after_last_indexable;
3559 GtkTextLineSegment *last_indexable;
3563 g_return_if_fail (line != NULL);
3565 if (byte_offset < 0)
3567 /* -1 means end of line; we here assume no line is
3568 longer than 1 bazillion bytes, of course we assumed
3569 that anyway since we'd wrap around... */
3571 byte_offset = G_MAXINT;
3575 *any_segment = NULL;
3578 offset = byte_offset;
3580 last_indexable = NULL;
3581 after_last_indexable = line->segments;
3582 after_prev_indexable = line->segments;
3583 seg = line->segments;
3585 /* The loop ends when we're inside a segment;
3586 last_indexable refers to the last segment
3587 we passed entirely. */
3588 while (seg && offset >= seg->byte_count)
3590 if (seg->char_count > 0)
3592 offset -= seg->byte_count;
3593 bytes_in_line += seg->byte_count;
3594 last_indexable = seg;
3595 after_prev_indexable = after_last_indexable;
3596 after_last_indexable = last_indexable->next;
3604 /* We went off the end of the line */
3605 *segment = last_indexable;
3606 *any_segment = after_prev_indexable;
3607 /* subtracting 1 is OK, we know it's a newline at the end. */
3608 offset = (*segment)->byte_count - 1;
3609 bytes_in_line -= (*segment)->byte_count;
3614 if (after_last_indexable != NULL)
3615 *any_segment = after_last_indexable;
3617 *any_segment = *segment;
3620 /* Override any_segment if we're in the middle of a segment. */
3622 *any_segment = *segment;
3624 *seg_byte_offset = offset;
3626 g_assert (*segment != NULL);
3627 g_assert (*any_segment != NULL);
3628 g_assert (*seg_byte_offset < (*segment)->byte_count);
3630 *line_byte_offset = bytes_in_line + *seg_byte_offset;
3633 /* FIXME sync with byte_locate (or figure out a clean
3634 way to merge the two functions) */
3636 _gtk_text_line_char_locate (GtkTextLine *line,
3638 GtkTextLineSegment **segment,
3639 GtkTextLineSegment **any_segment,
3640 gint *seg_char_offset,
3641 gint *line_char_offset)
3643 GtkTextLineSegment *seg;
3644 GtkTextLineSegment *after_prev_indexable;
3645 GtkTextLineSegment *after_last_indexable;
3646 GtkTextLineSegment *last_indexable;
3650 g_return_if_fail (line != NULL);
3652 if (char_offset < 0)
3654 /* -1 means end of line; we here assume no line is
3655 longer than 1 bazillion chars, of course we assumed
3656 that anyway since we'd wrap around... */
3658 char_offset = G_MAXINT;
3662 *any_segment = NULL;
3665 offset = char_offset;
3667 last_indexable = NULL;
3668 after_last_indexable = line->segments;
3669 after_prev_indexable = line->segments;
3670 seg = line->segments;
3672 /* The loop ends when we're inside a segment;
3673 last_indexable refers to the last segment
3674 we passed entirely. */
3675 while (seg && offset >= seg->char_count)
3677 if (seg->char_count > 0)
3679 offset -= seg->char_count;
3680 chars_in_line += seg->char_count;
3681 last_indexable = seg;
3682 after_prev_indexable = after_last_indexable;
3683 after_last_indexable = last_indexable->next;
3691 /* We went off the end of the line */
3692 *segment = last_indexable;
3693 *any_segment = after_prev_indexable;
3694 /* subtracting 1 is OK, we know it's a newline at the end. */
3695 offset = (*segment)->char_count - 1;
3696 chars_in_line -= (*segment)->char_count;
3701 if (after_last_indexable != NULL)
3702 *any_segment = after_last_indexable;
3704 *any_segment = *segment;
3707 /* Override any_segment if we're in the middle of a segment. */
3709 *any_segment = *segment;
3711 *seg_char_offset = offset;
3713 g_assert (*segment != NULL);
3714 g_assert (*any_segment != NULL);
3715 g_assert (*seg_char_offset < (*segment)->char_count);
3717 *line_char_offset = chars_in_line + *seg_char_offset;
3721 _gtk_text_line_byte_to_char_offsets (GtkTextLine *line,
3723 gint *line_char_offset,
3724 gint *seg_char_offset)
3726 GtkTextLineSegment *seg;
3729 g_return_if_fail (line != NULL);
3730 g_return_if_fail (byte_offset >= 0);
3732 *line_char_offset = 0;
3734 offset = byte_offset;
3735 seg = line->segments;
3737 while (offset >= seg->byte_count)
3739 offset -= seg->byte_count;
3740 *line_char_offset += seg->char_count;
3742 g_assert (seg != NULL); /* means an invalid char offset */
3745 g_assert (seg->char_count > 0); /* indexable. */
3747 /* offset is now the number of bytes into the current segment we
3748 * want to go. Count chars into the current segment.
3751 if (seg->type == >k_text_char_type)
3753 *seg_char_offset = g_utf8_strlen (seg->body.chars, offset);
3755 g_assert (*seg_char_offset < seg->char_count);
3757 *line_char_offset += *seg_char_offset;
3761 g_assert (offset == 0);
3762 *seg_char_offset = 0;
3767 _gtk_text_line_char_to_byte_offsets (GtkTextLine *line,
3769 gint *line_byte_offset,
3770 gint *seg_byte_offset)
3772 GtkTextLineSegment *seg;
3775 g_return_if_fail (line != NULL);
3776 g_return_if_fail (char_offset >= 0);
3778 *line_byte_offset = 0;
3780 offset = char_offset;
3781 seg = line->segments;
3783 while (offset >= seg->char_count)
3785 offset -= seg->char_count;
3786 *line_byte_offset += seg->byte_count;
3788 g_assert (seg != NULL); /* means an invalid char offset */
3791 g_assert (seg->char_count > 0); /* indexable. */
3793 /* offset is now the number of chars into the current segment we
3794 want to go. Count bytes into the current segment. */
3796 if (seg->type == >k_text_char_type)
3798 *seg_byte_offset = 0;
3802 const char * start = seg->body.chars + *seg_byte_offset;
3804 bytes = g_utf8_next_char (start) - start;
3805 *seg_byte_offset += bytes;
3809 g_assert (*seg_byte_offset < seg->byte_count);
3811 *line_byte_offset += *seg_byte_offset;
3815 g_assert (offset == 0);
3816 *seg_byte_offset = 0;
3821 node_compare (GtkTextBTreeNode *lhs,
3822 GtkTextBTreeNode *rhs)
3824 GtkTextBTreeNode *iter;
3825 GtkTextBTreeNode *node;
3826 GtkTextBTreeNode *common_parent;
3827 GtkTextBTreeNode *parent_of_lower;
3828 GtkTextBTreeNode *parent_of_higher;
3829 gboolean lhs_is_lower;
3830 GtkTextBTreeNode *lower;
3831 GtkTextBTreeNode *higher;
3833 /* This function assumes that lhs and rhs are not underneath each
3840 if (lhs->level < rhs->level)
3842 lhs_is_lower = TRUE;
3848 lhs_is_lower = FALSE;
3853 /* Algorithm: find common parent of lhs/rhs. Save the child nodes
3854 * of the common parent we used to reach the common parent; the
3855 * ordering of these child nodes in the child list is the ordering
3859 /* Get on the same level (may be on same level already) */
3861 while (node->level < higher->level)
3862 node = node->parent;
3864 g_assert (node->level == higher->level);
3866 g_assert (node != higher); /* Happens if lower is underneath higher */
3868 /* Go up until we have two children with a common parent.
3870 parent_of_lower = node;
3871 parent_of_higher = higher;
3873 while (parent_of_lower->parent != parent_of_higher->parent)
3875 parent_of_lower = parent_of_lower->parent;
3876 parent_of_higher = parent_of_higher->parent;
3879 g_assert (parent_of_lower->parent == parent_of_higher->parent);
3881 common_parent = parent_of_lower->parent;
3883 g_assert (common_parent != NULL);
3885 /* See which is first in the list of common_parent's children */
3886 iter = common_parent->children.node;
3887 while (iter != NULL)
3889 if (iter == parent_of_higher)
3891 /* higher is less than lower */
3894 return 1; /* lhs > rhs */
3898 else if (iter == parent_of_lower)
3900 /* lower is less than higher */
3903 return -1; /* lhs < rhs */
3911 g_assert_not_reached ();
3915 /* remember that tag == NULL means "any tag" */
3917 _gtk_text_line_next_could_contain_tag (GtkTextLine *line,
3921 GtkTextBTreeNode *node;
3922 GtkTextTagInfo *info;
3923 gboolean below_tag_root;
3925 g_return_val_if_fail (line != NULL, NULL);
3927 if (gtk_debug_flags & GTK_DEBUG_TEXT)
3928 _gtk_text_btree_check (tree);
3932 /* Right now we can only offer linear-search if the user wants
3933 * to know about any tag toggle at all.
3935 return _gtk_text_line_next (line);
3938 /* Our tag summaries only have node precision, not line
3939 precision. This means that if any line under a node could contain a
3940 tag, then any of the others could also contain a tag.
3942 In the future we could have some mechanism to keep track of how
3943 many toggles we've found under a node so far, since we have a
3944 count of toggles under the node. But for now I'm going with KISS.
3947 /* return same-node line, if any. */
3951 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3955 if (info->tag_root == NULL)
3958 if (info->tag_root == line->parent)
3959 return NULL; /* we were at the last line under the tag root */
3961 /* We need to go up out of this node, and on to the next one with
3962 toggles for the target tag. If we're below the tag root, we need to
3963 find the next node below the tag root that has tag summaries. If
3964 we're not below the tag root, we need to see if the tag root is
3965 after us in the tree, and if so, return the first line underneath
3968 node = line->parent;
3969 below_tag_root = FALSE;
3970 while (node != NULL)
3972 if (node == info->tag_root)
3974 below_tag_root = TRUE;
3978 node = node->parent;
3983 node = line->parent;
3984 while (node != info->tag_root)
3986 if (node->next == NULL)
3987 node = node->parent;
3992 if (gtk_text_btree_node_has_tag (node, tag))
4002 ordering = node_compare (line->parent, info->tag_root);
4006 /* Tag root is ahead of us, so search there. */
4007 node = info->tag_root;
4012 /* Tag root is after us, so no more lines that
4013 * could contain the tag.
4018 g_assert_not_reached ();
4023 g_assert (node != NULL);
4025 /* We have to find the first sub-node of this node that contains
4029 while (node->level > 0)
4031 g_assert (node != NULL); /* If this fails, it likely means an
4032 incorrect tag summary led us on a
4033 wild goose chase down this branch of
4035 node = node->children.node;
4036 while (node != NULL)
4038 if (gtk_text_btree_node_has_tag (node, tag))
4044 g_assert (node != NULL);
4045 g_assert (node->level == 0);
4047 return node->children.line;
4051 prev_line_under_node (GtkTextBTreeNode *node,
4056 prev = node->children.line;
4062 while (prev->next != line)
4072 _gtk_text_line_previous_could_contain_tag (GtkTextLine *line,
4076 GtkTextBTreeNode *node;
4077 GtkTextBTreeNode *found_node = NULL;
4078 GtkTextTagInfo *info;
4079 gboolean below_tag_root;
4081 GtkTextBTreeNode *line_ancestor;
4082 GtkTextBTreeNode *line_ancestor_parent;
4084 /* See next_could_contain_tag () for more extensive comments
4085 * on what's going on here.
4088 g_return_val_if_fail (line != NULL, NULL);
4090 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4091 _gtk_text_btree_check (tree);
4095 /* Right now we can only offer linear-search if the user wants
4096 * to know about any tag toggle at all.
4098 return _gtk_text_line_previous (line);
4101 /* Return same-node line, if any. */
4102 prev = prev_line_under_node (line->parent, line);
4106 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4110 if (info->tag_root == NULL)
4113 if (info->tag_root == line->parent)
4114 return NULL; /* we were at the first line under the tag root */
4116 /* Are we below the tag root */
4117 node = line->parent;
4118 below_tag_root = FALSE;
4119 while (node != NULL)
4121 if (node == info->tag_root)
4123 below_tag_root = TRUE;
4127 node = node->parent;
4132 /* Look for a previous node under this tag root that has our
4136 /* this assertion holds because line->parent is not the
4137 * tag root, we are below the tag root, and the tag
4140 g_assert (line->parent->parent != NULL);
4142 line_ancestor = line->parent;
4143 line_ancestor_parent = line->parent->parent;
4145 node = line_ancestor_parent->children.node;
4146 while (node != line_ancestor &&
4147 line_ancestor != info->tag_root)
4149 GSList *child_nodes = NULL;
4152 /* Create reverse-order list of nodes before
4155 while (node != line_ancestor
4158 child_nodes = g_slist_prepend (child_nodes, node);
4163 /* Try to find a node with our tag on it in the list */
4167 GtkTextBTreeNode *this_node = tmp->data;
4169 g_assert (this_node != line_ancestor);
4171 if (gtk_text_btree_node_has_tag (this_node, tag))
4173 found_node = this_node;
4174 g_slist_free (child_nodes);
4178 tmp = g_slist_next (tmp);
4181 g_slist_free (child_nodes);
4183 /* Didn't find anything on this level; go up one level. */
4184 line_ancestor = line_ancestor_parent;
4185 line_ancestor_parent = line_ancestor->parent;
4187 node = line_ancestor_parent->children.node;
4197 ordering = node_compare (line->parent, info->tag_root);
4201 /* Tag root is ahead of us, so no more lines
4208 /* Tag root is after us, so grab last tagged
4209 * line underneath the tag root.
4211 found_node = info->tag_root;
4215 g_assert_not_reached ();
4220 g_assert (found_node != NULL);
4222 /* We have to find the last sub-node of this node that contains
4227 while (node->level > 0)
4229 GSList *child_nodes = NULL;
4231 g_assert (node != NULL); /* If this fails, it likely means an
4232 incorrect tag summary led us on a
4233 wild goose chase down this branch of
4236 node = node->children.node;
4237 while (node != NULL)
4239 child_nodes = g_slist_prepend (child_nodes, node);
4243 node = NULL; /* detect failure to find a child node. */
4246 while (iter != NULL)
4248 if (gtk_text_btree_node_has_tag (iter->data, tag))
4250 /* recurse into this node. */
4255 iter = g_slist_next (iter);
4258 g_slist_free (child_nodes);
4260 g_assert (node != NULL);
4263 g_assert (node != NULL);
4264 g_assert (node->level == 0);
4266 /* this assertion is correct, but slow. */
4267 /* g_assert (node_compare (node, line->parent) < 0); */
4269 /* Return last line in this node. */
4271 prev = node->children.line;
4279 * Non-public function implementations
4283 summary_list_destroy (Summary *summary)
4286 while (summary != NULL)
4288 next = summary->next;
4289 summary_destroy (summary);
4295 get_last_line (GtkTextBTree *tree)
4297 if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
4303 n_lines = _gtk_text_btree_line_count (tree);
4305 g_assert (n_lines >= 1); /* num_lines doesn't return bogus last line. */
4307 line = _gtk_text_btree_get_line (tree, n_lines, &real_line);
4309 tree->end_iter_line_stamp = tree->chars_changed_stamp;
4310 tree->end_iter_line = line;
4313 return tree->end_iter_line;
4321 gtk_text_line_new (void)
4325 line = g_new0(GtkTextLine, 1);
4331 gtk_text_line_destroy (GtkTextBTree *tree, GtkTextLine *line)
4333 GtkTextLineData *ld;
4334 GtkTextLineData *next;
4336 g_return_if_fail (line != NULL);
4343 view = gtk_text_btree_get_view (tree, ld->view_id);
4345 g_assert (view != NULL);
4348 gtk_text_layout_free_line_data (view->layout, line, ld);
4357 gtk_text_line_set_parent (GtkTextLine *line,
4358 GtkTextBTreeNode *node)
4360 if (line->parent == node)
4362 line->parent = node;
4363 gtk_text_btree_node_invalidate_upward (node, NULL);
4367 cleanup_line (GtkTextLine *line)
4369 GtkTextLineSegment *seg, **prev_p;
4373 * Make a pass over all of the segments in the line, giving each
4374 * a chance to clean itself up. This could potentially change
4375 * the structure of the line, e.g. by merging two segments
4376 * together or having two segments cancel themselves; if so,
4377 * then repeat the whole process again, since the first structure
4378 * change might make other structure changes possible. Repeat
4379 * until eventually there are no changes.
4386 for (prev_p = &line->segments, seg = *prev_p;
4388 prev_p = &(*prev_p)->next, seg = *prev_p)
4390 if (seg->type->cleanupFunc != NULL)
4392 *prev_p = (*seg->type->cleanupFunc)(seg, line);
4405 node_data_new (gpointer view_id)
4409 nd = g_new (NodeData, 1);
4411 nd->view_id = view_id;
4421 node_data_destroy (NodeData *nd)
4428 node_data_list_destroy (NodeData *nd)
4434 while (iter != NULL)
4437 node_data_destroy (iter);
4443 node_data_find (NodeData *nd, gpointer view_id)
4447 if (nd->view_id == view_id)
4455 summary_destroy (Summary *summary)
4457 /* Fill with error-triggering garbage */
4458 summary->info = (void*)0x1;
4459 summary->toggle_count = 567;
4460 summary->next = (void*)0x1;
4464 static GtkTextBTreeNode*
4465 gtk_text_btree_node_new (void)
4467 GtkTextBTreeNode *node;
4469 node = g_new (GtkTextBTreeNode, 1);
4471 node->node_data = NULL;
4477 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
4478 GtkTextTagInfo *info,
4483 summary = node->summary;
4484 while (summary != NULL)
4486 if (summary->info == info)
4488 summary->toggle_count += adjust;
4492 summary = summary->next;
4495 if (summary == NULL)
4497 /* didn't find a summary for our tag. */
4498 g_return_if_fail (adjust > 0);
4499 summary = g_new (Summary, 1);
4500 summary->info = info;
4501 summary->toggle_count = adjust;
4502 summary->next = node->summary;
4503 node->summary = summary;
4507 /* Note that the tag root and above do not have summaries
4508 for the tag; only nodes below the tag root have
4511 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4515 summary = node->summary;
4516 while (summary != NULL)
4519 summary->info->tag == tag)
4522 summary = summary->next;
4528 /* Add node and all children to the damage region. */
4530 gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node)
4534 nd = node->node_data;
4541 if (node->level == 0)
4545 line = node->children.line;
4546 while (line != NULL)
4548 GtkTextLineData *ld;
4562 GtkTextBTreeNode *child;
4564 child = node->children.node;
4566 while (child != NULL)
4568 gtk_text_btree_node_invalidate_downward (child);
4570 child = child->next;
4576 gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node, gpointer view_id)
4578 GtkTextBTreeNode *iter;
4581 while (iter != NULL)
4587 nd = node_data_find (iter->node_data, view_id);
4589 if (nd == NULL || !nd->valid)
4590 break; /* Once a node is invalid, we know its parents are as well. */
4596 gboolean should_continue = FALSE;
4598 nd = iter->node_data;
4603 should_continue = TRUE;
4610 if (!should_continue)
4611 break; /* This node was totally invalidated, so are its
4615 iter = iter->parent;
4621 * _gtk_text_btree_is_valid:
4622 * @tree: a #GtkTextBTree
4623 * @view_id: ID for the view
4625 * Check to see if the entire #GtkTextBTree is valid or not for
4628 * Return value: %TRUE if the entire #GtkTextBTree is valid
4631 _gtk_text_btree_is_valid (GtkTextBTree *tree,
4635 g_return_val_if_fail (tree != NULL, FALSE);
4637 nd = node_data_find (tree->root_node->node_data, view_id);
4638 return (nd && nd->valid);
4641 typedef struct _ValidateState ValidateState;
4643 struct _ValidateState
4645 gint remaining_pixels;
4646 gboolean in_validation;
4653 gtk_text_btree_node_validate (BTreeView *view,
4654 GtkTextBTreeNode *node,
4656 ValidateState *state)
4658 gint node_valid = TRUE;
4659 gint node_width = 0;
4660 gint node_height = 0;
4662 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4663 g_return_if_fail (!nd->valid);
4665 if (node->level == 0)
4667 GtkTextLine *line = node->children.line;
4668 GtkTextLineData *ld;
4670 /* Iterate over leading valid lines */
4671 while (line != NULL)
4673 ld = _gtk_text_line_get_data (line, view_id);
4675 if (!ld || !ld->valid)
4677 else if (state->in_validation)
4679 state->in_validation = FALSE;
4684 state->y += ld->height;
4685 node_width = MAX (ld->width, node_width);
4686 node_height += ld->height;
4692 state->in_validation = TRUE;
4694 /* Iterate over invalid lines */
4695 while (line != NULL)
4697 ld = _gtk_text_line_get_data (line, view_id);
4699 if (ld && ld->valid)
4704 state->old_height += ld->height;
4705 ld = gtk_text_layout_wrap (view->layout, line, ld);
4706 state->new_height += ld->height;
4708 node_width = MAX (ld->width, node_width);
4709 node_height += ld->height;
4711 state->remaining_pixels -= ld->height;
4712 if (state->remaining_pixels <= 0)
4722 /* Iterate over the remaining lines */
4723 while (line != NULL)
4725 ld = _gtk_text_line_get_data (line, view_id);
4726 state->in_validation = FALSE;
4728 if (!ld || !ld->valid)
4733 node_width = MAX (ld->width, node_width);
4734 node_height += ld->height;
4742 GtkTextBTreeNode *child;
4745 child = node->children.node;
4747 /* Iterate over leading valid nodes */
4750 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4752 if (!child_nd->valid)
4754 else if (state->in_validation)
4756 state->in_validation = FALSE;
4761 state->y += child_nd->height;
4762 node_width = MAX (node_width, child_nd->width);
4763 node_height += child_nd->height;
4766 child = child->next;
4769 /* Iterate over invalid nodes */
4772 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4774 if (child_nd->valid)
4778 gtk_text_btree_node_validate (view, child, view_id, state);
4780 if (!child_nd->valid)
4782 node_width = MAX (node_width, child_nd->width);
4783 node_height += child_nd->height;
4785 if (!state->in_validation || state->remaining_pixels <= 0)
4787 child = child->next;
4792 child = child->next;
4795 /* Iterate over the remaining lines */
4798 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4799 state->in_validation = FALSE;
4801 if (!child_nd->valid)
4804 node_width = MAX (child_nd->width, node_width);
4805 node_height += child_nd->height;
4807 child = child->next;
4811 nd->width = node_width;
4812 nd->height = node_height;
4813 nd->valid = node_valid;
4817 * _gtk_text_btree_validate:
4818 * @tree: a #GtkTextBTree
4820 * @max_pixels: the maximum number of pixels to validate. (No more
4821 * than one paragraph beyond this limit will be validated)
4822 * @y: location to store starting y coordinate of validated region
4823 * @old_height: location to store old height of validated region
4824 * @new_height: location to store new height of validated region
4826 * Validate a single contiguous invalid region of a #GtkTextBTree for
4829 * Return value: %TRUE if a region has been validated, %FALSE if the
4830 * entire tree was already valid.
4833 _gtk_text_btree_validate (GtkTextBTree *tree,
4842 g_return_val_if_fail (tree != NULL, FALSE);
4844 view = gtk_text_btree_get_view (tree, view_id);
4845 g_return_val_if_fail (view != NULL, FALSE);
4847 if (!_gtk_text_btree_is_valid (tree, view_id))
4849 ValidateState state;
4851 state.remaining_pixels = max_pixels;
4852 state.in_validation = FALSE;
4854 state.old_height = 0;
4855 state.new_height = 0;
4857 gtk_text_btree_node_validate (view,
4864 *old_height = state.old_height;
4866 *new_height = state.new_height;
4868 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4869 _gtk_text_btree_check (tree);
4878 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
4882 gboolean *valid_out)
4886 gboolean valid = TRUE;
4888 if (node->level == 0)
4890 GtkTextLine *line = node->children.line;
4892 while (line != NULL)
4894 GtkTextLineData *ld = _gtk_text_line_get_data (line, view_id);
4896 if (!ld || !ld->valid)
4901 width = MAX (ld->width, width);
4902 height += ld->height;
4910 GtkTextBTreeNode *child = node->children.node;
4914 NodeData *child_nd = node_data_find (child->node_data, view_id);
4916 if (!child_nd || !child_nd->valid)
4921 width = MAX (child_nd->width, width);
4922 height += child_nd->height;
4925 child = child->next;
4930 *height_out = height;
4935 /* Recompute the validity and size of the view data for a given
4936 * view at this node from the immediate children of the node
4939 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
4942 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4947 gtk_text_btree_node_compute_view_aggregates (node, view_id,
4948 &width, &height, &valid);
4950 nd->height = height;
4957 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
4962 gtk_text_btree_node_check_valid (node, view_id);
4963 node = node->parent;
4968 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
4971 if (node->level == 0)
4973 return gtk_text_btree_node_check_valid (node, view_id);
4977 GtkTextBTreeNode *child = node->children.node;
4979 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4987 NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
4989 if (!child_nd->valid)
4991 nd->width = MAX (child_nd->width, nd->width);
4992 nd->height += child_nd->height;
4994 child = child->next;
5003 * _gtk_text_btree_validate_line:
5004 * @tree: a #GtkTextBTree
5005 * @line: line to validate
5006 * @view_id: view ID for the view to validate
5008 * Revalidate a single line of the btree for the given view, propagate
5009 * results up through the entire tree.
5012 _gtk_text_btree_validate_line (GtkTextBTree *tree,
5016 GtkTextLineData *ld;
5019 g_return_if_fail (tree != NULL);
5020 g_return_if_fail (line != NULL);
5022 view = gtk_text_btree_get_view (tree, view_id);
5023 g_return_if_fail (view != NULL);
5025 ld = _gtk_text_line_get_data (line, view_id);
5026 if (!ld || !ld->valid)
5028 ld = gtk_text_layout_wrap (view->layout, line, ld);
5030 gtk_text_btree_node_check_valid_upward (line->parent, view_id);
5035 gtk_text_btree_node_remove_view (BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
5037 if (node->level == 0)
5041 line = node->children.line;
5042 while (line != NULL)
5044 GtkTextLineData *ld;
5046 ld = _gtk_text_line_remove_data (line, view_id);
5049 gtk_text_layout_free_line_data (view->layout, line, ld);
5056 GtkTextBTreeNode *child;
5058 child = node->children.node;
5060 while (child != NULL)
5063 gtk_text_btree_node_remove_view (view, child, view_id);
5065 child = child->next;
5069 gtk_text_btree_node_remove_data (node, view_id);
5073 gtk_text_btree_node_destroy (GtkTextBTree *tree, GtkTextBTreeNode *node)
5075 if (node->level == 0)
5078 GtkTextLineSegment *seg;
5080 while (node->children.line != NULL)
5082 line = node->children.line;
5083 node->children.line = line->next;
5084 while (line->segments != NULL)
5086 seg = line->segments;
5087 line->segments = seg->next;
5089 if (GTK_IS_TEXT_MARK_SEGMENT (seg))
5091 /* Set the mark as deleted */
5092 seg->body.mark.tree = NULL;
5093 seg->body.mark.line = NULL;
5096 (*seg->type->deleteFunc) (seg, line, 1);
5098 gtk_text_line_destroy (tree, line);
5103 GtkTextBTreeNode *childPtr;
5105 while (node->children.node != NULL)
5107 childPtr = node->children.node;
5108 node->children.node = childPtr->next;
5109 gtk_text_btree_node_destroy (tree, childPtr);
5113 summary_list_destroy (node->summary);
5114 node_data_list_destroy (node->node_data);
5119 gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node, gpointer view_id)
5123 nd = node->node_data;
5126 if (nd->view_id == view_id)
5133 nd = node_data_new (view_id);
5135 if (node->node_data)
5136 nd->next = node->node_data;
5138 node->node_data = nd;
5145 gtk_text_btree_node_remove_data (GtkTextBTreeNode *node, gpointer view_id)
5151 nd = node->node_data;
5154 if (nd->view_id == view_id)
5165 prev->next = nd->next;
5167 if (node->node_data == nd)
5168 node->node_data = nd->next;
5172 node_data_destroy (nd);
5176 gtk_text_btree_node_get_size (GtkTextBTreeNode *node, gpointer view_id,
5177 gint *width, gint *height)
5181 g_return_if_fail (width != NULL);
5182 g_return_if_fail (height != NULL);
5184 nd = gtk_text_btree_node_ensure_data (node, view_id);
5189 *height = nd->height;
5192 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5193 * here isn't quite right, since for a lot of operations we want to
5194 * know which children of the common parent correspond to the two nodes
5195 * (e.g., when computing the order of two iters)
5197 static GtkTextBTreeNode *
5198 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5199 GtkTextBTreeNode *node2)
5201 while (node1->level < node2->level)
5202 node1 = node1->parent;
5203 while (node2->level < node1->level)
5204 node2 = node2->parent;
5205 while (node1 != node2)
5207 node1 = node1->parent;
5208 node2 = node2->parent;
5219 gtk_text_btree_get_view (GtkTextBTree *tree, gpointer view_id)
5224 while (view != NULL)
5226 if (view->view_id == view_id)
5235 get_tree_bounds (GtkTextBTree *tree,
5239 _gtk_text_btree_get_iter_at_line_char (tree, start, 0, 0);
5240 _gtk_text_btree_get_last_iter (tree, end);
5244 tag_changed_cb (GtkTextTagTable *table,
5246 gboolean size_changed,
5251 /* We need to queue a relayout on all regions that are tagged with
5258 if (_gtk_text_btree_get_iter_at_first_toggle (tree, &start, tag))
5260 /* Must be a last toggle if there was a first one. */
5261 _gtk_text_btree_get_iter_at_last_toggle (tree, &end, tag);
5262 _gtk_text_btree_invalidate_region (tree,
5269 /* We only need to queue a redraw, not a relayout */
5274 while (view != NULL)
5278 _gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5279 gtk_text_layout_changed (view->layout, 0, height, height);
5287 tag_removed_cb (GtkTextTagTable *table,
5291 /* Remove the tag from the tree */
5296 get_tree_bounds (tree, &start, &end);
5298 _gtk_text_btree_tag (&start, &end, tag, FALSE);
5299 gtk_text_btree_remove_tag_info (tree, tag);
5303 /* Rebalance the out-of-whack node "node" */
5305 gtk_text_btree_rebalance (GtkTextBTree *tree,
5306 GtkTextBTreeNode *node)
5309 * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5310 * up through the tree one GtkTextBTreeNode at a time until the root
5311 * GtkTextBTreeNode has been processed.
5314 while (node != NULL)
5316 GtkTextBTreeNode *new_node, *child;
5321 * Check to see if the GtkTextBTreeNode has too many children. If it does,
5322 * then split off all but the first MIN_CHILDREN into a separate
5323 * GtkTextBTreeNode following the original one. Then repeat until the
5324 * GtkTextBTreeNode has a decent size.
5327 if (node->num_children > MAX_CHILDREN)
5332 * If the GtkTextBTreeNode being split is the root
5333 * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5337 if (node->parent == NULL)
5339 new_node = gtk_text_btree_node_new ();
5340 new_node->parent = NULL;
5341 new_node->next = NULL;
5342 new_node->summary = NULL;
5343 new_node->level = node->level + 1;
5344 new_node->children.node = node;
5345 recompute_node_counts (tree, new_node);
5346 tree->root_node = new_node;
5348 new_node = gtk_text_btree_node_new ();
5349 new_node->parent = node->parent;
5350 new_node->next = node->next;
5351 node->next = new_node;
5352 new_node->summary = NULL;
5353 new_node->level = node->level;
5354 new_node->num_children = node->num_children - MIN_CHILDREN;
5355 if (node->level == 0)
5357 for (i = MIN_CHILDREN-1,
5358 line = node->children.line;
5359 i > 0; i--, line = line->next)
5361 /* Empty loop body. */
5363 new_node->children.line = line->next;
5368 for (i = MIN_CHILDREN-1,
5369 child = node->children.node;
5370 i > 0; i--, child = child->next)
5372 /* Empty loop body. */
5374 new_node->children.node = child->next;
5377 recompute_node_counts (tree, node);
5378 node->parent->num_children++;
5380 if (node->num_children <= MAX_CHILDREN)
5382 recompute_node_counts (tree, node);
5388 while (node->num_children < MIN_CHILDREN)
5390 GtkTextBTreeNode *other;
5391 GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5392 GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5393 int total_children, first_children, i;
5396 * Too few children for this GtkTextBTreeNode. If this is the root then,
5397 * it's OK for it to have less than MIN_CHILDREN children
5398 * as long as it's got at least two. If it has only one
5399 * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5400 * the tree and use its child as the new root.
5403 if (node->parent == NULL)
5405 if ((node->num_children == 1) && (node->level > 0))
5407 tree->root_node = node->children.node;
5408 tree->root_node->parent = NULL;
5409 summary_list_destroy (node->summary);
5416 * Not the root. Make sure that there are siblings to
5420 if (node->parent->num_children < 2)
5422 gtk_text_btree_rebalance (tree, node->parent);
5427 * Find a sibling neighbor to borrow from, and arrange for
5428 * node to be the earlier of the pair.
5431 if (node->next == NULL)
5433 for (other = node->parent->children.node;
5434 other->next != node;
5435 other = other->next)
5437 /* Empty loop body. */
5444 * We're going to either merge the two siblings together
5445 * into one GtkTextBTreeNode or redivide the children among them to
5446 * balance their loads. As preparation, join their two
5447 * child lists into a single list and remember the half-way
5448 * point in the list.
5451 total_children = node->num_children + other->num_children;
5452 first_children = total_children/2;
5453 if (node->children.node == NULL)
5455 node->children = other->children;
5456 other->children.node = NULL;
5457 other->children.line = NULL;
5459 if (node->level == 0)
5463 for (line = node->children.line, i = 1;
5465 line = line->next, i++)
5467 if (i == first_children)
5472 line->next = other->children.line;
5473 while (i <= first_children)
5482 GtkTextBTreeNode *child;
5484 for (child = node->children.node, i = 1;
5485 child->next != NULL;
5486 child = child->next, i++)
5488 if (i <= first_children)
5490 if (i == first_children)
5492 halfwaynode = child;
5496 child->next = other->children.node;
5497 while (i <= first_children)
5499 halfwaynode = child;
5500 child = child->next;
5506 * If the two siblings can simply be merged together, do it.
5509 if (total_children <= MAX_CHILDREN)
5511 recompute_node_counts (tree, node);
5512 node->next = other->next;
5513 node->parent->num_children--;
5514 summary_list_destroy (other->summary);
5520 * The siblings can't be merged, so just divide their
5521 * children evenly between them.
5524 if (node->level == 0)
5526 other->children.line = halfwayline->next;
5527 halfwayline->next = NULL;
5531 other->children.node = halfwaynode->next;
5532 halfwaynode->next = NULL;
5535 recompute_node_counts (tree, node);
5536 recompute_node_counts (tree, other);
5539 node = node->parent;
5544 post_insert_fixup (GtkTextBTree *tree,
5546 gint line_count_delta,
5547 gint char_count_delta)
5550 GtkTextBTreeNode *node;
5553 * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5554 * point, then rebalance the tree if necessary.
5557 for (node = line->parent ; node != NULL;
5558 node = node->parent)
5560 node->num_lines += line_count_delta;
5561 node->num_chars += char_count_delta;
5563 node = line->parent;
5564 node->num_children += line_count_delta;
5566 if (node->num_children > MAX_CHILDREN)
5568 gtk_text_btree_rebalance (tree, node);
5571 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5572 _gtk_text_btree_check (tree);
5575 static GtkTextTagInfo*
5576 gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
5579 GtkTextTagInfo *info;
5583 list = tree->tag_infos;
5584 while (list != NULL)
5587 if (info->tag == tag)
5590 list = g_slist_next (list);
5596 static GtkTextTagInfo*
5597 gtk_text_btree_get_tag_info (GtkTextBTree *tree,
5600 GtkTextTagInfo *info;
5602 info = gtk_text_btree_get_existing_tag_info (tree, tag);
5606 /* didn't find it, create. */
5608 info = g_new (GtkTextTagInfo, 1);
5611 g_object_ref (G_OBJECT (tag));
5612 info->tag_root = NULL;
5613 info->toggle_count = 0;
5615 tree->tag_infos = g_slist_prepend (tree->tag_infos, info);
5622 gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
5625 GtkTextTagInfo *info;
5630 list = tree->tag_infos;
5631 while (list != NULL)
5634 if (info->tag == tag)
5638 prev->next = list->next;
5642 tree->tag_infos = list->next;
5645 g_slist_free (list);
5647 g_object_unref (G_OBJECT (info->tag));
5653 list = g_slist_next (list);
5656 g_assert_not_reached ();
5661 recompute_level_zero_counts (GtkTextBTreeNode *node)
5664 GtkTextLineSegment *seg;
5666 g_assert (node->level == 0);
5668 line = node->children.line;
5669 while (line != NULL)
5671 node->num_children++;
5674 if (line->parent != node)
5675 gtk_text_line_set_parent (line, node);
5677 seg = line->segments;
5681 node->num_chars += seg->char_count;
5683 if (((seg->type != >k_text_toggle_on_type)
5684 && (seg->type != >k_text_toggle_off_type))
5685 || !(seg->body.toggle.inNodeCounts))
5691 GtkTextTagInfo *info;
5693 info = seg->body.toggle.info;
5695 gtk_text_btree_node_adjust_toggle_count (node, info, 1);
5706 recompute_level_nonzero_counts (GtkTextBTreeNode *node)
5709 GtkTextBTreeNode *child;
5711 g_assert (node->level > 0);
5713 child = node->children.node;
5714 while (child != NULL)
5716 node->num_children += 1;
5717 node->num_lines += child->num_lines;
5718 node->num_chars += child->num_chars;
5720 if (child->parent != node)
5722 child->parent = node;
5723 gtk_text_btree_node_invalidate_upward (node, NULL);
5726 summary = child->summary;
5727 while (summary != NULL)
5729 gtk_text_btree_node_adjust_toggle_count (node,
5731 summary->toggle_count);
5733 summary = summary->next;
5736 child = child->next;
5741 *----------------------------------------------------------------------
5743 * recompute_node_counts --
5745 * This procedure is called to recompute all the counts in a GtkTextBTreeNode
5746 * (tags, child information, etc.) by scanning the information in
5747 * its descendants. This procedure is called during rebalancing
5748 * when a GtkTextBTreeNode's child structure has changed.
5754 * The tag counts for node are modified to reflect its current
5755 * child structure, as are its num_children, num_lines, num_chars fields.
5756 * Also, all of the childrens' parent fields are made to point
5759 *----------------------------------------------------------------------
5763 recompute_node_counts (GtkTextBTree *tree, GtkTextBTreeNode *node)
5766 Summary *summary, *summary2;
5769 * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
5770 * the existing Summary records (most of them will probably be reused).
5773 summary = node->summary;
5774 while (summary != NULL)
5776 summary->toggle_count = 0;
5777 summary = summary->next;
5780 node->num_children = 0;
5781 node->num_lines = 0;
5782 node->num_chars = 0;
5785 * Scan through the children, adding the childrens' tag counts into
5786 * the GtkTextBTreeNode's tag counts and adding new Summary structures if
5790 if (node->level == 0)
5791 recompute_level_zero_counts (node);
5793 recompute_level_nonzero_counts (node);
5798 gtk_text_btree_node_check_valid (node, view->view_id);
5803 * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
5804 * records that still have a zero count, or that have all the toggles.
5805 * The GtkTextBTreeNode with the children that account for all the tags toggles
5806 * have no summary information, and they become the tag_root for the tag.
5810 for (summary = node->summary; summary != NULL; )
5812 if (summary->toggle_count > 0 &&
5813 summary->toggle_count < summary->info->toggle_count)
5815 if (node->level == summary->info->tag_root->level)
5818 * The tag's root GtkTextBTreeNode split and some toggles left.
5819 * The tag root must move up a level.
5821 summary->info->tag_root = node->parent;
5824 summary = summary->next;
5827 if (summary->toggle_count == summary->info->toggle_count)
5830 * A GtkTextBTreeNode merge has collected all the toggles under
5831 * one GtkTextBTreeNode. Push the root down to this level.
5833 summary->info->tag_root = node;
5835 if (summary2 != NULL)
5837 summary2->next = summary->next;
5838 summary_destroy (summary);
5839 summary = summary2->next;
5843 node->summary = summary->next;
5844 summary_destroy (summary);
5845 summary = node->summary;
5851 _gtk_change_node_toggle_count (GtkTextBTreeNode *node,
5852 GtkTextTagInfo *info,
5853 gint delta) /* may be negative */
5855 Summary *summary, *prevPtr;
5856 GtkTextBTreeNode *node2Ptr;
5857 int rootLevel; /* Level of original tag root */
5859 info->toggle_count += delta;
5861 if (info->tag_root == (GtkTextBTreeNode *) NULL)
5863 info->tag_root = node;
5868 * Note the level of the existing root for the tag so we can detect
5869 * if it needs to be moved because of the toggle count change.
5872 rootLevel = info->tag_root->level;
5875 * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
5876 * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
5880 for ( ; node != info->tag_root; node = node->parent)
5883 * See if there's already an entry for this tag for this GtkTextBTreeNode. If so,
5884 * perhaps all we have to do is adjust its count.
5887 for (prevPtr = NULL, summary = node->summary;
5889 prevPtr = summary, summary = summary->next)
5891 if (summary->info == info)
5896 if (summary != NULL)
5898 summary->toggle_count += delta;
5899 if (summary->toggle_count > 0 &&
5900 summary->toggle_count < info->toggle_count)
5904 if (summary->toggle_count != 0)
5907 * Should never find a GtkTextBTreeNode with max toggle count at this
5908 * point (there shouldn't have been a summary entry in the
5912 g_error ("%s: bad toggle count (%d) max (%d)",
5913 G_STRLOC, summary->toggle_count, info->toggle_count);
5917 * Zero toggle count; must remove this tag from the list.
5920 if (prevPtr == NULL)
5922 node->summary = summary->next;
5926 prevPtr->next = summary->next;
5928 summary_destroy (summary);
5933 * This tag isn't currently in the summary information list.
5936 if (rootLevel == node->level)
5940 * The old tag root is at the same level in the tree as this
5941 * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode. Move the tag root up
5942 * a level, in the hopes that it will now cover this GtkTextBTreeNode
5943 * as well as the old root (if not, we'll move it up again
5944 * the next time through the loop). To push it up one level
5945 * we copy the original toggle count into the summary
5946 * information at the old root and change the root to its
5947 * parent GtkTextBTreeNode.
5950 GtkTextBTreeNode *rootnode = info->tag_root;
5951 summary = (Summary *) g_malloc (sizeof (Summary));
5952 summary->info = info;
5953 summary->toggle_count = info->toggle_count - delta;
5954 summary->next = rootnode->summary;
5955 rootnode->summary = summary;
5956 rootnode = rootnode->parent;
5957 rootLevel = rootnode->level;
5958 info->tag_root = rootnode;
5960 summary = (Summary *) g_malloc (sizeof (Summary));
5961 summary->info = info;
5962 summary->toggle_count = delta;
5963 summary->next = node->summary;
5964 node->summary = summary;
5969 * If we've decremented the toggle count, then it may be necessary
5970 * to push the tag root down one or more levels.
5977 if (info->toggle_count == 0)
5979 info->tag_root = (GtkTextBTreeNode *) NULL;
5982 node = info->tag_root;
5983 while (node->level > 0)
5986 * See if a single child GtkTextBTreeNode accounts for all of the tag's
5987 * toggles. If so, push the root down one level.
5990 for (node2Ptr = node->children.node;
5991 node2Ptr != (GtkTextBTreeNode *)NULL ;
5992 node2Ptr = node2Ptr->next)
5994 for (prevPtr = NULL, summary = node2Ptr->summary;
5996 prevPtr = summary, summary = summary->next)
5998 if (summary->info == info)
6003 if (summary == NULL)
6007 if (summary->toggle_count != info->toggle_count)
6010 * No GtkTextBTreeNode has all toggles, so the root is still valid.
6017 * This GtkTextBTreeNode has all the toggles, so push down the root.
6020 if (prevPtr == NULL)
6022 node2Ptr->summary = summary->next;
6026 prevPtr->next = summary->next;
6028 summary_destroy (summary);
6029 info->tag_root = node2Ptr;
6032 node = info->tag_root;
6037 *----------------------------------------------------------------------
6041 * This is a utility procedure used by _gtk_text_btree_get_tags. It
6042 * increments the count for a particular tag, adding a new
6043 * entry for that tag if there wasn't one previously.
6049 * The information at *tagInfoPtr may be modified, and the arrays
6050 * may be reallocated to make them larger.
6052 *----------------------------------------------------------------------
6056 inc_count (GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
6061 for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
6062 count > 0; tag_p++, count--)
6066 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
6072 * There isn't currently an entry for this tag, so we have to
6073 * make a new one. If the arrays are full, then enlarge the
6077 if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
6079 GtkTextTag **newTags;
6080 int *newCounts, newSize;
6082 newSize = 2*tagInfoPtr->arraySize;
6083 newTags = (GtkTextTag **) g_malloc ((unsigned)
6084 (newSize*sizeof (GtkTextTag *)));
6085 memcpy ((void *) newTags, (void *) tagInfoPtr->tags,
6086 tagInfoPtr->arraySize *sizeof (GtkTextTag *));
6087 g_free ((char *) tagInfoPtr->tags);
6088 tagInfoPtr->tags = newTags;
6089 newCounts = (int *) g_malloc ((unsigned) (newSize*sizeof (int)));
6090 memcpy ((void *) newCounts, (void *) tagInfoPtr->counts,
6091 tagInfoPtr->arraySize *sizeof (int));
6092 g_free ((char *) tagInfoPtr->counts);
6093 tagInfoPtr->counts = newCounts;
6094 tagInfoPtr->arraySize = newSize;
6097 tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
6098 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
6099 tagInfoPtr->numTags++;
6103 gtk_text_btree_link_segment (GtkTextLineSegment *seg,
6104 const GtkTextIter *iter)
6106 GtkTextLineSegment *prev;
6110 line = gtk_text_iter_get_text_line (iter);
6111 tree = gtk_text_iter_get_btree (iter);
6113 prev = gtk_text_line_segment_split (iter);
6116 seg->next = line->segments;
6117 line->segments = seg;
6121 seg->next = prev->next;
6124 cleanup_line (line);
6125 segments_changed (tree);
6127 if (gtk_debug_flags & GTK_DEBUG_TEXT)
6128 _gtk_text_btree_check (tree);
6132 gtk_text_btree_unlink_segment (GtkTextBTree *tree,
6133 GtkTextLineSegment *seg,
6136 GtkTextLineSegment *prev;
6138 if (line->segments == seg)
6140 line->segments = seg->next;
6144 for (prev = line->segments; prev->next != seg;
6147 /* Empty loop body. */
6149 prev->next = seg->next;
6151 cleanup_line (line);
6152 segments_changed (tree);
6156 * This is here because it requires BTree internals, it logically
6157 * belongs in gtktextsegment.c
6162 *--------------------------------------------------------------
6164 * _gtk_toggle_segment_check_func --
6166 * This procedure is invoked to perform consistency checks
6167 * on toggle segments.
6173 * If a consistency problem is found the procedure g_errors.
6175 *--------------------------------------------------------------
6179 _gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6185 if (segPtr->byte_count != 0)
6187 g_error ("toggle_segment_check_func: segment had non-zero size");
6189 if (!segPtr->body.toggle.inNodeCounts)
6191 g_error ("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6193 needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6194 for (summary = line->parent->summary; ;
6195 summary = summary->next)
6197 if (summary == NULL)
6201 g_error ("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6208 if (summary->info == segPtr->body.toggle.info)
6212 g_error ("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6224 gtk_text_btree_node_view_check_consistency (GtkTextBTreeNode *node,
6231 gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6232 &width, &height, &valid);
6233 if (nd->width != width ||
6234 nd->height != height ||
6235 !nd->valid != !valid)
6237 g_error ("Node aggregates for view %p are invalid:\n"
6238 "Are (%d,%d,%s), should be (%d,%d,%s)",
6240 nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6241 width, height, valid ? "TRUE" : "FALSE");
6246 gtk_text_btree_node_check_consistency (GtkTextBTreeNode *node)
6248 GtkTextBTreeNode *childnode;
6249 Summary *summary, *summary2;
6251 GtkTextLineSegment *segPtr;
6252 int num_children, num_lines, num_chars, toggle_count, min_children;
6253 GtkTextLineData *ld;
6256 if (node->parent != NULL)
6258 min_children = MIN_CHILDREN;
6260 else if (node->level > 0)
6267 if ((node->num_children < min_children)
6268 || (node->num_children > MAX_CHILDREN))
6270 g_error ("gtk_text_btree_node_check_consistency: bad child count (%d)",
6271 node->num_children);
6274 nd = node->node_data;
6277 gtk_text_btree_node_view_check_consistency (node, nd);
6284 if (node->level == 0)
6286 for (line = node->children.line; line != NULL;
6289 if (line->parent != node)
6291 g_error ("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6293 if (line->segments == NULL)
6295 g_error ("gtk_text_btree_node_check_consistency: line has no segments");
6301 /* Just ensuring we don't segv while doing this loop */
6306 for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6308 if (segPtr->type->checkFunc != NULL)
6310 (*segPtr->type->checkFunc)(segPtr, line);
6312 if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6313 && (segPtr->next != NULL)
6314 && (segPtr->next->byte_count == 0)
6315 && (segPtr->next->type->leftGravity))
6317 g_error ("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6319 if ((segPtr->next == NULL)
6320 && (segPtr->type != >k_text_char_type))
6322 g_error ("gtk_text_btree_node_check_consistency: line ended with wrong type");
6325 num_chars += segPtr->char_count;
6334 for (childnode = node->children.node; childnode != NULL;
6335 childnode = childnode->next)
6337 if (childnode->parent != node)
6339 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6341 if (childnode->level != (node->level-1))
6343 g_error ("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6344 node->level, childnode->level);
6346 gtk_text_btree_node_check_consistency (childnode);
6347 for (summary = childnode->summary; summary != NULL;
6348 summary = summary->next)
6350 for (summary2 = node->summary; ;
6351 summary2 = summary2->next)
6353 if (summary2 == NULL)
6355 if (summary->info->tag_root == node)
6359 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6360 summary->info->tag->name,
6361 "present in parent summaries");
6363 if (summary->info == summary2->info)
6370 num_lines += childnode->num_lines;
6371 num_chars += childnode->num_chars;
6374 if (num_children != node->num_children)
6376 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6377 num_children, node->num_children);
6379 if (num_lines != node->num_lines)
6381 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6382 num_lines, node->num_lines);
6384 if (num_chars != node->num_chars)
6386 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6387 num_chars, node->num_chars);
6390 for (summary = node->summary; summary != NULL;
6391 summary = summary->next)
6393 if (summary->info->toggle_count == summary->toggle_count)
6395 g_error ("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6396 summary->info->tag->name);
6399 if (node->level == 0)
6401 for (line = node->children.line; line != NULL;
6404 for (segPtr = line->segments; segPtr != NULL;
6405 segPtr = segPtr->next)
6407 if ((segPtr->type != >k_text_toggle_on_type)
6408 && (segPtr->type != >k_text_toggle_off_type))
6412 if (segPtr->body.toggle.info == summary->info)
6414 if (!segPtr->body.toggle.inNodeCounts)
6415 g_error ("Toggle segment not in the node counts");
6424 for (childnode = node->children.node;
6426 childnode = childnode->next)
6428 for (summary2 = childnode->summary;
6430 summary2 = summary2->next)
6432 if (summary2->info == summary->info)
6434 toggle_count += summary2->toggle_count;
6439 if (toggle_count != summary->toggle_count)
6441 g_error ("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6442 toggle_count, summary->toggle_count);
6444 for (summary2 = summary->next; summary2 != NULL;
6445 summary2 = summary2->next)
6447 if (summary2->info == summary->info)
6449 g_error ("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6450 summary->info->tag->name);
6457 listify_foreach (GtkTextTag *tag, gpointer user_data)
6459 GSList** listp = user_data;
6461 *listp = g_slist_prepend (*listp, tag);
6465 list_of_tags (GtkTextTagTable *table)
6467 GSList *list = NULL;
6469 gtk_text_tag_table_foreach (table, listify_foreach, &list);
6475 _gtk_text_btree_check (GtkTextBTree *tree)
6478 GtkTextBTreeNode *node;
6480 GtkTextLineSegment *seg;
6482 GSList *taglist = NULL;
6484 GtkTextTagInfo *info;
6487 * Make sure that the tag toggle counts and the tag root pointers are OK.
6489 for (taglist = list_of_tags (tree->table);
6490 taglist != NULL ; taglist = taglist->next)
6492 tag = taglist->data;
6493 info = gtk_text_btree_get_existing_tag_info (tree, tag);
6496 node = info->tag_root;
6499 if (info->toggle_count != 0)
6501 g_error ("_gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6502 tag->name, info->toggle_count);
6504 continue; /* no ranges for the tag */
6506 else if (info->toggle_count == 0)
6508 g_error ("_gtk_text_btree_check found root for \"%s\" with no toggles",
6511 else if (info->toggle_count & 1)
6513 g_error ("_gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6514 tag->name, info->toggle_count);
6516 for (summary = node->summary; summary != NULL;
6517 summary = summary->next)
6519 if (summary->info->tag == tag)
6521 g_error ("_gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6525 if (node->level > 0)
6527 for (node = node->children.node ; node != NULL ;
6530 for (summary = node->summary; summary != NULL;
6531 summary = summary->next)
6533 if (summary->info->tag == tag)
6535 count += summary->toggle_count;
6542 GtkTextLineSegmentClass * last = NULL;
6544 for (line = node->children.line ; line != NULL ;
6547 for (seg = line->segments; seg != NULL;
6550 if ((seg->type == >k_text_toggle_on_type ||
6551 seg->type == >k_text_toggle_off_type) &&
6552 seg->body.toggle.info->tag == tag)
6554 if (last == seg->type)
6555 g_error ("Two consecutive toggles on or off weren't merged");
6556 if (!seg->body.toggle.inNodeCounts)
6557 g_error ("Toggle segment not in the node counts");
6566 if (count != info->toggle_count)
6568 g_error ("_gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
6569 info->toggle_count, tag->name, count);
6574 g_slist_free (taglist);
6578 * Call a recursive procedure to do the main body of checks.
6581 node = tree->root_node;
6582 gtk_text_btree_node_check_consistency (tree->root_node);
6585 * Make sure that there are at least two lines in the text and
6586 * that the last line has no characters except a newline.
6589 if (node->num_lines < 2)
6591 g_error ("_gtk_text_btree_check: less than 2 lines in tree");
6593 if (node->num_chars < 2)
6595 g_error ("_gtk_text_btree_check: less than 2 chars in tree");
6597 while (node->level > 0)
6599 node = node->children.node;
6600 while (node->next != NULL)
6605 line = node->children.line;
6606 while (line->next != NULL)
6610 seg = line->segments;
6611 while ((seg->type == >k_text_toggle_off_type)
6612 || (seg->type == >k_text_right_mark_type)
6613 || (seg->type == >k_text_left_mark_type))
6616 * It's OK to toggle a tag off in the last line, but
6617 * not to start a new range. It's also OK to have marks
6623 if (seg->type != >k_text_char_type)
6625 g_error ("_gtk_text_btree_check: last line has bogus segment type");
6627 if (seg->next != NULL)
6629 g_error ("_gtk_text_btree_check: last line has too many segments");
6631 if (seg->byte_count != 1)
6633 g_error ("_gtk_text_btree_check: last line has wrong # characters: %d",
6636 if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
6638 g_error ("_gtk_text_btree_check: last line had bad value: %s",
6643 void _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line);
6644 void _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment* seg);
6645 void _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent);
6646 void _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
6649 _gtk_text_btree_spew (GtkTextBTree *tree)
6654 printf ("%d lines in tree %p\n",
6655 _gtk_text_btree_line_count (tree), tree);
6657 line = _gtk_text_btree_get_line (tree, 0, &real_line);
6659 while (line != NULL)
6661 _gtk_text_btree_spew_line (tree, line);
6662 line = _gtk_text_line_next (line);
6665 printf ("=================== Tag information\n");
6670 list = tree->tag_infos;
6672 while (list != NULL)
6674 GtkTextTagInfo *info;
6678 printf (" tag `%s': root at %p, toggle count %d\n",
6679 info->tag->name, info->tag_root, info->toggle_count);
6681 list = g_slist_next (list);
6684 if (tree->tag_infos == NULL)
6686 printf (" (no tags in the tree)\n");
6690 printf ("=================== Tree nodes\n");
6693 _gtk_text_btree_spew_node (tree->root_node, 0);
6698 _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
6701 GtkTextLineSegment *seg;
6703 spaces = g_strnfill (indent, ' ');
6705 printf ("%sline %p chars %d bytes %d\n",
6707 _gtk_text_line_char_count (line),
6708 _gtk_text_line_byte_count (line));
6710 seg = line->segments;
6713 if (seg->type == >k_text_char_type)
6715 gchar* str = g_strndup (seg->body.chars, MIN (seg->byte_count, 10));
6720 if (*s == '\n' || *s == '\r')
6724 printf ("%s chars `%s'...\n", spaces, str);
6727 else if (seg->type == >k_text_right_mark_type)
6729 printf ("%s right mark `%s' visible: %d\n",
6731 seg->body.mark.name,
6732 seg->body.mark.visible);
6734 else if (seg->type == >k_text_left_mark_type)
6736 printf ("%s left mark `%s' visible: %d\n",
6738 seg->body.mark.name,
6739 seg->body.mark.visible);
6741 else if (seg->type == >k_text_toggle_on_type ||
6742 seg->type == >k_text_toggle_off_type)
6744 printf ("%s tag `%s' %s\n",
6745 spaces, seg->body.toggle.info->tag->name,
6746 seg->type == >k_text_toggle_off_type ? "off" : "on");
6756 _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent)
6759 GtkTextBTreeNode *iter;
6762 spaces = g_strnfill (indent, ' ');
6764 printf ("%snode %p level %d children %d lines %d chars %d\n",
6765 spaces, node, node->level,
6766 node->num_children, node->num_lines, node->num_chars);
6771 printf ("%s %d toggles of `%s' below this node\n",
6772 spaces, s->toggle_count, s->info->tag->name);
6778 if (node->level > 0)
6780 iter = node->children.node;
6781 while (iter != NULL)
6783 _gtk_text_btree_spew_node (iter, indent + 2);
6790 GtkTextLine *line = node->children.line;
6791 while (line != NULL)
6793 _gtk_text_btree_spew_line_short (line, indent + 2);
6801 _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line)
6803 GtkTextLineSegment * seg;
6805 printf ("%4d| line: %p parent: %p next: %p\n",
6806 _gtk_text_line_get_number (line), line, line->parent, line->next);
6808 seg = line->segments;
6812 _gtk_text_btree_spew_segment (tree, seg);
6818 _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment * seg)
6820 printf (" segment: %p type: %s bytes: %d chars: %d\n",
6821 seg, seg->type->name, seg->byte_count, seg->char_count);
6823 if (seg->type == >k_text_char_type)
6825 gchar* str = g_strndup (seg->body.chars, seg->byte_count);
6826 printf (" `%s'\n", str);
6829 else if (seg->type == >k_text_right_mark_type)
6831 printf (" right mark `%s' visible: %d not_deleteable: %d\n",
6832 seg->body.mark.name,
6833 seg->body.mark.visible,
6834 seg->body.mark.not_deleteable);
6836 else if (seg->type == >k_text_left_mark_type)
6838 printf (" left mark `%s' visible: %d not_deleteable: %d\n",
6839 seg->body.mark.name,
6840 seg->body.mark.visible,
6841 seg->body.mark.not_deleteable);
6843 else if (seg->type == >k_text_toggle_on_type ||
6844 seg->type == >k_text_toggle_off_type)
6846 printf (" tag `%s' priority %d\n",
6847 seg->body.toggle.info->tag->name,
6848 seg->body.toggle.info->tag->priority);