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);
963 * Chop the text up into lines and create a new segment for
964 * each line, plus a new line for the leftovers from the
970 line_count_delta = 0;
971 char_count_delta = 0;
974 pango_find_paragraph_boundary (text + sol,
979 /* make these relative to the start of the text */
983 chunk_len = eol - sol;
985 seg = _gtk_char_segment_new (&text[sol], chunk_len);
987 char_count_delta += seg->char_count;
991 seg->next = line->segments;
992 line->segments = seg;
996 seg->next = cur_seg->next;
1001 /* chunk didn't end with a paragraph separator */
1005 * The chunk ended with a newline, so create a new GtkTextLine
1006 * and move the remainder of the old line to it.
1009 newline = gtk_text_line_new ();
1010 gtk_text_line_set_parent (newline, line->parent);
1011 newline->next = line->next;
1012 line->next = newline;
1013 newline->segments = seg->next;
1023 * Cleanup the starting line for the insertion, plus the ending
1024 * line if it's different.
1027 cleanup_line (start_line);
1028 if (line != start_line)
1030 cleanup_line (line);
1033 post_insert_fixup (tree, line, line_count_delta, char_count_delta);
1035 /* Invalidate our region, and reset the iterator the user
1036 passed in to point to the end of the inserted text. */
1042 gtk_text_btree_get_iter_at_line (tree,
1048 /* We could almost certainly be more efficient here
1049 by saving the information from the insertion loop
1051 gtk_text_iter_forward_chars (&end, char_count_delta);
1053 gtk_text_btree_invalidate_region (tree,
1057 /* Convenience for the user */
1063 insert_pixbuf_or_widget_segment (GtkTextIter *iter,
1064 GtkTextLineSegment *seg)
1068 GtkTextLineSegment *prevPtr;
1071 gint start_byte_offset;
1073 line = gtk_text_iter_get_text_line (iter);
1074 tree = gtk_text_iter_get_btree (iter);
1075 start_byte_offset = gtk_text_iter_get_line_index (iter);
1077 prevPtr = gtk_text_line_segment_split (iter);
1078 if (prevPtr == NULL)
1080 seg->next = line->segments;
1081 line->segments = seg;
1085 seg->next = prevPtr->next;
1086 prevPtr->next = seg;
1089 post_insert_fixup (tree, line, 0, seg->char_count);
1091 chars_changed (tree);
1092 segments_changed (tree);
1094 /* reset *iter for the user, and invalidate tree nodes */
1096 gtk_text_btree_get_iter_at_line (tree, &start, line, start_byte_offset);
1099 gtk_text_iter_forward_char (iter); /* skip forward past the segment */
1101 gtk_text_btree_invalidate_region (tree, &start, iter);
1105 gtk_text_btree_insert_pixbuf (GtkTextIter *iter,
1108 GtkTextLineSegment *seg;
1110 seg = _gtk_pixbuf_segment_new (pixbuf);
1112 insert_pixbuf_or_widget_segment (iter, seg);
1116 gtk_text_btree_create_child_anchor (GtkTextIter *iter)
1118 GtkTextLineSegment *seg;
1121 seg = _gtk_widget_segment_new ();
1123 tree = seg->body.child.tree = gtk_text_iter_get_btree (iter);
1125 insert_pixbuf_or_widget_segment (iter, seg);
1127 if (tree->child_anchor_table == NULL)
1128 tree->child_anchor_table = g_hash_table_new (NULL, NULL);
1130 g_hash_table_insert (tree->child_anchor_table,
1131 seg->body.child.obj,
1132 seg->body.child.obj);
1134 return seg->body.child.obj;
1138 gtk_text_btree_unregister_child_anchor (GtkTextChildAnchor *anchor)
1140 GtkTextLineSegment *seg;
1142 seg = anchor->segment;
1144 g_hash_table_remove (seg->body.child.tree->child_anchor_table,
1153 find_line_by_y (GtkTextBTree *tree, BTreeView *view,
1154 GtkTextBTreeNode *node, gint y, gint *line_top,
1155 GtkTextLine *last_line)
1159 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1160 gtk_text_btree_check (tree);
1162 if (node->level == 0)
1166 line = node->children.line;
1168 while (line != NULL && line != last_line)
1170 GtkTextLineData *ld;
1172 ld = gtk_text_line_get_data (line, view->view_id);
1176 if (y < (current_y + (ld ? ld->height : 0)))
1179 current_y += ld->height;
1180 *line_top += ld->height;
1189 GtkTextBTreeNode *child;
1191 child = node->children.node;
1193 while (child != NULL)
1198 gtk_text_btree_node_get_size (child, view->view_id,
1201 if (y < (current_y + height))
1202 return find_line_by_y (tree, view, child,
1203 y - current_y, line_top,
1206 current_y += height;
1207 *line_top += height;
1209 child = child->next;
1217 gtk_text_btree_find_line_by_y (GtkTextBTree *tree,
1224 GtkTextLine *last_line;
1227 view = gtk_text_btree_get_view (tree, view_id);
1228 g_return_val_if_fail (view != NULL, NULL);
1230 last_line = get_last_line (tree);
1232 line = find_line_by_y (tree, view, tree->root_node, ypixel, &line_top,
1236 *line_top_out = line_top;
1242 find_line_top_in_line_list (GtkTextBTree *tree,
1245 GtkTextLine *target_line,
1248 while (line != NULL)
1250 GtkTextLineData *ld;
1252 if (line == target_line)
1255 ld = gtk_text_line_get_data (line, view->view_id);
1262 g_assert_not_reached (); /* If we get here, our
1263 target line didn't exist
1264 under its parent node */
1269 gtk_text_btree_find_line_top (GtkTextBTree *tree,
1270 GtkTextLine *target_line,
1277 GtkTextBTreeNode *node;
1279 view = gtk_text_btree_get_view (tree, view_id);
1281 g_return_val_if_fail (view != NULL, 0);
1284 node = target_line->parent;
1285 while (node != NULL)
1287 nodes = g_slist_prepend (nodes, node);
1288 node = node->parent;
1292 while (iter != NULL)
1296 if (node->level == 0)
1298 g_slist_free (nodes);
1299 return find_line_top_in_line_list (tree, view,
1300 node->children.line,
1305 GtkTextBTreeNode *child;
1306 GtkTextBTreeNode *target_node;
1308 g_assert (iter->next != NULL); /* not at level 0 */
1309 target_node = iter->next->data;
1311 child = node->children.node;
1313 while (child != NULL)
1318 if (child == target_node)
1322 gtk_text_btree_node_get_size (child, view->view_id,
1326 child = child->next;
1328 g_assert (child != NULL); /* should have broken out before we
1332 iter = g_slist_next (iter);
1335 g_assert_not_reached (); /* we return when we find the target line */
1340 gtk_text_btree_add_view (GtkTextBTree *tree,
1341 GtkTextLayout *layout)
1344 GtkTextLine *last_line;
1345 GtkTextLineData *line_data;
1347 g_return_if_fail (tree != NULL);
1349 view = g_new (BTreeView, 1);
1351 view->view_id = layout;
1352 view->layout = layout;
1354 view->next = tree->views;
1359 /* The last line in the buffer has identity values for the per-view
1360 * data so that we can avoid special case checks for it in a large
1363 last_line = get_last_line (tree);
1365 line_data = g_new (GtkTextLineData, 1);
1366 line_data->view_id = layout;
1367 line_data->next = NULL;
1368 line_data->width = 0;
1369 line_data->height = 0;
1370 line_data->valid = TRUE;
1372 gtk_text_line_add_data (last_line, line_data);
1376 gtk_text_btree_remove_view (GtkTextBTree *tree,
1380 GtkTextLine *last_line;
1381 GtkTextLineData *line_data;
1383 g_return_if_fail (tree != NULL);
1387 while (view != NULL)
1389 if (view->view_id == view_id)
1395 g_return_if_fail (view != NULL);
1398 view->next->prev = view->prev;
1401 view->prev->next = view->next;
1403 if (view == tree->views)
1404 tree->views = view->next;
1406 /* Remove the line data for the last line which we added ourselves.
1407 * (Do this first, so that we don't try to call the view's line data destructor on it.)
1409 last_line = get_last_line (tree);
1410 line_data = gtk_text_line_remove_data (last_line, view_id);
1413 gtk_text_btree_node_remove_view (view, tree->root_node, view_id);
1419 gtk_text_btree_invalidate_region (GtkTextBTree *tree,
1420 const GtkTextIter *start,
1421 const GtkTextIter *end)
1427 while (view != NULL)
1429 gtk_text_layout_invalidate (view->layout, start, end);
1436 gtk_text_btree_get_view_size (GtkTextBTree *tree,
1441 g_return_if_fail (tree != NULL);
1442 g_return_if_fail (view_id != NULL);
1444 gtk_text_btree_node_get_size (tree->root_node, view_id,
1459 iter_stack_new (void)
1462 stack = g_new (IterStack, 1);
1463 stack->iters = NULL;
1470 iter_stack_push (IterStack *stack, const GtkTextIter *iter)
1473 if (stack->count > stack->alloced)
1475 stack->alloced = stack->count*2;
1476 stack->iters = g_realloc (stack->iters,
1477 stack->alloced*sizeof (GtkTextIter));
1479 stack->iters[stack->count-1] = *iter;
1483 iter_stack_pop (IterStack *stack, GtkTextIter *iter)
1485 if (stack->count == 0)
1490 *iter = stack->iters[stack->count];
1496 iter_stack_free (IterStack *stack)
1498 g_free (stack->iters);
1503 iter_stack_invert (IterStack *stack)
1505 if (stack->count > 0)
1508 guint j = stack->count - 1;
1513 tmp = stack->iters[i];
1514 stack->iters[i] = stack->iters[j];
1515 stack->iters[j] = tmp;
1524 queue_tag_redisplay (GtkTextBTree *tree,
1526 const GtkTextIter *start,
1527 const GtkTextIter *end)
1529 if (gtk_text_tag_affects_size (tag))
1531 gtk_text_btree_invalidate_region (tree, start, end);
1534 else if (gtk_text_tag_affects_nonsize_appearance (tag))
1536 /* We only need to queue a redraw, not a relayout */
1537 redisplay_region (tree, start, end);
1540 /* We don't need to do anything if the tag doesn't affect display */
1544 gtk_text_btree_tag (const GtkTextIter *start_orig,
1545 const GtkTextIter *end_orig,
1549 GtkTextLineSegment *seg, *prev;
1550 GtkTextLine *cleanupline;
1551 gboolean toggled_on;
1552 GtkTextLine *start_line;
1553 GtkTextLine *end_line;
1555 GtkTextIter start, end;
1558 GtkTextTagInfo *info;
1560 g_return_if_fail (start_orig != NULL);
1561 g_return_if_fail (end_orig != NULL);
1562 g_return_if_fail (GTK_IS_TEXT_TAG (tag));
1563 g_return_if_fail (gtk_text_iter_get_btree (start_orig) ==
1564 gtk_text_iter_get_btree (end_orig));
1567 printf ("%s tag %s from %d to %d\n",
1568 add ? "Adding" : "Removing",
1570 gtk_text_buffer_get_offset (start_orig),
1571 gtk_text_buffer_get_offset (end_orig));
1574 if (gtk_text_iter_equal (start_orig, end_orig))
1577 start = *start_orig;
1580 gtk_text_iter_reorder (&start, &end);
1582 tree = gtk_text_iter_get_btree (&start);
1584 queue_tag_redisplay (tree, tag, &start, &end);
1586 info = gtk_text_btree_get_tag_info (tree, tag);
1588 start_line = gtk_text_iter_get_text_line (&start);
1589 end_line = gtk_text_iter_get_text_line (&end);
1591 /* Find all tag toggles in the region; we are going to delete them.
1592 We need to find them in advance, because
1593 forward_find_tag_toggle () won't work once we start playing around
1595 stack = iter_stack_new ();
1597 /* We don't want to delete a toggle that's at the start iterator. */
1598 gtk_text_iter_forward_char (&iter);
1599 while (gtk_text_iter_forward_to_tag_toggle (&iter, tag))
1601 if (gtk_text_iter_compare (&iter, &end) >= 0)
1604 iter_stack_push (stack, &iter);
1607 /* We need to traverse the toggles in order. */
1608 iter_stack_invert (stack);
1611 * See whether the tag is present at the start of the range. If
1612 * the state doesn't already match what we want then add a toggle
1616 toggled_on = gtk_text_iter_has_tag (&start, tag);
1617 if ( (add && !toggled_on) ||
1618 (!add && toggled_on) )
1620 /* This could create a second toggle at the start position;
1621 cleanup_line () will remove it if so. */
1622 seg = _gtk_toggle_segment_new (info, add);
1624 prev = gtk_text_line_segment_split (&start);
1627 seg->next = start_line->segments;
1628 start_line->segments = seg;
1632 seg->next = prev->next;
1636 /* cleanup_line adds the new toggle to the node counts. */
1638 printf ("added toggle at start\n");
1640 /* we should probably call segments_changed, but in theory
1641 any still-cached segments in the iters we are about to
1642 use are still valid, since they're in front
1648 * Scan the range of characters and delete any internal tag
1649 * transitions. Keep track of what the old state was at the end
1650 * of the range, and add a toggle there if it's needed.
1654 cleanupline = start_line;
1655 while (iter_stack_pop (stack, &iter))
1657 GtkTextLineSegment *indexable_seg;
1660 line = gtk_text_iter_get_text_line (&iter);
1661 seg = gtk_text_iter_get_any_segment (&iter);
1662 indexable_seg = gtk_text_iter_get_indexable_segment (&iter);
1664 g_assert (seg != NULL);
1665 g_assert (indexable_seg != NULL);
1666 g_assert (seg != indexable_seg);
1668 prev = line->segments;
1670 /* Find the segment that actually toggles this tag. */
1671 while (seg != indexable_seg)
1673 g_assert (seg != NULL);
1674 g_assert (indexable_seg != NULL);
1675 g_assert (seg != indexable_seg);
1677 if ( (seg->type == >k_text_toggle_on_type ||
1678 seg->type == >k_text_toggle_off_type) &&
1679 (seg->body.toggle.info == info) )
1685 g_assert (seg != NULL);
1686 g_assert (indexable_seg != NULL);
1688 g_assert (seg != indexable_seg); /* If this happens, then
1689 forward_to_tag_toggle was
1691 g_assert (seg->body.toggle.info->tag == tag);
1693 /* If this happens, when previously tagging we didn't merge
1694 overlapping tags. */
1695 g_assert ( (toggled_on && seg->type == >k_text_toggle_off_type) ||
1696 (!toggled_on && seg->type == >k_text_toggle_on_type) );
1698 toggled_on = !toggled_on;
1701 printf ("deleting %s toggle\n",
1702 seg->type == >k_text_toggle_on_type ? "on" : "off");
1704 /* Remove toggle segment from the list. */
1707 line->segments = seg->next;
1711 while (prev->next != seg)
1715 prev->next = seg->next;
1718 /* Inform iterators we've hosed them. This actually reflects a
1719 bit of inefficiency; if you have the same tag toggled on and
1720 off a lot in a single line, we keep having the rescan from
1721 the front of the line. Of course we have to do that to get
1722 "prev" anyway, but here we are doing it an additional
1724 segments_changed (tree);
1726 /* Update node counts */
1727 if (seg->body.toggle.inNodeCounts)
1729 _gtk_change_node_toggle_count (line->parent,
1731 seg->body.toggle.inNodeCounts = FALSE;
1736 /* We only clean up lines when we're done with them, saves some
1737 gratuitous line-segment-traversals */
1739 if (cleanupline != line)
1741 cleanup_line (cleanupline);
1746 iter_stack_free (stack);
1748 /* toggled_on now reflects the toggle state _just before_ the
1749 end iterator. The end iterator could already have a toggle
1750 on or a toggle off. */
1751 if ( (add && !toggled_on) ||
1752 (!add && toggled_on) )
1754 /* This could create a second toggle at the start position;
1755 cleanup_line () will remove it if so. */
1757 seg = _gtk_toggle_segment_new (info, !add);
1759 prev = gtk_text_line_segment_split (&end);
1762 seg->next = end_line->segments;
1763 end_line->segments = seg;
1767 seg->next = prev->next;
1770 /* cleanup_line adds the new toggle to the node counts. */
1771 g_assert (seg->body.toggle.inNodeCounts == FALSE);
1773 printf ("added toggle at end\n");
1778 * Cleanup cleanupline and the last line of the range, if
1779 * these are different.
1782 cleanup_line (cleanupline);
1783 if (cleanupline != end_line)
1785 cleanup_line (end_line);
1788 segments_changed (tree);
1790 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1791 gtk_text_btree_check (tree);
1800 gtk_text_btree_get_line (GtkTextBTree *tree,
1802 gint *real_line_number)
1804 GtkTextBTreeNode *node;
1809 line_count = gtk_text_btree_line_count (tree);
1811 if (line_number < 0)
1813 line_number = line_count;
1815 else if (line_number > line_count)
1817 line_number = line_count;
1820 if (real_line_number)
1821 *real_line_number = line_number;
1823 node = tree->root_node;
1824 lines_left = line_number;
1827 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1831 while (node->level != 0)
1833 for (node = node->children.node;
1834 node->num_lines <= lines_left;
1840 g_error ("gtk_text_btree_find_line ran out of GtkTextBTreeNodes");
1843 lines_left -= node->num_lines;
1848 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1851 for (line = node->children.line; lines_left > 0;
1857 g_error ("gtk_text_btree_find_line ran out of lines");
1866 gtk_text_btree_get_line_at_char (GtkTextBTree *tree,
1868 gint *line_start_index,
1869 gint *real_char_index)
1871 GtkTextBTreeNode *node;
1873 GtkTextLineSegment *seg;
1878 node = tree->root_node;
1880 /* Clamp to valid indexes (-1 is magic for "highest index") */
1881 if (char_index < 0 || char_index >= node->num_chars)
1883 char_index = node->num_chars - 1;
1886 *real_char_index = char_index;
1889 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1893 chars_left = char_index;
1894 while (node->level != 0)
1896 for (node = node->children.node;
1897 chars_left >= node->num_chars;
1900 chars_left -= node->num_chars;
1902 g_assert (chars_left >= 0);
1906 if (chars_left == 0)
1908 /* Start of a line */
1910 *line_start_index = char_index;
1911 return node->children.line;
1915 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1921 for (line = node->children.line; line != NULL; line = line->next)
1923 seg = line->segments;
1926 if (chars_in_line + seg->char_count > chars_left)
1927 goto found; /* found our line/segment */
1929 chars_in_line += seg->char_count;
1934 chars_left -= chars_in_line;
1942 g_assert (line != NULL); /* hosage, ran out of lines */
1943 g_assert (seg != NULL);
1945 *line_start_index = char_index - chars_left;
1950 gtk_text_btree_get_tags (const GtkTextIter *iter,
1953 GtkTextBTreeNode *node;
1954 GtkTextLine *siblingline;
1955 GtkTextLineSegment *seg;
1956 int src, dst, index;
1962 #define NUM_TAG_INFOS 10
1964 line = gtk_text_iter_get_text_line (iter);
1965 tree = gtk_text_iter_get_btree (iter);
1966 byte_index = gtk_text_iter_get_line_index (iter);
1968 tagInfo.numTags = 0;
1969 tagInfo.arraySize = NUM_TAG_INFOS;
1970 tagInfo.tags = g_new (GtkTextTag*, NUM_TAG_INFOS);
1971 tagInfo.counts = g_new (int, NUM_TAG_INFOS);
1974 * Record tag toggles within the line of indexPtr but preceding
1975 * indexPtr. Note that if this loop segfaults, your
1976 * byte_index probably points past the sum of all
1977 * seg->byte_count */
1979 for (index = 0, seg = line->segments;
1980 (index + seg->byte_count) <= byte_index;
1981 index += seg->byte_count, seg = seg->next)
1983 if ((seg->type == >k_text_toggle_on_type)
1984 || (seg->type == >k_text_toggle_off_type))
1986 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
1991 * Record toggles for tags in lines that are predecessors of
1992 * line but under the same level-0 GtkTextBTreeNode.
1995 for (siblingline = line->parent->children.line;
1996 siblingline != line;
1997 siblingline = siblingline->next)
1999 for (seg = siblingline->segments; seg != NULL;
2002 if ((seg->type == >k_text_toggle_on_type)
2003 || (seg->type == >k_text_toggle_off_type))
2005 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2011 * For each GtkTextBTreeNode in the ancestry of this line, record tag
2012 * toggles for all siblings that precede that GtkTextBTreeNode.
2015 for (node = line->parent; node->parent != NULL;
2016 node = node->parent)
2018 GtkTextBTreeNode *siblingPtr;
2021 for (siblingPtr = node->parent->children.node;
2022 siblingPtr != node; siblingPtr = siblingPtr->next)
2024 for (summary = siblingPtr->summary; summary != NULL;
2025 summary = summary->next)
2027 if (summary->toggle_count & 1)
2029 inc_count (summary->info->tag, summary->toggle_count,
2037 * Go through the tag information and squash out all of the tags
2038 * that have even toggle counts (these tags exist before the point
2039 * of interest, but not at the desired character itself).
2042 for (src = 0, dst = 0; src < tagInfo.numTags; src++)
2044 if (tagInfo.counts[src] & 1)
2046 g_assert (GTK_IS_TEXT_TAG (tagInfo.tags[src]));
2047 tagInfo.tags[dst] = tagInfo.tags[src];
2053 g_free (tagInfo.counts);
2056 g_free (tagInfo.tags);
2059 return tagInfo.tags;
2063 copy_segment (GString *string,
2064 gboolean include_hidden,
2065 gboolean include_nonchars,
2066 const GtkTextIter *start,
2067 const GtkTextIter *end)
2069 GtkTextLineSegment *end_seg;
2070 GtkTextLineSegment *seg;
2072 if (gtk_text_iter_equal (start, end))
2075 seg = gtk_text_iter_get_indexable_segment (start);
2076 end_seg = gtk_text_iter_get_indexable_segment (end);
2078 if (seg->type == >k_text_char_type)
2080 gboolean copy = TRUE;
2081 gint copy_bytes = 0;
2082 gint copy_start = 0;
2084 /* Don't copy if we're invisible; segments are invisible/not
2085 as a whole, no need to check each char */
2086 if (!include_hidden &&
2087 gtk_text_btree_char_is_invisible (start))
2090 /* printf (" <invisible>\n"); */
2093 copy_start = gtk_text_iter_get_segment_byte (start);
2097 /* End is in the same segment; need to copy fewer bytes. */
2098 gint end_byte = gtk_text_iter_get_segment_byte (end);
2100 copy_bytes = end_byte - copy_start;
2103 copy_bytes = seg->byte_count - copy_start;
2105 g_assert (copy_bytes != 0); /* Due to iter equality check at
2106 front of this function. */
2110 g_assert ((copy_start + copy_bytes) <= seg->byte_count);
2112 g_string_append_len (string,
2113 seg->body.chars + copy_start,
2117 /* printf (" :%s\n", string->str); */
2119 else if (seg->type == >k_text_pixbuf_type ||
2120 seg->type == >k_text_child_type)
2122 gboolean copy = TRUE;
2124 if (!include_nonchars)
2128 else if (!include_hidden &&
2129 gtk_text_btree_char_is_invisible (start))
2136 g_string_append_len (string,
2137 gtk_text_unknown_char_utf8,
2145 gtk_text_btree_get_text (const GtkTextIter *start_orig,
2146 const GtkTextIter *end_orig,
2147 gboolean include_hidden,
2148 gboolean include_nonchars)
2150 GtkTextLineSegment *seg;
2151 GtkTextLineSegment *end_seg;
2159 g_return_val_if_fail (start_orig != NULL, NULL);
2160 g_return_val_if_fail (end_orig != NULL, NULL);
2161 g_return_val_if_fail (gtk_text_iter_get_btree (start_orig) ==
2162 gtk_text_iter_get_btree (end_orig), NULL);
2164 start = *start_orig;
2167 gtk_text_iter_reorder (&start, &end);
2169 retval = g_string_new ("");
2171 tree = gtk_text_iter_get_btree (&start);
2173 end_seg = gtk_text_iter_get_indexable_segment (&end);
2175 seg = gtk_text_iter_get_indexable_segment (&iter);
2176 while (seg != end_seg)
2178 copy_segment (retval, include_hidden, include_nonchars,
2181 gtk_text_iter_forward_indexable_segment (&iter);
2183 seg = gtk_text_iter_get_indexable_segment (&iter);
2186 copy_segment (retval, include_hidden, include_nonchars, &iter, &end);
2189 g_string_free (retval, FALSE);
2194 gtk_text_btree_line_count (GtkTextBTree *tree)
2196 /* Subtract bogus line at the end; we return a count
2198 return tree->root_node->num_lines - 1;
2202 gtk_text_btree_char_count (GtkTextBTree *tree)
2204 /* Exclude newline in bogus last line */
2205 return tree->root_node->num_chars - 1;
2208 #define LOTSA_TAGS 1000
2210 gtk_text_btree_char_is_invisible (const GtkTextIter *iter)
2212 gboolean invisible = FALSE; /* if nobody says otherwise, it's visible */
2214 int deftagCnts[LOTSA_TAGS];
2215 int *tagCnts = deftagCnts;
2216 GtkTextTag *deftags[LOTSA_TAGS];
2217 GtkTextTag **tags = deftags;
2219 GtkTextBTreeNode *node;
2220 GtkTextLine *siblingline;
2221 GtkTextLineSegment *seg;
2228 line = gtk_text_iter_get_text_line (iter);
2229 tree = gtk_text_iter_get_btree (iter);
2230 byte_index = gtk_text_iter_get_line_index (iter);
2232 numTags = gtk_text_tag_table_size (tree->table);
2234 /* almost always avoid malloc, so stay out of system calls */
2235 if (LOTSA_TAGS < numTags)
2237 tagCnts = g_new (int, numTags);
2238 tags = g_new (GtkTextTag*, numTags);
2241 for (i=0; i<numTags; i++)
2247 * Record tag toggles within the line of indexPtr but preceding
2251 for (index = 0, seg = line->segments;
2252 (index + seg->byte_count) <= byte_index; /* segfault here means invalid index */
2253 index += seg->byte_count, seg = seg->next)
2255 if ((seg->type == >k_text_toggle_on_type)
2256 || (seg->type == >k_text_toggle_off_type))
2258 tag = seg->body.toggle.info->tag;
2259 if (tag->invisible_set && tag->values->invisible)
2261 tags[tag->priority] = tag;
2262 tagCnts[tag->priority]++;
2268 * Record toggles for tags in lines that are predecessors of
2269 * line but under the same level-0 GtkTextBTreeNode.
2272 for (siblingline = line->parent->children.line;
2273 siblingline != line;
2274 siblingline = siblingline->next)
2276 for (seg = siblingline->segments; seg != NULL;
2279 if ((seg->type == >k_text_toggle_on_type)
2280 || (seg->type == >k_text_toggle_off_type))
2282 tag = seg->body.toggle.info->tag;
2283 if (tag->invisible_set && tag->values->invisible)
2285 tags[tag->priority] = tag;
2286 tagCnts[tag->priority]++;
2293 * For each GtkTextBTreeNode in the ancestry of this line, record tag toggles
2294 * for all siblings that precede that GtkTextBTreeNode.
2297 for (node = line->parent; node->parent != NULL;
2298 node = node->parent)
2300 GtkTextBTreeNode *siblingPtr;
2303 for (siblingPtr = node->parent->children.node;
2304 siblingPtr != node; siblingPtr = siblingPtr->next)
2306 for (summary = siblingPtr->summary; summary != NULL;
2307 summary = summary->next)
2309 if (summary->toggle_count & 1)
2311 tag = summary->info->tag;
2312 if (tag->invisible_set && tag->values->invisible)
2314 tags[tag->priority] = tag;
2315 tagCnts[tag->priority] += summary->toggle_count;
2323 * Now traverse from highest priority to lowest,
2324 * take invisible value from first odd count (= on)
2327 for (i = numTags-1; i >=0; i--)
2331 /* FIXME not sure this should be if 0 */
2333 #ifndef ALWAYS_SHOW_SELECTION
2334 /* who would make the selection invisible? */
2335 if ((tag == tkxt->seltag)
2336 && !(tkxt->flags & GOT_FOCUS))
2342 invisible = tags[i]->values->invisible;
2347 if (LOTSA_TAGS < numTags)
2362 redisplay_region (GtkTextBTree *tree,
2363 const GtkTextIter *start,
2364 const GtkTextIter *end)
2367 GtkTextLine *start_line, *end_line;
2369 if (gtk_text_iter_compare (start, end) > 0)
2371 const GtkTextIter *tmp = start;
2376 start_line = gtk_text_iter_get_text_line (start);
2377 end_line = gtk_text_iter_get_text_line (end);
2380 while (view != NULL)
2382 gint start_y, end_y;
2383 GtkTextLineData *ld;
2385 start_y = gtk_text_btree_find_line_top (tree, start_line, view->view_id);
2387 if (end_line == start_line)
2390 end_y = gtk_text_btree_find_line_top (tree, end_line, view->view_id);
2392 ld = gtk_text_line_get_data (end_line, view->view_id);
2394 end_y += ld->height;
2396 gtk_text_layout_changed (view->layout, start_y,
2405 redisplay_mark (GtkTextLineSegment *mark)
2410 gtk_text_btree_get_iter_at_mark (mark->body.mark.tree,
2412 mark->body.mark.obj);
2415 gtk_text_iter_forward_char (&end);
2417 gtk_text_btree_invalidate_region (mark->body.mark.tree,
2422 redisplay_mark_if_visible (GtkTextLineSegment *mark)
2424 if (!mark->body.mark.visible)
2427 redisplay_mark (mark);
2431 ensure_not_off_end (GtkTextBTree *tree,
2432 GtkTextLineSegment *mark,
2435 if (gtk_text_iter_get_line (iter) ==
2436 gtk_text_btree_line_count (tree))
2437 gtk_text_iter_backward_char (iter);
2440 static GtkTextLineSegment*
2441 real_set_mark (GtkTextBTree *tree,
2442 GtkTextMark *existing_mark,
2444 gboolean left_gravity,
2445 const GtkTextIter *where,
2446 gboolean should_exist,
2447 gboolean redraw_selections)
2449 GtkTextLineSegment *mark;
2452 g_return_val_if_fail (tree != NULL, NULL);
2453 g_return_val_if_fail (where != NULL, NULL);
2454 g_return_val_if_fail (gtk_text_iter_get_btree (where) == tree, NULL);
2457 mark = existing_mark->segment;
2458 else if (name != NULL)
2459 mark = g_hash_table_lookup (tree->mark_table,
2464 if (should_exist && mark == NULL)
2466 g_warning ("No mark `%s' exists!", name);
2470 /* OK if !should_exist and it does already exist, in that case
2476 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2477 gtk_text_iter_check (&iter);
2481 if (redraw_selections &&
2482 (mark == tree->insert_mark->segment ||
2483 mark == tree->selection_bound_mark->segment))
2485 GtkTextIter old_pos;
2487 gtk_text_btree_get_iter_at_mark (tree, &old_pos,
2488 mark->body.mark.obj);
2489 redisplay_region (tree, &old_pos, where);
2493 * don't let visible marks be after the final newline of the
2497 if (mark->body.mark.visible)
2499 ensure_not_off_end (tree, mark, &iter);
2502 /* Redraw the mark's old location. */
2503 redisplay_mark_if_visible (mark);
2505 /* Unlink mark from its current location.
2506 This could hose our iterator... */
2507 gtk_text_btree_unlink_segment (tree, mark,
2508 mark->body.mark.line);
2509 mark->body.mark.line = gtk_text_iter_get_text_line (&iter);
2510 g_assert (mark->body.mark.line == gtk_text_iter_get_text_line (&iter));
2512 segments_changed (tree); /* make sure the iterator recomputes its
2517 mark = _gtk_mark_segment_new (tree,
2521 mark->body.mark.line = gtk_text_iter_get_text_line (&iter);
2523 if (mark->body.mark.name)
2524 g_hash_table_insert (tree->mark_table,
2525 mark->body.mark.name,
2529 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2530 gtk_text_iter_check (&iter);
2532 /* Link mark into new location */
2533 gtk_text_btree_link_segment (mark, &iter);
2535 /* Invalidate some iterators. */
2536 segments_changed (tree);
2539 * update the screen at the mark's new location.
2542 redisplay_mark_if_visible (mark);
2544 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2545 gtk_text_iter_check (&iter);
2547 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2548 gtk_text_btree_check (tree);
2555 gtk_text_btree_set_mark (GtkTextBTree *tree,
2556 GtkTextMark *existing_mark,
2558 gboolean left_gravity,
2559 const GtkTextIter *iter,
2560 gboolean should_exist)
2562 GtkTextLineSegment *seg;
2564 seg = real_set_mark (tree, existing_mark,
2565 name, left_gravity, iter, should_exist,
2568 return seg ? seg->body.mark.obj : NULL;
2572 gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2576 GtkTextIter tmp_start, tmp_end;
2578 gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2580 gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2581 tree->selection_bound_mark);
2583 if (gtk_text_iter_equal (&tmp_start, &tmp_end))
2595 gtk_text_iter_reorder (&tmp_start, &tmp_end);
2608 gtk_text_btree_place_cursor (GtkTextBTree *tree,
2609 const GtkTextIter *iter)
2611 GtkTextIter start, end;
2613 if (gtk_text_btree_get_selection_bounds (tree, &start, &end))
2614 redisplay_region (tree, &start, &end);
2616 /* Move insert AND selection_bound before we redisplay */
2617 real_set_mark (tree, tree->insert_mark,
2618 "insert", FALSE, iter, TRUE, FALSE);
2619 real_set_mark (tree, tree->selection_bound_mark,
2620 "selection_bound", FALSE, iter, TRUE, FALSE);
2624 gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2629 g_return_if_fail (tree != NULL);
2630 g_return_if_fail (name != NULL);
2632 mark = g_hash_table_lookup (tree->mark_table,
2635 gtk_text_btree_remove_mark (tree, mark);
2639 gtk_text_btree_remove_mark (GtkTextBTree *tree,
2642 GtkTextLineSegment *segment;
2644 g_return_if_fail (mark != NULL);
2645 g_return_if_fail (tree != NULL);
2647 segment = mark->segment;
2649 if (segment->body.mark.not_deleteable)
2651 g_warning ("Can't delete special mark `%s'", segment->body.mark.name);
2655 /* This calls cleanup_line and segments_changed */
2656 gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2658 if (segment->body.mark.name)
2659 g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2661 /* Remove the ref on the mark that belonged to the segment. */
2662 g_object_unref (G_OBJECT (mark));
2664 segment->body.mark.tree = NULL;
2665 segment->body.mark.line = NULL;
2669 gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2670 GtkTextMark *segment)
2672 return segment == tree->insert_mark;
2676 gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2677 GtkTextMark *segment)
2679 return segment == tree->selection_bound_mark;
2683 gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2686 GtkTextLineSegment *seg;
2688 g_return_val_if_fail (tree != NULL, NULL);
2689 g_return_val_if_fail (name != NULL, NULL);
2691 seg = g_hash_table_lookup (tree->mark_table, name);
2693 return seg ? seg->body.mark.obj : NULL;
2697 gtk_text_mark_set_visible (GtkTextMark *mark,
2700 GtkTextLineSegment *seg;
2702 g_return_if_fail (mark != NULL);
2704 seg = mark->segment;
2706 if (seg->body.mark.visible == setting)
2710 seg->body.mark.visible = setting;
2712 redisplay_mark (seg);
2717 gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
2720 GtkTextBTreeNode *node;
2721 GtkTextTagInfo *info;
2723 g_return_val_if_fail (tree != NULL, NULL);
2727 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2732 if (info->tag_root == NULL)
2735 node = info->tag_root;
2737 /* We know the tag root has instances of the given
2740 continue_outer_loop:
2741 g_assert (node != NULL);
2742 while (node->level > 0)
2744 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2745 node = node->children.node;
2746 while (node != NULL)
2748 if (gtk_text_btree_node_has_tag (node, tag))
2749 goto continue_outer_loop;
2753 g_assert (node != NULL);
2756 g_assert (node != NULL); /* The tag summaries said some node had
2759 g_assert (node->level == 0);
2761 return node->children.line;
2765 /* Looking for any tag at all (tag == NULL).
2766 Unfortunately this can't be done in a simple and efficient way
2767 right now; so I'm just going to return the
2768 first line in the btree. FIXME */
2769 return gtk_text_btree_get_line (tree, 0, NULL);
2774 gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
2777 GtkTextBTreeNode *node;
2778 GtkTextBTreeNode *last_node;
2780 GtkTextTagInfo *info;
2782 g_return_val_if_fail (tree != NULL, NULL);
2786 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2788 if (info->tag_root == NULL)
2791 node = info->tag_root;
2792 /* We know the tag root has instances of the given
2795 while (node->level > 0)
2797 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2799 node = node->children.node;
2800 while (node != NULL)
2802 if (gtk_text_btree_node_has_tag (node, tag))
2810 g_assert (node != NULL); /* The tag summaries said some node had
2813 g_assert (node->level == 0);
2815 /* Find the last line in this node */
2816 line = node->children.line;
2817 while (line->next != NULL)
2824 /* This search can't be done efficiently at the moment,
2825 at least not without complexity.
2826 So, we just return the last line.
2828 return gtk_text_btree_get_line (tree, -1, NULL);
2838 gtk_text_line_get_number (GtkTextLine *line)
2841 GtkTextBTreeNode *node, *parent, *node2;
2845 * First count how many lines precede this one in its level-0
2849 node = line->parent;
2851 for (line2 = node->children.line; line2 != line;
2852 line2 = line2->next)
2856 g_error ("gtk_text_btree_line_number couldn't find line");
2862 * Now work up through the levels of the tree one at a time,
2863 * counting how many lines are in GtkTextBTreeNodes preceding the current
2867 for (parent = node->parent ; parent != NULL;
2868 node = parent, parent = parent->parent)
2870 for (node2 = parent->children.node; node2 != node;
2871 node2 = node2->next)
2875 g_error ("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
2877 index += node2->num_lines;
2883 static GtkTextLineSegment*
2884 find_toggle_segment_before_char (GtkTextLine *line,
2888 GtkTextLineSegment *seg;
2889 GtkTextLineSegment *toggle_seg;
2894 seg = line->segments;
2895 while ( (index + seg->char_count) <= char_in_line )
2897 if (((seg->type == >k_text_toggle_on_type)
2898 || (seg->type == >k_text_toggle_off_type))
2899 && (seg->body.toggle.info->tag == tag))
2902 index += seg->char_count;
2909 static GtkTextLineSegment*
2910 find_toggle_segment_before_byte (GtkTextLine *line,
2914 GtkTextLineSegment *seg;
2915 GtkTextLineSegment *toggle_seg;
2920 seg = line->segments;
2921 while ( (index + seg->byte_count) <= byte_in_line )
2923 if (((seg->type == >k_text_toggle_on_type)
2924 || (seg->type == >k_text_toggle_off_type))
2925 && (seg->body.toggle.info->tag == tag))
2928 index += seg->byte_count;
2936 find_toggle_outside_current_line (GtkTextLine *line,
2940 GtkTextBTreeNode *node;
2941 GtkTextLine *sibling_line;
2942 GtkTextLineSegment *seg;
2943 GtkTextLineSegment *toggle_seg;
2945 GtkTextTagInfo *info = NULL;
2948 * No toggle in this line. Look for toggles for the tag in lines
2949 * that are predecessors of line but under the same
2950 * level-0 GtkTextBTreeNode.
2953 sibling_line = line->parent->children.line;
2954 while (sibling_line != line)
2956 seg = sibling_line->segments;
2959 if (((seg->type == >k_text_toggle_on_type)
2960 || (seg->type == >k_text_toggle_off_type))
2961 && (seg->body.toggle.info->tag == tag))
2967 sibling_line = sibling_line->next;
2970 if (toggle_seg != NULL)
2971 return (toggle_seg->type == >k_text_toggle_on_type);
2974 * No toggle in this GtkTextBTreeNode. Scan upwards through the ancestors of
2975 * this GtkTextBTreeNode, counting the number of toggles of the given tag in
2976 * siblings that precede that GtkTextBTreeNode.
2979 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2985 node = line->parent;
2986 while (node->parent != NULL)
2988 GtkTextBTreeNode *sibling_node;
2990 sibling_node = node->parent->children.node;
2991 while (sibling_node != node)
2995 summary = sibling_node->summary;
2996 while (summary != NULL)
2998 if (summary->info == info)
2999 toggles += summary->toggle_count;
3001 summary = summary->next;
3004 sibling_node = sibling_node->next;
3007 if (node == info->tag_root)
3010 node = node->parent;
3014 * An odd number of toggles means that the tag is present at the
3018 return (toggles & 1) != 0;
3021 /* FIXME this function is far too slow, for no good reason. */
3023 gtk_text_line_char_has_tag (GtkTextLine *line,
3028 GtkTextLineSegment *toggle_seg;
3030 g_return_val_if_fail (line != NULL, FALSE);
3033 * Check for toggles for the tag in the line but before
3034 * the char. If there is one, its type indicates whether or
3035 * not the character is tagged.
3038 toggle_seg = find_toggle_segment_before_char (line, char_in_line, tag);
3040 if (toggle_seg != NULL)
3041 return (toggle_seg->type == >k_text_toggle_on_type);
3043 return find_toggle_outside_current_line (line, tree, tag);
3047 gtk_text_line_byte_has_tag (GtkTextLine *line,
3052 GtkTextLineSegment *toggle_seg;
3054 g_return_val_if_fail (line != NULL, FALSE);
3057 * Check for toggles for the tag in the line but before
3058 * the char. If there is one, its type indicates whether or
3059 * not the character is tagged.
3062 toggle_seg = find_toggle_segment_before_byte (line, byte_in_line, tag);
3064 if (toggle_seg != NULL)
3065 return (toggle_seg->type == >k_text_toggle_on_type);
3067 return find_toggle_outside_current_line (line, tree, tag);
3071 gtk_text_line_is_last (GtkTextLine *line,
3074 return line == get_last_line (tree);
3078 gtk_text_line_next (GtkTextLine *line)
3080 GtkTextBTreeNode *node;
3082 if (line->next != NULL)
3087 * This was the last line associated with the particular parent
3088 * GtkTextBTreeNode. Search up the tree for the next GtkTextBTreeNode,
3089 * then search down from that GtkTextBTreeNode to find the first
3093 node = line->parent;
3094 while (node != NULL && node->next == NULL)
3095 node = node->parent;
3101 while (node->level > 0)
3103 node = node->children.node;
3106 g_assert (node->children.line != line);
3108 return node->children.line;
3113 gtk_text_line_previous (GtkTextLine *line)
3115 GtkTextBTreeNode *node;
3116 GtkTextBTreeNode *node2;
3120 * Find the line under this GtkTextBTreeNode just before the starting line.
3122 prev = line->parent->children.line; /* First line at leaf */
3123 while (prev != line)
3125 if (prev->next == line)
3131 g_error ("gtk_text_btree_previous_line ran out of lines");
3135 * This was the first line associated with the particular parent
3136 * GtkTextBTreeNode. Search up the tree for the previous GtkTextBTreeNode,
3137 * then search down from that GtkTextBTreeNode to find its last line.
3139 for (node = line->parent; ; node = node->parent)
3141 if (node == NULL || node->parent == NULL)
3143 else if (node != node->parent->children.node)
3147 for (node2 = node->parent->children.node; ;
3148 node2 = node2->children.node)
3150 while (node2->next != node)
3151 node2 = node2->next;
3153 if (node2->level == 0)
3159 for (prev = node2->children.line ; ; prev = prev->next)
3161 if (prev->next == NULL)
3165 g_assert_not_reached ();
3170 gtk_text_line_add_data (GtkTextLine *line,
3171 GtkTextLineData *data)
3173 g_return_if_fail (line != NULL);
3174 g_return_if_fail (data != NULL);
3175 g_return_if_fail (data->view_id != NULL);
3179 data->next = line->views;
3189 gtk_text_line_remove_data (GtkTextLine *line,
3192 GtkTextLineData *prev;
3193 GtkTextLineData *iter;
3195 g_return_val_if_fail (line != NULL, NULL);
3196 g_return_val_if_fail (view_id != NULL, NULL);
3200 while (iter != NULL)
3202 if (iter->view_id == view_id)
3211 prev->next = iter->next;
3213 line->views = iter->next;
3222 gtk_text_line_get_data (GtkTextLine *line,
3225 GtkTextLineData *iter;
3227 g_return_val_if_fail (line != NULL, NULL);
3228 g_return_val_if_fail (view_id != NULL, NULL);
3231 while (iter != NULL)
3233 if (iter->view_id == view_id)
3242 gtk_text_line_invalidate_wrap (GtkTextLine *line,
3243 GtkTextLineData *ld)
3245 /* For now this is totally unoptimized. FIXME?
3247 We could probably optimize the case where the width removed
3248 is less than the max width for the parent node,
3249 and the case where the height is unchanged when we re-wrap.
3252 g_return_if_fail (ld != NULL);
3255 gtk_text_btree_node_invalidate_upward (line->parent, ld->view_id);
3259 gtk_text_line_char_count (GtkTextLine *line)
3261 GtkTextLineSegment *seg;
3265 seg = line->segments;
3268 size += seg->char_count;
3275 gtk_text_line_byte_count (GtkTextLine *line)
3277 GtkTextLineSegment *seg;
3281 seg = line->segments;
3284 size += seg->byte_count;
3292 gtk_text_line_char_index (GtkTextLine *target_line)
3294 GSList *node_stack = NULL;
3295 GtkTextBTreeNode *iter;
3299 /* Push all our parent nodes onto a stack */
3300 iter = target_line->parent;
3302 g_assert (iter != NULL);
3304 while (iter != NULL)
3306 node_stack = g_slist_prepend (node_stack, iter);
3308 iter = iter->parent;
3311 /* Check that we have the root node on top of the stack. */
3312 g_assert (node_stack != NULL &&
3313 node_stack->data != NULL &&
3314 ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3316 /* Add up chars in all nodes before the nodes in our stack.
3320 iter = node_stack->data;
3321 while (iter != NULL)
3323 GtkTextBTreeNode *child_iter;
3324 GtkTextBTreeNode *next_node;
3326 next_node = node_stack->next ?
3327 node_stack->next->data : NULL;
3328 node_stack = g_slist_remove (node_stack, node_stack->data);
3330 if (iter->level == 0)
3332 /* stack should be empty when we're on the last node */
3333 g_assert (node_stack == NULL);
3334 break; /* Our children are now lines */
3337 g_assert (next_node != NULL);
3338 g_assert (iter != NULL);
3339 g_assert (next_node->parent == iter);
3341 /* Add up chars before us in the tree */
3342 child_iter = iter->children.node;
3343 while (child_iter != next_node)
3345 g_assert (child_iter != NULL);
3347 num_chars += child_iter->num_chars;
3349 child_iter = child_iter->next;
3355 g_assert (iter != NULL);
3356 g_assert (iter == target_line->parent);
3358 /* Since we don't store char counts in lines, only in segments, we
3359 have to iterate over the lines adding up segment char counts
3360 until we find our line. */
3361 line = iter->children.line;
3362 while (line != target_line)
3364 g_assert (line != NULL);
3366 num_chars += gtk_text_line_char_count (line);
3371 g_assert (line == target_line);
3377 gtk_text_line_byte_to_segment (GtkTextLine *line,
3381 GtkTextLineSegment *seg;
3384 g_return_val_if_fail (line != NULL, NULL);
3386 offset = byte_offset;
3387 seg = line->segments;
3389 while (offset >= seg->byte_count)
3391 g_assert (seg != NULL); /* means an invalid byte index */
3392 offset -= seg->byte_count;
3397 *seg_offset = offset;
3403 gtk_text_line_char_to_segment (GtkTextLine *line,
3407 GtkTextLineSegment *seg;
3410 g_return_val_if_fail (line != NULL, NULL);
3412 offset = char_offset;
3413 seg = line->segments;
3415 while (offset >= seg->char_count)
3417 g_assert (seg != NULL); /* means an invalid char index */
3418 offset -= seg->char_count;
3423 *seg_offset = offset;
3429 gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3433 GtkTextLineSegment *seg;
3436 g_return_val_if_fail (line != NULL, NULL);
3438 offset = byte_offset;
3439 seg = line->segments;
3441 while (offset > 0 && offset >= seg->byte_count)
3443 g_assert (seg != NULL); /* means an invalid byte index */
3444 offset -= seg->byte_count;
3449 *seg_offset = offset;
3455 gtk_text_line_char_to_any_segment (GtkTextLine *line,
3459 GtkTextLineSegment *seg;
3462 g_return_val_if_fail (line != NULL, NULL);
3464 offset = char_offset;
3465 seg = line->segments;
3467 while (offset > 0 && offset >= seg->char_count)
3469 g_assert (seg != NULL); /* means an invalid byte index */
3470 offset -= seg->char_count;
3475 *seg_offset = offset;
3481 gtk_text_line_byte_to_char (GtkTextLine *line,
3485 GtkTextLineSegment *seg;
3487 g_return_val_if_fail (line != NULL, 0);
3488 g_return_val_if_fail (byte_offset >= 0, 0);
3491 seg = line->segments;
3492 while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3493 the next segment) */
3495 g_assert (seg != NULL); /* our byte_index was bogus if this happens */
3497 byte_offset -= seg->byte_count;
3498 char_offset += seg->char_count;
3503 g_assert (seg != NULL);
3505 /* Now byte_offset is the offset into the current segment,
3506 and char_offset is the start of the current segment.
3507 Optimize the case where no chars use > 1 byte */
3508 if (seg->byte_count == seg->char_count)
3509 return char_offset + byte_offset;
3512 if (seg->type == >k_text_char_type)
3513 return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3516 g_assert (seg->char_count == 1);
3517 g_assert (byte_offset == 0);
3525 gtk_text_line_char_to_byte (GtkTextLine *line,
3528 g_warning ("FIXME not implemented");
3533 /* FIXME sync with char_locate (or figure out a clean
3534 way to merge the two functions) */
3536 gtk_text_line_byte_locate (GtkTextLine *line,
3538 GtkTextLineSegment **segment,
3539 GtkTextLineSegment **any_segment,
3540 gint *seg_byte_offset,
3541 gint *line_byte_offset)
3543 GtkTextLineSegment *seg;
3544 GtkTextLineSegment *after_prev_indexable;
3545 GtkTextLineSegment *after_last_indexable;
3546 GtkTextLineSegment *last_indexable;
3550 g_return_if_fail (line != NULL);
3552 if (byte_offset < 0)
3554 /* -1 means end of line; we here assume no line is
3555 longer than 1 bazillion bytes, of course we assumed
3556 that anyway since we'd wrap around... */
3558 byte_offset = G_MAXINT;
3562 *any_segment = NULL;
3565 offset = byte_offset;
3567 last_indexable = NULL;
3568 after_last_indexable = line->segments;
3569 after_prev_indexable = line->segments;
3570 seg = line->segments;
3572 /* The loop ends when we're inside a segment;
3573 last_indexable refers to the last segment
3574 we passed entirely. */
3575 while (seg && offset >= seg->byte_count)
3577 if (seg->char_count > 0)
3579 offset -= seg->byte_count;
3580 bytes_in_line += seg->byte_count;
3581 last_indexable = seg;
3582 after_prev_indexable = after_last_indexable;
3583 after_last_indexable = last_indexable->next;
3591 /* We went off the end of the line */
3592 *segment = last_indexable;
3593 *any_segment = after_prev_indexable;
3594 /* subtracting 1 is OK, we know it's a newline at the end. */
3595 offset = (*segment)->byte_count - 1;
3596 bytes_in_line -= (*segment)->byte_count;
3601 if (after_last_indexable != NULL)
3602 *any_segment = after_last_indexable;
3604 *any_segment = *segment;
3607 /* Override any_segment if we're in the middle of a segment. */
3609 *any_segment = *segment;
3611 *seg_byte_offset = offset;
3613 g_assert (*segment != NULL);
3614 g_assert (*any_segment != NULL);
3615 g_assert (*seg_byte_offset < (*segment)->byte_count);
3617 *line_byte_offset = bytes_in_line + *seg_byte_offset;
3620 /* FIXME sync with byte_locate (or figure out a clean
3621 way to merge the two functions) */
3623 gtk_text_line_char_locate (GtkTextLine *line,
3625 GtkTextLineSegment **segment,
3626 GtkTextLineSegment **any_segment,
3627 gint *seg_char_offset,
3628 gint *line_char_offset)
3630 GtkTextLineSegment *seg;
3631 GtkTextLineSegment *after_prev_indexable;
3632 GtkTextLineSegment *after_last_indexable;
3633 GtkTextLineSegment *last_indexable;
3637 g_return_if_fail (line != NULL);
3639 if (char_offset < 0)
3641 /* -1 means end of line; we here assume no line is
3642 longer than 1 bazillion chars, of course we assumed
3643 that anyway since we'd wrap around... */
3645 char_offset = G_MAXINT;
3649 *any_segment = NULL;
3652 offset = char_offset;
3654 last_indexable = NULL;
3655 after_last_indexable = line->segments;
3656 after_prev_indexable = line->segments;
3657 seg = line->segments;
3659 /* The loop ends when we're inside a segment;
3660 last_indexable refers to the last segment
3661 we passed entirely. */
3662 while (seg && offset >= seg->char_count)
3664 if (seg->char_count > 0)
3666 offset -= seg->char_count;
3667 chars_in_line += seg->char_count;
3668 last_indexable = seg;
3669 after_prev_indexable = after_last_indexable;
3670 after_last_indexable = last_indexable->next;
3678 /* We went off the end of the line */
3679 *segment = last_indexable;
3680 *any_segment = after_prev_indexable;
3681 /* subtracting 1 is OK, we know it's a newline at the end. */
3682 offset = (*segment)->char_count - 1;
3683 chars_in_line -= (*segment)->char_count;
3688 if (after_last_indexable != NULL)
3689 *any_segment = after_last_indexable;
3691 *any_segment = *segment;
3694 /* Override any_segment if we're in the middle of a segment. */
3696 *any_segment = *segment;
3698 *seg_char_offset = offset;
3700 g_assert (*segment != NULL);
3701 g_assert (*any_segment != NULL);
3702 g_assert (*seg_char_offset < (*segment)->char_count);
3704 *line_char_offset = chars_in_line + *seg_char_offset;
3708 gtk_text_line_byte_to_char_offsets (GtkTextLine *line,
3710 gint *line_char_offset,
3711 gint *seg_char_offset)
3713 GtkTextLineSegment *seg;
3716 g_return_if_fail (line != NULL);
3717 g_return_if_fail (byte_offset >= 0);
3719 *line_char_offset = 0;
3721 offset = byte_offset;
3722 seg = line->segments;
3724 while (offset >= seg->byte_count)
3726 offset -= seg->byte_count;
3727 *line_char_offset += seg->char_count;
3729 g_assert (seg != NULL); /* means an invalid char offset */
3732 g_assert (seg->char_count > 0); /* indexable. */
3734 /* offset is now the number of bytes into the current segment we
3735 * want to go. Count chars into the current segment.
3738 if (seg->type == >k_text_char_type)
3740 *seg_char_offset = g_utf8_strlen (seg->body.chars, offset);
3742 g_assert (*seg_char_offset < seg->char_count);
3744 *line_char_offset += *seg_char_offset;
3748 g_assert (offset == 0);
3749 *seg_char_offset = 0;
3754 gtk_text_line_char_to_byte_offsets (GtkTextLine *line,
3756 gint *line_byte_offset,
3757 gint *seg_byte_offset)
3759 GtkTextLineSegment *seg;
3762 g_return_if_fail (line != NULL);
3763 g_return_if_fail (char_offset >= 0);
3765 *line_byte_offset = 0;
3767 offset = char_offset;
3768 seg = line->segments;
3770 while (offset >= seg->char_count)
3772 offset -= seg->char_count;
3773 *line_byte_offset += seg->byte_count;
3775 g_assert (seg != NULL); /* means an invalid char offset */
3778 g_assert (seg->char_count > 0); /* indexable. */
3780 /* offset is now the number of chars into the current segment we
3781 want to go. Count bytes into the current segment. */
3783 if (seg->type == >k_text_char_type)
3785 *seg_byte_offset = 0;
3789 const char * start = seg->body.chars + *seg_byte_offset;
3791 bytes = g_utf8_next_char (start) - start;
3792 *seg_byte_offset += bytes;
3796 g_assert (*seg_byte_offset < seg->byte_count);
3798 *line_byte_offset += *seg_byte_offset;
3802 g_assert (offset == 0);
3803 *seg_byte_offset = 0;
3808 node_compare (GtkTextBTreeNode *lhs,
3809 GtkTextBTreeNode *rhs)
3811 GtkTextBTreeNode *iter;
3812 GtkTextBTreeNode *node;
3813 GtkTextBTreeNode *common_parent;
3814 GtkTextBTreeNode *parent_of_lower;
3815 GtkTextBTreeNode *parent_of_higher;
3816 gboolean lhs_is_lower;
3817 GtkTextBTreeNode *lower;
3818 GtkTextBTreeNode *higher;
3820 /* This function assumes that lhs and rhs are not underneath each
3827 if (lhs->level < rhs->level)
3829 lhs_is_lower = TRUE;
3835 lhs_is_lower = FALSE;
3840 /* Algorithm: find common parent of lhs/rhs. Save the child nodes
3841 * of the common parent we used to reach the common parent; the
3842 * ordering of these child nodes in the child list is the ordering
3846 /* Get on the same level (may be on same level already) */
3848 while (node->level < higher->level)
3849 node = node->parent;
3851 g_assert (node->level == higher->level);
3853 g_assert (node != higher); /* Happens if lower is underneath higher */
3855 /* Go up until we have two children with a common parent.
3857 parent_of_lower = node;
3858 parent_of_higher = higher;
3860 while (parent_of_lower->parent != parent_of_higher->parent)
3862 parent_of_lower = parent_of_lower->parent;
3863 parent_of_higher = parent_of_higher->parent;
3866 g_assert (parent_of_lower->parent == parent_of_higher->parent);
3868 common_parent = parent_of_lower->parent;
3870 g_assert (common_parent != NULL);
3872 /* See which is first in the list of common_parent's children */
3873 iter = common_parent->children.node;
3874 while (iter != NULL)
3876 if (iter == parent_of_higher)
3878 /* higher is less than lower */
3881 return 1; /* lhs > rhs */
3885 else if (iter == parent_of_lower)
3887 /* lower is less than higher */
3890 return -1; /* lhs < rhs */
3898 g_assert_not_reached ();
3902 /* remember that tag == NULL means "any tag" */
3904 gtk_text_line_next_could_contain_tag (GtkTextLine *line,
3908 GtkTextBTreeNode *node;
3909 GtkTextTagInfo *info;
3910 gboolean below_tag_root;
3912 g_return_val_if_fail (line != NULL, NULL);
3914 if (gtk_debug_flags & GTK_DEBUG_TEXT)
3915 gtk_text_btree_check (tree);
3919 /* Right now we can only offer linear-search if the user wants
3920 * to know about any tag toggle at all.
3922 return gtk_text_line_next (line);
3925 /* Our tag summaries only have node precision, not line
3926 precision. This means that if any line under a node could contain a
3927 tag, then any of the others could also contain a tag.
3929 In the future we could have some mechanism to keep track of how
3930 many toggles we've found under a node so far, since we have a
3931 count of toggles under the node. But for now I'm going with KISS.
3934 /* return same-node line, if any. */
3938 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3942 if (info->tag_root == NULL)
3945 if (info->tag_root == line->parent)
3946 return NULL; /* we were at the last line under the tag root */
3948 /* We need to go up out of this node, and on to the next one with
3949 toggles for the target tag. If we're below the tag root, we need to
3950 find the next node below the tag root that has tag summaries. If
3951 we're not below the tag root, we need to see if the tag root is
3952 after us in the tree, and if so, return the first line underneath
3955 node = line->parent;
3956 below_tag_root = FALSE;
3957 while (node != NULL)
3959 if (node == info->tag_root)
3961 below_tag_root = TRUE;
3965 node = node->parent;
3970 node = line->parent;
3971 while (node != info->tag_root)
3973 if (node->next == NULL)
3974 node = node->parent;
3979 if (gtk_text_btree_node_has_tag (node, tag))
3989 ordering = node_compare (line->parent, info->tag_root);
3993 /* Tag root is ahead of us, so search there. */
3994 node = info->tag_root;
3999 /* Tag root is after us, so no more lines that
4000 * could contain the tag.
4005 g_assert_not_reached ();
4010 g_assert (node != NULL);
4012 /* We have to find the first sub-node of this node that contains
4016 while (node->level > 0)
4018 g_assert (node != NULL); /* If this fails, it likely means an
4019 incorrect tag summary led us on a
4020 wild goose chase down this branch of
4022 node = node->children.node;
4023 while (node != NULL)
4025 if (gtk_text_btree_node_has_tag (node, tag))
4031 g_assert (node != NULL);
4032 g_assert (node->level == 0);
4034 return node->children.line;
4038 prev_line_under_node (GtkTextBTreeNode *node,
4043 prev = node->children.line;
4049 while (prev->next != line)
4059 gtk_text_line_previous_could_contain_tag (GtkTextLine *line,
4063 GtkTextBTreeNode *node;
4064 GtkTextBTreeNode *found_node = NULL;
4065 GtkTextTagInfo *info;
4066 gboolean below_tag_root;
4068 GtkTextBTreeNode *line_ancestor;
4069 GtkTextBTreeNode *line_ancestor_parent;
4071 /* See next_could_contain_tag () for more extensive comments
4072 * on what's going on here.
4075 g_return_val_if_fail (line != NULL, NULL);
4077 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4078 gtk_text_btree_check (tree);
4082 /* Right now we can only offer linear-search if the user wants
4083 * to know about any tag toggle at all.
4085 return gtk_text_line_previous (line);
4088 /* Return same-node line, if any. */
4089 prev = prev_line_under_node (line->parent, line);
4093 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4097 if (info->tag_root == NULL)
4100 if (info->tag_root == line->parent)
4101 return NULL; /* we were at the first line under the tag root */
4103 /* Are we below the tag root */
4104 node = line->parent;
4105 below_tag_root = FALSE;
4106 while (node != NULL)
4108 if (node == info->tag_root)
4110 below_tag_root = TRUE;
4114 node = node->parent;
4119 /* Look for a previous node under this tag root that has our
4123 /* this assertion holds because line->parent is not the
4124 * tag root, we are below the tag root, and the tag
4127 g_assert (line->parent->parent != NULL);
4129 line_ancestor = line->parent;
4130 line_ancestor_parent = line->parent->parent;
4132 node = line_ancestor_parent->children.node;
4133 while (node != line_ancestor &&
4134 line_ancestor != info->tag_root)
4136 GSList *child_nodes = NULL;
4139 /* Create reverse-order list of nodes before
4142 while (node != line_ancestor
4145 child_nodes = g_slist_prepend (child_nodes, node);
4150 /* Try to find a node with our tag on it in the list */
4154 GtkTextBTreeNode *this_node = tmp->data;
4156 g_assert (this_node != line_ancestor);
4158 if (gtk_text_btree_node_has_tag (this_node, tag))
4160 found_node = this_node;
4161 g_slist_free (child_nodes);
4165 tmp = g_slist_next (tmp);
4168 g_slist_free (child_nodes);
4170 /* Didn't find anything on this level; go up one level. */
4171 line_ancestor = line_ancestor_parent;
4172 line_ancestor_parent = line_ancestor->parent;
4174 node = line_ancestor_parent->children.node;
4184 ordering = node_compare (line->parent, info->tag_root);
4188 /* Tag root is ahead of us, so no more lines
4195 /* Tag root is after us, so grab last tagged
4196 * line underneath the tag root.
4198 found_node = info->tag_root;
4202 g_assert_not_reached ();
4207 g_assert (found_node != NULL);
4209 /* We have to find the last sub-node of this node that contains
4214 while (node->level > 0)
4216 GSList *child_nodes = NULL;
4218 g_assert (node != NULL); /* If this fails, it likely means an
4219 incorrect tag summary led us on a
4220 wild goose chase down this branch of
4223 node = node->children.node;
4224 while (node != NULL)
4226 child_nodes = g_slist_prepend (child_nodes, node);
4230 node = NULL; /* detect failure to find a child node. */
4233 while (iter != NULL)
4235 if (gtk_text_btree_node_has_tag (iter->data, tag))
4237 /* recurse into this node. */
4242 iter = g_slist_next (iter);
4245 g_slist_free (child_nodes);
4247 g_assert (node != NULL);
4250 g_assert (node != NULL);
4251 g_assert (node->level == 0);
4253 /* this assertion is correct, but slow. */
4254 /* g_assert (node_compare (node, line->parent) < 0); */
4256 /* Return last line in this node. */
4258 prev = node->children.line;
4266 * Non-public function implementations
4270 summary_list_destroy (Summary *summary)
4273 while (summary != NULL)
4275 next = summary->next;
4276 summary_destroy (summary);
4282 get_last_line (GtkTextBTree *tree)
4284 if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
4290 n_lines = gtk_text_btree_line_count (tree);
4292 g_assert (n_lines >= 1); /* num_lines doesn't return bogus last line. */
4294 line = gtk_text_btree_get_line (tree, n_lines, &real_line);
4296 tree->end_iter_line_stamp = tree->chars_changed_stamp;
4297 tree->end_iter_line = line;
4300 return tree->end_iter_line;
4308 gtk_text_line_new (void)
4312 line = g_new0(GtkTextLine, 1);
4318 gtk_text_line_destroy (GtkTextBTree *tree, GtkTextLine *line)
4320 GtkTextLineData *ld;
4321 GtkTextLineData *next;
4323 g_return_if_fail (line != NULL);
4330 view = gtk_text_btree_get_view (tree, ld->view_id);
4332 g_assert (view != NULL);
4335 gtk_text_layout_free_line_data (view->layout, line, ld);
4344 gtk_text_line_set_parent (GtkTextLine *line,
4345 GtkTextBTreeNode *node)
4347 if (line->parent == node)
4349 line->parent = node;
4350 gtk_text_btree_node_invalidate_upward (node, NULL);
4354 cleanup_line (GtkTextLine *line)
4356 GtkTextLineSegment *seg, **prev_p;
4360 * Make a pass over all of the segments in the line, giving each
4361 * a chance to clean itself up. This could potentially change
4362 * the structure of the line, e.g. by merging two segments
4363 * together or having two segments cancel themselves; if so,
4364 * then repeat the whole process again, since the first structure
4365 * change might make other structure changes possible. Repeat
4366 * until eventually there are no changes.
4373 for (prev_p = &line->segments, seg = *prev_p;
4375 prev_p = &(*prev_p)->next, seg = *prev_p)
4377 if (seg->type->cleanupFunc != NULL)
4379 *prev_p = (*seg->type->cleanupFunc)(seg, line);
4392 node_data_new (gpointer view_id)
4396 nd = g_new (NodeData, 1);
4398 nd->view_id = view_id;
4408 node_data_destroy (NodeData *nd)
4415 node_data_list_destroy (NodeData *nd)
4421 while (iter != NULL)
4424 node_data_destroy (iter);
4430 node_data_find (NodeData *nd, gpointer view_id)
4434 if (nd->view_id == view_id)
4442 summary_destroy (Summary *summary)
4444 /* Fill with error-triggering garbage */
4445 summary->info = (void*)0x1;
4446 summary->toggle_count = 567;
4447 summary->next = (void*)0x1;
4451 static GtkTextBTreeNode*
4452 gtk_text_btree_node_new (void)
4454 GtkTextBTreeNode *node;
4456 node = g_new (GtkTextBTreeNode, 1);
4458 node->node_data = NULL;
4464 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
4465 GtkTextTagInfo *info,
4470 summary = node->summary;
4471 while (summary != NULL)
4473 if (summary->info == info)
4475 summary->toggle_count += adjust;
4479 summary = summary->next;
4482 if (summary == NULL)
4484 /* didn't find a summary for our tag. */
4485 g_return_if_fail (adjust > 0);
4486 summary = g_new (Summary, 1);
4487 summary->info = info;
4488 summary->toggle_count = adjust;
4489 summary->next = node->summary;
4490 node->summary = summary;
4494 /* Note that the tag root and above do not have summaries
4495 for the tag; only nodes below the tag root have
4498 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4502 summary = node->summary;
4503 while (summary != NULL)
4506 summary->info->tag == tag)
4509 summary = summary->next;
4515 /* Add node and all children to the damage region. */
4517 gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node)
4521 nd = node->node_data;
4528 if (node->level == 0)
4532 line = node->children.line;
4533 while (line != NULL)
4535 GtkTextLineData *ld;
4549 GtkTextBTreeNode *child;
4551 child = node->children.node;
4553 while (child != NULL)
4555 gtk_text_btree_node_invalidate_downward (child);
4557 child = child->next;
4563 gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node, gpointer view_id)
4565 GtkTextBTreeNode *iter;
4568 while (iter != NULL)
4574 nd = node_data_find (iter->node_data, view_id);
4576 if (nd == NULL || !nd->valid)
4577 break; /* Once a node is invalid, we know its parents are as well. */
4583 gboolean should_continue = FALSE;
4585 nd = iter->node_data;
4590 should_continue = TRUE;
4597 if (!should_continue)
4598 break; /* This node was totally invalidated, so are its
4602 iter = iter->parent;
4608 * gtk_text_btree_is_valid:
4609 * @tree: a #GtkTextBTree
4610 * @view_id: ID for the view
4612 * Check to see if the entire #GtkTextBTree is valid or not for
4615 * Return value: %TRUE if the entire #GtkTextBTree is valid
4618 gtk_text_btree_is_valid (GtkTextBTree *tree,
4622 g_return_val_if_fail (tree != NULL, FALSE);
4624 nd = node_data_find (tree->root_node->node_data, view_id);
4625 return (nd && nd->valid);
4628 typedef struct _ValidateState ValidateState;
4630 struct _ValidateState
4632 gint remaining_pixels;
4633 gboolean in_validation;
4640 gtk_text_btree_node_validate (BTreeView *view,
4641 GtkTextBTreeNode *node,
4643 ValidateState *state)
4645 gint node_valid = TRUE;
4646 gint node_width = 0;
4647 gint node_height = 0;
4649 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4650 g_return_if_fail (!nd->valid);
4652 if (node->level == 0)
4654 GtkTextLine *line = node->children.line;
4655 GtkTextLineData *ld;
4657 /* Iterate over leading valid lines */
4658 while (line != NULL)
4660 ld = gtk_text_line_get_data (line, view_id);
4662 if (!ld || !ld->valid)
4664 else if (state->in_validation)
4666 state->in_validation = FALSE;
4671 state->y += ld->height;
4672 node_width = MAX (ld->width, node_width);
4673 node_height += ld->height;
4679 state->in_validation = TRUE;
4681 /* Iterate over invalid lines */
4682 while (line != NULL)
4684 ld = gtk_text_line_get_data (line, view_id);
4686 if (ld && ld->valid)
4691 state->old_height += ld->height;
4692 ld = gtk_text_layout_wrap (view->layout, line, ld);
4693 state->new_height += ld->height;
4695 node_width = MAX (ld->width, node_width);
4696 node_height += ld->height;
4698 state->remaining_pixels -= ld->height;
4699 if (state->remaining_pixels <= 0)
4709 /* Iterate over the remaining lines */
4710 while (line != NULL)
4712 ld = gtk_text_line_get_data (line, view_id);
4713 state->in_validation = FALSE;
4715 if (!ld || !ld->valid)
4720 node_width = MAX (ld->width, node_width);
4721 node_height += ld->height;
4729 GtkTextBTreeNode *child;
4732 child = node->children.node;
4734 /* Iterate over leading valid nodes */
4737 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4739 if (!child_nd->valid)
4741 else if (state->in_validation)
4743 state->in_validation = FALSE;
4748 state->y += child_nd->height;
4749 node_width = MAX (node_width, child_nd->width);
4750 node_height += child_nd->height;
4753 child = child->next;
4756 /* Iterate over invalid nodes */
4759 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4761 if (child_nd->valid)
4765 gtk_text_btree_node_validate (view, child, view_id, state);
4767 if (!child_nd->valid)
4769 node_width = MAX (node_width, child_nd->width);
4770 node_height += child_nd->height;
4772 if (!state->in_validation || state->remaining_pixels <= 0)
4774 child = child->next;
4779 child = child->next;
4782 /* Iterate over the remaining lines */
4785 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4786 state->in_validation = FALSE;
4788 if (!child_nd->valid)
4791 node_width = MAX (child_nd->width, node_width);
4792 node_height += child_nd->height;
4794 child = child->next;
4798 nd->width = node_width;
4799 nd->height = node_height;
4800 nd->valid = node_valid;
4804 * gtk_text_btree_validate:
4805 * @tree: a #GtkTextBTree
4807 * @max_pixels: the maximum number of pixels to validate. (No more
4808 * than one paragraph beyond this limit will be validated)
4809 * @y: location to store starting y coordinate of validated region
4810 * @old_height: location to store old height of validated region
4811 * @new_height: location to store new height of validated region
4813 * Validate a single contiguous invalid region of a #GtkTextBTree for
4816 * Return value: %TRUE if a region has been validated, %FALSE if the
4817 * entire tree was already valid.
4820 gtk_text_btree_validate (GtkTextBTree *tree,
4829 g_return_val_if_fail (tree != NULL, FALSE);
4831 view = gtk_text_btree_get_view (tree, view_id);
4832 g_return_val_if_fail (view != NULL, FALSE);
4834 if (!gtk_text_btree_is_valid (tree, view_id))
4836 ValidateState state;
4838 state.remaining_pixels = max_pixels;
4839 state.in_validation = FALSE;
4841 state.old_height = 0;
4842 state.new_height = 0;
4844 gtk_text_btree_node_validate (view,
4851 *old_height = state.old_height;
4853 *new_height = state.new_height;
4855 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4856 gtk_text_btree_check (tree);
4865 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
4869 gboolean *valid_out)
4873 gboolean valid = TRUE;
4875 if (node->level == 0)
4877 GtkTextLine *line = node->children.line;
4879 while (line != NULL)
4881 GtkTextLineData *ld = gtk_text_line_get_data (line, view_id);
4883 if (!ld || !ld->valid)
4888 width = MAX (ld->width, width);
4889 height += ld->height;
4897 GtkTextBTreeNode *child = node->children.node;
4901 NodeData *child_nd = node_data_find (child->node_data, view_id);
4903 if (!child_nd || !child_nd->valid)
4908 width = MAX (child_nd->width, width);
4909 height += child_nd->height;
4912 child = child->next;
4917 *height_out = height;
4922 /* Recompute the validity and size of the view data for a given
4923 * view at this node from the immediate children of the node
4926 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
4929 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4934 gtk_text_btree_node_compute_view_aggregates (node, view_id,
4935 &width, &height, &valid);
4937 nd->height = height;
4944 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
4949 gtk_text_btree_node_check_valid (node, view_id);
4950 node = node->parent;
4955 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
4958 if (node->level == 0)
4960 return gtk_text_btree_node_check_valid (node, view_id);
4964 GtkTextBTreeNode *child = node->children.node;
4966 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4974 NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
4976 if (!child_nd->valid)
4978 nd->width = MAX (child_nd->width, nd->width);
4979 nd->height += child_nd->height;
4981 child = child->next;
4990 * gtk_text_btree_validate_line:
4991 * @tree: a #GtkTextBTree
4992 * @line: line to validate
4993 * @view_id: view ID for the view to validate
4995 * Revalidate a single line of the btree for the given view, propagate
4996 * results up through the entire tree.
4999 gtk_text_btree_validate_line (GtkTextBTree *tree,
5003 GtkTextLineData *ld;
5004 GtkTextLine *last_line;
5007 g_return_if_fail (tree != NULL);
5008 g_return_if_fail (line != NULL);
5010 view = gtk_text_btree_get_view (tree, view_id);
5011 g_return_if_fail (view != NULL);
5013 ld = gtk_text_line_get_data (line, view_id);
5014 if (!ld || !ld->valid)
5016 ld = gtk_text_layout_wrap (view->layout, line, ld);
5017 last_line = get_last_line (tree);
5019 gtk_text_btree_node_check_valid_upward (line->parent, view_id);
5024 gtk_text_btree_node_remove_view (BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
5026 if (node->level == 0)
5030 line = node->children.line;
5031 while (line != NULL)
5033 GtkTextLineData *ld;
5035 ld = gtk_text_line_remove_data (line, view_id);
5038 gtk_text_layout_free_line_data (view->layout, line, ld);
5045 GtkTextBTreeNode *child;
5047 child = node->children.node;
5049 while (child != NULL)
5052 gtk_text_btree_node_remove_view (view, child, view_id);
5054 child = child->next;
5058 gtk_text_btree_node_remove_data (node, view_id);
5062 gtk_text_btree_node_destroy (GtkTextBTree *tree, GtkTextBTreeNode *node)
5064 if (node->level == 0)
5067 GtkTextLineSegment *seg;
5069 while (node->children.line != NULL)
5071 line = node->children.line;
5072 node->children.line = line->next;
5073 while (line->segments != NULL)
5075 seg = line->segments;
5076 line->segments = seg->next;
5078 if (GTK_IS_TEXT_MARK_SEGMENT (seg))
5080 /* Set the mark as deleted */
5081 seg->body.mark.tree = NULL;
5082 seg->body.mark.line = NULL;
5085 (*seg->type->deleteFunc) (seg, line, 1);
5087 gtk_text_line_destroy (tree, line);
5092 GtkTextBTreeNode *childPtr;
5094 while (node->children.node != NULL)
5096 childPtr = node->children.node;
5097 node->children.node = childPtr->next;
5098 gtk_text_btree_node_destroy (tree, childPtr);
5102 summary_list_destroy (node->summary);
5103 node_data_list_destroy (node->node_data);
5108 gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node, gpointer view_id)
5112 nd = node->node_data;
5115 if (nd->view_id == view_id)
5122 nd = node_data_new (view_id);
5124 if (node->node_data)
5125 nd->next = node->node_data;
5127 node->node_data = nd;
5134 gtk_text_btree_node_remove_data (GtkTextBTreeNode *node, gpointer view_id)
5140 nd = node->node_data;
5143 if (nd->view_id == view_id)
5154 prev->next = nd->next;
5156 if (node->node_data == nd)
5157 node->node_data = nd->next;
5161 node_data_destroy (nd);
5165 gtk_text_btree_node_get_size (GtkTextBTreeNode *node, gpointer view_id,
5166 gint *width, gint *height)
5170 g_return_if_fail (width != NULL);
5171 g_return_if_fail (height != NULL);
5173 nd = gtk_text_btree_node_ensure_data (node, view_id);
5178 *height = nd->height;
5181 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5182 * here isn't quite right, since for a lot of operations we want to
5183 * know which children of the common parent correspond to the two nodes
5184 * (e.g., when computing the order of two iters)
5186 static GtkTextBTreeNode *
5187 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5188 GtkTextBTreeNode *node2)
5190 while (node1->level < node2->level)
5191 node1 = node1->parent;
5192 while (node2->level < node1->level)
5193 node2 = node2->parent;
5194 while (node1 != node2)
5196 node1 = node1->parent;
5197 node2 = node2->parent;
5208 gtk_text_btree_get_view (GtkTextBTree *tree, gpointer view_id)
5213 while (view != NULL)
5215 if (view->view_id == view_id)
5224 get_tree_bounds (GtkTextBTree *tree,
5228 gtk_text_btree_get_iter_at_line_char (tree, start, 0, 0);
5229 gtk_text_btree_get_last_iter (tree, end);
5233 tag_changed_cb (GtkTextTagTable *table,
5235 gboolean size_changed,
5240 /* We need to queue a relayout on all regions that are tagged with
5247 if (gtk_text_btree_get_iter_at_first_toggle (tree, &start, tag))
5249 /* Must be a last toggle if there was a first one. */
5250 gtk_text_btree_get_iter_at_last_toggle (tree, &end, tag);
5251 gtk_text_btree_invalidate_region (tree,
5258 /* We only need to queue a redraw, not a relayout */
5263 while (view != NULL)
5267 gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5268 gtk_text_layout_changed (view->layout, 0, height, height);
5276 tag_removed_cb (GtkTextTagTable *table,
5280 /* Remove the tag from the tree */
5285 get_tree_bounds (tree, &start, &end);
5287 gtk_text_btree_tag (&start, &end, tag, FALSE);
5288 gtk_text_btree_remove_tag_info (tree, tag);
5292 /* Rebalance the out-of-whack node "node" */
5294 gtk_text_btree_rebalance (GtkTextBTree *tree,
5295 GtkTextBTreeNode *node)
5298 * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5299 * up through the tree one GtkTextBTreeNode at a time until the root
5300 * GtkTextBTreeNode has been processed.
5303 while (node != NULL)
5305 GtkTextBTreeNode *new_node, *child;
5310 * Check to see if the GtkTextBTreeNode has too many children. If it does,
5311 * then split off all but the first MIN_CHILDREN into a separate
5312 * GtkTextBTreeNode following the original one. Then repeat until the
5313 * GtkTextBTreeNode has a decent size.
5316 if (node->num_children > MAX_CHILDREN)
5321 * If the GtkTextBTreeNode being split is the root
5322 * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5326 if (node->parent == NULL)
5328 new_node = gtk_text_btree_node_new ();
5329 new_node->parent = NULL;
5330 new_node->next = NULL;
5331 new_node->summary = NULL;
5332 new_node->level = node->level + 1;
5333 new_node->children.node = node;
5334 recompute_node_counts (tree, new_node);
5335 tree->root_node = new_node;
5337 new_node = gtk_text_btree_node_new ();
5338 new_node->parent = node->parent;
5339 new_node->next = node->next;
5340 node->next = new_node;
5341 new_node->summary = NULL;
5342 new_node->level = node->level;
5343 new_node->num_children = node->num_children - MIN_CHILDREN;
5344 if (node->level == 0)
5346 for (i = MIN_CHILDREN-1,
5347 line = node->children.line;
5348 i > 0; i--, line = line->next)
5350 /* Empty loop body. */
5352 new_node->children.line = line->next;
5357 for (i = MIN_CHILDREN-1,
5358 child = node->children.node;
5359 i > 0; i--, child = child->next)
5361 /* Empty loop body. */
5363 new_node->children.node = child->next;
5366 recompute_node_counts (tree, node);
5367 node->parent->num_children++;
5369 if (node->num_children <= MAX_CHILDREN)
5371 recompute_node_counts (tree, node);
5377 while (node->num_children < MIN_CHILDREN)
5379 GtkTextBTreeNode *other;
5380 GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5381 GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5382 int total_children, first_children, i;
5385 * Too few children for this GtkTextBTreeNode. If this is the root then,
5386 * it's OK for it to have less than MIN_CHILDREN children
5387 * as long as it's got at least two. If it has only one
5388 * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5389 * the tree and use its child as the new root.
5392 if (node->parent == NULL)
5394 if ((node->num_children == 1) && (node->level > 0))
5396 tree->root_node = node->children.node;
5397 tree->root_node->parent = NULL;
5398 summary_list_destroy (node->summary);
5405 * Not the root. Make sure that there are siblings to
5409 if (node->parent->num_children < 2)
5411 gtk_text_btree_rebalance (tree, node->parent);
5416 * Find a sibling neighbor to borrow from, and arrange for
5417 * node to be the earlier of the pair.
5420 if (node->next == NULL)
5422 for (other = node->parent->children.node;
5423 other->next != node;
5424 other = other->next)
5426 /* Empty loop body. */
5433 * We're going to either merge the two siblings together
5434 * into one GtkTextBTreeNode or redivide the children among them to
5435 * balance their loads. As preparation, join their two
5436 * child lists into a single list and remember the half-way
5437 * point in the list.
5440 total_children = node->num_children + other->num_children;
5441 first_children = total_children/2;
5442 if (node->children.node == NULL)
5444 node->children = other->children;
5445 other->children.node = NULL;
5446 other->children.line = NULL;
5448 if (node->level == 0)
5452 for (line = node->children.line, i = 1;
5454 line = line->next, i++)
5456 if (i == first_children)
5461 line->next = other->children.line;
5462 while (i <= first_children)
5471 GtkTextBTreeNode *child;
5473 for (child = node->children.node, i = 1;
5474 child->next != NULL;
5475 child = child->next, i++)
5477 if (i <= first_children)
5479 if (i == first_children)
5481 halfwaynode = child;
5485 child->next = other->children.node;
5486 while (i <= first_children)
5488 halfwaynode = child;
5489 child = child->next;
5495 * If the two siblings can simply be merged together, do it.
5498 if (total_children <= MAX_CHILDREN)
5500 recompute_node_counts (tree, node);
5501 node->next = other->next;
5502 node->parent->num_children--;
5503 summary_list_destroy (other->summary);
5509 * The siblings can't be merged, so just divide their
5510 * children evenly between them.
5513 if (node->level == 0)
5515 other->children.line = halfwayline->next;
5516 halfwayline->next = NULL;
5520 other->children.node = halfwaynode->next;
5521 halfwaynode->next = NULL;
5524 recompute_node_counts (tree, node);
5525 recompute_node_counts (tree, other);
5528 node = node->parent;
5533 post_insert_fixup (GtkTextBTree *tree,
5535 gint line_count_delta,
5536 gint char_count_delta)
5539 GtkTextBTreeNode *node;
5542 * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5543 * point, then rebalance the tree if necessary.
5546 for (node = line->parent ; node != NULL;
5547 node = node->parent)
5549 node->num_lines += line_count_delta;
5550 node->num_chars += char_count_delta;
5552 node = line->parent;
5553 node->num_children += line_count_delta;
5555 if (node->num_children > MAX_CHILDREN)
5557 gtk_text_btree_rebalance (tree, node);
5560 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5561 gtk_text_btree_check (tree);
5564 static GtkTextTagInfo*
5565 gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
5568 GtkTextTagInfo *info;
5572 list = tree->tag_infos;
5573 while (list != NULL)
5576 if (info->tag == tag)
5579 list = g_slist_next (list);
5585 static GtkTextTagInfo*
5586 gtk_text_btree_get_tag_info (GtkTextBTree *tree,
5589 GtkTextTagInfo *info;
5591 info = gtk_text_btree_get_existing_tag_info (tree, tag);
5595 /* didn't find it, create. */
5597 info = g_new (GtkTextTagInfo, 1);
5600 gtk_object_ref (GTK_OBJECT (tag));
5601 info->tag_root = NULL;
5602 info->toggle_count = 0;
5604 tree->tag_infos = g_slist_prepend (tree->tag_infos, info);
5611 gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
5614 GtkTextTagInfo *info;
5619 list = tree->tag_infos;
5620 while (list != NULL)
5623 if (info->tag == tag)
5627 prev->next = list->next;
5631 tree->tag_infos = list->next;
5634 g_slist_free (list);
5636 gtk_object_unref (GTK_OBJECT (info->tag));
5642 list = g_slist_next (list);
5645 g_assert_not_reached ();
5650 recompute_level_zero_counts (GtkTextBTreeNode *node)
5653 GtkTextLineSegment *seg;
5655 g_assert (node->level == 0);
5657 line = node->children.line;
5658 while (line != NULL)
5660 node->num_children++;
5663 if (line->parent != node)
5664 gtk_text_line_set_parent (line, node);
5666 seg = line->segments;
5670 node->num_chars += seg->char_count;
5672 if (((seg->type != >k_text_toggle_on_type)
5673 && (seg->type != >k_text_toggle_off_type))
5674 || !(seg->body.toggle.inNodeCounts))
5680 GtkTextTagInfo *info;
5682 info = seg->body.toggle.info;
5684 gtk_text_btree_node_adjust_toggle_count (node, info, 1);
5695 recompute_level_nonzero_counts (GtkTextBTreeNode *node)
5698 GtkTextBTreeNode *child;
5700 g_assert (node->level > 0);
5702 child = node->children.node;
5703 while (child != NULL)
5705 node->num_children += 1;
5706 node->num_lines += child->num_lines;
5707 node->num_chars += child->num_chars;
5709 if (child->parent != node)
5711 child->parent = node;
5712 gtk_text_btree_node_invalidate_upward (node, NULL);
5715 summary = child->summary;
5716 while (summary != NULL)
5718 gtk_text_btree_node_adjust_toggle_count (node,
5720 summary->toggle_count);
5722 summary = summary->next;
5725 child = child->next;
5730 *----------------------------------------------------------------------
5732 * recompute_node_counts --
5734 * This procedure is called to recompute all the counts in a GtkTextBTreeNode
5735 * (tags, child information, etc.) by scanning the information in
5736 * its descendants. This procedure is called during rebalancing
5737 * when a GtkTextBTreeNode's child structure has changed.
5743 * The tag counts for node are modified to reflect its current
5744 * child structure, as are its num_children, num_lines, num_chars fields.
5745 * Also, all of the childrens' parent fields are made to point
5748 *----------------------------------------------------------------------
5752 recompute_node_counts (GtkTextBTree *tree, GtkTextBTreeNode *node)
5755 Summary *summary, *summary2;
5758 * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
5759 * the existing Summary records (most of them will probably be reused).
5762 summary = node->summary;
5763 while (summary != NULL)
5765 summary->toggle_count = 0;
5766 summary = summary->next;
5769 node->num_children = 0;
5770 node->num_lines = 0;
5771 node->num_chars = 0;
5774 * Scan through the children, adding the childrens' tag counts into
5775 * the GtkTextBTreeNode's tag counts and adding new Summary structures if
5779 if (node->level == 0)
5780 recompute_level_zero_counts (node);
5782 recompute_level_nonzero_counts (node);
5787 gtk_text_btree_node_check_valid (node, view->view_id);
5792 * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
5793 * records that still have a zero count, or that have all the toggles.
5794 * The GtkTextBTreeNode with the children that account for all the tags toggles
5795 * have no summary information, and they become the tag_root for the tag.
5799 for (summary = node->summary; summary != NULL; )
5801 if (summary->toggle_count > 0 &&
5802 summary->toggle_count < summary->info->toggle_count)
5804 if (node->level == summary->info->tag_root->level)
5807 * The tag's root GtkTextBTreeNode split and some toggles left.
5808 * The tag root must move up a level.
5810 summary->info->tag_root = node->parent;
5813 summary = summary->next;
5816 if (summary->toggle_count == summary->info->toggle_count)
5819 * A GtkTextBTreeNode merge has collected all the toggles under
5820 * one GtkTextBTreeNode. Push the root down to this level.
5822 summary->info->tag_root = node;
5824 if (summary2 != NULL)
5826 summary2->next = summary->next;
5827 summary_destroy (summary);
5828 summary = summary2->next;
5832 node->summary = summary->next;
5833 summary_destroy (summary);
5834 summary = node->summary;
5840 _gtk_change_node_toggle_count (GtkTextBTreeNode *node,
5841 GtkTextTagInfo *info,
5842 gint delta) /* may be negative */
5844 Summary *summary, *prevPtr;
5845 GtkTextBTreeNode *node2Ptr;
5846 int rootLevel; /* Level of original tag root */
5848 info->toggle_count += delta;
5850 if (info->tag_root == (GtkTextBTreeNode *) NULL)
5852 info->tag_root = node;
5857 * Note the level of the existing root for the tag so we can detect
5858 * if it needs to be moved because of the toggle count change.
5861 rootLevel = info->tag_root->level;
5864 * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
5865 * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
5869 for ( ; node != info->tag_root; node = node->parent)
5872 * See if there's already an entry for this tag for this GtkTextBTreeNode. If so,
5873 * perhaps all we have to do is adjust its count.
5876 for (prevPtr = NULL, summary = node->summary;
5878 prevPtr = summary, summary = summary->next)
5880 if (summary->info == info)
5885 if (summary != NULL)
5887 summary->toggle_count += delta;
5888 if (summary->toggle_count > 0 &&
5889 summary->toggle_count < info->toggle_count)
5893 if (summary->toggle_count != 0)
5896 * Should never find a GtkTextBTreeNode with max toggle count at this
5897 * point (there shouldn't have been a summary entry in the
5901 g_error ("%s: bad toggle count (%d) max (%d)",
5902 G_STRLOC, summary->toggle_count, info->toggle_count);
5906 * Zero toggle count; must remove this tag from the list.
5909 if (prevPtr == NULL)
5911 node->summary = summary->next;
5915 prevPtr->next = summary->next;
5917 summary_destroy (summary);
5922 * This tag isn't currently in the summary information list.
5925 if (rootLevel == node->level)
5929 * The old tag root is at the same level in the tree as this
5930 * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode. Move the tag root up
5931 * a level, in the hopes that it will now cover this GtkTextBTreeNode
5932 * as well as the old root (if not, we'll move it up again
5933 * the next time through the loop). To push it up one level
5934 * we copy the original toggle count into the summary
5935 * information at the old root and change the root to its
5936 * parent GtkTextBTreeNode.
5939 GtkTextBTreeNode *rootnode = info->tag_root;
5940 summary = (Summary *) g_malloc (sizeof (Summary));
5941 summary->info = info;
5942 summary->toggle_count = info->toggle_count - delta;
5943 summary->next = rootnode->summary;
5944 rootnode->summary = summary;
5945 rootnode = rootnode->parent;
5946 rootLevel = rootnode->level;
5947 info->tag_root = rootnode;
5949 summary = (Summary *) g_malloc (sizeof (Summary));
5950 summary->info = info;
5951 summary->toggle_count = delta;
5952 summary->next = node->summary;
5953 node->summary = summary;
5958 * If we've decremented the toggle count, then it may be necessary
5959 * to push the tag root down one or more levels.
5966 if (info->toggle_count == 0)
5968 info->tag_root = (GtkTextBTreeNode *) NULL;
5971 node = info->tag_root;
5972 while (node->level > 0)
5975 * See if a single child GtkTextBTreeNode accounts for all of the tag's
5976 * toggles. If so, push the root down one level.
5979 for (node2Ptr = node->children.node;
5980 node2Ptr != (GtkTextBTreeNode *)NULL ;
5981 node2Ptr = node2Ptr->next)
5983 for (prevPtr = NULL, summary = node2Ptr->summary;
5985 prevPtr = summary, summary = summary->next)
5987 if (summary->info == info)
5992 if (summary == NULL)
5996 if (summary->toggle_count != info->toggle_count)
5999 * No GtkTextBTreeNode has all toggles, so the root is still valid.
6006 * This GtkTextBTreeNode has all the toggles, so push down the root.
6009 if (prevPtr == NULL)
6011 node2Ptr->summary = summary->next;
6015 prevPtr->next = summary->next;
6017 summary_destroy (summary);
6018 info->tag_root = node2Ptr;
6021 node = info->tag_root;
6026 *----------------------------------------------------------------------
6030 * This is a utility procedure used by gtk_text_btree_get_tags. It
6031 * increments the count for a particular tag, adding a new
6032 * entry for that tag if there wasn't one previously.
6038 * The information at *tagInfoPtr may be modified, and the arrays
6039 * may be reallocated to make them larger.
6041 *----------------------------------------------------------------------
6045 inc_count (GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
6050 for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
6051 count > 0; tag_p++, count--)
6055 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
6061 * There isn't currently an entry for this tag, so we have to
6062 * make a new one. If the arrays are full, then enlarge the
6066 if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
6068 GtkTextTag **newTags;
6069 int *newCounts, newSize;
6071 newSize = 2*tagInfoPtr->arraySize;
6072 newTags = (GtkTextTag **) g_malloc ((unsigned)
6073 (newSize*sizeof (GtkTextTag *)));
6074 memcpy ((void *) newTags, (void *) tagInfoPtr->tags,
6075 tagInfoPtr->arraySize *sizeof (GtkTextTag *));
6076 g_free ((char *) tagInfoPtr->tags);
6077 tagInfoPtr->tags = newTags;
6078 newCounts = (int *) g_malloc ((unsigned) (newSize*sizeof (int)));
6079 memcpy ((void *) newCounts, (void *) tagInfoPtr->counts,
6080 tagInfoPtr->arraySize *sizeof (int));
6081 g_free ((char *) tagInfoPtr->counts);
6082 tagInfoPtr->counts = newCounts;
6083 tagInfoPtr->arraySize = newSize;
6086 tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
6087 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
6088 tagInfoPtr->numTags++;
6092 gtk_text_btree_link_segment (GtkTextLineSegment *seg,
6093 const GtkTextIter *iter)
6095 GtkTextLineSegment *prev;
6099 line = gtk_text_iter_get_text_line (iter);
6100 tree = gtk_text_iter_get_btree (iter);
6102 prev = gtk_text_line_segment_split (iter);
6105 seg->next = line->segments;
6106 line->segments = seg;
6110 seg->next = prev->next;
6113 cleanup_line (line);
6114 segments_changed (tree);
6116 if (gtk_debug_flags & GTK_DEBUG_TEXT)
6117 gtk_text_btree_check (tree);
6121 gtk_text_btree_unlink_segment (GtkTextBTree *tree,
6122 GtkTextLineSegment *seg,
6125 GtkTextLineSegment *prev;
6127 if (line->segments == seg)
6129 line->segments = seg->next;
6133 for (prev = line->segments; prev->next != seg;
6136 /* Empty loop body. */
6138 prev->next = seg->next;
6140 cleanup_line (line);
6141 segments_changed (tree);
6145 * This is here because it requires BTree internals, it logically
6146 * belongs in gtktextsegment.c
6151 *--------------------------------------------------------------
6153 * _gtk_toggle_segment_check_func --
6155 * This procedure is invoked to perform consistency checks
6156 * on toggle segments.
6162 * If a consistency problem is found the procedure g_errors.
6164 *--------------------------------------------------------------
6168 _gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6174 if (segPtr->byte_count != 0)
6176 g_error ("toggle_segment_check_func: segment had non-zero size");
6178 if (!segPtr->body.toggle.inNodeCounts)
6180 g_error ("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6182 needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6183 for (summary = line->parent->summary; ;
6184 summary = summary->next)
6186 if (summary == NULL)
6190 g_error ("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6197 if (summary->info == segPtr->body.toggle.info)
6201 g_error ("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6213 gtk_text_btree_node_view_check_consistency (GtkTextBTreeNode *node,
6220 gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6221 &width, &height, &valid);
6222 if (nd->width != width ||
6223 nd->height != height ||
6224 !nd->valid != !valid)
6226 g_error ("Node aggregates for view %p are invalid:\n"
6227 "Are (%d,%d,%s), should be (%d,%d,%s)",
6229 nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6230 width, height, valid ? "TRUE" : "FALSE");
6235 gtk_text_btree_node_check_consistency (GtkTextBTreeNode *node)
6237 GtkTextBTreeNode *childnode;
6238 Summary *summary, *summary2;
6240 GtkTextLineSegment *segPtr;
6241 int num_children, num_lines, num_chars, toggle_count, min_children;
6242 GtkTextLineData *ld;
6245 if (node->parent != NULL)
6247 min_children = MIN_CHILDREN;
6249 else if (node->level > 0)
6256 if ((node->num_children < min_children)
6257 || (node->num_children > MAX_CHILDREN))
6259 g_error ("gtk_text_btree_node_check_consistency: bad child count (%d)",
6260 node->num_children);
6263 nd = node->node_data;
6266 gtk_text_btree_node_view_check_consistency (node, nd);
6273 if (node->level == 0)
6275 for (line = node->children.line; line != NULL;
6278 if (line->parent != node)
6280 g_error ("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6282 if (line->segments == NULL)
6284 g_error ("gtk_text_btree_node_check_consistency: line has no segments");
6290 /* Just ensuring we don't segv while doing this loop */
6295 for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6297 if (segPtr->type->checkFunc != NULL)
6299 (*segPtr->type->checkFunc)(segPtr, line);
6301 if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6302 && (segPtr->next != NULL)
6303 && (segPtr->next->byte_count == 0)
6304 && (segPtr->next->type->leftGravity))
6306 g_error ("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6308 if ((segPtr->next == NULL)
6309 && (segPtr->type != >k_text_char_type))
6311 g_error ("gtk_text_btree_node_check_consistency: line ended with wrong type");
6314 num_chars += segPtr->char_count;
6323 for (childnode = node->children.node; childnode != NULL;
6324 childnode = childnode->next)
6326 if (childnode->parent != node)
6328 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6330 if (childnode->level != (node->level-1))
6332 g_error ("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6333 node->level, childnode->level);
6335 gtk_text_btree_node_check_consistency (childnode);
6336 for (summary = childnode->summary; summary != NULL;
6337 summary = summary->next)
6339 for (summary2 = node->summary; ;
6340 summary2 = summary2->next)
6342 if (summary2 == NULL)
6344 if (summary->info->tag_root == node)
6348 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6349 summary->info->tag->name,
6350 "present in parent summaries");
6352 if (summary->info == summary2->info)
6359 num_lines += childnode->num_lines;
6360 num_chars += childnode->num_chars;
6363 if (num_children != node->num_children)
6365 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6366 num_children, node->num_children);
6368 if (num_lines != node->num_lines)
6370 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6371 num_lines, node->num_lines);
6373 if (num_chars != node->num_chars)
6375 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6376 num_chars, node->num_chars);
6379 for (summary = node->summary; summary != NULL;
6380 summary = summary->next)
6382 if (summary->info->toggle_count == summary->toggle_count)
6384 g_error ("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6385 summary->info->tag->name);
6388 if (node->level == 0)
6390 for (line = node->children.line; line != NULL;
6393 for (segPtr = line->segments; segPtr != NULL;
6394 segPtr = segPtr->next)
6396 if ((segPtr->type != >k_text_toggle_on_type)
6397 && (segPtr->type != >k_text_toggle_off_type))
6401 if (segPtr->body.toggle.info == summary->info)
6403 if (!segPtr->body.toggle.inNodeCounts)
6404 g_error ("Toggle segment not in the node counts");
6413 for (childnode = node->children.node;
6415 childnode = childnode->next)
6417 for (summary2 = childnode->summary;
6419 summary2 = summary2->next)
6421 if (summary2->info == summary->info)
6423 toggle_count += summary2->toggle_count;
6428 if (toggle_count != summary->toggle_count)
6430 g_error ("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6431 toggle_count, summary->toggle_count);
6433 for (summary2 = summary->next; summary2 != NULL;
6434 summary2 = summary2->next)
6436 if (summary2->info == summary->info)
6438 g_error ("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6439 summary->info->tag->name);
6446 listify_foreach (GtkTextTag *tag, gpointer user_data)
6448 GSList** listp = user_data;
6450 *listp = g_slist_prepend (*listp, tag);
6454 list_of_tags (GtkTextTagTable *table)
6456 GSList *list = NULL;
6458 gtk_text_tag_table_foreach (table, listify_foreach, &list);
6464 gtk_text_btree_check (GtkTextBTree *tree)
6467 GtkTextBTreeNode *node;
6469 GtkTextLineSegment *seg;
6471 GSList *taglist = NULL;
6473 GtkTextTagInfo *info;
6476 * Make sure that the tag toggle counts and the tag root pointers are OK.
6478 for (taglist = list_of_tags (tree->table);
6479 taglist != NULL ; taglist = taglist->next)
6481 tag = taglist->data;
6482 info = gtk_text_btree_get_existing_tag_info (tree, tag);
6485 node = info->tag_root;
6488 if (info->toggle_count != 0)
6490 g_error ("gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6491 tag->name, info->toggle_count);
6493 continue; /* no ranges for the tag */
6495 else if (info->toggle_count == 0)
6497 g_error ("gtk_text_btree_check found root for \"%s\" with no toggles",
6500 else if (info->toggle_count & 1)
6502 g_error ("gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6503 tag->name, info->toggle_count);
6505 for (summary = node->summary; summary != NULL;
6506 summary = summary->next)
6508 if (summary->info->tag == tag)
6510 g_error ("gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6514 if (node->level > 0)
6516 for (node = node->children.node ; node != NULL ;
6519 for (summary = node->summary; summary != NULL;
6520 summary = summary->next)
6522 if (summary->info->tag == tag)
6524 count += summary->toggle_count;
6531 GtkTextLineSegmentClass * last = NULL;
6533 for (line = node->children.line ; line != NULL ;
6536 for (seg = line->segments; seg != NULL;
6539 if ((seg->type == >k_text_toggle_on_type ||
6540 seg->type == >k_text_toggle_off_type) &&
6541 seg->body.toggle.info->tag == tag)
6543 if (last == seg->type)
6544 g_error ("Two consecutive toggles on or off weren't merged");
6545 if (!seg->body.toggle.inNodeCounts)
6546 g_error ("Toggle segment not in the node counts");
6555 if (count != info->toggle_count)
6557 g_error ("gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
6558 info->toggle_count, tag->name, count);
6563 g_slist_free (taglist);
6567 * Call a recursive procedure to do the main body of checks.
6570 node = tree->root_node;
6571 gtk_text_btree_node_check_consistency (tree->root_node);
6574 * Make sure that there are at least two lines in the text and
6575 * that the last line has no characters except a newline.
6578 if (node->num_lines < 2)
6580 g_error ("gtk_text_btree_check: less than 2 lines in tree");
6582 if (node->num_chars < 2)
6584 g_error ("gtk_text_btree_check: less than 2 chars in tree");
6586 while (node->level > 0)
6588 node = node->children.node;
6589 while (node->next != NULL)
6594 line = node->children.line;
6595 while (line->next != NULL)
6599 seg = line->segments;
6600 while ((seg->type == >k_text_toggle_off_type)
6601 || (seg->type == >k_text_right_mark_type)
6602 || (seg->type == >k_text_left_mark_type))
6605 * It's OK to toggle a tag off in the last line, but
6606 * not to start a new range. It's also OK to have marks
6612 if (seg->type != >k_text_char_type)
6614 g_error ("gtk_text_btree_check: last line has bogus segment type");
6616 if (seg->next != NULL)
6618 g_error ("gtk_text_btree_check: last line has too many segments");
6620 if (seg->byte_count != 1)
6622 g_error ("gtk_text_btree_check: last line has wrong # characters: %d",
6625 if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
6627 g_error ("gtk_text_btree_check: last line had bad value: %s",
6632 void gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line);
6633 void gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment* seg);
6634 void gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent);
6635 void gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
6638 gtk_text_btree_spew (GtkTextBTree *tree)
6643 printf ("%d lines in tree %p\n",
6644 gtk_text_btree_line_count (tree), tree);
6646 line = gtk_text_btree_get_line (tree, 0, &real_line);
6648 while (line != NULL)
6650 gtk_text_btree_spew_line (tree, line);
6651 line = gtk_text_line_next (line);
6654 printf ("=================== Tag information\n");
6659 list = tree->tag_infos;
6661 while (list != NULL)
6663 GtkTextTagInfo *info;
6667 printf (" tag `%s': root at %p, toggle count %d\n",
6668 info->tag->name, info->tag_root, info->toggle_count);
6670 list = g_slist_next (list);
6673 if (tree->tag_infos == NULL)
6675 printf (" (no tags in the tree)\n");
6679 printf ("=================== Tree nodes\n");
6682 gtk_text_btree_spew_node (tree->root_node, 0);
6687 gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
6690 GtkTextLineSegment *seg;
6692 spaces = g_strnfill (indent, ' ');
6694 printf ("%sline %p chars %d bytes %d\n",
6696 gtk_text_line_char_count (line),
6697 gtk_text_line_byte_count (line));
6699 seg = line->segments;
6702 if (seg->type == >k_text_char_type)
6704 gchar* str = g_strndup (seg->body.chars, MIN (seg->byte_count, 10));
6709 if (*s == '\n' || *s == '\r')
6713 printf ("%s chars `%s'...\n", spaces, str);
6716 else if (seg->type == >k_text_right_mark_type)
6718 printf ("%s right mark `%s' visible: %d\n",
6720 seg->body.mark.name,
6721 seg->body.mark.visible);
6723 else if (seg->type == >k_text_left_mark_type)
6725 printf ("%s left mark `%s' visible: %d\n",
6727 seg->body.mark.name,
6728 seg->body.mark.visible);
6730 else if (seg->type == >k_text_toggle_on_type ||
6731 seg->type == >k_text_toggle_off_type)
6733 printf ("%s tag `%s' %s\n",
6734 spaces, seg->body.toggle.info->tag->name,
6735 seg->type == >k_text_toggle_off_type ? "off" : "on");
6745 gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent)
6748 GtkTextBTreeNode *iter;
6751 spaces = g_strnfill (indent, ' ');
6753 printf ("%snode %p level %d children %d lines %d chars %d\n",
6754 spaces, node, node->level,
6755 node->num_children, node->num_lines, node->num_chars);
6760 printf ("%s %d toggles of `%s' below this node\n",
6761 spaces, s->toggle_count, s->info->tag->name);
6767 if (node->level > 0)
6769 iter = node->children.node;
6770 while (iter != NULL)
6772 gtk_text_btree_spew_node (iter, indent + 2);
6779 GtkTextLine *line = node->children.line;
6780 while (line != NULL)
6782 gtk_text_btree_spew_line_short (line, indent + 2);
6790 gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line)
6792 GtkTextLineSegment * seg;
6794 printf ("%4d| line: %p parent: %p next: %p\n",
6795 gtk_text_line_get_number (line), line, line->parent, line->next);
6797 seg = line->segments;
6801 gtk_text_btree_spew_segment (tree, seg);
6807 gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment * seg)
6809 printf (" segment: %p type: %s bytes: %d chars: %d\n",
6810 seg, seg->type->name, seg->byte_count, seg->char_count);
6812 if (seg->type == >k_text_char_type)
6814 gchar* str = g_strndup (seg->body.chars, seg->byte_count);
6815 printf (" `%s'\n", str);
6818 else if (seg->type == >k_text_right_mark_type)
6820 printf (" right mark `%s' visible: %d not_deleteable: %d\n",
6821 seg->body.mark.name,
6822 seg->body.mark.visible,
6823 seg->body.mark.not_deleteable);
6825 else if (seg->type == >k_text_left_mark_type)
6827 printf (" left mark `%s' visible: %d not_deleteable: %d\n",
6828 seg->body.mark.name,
6829 seg->body.mark.visible,
6830 seg->body.mark.not_deleteable);
6832 else if (seg->type == >k_text_toggle_on_type ||
6833 seg->type == >k_text_toggle_off_type)
6835 printf (" tag `%s' priority %d\n",
6836 seg->body.toggle.info->tag->name,
6837 seg->body.toggle.info->tag->priority);