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 "gtktexttagprivate.h"
63 #include "gtktexttagtable.h"
64 #include "gtktextlayout.h"
65 #include "gtktextiterprivate.h"
67 #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 int num_lines; /* Total number of lines (leaves) in
147 * the subtree rooted here. */
148 int num_chars; /* Number of chars below here */
149 int num_children; /* Number of children of this node. */
150 union { /* First in linked list of children. */
151 struct _GtkTextBTreeNode *node; /* Used if level > 0. */
152 GtkTextLine *line; /* Used if level == 0. */
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);
285 static void gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node);
287 static void gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node,
289 static NodeData * gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
291 static NodeData * gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
293 static void gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
296 static void gtk_text_btree_node_remove_view (BTreeView *view,
297 GtkTextBTreeNode *node,
299 static void gtk_text_btree_node_destroy (GtkTextBTree *tree,
300 GtkTextBTreeNode *node);
301 static void gtk_text_btree_node_free_empty (GtkTextBTree *tree,
302 GtkTextBTreeNode *node);
303 static NodeData * gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node,
305 static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
307 static void gtk_text_btree_node_get_size (GtkTextBTreeNode *node,
311 static GtkTextBTreeNode * gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
312 GtkTextBTreeNode *node2);
313 static void get_tree_bounds (GtkTextBTree *tree,
316 static void tag_changed_cb (GtkTextTagTable *table,
318 gboolean size_changed,
320 static void cleanup_line (GtkTextLine *line);
321 static void recompute_node_counts (GtkTextBTree *tree,
322 GtkTextBTreeNode *node);
323 static void inc_count (GtkTextTag *tag,
325 TagInfo *tagInfoPtr);
327 static void summary_destroy (Summary *summary);
329 static void gtk_text_btree_link_segment (GtkTextLineSegment *seg,
330 const GtkTextIter *iter);
331 static void gtk_text_btree_unlink_segment (GtkTextBTree *tree,
332 GtkTextLineSegment *seg,
336 static GtkTextTagInfo *gtk_text_btree_get_tag_info (GtkTextBTree *tree,
338 static GtkTextTagInfo *gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
340 static void gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
343 static void redisplay_region (GtkTextBTree *tree,
344 const GtkTextIter *start,
345 const GtkTextIter *end,
346 gboolean cursors_only);
348 /* Inline thingies */
351 segments_changed (GtkTextBTree *tree)
353 tree->segments_changed_stamp += 1;
357 chars_changed (GtkTextBTree *tree)
359 tree->chars_changed_stamp += 1;
367 _gtk_text_btree_new (GtkTextTagTable *table,
368 GtkTextBuffer *buffer)
371 GtkTextBTreeNode *root_node;
372 GtkTextLine *line, *line2;
374 g_return_val_if_fail (GTK_IS_TEXT_TAG_TABLE (table), NULL);
375 g_return_val_if_fail (GTK_IS_TEXT_BUFFER (buffer), NULL);
378 * The tree will initially have two empty lines. The second line
379 * isn't actually part of the tree's contents, but its presence
380 * makes several operations easier. The tree will have one GtkTextBTreeNode,
381 * which is also the root of the tree.
384 /* Create the root node. */
386 root_node = gtk_text_btree_node_new ();
388 line = gtk_text_line_new ();
389 line2 = gtk_text_line_new ();
391 root_node->parent = NULL;
392 root_node->next = NULL;
393 root_node->summary = NULL;
394 root_node->level = 0;
395 root_node->children.line = line;
396 root_node->num_children = 2;
397 root_node->num_lines = 2;
398 root_node->num_chars = 2;
400 line->parent = root_node;
403 line->segments = _gtk_char_segment_new ("\n", 1);
405 line2->parent = root_node;
407 line2->segments = _gtk_char_segment_new ("\n", 1);
409 /* Create the tree itself */
411 tree = g_new0(GtkTextBTree, 1);
412 tree->root_node = root_node;
416 /* Set these to values that are unlikely to be found
417 * in random memory garbage, and also avoid
418 * duplicates between tree instances.
420 tree->chars_changed_stamp = g_random_int ();
421 tree->segments_changed_stamp = g_random_int ();
423 tree->last_line_stamp = tree->chars_changed_stamp - 1;
424 tree->last_line = NULL;
426 tree->end_iter_line_stamp = tree->chars_changed_stamp - 1;
427 tree->end_iter_segment_stamp = tree->segments_changed_stamp - 1;
428 tree->end_iter_line = NULL;
429 tree->end_iter_segment_byte_index = 0;
430 tree->end_iter_segment_char_offset = 0;
432 g_object_ref (tree->table);
434 tree->tag_changed_handler = g_signal_connect (tree->table,
436 G_CALLBACK (tag_changed_cb),
439 tree->mark_table = g_hash_table_new (g_str_hash, g_str_equal);
440 tree->child_anchor_table = NULL;
442 /* We don't ref the buffer, since the buffer owns us;
443 * we'd have some circularity issues. The buffer always
444 * lasts longer than the BTree
446 tree->buffer = buffer;
450 GtkTextLineSegment *seg;
452 _gtk_text_btree_get_iter_at_line_char (tree, &start, 0, 0);
455 tree->insert_mark = _gtk_text_btree_set_mark (tree,
462 seg = tree->insert_mark->segment;
464 seg->body.mark.not_deleteable = TRUE;
465 seg->body.mark.visible = TRUE;
467 tree->selection_bound_mark = _gtk_text_btree_set_mark (tree,
474 seg = tree->selection_bound_mark->segment;
476 seg->body.mark.not_deleteable = TRUE;
478 g_object_ref (tree->insert_mark);
479 g_object_ref (tree->selection_bound_mark);
488 _gtk_text_btree_ref (GtkTextBTree *tree)
490 g_return_if_fail (tree != NULL);
491 g_return_if_fail (tree->refcount > 0);
497 _gtk_text_btree_unref (GtkTextBTree *tree)
499 g_return_if_fail (tree != NULL);
500 g_return_if_fail (tree->refcount > 0);
504 if (tree->refcount == 0)
506 g_signal_handler_disconnect (tree->table,
507 tree->tag_changed_handler);
509 g_object_unref (tree->table);
512 gtk_text_btree_node_destroy (tree, tree->root_node);
513 tree->root_node = NULL;
515 g_assert (g_hash_table_size (tree->mark_table) == 0);
516 g_hash_table_destroy (tree->mark_table);
517 tree->mark_table = NULL;
518 if (tree->child_anchor_table != NULL)
520 g_hash_table_destroy (tree->child_anchor_table);
521 tree->child_anchor_table = NULL;
524 g_object_unref (tree->insert_mark);
525 tree->insert_mark = NULL;
526 g_object_unref (tree->selection_bound_mark);
527 tree->selection_bound_mark = NULL;
534 _gtk_text_btree_get_buffer (GtkTextBTree *tree)
540 _gtk_text_btree_get_chars_changed_stamp (GtkTextBTree *tree)
542 return tree->chars_changed_stamp;
546 _gtk_text_btree_get_segments_changed_stamp (GtkTextBTree *tree)
548 return tree->segments_changed_stamp;
552 _gtk_text_btree_segments_changed (GtkTextBTree *tree)
554 g_return_if_fail (tree != NULL);
555 segments_changed (tree);
559 * Indexable segment mutation
563 * The following function is responsible for resolving the bidi direction
564 * for the lines between start and end. But it also calculates any
565 * dependent bidi direction for surrounding lines that change as a result
566 * of the bidi direction decisions within the range. The function is
567 * trying to do as little propagation as is needed.
570 gtk_text_btree_resolve_bidi (GtkTextIter *start,
573 GtkTextBTree *tree = _gtk_text_iter_get_btree (start);
574 GtkTextLine *start_line, *end_line, *start_line_prev, *end_line_next, *line;
575 PangoDirection last_strong, dir_above_propagated, dir_below_propagated;
577 /* Resolve the strong bidi direction for all lines between
580 start_line = _gtk_text_iter_get_text_line (start);
581 start_line_prev = _gtk_text_line_previous (start_line);
582 end_line = _gtk_text_iter_get_text_line (end);
583 end_line_next = _gtk_text_line_next (end_line);
586 while (line && line != end_line_next)
588 /* Loop through the segments and search for a strong character
590 GtkTextLineSegment *seg = line->segments;
591 line->dir_strong = PANGO_DIRECTION_NEUTRAL;
595 if (seg->type == >k_text_char_type && seg->byte_count > 0)
597 PangoDirection pango_dir;
599 pango_dir = pango_find_base_dir (seg->body.chars,
602 if (pango_dir != PANGO_DIRECTION_NEUTRAL)
604 line->dir_strong = pango_dir;
611 line = _gtk_text_line_next (line);
616 /* The variable dir_above_propagated contains the forward propagated
617 * direction before start. It is neutral if start is in the beginning
620 dir_above_propagated = PANGO_DIRECTION_NEUTRAL;
622 dir_above_propagated = start_line_prev->dir_propagated_forward;
624 /* Loop forward and propagate the direction of each paragraph
625 * to all neutral lines.
628 last_strong = dir_above_propagated;
629 while (line != end_line_next)
631 if (line->dir_strong != PANGO_DIRECTION_NEUTRAL)
632 last_strong = line->dir_strong;
634 line->dir_propagated_forward = last_strong;
636 line = _gtk_text_line_next (line);
639 /* Continue propagating as long as the previous resolved forward
640 * is different from last_strong.
643 GtkTextIter end_propagate;
646 line->dir_strong == PANGO_DIRECTION_NEUTRAL &&
647 line->dir_propagated_forward != last_strong)
649 GtkTextLine *prev = line;
650 line->dir_propagated_forward = last_strong;
652 line = _gtk_text_line_next(line);
660 /* The last line to invalidate is the last line before the
661 * line with the strong character. Or in case of the end of the
662 * buffer, the last line of the buffer. (There seems to be an
663 * extra "virtual" last line in the buffer that must not be used
664 * calling _gtk_text_btree_get_iter_at_line (causes crash). Thus the
665 * _gtk_text_line_previous is ok in that case as well.)
667 line = _gtk_text_line_previous (line);
668 _gtk_text_btree_get_iter_at_line (tree, &end_propagate, line, 0);
669 _gtk_text_btree_invalidate_region (tree, end, &end_propagate, FALSE);
674 /* The variable dir_below_propagated contains the backward propagated
675 * direction after end. It is neutral if end is at the end of
678 dir_below_propagated = PANGO_DIRECTION_NEUTRAL;
680 dir_below_propagated = end_line_next->dir_propagated_back;
682 /* Loop backward and propagate the direction of each paragraph
683 * to all neutral lines.
686 last_strong = dir_below_propagated;
687 while (line != start_line_prev)
689 if (line->dir_strong != PANGO_DIRECTION_NEUTRAL)
690 last_strong = line->dir_strong;
692 line->dir_propagated_back = last_strong;
694 line = _gtk_text_line_previous (line);
697 /* Continue propagating as long as the resolved backward dir
698 * is different from last_strong.
701 GtkTextIter start_propagate;
704 line->dir_strong == PANGO_DIRECTION_NEUTRAL &&
705 line->dir_propagated_back != last_strong)
707 GtkTextLine *prev = line;
708 line->dir_propagated_back = last_strong;
710 line = _gtk_text_line_previous (line);
718 /* We only need to invalidate for backwards propagation if the
719 * line we ended up on didn't get a direction from forwards
722 if (line && line->dir_propagated_forward == PANGO_DIRECTION_NEUTRAL)
724 _gtk_text_btree_get_iter_at_line (tree, &start_propagate, line, 0);
725 _gtk_text_btree_invalidate_region (tree, &start_propagate, start, FALSE);
731 _gtk_text_btree_delete (GtkTextIter *start,
734 GtkTextLineSegment *prev_seg; /* The segment just before the start
735 * of the deletion range. */
736 GtkTextLineSegment *last_seg; /* The segment just after the end
737 * of the deletion range. */
738 GtkTextLineSegment *seg, *next, *next2;
739 GtkTextLine *curline;
740 GtkTextBTreeNode *curnode, *node;
742 GtkTextLine *start_line;
743 GtkTextLine *end_line;
745 GtkTextLine *deleted_lines = NULL; /* List of lines we've deleted */
746 gint start_byte_offset;
748 g_return_if_fail (start != NULL);
749 g_return_if_fail (end != NULL);
750 g_return_if_fail (_gtk_text_iter_get_btree (start) ==
751 _gtk_text_iter_get_btree (end));
753 gtk_text_iter_order (start, end);
755 tree = _gtk_text_iter_get_btree (start);
757 if (gtk_get_debug_flags () & GTK_DEBUG_TEXT)
758 _gtk_text_btree_check (tree);
760 /* Broadcast the need for redisplay before we break the iterators */
761 DV (g_print ("invalidating due to deleting some text (%s)\n", G_STRLOC));
762 _gtk_text_btree_invalidate_region (tree, start, end, FALSE);
764 /* Save the byte offset so we can reset the iterators */
765 start_byte_offset = gtk_text_iter_get_line_index (start);
767 start_line = _gtk_text_iter_get_text_line (start);
768 end_line = _gtk_text_iter_get_text_line (end);
771 * Split the start and end segments, so we have a place
772 * to insert our new text.
774 * Tricky point: split at end first; otherwise the split
775 * at end may invalidate seg and/or prev_seg. This allows
776 * us to avoid invalidating segments for start.
779 last_seg = gtk_text_line_segment_split (end);
780 if (last_seg != NULL)
781 last_seg = last_seg->next;
783 last_seg = end_line->segments;
785 prev_seg = gtk_text_line_segment_split (start);
786 if (prev_seg != NULL)
788 seg = prev_seg->next;
789 prev_seg->next = last_seg;
793 seg = start_line->segments;
794 start_line->segments = last_seg;
797 /* notify iterators that their segments need recomputation,
798 just for robustness. */
799 segments_changed (tree);
802 * Delete all of the segments between prev_seg and last_seg.
805 curline = start_line;
806 curnode = curline->parent;
807 while (seg != last_seg)
813 GtkTextLine *nextline;
816 * We just ran off the end of a line. First find the
817 * next line, then go back to the old line and delete it
818 * (unless it's the starting line for the range).
821 nextline = _gtk_text_line_next (curline);
822 if (curline != start_line)
824 if (curnode == start_line->parent)
825 start_line->next = curline->next;
827 curnode->children.line = curline->next;
829 for (node = curnode; node != NULL;
832 /* Don't update node->num_chars, because
833 * that was done when we deleted the segments.
835 node->num_lines -= 1;
838 curnode->num_children -= 1;
839 curline->next = deleted_lines;
840 deleted_lines = curline;
844 seg = curline->segments;
847 * If the GtkTextBTreeNode is empty then delete it and its parents,
848 * recursively upwards until a non-empty GtkTextBTreeNode is found.
851 while (curnode->num_children == 0)
853 GtkTextBTreeNode *parent;
855 parent = curnode->parent;
856 if (parent->children.node == curnode)
858 parent->children.node = curnode->next;
862 GtkTextBTreeNode *prevnode = parent->children.node;
863 while (prevnode->next != curnode)
865 prevnode = prevnode->next;
867 prevnode->next = curnode->next;
869 parent->num_children--;
870 gtk_text_btree_node_free_empty (tree, curnode);
873 curnode = curline->parent;
878 char_count = seg->char_count;
880 if ((*seg->type->deleteFunc)(seg, curline, FALSE) != 0)
883 * This segment refuses to die. Move it to prev_seg and
884 * advance prev_seg if the segment has left gravity.
887 if (prev_seg == NULL)
889 seg->next = start_line->segments;
890 start_line->segments = seg;
892 else if (prev_seg->next &&
893 prev_seg->next != last_seg &&
894 seg->type == >k_text_toggle_off_type &&
895 prev_seg->next->type == >k_text_toggle_on_type &&
896 seg->body.toggle.info == prev_seg->next->body.toggle.info)
898 /* Try to match an off toggle with the matching on toggle
899 * if it immediately follows. This is a common case, and
900 * handling it here prevents quadratic blowup in
901 * cleanup_line() below. See bug 317125.
903 next2 = prev_seg->next->next;
904 g_free ((char *)prev_seg->next);
905 prev_seg->next = next2;
906 g_free ((char *)seg);
911 seg->next = prev_seg->next;
912 prev_seg->next = seg;
915 if (seg && seg->type->leftGravity)
922 /* Segment is gone. Decrement the char count of the node and
924 for (node = curnode; node != NULL;
927 node->num_chars -= char_count;
935 * If the beginning and end of the deletion range are in different
936 * lines, join the two lines together and discard the ending line.
939 if (start_line != end_line)
942 GtkTextBTreeNode *ancestor_node;
943 GtkTextLine *prevline;
946 /* last_seg was appended to start_line up at the top of this function */
948 for (seg = last_seg; seg != NULL;
951 chars_moved += seg->char_count;
952 if (seg->type->lineChangeFunc != NULL)
954 (*seg->type->lineChangeFunc)(seg, end_line);
958 for (node = start_line->parent; node != NULL;
961 node->num_chars += chars_moved;
964 curnode = end_line->parent;
965 for (node = curnode; node != NULL;
968 node->num_chars -= chars_moved;
971 curnode->num_children--;
972 prevline = curnode->children.line;
973 if (prevline == end_line)
975 curnode->children.line = end_line->next;
979 while (prevline->next != end_line)
981 prevline = prevline->next;
983 prevline->next = end_line->next;
985 end_line->next = deleted_lines;
986 deleted_lines = end_line;
988 /* We now fix up the per-view aggregates. We add all the height and
989 * width for the deleted lines to the start line, so that when revalidation
990 * occurs, the correct change in size is seen.
992 ancestor_node = gtk_text_btree_node_common_parent (curnode, start_line->parent);
998 gint deleted_width = 0;
999 gint deleted_height = 0;
1001 line = deleted_lines;
1004 GtkTextLine *next_line = line->next;
1005 ld = _gtk_text_line_get_data (line, view->view_id);
1009 deleted_width = MAX (deleted_width, ld->width);
1010 deleted_height += ld->height;
1016 if (deleted_width > 0 || deleted_height > 0)
1018 ld = _gtk_text_line_get_data (start_line, view->view_id);
1022 /* This means that start_line has never been validated.
1023 * We don't really want to do the validation here but
1024 * we do need to store our temporary sizes. So we
1025 * create the line data and assume a line w/h of 0.
1027 ld = _gtk_text_line_data_new (view->layout, start_line);
1028 _gtk_text_line_add_data (start_line, ld);
1034 ld->width = MAX (deleted_width, ld->width);
1035 ld->height += deleted_height;
1039 gtk_text_btree_node_check_valid_downward (ancestor_node, view->view_id);
1040 if (ancestor_node->parent)
1041 gtk_text_btree_node_check_valid_upward (ancestor_node->parent, view->view_id);
1046 line = deleted_lines;
1049 GtkTextLine *next_line = line->next;
1051 gtk_text_line_destroy (tree, line);
1056 /* avoid dangling pointer */
1057 deleted_lines = NULL;
1059 gtk_text_btree_rebalance (tree, curnode);
1063 * Cleanup the segments in the new line.
1066 cleanup_line (start_line);
1069 * Lastly, rebalance the first GtkTextBTreeNode of the range.
1072 gtk_text_btree_rebalance (tree, start_line->parent);
1074 /* Notify outstanding iterators that they
1076 chars_changed (tree);
1077 segments_changed (tree);
1079 if (gtk_get_debug_flags () & GTK_DEBUG_TEXT)
1080 _gtk_text_btree_check (tree);
1082 /* Re-initialize our iterators */
1083 _gtk_text_btree_get_iter_at_line (tree, start, start_line, start_byte_offset);
1086 gtk_text_btree_resolve_bidi (start, end);
1090 _gtk_text_btree_insert (GtkTextIter *iter,
1094 GtkTextLineSegment *prev_seg; /* The segment just before the first
1095 * new segment (NULL means new segment
1096 * is at beginning of line). */
1097 GtkTextLineSegment *cur_seg; /* Current segment; new characters
1098 * are inserted just after this one.
1099 * NULL means insert at beginning of
1101 GtkTextLine *line; /* Current line (new segments are
1102 * added to this line). */
1103 GtkTextLineSegment *seg;
1104 GtkTextLine *newline;
1105 int chunk_len; /* # characters in current chunk. */
1106 gint sol; /* start of line */
1107 gint eol; /* Pointer to character just after last
1108 * one in current chunk.
1110 gint delim; /* index of paragraph delimiter */
1111 int line_count_delta; /* Counts change to total number of
1115 int char_count_delta; /* change to number of chars */
1117 gint start_byte_index;
1118 GtkTextLine *start_line;
1120 g_return_if_fail (text != NULL);
1121 g_return_if_fail (iter != NULL);
1124 len = strlen (text);
1126 /* extract iterator info */
1127 tree = _gtk_text_iter_get_btree (iter);
1128 line = _gtk_text_iter_get_text_line (iter);
1131 start_byte_index = gtk_text_iter_get_line_index (iter);
1133 /* Get our insertion segment split. Note this assumes line allows
1134 * char insertions, which isn't true of the "last" line. But iter
1135 * should not be on that line, as we assert here.
1137 g_assert (!_gtk_text_line_is_last (line, tree));
1138 prev_seg = gtk_text_line_segment_split (iter);
1141 /* Invalidate all iterators */
1142 chars_changed (tree);
1143 segments_changed (tree);
1146 * Chop the text up into lines and create a new segment for
1147 * each line, plus a new line for the leftovers from the
1153 line_count_delta = 0;
1154 char_count_delta = 0;
1159 pango_find_paragraph_boundary (text + sol,
1164 /* make these relative to the start of the text */
1168 g_assert (eol >= sol);
1169 g_assert (delim >= sol);
1170 g_assert (eol >= delim);
1171 g_assert (sol >= 0);
1172 g_assert (eol <= len);
1174 chunk_len = eol - sol;
1176 g_assert (g_utf8_validate (&text[sol], chunk_len, NULL));
1177 seg = _gtk_char_segment_new (&text[sol], chunk_len);
1179 char_count_delta += seg->char_count;
1181 if (cur_seg == NULL)
1183 seg->next = line->segments;
1184 line->segments = seg;
1188 seg->next = cur_seg->next;
1189 cur_seg->next = seg;
1194 /* chunk didn't end with a paragraph separator */
1195 g_assert (eol == len);
1200 * The chunk ended with a newline, so create a new GtkTextLine
1201 * and move the remainder of the old line to it.
1204 newline = gtk_text_line_new ();
1205 gtk_text_line_set_parent (newline, line->parent);
1206 newline->next = line->next;
1207 line->next = newline;
1208 newline->segments = seg->next;
1216 * Cleanup the starting line for the insertion, plus the ending
1217 * line if it's different.
1220 cleanup_line (start_line);
1221 if (line != start_line)
1223 cleanup_line (line);
1226 post_insert_fixup (tree, line, line_count_delta, char_count_delta);
1228 /* Invalidate our region, and reset the iterator the user
1229 passed in to point to the end of the inserted text. */
1235 _gtk_text_btree_get_iter_at_line (tree,
1241 /* We could almost certainly be more efficient here
1242 by saving the information from the insertion loop
1244 gtk_text_iter_forward_chars (&end, char_count_delta);
1246 DV (g_print ("invalidating due to inserting some text (%s)\n", G_STRLOC));
1247 _gtk_text_btree_invalidate_region (tree, &start, &end, FALSE);
1250 /* Convenience for the user */
1253 gtk_text_btree_resolve_bidi (&start, &end);
1258 insert_pixbuf_or_widget_segment (GtkTextIter *iter,
1259 GtkTextLineSegment *seg)
1263 GtkTextLineSegment *prevPtr;
1266 gint start_byte_offset;
1268 line = _gtk_text_iter_get_text_line (iter);
1269 tree = _gtk_text_iter_get_btree (iter);
1270 start_byte_offset = gtk_text_iter_get_line_index (iter);
1272 prevPtr = gtk_text_line_segment_split (iter);
1273 if (prevPtr == NULL)
1275 seg->next = line->segments;
1276 line->segments = seg;
1280 seg->next = prevPtr->next;
1281 prevPtr->next = seg;
1284 post_insert_fixup (tree, line, 0, seg->char_count);
1286 chars_changed (tree);
1287 segments_changed (tree);
1289 /* reset *iter for the user, and invalidate tree nodes */
1291 _gtk_text_btree_get_iter_at_line (tree, &start, line, start_byte_offset);
1294 gtk_text_iter_forward_char (iter); /* skip forward past the segment */
1296 DV (g_print ("invalidating due to inserting pixbuf/widget (%s)\n", G_STRLOC));
1297 _gtk_text_btree_invalidate_region (tree, &start, iter, FALSE);
1301 _gtk_text_btree_insert_pixbuf (GtkTextIter *iter,
1304 GtkTextLineSegment *seg;
1306 seg = _gtk_pixbuf_segment_new (pixbuf);
1308 insert_pixbuf_or_widget_segment (iter, seg);
1312 _gtk_text_btree_insert_child_anchor (GtkTextIter *iter,
1313 GtkTextChildAnchor *anchor)
1315 GtkTextLineSegment *seg;
1318 if (anchor->segment != NULL)
1320 g_warning (G_STRLOC": Same child anchor can't be inserted twice");
1324 seg = _gtk_widget_segment_new (anchor);
1326 tree = seg->body.child.tree = _gtk_text_iter_get_btree (iter);
1327 seg->body.child.line = _gtk_text_iter_get_text_line (iter);
1329 insert_pixbuf_or_widget_segment (iter, seg);
1331 if (tree->child_anchor_table == NULL)
1332 tree->child_anchor_table = g_hash_table_new (NULL, NULL);
1334 g_hash_table_insert (tree->child_anchor_table,
1335 seg->body.child.obj,
1336 seg->body.child.obj);
1340 _gtk_text_btree_unregister_child_anchor (GtkTextChildAnchor *anchor)
1342 GtkTextLineSegment *seg;
1344 seg = anchor->segment;
1346 g_hash_table_remove (seg->body.child.tree->child_anchor_table,
1355 find_line_by_y (GtkTextBTree *tree, BTreeView *view,
1356 GtkTextBTreeNode *node, gint y, gint *line_top,
1357 GtkTextLine *last_line)
1361 if (gtk_get_debug_flags () & GTK_DEBUG_TEXT)
1362 _gtk_text_btree_check (tree);
1364 if (node->level == 0)
1368 line = node->children.line;
1370 while (line != NULL && line != last_line)
1372 GtkTextLineData *ld;
1374 ld = _gtk_text_line_get_data (line, view->view_id);
1378 if (y < (current_y + (ld ? ld->height : 0)))
1381 current_y += ld->height;
1382 *line_top += ld->height;
1391 GtkTextBTreeNode *child;
1393 child = node->children.node;
1395 while (child != NULL)
1400 gtk_text_btree_node_get_size (child, view->view_id,
1403 if (y < (current_y + height))
1404 return find_line_by_y (tree, view, child,
1405 y - current_y, line_top,
1408 current_y += height;
1409 *line_top += height;
1411 child = child->next;
1419 _gtk_text_btree_find_line_by_y (GtkTextBTree *tree,
1426 GtkTextLine *last_line;
1429 view = gtk_text_btree_get_view (tree, view_id);
1430 g_return_val_if_fail (view != NULL, NULL);
1432 last_line = get_last_line (tree);
1434 line = find_line_by_y (tree, view, tree->root_node, ypixel, &line_top,
1438 *line_top_out = line_top;
1444 find_line_top_in_line_list (GtkTextBTree *tree,
1447 GtkTextLine *target_line,
1450 while (line != NULL)
1452 GtkTextLineData *ld;
1454 if (line == target_line)
1457 ld = _gtk_text_line_get_data (line, view->view_id);
1464 g_assert_not_reached (); /* If we get here, our
1465 target line didn't exist
1466 under its parent node */
1471 _gtk_text_btree_find_line_top (GtkTextBTree *tree,
1472 GtkTextLine *target_line,
1479 GtkTextBTreeNode *node;
1481 view = gtk_text_btree_get_view (tree, view_id);
1483 g_return_val_if_fail (view != NULL, 0);
1486 node = target_line->parent;
1487 while (node != NULL)
1489 nodes = g_slist_prepend (nodes, node);
1490 node = node->parent;
1494 while (iter != NULL)
1498 if (node->level == 0)
1500 g_slist_free (nodes);
1501 return find_line_top_in_line_list (tree, view,
1502 node->children.line,
1507 GtkTextBTreeNode *child;
1508 GtkTextBTreeNode *target_node;
1510 g_assert (iter->next != NULL); /* not at level 0 */
1511 target_node = iter->next->data;
1513 child = node->children.node;
1515 while (child != NULL)
1520 if (child == target_node)
1524 gtk_text_btree_node_get_size (child, view->view_id,
1528 child = child->next;
1530 g_assert (child != NULL); /* should have broken out before we
1534 iter = g_slist_next (iter);
1537 g_assert_not_reached (); /* we return when we find the target line */
1542 _gtk_text_btree_add_view (GtkTextBTree *tree,
1543 GtkTextLayout *layout)
1546 GtkTextLine *last_line;
1547 GtkTextLineData *line_data;
1549 g_return_if_fail (tree != NULL);
1551 view = g_new (BTreeView, 1);
1553 view->view_id = layout;
1554 view->layout = layout;
1556 view->next = tree->views;
1561 g_assert (tree->views->prev == NULL);
1562 tree->views->prev = view;
1567 /* The last line in the buffer has identity values for the per-view
1568 * data so that we can avoid special case checks for it in a large
1571 last_line = get_last_line (tree);
1573 line_data = g_new (GtkTextLineData, 1);
1574 line_data->view_id = layout;
1575 line_data->next = NULL;
1576 line_data->width = 0;
1577 line_data->height = 0;
1578 line_data->valid = TRUE;
1580 _gtk_text_line_add_data (last_line, line_data);
1584 _gtk_text_btree_remove_view (GtkTextBTree *tree,
1588 GtkTextLine *last_line;
1589 GtkTextLineData *line_data;
1591 g_return_if_fail (tree != NULL);
1595 while (view != NULL)
1597 if (view->view_id == view_id)
1603 g_return_if_fail (view != NULL);
1606 view->next->prev = view->prev;
1609 view->prev->next = view->next;
1611 if (view == tree->views)
1612 tree->views = view->next;
1614 /* Remove the line data for the last line which we added ourselves.
1615 * (Do this first, so that we don't try to call the view's line data destructor on it.)
1617 last_line = get_last_line (tree);
1618 line_data = _gtk_text_line_remove_data (last_line, view_id);
1621 gtk_text_btree_node_remove_view (view, tree->root_node, view_id);
1623 view->layout = (gpointer) 0xdeadbeef;
1624 view->view_id = (gpointer) 0xdeadbeef;
1630 _gtk_text_btree_invalidate_region (GtkTextBTree *tree,
1631 const GtkTextIter *start,
1632 const GtkTextIter *end,
1633 gboolean cursors_only)
1639 while (view != NULL)
1642 gtk_text_layout_invalidate_cursors (view->layout, start, end);
1644 gtk_text_layout_invalidate (view->layout, start, end);
1651 _gtk_text_btree_get_view_size (GtkTextBTree *tree,
1656 g_return_if_fail (tree != NULL);
1657 g_return_if_fail (view_id != NULL);
1659 gtk_text_btree_node_get_size (tree->root_node, view_id,
1674 iter_stack_new (void)
1677 stack = g_slice_new (IterStack);
1678 stack->iters = NULL;
1685 iter_stack_push (IterStack *stack,
1686 const GtkTextIter *iter)
1689 if (stack->count > stack->alloced)
1691 stack->alloced = stack->count*2;
1692 stack->iters = g_realloc (stack->iters,
1693 stack->alloced * sizeof (GtkTextIter));
1695 stack->iters[stack->count-1] = *iter;
1699 iter_stack_pop (IterStack *stack,
1702 if (stack->count == 0)
1707 *iter = stack->iters[stack->count];
1713 iter_stack_free (IterStack *stack)
1715 g_free (stack->iters);
1716 g_slice_free (IterStack, stack);
1720 iter_stack_invert (IterStack *stack)
1722 if (stack->count > 0)
1725 guint j = stack->count - 1;
1730 tmp = stack->iters[i];
1731 stack->iters[i] = stack->iters[j];
1732 stack->iters[j] = tmp;
1741 queue_tag_redisplay (GtkTextBTree *tree,
1743 const GtkTextIter *start,
1744 const GtkTextIter *end)
1746 if (_gtk_text_tag_affects_size (tag))
1748 DV (g_print ("invalidating due to size-affecting tag (%s)\n", G_STRLOC));
1749 _gtk_text_btree_invalidate_region (tree, start, end, FALSE);
1751 else if (_gtk_text_tag_affects_nonsize_appearance (tag))
1753 /* We only need to queue a redraw, not a relayout */
1754 redisplay_region (tree, start, end, FALSE);
1757 /* We don't need to do anything if the tag doesn't affect display */
1761 _gtk_text_btree_tag (const GtkTextIter *start_orig,
1762 const GtkTextIter *end_orig,
1766 GtkTextLineSegment *seg, *prev;
1767 GtkTextLine *cleanupline;
1768 gboolean toggled_on;
1769 GtkTextLine *start_line;
1770 GtkTextLine *end_line;
1772 GtkTextIter start, end;
1775 GtkTextTagInfo *info;
1777 g_return_if_fail (start_orig != NULL);
1778 g_return_if_fail (end_orig != NULL);
1779 g_return_if_fail (GTK_IS_TEXT_TAG (tag));
1780 g_return_if_fail (_gtk_text_iter_get_btree (start_orig) ==
1781 _gtk_text_iter_get_btree (end_orig));
1782 g_return_if_fail (tag->priv->table == _gtk_text_iter_get_btree (start_orig)->table);
1785 printf ("%s tag %s from %d to %d\n",
1786 add ? "Adding" : "Removing",
1788 gtk_text_buffer_get_offset (start_orig),
1789 gtk_text_buffer_get_offset (end_orig));
1792 if (gtk_text_iter_equal (start_orig, end_orig))
1795 start = *start_orig;
1798 gtk_text_iter_order (&start, &end);
1800 tree = _gtk_text_iter_get_btree (&start);
1802 queue_tag_redisplay (tree, tag, &start, &end);
1804 info = gtk_text_btree_get_tag_info (tree, tag);
1806 start_line = _gtk_text_iter_get_text_line (&start);
1807 end_line = _gtk_text_iter_get_text_line (&end);
1809 /* Find all tag toggles in the region; we are going to delete them.
1810 We need to find them in advance, because
1811 forward_find_tag_toggle () won't work once we start playing around
1813 stack = iter_stack_new ();
1816 /* forward_to_tag_toggle() skips a toggle at the start iterator,
1817 * which is deliberate - we don't want to delete a toggle at the
1820 while (gtk_text_iter_forward_to_tag_toggle (&iter, tag))
1822 if (gtk_text_iter_compare (&iter, &end) >= 0)
1825 iter_stack_push (stack, &iter);
1828 /* We need to traverse the toggles in order. */
1829 iter_stack_invert (stack);
1832 * See whether the tag is present at the start of the range. If
1833 * the state doesn't already match what we want then add a toggle
1837 toggled_on = gtk_text_iter_has_tag (&start, tag);
1838 if ( (add && !toggled_on) ||
1839 (!add && toggled_on) )
1841 /* This could create a second toggle at the start position;
1842 cleanup_line () will remove it if so. */
1843 seg = _gtk_toggle_segment_new (info, add);
1845 prev = gtk_text_line_segment_split (&start);
1848 seg->next = start_line->segments;
1849 start_line->segments = seg;
1853 seg->next = prev->next;
1857 /* cleanup_line adds the new toggle to the node counts. */
1859 printf ("added toggle at start\n");
1861 /* we should probably call segments_changed, but in theory
1862 any still-cached segments in the iters we are about to
1863 use are still valid, since they're in front
1869 * Scan the range of characters and delete any internal tag
1870 * transitions. Keep track of what the old state was at the end
1871 * of the range, and add a toggle there if it's needed.
1875 cleanupline = start_line;
1876 while (iter_stack_pop (stack, &iter))
1878 GtkTextLineSegment *indexable_seg;
1881 line = _gtk_text_iter_get_text_line (&iter);
1882 seg = _gtk_text_iter_get_any_segment (&iter);
1883 indexable_seg = _gtk_text_iter_get_indexable_segment (&iter);
1885 g_assert (seg != NULL);
1886 g_assert (indexable_seg != NULL);
1887 g_assert (seg != indexable_seg);
1889 prev = line->segments;
1891 /* Find the segment that actually toggles this tag. */
1892 while (seg != indexable_seg)
1894 g_assert (seg != NULL);
1895 g_assert (indexable_seg != NULL);
1896 g_assert (seg != indexable_seg);
1898 if ( (seg->type == >k_text_toggle_on_type ||
1899 seg->type == >k_text_toggle_off_type) &&
1900 (seg->body.toggle.info == info) )
1906 g_assert (seg != NULL);
1907 g_assert (indexable_seg != NULL);
1909 g_assert (seg != indexable_seg); /* If this happens, then
1910 forward_to_tag_toggle was
1912 g_assert (seg->body.toggle.info->tag == tag);
1914 /* If this happens, when previously tagging we didn't merge
1915 overlapping tags. */
1916 g_assert ( (toggled_on && seg->type == >k_text_toggle_off_type) ||
1917 (!toggled_on && seg->type == >k_text_toggle_on_type) );
1919 toggled_on = !toggled_on;
1922 printf ("deleting %s toggle\n",
1923 seg->type == >k_text_toggle_on_type ? "on" : "off");
1925 /* Remove toggle segment from the list. */
1928 line->segments = seg->next;
1932 while (prev->next != seg)
1936 prev->next = seg->next;
1939 /* Inform iterators we've hosed them. This actually reflects a
1940 bit of inefficiency; if you have the same tag toggled on and
1941 off a lot in a single line, we keep having the rescan from
1942 the front of the line. Of course we have to do that to get
1943 "prev" anyway, but here we are doing it an additional
1945 segments_changed (tree);
1947 /* Update node counts */
1948 if (seg->body.toggle.inNodeCounts)
1950 _gtk_change_node_toggle_count (line->parent,
1952 seg->body.toggle.inNodeCounts = FALSE;
1957 /* We only clean up lines when we're done with them, saves some
1958 gratuitous line-segment-traversals */
1960 if (cleanupline != line)
1962 cleanup_line (cleanupline);
1967 iter_stack_free (stack);
1969 /* toggled_on now reflects the toggle state _just before_ the
1970 end iterator. The end iterator could already have a toggle
1971 on or a toggle off. */
1972 if ( (add && !toggled_on) ||
1973 (!add && toggled_on) )
1975 /* This could create a second toggle at the start position;
1976 cleanup_line () will remove it if so. */
1978 seg = _gtk_toggle_segment_new (info, !add);
1980 prev = gtk_text_line_segment_split (&end);
1983 seg->next = end_line->segments;
1984 end_line->segments = seg;
1988 seg->next = prev->next;
1991 /* cleanup_line adds the new toggle to the node counts. */
1992 g_assert (seg->body.toggle.inNodeCounts == FALSE);
1994 printf ("added toggle at end\n");
1999 * Cleanup cleanupline and the last line of the range, if
2000 * these are different.
2003 cleanup_line (cleanupline);
2004 if (cleanupline != end_line)
2006 cleanup_line (end_line);
2009 segments_changed (tree);
2011 queue_tag_redisplay (tree, tag, &start, &end);
2013 if (gtk_get_debug_flags () & GTK_DEBUG_TEXT)
2014 _gtk_text_btree_check (tree);
2023 get_line_internal (GtkTextBTree *tree,
2025 gint *real_line_number,
2026 gboolean include_last)
2028 GtkTextBTreeNode *node;
2033 line_count = _gtk_text_btree_line_count (tree);
2037 if (line_number < 0)
2039 line_number = line_count;
2041 else if (line_number > line_count)
2043 line_number = line_count;
2046 if (real_line_number)
2047 *real_line_number = line_number;
2049 node = tree->root_node;
2050 lines_left = line_number;
2053 * Work down through levels of the tree until a GtkTextBTreeNode is found at
2057 while (node->level != 0)
2059 for (node = node->children.node;
2060 node->num_lines <= lines_left;
2066 g_error ("gtk_text_btree_find_line ran out of GtkTextBTreeNodes");
2069 lines_left -= node->num_lines;
2074 * Work through the lines attached to the level-0 GtkTextBTreeNode.
2077 for (line = node->children.line; lines_left > 0;
2083 g_error ("gtk_text_btree_find_line ran out of lines");
2092 _gtk_text_btree_get_end_iter_line (GtkTextBTree *tree)
2095 _gtk_text_btree_get_line (tree,
2096 _gtk_text_btree_line_count (tree) - 1,
2101 _gtk_text_btree_get_line (GtkTextBTree *tree,
2103 gint *real_line_number)
2105 return get_line_internal (tree, line_number, real_line_number, TRUE);
2109 _gtk_text_btree_get_line_no_last (GtkTextBTree *tree,
2111 gint *real_line_number)
2113 return get_line_internal (tree, line_number, real_line_number, FALSE);
2117 _gtk_text_btree_get_line_at_char (GtkTextBTree *tree,
2119 gint *line_start_index,
2120 gint *real_char_index)
2122 GtkTextBTreeNode *node;
2124 GtkTextLineSegment *seg;
2128 node = tree->root_node;
2130 /* Clamp to valid indexes (-1 is magic for "highest index"),
2131 * node->num_chars includes the two newlines that aren't really
2134 if (char_index < 0 || char_index >= (node->num_chars - 1))
2136 char_index = node->num_chars - 2;
2139 *real_char_index = char_index;
2142 * Work down through levels of the tree until a GtkTextBTreeNode is found at
2146 chars_left = char_index;
2147 while (node->level != 0)
2149 for (node = node->children.node;
2150 chars_left >= node->num_chars;
2153 chars_left -= node->num_chars;
2155 g_assert (chars_left >= 0);
2159 if (chars_left == 0)
2161 /* Start of a line */
2163 *line_start_index = char_index;
2164 return node->children.line;
2168 * Work through the lines attached to the level-0 GtkTextBTreeNode.
2173 for (line = node->children.line; line != NULL; line = line->next)
2175 seg = line->segments;
2178 if (chars_in_line + seg->char_count > chars_left)
2179 goto found; /* found our line/segment */
2181 chars_in_line += seg->char_count;
2186 chars_left -= chars_in_line;
2194 g_assert (line != NULL); /* hosage, ran out of lines */
2195 g_assert (seg != NULL);
2197 *line_start_index = char_index - chars_left;
2201 /* It returns an array sorted by tags priority, ready to pass to
2202 * _gtk_text_attributes_fill_from_tags() */
2204 _gtk_text_btree_get_tags (const GtkTextIter *iter,
2207 GtkTextBTreeNode *node;
2208 GtkTextLine *siblingline;
2209 GtkTextLineSegment *seg;
2210 int src, dst, index;
2215 #define NUM_TAG_INFOS 10
2217 line = _gtk_text_iter_get_text_line (iter);
2218 byte_index = gtk_text_iter_get_line_index (iter);
2220 tagInfo.numTags = 0;
2221 tagInfo.arraySize = NUM_TAG_INFOS;
2222 tagInfo.tags = g_new (GtkTextTag*, NUM_TAG_INFOS);
2223 tagInfo.counts = g_new (int, NUM_TAG_INFOS);
2226 * Record tag toggles within the line of indexPtr but preceding
2227 * indexPtr. Note that if this loop segfaults, your
2228 * byte_index probably points past the sum of all
2229 * seg->byte_count */
2231 for (index = 0, seg = line->segments;
2232 (index + seg->byte_count) <= byte_index;
2233 index += seg->byte_count, seg = seg->next)
2235 if ((seg->type == >k_text_toggle_on_type)
2236 || (seg->type == >k_text_toggle_off_type))
2238 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2243 * Record toggles for tags in lines that are predecessors of
2244 * line but under the same level-0 GtkTextBTreeNode.
2247 for (siblingline = line->parent->children.line;
2248 siblingline != line;
2249 siblingline = siblingline->next)
2251 for (seg = siblingline->segments; seg != NULL;
2254 if ((seg->type == >k_text_toggle_on_type)
2255 || (seg->type == >k_text_toggle_off_type))
2257 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2263 * For each GtkTextBTreeNode in the ancestry of this line, record tag
2264 * toggles for all siblings that precede that GtkTextBTreeNode.
2267 for (node = line->parent; node->parent != NULL;
2268 node = node->parent)
2270 GtkTextBTreeNode *siblingPtr;
2273 for (siblingPtr = node->parent->children.node;
2274 siblingPtr != node; siblingPtr = siblingPtr->next)
2276 for (summary = siblingPtr->summary; summary != NULL;
2277 summary = summary->next)
2279 if (summary->toggle_count & 1)
2281 inc_count (summary->info->tag, summary->toggle_count,
2289 * Go through the tag information and squash out all of the tags
2290 * that have even toggle counts (these tags exist before the point
2291 * of interest, but not at the desired character itself).
2294 for (src = 0, dst = 0; src < tagInfo.numTags; src++)
2296 if (tagInfo.counts[src] & 1)
2298 g_assert (GTK_IS_TEXT_TAG (tagInfo.tags[src]));
2299 tagInfo.tags[dst] = tagInfo.tags[src];
2305 g_free (tagInfo.counts);
2308 g_free (tagInfo.tags);
2312 /* Sort tags in ascending order of priority */
2313 _gtk_text_tag_array_sort (tagInfo.tags, dst);
2315 return tagInfo.tags;
2319 copy_segment (GString *string,
2320 gboolean include_hidden,
2321 gboolean include_nonchars,
2322 const GtkTextIter *start,
2323 const GtkTextIter *end)
2325 GtkTextLineSegment *end_seg;
2326 GtkTextLineSegment *seg;
2328 if (gtk_text_iter_equal (start, end))
2331 seg = _gtk_text_iter_get_indexable_segment (start);
2332 end_seg = _gtk_text_iter_get_indexable_segment (end);
2334 if (seg->type == >k_text_char_type)
2336 gboolean copy = TRUE;
2337 gint copy_bytes = 0;
2338 gint copy_start = 0;
2340 /* Don't copy if we're invisible; segments are invisible/not
2341 as a whole, no need to check each char */
2342 if (!include_hidden &&
2343 _gtk_text_btree_char_is_invisible (start))
2346 /* printf (" <invisible>\n"); */
2349 copy_start = _gtk_text_iter_get_segment_byte (start);
2353 /* End is in the same segment; need to copy fewer bytes. */
2354 gint end_byte = _gtk_text_iter_get_segment_byte (end);
2356 copy_bytes = end_byte - copy_start;
2359 copy_bytes = seg->byte_count - copy_start;
2361 g_assert (copy_bytes != 0); /* Due to iter equality check at
2362 front of this function. */
2366 g_assert ((copy_start + copy_bytes) <= seg->byte_count);
2368 g_string_append_len (string,
2369 seg->body.chars + copy_start,
2373 /* printf (" :%s\n", string->str); */
2375 else if (seg->type == >k_text_pixbuf_type ||
2376 seg->type == >k_text_child_type)
2378 gboolean copy = TRUE;
2380 if (!include_nonchars)
2384 else if (!include_hidden &&
2385 _gtk_text_btree_char_is_invisible (start))
2392 g_string_append_len (string,
2393 _gtk_text_unknown_char_utf8,
2394 GTK_TEXT_UNKNOWN_CHAR_UTF8_LEN);
2401 _gtk_text_btree_get_text (const GtkTextIter *start_orig,
2402 const GtkTextIter *end_orig,
2403 gboolean include_hidden,
2404 gboolean include_nonchars)
2406 GtkTextLineSegment *seg;
2407 GtkTextLineSegment *end_seg;
2414 g_return_val_if_fail (start_orig != NULL, NULL);
2415 g_return_val_if_fail (end_orig != NULL, NULL);
2416 g_return_val_if_fail (_gtk_text_iter_get_btree (start_orig) ==
2417 _gtk_text_iter_get_btree (end_orig), NULL);
2419 start = *start_orig;
2422 gtk_text_iter_order (&start, &end);
2424 retval = g_string_new (NULL);
2426 end_seg = _gtk_text_iter_get_indexable_segment (&end);
2428 seg = _gtk_text_iter_get_indexable_segment (&iter);
2429 while (seg != end_seg)
2431 copy_segment (retval, include_hidden, include_nonchars,
2434 _gtk_text_iter_forward_indexable_segment (&iter);
2436 seg = _gtk_text_iter_get_indexable_segment (&iter);
2439 copy_segment (retval, include_hidden, include_nonchars, &iter, &end);
2442 g_string_free (retval, FALSE);
2447 _gtk_text_btree_line_count (GtkTextBTree *tree)
2449 /* Subtract bogus line at the end; we return a count
2451 return tree->root_node->num_lines - 1;
2455 _gtk_text_btree_char_count (GtkTextBTree *tree)
2457 /* Exclude newline in bogus last line and the
2458 * one in the last line that is after the end iterator
2460 return tree->root_node->num_chars - 2;
2463 #define LOTSA_TAGS 1000
2465 _gtk_text_btree_char_is_invisible (const GtkTextIter *iter)
2467 gboolean invisible = FALSE; /* if nobody says otherwise, it's visible */
2469 int deftagCnts[LOTSA_TAGS] = { 0, };
2470 int *tagCnts = deftagCnts;
2471 GtkTextTag *deftags[LOTSA_TAGS];
2472 GtkTextTag **tags = deftags;
2474 GtkTextBTreeNode *node;
2475 GtkTextLine *siblingline;
2476 GtkTextLineSegment *seg;
2483 line = _gtk_text_iter_get_text_line (iter);
2484 tree = _gtk_text_iter_get_btree (iter);
2485 byte_index = gtk_text_iter_get_line_index (iter);
2487 numTags = gtk_text_tag_table_get_size (tree->table);
2489 /* almost always avoid malloc, so stay out of system calls */
2490 if (LOTSA_TAGS < numTags)
2492 tagCnts = g_new0 (int, numTags);
2493 tags = g_new (GtkTextTag*, numTags);
2497 * Record tag toggles within the line of indexPtr but preceding
2501 for (index = 0, seg = line->segments;
2502 (index + seg->byte_count) <= byte_index; /* segfault here means invalid index */
2503 index += seg->byte_count, seg = seg->next)
2505 if ((seg->type == >k_text_toggle_on_type)
2506 || (seg->type == >k_text_toggle_off_type))
2508 tag = seg->body.toggle.info->tag;
2509 if (tag->priv->invisible_set)
2511 tags[tag->priv->priority] = tag;
2512 tagCnts[tag->priv->priority]++;
2518 * Record toggles for tags in lines that are predecessors of
2519 * line but under the same level-0 GtkTextBTreeNode.
2522 for (siblingline = line->parent->children.line;
2523 siblingline != line;
2524 siblingline = siblingline->next)
2526 for (seg = siblingline->segments; seg != NULL;
2529 if ((seg->type == >k_text_toggle_on_type)
2530 || (seg->type == >k_text_toggle_off_type))
2532 tag = seg->body.toggle.info->tag;
2533 if (tag->priv->invisible_set)
2535 tags[tag->priv->priority] = tag;
2536 tagCnts[tag->priv->priority]++;
2543 * For each GtkTextBTreeNode in the ancestry of this line, record tag toggles
2544 * for all siblings that precede that GtkTextBTreeNode.
2547 for (node = line->parent; node->parent != NULL;
2548 node = node->parent)
2550 GtkTextBTreeNode *siblingPtr;
2553 for (siblingPtr = node->parent->children.node;
2554 siblingPtr != node; siblingPtr = siblingPtr->next)
2556 for (summary = siblingPtr->summary; summary != NULL;
2557 summary = summary->next)
2559 if (summary->toggle_count & 1)
2561 tag = summary->info->tag;
2562 if (tag->priv->invisible_set)
2564 tags[tag->priv->priority] = tag;
2565 tagCnts[tag->priv->priority] += summary->toggle_count;
2573 * Now traverse from highest priority to lowest,
2574 * take invisible value from first odd count (= on)
2577 for (i = numTags-1; i >=0; i--)
2581 /* FIXME not sure this should be if 0 */
2583 #ifndef ALWAYS_SHOW_SELECTION
2584 /* who would make the selection invisible? */
2585 if ((tag == tkxt->seltag)
2586 && !(tkxt->flags & GOT_FOCUS))
2592 invisible = tags[i]->priv->values->invisible;
2597 if (LOTSA_TAGS < numTags)
2612 redisplay_region (GtkTextBTree *tree,
2613 const GtkTextIter *start,
2614 const GtkTextIter *end,
2615 gboolean cursors_only)
2618 GtkTextLine *start_line, *end_line;
2620 if (gtk_text_iter_compare (start, end) > 0)
2622 const GtkTextIter *tmp = start;
2627 start_line = _gtk_text_iter_get_text_line (start);
2628 end_line = _gtk_text_iter_get_text_line (end);
2631 while (view != NULL)
2633 gint start_y, end_y;
2634 GtkTextLineData *ld;
2636 start_y = _gtk_text_btree_find_line_top (tree, start_line, view->view_id);
2638 if (end_line == start_line)
2641 end_y = _gtk_text_btree_find_line_top (tree, end_line, view->view_id);
2643 ld = _gtk_text_line_get_data (end_line, view->view_id);
2645 end_y += ld->height;
2648 gtk_text_layout_cursors_changed (view->layout, start_y,
2652 gtk_text_layout_changed (view->layout, start_y,
2661 redisplay_mark (GtkTextLineSegment *mark)
2665 gboolean cursor_only;
2667 _gtk_text_btree_get_iter_at_mark (mark->body.mark.tree,
2669 mark->body.mark.obj);
2672 gtk_text_iter_forward_char (&end);
2674 DV (g_print ("invalidating due to moving visible mark (%s)\n", G_STRLOC));
2675 cursor_only = mark == mark->body.mark.tree->insert_mark->segment;
2676 _gtk_text_btree_invalidate_region (mark->body.mark.tree, &iter, &end, cursor_only);
2680 redisplay_mark_if_visible (GtkTextLineSegment *mark)
2682 if (!mark->body.mark.visible)
2685 redisplay_mark (mark);
2689 ensure_not_off_end (GtkTextBTree *tree,
2690 GtkTextLineSegment *mark,
2693 if (gtk_text_iter_get_line (iter) == _gtk_text_btree_line_count (tree))
2694 gtk_text_iter_backward_char (iter);
2697 static GtkTextLineSegment*
2698 real_set_mark (GtkTextBTree *tree,
2699 GtkTextMark *existing_mark,
2701 gboolean left_gravity,
2702 const GtkTextIter *where,
2703 gboolean should_exist,
2704 gboolean redraw_selections)
2706 GtkTextLineSegment *mark;
2709 g_return_val_if_fail (tree != NULL, NULL);
2710 g_return_val_if_fail (where != NULL, NULL);
2711 g_return_val_if_fail (_gtk_text_iter_get_btree (where) == tree, NULL);
2715 if (gtk_text_mark_get_buffer (existing_mark) != NULL)
2716 mark = existing_mark->segment;
2720 else if (name != NULL)
2721 mark = g_hash_table_lookup (tree->mark_table,
2726 if (should_exist && mark == NULL)
2728 g_warning ("No mark `%s' exists!", name);
2732 /* OK if !should_exist and it does already exist, in that case
2738 if (gtk_get_debug_flags () & GTK_DEBUG_TEXT)
2739 _gtk_text_iter_check (&iter);
2743 if (redraw_selections &&
2744 (mark == tree->insert_mark->segment ||
2745 mark == tree->selection_bound_mark->segment))
2747 GtkTextIter old_pos;
2749 _gtk_text_btree_get_iter_at_mark (tree, &old_pos,
2750 mark->body.mark.obj);
2751 redisplay_region (tree, &old_pos, where, TRUE);
2755 * don't let visible marks be after the final newline of the
2759 if (mark->body.mark.visible)
2761 ensure_not_off_end (tree, mark, &iter);
2764 /* Redraw the mark's old location. */
2765 redisplay_mark_if_visible (mark);
2767 /* Unlink mark from its current location.
2768 This could hose our iterator... */
2769 gtk_text_btree_unlink_segment (tree, mark,
2770 mark->body.mark.line);
2771 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2772 g_assert (mark->body.mark.line == _gtk_text_iter_get_text_line (&iter));
2774 segments_changed (tree); /* make sure the iterator recomputes its
2780 g_object_ref (existing_mark);
2782 existing_mark = gtk_text_mark_new (name, left_gravity);
2784 mark = existing_mark->segment;
2785 _gtk_mark_segment_set_tree (mark, tree);
2787 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2789 if (mark->body.mark.name)
2790 g_hash_table_insert (tree->mark_table,
2791 mark->body.mark.name,
2795 if (gtk_get_debug_flags () & GTK_DEBUG_TEXT)
2796 _gtk_text_iter_check (&iter);
2798 /* Link mark into new location */
2799 gtk_text_btree_link_segment (mark, &iter);
2801 /* Invalidate some iterators. */
2802 segments_changed (tree);
2805 * update the screen at the mark's new location.
2808 redisplay_mark_if_visible (mark);
2810 if (gtk_get_debug_flags () & GTK_DEBUG_TEXT)
2811 _gtk_text_iter_check (&iter);
2813 if (gtk_get_debug_flags () & GTK_DEBUG_TEXT)
2814 _gtk_text_btree_check (tree);
2821 _gtk_text_btree_set_mark (GtkTextBTree *tree,
2822 GtkTextMark *existing_mark,
2824 gboolean left_gravity,
2825 const GtkTextIter *iter,
2826 gboolean should_exist)
2828 GtkTextLineSegment *seg;
2830 seg = real_set_mark (tree, existing_mark,
2831 name, left_gravity, iter, should_exist,
2834 return seg ? seg->body.mark.obj : NULL;
2838 _gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2842 GtkTextIter tmp_start, tmp_end;
2844 _gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2846 _gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2847 tree->selection_bound_mark);
2849 if (gtk_text_iter_equal (&tmp_start, &tmp_end))
2861 gtk_text_iter_order (&tmp_start, &tmp_end);
2874 _gtk_text_btree_place_cursor (GtkTextBTree *tree,
2875 const GtkTextIter *iter)
2877 _gtk_text_btree_select_range (tree, iter, iter);
2881 _gtk_text_btree_select_range (GtkTextBTree *tree,
2882 const GtkTextIter *ins,
2883 const GtkTextIter *bound)
2885 GtkTextIter old_ins, old_bound;
2887 _gtk_text_btree_get_iter_at_mark (tree, &old_ins,
2889 _gtk_text_btree_get_iter_at_mark (tree, &old_bound,
2890 tree->selection_bound_mark);
2892 /* Check if it's no-op since gtk_text_buffer_place_cursor()
2893 * also calls this, and this will redraw the cursor line. */
2894 if (!gtk_text_iter_equal (&old_ins, ins) ||
2895 !gtk_text_iter_equal (&old_bound, bound))
2897 redisplay_region (tree, &old_ins, &old_bound, TRUE);
2899 /* Move insert AND selection_bound before we redisplay */
2900 real_set_mark (tree, tree->insert_mark,
2901 "insert", FALSE, ins, TRUE, FALSE);
2902 real_set_mark (tree, tree->selection_bound_mark,
2903 "selection_bound", FALSE, bound, TRUE, FALSE);
2905 redisplay_region (tree, ins, bound, TRUE);
2911 _gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2916 g_return_if_fail (tree != NULL);
2917 g_return_if_fail (name != NULL);
2919 mark = g_hash_table_lookup (tree->mark_table,
2922 _gtk_text_btree_remove_mark (tree, mark);
2926 _gtk_text_btree_release_mark_segment (GtkTextBTree *tree,
2927 GtkTextLineSegment *segment)
2930 if (segment->body.mark.name)
2931 g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2933 segment->body.mark.tree = NULL;
2934 segment->body.mark.line = NULL;
2936 /* Remove the ref on the mark, which frees segment as a side effect
2937 * if this is the last reference.
2939 g_object_unref (segment->body.mark.obj);
2943 _gtk_text_btree_remove_mark (GtkTextBTree *tree,
2946 GtkTextLineSegment *segment;
2948 g_return_if_fail (mark != NULL);
2949 g_return_if_fail (tree != NULL);
2951 segment = mark->segment;
2953 if (segment->body.mark.not_deleteable)
2955 g_warning ("Can't delete special mark `%s'", segment->body.mark.name);
2959 /* This calls cleanup_line and segments_changed */
2960 gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2962 _gtk_text_btree_release_mark_segment (tree, segment);
2966 _gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2967 GtkTextMark *segment)
2969 return segment == tree->insert_mark;
2973 _gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2974 GtkTextMark *segment)
2976 return segment == tree->selection_bound_mark;
2980 _gtk_text_btree_get_insert (GtkTextBTree *tree)
2982 return tree->insert_mark;
2986 _gtk_text_btree_get_selection_bound (GtkTextBTree *tree)
2988 return tree->selection_bound_mark;
2992 _gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2995 GtkTextLineSegment *seg;
2997 g_return_val_if_fail (tree != NULL, NULL);
2998 g_return_val_if_fail (name != NULL, NULL);
3000 seg = g_hash_table_lookup (tree->mark_table, name);
3002 return seg ? seg->body.mark.obj : NULL;
3006 * gtk_text_mark_set_visible:
3007 * @mark: a #GtkTextMark
3008 * @setting: visibility of mark
3010 * Sets the visibility of @mark; the insertion point is normally
3011 * visible, i.e. you can see it as a vertical bar. Also, the text
3012 * widget uses a visible mark to indicate where a drop will occur when
3013 * dragging-and-dropping text. Most other marks are not visible.
3014 * Marks are not visible by default.
3018 gtk_text_mark_set_visible (GtkTextMark *mark,
3021 GtkTextLineSegment *seg;
3023 g_return_if_fail (mark != NULL);
3025 seg = mark->segment;
3027 if (seg->body.mark.visible == setting)
3031 seg->body.mark.visible = setting;
3033 if (seg->body.mark.tree)
3034 redisplay_mark (seg);
3039 _gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
3042 GtkTextBTreeNode *node;
3043 GtkTextTagInfo *info;
3045 g_return_val_if_fail (tree != NULL, NULL);
3049 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3054 if (info->tag_root == NULL)
3057 node = info->tag_root;
3059 /* We know the tag root has instances of the given
3062 continue_outer_loop:
3063 g_assert (node != NULL);
3064 while (node->level > 0)
3066 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
3067 node = node->children.node;
3068 while (node != NULL)
3070 if (gtk_text_btree_node_has_tag (node, tag))
3071 goto continue_outer_loop;
3075 g_assert (node != NULL);
3078 g_assert (node != NULL); /* The tag summaries said some node had
3081 g_assert (node->level == 0);
3083 return node->children.line;
3087 /* Looking for any tag at all (tag == NULL).
3088 Unfortunately this can't be done in a simple and efficient way
3089 right now; so I'm just going to return the
3090 first line in the btree. FIXME */
3091 return _gtk_text_btree_get_line (tree, 0, NULL);
3096 _gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
3099 GtkTextBTreeNode *node;
3100 GtkTextBTreeNode *last_node;
3102 GtkTextTagInfo *info;
3104 g_return_val_if_fail (tree != NULL, NULL);
3108 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3110 if (info->tag_root == NULL)
3113 node = info->tag_root;
3114 /* We know the tag root has instances of the given
3117 while (node->level > 0)
3119 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
3121 node = node->children.node;
3122 while (node != NULL)
3124 if (gtk_text_btree_node_has_tag (node, tag))
3132 g_assert (node != NULL); /* The tag summaries said some node had
3135 g_assert (node->level == 0);
3137 /* Find the last line in this node */
3138 line = node->children.line;
3139 while (line->next != NULL)
3146 /* This search can't be done efficiently at the moment,
3147 at least not without complexity.
3148 So, we just return the last line.
3150 return _gtk_text_btree_get_end_iter_line (tree);
3160 _gtk_text_line_get_number (GtkTextLine *line)
3163 GtkTextBTreeNode *node, *parent, *node2;
3167 * First count how many lines precede this one in its level-0
3171 node = line->parent;
3173 for (line2 = node->children.line; line2 != line;
3174 line2 = line2->next)
3178 g_error ("gtk_text_btree_line_number couldn't find line");
3184 * Now work up through the levels of the tree one at a time,
3185 * counting how many lines are in GtkTextBTreeNodes preceding the current
3189 for (parent = node->parent ; parent != NULL;
3190 node = parent, parent = parent->parent)
3192 for (node2 = parent->children.node; node2 != node;
3193 node2 = node2->next)
3197 g_error ("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
3199 index += node2->num_lines;
3205 static GtkTextLineSegment*
3206 find_toggle_segment_before_char (GtkTextLine *line,
3210 GtkTextLineSegment *seg;
3211 GtkTextLineSegment *toggle_seg;
3216 seg = line->segments;
3217 while ( (index + seg->char_count) <= char_in_line )
3219 if (((seg->type == >k_text_toggle_on_type)
3220 || (seg->type == >k_text_toggle_off_type))
3221 && (seg->body.toggle.info->tag == tag))
3224 index += seg->char_count;
3231 static GtkTextLineSegment*
3232 find_toggle_segment_before_byte (GtkTextLine *line,
3236 GtkTextLineSegment *seg;
3237 GtkTextLineSegment *toggle_seg;
3242 seg = line->segments;
3243 while ( (index + seg->byte_count) <= byte_in_line )
3245 if (((seg->type == >k_text_toggle_on_type)
3246 || (seg->type == >k_text_toggle_off_type))
3247 && (seg->body.toggle.info->tag == tag))
3250 index += seg->byte_count;
3258 find_toggle_outside_current_line (GtkTextLine *line,
3262 GtkTextBTreeNode *node;
3263 GtkTextLine *sibling_line;
3264 GtkTextLineSegment *seg;
3265 GtkTextLineSegment *toggle_seg;
3267 GtkTextTagInfo *info = NULL;
3270 * No toggle in this line. Look for toggles for the tag in lines
3271 * that are predecessors of line but under the same
3272 * level-0 GtkTextBTreeNode.
3275 sibling_line = line->parent->children.line;
3276 while (sibling_line != line)
3278 seg = sibling_line->segments;
3281 if (((seg->type == >k_text_toggle_on_type)
3282 || (seg->type == >k_text_toggle_off_type))
3283 && (seg->body.toggle.info->tag == tag))
3289 sibling_line = sibling_line->next;
3292 if (toggle_seg != NULL)
3293 return (toggle_seg->type == >k_text_toggle_on_type);
3296 * No toggle in this GtkTextBTreeNode. Scan upwards through the ancestors of
3297 * this GtkTextBTreeNode, counting the number of toggles of the given tag in
3298 * siblings that precede that GtkTextBTreeNode.
3301 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3307 node = line->parent;
3308 while (node->parent != NULL)
3310 GtkTextBTreeNode *sibling_node;
3312 sibling_node = node->parent->children.node;
3313 while (sibling_node != node)
3317 summary = sibling_node->summary;
3318 while (summary != NULL)
3320 if (summary->info == info)
3321 toggles += summary->toggle_count;
3323 summary = summary->next;
3326 sibling_node = sibling_node->next;
3329 if (node == info->tag_root)
3332 node = node->parent;
3336 * An odd number of toggles means that the tag is present at the
3340 return (toggles & 1) != 0;
3343 /* FIXME this function is far too slow, for no good reason. */
3345 _gtk_text_line_char_has_tag (GtkTextLine *line,
3350 GtkTextLineSegment *toggle_seg;
3352 g_return_val_if_fail (line != NULL, FALSE);
3355 * Check for toggles for the tag in the line but before
3356 * the char. If there is one, its type indicates whether or
3357 * not the character is tagged.
3360 toggle_seg = find_toggle_segment_before_char (line, char_in_line, tag);
3362 if (toggle_seg != NULL)
3363 return (toggle_seg->type == >k_text_toggle_on_type);
3365 return find_toggle_outside_current_line (line, tree, tag);
3369 _gtk_text_line_byte_has_tag (GtkTextLine *line,
3374 GtkTextLineSegment *toggle_seg;
3376 g_return_val_if_fail (line != NULL, FALSE);
3379 * Check for toggles for the tag in the line but before
3380 * the char. If there is one, its type indicates whether or
3381 * not the character is tagged.
3384 toggle_seg = find_toggle_segment_before_byte (line, byte_in_line, tag);
3386 if (toggle_seg != NULL)
3387 return (toggle_seg->type == >k_text_toggle_on_type);
3389 return find_toggle_outside_current_line (line, tree, tag);
3393 _gtk_text_line_is_last (GtkTextLine *line,
3396 return line == get_last_line (tree);
3400 ensure_end_iter_line (GtkTextBTree *tree)
3402 if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
3406 /* n_lines is without the magic line at the end */
3407 g_assert (_gtk_text_btree_line_count (tree) >= 1);
3409 tree->end_iter_line = _gtk_text_btree_get_line_no_last (tree, -1, &real_line);
3411 tree->end_iter_line_stamp = tree->chars_changed_stamp;
3416 ensure_end_iter_segment (GtkTextBTree *tree)
3418 if (tree->end_iter_segment_stamp != tree->segments_changed_stamp)
3420 GtkTextLineSegment *seg;
3421 GtkTextLineSegment *last_with_chars;
3423 ensure_end_iter_line (tree);
3425 last_with_chars = NULL;
3427 seg = tree->end_iter_line->segments;
3430 if (seg->char_count > 0)
3431 last_with_chars = seg;
3435 tree->end_iter_segment = last_with_chars;
3437 /* We know the last char in the last line is '\n' */
3438 tree->end_iter_segment_byte_index = last_with_chars->byte_count - 1;
3439 tree->end_iter_segment_char_offset = last_with_chars->char_count - 1;
3441 tree->end_iter_segment_stamp = tree->segments_changed_stamp;
3443 g_assert (tree->end_iter_segment->type == >k_text_char_type);
3444 g_assert (tree->end_iter_segment->body.chars[tree->end_iter_segment_byte_index] == '\n');
3449 _gtk_text_line_contains_end_iter (GtkTextLine *line,
3452 ensure_end_iter_line (tree);
3454 return line == tree->end_iter_line;
3458 _gtk_text_btree_is_end (GtkTextBTree *tree,
3460 GtkTextLineSegment *seg,
3464 g_return_val_if_fail (byte_index >= 0 || char_offset >= 0, FALSE);
3466 /* Do this first to avoid walking segments in most cases */
3467 if (!_gtk_text_line_contains_end_iter (line, tree))
3470 ensure_end_iter_segment (tree);
3472 if (seg != tree->end_iter_segment)
3475 if (byte_index >= 0)
3476 return byte_index == tree->end_iter_segment_byte_index;
3478 return char_offset == tree->end_iter_segment_char_offset;
3482 _gtk_text_line_next (GtkTextLine *line)
3484 GtkTextBTreeNode *node;
3486 if (line->next != NULL)
3491 * This was the last line associated with the particular parent
3492 * GtkTextBTreeNode. Search up the tree for the next GtkTextBTreeNode,
3493 * then search down from that GtkTextBTreeNode to find the first
3497 node = line->parent;
3498 while (node != NULL && node->next == NULL)
3499 node = node->parent;
3505 while (node->level > 0)
3507 node = node->children.node;
3510 g_assert (node->children.line != line);
3512 return node->children.line;
3517 _gtk_text_line_next_excluding_last (GtkTextLine *line)
3521 next = _gtk_text_line_next (line);
3523 /* If we were on the end iter line, we can't go to
3526 if (next && next->next == NULL && /* these checks are optimization only */
3527 _gtk_text_line_next (next) == NULL)
3534 _gtk_text_line_previous (GtkTextLine *line)
3536 GtkTextBTreeNode *node;
3537 GtkTextBTreeNode *node2;
3541 * Find the line under this GtkTextBTreeNode just before the starting line.
3543 prev = line->parent->children.line; /* First line at leaf */
3544 while (prev != line)
3546 if (prev->next == line)
3552 g_error ("gtk_text_btree_previous_line ran out of lines");
3556 * This was the first line associated with the particular parent
3557 * GtkTextBTreeNode. Search up the tree for the previous GtkTextBTreeNode,
3558 * then search down from that GtkTextBTreeNode to find its last line.
3560 for (node = line->parent; ; node = node->parent)
3562 if (node == NULL || node->parent == NULL)
3564 else if (node != node->parent->children.node)
3568 for (node2 = node->parent->children.node; ;
3569 node2 = node2->children.node)
3571 while (node2->next != node)
3572 node2 = node2->next;
3574 if (node2->level == 0)
3580 for (prev = node2->children.line ; ; prev = prev->next)
3582 if (prev->next == NULL)
3586 g_assert_not_reached ();
3592 _gtk_text_line_data_new (GtkTextLayout *layout,
3595 GtkTextLineData *line_data;
3597 line_data = g_new (GtkTextLineData, 1);
3599 line_data->view_id = layout;
3600 line_data->next = NULL;
3601 line_data->width = 0;
3602 line_data->height = 0;
3603 line_data->valid = FALSE;
3609 _gtk_text_line_add_data (GtkTextLine *line,
3610 GtkTextLineData *data)
3612 g_return_if_fail (line != NULL);
3613 g_return_if_fail (data != NULL);
3614 g_return_if_fail (data->view_id != NULL);
3618 data->next = line->views;
3628 _gtk_text_line_remove_data (GtkTextLine *line,
3631 GtkTextLineData *prev;
3632 GtkTextLineData *iter;
3634 g_return_val_if_fail (line != NULL, NULL);
3635 g_return_val_if_fail (view_id != NULL, NULL);
3639 while (iter != NULL)
3641 if (iter->view_id == view_id)
3650 prev->next = iter->next;
3652 line->views = iter->next;
3661 _gtk_text_line_get_data (GtkTextLine *line,
3664 GtkTextLineData *iter;
3666 g_return_val_if_fail (line != NULL, NULL);
3667 g_return_val_if_fail (view_id != NULL, NULL);
3670 while (iter != NULL)
3672 if (iter->view_id == view_id)
3681 _gtk_text_line_invalidate_wrap (GtkTextLine *line,
3682 GtkTextLineData *ld)
3684 /* For now this is totally unoptimized. FIXME?
3686 We could probably optimize the case where the width removed
3687 is less than the max width for the parent node,
3688 and the case where the height is unchanged when we re-wrap.
3691 g_return_if_fail (ld != NULL);
3694 gtk_text_btree_node_invalidate_upward (line->parent, ld->view_id);
3698 _gtk_text_line_char_count (GtkTextLine *line)
3700 GtkTextLineSegment *seg;
3704 seg = line->segments;
3707 size += seg->char_count;
3714 _gtk_text_line_byte_count (GtkTextLine *line)
3716 GtkTextLineSegment *seg;
3720 seg = line->segments;
3723 size += seg->byte_count;
3731 _gtk_text_line_char_index (GtkTextLine *target_line)
3733 GSList *node_stack = NULL;
3734 GtkTextBTreeNode *iter;
3738 /* Push all our parent nodes onto a stack */
3739 iter = target_line->parent;
3741 g_assert (iter != NULL);
3743 while (iter != NULL)
3745 node_stack = g_slist_prepend (node_stack, iter);
3747 iter = iter->parent;
3750 /* Check that we have the root node on top of the stack. */
3751 g_assert (node_stack != NULL &&
3752 node_stack->data != NULL &&
3753 ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3755 /* Add up chars in all nodes before the nodes in our stack.
3759 iter = node_stack->data;
3760 while (iter != NULL)
3762 GtkTextBTreeNode *child_iter;
3763 GtkTextBTreeNode *next_node;
3765 next_node = node_stack->next ?
3766 node_stack->next->data : NULL;
3767 node_stack = g_slist_remove (node_stack, node_stack->data);
3769 if (iter->level == 0)
3771 /* stack should be empty when we're on the last node */
3772 g_assert (node_stack == NULL);
3773 break; /* Our children are now lines */
3776 g_assert (next_node != NULL);
3777 g_assert (iter != NULL);
3778 g_assert (next_node->parent == iter);
3780 /* Add up chars before us in the tree */
3781 child_iter = iter->children.node;
3782 while (child_iter != next_node)
3784 g_assert (child_iter != NULL);
3786 num_chars += child_iter->num_chars;
3788 child_iter = child_iter->next;
3794 g_assert (iter != NULL);
3795 g_assert (iter == target_line->parent);
3797 /* Since we don't store char counts in lines, only in segments, we
3798 have to iterate over the lines adding up segment char counts
3799 until we find our line. */
3800 line = iter->children.line;
3801 while (line != target_line)
3803 g_assert (line != NULL);
3805 num_chars += _gtk_text_line_char_count (line);
3810 g_assert (line == target_line);
3816 _gtk_text_line_byte_to_segment (GtkTextLine *line,
3820 GtkTextLineSegment *seg;
3823 g_return_val_if_fail (line != NULL, NULL);
3825 offset = byte_offset;
3826 seg = line->segments;
3828 while (offset >= seg->byte_count)
3830 offset -= seg->byte_count;
3832 g_assert (seg != NULL); /* means an invalid byte index */
3836 *seg_offset = offset;
3842 _gtk_text_line_char_to_segment (GtkTextLine *line,
3846 GtkTextLineSegment *seg;
3849 g_return_val_if_fail (line != NULL, NULL);
3851 offset = char_offset;
3852 seg = line->segments;
3854 while (offset >= seg->char_count)
3856 offset -= seg->char_count;
3858 g_assert (seg != NULL); /* means an invalid char index */
3862 *seg_offset = offset;
3868 _gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3872 GtkTextLineSegment *seg;
3875 g_return_val_if_fail (line != NULL, NULL);
3877 offset = byte_offset;
3878 seg = line->segments;
3880 while (offset > 0 && offset >= seg->byte_count)
3882 offset -= seg->byte_count;
3884 g_assert (seg != NULL); /* means an invalid byte index */
3888 *seg_offset = offset;
3894 _gtk_text_line_char_to_any_segment (GtkTextLine *line,
3898 GtkTextLineSegment *seg;
3901 g_return_val_if_fail (line != NULL, NULL);
3903 offset = char_offset;
3904 seg = line->segments;
3906 while (offset > 0 && offset >= seg->char_count)
3908 offset -= seg->char_count;
3910 g_assert (seg != NULL); /* means an invalid byte index */
3914 *seg_offset = offset;
3920 _gtk_text_line_byte_to_char (GtkTextLine *line,
3924 GtkTextLineSegment *seg;
3926 g_return_val_if_fail (line != NULL, 0);
3927 g_return_val_if_fail (byte_offset >= 0, 0);
3930 seg = line->segments;
3931 while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3932 the next segment) */
3934 byte_offset -= seg->byte_count;
3935 char_offset += seg->char_count;
3937 g_assert (seg != NULL); /* our byte_index was bogus if this happens */
3940 g_assert (seg != NULL);
3942 /* Now byte_offset is the offset into the current segment,
3943 and char_offset is the start of the current segment.
3944 Optimize the case where no chars use > 1 byte */
3945 if (seg->byte_count == seg->char_count)
3946 return char_offset + byte_offset;
3949 if (seg->type == >k_text_char_type)
3950 return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3953 g_assert (seg->char_count == 1);
3954 g_assert (byte_offset == 0);
3962 _gtk_text_line_char_to_byte (GtkTextLine *line,
3965 g_warning ("FIXME not implemented");
3970 /* FIXME sync with char_locate (or figure out a clean
3971 way to merge the two functions) */
3973 _gtk_text_line_byte_locate (GtkTextLine *line,
3975 GtkTextLineSegment **segment,
3976 GtkTextLineSegment **any_segment,
3977 gint *seg_byte_offset,
3978 gint *line_byte_offset)
3980 GtkTextLineSegment *seg;
3981 GtkTextLineSegment *after_last_indexable;
3982 GtkTextLineSegment *last_indexable;
3986 g_return_val_if_fail (line != NULL, FALSE);
3987 g_return_val_if_fail (byte_offset >= 0, FALSE);
3990 *any_segment = NULL;
3993 offset = byte_offset;
3995 last_indexable = NULL;
3996 after_last_indexable = line->segments;
3997 seg = line->segments;
3999 /* The loop ends when we're inside a segment;
4000 last_indexable refers to the last segment
4001 we passed entirely. */
4002 while (seg && offset >= seg->byte_count)
4004 if (seg->char_count > 0)
4006 offset -= seg->byte_count;
4007 bytes_in_line += seg->byte_count;
4008 last_indexable = seg;
4009 after_last_indexable = last_indexable->next;
4017 /* We went off the end of the line */
4019 g_warning ("%s: byte index off the end of the line", G_STRLOC);
4026 if (after_last_indexable != NULL)
4027 *any_segment = after_last_indexable;
4029 *any_segment = *segment;
4032 /* Override any_segment if we're in the middle of a segment. */
4034 *any_segment = *segment;
4036 *seg_byte_offset = offset;
4038 g_assert (*segment != NULL);
4039 g_assert (*any_segment != NULL);
4040 g_assert (*seg_byte_offset < (*segment)->byte_count);
4042 *line_byte_offset = bytes_in_line + *seg_byte_offset;
4047 /* FIXME sync with byte_locate (or figure out a clean
4048 way to merge the two functions) */
4050 _gtk_text_line_char_locate (GtkTextLine *line,
4052 GtkTextLineSegment **segment,
4053 GtkTextLineSegment **any_segment,
4054 gint *seg_char_offset,
4055 gint *line_char_offset)
4057 GtkTextLineSegment *seg;
4058 GtkTextLineSegment *after_last_indexable;
4059 GtkTextLineSegment *last_indexable;
4063 g_return_val_if_fail (line != NULL, FALSE);
4064 g_return_val_if_fail (char_offset >= 0, FALSE);
4067 *any_segment = NULL;
4070 offset = char_offset;
4072 last_indexable = NULL;
4073 after_last_indexable = line->segments;
4074 seg = line->segments;
4076 /* The loop ends when we're inside a segment;
4077 last_indexable refers to the last segment
4078 we passed entirely. */
4079 while (seg && offset >= seg->char_count)
4081 if (seg->char_count > 0)
4083 offset -= seg->char_count;
4084 chars_in_line += seg->char_count;
4085 last_indexable = seg;
4086 after_last_indexable = last_indexable->next;
4094 /* end of the line */
4096 g_warning ("%s: char offset off the end of the line", G_STRLOC);
4103 if (after_last_indexable != NULL)
4104 *any_segment = after_last_indexable;
4106 *any_segment = *segment;
4109 /* Override any_segment if we're in the middle of a segment. */
4111 *any_segment = *segment;
4113 *seg_char_offset = offset;
4115 g_assert (*segment != NULL);
4116 g_assert (*any_segment != NULL);
4117 g_assert (*seg_char_offset < (*segment)->char_count);
4119 *line_char_offset = chars_in_line + *seg_char_offset;
4125 _gtk_text_line_byte_to_char_offsets (GtkTextLine *line,
4127 gint *line_char_offset,
4128 gint *seg_char_offset)
4130 GtkTextLineSegment *seg;
4133 g_return_if_fail (line != NULL);
4134 g_return_if_fail (byte_offset >= 0);
4136 *line_char_offset = 0;
4138 offset = byte_offset;
4139 seg = line->segments;
4141 while (offset >= seg->byte_count)
4143 offset -= seg->byte_count;
4144 *line_char_offset += seg->char_count;
4146 g_assert (seg != NULL); /* means an invalid char offset */
4149 g_assert (seg->char_count > 0); /* indexable. */
4151 /* offset is now the number of bytes into the current segment we
4152 * want to go. Count chars into the current segment.
4155 if (seg->type == >k_text_char_type)
4157 *seg_char_offset = g_utf8_strlen (seg->body.chars, offset);
4159 g_assert (*seg_char_offset < seg->char_count);
4161 *line_char_offset += *seg_char_offset;
4165 g_assert (offset == 0);
4166 *seg_char_offset = 0;
4171 _gtk_text_line_char_to_byte_offsets (GtkTextLine *line,
4173 gint *line_byte_offset,
4174 gint *seg_byte_offset)
4176 GtkTextLineSegment *seg;
4179 g_return_if_fail (line != NULL);
4180 g_return_if_fail (char_offset >= 0);
4182 *line_byte_offset = 0;
4184 offset = char_offset;
4185 seg = line->segments;
4187 while (offset >= seg->char_count)
4189 offset -= seg->char_count;
4190 *line_byte_offset += seg->byte_count;
4192 g_assert (seg != NULL); /* means an invalid char offset */
4195 g_assert (seg->char_count > 0); /* indexable. */
4197 /* offset is now the number of chars into the current segment we
4198 want to go. Count bytes into the current segment. */
4200 if (seg->type == >k_text_char_type)
4204 /* if in the last fourth of the segment walk backwards */
4205 if (seg->char_count - offset < seg->char_count / 4)
4206 p = g_utf8_offset_to_pointer (seg->body.chars + seg->byte_count,
4207 offset - seg->char_count);
4209 p = g_utf8_offset_to_pointer (seg->body.chars, offset);
4211 *seg_byte_offset = p - seg->body.chars;
4213 g_assert (*seg_byte_offset < seg->byte_count);
4215 *line_byte_offset += *seg_byte_offset;
4219 g_assert (offset == 0);
4220 *seg_byte_offset = 0;
4225 node_compare (GtkTextBTreeNode *lhs,
4226 GtkTextBTreeNode *rhs)
4228 GtkTextBTreeNode *iter;
4229 GtkTextBTreeNode *node;
4230 GtkTextBTreeNode *common_parent;
4231 GtkTextBTreeNode *parent_of_lower;
4232 GtkTextBTreeNode *parent_of_higher;
4233 gboolean lhs_is_lower;
4234 GtkTextBTreeNode *lower;
4235 GtkTextBTreeNode *higher;
4237 /* This function assumes that lhs and rhs are not underneath each
4244 if (lhs->level < rhs->level)
4246 lhs_is_lower = TRUE;
4252 lhs_is_lower = FALSE;
4257 /* Algorithm: find common parent of lhs/rhs. Save the child nodes
4258 * of the common parent we used to reach the common parent; the
4259 * ordering of these child nodes in the child list is the ordering
4263 /* Get on the same level (may be on same level already) */
4265 while (node->level < higher->level)
4266 node = node->parent;
4268 g_assert (node->level == higher->level);
4270 g_assert (node != higher); /* Happens if lower is underneath higher */
4272 /* Go up until we have two children with a common parent.
4274 parent_of_lower = node;
4275 parent_of_higher = higher;
4277 while (parent_of_lower->parent != parent_of_higher->parent)
4279 parent_of_lower = parent_of_lower->parent;
4280 parent_of_higher = parent_of_higher->parent;
4283 g_assert (parent_of_lower->parent == parent_of_higher->parent);
4285 common_parent = parent_of_lower->parent;
4287 g_assert (common_parent != NULL);
4289 /* See which is first in the list of common_parent's children */
4290 iter = common_parent->children.node;
4291 while (iter != NULL)
4293 if (iter == parent_of_higher)
4295 /* higher is less than lower */
4298 return 1; /* lhs > rhs */
4302 else if (iter == parent_of_lower)
4304 /* lower is less than higher */
4307 return -1; /* lhs < rhs */
4315 g_assert_not_reached ();
4319 /* remember that tag == NULL means "any tag" */
4321 _gtk_text_line_next_could_contain_tag (GtkTextLine *line,
4325 GtkTextBTreeNode *node;
4326 GtkTextTagInfo *info;
4327 gboolean below_tag_root;
4329 g_return_val_if_fail (line != NULL, NULL);
4331 if (gtk_get_debug_flags () & GTK_DEBUG_TEXT)
4332 _gtk_text_btree_check (tree);
4336 /* Right now we can only offer linear-search if the user wants
4337 * to know about any tag toggle at all.
4339 return _gtk_text_line_next_excluding_last (line);
4342 /* Our tag summaries only have node precision, not line
4343 * precision. This means that if any line under a node could contain a
4344 * tag, then any of the others could also contain a tag.
4346 * In the future we could have some mechanism to keep track of how
4347 * many toggles we've found under a node so far, since we have a
4348 * count of toggles under the node. But for now I'm going with KISS.
4351 /* return same-node line, if any. */
4355 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4359 if (info->tag_root == NULL)
4362 if (info->tag_root == line->parent)
4363 return NULL; /* we were at the last line under the tag root */
4365 /* We need to go up out of this node, and on to the next one with
4366 toggles for the target tag. If we're below the tag root, we need to
4367 find the next node below the tag root that has tag summaries. If
4368 we're not below the tag root, we need to see if the tag root is
4369 after us in the tree, and if so, return the first line underneath
4372 node = line->parent;
4373 below_tag_root = FALSE;
4374 while (node != NULL)
4376 if (node == info->tag_root)
4378 below_tag_root = TRUE;
4382 node = node->parent;
4387 node = line->parent;
4388 while (node != info->tag_root)
4390 if (node->next == NULL)
4391 node = node->parent;
4396 if (gtk_text_btree_node_has_tag (node, tag))
4406 ordering = node_compare (line->parent, info->tag_root);
4410 /* Tag root is ahead of us, so search there. */
4411 node = info->tag_root;
4416 /* Tag root is after us, so no more lines that
4417 * could contain the tag.
4422 g_assert_not_reached ();
4427 g_assert (node != NULL);
4429 /* We have to find the first sub-node of this node that contains
4433 while (node->level > 0)
4435 g_assert (node != NULL); /* If this fails, it likely means an
4436 incorrect tag summary led us on a
4437 wild goose chase down this branch of
4439 node = node->children.node;
4440 while (node != NULL)
4442 if (gtk_text_btree_node_has_tag (node, tag))
4448 g_assert (node != NULL);
4449 g_assert (node->level == 0);
4451 return node->children.line;
4455 prev_line_under_node (GtkTextBTreeNode *node,
4460 prev = node->children.line;
4466 while (prev->next != line)
4476 _gtk_text_line_previous_could_contain_tag (GtkTextLine *line,
4480 GtkTextBTreeNode *node;
4481 GtkTextBTreeNode *found_node = NULL;
4482 GtkTextTagInfo *info;
4483 gboolean below_tag_root;
4485 GtkTextBTreeNode *line_ancestor;
4486 GtkTextBTreeNode *line_ancestor_parent;
4488 /* See next_could_contain_tag () for more extensive comments
4489 * on what's going on here.
4492 g_return_val_if_fail (line != NULL, NULL);
4494 if (gtk_get_debug_flags () & GTK_DEBUG_TEXT)
4495 _gtk_text_btree_check (tree);
4499 /* Right now we can only offer linear-search if the user wants
4500 * to know about any tag toggle at all.
4502 return _gtk_text_line_previous (line);
4505 /* Return same-node line, if any. */
4506 prev = prev_line_under_node (line->parent, line);
4510 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4514 if (info->tag_root == NULL)
4517 if (info->tag_root == line->parent)
4518 return NULL; /* we were at the first line under the tag root */
4520 /* Are we below the tag root */
4521 node = line->parent;
4522 below_tag_root = FALSE;
4523 while (node != NULL)
4525 if (node == info->tag_root)
4527 below_tag_root = TRUE;
4531 node = node->parent;
4536 /* Look for a previous node under this tag root that has our
4540 /* this assertion holds because line->parent is not the
4541 * tag root, we are below the tag root, and the tag
4544 g_assert (line->parent->parent != NULL);
4546 line_ancestor = line->parent;
4547 line_ancestor_parent = line->parent->parent;
4549 while (line_ancestor != info->tag_root)
4551 GSList *child_nodes = NULL;
4554 /* Create reverse-order list of nodes before
4557 if (line_ancestor_parent != NULL)
4558 node = line_ancestor_parent->children.node;
4560 node = line_ancestor;
4562 while (node != line_ancestor && node != NULL)
4564 child_nodes = g_slist_prepend (child_nodes, node);
4569 /* Try to find a node with our tag on it in the list */
4573 GtkTextBTreeNode *this_node = tmp->data;
4575 g_assert (this_node != line_ancestor);
4577 if (gtk_text_btree_node_has_tag (this_node, tag))
4579 found_node = this_node;
4580 g_slist_free (child_nodes);
4584 tmp = g_slist_next (tmp);
4587 g_slist_free (child_nodes);
4589 /* Didn't find anything on this level; go up one level. */
4590 line_ancestor = line_ancestor_parent;
4591 line_ancestor_parent = line_ancestor->parent;
4601 ordering = node_compare (line->parent, info->tag_root);
4605 /* Tag root is ahead of us, so no more lines
4612 /* Tag root is after us, so grab last tagged
4613 * line underneath the tag root.
4615 found_node = info->tag_root;
4619 g_assert_not_reached ();
4624 g_assert (found_node != NULL);
4626 /* We have to find the last sub-node of this node that contains
4631 while (node->level > 0)
4633 GSList *child_nodes = NULL;
4635 g_assert (node != NULL); /* If this fails, it likely means an
4636 incorrect tag summary led us on a
4637 wild goose chase down this branch of
4640 node = node->children.node;
4641 while (node != NULL)
4643 child_nodes = g_slist_prepend (child_nodes, node);
4647 node = NULL; /* detect failure to find a child node. */
4650 while (iter != NULL)
4652 if (gtk_text_btree_node_has_tag (iter->data, tag))
4654 /* recurse into this node. */
4659 iter = g_slist_next (iter);
4662 g_slist_free (child_nodes);
4664 g_assert (node != NULL);
4667 g_assert (node != NULL);
4668 g_assert (node->level == 0);
4670 /* this assertion is correct, but slow. */
4671 /* g_assert (node_compare (node, line->parent) < 0); */
4673 /* Return last line in this node. */
4675 prev = node->children.line;
4683 * Non-public function implementations
4687 summary_list_destroy (Summary *summary)
4689 g_slice_free_chain (Summary, summary, next);
4693 get_last_line (GtkTextBTree *tree)
4695 if (tree->last_line_stamp != tree->chars_changed_stamp)
4701 n_lines = _gtk_text_btree_line_count (tree);
4703 g_assert (n_lines >= 1); /* num_lines doesn't return bogus last line. */
4705 line = _gtk_text_btree_get_line (tree, n_lines, &real_line);
4707 tree->last_line_stamp = tree->chars_changed_stamp;
4708 tree->last_line = line;
4711 return tree->last_line;
4719 gtk_text_line_new (void)
4723 line = g_slice_new0 (GtkTextLine);
4724 line->dir_strong = PANGO_DIRECTION_NEUTRAL;
4725 line->dir_propagated_forward = PANGO_DIRECTION_NEUTRAL;
4726 line->dir_propagated_back = PANGO_DIRECTION_NEUTRAL;
4732 gtk_text_line_destroy (GtkTextBTree *tree, GtkTextLine *line)
4734 GtkTextLineData *ld;
4735 GtkTextLineData *next;
4737 g_return_if_fail (line != NULL);
4744 view = gtk_text_btree_get_view (tree, ld->view_id);
4746 g_assert (view != NULL);
4749 gtk_text_layout_free_line_data (view->layout, line, ld);
4754 g_slice_free (GtkTextLine, line);
4758 gtk_text_line_set_parent (GtkTextLine *line,
4759 GtkTextBTreeNode *node)
4761 if (line->parent == node)
4763 line->parent = node;
4764 gtk_text_btree_node_invalidate_upward (node, NULL);
4768 cleanup_line (GtkTextLine *line)
4770 GtkTextLineSegment *seg, **prev_p;
4774 * Make a pass over all of the segments in the line, giving each
4775 * a chance to clean itself up. This could potentially change
4776 * the structure of the line, e.g. by merging two segments
4777 * together or having two segments cancel themselves; if so,
4778 * then repeat the whole process again, since the first structure
4779 * change might make other structure changes possible. Repeat
4780 * until eventually there are no changes.
4787 prev_p = &line->segments;
4788 for (seg = *prev_p; seg != NULL; seg = *prev_p)
4790 if (seg->type->cleanupFunc != NULL)
4792 *prev_p = (*seg->type->cleanupFunc)(seg, line);
4800 prev_p = &(*prev_p)->next;
4810 node_data_new (gpointer view_id)
4814 nd = g_slice_new (NodeData);
4816 nd->view_id = view_id;
4826 node_data_destroy (NodeData *nd)
4828 g_slice_free (NodeData, nd);
4832 node_data_list_destroy (NodeData *nd)
4834 g_slice_free_chain (NodeData, nd, next);
4838 node_data_find (NodeData *nd,
4843 if (nd->view_id == view_id)
4851 summary_destroy (Summary *summary)
4853 /* Fill with error-triggering garbage */
4854 summary->info = (void*)0x1;
4855 summary->toggle_count = 567;
4856 summary->next = (void*)0x1;
4857 g_slice_free (Summary, summary);
4860 static GtkTextBTreeNode*
4861 gtk_text_btree_node_new (void)
4863 GtkTextBTreeNode *node;
4865 node = g_slice_new (GtkTextBTreeNode);
4867 node->node_data = NULL;
4873 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
4874 GtkTextTagInfo *info,
4879 summary = node->summary;
4880 while (summary != NULL)
4882 if (summary->info == info)
4884 summary->toggle_count += adjust;
4888 summary = summary->next;
4891 if (summary == NULL)
4893 /* didn't find a summary for our tag. */
4894 g_return_if_fail (adjust > 0);
4895 summary = g_slice_new (Summary);
4896 summary->info = info;
4897 summary->toggle_count = adjust;
4898 summary->next = node->summary;
4899 node->summary = summary;
4903 /* Note that the tag root and above do not have summaries
4904 for the tag; only nodes below the tag root have
4907 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4911 summary = node->summary;
4912 while (summary != NULL)
4915 summary->info->tag == tag)
4918 summary = summary->next;
4924 /* Add node and all children to the damage region. */
4927 gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node)
4931 nd = node->node_data;
4938 if (node->level == 0)
4942 line = node->children.line;
4943 while (line != NULL)
4945 GtkTextLineData *ld;
4959 GtkTextBTreeNode *child;
4961 child = node->children.node;
4963 while (child != NULL)
4965 gtk_text_btree_node_invalidate_downward (child);
4967 child = child->next;
4974 gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node, gpointer view_id)
4976 GtkTextBTreeNode *iter;
4979 while (iter != NULL)
4985 nd = node_data_find (iter->node_data, view_id);
4987 if (nd == NULL || !nd->valid)
4988 break; /* Once a node is invalid, we know its parents are as well. */
4994 gboolean should_continue = FALSE;
4996 nd = iter->node_data;
5001 should_continue = TRUE;
5008 if (!should_continue)
5009 break; /* This node was totally invalidated, so are its
5013 iter = iter->parent;
5019 * _gtk_text_btree_is_valid:
5020 * @tree: a #GtkTextBTree
5021 * @view_id: ID for the view
5023 * Check to see if the entire #GtkTextBTree is valid or not for
5026 * Return value: %TRUE if the entire #GtkTextBTree is valid
5029 _gtk_text_btree_is_valid (GtkTextBTree *tree,
5033 g_return_val_if_fail (tree != NULL, FALSE);
5035 nd = node_data_find (tree->root_node->node_data, view_id);
5036 return (nd && nd->valid);
5039 typedef struct _ValidateState ValidateState;
5041 struct _ValidateState
5043 gint remaining_pixels;
5044 gboolean in_validation;
5051 gtk_text_btree_node_validate (BTreeView *view,
5052 GtkTextBTreeNode *node,
5054 ValidateState *state)
5056 gint node_valid = TRUE;
5057 gint node_width = 0;
5058 gint node_height = 0;
5060 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5061 g_return_if_fail (!nd->valid);
5063 if (node->level == 0)
5065 GtkTextLine *line = node->children.line;
5066 GtkTextLineData *ld;
5068 /* Iterate over leading valid lines */
5069 while (line != NULL)
5071 ld = _gtk_text_line_get_data (line, view_id);
5073 if (!ld || !ld->valid)
5075 else if (state->in_validation)
5077 state->in_validation = FALSE;
5082 state->y += ld->height;
5083 node_width = MAX (ld->width, node_width);
5084 node_height += ld->height;
5090 state->in_validation = TRUE;
5092 /* Iterate over invalid lines */
5093 while (line != NULL)
5095 ld = _gtk_text_line_get_data (line, view_id);
5097 if (ld && ld->valid)
5102 state->old_height += ld->height;
5103 ld = gtk_text_layout_wrap (view->layout, line, ld);
5104 state->new_height += ld->height;
5106 node_width = MAX (ld->width, node_width);
5107 node_height += ld->height;
5109 state->remaining_pixels -= ld->height;
5110 if (state->remaining_pixels <= 0)
5120 /* Iterate over the remaining lines */
5121 while (line != NULL)
5123 ld = _gtk_text_line_get_data (line, view_id);
5124 state->in_validation = FALSE;
5126 if (!ld || !ld->valid)
5131 node_width = MAX (ld->width, node_width);
5132 node_height += ld->height;
5140 GtkTextBTreeNode *child;
5143 child = node->children.node;
5145 /* Iterate over leading valid nodes */
5148 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5150 if (!child_nd->valid)
5152 else if (state->in_validation)
5154 state->in_validation = FALSE;
5159 state->y += child_nd->height;
5160 node_width = MAX (node_width, child_nd->width);
5161 node_height += child_nd->height;
5164 child = child->next;
5167 /* Iterate over invalid nodes */
5170 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5172 if (child_nd->valid)
5176 gtk_text_btree_node_validate (view, child, view_id, state);
5178 if (!child_nd->valid)
5180 node_width = MAX (node_width, child_nd->width);
5181 node_height += child_nd->height;
5183 if (!state->in_validation || state->remaining_pixels <= 0)
5185 child = child->next;
5190 child = child->next;
5193 /* Iterate over the remaining lines */
5196 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5197 state->in_validation = FALSE;
5199 if (!child_nd->valid)
5202 node_width = MAX (child_nd->width, node_width);
5203 node_height += child_nd->height;
5205 child = child->next;
5209 nd->width = node_width;
5210 nd->height = node_height;
5211 nd->valid = node_valid;
5215 * _gtk_text_btree_validate:
5216 * @tree: a #GtkTextBTree
5218 * @max_pixels: the maximum number of pixels to validate. (No more
5219 * than one paragraph beyond this limit will be validated)
5220 * @y: location to store starting y coordinate of validated region
5221 * @old_height: location to store old height of validated region
5222 * @new_height: location to store new height of validated region
5224 * Validate a single contiguous invalid region of a #GtkTextBTree for
5227 * Return value: %TRUE if a region has been validated, %FALSE if the
5228 * entire tree was already valid.
5231 _gtk_text_btree_validate (GtkTextBTree *tree,
5240 g_return_val_if_fail (tree != NULL, FALSE);
5242 view = gtk_text_btree_get_view (tree, view_id);
5243 g_return_val_if_fail (view != NULL, FALSE);
5245 if (!_gtk_text_btree_is_valid (tree, view_id))
5247 ValidateState state;
5249 state.remaining_pixels = max_pixels;
5250 state.in_validation = FALSE;
5252 state.old_height = 0;
5253 state.new_height = 0;
5255 gtk_text_btree_node_validate (view,
5262 *old_height = state.old_height;
5264 *new_height = state.new_height;
5266 if (gtk_get_debug_flags () & GTK_DEBUG_TEXT)
5267 _gtk_text_btree_check (tree);
5276 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
5280 gboolean *valid_out)
5284 gboolean valid = TRUE;
5286 if (node->level == 0)
5288 GtkTextLine *line = node->children.line;
5290 while (line != NULL)
5292 GtkTextLineData *ld = _gtk_text_line_get_data (line, view_id);
5294 if (!ld || !ld->valid)
5299 width = MAX (ld->width, width);
5300 height += ld->height;
5308 GtkTextBTreeNode *child = node->children.node;
5312 NodeData *child_nd = node_data_find (child->node_data, view_id);
5314 if (!child_nd || !child_nd->valid)
5319 width = MAX (child_nd->width, width);
5320 height += child_nd->height;
5323 child = child->next;
5328 *height_out = height;
5333 /* Recompute the validity and size of the view data for a given
5334 * view at this node from the immediate children of the node
5337 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
5340 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5345 gtk_text_btree_node_compute_view_aggregates (node, view_id,
5346 &width, &height, &valid);
5348 nd->height = height;
5355 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
5360 gtk_text_btree_node_check_valid (node, view_id);
5361 node = node->parent;
5366 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
5369 if (node->level == 0)
5371 return gtk_text_btree_node_check_valid (node, view_id);
5375 GtkTextBTreeNode *child = node->children.node;
5377 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5385 NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
5387 if (!child_nd->valid)
5389 nd->width = MAX (child_nd->width, nd->width);
5390 nd->height += child_nd->height;
5392 child = child->next;
5401 * _gtk_text_btree_validate_line:
5402 * @tree: a #GtkTextBTree
5403 * @line: line to validate
5404 * @view_id: view ID for the view to validate
5406 * Revalidate a single line of the btree for the given view, propagate
5407 * results up through the entire tree.
5410 _gtk_text_btree_validate_line (GtkTextBTree *tree,
5414 GtkTextLineData *ld;
5417 g_return_if_fail (tree != NULL);
5418 g_return_if_fail (line != NULL);
5420 view = gtk_text_btree_get_view (tree, view_id);
5421 g_return_if_fail (view != NULL);
5423 ld = _gtk_text_line_get_data (line, view_id);
5424 if (!ld || !ld->valid)
5426 ld = gtk_text_layout_wrap (view->layout, line, ld);
5428 gtk_text_btree_node_check_valid_upward (line->parent, view_id);
5433 gtk_text_btree_node_remove_view (BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
5435 if (node->level == 0)
5439 line = node->children.line;
5440 while (line != NULL)
5442 GtkTextLineData *ld;
5444 ld = _gtk_text_line_remove_data (line, view_id);
5447 gtk_text_layout_free_line_data (view->layout, line, ld);
5454 GtkTextBTreeNode *child;
5456 child = node->children.node;
5458 while (child != NULL)
5461 gtk_text_btree_node_remove_view (view, child, view_id);
5463 child = child->next;
5467 gtk_text_btree_node_remove_data (node, view_id);
5471 gtk_text_btree_node_destroy (GtkTextBTree *tree, GtkTextBTreeNode *node)
5473 if (node->level == 0)
5476 GtkTextLineSegment *seg;
5478 while (node->children.line != NULL)
5480 line = node->children.line;
5481 node->children.line = line->next;
5482 while (line->segments != NULL)
5484 seg = line->segments;
5485 line->segments = seg->next;
5487 (*seg->type->deleteFunc) (seg, line, TRUE);
5489 gtk_text_line_destroy (tree, line);
5494 GtkTextBTreeNode *childPtr;
5496 while (node->children.node != NULL)
5498 childPtr = node->children.node;
5499 node->children.node = childPtr->next;
5500 gtk_text_btree_node_destroy (tree, childPtr);
5504 gtk_text_btree_node_free_empty (tree, node);
5508 gtk_text_btree_node_free_empty (GtkTextBTree *tree,
5509 GtkTextBTreeNode *node)
5511 g_return_if_fail ((node->level > 0 && node->children.node == NULL) ||
5512 (node->level == 0 && node->children.line == NULL));
5514 summary_list_destroy (node->summary);
5515 node_data_list_destroy (node->node_data);
5516 g_slice_free (GtkTextBTreeNode, node);
5520 gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node, gpointer view_id)
5524 nd = node->node_data;
5527 if (nd->view_id == view_id)
5535 nd = node_data_new (view_id);
5537 if (node->node_data)
5538 nd->next = node->node_data;
5540 node->node_data = nd;
5547 gtk_text_btree_node_remove_data (GtkTextBTreeNode *node, gpointer view_id)
5553 nd = node->node_data;
5556 if (nd->view_id == view_id)
5567 prev->next = nd->next;
5569 if (node->node_data == nd)
5570 node->node_data = nd->next;
5574 node_data_destroy (nd);
5578 gtk_text_btree_node_get_size (GtkTextBTreeNode *node, gpointer view_id,
5579 gint *width, gint *height)
5583 g_return_if_fail (width != NULL);
5584 g_return_if_fail (height != NULL);
5586 nd = gtk_text_btree_node_ensure_data (node, view_id);
5591 *height = nd->height;
5594 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5595 * here isn't quite right, since for a lot of operations we want to
5596 * know which children of the common parent correspond to the two nodes
5597 * (e.g., when computing the order of two iters)
5599 static GtkTextBTreeNode *
5600 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5601 GtkTextBTreeNode *node2)
5603 while (node1->level < node2->level)
5604 node1 = node1->parent;
5605 while (node2->level < node1->level)
5606 node2 = node2->parent;
5607 while (node1 != node2)
5609 node1 = node1->parent;
5610 node2 = node2->parent;
5621 gtk_text_btree_get_view (GtkTextBTree *tree, gpointer view_id)
5626 while (view != NULL)
5628 if (view->view_id == view_id)
5637 get_tree_bounds (GtkTextBTree *tree,
5641 _gtk_text_btree_get_iter_at_line_char (tree, start, 0, 0);
5642 _gtk_text_btree_get_end_iter (tree, end);
5646 tag_changed_cb (GtkTextTagTable *table,
5648 gboolean size_changed,
5653 /* We need to queue a relayout on all regions that are tagged with
5660 if (_gtk_text_btree_get_iter_at_first_toggle (tree, &start, tag))
5662 /* Must be a last toggle if there was a first one. */
5663 _gtk_text_btree_get_iter_at_last_toggle (tree, &end, tag);
5664 DV (g_print ("invalidating due to tag change (%s)\n", G_STRLOC));
5665 _gtk_text_btree_invalidate_region (tree, &start, &end, FALSE);
5671 /* We only need to queue a redraw, not a relayout */
5676 while (view != NULL)
5680 _gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5681 gtk_text_layout_changed (view->layout, 0, height, height);
5689 _gtk_text_btree_notify_will_remove_tag (GtkTextBTree *tree,
5692 /* Remove the tag from the tree */
5697 get_tree_bounds (tree, &start, &end);
5699 _gtk_text_btree_tag (&start, &end, tag, FALSE);
5700 gtk_text_btree_remove_tag_info (tree, tag);
5704 /* Rebalance the out-of-whack node "node" */
5706 gtk_text_btree_rebalance (GtkTextBTree *tree,
5707 GtkTextBTreeNode *node)
5710 * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5711 * up through the tree one GtkTextBTreeNode at a time until the root
5712 * GtkTextBTreeNode has been processed.
5715 while (node != NULL)
5717 GtkTextBTreeNode *new_node, *child;
5722 * Check to see if the GtkTextBTreeNode has too many children. If it does,
5723 * then split off all but the first MIN_CHILDREN into a separate
5724 * GtkTextBTreeNode following the original one. Then repeat until the
5725 * GtkTextBTreeNode has a decent size.
5728 if (node->num_children > MAX_CHILDREN)
5733 * If the GtkTextBTreeNode being split is the root
5734 * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5738 if (node->parent == NULL)
5740 new_node = gtk_text_btree_node_new ();
5741 new_node->parent = NULL;
5742 new_node->next = NULL;
5743 new_node->summary = NULL;
5744 new_node->level = node->level + 1;
5745 new_node->children.node = node;
5746 recompute_node_counts (tree, new_node);
5747 tree->root_node = new_node;
5749 new_node = gtk_text_btree_node_new ();
5750 new_node->parent = node->parent;
5751 new_node->next = node->next;
5752 node->next = new_node;
5753 new_node->summary = NULL;
5754 new_node->level = node->level;
5755 new_node->num_children = node->num_children - MIN_CHILDREN;
5756 if (node->level == 0)
5758 for (i = MIN_CHILDREN-1,
5759 line = node->children.line;
5760 i > 0; i--, line = line->next)
5762 /* Empty loop body. */
5764 new_node->children.line = line->next;
5769 for (i = MIN_CHILDREN-1,
5770 child = node->children.node;
5771 i > 0; i--, child = child->next)
5773 /* Empty loop body. */
5775 new_node->children.node = child->next;
5778 recompute_node_counts (tree, node);
5779 node->parent->num_children++;
5781 if (node->num_children <= MAX_CHILDREN)
5783 recompute_node_counts (tree, node);
5789 while (node->num_children < MIN_CHILDREN)
5791 GtkTextBTreeNode *other;
5792 GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5793 GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5794 int total_children, first_children, i;
5797 * Too few children for this GtkTextBTreeNode. If this is the root then,
5798 * it's OK for it to have less than MIN_CHILDREN children
5799 * as long as it's got at least two. If it has only one
5800 * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5801 * the tree and use its child as the new root.
5804 if (node->parent == NULL)
5806 if ((node->num_children == 1) && (node->level > 0))
5808 tree->root_node = node->children.node;
5809 tree->root_node->parent = NULL;
5811 node->children.node = NULL;
5812 gtk_text_btree_node_free_empty (tree, node);
5818 * Not the root. Make sure that there are siblings to
5822 if (node->parent->num_children < 2)
5824 gtk_text_btree_rebalance (tree, node->parent);
5829 * Find a sibling neighbor to borrow from, and arrange for
5830 * node to be the earlier of the pair.
5833 if (node->next == NULL)
5835 for (other = node->parent->children.node;
5836 other->next != node;
5837 other = other->next)
5839 /* Empty loop body. */
5846 * We're going to either merge the two siblings together
5847 * into one GtkTextBTreeNode or redivide the children among them to
5848 * balance their loads. As preparation, join their two
5849 * child lists into a single list and remember the half-way
5850 * point in the list.
5853 total_children = node->num_children + other->num_children;
5854 first_children = total_children/2;
5855 if (node->children.node == NULL)
5857 node->children = other->children;
5858 other->children.node = NULL;
5859 other->children.line = NULL;
5861 if (node->level == 0)
5865 for (line = node->children.line, i = 1;
5867 line = line->next, i++)
5869 if (i == first_children)
5874 line->next = other->children.line;
5875 while (i <= first_children)
5884 GtkTextBTreeNode *child;
5886 for (child = node->children.node, i = 1;
5887 child->next != NULL;
5888 child = child->next, i++)
5890 if (i <= first_children)
5892 if (i == first_children)
5894 halfwaynode = child;
5898 child->next = other->children.node;
5899 while (i <= first_children)
5901 halfwaynode = child;
5902 child = child->next;
5908 * If the two siblings can simply be merged together, do it.
5911 if (total_children <= MAX_CHILDREN)
5913 recompute_node_counts (tree, node);
5914 node->next = other->next;
5915 node->parent->num_children--;
5917 other->children.node = NULL;
5918 other->children.line = NULL;
5919 gtk_text_btree_node_free_empty (tree, other);
5924 * The siblings can't be merged, so just divide their
5925 * children evenly between them.
5928 if (node->level == 0)
5930 other->children.line = halfwayline->next;
5931 halfwayline->next = NULL;
5935 other->children.node = halfwaynode->next;
5936 halfwaynode->next = NULL;
5939 recompute_node_counts (tree, node);
5940 recompute_node_counts (tree, other);
5943 node = node->parent;
5948 post_insert_fixup (GtkTextBTree *tree,
5950 gint line_count_delta,
5951 gint char_count_delta)
5954 GtkTextBTreeNode *node;
5957 * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5958 * point, then rebalance the tree if necessary.
5961 for (node = line->parent ; node != NULL;
5962 node = node->parent)
5964 node->num_lines += line_count_delta;
5965 node->num_chars += char_count_delta;
5967 node = line->parent;
5968 node->num_children += line_count_delta;
5970 if (node->num_children > MAX_CHILDREN)
5972 gtk_text_btree_rebalance (tree, node);
5975 if (gtk_get_debug_flags () & GTK_DEBUG_TEXT)
5976 _gtk_text_btree_check (tree);
5979 static GtkTextTagInfo*
5980 gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
5983 GtkTextTagInfo *info;
5987 list = tree->tag_infos;
5988 while (list != NULL)
5991 if (info->tag == tag)
5994 list = g_slist_next (list);
6000 static GtkTextTagInfo*
6001 gtk_text_btree_get_tag_info (GtkTextBTree *tree,
6004 GtkTextTagInfo *info;
6006 info = gtk_text_btree_get_existing_tag_info (tree, tag);
6010 /* didn't find it, create. */
6012 info = g_slice_new (GtkTextTagInfo);
6016 info->tag_root = NULL;
6017 info->toggle_count = 0;
6019 tree->tag_infos = g_slist_prepend (tree->tag_infos, info);
6022 g_print ("Created tag info %p for tag %s(%p)\n",
6023 info, info->tag->name ? info->tag->name : "anon",
6032 gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
6035 GtkTextTagInfo *info;
6040 list = tree->tag_infos;
6041 while (list != NULL)
6044 if (info->tag == tag)
6047 g_print ("Removing tag info %p for tag %s(%p)\n",
6048 info, info->tag->name ? info->tag->name : "anon",
6054 prev->next = list->next;
6058 tree->tag_infos = list->next;
6061 g_slist_free (list);
6063 g_object_unref (info->tag);
6065 g_slice_free (GtkTextTagInfo, info);
6070 list = g_slist_next (list);
6075 recompute_level_zero_counts (GtkTextBTreeNode *node)
6078 GtkTextLineSegment *seg;
6080 g_assert (node->level == 0);
6082 line = node->children.line;
6083 while (line != NULL)
6085 node->num_children++;
6088 if (line->parent != node)
6089 gtk_text_line_set_parent (line, node);
6091 seg = line->segments;
6095 node->num_chars += seg->char_count;
6097 if (((seg->type != >k_text_toggle_on_type)
6098 && (seg->type != >k_text_toggle_off_type))
6099 || !(seg->body.toggle.inNodeCounts))
6105 GtkTextTagInfo *info;
6107 info = seg->body.toggle.info;
6109 gtk_text_btree_node_adjust_toggle_count (node, info, 1);
6120 recompute_level_nonzero_counts (GtkTextBTreeNode *node)
6123 GtkTextBTreeNode *child;
6125 g_assert (node->level > 0);
6127 child = node->children.node;
6128 while (child != NULL)
6130 node->num_children += 1;
6131 node->num_lines += child->num_lines;
6132 node->num_chars += child->num_chars;
6134 if (child->parent != node)
6136 child->parent = node;
6137 gtk_text_btree_node_invalidate_upward (node, NULL);
6140 summary = child->summary;
6141 while (summary != NULL)
6143 gtk_text_btree_node_adjust_toggle_count (node,
6145 summary->toggle_count);
6147 summary = summary->next;
6150 child = child->next;
6155 *----------------------------------------------------------------------
6157 * recompute_node_counts --
6159 * This procedure is called to recompute all the counts in a GtkTextBTreeNode
6160 * (tags, child information, etc.) by scanning the information in
6161 * its descendants. This procedure is called during rebalancing
6162 * when a GtkTextBTreeNode's child structure has changed.
6168 * The tag counts for node are modified to reflect its current
6169 * child structure, as are its num_children, num_lines, num_chars fields.
6170 * Also, all of the childrens' parent fields are made to point
6173 *----------------------------------------------------------------------
6177 recompute_node_counts (GtkTextBTree *tree, GtkTextBTreeNode *node)
6180 Summary *summary, *summary2;
6183 * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
6184 * the existing Summary records (most of them will probably be reused).
6187 summary = node->summary;
6188 while (summary != NULL)
6190 summary->toggle_count = 0;
6191 summary = summary->next;
6194 node->num_children = 0;
6195 node->num_lines = 0;
6196 node->num_chars = 0;
6199 * Scan through the children, adding the childrens' tag counts into
6200 * the GtkTextBTreeNode's tag counts and adding new Summary structures if
6204 if (node->level == 0)
6205 recompute_level_zero_counts (node);
6207 recompute_level_nonzero_counts (node);
6212 gtk_text_btree_node_check_valid (node, view->view_id);
6217 * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
6218 * records that still have a zero count, or that have all the toggles.
6219 * The GtkTextBTreeNode with the children that account for all the tags toggles
6220 * have no summary information, and they become the tag_root for the tag.
6224 for (summary = node->summary; summary != NULL; )
6226 if (summary->toggle_count > 0 &&
6227 summary->toggle_count < summary->info->toggle_count)
6229 if (node->level == summary->info->tag_root->level)
6232 * The tag's root GtkTextBTreeNode split and some toggles left.
6233 * The tag root must move up a level.
6235 summary->info->tag_root = node->parent;
6238 summary = summary->next;
6241 if (summary->toggle_count == summary->info->toggle_count)
6244 * A GtkTextBTreeNode merge has collected all the toggles under
6245 * one GtkTextBTreeNode. Push the root down to this level.
6247 summary->info->tag_root = node;
6249 if (summary2 != NULL)
6251 summary2->next = summary->next;
6252 summary_destroy (summary);
6253 summary = summary2->next;
6257 node->summary = summary->next;
6258 summary_destroy (summary);
6259 summary = node->summary;
6265 _gtk_change_node_toggle_count (GtkTextBTreeNode *node,
6266 GtkTextTagInfo *info,
6267 gint delta) /* may be negative */
6269 Summary *summary, *prevPtr;
6270 GtkTextBTreeNode *node2Ptr;
6271 int rootLevel; /* Level of original tag root */
6273 info->toggle_count += delta;
6275 if (info->tag_root == (GtkTextBTreeNode *) NULL)
6277 info->tag_root = node;
6282 * Note the level of the existing root for the tag so we can detect
6283 * if it needs to be moved because of the toggle count change.
6286 rootLevel = info->tag_root->level;
6289 * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
6290 * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
6294 for ( ; node != info->tag_root; node = node->parent)
6297 * See if there's already an entry for this tag for this GtkTextBTreeNode. If so,
6298 * perhaps all we have to do is adjust its count.
6301 for (prevPtr = NULL, summary = node->summary;
6303 prevPtr = summary, summary = summary->next)
6305 if (summary->info == info)
6310 if (summary != NULL)
6312 summary->toggle_count += delta;
6313 if (summary->toggle_count > 0 &&
6314 summary->toggle_count < info->toggle_count)
6318 if (summary->toggle_count != 0)
6321 * Should never find a GtkTextBTreeNode with max toggle count at this
6322 * point (there shouldn't have been a summary entry in the
6326 g_error ("%s: bad toggle count (%d) max (%d)",
6327 G_STRLOC, summary->toggle_count, info->toggle_count);
6331 * Zero toggle count; must remove this tag from the list.
6334 if (prevPtr == NULL)
6336 node->summary = summary->next;
6340 prevPtr->next = summary->next;
6342 summary_destroy (summary);
6347 * This tag isn't currently in the summary information list.
6350 if (rootLevel == node->level)
6354 * The old tag root is at the same level in the tree as this
6355 * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode. Move the tag root up
6356 * a level, in the hopes that it will now cover this GtkTextBTreeNode
6357 * as well as the old root (if not, we'll move it up again
6358 * the next time through the loop). To push it up one level
6359 * we copy the original toggle count into the summary
6360 * information at the old root and change the root to its
6361 * parent GtkTextBTreeNode.
6364 GtkTextBTreeNode *rootnode = info->tag_root;
6365 summary = g_slice_new (Summary);
6366 summary->info = info;
6367 summary->toggle_count = info->toggle_count - delta;
6368 summary->next = rootnode->summary;
6369 rootnode->summary = summary;
6370 rootnode = rootnode->parent;
6371 rootLevel = rootnode->level;
6372 info->tag_root = rootnode;
6374 summary = g_slice_new (Summary);
6375 summary->info = info;
6376 summary->toggle_count = delta;
6377 summary->next = node->summary;
6378 node->summary = summary;
6383 * If we've decremented the toggle count, then it may be necessary
6384 * to push the tag root down one or more levels.
6391 if (info->toggle_count == 0)
6393 info->tag_root = (GtkTextBTreeNode *) NULL;
6396 node = info->tag_root;
6397 while (node->level > 0)
6400 * See if a single child GtkTextBTreeNode accounts for all of the tag's
6401 * toggles. If so, push the root down one level.
6404 for (node2Ptr = node->children.node;
6405 node2Ptr != (GtkTextBTreeNode *)NULL ;
6406 node2Ptr = node2Ptr->next)
6408 for (prevPtr = NULL, summary = node2Ptr->summary;
6410 prevPtr = summary, summary = summary->next)
6412 if (summary->info == info)
6417 if (summary == NULL)
6421 if (summary->toggle_count != info->toggle_count)
6424 * No GtkTextBTreeNode has all toggles, so the root is still valid.
6431 * This GtkTextBTreeNode has all the toggles, so push down the root.
6434 if (prevPtr == NULL)
6436 node2Ptr->summary = summary->next;
6440 prevPtr->next = summary->next;
6442 summary_destroy (summary);
6443 info->tag_root = node2Ptr;
6446 node = info->tag_root;
6451 *----------------------------------------------------------------------
6455 * This is a utility procedure used by _gtk_text_btree_get_tags. It
6456 * increments the count for a particular tag, adding a new
6457 * entry for that tag if there wasn't one previously.
6463 * The information at *tagInfoPtr may be modified, and the arrays
6464 * may be reallocated to make them larger.
6466 *----------------------------------------------------------------------
6470 inc_count (GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
6475 for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
6476 count > 0; tag_p++, count--)
6480 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
6486 * There isn't currently an entry for this tag, so we have to
6487 * make a new one. If the arrays are full, then enlarge the
6491 if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
6493 GtkTextTag **newTags;
6494 int *newCounts, newSize;
6496 newSize = 2*tagInfoPtr->arraySize;
6497 newTags = (GtkTextTag **) g_malloc ((unsigned)
6498 (newSize*sizeof (GtkTextTag *)));
6499 memcpy ((void *) newTags, (void *) tagInfoPtr->tags,
6500 tagInfoPtr->arraySize *sizeof (GtkTextTag *));
6501 g_free ((char *) tagInfoPtr->tags);
6502 tagInfoPtr->tags = newTags;
6503 newCounts = (int *) g_malloc ((unsigned) (newSize*sizeof (int)));
6504 memcpy ((void *) newCounts, (void *) tagInfoPtr->counts,
6505 tagInfoPtr->arraySize *sizeof (int));
6506 g_free ((char *) tagInfoPtr->counts);
6507 tagInfoPtr->counts = newCounts;
6508 tagInfoPtr->arraySize = newSize;
6511 tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
6512 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
6513 tagInfoPtr->numTags++;
6517 gtk_text_btree_link_segment (GtkTextLineSegment *seg,
6518 const GtkTextIter *iter)
6520 GtkTextLineSegment *prev;
6524 line = _gtk_text_iter_get_text_line (iter);
6525 tree = _gtk_text_iter_get_btree (iter);
6527 prev = gtk_text_line_segment_split (iter);
6530 seg->next = line->segments;
6531 line->segments = seg;
6535 seg->next = prev->next;
6538 cleanup_line (line);
6539 segments_changed (tree);
6541 if (gtk_get_debug_flags () & GTK_DEBUG_TEXT)
6542 _gtk_text_btree_check (tree);
6546 gtk_text_btree_unlink_segment (GtkTextBTree *tree,
6547 GtkTextLineSegment *seg,
6550 GtkTextLineSegment *prev;
6552 if (line->segments == seg)
6554 line->segments = seg->next;
6558 for (prev = line->segments; prev->next != seg;
6561 /* Empty loop body. */
6563 prev->next = seg->next;
6565 cleanup_line (line);
6566 segments_changed (tree);
6570 * This is here because it requires BTree internals, it logically
6571 * belongs in gtktextsegment.c
6576 *--------------------------------------------------------------
6578 * _gtk_toggle_segment_check_func --
6580 * This procedure is invoked to perform consistency checks
6581 * on toggle segments.
6587 * If a consistency problem is found the procedure g_errors.
6589 *--------------------------------------------------------------
6593 _gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6599 if (segPtr->byte_count != 0)
6601 g_error ("toggle_segment_check_func: segment had non-zero size");
6603 if (!segPtr->body.toggle.inNodeCounts)
6605 g_error ("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6607 needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6608 for (summary = line->parent->summary; ;
6609 summary = summary->next)
6611 if (summary == NULL)
6615 g_error ("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6622 if (summary->info == segPtr->body.toggle.info)
6626 g_error ("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6638 gtk_text_btree_node_view_check_consistency (GtkTextBTree *tree,
6639 GtkTextBTreeNode *node,
6649 while (view != NULL)
6651 if (view->view_id == nd->view_id)
6658 g_error ("Node has data for a view %p no longer attached to the tree",
6661 gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6662 &width, &height, &valid);
6664 /* valid aggregate not checked the same as width/height, because on
6665 * btree rebalance we can have invalid nodes where all lines below
6666 * them are actually valid, due to moving lines around between
6669 * The guarantee is that if there are invalid lines the node is
6670 * invalid - we don't guarantee that if the node is invalid there
6671 * are invalid lines.
6674 if (nd->width != width ||
6675 nd->height != height ||
6676 (nd->valid && !valid))
6678 g_error ("Node aggregates for view %p are invalid:\n"
6679 "Are (%d,%d,%s), should be (%d,%d,%s)",
6681 nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6682 width, height, valid ? "TRUE" : "FALSE");
6687 gtk_text_btree_node_check_consistency (GtkTextBTree *tree,
6688 GtkTextBTreeNode *node)
6690 GtkTextBTreeNode *childnode;
6691 Summary *summary, *summary2;
6693 GtkTextLineSegment *segPtr;
6694 int num_children, num_lines, num_chars, toggle_count, min_children;
6695 GtkTextLineData *ld;
6698 if (node->parent != NULL)
6700 min_children = MIN_CHILDREN;
6702 else if (node->level > 0)
6709 if ((node->num_children < min_children)
6710 || (node->num_children > MAX_CHILDREN))
6712 g_error ("gtk_text_btree_node_check_consistency: bad child count (%d)",
6713 node->num_children);
6716 nd = node->node_data;
6719 gtk_text_btree_node_view_check_consistency (tree, node, nd);
6726 if (node->level == 0)
6728 for (line = node->children.line; line != NULL;
6731 if (line->parent != node)
6733 g_error ("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6735 if (line->segments == NULL)
6737 g_error ("gtk_text_btree_node_check_consistency: line has no segments");
6743 /* Just ensuring we don't segv while doing this loop */
6748 for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6750 if (segPtr->type->checkFunc != NULL)
6752 (*segPtr->type->checkFunc)(segPtr, line);
6754 if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6755 && (segPtr->next != NULL)
6756 && (segPtr->next->byte_count == 0)
6757 && (segPtr->next->type->leftGravity))
6759 g_error ("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6761 if ((segPtr->next == NULL)
6762 && (segPtr->type != >k_text_char_type))
6764 g_error ("gtk_text_btree_node_check_consistency: line ended with wrong type");
6767 num_chars += segPtr->char_count;
6776 for (childnode = node->children.node; childnode != NULL;
6777 childnode = childnode->next)
6779 if (childnode->parent != node)
6781 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6783 if (childnode->level != (node->level-1))
6785 g_error ("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6786 node->level, childnode->level);
6788 gtk_text_btree_node_check_consistency (tree, childnode);
6789 for (summary = childnode->summary; summary != NULL;
6790 summary = summary->next)
6792 for (summary2 = node->summary; ;
6793 summary2 = summary2->next)
6795 if (summary2 == NULL)
6797 if (summary->info->tag_root == node)
6801 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6802 summary->info->tag->priv->name,
6803 "present in parent summaries");
6805 if (summary->info == summary2->info)
6812 num_lines += childnode->num_lines;
6813 num_chars += childnode->num_chars;
6816 if (num_children != node->num_children)
6818 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6819 num_children, node->num_children);
6821 if (num_lines != node->num_lines)
6823 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6824 num_lines, node->num_lines);
6826 if (num_chars != node->num_chars)
6828 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6829 num_chars, node->num_chars);
6832 for (summary = node->summary; summary != NULL;
6833 summary = summary->next)
6835 if (summary->info->toggle_count == summary->toggle_count)
6837 g_error ("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6838 summary->info->tag->priv->name);
6841 if (node->level == 0)
6843 for (line = node->children.line; line != NULL;
6846 for (segPtr = line->segments; segPtr != NULL;
6847 segPtr = segPtr->next)
6849 if ((segPtr->type != >k_text_toggle_on_type)
6850 && (segPtr->type != >k_text_toggle_off_type))
6854 if (segPtr->body.toggle.info == summary->info)
6856 if (!segPtr->body.toggle.inNodeCounts)
6857 g_error ("Toggle segment not in the node counts");
6866 for (childnode = node->children.node;
6868 childnode = childnode->next)
6870 for (summary2 = childnode->summary;
6872 summary2 = summary2->next)
6874 if (summary2->info == summary->info)
6876 toggle_count += summary2->toggle_count;
6881 if (toggle_count != summary->toggle_count)
6883 g_error ("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6884 toggle_count, summary->toggle_count);
6886 for (summary2 = summary->next; summary2 != NULL;
6887 summary2 = summary2->next)
6889 if (summary2->info == summary->info)
6891 g_error ("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6892 summary->info->tag->priv->name);
6899 listify_foreach (GtkTextTag *tag, gpointer user_data)
6901 GSList** listp = user_data;
6903 *listp = g_slist_prepend (*listp, tag);
6907 list_of_tags (GtkTextTagTable *table)
6909 GSList *list = NULL;
6911 gtk_text_tag_table_foreach (table, listify_foreach, &list);
6917 _gtk_text_btree_check (GtkTextBTree *tree)
6920 GtkTextBTreeNode *node;
6922 GtkTextLineSegment *seg;
6924 GSList *all_tags, *taglist = NULL;
6926 GtkTextTagInfo *info;
6929 * Make sure that the tag toggle counts and the tag root pointers are OK.
6931 all_tags = list_of_tags (tree->table);
6932 for (taglist = all_tags; taglist != NULL ; taglist = taglist->next)
6934 tag = taglist->data;
6935 info = gtk_text_btree_get_existing_tag_info (tree, tag);
6938 node = info->tag_root;
6941 if (info->toggle_count != 0)
6943 g_error ("_gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6944 tag->priv->name, info->toggle_count);
6946 continue; /* no ranges for the tag */
6948 else if (info->toggle_count == 0)
6950 g_error ("_gtk_text_btree_check found root for \"%s\" with no toggles",
6953 else if (info->toggle_count & 1)
6955 g_error ("_gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6956 tag->priv->name, info->toggle_count);
6958 for (summary = node->summary; summary != NULL;
6959 summary = summary->next)
6961 if (summary->info->tag == tag)
6963 g_error ("_gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6967 if (node->level > 0)
6969 for (node = node->children.node ; node != NULL ;
6972 for (summary = node->summary; summary != NULL;
6973 summary = summary->next)
6975 if (summary->info->tag == tag)
6977 count += summary->toggle_count;
6984 const GtkTextLineSegmentClass *last = NULL;
6986 for (line = node->children.line ; line != NULL ;
6989 for (seg = line->segments; seg != NULL;
6992 if ((seg->type == >k_text_toggle_on_type ||
6993 seg->type == >k_text_toggle_off_type) &&
6994 seg->body.toggle.info->tag == tag)
6996 if (last == seg->type)
6997 g_error ("Two consecutive toggles on or off weren't merged");
6998 if (!seg->body.toggle.inNodeCounts)
6999 g_error ("Toggle segment not in the node counts");
7008 if (count != info->toggle_count)
7010 g_error ("_gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
7011 info->toggle_count, tag->priv->name, count);
7016 g_slist_free (all_tags);
7019 * Call a recursive procedure to do the main body of checks.
7022 node = tree->root_node;
7023 gtk_text_btree_node_check_consistency (tree, tree->root_node);
7026 * Make sure that there are at least two lines in the text and
7027 * that the last line has no characters except a newline.
7030 if (node->num_lines < 2)
7032 g_error ("_gtk_text_btree_check: less than 2 lines in tree");
7034 if (node->num_chars < 2)
7036 g_error ("_gtk_text_btree_check: less than 2 chars in tree");
7038 while (node->level > 0)
7040 node = node->children.node;
7041 while (node->next != NULL)
7046 line = node->children.line;
7047 while (line->next != NULL)
7051 seg = line->segments;
7052 while ((seg->type == >k_text_toggle_off_type)
7053 || (seg->type == >k_text_right_mark_type)
7054 || (seg->type == >k_text_left_mark_type))
7057 * It's OK to toggle a tag off in the last line, but
7058 * not to start a new range. It's also OK to have marks
7064 if (seg->type != >k_text_char_type)
7066 g_error ("_gtk_text_btree_check: last line has bogus segment type");
7068 if (seg->next != NULL)
7070 g_error ("_gtk_text_btree_check: last line has too many segments");
7072 if (seg->byte_count != 1)
7074 g_error ("_gtk_text_btree_check: last line has wrong # characters: %d",
7077 if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
7079 g_error ("_gtk_text_btree_check: last line had bad value: %s",
7084 void _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line);
7085 void _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment* seg);
7086 void _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent);
7087 void _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
7090 _gtk_text_btree_spew (GtkTextBTree *tree)
7095 printf ("%d lines in tree %p\n",
7096 _gtk_text_btree_line_count (tree), tree);
7098 line = _gtk_text_btree_get_line (tree, 0, &real_line);
7100 while (line != NULL)
7102 _gtk_text_btree_spew_line (tree, line);
7103 line = _gtk_text_line_next (line);
7106 printf ("=================== Tag information\n");
7111 list = tree->tag_infos;
7113 while (list != NULL)
7115 GtkTextTagInfo *info;
7119 printf (" tag `%s': root at %p, toggle count %d\n",
7120 info->tag->priv->name, info->tag_root, info->toggle_count);
7122 list = g_slist_next (list);
7125 if (tree->tag_infos == NULL)
7127 printf (" (no tags in the tree)\n");
7131 printf ("=================== Tree nodes\n");
7134 _gtk_text_btree_spew_node (tree->root_node, 0);
7139 _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
7142 GtkTextLineSegment *seg;
7144 spaces = g_strnfill (indent, ' ');
7146 printf ("%sline %p chars %d bytes %d\n",
7148 _gtk_text_line_char_count (line),
7149 _gtk_text_line_byte_count (line));
7151 seg = line->segments;
7154 if (seg->type == >k_text_char_type)
7156 gchar* str = g_strndup (seg->body.chars, MIN (seg->byte_count, 10));
7161 if (*s == '\n' || *s == '\r')
7165 printf ("%s chars `%s'...\n", spaces, str);
7168 else if (seg->type == >k_text_right_mark_type)
7170 printf ("%s right mark `%s' visible: %d\n",
7172 seg->body.mark.name,
7173 seg->body.mark.visible);
7175 else if (seg->type == >k_text_left_mark_type)
7177 printf ("%s left mark `%s' visible: %d\n",
7179 seg->body.mark.name,
7180 seg->body.mark.visible);
7182 else if (seg->type == >k_text_toggle_on_type ||
7183 seg->type == >k_text_toggle_off_type)
7185 printf ("%s tag `%s' %s\n",
7186 spaces, seg->body.toggle.info->tag->priv->name,
7187 seg->type == >k_text_toggle_off_type ? "off" : "on");
7197 _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent)
7200 GtkTextBTreeNode *iter;
7203 spaces = g_strnfill (indent, ' ');
7205 printf ("%snode %p level %d children %d lines %d chars %d\n",
7206 spaces, node, node->level,
7207 node->num_children, node->num_lines, node->num_chars);
7212 printf ("%s %d toggles of `%s' below this node\n",
7213 spaces, s->toggle_count, s->info->tag->priv->name);
7219 if (node->level > 0)
7221 iter = node->children.node;
7222 while (iter != NULL)
7224 _gtk_text_btree_spew_node (iter, indent + 2);
7231 GtkTextLine *line = node->children.line;
7232 while (line != NULL)
7234 _gtk_text_btree_spew_line_short (line, indent + 2);
7242 _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line)
7244 GtkTextLineSegment * seg;
7246 printf ("%4d| line: %p parent: %p next: %p\n",
7247 _gtk_text_line_get_number (line), line, line->parent, line->next);
7249 seg = line->segments;
7253 _gtk_text_btree_spew_segment (tree, seg);
7259 _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment * seg)
7261 printf (" segment: %p type: %s bytes: %d chars: %d\n",
7262 seg, seg->type->name, seg->byte_count, seg->char_count);
7264 if (seg->type == >k_text_char_type)
7266 gchar* str = g_strndup (seg->body.chars, seg->byte_count);
7267 printf (" `%s'\n", str);
7270 else if (seg->type == >k_text_right_mark_type)
7272 printf (" right mark `%s' visible: %d not_deleteable: %d\n",
7273 seg->body.mark.name,
7274 seg->body.mark.visible,
7275 seg->body.mark.not_deleteable);
7277 else if (seg->type == >k_text_left_mark_type)
7279 printf (" left mark `%s' visible: %d not_deleteable: %d\n",
7280 seg->body.mark.name,
7281 seg->body.mark.visible,
7282 seg->body.mark.not_deleteable);
7284 else if (seg->type == >k_text_toggle_on_type ||
7285 seg->type == >k_text_toggle_off_type)
7287 printf (" tag `%s' priority %d\n",
7288 seg->body.toggle.info->tag->priv->name,
7289 seg->body.toggle.info->tag->priv->priority);