4 * This file contains code that manages the B-tree representation
5 * of text for the text buffer and implements character and
6 * toggle segment types.
8 * Copyright (c) 1992-1994 The Regents of the University of California.
9 * Copyright (c) 1994-1995 Sun Microsystems, Inc.
10 * Copyright (c) 2000 Red Hat, Inc.
11 * Tk -> Gtk port by Havoc Pennington <hp@redhat.com>
13 * This software is copyrighted by the Regents of the University of
14 * California, Sun Microsystems, Inc., and other parties. The
15 * following terms apply to all files associated with the software
16 * unless explicitly disclaimed in individual files.
18 * The authors hereby grant permission to use, copy, modify,
19 * distribute, and license this software and its documentation for any
20 * purpose, provided that existing copyright notices are retained in
21 * all copies and that this notice is included verbatim in any
22 * distributions. No written agreement, license, or royalty fee is
23 * required for any of the authorized uses. Modifications to this
24 * software may be copyrighted by their authors and need not follow
25 * the licensing terms described here, provided that the new terms are
26 * clearly indicated on the first page of each file where they apply.
28 * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY
29 * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
30 * DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION,
31 * OR ANY DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED
32 * OF THE POSSIBILITY OF SUCH DAMAGE.
34 * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
35 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
36 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND
37 * NON-INFRINGEMENT. THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS,
38 * AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE
39 * MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
41 * GOVERNMENT USE: If you are acquiring this software on behalf of the
42 * U.S. government, the Government shall have only "Restricted Rights"
43 * in the software and related documentation as defined in the Federal
44 * Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2). If you
45 * are acquiring the software on behalf of the Department of Defense,
46 * the software shall be classified as "Commercial Computer Software"
47 * and the Government shall have only "Restricted Rights" as defined
48 * in Clause 252.227-7013 (c) (1) of DFARs. Notwithstanding the
49 * foregoing, the authors grant the U.S. Government and others acting
50 * in its behalf permission to use and distribute the software in
51 * accordance with the terms specified in this license.
55 #define GTK_TEXT_USE_INTERNAL_UNSUPPORTED_API
57 #include "gtktextbtree.h"
61 #include "gtktexttag.h"
62 #include "gtktexttagtable.h"
63 #include "gtktextlayout.h"
64 #include "gtktextiterprivate.h"
66 #include "gtktextmarkprivate.h"
75 * The structure below is used to pass information between
76 * _gtk_text_btree_get_tags and inc_count:
79 typedef struct TagInfo {
80 int numTags; /* Number of tags for which there
81 * is currently information in
83 int arraySize; /* Number of entries allocated for
85 GtkTextTag **tags; /* Array of tags seen so far.
87 int *counts; /* Toggle count (so far) for each
88 * entry in tags. Malloc-ed. */
93 * This is used to store per-view width/height info at the tree nodes.
96 typedef struct _NodeData NodeData;
102 /* Height and width of this node */
104 signed int width : 24;
106 /* boolean indicating whether the lines below this node are in need of validation.
107 * However, width/height should always represent the current total width and
108 * max height for lines below this node; the valid flag indicates whether the
109 * width/height on the lines needs recomputing, not whether the totals
112 guint valid : 8; /* Actually a boolean */
117 * The data structure below keeps summary information about one tag as part
118 * of the tag information in a node.
121 typedef struct Summary {
122 GtkTextTagInfo *info; /* Handle for tag. */
123 int toggle_count; /* Number of transitions into or
124 * out of this tag that occur in
125 * the subtree rooted at this node. */
126 struct Summary *next; /* Next in list of all tags for same
127 * node, or NULL if at end of list. */
131 * The data structure below defines a node in the B-tree.
134 struct _GtkTextBTreeNode {
135 GtkTextBTreeNode *parent; /* Pointer to parent node, or NULL if
136 * this is the root. */
137 GtkTextBTreeNode *next; /* Next in list of siblings with the
138 * same parent node, or NULL for end
140 Summary *summary; /* First in malloc-ed list of info
141 * about tags in this subtree (NULL if
142 * no tag info in the subtree). */
143 int level; /* Level of this node in the B-tree.
144 * 0 refers to the bottom of the tree
145 * (children are lines, not nodes). */
146 union { /* First in linked list of children. */
147 struct _GtkTextBTreeNode *node; /* Used if level > 0. */
148 GtkTextLine *line; /* Used if level == 0. */
150 int num_children; /* Number of children of this node. */
151 int num_lines; /* Total number of lines (leaves) in
152 * the subtree rooted here. */
153 int num_chars; /* Number of chars below here */
160 * Used to store the list of views in our btree
163 typedef struct _BTreeView BTreeView;
167 GtkTextLayout *layout;
173 * And the tree itself
176 struct _GtkTextBTree {
177 GtkTextBTreeNode *root_node; /* Pointer to root of B-tree. */
178 GtkTextTagTable *table;
179 GHashTable *mark_table;
181 GtkTextMark *insert_mark;
182 GtkTextMark *selection_bound_mark;
183 GtkTextBuffer *buffer;
186 gulong tag_changed_handler;
188 /* Incremented when a segment with a byte size > 0
189 * is added to or removed from the tree (i.e. the
190 * length of a line may have changed, and lines may
191 * have been added or removed). This invalidates
192 * all outstanding iterators.
194 guint chars_changed_stamp;
195 /* Incremented when any segments are added or deleted;
196 * this makes outstanding iterators recalculate their
197 * pointed-to segment and segment offset.
199 guint segments_changed_stamp;
201 /* Cache the last line in the buffer */
202 GtkTextLine *last_line;
203 guint last_line_stamp;
205 /* Cache the next-to-last line in the buffer,
206 * containing the end iterator
208 GtkTextLine *end_iter_line;
209 GtkTextLineSegment *end_iter_segment;
210 int end_iter_segment_byte_index;
211 int end_iter_segment_char_offset;
212 guint end_iter_line_stamp;
213 guint end_iter_segment_stamp;
215 GHashTable *child_anchor_table;
220 * Upper and lower bounds on how many children a node may have:
221 * rebalance when either of these limits is exceeded. MAX_CHILDREN
222 * should be twice MIN_CHILDREN and MIN_CHILDREN must be >= 2.
225 /* Tk used MAX of 12 and MIN of 6. This makes the tree wide and
226 shallow. It appears to be faster to locate a particular line number
227 if the tree is narrow and deep, since it is more finely sorted. I
228 guess this may increase memory use though, and make it slower to
229 walk the tree in order, or locate a particular byte index (which
230 is done by walking the tree in order).
232 There's basically a tradeoff here. However I'm thinking we want to
233 add pixels, byte counts, and char counts to the tree nodes,
234 at that point narrow and deep should speed up all operations,
235 not just the line number searches.
239 #define MAX_CHILDREN 12
240 #define MIN_CHILDREN 6
242 #define MAX_CHILDREN 6
243 #define MIN_CHILDREN 3
250 static BTreeView *gtk_text_btree_get_view (GtkTextBTree *tree,
252 static void gtk_text_btree_rebalance (GtkTextBTree *tree,
253 GtkTextBTreeNode *node);
254 static GtkTextLine * get_last_line (GtkTextBTree *tree);
255 static void post_insert_fixup (GtkTextBTree *tree,
256 GtkTextLine *insert_line,
257 gint char_count_delta,
258 gint line_count_delta);
259 static void gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
260 GtkTextTagInfo *info,
262 static gboolean gtk_text_btree_node_has_tag (GtkTextBTreeNode *node,
265 static void segments_changed (GtkTextBTree *tree);
266 static void chars_changed (GtkTextBTree *tree);
267 static void summary_list_destroy (Summary *summary);
268 static GtkTextLine *gtk_text_line_new (void);
269 static void gtk_text_line_destroy (GtkTextBTree *tree,
271 static void gtk_text_line_set_parent (GtkTextLine *line,
272 GtkTextBTreeNode *node);
273 static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
277 static NodeData *node_data_new (gpointer view_id);
278 static void node_data_destroy (NodeData *nd);
279 static void node_data_list_destroy (NodeData *nd);
280 static NodeData *node_data_find (NodeData *nd,
283 static GtkTextBTreeNode *gtk_text_btree_node_new (void);
284 static void gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node);
285 static void gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node,
287 static NodeData * gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
289 static NodeData * gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
291 static void gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
294 static void gtk_text_btree_node_remove_view (BTreeView *view,
295 GtkTextBTreeNode *node,
297 static void gtk_text_btree_node_destroy (GtkTextBTree *tree,
298 GtkTextBTreeNode *node);
299 static void gtk_text_btree_node_free_empty (GtkTextBTree *tree,
300 GtkTextBTreeNode *node);
301 static NodeData * gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node,
303 static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
305 static void gtk_text_btree_node_get_size (GtkTextBTreeNode *node,
309 static GtkTextBTreeNode * gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
310 GtkTextBTreeNode *node2);
311 static void get_tree_bounds (GtkTextBTree *tree,
314 static void tag_changed_cb (GtkTextTagTable *table,
316 gboolean size_changed,
318 static void cleanup_line (GtkTextLine *line);
319 static void recompute_node_counts (GtkTextBTree *tree,
320 GtkTextBTreeNode *node);
321 static void inc_count (GtkTextTag *tag,
323 TagInfo *tagInfoPtr);
325 static void summary_destroy (Summary *summary);
327 static void gtk_text_btree_link_segment (GtkTextLineSegment *seg,
328 const GtkTextIter *iter);
329 static void gtk_text_btree_unlink_segment (GtkTextBTree *tree,
330 GtkTextLineSegment *seg,
334 static GtkTextTagInfo *gtk_text_btree_get_tag_info (GtkTextBTree *tree,
336 static GtkTextTagInfo *gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
338 static void gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
341 static void redisplay_region (GtkTextBTree *tree,
342 const GtkTextIter *start,
343 const GtkTextIter *end,
344 gboolean cursors_only);
346 /* Inline thingies */
349 segments_changed (GtkTextBTree *tree)
351 tree->segments_changed_stamp += 1;
355 chars_changed (GtkTextBTree *tree)
357 tree->chars_changed_stamp += 1;
365 _gtk_text_btree_new (GtkTextTagTable *table,
366 GtkTextBuffer *buffer)
369 GtkTextBTreeNode *root_node;
370 GtkTextLine *line, *line2;
372 g_return_val_if_fail (GTK_IS_TEXT_TAG_TABLE (table), NULL);
373 g_return_val_if_fail (GTK_IS_TEXT_BUFFER (buffer), NULL);
376 * The tree will initially have two empty lines. The second line
377 * isn't actually part of the tree's contents, but its presence
378 * makes several operations easier. The tree will have one GtkTextBTreeNode,
379 * which is also the root of the tree.
382 /* Create the root node. */
384 root_node = gtk_text_btree_node_new ();
386 line = gtk_text_line_new ();
387 line2 = gtk_text_line_new ();
389 root_node->parent = NULL;
390 root_node->next = NULL;
391 root_node->summary = NULL;
392 root_node->level = 0;
393 root_node->children.line = line;
394 root_node->num_children = 2;
395 root_node->num_lines = 2;
396 root_node->num_chars = 2;
398 line->parent = root_node;
401 line->segments = _gtk_char_segment_new ("\n", 1);
403 line2->parent = root_node;
405 line2->segments = _gtk_char_segment_new ("\n", 1);
407 /* Create the tree itself */
409 tree = g_new0(GtkTextBTree, 1);
410 tree->root_node = root_node;
414 /* Set these to values that are unlikely to be found
415 * in random memory garbage, and also avoid
416 * duplicates between tree instances.
418 tree->chars_changed_stamp = g_random_int ();
419 tree->segments_changed_stamp = g_random_int ();
421 tree->last_line_stamp = tree->chars_changed_stamp - 1;
422 tree->last_line = NULL;
424 tree->end_iter_line_stamp = tree->chars_changed_stamp - 1;
425 tree->end_iter_segment_stamp = tree->segments_changed_stamp - 1;
426 tree->end_iter_line = NULL;
427 tree->end_iter_segment_byte_index = 0;
428 tree->end_iter_segment_char_offset = 0;
430 g_object_ref (tree->table);
432 tree->tag_changed_handler = g_signal_connect (tree->table,
434 G_CALLBACK (tag_changed_cb),
437 tree->mark_table = g_hash_table_new (g_str_hash, g_str_equal);
438 tree->child_anchor_table = NULL;
440 /* We don't ref the buffer, since the buffer owns us;
441 * we'd have some circularity issues. The buffer always
442 * lasts longer than the BTree
444 tree->buffer = buffer;
448 GtkTextLineSegment *seg;
450 _gtk_text_btree_get_iter_at_line_char (tree, &start, 0, 0);
453 tree->insert_mark = _gtk_text_btree_set_mark (tree,
460 seg = tree->insert_mark->segment;
462 seg->body.mark.not_deleteable = TRUE;
463 seg->body.mark.visible = TRUE;
465 tree->selection_bound_mark = _gtk_text_btree_set_mark (tree,
472 seg = tree->selection_bound_mark->segment;
474 seg->body.mark.not_deleteable = TRUE;
476 g_object_ref (tree->insert_mark);
477 g_object_ref (tree->selection_bound_mark);
486 _gtk_text_btree_ref (GtkTextBTree *tree)
488 g_return_if_fail (tree != NULL);
489 g_return_if_fail (tree->refcount > 0);
495 _gtk_text_btree_unref (GtkTextBTree *tree)
497 g_return_if_fail (tree != NULL);
498 g_return_if_fail (tree->refcount > 0);
502 if (tree->refcount == 0)
504 g_signal_handler_disconnect (tree->table,
505 tree->tag_changed_handler);
507 g_object_unref (tree->table);
510 gtk_text_btree_node_destroy (tree, tree->root_node);
511 tree->root_node = NULL;
513 g_assert (g_hash_table_size (tree->mark_table) == 0);
514 g_hash_table_destroy (tree->mark_table);
515 tree->mark_table = NULL;
516 if (tree->child_anchor_table != NULL)
518 g_hash_table_destroy (tree->child_anchor_table);
519 tree->child_anchor_table = NULL;
522 g_object_unref (tree->insert_mark);
523 tree->insert_mark = NULL;
524 g_object_unref (tree->selection_bound_mark);
525 tree->selection_bound_mark = NULL;
532 _gtk_text_btree_get_buffer (GtkTextBTree *tree)
538 _gtk_text_btree_get_chars_changed_stamp (GtkTextBTree *tree)
540 return tree->chars_changed_stamp;
544 _gtk_text_btree_get_segments_changed_stamp (GtkTextBTree *tree)
546 return tree->segments_changed_stamp;
550 _gtk_text_btree_segments_changed (GtkTextBTree *tree)
552 g_return_if_fail (tree != NULL);
553 segments_changed (tree);
557 * Indexable segment mutation
561 * The following function is responsible for resolving the bidi direction
562 * for the lines between start and end. But it also calculates any
563 * dependent bidi direction for surrounding lines that change as a result
564 * of the bidi direction decisions within the range. The function is
565 * trying to do as little propagation as is needed.
568 gtk_text_btree_resolve_bidi (GtkTextIter *start,
571 GtkTextBTree *tree = _gtk_text_iter_get_btree (start);
572 GtkTextLine *start_line, *end_line, *start_line_prev, *end_line_next, *line;
573 PangoDirection last_strong, dir_above_propagated, dir_below_propagated;
575 /* Resolve the strong bidi direction for all lines between
578 start_line = _gtk_text_iter_get_text_line (start);
579 start_line_prev = _gtk_text_line_previous (start_line);
580 end_line = _gtk_text_iter_get_text_line (end);
581 end_line_next = _gtk_text_line_next (end_line);
584 while (line && line != end_line_next)
586 /* Loop through the segments and search for a strong character
588 GtkTextLineSegment *seg = line->segments;
589 line->dir_strong = PANGO_DIRECTION_NEUTRAL;
593 if (seg->type == >k_text_char_type && seg->byte_count > 0)
595 PangoDirection pango_dir;
597 pango_dir = pango_find_base_dir (seg->body.chars,
600 if (pango_dir != PANGO_DIRECTION_NEUTRAL)
602 line->dir_strong = pango_dir;
609 line = _gtk_text_line_next (line);
614 /* The variable dir_above_propagated contains the forward propagated
615 * direction before start. It is neutral if start is in the beginning
618 dir_above_propagated = PANGO_DIRECTION_NEUTRAL;
620 dir_above_propagated = start_line_prev->dir_propagated_forward;
622 /* Loop forward and propagate the direction of each paragraph
623 * to all neutral lines.
626 last_strong = dir_above_propagated;
627 while (line != end_line_next)
629 if (line->dir_strong != PANGO_DIRECTION_NEUTRAL)
630 last_strong = line->dir_strong;
632 line->dir_propagated_forward = last_strong;
634 line = _gtk_text_line_next (line);
637 /* Continue propagating as long as the previous resolved forward
638 * is different from last_strong.
641 GtkTextIter end_propagate;
644 line->dir_strong == PANGO_DIRECTION_NEUTRAL &&
645 line->dir_propagated_forward != last_strong)
647 GtkTextLine *prev = line;
648 line->dir_propagated_forward = last_strong;
650 line = _gtk_text_line_next(line);
658 /* The last line to invalidate is the last line before the
659 * line with the strong character. Or in case of the end of the
660 * buffer, the last line of the buffer. (There seems to be an
661 * extra "virtual" last line in the buffer that must not be used
662 * calling _gtk_text_btree_get_iter_at_line (causes crash). Thus the
663 * _gtk_text_line_previous is ok in that case as well.)
665 line = _gtk_text_line_previous (line);
666 _gtk_text_btree_get_iter_at_line (tree, &end_propagate, line, 0);
667 _gtk_text_btree_invalidate_region (tree, end, &end_propagate, FALSE);
672 /* The variable dir_below_propagated contains the backward propagated
673 * direction after end. It is neutral if end is at the end of
676 dir_below_propagated = PANGO_DIRECTION_NEUTRAL;
678 dir_below_propagated = end_line_next->dir_propagated_back;
680 /* Loop backward and propagate the direction of each paragraph
681 * to all neutral lines.
684 last_strong = dir_below_propagated;
685 while (line != start_line_prev)
687 if (line->dir_strong != PANGO_DIRECTION_NEUTRAL)
688 last_strong = line->dir_strong;
690 line->dir_propagated_back = last_strong;
692 line = _gtk_text_line_previous (line);
695 /* Continue propagating as long as the resolved backward dir
696 * is different from last_strong.
699 GtkTextIter start_propagate;
702 line->dir_strong == PANGO_DIRECTION_NEUTRAL &&
703 line->dir_propagated_back != last_strong)
705 GtkTextLine *prev = line;
706 line->dir_propagated_back = last_strong;
708 line = _gtk_text_line_previous (line);
716 /* We only need to invalidate for backwards propagation if the
717 * line we ended up on didn't get a direction from forwards
720 if (line && line->dir_propagated_forward == PANGO_DIRECTION_NEUTRAL)
722 _gtk_text_btree_get_iter_at_line (tree, &start_propagate, line, 0);
723 _gtk_text_btree_invalidate_region (tree, &start_propagate, start, FALSE);
729 _gtk_text_btree_delete (GtkTextIter *start,
732 GtkTextLineSegment *prev_seg; /* The segment just before the start
733 * of the deletion range. */
734 GtkTextLineSegment *last_seg; /* The segment just after the end
735 * of the deletion range. */
736 GtkTextLineSegment *seg, *next, *next2;
737 GtkTextLine *curline;
738 GtkTextBTreeNode *curnode, *node;
740 GtkTextLine *start_line;
741 GtkTextLine *end_line;
743 GtkTextLine *deleted_lines = NULL; /* List of lines we've deleted */
744 gint start_byte_offset;
746 g_return_if_fail (start != NULL);
747 g_return_if_fail (end != NULL);
748 g_return_if_fail (_gtk_text_iter_get_btree (start) ==
749 _gtk_text_iter_get_btree (end));
751 gtk_text_iter_order (start, end);
753 tree = _gtk_text_iter_get_btree (start);
755 if (gtk_debug_flags & GTK_DEBUG_TEXT)
756 _gtk_text_btree_check (tree);
758 /* Broadcast the need for redisplay before we break the iterators */
759 DV (g_print ("invalidating due to deleting some text (%s)\n", G_STRLOC));
760 _gtk_text_btree_invalidate_region (tree, start, end, FALSE);
762 /* Save the byte offset so we can reset the iterators */
763 start_byte_offset = gtk_text_iter_get_line_index (start);
765 start_line = _gtk_text_iter_get_text_line (start);
766 end_line = _gtk_text_iter_get_text_line (end);
769 * Split the start and end segments, so we have a place
770 * to insert our new text.
772 * Tricky point: split at end first; otherwise the split
773 * at end may invalidate seg and/or prev_seg. This allows
774 * us to avoid invalidating segments for start.
777 last_seg = gtk_text_line_segment_split (end);
778 if (last_seg != NULL)
779 last_seg = last_seg->next;
781 last_seg = end_line->segments;
783 prev_seg = gtk_text_line_segment_split (start);
784 if (prev_seg != NULL)
786 seg = prev_seg->next;
787 prev_seg->next = last_seg;
791 seg = start_line->segments;
792 start_line->segments = last_seg;
795 /* notify iterators that their segments need recomputation,
796 just for robustness. */
797 segments_changed (tree);
800 * Delete all of the segments between prev_seg and last_seg.
803 curline = start_line;
804 curnode = curline->parent;
805 while (seg != last_seg)
811 GtkTextLine *nextline;
814 * We just ran off the end of a line. First find the
815 * next line, then go back to the old line and delete it
816 * (unless it's the starting line for the range).
819 nextline = _gtk_text_line_next (curline);
820 if (curline != start_line)
822 if (curnode == start_line->parent)
823 start_line->next = curline->next;
825 curnode->children.line = curline->next;
827 for (node = curnode; node != NULL;
830 /* Don't update node->num_chars, because
831 * that was done when we deleted the segments.
833 node->num_lines -= 1;
836 curnode->num_children -= 1;
837 curline->next = deleted_lines;
838 deleted_lines = curline;
842 seg = curline->segments;
845 * If the GtkTextBTreeNode is empty then delete it and its parents,
846 * recursively upwards until a non-empty GtkTextBTreeNode is found.
849 while (curnode->num_children == 0)
851 GtkTextBTreeNode *parent;
853 parent = curnode->parent;
854 if (parent->children.node == curnode)
856 parent->children.node = curnode->next;
860 GtkTextBTreeNode *prevnode = parent->children.node;
861 while (prevnode->next != curnode)
863 prevnode = prevnode->next;
865 prevnode->next = curnode->next;
867 parent->num_children--;
868 gtk_text_btree_node_free_empty (tree, curnode);
871 curnode = curline->parent;
876 char_count = seg->char_count;
878 if ((*seg->type->deleteFunc)(seg, curline, FALSE) != 0)
881 * This segment refuses to die. Move it to prev_seg and
882 * advance prev_seg if the segment has left gravity.
885 if (prev_seg == NULL)
887 seg->next = start_line->segments;
888 start_line->segments = seg;
890 else if (prev_seg->next &&
891 prev_seg->next != last_seg &&
892 seg->type == >k_text_toggle_off_type &&
893 prev_seg->next->type == >k_text_toggle_on_type &&
894 seg->body.toggle.info == prev_seg->next->body.toggle.info)
896 /* Try to match an off toggle with the matching on toggle
897 * if it immediately follows. This is a common case, and
898 * handling it here prevents quadratic blowup in
899 * cleanup_line() below. See bug 317125.
901 next2 = prev_seg->next->next;
902 g_free ((char *)prev_seg->next);
903 prev_seg->next = next2;
904 g_free ((char *)seg);
909 seg->next = prev_seg->next;
910 prev_seg->next = seg;
913 if (seg && seg->type->leftGravity)
920 /* Segment is gone. Decrement the char count of the node and
922 for (node = curnode; node != NULL;
925 node->num_chars -= char_count;
933 * If the beginning and end of the deletion range are in different
934 * lines, join the two lines together and discard the ending line.
937 if (start_line != end_line)
940 GtkTextBTreeNode *ancestor_node;
941 GtkTextLine *prevline;
944 /* last_seg was appended to start_line up at the top of this function */
946 for (seg = last_seg; seg != NULL;
949 chars_moved += seg->char_count;
950 if (seg->type->lineChangeFunc != NULL)
952 (*seg->type->lineChangeFunc)(seg, end_line);
956 for (node = start_line->parent; node != NULL;
959 node->num_chars += chars_moved;
962 curnode = end_line->parent;
963 for (node = curnode; node != NULL;
966 node->num_chars -= chars_moved;
969 curnode->num_children--;
970 prevline = curnode->children.line;
971 if (prevline == end_line)
973 curnode->children.line = end_line->next;
977 while (prevline->next != end_line)
979 prevline = prevline->next;
981 prevline->next = end_line->next;
983 end_line->next = deleted_lines;
984 deleted_lines = end_line;
986 /* We now fix up the per-view aggregates. We add all the height and
987 * width for the deleted lines to the start line, so that when revalidation
988 * occurs, the correct change in size is seen.
990 ancestor_node = gtk_text_btree_node_common_parent (curnode, start_line->parent);
996 gint deleted_width = 0;
997 gint deleted_height = 0;
999 line = deleted_lines;
1002 GtkTextLine *next_line = line->next;
1003 ld = _gtk_text_line_get_data (line, view->view_id);
1007 deleted_width = MAX (deleted_width, ld->width);
1008 deleted_height += ld->height;
1014 if (deleted_width > 0 || deleted_height > 0)
1016 ld = _gtk_text_line_get_data (start_line, view->view_id);
1020 /* This means that start_line has never been validated.
1021 * We don't really want to do the validation here but
1022 * we do need to store our temporary sizes. So we
1023 * create the line data and assume a line w/h of 0.
1025 ld = _gtk_text_line_data_new (view->layout, start_line);
1026 _gtk_text_line_add_data (start_line, ld);
1032 ld->width = MAX (deleted_width, ld->width);
1033 ld->height += deleted_height;
1037 gtk_text_btree_node_check_valid_downward (ancestor_node, view->view_id);
1038 if (ancestor_node->parent)
1039 gtk_text_btree_node_check_valid_upward (ancestor_node->parent, view->view_id);
1044 line = deleted_lines;
1047 GtkTextLine *next_line = line->next;
1049 gtk_text_line_destroy (tree, line);
1054 /* avoid dangling pointer */
1055 deleted_lines = NULL;
1057 gtk_text_btree_rebalance (tree, curnode);
1061 * Cleanup the segments in the new line.
1064 cleanup_line (start_line);
1067 * Lastly, rebalance the first GtkTextBTreeNode of the range.
1070 gtk_text_btree_rebalance (tree, start_line->parent);
1072 /* Notify outstanding iterators that they
1074 chars_changed (tree);
1075 segments_changed (tree);
1077 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1078 _gtk_text_btree_check (tree);
1080 /* Re-initialize our iterators */
1081 _gtk_text_btree_get_iter_at_line (tree, start, start_line, start_byte_offset);
1084 gtk_text_btree_resolve_bidi (start, end);
1088 _gtk_text_btree_insert (GtkTextIter *iter,
1092 GtkTextLineSegment *prev_seg; /* The segment just before the first
1093 * new segment (NULL means new segment
1094 * is at beginning of line). */
1095 GtkTextLineSegment *cur_seg; /* Current segment; new characters
1096 * are inserted just after this one.
1097 * NULL means insert at beginning of
1099 GtkTextLine *line; /* Current line (new segments are
1100 * added to this line). */
1101 GtkTextLineSegment *seg;
1102 GtkTextLine *newline;
1103 int chunk_len; /* # characters in current chunk. */
1104 gint sol; /* start of line */
1105 gint eol; /* Pointer to character just after last
1106 * one in current chunk.
1108 gint delim; /* index of paragraph delimiter */
1109 int line_count_delta; /* Counts change to total number of
1113 int char_count_delta; /* change to number of chars */
1115 gint start_byte_index;
1116 GtkTextLine *start_line;
1118 g_return_if_fail (text != NULL);
1119 g_return_if_fail (iter != NULL);
1122 len = strlen (text);
1124 /* extract iterator info */
1125 tree = _gtk_text_iter_get_btree (iter);
1126 line = _gtk_text_iter_get_text_line (iter);
1129 start_byte_index = gtk_text_iter_get_line_index (iter);
1131 /* Get our insertion segment split. Note this assumes line allows
1132 * char insertions, which isn't true of the "last" line. But iter
1133 * should not be on that line, as we assert here.
1135 g_assert (!_gtk_text_line_is_last (line, tree));
1136 prev_seg = gtk_text_line_segment_split (iter);
1139 /* Invalidate all iterators */
1140 chars_changed (tree);
1141 segments_changed (tree);
1144 * Chop the text up into lines and create a new segment for
1145 * each line, plus a new line for the leftovers from the
1151 line_count_delta = 0;
1152 char_count_delta = 0;
1157 pango_find_paragraph_boundary (text + sol,
1162 /* make these relative to the start of the text */
1166 g_assert (eol >= sol);
1167 g_assert (delim >= sol);
1168 g_assert (eol >= delim);
1169 g_assert (sol >= 0);
1170 g_assert (eol <= len);
1172 chunk_len = eol - sol;
1174 g_assert (g_utf8_validate (&text[sol], chunk_len, NULL));
1175 seg = _gtk_char_segment_new (&text[sol], chunk_len);
1177 char_count_delta += seg->char_count;
1179 if (cur_seg == NULL)
1181 seg->next = line->segments;
1182 line->segments = seg;
1186 seg->next = cur_seg->next;
1187 cur_seg->next = seg;
1192 /* chunk didn't end with a paragraph separator */
1193 g_assert (eol == len);
1198 * The chunk ended with a newline, so create a new GtkTextLine
1199 * and move the remainder of the old line to it.
1202 newline = gtk_text_line_new ();
1203 gtk_text_line_set_parent (newline, line->parent);
1204 newline->next = line->next;
1205 line->next = newline;
1206 newline->segments = seg->next;
1214 * Cleanup the starting line for the insertion, plus the ending
1215 * line if it's different.
1218 cleanup_line (start_line);
1219 if (line != start_line)
1221 cleanup_line (line);
1224 post_insert_fixup (tree, line, line_count_delta, char_count_delta);
1226 /* Invalidate our region, and reset the iterator the user
1227 passed in to point to the end of the inserted text. */
1233 _gtk_text_btree_get_iter_at_line (tree,
1239 /* We could almost certainly be more efficient here
1240 by saving the information from the insertion loop
1242 gtk_text_iter_forward_chars (&end, char_count_delta);
1244 DV (g_print ("invalidating due to inserting some text (%s)\n", G_STRLOC));
1245 _gtk_text_btree_invalidate_region (tree, &start, &end, FALSE);
1248 /* Convenience for the user */
1251 gtk_text_btree_resolve_bidi (&start, &end);
1256 insert_pixbuf_or_widget_segment (GtkTextIter *iter,
1257 GtkTextLineSegment *seg)
1261 GtkTextLineSegment *prevPtr;
1264 gint start_byte_offset;
1266 line = _gtk_text_iter_get_text_line (iter);
1267 tree = _gtk_text_iter_get_btree (iter);
1268 start_byte_offset = gtk_text_iter_get_line_index (iter);
1270 prevPtr = gtk_text_line_segment_split (iter);
1271 if (prevPtr == NULL)
1273 seg->next = line->segments;
1274 line->segments = seg;
1278 seg->next = prevPtr->next;
1279 prevPtr->next = seg;
1282 post_insert_fixup (tree, line, 0, seg->char_count);
1284 chars_changed (tree);
1285 segments_changed (tree);
1287 /* reset *iter for the user, and invalidate tree nodes */
1289 _gtk_text_btree_get_iter_at_line (tree, &start, line, start_byte_offset);
1292 gtk_text_iter_forward_char (iter); /* skip forward past the segment */
1294 DV (g_print ("invalidating due to inserting pixbuf/widget (%s)\n", G_STRLOC));
1295 _gtk_text_btree_invalidate_region (tree, &start, iter, FALSE);
1299 _gtk_text_btree_insert_pixbuf (GtkTextIter *iter,
1302 GtkTextLineSegment *seg;
1304 seg = _gtk_pixbuf_segment_new (pixbuf);
1306 insert_pixbuf_or_widget_segment (iter, seg);
1310 _gtk_text_btree_insert_child_anchor (GtkTextIter *iter,
1311 GtkTextChildAnchor *anchor)
1313 GtkTextLineSegment *seg;
1316 if (anchor->segment != NULL)
1318 g_warning (G_STRLOC": Same child anchor can't be inserted twice");
1322 seg = _gtk_widget_segment_new (anchor);
1324 tree = seg->body.child.tree = _gtk_text_iter_get_btree (iter);
1325 seg->body.child.line = _gtk_text_iter_get_text_line (iter);
1327 insert_pixbuf_or_widget_segment (iter, seg);
1329 if (tree->child_anchor_table == NULL)
1330 tree->child_anchor_table = g_hash_table_new (NULL, NULL);
1332 g_hash_table_insert (tree->child_anchor_table,
1333 seg->body.child.obj,
1334 seg->body.child.obj);
1338 _gtk_text_btree_unregister_child_anchor (GtkTextChildAnchor *anchor)
1340 GtkTextLineSegment *seg;
1342 seg = anchor->segment;
1344 g_hash_table_remove (seg->body.child.tree->child_anchor_table,
1353 find_line_by_y (GtkTextBTree *tree, BTreeView *view,
1354 GtkTextBTreeNode *node, gint y, gint *line_top,
1355 GtkTextLine *last_line)
1359 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1360 _gtk_text_btree_check (tree);
1362 if (node->level == 0)
1366 line = node->children.line;
1368 while (line != NULL && line != last_line)
1370 GtkTextLineData *ld;
1372 ld = _gtk_text_line_get_data (line, view->view_id);
1376 if (y < (current_y + (ld ? ld->height : 0)))
1379 current_y += ld->height;
1380 *line_top += ld->height;
1389 GtkTextBTreeNode *child;
1391 child = node->children.node;
1393 while (child != NULL)
1398 gtk_text_btree_node_get_size (child, view->view_id,
1401 if (y < (current_y + height))
1402 return find_line_by_y (tree, view, child,
1403 y - current_y, line_top,
1406 current_y += height;
1407 *line_top += height;
1409 child = child->next;
1417 _gtk_text_btree_find_line_by_y (GtkTextBTree *tree,
1424 GtkTextLine *last_line;
1427 view = gtk_text_btree_get_view (tree, view_id);
1428 g_return_val_if_fail (view != NULL, NULL);
1430 last_line = get_last_line (tree);
1432 line = find_line_by_y (tree, view, tree->root_node, ypixel, &line_top,
1436 *line_top_out = line_top;
1442 find_line_top_in_line_list (GtkTextBTree *tree,
1445 GtkTextLine *target_line,
1448 while (line != NULL)
1450 GtkTextLineData *ld;
1452 if (line == target_line)
1455 ld = _gtk_text_line_get_data (line, view->view_id);
1462 g_assert_not_reached (); /* If we get here, our
1463 target line didn't exist
1464 under its parent node */
1469 _gtk_text_btree_find_line_top (GtkTextBTree *tree,
1470 GtkTextLine *target_line,
1477 GtkTextBTreeNode *node;
1479 view = gtk_text_btree_get_view (tree, view_id);
1481 g_return_val_if_fail (view != NULL, 0);
1484 node = target_line->parent;
1485 while (node != NULL)
1487 nodes = g_slist_prepend (nodes, node);
1488 node = node->parent;
1492 while (iter != NULL)
1496 if (node->level == 0)
1498 g_slist_free (nodes);
1499 return find_line_top_in_line_list (tree, view,
1500 node->children.line,
1505 GtkTextBTreeNode *child;
1506 GtkTextBTreeNode *target_node;
1508 g_assert (iter->next != NULL); /* not at level 0 */
1509 target_node = iter->next->data;
1511 child = node->children.node;
1513 while (child != NULL)
1518 if (child == target_node)
1522 gtk_text_btree_node_get_size (child, view->view_id,
1526 child = child->next;
1528 g_assert (child != NULL); /* should have broken out before we
1532 iter = g_slist_next (iter);
1535 g_assert_not_reached (); /* we return when we find the target line */
1540 _gtk_text_btree_add_view (GtkTextBTree *tree,
1541 GtkTextLayout *layout)
1544 GtkTextLine *last_line;
1545 GtkTextLineData *line_data;
1547 g_return_if_fail (tree != NULL);
1549 view = g_new (BTreeView, 1);
1551 view->view_id = layout;
1552 view->layout = layout;
1554 view->next = tree->views;
1559 g_assert (tree->views->prev == NULL);
1560 tree->views->prev = view;
1565 /* The last line in the buffer has identity values for the per-view
1566 * data so that we can avoid special case checks for it in a large
1569 last_line = get_last_line (tree);
1571 line_data = g_new (GtkTextLineData, 1);
1572 line_data->view_id = layout;
1573 line_data->next = NULL;
1574 line_data->width = 0;
1575 line_data->height = 0;
1576 line_data->valid = TRUE;
1578 _gtk_text_line_add_data (last_line, line_data);
1582 _gtk_text_btree_remove_view (GtkTextBTree *tree,
1586 GtkTextLine *last_line;
1587 GtkTextLineData *line_data;
1589 g_return_if_fail (tree != NULL);
1593 while (view != NULL)
1595 if (view->view_id == view_id)
1601 g_return_if_fail (view != NULL);
1604 view->next->prev = view->prev;
1607 view->prev->next = view->next;
1609 if (view == tree->views)
1610 tree->views = view->next;
1612 /* Remove the line data for the last line which we added ourselves.
1613 * (Do this first, so that we don't try to call the view's line data destructor on it.)
1615 last_line = get_last_line (tree);
1616 line_data = _gtk_text_line_remove_data (last_line, view_id);
1619 gtk_text_btree_node_remove_view (view, tree->root_node, view_id);
1621 view->layout = (gpointer) 0xdeadbeef;
1622 view->view_id = (gpointer) 0xdeadbeef;
1628 _gtk_text_btree_invalidate_region (GtkTextBTree *tree,
1629 const GtkTextIter *start,
1630 const GtkTextIter *end,
1631 gboolean cursors_only)
1637 while (view != NULL)
1640 gtk_text_layout_invalidate_cursors (view->layout, start, end);
1642 gtk_text_layout_invalidate (view->layout, start, end);
1649 _gtk_text_btree_get_view_size (GtkTextBTree *tree,
1654 g_return_if_fail (tree != NULL);
1655 g_return_if_fail (view_id != NULL);
1657 gtk_text_btree_node_get_size (tree->root_node, view_id,
1672 iter_stack_new (void)
1675 stack = g_slice_new (IterStack);
1676 stack->iters = NULL;
1683 iter_stack_push (IterStack *stack,
1684 const GtkTextIter *iter)
1687 if (stack->count > stack->alloced)
1689 stack->alloced = stack->count*2;
1690 stack->iters = g_realloc (stack->iters,
1691 stack->alloced * sizeof (GtkTextIter));
1693 stack->iters[stack->count-1] = *iter;
1697 iter_stack_pop (IterStack *stack,
1700 if (stack->count == 0)
1705 *iter = stack->iters[stack->count];
1711 iter_stack_free (IterStack *stack)
1713 g_free (stack->iters);
1714 g_slice_free (IterStack, stack);
1718 iter_stack_invert (IterStack *stack)
1720 if (stack->count > 0)
1723 guint j = stack->count - 1;
1728 tmp = stack->iters[i];
1729 stack->iters[i] = stack->iters[j];
1730 stack->iters[j] = tmp;
1739 queue_tag_redisplay (GtkTextBTree *tree,
1741 const GtkTextIter *start,
1742 const GtkTextIter *end)
1744 if (_gtk_text_tag_affects_size (tag))
1746 DV (g_print ("invalidating due to size-affecting tag (%s)\n", G_STRLOC));
1747 _gtk_text_btree_invalidate_region (tree, start, end, FALSE);
1749 else if (_gtk_text_tag_affects_nonsize_appearance (tag))
1751 /* We only need to queue a redraw, not a relayout */
1752 redisplay_region (tree, start, end, FALSE);
1755 /* We don't need to do anything if the tag doesn't affect display */
1759 _gtk_text_btree_tag (const GtkTextIter *start_orig,
1760 const GtkTextIter *end_orig,
1764 GtkTextLineSegment *seg, *prev;
1765 GtkTextLine *cleanupline;
1766 gboolean toggled_on;
1767 GtkTextLine *start_line;
1768 GtkTextLine *end_line;
1770 GtkTextIter start, end;
1773 GtkTextTagInfo *info;
1775 g_return_if_fail (start_orig != NULL);
1776 g_return_if_fail (end_orig != NULL);
1777 g_return_if_fail (GTK_IS_TEXT_TAG (tag));
1778 g_return_if_fail (_gtk_text_iter_get_btree (start_orig) ==
1779 _gtk_text_iter_get_btree (end_orig));
1780 g_return_if_fail (tag->table == _gtk_text_iter_get_btree (start_orig)->table);
1783 printf ("%s tag %s from %d to %d\n",
1784 add ? "Adding" : "Removing",
1786 gtk_text_buffer_get_offset (start_orig),
1787 gtk_text_buffer_get_offset (end_orig));
1790 if (gtk_text_iter_equal (start_orig, end_orig))
1793 start = *start_orig;
1796 gtk_text_iter_order (&start, &end);
1798 tree = _gtk_text_iter_get_btree (&start);
1800 queue_tag_redisplay (tree, tag, &start, &end);
1802 info = gtk_text_btree_get_tag_info (tree, tag);
1804 start_line = _gtk_text_iter_get_text_line (&start);
1805 end_line = _gtk_text_iter_get_text_line (&end);
1807 /* Find all tag toggles in the region; we are going to delete them.
1808 We need to find them in advance, because
1809 forward_find_tag_toggle () won't work once we start playing around
1811 stack = iter_stack_new ();
1814 /* forward_to_tag_toggle() skips a toggle at the start iterator,
1815 * which is deliberate - we don't want to delete a toggle at the
1818 while (gtk_text_iter_forward_to_tag_toggle (&iter, tag))
1820 if (gtk_text_iter_compare (&iter, &end) >= 0)
1823 iter_stack_push (stack, &iter);
1826 /* We need to traverse the toggles in order. */
1827 iter_stack_invert (stack);
1830 * See whether the tag is present at the start of the range. If
1831 * the state doesn't already match what we want then add a toggle
1835 toggled_on = gtk_text_iter_has_tag (&start, tag);
1836 if ( (add && !toggled_on) ||
1837 (!add && toggled_on) )
1839 /* This could create a second toggle at the start position;
1840 cleanup_line () will remove it if so. */
1841 seg = _gtk_toggle_segment_new (info, add);
1843 prev = gtk_text_line_segment_split (&start);
1846 seg->next = start_line->segments;
1847 start_line->segments = seg;
1851 seg->next = prev->next;
1855 /* cleanup_line adds the new toggle to the node counts. */
1857 printf ("added toggle at start\n");
1859 /* we should probably call segments_changed, but in theory
1860 any still-cached segments in the iters we are about to
1861 use are still valid, since they're in front
1867 * Scan the range of characters and delete any internal tag
1868 * transitions. Keep track of what the old state was at the end
1869 * of the range, and add a toggle there if it's needed.
1873 cleanupline = start_line;
1874 while (iter_stack_pop (stack, &iter))
1876 GtkTextLineSegment *indexable_seg;
1879 line = _gtk_text_iter_get_text_line (&iter);
1880 seg = _gtk_text_iter_get_any_segment (&iter);
1881 indexable_seg = _gtk_text_iter_get_indexable_segment (&iter);
1883 g_assert (seg != NULL);
1884 g_assert (indexable_seg != NULL);
1885 g_assert (seg != indexable_seg);
1887 prev = line->segments;
1889 /* Find the segment that actually toggles this tag. */
1890 while (seg != indexable_seg)
1892 g_assert (seg != NULL);
1893 g_assert (indexable_seg != NULL);
1894 g_assert (seg != indexable_seg);
1896 if ( (seg->type == >k_text_toggle_on_type ||
1897 seg->type == >k_text_toggle_off_type) &&
1898 (seg->body.toggle.info == info) )
1904 g_assert (seg != NULL);
1905 g_assert (indexable_seg != NULL);
1907 g_assert (seg != indexable_seg); /* If this happens, then
1908 forward_to_tag_toggle was
1910 g_assert (seg->body.toggle.info->tag == tag);
1912 /* If this happens, when previously tagging we didn't merge
1913 overlapping tags. */
1914 g_assert ( (toggled_on && seg->type == >k_text_toggle_off_type) ||
1915 (!toggled_on && seg->type == >k_text_toggle_on_type) );
1917 toggled_on = !toggled_on;
1920 printf ("deleting %s toggle\n",
1921 seg->type == >k_text_toggle_on_type ? "on" : "off");
1923 /* Remove toggle segment from the list. */
1926 line->segments = seg->next;
1930 while (prev->next != seg)
1934 prev->next = seg->next;
1937 /* Inform iterators we've hosed them. This actually reflects a
1938 bit of inefficiency; if you have the same tag toggled on and
1939 off a lot in a single line, we keep having the rescan from
1940 the front of the line. Of course we have to do that to get
1941 "prev" anyway, but here we are doing it an additional
1943 segments_changed (tree);
1945 /* Update node counts */
1946 if (seg->body.toggle.inNodeCounts)
1948 _gtk_change_node_toggle_count (line->parent,
1950 seg->body.toggle.inNodeCounts = FALSE;
1955 /* We only clean up lines when we're done with them, saves some
1956 gratuitous line-segment-traversals */
1958 if (cleanupline != line)
1960 cleanup_line (cleanupline);
1965 iter_stack_free (stack);
1967 /* toggled_on now reflects the toggle state _just before_ the
1968 end iterator. The end iterator could already have a toggle
1969 on or a toggle off. */
1970 if ( (add && !toggled_on) ||
1971 (!add && toggled_on) )
1973 /* This could create a second toggle at the start position;
1974 cleanup_line () will remove it if so. */
1976 seg = _gtk_toggle_segment_new (info, !add);
1978 prev = gtk_text_line_segment_split (&end);
1981 seg->next = end_line->segments;
1982 end_line->segments = seg;
1986 seg->next = prev->next;
1989 /* cleanup_line adds the new toggle to the node counts. */
1990 g_assert (seg->body.toggle.inNodeCounts == FALSE);
1992 printf ("added toggle at end\n");
1997 * Cleanup cleanupline and the last line of the range, if
1998 * these are different.
2001 cleanup_line (cleanupline);
2002 if (cleanupline != end_line)
2004 cleanup_line (end_line);
2007 segments_changed (tree);
2009 queue_tag_redisplay (tree, tag, &start, &end);
2011 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2012 _gtk_text_btree_check (tree);
2021 get_line_internal (GtkTextBTree *tree,
2023 gint *real_line_number,
2024 gboolean include_last)
2026 GtkTextBTreeNode *node;
2031 line_count = _gtk_text_btree_line_count (tree);
2035 if (line_number < 0)
2037 line_number = line_count;
2039 else if (line_number > line_count)
2041 line_number = line_count;
2044 if (real_line_number)
2045 *real_line_number = line_number;
2047 node = tree->root_node;
2048 lines_left = line_number;
2051 * Work down through levels of the tree until a GtkTextBTreeNode is found at
2055 while (node->level != 0)
2057 for (node = node->children.node;
2058 node->num_lines <= lines_left;
2064 g_error ("gtk_text_btree_find_line ran out of GtkTextBTreeNodes");
2067 lines_left -= node->num_lines;
2072 * Work through the lines attached to the level-0 GtkTextBTreeNode.
2075 for (line = node->children.line; lines_left > 0;
2081 g_error ("gtk_text_btree_find_line ran out of lines");
2090 _gtk_text_btree_get_end_iter_line (GtkTextBTree *tree)
2093 _gtk_text_btree_get_line (tree,
2094 _gtk_text_btree_line_count (tree) - 1,
2099 _gtk_text_btree_get_line (GtkTextBTree *tree,
2101 gint *real_line_number)
2103 return get_line_internal (tree, line_number, real_line_number, TRUE);
2107 _gtk_text_btree_get_line_no_last (GtkTextBTree *tree,
2109 gint *real_line_number)
2111 return get_line_internal (tree, line_number, real_line_number, FALSE);
2115 _gtk_text_btree_get_line_at_char (GtkTextBTree *tree,
2117 gint *line_start_index,
2118 gint *real_char_index)
2120 GtkTextBTreeNode *node;
2122 GtkTextLineSegment *seg;
2126 node = tree->root_node;
2128 /* Clamp to valid indexes (-1 is magic for "highest index"),
2129 * node->num_chars includes the two newlines that aren't really
2132 if (char_index < 0 || char_index >= (node->num_chars - 1))
2134 char_index = node->num_chars - 2;
2137 *real_char_index = char_index;
2140 * Work down through levels of the tree until a GtkTextBTreeNode is found at
2144 chars_left = char_index;
2145 while (node->level != 0)
2147 for (node = node->children.node;
2148 chars_left >= node->num_chars;
2151 chars_left -= node->num_chars;
2153 g_assert (chars_left >= 0);
2157 if (chars_left == 0)
2159 /* Start of a line */
2161 *line_start_index = char_index;
2162 return node->children.line;
2166 * Work through the lines attached to the level-0 GtkTextBTreeNode.
2171 for (line = node->children.line; line != NULL; line = line->next)
2173 seg = line->segments;
2176 if (chars_in_line + seg->char_count > chars_left)
2177 goto found; /* found our line/segment */
2179 chars_in_line += seg->char_count;
2184 chars_left -= chars_in_line;
2192 g_assert (line != NULL); /* hosage, ran out of lines */
2193 g_assert (seg != NULL);
2195 *line_start_index = char_index - chars_left;
2199 /* It returns an array sorted by tags priority, ready to pass to
2200 * _gtk_text_attributes_fill_from_tags() */
2202 _gtk_text_btree_get_tags (const GtkTextIter *iter,
2205 GtkTextBTreeNode *node;
2206 GtkTextLine *siblingline;
2207 GtkTextLineSegment *seg;
2208 int src, dst, index;
2213 #define NUM_TAG_INFOS 10
2215 line = _gtk_text_iter_get_text_line (iter);
2216 byte_index = gtk_text_iter_get_line_index (iter);
2218 tagInfo.numTags = 0;
2219 tagInfo.arraySize = NUM_TAG_INFOS;
2220 tagInfo.tags = g_new (GtkTextTag*, NUM_TAG_INFOS);
2221 tagInfo.counts = g_new (int, NUM_TAG_INFOS);
2224 * Record tag toggles within the line of indexPtr but preceding
2225 * indexPtr. Note that if this loop segfaults, your
2226 * byte_index probably points past the sum of all
2227 * seg->byte_count */
2229 for (index = 0, seg = line->segments;
2230 (index + seg->byte_count) <= byte_index;
2231 index += seg->byte_count, seg = seg->next)
2233 if ((seg->type == >k_text_toggle_on_type)
2234 || (seg->type == >k_text_toggle_off_type))
2236 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2241 * Record toggles for tags in lines that are predecessors of
2242 * line but under the same level-0 GtkTextBTreeNode.
2245 for (siblingline = line->parent->children.line;
2246 siblingline != line;
2247 siblingline = siblingline->next)
2249 for (seg = siblingline->segments; seg != NULL;
2252 if ((seg->type == >k_text_toggle_on_type)
2253 || (seg->type == >k_text_toggle_off_type))
2255 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2261 * For each GtkTextBTreeNode in the ancestry of this line, record tag
2262 * toggles for all siblings that precede that GtkTextBTreeNode.
2265 for (node = line->parent; node->parent != NULL;
2266 node = node->parent)
2268 GtkTextBTreeNode *siblingPtr;
2271 for (siblingPtr = node->parent->children.node;
2272 siblingPtr != node; siblingPtr = siblingPtr->next)
2274 for (summary = siblingPtr->summary; summary != NULL;
2275 summary = summary->next)
2277 if (summary->toggle_count & 1)
2279 inc_count (summary->info->tag, summary->toggle_count,
2287 * Go through the tag information and squash out all of the tags
2288 * that have even toggle counts (these tags exist before the point
2289 * of interest, but not at the desired character itself).
2292 for (src = 0, dst = 0; src < tagInfo.numTags; src++)
2294 if (tagInfo.counts[src] & 1)
2296 g_assert (GTK_IS_TEXT_TAG (tagInfo.tags[src]));
2297 tagInfo.tags[dst] = tagInfo.tags[src];
2303 g_free (tagInfo.counts);
2306 g_free (tagInfo.tags);
2310 /* Sort tags in ascending order of priority */
2311 _gtk_text_tag_array_sort (tagInfo.tags, dst);
2313 return tagInfo.tags;
2317 copy_segment (GString *string,
2318 gboolean include_hidden,
2319 gboolean include_nonchars,
2320 const GtkTextIter *start,
2321 const GtkTextIter *end)
2323 GtkTextLineSegment *end_seg;
2324 GtkTextLineSegment *seg;
2326 if (gtk_text_iter_equal (start, end))
2329 seg = _gtk_text_iter_get_indexable_segment (start);
2330 end_seg = _gtk_text_iter_get_indexable_segment (end);
2332 if (seg->type == >k_text_char_type)
2334 gboolean copy = TRUE;
2335 gint copy_bytes = 0;
2336 gint copy_start = 0;
2338 /* Don't copy if we're invisible; segments are invisible/not
2339 as a whole, no need to check each char */
2340 if (!include_hidden &&
2341 _gtk_text_btree_char_is_invisible (start))
2344 /* printf (" <invisible>\n"); */
2347 copy_start = _gtk_text_iter_get_segment_byte (start);
2351 /* End is in the same segment; need to copy fewer bytes. */
2352 gint end_byte = _gtk_text_iter_get_segment_byte (end);
2354 copy_bytes = end_byte - copy_start;
2357 copy_bytes = seg->byte_count - copy_start;
2359 g_assert (copy_bytes != 0); /* Due to iter equality check at
2360 front of this function. */
2364 g_assert ((copy_start + copy_bytes) <= seg->byte_count);
2366 g_string_append_len (string,
2367 seg->body.chars + copy_start,
2371 /* printf (" :%s\n", string->str); */
2373 else if (seg->type == >k_text_pixbuf_type ||
2374 seg->type == >k_text_child_type)
2376 gboolean copy = TRUE;
2378 if (!include_nonchars)
2382 else if (!include_hidden &&
2383 _gtk_text_btree_char_is_invisible (start))
2390 g_string_append_len (string,
2391 gtk_text_unknown_char_utf8,
2399 _gtk_text_btree_get_text (const GtkTextIter *start_orig,
2400 const GtkTextIter *end_orig,
2401 gboolean include_hidden,
2402 gboolean include_nonchars)
2404 GtkTextLineSegment *seg;
2405 GtkTextLineSegment *end_seg;
2412 g_return_val_if_fail (start_orig != NULL, NULL);
2413 g_return_val_if_fail (end_orig != NULL, NULL);
2414 g_return_val_if_fail (_gtk_text_iter_get_btree (start_orig) ==
2415 _gtk_text_iter_get_btree (end_orig), NULL);
2417 start = *start_orig;
2420 gtk_text_iter_order (&start, &end);
2422 retval = g_string_new (NULL);
2424 end_seg = _gtk_text_iter_get_indexable_segment (&end);
2426 seg = _gtk_text_iter_get_indexable_segment (&iter);
2427 while (seg != end_seg)
2429 copy_segment (retval, include_hidden, include_nonchars,
2432 _gtk_text_iter_forward_indexable_segment (&iter);
2434 seg = _gtk_text_iter_get_indexable_segment (&iter);
2437 copy_segment (retval, include_hidden, include_nonchars, &iter, &end);
2440 g_string_free (retval, FALSE);
2445 _gtk_text_btree_line_count (GtkTextBTree *tree)
2447 /* Subtract bogus line at the end; we return a count
2449 return tree->root_node->num_lines - 1;
2453 _gtk_text_btree_char_count (GtkTextBTree *tree)
2455 /* Exclude newline in bogus last line and the
2456 * one in the last line that is after the end iterator
2458 return tree->root_node->num_chars - 2;
2461 #define LOTSA_TAGS 1000
2463 _gtk_text_btree_char_is_invisible (const GtkTextIter *iter)
2465 gboolean invisible = FALSE; /* if nobody says otherwise, it's visible */
2467 int deftagCnts[LOTSA_TAGS] = { 0, };
2468 int *tagCnts = deftagCnts;
2469 GtkTextTag *deftags[LOTSA_TAGS];
2470 GtkTextTag **tags = deftags;
2472 GtkTextBTreeNode *node;
2473 GtkTextLine *siblingline;
2474 GtkTextLineSegment *seg;
2481 line = _gtk_text_iter_get_text_line (iter);
2482 tree = _gtk_text_iter_get_btree (iter);
2483 byte_index = gtk_text_iter_get_line_index (iter);
2485 numTags = gtk_text_tag_table_get_size (tree->table);
2487 /* almost always avoid malloc, so stay out of system calls */
2488 if (LOTSA_TAGS < numTags)
2490 tagCnts = g_new0 (int, numTags);
2491 tags = g_new (GtkTextTag*, numTags);
2495 * Record tag toggles within the line of indexPtr but preceding
2499 for (index = 0, seg = line->segments;
2500 (index + seg->byte_count) <= byte_index; /* segfault here means invalid index */
2501 index += seg->byte_count, seg = seg->next)
2503 if ((seg->type == >k_text_toggle_on_type)
2504 || (seg->type == >k_text_toggle_off_type))
2506 tag = seg->body.toggle.info->tag;
2507 if (tag->invisible_set)
2509 tags[tag->priority] = tag;
2510 tagCnts[tag->priority]++;
2516 * Record toggles for tags in lines that are predecessors of
2517 * line but under the same level-0 GtkTextBTreeNode.
2520 for (siblingline = line->parent->children.line;
2521 siblingline != line;
2522 siblingline = siblingline->next)
2524 for (seg = siblingline->segments; seg != NULL;
2527 if ((seg->type == >k_text_toggle_on_type)
2528 || (seg->type == >k_text_toggle_off_type))
2530 tag = seg->body.toggle.info->tag;
2531 if (tag->invisible_set)
2533 tags[tag->priority] = tag;
2534 tagCnts[tag->priority]++;
2541 * For each GtkTextBTreeNode in the ancestry of this line, record tag toggles
2542 * for all siblings that precede that GtkTextBTreeNode.
2545 for (node = line->parent; node->parent != NULL;
2546 node = node->parent)
2548 GtkTextBTreeNode *siblingPtr;
2551 for (siblingPtr = node->parent->children.node;
2552 siblingPtr != node; siblingPtr = siblingPtr->next)
2554 for (summary = siblingPtr->summary; summary != NULL;
2555 summary = summary->next)
2557 if (summary->toggle_count & 1)
2559 tag = summary->info->tag;
2560 if (tag->invisible_set)
2562 tags[tag->priority] = tag;
2563 tagCnts[tag->priority] += summary->toggle_count;
2571 * Now traverse from highest priority to lowest,
2572 * take invisible value from first odd count (= on)
2575 for (i = numTags-1; i >=0; i--)
2579 /* FIXME not sure this should be if 0 */
2581 #ifndef ALWAYS_SHOW_SELECTION
2582 /* who would make the selection invisible? */
2583 if ((tag == tkxt->seltag)
2584 && !(tkxt->flags & GOT_FOCUS))
2590 invisible = tags[i]->values->invisible;
2595 if (LOTSA_TAGS < numTags)
2610 redisplay_region (GtkTextBTree *tree,
2611 const GtkTextIter *start,
2612 const GtkTextIter *end,
2613 gboolean cursors_only)
2616 GtkTextLine *start_line, *end_line;
2618 if (gtk_text_iter_compare (start, end) > 0)
2620 const GtkTextIter *tmp = start;
2625 start_line = _gtk_text_iter_get_text_line (start);
2626 end_line = _gtk_text_iter_get_text_line (end);
2629 while (view != NULL)
2631 gint start_y, end_y;
2632 GtkTextLineData *ld;
2634 start_y = _gtk_text_btree_find_line_top (tree, start_line, view->view_id);
2636 if (end_line == start_line)
2639 end_y = _gtk_text_btree_find_line_top (tree, end_line, view->view_id);
2641 ld = _gtk_text_line_get_data (end_line, view->view_id);
2643 end_y += ld->height;
2646 gtk_text_layout_cursors_changed (view->layout, start_y,
2650 gtk_text_layout_changed (view->layout, start_y,
2659 redisplay_mark (GtkTextLineSegment *mark)
2664 _gtk_text_btree_get_iter_at_mark (mark->body.mark.tree,
2666 mark->body.mark.obj);
2669 gtk_text_iter_forward_char (&end);
2671 DV (g_print ("invalidating due to moving visible mark (%s)\n", G_STRLOC));
2672 _gtk_text_btree_invalidate_region (mark->body.mark.tree, &iter, &end, TRUE);
2676 redisplay_mark_if_visible (GtkTextLineSegment *mark)
2678 if (!mark->body.mark.visible)
2681 redisplay_mark (mark);
2685 ensure_not_off_end (GtkTextBTree *tree,
2686 GtkTextLineSegment *mark,
2689 if (gtk_text_iter_get_line (iter) == _gtk_text_btree_line_count (tree))
2690 gtk_text_iter_backward_char (iter);
2693 static GtkTextLineSegment*
2694 real_set_mark (GtkTextBTree *tree,
2695 GtkTextMark *existing_mark,
2697 gboolean left_gravity,
2698 const GtkTextIter *where,
2699 gboolean should_exist,
2700 gboolean redraw_selections)
2702 GtkTextLineSegment *mark;
2705 g_return_val_if_fail (tree != NULL, NULL);
2706 g_return_val_if_fail (where != NULL, NULL);
2707 g_return_val_if_fail (_gtk_text_iter_get_btree (where) == tree, NULL);
2711 if (gtk_text_mark_get_buffer (existing_mark) != NULL)
2712 mark = existing_mark->segment;
2716 else if (name != NULL)
2717 mark = g_hash_table_lookup (tree->mark_table,
2722 if (should_exist && mark == NULL)
2724 g_warning ("No mark `%s' exists!", name);
2728 /* OK if !should_exist and it does already exist, in that case
2734 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2735 _gtk_text_iter_check (&iter);
2739 if (redraw_selections &&
2740 (mark == tree->insert_mark->segment ||
2741 mark == tree->selection_bound_mark->segment))
2743 GtkTextIter old_pos;
2745 _gtk_text_btree_get_iter_at_mark (tree, &old_pos,
2746 mark->body.mark.obj);
2747 redisplay_region (tree, &old_pos, where, TRUE);
2751 * don't let visible marks be after the final newline of the
2755 if (mark->body.mark.visible)
2757 ensure_not_off_end (tree, mark, &iter);
2760 /* Redraw the mark's old location. */
2761 redisplay_mark_if_visible (mark);
2763 /* Unlink mark from its current location.
2764 This could hose our iterator... */
2765 gtk_text_btree_unlink_segment (tree, mark,
2766 mark->body.mark.line);
2767 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2768 g_assert (mark->body.mark.line == _gtk_text_iter_get_text_line (&iter));
2770 segments_changed (tree); /* make sure the iterator recomputes its
2776 g_object_ref (existing_mark);
2778 existing_mark = gtk_text_mark_new (name, left_gravity);
2780 mark = existing_mark->segment;
2781 _gtk_mark_segment_set_tree (mark, tree);
2783 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2785 if (mark->body.mark.name)
2786 g_hash_table_insert (tree->mark_table,
2787 mark->body.mark.name,
2791 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2792 _gtk_text_iter_check (&iter);
2794 /* Link mark into new location */
2795 gtk_text_btree_link_segment (mark, &iter);
2797 /* Invalidate some iterators. */
2798 segments_changed (tree);
2801 * update the screen at the mark's new location.
2804 redisplay_mark_if_visible (mark);
2806 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2807 _gtk_text_iter_check (&iter);
2809 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2810 _gtk_text_btree_check (tree);
2817 _gtk_text_btree_set_mark (GtkTextBTree *tree,
2818 GtkTextMark *existing_mark,
2820 gboolean left_gravity,
2821 const GtkTextIter *iter,
2822 gboolean should_exist)
2824 GtkTextLineSegment *seg;
2826 seg = real_set_mark (tree, existing_mark,
2827 name, left_gravity, iter, should_exist,
2830 return seg ? seg->body.mark.obj : NULL;
2834 _gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2838 GtkTextIter tmp_start, tmp_end;
2840 _gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2842 _gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2843 tree->selection_bound_mark);
2845 if (gtk_text_iter_equal (&tmp_start, &tmp_end))
2857 gtk_text_iter_order (&tmp_start, &tmp_end);
2870 _gtk_text_btree_place_cursor (GtkTextBTree *tree,
2871 const GtkTextIter *iter)
2873 _gtk_text_btree_select_range (tree, iter, iter);
2877 _gtk_text_btree_select_range (GtkTextBTree *tree,
2878 const GtkTextIter *ins,
2879 const GtkTextIter *bound)
2881 GtkTextIter old_ins, old_bound;
2883 _gtk_text_btree_get_iter_at_mark (tree, &old_ins,
2885 _gtk_text_btree_get_iter_at_mark (tree, &old_bound,
2886 tree->selection_bound_mark);
2888 /* Check if it's no-op since gtk_text_buffer_place_cursor()
2889 * also calls this, and this will redraw the cursor line. */
2890 if (!gtk_text_iter_equal (&old_ins, ins) ||
2891 !gtk_text_iter_equal (&old_bound, bound))
2893 redisplay_region (tree, &old_ins, &old_bound, TRUE);
2895 /* Move insert AND selection_bound before we redisplay */
2896 real_set_mark (tree, tree->insert_mark,
2897 "insert", FALSE, ins, TRUE, FALSE);
2898 real_set_mark (tree, tree->selection_bound_mark,
2899 "selection_bound", FALSE, bound, TRUE, FALSE);
2901 redisplay_region (tree, ins, bound, TRUE);
2907 _gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2912 g_return_if_fail (tree != NULL);
2913 g_return_if_fail (name != NULL);
2915 mark = g_hash_table_lookup (tree->mark_table,
2918 _gtk_text_btree_remove_mark (tree, mark);
2922 _gtk_text_btree_release_mark_segment (GtkTextBTree *tree,
2923 GtkTextLineSegment *segment)
2926 if (segment->body.mark.name)
2927 g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2929 segment->body.mark.tree = NULL;
2930 segment->body.mark.line = NULL;
2932 /* Remove the ref on the mark, which frees segment as a side effect
2933 * if this is the last reference.
2935 g_object_unref (segment->body.mark.obj);
2939 _gtk_text_btree_remove_mark (GtkTextBTree *tree,
2942 GtkTextLineSegment *segment;
2944 g_return_if_fail (mark != NULL);
2945 g_return_if_fail (tree != NULL);
2947 segment = mark->segment;
2949 if (segment->body.mark.not_deleteable)
2951 g_warning ("Can't delete special mark `%s'", segment->body.mark.name);
2955 /* This calls cleanup_line and segments_changed */
2956 gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2958 _gtk_text_btree_release_mark_segment (tree, segment);
2962 _gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2963 GtkTextMark *segment)
2965 return segment == tree->insert_mark;
2969 _gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2970 GtkTextMark *segment)
2972 return segment == tree->selection_bound_mark;
2976 _gtk_text_btree_get_insert (GtkTextBTree *tree)
2978 return tree->insert_mark;
2982 _gtk_text_btree_get_selection_bound (GtkTextBTree *tree)
2984 return tree->selection_bound_mark;
2988 _gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2991 GtkTextLineSegment *seg;
2993 g_return_val_if_fail (tree != NULL, NULL);
2994 g_return_val_if_fail (name != NULL, NULL);
2996 seg = g_hash_table_lookup (tree->mark_table, name);
2998 return seg ? seg->body.mark.obj : NULL;
3002 * gtk_text_mark_set_visible:
3003 * @mark: a #GtkTextMark
3004 * @setting: visibility of mark
3006 * Sets the visibility of @mark; the insertion point is normally
3007 * visible, i.e. you can see it as a vertical bar. Also, the text
3008 * widget uses a visible mark to indicate where a drop will occur when
3009 * dragging-and-dropping text. Most other marks are not visible.
3010 * Marks are not visible by default.
3014 gtk_text_mark_set_visible (GtkTextMark *mark,
3017 GtkTextLineSegment *seg;
3019 g_return_if_fail (mark != NULL);
3021 seg = mark->segment;
3023 if (seg->body.mark.visible == setting)
3027 seg->body.mark.visible = setting;
3029 if (seg->body.mark.tree)
3030 redisplay_mark (seg);
3035 _gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
3038 GtkTextBTreeNode *node;
3039 GtkTextTagInfo *info;
3041 g_return_val_if_fail (tree != NULL, NULL);
3045 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3050 if (info->tag_root == NULL)
3053 node = info->tag_root;
3055 /* We know the tag root has instances of the given
3058 continue_outer_loop:
3059 g_assert (node != NULL);
3060 while (node->level > 0)
3062 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
3063 node = node->children.node;
3064 while (node != NULL)
3066 if (gtk_text_btree_node_has_tag (node, tag))
3067 goto continue_outer_loop;
3071 g_assert (node != NULL);
3074 g_assert (node != NULL); /* The tag summaries said some node had
3077 g_assert (node->level == 0);
3079 return node->children.line;
3083 /* Looking for any tag at all (tag == NULL).
3084 Unfortunately this can't be done in a simple and efficient way
3085 right now; so I'm just going to return the
3086 first line in the btree. FIXME */
3087 return _gtk_text_btree_get_line (tree, 0, NULL);
3092 _gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
3095 GtkTextBTreeNode *node;
3096 GtkTextBTreeNode *last_node;
3098 GtkTextTagInfo *info;
3100 g_return_val_if_fail (tree != NULL, NULL);
3104 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3106 if (info->tag_root == NULL)
3109 node = info->tag_root;
3110 /* We know the tag root has instances of the given
3113 while (node->level > 0)
3115 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
3117 node = node->children.node;
3118 while (node != NULL)
3120 if (gtk_text_btree_node_has_tag (node, tag))
3128 g_assert (node != NULL); /* The tag summaries said some node had
3131 g_assert (node->level == 0);
3133 /* Find the last line in this node */
3134 line = node->children.line;
3135 while (line->next != NULL)
3142 /* This search can't be done efficiently at the moment,
3143 at least not without complexity.
3144 So, we just return the last line.
3146 return _gtk_text_btree_get_end_iter_line (tree);
3156 _gtk_text_line_get_number (GtkTextLine *line)
3159 GtkTextBTreeNode *node, *parent, *node2;
3163 * First count how many lines precede this one in its level-0
3167 node = line->parent;
3169 for (line2 = node->children.line; line2 != line;
3170 line2 = line2->next)
3174 g_error ("gtk_text_btree_line_number couldn't find line");
3180 * Now work up through the levels of the tree one at a time,
3181 * counting how many lines are in GtkTextBTreeNodes preceding the current
3185 for (parent = node->parent ; parent != NULL;
3186 node = parent, parent = parent->parent)
3188 for (node2 = parent->children.node; node2 != node;
3189 node2 = node2->next)
3193 g_error ("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
3195 index += node2->num_lines;
3201 static GtkTextLineSegment*
3202 find_toggle_segment_before_char (GtkTextLine *line,
3206 GtkTextLineSegment *seg;
3207 GtkTextLineSegment *toggle_seg;
3212 seg = line->segments;
3213 while ( (index + seg->char_count) <= char_in_line )
3215 if (((seg->type == >k_text_toggle_on_type)
3216 || (seg->type == >k_text_toggle_off_type))
3217 && (seg->body.toggle.info->tag == tag))
3220 index += seg->char_count;
3227 static GtkTextLineSegment*
3228 find_toggle_segment_before_byte (GtkTextLine *line,
3232 GtkTextLineSegment *seg;
3233 GtkTextLineSegment *toggle_seg;
3238 seg = line->segments;
3239 while ( (index + seg->byte_count) <= byte_in_line )
3241 if (((seg->type == >k_text_toggle_on_type)
3242 || (seg->type == >k_text_toggle_off_type))
3243 && (seg->body.toggle.info->tag == tag))
3246 index += seg->byte_count;
3254 find_toggle_outside_current_line (GtkTextLine *line,
3258 GtkTextBTreeNode *node;
3259 GtkTextLine *sibling_line;
3260 GtkTextLineSegment *seg;
3261 GtkTextLineSegment *toggle_seg;
3263 GtkTextTagInfo *info = NULL;
3266 * No toggle in this line. Look for toggles for the tag in lines
3267 * that are predecessors of line but under the same
3268 * level-0 GtkTextBTreeNode.
3271 sibling_line = line->parent->children.line;
3272 while (sibling_line != line)
3274 seg = sibling_line->segments;
3277 if (((seg->type == >k_text_toggle_on_type)
3278 || (seg->type == >k_text_toggle_off_type))
3279 && (seg->body.toggle.info->tag == tag))
3285 sibling_line = sibling_line->next;
3288 if (toggle_seg != NULL)
3289 return (toggle_seg->type == >k_text_toggle_on_type);
3292 * No toggle in this GtkTextBTreeNode. Scan upwards through the ancestors of
3293 * this GtkTextBTreeNode, counting the number of toggles of the given tag in
3294 * siblings that precede that GtkTextBTreeNode.
3297 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3303 node = line->parent;
3304 while (node->parent != NULL)
3306 GtkTextBTreeNode *sibling_node;
3308 sibling_node = node->parent->children.node;
3309 while (sibling_node != node)
3313 summary = sibling_node->summary;
3314 while (summary != NULL)
3316 if (summary->info == info)
3317 toggles += summary->toggle_count;
3319 summary = summary->next;
3322 sibling_node = sibling_node->next;
3325 if (node == info->tag_root)
3328 node = node->parent;
3332 * An odd number of toggles means that the tag is present at the
3336 return (toggles & 1) != 0;
3339 /* FIXME this function is far too slow, for no good reason. */
3341 _gtk_text_line_char_has_tag (GtkTextLine *line,
3346 GtkTextLineSegment *toggle_seg;
3348 g_return_val_if_fail (line != NULL, FALSE);
3351 * Check for toggles for the tag in the line but before
3352 * the char. If there is one, its type indicates whether or
3353 * not the character is tagged.
3356 toggle_seg = find_toggle_segment_before_char (line, char_in_line, tag);
3358 if (toggle_seg != NULL)
3359 return (toggle_seg->type == >k_text_toggle_on_type);
3361 return find_toggle_outside_current_line (line, tree, tag);
3365 _gtk_text_line_byte_has_tag (GtkTextLine *line,
3370 GtkTextLineSegment *toggle_seg;
3372 g_return_val_if_fail (line != NULL, FALSE);
3375 * Check for toggles for the tag in the line but before
3376 * the char. If there is one, its type indicates whether or
3377 * not the character is tagged.
3380 toggle_seg = find_toggle_segment_before_byte (line, byte_in_line, tag);
3382 if (toggle_seg != NULL)
3383 return (toggle_seg->type == >k_text_toggle_on_type);
3385 return find_toggle_outside_current_line (line, tree, tag);
3389 _gtk_text_line_is_last (GtkTextLine *line,
3392 return line == get_last_line (tree);
3396 ensure_end_iter_line (GtkTextBTree *tree)
3398 if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
3402 /* n_lines is without the magic line at the end */
3403 g_assert (_gtk_text_btree_line_count (tree) >= 1);
3405 tree->end_iter_line = _gtk_text_btree_get_line_no_last (tree, -1, &real_line);
3407 tree->end_iter_line_stamp = tree->chars_changed_stamp;
3412 ensure_end_iter_segment (GtkTextBTree *tree)
3414 if (tree->end_iter_segment_stamp != tree->segments_changed_stamp)
3416 GtkTextLineSegment *seg;
3417 GtkTextLineSegment *last_with_chars;
3419 ensure_end_iter_line (tree);
3421 last_with_chars = NULL;
3423 seg = tree->end_iter_line->segments;
3426 if (seg->char_count > 0)
3427 last_with_chars = seg;
3431 tree->end_iter_segment = last_with_chars;
3433 /* We know the last char in the last line is '\n' */
3434 tree->end_iter_segment_byte_index = last_with_chars->byte_count - 1;
3435 tree->end_iter_segment_char_offset = last_with_chars->char_count - 1;
3437 tree->end_iter_segment_stamp = tree->segments_changed_stamp;
3439 g_assert (tree->end_iter_segment->type == >k_text_char_type);
3440 g_assert (tree->end_iter_segment->body.chars[tree->end_iter_segment_byte_index] == '\n');
3445 _gtk_text_line_contains_end_iter (GtkTextLine *line,
3448 ensure_end_iter_line (tree);
3450 return line == tree->end_iter_line;
3454 _gtk_text_btree_is_end (GtkTextBTree *tree,
3456 GtkTextLineSegment *seg,
3460 g_return_val_if_fail (byte_index >= 0 || char_offset >= 0, FALSE);
3462 /* Do this first to avoid walking segments in most cases */
3463 if (!_gtk_text_line_contains_end_iter (line, tree))
3466 ensure_end_iter_segment (tree);
3468 if (seg != tree->end_iter_segment)
3471 if (byte_index >= 0)
3472 return byte_index == tree->end_iter_segment_byte_index;
3474 return char_offset == tree->end_iter_segment_char_offset;
3478 _gtk_text_line_next (GtkTextLine *line)
3480 GtkTextBTreeNode *node;
3482 if (line->next != NULL)
3487 * This was the last line associated with the particular parent
3488 * GtkTextBTreeNode. Search up the tree for the next GtkTextBTreeNode,
3489 * then search down from that GtkTextBTreeNode to find the first
3493 node = line->parent;
3494 while (node != NULL && node->next == NULL)
3495 node = node->parent;
3501 while (node->level > 0)
3503 node = node->children.node;
3506 g_assert (node->children.line != line);
3508 return node->children.line;
3513 _gtk_text_line_next_excluding_last (GtkTextLine *line)
3517 next = _gtk_text_line_next (line);
3519 /* If we were on the end iter line, we can't go to
3522 if (next && next->next == NULL && /* these checks are optimization only */
3523 _gtk_text_line_next (next) == NULL)
3530 _gtk_text_line_previous (GtkTextLine *line)
3532 GtkTextBTreeNode *node;
3533 GtkTextBTreeNode *node2;
3537 * Find the line under this GtkTextBTreeNode just before the starting line.
3539 prev = line->parent->children.line; /* First line at leaf */
3540 while (prev != line)
3542 if (prev->next == line)
3548 g_error ("gtk_text_btree_previous_line ran out of lines");
3552 * This was the first line associated with the particular parent
3553 * GtkTextBTreeNode. Search up the tree for the previous GtkTextBTreeNode,
3554 * then search down from that GtkTextBTreeNode to find its last line.
3556 for (node = line->parent; ; node = node->parent)
3558 if (node == NULL || node->parent == NULL)
3560 else if (node != node->parent->children.node)
3564 for (node2 = node->parent->children.node; ;
3565 node2 = node2->children.node)
3567 while (node2->next != node)
3568 node2 = node2->next;
3570 if (node2->level == 0)
3576 for (prev = node2->children.line ; ; prev = prev->next)
3578 if (prev->next == NULL)
3582 g_assert_not_reached ();
3588 _gtk_text_line_data_new (GtkTextLayout *layout,
3591 GtkTextLineData *line_data;
3593 line_data = g_new (GtkTextLineData, 1);
3595 line_data->view_id = layout;
3596 line_data->next = NULL;
3597 line_data->width = 0;
3598 line_data->height = 0;
3599 line_data->valid = FALSE;
3605 _gtk_text_line_add_data (GtkTextLine *line,
3606 GtkTextLineData *data)
3608 g_return_if_fail (line != NULL);
3609 g_return_if_fail (data != NULL);
3610 g_return_if_fail (data->view_id != NULL);
3614 data->next = line->views;
3624 _gtk_text_line_remove_data (GtkTextLine *line,
3627 GtkTextLineData *prev;
3628 GtkTextLineData *iter;
3630 g_return_val_if_fail (line != NULL, NULL);
3631 g_return_val_if_fail (view_id != NULL, NULL);
3635 while (iter != NULL)
3637 if (iter->view_id == view_id)
3646 prev->next = iter->next;
3648 line->views = iter->next;
3657 _gtk_text_line_get_data (GtkTextLine *line,
3660 GtkTextLineData *iter;
3662 g_return_val_if_fail (line != NULL, NULL);
3663 g_return_val_if_fail (view_id != NULL, NULL);
3666 while (iter != NULL)
3668 if (iter->view_id == view_id)
3677 _gtk_text_line_invalidate_wrap (GtkTextLine *line,
3678 GtkTextLineData *ld)
3680 /* For now this is totally unoptimized. FIXME?
3682 We could probably optimize the case where the width removed
3683 is less than the max width for the parent node,
3684 and the case where the height is unchanged when we re-wrap.
3687 g_return_if_fail (ld != NULL);
3690 gtk_text_btree_node_invalidate_upward (line->parent, ld->view_id);
3694 _gtk_text_line_char_count (GtkTextLine *line)
3696 GtkTextLineSegment *seg;
3700 seg = line->segments;
3703 size += seg->char_count;
3710 _gtk_text_line_byte_count (GtkTextLine *line)
3712 GtkTextLineSegment *seg;
3716 seg = line->segments;
3719 size += seg->byte_count;
3727 _gtk_text_line_char_index (GtkTextLine *target_line)
3729 GSList *node_stack = NULL;
3730 GtkTextBTreeNode *iter;
3734 /* Push all our parent nodes onto a stack */
3735 iter = target_line->parent;
3737 g_assert (iter != NULL);
3739 while (iter != NULL)
3741 node_stack = g_slist_prepend (node_stack, iter);
3743 iter = iter->parent;
3746 /* Check that we have the root node on top of the stack. */
3747 g_assert (node_stack != NULL &&
3748 node_stack->data != NULL &&
3749 ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3751 /* Add up chars in all nodes before the nodes in our stack.
3755 iter = node_stack->data;
3756 while (iter != NULL)
3758 GtkTextBTreeNode *child_iter;
3759 GtkTextBTreeNode *next_node;
3761 next_node = node_stack->next ?
3762 node_stack->next->data : NULL;
3763 node_stack = g_slist_remove (node_stack, node_stack->data);
3765 if (iter->level == 0)
3767 /* stack should be empty when we're on the last node */
3768 g_assert (node_stack == NULL);
3769 break; /* Our children are now lines */
3772 g_assert (next_node != NULL);
3773 g_assert (iter != NULL);
3774 g_assert (next_node->parent == iter);
3776 /* Add up chars before us in the tree */
3777 child_iter = iter->children.node;
3778 while (child_iter != next_node)
3780 g_assert (child_iter != NULL);
3782 num_chars += child_iter->num_chars;
3784 child_iter = child_iter->next;
3790 g_assert (iter != NULL);
3791 g_assert (iter == target_line->parent);
3793 /* Since we don't store char counts in lines, only in segments, we
3794 have to iterate over the lines adding up segment char counts
3795 until we find our line. */
3796 line = iter->children.line;
3797 while (line != target_line)
3799 g_assert (line != NULL);
3801 num_chars += _gtk_text_line_char_count (line);
3806 g_assert (line == target_line);
3812 _gtk_text_line_byte_to_segment (GtkTextLine *line,
3816 GtkTextLineSegment *seg;
3819 g_return_val_if_fail (line != NULL, NULL);
3821 offset = byte_offset;
3822 seg = line->segments;
3824 while (offset >= seg->byte_count)
3826 offset -= seg->byte_count;
3828 g_assert (seg != NULL); /* means an invalid byte index */
3832 *seg_offset = offset;
3838 _gtk_text_line_char_to_segment (GtkTextLine *line,
3842 GtkTextLineSegment *seg;
3845 g_return_val_if_fail (line != NULL, NULL);
3847 offset = char_offset;
3848 seg = line->segments;
3850 while (offset >= seg->char_count)
3852 offset -= seg->char_count;
3854 g_assert (seg != NULL); /* means an invalid char index */
3858 *seg_offset = offset;
3864 _gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3868 GtkTextLineSegment *seg;
3871 g_return_val_if_fail (line != NULL, NULL);
3873 offset = byte_offset;
3874 seg = line->segments;
3876 while (offset > 0 && offset >= seg->byte_count)
3878 offset -= seg->byte_count;
3880 g_assert (seg != NULL); /* means an invalid byte index */
3884 *seg_offset = offset;
3890 _gtk_text_line_char_to_any_segment (GtkTextLine *line,
3894 GtkTextLineSegment *seg;
3897 g_return_val_if_fail (line != NULL, NULL);
3899 offset = char_offset;
3900 seg = line->segments;
3902 while (offset > 0 && offset >= seg->char_count)
3904 offset -= seg->char_count;
3906 g_assert (seg != NULL); /* means an invalid byte index */
3910 *seg_offset = offset;
3916 _gtk_text_line_byte_to_char (GtkTextLine *line,
3920 GtkTextLineSegment *seg;
3922 g_return_val_if_fail (line != NULL, 0);
3923 g_return_val_if_fail (byte_offset >= 0, 0);
3926 seg = line->segments;
3927 while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3928 the next segment) */
3930 byte_offset -= seg->byte_count;
3931 char_offset += seg->char_count;
3933 g_assert (seg != NULL); /* our byte_index was bogus if this happens */
3936 g_assert (seg != NULL);
3938 /* Now byte_offset is the offset into the current segment,
3939 and char_offset is the start of the current segment.
3940 Optimize the case where no chars use > 1 byte */
3941 if (seg->byte_count == seg->char_count)
3942 return char_offset + byte_offset;
3945 if (seg->type == >k_text_char_type)
3946 return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3949 g_assert (seg->char_count == 1);
3950 g_assert (byte_offset == 0);
3958 _gtk_text_line_char_to_byte (GtkTextLine *line,
3961 g_warning ("FIXME not implemented");
3966 /* FIXME sync with char_locate (or figure out a clean
3967 way to merge the two functions) */
3969 _gtk_text_line_byte_locate (GtkTextLine *line,
3971 GtkTextLineSegment **segment,
3972 GtkTextLineSegment **any_segment,
3973 gint *seg_byte_offset,
3974 gint *line_byte_offset)
3976 GtkTextLineSegment *seg;
3977 GtkTextLineSegment *after_last_indexable;
3978 GtkTextLineSegment *last_indexable;
3982 g_return_val_if_fail (line != NULL, FALSE);
3983 g_return_val_if_fail (byte_offset >= 0, FALSE);
3986 *any_segment = NULL;
3989 offset = byte_offset;
3991 last_indexable = NULL;
3992 after_last_indexable = line->segments;
3993 seg = line->segments;
3995 /* The loop ends when we're inside a segment;
3996 last_indexable refers to the last segment
3997 we passed entirely. */
3998 while (seg && offset >= seg->byte_count)
4000 if (seg->char_count > 0)
4002 offset -= seg->byte_count;
4003 bytes_in_line += seg->byte_count;
4004 last_indexable = seg;
4005 after_last_indexable = last_indexable->next;
4013 /* We went off the end of the line */
4015 g_warning ("%s: byte index off the end of the line", G_STRLOC);
4022 if (after_last_indexable != NULL)
4023 *any_segment = after_last_indexable;
4025 *any_segment = *segment;
4028 /* Override any_segment if we're in the middle of a segment. */
4030 *any_segment = *segment;
4032 *seg_byte_offset = offset;
4034 g_assert (*segment != NULL);
4035 g_assert (*any_segment != NULL);
4036 g_assert (*seg_byte_offset < (*segment)->byte_count);
4038 *line_byte_offset = bytes_in_line + *seg_byte_offset;
4043 /* FIXME sync with byte_locate (or figure out a clean
4044 way to merge the two functions) */
4046 _gtk_text_line_char_locate (GtkTextLine *line,
4048 GtkTextLineSegment **segment,
4049 GtkTextLineSegment **any_segment,
4050 gint *seg_char_offset,
4051 gint *line_char_offset)
4053 GtkTextLineSegment *seg;
4054 GtkTextLineSegment *after_last_indexable;
4055 GtkTextLineSegment *last_indexable;
4059 g_return_val_if_fail (line != NULL, FALSE);
4060 g_return_val_if_fail (char_offset >= 0, FALSE);
4063 *any_segment = NULL;
4066 offset = char_offset;
4068 last_indexable = NULL;
4069 after_last_indexable = line->segments;
4070 seg = line->segments;
4072 /* The loop ends when we're inside a segment;
4073 last_indexable refers to the last segment
4074 we passed entirely. */
4075 while (seg && offset >= seg->char_count)
4077 if (seg->char_count > 0)
4079 offset -= seg->char_count;
4080 chars_in_line += seg->char_count;
4081 last_indexable = seg;
4082 after_last_indexable = last_indexable->next;
4090 /* end of the line */
4092 g_warning ("%s: char offset off the end of the line", G_STRLOC);
4099 if (after_last_indexable != NULL)
4100 *any_segment = after_last_indexable;
4102 *any_segment = *segment;
4105 /* Override any_segment if we're in the middle of a segment. */
4107 *any_segment = *segment;
4109 *seg_char_offset = offset;
4111 g_assert (*segment != NULL);
4112 g_assert (*any_segment != NULL);
4113 g_assert (*seg_char_offset < (*segment)->char_count);
4115 *line_char_offset = chars_in_line + *seg_char_offset;
4121 _gtk_text_line_byte_to_char_offsets (GtkTextLine *line,
4123 gint *line_char_offset,
4124 gint *seg_char_offset)
4126 GtkTextLineSegment *seg;
4129 g_return_if_fail (line != NULL);
4130 g_return_if_fail (byte_offset >= 0);
4132 *line_char_offset = 0;
4134 offset = byte_offset;
4135 seg = line->segments;
4137 while (offset >= seg->byte_count)
4139 offset -= seg->byte_count;
4140 *line_char_offset += seg->char_count;
4142 g_assert (seg != NULL); /* means an invalid char offset */
4145 g_assert (seg->char_count > 0); /* indexable. */
4147 /* offset is now the number of bytes into the current segment we
4148 * want to go. Count chars into the current segment.
4151 if (seg->type == >k_text_char_type)
4153 *seg_char_offset = g_utf8_strlen (seg->body.chars, offset);
4155 g_assert (*seg_char_offset < seg->char_count);
4157 *line_char_offset += *seg_char_offset;
4161 g_assert (offset == 0);
4162 *seg_char_offset = 0;
4167 _gtk_text_line_char_to_byte_offsets (GtkTextLine *line,
4169 gint *line_byte_offset,
4170 gint *seg_byte_offset)
4172 GtkTextLineSegment *seg;
4175 g_return_if_fail (line != NULL);
4176 g_return_if_fail (char_offset >= 0);
4178 *line_byte_offset = 0;
4180 offset = char_offset;
4181 seg = line->segments;
4183 while (offset >= seg->char_count)
4185 offset -= seg->char_count;
4186 *line_byte_offset += seg->byte_count;
4188 g_assert (seg != NULL); /* means an invalid char offset */
4191 g_assert (seg->char_count > 0); /* indexable. */
4193 /* offset is now the number of chars into the current segment we
4194 want to go. Count bytes into the current segment. */
4196 if (seg->type == >k_text_char_type)
4200 /* if in the last fourth of the segment walk backwards */
4201 if (seg->char_count - offset < seg->char_count / 4)
4202 p = g_utf8_offset_to_pointer (seg->body.chars + seg->byte_count,
4203 offset - seg->char_count);
4205 p = g_utf8_offset_to_pointer (seg->body.chars, offset);
4207 *seg_byte_offset = p - seg->body.chars;
4209 g_assert (*seg_byte_offset < seg->byte_count);
4211 *line_byte_offset += *seg_byte_offset;
4215 g_assert (offset == 0);
4216 *seg_byte_offset = 0;
4221 node_compare (GtkTextBTreeNode *lhs,
4222 GtkTextBTreeNode *rhs)
4224 GtkTextBTreeNode *iter;
4225 GtkTextBTreeNode *node;
4226 GtkTextBTreeNode *common_parent;
4227 GtkTextBTreeNode *parent_of_lower;
4228 GtkTextBTreeNode *parent_of_higher;
4229 gboolean lhs_is_lower;
4230 GtkTextBTreeNode *lower;
4231 GtkTextBTreeNode *higher;
4233 /* This function assumes that lhs and rhs are not underneath each
4240 if (lhs->level < rhs->level)
4242 lhs_is_lower = TRUE;
4248 lhs_is_lower = FALSE;
4253 /* Algorithm: find common parent of lhs/rhs. Save the child nodes
4254 * of the common parent we used to reach the common parent; the
4255 * ordering of these child nodes in the child list is the ordering
4259 /* Get on the same level (may be on same level already) */
4261 while (node->level < higher->level)
4262 node = node->parent;
4264 g_assert (node->level == higher->level);
4266 g_assert (node != higher); /* Happens if lower is underneath higher */
4268 /* Go up until we have two children with a common parent.
4270 parent_of_lower = node;
4271 parent_of_higher = higher;
4273 while (parent_of_lower->parent != parent_of_higher->parent)
4275 parent_of_lower = parent_of_lower->parent;
4276 parent_of_higher = parent_of_higher->parent;
4279 g_assert (parent_of_lower->parent == parent_of_higher->parent);
4281 common_parent = parent_of_lower->parent;
4283 g_assert (common_parent != NULL);
4285 /* See which is first in the list of common_parent's children */
4286 iter = common_parent->children.node;
4287 while (iter != NULL)
4289 if (iter == parent_of_higher)
4291 /* higher is less than lower */
4294 return 1; /* lhs > rhs */
4298 else if (iter == parent_of_lower)
4300 /* lower is less than higher */
4303 return -1; /* lhs < rhs */
4311 g_assert_not_reached ();
4315 /* remember that tag == NULL means "any tag" */
4317 _gtk_text_line_next_could_contain_tag (GtkTextLine *line,
4321 GtkTextBTreeNode *node;
4322 GtkTextTagInfo *info;
4323 gboolean below_tag_root;
4325 g_return_val_if_fail (line != NULL, NULL);
4327 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4328 _gtk_text_btree_check (tree);
4332 /* Right now we can only offer linear-search if the user wants
4333 * to know about any tag toggle at all.
4335 return _gtk_text_line_next_excluding_last (line);
4338 /* Our tag summaries only have node precision, not line
4339 * precision. This means that if any line under a node could contain a
4340 * tag, then any of the others could also contain a tag.
4342 * In the future we could have some mechanism to keep track of how
4343 * many toggles we've found under a node so far, since we have a
4344 * count of toggles under the node. But for now I'm going with KISS.
4347 /* return same-node line, if any. */
4351 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4355 if (info->tag_root == NULL)
4358 if (info->tag_root == line->parent)
4359 return NULL; /* we were at the last line under the tag root */
4361 /* We need to go up out of this node, and on to the next one with
4362 toggles for the target tag. If we're below the tag root, we need to
4363 find the next node below the tag root that has tag summaries. If
4364 we're not below the tag root, we need to see if the tag root is
4365 after us in the tree, and if so, return the first line underneath
4368 node = line->parent;
4369 below_tag_root = FALSE;
4370 while (node != NULL)
4372 if (node == info->tag_root)
4374 below_tag_root = TRUE;
4378 node = node->parent;
4383 node = line->parent;
4384 while (node != info->tag_root)
4386 if (node->next == NULL)
4387 node = node->parent;
4392 if (gtk_text_btree_node_has_tag (node, tag))
4402 ordering = node_compare (line->parent, info->tag_root);
4406 /* Tag root is ahead of us, so search there. */
4407 node = info->tag_root;
4412 /* Tag root is after us, so no more lines that
4413 * could contain the tag.
4418 g_assert_not_reached ();
4423 g_assert (node != NULL);
4425 /* We have to find the first sub-node of this node that contains
4429 while (node->level > 0)
4431 g_assert (node != NULL); /* If this fails, it likely means an
4432 incorrect tag summary led us on a
4433 wild goose chase down this branch of
4435 node = node->children.node;
4436 while (node != NULL)
4438 if (gtk_text_btree_node_has_tag (node, tag))
4444 g_assert (node != NULL);
4445 g_assert (node->level == 0);
4447 return node->children.line;
4451 prev_line_under_node (GtkTextBTreeNode *node,
4456 prev = node->children.line;
4462 while (prev->next != line)
4472 _gtk_text_line_previous_could_contain_tag (GtkTextLine *line,
4476 GtkTextBTreeNode *node;
4477 GtkTextBTreeNode *found_node = NULL;
4478 GtkTextTagInfo *info;
4479 gboolean below_tag_root;
4481 GtkTextBTreeNode *line_ancestor;
4482 GtkTextBTreeNode *line_ancestor_parent;
4484 /* See next_could_contain_tag () for more extensive comments
4485 * on what's going on here.
4488 g_return_val_if_fail (line != NULL, NULL);
4490 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4491 _gtk_text_btree_check (tree);
4495 /* Right now we can only offer linear-search if the user wants
4496 * to know about any tag toggle at all.
4498 return _gtk_text_line_previous (line);
4501 /* Return same-node line, if any. */
4502 prev = prev_line_under_node (line->parent, line);
4506 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4510 if (info->tag_root == NULL)
4513 if (info->tag_root == line->parent)
4514 return NULL; /* we were at the first line under the tag root */
4516 /* Are we below the tag root */
4517 node = line->parent;
4518 below_tag_root = FALSE;
4519 while (node != NULL)
4521 if (node == info->tag_root)
4523 below_tag_root = TRUE;
4527 node = node->parent;
4532 /* Look for a previous node under this tag root that has our
4536 /* this assertion holds because line->parent is not the
4537 * tag root, we are below the tag root, and the tag
4540 g_assert (line->parent->parent != NULL);
4542 line_ancestor = line->parent;
4543 line_ancestor_parent = line->parent->parent;
4545 while (line_ancestor != info->tag_root)
4547 GSList *child_nodes = NULL;
4550 /* Create reverse-order list of nodes before
4553 if (line_ancestor_parent != NULL)
4554 node = line_ancestor_parent->children.node;
4556 node = line_ancestor;
4558 while (node != line_ancestor && node != NULL)
4560 child_nodes = g_slist_prepend (child_nodes, node);
4565 /* Try to find a node with our tag on it in the list */
4569 GtkTextBTreeNode *this_node = tmp->data;
4571 g_assert (this_node != line_ancestor);
4573 if (gtk_text_btree_node_has_tag (this_node, tag))
4575 found_node = this_node;
4576 g_slist_free (child_nodes);
4580 tmp = g_slist_next (tmp);
4583 g_slist_free (child_nodes);
4585 /* Didn't find anything on this level; go up one level. */
4586 line_ancestor = line_ancestor_parent;
4587 line_ancestor_parent = line_ancestor->parent;
4597 ordering = node_compare (line->parent, info->tag_root);
4601 /* Tag root is ahead of us, so no more lines
4608 /* Tag root is after us, so grab last tagged
4609 * line underneath the tag root.
4611 found_node = info->tag_root;
4615 g_assert_not_reached ();
4620 g_assert (found_node != NULL);
4622 /* We have to find the last sub-node of this node that contains
4627 while (node->level > 0)
4629 GSList *child_nodes = NULL;
4631 g_assert (node != NULL); /* If this fails, it likely means an
4632 incorrect tag summary led us on a
4633 wild goose chase down this branch of
4636 node = node->children.node;
4637 while (node != NULL)
4639 child_nodes = g_slist_prepend (child_nodes, node);
4643 node = NULL; /* detect failure to find a child node. */
4646 while (iter != NULL)
4648 if (gtk_text_btree_node_has_tag (iter->data, tag))
4650 /* recurse into this node. */
4655 iter = g_slist_next (iter);
4658 g_slist_free (child_nodes);
4660 g_assert (node != NULL);
4663 g_assert (node != NULL);
4664 g_assert (node->level == 0);
4666 /* this assertion is correct, but slow. */
4667 /* g_assert (node_compare (node, line->parent) < 0); */
4669 /* Return last line in this node. */
4671 prev = node->children.line;
4679 * Non-public function implementations
4683 summary_list_destroy (Summary *summary)
4685 g_slice_free_chain (Summary, summary, next);
4689 get_last_line (GtkTextBTree *tree)
4691 if (tree->last_line_stamp != tree->chars_changed_stamp)
4697 n_lines = _gtk_text_btree_line_count (tree);
4699 g_assert (n_lines >= 1); /* num_lines doesn't return bogus last line. */
4701 line = _gtk_text_btree_get_line (tree, n_lines, &real_line);
4703 tree->last_line_stamp = tree->chars_changed_stamp;
4704 tree->last_line = line;
4707 return tree->last_line;
4715 gtk_text_line_new (void)
4719 line = g_new0(GtkTextLine, 1);
4720 line->dir_strong = PANGO_DIRECTION_NEUTRAL;
4721 line->dir_propagated_forward = PANGO_DIRECTION_NEUTRAL;
4722 line->dir_propagated_back = PANGO_DIRECTION_NEUTRAL;
4728 gtk_text_line_destroy (GtkTextBTree *tree, GtkTextLine *line)
4730 GtkTextLineData *ld;
4731 GtkTextLineData *next;
4733 g_return_if_fail (line != NULL);
4740 view = gtk_text_btree_get_view (tree, ld->view_id);
4742 g_assert (view != NULL);
4745 gtk_text_layout_free_line_data (view->layout, line, ld);
4754 gtk_text_line_set_parent (GtkTextLine *line,
4755 GtkTextBTreeNode *node)
4757 if (line->parent == node)
4759 line->parent = node;
4760 gtk_text_btree_node_invalidate_upward (node, NULL);
4764 cleanup_line (GtkTextLine *line)
4766 GtkTextLineSegment *seg, **prev_p;
4770 * Make a pass over all of the segments in the line, giving each
4771 * a chance to clean itself up. This could potentially change
4772 * the structure of the line, e.g. by merging two segments
4773 * together or having two segments cancel themselves; if so,
4774 * then repeat the whole process again, since the first structure
4775 * change might make other structure changes possible. Repeat
4776 * until eventually there are no changes.
4783 prev_p = &line->segments;
4784 for (seg = *prev_p; seg != NULL; seg = *prev_p)
4786 if (seg->type->cleanupFunc != NULL)
4788 *prev_p = (*seg->type->cleanupFunc)(seg, line);
4796 prev_p = &(*prev_p)->next;
4806 node_data_new (gpointer view_id)
4810 nd = g_slice_new (NodeData);
4812 nd->view_id = view_id;
4822 node_data_destroy (NodeData *nd)
4824 g_slice_free (NodeData, nd);
4828 node_data_list_destroy (NodeData *nd)
4830 g_slice_free_chain (NodeData, nd, next);
4834 node_data_find (NodeData *nd,
4839 if (nd->view_id == view_id)
4847 summary_destroy (Summary *summary)
4849 /* Fill with error-triggering garbage */
4850 summary->info = (void*)0x1;
4851 summary->toggle_count = 567;
4852 summary->next = (void*)0x1;
4853 g_slice_free (Summary, summary);
4856 static GtkTextBTreeNode*
4857 gtk_text_btree_node_new (void)
4859 GtkTextBTreeNode *node;
4861 node = g_new (GtkTextBTreeNode, 1);
4863 node->node_data = NULL;
4869 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
4870 GtkTextTagInfo *info,
4875 summary = node->summary;
4876 while (summary != NULL)
4878 if (summary->info == info)
4880 summary->toggle_count += adjust;
4884 summary = summary->next;
4887 if (summary == NULL)
4889 /* didn't find a summary for our tag. */
4890 g_return_if_fail (adjust > 0);
4891 summary = g_slice_new (Summary);
4892 summary->info = info;
4893 summary->toggle_count = adjust;
4894 summary->next = node->summary;
4895 node->summary = summary;
4899 /* Note that the tag root and above do not have summaries
4900 for the tag; only nodes below the tag root have
4903 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4907 summary = node->summary;
4908 while (summary != NULL)
4911 summary->info->tag == tag)
4914 summary = summary->next;
4920 /* Add node and all children to the damage region. */
4922 gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node)
4926 nd = node->node_data;
4933 if (node->level == 0)
4937 line = node->children.line;
4938 while (line != NULL)
4940 GtkTextLineData *ld;
4954 GtkTextBTreeNode *child;
4956 child = node->children.node;
4958 while (child != NULL)
4960 gtk_text_btree_node_invalidate_downward (child);
4962 child = child->next;
4968 gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node, gpointer view_id)
4970 GtkTextBTreeNode *iter;
4973 while (iter != NULL)
4979 nd = node_data_find (iter->node_data, view_id);
4981 if (nd == NULL || !nd->valid)
4982 break; /* Once a node is invalid, we know its parents are as well. */
4988 gboolean should_continue = FALSE;
4990 nd = iter->node_data;
4995 should_continue = TRUE;
5002 if (!should_continue)
5003 break; /* This node was totally invalidated, so are its
5007 iter = iter->parent;
5013 * _gtk_text_btree_is_valid:
5014 * @tree: a #GtkTextBTree
5015 * @view_id: ID for the view
5017 * Check to see if the entire #GtkTextBTree is valid or not for
5020 * Return value: %TRUE if the entire #GtkTextBTree is valid
5023 _gtk_text_btree_is_valid (GtkTextBTree *tree,
5027 g_return_val_if_fail (tree != NULL, FALSE);
5029 nd = node_data_find (tree->root_node->node_data, view_id);
5030 return (nd && nd->valid);
5033 typedef struct _ValidateState ValidateState;
5035 struct _ValidateState
5037 gint remaining_pixels;
5038 gboolean in_validation;
5045 gtk_text_btree_node_validate (BTreeView *view,
5046 GtkTextBTreeNode *node,
5048 ValidateState *state)
5050 gint node_valid = TRUE;
5051 gint node_width = 0;
5052 gint node_height = 0;
5054 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5055 g_return_if_fail (!nd->valid);
5057 if (node->level == 0)
5059 GtkTextLine *line = node->children.line;
5060 GtkTextLineData *ld;
5062 /* Iterate over leading valid lines */
5063 while (line != NULL)
5065 ld = _gtk_text_line_get_data (line, view_id);
5067 if (!ld || !ld->valid)
5069 else if (state->in_validation)
5071 state->in_validation = FALSE;
5076 state->y += ld->height;
5077 node_width = MAX (ld->width, node_width);
5078 node_height += ld->height;
5084 state->in_validation = TRUE;
5086 /* Iterate over invalid lines */
5087 while (line != NULL)
5089 ld = _gtk_text_line_get_data (line, view_id);
5091 if (ld && ld->valid)
5096 state->old_height += ld->height;
5097 ld = gtk_text_layout_wrap (view->layout, line, ld);
5098 state->new_height += ld->height;
5100 node_width = MAX (ld->width, node_width);
5101 node_height += ld->height;
5103 state->remaining_pixels -= ld->height;
5104 if (state->remaining_pixels <= 0)
5114 /* Iterate over the remaining lines */
5115 while (line != NULL)
5117 ld = _gtk_text_line_get_data (line, view_id);
5118 state->in_validation = FALSE;
5120 if (!ld || !ld->valid)
5125 node_width = MAX (ld->width, node_width);
5126 node_height += ld->height;
5134 GtkTextBTreeNode *child;
5137 child = node->children.node;
5139 /* Iterate over leading valid nodes */
5142 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5144 if (!child_nd->valid)
5146 else if (state->in_validation)
5148 state->in_validation = FALSE;
5153 state->y += child_nd->height;
5154 node_width = MAX (node_width, child_nd->width);
5155 node_height += child_nd->height;
5158 child = child->next;
5161 /* Iterate over invalid nodes */
5164 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5166 if (child_nd->valid)
5170 gtk_text_btree_node_validate (view, child, view_id, state);
5172 if (!child_nd->valid)
5174 node_width = MAX (node_width, child_nd->width);
5175 node_height += child_nd->height;
5177 if (!state->in_validation || state->remaining_pixels <= 0)
5179 child = child->next;
5184 child = child->next;
5187 /* Iterate over the remaining lines */
5190 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5191 state->in_validation = FALSE;
5193 if (!child_nd->valid)
5196 node_width = MAX (child_nd->width, node_width);
5197 node_height += child_nd->height;
5199 child = child->next;
5203 nd->width = node_width;
5204 nd->height = node_height;
5205 nd->valid = node_valid;
5209 * _gtk_text_btree_validate:
5210 * @tree: a #GtkTextBTree
5212 * @max_pixels: the maximum number of pixels to validate. (No more
5213 * than one paragraph beyond this limit will be validated)
5214 * @y: location to store starting y coordinate of validated region
5215 * @old_height: location to store old height of validated region
5216 * @new_height: location to store new height of validated region
5218 * Validate a single contiguous invalid region of a #GtkTextBTree for
5221 * Return value: %TRUE if a region has been validated, %FALSE if the
5222 * entire tree was already valid.
5225 _gtk_text_btree_validate (GtkTextBTree *tree,
5234 g_return_val_if_fail (tree != NULL, FALSE);
5236 view = gtk_text_btree_get_view (tree, view_id);
5237 g_return_val_if_fail (view != NULL, FALSE);
5239 if (!_gtk_text_btree_is_valid (tree, view_id))
5241 ValidateState state;
5243 state.remaining_pixels = max_pixels;
5244 state.in_validation = FALSE;
5246 state.old_height = 0;
5247 state.new_height = 0;
5249 gtk_text_btree_node_validate (view,
5256 *old_height = state.old_height;
5258 *new_height = state.new_height;
5260 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5261 _gtk_text_btree_check (tree);
5270 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
5274 gboolean *valid_out)
5278 gboolean valid = TRUE;
5280 if (node->level == 0)
5282 GtkTextLine *line = node->children.line;
5284 while (line != NULL)
5286 GtkTextLineData *ld = _gtk_text_line_get_data (line, view_id);
5288 if (!ld || !ld->valid)
5293 width = MAX (ld->width, width);
5294 height += ld->height;
5302 GtkTextBTreeNode *child = node->children.node;
5306 NodeData *child_nd = node_data_find (child->node_data, view_id);
5308 if (!child_nd || !child_nd->valid)
5313 width = MAX (child_nd->width, width);
5314 height += child_nd->height;
5317 child = child->next;
5322 *height_out = height;
5327 /* Recompute the validity and size of the view data for a given
5328 * view at this node from the immediate children of the node
5331 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
5334 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5339 gtk_text_btree_node_compute_view_aggregates (node, view_id,
5340 &width, &height, &valid);
5342 nd->height = height;
5349 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
5354 gtk_text_btree_node_check_valid (node, view_id);
5355 node = node->parent;
5360 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
5363 if (node->level == 0)
5365 return gtk_text_btree_node_check_valid (node, view_id);
5369 GtkTextBTreeNode *child = node->children.node;
5371 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5379 NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
5381 if (!child_nd->valid)
5383 nd->width = MAX (child_nd->width, nd->width);
5384 nd->height += child_nd->height;
5386 child = child->next;
5395 * _gtk_text_btree_validate_line:
5396 * @tree: a #GtkTextBTree
5397 * @line: line to validate
5398 * @view_id: view ID for the view to validate
5400 * Revalidate a single line of the btree for the given view, propagate
5401 * results up through the entire tree.
5404 _gtk_text_btree_validate_line (GtkTextBTree *tree,
5408 GtkTextLineData *ld;
5411 g_return_if_fail (tree != NULL);
5412 g_return_if_fail (line != NULL);
5414 view = gtk_text_btree_get_view (tree, view_id);
5415 g_return_if_fail (view != NULL);
5417 ld = _gtk_text_line_get_data (line, view_id);
5418 if (!ld || !ld->valid)
5420 ld = gtk_text_layout_wrap (view->layout, line, ld);
5422 gtk_text_btree_node_check_valid_upward (line->parent, view_id);
5427 gtk_text_btree_node_remove_view (BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
5429 if (node->level == 0)
5433 line = node->children.line;
5434 while (line != NULL)
5436 GtkTextLineData *ld;
5438 ld = _gtk_text_line_remove_data (line, view_id);
5441 gtk_text_layout_free_line_data (view->layout, line, ld);
5448 GtkTextBTreeNode *child;
5450 child = node->children.node;
5452 while (child != NULL)
5455 gtk_text_btree_node_remove_view (view, child, view_id);
5457 child = child->next;
5461 gtk_text_btree_node_remove_data (node, view_id);
5465 gtk_text_btree_node_destroy (GtkTextBTree *tree, GtkTextBTreeNode *node)
5467 if (node->level == 0)
5470 GtkTextLineSegment *seg;
5472 while (node->children.line != NULL)
5474 line = node->children.line;
5475 node->children.line = line->next;
5476 while (line->segments != NULL)
5478 seg = line->segments;
5479 line->segments = seg->next;
5481 (*seg->type->deleteFunc) (seg, line, TRUE);
5483 gtk_text_line_destroy (tree, line);
5488 GtkTextBTreeNode *childPtr;
5490 while (node->children.node != NULL)
5492 childPtr = node->children.node;
5493 node->children.node = childPtr->next;
5494 gtk_text_btree_node_destroy (tree, childPtr);
5498 gtk_text_btree_node_free_empty (tree, node);
5502 gtk_text_btree_node_free_empty (GtkTextBTree *tree,
5503 GtkTextBTreeNode *node)
5505 g_return_if_fail ((node->level > 0 && node->children.node == NULL) ||
5506 (node->level == 0 && node->children.line == NULL));
5508 summary_list_destroy (node->summary);
5509 node_data_list_destroy (node->node_data);
5514 gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node, gpointer view_id)
5518 nd = node->node_data;
5521 if (nd->view_id == view_id)
5529 nd = node_data_new (view_id);
5531 if (node->node_data)
5532 nd->next = node->node_data;
5534 node->node_data = nd;
5541 gtk_text_btree_node_remove_data (GtkTextBTreeNode *node, gpointer view_id)
5547 nd = node->node_data;
5550 if (nd->view_id == view_id)
5561 prev->next = nd->next;
5563 if (node->node_data == nd)
5564 node->node_data = nd->next;
5568 node_data_destroy (nd);
5572 gtk_text_btree_node_get_size (GtkTextBTreeNode *node, gpointer view_id,
5573 gint *width, gint *height)
5577 g_return_if_fail (width != NULL);
5578 g_return_if_fail (height != NULL);
5580 nd = gtk_text_btree_node_ensure_data (node, view_id);
5585 *height = nd->height;
5588 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5589 * here isn't quite right, since for a lot of operations we want to
5590 * know which children of the common parent correspond to the two nodes
5591 * (e.g., when computing the order of two iters)
5593 static GtkTextBTreeNode *
5594 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5595 GtkTextBTreeNode *node2)
5597 while (node1->level < node2->level)
5598 node1 = node1->parent;
5599 while (node2->level < node1->level)
5600 node2 = node2->parent;
5601 while (node1 != node2)
5603 node1 = node1->parent;
5604 node2 = node2->parent;
5615 gtk_text_btree_get_view (GtkTextBTree *tree, gpointer view_id)
5620 while (view != NULL)
5622 if (view->view_id == view_id)
5631 get_tree_bounds (GtkTextBTree *tree,
5635 _gtk_text_btree_get_iter_at_line_char (tree, start, 0, 0);
5636 _gtk_text_btree_get_end_iter (tree, end);
5640 tag_changed_cb (GtkTextTagTable *table,
5642 gboolean size_changed,
5647 /* We need to queue a relayout on all regions that are tagged with
5654 if (_gtk_text_btree_get_iter_at_first_toggle (tree, &start, tag))
5656 /* Must be a last toggle if there was a first one. */
5657 _gtk_text_btree_get_iter_at_last_toggle (tree, &end, tag);
5658 DV (g_print ("invalidating due to tag change (%s)\n", G_STRLOC));
5659 _gtk_text_btree_invalidate_region (tree, &start, &end, FALSE);
5665 /* We only need to queue a redraw, not a relayout */
5670 while (view != NULL)
5674 _gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5675 gtk_text_layout_changed (view->layout, 0, height, height);
5683 _gtk_text_btree_notify_will_remove_tag (GtkTextBTree *tree,
5686 /* Remove the tag from the tree */
5691 get_tree_bounds (tree, &start, &end);
5693 _gtk_text_btree_tag (&start, &end, tag, FALSE);
5694 gtk_text_btree_remove_tag_info (tree, tag);
5698 /* Rebalance the out-of-whack node "node" */
5700 gtk_text_btree_rebalance (GtkTextBTree *tree,
5701 GtkTextBTreeNode *node)
5704 * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5705 * up through the tree one GtkTextBTreeNode at a time until the root
5706 * GtkTextBTreeNode has been processed.
5709 while (node != NULL)
5711 GtkTextBTreeNode *new_node, *child;
5716 * Check to see if the GtkTextBTreeNode has too many children. If it does,
5717 * then split off all but the first MIN_CHILDREN into a separate
5718 * GtkTextBTreeNode following the original one. Then repeat until the
5719 * GtkTextBTreeNode has a decent size.
5722 if (node->num_children > MAX_CHILDREN)
5727 * If the GtkTextBTreeNode being split is the root
5728 * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5732 if (node->parent == NULL)
5734 new_node = gtk_text_btree_node_new ();
5735 new_node->parent = NULL;
5736 new_node->next = NULL;
5737 new_node->summary = NULL;
5738 new_node->level = node->level + 1;
5739 new_node->children.node = node;
5740 recompute_node_counts (tree, new_node);
5741 tree->root_node = new_node;
5743 new_node = gtk_text_btree_node_new ();
5744 new_node->parent = node->parent;
5745 new_node->next = node->next;
5746 node->next = new_node;
5747 new_node->summary = NULL;
5748 new_node->level = node->level;
5749 new_node->num_children = node->num_children - MIN_CHILDREN;
5750 if (node->level == 0)
5752 for (i = MIN_CHILDREN-1,
5753 line = node->children.line;
5754 i > 0; i--, line = line->next)
5756 /* Empty loop body. */
5758 new_node->children.line = line->next;
5763 for (i = MIN_CHILDREN-1,
5764 child = node->children.node;
5765 i > 0; i--, child = child->next)
5767 /* Empty loop body. */
5769 new_node->children.node = child->next;
5772 recompute_node_counts (tree, node);
5773 node->parent->num_children++;
5775 if (node->num_children <= MAX_CHILDREN)
5777 recompute_node_counts (tree, node);
5783 while (node->num_children < MIN_CHILDREN)
5785 GtkTextBTreeNode *other;
5786 GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5787 GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5788 int total_children, first_children, i;
5791 * Too few children for this GtkTextBTreeNode. If this is the root then,
5792 * it's OK for it to have less than MIN_CHILDREN children
5793 * as long as it's got at least two. If it has only one
5794 * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5795 * the tree and use its child as the new root.
5798 if (node->parent == NULL)
5800 if ((node->num_children == 1) && (node->level > 0))
5802 tree->root_node = node->children.node;
5803 tree->root_node->parent = NULL;
5805 node->children.node = NULL;
5806 gtk_text_btree_node_free_empty (tree, node);
5812 * Not the root. Make sure that there are siblings to
5816 if (node->parent->num_children < 2)
5818 gtk_text_btree_rebalance (tree, node->parent);
5823 * Find a sibling neighbor to borrow from, and arrange for
5824 * node to be the earlier of the pair.
5827 if (node->next == NULL)
5829 for (other = node->parent->children.node;
5830 other->next != node;
5831 other = other->next)
5833 /* Empty loop body. */
5840 * We're going to either merge the two siblings together
5841 * into one GtkTextBTreeNode or redivide the children among them to
5842 * balance their loads. As preparation, join their two
5843 * child lists into a single list and remember the half-way
5844 * point in the list.
5847 total_children = node->num_children + other->num_children;
5848 first_children = total_children/2;
5849 if (node->children.node == NULL)
5851 node->children = other->children;
5852 other->children.node = NULL;
5853 other->children.line = NULL;
5855 if (node->level == 0)
5859 for (line = node->children.line, i = 1;
5861 line = line->next, i++)
5863 if (i == first_children)
5868 line->next = other->children.line;
5869 while (i <= first_children)
5878 GtkTextBTreeNode *child;
5880 for (child = node->children.node, i = 1;
5881 child->next != NULL;
5882 child = child->next, i++)
5884 if (i <= first_children)
5886 if (i == first_children)
5888 halfwaynode = child;
5892 child->next = other->children.node;
5893 while (i <= first_children)
5895 halfwaynode = child;
5896 child = child->next;
5902 * If the two siblings can simply be merged together, do it.
5905 if (total_children <= MAX_CHILDREN)
5907 recompute_node_counts (tree, node);
5908 node->next = other->next;
5909 node->parent->num_children--;
5911 other->children.node = NULL;
5912 other->children.line = NULL;
5913 gtk_text_btree_node_free_empty (tree, other);
5918 * The siblings can't be merged, so just divide their
5919 * children evenly between them.
5922 if (node->level == 0)
5924 other->children.line = halfwayline->next;
5925 halfwayline->next = NULL;
5929 other->children.node = halfwaynode->next;
5930 halfwaynode->next = NULL;
5933 recompute_node_counts (tree, node);
5934 recompute_node_counts (tree, other);
5937 node = node->parent;
5942 post_insert_fixup (GtkTextBTree *tree,
5944 gint line_count_delta,
5945 gint char_count_delta)
5948 GtkTextBTreeNode *node;
5951 * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5952 * point, then rebalance the tree if necessary.
5955 for (node = line->parent ; node != NULL;
5956 node = node->parent)
5958 node->num_lines += line_count_delta;
5959 node->num_chars += char_count_delta;
5961 node = line->parent;
5962 node->num_children += line_count_delta;
5964 if (node->num_children > MAX_CHILDREN)
5966 gtk_text_btree_rebalance (tree, node);
5969 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5970 _gtk_text_btree_check (tree);
5973 static GtkTextTagInfo*
5974 gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
5977 GtkTextTagInfo *info;
5981 list = tree->tag_infos;
5982 while (list != NULL)
5985 if (info->tag == tag)
5988 list = g_slist_next (list);
5994 static GtkTextTagInfo*
5995 gtk_text_btree_get_tag_info (GtkTextBTree *tree,
5998 GtkTextTagInfo *info;
6000 info = gtk_text_btree_get_existing_tag_info (tree, tag);
6004 /* didn't find it, create. */
6006 info = g_slice_new (GtkTextTagInfo);
6010 info->tag_root = NULL;
6011 info->toggle_count = 0;
6013 tree->tag_infos = g_slist_prepend (tree->tag_infos, info);
6016 g_print ("Created tag info %p for tag %s(%p)\n",
6017 info, info->tag->name ? info->tag->name : "anon",
6026 gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
6029 GtkTextTagInfo *info;
6034 list = tree->tag_infos;
6035 while (list != NULL)
6038 if (info->tag == tag)
6041 g_print ("Removing tag info %p for tag %s(%p)\n",
6042 info, info->tag->name ? info->tag->name : "anon",
6048 prev->next = list->next;
6052 tree->tag_infos = list->next;
6055 g_slist_free (list);
6057 g_object_unref (info->tag);
6059 g_slice_free (GtkTextTagInfo, info);
6064 list = g_slist_next (list);
6069 recompute_level_zero_counts (GtkTextBTreeNode *node)
6072 GtkTextLineSegment *seg;
6074 g_assert (node->level == 0);
6076 line = node->children.line;
6077 while (line != NULL)
6079 node->num_children++;
6082 if (line->parent != node)
6083 gtk_text_line_set_parent (line, node);
6085 seg = line->segments;
6089 node->num_chars += seg->char_count;
6091 if (((seg->type != >k_text_toggle_on_type)
6092 && (seg->type != >k_text_toggle_off_type))
6093 || !(seg->body.toggle.inNodeCounts))
6099 GtkTextTagInfo *info;
6101 info = seg->body.toggle.info;
6103 gtk_text_btree_node_adjust_toggle_count (node, info, 1);
6114 recompute_level_nonzero_counts (GtkTextBTreeNode *node)
6117 GtkTextBTreeNode *child;
6119 g_assert (node->level > 0);
6121 child = node->children.node;
6122 while (child != NULL)
6124 node->num_children += 1;
6125 node->num_lines += child->num_lines;
6126 node->num_chars += child->num_chars;
6128 if (child->parent != node)
6130 child->parent = node;
6131 gtk_text_btree_node_invalidate_upward (node, NULL);
6134 summary = child->summary;
6135 while (summary != NULL)
6137 gtk_text_btree_node_adjust_toggle_count (node,
6139 summary->toggle_count);
6141 summary = summary->next;
6144 child = child->next;
6149 *----------------------------------------------------------------------
6151 * recompute_node_counts --
6153 * This procedure is called to recompute all the counts in a GtkTextBTreeNode
6154 * (tags, child information, etc.) by scanning the information in
6155 * its descendants. This procedure is called during rebalancing
6156 * when a GtkTextBTreeNode's child structure has changed.
6162 * The tag counts for node are modified to reflect its current
6163 * child structure, as are its num_children, num_lines, num_chars fields.
6164 * Also, all of the childrens' parent fields are made to point
6167 *----------------------------------------------------------------------
6171 recompute_node_counts (GtkTextBTree *tree, GtkTextBTreeNode *node)
6174 Summary *summary, *summary2;
6177 * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
6178 * the existing Summary records (most of them will probably be reused).
6181 summary = node->summary;
6182 while (summary != NULL)
6184 summary->toggle_count = 0;
6185 summary = summary->next;
6188 node->num_children = 0;
6189 node->num_lines = 0;
6190 node->num_chars = 0;
6193 * Scan through the children, adding the childrens' tag counts into
6194 * the GtkTextBTreeNode's tag counts and adding new Summary structures if
6198 if (node->level == 0)
6199 recompute_level_zero_counts (node);
6201 recompute_level_nonzero_counts (node);
6206 gtk_text_btree_node_check_valid (node, view->view_id);
6211 * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
6212 * records that still have a zero count, or that have all the toggles.
6213 * The GtkTextBTreeNode with the children that account for all the tags toggles
6214 * have no summary information, and they become the tag_root for the tag.
6218 for (summary = node->summary; summary != NULL; )
6220 if (summary->toggle_count > 0 &&
6221 summary->toggle_count < summary->info->toggle_count)
6223 if (node->level == summary->info->tag_root->level)
6226 * The tag's root GtkTextBTreeNode split and some toggles left.
6227 * The tag root must move up a level.
6229 summary->info->tag_root = node->parent;
6232 summary = summary->next;
6235 if (summary->toggle_count == summary->info->toggle_count)
6238 * A GtkTextBTreeNode merge has collected all the toggles under
6239 * one GtkTextBTreeNode. Push the root down to this level.
6241 summary->info->tag_root = node;
6243 if (summary2 != NULL)
6245 summary2->next = summary->next;
6246 summary_destroy (summary);
6247 summary = summary2->next;
6251 node->summary = summary->next;
6252 summary_destroy (summary);
6253 summary = node->summary;
6259 _gtk_change_node_toggle_count (GtkTextBTreeNode *node,
6260 GtkTextTagInfo *info,
6261 gint delta) /* may be negative */
6263 Summary *summary, *prevPtr;
6264 GtkTextBTreeNode *node2Ptr;
6265 int rootLevel; /* Level of original tag root */
6267 info->toggle_count += delta;
6269 if (info->tag_root == (GtkTextBTreeNode *) NULL)
6271 info->tag_root = node;
6276 * Note the level of the existing root for the tag so we can detect
6277 * if it needs to be moved because of the toggle count change.
6280 rootLevel = info->tag_root->level;
6283 * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
6284 * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
6288 for ( ; node != info->tag_root; node = node->parent)
6291 * See if there's already an entry for this tag for this GtkTextBTreeNode. If so,
6292 * perhaps all we have to do is adjust its count.
6295 for (prevPtr = NULL, summary = node->summary;
6297 prevPtr = summary, summary = summary->next)
6299 if (summary->info == info)
6304 if (summary != NULL)
6306 summary->toggle_count += delta;
6307 if (summary->toggle_count > 0 &&
6308 summary->toggle_count < info->toggle_count)
6312 if (summary->toggle_count != 0)
6315 * Should never find a GtkTextBTreeNode with max toggle count at this
6316 * point (there shouldn't have been a summary entry in the
6320 g_error ("%s: bad toggle count (%d) max (%d)",
6321 G_STRLOC, summary->toggle_count, info->toggle_count);
6325 * Zero toggle count; must remove this tag from the list.
6328 if (prevPtr == NULL)
6330 node->summary = summary->next;
6334 prevPtr->next = summary->next;
6336 summary_destroy (summary);
6341 * This tag isn't currently in the summary information list.
6344 if (rootLevel == node->level)
6348 * The old tag root is at the same level in the tree as this
6349 * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode. Move the tag root up
6350 * a level, in the hopes that it will now cover this GtkTextBTreeNode
6351 * as well as the old root (if not, we'll move it up again
6352 * the next time through the loop). To push it up one level
6353 * we copy the original toggle count into the summary
6354 * information at the old root and change the root to its
6355 * parent GtkTextBTreeNode.
6358 GtkTextBTreeNode *rootnode = info->tag_root;
6359 summary = g_slice_new (Summary);
6360 summary->info = info;
6361 summary->toggle_count = info->toggle_count - delta;
6362 summary->next = rootnode->summary;
6363 rootnode->summary = summary;
6364 rootnode = rootnode->parent;
6365 rootLevel = rootnode->level;
6366 info->tag_root = rootnode;
6368 summary = g_slice_new (Summary);
6369 summary->info = info;
6370 summary->toggle_count = delta;
6371 summary->next = node->summary;
6372 node->summary = summary;
6377 * If we've decremented the toggle count, then it may be necessary
6378 * to push the tag root down one or more levels.
6385 if (info->toggle_count == 0)
6387 info->tag_root = (GtkTextBTreeNode *) NULL;
6390 node = info->tag_root;
6391 while (node->level > 0)
6394 * See if a single child GtkTextBTreeNode accounts for all of the tag's
6395 * toggles. If so, push the root down one level.
6398 for (node2Ptr = node->children.node;
6399 node2Ptr != (GtkTextBTreeNode *)NULL ;
6400 node2Ptr = node2Ptr->next)
6402 for (prevPtr = NULL, summary = node2Ptr->summary;
6404 prevPtr = summary, summary = summary->next)
6406 if (summary->info == info)
6411 if (summary == NULL)
6415 if (summary->toggle_count != info->toggle_count)
6418 * No GtkTextBTreeNode has all toggles, so the root is still valid.
6425 * This GtkTextBTreeNode has all the toggles, so push down the root.
6428 if (prevPtr == NULL)
6430 node2Ptr->summary = summary->next;
6434 prevPtr->next = summary->next;
6436 summary_destroy (summary);
6437 info->tag_root = node2Ptr;
6440 node = info->tag_root;
6445 *----------------------------------------------------------------------
6449 * This is a utility procedure used by _gtk_text_btree_get_tags. It
6450 * increments the count for a particular tag, adding a new
6451 * entry for that tag if there wasn't one previously.
6457 * The information at *tagInfoPtr may be modified, and the arrays
6458 * may be reallocated to make them larger.
6460 *----------------------------------------------------------------------
6464 inc_count (GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
6469 for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
6470 count > 0; tag_p++, count--)
6474 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
6480 * There isn't currently an entry for this tag, so we have to
6481 * make a new one. If the arrays are full, then enlarge the
6485 if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
6487 GtkTextTag **newTags;
6488 int *newCounts, newSize;
6490 newSize = 2*tagInfoPtr->arraySize;
6491 newTags = (GtkTextTag **) g_malloc ((unsigned)
6492 (newSize*sizeof (GtkTextTag *)));
6493 memcpy ((void *) newTags, (void *) tagInfoPtr->tags,
6494 tagInfoPtr->arraySize *sizeof (GtkTextTag *));
6495 g_free ((char *) tagInfoPtr->tags);
6496 tagInfoPtr->tags = newTags;
6497 newCounts = (int *) g_malloc ((unsigned) (newSize*sizeof (int)));
6498 memcpy ((void *) newCounts, (void *) tagInfoPtr->counts,
6499 tagInfoPtr->arraySize *sizeof (int));
6500 g_free ((char *) tagInfoPtr->counts);
6501 tagInfoPtr->counts = newCounts;
6502 tagInfoPtr->arraySize = newSize;
6505 tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
6506 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
6507 tagInfoPtr->numTags++;
6511 gtk_text_btree_link_segment (GtkTextLineSegment *seg,
6512 const GtkTextIter *iter)
6514 GtkTextLineSegment *prev;
6518 line = _gtk_text_iter_get_text_line (iter);
6519 tree = _gtk_text_iter_get_btree (iter);
6521 prev = gtk_text_line_segment_split (iter);
6524 seg->next = line->segments;
6525 line->segments = seg;
6529 seg->next = prev->next;
6532 cleanup_line (line);
6533 segments_changed (tree);
6535 if (gtk_debug_flags & GTK_DEBUG_TEXT)
6536 _gtk_text_btree_check (tree);
6540 gtk_text_btree_unlink_segment (GtkTextBTree *tree,
6541 GtkTextLineSegment *seg,
6544 GtkTextLineSegment *prev;
6546 if (line->segments == seg)
6548 line->segments = seg->next;
6552 for (prev = line->segments; prev->next != seg;
6555 /* Empty loop body. */
6557 prev->next = seg->next;
6559 cleanup_line (line);
6560 segments_changed (tree);
6564 * This is here because it requires BTree internals, it logically
6565 * belongs in gtktextsegment.c
6570 *--------------------------------------------------------------
6572 * _gtk_toggle_segment_check_func --
6574 * This procedure is invoked to perform consistency checks
6575 * on toggle segments.
6581 * If a consistency problem is found the procedure g_errors.
6583 *--------------------------------------------------------------
6587 _gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6593 if (segPtr->byte_count != 0)
6595 g_error ("toggle_segment_check_func: segment had non-zero size");
6597 if (!segPtr->body.toggle.inNodeCounts)
6599 g_error ("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6601 needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6602 for (summary = line->parent->summary; ;
6603 summary = summary->next)
6605 if (summary == NULL)
6609 g_error ("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6616 if (summary->info == segPtr->body.toggle.info)
6620 g_error ("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6632 gtk_text_btree_node_view_check_consistency (GtkTextBTree *tree,
6633 GtkTextBTreeNode *node,
6643 while (view != NULL)
6645 if (view->view_id == nd->view_id)
6652 g_error ("Node has data for a view %p no longer attached to the tree",
6655 gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6656 &width, &height, &valid);
6658 /* valid aggregate not checked the same as width/height, because on
6659 * btree rebalance we can have invalid nodes where all lines below
6660 * them are actually valid, due to moving lines around between
6663 * The guarantee is that if there are invalid lines the node is
6664 * invalid - we don't guarantee that if the node is invalid there
6665 * are invalid lines.
6668 if (nd->width != width ||
6669 nd->height != height ||
6670 (nd->valid && !valid))
6672 g_error ("Node aggregates for view %p are invalid:\n"
6673 "Are (%d,%d,%s), should be (%d,%d,%s)",
6675 nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6676 width, height, valid ? "TRUE" : "FALSE");
6681 gtk_text_btree_node_check_consistency (GtkTextBTree *tree,
6682 GtkTextBTreeNode *node)
6684 GtkTextBTreeNode *childnode;
6685 Summary *summary, *summary2;
6687 GtkTextLineSegment *segPtr;
6688 int num_children, num_lines, num_chars, toggle_count, min_children;
6689 GtkTextLineData *ld;
6692 if (node->parent != NULL)
6694 min_children = MIN_CHILDREN;
6696 else if (node->level > 0)
6703 if ((node->num_children < min_children)
6704 || (node->num_children > MAX_CHILDREN))
6706 g_error ("gtk_text_btree_node_check_consistency: bad child count (%d)",
6707 node->num_children);
6710 nd = node->node_data;
6713 gtk_text_btree_node_view_check_consistency (tree, node, nd);
6720 if (node->level == 0)
6722 for (line = node->children.line; line != NULL;
6725 if (line->parent != node)
6727 g_error ("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6729 if (line->segments == NULL)
6731 g_error ("gtk_text_btree_node_check_consistency: line has no segments");
6737 /* Just ensuring we don't segv while doing this loop */
6742 for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6744 if (segPtr->type->checkFunc != NULL)
6746 (*segPtr->type->checkFunc)(segPtr, line);
6748 if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6749 && (segPtr->next != NULL)
6750 && (segPtr->next->byte_count == 0)
6751 && (segPtr->next->type->leftGravity))
6753 g_error ("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6755 if ((segPtr->next == NULL)
6756 && (segPtr->type != >k_text_char_type))
6758 g_error ("gtk_text_btree_node_check_consistency: line ended with wrong type");
6761 num_chars += segPtr->char_count;
6770 for (childnode = node->children.node; childnode != NULL;
6771 childnode = childnode->next)
6773 if (childnode->parent != node)
6775 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6777 if (childnode->level != (node->level-1))
6779 g_error ("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6780 node->level, childnode->level);
6782 gtk_text_btree_node_check_consistency (tree, childnode);
6783 for (summary = childnode->summary; summary != NULL;
6784 summary = summary->next)
6786 for (summary2 = node->summary; ;
6787 summary2 = summary2->next)
6789 if (summary2 == NULL)
6791 if (summary->info->tag_root == node)
6795 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6796 summary->info->tag->name,
6797 "present in parent summaries");
6799 if (summary->info == summary2->info)
6806 num_lines += childnode->num_lines;
6807 num_chars += childnode->num_chars;
6810 if (num_children != node->num_children)
6812 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6813 num_children, node->num_children);
6815 if (num_lines != node->num_lines)
6817 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6818 num_lines, node->num_lines);
6820 if (num_chars != node->num_chars)
6822 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6823 num_chars, node->num_chars);
6826 for (summary = node->summary; summary != NULL;
6827 summary = summary->next)
6829 if (summary->info->toggle_count == summary->toggle_count)
6831 g_error ("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6832 summary->info->tag->name);
6835 if (node->level == 0)
6837 for (line = node->children.line; line != NULL;
6840 for (segPtr = line->segments; segPtr != NULL;
6841 segPtr = segPtr->next)
6843 if ((segPtr->type != >k_text_toggle_on_type)
6844 && (segPtr->type != >k_text_toggle_off_type))
6848 if (segPtr->body.toggle.info == summary->info)
6850 if (!segPtr->body.toggle.inNodeCounts)
6851 g_error ("Toggle segment not in the node counts");
6860 for (childnode = node->children.node;
6862 childnode = childnode->next)
6864 for (summary2 = childnode->summary;
6866 summary2 = summary2->next)
6868 if (summary2->info == summary->info)
6870 toggle_count += summary2->toggle_count;
6875 if (toggle_count != summary->toggle_count)
6877 g_error ("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6878 toggle_count, summary->toggle_count);
6880 for (summary2 = summary->next; summary2 != NULL;
6881 summary2 = summary2->next)
6883 if (summary2->info == summary->info)
6885 g_error ("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6886 summary->info->tag->name);
6893 listify_foreach (GtkTextTag *tag, gpointer user_data)
6895 GSList** listp = user_data;
6897 *listp = g_slist_prepend (*listp, tag);
6901 list_of_tags (GtkTextTagTable *table)
6903 GSList *list = NULL;
6905 gtk_text_tag_table_foreach (table, listify_foreach, &list);
6911 _gtk_text_btree_check (GtkTextBTree *tree)
6914 GtkTextBTreeNode *node;
6916 GtkTextLineSegment *seg;
6918 GSList *all_tags, *taglist = NULL;
6920 GtkTextTagInfo *info;
6923 * Make sure that the tag toggle counts and the tag root pointers are OK.
6925 all_tags = list_of_tags (tree->table);
6926 for (taglist = all_tags; taglist != NULL ; taglist = taglist->next)
6928 tag = taglist->data;
6929 info = gtk_text_btree_get_existing_tag_info (tree, tag);
6932 node = info->tag_root;
6935 if (info->toggle_count != 0)
6937 g_error ("_gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6938 tag->name, info->toggle_count);
6940 continue; /* no ranges for the tag */
6942 else if (info->toggle_count == 0)
6944 g_error ("_gtk_text_btree_check found root for \"%s\" with no toggles",
6947 else if (info->toggle_count & 1)
6949 g_error ("_gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6950 tag->name, info->toggle_count);
6952 for (summary = node->summary; summary != NULL;
6953 summary = summary->next)
6955 if (summary->info->tag == tag)
6957 g_error ("_gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6961 if (node->level > 0)
6963 for (node = node->children.node ; node != NULL ;
6966 for (summary = node->summary; summary != NULL;
6967 summary = summary->next)
6969 if (summary->info->tag == tag)
6971 count += summary->toggle_count;
6978 const GtkTextLineSegmentClass *last = NULL;
6980 for (line = node->children.line ; line != NULL ;
6983 for (seg = line->segments; seg != NULL;
6986 if ((seg->type == >k_text_toggle_on_type ||
6987 seg->type == >k_text_toggle_off_type) &&
6988 seg->body.toggle.info->tag == tag)
6990 if (last == seg->type)
6991 g_error ("Two consecutive toggles on or off weren't merged");
6992 if (!seg->body.toggle.inNodeCounts)
6993 g_error ("Toggle segment not in the node counts");
7002 if (count != info->toggle_count)
7004 g_error ("_gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
7005 info->toggle_count, tag->name, count);
7010 g_slist_free (all_tags);
7013 * Call a recursive procedure to do the main body of checks.
7016 node = tree->root_node;
7017 gtk_text_btree_node_check_consistency (tree, tree->root_node);
7020 * Make sure that there are at least two lines in the text and
7021 * that the last line has no characters except a newline.
7024 if (node->num_lines < 2)
7026 g_error ("_gtk_text_btree_check: less than 2 lines in tree");
7028 if (node->num_chars < 2)
7030 g_error ("_gtk_text_btree_check: less than 2 chars in tree");
7032 while (node->level > 0)
7034 node = node->children.node;
7035 while (node->next != NULL)
7040 line = node->children.line;
7041 while (line->next != NULL)
7045 seg = line->segments;
7046 while ((seg->type == >k_text_toggle_off_type)
7047 || (seg->type == >k_text_right_mark_type)
7048 || (seg->type == >k_text_left_mark_type))
7051 * It's OK to toggle a tag off in the last line, but
7052 * not to start a new range. It's also OK to have marks
7058 if (seg->type != >k_text_char_type)
7060 g_error ("_gtk_text_btree_check: last line has bogus segment type");
7062 if (seg->next != NULL)
7064 g_error ("_gtk_text_btree_check: last line has too many segments");
7066 if (seg->byte_count != 1)
7068 g_error ("_gtk_text_btree_check: last line has wrong # characters: %d",
7071 if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
7073 g_error ("_gtk_text_btree_check: last line had bad value: %s",
7078 void _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line);
7079 void _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment* seg);
7080 void _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent);
7081 void _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
7084 _gtk_text_btree_spew (GtkTextBTree *tree)
7089 printf ("%d lines in tree %p\n",
7090 _gtk_text_btree_line_count (tree), tree);
7092 line = _gtk_text_btree_get_line (tree, 0, &real_line);
7094 while (line != NULL)
7096 _gtk_text_btree_spew_line (tree, line);
7097 line = _gtk_text_line_next (line);
7100 printf ("=================== Tag information\n");
7105 list = tree->tag_infos;
7107 while (list != NULL)
7109 GtkTextTagInfo *info;
7113 printf (" tag `%s': root at %p, toggle count %d\n",
7114 info->tag->name, info->tag_root, info->toggle_count);
7116 list = g_slist_next (list);
7119 if (tree->tag_infos == NULL)
7121 printf (" (no tags in the tree)\n");
7125 printf ("=================== Tree nodes\n");
7128 _gtk_text_btree_spew_node (tree->root_node, 0);
7133 _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
7136 GtkTextLineSegment *seg;
7138 spaces = g_strnfill (indent, ' ');
7140 printf ("%sline %p chars %d bytes %d\n",
7142 _gtk_text_line_char_count (line),
7143 _gtk_text_line_byte_count (line));
7145 seg = line->segments;
7148 if (seg->type == >k_text_char_type)
7150 gchar* str = g_strndup (seg->body.chars, MIN (seg->byte_count, 10));
7155 if (*s == '\n' || *s == '\r')
7159 printf ("%s chars `%s'...\n", spaces, str);
7162 else if (seg->type == >k_text_right_mark_type)
7164 printf ("%s right mark `%s' visible: %d\n",
7166 seg->body.mark.name,
7167 seg->body.mark.visible);
7169 else if (seg->type == >k_text_left_mark_type)
7171 printf ("%s left mark `%s' visible: %d\n",
7173 seg->body.mark.name,
7174 seg->body.mark.visible);
7176 else if (seg->type == >k_text_toggle_on_type ||
7177 seg->type == >k_text_toggle_off_type)
7179 printf ("%s tag `%s' %s\n",
7180 spaces, seg->body.toggle.info->tag->name,
7181 seg->type == >k_text_toggle_off_type ? "off" : "on");
7191 _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent)
7194 GtkTextBTreeNode *iter;
7197 spaces = g_strnfill (indent, ' ');
7199 printf ("%snode %p level %d children %d lines %d chars %d\n",
7200 spaces, node, node->level,
7201 node->num_children, node->num_lines, node->num_chars);
7206 printf ("%s %d toggles of `%s' below this node\n",
7207 spaces, s->toggle_count, s->info->tag->name);
7213 if (node->level > 0)
7215 iter = node->children.node;
7216 while (iter != NULL)
7218 _gtk_text_btree_spew_node (iter, indent + 2);
7225 GtkTextLine *line = node->children.line;
7226 while (line != NULL)
7228 _gtk_text_btree_spew_line_short (line, indent + 2);
7236 _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line)
7238 GtkTextLineSegment * seg;
7240 printf ("%4d| line: %p parent: %p next: %p\n",
7241 _gtk_text_line_get_number (line), line, line->parent, line->next);
7243 seg = line->segments;
7247 _gtk_text_btree_spew_segment (tree, seg);
7253 _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment * seg)
7255 printf (" segment: %p type: %s bytes: %d chars: %d\n",
7256 seg, seg->type->name, seg->byte_count, seg->char_count);
7258 if (seg->type == >k_text_char_type)
7260 gchar* str = g_strndup (seg->body.chars, seg->byte_count);
7261 printf (" `%s'\n", str);
7264 else if (seg->type == >k_text_right_mark_type)
7266 printf (" right mark `%s' visible: %d not_deleteable: %d\n",
7267 seg->body.mark.name,
7268 seg->body.mark.visible,
7269 seg->body.mark.not_deleteable);
7271 else if (seg->type == >k_text_left_mark_type)
7273 printf (" left mark `%s' visible: %d not_deleteable: %d\n",
7274 seg->body.mark.name,
7275 seg->body.mark.visible,
7276 seg->body.mark.not_deleteable);
7278 else if (seg->type == >k_text_toggle_on_type ||
7279 seg->type == >k_text_toggle_off_type)
7281 printf (" tag `%s' priority %d\n",
7282 seg->body.toggle.info->tag->name,
7283 seg->body.toggle.info->tag->priority);
7287 #define __GTK_TEXT_BTREE_C__
7288 #include "gtkaliasdef.c"