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 gtk_object_ref (GTK_OBJECT (tree->table));
409 gtk_object_sink (GTK_OBJECT (tree->table));
411 tree->tag_changed_handler = gtk_signal_connect (GTK_OBJECT (tree->table),
413 GTK_SIGNAL_FUNC (tag_changed_cb),
416 tree->tag_removed_handler = gtk_signal_connect (GTK_OBJECT (tree->table),
418 GTK_SIGNAL_FUNC (tag_removed_cb),
421 tree->mark_table = g_hash_table_new (g_str_hash, g_str_equal);
422 tree->child_anchor_table = NULL;
424 /* We don't ref the buffer, since the buffer owns us;
425 * we'd have some circularity issues. The buffer always
426 * lasts longer than the BTree
428 tree->buffer = buffer;
432 GtkTextLineSegment *seg;
434 _gtk_text_btree_get_iter_at_line_char (tree, &start, 0, 0);
437 tree->insert_mark = _gtk_text_btree_set_mark (tree,
444 seg = tree->insert_mark->segment;
446 seg->body.mark.not_deleteable = TRUE;
447 seg->body.mark.visible = TRUE;
449 tree->selection_bound_mark = _gtk_text_btree_set_mark (tree,
456 seg = tree->selection_bound_mark->segment;
458 seg->body.mark.not_deleteable = TRUE;
460 g_object_ref (G_OBJECT (tree->insert_mark));
461 g_object_ref (G_OBJECT (tree->selection_bound_mark));
470 _gtk_text_btree_ref (GtkTextBTree *tree)
472 g_return_if_fail (tree != NULL);
473 g_return_if_fail (tree->refcount > 0);
479 mark_destroy_foreach (gpointer key, gpointer value, gpointer user_data)
481 GtkTextLineSegment *seg = value;
483 g_return_if_fail (seg->body.mark.tree == NULL);
485 g_object_unref (G_OBJECT (seg->body.mark.obj));
489 _gtk_text_btree_unref (GtkTextBTree *tree)
491 g_return_if_fail (tree != NULL);
492 g_return_if_fail (tree->refcount > 0);
496 if (tree->refcount == 0)
498 gtk_text_btree_node_destroy (tree, tree->root_node);
500 g_hash_table_foreach (tree->mark_table,
501 mark_destroy_foreach,
503 g_hash_table_destroy (tree->mark_table);
505 g_object_unref (G_OBJECT (tree->insert_mark));
506 g_object_unref (G_OBJECT (tree->selection_bound_mark));
508 gtk_signal_disconnect (GTK_OBJECT (tree->table),
509 tree->tag_changed_handler);
511 gtk_signal_disconnect (GTK_OBJECT (tree->table),
512 tree->tag_removed_handler);
514 gtk_object_unref (GTK_OBJECT (tree->table));
521 _gtk_text_btree_get_buffer (GtkTextBTree *tree)
527 _gtk_text_btree_get_chars_changed_stamp (GtkTextBTree *tree)
529 return tree->chars_changed_stamp;
533 _gtk_text_btree_get_segments_changed_stamp (GtkTextBTree *tree)
535 return tree->segments_changed_stamp;
539 _gtk_text_btree_segments_changed (GtkTextBTree *tree)
541 g_return_if_fail (tree != NULL);
542 segments_changed (tree);
546 * Indexable segment mutation
550 _gtk_text_btree_delete (GtkTextIter *start,
553 GtkTextLineSegment *prev_seg; /* The segment just before the start
554 * of the deletion range. */
555 GtkTextLineSegment *last_seg; /* The segment just after the end
556 * of the deletion range. */
557 GtkTextLineSegment *seg, *next;
558 GtkTextLine *curline;
559 GtkTextBTreeNode *curnode, *node;
561 GtkTextLine *start_line;
562 GtkTextLine *end_line;
563 GtkTextLine *deleted_lines = NULL; /* List of lines we've deleted */
564 gint start_byte_offset;
566 g_return_if_fail (start != NULL);
567 g_return_if_fail (end != NULL);
568 g_return_if_fail (gtk_text_iter_get_btree (start) ==
569 gtk_text_iter_get_btree (end));
571 gtk_text_iter_reorder (start, end);
573 tree = gtk_text_iter_get_btree (start);
577 * The code below is ugly, but it's needed to make sure there
578 * is always a dummy empty line at the end of the text. If the
579 * final newline of the file (just before the dummy line) is being
580 * deleted, then back up index to just before the newline. If
581 * there is a newline just before the first character being deleted,
582 * then back up the first index too, so that an even number of lines
583 * gets deleted. Furthermore, remove any tags that are present on
584 * the newline that isn't going to be deleted after all (this simulates
585 * deleting the newline and then adding a "clean" one back again).
591 line1 = gtk_text_iter_get_line (start);
592 line2 = gtk_text_iter_get_line (end);
594 if (line2 == _gtk_text_btree_line_count (tree))
598 GtkTextIter orig_end;
601 gtk_text_iter_backward_char (end);
605 if (gtk_text_iter_get_line_offset (start) == 0 &&
608 gtk_text_iter_backward_char (start);
612 tags = _gtk_text_btree_get_tags (end,
620 while (i < array_size)
622 _gtk_text_btree_tag (end, &orig_end, tags[i], FALSE);
632 /* Broadcast the need for redisplay before we break the iterators */
633 _gtk_text_btree_invalidate_region (tree, start, end);
635 /* Save the byte offset so we can reset the iterators */
636 start_byte_offset = gtk_text_iter_get_line_index (start);
638 start_line = gtk_text_iter_get_text_line (start);
639 end_line = gtk_text_iter_get_text_line (end);
642 * Split the start and end segments, so we have a place
643 * to insert our new text.
645 * Tricky point: split at end first; otherwise the split
646 * at end may invalidate seg and/or prev_seg. This allows
647 * us to avoid invalidating segments for start.
650 last_seg = gtk_text_line_segment_split (end);
651 if (last_seg != NULL)
652 last_seg = last_seg->next;
654 last_seg = end_line->segments;
656 prev_seg = gtk_text_line_segment_split (start);
657 if (prev_seg != NULL)
659 seg = prev_seg->next;
660 prev_seg->next = last_seg;
664 seg = start_line->segments;
665 start_line->segments = last_seg;
668 /* notify iterators that their segments need recomputation,
669 just for robustness. */
670 segments_changed (tree);
673 * Delete all of the segments between prev_seg and last_seg.
676 curline = start_line;
677 curnode = curline->parent;
678 while (seg != last_seg)
684 GtkTextLine *nextline;
687 * We just ran off the end of a line. First find the
688 * next line, then go back to the old line and delete it
689 * (unless it's the starting line for the range).
692 nextline = _gtk_text_line_next (curline);
693 if (curline != start_line)
695 if (curnode == start_line->parent)
696 start_line->next = curline->next;
698 curnode->children.line = curline->next;
700 for (node = curnode; node != NULL;
703 node->num_lines -= 1;
706 curnode->num_children -= 1;
707 curline->next = deleted_lines;
708 deleted_lines = curline;
712 seg = curline->segments;
715 * If the GtkTextBTreeNode is empty then delete it and its parents,
716 * recursively upwards until a non-empty GtkTextBTreeNode is found.
719 while (curnode->num_children == 0)
721 GtkTextBTreeNode *parent;
723 parent = curnode->parent;
724 if (parent->children.node == curnode)
726 parent->children.node = curnode->next;
730 GtkTextBTreeNode *prevnode = parent->children.node;
731 while (prevnode->next != curnode)
733 prevnode = prevnode->next;
735 prevnode->next = curnode->next;
737 parent->num_children--;
741 curnode = curline->parent;
746 char_count = seg->char_count;
748 if ((*seg->type->deleteFunc)(seg, curline, 0) != 0)
751 * This segment refuses to die. Move it to prev_seg and
752 * advance prev_seg if the segment has left gravity.
755 if (prev_seg == NULL)
757 seg->next = start_line->segments;
758 start_line->segments = seg;
762 seg->next = prev_seg->next;
763 prev_seg->next = seg;
765 if (seg->type->leftGravity)
772 /* Segment is gone. Decrement the char count of the node and
774 for (node = curnode; node != NULL;
777 node->num_chars -= char_count;
785 * If the beginning and end of the deletion range are in different
786 * lines, join the two lines together and discard the ending line.
789 if (start_line != end_line)
792 GtkTextBTreeNode *ancestor_node;
794 GtkTextLine *prevline;
796 for (seg = last_seg; seg != NULL;
799 if (seg->type->lineChangeFunc != NULL)
801 (*seg->type->lineChangeFunc)(seg, end_line);
804 curnode = end_line->parent;
805 for (node = curnode; node != NULL;
810 curnode->num_children--;
811 prevline = curnode->children.line;
812 if (prevline == end_line)
814 curnode->children.line = end_line->next;
818 while (prevline->next != end_line)
820 prevline = prevline->next;
822 prevline->next = end_line->next;
824 end_line->next = deleted_lines;
825 deleted_lines = end_line;
827 /* We now fix up the per-view aggregates. We add all the height and
828 * width for the deleted lines to the start line, so that when revalidation
829 * occurs, the correct change in size is seen.
831 ancestor_node = gtk_text_btree_node_common_parent (curnode, start_line->parent);
838 gint deleted_width = 0;
839 gint deleted_height = 0;
841 line = deleted_lines;
844 GtkTextLine *next_line = line->next;
845 ld = _gtk_text_line_get_data (line, view->view_id);
849 deleted_width = MAX (deleted_width, ld->width);
850 deleted_height += ld->height;
854 gtk_text_line_destroy (tree, line);
859 if (deleted_width > 0 || deleted_height > 0)
861 ld = _gtk_text_line_get_data (start_line, view->view_id);
863 /* FIXME: ld is _NOT_ necessarily non-null here, but there is currently
864 * no way to add ld without also validating the node, which would
865 * be improper at this point.
867 /* This assertion does actually fail sometimes, must
868 fix before stable release -hp */
871 ld->width = MAX (deleted_width, ld->width);
872 ld->height += deleted_height;
876 gtk_text_btree_node_check_valid_downward (ancestor_node, view->view_id);
877 if (ancestor_node->parent)
878 gtk_text_btree_node_check_valid_upward (ancestor_node->parent, view->view_id);
883 gtk_text_btree_rebalance (tree, curnode);
887 * Cleanup the segments in the new line.
890 cleanup_line (start_line);
893 * Lastly, rebalance the first GtkTextBTreeNode of the range.
896 gtk_text_btree_rebalance (tree, start_line->parent);
898 /* Notify outstanding iterators that they
900 chars_changed (tree);
901 segments_changed (tree);
903 if (gtk_debug_flags & GTK_DEBUG_TEXT)
904 _gtk_text_btree_check (tree);
906 /* Re-initialize our iterators */
907 _gtk_text_btree_get_iter_at_line (tree, start, start_line, start_byte_offset);
912 _gtk_text_btree_insert (GtkTextIter *iter,
916 GtkTextLineSegment *prev_seg; /* The segment just before the first
917 * new segment (NULL means new segment
918 * is at beginning of line). */
919 GtkTextLineSegment *cur_seg; /* Current segment; new characters
920 * are inserted just after this one.
921 * NULL means insert at beginning of
923 GtkTextLine *line; /* Current line (new segments are
924 * added to this line). */
925 GtkTextLineSegment *seg;
926 GtkTextLine *newline;
927 int chunk_len; /* # characters in current chunk. */
928 gint sol; /* start of line */
929 gint eol; /* Pointer to character just after last
930 * one in current chunk.
932 gint delim; /* index of paragraph delimiter */
933 int line_count_delta; /* Counts change to total number of
937 int char_count_delta; /* change to number of chars */
939 gint start_byte_index;
940 GtkTextLine *start_line;
942 g_return_if_fail (text != NULL);
943 g_return_if_fail (iter != NULL);
948 /* extract iterator info */
949 tree = gtk_text_iter_get_btree (iter);
950 line = gtk_text_iter_get_text_line (iter);
952 start_byte_index = gtk_text_iter_get_line_index (iter);
954 /* Get our insertion segment split */
955 prev_seg = gtk_text_line_segment_split (iter);
958 /* Invalidate all iterators */
959 chars_changed (tree);
960 segments_changed (tree);
962 g_assert (g_utf8_validate (text, len, NULL));
965 * Chop the text up into lines and create a new segment for
966 * each line, plus a new line for the leftovers from the
972 line_count_delta = 0;
973 char_count_delta = 0;
978 pango_find_paragraph_boundary (text + sol,
983 /* make these relative to the start of the text */
987 g_assert (eol >= sol);
988 g_assert (delim >= sol);
989 g_assert (eol >= delim);
991 g_assert (eol <= len);
993 chunk_len = eol - sol;
995 g_assert (g_utf8_validate (&text[sol], chunk_len, NULL));
996 seg = _gtk_char_segment_new (&text[sol], chunk_len);
998 char_count_delta += seg->char_count;
1000 if (cur_seg == NULL)
1002 seg->next = line->segments;
1003 line->segments = seg;
1007 seg->next = cur_seg->next;
1008 cur_seg->next = seg;
1013 /* chunk didn't end with a paragraph separator */
1014 g_assert (eol == len);
1019 * The chunk ended with a newline, so create a new GtkTextLine
1020 * and move the remainder of the old line to it.
1023 newline = gtk_text_line_new ();
1024 gtk_text_line_set_parent (newline, line->parent);
1025 newline->next = line->next;
1026 line->next = newline;
1027 newline->segments = seg->next;
1035 * Cleanup the starting line for the insertion, plus the ending
1036 * line if it's different.
1039 cleanup_line (start_line);
1040 if (line != start_line)
1042 cleanup_line (line);
1045 post_insert_fixup (tree, line, line_count_delta, char_count_delta);
1047 /* Invalidate our region, and reset the iterator the user
1048 passed in to point to the end of the inserted text. */
1054 _gtk_text_btree_get_iter_at_line (tree,
1060 /* We could almost certainly be more efficient here
1061 by saving the information from the insertion loop
1063 gtk_text_iter_forward_chars (&end, char_count_delta);
1065 _gtk_text_btree_invalidate_region (tree,
1069 /* Convenience for the user */
1075 insert_pixbuf_or_widget_segment (GtkTextIter *iter,
1076 GtkTextLineSegment *seg)
1080 GtkTextLineSegment *prevPtr;
1083 gint start_byte_offset;
1085 line = gtk_text_iter_get_text_line (iter);
1086 tree = gtk_text_iter_get_btree (iter);
1087 start_byte_offset = gtk_text_iter_get_line_index (iter);
1089 prevPtr = gtk_text_line_segment_split (iter);
1090 if (prevPtr == NULL)
1092 seg->next = line->segments;
1093 line->segments = seg;
1097 seg->next = prevPtr->next;
1098 prevPtr->next = seg;
1101 post_insert_fixup (tree, line, 0, seg->char_count);
1103 chars_changed (tree);
1104 segments_changed (tree);
1106 /* reset *iter for the user, and invalidate tree nodes */
1108 _gtk_text_btree_get_iter_at_line (tree, &start, line, start_byte_offset);
1111 gtk_text_iter_forward_char (iter); /* skip forward past the segment */
1113 _gtk_text_btree_invalidate_region (tree, &start, iter);
1117 _gtk_text_btree_insert_pixbuf (GtkTextIter *iter,
1120 GtkTextLineSegment *seg;
1122 seg = _gtk_pixbuf_segment_new (pixbuf);
1124 insert_pixbuf_or_widget_segment (iter, seg);
1128 _gtk_text_btree_create_child_anchor (GtkTextIter *iter)
1130 GtkTextLineSegment *seg;
1133 seg = _gtk_widget_segment_new ();
1135 tree = seg->body.child.tree = gtk_text_iter_get_btree (iter);
1137 insert_pixbuf_or_widget_segment (iter, seg);
1139 if (tree->child_anchor_table == NULL)
1140 tree->child_anchor_table = g_hash_table_new (NULL, NULL);
1142 g_hash_table_insert (tree->child_anchor_table,
1143 seg->body.child.obj,
1144 seg->body.child.obj);
1146 return seg->body.child.obj;
1150 _gtk_text_btree_unregister_child_anchor (GtkTextChildAnchor *anchor)
1152 GtkTextLineSegment *seg;
1154 seg = anchor->segment;
1156 g_hash_table_remove (seg->body.child.tree->child_anchor_table,
1165 find_line_by_y (GtkTextBTree *tree, BTreeView *view,
1166 GtkTextBTreeNode *node, gint y, gint *line_top,
1167 GtkTextLine *last_line)
1171 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1172 _gtk_text_btree_check (tree);
1174 if (node->level == 0)
1178 line = node->children.line;
1180 while (line != NULL && line != last_line)
1182 GtkTextLineData *ld;
1184 ld = _gtk_text_line_get_data (line, view->view_id);
1188 if (y < (current_y + (ld ? ld->height : 0)))
1191 current_y += ld->height;
1192 *line_top += ld->height;
1201 GtkTextBTreeNode *child;
1203 child = node->children.node;
1205 while (child != NULL)
1210 gtk_text_btree_node_get_size (child, view->view_id,
1213 if (y < (current_y + height))
1214 return find_line_by_y (tree, view, child,
1215 y - current_y, line_top,
1218 current_y += height;
1219 *line_top += height;
1221 child = child->next;
1229 _gtk_text_btree_find_line_by_y (GtkTextBTree *tree,
1236 GtkTextLine *last_line;
1239 view = gtk_text_btree_get_view (tree, view_id);
1240 g_return_val_if_fail (view != NULL, NULL);
1242 last_line = get_last_line (tree);
1244 line = find_line_by_y (tree, view, tree->root_node, ypixel, &line_top,
1248 *line_top_out = line_top;
1254 find_line_top_in_line_list (GtkTextBTree *tree,
1257 GtkTextLine *target_line,
1260 while (line != NULL)
1262 GtkTextLineData *ld;
1264 if (line == target_line)
1267 ld = _gtk_text_line_get_data (line, view->view_id);
1274 g_assert_not_reached (); /* If we get here, our
1275 target line didn't exist
1276 under its parent node */
1281 _gtk_text_btree_find_line_top (GtkTextBTree *tree,
1282 GtkTextLine *target_line,
1289 GtkTextBTreeNode *node;
1291 view = gtk_text_btree_get_view (tree, view_id);
1293 g_return_val_if_fail (view != NULL, 0);
1296 node = target_line->parent;
1297 while (node != NULL)
1299 nodes = g_slist_prepend (nodes, node);
1300 node = node->parent;
1304 while (iter != NULL)
1308 if (node->level == 0)
1310 g_slist_free (nodes);
1311 return find_line_top_in_line_list (tree, view,
1312 node->children.line,
1317 GtkTextBTreeNode *child;
1318 GtkTextBTreeNode *target_node;
1320 g_assert (iter->next != NULL); /* not at level 0 */
1321 target_node = iter->next->data;
1323 child = node->children.node;
1325 while (child != NULL)
1330 if (child == target_node)
1334 gtk_text_btree_node_get_size (child, view->view_id,
1338 child = child->next;
1340 g_assert (child != NULL); /* should have broken out before we
1344 iter = g_slist_next (iter);
1347 g_assert_not_reached (); /* we return when we find the target line */
1352 _gtk_text_btree_add_view (GtkTextBTree *tree,
1353 GtkTextLayout *layout)
1356 GtkTextLine *last_line;
1357 GtkTextLineData *line_data;
1359 g_return_if_fail (tree != NULL);
1361 view = g_new (BTreeView, 1);
1363 view->view_id = layout;
1364 view->layout = layout;
1366 view->next = tree->views;
1371 /* The last line in the buffer has identity values for the per-view
1372 * data so that we can avoid special case checks for it in a large
1375 last_line = get_last_line (tree);
1377 line_data = g_new (GtkTextLineData, 1);
1378 line_data->view_id = layout;
1379 line_data->next = NULL;
1380 line_data->width = 0;
1381 line_data->height = 0;
1382 line_data->valid = TRUE;
1384 _gtk_text_line_add_data (last_line, line_data);
1388 _gtk_text_btree_remove_view (GtkTextBTree *tree,
1392 GtkTextLine *last_line;
1393 GtkTextLineData *line_data;
1395 g_return_if_fail (tree != NULL);
1399 while (view != NULL)
1401 if (view->view_id == view_id)
1407 g_return_if_fail (view != NULL);
1410 view->next->prev = view->prev;
1413 view->prev->next = view->next;
1415 if (view == tree->views)
1416 tree->views = view->next;
1418 /* Remove the line data for the last line which we added ourselves.
1419 * (Do this first, so that we don't try to call the view's line data destructor on it.)
1421 last_line = get_last_line (tree);
1422 line_data = _gtk_text_line_remove_data (last_line, view_id);
1425 gtk_text_btree_node_remove_view (view, tree->root_node, view_id);
1431 _gtk_text_btree_invalidate_region (GtkTextBTree *tree,
1432 const GtkTextIter *start,
1433 const GtkTextIter *end)
1439 while (view != NULL)
1441 gtk_text_layout_invalidate (view->layout, start, end);
1448 _gtk_text_btree_get_view_size (GtkTextBTree *tree,
1453 g_return_if_fail (tree != NULL);
1454 g_return_if_fail (view_id != NULL);
1456 gtk_text_btree_node_get_size (tree->root_node, view_id,
1471 iter_stack_new (void)
1474 stack = g_new (IterStack, 1);
1475 stack->iters = NULL;
1482 iter_stack_push (IterStack *stack, const GtkTextIter *iter)
1485 if (stack->count > stack->alloced)
1487 stack->alloced = stack->count*2;
1488 stack->iters = g_realloc (stack->iters,
1489 stack->alloced*sizeof (GtkTextIter));
1491 stack->iters[stack->count-1] = *iter;
1495 iter_stack_pop (IterStack *stack, GtkTextIter *iter)
1497 if (stack->count == 0)
1502 *iter = stack->iters[stack->count];
1508 iter_stack_free (IterStack *stack)
1510 g_free (stack->iters);
1515 iter_stack_invert (IterStack *stack)
1517 if (stack->count > 0)
1520 guint j = stack->count - 1;
1525 tmp = stack->iters[i];
1526 stack->iters[i] = stack->iters[j];
1527 stack->iters[j] = tmp;
1536 queue_tag_redisplay (GtkTextBTree *tree,
1538 const GtkTextIter *start,
1539 const GtkTextIter *end)
1541 if (gtk_text_tag_affects_size (tag))
1543 _gtk_text_btree_invalidate_region (tree, start, end);
1546 else if (gtk_text_tag_affects_nonsize_appearance (tag))
1548 /* We only need to queue a redraw, not a relayout */
1549 redisplay_region (tree, start, end);
1552 /* We don't need to do anything if the tag doesn't affect display */
1556 _gtk_text_btree_tag (const GtkTextIter *start_orig,
1557 const GtkTextIter *end_orig,
1561 GtkTextLineSegment *seg, *prev;
1562 GtkTextLine *cleanupline;
1563 gboolean toggled_on;
1564 GtkTextLine *start_line;
1565 GtkTextLine *end_line;
1567 GtkTextIter start, end;
1570 GtkTextTagInfo *info;
1572 g_return_if_fail (start_orig != NULL);
1573 g_return_if_fail (end_orig != NULL);
1574 g_return_if_fail (GTK_IS_TEXT_TAG (tag));
1575 g_return_if_fail (gtk_text_iter_get_btree (start_orig) ==
1576 gtk_text_iter_get_btree (end_orig));
1579 printf ("%s tag %s from %d to %d\n",
1580 add ? "Adding" : "Removing",
1582 gtk_text_buffer_get_offset (start_orig),
1583 gtk_text_buffer_get_offset (end_orig));
1586 if (gtk_text_iter_equal (start_orig, end_orig))
1589 start = *start_orig;
1592 gtk_text_iter_reorder (&start, &end);
1594 tree = gtk_text_iter_get_btree (&start);
1596 queue_tag_redisplay (tree, tag, &start, &end);
1598 info = gtk_text_btree_get_tag_info (tree, tag);
1600 start_line = gtk_text_iter_get_text_line (&start);
1601 end_line = gtk_text_iter_get_text_line (&end);
1603 /* Find all tag toggles in the region; we are going to delete them.
1604 We need to find them in advance, because
1605 forward_find_tag_toggle () won't work once we start playing around
1607 stack = iter_stack_new ();
1609 /* We don't want to delete a toggle that's at the start iterator. */
1610 gtk_text_iter_forward_char (&iter);
1611 while (gtk_text_iter_forward_to_tag_toggle (&iter, tag))
1613 if (gtk_text_iter_compare (&iter, &end) >= 0)
1616 iter_stack_push (stack, &iter);
1619 /* We need to traverse the toggles in order. */
1620 iter_stack_invert (stack);
1623 * See whether the tag is present at the start of the range. If
1624 * the state doesn't already match what we want then add a toggle
1628 toggled_on = gtk_text_iter_has_tag (&start, tag);
1629 if ( (add && !toggled_on) ||
1630 (!add && toggled_on) )
1632 /* This could create a second toggle at the start position;
1633 cleanup_line () will remove it if so. */
1634 seg = _gtk_toggle_segment_new (info, add);
1636 prev = gtk_text_line_segment_split (&start);
1639 seg->next = start_line->segments;
1640 start_line->segments = seg;
1644 seg->next = prev->next;
1648 /* cleanup_line adds the new toggle to the node counts. */
1650 printf ("added toggle at start\n");
1652 /* we should probably call segments_changed, but in theory
1653 any still-cached segments in the iters we are about to
1654 use are still valid, since they're in front
1660 * Scan the range of characters and delete any internal tag
1661 * transitions. Keep track of what the old state was at the end
1662 * of the range, and add a toggle there if it's needed.
1666 cleanupline = start_line;
1667 while (iter_stack_pop (stack, &iter))
1669 GtkTextLineSegment *indexable_seg;
1672 line = gtk_text_iter_get_text_line (&iter);
1673 seg = gtk_text_iter_get_any_segment (&iter);
1674 indexable_seg = gtk_text_iter_get_indexable_segment (&iter);
1676 g_assert (seg != NULL);
1677 g_assert (indexable_seg != NULL);
1678 g_assert (seg != indexable_seg);
1680 prev = line->segments;
1682 /* Find the segment that actually toggles this tag. */
1683 while (seg != indexable_seg)
1685 g_assert (seg != NULL);
1686 g_assert (indexable_seg != NULL);
1687 g_assert (seg != indexable_seg);
1689 if ( (seg->type == >k_text_toggle_on_type ||
1690 seg->type == >k_text_toggle_off_type) &&
1691 (seg->body.toggle.info == info) )
1697 g_assert (seg != NULL);
1698 g_assert (indexable_seg != NULL);
1700 g_assert (seg != indexable_seg); /* If this happens, then
1701 forward_to_tag_toggle was
1703 g_assert (seg->body.toggle.info->tag == tag);
1705 /* If this happens, when previously tagging we didn't merge
1706 overlapping tags. */
1707 g_assert ( (toggled_on && seg->type == >k_text_toggle_off_type) ||
1708 (!toggled_on && seg->type == >k_text_toggle_on_type) );
1710 toggled_on = !toggled_on;
1713 printf ("deleting %s toggle\n",
1714 seg->type == >k_text_toggle_on_type ? "on" : "off");
1716 /* Remove toggle segment from the list. */
1719 line->segments = seg->next;
1723 while (prev->next != seg)
1727 prev->next = seg->next;
1730 /* Inform iterators we've hosed them. This actually reflects a
1731 bit of inefficiency; if you have the same tag toggled on and
1732 off a lot in a single line, we keep having the rescan from
1733 the front of the line. Of course we have to do that to get
1734 "prev" anyway, but here we are doing it an additional
1736 segments_changed (tree);
1738 /* Update node counts */
1739 if (seg->body.toggle.inNodeCounts)
1741 _gtk_change_node_toggle_count (line->parent,
1743 seg->body.toggle.inNodeCounts = FALSE;
1748 /* We only clean up lines when we're done with them, saves some
1749 gratuitous line-segment-traversals */
1751 if (cleanupline != line)
1753 cleanup_line (cleanupline);
1758 iter_stack_free (stack);
1760 /* toggled_on now reflects the toggle state _just before_ the
1761 end iterator. The end iterator could already have a toggle
1762 on or a toggle off. */
1763 if ( (add && !toggled_on) ||
1764 (!add && toggled_on) )
1766 /* This could create a second toggle at the start position;
1767 cleanup_line () will remove it if so. */
1769 seg = _gtk_toggle_segment_new (info, !add);
1771 prev = gtk_text_line_segment_split (&end);
1774 seg->next = end_line->segments;
1775 end_line->segments = seg;
1779 seg->next = prev->next;
1782 /* cleanup_line adds the new toggle to the node counts. */
1783 g_assert (seg->body.toggle.inNodeCounts == FALSE);
1785 printf ("added toggle at end\n");
1790 * Cleanup cleanupline and the last line of the range, if
1791 * these are different.
1794 cleanup_line (cleanupline);
1795 if (cleanupline != end_line)
1797 cleanup_line (end_line);
1800 segments_changed (tree);
1802 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1803 _gtk_text_btree_check (tree);
1812 _gtk_text_btree_get_line (GtkTextBTree *tree,
1814 gint *real_line_number)
1816 GtkTextBTreeNode *node;
1821 line_count = _gtk_text_btree_line_count (tree);
1823 if (line_number < 0)
1825 line_number = line_count;
1827 else if (line_number > line_count)
1829 line_number = line_count;
1832 if (real_line_number)
1833 *real_line_number = line_number;
1835 node = tree->root_node;
1836 lines_left = line_number;
1839 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1843 while (node->level != 0)
1845 for (node = node->children.node;
1846 node->num_lines <= lines_left;
1852 g_error ("gtk_text_btree_find_line ran out of GtkTextBTreeNodes");
1855 lines_left -= node->num_lines;
1860 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1863 for (line = node->children.line; lines_left > 0;
1869 g_error ("gtk_text_btree_find_line ran out of lines");
1878 _gtk_text_btree_get_line_at_char (GtkTextBTree *tree,
1880 gint *line_start_index,
1881 gint *real_char_index)
1883 GtkTextBTreeNode *node;
1885 GtkTextLineSegment *seg;
1890 node = tree->root_node;
1892 /* Clamp to valid indexes (-1 is magic for "highest index") */
1893 if (char_index < 0 || char_index >= node->num_chars)
1895 char_index = node->num_chars - 1;
1898 *real_char_index = char_index;
1901 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1905 chars_left = char_index;
1906 while (node->level != 0)
1908 for (node = node->children.node;
1909 chars_left >= node->num_chars;
1912 chars_left -= node->num_chars;
1914 g_assert (chars_left >= 0);
1918 if (chars_left == 0)
1920 /* Start of a line */
1922 *line_start_index = char_index;
1923 return node->children.line;
1927 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1933 for (line = node->children.line; line != NULL; line = line->next)
1935 seg = line->segments;
1938 if (chars_in_line + seg->char_count > chars_left)
1939 goto found; /* found our line/segment */
1941 chars_in_line += seg->char_count;
1946 chars_left -= chars_in_line;
1954 g_assert (line != NULL); /* hosage, ran out of lines */
1955 g_assert (seg != NULL);
1957 *line_start_index = char_index - chars_left;
1962 _gtk_text_btree_get_tags (const GtkTextIter *iter,
1965 GtkTextBTreeNode *node;
1966 GtkTextLine *siblingline;
1967 GtkTextLineSegment *seg;
1968 int src, dst, index;
1974 #define NUM_TAG_INFOS 10
1976 line = gtk_text_iter_get_text_line (iter);
1977 tree = gtk_text_iter_get_btree (iter);
1978 byte_index = gtk_text_iter_get_line_index (iter);
1980 tagInfo.numTags = 0;
1981 tagInfo.arraySize = NUM_TAG_INFOS;
1982 tagInfo.tags = g_new (GtkTextTag*, NUM_TAG_INFOS);
1983 tagInfo.counts = g_new (int, NUM_TAG_INFOS);
1986 * Record tag toggles within the line of indexPtr but preceding
1987 * indexPtr. Note that if this loop segfaults, your
1988 * byte_index probably points past the sum of all
1989 * seg->byte_count */
1991 for (index = 0, seg = line->segments;
1992 (index + seg->byte_count) <= byte_index;
1993 index += seg->byte_count, seg = seg->next)
1995 if ((seg->type == >k_text_toggle_on_type)
1996 || (seg->type == >k_text_toggle_off_type))
1998 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2003 * Record toggles for tags in lines that are predecessors of
2004 * line but under the same level-0 GtkTextBTreeNode.
2007 for (siblingline = line->parent->children.line;
2008 siblingline != line;
2009 siblingline = siblingline->next)
2011 for (seg = siblingline->segments; seg != NULL;
2014 if ((seg->type == >k_text_toggle_on_type)
2015 || (seg->type == >k_text_toggle_off_type))
2017 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2023 * For each GtkTextBTreeNode in the ancestry of this line, record tag
2024 * toggles for all siblings that precede that GtkTextBTreeNode.
2027 for (node = line->parent; node->parent != NULL;
2028 node = node->parent)
2030 GtkTextBTreeNode *siblingPtr;
2033 for (siblingPtr = node->parent->children.node;
2034 siblingPtr != node; siblingPtr = siblingPtr->next)
2036 for (summary = siblingPtr->summary; summary != NULL;
2037 summary = summary->next)
2039 if (summary->toggle_count & 1)
2041 inc_count (summary->info->tag, summary->toggle_count,
2049 * Go through the tag information and squash out all of the tags
2050 * that have even toggle counts (these tags exist before the point
2051 * of interest, but not at the desired character itself).
2054 for (src = 0, dst = 0; src < tagInfo.numTags; src++)
2056 if (tagInfo.counts[src] & 1)
2058 g_assert (GTK_IS_TEXT_TAG (tagInfo.tags[src]));
2059 tagInfo.tags[dst] = tagInfo.tags[src];
2065 g_free (tagInfo.counts);
2068 g_free (tagInfo.tags);
2071 return tagInfo.tags;
2075 copy_segment (GString *string,
2076 gboolean include_hidden,
2077 gboolean include_nonchars,
2078 const GtkTextIter *start,
2079 const GtkTextIter *end)
2081 GtkTextLineSegment *end_seg;
2082 GtkTextLineSegment *seg;
2084 if (gtk_text_iter_equal (start, end))
2087 seg = gtk_text_iter_get_indexable_segment (start);
2088 end_seg = gtk_text_iter_get_indexable_segment (end);
2090 if (seg->type == >k_text_char_type)
2092 gboolean copy = TRUE;
2093 gint copy_bytes = 0;
2094 gint copy_start = 0;
2096 /* Don't copy if we're invisible; segments are invisible/not
2097 as a whole, no need to check each char */
2098 if (!include_hidden &&
2099 _gtk_text_btree_char_is_invisible (start))
2102 /* printf (" <invisible>\n"); */
2105 copy_start = gtk_text_iter_get_segment_byte (start);
2109 /* End is in the same segment; need to copy fewer bytes. */
2110 gint end_byte = gtk_text_iter_get_segment_byte (end);
2112 copy_bytes = end_byte - copy_start;
2115 copy_bytes = seg->byte_count - copy_start;
2117 g_assert (copy_bytes != 0); /* Due to iter equality check at
2118 front of this function. */
2122 g_assert ((copy_start + copy_bytes) <= seg->byte_count);
2124 g_string_append_len (string,
2125 seg->body.chars + copy_start,
2129 /* printf (" :%s\n", string->str); */
2131 else if (seg->type == >k_text_pixbuf_type ||
2132 seg->type == >k_text_child_type)
2134 gboolean copy = TRUE;
2136 if (!include_nonchars)
2140 else if (!include_hidden &&
2141 _gtk_text_btree_char_is_invisible (start))
2148 g_string_append_len (string,
2149 gtk_text_unknown_char_utf8,
2157 _gtk_text_btree_get_text (const GtkTextIter *start_orig,
2158 const GtkTextIter *end_orig,
2159 gboolean include_hidden,
2160 gboolean include_nonchars)
2162 GtkTextLineSegment *seg;
2163 GtkTextLineSegment *end_seg;
2171 g_return_val_if_fail (start_orig != NULL, NULL);
2172 g_return_val_if_fail (end_orig != NULL, NULL);
2173 g_return_val_if_fail (gtk_text_iter_get_btree (start_orig) ==
2174 gtk_text_iter_get_btree (end_orig), NULL);
2176 start = *start_orig;
2179 gtk_text_iter_reorder (&start, &end);
2181 retval = g_string_new ("");
2183 tree = gtk_text_iter_get_btree (&start);
2185 end_seg = gtk_text_iter_get_indexable_segment (&end);
2187 seg = gtk_text_iter_get_indexable_segment (&iter);
2188 while (seg != end_seg)
2190 copy_segment (retval, include_hidden, include_nonchars,
2193 gtk_text_iter_forward_indexable_segment (&iter);
2195 seg = gtk_text_iter_get_indexable_segment (&iter);
2198 copy_segment (retval, include_hidden, include_nonchars, &iter, &end);
2201 g_string_free (retval, FALSE);
2206 _gtk_text_btree_line_count (GtkTextBTree *tree)
2208 /* Subtract bogus line at the end; we return a count
2210 return tree->root_node->num_lines - 1;
2214 _gtk_text_btree_char_count (GtkTextBTree *tree)
2216 /* Exclude newline in bogus last line */
2217 return tree->root_node->num_chars - 1;
2220 #define LOTSA_TAGS 1000
2222 _gtk_text_btree_char_is_invisible (const GtkTextIter *iter)
2224 gboolean invisible = FALSE; /* if nobody says otherwise, it's visible */
2226 int deftagCnts[LOTSA_TAGS];
2227 int *tagCnts = deftagCnts;
2228 GtkTextTag *deftags[LOTSA_TAGS];
2229 GtkTextTag **tags = deftags;
2231 GtkTextBTreeNode *node;
2232 GtkTextLine *siblingline;
2233 GtkTextLineSegment *seg;
2240 line = gtk_text_iter_get_text_line (iter);
2241 tree = gtk_text_iter_get_btree (iter);
2242 byte_index = gtk_text_iter_get_line_index (iter);
2244 numTags = gtk_text_tag_table_size (tree->table);
2246 /* almost always avoid malloc, so stay out of system calls */
2247 if (LOTSA_TAGS < numTags)
2249 tagCnts = g_new (int, numTags);
2250 tags = g_new (GtkTextTag*, numTags);
2253 for (i=0; i<numTags; i++)
2259 * Record tag toggles within the line of indexPtr but preceding
2263 for (index = 0, seg = line->segments;
2264 (index + seg->byte_count) <= byte_index; /* segfault here means invalid index */
2265 index += seg->byte_count, seg = seg->next)
2267 if ((seg->type == >k_text_toggle_on_type)
2268 || (seg->type == >k_text_toggle_off_type))
2270 tag = seg->body.toggle.info->tag;
2271 if (tag->invisible_set && tag->values->invisible)
2273 tags[tag->priority] = tag;
2274 tagCnts[tag->priority]++;
2280 * Record toggles for tags in lines that are predecessors of
2281 * line but under the same level-0 GtkTextBTreeNode.
2284 for (siblingline = line->parent->children.line;
2285 siblingline != line;
2286 siblingline = siblingline->next)
2288 for (seg = siblingline->segments; seg != NULL;
2291 if ((seg->type == >k_text_toggle_on_type)
2292 || (seg->type == >k_text_toggle_off_type))
2294 tag = seg->body.toggle.info->tag;
2295 if (tag->invisible_set && tag->values->invisible)
2297 tags[tag->priority] = tag;
2298 tagCnts[tag->priority]++;
2305 * For each GtkTextBTreeNode in the ancestry of this line, record tag toggles
2306 * for all siblings that precede that GtkTextBTreeNode.
2309 for (node = line->parent; node->parent != NULL;
2310 node = node->parent)
2312 GtkTextBTreeNode *siblingPtr;
2315 for (siblingPtr = node->parent->children.node;
2316 siblingPtr != node; siblingPtr = siblingPtr->next)
2318 for (summary = siblingPtr->summary; summary != NULL;
2319 summary = summary->next)
2321 if (summary->toggle_count & 1)
2323 tag = summary->info->tag;
2324 if (tag->invisible_set && tag->values->invisible)
2326 tags[tag->priority] = tag;
2327 tagCnts[tag->priority] += summary->toggle_count;
2335 * Now traverse from highest priority to lowest,
2336 * take invisible value from first odd count (= on)
2339 for (i = numTags-1; i >=0; i--)
2343 /* FIXME not sure this should be if 0 */
2345 #ifndef ALWAYS_SHOW_SELECTION
2346 /* who would make the selection invisible? */
2347 if ((tag == tkxt->seltag)
2348 && !(tkxt->flags & GOT_FOCUS))
2354 invisible = tags[i]->values->invisible;
2359 if (LOTSA_TAGS < numTags)
2374 redisplay_region (GtkTextBTree *tree,
2375 const GtkTextIter *start,
2376 const GtkTextIter *end)
2379 GtkTextLine *start_line, *end_line;
2381 if (gtk_text_iter_compare (start, end) > 0)
2383 const GtkTextIter *tmp = start;
2388 start_line = gtk_text_iter_get_text_line (start);
2389 end_line = gtk_text_iter_get_text_line (end);
2392 while (view != NULL)
2394 gint start_y, end_y;
2395 GtkTextLineData *ld;
2397 start_y = _gtk_text_btree_find_line_top (tree, start_line, view->view_id);
2399 if (end_line == start_line)
2402 end_y = _gtk_text_btree_find_line_top (tree, end_line, view->view_id);
2404 ld = _gtk_text_line_get_data (end_line, view->view_id);
2406 end_y += ld->height;
2408 gtk_text_layout_changed (view->layout, start_y,
2417 redisplay_mark (GtkTextLineSegment *mark)
2422 _gtk_text_btree_get_iter_at_mark (mark->body.mark.tree,
2424 mark->body.mark.obj);
2427 gtk_text_iter_forward_char (&end);
2429 _gtk_text_btree_invalidate_region (mark->body.mark.tree,
2434 redisplay_mark_if_visible (GtkTextLineSegment *mark)
2436 if (!mark->body.mark.visible)
2439 redisplay_mark (mark);
2443 ensure_not_off_end (GtkTextBTree *tree,
2444 GtkTextLineSegment *mark,
2447 if (gtk_text_iter_get_line (iter) ==
2448 _gtk_text_btree_line_count (tree))
2449 gtk_text_iter_backward_char (iter);
2452 static GtkTextLineSegment*
2453 real_set_mark (GtkTextBTree *tree,
2454 GtkTextMark *existing_mark,
2456 gboolean left_gravity,
2457 const GtkTextIter *where,
2458 gboolean should_exist,
2459 gboolean redraw_selections)
2461 GtkTextLineSegment *mark;
2464 g_return_val_if_fail (tree != NULL, NULL);
2465 g_return_val_if_fail (where != NULL, NULL);
2466 g_return_val_if_fail (gtk_text_iter_get_btree (where) == tree, NULL);
2469 mark = existing_mark->segment;
2470 else if (name != NULL)
2471 mark = g_hash_table_lookup (tree->mark_table,
2476 if (should_exist && mark == NULL)
2478 g_warning ("No mark `%s' exists!", name);
2482 /* OK if !should_exist and it does already exist, in that case
2488 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2489 gtk_text_iter_check (&iter);
2493 if (redraw_selections &&
2494 (mark == tree->insert_mark->segment ||
2495 mark == tree->selection_bound_mark->segment))
2497 GtkTextIter old_pos;
2499 _gtk_text_btree_get_iter_at_mark (tree, &old_pos,
2500 mark->body.mark.obj);
2501 redisplay_region (tree, &old_pos, where);
2505 * don't let visible marks be after the final newline of the
2509 if (mark->body.mark.visible)
2511 ensure_not_off_end (tree, mark, &iter);
2514 /* Redraw the mark's old location. */
2515 redisplay_mark_if_visible (mark);
2517 /* Unlink mark from its current location.
2518 This could hose our iterator... */
2519 gtk_text_btree_unlink_segment (tree, mark,
2520 mark->body.mark.line);
2521 mark->body.mark.line = gtk_text_iter_get_text_line (&iter);
2522 g_assert (mark->body.mark.line == gtk_text_iter_get_text_line (&iter));
2524 segments_changed (tree); /* make sure the iterator recomputes its
2529 mark = _gtk_mark_segment_new (tree,
2533 mark->body.mark.line = gtk_text_iter_get_text_line (&iter);
2535 if (mark->body.mark.name)
2536 g_hash_table_insert (tree->mark_table,
2537 mark->body.mark.name,
2541 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2542 gtk_text_iter_check (&iter);
2544 /* Link mark into new location */
2545 gtk_text_btree_link_segment (mark, &iter);
2547 /* Invalidate some iterators. */
2548 segments_changed (tree);
2551 * update the screen at the mark's new location.
2554 redisplay_mark_if_visible (mark);
2556 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2557 gtk_text_iter_check (&iter);
2559 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2560 _gtk_text_btree_check (tree);
2567 _gtk_text_btree_set_mark (GtkTextBTree *tree,
2568 GtkTextMark *existing_mark,
2570 gboolean left_gravity,
2571 const GtkTextIter *iter,
2572 gboolean should_exist)
2574 GtkTextLineSegment *seg;
2576 seg = real_set_mark (tree, existing_mark,
2577 name, left_gravity, iter, should_exist,
2580 return seg ? seg->body.mark.obj : NULL;
2584 _gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2588 GtkTextIter tmp_start, tmp_end;
2590 _gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2592 _gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2593 tree->selection_bound_mark);
2595 if (gtk_text_iter_equal (&tmp_start, &tmp_end))
2607 gtk_text_iter_reorder (&tmp_start, &tmp_end);
2620 _gtk_text_btree_place_cursor (GtkTextBTree *tree,
2621 const GtkTextIter *iter)
2623 GtkTextIter start, end;
2625 if (_gtk_text_btree_get_selection_bounds (tree, &start, &end))
2626 redisplay_region (tree, &start, &end);
2628 /* Move insert AND selection_bound before we redisplay */
2629 real_set_mark (tree, tree->insert_mark,
2630 "insert", FALSE, iter, TRUE, FALSE);
2631 real_set_mark (tree, tree->selection_bound_mark,
2632 "selection_bound", FALSE, iter, TRUE, FALSE);
2636 _gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2641 g_return_if_fail (tree != NULL);
2642 g_return_if_fail (name != NULL);
2644 mark = g_hash_table_lookup (tree->mark_table,
2647 _gtk_text_btree_remove_mark (tree, mark);
2651 _gtk_text_btree_remove_mark (GtkTextBTree *tree,
2654 GtkTextLineSegment *segment;
2656 g_return_if_fail (mark != NULL);
2657 g_return_if_fail (tree != NULL);
2659 segment = mark->segment;
2661 if (segment->body.mark.not_deleteable)
2663 g_warning ("Can't delete special mark `%s'", segment->body.mark.name);
2667 /* This calls cleanup_line and segments_changed */
2668 gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2670 if (segment->body.mark.name)
2671 g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2673 /* Remove the ref on the mark that belonged to the segment. */
2674 g_object_unref (G_OBJECT (mark));
2676 segment->body.mark.tree = NULL;
2677 segment->body.mark.line = NULL;
2681 _gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2682 GtkTextMark *segment)
2684 return segment == tree->insert_mark;
2688 _gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2689 GtkTextMark *segment)
2691 return segment == tree->selection_bound_mark;
2695 _gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2698 GtkTextLineSegment *seg;
2700 g_return_val_if_fail (tree != NULL, NULL);
2701 g_return_val_if_fail (name != NULL, NULL);
2703 seg = g_hash_table_lookup (tree->mark_table, name);
2705 return seg ? seg->body.mark.obj : NULL;
2709 gtk_text_mark_set_visible (GtkTextMark *mark,
2712 GtkTextLineSegment *seg;
2714 g_return_if_fail (mark != NULL);
2716 seg = mark->segment;
2718 if (seg->body.mark.visible == setting)
2722 seg->body.mark.visible = setting;
2724 redisplay_mark (seg);
2729 _gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
2732 GtkTextBTreeNode *node;
2733 GtkTextTagInfo *info;
2735 g_return_val_if_fail (tree != NULL, NULL);
2739 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2744 if (info->tag_root == NULL)
2747 node = info->tag_root;
2749 /* We know the tag root has instances of the given
2752 continue_outer_loop:
2753 g_assert (node != NULL);
2754 while (node->level > 0)
2756 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2757 node = node->children.node;
2758 while (node != NULL)
2760 if (gtk_text_btree_node_has_tag (node, tag))
2761 goto continue_outer_loop;
2765 g_assert (node != NULL);
2768 g_assert (node != NULL); /* The tag summaries said some node had
2771 g_assert (node->level == 0);
2773 return node->children.line;
2777 /* Looking for any tag at all (tag == NULL).
2778 Unfortunately this can't be done in a simple and efficient way
2779 right now; so I'm just going to return the
2780 first line in the btree. FIXME */
2781 return _gtk_text_btree_get_line (tree, 0, NULL);
2786 _gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
2789 GtkTextBTreeNode *node;
2790 GtkTextBTreeNode *last_node;
2792 GtkTextTagInfo *info;
2794 g_return_val_if_fail (tree != NULL, NULL);
2798 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2800 if (info->tag_root == NULL)
2803 node = info->tag_root;
2804 /* We know the tag root has instances of the given
2807 while (node->level > 0)
2809 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2811 node = node->children.node;
2812 while (node != NULL)
2814 if (gtk_text_btree_node_has_tag (node, tag))
2822 g_assert (node != NULL); /* The tag summaries said some node had
2825 g_assert (node->level == 0);
2827 /* Find the last line in this node */
2828 line = node->children.line;
2829 while (line->next != NULL)
2836 /* This search can't be done efficiently at the moment,
2837 at least not without complexity.
2838 So, we just return the last line.
2840 return _gtk_text_btree_get_line (tree, -1, NULL);
2850 _gtk_text_line_get_number (GtkTextLine *line)
2853 GtkTextBTreeNode *node, *parent, *node2;
2857 * First count how many lines precede this one in its level-0
2861 node = line->parent;
2863 for (line2 = node->children.line; line2 != line;
2864 line2 = line2->next)
2868 g_error ("gtk_text_btree_line_number couldn't find line");
2874 * Now work up through the levels of the tree one at a time,
2875 * counting how many lines are in GtkTextBTreeNodes preceding the current
2879 for (parent = node->parent ; parent != NULL;
2880 node = parent, parent = parent->parent)
2882 for (node2 = parent->children.node; node2 != node;
2883 node2 = node2->next)
2887 g_error ("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
2889 index += node2->num_lines;
2895 static GtkTextLineSegment*
2896 find_toggle_segment_before_char (GtkTextLine *line,
2900 GtkTextLineSegment *seg;
2901 GtkTextLineSegment *toggle_seg;
2906 seg = line->segments;
2907 while ( (index + seg->char_count) <= char_in_line )
2909 if (((seg->type == >k_text_toggle_on_type)
2910 || (seg->type == >k_text_toggle_off_type))
2911 && (seg->body.toggle.info->tag == tag))
2914 index += seg->char_count;
2921 static GtkTextLineSegment*
2922 find_toggle_segment_before_byte (GtkTextLine *line,
2926 GtkTextLineSegment *seg;
2927 GtkTextLineSegment *toggle_seg;
2932 seg = line->segments;
2933 while ( (index + seg->byte_count) <= byte_in_line )
2935 if (((seg->type == >k_text_toggle_on_type)
2936 || (seg->type == >k_text_toggle_off_type))
2937 && (seg->body.toggle.info->tag == tag))
2940 index += seg->byte_count;
2948 find_toggle_outside_current_line (GtkTextLine *line,
2952 GtkTextBTreeNode *node;
2953 GtkTextLine *sibling_line;
2954 GtkTextLineSegment *seg;
2955 GtkTextLineSegment *toggle_seg;
2957 GtkTextTagInfo *info = NULL;
2960 * No toggle in this line. Look for toggles for the tag in lines
2961 * that are predecessors of line but under the same
2962 * level-0 GtkTextBTreeNode.
2965 sibling_line = line->parent->children.line;
2966 while (sibling_line != line)
2968 seg = sibling_line->segments;
2971 if (((seg->type == >k_text_toggle_on_type)
2972 || (seg->type == >k_text_toggle_off_type))
2973 && (seg->body.toggle.info->tag == tag))
2979 sibling_line = sibling_line->next;
2982 if (toggle_seg != NULL)
2983 return (toggle_seg->type == >k_text_toggle_on_type);
2986 * No toggle in this GtkTextBTreeNode. Scan upwards through the ancestors of
2987 * this GtkTextBTreeNode, counting the number of toggles of the given tag in
2988 * siblings that precede that GtkTextBTreeNode.
2991 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2997 node = line->parent;
2998 while (node->parent != NULL)
3000 GtkTextBTreeNode *sibling_node;
3002 sibling_node = node->parent->children.node;
3003 while (sibling_node != node)
3007 summary = sibling_node->summary;
3008 while (summary != NULL)
3010 if (summary->info == info)
3011 toggles += summary->toggle_count;
3013 summary = summary->next;
3016 sibling_node = sibling_node->next;
3019 if (node == info->tag_root)
3022 node = node->parent;
3026 * An odd number of toggles means that the tag is present at the
3030 return (toggles & 1) != 0;
3033 /* FIXME this function is far too slow, for no good reason. */
3035 _gtk_text_line_char_has_tag (GtkTextLine *line,
3040 GtkTextLineSegment *toggle_seg;
3042 g_return_val_if_fail (line != NULL, FALSE);
3045 * Check for toggles for the tag in the line but before
3046 * the char. If there is one, its type indicates whether or
3047 * not the character is tagged.
3050 toggle_seg = find_toggle_segment_before_char (line, char_in_line, tag);
3052 if (toggle_seg != NULL)
3053 return (toggle_seg->type == >k_text_toggle_on_type);
3055 return find_toggle_outside_current_line (line, tree, tag);
3059 _gtk_text_line_byte_has_tag (GtkTextLine *line,
3064 GtkTextLineSegment *toggle_seg;
3066 g_return_val_if_fail (line != NULL, FALSE);
3069 * Check for toggles for the tag in the line but before
3070 * the char. If there is one, its type indicates whether or
3071 * not the character is tagged.
3074 toggle_seg = find_toggle_segment_before_byte (line, byte_in_line, tag);
3076 if (toggle_seg != NULL)
3077 return (toggle_seg->type == >k_text_toggle_on_type);
3079 return find_toggle_outside_current_line (line, tree, tag);
3083 _gtk_text_line_is_last (GtkTextLine *line,
3086 return line == get_last_line (tree);
3090 _gtk_text_line_next (GtkTextLine *line)
3092 GtkTextBTreeNode *node;
3094 if (line->next != NULL)
3099 * This was the last line associated with the particular parent
3100 * GtkTextBTreeNode. Search up the tree for the next GtkTextBTreeNode,
3101 * then search down from that GtkTextBTreeNode to find the first
3105 node = line->parent;
3106 while (node != NULL && node->next == NULL)
3107 node = node->parent;
3113 while (node->level > 0)
3115 node = node->children.node;
3118 g_assert (node->children.line != line);
3120 return node->children.line;
3125 _gtk_text_line_previous (GtkTextLine *line)
3127 GtkTextBTreeNode *node;
3128 GtkTextBTreeNode *node2;
3132 * Find the line under this GtkTextBTreeNode just before the starting line.
3134 prev = line->parent->children.line; /* First line at leaf */
3135 while (prev != line)
3137 if (prev->next == line)
3143 g_error ("gtk_text_btree_previous_line ran out of lines");
3147 * This was the first line associated with the particular parent
3148 * GtkTextBTreeNode. Search up the tree for the previous GtkTextBTreeNode,
3149 * then search down from that GtkTextBTreeNode to find its last line.
3151 for (node = line->parent; ; node = node->parent)
3153 if (node == NULL || node->parent == NULL)
3155 else if (node != node->parent->children.node)
3159 for (node2 = node->parent->children.node; ;
3160 node2 = node2->children.node)
3162 while (node2->next != node)
3163 node2 = node2->next;
3165 if (node2->level == 0)
3171 for (prev = node2->children.line ; ; prev = prev->next)
3173 if (prev->next == NULL)
3177 g_assert_not_reached ();
3182 _gtk_text_line_add_data (GtkTextLine *line,
3183 GtkTextLineData *data)
3185 g_return_if_fail (line != NULL);
3186 g_return_if_fail (data != NULL);
3187 g_return_if_fail (data->view_id != NULL);
3191 data->next = line->views;
3201 _gtk_text_line_remove_data (GtkTextLine *line,
3204 GtkTextLineData *prev;
3205 GtkTextLineData *iter;
3207 g_return_val_if_fail (line != NULL, NULL);
3208 g_return_val_if_fail (view_id != NULL, NULL);
3212 while (iter != NULL)
3214 if (iter->view_id == view_id)
3223 prev->next = iter->next;
3225 line->views = iter->next;
3234 _gtk_text_line_get_data (GtkTextLine *line,
3237 GtkTextLineData *iter;
3239 g_return_val_if_fail (line != NULL, NULL);
3240 g_return_val_if_fail (view_id != NULL, NULL);
3243 while (iter != NULL)
3245 if (iter->view_id == view_id)
3254 _gtk_text_line_invalidate_wrap (GtkTextLine *line,
3255 GtkTextLineData *ld)
3257 /* For now this is totally unoptimized. FIXME?
3259 We could probably optimize the case where the width removed
3260 is less than the max width for the parent node,
3261 and the case where the height is unchanged when we re-wrap.
3264 g_return_if_fail (ld != NULL);
3267 gtk_text_btree_node_invalidate_upward (line->parent, ld->view_id);
3271 _gtk_text_line_char_count (GtkTextLine *line)
3273 GtkTextLineSegment *seg;
3277 seg = line->segments;
3280 size += seg->char_count;
3287 _gtk_text_line_byte_count (GtkTextLine *line)
3289 GtkTextLineSegment *seg;
3293 seg = line->segments;
3296 size += seg->byte_count;
3304 _gtk_text_line_char_index (GtkTextLine *target_line)
3306 GSList *node_stack = NULL;
3307 GtkTextBTreeNode *iter;
3311 /* Push all our parent nodes onto a stack */
3312 iter = target_line->parent;
3314 g_assert (iter != NULL);
3316 while (iter != NULL)
3318 node_stack = g_slist_prepend (node_stack, iter);
3320 iter = iter->parent;
3323 /* Check that we have the root node on top of the stack. */
3324 g_assert (node_stack != NULL &&
3325 node_stack->data != NULL &&
3326 ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3328 /* Add up chars in all nodes before the nodes in our stack.
3332 iter = node_stack->data;
3333 while (iter != NULL)
3335 GtkTextBTreeNode *child_iter;
3336 GtkTextBTreeNode *next_node;
3338 next_node = node_stack->next ?
3339 node_stack->next->data : NULL;
3340 node_stack = g_slist_remove (node_stack, node_stack->data);
3342 if (iter->level == 0)
3344 /* stack should be empty when we're on the last node */
3345 g_assert (node_stack == NULL);
3346 break; /* Our children are now lines */
3349 g_assert (next_node != NULL);
3350 g_assert (iter != NULL);
3351 g_assert (next_node->parent == iter);
3353 /* Add up chars before us in the tree */
3354 child_iter = iter->children.node;
3355 while (child_iter != next_node)
3357 g_assert (child_iter != NULL);
3359 num_chars += child_iter->num_chars;
3361 child_iter = child_iter->next;
3367 g_assert (iter != NULL);
3368 g_assert (iter == target_line->parent);
3370 /* Since we don't store char counts in lines, only in segments, we
3371 have to iterate over the lines adding up segment char counts
3372 until we find our line. */
3373 line = iter->children.line;
3374 while (line != target_line)
3376 g_assert (line != NULL);
3378 num_chars += _gtk_text_line_char_count (line);
3383 g_assert (line == target_line);
3389 _gtk_text_line_byte_to_segment (GtkTextLine *line,
3393 GtkTextLineSegment *seg;
3396 g_return_val_if_fail (line != NULL, NULL);
3398 offset = byte_offset;
3399 seg = line->segments;
3401 while (offset >= seg->byte_count)
3403 g_assert (seg != NULL); /* means an invalid byte index */
3404 offset -= seg->byte_count;
3409 *seg_offset = offset;
3415 _gtk_text_line_char_to_segment (GtkTextLine *line,
3419 GtkTextLineSegment *seg;
3422 g_return_val_if_fail (line != NULL, NULL);
3424 offset = char_offset;
3425 seg = line->segments;
3427 while (offset >= seg->char_count)
3429 g_assert (seg != NULL); /* means an invalid char index */
3430 offset -= seg->char_count;
3435 *seg_offset = offset;
3441 _gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3445 GtkTextLineSegment *seg;
3448 g_return_val_if_fail (line != NULL, NULL);
3450 offset = byte_offset;
3451 seg = line->segments;
3453 while (offset > 0 && offset >= seg->byte_count)
3455 g_assert (seg != NULL); /* means an invalid byte index */
3456 offset -= seg->byte_count;
3461 *seg_offset = offset;
3467 _gtk_text_line_char_to_any_segment (GtkTextLine *line,
3471 GtkTextLineSegment *seg;
3474 g_return_val_if_fail (line != NULL, NULL);
3476 offset = char_offset;
3477 seg = line->segments;
3479 while (offset > 0 && offset >= seg->char_count)
3481 g_assert (seg != NULL); /* means an invalid byte index */
3482 offset -= seg->char_count;
3487 *seg_offset = offset;
3493 _gtk_text_line_byte_to_char (GtkTextLine *line,
3497 GtkTextLineSegment *seg;
3499 g_return_val_if_fail (line != NULL, 0);
3500 g_return_val_if_fail (byte_offset >= 0, 0);
3503 seg = line->segments;
3504 while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3505 the next segment) */
3507 g_assert (seg != NULL); /* our byte_index was bogus if this happens */
3509 byte_offset -= seg->byte_count;
3510 char_offset += seg->char_count;
3515 g_assert (seg != NULL);
3517 /* Now byte_offset is the offset into the current segment,
3518 and char_offset is the start of the current segment.
3519 Optimize the case where no chars use > 1 byte */
3520 if (seg->byte_count == seg->char_count)
3521 return char_offset + byte_offset;
3524 if (seg->type == >k_text_char_type)
3525 return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3528 g_assert (seg->char_count == 1);
3529 g_assert (byte_offset == 0);
3537 _gtk_text_line_char_to_byte (GtkTextLine *line,
3540 g_warning ("FIXME not implemented");
3545 /* FIXME sync with char_locate (or figure out a clean
3546 way to merge the two functions) */
3548 _gtk_text_line_byte_locate (GtkTextLine *line,
3550 GtkTextLineSegment **segment,
3551 GtkTextLineSegment **any_segment,
3552 gint *seg_byte_offset,
3553 gint *line_byte_offset)
3555 GtkTextLineSegment *seg;
3556 GtkTextLineSegment *after_prev_indexable;
3557 GtkTextLineSegment *after_last_indexable;
3558 GtkTextLineSegment *last_indexable;
3562 g_return_if_fail (line != NULL);
3564 if (byte_offset < 0)
3566 /* -1 means end of line; we here assume no line is
3567 longer than 1 bazillion bytes, of course we assumed
3568 that anyway since we'd wrap around... */
3570 byte_offset = G_MAXINT;
3574 *any_segment = NULL;
3577 offset = byte_offset;
3579 last_indexable = NULL;
3580 after_last_indexable = line->segments;
3581 after_prev_indexable = line->segments;
3582 seg = line->segments;
3584 /* The loop ends when we're inside a segment;
3585 last_indexable refers to the last segment
3586 we passed entirely. */
3587 while (seg && offset >= seg->byte_count)
3589 if (seg->char_count > 0)
3591 offset -= seg->byte_count;
3592 bytes_in_line += seg->byte_count;
3593 last_indexable = seg;
3594 after_prev_indexable = after_last_indexable;
3595 after_last_indexable = last_indexable->next;
3603 /* We went off the end of the line */
3604 *segment = last_indexable;
3605 *any_segment = after_prev_indexable;
3606 /* subtracting 1 is OK, we know it's a newline at the end. */
3607 offset = (*segment)->byte_count - 1;
3608 bytes_in_line -= (*segment)->byte_count;
3613 if (after_last_indexable != NULL)
3614 *any_segment = after_last_indexable;
3616 *any_segment = *segment;
3619 /* Override any_segment if we're in the middle of a segment. */
3621 *any_segment = *segment;
3623 *seg_byte_offset = offset;
3625 g_assert (*segment != NULL);
3626 g_assert (*any_segment != NULL);
3627 g_assert (*seg_byte_offset < (*segment)->byte_count);
3629 *line_byte_offset = bytes_in_line + *seg_byte_offset;
3632 /* FIXME sync with byte_locate (or figure out a clean
3633 way to merge the two functions) */
3635 _gtk_text_line_char_locate (GtkTextLine *line,
3637 GtkTextLineSegment **segment,
3638 GtkTextLineSegment **any_segment,
3639 gint *seg_char_offset,
3640 gint *line_char_offset)
3642 GtkTextLineSegment *seg;
3643 GtkTextLineSegment *after_prev_indexable;
3644 GtkTextLineSegment *after_last_indexable;
3645 GtkTextLineSegment *last_indexable;
3649 g_return_if_fail (line != NULL);
3651 if (char_offset < 0)
3653 /* -1 means end of line; we here assume no line is
3654 longer than 1 bazillion chars, of course we assumed
3655 that anyway since we'd wrap around... */
3657 char_offset = G_MAXINT;
3661 *any_segment = NULL;
3664 offset = char_offset;
3666 last_indexable = NULL;
3667 after_last_indexable = line->segments;
3668 after_prev_indexable = line->segments;
3669 seg = line->segments;
3671 /* The loop ends when we're inside a segment;
3672 last_indexable refers to the last segment
3673 we passed entirely. */
3674 while (seg && offset >= seg->char_count)
3676 if (seg->char_count > 0)
3678 offset -= seg->char_count;
3679 chars_in_line += seg->char_count;
3680 last_indexable = seg;
3681 after_prev_indexable = after_last_indexable;
3682 after_last_indexable = last_indexable->next;
3690 /* We went off the end of the line */
3691 *segment = last_indexable;
3692 *any_segment = after_prev_indexable;
3693 /* subtracting 1 is OK, we know it's a newline at the end. */
3694 offset = (*segment)->char_count - 1;
3695 chars_in_line -= (*segment)->char_count;
3700 if (after_last_indexable != NULL)
3701 *any_segment = after_last_indexable;
3703 *any_segment = *segment;
3706 /* Override any_segment if we're in the middle of a segment. */
3708 *any_segment = *segment;
3710 *seg_char_offset = offset;
3712 g_assert (*segment != NULL);
3713 g_assert (*any_segment != NULL);
3714 g_assert (*seg_char_offset < (*segment)->char_count);
3716 *line_char_offset = chars_in_line + *seg_char_offset;
3720 _gtk_text_line_byte_to_char_offsets (GtkTextLine *line,
3722 gint *line_char_offset,
3723 gint *seg_char_offset)
3725 GtkTextLineSegment *seg;
3728 g_return_if_fail (line != NULL);
3729 g_return_if_fail (byte_offset >= 0);
3731 *line_char_offset = 0;
3733 offset = byte_offset;
3734 seg = line->segments;
3736 while (offset >= seg->byte_count)
3738 offset -= seg->byte_count;
3739 *line_char_offset += seg->char_count;
3741 g_assert (seg != NULL); /* means an invalid char offset */
3744 g_assert (seg->char_count > 0); /* indexable. */
3746 /* offset is now the number of bytes into the current segment we
3747 * want to go. Count chars into the current segment.
3750 if (seg->type == >k_text_char_type)
3752 *seg_char_offset = g_utf8_strlen (seg->body.chars, offset);
3754 g_assert (*seg_char_offset < seg->char_count);
3756 *line_char_offset += *seg_char_offset;
3760 g_assert (offset == 0);
3761 *seg_char_offset = 0;
3766 _gtk_text_line_char_to_byte_offsets (GtkTextLine *line,
3768 gint *line_byte_offset,
3769 gint *seg_byte_offset)
3771 GtkTextLineSegment *seg;
3774 g_return_if_fail (line != NULL);
3775 g_return_if_fail (char_offset >= 0);
3777 *line_byte_offset = 0;
3779 offset = char_offset;
3780 seg = line->segments;
3782 while (offset >= seg->char_count)
3784 offset -= seg->char_count;
3785 *line_byte_offset += seg->byte_count;
3787 g_assert (seg != NULL); /* means an invalid char offset */
3790 g_assert (seg->char_count > 0); /* indexable. */
3792 /* offset is now the number of chars into the current segment we
3793 want to go. Count bytes into the current segment. */
3795 if (seg->type == >k_text_char_type)
3797 *seg_byte_offset = 0;
3801 const char * start = seg->body.chars + *seg_byte_offset;
3803 bytes = g_utf8_next_char (start) - start;
3804 *seg_byte_offset += bytes;
3808 g_assert (*seg_byte_offset < seg->byte_count);
3810 *line_byte_offset += *seg_byte_offset;
3814 g_assert (offset == 0);
3815 *seg_byte_offset = 0;
3820 node_compare (GtkTextBTreeNode *lhs,
3821 GtkTextBTreeNode *rhs)
3823 GtkTextBTreeNode *iter;
3824 GtkTextBTreeNode *node;
3825 GtkTextBTreeNode *common_parent;
3826 GtkTextBTreeNode *parent_of_lower;
3827 GtkTextBTreeNode *parent_of_higher;
3828 gboolean lhs_is_lower;
3829 GtkTextBTreeNode *lower;
3830 GtkTextBTreeNode *higher;
3832 /* This function assumes that lhs and rhs are not underneath each
3839 if (lhs->level < rhs->level)
3841 lhs_is_lower = TRUE;
3847 lhs_is_lower = FALSE;
3852 /* Algorithm: find common parent of lhs/rhs. Save the child nodes
3853 * of the common parent we used to reach the common parent; the
3854 * ordering of these child nodes in the child list is the ordering
3858 /* Get on the same level (may be on same level already) */
3860 while (node->level < higher->level)
3861 node = node->parent;
3863 g_assert (node->level == higher->level);
3865 g_assert (node != higher); /* Happens if lower is underneath higher */
3867 /* Go up until we have two children with a common parent.
3869 parent_of_lower = node;
3870 parent_of_higher = higher;
3872 while (parent_of_lower->parent != parent_of_higher->parent)
3874 parent_of_lower = parent_of_lower->parent;
3875 parent_of_higher = parent_of_higher->parent;
3878 g_assert (parent_of_lower->parent == parent_of_higher->parent);
3880 common_parent = parent_of_lower->parent;
3882 g_assert (common_parent != NULL);
3884 /* See which is first in the list of common_parent's children */
3885 iter = common_parent->children.node;
3886 while (iter != NULL)
3888 if (iter == parent_of_higher)
3890 /* higher is less than lower */
3893 return 1; /* lhs > rhs */
3897 else if (iter == parent_of_lower)
3899 /* lower is less than higher */
3902 return -1; /* lhs < rhs */
3910 g_assert_not_reached ();
3914 /* remember that tag == NULL means "any tag" */
3916 _gtk_text_line_next_could_contain_tag (GtkTextLine *line,
3920 GtkTextBTreeNode *node;
3921 GtkTextTagInfo *info;
3922 gboolean below_tag_root;
3924 g_return_val_if_fail (line != NULL, NULL);
3926 if (gtk_debug_flags & GTK_DEBUG_TEXT)
3927 _gtk_text_btree_check (tree);
3931 /* Right now we can only offer linear-search if the user wants
3932 * to know about any tag toggle at all.
3934 return _gtk_text_line_next (line);
3937 /* Our tag summaries only have node precision, not line
3938 precision. This means that if any line under a node could contain a
3939 tag, then any of the others could also contain a tag.
3941 In the future we could have some mechanism to keep track of how
3942 many toggles we've found under a node so far, since we have a
3943 count of toggles under the node. But for now I'm going with KISS.
3946 /* return same-node line, if any. */
3950 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3954 if (info->tag_root == NULL)
3957 if (info->tag_root == line->parent)
3958 return NULL; /* we were at the last line under the tag root */
3960 /* We need to go up out of this node, and on to the next one with
3961 toggles for the target tag. If we're below the tag root, we need to
3962 find the next node below the tag root that has tag summaries. If
3963 we're not below the tag root, we need to see if the tag root is
3964 after us in the tree, and if so, return the first line underneath
3967 node = line->parent;
3968 below_tag_root = FALSE;
3969 while (node != NULL)
3971 if (node == info->tag_root)
3973 below_tag_root = TRUE;
3977 node = node->parent;
3982 node = line->parent;
3983 while (node != info->tag_root)
3985 if (node->next == NULL)
3986 node = node->parent;
3991 if (gtk_text_btree_node_has_tag (node, tag))
4001 ordering = node_compare (line->parent, info->tag_root);
4005 /* Tag root is ahead of us, so search there. */
4006 node = info->tag_root;
4011 /* Tag root is after us, so no more lines that
4012 * could contain the tag.
4017 g_assert_not_reached ();
4022 g_assert (node != NULL);
4024 /* We have to find the first sub-node of this node that contains
4028 while (node->level > 0)
4030 g_assert (node != NULL); /* If this fails, it likely means an
4031 incorrect tag summary led us on a
4032 wild goose chase down this branch of
4034 node = node->children.node;
4035 while (node != NULL)
4037 if (gtk_text_btree_node_has_tag (node, tag))
4043 g_assert (node != NULL);
4044 g_assert (node->level == 0);
4046 return node->children.line;
4050 prev_line_under_node (GtkTextBTreeNode *node,
4055 prev = node->children.line;
4061 while (prev->next != line)
4071 _gtk_text_line_previous_could_contain_tag (GtkTextLine *line,
4075 GtkTextBTreeNode *node;
4076 GtkTextBTreeNode *found_node = NULL;
4077 GtkTextTagInfo *info;
4078 gboolean below_tag_root;
4080 GtkTextBTreeNode *line_ancestor;
4081 GtkTextBTreeNode *line_ancestor_parent;
4083 /* See next_could_contain_tag () for more extensive comments
4084 * on what's going on here.
4087 g_return_val_if_fail (line != NULL, NULL);
4089 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4090 _gtk_text_btree_check (tree);
4094 /* Right now we can only offer linear-search if the user wants
4095 * to know about any tag toggle at all.
4097 return _gtk_text_line_previous (line);
4100 /* Return same-node line, if any. */
4101 prev = prev_line_under_node (line->parent, line);
4105 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4109 if (info->tag_root == NULL)
4112 if (info->tag_root == line->parent)
4113 return NULL; /* we were at the first line under the tag root */
4115 /* Are we below the tag root */
4116 node = line->parent;
4117 below_tag_root = FALSE;
4118 while (node != NULL)
4120 if (node == info->tag_root)
4122 below_tag_root = TRUE;
4126 node = node->parent;
4131 /* Look for a previous node under this tag root that has our
4135 /* this assertion holds because line->parent is not the
4136 * tag root, we are below the tag root, and the tag
4139 g_assert (line->parent->parent != NULL);
4141 line_ancestor = line->parent;
4142 line_ancestor_parent = line->parent->parent;
4144 node = line_ancestor_parent->children.node;
4145 while (node != line_ancestor &&
4146 line_ancestor != info->tag_root)
4148 GSList *child_nodes = NULL;
4151 /* Create reverse-order list of nodes before
4154 while (node != line_ancestor
4157 child_nodes = g_slist_prepend (child_nodes, node);
4162 /* Try to find a node with our tag on it in the list */
4166 GtkTextBTreeNode *this_node = tmp->data;
4168 g_assert (this_node != line_ancestor);
4170 if (gtk_text_btree_node_has_tag (this_node, tag))
4172 found_node = this_node;
4173 g_slist_free (child_nodes);
4177 tmp = g_slist_next (tmp);
4180 g_slist_free (child_nodes);
4182 /* Didn't find anything on this level; go up one level. */
4183 line_ancestor = line_ancestor_parent;
4184 line_ancestor_parent = line_ancestor->parent;
4186 node = line_ancestor_parent->children.node;
4196 ordering = node_compare (line->parent, info->tag_root);
4200 /* Tag root is ahead of us, so no more lines
4207 /* Tag root is after us, so grab last tagged
4208 * line underneath the tag root.
4210 found_node = info->tag_root;
4214 g_assert_not_reached ();
4219 g_assert (found_node != NULL);
4221 /* We have to find the last sub-node of this node that contains
4226 while (node->level > 0)
4228 GSList *child_nodes = NULL;
4230 g_assert (node != NULL); /* If this fails, it likely means an
4231 incorrect tag summary led us on a
4232 wild goose chase down this branch of
4235 node = node->children.node;
4236 while (node != NULL)
4238 child_nodes = g_slist_prepend (child_nodes, node);
4242 node = NULL; /* detect failure to find a child node. */
4245 while (iter != NULL)
4247 if (gtk_text_btree_node_has_tag (iter->data, tag))
4249 /* recurse into this node. */
4254 iter = g_slist_next (iter);
4257 g_slist_free (child_nodes);
4259 g_assert (node != NULL);
4262 g_assert (node != NULL);
4263 g_assert (node->level == 0);
4265 /* this assertion is correct, but slow. */
4266 /* g_assert (node_compare (node, line->parent) < 0); */
4268 /* Return last line in this node. */
4270 prev = node->children.line;
4278 * Non-public function implementations
4282 summary_list_destroy (Summary *summary)
4285 while (summary != NULL)
4287 next = summary->next;
4288 summary_destroy (summary);
4294 get_last_line (GtkTextBTree *tree)
4296 if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
4302 n_lines = _gtk_text_btree_line_count (tree);
4304 g_assert (n_lines >= 1); /* num_lines doesn't return bogus last line. */
4306 line = _gtk_text_btree_get_line (tree, n_lines, &real_line);
4308 tree->end_iter_line_stamp = tree->chars_changed_stamp;
4309 tree->end_iter_line = line;
4312 return tree->end_iter_line;
4320 gtk_text_line_new (void)
4324 line = g_new0(GtkTextLine, 1);
4330 gtk_text_line_destroy (GtkTextBTree *tree, GtkTextLine *line)
4332 GtkTextLineData *ld;
4333 GtkTextLineData *next;
4335 g_return_if_fail (line != NULL);
4342 view = gtk_text_btree_get_view (tree, ld->view_id);
4344 g_assert (view != NULL);
4347 gtk_text_layout_free_line_data (view->layout, line, ld);
4356 gtk_text_line_set_parent (GtkTextLine *line,
4357 GtkTextBTreeNode *node)
4359 if (line->parent == node)
4361 line->parent = node;
4362 gtk_text_btree_node_invalidate_upward (node, NULL);
4366 cleanup_line (GtkTextLine *line)
4368 GtkTextLineSegment *seg, **prev_p;
4372 * Make a pass over all of the segments in the line, giving each
4373 * a chance to clean itself up. This could potentially change
4374 * the structure of the line, e.g. by merging two segments
4375 * together or having two segments cancel themselves; if so,
4376 * then repeat the whole process again, since the first structure
4377 * change might make other structure changes possible. Repeat
4378 * until eventually there are no changes.
4385 for (prev_p = &line->segments, seg = *prev_p;
4387 prev_p = &(*prev_p)->next, seg = *prev_p)
4389 if (seg->type->cleanupFunc != NULL)
4391 *prev_p = (*seg->type->cleanupFunc)(seg, line);
4404 node_data_new (gpointer view_id)
4408 nd = g_new (NodeData, 1);
4410 nd->view_id = view_id;
4420 node_data_destroy (NodeData *nd)
4427 node_data_list_destroy (NodeData *nd)
4433 while (iter != NULL)
4436 node_data_destroy (iter);
4442 node_data_find (NodeData *nd, gpointer view_id)
4446 if (nd->view_id == view_id)
4454 summary_destroy (Summary *summary)
4456 /* Fill with error-triggering garbage */
4457 summary->info = (void*)0x1;
4458 summary->toggle_count = 567;
4459 summary->next = (void*)0x1;
4463 static GtkTextBTreeNode*
4464 gtk_text_btree_node_new (void)
4466 GtkTextBTreeNode *node;
4468 node = g_new (GtkTextBTreeNode, 1);
4470 node->node_data = NULL;
4476 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
4477 GtkTextTagInfo *info,
4482 summary = node->summary;
4483 while (summary != NULL)
4485 if (summary->info == info)
4487 summary->toggle_count += adjust;
4491 summary = summary->next;
4494 if (summary == NULL)
4496 /* didn't find a summary for our tag. */
4497 g_return_if_fail (adjust > 0);
4498 summary = g_new (Summary, 1);
4499 summary->info = info;
4500 summary->toggle_count = adjust;
4501 summary->next = node->summary;
4502 node->summary = summary;
4506 /* Note that the tag root and above do not have summaries
4507 for the tag; only nodes below the tag root have
4510 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4514 summary = node->summary;
4515 while (summary != NULL)
4518 summary->info->tag == tag)
4521 summary = summary->next;
4527 /* Add node and all children to the damage region. */
4529 gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node)
4533 nd = node->node_data;
4540 if (node->level == 0)
4544 line = node->children.line;
4545 while (line != NULL)
4547 GtkTextLineData *ld;
4561 GtkTextBTreeNode *child;
4563 child = node->children.node;
4565 while (child != NULL)
4567 gtk_text_btree_node_invalidate_downward (child);
4569 child = child->next;
4575 gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node, gpointer view_id)
4577 GtkTextBTreeNode *iter;
4580 while (iter != NULL)
4586 nd = node_data_find (iter->node_data, view_id);
4588 if (nd == NULL || !nd->valid)
4589 break; /* Once a node is invalid, we know its parents are as well. */
4595 gboolean should_continue = FALSE;
4597 nd = iter->node_data;
4602 should_continue = TRUE;
4609 if (!should_continue)
4610 break; /* This node was totally invalidated, so are its
4614 iter = iter->parent;
4620 * _gtk_text_btree_is_valid:
4621 * @tree: a #GtkTextBTree
4622 * @view_id: ID for the view
4624 * Check to see if the entire #GtkTextBTree is valid or not for
4627 * Return value: %TRUE if the entire #GtkTextBTree is valid
4630 _gtk_text_btree_is_valid (GtkTextBTree *tree,
4634 g_return_val_if_fail (tree != NULL, FALSE);
4636 nd = node_data_find (tree->root_node->node_data, view_id);
4637 return (nd && nd->valid);
4640 typedef struct _ValidateState ValidateState;
4642 struct _ValidateState
4644 gint remaining_pixels;
4645 gboolean in_validation;
4652 gtk_text_btree_node_validate (BTreeView *view,
4653 GtkTextBTreeNode *node,
4655 ValidateState *state)
4657 gint node_valid = TRUE;
4658 gint node_width = 0;
4659 gint node_height = 0;
4661 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4662 g_return_if_fail (!nd->valid);
4664 if (node->level == 0)
4666 GtkTextLine *line = node->children.line;
4667 GtkTextLineData *ld;
4669 /* Iterate over leading valid lines */
4670 while (line != NULL)
4672 ld = _gtk_text_line_get_data (line, view_id);
4674 if (!ld || !ld->valid)
4676 else if (state->in_validation)
4678 state->in_validation = FALSE;
4683 state->y += ld->height;
4684 node_width = MAX (ld->width, node_width);
4685 node_height += ld->height;
4691 state->in_validation = TRUE;
4693 /* Iterate over invalid lines */
4694 while (line != NULL)
4696 ld = _gtk_text_line_get_data (line, view_id);
4698 if (ld && ld->valid)
4703 state->old_height += ld->height;
4704 ld = gtk_text_layout_wrap (view->layout, line, ld);
4705 state->new_height += ld->height;
4707 node_width = MAX (ld->width, node_width);
4708 node_height += ld->height;
4710 state->remaining_pixels -= ld->height;
4711 if (state->remaining_pixels <= 0)
4721 /* Iterate over the remaining lines */
4722 while (line != NULL)
4724 ld = _gtk_text_line_get_data (line, view_id);
4725 state->in_validation = FALSE;
4727 if (!ld || !ld->valid)
4732 node_width = MAX (ld->width, node_width);
4733 node_height += ld->height;
4741 GtkTextBTreeNode *child;
4744 child = node->children.node;
4746 /* Iterate over leading valid nodes */
4749 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4751 if (!child_nd->valid)
4753 else if (state->in_validation)
4755 state->in_validation = FALSE;
4760 state->y += child_nd->height;
4761 node_width = MAX (node_width, child_nd->width);
4762 node_height += child_nd->height;
4765 child = child->next;
4768 /* Iterate over invalid nodes */
4771 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4773 if (child_nd->valid)
4777 gtk_text_btree_node_validate (view, child, view_id, state);
4779 if (!child_nd->valid)
4781 node_width = MAX (node_width, child_nd->width);
4782 node_height += child_nd->height;
4784 if (!state->in_validation || state->remaining_pixels <= 0)
4786 child = child->next;
4791 child = child->next;
4794 /* Iterate over the remaining lines */
4797 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4798 state->in_validation = FALSE;
4800 if (!child_nd->valid)
4803 node_width = MAX (child_nd->width, node_width);
4804 node_height += child_nd->height;
4806 child = child->next;
4810 nd->width = node_width;
4811 nd->height = node_height;
4812 nd->valid = node_valid;
4816 * _gtk_text_btree_validate:
4817 * @tree: a #GtkTextBTree
4819 * @max_pixels: the maximum number of pixels to validate. (No more
4820 * than one paragraph beyond this limit will be validated)
4821 * @y: location to store starting y coordinate of validated region
4822 * @old_height: location to store old height of validated region
4823 * @new_height: location to store new height of validated region
4825 * Validate a single contiguous invalid region of a #GtkTextBTree for
4828 * Return value: %TRUE if a region has been validated, %FALSE if the
4829 * entire tree was already valid.
4832 _gtk_text_btree_validate (GtkTextBTree *tree,
4841 g_return_val_if_fail (tree != NULL, FALSE);
4843 view = gtk_text_btree_get_view (tree, view_id);
4844 g_return_val_if_fail (view != NULL, FALSE);
4846 if (!_gtk_text_btree_is_valid (tree, view_id))
4848 ValidateState state;
4850 state.remaining_pixels = max_pixels;
4851 state.in_validation = FALSE;
4853 state.old_height = 0;
4854 state.new_height = 0;
4856 gtk_text_btree_node_validate (view,
4863 *old_height = state.old_height;
4865 *new_height = state.new_height;
4867 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4868 _gtk_text_btree_check (tree);
4877 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
4881 gboolean *valid_out)
4885 gboolean valid = TRUE;
4887 if (node->level == 0)
4889 GtkTextLine *line = node->children.line;
4891 while (line != NULL)
4893 GtkTextLineData *ld = _gtk_text_line_get_data (line, view_id);
4895 if (!ld || !ld->valid)
4900 width = MAX (ld->width, width);
4901 height += ld->height;
4909 GtkTextBTreeNode *child = node->children.node;
4913 NodeData *child_nd = node_data_find (child->node_data, view_id);
4915 if (!child_nd || !child_nd->valid)
4920 width = MAX (child_nd->width, width);
4921 height += child_nd->height;
4924 child = child->next;
4929 *height_out = height;
4934 /* Recompute the validity and size of the view data for a given
4935 * view at this node from the immediate children of the node
4938 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
4941 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4946 gtk_text_btree_node_compute_view_aggregates (node, view_id,
4947 &width, &height, &valid);
4949 nd->height = height;
4956 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
4961 gtk_text_btree_node_check_valid (node, view_id);
4962 node = node->parent;
4967 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
4970 if (node->level == 0)
4972 return gtk_text_btree_node_check_valid (node, view_id);
4976 GtkTextBTreeNode *child = node->children.node;
4978 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4986 NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
4988 if (!child_nd->valid)
4990 nd->width = MAX (child_nd->width, nd->width);
4991 nd->height += child_nd->height;
4993 child = child->next;
5002 * _gtk_text_btree_validate_line:
5003 * @tree: a #GtkTextBTree
5004 * @line: line to validate
5005 * @view_id: view ID for the view to validate
5007 * Revalidate a single line of the btree for the given view, propagate
5008 * results up through the entire tree.
5011 _gtk_text_btree_validate_line (GtkTextBTree *tree,
5015 GtkTextLineData *ld;
5018 g_return_if_fail (tree != NULL);
5019 g_return_if_fail (line != NULL);
5021 view = gtk_text_btree_get_view (tree, view_id);
5022 g_return_if_fail (view != NULL);
5024 ld = _gtk_text_line_get_data (line, view_id);
5025 if (!ld || !ld->valid)
5027 ld = gtk_text_layout_wrap (view->layout, line, ld);
5029 gtk_text_btree_node_check_valid_upward (line->parent, view_id);
5034 gtk_text_btree_node_remove_view (BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
5036 if (node->level == 0)
5040 line = node->children.line;
5041 while (line != NULL)
5043 GtkTextLineData *ld;
5045 ld = _gtk_text_line_remove_data (line, view_id);
5048 gtk_text_layout_free_line_data (view->layout, line, ld);
5055 GtkTextBTreeNode *child;
5057 child = node->children.node;
5059 while (child != NULL)
5062 gtk_text_btree_node_remove_view (view, child, view_id);
5064 child = child->next;
5068 gtk_text_btree_node_remove_data (node, view_id);
5072 gtk_text_btree_node_destroy (GtkTextBTree *tree, GtkTextBTreeNode *node)
5074 if (node->level == 0)
5077 GtkTextLineSegment *seg;
5079 while (node->children.line != NULL)
5081 line = node->children.line;
5082 node->children.line = line->next;
5083 while (line->segments != NULL)
5085 seg = line->segments;
5086 line->segments = seg->next;
5088 if (GTK_IS_TEXT_MARK_SEGMENT (seg))
5090 /* Set the mark as deleted */
5091 seg->body.mark.tree = NULL;
5092 seg->body.mark.line = NULL;
5095 (*seg->type->deleteFunc) (seg, line, 1);
5097 gtk_text_line_destroy (tree, line);
5102 GtkTextBTreeNode *childPtr;
5104 while (node->children.node != NULL)
5106 childPtr = node->children.node;
5107 node->children.node = childPtr->next;
5108 gtk_text_btree_node_destroy (tree, childPtr);
5112 summary_list_destroy (node->summary);
5113 node_data_list_destroy (node->node_data);
5118 gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node, gpointer view_id)
5122 nd = node->node_data;
5125 if (nd->view_id == view_id)
5132 nd = node_data_new (view_id);
5134 if (node->node_data)
5135 nd->next = node->node_data;
5137 node->node_data = nd;
5144 gtk_text_btree_node_remove_data (GtkTextBTreeNode *node, gpointer view_id)
5150 nd = node->node_data;
5153 if (nd->view_id == view_id)
5164 prev->next = nd->next;
5166 if (node->node_data == nd)
5167 node->node_data = nd->next;
5171 node_data_destroy (nd);
5175 gtk_text_btree_node_get_size (GtkTextBTreeNode *node, gpointer view_id,
5176 gint *width, gint *height)
5180 g_return_if_fail (width != NULL);
5181 g_return_if_fail (height != NULL);
5183 nd = gtk_text_btree_node_ensure_data (node, view_id);
5188 *height = nd->height;
5191 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5192 * here isn't quite right, since for a lot of operations we want to
5193 * know which children of the common parent correspond to the two nodes
5194 * (e.g., when computing the order of two iters)
5196 static GtkTextBTreeNode *
5197 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5198 GtkTextBTreeNode *node2)
5200 while (node1->level < node2->level)
5201 node1 = node1->parent;
5202 while (node2->level < node1->level)
5203 node2 = node2->parent;
5204 while (node1 != node2)
5206 node1 = node1->parent;
5207 node2 = node2->parent;
5218 gtk_text_btree_get_view (GtkTextBTree *tree, gpointer view_id)
5223 while (view != NULL)
5225 if (view->view_id == view_id)
5234 get_tree_bounds (GtkTextBTree *tree,
5238 _gtk_text_btree_get_iter_at_line_char (tree, start, 0, 0);
5239 _gtk_text_btree_get_last_iter (tree, end);
5243 tag_changed_cb (GtkTextTagTable *table,
5245 gboolean size_changed,
5250 /* We need to queue a relayout on all regions that are tagged with
5257 if (_gtk_text_btree_get_iter_at_first_toggle (tree, &start, tag))
5259 /* Must be a last toggle if there was a first one. */
5260 _gtk_text_btree_get_iter_at_last_toggle (tree, &end, tag);
5261 _gtk_text_btree_invalidate_region (tree,
5268 /* We only need to queue a redraw, not a relayout */
5273 while (view != NULL)
5277 _gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5278 gtk_text_layout_changed (view->layout, 0, height, height);
5286 tag_removed_cb (GtkTextTagTable *table,
5290 /* Remove the tag from the tree */
5295 get_tree_bounds (tree, &start, &end);
5297 _gtk_text_btree_tag (&start, &end, tag, FALSE);
5298 gtk_text_btree_remove_tag_info (tree, tag);
5302 /* Rebalance the out-of-whack node "node" */
5304 gtk_text_btree_rebalance (GtkTextBTree *tree,
5305 GtkTextBTreeNode *node)
5308 * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5309 * up through the tree one GtkTextBTreeNode at a time until the root
5310 * GtkTextBTreeNode has been processed.
5313 while (node != NULL)
5315 GtkTextBTreeNode *new_node, *child;
5320 * Check to see if the GtkTextBTreeNode has too many children. If it does,
5321 * then split off all but the first MIN_CHILDREN into a separate
5322 * GtkTextBTreeNode following the original one. Then repeat until the
5323 * GtkTextBTreeNode has a decent size.
5326 if (node->num_children > MAX_CHILDREN)
5331 * If the GtkTextBTreeNode being split is the root
5332 * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5336 if (node->parent == NULL)
5338 new_node = gtk_text_btree_node_new ();
5339 new_node->parent = NULL;
5340 new_node->next = NULL;
5341 new_node->summary = NULL;
5342 new_node->level = node->level + 1;
5343 new_node->children.node = node;
5344 recompute_node_counts (tree, new_node);
5345 tree->root_node = new_node;
5347 new_node = gtk_text_btree_node_new ();
5348 new_node->parent = node->parent;
5349 new_node->next = node->next;
5350 node->next = new_node;
5351 new_node->summary = NULL;
5352 new_node->level = node->level;
5353 new_node->num_children = node->num_children - MIN_CHILDREN;
5354 if (node->level == 0)
5356 for (i = MIN_CHILDREN-1,
5357 line = node->children.line;
5358 i > 0; i--, line = line->next)
5360 /* Empty loop body. */
5362 new_node->children.line = line->next;
5367 for (i = MIN_CHILDREN-1,
5368 child = node->children.node;
5369 i > 0; i--, child = child->next)
5371 /* Empty loop body. */
5373 new_node->children.node = child->next;
5376 recompute_node_counts (tree, node);
5377 node->parent->num_children++;
5379 if (node->num_children <= MAX_CHILDREN)
5381 recompute_node_counts (tree, node);
5387 while (node->num_children < MIN_CHILDREN)
5389 GtkTextBTreeNode *other;
5390 GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5391 GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5392 int total_children, first_children, i;
5395 * Too few children for this GtkTextBTreeNode. If this is the root then,
5396 * it's OK for it to have less than MIN_CHILDREN children
5397 * as long as it's got at least two. If it has only one
5398 * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5399 * the tree and use its child as the new root.
5402 if (node->parent == NULL)
5404 if ((node->num_children == 1) && (node->level > 0))
5406 tree->root_node = node->children.node;
5407 tree->root_node->parent = NULL;
5408 summary_list_destroy (node->summary);
5415 * Not the root. Make sure that there are siblings to
5419 if (node->parent->num_children < 2)
5421 gtk_text_btree_rebalance (tree, node->parent);
5426 * Find a sibling neighbor to borrow from, and arrange for
5427 * node to be the earlier of the pair.
5430 if (node->next == NULL)
5432 for (other = node->parent->children.node;
5433 other->next != node;
5434 other = other->next)
5436 /* Empty loop body. */
5443 * We're going to either merge the two siblings together
5444 * into one GtkTextBTreeNode or redivide the children among them to
5445 * balance their loads. As preparation, join their two
5446 * child lists into a single list and remember the half-way
5447 * point in the list.
5450 total_children = node->num_children + other->num_children;
5451 first_children = total_children/2;
5452 if (node->children.node == NULL)
5454 node->children = other->children;
5455 other->children.node = NULL;
5456 other->children.line = NULL;
5458 if (node->level == 0)
5462 for (line = node->children.line, i = 1;
5464 line = line->next, i++)
5466 if (i == first_children)
5471 line->next = other->children.line;
5472 while (i <= first_children)
5481 GtkTextBTreeNode *child;
5483 for (child = node->children.node, i = 1;
5484 child->next != NULL;
5485 child = child->next, i++)
5487 if (i <= first_children)
5489 if (i == first_children)
5491 halfwaynode = child;
5495 child->next = other->children.node;
5496 while (i <= first_children)
5498 halfwaynode = child;
5499 child = child->next;
5505 * If the two siblings can simply be merged together, do it.
5508 if (total_children <= MAX_CHILDREN)
5510 recompute_node_counts (tree, node);
5511 node->next = other->next;
5512 node->parent->num_children--;
5513 summary_list_destroy (other->summary);
5519 * The siblings can't be merged, so just divide their
5520 * children evenly between them.
5523 if (node->level == 0)
5525 other->children.line = halfwayline->next;
5526 halfwayline->next = NULL;
5530 other->children.node = halfwaynode->next;
5531 halfwaynode->next = NULL;
5534 recompute_node_counts (tree, node);
5535 recompute_node_counts (tree, other);
5538 node = node->parent;
5543 post_insert_fixup (GtkTextBTree *tree,
5545 gint line_count_delta,
5546 gint char_count_delta)
5549 GtkTextBTreeNode *node;
5552 * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5553 * point, then rebalance the tree if necessary.
5556 for (node = line->parent ; node != NULL;
5557 node = node->parent)
5559 node->num_lines += line_count_delta;
5560 node->num_chars += char_count_delta;
5562 node = line->parent;
5563 node->num_children += line_count_delta;
5565 if (node->num_children > MAX_CHILDREN)
5567 gtk_text_btree_rebalance (tree, node);
5570 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5571 _gtk_text_btree_check (tree);
5574 static GtkTextTagInfo*
5575 gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
5578 GtkTextTagInfo *info;
5582 list = tree->tag_infos;
5583 while (list != NULL)
5586 if (info->tag == tag)
5589 list = g_slist_next (list);
5595 static GtkTextTagInfo*
5596 gtk_text_btree_get_tag_info (GtkTextBTree *tree,
5599 GtkTextTagInfo *info;
5601 info = gtk_text_btree_get_existing_tag_info (tree, tag);
5605 /* didn't find it, create. */
5607 info = g_new (GtkTextTagInfo, 1);
5610 gtk_object_ref (GTK_OBJECT (tag));
5611 info->tag_root = NULL;
5612 info->toggle_count = 0;
5614 tree->tag_infos = g_slist_prepend (tree->tag_infos, info);
5621 gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
5624 GtkTextTagInfo *info;
5629 list = tree->tag_infos;
5630 while (list != NULL)
5633 if (info->tag == tag)
5637 prev->next = list->next;
5641 tree->tag_infos = list->next;
5644 g_slist_free (list);
5646 gtk_object_unref (GTK_OBJECT (info->tag));
5652 list = g_slist_next (list);
5655 g_assert_not_reached ();
5660 recompute_level_zero_counts (GtkTextBTreeNode *node)
5663 GtkTextLineSegment *seg;
5665 g_assert (node->level == 0);
5667 line = node->children.line;
5668 while (line != NULL)
5670 node->num_children++;
5673 if (line->parent != node)
5674 gtk_text_line_set_parent (line, node);
5676 seg = line->segments;
5680 node->num_chars += seg->char_count;
5682 if (((seg->type != >k_text_toggle_on_type)
5683 && (seg->type != >k_text_toggle_off_type))
5684 || !(seg->body.toggle.inNodeCounts))
5690 GtkTextTagInfo *info;
5692 info = seg->body.toggle.info;
5694 gtk_text_btree_node_adjust_toggle_count (node, info, 1);
5705 recompute_level_nonzero_counts (GtkTextBTreeNode *node)
5708 GtkTextBTreeNode *child;
5710 g_assert (node->level > 0);
5712 child = node->children.node;
5713 while (child != NULL)
5715 node->num_children += 1;
5716 node->num_lines += child->num_lines;
5717 node->num_chars += child->num_chars;
5719 if (child->parent != node)
5721 child->parent = node;
5722 gtk_text_btree_node_invalidate_upward (node, NULL);
5725 summary = child->summary;
5726 while (summary != NULL)
5728 gtk_text_btree_node_adjust_toggle_count (node,
5730 summary->toggle_count);
5732 summary = summary->next;
5735 child = child->next;
5740 *----------------------------------------------------------------------
5742 * recompute_node_counts --
5744 * This procedure is called to recompute all the counts in a GtkTextBTreeNode
5745 * (tags, child information, etc.) by scanning the information in
5746 * its descendants. This procedure is called during rebalancing
5747 * when a GtkTextBTreeNode's child structure has changed.
5753 * The tag counts for node are modified to reflect its current
5754 * child structure, as are its num_children, num_lines, num_chars fields.
5755 * Also, all of the childrens' parent fields are made to point
5758 *----------------------------------------------------------------------
5762 recompute_node_counts (GtkTextBTree *tree, GtkTextBTreeNode *node)
5765 Summary *summary, *summary2;
5768 * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
5769 * the existing Summary records (most of them will probably be reused).
5772 summary = node->summary;
5773 while (summary != NULL)
5775 summary->toggle_count = 0;
5776 summary = summary->next;
5779 node->num_children = 0;
5780 node->num_lines = 0;
5781 node->num_chars = 0;
5784 * Scan through the children, adding the childrens' tag counts into
5785 * the GtkTextBTreeNode's tag counts and adding new Summary structures if
5789 if (node->level == 0)
5790 recompute_level_zero_counts (node);
5792 recompute_level_nonzero_counts (node);
5797 gtk_text_btree_node_check_valid (node, view->view_id);
5802 * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
5803 * records that still have a zero count, or that have all the toggles.
5804 * The GtkTextBTreeNode with the children that account for all the tags toggles
5805 * have no summary information, and they become the tag_root for the tag.
5809 for (summary = node->summary; summary != NULL; )
5811 if (summary->toggle_count > 0 &&
5812 summary->toggle_count < summary->info->toggle_count)
5814 if (node->level == summary->info->tag_root->level)
5817 * The tag's root GtkTextBTreeNode split and some toggles left.
5818 * The tag root must move up a level.
5820 summary->info->tag_root = node->parent;
5823 summary = summary->next;
5826 if (summary->toggle_count == summary->info->toggle_count)
5829 * A GtkTextBTreeNode merge has collected all the toggles under
5830 * one GtkTextBTreeNode. Push the root down to this level.
5832 summary->info->tag_root = node;
5834 if (summary2 != NULL)
5836 summary2->next = summary->next;
5837 summary_destroy (summary);
5838 summary = summary2->next;
5842 node->summary = summary->next;
5843 summary_destroy (summary);
5844 summary = node->summary;
5850 _gtk_change_node_toggle_count (GtkTextBTreeNode *node,
5851 GtkTextTagInfo *info,
5852 gint delta) /* may be negative */
5854 Summary *summary, *prevPtr;
5855 GtkTextBTreeNode *node2Ptr;
5856 int rootLevel; /* Level of original tag root */
5858 info->toggle_count += delta;
5860 if (info->tag_root == (GtkTextBTreeNode *) NULL)
5862 info->tag_root = node;
5867 * Note the level of the existing root for the tag so we can detect
5868 * if it needs to be moved because of the toggle count change.
5871 rootLevel = info->tag_root->level;
5874 * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
5875 * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
5879 for ( ; node != info->tag_root; node = node->parent)
5882 * See if there's already an entry for this tag for this GtkTextBTreeNode. If so,
5883 * perhaps all we have to do is adjust its count.
5886 for (prevPtr = NULL, summary = node->summary;
5888 prevPtr = summary, summary = summary->next)
5890 if (summary->info == info)
5895 if (summary != NULL)
5897 summary->toggle_count += delta;
5898 if (summary->toggle_count > 0 &&
5899 summary->toggle_count < info->toggle_count)
5903 if (summary->toggle_count != 0)
5906 * Should never find a GtkTextBTreeNode with max toggle count at this
5907 * point (there shouldn't have been a summary entry in the
5911 g_error ("%s: bad toggle count (%d) max (%d)",
5912 G_STRLOC, summary->toggle_count, info->toggle_count);
5916 * Zero toggle count; must remove this tag from the list.
5919 if (prevPtr == NULL)
5921 node->summary = summary->next;
5925 prevPtr->next = summary->next;
5927 summary_destroy (summary);
5932 * This tag isn't currently in the summary information list.
5935 if (rootLevel == node->level)
5939 * The old tag root is at the same level in the tree as this
5940 * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode. Move the tag root up
5941 * a level, in the hopes that it will now cover this GtkTextBTreeNode
5942 * as well as the old root (if not, we'll move it up again
5943 * the next time through the loop). To push it up one level
5944 * we copy the original toggle count into the summary
5945 * information at the old root and change the root to its
5946 * parent GtkTextBTreeNode.
5949 GtkTextBTreeNode *rootnode = info->tag_root;
5950 summary = (Summary *) g_malloc (sizeof (Summary));
5951 summary->info = info;
5952 summary->toggle_count = info->toggle_count - delta;
5953 summary->next = rootnode->summary;
5954 rootnode->summary = summary;
5955 rootnode = rootnode->parent;
5956 rootLevel = rootnode->level;
5957 info->tag_root = rootnode;
5959 summary = (Summary *) g_malloc (sizeof (Summary));
5960 summary->info = info;
5961 summary->toggle_count = delta;
5962 summary->next = node->summary;
5963 node->summary = summary;
5968 * If we've decremented the toggle count, then it may be necessary
5969 * to push the tag root down one or more levels.
5976 if (info->toggle_count == 0)
5978 info->tag_root = (GtkTextBTreeNode *) NULL;
5981 node = info->tag_root;
5982 while (node->level > 0)
5985 * See if a single child GtkTextBTreeNode accounts for all of the tag's
5986 * toggles. If so, push the root down one level.
5989 for (node2Ptr = node->children.node;
5990 node2Ptr != (GtkTextBTreeNode *)NULL ;
5991 node2Ptr = node2Ptr->next)
5993 for (prevPtr = NULL, summary = node2Ptr->summary;
5995 prevPtr = summary, summary = summary->next)
5997 if (summary->info == info)
6002 if (summary == NULL)
6006 if (summary->toggle_count != info->toggle_count)
6009 * No GtkTextBTreeNode has all toggles, so the root is still valid.
6016 * This GtkTextBTreeNode has all the toggles, so push down the root.
6019 if (prevPtr == NULL)
6021 node2Ptr->summary = summary->next;
6025 prevPtr->next = summary->next;
6027 summary_destroy (summary);
6028 info->tag_root = node2Ptr;
6031 node = info->tag_root;
6036 *----------------------------------------------------------------------
6040 * This is a utility procedure used by _gtk_text_btree_get_tags. It
6041 * increments the count for a particular tag, adding a new
6042 * entry for that tag if there wasn't one previously.
6048 * The information at *tagInfoPtr may be modified, and the arrays
6049 * may be reallocated to make them larger.
6051 *----------------------------------------------------------------------
6055 inc_count (GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
6060 for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
6061 count > 0; tag_p++, count--)
6065 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
6071 * There isn't currently an entry for this tag, so we have to
6072 * make a new one. If the arrays are full, then enlarge the
6076 if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
6078 GtkTextTag **newTags;
6079 int *newCounts, newSize;
6081 newSize = 2*tagInfoPtr->arraySize;
6082 newTags = (GtkTextTag **) g_malloc ((unsigned)
6083 (newSize*sizeof (GtkTextTag *)));
6084 memcpy ((void *) newTags, (void *) tagInfoPtr->tags,
6085 tagInfoPtr->arraySize *sizeof (GtkTextTag *));
6086 g_free ((char *) tagInfoPtr->tags);
6087 tagInfoPtr->tags = newTags;
6088 newCounts = (int *) g_malloc ((unsigned) (newSize*sizeof (int)));
6089 memcpy ((void *) newCounts, (void *) tagInfoPtr->counts,
6090 tagInfoPtr->arraySize *sizeof (int));
6091 g_free ((char *) tagInfoPtr->counts);
6092 tagInfoPtr->counts = newCounts;
6093 tagInfoPtr->arraySize = newSize;
6096 tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
6097 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
6098 tagInfoPtr->numTags++;
6102 gtk_text_btree_link_segment (GtkTextLineSegment *seg,
6103 const GtkTextIter *iter)
6105 GtkTextLineSegment *prev;
6109 line = gtk_text_iter_get_text_line (iter);
6110 tree = gtk_text_iter_get_btree (iter);
6112 prev = gtk_text_line_segment_split (iter);
6115 seg->next = line->segments;
6116 line->segments = seg;
6120 seg->next = prev->next;
6123 cleanup_line (line);
6124 segments_changed (tree);
6126 if (gtk_debug_flags & GTK_DEBUG_TEXT)
6127 _gtk_text_btree_check (tree);
6131 gtk_text_btree_unlink_segment (GtkTextBTree *tree,
6132 GtkTextLineSegment *seg,
6135 GtkTextLineSegment *prev;
6137 if (line->segments == seg)
6139 line->segments = seg->next;
6143 for (prev = line->segments; prev->next != seg;
6146 /* Empty loop body. */
6148 prev->next = seg->next;
6150 cleanup_line (line);
6151 segments_changed (tree);
6155 * This is here because it requires BTree internals, it logically
6156 * belongs in gtktextsegment.c
6161 *--------------------------------------------------------------
6163 * _gtk_toggle_segment_check_func --
6165 * This procedure is invoked to perform consistency checks
6166 * on toggle segments.
6172 * If a consistency problem is found the procedure g_errors.
6174 *--------------------------------------------------------------
6178 _gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6184 if (segPtr->byte_count != 0)
6186 g_error ("toggle_segment_check_func: segment had non-zero size");
6188 if (!segPtr->body.toggle.inNodeCounts)
6190 g_error ("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6192 needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6193 for (summary = line->parent->summary; ;
6194 summary = summary->next)
6196 if (summary == NULL)
6200 g_error ("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6207 if (summary->info == segPtr->body.toggle.info)
6211 g_error ("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6223 gtk_text_btree_node_view_check_consistency (GtkTextBTreeNode *node,
6230 gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6231 &width, &height, &valid);
6232 if (nd->width != width ||
6233 nd->height != height ||
6234 !nd->valid != !valid)
6236 g_error ("Node aggregates for view %p are invalid:\n"
6237 "Are (%d,%d,%s), should be (%d,%d,%s)",
6239 nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6240 width, height, valid ? "TRUE" : "FALSE");
6245 gtk_text_btree_node_check_consistency (GtkTextBTreeNode *node)
6247 GtkTextBTreeNode *childnode;
6248 Summary *summary, *summary2;
6250 GtkTextLineSegment *segPtr;
6251 int num_children, num_lines, num_chars, toggle_count, min_children;
6252 GtkTextLineData *ld;
6255 if (node->parent != NULL)
6257 min_children = MIN_CHILDREN;
6259 else if (node->level > 0)
6266 if ((node->num_children < min_children)
6267 || (node->num_children > MAX_CHILDREN))
6269 g_error ("gtk_text_btree_node_check_consistency: bad child count (%d)",
6270 node->num_children);
6273 nd = node->node_data;
6276 gtk_text_btree_node_view_check_consistency (node, nd);
6283 if (node->level == 0)
6285 for (line = node->children.line; line != NULL;
6288 if (line->parent != node)
6290 g_error ("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6292 if (line->segments == NULL)
6294 g_error ("gtk_text_btree_node_check_consistency: line has no segments");
6300 /* Just ensuring we don't segv while doing this loop */
6305 for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6307 if (segPtr->type->checkFunc != NULL)
6309 (*segPtr->type->checkFunc)(segPtr, line);
6311 if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6312 && (segPtr->next != NULL)
6313 && (segPtr->next->byte_count == 0)
6314 && (segPtr->next->type->leftGravity))
6316 g_error ("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6318 if ((segPtr->next == NULL)
6319 && (segPtr->type != >k_text_char_type))
6321 g_error ("gtk_text_btree_node_check_consistency: line ended with wrong type");
6324 num_chars += segPtr->char_count;
6333 for (childnode = node->children.node; childnode != NULL;
6334 childnode = childnode->next)
6336 if (childnode->parent != node)
6338 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6340 if (childnode->level != (node->level-1))
6342 g_error ("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6343 node->level, childnode->level);
6345 gtk_text_btree_node_check_consistency (childnode);
6346 for (summary = childnode->summary; summary != NULL;
6347 summary = summary->next)
6349 for (summary2 = node->summary; ;
6350 summary2 = summary2->next)
6352 if (summary2 == NULL)
6354 if (summary->info->tag_root == node)
6358 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6359 summary->info->tag->name,
6360 "present in parent summaries");
6362 if (summary->info == summary2->info)
6369 num_lines += childnode->num_lines;
6370 num_chars += childnode->num_chars;
6373 if (num_children != node->num_children)
6375 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6376 num_children, node->num_children);
6378 if (num_lines != node->num_lines)
6380 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6381 num_lines, node->num_lines);
6383 if (num_chars != node->num_chars)
6385 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6386 num_chars, node->num_chars);
6389 for (summary = node->summary; summary != NULL;
6390 summary = summary->next)
6392 if (summary->info->toggle_count == summary->toggle_count)
6394 g_error ("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6395 summary->info->tag->name);
6398 if (node->level == 0)
6400 for (line = node->children.line; line != NULL;
6403 for (segPtr = line->segments; segPtr != NULL;
6404 segPtr = segPtr->next)
6406 if ((segPtr->type != >k_text_toggle_on_type)
6407 && (segPtr->type != >k_text_toggle_off_type))
6411 if (segPtr->body.toggle.info == summary->info)
6413 if (!segPtr->body.toggle.inNodeCounts)
6414 g_error ("Toggle segment not in the node counts");
6423 for (childnode = node->children.node;
6425 childnode = childnode->next)
6427 for (summary2 = childnode->summary;
6429 summary2 = summary2->next)
6431 if (summary2->info == summary->info)
6433 toggle_count += summary2->toggle_count;
6438 if (toggle_count != summary->toggle_count)
6440 g_error ("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6441 toggle_count, summary->toggle_count);
6443 for (summary2 = summary->next; summary2 != NULL;
6444 summary2 = summary2->next)
6446 if (summary2->info == summary->info)
6448 g_error ("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6449 summary->info->tag->name);
6456 listify_foreach (GtkTextTag *tag, gpointer user_data)
6458 GSList** listp = user_data;
6460 *listp = g_slist_prepend (*listp, tag);
6464 list_of_tags (GtkTextTagTable *table)
6466 GSList *list = NULL;
6468 gtk_text_tag_table_foreach (table, listify_foreach, &list);
6474 _gtk_text_btree_check (GtkTextBTree *tree)
6477 GtkTextBTreeNode *node;
6479 GtkTextLineSegment *seg;
6481 GSList *taglist = NULL;
6483 GtkTextTagInfo *info;
6486 * Make sure that the tag toggle counts and the tag root pointers are OK.
6488 for (taglist = list_of_tags (tree->table);
6489 taglist != NULL ; taglist = taglist->next)
6491 tag = taglist->data;
6492 info = gtk_text_btree_get_existing_tag_info (tree, tag);
6495 node = info->tag_root;
6498 if (info->toggle_count != 0)
6500 g_error ("_gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6501 tag->name, info->toggle_count);
6503 continue; /* no ranges for the tag */
6505 else if (info->toggle_count == 0)
6507 g_error ("_gtk_text_btree_check found root for \"%s\" with no toggles",
6510 else if (info->toggle_count & 1)
6512 g_error ("_gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6513 tag->name, info->toggle_count);
6515 for (summary = node->summary; summary != NULL;
6516 summary = summary->next)
6518 if (summary->info->tag == tag)
6520 g_error ("_gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6524 if (node->level > 0)
6526 for (node = node->children.node ; node != NULL ;
6529 for (summary = node->summary; summary != NULL;
6530 summary = summary->next)
6532 if (summary->info->tag == tag)
6534 count += summary->toggle_count;
6541 GtkTextLineSegmentClass * last = NULL;
6543 for (line = node->children.line ; line != NULL ;
6546 for (seg = line->segments; seg != NULL;
6549 if ((seg->type == >k_text_toggle_on_type ||
6550 seg->type == >k_text_toggle_off_type) &&
6551 seg->body.toggle.info->tag == tag)
6553 if (last == seg->type)
6554 g_error ("Two consecutive toggles on or off weren't merged");
6555 if (!seg->body.toggle.inNodeCounts)
6556 g_error ("Toggle segment not in the node counts");
6565 if (count != info->toggle_count)
6567 g_error ("_gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
6568 info->toggle_count, tag->name, count);
6573 g_slist_free (taglist);
6577 * Call a recursive procedure to do the main body of checks.
6580 node = tree->root_node;
6581 gtk_text_btree_node_check_consistency (tree->root_node);
6584 * Make sure that there are at least two lines in the text and
6585 * that the last line has no characters except a newline.
6588 if (node->num_lines < 2)
6590 g_error ("_gtk_text_btree_check: less than 2 lines in tree");
6592 if (node->num_chars < 2)
6594 g_error ("_gtk_text_btree_check: less than 2 chars in tree");
6596 while (node->level > 0)
6598 node = node->children.node;
6599 while (node->next != NULL)
6604 line = node->children.line;
6605 while (line->next != NULL)
6609 seg = line->segments;
6610 while ((seg->type == >k_text_toggle_off_type)
6611 || (seg->type == >k_text_right_mark_type)
6612 || (seg->type == >k_text_left_mark_type))
6615 * It's OK to toggle a tag off in the last line, but
6616 * not to start a new range. It's also OK to have marks
6622 if (seg->type != >k_text_char_type)
6624 g_error ("_gtk_text_btree_check: last line has bogus segment type");
6626 if (seg->next != NULL)
6628 g_error ("_gtk_text_btree_check: last line has too many segments");
6630 if (seg->byte_count != 1)
6632 g_error ("_gtk_text_btree_check: last line has wrong # characters: %d",
6635 if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
6637 g_error ("_gtk_text_btree_check: last line had bad value: %s",
6642 void _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line);
6643 void _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment* seg);
6644 void _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent);
6645 void _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
6648 _gtk_text_btree_spew (GtkTextBTree *tree)
6653 printf ("%d lines in tree %p\n",
6654 _gtk_text_btree_line_count (tree), tree);
6656 line = _gtk_text_btree_get_line (tree, 0, &real_line);
6658 while (line != NULL)
6660 _gtk_text_btree_spew_line (tree, line);
6661 line = _gtk_text_line_next (line);
6664 printf ("=================== Tag information\n");
6669 list = tree->tag_infos;
6671 while (list != NULL)
6673 GtkTextTagInfo *info;
6677 printf (" tag `%s': root at %p, toggle count %d\n",
6678 info->tag->name, info->tag_root, info->toggle_count);
6680 list = g_slist_next (list);
6683 if (tree->tag_infos == NULL)
6685 printf (" (no tags in the tree)\n");
6689 printf ("=================== Tree nodes\n");
6692 _gtk_text_btree_spew_node (tree->root_node, 0);
6697 _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
6700 GtkTextLineSegment *seg;
6702 spaces = g_strnfill (indent, ' ');
6704 printf ("%sline %p chars %d bytes %d\n",
6706 _gtk_text_line_char_count (line),
6707 _gtk_text_line_byte_count (line));
6709 seg = line->segments;
6712 if (seg->type == >k_text_char_type)
6714 gchar* str = g_strndup (seg->body.chars, MIN (seg->byte_count, 10));
6719 if (*s == '\n' || *s == '\r')
6723 printf ("%s chars `%s'...\n", spaces, str);
6726 else if (seg->type == >k_text_right_mark_type)
6728 printf ("%s right mark `%s' visible: %d\n",
6730 seg->body.mark.name,
6731 seg->body.mark.visible);
6733 else if (seg->type == >k_text_left_mark_type)
6735 printf ("%s left mark `%s' visible: %d\n",
6737 seg->body.mark.name,
6738 seg->body.mark.visible);
6740 else if (seg->type == >k_text_toggle_on_type ||
6741 seg->type == >k_text_toggle_off_type)
6743 printf ("%s tag `%s' %s\n",
6744 spaces, seg->body.toggle.info->tag->name,
6745 seg->type == >k_text_toggle_off_type ? "off" : "on");
6755 _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent)
6758 GtkTextBTreeNode *iter;
6761 spaces = g_strnfill (indent, ' ');
6763 printf ("%snode %p level %d children %d lines %d chars %d\n",
6764 spaces, node, node->level,
6765 node->num_children, node->num_lines, node->num_chars);
6770 printf ("%s %d toggles of `%s' below this node\n",
6771 spaces, s->toggle_count, s->info->tag->name);
6777 if (node->level > 0)
6779 iter = node->children.node;
6780 while (iter != NULL)
6782 _gtk_text_btree_spew_node (iter, indent + 2);
6789 GtkTextLine *line = node->children.line;
6790 while (line != NULL)
6792 _gtk_text_btree_spew_line_short (line, indent + 2);
6800 _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line)
6802 GtkTextLineSegment * seg;
6804 printf ("%4d| line: %p parent: %p next: %p\n",
6805 _gtk_text_line_get_number (line), line, line->parent, line->next);
6807 seg = line->segments;
6811 _gtk_text_btree_spew_segment (tree, seg);
6817 _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment * seg)
6819 printf (" segment: %p type: %s bytes: %d chars: %d\n",
6820 seg, seg->type->name, seg->byte_count, seg->char_count);
6822 if (seg->type == >k_text_char_type)
6824 gchar* str = g_strndup (seg->body.chars, seg->byte_count);
6825 printf (" `%s'\n", str);
6828 else if (seg->type == >k_text_right_mark_type)
6830 printf (" right mark `%s' visible: %d not_deleteable: %d\n",
6831 seg->body.mark.name,
6832 seg->body.mark.visible,
6833 seg->body.mark.not_deleteable);
6835 else if (seg->type == >k_text_left_mark_type)
6837 printf (" left mark `%s' visible: %d not_deleteable: %d\n",
6838 seg->body.mark.name,
6839 seg->body.mark.visible,
6840 seg->body.mark.not_deleteable);
6842 else if (seg->type == >k_text_toggle_on_type ||
6843 seg->type == >k_text_toggle_off_type)
6845 printf (" tag `%s' priority %d\n",
6846 seg->body.toggle.info->tag->name,
6847 seg->body.toggle.info->tag->priority);