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 #include "gtktextbtree.h"
60 #include "gtksignal.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 */
105 /* boolean indicating whether the height/width need to be recomputed */
111 * The data structure below keeps summary information about one tag as part
112 * of the tag information in a node.
115 typedef struct Summary {
116 GtkTextTagInfo *info; /* Handle for tag. */
117 int toggle_count; /* Number of transitions into or
118 * out of this tag that occur in
119 * the subtree rooted at this node. */
120 struct Summary *next; /* Next in list of all tags for same
121 * node, or NULL if at end of list. */
125 * The data structure below defines a node in the B-tree.
128 struct _GtkTextBTreeNode {
129 GtkTextBTreeNode *parent; /* Pointer to parent node, or NULL if
130 * this is the root. */
131 GtkTextBTreeNode *next; /* Next in list of siblings with the
132 * same parent node, or NULL for end
134 Summary *summary; /* First in malloc-ed list of info
135 * about tags in this subtree (NULL if
136 * no tag info in the subtree). */
137 int level; /* Level of this node in the B-tree.
138 * 0 refers to the bottom of the tree
139 * (children are lines, not nodes). */
140 union { /* First in linked list of children. */
141 struct _GtkTextBTreeNode *node; /* Used if level > 0. */
142 GtkTextLine *line; /* Used if level == 0. */
144 int num_children; /* Number of children of this node. */
145 int num_lines; /* Total number of lines (leaves) in
146 * the subtree rooted here. */
147 int num_chars; /* Number of chars below here */
154 * Used to store the list of views in our btree
157 typedef struct _BTreeView BTreeView;
161 GtkTextLayout *layout;
167 * And the tree itself
170 struct _GtkTextBTree {
171 GtkTextBTreeNode *root_node; /* Pointer to root of B-tree. */
172 GtkTextTagTable *table;
173 GHashTable *mark_table;
175 GtkTextMark *insert_mark;
176 GtkTextMark *selection_bound_mark;
177 GtkTextBuffer *buffer;
180 guint tag_changed_handler;
181 guint tag_removed_handler;
182 /* Incremented when a segment with a byte size > 0
183 is added to or removed from the tree (i.e. the
184 length of a line may have changed, and lines may
185 have been added or removed). This invalidates
186 all outstanding iterators.
188 guint chars_changed_stamp;
189 /* Incremented when any segments are added or deleted;
190 this makes outstanding iterators recalculate their
191 pointed-to segment and segment offset.
193 guint segments_changed_stamp;
195 GtkTextLine *end_iter_line;
197 guint end_iter_line_stamp;
199 GHashTable *child_anchor_table;
204 * Upper and lower bounds on how many children a node may have:
205 * rebalance when either of these limits is exceeded. MAX_CHILDREN
206 * should be twice MIN_CHILDREN and MIN_CHILDREN must be >= 2.
209 /* Tk used MAX of 12 and MIN of 6. This makes the tree wide and
210 shallow. It appears to be faster to locate a particular line number
211 if the tree is narrow and deep, since it is more finely sorted. I
212 guess this may increase memory use though, and make it slower to
213 walk the tree in order, or locate a particular byte index (which
214 is done by walking the tree in order).
216 There's basically a tradeoff here. However I'm thinking we want to
217 add pixels, byte counts, and char counts to the tree nodes,
218 at that point narrow and deep should speed up all operations,
219 not just the line number searches.
223 #define MAX_CHILDREN 12
224 #define MIN_CHILDREN 6
226 #define MAX_CHILDREN 6
227 #define MIN_CHILDREN 3
234 static BTreeView *gtk_text_btree_get_view (GtkTextBTree *tree,
236 static void gtk_text_btree_rebalance (GtkTextBTree *tree,
237 GtkTextBTreeNode *node);
238 static GtkTextLine * get_last_line (GtkTextBTree *tree);
239 static void post_insert_fixup (GtkTextBTree *tree,
240 GtkTextLine *insert_line,
241 gint char_count_delta,
242 gint line_count_delta);
243 static void gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
244 GtkTextTagInfo *info,
246 static gboolean gtk_text_btree_node_has_tag (GtkTextBTreeNode *node,
249 static void segments_changed (GtkTextBTree *tree);
250 static void chars_changed (GtkTextBTree *tree);
251 static void summary_list_destroy (Summary *summary);
252 static GtkTextLine *gtk_text_line_new (void);
253 static void gtk_text_line_destroy (GtkTextBTree *tree,
255 static void gtk_text_line_set_parent (GtkTextLine *line,
256 GtkTextBTreeNode *node);
257 static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
261 static NodeData *node_data_new (gpointer view_id);
262 static void node_data_destroy (NodeData *nd);
263 static void node_data_list_destroy (NodeData *nd);
264 static NodeData *node_data_find (NodeData *nd,
267 static GtkTextBTreeNode *gtk_text_btree_node_new (void);
268 static void gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node);
269 static void gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node,
271 static NodeData * gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
273 static NodeData * gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
275 static void gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
278 static void gtk_text_btree_node_remove_view (BTreeView *view,
279 GtkTextBTreeNode *node,
281 static void gtk_text_btree_node_destroy (GtkTextBTree *tree,
282 GtkTextBTreeNode *node);
283 static void gtk_text_btree_node_free_empty (GtkTextBTree *tree,
284 GtkTextBTreeNode *node);
285 static NodeData * gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node,
287 static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
289 static void gtk_text_btree_node_get_size (GtkTextBTreeNode *node,
293 static GtkTextBTreeNode * gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
294 GtkTextBTreeNode *node2);
295 static void get_tree_bounds (GtkTextBTree *tree,
298 static void tag_changed_cb (GtkTextTagTable *table,
300 gboolean size_changed,
302 static void tag_removed_cb (GtkTextTagTable *table,
305 static void cleanup_line (GtkTextLine *line);
306 static void recompute_node_counts (GtkTextBTree *tree,
307 GtkTextBTreeNode *node);
308 static void inc_count (GtkTextTag *tag,
310 TagInfo *tagInfoPtr);
312 static void summary_destroy (Summary *summary);
314 static void gtk_text_btree_link_segment (GtkTextLineSegment *seg,
315 const GtkTextIter *iter);
316 static void gtk_text_btree_unlink_segment (GtkTextBTree *tree,
317 GtkTextLineSegment *seg,
321 static GtkTextTagInfo *gtk_text_btree_get_tag_info (GtkTextBTree *tree,
323 static GtkTextTagInfo *gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
325 static void gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
328 static void redisplay_region (GtkTextBTree *tree,
329 const GtkTextIter *start,
330 const GtkTextIter *end);
332 /* Inline thingies */
335 segments_changed (GtkTextBTree *tree)
337 tree->segments_changed_stamp += 1;
341 chars_changed (GtkTextBTree *tree)
343 tree->chars_changed_stamp += 1;
351 _gtk_text_btree_new (GtkTextTagTable *table,
352 GtkTextBuffer *buffer)
355 GtkTextBTreeNode *root_node;
356 GtkTextLine *line, *line2;
358 g_return_val_if_fail (GTK_IS_TEXT_TAG_TABLE (table), NULL);
359 g_return_val_if_fail (GTK_IS_TEXT_BUFFER (buffer), NULL);
362 * The tree will initially have two empty lines. The second line
363 * isn't actually part of the tree's contents, but its presence
364 * makes several operations easier. The tree will have one GtkTextBTreeNode,
365 * which is also the root of the tree.
368 /* Create the root node. */
370 root_node = gtk_text_btree_node_new ();
372 line = gtk_text_line_new ();
373 line2 = gtk_text_line_new ();
375 root_node->parent = NULL;
376 root_node->next = NULL;
377 root_node->summary = NULL;
378 root_node->level = 0;
379 root_node->children.line = line;
380 root_node->num_children = 2;
381 root_node->num_lines = 2;
382 root_node->num_chars = 2;
384 line->parent = root_node;
387 line->segments = _gtk_char_segment_new ("\n", 1);
389 line2->parent = root_node;
391 line2->segments = _gtk_char_segment_new ("\n", 1);
393 /* Create the tree itself */
395 tree = g_new0(GtkTextBTree, 1);
396 tree->root_node = root_node;
400 /* Set these to values that are unlikely to be found
401 * in random memory garbage, and also avoid
402 * duplicates between tree instances.
404 tree->chars_changed_stamp = g_random_int ();
405 tree->segments_changed_stamp = g_random_int ();
407 tree->end_iter_line_stamp = tree->chars_changed_stamp - 1;
408 tree->end_iter_line = NULL;
410 g_object_ref (G_OBJECT (tree->table));
412 tree->tag_changed_handler = g_signal_connect_data (G_OBJECT (tree->table),
414 G_CALLBACK (tag_changed_cb),
418 tree->tag_removed_handler = g_signal_connect_data (G_OBJECT (tree->table),
420 G_CALLBACK (tag_removed_cb),
424 tree->mark_table = g_hash_table_new (g_str_hash, g_str_equal);
425 tree->child_anchor_table = NULL;
427 /* We don't ref the buffer, since the buffer owns us;
428 * we'd have some circularity issues. The buffer always
429 * lasts longer than the BTree
431 tree->buffer = buffer;
435 GtkTextLineSegment *seg;
437 _gtk_text_btree_get_iter_at_line_char (tree, &start, 0, 0);
440 tree->insert_mark = _gtk_text_btree_set_mark (tree,
447 seg = tree->insert_mark->segment;
449 seg->body.mark.not_deleteable = TRUE;
450 seg->body.mark.visible = TRUE;
452 tree->selection_bound_mark = _gtk_text_btree_set_mark (tree,
459 seg = tree->selection_bound_mark->segment;
461 seg->body.mark.not_deleteable = TRUE;
463 g_object_ref (G_OBJECT (tree->insert_mark));
464 g_object_ref (G_OBJECT (tree->selection_bound_mark));
473 _gtk_text_btree_ref (GtkTextBTree *tree)
475 g_return_if_fail (tree != NULL);
476 g_return_if_fail (tree->refcount > 0);
482 mark_destroy_foreach (gpointer key, gpointer value, gpointer user_data)
484 GtkTextLineSegment *seg = value;
486 g_return_if_fail (seg->body.mark.tree == NULL);
488 g_object_unref (G_OBJECT (seg->body.mark.obj));
492 _gtk_text_btree_unref (GtkTextBTree *tree)
494 g_return_if_fail (tree != NULL);
495 g_return_if_fail (tree->refcount > 0);
499 if (tree->refcount == 0)
501 gtk_text_btree_node_destroy (tree, tree->root_node);
503 g_hash_table_foreach (tree->mark_table,
504 mark_destroy_foreach,
506 g_hash_table_destroy (tree->mark_table);
508 g_object_unref (G_OBJECT (tree->insert_mark));
509 g_object_unref (G_OBJECT (tree->selection_bound_mark));
511 g_signal_handler_disconnect (G_OBJECT (tree->table),
512 tree->tag_changed_handler);
514 g_signal_handler_disconnect (G_OBJECT (tree->table),
515 tree->tag_removed_handler);
517 g_object_unref (G_OBJECT (tree->table));
524 _gtk_text_btree_get_buffer (GtkTextBTree *tree)
530 _gtk_text_btree_get_chars_changed_stamp (GtkTextBTree *tree)
532 return tree->chars_changed_stamp;
536 _gtk_text_btree_get_segments_changed_stamp (GtkTextBTree *tree)
538 return tree->segments_changed_stamp;
542 _gtk_text_btree_segments_changed (GtkTextBTree *tree)
544 g_return_if_fail (tree != NULL);
545 segments_changed (tree);
549 * Indexable segment mutation
553 _gtk_text_btree_delete (GtkTextIter *start,
556 GtkTextLineSegment *prev_seg; /* The segment just before the start
557 * of the deletion range. */
558 GtkTextLineSegment *last_seg; /* The segment just after the end
559 * of the deletion range. */
560 GtkTextLineSegment *seg, *next;
561 GtkTextLine *curline;
562 GtkTextBTreeNode *curnode, *node;
564 GtkTextLine *start_line;
565 GtkTextLine *end_line;
566 GtkTextLine *deleted_lines = NULL; /* List of lines we've deleted */
567 gint start_byte_offset;
569 g_return_if_fail (start != NULL);
570 g_return_if_fail (end != NULL);
571 g_return_if_fail (_gtk_text_iter_get_btree (start) ==
572 _gtk_text_iter_get_btree (end));
574 gtk_text_iter_order (start, end);
576 tree = _gtk_text_iter_get_btree (start);
580 * The code below is ugly, but it's needed to make sure there
581 * is always a dummy empty line at the end of the text. If the
582 * final newline of the file (just before the dummy line) is being
583 * deleted, then back up index to just before the newline. If
584 * there is a newline just before the first character being deleted,
585 * then back up the first index too, so that an even number of lines
586 * gets deleted. Furthermore, remove any tags that are present on
587 * the newline that isn't going to be deleted after all (this simulates
588 * deleting the newline and then adding a "clean" one back again).
594 line1 = gtk_text_iter_get_line (start);
595 line2 = gtk_text_iter_get_line (end);
597 if (line2 == _gtk_text_btree_line_count (tree))
601 GtkTextIter orig_end;
604 gtk_text_iter_backward_char (end);
608 if (gtk_text_iter_get_line_offset (start) == 0 &&
611 gtk_text_iter_backward_char (start);
615 tags = _gtk_text_btree_get_tags (end,
623 while (i < array_size)
625 _gtk_text_btree_tag (end, &orig_end, tags[i], FALSE);
635 /* Broadcast the need for redisplay before we break the iterators */
636 _gtk_text_btree_invalidate_region (tree, start, end);
638 /* Save the byte offset so we can reset the iterators */
639 start_byte_offset = gtk_text_iter_get_line_index (start);
641 start_line = _gtk_text_iter_get_text_line (start);
642 end_line = _gtk_text_iter_get_text_line (end);
645 * Split the start and end segments, so we have a place
646 * to insert our new text.
648 * Tricky point: split at end first; otherwise the split
649 * at end may invalidate seg and/or prev_seg. This allows
650 * us to avoid invalidating segments for start.
653 last_seg = gtk_text_line_segment_split (end);
654 if (last_seg != NULL)
655 last_seg = last_seg->next;
657 last_seg = end_line->segments;
659 prev_seg = gtk_text_line_segment_split (start);
660 if (prev_seg != NULL)
662 seg = prev_seg->next;
663 prev_seg->next = last_seg;
667 seg = start_line->segments;
668 start_line->segments = last_seg;
671 /* notify iterators that their segments need recomputation,
672 just for robustness. */
673 segments_changed (tree);
676 * Delete all of the segments between prev_seg and last_seg.
679 curline = start_line;
680 curnode = curline->parent;
681 while (seg != last_seg)
687 GtkTextLine *nextline;
690 * We just ran off the end of a line. First find the
691 * next line, then go back to the old line and delete it
692 * (unless it's the starting line for the range).
695 nextline = _gtk_text_line_next (curline);
696 if (curline != start_line)
698 if (curnode == start_line->parent)
699 start_line->next = curline->next;
701 curnode->children.line = curline->next;
703 for (node = curnode; node != NULL;
706 node->num_lines -= 1;
709 curnode->num_children -= 1;
710 curline->next = deleted_lines;
711 deleted_lines = curline;
715 seg = curline->segments;
718 * If the GtkTextBTreeNode is empty then delete it and its parents,
719 * recursively upwards until a non-empty GtkTextBTreeNode is found.
722 while (curnode->num_children == 0)
724 GtkTextBTreeNode *parent;
726 parent = curnode->parent;
727 if (parent->children.node == curnode)
729 parent->children.node = curnode->next;
733 GtkTextBTreeNode *prevnode = parent->children.node;
734 while (prevnode->next != curnode)
736 prevnode = prevnode->next;
738 prevnode->next = curnode->next;
740 parent->num_children--;
741 gtk_text_btree_node_free_empty (tree, curnode);
744 curnode = curline->parent;
749 char_count = seg->char_count;
751 if ((*seg->type->deleteFunc)(seg, curline, 0) != 0)
754 * This segment refuses to die. Move it to prev_seg and
755 * advance prev_seg if the segment has left gravity.
758 if (prev_seg == NULL)
760 seg->next = start_line->segments;
761 start_line->segments = seg;
765 seg->next = prev_seg->next;
766 prev_seg->next = seg;
768 if (seg->type->leftGravity)
775 /* Segment is gone. Decrement the char count of the node and
777 for (node = curnode; node != NULL;
780 node->num_chars -= char_count;
788 * If the beginning and end of the deletion range are in different
789 * lines, join the two lines together and discard the ending line.
792 if (start_line != end_line)
795 GtkTextBTreeNode *ancestor_node;
797 GtkTextLine *prevline;
799 for (seg = last_seg; seg != NULL;
802 if (seg->type->lineChangeFunc != NULL)
804 (*seg->type->lineChangeFunc)(seg, end_line);
807 curnode = end_line->parent;
808 for (node = curnode; node != NULL;
813 curnode->num_children--;
814 prevline = curnode->children.line;
815 if (prevline == end_line)
817 curnode->children.line = end_line->next;
821 while (prevline->next != end_line)
823 prevline = prevline->next;
825 prevline->next = end_line->next;
827 end_line->next = deleted_lines;
828 deleted_lines = end_line;
830 /* We now fix up the per-view aggregates. We add all the height and
831 * width for the deleted lines to the start line, so that when revalidation
832 * occurs, the correct change in size is seen.
834 ancestor_node = gtk_text_btree_node_common_parent (curnode, start_line->parent);
841 gint deleted_width = 0;
842 gint deleted_height = 0;
844 line = deleted_lines;
847 GtkTextLine *next_line = line->next;
848 ld = _gtk_text_line_get_data (line, view->view_id);
852 deleted_width = MAX (deleted_width, ld->width);
853 deleted_height += ld->height;
857 gtk_text_line_destroy (tree, line);
862 if (deleted_width > 0 || deleted_height > 0)
864 ld = _gtk_text_line_get_data (start_line, view->view_id);
866 /* FIXME: ld is _NOT_ necessarily non-null here, but there is currently
867 * no way to add ld without also validating the node, which would
868 * be improper at this point.
870 /* This assertion does actually fail sometimes, must
871 fix before stable release -hp */
874 ld->width = MAX (deleted_width, ld->width);
875 ld->height += deleted_height;
879 gtk_text_btree_node_check_valid_downward (ancestor_node, view->view_id);
880 if (ancestor_node->parent)
881 gtk_text_btree_node_check_valid_upward (ancestor_node->parent, view->view_id);
886 gtk_text_btree_rebalance (tree, curnode);
890 * Cleanup the segments in the new line.
893 cleanup_line (start_line);
896 * Lastly, rebalance the first GtkTextBTreeNode of the range.
899 gtk_text_btree_rebalance (tree, start_line->parent);
901 /* Notify outstanding iterators that they
903 chars_changed (tree);
904 segments_changed (tree);
906 if (gtk_debug_flags & GTK_DEBUG_TEXT)
907 _gtk_text_btree_check (tree);
909 /* Re-initialize our iterators */
910 _gtk_text_btree_get_iter_at_line (tree, start, start_line, start_byte_offset);
915 _gtk_text_btree_insert (GtkTextIter *iter,
919 GtkTextLineSegment *prev_seg; /* The segment just before the first
920 * new segment (NULL means new segment
921 * is at beginning of line). */
922 GtkTextLineSegment *cur_seg; /* Current segment; new characters
923 * are inserted just after this one.
924 * NULL means insert at beginning of
926 GtkTextLine *line; /* Current line (new segments are
927 * added to this line). */
928 GtkTextLineSegment *seg;
929 GtkTextLine *newline;
930 int chunk_len; /* # characters in current chunk. */
931 gint sol; /* start of line */
932 gint eol; /* Pointer to character just after last
933 * one in current chunk.
935 gint delim; /* index of paragraph delimiter */
936 int line_count_delta; /* Counts change to total number of
940 int char_count_delta; /* change to number of chars */
942 gint start_byte_index;
943 GtkTextLine *start_line;
945 g_return_if_fail (text != NULL);
946 g_return_if_fail (iter != NULL);
951 /* extract iterator info */
952 tree = _gtk_text_iter_get_btree (iter);
953 line = _gtk_text_iter_get_text_line (iter);
955 start_byte_index = gtk_text_iter_get_line_index (iter);
957 /* Get our insertion segment split */
958 prev_seg = gtk_text_line_segment_split (iter);
961 /* Invalidate all iterators */
962 chars_changed (tree);
963 segments_changed (tree);
966 * Chop the text up into lines and create a new segment for
967 * each line, plus a new line for the leftovers from the
973 line_count_delta = 0;
974 char_count_delta = 0;
979 pango_find_paragraph_boundary (text + sol,
984 /* make these relative to the start of the text */
988 g_assert (eol >= sol);
989 g_assert (delim >= sol);
990 g_assert (eol >= delim);
992 g_assert (eol <= len);
994 chunk_len = eol - sol;
996 g_assert (g_utf8_validate (&text[sol], chunk_len, NULL));
997 seg = _gtk_char_segment_new (&text[sol], chunk_len);
999 char_count_delta += seg->char_count;
1001 if (cur_seg == NULL)
1003 seg->next = line->segments;
1004 line->segments = seg;
1008 seg->next = cur_seg->next;
1009 cur_seg->next = seg;
1014 /* chunk didn't end with a paragraph separator */
1015 g_assert (eol == len);
1020 * The chunk ended with a newline, so create a new GtkTextLine
1021 * and move the remainder of the old line to it.
1024 newline = gtk_text_line_new ();
1025 gtk_text_line_set_parent (newline, line->parent);
1026 newline->next = line->next;
1027 line->next = newline;
1028 newline->segments = seg->next;
1036 * Cleanup the starting line for the insertion, plus the ending
1037 * line if it's different.
1040 cleanup_line (start_line);
1041 if (line != start_line)
1043 cleanup_line (line);
1046 post_insert_fixup (tree, line, line_count_delta, char_count_delta);
1048 /* Invalidate our region, and reset the iterator the user
1049 passed in to point to the end of the inserted text. */
1055 _gtk_text_btree_get_iter_at_line (tree,
1061 /* We could almost certainly be more efficient here
1062 by saving the information from the insertion loop
1064 gtk_text_iter_forward_chars (&end, char_count_delta);
1066 _gtk_text_btree_invalidate_region (tree,
1070 /* Convenience for the user */
1076 insert_pixbuf_or_widget_segment (GtkTextIter *iter,
1077 GtkTextLineSegment *seg)
1081 GtkTextLineSegment *prevPtr;
1084 gint start_byte_offset;
1086 line = _gtk_text_iter_get_text_line (iter);
1087 tree = _gtk_text_iter_get_btree (iter);
1088 start_byte_offset = gtk_text_iter_get_line_index (iter);
1090 prevPtr = gtk_text_line_segment_split (iter);
1091 if (prevPtr == NULL)
1093 seg->next = line->segments;
1094 line->segments = seg;
1098 seg->next = prevPtr->next;
1099 prevPtr->next = seg;
1102 post_insert_fixup (tree, line, 0, seg->char_count);
1104 chars_changed (tree);
1105 segments_changed (tree);
1107 /* reset *iter for the user, and invalidate tree nodes */
1109 _gtk_text_btree_get_iter_at_line (tree, &start, line, start_byte_offset);
1112 gtk_text_iter_forward_char (iter); /* skip forward past the segment */
1114 _gtk_text_btree_invalidate_region (tree, &start, iter);
1118 _gtk_text_btree_insert_pixbuf (GtkTextIter *iter,
1121 GtkTextLineSegment *seg;
1123 seg = _gtk_pixbuf_segment_new (pixbuf);
1125 insert_pixbuf_or_widget_segment (iter, seg);
1129 _gtk_text_btree_insert_child_anchor (GtkTextIter *iter,
1130 GtkTextChildAnchor *anchor)
1132 GtkTextLineSegment *seg;
1135 if (anchor->segment != NULL)
1137 g_warning (G_STRLOC": Same child anchor can't be inserted twice");
1141 seg = _gtk_widget_segment_new (anchor);
1143 tree = seg->body.child.tree = _gtk_text_iter_get_btree (iter);
1145 insert_pixbuf_or_widget_segment (iter, seg);
1147 if (tree->child_anchor_table == NULL)
1148 tree->child_anchor_table = g_hash_table_new (NULL, NULL);
1150 g_hash_table_insert (tree->child_anchor_table,
1151 seg->body.child.obj,
1152 seg->body.child.obj);
1156 _gtk_text_btree_unregister_child_anchor (GtkTextChildAnchor *anchor)
1158 GtkTextLineSegment *seg;
1160 seg = anchor->segment;
1162 g_hash_table_remove (seg->body.child.tree->child_anchor_table,
1171 find_line_by_y (GtkTextBTree *tree, BTreeView *view,
1172 GtkTextBTreeNode *node, gint y, gint *line_top,
1173 GtkTextLine *last_line)
1177 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1178 _gtk_text_btree_check (tree);
1180 if (node->level == 0)
1184 line = node->children.line;
1186 while (line != NULL && line != last_line)
1188 GtkTextLineData *ld;
1190 ld = _gtk_text_line_get_data (line, view->view_id);
1194 if (y < (current_y + (ld ? ld->height : 0)))
1197 current_y += ld->height;
1198 *line_top += ld->height;
1207 GtkTextBTreeNode *child;
1209 child = node->children.node;
1211 while (child != NULL)
1216 gtk_text_btree_node_get_size (child, view->view_id,
1219 if (y < (current_y + height))
1220 return find_line_by_y (tree, view, child,
1221 y - current_y, line_top,
1224 current_y += height;
1225 *line_top += height;
1227 child = child->next;
1235 _gtk_text_btree_find_line_by_y (GtkTextBTree *tree,
1242 GtkTextLine *last_line;
1245 view = gtk_text_btree_get_view (tree, view_id);
1246 g_return_val_if_fail (view != NULL, NULL);
1248 last_line = get_last_line (tree);
1250 line = find_line_by_y (tree, view, tree->root_node, ypixel, &line_top,
1254 *line_top_out = line_top;
1260 find_line_top_in_line_list (GtkTextBTree *tree,
1263 GtkTextLine *target_line,
1266 while (line != NULL)
1268 GtkTextLineData *ld;
1270 if (line == target_line)
1273 ld = _gtk_text_line_get_data (line, view->view_id);
1280 g_assert_not_reached (); /* If we get here, our
1281 target line didn't exist
1282 under its parent node */
1287 _gtk_text_btree_find_line_top (GtkTextBTree *tree,
1288 GtkTextLine *target_line,
1295 GtkTextBTreeNode *node;
1297 view = gtk_text_btree_get_view (tree, view_id);
1299 g_return_val_if_fail (view != NULL, 0);
1302 node = target_line->parent;
1303 while (node != NULL)
1305 nodes = g_slist_prepend (nodes, node);
1306 node = node->parent;
1310 while (iter != NULL)
1314 if (node->level == 0)
1316 g_slist_free (nodes);
1317 return find_line_top_in_line_list (tree, view,
1318 node->children.line,
1323 GtkTextBTreeNode *child;
1324 GtkTextBTreeNode *target_node;
1326 g_assert (iter->next != NULL); /* not at level 0 */
1327 target_node = iter->next->data;
1329 child = node->children.node;
1331 while (child != NULL)
1336 if (child == target_node)
1340 gtk_text_btree_node_get_size (child, view->view_id,
1344 child = child->next;
1346 g_assert (child != NULL); /* should have broken out before we
1350 iter = g_slist_next (iter);
1353 g_assert_not_reached (); /* we return when we find the target line */
1358 _gtk_text_btree_add_view (GtkTextBTree *tree,
1359 GtkTextLayout *layout)
1362 GtkTextLine *last_line;
1363 GtkTextLineData *line_data;
1365 g_return_if_fail (tree != NULL);
1367 view = g_new (BTreeView, 1);
1369 view->view_id = layout;
1370 view->layout = layout;
1372 view->next = tree->views;
1377 /* The last line in the buffer has identity values for the per-view
1378 * data so that we can avoid special case checks for it in a large
1381 last_line = get_last_line (tree);
1383 line_data = g_new (GtkTextLineData, 1);
1384 line_data->view_id = layout;
1385 line_data->next = NULL;
1386 line_data->width = 0;
1387 line_data->height = 0;
1388 line_data->valid = TRUE;
1390 _gtk_text_line_add_data (last_line, line_data);
1394 _gtk_text_btree_remove_view (GtkTextBTree *tree,
1398 GtkTextLine *last_line;
1399 GtkTextLineData *line_data;
1401 g_return_if_fail (tree != NULL);
1405 while (view != NULL)
1407 if (view->view_id == view_id)
1413 g_return_if_fail (view != NULL);
1416 view->next->prev = view->prev;
1419 view->prev->next = view->next;
1421 if (view == tree->views)
1422 tree->views = view->next;
1424 /* Remove the line data for the last line which we added ourselves.
1425 * (Do this first, so that we don't try to call the view's line data destructor on it.)
1427 last_line = get_last_line (tree);
1428 line_data = _gtk_text_line_remove_data (last_line, view_id);
1431 gtk_text_btree_node_remove_view (view, tree->root_node, view_id);
1437 _gtk_text_btree_invalidate_region (GtkTextBTree *tree,
1438 const GtkTextIter *start,
1439 const GtkTextIter *end)
1445 while (view != NULL)
1447 gtk_text_layout_invalidate (view->layout, start, end);
1454 _gtk_text_btree_get_view_size (GtkTextBTree *tree,
1459 g_return_if_fail (tree != NULL);
1460 g_return_if_fail (view_id != NULL);
1462 gtk_text_btree_node_get_size (tree->root_node, view_id,
1477 iter_stack_new (void)
1480 stack = g_new (IterStack, 1);
1481 stack->iters = NULL;
1488 iter_stack_push (IterStack *stack, const GtkTextIter *iter)
1491 if (stack->count > stack->alloced)
1493 stack->alloced = stack->count*2;
1494 stack->iters = g_realloc (stack->iters,
1495 stack->alloced*sizeof (GtkTextIter));
1497 stack->iters[stack->count-1] = *iter;
1501 iter_stack_pop (IterStack *stack, GtkTextIter *iter)
1503 if (stack->count == 0)
1508 *iter = stack->iters[stack->count];
1514 iter_stack_free (IterStack *stack)
1516 g_free (stack->iters);
1521 iter_stack_invert (IterStack *stack)
1523 if (stack->count > 0)
1526 guint j = stack->count - 1;
1531 tmp = stack->iters[i];
1532 stack->iters[i] = stack->iters[j];
1533 stack->iters[j] = tmp;
1542 queue_tag_redisplay (GtkTextBTree *tree,
1544 const GtkTextIter *start,
1545 const GtkTextIter *end)
1547 if (_gtk_text_tag_affects_size (tag))
1549 _gtk_text_btree_invalidate_region (tree, start, end);
1551 else if (_gtk_text_tag_affects_nonsize_appearance (tag))
1553 /* We only need to queue a redraw, not a relayout */
1554 redisplay_region (tree, start, end);
1557 /* We don't need to do anything if the tag doesn't affect display */
1561 _gtk_text_btree_tag (const GtkTextIter *start_orig,
1562 const GtkTextIter *end_orig,
1566 GtkTextLineSegment *seg, *prev;
1567 GtkTextLine *cleanupline;
1568 gboolean toggled_on;
1569 GtkTextLine *start_line;
1570 GtkTextLine *end_line;
1572 GtkTextIter start, end;
1575 GtkTextTagInfo *info;
1577 g_return_if_fail (start_orig != NULL);
1578 g_return_if_fail (end_orig != NULL);
1579 g_return_if_fail (GTK_IS_TEXT_TAG (tag));
1580 g_return_if_fail (_gtk_text_iter_get_btree (start_orig) ==
1581 _gtk_text_iter_get_btree (end_orig));
1582 g_return_if_fail (tag->table == _gtk_text_iter_get_btree (start_orig)->table);
1585 printf ("%s tag %s from %d to %d\n",
1586 add ? "Adding" : "Removing",
1588 gtk_text_buffer_get_offset (start_orig),
1589 gtk_text_buffer_get_offset (end_orig));
1592 if (gtk_text_iter_equal (start_orig, end_orig))
1595 start = *start_orig;
1598 gtk_text_iter_order (&start, &end);
1600 tree = _gtk_text_iter_get_btree (&start);
1602 queue_tag_redisplay (tree, tag, &start, &end);
1604 info = gtk_text_btree_get_tag_info (tree, tag);
1606 start_line = _gtk_text_iter_get_text_line (&start);
1607 end_line = _gtk_text_iter_get_text_line (&end);
1609 /* Find all tag toggles in the region; we are going to delete them.
1610 We need to find them in advance, because
1611 forward_find_tag_toggle () won't work once we start playing around
1613 stack = iter_stack_new ();
1616 /* forward_to_tag_toggle() skips a toggle at the start iterator,
1617 * which is deliberate - we don't want to delete a toggle at the
1620 while (gtk_text_iter_forward_to_tag_toggle (&iter, tag))
1622 if (gtk_text_iter_compare (&iter, &end) >= 0)
1625 iter_stack_push (stack, &iter);
1628 /* We need to traverse the toggles in order. */
1629 iter_stack_invert (stack);
1632 * See whether the tag is present at the start of the range. If
1633 * the state doesn't already match what we want then add a toggle
1637 toggled_on = gtk_text_iter_has_tag (&start, tag);
1638 if ( (add && !toggled_on) ||
1639 (!add && toggled_on) )
1641 /* This could create a second toggle at the start position;
1642 cleanup_line () will remove it if so. */
1643 seg = _gtk_toggle_segment_new (info, add);
1645 prev = gtk_text_line_segment_split (&start);
1648 seg->next = start_line->segments;
1649 start_line->segments = seg;
1653 seg->next = prev->next;
1657 /* cleanup_line adds the new toggle to the node counts. */
1659 printf ("added toggle at start\n");
1661 /* we should probably call segments_changed, but in theory
1662 any still-cached segments in the iters we are about to
1663 use are still valid, since they're in front
1669 * Scan the range of characters and delete any internal tag
1670 * transitions. Keep track of what the old state was at the end
1671 * of the range, and add a toggle there if it's needed.
1675 cleanupline = start_line;
1676 while (iter_stack_pop (stack, &iter))
1678 GtkTextLineSegment *indexable_seg;
1681 line = _gtk_text_iter_get_text_line (&iter);
1682 seg = _gtk_text_iter_get_any_segment (&iter);
1683 indexable_seg = _gtk_text_iter_get_indexable_segment (&iter);
1685 g_assert (seg != NULL);
1686 g_assert (indexable_seg != NULL);
1687 g_assert (seg != indexable_seg);
1689 prev = line->segments;
1691 /* Find the segment that actually toggles this tag. */
1692 while (seg != indexable_seg)
1694 g_assert (seg != NULL);
1695 g_assert (indexable_seg != NULL);
1696 g_assert (seg != indexable_seg);
1698 if ( (seg->type == >k_text_toggle_on_type ||
1699 seg->type == >k_text_toggle_off_type) &&
1700 (seg->body.toggle.info == info) )
1706 g_assert (seg != NULL);
1707 g_assert (indexable_seg != NULL);
1709 g_assert (seg != indexable_seg); /* If this happens, then
1710 forward_to_tag_toggle was
1712 g_assert (seg->body.toggle.info->tag == tag);
1714 /* If this happens, when previously tagging we didn't merge
1715 overlapping tags. */
1716 g_assert ( (toggled_on && seg->type == >k_text_toggle_off_type) ||
1717 (!toggled_on && seg->type == >k_text_toggle_on_type) );
1719 toggled_on = !toggled_on;
1722 printf ("deleting %s toggle\n",
1723 seg->type == >k_text_toggle_on_type ? "on" : "off");
1725 /* Remove toggle segment from the list. */
1728 line->segments = seg->next;
1732 while (prev->next != seg)
1736 prev->next = seg->next;
1739 /* Inform iterators we've hosed them. This actually reflects a
1740 bit of inefficiency; if you have the same tag toggled on and
1741 off a lot in a single line, we keep having the rescan from
1742 the front of the line. Of course we have to do that to get
1743 "prev" anyway, but here we are doing it an additional
1745 segments_changed (tree);
1747 /* Update node counts */
1748 if (seg->body.toggle.inNodeCounts)
1750 _gtk_change_node_toggle_count (line->parent,
1752 seg->body.toggle.inNodeCounts = FALSE;
1757 /* We only clean up lines when we're done with them, saves some
1758 gratuitous line-segment-traversals */
1760 if (cleanupline != line)
1762 cleanup_line (cleanupline);
1767 iter_stack_free (stack);
1769 /* toggled_on now reflects the toggle state _just before_ the
1770 end iterator. The end iterator could already have a toggle
1771 on or a toggle off. */
1772 if ( (add && !toggled_on) ||
1773 (!add && toggled_on) )
1775 /* This could create a second toggle at the start position;
1776 cleanup_line () will remove it if so. */
1778 seg = _gtk_toggle_segment_new (info, !add);
1780 prev = gtk_text_line_segment_split (&end);
1783 seg->next = end_line->segments;
1784 end_line->segments = seg;
1788 seg->next = prev->next;
1791 /* cleanup_line adds the new toggle to the node counts. */
1792 g_assert (seg->body.toggle.inNodeCounts == FALSE);
1794 printf ("added toggle at end\n");
1799 * Cleanup cleanupline and the last line of the range, if
1800 * these are different.
1803 cleanup_line (cleanupline);
1804 if (cleanupline != end_line)
1806 cleanup_line (end_line);
1809 segments_changed (tree);
1811 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1812 _gtk_text_btree_check (tree);
1821 _gtk_text_btree_get_line (GtkTextBTree *tree,
1823 gint *real_line_number)
1825 GtkTextBTreeNode *node;
1830 line_count = _gtk_text_btree_line_count (tree);
1832 if (line_number < 0)
1834 line_number = line_count;
1836 else if (line_number > line_count)
1838 line_number = line_count;
1841 if (real_line_number)
1842 *real_line_number = line_number;
1844 node = tree->root_node;
1845 lines_left = line_number;
1848 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1852 while (node->level != 0)
1854 for (node = node->children.node;
1855 node->num_lines <= lines_left;
1861 g_error ("gtk_text_btree_find_line ran out of GtkTextBTreeNodes");
1864 lines_left -= node->num_lines;
1869 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1872 for (line = node->children.line; lines_left > 0;
1878 g_error ("gtk_text_btree_find_line ran out of lines");
1887 _gtk_text_btree_get_line_at_char (GtkTextBTree *tree,
1889 gint *line_start_index,
1890 gint *real_char_index)
1892 GtkTextBTreeNode *node;
1894 GtkTextLineSegment *seg;
1899 node = tree->root_node;
1901 /* Clamp to valid indexes (-1 is magic for "highest index") */
1902 if (char_index < 0 || char_index >= node->num_chars)
1904 char_index = node->num_chars - 1;
1907 *real_char_index = char_index;
1910 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1914 chars_left = char_index;
1915 while (node->level != 0)
1917 for (node = node->children.node;
1918 chars_left >= node->num_chars;
1921 chars_left -= node->num_chars;
1923 g_assert (chars_left >= 0);
1927 if (chars_left == 0)
1929 /* Start of a line */
1931 *line_start_index = char_index;
1932 return node->children.line;
1936 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1942 for (line = node->children.line; line != NULL; line = line->next)
1944 seg = line->segments;
1947 if (chars_in_line + seg->char_count > chars_left)
1948 goto found; /* found our line/segment */
1950 chars_in_line += seg->char_count;
1955 chars_left -= chars_in_line;
1963 g_assert (line != NULL); /* hosage, ran out of lines */
1964 g_assert (seg != NULL);
1966 *line_start_index = char_index - chars_left;
1971 _gtk_text_btree_get_tags (const GtkTextIter *iter,
1974 GtkTextBTreeNode *node;
1975 GtkTextLine *siblingline;
1976 GtkTextLineSegment *seg;
1977 int src, dst, index;
1983 #define NUM_TAG_INFOS 10
1985 line = _gtk_text_iter_get_text_line (iter);
1986 tree = _gtk_text_iter_get_btree (iter);
1987 byte_index = gtk_text_iter_get_line_index (iter);
1989 tagInfo.numTags = 0;
1990 tagInfo.arraySize = NUM_TAG_INFOS;
1991 tagInfo.tags = g_new (GtkTextTag*, NUM_TAG_INFOS);
1992 tagInfo.counts = g_new (int, NUM_TAG_INFOS);
1995 * Record tag toggles within the line of indexPtr but preceding
1996 * indexPtr. Note that if this loop segfaults, your
1997 * byte_index probably points past the sum of all
1998 * seg->byte_count */
2000 for (index = 0, seg = line->segments;
2001 (index + seg->byte_count) <= byte_index;
2002 index += seg->byte_count, seg = seg->next)
2004 if ((seg->type == >k_text_toggle_on_type)
2005 || (seg->type == >k_text_toggle_off_type))
2007 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2012 * Record toggles for tags in lines that are predecessors of
2013 * line but under the same level-0 GtkTextBTreeNode.
2016 for (siblingline = line->parent->children.line;
2017 siblingline != line;
2018 siblingline = siblingline->next)
2020 for (seg = siblingline->segments; seg != NULL;
2023 if ((seg->type == >k_text_toggle_on_type)
2024 || (seg->type == >k_text_toggle_off_type))
2026 inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2032 * For each GtkTextBTreeNode in the ancestry of this line, record tag
2033 * toggles for all siblings that precede that GtkTextBTreeNode.
2036 for (node = line->parent; node->parent != NULL;
2037 node = node->parent)
2039 GtkTextBTreeNode *siblingPtr;
2042 for (siblingPtr = node->parent->children.node;
2043 siblingPtr != node; siblingPtr = siblingPtr->next)
2045 for (summary = siblingPtr->summary; summary != NULL;
2046 summary = summary->next)
2048 if (summary->toggle_count & 1)
2050 inc_count (summary->info->tag, summary->toggle_count,
2058 * Go through the tag information and squash out all of the tags
2059 * that have even toggle counts (these tags exist before the point
2060 * of interest, but not at the desired character itself).
2063 for (src = 0, dst = 0; src < tagInfo.numTags; src++)
2065 if (tagInfo.counts[src] & 1)
2067 g_assert (GTK_IS_TEXT_TAG (tagInfo.tags[src]));
2068 tagInfo.tags[dst] = tagInfo.tags[src];
2074 g_free (tagInfo.counts);
2077 g_free (tagInfo.tags);
2080 return tagInfo.tags;
2084 copy_segment (GString *string,
2085 gboolean include_hidden,
2086 gboolean include_nonchars,
2087 const GtkTextIter *start,
2088 const GtkTextIter *end)
2090 GtkTextLineSegment *end_seg;
2091 GtkTextLineSegment *seg;
2093 if (gtk_text_iter_equal (start, end))
2096 seg = _gtk_text_iter_get_indexable_segment (start);
2097 end_seg = _gtk_text_iter_get_indexable_segment (end);
2099 if (seg->type == >k_text_char_type)
2101 gboolean copy = TRUE;
2102 gint copy_bytes = 0;
2103 gint copy_start = 0;
2105 /* Don't copy if we're invisible; segments are invisible/not
2106 as a whole, no need to check each char */
2107 if (!include_hidden &&
2108 _gtk_text_btree_char_is_invisible (start))
2111 /* printf (" <invisible>\n"); */
2114 copy_start = _gtk_text_iter_get_segment_byte (start);
2118 /* End is in the same segment; need to copy fewer bytes. */
2119 gint end_byte = _gtk_text_iter_get_segment_byte (end);
2121 copy_bytes = end_byte - copy_start;
2124 copy_bytes = seg->byte_count - copy_start;
2126 g_assert (copy_bytes != 0); /* Due to iter equality check at
2127 front of this function. */
2131 g_assert ((copy_start + copy_bytes) <= seg->byte_count);
2133 g_string_append_len (string,
2134 seg->body.chars + copy_start,
2138 /* printf (" :%s\n", string->str); */
2140 else if (seg->type == >k_text_pixbuf_type ||
2141 seg->type == >k_text_child_type)
2143 gboolean copy = TRUE;
2145 if (!include_nonchars)
2149 else if (!include_hidden &&
2150 _gtk_text_btree_char_is_invisible (start))
2157 g_string_append_len (string,
2158 gtk_text_unknown_char_utf8,
2166 _gtk_text_btree_get_text (const GtkTextIter *start_orig,
2167 const GtkTextIter *end_orig,
2168 gboolean include_hidden,
2169 gboolean include_nonchars)
2171 GtkTextLineSegment *seg;
2172 GtkTextLineSegment *end_seg;
2180 g_return_val_if_fail (start_orig != NULL, NULL);
2181 g_return_val_if_fail (end_orig != NULL, NULL);
2182 g_return_val_if_fail (_gtk_text_iter_get_btree (start_orig) ==
2183 _gtk_text_iter_get_btree (end_orig), NULL);
2185 start = *start_orig;
2188 gtk_text_iter_order (&start, &end);
2190 retval = g_string_new ("");
2192 tree = _gtk_text_iter_get_btree (&start);
2194 end_seg = _gtk_text_iter_get_indexable_segment (&end);
2196 seg = _gtk_text_iter_get_indexable_segment (&iter);
2197 while (seg != end_seg)
2199 copy_segment (retval, include_hidden, include_nonchars,
2202 _gtk_text_iter_forward_indexable_segment (&iter);
2204 seg = _gtk_text_iter_get_indexable_segment (&iter);
2207 copy_segment (retval, include_hidden, include_nonchars, &iter, &end);
2210 g_string_free (retval, FALSE);
2215 _gtk_text_btree_line_count (GtkTextBTree *tree)
2217 /* Subtract bogus line at the end; we return a count
2219 return tree->root_node->num_lines - 1;
2223 _gtk_text_btree_char_count (GtkTextBTree *tree)
2225 /* Exclude newline in bogus last line */
2226 return tree->root_node->num_chars - 1;
2229 #define LOTSA_TAGS 1000
2231 _gtk_text_btree_char_is_invisible (const GtkTextIter *iter)
2233 gboolean invisible = FALSE; /* if nobody says otherwise, it's visible */
2235 int deftagCnts[LOTSA_TAGS];
2236 int *tagCnts = deftagCnts;
2237 GtkTextTag *deftags[LOTSA_TAGS];
2238 GtkTextTag **tags = deftags;
2240 GtkTextBTreeNode *node;
2241 GtkTextLine *siblingline;
2242 GtkTextLineSegment *seg;
2249 line = _gtk_text_iter_get_text_line (iter);
2250 tree = _gtk_text_iter_get_btree (iter);
2251 byte_index = gtk_text_iter_get_line_index (iter);
2253 numTags = gtk_text_tag_table_size (tree->table);
2255 /* almost always avoid malloc, so stay out of system calls */
2256 if (LOTSA_TAGS < numTags)
2258 tagCnts = g_new (int, numTags);
2259 tags = g_new (GtkTextTag*, numTags);
2262 for (i=0; i<numTags; i++)
2268 * Record tag toggles within the line of indexPtr but preceding
2272 for (index = 0, seg = line->segments;
2273 (index + seg->byte_count) <= byte_index; /* segfault here means invalid index */
2274 index += seg->byte_count, seg = seg->next)
2276 if ((seg->type == >k_text_toggle_on_type)
2277 || (seg->type == >k_text_toggle_off_type))
2279 tag = seg->body.toggle.info->tag;
2280 if (tag->invisible_set && tag->values->invisible)
2282 tags[tag->priority] = tag;
2283 tagCnts[tag->priority]++;
2289 * Record toggles for tags in lines that are predecessors of
2290 * line but under the same level-0 GtkTextBTreeNode.
2293 for (siblingline = line->parent->children.line;
2294 siblingline != line;
2295 siblingline = siblingline->next)
2297 for (seg = siblingline->segments; seg != NULL;
2300 if ((seg->type == >k_text_toggle_on_type)
2301 || (seg->type == >k_text_toggle_off_type))
2303 tag = seg->body.toggle.info->tag;
2304 if (tag->invisible_set && tag->values->invisible)
2306 tags[tag->priority] = tag;
2307 tagCnts[tag->priority]++;
2314 * For each GtkTextBTreeNode in the ancestry of this line, record tag toggles
2315 * for all siblings that precede that GtkTextBTreeNode.
2318 for (node = line->parent; node->parent != NULL;
2319 node = node->parent)
2321 GtkTextBTreeNode *siblingPtr;
2324 for (siblingPtr = node->parent->children.node;
2325 siblingPtr != node; siblingPtr = siblingPtr->next)
2327 for (summary = siblingPtr->summary; summary != NULL;
2328 summary = summary->next)
2330 if (summary->toggle_count & 1)
2332 tag = summary->info->tag;
2333 if (tag->invisible_set && tag->values->invisible)
2335 tags[tag->priority] = tag;
2336 tagCnts[tag->priority] += summary->toggle_count;
2344 * Now traverse from highest priority to lowest,
2345 * take invisible value from first odd count (= on)
2348 for (i = numTags-1; i >=0; i--)
2352 /* FIXME not sure this should be if 0 */
2354 #ifndef ALWAYS_SHOW_SELECTION
2355 /* who would make the selection invisible? */
2356 if ((tag == tkxt->seltag)
2357 && !(tkxt->flags & GOT_FOCUS))
2363 invisible = tags[i]->values->invisible;
2368 if (LOTSA_TAGS < numTags)
2383 redisplay_region (GtkTextBTree *tree,
2384 const GtkTextIter *start,
2385 const GtkTextIter *end)
2388 GtkTextLine *start_line, *end_line;
2390 if (gtk_text_iter_compare (start, end) > 0)
2392 const GtkTextIter *tmp = start;
2397 start_line = _gtk_text_iter_get_text_line (start);
2398 end_line = _gtk_text_iter_get_text_line (end);
2401 while (view != NULL)
2403 gint start_y, end_y;
2404 GtkTextLineData *ld;
2406 start_y = _gtk_text_btree_find_line_top (tree, start_line, view->view_id);
2408 if (end_line == start_line)
2411 end_y = _gtk_text_btree_find_line_top (tree, end_line, view->view_id);
2413 ld = _gtk_text_line_get_data (end_line, view->view_id);
2415 end_y += ld->height;
2417 gtk_text_layout_changed (view->layout, start_y,
2426 redisplay_mark (GtkTextLineSegment *mark)
2431 _gtk_text_btree_get_iter_at_mark (mark->body.mark.tree,
2433 mark->body.mark.obj);
2436 gtk_text_iter_forward_char (&end);
2438 _gtk_text_btree_invalidate_region (mark->body.mark.tree,
2443 redisplay_mark_if_visible (GtkTextLineSegment *mark)
2445 if (!mark->body.mark.visible)
2448 redisplay_mark (mark);
2452 ensure_not_off_end (GtkTextBTree *tree,
2453 GtkTextLineSegment *mark,
2456 if (gtk_text_iter_get_line (iter) ==
2457 _gtk_text_btree_line_count (tree))
2458 gtk_text_iter_backward_char (iter);
2461 static GtkTextLineSegment*
2462 real_set_mark (GtkTextBTree *tree,
2463 GtkTextMark *existing_mark,
2465 gboolean left_gravity,
2466 const GtkTextIter *where,
2467 gboolean should_exist,
2468 gboolean redraw_selections)
2470 GtkTextLineSegment *mark;
2473 g_return_val_if_fail (tree != NULL, NULL);
2474 g_return_val_if_fail (where != NULL, NULL);
2475 g_return_val_if_fail (_gtk_text_iter_get_btree (where) == tree, NULL);
2478 mark = existing_mark->segment;
2479 else if (name != NULL)
2480 mark = g_hash_table_lookup (tree->mark_table,
2485 if (should_exist && mark == NULL)
2487 g_warning ("No mark `%s' exists!", name);
2491 /* OK if !should_exist and it does already exist, in that case
2497 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2498 _gtk_text_iter_check (&iter);
2502 if (redraw_selections &&
2503 (mark == tree->insert_mark->segment ||
2504 mark == tree->selection_bound_mark->segment))
2506 GtkTextIter old_pos;
2508 _gtk_text_btree_get_iter_at_mark (tree, &old_pos,
2509 mark->body.mark.obj);
2510 redisplay_region (tree, &old_pos, where);
2514 * don't let visible marks be after the final newline of the
2518 if (mark->body.mark.visible)
2520 ensure_not_off_end (tree, mark, &iter);
2523 /* Redraw the mark's old location. */
2524 redisplay_mark_if_visible (mark);
2526 /* Unlink mark from its current location.
2527 This could hose our iterator... */
2528 gtk_text_btree_unlink_segment (tree, mark,
2529 mark->body.mark.line);
2530 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2531 g_assert (mark->body.mark.line == _gtk_text_iter_get_text_line (&iter));
2533 segments_changed (tree); /* make sure the iterator recomputes its
2538 mark = _gtk_mark_segment_new (tree,
2542 mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2544 if (mark->body.mark.name)
2545 g_hash_table_insert (tree->mark_table,
2546 mark->body.mark.name,
2550 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2551 _gtk_text_iter_check (&iter);
2553 /* Link mark into new location */
2554 gtk_text_btree_link_segment (mark, &iter);
2556 /* Invalidate some iterators. */
2557 segments_changed (tree);
2560 * update the screen at the mark's new location.
2563 redisplay_mark_if_visible (mark);
2565 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2566 _gtk_text_iter_check (&iter);
2568 if (gtk_debug_flags & GTK_DEBUG_TEXT)
2569 _gtk_text_btree_check (tree);
2576 _gtk_text_btree_set_mark (GtkTextBTree *tree,
2577 GtkTextMark *existing_mark,
2579 gboolean left_gravity,
2580 const GtkTextIter *iter,
2581 gboolean should_exist)
2583 GtkTextLineSegment *seg;
2585 seg = real_set_mark (tree, existing_mark,
2586 name, left_gravity, iter, should_exist,
2589 return seg ? seg->body.mark.obj : NULL;
2593 _gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2597 GtkTextIter tmp_start, tmp_end;
2599 _gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2601 _gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2602 tree->selection_bound_mark);
2604 if (gtk_text_iter_equal (&tmp_start, &tmp_end))
2616 gtk_text_iter_order (&tmp_start, &tmp_end);
2629 _gtk_text_btree_place_cursor (GtkTextBTree *tree,
2630 const GtkTextIter *iter)
2632 GtkTextIter start, end;
2634 if (_gtk_text_btree_get_selection_bounds (tree, &start, &end))
2635 redisplay_region (tree, &start, &end);
2637 /* Move insert AND selection_bound before we redisplay */
2638 real_set_mark (tree, tree->insert_mark,
2639 "insert", FALSE, iter, TRUE, FALSE);
2640 real_set_mark (tree, tree->selection_bound_mark,
2641 "selection_bound", FALSE, iter, TRUE, FALSE);
2645 _gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2650 g_return_if_fail (tree != NULL);
2651 g_return_if_fail (name != NULL);
2653 mark = g_hash_table_lookup (tree->mark_table,
2656 _gtk_text_btree_remove_mark (tree, mark);
2660 _gtk_text_btree_remove_mark (GtkTextBTree *tree,
2663 GtkTextLineSegment *segment;
2665 g_return_if_fail (mark != NULL);
2666 g_return_if_fail (tree != NULL);
2668 segment = mark->segment;
2670 if (segment->body.mark.not_deleteable)
2672 g_warning ("Can't delete special mark `%s'", segment->body.mark.name);
2676 /* This calls cleanup_line and segments_changed */
2677 gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2679 if (segment->body.mark.name)
2680 g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2682 /* Remove the ref on the mark that belonged to the segment. */
2683 g_object_unref (G_OBJECT (mark));
2685 segment->body.mark.tree = NULL;
2686 segment->body.mark.line = NULL;
2690 _gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2691 GtkTextMark *segment)
2693 return segment == tree->insert_mark;
2697 _gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2698 GtkTextMark *segment)
2700 return segment == tree->selection_bound_mark;
2704 _gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2707 GtkTextLineSegment *seg;
2709 g_return_val_if_fail (tree != NULL, NULL);
2710 g_return_val_if_fail (name != NULL, NULL);
2712 seg = g_hash_table_lookup (tree->mark_table, name);
2714 return seg ? seg->body.mark.obj : NULL;
2718 * gtk_text_mark_set_visible:
2719 * @mark: a #GtkTextMark
2720 * @setting: visibility of mark
2722 * Sets the visibility of @mark; the insertion point is normally
2723 * visible, i.e. you can see it as a vertical bar. Also, the text
2724 * widget uses a visible mark to indicate where a drop will occur when
2725 * dragging-and-dropping text. Most other marks are not visible.
2726 * Marks are not visible by default.
2730 gtk_text_mark_set_visible (GtkTextMark *mark,
2733 GtkTextLineSegment *seg;
2735 g_return_if_fail (mark != NULL);
2737 seg = mark->segment;
2739 if (seg->body.mark.visible == setting)
2743 seg->body.mark.visible = setting;
2745 redisplay_mark (seg);
2750 _gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
2753 GtkTextBTreeNode *node;
2754 GtkTextTagInfo *info;
2756 g_return_val_if_fail (tree != NULL, NULL);
2760 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2765 if (info->tag_root == NULL)
2768 node = info->tag_root;
2770 /* We know the tag root has instances of the given
2773 continue_outer_loop:
2774 g_assert (node != NULL);
2775 while (node->level > 0)
2777 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2778 node = node->children.node;
2779 while (node != NULL)
2781 if (gtk_text_btree_node_has_tag (node, tag))
2782 goto continue_outer_loop;
2786 g_assert (node != NULL);
2789 g_assert (node != NULL); /* The tag summaries said some node had
2792 g_assert (node->level == 0);
2794 return node->children.line;
2798 /* Looking for any tag at all (tag == NULL).
2799 Unfortunately this can't be done in a simple and efficient way
2800 right now; so I'm just going to return the
2801 first line in the btree. FIXME */
2802 return _gtk_text_btree_get_line (tree, 0, NULL);
2807 _gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
2810 GtkTextBTreeNode *node;
2811 GtkTextBTreeNode *last_node;
2813 GtkTextTagInfo *info;
2815 g_return_val_if_fail (tree != NULL, NULL);
2819 info = gtk_text_btree_get_existing_tag_info (tree, tag);
2821 if (info->tag_root == NULL)
2824 node = info->tag_root;
2825 /* We know the tag root has instances of the given
2828 while (node->level > 0)
2830 g_assert (node != NULL); /* Failure probably means bad tag summaries. */
2832 node = node->children.node;
2833 while (node != NULL)
2835 if (gtk_text_btree_node_has_tag (node, tag))
2843 g_assert (node != NULL); /* The tag summaries said some node had
2846 g_assert (node->level == 0);
2848 /* Find the last line in this node */
2849 line = node->children.line;
2850 while (line->next != NULL)
2857 /* This search can't be done efficiently at the moment,
2858 at least not without complexity.
2859 So, we just return the last line.
2861 return _gtk_text_btree_get_line (tree, -1, NULL);
2871 _gtk_text_line_get_number (GtkTextLine *line)
2874 GtkTextBTreeNode *node, *parent, *node2;
2878 * First count how many lines precede this one in its level-0
2882 node = line->parent;
2884 for (line2 = node->children.line; line2 != line;
2885 line2 = line2->next)
2889 g_error ("gtk_text_btree_line_number couldn't find line");
2895 * Now work up through the levels of the tree one at a time,
2896 * counting how many lines are in GtkTextBTreeNodes preceding the current
2900 for (parent = node->parent ; parent != NULL;
2901 node = parent, parent = parent->parent)
2903 for (node2 = parent->children.node; node2 != node;
2904 node2 = node2->next)
2908 g_error ("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
2910 index += node2->num_lines;
2916 static GtkTextLineSegment*
2917 find_toggle_segment_before_char (GtkTextLine *line,
2921 GtkTextLineSegment *seg;
2922 GtkTextLineSegment *toggle_seg;
2927 seg = line->segments;
2928 while ( (index + seg->char_count) <= char_in_line )
2930 if (((seg->type == >k_text_toggle_on_type)
2931 || (seg->type == >k_text_toggle_off_type))
2932 && (seg->body.toggle.info->tag == tag))
2935 index += seg->char_count;
2942 static GtkTextLineSegment*
2943 find_toggle_segment_before_byte (GtkTextLine *line,
2947 GtkTextLineSegment *seg;
2948 GtkTextLineSegment *toggle_seg;
2953 seg = line->segments;
2954 while ( (index + seg->byte_count) <= byte_in_line )
2956 if (((seg->type == >k_text_toggle_on_type)
2957 || (seg->type == >k_text_toggle_off_type))
2958 && (seg->body.toggle.info->tag == tag))
2961 index += seg->byte_count;
2969 find_toggle_outside_current_line (GtkTextLine *line,
2973 GtkTextBTreeNode *node;
2974 GtkTextLine *sibling_line;
2975 GtkTextLineSegment *seg;
2976 GtkTextLineSegment *toggle_seg;
2978 GtkTextTagInfo *info = NULL;
2981 * No toggle in this line. Look for toggles for the tag in lines
2982 * that are predecessors of line but under the same
2983 * level-0 GtkTextBTreeNode.
2986 sibling_line = line->parent->children.line;
2987 while (sibling_line != line)
2989 seg = sibling_line->segments;
2992 if (((seg->type == >k_text_toggle_on_type)
2993 || (seg->type == >k_text_toggle_off_type))
2994 && (seg->body.toggle.info->tag == tag))
3000 sibling_line = sibling_line->next;
3003 if (toggle_seg != NULL)
3004 return (toggle_seg->type == >k_text_toggle_on_type);
3007 * No toggle in this GtkTextBTreeNode. Scan upwards through the ancestors of
3008 * this GtkTextBTreeNode, counting the number of toggles of the given tag in
3009 * siblings that precede that GtkTextBTreeNode.
3012 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3018 node = line->parent;
3019 while (node->parent != NULL)
3021 GtkTextBTreeNode *sibling_node;
3023 sibling_node = node->parent->children.node;
3024 while (sibling_node != node)
3028 summary = sibling_node->summary;
3029 while (summary != NULL)
3031 if (summary->info == info)
3032 toggles += summary->toggle_count;
3034 summary = summary->next;
3037 sibling_node = sibling_node->next;
3040 if (node == info->tag_root)
3043 node = node->parent;
3047 * An odd number of toggles means that the tag is present at the
3051 return (toggles & 1) != 0;
3054 /* FIXME this function is far too slow, for no good reason. */
3056 _gtk_text_line_char_has_tag (GtkTextLine *line,
3061 GtkTextLineSegment *toggle_seg;
3063 g_return_val_if_fail (line != NULL, FALSE);
3066 * Check for toggles for the tag in the line but before
3067 * the char. If there is one, its type indicates whether or
3068 * not the character is tagged.
3071 toggle_seg = find_toggle_segment_before_char (line, char_in_line, tag);
3073 if (toggle_seg != NULL)
3074 return (toggle_seg->type == >k_text_toggle_on_type);
3076 return find_toggle_outside_current_line (line, tree, tag);
3080 _gtk_text_line_byte_has_tag (GtkTextLine *line,
3085 GtkTextLineSegment *toggle_seg;
3087 g_return_val_if_fail (line != NULL, FALSE);
3090 * Check for toggles for the tag in the line but before
3091 * the char. If there is one, its type indicates whether or
3092 * not the character is tagged.
3095 toggle_seg = find_toggle_segment_before_byte (line, byte_in_line, tag);
3097 if (toggle_seg != NULL)
3098 return (toggle_seg->type == >k_text_toggle_on_type);
3100 return find_toggle_outside_current_line (line, tree, tag);
3104 _gtk_text_line_is_last (GtkTextLine *line,
3107 return line == get_last_line (tree);
3111 _gtk_text_line_next (GtkTextLine *line)
3113 GtkTextBTreeNode *node;
3115 if (line->next != NULL)
3120 * This was the last line associated with the particular parent
3121 * GtkTextBTreeNode. Search up the tree for the next GtkTextBTreeNode,
3122 * then search down from that GtkTextBTreeNode to find the first
3126 node = line->parent;
3127 while (node != NULL && node->next == NULL)
3128 node = node->parent;
3134 while (node->level > 0)
3136 node = node->children.node;
3139 g_assert (node->children.line != line);
3141 return node->children.line;
3146 _gtk_text_line_previous (GtkTextLine *line)
3148 GtkTextBTreeNode *node;
3149 GtkTextBTreeNode *node2;
3153 * Find the line under this GtkTextBTreeNode just before the starting line.
3155 prev = line->parent->children.line; /* First line at leaf */
3156 while (prev != line)
3158 if (prev->next == line)
3164 g_error ("gtk_text_btree_previous_line ran out of lines");
3168 * This was the first line associated with the particular parent
3169 * GtkTextBTreeNode. Search up the tree for the previous GtkTextBTreeNode,
3170 * then search down from that GtkTextBTreeNode to find its last line.
3172 for (node = line->parent; ; node = node->parent)
3174 if (node == NULL || node->parent == NULL)
3176 else if (node != node->parent->children.node)
3180 for (node2 = node->parent->children.node; ;
3181 node2 = node2->children.node)
3183 while (node2->next != node)
3184 node2 = node2->next;
3186 if (node2->level == 0)
3192 for (prev = node2->children.line ; ; prev = prev->next)
3194 if (prev->next == NULL)
3198 g_assert_not_reached ();
3203 _gtk_text_line_add_data (GtkTextLine *line,
3204 GtkTextLineData *data)
3206 g_return_if_fail (line != NULL);
3207 g_return_if_fail (data != NULL);
3208 g_return_if_fail (data->view_id != NULL);
3212 data->next = line->views;
3222 _gtk_text_line_remove_data (GtkTextLine *line,
3225 GtkTextLineData *prev;
3226 GtkTextLineData *iter;
3228 g_return_val_if_fail (line != NULL, NULL);
3229 g_return_val_if_fail (view_id != NULL, NULL);
3233 while (iter != NULL)
3235 if (iter->view_id == view_id)
3244 prev->next = iter->next;
3246 line->views = iter->next;
3255 _gtk_text_line_get_data (GtkTextLine *line,
3258 GtkTextLineData *iter;
3260 g_return_val_if_fail (line != NULL, NULL);
3261 g_return_val_if_fail (view_id != NULL, NULL);
3264 while (iter != NULL)
3266 if (iter->view_id == view_id)
3275 _gtk_text_line_invalidate_wrap (GtkTextLine *line,
3276 GtkTextLineData *ld)
3278 /* For now this is totally unoptimized. FIXME?
3280 We could probably optimize the case where the width removed
3281 is less than the max width for the parent node,
3282 and the case where the height is unchanged when we re-wrap.
3285 g_return_if_fail (ld != NULL);
3288 gtk_text_btree_node_invalidate_upward (line->parent, ld->view_id);
3292 _gtk_text_line_char_count (GtkTextLine *line)
3294 GtkTextLineSegment *seg;
3298 seg = line->segments;
3301 size += seg->char_count;
3308 _gtk_text_line_byte_count (GtkTextLine *line)
3310 GtkTextLineSegment *seg;
3314 seg = line->segments;
3317 size += seg->byte_count;
3325 _gtk_text_line_char_index (GtkTextLine *target_line)
3327 GSList *node_stack = NULL;
3328 GtkTextBTreeNode *iter;
3332 /* Push all our parent nodes onto a stack */
3333 iter = target_line->parent;
3335 g_assert (iter != NULL);
3337 while (iter != NULL)
3339 node_stack = g_slist_prepend (node_stack, iter);
3341 iter = iter->parent;
3344 /* Check that we have the root node on top of the stack. */
3345 g_assert (node_stack != NULL &&
3346 node_stack->data != NULL &&
3347 ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3349 /* Add up chars in all nodes before the nodes in our stack.
3353 iter = node_stack->data;
3354 while (iter != NULL)
3356 GtkTextBTreeNode *child_iter;
3357 GtkTextBTreeNode *next_node;
3359 next_node = node_stack->next ?
3360 node_stack->next->data : NULL;
3361 node_stack = g_slist_remove (node_stack, node_stack->data);
3363 if (iter->level == 0)
3365 /* stack should be empty when we're on the last node */
3366 g_assert (node_stack == NULL);
3367 break; /* Our children are now lines */
3370 g_assert (next_node != NULL);
3371 g_assert (iter != NULL);
3372 g_assert (next_node->parent == iter);
3374 /* Add up chars before us in the tree */
3375 child_iter = iter->children.node;
3376 while (child_iter != next_node)
3378 g_assert (child_iter != NULL);
3380 num_chars += child_iter->num_chars;
3382 child_iter = child_iter->next;
3388 g_assert (iter != NULL);
3389 g_assert (iter == target_line->parent);
3391 /* Since we don't store char counts in lines, only in segments, we
3392 have to iterate over the lines adding up segment char counts
3393 until we find our line. */
3394 line = iter->children.line;
3395 while (line != target_line)
3397 g_assert (line != NULL);
3399 num_chars += _gtk_text_line_char_count (line);
3404 g_assert (line == target_line);
3410 _gtk_text_line_byte_to_segment (GtkTextLine *line,
3414 GtkTextLineSegment *seg;
3417 g_return_val_if_fail (line != NULL, NULL);
3419 offset = byte_offset;
3420 seg = line->segments;
3422 while (offset >= seg->byte_count)
3424 g_assert (seg != NULL); /* means an invalid byte index */
3425 offset -= seg->byte_count;
3430 *seg_offset = offset;
3436 _gtk_text_line_char_to_segment (GtkTextLine *line,
3440 GtkTextLineSegment *seg;
3443 g_return_val_if_fail (line != NULL, NULL);
3445 offset = char_offset;
3446 seg = line->segments;
3448 while (offset >= seg->char_count)
3450 g_assert (seg != NULL); /* means an invalid char index */
3451 offset -= seg->char_count;
3456 *seg_offset = offset;
3462 _gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3466 GtkTextLineSegment *seg;
3469 g_return_val_if_fail (line != NULL, NULL);
3471 offset = byte_offset;
3472 seg = line->segments;
3474 while (offset > 0 && offset >= seg->byte_count)
3476 g_assert (seg != NULL); /* means an invalid byte index */
3477 offset -= seg->byte_count;
3482 *seg_offset = offset;
3488 _gtk_text_line_char_to_any_segment (GtkTextLine *line,
3492 GtkTextLineSegment *seg;
3495 g_return_val_if_fail (line != NULL, NULL);
3497 offset = char_offset;
3498 seg = line->segments;
3500 while (offset > 0 && offset >= seg->char_count)
3502 g_assert (seg != NULL); /* means an invalid byte index */
3503 offset -= seg->char_count;
3508 *seg_offset = offset;
3514 _gtk_text_line_byte_to_char (GtkTextLine *line,
3518 GtkTextLineSegment *seg;
3520 g_return_val_if_fail (line != NULL, 0);
3521 g_return_val_if_fail (byte_offset >= 0, 0);
3524 seg = line->segments;
3525 while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3526 the next segment) */
3528 g_assert (seg != NULL); /* our byte_index was bogus if this happens */
3530 byte_offset -= seg->byte_count;
3531 char_offset += seg->char_count;
3536 g_assert (seg != NULL);
3538 /* Now byte_offset is the offset into the current segment,
3539 and char_offset is the start of the current segment.
3540 Optimize the case where no chars use > 1 byte */
3541 if (seg->byte_count == seg->char_count)
3542 return char_offset + byte_offset;
3545 if (seg->type == >k_text_char_type)
3546 return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3549 g_assert (seg->char_count == 1);
3550 g_assert (byte_offset == 0);
3558 _gtk_text_line_char_to_byte (GtkTextLine *line,
3561 g_warning ("FIXME not implemented");
3566 /* FIXME sync with char_locate (or figure out a clean
3567 way to merge the two functions) */
3569 _gtk_text_line_byte_locate (GtkTextLine *line,
3571 GtkTextLineSegment **segment,
3572 GtkTextLineSegment **any_segment,
3573 gint *seg_byte_offset,
3574 gint *line_byte_offset)
3576 GtkTextLineSegment *seg;
3577 GtkTextLineSegment *after_prev_indexable;
3578 GtkTextLineSegment *after_last_indexable;
3579 GtkTextLineSegment *last_indexable;
3583 g_return_val_if_fail (line != NULL, FALSE);
3584 g_return_val_if_fail (byte_offset >= 0, FALSE);
3587 *any_segment = NULL;
3590 offset = byte_offset;
3592 last_indexable = NULL;
3593 after_last_indexable = line->segments;
3594 after_prev_indexable = line->segments;
3595 seg = line->segments;
3597 /* The loop ends when we're inside a segment;
3598 last_indexable refers to the last segment
3599 we passed entirely. */
3600 while (seg && offset >= seg->byte_count)
3602 if (seg->char_count > 0)
3604 offset -= seg->byte_count;
3605 bytes_in_line += seg->byte_count;
3606 last_indexable = seg;
3607 after_prev_indexable = after_last_indexable;
3608 after_last_indexable = last_indexable->next;
3616 /* We went off the end of the line */
3618 g_warning ("%s: byte index off the end of the line", G_STRLOC);
3625 if (after_last_indexable != NULL)
3626 *any_segment = after_last_indexable;
3628 *any_segment = *segment;
3631 /* Override any_segment if we're in the middle of a segment. */
3633 *any_segment = *segment;
3635 *seg_byte_offset = offset;
3637 g_assert (*segment != NULL);
3638 g_assert (*any_segment != NULL);
3639 g_assert (*seg_byte_offset < (*segment)->byte_count);
3641 *line_byte_offset = bytes_in_line + *seg_byte_offset;
3646 /* FIXME sync with byte_locate (or figure out a clean
3647 way to merge the two functions) */
3649 _gtk_text_line_char_locate (GtkTextLine *line,
3651 GtkTextLineSegment **segment,
3652 GtkTextLineSegment **any_segment,
3653 gint *seg_char_offset,
3654 gint *line_char_offset)
3656 GtkTextLineSegment *seg;
3657 GtkTextLineSegment *after_prev_indexable;
3658 GtkTextLineSegment *after_last_indexable;
3659 GtkTextLineSegment *last_indexable;
3663 g_return_val_if_fail (line != NULL, FALSE);
3664 g_return_val_if_fail (char_offset >= 0, FALSE);
3667 *any_segment = NULL;
3670 offset = char_offset;
3672 last_indexable = NULL;
3673 after_last_indexable = line->segments;
3674 after_prev_indexable = line->segments;
3675 seg = line->segments;
3677 /* The loop ends when we're inside a segment;
3678 last_indexable refers to the last segment
3679 we passed entirely. */
3680 while (seg && offset >= seg->char_count)
3682 if (seg->char_count > 0)
3684 offset -= seg->char_count;
3685 chars_in_line += seg->char_count;
3686 last_indexable = seg;
3687 after_prev_indexable = after_last_indexable;
3688 after_last_indexable = last_indexable->next;
3696 /* end of the line */
3698 g_warning ("%s: char offset off the end of the line", G_STRLOC);
3705 if (after_last_indexable != NULL)
3706 *any_segment = after_last_indexable;
3708 *any_segment = *segment;
3711 /* Override any_segment if we're in the middle of a segment. */
3713 *any_segment = *segment;
3715 *seg_char_offset = offset;
3717 g_assert (*segment != NULL);
3718 g_assert (*any_segment != NULL);
3719 g_assert (*seg_char_offset < (*segment)->char_count);
3721 *line_char_offset = chars_in_line + *seg_char_offset;
3727 _gtk_text_line_byte_to_char_offsets (GtkTextLine *line,
3729 gint *line_char_offset,
3730 gint *seg_char_offset)
3732 GtkTextLineSegment *seg;
3735 g_return_if_fail (line != NULL);
3736 g_return_if_fail (byte_offset >= 0);
3738 *line_char_offset = 0;
3740 offset = byte_offset;
3741 seg = line->segments;
3743 while (offset >= seg->byte_count)
3745 offset -= seg->byte_count;
3746 *line_char_offset += seg->char_count;
3748 g_assert (seg != NULL); /* means an invalid char offset */
3751 g_assert (seg->char_count > 0); /* indexable. */
3753 /* offset is now the number of bytes into the current segment we
3754 * want to go. Count chars into the current segment.
3757 if (seg->type == >k_text_char_type)
3759 *seg_char_offset = g_utf8_strlen (seg->body.chars, offset);
3761 g_assert (*seg_char_offset < seg->char_count);
3763 *line_char_offset += *seg_char_offset;
3767 g_assert (offset == 0);
3768 *seg_char_offset = 0;
3773 _gtk_text_line_char_to_byte_offsets (GtkTextLine *line,
3775 gint *line_byte_offset,
3776 gint *seg_byte_offset)
3778 GtkTextLineSegment *seg;
3781 g_return_if_fail (line != NULL);
3782 g_return_if_fail (char_offset >= 0);
3784 *line_byte_offset = 0;
3786 offset = char_offset;
3787 seg = line->segments;
3789 while (offset >= seg->char_count)
3791 offset -= seg->char_count;
3792 *line_byte_offset += seg->byte_count;
3794 g_assert (seg != NULL); /* means an invalid char offset */
3797 g_assert (seg->char_count > 0); /* indexable. */
3799 /* offset is now the number of chars into the current segment we
3800 want to go. Count bytes into the current segment. */
3802 if (seg->type == >k_text_char_type)
3804 *seg_byte_offset = 0;
3808 const char * start = seg->body.chars + *seg_byte_offset;
3810 bytes = g_utf8_next_char (start) - start;
3811 *seg_byte_offset += bytes;
3815 g_assert (*seg_byte_offset < seg->byte_count);
3817 *line_byte_offset += *seg_byte_offset;
3821 g_assert (offset == 0);
3822 *seg_byte_offset = 0;
3827 node_compare (GtkTextBTreeNode *lhs,
3828 GtkTextBTreeNode *rhs)
3830 GtkTextBTreeNode *iter;
3831 GtkTextBTreeNode *node;
3832 GtkTextBTreeNode *common_parent;
3833 GtkTextBTreeNode *parent_of_lower;
3834 GtkTextBTreeNode *parent_of_higher;
3835 gboolean lhs_is_lower;
3836 GtkTextBTreeNode *lower;
3837 GtkTextBTreeNode *higher;
3839 /* This function assumes that lhs and rhs are not underneath each
3846 if (lhs->level < rhs->level)
3848 lhs_is_lower = TRUE;
3854 lhs_is_lower = FALSE;
3859 /* Algorithm: find common parent of lhs/rhs. Save the child nodes
3860 * of the common parent we used to reach the common parent; the
3861 * ordering of these child nodes in the child list is the ordering
3865 /* Get on the same level (may be on same level already) */
3867 while (node->level < higher->level)
3868 node = node->parent;
3870 g_assert (node->level == higher->level);
3872 g_assert (node != higher); /* Happens if lower is underneath higher */
3874 /* Go up until we have two children with a common parent.
3876 parent_of_lower = node;
3877 parent_of_higher = higher;
3879 while (parent_of_lower->parent != parent_of_higher->parent)
3881 parent_of_lower = parent_of_lower->parent;
3882 parent_of_higher = parent_of_higher->parent;
3885 g_assert (parent_of_lower->parent == parent_of_higher->parent);
3887 common_parent = parent_of_lower->parent;
3889 g_assert (common_parent != NULL);
3891 /* See which is first in the list of common_parent's children */
3892 iter = common_parent->children.node;
3893 while (iter != NULL)
3895 if (iter == parent_of_higher)
3897 /* higher is less than lower */
3900 return 1; /* lhs > rhs */
3904 else if (iter == parent_of_lower)
3906 /* lower is less than higher */
3909 return -1; /* lhs < rhs */
3917 g_assert_not_reached ();
3921 /* remember that tag == NULL means "any tag" */
3923 _gtk_text_line_next_could_contain_tag (GtkTextLine *line,
3927 GtkTextBTreeNode *node;
3928 GtkTextTagInfo *info;
3929 gboolean below_tag_root;
3931 g_return_val_if_fail (line != NULL, NULL);
3933 if (gtk_debug_flags & GTK_DEBUG_TEXT)
3934 _gtk_text_btree_check (tree);
3938 /* Right now we can only offer linear-search if the user wants
3939 * to know about any tag toggle at all.
3941 return _gtk_text_line_next (line);
3944 /* Our tag summaries only have node precision, not line
3945 precision. This means that if any line under a node could contain a
3946 tag, then any of the others could also contain a tag.
3948 In the future we could have some mechanism to keep track of how
3949 many toggles we've found under a node so far, since we have a
3950 count of toggles under the node. But for now I'm going with KISS.
3953 /* return same-node line, if any. */
3957 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3961 if (info->tag_root == NULL)
3964 if (info->tag_root == line->parent)
3965 return NULL; /* we were at the last line under the tag root */
3967 /* We need to go up out of this node, and on to the next one with
3968 toggles for the target tag. If we're below the tag root, we need to
3969 find the next node below the tag root that has tag summaries. If
3970 we're not below the tag root, we need to see if the tag root is
3971 after us in the tree, and if so, return the first line underneath
3974 node = line->parent;
3975 below_tag_root = FALSE;
3976 while (node != NULL)
3978 if (node == info->tag_root)
3980 below_tag_root = TRUE;
3984 node = node->parent;
3989 node = line->parent;
3990 while (node != info->tag_root)
3992 if (node->next == NULL)
3993 node = node->parent;
3998 if (gtk_text_btree_node_has_tag (node, tag))
4008 ordering = node_compare (line->parent, info->tag_root);
4012 /* Tag root is ahead of us, so search there. */
4013 node = info->tag_root;
4018 /* Tag root is after us, so no more lines that
4019 * could contain the tag.
4024 g_assert_not_reached ();
4029 g_assert (node != NULL);
4031 /* We have to find the first sub-node of this node that contains
4035 while (node->level > 0)
4037 g_assert (node != NULL); /* If this fails, it likely means an
4038 incorrect tag summary led us on a
4039 wild goose chase down this branch of
4041 node = node->children.node;
4042 while (node != NULL)
4044 if (gtk_text_btree_node_has_tag (node, tag))
4050 g_assert (node != NULL);
4051 g_assert (node->level == 0);
4053 return node->children.line;
4057 prev_line_under_node (GtkTextBTreeNode *node,
4062 prev = node->children.line;
4068 while (prev->next != line)
4078 _gtk_text_line_previous_could_contain_tag (GtkTextLine *line,
4082 GtkTextBTreeNode *node;
4083 GtkTextBTreeNode *found_node = NULL;
4084 GtkTextTagInfo *info;
4085 gboolean below_tag_root;
4087 GtkTextBTreeNode *line_ancestor;
4088 GtkTextBTreeNode *line_ancestor_parent;
4090 /* See next_could_contain_tag () for more extensive comments
4091 * on what's going on here.
4094 g_return_val_if_fail (line != NULL, NULL);
4096 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4097 _gtk_text_btree_check (tree);
4101 /* Right now we can only offer linear-search if the user wants
4102 * to know about any tag toggle at all.
4104 return _gtk_text_line_previous (line);
4107 /* Return same-node line, if any. */
4108 prev = prev_line_under_node (line->parent, line);
4112 info = gtk_text_btree_get_existing_tag_info (tree, tag);
4116 if (info->tag_root == NULL)
4119 if (info->tag_root == line->parent)
4120 return NULL; /* we were at the first line under the tag root */
4122 /* Are we below the tag root */
4123 node = line->parent;
4124 below_tag_root = FALSE;
4125 while (node != NULL)
4127 if (node == info->tag_root)
4129 below_tag_root = TRUE;
4133 node = node->parent;
4138 /* Look for a previous node under this tag root that has our
4142 /* this assertion holds because line->parent is not the
4143 * tag root, we are below the tag root, and the tag
4146 g_assert (line->parent->parent != NULL);
4148 line_ancestor = line->parent;
4149 line_ancestor_parent = line->parent->parent;
4151 node = line_ancestor_parent->children.node;
4152 while (node != line_ancestor &&
4153 line_ancestor != info->tag_root)
4155 GSList *child_nodes = NULL;
4158 /* Create reverse-order list of nodes before
4161 while (node != line_ancestor
4164 child_nodes = g_slist_prepend (child_nodes, node);
4169 /* Try to find a node with our tag on it in the list */
4173 GtkTextBTreeNode *this_node = tmp->data;
4175 g_assert (this_node != line_ancestor);
4177 if (gtk_text_btree_node_has_tag (this_node, tag))
4179 found_node = this_node;
4180 g_slist_free (child_nodes);
4184 tmp = g_slist_next (tmp);
4187 g_slist_free (child_nodes);
4189 /* Didn't find anything on this level; go up one level. */
4190 line_ancestor = line_ancestor_parent;
4191 line_ancestor_parent = line_ancestor->parent;
4193 node = line_ancestor_parent->children.node;
4203 ordering = node_compare (line->parent, info->tag_root);
4207 /* Tag root is ahead of us, so no more lines
4214 /* Tag root is after us, so grab last tagged
4215 * line underneath the tag root.
4217 found_node = info->tag_root;
4221 g_assert_not_reached ();
4226 g_assert (found_node != NULL);
4228 /* We have to find the last sub-node of this node that contains
4233 while (node->level > 0)
4235 GSList *child_nodes = NULL;
4237 g_assert (node != NULL); /* If this fails, it likely means an
4238 incorrect tag summary led us on a
4239 wild goose chase down this branch of
4242 node = node->children.node;
4243 while (node != NULL)
4245 child_nodes = g_slist_prepend (child_nodes, node);
4249 node = NULL; /* detect failure to find a child node. */
4252 while (iter != NULL)
4254 if (gtk_text_btree_node_has_tag (iter->data, tag))
4256 /* recurse into this node. */
4261 iter = g_slist_next (iter);
4264 g_slist_free (child_nodes);
4266 g_assert (node != NULL);
4269 g_assert (node != NULL);
4270 g_assert (node->level == 0);
4272 /* this assertion is correct, but slow. */
4273 /* g_assert (node_compare (node, line->parent) < 0); */
4275 /* Return last line in this node. */
4277 prev = node->children.line;
4285 * Non-public function implementations
4289 summary_list_destroy (Summary *summary)
4292 while (summary != NULL)
4294 next = summary->next;
4295 summary_destroy (summary);
4301 get_last_line (GtkTextBTree *tree)
4303 if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
4309 n_lines = _gtk_text_btree_line_count (tree);
4311 g_assert (n_lines >= 1); /* num_lines doesn't return bogus last line. */
4313 line = _gtk_text_btree_get_line (tree, n_lines, &real_line);
4315 tree->end_iter_line_stamp = tree->chars_changed_stamp;
4316 tree->end_iter_line = line;
4319 return tree->end_iter_line;
4327 gtk_text_line_new (void)
4331 line = g_new0(GtkTextLine, 1);
4337 gtk_text_line_destroy (GtkTextBTree *tree, GtkTextLine *line)
4339 GtkTextLineData *ld;
4340 GtkTextLineData *next;
4342 g_return_if_fail (line != NULL);
4349 view = gtk_text_btree_get_view (tree, ld->view_id);
4351 g_assert (view != NULL);
4354 gtk_text_layout_free_line_data (view->layout, line, ld);
4363 gtk_text_line_set_parent (GtkTextLine *line,
4364 GtkTextBTreeNode *node)
4366 if (line->parent == node)
4368 line->parent = node;
4369 gtk_text_btree_node_invalidate_upward (node, NULL);
4373 cleanup_line (GtkTextLine *line)
4375 GtkTextLineSegment *seg, **prev_p;
4379 * Make a pass over all of the segments in the line, giving each
4380 * a chance to clean itself up. This could potentially change
4381 * the structure of the line, e.g. by merging two segments
4382 * together or having two segments cancel themselves; if so,
4383 * then repeat the whole process again, since the first structure
4384 * change might make other structure changes possible. Repeat
4385 * until eventually there are no changes.
4392 for (prev_p = &line->segments, seg = *prev_p;
4394 prev_p = &(*prev_p)->next, seg = *prev_p)
4396 if (seg->type->cleanupFunc != NULL)
4398 *prev_p = (*seg->type->cleanupFunc)(seg, line);
4411 node_data_new (gpointer view_id)
4415 nd = g_new (NodeData, 1);
4417 nd->view_id = view_id;
4427 node_data_destroy (NodeData *nd)
4433 node_data_list_destroy (NodeData *nd)
4439 while (iter != NULL)
4442 node_data_destroy (iter);
4448 node_data_find (NodeData *nd, gpointer view_id)
4452 if (nd->view_id == view_id)
4460 summary_destroy (Summary *summary)
4462 /* Fill with error-triggering garbage */
4463 summary->info = (void*)0x1;
4464 summary->toggle_count = 567;
4465 summary->next = (void*)0x1;
4469 static GtkTextBTreeNode*
4470 gtk_text_btree_node_new (void)
4472 GtkTextBTreeNode *node;
4474 node = g_new (GtkTextBTreeNode, 1);
4476 node->node_data = NULL;
4482 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
4483 GtkTextTagInfo *info,
4488 summary = node->summary;
4489 while (summary != NULL)
4491 if (summary->info == info)
4493 summary->toggle_count += adjust;
4497 summary = summary->next;
4500 if (summary == NULL)
4502 /* didn't find a summary for our tag. */
4503 g_return_if_fail (adjust > 0);
4504 summary = g_new (Summary, 1);
4505 summary->info = info;
4506 summary->toggle_count = adjust;
4507 summary->next = node->summary;
4508 node->summary = summary;
4512 /* Note that the tag root and above do not have summaries
4513 for the tag; only nodes below the tag root have
4516 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4520 summary = node->summary;
4521 while (summary != NULL)
4524 summary->info->tag == tag)
4527 summary = summary->next;
4533 /* Add node and all children to the damage region. */
4535 gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node)
4539 nd = node->node_data;
4546 if (node->level == 0)
4550 line = node->children.line;
4551 while (line != NULL)
4553 GtkTextLineData *ld;
4567 GtkTextBTreeNode *child;
4569 child = node->children.node;
4571 while (child != NULL)
4573 gtk_text_btree_node_invalidate_downward (child);
4575 child = child->next;
4581 gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node, gpointer view_id)
4583 GtkTextBTreeNode *iter;
4586 while (iter != NULL)
4592 nd = node_data_find (iter->node_data, view_id);
4594 if (nd == NULL || !nd->valid)
4595 break; /* Once a node is invalid, we know its parents are as well. */
4601 gboolean should_continue = FALSE;
4603 nd = iter->node_data;
4608 should_continue = TRUE;
4615 if (!should_continue)
4616 break; /* This node was totally invalidated, so are its
4620 iter = iter->parent;
4626 * _gtk_text_btree_is_valid:
4627 * @tree: a #GtkTextBTree
4628 * @view_id: ID for the view
4630 * Check to see if the entire #GtkTextBTree is valid or not for
4633 * Return value: %TRUE if the entire #GtkTextBTree is valid
4636 _gtk_text_btree_is_valid (GtkTextBTree *tree,
4640 g_return_val_if_fail (tree != NULL, FALSE);
4642 nd = node_data_find (tree->root_node->node_data, view_id);
4643 return (nd && nd->valid);
4646 typedef struct _ValidateState ValidateState;
4648 struct _ValidateState
4650 gint remaining_pixels;
4651 gboolean in_validation;
4658 gtk_text_btree_node_validate (BTreeView *view,
4659 GtkTextBTreeNode *node,
4661 ValidateState *state)
4663 gint node_valid = TRUE;
4664 gint node_width = 0;
4665 gint node_height = 0;
4667 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4668 g_return_if_fail (!nd->valid);
4670 if (node->level == 0)
4672 GtkTextLine *line = node->children.line;
4673 GtkTextLineData *ld;
4675 /* Iterate over leading valid lines */
4676 while (line != NULL)
4678 ld = _gtk_text_line_get_data (line, view_id);
4680 if (!ld || !ld->valid)
4682 else if (state->in_validation)
4684 state->in_validation = FALSE;
4689 state->y += ld->height;
4690 node_width = MAX (ld->width, node_width);
4691 node_height += ld->height;
4697 state->in_validation = TRUE;
4699 /* Iterate over invalid lines */
4700 while (line != NULL)
4702 ld = _gtk_text_line_get_data (line, view_id);
4704 if (ld && ld->valid)
4709 state->old_height += ld->height;
4710 ld = gtk_text_layout_wrap (view->layout, line, ld);
4711 state->new_height += ld->height;
4713 node_width = MAX (ld->width, node_width);
4714 node_height += ld->height;
4716 state->remaining_pixels -= ld->height;
4717 if (state->remaining_pixels <= 0)
4727 /* Iterate over the remaining lines */
4728 while (line != NULL)
4730 ld = _gtk_text_line_get_data (line, view_id);
4731 state->in_validation = FALSE;
4733 if (!ld || !ld->valid)
4738 node_width = MAX (ld->width, node_width);
4739 node_height += ld->height;
4747 GtkTextBTreeNode *child;
4750 child = node->children.node;
4752 /* Iterate over leading valid nodes */
4755 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4757 if (!child_nd->valid)
4759 else if (state->in_validation)
4761 state->in_validation = FALSE;
4766 state->y += child_nd->height;
4767 node_width = MAX (node_width, child_nd->width);
4768 node_height += child_nd->height;
4771 child = child->next;
4774 /* Iterate over invalid nodes */
4777 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4779 if (child_nd->valid)
4783 gtk_text_btree_node_validate (view, child, view_id, state);
4785 if (!child_nd->valid)
4787 node_width = MAX (node_width, child_nd->width);
4788 node_height += child_nd->height;
4790 if (!state->in_validation || state->remaining_pixels <= 0)
4792 child = child->next;
4797 child = child->next;
4800 /* Iterate over the remaining lines */
4803 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4804 state->in_validation = FALSE;
4806 if (!child_nd->valid)
4809 node_width = MAX (child_nd->width, node_width);
4810 node_height += child_nd->height;
4812 child = child->next;
4816 nd->width = node_width;
4817 nd->height = node_height;
4818 nd->valid = node_valid;
4822 * _gtk_text_btree_validate:
4823 * @tree: a #GtkTextBTree
4825 * @max_pixels: the maximum number of pixels to validate. (No more
4826 * than one paragraph beyond this limit will be validated)
4827 * @y: location to store starting y coordinate of validated region
4828 * @old_height: location to store old height of validated region
4829 * @new_height: location to store new height of validated region
4831 * Validate a single contiguous invalid region of a #GtkTextBTree for
4834 * Return value: %TRUE if a region has been validated, %FALSE if the
4835 * entire tree was already valid.
4838 _gtk_text_btree_validate (GtkTextBTree *tree,
4847 g_return_val_if_fail (tree != NULL, FALSE);
4849 view = gtk_text_btree_get_view (tree, view_id);
4850 g_return_val_if_fail (view != NULL, FALSE);
4852 if (!_gtk_text_btree_is_valid (tree, view_id))
4854 ValidateState state;
4856 state.remaining_pixels = max_pixels;
4857 state.in_validation = FALSE;
4859 state.old_height = 0;
4860 state.new_height = 0;
4862 gtk_text_btree_node_validate (view,
4869 *old_height = state.old_height;
4871 *new_height = state.new_height;
4873 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4874 _gtk_text_btree_check (tree);
4883 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
4887 gboolean *valid_out)
4891 gboolean valid = TRUE;
4893 if (node->level == 0)
4895 GtkTextLine *line = node->children.line;
4897 while (line != NULL)
4899 GtkTextLineData *ld = _gtk_text_line_get_data (line, view_id);
4901 if (!ld || !ld->valid)
4906 width = MAX (ld->width, width);
4907 height += ld->height;
4915 GtkTextBTreeNode *child = node->children.node;
4919 NodeData *child_nd = node_data_find (child->node_data, view_id);
4921 if (!child_nd || !child_nd->valid)
4926 width = MAX (child_nd->width, width);
4927 height += child_nd->height;
4930 child = child->next;
4935 *height_out = height;
4940 /* Recompute the validity and size of the view data for a given
4941 * view at this node from the immediate children of the node
4944 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
4947 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4952 gtk_text_btree_node_compute_view_aggregates (node, view_id,
4953 &width, &height, &valid);
4955 nd->height = height;
4962 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
4967 gtk_text_btree_node_check_valid (node, view_id);
4968 node = node->parent;
4973 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
4976 if (node->level == 0)
4978 return gtk_text_btree_node_check_valid (node, view_id);
4982 GtkTextBTreeNode *child = node->children.node;
4984 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4992 NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
4994 if (!child_nd->valid)
4996 nd->width = MAX (child_nd->width, nd->width);
4997 nd->height += child_nd->height;
4999 child = child->next;
5008 * _gtk_text_btree_validate_line:
5009 * @tree: a #GtkTextBTree
5010 * @line: line to validate
5011 * @view_id: view ID for the view to validate
5013 * Revalidate a single line of the btree for the given view, propagate
5014 * results up through the entire tree.
5017 _gtk_text_btree_validate_line (GtkTextBTree *tree,
5021 GtkTextLineData *ld;
5024 g_return_if_fail (tree != NULL);
5025 g_return_if_fail (line != NULL);
5027 view = gtk_text_btree_get_view (tree, view_id);
5028 g_return_if_fail (view != NULL);
5030 ld = _gtk_text_line_get_data (line, view_id);
5031 if (!ld || !ld->valid)
5033 ld = gtk_text_layout_wrap (view->layout, line, ld);
5035 gtk_text_btree_node_check_valid_upward (line->parent, view_id);
5040 gtk_text_btree_node_remove_view (BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
5042 if (node->level == 0)
5046 line = node->children.line;
5047 while (line != NULL)
5049 GtkTextLineData *ld;
5051 ld = _gtk_text_line_remove_data (line, view_id);
5054 gtk_text_layout_free_line_data (view->layout, line, ld);
5061 GtkTextBTreeNode *child;
5063 child = node->children.node;
5065 while (child != NULL)
5068 gtk_text_btree_node_remove_view (view, child, view_id);
5070 child = child->next;
5074 gtk_text_btree_node_remove_data (node, view_id);
5078 gtk_text_btree_node_destroy (GtkTextBTree *tree, GtkTextBTreeNode *node)
5080 if (node->level == 0)
5083 GtkTextLineSegment *seg;
5085 while (node->children.line != NULL)
5087 line = node->children.line;
5088 node->children.line = line->next;
5089 while (line->segments != NULL)
5091 seg = line->segments;
5092 line->segments = seg->next;
5094 if (GTK_IS_TEXT_MARK_SEGMENT (seg))
5096 /* Set the mark as deleted */
5097 seg->body.mark.tree = NULL;
5098 seg->body.mark.line = NULL;
5101 (*seg->type->deleteFunc) (seg, line, 1);
5103 gtk_text_line_destroy (tree, line);
5108 GtkTextBTreeNode *childPtr;
5110 while (node->children.node != NULL)
5112 childPtr = node->children.node;
5113 node->children.node = childPtr->next;
5114 gtk_text_btree_node_destroy (tree, childPtr);
5118 gtk_text_btree_node_free_empty (tree, node);
5122 gtk_text_btree_node_free_empty (GtkTextBTree *tree,
5123 GtkTextBTreeNode *node)
5125 g_return_if_fail ((node->level > 0 && node->children.node == NULL) ||
5126 (node->level == 0 && node->children.line == NULL));
5128 summary_list_destroy (node->summary);
5129 node_data_list_destroy (node->node_data);
5134 gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node, gpointer view_id)
5138 nd = node->node_data;
5141 if (nd->view_id == view_id)
5149 nd = node_data_new (view_id);
5151 if (node->node_data)
5152 nd->next = node->node_data;
5154 node->node_data = nd;
5161 gtk_text_btree_node_remove_data (GtkTextBTreeNode *node, gpointer view_id)
5167 nd = node->node_data;
5170 if (nd->view_id == view_id)
5181 prev->next = nd->next;
5183 if (node->node_data == nd)
5184 node->node_data = nd->next;
5188 node_data_destroy (nd);
5192 gtk_text_btree_node_get_size (GtkTextBTreeNode *node, gpointer view_id,
5193 gint *width, gint *height)
5197 g_return_if_fail (width != NULL);
5198 g_return_if_fail (height != NULL);
5200 nd = gtk_text_btree_node_ensure_data (node, view_id);
5205 *height = nd->height;
5208 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5209 * here isn't quite right, since for a lot of operations we want to
5210 * know which children of the common parent correspond to the two nodes
5211 * (e.g., when computing the order of two iters)
5213 static GtkTextBTreeNode *
5214 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5215 GtkTextBTreeNode *node2)
5217 while (node1->level < node2->level)
5218 node1 = node1->parent;
5219 while (node2->level < node1->level)
5220 node2 = node2->parent;
5221 while (node1 != node2)
5223 node1 = node1->parent;
5224 node2 = node2->parent;
5235 gtk_text_btree_get_view (GtkTextBTree *tree, gpointer view_id)
5240 while (view != NULL)
5242 if (view->view_id == view_id)
5251 get_tree_bounds (GtkTextBTree *tree,
5255 _gtk_text_btree_get_iter_at_line_char (tree, start, 0, 0);
5256 _gtk_text_btree_get_end_iter (tree, end);
5260 tag_changed_cb (GtkTextTagTable *table,
5262 gboolean size_changed,
5267 /* We need to queue a relayout on all regions that are tagged with
5274 if (_gtk_text_btree_get_iter_at_first_toggle (tree, &start, tag))
5276 /* Must be a last toggle if there was a first one. */
5277 _gtk_text_btree_get_iter_at_last_toggle (tree, &end, tag);
5278 _gtk_text_btree_invalidate_region (tree,
5285 /* We only need to queue a redraw, not a relayout */
5290 while (view != NULL)
5294 _gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5295 gtk_text_layout_changed (view->layout, 0, height, height);
5303 tag_removed_cb (GtkTextTagTable *table,
5307 /* Remove the tag from the tree */
5312 get_tree_bounds (tree, &start, &end);
5314 _gtk_text_btree_tag (&start, &end, tag, FALSE);
5315 gtk_text_btree_remove_tag_info (tree, tag);
5319 /* Rebalance the out-of-whack node "node" */
5321 gtk_text_btree_rebalance (GtkTextBTree *tree,
5322 GtkTextBTreeNode *node)
5325 * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5326 * up through the tree one GtkTextBTreeNode at a time until the root
5327 * GtkTextBTreeNode has been processed.
5330 while (node != NULL)
5332 GtkTextBTreeNode *new_node, *child;
5337 * Check to see if the GtkTextBTreeNode has too many children. If it does,
5338 * then split off all but the first MIN_CHILDREN into a separate
5339 * GtkTextBTreeNode following the original one. Then repeat until the
5340 * GtkTextBTreeNode has a decent size.
5343 if (node->num_children > MAX_CHILDREN)
5348 * If the GtkTextBTreeNode being split is the root
5349 * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5353 if (node->parent == NULL)
5355 new_node = gtk_text_btree_node_new ();
5356 new_node->parent = NULL;
5357 new_node->next = NULL;
5358 new_node->summary = NULL;
5359 new_node->level = node->level + 1;
5360 new_node->children.node = node;
5361 recompute_node_counts (tree, new_node);
5362 tree->root_node = new_node;
5364 new_node = gtk_text_btree_node_new ();
5365 new_node->parent = node->parent;
5366 new_node->next = node->next;
5367 node->next = new_node;
5368 new_node->summary = NULL;
5369 new_node->level = node->level;
5370 new_node->num_children = node->num_children - MIN_CHILDREN;
5371 if (node->level == 0)
5373 for (i = MIN_CHILDREN-1,
5374 line = node->children.line;
5375 i > 0; i--, line = line->next)
5377 /* Empty loop body. */
5379 new_node->children.line = line->next;
5384 for (i = MIN_CHILDREN-1,
5385 child = node->children.node;
5386 i > 0; i--, child = child->next)
5388 /* Empty loop body. */
5390 new_node->children.node = child->next;
5393 recompute_node_counts (tree, node);
5394 node->parent->num_children++;
5396 if (node->num_children <= MAX_CHILDREN)
5398 recompute_node_counts (tree, node);
5404 while (node->num_children < MIN_CHILDREN)
5406 GtkTextBTreeNode *other;
5407 GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5408 GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5409 int total_children, first_children, i;
5412 * Too few children for this GtkTextBTreeNode. If this is the root then,
5413 * it's OK for it to have less than MIN_CHILDREN children
5414 * as long as it's got at least two. If it has only one
5415 * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5416 * the tree and use its child as the new root.
5419 if (node->parent == NULL)
5421 if ((node->num_children == 1) && (node->level > 0))
5423 tree->root_node = node->children.node;
5424 tree->root_node->parent = NULL;
5426 node->children.node = NULL;
5427 gtk_text_btree_node_free_empty (tree, node);
5433 * Not the root. Make sure that there are siblings to
5437 if (node->parent->num_children < 2)
5439 gtk_text_btree_rebalance (tree, node->parent);
5444 * Find a sibling neighbor to borrow from, and arrange for
5445 * node to be the earlier of the pair.
5448 if (node->next == NULL)
5450 for (other = node->parent->children.node;
5451 other->next != node;
5452 other = other->next)
5454 /* Empty loop body. */
5461 * We're going to either merge the two siblings together
5462 * into one GtkTextBTreeNode or redivide the children among them to
5463 * balance their loads. As preparation, join their two
5464 * child lists into a single list and remember the half-way
5465 * point in the list.
5468 total_children = node->num_children + other->num_children;
5469 first_children = total_children/2;
5470 if (node->children.node == NULL)
5472 node->children = other->children;
5473 other->children.node = NULL;
5474 other->children.line = NULL;
5476 if (node->level == 0)
5480 for (line = node->children.line, i = 1;
5482 line = line->next, i++)
5484 if (i == first_children)
5489 line->next = other->children.line;
5490 while (i <= first_children)
5499 GtkTextBTreeNode *child;
5501 for (child = node->children.node, i = 1;
5502 child->next != NULL;
5503 child = child->next, i++)
5505 if (i <= first_children)
5507 if (i == first_children)
5509 halfwaynode = child;
5513 child->next = other->children.node;
5514 while (i <= first_children)
5516 halfwaynode = child;
5517 child = child->next;
5523 * If the two siblings can simply be merged together, do it.
5526 if (total_children <= MAX_CHILDREN)
5528 recompute_node_counts (tree, node);
5529 node->next = other->next;
5530 node->parent->num_children--;
5532 other->children.node = NULL;
5533 other->children.line = NULL;
5534 gtk_text_btree_node_free_empty (tree, other);
5539 * The siblings can't be merged, so just divide their
5540 * children evenly between them.
5543 if (node->level == 0)
5545 other->children.line = halfwayline->next;
5546 halfwayline->next = NULL;
5550 other->children.node = halfwaynode->next;
5551 halfwaynode->next = NULL;
5554 recompute_node_counts (tree, node);
5555 recompute_node_counts (tree, other);
5558 node = node->parent;
5563 post_insert_fixup (GtkTextBTree *tree,
5565 gint line_count_delta,
5566 gint char_count_delta)
5569 GtkTextBTreeNode *node;
5572 * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5573 * point, then rebalance the tree if necessary.
5576 for (node = line->parent ; node != NULL;
5577 node = node->parent)
5579 node->num_lines += line_count_delta;
5580 node->num_chars += char_count_delta;
5582 node = line->parent;
5583 node->num_children += line_count_delta;
5585 if (node->num_children > MAX_CHILDREN)
5587 gtk_text_btree_rebalance (tree, node);
5590 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5591 _gtk_text_btree_check (tree);
5594 static GtkTextTagInfo*
5595 gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
5598 GtkTextTagInfo *info;
5602 list = tree->tag_infos;
5603 while (list != NULL)
5606 if (info->tag == tag)
5609 list = g_slist_next (list);
5615 static GtkTextTagInfo*
5616 gtk_text_btree_get_tag_info (GtkTextBTree *tree,
5619 GtkTextTagInfo *info;
5621 info = gtk_text_btree_get_existing_tag_info (tree, tag);
5625 /* didn't find it, create. */
5627 info = g_new (GtkTextTagInfo, 1);
5630 g_object_ref (G_OBJECT (tag));
5631 info->tag_root = NULL;
5632 info->toggle_count = 0;
5634 tree->tag_infos = g_slist_prepend (tree->tag_infos, info);
5641 gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
5644 GtkTextTagInfo *info;
5649 list = tree->tag_infos;
5650 while (list != NULL)
5653 if (info->tag == tag)
5657 prev->next = list->next;
5661 tree->tag_infos = list->next;
5664 g_slist_free (list);
5666 g_object_unref (G_OBJECT (info->tag));
5672 list = g_slist_next (list);
5675 g_assert_not_reached ();
5680 recompute_level_zero_counts (GtkTextBTreeNode *node)
5683 GtkTextLineSegment *seg;
5685 g_assert (node->level == 0);
5687 line = node->children.line;
5688 while (line != NULL)
5690 node->num_children++;
5693 if (line->parent != node)
5694 gtk_text_line_set_parent (line, node);
5696 seg = line->segments;
5700 node->num_chars += seg->char_count;
5702 if (((seg->type != >k_text_toggle_on_type)
5703 && (seg->type != >k_text_toggle_off_type))
5704 || !(seg->body.toggle.inNodeCounts))
5710 GtkTextTagInfo *info;
5712 info = seg->body.toggle.info;
5714 gtk_text_btree_node_adjust_toggle_count (node, info, 1);
5725 recompute_level_nonzero_counts (GtkTextBTreeNode *node)
5728 GtkTextBTreeNode *child;
5730 g_assert (node->level > 0);
5732 child = node->children.node;
5733 while (child != NULL)
5735 node->num_children += 1;
5736 node->num_lines += child->num_lines;
5737 node->num_chars += child->num_chars;
5739 if (child->parent != node)
5741 child->parent = node;
5742 gtk_text_btree_node_invalidate_upward (node, NULL);
5745 summary = child->summary;
5746 while (summary != NULL)
5748 gtk_text_btree_node_adjust_toggle_count (node,
5750 summary->toggle_count);
5752 summary = summary->next;
5755 child = child->next;
5760 *----------------------------------------------------------------------
5762 * recompute_node_counts --
5764 * This procedure is called to recompute all the counts in a GtkTextBTreeNode
5765 * (tags, child information, etc.) by scanning the information in
5766 * its descendants. This procedure is called during rebalancing
5767 * when a GtkTextBTreeNode's child structure has changed.
5773 * The tag counts for node are modified to reflect its current
5774 * child structure, as are its num_children, num_lines, num_chars fields.
5775 * Also, all of the childrens' parent fields are made to point
5778 *----------------------------------------------------------------------
5782 recompute_node_counts (GtkTextBTree *tree, GtkTextBTreeNode *node)
5785 Summary *summary, *summary2;
5788 * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
5789 * the existing Summary records (most of them will probably be reused).
5792 summary = node->summary;
5793 while (summary != NULL)
5795 summary->toggle_count = 0;
5796 summary = summary->next;
5799 node->num_children = 0;
5800 node->num_lines = 0;
5801 node->num_chars = 0;
5804 * Scan through the children, adding the childrens' tag counts into
5805 * the GtkTextBTreeNode's tag counts and adding new Summary structures if
5809 if (node->level == 0)
5810 recompute_level_zero_counts (node);
5812 recompute_level_nonzero_counts (node);
5817 gtk_text_btree_node_check_valid (node, view->view_id);
5822 * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
5823 * records that still have a zero count, or that have all the toggles.
5824 * The GtkTextBTreeNode with the children that account for all the tags toggles
5825 * have no summary information, and they become the tag_root for the tag.
5829 for (summary = node->summary; summary != NULL; )
5831 if (summary->toggle_count > 0 &&
5832 summary->toggle_count < summary->info->toggle_count)
5834 if (node->level == summary->info->tag_root->level)
5837 * The tag's root GtkTextBTreeNode split and some toggles left.
5838 * The tag root must move up a level.
5840 summary->info->tag_root = node->parent;
5843 summary = summary->next;
5846 if (summary->toggle_count == summary->info->toggle_count)
5849 * A GtkTextBTreeNode merge has collected all the toggles under
5850 * one GtkTextBTreeNode. Push the root down to this level.
5852 summary->info->tag_root = node;
5854 if (summary2 != NULL)
5856 summary2->next = summary->next;
5857 summary_destroy (summary);
5858 summary = summary2->next;
5862 node->summary = summary->next;
5863 summary_destroy (summary);
5864 summary = node->summary;
5870 _gtk_change_node_toggle_count (GtkTextBTreeNode *node,
5871 GtkTextTagInfo *info,
5872 gint delta) /* may be negative */
5874 Summary *summary, *prevPtr;
5875 GtkTextBTreeNode *node2Ptr;
5876 int rootLevel; /* Level of original tag root */
5878 info->toggle_count += delta;
5880 if (info->tag_root == (GtkTextBTreeNode *) NULL)
5882 info->tag_root = node;
5887 * Note the level of the existing root for the tag so we can detect
5888 * if it needs to be moved because of the toggle count change.
5891 rootLevel = info->tag_root->level;
5894 * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
5895 * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
5899 for ( ; node != info->tag_root; node = node->parent)
5902 * See if there's already an entry for this tag for this GtkTextBTreeNode. If so,
5903 * perhaps all we have to do is adjust its count.
5906 for (prevPtr = NULL, summary = node->summary;
5908 prevPtr = summary, summary = summary->next)
5910 if (summary->info == info)
5915 if (summary != NULL)
5917 summary->toggle_count += delta;
5918 if (summary->toggle_count > 0 &&
5919 summary->toggle_count < info->toggle_count)
5923 if (summary->toggle_count != 0)
5926 * Should never find a GtkTextBTreeNode with max toggle count at this
5927 * point (there shouldn't have been a summary entry in the
5931 g_error ("%s: bad toggle count (%d) max (%d)",
5932 G_STRLOC, summary->toggle_count, info->toggle_count);
5936 * Zero toggle count; must remove this tag from the list.
5939 if (prevPtr == NULL)
5941 node->summary = summary->next;
5945 prevPtr->next = summary->next;
5947 summary_destroy (summary);
5952 * This tag isn't currently in the summary information list.
5955 if (rootLevel == node->level)
5959 * The old tag root is at the same level in the tree as this
5960 * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode. Move the tag root up
5961 * a level, in the hopes that it will now cover this GtkTextBTreeNode
5962 * as well as the old root (if not, we'll move it up again
5963 * the next time through the loop). To push it up one level
5964 * we copy the original toggle count into the summary
5965 * information at the old root and change the root to its
5966 * parent GtkTextBTreeNode.
5969 GtkTextBTreeNode *rootnode = info->tag_root;
5970 summary = (Summary *) g_malloc (sizeof (Summary));
5971 summary->info = info;
5972 summary->toggle_count = info->toggle_count - delta;
5973 summary->next = rootnode->summary;
5974 rootnode->summary = summary;
5975 rootnode = rootnode->parent;
5976 rootLevel = rootnode->level;
5977 info->tag_root = rootnode;
5979 summary = (Summary *) g_malloc (sizeof (Summary));
5980 summary->info = info;
5981 summary->toggle_count = delta;
5982 summary->next = node->summary;
5983 node->summary = summary;
5988 * If we've decremented the toggle count, then it may be necessary
5989 * to push the tag root down one or more levels.
5996 if (info->toggle_count == 0)
5998 info->tag_root = (GtkTextBTreeNode *) NULL;
6001 node = info->tag_root;
6002 while (node->level > 0)
6005 * See if a single child GtkTextBTreeNode accounts for all of the tag's
6006 * toggles. If so, push the root down one level.
6009 for (node2Ptr = node->children.node;
6010 node2Ptr != (GtkTextBTreeNode *)NULL ;
6011 node2Ptr = node2Ptr->next)
6013 for (prevPtr = NULL, summary = node2Ptr->summary;
6015 prevPtr = summary, summary = summary->next)
6017 if (summary->info == info)
6022 if (summary == NULL)
6026 if (summary->toggle_count != info->toggle_count)
6029 * No GtkTextBTreeNode has all toggles, so the root is still valid.
6036 * This GtkTextBTreeNode has all the toggles, so push down the root.
6039 if (prevPtr == NULL)
6041 node2Ptr->summary = summary->next;
6045 prevPtr->next = summary->next;
6047 summary_destroy (summary);
6048 info->tag_root = node2Ptr;
6051 node = info->tag_root;
6056 *----------------------------------------------------------------------
6060 * This is a utility procedure used by _gtk_text_btree_get_tags. It
6061 * increments the count for a particular tag, adding a new
6062 * entry for that tag if there wasn't one previously.
6068 * The information at *tagInfoPtr may be modified, and the arrays
6069 * may be reallocated to make them larger.
6071 *----------------------------------------------------------------------
6075 inc_count (GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
6080 for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
6081 count > 0; tag_p++, count--)
6085 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
6091 * There isn't currently an entry for this tag, so we have to
6092 * make a new one. If the arrays are full, then enlarge the
6096 if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
6098 GtkTextTag **newTags;
6099 int *newCounts, newSize;
6101 newSize = 2*tagInfoPtr->arraySize;
6102 newTags = (GtkTextTag **) g_malloc ((unsigned)
6103 (newSize*sizeof (GtkTextTag *)));
6104 memcpy ((void *) newTags, (void *) tagInfoPtr->tags,
6105 tagInfoPtr->arraySize *sizeof (GtkTextTag *));
6106 g_free ((char *) tagInfoPtr->tags);
6107 tagInfoPtr->tags = newTags;
6108 newCounts = (int *) g_malloc ((unsigned) (newSize*sizeof (int)));
6109 memcpy ((void *) newCounts, (void *) tagInfoPtr->counts,
6110 tagInfoPtr->arraySize *sizeof (int));
6111 g_free ((char *) tagInfoPtr->counts);
6112 tagInfoPtr->counts = newCounts;
6113 tagInfoPtr->arraySize = newSize;
6116 tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
6117 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
6118 tagInfoPtr->numTags++;
6122 gtk_text_btree_link_segment (GtkTextLineSegment *seg,
6123 const GtkTextIter *iter)
6125 GtkTextLineSegment *prev;
6129 line = _gtk_text_iter_get_text_line (iter);
6130 tree = _gtk_text_iter_get_btree (iter);
6132 prev = gtk_text_line_segment_split (iter);
6135 seg->next = line->segments;
6136 line->segments = seg;
6140 seg->next = prev->next;
6143 cleanup_line (line);
6144 segments_changed (tree);
6146 if (gtk_debug_flags & GTK_DEBUG_TEXT)
6147 _gtk_text_btree_check (tree);
6151 gtk_text_btree_unlink_segment (GtkTextBTree *tree,
6152 GtkTextLineSegment *seg,
6155 GtkTextLineSegment *prev;
6157 if (line->segments == seg)
6159 line->segments = seg->next;
6163 for (prev = line->segments; prev->next != seg;
6166 /* Empty loop body. */
6168 prev->next = seg->next;
6170 cleanup_line (line);
6171 segments_changed (tree);
6175 * This is here because it requires BTree internals, it logically
6176 * belongs in gtktextsegment.c
6181 *--------------------------------------------------------------
6183 * _gtk_toggle_segment_check_func --
6185 * This procedure is invoked to perform consistency checks
6186 * on toggle segments.
6192 * If a consistency problem is found the procedure g_errors.
6194 *--------------------------------------------------------------
6198 _gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6204 if (segPtr->byte_count != 0)
6206 g_error ("toggle_segment_check_func: segment had non-zero size");
6208 if (!segPtr->body.toggle.inNodeCounts)
6210 g_error ("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6212 needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6213 for (summary = line->parent->summary; ;
6214 summary = summary->next)
6216 if (summary == NULL)
6220 g_error ("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6227 if (summary->info == segPtr->body.toggle.info)
6231 g_error ("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6243 gtk_text_btree_node_view_check_consistency (GtkTextBTree *tree,
6244 GtkTextBTreeNode *node,
6254 while (view != NULL)
6256 if (view->view_id == nd->view_id)
6263 g_error ("Node has data for a view %p no longer attached to the tree",
6266 gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6267 &width, &height, &valid);
6268 if (nd->width != width ||
6269 nd->height != height ||
6270 !nd->valid != !valid)
6272 g_error ("Node aggregates for view %p are invalid:\n"
6273 "Are (%d,%d,%s), should be (%d,%d,%s)",
6275 nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6276 width, height, valid ? "TRUE" : "FALSE");
6281 gtk_text_btree_node_check_consistency (GtkTextBTree *tree,
6282 GtkTextBTreeNode *node)
6284 GtkTextBTreeNode *childnode;
6285 Summary *summary, *summary2;
6287 GtkTextLineSegment *segPtr;
6288 int num_children, num_lines, num_chars, toggle_count, min_children;
6289 GtkTextLineData *ld;
6292 if (node->parent != NULL)
6294 min_children = MIN_CHILDREN;
6296 else if (node->level > 0)
6303 if ((node->num_children < min_children)
6304 || (node->num_children > MAX_CHILDREN))
6306 g_error ("gtk_text_btree_node_check_consistency: bad child count (%d)",
6307 node->num_children);
6310 nd = node->node_data;
6313 gtk_text_btree_node_view_check_consistency (tree, node, nd);
6320 if (node->level == 0)
6322 for (line = node->children.line; line != NULL;
6325 if (line->parent != node)
6327 g_error ("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6329 if (line->segments == NULL)
6331 g_error ("gtk_text_btree_node_check_consistency: line has no segments");
6337 /* Just ensuring we don't segv while doing this loop */
6342 for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6344 if (segPtr->type->checkFunc != NULL)
6346 (*segPtr->type->checkFunc)(segPtr, line);
6348 if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6349 && (segPtr->next != NULL)
6350 && (segPtr->next->byte_count == 0)
6351 && (segPtr->next->type->leftGravity))
6353 g_error ("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6355 if ((segPtr->next == NULL)
6356 && (segPtr->type != >k_text_char_type))
6358 g_error ("gtk_text_btree_node_check_consistency: line ended with wrong type");
6361 num_chars += segPtr->char_count;
6370 for (childnode = node->children.node; childnode != NULL;
6371 childnode = childnode->next)
6373 if (childnode->parent != node)
6375 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6377 if (childnode->level != (node->level-1))
6379 g_error ("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6380 node->level, childnode->level);
6382 gtk_text_btree_node_check_consistency (tree, childnode);
6383 for (summary = childnode->summary; summary != NULL;
6384 summary = summary->next)
6386 for (summary2 = node->summary; ;
6387 summary2 = summary2->next)
6389 if (summary2 == NULL)
6391 if (summary->info->tag_root == node)
6395 g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6396 summary->info->tag->name,
6397 "present in parent summaries");
6399 if (summary->info == summary2->info)
6406 num_lines += childnode->num_lines;
6407 num_chars += childnode->num_chars;
6410 if (num_children != node->num_children)
6412 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6413 num_children, node->num_children);
6415 if (num_lines != node->num_lines)
6417 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6418 num_lines, node->num_lines);
6420 if (num_chars != node->num_chars)
6422 g_error ("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6423 num_chars, node->num_chars);
6426 for (summary = node->summary; summary != NULL;
6427 summary = summary->next)
6429 if (summary->info->toggle_count == summary->toggle_count)
6431 g_error ("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6432 summary->info->tag->name);
6435 if (node->level == 0)
6437 for (line = node->children.line; line != NULL;
6440 for (segPtr = line->segments; segPtr != NULL;
6441 segPtr = segPtr->next)
6443 if ((segPtr->type != >k_text_toggle_on_type)
6444 && (segPtr->type != >k_text_toggle_off_type))
6448 if (segPtr->body.toggle.info == summary->info)
6450 if (!segPtr->body.toggle.inNodeCounts)
6451 g_error ("Toggle segment not in the node counts");
6460 for (childnode = node->children.node;
6462 childnode = childnode->next)
6464 for (summary2 = childnode->summary;
6466 summary2 = summary2->next)
6468 if (summary2->info == summary->info)
6470 toggle_count += summary2->toggle_count;
6475 if (toggle_count != summary->toggle_count)
6477 g_error ("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6478 toggle_count, summary->toggle_count);
6480 for (summary2 = summary->next; summary2 != NULL;
6481 summary2 = summary2->next)
6483 if (summary2->info == summary->info)
6485 g_error ("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6486 summary->info->tag->name);
6493 listify_foreach (GtkTextTag *tag, gpointer user_data)
6495 GSList** listp = user_data;
6497 *listp = g_slist_prepend (*listp, tag);
6501 list_of_tags (GtkTextTagTable *table)
6503 GSList *list = NULL;
6505 gtk_text_tag_table_foreach (table, listify_foreach, &list);
6511 _gtk_text_btree_check (GtkTextBTree *tree)
6514 GtkTextBTreeNode *node;
6516 GtkTextLineSegment *seg;
6518 GSList *taglist = NULL;
6520 GtkTextTagInfo *info;
6523 * Make sure that the tag toggle counts and the tag root pointers are OK.
6525 for (taglist = list_of_tags (tree->table);
6526 taglist != NULL ; taglist = taglist->next)
6528 tag = taglist->data;
6529 info = gtk_text_btree_get_existing_tag_info (tree, tag);
6532 node = info->tag_root;
6535 if (info->toggle_count != 0)
6537 g_error ("_gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6538 tag->name, info->toggle_count);
6540 continue; /* no ranges for the tag */
6542 else if (info->toggle_count == 0)
6544 g_error ("_gtk_text_btree_check found root for \"%s\" with no toggles",
6547 else if (info->toggle_count & 1)
6549 g_error ("_gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6550 tag->name, info->toggle_count);
6552 for (summary = node->summary; summary != NULL;
6553 summary = summary->next)
6555 if (summary->info->tag == tag)
6557 g_error ("_gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6561 if (node->level > 0)
6563 for (node = node->children.node ; node != NULL ;
6566 for (summary = node->summary; summary != NULL;
6567 summary = summary->next)
6569 if (summary->info->tag == tag)
6571 count += summary->toggle_count;
6578 GtkTextLineSegmentClass * last = NULL;
6580 for (line = node->children.line ; line != NULL ;
6583 for (seg = line->segments; seg != NULL;
6586 if ((seg->type == >k_text_toggle_on_type ||
6587 seg->type == >k_text_toggle_off_type) &&
6588 seg->body.toggle.info->tag == tag)
6590 if (last == seg->type)
6591 g_error ("Two consecutive toggles on or off weren't merged");
6592 if (!seg->body.toggle.inNodeCounts)
6593 g_error ("Toggle segment not in the node counts");
6602 if (count != info->toggle_count)
6604 g_error ("_gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
6605 info->toggle_count, tag->name, count);
6610 g_slist_free (taglist);
6614 * Call a recursive procedure to do the main body of checks.
6617 node = tree->root_node;
6618 gtk_text_btree_node_check_consistency (tree, tree->root_node);
6621 * Make sure that there are at least two lines in the text and
6622 * that the last line has no characters except a newline.
6625 if (node->num_lines < 2)
6627 g_error ("_gtk_text_btree_check: less than 2 lines in tree");
6629 if (node->num_chars < 2)
6631 g_error ("_gtk_text_btree_check: less than 2 chars in tree");
6633 while (node->level > 0)
6635 node = node->children.node;
6636 while (node->next != NULL)
6641 line = node->children.line;
6642 while (line->next != NULL)
6646 seg = line->segments;
6647 while ((seg->type == >k_text_toggle_off_type)
6648 || (seg->type == >k_text_right_mark_type)
6649 || (seg->type == >k_text_left_mark_type))
6652 * It's OK to toggle a tag off in the last line, but
6653 * not to start a new range. It's also OK to have marks
6659 if (seg->type != >k_text_char_type)
6661 g_error ("_gtk_text_btree_check: last line has bogus segment type");
6663 if (seg->next != NULL)
6665 g_error ("_gtk_text_btree_check: last line has too many segments");
6667 if (seg->byte_count != 1)
6669 g_error ("_gtk_text_btree_check: last line has wrong # characters: %d",
6672 if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
6674 g_error ("_gtk_text_btree_check: last line had bad value: %s",
6679 void _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line);
6680 void _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment* seg);
6681 void _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent);
6682 void _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
6685 _gtk_text_btree_spew (GtkTextBTree *tree)
6690 printf ("%d lines in tree %p\n",
6691 _gtk_text_btree_line_count (tree), tree);
6693 line = _gtk_text_btree_get_line (tree, 0, &real_line);
6695 while (line != NULL)
6697 _gtk_text_btree_spew_line (tree, line);
6698 line = _gtk_text_line_next (line);
6701 printf ("=================== Tag information\n");
6706 list = tree->tag_infos;
6708 while (list != NULL)
6710 GtkTextTagInfo *info;
6714 printf (" tag `%s': root at %p, toggle count %d\n",
6715 info->tag->name, info->tag_root, info->toggle_count);
6717 list = g_slist_next (list);
6720 if (tree->tag_infos == NULL)
6722 printf (" (no tags in the tree)\n");
6726 printf ("=================== Tree nodes\n");
6729 _gtk_text_btree_spew_node (tree->root_node, 0);
6734 _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
6737 GtkTextLineSegment *seg;
6739 spaces = g_strnfill (indent, ' ');
6741 printf ("%sline %p chars %d bytes %d\n",
6743 _gtk_text_line_char_count (line),
6744 _gtk_text_line_byte_count (line));
6746 seg = line->segments;
6749 if (seg->type == >k_text_char_type)
6751 gchar* str = g_strndup (seg->body.chars, MIN (seg->byte_count, 10));
6756 if (*s == '\n' || *s == '\r')
6760 printf ("%s chars `%s'...\n", spaces, str);
6763 else if (seg->type == >k_text_right_mark_type)
6765 printf ("%s right mark `%s' visible: %d\n",
6767 seg->body.mark.name,
6768 seg->body.mark.visible);
6770 else if (seg->type == >k_text_left_mark_type)
6772 printf ("%s left mark `%s' visible: %d\n",
6774 seg->body.mark.name,
6775 seg->body.mark.visible);
6777 else if (seg->type == >k_text_toggle_on_type ||
6778 seg->type == >k_text_toggle_off_type)
6780 printf ("%s tag `%s' %s\n",
6781 spaces, seg->body.toggle.info->tag->name,
6782 seg->type == >k_text_toggle_off_type ? "off" : "on");
6792 _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent)
6795 GtkTextBTreeNode *iter;
6798 spaces = g_strnfill (indent, ' ');
6800 printf ("%snode %p level %d children %d lines %d chars %d\n",
6801 spaces, node, node->level,
6802 node->num_children, node->num_lines, node->num_chars);
6807 printf ("%s %d toggles of `%s' below this node\n",
6808 spaces, s->toggle_count, s->info->tag->name);
6814 if (node->level > 0)
6816 iter = node->children.node;
6817 while (iter != NULL)
6819 _gtk_text_btree_spew_node (iter, indent + 2);
6826 GtkTextLine *line = node->children.line;
6827 while (line != NULL)
6829 _gtk_text_btree_spew_line_short (line, indent + 2);
6837 _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line)
6839 GtkTextLineSegment * seg;
6841 printf ("%4d| line: %p parent: %p next: %p\n",
6842 _gtk_text_line_get_number (line), line, line->parent, line->next);
6844 seg = line->segments;
6848 _gtk_text_btree_spew_segment (tree, seg);
6854 _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment * seg)
6856 printf (" segment: %p type: %s bytes: %d chars: %d\n",
6857 seg, seg->type->name, seg->byte_count, seg->char_count);
6859 if (seg->type == >k_text_char_type)
6861 gchar* str = g_strndup (seg->body.chars, seg->byte_count);
6862 printf (" `%s'\n", str);
6865 else if (seg->type == >k_text_right_mark_type)
6867 printf (" right mark `%s' visible: %d not_deleteable: %d\n",
6868 seg->body.mark.name,
6869 seg->body.mark.visible,
6870 seg->body.mark.not_deleteable);
6872 else if (seg->type == >k_text_left_mark_type)
6874 printf (" left mark `%s' visible: %d not_deleteable: %d\n",
6875 seg->body.mark.name,
6876 seg->body.mark.visible,
6877 seg->body.mark.not_deleteable);
6879 else if (seg->type == >k_text_toggle_on_type ||
6880 seg->type == >k_text_toggle_off_type)
6882 printf (" tag `%s' priority %d\n",
6883 seg->body.toggle.info->tag->name,
6884 seg->body.toggle.info->tag->priority);