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 lines below this node are in need of validation.
106 * However, width/height should always represent the current total width and
107 * max height for lines below this node; the valid flag indicates whether the
108 * width/height on the lines needs recomputing, not whether the totals
116 * The data structure below keeps summary information about one tag as part
117 * of the tag information in a node.
120 typedef struct Summary {
121 GtkTextTagInfo *info; /* Handle for tag. */
122 int toggle_count; /* Number of transitions into or
123 * out of this tag that occur in
124 * the subtree rooted at this node. */
125 struct Summary *next; /* Next in list of all tags for same
126 * node, or NULL if at end of list. */
130 * The data structure below defines a node in the B-tree.
133 struct _GtkTextBTreeNode {
134 GtkTextBTreeNode *parent; /* Pointer to parent node, or NULL if
135 * this is the root. */
136 GtkTextBTreeNode *next; /* Next in list of siblings with the
137 * same parent node, or NULL for end
139 Summary *summary; /* First in malloc-ed list of info
140 * about tags in this subtree (NULL if
141 * no tag info in the subtree). */
142 int level; /* Level of this node in the B-tree.
143 * 0 refers to the bottom of the tree
144 * (children are lines, not nodes). */
145 union { /* First in linked list of children. */
146 struct _GtkTextBTreeNode *node; /* Used if level > 0. */
147 GtkTextLine *line; /* Used if level == 0. */
149 int num_children; /* Number of children of this node. */
150 int num_lines; /* Total number of lines (leaves) in
151 * the subtree rooted here. */
152 int num_chars; /* Number of chars below here */
159 * Used to store the list of views in our btree
162 typedef struct _BTreeView BTreeView;
166 GtkTextLayout *layout;
172 * And the tree itself
175 struct _GtkTextBTree {
176 GtkTextBTreeNode *root_node; /* Pointer to root of B-tree. */
177 GtkTextTagTable *table;
178 GHashTable *mark_table;
180 GtkTextMark *insert_mark;
181 GtkTextMark *selection_bound_mark;
182 GtkTextBuffer *buffer;
185 guint tag_changed_handler;
186 guint tag_removed_handler;
187 /* Incremented when a segment with a byte size > 0
188 is added to or removed from the tree (i.e. the
189 length of a line may have changed, and lines may
190 have been added or removed). This invalidates
191 all outstanding iterators.
193 guint chars_changed_stamp;
194 /* Incremented when any segments are added or deleted;
195 this makes outstanding iterators recalculate their
196 pointed-to segment and segment offset.
198 guint segments_changed_stamp;
200 GtkTextLine *end_iter_line;
202 guint end_iter_line_stamp;
204 GHashTable *child_anchor_table;
209 * Upper and lower bounds on how many children a node may have:
210 * rebalance when either of these limits is exceeded. MAX_CHILDREN
211 * should be twice MIN_CHILDREN and MIN_CHILDREN must be >= 2.
214 /* Tk used MAX of 12 and MIN of 6. This makes the tree wide and
215 shallow. It appears to be faster to locate a particular line number
216 if the tree is narrow and deep, since it is more finely sorted. I
217 guess this may increase memory use though, and make it slower to
218 walk the tree in order, or locate a particular byte index (which
219 is done by walking the tree in order).
221 There's basically a tradeoff here. However I'm thinking we want to
222 add pixels, byte counts, and char counts to the tree nodes,
223 at that point narrow and deep should speed up all operations,
224 not just the line number searches.
228 #define MAX_CHILDREN 12
229 #define MIN_CHILDREN 6
231 #define MAX_CHILDREN 6
232 #define MIN_CHILDREN 3
239 static BTreeView *gtk_text_btree_get_view (GtkTextBTree *tree,
241 static void gtk_text_btree_rebalance (GtkTextBTree *tree,
242 GtkTextBTreeNode *node);
243 static GtkTextLine * get_last_line (GtkTextBTree *tree);
244 static void post_insert_fixup (GtkTextBTree *tree,
245 GtkTextLine *insert_line,
246 gint char_count_delta,
247 gint line_count_delta);
248 static void gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
249 GtkTextTagInfo *info,
251 static gboolean gtk_text_btree_node_has_tag (GtkTextBTreeNode *node,
254 static void segments_changed (GtkTextBTree *tree);
255 static void chars_changed (GtkTextBTree *tree);
256 static void summary_list_destroy (Summary *summary);
257 static GtkTextLine *gtk_text_line_new (void);
258 static void gtk_text_line_destroy (GtkTextBTree *tree,
260 static void gtk_text_line_set_parent (GtkTextLine *line,
261 GtkTextBTreeNode *node);
262 static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
266 static NodeData *node_data_new (gpointer view_id);
267 static void node_data_destroy (NodeData *nd);
268 static void node_data_list_destroy (NodeData *nd);
269 static NodeData *node_data_find (NodeData *nd,
272 static GtkTextBTreeNode *gtk_text_btree_node_new (void);
273 static void gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node);
274 static void gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node,
276 static NodeData * gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
278 static NodeData * gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
280 static void gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
283 static void gtk_text_btree_node_remove_view (BTreeView *view,
284 GtkTextBTreeNode *node,
286 static void gtk_text_btree_node_destroy (GtkTextBTree *tree,
287 GtkTextBTreeNode *node);
288 static void gtk_text_btree_node_free_empty (GtkTextBTree *tree,
289 GtkTextBTreeNode *node);
290 static NodeData * gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node,
292 static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
294 static void gtk_text_btree_node_get_size (GtkTextBTreeNode *node,
298 static GtkTextBTreeNode * gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
299 GtkTextBTreeNode *node2);
300 static void get_tree_bounds (GtkTextBTree *tree,
303 static void tag_changed_cb (GtkTextTagTable *table,
305 gboolean size_changed,
307 static void tag_removed_cb (GtkTextTagTable *table,
310 static void cleanup_line (GtkTextLine *line);
311 static void recompute_node_counts (GtkTextBTree *tree,
312 GtkTextBTreeNode *node);
313 static void inc_count (GtkTextTag *tag,
315 TagInfo *tagInfoPtr);
317 static void summary_destroy (Summary *summary);
319 static void gtk_text_btree_link_segment (GtkTextLineSegment *seg,
320 const GtkTextIter *iter);
321 static void gtk_text_btree_unlink_segment (GtkTextBTree *tree,
322 GtkTextLineSegment *seg,
326 static GtkTextTagInfo *gtk_text_btree_get_tag_info (GtkTextBTree *tree,
328 static GtkTextTagInfo *gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
330 static void gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
333 static void redisplay_region (GtkTextBTree *tree,
334 const GtkTextIter *start,
335 const GtkTextIter *end);
337 /* Inline thingies */
340 segments_changed (GtkTextBTree *tree)
342 tree->segments_changed_stamp += 1;
346 chars_changed (GtkTextBTree *tree)
348 tree->chars_changed_stamp += 1;
356 _gtk_text_btree_new (GtkTextTagTable *table,
357 GtkTextBuffer *buffer)
360 GtkTextBTreeNode *root_node;
361 GtkTextLine *line, *line2;
363 g_return_val_if_fail (GTK_IS_TEXT_TAG_TABLE (table), NULL);
364 g_return_val_if_fail (GTK_IS_TEXT_BUFFER (buffer), NULL);
367 * The tree will initially have two empty lines. The second line
368 * isn't actually part of the tree's contents, but its presence
369 * makes several operations easier. The tree will have one GtkTextBTreeNode,
370 * which is also the root of the tree.
373 /* Create the root node. */
375 root_node = gtk_text_btree_node_new ();
377 line = gtk_text_line_new ();
378 line2 = gtk_text_line_new ();
380 root_node->parent = NULL;
381 root_node->next = NULL;
382 root_node->summary = NULL;
383 root_node->level = 0;
384 root_node->children.line = line;
385 root_node->num_children = 2;
386 root_node->num_lines = 2;
387 root_node->num_chars = 2;
389 line->parent = root_node;
392 line->segments = _gtk_char_segment_new ("\n", 1);
394 line2->parent = root_node;
396 line2->segments = _gtk_char_segment_new ("\n", 1);
398 /* Create the tree itself */
400 tree = g_new0(GtkTextBTree, 1);
401 tree->root_node = root_node;
405 /* Set these to values that are unlikely to be found
406 * in random memory garbage, and also avoid
407 * duplicates between tree instances.
409 tree->chars_changed_stamp = g_random_int ();
410 tree->segments_changed_stamp = g_random_int ();
412 tree->end_iter_line_stamp = tree->chars_changed_stamp - 1;
413 tree->end_iter_line = NULL;
415 g_object_ref (G_OBJECT (tree->table));
417 tree->tag_changed_handler = g_signal_connect (G_OBJECT (tree->table),
419 G_CALLBACK (tag_changed_cb),
422 tree->tag_removed_handler = g_signal_connect (G_OBJECT (tree->table),
424 G_CALLBACK (tag_removed_cb),
427 tree->mark_table = g_hash_table_new (g_str_hash, g_str_equal);
428 tree->child_anchor_table = NULL;
430 /* We don't ref the buffer, since the buffer owns us;
431 * we'd have some circularity issues. The buffer always
432 * lasts longer than the BTree
434 tree->buffer = buffer;
438 GtkTextLineSegment *seg;
440 _gtk_text_btree_get_iter_at_line_char (tree, &start, 0, 0);
443 tree->insert_mark = _gtk_text_btree_set_mark (tree,
450 seg = tree->insert_mark->segment;
452 seg->body.mark.not_deleteable = TRUE;
453 seg->body.mark.visible = TRUE;
455 tree->selection_bound_mark = _gtk_text_btree_set_mark (tree,
462 seg = tree->selection_bound_mark->segment;
464 seg->body.mark.not_deleteable = TRUE;
466 g_object_ref (G_OBJECT (tree->insert_mark));
467 g_object_ref (G_OBJECT (tree->selection_bound_mark));
476 _gtk_text_btree_ref (GtkTextBTree *tree)
478 g_return_if_fail (tree != NULL);
479 g_return_if_fail (tree->refcount > 0);
485 mark_destroy_foreach (gpointer key, gpointer value, gpointer user_data)
487 GtkTextLineSegment *seg = value;
489 g_return_if_fail (seg->body.mark.tree == NULL);
491 g_object_unref (G_OBJECT (seg->body.mark.obj));
495 _gtk_text_btree_unref (GtkTextBTree *tree)
497 g_return_if_fail (tree != NULL);
498 g_return_if_fail (tree->refcount > 0);
502 if (tree->refcount == 0)
504 gtk_text_btree_node_destroy (tree, tree->root_node);
506 g_hash_table_foreach (tree->mark_table,
507 mark_destroy_foreach,
509 g_hash_table_destroy (tree->mark_table);
511 g_object_unref (G_OBJECT (tree->insert_mark));
512 g_object_unref (G_OBJECT (tree->selection_bound_mark));
514 g_signal_handler_disconnect (G_OBJECT (tree->table),
515 tree->tag_changed_handler);
517 g_signal_handler_disconnect (G_OBJECT (tree->table),
518 tree->tag_removed_handler);
520 g_object_unref (G_OBJECT (tree->table));
527 _gtk_text_btree_get_buffer (GtkTextBTree *tree)
533 _gtk_text_btree_get_chars_changed_stamp (GtkTextBTree *tree)
535 return tree->chars_changed_stamp;
539 _gtk_text_btree_get_segments_changed_stamp (GtkTextBTree *tree)
541 return tree->segments_changed_stamp;
545 _gtk_text_btree_segments_changed (GtkTextBTree *tree)
547 g_return_if_fail (tree != NULL);
548 segments_changed (tree);
552 * Indexable segment mutation
556 _gtk_text_btree_delete (GtkTextIter *start,
559 GtkTextLineSegment *prev_seg; /* The segment just before the start
560 * of the deletion range. */
561 GtkTextLineSegment *last_seg; /* The segment just after the end
562 * of the deletion range. */
563 GtkTextLineSegment *seg, *next;
564 GtkTextLine *curline;
565 GtkTextBTreeNode *curnode, *node;
567 GtkTextLine *start_line;
568 GtkTextLine *end_line;
569 GtkTextLine *deleted_lines = NULL; /* List of lines we've deleted */
570 gint start_byte_offset;
572 g_return_if_fail (start != NULL);
573 g_return_if_fail (end != NULL);
574 g_return_if_fail (_gtk_text_iter_get_btree (start) ==
575 _gtk_text_iter_get_btree (end));
577 gtk_text_iter_order (start, end);
579 tree = _gtk_text_iter_get_btree (start);
581 if (gtk_debug_flags & GTK_DEBUG_TEXT)
582 _gtk_text_btree_check (tree);
586 * The code below is ugly, but it's needed to make sure there
587 * is always a dummy empty line at the end of the text. If the
588 * final newline of the file (just before the dummy line) is being
589 * deleted, then back up index to just before the newline. If
590 * there is a newline just before the first character being deleted,
591 * then back up the first index too, so that an even number of lines
592 * gets deleted. Furthermore, remove any tags that are present on
593 * the newline that isn't going to be deleted after all (this simulates
594 * deleting the newline and then adding a "clean" one back again).
600 line1 = gtk_text_iter_get_line (start);
601 line2 = gtk_text_iter_get_line (end);
603 if (line2 == _gtk_text_btree_line_count (tree))
607 GtkTextIter orig_end;
610 gtk_text_iter_backward_char (end);
614 if (gtk_text_iter_get_line_offset (start) == 0 &&
617 gtk_text_iter_backward_char (start);
621 tags = _gtk_text_btree_get_tags (end,
629 while (i < array_size)
631 _gtk_text_btree_tag (end, &orig_end, tags[i], FALSE);
641 /* Broadcast the need for redisplay before we break the iterators */
642 _gtk_text_btree_invalidate_region (tree, start, end);
644 /* Save the byte offset so we can reset the iterators */
645 start_byte_offset = gtk_text_iter_get_line_index (start);
647 start_line = _gtk_text_iter_get_text_line (start);
648 end_line = _gtk_text_iter_get_text_line (end);
651 * Split the start and end segments, so we have a place
652 * to insert our new text.
654 * Tricky point: split at end first; otherwise the split
655 * at end may invalidate seg and/or prev_seg. This allows
656 * us to avoid invalidating segments for start.
659 last_seg = gtk_text_line_segment_split (end);
660 if (last_seg != NULL)
661 last_seg = last_seg->next;
663 last_seg = end_line->segments;
665 prev_seg = gtk_text_line_segment_split (start);
666 if (prev_seg != NULL)
668 seg = prev_seg->next;
669 prev_seg->next = last_seg;
673 seg = start_line->segments;
674 start_line->segments = last_seg;
677 /* notify iterators that their segments need recomputation,
678 just for robustness. */
679 segments_changed (tree);
682 * Delete all of the segments between prev_seg and last_seg.
685 curline = start_line;
686 curnode = curline->parent;
687 while (seg != last_seg)
693 GtkTextLine *nextline;
696 * We just ran off the end of a line. First find the
697 * next line, then go back to the old line and delete it
698 * (unless it's the starting line for the range).
701 nextline = _gtk_text_line_next (curline);
702 if (curline != start_line)
704 if (curnode == start_line->parent)
705 start_line->next = curline->next;
707 curnode->children.line = curline->next;
709 for (node = curnode; node != NULL;
712 /* Don't update node->num_chars, because
713 * that was done when we deleted the segments.
715 node->num_lines -= 1;
718 curnode->num_children -= 1;
719 curline->next = deleted_lines;
720 deleted_lines = curline;
724 seg = curline->segments;
727 * If the GtkTextBTreeNode is empty then delete it and its parents,
728 * recursively upwards until a non-empty GtkTextBTreeNode is found.
731 while (curnode->num_children == 0)
733 GtkTextBTreeNode *parent;
735 parent = curnode->parent;
736 if (parent->children.node == curnode)
738 parent->children.node = curnode->next;
742 GtkTextBTreeNode *prevnode = parent->children.node;
743 while (prevnode->next != curnode)
745 prevnode = prevnode->next;
747 prevnode->next = curnode->next;
749 parent->num_children--;
750 gtk_text_btree_node_free_empty (tree, curnode);
753 curnode = curline->parent;
758 char_count = seg->char_count;
760 if ((*seg->type->deleteFunc)(seg, curline, 0) != 0)
763 * This segment refuses to die. Move it to prev_seg and
764 * advance prev_seg if the segment has left gravity.
767 if (prev_seg == NULL)
769 seg->next = start_line->segments;
770 start_line->segments = seg;
774 seg->next = prev_seg->next;
775 prev_seg->next = seg;
777 if (seg->type->leftGravity)
784 /* Segment is gone. Decrement the char count of the node and
786 for (node = curnode; node != NULL;
789 node->num_chars -= char_count;
797 * If the beginning and end of the deletion range are in different
798 * lines, join the two lines together and discard the ending line.
801 if (start_line != end_line)
804 GtkTextBTreeNode *ancestor_node;
805 GtkTextLine *prevline;
808 /* last_seg was appended to start_line up at the top of this function */
810 for (seg = last_seg; seg != NULL;
813 chars_moved += seg->char_count;
814 if (seg->type->lineChangeFunc != NULL)
816 (*seg->type->lineChangeFunc)(seg, end_line);
820 for (node = start_line->parent; node != NULL;
823 node->num_chars += chars_moved;
826 curnode = end_line->parent;
827 for (node = curnode; node != NULL;
830 node->num_chars -= chars_moved;
833 curnode->num_children--;
834 prevline = curnode->children.line;
835 if (prevline == end_line)
837 curnode->children.line = end_line->next;
841 while (prevline->next != end_line)
843 prevline = prevline->next;
845 prevline->next = end_line->next;
847 end_line->next = deleted_lines;
848 deleted_lines = end_line;
850 /* We now fix up the per-view aggregates. We add all the height and
851 * width for the deleted lines to the start line, so that when revalidation
852 * occurs, the correct change in size is seen.
854 ancestor_node = gtk_text_btree_node_common_parent (curnode, start_line->parent);
861 gint deleted_width = 0;
862 gint deleted_height = 0;
864 line = deleted_lines;
867 GtkTextLine *next_line = line->next;
868 ld = _gtk_text_line_get_data (line, view->view_id);
872 deleted_width = MAX (deleted_width, ld->width);
873 deleted_height += ld->height;
877 gtk_text_line_destroy (tree, line);
882 if (deleted_width > 0 || deleted_height > 0)
884 ld = _gtk_text_line_get_data (start_line, view->view_id);
886 /* FIXME: ld is _NOT_ necessarily non-null here, but there is currently
887 * no way to add ld without also validating the node, which would
888 * be improper at this point.
890 /* This assertion does actually fail sometimes, must
891 fix before stable release -hp */
894 ld->width = MAX (deleted_width, ld->width);
895 ld->height += deleted_height;
899 gtk_text_btree_node_check_valid_downward (ancestor_node, view->view_id);
900 if (ancestor_node->parent)
901 gtk_text_btree_node_check_valid_upward (ancestor_node->parent, view->view_id);
906 /* avoid dangling pointer */
907 deleted_lines = NULL;
909 gtk_text_btree_rebalance (tree, curnode);
913 * Cleanup the segments in the new line.
916 cleanup_line (start_line);
919 * Lastly, rebalance the first GtkTextBTreeNode of the range.
922 gtk_text_btree_rebalance (tree, start_line->parent);
924 /* Notify outstanding iterators that they
926 chars_changed (tree);
927 segments_changed (tree);
929 if (gtk_debug_flags & GTK_DEBUG_TEXT)
930 _gtk_text_btree_check (tree);
932 /* Re-initialize our iterators */
933 _gtk_text_btree_get_iter_at_line (tree, start, start_line, start_byte_offset);
938 _gtk_text_btree_insert (GtkTextIter *iter,
942 GtkTextLineSegment *prev_seg; /* The segment just before the first
943 * new segment (NULL means new segment
944 * is at beginning of line). */
945 GtkTextLineSegment *cur_seg; /* Current segment; new characters
946 * are inserted just after this one.
947 * NULL means insert at beginning of
949 GtkTextLine *line; /* Current line (new segments are
950 * added to this line). */
951 GtkTextLineSegment *seg;
952 GtkTextLine *newline;
953 int chunk_len; /* # characters in current chunk. */
954 gint sol; /* start of line */
955 gint eol; /* Pointer to character just after last
956 * one in current chunk.
958 gint delim; /* index of paragraph delimiter */
959 int line_count_delta; /* Counts change to total number of
963 int char_count_delta; /* change to number of chars */
965 gint start_byte_index;
966 GtkTextLine *start_line;
968 g_return_if_fail (text != NULL);
969 g_return_if_fail (iter != NULL);
974 /* extract iterator info */
975 tree = _gtk_text_iter_get_btree (iter);
976 line = _gtk_text_iter_get_text_line (iter);
978 start_byte_index = gtk_text_iter_get_line_index (iter);
980 /* Get our insertion segment split */
981 prev_seg = gtk_text_line_segment_split (iter);
984 /* Invalidate all iterators */
985 chars_changed (tree);
986 segments_changed (tree);
989 * Chop the text up into lines and create a new segment for
990 * each line, plus a new line for the leftovers from the
996 line_count_delta = 0;
997 char_count_delta = 0;
1002 pango_find_paragraph_boundary (text + sol,
1007 /* make these relative to the start of the text */
1011 g_assert (eol >= sol);
1012 g_assert (delim >= sol);
1013 g_assert (eol >= delim);
1014 g_assert (sol >= 0);
1015 g_assert (eol <= len);
1017 chunk_len = eol - sol;
1019 g_assert (g_utf8_validate (&text[sol], chunk_len, NULL));
1020 seg = _gtk_char_segment_new (&text[sol], chunk_len);
1022 char_count_delta += seg->char_count;
1024 if (cur_seg == NULL)
1026 seg->next = line->segments;
1027 line->segments = seg;
1031 seg->next = cur_seg->next;
1032 cur_seg->next = seg;
1037 /* chunk didn't end with a paragraph separator */
1038 g_assert (eol == len);
1043 * The chunk ended with a newline, so create a new GtkTextLine
1044 * and move the remainder of the old line to it.
1047 newline = gtk_text_line_new ();
1048 gtk_text_line_set_parent (newline, line->parent);
1049 newline->next = line->next;
1050 line->next = newline;
1051 newline->segments = seg->next;
1059 * Cleanup the starting line for the insertion, plus the ending
1060 * line if it's different.
1063 cleanup_line (start_line);
1064 if (line != start_line)
1066 cleanup_line (line);
1069 post_insert_fixup (tree, line, line_count_delta, char_count_delta);
1071 /* Invalidate our region, and reset the iterator the user
1072 passed in to point to the end of the inserted text. */
1078 _gtk_text_btree_get_iter_at_line (tree,
1084 /* We could almost certainly be more efficient here
1085 by saving the information from the insertion loop
1087 gtk_text_iter_forward_chars (&end, char_count_delta);
1089 _gtk_text_btree_invalidate_region (tree,
1093 /* Convenience for the user */
1099 insert_pixbuf_or_widget_segment (GtkTextIter *iter,
1100 GtkTextLineSegment *seg)
1104 GtkTextLineSegment *prevPtr;
1107 gint start_byte_offset;
1109 line = _gtk_text_iter_get_text_line (iter);
1110 tree = _gtk_text_iter_get_btree (iter);
1111 start_byte_offset = gtk_text_iter_get_line_index (iter);
1113 prevPtr = gtk_text_line_segment_split (iter);
1114 if (prevPtr == NULL)
1116 seg->next = line->segments;
1117 line->segments = seg;
1121 seg->next = prevPtr->next;
1122 prevPtr->next = seg;
1125 post_insert_fixup (tree, line, 0, seg->char_count);
1127 chars_changed (tree);
1128 segments_changed (tree);
1130 /* reset *iter for the user, and invalidate tree nodes */
1132 _gtk_text_btree_get_iter_at_line (tree, &start, line, start_byte_offset);
1135 gtk_text_iter_forward_char (iter); /* skip forward past the segment */
1137 _gtk_text_btree_invalidate_region (tree, &start, iter);
1141 _gtk_text_btree_insert_pixbuf (GtkTextIter *iter,
1144 GtkTextLineSegment *seg;
1146 seg = _gtk_pixbuf_segment_new (pixbuf);
1148 insert_pixbuf_or_widget_segment (iter, seg);
1152 _gtk_text_btree_insert_child_anchor (GtkTextIter *iter,
1153 GtkTextChildAnchor *anchor)
1155 GtkTextLineSegment *seg;
1158 if (anchor->segment != NULL)
1160 g_warning (G_STRLOC": Same child anchor can't be inserted twice");
1164 seg = _gtk_widget_segment_new (anchor);
1166 tree = seg->body.child.tree = _gtk_text_iter_get_btree (iter);
1168 insert_pixbuf_or_widget_segment (iter, seg);
1170 if (tree->child_anchor_table == NULL)
1171 tree->child_anchor_table = g_hash_table_new (NULL, NULL);
1173 g_hash_table_insert (tree->child_anchor_table,
1174 seg->body.child.obj,
1175 seg->body.child.obj);
1179 _gtk_text_btree_unregister_child_anchor (GtkTextChildAnchor *anchor)
1181 GtkTextLineSegment *seg;
1183 seg = anchor->segment;
1185 g_hash_table_remove (seg->body.child.tree->child_anchor_table,
1194 find_line_by_y (GtkTextBTree *tree, BTreeView *view,
1195 GtkTextBTreeNode *node, gint y, gint *line_top,
1196 GtkTextLine *last_line)
1200 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1201 _gtk_text_btree_check (tree);
1203 if (node->level == 0)
1207 line = node->children.line;
1209 while (line != NULL && line != last_line)
1211 GtkTextLineData *ld;
1213 ld = _gtk_text_line_get_data (line, view->view_id);
1217 if (y < (current_y + (ld ? ld->height : 0)))
1220 current_y += ld->height;
1221 *line_top += ld->height;
1230 GtkTextBTreeNode *child;
1232 child = node->children.node;
1234 while (child != NULL)
1239 gtk_text_btree_node_get_size (child, view->view_id,
1242 if (y < (current_y + height))
1243 return find_line_by_y (tree, view, child,
1244 y - current_y, line_top,
1247 current_y += height;
1248 *line_top += height;
1250 child = child->next;
1258 _gtk_text_btree_find_line_by_y (GtkTextBTree *tree,
1265 GtkTextLine *last_line;
1268 view = gtk_text_btree_get_view (tree, view_id);
1269 g_return_val_if_fail (view != NULL, NULL);
1271 last_line = get_last_line (tree);
1273 line = find_line_by_y (tree, view, tree->root_node, ypixel, &line_top,
1277 *line_top_out = line_top;
1283 find_line_top_in_line_list (GtkTextBTree *tree,
1286 GtkTextLine *target_line,
1289 while (line != NULL)
1291 GtkTextLineData *ld;
1293 if (line == target_line)
1296 ld = _gtk_text_line_get_data (line, view->view_id);
1303 g_assert_not_reached (); /* If we get here, our
1304 target line didn't exist
1305 under its parent node */
1310 _gtk_text_btree_find_line_top (GtkTextBTree *tree,
1311 GtkTextLine *target_line,
1318 GtkTextBTreeNode *node;
1320 view = gtk_text_btree_get_view (tree, view_id);
1322 g_return_val_if_fail (view != NULL, 0);
1325 node = target_line->parent;
1326 while (node != NULL)
1328 nodes = g_slist_prepend (nodes, node);
1329 node = node->parent;
1333 while (iter != NULL)
1337 if (node->level == 0)
1339 g_slist_free (nodes);
1340 return find_line_top_in_line_list (tree, view,
1341 node->children.line,
1346 GtkTextBTreeNode *child;
1347 GtkTextBTreeNode *target_node;
1349 g_assert (iter->next != NULL); /* not at level 0 */
1350 target_node = iter->next->data;
1352 child = node->children.node;
1354 while (child != NULL)
1359 if (child == target_node)
1363 gtk_text_btree_node_get_size (child, view->view_id,
1367 child = child->next;
1369 g_assert (child != NULL); /* should have broken out before we
1373 iter = g_slist_next (iter);
1376 g_assert_not_reached (); /* we return when we find the target line */
1381 _gtk_text_btree_add_view (GtkTextBTree *tree,
1382 GtkTextLayout *layout)
1385 GtkTextLine *last_line;
1386 GtkTextLineData *line_data;
1388 g_return_if_fail (tree != NULL);
1390 view = g_new (BTreeView, 1);
1392 view->view_id = layout;
1393 view->layout = layout;
1395 view->next = tree->views;
1400 g_assert (tree->views->prev == NULL);
1401 tree->views->prev = view;
1406 /* The last line in the buffer has identity values for the per-view
1407 * data so that we can avoid special case checks for it in a large
1410 last_line = get_last_line (tree);
1412 line_data = g_new (GtkTextLineData, 1);
1413 line_data->view_id = layout;
1414 line_data->next = NULL;
1415 line_data->width = 0;
1416 line_data->height = 0;
1417 line_data->valid = TRUE;
1419 _gtk_text_line_add_data (last_line, line_data);
1423 _gtk_text_btree_remove_view (GtkTextBTree *tree,
1427 GtkTextLine *last_line;
1428 GtkTextLineData *line_data;
1430 g_return_if_fail (tree != NULL);
1434 while (view != NULL)
1436 if (view->view_id == view_id)
1442 g_return_if_fail (view != NULL);
1445 view->next->prev = view->prev;
1448 view->prev->next = view->next;
1450 if (view == tree->views)
1451 tree->views = view->next;
1453 /* Remove the line data for the last line which we added ourselves.
1454 * (Do this first, so that we don't try to call the view's line data destructor on it.)
1456 last_line = get_last_line (tree);
1457 line_data = _gtk_text_line_remove_data (last_line, view_id);
1460 gtk_text_btree_node_remove_view (view, tree->root_node, view_id);
1462 view->layout = (gpointer) 0xdeadbeef;
1463 view->view_id = (gpointer) 0xdeadbeef;
1469 _gtk_text_btree_invalidate_region (GtkTextBTree *tree,
1470 const GtkTextIter *start,
1471 const GtkTextIter *end)
1477 while (view != NULL)
1479 gtk_text_layout_invalidate (view->layout, start, end);
1486 _gtk_text_btree_get_view_size (GtkTextBTree *tree,
1491 g_return_if_fail (tree != NULL);
1492 g_return_if_fail (view_id != NULL);
1494 gtk_text_btree_node_get_size (tree->root_node, view_id,
1509 iter_stack_new (void)
1512 stack = g_new (IterStack, 1);
1513 stack->iters = NULL;
1520 iter_stack_push (IterStack *stack, const GtkTextIter *iter)
1523 if (stack->count > stack->alloced)
1525 stack->alloced = stack->count*2;
1526 stack->iters = g_realloc (stack->iters,
1527 stack->alloced*sizeof (GtkTextIter));
1529 stack->iters[stack->count-1] = *iter;
1533 iter_stack_pop (IterStack *stack, GtkTextIter *iter)
1535 if (stack->count == 0)
1540 *iter = stack->iters[stack->count];
1546 iter_stack_free (IterStack *stack)
1548 g_free (stack->iters);
1553 iter_stack_invert (IterStack *stack)
1555 if (stack->count > 0)
1558 guint j = stack->count - 1;
1563 tmp = stack->iters[i];
1564 stack->iters[i] = stack->iters[j];
1565 stack->iters[j] = tmp;
1574 queue_tag_redisplay (GtkTextBTree *tree,
1576 const GtkTextIter *start,
1577 const GtkTextIter *end)
1579 if (_gtk_text_tag_affects_size (tag))
1581 _gtk_text_btree_invalidate_region (tree, start, end);
1583 else if (_gtk_text_tag_affects_nonsize_appearance (tag))
1585 /* We only need to queue a redraw, not a relayout */
1586 redisplay_region (tree, start, end);
1589 /* We don't need to do anything if the tag doesn't affect display */
1593 _gtk_text_btree_tag (const GtkTextIter *start_orig,
1594 const GtkTextIter *end_orig,
1598 GtkTextLineSegment *seg, *prev;
1599 GtkTextLine *cleanupline;
1600 gboolean toggled_on;
1601 GtkTextLine *start_line;
1602 GtkTextLine *end_line;
1604 GtkTextIter start, end;
1607 GtkTextTagInfo *info;
1609 g_return_if_fail (start_orig != NULL);
1610 g_return_if_fail (end_orig != NULL);
1611 g_return_if_fail (GTK_IS_TEXT_TAG (tag));
1612 g_return_if_fail (_gtk_text_iter_get_btree (start_orig) ==
1613 _gtk_text_iter_get_btree (end_orig));
1614 g_return_if_fail (tag->table == _gtk_text_iter_get_btree (start_orig)->table);
1617 printf ("%s tag %s from %d to %d\n",
1618 add ? "Adding" : "Removing",
1620 gtk_text_buffer_get_offset (start_orig),
1621 gtk_text_buffer_get_offset (end_orig));
1624 if (gtk_text_iter_equal (start_orig, end_orig))
1627 start = *start_orig;
1630 gtk_text_iter_order (&start, &end);
1632 tree = _gtk_text_iter_get_btree (&start);
1634 queue_tag_redisplay (tree, tag, &start, &end);
1636 info = gtk_text_btree_get_tag_info (tree, tag);
1638 start_line = _gtk_text_iter_get_text_line (&start);
1639 end_line = _gtk_text_iter_get_text_line (&end);
1641 /* Find all tag toggles in the region; we are going to delete them.
1642 We need to find them in advance, because
1643 forward_find_tag_toggle () won't work once we start playing around
1645 stack = iter_stack_new ();
1648 /* forward_to_tag_toggle() skips a toggle at the start iterator,
1649 * which is deliberate - we don't want to delete a toggle at the
1652 while (gtk_text_iter_forward_to_tag_toggle (&iter, tag))
1654 if (gtk_text_iter_compare (&iter, &end) >= 0)
1657 iter_stack_push (stack, &iter);
1660 /* We need to traverse the toggles in order. */
1661 iter_stack_invert (stack);
1664 * See whether the tag is present at the start of the range. If
1665 * the state doesn't already match what we want then add a toggle
1669 toggled_on = gtk_text_iter_has_tag (&start, tag);
1670 if ( (add && !toggled_on) ||
1671 (!add && toggled_on) )
1673 /* This could create a second toggle at the start position;
1674 cleanup_line () will remove it if so. */
1675 seg = _gtk_toggle_segment_new (info, add);
1677 prev = gtk_text_line_segment_split (&start);
1680 seg->next = start_line->segments;
1681 start_line->segments = seg;
1685 seg->next = prev->next;
1689 /* cleanup_line adds the new toggle to the node counts. */
1691 printf ("added toggle at start\n");
1693 /* we should probably call segments_changed, but in theory
1694 any still-cached segments in the iters we are about to
1695 use are still valid, since they're in front
1701 * Scan the range of characters and delete any internal tag
1702 * transitions. Keep track of what the old state was at the end
1703 * of the range, and add a toggle there if it's needed.
1707 cleanupline = start_line;
1708 while (iter_stack_pop (stack, &iter))
1710 GtkTextLineSegment *indexable_seg;
1713 line = _gtk_text_iter_get_text_line (&iter);
1714 seg = _gtk_text_iter_get_any_segment (&iter);
1715 indexable_seg = _gtk_text_iter_get_indexable_segment (&iter);
1717 g_assert (seg != NULL);
1718 g_assert (indexable_seg != NULL);
1719 g_assert (seg != indexable_seg);
1721 prev = line->segments;
1723 /* Find the segment that actually toggles this tag. */
1724 while (seg != indexable_seg)
1726 g_assert (seg != NULL);
1727 g_assert (indexable_seg != NULL);
1728 g_assert (seg != indexable_seg);
1730 if ( (seg->type == >k_text_toggle_on_type ||
1731 seg->type == >k_text_toggle_off_type) &&
1732 (seg->body.toggle.info == info) )
1738 g_assert (seg != NULL);
1739 g_assert (indexable_seg != NULL);
1741 g_assert (seg != indexable_seg); /* If this happens, then
1742 forward_to_tag_toggle was
1744 g_assert (seg->body.toggle.info->tag == tag);
1746 /* If this happens, when previously tagging we didn't merge
1747 overlapping tags. */
1748 g_assert ( (toggled_on && seg->type == >k_text_toggle_off_type) ||
1749 (!toggled_on && seg->type == >k_text_toggle_on_type) );
1751 toggled_on = !toggled_on;
1754 printf ("deleting %s toggle\n",
1755 seg->type == >k_text_toggle_on_type ? "on" : "off");
1757 /* Remove toggle segment from the list. */
1760 line->segments = seg->next;
1764 while (prev->next != seg)
1768 prev->next = seg->next;
1771 /* Inform iterators we've hosed them. This actually reflects a
1772 bit of inefficiency; if you have the same tag toggled on and
1773 off a lot in a single line, we keep having the rescan from
1774 the front of the line. Of course we have to do that to get
1775 "prev" anyway, but here we are doing it an additional
1777 segments_changed (tree);
1779 /* Update node counts */
1780 if (seg->body.toggle.inNodeCounts)
1782 _gtk_change_node_toggle_count (line->parent,
1784 seg->body.toggle.inNodeCounts = FALSE;
1789 /* We only clean up lines when we're done with them, saves some
1790 gratuitous line-segment-traversals */
1792 if (cleanupline != line)
1794 cleanup_line (cleanupline);
1799 iter_stack_free (stack);
1801 /* toggled_on now reflects the toggle state _just before_ the
1802 end iterator. The end iterator could already have a toggle
1803 on or a toggle off. */
1804 if ( (add && !toggled_on) ||
1805 (!add && toggled_on) )
1807 /* This could create a second toggle at the start position;
1808 cleanup_line () will remove it if so. */
1810 seg = _gtk_toggle_segment_new (info, !add);
1812 prev = gtk_text_line_segment_split (&end);
1815 seg->next = end_line->segments;
1816 end_line->segments = seg;
1820 seg->next = prev->next;
1823 /* cleanup_line adds the new toggle to the node counts. */
1824 g_assert (seg->body.toggle.inNodeCounts == FALSE);
1826 printf ("added toggle at end\n");
1831 * Cleanup cleanupline and the last line of the range, if
1832 * these are different.
1835 cleanup_line (cleanupline);
1836 if (cleanupline != end_line)
1838 cleanup_line (end_line);
1841 segments_changed (tree);
1843 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1844 _gtk_text_btree_check (tree);
1853 _gtk_text_btree_get_line (GtkTextBTree *tree,
1855 gint *real_line_number)
1857 GtkTextBTreeNode *node;
1862 line_count = _gtk_text_btree_line_count (tree);
1864 if (line_number < 0)
1866 line_number = line_count;
1868 else if (line_number > line_count)
1870 line_number = line_count;
1873 if (real_line_number)
1874 *real_line_number = line_number;
1876 node = tree->root_node;
1877 lines_left = line_number;
1880 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1884 while (node->level != 0)
1886 for (node = node->children.node;
1887 node->num_lines <= lines_left;
1893 g_error ("gtk_text_btree_find_line ran out of GtkTextBTreeNodes");
1896 lines_left -= node->num_lines;
1901 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1904 for (line = node->children.line; lines_left > 0;
1910 g_error ("gtk_text_btree_find_line ran out of lines");
1919 _gtk_text_btree_get_line_at_char (GtkTextBTree *tree,
1921 gint *line_start_index,
1922 gint *real_char_index)
1924 GtkTextBTreeNode *node;
1926 GtkTextLineSegment *seg;
1931 node = tree->root_node;
1933 /* Clamp to valid indexes (-1 is magic for "highest index") */
1934 if (char_index < 0 || char_index >= node->num_chars)
1936 char_index = node->num_chars - 1;
1939 *real_char_index = char_index;
1942 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1946 chars_left = char_index;
1947 while (node->level != 0)
1949 for (node = node->children.node;
1950 chars_left >= node->num_chars;
1953 chars_left -= node->num_chars;
1955 g_assert (chars_left >= 0);
1959 if (chars_left == 0)
1961 /* Start of a line */
1963 *line_start_index = char_index;
1964 return node->children.line;
1968 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1974 for (line = node->children.line; line != NULL; line = line->next)
1976 seg = line->segments;
1979 if (chars_in_line + seg->char_count > chars_left)
1980 goto found; /* found our line/segment */
1982 chars_in_line += seg->char_count;
1987 chars_left -= chars_in_line;
1995 g_assert (line != NULL); /* hosage, ran out of lines */
1996 g_assert (seg != NULL);
1998 *line_start_index = char_index - chars_left;
2003 _gtk_text_btree_get_tags (const GtkTextIter *iter,
2006 GtkTextBTreeNode *node;
2007 GtkTextLine *siblingline;
2008 GtkTextLineSegment *seg;
2009 int src, dst, index;
2015 #define NUM_TAG_INFOS 10
2017 line = _gtk_text_iter_get_text_line (iter);
2018 tree = _gtk_text_iter_get_btree (iter);
2019 byte_index = gtk_text_iter_get_line_index (iter);
2021 tagInfo.numTags = 0;
2022 tagInfo.arraySize = NUM_TAG_INFOS;
2023 tagInfo.tags = g_new (GtkTextTag*, NUM_TAG_INFOS);
2024 tagInfo.counts = g_new (int, NUM_TAG_INFOS);
2027 * Record tag toggles within the line of indexPtr but preceding
2028 * indexPtr. Note that if this loop segfaults, your
2029 * byte_index probably points past the sum of all
2030 * seg->byte_count */
2032 for (index = 0, seg = line->segments;
2033 (index + seg->byte_count) <= byte_index;
2034 index += seg->byte_count, seg = seg->next)
2036 if ((seg->type == >k_text_toggle_on_type)
2037 || (seg->type == >k_text_toggle_off_type))
2039 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2044 * Record toggles for tags in lines that are predecessors of
2045 * line but under the same level-0 GtkTextBTreeNode.
2048 for (siblingline = line->parent->children.line;
2049 siblingline != line;
2050 siblingline = siblingline->next)
2052 for (seg = siblingline->segments; seg != NULL;
2055 if ((seg->type == >k_text_toggle_on_type)
2056 || (seg->type == >k_text_toggle_off_type))
2058 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2064 * For each GtkTextBTreeNode in the ancestry of this line, record tag
2065 * toggles for all siblings that precede that GtkTextBTreeNode.
2068 for (node = line->parent; node->parent != NULL;
2069 node = node->parent)
2071 GtkTextBTreeNode *siblingPtr;
2074 for (siblingPtr = node->parent->children.node;
2075 siblingPtr != node; siblingPtr = siblingPtr->next)
2077 for (summary = siblingPtr->summary; summary != NULL;
2078 summary = summary->next)
2080 if (summary->toggle_count & 1)
2082 inc_count (summary->info->tag, summary->toggle_count,
2090 * Go through the tag information and squash out all of the tags
2091 * that have even toggle counts (these tags exist before the point
2092 * of interest, but not at the desired character itself).
2095 for (src = 0, dst = 0; src < tagInfo.numTags; src++)
2097 if (tagInfo.counts[src] & 1)
2099 g_assert (GTK_IS_TEXT_TAG (tagInfo.tags[src]));
2100 tagInfo.tags[dst] = tagInfo.tags[src];
2106 g_free (tagInfo.counts);
2109 g_free (tagInfo.tags);
2112 return tagInfo.tags;
2116 copy_segment (GString *string,
2117 gboolean include_hidden,
2118 gboolean include_nonchars,
2119 const GtkTextIter *start,
2120 const GtkTextIter *end)
2122 GtkTextLineSegment *end_seg;
2123 GtkTextLineSegment *seg;
2125 if (gtk_text_iter_equal (start, end))
2128 seg = _gtk_text_iter_get_indexable_segment (start);
2129 end_seg = _gtk_text_iter_get_indexable_segment (end);
2131 if (seg->type == >k_text_char_type)
2133 gboolean copy = TRUE;
2134 gint copy_bytes = 0;
2135 gint copy_start = 0;
2137 /* Don't copy if we're invisible; segments are invisible/not
2138 as a whole, no need to check each char */
2139 if (!include_hidden &&
2140 _gtk_text_btree_char_is_invisible (start))
2143 /* printf (" <invisible>\n"); */
2146 copy_start = _gtk_text_iter_get_segment_byte (start);
2150 /* End is in the same segment; need to copy fewer bytes. */
2151 gint end_byte = _gtk_text_iter_get_segment_byte (end);
2153 copy_bytes = end_byte - copy_start;
2156 copy_bytes = seg->byte_count - copy_start;
2158 g_assert (copy_bytes != 0); /* Due to iter equality check at
2159 front of this function. */
2163 g_assert ((copy_start + copy_bytes) <= seg->byte_count);
2165 g_string_append_len (string,
2166 seg->body.chars + copy_start,
2170 /* printf (" :%s\n", string->str); */
2172 else if (seg->type == >k_text_pixbuf_type ||
2173 seg->type == >k_text_child_type)
2175 gboolean copy = TRUE;
2177 if (!include_nonchars)
2181 else if (!include_hidden &&
2182 _gtk_text_btree_char_is_invisible (start))
2189 g_string_append_len (string,
2190 gtk_text_unknown_char_utf8,
2198 _gtk_text_btree_get_text (const GtkTextIter *start_orig,
2199 const GtkTextIter *end_orig,
2200 gboolean include_hidden,
2201 gboolean include_nonchars)
2203 GtkTextLineSegment *seg;
2204 GtkTextLineSegment *end_seg;
2212 g_return_val_if_fail (start_orig != NULL, NULL);
2213 g_return_val_if_fail (end_orig != NULL, NULL);
2214 g_return_val_if_fail (_gtk_text_iter_get_btree (start_orig) ==
2215 _gtk_text_iter_get_btree (end_orig), NULL);
2217 start = *start_orig;
2220 gtk_text_iter_order (&start, &end);
2222 retval = g_string_new ("");
2224 tree = _gtk_text_iter_get_btree (&start);
2226 end_seg = _gtk_text_iter_get_indexable_segment (&end);
2228 seg = _gtk_text_iter_get_indexable_segment (&iter);
2229 while (seg != end_seg)
2231 copy_segment (retval, include_hidden, include_nonchars,
2234 _gtk_text_iter_forward_indexable_segment (&iter);
2236 seg = _gtk_text_iter_get_indexable_segment (&iter);
2239 copy_segment (retval, include_hidden, include_nonchars, &iter, &end);
2242 g_string_free (retval, FALSE);
2247 _gtk_text_btree_line_count (GtkTextBTree *tree)
2249 /* Subtract bogus line at the end; we return a count
2251 return tree->root_node->num_lines - 1;
2255 _gtk_text_btree_char_count (GtkTextBTree *tree)
2257 /* Exclude newline in bogus last line */
2258 return tree->root_node->num_chars - 1;
2261 #define LOTSA_TAGS 1000
2263 _gtk_text_btree_char_is_invisible (const GtkTextIter *iter)
2265 gboolean invisible = FALSE; /* if nobody says otherwise, it's visible */
2267 int deftagCnts[LOTSA_TAGS];
2268 int *tagCnts = deftagCnts;
2269 GtkTextTag *deftags[LOTSA_TAGS];
2270 GtkTextTag **tags = deftags;
2272 GtkTextBTreeNode *node;
2273 GtkTextLine *siblingline;
2274 GtkTextLineSegment *seg;
2281 line = _gtk_text_iter_get_text_line (iter);
2282 tree = _gtk_text_iter_get_btree (iter);
2283 byte_index = gtk_text_iter_get_line_index (iter);
2285 numTags = gtk_text_tag_table_get_size (tree->table);
2287 /* almost always avoid malloc, so stay out of system calls */
2288 if (LOTSA_TAGS < numTags)
2290 tagCnts = g_new (int, numTags);
2291 tags = g_new (GtkTextTag*, numTags);
2294 for (i=0; i<numTags; i++)
2300 * Record tag toggles within the line of indexPtr but preceding
2304 for (index = 0, seg = line->segments;
2305 (index + seg->byte_count) <= byte_index; /* segfault here means invalid index */
2306 index += seg->byte_count, seg = seg->next)
2308 if ((seg->type == >k_text_toggle_on_type)
2309 || (seg->type == >k_text_toggle_off_type))
2311 tag = seg->body.toggle.info->tag;
2312 if (tag->invisible_set && tag->values->invisible)
2314 tags[tag->priority] = tag;
2315 tagCnts[tag->priority]++;
2321 * Record toggles for tags in lines that are predecessors of
2322 * line but under the same level-0 GtkTextBTreeNode.
2325 for (siblingline = line->parent->children.line;
2326 siblingline != line;
2327 siblingline = siblingline->next)
2329 for (seg = siblingline->segments; seg != NULL;
2332 if ((seg->type == >k_text_toggle_on_type)
2333 || (seg->type == >k_text_toggle_off_type))
2335 tag = seg->body.toggle.info->tag;
2336 if (tag->invisible_set && tag->values->invisible)
2338 tags[tag->priority] = tag;
2339 tagCnts[tag->priority]++;
2346 * For each GtkTextBTreeNode in the ancestry of this line, record tag toggles
2347 * for all siblings that precede that GtkTextBTreeNode.
2350 for (node = line->parent; node->parent != NULL;
2351 node = node->parent)
2353 GtkTextBTreeNode *siblingPtr;
2356 for (siblingPtr = node->parent->children.node;
2357 siblingPtr != node; siblingPtr = siblingPtr->next)
2359 for (summary = siblingPtr->summary; summary != NULL;
2360 summary = summary->next)
2362 if (summary->toggle_count & 1)
2364 tag = summary->info->tag;
2365 if (tag->invisible_set && tag->values->invisible)
2367 tags[tag->priority] = tag;
2368 tagCnts[tag->priority] += summary->toggle_count;
2376 * Now traverse from highest priority to lowest,
2377 * take invisible value from first odd count (= on)
2380 for (i = numTags-1; i >=0; i--)
2384 /* FIXME not sure this should be if 0 */
2386 #ifndef ALWAYS_SHOW_SELECTION
2387 /* who would make the selection invisible? */
2388 if ((tag == tkxt->seltag)
2389 && !(tkxt->flags & GOT_FOCUS))
2395 invisible = tags[i]->values->invisible;
2400 if (LOTSA_TAGS < numTags)
2415 redisplay_region (GtkTextBTree *tree,
2416 const GtkTextIter *start,
2417 const GtkTextIter *end)
2420 GtkTextLine *start_line, *end_line;
2422 if (gtk_text_iter_compare (start, end) > 0)
2424 const GtkTextIter *tmp = start;
2429 start_line = _gtk_text_iter_get_text_line (start);
2430 end_line = _gtk_text_iter_get_text_line (end);
2433 while (view != NULL)
2435 gint start_y, end_y;
2436 GtkTextLineData *ld;
2438 start_y = _gtk_text_btree_find_line_top (tree, start_line, view->view_id);
2440 if (end_line == start_line)
2443 end_y = _gtk_text_btree_find_line_top (tree, end_line, view->view_id);
2445 ld = _gtk_text_line_get_data (end_line, view->view_id);
2447 end_y += ld->height;
2449 gtk_text_layout_changed (view->layout, start_y,
2458 redisplay_mark (GtkTextLineSegment *mark)
2463 _gtk_text_btree_get_iter_at_mark (mark->body.mark.tree,
2465 mark->body.mark.obj);
2468 gtk_text_iter_forward_char (&end);
2470 _gtk_text_btree_invalidate_region (mark->body.mark.tree,
2475 redisplay_mark_if_visible (GtkTextLineSegment *mark)
2477 if (!mark->body.mark.visible)
2480 redisplay_mark (mark);
2484 ensure_not_off_end (GtkTextBTree *tree,
2485 GtkTextLineSegment *mark,
2488 if (gtk_text_iter_get_line (iter) ==
2489 _gtk_text_btree_line_count (tree))
2490 gtk_text_iter_backward_char (iter);
2493 static GtkTextLineSegment*
2494 real_set_mark (GtkTextBTree *tree,
2495 GtkTextMark *existing_mark,
2497 gboolean left_gravity,
2498 const GtkTextIter *where,
2499 gboolean should_exist,
2500 gboolean redraw_selections)
2502 GtkTextLineSegment *mark;
2505 g_return_val_if_fail (tree != NULL, NULL);
2506 g_return_val_if_fail (where != NULL, NULL);
2507 g_return_val_if_fail (_gtk_text_iter_get_btree (where) == tree, NULL);
2510 mark = existing_mark->segment;
2511 else if (name != NULL)
2512 mark = g_hash_table_lookup (tree->mark_table,
2517 if (should_exist && mark == NULL)
2519 g_warning ("No mark `%s' exists!", name);
2523 /* OK if !should_exist and it does already exist, in that case
2529 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2530 _gtk_text_iter_check (&iter);
2534 if (redraw_selections &&
2535 (mark == tree->insert_mark->segment ||
2536 mark == tree->selection_bound_mark->segment))
2538 GtkTextIter old_pos;
2540 _gtk_text_btree_get_iter_at_mark (tree, &old_pos,
2541 mark->body.mark.obj);
2542 redisplay_region (tree, &old_pos, where);
2546 * don't let visible marks be after the final newline of the
2550 if (mark->body.mark.visible)
2552 ensure_not_off_end (tree, mark, &iter);
2555 /* Redraw the mark's old location. */
2556 redisplay_mark_if_visible (mark);
2558 /* Unlink mark from its current location.
2559 This could hose our iterator... */
2560 gtk_text_btree_unlink_segment (tree, mark,
2561 mark->body.mark.line);
2562 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2563 g_assert (mark->body.mark.line == _gtk_text_iter_get_text_line (&iter));
2565 segments_changed (tree); /* make sure the iterator recomputes its
2570 mark = _gtk_mark_segment_new (tree,
2574 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2576 if (mark->body.mark.name)
2577 g_hash_table_insert (tree->mark_table,
2578 mark->body.mark.name,
2582 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2583 _gtk_text_iter_check (&iter);
2585 /* Link mark into new location */
2586 gtk_text_btree_link_segment (mark, &iter);
2588 /* Invalidate some iterators. */
2589 segments_changed (tree);
2592 * update the screen at the mark's new location.
2595 redisplay_mark_if_visible (mark);
2597 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2598 _gtk_text_iter_check (&iter);
2600 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2601 _gtk_text_btree_check (tree);
2608 _gtk_text_btree_set_mark (GtkTextBTree *tree,
2609 GtkTextMark *existing_mark,
2611 gboolean left_gravity,
2612 const GtkTextIter *iter,
2613 gboolean should_exist)
2615 GtkTextLineSegment *seg;
2617 seg = real_set_mark (tree, existing_mark,
2618 name, left_gravity, iter, should_exist,
2621 return seg ? seg->body.mark.obj : NULL;
2625 _gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2629 GtkTextIter tmp_start, tmp_end;
2631 _gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2633 _gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2634 tree->selection_bound_mark);
2636 if (gtk_text_iter_equal (&tmp_start, &tmp_end))
2648 gtk_text_iter_order (&tmp_start, &tmp_end);
2661 _gtk_text_btree_place_cursor (GtkTextBTree *tree,
2662 const GtkTextIter *iter)
2664 GtkTextIter start, end;
2666 if (_gtk_text_btree_get_selection_bounds (tree, &start, &end))
2667 redisplay_region (tree, &start, &end);
2669 /* Move insert AND selection_bound before we redisplay */
2670 real_set_mark (tree, tree->insert_mark,
2671 "insert", FALSE, iter, TRUE, FALSE);
2672 real_set_mark (tree, tree->selection_bound_mark,
2673 "selection_bound", FALSE, iter, TRUE, FALSE);
2677 _gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2682 g_return_if_fail (tree != NULL);
2683 g_return_if_fail (name != NULL);
2685 mark = g_hash_table_lookup (tree->mark_table,
2688 _gtk_text_btree_remove_mark (tree, mark);
2692 _gtk_text_btree_remove_mark (GtkTextBTree *tree,
2695 GtkTextLineSegment *segment;
2697 g_return_if_fail (mark != NULL);
2698 g_return_if_fail (tree != NULL);
2700 segment = mark->segment;
2702 if (segment->body.mark.not_deleteable)
2704 g_warning ("Can't delete special mark `%s'", segment->body.mark.name);
2708 /* This calls cleanup_line and segments_changed */
2709 gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2711 if (segment->body.mark.name)
2712 g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2714 /* Remove the ref on the mark that belonged to the segment. */
2715 g_object_unref (G_OBJECT (mark));
2717 segment->body.mark.tree = NULL;
2718 segment->body.mark.line = NULL;
2722 _gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2723 GtkTextMark *segment)
2725 return segment == tree->insert_mark;
2729 _gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2730 GtkTextMark *segment)
2732 return segment == tree->selection_bound_mark;
2736 _gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2739 GtkTextLineSegment *seg;
2741 g_return_val_if_fail (tree != NULL, NULL);
2742 g_return_val_if_fail (name != NULL, NULL);
2744 seg = g_hash_table_lookup (tree->mark_table, name);
2746 return seg ? seg->body.mark.obj : NULL;
2750 * gtk_text_mark_set_visible:
2751 * @mark: a #GtkTextMark
2752 * @setting: visibility of mark
2754 * Sets the visibility of @mark; the insertion point is normally
2755 * visible, i.e. you can see it as a vertical bar. Also, the text
2756 * widget uses a visible mark to indicate where a drop will occur when
2757 * dragging-and-dropping text. Most other marks are not visible.
2758 * Marks are not visible by default.
2762 gtk_text_mark_set_visible (GtkTextMark *mark,
2765 GtkTextLineSegment *seg;
2767 g_return_if_fail (mark != NULL);
2769 seg = mark->segment;
2771 if (seg->body.mark.visible == setting)
2775 seg->body.mark.visible = setting;
2777 redisplay_mark (seg);
2782 _gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
2785 GtkTextBTreeNode *node;
2786 GtkTextTagInfo *info;
2788 g_return_val_if_fail (tree != NULL, NULL);
2792 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2797 if (info->tag_root == NULL)
2800 node = info->tag_root;
2802 /* We know the tag root has instances of the given
2805 continue_outer_loop:
2806 g_assert (node != NULL);
2807 while (node->level > 0)
2809 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2810 node = node->children.node;
2811 while (node != NULL)
2813 if (gtk_text_btree_node_has_tag (node, tag))
2814 goto continue_outer_loop;
2818 g_assert (node != NULL);
2821 g_assert (node != NULL); /* The tag summaries said some node had
2824 g_assert (node->level == 0);
2826 return node->children.line;
2830 /* Looking for any tag at all (tag == NULL).
2831 Unfortunately this can't be done in a simple and efficient way
2832 right now; so I'm just going to return the
2833 first line in the btree. FIXME */
2834 return _gtk_text_btree_get_line (tree, 0, NULL);
2839 _gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
2842 GtkTextBTreeNode *node;
2843 GtkTextBTreeNode *last_node;
2845 GtkTextTagInfo *info;
2847 g_return_val_if_fail (tree != NULL, NULL);
2851 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2853 if (info->tag_root == NULL)
2856 node = info->tag_root;
2857 /* We know the tag root has instances of the given
2860 while (node->level > 0)
2862 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2864 node = node->children.node;
2865 while (node != NULL)
2867 if (gtk_text_btree_node_has_tag (node, tag))
2875 g_assert (node != NULL); /* The tag summaries said some node had
2878 g_assert (node->level == 0);
2880 /* Find the last line in this node */
2881 line = node->children.line;
2882 while (line->next != NULL)
2889 /* This search can't be done efficiently at the moment,
2890 at least not without complexity.
2891 So, we just return the last line.
2893 return _gtk_text_btree_get_line (tree, -1, NULL);
2903 _gtk_text_line_get_number (GtkTextLine *line)
2906 GtkTextBTreeNode *node, *parent, *node2;
2910 * First count how many lines precede this one in its level-0
2914 node = line->parent;
2916 for (line2 = node->children.line; line2 != line;
2917 line2 = line2->next)
2921 g_error ("gtk_text_btree_line_number couldn't find line");
2927 * Now work up through the levels of the tree one at a time,
2928 * counting how many lines are in GtkTextBTreeNodes preceding the current
2932 for (parent = node->parent ; parent != NULL;
2933 node = parent, parent = parent->parent)
2935 for (node2 = parent->children.node; node2 != node;
2936 node2 = node2->next)
2940 g_error ("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
2942 index += node2->num_lines;
2948 static GtkTextLineSegment*
2949 find_toggle_segment_before_char (GtkTextLine *line,
2953 GtkTextLineSegment *seg;
2954 GtkTextLineSegment *toggle_seg;
2959 seg = line->segments;
2960 while ( (index + seg->char_count) <= char_in_line )
2962 if (((seg->type == >k_text_toggle_on_type)
2963 || (seg->type == >k_text_toggle_off_type))
2964 && (seg->body.toggle.info->tag == tag))
2967 index += seg->char_count;
2974 static GtkTextLineSegment*
2975 find_toggle_segment_before_byte (GtkTextLine *line,
2979 GtkTextLineSegment *seg;
2980 GtkTextLineSegment *toggle_seg;
2985 seg = line->segments;
2986 while ( (index + seg->byte_count) <= byte_in_line )
2988 if (((seg->type == >k_text_toggle_on_type)
2989 || (seg->type == >k_text_toggle_off_type))
2990 && (seg->body.toggle.info->tag == tag))
2993 index += seg->byte_count;
3001 find_toggle_outside_current_line (GtkTextLine *line,
3005 GtkTextBTreeNode *node;
3006 GtkTextLine *sibling_line;
3007 GtkTextLineSegment *seg;
3008 GtkTextLineSegment *toggle_seg;
3010 GtkTextTagInfo *info = NULL;
3013 * No toggle in this line. Look for toggles for the tag in lines
3014 * that are predecessors of line but under the same
3015 * level-0 GtkTextBTreeNode.
3018 sibling_line = line->parent->children.line;
3019 while (sibling_line != line)
3021 seg = sibling_line->segments;
3024 if (((seg->type == >k_text_toggle_on_type)
3025 || (seg->type == >k_text_toggle_off_type))
3026 && (seg->body.toggle.info->tag == tag))
3032 sibling_line = sibling_line->next;
3035 if (toggle_seg != NULL)
3036 return (toggle_seg->type == >k_text_toggle_on_type);
3039 * No toggle in this GtkTextBTreeNode. Scan upwards through the ancestors of
3040 * this GtkTextBTreeNode, counting the number of toggles of the given tag in
3041 * siblings that precede that GtkTextBTreeNode.
3044 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3050 node = line->parent;
3051 while (node->parent != NULL)
3053 GtkTextBTreeNode *sibling_node;
3055 sibling_node = node->parent->children.node;
3056 while (sibling_node != node)
3060 summary = sibling_node->summary;
3061 while (summary != NULL)
3063 if (summary->info == info)
3064 toggles += summary->toggle_count;
3066 summary = summary->next;
3069 sibling_node = sibling_node->next;
3072 if (node == info->tag_root)
3075 node = node->parent;
3079 * An odd number of toggles means that the tag is present at the
3083 return (toggles & 1) != 0;
3086 /* FIXME this function is far too slow, for no good reason. */
3088 _gtk_text_line_char_has_tag (GtkTextLine *line,
3093 GtkTextLineSegment *toggle_seg;
3095 g_return_val_if_fail (line != NULL, FALSE);
3098 * Check for toggles for the tag in the line but before
3099 * the char. If there is one, its type indicates whether or
3100 * not the character is tagged.
3103 toggle_seg = find_toggle_segment_before_char (line, char_in_line, tag);
3105 if (toggle_seg != NULL)
3106 return (toggle_seg->type == >k_text_toggle_on_type);
3108 return find_toggle_outside_current_line (line, tree, tag);
3112 _gtk_text_line_byte_has_tag (GtkTextLine *line,
3117 GtkTextLineSegment *toggle_seg;
3119 g_return_val_if_fail (line != NULL, FALSE);
3122 * Check for toggles for the tag in the line but before
3123 * the char. If there is one, its type indicates whether or
3124 * not the character is tagged.
3127 toggle_seg = find_toggle_segment_before_byte (line, byte_in_line, tag);
3129 if (toggle_seg != NULL)
3130 return (toggle_seg->type == >k_text_toggle_on_type);
3132 return find_toggle_outside_current_line (line, tree, tag);
3136 _gtk_text_line_is_last (GtkTextLine *line,
3139 return line == get_last_line (tree);
3143 _gtk_text_line_next (GtkTextLine *line)
3145 GtkTextBTreeNode *node;
3147 if (line->next != NULL)
3152 * This was the last line associated with the particular parent
3153 * GtkTextBTreeNode. Search up the tree for the next GtkTextBTreeNode,
3154 * then search down from that GtkTextBTreeNode to find the first
3158 node = line->parent;
3159 while (node != NULL && node->next == NULL)
3160 node = node->parent;
3166 while (node->level > 0)
3168 node = node->children.node;
3171 g_assert (node->children.line != line);
3173 return node->children.line;
3178 _gtk_text_line_previous (GtkTextLine *line)
3180 GtkTextBTreeNode *node;
3181 GtkTextBTreeNode *node2;
3185 * Find the line under this GtkTextBTreeNode just before the starting line.
3187 prev = line->parent->children.line; /* First line at leaf */
3188 while (prev != line)
3190 if (prev->next == line)
3196 g_error ("gtk_text_btree_previous_line ran out of lines");
3200 * This was the first line associated with the particular parent
3201 * GtkTextBTreeNode. Search up the tree for the previous GtkTextBTreeNode,
3202 * then search down from that GtkTextBTreeNode to find its last line.
3204 for (node = line->parent; ; node = node->parent)
3206 if (node == NULL || node->parent == NULL)
3208 else if (node != node->parent->children.node)
3212 for (node2 = node->parent->children.node; ;
3213 node2 = node2->children.node)
3215 while (node2->next != node)
3216 node2 = node2->next;
3218 if (node2->level == 0)
3224 for (prev = node2->children.line ; ; prev = prev->next)
3226 if (prev->next == NULL)
3230 g_assert_not_reached ();
3235 _gtk_text_line_add_data (GtkTextLine *line,
3236 GtkTextLineData *data)
3238 g_return_if_fail (line != NULL);
3239 g_return_if_fail (data != NULL);
3240 g_return_if_fail (data->view_id != NULL);
3244 data->next = line->views;
3254 _gtk_text_line_remove_data (GtkTextLine *line,
3257 GtkTextLineData *prev;
3258 GtkTextLineData *iter;
3260 g_return_val_if_fail (line != NULL, NULL);
3261 g_return_val_if_fail (view_id != NULL, NULL);
3265 while (iter != NULL)
3267 if (iter->view_id == view_id)
3276 prev->next = iter->next;
3278 line->views = iter->next;
3287 _gtk_text_line_get_data (GtkTextLine *line,
3290 GtkTextLineData *iter;
3292 g_return_val_if_fail (line != NULL, NULL);
3293 g_return_val_if_fail (view_id != NULL, NULL);
3296 while (iter != NULL)
3298 if (iter->view_id == view_id)
3307 _gtk_text_line_invalidate_wrap (GtkTextLine *line,
3308 GtkTextLineData *ld)
3310 /* For now this is totally unoptimized. FIXME?
3312 We could probably optimize the case where the width removed
3313 is less than the max width for the parent node,
3314 and the case where the height is unchanged when we re-wrap.
3317 g_return_if_fail (ld != NULL);
3320 gtk_text_btree_node_invalidate_upward (line->parent, ld->view_id);
3324 _gtk_text_line_char_count (GtkTextLine *line)
3326 GtkTextLineSegment *seg;
3330 seg = line->segments;
3333 size += seg->char_count;
3340 _gtk_text_line_byte_count (GtkTextLine *line)
3342 GtkTextLineSegment *seg;
3346 seg = line->segments;
3349 size += seg->byte_count;
3357 _gtk_text_line_char_index (GtkTextLine *target_line)
3359 GSList *node_stack = NULL;
3360 GtkTextBTreeNode *iter;
3364 /* Push all our parent nodes onto a stack */
3365 iter = target_line->parent;
3367 g_assert (iter != NULL);
3369 while (iter != NULL)
3371 node_stack = g_slist_prepend (node_stack, iter);
3373 iter = iter->parent;
3376 /* Check that we have the root node on top of the stack. */
3377 g_assert (node_stack != NULL &&
3378 node_stack->data != NULL &&
3379 ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3381 /* Add up chars in all nodes before the nodes in our stack.
3385 iter = node_stack->data;
3386 while (iter != NULL)
3388 GtkTextBTreeNode *child_iter;
3389 GtkTextBTreeNode *next_node;
3391 next_node = node_stack->next ?
3392 node_stack->next->data : NULL;
3393 node_stack = g_slist_remove (node_stack, node_stack->data);
3395 if (iter->level == 0)
3397 /* stack should be empty when we're on the last node */
3398 g_assert (node_stack == NULL);
3399 break; /* Our children are now lines */
3402 g_assert (next_node != NULL);
3403 g_assert (iter != NULL);
3404 g_assert (next_node->parent == iter);
3406 /* Add up chars before us in the tree */
3407 child_iter = iter->children.node;
3408 while (child_iter != next_node)
3410 g_assert (child_iter != NULL);
3412 num_chars += child_iter->num_chars;
3414 child_iter = child_iter->next;
3420 g_assert (iter != NULL);
3421 g_assert (iter == target_line->parent);
3423 /* Since we don't store char counts in lines, only in segments, we
3424 have to iterate over the lines adding up segment char counts
3425 until we find our line. */
3426 line = iter->children.line;
3427 while (line != target_line)
3429 g_assert (line != NULL);
3431 num_chars += _gtk_text_line_char_count (line);
3436 g_assert (line == target_line);
3442 _gtk_text_line_byte_to_segment (GtkTextLine *line,
3446 GtkTextLineSegment *seg;
3449 g_return_val_if_fail (line != NULL, NULL);
3451 offset = byte_offset;
3452 seg = line->segments;
3454 while (offset >= seg->byte_count)
3456 g_assert (seg != NULL); /* means an invalid byte index */
3457 offset -= seg->byte_count;
3462 *seg_offset = offset;
3468 _gtk_text_line_char_to_segment (GtkTextLine *line,
3472 GtkTextLineSegment *seg;
3475 g_return_val_if_fail (line != NULL, NULL);
3477 offset = char_offset;
3478 seg = line->segments;
3480 while (offset >= seg->char_count)
3482 g_assert (seg != NULL); /* means an invalid char index */
3483 offset -= seg->char_count;
3488 *seg_offset = offset;
3494 _gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3498 GtkTextLineSegment *seg;
3501 g_return_val_if_fail (line != NULL, NULL);
3503 offset = byte_offset;
3504 seg = line->segments;
3506 while (offset > 0 && offset >= seg->byte_count)
3508 g_assert (seg != NULL); /* means an invalid byte index */
3509 offset -= seg->byte_count;
3514 *seg_offset = offset;
3520 _gtk_text_line_char_to_any_segment (GtkTextLine *line,
3524 GtkTextLineSegment *seg;
3527 g_return_val_if_fail (line != NULL, NULL);
3529 offset = char_offset;
3530 seg = line->segments;
3532 while (offset > 0 && offset >= seg->char_count)
3534 g_assert (seg != NULL); /* means an invalid byte index */
3535 offset -= seg->char_count;
3540 *seg_offset = offset;
3546 _gtk_text_line_byte_to_char (GtkTextLine *line,
3550 GtkTextLineSegment *seg;
3552 g_return_val_if_fail (line != NULL, 0);
3553 g_return_val_if_fail (byte_offset >= 0, 0);
3556 seg = line->segments;
3557 while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3558 the next segment) */
3560 g_assert (seg != NULL); /* our byte_index was bogus if this happens */
3562 byte_offset -= seg->byte_count;
3563 char_offset += seg->char_count;
3568 g_assert (seg != NULL);
3570 /* Now byte_offset is the offset into the current segment,
3571 and char_offset is the start of the current segment.
3572 Optimize the case where no chars use > 1 byte */
3573 if (seg->byte_count == seg->char_count)
3574 return char_offset + byte_offset;
3577 if (seg->type == >k_text_char_type)
3578 return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3581 g_assert (seg->char_count == 1);
3582 g_assert (byte_offset == 0);
3590 _gtk_text_line_char_to_byte (GtkTextLine *line,
3593 g_warning ("FIXME not implemented");
3598 /* FIXME sync with char_locate (or figure out a clean
3599 way to merge the two functions) */
3601 _gtk_text_line_byte_locate (GtkTextLine *line,
3603 GtkTextLineSegment **segment,
3604 GtkTextLineSegment **any_segment,
3605 gint *seg_byte_offset,
3606 gint *line_byte_offset)
3608 GtkTextLineSegment *seg;
3609 GtkTextLineSegment *after_prev_indexable;
3610 GtkTextLineSegment *after_last_indexable;
3611 GtkTextLineSegment *last_indexable;
3615 g_return_val_if_fail (line != NULL, FALSE);
3616 g_return_val_if_fail (byte_offset >= 0, FALSE);
3619 *any_segment = NULL;
3622 offset = byte_offset;
3624 last_indexable = NULL;
3625 after_last_indexable = line->segments;
3626 after_prev_indexable = line->segments;
3627 seg = line->segments;
3629 /* The loop ends when we're inside a segment;
3630 last_indexable refers to the last segment
3631 we passed entirely. */
3632 while (seg && offset >= seg->byte_count)
3634 if (seg->char_count > 0)
3636 offset -= seg->byte_count;
3637 bytes_in_line += seg->byte_count;
3638 last_indexable = seg;
3639 after_prev_indexable = after_last_indexable;
3640 after_last_indexable = last_indexable->next;
3648 /* We went off the end of the line */
3650 g_warning ("%s: byte index off the end of the line", G_STRLOC);
3657 if (after_last_indexable != NULL)
3658 *any_segment = after_last_indexable;
3660 *any_segment = *segment;
3663 /* Override any_segment if we're in the middle of a segment. */
3665 *any_segment = *segment;
3667 *seg_byte_offset = offset;
3669 g_assert (*segment != NULL);
3670 g_assert (*any_segment != NULL);
3671 g_assert (*seg_byte_offset < (*segment)->byte_count);
3673 *line_byte_offset = bytes_in_line + *seg_byte_offset;
3678 /* FIXME sync with byte_locate (or figure out a clean
3679 way to merge the two functions) */
3681 _gtk_text_line_char_locate (GtkTextLine *line,
3683 GtkTextLineSegment **segment,
3684 GtkTextLineSegment **any_segment,
3685 gint *seg_char_offset,
3686 gint *line_char_offset)
3688 GtkTextLineSegment *seg;
3689 GtkTextLineSegment *after_prev_indexable;
3690 GtkTextLineSegment *after_last_indexable;
3691 GtkTextLineSegment *last_indexable;
3695 g_return_val_if_fail (line != NULL, FALSE);
3696 g_return_val_if_fail (char_offset >= 0, FALSE);
3699 *any_segment = NULL;
3702 offset = char_offset;
3704 last_indexable = NULL;
3705 after_last_indexable = line->segments;
3706 after_prev_indexable = line->segments;
3707 seg = line->segments;
3709 /* The loop ends when we're inside a segment;
3710 last_indexable refers to the last segment
3711 we passed entirely. */
3712 while (seg && offset >= seg->char_count)
3714 if (seg->char_count > 0)
3716 offset -= seg->char_count;
3717 chars_in_line += seg->char_count;
3718 last_indexable = seg;
3719 after_prev_indexable = after_last_indexable;
3720 after_last_indexable = last_indexable->next;
3728 /* end of the line */
3730 g_warning ("%s: char offset off the end of the line", G_STRLOC);
3737 if (after_last_indexable != NULL)
3738 *any_segment = after_last_indexable;
3740 *any_segment = *segment;
3743 /* Override any_segment if we're in the middle of a segment. */
3745 *any_segment = *segment;
3747 *seg_char_offset = offset;
3749 g_assert (*segment != NULL);
3750 g_assert (*any_segment != NULL);
3751 g_assert (*seg_char_offset < (*segment)->char_count);
3753 *line_char_offset = chars_in_line + *seg_char_offset;
3759 _gtk_text_line_byte_to_char_offsets (GtkTextLine *line,
3761 gint *line_char_offset,
3762 gint *seg_char_offset)
3764 GtkTextLineSegment *seg;
3767 g_return_if_fail (line != NULL);
3768 g_return_if_fail (byte_offset >= 0);
3770 *line_char_offset = 0;
3772 offset = byte_offset;
3773 seg = line->segments;
3775 while (offset >= seg->byte_count)
3777 offset -= seg->byte_count;
3778 *line_char_offset += seg->char_count;
3780 g_assert (seg != NULL); /* means an invalid char offset */
3783 g_assert (seg->char_count > 0); /* indexable. */
3785 /* offset is now the number of bytes into the current segment we
3786 * want to go. Count chars into the current segment.
3789 if (seg->type == >k_text_char_type)
3791 *seg_char_offset = g_utf8_strlen (seg->body.chars, offset);
3793 g_assert (*seg_char_offset < seg->char_count);
3795 *line_char_offset += *seg_char_offset;
3799 g_assert (offset == 0);
3800 *seg_char_offset = 0;
3805 _gtk_text_line_char_to_byte_offsets (GtkTextLine *line,
3807 gint *line_byte_offset,
3808 gint *seg_byte_offset)
3810 GtkTextLineSegment *seg;
3813 g_return_if_fail (line != NULL);
3814 g_return_if_fail (char_offset >= 0);
3816 *line_byte_offset = 0;
3818 offset = char_offset;
3819 seg = line->segments;
3821 while (offset >= seg->char_count)
3823 offset -= seg->char_count;
3824 *line_byte_offset += seg->byte_count;
3826 g_assert (seg != NULL); /* means an invalid char offset */
3829 g_assert (seg->char_count > 0); /* indexable. */
3831 /* offset is now the number of chars into the current segment we
3832 want to go. Count bytes into the current segment. */
3834 if (seg->type == >k_text_char_type)
3836 *seg_byte_offset = 0;
3840 const char * start = seg->body.chars + *seg_byte_offset;
3842 bytes = g_utf8_next_char (start) - start;
3843 *seg_byte_offset += bytes;
3847 g_assert (*seg_byte_offset < seg->byte_count);
3849 *line_byte_offset += *seg_byte_offset;
3853 g_assert (offset == 0);
3854 *seg_byte_offset = 0;
3859 node_compare (GtkTextBTreeNode *lhs,
3860 GtkTextBTreeNode *rhs)
3862 GtkTextBTreeNode *iter;
3863 GtkTextBTreeNode *node;
3864 GtkTextBTreeNode *common_parent;
3865 GtkTextBTreeNode *parent_of_lower;
3866 GtkTextBTreeNode *parent_of_higher;
3867 gboolean lhs_is_lower;
3868 GtkTextBTreeNode *lower;
3869 GtkTextBTreeNode *higher;
3871 /* This function assumes that lhs and rhs are not underneath each
3878 if (lhs->level < rhs->level)
3880 lhs_is_lower = TRUE;
3886 lhs_is_lower = FALSE;
3891 /* Algorithm: find common parent of lhs/rhs. Save the child nodes
3892 * of the common parent we used to reach the common parent; the
3893 * ordering of these child nodes in the child list is the ordering
3897 /* Get on the same level (may be on same level already) */
3899 while (node->level < higher->level)
3900 node = node->parent;
3902 g_assert (node->level == higher->level);
3904 g_assert (node != higher); /* Happens if lower is underneath higher */
3906 /* Go up until we have two children with a common parent.
3908 parent_of_lower = node;
3909 parent_of_higher = higher;
3911 while (parent_of_lower->parent != parent_of_higher->parent)
3913 parent_of_lower = parent_of_lower->parent;
3914 parent_of_higher = parent_of_higher->parent;
3917 g_assert (parent_of_lower->parent == parent_of_higher->parent);
3919 common_parent = parent_of_lower->parent;
3921 g_assert (common_parent != NULL);
3923 /* See which is first in the list of common_parent's children */
3924 iter = common_parent->children.node;
3925 while (iter != NULL)
3927 if (iter == parent_of_higher)
3929 /* higher is less than lower */
3932 return 1; /* lhs > rhs */
3936 else if (iter == parent_of_lower)
3938 /* lower is less than higher */
3941 return -1; /* lhs < rhs */
3949 g_assert_not_reached ();
3953 /* remember that tag == NULL means "any tag" */
3955 _gtk_text_line_next_could_contain_tag (GtkTextLine *line,
3959 GtkTextBTreeNode *node;
3960 GtkTextTagInfo *info;
3961 gboolean below_tag_root;
3963 g_return_val_if_fail (line != NULL, NULL);
3965 if (gtk_debug_flags & GTK_DEBUG_TEXT)
3966 _gtk_text_btree_check (tree);
3970 /* Right now we can only offer linear-search if the user wants
3971 * to know about any tag toggle at all.
3973 return _gtk_text_line_next (line);
3976 /* Our tag summaries only have node precision, not line
3977 precision. This means that if any line under a node could contain a
3978 tag, then any of the others could also contain a tag.
3980 In the future we could have some mechanism to keep track of how
3981 many toggles we've found under a node so far, since we have a
3982 count of toggles under the node. But for now I'm going with KISS.
3985 /* return same-node line, if any. */
3989 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3993 if (info->tag_root == NULL)
3996 if (info->tag_root == line->parent)
3997 return NULL; /* we were at the last line under the tag root */
3999 /* We need to go up out of this node, and on to the next one with
4000 toggles for the target tag. If we're below the tag root, we need to
4001 find the next node below the tag root that has tag summaries. If
4002 we're not below the tag root, we need to see if the tag root is
4003 after us in the tree, and if so, return the first line underneath
4006 node = line->parent;
4007 below_tag_root = FALSE;
4008 while (node != NULL)
4010 if (node == info->tag_root)
4012 below_tag_root = TRUE;
4016 node = node->parent;
4021 node = line->parent;
4022 while (node != info->tag_root)
4024 if (node->next == NULL)
4025 node = node->parent;
4030 if (gtk_text_btree_node_has_tag (node, tag))
4040 ordering = node_compare (line->parent, info->tag_root);
4044 /* Tag root is ahead of us, so search there. */
4045 node = info->tag_root;
4050 /* Tag root is after us, so no more lines that
4051 * could contain the tag.
4056 g_assert_not_reached ();
4061 g_assert (node != NULL);
4063 /* We have to find the first sub-node of this node that contains
4067 while (node->level > 0)
4069 g_assert (node != NULL); /* If this fails, it likely means an
4070 incorrect tag summary led us on a
4071 wild goose chase down this branch of
4073 node = node->children.node;
4074 while (node != NULL)
4076 if (gtk_text_btree_node_has_tag (node, tag))
4082 g_assert (node != NULL);
4083 g_assert (node->level == 0);
4085 return node->children.line;
4089 prev_line_under_node (GtkTextBTreeNode *node,
4094 prev = node->children.line;
4100 while (prev->next != line)
4110 _gtk_text_line_previous_could_contain_tag (GtkTextLine *line,
4114 GtkTextBTreeNode *node;
4115 GtkTextBTreeNode *found_node = NULL;
4116 GtkTextTagInfo *info;
4117 gboolean below_tag_root;
4119 GtkTextBTreeNode *line_ancestor;
4120 GtkTextBTreeNode *line_ancestor_parent;
4122 /* See next_could_contain_tag () for more extensive comments
4123 * on what's going on here.
4126 g_return_val_if_fail (line != NULL, NULL);
4128 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4129 _gtk_text_btree_check (tree);
4133 /* Right now we can only offer linear-search if the user wants
4134 * to know about any tag toggle at all.
4136 return _gtk_text_line_previous (line);
4139 /* Return same-node line, if any. */
4140 prev = prev_line_under_node (line->parent, line);
4144 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4148 if (info->tag_root == NULL)
4151 if (info->tag_root == line->parent)
4152 return NULL; /* we were at the first line under the tag root */
4154 /* Are we below the tag root */
4155 node = line->parent;
4156 below_tag_root = FALSE;
4157 while (node != NULL)
4159 if (node == info->tag_root)
4161 below_tag_root = TRUE;
4165 node = node->parent;
4170 /* Look for a previous node under this tag root that has our
4174 /* this assertion holds because line->parent is not the
4175 * tag root, we are below the tag root, and the tag
4178 g_assert (line->parent->parent != NULL);
4180 line_ancestor = line->parent;
4181 line_ancestor_parent = line->parent->parent;
4183 node = line_ancestor_parent->children.node;
4184 while (node != line_ancestor &&
4185 line_ancestor != info->tag_root)
4187 GSList *child_nodes = NULL;
4190 /* Create reverse-order list of nodes before
4193 while (node != line_ancestor
4196 child_nodes = g_slist_prepend (child_nodes, node);
4201 /* Try to find a node with our tag on it in the list */
4205 GtkTextBTreeNode *this_node = tmp->data;
4207 g_assert (this_node != line_ancestor);
4209 if (gtk_text_btree_node_has_tag (this_node, tag))
4211 found_node = this_node;
4212 g_slist_free (child_nodes);
4216 tmp = g_slist_next (tmp);
4219 g_slist_free (child_nodes);
4221 /* Didn't find anything on this level; go up one level. */
4222 line_ancestor = line_ancestor_parent;
4223 line_ancestor_parent = line_ancestor->parent;
4225 node = line_ancestor_parent->children.node;
4235 ordering = node_compare (line->parent, info->tag_root);
4239 /* Tag root is ahead of us, so no more lines
4246 /* Tag root is after us, so grab last tagged
4247 * line underneath the tag root.
4249 found_node = info->tag_root;
4253 g_assert_not_reached ();
4258 g_assert (found_node != NULL);
4260 /* We have to find the last sub-node of this node that contains
4265 while (node->level > 0)
4267 GSList *child_nodes = NULL;
4269 g_assert (node != NULL); /* If this fails, it likely means an
4270 incorrect tag summary led us on a
4271 wild goose chase down this branch of
4274 node = node->children.node;
4275 while (node != NULL)
4277 child_nodes = g_slist_prepend (child_nodes, node);
4281 node = NULL; /* detect failure to find a child node. */
4284 while (iter != NULL)
4286 if (gtk_text_btree_node_has_tag (iter->data, tag))
4288 /* recurse into this node. */
4293 iter = g_slist_next (iter);
4296 g_slist_free (child_nodes);
4298 g_assert (node != NULL);
4301 g_assert (node != NULL);
4302 g_assert (node->level == 0);
4304 /* this assertion is correct, but slow. */
4305 /* g_assert (node_compare (node, line->parent) < 0); */
4307 /* Return last line in this node. */
4309 prev = node->children.line;
4317 * Non-public function implementations
4321 summary_list_destroy (Summary *summary)
4324 while (summary != NULL)
4326 next = summary->next;
4327 summary_destroy (summary);
4333 get_last_line (GtkTextBTree *tree)
4335 if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
4341 n_lines = _gtk_text_btree_line_count (tree);
4343 g_assert (n_lines >= 1); /* num_lines doesn't return bogus last line. */
4345 line = _gtk_text_btree_get_line (tree, n_lines, &real_line);
4347 tree->end_iter_line_stamp = tree->chars_changed_stamp;
4348 tree->end_iter_line = line;
4351 return tree->end_iter_line;
4359 gtk_text_line_new (void)
4363 line = g_new0(GtkTextLine, 1);
4369 gtk_text_line_destroy (GtkTextBTree *tree, GtkTextLine *line)
4371 GtkTextLineData *ld;
4372 GtkTextLineData *next;
4374 g_return_if_fail (line != NULL);
4381 view = gtk_text_btree_get_view (tree, ld->view_id);
4383 g_assert (view != NULL);
4386 gtk_text_layout_free_line_data (view->layout, line, ld);
4395 gtk_text_line_set_parent (GtkTextLine *line,
4396 GtkTextBTreeNode *node)
4398 if (line->parent == node)
4400 line->parent = node;
4401 gtk_text_btree_node_invalidate_upward (node, NULL);
4405 cleanup_line (GtkTextLine *line)
4407 GtkTextLineSegment *seg, **prev_p;
4411 * Make a pass over all of the segments in the line, giving each
4412 * a chance to clean itself up. This could potentially change
4413 * the structure of the line, e.g. by merging two segments
4414 * together or having two segments cancel themselves; if so,
4415 * then repeat the whole process again, since the first structure
4416 * change might make other structure changes possible. Repeat
4417 * until eventually there are no changes.
4424 for (prev_p = &line->segments, seg = *prev_p;
4426 prev_p = &(*prev_p)->next, seg = *prev_p)
4428 if (seg->type->cleanupFunc != NULL)
4430 *prev_p = (*seg->type->cleanupFunc)(seg, line);
4443 node_data_new (gpointer view_id)
4447 nd = g_new (NodeData, 1);
4449 nd->view_id = view_id;
4459 node_data_destroy (NodeData *nd)
4465 node_data_list_destroy (NodeData *nd)
4471 while (iter != NULL)
4474 node_data_destroy (iter);
4480 node_data_find (NodeData *nd, gpointer view_id)
4484 if (nd->view_id == view_id)
4492 summary_destroy (Summary *summary)
4494 /* Fill with error-triggering garbage */
4495 summary->info = (void*)0x1;
4496 summary->toggle_count = 567;
4497 summary->next = (void*)0x1;
4501 static GtkTextBTreeNode*
4502 gtk_text_btree_node_new (void)
4504 GtkTextBTreeNode *node;
4506 node = g_new (GtkTextBTreeNode, 1);
4508 node->node_data = NULL;
4514 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
4515 GtkTextTagInfo *info,
4520 summary = node->summary;
4521 while (summary != NULL)
4523 if (summary->info == info)
4525 summary->toggle_count += adjust;
4529 summary = summary->next;
4532 if (summary == NULL)
4534 /* didn't find a summary for our tag. */
4535 g_return_if_fail (adjust > 0);
4536 summary = g_new (Summary, 1);
4537 summary->info = info;
4538 summary->toggle_count = adjust;
4539 summary->next = node->summary;
4540 node->summary = summary;
4544 /* Note that the tag root and above do not have summaries
4545 for the tag; only nodes below the tag root have
4548 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4552 summary = node->summary;
4553 while (summary != NULL)
4556 summary->info->tag == tag)
4559 summary = summary->next;
4565 /* Add node and all children to the damage region. */
4567 gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node)
4571 nd = node->node_data;
4578 if (node->level == 0)
4582 line = node->children.line;
4583 while (line != NULL)
4585 GtkTextLineData *ld;
4599 GtkTextBTreeNode *child;
4601 child = node->children.node;
4603 while (child != NULL)
4605 gtk_text_btree_node_invalidate_downward (child);
4607 child = child->next;
4613 gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node, gpointer view_id)
4615 GtkTextBTreeNode *iter;
4618 while (iter != NULL)
4624 nd = node_data_find (iter->node_data, view_id);
4626 if (nd == NULL || !nd->valid)
4627 break; /* Once a node is invalid, we know its parents are as well. */
4633 gboolean should_continue = FALSE;
4635 nd = iter->node_data;
4640 should_continue = TRUE;
4647 if (!should_continue)
4648 break; /* This node was totally invalidated, so are its
4652 iter = iter->parent;
4658 * _gtk_text_btree_is_valid:
4659 * @tree: a #GtkTextBTree
4660 * @view_id: ID for the view
4662 * Check to see if the entire #GtkTextBTree is valid or not for
4665 * Return value: %TRUE if the entire #GtkTextBTree is valid
4668 _gtk_text_btree_is_valid (GtkTextBTree *tree,
4672 g_return_val_if_fail (tree != NULL, FALSE);
4674 nd = node_data_find (tree->root_node->node_data, view_id);
4675 return (nd && nd->valid);
4678 typedef struct _ValidateState ValidateState;
4680 struct _ValidateState
4682 gint remaining_pixels;
4683 gboolean in_validation;
4690 gtk_text_btree_node_validate (BTreeView *view,
4691 GtkTextBTreeNode *node,
4693 ValidateState *state)
4695 gint node_valid = TRUE;
4696 gint node_width = 0;
4697 gint node_height = 0;
4699 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4700 g_return_if_fail (!nd->valid);
4702 if (node->level == 0)
4704 GtkTextLine *line = node->children.line;
4705 GtkTextLineData *ld;
4707 /* Iterate over leading valid lines */
4708 while (line != NULL)
4710 ld = _gtk_text_line_get_data (line, view_id);
4712 if (!ld || !ld->valid)
4714 else if (state->in_validation)
4716 state->in_validation = FALSE;
4721 state->y += ld->height;
4722 node_width = MAX (ld->width, node_width);
4723 node_height += ld->height;
4729 state->in_validation = TRUE;
4731 /* Iterate over invalid lines */
4732 while (line != NULL)
4734 ld = _gtk_text_line_get_data (line, view_id);
4736 if (ld && ld->valid)
4741 state->old_height += ld->height;
4742 ld = gtk_text_layout_wrap (view->layout, line, ld);
4743 state->new_height += ld->height;
4745 node_width = MAX (ld->width, node_width);
4746 node_height += ld->height;
4748 state->remaining_pixels -= ld->height;
4749 if (state->remaining_pixels <= 0)
4759 /* Iterate over the remaining lines */
4760 while (line != NULL)
4762 ld = _gtk_text_line_get_data (line, view_id);
4763 state->in_validation = FALSE;
4765 if (!ld || !ld->valid)
4770 node_width = MAX (ld->width, node_width);
4771 node_height += ld->height;
4779 GtkTextBTreeNode *child;
4782 child = node->children.node;
4784 /* Iterate over leading valid nodes */
4787 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4789 if (!child_nd->valid)
4791 else if (state->in_validation)
4793 state->in_validation = FALSE;
4798 state->y += child_nd->height;
4799 node_width = MAX (node_width, child_nd->width);
4800 node_height += child_nd->height;
4803 child = child->next;
4806 /* Iterate over invalid nodes */
4809 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4811 if (child_nd->valid)
4815 gtk_text_btree_node_validate (view, child, view_id, state);
4817 if (!child_nd->valid)
4819 node_width = MAX (node_width, child_nd->width);
4820 node_height += child_nd->height;
4822 if (!state->in_validation || state->remaining_pixels <= 0)
4824 child = child->next;
4829 child = child->next;
4832 /* Iterate over the remaining lines */
4835 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4836 state->in_validation = FALSE;
4838 if (!child_nd->valid)
4841 node_width = MAX (child_nd->width, node_width);
4842 node_height += child_nd->height;
4844 child = child->next;
4848 nd->width = node_width;
4849 nd->height = node_height;
4850 nd->valid = node_valid;
4854 * _gtk_text_btree_validate:
4855 * @tree: a #GtkTextBTree
4857 * @max_pixels: the maximum number of pixels to validate. (No more
4858 * than one paragraph beyond this limit will be validated)
4859 * @y: location to store starting y coordinate of validated region
4860 * @old_height: location to store old height of validated region
4861 * @new_height: location to store new height of validated region
4863 * Validate a single contiguous invalid region of a #GtkTextBTree for
4866 * Return value: %TRUE if a region has been validated, %FALSE if the
4867 * entire tree was already valid.
4870 _gtk_text_btree_validate (GtkTextBTree *tree,
4879 g_return_val_if_fail (tree != NULL, FALSE);
4881 view = gtk_text_btree_get_view (tree, view_id);
4882 g_return_val_if_fail (view != NULL, FALSE);
4884 if (!_gtk_text_btree_is_valid (tree, view_id))
4886 ValidateState state;
4888 state.remaining_pixels = max_pixels;
4889 state.in_validation = FALSE;
4891 state.old_height = 0;
4892 state.new_height = 0;
4894 gtk_text_btree_node_validate (view,
4901 *old_height = state.old_height;
4903 *new_height = state.new_height;
4905 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4906 _gtk_text_btree_check (tree);
4915 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
4919 gboolean *valid_out)
4923 gboolean valid = TRUE;
4925 if (node->level == 0)
4927 GtkTextLine *line = node->children.line;
4929 while (line != NULL)
4931 GtkTextLineData *ld = _gtk_text_line_get_data (line, view_id);
4933 if (!ld || !ld->valid)
4938 width = MAX (ld->width, width);
4939 height += ld->height;
4947 GtkTextBTreeNode *child = node->children.node;
4951 NodeData *child_nd = node_data_find (child->node_data, view_id);
4953 if (!child_nd || !child_nd->valid)
4958 width = MAX (child_nd->width, width);
4959 height += child_nd->height;
4962 child = child->next;
4967 *height_out = height;
4972 /* Recompute the validity and size of the view data for a given
4973 * view at this node from the immediate children of the node
4976 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
4979 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4984 gtk_text_btree_node_compute_view_aggregates (node, view_id,
4985 &width, &height, &valid);
4987 nd->height = height;
4994 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
4999 gtk_text_btree_node_check_valid (node, view_id);
5000 node = node->parent;
5005 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
5008 if (node->level == 0)
5010 return gtk_text_btree_node_check_valid (node, view_id);
5014 GtkTextBTreeNode *child = node->children.node;
5016 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5024 NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
5026 if (!child_nd->valid)
5028 nd->width = MAX (child_nd->width, nd->width);
5029 nd->height += child_nd->height;
5031 child = child->next;
5040 * _gtk_text_btree_validate_line:
5041 * @tree: a #GtkTextBTree
5042 * @line: line to validate
5043 * @view_id: view ID for the view to validate
5045 * Revalidate a single line of the btree for the given view, propagate
5046 * results up through the entire tree.
5049 _gtk_text_btree_validate_line (GtkTextBTree *tree,
5053 GtkTextLineData *ld;
5056 g_return_if_fail (tree != NULL);
5057 g_return_if_fail (line != NULL);
5059 view = gtk_text_btree_get_view (tree, view_id);
5060 g_return_if_fail (view != NULL);
5062 ld = _gtk_text_line_get_data (line, view_id);
5063 if (!ld || !ld->valid)
5065 ld = gtk_text_layout_wrap (view->layout, line, ld);
5067 gtk_text_btree_node_check_valid_upward (line->parent, view_id);
5072 gtk_text_btree_node_remove_view (BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
5074 if (node->level == 0)
5078 line = node->children.line;
5079 while (line != NULL)
5081 GtkTextLineData *ld;
5083 ld = _gtk_text_line_remove_data (line, view_id);
5086 gtk_text_layout_free_line_data (view->layout, line, ld);
5093 GtkTextBTreeNode *child;
5095 child = node->children.node;
5097 while (child != NULL)
5100 gtk_text_btree_node_remove_view (view, child, view_id);
5102 child = child->next;
5106 gtk_text_btree_node_remove_data (node, view_id);
5110 gtk_text_btree_node_destroy (GtkTextBTree *tree, GtkTextBTreeNode *node)
5112 if (node->level == 0)
5115 GtkTextLineSegment *seg;
5117 while (node->children.line != NULL)
5119 line = node->children.line;
5120 node->children.line = line->next;
5121 while (line->segments != NULL)
5123 seg = line->segments;
5124 line->segments = seg->next;
5126 if (GTK_IS_TEXT_MARK_SEGMENT (seg))
5128 /* Set the mark as deleted */
5129 seg->body.mark.tree = NULL;
5130 seg->body.mark.line = NULL;
5133 (*seg->type->deleteFunc) (seg, line, 1);
5135 gtk_text_line_destroy (tree, line);
5140 GtkTextBTreeNode *childPtr;
5142 while (node->children.node != NULL)
5144 childPtr = node->children.node;
5145 node->children.node = childPtr->next;
5146 gtk_text_btree_node_destroy (tree, childPtr);
5150 gtk_text_btree_node_free_empty (tree, node);
5154 gtk_text_btree_node_free_empty (GtkTextBTree *tree,
5155 GtkTextBTreeNode *node)
5157 g_return_if_fail ((node->level > 0 && node->children.node == NULL) ||
5158 (node->level == 0 && node->children.line == NULL));
5160 summary_list_destroy (node->summary);
5161 node_data_list_destroy (node->node_data);
5166 gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node, gpointer view_id)
5170 nd = node->node_data;
5173 if (nd->view_id == view_id)
5181 nd = node_data_new (view_id);
5183 if (node->node_data)
5184 nd->next = node->node_data;
5186 node->node_data = nd;
5193 gtk_text_btree_node_remove_data (GtkTextBTreeNode *node, gpointer view_id)
5199 nd = node->node_data;
5202 if (nd->view_id == view_id)
5213 prev->next = nd->next;
5215 if (node->node_data == nd)
5216 node->node_data = nd->next;
5220 node_data_destroy (nd);
5224 gtk_text_btree_node_get_size (GtkTextBTreeNode *node, gpointer view_id,
5225 gint *width, gint *height)
5229 g_return_if_fail (width != NULL);
5230 g_return_if_fail (height != NULL);
5232 nd = gtk_text_btree_node_ensure_data (node, view_id);
5237 *height = nd->height;
5240 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5241 * here isn't quite right, since for a lot of operations we want to
5242 * know which children of the common parent correspond to the two nodes
5243 * (e.g., when computing the order of two iters)
5245 static GtkTextBTreeNode *
5246 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5247 GtkTextBTreeNode *node2)
5249 while (node1->level < node2->level)
5250 node1 = node1->parent;
5251 while (node2->level < node1->level)
5252 node2 = node2->parent;
5253 while (node1 != node2)
5255 node1 = node1->parent;
5256 node2 = node2->parent;
5267 gtk_text_btree_get_view (GtkTextBTree *tree, gpointer view_id)
5272 while (view != NULL)
5274 if (view->view_id == view_id)
5283 get_tree_bounds (GtkTextBTree *tree,
5287 _gtk_text_btree_get_iter_at_line_char (tree, start, 0, 0);
5288 _gtk_text_btree_get_end_iter (tree, end);
5292 tag_changed_cb (GtkTextTagTable *table,
5294 gboolean size_changed,
5299 /* We need to queue a relayout on all regions that are tagged with
5306 if (_gtk_text_btree_get_iter_at_first_toggle (tree, &start, tag))
5308 /* Must be a last toggle if there was a first one. */
5309 _gtk_text_btree_get_iter_at_last_toggle (tree, &end, tag);
5310 _gtk_text_btree_invalidate_region (tree,
5317 /* We only need to queue a redraw, not a relayout */
5322 while (view != NULL)
5326 _gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5327 gtk_text_layout_changed (view->layout, 0, height, height);
5335 tag_removed_cb (GtkTextTagTable *table,
5339 /* Remove the tag from the tree */
5344 get_tree_bounds (tree, &start, &end);
5346 _gtk_text_btree_tag (&start, &end, tag, FALSE);
5347 gtk_text_btree_remove_tag_info (tree, tag);
5351 /* Rebalance the out-of-whack node "node" */
5353 gtk_text_btree_rebalance (GtkTextBTree *tree,
5354 GtkTextBTreeNode *node)
5357 * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5358 * up through the tree one GtkTextBTreeNode at a time until the root
5359 * GtkTextBTreeNode has been processed.
5362 while (node != NULL)
5364 GtkTextBTreeNode *new_node, *child;
5369 * Check to see if the GtkTextBTreeNode has too many children. If it does,
5370 * then split off all but the first MIN_CHILDREN into a separate
5371 * GtkTextBTreeNode following the original one. Then repeat until the
5372 * GtkTextBTreeNode has a decent size.
5375 if (node->num_children > MAX_CHILDREN)
5380 * If the GtkTextBTreeNode being split is the root
5381 * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5385 if (node->parent == NULL)
5387 new_node = gtk_text_btree_node_new ();
5388 new_node->parent = NULL;
5389 new_node->next = NULL;
5390 new_node->summary = NULL;
5391 new_node->level = node->level + 1;
5392 new_node->children.node = node;
5393 recompute_node_counts (tree, new_node);
5394 tree->root_node = new_node;
5396 new_node = gtk_text_btree_node_new ();
5397 new_node->parent = node->parent;
5398 new_node->next = node->next;
5399 node->next = new_node;
5400 new_node->summary = NULL;
5401 new_node->level = node->level;
5402 new_node->num_children = node->num_children - MIN_CHILDREN;
5403 if (node->level == 0)
5405 for (i = MIN_CHILDREN-1,
5406 line = node->children.line;
5407 i > 0; i--, line = line->next)
5409 /* Empty loop body. */
5411 new_node->children.line = line->next;
5416 for (i = MIN_CHILDREN-1,
5417 child = node->children.node;
5418 i > 0; i--, child = child->next)
5420 /* Empty loop body. */
5422 new_node->children.node = child->next;
5425 recompute_node_counts (tree, node);
5426 node->parent->num_children++;
5428 if (node->num_children <= MAX_CHILDREN)
5430 recompute_node_counts (tree, node);
5436 while (node->num_children < MIN_CHILDREN)
5438 GtkTextBTreeNode *other;
5439 GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5440 GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5441 int total_children, first_children, i;
5444 * Too few children for this GtkTextBTreeNode. If this is the root then,
5445 * it's OK for it to have less than MIN_CHILDREN children
5446 * as long as it's got at least two. If it has only one
5447 * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5448 * the tree and use its child as the new root.
5451 if (node->parent == NULL)
5453 if ((node->num_children == 1) && (node->level > 0))
5455 tree->root_node = node->children.node;
5456 tree->root_node->parent = NULL;
5458 node->children.node = NULL;
5459 gtk_text_btree_node_free_empty (tree, node);
5465 * Not the root. Make sure that there are siblings to
5469 if (node->parent->num_children < 2)
5471 gtk_text_btree_rebalance (tree, node->parent);
5476 * Find a sibling neighbor to borrow from, and arrange for
5477 * node to be the earlier of the pair.
5480 if (node->next == NULL)
5482 for (other = node->parent->children.node;
5483 other->next != node;
5484 other = other->next)
5486 /* Empty loop body. */
5493 * We're going to either merge the two siblings together
5494 * into one GtkTextBTreeNode or redivide the children among them to
5495 * balance their loads. As preparation, join their two
5496 * child lists into a single list and remember the half-way
5497 * point in the list.
5500 total_children = node->num_children + other->num_children;
5501 first_children = total_children/2;
5502 if (node->children.node == NULL)
5504 node->children = other->children;
5505 other->children.node = NULL;
5506 other->children.line = NULL;
5508 if (node->level == 0)
5512 for (line = node->children.line, i = 1;
5514 line = line->next, i++)
5516 if (i == first_children)
5521 line->next = other->children.line;
5522 while (i <= first_children)
5531 GtkTextBTreeNode *child;
5533 for (child = node->children.node, i = 1;
5534 child->next != NULL;
5535 child = child->next, i++)
5537 if (i <= first_children)
5539 if (i == first_children)
5541 halfwaynode = child;
5545 child->next = other->children.node;
5546 while (i <= first_children)
5548 halfwaynode = child;
5549 child = child->next;
5555 * If the two siblings can simply be merged together, do it.
5558 if (total_children <= MAX_CHILDREN)
5560 recompute_node_counts (tree, node);
5561 node->next = other->next;
5562 node->parent->num_children--;
5564 other->children.node = NULL;
5565 other->children.line = NULL;
5566 gtk_text_btree_node_free_empty (tree, other);
5571 * The siblings can't be merged, so just divide their
5572 * children evenly between them.
5575 if (node->level == 0)
5577 other->children.line = halfwayline->next;
5578 halfwayline->next = NULL;
5582 other->children.node = halfwaynode->next;
5583 halfwaynode->next = NULL;
5586 recompute_node_counts (tree, node);
5587 recompute_node_counts (tree, other);
5590 node = node->parent;
5595 post_insert_fixup (GtkTextBTree *tree,
5597 gint line_count_delta,
5598 gint char_count_delta)
5601 GtkTextBTreeNode *node;
5604 * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5605 * point, then rebalance the tree if necessary.
5608 for (node = line->parent ; node != NULL;
5609 node = node->parent)
5611 node->num_lines += line_count_delta;
5612 node->num_chars += char_count_delta;
5614 node = line->parent;
5615 node->num_children += line_count_delta;
5617 if (node->num_children > MAX_CHILDREN)
5619 gtk_text_btree_rebalance (tree, node);
5622 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5623 _gtk_text_btree_check (tree);
5626 static GtkTextTagInfo*
5627 gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
5630 GtkTextTagInfo *info;
5634 list = tree->tag_infos;
5635 while (list != NULL)
5638 if (info->tag == tag)
5641 list = g_slist_next (list);
5647 static GtkTextTagInfo*
5648 gtk_text_btree_get_tag_info (GtkTextBTree *tree,
5651 GtkTextTagInfo *info;
5653 info = gtk_text_btree_get_existing_tag_info (tree, tag);
5657 /* didn't find it, create. */
5659 info = g_new (GtkTextTagInfo, 1);
5662 g_object_ref (G_OBJECT (tag));
5663 info->tag_root = NULL;
5664 info->toggle_count = 0;
5666 tree->tag_infos = g_slist_prepend (tree->tag_infos, info);
5673 gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
5676 GtkTextTagInfo *info;
5681 list = tree->tag_infos;
5682 while (list != NULL)
5685 if (info->tag == tag)
5689 prev->next = list->next;
5693 tree->tag_infos = list->next;
5696 g_slist_free (list);
5698 g_object_unref (G_OBJECT (info->tag));
5704 list = g_slist_next (list);
5707 g_assert_not_reached ();
5712 recompute_level_zero_counts (GtkTextBTreeNode *node)
5715 GtkTextLineSegment *seg;
5717 g_assert (node->level == 0);
5719 line = node->children.line;
5720 while (line != NULL)
5722 node->num_children++;
5725 if (line->parent != node)
5726 gtk_text_line_set_parent (line, node);
5728 seg = line->segments;
5732 node->num_chars += seg->char_count;
5734 if (((seg->type != >k_text_toggle_on_type)
5735 && (seg->type != >k_text_toggle_off_type))
5736 || !(seg->body.toggle.inNodeCounts))
5742 GtkTextTagInfo *info;
5744 info = seg->body.toggle.info;
5746 gtk_text_btree_node_adjust_toggle_count (node, info, 1);
5757 recompute_level_nonzero_counts (GtkTextBTreeNode *node)
5760 GtkTextBTreeNode *child;
5762 g_assert (node->level > 0);
5764 child = node->children.node;
5765 while (child != NULL)
5767 node->num_children += 1;
5768 node->num_lines += child->num_lines;
5769 node->num_chars += child->num_chars;
5771 if (child->parent != node)
5773 child->parent = node;
5774 gtk_text_btree_node_invalidate_upward (node, NULL);
5777 summary = child->summary;
5778 while (summary != NULL)
5780 gtk_text_btree_node_adjust_toggle_count (node,
5782 summary->toggle_count);
5784 summary = summary->next;
5787 child = child->next;
5792 *----------------------------------------------------------------------
5794 * recompute_node_counts --
5796 * This procedure is called to recompute all the counts in a GtkTextBTreeNode
5797 * (tags, child information, etc.) by scanning the information in
5798 * its descendants. This procedure is called during rebalancing
5799 * when a GtkTextBTreeNode's child structure has changed.
5805 * The tag counts for node are modified to reflect its current
5806 * child structure, as are its num_children, num_lines, num_chars fields.
5807 * Also, all of the childrens' parent fields are made to point
5810 *----------------------------------------------------------------------
5814 recompute_node_counts (GtkTextBTree *tree, GtkTextBTreeNode *node)
5817 Summary *summary, *summary2;
5820 * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
5821 * the existing Summary records (most of them will probably be reused).
5824 summary = node->summary;
5825 while (summary != NULL)
5827 summary->toggle_count = 0;
5828 summary = summary->next;
5831 node->num_children = 0;
5832 node->num_lines = 0;
5833 node->num_chars = 0;
5836 * Scan through the children, adding the childrens' tag counts into
5837 * the GtkTextBTreeNode's tag counts and adding new Summary structures if
5841 if (node->level == 0)
5842 recompute_level_zero_counts (node);
5844 recompute_level_nonzero_counts (node);
5849 gtk_text_btree_node_check_valid (node, view->view_id);
5854 * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
5855 * records that still have a zero count, or that have all the toggles.
5856 * The GtkTextBTreeNode with the children that account for all the tags toggles
5857 * have no summary information, and they become the tag_root for the tag.
5861 for (summary = node->summary; summary != NULL; )
5863 if (summary->toggle_count > 0 &&
5864 summary->toggle_count < summary->info->toggle_count)
5866 if (node->level == summary->info->tag_root->level)
5869 * The tag's root GtkTextBTreeNode split and some toggles left.
5870 * The tag root must move up a level.
5872 summary->info->tag_root = node->parent;
5875 summary = summary->next;
5878 if (summary->toggle_count == summary->info->toggle_count)
5881 * A GtkTextBTreeNode merge has collected all the toggles under
5882 * one GtkTextBTreeNode. Push the root down to this level.
5884 summary->info->tag_root = node;
5886 if (summary2 != NULL)
5888 summary2->next = summary->next;
5889 summary_destroy (summary);
5890 summary = summary2->next;
5894 node->summary = summary->next;
5895 summary_destroy (summary);
5896 summary = node->summary;
5902 _gtk_change_node_toggle_count (GtkTextBTreeNode *node,
5903 GtkTextTagInfo *info,
5904 gint delta) /* may be negative */
5906 Summary *summary, *prevPtr;
5907 GtkTextBTreeNode *node2Ptr;
5908 int rootLevel; /* Level of original tag root */
5910 info->toggle_count += delta;
5912 if (info->tag_root == (GtkTextBTreeNode *) NULL)
5914 info->tag_root = node;
5919 * Note the level of the existing root for the tag so we can detect
5920 * if it needs to be moved because of the toggle count change.
5923 rootLevel = info->tag_root->level;
5926 * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
5927 * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
5931 for ( ; node != info->tag_root; node = node->parent)
5934 * See if there's already an entry for this tag for this GtkTextBTreeNode. If so,
5935 * perhaps all we have to do is adjust its count.
5938 for (prevPtr = NULL, summary = node->summary;
5940 prevPtr = summary, summary = summary->next)
5942 if (summary->info == info)
5947 if (summary != NULL)
5949 summary->toggle_count += delta;
5950 if (summary->toggle_count > 0 &&
5951 summary->toggle_count < info->toggle_count)
5955 if (summary->toggle_count != 0)
5958 * Should never find a GtkTextBTreeNode with max toggle count at this
5959 * point (there shouldn't have been a summary entry in the
5963 g_error ("%s: bad toggle count (%d) max (%d)",
5964 G_STRLOC, summary->toggle_count, info->toggle_count);
5968 * Zero toggle count; must remove this tag from the list.
5971 if (prevPtr == NULL)
5973 node->summary = summary->next;
5977 prevPtr->next = summary->next;
5979 summary_destroy (summary);
5984 * This tag isn't currently in the summary information list.
5987 if (rootLevel == node->level)
5991 * The old tag root is at the same level in the tree as this
5992 * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode. Move the tag root up
5993 * a level, in the hopes that it will now cover this GtkTextBTreeNode
5994 * as well as the old root (if not, we'll move it up again
5995 * the next time through the loop). To push it up one level
5996 * we copy the original toggle count into the summary
5997 * information at the old root and change the root to its
5998 * parent GtkTextBTreeNode.
6001 GtkTextBTreeNode *rootnode = info->tag_root;
6002 summary = (Summary *) g_malloc (sizeof (Summary));
6003 summary->info = info;
6004 summary->toggle_count = info->toggle_count - delta;
6005 summary->next = rootnode->summary;
6006 rootnode->summary = summary;
6007 rootnode = rootnode->parent;
6008 rootLevel = rootnode->level;
6009 info->tag_root = rootnode;
6011 summary = (Summary *) g_malloc (sizeof (Summary));
6012 summary->info = info;
6013 summary->toggle_count = delta;
6014 summary->next = node->summary;
6015 node->summary = summary;
6020 * If we've decremented the toggle count, then it may be necessary
6021 * to push the tag root down one or more levels.
6028 if (info->toggle_count == 0)
6030 info->tag_root = (GtkTextBTreeNode *) NULL;
6033 node = info->tag_root;
6034 while (node->level > 0)
6037 * See if a single child GtkTextBTreeNode accounts for all of the tag's
6038 * toggles. If so, push the root down one level.
6041 for (node2Ptr = node->children.node;
6042 node2Ptr != (GtkTextBTreeNode *)NULL ;
6043 node2Ptr = node2Ptr->next)
6045 for (prevPtr = NULL, summary = node2Ptr->summary;
6047 prevPtr = summary, summary = summary->next)
6049 if (summary->info == info)
6054 if (summary == NULL)
6058 if (summary->toggle_count != info->toggle_count)
6061 * No GtkTextBTreeNode has all toggles, so the root is still valid.
6068 * This GtkTextBTreeNode has all the toggles, so push down the root.
6071 if (prevPtr == NULL)
6073 node2Ptr->summary = summary->next;
6077 prevPtr->next = summary->next;
6079 summary_destroy (summary);
6080 info->tag_root = node2Ptr;
6083 node = info->tag_root;
6088 *----------------------------------------------------------------------
6092 * This is a utility procedure used by _gtk_text_btree_get_tags. It
6093 * increments the count for a particular tag, adding a new
6094 * entry for that tag if there wasn't one previously.
6100 * The information at *tagInfoPtr may be modified, and the arrays
6101 * may be reallocated to make them larger.
6103 *----------------------------------------------------------------------
6107 inc_count (GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
6112 for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
6113 count > 0; tag_p++, count--)
6117 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
6123 * There isn't currently an entry for this tag, so we have to
6124 * make a new one. If the arrays are full, then enlarge the
6128 if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
6130 GtkTextTag **newTags;
6131 int *newCounts, newSize;
6133 newSize = 2*tagInfoPtr->arraySize;
6134 newTags = (GtkTextTag **) g_malloc ((unsigned)
6135 (newSize*sizeof (GtkTextTag *)));
6136 memcpy ((void *) newTags, (void *) tagInfoPtr->tags,
6137 tagInfoPtr->arraySize *sizeof (GtkTextTag *));
6138 g_free ((char *) tagInfoPtr->tags);
6139 tagInfoPtr->tags = newTags;
6140 newCounts = (int *) g_malloc ((unsigned) (newSize*sizeof (int)));
6141 memcpy ((void *) newCounts, (void *) tagInfoPtr->counts,
6142 tagInfoPtr->arraySize *sizeof (int));
6143 g_free ((char *) tagInfoPtr->counts);
6144 tagInfoPtr->counts = newCounts;
6145 tagInfoPtr->arraySize = newSize;
6148 tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
6149 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
6150 tagInfoPtr->numTags++;
6154 gtk_text_btree_link_segment (GtkTextLineSegment *seg,
6155 const GtkTextIter *iter)
6157 GtkTextLineSegment *prev;
6161 line = _gtk_text_iter_get_text_line (iter);
6162 tree = _gtk_text_iter_get_btree (iter);
6164 prev = gtk_text_line_segment_split (iter);
6167 seg->next = line->segments;
6168 line->segments = seg;
6172 seg->next = prev->next;
6175 cleanup_line (line);
6176 segments_changed (tree);
6178 if (gtk_debug_flags & GTK_DEBUG_TEXT)
6179 _gtk_text_btree_check (tree);
6183 gtk_text_btree_unlink_segment (GtkTextBTree *tree,
6184 GtkTextLineSegment *seg,
6187 GtkTextLineSegment *prev;
6189 if (line->segments == seg)
6191 line->segments = seg->next;
6195 for (prev = line->segments; prev->next != seg;
6198 /* Empty loop body. */
6200 prev->next = seg->next;
6202 cleanup_line (line);
6203 segments_changed (tree);
6207 * This is here because it requires BTree internals, it logically
6208 * belongs in gtktextsegment.c
6213 *--------------------------------------------------------------
6215 * _gtk_toggle_segment_check_func --
6217 * This procedure is invoked to perform consistency checks
6218 * on toggle segments.
6224 * If a consistency problem is found the procedure g_errors.
6226 *--------------------------------------------------------------
6230 _gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6236 if (segPtr->byte_count != 0)
6238 g_error ("toggle_segment_check_func: segment had non-zero size");
6240 if (!segPtr->body.toggle.inNodeCounts)
6242 g_error ("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6244 needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6245 for (summary = line->parent->summary; ;
6246 summary = summary->next)
6248 if (summary == NULL)
6252 g_error ("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6259 if (summary->info == segPtr->body.toggle.info)
6263 g_error ("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6275 gtk_text_btree_node_view_check_consistency (GtkTextBTree *tree,
6276 GtkTextBTreeNode *node,
6286 while (view != NULL)
6288 if (view->view_id == nd->view_id)
6295 g_error ("Node has data for a view %p no longer attached to the tree",
6298 gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6299 &width, &height, &valid);
6300 if (nd->width != width ||
6301 nd->height != height ||
6302 !nd->valid != !valid)
6304 g_error ("Node aggregates for view %p are invalid:\n"
6305 "Are (%d,%d,%s), should be (%d,%d,%s)",
6307 nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6308 width, height, valid ? "TRUE" : "FALSE");
6313 gtk_text_btree_node_check_consistency (GtkTextBTree *tree,
6314 GtkTextBTreeNode *node)
6316 GtkTextBTreeNode *childnode;
6317 Summary *summary, *summary2;
6319 GtkTextLineSegment *segPtr;
6320 int num_children, num_lines, num_chars, toggle_count, min_children;
6321 GtkTextLineData *ld;
6324 if (node->parent != NULL)
6326 min_children = MIN_CHILDREN;
6328 else if (node->level > 0)
6335 if ((node->num_children < min_children)
6336 || (node->num_children > MAX_CHILDREN))
6338 g_error ("gtk_text_btree_node_check_consistency: bad child count (%d)",
6339 node->num_children);
6342 nd = node->node_data;
6345 gtk_text_btree_node_view_check_consistency (tree, node, nd);
6352 if (node->level == 0)
6354 for (line = node->children.line; line != NULL;
6357 if (line->parent != node)
6359 g_error ("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6361 if (line->segments == NULL)
6363 g_error ("gtk_text_btree_node_check_consistency: line has no segments");
6369 /* Just ensuring we don't segv while doing this loop */
6374 for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6376 if (segPtr->type->checkFunc != NULL)
6378 (*segPtr->type->checkFunc)(segPtr, line);
6380 if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6381 && (segPtr->next != NULL)
6382 && (segPtr->next->byte_count == 0)
6383 && (segPtr->next->type->leftGravity))
6385 g_error ("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6387 if ((segPtr->next == NULL)
6388 && (segPtr->type != >k_text_char_type))
6390 g_error ("gtk_text_btree_node_check_consistency: line ended with wrong type");
6393 num_chars += segPtr->char_count;
6402 for (childnode = node->children.node; childnode != NULL;
6403 childnode = childnode->next)
6405 if (childnode->parent != node)
6407 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6409 if (childnode->level != (node->level-1))
6411 g_error ("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6412 node->level, childnode->level);
6414 gtk_text_btree_node_check_consistency (tree, childnode);
6415 for (summary = childnode->summary; summary != NULL;
6416 summary = summary->next)
6418 for (summary2 = node->summary; ;
6419 summary2 = summary2->next)
6421 if (summary2 == NULL)
6423 if (summary->info->tag_root == node)
6427 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6428 summary->info->tag->name,
6429 "present in parent summaries");
6431 if (summary->info == summary2->info)
6438 num_lines += childnode->num_lines;
6439 num_chars += childnode->num_chars;
6442 if (num_children != node->num_children)
6444 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6445 num_children, node->num_children);
6447 if (num_lines != node->num_lines)
6449 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6450 num_lines, node->num_lines);
6452 if (num_chars != node->num_chars)
6454 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6455 num_chars, node->num_chars);
6458 for (summary = node->summary; summary != NULL;
6459 summary = summary->next)
6461 if (summary->info->toggle_count == summary->toggle_count)
6463 g_error ("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6464 summary->info->tag->name);
6467 if (node->level == 0)
6469 for (line = node->children.line; line != NULL;
6472 for (segPtr = line->segments; segPtr != NULL;
6473 segPtr = segPtr->next)
6475 if ((segPtr->type != >k_text_toggle_on_type)
6476 && (segPtr->type != >k_text_toggle_off_type))
6480 if (segPtr->body.toggle.info == summary->info)
6482 if (!segPtr->body.toggle.inNodeCounts)
6483 g_error ("Toggle segment not in the node counts");
6492 for (childnode = node->children.node;
6494 childnode = childnode->next)
6496 for (summary2 = childnode->summary;
6498 summary2 = summary2->next)
6500 if (summary2->info == summary->info)
6502 toggle_count += summary2->toggle_count;
6507 if (toggle_count != summary->toggle_count)
6509 g_error ("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6510 toggle_count, summary->toggle_count);
6512 for (summary2 = summary->next; summary2 != NULL;
6513 summary2 = summary2->next)
6515 if (summary2->info == summary->info)
6517 g_error ("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6518 summary->info->tag->name);
6525 listify_foreach (GtkTextTag *tag, gpointer user_data)
6527 GSList** listp = user_data;
6529 *listp = g_slist_prepend (*listp, tag);
6533 list_of_tags (GtkTextTagTable *table)
6535 GSList *list = NULL;
6537 gtk_text_tag_table_foreach (table, listify_foreach, &list);
6543 _gtk_text_btree_check (GtkTextBTree *tree)
6546 GtkTextBTreeNode *node;
6548 GtkTextLineSegment *seg;
6550 GSList *taglist = NULL;
6552 GtkTextTagInfo *info;
6555 * Make sure that the tag toggle counts and the tag root pointers are OK.
6557 for (taglist = list_of_tags (tree->table);
6558 taglist != NULL ; taglist = taglist->next)
6560 tag = taglist->data;
6561 info = gtk_text_btree_get_existing_tag_info (tree, tag);
6564 node = info->tag_root;
6567 if (info->toggle_count != 0)
6569 g_error ("_gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6570 tag->name, info->toggle_count);
6572 continue; /* no ranges for the tag */
6574 else if (info->toggle_count == 0)
6576 g_error ("_gtk_text_btree_check found root for \"%s\" with no toggles",
6579 else if (info->toggle_count & 1)
6581 g_error ("_gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6582 tag->name, info->toggle_count);
6584 for (summary = node->summary; summary != NULL;
6585 summary = summary->next)
6587 if (summary->info->tag == tag)
6589 g_error ("_gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6593 if (node->level > 0)
6595 for (node = node->children.node ; node != NULL ;
6598 for (summary = node->summary; summary != NULL;
6599 summary = summary->next)
6601 if (summary->info->tag == tag)
6603 count += summary->toggle_count;
6610 GtkTextLineSegmentClass * last = NULL;
6612 for (line = node->children.line ; line != NULL ;
6615 for (seg = line->segments; seg != NULL;
6618 if ((seg->type == >k_text_toggle_on_type ||
6619 seg->type == >k_text_toggle_off_type) &&
6620 seg->body.toggle.info->tag == tag)
6622 if (last == seg->type)
6623 g_error ("Two consecutive toggles on or off weren't merged");
6624 if (!seg->body.toggle.inNodeCounts)
6625 g_error ("Toggle segment not in the node counts");
6634 if (count != info->toggle_count)
6636 g_error ("_gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
6637 info->toggle_count, tag->name, count);
6642 g_slist_free (taglist);
6646 * Call a recursive procedure to do the main body of checks.
6649 node = tree->root_node;
6650 gtk_text_btree_node_check_consistency (tree, tree->root_node);
6653 * Make sure that there are at least two lines in the text and
6654 * that the last line has no characters except a newline.
6657 if (node->num_lines < 2)
6659 g_error ("_gtk_text_btree_check: less than 2 lines in tree");
6661 if (node->num_chars < 2)
6663 g_error ("_gtk_text_btree_check: less than 2 chars in tree");
6665 while (node->level > 0)
6667 node = node->children.node;
6668 while (node->next != NULL)
6673 line = node->children.line;
6674 while (line->next != NULL)
6678 seg = line->segments;
6679 while ((seg->type == >k_text_toggle_off_type)
6680 || (seg->type == >k_text_right_mark_type)
6681 || (seg->type == >k_text_left_mark_type))
6684 * It's OK to toggle a tag off in the last line, but
6685 * not to start a new range. It's also OK to have marks
6691 if (seg->type != >k_text_char_type)
6693 g_error ("_gtk_text_btree_check: last line has bogus segment type");
6695 if (seg->next != NULL)
6697 g_error ("_gtk_text_btree_check: last line has too many segments");
6699 if (seg->byte_count != 1)
6701 g_error ("_gtk_text_btree_check: last line has wrong # characters: %d",
6704 if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
6706 g_error ("_gtk_text_btree_check: last line had bad value: %s",
6711 void _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line);
6712 void _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment* seg);
6713 void _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent);
6714 void _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
6717 _gtk_text_btree_spew (GtkTextBTree *tree)
6722 printf ("%d lines in tree %p\n",
6723 _gtk_text_btree_line_count (tree), tree);
6725 line = _gtk_text_btree_get_line (tree, 0, &real_line);
6727 while (line != NULL)
6729 _gtk_text_btree_spew_line (tree, line);
6730 line = _gtk_text_line_next (line);
6733 printf ("=================== Tag information\n");
6738 list = tree->tag_infos;
6740 while (list != NULL)
6742 GtkTextTagInfo *info;
6746 printf (" tag `%s': root at %p, toggle count %d\n",
6747 info->tag->name, info->tag_root, info->toggle_count);
6749 list = g_slist_next (list);
6752 if (tree->tag_infos == NULL)
6754 printf (" (no tags in the tree)\n");
6758 printf ("=================== Tree nodes\n");
6761 _gtk_text_btree_spew_node (tree->root_node, 0);
6766 _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
6769 GtkTextLineSegment *seg;
6771 spaces = g_strnfill (indent, ' ');
6773 printf ("%sline %p chars %d bytes %d\n",
6775 _gtk_text_line_char_count (line),
6776 _gtk_text_line_byte_count (line));
6778 seg = line->segments;
6781 if (seg->type == >k_text_char_type)
6783 gchar* str = g_strndup (seg->body.chars, MIN (seg->byte_count, 10));
6788 if (*s == '\n' || *s == '\r')
6792 printf ("%s chars `%s'...\n", spaces, str);
6795 else if (seg->type == >k_text_right_mark_type)
6797 printf ("%s right mark `%s' visible: %d\n",
6799 seg->body.mark.name,
6800 seg->body.mark.visible);
6802 else if (seg->type == >k_text_left_mark_type)
6804 printf ("%s left mark `%s' visible: %d\n",
6806 seg->body.mark.name,
6807 seg->body.mark.visible);
6809 else if (seg->type == >k_text_toggle_on_type ||
6810 seg->type == >k_text_toggle_off_type)
6812 printf ("%s tag `%s' %s\n",
6813 spaces, seg->body.toggle.info->tag->name,
6814 seg->type == >k_text_toggle_off_type ? "off" : "on");
6824 _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent)
6827 GtkTextBTreeNode *iter;
6830 spaces = g_strnfill (indent, ' ');
6832 printf ("%snode %p level %d children %d lines %d chars %d\n",
6833 spaces, node, node->level,
6834 node->num_children, node->num_lines, node->num_chars);
6839 printf ("%s %d toggles of `%s' below this node\n",
6840 spaces, s->toggle_count, s->info->tag->name);
6846 if (node->level > 0)
6848 iter = node->children.node;
6849 while (iter != NULL)
6851 _gtk_text_btree_spew_node (iter, indent + 2);
6858 GtkTextLine *line = node->children.line;
6859 while (line != NULL)
6861 _gtk_text_btree_spew_line_short (line, indent + 2);
6869 _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line)
6871 GtkTextLineSegment * seg;
6873 printf ("%4d| line: %p parent: %p next: %p\n",
6874 _gtk_text_line_get_number (line), line, line->parent, line->next);
6876 seg = line->segments;
6880 _gtk_text_btree_spew_segment (tree, seg);
6886 _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment * seg)
6888 printf (" segment: %p type: %s bytes: %d chars: %d\n",
6889 seg, seg->type->name, seg->byte_count, seg->char_count);
6891 if (seg->type == >k_text_char_type)
6893 gchar* str = g_strndup (seg->body.chars, seg->byte_count);
6894 printf (" `%s'\n", str);
6897 else if (seg->type == >k_text_right_mark_type)
6899 printf (" right mark `%s' visible: %d not_deleteable: %d\n",
6900 seg->body.mark.name,
6901 seg->body.mark.visible,
6902 seg->body.mark.not_deleteable);
6904 else if (seg->type == >k_text_left_mark_type)
6906 printf (" left mark `%s' visible: %d not_deleteable: %d\n",
6907 seg->body.mark.name,
6908 seg->body.mark.visible,
6909 seg->body.mark.not_deleteable);
6911 else if (seg->type == >k_text_toggle_on_type ||
6912 seg->type == >k_text_toggle_off_type)
6914 printf (" tag `%s' priority %d\n",
6915 seg->body.toggle.info->tag->name,
6916 seg->body.toggle.info->tag->priority);