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 /* The last line in the buffer has identity values for the per-view
1401 * data so that we can avoid special case checks for it in a large
1404 last_line = get_last_line (tree);
1406 line_data = g_new (GtkTextLineData, 1);
1407 line_data->view_id = layout;
1408 line_data->next = NULL;
1409 line_data->width = 0;
1410 line_data->height = 0;
1411 line_data->valid = TRUE;
1413 _gtk_text_line_add_data (last_line, line_data);
1417 _gtk_text_btree_remove_view (GtkTextBTree *tree,
1421 GtkTextLine *last_line;
1422 GtkTextLineData *line_data;
1424 g_return_if_fail (tree != NULL);
1428 while (view != NULL)
1430 if (view->view_id == view_id)
1436 g_return_if_fail (view != NULL);
1439 view->next->prev = view->prev;
1442 view->prev->next = view->next;
1444 if (view == tree->views)
1445 tree->views = view->next;
1447 /* Remove the line data for the last line which we added ourselves.
1448 * (Do this first, so that we don't try to call the view's line data destructor on it.)
1450 last_line = get_last_line (tree);
1451 line_data = _gtk_text_line_remove_data (last_line, view_id);
1454 gtk_text_btree_node_remove_view (view, tree->root_node, view_id);
1460 _gtk_text_btree_invalidate_region (GtkTextBTree *tree,
1461 const GtkTextIter *start,
1462 const GtkTextIter *end)
1468 while (view != NULL)
1470 gtk_text_layout_invalidate (view->layout, start, end);
1477 _gtk_text_btree_get_view_size (GtkTextBTree *tree,
1482 g_return_if_fail (tree != NULL);
1483 g_return_if_fail (view_id != NULL);
1485 gtk_text_btree_node_get_size (tree->root_node, view_id,
1500 iter_stack_new (void)
1503 stack = g_new (IterStack, 1);
1504 stack->iters = NULL;
1511 iter_stack_push (IterStack *stack, const GtkTextIter *iter)
1514 if (stack->count > stack->alloced)
1516 stack->alloced = stack->count*2;
1517 stack->iters = g_realloc (stack->iters,
1518 stack->alloced*sizeof (GtkTextIter));
1520 stack->iters[stack->count-1] = *iter;
1524 iter_stack_pop (IterStack *stack, GtkTextIter *iter)
1526 if (stack->count == 0)
1531 *iter = stack->iters[stack->count];
1537 iter_stack_free (IterStack *stack)
1539 g_free (stack->iters);
1544 iter_stack_invert (IterStack *stack)
1546 if (stack->count > 0)
1549 guint j = stack->count - 1;
1554 tmp = stack->iters[i];
1555 stack->iters[i] = stack->iters[j];
1556 stack->iters[j] = tmp;
1565 queue_tag_redisplay (GtkTextBTree *tree,
1567 const GtkTextIter *start,
1568 const GtkTextIter *end)
1570 if (_gtk_text_tag_affects_size (tag))
1572 _gtk_text_btree_invalidate_region (tree, start, end);
1574 else if (_gtk_text_tag_affects_nonsize_appearance (tag))
1576 /* We only need to queue a redraw, not a relayout */
1577 redisplay_region (tree, start, end);
1580 /* We don't need to do anything if the tag doesn't affect display */
1584 _gtk_text_btree_tag (const GtkTextIter *start_orig,
1585 const GtkTextIter *end_orig,
1589 GtkTextLineSegment *seg, *prev;
1590 GtkTextLine *cleanupline;
1591 gboolean toggled_on;
1592 GtkTextLine *start_line;
1593 GtkTextLine *end_line;
1595 GtkTextIter start, end;
1598 GtkTextTagInfo *info;
1600 g_return_if_fail (start_orig != NULL);
1601 g_return_if_fail (end_orig != NULL);
1602 g_return_if_fail (GTK_IS_TEXT_TAG (tag));
1603 g_return_if_fail (_gtk_text_iter_get_btree (start_orig) ==
1604 _gtk_text_iter_get_btree (end_orig));
1605 g_return_if_fail (tag->table == _gtk_text_iter_get_btree (start_orig)->table);
1608 printf ("%s tag %s from %d to %d\n",
1609 add ? "Adding" : "Removing",
1611 gtk_text_buffer_get_offset (start_orig),
1612 gtk_text_buffer_get_offset (end_orig));
1615 if (gtk_text_iter_equal (start_orig, end_orig))
1618 start = *start_orig;
1621 gtk_text_iter_order (&start, &end);
1623 tree = _gtk_text_iter_get_btree (&start);
1625 queue_tag_redisplay (tree, tag, &start, &end);
1627 info = gtk_text_btree_get_tag_info (tree, tag);
1629 start_line = _gtk_text_iter_get_text_line (&start);
1630 end_line = _gtk_text_iter_get_text_line (&end);
1632 /* Find all tag toggles in the region; we are going to delete them.
1633 We need to find them in advance, because
1634 forward_find_tag_toggle () won't work once we start playing around
1636 stack = iter_stack_new ();
1639 /* forward_to_tag_toggle() skips a toggle at the start iterator,
1640 * which is deliberate - we don't want to delete a toggle at the
1643 while (gtk_text_iter_forward_to_tag_toggle (&iter, tag))
1645 if (gtk_text_iter_compare (&iter, &end) >= 0)
1648 iter_stack_push (stack, &iter);
1651 /* We need to traverse the toggles in order. */
1652 iter_stack_invert (stack);
1655 * See whether the tag is present at the start of the range. If
1656 * the state doesn't already match what we want then add a toggle
1660 toggled_on = gtk_text_iter_has_tag (&start, tag);
1661 if ( (add && !toggled_on) ||
1662 (!add && toggled_on) )
1664 /* This could create a second toggle at the start position;
1665 cleanup_line () will remove it if so. */
1666 seg = _gtk_toggle_segment_new (info, add);
1668 prev = gtk_text_line_segment_split (&start);
1671 seg->next = start_line->segments;
1672 start_line->segments = seg;
1676 seg->next = prev->next;
1680 /* cleanup_line adds the new toggle to the node counts. */
1682 printf ("added toggle at start\n");
1684 /* we should probably call segments_changed, but in theory
1685 any still-cached segments in the iters we are about to
1686 use are still valid, since they're in front
1692 * Scan the range of characters and delete any internal tag
1693 * transitions. Keep track of what the old state was at the end
1694 * of the range, and add a toggle there if it's needed.
1698 cleanupline = start_line;
1699 while (iter_stack_pop (stack, &iter))
1701 GtkTextLineSegment *indexable_seg;
1704 line = _gtk_text_iter_get_text_line (&iter);
1705 seg = _gtk_text_iter_get_any_segment (&iter);
1706 indexable_seg = _gtk_text_iter_get_indexable_segment (&iter);
1708 g_assert (seg != NULL);
1709 g_assert (indexable_seg != NULL);
1710 g_assert (seg != indexable_seg);
1712 prev = line->segments;
1714 /* Find the segment that actually toggles this tag. */
1715 while (seg != indexable_seg)
1717 g_assert (seg != NULL);
1718 g_assert (indexable_seg != NULL);
1719 g_assert (seg != indexable_seg);
1721 if ( (seg->type == >k_text_toggle_on_type ||
1722 seg->type == >k_text_toggle_off_type) &&
1723 (seg->body.toggle.info == info) )
1729 g_assert (seg != NULL);
1730 g_assert (indexable_seg != NULL);
1732 g_assert (seg != indexable_seg); /* If this happens, then
1733 forward_to_tag_toggle was
1735 g_assert (seg->body.toggle.info->tag == tag);
1737 /* If this happens, when previously tagging we didn't merge
1738 overlapping tags. */
1739 g_assert ( (toggled_on && seg->type == >k_text_toggle_off_type) ||
1740 (!toggled_on && seg->type == >k_text_toggle_on_type) );
1742 toggled_on = !toggled_on;
1745 printf ("deleting %s toggle\n",
1746 seg->type == >k_text_toggle_on_type ? "on" : "off");
1748 /* Remove toggle segment from the list. */
1751 line->segments = seg->next;
1755 while (prev->next != seg)
1759 prev->next = seg->next;
1762 /* Inform iterators we've hosed them. This actually reflects a
1763 bit of inefficiency; if you have the same tag toggled on and
1764 off a lot in a single line, we keep having the rescan from
1765 the front of the line. Of course we have to do that to get
1766 "prev" anyway, but here we are doing it an additional
1768 segments_changed (tree);
1770 /* Update node counts */
1771 if (seg->body.toggle.inNodeCounts)
1773 _gtk_change_node_toggle_count (line->parent,
1775 seg->body.toggle.inNodeCounts = FALSE;
1780 /* We only clean up lines when we're done with them, saves some
1781 gratuitous line-segment-traversals */
1783 if (cleanupline != line)
1785 cleanup_line (cleanupline);
1790 iter_stack_free (stack);
1792 /* toggled_on now reflects the toggle state _just before_ the
1793 end iterator. The end iterator could already have a toggle
1794 on or a toggle off. */
1795 if ( (add && !toggled_on) ||
1796 (!add && toggled_on) )
1798 /* This could create a second toggle at the start position;
1799 cleanup_line () will remove it if so. */
1801 seg = _gtk_toggle_segment_new (info, !add);
1803 prev = gtk_text_line_segment_split (&end);
1806 seg->next = end_line->segments;
1807 end_line->segments = seg;
1811 seg->next = prev->next;
1814 /* cleanup_line adds the new toggle to the node counts. */
1815 g_assert (seg->body.toggle.inNodeCounts == FALSE);
1817 printf ("added toggle at end\n");
1822 * Cleanup cleanupline and the last line of the range, if
1823 * these are different.
1826 cleanup_line (cleanupline);
1827 if (cleanupline != end_line)
1829 cleanup_line (end_line);
1832 segments_changed (tree);
1834 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1835 _gtk_text_btree_check (tree);
1844 _gtk_text_btree_get_line (GtkTextBTree *tree,
1846 gint *real_line_number)
1848 GtkTextBTreeNode *node;
1853 line_count = _gtk_text_btree_line_count (tree);
1855 if (line_number < 0)
1857 line_number = line_count;
1859 else if (line_number > line_count)
1861 line_number = line_count;
1864 if (real_line_number)
1865 *real_line_number = line_number;
1867 node = tree->root_node;
1868 lines_left = line_number;
1871 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1875 while (node->level != 0)
1877 for (node = node->children.node;
1878 node->num_lines <= lines_left;
1884 g_error ("gtk_text_btree_find_line ran out of GtkTextBTreeNodes");
1887 lines_left -= node->num_lines;
1892 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1895 for (line = node->children.line; lines_left > 0;
1901 g_error ("gtk_text_btree_find_line ran out of lines");
1910 _gtk_text_btree_get_line_at_char (GtkTextBTree *tree,
1912 gint *line_start_index,
1913 gint *real_char_index)
1915 GtkTextBTreeNode *node;
1917 GtkTextLineSegment *seg;
1922 node = tree->root_node;
1924 /* Clamp to valid indexes (-1 is magic for "highest index") */
1925 if (char_index < 0 || char_index >= node->num_chars)
1927 char_index = node->num_chars - 1;
1930 *real_char_index = char_index;
1933 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1937 chars_left = char_index;
1938 while (node->level != 0)
1940 for (node = node->children.node;
1941 chars_left >= node->num_chars;
1944 chars_left -= node->num_chars;
1946 g_assert (chars_left >= 0);
1950 if (chars_left == 0)
1952 /* Start of a line */
1954 *line_start_index = char_index;
1955 return node->children.line;
1959 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1965 for (line = node->children.line; line != NULL; line = line->next)
1967 seg = line->segments;
1970 if (chars_in_line + seg->char_count > chars_left)
1971 goto found; /* found our line/segment */
1973 chars_in_line += seg->char_count;
1978 chars_left -= chars_in_line;
1986 g_assert (line != NULL); /* hosage, ran out of lines */
1987 g_assert (seg != NULL);
1989 *line_start_index = char_index - chars_left;
1994 _gtk_text_btree_get_tags (const GtkTextIter *iter,
1997 GtkTextBTreeNode *node;
1998 GtkTextLine *siblingline;
1999 GtkTextLineSegment *seg;
2000 int src, dst, index;
2006 #define NUM_TAG_INFOS 10
2008 line = _gtk_text_iter_get_text_line (iter);
2009 tree = _gtk_text_iter_get_btree (iter);
2010 byte_index = gtk_text_iter_get_line_index (iter);
2012 tagInfo.numTags = 0;
2013 tagInfo.arraySize = NUM_TAG_INFOS;
2014 tagInfo.tags = g_new (GtkTextTag*, NUM_TAG_INFOS);
2015 tagInfo.counts = g_new (int, NUM_TAG_INFOS);
2018 * Record tag toggles within the line of indexPtr but preceding
2019 * indexPtr. Note that if this loop segfaults, your
2020 * byte_index probably points past the sum of all
2021 * seg->byte_count */
2023 for (index = 0, seg = line->segments;
2024 (index + seg->byte_count) <= byte_index;
2025 index += seg->byte_count, seg = seg->next)
2027 if ((seg->type == >k_text_toggle_on_type)
2028 || (seg->type == >k_text_toggle_off_type))
2030 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2035 * Record toggles for tags in lines that are predecessors of
2036 * line but under the same level-0 GtkTextBTreeNode.
2039 for (siblingline = line->parent->children.line;
2040 siblingline != line;
2041 siblingline = siblingline->next)
2043 for (seg = siblingline->segments; seg != NULL;
2046 if ((seg->type == >k_text_toggle_on_type)
2047 || (seg->type == >k_text_toggle_off_type))
2049 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2055 * For each GtkTextBTreeNode in the ancestry of this line, record tag
2056 * toggles for all siblings that precede that GtkTextBTreeNode.
2059 for (node = line->parent; node->parent != NULL;
2060 node = node->parent)
2062 GtkTextBTreeNode *siblingPtr;
2065 for (siblingPtr = node->parent->children.node;
2066 siblingPtr != node; siblingPtr = siblingPtr->next)
2068 for (summary = siblingPtr->summary; summary != NULL;
2069 summary = summary->next)
2071 if (summary->toggle_count & 1)
2073 inc_count (summary->info->tag, summary->toggle_count,
2081 * Go through the tag information and squash out all of the tags
2082 * that have even toggle counts (these tags exist before the point
2083 * of interest, but not at the desired character itself).
2086 for (src = 0, dst = 0; src < tagInfo.numTags; src++)
2088 if (tagInfo.counts[src] & 1)
2090 g_assert (GTK_IS_TEXT_TAG (tagInfo.tags[src]));
2091 tagInfo.tags[dst] = tagInfo.tags[src];
2097 g_free (tagInfo.counts);
2100 g_free (tagInfo.tags);
2103 return tagInfo.tags;
2107 copy_segment (GString *string,
2108 gboolean include_hidden,
2109 gboolean include_nonchars,
2110 const GtkTextIter *start,
2111 const GtkTextIter *end)
2113 GtkTextLineSegment *end_seg;
2114 GtkTextLineSegment *seg;
2116 if (gtk_text_iter_equal (start, end))
2119 seg = _gtk_text_iter_get_indexable_segment (start);
2120 end_seg = _gtk_text_iter_get_indexable_segment (end);
2122 if (seg->type == >k_text_char_type)
2124 gboolean copy = TRUE;
2125 gint copy_bytes = 0;
2126 gint copy_start = 0;
2128 /* Don't copy if we're invisible; segments are invisible/not
2129 as a whole, no need to check each char */
2130 if (!include_hidden &&
2131 _gtk_text_btree_char_is_invisible (start))
2134 /* printf (" <invisible>\n"); */
2137 copy_start = _gtk_text_iter_get_segment_byte (start);
2141 /* End is in the same segment; need to copy fewer bytes. */
2142 gint end_byte = _gtk_text_iter_get_segment_byte (end);
2144 copy_bytes = end_byte - copy_start;
2147 copy_bytes = seg->byte_count - copy_start;
2149 g_assert (copy_bytes != 0); /* Due to iter equality check at
2150 front of this function. */
2154 g_assert ((copy_start + copy_bytes) <= seg->byte_count);
2156 g_string_append_len (string,
2157 seg->body.chars + copy_start,
2161 /* printf (" :%s\n", string->str); */
2163 else if (seg->type == >k_text_pixbuf_type ||
2164 seg->type == >k_text_child_type)
2166 gboolean copy = TRUE;
2168 if (!include_nonchars)
2172 else if (!include_hidden &&
2173 _gtk_text_btree_char_is_invisible (start))
2180 g_string_append_len (string,
2181 gtk_text_unknown_char_utf8,
2189 _gtk_text_btree_get_text (const GtkTextIter *start_orig,
2190 const GtkTextIter *end_orig,
2191 gboolean include_hidden,
2192 gboolean include_nonchars)
2194 GtkTextLineSegment *seg;
2195 GtkTextLineSegment *end_seg;
2203 g_return_val_if_fail (start_orig != NULL, NULL);
2204 g_return_val_if_fail (end_orig != NULL, NULL);
2205 g_return_val_if_fail (_gtk_text_iter_get_btree (start_orig) ==
2206 _gtk_text_iter_get_btree (end_orig), NULL);
2208 start = *start_orig;
2211 gtk_text_iter_order (&start, &end);
2213 retval = g_string_new ("");
2215 tree = _gtk_text_iter_get_btree (&start);
2217 end_seg = _gtk_text_iter_get_indexable_segment (&end);
2219 seg = _gtk_text_iter_get_indexable_segment (&iter);
2220 while (seg != end_seg)
2222 copy_segment (retval, include_hidden, include_nonchars,
2225 _gtk_text_iter_forward_indexable_segment (&iter);
2227 seg = _gtk_text_iter_get_indexable_segment (&iter);
2230 copy_segment (retval, include_hidden, include_nonchars, &iter, &end);
2233 g_string_free (retval, FALSE);
2238 _gtk_text_btree_line_count (GtkTextBTree *tree)
2240 /* Subtract bogus line at the end; we return a count
2242 return tree->root_node->num_lines - 1;
2246 _gtk_text_btree_char_count (GtkTextBTree *tree)
2248 /* Exclude newline in bogus last line */
2249 return tree->root_node->num_chars - 1;
2252 #define LOTSA_TAGS 1000
2254 _gtk_text_btree_char_is_invisible (const GtkTextIter *iter)
2256 gboolean invisible = FALSE; /* if nobody says otherwise, it's visible */
2258 int deftagCnts[LOTSA_TAGS];
2259 int *tagCnts = deftagCnts;
2260 GtkTextTag *deftags[LOTSA_TAGS];
2261 GtkTextTag **tags = deftags;
2263 GtkTextBTreeNode *node;
2264 GtkTextLine *siblingline;
2265 GtkTextLineSegment *seg;
2272 line = _gtk_text_iter_get_text_line (iter);
2273 tree = _gtk_text_iter_get_btree (iter);
2274 byte_index = gtk_text_iter_get_line_index (iter);
2276 numTags = gtk_text_tag_table_get_size (tree->table);
2278 /* almost always avoid malloc, so stay out of system calls */
2279 if (LOTSA_TAGS < numTags)
2281 tagCnts = g_new (int, numTags);
2282 tags = g_new (GtkTextTag*, numTags);
2285 for (i=0; i<numTags; i++)
2291 * Record tag toggles within the line of indexPtr but preceding
2295 for (index = 0, seg = line->segments;
2296 (index + seg->byte_count) <= byte_index; /* segfault here means invalid index */
2297 index += seg->byte_count, seg = seg->next)
2299 if ((seg->type == >k_text_toggle_on_type)
2300 || (seg->type == >k_text_toggle_off_type))
2302 tag = seg->body.toggle.info->tag;
2303 if (tag->invisible_set && tag->values->invisible)
2305 tags[tag->priority] = tag;
2306 tagCnts[tag->priority]++;
2312 * Record toggles for tags in lines that are predecessors of
2313 * line but under the same level-0 GtkTextBTreeNode.
2316 for (siblingline = line->parent->children.line;
2317 siblingline != line;
2318 siblingline = siblingline->next)
2320 for (seg = siblingline->segments; seg != NULL;
2323 if ((seg->type == >k_text_toggle_on_type)
2324 || (seg->type == >k_text_toggle_off_type))
2326 tag = seg->body.toggle.info->tag;
2327 if (tag->invisible_set && tag->values->invisible)
2329 tags[tag->priority] = tag;
2330 tagCnts[tag->priority]++;
2337 * For each GtkTextBTreeNode in the ancestry of this line, record tag toggles
2338 * for all siblings that precede that GtkTextBTreeNode.
2341 for (node = line->parent; node->parent != NULL;
2342 node = node->parent)
2344 GtkTextBTreeNode *siblingPtr;
2347 for (siblingPtr = node->parent->children.node;
2348 siblingPtr != node; siblingPtr = siblingPtr->next)
2350 for (summary = siblingPtr->summary; summary != NULL;
2351 summary = summary->next)
2353 if (summary->toggle_count & 1)
2355 tag = summary->info->tag;
2356 if (tag->invisible_set && tag->values->invisible)
2358 tags[tag->priority] = tag;
2359 tagCnts[tag->priority] += summary->toggle_count;
2367 * Now traverse from highest priority to lowest,
2368 * take invisible value from first odd count (= on)
2371 for (i = numTags-1; i >=0; i--)
2375 /* FIXME not sure this should be if 0 */
2377 #ifndef ALWAYS_SHOW_SELECTION
2378 /* who would make the selection invisible? */
2379 if ((tag == tkxt->seltag)
2380 && !(tkxt->flags & GOT_FOCUS))
2386 invisible = tags[i]->values->invisible;
2391 if (LOTSA_TAGS < numTags)
2406 redisplay_region (GtkTextBTree *tree,
2407 const GtkTextIter *start,
2408 const GtkTextIter *end)
2411 GtkTextLine *start_line, *end_line;
2413 if (gtk_text_iter_compare (start, end) > 0)
2415 const GtkTextIter *tmp = start;
2420 start_line = _gtk_text_iter_get_text_line (start);
2421 end_line = _gtk_text_iter_get_text_line (end);
2424 while (view != NULL)
2426 gint start_y, end_y;
2427 GtkTextLineData *ld;
2429 start_y = _gtk_text_btree_find_line_top (tree, start_line, view->view_id);
2431 if (end_line == start_line)
2434 end_y = _gtk_text_btree_find_line_top (tree, end_line, view->view_id);
2436 ld = _gtk_text_line_get_data (end_line, view->view_id);
2438 end_y += ld->height;
2440 gtk_text_layout_changed (view->layout, start_y,
2449 redisplay_mark (GtkTextLineSegment *mark)
2454 _gtk_text_btree_get_iter_at_mark (mark->body.mark.tree,
2456 mark->body.mark.obj);
2459 gtk_text_iter_forward_char (&end);
2461 _gtk_text_btree_invalidate_region (mark->body.mark.tree,
2466 redisplay_mark_if_visible (GtkTextLineSegment *mark)
2468 if (!mark->body.mark.visible)
2471 redisplay_mark (mark);
2475 ensure_not_off_end (GtkTextBTree *tree,
2476 GtkTextLineSegment *mark,
2479 if (gtk_text_iter_get_line (iter) ==
2480 _gtk_text_btree_line_count (tree))
2481 gtk_text_iter_backward_char (iter);
2484 static GtkTextLineSegment*
2485 real_set_mark (GtkTextBTree *tree,
2486 GtkTextMark *existing_mark,
2488 gboolean left_gravity,
2489 const GtkTextIter *where,
2490 gboolean should_exist,
2491 gboolean redraw_selections)
2493 GtkTextLineSegment *mark;
2496 g_return_val_if_fail (tree != NULL, NULL);
2497 g_return_val_if_fail (where != NULL, NULL);
2498 g_return_val_if_fail (_gtk_text_iter_get_btree (where) == tree, NULL);
2501 mark = existing_mark->segment;
2502 else if (name != NULL)
2503 mark = g_hash_table_lookup (tree->mark_table,
2508 if (should_exist && mark == NULL)
2510 g_warning ("No mark `%s' exists!", name);
2514 /* OK if !should_exist and it does already exist, in that case
2520 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2521 _gtk_text_iter_check (&iter);
2525 if (redraw_selections &&
2526 (mark == tree->insert_mark->segment ||
2527 mark == tree->selection_bound_mark->segment))
2529 GtkTextIter old_pos;
2531 _gtk_text_btree_get_iter_at_mark (tree, &old_pos,
2532 mark->body.mark.obj);
2533 redisplay_region (tree, &old_pos, where);
2537 * don't let visible marks be after the final newline of the
2541 if (mark->body.mark.visible)
2543 ensure_not_off_end (tree, mark, &iter);
2546 /* Redraw the mark's old location. */
2547 redisplay_mark_if_visible (mark);
2549 /* Unlink mark from its current location.
2550 This could hose our iterator... */
2551 gtk_text_btree_unlink_segment (tree, mark,
2552 mark->body.mark.line);
2553 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2554 g_assert (mark->body.mark.line == _gtk_text_iter_get_text_line (&iter));
2556 segments_changed (tree); /* make sure the iterator recomputes its
2561 mark = _gtk_mark_segment_new (tree,
2565 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2567 if (mark->body.mark.name)
2568 g_hash_table_insert (tree->mark_table,
2569 mark->body.mark.name,
2573 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2574 _gtk_text_iter_check (&iter);
2576 /* Link mark into new location */
2577 gtk_text_btree_link_segment (mark, &iter);
2579 /* Invalidate some iterators. */
2580 segments_changed (tree);
2583 * update the screen at the mark's new location.
2586 redisplay_mark_if_visible (mark);
2588 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2589 _gtk_text_iter_check (&iter);
2591 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2592 _gtk_text_btree_check (tree);
2599 _gtk_text_btree_set_mark (GtkTextBTree *tree,
2600 GtkTextMark *existing_mark,
2602 gboolean left_gravity,
2603 const GtkTextIter *iter,
2604 gboolean should_exist)
2606 GtkTextLineSegment *seg;
2608 seg = real_set_mark (tree, existing_mark,
2609 name, left_gravity, iter, should_exist,
2612 return seg ? seg->body.mark.obj : NULL;
2616 _gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2620 GtkTextIter tmp_start, tmp_end;
2622 _gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2624 _gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2625 tree->selection_bound_mark);
2627 if (gtk_text_iter_equal (&tmp_start, &tmp_end))
2639 gtk_text_iter_order (&tmp_start, &tmp_end);
2652 _gtk_text_btree_place_cursor (GtkTextBTree *tree,
2653 const GtkTextIter *iter)
2655 GtkTextIter start, end;
2657 if (_gtk_text_btree_get_selection_bounds (tree, &start, &end))
2658 redisplay_region (tree, &start, &end);
2660 /* Move insert AND selection_bound before we redisplay */
2661 real_set_mark (tree, tree->insert_mark,
2662 "insert", FALSE, iter, TRUE, FALSE);
2663 real_set_mark (tree, tree->selection_bound_mark,
2664 "selection_bound", FALSE, iter, TRUE, FALSE);
2668 _gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2673 g_return_if_fail (tree != NULL);
2674 g_return_if_fail (name != NULL);
2676 mark = g_hash_table_lookup (tree->mark_table,
2679 _gtk_text_btree_remove_mark (tree, mark);
2683 _gtk_text_btree_remove_mark (GtkTextBTree *tree,
2686 GtkTextLineSegment *segment;
2688 g_return_if_fail (mark != NULL);
2689 g_return_if_fail (tree != NULL);
2691 segment = mark->segment;
2693 if (segment->body.mark.not_deleteable)
2695 g_warning ("Can't delete special mark `%s'", segment->body.mark.name);
2699 /* This calls cleanup_line and segments_changed */
2700 gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2702 if (segment->body.mark.name)
2703 g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2705 /* Remove the ref on the mark that belonged to the segment. */
2706 g_object_unref (G_OBJECT (mark));
2708 segment->body.mark.tree = NULL;
2709 segment->body.mark.line = NULL;
2713 _gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2714 GtkTextMark *segment)
2716 return segment == tree->insert_mark;
2720 _gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2721 GtkTextMark *segment)
2723 return segment == tree->selection_bound_mark;
2727 _gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2730 GtkTextLineSegment *seg;
2732 g_return_val_if_fail (tree != NULL, NULL);
2733 g_return_val_if_fail (name != NULL, NULL);
2735 seg = g_hash_table_lookup (tree->mark_table, name);
2737 return seg ? seg->body.mark.obj : NULL;
2741 * gtk_text_mark_set_visible:
2742 * @mark: a #GtkTextMark
2743 * @setting: visibility of mark
2745 * Sets the visibility of @mark; the insertion point is normally
2746 * visible, i.e. you can see it as a vertical bar. Also, the text
2747 * widget uses a visible mark to indicate where a drop will occur when
2748 * dragging-and-dropping text. Most other marks are not visible.
2749 * Marks are not visible by default.
2753 gtk_text_mark_set_visible (GtkTextMark *mark,
2756 GtkTextLineSegment *seg;
2758 g_return_if_fail (mark != NULL);
2760 seg = mark->segment;
2762 if (seg->body.mark.visible == setting)
2766 seg->body.mark.visible = setting;
2768 redisplay_mark (seg);
2773 _gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
2776 GtkTextBTreeNode *node;
2777 GtkTextTagInfo *info;
2779 g_return_val_if_fail (tree != NULL, NULL);
2783 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2788 if (info->tag_root == NULL)
2791 node = info->tag_root;
2793 /* We know the tag root has instances of the given
2796 continue_outer_loop:
2797 g_assert (node != NULL);
2798 while (node->level > 0)
2800 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2801 node = node->children.node;
2802 while (node != NULL)
2804 if (gtk_text_btree_node_has_tag (node, tag))
2805 goto continue_outer_loop;
2809 g_assert (node != NULL);
2812 g_assert (node != NULL); /* The tag summaries said some node had
2815 g_assert (node->level == 0);
2817 return node->children.line;
2821 /* Looking for any tag at all (tag == NULL).
2822 Unfortunately this can't be done in a simple and efficient way
2823 right now; so I'm just going to return the
2824 first line in the btree. FIXME */
2825 return _gtk_text_btree_get_line (tree, 0, NULL);
2830 _gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
2833 GtkTextBTreeNode *node;
2834 GtkTextBTreeNode *last_node;
2836 GtkTextTagInfo *info;
2838 g_return_val_if_fail (tree != NULL, NULL);
2842 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2844 if (info->tag_root == NULL)
2847 node = info->tag_root;
2848 /* We know the tag root has instances of the given
2851 while (node->level > 0)
2853 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2855 node = node->children.node;
2856 while (node != NULL)
2858 if (gtk_text_btree_node_has_tag (node, tag))
2866 g_assert (node != NULL); /* The tag summaries said some node had
2869 g_assert (node->level == 0);
2871 /* Find the last line in this node */
2872 line = node->children.line;
2873 while (line->next != NULL)
2880 /* This search can't be done efficiently at the moment,
2881 at least not without complexity.
2882 So, we just return the last line.
2884 return _gtk_text_btree_get_line (tree, -1, NULL);
2894 _gtk_text_line_get_number (GtkTextLine *line)
2897 GtkTextBTreeNode *node, *parent, *node2;
2901 * First count how many lines precede this one in its level-0
2905 node = line->parent;
2907 for (line2 = node->children.line; line2 != line;
2908 line2 = line2->next)
2912 g_error ("gtk_text_btree_line_number couldn't find line");
2918 * Now work up through the levels of the tree one at a time,
2919 * counting how many lines are in GtkTextBTreeNodes preceding the current
2923 for (parent = node->parent ; parent != NULL;
2924 node = parent, parent = parent->parent)
2926 for (node2 = parent->children.node; node2 != node;
2927 node2 = node2->next)
2931 g_error ("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
2933 index += node2->num_lines;
2939 static GtkTextLineSegment*
2940 find_toggle_segment_before_char (GtkTextLine *line,
2944 GtkTextLineSegment *seg;
2945 GtkTextLineSegment *toggle_seg;
2950 seg = line->segments;
2951 while ( (index + seg->char_count) <= char_in_line )
2953 if (((seg->type == >k_text_toggle_on_type)
2954 || (seg->type == >k_text_toggle_off_type))
2955 && (seg->body.toggle.info->tag == tag))
2958 index += seg->char_count;
2965 static GtkTextLineSegment*
2966 find_toggle_segment_before_byte (GtkTextLine *line,
2970 GtkTextLineSegment *seg;
2971 GtkTextLineSegment *toggle_seg;
2976 seg = line->segments;
2977 while ( (index + seg->byte_count) <= byte_in_line )
2979 if (((seg->type == >k_text_toggle_on_type)
2980 || (seg->type == >k_text_toggle_off_type))
2981 && (seg->body.toggle.info->tag == tag))
2984 index += seg->byte_count;
2992 find_toggle_outside_current_line (GtkTextLine *line,
2996 GtkTextBTreeNode *node;
2997 GtkTextLine *sibling_line;
2998 GtkTextLineSegment *seg;
2999 GtkTextLineSegment *toggle_seg;
3001 GtkTextTagInfo *info = NULL;
3004 * No toggle in this line. Look for toggles for the tag in lines
3005 * that are predecessors of line but under the same
3006 * level-0 GtkTextBTreeNode.
3009 sibling_line = line->parent->children.line;
3010 while (sibling_line != line)
3012 seg = sibling_line->segments;
3015 if (((seg->type == >k_text_toggle_on_type)
3016 || (seg->type == >k_text_toggle_off_type))
3017 && (seg->body.toggle.info->tag == tag))
3023 sibling_line = sibling_line->next;
3026 if (toggle_seg != NULL)
3027 return (toggle_seg->type == >k_text_toggle_on_type);
3030 * No toggle in this GtkTextBTreeNode. Scan upwards through the ancestors of
3031 * this GtkTextBTreeNode, counting the number of toggles of the given tag in
3032 * siblings that precede that GtkTextBTreeNode.
3035 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3041 node = line->parent;
3042 while (node->parent != NULL)
3044 GtkTextBTreeNode *sibling_node;
3046 sibling_node = node->parent->children.node;
3047 while (sibling_node != node)
3051 summary = sibling_node->summary;
3052 while (summary != NULL)
3054 if (summary->info == info)
3055 toggles += summary->toggle_count;
3057 summary = summary->next;
3060 sibling_node = sibling_node->next;
3063 if (node == info->tag_root)
3066 node = node->parent;
3070 * An odd number of toggles means that the tag is present at the
3074 return (toggles & 1) != 0;
3077 /* FIXME this function is far too slow, for no good reason. */
3079 _gtk_text_line_char_has_tag (GtkTextLine *line,
3084 GtkTextLineSegment *toggle_seg;
3086 g_return_val_if_fail (line != NULL, FALSE);
3089 * Check for toggles for the tag in the line but before
3090 * the char. If there is one, its type indicates whether or
3091 * not the character is tagged.
3094 toggle_seg = find_toggle_segment_before_char (line, char_in_line, tag);
3096 if (toggle_seg != NULL)
3097 return (toggle_seg->type == >k_text_toggle_on_type);
3099 return find_toggle_outside_current_line (line, tree, tag);
3103 _gtk_text_line_byte_has_tag (GtkTextLine *line,
3108 GtkTextLineSegment *toggle_seg;
3110 g_return_val_if_fail (line != NULL, FALSE);
3113 * Check for toggles for the tag in the line but before
3114 * the char. If there is one, its type indicates whether or
3115 * not the character is tagged.
3118 toggle_seg = find_toggle_segment_before_byte (line, byte_in_line, tag);
3120 if (toggle_seg != NULL)
3121 return (toggle_seg->type == >k_text_toggle_on_type);
3123 return find_toggle_outside_current_line (line, tree, tag);
3127 _gtk_text_line_is_last (GtkTextLine *line,
3130 return line == get_last_line (tree);
3134 _gtk_text_line_next (GtkTextLine *line)
3136 GtkTextBTreeNode *node;
3138 if (line->next != NULL)
3143 * This was the last line associated with the particular parent
3144 * GtkTextBTreeNode. Search up the tree for the next GtkTextBTreeNode,
3145 * then search down from that GtkTextBTreeNode to find the first
3149 node = line->parent;
3150 while (node != NULL && node->next == NULL)
3151 node = node->parent;
3157 while (node->level > 0)
3159 node = node->children.node;
3162 g_assert (node->children.line != line);
3164 return node->children.line;
3169 _gtk_text_line_previous (GtkTextLine *line)
3171 GtkTextBTreeNode *node;
3172 GtkTextBTreeNode *node2;
3176 * Find the line under this GtkTextBTreeNode just before the starting line.
3178 prev = line->parent->children.line; /* First line at leaf */
3179 while (prev != line)
3181 if (prev->next == line)
3187 g_error ("gtk_text_btree_previous_line ran out of lines");
3191 * This was the first line associated with the particular parent
3192 * GtkTextBTreeNode. Search up the tree for the previous GtkTextBTreeNode,
3193 * then search down from that GtkTextBTreeNode to find its last line.
3195 for (node = line->parent; ; node = node->parent)
3197 if (node == NULL || node->parent == NULL)
3199 else if (node != node->parent->children.node)
3203 for (node2 = node->parent->children.node; ;
3204 node2 = node2->children.node)
3206 while (node2->next != node)
3207 node2 = node2->next;
3209 if (node2->level == 0)
3215 for (prev = node2->children.line ; ; prev = prev->next)
3217 if (prev->next == NULL)
3221 g_assert_not_reached ();
3226 _gtk_text_line_add_data (GtkTextLine *line,
3227 GtkTextLineData *data)
3229 g_return_if_fail (line != NULL);
3230 g_return_if_fail (data != NULL);
3231 g_return_if_fail (data->view_id != NULL);
3235 data->next = line->views;
3245 _gtk_text_line_remove_data (GtkTextLine *line,
3248 GtkTextLineData *prev;
3249 GtkTextLineData *iter;
3251 g_return_val_if_fail (line != NULL, NULL);
3252 g_return_val_if_fail (view_id != NULL, NULL);
3256 while (iter != NULL)
3258 if (iter->view_id == view_id)
3267 prev->next = iter->next;
3269 line->views = iter->next;
3278 _gtk_text_line_get_data (GtkTextLine *line,
3281 GtkTextLineData *iter;
3283 g_return_val_if_fail (line != NULL, NULL);
3284 g_return_val_if_fail (view_id != NULL, NULL);
3287 while (iter != NULL)
3289 if (iter->view_id == view_id)
3298 _gtk_text_line_invalidate_wrap (GtkTextLine *line,
3299 GtkTextLineData *ld)
3301 /* For now this is totally unoptimized. FIXME?
3303 We could probably optimize the case where the width removed
3304 is less than the max width for the parent node,
3305 and the case where the height is unchanged when we re-wrap.
3308 g_return_if_fail (ld != NULL);
3311 gtk_text_btree_node_invalidate_upward (line->parent, ld->view_id);
3315 _gtk_text_line_char_count (GtkTextLine *line)
3317 GtkTextLineSegment *seg;
3321 seg = line->segments;
3324 size += seg->char_count;
3331 _gtk_text_line_byte_count (GtkTextLine *line)
3333 GtkTextLineSegment *seg;
3337 seg = line->segments;
3340 size += seg->byte_count;
3348 _gtk_text_line_char_index (GtkTextLine *target_line)
3350 GSList *node_stack = NULL;
3351 GtkTextBTreeNode *iter;
3355 /* Push all our parent nodes onto a stack */
3356 iter = target_line->parent;
3358 g_assert (iter != NULL);
3360 while (iter != NULL)
3362 node_stack = g_slist_prepend (node_stack, iter);
3364 iter = iter->parent;
3367 /* Check that we have the root node on top of the stack. */
3368 g_assert (node_stack != NULL &&
3369 node_stack->data != NULL &&
3370 ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3372 /* Add up chars in all nodes before the nodes in our stack.
3376 iter = node_stack->data;
3377 while (iter != NULL)
3379 GtkTextBTreeNode *child_iter;
3380 GtkTextBTreeNode *next_node;
3382 next_node = node_stack->next ?
3383 node_stack->next->data : NULL;
3384 node_stack = g_slist_remove (node_stack, node_stack->data);
3386 if (iter->level == 0)
3388 /* stack should be empty when we're on the last node */
3389 g_assert (node_stack == NULL);
3390 break; /* Our children are now lines */
3393 g_assert (next_node != NULL);
3394 g_assert (iter != NULL);
3395 g_assert (next_node->parent == iter);
3397 /* Add up chars before us in the tree */
3398 child_iter = iter->children.node;
3399 while (child_iter != next_node)
3401 g_assert (child_iter != NULL);
3403 num_chars += child_iter->num_chars;
3405 child_iter = child_iter->next;
3411 g_assert (iter != NULL);
3412 g_assert (iter == target_line->parent);
3414 /* Since we don't store char counts in lines, only in segments, we
3415 have to iterate over the lines adding up segment char counts
3416 until we find our line. */
3417 line = iter->children.line;
3418 while (line != target_line)
3420 g_assert (line != NULL);
3422 num_chars += _gtk_text_line_char_count (line);
3427 g_assert (line == target_line);
3433 _gtk_text_line_byte_to_segment (GtkTextLine *line,
3437 GtkTextLineSegment *seg;
3440 g_return_val_if_fail (line != NULL, NULL);
3442 offset = byte_offset;
3443 seg = line->segments;
3445 while (offset >= seg->byte_count)
3447 g_assert (seg != NULL); /* means an invalid byte index */
3448 offset -= seg->byte_count;
3453 *seg_offset = offset;
3459 _gtk_text_line_char_to_segment (GtkTextLine *line,
3463 GtkTextLineSegment *seg;
3466 g_return_val_if_fail (line != NULL, NULL);
3468 offset = char_offset;
3469 seg = line->segments;
3471 while (offset >= seg->char_count)
3473 g_assert (seg != NULL); /* means an invalid char index */
3474 offset -= seg->char_count;
3479 *seg_offset = offset;
3485 _gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3489 GtkTextLineSegment *seg;
3492 g_return_val_if_fail (line != NULL, NULL);
3494 offset = byte_offset;
3495 seg = line->segments;
3497 while (offset > 0 && offset >= seg->byte_count)
3499 g_assert (seg != NULL); /* means an invalid byte index */
3500 offset -= seg->byte_count;
3505 *seg_offset = offset;
3511 _gtk_text_line_char_to_any_segment (GtkTextLine *line,
3515 GtkTextLineSegment *seg;
3518 g_return_val_if_fail (line != NULL, NULL);
3520 offset = char_offset;
3521 seg = line->segments;
3523 while (offset > 0 && offset >= seg->char_count)
3525 g_assert (seg != NULL); /* means an invalid byte index */
3526 offset -= seg->char_count;
3531 *seg_offset = offset;
3537 _gtk_text_line_byte_to_char (GtkTextLine *line,
3541 GtkTextLineSegment *seg;
3543 g_return_val_if_fail (line != NULL, 0);
3544 g_return_val_if_fail (byte_offset >= 0, 0);
3547 seg = line->segments;
3548 while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3549 the next segment) */
3551 g_assert (seg != NULL); /* our byte_index was bogus if this happens */
3553 byte_offset -= seg->byte_count;
3554 char_offset += seg->char_count;
3559 g_assert (seg != NULL);
3561 /* Now byte_offset is the offset into the current segment,
3562 and char_offset is the start of the current segment.
3563 Optimize the case where no chars use > 1 byte */
3564 if (seg->byte_count == seg->char_count)
3565 return char_offset + byte_offset;
3568 if (seg->type == >k_text_char_type)
3569 return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3572 g_assert (seg->char_count == 1);
3573 g_assert (byte_offset == 0);
3581 _gtk_text_line_char_to_byte (GtkTextLine *line,
3584 g_warning ("FIXME not implemented");
3589 /* FIXME sync with char_locate (or figure out a clean
3590 way to merge the two functions) */
3592 _gtk_text_line_byte_locate (GtkTextLine *line,
3594 GtkTextLineSegment **segment,
3595 GtkTextLineSegment **any_segment,
3596 gint *seg_byte_offset,
3597 gint *line_byte_offset)
3599 GtkTextLineSegment *seg;
3600 GtkTextLineSegment *after_prev_indexable;
3601 GtkTextLineSegment *after_last_indexable;
3602 GtkTextLineSegment *last_indexable;
3606 g_return_val_if_fail (line != NULL, FALSE);
3607 g_return_val_if_fail (byte_offset >= 0, FALSE);
3610 *any_segment = NULL;
3613 offset = byte_offset;
3615 last_indexable = NULL;
3616 after_last_indexable = line->segments;
3617 after_prev_indexable = line->segments;
3618 seg = line->segments;
3620 /* The loop ends when we're inside a segment;
3621 last_indexable refers to the last segment
3622 we passed entirely. */
3623 while (seg && offset >= seg->byte_count)
3625 if (seg->char_count > 0)
3627 offset -= seg->byte_count;
3628 bytes_in_line += seg->byte_count;
3629 last_indexable = seg;
3630 after_prev_indexable = after_last_indexable;
3631 after_last_indexable = last_indexable->next;
3639 /* We went off the end of the line */
3641 g_warning ("%s: byte index off the end of the line", G_STRLOC);
3648 if (after_last_indexable != NULL)
3649 *any_segment = after_last_indexable;
3651 *any_segment = *segment;
3654 /* Override any_segment if we're in the middle of a segment. */
3656 *any_segment = *segment;
3658 *seg_byte_offset = offset;
3660 g_assert (*segment != NULL);
3661 g_assert (*any_segment != NULL);
3662 g_assert (*seg_byte_offset < (*segment)->byte_count);
3664 *line_byte_offset = bytes_in_line + *seg_byte_offset;
3669 /* FIXME sync with byte_locate (or figure out a clean
3670 way to merge the two functions) */
3672 _gtk_text_line_char_locate (GtkTextLine *line,
3674 GtkTextLineSegment **segment,
3675 GtkTextLineSegment **any_segment,
3676 gint *seg_char_offset,
3677 gint *line_char_offset)
3679 GtkTextLineSegment *seg;
3680 GtkTextLineSegment *after_prev_indexable;
3681 GtkTextLineSegment *after_last_indexable;
3682 GtkTextLineSegment *last_indexable;
3686 g_return_val_if_fail (line != NULL, FALSE);
3687 g_return_val_if_fail (char_offset >= 0, FALSE);
3690 *any_segment = NULL;
3693 offset = char_offset;
3695 last_indexable = NULL;
3696 after_last_indexable = line->segments;
3697 after_prev_indexable = line->segments;
3698 seg = line->segments;
3700 /* The loop ends when we're inside a segment;
3701 last_indexable refers to the last segment
3702 we passed entirely. */
3703 while (seg && offset >= seg->char_count)
3705 if (seg->char_count > 0)
3707 offset -= seg->char_count;
3708 chars_in_line += seg->char_count;
3709 last_indexable = seg;
3710 after_prev_indexable = after_last_indexable;
3711 after_last_indexable = last_indexable->next;
3719 /* end of the line */
3721 g_warning ("%s: char offset off the end of the line", G_STRLOC);
3728 if (after_last_indexable != NULL)
3729 *any_segment = after_last_indexable;
3731 *any_segment = *segment;
3734 /* Override any_segment if we're in the middle of a segment. */
3736 *any_segment = *segment;
3738 *seg_char_offset = offset;
3740 g_assert (*segment != NULL);
3741 g_assert (*any_segment != NULL);
3742 g_assert (*seg_char_offset < (*segment)->char_count);
3744 *line_char_offset = chars_in_line + *seg_char_offset;
3750 _gtk_text_line_byte_to_char_offsets (GtkTextLine *line,
3752 gint *line_char_offset,
3753 gint *seg_char_offset)
3755 GtkTextLineSegment *seg;
3758 g_return_if_fail (line != NULL);
3759 g_return_if_fail (byte_offset >= 0);
3761 *line_char_offset = 0;
3763 offset = byte_offset;
3764 seg = line->segments;
3766 while (offset >= seg->byte_count)
3768 offset -= seg->byte_count;
3769 *line_char_offset += seg->char_count;
3771 g_assert (seg != NULL); /* means an invalid char offset */
3774 g_assert (seg->char_count > 0); /* indexable. */
3776 /* offset is now the number of bytes into the current segment we
3777 * want to go. Count chars into the current segment.
3780 if (seg->type == >k_text_char_type)
3782 *seg_char_offset = g_utf8_strlen (seg->body.chars, offset);
3784 g_assert (*seg_char_offset < seg->char_count);
3786 *line_char_offset += *seg_char_offset;
3790 g_assert (offset == 0);
3791 *seg_char_offset = 0;
3796 _gtk_text_line_char_to_byte_offsets (GtkTextLine *line,
3798 gint *line_byte_offset,
3799 gint *seg_byte_offset)
3801 GtkTextLineSegment *seg;
3804 g_return_if_fail (line != NULL);
3805 g_return_if_fail (char_offset >= 0);
3807 *line_byte_offset = 0;
3809 offset = char_offset;
3810 seg = line->segments;
3812 while (offset >= seg->char_count)
3814 offset -= seg->char_count;
3815 *line_byte_offset += seg->byte_count;
3817 g_assert (seg != NULL); /* means an invalid char offset */
3820 g_assert (seg->char_count > 0); /* indexable. */
3822 /* offset is now the number of chars into the current segment we
3823 want to go. Count bytes into the current segment. */
3825 if (seg->type == >k_text_char_type)
3827 *seg_byte_offset = 0;
3831 const char * start = seg->body.chars + *seg_byte_offset;
3833 bytes = g_utf8_next_char (start) - start;
3834 *seg_byte_offset += bytes;
3838 g_assert (*seg_byte_offset < seg->byte_count);
3840 *line_byte_offset += *seg_byte_offset;
3844 g_assert (offset == 0);
3845 *seg_byte_offset = 0;
3850 node_compare (GtkTextBTreeNode *lhs,
3851 GtkTextBTreeNode *rhs)
3853 GtkTextBTreeNode *iter;
3854 GtkTextBTreeNode *node;
3855 GtkTextBTreeNode *common_parent;
3856 GtkTextBTreeNode *parent_of_lower;
3857 GtkTextBTreeNode *parent_of_higher;
3858 gboolean lhs_is_lower;
3859 GtkTextBTreeNode *lower;
3860 GtkTextBTreeNode *higher;
3862 /* This function assumes that lhs and rhs are not underneath each
3869 if (lhs->level < rhs->level)
3871 lhs_is_lower = TRUE;
3877 lhs_is_lower = FALSE;
3882 /* Algorithm: find common parent of lhs/rhs. Save the child nodes
3883 * of the common parent we used to reach the common parent; the
3884 * ordering of these child nodes in the child list is the ordering
3888 /* Get on the same level (may be on same level already) */
3890 while (node->level < higher->level)
3891 node = node->parent;
3893 g_assert (node->level == higher->level);
3895 g_assert (node != higher); /* Happens if lower is underneath higher */
3897 /* Go up until we have two children with a common parent.
3899 parent_of_lower = node;
3900 parent_of_higher = higher;
3902 while (parent_of_lower->parent != parent_of_higher->parent)
3904 parent_of_lower = parent_of_lower->parent;
3905 parent_of_higher = parent_of_higher->parent;
3908 g_assert (parent_of_lower->parent == parent_of_higher->parent);
3910 common_parent = parent_of_lower->parent;
3912 g_assert (common_parent != NULL);
3914 /* See which is first in the list of common_parent's children */
3915 iter = common_parent->children.node;
3916 while (iter != NULL)
3918 if (iter == parent_of_higher)
3920 /* higher is less than lower */
3923 return 1; /* lhs > rhs */
3927 else if (iter == parent_of_lower)
3929 /* lower is less than higher */
3932 return -1; /* lhs < rhs */
3940 g_assert_not_reached ();
3944 /* remember that tag == NULL means "any tag" */
3946 _gtk_text_line_next_could_contain_tag (GtkTextLine *line,
3950 GtkTextBTreeNode *node;
3951 GtkTextTagInfo *info;
3952 gboolean below_tag_root;
3954 g_return_val_if_fail (line != NULL, NULL);
3956 if (gtk_debug_flags & GTK_DEBUG_TEXT)
3957 _gtk_text_btree_check (tree);
3961 /* Right now we can only offer linear-search if the user wants
3962 * to know about any tag toggle at all.
3964 return _gtk_text_line_next (line);
3967 /* Our tag summaries only have node precision, not line
3968 precision. This means that if any line under a node could contain a
3969 tag, then any of the others could also contain a tag.
3971 In the future we could have some mechanism to keep track of how
3972 many toggles we've found under a node so far, since we have a
3973 count of toggles under the node. But for now I'm going with KISS.
3976 /* return same-node line, if any. */
3980 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3984 if (info->tag_root == NULL)
3987 if (info->tag_root == line->parent)
3988 return NULL; /* we were at the last line under the tag root */
3990 /* We need to go up out of this node, and on to the next one with
3991 toggles for the target tag. If we're below the tag root, we need to
3992 find the next node below the tag root that has tag summaries. If
3993 we're not below the tag root, we need to see if the tag root is
3994 after us in the tree, and if so, return the first line underneath
3997 node = line->parent;
3998 below_tag_root = FALSE;
3999 while (node != NULL)
4001 if (node == info->tag_root)
4003 below_tag_root = TRUE;
4007 node = node->parent;
4012 node = line->parent;
4013 while (node != info->tag_root)
4015 if (node->next == NULL)
4016 node = node->parent;
4021 if (gtk_text_btree_node_has_tag (node, tag))
4031 ordering = node_compare (line->parent, info->tag_root);
4035 /* Tag root is ahead of us, so search there. */
4036 node = info->tag_root;
4041 /* Tag root is after us, so no more lines that
4042 * could contain the tag.
4047 g_assert_not_reached ();
4052 g_assert (node != NULL);
4054 /* We have to find the first sub-node of this node that contains
4058 while (node->level > 0)
4060 g_assert (node != NULL); /* If this fails, it likely means an
4061 incorrect tag summary led us on a
4062 wild goose chase down this branch of
4064 node = node->children.node;
4065 while (node != NULL)
4067 if (gtk_text_btree_node_has_tag (node, tag))
4073 g_assert (node != NULL);
4074 g_assert (node->level == 0);
4076 return node->children.line;
4080 prev_line_under_node (GtkTextBTreeNode *node,
4085 prev = node->children.line;
4091 while (prev->next != line)
4101 _gtk_text_line_previous_could_contain_tag (GtkTextLine *line,
4105 GtkTextBTreeNode *node;
4106 GtkTextBTreeNode *found_node = NULL;
4107 GtkTextTagInfo *info;
4108 gboolean below_tag_root;
4110 GtkTextBTreeNode *line_ancestor;
4111 GtkTextBTreeNode *line_ancestor_parent;
4113 /* See next_could_contain_tag () for more extensive comments
4114 * on what's going on here.
4117 g_return_val_if_fail (line != NULL, NULL);
4119 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4120 _gtk_text_btree_check (tree);
4124 /* Right now we can only offer linear-search if the user wants
4125 * to know about any tag toggle at all.
4127 return _gtk_text_line_previous (line);
4130 /* Return same-node line, if any. */
4131 prev = prev_line_under_node (line->parent, line);
4135 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4139 if (info->tag_root == NULL)
4142 if (info->tag_root == line->parent)
4143 return NULL; /* we were at the first line under the tag root */
4145 /* Are we below the tag root */
4146 node = line->parent;
4147 below_tag_root = FALSE;
4148 while (node != NULL)
4150 if (node == info->tag_root)
4152 below_tag_root = TRUE;
4156 node = node->parent;
4161 /* Look for a previous node under this tag root that has our
4165 /* this assertion holds because line->parent is not the
4166 * tag root, we are below the tag root, and the tag
4169 g_assert (line->parent->parent != NULL);
4171 line_ancestor = line->parent;
4172 line_ancestor_parent = line->parent->parent;
4174 node = line_ancestor_parent->children.node;
4175 while (node != line_ancestor &&
4176 line_ancestor != info->tag_root)
4178 GSList *child_nodes = NULL;
4181 /* Create reverse-order list of nodes before
4184 while (node != line_ancestor
4187 child_nodes = g_slist_prepend (child_nodes, node);
4192 /* Try to find a node with our tag on it in the list */
4196 GtkTextBTreeNode *this_node = tmp->data;
4198 g_assert (this_node != line_ancestor);
4200 if (gtk_text_btree_node_has_tag (this_node, tag))
4202 found_node = this_node;
4203 g_slist_free (child_nodes);
4207 tmp = g_slist_next (tmp);
4210 g_slist_free (child_nodes);
4212 /* Didn't find anything on this level; go up one level. */
4213 line_ancestor = line_ancestor_parent;
4214 line_ancestor_parent = line_ancestor->parent;
4216 node = line_ancestor_parent->children.node;
4226 ordering = node_compare (line->parent, info->tag_root);
4230 /* Tag root is ahead of us, so no more lines
4237 /* Tag root is after us, so grab last tagged
4238 * line underneath the tag root.
4240 found_node = info->tag_root;
4244 g_assert_not_reached ();
4249 g_assert (found_node != NULL);
4251 /* We have to find the last sub-node of this node that contains
4256 while (node->level > 0)
4258 GSList *child_nodes = NULL;
4260 g_assert (node != NULL); /* If this fails, it likely means an
4261 incorrect tag summary led us on a
4262 wild goose chase down this branch of
4265 node = node->children.node;
4266 while (node != NULL)
4268 child_nodes = g_slist_prepend (child_nodes, node);
4272 node = NULL; /* detect failure to find a child node. */
4275 while (iter != NULL)
4277 if (gtk_text_btree_node_has_tag (iter->data, tag))
4279 /* recurse into this node. */
4284 iter = g_slist_next (iter);
4287 g_slist_free (child_nodes);
4289 g_assert (node != NULL);
4292 g_assert (node != NULL);
4293 g_assert (node->level == 0);
4295 /* this assertion is correct, but slow. */
4296 /* g_assert (node_compare (node, line->parent) < 0); */
4298 /* Return last line in this node. */
4300 prev = node->children.line;
4308 * Non-public function implementations
4312 summary_list_destroy (Summary *summary)
4315 while (summary != NULL)
4317 next = summary->next;
4318 summary_destroy (summary);
4324 get_last_line (GtkTextBTree *tree)
4326 if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
4332 n_lines = _gtk_text_btree_line_count (tree);
4334 g_assert (n_lines >= 1); /* num_lines doesn't return bogus last line. */
4336 line = _gtk_text_btree_get_line (tree, n_lines, &real_line);
4338 tree->end_iter_line_stamp = tree->chars_changed_stamp;
4339 tree->end_iter_line = line;
4342 return tree->end_iter_line;
4350 gtk_text_line_new (void)
4354 line = g_new0(GtkTextLine, 1);
4360 gtk_text_line_destroy (GtkTextBTree *tree, GtkTextLine *line)
4362 GtkTextLineData *ld;
4363 GtkTextLineData *next;
4365 g_return_if_fail (line != NULL);
4372 view = gtk_text_btree_get_view (tree, ld->view_id);
4374 g_assert (view != NULL);
4377 gtk_text_layout_free_line_data (view->layout, line, ld);
4386 gtk_text_line_set_parent (GtkTextLine *line,
4387 GtkTextBTreeNode *node)
4389 if (line->parent == node)
4391 line->parent = node;
4392 gtk_text_btree_node_invalidate_upward (node, NULL);
4396 cleanup_line (GtkTextLine *line)
4398 GtkTextLineSegment *seg, **prev_p;
4402 * Make a pass over all of the segments in the line, giving each
4403 * a chance to clean itself up. This could potentially change
4404 * the structure of the line, e.g. by merging two segments
4405 * together or having two segments cancel themselves; if so,
4406 * then repeat the whole process again, since the first structure
4407 * change might make other structure changes possible. Repeat
4408 * until eventually there are no changes.
4415 for (prev_p = &line->segments, seg = *prev_p;
4417 prev_p = &(*prev_p)->next, seg = *prev_p)
4419 if (seg->type->cleanupFunc != NULL)
4421 *prev_p = (*seg->type->cleanupFunc)(seg, line);
4434 node_data_new (gpointer view_id)
4438 nd = g_new (NodeData, 1);
4440 nd->view_id = view_id;
4450 node_data_destroy (NodeData *nd)
4456 node_data_list_destroy (NodeData *nd)
4462 while (iter != NULL)
4465 node_data_destroy (iter);
4471 node_data_find (NodeData *nd, gpointer view_id)
4475 if (nd->view_id == view_id)
4483 summary_destroy (Summary *summary)
4485 /* Fill with error-triggering garbage */
4486 summary->info = (void*)0x1;
4487 summary->toggle_count = 567;
4488 summary->next = (void*)0x1;
4492 static GtkTextBTreeNode*
4493 gtk_text_btree_node_new (void)
4495 GtkTextBTreeNode *node;
4497 node = g_new (GtkTextBTreeNode, 1);
4499 node->node_data = NULL;
4505 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
4506 GtkTextTagInfo *info,
4511 summary = node->summary;
4512 while (summary != NULL)
4514 if (summary->info == info)
4516 summary->toggle_count += adjust;
4520 summary = summary->next;
4523 if (summary == NULL)
4525 /* didn't find a summary for our tag. */
4526 g_return_if_fail (adjust > 0);
4527 summary = g_new (Summary, 1);
4528 summary->info = info;
4529 summary->toggle_count = adjust;
4530 summary->next = node->summary;
4531 node->summary = summary;
4535 /* Note that the tag root and above do not have summaries
4536 for the tag; only nodes below the tag root have
4539 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4543 summary = node->summary;
4544 while (summary != NULL)
4547 summary->info->tag == tag)
4550 summary = summary->next;
4556 /* Add node and all children to the damage region. */
4558 gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node)
4562 nd = node->node_data;
4569 if (node->level == 0)
4573 line = node->children.line;
4574 while (line != NULL)
4576 GtkTextLineData *ld;
4590 GtkTextBTreeNode *child;
4592 child = node->children.node;
4594 while (child != NULL)
4596 gtk_text_btree_node_invalidate_downward (child);
4598 child = child->next;
4604 gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node, gpointer view_id)
4606 GtkTextBTreeNode *iter;
4609 while (iter != NULL)
4615 nd = node_data_find (iter->node_data, view_id);
4617 if (nd == NULL || !nd->valid)
4618 break; /* Once a node is invalid, we know its parents are as well. */
4624 gboolean should_continue = FALSE;
4626 nd = iter->node_data;
4631 should_continue = TRUE;
4638 if (!should_continue)
4639 break; /* This node was totally invalidated, so are its
4643 iter = iter->parent;
4649 * _gtk_text_btree_is_valid:
4650 * @tree: a #GtkTextBTree
4651 * @view_id: ID for the view
4653 * Check to see if the entire #GtkTextBTree is valid or not for
4656 * Return value: %TRUE if the entire #GtkTextBTree is valid
4659 _gtk_text_btree_is_valid (GtkTextBTree *tree,
4663 g_return_val_if_fail (tree != NULL, FALSE);
4665 nd = node_data_find (tree->root_node->node_data, view_id);
4666 return (nd && nd->valid);
4669 typedef struct _ValidateState ValidateState;
4671 struct _ValidateState
4673 gint remaining_pixels;
4674 gboolean in_validation;
4681 gtk_text_btree_node_validate (BTreeView *view,
4682 GtkTextBTreeNode *node,
4684 ValidateState *state)
4686 gint node_valid = TRUE;
4687 gint node_width = 0;
4688 gint node_height = 0;
4690 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4691 g_return_if_fail (!nd->valid);
4693 if (node->level == 0)
4695 GtkTextLine *line = node->children.line;
4696 GtkTextLineData *ld;
4698 /* Iterate over leading valid lines */
4699 while (line != NULL)
4701 ld = _gtk_text_line_get_data (line, view_id);
4703 if (!ld || !ld->valid)
4705 else if (state->in_validation)
4707 state->in_validation = FALSE;
4712 state->y += ld->height;
4713 node_width = MAX (ld->width, node_width);
4714 node_height += ld->height;
4720 state->in_validation = TRUE;
4722 /* Iterate over invalid lines */
4723 while (line != NULL)
4725 ld = _gtk_text_line_get_data (line, view_id);
4727 if (ld && ld->valid)
4732 state->old_height += ld->height;
4733 ld = gtk_text_layout_wrap (view->layout, line, ld);
4734 state->new_height += ld->height;
4736 node_width = MAX (ld->width, node_width);
4737 node_height += ld->height;
4739 state->remaining_pixels -= ld->height;
4740 if (state->remaining_pixels <= 0)
4750 /* Iterate over the remaining lines */
4751 while (line != NULL)
4753 ld = _gtk_text_line_get_data (line, view_id);
4754 state->in_validation = FALSE;
4756 if (!ld || !ld->valid)
4761 node_width = MAX (ld->width, node_width);
4762 node_height += ld->height;
4770 GtkTextBTreeNode *child;
4773 child = node->children.node;
4775 /* Iterate over leading valid nodes */
4778 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4780 if (!child_nd->valid)
4782 else if (state->in_validation)
4784 state->in_validation = FALSE;
4789 state->y += child_nd->height;
4790 node_width = MAX (node_width, child_nd->width);
4791 node_height += child_nd->height;
4794 child = child->next;
4797 /* Iterate over invalid nodes */
4800 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4802 if (child_nd->valid)
4806 gtk_text_btree_node_validate (view, child, view_id, state);
4808 if (!child_nd->valid)
4810 node_width = MAX (node_width, child_nd->width);
4811 node_height += child_nd->height;
4813 if (!state->in_validation || state->remaining_pixels <= 0)
4815 child = child->next;
4820 child = child->next;
4823 /* Iterate over the remaining lines */
4826 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4827 state->in_validation = FALSE;
4829 if (!child_nd->valid)
4832 node_width = MAX (child_nd->width, node_width);
4833 node_height += child_nd->height;
4835 child = child->next;
4839 nd->width = node_width;
4840 nd->height = node_height;
4841 nd->valid = node_valid;
4845 * _gtk_text_btree_validate:
4846 * @tree: a #GtkTextBTree
4848 * @max_pixels: the maximum number of pixels to validate. (No more
4849 * than one paragraph beyond this limit will be validated)
4850 * @y: location to store starting y coordinate of validated region
4851 * @old_height: location to store old height of validated region
4852 * @new_height: location to store new height of validated region
4854 * Validate a single contiguous invalid region of a #GtkTextBTree for
4857 * Return value: %TRUE if a region has been validated, %FALSE if the
4858 * entire tree was already valid.
4861 _gtk_text_btree_validate (GtkTextBTree *tree,
4870 g_return_val_if_fail (tree != NULL, FALSE);
4872 view = gtk_text_btree_get_view (tree, view_id);
4873 g_return_val_if_fail (view != NULL, FALSE);
4875 if (!_gtk_text_btree_is_valid (tree, view_id))
4877 ValidateState state;
4879 state.remaining_pixels = max_pixels;
4880 state.in_validation = FALSE;
4882 state.old_height = 0;
4883 state.new_height = 0;
4885 gtk_text_btree_node_validate (view,
4892 *old_height = state.old_height;
4894 *new_height = state.new_height;
4896 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4897 _gtk_text_btree_check (tree);
4906 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
4910 gboolean *valid_out)
4914 gboolean valid = TRUE;
4916 if (node->level == 0)
4918 GtkTextLine *line = node->children.line;
4920 while (line != NULL)
4922 GtkTextLineData *ld = _gtk_text_line_get_data (line, view_id);
4924 if (!ld || !ld->valid)
4929 width = MAX (ld->width, width);
4930 height += ld->height;
4938 GtkTextBTreeNode *child = node->children.node;
4942 NodeData *child_nd = node_data_find (child->node_data, view_id);
4944 if (!child_nd || !child_nd->valid)
4949 width = MAX (child_nd->width, width);
4950 height += child_nd->height;
4953 child = child->next;
4958 *height_out = height;
4963 /* Recompute the validity and size of the view data for a given
4964 * view at this node from the immediate children of the node
4967 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
4970 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4975 gtk_text_btree_node_compute_view_aggregates (node, view_id,
4976 &width, &height, &valid);
4978 nd->height = height;
4985 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
4990 gtk_text_btree_node_check_valid (node, view_id);
4991 node = node->parent;
4996 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
4999 if (node->level == 0)
5001 return gtk_text_btree_node_check_valid (node, view_id);
5005 GtkTextBTreeNode *child = node->children.node;
5007 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5015 NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
5017 if (!child_nd->valid)
5019 nd->width = MAX (child_nd->width, nd->width);
5020 nd->height += child_nd->height;
5022 child = child->next;
5031 * _gtk_text_btree_validate_line:
5032 * @tree: a #GtkTextBTree
5033 * @line: line to validate
5034 * @view_id: view ID for the view to validate
5036 * Revalidate a single line of the btree for the given view, propagate
5037 * results up through the entire tree.
5040 _gtk_text_btree_validate_line (GtkTextBTree *tree,
5044 GtkTextLineData *ld;
5047 g_return_if_fail (tree != NULL);
5048 g_return_if_fail (line != NULL);
5050 view = gtk_text_btree_get_view (tree, view_id);
5051 g_return_if_fail (view != NULL);
5053 ld = _gtk_text_line_get_data (line, view_id);
5054 if (!ld || !ld->valid)
5056 ld = gtk_text_layout_wrap (view->layout, line, ld);
5058 gtk_text_btree_node_check_valid_upward (line->parent, view_id);
5063 gtk_text_btree_node_remove_view (BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
5065 if (node->level == 0)
5069 line = node->children.line;
5070 while (line != NULL)
5072 GtkTextLineData *ld;
5074 ld = _gtk_text_line_remove_data (line, view_id);
5077 gtk_text_layout_free_line_data (view->layout, line, ld);
5084 GtkTextBTreeNode *child;
5086 child = node->children.node;
5088 while (child != NULL)
5091 gtk_text_btree_node_remove_view (view, child, view_id);
5093 child = child->next;
5097 gtk_text_btree_node_remove_data (node, view_id);
5101 gtk_text_btree_node_destroy (GtkTextBTree *tree, GtkTextBTreeNode *node)
5103 if (node->level == 0)
5106 GtkTextLineSegment *seg;
5108 while (node->children.line != NULL)
5110 line = node->children.line;
5111 node->children.line = line->next;
5112 while (line->segments != NULL)
5114 seg = line->segments;
5115 line->segments = seg->next;
5117 if (GTK_IS_TEXT_MARK_SEGMENT (seg))
5119 /* Set the mark as deleted */
5120 seg->body.mark.tree = NULL;
5121 seg->body.mark.line = NULL;
5124 (*seg->type->deleteFunc) (seg, line, 1);
5126 gtk_text_line_destroy (tree, line);
5131 GtkTextBTreeNode *childPtr;
5133 while (node->children.node != NULL)
5135 childPtr = node->children.node;
5136 node->children.node = childPtr->next;
5137 gtk_text_btree_node_destroy (tree, childPtr);
5141 gtk_text_btree_node_free_empty (tree, node);
5145 gtk_text_btree_node_free_empty (GtkTextBTree *tree,
5146 GtkTextBTreeNode *node)
5148 g_return_if_fail ((node->level > 0 && node->children.node == NULL) ||
5149 (node->level == 0 && node->children.line == NULL));
5151 summary_list_destroy (node->summary);
5152 node_data_list_destroy (node->node_data);
5157 gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node, gpointer view_id)
5161 nd = node->node_data;
5164 if (nd->view_id == view_id)
5172 nd = node_data_new (view_id);
5174 if (node->node_data)
5175 nd->next = node->node_data;
5177 node->node_data = nd;
5184 gtk_text_btree_node_remove_data (GtkTextBTreeNode *node, gpointer view_id)
5190 nd = node->node_data;
5193 if (nd->view_id == view_id)
5204 prev->next = nd->next;
5206 if (node->node_data == nd)
5207 node->node_data = nd->next;
5211 node_data_destroy (nd);
5215 gtk_text_btree_node_get_size (GtkTextBTreeNode *node, gpointer view_id,
5216 gint *width, gint *height)
5220 g_return_if_fail (width != NULL);
5221 g_return_if_fail (height != NULL);
5223 nd = gtk_text_btree_node_ensure_data (node, view_id);
5228 *height = nd->height;
5231 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5232 * here isn't quite right, since for a lot of operations we want to
5233 * know which children of the common parent correspond to the two nodes
5234 * (e.g., when computing the order of two iters)
5236 static GtkTextBTreeNode *
5237 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5238 GtkTextBTreeNode *node2)
5240 while (node1->level < node2->level)
5241 node1 = node1->parent;
5242 while (node2->level < node1->level)
5243 node2 = node2->parent;
5244 while (node1 != node2)
5246 node1 = node1->parent;
5247 node2 = node2->parent;
5258 gtk_text_btree_get_view (GtkTextBTree *tree, gpointer view_id)
5263 while (view != NULL)
5265 if (view->view_id == view_id)
5274 get_tree_bounds (GtkTextBTree *tree,
5278 _gtk_text_btree_get_iter_at_line_char (tree, start, 0, 0);
5279 _gtk_text_btree_get_end_iter (tree, end);
5283 tag_changed_cb (GtkTextTagTable *table,
5285 gboolean size_changed,
5290 /* We need to queue a relayout on all regions that are tagged with
5297 if (_gtk_text_btree_get_iter_at_first_toggle (tree, &start, tag))
5299 /* Must be a last toggle if there was a first one. */
5300 _gtk_text_btree_get_iter_at_last_toggle (tree, &end, tag);
5301 _gtk_text_btree_invalidate_region (tree,
5308 /* We only need to queue a redraw, not a relayout */
5313 while (view != NULL)
5317 _gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5318 gtk_text_layout_changed (view->layout, 0, height, height);
5326 tag_removed_cb (GtkTextTagTable *table,
5330 /* Remove the tag from the tree */
5335 get_tree_bounds (tree, &start, &end);
5337 _gtk_text_btree_tag (&start, &end, tag, FALSE);
5338 gtk_text_btree_remove_tag_info (tree, tag);
5342 /* Rebalance the out-of-whack node "node" */
5344 gtk_text_btree_rebalance (GtkTextBTree *tree,
5345 GtkTextBTreeNode *node)
5348 * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5349 * up through the tree one GtkTextBTreeNode at a time until the root
5350 * GtkTextBTreeNode has been processed.
5353 while (node != NULL)
5355 GtkTextBTreeNode *new_node, *child;
5360 * Check to see if the GtkTextBTreeNode has too many children. If it does,
5361 * then split off all but the first MIN_CHILDREN into a separate
5362 * GtkTextBTreeNode following the original one. Then repeat until the
5363 * GtkTextBTreeNode has a decent size.
5366 if (node->num_children > MAX_CHILDREN)
5371 * If the GtkTextBTreeNode being split is the root
5372 * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5376 if (node->parent == NULL)
5378 new_node = gtk_text_btree_node_new ();
5379 new_node->parent = NULL;
5380 new_node->next = NULL;
5381 new_node->summary = NULL;
5382 new_node->level = node->level + 1;
5383 new_node->children.node = node;
5384 recompute_node_counts (tree, new_node);
5385 tree->root_node = new_node;
5387 new_node = gtk_text_btree_node_new ();
5388 new_node->parent = node->parent;
5389 new_node->next = node->next;
5390 node->next = new_node;
5391 new_node->summary = NULL;
5392 new_node->level = node->level;
5393 new_node->num_children = node->num_children - MIN_CHILDREN;
5394 if (node->level == 0)
5396 for (i = MIN_CHILDREN-1,
5397 line = node->children.line;
5398 i > 0; i--, line = line->next)
5400 /* Empty loop body. */
5402 new_node->children.line = line->next;
5407 for (i = MIN_CHILDREN-1,
5408 child = node->children.node;
5409 i > 0; i--, child = child->next)
5411 /* Empty loop body. */
5413 new_node->children.node = child->next;
5416 recompute_node_counts (tree, node);
5417 node->parent->num_children++;
5419 if (node->num_children <= MAX_CHILDREN)
5421 recompute_node_counts (tree, node);
5427 while (node->num_children < MIN_CHILDREN)
5429 GtkTextBTreeNode *other;
5430 GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5431 GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5432 int total_children, first_children, i;
5435 * Too few children for this GtkTextBTreeNode. If this is the root then,
5436 * it's OK for it to have less than MIN_CHILDREN children
5437 * as long as it's got at least two. If it has only one
5438 * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5439 * the tree and use its child as the new root.
5442 if (node->parent == NULL)
5444 if ((node->num_children == 1) && (node->level > 0))
5446 tree->root_node = node->children.node;
5447 tree->root_node->parent = NULL;
5449 node->children.node = NULL;
5450 gtk_text_btree_node_free_empty (tree, node);
5456 * Not the root. Make sure that there are siblings to
5460 if (node->parent->num_children < 2)
5462 gtk_text_btree_rebalance (tree, node->parent);
5467 * Find a sibling neighbor to borrow from, and arrange for
5468 * node to be the earlier of the pair.
5471 if (node->next == NULL)
5473 for (other = node->parent->children.node;
5474 other->next != node;
5475 other = other->next)
5477 /* Empty loop body. */
5484 * We're going to either merge the two siblings together
5485 * into one GtkTextBTreeNode or redivide the children among them to
5486 * balance their loads. As preparation, join their two
5487 * child lists into a single list and remember the half-way
5488 * point in the list.
5491 total_children = node->num_children + other->num_children;
5492 first_children = total_children/2;
5493 if (node->children.node == NULL)
5495 node->children = other->children;
5496 other->children.node = NULL;
5497 other->children.line = NULL;
5499 if (node->level == 0)
5503 for (line = node->children.line, i = 1;
5505 line = line->next, i++)
5507 if (i == first_children)
5512 line->next = other->children.line;
5513 while (i <= first_children)
5522 GtkTextBTreeNode *child;
5524 for (child = node->children.node, i = 1;
5525 child->next != NULL;
5526 child = child->next, i++)
5528 if (i <= first_children)
5530 if (i == first_children)
5532 halfwaynode = child;
5536 child->next = other->children.node;
5537 while (i <= first_children)
5539 halfwaynode = child;
5540 child = child->next;
5546 * If the two siblings can simply be merged together, do it.
5549 if (total_children <= MAX_CHILDREN)
5551 recompute_node_counts (tree, node);
5552 node->next = other->next;
5553 node->parent->num_children--;
5555 other->children.node = NULL;
5556 other->children.line = NULL;
5557 gtk_text_btree_node_free_empty (tree, other);
5562 * The siblings can't be merged, so just divide their
5563 * children evenly between them.
5566 if (node->level == 0)
5568 other->children.line = halfwayline->next;
5569 halfwayline->next = NULL;
5573 other->children.node = halfwaynode->next;
5574 halfwaynode->next = NULL;
5577 recompute_node_counts (tree, node);
5578 recompute_node_counts (tree, other);
5581 node = node->parent;
5586 post_insert_fixup (GtkTextBTree *tree,
5588 gint line_count_delta,
5589 gint char_count_delta)
5592 GtkTextBTreeNode *node;
5595 * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5596 * point, then rebalance the tree if necessary.
5599 for (node = line->parent ; node != NULL;
5600 node = node->parent)
5602 node->num_lines += line_count_delta;
5603 node->num_chars += char_count_delta;
5605 node = line->parent;
5606 node->num_children += line_count_delta;
5608 if (node->num_children > MAX_CHILDREN)
5610 gtk_text_btree_rebalance (tree, node);
5613 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5614 _gtk_text_btree_check (tree);
5617 static GtkTextTagInfo*
5618 gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
5621 GtkTextTagInfo *info;
5625 list = tree->tag_infos;
5626 while (list != NULL)
5629 if (info->tag == tag)
5632 list = g_slist_next (list);
5638 static GtkTextTagInfo*
5639 gtk_text_btree_get_tag_info (GtkTextBTree *tree,
5642 GtkTextTagInfo *info;
5644 info = gtk_text_btree_get_existing_tag_info (tree, tag);
5648 /* didn't find it, create. */
5650 info = g_new (GtkTextTagInfo, 1);
5653 g_object_ref (G_OBJECT (tag));
5654 info->tag_root = NULL;
5655 info->toggle_count = 0;
5657 tree->tag_infos = g_slist_prepend (tree->tag_infos, info);
5664 gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
5667 GtkTextTagInfo *info;
5672 list = tree->tag_infos;
5673 while (list != NULL)
5676 if (info->tag == tag)
5680 prev->next = list->next;
5684 tree->tag_infos = list->next;
5687 g_slist_free (list);
5689 g_object_unref (G_OBJECT (info->tag));
5695 list = g_slist_next (list);
5698 g_assert_not_reached ();
5703 recompute_level_zero_counts (GtkTextBTreeNode *node)
5706 GtkTextLineSegment *seg;
5708 g_assert (node->level == 0);
5710 line = node->children.line;
5711 while (line != NULL)
5713 node->num_children++;
5716 if (line->parent != node)
5717 gtk_text_line_set_parent (line, node);
5719 seg = line->segments;
5723 node->num_chars += seg->char_count;
5725 if (((seg->type != >k_text_toggle_on_type)
5726 && (seg->type != >k_text_toggle_off_type))
5727 || !(seg->body.toggle.inNodeCounts))
5733 GtkTextTagInfo *info;
5735 info = seg->body.toggle.info;
5737 gtk_text_btree_node_adjust_toggle_count (node, info, 1);
5748 recompute_level_nonzero_counts (GtkTextBTreeNode *node)
5751 GtkTextBTreeNode *child;
5753 g_assert (node->level > 0);
5755 child = node->children.node;
5756 while (child != NULL)
5758 node->num_children += 1;
5759 node->num_lines += child->num_lines;
5760 node->num_chars += child->num_chars;
5762 if (child->parent != node)
5764 child->parent = node;
5765 gtk_text_btree_node_invalidate_upward (node, NULL);
5768 summary = child->summary;
5769 while (summary != NULL)
5771 gtk_text_btree_node_adjust_toggle_count (node,
5773 summary->toggle_count);
5775 summary = summary->next;
5778 child = child->next;
5783 *----------------------------------------------------------------------
5785 * recompute_node_counts --
5787 * This procedure is called to recompute all the counts in a GtkTextBTreeNode
5788 * (tags, child information, etc.) by scanning the information in
5789 * its descendants. This procedure is called during rebalancing
5790 * when a GtkTextBTreeNode's child structure has changed.
5796 * The tag counts for node are modified to reflect its current
5797 * child structure, as are its num_children, num_lines, num_chars fields.
5798 * Also, all of the childrens' parent fields are made to point
5801 *----------------------------------------------------------------------
5805 recompute_node_counts (GtkTextBTree *tree, GtkTextBTreeNode *node)
5808 Summary *summary, *summary2;
5811 * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
5812 * the existing Summary records (most of them will probably be reused).
5815 summary = node->summary;
5816 while (summary != NULL)
5818 summary->toggle_count = 0;
5819 summary = summary->next;
5822 node->num_children = 0;
5823 node->num_lines = 0;
5824 node->num_chars = 0;
5827 * Scan through the children, adding the childrens' tag counts into
5828 * the GtkTextBTreeNode's tag counts and adding new Summary structures if
5832 if (node->level == 0)
5833 recompute_level_zero_counts (node);
5835 recompute_level_nonzero_counts (node);
5840 gtk_text_btree_node_check_valid (node, view->view_id);
5845 * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
5846 * records that still have a zero count, or that have all the toggles.
5847 * The GtkTextBTreeNode with the children that account for all the tags toggles
5848 * have no summary information, and they become the tag_root for the tag.
5852 for (summary = node->summary; summary != NULL; )
5854 if (summary->toggle_count > 0 &&
5855 summary->toggle_count < summary->info->toggle_count)
5857 if (node->level == summary->info->tag_root->level)
5860 * The tag's root GtkTextBTreeNode split and some toggles left.
5861 * The tag root must move up a level.
5863 summary->info->tag_root = node->parent;
5866 summary = summary->next;
5869 if (summary->toggle_count == summary->info->toggle_count)
5872 * A GtkTextBTreeNode merge has collected all the toggles under
5873 * one GtkTextBTreeNode. Push the root down to this level.
5875 summary->info->tag_root = node;
5877 if (summary2 != NULL)
5879 summary2->next = summary->next;
5880 summary_destroy (summary);
5881 summary = summary2->next;
5885 node->summary = summary->next;
5886 summary_destroy (summary);
5887 summary = node->summary;
5893 _gtk_change_node_toggle_count (GtkTextBTreeNode *node,
5894 GtkTextTagInfo *info,
5895 gint delta) /* may be negative */
5897 Summary *summary, *prevPtr;
5898 GtkTextBTreeNode *node2Ptr;
5899 int rootLevel; /* Level of original tag root */
5901 info->toggle_count += delta;
5903 if (info->tag_root == (GtkTextBTreeNode *) NULL)
5905 info->tag_root = node;
5910 * Note the level of the existing root for the tag so we can detect
5911 * if it needs to be moved because of the toggle count change.
5914 rootLevel = info->tag_root->level;
5917 * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
5918 * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
5922 for ( ; node != info->tag_root; node = node->parent)
5925 * See if there's already an entry for this tag for this GtkTextBTreeNode. If so,
5926 * perhaps all we have to do is adjust its count.
5929 for (prevPtr = NULL, summary = node->summary;
5931 prevPtr = summary, summary = summary->next)
5933 if (summary->info == info)
5938 if (summary != NULL)
5940 summary->toggle_count += delta;
5941 if (summary->toggle_count > 0 &&
5942 summary->toggle_count < info->toggle_count)
5946 if (summary->toggle_count != 0)
5949 * Should never find a GtkTextBTreeNode with max toggle count at this
5950 * point (there shouldn't have been a summary entry in the
5954 g_error ("%s: bad toggle count (%d) max (%d)",
5955 G_STRLOC, summary->toggle_count, info->toggle_count);
5959 * Zero toggle count; must remove this tag from the list.
5962 if (prevPtr == NULL)
5964 node->summary = summary->next;
5968 prevPtr->next = summary->next;
5970 summary_destroy (summary);
5975 * This tag isn't currently in the summary information list.
5978 if (rootLevel == node->level)
5982 * The old tag root is at the same level in the tree as this
5983 * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode. Move the tag root up
5984 * a level, in the hopes that it will now cover this GtkTextBTreeNode
5985 * as well as the old root (if not, we'll move it up again
5986 * the next time through the loop). To push it up one level
5987 * we copy the original toggle count into the summary
5988 * information at the old root and change the root to its
5989 * parent GtkTextBTreeNode.
5992 GtkTextBTreeNode *rootnode = info->tag_root;
5993 summary = (Summary *) g_malloc (sizeof (Summary));
5994 summary->info = info;
5995 summary->toggle_count = info->toggle_count - delta;
5996 summary->next = rootnode->summary;
5997 rootnode->summary = summary;
5998 rootnode = rootnode->parent;
5999 rootLevel = rootnode->level;
6000 info->tag_root = rootnode;
6002 summary = (Summary *) g_malloc (sizeof (Summary));
6003 summary->info = info;
6004 summary->toggle_count = delta;
6005 summary->next = node->summary;
6006 node->summary = summary;
6011 * If we've decremented the toggle count, then it may be necessary
6012 * to push the tag root down one or more levels.
6019 if (info->toggle_count == 0)
6021 info->tag_root = (GtkTextBTreeNode *) NULL;
6024 node = info->tag_root;
6025 while (node->level > 0)
6028 * See if a single child GtkTextBTreeNode accounts for all of the tag's
6029 * toggles. If so, push the root down one level.
6032 for (node2Ptr = node->children.node;
6033 node2Ptr != (GtkTextBTreeNode *)NULL ;
6034 node2Ptr = node2Ptr->next)
6036 for (prevPtr = NULL, summary = node2Ptr->summary;
6038 prevPtr = summary, summary = summary->next)
6040 if (summary->info == info)
6045 if (summary == NULL)
6049 if (summary->toggle_count != info->toggle_count)
6052 * No GtkTextBTreeNode has all toggles, so the root is still valid.
6059 * This GtkTextBTreeNode has all the toggles, so push down the root.
6062 if (prevPtr == NULL)
6064 node2Ptr->summary = summary->next;
6068 prevPtr->next = summary->next;
6070 summary_destroy (summary);
6071 info->tag_root = node2Ptr;
6074 node = info->tag_root;
6079 *----------------------------------------------------------------------
6083 * This is a utility procedure used by _gtk_text_btree_get_tags. It
6084 * increments the count for a particular tag, adding a new
6085 * entry for that tag if there wasn't one previously.
6091 * The information at *tagInfoPtr may be modified, and the arrays
6092 * may be reallocated to make them larger.
6094 *----------------------------------------------------------------------
6098 inc_count (GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
6103 for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
6104 count > 0; tag_p++, count--)
6108 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
6114 * There isn't currently an entry for this tag, so we have to
6115 * make a new one. If the arrays are full, then enlarge the
6119 if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
6121 GtkTextTag **newTags;
6122 int *newCounts, newSize;
6124 newSize = 2*tagInfoPtr->arraySize;
6125 newTags = (GtkTextTag **) g_malloc ((unsigned)
6126 (newSize*sizeof (GtkTextTag *)));
6127 memcpy ((void *) newTags, (void *) tagInfoPtr->tags,
6128 tagInfoPtr->arraySize *sizeof (GtkTextTag *));
6129 g_free ((char *) tagInfoPtr->tags);
6130 tagInfoPtr->tags = newTags;
6131 newCounts = (int *) g_malloc ((unsigned) (newSize*sizeof (int)));
6132 memcpy ((void *) newCounts, (void *) tagInfoPtr->counts,
6133 tagInfoPtr->arraySize *sizeof (int));
6134 g_free ((char *) tagInfoPtr->counts);
6135 tagInfoPtr->counts = newCounts;
6136 tagInfoPtr->arraySize = newSize;
6139 tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
6140 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
6141 tagInfoPtr->numTags++;
6145 gtk_text_btree_link_segment (GtkTextLineSegment *seg,
6146 const GtkTextIter *iter)
6148 GtkTextLineSegment *prev;
6152 line = _gtk_text_iter_get_text_line (iter);
6153 tree = _gtk_text_iter_get_btree (iter);
6155 prev = gtk_text_line_segment_split (iter);
6158 seg->next = line->segments;
6159 line->segments = seg;
6163 seg->next = prev->next;
6166 cleanup_line (line);
6167 segments_changed (tree);
6169 if (gtk_debug_flags & GTK_DEBUG_TEXT)
6170 _gtk_text_btree_check (tree);
6174 gtk_text_btree_unlink_segment (GtkTextBTree *tree,
6175 GtkTextLineSegment *seg,
6178 GtkTextLineSegment *prev;
6180 if (line->segments == seg)
6182 line->segments = seg->next;
6186 for (prev = line->segments; prev->next != seg;
6189 /* Empty loop body. */
6191 prev->next = seg->next;
6193 cleanup_line (line);
6194 segments_changed (tree);
6198 * This is here because it requires BTree internals, it logically
6199 * belongs in gtktextsegment.c
6204 *--------------------------------------------------------------
6206 * _gtk_toggle_segment_check_func --
6208 * This procedure is invoked to perform consistency checks
6209 * on toggle segments.
6215 * If a consistency problem is found the procedure g_errors.
6217 *--------------------------------------------------------------
6221 _gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6227 if (segPtr->byte_count != 0)
6229 g_error ("toggle_segment_check_func: segment had non-zero size");
6231 if (!segPtr->body.toggle.inNodeCounts)
6233 g_error ("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6235 needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6236 for (summary = line->parent->summary; ;
6237 summary = summary->next)
6239 if (summary == NULL)
6243 g_error ("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6250 if (summary->info == segPtr->body.toggle.info)
6254 g_error ("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6266 gtk_text_btree_node_view_check_consistency (GtkTextBTree *tree,
6267 GtkTextBTreeNode *node,
6277 while (view != NULL)
6279 if (view->view_id == nd->view_id)
6286 g_error ("Node has data for a view %p no longer attached to the tree",
6289 gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6290 &width, &height, &valid);
6291 if (nd->width != width ||
6292 nd->height != height ||
6293 !nd->valid != !valid)
6295 g_error ("Node aggregates for view %p are invalid:\n"
6296 "Are (%d,%d,%s), should be (%d,%d,%s)",
6298 nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6299 width, height, valid ? "TRUE" : "FALSE");
6304 gtk_text_btree_node_check_consistency (GtkTextBTree *tree,
6305 GtkTextBTreeNode *node)
6307 GtkTextBTreeNode *childnode;
6308 Summary *summary, *summary2;
6310 GtkTextLineSegment *segPtr;
6311 int num_children, num_lines, num_chars, toggle_count, min_children;
6312 GtkTextLineData *ld;
6315 if (node->parent != NULL)
6317 min_children = MIN_CHILDREN;
6319 else if (node->level > 0)
6326 if ((node->num_children < min_children)
6327 || (node->num_children > MAX_CHILDREN))
6329 g_error ("gtk_text_btree_node_check_consistency: bad child count (%d)",
6330 node->num_children);
6333 nd = node->node_data;
6336 gtk_text_btree_node_view_check_consistency (tree, node, nd);
6343 if (node->level == 0)
6345 for (line = node->children.line; line != NULL;
6348 if (line->parent != node)
6350 g_error ("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6352 if (line->segments == NULL)
6354 g_error ("gtk_text_btree_node_check_consistency: line has no segments");
6360 /* Just ensuring we don't segv while doing this loop */
6365 for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6367 if (segPtr->type->checkFunc != NULL)
6369 (*segPtr->type->checkFunc)(segPtr, line);
6371 if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6372 && (segPtr->next != NULL)
6373 && (segPtr->next->byte_count == 0)
6374 && (segPtr->next->type->leftGravity))
6376 g_error ("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6378 if ((segPtr->next == NULL)
6379 && (segPtr->type != >k_text_char_type))
6381 g_error ("gtk_text_btree_node_check_consistency: line ended with wrong type");
6384 num_chars += segPtr->char_count;
6393 for (childnode = node->children.node; childnode != NULL;
6394 childnode = childnode->next)
6396 if (childnode->parent != node)
6398 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6400 if (childnode->level != (node->level-1))
6402 g_error ("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6403 node->level, childnode->level);
6405 gtk_text_btree_node_check_consistency (tree, childnode);
6406 for (summary = childnode->summary; summary != NULL;
6407 summary = summary->next)
6409 for (summary2 = node->summary; ;
6410 summary2 = summary2->next)
6412 if (summary2 == NULL)
6414 if (summary->info->tag_root == node)
6418 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6419 summary->info->tag->name,
6420 "present in parent summaries");
6422 if (summary->info == summary2->info)
6429 num_lines += childnode->num_lines;
6430 num_chars += childnode->num_chars;
6433 if (num_children != node->num_children)
6435 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6436 num_children, node->num_children);
6438 if (num_lines != node->num_lines)
6440 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6441 num_lines, node->num_lines);
6443 if (num_chars != node->num_chars)
6445 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6446 num_chars, node->num_chars);
6449 for (summary = node->summary; summary != NULL;
6450 summary = summary->next)
6452 if (summary->info->toggle_count == summary->toggle_count)
6454 g_error ("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6455 summary->info->tag->name);
6458 if (node->level == 0)
6460 for (line = node->children.line; line != NULL;
6463 for (segPtr = line->segments; segPtr != NULL;
6464 segPtr = segPtr->next)
6466 if ((segPtr->type != >k_text_toggle_on_type)
6467 && (segPtr->type != >k_text_toggle_off_type))
6471 if (segPtr->body.toggle.info == summary->info)
6473 if (!segPtr->body.toggle.inNodeCounts)
6474 g_error ("Toggle segment not in the node counts");
6483 for (childnode = node->children.node;
6485 childnode = childnode->next)
6487 for (summary2 = childnode->summary;
6489 summary2 = summary2->next)
6491 if (summary2->info == summary->info)
6493 toggle_count += summary2->toggle_count;
6498 if (toggle_count != summary->toggle_count)
6500 g_error ("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6501 toggle_count, summary->toggle_count);
6503 for (summary2 = summary->next; summary2 != NULL;
6504 summary2 = summary2->next)
6506 if (summary2->info == summary->info)
6508 g_error ("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6509 summary->info->tag->name);
6516 listify_foreach (GtkTextTag *tag, gpointer user_data)
6518 GSList** listp = user_data;
6520 *listp = g_slist_prepend (*listp, tag);
6524 list_of_tags (GtkTextTagTable *table)
6526 GSList *list = NULL;
6528 gtk_text_tag_table_foreach (table, listify_foreach, &list);
6534 _gtk_text_btree_check (GtkTextBTree *tree)
6537 GtkTextBTreeNode *node;
6539 GtkTextLineSegment *seg;
6541 GSList *taglist = NULL;
6543 GtkTextTagInfo *info;
6546 * Make sure that the tag toggle counts and the tag root pointers are OK.
6548 for (taglist = list_of_tags (tree->table);
6549 taglist != NULL ; taglist = taglist->next)
6551 tag = taglist->data;
6552 info = gtk_text_btree_get_existing_tag_info (tree, tag);
6555 node = info->tag_root;
6558 if (info->toggle_count != 0)
6560 g_error ("_gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6561 tag->name, info->toggle_count);
6563 continue; /* no ranges for the tag */
6565 else if (info->toggle_count == 0)
6567 g_error ("_gtk_text_btree_check found root for \"%s\" with no toggles",
6570 else if (info->toggle_count & 1)
6572 g_error ("_gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6573 tag->name, info->toggle_count);
6575 for (summary = node->summary; summary != NULL;
6576 summary = summary->next)
6578 if (summary->info->tag == tag)
6580 g_error ("_gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6584 if (node->level > 0)
6586 for (node = node->children.node ; node != NULL ;
6589 for (summary = node->summary; summary != NULL;
6590 summary = summary->next)
6592 if (summary->info->tag == tag)
6594 count += summary->toggle_count;
6601 GtkTextLineSegmentClass * last = NULL;
6603 for (line = node->children.line ; line != NULL ;
6606 for (seg = line->segments; seg != NULL;
6609 if ((seg->type == >k_text_toggle_on_type ||
6610 seg->type == >k_text_toggle_off_type) &&
6611 seg->body.toggle.info->tag == tag)
6613 if (last == seg->type)
6614 g_error ("Two consecutive toggles on or off weren't merged");
6615 if (!seg->body.toggle.inNodeCounts)
6616 g_error ("Toggle segment not in the node counts");
6625 if (count != info->toggle_count)
6627 g_error ("_gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
6628 info->toggle_count, tag->name, count);
6633 g_slist_free (taglist);
6637 * Call a recursive procedure to do the main body of checks.
6640 node = tree->root_node;
6641 gtk_text_btree_node_check_consistency (tree, tree->root_node);
6644 * Make sure that there are at least two lines in the text and
6645 * that the last line has no characters except a newline.
6648 if (node->num_lines < 2)
6650 g_error ("_gtk_text_btree_check: less than 2 lines in tree");
6652 if (node->num_chars < 2)
6654 g_error ("_gtk_text_btree_check: less than 2 chars in tree");
6656 while (node->level > 0)
6658 node = node->children.node;
6659 while (node->next != NULL)
6664 line = node->children.line;
6665 while (line->next != NULL)
6669 seg = line->segments;
6670 while ((seg->type == >k_text_toggle_off_type)
6671 || (seg->type == >k_text_right_mark_type)
6672 || (seg->type == >k_text_left_mark_type))
6675 * It's OK to toggle a tag off in the last line, but
6676 * not to start a new range. It's also OK to have marks
6682 if (seg->type != >k_text_char_type)
6684 g_error ("_gtk_text_btree_check: last line has bogus segment type");
6686 if (seg->next != NULL)
6688 g_error ("_gtk_text_btree_check: last line has too many segments");
6690 if (seg->byte_count != 1)
6692 g_error ("_gtk_text_btree_check: last line has wrong # characters: %d",
6695 if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
6697 g_error ("_gtk_text_btree_check: last line had bad value: %s",
6702 void _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line);
6703 void _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment* seg);
6704 void _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent);
6705 void _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
6708 _gtk_text_btree_spew (GtkTextBTree *tree)
6713 printf ("%d lines in tree %p\n",
6714 _gtk_text_btree_line_count (tree), tree);
6716 line = _gtk_text_btree_get_line (tree, 0, &real_line);
6718 while (line != NULL)
6720 _gtk_text_btree_spew_line (tree, line);
6721 line = _gtk_text_line_next (line);
6724 printf ("=================== Tag information\n");
6729 list = tree->tag_infos;
6731 while (list != NULL)
6733 GtkTextTagInfo *info;
6737 printf (" tag `%s': root at %p, toggle count %d\n",
6738 info->tag->name, info->tag_root, info->toggle_count);
6740 list = g_slist_next (list);
6743 if (tree->tag_infos == NULL)
6745 printf (" (no tags in the tree)\n");
6749 printf ("=================== Tree nodes\n");
6752 _gtk_text_btree_spew_node (tree->root_node, 0);
6757 _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
6760 GtkTextLineSegment *seg;
6762 spaces = g_strnfill (indent, ' ');
6764 printf ("%sline %p chars %d bytes %d\n",
6766 _gtk_text_line_char_count (line),
6767 _gtk_text_line_byte_count (line));
6769 seg = line->segments;
6772 if (seg->type == >k_text_char_type)
6774 gchar* str = g_strndup (seg->body.chars, MIN (seg->byte_count, 10));
6779 if (*s == '\n' || *s == '\r')
6783 printf ("%s chars `%s'...\n", spaces, str);
6786 else if (seg->type == >k_text_right_mark_type)
6788 printf ("%s right mark `%s' visible: %d\n",
6790 seg->body.mark.name,
6791 seg->body.mark.visible);
6793 else if (seg->type == >k_text_left_mark_type)
6795 printf ("%s left mark `%s' visible: %d\n",
6797 seg->body.mark.name,
6798 seg->body.mark.visible);
6800 else if (seg->type == >k_text_toggle_on_type ||
6801 seg->type == >k_text_toggle_off_type)
6803 printf ("%s tag `%s' %s\n",
6804 spaces, seg->body.toggle.info->tag->name,
6805 seg->type == >k_text_toggle_off_type ? "off" : "on");
6815 _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent)
6818 GtkTextBTreeNode *iter;
6821 spaces = g_strnfill (indent, ' ');
6823 printf ("%snode %p level %d children %d lines %d chars %d\n",
6824 spaces, node, node->level,
6825 node->num_children, node->num_lines, node->num_chars);
6830 printf ("%s %d toggles of `%s' below this node\n",
6831 spaces, s->toggle_count, s->info->tag->name);
6837 if (node->level > 0)
6839 iter = node->children.node;
6840 while (iter != NULL)
6842 _gtk_text_btree_spew_node (iter, indent + 2);
6849 GtkTextLine *line = node->children.line;
6850 while (line != NULL)
6852 _gtk_text_btree_spew_line_short (line, indent + 2);
6860 _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line)
6862 GtkTextLineSegment * seg;
6864 printf ("%4d| line: %p parent: %p next: %p\n",
6865 _gtk_text_line_get_number (line), line, line->parent, line->next);
6867 seg = line->segments;
6871 _gtk_text_btree_spew_segment (tree, seg);
6877 _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment * seg)
6879 printf (" segment: %p type: %s bytes: %d chars: %d\n",
6880 seg, seg->type->name, seg->byte_count, seg->char_count);
6882 if (seg->type == >k_text_char_type)
6884 gchar* str = g_strndup (seg->body.chars, seg->byte_count);
6885 printf (" `%s'\n", str);
6888 else if (seg->type == >k_text_right_mark_type)
6890 printf (" right mark `%s' visible: %d not_deleteable: %d\n",
6891 seg->body.mark.name,
6892 seg->body.mark.visible,
6893 seg->body.mark.not_deleteable);
6895 else if (seg->type == >k_text_left_mark_type)
6897 printf (" left mark `%s' visible: %d not_deleteable: %d\n",
6898 seg->body.mark.name,
6899 seg->body.mark.visible,
6900 seg->body.mark.not_deleteable);
6902 else if (seg->type == >k_text_toggle_on_type ||
6903 seg->type == >k_text_toggle_off_type)
6905 printf (" tag `%s' priority %d\n",
6906 seg->body.toggle.info->tag->name,
6907 seg->body.toggle.info->tag->priority);