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 #define GTK_TEXT_USE_INTERNAL_UNSUPPORTED_API
57 #include "gtktextbtree.h"
61 #include "gtktexttag.h"
62 #include "gtktexttagtable.h"
63 #include "gtktextlayout.h"
64 #include "gtktextiterprivate.h"
66 #include "gtktextmarkprivate.h"
75 * The structure below is used to pass information between
76 * _gtk_text_btree_get_tags and inc_count:
79 typedef struct TagInfo {
80 int numTags; /* Number of tags for which there
81 * is currently information in
83 int arraySize; /* Number of entries allocated for
85 GtkTextTag **tags; /* Array of tags seen so far.
87 int *counts; /* Toggle count (so far) for each
88 * entry in tags. Malloc-ed. */
93 * This is used to store per-view width/height info at the tree nodes.
96 typedef struct _NodeData NodeData;
102 /* Height and width of this node */
104 signed int width : 24;
106 /* boolean indicating whether the lines below this node are in need of validation.
107 * However, width/height should always represent the current total width and
108 * max height for lines below this node; the valid flag indicates whether the
109 * width/height on the lines needs recomputing, not whether the totals
112 guint valid : 8; /* Actually a boolean */
117 * The data structure below keeps summary information about one tag as part
118 * of the tag information in a node.
121 typedef struct Summary {
122 GtkTextTagInfo *info; /* Handle for tag. */
123 int toggle_count; /* Number of transitions into or
124 * out of this tag that occur in
125 * the subtree rooted at this node. */
126 struct Summary *next; /* Next in list of all tags for same
127 * node, or NULL if at end of list. */
131 * The data structure below defines a node in the B-tree.
134 struct _GtkTextBTreeNode {
135 GtkTextBTreeNode *parent; /* Pointer to parent node, or NULL if
136 * this is the root. */
137 GtkTextBTreeNode *next; /* Next in list of siblings with the
138 * same parent node, or NULL for end
140 Summary *summary; /* First in malloc-ed list of info
141 * about tags in this subtree (NULL if
142 * no tag info in the subtree). */
143 int level; /* Level of this node in the B-tree.
144 * 0 refers to the bottom of the tree
145 * (children are lines, not nodes). */
146 union { /* First in linked list of children. */
147 struct _GtkTextBTreeNode *node; /* Used if level > 0. */
148 GtkTextLine *line; /* Used if level == 0. */
150 int num_children; /* Number of children of this node. */
151 int num_lines; /* Total number of lines (leaves) in
152 * the subtree rooted here. */
153 int num_chars; /* Number of chars below here */
160 * Used to store the list of views in our btree
163 typedef struct _BTreeView BTreeView;
167 GtkTextLayout *layout;
173 * And the tree itself
176 struct _GtkTextBTree {
177 GtkTextBTreeNode *root_node; /* Pointer to root of B-tree. */
178 GtkTextTagTable *table;
179 GHashTable *mark_table;
181 GtkTextMark *insert_mark;
182 GtkTextMark *selection_bound_mark;
183 GtkTextBuffer *buffer;
186 gulong tag_changed_handler;
188 /* Incremented when a segment with a byte size > 0
189 * is added to or removed from the tree (i.e. the
190 * length of a line may have changed, and lines may
191 * have been added or removed). This invalidates
192 * all outstanding iterators.
194 guint chars_changed_stamp;
195 /* Incremented when any segments are added or deleted;
196 * this makes outstanding iterators recalculate their
197 * pointed-to segment and segment offset.
199 guint segments_changed_stamp;
201 /* Cache the last line in the buffer */
202 GtkTextLine *last_line;
203 guint last_line_stamp;
205 /* Cache the next-to-last line in the buffer,
206 * containing the end iterator
208 GtkTextLine *end_iter_line;
209 GtkTextLineSegment *end_iter_segment;
210 int end_iter_segment_byte_index;
211 int end_iter_segment_char_offset;
212 guint end_iter_line_stamp;
213 guint end_iter_segment_stamp;
215 GHashTable *child_anchor_table;
220 * Upper and lower bounds on how many children a node may have:
221 * rebalance when either of these limits is exceeded. MAX_CHILDREN
222 * should be twice MIN_CHILDREN and MIN_CHILDREN must be >= 2.
225 /* Tk used MAX of 12 and MIN of 6. This makes the tree wide and
226 shallow. It appears to be faster to locate a particular line number
227 if the tree is narrow and deep, since it is more finely sorted. I
228 guess this may increase memory use though, and make it slower to
229 walk the tree in order, or locate a particular byte index (which
230 is done by walking the tree in order).
232 There's basically a tradeoff here. However I'm thinking we want to
233 add pixels, byte counts, and char counts to the tree nodes,
234 at that point narrow and deep should speed up all operations,
235 not just the line number searches.
239 #define MAX_CHILDREN 12
240 #define MIN_CHILDREN 6
242 #define MAX_CHILDREN 6
243 #define MIN_CHILDREN 3
250 static BTreeView *gtk_text_btree_get_view (GtkTextBTree *tree,
252 static void gtk_text_btree_rebalance (GtkTextBTree *tree,
253 GtkTextBTreeNode *node);
254 static GtkTextLine * get_last_line (GtkTextBTree *tree);
255 static void post_insert_fixup (GtkTextBTree *tree,
256 GtkTextLine *insert_line,
257 gint char_count_delta,
258 gint line_count_delta);
259 static void gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
260 GtkTextTagInfo *info,
262 static gboolean gtk_text_btree_node_has_tag (GtkTextBTreeNode *node,
265 static void segments_changed (GtkTextBTree *tree);
266 static void chars_changed (GtkTextBTree *tree);
267 static void summary_list_destroy (Summary *summary);
268 static GtkTextLine *gtk_text_line_new (void);
269 static void gtk_text_line_destroy (GtkTextBTree *tree,
271 static void gtk_text_line_set_parent (GtkTextLine *line,
272 GtkTextBTreeNode *node);
273 static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
277 static NodeData *node_data_new (gpointer view_id);
278 static void node_data_destroy (NodeData *nd);
279 static void node_data_list_destroy (NodeData *nd);
280 static NodeData *node_data_find (NodeData *nd,
283 static GtkTextBTreeNode *gtk_text_btree_node_new (void);
284 static void gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node);
285 static void gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node,
287 static NodeData * gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
289 static NodeData * gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
291 static void gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
294 static void gtk_text_btree_node_remove_view (BTreeView *view,
295 GtkTextBTreeNode *node,
297 static void gtk_text_btree_node_destroy (GtkTextBTree *tree,
298 GtkTextBTreeNode *node);
299 static void gtk_text_btree_node_free_empty (GtkTextBTree *tree,
300 GtkTextBTreeNode *node);
301 static NodeData * gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node,
303 static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
305 static void gtk_text_btree_node_get_size (GtkTextBTreeNode *node,
309 static GtkTextBTreeNode * gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
310 GtkTextBTreeNode *node2);
311 static void get_tree_bounds (GtkTextBTree *tree,
314 static void tag_changed_cb (GtkTextTagTable *table,
316 gboolean size_changed,
318 static void cleanup_line (GtkTextLine *line);
319 static void recompute_node_counts (GtkTextBTree *tree,
320 GtkTextBTreeNode *node);
321 static void inc_count (GtkTextTag *tag,
323 TagInfo *tagInfoPtr);
325 static void summary_destroy (Summary *summary);
327 static void gtk_text_btree_link_segment (GtkTextLineSegment *seg,
328 const GtkTextIter *iter);
329 static void gtk_text_btree_unlink_segment (GtkTextBTree *tree,
330 GtkTextLineSegment *seg,
334 static GtkTextTagInfo *gtk_text_btree_get_tag_info (GtkTextBTree *tree,
336 static GtkTextTagInfo *gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
338 static void gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
341 static void redisplay_region (GtkTextBTree *tree,
342 const GtkTextIter *start,
343 const GtkTextIter *end);
345 /* Inline thingies */
348 segments_changed (GtkTextBTree *tree)
350 tree->segments_changed_stamp += 1;
354 chars_changed (GtkTextBTree *tree)
356 tree->chars_changed_stamp += 1;
364 _gtk_text_btree_new (GtkTextTagTable *table,
365 GtkTextBuffer *buffer)
368 GtkTextBTreeNode *root_node;
369 GtkTextLine *line, *line2;
371 g_return_val_if_fail (GTK_IS_TEXT_TAG_TABLE (table), NULL);
372 g_return_val_if_fail (GTK_IS_TEXT_BUFFER (buffer), NULL);
375 * The tree will initially have two empty lines. The second line
376 * isn't actually part of the tree's contents, but its presence
377 * makes several operations easier. The tree will have one GtkTextBTreeNode,
378 * which is also the root of the tree.
381 /* Create the root node. */
383 root_node = gtk_text_btree_node_new ();
385 line = gtk_text_line_new ();
386 line2 = gtk_text_line_new ();
388 root_node->parent = NULL;
389 root_node->next = NULL;
390 root_node->summary = NULL;
391 root_node->level = 0;
392 root_node->children.line = line;
393 root_node->num_children = 2;
394 root_node->num_lines = 2;
395 root_node->num_chars = 2;
397 line->parent = root_node;
400 line->segments = _gtk_char_segment_new ("\n", 1);
402 line2->parent = root_node;
404 line2->segments = _gtk_char_segment_new ("\n", 1);
406 /* Create the tree itself */
408 tree = g_new0(GtkTextBTree, 1);
409 tree->root_node = root_node;
413 /* Set these to values that are unlikely to be found
414 * in random memory garbage, and also avoid
415 * duplicates between tree instances.
417 tree->chars_changed_stamp = g_random_int ();
418 tree->segments_changed_stamp = g_random_int ();
420 tree->last_line_stamp = tree->chars_changed_stamp - 1;
421 tree->last_line = NULL;
423 tree->end_iter_line_stamp = tree->chars_changed_stamp - 1;
424 tree->end_iter_segment_stamp = tree->segments_changed_stamp - 1;
425 tree->end_iter_line = NULL;
426 tree->end_iter_segment_byte_index = 0;
427 tree->end_iter_segment_char_offset = 0;
429 g_object_ref (tree->table);
431 tree->tag_changed_handler = g_signal_connect (tree->table,
433 G_CALLBACK (tag_changed_cb),
436 tree->mark_table = g_hash_table_new (g_str_hash, g_str_equal);
437 tree->child_anchor_table = NULL;
439 /* We don't ref the buffer, since the buffer owns us;
440 * we'd have some circularity issues. The buffer always
441 * lasts longer than the BTree
443 tree->buffer = buffer;
447 GtkTextLineSegment *seg;
449 _gtk_text_btree_get_iter_at_line_char (tree, &start, 0, 0);
452 tree->insert_mark = _gtk_text_btree_set_mark (tree,
459 seg = tree->insert_mark->segment;
461 seg->body.mark.not_deleteable = TRUE;
462 seg->body.mark.visible = TRUE;
464 tree->selection_bound_mark = _gtk_text_btree_set_mark (tree,
471 seg = tree->selection_bound_mark->segment;
473 seg->body.mark.not_deleteable = TRUE;
475 g_object_ref (tree->insert_mark);
476 g_object_ref (tree->selection_bound_mark);
485 _gtk_text_btree_ref (GtkTextBTree *tree)
487 g_return_if_fail (tree != NULL);
488 g_return_if_fail (tree->refcount > 0);
494 _gtk_text_btree_unref (GtkTextBTree *tree)
496 g_return_if_fail (tree != NULL);
497 g_return_if_fail (tree->refcount > 0);
501 if (tree->refcount == 0)
503 g_signal_handler_disconnect (tree->table,
504 tree->tag_changed_handler);
506 g_object_unref (tree->table);
509 gtk_text_btree_node_destroy (tree, tree->root_node);
510 tree->root_node = NULL;
512 g_assert (g_hash_table_size (tree->mark_table) == 0);
513 g_hash_table_destroy (tree->mark_table);
514 tree->mark_table = NULL;
515 if (tree->child_anchor_table != NULL)
517 g_hash_table_destroy (tree->child_anchor_table);
518 tree->child_anchor_table = NULL;
521 g_object_unref (tree->insert_mark);
522 tree->insert_mark = NULL;
523 g_object_unref (tree->selection_bound_mark);
524 tree->selection_bound_mark = NULL;
531 _gtk_text_btree_get_buffer (GtkTextBTree *tree)
537 _gtk_text_btree_get_chars_changed_stamp (GtkTextBTree *tree)
539 return tree->chars_changed_stamp;
543 _gtk_text_btree_get_segments_changed_stamp (GtkTextBTree *tree)
545 return tree->segments_changed_stamp;
549 _gtk_text_btree_segments_changed (GtkTextBTree *tree)
551 g_return_if_fail (tree != NULL);
552 segments_changed (tree);
556 * Indexable segment mutation
560 * The following function is responsible for resolving the bidi direction
561 * for the lines between start and end. But it also calculates any
562 * dependent bidi direction for surrounding lines that change as a result
563 * of the bidi direction decisions within the range. The function is
564 * trying to do as little propagation as is needed.
567 gtk_text_btree_resolve_bidi (GtkTextIter *start,
570 GtkTextBTree *tree = _gtk_text_iter_get_btree (start);
571 GtkTextLine *start_line, *end_line, *start_line_prev, *end_line_next, *line;
572 PangoDirection last_strong, dir_above_propagated, dir_below_propagated;
574 /* Resolve the strong bidi direction for all lines between
577 start_line = _gtk_text_iter_get_text_line (start);
578 start_line_prev = _gtk_text_line_previous (start_line);
579 end_line = _gtk_text_iter_get_text_line (end);
580 end_line_next = _gtk_text_line_next (end_line);
583 while (line && line != end_line_next)
585 /* Loop through the segments and search for a strong character
587 GtkTextLineSegment *seg = line->segments;
588 line->dir_strong = PANGO_DIRECTION_NEUTRAL;
592 if (seg->byte_count > 0)
594 PangoDirection pango_dir;
596 pango_dir = pango_find_base_dir (seg->body.chars,
599 if (pango_dir != PANGO_DIRECTION_NEUTRAL)
601 line->dir_strong = pango_dir;
608 line = _gtk_text_line_next (line);
613 /* The variable dir_above_propagated contains the forward propagated
614 * direction before start. It is neutral if start is in the beginning
617 dir_above_propagated = PANGO_DIRECTION_NEUTRAL;
619 dir_above_propagated = start_line_prev->dir_propagated_forward;
621 /* Loop forward and propagate the direction of each paragraph
622 * to all neutral lines.
625 last_strong = dir_above_propagated;
626 while (line != end_line_next)
628 if (line->dir_strong != PANGO_DIRECTION_NEUTRAL)
629 last_strong = line->dir_strong;
631 line->dir_propagated_forward = last_strong;
633 line = _gtk_text_line_next (line);
636 /* Continue propagating as long as the previous resolved forward
637 * is different from last_strong.
640 GtkTextIter end_propagate;
643 line->dir_strong == PANGO_DIRECTION_NEUTRAL &&
644 line->dir_propagated_forward != last_strong)
646 GtkTextLine *prev = line;
647 line->dir_propagated_forward = last_strong;
649 line = _gtk_text_line_next(line);
657 /* The last line to invalidate is the last line before the
658 * line with the strong character. Or in case of the end of the
659 * buffer, the last line of the buffer. (There seems to be an
660 * extra "virtual" last line in the buffer that must not be used
661 * calling _gtk_text_btree_get_iter_at_line (causes crash). Thus the
662 * _gtk_text_line_previous is ok in that case as well.)
664 line = _gtk_text_line_previous (line);
665 _gtk_text_btree_get_iter_at_line (tree, &end_propagate, line, 0);
666 _gtk_text_btree_invalidate_region (tree, end, &end_propagate);
671 /* The variable dir_below_propagated contains the backward propagated
672 * direction after end. It is neutral if end is at the end of
675 dir_below_propagated = PANGO_DIRECTION_NEUTRAL;
677 dir_below_propagated = end_line_next->dir_propagated_back;
679 /* Loop backward and propagate the direction of each paragraph
680 * to all neutral lines.
683 last_strong = dir_below_propagated;
684 while (line != start_line_prev)
686 if (line->dir_strong != PANGO_DIRECTION_NEUTRAL)
687 last_strong = line->dir_strong;
689 line->dir_propagated_back = last_strong;
691 line = _gtk_text_line_previous (line);
694 /* Continue propagating as long as the resolved backward dir
695 * is different from last_strong.
698 GtkTextIter start_propagate;
701 line->dir_strong == PANGO_DIRECTION_NEUTRAL &&
702 line->dir_propagated_back != last_strong)
704 GtkTextLine *prev = line;
705 line->dir_propagated_back = last_strong;
707 line = _gtk_text_line_previous (line);
715 /* We only need to invalidate for backwards propagation if the
716 * line we ended up on didn't get a direction from forwards
719 if (line && line->dir_propagated_forward == PANGO_DIRECTION_NEUTRAL)
721 _gtk_text_btree_get_iter_at_line (tree, &start_propagate, line, 0);
722 _gtk_text_btree_invalidate_region(tree, &start_propagate, start);
728 _gtk_text_btree_delete (GtkTextIter *start,
731 GtkTextLineSegment *prev_seg; /* The segment just before the start
732 * of the deletion range. */
733 GtkTextLineSegment *last_seg; /* The segment just after the end
734 * of the deletion range. */
735 GtkTextLineSegment *seg, *next, *next2;
736 GtkTextLine *curline;
737 GtkTextBTreeNode *curnode, *node;
739 GtkTextLine *start_line;
740 GtkTextLine *end_line;
741 GtkTextLine *deleted_lines = NULL; /* List of lines we've deleted */
742 gint start_byte_offset;
744 g_return_if_fail (start != NULL);
745 g_return_if_fail (end != NULL);
746 g_return_if_fail (_gtk_text_iter_get_btree (start) ==
747 _gtk_text_iter_get_btree (end));
749 gtk_text_iter_order (start, end);
751 tree = _gtk_text_iter_get_btree (start);
753 if (gtk_debug_flags & GTK_DEBUG_TEXT)
754 _gtk_text_btree_check (tree);
756 /* Broadcast the need for redisplay before we break the iterators */
757 DV (g_print ("invalidating due to deleting some text (%s)\n", G_STRLOC));
758 _gtk_text_btree_invalidate_region (tree, start, end);
760 /* Save the byte offset so we can reset the iterators */
761 start_byte_offset = gtk_text_iter_get_line_index (start);
763 start_line = _gtk_text_iter_get_text_line (start);
764 end_line = _gtk_text_iter_get_text_line (end);
767 * Split the start and end segments, so we have a place
768 * to insert our new text.
770 * Tricky point: split at end first; otherwise the split
771 * at end may invalidate seg and/or prev_seg. This allows
772 * us to avoid invalidating segments for start.
775 last_seg = gtk_text_line_segment_split (end);
776 if (last_seg != NULL)
777 last_seg = last_seg->next;
779 last_seg = end_line->segments;
781 prev_seg = gtk_text_line_segment_split (start);
782 if (prev_seg != NULL)
784 seg = prev_seg->next;
785 prev_seg->next = last_seg;
789 seg = start_line->segments;
790 start_line->segments = last_seg;
793 /* notify iterators that their segments need recomputation,
794 just for robustness. */
795 segments_changed (tree);
798 * Delete all of the segments between prev_seg and last_seg.
801 curline = start_line;
802 curnode = curline->parent;
803 while (seg != last_seg)
809 GtkTextLine *nextline;
812 * We just ran off the end of a line. First find the
813 * next line, then go back to the old line and delete it
814 * (unless it's the starting line for the range).
817 nextline = _gtk_text_line_next (curline);
818 if (curline != start_line)
820 if (curnode == start_line->parent)
821 start_line->next = curline->next;
823 curnode->children.line = curline->next;
825 for (node = curnode; node != NULL;
828 /* Don't update node->num_chars, because
829 * that was done when we deleted the segments.
831 node->num_lines -= 1;
834 curnode->num_children -= 1;
835 curline->next = deleted_lines;
836 deleted_lines = curline;
840 seg = curline->segments;
843 * If the GtkTextBTreeNode is empty then delete it and its parents,
844 * recursively upwards until a non-empty GtkTextBTreeNode is found.
847 while (curnode->num_children == 0)
849 GtkTextBTreeNode *parent;
851 parent = curnode->parent;
852 if (parent->children.node == curnode)
854 parent->children.node = curnode->next;
858 GtkTextBTreeNode *prevnode = parent->children.node;
859 while (prevnode->next != curnode)
861 prevnode = prevnode->next;
863 prevnode->next = curnode->next;
865 parent->num_children--;
866 gtk_text_btree_node_free_empty (tree, curnode);
869 curnode = curline->parent;
874 char_count = seg->char_count;
876 if ((*seg->type->deleteFunc)(seg, curline, FALSE) != 0)
879 * This segment refuses to die. Move it to prev_seg and
880 * advance prev_seg if the segment has left gravity.
883 if (prev_seg == NULL)
885 seg->next = start_line->segments;
886 start_line->segments = seg;
888 else if (prev_seg->next &&
889 seg->type == >k_text_toggle_off_type &&
890 prev_seg->next->type == >k_text_toggle_on_type &&
891 seg->body.toggle.info == prev_seg->next->body.toggle.info)
893 /* Try to match an off toggle with the matching on toggle
894 * if it immediately follows. This is a common case, and
895 * handling it here prevents quadratic blowup in
896 * cleanup_line() below. See bug 317125.
898 next2 = prev_seg->next->next;
899 g_free ((char *)prev_seg->next);
900 prev_seg->next = next2;
901 g_free ((char *)seg);
906 seg->next = prev_seg->next;
907 prev_seg->next = seg;
910 if (seg && seg->type->leftGravity)
917 /* Segment is gone. Decrement the char count of the node and
919 for (node = curnode; node != NULL;
922 node->num_chars -= char_count;
930 * If the beginning and end of the deletion range are in different
931 * lines, join the two lines together and discard the ending line.
934 if (start_line != end_line)
937 GtkTextBTreeNode *ancestor_node;
938 GtkTextLine *prevline;
941 /* last_seg was appended to start_line up at the top of this function */
943 for (seg = last_seg; seg != NULL;
946 chars_moved += seg->char_count;
947 if (seg->type->lineChangeFunc != NULL)
949 (*seg->type->lineChangeFunc)(seg, end_line);
953 for (node = start_line->parent; node != NULL;
956 node->num_chars += chars_moved;
959 curnode = end_line->parent;
960 for (node = curnode; node != NULL;
963 node->num_chars -= chars_moved;
966 curnode->num_children--;
967 prevline = curnode->children.line;
968 if (prevline == end_line)
970 curnode->children.line = end_line->next;
974 while (prevline->next != end_line)
976 prevline = prevline->next;
978 prevline->next = end_line->next;
980 end_line->next = deleted_lines;
981 deleted_lines = end_line;
983 /* We now fix up the per-view aggregates. We add all the height and
984 * width for the deleted lines to the start line, so that when revalidation
985 * occurs, the correct change in size is seen.
987 ancestor_node = gtk_text_btree_node_common_parent (curnode, start_line->parent);
994 gint deleted_width = 0;
995 gint deleted_height = 0;
997 line = deleted_lines;
1000 GtkTextLine *next_line = line->next;
1001 ld = _gtk_text_line_get_data (line, view->view_id);
1005 deleted_width = MAX (deleted_width, ld->width);
1006 deleted_height += ld->height;
1010 gtk_text_line_destroy (tree, line);
1015 if (deleted_width > 0 || deleted_height > 0)
1017 ld = _gtk_text_line_get_data (start_line, view->view_id);
1021 /* This means that start_line has never been validated.
1022 * We don't really want to do the validation here but
1023 * we do need to store our temporary sizes. So we
1024 * create the line data and assume a line w/h of 0.
1026 ld = _gtk_text_line_data_new (view->layout, start_line);
1027 _gtk_text_line_add_data (start_line, ld);
1033 ld->width = MAX (deleted_width, ld->width);
1034 ld->height += deleted_height;
1038 gtk_text_btree_node_check_valid_downward (ancestor_node, view->view_id);
1039 if (ancestor_node->parent)
1040 gtk_text_btree_node_check_valid_upward (ancestor_node->parent, view->view_id);
1045 /* avoid dangling pointer */
1046 deleted_lines = NULL;
1048 gtk_text_btree_rebalance (tree, curnode);
1052 * Cleanup the segments in the new line.
1055 cleanup_line (start_line);
1058 * Lastly, rebalance the first GtkTextBTreeNode of the range.
1061 gtk_text_btree_rebalance (tree, start_line->parent);
1063 /* Notify outstanding iterators that they
1065 chars_changed (tree);
1066 segments_changed (tree);
1068 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1069 _gtk_text_btree_check (tree);
1071 /* Re-initialize our iterators */
1072 _gtk_text_btree_get_iter_at_line (tree, start, start_line, start_byte_offset);
1075 gtk_text_btree_resolve_bidi (start, end);
1079 _gtk_text_btree_insert (GtkTextIter *iter,
1083 GtkTextLineSegment *prev_seg; /* The segment just before the first
1084 * new segment (NULL means new segment
1085 * is at beginning of line). */
1086 GtkTextLineSegment *cur_seg; /* Current segment; new characters
1087 * are inserted just after this one.
1088 * NULL means insert at beginning of
1090 GtkTextLine *line; /* Current line (new segments are
1091 * added to this line). */
1092 GtkTextLineSegment *seg;
1093 GtkTextLine *newline;
1094 int chunk_len; /* # characters in current chunk. */
1095 gint sol; /* start of line */
1096 gint eol; /* Pointer to character just after last
1097 * one in current chunk.
1099 gint delim; /* index of paragraph delimiter */
1100 int line_count_delta; /* Counts change to total number of
1104 int char_count_delta; /* change to number of chars */
1106 gint start_byte_index;
1107 GtkTextLine *start_line;
1109 g_return_if_fail (text != NULL);
1110 g_return_if_fail (iter != NULL);
1113 len = strlen (text);
1115 /* extract iterator info */
1116 tree = _gtk_text_iter_get_btree (iter);
1117 line = _gtk_text_iter_get_text_line (iter);
1120 start_byte_index = gtk_text_iter_get_line_index (iter);
1122 /* Get our insertion segment split. Note this assumes line allows
1123 * char insertions, which isn't true of the "last" line. But iter
1124 * should not be on that line, as we assert here.
1126 g_assert (!_gtk_text_line_is_last (line, tree));
1127 prev_seg = gtk_text_line_segment_split (iter);
1130 /* Invalidate all iterators */
1131 chars_changed (tree);
1132 segments_changed (tree);
1135 * Chop the text up into lines and create a new segment for
1136 * each line, plus a new line for the leftovers from the
1142 line_count_delta = 0;
1143 char_count_delta = 0;
1148 pango_find_paragraph_boundary (text + sol,
1153 /* make these relative to the start of the text */
1157 g_assert (eol >= sol);
1158 g_assert (delim >= sol);
1159 g_assert (eol >= delim);
1160 g_assert (sol >= 0);
1161 g_assert (eol <= len);
1163 chunk_len = eol - sol;
1165 g_assert (g_utf8_validate (&text[sol], chunk_len, NULL));
1166 seg = _gtk_char_segment_new (&text[sol], chunk_len);
1168 char_count_delta += seg->char_count;
1170 if (cur_seg == NULL)
1172 seg->next = line->segments;
1173 line->segments = seg;
1177 seg->next = cur_seg->next;
1178 cur_seg->next = seg;
1183 /* chunk didn't end with a paragraph separator */
1184 g_assert (eol == len);
1189 * The chunk ended with a newline, so create a new GtkTextLine
1190 * and move the remainder of the old line to it.
1193 newline = gtk_text_line_new ();
1194 gtk_text_line_set_parent (newline, line->parent);
1195 newline->next = line->next;
1196 line->next = newline;
1197 newline->segments = seg->next;
1205 * Cleanup the starting line for the insertion, plus the ending
1206 * line if it's different.
1209 cleanup_line (start_line);
1210 if (line != start_line)
1212 cleanup_line (line);
1215 post_insert_fixup (tree, line, line_count_delta, char_count_delta);
1217 /* Invalidate our region, and reset the iterator the user
1218 passed in to point to the end of the inserted text. */
1224 _gtk_text_btree_get_iter_at_line (tree,
1230 /* We could almost certainly be more efficient here
1231 by saving the information from the insertion loop
1233 gtk_text_iter_forward_chars (&end, char_count_delta);
1235 DV (g_print ("invalidating due to inserting some text (%s)\n", G_STRLOC));
1236 _gtk_text_btree_invalidate_region (tree,
1240 /* Convenience for the user */
1243 gtk_text_btree_resolve_bidi (&start, &end);
1248 insert_pixbuf_or_widget_segment (GtkTextIter *iter,
1249 GtkTextLineSegment *seg)
1253 GtkTextLineSegment *prevPtr;
1256 gint start_byte_offset;
1258 line = _gtk_text_iter_get_text_line (iter);
1259 tree = _gtk_text_iter_get_btree (iter);
1260 start_byte_offset = gtk_text_iter_get_line_index (iter);
1262 prevPtr = gtk_text_line_segment_split (iter);
1263 if (prevPtr == NULL)
1265 seg->next = line->segments;
1266 line->segments = seg;
1270 seg->next = prevPtr->next;
1271 prevPtr->next = seg;
1274 post_insert_fixup (tree, line, 0, seg->char_count);
1276 chars_changed (tree);
1277 segments_changed (tree);
1279 /* reset *iter for the user, and invalidate tree nodes */
1281 _gtk_text_btree_get_iter_at_line (tree, &start, line, start_byte_offset);
1284 gtk_text_iter_forward_char (iter); /* skip forward past the segment */
1286 DV (g_print ("invalidating due to inserting pixbuf/widget (%s)\n", G_STRLOC));
1287 _gtk_text_btree_invalidate_region (tree, &start, iter);
1291 _gtk_text_btree_insert_pixbuf (GtkTextIter *iter,
1294 GtkTextLineSegment *seg;
1296 seg = _gtk_pixbuf_segment_new (pixbuf);
1298 insert_pixbuf_or_widget_segment (iter, seg);
1302 _gtk_text_btree_insert_child_anchor (GtkTextIter *iter,
1303 GtkTextChildAnchor *anchor)
1305 GtkTextLineSegment *seg;
1308 if (anchor->segment != NULL)
1310 g_warning (G_STRLOC": Same child anchor can't be inserted twice");
1314 seg = _gtk_widget_segment_new (anchor);
1316 tree = seg->body.child.tree = _gtk_text_iter_get_btree (iter);
1317 seg->body.child.line = _gtk_text_iter_get_text_line (iter);
1319 insert_pixbuf_or_widget_segment (iter, seg);
1321 if (tree->child_anchor_table == NULL)
1322 tree->child_anchor_table = g_hash_table_new (NULL, NULL);
1324 g_hash_table_insert (tree->child_anchor_table,
1325 seg->body.child.obj,
1326 seg->body.child.obj);
1330 _gtk_text_btree_unregister_child_anchor (GtkTextChildAnchor *anchor)
1332 GtkTextLineSegment *seg;
1334 seg = anchor->segment;
1336 g_hash_table_remove (seg->body.child.tree->child_anchor_table,
1345 find_line_by_y (GtkTextBTree *tree, BTreeView *view,
1346 GtkTextBTreeNode *node, gint y, gint *line_top,
1347 GtkTextLine *last_line)
1351 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1352 _gtk_text_btree_check (tree);
1354 if (node->level == 0)
1358 line = node->children.line;
1360 while (line != NULL && line != last_line)
1362 GtkTextLineData *ld;
1364 ld = _gtk_text_line_get_data (line, view->view_id);
1368 if (y < (current_y + (ld ? ld->height : 0)))
1371 current_y += ld->height;
1372 *line_top += ld->height;
1381 GtkTextBTreeNode *child;
1383 child = node->children.node;
1385 while (child != NULL)
1390 gtk_text_btree_node_get_size (child, view->view_id,
1393 if (y < (current_y + height))
1394 return find_line_by_y (tree, view, child,
1395 y - current_y, line_top,
1398 current_y += height;
1399 *line_top += height;
1401 child = child->next;
1409 _gtk_text_btree_find_line_by_y (GtkTextBTree *tree,
1416 GtkTextLine *last_line;
1419 view = gtk_text_btree_get_view (tree, view_id);
1420 g_return_val_if_fail (view != NULL, NULL);
1422 last_line = get_last_line (tree);
1424 line = find_line_by_y (tree, view, tree->root_node, ypixel, &line_top,
1428 *line_top_out = line_top;
1434 find_line_top_in_line_list (GtkTextBTree *tree,
1437 GtkTextLine *target_line,
1440 while (line != NULL)
1442 GtkTextLineData *ld;
1444 if (line == target_line)
1447 ld = _gtk_text_line_get_data (line, view->view_id);
1454 g_assert_not_reached (); /* If we get here, our
1455 target line didn't exist
1456 under its parent node */
1461 _gtk_text_btree_find_line_top (GtkTextBTree *tree,
1462 GtkTextLine *target_line,
1469 GtkTextBTreeNode *node;
1471 view = gtk_text_btree_get_view (tree, view_id);
1473 g_return_val_if_fail (view != NULL, 0);
1476 node = target_line->parent;
1477 while (node != NULL)
1479 nodes = g_slist_prepend (nodes, node);
1480 node = node->parent;
1484 while (iter != NULL)
1488 if (node->level == 0)
1490 g_slist_free (nodes);
1491 return find_line_top_in_line_list (tree, view,
1492 node->children.line,
1497 GtkTextBTreeNode *child;
1498 GtkTextBTreeNode *target_node;
1500 g_assert (iter->next != NULL); /* not at level 0 */
1501 target_node = iter->next->data;
1503 child = node->children.node;
1505 while (child != NULL)
1510 if (child == target_node)
1514 gtk_text_btree_node_get_size (child, view->view_id,
1518 child = child->next;
1520 g_assert (child != NULL); /* should have broken out before we
1524 iter = g_slist_next (iter);
1527 g_assert_not_reached (); /* we return when we find the target line */
1532 _gtk_text_btree_add_view (GtkTextBTree *tree,
1533 GtkTextLayout *layout)
1536 GtkTextLine *last_line;
1537 GtkTextLineData *line_data;
1539 g_return_if_fail (tree != NULL);
1541 view = g_new (BTreeView, 1);
1543 view->view_id = layout;
1544 view->layout = layout;
1546 view->next = tree->views;
1551 g_assert (tree->views->prev == NULL);
1552 tree->views->prev = view;
1557 /* The last line in the buffer has identity values for the per-view
1558 * data so that we can avoid special case checks for it in a large
1561 last_line = get_last_line (tree);
1563 line_data = g_new (GtkTextLineData, 1);
1564 line_data->view_id = layout;
1565 line_data->next = NULL;
1566 line_data->width = 0;
1567 line_data->height = 0;
1568 line_data->valid = TRUE;
1570 _gtk_text_line_add_data (last_line, line_data);
1574 _gtk_text_btree_remove_view (GtkTextBTree *tree,
1578 GtkTextLine *last_line;
1579 GtkTextLineData *line_data;
1581 g_return_if_fail (tree != NULL);
1585 while (view != NULL)
1587 if (view->view_id == view_id)
1593 g_return_if_fail (view != NULL);
1596 view->next->prev = view->prev;
1599 view->prev->next = view->next;
1601 if (view == tree->views)
1602 tree->views = view->next;
1604 /* Remove the line data for the last line which we added ourselves.
1605 * (Do this first, so that we don't try to call the view's line data destructor on it.)
1607 last_line = get_last_line (tree);
1608 line_data = _gtk_text_line_remove_data (last_line, view_id);
1611 gtk_text_btree_node_remove_view (view, tree->root_node, view_id);
1613 view->layout = (gpointer) 0xdeadbeef;
1614 view->view_id = (gpointer) 0xdeadbeef;
1620 _gtk_text_btree_invalidate_region (GtkTextBTree *tree,
1621 const GtkTextIter *start,
1622 const GtkTextIter *end)
1628 while (view != NULL)
1630 gtk_text_layout_invalidate (view->layout, start, end);
1637 _gtk_text_btree_get_view_size (GtkTextBTree *tree,
1642 g_return_if_fail (tree != NULL);
1643 g_return_if_fail (view_id != NULL);
1645 gtk_text_btree_node_get_size (tree->root_node, view_id,
1660 iter_stack_new (void)
1663 stack = g_new (IterStack, 1);
1664 stack->iters = NULL;
1671 iter_stack_push (IterStack *stack, const GtkTextIter *iter)
1674 if (stack->count > stack->alloced)
1676 stack->alloced = stack->count*2;
1677 stack->iters = g_realloc (stack->iters,
1678 stack->alloced*sizeof (GtkTextIter));
1680 stack->iters[stack->count-1] = *iter;
1684 iter_stack_pop (IterStack *stack, GtkTextIter *iter)
1686 if (stack->count == 0)
1691 *iter = stack->iters[stack->count];
1697 iter_stack_free (IterStack *stack)
1699 g_free (stack->iters);
1704 iter_stack_invert (IterStack *stack)
1706 if (stack->count > 0)
1709 guint j = stack->count - 1;
1714 tmp = stack->iters[i];
1715 stack->iters[i] = stack->iters[j];
1716 stack->iters[j] = tmp;
1725 queue_tag_redisplay (GtkTextBTree *tree,
1727 const GtkTextIter *start,
1728 const GtkTextIter *end)
1730 if (_gtk_text_tag_affects_size (tag))
1732 DV (g_print ("invalidating due to size-affecting tag (%s)\n", G_STRLOC));
1733 _gtk_text_btree_invalidate_region (tree, start, end);
1735 else if (_gtk_text_tag_affects_nonsize_appearance (tag))
1737 /* We only need to queue a redraw, not a relayout */
1738 redisplay_region (tree, start, end);
1741 /* We don't need to do anything if the tag doesn't affect display */
1745 _gtk_text_btree_tag (const GtkTextIter *start_orig,
1746 const GtkTextIter *end_orig,
1750 GtkTextLineSegment *seg, *prev;
1751 GtkTextLine *cleanupline;
1752 gboolean toggled_on;
1753 GtkTextLine *start_line;
1754 GtkTextLine *end_line;
1756 GtkTextIter start, end;
1759 GtkTextTagInfo *info;
1761 g_return_if_fail (start_orig != NULL);
1762 g_return_if_fail (end_orig != NULL);
1763 g_return_if_fail (GTK_IS_TEXT_TAG (tag));
1764 g_return_if_fail (_gtk_text_iter_get_btree (start_orig) ==
1765 _gtk_text_iter_get_btree (end_orig));
1766 g_return_if_fail (tag->table == _gtk_text_iter_get_btree (start_orig)->table);
1769 printf ("%s tag %s from %d to %d\n",
1770 add ? "Adding" : "Removing",
1772 gtk_text_buffer_get_offset (start_orig),
1773 gtk_text_buffer_get_offset (end_orig));
1776 if (gtk_text_iter_equal (start_orig, end_orig))
1779 start = *start_orig;
1782 gtk_text_iter_order (&start, &end);
1784 tree = _gtk_text_iter_get_btree (&start);
1786 queue_tag_redisplay (tree, tag, &start, &end);
1788 info = gtk_text_btree_get_tag_info (tree, tag);
1790 start_line = _gtk_text_iter_get_text_line (&start);
1791 end_line = _gtk_text_iter_get_text_line (&end);
1793 /* Find all tag toggles in the region; we are going to delete them.
1794 We need to find them in advance, because
1795 forward_find_tag_toggle () won't work once we start playing around
1797 stack = iter_stack_new ();
1800 /* forward_to_tag_toggle() skips a toggle at the start iterator,
1801 * which is deliberate - we don't want to delete a toggle at the
1804 while (gtk_text_iter_forward_to_tag_toggle (&iter, tag))
1806 if (gtk_text_iter_compare (&iter, &end) >= 0)
1809 iter_stack_push (stack, &iter);
1812 /* We need to traverse the toggles in order. */
1813 iter_stack_invert (stack);
1816 * See whether the tag is present at the start of the range. If
1817 * the state doesn't already match what we want then add a toggle
1821 toggled_on = gtk_text_iter_has_tag (&start, tag);
1822 if ( (add && !toggled_on) ||
1823 (!add && toggled_on) )
1825 /* This could create a second toggle at the start position;
1826 cleanup_line () will remove it if so. */
1827 seg = _gtk_toggle_segment_new (info, add);
1829 prev = gtk_text_line_segment_split (&start);
1832 seg->next = start_line->segments;
1833 start_line->segments = seg;
1837 seg->next = prev->next;
1841 /* cleanup_line adds the new toggle to the node counts. */
1843 printf ("added toggle at start\n");
1845 /* we should probably call segments_changed, but in theory
1846 any still-cached segments in the iters we are about to
1847 use are still valid, since they're in front
1853 * Scan the range of characters and delete any internal tag
1854 * transitions. Keep track of what the old state was at the end
1855 * of the range, and add a toggle there if it's needed.
1859 cleanupline = start_line;
1860 while (iter_stack_pop (stack, &iter))
1862 GtkTextLineSegment *indexable_seg;
1865 line = _gtk_text_iter_get_text_line (&iter);
1866 seg = _gtk_text_iter_get_any_segment (&iter);
1867 indexable_seg = _gtk_text_iter_get_indexable_segment (&iter);
1869 g_assert (seg != NULL);
1870 g_assert (indexable_seg != NULL);
1871 g_assert (seg != indexable_seg);
1873 prev = line->segments;
1875 /* Find the segment that actually toggles this tag. */
1876 while (seg != indexable_seg)
1878 g_assert (seg != NULL);
1879 g_assert (indexable_seg != NULL);
1880 g_assert (seg != indexable_seg);
1882 if ( (seg->type == >k_text_toggle_on_type ||
1883 seg->type == >k_text_toggle_off_type) &&
1884 (seg->body.toggle.info == info) )
1890 g_assert (seg != NULL);
1891 g_assert (indexable_seg != NULL);
1893 g_assert (seg != indexable_seg); /* If this happens, then
1894 forward_to_tag_toggle was
1896 g_assert (seg->body.toggle.info->tag == tag);
1898 /* If this happens, when previously tagging we didn't merge
1899 overlapping tags. */
1900 g_assert ( (toggled_on && seg->type == >k_text_toggle_off_type) ||
1901 (!toggled_on && seg->type == >k_text_toggle_on_type) );
1903 toggled_on = !toggled_on;
1906 printf ("deleting %s toggle\n",
1907 seg->type == >k_text_toggle_on_type ? "on" : "off");
1909 /* Remove toggle segment from the list. */
1912 line->segments = seg->next;
1916 while (prev->next != seg)
1920 prev->next = seg->next;
1923 /* Inform iterators we've hosed them. This actually reflects a
1924 bit of inefficiency; if you have the same tag toggled on and
1925 off a lot in a single line, we keep having the rescan from
1926 the front of the line. Of course we have to do that to get
1927 "prev" anyway, but here we are doing it an additional
1929 segments_changed (tree);
1931 /* Update node counts */
1932 if (seg->body.toggle.inNodeCounts)
1934 _gtk_change_node_toggle_count (line->parent,
1936 seg->body.toggle.inNodeCounts = FALSE;
1941 /* We only clean up lines when we're done with them, saves some
1942 gratuitous line-segment-traversals */
1944 if (cleanupline != line)
1946 cleanup_line (cleanupline);
1951 iter_stack_free (stack);
1953 /* toggled_on now reflects the toggle state _just before_ the
1954 end iterator. The end iterator could already have a toggle
1955 on or a toggle off. */
1956 if ( (add && !toggled_on) ||
1957 (!add && toggled_on) )
1959 /* This could create a second toggle at the start position;
1960 cleanup_line () will remove it if so. */
1962 seg = _gtk_toggle_segment_new (info, !add);
1964 prev = gtk_text_line_segment_split (&end);
1967 seg->next = end_line->segments;
1968 end_line->segments = seg;
1972 seg->next = prev->next;
1975 /* cleanup_line adds the new toggle to the node counts. */
1976 g_assert (seg->body.toggle.inNodeCounts == FALSE);
1978 printf ("added toggle at end\n");
1983 * Cleanup cleanupline and the last line of the range, if
1984 * these are different.
1987 cleanup_line (cleanupline);
1988 if (cleanupline != end_line)
1990 cleanup_line (end_line);
1993 segments_changed (tree);
1995 queue_tag_redisplay (tree, tag, &start, &end);
1997 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1998 _gtk_text_btree_check (tree);
2007 get_line_internal (GtkTextBTree *tree,
2009 gint *real_line_number,
2010 gboolean include_last)
2012 GtkTextBTreeNode *node;
2017 line_count = _gtk_text_btree_line_count (tree);
2021 if (line_number < 0)
2023 line_number = line_count;
2025 else if (line_number > line_count)
2027 line_number = line_count;
2030 if (real_line_number)
2031 *real_line_number = line_number;
2033 node = tree->root_node;
2034 lines_left = line_number;
2037 * Work down through levels of the tree until a GtkTextBTreeNode is found at
2041 while (node->level != 0)
2043 for (node = node->children.node;
2044 node->num_lines <= lines_left;
2050 g_error ("gtk_text_btree_find_line ran out of GtkTextBTreeNodes");
2053 lines_left -= node->num_lines;
2058 * Work through the lines attached to the level-0 GtkTextBTreeNode.
2061 for (line = node->children.line; lines_left > 0;
2067 g_error ("gtk_text_btree_find_line ran out of lines");
2076 _gtk_text_btree_get_end_iter_line (GtkTextBTree *tree)
2079 _gtk_text_btree_get_line (tree,
2080 _gtk_text_btree_line_count (tree) - 1,
2085 _gtk_text_btree_get_line (GtkTextBTree *tree,
2087 gint *real_line_number)
2089 return get_line_internal (tree, line_number, real_line_number, TRUE);
2093 _gtk_text_btree_get_line_no_last (GtkTextBTree *tree,
2095 gint *real_line_number)
2097 return get_line_internal (tree, line_number, real_line_number, FALSE);
2101 _gtk_text_btree_get_line_at_char (GtkTextBTree *tree,
2103 gint *line_start_index,
2104 gint *real_char_index)
2106 GtkTextBTreeNode *node;
2108 GtkTextLineSegment *seg;
2112 node = tree->root_node;
2114 /* Clamp to valid indexes (-1 is magic for "highest index"),
2115 * node->num_chars includes the two newlines that aren't really
2118 if (char_index < 0 || char_index >= (node->num_chars - 1))
2120 char_index = node->num_chars - 2;
2123 *real_char_index = char_index;
2126 * Work down through levels of the tree until a GtkTextBTreeNode is found at
2130 chars_left = char_index;
2131 while (node->level != 0)
2133 for (node = node->children.node;
2134 chars_left >= node->num_chars;
2137 chars_left -= node->num_chars;
2139 g_assert (chars_left >= 0);
2143 if (chars_left == 0)
2145 /* Start of a line */
2147 *line_start_index = char_index;
2148 return node->children.line;
2152 * Work through the lines attached to the level-0 GtkTextBTreeNode.
2157 for (line = node->children.line; line != NULL; line = line->next)
2159 seg = line->segments;
2162 if (chars_in_line + seg->char_count > chars_left)
2163 goto found; /* found our line/segment */
2165 chars_in_line += seg->char_count;
2170 chars_left -= chars_in_line;
2178 g_assert (line != NULL); /* hosage, ran out of lines */
2179 g_assert (seg != NULL);
2181 *line_start_index = char_index - chars_left;
2186 _gtk_text_btree_get_tags (const GtkTextIter *iter,
2189 GtkTextBTreeNode *node;
2190 GtkTextLine *siblingline;
2191 GtkTextLineSegment *seg;
2192 int src, dst, index;
2197 #define NUM_TAG_INFOS 10
2199 line = _gtk_text_iter_get_text_line (iter);
2200 byte_index = gtk_text_iter_get_line_index (iter);
2202 tagInfo.numTags = 0;
2203 tagInfo.arraySize = NUM_TAG_INFOS;
2204 tagInfo.tags = g_new (GtkTextTag*, NUM_TAG_INFOS);
2205 tagInfo.counts = g_new (int, NUM_TAG_INFOS);
2208 * Record tag toggles within the line of indexPtr but preceding
2209 * indexPtr. Note that if this loop segfaults, your
2210 * byte_index probably points past the sum of all
2211 * seg->byte_count */
2213 for (index = 0, seg = line->segments;
2214 (index + seg->byte_count) <= byte_index;
2215 index += seg->byte_count, seg = seg->next)
2217 if ((seg->type == >k_text_toggle_on_type)
2218 || (seg->type == >k_text_toggle_off_type))
2220 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2225 * Record toggles for tags in lines that are predecessors of
2226 * line but under the same level-0 GtkTextBTreeNode.
2229 for (siblingline = line->parent->children.line;
2230 siblingline != line;
2231 siblingline = siblingline->next)
2233 for (seg = siblingline->segments; seg != NULL;
2236 if ((seg->type == >k_text_toggle_on_type)
2237 || (seg->type == >k_text_toggle_off_type))
2239 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2245 * For each GtkTextBTreeNode in the ancestry of this line, record tag
2246 * toggles for all siblings that precede that GtkTextBTreeNode.
2249 for (node = line->parent; node->parent != NULL;
2250 node = node->parent)
2252 GtkTextBTreeNode *siblingPtr;
2255 for (siblingPtr = node->parent->children.node;
2256 siblingPtr != node; siblingPtr = siblingPtr->next)
2258 for (summary = siblingPtr->summary; summary != NULL;
2259 summary = summary->next)
2261 if (summary->toggle_count & 1)
2263 inc_count (summary->info->tag, summary->toggle_count,
2271 * Go through the tag information and squash out all of the tags
2272 * that have even toggle counts (these tags exist before the point
2273 * of interest, but not at the desired character itself).
2276 for (src = 0, dst = 0; src < tagInfo.numTags; src++)
2278 if (tagInfo.counts[src] & 1)
2280 g_assert (GTK_IS_TEXT_TAG (tagInfo.tags[src]));
2281 tagInfo.tags[dst] = tagInfo.tags[src];
2287 g_free (tagInfo.counts);
2290 g_free (tagInfo.tags);
2293 return tagInfo.tags;
2297 copy_segment (GString *string,
2298 gboolean include_hidden,
2299 gboolean include_nonchars,
2300 const GtkTextIter *start,
2301 const GtkTextIter *end)
2303 GtkTextLineSegment *end_seg;
2304 GtkTextLineSegment *seg;
2306 if (gtk_text_iter_equal (start, end))
2309 seg = _gtk_text_iter_get_indexable_segment (start);
2310 end_seg = _gtk_text_iter_get_indexable_segment (end);
2312 if (seg->type == >k_text_char_type)
2314 gboolean copy = TRUE;
2315 gint copy_bytes = 0;
2316 gint copy_start = 0;
2318 /* Don't copy if we're invisible; segments are invisible/not
2319 as a whole, no need to check each char */
2320 if (!include_hidden &&
2321 _gtk_text_btree_char_is_invisible (start))
2324 /* printf (" <invisible>\n"); */
2327 copy_start = _gtk_text_iter_get_segment_byte (start);
2331 /* End is in the same segment; need to copy fewer bytes. */
2332 gint end_byte = _gtk_text_iter_get_segment_byte (end);
2334 copy_bytes = end_byte - copy_start;
2337 copy_bytes = seg->byte_count - copy_start;
2339 g_assert (copy_bytes != 0); /* Due to iter equality check at
2340 front of this function. */
2344 g_assert ((copy_start + copy_bytes) <= seg->byte_count);
2346 g_string_append_len (string,
2347 seg->body.chars + copy_start,
2351 /* printf (" :%s\n", string->str); */
2353 else if (seg->type == >k_text_pixbuf_type ||
2354 seg->type == >k_text_child_type)
2356 gboolean copy = TRUE;
2358 if (!include_nonchars)
2362 else if (!include_hidden &&
2363 _gtk_text_btree_char_is_invisible (start))
2370 g_string_append_len (string,
2371 gtk_text_unknown_char_utf8,
2379 _gtk_text_btree_get_text (const GtkTextIter *start_orig,
2380 const GtkTextIter *end_orig,
2381 gboolean include_hidden,
2382 gboolean include_nonchars)
2384 GtkTextLineSegment *seg;
2385 GtkTextLineSegment *end_seg;
2392 g_return_val_if_fail (start_orig != NULL, NULL);
2393 g_return_val_if_fail (end_orig != NULL, NULL);
2394 g_return_val_if_fail (_gtk_text_iter_get_btree (start_orig) ==
2395 _gtk_text_iter_get_btree (end_orig), NULL);
2397 start = *start_orig;
2400 gtk_text_iter_order (&start, &end);
2402 retval = g_string_new (NULL);
2404 end_seg = _gtk_text_iter_get_indexable_segment (&end);
2406 seg = _gtk_text_iter_get_indexable_segment (&iter);
2407 while (seg != end_seg)
2409 copy_segment (retval, include_hidden, include_nonchars,
2412 _gtk_text_iter_forward_indexable_segment (&iter);
2414 seg = _gtk_text_iter_get_indexable_segment (&iter);
2417 copy_segment (retval, include_hidden, include_nonchars, &iter, &end);
2420 g_string_free (retval, FALSE);
2425 _gtk_text_btree_line_count (GtkTextBTree *tree)
2427 /* Subtract bogus line at the end; we return a count
2429 return tree->root_node->num_lines - 1;
2433 _gtk_text_btree_char_count (GtkTextBTree *tree)
2435 /* Exclude newline in bogus last line and the
2436 * one in the last line that is after the end iterator
2438 return tree->root_node->num_chars - 2;
2441 #define LOTSA_TAGS 1000
2443 _gtk_text_btree_char_is_invisible (const GtkTextIter *iter)
2445 gboolean invisible = FALSE; /* if nobody says otherwise, it's visible */
2447 int deftagCnts[LOTSA_TAGS] = { 0, };
2448 int *tagCnts = deftagCnts;
2449 GtkTextTag *deftags[LOTSA_TAGS];
2450 GtkTextTag **tags = deftags;
2452 GtkTextBTreeNode *node;
2453 GtkTextLine *siblingline;
2454 GtkTextLineSegment *seg;
2461 line = _gtk_text_iter_get_text_line (iter);
2462 tree = _gtk_text_iter_get_btree (iter);
2463 byte_index = gtk_text_iter_get_line_index (iter);
2465 numTags = gtk_text_tag_table_get_size (tree->table);
2467 /* almost always avoid malloc, so stay out of system calls */
2468 if (LOTSA_TAGS < numTags)
2470 tagCnts = g_new0 (int, numTags);
2471 tags = g_new (GtkTextTag*, numTags);
2475 * Record tag toggles within the line of indexPtr but preceding
2479 for (index = 0, seg = line->segments;
2480 (index + seg->byte_count) <= byte_index; /* segfault here means invalid index */
2481 index += seg->byte_count, seg = seg->next)
2483 if ((seg->type == >k_text_toggle_on_type)
2484 || (seg->type == >k_text_toggle_off_type))
2486 tag = seg->body.toggle.info->tag;
2487 if (tag->invisible_set && tag->values->invisible)
2489 tags[tag->priority] = tag;
2490 tagCnts[tag->priority]++;
2496 * Record toggles for tags in lines that are predecessors of
2497 * line but under the same level-0 GtkTextBTreeNode.
2500 for (siblingline = line->parent->children.line;
2501 siblingline != line;
2502 siblingline = siblingline->next)
2504 for (seg = siblingline->segments; seg != NULL;
2507 if ((seg->type == >k_text_toggle_on_type)
2508 || (seg->type == >k_text_toggle_off_type))
2510 tag = seg->body.toggle.info->tag;
2511 if (tag->invisible_set && tag->values->invisible)
2513 tags[tag->priority] = tag;
2514 tagCnts[tag->priority]++;
2521 * For each GtkTextBTreeNode in the ancestry of this line, record tag toggles
2522 * for all siblings that precede that GtkTextBTreeNode.
2525 for (node = line->parent; node->parent != NULL;
2526 node = node->parent)
2528 GtkTextBTreeNode *siblingPtr;
2531 for (siblingPtr = node->parent->children.node;
2532 siblingPtr != node; siblingPtr = siblingPtr->next)
2534 for (summary = siblingPtr->summary; summary != NULL;
2535 summary = summary->next)
2537 if (summary->toggle_count & 1)
2539 tag = summary->info->tag;
2540 if (tag->invisible_set && tag->values->invisible)
2542 tags[tag->priority] = tag;
2543 tagCnts[tag->priority] += summary->toggle_count;
2551 * Now traverse from highest priority to lowest,
2552 * take invisible value from first odd count (= on)
2555 for (i = numTags-1; i >=0; i--)
2559 /* FIXME not sure this should be if 0 */
2561 #ifndef ALWAYS_SHOW_SELECTION
2562 /* who would make the selection invisible? */
2563 if ((tag == tkxt->seltag)
2564 && !(tkxt->flags & GOT_FOCUS))
2570 invisible = tags[i]->values->invisible;
2575 if (LOTSA_TAGS < numTags)
2590 redisplay_region (GtkTextBTree *tree,
2591 const GtkTextIter *start,
2592 const GtkTextIter *end)
2595 GtkTextLine *start_line, *end_line;
2597 if (gtk_text_iter_compare (start, end) > 0)
2599 const GtkTextIter *tmp = start;
2604 start_line = _gtk_text_iter_get_text_line (start);
2605 end_line = _gtk_text_iter_get_text_line (end);
2608 while (view != NULL)
2610 gint start_y, end_y;
2611 GtkTextLineData *ld;
2613 start_y = _gtk_text_btree_find_line_top (tree, start_line, view->view_id);
2615 if (end_line == start_line)
2618 end_y = _gtk_text_btree_find_line_top (tree, end_line, view->view_id);
2620 ld = _gtk_text_line_get_data (end_line, view->view_id);
2622 end_y += ld->height;
2624 gtk_text_layout_changed (view->layout, start_y,
2633 redisplay_mark (GtkTextLineSegment *mark)
2638 _gtk_text_btree_get_iter_at_mark (mark->body.mark.tree,
2640 mark->body.mark.obj);
2643 gtk_text_iter_forward_char (&end);
2645 DV (g_print ("invalidating due to moving visible mark (%s)\n", G_STRLOC));
2646 _gtk_text_btree_invalidate_region (mark->body.mark.tree,
2651 redisplay_mark_if_visible (GtkTextLineSegment *mark)
2653 if (!mark->body.mark.visible)
2656 redisplay_mark (mark);
2660 ensure_not_off_end (GtkTextBTree *tree,
2661 GtkTextLineSegment *mark,
2664 if (gtk_text_iter_get_line (iter) ==
2665 _gtk_text_btree_line_count (tree))
2666 gtk_text_iter_backward_char (iter);
2669 static GtkTextLineSegment*
2670 real_set_mark (GtkTextBTree *tree,
2671 GtkTextMark *existing_mark,
2673 gboolean left_gravity,
2674 const GtkTextIter *where,
2675 gboolean should_exist,
2676 gboolean redraw_selections)
2678 GtkTextLineSegment *mark;
2681 g_return_val_if_fail (tree != NULL, NULL);
2682 g_return_val_if_fail (where != NULL, NULL);
2683 g_return_val_if_fail (_gtk_text_iter_get_btree (where) == tree, NULL);
2686 mark = existing_mark->segment;
2687 else if (name != NULL)
2688 mark = g_hash_table_lookup (tree->mark_table,
2693 if (should_exist && mark == NULL)
2695 g_warning ("No mark `%s' exists!", name);
2699 /* OK if !should_exist and it does already exist, in that case
2705 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2706 _gtk_text_iter_check (&iter);
2710 if (redraw_selections &&
2711 (mark == tree->insert_mark->segment ||
2712 mark == tree->selection_bound_mark->segment))
2714 GtkTextIter old_pos;
2716 _gtk_text_btree_get_iter_at_mark (tree, &old_pos,
2717 mark->body.mark.obj);
2718 redisplay_region (tree, &old_pos, where);
2722 * don't let visible marks be after the final newline of the
2726 if (mark->body.mark.visible)
2728 ensure_not_off_end (tree, mark, &iter);
2731 /* Redraw the mark's old location. */
2732 redisplay_mark_if_visible (mark);
2734 /* Unlink mark from its current location.
2735 This could hose our iterator... */
2736 gtk_text_btree_unlink_segment (tree, mark,
2737 mark->body.mark.line);
2738 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2739 g_assert (mark->body.mark.line == _gtk_text_iter_get_text_line (&iter));
2741 segments_changed (tree); /* make sure the iterator recomputes its
2746 mark = _gtk_mark_segment_new (tree,
2750 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2752 if (mark->body.mark.name)
2753 g_hash_table_insert (tree->mark_table,
2754 mark->body.mark.name,
2758 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2759 _gtk_text_iter_check (&iter);
2761 /* Link mark into new location */
2762 gtk_text_btree_link_segment (mark, &iter);
2764 /* Invalidate some iterators. */
2765 segments_changed (tree);
2768 * update the screen at the mark's new location.
2771 redisplay_mark_if_visible (mark);
2773 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2774 _gtk_text_iter_check (&iter);
2776 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2777 _gtk_text_btree_check (tree);
2784 _gtk_text_btree_set_mark (GtkTextBTree *tree,
2785 GtkTextMark *existing_mark,
2787 gboolean left_gravity,
2788 const GtkTextIter *iter,
2789 gboolean should_exist)
2791 GtkTextLineSegment *seg;
2793 seg = real_set_mark (tree, existing_mark,
2794 name, left_gravity, iter, should_exist,
2797 return seg ? seg->body.mark.obj : NULL;
2801 _gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2805 GtkTextIter tmp_start, tmp_end;
2807 _gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2809 _gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2810 tree->selection_bound_mark);
2812 if (gtk_text_iter_equal (&tmp_start, &tmp_end))
2824 gtk_text_iter_order (&tmp_start, &tmp_end);
2837 _gtk_text_btree_place_cursor (GtkTextBTree *tree,
2838 const GtkTextIter *iter)
2840 _gtk_text_btree_select_range (tree, iter, iter);
2844 _gtk_text_btree_select_range (GtkTextBTree *tree,
2845 const GtkTextIter *ins,
2846 const GtkTextIter *bound)
2848 GtkTextIter start, end;
2850 if (_gtk_text_btree_get_selection_bounds (tree, &start, &end))
2851 redisplay_region (tree, &start, &end);
2853 /* Move insert AND selection_bound before we redisplay */
2854 real_set_mark (tree, tree->insert_mark,
2855 "insert", FALSE, ins, TRUE, FALSE);
2856 real_set_mark (tree, tree->selection_bound_mark,
2857 "selection_bound", FALSE, bound, TRUE, FALSE);
2859 redisplay_region (tree, ins, bound);
2864 _gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2869 g_return_if_fail (tree != NULL);
2870 g_return_if_fail (name != NULL);
2872 mark = g_hash_table_lookup (tree->mark_table,
2875 _gtk_text_btree_remove_mark (tree, mark);
2879 _gtk_text_btree_release_mark_segment (GtkTextBTree *tree,
2880 GtkTextLineSegment *segment)
2883 if (segment->body.mark.name)
2884 g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2886 segment->body.mark.tree = NULL;
2887 segment->body.mark.line = NULL;
2889 /* Remove the ref on the mark, which frees segment as a side effect
2890 * if this is the last reference.
2892 g_object_unref (segment->body.mark.obj);
2896 _gtk_text_btree_remove_mark (GtkTextBTree *tree,
2899 GtkTextLineSegment *segment;
2901 g_return_if_fail (mark != NULL);
2902 g_return_if_fail (tree != NULL);
2904 segment = mark->segment;
2906 if (segment->body.mark.not_deleteable)
2908 g_warning ("Can't delete special mark `%s'", segment->body.mark.name);
2912 /* This calls cleanup_line and segments_changed */
2913 gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2915 _gtk_text_btree_release_mark_segment (tree, segment);
2919 _gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2920 GtkTextMark *segment)
2922 return segment == tree->insert_mark;
2926 _gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2927 GtkTextMark *segment)
2929 return segment == tree->selection_bound_mark;
2933 _gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2936 GtkTextLineSegment *seg;
2938 g_return_val_if_fail (tree != NULL, NULL);
2939 g_return_val_if_fail (name != NULL, NULL);
2941 seg = g_hash_table_lookup (tree->mark_table, name);
2943 return seg ? seg->body.mark.obj : NULL;
2947 * gtk_text_mark_set_visible:
2948 * @mark: a #GtkTextMark
2949 * @setting: visibility of mark
2951 * Sets the visibility of @mark; the insertion point is normally
2952 * visible, i.e. you can see it as a vertical bar. Also, the text
2953 * widget uses a visible mark to indicate where a drop will occur when
2954 * dragging-and-dropping text. Most other marks are not visible.
2955 * Marks are not visible by default.
2959 gtk_text_mark_set_visible (GtkTextMark *mark,
2962 GtkTextLineSegment *seg;
2964 g_return_if_fail (mark != NULL);
2966 seg = mark->segment;
2968 if (seg->body.mark.visible == setting)
2972 seg->body.mark.visible = setting;
2974 redisplay_mark (seg);
2979 _gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
2982 GtkTextBTreeNode *node;
2983 GtkTextTagInfo *info;
2985 g_return_val_if_fail (tree != NULL, NULL);
2989 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2994 if (info->tag_root == NULL)
2997 node = info->tag_root;
2999 /* We know the tag root has instances of the given
3002 continue_outer_loop:
3003 g_assert (node != NULL);
3004 while (node->level > 0)
3006 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
3007 node = node->children.node;
3008 while (node != NULL)
3010 if (gtk_text_btree_node_has_tag (node, tag))
3011 goto continue_outer_loop;
3015 g_assert (node != NULL);
3018 g_assert (node != NULL); /* The tag summaries said some node had
3021 g_assert (node->level == 0);
3023 return node->children.line;
3027 /* Looking for any tag at all (tag == NULL).
3028 Unfortunately this can't be done in a simple and efficient way
3029 right now; so I'm just going to return the
3030 first line in the btree. FIXME */
3031 return _gtk_text_btree_get_line (tree, 0, NULL);
3036 _gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
3039 GtkTextBTreeNode *node;
3040 GtkTextBTreeNode *last_node;
3042 GtkTextTagInfo *info;
3044 g_return_val_if_fail (tree != NULL, NULL);
3048 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3050 if (info->tag_root == NULL)
3053 node = info->tag_root;
3054 /* We know the tag root has instances of the given
3057 while (node->level > 0)
3059 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
3061 node = node->children.node;
3062 while (node != NULL)
3064 if (gtk_text_btree_node_has_tag (node, tag))
3072 g_assert (node != NULL); /* The tag summaries said some node had
3075 g_assert (node->level == 0);
3077 /* Find the last line in this node */
3078 line = node->children.line;
3079 while (line->next != NULL)
3086 /* This search can't be done efficiently at the moment,
3087 at least not without complexity.
3088 So, we just return the last line.
3090 return _gtk_text_btree_get_end_iter_line (tree);
3100 _gtk_text_line_get_number (GtkTextLine *line)
3103 GtkTextBTreeNode *node, *parent, *node2;
3107 * First count how many lines precede this one in its level-0
3111 node = line->parent;
3113 for (line2 = node->children.line; line2 != line;
3114 line2 = line2->next)
3118 g_error ("gtk_text_btree_line_number couldn't find line");
3124 * Now work up through the levels of the tree one at a time,
3125 * counting how many lines are in GtkTextBTreeNodes preceding the current
3129 for (parent = node->parent ; parent != NULL;
3130 node = parent, parent = parent->parent)
3132 for (node2 = parent->children.node; node2 != node;
3133 node2 = node2->next)
3137 g_error ("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
3139 index += node2->num_lines;
3145 static GtkTextLineSegment*
3146 find_toggle_segment_before_char (GtkTextLine *line,
3150 GtkTextLineSegment *seg;
3151 GtkTextLineSegment *toggle_seg;
3156 seg = line->segments;
3157 while ( (index + seg->char_count) <= char_in_line )
3159 if (((seg->type == >k_text_toggle_on_type)
3160 || (seg->type == >k_text_toggle_off_type))
3161 && (seg->body.toggle.info->tag == tag))
3164 index += seg->char_count;
3171 static GtkTextLineSegment*
3172 find_toggle_segment_before_byte (GtkTextLine *line,
3176 GtkTextLineSegment *seg;
3177 GtkTextLineSegment *toggle_seg;
3182 seg = line->segments;
3183 while ( (index + seg->byte_count) <= byte_in_line )
3185 if (((seg->type == >k_text_toggle_on_type)
3186 || (seg->type == >k_text_toggle_off_type))
3187 && (seg->body.toggle.info->tag == tag))
3190 index += seg->byte_count;
3198 find_toggle_outside_current_line (GtkTextLine *line,
3202 GtkTextBTreeNode *node;
3203 GtkTextLine *sibling_line;
3204 GtkTextLineSegment *seg;
3205 GtkTextLineSegment *toggle_seg;
3207 GtkTextTagInfo *info = NULL;
3210 * No toggle in this line. Look for toggles for the tag in lines
3211 * that are predecessors of line but under the same
3212 * level-0 GtkTextBTreeNode.
3215 sibling_line = line->parent->children.line;
3216 while (sibling_line != line)
3218 seg = sibling_line->segments;
3221 if (((seg->type == >k_text_toggle_on_type)
3222 || (seg->type == >k_text_toggle_off_type))
3223 && (seg->body.toggle.info->tag == tag))
3229 sibling_line = sibling_line->next;
3232 if (toggle_seg != NULL)
3233 return (toggle_seg->type == >k_text_toggle_on_type);
3236 * No toggle in this GtkTextBTreeNode. Scan upwards through the ancestors of
3237 * this GtkTextBTreeNode, counting the number of toggles of the given tag in
3238 * siblings that precede that GtkTextBTreeNode.
3241 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3247 node = line->parent;
3248 while (node->parent != NULL)
3250 GtkTextBTreeNode *sibling_node;
3252 sibling_node = node->parent->children.node;
3253 while (sibling_node != node)
3257 summary = sibling_node->summary;
3258 while (summary != NULL)
3260 if (summary->info == info)
3261 toggles += summary->toggle_count;
3263 summary = summary->next;
3266 sibling_node = sibling_node->next;
3269 if (node == info->tag_root)
3272 node = node->parent;
3276 * An odd number of toggles means that the tag is present at the
3280 return (toggles & 1) != 0;
3283 /* FIXME this function is far too slow, for no good reason. */
3285 _gtk_text_line_char_has_tag (GtkTextLine *line,
3290 GtkTextLineSegment *toggle_seg;
3292 g_return_val_if_fail (line != NULL, FALSE);
3295 * Check for toggles for the tag in the line but before
3296 * the char. If there is one, its type indicates whether or
3297 * not the character is tagged.
3300 toggle_seg = find_toggle_segment_before_char (line, char_in_line, tag);
3302 if (toggle_seg != NULL)
3303 return (toggle_seg->type == >k_text_toggle_on_type);
3305 return find_toggle_outside_current_line (line, tree, tag);
3309 _gtk_text_line_byte_has_tag (GtkTextLine *line,
3314 GtkTextLineSegment *toggle_seg;
3316 g_return_val_if_fail (line != NULL, FALSE);
3319 * Check for toggles for the tag in the line but before
3320 * the char. If there is one, its type indicates whether or
3321 * not the character is tagged.
3324 toggle_seg = find_toggle_segment_before_byte (line, byte_in_line, tag);
3326 if (toggle_seg != NULL)
3327 return (toggle_seg->type == >k_text_toggle_on_type);
3329 return find_toggle_outside_current_line (line, tree, tag);
3333 _gtk_text_line_is_last (GtkTextLine *line,
3336 return line == get_last_line (tree);
3340 ensure_end_iter_line (GtkTextBTree *tree)
3342 if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
3347 /* n_lines is without the magic line at the end */
3348 n_lines = _gtk_text_btree_line_count (tree);
3350 g_assert (n_lines >= 1);
3352 tree->end_iter_line = _gtk_text_btree_get_line_no_last (tree, -1, &real_line);
3354 tree->end_iter_line_stamp = tree->chars_changed_stamp;
3359 ensure_end_iter_segment (GtkTextBTree *tree)
3361 if (tree->end_iter_segment_stamp != tree->segments_changed_stamp)
3363 GtkTextLineSegment *seg;
3364 GtkTextLineSegment *last_with_chars;
3366 ensure_end_iter_line (tree);
3368 last_with_chars = NULL;
3370 seg = tree->end_iter_line->segments;
3373 if (seg->char_count > 0)
3374 last_with_chars = seg;
3378 tree->end_iter_segment = last_with_chars;
3380 /* We know the last char in the last line is '\n' */
3381 tree->end_iter_segment_byte_index = last_with_chars->byte_count - 1;
3382 tree->end_iter_segment_char_offset = last_with_chars->char_count - 1;
3384 tree->end_iter_segment_stamp = tree->segments_changed_stamp;
3386 g_assert (tree->end_iter_segment->type == >k_text_char_type);
3387 g_assert (tree->end_iter_segment->body.chars[tree->end_iter_segment_byte_index] == '\n');
3392 _gtk_text_line_contains_end_iter (GtkTextLine *line,
3395 ensure_end_iter_line (tree);
3397 return line == tree->end_iter_line;
3401 _gtk_text_btree_is_end (GtkTextBTree *tree,
3403 GtkTextLineSegment *seg,
3407 g_return_val_if_fail (byte_index >= 0 || char_offset >= 0, FALSE);
3409 /* Do this first to avoid walking segments in most cases */
3410 if (!_gtk_text_line_contains_end_iter (line, tree))
3413 ensure_end_iter_segment (tree);
3415 if (seg != tree->end_iter_segment)
3418 if (byte_index >= 0)
3419 return byte_index == tree->end_iter_segment_byte_index;
3421 return char_offset == tree->end_iter_segment_char_offset;
3425 _gtk_text_line_next (GtkTextLine *line)
3427 GtkTextBTreeNode *node;
3429 if (line->next != NULL)
3434 * This was the last line associated with the particular parent
3435 * GtkTextBTreeNode. Search up the tree for the next GtkTextBTreeNode,
3436 * then search down from that GtkTextBTreeNode to find the first
3440 node = line->parent;
3441 while (node != NULL && node->next == NULL)
3442 node = node->parent;
3448 while (node->level > 0)
3450 node = node->children.node;
3453 g_assert (node->children.line != line);
3455 return node->children.line;
3460 _gtk_text_line_next_excluding_last (GtkTextLine *line)
3464 next = _gtk_text_line_next (line);
3466 /* If we were on the end iter line, we can't go to
3469 if (next && next->next == NULL && /* these checks are optimization only */
3470 _gtk_text_line_next (next) == NULL)
3477 _gtk_text_line_previous (GtkTextLine *line)
3479 GtkTextBTreeNode *node;
3480 GtkTextBTreeNode *node2;
3484 * Find the line under this GtkTextBTreeNode just before the starting line.
3486 prev = line->parent->children.line; /* First line at leaf */
3487 while (prev != line)
3489 if (prev->next == line)
3495 g_error ("gtk_text_btree_previous_line ran out of lines");
3499 * This was the first line associated with the particular parent
3500 * GtkTextBTreeNode. Search up the tree for the previous GtkTextBTreeNode,
3501 * then search down from that GtkTextBTreeNode to find its last line.
3503 for (node = line->parent; ; node = node->parent)
3505 if (node == NULL || node->parent == NULL)
3507 else if (node != node->parent->children.node)
3511 for (node2 = node->parent->children.node; ;
3512 node2 = node2->children.node)
3514 while (node2->next != node)
3515 node2 = node2->next;
3517 if (node2->level == 0)
3523 for (prev = node2->children.line ; ; prev = prev->next)
3525 if (prev->next == NULL)
3529 g_assert_not_reached ();
3535 _gtk_text_line_data_new (GtkTextLayout *layout,
3538 GtkTextLineData *line_data;
3540 line_data = g_new (GtkTextLineData, 1);
3542 line_data->view_id = layout;
3543 line_data->next = NULL;
3544 line_data->width = 0;
3545 line_data->height = 0;
3546 line_data->valid = FALSE;
3552 _gtk_text_line_add_data (GtkTextLine *line,
3553 GtkTextLineData *data)
3555 g_return_if_fail (line != NULL);
3556 g_return_if_fail (data != NULL);
3557 g_return_if_fail (data->view_id != NULL);
3561 data->next = line->views;
3571 _gtk_text_line_remove_data (GtkTextLine *line,
3574 GtkTextLineData *prev;
3575 GtkTextLineData *iter;
3577 g_return_val_if_fail (line != NULL, NULL);
3578 g_return_val_if_fail (view_id != NULL, NULL);
3582 while (iter != NULL)
3584 if (iter->view_id == view_id)
3593 prev->next = iter->next;
3595 line->views = iter->next;
3604 _gtk_text_line_get_data (GtkTextLine *line,
3607 GtkTextLineData *iter;
3609 g_return_val_if_fail (line != NULL, NULL);
3610 g_return_val_if_fail (view_id != NULL, NULL);
3613 while (iter != NULL)
3615 if (iter->view_id == view_id)
3624 _gtk_text_line_invalidate_wrap (GtkTextLine *line,
3625 GtkTextLineData *ld)
3627 /* For now this is totally unoptimized. FIXME?
3629 We could probably optimize the case where the width removed
3630 is less than the max width for the parent node,
3631 and the case where the height is unchanged when we re-wrap.
3634 g_return_if_fail (ld != NULL);
3637 gtk_text_btree_node_invalidate_upward (line->parent, ld->view_id);
3641 _gtk_text_line_char_count (GtkTextLine *line)
3643 GtkTextLineSegment *seg;
3647 seg = line->segments;
3650 size += seg->char_count;
3657 _gtk_text_line_byte_count (GtkTextLine *line)
3659 GtkTextLineSegment *seg;
3663 seg = line->segments;
3666 size += seg->byte_count;
3674 _gtk_text_line_char_index (GtkTextLine *target_line)
3676 GSList *node_stack = NULL;
3677 GtkTextBTreeNode *iter;
3681 /* Push all our parent nodes onto a stack */
3682 iter = target_line->parent;
3684 g_assert (iter != NULL);
3686 while (iter != NULL)
3688 node_stack = g_slist_prepend (node_stack, iter);
3690 iter = iter->parent;
3693 /* Check that we have the root node on top of the stack. */
3694 g_assert (node_stack != NULL &&
3695 node_stack->data != NULL &&
3696 ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3698 /* Add up chars in all nodes before the nodes in our stack.
3702 iter = node_stack->data;
3703 while (iter != NULL)
3705 GtkTextBTreeNode *child_iter;
3706 GtkTextBTreeNode *next_node;
3708 next_node = node_stack->next ?
3709 node_stack->next->data : NULL;
3710 node_stack = g_slist_remove (node_stack, node_stack->data);
3712 if (iter->level == 0)
3714 /* stack should be empty when we're on the last node */
3715 g_assert (node_stack == NULL);
3716 break; /* Our children are now lines */
3719 g_assert (next_node != NULL);
3720 g_assert (iter != NULL);
3721 g_assert (next_node->parent == iter);
3723 /* Add up chars before us in the tree */
3724 child_iter = iter->children.node;
3725 while (child_iter != next_node)
3727 g_assert (child_iter != NULL);
3729 num_chars += child_iter->num_chars;
3731 child_iter = child_iter->next;
3737 g_assert (iter != NULL);
3738 g_assert (iter == target_line->parent);
3740 /* Since we don't store char counts in lines, only in segments, we
3741 have to iterate over the lines adding up segment char counts
3742 until we find our line. */
3743 line = iter->children.line;
3744 while (line != target_line)
3746 g_assert (line != NULL);
3748 num_chars += _gtk_text_line_char_count (line);
3753 g_assert (line == target_line);
3759 _gtk_text_line_byte_to_segment (GtkTextLine *line,
3763 GtkTextLineSegment *seg;
3766 g_return_val_if_fail (line != NULL, NULL);
3768 offset = byte_offset;
3769 seg = line->segments;
3771 while (offset >= seg->byte_count)
3773 g_assert (seg != NULL); /* means an invalid byte index */
3774 offset -= seg->byte_count;
3779 *seg_offset = offset;
3785 _gtk_text_line_char_to_segment (GtkTextLine *line,
3789 GtkTextLineSegment *seg;
3792 g_return_val_if_fail (line != NULL, NULL);
3794 offset = char_offset;
3795 seg = line->segments;
3797 while (offset >= seg->char_count)
3799 g_assert (seg != NULL); /* means an invalid char index */
3800 offset -= seg->char_count;
3805 *seg_offset = offset;
3811 _gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3815 GtkTextLineSegment *seg;
3818 g_return_val_if_fail (line != NULL, NULL);
3820 offset = byte_offset;
3821 seg = line->segments;
3823 while (offset > 0 && offset >= seg->byte_count)
3825 g_assert (seg != NULL); /* means an invalid byte index */
3826 offset -= seg->byte_count;
3831 *seg_offset = offset;
3837 _gtk_text_line_char_to_any_segment (GtkTextLine *line,
3841 GtkTextLineSegment *seg;
3844 g_return_val_if_fail (line != NULL, NULL);
3846 offset = char_offset;
3847 seg = line->segments;
3849 while (offset > 0 && offset >= seg->char_count)
3851 g_assert (seg != NULL); /* means an invalid byte index */
3852 offset -= seg->char_count;
3857 *seg_offset = offset;
3863 _gtk_text_line_byte_to_char (GtkTextLine *line,
3867 GtkTextLineSegment *seg;
3869 g_return_val_if_fail (line != NULL, 0);
3870 g_return_val_if_fail (byte_offset >= 0, 0);
3873 seg = line->segments;
3874 while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3875 the next segment) */
3877 g_assert (seg != NULL); /* our byte_index was bogus if this happens */
3879 byte_offset -= seg->byte_count;
3880 char_offset += seg->char_count;
3885 g_assert (seg != NULL);
3887 /* Now byte_offset is the offset into the current segment,
3888 and char_offset is the start of the current segment.
3889 Optimize the case where no chars use > 1 byte */
3890 if (seg->byte_count == seg->char_count)
3891 return char_offset + byte_offset;
3894 if (seg->type == >k_text_char_type)
3895 return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3898 g_assert (seg->char_count == 1);
3899 g_assert (byte_offset == 0);
3907 _gtk_text_line_char_to_byte (GtkTextLine *line,
3910 g_warning ("FIXME not implemented");
3915 /* FIXME sync with char_locate (or figure out a clean
3916 way to merge the two functions) */
3918 _gtk_text_line_byte_locate (GtkTextLine *line,
3920 GtkTextLineSegment **segment,
3921 GtkTextLineSegment **any_segment,
3922 gint *seg_byte_offset,
3923 gint *line_byte_offset)
3925 GtkTextLineSegment *seg;
3926 GtkTextLineSegment *after_last_indexable;
3927 GtkTextLineSegment *last_indexable;
3931 g_return_val_if_fail (line != NULL, FALSE);
3932 g_return_val_if_fail (byte_offset >= 0, FALSE);
3935 *any_segment = NULL;
3938 offset = byte_offset;
3940 last_indexable = NULL;
3941 after_last_indexable = line->segments;
3942 seg = line->segments;
3944 /* The loop ends when we're inside a segment;
3945 last_indexable refers to the last segment
3946 we passed entirely. */
3947 while (seg && offset >= seg->byte_count)
3949 if (seg->char_count > 0)
3951 offset -= seg->byte_count;
3952 bytes_in_line += seg->byte_count;
3953 last_indexable = seg;
3954 after_last_indexable = last_indexable->next;
3962 /* We went off the end of the line */
3964 g_warning ("%s: byte index off the end of the line", G_STRLOC);
3971 if (after_last_indexable != NULL)
3972 *any_segment = after_last_indexable;
3974 *any_segment = *segment;
3977 /* Override any_segment if we're in the middle of a segment. */
3979 *any_segment = *segment;
3981 *seg_byte_offset = offset;
3983 g_assert (*segment != NULL);
3984 g_assert (*any_segment != NULL);
3985 g_assert (*seg_byte_offset < (*segment)->byte_count);
3987 *line_byte_offset = bytes_in_line + *seg_byte_offset;
3992 /* FIXME sync with byte_locate (or figure out a clean
3993 way to merge the two functions) */
3995 _gtk_text_line_char_locate (GtkTextLine *line,
3997 GtkTextLineSegment **segment,
3998 GtkTextLineSegment **any_segment,
3999 gint *seg_char_offset,
4000 gint *line_char_offset)
4002 GtkTextLineSegment *seg;
4003 GtkTextLineSegment *after_last_indexable;
4004 GtkTextLineSegment *last_indexable;
4008 g_return_val_if_fail (line != NULL, FALSE);
4009 g_return_val_if_fail (char_offset >= 0, FALSE);
4012 *any_segment = NULL;
4015 offset = char_offset;
4017 last_indexable = NULL;
4018 after_last_indexable = line->segments;
4019 seg = line->segments;
4021 /* The loop ends when we're inside a segment;
4022 last_indexable refers to the last segment
4023 we passed entirely. */
4024 while (seg && offset >= seg->char_count)
4026 if (seg->char_count > 0)
4028 offset -= seg->char_count;
4029 chars_in_line += seg->char_count;
4030 last_indexable = seg;
4031 after_last_indexable = last_indexable->next;
4039 /* end of the line */
4041 g_warning ("%s: char offset off the end of the line", G_STRLOC);
4048 if (after_last_indexable != NULL)
4049 *any_segment = after_last_indexable;
4051 *any_segment = *segment;
4054 /* Override any_segment if we're in the middle of a segment. */
4056 *any_segment = *segment;
4058 *seg_char_offset = offset;
4060 g_assert (*segment != NULL);
4061 g_assert (*any_segment != NULL);
4062 g_assert (*seg_char_offset < (*segment)->char_count);
4064 *line_char_offset = chars_in_line + *seg_char_offset;
4070 _gtk_text_line_byte_to_char_offsets (GtkTextLine *line,
4072 gint *line_char_offset,
4073 gint *seg_char_offset)
4075 GtkTextLineSegment *seg;
4078 g_return_if_fail (line != NULL);
4079 g_return_if_fail (byte_offset >= 0);
4081 *line_char_offset = 0;
4083 offset = byte_offset;
4084 seg = line->segments;
4086 while (offset >= seg->byte_count)
4088 offset -= seg->byte_count;
4089 *line_char_offset += seg->char_count;
4091 g_assert (seg != NULL); /* means an invalid char offset */
4094 g_assert (seg->char_count > 0); /* indexable. */
4096 /* offset is now the number of bytes into the current segment we
4097 * want to go. Count chars into the current segment.
4100 if (seg->type == >k_text_char_type)
4102 *seg_char_offset = g_utf8_strlen (seg->body.chars, offset);
4104 g_assert (*seg_char_offset < seg->char_count);
4106 *line_char_offset += *seg_char_offset;
4110 g_assert (offset == 0);
4111 *seg_char_offset = 0;
4116 _gtk_text_line_char_to_byte_offsets (GtkTextLine *line,
4118 gint *line_byte_offset,
4119 gint *seg_byte_offset)
4121 GtkTextLineSegment *seg;
4124 g_return_if_fail (line != NULL);
4125 g_return_if_fail (char_offset >= 0);
4127 *line_byte_offset = 0;
4129 offset = char_offset;
4130 seg = line->segments;
4132 while (offset >= seg->char_count)
4134 offset -= seg->char_count;
4135 *line_byte_offset += seg->byte_count;
4137 g_assert (seg != NULL); /* means an invalid char offset */
4140 g_assert (seg->char_count > 0); /* indexable. */
4142 /* offset is now the number of chars into the current segment we
4143 want to go. Count bytes into the current segment. */
4145 if (seg->type == >k_text_char_type)
4147 *seg_byte_offset = 0;
4151 const char * start = seg->body.chars + *seg_byte_offset;
4153 bytes = g_utf8_next_char (start) - start;
4154 *seg_byte_offset += bytes;
4158 g_assert (*seg_byte_offset < seg->byte_count);
4160 *line_byte_offset += *seg_byte_offset;
4164 g_assert (offset == 0);
4165 *seg_byte_offset = 0;
4170 node_compare (GtkTextBTreeNode *lhs,
4171 GtkTextBTreeNode *rhs)
4173 GtkTextBTreeNode *iter;
4174 GtkTextBTreeNode *node;
4175 GtkTextBTreeNode *common_parent;
4176 GtkTextBTreeNode *parent_of_lower;
4177 GtkTextBTreeNode *parent_of_higher;
4178 gboolean lhs_is_lower;
4179 GtkTextBTreeNode *lower;
4180 GtkTextBTreeNode *higher;
4182 /* This function assumes that lhs and rhs are not underneath each
4189 if (lhs->level < rhs->level)
4191 lhs_is_lower = TRUE;
4197 lhs_is_lower = FALSE;
4202 /* Algorithm: find common parent of lhs/rhs. Save the child nodes
4203 * of the common parent we used to reach the common parent; the
4204 * ordering of these child nodes in the child list is the ordering
4208 /* Get on the same level (may be on same level already) */
4210 while (node->level < higher->level)
4211 node = node->parent;
4213 g_assert (node->level == higher->level);
4215 g_assert (node != higher); /* Happens if lower is underneath higher */
4217 /* Go up until we have two children with a common parent.
4219 parent_of_lower = node;
4220 parent_of_higher = higher;
4222 while (parent_of_lower->parent != parent_of_higher->parent)
4224 parent_of_lower = parent_of_lower->parent;
4225 parent_of_higher = parent_of_higher->parent;
4228 g_assert (parent_of_lower->parent == parent_of_higher->parent);
4230 common_parent = parent_of_lower->parent;
4232 g_assert (common_parent != NULL);
4234 /* See which is first in the list of common_parent's children */
4235 iter = common_parent->children.node;
4236 while (iter != NULL)
4238 if (iter == parent_of_higher)
4240 /* higher is less than lower */
4243 return 1; /* lhs > rhs */
4247 else if (iter == parent_of_lower)
4249 /* lower is less than higher */
4252 return -1; /* lhs < rhs */
4260 g_assert_not_reached ();
4264 /* remember that tag == NULL means "any tag" */
4266 _gtk_text_line_next_could_contain_tag (GtkTextLine *line,
4270 GtkTextBTreeNode *node;
4271 GtkTextTagInfo *info;
4272 gboolean below_tag_root;
4274 g_return_val_if_fail (line != NULL, NULL);
4276 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4277 _gtk_text_btree_check (tree);
4281 /* Right now we can only offer linear-search if the user wants
4282 * to know about any tag toggle at all.
4284 return _gtk_text_line_next_excluding_last (line);
4287 /* Our tag summaries only have node precision, not line
4288 * precision. This means that if any line under a node could contain a
4289 * tag, then any of the others could also contain a tag.
4291 * In the future we could have some mechanism to keep track of how
4292 * many toggles we've found under a node so far, since we have a
4293 * count of toggles under the node. But for now I'm going with KISS.
4296 /* return same-node line, if any. */
4300 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4304 if (info->tag_root == NULL)
4307 if (info->tag_root == line->parent)
4308 return NULL; /* we were at the last line under the tag root */
4310 /* We need to go up out of this node, and on to the next one with
4311 toggles for the target tag. If we're below the tag root, we need to
4312 find the next node below the tag root that has tag summaries. If
4313 we're not below the tag root, we need to see if the tag root is
4314 after us in the tree, and if so, return the first line underneath
4317 node = line->parent;
4318 below_tag_root = FALSE;
4319 while (node != NULL)
4321 if (node == info->tag_root)
4323 below_tag_root = TRUE;
4327 node = node->parent;
4332 node = line->parent;
4333 while (node != info->tag_root)
4335 if (node->next == NULL)
4336 node = node->parent;
4341 if (gtk_text_btree_node_has_tag (node, tag))
4351 ordering = node_compare (line->parent, info->tag_root);
4355 /* Tag root is ahead of us, so search there. */
4356 node = info->tag_root;
4361 /* Tag root is after us, so no more lines that
4362 * could contain the tag.
4367 g_assert_not_reached ();
4372 g_assert (node != NULL);
4374 /* We have to find the first sub-node of this node that contains
4378 while (node->level > 0)
4380 g_assert (node != NULL); /* If this fails, it likely means an
4381 incorrect tag summary led us on a
4382 wild goose chase down this branch of
4384 node = node->children.node;
4385 while (node != NULL)
4387 if (gtk_text_btree_node_has_tag (node, tag))
4393 g_assert (node != NULL);
4394 g_assert (node->level == 0);
4396 return node->children.line;
4400 prev_line_under_node (GtkTextBTreeNode *node,
4405 prev = node->children.line;
4411 while (prev->next != line)
4421 _gtk_text_line_previous_could_contain_tag (GtkTextLine *line,
4425 GtkTextBTreeNode *node;
4426 GtkTextBTreeNode *found_node = NULL;
4427 GtkTextTagInfo *info;
4428 gboolean below_tag_root;
4430 GtkTextBTreeNode *line_ancestor;
4431 GtkTextBTreeNode *line_ancestor_parent;
4433 /* See next_could_contain_tag () for more extensive comments
4434 * on what's going on here.
4437 g_return_val_if_fail (line != NULL, NULL);
4439 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4440 _gtk_text_btree_check (tree);
4444 /* Right now we can only offer linear-search if the user wants
4445 * to know about any tag toggle at all.
4447 return _gtk_text_line_previous (line);
4450 /* Return same-node line, if any. */
4451 prev = prev_line_under_node (line->parent, line);
4455 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4459 if (info->tag_root == NULL)
4462 if (info->tag_root == line->parent)
4463 return NULL; /* we were at the first line under the tag root */
4465 /* Are we below the tag root */
4466 node = line->parent;
4467 below_tag_root = FALSE;
4468 while (node != NULL)
4470 if (node == info->tag_root)
4472 below_tag_root = TRUE;
4476 node = node->parent;
4481 /* Look for a previous node under this tag root that has our
4485 /* this assertion holds because line->parent is not the
4486 * tag root, we are below the tag root, and the tag
4489 g_assert (line->parent->parent != NULL);
4491 line_ancestor = line->parent;
4492 line_ancestor_parent = line->parent->parent;
4494 while (line_ancestor != info->tag_root)
4496 GSList *child_nodes = NULL;
4499 /* Create reverse-order list of nodes before
4502 if (line_ancestor_parent != NULL)
4503 node = line_ancestor_parent->children.node;
4505 node = line_ancestor;
4507 while (node != line_ancestor && node != NULL)
4509 child_nodes = g_slist_prepend (child_nodes, node);
4514 /* Try to find a node with our tag on it in the list */
4518 GtkTextBTreeNode *this_node = tmp->data;
4520 g_assert (this_node != line_ancestor);
4522 if (gtk_text_btree_node_has_tag (this_node, tag))
4524 found_node = this_node;
4525 g_slist_free (child_nodes);
4529 tmp = g_slist_next (tmp);
4532 g_slist_free (child_nodes);
4534 /* Didn't find anything on this level; go up one level. */
4535 line_ancestor = line_ancestor_parent;
4536 line_ancestor_parent = line_ancestor->parent;
4546 ordering = node_compare (line->parent, info->tag_root);
4550 /* Tag root is ahead of us, so no more lines
4557 /* Tag root is after us, so grab last tagged
4558 * line underneath the tag root.
4560 found_node = info->tag_root;
4564 g_assert_not_reached ();
4569 g_assert (found_node != NULL);
4571 /* We have to find the last sub-node of this node that contains
4576 while (node->level > 0)
4578 GSList *child_nodes = NULL;
4580 g_assert (node != NULL); /* If this fails, it likely means an
4581 incorrect tag summary led us on a
4582 wild goose chase down this branch of
4585 node = node->children.node;
4586 while (node != NULL)
4588 child_nodes = g_slist_prepend (child_nodes, node);
4592 node = NULL; /* detect failure to find a child node. */
4595 while (iter != NULL)
4597 if (gtk_text_btree_node_has_tag (iter->data, tag))
4599 /* recurse into this node. */
4604 iter = g_slist_next (iter);
4607 g_slist_free (child_nodes);
4609 g_assert (node != NULL);
4612 g_assert (node != NULL);
4613 g_assert (node->level == 0);
4615 /* this assertion is correct, but slow. */
4616 /* g_assert (node_compare (node, line->parent) < 0); */
4618 /* Return last line in this node. */
4620 prev = node->children.line;
4628 * Non-public function implementations
4632 summary_list_destroy (Summary *summary)
4635 while (summary != NULL)
4637 next = summary->next;
4638 summary_destroy (summary);
4644 get_last_line (GtkTextBTree *tree)
4646 if (tree->last_line_stamp != tree->chars_changed_stamp)
4652 n_lines = _gtk_text_btree_line_count (tree);
4654 g_assert (n_lines >= 1); /* num_lines doesn't return bogus last line. */
4656 line = _gtk_text_btree_get_line (tree, n_lines, &real_line);
4658 tree->last_line_stamp = tree->chars_changed_stamp;
4659 tree->last_line = line;
4662 return tree->last_line;
4670 gtk_text_line_new (void)
4674 line = g_new0(GtkTextLine, 1);
4675 line->dir_strong = PANGO_DIRECTION_NEUTRAL;
4676 line->dir_propagated_forward = PANGO_DIRECTION_NEUTRAL;
4677 line->dir_propagated_back = PANGO_DIRECTION_NEUTRAL;
4683 gtk_text_line_destroy (GtkTextBTree *tree, GtkTextLine *line)
4685 GtkTextLineData *ld;
4686 GtkTextLineData *next;
4688 g_return_if_fail (line != NULL);
4695 view = gtk_text_btree_get_view (tree, ld->view_id);
4697 g_assert (view != NULL);
4700 gtk_text_layout_free_line_data (view->layout, line, ld);
4709 gtk_text_line_set_parent (GtkTextLine *line,
4710 GtkTextBTreeNode *node)
4712 if (line->parent == node)
4714 line->parent = node;
4715 gtk_text_btree_node_invalidate_upward (node, NULL);
4719 cleanup_line (GtkTextLine *line)
4721 GtkTextLineSegment *seg, **prev_p;
4725 * Make a pass over all of the segments in the line, giving each
4726 * a chance to clean itself up. This could potentially change
4727 * the structure of the line, e.g. by merging two segments
4728 * together or having two segments cancel themselves; if so,
4729 * then repeat the whole process again, since the first structure
4730 * change might make other structure changes possible. Repeat
4731 * until eventually there are no changes.
4738 prev_p = &line->segments;
4739 for (seg = *prev_p; seg != NULL; seg = *prev_p)
4741 if (seg->type->cleanupFunc != NULL)
4743 *prev_p = (*seg->type->cleanupFunc)(seg, line);
4751 prev_p = &(*prev_p)->next;
4761 node_data_new (gpointer view_id)
4765 nd = g_new (NodeData, 1);
4767 nd->view_id = view_id;
4777 node_data_destroy (NodeData *nd)
4783 node_data_list_destroy (NodeData *nd)
4789 while (iter != NULL)
4792 node_data_destroy (iter);
4798 node_data_find (NodeData *nd, gpointer view_id)
4802 if (nd->view_id == view_id)
4810 summary_destroy (Summary *summary)
4812 /* Fill with error-triggering garbage */
4813 summary->info = (void*)0x1;
4814 summary->toggle_count = 567;
4815 summary->next = (void*)0x1;
4819 static GtkTextBTreeNode*
4820 gtk_text_btree_node_new (void)
4822 GtkTextBTreeNode *node;
4824 node = g_new (GtkTextBTreeNode, 1);
4826 node->node_data = NULL;
4832 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
4833 GtkTextTagInfo *info,
4838 summary = node->summary;
4839 while (summary != NULL)
4841 if (summary->info == info)
4843 summary->toggle_count += adjust;
4847 summary = summary->next;
4850 if (summary == NULL)
4852 /* didn't find a summary for our tag. */
4853 g_return_if_fail (adjust > 0);
4854 summary = g_new (Summary, 1);
4855 summary->info = info;
4856 summary->toggle_count = adjust;
4857 summary->next = node->summary;
4858 node->summary = summary;
4862 /* Note that the tag root and above do not have summaries
4863 for the tag; only nodes below the tag root have
4866 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4870 summary = node->summary;
4871 while (summary != NULL)
4874 summary->info->tag == tag)
4877 summary = summary->next;
4883 /* Add node and all children to the damage region. */
4885 gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node)
4889 nd = node->node_data;
4896 if (node->level == 0)
4900 line = node->children.line;
4901 while (line != NULL)
4903 GtkTextLineData *ld;
4917 GtkTextBTreeNode *child;
4919 child = node->children.node;
4921 while (child != NULL)
4923 gtk_text_btree_node_invalidate_downward (child);
4925 child = child->next;
4931 gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node, gpointer view_id)
4933 GtkTextBTreeNode *iter;
4936 while (iter != NULL)
4942 nd = node_data_find (iter->node_data, view_id);
4944 if (nd == NULL || !nd->valid)
4945 break; /* Once a node is invalid, we know its parents are as well. */
4951 gboolean should_continue = FALSE;
4953 nd = iter->node_data;
4958 should_continue = TRUE;
4965 if (!should_continue)
4966 break; /* This node was totally invalidated, so are its
4970 iter = iter->parent;
4976 * _gtk_text_btree_is_valid:
4977 * @tree: a #GtkTextBTree
4978 * @view_id: ID for the view
4980 * Check to see if the entire #GtkTextBTree is valid or not for
4983 * Return value: %TRUE if the entire #GtkTextBTree is valid
4986 _gtk_text_btree_is_valid (GtkTextBTree *tree,
4990 g_return_val_if_fail (tree != NULL, FALSE);
4992 nd = node_data_find (tree->root_node->node_data, view_id);
4993 return (nd && nd->valid);
4996 typedef struct _ValidateState ValidateState;
4998 struct _ValidateState
5000 gint remaining_pixels;
5001 gboolean in_validation;
5008 gtk_text_btree_node_validate (BTreeView *view,
5009 GtkTextBTreeNode *node,
5011 ValidateState *state)
5013 gint node_valid = TRUE;
5014 gint node_width = 0;
5015 gint node_height = 0;
5017 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5018 g_return_if_fail (!nd->valid);
5020 if (node->level == 0)
5022 GtkTextLine *line = node->children.line;
5023 GtkTextLineData *ld;
5025 /* Iterate over leading valid lines */
5026 while (line != NULL)
5028 ld = _gtk_text_line_get_data (line, view_id);
5030 if (!ld || !ld->valid)
5032 else if (state->in_validation)
5034 state->in_validation = FALSE;
5039 state->y += ld->height;
5040 node_width = MAX (ld->width, node_width);
5041 node_height += ld->height;
5047 state->in_validation = TRUE;
5049 /* Iterate over invalid lines */
5050 while (line != NULL)
5052 ld = _gtk_text_line_get_data (line, view_id);
5054 if (ld && ld->valid)
5059 state->old_height += ld->height;
5060 ld = gtk_text_layout_wrap (view->layout, line, ld);
5061 state->new_height += ld->height;
5063 node_width = MAX (ld->width, node_width);
5064 node_height += ld->height;
5066 state->remaining_pixels -= ld->height;
5067 if (state->remaining_pixels <= 0)
5077 /* Iterate over the remaining lines */
5078 while (line != NULL)
5080 ld = _gtk_text_line_get_data (line, view_id);
5081 state->in_validation = FALSE;
5083 if (!ld || !ld->valid)
5088 node_width = MAX (ld->width, node_width);
5089 node_height += ld->height;
5097 GtkTextBTreeNode *child;
5100 child = node->children.node;
5102 /* Iterate over leading valid nodes */
5105 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5107 if (!child_nd->valid)
5109 else if (state->in_validation)
5111 state->in_validation = FALSE;
5116 state->y += child_nd->height;
5117 node_width = MAX (node_width, child_nd->width);
5118 node_height += child_nd->height;
5121 child = child->next;
5124 /* Iterate over invalid nodes */
5127 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5129 if (child_nd->valid)
5133 gtk_text_btree_node_validate (view, child, view_id, state);
5135 if (!child_nd->valid)
5137 node_width = MAX (node_width, child_nd->width);
5138 node_height += child_nd->height;
5140 if (!state->in_validation || state->remaining_pixels <= 0)
5142 child = child->next;
5147 child = child->next;
5150 /* Iterate over the remaining lines */
5153 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5154 state->in_validation = FALSE;
5156 if (!child_nd->valid)
5159 node_width = MAX (child_nd->width, node_width);
5160 node_height += child_nd->height;
5162 child = child->next;
5166 nd->width = node_width;
5167 nd->height = node_height;
5168 nd->valid = node_valid;
5172 * _gtk_text_btree_validate:
5173 * @tree: a #GtkTextBTree
5175 * @max_pixels: the maximum number of pixels to validate. (No more
5176 * than one paragraph beyond this limit will be validated)
5177 * @y: location to store starting y coordinate of validated region
5178 * @old_height: location to store old height of validated region
5179 * @new_height: location to store new height of validated region
5181 * Validate a single contiguous invalid region of a #GtkTextBTree for
5184 * Return value: %TRUE if a region has been validated, %FALSE if the
5185 * entire tree was already valid.
5188 _gtk_text_btree_validate (GtkTextBTree *tree,
5197 g_return_val_if_fail (tree != NULL, FALSE);
5199 view = gtk_text_btree_get_view (tree, view_id);
5200 g_return_val_if_fail (view != NULL, FALSE);
5202 if (!_gtk_text_btree_is_valid (tree, view_id))
5204 ValidateState state;
5206 state.remaining_pixels = max_pixels;
5207 state.in_validation = FALSE;
5209 state.old_height = 0;
5210 state.new_height = 0;
5212 gtk_text_btree_node_validate (view,
5219 *old_height = state.old_height;
5221 *new_height = state.new_height;
5223 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5224 _gtk_text_btree_check (tree);
5233 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
5237 gboolean *valid_out)
5241 gboolean valid = TRUE;
5243 if (node->level == 0)
5245 GtkTextLine *line = node->children.line;
5247 while (line != NULL)
5249 GtkTextLineData *ld = _gtk_text_line_get_data (line, view_id);
5251 if (!ld || !ld->valid)
5256 width = MAX (ld->width, width);
5257 height += ld->height;
5265 GtkTextBTreeNode *child = node->children.node;
5269 NodeData *child_nd = node_data_find (child->node_data, view_id);
5271 if (!child_nd || !child_nd->valid)
5276 width = MAX (child_nd->width, width);
5277 height += child_nd->height;
5280 child = child->next;
5285 *height_out = height;
5290 /* Recompute the validity and size of the view data for a given
5291 * view at this node from the immediate children of the node
5294 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
5297 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5302 gtk_text_btree_node_compute_view_aggregates (node, view_id,
5303 &width, &height, &valid);
5305 nd->height = height;
5312 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
5317 gtk_text_btree_node_check_valid (node, view_id);
5318 node = node->parent;
5323 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
5326 if (node->level == 0)
5328 return gtk_text_btree_node_check_valid (node, view_id);
5332 GtkTextBTreeNode *child = node->children.node;
5334 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5342 NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
5344 if (!child_nd->valid)
5346 nd->width = MAX (child_nd->width, nd->width);
5347 nd->height += child_nd->height;
5349 child = child->next;
5358 * _gtk_text_btree_validate_line:
5359 * @tree: a #GtkTextBTree
5360 * @line: line to validate
5361 * @view_id: view ID for the view to validate
5363 * Revalidate a single line of the btree for the given view, propagate
5364 * results up through the entire tree.
5367 _gtk_text_btree_validate_line (GtkTextBTree *tree,
5371 GtkTextLineData *ld;
5374 g_return_if_fail (tree != NULL);
5375 g_return_if_fail (line != NULL);
5377 view = gtk_text_btree_get_view (tree, view_id);
5378 g_return_if_fail (view != NULL);
5380 ld = _gtk_text_line_get_data (line, view_id);
5381 if (!ld || !ld->valid)
5383 ld = gtk_text_layout_wrap (view->layout, line, ld);
5385 gtk_text_btree_node_check_valid_upward (line->parent, view_id);
5390 gtk_text_btree_node_remove_view (BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
5392 if (node->level == 0)
5396 line = node->children.line;
5397 while (line != NULL)
5399 GtkTextLineData *ld;
5401 ld = _gtk_text_line_remove_data (line, view_id);
5404 gtk_text_layout_free_line_data (view->layout, line, ld);
5411 GtkTextBTreeNode *child;
5413 child = node->children.node;
5415 while (child != NULL)
5418 gtk_text_btree_node_remove_view (view, child, view_id);
5420 child = child->next;
5424 gtk_text_btree_node_remove_data (node, view_id);
5428 gtk_text_btree_node_destroy (GtkTextBTree *tree, GtkTextBTreeNode *node)
5430 if (node->level == 0)
5433 GtkTextLineSegment *seg;
5435 while (node->children.line != NULL)
5437 line = node->children.line;
5438 node->children.line = line->next;
5439 while (line->segments != NULL)
5441 seg = line->segments;
5442 line->segments = seg->next;
5444 (*seg->type->deleteFunc) (seg, line, TRUE);
5446 gtk_text_line_destroy (tree, line);
5451 GtkTextBTreeNode *childPtr;
5453 while (node->children.node != NULL)
5455 childPtr = node->children.node;
5456 node->children.node = childPtr->next;
5457 gtk_text_btree_node_destroy (tree, childPtr);
5461 gtk_text_btree_node_free_empty (tree, node);
5465 gtk_text_btree_node_free_empty (GtkTextBTree *tree,
5466 GtkTextBTreeNode *node)
5468 g_return_if_fail ((node->level > 0 && node->children.node == NULL) ||
5469 (node->level == 0 && node->children.line == NULL));
5471 summary_list_destroy (node->summary);
5472 node_data_list_destroy (node->node_data);
5477 gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node, gpointer view_id)
5481 nd = node->node_data;
5484 if (nd->view_id == view_id)
5492 nd = node_data_new (view_id);
5494 if (node->node_data)
5495 nd->next = node->node_data;
5497 node->node_data = nd;
5504 gtk_text_btree_node_remove_data (GtkTextBTreeNode *node, gpointer view_id)
5510 nd = node->node_data;
5513 if (nd->view_id == view_id)
5524 prev->next = nd->next;
5526 if (node->node_data == nd)
5527 node->node_data = nd->next;
5531 node_data_destroy (nd);
5535 gtk_text_btree_node_get_size (GtkTextBTreeNode *node, gpointer view_id,
5536 gint *width, gint *height)
5540 g_return_if_fail (width != NULL);
5541 g_return_if_fail (height != NULL);
5543 nd = gtk_text_btree_node_ensure_data (node, view_id);
5548 *height = nd->height;
5551 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5552 * here isn't quite right, since for a lot of operations we want to
5553 * know which children of the common parent correspond to the two nodes
5554 * (e.g., when computing the order of two iters)
5556 static GtkTextBTreeNode *
5557 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5558 GtkTextBTreeNode *node2)
5560 while (node1->level < node2->level)
5561 node1 = node1->parent;
5562 while (node2->level < node1->level)
5563 node2 = node2->parent;
5564 while (node1 != node2)
5566 node1 = node1->parent;
5567 node2 = node2->parent;
5578 gtk_text_btree_get_view (GtkTextBTree *tree, gpointer view_id)
5583 while (view != NULL)
5585 if (view->view_id == view_id)
5594 get_tree_bounds (GtkTextBTree *tree,
5598 _gtk_text_btree_get_iter_at_line_char (tree, start, 0, 0);
5599 _gtk_text_btree_get_end_iter (tree, end);
5603 tag_changed_cb (GtkTextTagTable *table,
5605 gboolean size_changed,
5610 /* We need to queue a relayout on all regions that are tagged with
5617 if (_gtk_text_btree_get_iter_at_first_toggle (tree, &start, tag))
5619 /* Must be a last toggle if there was a first one. */
5620 _gtk_text_btree_get_iter_at_last_toggle (tree, &end, tag);
5621 DV (g_print ("invalidating due to tag change (%s)\n", G_STRLOC));
5622 _gtk_text_btree_invalidate_region (tree,
5629 /* We only need to queue a redraw, not a relayout */
5634 while (view != NULL)
5638 _gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5639 gtk_text_layout_changed (view->layout, 0, height, height);
5647 _gtk_text_btree_notify_will_remove_tag (GtkTextBTree *tree,
5650 /* Remove the tag from the tree */
5655 get_tree_bounds (tree, &start, &end);
5657 _gtk_text_btree_tag (&start, &end, tag, FALSE);
5658 gtk_text_btree_remove_tag_info (tree, tag);
5662 /* Rebalance the out-of-whack node "node" */
5664 gtk_text_btree_rebalance (GtkTextBTree *tree,
5665 GtkTextBTreeNode *node)
5668 * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5669 * up through the tree one GtkTextBTreeNode at a time until the root
5670 * GtkTextBTreeNode has been processed.
5673 while (node != NULL)
5675 GtkTextBTreeNode *new_node, *child;
5680 * Check to see if the GtkTextBTreeNode has too many children. If it does,
5681 * then split off all but the first MIN_CHILDREN into a separate
5682 * GtkTextBTreeNode following the original one. Then repeat until the
5683 * GtkTextBTreeNode has a decent size.
5686 if (node->num_children > MAX_CHILDREN)
5691 * If the GtkTextBTreeNode being split is the root
5692 * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5696 if (node->parent == NULL)
5698 new_node = gtk_text_btree_node_new ();
5699 new_node->parent = NULL;
5700 new_node->next = NULL;
5701 new_node->summary = NULL;
5702 new_node->level = node->level + 1;
5703 new_node->children.node = node;
5704 recompute_node_counts (tree, new_node);
5705 tree->root_node = new_node;
5707 new_node = gtk_text_btree_node_new ();
5708 new_node->parent = node->parent;
5709 new_node->next = node->next;
5710 node->next = new_node;
5711 new_node->summary = NULL;
5712 new_node->level = node->level;
5713 new_node->num_children = node->num_children - MIN_CHILDREN;
5714 if (node->level == 0)
5716 for (i = MIN_CHILDREN-1,
5717 line = node->children.line;
5718 i > 0; i--, line = line->next)
5720 /* Empty loop body. */
5722 new_node->children.line = line->next;
5727 for (i = MIN_CHILDREN-1,
5728 child = node->children.node;
5729 i > 0; i--, child = child->next)
5731 /* Empty loop body. */
5733 new_node->children.node = child->next;
5736 recompute_node_counts (tree, node);
5737 node->parent->num_children++;
5739 if (node->num_children <= MAX_CHILDREN)
5741 recompute_node_counts (tree, node);
5747 while (node->num_children < MIN_CHILDREN)
5749 GtkTextBTreeNode *other;
5750 GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5751 GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5752 int total_children, first_children, i;
5755 * Too few children for this GtkTextBTreeNode. If this is the root then,
5756 * it's OK for it to have less than MIN_CHILDREN children
5757 * as long as it's got at least two. If it has only one
5758 * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5759 * the tree and use its child as the new root.
5762 if (node->parent == NULL)
5764 if ((node->num_children == 1) && (node->level > 0))
5766 tree->root_node = node->children.node;
5767 tree->root_node->parent = NULL;
5769 node->children.node = NULL;
5770 gtk_text_btree_node_free_empty (tree, node);
5776 * Not the root. Make sure that there are siblings to
5780 if (node->parent->num_children < 2)
5782 gtk_text_btree_rebalance (tree, node->parent);
5787 * Find a sibling neighbor to borrow from, and arrange for
5788 * node to be the earlier of the pair.
5791 if (node->next == NULL)
5793 for (other = node->parent->children.node;
5794 other->next != node;
5795 other = other->next)
5797 /* Empty loop body. */
5804 * We're going to either merge the two siblings together
5805 * into one GtkTextBTreeNode or redivide the children among them to
5806 * balance their loads. As preparation, join their two
5807 * child lists into a single list and remember the half-way
5808 * point in the list.
5811 total_children = node->num_children + other->num_children;
5812 first_children = total_children/2;
5813 if (node->children.node == NULL)
5815 node->children = other->children;
5816 other->children.node = NULL;
5817 other->children.line = NULL;
5819 if (node->level == 0)
5823 for (line = node->children.line, i = 1;
5825 line = line->next, i++)
5827 if (i == first_children)
5832 line->next = other->children.line;
5833 while (i <= first_children)
5842 GtkTextBTreeNode *child;
5844 for (child = node->children.node, i = 1;
5845 child->next != NULL;
5846 child = child->next, i++)
5848 if (i <= first_children)
5850 if (i == first_children)
5852 halfwaynode = child;
5856 child->next = other->children.node;
5857 while (i <= first_children)
5859 halfwaynode = child;
5860 child = child->next;
5866 * If the two siblings can simply be merged together, do it.
5869 if (total_children <= MAX_CHILDREN)
5871 recompute_node_counts (tree, node);
5872 node->next = other->next;
5873 node->parent->num_children--;
5875 other->children.node = NULL;
5876 other->children.line = NULL;
5877 gtk_text_btree_node_free_empty (tree, other);
5882 * The siblings can't be merged, so just divide their
5883 * children evenly between them.
5886 if (node->level == 0)
5888 other->children.line = halfwayline->next;
5889 halfwayline->next = NULL;
5893 other->children.node = halfwaynode->next;
5894 halfwaynode->next = NULL;
5897 recompute_node_counts (tree, node);
5898 recompute_node_counts (tree, other);
5901 node = node->parent;
5906 post_insert_fixup (GtkTextBTree *tree,
5908 gint line_count_delta,
5909 gint char_count_delta)
5912 GtkTextBTreeNode *node;
5915 * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5916 * point, then rebalance the tree if necessary.
5919 for (node = line->parent ; node != NULL;
5920 node = node->parent)
5922 node->num_lines += line_count_delta;
5923 node->num_chars += char_count_delta;
5925 node = line->parent;
5926 node->num_children += line_count_delta;
5928 if (node->num_children > MAX_CHILDREN)
5930 gtk_text_btree_rebalance (tree, node);
5933 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5934 _gtk_text_btree_check (tree);
5937 static GtkTextTagInfo*
5938 gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
5941 GtkTextTagInfo *info;
5945 list = tree->tag_infos;
5946 while (list != NULL)
5949 if (info->tag == tag)
5952 list = g_slist_next (list);
5958 static GtkTextTagInfo*
5959 gtk_text_btree_get_tag_info (GtkTextBTree *tree,
5962 GtkTextTagInfo *info;
5964 info = gtk_text_btree_get_existing_tag_info (tree, tag);
5968 /* didn't find it, create. */
5970 info = g_new (GtkTextTagInfo, 1);
5974 info->tag_root = NULL;
5975 info->toggle_count = 0;
5977 tree->tag_infos = g_slist_prepend (tree->tag_infos, info);
5980 g_print ("Created tag info %p for tag %s(%p)\n",
5981 info, info->tag->name ? info->tag->name : "anon",
5990 gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
5993 GtkTextTagInfo *info;
5998 list = tree->tag_infos;
5999 while (list != NULL)
6002 if (info->tag == tag)
6005 g_print ("Removing tag info %p for tag %s(%p)\n",
6006 info, info->tag->name ? info->tag->name : "anon",
6012 prev->next = list->next;
6016 tree->tag_infos = list->next;
6019 g_slist_free (list);
6021 g_object_unref (info->tag);
6028 list = g_slist_next (list);
6033 recompute_level_zero_counts (GtkTextBTreeNode *node)
6036 GtkTextLineSegment *seg;
6038 g_assert (node->level == 0);
6040 line = node->children.line;
6041 while (line != NULL)
6043 node->num_children++;
6046 if (line->parent != node)
6047 gtk_text_line_set_parent (line, node);
6049 seg = line->segments;
6053 node->num_chars += seg->char_count;
6055 if (((seg->type != >k_text_toggle_on_type)
6056 && (seg->type != >k_text_toggle_off_type))
6057 || !(seg->body.toggle.inNodeCounts))
6063 GtkTextTagInfo *info;
6065 info = seg->body.toggle.info;
6067 gtk_text_btree_node_adjust_toggle_count (node, info, 1);
6078 recompute_level_nonzero_counts (GtkTextBTreeNode *node)
6081 GtkTextBTreeNode *child;
6083 g_assert (node->level > 0);
6085 child = node->children.node;
6086 while (child != NULL)
6088 node->num_children += 1;
6089 node->num_lines += child->num_lines;
6090 node->num_chars += child->num_chars;
6092 if (child->parent != node)
6094 child->parent = node;
6095 gtk_text_btree_node_invalidate_upward (node, NULL);
6098 summary = child->summary;
6099 while (summary != NULL)
6101 gtk_text_btree_node_adjust_toggle_count (node,
6103 summary->toggle_count);
6105 summary = summary->next;
6108 child = child->next;
6113 *----------------------------------------------------------------------
6115 * recompute_node_counts --
6117 * This procedure is called to recompute all the counts in a GtkTextBTreeNode
6118 * (tags, child information, etc.) by scanning the information in
6119 * its descendants. This procedure is called during rebalancing
6120 * when a GtkTextBTreeNode's child structure has changed.
6126 * The tag counts for node are modified to reflect its current
6127 * child structure, as are its num_children, num_lines, num_chars fields.
6128 * Also, all of the childrens' parent fields are made to point
6131 *----------------------------------------------------------------------
6135 recompute_node_counts (GtkTextBTree *tree, GtkTextBTreeNode *node)
6138 Summary *summary, *summary2;
6141 * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
6142 * the existing Summary records (most of them will probably be reused).
6145 summary = node->summary;
6146 while (summary != NULL)
6148 summary->toggle_count = 0;
6149 summary = summary->next;
6152 node->num_children = 0;
6153 node->num_lines = 0;
6154 node->num_chars = 0;
6157 * Scan through the children, adding the childrens' tag counts into
6158 * the GtkTextBTreeNode's tag counts and adding new Summary structures if
6162 if (node->level == 0)
6163 recompute_level_zero_counts (node);
6165 recompute_level_nonzero_counts (node);
6170 gtk_text_btree_node_check_valid (node, view->view_id);
6175 * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
6176 * records that still have a zero count, or that have all the toggles.
6177 * The GtkTextBTreeNode with the children that account for all the tags toggles
6178 * have no summary information, and they become the tag_root for the tag.
6182 for (summary = node->summary; summary != NULL; )
6184 if (summary->toggle_count > 0 &&
6185 summary->toggle_count < summary->info->toggle_count)
6187 if (node->level == summary->info->tag_root->level)
6190 * The tag's root GtkTextBTreeNode split and some toggles left.
6191 * The tag root must move up a level.
6193 summary->info->tag_root = node->parent;
6196 summary = summary->next;
6199 if (summary->toggle_count == summary->info->toggle_count)
6202 * A GtkTextBTreeNode merge has collected all the toggles under
6203 * one GtkTextBTreeNode. Push the root down to this level.
6205 summary->info->tag_root = node;
6207 if (summary2 != NULL)
6209 summary2->next = summary->next;
6210 summary_destroy (summary);
6211 summary = summary2->next;
6215 node->summary = summary->next;
6216 summary_destroy (summary);
6217 summary = node->summary;
6223 _gtk_change_node_toggle_count (GtkTextBTreeNode *node,
6224 GtkTextTagInfo *info,
6225 gint delta) /* may be negative */
6227 Summary *summary, *prevPtr;
6228 GtkTextBTreeNode *node2Ptr;
6229 int rootLevel; /* Level of original tag root */
6231 info->toggle_count += delta;
6233 if (info->tag_root == (GtkTextBTreeNode *) NULL)
6235 info->tag_root = node;
6240 * Note the level of the existing root for the tag so we can detect
6241 * if it needs to be moved because of the toggle count change.
6244 rootLevel = info->tag_root->level;
6247 * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
6248 * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
6252 for ( ; node != info->tag_root; node = node->parent)
6255 * See if there's already an entry for this tag for this GtkTextBTreeNode. If so,
6256 * perhaps all we have to do is adjust its count.
6259 for (prevPtr = NULL, summary = node->summary;
6261 prevPtr = summary, summary = summary->next)
6263 if (summary->info == info)
6268 if (summary != NULL)
6270 summary->toggle_count += delta;
6271 if (summary->toggle_count > 0 &&
6272 summary->toggle_count < info->toggle_count)
6276 if (summary->toggle_count != 0)
6279 * Should never find a GtkTextBTreeNode with max toggle count at this
6280 * point (there shouldn't have been a summary entry in the
6284 g_error ("%s: bad toggle count (%d) max (%d)",
6285 G_STRLOC, summary->toggle_count, info->toggle_count);
6289 * Zero toggle count; must remove this tag from the list.
6292 if (prevPtr == NULL)
6294 node->summary = summary->next;
6298 prevPtr->next = summary->next;
6300 summary_destroy (summary);
6305 * This tag isn't currently in the summary information list.
6308 if (rootLevel == node->level)
6312 * The old tag root is at the same level in the tree as this
6313 * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode. Move the tag root up
6314 * a level, in the hopes that it will now cover this GtkTextBTreeNode
6315 * as well as the old root (if not, we'll move it up again
6316 * the next time through the loop). To push it up one level
6317 * we copy the original toggle count into the summary
6318 * information at the old root and change the root to its
6319 * parent GtkTextBTreeNode.
6322 GtkTextBTreeNode *rootnode = info->tag_root;
6323 summary = (Summary *) g_malloc (sizeof (Summary));
6324 summary->info = info;
6325 summary->toggle_count = info->toggle_count - delta;
6326 summary->next = rootnode->summary;
6327 rootnode->summary = summary;
6328 rootnode = rootnode->parent;
6329 rootLevel = rootnode->level;
6330 info->tag_root = rootnode;
6332 summary = (Summary *) g_malloc (sizeof (Summary));
6333 summary->info = info;
6334 summary->toggle_count = delta;
6335 summary->next = node->summary;
6336 node->summary = summary;
6341 * If we've decremented the toggle count, then it may be necessary
6342 * to push the tag root down one or more levels.
6349 if (info->toggle_count == 0)
6351 info->tag_root = (GtkTextBTreeNode *) NULL;
6354 node = info->tag_root;
6355 while (node->level > 0)
6358 * See if a single child GtkTextBTreeNode accounts for all of the tag's
6359 * toggles. If so, push the root down one level.
6362 for (node2Ptr = node->children.node;
6363 node2Ptr != (GtkTextBTreeNode *)NULL ;
6364 node2Ptr = node2Ptr->next)
6366 for (prevPtr = NULL, summary = node2Ptr->summary;
6368 prevPtr = summary, summary = summary->next)
6370 if (summary->info == info)
6375 if (summary == NULL)
6379 if (summary->toggle_count != info->toggle_count)
6382 * No GtkTextBTreeNode has all toggles, so the root is still valid.
6389 * This GtkTextBTreeNode has all the toggles, so push down the root.
6392 if (prevPtr == NULL)
6394 node2Ptr->summary = summary->next;
6398 prevPtr->next = summary->next;
6400 summary_destroy (summary);
6401 info->tag_root = node2Ptr;
6404 node = info->tag_root;
6409 *----------------------------------------------------------------------
6413 * This is a utility procedure used by _gtk_text_btree_get_tags. It
6414 * increments the count for a particular tag, adding a new
6415 * entry for that tag if there wasn't one previously.
6421 * The information at *tagInfoPtr may be modified, and the arrays
6422 * may be reallocated to make them larger.
6424 *----------------------------------------------------------------------
6428 inc_count (GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
6433 for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
6434 count > 0; tag_p++, count--)
6438 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
6444 * There isn't currently an entry for this tag, so we have to
6445 * make a new one. If the arrays are full, then enlarge the
6449 if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
6451 GtkTextTag **newTags;
6452 int *newCounts, newSize;
6454 newSize = 2*tagInfoPtr->arraySize;
6455 newTags = (GtkTextTag **) g_malloc ((unsigned)
6456 (newSize*sizeof (GtkTextTag *)));
6457 memcpy ((void *) newTags, (void *) tagInfoPtr->tags,
6458 tagInfoPtr->arraySize *sizeof (GtkTextTag *));
6459 g_free ((char *) tagInfoPtr->tags);
6460 tagInfoPtr->tags = newTags;
6461 newCounts = (int *) g_malloc ((unsigned) (newSize*sizeof (int)));
6462 memcpy ((void *) newCounts, (void *) tagInfoPtr->counts,
6463 tagInfoPtr->arraySize *sizeof (int));
6464 g_free ((char *) tagInfoPtr->counts);
6465 tagInfoPtr->counts = newCounts;
6466 tagInfoPtr->arraySize = newSize;
6469 tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
6470 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
6471 tagInfoPtr->numTags++;
6475 gtk_text_btree_link_segment (GtkTextLineSegment *seg,
6476 const GtkTextIter *iter)
6478 GtkTextLineSegment *prev;
6482 line = _gtk_text_iter_get_text_line (iter);
6483 tree = _gtk_text_iter_get_btree (iter);
6485 prev = gtk_text_line_segment_split (iter);
6488 seg->next = line->segments;
6489 line->segments = seg;
6493 seg->next = prev->next;
6496 cleanup_line (line);
6497 segments_changed (tree);
6499 if (gtk_debug_flags & GTK_DEBUG_TEXT)
6500 _gtk_text_btree_check (tree);
6504 gtk_text_btree_unlink_segment (GtkTextBTree *tree,
6505 GtkTextLineSegment *seg,
6508 GtkTextLineSegment *prev;
6510 if (line->segments == seg)
6512 line->segments = seg->next;
6516 for (prev = line->segments; prev->next != seg;
6519 /* Empty loop body. */
6521 prev->next = seg->next;
6523 cleanup_line (line);
6524 segments_changed (tree);
6528 * This is here because it requires BTree internals, it logically
6529 * belongs in gtktextsegment.c
6534 *--------------------------------------------------------------
6536 * _gtk_toggle_segment_check_func --
6538 * This procedure is invoked to perform consistency checks
6539 * on toggle segments.
6545 * If a consistency problem is found the procedure g_errors.
6547 *--------------------------------------------------------------
6551 _gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6557 if (segPtr->byte_count != 0)
6559 g_error ("toggle_segment_check_func: segment had non-zero size");
6561 if (!segPtr->body.toggle.inNodeCounts)
6563 g_error ("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6565 needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6566 for (summary = line->parent->summary; ;
6567 summary = summary->next)
6569 if (summary == NULL)
6573 g_error ("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6580 if (summary->info == segPtr->body.toggle.info)
6584 g_error ("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6596 gtk_text_btree_node_view_check_consistency (GtkTextBTree *tree,
6597 GtkTextBTreeNode *node,
6607 while (view != NULL)
6609 if (view->view_id == nd->view_id)
6616 g_error ("Node has data for a view %p no longer attached to the tree",
6619 gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6620 &width, &height, &valid);
6622 /* valid aggregate not checked the same as width/height, because on
6623 * btree rebalance we can have invalid nodes where all lines below
6624 * them are actually valid, due to moving lines around between
6627 * The guarantee is that if there are invalid lines the node is
6628 * invalid - we don't guarantee that if the node is invalid there
6629 * are invalid lines.
6632 if (nd->width != width ||
6633 nd->height != height ||
6634 (nd->valid && !valid))
6636 g_error ("Node aggregates for view %p are invalid:\n"
6637 "Are (%d,%d,%s), should be (%d,%d,%s)",
6639 nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6640 width, height, valid ? "TRUE" : "FALSE");
6645 gtk_text_btree_node_check_consistency (GtkTextBTree *tree,
6646 GtkTextBTreeNode *node)
6648 GtkTextBTreeNode *childnode;
6649 Summary *summary, *summary2;
6651 GtkTextLineSegment *segPtr;
6652 int num_children, num_lines, num_chars, toggle_count, min_children;
6653 GtkTextLineData *ld;
6656 if (node->parent != NULL)
6658 min_children = MIN_CHILDREN;
6660 else if (node->level > 0)
6667 if ((node->num_children < min_children)
6668 || (node->num_children > MAX_CHILDREN))
6670 g_error ("gtk_text_btree_node_check_consistency: bad child count (%d)",
6671 node->num_children);
6674 nd = node->node_data;
6677 gtk_text_btree_node_view_check_consistency (tree, node, nd);
6684 if (node->level == 0)
6686 for (line = node->children.line; line != NULL;
6689 if (line->parent != node)
6691 g_error ("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6693 if (line->segments == NULL)
6695 g_error ("gtk_text_btree_node_check_consistency: line has no segments");
6701 /* Just ensuring we don't segv while doing this loop */
6706 for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6708 if (segPtr->type->checkFunc != NULL)
6710 (*segPtr->type->checkFunc)(segPtr, line);
6712 if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6713 && (segPtr->next != NULL)
6714 && (segPtr->next->byte_count == 0)
6715 && (segPtr->next->type->leftGravity))
6717 g_error ("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6719 if ((segPtr->next == NULL)
6720 && (segPtr->type != >k_text_char_type))
6722 g_error ("gtk_text_btree_node_check_consistency: line ended with wrong type");
6725 num_chars += segPtr->char_count;
6734 for (childnode = node->children.node; childnode != NULL;
6735 childnode = childnode->next)
6737 if (childnode->parent != node)
6739 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6741 if (childnode->level != (node->level-1))
6743 g_error ("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6744 node->level, childnode->level);
6746 gtk_text_btree_node_check_consistency (tree, childnode);
6747 for (summary = childnode->summary; summary != NULL;
6748 summary = summary->next)
6750 for (summary2 = node->summary; ;
6751 summary2 = summary2->next)
6753 if (summary2 == NULL)
6755 if (summary->info->tag_root == node)
6759 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6760 summary->info->tag->name,
6761 "present in parent summaries");
6763 if (summary->info == summary2->info)
6770 num_lines += childnode->num_lines;
6771 num_chars += childnode->num_chars;
6774 if (num_children != node->num_children)
6776 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6777 num_children, node->num_children);
6779 if (num_lines != node->num_lines)
6781 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6782 num_lines, node->num_lines);
6784 if (num_chars != node->num_chars)
6786 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6787 num_chars, node->num_chars);
6790 for (summary = node->summary; summary != NULL;
6791 summary = summary->next)
6793 if (summary->info->toggle_count == summary->toggle_count)
6795 g_error ("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6796 summary->info->tag->name);
6799 if (node->level == 0)
6801 for (line = node->children.line; line != NULL;
6804 for (segPtr = line->segments; segPtr != NULL;
6805 segPtr = segPtr->next)
6807 if ((segPtr->type != >k_text_toggle_on_type)
6808 && (segPtr->type != >k_text_toggle_off_type))
6812 if (segPtr->body.toggle.info == summary->info)
6814 if (!segPtr->body.toggle.inNodeCounts)
6815 g_error ("Toggle segment not in the node counts");
6824 for (childnode = node->children.node;
6826 childnode = childnode->next)
6828 for (summary2 = childnode->summary;
6830 summary2 = summary2->next)
6832 if (summary2->info == summary->info)
6834 toggle_count += summary2->toggle_count;
6839 if (toggle_count != summary->toggle_count)
6841 g_error ("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6842 toggle_count, summary->toggle_count);
6844 for (summary2 = summary->next; summary2 != NULL;
6845 summary2 = summary2->next)
6847 if (summary2->info == summary->info)
6849 g_error ("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6850 summary->info->tag->name);
6857 listify_foreach (GtkTextTag *tag, gpointer user_data)
6859 GSList** listp = user_data;
6861 *listp = g_slist_prepend (*listp, tag);
6865 list_of_tags (GtkTextTagTable *table)
6867 GSList *list = NULL;
6869 gtk_text_tag_table_foreach (table, listify_foreach, &list);
6875 _gtk_text_btree_check (GtkTextBTree *tree)
6878 GtkTextBTreeNode *node;
6880 GtkTextLineSegment *seg;
6882 GSList *all_tags, *taglist = NULL;
6884 GtkTextTagInfo *info;
6887 * Make sure that the tag toggle counts and the tag root pointers are OK.
6889 all_tags = list_of_tags (tree->table);
6890 for (taglist = all_tags; taglist != NULL ; taglist = taglist->next)
6892 tag = taglist->data;
6893 info = gtk_text_btree_get_existing_tag_info (tree, tag);
6896 node = info->tag_root;
6899 if (info->toggle_count != 0)
6901 g_error ("_gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6902 tag->name, info->toggle_count);
6904 continue; /* no ranges for the tag */
6906 else if (info->toggle_count == 0)
6908 g_error ("_gtk_text_btree_check found root for \"%s\" with no toggles",
6911 else if (info->toggle_count & 1)
6913 g_error ("_gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6914 tag->name, info->toggle_count);
6916 for (summary = node->summary; summary != NULL;
6917 summary = summary->next)
6919 if (summary->info->tag == tag)
6921 g_error ("_gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6925 if (node->level > 0)
6927 for (node = node->children.node ; node != NULL ;
6930 for (summary = node->summary; summary != NULL;
6931 summary = summary->next)
6933 if (summary->info->tag == tag)
6935 count += summary->toggle_count;
6942 GtkTextLineSegmentClass * last = NULL;
6944 for (line = node->children.line ; line != NULL ;
6947 for (seg = line->segments; seg != NULL;
6950 if ((seg->type == >k_text_toggle_on_type ||
6951 seg->type == >k_text_toggle_off_type) &&
6952 seg->body.toggle.info->tag == tag)
6954 if (last == seg->type)
6955 g_error ("Two consecutive toggles on or off weren't merged");
6956 if (!seg->body.toggle.inNodeCounts)
6957 g_error ("Toggle segment not in the node counts");
6966 if (count != info->toggle_count)
6968 g_error ("_gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
6969 info->toggle_count, tag->name, count);
6974 g_slist_free (all_tags);
6977 * Call a recursive procedure to do the main body of checks.
6980 node = tree->root_node;
6981 gtk_text_btree_node_check_consistency (tree, tree->root_node);
6984 * Make sure that there are at least two lines in the text and
6985 * that the last line has no characters except a newline.
6988 if (node->num_lines < 2)
6990 g_error ("_gtk_text_btree_check: less than 2 lines in tree");
6992 if (node->num_chars < 2)
6994 g_error ("_gtk_text_btree_check: less than 2 chars in tree");
6996 while (node->level > 0)
6998 node = node->children.node;
6999 while (node->next != NULL)
7004 line = node->children.line;
7005 while (line->next != NULL)
7009 seg = line->segments;
7010 while ((seg->type == >k_text_toggle_off_type)
7011 || (seg->type == >k_text_right_mark_type)
7012 || (seg->type == >k_text_left_mark_type))
7015 * It's OK to toggle a tag off in the last line, but
7016 * not to start a new range. It's also OK to have marks
7022 if (seg->type != >k_text_char_type)
7024 g_error ("_gtk_text_btree_check: last line has bogus segment type");
7026 if (seg->next != NULL)
7028 g_error ("_gtk_text_btree_check: last line has too many segments");
7030 if (seg->byte_count != 1)
7032 g_error ("_gtk_text_btree_check: last line has wrong # characters: %d",
7035 if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
7037 g_error ("_gtk_text_btree_check: last line had bad value: %s",
7042 void _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line);
7043 void _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment* seg);
7044 void _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent);
7045 void _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
7048 _gtk_text_btree_spew (GtkTextBTree *tree)
7053 printf ("%d lines in tree %p\n",
7054 _gtk_text_btree_line_count (tree), tree);
7056 line = _gtk_text_btree_get_line (tree, 0, &real_line);
7058 while (line != NULL)
7060 _gtk_text_btree_spew_line (tree, line);
7061 line = _gtk_text_line_next (line);
7064 printf ("=================== Tag information\n");
7069 list = tree->tag_infos;
7071 while (list != NULL)
7073 GtkTextTagInfo *info;
7077 printf (" tag `%s': root at %p, toggle count %d\n",
7078 info->tag->name, info->tag_root, info->toggle_count);
7080 list = g_slist_next (list);
7083 if (tree->tag_infos == NULL)
7085 printf (" (no tags in the tree)\n");
7089 printf ("=================== Tree nodes\n");
7092 _gtk_text_btree_spew_node (tree->root_node, 0);
7097 _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
7100 GtkTextLineSegment *seg;
7102 spaces = g_strnfill (indent, ' ');
7104 printf ("%sline %p chars %d bytes %d\n",
7106 _gtk_text_line_char_count (line),
7107 _gtk_text_line_byte_count (line));
7109 seg = line->segments;
7112 if (seg->type == >k_text_char_type)
7114 gchar* str = g_strndup (seg->body.chars, MIN (seg->byte_count, 10));
7119 if (*s == '\n' || *s == '\r')
7123 printf ("%s chars `%s'...\n", spaces, str);
7126 else if (seg->type == >k_text_right_mark_type)
7128 printf ("%s right mark `%s' visible: %d\n",
7130 seg->body.mark.name,
7131 seg->body.mark.visible);
7133 else if (seg->type == >k_text_left_mark_type)
7135 printf ("%s left mark `%s' visible: %d\n",
7137 seg->body.mark.name,
7138 seg->body.mark.visible);
7140 else if (seg->type == >k_text_toggle_on_type ||
7141 seg->type == >k_text_toggle_off_type)
7143 printf ("%s tag `%s' %s\n",
7144 spaces, seg->body.toggle.info->tag->name,
7145 seg->type == >k_text_toggle_off_type ? "off" : "on");
7155 _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent)
7158 GtkTextBTreeNode *iter;
7161 spaces = g_strnfill (indent, ' ');
7163 printf ("%snode %p level %d children %d lines %d chars %d\n",
7164 spaces, node, node->level,
7165 node->num_children, node->num_lines, node->num_chars);
7170 printf ("%s %d toggles of `%s' below this node\n",
7171 spaces, s->toggle_count, s->info->tag->name);
7177 if (node->level > 0)
7179 iter = node->children.node;
7180 while (iter != NULL)
7182 _gtk_text_btree_spew_node (iter, indent + 2);
7189 GtkTextLine *line = node->children.line;
7190 while (line != NULL)
7192 _gtk_text_btree_spew_line_short (line, indent + 2);
7200 _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line)
7202 GtkTextLineSegment * seg;
7204 printf ("%4d| line: %p parent: %p next: %p\n",
7205 _gtk_text_line_get_number (line), line, line->parent, line->next);
7207 seg = line->segments;
7211 _gtk_text_btree_spew_segment (tree, seg);
7217 _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment * seg)
7219 printf (" segment: %p type: %s bytes: %d chars: %d\n",
7220 seg, seg->type->name, seg->byte_count, seg->char_count);
7222 if (seg->type == >k_text_char_type)
7224 gchar* str = g_strndup (seg->body.chars, seg->byte_count);
7225 printf (" `%s'\n", str);
7228 else if (seg->type == >k_text_right_mark_type)
7230 printf (" right mark `%s' visible: %d not_deleteable: %d\n",
7231 seg->body.mark.name,
7232 seg->body.mark.visible,
7233 seg->body.mark.not_deleteable);
7235 else if (seg->type == >k_text_left_mark_type)
7237 printf (" left mark `%s' visible: %d not_deleteable: %d\n",
7238 seg->body.mark.name,
7239 seg->body.mark.visible,
7240 seg->body.mark.not_deleteable);
7242 else if (seg->type == >k_text_toggle_on_type ||
7243 seg->type == >k_text_toggle_off_type)
7245 printf (" tag `%s' priority %d\n",
7246 seg->body.toggle.info->tag->name,
7247 seg->body.toggle.info->tag->priority);
7251 #define __GTK_TEXT_BTREE_C__
7252 #include "gtkaliasdef.c"