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);
283 static void gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node);
284 static void gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node,
286 static NodeData * gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
288 static NodeData * gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
290 static void gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
293 static void gtk_text_btree_node_remove_view (BTreeView *view,
294 GtkTextBTreeNode *node,
296 static void gtk_text_btree_node_destroy (GtkTextBTree *tree,
297 GtkTextBTreeNode *node);
298 static void gtk_text_btree_node_free_empty (GtkTextBTree *tree,
299 GtkTextBTreeNode *node);
300 static NodeData * gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node,
302 static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
304 static void gtk_text_btree_node_get_size (GtkTextBTreeNode *node,
308 static GtkTextBTreeNode * gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
309 GtkTextBTreeNode *node2);
310 static void get_tree_bounds (GtkTextBTree *tree,
313 static void tag_changed_cb (GtkTextTagTable *table,
315 gboolean size_changed,
317 static void cleanup_line (GtkTextLine *line);
318 static void recompute_node_counts (GtkTextBTree *tree,
319 GtkTextBTreeNode *node);
320 static void inc_count (GtkTextTag *tag,
322 TagInfo *tagInfoPtr);
324 static void summary_destroy (Summary *summary);
326 static void gtk_text_btree_link_segment (GtkTextLineSegment *seg,
327 const GtkTextIter *iter);
328 static void gtk_text_btree_unlink_segment (GtkTextBTree *tree,
329 GtkTextLineSegment *seg,
333 static GtkTextTagInfo *gtk_text_btree_get_tag_info (GtkTextBTree *tree,
335 static GtkTextTagInfo *gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
337 static void gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
340 static void redisplay_region (GtkTextBTree *tree,
341 const GtkTextIter *start,
342 const GtkTextIter *end);
344 /* Inline thingies */
347 segments_changed (GtkTextBTree *tree)
349 tree->segments_changed_stamp += 1;
353 chars_changed (GtkTextBTree *tree)
355 tree->chars_changed_stamp += 1;
363 _gtk_text_btree_new (GtkTextTagTable *table,
364 GtkTextBuffer *buffer)
367 GtkTextBTreeNode *root_node;
368 GtkTextLine *line, *line2;
370 g_return_val_if_fail (GTK_IS_TEXT_TAG_TABLE (table), NULL);
371 g_return_val_if_fail (GTK_IS_TEXT_BUFFER (buffer), NULL);
374 * The tree will initially have two empty lines. The second line
375 * isn't actually part of the tree's contents, but its presence
376 * makes several operations easier. The tree will have one GtkTextBTreeNode,
377 * which is also the root of the tree.
380 /* Create the root node. */
382 root_node = gtk_text_btree_node_new ();
384 line = gtk_text_line_new ();
385 line2 = gtk_text_line_new ();
387 root_node->parent = NULL;
388 root_node->next = NULL;
389 root_node->summary = NULL;
390 root_node->level = 0;
391 root_node->children.line = line;
392 root_node->num_children = 2;
393 root_node->num_lines = 2;
394 root_node->num_chars = 2;
396 line->parent = root_node;
399 line->segments = _gtk_char_segment_new ("\n", 1);
401 line2->parent = root_node;
403 line2->segments = _gtk_char_segment_new ("\n", 1);
405 /* Create the tree itself */
407 tree = g_new0(GtkTextBTree, 1);
408 tree->root_node = root_node;
412 /* Set these to values that are unlikely to be found
413 * in random memory garbage, and also avoid
414 * duplicates between tree instances.
416 tree->chars_changed_stamp = g_random_int ();
417 tree->segments_changed_stamp = g_random_int ();
419 tree->last_line_stamp = tree->chars_changed_stamp - 1;
420 tree->last_line = NULL;
422 tree->end_iter_line_stamp = tree->chars_changed_stamp - 1;
423 tree->end_iter_segment_stamp = tree->segments_changed_stamp - 1;
424 tree->end_iter_line = NULL;
425 tree->end_iter_segment_byte_index = 0;
426 tree->end_iter_segment_char_offset = 0;
428 g_object_ref (tree->table);
430 tree->tag_changed_handler = g_signal_connect (tree->table,
432 G_CALLBACK (tag_changed_cb),
435 tree->mark_table = g_hash_table_new (g_str_hash, g_str_equal);
436 tree->child_anchor_table = NULL;
438 /* We don't ref the buffer, since the buffer owns us;
439 * we'd have some circularity issues. The buffer always
440 * lasts longer than the BTree
442 tree->buffer = buffer;
446 GtkTextLineSegment *seg;
448 _gtk_text_btree_get_iter_at_line_char (tree, &start, 0, 0);
451 tree->insert_mark = _gtk_text_btree_set_mark (tree,
458 seg = tree->insert_mark->segment;
460 seg->body.mark.not_deleteable = TRUE;
461 seg->body.mark.visible = TRUE;
463 tree->selection_bound_mark = _gtk_text_btree_set_mark (tree,
470 seg = tree->selection_bound_mark->segment;
472 seg->body.mark.not_deleteable = TRUE;
474 g_object_ref (tree->insert_mark);
475 g_object_ref (tree->selection_bound_mark);
484 _gtk_text_btree_ref (GtkTextBTree *tree)
486 g_return_if_fail (tree != NULL);
487 g_return_if_fail (tree->refcount > 0);
493 _gtk_text_btree_unref (GtkTextBTree *tree)
495 g_return_if_fail (tree != NULL);
496 g_return_if_fail (tree->refcount > 0);
500 if (tree->refcount == 0)
502 g_signal_handler_disconnect (tree->table,
503 tree->tag_changed_handler);
505 g_object_unref (tree->table);
508 gtk_text_btree_node_destroy (tree, tree->root_node);
509 tree->root_node = NULL;
511 g_assert (g_hash_table_size (tree->mark_table) == 0);
512 g_hash_table_destroy (tree->mark_table);
513 tree->mark_table = NULL;
514 if (tree->child_anchor_table != NULL)
516 g_hash_table_destroy (tree->child_anchor_table);
517 tree->child_anchor_table = NULL;
520 g_object_unref (tree->insert_mark);
521 tree->insert_mark = NULL;
522 g_object_unref (tree->selection_bound_mark);
523 tree->selection_bound_mark = NULL;
530 _gtk_text_btree_get_buffer (GtkTextBTree *tree)
536 _gtk_text_btree_get_chars_changed_stamp (GtkTextBTree *tree)
538 return tree->chars_changed_stamp;
542 _gtk_text_btree_get_segments_changed_stamp (GtkTextBTree *tree)
544 return tree->segments_changed_stamp;
548 _gtk_text_btree_segments_changed (GtkTextBTree *tree)
550 g_return_if_fail (tree != NULL);
551 segments_changed (tree);
555 * Indexable segment mutation
559 * The following function is responsible for resolving the bidi direction
560 * for the lines between start and end. But it also calculates any
561 * dependent bidi direction for surrounding lines that change as a result
562 * of the bidi direction decisions within the range. The function is
563 * trying to do as little propagation as is needed.
566 gtk_text_btree_resolve_bidi (GtkTextIter *start,
569 GtkTextBTree *tree = _gtk_text_iter_get_btree (start);
570 GtkTextLine *start_line, *end_line, *start_line_prev, *end_line_next, *line;
571 PangoDirection last_strong, dir_above_propagated, dir_below_propagated;
573 /* Resolve the strong bidi direction for all lines between
576 start_line = _gtk_text_iter_get_text_line (start);
577 start_line_prev = _gtk_text_line_previous (start_line);
578 end_line = _gtk_text_iter_get_text_line (end);
579 end_line_next = _gtk_text_line_next (end_line);
582 while (line && line != end_line_next)
584 /* Loop through the segments and search for a strong character
586 GtkTextLineSegment *seg = line->segments;
587 line->dir_strong = PANGO_DIRECTION_NEUTRAL;
591 if (seg->byte_count > 0)
593 PangoDirection pango_dir;
595 pango_dir = pango_find_base_dir (seg->body.chars,
598 if (pango_dir != PANGO_DIRECTION_NEUTRAL)
600 line->dir_strong = pango_dir;
607 line = _gtk_text_line_next (line);
612 /* The variable dir_above_propagated contains the forward propagated
613 * direction before start. It is neutral if start is in the beginning
616 dir_above_propagated = PANGO_DIRECTION_NEUTRAL;
618 dir_above_propagated = start_line_prev->dir_propagated_forward;
620 /* Loop forward and propagate the direction of each paragraph
621 * to all neutral lines.
624 last_strong = dir_above_propagated;
625 while (line != end_line_next)
627 if (line->dir_strong != PANGO_DIRECTION_NEUTRAL)
628 last_strong = line->dir_strong;
630 line->dir_propagated_forward = last_strong;
632 line = _gtk_text_line_next (line);
635 /* Continue propagating as long as the previous resolved forward
636 * is different from last_strong.
639 GtkTextIter end_propagate;
642 line->dir_strong == PANGO_DIRECTION_NEUTRAL &&
643 line->dir_propagated_forward != last_strong)
645 GtkTextLine *prev = line;
646 line->dir_propagated_forward = last_strong;
648 line = _gtk_text_line_next(line);
656 /* The last line to invalidate is the last line before the
657 * line with the strong character. Or in case of the end of the
658 * buffer, the last line of the buffer. (There seems to be an
659 * extra "virtual" last line in the buffer that must not be used
660 * calling _gtk_text_btree_get_iter_at_line (causes crash). Thus the
661 * _gtk_text_line_previous is ok in that case as well.)
663 line = _gtk_text_line_previous (line);
664 _gtk_text_btree_get_iter_at_line (tree, &end_propagate, line, 0);
665 _gtk_text_btree_invalidate_region (tree, end, &end_propagate);
670 /* The variable dir_below_propagated contains the backward propagated
671 * direction after end. It is neutral if end is at the end of
674 dir_below_propagated = PANGO_DIRECTION_NEUTRAL;
676 dir_below_propagated = end_line_next->dir_propagated_back;
678 /* Loop backward and propagate the direction of each paragraph
679 * to all neutral lines.
682 last_strong = dir_below_propagated;
683 while (line != start_line_prev)
685 if (line->dir_strong != PANGO_DIRECTION_NEUTRAL)
686 last_strong = line->dir_strong;
688 line->dir_propagated_back = last_strong;
690 line = _gtk_text_line_previous (line);
693 /* Continue propagating as long as the resolved backward dir
694 * is different from last_strong.
697 GtkTextIter start_propagate;
700 line->dir_strong == PANGO_DIRECTION_NEUTRAL &&
701 line->dir_propagated_back != last_strong)
703 GtkTextLine *prev = line;
704 line->dir_propagated_back = last_strong;
706 line = _gtk_text_line_previous (line);
714 /* We only need to invalidate for backwards propagation if the
715 * line we ended up on didn't get a direction from forwards
718 if (line && line->dir_propagated_forward == PANGO_DIRECTION_NEUTRAL)
720 _gtk_text_btree_get_iter_at_line (tree, &start_propagate, line, 0);
721 _gtk_text_btree_invalidate_region(tree, &start_propagate, start);
727 _gtk_text_btree_delete (GtkTextIter *start,
730 GtkTextLineSegment *prev_seg; /* The segment just before the start
731 * of the deletion range. */
732 GtkTextLineSegment *last_seg; /* The segment just after the end
733 * of the deletion range. */
734 GtkTextLineSegment *seg, *next;
735 GtkTextLine *curline;
736 GtkTextBTreeNode *curnode, *node;
738 GtkTextLine *start_line;
739 GtkTextLine *end_line;
740 GtkTextLine *deleted_lines = NULL; /* List of lines we've deleted */
741 gint start_byte_offset;
743 g_return_if_fail (start != NULL);
744 g_return_if_fail (end != NULL);
745 g_return_if_fail (_gtk_text_iter_get_btree (start) ==
746 _gtk_text_iter_get_btree (end));
748 gtk_text_iter_order (start, end);
750 tree = _gtk_text_iter_get_btree (start);
752 if (gtk_debug_flags & GTK_DEBUG_TEXT)
753 _gtk_text_btree_check (tree);
755 /* Broadcast the need for redisplay before we break the iterators */
756 DV (g_print ("invalidating due to deleting some text (%s)\n", G_STRLOC));
757 _gtk_text_btree_invalidate_region (tree, start, end);
759 /* Save the byte offset so we can reset the iterators */
760 start_byte_offset = gtk_text_iter_get_line_index (start);
762 start_line = _gtk_text_iter_get_text_line (start);
763 end_line = _gtk_text_iter_get_text_line (end);
766 * Split the start and end segments, so we have a place
767 * to insert our new text.
769 * Tricky point: split at end first; otherwise the split
770 * at end may invalidate seg and/or prev_seg. This allows
771 * us to avoid invalidating segments for start.
774 last_seg = gtk_text_line_segment_split (end);
775 if (last_seg != NULL)
776 last_seg = last_seg->next;
778 last_seg = end_line->segments;
780 prev_seg = gtk_text_line_segment_split (start);
781 if (prev_seg != NULL)
783 seg = prev_seg->next;
784 prev_seg->next = last_seg;
788 seg = start_line->segments;
789 start_line->segments = last_seg;
792 /* notify iterators that their segments need recomputation,
793 just for robustness. */
794 segments_changed (tree);
797 * Delete all of the segments between prev_seg and last_seg.
800 curline = start_line;
801 curnode = curline->parent;
802 while (seg != last_seg)
808 GtkTextLine *nextline;
811 * We just ran off the end of a line. First find the
812 * next line, then go back to the old line and delete it
813 * (unless it's the starting line for the range).
816 nextline = _gtk_text_line_next (curline);
817 if (curline != start_line)
819 if (curnode == start_line->parent)
820 start_line->next = curline->next;
822 curnode->children.line = curline->next;
824 for (node = curnode; node != NULL;
827 /* Don't update node->num_chars, because
828 * that was done when we deleted the segments.
830 node->num_lines -= 1;
833 curnode->num_children -= 1;
834 curline->next = deleted_lines;
835 deleted_lines = curline;
839 seg = curline->segments;
842 * If the GtkTextBTreeNode is empty then delete it and its parents,
843 * recursively upwards until a non-empty GtkTextBTreeNode is found.
846 while (curnode->num_children == 0)
848 GtkTextBTreeNode *parent;
850 parent = curnode->parent;
851 if (parent->children.node == curnode)
853 parent->children.node = curnode->next;
857 GtkTextBTreeNode *prevnode = parent->children.node;
858 while (prevnode->next != curnode)
860 prevnode = prevnode->next;
862 prevnode->next = curnode->next;
864 parent->num_children--;
865 gtk_text_btree_node_free_empty (tree, curnode);
868 curnode = curline->parent;
873 char_count = seg->char_count;
875 if ((*seg->type->deleteFunc)(seg, curline, FALSE) != 0)
878 * This segment refuses to die. Move it to prev_seg and
879 * advance prev_seg if the segment has left gravity.
882 if (prev_seg == NULL)
884 seg->next = start_line->segments;
885 start_line->segments = seg;
889 seg->next = prev_seg->next;
890 prev_seg->next = seg;
892 if (seg->type->leftGravity)
899 /* Segment is gone. Decrement the char count of the node and
901 for (node = curnode; node != NULL;
904 node->num_chars -= char_count;
912 * If the beginning and end of the deletion range are in different
913 * lines, join the two lines together and discard the ending line.
916 if (start_line != end_line)
919 GtkTextBTreeNode *ancestor_node;
920 GtkTextLine *prevline;
923 /* last_seg was appended to start_line up at the top of this function */
925 for (seg = last_seg; seg != NULL;
928 chars_moved += seg->char_count;
929 if (seg->type->lineChangeFunc != NULL)
931 (*seg->type->lineChangeFunc)(seg, end_line);
935 for (node = start_line->parent; node != NULL;
938 node->num_chars += chars_moved;
941 curnode = end_line->parent;
942 for (node = curnode; node != NULL;
945 node->num_chars -= chars_moved;
948 curnode->num_children--;
949 prevline = curnode->children.line;
950 if (prevline == end_line)
952 curnode->children.line = end_line->next;
956 while (prevline->next != end_line)
958 prevline = prevline->next;
960 prevline->next = end_line->next;
962 end_line->next = deleted_lines;
963 deleted_lines = end_line;
965 /* We now fix up the per-view aggregates. We add all the height and
966 * width for the deleted lines to the start line, so that when revalidation
967 * occurs, the correct change in size is seen.
969 ancestor_node = gtk_text_btree_node_common_parent (curnode, start_line->parent);
976 gint deleted_width = 0;
977 gint deleted_height = 0;
979 line = deleted_lines;
982 GtkTextLine *next_line = line->next;
983 ld = _gtk_text_line_get_data (line, view->view_id);
987 deleted_width = MAX (deleted_width, ld->width);
988 deleted_height += ld->height;
992 gtk_text_line_destroy (tree, line);
997 if (deleted_width > 0 || deleted_height > 0)
999 ld = _gtk_text_line_get_data (start_line, view->view_id);
1003 /* This means that start_line has never been validated.
1004 * We don't really want to do the validation here but
1005 * we do need to store our temporary sizes. So we
1006 * create the line data and assume a line w/h of 0.
1008 ld = _gtk_text_line_data_new (view->layout, start_line);
1009 _gtk_text_line_add_data (start_line, ld);
1015 ld->width = MAX (deleted_width, ld->width);
1016 ld->height += deleted_height;
1020 gtk_text_btree_node_check_valid_downward (ancestor_node, view->view_id);
1021 if (ancestor_node->parent)
1022 gtk_text_btree_node_check_valid_upward (ancestor_node->parent, view->view_id);
1027 /* avoid dangling pointer */
1028 deleted_lines = NULL;
1030 gtk_text_btree_rebalance (tree, curnode);
1034 * Cleanup the segments in the new line.
1037 cleanup_line (start_line);
1040 * Lastly, rebalance the first GtkTextBTreeNode of the range.
1043 gtk_text_btree_rebalance (tree, start_line->parent);
1045 /* Notify outstanding iterators that they
1047 chars_changed (tree);
1048 segments_changed (tree);
1050 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1051 _gtk_text_btree_check (tree);
1053 /* Re-initialize our iterators */
1054 _gtk_text_btree_get_iter_at_line (tree, start, start_line, start_byte_offset);
1057 gtk_text_btree_resolve_bidi (start, end);
1061 _gtk_text_btree_insert (GtkTextIter *iter,
1065 GtkTextLineSegment *prev_seg; /* The segment just before the first
1066 * new segment (NULL means new segment
1067 * is at beginning of line). */
1068 GtkTextLineSegment *cur_seg; /* Current segment; new characters
1069 * are inserted just after this one.
1070 * NULL means insert at beginning of
1072 GtkTextLine *line; /* Current line (new segments are
1073 * added to this line). */
1074 GtkTextLineSegment *seg;
1075 GtkTextLine *newline;
1076 int chunk_len; /* # characters in current chunk. */
1077 gint sol; /* start of line */
1078 gint eol; /* Pointer to character just after last
1079 * one in current chunk.
1081 gint delim; /* index of paragraph delimiter */
1082 int line_count_delta; /* Counts change to total number of
1086 int char_count_delta; /* change to number of chars */
1088 gint start_byte_index;
1089 GtkTextLine *start_line;
1091 g_return_if_fail (text != NULL);
1092 g_return_if_fail (iter != NULL);
1095 len = strlen (text);
1097 /* extract iterator info */
1098 tree = _gtk_text_iter_get_btree (iter);
1099 line = _gtk_text_iter_get_text_line (iter);
1102 start_byte_index = gtk_text_iter_get_line_index (iter);
1104 /* Get our insertion segment split. Note this assumes line allows
1105 * char insertions, which isn't true of the "last" line. But iter
1106 * should not be on that line, as we assert here.
1108 g_assert (!_gtk_text_line_is_last (line, tree));
1109 prev_seg = gtk_text_line_segment_split (iter);
1112 /* Invalidate all iterators */
1113 chars_changed (tree);
1114 segments_changed (tree);
1117 * Chop the text up into lines and create a new segment for
1118 * each line, plus a new line for the leftovers from the
1124 line_count_delta = 0;
1125 char_count_delta = 0;
1130 pango_find_paragraph_boundary (text + sol,
1135 /* make these relative to the start of the text */
1139 g_assert (eol >= sol);
1140 g_assert (delim >= sol);
1141 g_assert (eol >= delim);
1142 g_assert (sol >= 0);
1143 g_assert (eol <= len);
1145 chunk_len = eol - sol;
1147 g_assert (g_utf8_validate (&text[sol], chunk_len, NULL));
1148 seg = _gtk_char_segment_new (&text[sol], chunk_len);
1150 char_count_delta += seg->char_count;
1152 if (cur_seg == NULL)
1154 seg->next = line->segments;
1155 line->segments = seg;
1159 seg->next = cur_seg->next;
1160 cur_seg->next = seg;
1165 /* chunk didn't end with a paragraph separator */
1166 g_assert (eol == len);
1171 * The chunk ended with a newline, so create a new GtkTextLine
1172 * and move the remainder of the old line to it.
1175 newline = gtk_text_line_new ();
1176 gtk_text_line_set_parent (newline, line->parent);
1177 newline->next = line->next;
1178 line->next = newline;
1179 newline->segments = seg->next;
1187 * Cleanup the starting line for the insertion, plus the ending
1188 * line if it's different.
1191 cleanup_line (start_line);
1192 if (line != start_line)
1194 cleanup_line (line);
1197 post_insert_fixup (tree, line, line_count_delta, char_count_delta);
1199 /* Invalidate our region, and reset the iterator the user
1200 passed in to point to the end of the inserted text. */
1206 _gtk_text_btree_get_iter_at_line (tree,
1212 /* We could almost certainly be more efficient here
1213 by saving the information from the insertion loop
1215 gtk_text_iter_forward_chars (&end, char_count_delta);
1217 DV (g_print ("invalidating due to inserting some text (%s)\n", G_STRLOC));
1218 _gtk_text_btree_invalidate_region (tree,
1222 /* Convenience for the user */
1225 gtk_text_btree_resolve_bidi (&start, &end);
1230 insert_pixbuf_or_widget_segment (GtkTextIter *iter,
1231 GtkTextLineSegment *seg)
1235 GtkTextLineSegment *prevPtr;
1238 gint start_byte_offset;
1240 line = _gtk_text_iter_get_text_line (iter);
1241 tree = _gtk_text_iter_get_btree (iter);
1242 start_byte_offset = gtk_text_iter_get_line_index (iter);
1244 prevPtr = gtk_text_line_segment_split (iter);
1245 if (prevPtr == NULL)
1247 seg->next = line->segments;
1248 line->segments = seg;
1252 seg->next = prevPtr->next;
1253 prevPtr->next = seg;
1256 post_insert_fixup (tree, line, 0, seg->char_count);
1258 chars_changed (tree);
1259 segments_changed (tree);
1261 /* reset *iter for the user, and invalidate tree nodes */
1263 _gtk_text_btree_get_iter_at_line (tree, &start, line, start_byte_offset);
1266 gtk_text_iter_forward_char (iter); /* skip forward past the segment */
1268 DV (g_print ("invalidating due to inserting pixbuf/widget (%s)\n", G_STRLOC));
1269 _gtk_text_btree_invalidate_region (tree, &start, iter);
1273 _gtk_text_btree_insert_pixbuf (GtkTextIter *iter,
1276 GtkTextLineSegment *seg;
1278 seg = _gtk_pixbuf_segment_new (pixbuf);
1280 insert_pixbuf_or_widget_segment (iter, seg);
1284 _gtk_text_btree_insert_child_anchor (GtkTextIter *iter,
1285 GtkTextChildAnchor *anchor)
1287 GtkTextLineSegment *seg;
1290 if (anchor->segment != NULL)
1292 g_warning (G_STRLOC": Same child anchor can't be inserted twice");
1296 seg = _gtk_widget_segment_new (anchor);
1298 tree = seg->body.child.tree = _gtk_text_iter_get_btree (iter);
1299 seg->body.child.line = _gtk_text_iter_get_text_line (iter);
1301 insert_pixbuf_or_widget_segment (iter, seg);
1303 if (tree->child_anchor_table == NULL)
1304 tree->child_anchor_table = g_hash_table_new (NULL, NULL);
1306 g_hash_table_insert (tree->child_anchor_table,
1307 seg->body.child.obj,
1308 seg->body.child.obj);
1312 _gtk_text_btree_unregister_child_anchor (GtkTextChildAnchor *anchor)
1314 GtkTextLineSegment *seg;
1316 seg = anchor->segment;
1318 g_hash_table_remove (seg->body.child.tree->child_anchor_table,
1327 find_line_by_y (GtkTextBTree *tree, BTreeView *view,
1328 GtkTextBTreeNode *node, gint y, gint *line_top,
1329 GtkTextLine *last_line)
1333 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1334 _gtk_text_btree_check (tree);
1336 if (node->level == 0)
1340 line = node->children.line;
1342 while (line != NULL && line != last_line)
1344 GtkTextLineData *ld;
1346 ld = _gtk_text_line_get_data (line, view->view_id);
1350 if (y < (current_y + (ld ? ld->height : 0)))
1353 current_y += ld->height;
1354 *line_top += ld->height;
1363 GtkTextBTreeNode *child;
1365 child = node->children.node;
1367 while (child != NULL)
1372 gtk_text_btree_node_get_size (child, view->view_id,
1375 if (y < (current_y + height))
1376 return find_line_by_y (tree, view, child,
1377 y - current_y, line_top,
1380 current_y += height;
1381 *line_top += height;
1383 child = child->next;
1391 _gtk_text_btree_find_line_by_y (GtkTextBTree *tree,
1398 GtkTextLine *last_line;
1401 view = gtk_text_btree_get_view (tree, view_id);
1402 g_return_val_if_fail (view != NULL, NULL);
1404 last_line = get_last_line (tree);
1406 line = find_line_by_y (tree, view, tree->root_node, ypixel, &line_top,
1410 *line_top_out = line_top;
1416 find_line_top_in_line_list (GtkTextBTree *tree,
1419 GtkTextLine *target_line,
1422 while (line != NULL)
1424 GtkTextLineData *ld;
1426 if (line == target_line)
1429 ld = _gtk_text_line_get_data (line, view->view_id);
1436 g_assert_not_reached (); /* If we get here, our
1437 target line didn't exist
1438 under its parent node */
1443 _gtk_text_btree_find_line_top (GtkTextBTree *tree,
1444 GtkTextLine *target_line,
1451 GtkTextBTreeNode *node;
1453 view = gtk_text_btree_get_view (tree, view_id);
1455 g_return_val_if_fail (view != NULL, 0);
1458 node = target_line->parent;
1459 while (node != NULL)
1461 nodes = g_slist_prepend (nodes, node);
1462 node = node->parent;
1466 while (iter != NULL)
1470 if (node->level == 0)
1472 g_slist_free (nodes);
1473 return find_line_top_in_line_list (tree, view,
1474 node->children.line,
1479 GtkTextBTreeNode *child;
1480 GtkTextBTreeNode *target_node;
1482 g_assert (iter->next != NULL); /* not at level 0 */
1483 target_node = iter->next->data;
1485 child = node->children.node;
1487 while (child != NULL)
1492 if (child == target_node)
1496 gtk_text_btree_node_get_size (child, view->view_id,
1500 child = child->next;
1502 g_assert (child != NULL); /* should have broken out before we
1506 iter = g_slist_next (iter);
1509 g_assert_not_reached (); /* we return when we find the target line */
1514 _gtk_text_btree_add_view (GtkTextBTree *tree,
1515 GtkTextLayout *layout)
1518 GtkTextLine *last_line;
1519 GtkTextLineData *line_data;
1521 g_return_if_fail (tree != NULL);
1523 view = g_new (BTreeView, 1);
1525 view->view_id = layout;
1526 view->layout = layout;
1528 view->next = tree->views;
1533 g_assert (tree->views->prev == NULL);
1534 tree->views->prev = view;
1539 /* The last line in the buffer has identity values for the per-view
1540 * data so that we can avoid special case checks for it in a large
1543 last_line = get_last_line (tree);
1545 line_data = g_new (GtkTextLineData, 1);
1546 line_data->view_id = layout;
1547 line_data->next = NULL;
1548 line_data->width = 0;
1549 line_data->height = 0;
1550 line_data->valid = TRUE;
1552 _gtk_text_line_add_data (last_line, line_data);
1556 _gtk_text_btree_remove_view (GtkTextBTree *tree,
1560 GtkTextLine *last_line;
1561 GtkTextLineData *line_data;
1563 g_return_if_fail (tree != NULL);
1567 while (view != NULL)
1569 if (view->view_id == view_id)
1575 g_return_if_fail (view != NULL);
1578 view->next->prev = view->prev;
1581 view->prev->next = view->next;
1583 if (view == tree->views)
1584 tree->views = view->next;
1586 /* Remove the line data for the last line which we added ourselves.
1587 * (Do this first, so that we don't try to call the view's line data destructor on it.)
1589 last_line = get_last_line (tree);
1590 line_data = _gtk_text_line_remove_data (last_line, view_id);
1593 gtk_text_btree_node_remove_view (view, tree->root_node, view_id);
1595 view->layout = (gpointer) 0xdeadbeef;
1596 view->view_id = (gpointer) 0xdeadbeef;
1602 _gtk_text_btree_invalidate_region (GtkTextBTree *tree,
1603 const GtkTextIter *start,
1604 const GtkTextIter *end)
1610 while (view != NULL)
1612 gtk_text_layout_invalidate (view->layout, start, end);
1619 _gtk_text_btree_get_view_size (GtkTextBTree *tree,
1624 g_return_if_fail (tree != NULL);
1625 g_return_if_fail (view_id != NULL);
1627 gtk_text_btree_node_get_size (tree->root_node, view_id,
1642 iter_stack_new (void)
1645 stack = g_new (IterStack, 1);
1646 stack->iters = NULL;
1653 iter_stack_push (IterStack *stack, const GtkTextIter *iter)
1656 if (stack->count > stack->alloced)
1658 stack->alloced = stack->count*2;
1659 stack->iters = g_realloc (stack->iters,
1660 stack->alloced*sizeof (GtkTextIter));
1662 stack->iters[stack->count-1] = *iter;
1666 iter_stack_pop (IterStack *stack, GtkTextIter *iter)
1668 if (stack->count == 0)
1673 *iter = stack->iters[stack->count];
1679 iter_stack_free (IterStack *stack)
1681 g_free (stack->iters);
1686 iter_stack_invert (IterStack *stack)
1688 if (stack->count > 0)
1691 guint j = stack->count - 1;
1696 tmp = stack->iters[i];
1697 stack->iters[i] = stack->iters[j];
1698 stack->iters[j] = tmp;
1707 queue_tag_redisplay (GtkTextBTree *tree,
1709 const GtkTextIter *start,
1710 const GtkTextIter *end)
1712 if (_gtk_text_tag_affects_size (tag))
1714 DV (g_print ("invalidating due to size-affecting tag (%s)\n", G_STRLOC));
1715 _gtk_text_btree_invalidate_region (tree, start, end);
1717 else if (_gtk_text_tag_affects_nonsize_appearance (tag))
1719 /* We only need to queue a redraw, not a relayout */
1720 redisplay_region (tree, start, end);
1723 /* We don't need to do anything if the tag doesn't affect display */
1727 _gtk_text_btree_tag (const GtkTextIter *start_orig,
1728 const GtkTextIter *end_orig,
1732 GtkTextLineSegment *seg, *prev;
1733 GtkTextLine *cleanupline;
1734 gboolean toggled_on;
1735 GtkTextLine *start_line;
1736 GtkTextLine *end_line;
1738 GtkTextIter start, end;
1741 GtkTextTagInfo *info;
1743 g_return_if_fail (start_orig != NULL);
1744 g_return_if_fail (end_orig != NULL);
1745 g_return_if_fail (GTK_IS_TEXT_TAG (tag));
1746 g_return_if_fail (_gtk_text_iter_get_btree (start_orig) ==
1747 _gtk_text_iter_get_btree (end_orig));
1748 g_return_if_fail (tag->table == _gtk_text_iter_get_btree (start_orig)->table);
1751 printf ("%s tag %s from %d to %d\n",
1752 add ? "Adding" : "Removing",
1754 gtk_text_buffer_get_offset (start_orig),
1755 gtk_text_buffer_get_offset (end_orig));
1758 if (gtk_text_iter_equal (start_orig, end_orig))
1761 start = *start_orig;
1764 gtk_text_iter_order (&start, &end);
1766 tree = _gtk_text_iter_get_btree (&start);
1768 queue_tag_redisplay (tree, tag, &start, &end);
1770 info = gtk_text_btree_get_tag_info (tree, tag);
1772 start_line = _gtk_text_iter_get_text_line (&start);
1773 end_line = _gtk_text_iter_get_text_line (&end);
1775 /* Find all tag toggles in the region; we are going to delete them.
1776 We need to find them in advance, because
1777 forward_find_tag_toggle () won't work once we start playing around
1779 stack = iter_stack_new ();
1782 /* forward_to_tag_toggle() skips a toggle at the start iterator,
1783 * which is deliberate - we don't want to delete a toggle at the
1786 while (gtk_text_iter_forward_to_tag_toggle (&iter, tag))
1788 if (gtk_text_iter_compare (&iter, &end) >= 0)
1791 iter_stack_push (stack, &iter);
1794 /* We need to traverse the toggles in order. */
1795 iter_stack_invert (stack);
1798 * See whether the tag is present at the start of the range. If
1799 * the state doesn't already match what we want then add a toggle
1803 toggled_on = gtk_text_iter_has_tag (&start, tag);
1804 if ( (add && !toggled_on) ||
1805 (!add && toggled_on) )
1807 /* This could create a second toggle at the start position;
1808 cleanup_line () will remove it if so. */
1809 seg = _gtk_toggle_segment_new (info, add);
1811 prev = gtk_text_line_segment_split (&start);
1814 seg->next = start_line->segments;
1815 start_line->segments = seg;
1819 seg->next = prev->next;
1823 /* cleanup_line adds the new toggle to the node counts. */
1825 printf ("added toggle at start\n");
1827 /* we should probably call segments_changed, but in theory
1828 any still-cached segments in the iters we are about to
1829 use are still valid, since they're in front
1835 * Scan the range of characters and delete any internal tag
1836 * transitions. Keep track of what the old state was at the end
1837 * of the range, and add a toggle there if it's needed.
1841 cleanupline = start_line;
1842 while (iter_stack_pop (stack, &iter))
1844 GtkTextLineSegment *indexable_seg;
1847 line = _gtk_text_iter_get_text_line (&iter);
1848 seg = _gtk_text_iter_get_any_segment (&iter);
1849 indexable_seg = _gtk_text_iter_get_indexable_segment (&iter);
1851 g_assert (seg != NULL);
1852 g_assert (indexable_seg != NULL);
1853 g_assert (seg != indexable_seg);
1855 prev = line->segments;
1857 /* Find the segment that actually toggles this tag. */
1858 while (seg != indexable_seg)
1860 g_assert (seg != NULL);
1861 g_assert (indexable_seg != NULL);
1862 g_assert (seg != indexable_seg);
1864 if ( (seg->type == >k_text_toggle_on_type ||
1865 seg->type == >k_text_toggle_off_type) &&
1866 (seg->body.toggle.info == info) )
1872 g_assert (seg != NULL);
1873 g_assert (indexable_seg != NULL);
1875 g_assert (seg != indexable_seg); /* If this happens, then
1876 forward_to_tag_toggle was
1878 g_assert (seg->body.toggle.info->tag == tag);
1880 /* If this happens, when previously tagging we didn't merge
1881 overlapping tags. */
1882 g_assert ( (toggled_on && seg->type == >k_text_toggle_off_type) ||
1883 (!toggled_on && seg->type == >k_text_toggle_on_type) );
1885 toggled_on = !toggled_on;
1888 printf ("deleting %s toggle\n",
1889 seg->type == >k_text_toggle_on_type ? "on" : "off");
1891 /* Remove toggle segment from the list. */
1894 line->segments = seg->next;
1898 while (prev->next != seg)
1902 prev->next = seg->next;
1905 /* Inform iterators we've hosed them. This actually reflects a
1906 bit of inefficiency; if you have the same tag toggled on and
1907 off a lot in a single line, we keep having the rescan from
1908 the front of the line. Of course we have to do that to get
1909 "prev" anyway, but here we are doing it an additional
1911 segments_changed (tree);
1913 /* Update node counts */
1914 if (seg->body.toggle.inNodeCounts)
1916 _gtk_change_node_toggle_count (line->parent,
1918 seg->body.toggle.inNodeCounts = FALSE;
1923 /* We only clean up lines when we're done with them, saves some
1924 gratuitous line-segment-traversals */
1926 if (cleanupline != line)
1928 cleanup_line (cleanupline);
1933 iter_stack_free (stack);
1935 /* toggled_on now reflects the toggle state _just before_ the
1936 end iterator. The end iterator could already have a toggle
1937 on or a toggle off. */
1938 if ( (add && !toggled_on) ||
1939 (!add && toggled_on) )
1941 /* This could create a second toggle at the start position;
1942 cleanup_line () will remove it if so. */
1944 seg = _gtk_toggle_segment_new (info, !add);
1946 prev = gtk_text_line_segment_split (&end);
1949 seg->next = end_line->segments;
1950 end_line->segments = seg;
1954 seg->next = prev->next;
1957 /* cleanup_line adds the new toggle to the node counts. */
1958 g_assert (seg->body.toggle.inNodeCounts == FALSE);
1960 printf ("added toggle at end\n");
1965 * Cleanup cleanupline and the last line of the range, if
1966 * these are different.
1969 cleanup_line (cleanupline);
1970 if (cleanupline != end_line)
1972 cleanup_line (end_line);
1975 segments_changed (tree);
1977 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1978 _gtk_text_btree_check (tree);
1987 get_line_internal (GtkTextBTree *tree,
1989 gint *real_line_number,
1990 gboolean include_last)
1992 GtkTextBTreeNode *node;
1997 line_count = _gtk_text_btree_line_count (tree);
2001 if (line_number < 0)
2003 line_number = line_count;
2005 else if (line_number > line_count)
2007 line_number = line_count;
2010 if (real_line_number)
2011 *real_line_number = line_number;
2013 node = tree->root_node;
2014 lines_left = line_number;
2017 * Work down through levels of the tree until a GtkTextBTreeNode is found at
2021 while (node->level != 0)
2023 for (node = node->children.node;
2024 node->num_lines <= lines_left;
2030 g_error ("gtk_text_btree_find_line ran out of GtkTextBTreeNodes");
2033 lines_left -= node->num_lines;
2038 * Work through the lines attached to the level-0 GtkTextBTreeNode.
2041 for (line = node->children.line; lines_left > 0;
2047 g_error ("gtk_text_btree_find_line ran out of lines");
2056 _gtk_text_btree_get_end_iter_line (GtkTextBTree *tree)
2059 _gtk_text_btree_get_line (tree,
2060 _gtk_text_btree_line_count (tree) - 1,
2065 _gtk_text_btree_get_line (GtkTextBTree *tree,
2067 gint *real_line_number)
2069 return get_line_internal (tree, line_number, real_line_number, TRUE);
2073 _gtk_text_btree_get_line_no_last (GtkTextBTree *tree,
2075 gint *real_line_number)
2077 return get_line_internal (tree, line_number, real_line_number, FALSE);
2081 _gtk_text_btree_get_line_at_char (GtkTextBTree *tree,
2083 gint *line_start_index,
2084 gint *real_char_index)
2086 GtkTextBTreeNode *node;
2088 GtkTextLineSegment *seg;
2093 node = tree->root_node;
2095 /* Clamp to valid indexes (-1 is magic for "highest index"),
2096 * node->num_chars includes the two newlines that aren't really
2099 if (char_index < 0 || char_index >= (node->num_chars - 1))
2101 char_index = node->num_chars - 2;
2104 *real_char_index = char_index;
2107 * Work down through levels of the tree until a GtkTextBTreeNode is found at
2111 chars_left = char_index;
2112 while (node->level != 0)
2114 for (node = node->children.node;
2115 chars_left >= node->num_chars;
2118 chars_left -= node->num_chars;
2120 g_assert (chars_left >= 0);
2124 if (chars_left == 0)
2126 /* Start of a line */
2128 *line_start_index = char_index;
2129 return node->children.line;
2133 * Work through the lines attached to the level-0 GtkTextBTreeNode.
2139 for (line = node->children.line; line != NULL; line = line->next)
2141 seg = line->segments;
2144 if (chars_in_line + seg->char_count > chars_left)
2145 goto found; /* found our line/segment */
2147 chars_in_line += seg->char_count;
2152 chars_left -= chars_in_line;
2160 g_assert (line != NULL); /* hosage, ran out of lines */
2161 g_assert (seg != NULL);
2163 *line_start_index = char_index - chars_left;
2168 _gtk_text_btree_get_tags (const GtkTextIter *iter,
2171 GtkTextBTreeNode *node;
2172 GtkTextLine *siblingline;
2173 GtkTextLineSegment *seg;
2174 int src, dst, index;
2180 #define NUM_TAG_INFOS 10
2182 line = _gtk_text_iter_get_text_line (iter);
2183 tree = _gtk_text_iter_get_btree (iter);
2184 byte_index = gtk_text_iter_get_line_index (iter);
2186 tagInfo.numTags = 0;
2187 tagInfo.arraySize = NUM_TAG_INFOS;
2188 tagInfo.tags = g_new (GtkTextTag*, NUM_TAG_INFOS);
2189 tagInfo.counts = g_new (int, NUM_TAG_INFOS);
2192 * Record tag toggles within the line of indexPtr but preceding
2193 * indexPtr. Note that if this loop segfaults, your
2194 * byte_index probably points past the sum of all
2195 * seg->byte_count */
2197 for (index = 0, seg = line->segments;
2198 (index + seg->byte_count) <= byte_index;
2199 index += seg->byte_count, seg = seg->next)
2201 if ((seg->type == >k_text_toggle_on_type)
2202 || (seg->type == >k_text_toggle_off_type))
2204 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2209 * Record toggles for tags in lines that are predecessors of
2210 * line but under the same level-0 GtkTextBTreeNode.
2213 for (siblingline = line->parent->children.line;
2214 siblingline != line;
2215 siblingline = siblingline->next)
2217 for (seg = siblingline->segments; seg != NULL;
2220 if ((seg->type == >k_text_toggle_on_type)
2221 || (seg->type == >k_text_toggle_off_type))
2223 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2229 * For each GtkTextBTreeNode in the ancestry of this line, record tag
2230 * toggles for all siblings that precede that GtkTextBTreeNode.
2233 for (node = line->parent; node->parent != NULL;
2234 node = node->parent)
2236 GtkTextBTreeNode *siblingPtr;
2239 for (siblingPtr = node->parent->children.node;
2240 siblingPtr != node; siblingPtr = siblingPtr->next)
2242 for (summary = siblingPtr->summary; summary != NULL;
2243 summary = summary->next)
2245 if (summary->toggle_count & 1)
2247 inc_count (summary->info->tag, summary->toggle_count,
2255 * Go through the tag information and squash out all of the tags
2256 * that have even toggle counts (these tags exist before the point
2257 * of interest, but not at the desired character itself).
2260 for (src = 0, dst = 0; src < tagInfo.numTags; src++)
2262 if (tagInfo.counts[src] & 1)
2264 g_assert (GTK_IS_TEXT_TAG (tagInfo.tags[src]));
2265 tagInfo.tags[dst] = tagInfo.tags[src];
2271 g_free (tagInfo.counts);
2274 g_free (tagInfo.tags);
2277 return tagInfo.tags;
2281 copy_segment (GString *string,
2282 gboolean include_hidden,
2283 gboolean include_nonchars,
2284 const GtkTextIter *start,
2285 const GtkTextIter *end)
2287 GtkTextLineSegment *end_seg;
2288 GtkTextLineSegment *seg;
2290 if (gtk_text_iter_equal (start, end))
2293 seg = _gtk_text_iter_get_indexable_segment (start);
2294 end_seg = _gtk_text_iter_get_indexable_segment (end);
2296 if (seg->type == >k_text_char_type)
2298 gboolean copy = TRUE;
2299 gint copy_bytes = 0;
2300 gint copy_start = 0;
2302 /* Don't copy if we're invisible; segments are invisible/not
2303 as a whole, no need to check each char */
2304 if (!include_hidden &&
2305 _gtk_text_btree_char_is_invisible (start))
2308 /* printf (" <invisible>\n"); */
2311 copy_start = _gtk_text_iter_get_segment_byte (start);
2315 /* End is in the same segment; need to copy fewer bytes. */
2316 gint end_byte = _gtk_text_iter_get_segment_byte (end);
2318 copy_bytes = end_byte - copy_start;
2321 copy_bytes = seg->byte_count - copy_start;
2323 g_assert (copy_bytes != 0); /* Due to iter equality check at
2324 front of this function. */
2328 g_assert ((copy_start + copy_bytes) <= seg->byte_count);
2330 g_string_append_len (string,
2331 seg->body.chars + copy_start,
2335 /* printf (" :%s\n", string->str); */
2337 else if (seg->type == >k_text_pixbuf_type ||
2338 seg->type == >k_text_child_type)
2340 gboolean copy = TRUE;
2342 if (!include_nonchars)
2346 else if (!include_hidden &&
2347 _gtk_text_btree_char_is_invisible (start))
2354 g_string_append_len (string,
2355 gtk_text_unknown_char_utf8,
2363 _gtk_text_btree_get_text (const GtkTextIter *start_orig,
2364 const GtkTextIter *end_orig,
2365 gboolean include_hidden,
2366 gboolean include_nonchars)
2368 GtkTextLineSegment *seg;
2369 GtkTextLineSegment *end_seg;
2377 g_return_val_if_fail (start_orig != NULL, NULL);
2378 g_return_val_if_fail (end_orig != NULL, NULL);
2379 g_return_val_if_fail (_gtk_text_iter_get_btree (start_orig) ==
2380 _gtk_text_iter_get_btree (end_orig), NULL);
2382 start = *start_orig;
2385 gtk_text_iter_order (&start, &end);
2387 retval = g_string_new (NULL);
2389 tree = _gtk_text_iter_get_btree (&start);
2391 end_seg = _gtk_text_iter_get_indexable_segment (&end);
2393 seg = _gtk_text_iter_get_indexable_segment (&iter);
2394 while (seg != end_seg)
2396 copy_segment (retval, include_hidden, include_nonchars,
2399 _gtk_text_iter_forward_indexable_segment (&iter);
2401 seg = _gtk_text_iter_get_indexable_segment (&iter);
2404 copy_segment (retval, include_hidden, include_nonchars, &iter, &end);
2407 g_string_free (retval, FALSE);
2412 _gtk_text_btree_line_count (GtkTextBTree *tree)
2414 /* Subtract bogus line at the end; we return a count
2416 return tree->root_node->num_lines - 1;
2420 _gtk_text_btree_char_count (GtkTextBTree *tree)
2422 /* Exclude newline in bogus last line and the
2423 * one in the last line that is after the end iterator
2425 return tree->root_node->num_chars - 2;
2428 #define LOTSA_TAGS 1000
2430 _gtk_text_btree_char_is_invisible (const GtkTextIter *iter)
2432 gboolean invisible = FALSE; /* if nobody says otherwise, it's visible */
2434 int deftagCnts[LOTSA_TAGS];
2435 int *tagCnts = deftagCnts;
2436 GtkTextTag *deftags[LOTSA_TAGS];
2437 GtkTextTag **tags = deftags;
2439 GtkTextBTreeNode *node;
2440 GtkTextLine *siblingline;
2441 GtkTextLineSegment *seg;
2448 line = _gtk_text_iter_get_text_line (iter);
2449 tree = _gtk_text_iter_get_btree (iter);
2450 byte_index = gtk_text_iter_get_line_index (iter);
2452 numTags = gtk_text_tag_table_get_size (tree->table);
2454 /* almost always avoid malloc, so stay out of system calls */
2455 if (LOTSA_TAGS < numTags)
2457 tagCnts = g_new (int, numTags);
2458 tags = g_new (GtkTextTag*, numTags);
2461 for (i=0; i<numTags; i++)
2467 * Record tag toggles within the line of indexPtr but preceding
2471 for (index = 0, seg = line->segments;
2472 (index + seg->byte_count) <= byte_index; /* segfault here means invalid index */
2473 index += seg->byte_count, seg = seg->next)
2475 if ((seg->type == >k_text_toggle_on_type)
2476 || (seg->type == >k_text_toggle_off_type))
2478 tag = seg->body.toggle.info->tag;
2479 if (tag->invisible_set && tag->values->invisible)
2481 tags[tag->priority] = tag;
2482 tagCnts[tag->priority]++;
2488 * Record toggles for tags in lines that are predecessors of
2489 * line but under the same level-0 GtkTextBTreeNode.
2492 for (siblingline = line->parent->children.line;
2493 siblingline != line;
2494 siblingline = siblingline->next)
2496 for (seg = siblingline->segments; seg != NULL;
2499 if ((seg->type == >k_text_toggle_on_type)
2500 || (seg->type == >k_text_toggle_off_type))
2502 tag = seg->body.toggle.info->tag;
2503 if (tag->invisible_set && tag->values->invisible)
2505 tags[tag->priority] = tag;
2506 tagCnts[tag->priority]++;
2513 * For each GtkTextBTreeNode in the ancestry of this line, record tag toggles
2514 * for all siblings that precede that GtkTextBTreeNode.
2517 for (node = line->parent; node->parent != NULL;
2518 node = node->parent)
2520 GtkTextBTreeNode *siblingPtr;
2523 for (siblingPtr = node->parent->children.node;
2524 siblingPtr != node; siblingPtr = siblingPtr->next)
2526 for (summary = siblingPtr->summary; summary != NULL;
2527 summary = summary->next)
2529 if (summary->toggle_count & 1)
2531 tag = summary->info->tag;
2532 if (tag->invisible_set && tag->values->invisible)
2534 tags[tag->priority] = tag;
2535 tagCnts[tag->priority] += summary->toggle_count;
2543 * Now traverse from highest priority to lowest,
2544 * take invisible value from first odd count (= on)
2547 for (i = numTags-1; i >=0; i--)
2551 /* FIXME not sure this should be if 0 */
2553 #ifndef ALWAYS_SHOW_SELECTION
2554 /* who would make the selection invisible? */
2555 if ((tag == tkxt->seltag)
2556 && !(tkxt->flags & GOT_FOCUS))
2562 invisible = tags[i]->values->invisible;
2567 if (LOTSA_TAGS < numTags)
2582 redisplay_region (GtkTextBTree *tree,
2583 const GtkTextIter *start,
2584 const GtkTextIter *end)
2587 GtkTextLine *start_line, *end_line;
2589 if (gtk_text_iter_compare (start, end) > 0)
2591 const GtkTextIter *tmp = start;
2596 start_line = _gtk_text_iter_get_text_line (start);
2597 end_line = _gtk_text_iter_get_text_line (end);
2600 while (view != NULL)
2602 gint start_y, end_y;
2603 GtkTextLineData *ld;
2605 start_y = _gtk_text_btree_find_line_top (tree, start_line, view->view_id);
2607 if (end_line == start_line)
2610 end_y = _gtk_text_btree_find_line_top (tree, end_line, view->view_id);
2612 ld = _gtk_text_line_get_data (end_line, view->view_id);
2614 end_y += ld->height;
2616 gtk_text_layout_changed (view->layout, start_y,
2625 redisplay_mark (GtkTextLineSegment *mark)
2630 _gtk_text_btree_get_iter_at_mark (mark->body.mark.tree,
2632 mark->body.mark.obj);
2635 gtk_text_iter_forward_char (&end);
2637 DV (g_print ("invalidating due to moving visible mark (%s)\n", G_STRLOC));
2638 _gtk_text_btree_invalidate_region (mark->body.mark.tree,
2643 redisplay_mark_if_visible (GtkTextLineSegment *mark)
2645 if (!mark->body.mark.visible)
2648 redisplay_mark (mark);
2652 ensure_not_off_end (GtkTextBTree *tree,
2653 GtkTextLineSegment *mark,
2656 if (gtk_text_iter_get_line (iter) ==
2657 _gtk_text_btree_line_count (tree))
2658 gtk_text_iter_backward_char (iter);
2661 static GtkTextLineSegment*
2662 real_set_mark (GtkTextBTree *tree,
2663 GtkTextMark *existing_mark,
2665 gboolean left_gravity,
2666 const GtkTextIter *where,
2667 gboolean should_exist,
2668 gboolean redraw_selections)
2670 GtkTextLineSegment *mark;
2673 g_return_val_if_fail (tree != NULL, NULL);
2674 g_return_val_if_fail (where != NULL, NULL);
2675 g_return_val_if_fail (_gtk_text_iter_get_btree (where) == tree, NULL);
2678 mark = existing_mark->segment;
2679 else if (name != NULL)
2680 mark = g_hash_table_lookup (tree->mark_table,
2685 if (should_exist && mark == NULL)
2687 g_warning ("No mark `%s' exists!", name);
2691 /* OK if !should_exist and it does already exist, in that case
2697 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2698 _gtk_text_iter_check (&iter);
2702 if (redraw_selections &&
2703 (mark == tree->insert_mark->segment ||
2704 mark == tree->selection_bound_mark->segment))
2706 GtkTextIter old_pos;
2708 _gtk_text_btree_get_iter_at_mark (tree, &old_pos,
2709 mark->body.mark.obj);
2710 redisplay_region (tree, &old_pos, where);
2714 * don't let visible marks be after the final newline of the
2718 if (mark->body.mark.visible)
2720 ensure_not_off_end (tree, mark, &iter);
2723 /* Redraw the mark's old location. */
2724 redisplay_mark_if_visible (mark);
2726 /* Unlink mark from its current location.
2727 This could hose our iterator... */
2728 gtk_text_btree_unlink_segment (tree, mark,
2729 mark->body.mark.line);
2730 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2731 g_assert (mark->body.mark.line == _gtk_text_iter_get_text_line (&iter));
2733 segments_changed (tree); /* make sure the iterator recomputes its
2738 mark = _gtk_mark_segment_new (tree,
2742 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2744 if (mark->body.mark.name)
2745 g_hash_table_insert (tree->mark_table,
2746 mark->body.mark.name,
2750 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2751 _gtk_text_iter_check (&iter);
2753 /* Link mark into new location */
2754 gtk_text_btree_link_segment (mark, &iter);
2756 /* Invalidate some iterators. */
2757 segments_changed (tree);
2760 * update the screen at the mark's new location.
2763 redisplay_mark_if_visible (mark);
2765 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2766 _gtk_text_iter_check (&iter);
2768 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2769 _gtk_text_btree_check (tree);
2776 _gtk_text_btree_set_mark (GtkTextBTree *tree,
2777 GtkTextMark *existing_mark,
2779 gboolean left_gravity,
2780 const GtkTextIter *iter,
2781 gboolean should_exist)
2783 GtkTextLineSegment *seg;
2785 seg = real_set_mark (tree, existing_mark,
2786 name, left_gravity, iter, should_exist,
2789 return seg ? seg->body.mark.obj : NULL;
2793 _gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2797 GtkTextIter tmp_start, tmp_end;
2799 _gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2801 _gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2802 tree->selection_bound_mark);
2804 if (gtk_text_iter_equal (&tmp_start, &tmp_end))
2816 gtk_text_iter_order (&tmp_start, &tmp_end);
2829 _gtk_text_btree_place_cursor (GtkTextBTree *tree,
2830 const GtkTextIter *iter)
2832 _gtk_text_btree_select_range (tree, iter, iter);
2836 _gtk_text_btree_select_range (GtkTextBTree *tree,
2837 const GtkTextIter *ins,
2838 const GtkTextIter *bound)
2840 GtkTextIter start, end;
2842 if (_gtk_text_btree_get_selection_bounds (tree, &start, &end))
2843 redisplay_region (tree, &start, &end);
2845 /* Move insert AND selection_bound before we redisplay */
2846 real_set_mark (tree, tree->insert_mark,
2847 "insert", FALSE, ins, TRUE, FALSE);
2848 real_set_mark (tree, tree->selection_bound_mark,
2849 "selection_bound", FALSE, bound, TRUE, FALSE);
2854 _gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2859 g_return_if_fail (tree != NULL);
2860 g_return_if_fail (name != NULL);
2862 mark = g_hash_table_lookup (tree->mark_table,
2865 _gtk_text_btree_remove_mark (tree, mark);
2869 _gtk_text_btree_release_mark_segment (GtkTextBTree *tree,
2870 GtkTextLineSegment *segment)
2873 if (segment->body.mark.name)
2874 g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2876 segment->body.mark.tree = NULL;
2877 segment->body.mark.line = NULL;
2879 /* Remove the ref on the mark, which frees segment as a side effect
2880 * if this is the last reference.
2882 g_object_unref (segment->body.mark.obj);
2886 _gtk_text_btree_remove_mark (GtkTextBTree *tree,
2889 GtkTextLineSegment *segment;
2891 g_return_if_fail (mark != NULL);
2892 g_return_if_fail (tree != NULL);
2894 segment = mark->segment;
2896 if (segment->body.mark.not_deleteable)
2898 g_warning ("Can't delete special mark `%s'", segment->body.mark.name);
2902 /* This calls cleanup_line and segments_changed */
2903 gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2905 _gtk_text_btree_release_mark_segment (tree, segment);
2909 _gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2910 GtkTextMark *segment)
2912 return segment == tree->insert_mark;
2916 _gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2917 GtkTextMark *segment)
2919 return segment == tree->selection_bound_mark;
2923 _gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2926 GtkTextLineSegment *seg;
2928 g_return_val_if_fail (tree != NULL, NULL);
2929 g_return_val_if_fail (name != NULL, NULL);
2931 seg = g_hash_table_lookup (tree->mark_table, name);
2933 return seg ? seg->body.mark.obj : NULL;
2937 * gtk_text_mark_set_visible:
2938 * @mark: a #GtkTextMark
2939 * @setting: visibility of mark
2941 * Sets the visibility of @mark; the insertion point is normally
2942 * visible, i.e. you can see it as a vertical bar. Also, the text
2943 * widget uses a visible mark to indicate where a drop will occur when
2944 * dragging-and-dropping text. Most other marks are not visible.
2945 * Marks are not visible by default.
2949 gtk_text_mark_set_visible (GtkTextMark *mark,
2952 GtkTextLineSegment *seg;
2954 g_return_if_fail (mark != NULL);
2956 seg = mark->segment;
2958 if (seg->body.mark.visible == setting)
2962 seg->body.mark.visible = setting;
2964 redisplay_mark (seg);
2969 _gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
2972 GtkTextBTreeNode *node;
2973 GtkTextTagInfo *info;
2975 g_return_val_if_fail (tree != NULL, NULL);
2979 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2984 if (info->tag_root == NULL)
2987 node = info->tag_root;
2989 /* We know the tag root has instances of the given
2992 continue_outer_loop:
2993 g_assert (node != NULL);
2994 while (node->level > 0)
2996 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2997 node = node->children.node;
2998 while (node != NULL)
3000 if (gtk_text_btree_node_has_tag (node, tag))
3001 goto continue_outer_loop;
3005 g_assert (node != NULL);
3008 g_assert (node != NULL); /* The tag summaries said some node had
3011 g_assert (node->level == 0);
3013 return node->children.line;
3017 /* Looking for any tag at all (tag == NULL).
3018 Unfortunately this can't be done in a simple and efficient way
3019 right now; so I'm just going to return the
3020 first line in the btree. FIXME */
3021 return _gtk_text_btree_get_line (tree, 0, NULL);
3026 _gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
3029 GtkTextBTreeNode *node;
3030 GtkTextBTreeNode *last_node;
3032 GtkTextTagInfo *info;
3034 g_return_val_if_fail (tree != NULL, NULL);
3038 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3040 if (info->tag_root == NULL)
3043 node = info->tag_root;
3044 /* We know the tag root has instances of the given
3047 while (node->level > 0)
3049 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
3051 node = node->children.node;
3052 while (node != NULL)
3054 if (gtk_text_btree_node_has_tag (node, tag))
3062 g_assert (node != NULL); /* The tag summaries said some node had
3065 g_assert (node->level == 0);
3067 /* Find the last line in this node */
3068 line = node->children.line;
3069 while (line->next != NULL)
3076 /* This search can't be done efficiently at the moment,
3077 at least not without complexity.
3078 So, we just return the last line.
3080 return _gtk_text_btree_get_end_iter_line (tree);
3090 _gtk_text_line_get_number (GtkTextLine *line)
3093 GtkTextBTreeNode *node, *parent, *node2;
3097 * First count how many lines precede this one in its level-0
3101 node = line->parent;
3103 for (line2 = node->children.line; line2 != line;
3104 line2 = line2->next)
3108 g_error ("gtk_text_btree_line_number couldn't find line");
3114 * Now work up through the levels of the tree one at a time,
3115 * counting how many lines are in GtkTextBTreeNodes preceding the current
3119 for (parent = node->parent ; parent != NULL;
3120 node = parent, parent = parent->parent)
3122 for (node2 = parent->children.node; node2 != node;
3123 node2 = node2->next)
3127 g_error ("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
3129 index += node2->num_lines;
3135 static GtkTextLineSegment*
3136 find_toggle_segment_before_char (GtkTextLine *line,
3140 GtkTextLineSegment *seg;
3141 GtkTextLineSegment *toggle_seg;
3146 seg = line->segments;
3147 while ( (index + seg->char_count) <= char_in_line )
3149 if (((seg->type == >k_text_toggle_on_type)
3150 || (seg->type == >k_text_toggle_off_type))
3151 && (seg->body.toggle.info->tag == tag))
3154 index += seg->char_count;
3161 static GtkTextLineSegment*
3162 find_toggle_segment_before_byte (GtkTextLine *line,
3166 GtkTextLineSegment *seg;
3167 GtkTextLineSegment *toggle_seg;
3172 seg = line->segments;
3173 while ( (index + seg->byte_count) <= byte_in_line )
3175 if (((seg->type == >k_text_toggle_on_type)
3176 || (seg->type == >k_text_toggle_off_type))
3177 && (seg->body.toggle.info->tag == tag))
3180 index += seg->byte_count;
3188 find_toggle_outside_current_line (GtkTextLine *line,
3192 GtkTextBTreeNode *node;
3193 GtkTextLine *sibling_line;
3194 GtkTextLineSegment *seg;
3195 GtkTextLineSegment *toggle_seg;
3197 GtkTextTagInfo *info = NULL;
3200 * No toggle in this line. Look for toggles for the tag in lines
3201 * that are predecessors of line but under the same
3202 * level-0 GtkTextBTreeNode.
3205 sibling_line = line->parent->children.line;
3206 while (sibling_line != line)
3208 seg = sibling_line->segments;
3211 if (((seg->type == >k_text_toggle_on_type)
3212 || (seg->type == >k_text_toggle_off_type))
3213 && (seg->body.toggle.info->tag == tag))
3219 sibling_line = sibling_line->next;
3222 if (toggle_seg != NULL)
3223 return (toggle_seg->type == >k_text_toggle_on_type);
3226 * No toggle in this GtkTextBTreeNode. Scan upwards through the ancestors of
3227 * this GtkTextBTreeNode, counting the number of toggles of the given tag in
3228 * siblings that precede that GtkTextBTreeNode.
3231 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3237 node = line->parent;
3238 while (node->parent != NULL)
3240 GtkTextBTreeNode *sibling_node;
3242 sibling_node = node->parent->children.node;
3243 while (sibling_node != node)
3247 summary = sibling_node->summary;
3248 while (summary != NULL)
3250 if (summary->info == info)
3251 toggles += summary->toggle_count;
3253 summary = summary->next;
3256 sibling_node = sibling_node->next;
3259 if (node == info->tag_root)
3262 node = node->parent;
3266 * An odd number of toggles means that the tag is present at the
3270 return (toggles & 1) != 0;
3273 /* FIXME this function is far too slow, for no good reason. */
3275 _gtk_text_line_char_has_tag (GtkTextLine *line,
3280 GtkTextLineSegment *toggle_seg;
3282 g_return_val_if_fail (line != NULL, FALSE);
3285 * Check for toggles for the tag in the line but before
3286 * the char. If there is one, its type indicates whether or
3287 * not the character is tagged.
3290 toggle_seg = find_toggle_segment_before_char (line, char_in_line, tag);
3292 if (toggle_seg != NULL)
3293 return (toggle_seg->type == >k_text_toggle_on_type);
3295 return find_toggle_outside_current_line (line, tree, tag);
3299 _gtk_text_line_byte_has_tag (GtkTextLine *line,
3304 GtkTextLineSegment *toggle_seg;
3306 g_return_val_if_fail (line != NULL, FALSE);
3309 * Check for toggles for the tag in the line but before
3310 * the char. If there is one, its type indicates whether or
3311 * not the character is tagged.
3314 toggle_seg = find_toggle_segment_before_byte (line, byte_in_line, tag);
3316 if (toggle_seg != NULL)
3317 return (toggle_seg->type == >k_text_toggle_on_type);
3319 return find_toggle_outside_current_line (line, tree, tag);
3323 _gtk_text_line_is_last (GtkTextLine *line,
3326 return line == get_last_line (tree);
3330 ensure_end_iter_line (GtkTextBTree *tree)
3332 if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
3337 /* n_lines is without the magic line at the end */
3338 n_lines = _gtk_text_btree_line_count (tree);
3340 g_assert (n_lines >= 1);
3342 tree->end_iter_line = _gtk_text_btree_get_line_no_last (tree, -1, &real_line);
3344 tree->end_iter_line_stamp = tree->chars_changed_stamp;
3349 ensure_end_iter_segment (GtkTextBTree *tree)
3351 if (tree->end_iter_segment_stamp != tree->segments_changed_stamp)
3353 GtkTextLineSegment *seg;
3354 GtkTextLineSegment *last_with_chars;
3356 ensure_end_iter_line (tree);
3358 last_with_chars = NULL;
3360 seg = tree->end_iter_line->segments;
3363 if (seg->char_count > 0)
3364 last_with_chars = seg;
3368 tree->end_iter_segment = last_with_chars;
3370 /* We know the last char in the last line is '\n' */
3371 tree->end_iter_segment_byte_index = last_with_chars->byte_count - 1;
3372 tree->end_iter_segment_char_offset = last_with_chars->char_count - 1;
3374 tree->end_iter_segment_stamp = tree->segments_changed_stamp;
3376 g_assert (tree->end_iter_segment->type == >k_text_char_type);
3377 g_assert (tree->end_iter_segment->body.chars[tree->end_iter_segment_byte_index] == '\n');
3382 _gtk_text_line_contains_end_iter (GtkTextLine *line,
3385 ensure_end_iter_line (tree);
3387 return line == tree->end_iter_line;
3391 _gtk_text_btree_is_end (GtkTextBTree *tree,
3393 GtkTextLineSegment *seg,
3397 g_return_val_if_fail (byte_index >= 0 || char_offset >= 0, FALSE);
3399 /* Do this first to avoid walking segments in most cases */
3400 if (!_gtk_text_line_contains_end_iter (line, tree))
3403 ensure_end_iter_segment (tree);
3405 if (seg != tree->end_iter_segment)
3408 if (byte_index >= 0)
3409 return byte_index == tree->end_iter_segment_byte_index;
3411 return char_offset == tree->end_iter_segment_char_offset;
3415 _gtk_text_line_next (GtkTextLine *line)
3417 GtkTextBTreeNode *node;
3419 if (line->next != NULL)
3424 * This was the last line associated with the particular parent
3425 * GtkTextBTreeNode. Search up the tree for the next GtkTextBTreeNode,
3426 * then search down from that GtkTextBTreeNode to find the first
3430 node = line->parent;
3431 while (node != NULL && node->next == NULL)
3432 node = node->parent;
3438 while (node->level > 0)
3440 node = node->children.node;
3443 g_assert (node->children.line != line);
3445 return node->children.line;
3450 _gtk_text_line_next_excluding_last (GtkTextLine *line)
3454 next = _gtk_text_line_next (line);
3456 /* If we were on the end iter line, we can't go to
3459 if (next && next->next == NULL && /* these checks are optimization only */
3460 _gtk_text_line_next (next) == NULL)
3467 _gtk_text_line_previous (GtkTextLine *line)
3469 GtkTextBTreeNode *node;
3470 GtkTextBTreeNode *node2;
3474 * Find the line under this GtkTextBTreeNode just before the starting line.
3476 prev = line->parent->children.line; /* First line at leaf */
3477 while (prev != line)
3479 if (prev->next == line)
3485 g_error ("gtk_text_btree_previous_line ran out of lines");
3489 * This was the first line associated with the particular parent
3490 * GtkTextBTreeNode. Search up the tree for the previous GtkTextBTreeNode,
3491 * then search down from that GtkTextBTreeNode to find its last line.
3493 for (node = line->parent; ; node = node->parent)
3495 if (node == NULL || node->parent == NULL)
3497 else if (node != node->parent->children.node)
3501 for (node2 = node->parent->children.node; ;
3502 node2 = node2->children.node)
3504 while (node2->next != node)
3505 node2 = node2->next;
3507 if (node2->level == 0)
3513 for (prev = node2->children.line ; ; prev = prev->next)
3515 if (prev->next == NULL)
3519 g_assert_not_reached ();
3525 _gtk_text_line_data_new (GtkTextLayout *layout,
3528 GtkTextLineData *line_data;
3530 line_data = g_new (GtkTextLineData, 1);
3532 line_data->view_id = layout;
3533 line_data->next = NULL;
3534 line_data->width = 0;
3535 line_data->height = 0;
3536 line_data->valid = FALSE;
3542 _gtk_text_line_add_data (GtkTextLine *line,
3543 GtkTextLineData *data)
3545 g_return_if_fail (line != NULL);
3546 g_return_if_fail (data != NULL);
3547 g_return_if_fail (data->view_id != NULL);
3551 data->next = line->views;
3561 _gtk_text_line_remove_data (GtkTextLine *line,
3564 GtkTextLineData *prev;
3565 GtkTextLineData *iter;
3567 g_return_val_if_fail (line != NULL, NULL);
3568 g_return_val_if_fail (view_id != NULL, NULL);
3572 while (iter != NULL)
3574 if (iter->view_id == view_id)
3583 prev->next = iter->next;
3585 line->views = iter->next;
3594 _gtk_text_line_get_data (GtkTextLine *line,
3597 GtkTextLineData *iter;
3599 g_return_val_if_fail (line != NULL, NULL);
3600 g_return_val_if_fail (view_id != NULL, NULL);
3603 while (iter != NULL)
3605 if (iter->view_id == view_id)
3614 _gtk_text_line_invalidate_wrap (GtkTextLine *line,
3615 GtkTextLineData *ld)
3617 /* For now this is totally unoptimized. FIXME?
3619 We could probably optimize the case where the width removed
3620 is less than the max width for the parent node,
3621 and the case where the height is unchanged when we re-wrap.
3624 g_return_if_fail (ld != NULL);
3627 gtk_text_btree_node_invalidate_upward (line->parent, ld->view_id);
3631 _gtk_text_line_char_count (GtkTextLine *line)
3633 GtkTextLineSegment *seg;
3637 seg = line->segments;
3640 size += seg->char_count;
3647 _gtk_text_line_byte_count (GtkTextLine *line)
3649 GtkTextLineSegment *seg;
3653 seg = line->segments;
3656 size += seg->byte_count;
3664 _gtk_text_line_char_index (GtkTextLine *target_line)
3666 GSList *node_stack = NULL;
3667 GtkTextBTreeNode *iter;
3671 /* Push all our parent nodes onto a stack */
3672 iter = target_line->parent;
3674 g_assert (iter != NULL);
3676 while (iter != NULL)
3678 node_stack = g_slist_prepend (node_stack, iter);
3680 iter = iter->parent;
3683 /* Check that we have the root node on top of the stack. */
3684 g_assert (node_stack != NULL &&
3685 node_stack->data != NULL &&
3686 ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3688 /* Add up chars in all nodes before the nodes in our stack.
3692 iter = node_stack->data;
3693 while (iter != NULL)
3695 GtkTextBTreeNode *child_iter;
3696 GtkTextBTreeNode *next_node;
3698 next_node = node_stack->next ?
3699 node_stack->next->data : NULL;
3700 node_stack = g_slist_remove (node_stack, node_stack->data);
3702 if (iter->level == 0)
3704 /* stack should be empty when we're on the last node */
3705 g_assert (node_stack == NULL);
3706 break; /* Our children are now lines */
3709 g_assert (next_node != NULL);
3710 g_assert (iter != NULL);
3711 g_assert (next_node->parent == iter);
3713 /* Add up chars before us in the tree */
3714 child_iter = iter->children.node;
3715 while (child_iter != next_node)
3717 g_assert (child_iter != NULL);
3719 num_chars += child_iter->num_chars;
3721 child_iter = child_iter->next;
3727 g_assert (iter != NULL);
3728 g_assert (iter == target_line->parent);
3730 /* Since we don't store char counts in lines, only in segments, we
3731 have to iterate over the lines adding up segment char counts
3732 until we find our line. */
3733 line = iter->children.line;
3734 while (line != target_line)
3736 g_assert (line != NULL);
3738 num_chars += _gtk_text_line_char_count (line);
3743 g_assert (line == target_line);
3749 _gtk_text_line_byte_to_segment (GtkTextLine *line,
3753 GtkTextLineSegment *seg;
3756 g_return_val_if_fail (line != NULL, NULL);
3758 offset = byte_offset;
3759 seg = line->segments;
3761 while (offset >= seg->byte_count)
3763 g_assert (seg != NULL); /* means an invalid byte index */
3764 offset -= seg->byte_count;
3769 *seg_offset = offset;
3775 _gtk_text_line_char_to_segment (GtkTextLine *line,
3779 GtkTextLineSegment *seg;
3782 g_return_val_if_fail (line != NULL, NULL);
3784 offset = char_offset;
3785 seg = line->segments;
3787 while (offset >= seg->char_count)
3789 g_assert (seg != NULL); /* means an invalid char index */
3790 offset -= seg->char_count;
3795 *seg_offset = offset;
3801 _gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3805 GtkTextLineSegment *seg;
3808 g_return_val_if_fail (line != NULL, NULL);
3810 offset = byte_offset;
3811 seg = line->segments;
3813 while (offset > 0 && offset >= seg->byte_count)
3815 g_assert (seg != NULL); /* means an invalid byte index */
3816 offset -= seg->byte_count;
3821 *seg_offset = offset;
3827 _gtk_text_line_char_to_any_segment (GtkTextLine *line,
3831 GtkTextLineSegment *seg;
3834 g_return_val_if_fail (line != NULL, NULL);
3836 offset = char_offset;
3837 seg = line->segments;
3839 while (offset > 0 && offset >= seg->char_count)
3841 g_assert (seg != NULL); /* means an invalid byte index */
3842 offset -= seg->char_count;
3847 *seg_offset = offset;
3853 _gtk_text_line_byte_to_char (GtkTextLine *line,
3857 GtkTextLineSegment *seg;
3859 g_return_val_if_fail (line != NULL, 0);
3860 g_return_val_if_fail (byte_offset >= 0, 0);
3863 seg = line->segments;
3864 while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3865 the next segment) */
3867 g_assert (seg != NULL); /* our byte_index was bogus if this happens */
3869 byte_offset -= seg->byte_count;
3870 char_offset += seg->char_count;
3875 g_assert (seg != NULL);
3877 /* Now byte_offset is the offset into the current segment,
3878 and char_offset is the start of the current segment.
3879 Optimize the case where no chars use > 1 byte */
3880 if (seg->byte_count == seg->char_count)
3881 return char_offset + byte_offset;
3884 if (seg->type == >k_text_char_type)
3885 return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3888 g_assert (seg->char_count == 1);
3889 g_assert (byte_offset == 0);
3897 _gtk_text_line_char_to_byte (GtkTextLine *line,
3900 g_warning ("FIXME not implemented");
3905 /* FIXME sync with char_locate (or figure out a clean
3906 way to merge the two functions) */
3908 _gtk_text_line_byte_locate (GtkTextLine *line,
3910 GtkTextLineSegment **segment,
3911 GtkTextLineSegment **any_segment,
3912 gint *seg_byte_offset,
3913 gint *line_byte_offset)
3915 GtkTextLineSegment *seg;
3916 GtkTextLineSegment *after_prev_indexable;
3917 GtkTextLineSegment *after_last_indexable;
3918 GtkTextLineSegment *last_indexable;
3922 g_return_val_if_fail (line != NULL, FALSE);
3923 g_return_val_if_fail (byte_offset >= 0, FALSE);
3926 *any_segment = NULL;
3929 offset = byte_offset;
3931 last_indexable = NULL;
3932 after_last_indexable = line->segments;
3933 after_prev_indexable = line->segments;
3934 seg = line->segments;
3936 /* The loop ends when we're inside a segment;
3937 last_indexable refers to the last segment
3938 we passed entirely. */
3939 while (seg && offset >= seg->byte_count)
3941 if (seg->char_count > 0)
3943 offset -= seg->byte_count;
3944 bytes_in_line += seg->byte_count;
3945 last_indexable = seg;
3946 after_prev_indexable = after_last_indexable;
3947 after_last_indexable = last_indexable->next;
3955 /* We went off the end of the line */
3957 g_warning ("%s: byte index off the end of the line", G_STRLOC);
3964 if (after_last_indexable != NULL)
3965 *any_segment = after_last_indexable;
3967 *any_segment = *segment;
3970 /* Override any_segment if we're in the middle of a segment. */
3972 *any_segment = *segment;
3974 *seg_byte_offset = offset;
3976 g_assert (*segment != NULL);
3977 g_assert (*any_segment != NULL);
3978 g_assert (*seg_byte_offset < (*segment)->byte_count);
3980 *line_byte_offset = bytes_in_line + *seg_byte_offset;
3985 /* FIXME sync with byte_locate (or figure out a clean
3986 way to merge the two functions) */
3988 _gtk_text_line_char_locate (GtkTextLine *line,
3990 GtkTextLineSegment **segment,
3991 GtkTextLineSegment **any_segment,
3992 gint *seg_char_offset,
3993 gint *line_char_offset)
3995 GtkTextLineSegment *seg;
3996 GtkTextLineSegment *after_prev_indexable;
3997 GtkTextLineSegment *after_last_indexable;
3998 GtkTextLineSegment *last_indexable;
4002 g_return_val_if_fail (line != NULL, FALSE);
4003 g_return_val_if_fail (char_offset >= 0, FALSE);
4006 *any_segment = NULL;
4009 offset = char_offset;
4011 last_indexable = NULL;
4012 after_last_indexable = line->segments;
4013 after_prev_indexable = line->segments;
4014 seg = line->segments;
4016 /* The loop ends when we're inside a segment;
4017 last_indexable refers to the last segment
4018 we passed entirely. */
4019 while (seg && offset >= seg->char_count)
4021 if (seg->char_count > 0)
4023 offset -= seg->char_count;
4024 chars_in_line += seg->char_count;
4025 last_indexable = seg;
4026 after_prev_indexable = after_last_indexable;
4027 after_last_indexable = last_indexable->next;
4035 /* end of the line */
4037 g_warning ("%s: char offset off the end of the line", G_STRLOC);
4044 if (after_last_indexable != NULL)
4045 *any_segment = after_last_indexable;
4047 *any_segment = *segment;
4050 /* Override any_segment if we're in the middle of a segment. */
4052 *any_segment = *segment;
4054 *seg_char_offset = offset;
4056 g_assert (*segment != NULL);
4057 g_assert (*any_segment != NULL);
4058 g_assert (*seg_char_offset < (*segment)->char_count);
4060 *line_char_offset = chars_in_line + *seg_char_offset;
4066 _gtk_text_line_byte_to_char_offsets (GtkTextLine *line,
4068 gint *line_char_offset,
4069 gint *seg_char_offset)
4071 GtkTextLineSegment *seg;
4074 g_return_if_fail (line != NULL);
4075 g_return_if_fail (byte_offset >= 0);
4077 *line_char_offset = 0;
4079 offset = byte_offset;
4080 seg = line->segments;
4082 while (offset >= seg->byte_count)
4084 offset -= seg->byte_count;
4085 *line_char_offset += seg->char_count;
4087 g_assert (seg != NULL); /* means an invalid char offset */
4090 g_assert (seg->char_count > 0); /* indexable. */
4092 /* offset is now the number of bytes into the current segment we
4093 * want to go. Count chars into the current segment.
4096 if (seg->type == >k_text_char_type)
4098 *seg_char_offset = g_utf8_strlen (seg->body.chars, offset);
4100 g_assert (*seg_char_offset < seg->char_count);
4102 *line_char_offset += *seg_char_offset;
4106 g_assert (offset == 0);
4107 *seg_char_offset = 0;
4112 _gtk_text_line_char_to_byte_offsets (GtkTextLine *line,
4114 gint *line_byte_offset,
4115 gint *seg_byte_offset)
4117 GtkTextLineSegment *seg;
4120 g_return_if_fail (line != NULL);
4121 g_return_if_fail (char_offset >= 0);
4123 *line_byte_offset = 0;
4125 offset = char_offset;
4126 seg = line->segments;
4128 while (offset >= seg->char_count)
4130 offset -= seg->char_count;
4131 *line_byte_offset += seg->byte_count;
4133 g_assert (seg != NULL); /* means an invalid char offset */
4136 g_assert (seg->char_count > 0); /* indexable. */
4138 /* offset is now the number of chars into the current segment we
4139 want to go. Count bytes into the current segment. */
4141 if (seg->type == >k_text_char_type)
4143 *seg_byte_offset = 0;
4147 const char * start = seg->body.chars + *seg_byte_offset;
4149 bytes = g_utf8_next_char (start) - start;
4150 *seg_byte_offset += bytes;
4154 g_assert (*seg_byte_offset < seg->byte_count);
4156 *line_byte_offset += *seg_byte_offset;
4160 g_assert (offset == 0);
4161 *seg_byte_offset = 0;
4166 node_compare (GtkTextBTreeNode *lhs,
4167 GtkTextBTreeNode *rhs)
4169 GtkTextBTreeNode *iter;
4170 GtkTextBTreeNode *node;
4171 GtkTextBTreeNode *common_parent;
4172 GtkTextBTreeNode *parent_of_lower;
4173 GtkTextBTreeNode *parent_of_higher;
4174 gboolean lhs_is_lower;
4175 GtkTextBTreeNode *lower;
4176 GtkTextBTreeNode *higher;
4178 /* This function assumes that lhs and rhs are not underneath each
4185 if (lhs->level < rhs->level)
4187 lhs_is_lower = TRUE;
4193 lhs_is_lower = FALSE;
4198 /* Algorithm: find common parent of lhs/rhs. Save the child nodes
4199 * of the common parent we used to reach the common parent; the
4200 * ordering of these child nodes in the child list is the ordering
4204 /* Get on the same level (may be on same level already) */
4206 while (node->level < higher->level)
4207 node = node->parent;
4209 g_assert (node->level == higher->level);
4211 g_assert (node != higher); /* Happens if lower is underneath higher */
4213 /* Go up until we have two children with a common parent.
4215 parent_of_lower = node;
4216 parent_of_higher = higher;
4218 while (parent_of_lower->parent != parent_of_higher->parent)
4220 parent_of_lower = parent_of_lower->parent;
4221 parent_of_higher = parent_of_higher->parent;
4224 g_assert (parent_of_lower->parent == parent_of_higher->parent);
4226 common_parent = parent_of_lower->parent;
4228 g_assert (common_parent != NULL);
4230 /* See which is first in the list of common_parent's children */
4231 iter = common_parent->children.node;
4232 while (iter != NULL)
4234 if (iter == parent_of_higher)
4236 /* higher is less than lower */
4239 return 1; /* lhs > rhs */
4243 else if (iter == parent_of_lower)
4245 /* lower is less than higher */
4248 return -1; /* lhs < rhs */
4256 g_assert_not_reached ();
4260 /* remember that tag == NULL means "any tag" */
4262 _gtk_text_line_next_could_contain_tag (GtkTextLine *line,
4266 GtkTextBTreeNode *node;
4267 GtkTextTagInfo *info;
4268 gboolean below_tag_root;
4270 g_return_val_if_fail (line != NULL, NULL);
4272 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4273 _gtk_text_btree_check (tree);
4277 /* Right now we can only offer linear-search if the user wants
4278 * to know about any tag toggle at all.
4280 return _gtk_text_line_next_excluding_last (line);
4283 /* Our tag summaries only have node precision, not line
4284 * precision. This means that if any line under a node could contain a
4285 * tag, then any of the others could also contain a tag.
4287 * In the future we could have some mechanism to keep track of how
4288 * many toggles we've found under a node so far, since we have a
4289 * count of toggles under the node. But for now I'm going with KISS.
4292 /* return same-node line, if any. */
4296 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4300 if (info->tag_root == NULL)
4303 if (info->tag_root == line->parent)
4304 return NULL; /* we were at the last line under the tag root */
4306 /* We need to go up out of this node, and on to the next one with
4307 toggles for the target tag. If we're below the tag root, we need to
4308 find the next node below the tag root that has tag summaries. If
4309 we're not below the tag root, we need to see if the tag root is
4310 after us in the tree, and if so, return the first line underneath
4313 node = line->parent;
4314 below_tag_root = FALSE;
4315 while (node != NULL)
4317 if (node == info->tag_root)
4319 below_tag_root = TRUE;
4323 node = node->parent;
4328 node = line->parent;
4329 while (node != info->tag_root)
4331 if (node->next == NULL)
4332 node = node->parent;
4337 if (gtk_text_btree_node_has_tag (node, tag))
4347 ordering = node_compare (line->parent, info->tag_root);
4351 /* Tag root is ahead of us, so search there. */
4352 node = info->tag_root;
4357 /* Tag root is after us, so no more lines that
4358 * could contain the tag.
4363 g_assert_not_reached ();
4368 g_assert (node != NULL);
4370 /* We have to find the first sub-node of this node that contains
4374 while (node->level > 0)
4376 g_assert (node != NULL); /* If this fails, it likely means an
4377 incorrect tag summary led us on a
4378 wild goose chase down this branch of
4380 node = node->children.node;
4381 while (node != NULL)
4383 if (gtk_text_btree_node_has_tag (node, tag))
4389 g_assert (node != NULL);
4390 g_assert (node->level == 0);
4392 return node->children.line;
4396 prev_line_under_node (GtkTextBTreeNode *node,
4401 prev = node->children.line;
4407 while (prev->next != line)
4417 _gtk_text_line_previous_could_contain_tag (GtkTextLine *line,
4421 GtkTextBTreeNode *node;
4422 GtkTextBTreeNode *found_node = NULL;
4423 GtkTextTagInfo *info;
4424 gboolean below_tag_root;
4426 GtkTextBTreeNode *line_ancestor;
4427 GtkTextBTreeNode *line_ancestor_parent;
4429 /* See next_could_contain_tag () for more extensive comments
4430 * on what's going on here.
4433 g_return_val_if_fail (line != NULL, NULL);
4435 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4436 _gtk_text_btree_check (tree);
4440 /* Right now we can only offer linear-search if the user wants
4441 * to know about any tag toggle at all.
4443 return _gtk_text_line_previous (line);
4446 /* Return same-node line, if any. */
4447 prev = prev_line_under_node (line->parent, line);
4451 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4455 if (info->tag_root == NULL)
4458 if (info->tag_root == line->parent)
4459 return NULL; /* we were at the first line under the tag root */
4461 /* Are we below the tag root */
4462 node = line->parent;
4463 below_tag_root = FALSE;
4464 while (node != NULL)
4466 if (node == info->tag_root)
4468 below_tag_root = TRUE;
4472 node = node->parent;
4477 /* Look for a previous node under this tag root that has our
4481 /* this assertion holds because line->parent is not the
4482 * tag root, we are below the tag root, and the tag
4485 g_assert (line->parent->parent != NULL);
4487 line_ancestor = line->parent;
4488 line_ancestor_parent = line->parent->parent;
4490 node = line_ancestor_parent->children.node;
4491 while (node != line_ancestor || line_ancestor != info->tag_root)
4493 GSList *child_nodes = NULL;
4496 /* Create reverse-order list of nodes before
4499 while (node != line_ancestor && node != NULL)
4501 child_nodes = g_slist_prepend (child_nodes, node);
4506 /* Try to find a node with our tag on it in the list */
4510 GtkTextBTreeNode *this_node = tmp->data;
4512 g_assert (this_node != line_ancestor);
4514 if (gtk_text_btree_node_has_tag (this_node, tag))
4516 found_node = this_node;
4517 g_slist_free (child_nodes);
4521 tmp = g_slist_next (tmp);
4524 g_slist_free (child_nodes);
4526 /* Didn't find anything on this level; go up one level. */
4527 line_ancestor = line_ancestor_parent;
4528 line_ancestor_parent = line_ancestor->parent;
4530 if (line_ancestor_parent != NULL)
4532 node = line_ancestor_parent->children.node;
4543 ordering = node_compare (line->parent, info->tag_root);
4547 /* Tag root is ahead of us, so no more lines
4554 /* Tag root is after us, so grab last tagged
4555 * line underneath the tag root.
4557 found_node = info->tag_root;
4561 g_assert_not_reached ();
4566 g_assert (found_node != NULL);
4568 /* We have to find the last sub-node of this node that contains
4573 while (node->level > 0)
4575 GSList *child_nodes = NULL;
4577 g_assert (node != NULL); /* If this fails, it likely means an
4578 incorrect tag summary led us on a
4579 wild goose chase down this branch of
4582 node = node->children.node;
4583 while (node != NULL)
4585 child_nodes = g_slist_prepend (child_nodes, node);
4589 node = NULL; /* detect failure to find a child node. */
4592 while (iter != NULL)
4594 if (gtk_text_btree_node_has_tag (iter->data, tag))
4596 /* recurse into this node. */
4601 iter = g_slist_next (iter);
4604 g_slist_free (child_nodes);
4606 g_assert (node != NULL);
4609 g_assert (node != NULL);
4610 g_assert (node->level == 0);
4612 /* this assertion is correct, but slow. */
4613 /* g_assert (node_compare (node, line->parent) < 0); */
4615 /* Return last line in this node. */
4617 prev = node->children.line;
4625 * Non-public function implementations
4629 summary_list_destroy (Summary *summary)
4632 while (summary != NULL)
4634 next = summary->next;
4635 summary_destroy (summary);
4641 get_last_line (GtkTextBTree *tree)
4643 if (tree->last_line_stamp != tree->chars_changed_stamp)
4649 n_lines = _gtk_text_btree_line_count (tree);
4651 g_assert (n_lines >= 1); /* num_lines doesn't return bogus last line. */
4653 line = _gtk_text_btree_get_line (tree, n_lines, &real_line);
4655 tree->last_line_stamp = tree->chars_changed_stamp;
4656 tree->last_line = line;
4659 return tree->last_line;
4667 gtk_text_line_new (void)
4671 line = g_new0(GtkTextLine, 1);
4672 line->dir_strong = PANGO_DIRECTION_NEUTRAL;
4673 line->dir_propagated_forward = PANGO_DIRECTION_NEUTRAL;
4674 line->dir_propagated_back = PANGO_DIRECTION_NEUTRAL;
4680 gtk_text_line_destroy (GtkTextBTree *tree, GtkTextLine *line)
4682 GtkTextLineData *ld;
4683 GtkTextLineData *next;
4685 g_return_if_fail (line != NULL);
4692 view = gtk_text_btree_get_view (tree, ld->view_id);
4694 g_assert (view != NULL);
4697 gtk_text_layout_free_line_data (view->layout, line, ld);
4706 gtk_text_line_set_parent (GtkTextLine *line,
4707 GtkTextBTreeNode *node)
4709 if (line->parent == node)
4711 line->parent = node;
4712 gtk_text_btree_node_invalidate_upward (node, NULL);
4716 cleanup_line (GtkTextLine *line)
4718 GtkTextLineSegment *seg, **prev_p;
4722 * Make a pass over all of the segments in the line, giving each
4723 * a chance to clean itself up. This could potentially change
4724 * the structure of the line, e.g. by merging two segments
4725 * together or having two segments cancel themselves; if so,
4726 * then repeat the whole process again, since the first structure
4727 * change might make other structure changes possible. Repeat
4728 * until eventually there are no changes.
4735 for (prev_p = &line->segments, seg = *prev_p;
4737 prev_p = &(*prev_p)->next, seg = *prev_p)
4739 if (seg->type->cleanupFunc != NULL)
4741 *prev_p = (*seg->type->cleanupFunc)(seg, line);
4754 node_data_new (gpointer view_id)
4758 nd = g_new (NodeData, 1);
4760 nd->view_id = view_id;
4770 node_data_destroy (NodeData *nd)
4776 node_data_list_destroy (NodeData *nd)
4782 while (iter != NULL)
4785 node_data_destroy (iter);
4791 node_data_find (NodeData *nd, gpointer view_id)
4795 if (nd->view_id == view_id)
4803 summary_destroy (Summary *summary)
4805 /* Fill with error-triggering garbage */
4806 summary->info = (void*)0x1;
4807 summary->toggle_count = 567;
4808 summary->next = (void*)0x1;
4812 static GtkTextBTreeNode*
4813 gtk_text_btree_node_new (void)
4815 GtkTextBTreeNode *node;
4817 node = g_new (GtkTextBTreeNode, 1);
4819 node->node_data = NULL;
4825 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
4826 GtkTextTagInfo *info,
4831 summary = node->summary;
4832 while (summary != NULL)
4834 if (summary->info == info)
4836 summary->toggle_count += adjust;
4840 summary = summary->next;
4843 if (summary == NULL)
4845 /* didn't find a summary for our tag. */
4846 g_return_if_fail (adjust > 0);
4847 summary = g_new (Summary, 1);
4848 summary->info = info;
4849 summary->toggle_count = adjust;
4850 summary->next = node->summary;
4851 node->summary = summary;
4855 /* Note that the tag root and above do not have summaries
4856 for the tag; only nodes below the tag root have
4859 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4863 summary = node->summary;
4864 while (summary != NULL)
4867 summary->info->tag == tag)
4870 summary = summary->next;
4876 /* Add node and all children to the damage region. */
4878 gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node)
4882 nd = node->node_data;
4889 if (node->level == 0)
4893 line = node->children.line;
4894 while (line != NULL)
4896 GtkTextLineData *ld;
4910 GtkTextBTreeNode *child;
4912 child = node->children.node;
4914 while (child != NULL)
4916 gtk_text_btree_node_invalidate_downward (child);
4918 child = child->next;
4924 gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node, gpointer view_id)
4926 GtkTextBTreeNode *iter;
4929 while (iter != NULL)
4935 nd = node_data_find (iter->node_data, view_id);
4937 if (nd == NULL || !nd->valid)
4938 break; /* Once a node is invalid, we know its parents are as well. */
4944 gboolean should_continue = FALSE;
4946 nd = iter->node_data;
4951 should_continue = TRUE;
4958 if (!should_continue)
4959 break; /* This node was totally invalidated, so are its
4963 iter = iter->parent;
4969 * _gtk_text_btree_is_valid:
4970 * @tree: a #GtkTextBTree
4971 * @view_id: ID for the view
4973 * Check to see if the entire #GtkTextBTree is valid or not for
4976 * Return value: %TRUE if the entire #GtkTextBTree is valid
4979 _gtk_text_btree_is_valid (GtkTextBTree *tree,
4983 g_return_val_if_fail (tree != NULL, FALSE);
4985 nd = node_data_find (tree->root_node->node_data, view_id);
4986 return (nd && nd->valid);
4989 typedef struct _ValidateState ValidateState;
4991 struct _ValidateState
4993 gint remaining_pixels;
4994 gboolean in_validation;
5001 gtk_text_btree_node_validate (BTreeView *view,
5002 GtkTextBTreeNode *node,
5004 ValidateState *state)
5006 gint node_valid = TRUE;
5007 gint node_width = 0;
5008 gint node_height = 0;
5010 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5011 g_return_if_fail (!nd->valid);
5013 if (node->level == 0)
5015 GtkTextLine *line = node->children.line;
5016 GtkTextLineData *ld;
5018 /* Iterate over leading valid lines */
5019 while (line != NULL)
5021 ld = _gtk_text_line_get_data (line, view_id);
5023 if (!ld || !ld->valid)
5025 else if (state->in_validation)
5027 state->in_validation = FALSE;
5032 state->y += ld->height;
5033 node_width = MAX (ld->width, node_width);
5034 node_height += ld->height;
5040 state->in_validation = TRUE;
5042 /* Iterate over invalid lines */
5043 while (line != NULL)
5045 ld = _gtk_text_line_get_data (line, view_id);
5047 if (ld && ld->valid)
5052 state->old_height += ld->height;
5053 ld = gtk_text_layout_wrap (view->layout, line, ld);
5054 state->new_height += ld->height;
5056 node_width = MAX (ld->width, node_width);
5057 node_height += ld->height;
5059 state->remaining_pixels -= ld->height;
5060 if (state->remaining_pixels <= 0)
5070 /* Iterate over the remaining lines */
5071 while (line != NULL)
5073 ld = _gtk_text_line_get_data (line, view_id);
5074 state->in_validation = FALSE;
5076 if (!ld || !ld->valid)
5081 node_width = MAX (ld->width, node_width);
5082 node_height += ld->height;
5090 GtkTextBTreeNode *child;
5093 child = node->children.node;
5095 /* Iterate over leading valid nodes */
5098 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5100 if (!child_nd->valid)
5102 else if (state->in_validation)
5104 state->in_validation = FALSE;
5109 state->y += child_nd->height;
5110 node_width = MAX (node_width, child_nd->width);
5111 node_height += child_nd->height;
5114 child = child->next;
5117 /* Iterate over invalid nodes */
5120 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5122 if (child_nd->valid)
5126 gtk_text_btree_node_validate (view, child, view_id, state);
5128 if (!child_nd->valid)
5130 node_width = MAX (node_width, child_nd->width);
5131 node_height += child_nd->height;
5133 if (!state->in_validation || state->remaining_pixels <= 0)
5135 child = child->next;
5140 child = child->next;
5143 /* Iterate over the remaining lines */
5146 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5147 state->in_validation = FALSE;
5149 if (!child_nd->valid)
5152 node_width = MAX (child_nd->width, node_width);
5153 node_height += child_nd->height;
5155 child = child->next;
5159 nd->width = node_width;
5160 nd->height = node_height;
5161 nd->valid = node_valid;
5165 * _gtk_text_btree_validate:
5166 * @tree: a #GtkTextBTree
5168 * @max_pixels: the maximum number of pixels to validate. (No more
5169 * than one paragraph beyond this limit will be validated)
5170 * @y: location to store starting y coordinate of validated region
5171 * @old_height: location to store old height of validated region
5172 * @new_height: location to store new height of validated region
5174 * Validate a single contiguous invalid region of a #GtkTextBTree for
5177 * Return value: %TRUE if a region has been validated, %FALSE if the
5178 * entire tree was already valid.
5181 _gtk_text_btree_validate (GtkTextBTree *tree,
5190 g_return_val_if_fail (tree != NULL, FALSE);
5192 view = gtk_text_btree_get_view (tree, view_id);
5193 g_return_val_if_fail (view != NULL, FALSE);
5195 if (!_gtk_text_btree_is_valid (tree, view_id))
5197 ValidateState state;
5199 state.remaining_pixels = max_pixels;
5200 state.in_validation = FALSE;
5202 state.old_height = 0;
5203 state.new_height = 0;
5205 gtk_text_btree_node_validate (view,
5212 *old_height = state.old_height;
5214 *new_height = state.new_height;
5216 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5217 _gtk_text_btree_check (tree);
5226 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
5230 gboolean *valid_out)
5234 gboolean valid = TRUE;
5236 if (node->level == 0)
5238 GtkTextLine *line = node->children.line;
5240 while (line != NULL)
5242 GtkTextLineData *ld = _gtk_text_line_get_data (line, view_id);
5244 if (!ld || !ld->valid)
5249 width = MAX (ld->width, width);
5250 height += ld->height;
5258 GtkTextBTreeNode *child = node->children.node;
5262 NodeData *child_nd = node_data_find (child->node_data, view_id);
5264 if (!child_nd || !child_nd->valid)
5269 width = MAX (child_nd->width, width);
5270 height += child_nd->height;
5273 child = child->next;
5278 *height_out = height;
5283 /* Recompute the validity and size of the view data for a given
5284 * view at this node from the immediate children of the node
5287 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
5290 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5295 gtk_text_btree_node_compute_view_aggregates (node, view_id,
5296 &width, &height, &valid);
5298 nd->height = height;
5305 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
5310 gtk_text_btree_node_check_valid (node, view_id);
5311 node = node->parent;
5316 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
5319 if (node->level == 0)
5321 return gtk_text_btree_node_check_valid (node, view_id);
5325 GtkTextBTreeNode *child = node->children.node;
5327 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5335 NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
5337 if (!child_nd->valid)
5339 nd->width = MAX (child_nd->width, nd->width);
5340 nd->height += child_nd->height;
5342 child = child->next;
5351 * _gtk_text_btree_validate_line:
5352 * @tree: a #GtkTextBTree
5353 * @line: line to validate
5354 * @view_id: view ID for the view to validate
5356 * Revalidate a single line of the btree for the given view, propagate
5357 * results up through the entire tree.
5360 _gtk_text_btree_validate_line (GtkTextBTree *tree,
5364 GtkTextLineData *ld;
5367 g_return_if_fail (tree != NULL);
5368 g_return_if_fail (line != NULL);
5370 view = gtk_text_btree_get_view (tree, view_id);
5371 g_return_if_fail (view != NULL);
5373 ld = _gtk_text_line_get_data (line, view_id);
5374 if (!ld || !ld->valid)
5376 ld = gtk_text_layout_wrap (view->layout, line, ld);
5378 gtk_text_btree_node_check_valid_upward (line->parent, view_id);
5383 gtk_text_btree_node_remove_view (BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
5385 if (node->level == 0)
5389 line = node->children.line;
5390 while (line != NULL)
5392 GtkTextLineData *ld;
5394 ld = _gtk_text_line_remove_data (line, view_id);
5397 gtk_text_layout_free_line_data (view->layout, line, ld);
5404 GtkTextBTreeNode *child;
5406 child = node->children.node;
5408 while (child != NULL)
5411 gtk_text_btree_node_remove_view (view, child, view_id);
5413 child = child->next;
5417 gtk_text_btree_node_remove_data (node, view_id);
5421 gtk_text_btree_node_destroy (GtkTextBTree *tree, GtkTextBTreeNode *node)
5423 if (node->level == 0)
5426 GtkTextLineSegment *seg;
5428 while (node->children.line != NULL)
5430 line = node->children.line;
5431 node->children.line = line->next;
5432 while (line->segments != NULL)
5434 seg = line->segments;
5435 line->segments = seg->next;
5437 (*seg->type->deleteFunc) (seg, line, TRUE);
5439 gtk_text_line_destroy (tree, line);
5444 GtkTextBTreeNode *childPtr;
5446 while (node->children.node != NULL)
5448 childPtr = node->children.node;
5449 node->children.node = childPtr->next;
5450 gtk_text_btree_node_destroy (tree, childPtr);
5454 gtk_text_btree_node_free_empty (tree, node);
5458 gtk_text_btree_node_free_empty (GtkTextBTree *tree,
5459 GtkTextBTreeNode *node)
5461 g_return_if_fail ((node->level > 0 && node->children.node == NULL) ||
5462 (node->level == 0 && node->children.line == NULL));
5464 summary_list_destroy (node->summary);
5465 node_data_list_destroy (node->node_data);
5470 gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node, gpointer view_id)
5474 nd = node->node_data;
5477 if (nd->view_id == view_id)
5485 nd = node_data_new (view_id);
5487 if (node->node_data)
5488 nd->next = node->node_data;
5490 node->node_data = nd;
5497 gtk_text_btree_node_remove_data (GtkTextBTreeNode *node, gpointer view_id)
5503 nd = node->node_data;
5506 if (nd->view_id == view_id)
5517 prev->next = nd->next;
5519 if (node->node_data == nd)
5520 node->node_data = nd->next;
5524 node_data_destroy (nd);
5528 gtk_text_btree_node_get_size (GtkTextBTreeNode *node, gpointer view_id,
5529 gint *width, gint *height)
5533 g_return_if_fail (width != NULL);
5534 g_return_if_fail (height != NULL);
5536 nd = gtk_text_btree_node_ensure_data (node, view_id);
5541 *height = nd->height;
5544 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5545 * here isn't quite right, since for a lot of operations we want to
5546 * know which children of the common parent correspond to the two nodes
5547 * (e.g., when computing the order of two iters)
5549 static GtkTextBTreeNode *
5550 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5551 GtkTextBTreeNode *node2)
5553 while (node1->level < node2->level)
5554 node1 = node1->parent;
5555 while (node2->level < node1->level)
5556 node2 = node2->parent;
5557 while (node1 != node2)
5559 node1 = node1->parent;
5560 node2 = node2->parent;
5571 gtk_text_btree_get_view (GtkTextBTree *tree, gpointer view_id)
5576 while (view != NULL)
5578 if (view->view_id == view_id)
5587 get_tree_bounds (GtkTextBTree *tree,
5591 _gtk_text_btree_get_iter_at_line_char (tree, start, 0, 0);
5592 _gtk_text_btree_get_end_iter (tree, end);
5596 tag_changed_cb (GtkTextTagTable *table,
5598 gboolean size_changed,
5603 /* We need to queue a relayout on all regions that are tagged with
5610 if (_gtk_text_btree_get_iter_at_first_toggle (tree, &start, tag))
5612 /* Must be a last toggle if there was a first one. */
5613 _gtk_text_btree_get_iter_at_last_toggle (tree, &end, tag);
5614 DV (g_print ("invalidating due to tag change (%s)\n", G_STRLOC));
5615 _gtk_text_btree_invalidate_region (tree,
5622 /* We only need to queue a redraw, not a relayout */
5627 while (view != NULL)
5631 _gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5632 gtk_text_layout_changed (view->layout, 0, height, height);
5640 _gtk_text_btree_notify_will_remove_tag (GtkTextBTree *tree,
5643 /* Remove the tag from the tree */
5648 get_tree_bounds (tree, &start, &end);
5650 _gtk_text_btree_tag (&start, &end, tag, FALSE);
5651 gtk_text_btree_remove_tag_info (tree, tag);
5655 /* Rebalance the out-of-whack node "node" */
5657 gtk_text_btree_rebalance (GtkTextBTree *tree,
5658 GtkTextBTreeNode *node)
5661 * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5662 * up through the tree one GtkTextBTreeNode at a time until the root
5663 * GtkTextBTreeNode has been processed.
5666 while (node != NULL)
5668 GtkTextBTreeNode *new_node, *child;
5673 * Check to see if the GtkTextBTreeNode has too many children. If it does,
5674 * then split off all but the first MIN_CHILDREN into a separate
5675 * GtkTextBTreeNode following the original one. Then repeat until the
5676 * GtkTextBTreeNode has a decent size.
5679 if (node->num_children > MAX_CHILDREN)
5684 * If the GtkTextBTreeNode being split is the root
5685 * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5689 if (node->parent == NULL)
5691 new_node = gtk_text_btree_node_new ();
5692 new_node->parent = NULL;
5693 new_node->next = NULL;
5694 new_node->summary = NULL;
5695 new_node->level = node->level + 1;
5696 new_node->children.node = node;
5697 recompute_node_counts (tree, new_node);
5698 tree->root_node = new_node;
5700 new_node = gtk_text_btree_node_new ();
5701 new_node->parent = node->parent;
5702 new_node->next = node->next;
5703 node->next = new_node;
5704 new_node->summary = NULL;
5705 new_node->level = node->level;
5706 new_node->num_children = node->num_children - MIN_CHILDREN;
5707 if (node->level == 0)
5709 for (i = MIN_CHILDREN-1,
5710 line = node->children.line;
5711 i > 0; i--, line = line->next)
5713 /* Empty loop body. */
5715 new_node->children.line = line->next;
5720 for (i = MIN_CHILDREN-1,
5721 child = node->children.node;
5722 i > 0; i--, child = child->next)
5724 /* Empty loop body. */
5726 new_node->children.node = child->next;
5729 recompute_node_counts (tree, node);
5730 node->parent->num_children++;
5732 if (node->num_children <= MAX_CHILDREN)
5734 recompute_node_counts (tree, node);
5740 while (node->num_children < MIN_CHILDREN)
5742 GtkTextBTreeNode *other;
5743 GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5744 GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5745 int total_children, first_children, i;
5748 * Too few children for this GtkTextBTreeNode. If this is the root then,
5749 * it's OK for it to have less than MIN_CHILDREN children
5750 * as long as it's got at least two. If it has only one
5751 * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5752 * the tree and use its child as the new root.
5755 if (node->parent == NULL)
5757 if ((node->num_children == 1) && (node->level > 0))
5759 tree->root_node = node->children.node;
5760 tree->root_node->parent = NULL;
5762 node->children.node = NULL;
5763 gtk_text_btree_node_free_empty (tree, node);
5769 * Not the root. Make sure that there are siblings to
5773 if (node->parent->num_children < 2)
5775 gtk_text_btree_rebalance (tree, node->parent);
5780 * Find a sibling neighbor to borrow from, and arrange for
5781 * node to be the earlier of the pair.
5784 if (node->next == NULL)
5786 for (other = node->parent->children.node;
5787 other->next != node;
5788 other = other->next)
5790 /* Empty loop body. */
5797 * We're going to either merge the two siblings together
5798 * into one GtkTextBTreeNode or redivide the children among them to
5799 * balance their loads. As preparation, join their two
5800 * child lists into a single list and remember the half-way
5801 * point in the list.
5804 total_children = node->num_children + other->num_children;
5805 first_children = total_children/2;
5806 if (node->children.node == NULL)
5808 node->children = other->children;
5809 other->children.node = NULL;
5810 other->children.line = NULL;
5812 if (node->level == 0)
5816 for (line = node->children.line, i = 1;
5818 line = line->next, i++)
5820 if (i == first_children)
5825 line->next = other->children.line;
5826 while (i <= first_children)
5835 GtkTextBTreeNode *child;
5837 for (child = node->children.node, i = 1;
5838 child->next != NULL;
5839 child = child->next, i++)
5841 if (i <= first_children)
5843 if (i == first_children)
5845 halfwaynode = child;
5849 child->next = other->children.node;
5850 while (i <= first_children)
5852 halfwaynode = child;
5853 child = child->next;
5859 * If the two siblings can simply be merged together, do it.
5862 if (total_children <= MAX_CHILDREN)
5864 recompute_node_counts (tree, node);
5865 node->next = other->next;
5866 node->parent->num_children--;
5868 other->children.node = NULL;
5869 other->children.line = NULL;
5870 gtk_text_btree_node_free_empty (tree, other);
5875 * The siblings can't be merged, so just divide their
5876 * children evenly between them.
5879 if (node->level == 0)
5881 other->children.line = halfwayline->next;
5882 halfwayline->next = NULL;
5886 other->children.node = halfwaynode->next;
5887 halfwaynode->next = NULL;
5890 recompute_node_counts (tree, node);
5891 recompute_node_counts (tree, other);
5894 node = node->parent;
5899 post_insert_fixup (GtkTextBTree *tree,
5901 gint line_count_delta,
5902 gint char_count_delta)
5905 GtkTextBTreeNode *node;
5908 * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5909 * point, then rebalance the tree if necessary.
5912 for (node = line->parent ; node != NULL;
5913 node = node->parent)
5915 node->num_lines += line_count_delta;
5916 node->num_chars += char_count_delta;
5918 node = line->parent;
5919 node->num_children += line_count_delta;
5921 if (node->num_children > MAX_CHILDREN)
5923 gtk_text_btree_rebalance (tree, node);
5926 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5927 _gtk_text_btree_check (tree);
5930 static GtkTextTagInfo*
5931 gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
5934 GtkTextTagInfo *info;
5938 list = tree->tag_infos;
5939 while (list != NULL)
5942 if (info->tag == tag)
5945 list = g_slist_next (list);
5951 static GtkTextTagInfo*
5952 gtk_text_btree_get_tag_info (GtkTextBTree *tree,
5955 GtkTextTagInfo *info;
5957 info = gtk_text_btree_get_existing_tag_info (tree, tag);
5961 /* didn't find it, create. */
5963 info = g_new (GtkTextTagInfo, 1);
5967 info->tag_root = NULL;
5968 info->toggle_count = 0;
5970 tree->tag_infos = g_slist_prepend (tree->tag_infos, info);
5973 g_print ("Created tag info %p for tag %s(%p)\n",
5974 info, info->tag->name ? info->tag->name : "anon",
5983 gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
5986 GtkTextTagInfo *info;
5991 list = tree->tag_infos;
5992 while (list != NULL)
5995 if (info->tag == tag)
5998 g_print ("Removing tag info %p for tag %s(%p)\n",
5999 info, info->tag->name ? info->tag->name : "anon",
6005 prev->next = list->next;
6009 tree->tag_infos = list->next;
6012 g_slist_free (list);
6014 g_object_unref (info->tag);
6021 list = g_slist_next (list);
6026 recompute_level_zero_counts (GtkTextBTreeNode *node)
6029 GtkTextLineSegment *seg;
6031 g_assert (node->level == 0);
6033 line = node->children.line;
6034 while (line != NULL)
6036 node->num_children++;
6039 if (line->parent != node)
6040 gtk_text_line_set_parent (line, node);
6042 seg = line->segments;
6046 node->num_chars += seg->char_count;
6048 if (((seg->type != >k_text_toggle_on_type)
6049 && (seg->type != >k_text_toggle_off_type))
6050 || !(seg->body.toggle.inNodeCounts))
6056 GtkTextTagInfo *info;
6058 info = seg->body.toggle.info;
6060 gtk_text_btree_node_adjust_toggle_count (node, info, 1);
6071 recompute_level_nonzero_counts (GtkTextBTreeNode *node)
6074 GtkTextBTreeNode *child;
6076 g_assert (node->level > 0);
6078 child = node->children.node;
6079 while (child != NULL)
6081 node->num_children += 1;
6082 node->num_lines += child->num_lines;
6083 node->num_chars += child->num_chars;
6085 if (child->parent != node)
6087 child->parent = node;
6088 gtk_text_btree_node_invalidate_upward (node, NULL);
6091 summary = child->summary;
6092 while (summary != NULL)
6094 gtk_text_btree_node_adjust_toggle_count (node,
6096 summary->toggle_count);
6098 summary = summary->next;
6101 child = child->next;
6106 *----------------------------------------------------------------------
6108 * recompute_node_counts --
6110 * This procedure is called to recompute all the counts in a GtkTextBTreeNode
6111 * (tags, child information, etc.) by scanning the information in
6112 * its descendants. This procedure is called during rebalancing
6113 * when a GtkTextBTreeNode's child structure has changed.
6119 * The tag counts for node are modified to reflect its current
6120 * child structure, as are its num_children, num_lines, num_chars fields.
6121 * Also, all of the childrens' parent fields are made to point
6124 *----------------------------------------------------------------------
6128 recompute_node_counts (GtkTextBTree *tree, GtkTextBTreeNode *node)
6131 Summary *summary, *summary2;
6134 * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
6135 * the existing Summary records (most of them will probably be reused).
6138 summary = node->summary;
6139 while (summary != NULL)
6141 summary->toggle_count = 0;
6142 summary = summary->next;
6145 node->num_children = 0;
6146 node->num_lines = 0;
6147 node->num_chars = 0;
6150 * Scan through the children, adding the childrens' tag counts into
6151 * the GtkTextBTreeNode's tag counts and adding new Summary structures if
6155 if (node->level == 0)
6156 recompute_level_zero_counts (node);
6158 recompute_level_nonzero_counts (node);
6163 gtk_text_btree_node_check_valid (node, view->view_id);
6168 * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
6169 * records that still have a zero count, or that have all the toggles.
6170 * The GtkTextBTreeNode with the children that account for all the tags toggles
6171 * have no summary information, and they become the tag_root for the tag.
6175 for (summary = node->summary; summary != NULL; )
6177 if (summary->toggle_count > 0 &&
6178 summary->toggle_count < summary->info->toggle_count)
6180 if (node->level == summary->info->tag_root->level)
6183 * The tag's root GtkTextBTreeNode split and some toggles left.
6184 * The tag root must move up a level.
6186 summary->info->tag_root = node->parent;
6189 summary = summary->next;
6192 if (summary->toggle_count == summary->info->toggle_count)
6195 * A GtkTextBTreeNode merge has collected all the toggles under
6196 * one GtkTextBTreeNode. Push the root down to this level.
6198 summary->info->tag_root = node;
6200 if (summary2 != NULL)
6202 summary2->next = summary->next;
6203 summary_destroy (summary);
6204 summary = summary2->next;
6208 node->summary = summary->next;
6209 summary_destroy (summary);
6210 summary = node->summary;
6216 _gtk_change_node_toggle_count (GtkTextBTreeNode *node,
6217 GtkTextTagInfo *info,
6218 gint delta) /* may be negative */
6220 Summary *summary, *prevPtr;
6221 GtkTextBTreeNode *node2Ptr;
6222 int rootLevel; /* Level of original tag root */
6224 info->toggle_count += delta;
6226 if (info->tag_root == (GtkTextBTreeNode *) NULL)
6228 info->tag_root = node;
6233 * Note the level of the existing root for the tag so we can detect
6234 * if it needs to be moved because of the toggle count change.
6237 rootLevel = info->tag_root->level;
6240 * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
6241 * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
6245 for ( ; node != info->tag_root; node = node->parent)
6248 * See if there's already an entry for this tag for this GtkTextBTreeNode. If so,
6249 * perhaps all we have to do is adjust its count.
6252 for (prevPtr = NULL, summary = node->summary;
6254 prevPtr = summary, summary = summary->next)
6256 if (summary->info == info)
6261 if (summary != NULL)
6263 summary->toggle_count += delta;
6264 if (summary->toggle_count > 0 &&
6265 summary->toggle_count < info->toggle_count)
6269 if (summary->toggle_count != 0)
6272 * Should never find a GtkTextBTreeNode with max toggle count at this
6273 * point (there shouldn't have been a summary entry in the
6277 g_error ("%s: bad toggle count (%d) max (%d)",
6278 G_STRLOC, summary->toggle_count, info->toggle_count);
6282 * Zero toggle count; must remove this tag from the list.
6285 if (prevPtr == NULL)
6287 node->summary = summary->next;
6291 prevPtr->next = summary->next;
6293 summary_destroy (summary);
6298 * This tag isn't currently in the summary information list.
6301 if (rootLevel == node->level)
6305 * The old tag root is at the same level in the tree as this
6306 * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode. Move the tag root up
6307 * a level, in the hopes that it will now cover this GtkTextBTreeNode
6308 * as well as the old root (if not, we'll move it up again
6309 * the next time through the loop). To push it up one level
6310 * we copy the original toggle count into the summary
6311 * information at the old root and change the root to its
6312 * parent GtkTextBTreeNode.
6315 GtkTextBTreeNode *rootnode = info->tag_root;
6316 summary = (Summary *) g_malloc (sizeof (Summary));
6317 summary->info = info;
6318 summary->toggle_count = info->toggle_count - delta;
6319 summary->next = rootnode->summary;
6320 rootnode->summary = summary;
6321 rootnode = rootnode->parent;
6322 rootLevel = rootnode->level;
6323 info->tag_root = rootnode;
6325 summary = (Summary *) g_malloc (sizeof (Summary));
6326 summary->info = info;
6327 summary->toggle_count = delta;
6328 summary->next = node->summary;
6329 node->summary = summary;
6334 * If we've decremented the toggle count, then it may be necessary
6335 * to push the tag root down one or more levels.
6342 if (info->toggle_count == 0)
6344 info->tag_root = (GtkTextBTreeNode *) NULL;
6347 node = info->tag_root;
6348 while (node->level > 0)
6351 * See if a single child GtkTextBTreeNode accounts for all of the tag's
6352 * toggles. If so, push the root down one level.
6355 for (node2Ptr = node->children.node;
6356 node2Ptr != (GtkTextBTreeNode *)NULL ;
6357 node2Ptr = node2Ptr->next)
6359 for (prevPtr = NULL, summary = node2Ptr->summary;
6361 prevPtr = summary, summary = summary->next)
6363 if (summary->info == info)
6368 if (summary == NULL)
6372 if (summary->toggle_count != info->toggle_count)
6375 * No GtkTextBTreeNode has all toggles, so the root is still valid.
6382 * This GtkTextBTreeNode has all the toggles, so push down the root.
6385 if (prevPtr == NULL)
6387 node2Ptr->summary = summary->next;
6391 prevPtr->next = summary->next;
6393 summary_destroy (summary);
6394 info->tag_root = node2Ptr;
6397 node = info->tag_root;
6402 *----------------------------------------------------------------------
6406 * This is a utility procedure used by _gtk_text_btree_get_tags. It
6407 * increments the count for a particular tag, adding a new
6408 * entry for that tag if there wasn't one previously.
6414 * The information at *tagInfoPtr may be modified, and the arrays
6415 * may be reallocated to make them larger.
6417 *----------------------------------------------------------------------
6421 inc_count (GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
6426 for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
6427 count > 0; tag_p++, count--)
6431 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
6437 * There isn't currently an entry for this tag, so we have to
6438 * make a new one. If the arrays are full, then enlarge the
6442 if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
6444 GtkTextTag **newTags;
6445 int *newCounts, newSize;
6447 newSize = 2*tagInfoPtr->arraySize;
6448 newTags = (GtkTextTag **) g_malloc ((unsigned)
6449 (newSize*sizeof (GtkTextTag *)));
6450 memcpy ((void *) newTags, (void *) tagInfoPtr->tags,
6451 tagInfoPtr->arraySize *sizeof (GtkTextTag *));
6452 g_free ((char *) tagInfoPtr->tags);
6453 tagInfoPtr->tags = newTags;
6454 newCounts = (int *) g_malloc ((unsigned) (newSize*sizeof (int)));
6455 memcpy ((void *) newCounts, (void *) tagInfoPtr->counts,
6456 tagInfoPtr->arraySize *sizeof (int));
6457 g_free ((char *) tagInfoPtr->counts);
6458 tagInfoPtr->counts = newCounts;
6459 tagInfoPtr->arraySize = newSize;
6462 tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
6463 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
6464 tagInfoPtr->numTags++;
6468 gtk_text_btree_link_segment (GtkTextLineSegment *seg,
6469 const GtkTextIter *iter)
6471 GtkTextLineSegment *prev;
6475 line = _gtk_text_iter_get_text_line (iter);
6476 tree = _gtk_text_iter_get_btree (iter);
6478 prev = gtk_text_line_segment_split (iter);
6481 seg->next = line->segments;
6482 line->segments = seg;
6486 seg->next = prev->next;
6489 cleanup_line (line);
6490 segments_changed (tree);
6492 if (gtk_debug_flags & GTK_DEBUG_TEXT)
6493 _gtk_text_btree_check (tree);
6497 gtk_text_btree_unlink_segment (GtkTextBTree *tree,
6498 GtkTextLineSegment *seg,
6501 GtkTextLineSegment *prev;
6503 if (line->segments == seg)
6505 line->segments = seg->next;
6509 for (prev = line->segments; prev->next != seg;
6512 /* Empty loop body. */
6514 prev->next = seg->next;
6516 cleanup_line (line);
6517 segments_changed (tree);
6521 * This is here because it requires BTree internals, it logically
6522 * belongs in gtktextsegment.c
6527 *--------------------------------------------------------------
6529 * _gtk_toggle_segment_check_func --
6531 * This procedure is invoked to perform consistency checks
6532 * on toggle segments.
6538 * If a consistency problem is found the procedure g_errors.
6540 *--------------------------------------------------------------
6544 _gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6550 if (segPtr->byte_count != 0)
6552 g_error ("toggle_segment_check_func: segment had non-zero size");
6554 if (!segPtr->body.toggle.inNodeCounts)
6556 g_error ("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6558 needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6559 for (summary = line->parent->summary; ;
6560 summary = summary->next)
6562 if (summary == NULL)
6566 g_error ("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6573 if (summary->info == segPtr->body.toggle.info)
6577 g_error ("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6589 gtk_text_btree_node_view_check_consistency (GtkTextBTree *tree,
6590 GtkTextBTreeNode *node,
6600 while (view != NULL)
6602 if (view->view_id == nd->view_id)
6609 g_error ("Node has data for a view %p no longer attached to the tree",
6612 gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6613 &width, &height, &valid);
6615 /* valid aggregate not checked the same as width/height, because on
6616 * btree rebalance we can have invalid nodes where all lines below
6617 * them are actually valid, due to moving lines around between
6620 * The guarantee is that if there are invalid lines the node is
6621 * invalid - we don't guarantee that if the node is invalid there
6622 * are invalid lines.
6625 if (nd->width != width ||
6626 nd->height != height ||
6627 (nd->valid && !valid))
6629 g_error ("Node aggregates for view %p are invalid:\n"
6630 "Are (%d,%d,%s), should be (%d,%d,%s)",
6632 nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6633 width, height, valid ? "TRUE" : "FALSE");
6638 gtk_text_btree_node_check_consistency (GtkTextBTree *tree,
6639 GtkTextBTreeNode *node)
6641 GtkTextBTreeNode *childnode;
6642 Summary *summary, *summary2;
6644 GtkTextLineSegment *segPtr;
6645 int num_children, num_lines, num_chars, toggle_count, min_children;
6646 GtkTextLineData *ld;
6649 if (node->parent != NULL)
6651 min_children = MIN_CHILDREN;
6653 else if (node->level > 0)
6660 if ((node->num_children < min_children)
6661 || (node->num_children > MAX_CHILDREN))
6663 g_error ("gtk_text_btree_node_check_consistency: bad child count (%d)",
6664 node->num_children);
6667 nd = node->node_data;
6670 gtk_text_btree_node_view_check_consistency (tree, node, nd);
6677 if (node->level == 0)
6679 for (line = node->children.line; line != NULL;
6682 if (line->parent != node)
6684 g_error ("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6686 if (line->segments == NULL)
6688 g_error ("gtk_text_btree_node_check_consistency: line has no segments");
6694 /* Just ensuring we don't segv while doing this loop */
6699 for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6701 if (segPtr->type->checkFunc != NULL)
6703 (*segPtr->type->checkFunc)(segPtr, line);
6705 if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6706 && (segPtr->next != NULL)
6707 && (segPtr->next->byte_count == 0)
6708 && (segPtr->next->type->leftGravity))
6710 g_error ("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6712 if ((segPtr->next == NULL)
6713 && (segPtr->type != >k_text_char_type))
6715 g_error ("gtk_text_btree_node_check_consistency: line ended with wrong type");
6718 num_chars += segPtr->char_count;
6727 for (childnode = node->children.node; childnode != NULL;
6728 childnode = childnode->next)
6730 if (childnode->parent != node)
6732 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6734 if (childnode->level != (node->level-1))
6736 g_error ("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6737 node->level, childnode->level);
6739 gtk_text_btree_node_check_consistency (tree, childnode);
6740 for (summary = childnode->summary; summary != NULL;
6741 summary = summary->next)
6743 for (summary2 = node->summary; ;
6744 summary2 = summary2->next)
6746 if (summary2 == NULL)
6748 if (summary->info->tag_root == node)
6752 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6753 summary->info->tag->name,
6754 "present in parent summaries");
6756 if (summary->info == summary2->info)
6763 num_lines += childnode->num_lines;
6764 num_chars += childnode->num_chars;
6767 if (num_children != node->num_children)
6769 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6770 num_children, node->num_children);
6772 if (num_lines != node->num_lines)
6774 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6775 num_lines, node->num_lines);
6777 if (num_chars != node->num_chars)
6779 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6780 num_chars, node->num_chars);
6783 for (summary = node->summary; summary != NULL;
6784 summary = summary->next)
6786 if (summary->info->toggle_count == summary->toggle_count)
6788 g_error ("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6789 summary->info->tag->name);
6792 if (node->level == 0)
6794 for (line = node->children.line; line != NULL;
6797 for (segPtr = line->segments; segPtr != NULL;
6798 segPtr = segPtr->next)
6800 if ((segPtr->type != >k_text_toggle_on_type)
6801 && (segPtr->type != >k_text_toggle_off_type))
6805 if (segPtr->body.toggle.info == summary->info)
6807 if (!segPtr->body.toggle.inNodeCounts)
6808 g_error ("Toggle segment not in the node counts");
6817 for (childnode = node->children.node;
6819 childnode = childnode->next)
6821 for (summary2 = childnode->summary;
6823 summary2 = summary2->next)
6825 if (summary2->info == summary->info)
6827 toggle_count += summary2->toggle_count;
6832 if (toggle_count != summary->toggle_count)
6834 g_error ("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6835 toggle_count, summary->toggle_count);
6837 for (summary2 = summary->next; summary2 != NULL;
6838 summary2 = summary2->next)
6840 if (summary2->info == summary->info)
6842 g_error ("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6843 summary->info->tag->name);
6850 listify_foreach (GtkTextTag *tag, gpointer user_data)
6852 GSList** listp = user_data;
6854 *listp = g_slist_prepend (*listp, tag);
6858 list_of_tags (GtkTextTagTable *table)
6860 GSList *list = NULL;
6862 gtk_text_tag_table_foreach (table, listify_foreach, &list);
6868 _gtk_text_btree_check (GtkTextBTree *tree)
6871 GtkTextBTreeNode *node;
6873 GtkTextLineSegment *seg;
6875 GSList *all_tags, *taglist = NULL;
6877 GtkTextTagInfo *info;
6880 * Make sure that the tag toggle counts and the tag root pointers are OK.
6882 all_tags = list_of_tags (tree->table);
6883 for (taglist = all_tags; taglist != NULL ; taglist = taglist->next)
6885 tag = taglist->data;
6886 info = gtk_text_btree_get_existing_tag_info (tree, tag);
6889 node = info->tag_root;
6892 if (info->toggle_count != 0)
6894 g_error ("_gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6895 tag->name, info->toggle_count);
6897 continue; /* no ranges for the tag */
6899 else if (info->toggle_count == 0)
6901 g_error ("_gtk_text_btree_check found root for \"%s\" with no toggles",
6904 else if (info->toggle_count & 1)
6906 g_error ("_gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6907 tag->name, info->toggle_count);
6909 for (summary = node->summary; summary != NULL;
6910 summary = summary->next)
6912 if (summary->info->tag == tag)
6914 g_error ("_gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6918 if (node->level > 0)
6920 for (node = node->children.node ; node != NULL ;
6923 for (summary = node->summary; summary != NULL;
6924 summary = summary->next)
6926 if (summary->info->tag == tag)
6928 count += summary->toggle_count;
6935 GtkTextLineSegmentClass * last = NULL;
6937 for (line = node->children.line ; line != NULL ;
6940 for (seg = line->segments; seg != NULL;
6943 if ((seg->type == >k_text_toggle_on_type ||
6944 seg->type == >k_text_toggle_off_type) &&
6945 seg->body.toggle.info->tag == tag)
6947 if (last == seg->type)
6948 g_error ("Two consecutive toggles on or off weren't merged");
6949 if (!seg->body.toggle.inNodeCounts)
6950 g_error ("Toggle segment not in the node counts");
6959 if (count != info->toggle_count)
6961 g_error ("_gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
6962 info->toggle_count, tag->name, count);
6967 g_slist_free (all_tags);
6970 * Call a recursive procedure to do the main body of checks.
6973 node = tree->root_node;
6974 gtk_text_btree_node_check_consistency (tree, tree->root_node);
6977 * Make sure that there are at least two lines in the text and
6978 * that the last line has no characters except a newline.
6981 if (node->num_lines < 2)
6983 g_error ("_gtk_text_btree_check: less than 2 lines in tree");
6985 if (node->num_chars < 2)
6987 g_error ("_gtk_text_btree_check: less than 2 chars in tree");
6989 while (node->level > 0)
6991 node = node->children.node;
6992 while (node->next != NULL)
6997 line = node->children.line;
6998 while (line->next != NULL)
7002 seg = line->segments;
7003 while ((seg->type == >k_text_toggle_off_type)
7004 || (seg->type == >k_text_right_mark_type)
7005 || (seg->type == >k_text_left_mark_type))
7008 * It's OK to toggle a tag off in the last line, but
7009 * not to start a new range. It's also OK to have marks
7015 if (seg->type != >k_text_char_type)
7017 g_error ("_gtk_text_btree_check: last line has bogus segment type");
7019 if (seg->next != NULL)
7021 g_error ("_gtk_text_btree_check: last line has too many segments");
7023 if (seg->byte_count != 1)
7025 g_error ("_gtk_text_btree_check: last line has wrong # characters: %d",
7028 if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
7030 g_error ("_gtk_text_btree_check: last line had bad value: %s",
7035 void _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line);
7036 void _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment* seg);
7037 void _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent);
7038 void _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
7041 _gtk_text_btree_spew (GtkTextBTree *tree)
7046 printf ("%d lines in tree %p\n",
7047 _gtk_text_btree_line_count (tree), tree);
7049 line = _gtk_text_btree_get_line (tree, 0, &real_line);
7051 while (line != NULL)
7053 _gtk_text_btree_spew_line (tree, line);
7054 line = _gtk_text_line_next (line);
7057 printf ("=================== Tag information\n");
7062 list = tree->tag_infos;
7064 while (list != NULL)
7066 GtkTextTagInfo *info;
7070 printf (" tag `%s': root at %p, toggle count %d\n",
7071 info->tag->name, info->tag_root, info->toggle_count);
7073 list = g_slist_next (list);
7076 if (tree->tag_infos == NULL)
7078 printf (" (no tags in the tree)\n");
7082 printf ("=================== Tree nodes\n");
7085 _gtk_text_btree_spew_node (tree->root_node, 0);
7090 _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
7093 GtkTextLineSegment *seg;
7095 spaces = g_strnfill (indent, ' ');
7097 printf ("%sline %p chars %d bytes %d\n",
7099 _gtk_text_line_char_count (line),
7100 _gtk_text_line_byte_count (line));
7102 seg = line->segments;
7105 if (seg->type == >k_text_char_type)
7107 gchar* str = g_strndup (seg->body.chars, MIN (seg->byte_count, 10));
7112 if (*s == '\n' || *s == '\r')
7116 printf ("%s chars `%s'...\n", spaces, str);
7119 else if (seg->type == >k_text_right_mark_type)
7121 printf ("%s right mark `%s' visible: %d\n",
7123 seg->body.mark.name,
7124 seg->body.mark.visible);
7126 else if (seg->type == >k_text_left_mark_type)
7128 printf ("%s left mark `%s' visible: %d\n",
7130 seg->body.mark.name,
7131 seg->body.mark.visible);
7133 else if (seg->type == >k_text_toggle_on_type ||
7134 seg->type == >k_text_toggle_off_type)
7136 printf ("%s tag `%s' %s\n",
7137 spaces, seg->body.toggle.info->tag->name,
7138 seg->type == >k_text_toggle_off_type ? "off" : "on");
7148 _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent)
7151 GtkTextBTreeNode *iter;
7154 spaces = g_strnfill (indent, ' ');
7156 printf ("%snode %p level %d children %d lines %d chars %d\n",
7157 spaces, node, node->level,
7158 node->num_children, node->num_lines, node->num_chars);
7163 printf ("%s %d toggles of `%s' below this node\n",
7164 spaces, s->toggle_count, s->info->tag->name);
7170 if (node->level > 0)
7172 iter = node->children.node;
7173 while (iter != NULL)
7175 _gtk_text_btree_spew_node (iter, indent + 2);
7182 GtkTextLine *line = node->children.line;
7183 while (line != NULL)
7185 _gtk_text_btree_spew_line_short (line, indent + 2);
7193 _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line)
7195 GtkTextLineSegment * seg;
7197 printf ("%4d| line: %p parent: %p next: %p\n",
7198 _gtk_text_line_get_number (line), line, line->parent, line->next);
7200 seg = line->segments;
7204 _gtk_text_btree_spew_segment (tree, seg);
7210 _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment * seg)
7212 printf (" segment: %p type: %s bytes: %d chars: %d\n",
7213 seg, seg->type->name, seg->byte_count, seg->char_count);
7215 if (seg->type == >k_text_char_type)
7217 gchar* str = g_strndup (seg->body.chars, seg->byte_count);
7218 printf (" `%s'\n", str);
7221 else if (seg->type == >k_text_right_mark_type)
7223 printf (" right mark `%s' visible: %d not_deleteable: %d\n",
7224 seg->body.mark.name,
7225 seg->body.mark.visible,
7226 seg->body.mark.not_deleteable);
7228 else if (seg->type == >k_text_left_mark_type)
7230 printf (" left mark `%s' visible: %d not_deleteable: %d\n",
7231 seg->body.mark.name,
7232 seg->body.mark.visible,
7233 seg->body.mark.not_deleteable);
7235 else if (seg->type == >k_text_toggle_on_type ||
7236 seg->type == >k_text_toggle_off_type)
7238 printf (" tag `%s' priority %d\n",
7239 seg->body.toggle.info->tag->name,
7240 seg->body.toggle.info->tag->priority);