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"
74 * The structure below is used to pass information between
75 * _gtk_text_btree_get_tags and inc_count:
78 typedef struct TagInfo {
79 int numTags; /* Number of tags for which there
80 * is currently information in
82 int arraySize; /* Number of entries allocated for
84 GtkTextTag **tags; /* Array of tags seen so far.
86 int *counts; /* Toggle count (so far) for each
87 * entry in tags. Malloc-ed. */
92 * This is used to store per-view width/height info at the tree nodes.
95 typedef struct _NodeData NodeData;
101 /* Height and width of this node */
103 signed int width : 24;
105 /* boolean indicating whether the lines below this node are in need of validation.
106 * However, width/height should always represent the current total width and
107 * max height for lines below this node; the valid flag indicates whether the
108 * width/height on the lines needs recomputing, not whether the totals
111 guint valid : 8; /* Actually a boolean */
116 * The data structure below keeps summary information about one tag as part
117 * of the tag information in a node.
120 typedef struct Summary {
121 GtkTextTagInfo *info; /* Handle for tag. */
122 int toggle_count; /* Number of transitions into or
123 * out of this tag that occur in
124 * the subtree rooted at this node. */
125 struct Summary *next; /* Next in list of all tags for same
126 * node, or NULL if at end of list. */
130 * The data structure below defines a node in the B-tree.
133 struct _GtkTextBTreeNode {
134 GtkTextBTreeNode *parent; /* Pointer to parent node, or NULL if
135 * this is the root. */
136 GtkTextBTreeNode *next; /* Next in list of siblings with the
137 * same parent node, or NULL for end
139 Summary *summary; /* First in malloc-ed list of info
140 * about tags in this subtree (NULL if
141 * no tag info in the subtree). */
142 int level; /* Level of this node in the B-tree.
143 * 0 refers to the bottom of the tree
144 * (children are lines, not nodes). */
145 union { /* First in linked list of children. */
146 struct _GtkTextBTreeNode *node; /* Used if level > 0. */
147 GtkTextLine *line; /* Used if level == 0. */
149 int num_children; /* Number of children of this node. */
150 int num_lines; /* Total number of lines (leaves) in
151 * the subtree rooted here. */
152 int num_chars; /* Number of chars below here */
159 * Used to store the list of views in our btree
162 typedef struct _BTreeView BTreeView;
166 GtkTextLayout *layout;
172 * And the tree itself
175 struct _GtkTextBTree {
176 GtkTextBTreeNode *root_node; /* Pointer to root of B-tree. */
177 GtkTextTagTable *table;
178 GHashTable *mark_table;
180 GtkTextMark *insert_mark;
181 GtkTextMark *selection_bound_mark;
182 GtkTextBuffer *buffer;
185 gulong tag_changed_handler;
187 /* Incremented when a segment with a byte size > 0
188 * is added to or removed from the tree (i.e. the
189 * length of a line may have changed, and lines may
190 * have been added or removed). This invalidates
191 * all outstanding iterators.
193 guint chars_changed_stamp;
194 /* Incremented when any segments are added or deleted;
195 * this makes outstanding iterators recalculate their
196 * pointed-to segment and segment offset.
198 guint segments_changed_stamp;
200 /* Cache the last line in the buffer */
201 GtkTextLine *last_line;
202 guint last_line_stamp;
204 /* Cache the next-to-last line in the buffer,
205 * containing the end iterator
207 GtkTextLine *end_iter_line;
208 GtkTextLineSegment *end_iter_segment;
209 int end_iter_segment_byte_index;
210 int end_iter_segment_char_offset;
211 guint end_iter_line_stamp;
212 guint end_iter_segment_stamp;
214 GHashTable *child_anchor_table;
219 * Upper and lower bounds on how many children a node may have:
220 * rebalance when either of these limits is exceeded. MAX_CHILDREN
221 * should be twice MIN_CHILDREN and MIN_CHILDREN must be >= 2.
224 /* Tk used MAX of 12 and MIN of 6. This makes the tree wide and
225 shallow. It appears to be faster to locate a particular line number
226 if the tree is narrow and deep, since it is more finely sorted. I
227 guess this may increase memory use though, and make it slower to
228 walk the tree in order, or locate a particular byte index (which
229 is done by walking the tree in order).
231 There's basically a tradeoff here. However I'm thinking we want to
232 add pixels, byte counts, and char counts to the tree nodes,
233 at that point narrow and deep should speed up all operations,
234 not just the line number searches.
238 #define MAX_CHILDREN 12
239 #define MIN_CHILDREN 6
241 #define MAX_CHILDREN 6
242 #define MIN_CHILDREN 3
249 static BTreeView *gtk_text_btree_get_view (GtkTextBTree *tree,
251 static void gtk_text_btree_rebalance (GtkTextBTree *tree,
252 GtkTextBTreeNode *node);
253 static GtkTextLine * get_last_line (GtkTextBTree *tree);
254 static void post_insert_fixup (GtkTextBTree *tree,
255 GtkTextLine *insert_line,
256 gint char_count_delta,
257 gint line_count_delta);
258 static void gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
259 GtkTextTagInfo *info,
261 static gboolean gtk_text_btree_node_has_tag (GtkTextBTreeNode *node,
264 static void segments_changed (GtkTextBTree *tree);
265 static void chars_changed (GtkTextBTree *tree);
266 static void summary_list_destroy (Summary *summary);
267 static GtkTextLine *gtk_text_line_new (void);
268 static void gtk_text_line_destroy (GtkTextBTree *tree,
270 static void gtk_text_line_set_parent (GtkTextLine *line,
271 GtkTextBTreeNode *node);
272 static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
276 static NodeData *node_data_new (gpointer view_id);
277 static void node_data_destroy (NodeData *nd);
278 static void node_data_list_destroy (NodeData *nd);
279 static NodeData *node_data_find (NodeData *nd,
282 static GtkTextBTreeNode *gtk_text_btree_node_new (void);
284 static void gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node);
286 static void gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node,
288 static NodeData * gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
290 static NodeData * gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
292 static void gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
295 static void gtk_text_btree_node_remove_view (BTreeView *view,
296 GtkTextBTreeNode *node,
298 static void gtk_text_btree_node_destroy (GtkTextBTree *tree,
299 GtkTextBTreeNode *node);
300 static void gtk_text_btree_node_free_empty (GtkTextBTree *tree,
301 GtkTextBTreeNode *node);
302 static NodeData * gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node,
304 static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
306 static void gtk_text_btree_node_get_size (GtkTextBTreeNode *node,
310 static GtkTextBTreeNode * gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
311 GtkTextBTreeNode *node2);
312 static void get_tree_bounds (GtkTextBTree *tree,
315 static void tag_changed_cb (GtkTextTagTable *table,
317 gboolean size_changed,
319 static void cleanup_line (GtkTextLine *line);
320 static void recompute_node_counts (GtkTextBTree *tree,
321 GtkTextBTreeNode *node);
322 static void inc_count (GtkTextTag *tag,
324 TagInfo *tagInfoPtr);
326 static void summary_destroy (Summary *summary);
328 static void gtk_text_btree_link_segment (GtkTextLineSegment *seg,
329 const GtkTextIter *iter);
330 static void gtk_text_btree_unlink_segment (GtkTextBTree *tree,
331 GtkTextLineSegment *seg,
335 static GtkTextTagInfo *gtk_text_btree_get_tag_info (GtkTextBTree *tree,
337 static GtkTextTagInfo *gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
339 static void gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
342 static void redisplay_region (GtkTextBTree *tree,
343 const GtkTextIter *start,
344 const GtkTextIter *end,
345 gboolean cursors_only);
347 /* Inline thingies */
350 segments_changed (GtkTextBTree *tree)
352 tree->segments_changed_stamp += 1;
356 chars_changed (GtkTextBTree *tree)
358 tree->chars_changed_stamp += 1;
366 _gtk_text_btree_new (GtkTextTagTable *table,
367 GtkTextBuffer *buffer)
370 GtkTextBTreeNode *root_node;
371 GtkTextLine *line, *line2;
373 g_return_val_if_fail (GTK_IS_TEXT_TAG_TABLE (table), NULL);
374 g_return_val_if_fail (GTK_IS_TEXT_BUFFER (buffer), NULL);
377 * The tree will initially have two empty lines. The second line
378 * isn't actually part of the tree's contents, but its presence
379 * makes several operations easier. The tree will have one GtkTextBTreeNode,
380 * which is also the root of the tree.
383 /* Create the root node. */
385 root_node = gtk_text_btree_node_new ();
387 line = gtk_text_line_new ();
388 line2 = gtk_text_line_new ();
390 root_node->parent = NULL;
391 root_node->next = NULL;
392 root_node->summary = NULL;
393 root_node->level = 0;
394 root_node->children.line = line;
395 root_node->num_children = 2;
396 root_node->num_lines = 2;
397 root_node->num_chars = 2;
399 line->parent = root_node;
402 line->segments = _gtk_char_segment_new ("\n", 1);
404 line2->parent = root_node;
406 line2->segments = _gtk_char_segment_new ("\n", 1);
408 /* Create the tree itself */
410 tree = g_new0(GtkTextBTree, 1);
411 tree->root_node = root_node;
415 /* Set these to values that are unlikely to be found
416 * in random memory garbage, and also avoid
417 * duplicates between tree instances.
419 tree->chars_changed_stamp = g_random_int ();
420 tree->segments_changed_stamp = g_random_int ();
422 tree->last_line_stamp = tree->chars_changed_stamp - 1;
423 tree->last_line = NULL;
425 tree->end_iter_line_stamp = tree->chars_changed_stamp - 1;
426 tree->end_iter_segment_stamp = tree->segments_changed_stamp - 1;
427 tree->end_iter_line = NULL;
428 tree->end_iter_segment_byte_index = 0;
429 tree->end_iter_segment_char_offset = 0;
431 g_object_ref (tree->table);
433 tree->tag_changed_handler = g_signal_connect (tree->table,
435 G_CALLBACK (tag_changed_cb),
438 tree->mark_table = g_hash_table_new (g_str_hash, g_str_equal);
439 tree->child_anchor_table = NULL;
441 /* We don't ref the buffer, since the buffer owns us;
442 * we'd have some circularity issues. The buffer always
443 * lasts longer than the BTree
445 tree->buffer = buffer;
449 GtkTextLineSegment *seg;
451 _gtk_text_btree_get_iter_at_line_char (tree, &start, 0, 0);
454 tree->insert_mark = _gtk_text_btree_set_mark (tree,
461 seg = tree->insert_mark->segment;
463 seg->body.mark.not_deleteable = TRUE;
464 seg->body.mark.visible = TRUE;
466 tree->selection_bound_mark = _gtk_text_btree_set_mark (tree,
473 seg = tree->selection_bound_mark->segment;
475 seg->body.mark.not_deleteable = TRUE;
477 g_object_ref (tree->insert_mark);
478 g_object_ref (tree->selection_bound_mark);
487 _gtk_text_btree_ref (GtkTextBTree *tree)
489 g_return_if_fail (tree != NULL);
490 g_return_if_fail (tree->refcount > 0);
496 _gtk_text_btree_unref (GtkTextBTree *tree)
498 g_return_if_fail (tree != NULL);
499 g_return_if_fail (tree->refcount > 0);
503 if (tree->refcount == 0)
505 g_signal_handler_disconnect (tree->table,
506 tree->tag_changed_handler);
508 g_object_unref (tree->table);
511 gtk_text_btree_node_destroy (tree, tree->root_node);
512 tree->root_node = NULL;
514 g_assert (g_hash_table_size (tree->mark_table) == 0);
515 g_hash_table_destroy (tree->mark_table);
516 tree->mark_table = NULL;
517 if (tree->child_anchor_table != NULL)
519 g_hash_table_destroy (tree->child_anchor_table);
520 tree->child_anchor_table = NULL;
523 g_object_unref (tree->insert_mark);
524 tree->insert_mark = NULL;
525 g_object_unref (tree->selection_bound_mark);
526 tree->selection_bound_mark = NULL;
533 _gtk_text_btree_get_buffer (GtkTextBTree *tree)
539 _gtk_text_btree_get_chars_changed_stamp (GtkTextBTree *tree)
541 return tree->chars_changed_stamp;
545 _gtk_text_btree_get_segments_changed_stamp (GtkTextBTree *tree)
547 return tree->segments_changed_stamp;
551 _gtk_text_btree_segments_changed (GtkTextBTree *tree)
553 g_return_if_fail (tree != NULL);
554 segments_changed (tree);
558 * Indexable segment mutation
562 * The following function is responsible for resolving the bidi direction
563 * for the lines between start and end. But it also calculates any
564 * dependent bidi direction for surrounding lines that change as a result
565 * of the bidi direction decisions within the range. The function is
566 * trying to do as little propagation as is needed.
569 gtk_text_btree_resolve_bidi (GtkTextIter *start,
572 GtkTextBTree *tree = _gtk_text_iter_get_btree (start);
573 GtkTextLine *start_line, *end_line, *start_line_prev, *end_line_next, *line;
574 PangoDirection last_strong, dir_above_propagated, dir_below_propagated;
576 /* Resolve the strong bidi direction for all lines between
579 start_line = _gtk_text_iter_get_text_line (start);
580 start_line_prev = _gtk_text_line_previous (start_line);
581 end_line = _gtk_text_iter_get_text_line (end);
582 end_line_next = _gtk_text_line_next (end_line);
585 while (line && line != end_line_next)
587 /* Loop through the segments and search for a strong character
589 GtkTextLineSegment *seg = line->segments;
590 line->dir_strong = PANGO_DIRECTION_NEUTRAL;
594 if (seg->type == >k_text_char_type && seg->byte_count > 0)
596 PangoDirection pango_dir;
598 pango_dir = pango_find_base_dir (seg->body.chars,
601 if (pango_dir != PANGO_DIRECTION_NEUTRAL)
603 line->dir_strong = pango_dir;
610 line = _gtk_text_line_next (line);
615 /* The variable dir_above_propagated contains the forward propagated
616 * direction before start. It is neutral if start is in the beginning
619 dir_above_propagated = PANGO_DIRECTION_NEUTRAL;
621 dir_above_propagated = start_line_prev->dir_propagated_forward;
623 /* Loop forward and propagate the direction of each paragraph
624 * to all neutral lines.
627 last_strong = dir_above_propagated;
628 while (line != end_line_next)
630 if (line->dir_strong != PANGO_DIRECTION_NEUTRAL)
631 last_strong = line->dir_strong;
633 line->dir_propagated_forward = last_strong;
635 line = _gtk_text_line_next (line);
638 /* Continue propagating as long as the previous resolved forward
639 * is different from last_strong.
642 GtkTextIter end_propagate;
645 line->dir_strong == PANGO_DIRECTION_NEUTRAL &&
646 line->dir_propagated_forward != last_strong)
648 GtkTextLine *prev = line;
649 line->dir_propagated_forward = last_strong;
651 line = _gtk_text_line_next(line);
659 /* The last line to invalidate is the last line before the
660 * line with the strong character. Or in case of the end of the
661 * buffer, the last line of the buffer. (There seems to be an
662 * extra "virtual" last line in the buffer that must not be used
663 * calling _gtk_text_btree_get_iter_at_line (causes crash). Thus the
664 * _gtk_text_line_previous is ok in that case as well.)
666 line = _gtk_text_line_previous (line);
667 _gtk_text_btree_get_iter_at_line (tree, &end_propagate, line, 0);
668 _gtk_text_btree_invalidate_region (tree, end, &end_propagate, FALSE);
673 /* The variable dir_below_propagated contains the backward propagated
674 * direction after end. It is neutral if end is at the end of
677 dir_below_propagated = PANGO_DIRECTION_NEUTRAL;
679 dir_below_propagated = end_line_next->dir_propagated_back;
681 /* Loop backward and propagate the direction of each paragraph
682 * to all neutral lines.
685 last_strong = dir_below_propagated;
686 while (line != start_line_prev)
688 if (line->dir_strong != PANGO_DIRECTION_NEUTRAL)
689 last_strong = line->dir_strong;
691 line->dir_propagated_back = last_strong;
693 line = _gtk_text_line_previous (line);
696 /* Continue propagating as long as the resolved backward dir
697 * is different from last_strong.
700 GtkTextIter start_propagate;
703 line->dir_strong == PANGO_DIRECTION_NEUTRAL &&
704 line->dir_propagated_back != last_strong)
706 GtkTextLine *prev = line;
707 line->dir_propagated_back = last_strong;
709 line = _gtk_text_line_previous (line);
717 /* We only need to invalidate for backwards propagation if the
718 * line we ended up on didn't get a direction from forwards
721 if (line && line->dir_propagated_forward == PANGO_DIRECTION_NEUTRAL)
723 _gtk_text_btree_get_iter_at_line (tree, &start_propagate, line, 0);
724 _gtk_text_btree_invalidate_region (tree, &start_propagate, start, FALSE);
730 _gtk_text_btree_delete (GtkTextIter *start,
733 GtkTextLineSegment *prev_seg; /* The segment just before the start
734 * of the deletion range. */
735 GtkTextLineSegment *last_seg; /* The segment just after the end
736 * of the deletion range. */
737 GtkTextLineSegment *seg, *next, *next2;
738 GtkTextLine *curline;
739 GtkTextBTreeNode *curnode, *node;
741 GtkTextLine *start_line;
742 GtkTextLine *end_line;
744 GtkTextLine *deleted_lines = NULL; /* List of lines we've deleted */
745 gint start_byte_offset;
747 g_return_if_fail (start != NULL);
748 g_return_if_fail (end != NULL);
749 g_return_if_fail (_gtk_text_iter_get_btree (start) ==
750 _gtk_text_iter_get_btree (end));
752 gtk_text_iter_order (start, end);
754 tree = _gtk_text_iter_get_btree (start);
756 if (gtk_debug_flags & GTK_DEBUG_TEXT)
757 _gtk_text_btree_check (tree);
759 /* Broadcast the need for redisplay before we break the iterators */
760 DV (g_print ("invalidating due to deleting some text (%s)\n", G_STRLOC));
761 _gtk_text_btree_invalidate_region (tree, start, end, FALSE);
763 /* Save the byte offset so we can reset the iterators */
764 start_byte_offset = gtk_text_iter_get_line_index (start);
766 start_line = _gtk_text_iter_get_text_line (start);
767 end_line = _gtk_text_iter_get_text_line (end);
770 * Split the start and end segments, so we have a place
771 * to insert our new text.
773 * Tricky point: split at end first; otherwise the split
774 * at end may invalidate seg and/or prev_seg. This allows
775 * us to avoid invalidating segments for start.
778 last_seg = gtk_text_line_segment_split (end);
779 if (last_seg != NULL)
780 last_seg = last_seg->next;
782 last_seg = end_line->segments;
784 prev_seg = gtk_text_line_segment_split (start);
785 if (prev_seg != NULL)
787 seg = prev_seg->next;
788 prev_seg->next = last_seg;
792 seg = start_line->segments;
793 start_line->segments = last_seg;
796 /* notify iterators that their segments need recomputation,
797 just for robustness. */
798 segments_changed (tree);
801 * Delete all of the segments between prev_seg and last_seg.
804 curline = start_line;
805 curnode = curline->parent;
806 while (seg != last_seg)
812 GtkTextLine *nextline;
815 * We just ran off the end of a line. First find the
816 * next line, then go back to the old line and delete it
817 * (unless it's the starting line for the range).
820 nextline = _gtk_text_line_next (curline);
821 if (curline != start_line)
823 if (curnode == start_line->parent)
824 start_line->next = curline->next;
826 curnode->children.line = curline->next;
828 for (node = curnode; node != NULL;
831 /* Don't update node->num_chars, because
832 * that was done when we deleted the segments.
834 node->num_lines -= 1;
837 curnode->num_children -= 1;
838 curline->next = deleted_lines;
839 deleted_lines = curline;
843 seg = curline->segments;
846 * If the GtkTextBTreeNode is empty then delete it and its parents,
847 * recursively upwards until a non-empty GtkTextBTreeNode is found.
850 while (curnode->num_children == 0)
852 GtkTextBTreeNode *parent;
854 parent = curnode->parent;
855 if (parent->children.node == curnode)
857 parent->children.node = curnode->next;
861 GtkTextBTreeNode *prevnode = parent->children.node;
862 while (prevnode->next != curnode)
864 prevnode = prevnode->next;
866 prevnode->next = curnode->next;
868 parent->num_children--;
869 gtk_text_btree_node_free_empty (tree, curnode);
872 curnode = curline->parent;
877 char_count = seg->char_count;
879 if ((*seg->type->deleteFunc)(seg, curline, FALSE) != 0)
882 * This segment refuses to die. Move it to prev_seg and
883 * advance prev_seg if the segment has left gravity.
886 if (prev_seg == NULL)
888 seg->next = start_line->segments;
889 start_line->segments = seg;
891 else if (prev_seg->next &&
892 prev_seg->next != last_seg &&
893 seg->type == >k_text_toggle_off_type &&
894 prev_seg->next->type == >k_text_toggle_on_type &&
895 seg->body.toggle.info == prev_seg->next->body.toggle.info)
897 /* Try to match an off toggle with the matching on toggle
898 * if it immediately follows. This is a common case, and
899 * handling it here prevents quadratic blowup in
900 * cleanup_line() below. See bug 317125.
902 next2 = prev_seg->next->next;
903 g_free ((char *)prev_seg->next);
904 prev_seg->next = next2;
905 g_free ((char *)seg);
910 seg->next = prev_seg->next;
911 prev_seg->next = seg;
914 if (seg && seg->type->leftGravity)
921 /* Segment is gone. Decrement the char count of the node and
923 for (node = curnode; node != NULL;
926 node->num_chars -= char_count;
934 * If the beginning and end of the deletion range are in different
935 * lines, join the two lines together and discard the ending line.
938 if (start_line != end_line)
941 GtkTextBTreeNode *ancestor_node;
942 GtkTextLine *prevline;
945 /* last_seg was appended to start_line up at the top of this function */
947 for (seg = last_seg; seg != NULL;
950 chars_moved += seg->char_count;
951 if (seg->type->lineChangeFunc != NULL)
953 (*seg->type->lineChangeFunc)(seg, end_line);
957 for (node = start_line->parent; node != NULL;
960 node->num_chars += chars_moved;
963 curnode = end_line->parent;
964 for (node = curnode; node != NULL;
967 node->num_chars -= chars_moved;
970 curnode->num_children--;
971 prevline = curnode->children.line;
972 if (prevline == end_line)
974 curnode->children.line = end_line->next;
978 while (prevline->next != end_line)
980 prevline = prevline->next;
982 prevline->next = end_line->next;
984 end_line->next = deleted_lines;
985 deleted_lines = end_line;
987 /* We now fix up the per-view aggregates. We add all the height and
988 * width for the deleted lines to the start line, so that when revalidation
989 * occurs, the correct change in size is seen.
991 ancestor_node = gtk_text_btree_node_common_parent (curnode, start_line->parent);
997 gint deleted_width = 0;
998 gint deleted_height = 0;
1000 line = deleted_lines;
1003 GtkTextLine *next_line = line->next;
1004 ld = _gtk_text_line_get_data (line, view->view_id);
1008 deleted_width = MAX (deleted_width, ld->width);
1009 deleted_height += ld->height;
1015 if (deleted_width > 0 || deleted_height > 0)
1017 ld = _gtk_text_line_get_data (start_line, view->view_id);
1021 /* This means that start_line has never been validated.
1022 * We don't really want to do the validation here but
1023 * we do need to store our temporary sizes. So we
1024 * create the line data and assume a line w/h of 0.
1026 ld = _gtk_text_line_data_new (view->layout, start_line);
1027 _gtk_text_line_add_data (start_line, ld);
1033 ld->width = MAX (deleted_width, ld->width);
1034 ld->height += deleted_height;
1038 gtk_text_btree_node_check_valid_downward (ancestor_node, view->view_id);
1039 if (ancestor_node->parent)
1040 gtk_text_btree_node_check_valid_upward (ancestor_node->parent, view->view_id);
1045 line = deleted_lines;
1048 GtkTextLine *next_line = line->next;
1050 gtk_text_line_destroy (tree, line);
1055 /* avoid dangling pointer */
1056 deleted_lines = NULL;
1058 gtk_text_btree_rebalance (tree, curnode);
1062 * Cleanup the segments in the new line.
1065 cleanup_line (start_line);
1068 * Lastly, rebalance the first GtkTextBTreeNode of the range.
1071 gtk_text_btree_rebalance (tree, start_line->parent);
1073 /* Notify outstanding iterators that they
1075 chars_changed (tree);
1076 segments_changed (tree);
1078 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1079 _gtk_text_btree_check (tree);
1081 /* Re-initialize our iterators */
1082 _gtk_text_btree_get_iter_at_line (tree, start, start_line, start_byte_offset);
1085 gtk_text_btree_resolve_bidi (start, end);
1089 _gtk_text_btree_insert (GtkTextIter *iter,
1093 GtkTextLineSegment *prev_seg; /* The segment just before the first
1094 * new segment (NULL means new segment
1095 * is at beginning of line). */
1096 GtkTextLineSegment *cur_seg; /* Current segment; new characters
1097 * are inserted just after this one.
1098 * NULL means insert at beginning of
1100 GtkTextLine *line; /* Current line (new segments are
1101 * added to this line). */
1102 GtkTextLineSegment *seg;
1103 GtkTextLine *newline;
1104 int chunk_len; /* # characters in current chunk. */
1105 gint sol; /* start of line */
1106 gint eol; /* Pointer to character just after last
1107 * one in current chunk.
1109 gint delim; /* index of paragraph delimiter */
1110 int line_count_delta; /* Counts change to total number of
1114 int char_count_delta; /* change to number of chars */
1116 gint start_byte_index;
1117 GtkTextLine *start_line;
1119 g_return_if_fail (text != NULL);
1120 g_return_if_fail (iter != NULL);
1123 len = strlen (text);
1125 /* extract iterator info */
1126 tree = _gtk_text_iter_get_btree (iter);
1127 line = _gtk_text_iter_get_text_line (iter);
1130 start_byte_index = gtk_text_iter_get_line_index (iter);
1132 /* Get our insertion segment split. Note this assumes line allows
1133 * char insertions, which isn't true of the "last" line. But iter
1134 * should not be on that line, as we assert here.
1136 g_assert (!_gtk_text_line_is_last (line, tree));
1137 prev_seg = gtk_text_line_segment_split (iter);
1140 /* Invalidate all iterators */
1141 chars_changed (tree);
1142 segments_changed (tree);
1145 * Chop the text up into lines and create a new segment for
1146 * each line, plus a new line for the leftovers from the
1152 line_count_delta = 0;
1153 char_count_delta = 0;
1158 pango_find_paragraph_boundary (text + sol,
1163 /* make these relative to the start of the text */
1167 g_assert (eol >= sol);
1168 g_assert (delim >= sol);
1169 g_assert (eol >= delim);
1170 g_assert (sol >= 0);
1171 g_assert (eol <= len);
1173 chunk_len = eol - sol;
1175 g_assert (g_utf8_validate (&text[sol], chunk_len, NULL));
1176 seg = _gtk_char_segment_new (&text[sol], chunk_len);
1178 char_count_delta += seg->char_count;
1180 if (cur_seg == NULL)
1182 seg->next = line->segments;
1183 line->segments = seg;
1187 seg->next = cur_seg->next;
1188 cur_seg->next = seg;
1193 /* chunk didn't end with a paragraph separator */
1194 g_assert (eol == len);
1199 * The chunk ended with a newline, so create a new GtkTextLine
1200 * and move the remainder of the old line to it.
1203 newline = gtk_text_line_new ();
1204 gtk_text_line_set_parent (newline, line->parent);
1205 newline->next = line->next;
1206 line->next = newline;
1207 newline->segments = seg->next;
1215 * Cleanup the starting line for the insertion, plus the ending
1216 * line if it's different.
1219 cleanup_line (start_line);
1220 if (line != start_line)
1222 cleanup_line (line);
1225 post_insert_fixup (tree, line, line_count_delta, char_count_delta);
1227 /* Invalidate our region, and reset the iterator the user
1228 passed in to point to the end of the inserted text. */
1234 _gtk_text_btree_get_iter_at_line (tree,
1240 /* We could almost certainly be more efficient here
1241 by saving the information from the insertion loop
1243 gtk_text_iter_forward_chars (&end, char_count_delta);
1245 DV (g_print ("invalidating due to inserting some text (%s)\n", G_STRLOC));
1246 _gtk_text_btree_invalidate_region (tree, &start, &end, FALSE);
1249 /* Convenience for the user */
1252 gtk_text_btree_resolve_bidi (&start, &end);
1257 insert_pixbuf_or_widget_segment (GtkTextIter *iter,
1258 GtkTextLineSegment *seg)
1262 GtkTextLineSegment *prevPtr;
1265 gint start_byte_offset;
1267 line = _gtk_text_iter_get_text_line (iter);
1268 tree = _gtk_text_iter_get_btree (iter);
1269 start_byte_offset = gtk_text_iter_get_line_index (iter);
1271 prevPtr = gtk_text_line_segment_split (iter);
1272 if (prevPtr == NULL)
1274 seg->next = line->segments;
1275 line->segments = seg;
1279 seg->next = prevPtr->next;
1280 prevPtr->next = seg;
1283 post_insert_fixup (tree, line, 0, seg->char_count);
1285 chars_changed (tree);
1286 segments_changed (tree);
1288 /* reset *iter for the user, and invalidate tree nodes */
1290 _gtk_text_btree_get_iter_at_line (tree, &start, line, start_byte_offset);
1293 gtk_text_iter_forward_char (iter); /* skip forward past the segment */
1295 DV (g_print ("invalidating due to inserting pixbuf/widget (%s)\n", G_STRLOC));
1296 _gtk_text_btree_invalidate_region (tree, &start, iter, FALSE);
1300 _gtk_text_btree_insert_pixbuf (GtkTextIter *iter,
1303 GtkTextLineSegment *seg;
1305 seg = _gtk_pixbuf_segment_new (pixbuf);
1307 insert_pixbuf_or_widget_segment (iter, seg);
1311 _gtk_text_btree_insert_child_anchor (GtkTextIter *iter,
1312 GtkTextChildAnchor *anchor)
1314 GtkTextLineSegment *seg;
1317 if (anchor->segment != NULL)
1319 g_warning (G_STRLOC": Same child anchor can't be inserted twice");
1323 seg = _gtk_widget_segment_new (anchor);
1325 tree = seg->body.child.tree = _gtk_text_iter_get_btree (iter);
1326 seg->body.child.line = _gtk_text_iter_get_text_line (iter);
1328 insert_pixbuf_or_widget_segment (iter, seg);
1330 if (tree->child_anchor_table == NULL)
1331 tree->child_anchor_table = g_hash_table_new (NULL, NULL);
1333 g_hash_table_insert (tree->child_anchor_table,
1334 seg->body.child.obj,
1335 seg->body.child.obj);
1339 _gtk_text_btree_unregister_child_anchor (GtkTextChildAnchor *anchor)
1341 GtkTextLineSegment *seg;
1343 seg = anchor->segment;
1345 g_hash_table_remove (seg->body.child.tree->child_anchor_table,
1354 find_line_by_y (GtkTextBTree *tree, BTreeView *view,
1355 GtkTextBTreeNode *node, gint y, gint *line_top,
1356 GtkTextLine *last_line)
1360 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1361 _gtk_text_btree_check (tree);
1363 if (node->level == 0)
1367 line = node->children.line;
1369 while (line != NULL && line != last_line)
1371 GtkTextLineData *ld;
1373 ld = _gtk_text_line_get_data (line, view->view_id);
1377 if (y < (current_y + (ld ? ld->height : 0)))
1380 current_y += ld->height;
1381 *line_top += ld->height;
1390 GtkTextBTreeNode *child;
1392 child = node->children.node;
1394 while (child != NULL)
1399 gtk_text_btree_node_get_size (child, view->view_id,
1402 if (y < (current_y + height))
1403 return find_line_by_y (tree, view, child,
1404 y - current_y, line_top,
1407 current_y += height;
1408 *line_top += height;
1410 child = child->next;
1418 _gtk_text_btree_find_line_by_y (GtkTextBTree *tree,
1425 GtkTextLine *last_line;
1428 view = gtk_text_btree_get_view (tree, view_id);
1429 g_return_val_if_fail (view != NULL, NULL);
1431 last_line = get_last_line (tree);
1433 line = find_line_by_y (tree, view, tree->root_node, ypixel, &line_top,
1437 *line_top_out = line_top;
1443 find_line_top_in_line_list (GtkTextBTree *tree,
1446 GtkTextLine *target_line,
1449 while (line != NULL)
1451 GtkTextLineData *ld;
1453 if (line == target_line)
1456 ld = _gtk_text_line_get_data (line, view->view_id);
1463 g_assert_not_reached (); /* If we get here, our
1464 target line didn't exist
1465 under its parent node */
1470 _gtk_text_btree_find_line_top (GtkTextBTree *tree,
1471 GtkTextLine *target_line,
1478 GtkTextBTreeNode *node;
1480 view = gtk_text_btree_get_view (tree, view_id);
1482 g_return_val_if_fail (view != NULL, 0);
1485 node = target_line->parent;
1486 while (node != NULL)
1488 nodes = g_slist_prepend (nodes, node);
1489 node = node->parent;
1493 while (iter != NULL)
1497 if (node->level == 0)
1499 g_slist_free (nodes);
1500 return find_line_top_in_line_list (tree, view,
1501 node->children.line,
1506 GtkTextBTreeNode *child;
1507 GtkTextBTreeNode *target_node;
1509 g_assert (iter->next != NULL); /* not at level 0 */
1510 target_node = iter->next->data;
1512 child = node->children.node;
1514 while (child != NULL)
1519 if (child == target_node)
1523 gtk_text_btree_node_get_size (child, view->view_id,
1527 child = child->next;
1529 g_assert (child != NULL); /* should have broken out before we
1533 iter = g_slist_next (iter);
1536 g_assert_not_reached (); /* we return when we find the target line */
1541 _gtk_text_btree_add_view (GtkTextBTree *tree,
1542 GtkTextLayout *layout)
1545 GtkTextLine *last_line;
1546 GtkTextLineData *line_data;
1548 g_return_if_fail (tree != NULL);
1550 view = g_new (BTreeView, 1);
1552 view->view_id = layout;
1553 view->layout = layout;
1555 view->next = tree->views;
1560 g_assert (tree->views->prev == NULL);
1561 tree->views->prev = view;
1566 /* The last line in the buffer has identity values for the per-view
1567 * data so that we can avoid special case checks for it in a large
1570 last_line = get_last_line (tree);
1572 line_data = g_new (GtkTextLineData, 1);
1573 line_data->view_id = layout;
1574 line_data->next = NULL;
1575 line_data->width = 0;
1576 line_data->height = 0;
1577 line_data->valid = TRUE;
1579 _gtk_text_line_add_data (last_line, line_data);
1583 _gtk_text_btree_remove_view (GtkTextBTree *tree,
1587 GtkTextLine *last_line;
1588 GtkTextLineData *line_data;
1590 g_return_if_fail (tree != NULL);
1594 while (view != NULL)
1596 if (view->view_id == view_id)
1602 g_return_if_fail (view != NULL);
1605 view->next->prev = view->prev;
1608 view->prev->next = view->next;
1610 if (view == tree->views)
1611 tree->views = view->next;
1613 /* Remove the line data for the last line which we added ourselves.
1614 * (Do this first, so that we don't try to call the view's line data destructor on it.)
1616 last_line = get_last_line (tree);
1617 line_data = _gtk_text_line_remove_data (last_line, view_id);
1620 gtk_text_btree_node_remove_view (view, tree->root_node, view_id);
1622 view->layout = (gpointer) 0xdeadbeef;
1623 view->view_id = (gpointer) 0xdeadbeef;
1629 _gtk_text_btree_invalidate_region (GtkTextBTree *tree,
1630 const GtkTextIter *start,
1631 const GtkTextIter *end,
1632 gboolean cursors_only)
1638 while (view != NULL)
1641 gtk_text_layout_invalidate_cursors (view->layout, start, end);
1643 gtk_text_layout_invalidate (view->layout, start, end);
1650 _gtk_text_btree_get_view_size (GtkTextBTree *tree,
1655 g_return_if_fail (tree != NULL);
1656 g_return_if_fail (view_id != NULL);
1658 gtk_text_btree_node_get_size (tree->root_node, view_id,
1673 iter_stack_new (void)
1676 stack = g_slice_new (IterStack);
1677 stack->iters = NULL;
1684 iter_stack_push (IterStack *stack,
1685 const GtkTextIter *iter)
1688 if (stack->count > stack->alloced)
1690 stack->alloced = stack->count*2;
1691 stack->iters = g_realloc (stack->iters,
1692 stack->alloced * sizeof (GtkTextIter));
1694 stack->iters[stack->count-1] = *iter;
1698 iter_stack_pop (IterStack *stack,
1701 if (stack->count == 0)
1706 *iter = stack->iters[stack->count];
1712 iter_stack_free (IterStack *stack)
1714 g_free (stack->iters);
1715 g_slice_free (IterStack, stack);
1719 iter_stack_invert (IterStack *stack)
1721 if (stack->count > 0)
1724 guint j = stack->count - 1;
1729 tmp = stack->iters[i];
1730 stack->iters[i] = stack->iters[j];
1731 stack->iters[j] = tmp;
1740 queue_tag_redisplay (GtkTextBTree *tree,
1742 const GtkTextIter *start,
1743 const GtkTextIter *end)
1745 if (_gtk_text_tag_affects_size (tag))
1747 DV (g_print ("invalidating due to size-affecting tag (%s)\n", G_STRLOC));
1748 _gtk_text_btree_invalidate_region (tree, start, end, FALSE);
1750 else if (_gtk_text_tag_affects_nonsize_appearance (tag))
1752 /* We only need to queue a redraw, not a relayout */
1753 redisplay_region (tree, start, end, FALSE);
1756 /* We don't need to do anything if the tag doesn't affect display */
1760 _gtk_text_btree_tag (const GtkTextIter *start_orig,
1761 const GtkTextIter *end_orig,
1765 GtkTextLineSegment *seg, *prev;
1766 GtkTextLine *cleanupline;
1767 gboolean toggled_on;
1768 GtkTextLine *start_line;
1769 GtkTextLine *end_line;
1771 GtkTextIter start, end;
1774 GtkTextTagInfo *info;
1776 g_return_if_fail (start_orig != NULL);
1777 g_return_if_fail (end_orig != NULL);
1778 g_return_if_fail (GTK_IS_TEXT_TAG (tag));
1779 g_return_if_fail (_gtk_text_iter_get_btree (start_orig) ==
1780 _gtk_text_iter_get_btree (end_orig));
1781 g_return_if_fail (tag->table == _gtk_text_iter_get_btree (start_orig)->table);
1784 printf ("%s tag %s from %d to %d\n",
1785 add ? "Adding" : "Removing",
1787 gtk_text_buffer_get_offset (start_orig),
1788 gtk_text_buffer_get_offset (end_orig));
1791 if (gtk_text_iter_equal (start_orig, end_orig))
1794 start = *start_orig;
1797 gtk_text_iter_order (&start, &end);
1799 tree = _gtk_text_iter_get_btree (&start);
1801 queue_tag_redisplay (tree, tag, &start, &end);
1803 info = gtk_text_btree_get_tag_info (tree, tag);
1805 start_line = _gtk_text_iter_get_text_line (&start);
1806 end_line = _gtk_text_iter_get_text_line (&end);
1808 /* Find all tag toggles in the region; we are going to delete them.
1809 We need to find them in advance, because
1810 forward_find_tag_toggle () won't work once we start playing around
1812 stack = iter_stack_new ();
1815 /* forward_to_tag_toggle() skips a toggle at the start iterator,
1816 * which is deliberate - we don't want to delete a toggle at the
1819 while (gtk_text_iter_forward_to_tag_toggle (&iter, tag))
1821 if (gtk_text_iter_compare (&iter, &end) >= 0)
1824 iter_stack_push (stack, &iter);
1827 /* We need to traverse the toggles in order. */
1828 iter_stack_invert (stack);
1831 * See whether the tag is present at the start of the range. If
1832 * the state doesn't already match what we want then add a toggle
1836 toggled_on = gtk_text_iter_has_tag (&start, tag);
1837 if ( (add && !toggled_on) ||
1838 (!add && toggled_on) )
1840 /* This could create a second toggle at the start position;
1841 cleanup_line () will remove it if so. */
1842 seg = _gtk_toggle_segment_new (info, add);
1844 prev = gtk_text_line_segment_split (&start);
1847 seg->next = start_line->segments;
1848 start_line->segments = seg;
1852 seg->next = prev->next;
1856 /* cleanup_line adds the new toggle to the node counts. */
1858 printf ("added toggle at start\n");
1860 /* we should probably call segments_changed, but in theory
1861 any still-cached segments in the iters we are about to
1862 use are still valid, since they're in front
1868 * Scan the range of characters and delete any internal tag
1869 * transitions. Keep track of what the old state was at the end
1870 * of the range, and add a toggle there if it's needed.
1874 cleanupline = start_line;
1875 while (iter_stack_pop (stack, &iter))
1877 GtkTextLineSegment *indexable_seg;
1880 line = _gtk_text_iter_get_text_line (&iter);
1881 seg = _gtk_text_iter_get_any_segment (&iter);
1882 indexable_seg = _gtk_text_iter_get_indexable_segment (&iter);
1884 g_assert (seg != NULL);
1885 g_assert (indexable_seg != NULL);
1886 g_assert (seg != indexable_seg);
1888 prev = line->segments;
1890 /* Find the segment that actually toggles this tag. */
1891 while (seg != indexable_seg)
1893 g_assert (seg != NULL);
1894 g_assert (indexable_seg != NULL);
1895 g_assert (seg != indexable_seg);
1897 if ( (seg->type == >k_text_toggle_on_type ||
1898 seg->type == >k_text_toggle_off_type) &&
1899 (seg->body.toggle.info == info) )
1905 g_assert (seg != NULL);
1906 g_assert (indexable_seg != NULL);
1908 g_assert (seg != indexable_seg); /* If this happens, then
1909 forward_to_tag_toggle was
1911 g_assert (seg->body.toggle.info->tag == tag);
1913 /* If this happens, when previously tagging we didn't merge
1914 overlapping tags. */
1915 g_assert ( (toggled_on && seg->type == >k_text_toggle_off_type) ||
1916 (!toggled_on && seg->type == >k_text_toggle_on_type) );
1918 toggled_on = !toggled_on;
1921 printf ("deleting %s toggle\n",
1922 seg->type == >k_text_toggle_on_type ? "on" : "off");
1924 /* Remove toggle segment from the list. */
1927 line->segments = seg->next;
1931 while (prev->next != seg)
1935 prev->next = seg->next;
1938 /* Inform iterators we've hosed them. This actually reflects a
1939 bit of inefficiency; if you have the same tag toggled on and
1940 off a lot in a single line, we keep having the rescan from
1941 the front of the line. Of course we have to do that to get
1942 "prev" anyway, but here we are doing it an additional
1944 segments_changed (tree);
1946 /* Update node counts */
1947 if (seg->body.toggle.inNodeCounts)
1949 _gtk_change_node_toggle_count (line->parent,
1951 seg->body.toggle.inNodeCounts = FALSE;
1956 /* We only clean up lines when we're done with them, saves some
1957 gratuitous line-segment-traversals */
1959 if (cleanupline != line)
1961 cleanup_line (cleanupline);
1966 iter_stack_free (stack);
1968 /* toggled_on now reflects the toggle state _just before_ the
1969 end iterator. The end iterator could already have a toggle
1970 on or a toggle off. */
1971 if ( (add && !toggled_on) ||
1972 (!add && toggled_on) )
1974 /* This could create a second toggle at the start position;
1975 cleanup_line () will remove it if so. */
1977 seg = _gtk_toggle_segment_new (info, !add);
1979 prev = gtk_text_line_segment_split (&end);
1982 seg->next = end_line->segments;
1983 end_line->segments = seg;
1987 seg->next = prev->next;
1990 /* cleanup_line adds the new toggle to the node counts. */
1991 g_assert (seg->body.toggle.inNodeCounts == FALSE);
1993 printf ("added toggle at end\n");
1998 * Cleanup cleanupline and the last line of the range, if
1999 * these are different.
2002 cleanup_line (cleanupline);
2003 if (cleanupline != end_line)
2005 cleanup_line (end_line);
2008 segments_changed (tree);
2010 queue_tag_redisplay (tree, tag, &start, &end);
2012 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2013 _gtk_text_btree_check (tree);
2022 get_line_internal (GtkTextBTree *tree,
2024 gint *real_line_number,
2025 gboolean include_last)
2027 GtkTextBTreeNode *node;
2032 line_count = _gtk_text_btree_line_count (tree);
2036 if (line_number < 0)
2038 line_number = line_count;
2040 else if (line_number > line_count)
2042 line_number = line_count;
2045 if (real_line_number)
2046 *real_line_number = line_number;
2048 node = tree->root_node;
2049 lines_left = line_number;
2052 * Work down through levels of the tree until a GtkTextBTreeNode is found at
2056 while (node->level != 0)
2058 for (node = node->children.node;
2059 node->num_lines <= lines_left;
2065 g_error ("gtk_text_btree_find_line ran out of GtkTextBTreeNodes");
2068 lines_left -= node->num_lines;
2073 * Work through the lines attached to the level-0 GtkTextBTreeNode.
2076 for (line = node->children.line; lines_left > 0;
2082 g_error ("gtk_text_btree_find_line ran out of lines");
2091 _gtk_text_btree_get_end_iter_line (GtkTextBTree *tree)
2094 _gtk_text_btree_get_line (tree,
2095 _gtk_text_btree_line_count (tree) - 1,
2100 _gtk_text_btree_get_line (GtkTextBTree *tree,
2102 gint *real_line_number)
2104 return get_line_internal (tree, line_number, real_line_number, TRUE);
2108 _gtk_text_btree_get_line_no_last (GtkTextBTree *tree,
2110 gint *real_line_number)
2112 return get_line_internal (tree, line_number, real_line_number, FALSE);
2116 _gtk_text_btree_get_line_at_char (GtkTextBTree *tree,
2118 gint *line_start_index,
2119 gint *real_char_index)
2121 GtkTextBTreeNode *node;
2123 GtkTextLineSegment *seg;
2127 node = tree->root_node;
2129 /* Clamp to valid indexes (-1 is magic for "highest index"),
2130 * node->num_chars includes the two newlines that aren't really
2133 if (char_index < 0 || char_index >= (node->num_chars - 1))
2135 char_index = node->num_chars - 2;
2138 *real_char_index = char_index;
2141 * Work down through levels of the tree until a GtkTextBTreeNode is found at
2145 chars_left = char_index;
2146 while (node->level != 0)
2148 for (node = node->children.node;
2149 chars_left >= node->num_chars;
2152 chars_left -= node->num_chars;
2154 g_assert (chars_left >= 0);
2158 if (chars_left == 0)
2160 /* Start of a line */
2162 *line_start_index = char_index;
2163 return node->children.line;
2167 * Work through the lines attached to the level-0 GtkTextBTreeNode.
2172 for (line = node->children.line; line != NULL; line = line->next)
2174 seg = line->segments;
2177 if (chars_in_line + seg->char_count > chars_left)
2178 goto found; /* found our line/segment */
2180 chars_in_line += seg->char_count;
2185 chars_left -= chars_in_line;
2193 g_assert (line != NULL); /* hosage, ran out of lines */
2194 g_assert (seg != NULL);
2196 *line_start_index = char_index - chars_left;
2200 /* It returns an array sorted by tags priority, ready to pass to
2201 * _gtk_text_attributes_fill_from_tags() */
2203 _gtk_text_btree_get_tags (const GtkTextIter *iter,
2206 GtkTextBTreeNode *node;
2207 GtkTextLine *siblingline;
2208 GtkTextLineSegment *seg;
2209 int src, dst, index;
2214 #define NUM_TAG_INFOS 10
2216 line = _gtk_text_iter_get_text_line (iter);
2217 byte_index = gtk_text_iter_get_line_index (iter);
2219 tagInfo.numTags = 0;
2220 tagInfo.arraySize = NUM_TAG_INFOS;
2221 tagInfo.tags = g_new (GtkTextTag*, NUM_TAG_INFOS);
2222 tagInfo.counts = g_new (int, NUM_TAG_INFOS);
2225 * Record tag toggles within the line of indexPtr but preceding
2226 * indexPtr. Note that if this loop segfaults, your
2227 * byte_index probably points past the sum of all
2228 * seg->byte_count */
2230 for (index = 0, seg = line->segments;
2231 (index + seg->byte_count) <= byte_index;
2232 index += seg->byte_count, seg = seg->next)
2234 if ((seg->type == >k_text_toggle_on_type)
2235 || (seg->type == >k_text_toggle_off_type))
2237 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2242 * Record toggles for tags in lines that are predecessors of
2243 * line but under the same level-0 GtkTextBTreeNode.
2246 for (siblingline = line->parent->children.line;
2247 siblingline != line;
2248 siblingline = siblingline->next)
2250 for (seg = siblingline->segments; seg != NULL;
2253 if ((seg->type == >k_text_toggle_on_type)
2254 || (seg->type == >k_text_toggle_off_type))
2256 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2262 * For each GtkTextBTreeNode in the ancestry of this line, record tag
2263 * toggles for all siblings that precede that GtkTextBTreeNode.
2266 for (node = line->parent; node->parent != NULL;
2267 node = node->parent)
2269 GtkTextBTreeNode *siblingPtr;
2272 for (siblingPtr = node->parent->children.node;
2273 siblingPtr != node; siblingPtr = siblingPtr->next)
2275 for (summary = siblingPtr->summary; summary != NULL;
2276 summary = summary->next)
2278 if (summary->toggle_count & 1)
2280 inc_count (summary->info->tag, summary->toggle_count,
2288 * Go through the tag information and squash out all of the tags
2289 * that have even toggle counts (these tags exist before the point
2290 * of interest, but not at the desired character itself).
2293 for (src = 0, dst = 0; src < tagInfo.numTags; src++)
2295 if (tagInfo.counts[src] & 1)
2297 g_assert (GTK_IS_TEXT_TAG (tagInfo.tags[src]));
2298 tagInfo.tags[dst] = tagInfo.tags[src];
2304 g_free (tagInfo.counts);
2307 g_free (tagInfo.tags);
2311 /* Sort tags in ascending order of priority */
2312 _gtk_text_tag_array_sort (tagInfo.tags, dst);
2314 return tagInfo.tags;
2318 copy_segment (GString *string,
2319 gboolean include_hidden,
2320 gboolean include_nonchars,
2321 const GtkTextIter *start,
2322 const GtkTextIter *end)
2324 GtkTextLineSegment *end_seg;
2325 GtkTextLineSegment *seg;
2327 if (gtk_text_iter_equal (start, end))
2330 seg = _gtk_text_iter_get_indexable_segment (start);
2331 end_seg = _gtk_text_iter_get_indexable_segment (end);
2333 if (seg->type == >k_text_char_type)
2335 gboolean copy = TRUE;
2336 gint copy_bytes = 0;
2337 gint copy_start = 0;
2339 /* Don't copy if we're invisible; segments are invisible/not
2340 as a whole, no need to check each char */
2341 if (!include_hidden &&
2342 _gtk_text_btree_char_is_invisible (start))
2345 /* printf (" <invisible>\n"); */
2348 copy_start = _gtk_text_iter_get_segment_byte (start);
2352 /* End is in the same segment; need to copy fewer bytes. */
2353 gint end_byte = _gtk_text_iter_get_segment_byte (end);
2355 copy_bytes = end_byte - copy_start;
2358 copy_bytes = seg->byte_count - copy_start;
2360 g_assert (copy_bytes != 0); /* Due to iter equality check at
2361 front of this function. */
2365 g_assert ((copy_start + copy_bytes) <= seg->byte_count);
2367 g_string_append_len (string,
2368 seg->body.chars + copy_start,
2372 /* printf (" :%s\n", string->str); */
2374 else if (seg->type == >k_text_pixbuf_type ||
2375 seg->type == >k_text_child_type)
2377 gboolean copy = TRUE;
2379 if (!include_nonchars)
2383 else if (!include_hidden &&
2384 _gtk_text_btree_char_is_invisible (start))
2391 g_string_append_len (string,
2392 gtk_text_unknown_char_utf8,
2400 _gtk_text_btree_get_text (const GtkTextIter *start_orig,
2401 const GtkTextIter *end_orig,
2402 gboolean include_hidden,
2403 gboolean include_nonchars)
2405 GtkTextLineSegment *seg;
2406 GtkTextLineSegment *end_seg;
2413 g_return_val_if_fail (start_orig != NULL, NULL);
2414 g_return_val_if_fail (end_orig != NULL, NULL);
2415 g_return_val_if_fail (_gtk_text_iter_get_btree (start_orig) ==
2416 _gtk_text_iter_get_btree (end_orig), NULL);
2418 start = *start_orig;
2421 gtk_text_iter_order (&start, &end);
2423 retval = g_string_new (NULL);
2425 end_seg = _gtk_text_iter_get_indexable_segment (&end);
2427 seg = _gtk_text_iter_get_indexable_segment (&iter);
2428 while (seg != end_seg)
2430 copy_segment (retval, include_hidden, include_nonchars,
2433 _gtk_text_iter_forward_indexable_segment (&iter);
2435 seg = _gtk_text_iter_get_indexable_segment (&iter);
2438 copy_segment (retval, include_hidden, include_nonchars, &iter, &end);
2441 g_string_free (retval, FALSE);
2446 _gtk_text_btree_line_count (GtkTextBTree *tree)
2448 /* Subtract bogus line at the end; we return a count
2450 return tree->root_node->num_lines - 1;
2454 _gtk_text_btree_char_count (GtkTextBTree *tree)
2456 /* Exclude newline in bogus last line and the
2457 * one in the last line that is after the end iterator
2459 return tree->root_node->num_chars - 2;
2462 #define LOTSA_TAGS 1000
2464 _gtk_text_btree_char_is_invisible (const GtkTextIter *iter)
2466 gboolean invisible = FALSE; /* if nobody says otherwise, it's visible */
2468 int deftagCnts[LOTSA_TAGS] = { 0, };
2469 int *tagCnts = deftagCnts;
2470 GtkTextTag *deftags[LOTSA_TAGS];
2471 GtkTextTag **tags = deftags;
2473 GtkTextBTreeNode *node;
2474 GtkTextLine *siblingline;
2475 GtkTextLineSegment *seg;
2482 line = _gtk_text_iter_get_text_line (iter);
2483 tree = _gtk_text_iter_get_btree (iter);
2484 byte_index = gtk_text_iter_get_line_index (iter);
2486 numTags = gtk_text_tag_table_get_size (tree->table);
2488 /* almost always avoid malloc, so stay out of system calls */
2489 if (LOTSA_TAGS < numTags)
2491 tagCnts = g_new0 (int, numTags);
2492 tags = g_new (GtkTextTag*, numTags);
2496 * Record tag toggles within the line of indexPtr but preceding
2500 for (index = 0, seg = line->segments;
2501 (index + seg->byte_count) <= byte_index; /* segfault here means invalid index */
2502 index += seg->byte_count, seg = seg->next)
2504 if ((seg->type == >k_text_toggle_on_type)
2505 || (seg->type == >k_text_toggle_off_type))
2507 tag = seg->body.toggle.info->tag;
2508 if (tag->invisible_set)
2510 tags[tag->priority] = tag;
2511 tagCnts[tag->priority]++;
2517 * Record toggles for tags in lines that are predecessors of
2518 * line but under the same level-0 GtkTextBTreeNode.
2521 for (siblingline = line->parent->children.line;
2522 siblingline != line;
2523 siblingline = siblingline->next)
2525 for (seg = siblingline->segments; seg != NULL;
2528 if ((seg->type == >k_text_toggle_on_type)
2529 || (seg->type == >k_text_toggle_off_type))
2531 tag = seg->body.toggle.info->tag;
2532 if (tag->invisible_set)
2534 tags[tag->priority] = tag;
2535 tagCnts[tag->priority]++;
2542 * For each GtkTextBTreeNode in the ancestry of this line, record tag toggles
2543 * for all siblings that precede that GtkTextBTreeNode.
2546 for (node = line->parent; node->parent != NULL;
2547 node = node->parent)
2549 GtkTextBTreeNode *siblingPtr;
2552 for (siblingPtr = node->parent->children.node;
2553 siblingPtr != node; siblingPtr = siblingPtr->next)
2555 for (summary = siblingPtr->summary; summary != NULL;
2556 summary = summary->next)
2558 if (summary->toggle_count & 1)
2560 tag = summary->info->tag;
2561 if (tag->invisible_set)
2563 tags[tag->priority] = tag;
2564 tagCnts[tag->priority] += summary->toggle_count;
2572 * Now traverse from highest priority to lowest,
2573 * take invisible value from first odd count (= on)
2576 for (i = numTags-1; i >=0; i--)
2580 /* FIXME not sure this should be if 0 */
2582 #ifndef ALWAYS_SHOW_SELECTION
2583 /* who would make the selection invisible? */
2584 if ((tag == tkxt->seltag)
2585 && !(tkxt->flags & GOT_FOCUS))
2591 invisible = tags[i]->values->invisible;
2596 if (LOTSA_TAGS < numTags)
2611 redisplay_region (GtkTextBTree *tree,
2612 const GtkTextIter *start,
2613 const GtkTextIter *end,
2614 gboolean cursors_only)
2617 GtkTextLine *start_line, *end_line;
2619 if (gtk_text_iter_compare (start, end) > 0)
2621 const GtkTextIter *tmp = start;
2626 start_line = _gtk_text_iter_get_text_line (start);
2627 end_line = _gtk_text_iter_get_text_line (end);
2630 while (view != NULL)
2632 gint start_y, end_y;
2633 GtkTextLineData *ld;
2635 start_y = _gtk_text_btree_find_line_top (tree, start_line, view->view_id);
2637 if (end_line == start_line)
2640 end_y = _gtk_text_btree_find_line_top (tree, end_line, view->view_id);
2642 ld = _gtk_text_line_get_data (end_line, view->view_id);
2644 end_y += ld->height;
2647 gtk_text_layout_cursors_changed (view->layout, start_y,
2651 gtk_text_layout_changed (view->layout, start_y,
2660 redisplay_mark (GtkTextLineSegment *mark)
2664 gboolean cursor_only;
2666 _gtk_text_btree_get_iter_at_mark (mark->body.mark.tree,
2668 mark->body.mark.obj);
2671 gtk_text_iter_forward_char (&end);
2673 DV (g_print ("invalidating due to moving visible mark (%s)\n", G_STRLOC));
2674 cursor_only = mark == mark->body.mark.tree->insert_mark->segment;
2675 _gtk_text_btree_invalidate_region (mark->body.mark.tree, &iter, &end, cursor_only);
2679 redisplay_mark_if_visible (GtkTextLineSegment *mark)
2681 if (!mark->body.mark.visible)
2684 redisplay_mark (mark);
2688 ensure_not_off_end (GtkTextBTree *tree,
2689 GtkTextLineSegment *mark,
2692 if (gtk_text_iter_get_line (iter) == _gtk_text_btree_line_count (tree))
2693 gtk_text_iter_backward_char (iter);
2696 static GtkTextLineSegment*
2697 real_set_mark (GtkTextBTree *tree,
2698 GtkTextMark *existing_mark,
2700 gboolean left_gravity,
2701 const GtkTextIter *where,
2702 gboolean should_exist,
2703 gboolean redraw_selections)
2705 GtkTextLineSegment *mark;
2708 g_return_val_if_fail (tree != NULL, NULL);
2709 g_return_val_if_fail (where != NULL, NULL);
2710 g_return_val_if_fail (_gtk_text_iter_get_btree (where) == tree, NULL);
2714 if (gtk_text_mark_get_buffer (existing_mark) != NULL)
2715 mark = existing_mark->segment;
2719 else if (name != NULL)
2720 mark = g_hash_table_lookup (tree->mark_table,
2725 if (should_exist && mark == NULL)
2727 g_warning ("No mark `%s' exists!", name);
2731 /* OK if !should_exist and it does already exist, in that case
2737 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2738 _gtk_text_iter_check (&iter);
2742 if (redraw_selections &&
2743 (mark == tree->insert_mark->segment ||
2744 mark == tree->selection_bound_mark->segment))
2746 GtkTextIter old_pos;
2748 _gtk_text_btree_get_iter_at_mark (tree, &old_pos,
2749 mark->body.mark.obj);
2750 redisplay_region (tree, &old_pos, where, TRUE);
2754 * don't let visible marks be after the final newline of the
2758 if (mark->body.mark.visible)
2760 ensure_not_off_end (tree, mark, &iter);
2763 /* Redraw the mark's old location. */
2764 redisplay_mark_if_visible (mark);
2766 /* Unlink mark from its current location.
2767 This could hose our iterator... */
2768 gtk_text_btree_unlink_segment (tree, mark,
2769 mark->body.mark.line);
2770 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2771 g_assert (mark->body.mark.line == _gtk_text_iter_get_text_line (&iter));
2773 segments_changed (tree); /* make sure the iterator recomputes its
2779 g_object_ref (existing_mark);
2781 existing_mark = gtk_text_mark_new (name, left_gravity);
2783 mark = existing_mark->segment;
2784 _gtk_mark_segment_set_tree (mark, tree);
2786 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2788 if (mark->body.mark.name)
2789 g_hash_table_insert (tree->mark_table,
2790 mark->body.mark.name,
2794 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2795 _gtk_text_iter_check (&iter);
2797 /* Link mark into new location */
2798 gtk_text_btree_link_segment (mark, &iter);
2800 /* Invalidate some iterators. */
2801 segments_changed (tree);
2804 * update the screen at the mark's new location.
2807 redisplay_mark_if_visible (mark);
2809 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2810 _gtk_text_iter_check (&iter);
2812 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2813 _gtk_text_btree_check (tree);
2820 _gtk_text_btree_set_mark (GtkTextBTree *tree,
2821 GtkTextMark *existing_mark,
2823 gboolean left_gravity,
2824 const GtkTextIter *iter,
2825 gboolean should_exist)
2827 GtkTextLineSegment *seg;
2829 seg = real_set_mark (tree, existing_mark,
2830 name, left_gravity, iter, should_exist,
2833 return seg ? seg->body.mark.obj : NULL;
2837 _gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2841 GtkTextIter tmp_start, tmp_end;
2843 _gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2845 _gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2846 tree->selection_bound_mark);
2848 if (gtk_text_iter_equal (&tmp_start, &tmp_end))
2860 gtk_text_iter_order (&tmp_start, &tmp_end);
2873 _gtk_text_btree_place_cursor (GtkTextBTree *tree,
2874 const GtkTextIter *iter)
2876 _gtk_text_btree_select_range (tree, iter, iter);
2880 _gtk_text_btree_select_range (GtkTextBTree *tree,
2881 const GtkTextIter *ins,
2882 const GtkTextIter *bound)
2884 GtkTextIter old_ins, old_bound;
2886 _gtk_text_btree_get_iter_at_mark (tree, &old_ins,
2888 _gtk_text_btree_get_iter_at_mark (tree, &old_bound,
2889 tree->selection_bound_mark);
2891 /* Check if it's no-op since gtk_text_buffer_place_cursor()
2892 * also calls this, and this will redraw the cursor line. */
2893 if (!gtk_text_iter_equal (&old_ins, ins) ||
2894 !gtk_text_iter_equal (&old_bound, bound))
2896 redisplay_region (tree, &old_ins, &old_bound, TRUE);
2898 /* Move insert AND selection_bound before we redisplay */
2899 real_set_mark (tree, tree->insert_mark,
2900 "insert", FALSE, ins, TRUE, FALSE);
2901 real_set_mark (tree, tree->selection_bound_mark,
2902 "selection_bound", FALSE, bound, TRUE, FALSE);
2904 redisplay_region (tree, ins, bound, TRUE);
2910 _gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2915 g_return_if_fail (tree != NULL);
2916 g_return_if_fail (name != NULL);
2918 mark = g_hash_table_lookup (tree->mark_table,
2921 _gtk_text_btree_remove_mark (tree, mark);
2925 _gtk_text_btree_release_mark_segment (GtkTextBTree *tree,
2926 GtkTextLineSegment *segment)
2929 if (segment->body.mark.name)
2930 g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2932 segment->body.mark.tree = NULL;
2933 segment->body.mark.line = NULL;
2935 /* Remove the ref on the mark, which frees segment as a side effect
2936 * if this is the last reference.
2938 g_object_unref (segment->body.mark.obj);
2942 _gtk_text_btree_remove_mark (GtkTextBTree *tree,
2945 GtkTextLineSegment *segment;
2947 g_return_if_fail (mark != NULL);
2948 g_return_if_fail (tree != NULL);
2950 segment = mark->segment;
2952 if (segment->body.mark.not_deleteable)
2954 g_warning ("Can't delete special mark `%s'", segment->body.mark.name);
2958 /* This calls cleanup_line and segments_changed */
2959 gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2961 _gtk_text_btree_release_mark_segment (tree, segment);
2965 _gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2966 GtkTextMark *segment)
2968 return segment == tree->insert_mark;
2972 _gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2973 GtkTextMark *segment)
2975 return segment == tree->selection_bound_mark;
2979 _gtk_text_btree_get_insert (GtkTextBTree *tree)
2981 return tree->insert_mark;
2985 _gtk_text_btree_get_selection_bound (GtkTextBTree *tree)
2987 return tree->selection_bound_mark;
2991 _gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2994 GtkTextLineSegment *seg;
2996 g_return_val_if_fail (tree != NULL, NULL);
2997 g_return_val_if_fail (name != NULL, NULL);
2999 seg = g_hash_table_lookup (tree->mark_table, name);
3001 return seg ? seg->body.mark.obj : NULL;
3005 * gtk_text_mark_set_visible:
3006 * @mark: a #GtkTextMark
3007 * @setting: visibility of mark
3009 * Sets the visibility of @mark; the insertion point is normally
3010 * visible, i.e. you can see it as a vertical bar. Also, the text
3011 * widget uses a visible mark to indicate where a drop will occur when
3012 * dragging-and-dropping text. Most other marks are not visible.
3013 * Marks are not visible by default.
3017 gtk_text_mark_set_visible (GtkTextMark *mark,
3020 GtkTextLineSegment *seg;
3022 g_return_if_fail (mark != NULL);
3024 seg = mark->segment;
3026 if (seg->body.mark.visible == setting)
3030 seg->body.mark.visible = setting;
3032 if (seg->body.mark.tree)
3033 redisplay_mark (seg);
3038 _gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
3041 GtkTextBTreeNode *node;
3042 GtkTextTagInfo *info;
3044 g_return_val_if_fail (tree != NULL, NULL);
3048 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3053 if (info->tag_root == NULL)
3056 node = info->tag_root;
3058 /* We know the tag root has instances of the given
3061 continue_outer_loop:
3062 g_assert (node != NULL);
3063 while (node->level > 0)
3065 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
3066 node = node->children.node;
3067 while (node != NULL)
3069 if (gtk_text_btree_node_has_tag (node, tag))
3070 goto continue_outer_loop;
3074 g_assert (node != NULL);
3077 g_assert (node != NULL); /* The tag summaries said some node had
3080 g_assert (node->level == 0);
3082 return node->children.line;
3086 /* Looking for any tag at all (tag == NULL).
3087 Unfortunately this can't be done in a simple and efficient way
3088 right now; so I'm just going to return the
3089 first line in the btree. FIXME */
3090 return _gtk_text_btree_get_line (tree, 0, NULL);
3095 _gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
3098 GtkTextBTreeNode *node;
3099 GtkTextBTreeNode *last_node;
3101 GtkTextTagInfo *info;
3103 g_return_val_if_fail (tree != NULL, NULL);
3107 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3109 if (info->tag_root == NULL)
3112 node = info->tag_root;
3113 /* We know the tag root has instances of the given
3116 while (node->level > 0)
3118 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
3120 node = node->children.node;
3121 while (node != NULL)
3123 if (gtk_text_btree_node_has_tag (node, tag))
3131 g_assert (node != NULL); /* The tag summaries said some node had
3134 g_assert (node->level == 0);
3136 /* Find the last line in this node */
3137 line = node->children.line;
3138 while (line->next != NULL)
3145 /* This search can't be done efficiently at the moment,
3146 at least not without complexity.
3147 So, we just return the last line.
3149 return _gtk_text_btree_get_end_iter_line (tree);
3159 _gtk_text_line_get_number (GtkTextLine *line)
3162 GtkTextBTreeNode *node, *parent, *node2;
3166 * First count how many lines precede this one in its level-0
3170 node = line->parent;
3172 for (line2 = node->children.line; line2 != line;
3173 line2 = line2->next)
3177 g_error ("gtk_text_btree_line_number couldn't find line");
3183 * Now work up through the levels of the tree one at a time,
3184 * counting how many lines are in GtkTextBTreeNodes preceding the current
3188 for (parent = node->parent ; parent != NULL;
3189 node = parent, parent = parent->parent)
3191 for (node2 = parent->children.node; node2 != node;
3192 node2 = node2->next)
3196 g_error ("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
3198 index += node2->num_lines;
3204 static GtkTextLineSegment*
3205 find_toggle_segment_before_char (GtkTextLine *line,
3209 GtkTextLineSegment *seg;
3210 GtkTextLineSegment *toggle_seg;
3215 seg = line->segments;
3216 while ( (index + seg->char_count) <= char_in_line )
3218 if (((seg->type == >k_text_toggle_on_type)
3219 || (seg->type == >k_text_toggle_off_type))
3220 && (seg->body.toggle.info->tag == tag))
3223 index += seg->char_count;
3230 static GtkTextLineSegment*
3231 find_toggle_segment_before_byte (GtkTextLine *line,
3235 GtkTextLineSegment *seg;
3236 GtkTextLineSegment *toggle_seg;
3241 seg = line->segments;
3242 while ( (index + seg->byte_count) <= byte_in_line )
3244 if (((seg->type == >k_text_toggle_on_type)
3245 || (seg->type == >k_text_toggle_off_type))
3246 && (seg->body.toggle.info->tag == tag))
3249 index += seg->byte_count;
3257 find_toggle_outside_current_line (GtkTextLine *line,
3261 GtkTextBTreeNode *node;
3262 GtkTextLine *sibling_line;
3263 GtkTextLineSegment *seg;
3264 GtkTextLineSegment *toggle_seg;
3266 GtkTextTagInfo *info = NULL;
3269 * No toggle in this line. Look for toggles for the tag in lines
3270 * that are predecessors of line but under the same
3271 * level-0 GtkTextBTreeNode.
3274 sibling_line = line->parent->children.line;
3275 while (sibling_line != line)
3277 seg = sibling_line->segments;
3280 if (((seg->type == >k_text_toggle_on_type)
3281 || (seg->type == >k_text_toggle_off_type))
3282 && (seg->body.toggle.info->tag == tag))
3288 sibling_line = sibling_line->next;
3291 if (toggle_seg != NULL)
3292 return (toggle_seg->type == >k_text_toggle_on_type);
3295 * No toggle in this GtkTextBTreeNode. Scan upwards through the ancestors of
3296 * this GtkTextBTreeNode, counting the number of toggles of the given tag in
3297 * siblings that precede that GtkTextBTreeNode.
3300 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3306 node = line->parent;
3307 while (node->parent != NULL)
3309 GtkTextBTreeNode *sibling_node;
3311 sibling_node = node->parent->children.node;
3312 while (sibling_node != node)
3316 summary = sibling_node->summary;
3317 while (summary != NULL)
3319 if (summary->info == info)
3320 toggles += summary->toggle_count;
3322 summary = summary->next;
3325 sibling_node = sibling_node->next;
3328 if (node == info->tag_root)
3331 node = node->parent;
3335 * An odd number of toggles means that the tag is present at the
3339 return (toggles & 1) != 0;
3342 /* FIXME this function is far too slow, for no good reason. */
3344 _gtk_text_line_char_has_tag (GtkTextLine *line,
3349 GtkTextLineSegment *toggle_seg;
3351 g_return_val_if_fail (line != NULL, FALSE);
3354 * Check for toggles for the tag in the line but before
3355 * the char. If there is one, its type indicates whether or
3356 * not the character is tagged.
3359 toggle_seg = find_toggle_segment_before_char (line, char_in_line, tag);
3361 if (toggle_seg != NULL)
3362 return (toggle_seg->type == >k_text_toggle_on_type);
3364 return find_toggle_outside_current_line (line, tree, tag);
3368 _gtk_text_line_byte_has_tag (GtkTextLine *line,
3373 GtkTextLineSegment *toggle_seg;
3375 g_return_val_if_fail (line != NULL, FALSE);
3378 * Check for toggles for the tag in the line but before
3379 * the char. If there is one, its type indicates whether or
3380 * not the character is tagged.
3383 toggle_seg = find_toggle_segment_before_byte (line, byte_in_line, tag);
3385 if (toggle_seg != NULL)
3386 return (toggle_seg->type == >k_text_toggle_on_type);
3388 return find_toggle_outside_current_line (line, tree, tag);
3392 _gtk_text_line_is_last (GtkTextLine *line,
3395 return line == get_last_line (tree);
3399 ensure_end_iter_line (GtkTextBTree *tree)
3401 if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
3405 /* n_lines is without the magic line at the end */
3406 g_assert (_gtk_text_btree_line_count (tree) >= 1);
3408 tree->end_iter_line = _gtk_text_btree_get_line_no_last (tree, -1, &real_line);
3410 tree->end_iter_line_stamp = tree->chars_changed_stamp;
3415 ensure_end_iter_segment (GtkTextBTree *tree)
3417 if (tree->end_iter_segment_stamp != tree->segments_changed_stamp)
3419 GtkTextLineSegment *seg;
3420 GtkTextLineSegment *last_with_chars;
3422 ensure_end_iter_line (tree);
3424 last_with_chars = NULL;
3426 seg = tree->end_iter_line->segments;
3429 if (seg->char_count > 0)
3430 last_with_chars = seg;
3434 tree->end_iter_segment = last_with_chars;
3436 /* We know the last char in the last line is '\n' */
3437 tree->end_iter_segment_byte_index = last_with_chars->byte_count - 1;
3438 tree->end_iter_segment_char_offset = last_with_chars->char_count - 1;
3440 tree->end_iter_segment_stamp = tree->segments_changed_stamp;
3442 g_assert (tree->end_iter_segment->type == >k_text_char_type);
3443 g_assert (tree->end_iter_segment->body.chars[tree->end_iter_segment_byte_index] == '\n');
3448 _gtk_text_line_contains_end_iter (GtkTextLine *line,
3451 ensure_end_iter_line (tree);
3453 return line == tree->end_iter_line;
3457 _gtk_text_btree_is_end (GtkTextBTree *tree,
3459 GtkTextLineSegment *seg,
3463 g_return_val_if_fail (byte_index >= 0 || char_offset >= 0, FALSE);
3465 /* Do this first to avoid walking segments in most cases */
3466 if (!_gtk_text_line_contains_end_iter (line, tree))
3469 ensure_end_iter_segment (tree);
3471 if (seg != tree->end_iter_segment)
3474 if (byte_index >= 0)
3475 return byte_index == tree->end_iter_segment_byte_index;
3477 return char_offset == tree->end_iter_segment_char_offset;
3481 _gtk_text_line_next (GtkTextLine *line)
3483 GtkTextBTreeNode *node;
3485 if (line->next != NULL)
3490 * This was the last line associated with the particular parent
3491 * GtkTextBTreeNode. Search up the tree for the next GtkTextBTreeNode,
3492 * then search down from that GtkTextBTreeNode to find the first
3496 node = line->parent;
3497 while (node != NULL && node->next == NULL)
3498 node = node->parent;
3504 while (node->level > 0)
3506 node = node->children.node;
3509 g_assert (node->children.line != line);
3511 return node->children.line;
3516 _gtk_text_line_next_excluding_last (GtkTextLine *line)
3520 next = _gtk_text_line_next (line);
3522 /* If we were on the end iter line, we can't go to
3525 if (next && next->next == NULL && /* these checks are optimization only */
3526 _gtk_text_line_next (next) == NULL)
3533 _gtk_text_line_previous (GtkTextLine *line)
3535 GtkTextBTreeNode *node;
3536 GtkTextBTreeNode *node2;
3540 * Find the line under this GtkTextBTreeNode just before the starting line.
3542 prev = line->parent->children.line; /* First line at leaf */
3543 while (prev != line)
3545 if (prev->next == line)
3551 g_error ("gtk_text_btree_previous_line ran out of lines");
3555 * This was the first line associated with the particular parent
3556 * GtkTextBTreeNode. Search up the tree for the previous GtkTextBTreeNode,
3557 * then search down from that GtkTextBTreeNode to find its last line.
3559 for (node = line->parent; ; node = node->parent)
3561 if (node == NULL || node->parent == NULL)
3563 else if (node != node->parent->children.node)
3567 for (node2 = node->parent->children.node; ;
3568 node2 = node2->children.node)
3570 while (node2->next != node)
3571 node2 = node2->next;
3573 if (node2->level == 0)
3579 for (prev = node2->children.line ; ; prev = prev->next)
3581 if (prev->next == NULL)
3585 g_assert_not_reached ();
3591 _gtk_text_line_data_new (GtkTextLayout *layout,
3594 GtkTextLineData *line_data;
3596 line_data = g_new (GtkTextLineData, 1);
3598 line_data->view_id = layout;
3599 line_data->next = NULL;
3600 line_data->width = 0;
3601 line_data->height = 0;
3602 line_data->valid = FALSE;
3608 _gtk_text_line_add_data (GtkTextLine *line,
3609 GtkTextLineData *data)
3611 g_return_if_fail (line != NULL);
3612 g_return_if_fail (data != NULL);
3613 g_return_if_fail (data->view_id != NULL);
3617 data->next = line->views;
3627 _gtk_text_line_remove_data (GtkTextLine *line,
3630 GtkTextLineData *prev;
3631 GtkTextLineData *iter;
3633 g_return_val_if_fail (line != NULL, NULL);
3634 g_return_val_if_fail (view_id != NULL, NULL);
3638 while (iter != NULL)
3640 if (iter->view_id == view_id)
3649 prev->next = iter->next;
3651 line->views = iter->next;
3660 _gtk_text_line_get_data (GtkTextLine *line,
3663 GtkTextLineData *iter;
3665 g_return_val_if_fail (line != NULL, NULL);
3666 g_return_val_if_fail (view_id != NULL, NULL);
3669 while (iter != NULL)
3671 if (iter->view_id == view_id)
3680 _gtk_text_line_invalidate_wrap (GtkTextLine *line,
3681 GtkTextLineData *ld)
3683 /* For now this is totally unoptimized. FIXME?
3685 We could probably optimize the case where the width removed
3686 is less than the max width for the parent node,
3687 and the case where the height is unchanged when we re-wrap.
3690 g_return_if_fail (ld != NULL);
3693 gtk_text_btree_node_invalidate_upward (line->parent, ld->view_id);
3697 _gtk_text_line_char_count (GtkTextLine *line)
3699 GtkTextLineSegment *seg;
3703 seg = line->segments;
3706 size += seg->char_count;
3713 _gtk_text_line_byte_count (GtkTextLine *line)
3715 GtkTextLineSegment *seg;
3719 seg = line->segments;
3722 size += seg->byte_count;
3730 _gtk_text_line_char_index (GtkTextLine *target_line)
3732 GSList *node_stack = NULL;
3733 GtkTextBTreeNode *iter;
3737 /* Push all our parent nodes onto a stack */
3738 iter = target_line->parent;
3740 g_assert (iter != NULL);
3742 while (iter != NULL)
3744 node_stack = g_slist_prepend (node_stack, iter);
3746 iter = iter->parent;
3749 /* Check that we have the root node on top of the stack. */
3750 g_assert (node_stack != NULL &&
3751 node_stack->data != NULL &&
3752 ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3754 /* Add up chars in all nodes before the nodes in our stack.
3758 iter = node_stack->data;
3759 while (iter != NULL)
3761 GtkTextBTreeNode *child_iter;
3762 GtkTextBTreeNode *next_node;
3764 next_node = node_stack->next ?
3765 node_stack->next->data : NULL;
3766 node_stack = g_slist_remove (node_stack, node_stack->data);
3768 if (iter->level == 0)
3770 /* stack should be empty when we're on the last node */
3771 g_assert (node_stack == NULL);
3772 break; /* Our children are now lines */
3775 g_assert (next_node != NULL);
3776 g_assert (iter != NULL);
3777 g_assert (next_node->parent == iter);
3779 /* Add up chars before us in the tree */
3780 child_iter = iter->children.node;
3781 while (child_iter != next_node)
3783 g_assert (child_iter != NULL);
3785 num_chars += child_iter->num_chars;
3787 child_iter = child_iter->next;
3793 g_assert (iter != NULL);
3794 g_assert (iter == target_line->parent);
3796 /* Since we don't store char counts in lines, only in segments, we
3797 have to iterate over the lines adding up segment char counts
3798 until we find our line. */
3799 line = iter->children.line;
3800 while (line != target_line)
3802 g_assert (line != NULL);
3804 num_chars += _gtk_text_line_char_count (line);
3809 g_assert (line == target_line);
3815 _gtk_text_line_byte_to_segment (GtkTextLine *line,
3819 GtkTextLineSegment *seg;
3822 g_return_val_if_fail (line != NULL, NULL);
3824 offset = byte_offset;
3825 seg = line->segments;
3827 while (offset >= seg->byte_count)
3829 offset -= seg->byte_count;
3831 g_assert (seg != NULL); /* means an invalid byte index */
3835 *seg_offset = offset;
3841 _gtk_text_line_char_to_segment (GtkTextLine *line,
3845 GtkTextLineSegment *seg;
3848 g_return_val_if_fail (line != NULL, NULL);
3850 offset = char_offset;
3851 seg = line->segments;
3853 while (offset >= seg->char_count)
3855 offset -= seg->char_count;
3857 g_assert (seg != NULL); /* means an invalid char index */
3861 *seg_offset = offset;
3867 _gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3871 GtkTextLineSegment *seg;
3874 g_return_val_if_fail (line != NULL, NULL);
3876 offset = byte_offset;
3877 seg = line->segments;
3879 while (offset > 0 && offset >= seg->byte_count)
3881 offset -= seg->byte_count;
3883 g_assert (seg != NULL); /* means an invalid byte index */
3887 *seg_offset = offset;
3893 _gtk_text_line_char_to_any_segment (GtkTextLine *line,
3897 GtkTextLineSegment *seg;
3900 g_return_val_if_fail (line != NULL, NULL);
3902 offset = char_offset;
3903 seg = line->segments;
3905 while (offset > 0 && offset >= seg->char_count)
3907 offset -= seg->char_count;
3909 g_assert (seg != NULL); /* means an invalid byte index */
3913 *seg_offset = offset;
3919 _gtk_text_line_byte_to_char (GtkTextLine *line,
3923 GtkTextLineSegment *seg;
3925 g_return_val_if_fail (line != NULL, 0);
3926 g_return_val_if_fail (byte_offset >= 0, 0);
3929 seg = line->segments;
3930 while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3931 the next segment) */
3933 byte_offset -= seg->byte_count;
3934 char_offset += seg->char_count;
3936 g_assert (seg != NULL); /* our byte_index was bogus if this happens */
3939 g_assert (seg != NULL);
3941 /* Now byte_offset is the offset into the current segment,
3942 and char_offset is the start of the current segment.
3943 Optimize the case where no chars use > 1 byte */
3944 if (seg->byte_count == seg->char_count)
3945 return char_offset + byte_offset;
3948 if (seg->type == >k_text_char_type)
3949 return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3952 g_assert (seg->char_count == 1);
3953 g_assert (byte_offset == 0);
3961 _gtk_text_line_char_to_byte (GtkTextLine *line,
3964 g_warning ("FIXME not implemented");
3969 /* FIXME sync with char_locate (or figure out a clean
3970 way to merge the two functions) */
3972 _gtk_text_line_byte_locate (GtkTextLine *line,
3974 GtkTextLineSegment **segment,
3975 GtkTextLineSegment **any_segment,
3976 gint *seg_byte_offset,
3977 gint *line_byte_offset)
3979 GtkTextLineSegment *seg;
3980 GtkTextLineSegment *after_last_indexable;
3981 GtkTextLineSegment *last_indexable;
3985 g_return_val_if_fail (line != NULL, FALSE);
3986 g_return_val_if_fail (byte_offset >= 0, FALSE);
3989 *any_segment = NULL;
3992 offset = byte_offset;
3994 last_indexable = NULL;
3995 after_last_indexable = line->segments;
3996 seg = line->segments;
3998 /* The loop ends when we're inside a segment;
3999 last_indexable refers to the last segment
4000 we passed entirely. */
4001 while (seg && offset >= seg->byte_count)
4003 if (seg->char_count > 0)
4005 offset -= seg->byte_count;
4006 bytes_in_line += seg->byte_count;
4007 last_indexable = seg;
4008 after_last_indexable = last_indexable->next;
4016 /* We went off the end of the line */
4018 g_warning ("%s: byte index off the end of the line", G_STRLOC);
4025 if (after_last_indexable != NULL)
4026 *any_segment = after_last_indexable;
4028 *any_segment = *segment;
4031 /* Override any_segment if we're in the middle of a segment. */
4033 *any_segment = *segment;
4035 *seg_byte_offset = offset;
4037 g_assert (*segment != NULL);
4038 g_assert (*any_segment != NULL);
4039 g_assert (*seg_byte_offset < (*segment)->byte_count);
4041 *line_byte_offset = bytes_in_line + *seg_byte_offset;
4046 /* FIXME sync with byte_locate (or figure out a clean
4047 way to merge the two functions) */
4049 _gtk_text_line_char_locate (GtkTextLine *line,
4051 GtkTextLineSegment **segment,
4052 GtkTextLineSegment **any_segment,
4053 gint *seg_char_offset,
4054 gint *line_char_offset)
4056 GtkTextLineSegment *seg;
4057 GtkTextLineSegment *after_last_indexable;
4058 GtkTextLineSegment *last_indexable;
4062 g_return_val_if_fail (line != NULL, FALSE);
4063 g_return_val_if_fail (char_offset >= 0, FALSE);
4066 *any_segment = NULL;
4069 offset = char_offset;
4071 last_indexable = NULL;
4072 after_last_indexable = line->segments;
4073 seg = line->segments;
4075 /* The loop ends when we're inside a segment;
4076 last_indexable refers to the last segment
4077 we passed entirely. */
4078 while (seg && offset >= seg->char_count)
4080 if (seg->char_count > 0)
4082 offset -= seg->char_count;
4083 chars_in_line += seg->char_count;
4084 last_indexable = seg;
4085 after_last_indexable = last_indexable->next;
4093 /* end of the line */
4095 g_warning ("%s: char offset off the end of the line", G_STRLOC);
4102 if (after_last_indexable != NULL)
4103 *any_segment = after_last_indexable;
4105 *any_segment = *segment;
4108 /* Override any_segment if we're in the middle of a segment. */
4110 *any_segment = *segment;
4112 *seg_char_offset = offset;
4114 g_assert (*segment != NULL);
4115 g_assert (*any_segment != NULL);
4116 g_assert (*seg_char_offset < (*segment)->char_count);
4118 *line_char_offset = chars_in_line + *seg_char_offset;
4124 _gtk_text_line_byte_to_char_offsets (GtkTextLine *line,
4126 gint *line_char_offset,
4127 gint *seg_char_offset)
4129 GtkTextLineSegment *seg;
4132 g_return_if_fail (line != NULL);
4133 g_return_if_fail (byte_offset >= 0);
4135 *line_char_offset = 0;
4137 offset = byte_offset;
4138 seg = line->segments;
4140 while (offset >= seg->byte_count)
4142 offset -= seg->byte_count;
4143 *line_char_offset += seg->char_count;
4145 g_assert (seg != NULL); /* means an invalid char offset */
4148 g_assert (seg->char_count > 0); /* indexable. */
4150 /* offset is now the number of bytes into the current segment we
4151 * want to go. Count chars into the current segment.
4154 if (seg->type == >k_text_char_type)
4156 *seg_char_offset = g_utf8_strlen (seg->body.chars, offset);
4158 g_assert (*seg_char_offset < seg->char_count);
4160 *line_char_offset += *seg_char_offset;
4164 g_assert (offset == 0);
4165 *seg_char_offset = 0;
4170 _gtk_text_line_char_to_byte_offsets (GtkTextLine *line,
4172 gint *line_byte_offset,
4173 gint *seg_byte_offset)
4175 GtkTextLineSegment *seg;
4178 g_return_if_fail (line != NULL);
4179 g_return_if_fail (char_offset >= 0);
4181 *line_byte_offset = 0;
4183 offset = char_offset;
4184 seg = line->segments;
4186 while (offset >= seg->char_count)
4188 offset -= seg->char_count;
4189 *line_byte_offset += seg->byte_count;
4191 g_assert (seg != NULL); /* means an invalid char offset */
4194 g_assert (seg->char_count > 0); /* indexable. */
4196 /* offset is now the number of chars into the current segment we
4197 want to go. Count bytes into the current segment. */
4199 if (seg->type == >k_text_char_type)
4203 /* if in the last fourth of the segment walk backwards */
4204 if (seg->char_count - offset < seg->char_count / 4)
4205 p = g_utf8_offset_to_pointer (seg->body.chars + seg->byte_count,
4206 offset - seg->char_count);
4208 p = g_utf8_offset_to_pointer (seg->body.chars, offset);
4210 *seg_byte_offset = p - seg->body.chars;
4212 g_assert (*seg_byte_offset < seg->byte_count);
4214 *line_byte_offset += *seg_byte_offset;
4218 g_assert (offset == 0);
4219 *seg_byte_offset = 0;
4224 node_compare (GtkTextBTreeNode *lhs,
4225 GtkTextBTreeNode *rhs)
4227 GtkTextBTreeNode *iter;
4228 GtkTextBTreeNode *node;
4229 GtkTextBTreeNode *common_parent;
4230 GtkTextBTreeNode *parent_of_lower;
4231 GtkTextBTreeNode *parent_of_higher;
4232 gboolean lhs_is_lower;
4233 GtkTextBTreeNode *lower;
4234 GtkTextBTreeNode *higher;
4236 /* This function assumes that lhs and rhs are not underneath each
4243 if (lhs->level < rhs->level)
4245 lhs_is_lower = TRUE;
4251 lhs_is_lower = FALSE;
4256 /* Algorithm: find common parent of lhs/rhs. Save the child nodes
4257 * of the common parent we used to reach the common parent; the
4258 * ordering of these child nodes in the child list is the ordering
4262 /* Get on the same level (may be on same level already) */
4264 while (node->level < higher->level)
4265 node = node->parent;
4267 g_assert (node->level == higher->level);
4269 g_assert (node != higher); /* Happens if lower is underneath higher */
4271 /* Go up until we have two children with a common parent.
4273 parent_of_lower = node;
4274 parent_of_higher = higher;
4276 while (parent_of_lower->parent != parent_of_higher->parent)
4278 parent_of_lower = parent_of_lower->parent;
4279 parent_of_higher = parent_of_higher->parent;
4282 g_assert (parent_of_lower->parent == parent_of_higher->parent);
4284 common_parent = parent_of_lower->parent;
4286 g_assert (common_parent != NULL);
4288 /* See which is first in the list of common_parent's children */
4289 iter = common_parent->children.node;
4290 while (iter != NULL)
4292 if (iter == parent_of_higher)
4294 /* higher is less than lower */
4297 return 1; /* lhs > rhs */
4301 else if (iter == parent_of_lower)
4303 /* lower is less than higher */
4306 return -1; /* lhs < rhs */
4314 g_assert_not_reached ();
4318 /* remember that tag == NULL means "any tag" */
4320 _gtk_text_line_next_could_contain_tag (GtkTextLine *line,
4324 GtkTextBTreeNode *node;
4325 GtkTextTagInfo *info;
4326 gboolean below_tag_root;
4328 g_return_val_if_fail (line != NULL, NULL);
4330 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4331 _gtk_text_btree_check (tree);
4335 /* Right now we can only offer linear-search if the user wants
4336 * to know about any tag toggle at all.
4338 return _gtk_text_line_next_excluding_last (line);
4341 /* Our tag summaries only have node precision, not line
4342 * precision. This means that if any line under a node could contain a
4343 * tag, then any of the others could also contain a tag.
4345 * In the future we could have some mechanism to keep track of how
4346 * many toggles we've found under a node so far, since we have a
4347 * count of toggles under the node. But for now I'm going with KISS.
4350 /* return same-node line, if any. */
4354 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4358 if (info->tag_root == NULL)
4361 if (info->tag_root == line->parent)
4362 return NULL; /* we were at the last line under the tag root */
4364 /* We need to go up out of this node, and on to the next one with
4365 toggles for the target tag. If we're below the tag root, we need to
4366 find the next node below the tag root that has tag summaries. If
4367 we're not below the tag root, we need to see if the tag root is
4368 after us in the tree, and if so, return the first line underneath
4371 node = line->parent;
4372 below_tag_root = FALSE;
4373 while (node != NULL)
4375 if (node == info->tag_root)
4377 below_tag_root = TRUE;
4381 node = node->parent;
4386 node = line->parent;
4387 while (node != info->tag_root)
4389 if (node->next == NULL)
4390 node = node->parent;
4395 if (gtk_text_btree_node_has_tag (node, tag))
4405 ordering = node_compare (line->parent, info->tag_root);
4409 /* Tag root is ahead of us, so search there. */
4410 node = info->tag_root;
4415 /* Tag root is after us, so no more lines that
4416 * could contain the tag.
4421 g_assert_not_reached ();
4426 g_assert (node != NULL);
4428 /* We have to find the first sub-node of this node that contains
4432 while (node->level > 0)
4434 g_assert (node != NULL); /* If this fails, it likely means an
4435 incorrect tag summary led us on a
4436 wild goose chase down this branch of
4438 node = node->children.node;
4439 while (node != NULL)
4441 if (gtk_text_btree_node_has_tag (node, tag))
4447 g_assert (node != NULL);
4448 g_assert (node->level == 0);
4450 return node->children.line;
4454 prev_line_under_node (GtkTextBTreeNode *node,
4459 prev = node->children.line;
4465 while (prev->next != line)
4475 _gtk_text_line_previous_could_contain_tag (GtkTextLine *line,
4479 GtkTextBTreeNode *node;
4480 GtkTextBTreeNode *found_node = NULL;
4481 GtkTextTagInfo *info;
4482 gboolean below_tag_root;
4484 GtkTextBTreeNode *line_ancestor;
4485 GtkTextBTreeNode *line_ancestor_parent;
4487 /* See next_could_contain_tag () for more extensive comments
4488 * on what's going on here.
4491 g_return_val_if_fail (line != NULL, NULL);
4493 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4494 _gtk_text_btree_check (tree);
4498 /* Right now we can only offer linear-search if the user wants
4499 * to know about any tag toggle at all.
4501 return _gtk_text_line_previous (line);
4504 /* Return same-node line, if any. */
4505 prev = prev_line_under_node (line->parent, line);
4509 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4513 if (info->tag_root == NULL)
4516 if (info->tag_root == line->parent)
4517 return NULL; /* we were at the first line under the tag root */
4519 /* Are we below the tag root */
4520 node = line->parent;
4521 below_tag_root = FALSE;
4522 while (node != NULL)
4524 if (node == info->tag_root)
4526 below_tag_root = TRUE;
4530 node = node->parent;
4535 /* Look for a previous node under this tag root that has our
4539 /* this assertion holds because line->parent is not the
4540 * tag root, we are below the tag root, and the tag
4543 g_assert (line->parent->parent != NULL);
4545 line_ancestor = line->parent;
4546 line_ancestor_parent = line->parent->parent;
4548 while (line_ancestor != info->tag_root)
4550 GSList *child_nodes = NULL;
4553 /* Create reverse-order list of nodes before
4556 if (line_ancestor_parent != NULL)
4557 node = line_ancestor_parent->children.node;
4559 node = line_ancestor;
4561 while (node != line_ancestor && node != NULL)
4563 child_nodes = g_slist_prepend (child_nodes, node);
4568 /* Try to find a node with our tag on it in the list */
4572 GtkTextBTreeNode *this_node = tmp->data;
4574 g_assert (this_node != line_ancestor);
4576 if (gtk_text_btree_node_has_tag (this_node, tag))
4578 found_node = this_node;
4579 g_slist_free (child_nodes);
4583 tmp = g_slist_next (tmp);
4586 g_slist_free (child_nodes);
4588 /* Didn't find anything on this level; go up one level. */
4589 line_ancestor = line_ancestor_parent;
4590 line_ancestor_parent = line_ancestor->parent;
4600 ordering = node_compare (line->parent, info->tag_root);
4604 /* Tag root is ahead of us, so no more lines
4611 /* Tag root is after us, so grab last tagged
4612 * line underneath the tag root.
4614 found_node = info->tag_root;
4618 g_assert_not_reached ();
4623 g_assert (found_node != NULL);
4625 /* We have to find the last sub-node of this node that contains
4630 while (node->level > 0)
4632 GSList *child_nodes = NULL;
4634 g_assert (node != NULL); /* If this fails, it likely means an
4635 incorrect tag summary led us on a
4636 wild goose chase down this branch of
4639 node = node->children.node;
4640 while (node != NULL)
4642 child_nodes = g_slist_prepend (child_nodes, node);
4646 node = NULL; /* detect failure to find a child node. */
4649 while (iter != NULL)
4651 if (gtk_text_btree_node_has_tag (iter->data, tag))
4653 /* recurse into this node. */
4658 iter = g_slist_next (iter);
4661 g_slist_free (child_nodes);
4663 g_assert (node != NULL);
4666 g_assert (node != NULL);
4667 g_assert (node->level == 0);
4669 /* this assertion is correct, but slow. */
4670 /* g_assert (node_compare (node, line->parent) < 0); */
4672 /* Return last line in this node. */
4674 prev = node->children.line;
4682 * Non-public function implementations
4686 summary_list_destroy (Summary *summary)
4688 g_slice_free_chain (Summary, summary, next);
4692 get_last_line (GtkTextBTree *tree)
4694 if (tree->last_line_stamp != tree->chars_changed_stamp)
4700 n_lines = _gtk_text_btree_line_count (tree);
4702 g_assert (n_lines >= 1); /* num_lines doesn't return bogus last line. */
4704 line = _gtk_text_btree_get_line (tree, n_lines, &real_line);
4706 tree->last_line_stamp = tree->chars_changed_stamp;
4707 tree->last_line = line;
4710 return tree->last_line;
4718 gtk_text_line_new (void)
4722 line = g_new0(GtkTextLine, 1);
4723 line->dir_strong = PANGO_DIRECTION_NEUTRAL;
4724 line->dir_propagated_forward = PANGO_DIRECTION_NEUTRAL;
4725 line->dir_propagated_back = PANGO_DIRECTION_NEUTRAL;
4731 gtk_text_line_destroy (GtkTextBTree *tree, GtkTextLine *line)
4733 GtkTextLineData *ld;
4734 GtkTextLineData *next;
4736 g_return_if_fail (line != NULL);
4743 view = gtk_text_btree_get_view (tree, ld->view_id);
4745 g_assert (view != NULL);
4748 gtk_text_layout_free_line_data (view->layout, line, ld);
4757 gtk_text_line_set_parent (GtkTextLine *line,
4758 GtkTextBTreeNode *node)
4760 if (line->parent == node)
4762 line->parent = node;
4763 gtk_text_btree_node_invalidate_upward (node, NULL);
4767 cleanup_line (GtkTextLine *line)
4769 GtkTextLineSegment *seg, **prev_p;
4773 * Make a pass over all of the segments in the line, giving each
4774 * a chance to clean itself up. This could potentially change
4775 * the structure of the line, e.g. by merging two segments
4776 * together or having two segments cancel themselves; if so,
4777 * then repeat the whole process again, since the first structure
4778 * change might make other structure changes possible. Repeat
4779 * until eventually there are no changes.
4786 prev_p = &line->segments;
4787 for (seg = *prev_p; seg != NULL; seg = *prev_p)
4789 if (seg->type->cleanupFunc != NULL)
4791 *prev_p = (*seg->type->cleanupFunc)(seg, line);
4799 prev_p = &(*prev_p)->next;
4809 node_data_new (gpointer view_id)
4813 nd = g_slice_new (NodeData);
4815 nd->view_id = view_id;
4825 node_data_destroy (NodeData *nd)
4827 g_slice_free (NodeData, nd);
4831 node_data_list_destroy (NodeData *nd)
4833 g_slice_free_chain (NodeData, nd, next);
4837 node_data_find (NodeData *nd,
4842 if (nd->view_id == view_id)
4850 summary_destroy (Summary *summary)
4852 /* Fill with error-triggering garbage */
4853 summary->info = (void*)0x1;
4854 summary->toggle_count = 567;
4855 summary->next = (void*)0x1;
4856 g_slice_free (Summary, summary);
4859 static GtkTextBTreeNode*
4860 gtk_text_btree_node_new (void)
4862 GtkTextBTreeNode *node;
4864 node = g_new (GtkTextBTreeNode, 1);
4866 node->node_data = NULL;
4872 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
4873 GtkTextTagInfo *info,
4878 summary = node->summary;
4879 while (summary != NULL)
4881 if (summary->info == info)
4883 summary->toggle_count += adjust;
4887 summary = summary->next;
4890 if (summary == NULL)
4892 /* didn't find a summary for our tag. */
4893 g_return_if_fail (adjust > 0);
4894 summary = g_slice_new (Summary);
4895 summary->info = info;
4896 summary->toggle_count = adjust;
4897 summary->next = node->summary;
4898 node->summary = summary;
4902 /* Note that the tag root and above do not have summaries
4903 for the tag; only nodes below the tag root have
4906 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4910 summary = node->summary;
4911 while (summary != NULL)
4914 summary->info->tag == tag)
4917 summary = summary->next;
4923 /* Add node and all children to the damage region. */
4926 gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node)
4930 nd = node->node_data;
4937 if (node->level == 0)
4941 line = node->children.line;
4942 while (line != NULL)
4944 GtkTextLineData *ld;
4958 GtkTextBTreeNode *child;
4960 child = node->children.node;
4962 while (child != NULL)
4964 gtk_text_btree_node_invalidate_downward (child);
4966 child = child->next;
4973 gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node, gpointer view_id)
4975 GtkTextBTreeNode *iter;
4978 while (iter != NULL)
4984 nd = node_data_find (iter->node_data, view_id);
4986 if (nd == NULL || !nd->valid)
4987 break; /* Once a node is invalid, we know its parents are as well. */
4993 gboolean should_continue = FALSE;
4995 nd = iter->node_data;
5000 should_continue = TRUE;
5007 if (!should_continue)
5008 break; /* This node was totally invalidated, so are its
5012 iter = iter->parent;
5018 * _gtk_text_btree_is_valid:
5019 * @tree: a #GtkTextBTree
5020 * @view_id: ID for the view
5022 * Check to see if the entire #GtkTextBTree is valid or not for
5025 * Return value: %TRUE if the entire #GtkTextBTree is valid
5028 _gtk_text_btree_is_valid (GtkTextBTree *tree,
5032 g_return_val_if_fail (tree != NULL, FALSE);
5034 nd = node_data_find (tree->root_node->node_data, view_id);
5035 return (nd && nd->valid);
5038 typedef struct _ValidateState ValidateState;
5040 struct _ValidateState
5042 gint remaining_pixels;
5043 gboolean in_validation;
5050 gtk_text_btree_node_validate (BTreeView *view,
5051 GtkTextBTreeNode *node,
5053 ValidateState *state)
5055 gint node_valid = TRUE;
5056 gint node_width = 0;
5057 gint node_height = 0;
5059 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5060 g_return_if_fail (!nd->valid);
5062 if (node->level == 0)
5064 GtkTextLine *line = node->children.line;
5065 GtkTextLineData *ld;
5067 /* Iterate over leading valid lines */
5068 while (line != NULL)
5070 ld = _gtk_text_line_get_data (line, view_id);
5072 if (!ld || !ld->valid)
5074 else if (state->in_validation)
5076 state->in_validation = FALSE;
5081 state->y += ld->height;
5082 node_width = MAX (ld->width, node_width);
5083 node_height += ld->height;
5089 state->in_validation = TRUE;
5091 /* Iterate over invalid lines */
5092 while (line != NULL)
5094 ld = _gtk_text_line_get_data (line, view_id);
5096 if (ld && ld->valid)
5101 state->old_height += ld->height;
5102 ld = gtk_text_layout_wrap (view->layout, line, ld);
5103 state->new_height += ld->height;
5105 node_width = MAX (ld->width, node_width);
5106 node_height += ld->height;
5108 state->remaining_pixels -= ld->height;
5109 if (state->remaining_pixels <= 0)
5119 /* Iterate over the remaining lines */
5120 while (line != NULL)
5122 ld = _gtk_text_line_get_data (line, view_id);
5123 state->in_validation = FALSE;
5125 if (!ld || !ld->valid)
5130 node_width = MAX (ld->width, node_width);
5131 node_height += ld->height;
5139 GtkTextBTreeNode *child;
5142 child = node->children.node;
5144 /* Iterate over leading valid nodes */
5147 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5149 if (!child_nd->valid)
5151 else if (state->in_validation)
5153 state->in_validation = FALSE;
5158 state->y += child_nd->height;
5159 node_width = MAX (node_width, child_nd->width);
5160 node_height += child_nd->height;
5163 child = child->next;
5166 /* Iterate over invalid nodes */
5169 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5171 if (child_nd->valid)
5175 gtk_text_btree_node_validate (view, child, view_id, state);
5177 if (!child_nd->valid)
5179 node_width = MAX (node_width, child_nd->width);
5180 node_height += child_nd->height;
5182 if (!state->in_validation || state->remaining_pixels <= 0)
5184 child = child->next;
5189 child = child->next;
5192 /* Iterate over the remaining lines */
5195 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5196 state->in_validation = FALSE;
5198 if (!child_nd->valid)
5201 node_width = MAX (child_nd->width, node_width);
5202 node_height += child_nd->height;
5204 child = child->next;
5208 nd->width = node_width;
5209 nd->height = node_height;
5210 nd->valid = node_valid;
5214 * _gtk_text_btree_validate:
5215 * @tree: a #GtkTextBTree
5217 * @max_pixels: the maximum number of pixels to validate. (No more
5218 * than one paragraph beyond this limit will be validated)
5219 * @y: location to store starting y coordinate of validated region
5220 * @old_height: location to store old height of validated region
5221 * @new_height: location to store new height of validated region
5223 * Validate a single contiguous invalid region of a #GtkTextBTree for
5226 * Return value: %TRUE if a region has been validated, %FALSE if the
5227 * entire tree was already valid.
5230 _gtk_text_btree_validate (GtkTextBTree *tree,
5239 g_return_val_if_fail (tree != NULL, FALSE);
5241 view = gtk_text_btree_get_view (tree, view_id);
5242 g_return_val_if_fail (view != NULL, FALSE);
5244 if (!_gtk_text_btree_is_valid (tree, view_id))
5246 ValidateState state;
5248 state.remaining_pixels = max_pixels;
5249 state.in_validation = FALSE;
5251 state.old_height = 0;
5252 state.new_height = 0;
5254 gtk_text_btree_node_validate (view,
5261 *old_height = state.old_height;
5263 *new_height = state.new_height;
5265 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5266 _gtk_text_btree_check (tree);
5275 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
5279 gboolean *valid_out)
5283 gboolean valid = TRUE;
5285 if (node->level == 0)
5287 GtkTextLine *line = node->children.line;
5289 while (line != NULL)
5291 GtkTextLineData *ld = _gtk_text_line_get_data (line, view_id);
5293 if (!ld || !ld->valid)
5298 width = MAX (ld->width, width);
5299 height += ld->height;
5307 GtkTextBTreeNode *child = node->children.node;
5311 NodeData *child_nd = node_data_find (child->node_data, view_id);
5313 if (!child_nd || !child_nd->valid)
5318 width = MAX (child_nd->width, width);
5319 height += child_nd->height;
5322 child = child->next;
5327 *height_out = height;
5332 /* Recompute the validity and size of the view data for a given
5333 * view at this node from the immediate children of the node
5336 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
5339 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5344 gtk_text_btree_node_compute_view_aggregates (node, view_id,
5345 &width, &height, &valid);
5347 nd->height = height;
5354 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
5359 gtk_text_btree_node_check_valid (node, view_id);
5360 node = node->parent;
5365 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
5368 if (node->level == 0)
5370 return gtk_text_btree_node_check_valid (node, view_id);
5374 GtkTextBTreeNode *child = node->children.node;
5376 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5384 NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
5386 if (!child_nd->valid)
5388 nd->width = MAX (child_nd->width, nd->width);
5389 nd->height += child_nd->height;
5391 child = child->next;
5400 * _gtk_text_btree_validate_line:
5401 * @tree: a #GtkTextBTree
5402 * @line: line to validate
5403 * @view_id: view ID for the view to validate
5405 * Revalidate a single line of the btree for the given view, propagate
5406 * results up through the entire tree.
5409 _gtk_text_btree_validate_line (GtkTextBTree *tree,
5413 GtkTextLineData *ld;
5416 g_return_if_fail (tree != NULL);
5417 g_return_if_fail (line != NULL);
5419 view = gtk_text_btree_get_view (tree, view_id);
5420 g_return_if_fail (view != NULL);
5422 ld = _gtk_text_line_get_data (line, view_id);
5423 if (!ld || !ld->valid)
5425 ld = gtk_text_layout_wrap (view->layout, line, ld);
5427 gtk_text_btree_node_check_valid_upward (line->parent, view_id);
5432 gtk_text_btree_node_remove_view (BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
5434 if (node->level == 0)
5438 line = node->children.line;
5439 while (line != NULL)
5441 GtkTextLineData *ld;
5443 ld = _gtk_text_line_remove_data (line, view_id);
5446 gtk_text_layout_free_line_data (view->layout, line, ld);
5453 GtkTextBTreeNode *child;
5455 child = node->children.node;
5457 while (child != NULL)
5460 gtk_text_btree_node_remove_view (view, child, view_id);
5462 child = child->next;
5466 gtk_text_btree_node_remove_data (node, view_id);
5470 gtk_text_btree_node_destroy (GtkTextBTree *tree, GtkTextBTreeNode *node)
5472 if (node->level == 0)
5475 GtkTextLineSegment *seg;
5477 while (node->children.line != NULL)
5479 line = node->children.line;
5480 node->children.line = line->next;
5481 while (line->segments != NULL)
5483 seg = line->segments;
5484 line->segments = seg->next;
5486 (*seg->type->deleteFunc) (seg, line, TRUE);
5488 gtk_text_line_destroy (tree, line);
5493 GtkTextBTreeNode *childPtr;
5495 while (node->children.node != NULL)
5497 childPtr = node->children.node;
5498 node->children.node = childPtr->next;
5499 gtk_text_btree_node_destroy (tree, childPtr);
5503 gtk_text_btree_node_free_empty (tree, node);
5507 gtk_text_btree_node_free_empty (GtkTextBTree *tree,
5508 GtkTextBTreeNode *node)
5510 g_return_if_fail ((node->level > 0 && node->children.node == NULL) ||
5511 (node->level == 0 && node->children.line == NULL));
5513 summary_list_destroy (node->summary);
5514 node_data_list_destroy (node->node_data);
5519 gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node, gpointer view_id)
5523 nd = node->node_data;
5526 if (nd->view_id == view_id)
5534 nd = node_data_new (view_id);
5536 if (node->node_data)
5537 nd->next = node->node_data;
5539 node->node_data = nd;
5546 gtk_text_btree_node_remove_data (GtkTextBTreeNode *node, gpointer view_id)
5552 nd = node->node_data;
5555 if (nd->view_id == view_id)
5566 prev->next = nd->next;
5568 if (node->node_data == nd)
5569 node->node_data = nd->next;
5573 node_data_destroy (nd);
5577 gtk_text_btree_node_get_size (GtkTextBTreeNode *node, gpointer view_id,
5578 gint *width, gint *height)
5582 g_return_if_fail (width != NULL);
5583 g_return_if_fail (height != NULL);
5585 nd = gtk_text_btree_node_ensure_data (node, view_id);
5590 *height = nd->height;
5593 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5594 * here isn't quite right, since for a lot of operations we want to
5595 * know which children of the common parent correspond to the two nodes
5596 * (e.g., when computing the order of two iters)
5598 static GtkTextBTreeNode *
5599 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5600 GtkTextBTreeNode *node2)
5602 while (node1->level < node2->level)
5603 node1 = node1->parent;
5604 while (node2->level < node1->level)
5605 node2 = node2->parent;
5606 while (node1 != node2)
5608 node1 = node1->parent;
5609 node2 = node2->parent;
5620 gtk_text_btree_get_view (GtkTextBTree *tree, gpointer view_id)
5625 while (view != NULL)
5627 if (view->view_id == view_id)
5636 get_tree_bounds (GtkTextBTree *tree,
5640 _gtk_text_btree_get_iter_at_line_char (tree, start, 0, 0);
5641 _gtk_text_btree_get_end_iter (tree, end);
5645 tag_changed_cb (GtkTextTagTable *table,
5647 gboolean size_changed,
5652 /* We need to queue a relayout on all regions that are tagged with
5659 if (_gtk_text_btree_get_iter_at_first_toggle (tree, &start, tag))
5661 /* Must be a last toggle if there was a first one. */
5662 _gtk_text_btree_get_iter_at_last_toggle (tree, &end, tag);
5663 DV (g_print ("invalidating due to tag change (%s)\n", G_STRLOC));
5664 _gtk_text_btree_invalidate_region (tree, &start, &end, FALSE);
5670 /* We only need to queue a redraw, not a relayout */
5675 while (view != NULL)
5679 _gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5680 gtk_text_layout_changed (view->layout, 0, height, height);
5688 _gtk_text_btree_notify_will_remove_tag (GtkTextBTree *tree,
5691 /* Remove the tag from the tree */
5696 get_tree_bounds (tree, &start, &end);
5698 _gtk_text_btree_tag (&start, &end, tag, FALSE);
5699 gtk_text_btree_remove_tag_info (tree, tag);
5703 /* Rebalance the out-of-whack node "node" */
5705 gtk_text_btree_rebalance (GtkTextBTree *tree,
5706 GtkTextBTreeNode *node)
5709 * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5710 * up through the tree one GtkTextBTreeNode at a time until the root
5711 * GtkTextBTreeNode has been processed.
5714 while (node != NULL)
5716 GtkTextBTreeNode *new_node, *child;
5721 * Check to see if the GtkTextBTreeNode has too many children. If it does,
5722 * then split off all but the first MIN_CHILDREN into a separate
5723 * GtkTextBTreeNode following the original one. Then repeat until the
5724 * GtkTextBTreeNode has a decent size.
5727 if (node->num_children > MAX_CHILDREN)
5732 * If the GtkTextBTreeNode being split is the root
5733 * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5737 if (node->parent == NULL)
5739 new_node = gtk_text_btree_node_new ();
5740 new_node->parent = NULL;
5741 new_node->next = NULL;
5742 new_node->summary = NULL;
5743 new_node->level = node->level + 1;
5744 new_node->children.node = node;
5745 recompute_node_counts (tree, new_node);
5746 tree->root_node = new_node;
5748 new_node = gtk_text_btree_node_new ();
5749 new_node->parent = node->parent;
5750 new_node->next = node->next;
5751 node->next = new_node;
5752 new_node->summary = NULL;
5753 new_node->level = node->level;
5754 new_node->num_children = node->num_children - MIN_CHILDREN;
5755 if (node->level == 0)
5757 for (i = MIN_CHILDREN-1,
5758 line = node->children.line;
5759 i > 0; i--, line = line->next)
5761 /* Empty loop body. */
5763 new_node->children.line = line->next;
5768 for (i = MIN_CHILDREN-1,
5769 child = node->children.node;
5770 i > 0; i--, child = child->next)
5772 /* Empty loop body. */
5774 new_node->children.node = child->next;
5777 recompute_node_counts (tree, node);
5778 node->parent->num_children++;
5780 if (node->num_children <= MAX_CHILDREN)
5782 recompute_node_counts (tree, node);
5788 while (node->num_children < MIN_CHILDREN)
5790 GtkTextBTreeNode *other;
5791 GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5792 GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5793 int total_children, first_children, i;
5796 * Too few children for this GtkTextBTreeNode. If this is the root then,
5797 * it's OK for it to have less than MIN_CHILDREN children
5798 * as long as it's got at least two. If it has only one
5799 * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5800 * the tree and use its child as the new root.
5803 if (node->parent == NULL)
5805 if ((node->num_children == 1) && (node->level > 0))
5807 tree->root_node = node->children.node;
5808 tree->root_node->parent = NULL;
5810 node->children.node = NULL;
5811 gtk_text_btree_node_free_empty (tree, node);
5817 * Not the root. Make sure that there are siblings to
5821 if (node->parent->num_children < 2)
5823 gtk_text_btree_rebalance (tree, node->parent);
5828 * Find a sibling neighbor to borrow from, and arrange for
5829 * node to be the earlier of the pair.
5832 if (node->next == NULL)
5834 for (other = node->parent->children.node;
5835 other->next != node;
5836 other = other->next)
5838 /* Empty loop body. */
5845 * We're going to either merge the two siblings together
5846 * into one GtkTextBTreeNode or redivide the children among them to
5847 * balance their loads. As preparation, join their two
5848 * child lists into a single list and remember the half-way
5849 * point in the list.
5852 total_children = node->num_children + other->num_children;
5853 first_children = total_children/2;
5854 if (node->children.node == NULL)
5856 node->children = other->children;
5857 other->children.node = NULL;
5858 other->children.line = NULL;
5860 if (node->level == 0)
5864 for (line = node->children.line, i = 1;
5866 line = line->next, i++)
5868 if (i == first_children)
5873 line->next = other->children.line;
5874 while (i <= first_children)
5883 GtkTextBTreeNode *child;
5885 for (child = node->children.node, i = 1;
5886 child->next != NULL;
5887 child = child->next, i++)
5889 if (i <= first_children)
5891 if (i == first_children)
5893 halfwaynode = child;
5897 child->next = other->children.node;
5898 while (i <= first_children)
5900 halfwaynode = child;
5901 child = child->next;
5907 * If the two siblings can simply be merged together, do it.
5910 if (total_children <= MAX_CHILDREN)
5912 recompute_node_counts (tree, node);
5913 node->next = other->next;
5914 node->parent->num_children--;
5916 other->children.node = NULL;
5917 other->children.line = NULL;
5918 gtk_text_btree_node_free_empty (tree, other);
5923 * The siblings can't be merged, so just divide their
5924 * children evenly between them.
5927 if (node->level == 0)
5929 other->children.line = halfwayline->next;
5930 halfwayline->next = NULL;
5934 other->children.node = halfwaynode->next;
5935 halfwaynode->next = NULL;
5938 recompute_node_counts (tree, node);
5939 recompute_node_counts (tree, other);
5942 node = node->parent;
5947 post_insert_fixup (GtkTextBTree *tree,
5949 gint line_count_delta,
5950 gint char_count_delta)
5953 GtkTextBTreeNode *node;
5956 * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5957 * point, then rebalance the tree if necessary.
5960 for (node = line->parent ; node != NULL;
5961 node = node->parent)
5963 node->num_lines += line_count_delta;
5964 node->num_chars += char_count_delta;
5966 node = line->parent;
5967 node->num_children += line_count_delta;
5969 if (node->num_children > MAX_CHILDREN)
5971 gtk_text_btree_rebalance (tree, node);
5974 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5975 _gtk_text_btree_check (tree);
5978 static GtkTextTagInfo*
5979 gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
5982 GtkTextTagInfo *info;
5986 list = tree->tag_infos;
5987 while (list != NULL)
5990 if (info->tag == tag)
5993 list = g_slist_next (list);
5999 static GtkTextTagInfo*
6000 gtk_text_btree_get_tag_info (GtkTextBTree *tree,
6003 GtkTextTagInfo *info;
6005 info = gtk_text_btree_get_existing_tag_info (tree, tag);
6009 /* didn't find it, create. */
6011 info = g_slice_new (GtkTextTagInfo);
6015 info->tag_root = NULL;
6016 info->toggle_count = 0;
6018 tree->tag_infos = g_slist_prepend (tree->tag_infos, info);
6021 g_print ("Created tag info %p for tag %s(%p)\n",
6022 info, info->tag->name ? info->tag->name : "anon",
6031 gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
6034 GtkTextTagInfo *info;
6039 list = tree->tag_infos;
6040 while (list != NULL)
6043 if (info->tag == tag)
6046 g_print ("Removing tag info %p for tag %s(%p)\n",
6047 info, info->tag->name ? info->tag->name : "anon",
6053 prev->next = list->next;
6057 tree->tag_infos = list->next;
6060 g_slist_free (list);
6062 g_object_unref (info->tag);
6064 g_slice_free (GtkTextTagInfo, info);
6069 list = g_slist_next (list);
6074 recompute_level_zero_counts (GtkTextBTreeNode *node)
6077 GtkTextLineSegment *seg;
6079 g_assert (node->level == 0);
6081 line = node->children.line;
6082 while (line != NULL)
6084 node->num_children++;
6087 if (line->parent != node)
6088 gtk_text_line_set_parent (line, node);
6090 seg = line->segments;
6094 node->num_chars += seg->char_count;
6096 if (((seg->type != >k_text_toggle_on_type)
6097 && (seg->type != >k_text_toggle_off_type))
6098 || !(seg->body.toggle.inNodeCounts))
6104 GtkTextTagInfo *info;
6106 info = seg->body.toggle.info;
6108 gtk_text_btree_node_adjust_toggle_count (node, info, 1);
6119 recompute_level_nonzero_counts (GtkTextBTreeNode *node)
6122 GtkTextBTreeNode *child;
6124 g_assert (node->level > 0);
6126 child = node->children.node;
6127 while (child != NULL)
6129 node->num_children += 1;
6130 node->num_lines += child->num_lines;
6131 node->num_chars += child->num_chars;
6133 if (child->parent != node)
6135 child->parent = node;
6136 gtk_text_btree_node_invalidate_upward (node, NULL);
6139 summary = child->summary;
6140 while (summary != NULL)
6142 gtk_text_btree_node_adjust_toggle_count (node,
6144 summary->toggle_count);
6146 summary = summary->next;
6149 child = child->next;
6154 *----------------------------------------------------------------------
6156 * recompute_node_counts --
6158 * This procedure is called to recompute all the counts in a GtkTextBTreeNode
6159 * (tags, child information, etc.) by scanning the information in
6160 * its descendants. This procedure is called during rebalancing
6161 * when a GtkTextBTreeNode's child structure has changed.
6167 * The tag counts for node are modified to reflect its current
6168 * child structure, as are its num_children, num_lines, num_chars fields.
6169 * Also, all of the childrens' parent fields are made to point
6172 *----------------------------------------------------------------------
6176 recompute_node_counts (GtkTextBTree *tree, GtkTextBTreeNode *node)
6179 Summary *summary, *summary2;
6182 * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
6183 * the existing Summary records (most of them will probably be reused).
6186 summary = node->summary;
6187 while (summary != NULL)
6189 summary->toggle_count = 0;
6190 summary = summary->next;
6193 node->num_children = 0;
6194 node->num_lines = 0;
6195 node->num_chars = 0;
6198 * Scan through the children, adding the childrens' tag counts into
6199 * the GtkTextBTreeNode's tag counts and adding new Summary structures if
6203 if (node->level == 0)
6204 recompute_level_zero_counts (node);
6206 recompute_level_nonzero_counts (node);
6211 gtk_text_btree_node_check_valid (node, view->view_id);
6216 * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
6217 * records that still have a zero count, or that have all the toggles.
6218 * The GtkTextBTreeNode with the children that account for all the tags toggles
6219 * have no summary information, and they become the tag_root for the tag.
6223 for (summary = node->summary; summary != NULL; )
6225 if (summary->toggle_count > 0 &&
6226 summary->toggle_count < summary->info->toggle_count)
6228 if (node->level == summary->info->tag_root->level)
6231 * The tag's root GtkTextBTreeNode split and some toggles left.
6232 * The tag root must move up a level.
6234 summary->info->tag_root = node->parent;
6237 summary = summary->next;
6240 if (summary->toggle_count == summary->info->toggle_count)
6243 * A GtkTextBTreeNode merge has collected all the toggles under
6244 * one GtkTextBTreeNode. Push the root down to this level.
6246 summary->info->tag_root = node;
6248 if (summary2 != NULL)
6250 summary2->next = summary->next;
6251 summary_destroy (summary);
6252 summary = summary2->next;
6256 node->summary = summary->next;
6257 summary_destroy (summary);
6258 summary = node->summary;
6264 _gtk_change_node_toggle_count (GtkTextBTreeNode *node,
6265 GtkTextTagInfo *info,
6266 gint delta) /* may be negative */
6268 Summary *summary, *prevPtr;
6269 GtkTextBTreeNode *node2Ptr;
6270 int rootLevel; /* Level of original tag root */
6272 info->toggle_count += delta;
6274 if (info->tag_root == (GtkTextBTreeNode *) NULL)
6276 info->tag_root = node;
6281 * Note the level of the existing root for the tag so we can detect
6282 * if it needs to be moved because of the toggle count change.
6285 rootLevel = info->tag_root->level;
6288 * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
6289 * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
6293 for ( ; node != info->tag_root; node = node->parent)
6296 * See if there's already an entry for this tag for this GtkTextBTreeNode. If so,
6297 * perhaps all we have to do is adjust its count.
6300 for (prevPtr = NULL, summary = node->summary;
6302 prevPtr = summary, summary = summary->next)
6304 if (summary->info == info)
6309 if (summary != NULL)
6311 summary->toggle_count += delta;
6312 if (summary->toggle_count > 0 &&
6313 summary->toggle_count < info->toggle_count)
6317 if (summary->toggle_count != 0)
6320 * Should never find a GtkTextBTreeNode with max toggle count at this
6321 * point (there shouldn't have been a summary entry in the
6325 g_error ("%s: bad toggle count (%d) max (%d)",
6326 G_STRLOC, summary->toggle_count, info->toggle_count);
6330 * Zero toggle count; must remove this tag from the list.
6333 if (prevPtr == NULL)
6335 node->summary = summary->next;
6339 prevPtr->next = summary->next;
6341 summary_destroy (summary);
6346 * This tag isn't currently in the summary information list.
6349 if (rootLevel == node->level)
6353 * The old tag root is at the same level in the tree as this
6354 * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode. Move the tag root up
6355 * a level, in the hopes that it will now cover this GtkTextBTreeNode
6356 * as well as the old root (if not, we'll move it up again
6357 * the next time through the loop). To push it up one level
6358 * we copy the original toggle count into the summary
6359 * information at the old root and change the root to its
6360 * parent GtkTextBTreeNode.
6363 GtkTextBTreeNode *rootnode = info->tag_root;
6364 summary = g_slice_new (Summary);
6365 summary->info = info;
6366 summary->toggle_count = info->toggle_count - delta;
6367 summary->next = rootnode->summary;
6368 rootnode->summary = summary;
6369 rootnode = rootnode->parent;
6370 rootLevel = rootnode->level;
6371 info->tag_root = rootnode;
6373 summary = g_slice_new (Summary);
6374 summary->info = info;
6375 summary->toggle_count = delta;
6376 summary->next = node->summary;
6377 node->summary = summary;
6382 * If we've decremented the toggle count, then it may be necessary
6383 * to push the tag root down one or more levels.
6390 if (info->toggle_count == 0)
6392 info->tag_root = (GtkTextBTreeNode *) NULL;
6395 node = info->tag_root;
6396 while (node->level > 0)
6399 * See if a single child GtkTextBTreeNode accounts for all of the tag's
6400 * toggles. If so, push the root down one level.
6403 for (node2Ptr = node->children.node;
6404 node2Ptr != (GtkTextBTreeNode *)NULL ;
6405 node2Ptr = node2Ptr->next)
6407 for (prevPtr = NULL, summary = node2Ptr->summary;
6409 prevPtr = summary, summary = summary->next)
6411 if (summary->info == info)
6416 if (summary == NULL)
6420 if (summary->toggle_count != info->toggle_count)
6423 * No GtkTextBTreeNode has all toggles, so the root is still valid.
6430 * This GtkTextBTreeNode has all the toggles, so push down the root.
6433 if (prevPtr == NULL)
6435 node2Ptr->summary = summary->next;
6439 prevPtr->next = summary->next;
6441 summary_destroy (summary);
6442 info->tag_root = node2Ptr;
6445 node = info->tag_root;
6450 *----------------------------------------------------------------------
6454 * This is a utility procedure used by _gtk_text_btree_get_tags. It
6455 * increments the count for a particular tag, adding a new
6456 * entry for that tag if there wasn't one previously.
6462 * The information at *tagInfoPtr may be modified, and the arrays
6463 * may be reallocated to make them larger.
6465 *----------------------------------------------------------------------
6469 inc_count (GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
6474 for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
6475 count > 0; tag_p++, count--)
6479 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
6485 * There isn't currently an entry for this tag, so we have to
6486 * make a new one. If the arrays are full, then enlarge the
6490 if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
6492 GtkTextTag **newTags;
6493 int *newCounts, newSize;
6495 newSize = 2*tagInfoPtr->arraySize;
6496 newTags = (GtkTextTag **) g_malloc ((unsigned)
6497 (newSize*sizeof (GtkTextTag *)));
6498 memcpy ((void *) newTags, (void *) tagInfoPtr->tags,
6499 tagInfoPtr->arraySize *sizeof (GtkTextTag *));
6500 g_free ((char *) tagInfoPtr->tags);
6501 tagInfoPtr->tags = newTags;
6502 newCounts = (int *) g_malloc ((unsigned) (newSize*sizeof (int)));
6503 memcpy ((void *) newCounts, (void *) tagInfoPtr->counts,
6504 tagInfoPtr->arraySize *sizeof (int));
6505 g_free ((char *) tagInfoPtr->counts);
6506 tagInfoPtr->counts = newCounts;
6507 tagInfoPtr->arraySize = newSize;
6510 tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
6511 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
6512 tagInfoPtr->numTags++;
6516 gtk_text_btree_link_segment (GtkTextLineSegment *seg,
6517 const GtkTextIter *iter)
6519 GtkTextLineSegment *prev;
6523 line = _gtk_text_iter_get_text_line (iter);
6524 tree = _gtk_text_iter_get_btree (iter);
6526 prev = gtk_text_line_segment_split (iter);
6529 seg->next = line->segments;
6530 line->segments = seg;
6534 seg->next = prev->next;
6537 cleanup_line (line);
6538 segments_changed (tree);
6540 if (gtk_debug_flags & GTK_DEBUG_TEXT)
6541 _gtk_text_btree_check (tree);
6545 gtk_text_btree_unlink_segment (GtkTextBTree *tree,
6546 GtkTextLineSegment *seg,
6549 GtkTextLineSegment *prev;
6551 if (line->segments == seg)
6553 line->segments = seg->next;
6557 for (prev = line->segments; prev->next != seg;
6560 /* Empty loop body. */
6562 prev->next = seg->next;
6564 cleanup_line (line);
6565 segments_changed (tree);
6569 * This is here because it requires BTree internals, it logically
6570 * belongs in gtktextsegment.c
6575 *--------------------------------------------------------------
6577 * _gtk_toggle_segment_check_func --
6579 * This procedure is invoked to perform consistency checks
6580 * on toggle segments.
6586 * If a consistency problem is found the procedure g_errors.
6588 *--------------------------------------------------------------
6592 _gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6598 if (segPtr->byte_count != 0)
6600 g_error ("toggle_segment_check_func: segment had non-zero size");
6602 if (!segPtr->body.toggle.inNodeCounts)
6604 g_error ("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6606 needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6607 for (summary = line->parent->summary; ;
6608 summary = summary->next)
6610 if (summary == NULL)
6614 g_error ("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6621 if (summary->info == segPtr->body.toggle.info)
6625 g_error ("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6637 gtk_text_btree_node_view_check_consistency (GtkTextBTree *tree,
6638 GtkTextBTreeNode *node,
6648 while (view != NULL)
6650 if (view->view_id == nd->view_id)
6657 g_error ("Node has data for a view %p no longer attached to the tree",
6660 gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6661 &width, &height, &valid);
6663 /* valid aggregate not checked the same as width/height, because on
6664 * btree rebalance we can have invalid nodes where all lines below
6665 * them are actually valid, due to moving lines around between
6668 * The guarantee is that if there are invalid lines the node is
6669 * invalid - we don't guarantee that if the node is invalid there
6670 * are invalid lines.
6673 if (nd->width != width ||
6674 nd->height != height ||
6675 (nd->valid && !valid))
6677 g_error ("Node aggregates for view %p are invalid:\n"
6678 "Are (%d,%d,%s), should be (%d,%d,%s)",
6680 nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6681 width, height, valid ? "TRUE" : "FALSE");
6686 gtk_text_btree_node_check_consistency (GtkTextBTree *tree,
6687 GtkTextBTreeNode *node)
6689 GtkTextBTreeNode *childnode;
6690 Summary *summary, *summary2;
6692 GtkTextLineSegment *segPtr;
6693 int num_children, num_lines, num_chars, toggle_count, min_children;
6694 GtkTextLineData *ld;
6697 if (node->parent != NULL)
6699 min_children = MIN_CHILDREN;
6701 else if (node->level > 0)
6708 if ((node->num_children < min_children)
6709 || (node->num_children > MAX_CHILDREN))
6711 g_error ("gtk_text_btree_node_check_consistency: bad child count (%d)",
6712 node->num_children);
6715 nd = node->node_data;
6718 gtk_text_btree_node_view_check_consistency (tree, node, nd);
6725 if (node->level == 0)
6727 for (line = node->children.line; line != NULL;
6730 if (line->parent != node)
6732 g_error ("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6734 if (line->segments == NULL)
6736 g_error ("gtk_text_btree_node_check_consistency: line has no segments");
6742 /* Just ensuring we don't segv while doing this loop */
6747 for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6749 if (segPtr->type->checkFunc != NULL)
6751 (*segPtr->type->checkFunc)(segPtr, line);
6753 if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6754 && (segPtr->next != NULL)
6755 && (segPtr->next->byte_count == 0)
6756 && (segPtr->next->type->leftGravity))
6758 g_error ("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6760 if ((segPtr->next == NULL)
6761 && (segPtr->type != >k_text_char_type))
6763 g_error ("gtk_text_btree_node_check_consistency: line ended with wrong type");
6766 num_chars += segPtr->char_count;
6775 for (childnode = node->children.node; childnode != NULL;
6776 childnode = childnode->next)
6778 if (childnode->parent != node)
6780 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6782 if (childnode->level != (node->level-1))
6784 g_error ("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6785 node->level, childnode->level);
6787 gtk_text_btree_node_check_consistency (tree, childnode);
6788 for (summary = childnode->summary; summary != NULL;
6789 summary = summary->next)
6791 for (summary2 = node->summary; ;
6792 summary2 = summary2->next)
6794 if (summary2 == NULL)
6796 if (summary->info->tag_root == node)
6800 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6801 summary->info->tag->name,
6802 "present in parent summaries");
6804 if (summary->info == summary2->info)
6811 num_lines += childnode->num_lines;
6812 num_chars += childnode->num_chars;
6815 if (num_children != node->num_children)
6817 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6818 num_children, node->num_children);
6820 if (num_lines != node->num_lines)
6822 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6823 num_lines, node->num_lines);
6825 if (num_chars != node->num_chars)
6827 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6828 num_chars, node->num_chars);
6831 for (summary = node->summary; summary != NULL;
6832 summary = summary->next)
6834 if (summary->info->toggle_count == summary->toggle_count)
6836 g_error ("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6837 summary->info->tag->name);
6840 if (node->level == 0)
6842 for (line = node->children.line; line != NULL;
6845 for (segPtr = line->segments; segPtr != NULL;
6846 segPtr = segPtr->next)
6848 if ((segPtr->type != >k_text_toggle_on_type)
6849 && (segPtr->type != >k_text_toggle_off_type))
6853 if (segPtr->body.toggle.info == summary->info)
6855 if (!segPtr->body.toggle.inNodeCounts)
6856 g_error ("Toggle segment not in the node counts");
6865 for (childnode = node->children.node;
6867 childnode = childnode->next)
6869 for (summary2 = childnode->summary;
6871 summary2 = summary2->next)
6873 if (summary2->info == summary->info)
6875 toggle_count += summary2->toggle_count;
6880 if (toggle_count != summary->toggle_count)
6882 g_error ("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6883 toggle_count, summary->toggle_count);
6885 for (summary2 = summary->next; summary2 != NULL;
6886 summary2 = summary2->next)
6888 if (summary2->info == summary->info)
6890 g_error ("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6891 summary->info->tag->name);
6898 listify_foreach (GtkTextTag *tag, gpointer user_data)
6900 GSList** listp = user_data;
6902 *listp = g_slist_prepend (*listp, tag);
6906 list_of_tags (GtkTextTagTable *table)
6908 GSList *list = NULL;
6910 gtk_text_tag_table_foreach (table, listify_foreach, &list);
6916 _gtk_text_btree_check (GtkTextBTree *tree)
6919 GtkTextBTreeNode *node;
6921 GtkTextLineSegment *seg;
6923 GSList *all_tags, *taglist = NULL;
6925 GtkTextTagInfo *info;
6928 * Make sure that the tag toggle counts and the tag root pointers are OK.
6930 all_tags = list_of_tags (tree->table);
6931 for (taglist = all_tags; taglist != NULL ; taglist = taglist->next)
6933 tag = taglist->data;
6934 info = gtk_text_btree_get_existing_tag_info (tree, tag);
6937 node = info->tag_root;
6940 if (info->toggle_count != 0)
6942 g_error ("_gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6943 tag->name, info->toggle_count);
6945 continue; /* no ranges for the tag */
6947 else if (info->toggle_count == 0)
6949 g_error ("_gtk_text_btree_check found root for \"%s\" with no toggles",
6952 else if (info->toggle_count & 1)
6954 g_error ("_gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6955 tag->name, info->toggle_count);
6957 for (summary = node->summary; summary != NULL;
6958 summary = summary->next)
6960 if (summary->info->tag == tag)
6962 g_error ("_gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6966 if (node->level > 0)
6968 for (node = node->children.node ; node != NULL ;
6971 for (summary = node->summary; summary != NULL;
6972 summary = summary->next)
6974 if (summary->info->tag == tag)
6976 count += summary->toggle_count;
6983 const GtkTextLineSegmentClass *last = NULL;
6985 for (line = node->children.line ; line != NULL ;
6988 for (seg = line->segments; seg != NULL;
6991 if ((seg->type == >k_text_toggle_on_type ||
6992 seg->type == >k_text_toggle_off_type) &&
6993 seg->body.toggle.info->tag == tag)
6995 if (last == seg->type)
6996 g_error ("Two consecutive toggles on or off weren't merged");
6997 if (!seg->body.toggle.inNodeCounts)
6998 g_error ("Toggle segment not in the node counts");
7007 if (count != info->toggle_count)
7009 g_error ("_gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
7010 info->toggle_count, tag->name, count);
7015 g_slist_free (all_tags);
7018 * Call a recursive procedure to do the main body of checks.
7021 node = tree->root_node;
7022 gtk_text_btree_node_check_consistency (tree, tree->root_node);
7025 * Make sure that there are at least two lines in the text and
7026 * that the last line has no characters except a newline.
7029 if (node->num_lines < 2)
7031 g_error ("_gtk_text_btree_check: less than 2 lines in tree");
7033 if (node->num_chars < 2)
7035 g_error ("_gtk_text_btree_check: less than 2 chars in tree");
7037 while (node->level > 0)
7039 node = node->children.node;
7040 while (node->next != NULL)
7045 line = node->children.line;
7046 while (line->next != NULL)
7050 seg = line->segments;
7051 while ((seg->type == >k_text_toggle_off_type)
7052 || (seg->type == >k_text_right_mark_type)
7053 || (seg->type == >k_text_left_mark_type))
7056 * It's OK to toggle a tag off in the last line, but
7057 * not to start a new range. It's also OK to have marks
7063 if (seg->type != >k_text_char_type)
7065 g_error ("_gtk_text_btree_check: last line has bogus segment type");
7067 if (seg->next != NULL)
7069 g_error ("_gtk_text_btree_check: last line has too many segments");
7071 if (seg->byte_count != 1)
7073 g_error ("_gtk_text_btree_check: last line has wrong # characters: %d",
7076 if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
7078 g_error ("_gtk_text_btree_check: last line had bad value: %s",
7083 void _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line);
7084 void _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment* seg);
7085 void _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent);
7086 void _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
7089 _gtk_text_btree_spew (GtkTextBTree *tree)
7094 printf ("%d lines in tree %p\n",
7095 _gtk_text_btree_line_count (tree), tree);
7097 line = _gtk_text_btree_get_line (tree, 0, &real_line);
7099 while (line != NULL)
7101 _gtk_text_btree_spew_line (tree, line);
7102 line = _gtk_text_line_next (line);
7105 printf ("=================== Tag information\n");
7110 list = tree->tag_infos;
7112 while (list != NULL)
7114 GtkTextTagInfo *info;
7118 printf (" tag `%s': root at %p, toggle count %d\n",
7119 info->tag->name, info->tag_root, info->toggle_count);
7121 list = g_slist_next (list);
7124 if (tree->tag_infos == NULL)
7126 printf (" (no tags in the tree)\n");
7130 printf ("=================== Tree nodes\n");
7133 _gtk_text_btree_spew_node (tree->root_node, 0);
7138 _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
7141 GtkTextLineSegment *seg;
7143 spaces = g_strnfill (indent, ' ');
7145 printf ("%sline %p chars %d bytes %d\n",
7147 _gtk_text_line_char_count (line),
7148 _gtk_text_line_byte_count (line));
7150 seg = line->segments;
7153 if (seg->type == >k_text_char_type)
7155 gchar* str = g_strndup (seg->body.chars, MIN (seg->byte_count, 10));
7160 if (*s == '\n' || *s == '\r')
7164 printf ("%s chars `%s'...\n", spaces, str);
7167 else if (seg->type == >k_text_right_mark_type)
7169 printf ("%s right mark `%s' visible: %d\n",
7171 seg->body.mark.name,
7172 seg->body.mark.visible);
7174 else if (seg->type == >k_text_left_mark_type)
7176 printf ("%s left mark `%s' visible: %d\n",
7178 seg->body.mark.name,
7179 seg->body.mark.visible);
7181 else if (seg->type == >k_text_toggle_on_type ||
7182 seg->type == >k_text_toggle_off_type)
7184 printf ("%s tag `%s' %s\n",
7185 spaces, seg->body.toggle.info->tag->name,
7186 seg->type == >k_text_toggle_off_type ? "off" : "on");
7196 _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent)
7199 GtkTextBTreeNode *iter;
7202 spaces = g_strnfill (indent, ' ');
7204 printf ("%snode %p level %d children %d lines %d chars %d\n",
7205 spaces, node, node->level,
7206 node->num_children, node->num_lines, node->num_chars);
7211 printf ("%s %d toggles of `%s' below this node\n",
7212 spaces, s->toggle_count, s->info->tag->name);
7218 if (node->level > 0)
7220 iter = node->children.node;
7221 while (iter != NULL)
7223 _gtk_text_btree_spew_node (iter, indent + 2);
7230 GtkTextLine *line = node->children.line;
7231 while (line != NULL)
7233 _gtk_text_btree_spew_line_short (line, indent + 2);
7241 _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line)
7243 GtkTextLineSegment * seg;
7245 printf ("%4d| line: %p parent: %p next: %p\n",
7246 _gtk_text_line_get_number (line), line, line->parent, line->next);
7248 seg = line->segments;
7252 _gtk_text_btree_spew_segment (tree, seg);
7258 _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment * seg)
7260 printf (" segment: %p type: %s bytes: %d chars: %d\n",
7261 seg, seg->type->name, seg->byte_count, seg->char_count);
7263 if (seg->type == >k_text_char_type)
7265 gchar* str = g_strndup (seg->body.chars, seg->byte_count);
7266 printf (" `%s'\n", str);
7269 else if (seg->type == >k_text_right_mark_type)
7271 printf (" right mark `%s' visible: %d not_deleteable: %d\n",
7272 seg->body.mark.name,
7273 seg->body.mark.visible,
7274 seg->body.mark.not_deleteable);
7276 else if (seg->type == >k_text_left_mark_type)
7278 printf (" left mark `%s' visible: %d not_deleteable: %d\n",
7279 seg->body.mark.name,
7280 seg->body.mark.visible,
7281 seg->body.mark.not_deleteable);
7283 else if (seg->type == >k_text_toggle_on_type ||
7284 seg->type == >k_text_toggle_off_type)
7286 printf (" tag `%s' priority %d\n",
7287 seg->body.toggle.info->tag->name,
7288 seg->body.toggle.info->tag->priority);