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
2474 if (redraw_selections &&
2475 (mark == tree->insert_mark->segment ||
2476 mark == tree->selection_bound_mark->segment))
2478 GtkTextIter old_pos;
2480 gtk_text_btree_get_iter_at_mark (tree, &old_pos,
2481 mark->body.mark.obj);
2482 redisplay_region (tree, &old_pos, where);
2486 * don't let visible marks be after the final newline of the
2490 if (mark->body.mark.visible)
2492 ensure_not_off_end (tree, mark, &iter);
2495 /* Redraw the mark's old location. */
2496 redisplay_mark_if_visible (mark);
2498 /* Unlink mark from its current location.
2499 This could hose our iterator... */
2500 gtk_text_btree_unlink_segment (tree, mark,
2501 mark->body.mark.line);
2502 mark->body.mark.line = gtk_text_iter_get_text_line (&iter);
2503 g_assert (mark->body.mark.line == gtk_text_iter_get_text_line (&iter));
2505 segments_changed (tree); /* make sure the iterator recomputes its
2510 mark = _gtk_mark_segment_new (tree,
2514 mark->body.mark.line = gtk_text_iter_get_text_line (&iter);
2516 if (mark->body.mark.name)
2517 g_hash_table_insert (tree->mark_table,
2518 mark->body.mark.name,
2522 /* Link mark into new location */
2523 gtk_text_btree_link_segment (mark, &iter);
2525 /* Invalidate some iterators. */
2526 segments_changed (tree);
2529 * update the screen at the mark's new location.
2532 redisplay_mark_if_visible (mark);
2539 gtk_text_btree_set_mark (GtkTextBTree *tree,
2540 GtkTextMark *existing_mark,
2542 gboolean left_gravity,
2543 const GtkTextIter *iter,
2544 gboolean should_exist)
2546 GtkTextLineSegment *seg;
2548 seg = real_set_mark (tree, existing_mark,
2549 name, left_gravity, iter, should_exist,
2552 return seg ? seg->body.mark.obj : NULL;
2556 gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2560 GtkTextIter tmp_start, tmp_end;
2562 gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2564 gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2565 tree->selection_bound_mark);
2567 if (gtk_text_iter_equal (&tmp_start, &tmp_end))
2579 gtk_text_iter_reorder (&tmp_start, &tmp_end);
2592 gtk_text_btree_place_cursor (GtkTextBTree *tree,
2593 const GtkTextIter *iter)
2595 GtkTextIter start, end;
2597 if (gtk_text_btree_get_selection_bounds (tree, &start, &end))
2598 redisplay_region (tree, &start, &end);
2600 /* Move insert AND selection_bound before we redisplay */
2601 real_set_mark (tree, tree->insert_mark,
2602 "insert", FALSE, iter, TRUE, FALSE);
2603 real_set_mark (tree, tree->selection_bound_mark,
2604 "selection_bound", FALSE, iter, TRUE, FALSE);
2608 gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2613 g_return_if_fail (tree != NULL);
2614 g_return_if_fail (name != NULL);
2616 mark = g_hash_table_lookup (tree->mark_table,
2619 gtk_text_btree_remove_mark (tree, mark);
2623 gtk_text_btree_remove_mark (GtkTextBTree *tree,
2626 GtkTextLineSegment *segment;
2628 g_return_if_fail (mark != NULL);
2629 g_return_if_fail (tree != NULL);
2631 segment = mark->segment;
2633 if (segment->body.mark.not_deleteable)
2635 g_warning ("Can't delete special mark `%s'", segment->body.mark.name);
2639 /* This calls cleanup_line and segments_changed */
2640 gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2642 if (segment->body.mark.name)
2643 g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2645 /* Remove the ref on the mark that belonged to the segment. */
2646 g_object_unref (G_OBJECT (mark));
2648 segment->body.mark.tree = NULL;
2649 segment->body.mark.line = NULL;
2653 gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2654 GtkTextMark *segment)
2656 return segment == tree->insert_mark;
2660 gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2661 GtkTextMark *segment)
2663 return segment == tree->selection_bound_mark;
2667 gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2670 GtkTextLineSegment *seg;
2672 g_return_val_if_fail (tree != NULL, NULL);
2673 g_return_val_if_fail (name != NULL, NULL);
2675 seg = g_hash_table_lookup (tree->mark_table, name);
2677 return seg ? seg->body.mark.obj : NULL;
2681 gtk_text_mark_set_visible (GtkTextMark *mark,
2684 GtkTextLineSegment *seg;
2686 g_return_if_fail (mark != NULL);
2688 seg = mark->segment;
2690 if (seg->body.mark.visible == setting)
2694 seg->body.mark.visible = setting;
2696 redisplay_mark (seg);
2701 gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
2704 GtkTextBTreeNode *node;
2705 GtkTextTagInfo *info;
2707 g_return_val_if_fail (tree != NULL, NULL);
2711 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2716 if (info->tag_root == NULL)
2719 node = info->tag_root;
2721 /* We know the tag root has instances of the given
2724 continue_outer_loop:
2725 g_assert (node != NULL);
2726 while (node->level > 0)
2728 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2729 node = node->children.node;
2730 while (node != NULL)
2732 if (gtk_text_btree_node_has_tag (node, tag))
2733 goto continue_outer_loop;
2737 g_assert (node != NULL);
2740 g_assert (node != NULL); /* The tag summaries said some node had
2743 g_assert (node->level == 0);
2745 return node->children.line;
2749 /* Looking for any tag at all (tag == NULL).
2750 Unfortunately this can't be done in a simple and efficient way
2751 right now; so I'm just going to return the
2752 first line in the btree. FIXME */
2753 return gtk_text_btree_get_line (tree, 0, NULL);
2758 gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
2761 GtkTextBTreeNode *node;
2762 GtkTextBTreeNode *last_node;
2764 GtkTextTagInfo *info;
2766 g_return_val_if_fail (tree != NULL, NULL);
2770 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2772 if (info->tag_root == NULL)
2775 node = info->tag_root;
2776 /* We know the tag root has instances of the given
2779 while (node->level > 0)
2781 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2783 node = node->children.node;
2784 while (node != NULL)
2786 if (gtk_text_btree_node_has_tag (node, tag))
2794 g_assert (node != NULL); /* The tag summaries said some node had
2797 g_assert (node->level == 0);
2799 /* Find the last line in this node */
2800 line = node->children.line;
2801 while (line->next != NULL)
2808 /* This search can't be done efficiently at the moment,
2809 at least not without complexity.
2810 So, we just return the last line.
2812 return gtk_text_btree_get_line (tree, -1, NULL);
2822 gtk_text_line_get_number (GtkTextLine *line)
2825 GtkTextBTreeNode *node, *parent, *node2;
2829 * First count how many lines precede this one in its level-0
2833 node = line->parent;
2835 for (line2 = node->children.line; line2 != line;
2836 line2 = line2->next)
2840 g_error ("gtk_text_btree_line_number couldn't find line");
2846 * Now work up through the levels of the tree one at a time,
2847 * counting how many lines are in GtkTextBTreeNodes preceding the current
2851 for (parent = node->parent ; parent != NULL;
2852 node = parent, parent = parent->parent)
2854 for (node2 = parent->children.node; node2 != node;
2855 node2 = node2->next)
2859 g_error ("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
2861 index += node2->num_lines;
2867 static GtkTextLineSegment*
2868 find_toggle_segment_before_char (GtkTextLine *line,
2872 GtkTextLineSegment *seg;
2873 GtkTextLineSegment *toggle_seg;
2878 seg = line->segments;
2879 while ( (index + seg->char_count) <= char_in_line )
2881 if (((seg->type == >k_text_toggle_on_type)
2882 || (seg->type == >k_text_toggle_off_type))
2883 && (seg->body.toggle.info->tag == tag))
2886 index += seg->char_count;
2893 static GtkTextLineSegment*
2894 find_toggle_segment_before_byte (GtkTextLine *line,
2898 GtkTextLineSegment *seg;
2899 GtkTextLineSegment *toggle_seg;
2904 seg = line->segments;
2905 while ( (index + seg->byte_count) <= byte_in_line )
2907 if (((seg->type == >k_text_toggle_on_type)
2908 || (seg->type == >k_text_toggle_off_type))
2909 && (seg->body.toggle.info->tag == tag))
2912 index += seg->byte_count;
2920 find_toggle_outside_current_line (GtkTextLine *line,
2924 GtkTextBTreeNode *node;
2925 GtkTextLine *sibling_line;
2926 GtkTextLineSegment *seg;
2927 GtkTextLineSegment *toggle_seg;
2929 GtkTextTagInfo *info = NULL;
2932 * No toggle in this line. Look for toggles for the tag in lines
2933 * that are predecessors of line but under the same
2934 * level-0 GtkTextBTreeNode.
2937 sibling_line = line->parent->children.line;
2938 while (sibling_line != line)
2940 seg = sibling_line->segments;
2943 if (((seg->type == >k_text_toggle_on_type)
2944 || (seg->type == >k_text_toggle_off_type))
2945 && (seg->body.toggle.info->tag == tag))
2951 sibling_line = sibling_line->next;
2954 if (toggle_seg != NULL)
2955 return (toggle_seg->type == >k_text_toggle_on_type);
2958 * No toggle in this GtkTextBTreeNode. Scan upwards through the ancestors of
2959 * this GtkTextBTreeNode, counting the number of toggles of the given tag in
2960 * siblings that precede that GtkTextBTreeNode.
2963 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2969 node = line->parent;
2970 while (node->parent != NULL)
2972 GtkTextBTreeNode *sibling_node;
2974 sibling_node = node->parent->children.node;
2975 while (sibling_node != node)
2979 summary = sibling_node->summary;
2980 while (summary != NULL)
2982 if (summary->info == info)
2983 toggles += summary->toggle_count;
2985 summary = summary->next;
2988 sibling_node = sibling_node->next;
2991 if (node == info->tag_root)
2994 node = node->parent;
2998 * An odd number of toggles means that the tag is present at the
3002 return (toggles & 1) != 0;
3005 /* FIXME this function is far too slow, for no good reason. */
3007 gtk_text_line_char_has_tag (GtkTextLine *line,
3012 GtkTextLineSegment *toggle_seg;
3014 g_return_val_if_fail (line != NULL, FALSE);
3017 * Check for toggles for the tag in the line but before
3018 * the char. If there is one, its type indicates whether or
3019 * not the character is tagged.
3022 toggle_seg = find_toggle_segment_before_char (line, char_in_line, tag);
3024 if (toggle_seg != NULL)
3025 return (toggle_seg->type == >k_text_toggle_on_type);
3027 return find_toggle_outside_current_line (line, tree, tag);
3031 gtk_text_line_byte_has_tag (GtkTextLine *line,
3036 GtkTextLineSegment *toggle_seg;
3038 g_return_val_if_fail (line != NULL, FALSE);
3041 * Check for toggles for the tag in the line but before
3042 * the char. If there is one, its type indicates whether or
3043 * not the character is tagged.
3046 toggle_seg = find_toggle_segment_before_byte (line, byte_in_line, tag);
3048 if (toggle_seg != NULL)
3049 return (toggle_seg->type == >k_text_toggle_on_type);
3051 return find_toggle_outside_current_line (line, tree, tag);
3055 gtk_text_line_is_last (GtkTextLine *line,
3058 return line == get_last_line (tree);
3062 gtk_text_line_next (GtkTextLine *line)
3064 GtkTextBTreeNode *node;
3066 if (line->next != NULL)
3071 * This was the last line associated with the particular parent
3072 * GtkTextBTreeNode. Search up the tree for the next GtkTextBTreeNode,
3073 * then search down from that GtkTextBTreeNode to find the first
3077 node = line->parent;
3078 while (node != NULL && node->next == NULL)
3079 node = node->parent;
3085 while (node->level > 0)
3087 node = node->children.node;
3090 g_assert (node->children.line != line);
3092 return node->children.line;
3097 gtk_text_line_previous (GtkTextLine *line)
3099 GtkTextBTreeNode *node;
3100 GtkTextBTreeNode *node2;
3104 * Find the line under this GtkTextBTreeNode just before the starting line.
3106 prev = line->parent->children.line; /* First line at leaf */
3107 while (prev != line)
3109 if (prev->next == line)
3115 g_error ("gtk_text_btree_previous_line ran out of lines");
3119 * This was the first line associated with the particular parent
3120 * GtkTextBTreeNode. Search up the tree for the previous GtkTextBTreeNode,
3121 * then search down from that GtkTextBTreeNode to find its last line.
3123 for (node = line->parent; ; node = node->parent)
3125 if (node == NULL || node->parent == NULL)
3127 else if (node != node->parent->children.node)
3131 for (node2 = node->parent->children.node; ;
3132 node2 = node2->children.node)
3134 while (node2->next != node)
3135 node2 = node2->next;
3137 if (node2->level == 0)
3143 for (prev = node2->children.line ; ; prev = prev->next)
3145 if (prev->next == NULL)
3149 g_assert_not_reached ();
3154 gtk_text_line_add_data (GtkTextLine *line,
3155 GtkTextLineData *data)
3157 g_return_if_fail (line != NULL);
3158 g_return_if_fail (data != NULL);
3159 g_return_if_fail (data->view_id != NULL);
3163 data->next = line->views;
3173 gtk_text_line_remove_data (GtkTextLine *line,
3176 GtkTextLineData *prev;
3177 GtkTextLineData *iter;
3179 g_return_val_if_fail (line != NULL, NULL);
3180 g_return_val_if_fail (view_id != NULL, NULL);
3184 while (iter != NULL)
3186 if (iter->view_id == view_id)
3195 prev->next = iter->next;
3197 line->views = iter->next;
3206 gtk_text_line_get_data (GtkTextLine *line,
3209 GtkTextLineData *iter;
3211 g_return_val_if_fail (line != NULL, NULL);
3212 g_return_val_if_fail (view_id != NULL, NULL);
3215 while (iter != NULL)
3217 if (iter->view_id == view_id)
3226 gtk_text_line_invalidate_wrap (GtkTextLine *line,
3227 GtkTextLineData *ld)
3229 /* For now this is totally unoptimized. FIXME?
3231 We could probably optimize the case where the width removed
3232 is less than the max width for the parent node,
3233 and the case where the height is unchanged when we re-wrap.
3236 g_return_if_fail (ld != NULL);
3239 gtk_text_btree_node_invalidate_upward (line->parent, ld->view_id);
3243 gtk_text_line_char_count (GtkTextLine *line)
3245 GtkTextLineSegment *seg;
3249 seg = line->segments;
3252 size += seg->char_count;
3259 gtk_text_line_byte_count (GtkTextLine *line)
3261 GtkTextLineSegment *seg;
3265 seg = line->segments;
3268 size += seg->byte_count;
3276 gtk_text_line_char_index (GtkTextLine *target_line)
3278 GSList *node_stack = NULL;
3279 GtkTextBTreeNode *iter;
3283 /* Push all our parent nodes onto a stack */
3284 iter = target_line->parent;
3286 g_assert (iter != NULL);
3288 while (iter != NULL)
3290 node_stack = g_slist_prepend (node_stack, iter);
3292 iter = iter->parent;
3295 /* Check that we have the root node on top of the stack. */
3296 g_assert (node_stack != NULL &&
3297 node_stack->data != NULL &&
3298 ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3300 /* Add up chars in all nodes before the nodes in our stack.
3304 iter = node_stack->data;
3305 while (iter != NULL)
3307 GtkTextBTreeNode *child_iter;
3308 GtkTextBTreeNode *next_node;
3310 next_node = node_stack->next ?
3311 node_stack->next->data : NULL;
3312 node_stack = g_slist_remove (node_stack, node_stack->data);
3314 if (iter->level == 0)
3316 /* stack should be empty when we're on the last node */
3317 g_assert (node_stack == NULL);
3318 break; /* Our children are now lines */
3321 g_assert (next_node != NULL);
3322 g_assert (iter != NULL);
3323 g_assert (next_node->parent == iter);
3325 /* Add up chars before us in the tree */
3326 child_iter = iter->children.node;
3327 while (child_iter != next_node)
3329 g_assert (child_iter != NULL);
3331 num_chars += child_iter->num_chars;
3333 child_iter = child_iter->next;
3339 g_assert (iter != NULL);
3340 g_assert (iter == target_line->parent);
3342 /* Since we don't store char counts in lines, only in segments, we
3343 have to iterate over the lines adding up segment char counts
3344 until we find our line. */
3345 line = iter->children.line;
3346 while (line != target_line)
3348 g_assert (line != NULL);
3350 num_chars += gtk_text_line_char_count (line);
3355 g_assert (line == target_line);
3361 gtk_text_line_byte_to_segment (GtkTextLine *line,
3365 GtkTextLineSegment *seg;
3368 g_return_val_if_fail (line != NULL, NULL);
3370 offset = byte_offset;
3371 seg = line->segments;
3373 while (offset >= seg->byte_count)
3375 g_assert (seg != NULL); /* means an invalid byte index */
3376 offset -= seg->byte_count;
3381 *seg_offset = offset;
3387 gtk_text_line_char_to_segment (GtkTextLine *line,
3391 GtkTextLineSegment *seg;
3394 g_return_val_if_fail (line != NULL, NULL);
3396 offset = char_offset;
3397 seg = line->segments;
3399 while (offset >= seg->char_count)
3401 g_assert (seg != NULL); /* means an invalid char index */
3402 offset -= seg->char_count;
3407 *seg_offset = offset;
3413 gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3417 GtkTextLineSegment *seg;
3420 g_return_val_if_fail (line != NULL, NULL);
3422 offset = byte_offset;
3423 seg = line->segments;
3425 while (offset > 0 && offset >= seg->byte_count)
3427 g_assert (seg != NULL); /* means an invalid byte index */
3428 offset -= seg->byte_count;
3433 *seg_offset = offset;
3439 gtk_text_line_char_to_any_segment (GtkTextLine *line,
3443 GtkTextLineSegment *seg;
3446 g_return_val_if_fail (line != NULL, NULL);
3448 offset = char_offset;
3449 seg = line->segments;
3451 while (offset > 0 && offset >= seg->char_count)
3453 g_assert (seg != NULL); /* means an invalid byte index */
3454 offset -= seg->char_count;
3459 *seg_offset = offset;
3465 gtk_text_line_byte_to_char (GtkTextLine *line,
3469 GtkTextLineSegment *seg;
3471 g_return_val_if_fail (line != NULL, 0);
3472 g_return_val_if_fail (byte_offset >= 0, 0);
3475 seg = line->segments;
3476 while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3477 the next segment) */
3479 g_assert (seg != NULL); /* our byte_index was bogus if this happens */
3481 byte_offset -= seg->byte_count;
3482 char_offset += seg->char_count;
3487 g_assert (seg != NULL);
3489 /* Now byte_offset is the offset into the current segment,
3490 and char_offset is the start of the current segment.
3491 Optimize the case where no chars use > 1 byte */
3492 if (seg->byte_count == seg->char_count)
3493 return char_offset + byte_offset;
3496 if (seg->type == >k_text_char_type)
3497 return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3500 g_assert (seg->char_count == 1);
3501 g_assert (byte_offset == 0);
3509 gtk_text_line_char_to_byte (GtkTextLine *line,
3512 g_warning ("FIXME not implemented");
3517 /* FIXME sync with char_locate (or figure out a clean
3518 way to merge the two functions) */
3520 gtk_text_line_byte_locate (GtkTextLine *line,
3522 GtkTextLineSegment **segment,
3523 GtkTextLineSegment **any_segment,
3524 gint *seg_byte_offset,
3525 gint *line_byte_offset)
3527 GtkTextLineSegment *seg;
3528 GtkTextLineSegment *after_prev_indexable;
3529 GtkTextLineSegment *after_last_indexable;
3530 GtkTextLineSegment *last_indexable;
3534 g_return_if_fail (line != NULL);
3536 if (byte_offset < 0)
3538 /* -1 means end of line; we here assume no line is
3539 longer than 1 bazillion bytes, of course we assumed
3540 that anyway since we'd wrap around... */
3542 byte_offset = G_MAXINT;
3546 *any_segment = NULL;
3549 offset = byte_offset;
3551 last_indexable = NULL;
3552 after_last_indexable = line->segments;
3553 after_prev_indexable = line->segments;
3554 seg = line->segments;
3556 /* The loop ends when we're inside a segment;
3557 last_indexable refers to the last segment
3558 we passed entirely. */
3559 while (seg && offset >= seg->byte_count)
3561 if (seg->char_count > 0)
3563 offset -= seg->byte_count;
3564 bytes_in_line += seg->byte_count;
3565 last_indexable = seg;
3566 after_prev_indexable = after_last_indexable;
3567 after_last_indexable = last_indexable->next;
3575 /* We went off the end of the line */
3576 *segment = last_indexable;
3577 *any_segment = after_prev_indexable;
3578 /* subtracting 1 is OK, we know it's a newline at the end. */
3579 offset = (*segment)->byte_count - 1;
3580 bytes_in_line -= (*segment)->byte_count;
3585 if (after_last_indexable != NULL)
3586 *any_segment = after_last_indexable;
3588 *any_segment = *segment;
3591 /* Override any_segment if we're in the middle of a segment. */
3593 *any_segment = *segment;
3595 *seg_byte_offset = offset;
3597 g_assert (*segment != NULL);
3598 g_assert (*any_segment != NULL);
3599 g_assert (*seg_byte_offset < (*segment)->byte_count);
3601 *line_byte_offset = bytes_in_line + *seg_byte_offset;
3604 /* FIXME sync with byte_locate (or figure out a clean
3605 way to merge the two functions) */
3607 gtk_text_line_char_locate (GtkTextLine *line,
3609 GtkTextLineSegment **segment,
3610 GtkTextLineSegment **any_segment,
3611 gint *seg_char_offset,
3612 gint *line_char_offset)
3614 GtkTextLineSegment *seg;
3615 GtkTextLineSegment *after_prev_indexable;
3616 GtkTextLineSegment *after_last_indexable;
3617 GtkTextLineSegment *last_indexable;
3621 g_return_if_fail (line != NULL);
3623 if (char_offset < 0)
3625 /* -1 means end of line; we here assume no line is
3626 longer than 1 bazillion chars, of course we assumed
3627 that anyway since we'd wrap around... */
3629 char_offset = G_MAXINT;
3633 *any_segment = NULL;
3636 offset = char_offset;
3638 last_indexable = NULL;
3639 after_last_indexable = line->segments;
3640 after_prev_indexable = line->segments;
3641 seg = line->segments;
3643 /* The loop ends when we're inside a segment;
3644 last_indexable refers to the last segment
3645 we passed entirely. */
3646 while (seg && offset >= seg->char_count)
3648 if (seg->char_count > 0)
3650 offset -= seg->char_count;
3651 chars_in_line += seg->char_count;
3652 last_indexable = seg;
3653 after_prev_indexable = after_last_indexable;
3654 after_last_indexable = last_indexable->next;
3662 /* We went off the end of the line */
3663 *segment = last_indexable;
3664 *any_segment = after_prev_indexable;
3665 /* subtracting 1 is OK, we know it's a newline at the end. */
3666 offset = (*segment)->char_count - 1;
3667 chars_in_line -= (*segment)->char_count;
3672 if (after_last_indexable != NULL)
3673 *any_segment = after_last_indexable;
3675 *any_segment = *segment;
3678 /* Override any_segment if we're in the middle of a segment. */
3680 *any_segment = *segment;
3682 *seg_char_offset = offset;
3684 g_assert (*segment != NULL);
3685 g_assert (*any_segment != NULL);
3686 g_assert (*seg_char_offset < (*segment)->char_count);
3688 *line_char_offset = chars_in_line + *seg_char_offset;
3692 gtk_text_line_byte_to_char_offsets (GtkTextLine *line,
3694 gint *line_char_offset,
3695 gint *seg_char_offset)
3697 GtkTextLineSegment *seg;
3700 g_return_if_fail (line != NULL);
3701 g_return_if_fail (byte_offset >= 0);
3703 *line_char_offset = 0;
3705 offset = byte_offset;
3706 seg = line->segments;
3708 while (offset >= seg->byte_count)
3710 offset -= seg->byte_count;
3711 *line_char_offset += seg->char_count;
3713 g_assert (seg != NULL); /* means an invalid char offset */
3716 g_assert (seg->char_count > 0); /* indexable. */
3718 /* offset is now the number of bytes into the current segment we
3719 want to go. Count chars into the current segment. */
3721 if (seg->type == >k_text_char_type)
3723 *seg_char_offset = g_utf8_strlen (seg->body.chars, offset);
3725 g_assert (*seg_char_offset < seg->char_count);
3727 *line_char_offset += *seg_char_offset;
3731 g_assert (offset == 0);
3732 *seg_char_offset = 0;
3737 gtk_text_line_char_to_byte_offsets (GtkTextLine *line,
3739 gint *line_byte_offset,
3740 gint *seg_byte_offset)
3742 GtkTextLineSegment *seg;
3745 g_return_if_fail (line != NULL);
3746 g_return_if_fail (char_offset >= 0);
3748 *line_byte_offset = 0;
3750 offset = char_offset;
3751 seg = line->segments;
3753 while (offset >= seg->char_count)
3755 offset -= seg->char_count;
3756 *line_byte_offset += seg->byte_count;
3758 g_assert (seg != NULL); /* means an invalid char offset */
3761 g_assert (seg->char_count > 0); /* indexable. */
3763 /* offset is now the number of chars into the current segment we
3764 want to go. Count bytes into the current segment. */
3766 if (seg->type == >k_text_char_type)
3768 *seg_byte_offset = 0;
3772 const char * start = seg->body.chars + *seg_byte_offset;
3774 bytes = g_utf8_next_char (start) - start;
3775 *seg_byte_offset += bytes;
3779 g_assert (*seg_byte_offset < seg->byte_count);
3781 *line_byte_offset += *seg_byte_offset;
3785 g_assert (offset == 0);
3786 *seg_byte_offset = 0;
3791 node_compare (GtkTextBTreeNode *lhs,
3792 GtkTextBTreeNode *rhs)
3794 GtkTextBTreeNode *iter;
3795 GtkTextBTreeNode *node;
3796 GtkTextBTreeNode *common_parent;
3797 GtkTextBTreeNode *parent_of_lower;
3798 GtkTextBTreeNode *parent_of_higher;
3799 gboolean lhs_is_lower;
3800 GtkTextBTreeNode *lower;
3801 GtkTextBTreeNode *higher;
3803 /* This function assumes that lhs and rhs are not underneath each
3810 if (lhs->level < rhs->level)
3812 lhs_is_lower = TRUE;
3818 lhs_is_lower = FALSE;
3823 /* Algorithm: find common parent of lhs/rhs. Save the child nodes
3824 * of the common parent we used to reach the common parent; the
3825 * ordering of these child nodes in the child list is the ordering
3829 /* Get on the same level (may be on same level already) */
3831 while (node->level < higher->level)
3832 node = node->parent;
3834 g_assert (node->level == higher->level);
3836 g_assert (node != higher); /* Happens if lower is underneath higher */
3838 /* Go up until we have two children with a common parent.
3840 parent_of_lower = node;
3841 parent_of_higher = higher;
3843 while (parent_of_lower->parent != parent_of_higher->parent)
3845 parent_of_lower = parent_of_lower->parent;
3846 parent_of_higher = parent_of_higher->parent;
3849 g_assert (parent_of_lower->parent == parent_of_higher->parent);
3851 common_parent = parent_of_lower->parent;
3853 g_assert (common_parent != NULL);
3855 /* See which is first in the list of common_parent's children */
3856 iter = common_parent->children.node;
3857 while (iter != NULL)
3859 if (iter == parent_of_higher)
3861 /* higher is less than lower */
3864 return 1; /* lhs > rhs */
3868 else if (iter == parent_of_lower)
3870 /* lower is less than higher */
3873 return -1; /* lhs < rhs */
3881 g_assert_not_reached ();
3885 /* remember that tag == NULL means "any tag" */
3887 gtk_text_line_next_could_contain_tag (GtkTextLine *line,
3891 GtkTextBTreeNode *node;
3892 GtkTextTagInfo *info;
3893 gboolean below_tag_root;
3895 g_return_val_if_fail (line != NULL, NULL);
3897 if (gtk_debug_flags & GTK_DEBUG_TEXT)
3898 gtk_text_btree_check (tree);
3902 /* Right now we can only offer linear-search if the user wants
3903 * to know about any tag toggle at all.
3905 return gtk_text_line_next (line);
3908 /* Our tag summaries only have node precision, not line
3909 precision. This means that if any line under a node could contain a
3910 tag, then any of the others could also contain a tag.
3912 In the future we could have some mechanism to keep track of how
3913 many toggles we've found under a node so far, since we have a
3914 count of toggles under the node. But for now I'm going with KISS.
3917 /* return same-node line, if any. */
3921 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3925 if (info->tag_root == NULL)
3928 if (info->tag_root == line->parent)
3929 return NULL; /* we were at the last line under the tag root */
3931 /* We need to go up out of this node, and on to the next one with
3932 toggles for the target tag. If we're below the tag root, we need to
3933 find the next node below the tag root that has tag summaries. If
3934 we're not below the tag root, we need to see if the tag root is
3935 after us in the tree, and if so, return the first line underneath
3938 node = line->parent;
3939 below_tag_root = FALSE;
3940 while (node != NULL)
3942 if (node == info->tag_root)
3944 below_tag_root = TRUE;
3948 node = node->parent;
3953 node = line->parent;
3954 while (node != info->tag_root)
3956 if (node->next == NULL)
3957 node = node->parent;
3962 if (gtk_text_btree_node_has_tag (node, tag))
3972 ordering = node_compare (line->parent, info->tag_root);
3976 /* Tag root is ahead of us, so search there. */
3977 node = info->tag_root;
3982 /* Tag root is after us, so no more lines that
3983 * could contain the tag.
3988 g_assert_not_reached ();
3993 g_assert (node != NULL);
3995 /* We have to find the first sub-node of this node that contains
3999 while (node->level > 0)
4001 g_assert (node != NULL); /* If this fails, it likely means an
4002 incorrect tag summary led us on a
4003 wild goose chase down this branch of
4005 node = node->children.node;
4006 while (node != NULL)
4008 if (gtk_text_btree_node_has_tag (node, tag))
4014 g_assert (node != NULL);
4015 g_assert (node->level == 0);
4017 return node->children.line;
4021 prev_line_under_node (GtkTextBTreeNode *node,
4026 prev = node->children.line;
4032 while (prev->next != line)
4042 gtk_text_line_previous_could_contain_tag (GtkTextLine *line,
4046 GtkTextBTreeNode *node;
4047 GtkTextBTreeNode *found_node = NULL;
4048 GtkTextTagInfo *info;
4049 gboolean below_tag_root;
4051 GtkTextBTreeNode *line_ancestor;
4052 GtkTextBTreeNode *line_ancestor_parent;
4054 /* See next_could_contain_tag () for more extensive comments
4055 * on what's going on here.
4058 g_return_val_if_fail (line != NULL, NULL);
4060 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4061 gtk_text_btree_check (tree);
4065 /* Right now we can only offer linear-search if the user wants
4066 * to know about any tag toggle at all.
4068 return gtk_text_line_previous (line);
4071 /* Return same-node line, if any. */
4072 prev = prev_line_under_node (line->parent, line);
4076 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4080 if (info->tag_root == NULL)
4083 if (info->tag_root == line->parent)
4084 return NULL; /* we were at the first line under the tag root */
4086 /* Are we below the tag root */
4087 node = line->parent;
4088 below_tag_root = FALSE;
4089 while (node != NULL)
4091 if (node == info->tag_root)
4093 below_tag_root = TRUE;
4097 node = node->parent;
4102 /* Look for a previous node under this tag root that has our
4106 /* this assertion holds because line->parent is not the
4107 * tag root, we are below the tag root, and the tag
4110 g_assert (line->parent->parent != NULL);
4112 line_ancestor = line->parent;
4113 line_ancestor_parent = line->parent->parent;
4115 node = line_ancestor_parent->children.node;
4116 while (node != line_ancestor &&
4117 line_ancestor != info->tag_root)
4119 GSList *child_nodes = NULL;
4122 /* Create reverse-order list of nodes before
4125 while (node != line_ancestor
4128 child_nodes = g_slist_prepend (child_nodes, node);
4133 /* Try to find a node with our tag on it in the list */
4137 GtkTextBTreeNode *this_node = tmp->data;
4139 g_assert (this_node != line_ancestor);
4141 if (gtk_text_btree_node_has_tag (this_node, tag))
4143 found_node = this_node;
4144 g_slist_free (child_nodes);
4148 tmp = g_slist_next (tmp);
4151 g_slist_free (child_nodes);
4153 /* Didn't find anything on this level; go up one level. */
4154 line_ancestor = line_ancestor_parent;
4155 line_ancestor_parent = line_ancestor->parent;
4157 node = line_ancestor_parent->children.node;
4167 ordering = node_compare (line->parent, info->tag_root);
4171 /* Tag root is ahead of us, so no more lines
4178 /* Tag root is after us, so grab last tagged
4179 * line underneath the tag root.
4181 found_node = info->tag_root;
4185 g_assert_not_reached ();
4190 g_assert (found_node != NULL);
4192 /* We have to find the last sub-node of this node that contains
4197 while (node->level > 0)
4199 GSList *child_nodes = NULL;
4201 g_assert (node != NULL); /* If this fails, it likely means an
4202 incorrect tag summary led us on a
4203 wild goose chase down this branch of
4206 node = node->children.node;
4207 while (node != NULL)
4209 child_nodes = g_slist_prepend (child_nodes, node);
4213 node = NULL; /* detect failure to find a child node. */
4216 while (iter != NULL)
4218 if (gtk_text_btree_node_has_tag (iter->data, tag))
4220 /* recurse into this node. */
4225 iter = g_slist_next (iter);
4228 g_slist_free (child_nodes);
4230 g_assert (node != NULL);
4233 g_assert (node != NULL);
4234 g_assert (node->level == 0);
4236 /* this assertion is correct, but slow. */
4237 /* g_assert (node_compare (node, line->parent) < 0); */
4239 /* Return last line in this node. */
4241 prev = node->children.line;
4249 * Non-public function implementations
4253 summary_list_destroy (Summary *summary)
4256 while (summary != NULL)
4258 next = summary->next;
4259 summary_destroy (summary);
4265 get_last_line (GtkTextBTree *tree)
4267 if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
4273 n_lines = gtk_text_btree_line_count (tree);
4275 g_assert (n_lines >= 1); /* num_lines doesn't return bogus last line. */
4277 line = gtk_text_btree_get_line (tree, n_lines, &real_line);
4279 tree->end_iter_line_stamp = tree->chars_changed_stamp;
4280 tree->end_iter_line = line;
4283 return tree->end_iter_line;
4291 gtk_text_line_new (void)
4295 line = g_new0(GtkTextLine, 1);
4301 gtk_text_line_destroy (GtkTextBTree *tree, GtkTextLine *line)
4303 GtkTextLineData *ld;
4304 GtkTextLineData *next;
4306 g_return_if_fail (line != NULL);
4313 view = gtk_text_btree_get_view (tree, ld->view_id);
4315 g_assert (view != NULL);
4318 gtk_text_layout_free_line_data (view->layout, line, ld);
4327 gtk_text_line_set_parent (GtkTextLine *line,
4328 GtkTextBTreeNode *node)
4330 if (line->parent == node)
4332 line->parent = node;
4333 gtk_text_btree_node_invalidate_upward (node, NULL);
4337 cleanup_line (GtkTextLine *line)
4339 GtkTextLineSegment *seg, **prev_p;
4343 * Make a pass over all of the segments in the line, giving each
4344 * a chance to clean itself up. This could potentially change
4345 * the structure of the line, e.g. by merging two segments
4346 * together or having two segments cancel themselves; if so,
4347 * then repeat the whole process again, since the first structure
4348 * change might make other structure changes possible. Repeat
4349 * until eventually there are no changes.
4356 for (prev_p = &line->segments, seg = *prev_p;
4358 prev_p = &(*prev_p)->next, seg = *prev_p)
4360 if (seg->type->cleanupFunc != NULL)
4362 *prev_p = (*seg->type->cleanupFunc)(seg, line);
4375 node_data_new (gpointer view_id)
4379 nd = g_new (NodeData, 1);
4381 nd->view_id = view_id;
4391 node_data_destroy (NodeData *nd)
4398 node_data_list_destroy (NodeData *nd)
4404 while (iter != NULL)
4407 node_data_destroy (iter);
4413 node_data_find (NodeData *nd, gpointer view_id)
4417 if (nd->view_id == view_id)
4425 summary_destroy (Summary *summary)
4427 /* Fill with error-triggering garbage */
4428 summary->info = (void*)0x1;
4429 summary->toggle_count = 567;
4430 summary->next = (void*)0x1;
4434 static GtkTextBTreeNode*
4435 gtk_text_btree_node_new (void)
4437 GtkTextBTreeNode *node;
4439 node = g_new (GtkTextBTreeNode, 1);
4441 node->node_data = NULL;
4447 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
4448 GtkTextTagInfo *info,
4453 summary = node->summary;
4454 while (summary != NULL)
4456 if (summary->info == info)
4458 summary->toggle_count += adjust;
4462 summary = summary->next;
4465 if (summary == NULL)
4467 /* didn't find a summary for our tag. */
4468 g_return_if_fail (adjust > 0);
4469 summary = g_new (Summary, 1);
4470 summary->info = info;
4471 summary->toggle_count = adjust;
4472 summary->next = node->summary;
4473 node->summary = summary;
4477 /* Note that the tag root and above do not have summaries
4478 for the tag; only nodes below the tag root have
4481 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4485 summary = node->summary;
4486 while (summary != NULL)
4489 summary->info->tag == tag)
4492 summary = summary->next;
4498 /* Add node and all children to the damage region. */
4500 gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node)
4504 nd = node->node_data;
4511 if (node->level == 0)
4515 line = node->children.line;
4516 while (line != NULL)
4518 GtkTextLineData *ld;
4532 GtkTextBTreeNode *child;
4534 child = node->children.node;
4536 while (child != NULL)
4538 gtk_text_btree_node_invalidate_downward (child);
4540 child = child->next;
4546 gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node, gpointer view_id)
4548 GtkTextBTreeNode *iter;
4551 while (iter != NULL)
4557 nd = node_data_find (iter->node_data, view_id);
4559 if (nd == NULL || !nd->valid)
4560 break; /* Once a node is invalid, we know its parents are as well. */
4566 gboolean should_continue = FALSE;
4568 nd = iter->node_data;
4573 should_continue = TRUE;
4580 if (!should_continue)
4581 break; /* This node was totally invalidated, so are its
4585 iter = iter->parent;
4591 * gtk_text_btree_is_valid:
4592 * @tree: a #GtkTextBTree
4593 * @view_id: ID for the view
4595 * Check to see if the entire #GtkTextBTree is valid or not for
4598 * Return value: %TRUE if the entire #GtkTextBTree is valid
4601 gtk_text_btree_is_valid (GtkTextBTree *tree,
4605 g_return_val_if_fail (tree != NULL, FALSE);
4607 nd = node_data_find (tree->root_node->node_data, view_id);
4608 return (nd && nd->valid);
4611 typedef struct _ValidateState ValidateState;
4613 struct _ValidateState
4615 gint remaining_pixels;
4616 gboolean in_validation;
4623 gtk_text_btree_node_validate (BTreeView *view,
4624 GtkTextBTreeNode *node,
4626 ValidateState *state)
4628 gint node_valid = TRUE;
4629 gint node_width = 0;
4630 gint node_height = 0;
4632 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4633 g_return_if_fail (!nd->valid);
4635 if (node->level == 0)
4637 GtkTextLine *line = node->children.line;
4638 GtkTextLineData *ld;
4640 /* Iterate over leading valid lines */
4641 while (line != NULL)
4643 ld = gtk_text_line_get_data (line, view_id);
4645 if (!ld || !ld->valid)
4647 else if (state->in_validation)
4649 state->in_validation = FALSE;
4654 state->y += ld->height;
4655 node_width = MAX (ld->width, node_width);
4656 node_height += ld->height;
4662 state->in_validation = TRUE;
4664 /* Iterate over invalid lines */
4665 while (line != NULL)
4667 ld = gtk_text_line_get_data (line, view_id);
4669 if (ld && ld->valid)
4674 state->old_height += ld->height;
4675 ld = gtk_text_layout_wrap (view->layout, line, ld);
4676 state->new_height += ld->height;
4678 node_width = MAX (ld->width, node_width);
4679 node_height += ld->height;
4681 state->remaining_pixels -= ld->height;
4682 if (state->remaining_pixels <= 0)
4692 /* Iterate over the remaining lines */
4693 while (line != NULL)
4695 ld = gtk_text_line_get_data (line, view_id);
4696 state->in_validation = FALSE;
4698 if (!ld || !ld->valid)
4703 node_width = MAX (ld->width, node_width);
4704 node_height += ld->height;
4712 GtkTextBTreeNode *child;
4715 child = node->children.node;
4717 /* Iterate over leading valid nodes */
4720 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4722 if (!child_nd->valid)
4724 else if (state->in_validation)
4726 state->in_validation = FALSE;
4731 state->y += child_nd->height;
4732 node_width = MAX (node_width, child_nd->width);
4733 node_height += child_nd->height;
4736 child = child->next;
4739 /* Iterate over invalid nodes */
4742 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4744 if (child_nd->valid)
4748 gtk_text_btree_node_validate (view, child, view_id, state);
4750 if (!child_nd->valid)
4752 node_width = MAX (node_width, child_nd->width);
4753 node_height += child_nd->height;
4755 if (!state->in_validation || state->remaining_pixels <= 0)
4757 child = child->next;
4762 child = child->next;
4765 /* Iterate over the remaining lines */
4768 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4769 state->in_validation = FALSE;
4771 if (!child_nd->valid)
4774 node_width = MAX (child_nd->width, node_width);
4775 node_height += child_nd->height;
4777 child = child->next;
4781 nd->width = node_width;
4782 nd->height = node_height;
4783 nd->valid = node_valid;
4787 * gtk_text_btree_validate:
4788 * @tree: a #GtkTextBTree
4790 * @max_pixels: the maximum number of pixels to validate. (No more
4791 * than one paragraph beyond this limit will be validated)
4792 * @y: location to store starting y coordinate of validated region
4793 * @old_height: location to store old height of validated region
4794 * @new_height: location to store new height of validated region
4796 * Validate a single contiguous invalid region of a #GtkTextBTree for
4799 * Return value: %TRUE if a region has been validated, %FALSE if the
4800 * entire tree was already valid.
4803 gtk_text_btree_validate (GtkTextBTree *tree,
4812 g_return_val_if_fail (tree != NULL, FALSE);
4814 view = gtk_text_btree_get_view (tree, view_id);
4815 g_return_val_if_fail (view != NULL, FALSE);
4817 if (!gtk_text_btree_is_valid (tree, view_id))
4819 ValidateState state;
4821 state.remaining_pixels = max_pixels;
4822 state.in_validation = FALSE;
4824 state.old_height = 0;
4825 state.new_height = 0;
4827 gtk_text_btree_node_validate (view,
4834 *old_height = state.old_height;
4836 *new_height = state.new_height;
4838 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4839 gtk_text_btree_check (tree);
4848 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
4852 gboolean *valid_out)
4856 gboolean valid = TRUE;
4858 if (node->level == 0)
4860 GtkTextLine *line = node->children.line;
4862 while (line != NULL)
4864 GtkTextLineData *ld = gtk_text_line_get_data (line, view_id);
4866 if (!ld || !ld->valid)
4871 width = MAX (ld->width, width);
4872 height += ld->height;
4880 GtkTextBTreeNode *child = node->children.node;
4884 NodeData *child_nd = node_data_find (child->node_data, view_id);
4886 if (!child_nd || !child_nd->valid)
4891 width = MAX (child_nd->width, width);
4892 height += child_nd->height;
4895 child = child->next;
4900 *height_out = height;
4905 /* Recompute the validity and size of the view data for a given
4906 * view at this node from the immediate children of the node
4909 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
4912 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4917 gtk_text_btree_node_compute_view_aggregates (node, view_id,
4918 &width, &height, &valid);
4920 nd->height = height;
4927 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
4932 gtk_text_btree_node_check_valid (node, view_id);
4933 node = node->parent;
4938 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
4941 if (node->level == 0)
4943 return gtk_text_btree_node_check_valid (node, view_id);
4947 GtkTextBTreeNode *child = node->children.node;
4949 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4957 NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
4959 if (!child_nd->valid)
4961 nd->width = MAX (child_nd->width, nd->width);
4962 nd->height += child_nd->height;
4964 child = child->next;
4973 * gtk_text_btree_validate_line:
4974 * @tree: a #GtkTextBTree
4975 * @line: line to validate
4976 * @view_id: view ID for the view to validate
4978 * Revalidate a single line of the btree for the given view, propagate
4979 * results up through the entire tree.
4982 gtk_text_btree_validate_line (GtkTextBTree *tree,
4986 GtkTextLineData *ld;
4987 GtkTextLine *last_line;
4990 g_return_if_fail (tree != NULL);
4991 g_return_if_fail (line != NULL);
4993 view = gtk_text_btree_get_view (tree, view_id);
4994 g_return_if_fail (view != NULL);
4996 ld = gtk_text_line_get_data (line, view_id);
4997 if (!ld || !ld->valid)
4999 ld = gtk_text_layout_wrap (view->layout, line, ld);
5000 last_line = get_last_line (tree);
5002 gtk_text_btree_node_check_valid_upward (line->parent, view_id);
5007 gtk_text_btree_node_remove_view (BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
5009 if (node->level == 0)
5013 line = node->children.line;
5014 while (line != NULL)
5016 GtkTextLineData *ld;
5018 ld = gtk_text_line_remove_data (line, view_id);
5021 gtk_text_layout_free_line_data (view->layout, line, ld);
5028 GtkTextBTreeNode *child;
5030 child = node->children.node;
5032 while (child != NULL)
5035 gtk_text_btree_node_remove_view (view, child, view_id);
5037 child = child->next;
5041 gtk_text_btree_node_remove_data (node, view_id);
5045 gtk_text_btree_node_destroy (GtkTextBTree *tree, GtkTextBTreeNode *node)
5047 if (node->level == 0)
5050 GtkTextLineSegment *seg;
5052 while (node->children.line != NULL)
5054 line = node->children.line;
5055 node->children.line = line->next;
5056 while (line->segments != NULL)
5058 seg = line->segments;
5059 line->segments = seg->next;
5061 if (GTK_IS_TEXT_MARK_SEGMENT (seg))
5063 /* Set the mark as deleted */
5064 seg->body.mark.tree = NULL;
5065 seg->body.mark.line = NULL;
5068 (*seg->type->deleteFunc) (seg, line, 1);
5070 gtk_text_line_destroy (tree, line);
5075 GtkTextBTreeNode *childPtr;
5077 while (node->children.node != NULL)
5079 childPtr = node->children.node;
5080 node->children.node = childPtr->next;
5081 gtk_text_btree_node_destroy (tree, childPtr);
5085 summary_list_destroy (node->summary);
5086 node_data_list_destroy (node->node_data);
5091 gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node, gpointer view_id)
5095 nd = node->node_data;
5098 if (nd->view_id == view_id)
5105 nd = node_data_new (view_id);
5107 if (node->node_data)
5108 nd->next = node->node_data;
5110 node->node_data = nd;
5117 gtk_text_btree_node_remove_data (GtkTextBTreeNode *node, gpointer view_id)
5123 nd = node->node_data;
5126 if (nd->view_id == view_id)
5137 prev->next = nd->next;
5139 if (node->node_data == nd)
5140 node->node_data = nd->next;
5144 node_data_destroy (nd);
5148 gtk_text_btree_node_get_size (GtkTextBTreeNode *node, gpointer view_id,
5149 gint *width, gint *height)
5153 g_return_if_fail (width != NULL);
5154 g_return_if_fail (height != NULL);
5156 nd = gtk_text_btree_node_ensure_data (node, view_id);
5161 *height = nd->height;
5164 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5165 * here isn't quite right, since for a lot of operations we want to
5166 * know which children of the common parent correspond to the two nodes
5167 * (e.g., when computing the order of two iters)
5169 static GtkTextBTreeNode *
5170 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5171 GtkTextBTreeNode *node2)
5173 while (node1->level < node2->level)
5174 node1 = node1->parent;
5175 while (node2->level < node1->level)
5176 node2 = node2->parent;
5177 while (node1 != node2)
5179 node1 = node1->parent;
5180 node2 = node2->parent;
5191 gtk_text_btree_get_view (GtkTextBTree *tree, gpointer view_id)
5196 while (view != NULL)
5198 if (view->view_id == view_id)
5207 get_tree_bounds (GtkTextBTree *tree,
5211 gtk_text_btree_get_iter_at_line_char (tree, start, 0, 0);
5212 gtk_text_btree_get_last_iter (tree, end);
5216 tag_changed_cb (GtkTextTagTable *table,
5218 gboolean size_changed,
5223 /* We need to queue a relayout on all regions that are tagged with
5230 if (gtk_text_btree_get_iter_at_first_toggle (tree, &start, tag))
5232 /* Must be a last toggle if there was a first one. */
5233 gtk_text_btree_get_iter_at_last_toggle (tree, &end, tag);
5234 gtk_text_btree_invalidate_region (tree,
5241 /* We only need to queue a redraw, not a relayout */
5246 while (view != NULL)
5250 gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5251 gtk_text_layout_changed (view->layout, 0, height, height);
5259 tag_removed_cb (GtkTextTagTable *table,
5263 /* Remove the tag from the tree */
5268 get_tree_bounds (tree, &start, &end);
5270 gtk_text_btree_tag (&start, &end, tag, FALSE);
5271 gtk_text_btree_remove_tag_info (tree, tag);
5275 /* Rebalance the out-of-whack node "node" */
5277 gtk_text_btree_rebalance (GtkTextBTree *tree,
5278 GtkTextBTreeNode *node)
5281 * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5282 * up through the tree one GtkTextBTreeNode at a time until the root
5283 * GtkTextBTreeNode has been processed.
5286 while (node != NULL)
5288 GtkTextBTreeNode *new_node, *child;
5293 * Check to see if the GtkTextBTreeNode has too many children. If it does,
5294 * then split off all but the first MIN_CHILDREN into a separate
5295 * GtkTextBTreeNode following the original one. Then repeat until the
5296 * GtkTextBTreeNode has a decent size.
5299 if (node->num_children > MAX_CHILDREN)
5304 * If the GtkTextBTreeNode being split is the root
5305 * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5309 if (node->parent == NULL)
5311 new_node = gtk_text_btree_node_new ();
5312 new_node->parent = NULL;
5313 new_node->next = NULL;
5314 new_node->summary = NULL;
5315 new_node->level = node->level + 1;
5316 new_node->children.node = node;
5317 recompute_node_counts (tree, new_node);
5318 tree->root_node = new_node;
5320 new_node = gtk_text_btree_node_new ();
5321 new_node->parent = node->parent;
5322 new_node->next = node->next;
5323 node->next = new_node;
5324 new_node->summary = NULL;
5325 new_node->level = node->level;
5326 new_node->num_children = node->num_children - MIN_CHILDREN;
5327 if (node->level == 0)
5329 for (i = MIN_CHILDREN-1,
5330 line = node->children.line;
5331 i > 0; i--, line = line->next)
5333 /* Empty loop body. */
5335 new_node->children.line = line->next;
5340 for (i = MIN_CHILDREN-1,
5341 child = node->children.node;
5342 i > 0; i--, child = child->next)
5344 /* Empty loop body. */
5346 new_node->children.node = child->next;
5349 recompute_node_counts (tree, node);
5350 node->parent->num_children++;
5352 if (node->num_children <= MAX_CHILDREN)
5354 recompute_node_counts (tree, node);
5360 while (node->num_children < MIN_CHILDREN)
5362 GtkTextBTreeNode *other;
5363 GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5364 GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5365 int total_children, first_children, i;
5368 * Too few children for this GtkTextBTreeNode. If this is the root then,
5369 * it's OK for it to have less than MIN_CHILDREN children
5370 * as long as it's got at least two. If it has only one
5371 * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5372 * the tree and use its child as the new root.
5375 if (node->parent == NULL)
5377 if ((node->num_children == 1) && (node->level > 0))
5379 tree->root_node = node->children.node;
5380 tree->root_node->parent = NULL;
5381 summary_list_destroy (node->summary);
5388 * Not the root. Make sure that there are siblings to
5392 if (node->parent->num_children < 2)
5394 gtk_text_btree_rebalance (tree, node->parent);
5399 * Find a sibling neighbor to borrow from, and arrange for
5400 * node to be the earlier of the pair.
5403 if (node->next == NULL)
5405 for (other = node->parent->children.node;
5406 other->next != node;
5407 other = other->next)
5409 /* Empty loop body. */
5416 * We're going to either merge the two siblings together
5417 * into one GtkTextBTreeNode or redivide the children among them to
5418 * balance their loads. As preparation, join their two
5419 * child lists into a single list and remember the half-way
5420 * point in the list.
5423 total_children = node->num_children + other->num_children;
5424 first_children = total_children/2;
5425 if (node->children.node == NULL)
5427 node->children = other->children;
5428 other->children.node = NULL;
5429 other->children.line = NULL;
5431 if (node->level == 0)
5435 for (line = node->children.line, i = 1;
5437 line = line->next, i++)
5439 if (i == first_children)
5444 line->next = other->children.line;
5445 while (i <= first_children)
5454 GtkTextBTreeNode *child;
5456 for (child = node->children.node, i = 1;
5457 child->next != NULL;
5458 child = child->next, i++)
5460 if (i <= first_children)
5462 if (i == first_children)
5464 halfwaynode = child;
5468 child->next = other->children.node;
5469 while (i <= first_children)
5471 halfwaynode = child;
5472 child = child->next;
5478 * If the two siblings can simply be merged together, do it.
5481 if (total_children <= MAX_CHILDREN)
5483 recompute_node_counts (tree, node);
5484 node->next = other->next;
5485 node->parent->num_children--;
5486 summary_list_destroy (other->summary);
5492 * The siblings can't be merged, so just divide their
5493 * children evenly between them.
5496 if (node->level == 0)
5498 other->children.line = halfwayline->next;
5499 halfwayline->next = NULL;
5503 other->children.node = halfwaynode->next;
5504 halfwaynode->next = NULL;
5507 recompute_node_counts (tree, node);
5508 recompute_node_counts (tree, other);
5511 node = node->parent;
5516 post_insert_fixup (GtkTextBTree *tree,
5518 gint line_count_delta,
5519 gint char_count_delta)
5522 GtkTextBTreeNode *node;
5525 * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5526 * point, then rebalance the tree if necessary.
5529 for (node = line->parent ; node != NULL;
5530 node = node->parent)
5532 node->num_lines += line_count_delta;
5533 node->num_chars += char_count_delta;
5535 node = line->parent;
5536 node->num_children += line_count_delta;
5538 if (node->num_children > MAX_CHILDREN)
5540 gtk_text_btree_rebalance (tree, node);
5543 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5544 gtk_text_btree_check (tree);
5547 static GtkTextTagInfo*
5548 gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
5551 GtkTextTagInfo *info;
5555 list = tree->tag_infos;
5556 while (list != NULL)
5559 if (info->tag == tag)
5562 list = g_slist_next (list);
5568 static GtkTextTagInfo*
5569 gtk_text_btree_get_tag_info (GtkTextBTree *tree,
5572 GtkTextTagInfo *info;
5574 info = gtk_text_btree_get_existing_tag_info (tree, tag);
5578 /* didn't find it, create. */
5580 info = g_new (GtkTextTagInfo, 1);
5583 gtk_object_ref (GTK_OBJECT (tag));
5584 info->tag_root = NULL;
5585 info->toggle_count = 0;
5587 tree->tag_infos = g_slist_prepend (tree->tag_infos, info);
5594 gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
5597 GtkTextTagInfo *info;
5602 list = tree->tag_infos;
5603 while (list != NULL)
5606 if (info->tag == tag)
5610 prev->next = list->next;
5614 tree->tag_infos = list->next;
5617 g_slist_free (list);
5619 gtk_object_unref (GTK_OBJECT (info->tag));
5625 list = g_slist_next (list);
5628 g_assert_not_reached ();
5633 recompute_level_zero_counts (GtkTextBTreeNode *node)
5636 GtkTextLineSegment *seg;
5638 g_assert (node->level == 0);
5640 line = node->children.line;
5641 while (line != NULL)
5643 node->num_children++;
5646 if (line->parent != node)
5647 gtk_text_line_set_parent (line, node);
5649 seg = line->segments;
5653 node->num_chars += seg->char_count;
5655 if (((seg->type != >k_text_toggle_on_type)
5656 && (seg->type != >k_text_toggle_off_type))
5657 || !(seg->body.toggle.inNodeCounts))
5663 GtkTextTagInfo *info;
5665 info = seg->body.toggle.info;
5667 gtk_text_btree_node_adjust_toggle_count (node, info, 1);
5678 recompute_level_nonzero_counts (GtkTextBTreeNode *node)
5681 GtkTextBTreeNode *child;
5683 g_assert (node->level > 0);
5685 child = node->children.node;
5686 while (child != NULL)
5688 node->num_children += 1;
5689 node->num_lines += child->num_lines;
5690 node->num_chars += child->num_chars;
5692 if (child->parent != node)
5694 child->parent = node;
5695 gtk_text_btree_node_invalidate_upward (node, NULL);
5698 summary = child->summary;
5699 while (summary != NULL)
5701 gtk_text_btree_node_adjust_toggle_count (node,
5703 summary->toggle_count);
5705 summary = summary->next;
5708 child = child->next;
5713 *----------------------------------------------------------------------
5715 * recompute_node_counts --
5717 * This procedure is called to recompute all the counts in a GtkTextBTreeNode
5718 * (tags, child information, etc.) by scanning the information in
5719 * its descendants. This procedure is called during rebalancing
5720 * when a GtkTextBTreeNode's child structure has changed.
5726 * The tag counts for node are modified to reflect its current
5727 * child structure, as are its num_children, num_lines, num_chars fields.
5728 * Also, all of the childrens' parent fields are made to point
5731 *----------------------------------------------------------------------
5735 recompute_node_counts (GtkTextBTree *tree, GtkTextBTreeNode *node)
5738 Summary *summary, *summary2;
5741 * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
5742 * the existing Summary records (most of them will probably be reused).
5745 summary = node->summary;
5746 while (summary != NULL)
5748 summary->toggle_count = 0;
5749 summary = summary->next;
5752 node->num_children = 0;
5753 node->num_lines = 0;
5754 node->num_chars = 0;
5757 * Scan through the children, adding the childrens' tag counts into
5758 * the GtkTextBTreeNode's tag counts and adding new Summary structures if
5762 if (node->level == 0)
5763 recompute_level_zero_counts (node);
5765 recompute_level_nonzero_counts (node);
5770 gtk_text_btree_node_check_valid (node, view->view_id);
5775 * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
5776 * records that still have a zero count, or that have all the toggles.
5777 * The GtkTextBTreeNode with the children that account for all the tags toggles
5778 * have no summary information, and they become the tag_root for the tag.
5782 for (summary = node->summary; summary != NULL; )
5784 if (summary->toggle_count > 0 &&
5785 summary->toggle_count < summary->info->toggle_count)
5787 if (node->level == summary->info->tag_root->level)
5790 * The tag's root GtkTextBTreeNode split and some toggles left.
5791 * The tag root must move up a level.
5793 summary->info->tag_root = node->parent;
5796 summary = summary->next;
5799 if (summary->toggle_count == summary->info->toggle_count)
5802 * A GtkTextBTreeNode merge has collected all the toggles under
5803 * one GtkTextBTreeNode. Push the root down to this level.
5805 summary->info->tag_root = node;
5807 if (summary2 != NULL)
5809 summary2->next = summary->next;
5810 summary_destroy (summary);
5811 summary = summary2->next;
5815 node->summary = summary->next;
5816 summary_destroy (summary);
5817 summary = node->summary;
5823 _gtk_change_node_toggle_count (GtkTextBTreeNode *node,
5824 GtkTextTagInfo *info,
5825 gint delta) /* may be negative */
5827 Summary *summary, *prevPtr;
5828 GtkTextBTreeNode *node2Ptr;
5829 int rootLevel; /* Level of original tag root */
5831 info->toggle_count += delta;
5833 if (info->tag_root == (GtkTextBTreeNode *) NULL)
5835 info->tag_root = node;
5840 * Note the level of the existing root for the tag so we can detect
5841 * if it needs to be moved because of the toggle count change.
5844 rootLevel = info->tag_root->level;
5847 * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
5848 * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
5852 for ( ; node != info->tag_root; node = node->parent)
5855 * See if there's already an entry for this tag for this GtkTextBTreeNode. If so,
5856 * perhaps all we have to do is adjust its count.
5859 for (prevPtr = NULL, summary = node->summary;
5861 prevPtr = summary, summary = summary->next)
5863 if (summary->info == info)
5868 if (summary != NULL)
5870 summary->toggle_count += delta;
5871 if (summary->toggle_count > 0 &&
5872 summary->toggle_count < info->toggle_count)
5876 if (summary->toggle_count != 0)
5879 * Should never find a GtkTextBTreeNode with max toggle count at this
5880 * point (there shouldn't have been a summary entry in the
5884 g_error ("%s: bad toggle count (%d) max (%d)",
5885 G_STRLOC, summary->toggle_count, info->toggle_count);
5889 * Zero toggle count; must remove this tag from the list.
5892 if (prevPtr == NULL)
5894 node->summary = summary->next;
5898 prevPtr->next = summary->next;
5900 summary_destroy (summary);
5905 * This tag isn't currently in the summary information list.
5908 if (rootLevel == node->level)
5912 * The old tag root is at the same level in the tree as this
5913 * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode. Move the tag root up
5914 * a level, in the hopes that it will now cover this GtkTextBTreeNode
5915 * as well as the old root (if not, we'll move it up again
5916 * the next time through the loop). To push it up one level
5917 * we copy the original toggle count into the summary
5918 * information at the old root and change the root to its
5919 * parent GtkTextBTreeNode.
5922 GtkTextBTreeNode *rootnode = info->tag_root;
5923 summary = (Summary *) g_malloc (sizeof (Summary));
5924 summary->info = info;
5925 summary->toggle_count = info->toggle_count - delta;
5926 summary->next = rootnode->summary;
5927 rootnode->summary = summary;
5928 rootnode = rootnode->parent;
5929 rootLevel = rootnode->level;
5930 info->tag_root = rootnode;
5932 summary = (Summary *) g_malloc (sizeof (Summary));
5933 summary->info = info;
5934 summary->toggle_count = delta;
5935 summary->next = node->summary;
5936 node->summary = summary;
5941 * If we've decremented the toggle count, then it may be necessary
5942 * to push the tag root down one or more levels.
5949 if (info->toggle_count == 0)
5951 info->tag_root = (GtkTextBTreeNode *) NULL;
5954 node = info->tag_root;
5955 while (node->level > 0)
5958 * See if a single child GtkTextBTreeNode accounts for all of the tag's
5959 * toggles. If so, push the root down one level.
5962 for (node2Ptr = node->children.node;
5963 node2Ptr != (GtkTextBTreeNode *)NULL ;
5964 node2Ptr = node2Ptr->next)
5966 for (prevPtr = NULL, summary = node2Ptr->summary;
5968 prevPtr = summary, summary = summary->next)
5970 if (summary->info == info)
5975 if (summary == NULL)
5979 if (summary->toggle_count != info->toggle_count)
5982 * No GtkTextBTreeNode has all toggles, so the root is still valid.
5989 * This GtkTextBTreeNode has all the toggles, so push down the root.
5992 if (prevPtr == NULL)
5994 node2Ptr->summary = summary->next;
5998 prevPtr->next = summary->next;
6000 summary_destroy (summary);
6001 info->tag_root = node2Ptr;
6004 node = info->tag_root;
6009 *----------------------------------------------------------------------
6013 * This is a utility procedure used by gtk_text_btree_get_tags. It
6014 * increments the count for a particular tag, adding a new
6015 * entry for that tag if there wasn't one previously.
6021 * The information at *tagInfoPtr may be modified, and the arrays
6022 * may be reallocated to make them larger.
6024 *----------------------------------------------------------------------
6028 inc_count (GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
6033 for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
6034 count > 0; tag_p++, count--)
6038 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
6044 * There isn't currently an entry for this tag, so we have to
6045 * make a new one. If the arrays are full, then enlarge the
6049 if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
6051 GtkTextTag **newTags;
6052 int *newCounts, newSize;
6054 newSize = 2*tagInfoPtr->arraySize;
6055 newTags = (GtkTextTag **) g_malloc ((unsigned)
6056 (newSize*sizeof (GtkTextTag *)));
6057 memcpy ((void *) newTags, (void *) tagInfoPtr->tags,
6058 tagInfoPtr->arraySize *sizeof (GtkTextTag *));
6059 g_free ((char *) tagInfoPtr->tags);
6060 tagInfoPtr->tags = newTags;
6061 newCounts = (int *) g_malloc ((unsigned) (newSize*sizeof (int)));
6062 memcpy ((void *) newCounts, (void *) tagInfoPtr->counts,
6063 tagInfoPtr->arraySize *sizeof (int));
6064 g_free ((char *) tagInfoPtr->counts);
6065 tagInfoPtr->counts = newCounts;
6066 tagInfoPtr->arraySize = newSize;
6069 tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
6070 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
6071 tagInfoPtr->numTags++;
6075 gtk_text_btree_link_segment (GtkTextLineSegment *seg,
6076 const GtkTextIter *iter)
6078 GtkTextLineSegment *prev;
6082 line = gtk_text_iter_get_text_line (iter);
6083 tree = gtk_text_iter_get_btree (iter);
6085 prev = gtk_text_line_segment_split (iter);
6088 seg->next = line->segments;
6089 line->segments = seg;
6093 seg->next = prev->next;
6096 cleanup_line (line);
6097 segments_changed (tree);
6099 if (gtk_debug_flags & GTK_DEBUG_TEXT)
6100 gtk_text_btree_check (tree);
6104 gtk_text_btree_unlink_segment (GtkTextBTree *tree,
6105 GtkTextLineSegment *seg,
6108 GtkTextLineSegment *prev;
6110 if (line->segments == seg)
6112 line->segments = seg->next;
6116 for (prev = line->segments; prev->next != seg;
6119 /* Empty loop body. */
6121 prev->next = seg->next;
6123 cleanup_line (line);
6124 segments_changed (tree);
6128 * This is here because it requires BTree internals, it logically
6129 * belongs in gtktextsegment.c
6134 *--------------------------------------------------------------
6136 * _gtk_toggle_segment_check_func --
6138 * This procedure is invoked to perform consistency checks
6139 * on toggle segments.
6145 * If a consistency problem is found the procedure g_errors.
6147 *--------------------------------------------------------------
6151 _gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6157 if (segPtr->byte_count != 0)
6159 g_error ("toggle_segment_check_func: segment had non-zero size");
6161 if (!segPtr->body.toggle.inNodeCounts)
6163 g_error ("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6165 needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6166 for (summary = line->parent->summary; ;
6167 summary = summary->next)
6169 if (summary == NULL)
6173 g_error ("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6180 if (summary->info == segPtr->body.toggle.info)
6184 g_error ("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6196 gtk_text_btree_node_view_check_consistency (GtkTextBTreeNode *node,
6203 gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6204 &width, &height, &valid);
6205 if (nd->width != width ||
6206 nd->height != height ||
6207 !nd->valid != !valid)
6209 g_error ("Node aggregates for view %p are invalid:\n"
6210 "Are (%d,%d,%s), should be (%d,%d,%s)",
6212 nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6213 width, height, valid ? "TRUE" : "FALSE");
6218 gtk_text_btree_node_check_consistency (GtkTextBTreeNode *node)
6220 GtkTextBTreeNode *childnode;
6221 Summary *summary, *summary2;
6223 GtkTextLineSegment *segPtr;
6224 int num_children, num_lines, num_chars, toggle_count, min_children;
6225 GtkTextLineData *ld;
6228 if (node->parent != NULL)
6230 min_children = MIN_CHILDREN;
6232 else if (node->level > 0)
6239 if ((node->num_children < min_children)
6240 || (node->num_children > MAX_CHILDREN))
6242 g_error ("gtk_text_btree_node_check_consistency: bad child count (%d)",
6243 node->num_children);
6246 nd = node->node_data;
6249 gtk_text_btree_node_view_check_consistency (node, nd);
6256 if (node->level == 0)
6258 for (line = node->children.line; line != NULL;
6261 if (line->parent != node)
6263 g_error ("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6265 if (line->segments == NULL)
6267 g_error ("gtk_text_btree_node_check_consistency: line has no segments");
6273 /* Just ensuring we don't segv while doing this loop */
6278 for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6280 if (segPtr->type->checkFunc != NULL)
6282 (*segPtr->type->checkFunc)(segPtr, line);
6284 if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6285 && (segPtr->next != NULL)
6286 && (segPtr->next->byte_count == 0)
6287 && (segPtr->next->type->leftGravity))
6289 g_error ("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6291 if ((segPtr->next == NULL)
6292 && (segPtr->type != >k_text_char_type))
6294 g_error ("gtk_text_btree_node_check_consistency: line ended with wrong type");
6297 num_chars += segPtr->char_count;
6306 for (childnode = node->children.node; childnode != NULL;
6307 childnode = childnode->next)
6309 if (childnode->parent != node)
6311 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6313 if (childnode->level != (node->level-1))
6315 g_error ("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6316 node->level, childnode->level);
6318 gtk_text_btree_node_check_consistency (childnode);
6319 for (summary = childnode->summary; summary != NULL;
6320 summary = summary->next)
6322 for (summary2 = node->summary; ;
6323 summary2 = summary2->next)
6325 if (summary2 == NULL)
6327 if (summary->info->tag_root == node)
6331 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6332 summary->info->tag->name,
6333 "present in parent summaries");
6335 if (summary->info == summary2->info)
6342 num_lines += childnode->num_lines;
6343 num_chars += childnode->num_chars;
6346 if (num_children != node->num_children)
6348 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6349 num_children, node->num_children);
6351 if (num_lines != node->num_lines)
6353 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6354 num_lines, node->num_lines);
6356 if (num_chars != node->num_chars)
6358 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6359 num_chars, node->num_chars);
6362 for (summary = node->summary; summary != NULL;
6363 summary = summary->next)
6365 if (summary->info->toggle_count == summary->toggle_count)
6367 g_error ("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6368 summary->info->tag->name);
6371 if (node->level == 0)
6373 for (line = node->children.line; line != NULL;
6376 for (segPtr = line->segments; segPtr != NULL;
6377 segPtr = segPtr->next)
6379 if ((segPtr->type != >k_text_toggle_on_type)
6380 && (segPtr->type != >k_text_toggle_off_type))
6384 if (segPtr->body.toggle.info == summary->info)
6386 if (!segPtr->body.toggle.inNodeCounts)
6387 g_error ("Toggle segment not in the node counts");
6396 for (childnode = node->children.node;
6398 childnode = childnode->next)
6400 for (summary2 = childnode->summary;
6402 summary2 = summary2->next)
6404 if (summary2->info == summary->info)
6406 toggle_count += summary2->toggle_count;
6411 if (toggle_count != summary->toggle_count)
6413 g_error ("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6414 toggle_count, summary->toggle_count);
6416 for (summary2 = summary->next; summary2 != NULL;
6417 summary2 = summary2->next)
6419 if (summary2->info == summary->info)
6421 g_error ("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6422 summary->info->tag->name);
6429 listify_foreach (GtkTextTag *tag, gpointer user_data)
6431 GSList** listp = user_data;
6433 *listp = g_slist_prepend (*listp, tag);
6437 list_of_tags (GtkTextTagTable *table)
6439 GSList *list = NULL;
6441 gtk_text_tag_table_foreach (table, listify_foreach, &list);
6447 gtk_text_btree_check (GtkTextBTree *tree)
6450 GtkTextBTreeNode *node;
6452 GtkTextLineSegment *seg;
6454 GSList *taglist = NULL;
6456 GtkTextTagInfo *info;
6459 * Make sure that the tag toggle counts and the tag root pointers are OK.
6461 for (taglist = list_of_tags (tree->table);
6462 taglist != NULL ; taglist = taglist->next)
6464 tag = taglist->data;
6465 info = gtk_text_btree_get_existing_tag_info (tree, tag);
6468 node = info->tag_root;
6471 if (info->toggle_count != 0)
6473 g_error ("gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6474 tag->name, info->toggle_count);
6476 continue; /* no ranges for the tag */
6478 else if (info->toggle_count == 0)
6480 g_error ("gtk_text_btree_check found root for \"%s\" with no toggles",
6483 else if (info->toggle_count & 1)
6485 g_error ("gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6486 tag->name, info->toggle_count);
6488 for (summary = node->summary; summary != NULL;
6489 summary = summary->next)
6491 if (summary->info->tag == tag)
6493 g_error ("gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6497 if (node->level > 0)
6499 for (node = node->children.node ; node != NULL ;
6502 for (summary = node->summary; summary != NULL;
6503 summary = summary->next)
6505 if (summary->info->tag == tag)
6507 count += summary->toggle_count;
6514 GtkTextLineSegmentClass * last = NULL;
6516 for (line = node->children.line ; line != NULL ;
6519 for (seg = line->segments; seg != NULL;
6522 if ((seg->type == >k_text_toggle_on_type ||
6523 seg->type == >k_text_toggle_off_type) &&
6524 seg->body.toggle.info->tag == tag)
6526 if (last == seg->type)
6527 g_error ("Two consecutive toggles on or off weren't merged");
6528 if (!seg->body.toggle.inNodeCounts)
6529 g_error ("Toggle segment not in the node counts");
6538 if (count != info->toggle_count)
6540 g_error ("gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
6541 info->toggle_count, tag->name, count);
6546 g_slist_free (taglist);
6550 * Call a recursive procedure to do the main body of checks.
6553 node = tree->root_node;
6554 gtk_text_btree_node_check_consistency (tree->root_node);
6557 * Make sure that there are at least two lines in the text and
6558 * that the last line has no characters except a newline.
6561 if (node->num_lines < 2)
6563 g_error ("gtk_text_btree_check: less than 2 lines in tree");
6565 if (node->num_chars < 2)
6567 g_error ("gtk_text_btree_check: less than 2 chars in tree");
6569 while (node->level > 0)
6571 node = node->children.node;
6572 while (node->next != NULL)
6577 line = node->children.line;
6578 while (line->next != NULL)
6582 seg = line->segments;
6583 while ((seg->type == >k_text_toggle_off_type)
6584 || (seg->type == >k_text_right_mark_type)
6585 || (seg->type == >k_text_left_mark_type))
6588 * It's OK to toggle a tag off in the last line, but
6589 * not to start a new range. It's also OK to have marks
6595 if (seg->type != >k_text_char_type)
6597 g_error ("gtk_text_btree_check: last line has bogus segment type");
6599 if (seg->next != NULL)
6601 g_error ("gtk_text_btree_check: last line has too many segments");
6603 if (seg->byte_count != 1)
6605 g_error ("gtk_text_btree_check: last line has wrong # characters: %d",
6608 if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
6610 g_error ("gtk_text_btree_check: last line had bad value: %s",
6615 void gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line);
6616 void gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment* seg);
6617 void gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent);
6618 void gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
6621 gtk_text_btree_spew (GtkTextBTree *tree)
6626 printf ("%d lines in tree %p\n",
6627 gtk_text_btree_line_count (tree), tree);
6629 line = gtk_text_btree_get_line (tree, 0, &real_line);
6631 while (line != NULL)
6633 gtk_text_btree_spew_line (tree, line);
6634 line = gtk_text_line_next (line);
6637 printf ("=================== Tag information\n");
6642 list = tree->tag_infos;
6644 while (list != NULL)
6646 GtkTextTagInfo *info;
6650 printf (" tag `%s': root at %p, toggle count %d\n",
6651 info->tag->name, info->tag_root, info->toggle_count);
6653 list = g_slist_next (list);
6656 if (tree->tag_infos == NULL)
6658 printf (" (no tags in the tree)\n");
6662 printf ("=================== Tree nodes\n");
6665 gtk_text_btree_spew_node (tree->root_node, 0);
6670 gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
6673 GtkTextLineSegment *seg;
6675 spaces = g_strnfill (indent, ' ');
6677 printf ("%sline %p chars %d bytes %d\n",
6679 gtk_text_line_char_count (line),
6680 gtk_text_line_byte_count (line));
6682 seg = line->segments;
6685 if (seg->type == >k_text_char_type)
6687 gchar* str = g_strndup (seg->body.chars, MIN (seg->byte_count, 10));
6696 printf ("%s chars `%s'...\n", spaces, str);
6699 else if (seg->type == >k_text_right_mark_type)
6701 printf ("%s right mark `%s' visible: %d\n",
6703 seg->body.mark.name,
6704 seg->body.mark.visible);
6706 else if (seg->type == >k_text_left_mark_type)
6708 printf ("%s left mark `%s' visible: %d\n",
6710 seg->body.mark.name,
6711 seg->body.mark.visible);
6713 else if (seg->type == >k_text_toggle_on_type ||
6714 seg->type == >k_text_toggle_off_type)
6716 printf ("%s tag `%s' %s\n",
6717 spaces, seg->body.toggle.info->tag->name,
6718 seg->type == >k_text_toggle_off_type ? "off" : "on");
6728 gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent)
6731 GtkTextBTreeNode *iter;
6734 spaces = g_strnfill (indent, ' ');
6736 printf ("%snode %p level %d children %d lines %d chars %d\n",
6737 spaces, node, node->level,
6738 node->num_children, node->num_lines, node->num_chars);
6743 printf ("%s %d toggles of `%s' below this node\n",
6744 spaces, s->toggle_count, s->info->tag->name);
6750 if (node->level > 0)
6752 iter = node->children.node;
6753 while (iter != NULL)
6755 gtk_text_btree_spew_node (iter, indent + 2);
6762 GtkTextLine *line = node->children.line;
6763 while (line != NULL)
6765 gtk_text_btree_spew_line_short (line, indent + 2);
6773 gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line)
6775 GtkTextLineSegment * seg;
6777 printf ("%4d| line: %p parent: %p next: %p\n",
6778 gtk_text_line_get_number (line), line, line->parent, line->next);
6780 seg = line->segments;
6784 gtk_text_btree_spew_segment (tree, seg);
6790 gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment * seg)
6792 printf (" segment: %p type: %s bytes: %d chars: %d\n",
6793 seg, seg->type->name, seg->byte_count, seg->char_count);
6795 if (seg->type == >k_text_char_type)
6797 gchar* str = g_strndup (seg->body.chars, seg->byte_count);
6798 printf (" `%s'\n", str);
6801 else if (seg->type == >k_text_right_mark_type)
6803 printf (" right mark `%s' visible: %d not_deleteable: %d\n",
6804 seg->body.mark.name,
6805 seg->body.mark.visible,
6806 seg->body.mark.not_deleteable);
6808 else if (seg->type == >k_text_left_mark_type)
6810 printf (" left mark `%s' visible: %d not_deleteable: %d\n",
6811 seg->body.mark.name,
6812 seg->body.mark.visible,
6813 seg->body.mark.not_deleteable);
6815 else if (seg->type == >k_text_toggle_on_type ||
6816 seg->type == >k_text_toggle_off_type)
6818 printf (" tag `%s' priority %d\n",
6819 seg->body.toggle.info->tag->name,
6820 seg->body.toggle.info->tag->priority);