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;
2200 _gtk_text_btree_get_tags (const GtkTextIter *iter,
2203 GtkTextBTreeNode *node;
2204 GtkTextLine *siblingline;
2205 GtkTextLineSegment *seg;
2206 int src, dst, index;
2211 #define NUM_TAG_INFOS 10
2213 line = _gtk_text_iter_get_text_line (iter);
2214 byte_index = gtk_text_iter_get_line_index (iter);
2216 tagInfo.numTags = 0;
2217 tagInfo.arraySize = NUM_TAG_INFOS;
2218 tagInfo.tags = g_new (GtkTextTag*, NUM_TAG_INFOS);
2219 tagInfo.counts = g_new (int, NUM_TAG_INFOS);
2222 * Record tag toggles within the line of indexPtr but preceding
2223 * indexPtr. Note that if this loop segfaults, your
2224 * byte_index probably points past the sum of all
2225 * seg->byte_count */
2227 for (index = 0, seg = line->segments;
2228 (index + seg->byte_count) <= byte_index;
2229 index += seg->byte_count, seg = seg->next)
2231 if ((seg->type == >k_text_toggle_on_type)
2232 || (seg->type == >k_text_toggle_off_type))
2234 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2239 * Record toggles for tags in lines that are predecessors of
2240 * line but under the same level-0 GtkTextBTreeNode.
2243 for (siblingline = line->parent->children.line;
2244 siblingline != line;
2245 siblingline = siblingline->next)
2247 for (seg = siblingline->segments; seg != NULL;
2250 if ((seg->type == >k_text_toggle_on_type)
2251 || (seg->type == >k_text_toggle_off_type))
2253 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2259 * For each GtkTextBTreeNode in the ancestry of this line, record tag
2260 * toggles for all siblings that precede that GtkTextBTreeNode.
2263 for (node = line->parent; node->parent != NULL;
2264 node = node->parent)
2266 GtkTextBTreeNode *siblingPtr;
2269 for (siblingPtr = node->parent->children.node;
2270 siblingPtr != node; siblingPtr = siblingPtr->next)
2272 for (summary = siblingPtr->summary; summary != NULL;
2273 summary = summary->next)
2275 if (summary->toggle_count & 1)
2277 inc_count (summary->info->tag, summary->toggle_count,
2285 * Go through the tag information and squash out all of the tags
2286 * that have even toggle counts (these tags exist before the point
2287 * of interest, but not at the desired character itself).
2290 for (src = 0, dst = 0; src < tagInfo.numTags; src++)
2292 if (tagInfo.counts[src] & 1)
2294 g_assert (GTK_IS_TEXT_TAG (tagInfo.tags[src]));
2295 tagInfo.tags[dst] = tagInfo.tags[src];
2301 g_free (tagInfo.counts);
2304 g_free (tagInfo.tags);
2307 return tagInfo.tags;
2311 copy_segment (GString *string,
2312 gboolean include_hidden,
2313 gboolean include_nonchars,
2314 const GtkTextIter *start,
2315 const GtkTextIter *end)
2317 GtkTextLineSegment *end_seg;
2318 GtkTextLineSegment *seg;
2320 if (gtk_text_iter_equal (start, end))
2323 seg = _gtk_text_iter_get_indexable_segment (start);
2324 end_seg = _gtk_text_iter_get_indexable_segment (end);
2326 if (seg->type == >k_text_char_type)
2328 gboolean copy = TRUE;
2329 gint copy_bytes = 0;
2330 gint copy_start = 0;
2332 /* Don't copy if we're invisible; segments are invisible/not
2333 as a whole, no need to check each char */
2334 if (!include_hidden &&
2335 _gtk_text_btree_char_is_invisible (start))
2338 /* printf (" <invisible>\n"); */
2341 copy_start = _gtk_text_iter_get_segment_byte (start);
2345 /* End is in the same segment; need to copy fewer bytes. */
2346 gint end_byte = _gtk_text_iter_get_segment_byte (end);
2348 copy_bytes = end_byte - copy_start;
2351 copy_bytes = seg->byte_count - copy_start;
2353 g_assert (copy_bytes != 0); /* Due to iter equality check at
2354 front of this function. */
2358 g_assert ((copy_start + copy_bytes) <= seg->byte_count);
2360 g_string_append_len (string,
2361 seg->body.chars + copy_start,
2365 /* printf (" :%s\n", string->str); */
2367 else if (seg->type == >k_text_pixbuf_type ||
2368 seg->type == >k_text_child_type)
2370 gboolean copy = TRUE;
2372 if (!include_nonchars)
2376 else if (!include_hidden &&
2377 _gtk_text_btree_char_is_invisible (start))
2384 g_string_append_len (string,
2385 gtk_text_unknown_char_utf8,
2393 _gtk_text_btree_get_text (const GtkTextIter *start_orig,
2394 const GtkTextIter *end_orig,
2395 gboolean include_hidden,
2396 gboolean include_nonchars)
2398 GtkTextLineSegment *seg;
2399 GtkTextLineSegment *end_seg;
2406 g_return_val_if_fail (start_orig != NULL, NULL);
2407 g_return_val_if_fail (end_orig != NULL, NULL);
2408 g_return_val_if_fail (_gtk_text_iter_get_btree (start_orig) ==
2409 _gtk_text_iter_get_btree (end_orig), NULL);
2411 start = *start_orig;
2414 gtk_text_iter_order (&start, &end);
2416 retval = g_string_new (NULL);
2418 end_seg = _gtk_text_iter_get_indexable_segment (&end);
2420 seg = _gtk_text_iter_get_indexable_segment (&iter);
2421 while (seg != end_seg)
2423 copy_segment (retval, include_hidden, include_nonchars,
2426 _gtk_text_iter_forward_indexable_segment (&iter);
2428 seg = _gtk_text_iter_get_indexable_segment (&iter);
2431 copy_segment (retval, include_hidden, include_nonchars, &iter, &end);
2434 g_string_free (retval, FALSE);
2439 _gtk_text_btree_line_count (GtkTextBTree *tree)
2441 /* Subtract bogus line at the end; we return a count
2443 return tree->root_node->num_lines - 1;
2447 _gtk_text_btree_char_count (GtkTextBTree *tree)
2449 /* Exclude newline in bogus last line and the
2450 * one in the last line that is after the end iterator
2452 return tree->root_node->num_chars - 2;
2455 #define LOTSA_TAGS 1000
2457 _gtk_text_btree_char_is_invisible (const GtkTextIter *iter)
2459 gboolean invisible = FALSE; /* if nobody says otherwise, it's visible */
2461 int deftagCnts[LOTSA_TAGS] = { 0, };
2462 int *tagCnts = deftagCnts;
2463 GtkTextTag *deftags[LOTSA_TAGS];
2464 GtkTextTag **tags = deftags;
2466 GtkTextBTreeNode *node;
2467 GtkTextLine *siblingline;
2468 GtkTextLineSegment *seg;
2475 line = _gtk_text_iter_get_text_line (iter);
2476 tree = _gtk_text_iter_get_btree (iter);
2477 byte_index = gtk_text_iter_get_line_index (iter);
2479 numTags = gtk_text_tag_table_get_size (tree->table);
2481 /* almost always avoid malloc, so stay out of system calls */
2482 if (LOTSA_TAGS < numTags)
2484 tagCnts = g_new0 (int, numTags);
2485 tags = g_new (GtkTextTag*, numTags);
2489 * Record tag toggles within the line of indexPtr but preceding
2493 for (index = 0, seg = line->segments;
2494 (index + seg->byte_count) <= byte_index; /* segfault here means invalid index */
2495 index += seg->byte_count, seg = seg->next)
2497 if ((seg->type == >k_text_toggle_on_type)
2498 || (seg->type == >k_text_toggle_off_type))
2500 tag = seg->body.toggle.info->tag;
2501 if (tag->invisible_set)
2503 tags[tag->priority] = tag;
2504 tagCnts[tag->priority]++;
2510 * Record toggles for tags in lines that are predecessors of
2511 * line but under the same level-0 GtkTextBTreeNode.
2514 for (siblingline = line->parent->children.line;
2515 siblingline != line;
2516 siblingline = siblingline->next)
2518 for (seg = siblingline->segments; seg != NULL;
2521 if ((seg->type == >k_text_toggle_on_type)
2522 || (seg->type == >k_text_toggle_off_type))
2524 tag = seg->body.toggle.info->tag;
2525 if (tag->invisible_set)
2527 tags[tag->priority] = tag;
2528 tagCnts[tag->priority]++;
2535 * For each GtkTextBTreeNode in the ancestry of this line, record tag toggles
2536 * for all siblings that precede that GtkTextBTreeNode.
2539 for (node = line->parent; node->parent != NULL;
2540 node = node->parent)
2542 GtkTextBTreeNode *siblingPtr;
2545 for (siblingPtr = node->parent->children.node;
2546 siblingPtr != node; siblingPtr = siblingPtr->next)
2548 for (summary = siblingPtr->summary; summary != NULL;
2549 summary = summary->next)
2551 if (summary->toggle_count & 1)
2553 tag = summary->info->tag;
2554 if (tag->invisible_set)
2556 tags[tag->priority] = tag;
2557 tagCnts[tag->priority] += summary->toggle_count;
2565 * Now traverse from highest priority to lowest,
2566 * take invisible value from first odd count (= on)
2569 for (i = numTags-1; i >=0; i--)
2573 /* FIXME not sure this should be if 0 */
2575 #ifndef ALWAYS_SHOW_SELECTION
2576 /* who would make the selection invisible? */
2577 if ((tag == tkxt->seltag)
2578 && !(tkxt->flags & GOT_FOCUS))
2584 invisible = tags[i]->values->invisible;
2589 if (LOTSA_TAGS < numTags)
2604 redisplay_region (GtkTextBTree *tree,
2605 const GtkTextIter *start,
2606 const GtkTextIter *end,
2607 gboolean cursors_only)
2610 GtkTextLine *start_line, *end_line;
2612 if (gtk_text_iter_compare (start, end) > 0)
2614 const GtkTextIter *tmp = start;
2619 start_line = _gtk_text_iter_get_text_line (start);
2620 end_line = _gtk_text_iter_get_text_line (end);
2623 while (view != NULL)
2625 gint start_y, end_y;
2626 GtkTextLineData *ld;
2628 start_y = _gtk_text_btree_find_line_top (tree, start_line, view->view_id);
2630 if (end_line == start_line)
2633 end_y = _gtk_text_btree_find_line_top (tree, end_line, view->view_id);
2635 ld = _gtk_text_line_get_data (end_line, view->view_id);
2637 end_y += ld->height;
2640 gtk_text_layout_cursors_changed (view->layout, start_y,
2644 gtk_text_layout_changed (view->layout, start_y,
2653 redisplay_mark (GtkTextLineSegment *mark)
2658 _gtk_text_btree_get_iter_at_mark (mark->body.mark.tree,
2660 mark->body.mark.obj);
2663 gtk_text_iter_forward_char (&end);
2665 DV (g_print ("invalidating due to moving visible mark (%s)\n", G_STRLOC));
2666 _gtk_text_btree_invalidate_region (mark->body.mark.tree, &iter, &end, TRUE);
2670 redisplay_mark_if_visible (GtkTextLineSegment *mark)
2672 if (!mark->body.mark.visible)
2675 redisplay_mark (mark);
2679 ensure_not_off_end (GtkTextBTree *tree,
2680 GtkTextLineSegment *mark,
2683 if (gtk_text_iter_get_line (iter) == _gtk_text_btree_line_count (tree))
2684 gtk_text_iter_backward_char (iter);
2687 static GtkTextLineSegment*
2688 real_set_mark (GtkTextBTree *tree,
2689 GtkTextMark *existing_mark,
2691 gboolean left_gravity,
2692 const GtkTextIter *where,
2693 gboolean should_exist,
2694 gboolean redraw_selections)
2696 GtkTextLineSegment *mark;
2699 g_return_val_if_fail (tree != NULL, NULL);
2700 g_return_val_if_fail (where != NULL, NULL);
2701 g_return_val_if_fail (_gtk_text_iter_get_btree (where) == tree, NULL);
2705 if (gtk_text_mark_get_buffer (existing_mark) != NULL)
2706 mark = existing_mark->segment;
2710 else if (name != NULL)
2711 mark = g_hash_table_lookup (tree->mark_table,
2716 if (should_exist && mark == NULL)
2718 g_warning ("No mark `%s' exists!", name);
2722 /* OK if !should_exist and it does already exist, in that case
2728 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2729 _gtk_text_iter_check (&iter);
2733 if (redraw_selections &&
2734 (mark == tree->insert_mark->segment ||
2735 mark == tree->selection_bound_mark->segment))
2737 GtkTextIter old_pos;
2739 _gtk_text_btree_get_iter_at_mark (tree, &old_pos,
2740 mark->body.mark.obj);
2741 redisplay_region (tree, &old_pos, where, TRUE);
2745 * don't let visible marks be after the final newline of the
2749 if (mark->body.mark.visible)
2751 ensure_not_off_end (tree, mark, &iter);
2754 /* Redraw the mark's old location. */
2755 redisplay_mark_if_visible (mark);
2757 /* Unlink mark from its current location.
2758 This could hose our iterator... */
2759 gtk_text_btree_unlink_segment (tree, mark,
2760 mark->body.mark.line);
2761 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2762 g_assert (mark->body.mark.line == _gtk_text_iter_get_text_line (&iter));
2764 segments_changed (tree); /* make sure the iterator recomputes its
2770 g_object_ref (existing_mark);
2772 existing_mark = gtk_text_mark_new (name, left_gravity);
2774 mark = existing_mark->segment;
2775 _gtk_mark_segment_set_tree (mark, tree);
2777 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2779 if (mark->body.mark.name)
2780 g_hash_table_insert (tree->mark_table,
2781 mark->body.mark.name,
2785 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2786 _gtk_text_iter_check (&iter);
2788 /* Link mark into new location */
2789 gtk_text_btree_link_segment (mark, &iter);
2791 /* Invalidate some iterators. */
2792 segments_changed (tree);
2795 * update the screen at the mark's new location.
2798 redisplay_mark_if_visible (mark);
2800 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2801 _gtk_text_iter_check (&iter);
2803 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2804 _gtk_text_btree_check (tree);
2811 _gtk_text_btree_set_mark (GtkTextBTree *tree,
2812 GtkTextMark *existing_mark,
2814 gboolean left_gravity,
2815 const GtkTextIter *iter,
2816 gboolean should_exist)
2818 GtkTextLineSegment *seg;
2820 seg = real_set_mark (tree, existing_mark,
2821 name, left_gravity, iter, should_exist,
2824 return seg ? seg->body.mark.obj : NULL;
2828 _gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2832 GtkTextIter tmp_start, tmp_end;
2834 _gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2836 _gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2837 tree->selection_bound_mark);
2839 if (gtk_text_iter_equal (&tmp_start, &tmp_end))
2851 gtk_text_iter_order (&tmp_start, &tmp_end);
2864 _gtk_text_btree_place_cursor (GtkTextBTree *tree,
2865 const GtkTextIter *iter)
2867 _gtk_text_btree_select_range (tree, iter, iter);
2871 _gtk_text_btree_select_range (GtkTextBTree *tree,
2872 const GtkTextIter *ins,
2873 const GtkTextIter *bound)
2875 GtkTextIter old_ins, old_bound;
2877 _gtk_text_btree_get_iter_at_mark (tree, &old_ins,
2879 _gtk_text_btree_get_iter_at_mark (tree, &old_bound,
2880 tree->selection_bound_mark);
2882 /* Check if it's no-op since gtk_text_buffer_place_cursor()
2883 * also calls this, and this will redraw the cursor line. */
2884 if (!gtk_text_iter_equal (&old_ins, ins) ||
2885 !gtk_text_iter_equal (&old_bound, bound))
2887 redisplay_region (tree, &old_ins, &old_bound, TRUE);
2889 /* Move insert AND selection_bound before we redisplay */
2890 real_set_mark (tree, tree->insert_mark,
2891 "insert", FALSE, ins, TRUE, FALSE);
2892 real_set_mark (tree, tree->selection_bound_mark,
2893 "selection_bound", FALSE, bound, TRUE, FALSE);
2895 redisplay_region (tree, ins, bound, TRUE);
2901 _gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2906 g_return_if_fail (tree != NULL);
2907 g_return_if_fail (name != NULL);
2909 mark = g_hash_table_lookup (tree->mark_table,
2912 _gtk_text_btree_remove_mark (tree, mark);
2916 _gtk_text_btree_release_mark_segment (GtkTextBTree *tree,
2917 GtkTextLineSegment *segment)
2920 if (segment->body.mark.name)
2921 g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2923 segment->body.mark.tree = NULL;
2924 segment->body.mark.line = NULL;
2926 /* Remove the ref on the mark, which frees segment as a side effect
2927 * if this is the last reference.
2929 g_object_unref (segment->body.mark.obj);
2933 _gtk_text_btree_remove_mark (GtkTextBTree *tree,
2936 GtkTextLineSegment *segment;
2938 g_return_if_fail (mark != NULL);
2939 g_return_if_fail (tree != NULL);
2941 segment = mark->segment;
2943 if (segment->body.mark.not_deleteable)
2945 g_warning ("Can't delete special mark `%s'", segment->body.mark.name);
2949 /* This calls cleanup_line and segments_changed */
2950 gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2952 _gtk_text_btree_release_mark_segment (tree, segment);
2956 _gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2957 GtkTextMark *segment)
2959 return segment == tree->insert_mark;
2963 _gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2964 GtkTextMark *segment)
2966 return segment == tree->selection_bound_mark;
2970 _gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2973 GtkTextLineSegment *seg;
2975 g_return_val_if_fail (tree != NULL, NULL);
2976 g_return_val_if_fail (name != NULL, NULL);
2978 seg = g_hash_table_lookup (tree->mark_table, name);
2980 return seg ? seg->body.mark.obj : NULL;
2984 * gtk_text_mark_set_visible:
2985 * @mark: a #GtkTextMark
2986 * @setting: visibility of mark
2988 * Sets the visibility of @mark; the insertion point is normally
2989 * visible, i.e. you can see it as a vertical bar. Also, the text
2990 * widget uses a visible mark to indicate where a drop will occur when
2991 * dragging-and-dropping text. Most other marks are not visible.
2992 * Marks are not visible by default.
2996 gtk_text_mark_set_visible (GtkTextMark *mark,
2999 GtkTextLineSegment *seg;
3001 g_return_if_fail (mark != NULL);
3003 seg = mark->segment;
3005 if (seg->body.mark.visible == setting)
3009 seg->body.mark.visible = setting;
3011 if (seg->body.mark.tree)
3012 redisplay_mark (seg);
3017 _gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
3020 GtkTextBTreeNode *node;
3021 GtkTextTagInfo *info;
3023 g_return_val_if_fail (tree != NULL, NULL);
3027 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3032 if (info->tag_root == NULL)
3035 node = info->tag_root;
3037 /* We know the tag root has instances of the given
3040 continue_outer_loop:
3041 g_assert (node != NULL);
3042 while (node->level > 0)
3044 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
3045 node = node->children.node;
3046 while (node != NULL)
3048 if (gtk_text_btree_node_has_tag (node, tag))
3049 goto continue_outer_loop;
3053 g_assert (node != NULL);
3056 g_assert (node != NULL); /* The tag summaries said some node had
3059 g_assert (node->level == 0);
3061 return node->children.line;
3065 /* Looking for any tag at all (tag == NULL).
3066 Unfortunately this can't be done in a simple and efficient way
3067 right now; so I'm just going to return the
3068 first line in the btree. FIXME */
3069 return _gtk_text_btree_get_line (tree, 0, NULL);
3074 _gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
3077 GtkTextBTreeNode *node;
3078 GtkTextBTreeNode *last_node;
3080 GtkTextTagInfo *info;
3082 g_return_val_if_fail (tree != NULL, NULL);
3086 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3088 if (info->tag_root == NULL)
3091 node = info->tag_root;
3092 /* We know the tag root has instances of the given
3095 while (node->level > 0)
3097 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
3099 node = node->children.node;
3100 while (node != NULL)
3102 if (gtk_text_btree_node_has_tag (node, tag))
3110 g_assert (node != NULL); /* The tag summaries said some node had
3113 g_assert (node->level == 0);
3115 /* Find the last line in this node */
3116 line = node->children.line;
3117 while (line->next != NULL)
3124 /* This search can't be done efficiently at the moment,
3125 at least not without complexity.
3126 So, we just return the last line.
3128 return _gtk_text_btree_get_end_iter_line (tree);
3138 _gtk_text_line_get_number (GtkTextLine *line)
3141 GtkTextBTreeNode *node, *parent, *node2;
3145 * First count how many lines precede this one in its level-0
3149 node = line->parent;
3151 for (line2 = node->children.line; line2 != line;
3152 line2 = line2->next)
3156 g_error ("gtk_text_btree_line_number couldn't find line");
3162 * Now work up through the levels of the tree one at a time,
3163 * counting how many lines are in GtkTextBTreeNodes preceding the current
3167 for (parent = node->parent ; parent != NULL;
3168 node = parent, parent = parent->parent)
3170 for (node2 = parent->children.node; node2 != node;
3171 node2 = node2->next)
3175 g_error ("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
3177 index += node2->num_lines;
3183 static GtkTextLineSegment*
3184 find_toggle_segment_before_char (GtkTextLine *line,
3188 GtkTextLineSegment *seg;
3189 GtkTextLineSegment *toggle_seg;
3194 seg = line->segments;
3195 while ( (index + seg->char_count) <= char_in_line )
3197 if (((seg->type == >k_text_toggle_on_type)
3198 || (seg->type == >k_text_toggle_off_type))
3199 && (seg->body.toggle.info->tag == tag))
3202 index += seg->char_count;
3209 static GtkTextLineSegment*
3210 find_toggle_segment_before_byte (GtkTextLine *line,
3214 GtkTextLineSegment *seg;
3215 GtkTextLineSegment *toggle_seg;
3220 seg = line->segments;
3221 while ( (index + seg->byte_count) <= byte_in_line )
3223 if (((seg->type == >k_text_toggle_on_type)
3224 || (seg->type == >k_text_toggle_off_type))
3225 && (seg->body.toggle.info->tag == tag))
3228 index += seg->byte_count;
3236 find_toggle_outside_current_line (GtkTextLine *line,
3240 GtkTextBTreeNode *node;
3241 GtkTextLine *sibling_line;
3242 GtkTextLineSegment *seg;
3243 GtkTextLineSegment *toggle_seg;
3245 GtkTextTagInfo *info = NULL;
3248 * No toggle in this line. Look for toggles for the tag in lines
3249 * that are predecessors of line but under the same
3250 * level-0 GtkTextBTreeNode.
3253 sibling_line = line->parent->children.line;
3254 while (sibling_line != line)
3256 seg = sibling_line->segments;
3259 if (((seg->type == >k_text_toggle_on_type)
3260 || (seg->type == >k_text_toggle_off_type))
3261 && (seg->body.toggle.info->tag == tag))
3267 sibling_line = sibling_line->next;
3270 if (toggle_seg != NULL)
3271 return (toggle_seg->type == >k_text_toggle_on_type);
3274 * No toggle in this GtkTextBTreeNode. Scan upwards through the ancestors of
3275 * this GtkTextBTreeNode, counting the number of toggles of the given tag in
3276 * siblings that precede that GtkTextBTreeNode.
3279 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3285 node = line->parent;
3286 while (node->parent != NULL)
3288 GtkTextBTreeNode *sibling_node;
3290 sibling_node = node->parent->children.node;
3291 while (sibling_node != node)
3295 summary = sibling_node->summary;
3296 while (summary != NULL)
3298 if (summary->info == info)
3299 toggles += summary->toggle_count;
3301 summary = summary->next;
3304 sibling_node = sibling_node->next;
3307 if (node == info->tag_root)
3310 node = node->parent;
3314 * An odd number of toggles means that the tag is present at the
3318 return (toggles & 1) != 0;
3321 /* FIXME this function is far too slow, for no good reason. */
3323 _gtk_text_line_char_has_tag (GtkTextLine *line,
3328 GtkTextLineSegment *toggle_seg;
3330 g_return_val_if_fail (line != NULL, FALSE);
3333 * Check for toggles for the tag in the line but before
3334 * the char. If there is one, its type indicates whether or
3335 * not the character is tagged.
3338 toggle_seg = find_toggle_segment_before_char (line, char_in_line, tag);
3340 if (toggle_seg != NULL)
3341 return (toggle_seg->type == >k_text_toggle_on_type);
3343 return find_toggle_outside_current_line (line, tree, tag);
3347 _gtk_text_line_byte_has_tag (GtkTextLine *line,
3352 GtkTextLineSegment *toggle_seg;
3354 g_return_val_if_fail (line != NULL, FALSE);
3357 * Check for toggles for the tag in the line but before
3358 * the char. If there is one, its type indicates whether or
3359 * not the character is tagged.
3362 toggle_seg = find_toggle_segment_before_byte (line, byte_in_line, tag);
3364 if (toggle_seg != NULL)
3365 return (toggle_seg->type == >k_text_toggle_on_type);
3367 return find_toggle_outside_current_line (line, tree, tag);
3371 _gtk_text_line_is_last (GtkTextLine *line,
3374 return line == get_last_line (tree);
3378 ensure_end_iter_line (GtkTextBTree *tree)
3380 if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
3384 /* n_lines is without the magic line at the end */
3385 g_assert (_gtk_text_btree_line_count (tree) >= 1);
3387 tree->end_iter_line = _gtk_text_btree_get_line_no_last (tree, -1, &real_line);
3389 tree->end_iter_line_stamp = tree->chars_changed_stamp;
3394 ensure_end_iter_segment (GtkTextBTree *tree)
3396 if (tree->end_iter_segment_stamp != tree->segments_changed_stamp)
3398 GtkTextLineSegment *seg;
3399 GtkTextLineSegment *last_with_chars;
3401 ensure_end_iter_line (tree);
3403 last_with_chars = NULL;
3405 seg = tree->end_iter_line->segments;
3408 if (seg->char_count > 0)
3409 last_with_chars = seg;
3413 tree->end_iter_segment = last_with_chars;
3415 /* We know the last char in the last line is '\n' */
3416 tree->end_iter_segment_byte_index = last_with_chars->byte_count - 1;
3417 tree->end_iter_segment_char_offset = last_with_chars->char_count - 1;
3419 tree->end_iter_segment_stamp = tree->segments_changed_stamp;
3421 g_assert (tree->end_iter_segment->type == >k_text_char_type);
3422 g_assert (tree->end_iter_segment->body.chars[tree->end_iter_segment_byte_index] == '\n');
3427 _gtk_text_line_contains_end_iter (GtkTextLine *line,
3430 ensure_end_iter_line (tree);
3432 return line == tree->end_iter_line;
3436 _gtk_text_btree_is_end (GtkTextBTree *tree,
3438 GtkTextLineSegment *seg,
3442 g_return_val_if_fail (byte_index >= 0 || char_offset >= 0, FALSE);
3444 /* Do this first to avoid walking segments in most cases */
3445 if (!_gtk_text_line_contains_end_iter (line, tree))
3448 ensure_end_iter_segment (tree);
3450 if (seg != tree->end_iter_segment)
3453 if (byte_index >= 0)
3454 return byte_index == tree->end_iter_segment_byte_index;
3456 return char_offset == tree->end_iter_segment_char_offset;
3460 _gtk_text_line_next (GtkTextLine *line)
3462 GtkTextBTreeNode *node;
3464 if (line->next != NULL)
3469 * This was the last line associated with the particular parent
3470 * GtkTextBTreeNode. Search up the tree for the next GtkTextBTreeNode,
3471 * then search down from that GtkTextBTreeNode to find the first
3475 node = line->parent;
3476 while (node != NULL && node->next == NULL)
3477 node = node->parent;
3483 while (node->level > 0)
3485 node = node->children.node;
3488 g_assert (node->children.line != line);
3490 return node->children.line;
3495 _gtk_text_line_next_excluding_last (GtkTextLine *line)
3499 next = _gtk_text_line_next (line);
3501 /* If we were on the end iter line, we can't go to
3504 if (next && next->next == NULL && /* these checks are optimization only */
3505 _gtk_text_line_next (next) == NULL)
3512 _gtk_text_line_previous (GtkTextLine *line)
3514 GtkTextBTreeNode *node;
3515 GtkTextBTreeNode *node2;
3519 * Find the line under this GtkTextBTreeNode just before the starting line.
3521 prev = line->parent->children.line; /* First line at leaf */
3522 while (prev != line)
3524 if (prev->next == line)
3530 g_error ("gtk_text_btree_previous_line ran out of lines");
3534 * This was the first line associated with the particular parent
3535 * GtkTextBTreeNode. Search up the tree for the previous GtkTextBTreeNode,
3536 * then search down from that GtkTextBTreeNode to find its last line.
3538 for (node = line->parent; ; node = node->parent)
3540 if (node == NULL || node->parent == NULL)
3542 else if (node != node->parent->children.node)
3546 for (node2 = node->parent->children.node; ;
3547 node2 = node2->children.node)
3549 while (node2->next != node)
3550 node2 = node2->next;
3552 if (node2->level == 0)
3558 for (prev = node2->children.line ; ; prev = prev->next)
3560 if (prev->next == NULL)
3564 g_assert_not_reached ();
3570 _gtk_text_line_data_new (GtkTextLayout *layout,
3573 GtkTextLineData *line_data;
3575 line_data = g_new (GtkTextLineData, 1);
3577 line_data->view_id = layout;
3578 line_data->next = NULL;
3579 line_data->width = 0;
3580 line_data->height = 0;
3581 line_data->valid = FALSE;
3587 _gtk_text_line_add_data (GtkTextLine *line,
3588 GtkTextLineData *data)
3590 g_return_if_fail (line != NULL);
3591 g_return_if_fail (data != NULL);
3592 g_return_if_fail (data->view_id != NULL);
3596 data->next = line->views;
3606 _gtk_text_line_remove_data (GtkTextLine *line,
3609 GtkTextLineData *prev;
3610 GtkTextLineData *iter;
3612 g_return_val_if_fail (line != NULL, NULL);
3613 g_return_val_if_fail (view_id != NULL, NULL);
3617 while (iter != NULL)
3619 if (iter->view_id == view_id)
3628 prev->next = iter->next;
3630 line->views = iter->next;
3639 _gtk_text_line_get_data (GtkTextLine *line,
3642 GtkTextLineData *iter;
3644 g_return_val_if_fail (line != NULL, NULL);
3645 g_return_val_if_fail (view_id != NULL, NULL);
3648 while (iter != NULL)
3650 if (iter->view_id == view_id)
3659 _gtk_text_line_invalidate_wrap (GtkTextLine *line,
3660 GtkTextLineData *ld)
3662 /* For now this is totally unoptimized. FIXME?
3664 We could probably optimize the case where the width removed
3665 is less than the max width for the parent node,
3666 and the case where the height is unchanged when we re-wrap.
3669 g_return_if_fail (ld != NULL);
3672 gtk_text_btree_node_invalidate_upward (line->parent, ld->view_id);
3676 _gtk_text_line_char_count (GtkTextLine *line)
3678 GtkTextLineSegment *seg;
3682 seg = line->segments;
3685 size += seg->char_count;
3692 _gtk_text_line_byte_count (GtkTextLine *line)
3694 GtkTextLineSegment *seg;
3698 seg = line->segments;
3701 size += seg->byte_count;
3709 _gtk_text_line_char_index (GtkTextLine *target_line)
3711 GSList *node_stack = NULL;
3712 GtkTextBTreeNode *iter;
3716 /* Push all our parent nodes onto a stack */
3717 iter = target_line->parent;
3719 g_assert (iter != NULL);
3721 while (iter != NULL)
3723 node_stack = g_slist_prepend (node_stack, iter);
3725 iter = iter->parent;
3728 /* Check that we have the root node on top of the stack. */
3729 g_assert (node_stack != NULL &&
3730 node_stack->data != NULL &&
3731 ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3733 /* Add up chars in all nodes before the nodes in our stack.
3737 iter = node_stack->data;
3738 while (iter != NULL)
3740 GtkTextBTreeNode *child_iter;
3741 GtkTextBTreeNode *next_node;
3743 next_node = node_stack->next ?
3744 node_stack->next->data : NULL;
3745 node_stack = g_slist_remove (node_stack, node_stack->data);
3747 if (iter->level == 0)
3749 /* stack should be empty when we're on the last node */
3750 g_assert (node_stack == NULL);
3751 break; /* Our children are now lines */
3754 g_assert (next_node != NULL);
3755 g_assert (iter != NULL);
3756 g_assert (next_node->parent == iter);
3758 /* Add up chars before us in the tree */
3759 child_iter = iter->children.node;
3760 while (child_iter != next_node)
3762 g_assert (child_iter != NULL);
3764 num_chars += child_iter->num_chars;
3766 child_iter = child_iter->next;
3772 g_assert (iter != NULL);
3773 g_assert (iter == target_line->parent);
3775 /* Since we don't store char counts in lines, only in segments, we
3776 have to iterate over the lines adding up segment char counts
3777 until we find our line. */
3778 line = iter->children.line;
3779 while (line != target_line)
3781 g_assert (line != NULL);
3783 num_chars += _gtk_text_line_char_count (line);
3788 g_assert (line == target_line);
3794 _gtk_text_line_byte_to_segment (GtkTextLine *line,
3798 GtkTextLineSegment *seg;
3801 g_return_val_if_fail (line != NULL, NULL);
3803 offset = byte_offset;
3804 seg = line->segments;
3806 while (offset >= seg->byte_count)
3808 offset -= seg->byte_count;
3810 g_assert (seg != NULL); /* means an invalid byte index */
3814 *seg_offset = offset;
3820 _gtk_text_line_char_to_segment (GtkTextLine *line,
3824 GtkTextLineSegment *seg;
3827 g_return_val_if_fail (line != NULL, NULL);
3829 offset = char_offset;
3830 seg = line->segments;
3832 while (offset >= seg->char_count)
3834 offset -= seg->char_count;
3836 g_assert (seg != NULL); /* means an invalid char index */
3840 *seg_offset = offset;
3846 _gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3850 GtkTextLineSegment *seg;
3853 g_return_val_if_fail (line != NULL, NULL);
3855 offset = byte_offset;
3856 seg = line->segments;
3858 while (offset > 0 && offset >= seg->byte_count)
3860 offset -= seg->byte_count;
3862 g_assert (seg != NULL); /* means an invalid byte index */
3866 *seg_offset = offset;
3872 _gtk_text_line_char_to_any_segment (GtkTextLine *line,
3876 GtkTextLineSegment *seg;
3879 g_return_val_if_fail (line != NULL, NULL);
3881 offset = char_offset;
3882 seg = line->segments;
3884 while (offset > 0 && offset >= seg->char_count)
3886 offset -= seg->char_count;
3888 g_assert (seg != NULL); /* means an invalid byte index */
3892 *seg_offset = offset;
3898 _gtk_text_line_byte_to_char (GtkTextLine *line,
3902 GtkTextLineSegment *seg;
3904 g_return_val_if_fail (line != NULL, 0);
3905 g_return_val_if_fail (byte_offset >= 0, 0);
3908 seg = line->segments;
3909 while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3910 the next segment) */
3912 byte_offset -= seg->byte_count;
3913 char_offset += seg->char_count;
3915 g_assert (seg != NULL); /* our byte_index was bogus if this happens */
3918 g_assert (seg != NULL);
3920 /* Now byte_offset is the offset into the current segment,
3921 and char_offset is the start of the current segment.
3922 Optimize the case where no chars use > 1 byte */
3923 if (seg->byte_count == seg->char_count)
3924 return char_offset + byte_offset;
3927 if (seg->type == >k_text_char_type)
3928 return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3931 g_assert (seg->char_count == 1);
3932 g_assert (byte_offset == 0);
3940 _gtk_text_line_char_to_byte (GtkTextLine *line,
3943 g_warning ("FIXME not implemented");
3948 /* FIXME sync with char_locate (or figure out a clean
3949 way to merge the two functions) */
3951 _gtk_text_line_byte_locate (GtkTextLine *line,
3953 GtkTextLineSegment **segment,
3954 GtkTextLineSegment **any_segment,
3955 gint *seg_byte_offset,
3956 gint *line_byte_offset)
3958 GtkTextLineSegment *seg;
3959 GtkTextLineSegment *after_last_indexable;
3960 GtkTextLineSegment *last_indexable;
3964 g_return_val_if_fail (line != NULL, FALSE);
3965 g_return_val_if_fail (byte_offset >= 0, FALSE);
3968 *any_segment = NULL;
3971 offset = byte_offset;
3973 last_indexable = NULL;
3974 after_last_indexable = line->segments;
3975 seg = line->segments;
3977 /* The loop ends when we're inside a segment;
3978 last_indexable refers to the last segment
3979 we passed entirely. */
3980 while (seg && offset >= seg->byte_count)
3982 if (seg->char_count > 0)
3984 offset -= seg->byte_count;
3985 bytes_in_line += seg->byte_count;
3986 last_indexable = seg;
3987 after_last_indexable = last_indexable->next;
3995 /* We went off the end of the line */
3997 g_warning ("%s: byte index off the end of the line", G_STRLOC);
4004 if (after_last_indexable != NULL)
4005 *any_segment = after_last_indexable;
4007 *any_segment = *segment;
4010 /* Override any_segment if we're in the middle of a segment. */
4012 *any_segment = *segment;
4014 *seg_byte_offset = offset;
4016 g_assert (*segment != NULL);
4017 g_assert (*any_segment != NULL);
4018 g_assert (*seg_byte_offset < (*segment)->byte_count);
4020 *line_byte_offset = bytes_in_line + *seg_byte_offset;
4025 /* FIXME sync with byte_locate (or figure out a clean
4026 way to merge the two functions) */
4028 _gtk_text_line_char_locate (GtkTextLine *line,
4030 GtkTextLineSegment **segment,
4031 GtkTextLineSegment **any_segment,
4032 gint *seg_char_offset,
4033 gint *line_char_offset)
4035 GtkTextLineSegment *seg;
4036 GtkTextLineSegment *after_last_indexable;
4037 GtkTextLineSegment *last_indexable;
4041 g_return_val_if_fail (line != NULL, FALSE);
4042 g_return_val_if_fail (char_offset >= 0, FALSE);
4045 *any_segment = NULL;
4048 offset = char_offset;
4050 last_indexable = NULL;
4051 after_last_indexable = line->segments;
4052 seg = line->segments;
4054 /* The loop ends when we're inside a segment;
4055 last_indexable refers to the last segment
4056 we passed entirely. */
4057 while (seg && offset >= seg->char_count)
4059 if (seg->char_count > 0)
4061 offset -= seg->char_count;
4062 chars_in_line += seg->char_count;
4063 last_indexable = seg;
4064 after_last_indexable = last_indexable->next;
4072 /* end of the line */
4074 g_warning ("%s: char offset off the end of the line", G_STRLOC);
4081 if (after_last_indexable != NULL)
4082 *any_segment = after_last_indexable;
4084 *any_segment = *segment;
4087 /* Override any_segment if we're in the middle of a segment. */
4089 *any_segment = *segment;
4091 *seg_char_offset = offset;
4093 g_assert (*segment != NULL);
4094 g_assert (*any_segment != NULL);
4095 g_assert (*seg_char_offset < (*segment)->char_count);
4097 *line_char_offset = chars_in_line + *seg_char_offset;
4103 _gtk_text_line_byte_to_char_offsets (GtkTextLine *line,
4105 gint *line_char_offset,
4106 gint *seg_char_offset)
4108 GtkTextLineSegment *seg;
4111 g_return_if_fail (line != NULL);
4112 g_return_if_fail (byte_offset >= 0);
4114 *line_char_offset = 0;
4116 offset = byte_offset;
4117 seg = line->segments;
4119 while (offset >= seg->byte_count)
4121 offset -= seg->byte_count;
4122 *line_char_offset += seg->char_count;
4124 g_assert (seg != NULL); /* means an invalid char offset */
4127 g_assert (seg->char_count > 0); /* indexable. */
4129 /* offset is now the number of bytes into the current segment we
4130 * want to go. Count chars into the current segment.
4133 if (seg->type == >k_text_char_type)
4135 *seg_char_offset = g_utf8_strlen (seg->body.chars, offset);
4137 g_assert (*seg_char_offset < seg->char_count);
4139 *line_char_offset += *seg_char_offset;
4143 g_assert (offset == 0);
4144 *seg_char_offset = 0;
4149 _gtk_text_line_char_to_byte_offsets (GtkTextLine *line,
4151 gint *line_byte_offset,
4152 gint *seg_byte_offset)
4154 GtkTextLineSegment *seg;
4157 g_return_if_fail (line != NULL);
4158 g_return_if_fail (char_offset >= 0);
4160 *line_byte_offset = 0;
4162 offset = char_offset;
4163 seg = line->segments;
4165 while (offset >= seg->char_count)
4167 offset -= seg->char_count;
4168 *line_byte_offset += seg->byte_count;
4170 g_assert (seg != NULL); /* means an invalid char offset */
4173 g_assert (seg->char_count > 0); /* indexable. */
4175 /* offset is now the number of chars into the current segment we
4176 want to go. Count bytes into the current segment. */
4178 if (seg->type == >k_text_char_type)
4182 /* if in the last fourth of the segment walk backwards */
4183 if (seg->char_count - offset < seg->char_count / 4)
4184 p = g_utf8_offset_to_pointer (seg->body.chars + seg->byte_count,
4185 offset - seg->char_count);
4187 p = g_utf8_offset_to_pointer (seg->body.chars, offset);
4189 *seg_byte_offset = p - seg->body.chars;
4191 g_assert (*seg_byte_offset < seg->byte_count);
4193 *line_byte_offset += *seg_byte_offset;
4197 g_assert (offset == 0);
4198 *seg_byte_offset = 0;
4203 node_compare (GtkTextBTreeNode *lhs,
4204 GtkTextBTreeNode *rhs)
4206 GtkTextBTreeNode *iter;
4207 GtkTextBTreeNode *node;
4208 GtkTextBTreeNode *common_parent;
4209 GtkTextBTreeNode *parent_of_lower;
4210 GtkTextBTreeNode *parent_of_higher;
4211 gboolean lhs_is_lower;
4212 GtkTextBTreeNode *lower;
4213 GtkTextBTreeNode *higher;
4215 /* This function assumes that lhs and rhs are not underneath each
4222 if (lhs->level < rhs->level)
4224 lhs_is_lower = TRUE;
4230 lhs_is_lower = FALSE;
4235 /* Algorithm: find common parent of lhs/rhs. Save the child nodes
4236 * of the common parent we used to reach the common parent; the
4237 * ordering of these child nodes in the child list is the ordering
4241 /* Get on the same level (may be on same level already) */
4243 while (node->level < higher->level)
4244 node = node->parent;
4246 g_assert (node->level == higher->level);
4248 g_assert (node != higher); /* Happens if lower is underneath higher */
4250 /* Go up until we have two children with a common parent.
4252 parent_of_lower = node;
4253 parent_of_higher = higher;
4255 while (parent_of_lower->parent != parent_of_higher->parent)
4257 parent_of_lower = parent_of_lower->parent;
4258 parent_of_higher = parent_of_higher->parent;
4261 g_assert (parent_of_lower->parent == parent_of_higher->parent);
4263 common_parent = parent_of_lower->parent;
4265 g_assert (common_parent != NULL);
4267 /* See which is first in the list of common_parent's children */
4268 iter = common_parent->children.node;
4269 while (iter != NULL)
4271 if (iter == parent_of_higher)
4273 /* higher is less than lower */
4276 return 1; /* lhs > rhs */
4280 else if (iter == parent_of_lower)
4282 /* lower is less than higher */
4285 return -1; /* lhs < rhs */
4293 g_assert_not_reached ();
4297 /* remember that tag == NULL means "any tag" */
4299 _gtk_text_line_next_could_contain_tag (GtkTextLine *line,
4303 GtkTextBTreeNode *node;
4304 GtkTextTagInfo *info;
4305 gboolean below_tag_root;
4307 g_return_val_if_fail (line != NULL, NULL);
4309 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4310 _gtk_text_btree_check (tree);
4314 /* Right now we can only offer linear-search if the user wants
4315 * to know about any tag toggle at all.
4317 return _gtk_text_line_next_excluding_last (line);
4320 /* Our tag summaries only have node precision, not line
4321 * precision. This means that if any line under a node could contain a
4322 * tag, then any of the others could also contain a tag.
4324 * In the future we could have some mechanism to keep track of how
4325 * many toggles we've found under a node so far, since we have a
4326 * count of toggles under the node. But for now I'm going with KISS.
4329 /* return same-node line, if any. */
4333 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4337 if (info->tag_root == NULL)
4340 if (info->tag_root == line->parent)
4341 return NULL; /* we were at the last line under the tag root */
4343 /* We need to go up out of this node, and on to the next one with
4344 toggles for the target tag. If we're below the tag root, we need to
4345 find the next node below the tag root that has tag summaries. If
4346 we're not below the tag root, we need to see if the tag root is
4347 after us in the tree, and if so, return the first line underneath
4350 node = line->parent;
4351 below_tag_root = FALSE;
4352 while (node != NULL)
4354 if (node == info->tag_root)
4356 below_tag_root = TRUE;
4360 node = node->parent;
4365 node = line->parent;
4366 while (node != info->tag_root)
4368 if (node->next == NULL)
4369 node = node->parent;
4374 if (gtk_text_btree_node_has_tag (node, tag))
4384 ordering = node_compare (line->parent, info->tag_root);
4388 /* Tag root is ahead of us, so search there. */
4389 node = info->tag_root;
4394 /* Tag root is after us, so no more lines that
4395 * could contain the tag.
4400 g_assert_not_reached ();
4405 g_assert (node != NULL);
4407 /* We have to find the first sub-node of this node that contains
4411 while (node->level > 0)
4413 g_assert (node != NULL); /* If this fails, it likely means an
4414 incorrect tag summary led us on a
4415 wild goose chase down this branch of
4417 node = node->children.node;
4418 while (node != NULL)
4420 if (gtk_text_btree_node_has_tag (node, tag))
4426 g_assert (node != NULL);
4427 g_assert (node->level == 0);
4429 return node->children.line;
4433 prev_line_under_node (GtkTextBTreeNode *node,
4438 prev = node->children.line;
4444 while (prev->next != line)
4454 _gtk_text_line_previous_could_contain_tag (GtkTextLine *line,
4458 GtkTextBTreeNode *node;
4459 GtkTextBTreeNode *found_node = NULL;
4460 GtkTextTagInfo *info;
4461 gboolean below_tag_root;
4463 GtkTextBTreeNode *line_ancestor;
4464 GtkTextBTreeNode *line_ancestor_parent;
4466 /* See next_could_contain_tag () for more extensive comments
4467 * on what's going on here.
4470 g_return_val_if_fail (line != NULL, NULL);
4472 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4473 _gtk_text_btree_check (tree);
4477 /* Right now we can only offer linear-search if the user wants
4478 * to know about any tag toggle at all.
4480 return _gtk_text_line_previous (line);
4483 /* Return same-node line, if any. */
4484 prev = prev_line_under_node (line->parent, line);
4488 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4492 if (info->tag_root == NULL)
4495 if (info->tag_root == line->parent)
4496 return NULL; /* we were at the first line under the tag root */
4498 /* Are we below the tag root */
4499 node = line->parent;
4500 below_tag_root = FALSE;
4501 while (node != NULL)
4503 if (node == info->tag_root)
4505 below_tag_root = TRUE;
4509 node = node->parent;
4514 /* Look for a previous node under this tag root that has our
4518 /* this assertion holds because line->parent is not the
4519 * tag root, we are below the tag root, and the tag
4522 g_assert (line->parent->parent != NULL);
4524 line_ancestor = line->parent;
4525 line_ancestor_parent = line->parent->parent;
4527 while (line_ancestor != info->tag_root)
4529 GSList *child_nodes = NULL;
4532 /* Create reverse-order list of nodes before
4535 if (line_ancestor_parent != NULL)
4536 node = line_ancestor_parent->children.node;
4538 node = line_ancestor;
4540 while (node != line_ancestor && node != NULL)
4542 child_nodes = g_slist_prepend (child_nodes, node);
4547 /* Try to find a node with our tag on it in the list */
4551 GtkTextBTreeNode *this_node = tmp->data;
4553 g_assert (this_node != line_ancestor);
4555 if (gtk_text_btree_node_has_tag (this_node, tag))
4557 found_node = this_node;
4558 g_slist_free (child_nodes);
4562 tmp = g_slist_next (tmp);
4565 g_slist_free (child_nodes);
4567 /* Didn't find anything on this level; go up one level. */
4568 line_ancestor = line_ancestor_parent;
4569 line_ancestor_parent = line_ancestor->parent;
4579 ordering = node_compare (line->parent, info->tag_root);
4583 /* Tag root is ahead of us, so no more lines
4590 /* Tag root is after us, so grab last tagged
4591 * line underneath the tag root.
4593 found_node = info->tag_root;
4597 g_assert_not_reached ();
4602 g_assert (found_node != NULL);
4604 /* We have to find the last sub-node of this node that contains
4609 while (node->level > 0)
4611 GSList *child_nodes = NULL;
4613 g_assert (node != NULL); /* If this fails, it likely means an
4614 incorrect tag summary led us on a
4615 wild goose chase down this branch of
4618 node = node->children.node;
4619 while (node != NULL)
4621 child_nodes = g_slist_prepend (child_nodes, node);
4625 node = NULL; /* detect failure to find a child node. */
4628 while (iter != NULL)
4630 if (gtk_text_btree_node_has_tag (iter->data, tag))
4632 /* recurse into this node. */
4637 iter = g_slist_next (iter);
4640 g_slist_free (child_nodes);
4642 g_assert (node != NULL);
4645 g_assert (node != NULL);
4646 g_assert (node->level == 0);
4648 /* this assertion is correct, but slow. */
4649 /* g_assert (node_compare (node, line->parent) < 0); */
4651 /* Return last line in this node. */
4653 prev = node->children.line;
4661 * Non-public function implementations
4665 summary_list_destroy (Summary *summary)
4667 g_slice_free_chain (Summary, summary, next);
4671 get_last_line (GtkTextBTree *tree)
4673 if (tree->last_line_stamp != tree->chars_changed_stamp)
4679 n_lines = _gtk_text_btree_line_count (tree);
4681 g_assert (n_lines >= 1); /* num_lines doesn't return bogus last line. */
4683 line = _gtk_text_btree_get_line (tree, n_lines, &real_line);
4685 tree->last_line_stamp = tree->chars_changed_stamp;
4686 tree->last_line = line;
4689 return tree->last_line;
4697 gtk_text_line_new (void)
4701 line = g_new0(GtkTextLine, 1);
4702 line->dir_strong = PANGO_DIRECTION_NEUTRAL;
4703 line->dir_propagated_forward = PANGO_DIRECTION_NEUTRAL;
4704 line->dir_propagated_back = PANGO_DIRECTION_NEUTRAL;
4710 gtk_text_line_destroy (GtkTextBTree *tree, GtkTextLine *line)
4712 GtkTextLineData *ld;
4713 GtkTextLineData *next;
4715 g_return_if_fail (line != NULL);
4722 view = gtk_text_btree_get_view (tree, ld->view_id);
4724 g_assert (view != NULL);
4727 gtk_text_layout_free_line_data (view->layout, line, ld);
4736 gtk_text_line_set_parent (GtkTextLine *line,
4737 GtkTextBTreeNode *node)
4739 if (line->parent == node)
4741 line->parent = node;
4742 gtk_text_btree_node_invalidate_upward (node, NULL);
4746 cleanup_line (GtkTextLine *line)
4748 GtkTextLineSegment *seg, **prev_p;
4752 * Make a pass over all of the segments in the line, giving each
4753 * a chance to clean itself up. This could potentially change
4754 * the structure of the line, e.g. by merging two segments
4755 * together or having two segments cancel themselves; if so,
4756 * then repeat the whole process again, since the first structure
4757 * change might make other structure changes possible. Repeat
4758 * until eventually there are no changes.
4765 prev_p = &line->segments;
4766 for (seg = *prev_p; seg != NULL; seg = *prev_p)
4768 if (seg->type->cleanupFunc != NULL)
4770 *prev_p = (*seg->type->cleanupFunc)(seg, line);
4778 prev_p = &(*prev_p)->next;
4788 node_data_new (gpointer view_id)
4792 nd = g_slice_new (NodeData);
4794 nd->view_id = view_id;
4804 node_data_destroy (NodeData *nd)
4806 g_slice_free (NodeData, nd);
4810 node_data_list_destroy (NodeData *nd)
4812 g_slice_free_chain (NodeData, nd, next);
4816 node_data_find (NodeData *nd,
4821 if (nd->view_id == view_id)
4829 summary_destroy (Summary *summary)
4831 /* Fill with error-triggering garbage */
4832 summary->info = (void*)0x1;
4833 summary->toggle_count = 567;
4834 summary->next = (void*)0x1;
4835 g_slice_free (Summary, summary);
4838 static GtkTextBTreeNode*
4839 gtk_text_btree_node_new (void)
4841 GtkTextBTreeNode *node;
4843 node = g_new (GtkTextBTreeNode, 1);
4845 node->node_data = NULL;
4851 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
4852 GtkTextTagInfo *info,
4857 summary = node->summary;
4858 while (summary != NULL)
4860 if (summary->info == info)
4862 summary->toggle_count += adjust;
4866 summary = summary->next;
4869 if (summary == NULL)
4871 /* didn't find a summary for our tag. */
4872 g_return_if_fail (adjust > 0);
4873 summary = g_slice_new (Summary);
4874 summary->info = info;
4875 summary->toggle_count = adjust;
4876 summary->next = node->summary;
4877 node->summary = summary;
4881 /* Note that the tag root and above do not have summaries
4882 for the tag; only nodes below the tag root have
4885 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4889 summary = node->summary;
4890 while (summary != NULL)
4893 summary->info->tag == tag)
4896 summary = summary->next;
4902 /* Add node and all children to the damage region. */
4904 gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node)
4908 nd = node->node_data;
4915 if (node->level == 0)
4919 line = node->children.line;
4920 while (line != NULL)
4922 GtkTextLineData *ld;
4936 GtkTextBTreeNode *child;
4938 child = node->children.node;
4940 while (child != NULL)
4942 gtk_text_btree_node_invalidate_downward (child);
4944 child = child->next;
4950 gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node, gpointer view_id)
4952 GtkTextBTreeNode *iter;
4955 while (iter != NULL)
4961 nd = node_data_find (iter->node_data, view_id);
4963 if (nd == NULL || !nd->valid)
4964 break; /* Once a node is invalid, we know its parents are as well. */
4970 gboolean should_continue = FALSE;
4972 nd = iter->node_data;
4977 should_continue = TRUE;
4984 if (!should_continue)
4985 break; /* This node was totally invalidated, so are its
4989 iter = iter->parent;
4995 * _gtk_text_btree_is_valid:
4996 * @tree: a #GtkTextBTree
4997 * @view_id: ID for the view
4999 * Check to see if the entire #GtkTextBTree is valid or not for
5002 * Return value: %TRUE if the entire #GtkTextBTree is valid
5005 _gtk_text_btree_is_valid (GtkTextBTree *tree,
5009 g_return_val_if_fail (tree != NULL, FALSE);
5011 nd = node_data_find (tree->root_node->node_data, view_id);
5012 return (nd && nd->valid);
5015 typedef struct _ValidateState ValidateState;
5017 struct _ValidateState
5019 gint remaining_pixels;
5020 gboolean in_validation;
5027 gtk_text_btree_node_validate (BTreeView *view,
5028 GtkTextBTreeNode *node,
5030 ValidateState *state)
5032 gint node_valid = TRUE;
5033 gint node_width = 0;
5034 gint node_height = 0;
5036 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5037 g_return_if_fail (!nd->valid);
5039 if (node->level == 0)
5041 GtkTextLine *line = node->children.line;
5042 GtkTextLineData *ld;
5044 /* Iterate over leading valid lines */
5045 while (line != NULL)
5047 ld = _gtk_text_line_get_data (line, view_id);
5049 if (!ld || !ld->valid)
5051 else if (state->in_validation)
5053 state->in_validation = FALSE;
5058 state->y += ld->height;
5059 node_width = MAX (ld->width, node_width);
5060 node_height += ld->height;
5066 state->in_validation = TRUE;
5068 /* Iterate over invalid lines */
5069 while (line != NULL)
5071 ld = _gtk_text_line_get_data (line, view_id);
5073 if (ld && ld->valid)
5078 state->old_height += ld->height;
5079 ld = gtk_text_layout_wrap (view->layout, line, ld);
5080 state->new_height += ld->height;
5082 node_width = MAX (ld->width, node_width);
5083 node_height += ld->height;
5085 state->remaining_pixels -= ld->height;
5086 if (state->remaining_pixels <= 0)
5096 /* Iterate over the remaining lines */
5097 while (line != NULL)
5099 ld = _gtk_text_line_get_data (line, view_id);
5100 state->in_validation = FALSE;
5102 if (!ld || !ld->valid)
5107 node_width = MAX (ld->width, node_width);
5108 node_height += ld->height;
5116 GtkTextBTreeNode *child;
5119 child = node->children.node;
5121 /* Iterate over leading valid nodes */
5124 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5126 if (!child_nd->valid)
5128 else if (state->in_validation)
5130 state->in_validation = FALSE;
5135 state->y += child_nd->height;
5136 node_width = MAX (node_width, child_nd->width);
5137 node_height += child_nd->height;
5140 child = child->next;
5143 /* Iterate over invalid nodes */
5146 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5148 if (child_nd->valid)
5152 gtk_text_btree_node_validate (view, child, view_id, state);
5154 if (!child_nd->valid)
5156 node_width = MAX (node_width, child_nd->width);
5157 node_height += child_nd->height;
5159 if (!state->in_validation || state->remaining_pixels <= 0)
5161 child = child->next;
5166 child = child->next;
5169 /* Iterate over the remaining lines */
5172 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5173 state->in_validation = FALSE;
5175 if (!child_nd->valid)
5178 node_width = MAX (child_nd->width, node_width);
5179 node_height += child_nd->height;
5181 child = child->next;
5185 nd->width = node_width;
5186 nd->height = node_height;
5187 nd->valid = node_valid;
5191 * _gtk_text_btree_validate:
5192 * @tree: a #GtkTextBTree
5194 * @max_pixels: the maximum number of pixels to validate. (No more
5195 * than one paragraph beyond this limit will be validated)
5196 * @y: location to store starting y coordinate of validated region
5197 * @old_height: location to store old height of validated region
5198 * @new_height: location to store new height of validated region
5200 * Validate a single contiguous invalid region of a #GtkTextBTree for
5203 * Return value: %TRUE if a region has been validated, %FALSE if the
5204 * entire tree was already valid.
5207 _gtk_text_btree_validate (GtkTextBTree *tree,
5216 g_return_val_if_fail (tree != NULL, FALSE);
5218 view = gtk_text_btree_get_view (tree, view_id);
5219 g_return_val_if_fail (view != NULL, FALSE);
5221 if (!_gtk_text_btree_is_valid (tree, view_id))
5223 ValidateState state;
5225 state.remaining_pixels = max_pixels;
5226 state.in_validation = FALSE;
5228 state.old_height = 0;
5229 state.new_height = 0;
5231 gtk_text_btree_node_validate (view,
5238 *old_height = state.old_height;
5240 *new_height = state.new_height;
5242 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5243 _gtk_text_btree_check (tree);
5252 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
5256 gboolean *valid_out)
5260 gboolean valid = TRUE;
5262 if (node->level == 0)
5264 GtkTextLine *line = node->children.line;
5266 while (line != NULL)
5268 GtkTextLineData *ld = _gtk_text_line_get_data (line, view_id);
5270 if (!ld || !ld->valid)
5275 width = MAX (ld->width, width);
5276 height += ld->height;
5284 GtkTextBTreeNode *child = node->children.node;
5288 NodeData *child_nd = node_data_find (child->node_data, view_id);
5290 if (!child_nd || !child_nd->valid)
5295 width = MAX (child_nd->width, width);
5296 height += child_nd->height;
5299 child = child->next;
5304 *height_out = height;
5309 /* Recompute the validity and size of the view data for a given
5310 * view at this node from the immediate children of the node
5313 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
5316 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5321 gtk_text_btree_node_compute_view_aggregates (node, view_id,
5322 &width, &height, &valid);
5324 nd->height = height;
5331 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
5336 gtk_text_btree_node_check_valid (node, view_id);
5337 node = node->parent;
5342 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
5345 if (node->level == 0)
5347 return gtk_text_btree_node_check_valid (node, view_id);
5351 GtkTextBTreeNode *child = node->children.node;
5353 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5361 NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
5363 if (!child_nd->valid)
5365 nd->width = MAX (child_nd->width, nd->width);
5366 nd->height += child_nd->height;
5368 child = child->next;
5377 * _gtk_text_btree_validate_line:
5378 * @tree: a #GtkTextBTree
5379 * @line: line to validate
5380 * @view_id: view ID for the view to validate
5382 * Revalidate a single line of the btree for the given view, propagate
5383 * results up through the entire tree.
5386 _gtk_text_btree_validate_line (GtkTextBTree *tree,
5390 GtkTextLineData *ld;
5393 g_return_if_fail (tree != NULL);
5394 g_return_if_fail (line != NULL);
5396 view = gtk_text_btree_get_view (tree, view_id);
5397 g_return_if_fail (view != NULL);
5399 ld = _gtk_text_line_get_data (line, view_id);
5400 if (!ld || !ld->valid)
5402 ld = gtk_text_layout_wrap (view->layout, line, ld);
5404 gtk_text_btree_node_check_valid_upward (line->parent, view_id);
5409 gtk_text_btree_node_remove_view (BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
5411 if (node->level == 0)
5415 line = node->children.line;
5416 while (line != NULL)
5418 GtkTextLineData *ld;
5420 ld = _gtk_text_line_remove_data (line, view_id);
5423 gtk_text_layout_free_line_data (view->layout, line, ld);
5430 GtkTextBTreeNode *child;
5432 child = node->children.node;
5434 while (child != NULL)
5437 gtk_text_btree_node_remove_view (view, child, view_id);
5439 child = child->next;
5443 gtk_text_btree_node_remove_data (node, view_id);
5447 gtk_text_btree_node_destroy (GtkTextBTree *tree, GtkTextBTreeNode *node)
5449 if (node->level == 0)
5452 GtkTextLineSegment *seg;
5454 while (node->children.line != NULL)
5456 line = node->children.line;
5457 node->children.line = line->next;
5458 while (line->segments != NULL)
5460 seg = line->segments;
5461 line->segments = seg->next;
5463 (*seg->type->deleteFunc) (seg, line, TRUE);
5465 gtk_text_line_destroy (tree, line);
5470 GtkTextBTreeNode *childPtr;
5472 while (node->children.node != NULL)
5474 childPtr = node->children.node;
5475 node->children.node = childPtr->next;
5476 gtk_text_btree_node_destroy (tree, childPtr);
5480 gtk_text_btree_node_free_empty (tree, node);
5484 gtk_text_btree_node_free_empty (GtkTextBTree *tree,
5485 GtkTextBTreeNode *node)
5487 g_return_if_fail ((node->level > 0 && node->children.node == NULL) ||
5488 (node->level == 0 && node->children.line == NULL));
5490 summary_list_destroy (node->summary);
5491 node_data_list_destroy (node->node_data);
5496 gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node, gpointer view_id)
5500 nd = node->node_data;
5503 if (nd->view_id == view_id)
5511 nd = node_data_new (view_id);
5513 if (node->node_data)
5514 nd->next = node->node_data;
5516 node->node_data = nd;
5523 gtk_text_btree_node_remove_data (GtkTextBTreeNode *node, gpointer view_id)
5529 nd = node->node_data;
5532 if (nd->view_id == view_id)
5543 prev->next = nd->next;
5545 if (node->node_data == nd)
5546 node->node_data = nd->next;
5550 node_data_destroy (nd);
5554 gtk_text_btree_node_get_size (GtkTextBTreeNode *node, gpointer view_id,
5555 gint *width, gint *height)
5559 g_return_if_fail (width != NULL);
5560 g_return_if_fail (height != NULL);
5562 nd = gtk_text_btree_node_ensure_data (node, view_id);
5567 *height = nd->height;
5570 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5571 * here isn't quite right, since for a lot of operations we want to
5572 * know which children of the common parent correspond to the two nodes
5573 * (e.g., when computing the order of two iters)
5575 static GtkTextBTreeNode *
5576 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5577 GtkTextBTreeNode *node2)
5579 while (node1->level < node2->level)
5580 node1 = node1->parent;
5581 while (node2->level < node1->level)
5582 node2 = node2->parent;
5583 while (node1 != node2)
5585 node1 = node1->parent;
5586 node2 = node2->parent;
5597 gtk_text_btree_get_view (GtkTextBTree *tree, gpointer view_id)
5602 while (view != NULL)
5604 if (view->view_id == view_id)
5613 get_tree_bounds (GtkTextBTree *tree,
5617 _gtk_text_btree_get_iter_at_line_char (tree, start, 0, 0);
5618 _gtk_text_btree_get_end_iter (tree, end);
5622 tag_changed_cb (GtkTextTagTable *table,
5624 gboolean size_changed,
5629 /* We need to queue a relayout on all regions that are tagged with
5636 if (_gtk_text_btree_get_iter_at_first_toggle (tree, &start, tag))
5638 /* Must be a last toggle if there was a first one. */
5639 _gtk_text_btree_get_iter_at_last_toggle (tree, &end, tag);
5640 DV (g_print ("invalidating due to tag change (%s)\n", G_STRLOC));
5641 _gtk_text_btree_invalidate_region (tree, &start, &end, FALSE);
5647 /* We only need to queue a redraw, not a relayout */
5652 while (view != NULL)
5656 _gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5657 gtk_text_layout_changed (view->layout, 0, height, height);
5665 _gtk_text_btree_notify_will_remove_tag (GtkTextBTree *tree,
5668 /* Remove the tag from the tree */
5673 get_tree_bounds (tree, &start, &end);
5675 _gtk_text_btree_tag (&start, &end, tag, FALSE);
5676 gtk_text_btree_remove_tag_info (tree, tag);
5680 /* Rebalance the out-of-whack node "node" */
5682 gtk_text_btree_rebalance (GtkTextBTree *tree,
5683 GtkTextBTreeNode *node)
5686 * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5687 * up through the tree one GtkTextBTreeNode at a time until the root
5688 * GtkTextBTreeNode has been processed.
5691 while (node != NULL)
5693 GtkTextBTreeNode *new_node, *child;
5698 * Check to see if the GtkTextBTreeNode has too many children. If it does,
5699 * then split off all but the first MIN_CHILDREN into a separate
5700 * GtkTextBTreeNode following the original one. Then repeat until the
5701 * GtkTextBTreeNode has a decent size.
5704 if (node->num_children > MAX_CHILDREN)
5709 * If the GtkTextBTreeNode being split is the root
5710 * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5714 if (node->parent == NULL)
5716 new_node = gtk_text_btree_node_new ();
5717 new_node->parent = NULL;
5718 new_node->next = NULL;
5719 new_node->summary = NULL;
5720 new_node->level = node->level + 1;
5721 new_node->children.node = node;
5722 recompute_node_counts (tree, new_node);
5723 tree->root_node = new_node;
5725 new_node = gtk_text_btree_node_new ();
5726 new_node->parent = node->parent;
5727 new_node->next = node->next;
5728 node->next = new_node;
5729 new_node->summary = NULL;
5730 new_node->level = node->level;
5731 new_node->num_children = node->num_children - MIN_CHILDREN;
5732 if (node->level == 0)
5734 for (i = MIN_CHILDREN-1,
5735 line = node->children.line;
5736 i > 0; i--, line = line->next)
5738 /* Empty loop body. */
5740 new_node->children.line = line->next;
5745 for (i = MIN_CHILDREN-1,
5746 child = node->children.node;
5747 i > 0; i--, child = child->next)
5749 /* Empty loop body. */
5751 new_node->children.node = child->next;
5754 recompute_node_counts (tree, node);
5755 node->parent->num_children++;
5757 if (node->num_children <= MAX_CHILDREN)
5759 recompute_node_counts (tree, node);
5765 while (node->num_children < MIN_CHILDREN)
5767 GtkTextBTreeNode *other;
5768 GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5769 GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5770 int total_children, first_children, i;
5773 * Too few children for this GtkTextBTreeNode. If this is the root then,
5774 * it's OK for it to have less than MIN_CHILDREN children
5775 * as long as it's got at least two. If it has only one
5776 * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5777 * the tree and use its child as the new root.
5780 if (node->parent == NULL)
5782 if ((node->num_children == 1) && (node->level > 0))
5784 tree->root_node = node->children.node;
5785 tree->root_node->parent = NULL;
5787 node->children.node = NULL;
5788 gtk_text_btree_node_free_empty (tree, node);
5794 * Not the root. Make sure that there are siblings to
5798 if (node->parent->num_children < 2)
5800 gtk_text_btree_rebalance (tree, node->parent);
5805 * Find a sibling neighbor to borrow from, and arrange for
5806 * node to be the earlier of the pair.
5809 if (node->next == NULL)
5811 for (other = node->parent->children.node;
5812 other->next != node;
5813 other = other->next)
5815 /* Empty loop body. */
5822 * We're going to either merge the two siblings together
5823 * into one GtkTextBTreeNode or redivide the children among them to
5824 * balance their loads. As preparation, join their two
5825 * child lists into a single list and remember the half-way
5826 * point in the list.
5829 total_children = node->num_children + other->num_children;
5830 first_children = total_children/2;
5831 if (node->children.node == NULL)
5833 node->children = other->children;
5834 other->children.node = NULL;
5835 other->children.line = NULL;
5837 if (node->level == 0)
5841 for (line = node->children.line, i = 1;
5843 line = line->next, i++)
5845 if (i == first_children)
5850 line->next = other->children.line;
5851 while (i <= first_children)
5860 GtkTextBTreeNode *child;
5862 for (child = node->children.node, i = 1;
5863 child->next != NULL;
5864 child = child->next, i++)
5866 if (i <= first_children)
5868 if (i == first_children)
5870 halfwaynode = child;
5874 child->next = other->children.node;
5875 while (i <= first_children)
5877 halfwaynode = child;
5878 child = child->next;
5884 * If the two siblings can simply be merged together, do it.
5887 if (total_children <= MAX_CHILDREN)
5889 recompute_node_counts (tree, node);
5890 node->next = other->next;
5891 node->parent->num_children--;
5893 other->children.node = NULL;
5894 other->children.line = NULL;
5895 gtk_text_btree_node_free_empty (tree, other);
5900 * The siblings can't be merged, so just divide their
5901 * children evenly between them.
5904 if (node->level == 0)
5906 other->children.line = halfwayline->next;
5907 halfwayline->next = NULL;
5911 other->children.node = halfwaynode->next;
5912 halfwaynode->next = NULL;
5915 recompute_node_counts (tree, node);
5916 recompute_node_counts (tree, other);
5919 node = node->parent;
5924 post_insert_fixup (GtkTextBTree *tree,
5926 gint line_count_delta,
5927 gint char_count_delta)
5930 GtkTextBTreeNode *node;
5933 * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5934 * point, then rebalance the tree if necessary.
5937 for (node = line->parent ; node != NULL;
5938 node = node->parent)
5940 node->num_lines += line_count_delta;
5941 node->num_chars += char_count_delta;
5943 node = line->parent;
5944 node->num_children += line_count_delta;
5946 if (node->num_children > MAX_CHILDREN)
5948 gtk_text_btree_rebalance (tree, node);
5951 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5952 _gtk_text_btree_check (tree);
5955 static GtkTextTagInfo*
5956 gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
5959 GtkTextTagInfo *info;
5963 list = tree->tag_infos;
5964 while (list != NULL)
5967 if (info->tag == tag)
5970 list = g_slist_next (list);
5976 static GtkTextTagInfo*
5977 gtk_text_btree_get_tag_info (GtkTextBTree *tree,
5980 GtkTextTagInfo *info;
5982 info = gtk_text_btree_get_existing_tag_info (tree, tag);
5986 /* didn't find it, create. */
5988 info = g_slice_new (GtkTextTagInfo);
5992 info->tag_root = NULL;
5993 info->toggle_count = 0;
5995 tree->tag_infos = g_slist_prepend (tree->tag_infos, info);
5998 g_print ("Created tag info %p for tag %s(%p)\n",
5999 info, info->tag->name ? info->tag->name : "anon",
6008 gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
6011 GtkTextTagInfo *info;
6016 list = tree->tag_infos;
6017 while (list != NULL)
6020 if (info->tag == tag)
6023 g_print ("Removing tag info %p for tag %s(%p)\n",
6024 info, info->tag->name ? info->tag->name : "anon",
6030 prev->next = list->next;
6034 tree->tag_infos = list->next;
6037 g_slist_free (list);
6039 g_object_unref (info->tag);
6041 g_slice_free (GtkTextTagInfo, info);
6046 list = g_slist_next (list);
6051 recompute_level_zero_counts (GtkTextBTreeNode *node)
6054 GtkTextLineSegment *seg;
6056 g_assert (node->level == 0);
6058 line = node->children.line;
6059 while (line != NULL)
6061 node->num_children++;
6064 if (line->parent != node)
6065 gtk_text_line_set_parent (line, node);
6067 seg = line->segments;
6071 node->num_chars += seg->char_count;
6073 if (((seg->type != >k_text_toggle_on_type)
6074 && (seg->type != >k_text_toggle_off_type))
6075 || !(seg->body.toggle.inNodeCounts))
6081 GtkTextTagInfo *info;
6083 info = seg->body.toggle.info;
6085 gtk_text_btree_node_adjust_toggle_count (node, info, 1);
6096 recompute_level_nonzero_counts (GtkTextBTreeNode *node)
6099 GtkTextBTreeNode *child;
6101 g_assert (node->level > 0);
6103 child = node->children.node;
6104 while (child != NULL)
6106 node->num_children += 1;
6107 node->num_lines += child->num_lines;
6108 node->num_chars += child->num_chars;
6110 if (child->parent != node)
6112 child->parent = node;
6113 gtk_text_btree_node_invalidate_upward (node, NULL);
6116 summary = child->summary;
6117 while (summary != NULL)
6119 gtk_text_btree_node_adjust_toggle_count (node,
6121 summary->toggle_count);
6123 summary = summary->next;
6126 child = child->next;
6131 *----------------------------------------------------------------------
6133 * recompute_node_counts --
6135 * This procedure is called to recompute all the counts in a GtkTextBTreeNode
6136 * (tags, child information, etc.) by scanning the information in
6137 * its descendants. This procedure is called during rebalancing
6138 * when a GtkTextBTreeNode's child structure has changed.
6144 * The tag counts for node are modified to reflect its current
6145 * child structure, as are its num_children, num_lines, num_chars fields.
6146 * Also, all of the childrens' parent fields are made to point
6149 *----------------------------------------------------------------------
6153 recompute_node_counts (GtkTextBTree *tree, GtkTextBTreeNode *node)
6156 Summary *summary, *summary2;
6159 * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
6160 * the existing Summary records (most of them will probably be reused).
6163 summary = node->summary;
6164 while (summary != NULL)
6166 summary->toggle_count = 0;
6167 summary = summary->next;
6170 node->num_children = 0;
6171 node->num_lines = 0;
6172 node->num_chars = 0;
6175 * Scan through the children, adding the childrens' tag counts into
6176 * the GtkTextBTreeNode's tag counts and adding new Summary structures if
6180 if (node->level == 0)
6181 recompute_level_zero_counts (node);
6183 recompute_level_nonzero_counts (node);
6188 gtk_text_btree_node_check_valid (node, view->view_id);
6193 * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
6194 * records that still have a zero count, or that have all the toggles.
6195 * The GtkTextBTreeNode with the children that account for all the tags toggles
6196 * have no summary information, and they become the tag_root for the tag.
6200 for (summary = node->summary; summary != NULL; )
6202 if (summary->toggle_count > 0 &&
6203 summary->toggle_count < summary->info->toggle_count)
6205 if (node->level == summary->info->tag_root->level)
6208 * The tag's root GtkTextBTreeNode split and some toggles left.
6209 * The tag root must move up a level.
6211 summary->info->tag_root = node->parent;
6214 summary = summary->next;
6217 if (summary->toggle_count == summary->info->toggle_count)
6220 * A GtkTextBTreeNode merge has collected all the toggles under
6221 * one GtkTextBTreeNode. Push the root down to this level.
6223 summary->info->tag_root = node;
6225 if (summary2 != NULL)
6227 summary2->next = summary->next;
6228 summary_destroy (summary);
6229 summary = summary2->next;
6233 node->summary = summary->next;
6234 summary_destroy (summary);
6235 summary = node->summary;
6241 _gtk_change_node_toggle_count (GtkTextBTreeNode *node,
6242 GtkTextTagInfo *info,
6243 gint delta) /* may be negative */
6245 Summary *summary, *prevPtr;
6246 GtkTextBTreeNode *node2Ptr;
6247 int rootLevel; /* Level of original tag root */
6249 info->toggle_count += delta;
6251 if (info->tag_root == (GtkTextBTreeNode *) NULL)
6253 info->tag_root = node;
6258 * Note the level of the existing root for the tag so we can detect
6259 * if it needs to be moved because of the toggle count change.
6262 rootLevel = info->tag_root->level;
6265 * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
6266 * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
6270 for ( ; node != info->tag_root; node = node->parent)
6273 * See if there's already an entry for this tag for this GtkTextBTreeNode. If so,
6274 * perhaps all we have to do is adjust its count.
6277 for (prevPtr = NULL, summary = node->summary;
6279 prevPtr = summary, summary = summary->next)
6281 if (summary->info == info)
6286 if (summary != NULL)
6288 summary->toggle_count += delta;
6289 if (summary->toggle_count > 0 &&
6290 summary->toggle_count < info->toggle_count)
6294 if (summary->toggle_count != 0)
6297 * Should never find a GtkTextBTreeNode with max toggle count at this
6298 * point (there shouldn't have been a summary entry in the
6302 g_error ("%s: bad toggle count (%d) max (%d)",
6303 G_STRLOC, summary->toggle_count, info->toggle_count);
6307 * Zero toggle count; must remove this tag from the list.
6310 if (prevPtr == NULL)
6312 node->summary = summary->next;
6316 prevPtr->next = summary->next;
6318 summary_destroy (summary);
6323 * This tag isn't currently in the summary information list.
6326 if (rootLevel == node->level)
6330 * The old tag root is at the same level in the tree as this
6331 * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode. Move the tag root up
6332 * a level, in the hopes that it will now cover this GtkTextBTreeNode
6333 * as well as the old root (if not, we'll move it up again
6334 * the next time through the loop). To push it up one level
6335 * we copy the original toggle count into the summary
6336 * information at the old root and change the root to its
6337 * parent GtkTextBTreeNode.
6340 GtkTextBTreeNode *rootnode = info->tag_root;
6341 summary = g_slice_new (Summary);
6342 summary->info = info;
6343 summary->toggle_count = info->toggle_count - delta;
6344 summary->next = rootnode->summary;
6345 rootnode->summary = summary;
6346 rootnode = rootnode->parent;
6347 rootLevel = rootnode->level;
6348 info->tag_root = rootnode;
6350 summary = g_slice_new (Summary);
6351 summary->info = info;
6352 summary->toggle_count = delta;
6353 summary->next = node->summary;
6354 node->summary = summary;
6359 * If we've decremented the toggle count, then it may be necessary
6360 * to push the tag root down one or more levels.
6367 if (info->toggle_count == 0)
6369 info->tag_root = (GtkTextBTreeNode *) NULL;
6372 node = info->tag_root;
6373 while (node->level > 0)
6376 * See if a single child GtkTextBTreeNode accounts for all of the tag's
6377 * toggles. If so, push the root down one level.
6380 for (node2Ptr = node->children.node;
6381 node2Ptr != (GtkTextBTreeNode *)NULL ;
6382 node2Ptr = node2Ptr->next)
6384 for (prevPtr = NULL, summary = node2Ptr->summary;
6386 prevPtr = summary, summary = summary->next)
6388 if (summary->info == info)
6393 if (summary == NULL)
6397 if (summary->toggle_count != info->toggle_count)
6400 * No GtkTextBTreeNode has all toggles, so the root is still valid.
6407 * This GtkTextBTreeNode has all the toggles, so push down the root.
6410 if (prevPtr == NULL)
6412 node2Ptr->summary = summary->next;
6416 prevPtr->next = summary->next;
6418 summary_destroy (summary);
6419 info->tag_root = node2Ptr;
6422 node = info->tag_root;
6427 *----------------------------------------------------------------------
6431 * This is a utility procedure used by _gtk_text_btree_get_tags. It
6432 * increments the count for a particular tag, adding a new
6433 * entry for that tag if there wasn't one previously.
6439 * The information at *tagInfoPtr may be modified, and the arrays
6440 * may be reallocated to make them larger.
6442 *----------------------------------------------------------------------
6446 inc_count (GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
6451 for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
6452 count > 0; tag_p++, count--)
6456 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
6462 * There isn't currently an entry for this tag, so we have to
6463 * make a new one. If the arrays are full, then enlarge the
6467 if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
6469 GtkTextTag **newTags;
6470 int *newCounts, newSize;
6472 newSize = 2*tagInfoPtr->arraySize;
6473 newTags = (GtkTextTag **) g_malloc ((unsigned)
6474 (newSize*sizeof (GtkTextTag *)));
6475 memcpy ((void *) newTags, (void *) tagInfoPtr->tags,
6476 tagInfoPtr->arraySize *sizeof (GtkTextTag *));
6477 g_free ((char *) tagInfoPtr->tags);
6478 tagInfoPtr->tags = newTags;
6479 newCounts = (int *) g_malloc ((unsigned) (newSize*sizeof (int)));
6480 memcpy ((void *) newCounts, (void *) tagInfoPtr->counts,
6481 tagInfoPtr->arraySize *sizeof (int));
6482 g_free ((char *) tagInfoPtr->counts);
6483 tagInfoPtr->counts = newCounts;
6484 tagInfoPtr->arraySize = newSize;
6487 tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
6488 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
6489 tagInfoPtr->numTags++;
6493 gtk_text_btree_link_segment (GtkTextLineSegment *seg,
6494 const GtkTextIter *iter)
6496 GtkTextLineSegment *prev;
6500 line = _gtk_text_iter_get_text_line (iter);
6501 tree = _gtk_text_iter_get_btree (iter);
6503 prev = gtk_text_line_segment_split (iter);
6506 seg->next = line->segments;
6507 line->segments = seg;
6511 seg->next = prev->next;
6514 cleanup_line (line);
6515 segments_changed (tree);
6517 if (gtk_debug_flags & GTK_DEBUG_TEXT)
6518 _gtk_text_btree_check (tree);
6522 gtk_text_btree_unlink_segment (GtkTextBTree *tree,
6523 GtkTextLineSegment *seg,
6526 GtkTextLineSegment *prev;
6528 if (line->segments == seg)
6530 line->segments = seg->next;
6534 for (prev = line->segments; prev->next != seg;
6537 /* Empty loop body. */
6539 prev->next = seg->next;
6541 cleanup_line (line);
6542 segments_changed (tree);
6546 * This is here because it requires BTree internals, it logically
6547 * belongs in gtktextsegment.c
6552 *--------------------------------------------------------------
6554 * _gtk_toggle_segment_check_func --
6556 * This procedure is invoked to perform consistency checks
6557 * on toggle segments.
6563 * If a consistency problem is found the procedure g_errors.
6565 *--------------------------------------------------------------
6569 _gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6575 if (segPtr->byte_count != 0)
6577 g_error ("toggle_segment_check_func: segment had non-zero size");
6579 if (!segPtr->body.toggle.inNodeCounts)
6581 g_error ("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6583 needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6584 for (summary = line->parent->summary; ;
6585 summary = summary->next)
6587 if (summary == NULL)
6591 g_error ("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6598 if (summary->info == segPtr->body.toggle.info)
6602 g_error ("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6614 gtk_text_btree_node_view_check_consistency (GtkTextBTree *tree,
6615 GtkTextBTreeNode *node,
6625 while (view != NULL)
6627 if (view->view_id == nd->view_id)
6634 g_error ("Node has data for a view %p no longer attached to the tree",
6637 gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6638 &width, &height, &valid);
6640 /* valid aggregate not checked the same as width/height, because on
6641 * btree rebalance we can have invalid nodes where all lines below
6642 * them are actually valid, due to moving lines around between
6645 * The guarantee is that if there are invalid lines the node is
6646 * invalid - we don't guarantee that if the node is invalid there
6647 * are invalid lines.
6650 if (nd->width != width ||
6651 nd->height != height ||
6652 (nd->valid && !valid))
6654 g_error ("Node aggregates for view %p are invalid:\n"
6655 "Are (%d,%d,%s), should be (%d,%d,%s)",
6657 nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6658 width, height, valid ? "TRUE" : "FALSE");
6663 gtk_text_btree_node_check_consistency (GtkTextBTree *tree,
6664 GtkTextBTreeNode *node)
6666 GtkTextBTreeNode *childnode;
6667 Summary *summary, *summary2;
6669 GtkTextLineSegment *segPtr;
6670 int num_children, num_lines, num_chars, toggle_count, min_children;
6671 GtkTextLineData *ld;
6674 if (node->parent != NULL)
6676 min_children = MIN_CHILDREN;
6678 else if (node->level > 0)
6685 if ((node->num_children < min_children)
6686 || (node->num_children > MAX_CHILDREN))
6688 g_error ("gtk_text_btree_node_check_consistency: bad child count (%d)",
6689 node->num_children);
6692 nd = node->node_data;
6695 gtk_text_btree_node_view_check_consistency (tree, node, nd);
6702 if (node->level == 0)
6704 for (line = node->children.line; line != NULL;
6707 if (line->parent != node)
6709 g_error ("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6711 if (line->segments == NULL)
6713 g_error ("gtk_text_btree_node_check_consistency: line has no segments");
6719 /* Just ensuring we don't segv while doing this loop */
6724 for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6726 if (segPtr->type->checkFunc != NULL)
6728 (*segPtr->type->checkFunc)(segPtr, line);
6730 if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6731 && (segPtr->next != NULL)
6732 && (segPtr->next->byte_count == 0)
6733 && (segPtr->next->type->leftGravity))
6735 g_error ("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6737 if ((segPtr->next == NULL)
6738 && (segPtr->type != >k_text_char_type))
6740 g_error ("gtk_text_btree_node_check_consistency: line ended with wrong type");
6743 num_chars += segPtr->char_count;
6752 for (childnode = node->children.node; childnode != NULL;
6753 childnode = childnode->next)
6755 if (childnode->parent != node)
6757 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6759 if (childnode->level != (node->level-1))
6761 g_error ("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6762 node->level, childnode->level);
6764 gtk_text_btree_node_check_consistency (tree, childnode);
6765 for (summary = childnode->summary; summary != NULL;
6766 summary = summary->next)
6768 for (summary2 = node->summary; ;
6769 summary2 = summary2->next)
6771 if (summary2 == NULL)
6773 if (summary->info->tag_root == node)
6777 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6778 summary->info->tag->name,
6779 "present in parent summaries");
6781 if (summary->info == summary2->info)
6788 num_lines += childnode->num_lines;
6789 num_chars += childnode->num_chars;
6792 if (num_children != node->num_children)
6794 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6795 num_children, node->num_children);
6797 if (num_lines != node->num_lines)
6799 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6800 num_lines, node->num_lines);
6802 if (num_chars != node->num_chars)
6804 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6805 num_chars, node->num_chars);
6808 for (summary = node->summary; summary != NULL;
6809 summary = summary->next)
6811 if (summary->info->toggle_count == summary->toggle_count)
6813 g_error ("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6814 summary->info->tag->name);
6817 if (node->level == 0)
6819 for (line = node->children.line; line != NULL;
6822 for (segPtr = line->segments; segPtr != NULL;
6823 segPtr = segPtr->next)
6825 if ((segPtr->type != >k_text_toggle_on_type)
6826 && (segPtr->type != >k_text_toggle_off_type))
6830 if (segPtr->body.toggle.info == summary->info)
6832 if (!segPtr->body.toggle.inNodeCounts)
6833 g_error ("Toggle segment not in the node counts");
6842 for (childnode = node->children.node;
6844 childnode = childnode->next)
6846 for (summary2 = childnode->summary;
6848 summary2 = summary2->next)
6850 if (summary2->info == summary->info)
6852 toggle_count += summary2->toggle_count;
6857 if (toggle_count != summary->toggle_count)
6859 g_error ("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6860 toggle_count, summary->toggle_count);
6862 for (summary2 = summary->next; summary2 != NULL;
6863 summary2 = summary2->next)
6865 if (summary2->info == summary->info)
6867 g_error ("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6868 summary->info->tag->name);
6875 listify_foreach (GtkTextTag *tag, gpointer user_data)
6877 GSList** listp = user_data;
6879 *listp = g_slist_prepend (*listp, tag);
6883 list_of_tags (GtkTextTagTable *table)
6885 GSList *list = NULL;
6887 gtk_text_tag_table_foreach (table, listify_foreach, &list);
6893 _gtk_text_btree_check (GtkTextBTree *tree)
6896 GtkTextBTreeNode *node;
6898 GtkTextLineSegment *seg;
6900 GSList *all_tags, *taglist = NULL;
6902 GtkTextTagInfo *info;
6905 * Make sure that the tag toggle counts and the tag root pointers are OK.
6907 all_tags = list_of_tags (tree->table);
6908 for (taglist = all_tags; taglist != NULL ; taglist = taglist->next)
6910 tag = taglist->data;
6911 info = gtk_text_btree_get_existing_tag_info (tree, tag);
6914 node = info->tag_root;
6917 if (info->toggle_count != 0)
6919 g_error ("_gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6920 tag->name, info->toggle_count);
6922 continue; /* no ranges for the tag */
6924 else if (info->toggle_count == 0)
6926 g_error ("_gtk_text_btree_check found root for \"%s\" with no toggles",
6929 else if (info->toggle_count & 1)
6931 g_error ("_gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6932 tag->name, info->toggle_count);
6934 for (summary = node->summary; summary != NULL;
6935 summary = summary->next)
6937 if (summary->info->tag == tag)
6939 g_error ("_gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6943 if (node->level > 0)
6945 for (node = node->children.node ; node != NULL ;
6948 for (summary = node->summary; summary != NULL;
6949 summary = summary->next)
6951 if (summary->info->tag == tag)
6953 count += summary->toggle_count;
6960 const GtkTextLineSegmentClass *last = NULL;
6962 for (line = node->children.line ; line != NULL ;
6965 for (seg = line->segments; seg != NULL;
6968 if ((seg->type == >k_text_toggle_on_type ||
6969 seg->type == >k_text_toggle_off_type) &&
6970 seg->body.toggle.info->tag == tag)
6972 if (last == seg->type)
6973 g_error ("Two consecutive toggles on or off weren't merged");
6974 if (!seg->body.toggle.inNodeCounts)
6975 g_error ("Toggle segment not in the node counts");
6984 if (count != info->toggle_count)
6986 g_error ("_gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
6987 info->toggle_count, tag->name, count);
6992 g_slist_free (all_tags);
6995 * Call a recursive procedure to do the main body of checks.
6998 node = tree->root_node;
6999 gtk_text_btree_node_check_consistency (tree, tree->root_node);
7002 * Make sure that there are at least two lines in the text and
7003 * that the last line has no characters except a newline.
7006 if (node->num_lines < 2)
7008 g_error ("_gtk_text_btree_check: less than 2 lines in tree");
7010 if (node->num_chars < 2)
7012 g_error ("_gtk_text_btree_check: less than 2 chars in tree");
7014 while (node->level > 0)
7016 node = node->children.node;
7017 while (node->next != NULL)
7022 line = node->children.line;
7023 while (line->next != NULL)
7027 seg = line->segments;
7028 while ((seg->type == >k_text_toggle_off_type)
7029 || (seg->type == >k_text_right_mark_type)
7030 || (seg->type == >k_text_left_mark_type))
7033 * It's OK to toggle a tag off in the last line, but
7034 * not to start a new range. It's also OK to have marks
7040 if (seg->type != >k_text_char_type)
7042 g_error ("_gtk_text_btree_check: last line has bogus segment type");
7044 if (seg->next != NULL)
7046 g_error ("_gtk_text_btree_check: last line has too many segments");
7048 if (seg->byte_count != 1)
7050 g_error ("_gtk_text_btree_check: last line has wrong # characters: %d",
7053 if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
7055 g_error ("_gtk_text_btree_check: last line had bad value: %s",
7060 void _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line);
7061 void _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment* seg);
7062 void _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent);
7063 void _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
7066 _gtk_text_btree_spew (GtkTextBTree *tree)
7071 printf ("%d lines in tree %p\n",
7072 _gtk_text_btree_line_count (tree), tree);
7074 line = _gtk_text_btree_get_line (tree, 0, &real_line);
7076 while (line != NULL)
7078 _gtk_text_btree_spew_line (tree, line);
7079 line = _gtk_text_line_next (line);
7082 printf ("=================== Tag information\n");
7087 list = tree->tag_infos;
7089 while (list != NULL)
7091 GtkTextTagInfo *info;
7095 printf (" tag `%s': root at %p, toggle count %d\n",
7096 info->tag->name, info->tag_root, info->toggle_count);
7098 list = g_slist_next (list);
7101 if (tree->tag_infos == NULL)
7103 printf (" (no tags in the tree)\n");
7107 printf ("=================== Tree nodes\n");
7110 _gtk_text_btree_spew_node (tree->root_node, 0);
7115 _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
7118 GtkTextLineSegment *seg;
7120 spaces = g_strnfill (indent, ' ');
7122 printf ("%sline %p chars %d bytes %d\n",
7124 _gtk_text_line_char_count (line),
7125 _gtk_text_line_byte_count (line));
7127 seg = line->segments;
7130 if (seg->type == >k_text_char_type)
7132 gchar* str = g_strndup (seg->body.chars, MIN (seg->byte_count, 10));
7137 if (*s == '\n' || *s == '\r')
7141 printf ("%s chars `%s'...\n", spaces, str);
7144 else if (seg->type == >k_text_right_mark_type)
7146 printf ("%s right mark `%s' visible: %d\n",
7148 seg->body.mark.name,
7149 seg->body.mark.visible);
7151 else if (seg->type == >k_text_left_mark_type)
7153 printf ("%s left mark `%s' visible: %d\n",
7155 seg->body.mark.name,
7156 seg->body.mark.visible);
7158 else if (seg->type == >k_text_toggle_on_type ||
7159 seg->type == >k_text_toggle_off_type)
7161 printf ("%s tag `%s' %s\n",
7162 spaces, seg->body.toggle.info->tag->name,
7163 seg->type == >k_text_toggle_off_type ? "off" : "on");
7173 _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent)
7176 GtkTextBTreeNode *iter;
7179 spaces = g_strnfill (indent, ' ');
7181 printf ("%snode %p level %d children %d lines %d chars %d\n",
7182 spaces, node, node->level,
7183 node->num_children, node->num_lines, node->num_chars);
7188 printf ("%s %d toggles of `%s' below this node\n",
7189 spaces, s->toggle_count, s->info->tag->name);
7195 if (node->level > 0)
7197 iter = node->children.node;
7198 while (iter != NULL)
7200 _gtk_text_btree_spew_node (iter, indent + 2);
7207 GtkTextLine *line = node->children.line;
7208 while (line != NULL)
7210 _gtk_text_btree_spew_line_short (line, indent + 2);
7218 _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line)
7220 GtkTextLineSegment * seg;
7222 printf ("%4d| line: %p parent: %p next: %p\n",
7223 _gtk_text_line_get_number (line), line, line->parent, line->next);
7225 seg = line->segments;
7229 _gtk_text_btree_spew_segment (tree, seg);
7235 _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment * seg)
7237 printf (" segment: %p type: %s bytes: %d chars: %d\n",
7238 seg, seg->type->name, seg->byte_count, seg->char_count);
7240 if (seg->type == >k_text_char_type)
7242 gchar* str = g_strndup (seg->body.chars, seg->byte_count);
7243 printf (" `%s'\n", str);
7246 else if (seg->type == >k_text_right_mark_type)
7248 printf (" right mark `%s' visible: %d not_deleteable: %d\n",
7249 seg->body.mark.name,
7250 seg->body.mark.visible,
7251 seg->body.mark.not_deleteable);
7253 else if (seg->type == >k_text_left_mark_type)
7255 printf (" left mark `%s' visible: %d not_deleteable: %d\n",
7256 seg->body.mark.name,
7257 seg->body.mark.visible,
7258 seg->body.mark.not_deleteable);
7260 else if (seg->type == >k_text_toggle_on_type ||
7261 seg->type == >k_text_toggle_off_type)
7263 printf (" tag `%s' priority %d\n",
7264 seg->body.toggle.info->tag->name,
7265 seg->body.toggle.info->tag->priority);
7269 #define __GTK_TEXT_BTREE_C__
7270 #include "gtkaliasdef.c"