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_prev_char (end);
605 if (gtk_text_iter_get_line_offset (start) == 0 &&
608 gtk_text_iter_prev_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 chunkSize; /* # characters in current chunk. */
928 guint sol; /* start of line */
929 guint eol; /* Pointer to character just after last
930 * one in current chunk. */
931 int line_count_delta; /* Counts change to total number of
934 int char_count_delta; /* change to number of chars */
936 gint start_byte_index;
937 GtkTextLine *start_line;
939 g_return_if_fail (text != NULL);
940 g_return_if_fail (iter != NULL);
945 /* extract iterator info */
946 tree = gtk_text_iter_get_btree (iter);
947 line = gtk_text_iter_get_text_line (iter);
949 start_byte_index = gtk_text_iter_get_line_index (iter);
951 /* Get our insertion segment split */
952 prev_seg = gtk_text_line_segment_split (iter);
955 /* Invalidate all iterators */
956 chars_changed (tree);
957 segments_changed (tree);
960 * Chop the text up into lines and create a new segment for
961 * each line, plus a new line for the leftovers from the
967 line_count_delta = 0;
968 char_count_delta = 0;
971 for (; eol < len; eol++)
973 if (text[eol] == '\n')
979 chunkSize = eol - sol;
981 seg = _gtk_char_segment_new (&text[sol], chunkSize);
983 char_count_delta += seg->char_count;
987 seg->next = line->segments;
988 line->segments = seg;
992 seg->next = cur_seg->next;
996 if (text[eol-1] != '\n')
1002 * The chunk ended with a newline, so create a new GtkTextLine
1003 * and move the remainder of the old line to it.
1006 newline = gtk_text_line_new ();
1007 gtk_text_line_set_parent (newline, line->parent);
1008 newline->next = line->next;
1009 line->next = newline;
1010 newline->segments = seg->next;
1020 * Cleanup the starting line for the insertion, plus the ending
1021 * line if it's different.
1024 cleanup_line (start_line);
1025 if (line != start_line)
1027 cleanup_line (line);
1030 post_insert_fixup (tree, line, line_count_delta, char_count_delta);
1032 /* Invalidate our region, and reset the iterator the user
1033 passed in to point to the end of the inserted text. */
1039 gtk_text_btree_get_iter_at_line (tree,
1045 /* We could almost certainly be more efficient here
1046 by saving the information from the insertion loop
1048 gtk_text_iter_forward_chars (&end, char_count_delta);
1050 gtk_text_btree_invalidate_region (tree,
1054 /* Convenience for the user */
1060 insert_pixbuf_or_widget_segment (GtkTextIter *iter,
1061 GtkTextLineSegment *seg)
1065 GtkTextLineSegment *prevPtr;
1068 gint start_byte_offset;
1070 line = gtk_text_iter_get_text_line (iter);
1071 tree = gtk_text_iter_get_btree (iter);
1072 start_byte_offset = gtk_text_iter_get_line_index (iter);
1074 prevPtr = gtk_text_line_segment_split (iter);
1075 if (prevPtr == NULL)
1077 seg->next = line->segments;
1078 line->segments = seg;
1082 seg->next = prevPtr->next;
1083 prevPtr->next = seg;
1086 post_insert_fixup (tree, line, 0, seg->char_count);
1088 chars_changed (tree);
1089 segments_changed (tree);
1091 /* reset *iter for the user, and invalidate tree nodes */
1093 gtk_text_btree_get_iter_at_line (tree, &start, line, start_byte_offset);
1096 gtk_text_iter_next_char (iter); /* skip forward past the segment */
1098 gtk_text_btree_invalidate_region (tree, &start, iter);
1102 gtk_text_btree_insert_pixbuf (GtkTextIter *iter,
1105 GtkTextLineSegment *seg;
1107 seg = _gtk_pixbuf_segment_new (pixbuf);
1109 insert_pixbuf_or_widget_segment (iter, seg);
1113 gtk_text_btree_create_child_anchor (GtkTextIter *iter)
1115 GtkTextLineSegment *seg;
1118 seg = _gtk_widget_segment_new ();
1120 insert_pixbuf_or_widget_segment (iter, seg);
1122 tree = seg->body.child.tree;
1124 if (tree->child_anchor_table == NULL)
1125 tree->child_anchor_table = g_hash_table_new (NULL, NULL);
1127 g_hash_table_insert (tree->child_anchor_table,
1128 seg->body.child.obj,
1129 seg->body.child.obj);
1131 return seg->body.child.obj;
1135 gtk_text_btree_unregister_child_anchor (GtkTextChildAnchor *anchor)
1137 GtkTextLineSegment *seg;
1139 seg = anchor->segment;
1141 g_hash_table_remove (seg->body.child.tree->child_anchor_table,
1150 find_line_by_y (GtkTextBTree *tree, BTreeView *view,
1151 GtkTextBTreeNode *node, gint y, gint *line_top,
1152 GtkTextLine *last_line)
1156 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1157 gtk_text_btree_check (tree);
1159 if (node->level == 0)
1163 line = node->children.line;
1165 while (line != NULL && line != last_line)
1167 GtkTextLineData *ld;
1169 ld = gtk_text_line_get_data (line, view->view_id);
1173 if (y < (current_y + (ld ? ld->height : 0)))
1176 current_y += ld->height;
1177 *line_top += ld->height;
1186 GtkTextBTreeNode *child;
1188 child = node->children.node;
1190 while (child != NULL)
1195 gtk_text_btree_node_get_size (child, view->view_id,
1198 if (y < (current_y + height))
1199 return find_line_by_y (tree, view, child,
1200 y - current_y, line_top,
1203 current_y += height;
1204 *line_top += height;
1206 child = child->next;
1214 gtk_text_btree_find_line_by_y (GtkTextBTree *tree,
1221 GtkTextLine *last_line;
1224 view = gtk_text_btree_get_view (tree, view_id);
1225 g_return_val_if_fail (view != NULL, NULL);
1227 last_line = get_last_line (tree);
1229 line = find_line_by_y (tree, view, tree->root_node, ypixel, &line_top,
1233 *line_top_out = line_top;
1239 find_line_top_in_line_list (GtkTextBTree *tree,
1242 GtkTextLine *target_line,
1245 while (line != NULL)
1247 GtkTextLineData *ld;
1249 if (line == target_line)
1252 ld = gtk_text_line_get_data (line, view->view_id);
1259 g_assert_not_reached (); /* If we get here, our
1260 target line didn't exist
1261 under its parent node */
1266 gtk_text_btree_find_line_top (GtkTextBTree *tree,
1267 GtkTextLine *target_line,
1274 GtkTextBTreeNode *node;
1276 view = gtk_text_btree_get_view (tree, view_id);
1278 g_return_val_if_fail (view != NULL, 0);
1281 node = target_line->parent;
1282 while (node != NULL)
1284 nodes = g_slist_prepend (nodes, node);
1285 node = node->parent;
1289 while (iter != NULL)
1293 if (node->level == 0)
1295 g_slist_free (nodes);
1296 return find_line_top_in_line_list (tree, view,
1297 node->children.line,
1302 GtkTextBTreeNode *child;
1303 GtkTextBTreeNode *target_node;
1305 g_assert (iter->next != NULL); /* not at level 0 */
1306 target_node = iter->next->data;
1308 child = node->children.node;
1310 while (child != NULL)
1315 if (child == target_node)
1319 gtk_text_btree_node_get_size (child, view->view_id,
1323 child = child->next;
1325 g_assert (child != NULL); /* should have broken out before we
1329 iter = g_slist_next (iter);
1332 g_assert_not_reached (); /* we return when we find the target line */
1337 gtk_text_btree_add_view (GtkTextBTree *tree,
1338 GtkTextLayout *layout)
1341 GtkTextLine *last_line;
1342 GtkTextLineData *line_data;
1344 g_return_if_fail (tree != NULL);
1346 view = g_new (BTreeView, 1);
1348 view->view_id = layout;
1349 view->layout = layout;
1351 view->next = tree->views;
1356 /* The last line in the buffer has identity values for the per-view
1357 * data so that we can avoid special case checks for it in a large
1360 last_line = get_last_line (tree);
1362 line_data = g_new (GtkTextLineData, 1);
1363 line_data->view_id = layout;
1364 line_data->next = NULL;
1365 line_data->width = 0;
1366 line_data->height = 0;
1367 line_data->valid = TRUE;
1369 gtk_text_line_add_data (last_line, line_data);
1373 gtk_text_btree_remove_view (GtkTextBTree *tree,
1377 GtkTextLine *last_line;
1378 GtkTextLineData *line_data;
1380 g_return_if_fail (tree != NULL);
1384 while (view != NULL)
1386 if (view->view_id == view_id)
1392 g_return_if_fail (view != NULL);
1395 view->next->prev = view->prev;
1398 view->prev->next = view->next;
1400 if (view == tree->views)
1401 tree->views = view->next;
1403 /* Remove the line data for the last line which we added ourselves.
1404 * (Do this first, so that we don't try to call the view's line data destructor on it.)
1406 last_line = get_last_line (tree);
1407 line_data = gtk_text_line_remove_data (last_line, view_id);
1410 gtk_text_btree_node_remove_view (view, tree->root_node, view_id);
1416 gtk_text_btree_invalidate_region (GtkTextBTree *tree,
1417 const GtkTextIter *start,
1418 const GtkTextIter *end)
1424 while (view != NULL)
1426 gtk_text_layout_invalidate (view->layout, start, end);
1433 gtk_text_btree_get_view_size (GtkTextBTree *tree,
1438 g_return_if_fail (tree != NULL);
1439 g_return_if_fail (view_id != NULL);
1441 gtk_text_btree_node_get_size (tree->root_node, view_id,
1456 iter_stack_new (void)
1459 stack = g_new (IterStack, 1);
1460 stack->iters = NULL;
1467 iter_stack_push (IterStack *stack, const GtkTextIter *iter)
1470 if (stack->count > stack->alloced)
1472 stack->alloced = stack->count*2;
1473 stack->iters = g_realloc (stack->iters,
1474 stack->alloced*sizeof (GtkTextIter));
1476 stack->iters[stack->count-1] = *iter;
1480 iter_stack_pop (IterStack *stack, GtkTextIter *iter)
1482 if (stack->count == 0)
1487 *iter = stack->iters[stack->count];
1493 iter_stack_free (IterStack *stack)
1495 g_free (stack->iters);
1500 iter_stack_invert (IterStack *stack)
1502 if (stack->count > 0)
1505 guint j = stack->count - 1;
1510 tmp = stack->iters[i];
1511 stack->iters[i] = stack->iters[j];
1512 stack->iters[j] = tmp;
1521 queue_tag_redisplay (GtkTextBTree *tree,
1523 const GtkTextIter *start,
1524 const GtkTextIter *end)
1526 if (gtk_text_tag_affects_size (tag))
1528 gtk_text_btree_invalidate_region (tree, start, end);
1531 else if (gtk_text_tag_affects_nonsize_appearance (tag))
1533 /* We only need to queue a redraw, not a relayout */
1534 redisplay_region (tree, start, end);
1537 /* We don't need to do anything if the tag doesn't affect display */
1541 gtk_text_btree_tag (const GtkTextIter *start_orig,
1542 const GtkTextIter *end_orig,
1546 GtkTextLineSegment *seg, *prev;
1547 GtkTextLine *cleanupline;
1548 gboolean toggled_on;
1549 GtkTextLine *start_line;
1550 GtkTextLine *end_line;
1552 GtkTextIter start, end;
1555 GtkTextTagInfo *info;
1557 g_return_if_fail (start_orig != NULL);
1558 g_return_if_fail (end_orig != NULL);
1559 g_return_if_fail (GTK_IS_TEXT_TAG (tag));
1560 g_return_if_fail (gtk_text_iter_get_btree (start_orig) ==
1561 gtk_text_iter_get_btree (end_orig));
1564 printf ("%s tag %s from %d to %d\n",
1565 add ? "Adding" : "Removing",
1567 gtk_text_buffer_get_offset (start_orig),
1568 gtk_text_buffer_get_offset (end_orig));
1571 if (gtk_text_iter_equal (start_orig, end_orig))
1574 start = *start_orig;
1577 gtk_text_iter_reorder (&start, &end);
1579 tree = gtk_text_iter_get_btree (&start);
1581 queue_tag_redisplay (tree, tag, &start, &end);
1583 info = gtk_text_btree_get_tag_info (tree, tag);
1585 start_line = gtk_text_iter_get_text_line (&start);
1586 end_line = gtk_text_iter_get_text_line (&end);
1588 /* Find all tag toggles in the region; we are going to delete them.
1589 We need to find them in advance, because
1590 forward_find_tag_toggle () won't work once we start playing around
1592 stack = iter_stack_new ();
1594 /* We don't want to delete a toggle that's at the start iterator. */
1595 gtk_text_iter_next_char (&iter);
1596 while (gtk_text_iter_forward_to_tag_toggle (&iter, tag))
1598 if (gtk_text_iter_compare (&iter, &end) >= 0)
1601 iter_stack_push (stack, &iter);
1604 /* We need to traverse the toggles in order. */
1605 iter_stack_invert (stack);
1608 * See whether the tag is present at the start of the range. If
1609 * the state doesn't already match what we want then add a toggle
1613 toggled_on = gtk_text_iter_has_tag (&start, tag);
1614 if ( (add && !toggled_on) ||
1615 (!add && toggled_on) )
1617 /* This could create a second toggle at the start position;
1618 cleanup_line () will remove it if so. */
1619 seg = _gtk_toggle_segment_new (info, add);
1621 prev = gtk_text_line_segment_split (&start);
1624 seg->next = start_line->segments;
1625 start_line->segments = seg;
1629 seg->next = prev->next;
1633 /* cleanup_line adds the new toggle to the node counts. */
1635 printf ("added toggle at start\n");
1637 /* we should probably call segments_changed, but in theory
1638 any still-cached segments in the iters we are about to
1639 use are still valid, since they're in front
1645 * Scan the range of characters and delete any internal tag
1646 * transitions. Keep track of what the old state was at the end
1647 * of the range, and add a toggle there if it's needed.
1651 cleanupline = start_line;
1652 while (iter_stack_pop (stack, &iter))
1654 GtkTextLineSegment *indexable_seg;
1657 line = gtk_text_iter_get_text_line (&iter);
1658 seg = gtk_text_iter_get_any_segment (&iter);
1659 indexable_seg = gtk_text_iter_get_indexable_segment (&iter);
1661 g_assert (seg != NULL);
1662 g_assert (indexable_seg != NULL);
1663 g_assert (seg != indexable_seg);
1665 prev = line->segments;
1667 /* Find the segment that actually toggles this tag. */
1668 while (seg != indexable_seg)
1670 g_assert (seg != NULL);
1671 g_assert (indexable_seg != NULL);
1672 g_assert (seg != indexable_seg);
1674 if ( (seg->type == >k_text_toggle_on_type ||
1675 seg->type == >k_text_toggle_off_type) &&
1676 (seg->body.toggle.info == info) )
1682 g_assert (seg != NULL);
1683 g_assert (indexable_seg != NULL);
1685 g_assert (seg != indexable_seg); /* If this happens, then
1686 forward_to_tag_toggle was
1688 g_assert (seg->body.toggle.info->tag == tag);
1690 /* If this happens, when previously tagging we didn't merge
1691 overlapping tags. */
1692 g_assert ( (toggled_on && seg->type == >k_text_toggle_off_type) ||
1693 (!toggled_on && seg->type == >k_text_toggle_on_type) );
1695 toggled_on = !toggled_on;
1698 printf ("deleting %s toggle\n",
1699 seg->type == >k_text_toggle_on_type ? "on" : "off");
1701 /* Remove toggle segment from the list. */
1704 line->segments = seg->next;
1708 while (prev->next != seg)
1712 prev->next = seg->next;
1715 /* Inform iterators we've hosed them. This actually reflects a
1716 bit of inefficiency; if you have the same tag toggled on and
1717 off a lot in a single line, we keep having the rescan from
1718 the front of the line. Of course we have to do that to get
1719 "prev" anyway, but here we are doing it an additional
1721 segments_changed (tree);
1723 /* Update node counts */
1724 if (seg->body.toggle.inNodeCounts)
1726 _gtk_change_node_toggle_count (line->parent,
1728 seg->body.toggle.inNodeCounts = FALSE;
1733 /* We only clean up lines when we're done with them, saves some
1734 gratuitous line-segment-traversals */
1736 if (cleanupline != line)
1738 cleanup_line (cleanupline);
1743 iter_stack_free (stack);
1745 /* toggled_on now reflects the toggle state _just before_ the
1746 end iterator. The end iterator could already have a toggle
1747 on or a toggle off. */
1748 if ( (add && !toggled_on) ||
1749 (!add && toggled_on) )
1751 /* This could create a second toggle at the start position;
1752 cleanup_line () will remove it if so. */
1754 seg = _gtk_toggle_segment_new (info, !add);
1756 prev = gtk_text_line_segment_split (&end);
1759 seg->next = end_line->segments;
1760 end_line->segments = seg;
1764 seg->next = prev->next;
1767 /* cleanup_line adds the new toggle to the node counts. */
1768 g_assert (seg->body.toggle.inNodeCounts == FALSE);
1770 printf ("added toggle at end\n");
1775 * Cleanup cleanupline and the last line of the range, if
1776 * these are different.
1779 cleanup_line (cleanupline);
1780 if (cleanupline != end_line)
1782 cleanup_line (end_line);
1785 segments_changed (tree);
1787 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1788 gtk_text_btree_check (tree);
1797 gtk_text_btree_get_line (GtkTextBTree *tree,
1799 gint *real_line_number)
1801 GtkTextBTreeNode *node;
1806 line_count = gtk_text_btree_line_count (tree);
1808 if (line_number < 0)
1810 line_number = line_count;
1812 else if (line_number > line_count)
1814 line_number = line_count;
1817 if (real_line_number)
1818 *real_line_number = line_number;
1820 node = tree->root_node;
1821 lines_left = line_number;
1824 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1828 while (node->level != 0)
1830 for (node = node->children.node;
1831 node->num_lines <= lines_left;
1837 g_error ("gtk_text_btree_find_line ran out of GtkTextBTreeNodes");
1840 lines_left -= node->num_lines;
1845 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1848 for (line = node->children.line; lines_left > 0;
1854 g_error ("gtk_text_btree_find_line ran out of lines");
1863 gtk_text_btree_get_line_at_char (GtkTextBTree *tree,
1865 gint *line_start_index,
1866 gint *real_char_index)
1868 GtkTextBTreeNode *node;
1870 GtkTextLineSegment *seg;
1875 node = tree->root_node;
1877 /* Clamp to valid indexes (-1 is magic for "highest index") */
1878 if (char_index < 0 || char_index >= node->num_chars)
1880 char_index = node->num_chars - 1;
1883 *real_char_index = char_index;
1886 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1890 chars_left = char_index;
1891 while (node->level != 0)
1893 for (node = node->children.node;
1894 chars_left >= node->num_chars;
1897 chars_left -= node->num_chars;
1899 g_assert (chars_left >= 0);
1903 if (chars_left == 0)
1905 /* Start of a line */
1907 *line_start_index = char_index;
1908 return node->children.line;
1912 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1918 for (line = node->children.line; line != NULL; line = line->next)
1920 seg = line->segments;
1923 if (chars_in_line + seg->char_count > chars_left)
1924 goto found; /* found our line/segment */
1926 chars_in_line += seg->char_count;
1931 chars_left -= chars_in_line;
1939 g_assert (line != NULL); /* hosage, ran out of lines */
1940 g_assert (seg != NULL);
1942 *line_start_index = char_index - chars_left;
1947 gtk_text_btree_get_tags (const GtkTextIter *iter,
1950 GtkTextBTreeNode *node;
1951 GtkTextLine *siblingline;
1952 GtkTextLineSegment *seg;
1953 int src, dst, index;
1959 #define NUM_TAG_INFOS 10
1961 line = gtk_text_iter_get_text_line (iter);
1962 tree = gtk_text_iter_get_btree (iter);
1963 byte_index = gtk_text_iter_get_line_index (iter);
1965 tagInfo.numTags = 0;
1966 tagInfo.arraySize = NUM_TAG_INFOS;
1967 tagInfo.tags = g_new (GtkTextTag*, NUM_TAG_INFOS);
1968 tagInfo.counts = g_new (int, NUM_TAG_INFOS);
1971 * Record tag toggles within the line of indexPtr but preceding
1972 * indexPtr. Note that if this loop segfaults, your
1973 * byte_index probably points past the sum of all
1974 * seg->byte_count */
1976 for (index = 0, seg = line->segments;
1977 (index + seg->byte_count) <= byte_index;
1978 index += seg->byte_count, seg = seg->next)
1980 if ((seg->type == >k_text_toggle_on_type)
1981 || (seg->type == >k_text_toggle_off_type))
1983 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
1988 * Record toggles for tags in lines that are predecessors of
1989 * line but under the same level-0 GtkTextBTreeNode.
1992 for (siblingline = line->parent->children.line;
1993 siblingline != line;
1994 siblingline = siblingline->next)
1996 for (seg = siblingline->segments; seg != NULL;
1999 if ((seg->type == >k_text_toggle_on_type)
2000 || (seg->type == >k_text_toggle_off_type))
2002 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2008 * For each GtkTextBTreeNode in the ancestry of this line, record tag
2009 * toggles for all siblings that precede that GtkTextBTreeNode.
2012 for (node = line->parent; node->parent != NULL;
2013 node = node->parent)
2015 GtkTextBTreeNode *siblingPtr;
2018 for (siblingPtr = node->parent->children.node;
2019 siblingPtr != node; siblingPtr = siblingPtr->next)
2021 for (summary = siblingPtr->summary; summary != NULL;
2022 summary = summary->next)
2024 if (summary->toggle_count & 1)
2026 inc_count (summary->info->tag, summary->toggle_count,
2034 * Go through the tag information and squash out all of the tags
2035 * that have even toggle counts (these tags exist before the point
2036 * of interest, but not at the desired character itself).
2039 for (src = 0, dst = 0; src < tagInfo.numTags; src++)
2041 if (tagInfo.counts[src] & 1)
2043 g_assert (GTK_IS_TEXT_TAG (tagInfo.tags[src]));
2044 tagInfo.tags[dst] = tagInfo.tags[src];
2050 g_free (tagInfo.counts);
2053 g_free (tagInfo.tags);
2056 return tagInfo.tags;
2060 copy_segment (GString *string,
2061 gboolean include_hidden,
2062 gboolean include_nonchars,
2063 const GtkTextIter *start,
2064 const GtkTextIter *end)
2066 GtkTextLineSegment *end_seg;
2067 GtkTextLineSegment *seg;
2069 if (gtk_text_iter_equal (start, end))
2072 seg = gtk_text_iter_get_indexable_segment (start);
2073 end_seg = gtk_text_iter_get_indexable_segment (end);
2075 if (seg->type == >k_text_char_type)
2077 gboolean copy = TRUE;
2078 gint copy_bytes = 0;
2079 gint copy_start = 0;
2081 /* Don't copy if we're invisible; segments are invisible/not
2082 as a whole, no need to check each char */
2083 if (!include_hidden &&
2084 gtk_text_btree_char_is_invisible (start))
2087 /* printf (" <invisible>\n"); */
2090 copy_start = gtk_text_iter_get_segment_byte (start);
2094 /* End is in the same segment; need to copy fewer bytes. */
2095 gint end_byte = gtk_text_iter_get_segment_byte (end);
2097 copy_bytes = end_byte - copy_start;
2100 copy_bytes = seg->byte_count - copy_start;
2102 g_assert (copy_bytes != 0); /* Due to iter equality check at
2103 front of this function. */
2107 g_assert ((copy_start + copy_bytes) <= seg->byte_count);
2109 g_string_append_len (string,
2110 seg->body.chars + copy_start,
2114 /* printf (" :%s\n", string->str); */
2116 else if (seg->type == >k_text_pixbuf_type ||
2117 seg->type == >k_text_child_type)
2119 gboolean copy = TRUE;
2121 if (!include_nonchars)
2125 else if (!include_hidden &&
2126 gtk_text_btree_char_is_invisible (start))
2133 g_string_append_len (string,
2134 gtk_text_unknown_char_utf8,
2142 gtk_text_btree_get_text (const GtkTextIter *start_orig,
2143 const GtkTextIter *end_orig,
2144 gboolean include_hidden,
2145 gboolean include_nonchars)
2147 GtkTextLineSegment *seg;
2148 GtkTextLineSegment *end_seg;
2156 g_return_val_if_fail (start_orig != NULL, NULL);
2157 g_return_val_if_fail (end_orig != NULL, NULL);
2158 g_return_val_if_fail (gtk_text_iter_get_btree (start_orig) ==
2159 gtk_text_iter_get_btree (end_orig), NULL);
2161 start = *start_orig;
2164 gtk_text_iter_reorder (&start, &end);
2166 retval = g_string_new ("");
2168 tree = gtk_text_iter_get_btree (&start);
2170 end_seg = gtk_text_iter_get_indexable_segment (&end);
2172 seg = gtk_text_iter_get_indexable_segment (&iter);
2173 while (seg != end_seg)
2175 copy_segment (retval, include_hidden, include_nonchars,
2178 gtk_text_iter_forward_indexable_segment (&iter);
2180 seg = gtk_text_iter_get_indexable_segment (&iter);
2183 copy_segment (retval, include_hidden, include_nonchars, &iter, &end);
2186 g_string_free (retval, FALSE);
2191 gtk_text_btree_line_count (GtkTextBTree *tree)
2193 /* Subtract bogus line at the end; we return a count
2195 return tree->root_node->num_lines - 1;
2199 gtk_text_btree_char_count (GtkTextBTree *tree)
2201 /* Exclude newline in bogus last line */
2202 return tree->root_node->num_chars - 1;
2205 #define LOTSA_TAGS 1000
2207 gtk_text_btree_char_is_invisible (const GtkTextIter *iter)
2209 gboolean invisible = FALSE; /* if nobody says otherwise, it's visible */
2211 int deftagCnts[LOTSA_TAGS];
2212 int *tagCnts = deftagCnts;
2213 GtkTextTag *deftags[LOTSA_TAGS];
2214 GtkTextTag **tags = deftags;
2216 GtkTextBTreeNode *node;
2217 GtkTextLine *siblingline;
2218 GtkTextLineSegment *seg;
2225 line = gtk_text_iter_get_text_line (iter);
2226 tree = gtk_text_iter_get_btree (iter);
2227 byte_index = gtk_text_iter_get_line_index (iter);
2229 numTags = gtk_text_tag_table_size (tree->table);
2231 /* almost always avoid malloc, so stay out of system calls */
2232 if (LOTSA_TAGS < numTags)
2234 tagCnts = g_new (int, numTags);
2235 tags = g_new (GtkTextTag*, numTags);
2238 for (i=0; i<numTags; i++)
2244 * Record tag toggles within the line of indexPtr but preceding
2248 for (index = 0, seg = line->segments;
2249 (index + seg->byte_count) <= byte_index; /* segfault here means invalid index */
2250 index += seg->byte_count, seg = seg->next)
2252 if ((seg->type == >k_text_toggle_on_type)
2253 || (seg->type == >k_text_toggle_off_type))
2255 tag = seg->body.toggle.info->tag;
2256 if (tag->invisible_set && tag->values->invisible)
2258 tags[tag->priority] = tag;
2259 tagCnts[tag->priority]++;
2265 * Record toggles for tags in lines that are predecessors of
2266 * line but under the same level-0 GtkTextBTreeNode.
2269 for (siblingline = line->parent->children.line;
2270 siblingline != line;
2271 siblingline = siblingline->next)
2273 for (seg = siblingline->segments; seg != NULL;
2276 if ((seg->type == >k_text_toggle_on_type)
2277 || (seg->type == >k_text_toggle_off_type))
2279 tag = seg->body.toggle.info->tag;
2280 if (tag->invisible_set && tag->values->invisible)
2282 tags[tag->priority] = tag;
2283 tagCnts[tag->priority]++;
2290 * For each GtkTextBTreeNode in the ancestry of this line, record tag toggles
2291 * for all siblings that precede that GtkTextBTreeNode.
2294 for (node = line->parent; node->parent != NULL;
2295 node = node->parent)
2297 GtkTextBTreeNode *siblingPtr;
2300 for (siblingPtr = node->parent->children.node;
2301 siblingPtr != node; siblingPtr = siblingPtr->next)
2303 for (summary = siblingPtr->summary; summary != NULL;
2304 summary = summary->next)
2306 if (summary->toggle_count & 1)
2308 tag = summary->info->tag;
2309 if (tag->invisible_set && tag->values->invisible)
2311 tags[tag->priority] = tag;
2312 tagCnts[tag->priority] += summary->toggle_count;
2320 * Now traverse from highest priority to lowest,
2321 * take invisible value from first odd count (= on)
2324 for (i = numTags-1; i >=0; i--)
2328 /* FIXME not sure this should be if 0 */
2330 #ifndef ALWAYS_SHOW_SELECTION
2331 /* who would make the selection invisible? */
2332 if ((tag == tkxt->seltag)
2333 && !(tkxt->flags & GOT_FOCUS))
2339 invisible = tags[i]->values->invisible;
2344 if (LOTSA_TAGS < numTags)
2359 redisplay_region (GtkTextBTree *tree,
2360 const GtkTextIter *start,
2361 const GtkTextIter *end)
2364 GtkTextLine *start_line, *end_line;
2366 if (gtk_text_iter_compare (start, end) > 0)
2368 const GtkTextIter *tmp = start;
2373 start_line = gtk_text_iter_get_text_line (start);
2374 end_line = gtk_text_iter_get_text_line (end);
2377 while (view != NULL)
2379 gint start_y, end_y;
2380 GtkTextLineData *ld;
2382 start_y = gtk_text_btree_find_line_top (tree, start_line, view->view_id);
2384 if (end_line == start_line)
2387 end_y = gtk_text_btree_find_line_top (tree, end_line, view->view_id);
2389 ld = gtk_text_line_get_data (end_line, view->view_id);
2391 end_y += ld->height;
2393 gtk_text_layout_changed (view->layout, start_y,
2402 redisplay_mark (GtkTextLineSegment *mark)
2407 gtk_text_btree_get_iter_at_mark (mark->body.mark.tree,
2409 mark->body.mark.obj);
2412 gtk_text_iter_next_char (&end);
2414 gtk_text_btree_invalidate_region (mark->body.mark.tree,
2419 redisplay_mark_if_visible (GtkTextLineSegment *mark)
2421 if (!mark->body.mark.visible)
2424 redisplay_mark (mark);
2428 ensure_not_off_end (GtkTextBTree *tree,
2429 GtkTextLineSegment *mark,
2432 if (gtk_text_iter_get_line (iter) ==
2433 gtk_text_btree_line_count (tree))
2434 gtk_text_iter_prev_char (iter);
2437 static GtkTextLineSegment*
2438 real_set_mark (GtkTextBTree *tree,
2439 GtkTextMark *existing_mark,
2441 gboolean left_gravity,
2442 const GtkTextIter *where,
2443 gboolean should_exist,
2444 gboolean redraw_selections)
2446 GtkTextLineSegment *mark;
2449 g_return_val_if_fail (tree != NULL, NULL);
2450 g_return_val_if_fail (where != NULL, NULL);
2451 g_return_val_if_fail (gtk_text_iter_get_btree (where) == tree, NULL);
2454 mark = existing_mark->segment;
2455 else if (name != NULL)
2456 mark = g_hash_table_lookup (tree->mark_table,
2461 if (should_exist && mark == NULL)
2463 g_warning ("No mark `%s' exists!", name);
2467 /* OK if !should_exist and it does already exist, in that case
2473 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2474 gtk_text_iter_check (&iter);
2478 if (redraw_selections &&
2479 (mark == tree->insert_mark->segment ||
2480 mark == tree->selection_bound_mark->segment))
2482 GtkTextIter old_pos;
2484 gtk_text_btree_get_iter_at_mark (tree, &old_pos,
2485 mark->body.mark.obj);
2486 redisplay_region (tree, &old_pos, where);
2490 * don't let visible marks be after the final newline of the
2494 if (mark->body.mark.visible)
2496 ensure_not_off_end (tree, mark, &iter);
2499 /* Redraw the mark's old location. */
2500 redisplay_mark_if_visible (mark);
2502 /* Unlink mark from its current location.
2503 This could hose our iterator... */
2504 gtk_text_btree_unlink_segment (tree, mark,
2505 mark->body.mark.line);
2506 mark->body.mark.line = gtk_text_iter_get_text_line (&iter);
2507 g_assert (mark->body.mark.line == gtk_text_iter_get_text_line (&iter));
2509 segments_changed (tree); /* make sure the iterator recomputes its
2514 mark = _gtk_mark_segment_new (tree,
2518 mark->body.mark.line = gtk_text_iter_get_text_line (&iter);
2520 if (mark->body.mark.name)
2521 g_hash_table_insert (tree->mark_table,
2522 mark->body.mark.name,
2526 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2527 gtk_text_iter_check (&iter);
2529 /* Link mark into new location */
2530 gtk_text_btree_link_segment (mark, &iter);
2532 /* Invalidate some iterators. */
2533 segments_changed (tree);
2536 * update the screen at the mark's new location.
2539 redisplay_mark_if_visible (mark);
2541 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2542 gtk_text_iter_check (&iter);
2544 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2545 gtk_text_btree_check (tree);
2552 gtk_text_btree_set_mark (GtkTextBTree *tree,
2553 GtkTextMark *existing_mark,
2555 gboolean left_gravity,
2556 const GtkTextIter *iter,
2557 gboolean should_exist)
2559 GtkTextLineSegment *seg;
2561 seg = real_set_mark (tree, existing_mark,
2562 name, left_gravity, iter, should_exist,
2565 return seg ? seg->body.mark.obj : NULL;
2569 gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2573 GtkTextIter tmp_start, tmp_end;
2575 gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2577 gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2578 tree->selection_bound_mark);
2580 if (gtk_text_iter_equal (&tmp_start, &tmp_end))
2592 gtk_text_iter_reorder (&tmp_start, &tmp_end);
2605 gtk_text_btree_place_cursor (GtkTextBTree *tree,
2606 const GtkTextIter *iter)
2608 GtkTextIter start, end;
2610 if (gtk_text_btree_get_selection_bounds (tree, &start, &end))
2611 redisplay_region (tree, &start, &end);
2613 /* Move insert AND selection_bound before we redisplay */
2614 real_set_mark (tree, tree->insert_mark,
2615 "insert", FALSE, iter, TRUE, FALSE);
2616 real_set_mark (tree, tree->selection_bound_mark,
2617 "selection_bound", FALSE, iter, TRUE, FALSE);
2621 gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2626 g_return_if_fail (tree != NULL);
2627 g_return_if_fail (name != NULL);
2629 mark = g_hash_table_lookup (tree->mark_table,
2632 gtk_text_btree_remove_mark (tree, mark);
2636 gtk_text_btree_remove_mark (GtkTextBTree *tree,
2639 GtkTextLineSegment *segment;
2641 g_return_if_fail (mark != NULL);
2642 g_return_if_fail (tree != NULL);
2644 segment = mark->segment;
2646 if (segment->body.mark.not_deleteable)
2648 g_warning ("Can't delete special mark `%s'", segment->body.mark.name);
2652 /* This calls cleanup_line and segments_changed */
2653 gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2655 if (segment->body.mark.name)
2656 g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2658 /* Remove the ref on the mark that belonged to the segment. */
2659 g_object_unref (G_OBJECT (mark));
2661 segment->body.mark.tree = NULL;
2662 segment->body.mark.line = NULL;
2666 gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2667 GtkTextMark *segment)
2669 return segment == tree->insert_mark;
2673 gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2674 GtkTextMark *segment)
2676 return segment == tree->selection_bound_mark;
2680 gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2683 GtkTextLineSegment *seg;
2685 g_return_val_if_fail (tree != NULL, NULL);
2686 g_return_val_if_fail (name != NULL, NULL);
2688 seg = g_hash_table_lookup (tree->mark_table, name);
2690 return seg ? seg->body.mark.obj : NULL;
2694 gtk_text_mark_set_visible (GtkTextMark *mark,
2697 GtkTextLineSegment *seg;
2699 g_return_if_fail (mark != NULL);
2701 seg = mark->segment;
2703 if (seg->body.mark.visible == setting)
2707 seg->body.mark.visible = setting;
2709 redisplay_mark (seg);
2714 gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
2717 GtkTextBTreeNode *node;
2718 GtkTextTagInfo *info;
2720 g_return_val_if_fail (tree != NULL, NULL);
2724 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2729 if (info->tag_root == NULL)
2732 node = info->tag_root;
2734 /* We know the tag root has instances of the given
2737 continue_outer_loop:
2738 g_assert (node != NULL);
2739 while (node->level > 0)
2741 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2742 node = node->children.node;
2743 while (node != NULL)
2745 if (gtk_text_btree_node_has_tag (node, tag))
2746 goto continue_outer_loop;
2750 g_assert (node != NULL);
2753 g_assert (node != NULL); /* The tag summaries said some node had
2756 g_assert (node->level == 0);
2758 return node->children.line;
2762 /* Looking for any tag at all (tag == NULL).
2763 Unfortunately this can't be done in a simple and efficient way
2764 right now; so I'm just going to return the
2765 first line in the btree. FIXME */
2766 return gtk_text_btree_get_line (tree, 0, NULL);
2771 gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
2774 GtkTextBTreeNode *node;
2775 GtkTextBTreeNode *last_node;
2777 GtkTextTagInfo *info;
2779 g_return_val_if_fail (tree != NULL, NULL);
2783 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2785 if (info->tag_root == NULL)
2788 node = info->tag_root;
2789 /* We know the tag root has instances of the given
2792 while (node->level > 0)
2794 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2796 node = node->children.node;
2797 while (node != NULL)
2799 if (gtk_text_btree_node_has_tag (node, tag))
2807 g_assert (node != NULL); /* The tag summaries said some node had
2810 g_assert (node->level == 0);
2812 /* Find the last line in this node */
2813 line = node->children.line;
2814 while (line->next != NULL)
2821 /* This search can't be done efficiently at the moment,
2822 at least not without complexity.
2823 So, we just return the last line.
2825 return gtk_text_btree_get_line (tree, -1, NULL);
2835 gtk_text_line_get_number (GtkTextLine *line)
2838 GtkTextBTreeNode *node, *parent, *node2;
2842 * First count how many lines precede this one in its level-0
2846 node = line->parent;
2848 for (line2 = node->children.line; line2 != line;
2849 line2 = line2->next)
2853 g_error ("gtk_text_btree_line_number couldn't find line");
2859 * Now work up through the levels of the tree one at a time,
2860 * counting how many lines are in GtkTextBTreeNodes preceding the current
2864 for (parent = node->parent ; parent != NULL;
2865 node = parent, parent = parent->parent)
2867 for (node2 = parent->children.node; node2 != node;
2868 node2 = node2->next)
2872 g_error ("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
2874 index += node2->num_lines;
2880 static GtkTextLineSegment*
2881 find_toggle_segment_before_char (GtkTextLine *line,
2885 GtkTextLineSegment *seg;
2886 GtkTextLineSegment *toggle_seg;
2891 seg = line->segments;
2892 while ( (index + seg->char_count) <= char_in_line )
2894 if (((seg->type == >k_text_toggle_on_type)
2895 || (seg->type == >k_text_toggle_off_type))
2896 && (seg->body.toggle.info->tag == tag))
2899 index += seg->char_count;
2906 static GtkTextLineSegment*
2907 find_toggle_segment_before_byte (GtkTextLine *line,
2911 GtkTextLineSegment *seg;
2912 GtkTextLineSegment *toggle_seg;
2917 seg = line->segments;
2918 while ( (index + seg->byte_count) <= byte_in_line )
2920 if (((seg->type == >k_text_toggle_on_type)
2921 || (seg->type == >k_text_toggle_off_type))
2922 && (seg->body.toggle.info->tag == tag))
2925 index += seg->byte_count;
2933 find_toggle_outside_current_line (GtkTextLine *line,
2937 GtkTextBTreeNode *node;
2938 GtkTextLine *sibling_line;
2939 GtkTextLineSegment *seg;
2940 GtkTextLineSegment *toggle_seg;
2942 GtkTextTagInfo *info = NULL;
2945 * No toggle in this line. Look for toggles for the tag in lines
2946 * that are predecessors of line but under the same
2947 * level-0 GtkTextBTreeNode.
2950 sibling_line = line->parent->children.line;
2951 while (sibling_line != line)
2953 seg = sibling_line->segments;
2956 if (((seg->type == >k_text_toggle_on_type)
2957 || (seg->type == >k_text_toggle_off_type))
2958 && (seg->body.toggle.info->tag == tag))
2964 sibling_line = sibling_line->next;
2967 if (toggle_seg != NULL)
2968 return (toggle_seg->type == >k_text_toggle_on_type);
2971 * No toggle in this GtkTextBTreeNode. Scan upwards through the ancestors of
2972 * this GtkTextBTreeNode, counting the number of toggles of the given tag in
2973 * siblings that precede that GtkTextBTreeNode.
2976 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2982 node = line->parent;
2983 while (node->parent != NULL)
2985 GtkTextBTreeNode *sibling_node;
2987 sibling_node = node->parent->children.node;
2988 while (sibling_node != node)
2992 summary = sibling_node->summary;
2993 while (summary != NULL)
2995 if (summary->info == info)
2996 toggles += summary->toggle_count;
2998 summary = summary->next;
3001 sibling_node = sibling_node->next;
3004 if (node == info->tag_root)
3007 node = node->parent;
3011 * An odd number of toggles means that the tag is present at the
3015 return (toggles & 1) != 0;
3018 /* FIXME this function is far too slow, for no good reason. */
3020 gtk_text_line_char_has_tag (GtkTextLine *line,
3025 GtkTextLineSegment *toggle_seg;
3027 g_return_val_if_fail (line != NULL, FALSE);
3030 * Check for toggles for the tag in the line but before
3031 * the char. If there is one, its type indicates whether or
3032 * not the character is tagged.
3035 toggle_seg = find_toggle_segment_before_char (line, char_in_line, tag);
3037 if (toggle_seg != NULL)
3038 return (toggle_seg->type == >k_text_toggle_on_type);
3040 return find_toggle_outside_current_line (line, tree, tag);
3044 gtk_text_line_byte_has_tag (GtkTextLine *line,
3049 GtkTextLineSegment *toggle_seg;
3051 g_return_val_if_fail (line != NULL, FALSE);
3054 * Check for toggles for the tag in the line but before
3055 * the char. If there is one, its type indicates whether or
3056 * not the character is tagged.
3059 toggle_seg = find_toggle_segment_before_byte (line, byte_in_line, tag);
3061 if (toggle_seg != NULL)
3062 return (toggle_seg->type == >k_text_toggle_on_type);
3064 return find_toggle_outside_current_line (line, tree, tag);
3068 gtk_text_line_is_last (GtkTextLine *line,
3071 return line == get_last_line (tree);
3075 gtk_text_line_next (GtkTextLine *line)
3077 GtkTextBTreeNode *node;
3079 if (line->next != NULL)
3084 * This was the last line associated with the particular parent
3085 * GtkTextBTreeNode. Search up the tree for the next GtkTextBTreeNode,
3086 * then search down from that GtkTextBTreeNode to find the first
3090 node = line->parent;
3091 while (node != NULL && node->next == NULL)
3092 node = node->parent;
3098 while (node->level > 0)
3100 node = node->children.node;
3103 g_assert (node->children.line != line);
3105 return node->children.line;
3110 gtk_text_line_previous (GtkTextLine *line)
3112 GtkTextBTreeNode *node;
3113 GtkTextBTreeNode *node2;
3117 * Find the line under this GtkTextBTreeNode just before the starting line.
3119 prev = line->parent->children.line; /* First line at leaf */
3120 while (prev != line)
3122 if (prev->next == line)
3128 g_error ("gtk_text_btree_previous_line ran out of lines");
3132 * This was the first line associated with the particular parent
3133 * GtkTextBTreeNode. Search up the tree for the previous GtkTextBTreeNode,
3134 * then search down from that GtkTextBTreeNode to find its last line.
3136 for (node = line->parent; ; node = node->parent)
3138 if (node == NULL || node->parent == NULL)
3140 else if (node != node->parent->children.node)
3144 for (node2 = node->parent->children.node; ;
3145 node2 = node2->children.node)
3147 while (node2->next != node)
3148 node2 = node2->next;
3150 if (node2->level == 0)
3156 for (prev = node2->children.line ; ; prev = prev->next)
3158 if (prev->next == NULL)
3162 g_assert_not_reached ();
3167 gtk_text_line_add_data (GtkTextLine *line,
3168 GtkTextLineData *data)
3170 g_return_if_fail (line != NULL);
3171 g_return_if_fail (data != NULL);
3172 g_return_if_fail (data->view_id != NULL);
3176 data->next = line->views;
3186 gtk_text_line_remove_data (GtkTextLine *line,
3189 GtkTextLineData *prev;
3190 GtkTextLineData *iter;
3192 g_return_val_if_fail (line != NULL, NULL);
3193 g_return_val_if_fail (view_id != NULL, NULL);
3197 while (iter != NULL)
3199 if (iter->view_id == view_id)
3208 prev->next = iter->next;
3210 line->views = iter->next;
3219 gtk_text_line_get_data (GtkTextLine *line,
3222 GtkTextLineData *iter;
3224 g_return_val_if_fail (line != NULL, NULL);
3225 g_return_val_if_fail (view_id != NULL, NULL);
3228 while (iter != NULL)
3230 if (iter->view_id == view_id)
3239 gtk_text_line_invalidate_wrap (GtkTextLine *line,
3240 GtkTextLineData *ld)
3242 /* For now this is totally unoptimized. FIXME?
3244 We could probably optimize the case where the width removed
3245 is less than the max width for the parent node,
3246 and the case where the height is unchanged when we re-wrap.
3249 g_return_if_fail (ld != NULL);
3252 gtk_text_btree_node_invalidate_upward (line->parent, ld->view_id);
3256 gtk_text_line_char_count (GtkTextLine *line)
3258 GtkTextLineSegment *seg;
3262 seg = line->segments;
3265 size += seg->char_count;
3272 gtk_text_line_byte_count (GtkTextLine *line)
3274 GtkTextLineSegment *seg;
3278 seg = line->segments;
3281 size += seg->byte_count;
3289 gtk_text_line_char_index (GtkTextLine *target_line)
3291 GSList *node_stack = NULL;
3292 GtkTextBTreeNode *iter;
3296 /* Push all our parent nodes onto a stack */
3297 iter = target_line->parent;
3299 g_assert (iter != NULL);
3301 while (iter != NULL)
3303 node_stack = g_slist_prepend (node_stack, iter);
3305 iter = iter->parent;
3308 /* Check that we have the root node on top of the stack. */
3309 g_assert (node_stack != NULL &&
3310 node_stack->data != NULL &&
3311 ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3313 /* Add up chars in all nodes before the nodes in our stack.
3317 iter = node_stack->data;
3318 while (iter != NULL)
3320 GtkTextBTreeNode *child_iter;
3321 GtkTextBTreeNode *next_node;
3323 next_node = node_stack->next ?
3324 node_stack->next->data : NULL;
3325 node_stack = g_slist_remove (node_stack, node_stack->data);
3327 if (iter->level == 0)
3329 /* stack should be empty when we're on the last node */
3330 g_assert (node_stack == NULL);
3331 break; /* Our children are now lines */
3334 g_assert (next_node != NULL);
3335 g_assert (iter != NULL);
3336 g_assert (next_node->parent == iter);
3338 /* Add up chars before us in the tree */
3339 child_iter = iter->children.node;
3340 while (child_iter != next_node)
3342 g_assert (child_iter != NULL);
3344 num_chars += child_iter->num_chars;
3346 child_iter = child_iter->next;
3352 g_assert (iter != NULL);
3353 g_assert (iter == target_line->parent);
3355 /* Since we don't store char counts in lines, only in segments, we
3356 have to iterate over the lines adding up segment char counts
3357 until we find our line. */
3358 line = iter->children.line;
3359 while (line != target_line)
3361 g_assert (line != NULL);
3363 num_chars += gtk_text_line_char_count (line);
3368 g_assert (line == target_line);
3374 gtk_text_line_byte_to_segment (GtkTextLine *line,
3378 GtkTextLineSegment *seg;
3381 g_return_val_if_fail (line != NULL, NULL);
3383 offset = byte_offset;
3384 seg = line->segments;
3386 while (offset >= seg->byte_count)
3388 g_assert (seg != NULL); /* means an invalid byte index */
3389 offset -= seg->byte_count;
3394 *seg_offset = offset;
3400 gtk_text_line_char_to_segment (GtkTextLine *line,
3404 GtkTextLineSegment *seg;
3407 g_return_val_if_fail (line != NULL, NULL);
3409 offset = char_offset;
3410 seg = line->segments;
3412 while (offset >= seg->char_count)
3414 g_assert (seg != NULL); /* means an invalid char index */
3415 offset -= seg->char_count;
3420 *seg_offset = offset;
3426 gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3430 GtkTextLineSegment *seg;
3433 g_return_val_if_fail (line != NULL, NULL);
3435 offset = byte_offset;
3436 seg = line->segments;
3438 while (offset > 0 && offset >= seg->byte_count)
3440 g_assert (seg != NULL); /* means an invalid byte index */
3441 offset -= seg->byte_count;
3446 *seg_offset = offset;
3452 gtk_text_line_char_to_any_segment (GtkTextLine *line,
3456 GtkTextLineSegment *seg;
3459 g_return_val_if_fail (line != NULL, NULL);
3461 offset = char_offset;
3462 seg = line->segments;
3464 while (offset > 0 && offset >= seg->char_count)
3466 g_assert (seg != NULL); /* means an invalid byte index */
3467 offset -= seg->char_count;
3472 *seg_offset = offset;
3478 gtk_text_line_byte_to_char (GtkTextLine *line,
3482 GtkTextLineSegment *seg;
3484 g_return_val_if_fail (line != NULL, 0);
3485 g_return_val_if_fail (byte_offset >= 0, 0);
3488 seg = line->segments;
3489 while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3490 the next segment) */
3492 g_assert (seg != NULL); /* our byte_index was bogus if this happens */
3494 byte_offset -= seg->byte_count;
3495 char_offset += seg->char_count;
3500 g_assert (seg != NULL);
3502 /* Now byte_offset is the offset into the current segment,
3503 and char_offset is the start of the current segment.
3504 Optimize the case where no chars use > 1 byte */
3505 if (seg->byte_count == seg->char_count)
3506 return char_offset + byte_offset;
3509 if (seg->type == >k_text_char_type)
3510 return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3513 g_assert (seg->char_count == 1);
3514 g_assert (byte_offset == 0);
3522 gtk_text_line_char_to_byte (GtkTextLine *line,
3525 g_warning ("FIXME not implemented");
3530 /* FIXME sync with char_locate (or figure out a clean
3531 way to merge the two functions) */
3533 gtk_text_line_byte_locate (GtkTextLine *line,
3535 GtkTextLineSegment **segment,
3536 GtkTextLineSegment **any_segment,
3537 gint *seg_byte_offset,
3538 gint *line_byte_offset)
3540 GtkTextLineSegment *seg;
3541 GtkTextLineSegment *after_prev_indexable;
3542 GtkTextLineSegment *after_last_indexable;
3543 GtkTextLineSegment *last_indexable;
3547 g_return_if_fail (line != NULL);
3549 if (byte_offset < 0)
3551 /* -1 means end of line; we here assume no line is
3552 longer than 1 bazillion bytes, of course we assumed
3553 that anyway since we'd wrap around... */
3555 byte_offset = G_MAXINT;
3559 *any_segment = NULL;
3562 offset = byte_offset;
3564 last_indexable = NULL;
3565 after_last_indexable = line->segments;
3566 after_prev_indexable = line->segments;
3567 seg = line->segments;
3569 /* The loop ends when we're inside a segment;
3570 last_indexable refers to the last segment
3571 we passed entirely. */
3572 while (seg && offset >= seg->byte_count)
3574 if (seg->char_count > 0)
3576 offset -= seg->byte_count;
3577 bytes_in_line += seg->byte_count;
3578 last_indexable = seg;
3579 after_prev_indexable = after_last_indexable;
3580 after_last_indexable = last_indexable->next;
3588 /* We went off the end of the line */
3589 *segment = last_indexable;
3590 *any_segment = after_prev_indexable;
3591 /* subtracting 1 is OK, we know it's a newline at the end. */
3592 offset = (*segment)->byte_count - 1;
3593 bytes_in_line -= (*segment)->byte_count;
3598 if (after_last_indexable != NULL)
3599 *any_segment = after_last_indexable;
3601 *any_segment = *segment;
3604 /* Override any_segment if we're in the middle of a segment. */
3606 *any_segment = *segment;
3608 *seg_byte_offset = offset;
3610 g_assert (*segment != NULL);
3611 g_assert (*any_segment != NULL);
3612 g_assert (*seg_byte_offset < (*segment)->byte_count);
3614 *line_byte_offset = bytes_in_line + *seg_byte_offset;
3617 /* FIXME sync with byte_locate (or figure out a clean
3618 way to merge the two functions) */
3620 gtk_text_line_char_locate (GtkTextLine *line,
3622 GtkTextLineSegment **segment,
3623 GtkTextLineSegment **any_segment,
3624 gint *seg_char_offset,
3625 gint *line_char_offset)
3627 GtkTextLineSegment *seg;
3628 GtkTextLineSegment *after_prev_indexable;
3629 GtkTextLineSegment *after_last_indexable;
3630 GtkTextLineSegment *last_indexable;
3634 g_return_if_fail (line != NULL);
3636 if (char_offset < 0)
3638 /* -1 means end of line; we here assume no line is
3639 longer than 1 bazillion chars, of course we assumed
3640 that anyway since we'd wrap around... */
3642 char_offset = G_MAXINT;
3646 *any_segment = NULL;
3649 offset = char_offset;
3651 last_indexable = NULL;
3652 after_last_indexable = line->segments;
3653 after_prev_indexable = line->segments;
3654 seg = line->segments;
3656 /* The loop ends when we're inside a segment;
3657 last_indexable refers to the last segment
3658 we passed entirely. */
3659 while (seg && offset >= seg->char_count)
3661 if (seg->char_count > 0)
3663 offset -= seg->char_count;
3664 chars_in_line += seg->char_count;
3665 last_indexable = seg;
3666 after_prev_indexable = after_last_indexable;
3667 after_last_indexable = last_indexable->next;
3675 /* We went off the end of the line */
3676 *segment = last_indexable;
3677 *any_segment = after_prev_indexable;
3678 /* subtracting 1 is OK, we know it's a newline at the end. */
3679 offset = (*segment)->char_count - 1;
3680 chars_in_line -= (*segment)->char_count;
3685 if (after_last_indexable != NULL)
3686 *any_segment = after_last_indexable;
3688 *any_segment = *segment;
3691 /* Override any_segment if we're in the middle of a segment. */
3693 *any_segment = *segment;
3695 *seg_char_offset = offset;
3697 g_assert (*segment != NULL);
3698 g_assert (*any_segment != NULL);
3699 g_assert (*seg_char_offset < (*segment)->char_count);
3701 *line_char_offset = chars_in_line + *seg_char_offset;
3705 gtk_text_line_byte_to_char_offsets (GtkTextLine *line,
3707 gint *line_char_offset,
3708 gint *seg_char_offset)
3710 GtkTextLineSegment *seg;
3713 g_return_if_fail (line != NULL);
3714 g_return_if_fail (byte_offset >= 0);
3716 *line_char_offset = 0;
3718 offset = byte_offset;
3719 seg = line->segments;
3721 while (offset >= seg->byte_count)
3723 offset -= seg->byte_count;
3724 *line_char_offset += seg->char_count;
3726 g_assert (seg != NULL); /* means an invalid char offset */
3729 g_assert (seg->char_count > 0); /* indexable. */
3731 /* offset is now the number of bytes into the current segment we
3732 * want to go. Count chars into the current segment.
3735 if (seg->type == >k_text_char_type)
3737 *seg_char_offset = g_utf8_strlen (seg->body.chars, offset);
3739 g_assert (*seg_char_offset < seg->char_count);
3741 *line_char_offset += *seg_char_offset;
3745 g_assert (offset == 0);
3746 *seg_char_offset = 0;
3751 gtk_text_line_char_to_byte_offsets (GtkTextLine *line,
3753 gint *line_byte_offset,
3754 gint *seg_byte_offset)
3756 GtkTextLineSegment *seg;
3759 g_return_if_fail (line != NULL);
3760 g_return_if_fail (char_offset >= 0);
3762 *line_byte_offset = 0;
3764 offset = char_offset;
3765 seg = line->segments;
3767 while (offset >= seg->char_count)
3769 offset -= seg->char_count;
3770 *line_byte_offset += seg->byte_count;
3772 g_assert (seg != NULL); /* means an invalid char offset */
3775 g_assert (seg->char_count > 0); /* indexable. */
3777 /* offset is now the number of chars into the current segment we
3778 want to go. Count bytes into the current segment. */
3780 if (seg->type == >k_text_char_type)
3782 *seg_byte_offset = 0;
3786 const char * start = seg->body.chars + *seg_byte_offset;
3788 bytes = g_utf8_next_char (start) - start;
3789 *seg_byte_offset += bytes;
3793 g_assert (*seg_byte_offset < seg->byte_count);
3795 *line_byte_offset += *seg_byte_offset;
3799 g_assert (offset == 0);
3800 *seg_byte_offset = 0;
3805 node_compare (GtkTextBTreeNode *lhs,
3806 GtkTextBTreeNode *rhs)
3808 GtkTextBTreeNode *iter;
3809 GtkTextBTreeNode *node;
3810 GtkTextBTreeNode *common_parent;
3811 GtkTextBTreeNode *parent_of_lower;
3812 GtkTextBTreeNode *parent_of_higher;
3813 gboolean lhs_is_lower;
3814 GtkTextBTreeNode *lower;
3815 GtkTextBTreeNode *higher;
3817 /* This function assumes that lhs and rhs are not underneath each
3824 if (lhs->level < rhs->level)
3826 lhs_is_lower = TRUE;
3832 lhs_is_lower = FALSE;
3837 /* Algorithm: find common parent of lhs/rhs. Save the child nodes
3838 * of the common parent we used to reach the common parent; the
3839 * ordering of these child nodes in the child list is the ordering
3843 /* Get on the same level (may be on same level already) */
3845 while (node->level < higher->level)
3846 node = node->parent;
3848 g_assert (node->level == higher->level);
3850 g_assert (node != higher); /* Happens if lower is underneath higher */
3852 /* Go up until we have two children with a common parent.
3854 parent_of_lower = node;
3855 parent_of_higher = higher;
3857 while (parent_of_lower->parent != parent_of_higher->parent)
3859 parent_of_lower = parent_of_lower->parent;
3860 parent_of_higher = parent_of_higher->parent;
3863 g_assert (parent_of_lower->parent == parent_of_higher->parent);
3865 common_parent = parent_of_lower->parent;
3867 g_assert (common_parent != NULL);
3869 /* See which is first in the list of common_parent's children */
3870 iter = common_parent->children.node;
3871 while (iter != NULL)
3873 if (iter == parent_of_higher)
3875 /* higher is less than lower */
3878 return 1; /* lhs > rhs */
3882 else if (iter == parent_of_lower)
3884 /* lower is less than higher */
3887 return -1; /* lhs < rhs */
3895 g_assert_not_reached ();
3899 /* remember that tag == NULL means "any tag" */
3901 gtk_text_line_next_could_contain_tag (GtkTextLine *line,
3905 GtkTextBTreeNode *node;
3906 GtkTextTagInfo *info;
3907 gboolean below_tag_root;
3909 g_return_val_if_fail (line != NULL, NULL);
3911 if (gtk_debug_flags & GTK_DEBUG_TEXT)
3912 gtk_text_btree_check (tree);
3916 /* Right now we can only offer linear-search if the user wants
3917 * to know about any tag toggle at all.
3919 return gtk_text_line_next (line);
3922 /* Our tag summaries only have node precision, not line
3923 precision. This means that if any line under a node could contain a
3924 tag, then any of the others could also contain a tag.
3926 In the future we could have some mechanism to keep track of how
3927 many toggles we've found under a node so far, since we have a
3928 count of toggles under the node. But for now I'm going with KISS.
3931 /* return same-node line, if any. */
3935 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3939 if (info->tag_root == NULL)
3942 if (info->tag_root == line->parent)
3943 return NULL; /* we were at the last line under the tag root */
3945 /* We need to go up out of this node, and on to the next one with
3946 toggles for the target tag. If we're below the tag root, we need to
3947 find the next node below the tag root that has tag summaries. If
3948 we're not below the tag root, we need to see if the tag root is
3949 after us in the tree, and if so, return the first line underneath
3952 node = line->parent;
3953 below_tag_root = FALSE;
3954 while (node != NULL)
3956 if (node == info->tag_root)
3958 below_tag_root = TRUE;
3962 node = node->parent;
3967 node = line->parent;
3968 while (node != info->tag_root)
3970 if (node->next == NULL)
3971 node = node->parent;
3976 if (gtk_text_btree_node_has_tag (node, tag))
3986 ordering = node_compare (line->parent, info->tag_root);
3990 /* Tag root is ahead of us, so search there. */
3991 node = info->tag_root;
3996 /* Tag root is after us, so no more lines that
3997 * could contain the tag.
4002 g_assert_not_reached ();
4007 g_assert (node != NULL);
4009 /* We have to find the first sub-node of this node that contains
4013 while (node->level > 0)
4015 g_assert (node != NULL); /* If this fails, it likely means an
4016 incorrect tag summary led us on a
4017 wild goose chase down this branch of
4019 node = node->children.node;
4020 while (node != NULL)
4022 if (gtk_text_btree_node_has_tag (node, tag))
4028 g_assert (node != NULL);
4029 g_assert (node->level == 0);
4031 return node->children.line;
4035 prev_line_under_node (GtkTextBTreeNode *node,
4040 prev = node->children.line;
4046 while (prev->next != line)
4056 gtk_text_line_previous_could_contain_tag (GtkTextLine *line,
4060 GtkTextBTreeNode *node;
4061 GtkTextBTreeNode *found_node = NULL;
4062 GtkTextTagInfo *info;
4063 gboolean below_tag_root;
4065 GtkTextBTreeNode *line_ancestor;
4066 GtkTextBTreeNode *line_ancestor_parent;
4068 /* See next_could_contain_tag () for more extensive comments
4069 * on what's going on here.
4072 g_return_val_if_fail (line != NULL, NULL);
4074 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4075 gtk_text_btree_check (tree);
4079 /* Right now we can only offer linear-search if the user wants
4080 * to know about any tag toggle at all.
4082 return gtk_text_line_previous (line);
4085 /* Return same-node line, if any. */
4086 prev = prev_line_under_node (line->parent, line);
4090 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4094 if (info->tag_root == NULL)
4097 if (info->tag_root == line->parent)
4098 return NULL; /* we were at the first line under the tag root */
4100 /* Are we below the tag root */
4101 node = line->parent;
4102 below_tag_root = FALSE;
4103 while (node != NULL)
4105 if (node == info->tag_root)
4107 below_tag_root = TRUE;
4111 node = node->parent;
4116 /* Look for a previous node under this tag root that has our
4120 /* this assertion holds because line->parent is not the
4121 * tag root, we are below the tag root, and the tag
4124 g_assert (line->parent->parent != NULL);
4126 line_ancestor = line->parent;
4127 line_ancestor_parent = line->parent->parent;
4129 node = line_ancestor_parent->children.node;
4130 while (node != line_ancestor &&
4131 line_ancestor != info->tag_root)
4133 GSList *child_nodes = NULL;
4136 /* Create reverse-order list of nodes before
4139 while (node != line_ancestor
4142 child_nodes = g_slist_prepend (child_nodes, node);
4147 /* Try to find a node with our tag on it in the list */
4151 GtkTextBTreeNode *this_node = tmp->data;
4153 g_assert (this_node != line_ancestor);
4155 if (gtk_text_btree_node_has_tag (this_node, tag))
4157 found_node = this_node;
4158 g_slist_free (child_nodes);
4162 tmp = g_slist_next (tmp);
4165 g_slist_free (child_nodes);
4167 /* Didn't find anything on this level; go up one level. */
4168 line_ancestor = line_ancestor_parent;
4169 line_ancestor_parent = line_ancestor->parent;
4171 node = line_ancestor_parent->children.node;
4181 ordering = node_compare (line->parent, info->tag_root);
4185 /* Tag root is ahead of us, so no more lines
4192 /* Tag root is after us, so grab last tagged
4193 * line underneath the tag root.
4195 found_node = info->tag_root;
4199 g_assert_not_reached ();
4204 g_assert (found_node != NULL);
4206 /* We have to find the last sub-node of this node that contains
4211 while (node->level > 0)
4213 GSList *child_nodes = NULL;
4215 g_assert (node != NULL); /* If this fails, it likely means an
4216 incorrect tag summary led us on a
4217 wild goose chase down this branch of
4220 node = node->children.node;
4221 while (node != NULL)
4223 child_nodes = g_slist_prepend (child_nodes, node);
4227 node = NULL; /* detect failure to find a child node. */
4230 while (iter != NULL)
4232 if (gtk_text_btree_node_has_tag (iter->data, tag))
4234 /* recurse into this node. */
4239 iter = g_slist_next (iter);
4242 g_slist_free (child_nodes);
4244 g_assert (node != NULL);
4247 g_assert (node != NULL);
4248 g_assert (node->level == 0);
4250 /* this assertion is correct, but slow. */
4251 /* g_assert (node_compare (node, line->parent) < 0); */
4253 /* Return last line in this node. */
4255 prev = node->children.line;
4263 * Non-public function implementations
4267 summary_list_destroy (Summary *summary)
4270 while (summary != NULL)
4272 next = summary->next;
4273 summary_destroy (summary);
4279 get_last_line (GtkTextBTree *tree)
4281 if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
4287 n_lines = gtk_text_btree_line_count (tree);
4289 g_assert (n_lines >= 1); /* num_lines doesn't return bogus last line. */
4291 line = gtk_text_btree_get_line (tree, n_lines, &real_line);
4293 tree->end_iter_line_stamp = tree->chars_changed_stamp;
4294 tree->end_iter_line = line;
4297 return tree->end_iter_line;
4305 gtk_text_line_new (void)
4309 line = g_new0(GtkTextLine, 1);
4315 gtk_text_line_destroy (GtkTextBTree *tree, GtkTextLine *line)
4317 GtkTextLineData *ld;
4318 GtkTextLineData *next;
4320 g_return_if_fail (line != NULL);
4327 view = gtk_text_btree_get_view (tree, ld->view_id);
4329 g_assert (view != NULL);
4332 gtk_text_layout_free_line_data (view->layout, line, ld);
4341 gtk_text_line_set_parent (GtkTextLine *line,
4342 GtkTextBTreeNode *node)
4344 if (line->parent == node)
4346 line->parent = node;
4347 gtk_text_btree_node_invalidate_upward (node, NULL);
4351 cleanup_line (GtkTextLine *line)
4353 GtkTextLineSegment *seg, **prev_p;
4357 * Make a pass over all of the segments in the line, giving each
4358 * a chance to clean itself up. This could potentially change
4359 * the structure of the line, e.g. by merging two segments
4360 * together or having two segments cancel themselves; if so,
4361 * then repeat the whole process again, since the first structure
4362 * change might make other structure changes possible. Repeat
4363 * until eventually there are no changes.
4370 for (prev_p = &line->segments, seg = *prev_p;
4372 prev_p = &(*prev_p)->next, seg = *prev_p)
4374 if (seg->type->cleanupFunc != NULL)
4376 *prev_p = (*seg->type->cleanupFunc)(seg, line);
4389 node_data_new (gpointer view_id)
4393 nd = g_new (NodeData, 1);
4395 nd->view_id = view_id;
4405 node_data_destroy (NodeData *nd)
4412 node_data_list_destroy (NodeData *nd)
4418 while (iter != NULL)
4421 node_data_destroy (iter);
4427 node_data_find (NodeData *nd, gpointer view_id)
4431 if (nd->view_id == view_id)
4439 summary_destroy (Summary *summary)
4441 /* Fill with error-triggering garbage */
4442 summary->info = (void*)0x1;
4443 summary->toggle_count = 567;
4444 summary->next = (void*)0x1;
4448 static GtkTextBTreeNode*
4449 gtk_text_btree_node_new (void)
4451 GtkTextBTreeNode *node;
4453 node = g_new (GtkTextBTreeNode, 1);
4455 node->node_data = NULL;
4461 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
4462 GtkTextTagInfo *info,
4467 summary = node->summary;
4468 while (summary != NULL)
4470 if (summary->info == info)
4472 summary->toggle_count += adjust;
4476 summary = summary->next;
4479 if (summary == NULL)
4481 /* didn't find a summary for our tag. */
4482 g_return_if_fail (adjust > 0);
4483 summary = g_new (Summary, 1);
4484 summary->info = info;
4485 summary->toggle_count = adjust;
4486 summary->next = node->summary;
4487 node->summary = summary;
4491 /* Note that the tag root and above do not have summaries
4492 for the tag; only nodes below the tag root have
4495 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4499 summary = node->summary;
4500 while (summary != NULL)
4503 summary->info->tag == tag)
4506 summary = summary->next;
4512 /* Add node and all children to the damage region. */
4514 gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node)
4518 nd = node->node_data;
4525 if (node->level == 0)
4529 line = node->children.line;
4530 while (line != NULL)
4532 GtkTextLineData *ld;
4546 GtkTextBTreeNode *child;
4548 child = node->children.node;
4550 while (child != NULL)
4552 gtk_text_btree_node_invalidate_downward (child);
4554 child = child->next;
4560 gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node, gpointer view_id)
4562 GtkTextBTreeNode *iter;
4565 while (iter != NULL)
4571 nd = node_data_find (iter->node_data, view_id);
4573 if (nd == NULL || !nd->valid)
4574 break; /* Once a node is invalid, we know its parents are as well. */
4580 gboolean should_continue = FALSE;
4582 nd = iter->node_data;
4587 should_continue = TRUE;
4594 if (!should_continue)
4595 break; /* This node was totally invalidated, so are its
4599 iter = iter->parent;
4605 * gtk_text_btree_is_valid:
4606 * @tree: a #GtkTextBTree
4607 * @view_id: ID for the view
4609 * Check to see if the entire #GtkTextBTree is valid or not for
4612 * Return value: %TRUE if the entire #GtkTextBTree is valid
4615 gtk_text_btree_is_valid (GtkTextBTree *tree,
4619 g_return_val_if_fail (tree != NULL, FALSE);
4621 nd = node_data_find (tree->root_node->node_data, view_id);
4622 return (nd && nd->valid);
4625 typedef struct _ValidateState ValidateState;
4627 struct _ValidateState
4629 gint remaining_pixels;
4630 gboolean in_validation;
4637 gtk_text_btree_node_validate (BTreeView *view,
4638 GtkTextBTreeNode *node,
4640 ValidateState *state)
4642 gint node_valid = TRUE;
4643 gint node_width = 0;
4644 gint node_height = 0;
4646 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4647 g_return_if_fail (!nd->valid);
4649 if (node->level == 0)
4651 GtkTextLine *line = node->children.line;
4652 GtkTextLineData *ld;
4654 /* Iterate over leading valid lines */
4655 while (line != NULL)
4657 ld = gtk_text_line_get_data (line, view_id);
4659 if (!ld || !ld->valid)
4661 else if (state->in_validation)
4663 state->in_validation = FALSE;
4668 state->y += ld->height;
4669 node_width = MAX (ld->width, node_width);
4670 node_height += ld->height;
4676 state->in_validation = TRUE;
4678 /* Iterate over invalid lines */
4679 while (line != NULL)
4681 ld = gtk_text_line_get_data (line, view_id);
4683 if (ld && ld->valid)
4688 state->old_height += ld->height;
4689 ld = gtk_text_layout_wrap (view->layout, line, ld);
4690 state->new_height += ld->height;
4692 node_width = MAX (ld->width, node_width);
4693 node_height += ld->height;
4695 state->remaining_pixels -= ld->height;
4696 if (state->remaining_pixels <= 0)
4706 /* Iterate over the remaining lines */
4707 while (line != NULL)
4709 ld = gtk_text_line_get_data (line, view_id);
4710 state->in_validation = FALSE;
4712 if (!ld || !ld->valid)
4717 node_width = MAX (ld->width, node_width);
4718 node_height += ld->height;
4726 GtkTextBTreeNode *child;
4729 child = node->children.node;
4731 /* Iterate over leading valid nodes */
4734 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4736 if (!child_nd->valid)
4738 else if (state->in_validation)
4740 state->in_validation = FALSE;
4745 state->y += child_nd->height;
4746 node_width = MAX (node_width, child_nd->width);
4747 node_height += child_nd->height;
4750 child = child->next;
4753 /* Iterate over invalid nodes */
4756 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4758 if (child_nd->valid)
4762 gtk_text_btree_node_validate (view, child, view_id, state);
4764 if (!child_nd->valid)
4766 node_width = MAX (node_width, child_nd->width);
4767 node_height += child_nd->height;
4769 if (!state->in_validation || state->remaining_pixels <= 0)
4771 child = child->next;
4776 child = child->next;
4779 /* Iterate over the remaining lines */
4782 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4783 state->in_validation = FALSE;
4785 if (!child_nd->valid)
4788 node_width = MAX (child_nd->width, node_width);
4789 node_height += child_nd->height;
4791 child = child->next;
4795 nd->width = node_width;
4796 nd->height = node_height;
4797 nd->valid = node_valid;
4801 * gtk_text_btree_validate:
4802 * @tree: a #GtkTextBTree
4804 * @max_pixels: the maximum number of pixels to validate. (No more
4805 * than one paragraph beyond this limit will be validated)
4806 * @y: location to store starting y coordinate of validated region
4807 * @old_height: location to store old height of validated region
4808 * @new_height: location to store new height of validated region
4810 * Validate a single contiguous invalid region of a #GtkTextBTree for
4813 * Return value: %TRUE if a region has been validated, %FALSE if the
4814 * entire tree was already valid.
4817 gtk_text_btree_validate (GtkTextBTree *tree,
4826 g_return_val_if_fail (tree != NULL, FALSE);
4828 view = gtk_text_btree_get_view (tree, view_id);
4829 g_return_val_if_fail (view != NULL, FALSE);
4831 if (!gtk_text_btree_is_valid (tree, view_id))
4833 ValidateState state;
4835 state.remaining_pixels = max_pixels;
4836 state.in_validation = FALSE;
4838 state.old_height = 0;
4839 state.new_height = 0;
4841 gtk_text_btree_node_validate (view,
4848 *old_height = state.old_height;
4850 *new_height = state.new_height;
4852 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4853 gtk_text_btree_check (tree);
4862 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
4866 gboolean *valid_out)
4870 gboolean valid = TRUE;
4872 if (node->level == 0)
4874 GtkTextLine *line = node->children.line;
4876 while (line != NULL)
4878 GtkTextLineData *ld = gtk_text_line_get_data (line, view_id);
4880 if (!ld || !ld->valid)
4885 width = MAX (ld->width, width);
4886 height += ld->height;
4894 GtkTextBTreeNode *child = node->children.node;
4898 NodeData *child_nd = node_data_find (child->node_data, view_id);
4900 if (!child_nd || !child_nd->valid)
4905 width = MAX (child_nd->width, width);
4906 height += child_nd->height;
4909 child = child->next;
4914 *height_out = height;
4919 /* Recompute the validity and size of the view data for a given
4920 * view at this node from the immediate children of the node
4923 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
4926 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4931 gtk_text_btree_node_compute_view_aggregates (node, view_id,
4932 &width, &height, &valid);
4934 nd->height = height;
4941 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
4946 gtk_text_btree_node_check_valid (node, view_id);
4947 node = node->parent;
4952 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
4955 if (node->level == 0)
4957 return gtk_text_btree_node_check_valid (node, view_id);
4961 GtkTextBTreeNode *child = node->children.node;
4963 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4971 NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
4973 if (!child_nd->valid)
4975 nd->width = MAX (child_nd->width, nd->width);
4976 nd->height += child_nd->height;
4978 child = child->next;
4987 * gtk_text_btree_validate_line:
4988 * @tree: a #GtkTextBTree
4989 * @line: line to validate
4990 * @view_id: view ID for the view to validate
4992 * Revalidate a single line of the btree for the given view, propagate
4993 * results up through the entire tree.
4996 gtk_text_btree_validate_line (GtkTextBTree *tree,
5000 GtkTextLineData *ld;
5001 GtkTextLine *last_line;
5004 g_return_if_fail (tree != NULL);
5005 g_return_if_fail (line != NULL);
5007 view = gtk_text_btree_get_view (tree, view_id);
5008 g_return_if_fail (view != NULL);
5010 ld = gtk_text_line_get_data (line, view_id);
5011 if (!ld || !ld->valid)
5013 ld = gtk_text_layout_wrap (view->layout, line, ld);
5014 last_line = get_last_line (tree);
5016 gtk_text_btree_node_check_valid_upward (line->parent, view_id);
5021 gtk_text_btree_node_remove_view (BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
5023 if (node->level == 0)
5027 line = node->children.line;
5028 while (line != NULL)
5030 GtkTextLineData *ld;
5032 ld = gtk_text_line_remove_data (line, view_id);
5035 gtk_text_layout_free_line_data (view->layout, line, ld);
5042 GtkTextBTreeNode *child;
5044 child = node->children.node;
5046 while (child != NULL)
5049 gtk_text_btree_node_remove_view (view, child, view_id);
5051 child = child->next;
5055 gtk_text_btree_node_remove_data (node, view_id);
5059 gtk_text_btree_node_destroy (GtkTextBTree *tree, GtkTextBTreeNode *node)
5061 if (node->level == 0)
5064 GtkTextLineSegment *seg;
5066 while (node->children.line != NULL)
5068 line = node->children.line;
5069 node->children.line = line->next;
5070 while (line->segments != NULL)
5072 seg = line->segments;
5073 line->segments = seg->next;
5075 if (GTK_IS_TEXT_MARK_SEGMENT (seg))
5077 /* Set the mark as deleted */
5078 seg->body.mark.tree = NULL;
5079 seg->body.mark.line = NULL;
5082 (*seg->type->deleteFunc) (seg, line, 1);
5084 gtk_text_line_destroy (tree, line);
5089 GtkTextBTreeNode *childPtr;
5091 while (node->children.node != NULL)
5093 childPtr = node->children.node;
5094 node->children.node = childPtr->next;
5095 gtk_text_btree_node_destroy (tree, childPtr);
5099 summary_list_destroy (node->summary);
5100 node_data_list_destroy (node->node_data);
5105 gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node, gpointer view_id)
5109 nd = node->node_data;
5112 if (nd->view_id == view_id)
5119 nd = node_data_new (view_id);
5121 if (node->node_data)
5122 nd->next = node->node_data;
5124 node->node_data = nd;
5131 gtk_text_btree_node_remove_data (GtkTextBTreeNode *node, gpointer view_id)
5137 nd = node->node_data;
5140 if (nd->view_id == view_id)
5151 prev->next = nd->next;
5153 if (node->node_data == nd)
5154 node->node_data = nd->next;
5158 node_data_destroy (nd);
5162 gtk_text_btree_node_get_size (GtkTextBTreeNode *node, gpointer view_id,
5163 gint *width, gint *height)
5167 g_return_if_fail (width != NULL);
5168 g_return_if_fail (height != NULL);
5170 nd = gtk_text_btree_node_ensure_data (node, view_id);
5175 *height = nd->height;
5178 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5179 * here isn't quite right, since for a lot of operations we want to
5180 * know which children of the common parent correspond to the two nodes
5181 * (e.g., when computing the order of two iters)
5183 static GtkTextBTreeNode *
5184 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5185 GtkTextBTreeNode *node2)
5187 while (node1->level < node2->level)
5188 node1 = node1->parent;
5189 while (node2->level < node1->level)
5190 node2 = node2->parent;
5191 while (node1 != node2)
5193 node1 = node1->parent;
5194 node2 = node2->parent;
5205 gtk_text_btree_get_view (GtkTextBTree *tree, gpointer view_id)
5210 while (view != NULL)
5212 if (view->view_id == view_id)
5221 get_tree_bounds (GtkTextBTree *tree,
5225 gtk_text_btree_get_iter_at_line_char (tree, start, 0, 0);
5226 gtk_text_btree_get_last_iter (tree, end);
5230 tag_changed_cb (GtkTextTagTable *table,
5232 gboolean size_changed,
5237 /* We need to queue a relayout on all regions that are tagged with
5244 if (gtk_text_btree_get_iter_at_first_toggle (tree, &start, tag))
5246 /* Must be a last toggle if there was a first one. */
5247 gtk_text_btree_get_iter_at_last_toggle (tree, &end, tag);
5248 gtk_text_btree_invalidate_region (tree,
5255 /* We only need to queue a redraw, not a relayout */
5260 while (view != NULL)
5264 gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5265 gtk_text_layout_changed (view->layout, 0, height, height);
5273 tag_removed_cb (GtkTextTagTable *table,
5277 /* Remove the tag from the tree */
5282 get_tree_bounds (tree, &start, &end);
5284 gtk_text_btree_tag (&start, &end, tag, FALSE);
5285 gtk_text_btree_remove_tag_info (tree, tag);
5289 /* Rebalance the out-of-whack node "node" */
5291 gtk_text_btree_rebalance (GtkTextBTree *tree,
5292 GtkTextBTreeNode *node)
5295 * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5296 * up through the tree one GtkTextBTreeNode at a time until the root
5297 * GtkTextBTreeNode has been processed.
5300 while (node != NULL)
5302 GtkTextBTreeNode *new_node, *child;
5307 * Check to see if the GtkTextBTreeNode has too many children. If it does,
5308 * then split off all but the first MIN_CHILDREN into a separate
5309 * GtkTextBTreeNode following the original one. Then repeat until the
5310 * GtkTextBTreeNode has a decent size.
5313 if (node->num_children > MAX_CHILDREN)
5318 * If the GtkTextBTreeNode being split is the root
5319 * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5323 if (node->parent == NULL)
5325 new_node = gtk_text_btree_node_new ();
5326 new_node->parent = NULL;
5327 new_node->next = NULL;
5328 new_node->summary = NULL;
5329 new_node->level = node->level + 1;
5330 new_node->children.node = node;
5331 recompute_node_counts (tree, new_node);
5332 tree->root_node = new_node;
5334 new_node = gtk_text_btree_node_new ();
5335 new_node->parent = node->parent;
5336 new_node->next = node->next;
5337 node->next = new_node;
5338 new_node->summary = NULL;
5339 new_node->level = node->level;
5340 new_node->num_children = node->num_children - MIN_CHILDREN;
5341 if (node->level == 0)
5343 for (i = MIN_CHILDREN-1,
5344 line = node->children.line;
5345 i > 0; i--, line = line->next)
5347 /* Empty loop body. */
5349 new_node->children.line = line->next;
5354 for (i = MIN_CHILDREN-1,
5355 child = node->children.node;
5356 i > 0; i--, child = child->next)
5358 /* Empty loop body. */
5360 new_node->children.node = child->next;
5363 recompute_node_counts (tree, node);
5364 node->parent->num_children++;
5366 if (node->num_children <= MAX_CHILDREN)
5368 recompute_node_counts (tree, node);
5374 while (node->num_children < MIN_CHILDREN)
5376 GtkTextBTreeNode *other;
5377 GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5378 GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5379 int total_children, first_children, i;
5382 * Too few children for this GtkTextBTreeNode. If this is the root then,
5383 * it's OK for it to have less than MIN_CHILDREN children
5384 * as long as it's got at least two. If it has only one
5385 * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5386 * the tree and use its child as the new root.
5389 if (node->parent == NULL)
5391 if ((node->num_children == 1) && (node->level > 0))
5393 tree->root_node = node->children.node;
5394 tree->root_node->parent = NULL;
5395 summary_list_destroy (node->summary);
5402 * Not the root. Make sure that there are siblings to
5406 if (node->parent->num_children < 2)
5408 gtk_text_btree_rebalance (tree, node->parent);
5413 * Find a sibling neighbor to borrow from, and arrange for
5414 * node to be the earlier of the pair.
5417 if (node->next == NULL)
5419 for (other = node->parent->children.node;
5420 other->next != node;
5421 other = other->next)
5423 /* Empty loop body. */
5430 * We're going to either merge the two siblings together
5431 * into one GtkTextBTreeNode or redivide the children among them to
5432 * balance their loads. As preparation, join their two
5433 * child lists into a single list and remember the half-way
5434 * point in the list.
5437 total_children = node->num_children + other->num_children;
5438 first_children = total_children/2;
5439 if (node->children.node == NULL)
5441 node->children = other->children;
5442 other->children.node = NULL;
5443 other->children.line = NULL;
5445 if (node->level == 0)
5449 for (line = node->children.line, i = 1;
5451 line = line->next, i++)
5453 if (i == first_children)
5458 line->next = other->children.line;
5459 while (i <= first_children)
5468 GtkTextBTreeNode *child;
5470 for (child = node->children.node, i = 1;
5471 child->next != NULL;
5472 child = child->next, i++)
5474 if (i <= first_children)
5476 if (i == first_children)
5478 halfwaynode = child;
5482 child->next = other->children.node;
5483 while (i <= first_children)
5485 halfwaynode = child;
5486 child = child->next;
5492 * If the two siblings can simply be merged together, do it.
5495 if (total_children <= MAX_CHILDREN)
5497 recompute_node_counts (tree, node);
5498 node->next = other->next;
5499 node->parent->num_children--;
5500 summary_list_destroy (other->summary);
5506 * The siblings can't be merged, so just divide their
5507 * children evenly between them.
5510 if (node->level == 0)
5512 other->children.line = halfwayline->next;
5513 halfwayline->next = NULL;
5517 other->children.node = halfwaynode->next;
5518 halfwaynode->next = NULL;
5521 recompute_node_counts (tree, node);
5522 recompute_node_counts (tree, other);
5525 node = node->parent;
5530 post_insert_fixup (GtkTextBTree *tree,
5532 gint line_count_delta,
5533 gint char_count_delta)
5536 GtkTextBTreeNode *node;
5539 * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5540 * point, then rebalance the tree if necessary.
5543 for (node = line->parent ; node != NULL;
5544 node = node->parent)
5546 node->num_lines += line_count_delta;
5547 node->num_chars += char_count_delta;
5549 node = line->parent;
5550 node->num_children += line_count_delta;
5552 if (node->num_children > MAX_CHILDREN)
5554 gtk_text_btree_rebalance (tree, node);
5557 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5558 gtk_text_btree_check (tree);
5561 static GtkTextTagInfo*
5562 gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
5565 GtkTextTagInfo *info;
5569 list = tree->tag_infos;
5570 while (list != NULL)
5573 if (info->tag == tag)
5576 list = g_slist_next (list);
5582 static GtkTextTagInfo*
5583 gtk_text_btree_get_tag_info (GtkTextBTree *tree,
5586 GtkTextTagInfo *info;
5588 info = gtk_text_btree_get_existing_tag_info (tree, tag);
5592 /* didn't find it, create. */
5594 info = g_new (GtkTextTagInfo, 1);
5597 gtk_object_ref (GTK_OBJECT (tag));
5598 info->tag_root = NULL;
5599 info->toggle_count = 0;
5601 tree->tag_infos = g_slist_prepend (tree->tag_infos, info);
5608 gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
5611 GtkTextTagInfo *info;
5616 list = tree->tag_infos;
5617 while (list != NULL)
5620 if (info->tag == tag)
5624 prev->next = list->next;
5628 tree->tag_infos = list->next;
5631 g_slist_free (list);
5633 gtk_object_unref (GTK_OBJECT (info->tag));
5639 list = g_slist_next (list);
5642 g_assert_not_reached ();
5647 recompute_level_zero_counts (GtkTextBTreeNode *node)
5650 GtkTextLineSegment *seg;
5652 g_assert (node->level == 0);
5654 line = node->children.line;
5655 while (line != NULL)
5657 node->num_children++;
5660 if (line->parent != node)
5661 gtk_text_line_set_parent (line, node);
5663 seg = line->segments;
5667 node->num_chars += seg->char_count;
5669 if (((seg->type != >k_text_toggle_on_type)
5670 && (seg->type != >k_text_toggle_off_type))
5671 || !(seg->body.toggle.inNodeCounts))
5677 GtkTextTagInfo *info;
5679 info = seg->body.toggle.info;
5681 gtk_text_btree_node_adjust_toggle_count (node, info, 1);
5692 recompute_level_nonzero_counts (GtkTextBTreeNode *node)
5695 GtkTextBTreeNode *child;
5697 g_assert (node->level > 0);
5699 child = node->children.node;
5700 while (child != NULL)
5702 node->num_children += 1;
5703 node->num_lines += child->num_lines;
5704 node->num_chars += child->num_chars;
5706 if (child->parent != node)
5708 child->parent = node;
5709 gtk_text_btree_node_invalidate_upward (node, NULL);
5712 summary = child->summary;
5713 while (summary != NULL)
5715 gtk_text_btree_node_adjust_toggle_count (node,
5717 summary->toggle_count);
5719 summary = summary->next;
5722 child = child->next;
5727 *----------------------------------------------------------------------
5729 * recompute_node_counts --
5731 * This procedure is called to recompute all the counts in a GtkTextBTreeNode
5732 * (tags, child information, etc.) by scanning the information in
5733 * its descendants. This procedure is called during rebalancing
5734 * when a GtkTextBTreeNode's child structure has changed.
5740 * The tag counts for node are modified to reflect its current
5741 * child structure, as are its num_children, num_lines, num_chars fields.
5742 * Also, all of the childrens' parent fields are made to point
5745 *----------------------------------------------------------------------
5749 recompute_node_counts (GtkTextBTree *tree, GtkTextBTreeNode *node)
5752 Summary *summary, *summary2;
5755 * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
5756 * the existing Summary records (most of them will probably be reused).
5759 summary = node->summary;
5760 while (summary != NULL)
5762 summary->toggle_count = 0;
5763 summary = summary->next;
5766 node->num_children = 0;
5767 node->num_lines = 0;
5768 node->num_chars = 0;
5771 * Scan through the children, adding the childrens' tag counts into
5772 * the GtkTextBTreeNode's tag counts and adding new Summary structures if
5776 if (node->level == 0)
5777 recompute_level_zero_counts (node);
5779 recompute_level_nonzero_counts (node);
5784 gtk_text_btree_node_check_valid (node, view->view_id);
5789 * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
5790 * records that still have a zero count, or that have all the toggles.
5791 * The GtkTextBTreeNode with the children that account for all the tags toggles
5792 * have no summary information, and they become the tag_root for the tag.
5796 for (summary = node->summary; summary != NULL; )
5798 if (summary->toggle_count > 0 &&
5799 summary->toggle_count < summary->info->toggle_count)
5801 if (node->level == summary->info->tag_root->level)
5804 * The tag's root GtkTextBTreeNode split and some toggles left.
5805 * The tag root must move up a level.
5807 summary->info->tag_root = node->parent;
5810 summary = summary->next;
5813 if (summary->toggle_count == summary->info->toggle_count)
5816 * A GtkTextBTreeNode merge has collected all the toggles under
5817 * one GtkTextBTreeNode. Push the root down to this level.
5819 summary->info->tag_root = node;
5821 if (summary2 != NULL)
5823 summary2->next = summary->next;
5824 summary_destroy (summary);
5825 summary = summary2->next;
5829 node->summary = summary->next;
5830 summary_destroy (summary);
5831 summary = node->summary;
5837 _gtk_change_node_toggle_count (GtkTextBTreeNode *node,
5838 GtkTextTagInfo *info,
5839 gint delta) /* may be negative */
5841 Summary *summary, *prevPtr;
5842 GtkTextBTreeNode *node2Ptr;
5843 int rootLevel; /* Level of original tag root */
5845 info->toggle_count += delta;
5847 if (info->tag_root == (GtkTextBTreeNode *) NULL)
5849 info->tag_root = node;
5854 * Note the level of the existing root for the tag so we can detect
5855 * if it needs to be moved because of the toggle count change.
5858 rootLevel = info->tag_root->level;
5861 * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
5862 * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
5866 for ( ; node != info->tag_root; node = node->parent)
5869 * See if there's already an entry for this tag for this GtkTextBTreeNode. If so,
5870 * perhaps all we have to do is adjust its count.
5873 for (prevPtr = NULL, summary = node->summary;
5875 prevPtr = summary, summary = summary->next)
5877 if (summary->info == info)
5882 if (summary != NULL)
5884 summary->toggle_count += delta;
5885 if (summary->toggle_count > 0 &&
5886 summary->toggle_count < info->toggle_count)
5890 if (summary->toggle_count != 0)
5893 * Should never find a GtkTextBTreeNode with max toggle count at this
5894 * point (there shouldn't have been a summary entry in the
5898 g_error ("%s: bad toggle count (%d) max (%d)",
5899 G_STRLOC, summary->toggle_count, info->toggle_count);
5903 * Zero toggle count; must remove this tag from the list.
5906 if (prevPtr == NULL)
5908 node->summary = summary->next;
5912 prevPtr->next = summary->next;
5914 summary_destroy (summary);
5919 * This tag isn't currently in the summary information list.
5922 if (rootLevel == node->level)
5926 * The old tag root is at the same level in the tree as this
5927 * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode. Move the tag root up
5928 * a level, in the hopes that it will now cover this GtkTextBTreeNode
5929 * as well as the old root (if not, we'll move it up again
5930 * the next time through the loop). To push it up one level
5931 * we copy the original toggle count into the summary
5932 * information at the old root and change the root to its
5933 * parent GtkTextBTreeNode.
5936 GtkTextBTreeNode *rootnode = info->tag_root;
5937 summary = (Summary *) g_malloc (sizeof (Summary));
5938 summary->info = info;
5939 summary->toggle_count = info->toggle_count - delta;
5940 summary->next = rootnode->summary;
5941 rootnode->summary = summary;
5942 rootnode = rootnode->parent;
5943 rootLevel = rootnode->level;
5944 info->tag_root = rootnode;
5946 summary = (Summary *) g_malloc (sizeof (Summary));
5947 summary->info = info;
5948 summary->toggle_count = delta;
5949 summary->next = node->summary;
5950 node->summary = summary;
5955 * If we've decremented the toggle count, then it may be necessary
5956 * to push the tag root down one or more levels.
5963 if (info->toggle_count == 0)
5965 info->tag_root = (GtkTextBTreeNode *) NULL;
5968 node = info->tag_root;
5969 while (node->level > 0)
5972 * See if a single child GtkTextBTreeNode accounts for all of the tag's
5973 * toggles. If so, push the root down one level.
5976 for (node2Ptr = node->children.node;
5977 node2Ptr != (GtkTextBTreeNode *)NULL ;
5978 node2Ptr = node2Ptr->next)
5980 for (prevPtr = NULL, summary = node2Ptr->summary;
5982 prevPtr = summary, summary = summary->next)
5984 if (summary->info == info)
5989 if (summary == NULL)
5993 if (summary->toggle_count != info->toggle_count)
5996 * No GtkTextBTreeNode has all toggles, so the root is still valid.
6003 * This GtkTextBTreeNode has all the toggles, so push down the root.
6006 if (prevPtr == NULL)
6008 node2Ptr->summary = summary->next;
6012 prevPtr->next = summary->next;
6014 summary_destroy (summary);
6015 info->tag_root = node2Ptr;
6018 node = info->tag_root;
6023 *----------------------------------------------------------------------
6027 * This is a utility procedure used by gtk_text_btree_get_tags. It
6028 * increments the count for a particular tag, adding a new
6029 * entry for that tag if there wasn't one previously.
6035 * The information at *tagInfoPtr may be modified, and the arrays
6036 * may be reallocated to make them larger.
6038 *----------------------------------------------------------------------
6042 inc_count (GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
6047 for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
6048 count > 0; tag_p++, count--)
6052 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
6058 * There isn't currently an entry for this tag, so we have to
6059 * make a new one. If the arrays are full, then enlarge the
6063 if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
6065 GtkTextTag **newTags;
6066 int *newCounts, newSize;
6068 newSize = 2*tagInfoPtr->arraySize;
6069 newTags = (GtkTextTag **) g_malloc ((unsigned)
6070 (newSize*sizeof (GtkTextTag *)));
6071 memcpy ((void *) newTags, (void *) tagInfoPtr->tags,
6072 tagInfoPtr->arraySize *sizeof (GtkTextTag *));
6073 g_free ((char *) tagInfoPtr->tags);
6074 tagInfoPtr->tags = newTags;
6075 newCounts = (int *) g_malloc ((unsigned) (newSize*sizeof (int)));
6076 memcpy ((void *) newCounts, (void *) tagInfoPtr->counts,
6077 tagInfoPtr->arraySize *sizeof (int));
6078 g_free ((char *) tagInfoPtr->counts);
6079 tagInfoPtr->counts = newCounts;
6080 tagInfoPtr->arraySize = newSize;
6083 tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
6084 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
6085 tagInfoPtr->numTags++;
6089 gtk_text_btree_link_segment (GtkTextLineSegment *seg,
6090 const GtkTextIter *iter)
6092 GtkTextLineSegment *prev;
6096 line = gtk_text_iter_get_text_line (iter);
6097 tree = gtk_text_iter_get_btree (iter);
6099 prev = gtk_text_line_segment_split (iter);
6102 seg->next = line->segments;
6103 line->segments = seg;
6107 seg->next = prev->next;
6110 cleanup_line (line);
6111 segments_changed (tree);
6113 if (gtk_debug_flags & GTK_DEBUG_TEXT)
6114 gtk_text_btree_check (tree);
6118 gtk_text_btree_unlink_segment (GtkTextBTree *tree,
6119 GtkTextLineSegment *seg,
6122 GtkTextLineSegment *prev;
6124 if (line->segments == seg)
6126 line->segments = seg->next;
6130 for (prev = line->segments; prev->next != seg;
6133 /* Empty loop body. */
6135 prev->next = seg->next;
6137 cleanup_line (line);
6138 segments_changed (tree);
6142 * This is here because it requires BTree internals, it logically
6143 * belongs in gtktextsegment.c
6148 *--------------------------------------------------------------
6150 * _gtk_toggle_segment_check_func --
6152 * This procedure is invoked to perform consistency checks
6153 * on toggle segments.
6159 * If a consistency problem is found the procedure g_errors.
6161 *--------------------------------------------------------------
6165 _gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6171 if (segPtr->byte_count != 0)
6173 g_error ("toggle_segment_check_func: segment had non-zero size");
6175 if (!segPtr->body.toggle.inNodeCounts)
6177 g_error ("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6179 needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6180 for (summary = line->parent->summary; ;
6181 summary = summary->next)
6183 if (summary == NULL)
6187 g_error ("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6194 if (summary->info == segPtr->body.toggle.info)
6198 g_error ("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6210 gtk_text_btree_node_view_check_consistency (GtkTextBTreeNode *node,
6217 gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6218 &width, &height, &valid);
6219 if (nd->width != width ||
6220 nd->height != height ||
6221 !nd->valid != !valid)
6223 g_error ("Node aggregates for view %p are invalid:\n"
6224 "Are (%d,%d,%s), should be (%d,%d,%s)",
6226 nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6227 width, height, valid ? "TRUE" : "FALSE");
6232 gtk_text_btree_node_check_consistency (GtkTextBTreeNode *node)
6234 GtkTextBTreeNode *childnode;
6235 Summary *summary, *summary2;
6237 GtkTextLineSegment *segPtr;
6238 int num_children, num_lines, num_chars, toggle_count, min_children;
6239 GtkTextLineData *ld;
6242 if (node->parent != NULL)
6244 min_children = MIN_CHILDREN;
6246 else if (node->level > 0)
6253 if ((node->num_children < min_children)
6254 || (node->num_children > MAX_CHILDREN))
6256 g_error ("gtk_text_btree_node_check_consistency: bad child count (%d)",
6257 node->num_children);
6260 nd = node->node_data;
6263 gtk_text_btree_node_view_check_consistency (node, nd);
6270 if (node->level == 0)
6272 for (line = node->children.line; line != NULL;
6275 if (line->parent != node)
6277 g_error ("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6279 if (line->segments == NULL)
6281 g_error ("gtk_text_btree_node_check_consistency: line has no segments");
6287 /* Just ensuring we don't segv while doing this loop */
6292 for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6294 if (segPtr->type->checkFunc != NULL)
6296 (*segPtr->type->checkFunc)(segPtr, line);
6298 if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6299 && (segPtr->next != NULL)
6300 && (segPtr->next->byte_count == 0)
6301 && (segPtr->next->type->leftGravity))
6303 g_error ("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6305 if ((segPtr->next == NULL)
6306 && (segPtr->type != >k_text_char_type))
6308 g_error ("gtk_text_btree_node_check_consistency: line ended with wrong type");
6311 num_chars += segPtr->char_count;
6320 for (childnode = node->children.node; childnode != NULL;
6321 childnode = childnode->next)
6323 if (childnode->parent != node)
6325 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6327 if (childnode->level != (node->level-1))
6329 g_error ("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6330 node->level, childnode->level);
6332 gtk_text_btree_node_check_consistency (childnode);
6333 for (summary = childnode->summary; summary != NULL;
6334 summary = summary->next)
6336 for (summary2 = node->summary; ;
6337 summary2 = summary2->next)
6339 if (summary2 == NULL)
6341 if (summary->info->tag_root == node)
6345 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6346 summary->info->tag->name,
6347 "present in parent summaries");
6349 if (summary->info == summary2->info)
6356 num_lines += childnode->num_lines;
6357 num_chars += childnode->num_chars;
6360 if (num_children != node->num_children)
6362 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6363 num_children, node->num_children);
6365 if (num_lines != node->num_lines)
6367 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6368 num_lines, node->num_lines);
6370 if (num_chars != node->num_chars)
6372 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6373 num_chars, node->num_chars);
6376 for (summary = node->summary; summary != NULL;
6377 summary = summary->next)
6379 if (summary->info->toggle_count == summary->toggle_count)
6381 g_error ("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6382 summary->info->tag->name);
6385 if (node->level == 0)
6387 for (line = node->children.line; line != NULL;
6390 for (segPtr = line->segments; segPtr != NULL;
6391 segPtr = segPtr->next)
6393 if ((segPtr->type != >k_text_toggle_on_type)
6394 && (segPtr->type != >k_text_toggle_off_type))
6398 if (segPtr->body.toggle.info == summary->info)
6400 if (!segPtr->body.toggle.inNodeCounts)
6401 g_error ("Toggle segment not in the node counts");
6410 for (childnode = node->children.node;
6412 childnode = childnode->next)
6414 for (summary2 = childnode->summary;
6416 summary2 = summary2->next)
6418 if (summary2->info == summary->info)
6420 toggle_count += summary2->toggle_count;
6425 if (toggle_count != summary->toggle_count)
6427 g_error ("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6428 toggle_count, summary->toggle_count);
6430 for (summary2 = summary->next; summary2 != NULL;
6431 summary2 = summary2->next)
6433 if (summary2->info == summary->info)
6435 g_error ("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6436 summary->info->tag->name);
6443 listify_foreach (GtkTextTag *tag, gpointer user_data)
6445 GSList** listp = user_data;
6447 *listp = g_slist_prepend (*listp, tag);
6451 list_of_tags (GtkTextTagTable *table)
6453 GSList *list = NULL;
6455 gtk_text_tag_table_foreach (table, listify_foreach, &list);
6461 gtk_text_btree_check (GtkTextBTree *tree)
6464 GtkTextBTreeNode *node;
6466 GtkTextLineSegment *seg;
6468 GSList *taglist = NULL;
6470 GtkTextTagInfo *info;
6473 * Make sure that the tag toggle counts and the tag root pointers are OK.
6475 for (taglist = list_of_tags (tree->table);
6476 taglist != NULL ; taglist = taglist->next)
6478 tag = taglist->data;
6479 info = gtk_text_btree_get_existing_tag_info (tree, tag);
6482 node = info->tag_root;
6485 if (info->toggle_count != 0)
6487 g_error ("gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6488 tag->name, info->toggle_count);
6490 continue; /* no ranges for the tag */
6492 else if (info->toggle_count == 0)
6494 g_error ("gtk_text_btree_check found root for \"%s\" with no toggles",
6497 else if (info->toggle_count & 1)
6499 g_error ("gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6500 tag->name, info->toggle_count);
6502 for (summary = node->summary; summary != NULL;
6503 summary = summary->next)
6505 if (summary->info->tag == tag)
6507 g_error ("gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6511 if (node->level > 0)
6513 for (node = node->children.node ; node != NULL ;
6516 for (summary = node->summary; summary != NULL;
6517 summary = summary->next)
6519 if (summary->info->tag == tag)
6521 count += summary->toggle_count;
6528 GtkTextLineSegmentClass * last = NULL;
6530 for (line = node->children.line ; line != NULL ;
6533 for (seg = line->segments; seg != NULL;
6536 if ((seg->type == >k_text_toggle_on_type ||
6537 seg->type == >k_text_toggle_off_type) &&
6538 seg->body.toggle.info->tag == tag)
6540 if (last == seg->type)
6541 g_error ("Two consecutive toggles on or off weren't merged");
6542 if (!seg->body.toggle.inNodeCounts)
6543 g_error ("Toggle segment not in the node counts");
6552 if (count != info->toggle_count)
6554 g_error ("gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
6555 info->toggle_count, tag->name, count);
6560 g_slist_free (taglist);
6564 * Call a recursive procedure to do the main body of checks.
6567 node = tree->root_node;
6568 gtk_text_btree_node_check_consistency (tree->root_node);
6571 * Make sure that there are at least two lines in the text and
6572 * that the last line has no characters except a newline.
6575 if (node->num_lines < 2)
6577 g_error ("gtk_text_btree_check: less than 2 lines in tree");
6579 if (node->num_chars < 2)
6581 g_error ("gtk_text_btree_check: less than 2 chars in tree");
6583 while (node->level > 0)
6585 node = node->children.node;
6586 while (node->next != NULL)
6591 line = node->children.line;
6592 while (line->next != NULL)
6596 seg = line->segments;
6597 while ((seg->type == >k_text_toggle_off_type)
6598 || (seg->type == >k_text_right_mark_type)
6599 || (seg->type == >k_text_left_mark_type))
6602 * It's OK to toggle a tag off in the last line, but
6603 * not to start a new range. It's also OK to have marks
6609 if (seg->type != >k_text_char_type)
6611 g_error ("gtk_text_btree_check: last line has bogus segment type");
6613 if (seg->next != NULL)
6615 g_error ("gtk_text_btree_check: last line has too many segments");
6617 if (seg->byte_count != 1)
6619 g_error ("gtk_text_btree_check: last line has wrong # characters: %d",
6622 if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
6624 g_error ("gtk_text_btree_check: last line had bad value: %s",
6629 void gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line);
6630 void gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment* seg);
6631 void gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent);
6632 void gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
6635 gtk_text_btree_spew (GtkTextBTree *tree)
6640 printf ("%d lines in tree %p\n",
6641 gtk_text_btree_line_count (tree), tree);
6643 line = gtk_text_btree_get_line (tree, 0, &real_line);
6645 while (line != NULL)
6647 gtk_text_btree_spew_line (tree, line);
6648 line = gtk_text_line_next (line);
6651 printf ("=================== Tag information\n");
6656 list = tree->tag_infos;
6658 while (list != NULL)
6660 GtkTextTagInfo *info;
6664 printf (" tag `%s': root at %p, toggle count %d\n",
6665 info->tag->name, info->tag_root, info->toggle_count);
6667 list = g_slist_next (list);
6670 if (tree->tag_infos == NULL)
6672 printf (" (no tags in the tree)\n");
6676 printf ("=================== Tree nodes\n");
6679 gtk_text_btree_spew_node (tree->root_node, 0);
6684 gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
6687 GtkTextLineSegment *seg;
6689 spaces = g_strnfill (indent, ' ');
6691 printf ("%sline %p chars %d bytes %d\n",
6693 gtk_text_line_char_count (line),
6694 gtk_text_line_byte_count (line));
6696 seg = line->segments;
6699 if (seg->type == >k_text_char_type)
6701 gchar* str = g_strndup (seg->body.chars, MIN (seg->byte_count, 10));
6710 printf ("%s chars `%s'...\n", spaces, str);
6713 else if (seg->type == >k_text_right_mark_type)
6715 printf ("%s right mark `%s' visible: %d\n",
6717 seg->body.mark.name,
6718 seg->body.mark.visible);
6720 else if (seg->type == >k_text_left_mark_type)
6722 printf ("%s left mark `%s' visible: %d\n",
6724 seg->body.mark.name,
6725 seg->body.mark.visible);
6727 else if (seg->type == >k_text_toggle_on_type ||
6728 seg->type == >k_text_toggle_off_type)
6730 printf ("%s tag `%s' %s\n",
6731 spaces, seg->body.toggle.info->tag->name,
6732 seg->type == >k_text_toggle_off_type ? "off" : "on");
6742 gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent)
6745 GtkTextBTreeNode *iter;
6748 spaces = g_strnfill (indent, ' ');
6750 printf ("%snode %p level %d children %d lines %d chars %d\n",
6751 spaces, node, node->level,
6752 node->num_children, node->num_lines, node->num_chars);
6757 printf ("%s %d toggles of `%s' below this node\n",
6758 spaces, s->toggle_count, s->info->tag->name);
6764 if (node->level > 0)
6766 iter = node->children.node;
6767 while (iter != NULL)
6769 gtk_text_btree_spew_node (iter, indent + 2);
6776 GtkTextLine *line = node->children.line;
6777 while (line != NULL)
6779 gtk_text_btree_spew_line_short (line, indent + 2);
6787 gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line)
6789 GtkTextLineSegment * seg;
6791 printf ("%4d| line: %p parent: %p next: %p\n",
6792 gtk_text_line_get_number (line), line, line->parent, line->next);
6794 seg = line->segments;
6798 gtk_text_btree_spew_segment (tree, seg);
6804 gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment * seg)
6806 printf (" segment: %p type: %s bytes: %d chars: %d\n",
6807 seg, seg->type->name, seg->byte_count, seg->char_count);
6809 if (seg->type == >k_text_char_type)
6811 gchar* str = g_strndup (seg->body.chars, seg->byte_count);
6812 printf (" `%s'\n", str);
6815 else if (seg->type == >k_text_right_mark_type)
6817 printf (" right mark `%s' visible: %d not_deleteable: %d\n",
6818 seg->body.mark.name,
6819 seg->body.mark.visible,
6820 seg->body.mark.not_deleteable);
6822 else if (seg->type == >k_text_left_mark_type)
6824 printf (" left mark `%s' visible: %d not_deleteable: %d\n",
6825 seg->body.mark.name,
6826 seg->body.mark.visible,
6827 seg->body.mark.not_deleteable);
6829 else if (seg->type == >k_text_toggle_on_type ||
6830 seg->type == >k_text_toggle_off_type)
6832 printf (" tag `%s' priority %d\n",
6833 seg->body.toggle.info->tag->name,
6834 seg->body.toggle.info->tag->priority);