diff options
| -rw-r--r-- | gtk/gtkcssrbtreeprivate.h | 90 | ||||
| -rw-r--r-- | gtk/gtkfilterlistmodel.c | 82 | ||||
| -rw-r--r-- | gtk/gtkflattenlistmodel.c | 72 | ||||
| -rw-r--r-- | gtk/gtkmaplistmodel.c | 80 | ||||
| -rw-r--r-- | gtk/gtkrbtree.c (renamed from gtk/gtkcssrbtree.c) | 300 | ||||
| -rw-r--r-- | gtk/gtkrbtreeprivate.h | 89 | ||||
| -rw-r--r-- | gtk/gtkslicelistmodel.c | 1 | ||||
| -rw-r--r-- | gtk/gtktreelistmodel.c | 104 | ||||
| -rw-r--r-- | gtk/meson.build | 2 | ||||
| -rw-r--r-- | testsuite/gtk/meson.build | 2 | ||||
| -rw-r--r-- | testsuite/gtk/rbtree-crash.c (renamed from testsuite/gtk/cssrbtree-crash.c) | 64 |
11 files changed, 442 insertions, 444 deletions
diff --git a/gtk/gtkcssrbtreeprivate.h b/gtk/gtkcssrbtreeprivate.h deleted file mode 100644 index f80108dba8..0000000000 --- a/gtk/gtkcssrbtreeprivate.h +++ /dev/null @@ -1,90 +0,0 @@ -/* gtkrb_tree.h - * Copyright (C) 2000 Red Hat, Inc., Jonathan Blandford <jrb@redhat.com> - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Library General Public - * License as published by the Free Software Foundation; either - * version 2 of the License, or (at your option) any later version. - * - * This library is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * Library General Public License for more details. - * - * You should have received a copy of the GNU Library General Public - * License along with this library. If not, see <http://www.gnu.org/licenses/>. - */ - -/* A Red-Black Tree implementation used specifically by GtkTreeView. - */ -#ifndef __GTK_CSS_RB_TREE_H__ -#define __GTK_CSS_RB_TREE_H__ - -#include <glib.h> - - -G_BEGIN_DECLS - - -typedef struct _GtkCssRbTree GtkCssRbTree; - -typedef void (* GtkCssRbTreeAugmentFunc) (GtkCssRbTree *tree, - gpointer node_augment, - gpointer node, - gpointer left, - gpointer right); -typedef int (* GtkCssRbTreeFindFunc) (GtkCssRbTree *tree, - gpointer node, - gpointer user_data); - -GtkCssRbTree * gtk_css_rb_tree_new_for_size (gsize element_size, - gsize augment_size, - GtkCssRbTreeAugmentFunc augment_func, - GDestroyNotify clear_func, - GDestroyNotify clear_augment_func); -#define gtk_css_rb_tree_new(type, augment_type, augment_func, clear_func, clear_augment_func) \ - gtk_css_rb_tree_new_for_size (sizeof (type), sizeof (augment_type), (augment_func), (clear_func), (clear_augment_func)) - -GtkCssRbTree * gtk_css_rb_tree_ref (GtkCssRbTree *tree); -void gtk_css_rb_tree_unref (GtkCssRbTree *tree); - -gpointer gtk_css_rb_tree_get_first (GtkCssRbTree *tree); -gpointer gtk_css_rb_tree_get_last (GtkCssRbTree *tree); -gpointer gtk_css_rb_tree_get_previous (GtkCssRbTree *tree, - gpointer node); -gpointer gtk_css_rb_tree_get_next (GtkCssRbTree *tree, - gpointer node); - -gpointer gtk_css_rb_tree_get_root (GtkCssRbTree *tree); -gpointer gtk_css_rb_tree_get_parent (GtkCssRbTree *tree, - gpointer node); -gpointer gtk_css_rb_tree_get_left (GtkCssRbTree *tree, - gpointer node); -gpointer gtk_css_rb_tree_get_right (GtkCssRbTree *tree, - gpointer node); -gpointer gtk_css_rb_tree_get_augment (GtkCssRbTree *tree, - gpointer node); - -void gtk_css_rb_tree_mark_dirty (GtkCssRbTree *tree, - gpointer node); - -gpointer gtk_css_rb_tree_insert_before (GtkCssRbTree *tree, - gpointer node); -gpointer gtk_css_rb_tree_insert_after (GtkCssRbTree *tree, - gpointer node); -void gtk_css_rb_tree_remove (GtkCssRbTree *tree, - gpointer node); -void gtk_css_rb_tree_remove_all (GtkCssRbTree *tree); - -gpointer gtk_css_rb_tree_find (GtkCssRbTree *tree, - gpointer *out_before, - gpointer *out_after, - GtkCssRbTreeFindFunc find_func, - gpointer user_data); - - - -G_END_DECLS - - -#endif /* __GTK_CSS_RB_TREE_H__ */ diff --git a/gtk/gtkfilterlistmodel.c b/gtk/gtkfilterlistmodel.c index bf2ced74e5..aa5abe8df2 100644 --- a/gtk/gtkfilterlistmodel.c +++ b/gtk/gtkfilterlistmodel.c @@ -21,7 +21,7 @@ #include "gtkfilterlistmodel.h" -#include "gtkcssrbtreeprivate.h" +#include "gtkrbtreeprivate.h" #include "gtkintl.h" #include "gtkprivate.h" @@ -69,7 +69,7 @@ struct _GtkFilterListModel gpointer user_data; GDestroyNotify user_destroy; - GtkCssRbTree *items; /* NULL if filter_func == NULL */ + GtkRbTree *items; /* NULL if filter_func == NULL */ }; struct _GtkFilterListModelClass @@ -80,22 +80,22 @@ struct _GtkFilterListModelClass static GParamSpec *properties[NUM_PROPERTIES] = { NULL, }; static FilterNode * -gtk_filter_list_model_get_nth_filtered (GtkCssRbTree *tree, - guint position, - guint *out_unfiltered) +gtk_filter_list_model_get_nth_filtered (GtkRbTree *tree, + guint position, + guint *out_unfiltered) { FilterNode *node, *tmp; guint unfiltered; - node = gtk_css_rb_tree_get_root (tree); + node = gtk_rb_tree_get_root (tree); unfiltered = 0; while (node) { - tmp = gtk_css_rb_tree_get_left (tree, node); + tmp = gtk_rb_tree_get_left (tree, node); if (tmp) { - FilterAugment *aug = gtk_css_rb_tree_get_augment (tree, tmp); + FilterAugment *aug = gtk_rb_tree_get_augment (tree, tmp); if (position < aug->n_visible) { node = tmp; @@ -114,7 +114,7 @@ gtk_filter_list_model_get_nth_filtered (GtkCssRbTree *tree, unfiltered++; - node = gtk_css_rb_tree_get_right (tree, node); + node = gtk_rb_tree_get_right (tree, node); } if (out_unfiltered) @@ -124,22 +124,22 @@ gtk_filter_list_model_get_nth_filtered (GtkCssRbTree *tree, } static FilterNode * -gtk_filter_list_model_get_nth (GtkCssRbTree *tree, - guint position, - guint *out_filtered) +gtk_filter_list_model_get_nth (GtkRbTree *tree, + guint position, + guint *out_filtered) { FilterNode *node, *tmp; guint filtered; - node = gtk_css_rb_tree_get_root (tree); + node = gtk_rb_tree_get_root (tree); filtered = 0; while (node) { - tmp = gtk_css_rb_tree_get_left (tree, node); + tmp = gtk_rb_tree_get_left (tree, node); if (tmp) { - FilterAugment *aug = gtk_css_rb_tree_get_augment (tree, tmp); + FilterAugment *aug = gtk_rb_tree_get_augment (tree, tmp); if (position < aug->n_items) { node = tmp; @@ -156,7 +156,7 @@ gtk_filter_list_model_get_nth (GtkCssRbTree *tree, if (node->visible) filtered++; - node = gtk_css_rb_tree_get_right (tree, node); + node = gtk_rb_tree_get_right (tree, node); } if (out_filtered) @@ -186,11 +186,11 @@ gtk_filter_list_model_get_n_items (GListModel *list) if (!self->items) return g_list_model_get_n_items (self->model); - node = gtk_css_rb_tree_get_root (self->items); + node = gtk_rb_tree_get_root (self->items); if (node == NULL) return 0; - aug = gtk_css_rb_tree_get_augment (self->items, node); + aug = gtk_rb_tree_get_augment (self->items, node); return aug->n_visible; } @@ -250,7 +250,7 @@ gtk_filter_list_model_add_items (GtkFilterListModel *self, for (i = 0; i < n_items; i++) { - node = gtk_css_rb_tree_insert_before (self->items, after); + node = gtk_rb_tree_insert_before (self->items, after); node->visible = gtk_filter_list_model_run_filter (self, position + i); if (node->visible) n_visible++; @@ -280,10 +280,10 @@ gtk_filter_list_model_items_changed_cb (GListModel *model, filter_removed = 0; for (i = 0; i < removed; i++) { - FilterNode *next = gtk_css_rb_tree_get_next (self->items, node); + FilterNode *next = gtk_rb_tree_get_next (self->items, node); if (node->visible) filter_removed++; - gtk_css_rb_tree_remove (self->items, node); + gtk_rb_tree_remove (self->items, node); node = next; } @@ -354,7 +354,7 @@ gtk_filter_list_model_clear_model (GtkFilterListModel *self) g_signal_handlers_disconnect_by_func (self->model, gtk_filter_list_model_items_changed_cb, self); g_clear_object (&self->model); if (self->items) - gtk_css_rb_tree_remove_all (self->items); + gtk_rb_tree_remove_all (self->items); } static void @@ -368,10 +368,10 @@ gtk_filter_list_model_dispose (GObject *object) self->filter_func = NULL; self->user_data = NULL; self->user_destroy = NULL; - g_clear_pointer (&self->items, gtk_css_rb_tree_unref); + g_clear_pointer (&self->items, gtk_rb_tree_unref); G_OBJECT_CLASS (gtk_filter_list_model_parent_class)->dispose (object); -}; +} static void gtk_filter_list_model_class_init (GtkFilterListModelClass *class) @@ -428,13 +428,13 @@ gtk_filter_list_model_init (GtkFilterListModel *self) static void -gtk_filter_list_model_augment (GtkCssRbTree *filter, - gpointer _aug, - gpointer _node, - gpointer left, - gpointer right) +gtk_filter_list_model_augment (GtkRbTree *filter, + gpointer _aug, + gpointer _node, + gpointer left, + gpointer right) { - FilterNode *node= _node; + FilterNode *node = _node; FilterAugment *aug = _aug; aug->n_items = 1; @@ -442,13 +442,13 @@ gtk_filter_list_model_augment (GtkCssRbTree *filter, if (left) { - FilterAugment *left_aug = gtk_css_rb_tree_get_augment (filter, left); + FilterAugment *left_aug = gtk_rb_tree_get_augment (filter, left); aug->n_items += left_aug->n_items; aug->n_visible += left_aug->n_visible; } if (right) { - FilterAugment *right_aug = gtk_css_rb_tree_get_augment (filter, right); + FilterAugment *right_aug = gtk_rb_tree_get_augment (filter, right); aug->n_items += right_aug->n_items; aug->n_visible += right_aug->n_visible; } @@ -543,22 +543,22 @@ gtk_filter_list_model_set_filter_func (GtkFilterListModel *self, if (!will_be_filtered) { - g_clear_pointer (&self->items, gtk_css_rb_tree_unref); + g_clear_pointer (&self->items, gtk_rb_tree_unref); } else if (!was_filtered) { guint i, n_items; - self->items = gtk_css_rb_tree_new (FilterNode, - FilterAugment, - gtk_filter_list_model_augment, - NULL, NULL); + self->items = gtk_rb_tree_new (FilterNode, + FilterAugment, + gtk_filter_list_model_augment, + NULL, NULL); if (self->model) { n_items = g_list_model_get_n_items (self->model); for (i = 0; i < n_items; i++) { - FilterNode *node = gtk_css_rb_tree_insert_before (self->items, NULL); + FilterNode *node = gtk_rb_tree_insert_before (self->items, NULL); node->visible = TRUE; } } @@ -675,9 +675,9 @@ gtk_filter_list_model_refilter (GtkFilterListModel *self) last_change = 0; n_is_visible = 0; n_was_visible = 0; - for (i = 0, node = gtk_css_rb_tree_get_first (self->items); + for (i = 0, node = gtk_rb_tree_get_first (self->items); node != NULL; - i++, node = gtk_css_rb_tree_get_next (self->items, node)) + i++, node = gtk_rb_tree_get_next (self->items, node)) { visible = gtk_filter_list_model_run_filter (self, i); if (visible == node->visible) @@ -691,7 +691,7 @@ gtk_filter_list_model_refilter (GtkFilterListModel *self) } node->visible = visible; - gtk_css_rb_tree_mark_dirty (self->items, node); + gtk_rb_tree_mark_dirty (self->items, node); first_change = MIN (n_is_visible, first_change); if (visible) n_is_visible++; diff --git a/gtk/gtkflattenlistmodel.c b/gtk/gtkflattenlistmodel.c index b7066742b7..58852061e2 100644 --- a/gtk/gtkflattenlistmodel.c +++ b/gtk/gtkflattenlistmodel.c @@ -21,7 +21,7 @@ #include "gtkflattenlistmodel.h" -#include "gtkcssrbtreeprivate.h" +#include "gtkrbtreeprivate.h" #include "gtkintl.h" #include "gtkprivate.h" @@ -66,7 +66,7 @@ struct _GtkFlattenListModel GType item_type; GListModel *model; - GtkCssRbTree *items; /* NULL if model == NULL */ + GtkRbTree *items; /* NULL if model == NULL */ }; struct _GtkFlattenListModelClass @@ -77,21 +77,21 @@ struct _GtkFlattenListModelClass static GParamSpec *properties[NUM_PROPERTIES] = { NULL, }; static FlattenNode * -gtk_flatten_list_model_get_nth (GtkCssRbTree *tree, +gtk_flatten_list_model_get_nth (GtkRbTree *tree, guint position, guint *model_position) { FlattenNode *node, *tmp; guint model_n_items; - node = gtk_css_rb_tree_get_root (tree); + node = gtk_rb_tree_get_root (tree); while (node) { - tmp = gtk_css_rb_tree_get_left (tree, node); + tmp = gtk_rb_tree_get_left (tree, node); if (tmp) { - FlattenAugment *aug = gtk_css_rb_tree_get_augment (tree, tmp); + FlattenAugment *aug = gtk_rb_tree_get_augment (tree, tmp); if (position < aug->n_items) { node = tmp; @@ -105,7 +105,7 @@ gtk_flatten_list_model_get_nth (GtkCssRbTree *tree, break; position -= model_n_items; - node = gtk_css_rb_tree_get_right (tree, node); + node = gtk_rb_tree_get_right (tree, node); } if (model_position) @@ -115,22 +115,22 @@ gtk_flatten_list_model_get_nth (GtkCssRbTree *tree, } static FlattenNode * -gtk_flatten_list_model_get_nth_model (GtkCssRbTree *tree, +gtk_flatten_list_model_get_nth_model (GtkRbTree *tree, guint position, guint *items_before) { FlattenNode *node, *tmp; guint before; - node = gtk_css_rb_tree_get_root (tree); + node = gtk_rb_tree_get_root (tree); before = 0; while (node) { - tmp = gtk_css_rb_tree_get_left (tree, node); + tmp = gtk_rb_tree_get_left (tree, node); if (tmp) { - FlattenAugment *aug = gtk_css_rb_tree_get_augment (tree, tmp); + FlattenAugment *aug = gtk_rb_tree_get_augment (tree, tmp); if (position < aug->n_models) { node = tmp; @@ -145,7 +145,7 @@ gtk_flatten_list_model_get_nth_model (GtkCssRbTree *tree, position--; before += g_list_model_get_n_items (node->model); - node = gtk_css_rb_tree_get_right (tree, node); + node = gtk_rb_tree_get_right (tree, node); } if (items_before) @@ -172,11 +172,11 @@ gtk_flatten_list_model_get_n_items (GListModel *list) if (!self->items) return 0; - node = gtk_css_rb_tree_get_root (self->items); + node = gtk_rb_tree_get_root (self->items); if (node == NULL) return 0; - aug = gtk_css_rb_tree_get_augment (self->items, node); + aug = gtk_rb_tree_get_augment (self->items, node); return aug->n_items; } @@ -220,18 +220,18 @@ gtk_flatten_list_model_items_changed_cb (GListModel *model, GtkFlattenListModel *self = node->list; guint real_position; - gtk_css_rb_tree_mark_dirty (self->items, node); + gtk_rb_tree_mark_dirty (self->items, node); for (real_position = position; - (parent = gtk_css_rb_tree_get_parent (self->items, node)) != NULL; + (parent = gtk_rb_tree_get_parent (self->items, node)) != NULL; node = parent) { - FlattenNode *left = gtk_css_rb_tree_get_left (self->items, parent); + FlattenNode *left = gtk_rb_tree_get_left (self->items, parent); if (left != node) { if (left) { - FlattenAugment *aug = gtk_css_rb_tree_get_augment (self->items, left); + FlattenAugment *aug = gtk_rb_tree_get_augment (self->items, left); real_position += aug->n_items; } real_position += g_list_model_get_n_items (parent->model); @@ -251,13 +251,13 @@ gtk_flatten_list_model_clear_node (gpointer _node) } static void -gtk_flatten_list_model_augment (GtkCssRbTree *flatten, - gpointer _aug, - gpointer _node, - gpointer left, - gpointer right) +gtk_flatten_list_model_augment (GtkRbTree *flatten, + gpointer _aug, + gpointer _node, + gpointer left, + gpointer right) { - FlattenNode *node= _node; + FlattenNode *node = _node; FlattenAugment *aug = _aug; aug->n_items = g_list_model_get_n_items (node->model); @@ -265,13 +265,13 @@ gtk_flatten_list_model_augment (GtkCssRbTree *flatten, if (left) { - FlattenAugment *left_aug = gtk_css_rb_tree_get_augment (flatten, left); + FlattenAugment *left_aug = gtk_rb_tree_get_augment (flatten, left); aug->n_items += left_aug->n_items; aug->n_models += left_aug->n_models; } if (right) { - FlattenAugment *right_aug = gtk_css_rb_tree_get_augment (flatten, right); + FlattenAugment *right_aug = gtk_rb_tree_get_augment (flatten, right); aug->n_items += right_aug->n_items; aug->n_models += right_aug->n_models; } @@ -289,7 +289,7 @@ gtk_flatten_list_model_add_items (GtkFlattenListModel *self, added = 0; for (i = 0; i < n; i++) { - node = gtk_css_rb_tree_insert_before (self->items, after); + node = gtk_rb_tree_insert_before (self->items, after); node->model = g_list_model_get_item (self->model, position + i); g_warn_if_fail (g_type_is_a (g_list_model_get_item_type (node->model), self->item_type)); g_signal_connect (node->model, @@ -366,9 +366,9 @@ gtk_flatten_list_model_model_items_changed_cb (GListModel *model, real_removed = 0; for (i = 0; i < removed; i++) { - FlattenNode *next = gtk_css_rb_tree_get_next (self->items, node); + FlattenNode *next = gtk_rb_tree_get_next (self->items, node); real_removed += g_list_model_get_n_items (node->model); - gtk_css_rb_tree_remove (self->items, node); + gtk_rb_tree_remove (self->items, node); node = next; } @@ -385,7 +385,7 @@ gtk_flatten_list_clear_model (GtkFlattenListModel *self) { g_signal_handlers_disconnect_by_func (self->model, gtk_flatten_list_model_model_items_changed_cb, self); g_clear_object (&self->model); - g_clear_pointer (&self->items, gtk_css_rb_tree_unref); + g_clear_pointer (&self->items, gtk_rb_tree_unref); } } @@ -397,7 +397,7 @@ gtk_flatten_list_model_dispose (GObject *object) gtk_flatten_list_clear_model (self); G_OBJECT_CLASS (gtk_flatten_list_model_parent_class)->dispose (object); -}; +} static void gtk_flatten_list_model_class_init (GtkFlattenListModelClass *class) @@ -501,11 +501,11 @@ gtk_flatten_list_model_set_model (GtkFlattenListModel *self, { g_object_ref (model); g_signal_connect (model, "items-changed", G_CALLBACK (gtk_flatten_list_model_model_items_changed_cb), self); - self->items = gtk_css_rb_tree_new (FlattenNode, - FlattenAugment, - gtk_flatten_list_model_augment, - gtk_flatten_list_model_clear_node, - NULL); + self->items = gtk_rb_tree_new (FlattenNode, + FlattenAugment, + gtk_flatten_list_model_augment, + gtk_flatten_list_model_clear_node, + NULL); added = gtk_flatten_list_model_add_items (self, NULL, 0, g_list_model_get_n_items (model)); } diff --git a/gtk/gtkmaplistmodel.c b/gtk/gtkmaplistmodel.c index 6f5e331d80..9be8aa7922 100644 --- a/gtk/gtkmaplistmodel.c +++ b/gtk/gtkmaplistmodel.c @@ -21,7 +21,7 @@ #include "gtkmaplistmodel.h" -#include "gtkcssrbtreeprivate.h" +#include "gtkrbtreeprivate.h" #include "gtkintl.h" #include "gtkprivate.h" @@ -73,7 +73,7 @@ struct _GtkMapListModel gpointer user_data; GDestroyNotify user_destroy; - GtkCssRbTree *items; /* NULL if map_func == NULL */ + GtkRbTree *items; /* NULL if map_func == NULL */ }; struct _GtkMapListModelClass @@ -84,21 +84,21 @@ struct _GtkMapListModelClass static GParamSpec *properties[NUM_PROPERTIES] = { NULL, }; static MapNode * -gtk_map_list_model_get_nth (GtkCssRbTree *tree, - guint position, - guint *out_start_pos) +gtk_map_list_model_get_nth (GtkRbTree *tree, + guint position, + guint *out_start_pos) { MapNode *node, *tmp; guint start_pos = position; - node = gtk_css_rb_tree_get_root (tree); + node = gtk_rb_tree_get_root (tree); while (node) { - tmp = gtk_css_rb_tree_get_left (tree, node); + tmp = gtk_rb_tree_get_left (tree, node); if (tmp) { - MapAugment *aug = gtk_css_rb_tree_get_augment (tree, tmp); + MapAugment *aug = gtk_rb_tree_get_augment (tree, tmp); if (position < aug->n_items) { node = tmp; @@ -114,7 +114,7 @@ gtk_map_list_model_get_nth (GtkCssRbTree *tree, } position -= node->n_items; - node = gtk_css_rb_tree_get_right (tree, node); + node = gtk_rb_tree_get_right (tree, node); } if (out_start_pos) @@ -165,18 +165,18 @@ gtk_map_list_model_get_item (GListModel *list, if (offset != position) { - MapNode *before = gtk_css_rb_tree_insert_before (self->items, node); + MapNode *before = gtk_rb_tree_insert_before (self->items, node); before->n_items = position - offset; node->n_items -= before->n_items; - gtk_css_rb_tree_mark_dirty (self->items, node); + gtk_rb_tree_mark_dirty (self->items, node); } if (node->n_items > 1) { - MapNode *after = gtk_css_rb_tree_insert_after (self->items, node); + MapNode *after = gtk_rb_tree_insert_after (self->items, node); after->n_items = node->n_items - 1; node->n_items = 1; - gtk_css_rb_tree_mark_dirty (self->items, node); + gtk_rb_tree_mark_dirty (self->items, node); } node->item = self->map_func (g_list_model_get_item (self->model, position), self->user_data); @@ -225,9 +225,9 @@ gtk_map_list_model_items_changed_cb (GListModel *model, end = start + node->n_items; if (start == position && end <= position + removed) { - MapNode *next = gtk_css_rb_tree_get_next (self->items, node); + MapNode *next = gtk_rb_tree_get_next (self->items, node); removed -= node->n_items; - gtk_css_rb_tree_remove (self->items, node); + gtk_rb_tree_remove (self->items, node); node = next; } else @@ -236,16 +236,16 @@ gtk_map_list_model_items_changed_cb (GListModel *model, { node->n_items -= removed; removed = 0; - gtk_css_rb_tree_mark_dirty (self->items, node); + gtk_rb_tree_mark_dirty (self->items, node); } else if (start < position) { guint overlap = node->n_items - (position - start); node->n_items -= overlap; - gtk_css_rb_tree_mark_dirty (self->items, node); + gtk_rb_tree_mark_dirty (self->items, node); removed -= overlap; start = position; - node = gtk_css_rb_tree_get_next (self->items, node); + node = gtk_rb_tree_get_next (self->items, node); } } } @@ -253,12 +253,12 @@ gtk_map_list_model_items_changed_cb (GListModel *model, if (added) { if (node == NULL) - node = gtk_css_rb_tree_insert_before (self->items, NULL); + node = gtk_rb_tree_insert_before (self->items, NULL); else if (node->item) - node = gtk_css_rb_tree_insert_after (self->items, node); + node = gtk_rb_tree_insert_after (self->items, node); node->n_items += added; - gtk_css_rb_tree_mark_dirty (self->items, node); + gtk_rb_tree_mark_dirty (self->items, node); } g_list_model_items_changed (G_LIST_MODEL (self), position, removed, added); @@ -337,10 +337,10 @@ gtk_map_list_model_dispose (GObject *object) self->map_func = NULL; self->user_data = NULL; self->user_destroy = NULL; - g_clear_pointer (&self->items, gtk_css_rb_tree_unref); + g_clear_pointer (&self->items, gtk_rb_tree_unref); G_OBJECT_CLASS (gtk_map_list_model_parent_class)->dispose (object); -}; +} static void gtk_map_list_model_class_init (GtkMapListModelClass *class) @@ -397,25 +397,25 @@ gtk_map_list_model_init (GtkMapListModel *self) static void -gtk_map_list_model_augment (GtkCssRbTree *map, - gpointer _aug, - gpointer _node, - gpointer left, - gpointer right) +gtk_map_list_model_augment (GtkRbTree *map, + gpointer _aug, + gpointer _node, + gpointer left, + gpointer right) { - MapNode *node= _node; + MapNode *node = _node; MapAugment *aug = _aug; aug->n_items = node->n_items; if (left) { - MapAugment *left_aug = gtk_css_rb_tree_get_augment (map, left); + MapAugment *left_aug = gtk_rb_tree_get_augment (map, left); aug->n_items += left_aug->n_items; } if (right) { - MapAugment *right_aug = gtk_css_rb_tree_get_augment (map, right); + MapAugment *right_aug = gtk_rb_tree_get_augment (map, right); aug->n_items += right_aug->n_items; } } @@ -473,28 +473,28 @@ gtk_map_list_model_init_items (GtkMapListModel *self) if (self->items) { - gtk_css_rb_tree_remove_all (self->items); + gtk_rb_tree_remove_all (self->items); } else { - self->items = gtk_css_rb_tree_new (MapNode, - MapAugment, - gtk_map_list_model_augment, - gtk_map_list_model_clear_node, - NULL); + self->items = gtk_rb_tree_new (MapNode, + MapAugment, + gtk_map_list_model_augment, + gtk_map_list_model_clear_node, + NULL); } n_items = g_list_model_get_n_items (self->model); if (n_items) { - MapNode *node = gtk_css_rb_tree_insert_before (self->items, NULL); + MapNode *node = gtk_rb_tree_insert_before (self->items, NULL); node->n_items = g_list_model_get_n_items (self->model); - gtk_css_rb_tree_mark_dirty (self->items, node); + gtk_rb_tree_mark_dirty (self->items, node); } } else { - g_clear_pointer (&self->items, gtk_css_rb_tree_unref); + g_clear_pointer (&self->items, gtk_rb_tree_unref); } } diff --git a/gtk/gtkcssrbtree.c b/gtk/gtkrbtree.c index d791f042b3..a7576ffc2b 100644 --- a/gtk/gtkcssrbtree.c +++ b/gtk/gtkrbtree.c @@ -17,51 +17,51 @@ #include "config.h" -#include "gtkcssrbtreeprivate.h" +#include "gtkrbtreeprivate.h" #include "gtkdebug.h" -typedef struct _GtkCssRbNode GtkCssRbNode; +typedef struct _GtkRbNode GtkRbNode; -struct _GtkCssRbTree +struct _GtkRbTree { guint ref_count; gsize element_size; gsize augment_size; - GtkCssRbTreeAugmentFunc augment_func; + GtkRbTreeAugmentFunc augment_func; GDestroyNotify clear_func; GDestroyNotify clear_augment_func; - GtkCssRbNode *root; + GtkRbNode *root; }; -struct _GtkCssRbNode +struct _GtkRbNode { guint red :1; guint dirty :1; - GtkCssRbNode *left; - GtkCssRbNode *right; - GtkCssRbNode *parent; + GtkRbNode *left; + GtkRbNode *right; + GtkRbNode *parent; }; -#define NODE_FROM_POINTER(ptr) ((GtkCssRbNode *) ((ptr) ? (((guchar *) (ptr)) - sizeof (GtkCssRbNode)) : NULL)) -#define NODE_TO_POINTER(node) ((gpointer) ((node) ? (((guchar *) (node)) + sizeof (GtkCssRbNode)) : NULL)) -#define NODE_TO_AUG_POINTER(tree, node) ((gpointer) ((node) ? (((guchar *) (node)) + sizeof (GtkCssRbNode) + (tree)->element_size) : NULL)) +#define NODE_FROM_POINTER(ptr) ((GtkRbNode *) ((ptr) ? (((guchar *) (ptr)) - sizeof (GtkRbNode)) : NULL)) +#define NODE_TO_POINTER(node) ((gpointer) ((node) ? (((guchar *) (node)) + sizeof (GtkRbNode)) : NULL)) +#define NODE_TO_AUG_POINTER(tree, node) ((gpointer) ((node) ? (((guchar *) (node)) + sizeof (GtkRbNode) + (tree)->element_size) : NULL)) static inline gsize -gtk_css_rb_node_get_size (GtkCssRbTree *tree) +gtk_rb_node_get_size (GtkRbTree *tree) { - return sizeof (GtkCssRbNode) + tree->element_size + tree->augment_size; + return sizeof (GtkRbNode) + tree->element_size + tree->augment_size; } -static GtkCssRbNode * -gtk_css_rb_node_new (GtkCssRbTree *tree) +static GtkRbNode * +gtk_rb_node_new (GtkRbTree *tree) { - GtkCssRbNode *result; + GtkRbNode *result; - result = g_slice_alloc0 (gtk_css_rb_node_get_size (tree)); + result = g_slice_alloc0 (gtk_rb_node_get_size (tree)); result->red = TRUE; result->dirty = TRUE; @@ -70,35 +70,35 @@ gtk_css_rb_node_new (GtkCssRbTree *tree) } static void -gtk_css_rb_node_free (GtkCssRbTree *tree, - GtkCssRbNode *node) +gtk_rb_node_free (GtkRbTree *tree, + GtkRbNode *node) { if (tree->clear_func) tree->clear_func (NODE_TO_POINTER (node)); if (tree->clear_augment_func) tree->clear_augment_func (NODE_TO_AUG_POINTER (tree, node)); - g_slice_free1 (gtk_css_rb_node_get_size (tree), node); + g_slice_free1 (gtk_rb_node_get_size (tree), node); } static void -gtk_css_rb_node_free_deep (GtkCssRbTree *tree, - GtkCssRbNode *node) +gtk_rb_node_free_deep (GtkRbTree *tree, + GtkRbNode *node) { - GtkCssRbNode *right = node->right; + GtkRbNode *right = node->right; if (node->left) - gtk_css_rb_node_free_deep (tree, node->left); + gtk_rb_node_free_deep (tree, node->left); - gtk_css_rb_node_free (tree, node); + gtk_rb_node_free (tree, node); if (right) - gtk_css_rb_node_free_deep (tree, right); + gtk_rb_node_free_deep (tree, right); } static void -gtk_css_rb_node_mark_dirty (GtkCssRbNode *node, - gboolean mark_parent) +gtk_rb_node_mark_dirty (GtkRbNode *node, + gboolean mark_parent) { if (node->dirty) return; @@ -106,12 +106,12 @@ gtk_css_rb_node_mark_dirty (GtkCssRbNode *node, node->dirty = TRUE; if (mark_parent && node->parent) - gtk_css_rb_node_mark_dirty (node->parent, TRUE); + gtk_rb_node_mark_dirty (node->parent, TRUE); } static void -gtk_css_rb_node_clean (GtkCssRbTree *tree, - GtkCssRbNode *node) +gtk_rb_node_clean (GtkRbTree *tree, + GtkRbNode *node) { if (!node->dirty) return; @@ -125,8 +125,8 @@ gtk_css_rb_node_clean (GtkCssRbTree *tree, NODE_TO_POINTER (node->right)); } -static GtkCssRbNode * -gtk_css_rb_node_get_first (GtkCssRbNode *node) +static GtkRbNode * +gtk_rb_node_get_first (GtkRbNode *node) { while (node->left) node = node->left; @@ -134,8 +134,8 @@ gtk_css_rb_node_get_first (GtkCssRbNode *node) return node; } -static GtkCssRbNode * -gtk_css_rb_node_get_last (GtkCssRbNode *node) +static GtkRbNode * +gtk_rb_node_get_last (GtkRbNode *node) { while (node->right) node = node->right; @@ -143,13 +143,13 @@ gtk_css_rb_node_get_last (GtkCssRbNode *node) return node; } -static GtkCssRbNode * -gtk_css_rb_node_get_previous (GtkCssRbNode *node) +static GtkRbNode * +gtk_rb_node_get_previous (GtkRbNode *node) { - GtkCssRbNode *parent; + GtkRbNode *parent; if (node->left) - return gtk_css_rb_node_get_last (node->left); + return gtk_rb_node_get_last (node->left); for (parent = node->parent; parent != NULL; parent = node->parent) { @@ -162,13 +162,13 @@ gtk_css_rb_node_get_previous (GtkCssRbNode *node) return NULL; } -static GtkCssRbNode * -gtk_css_rb_node_get_next (GtkCssRbNode *node) +static GtkRbNode * +gtk_rb_node_get_next (GtkRbNode *node) { - GtkCssRbNode *parent; + GtkRbNode *parent; if (node->right) - return gtk_css_rb_node_get_first (node->right); + return gtk_rb_node_get_first (node->right); for (parent = node->parent; parent != NULL; parent = node->parent) { @@ -182,10 +182,10 @@ gtk_css_rb_node_get_next (GtkCssRbNode *node) } static void -gtk_css_rb_node_rotate_left (GtkCssRbTree *tree, - GtkCssRbNode *node) +gtk_rb_node_rotate_left (GtkRbTree *tree, + GtkRbNode *node) { - GtkCssRbNode *right; + GtkRbNode *right; right = node->right; @@ -209,15 +209,15 @@ gtk_css_rb_node_rotate_left (GtkCssRbTree *tree, right->left = node; node->parent = right; - gtk_css_rb_node_mark_dirty (node, FALSE); - gtk_css_rb_node_mark_dirty (right, FALSE); + gtk_rb_node_mark_dirty (node, FALSE); + gtk_rb_node_mark_dirty (right, FALSE); } static void -gtk_css_rb_node_rotate_right (GtkCssRbTree *tree, - GtkCssRbNode *node) +gtk_rb_node_rotate_right (GtkRbTree *tree, + GtkRbNode *node) { - GtkCssRbNode *left; + GtkRbNode *left; left = node->left; @@ -242,12 +242,12 @@ gtk_css_rb_node_rotate_right (GtkCssRbTree *tree, left->right = node; node->parent = left; - gtk_css_rb_node_mark_dirty (node, FALSE); - gtk_css_rb_node_mark_dirty (left, FALSE); + gtk_rb_node_mark_dirty (node, FALSE); + gtk_rb_node_mark_dirty (left, FALSE); } static gboolean -is_red (GtkCssRbNode *node_or_null) +is_red (GtkRbNode *node_or_null) { if (node_or_null == NULL) return FALSE; @@ -256,13 +256,13 @@ is_red (GtkCssRbNode *node_or_null) } static inline gboolean -is_black (GtkCssRbNode *node_or_null) +is_black (GtkRbNode *node_or_null) { return !is_red (node_or_null); } static void -set_black (GtkCssRbNode *node_or_null) +set_black (GtkRbNode *node_or_null) { if (node_or_null == NULL) return; @@ -271,7 +271,7 @@ set_black (GtkCssRbNode *node_or_null) } static void -set_red (GtkCssRbNode *node_or_null) +set_red (GtkRbNode *node_or_null) { if (node_or_null == NULL) return; @@ -280,8 +280,8 @@ set_red (GtkCssRbNode *node_or_null) } static void -gtk_css_rb_tree_insert_fixup (GtkCssRbTree *tree, - GtkCssRbNode *node) +gtk_rb_tree_insert_fixup (GtkRbTree *tree, + GtkRbNode *node) { /* check Red-Black properties */ @@ -292,7 +292,7 @@ gtk_css_rb_tree_insert_fixup (GtkCssRbTree *tree, if (node->parent == node->parent->parent->left) { - GtkCssRbNode *uncle = node->parent->parent->right; + GtkRbNode *uncle = node->parent->parent->right; if (is_red (uncle)) { @@ -309,18 +309,18 @@ gtk_css_rb_tree_insert_fixup (GtkCssRbTree *tree, { /* make node a left child */ node = node->parent; - gtk_css_rb_node_rotate_left (tree, node); + gtk_rb_node_rotate_left (tree, node); } /* recolor and rotate */ set_black (node->parent); set_red (node->parent->parent); - gtk_css_rb_node_rotate_right (tree, node->parent->parent); + gtk_rb_node_rotate_right (tree, node->parent->parent); } } else { /* mirror image of above code */ - GtkCssRbNode *uncle = node->parent->parent->left; + GtkRbNode *uncle = node->parent->parent->left; if (is_red (uncle)) { @@ -336,11 +336,11 @@ gtk_css_rb_tree_insert_fixup (GtkCssRbTree *tree, if (node == node->parent->left) { node = node->parent; - gtk_css_rb_node_rotate_right (tree, node); + gtk_rb_node_rotate_right (tree, node); } set_black (node->parent); set_red (node->parent->parent); - gtk_css_rb_node_rotate_left (tree, node->parent->parent); + gtk_rb_node_rotate_left (tree, node->parent->parent); } } } @@ -349,21 +349,21 @@ gtk_css_rb_tree_insert_fixup (GtkCssRbTree *tree, } static void -gtk_css_rb_tree_remove_node_fixup (GtkCssRbTree *tree, - GtkCssRbNode *node, - GtkCssRbNode *parent) +gtk_rb_tree_remove_node_fixup (GtkRbTree *tree, + GtkRbNode *node, + GtkRbNode *parent) { while (node != tree->root && is_black (node)) { if (node == parent->left) { - GtkCssRbNode *w = parent->right; + GtkRbNode *w = parent->right; if (is_red (w)) { set_black (w); set_red (parent); - gtk_css_rb_node_rotate_left (tree, parent); + gtk_rb_node_rotate_left (tree, parent); w = parent->right; } if (is_black (w->left) && is_black (w->right)) @@ -377,24 +377,24 @@ gtk_css_rb_tree_remove_node_fixup (GtkCssRbTree *tree, { set_black (w->left); set_red (w); - gtk_css_rb_node_rotate_right (tree, w); + gtk_rb_node_rotate_right (tree, w); w = parent->right; } w->red = parent->red; set_black (parent); set_black (w->right); - gtk_css_rb_node_rotate_left (tree, parent); + gtk_rb_node_rotate_left (tree, parent); node = tree->root; } } else { - GtkCssRbNode *w = parent->left; + GtkRbNode *w = parent->left; if (is_red (w)) { set_black (w); set_red (parent); - gtk_css_rb_node_rotate_right (tree, parent); + gtk_rb_node_rotate_right (tree, parent); w = parent->left; } if (is_black (w->right) && is_black (w->left)) @@ -408,13 +408,13 @@ gtk_css_rb_tree_remove_node_fixup (GtkCssRbTree *tree, { set_black (w->right); set_red (w); - gtk_css_rb_node_rotate_left (tree, w); + gtk_rb_node_rotate_left (tree, w); w = parent->left; } w->red = parent->red; set_black (parent); set_black (w->left); - gtk_css_rb_node_rotate_right (tree, parent); + gtk_rb_node_rotate_right (tree, parent); node = tree->root; } } @@ -425,16 +425,16 @@ gtk_css_rb_tree_remove_node_fixup (GtkCssRbTree *tree, set_black (node); } -GtkCssRbTree * -gtk_css_rb_tree_new_for_size (gsize element_size, - gsize augment_size, - GtkCssRbTreeAugmentFunc augment_func, - GDestroyNotify clear_func, - GDestroyNotify clear_augment_func) +GtkRbTree * +gtk_rb_tree_new_for_size (gsize element_size, + gsize augment_size, + GtkRbTreeAugmentFunc augment_func, + GDestroyNotify clear_func, + GDestroyNotify clear_augment_func) { - GtkCssRbTree *tree; + GtkRbTree *tree; - tree = g_slice_new0 (GtkCssRbTree); + tree = g_slice_new0 (GtkRbTree); tree->ref_count = 1; tree->element_size = element_size; @@ -446,8 +446,8 @@ gtk_css_rb_tree_new_for_size (gsize element_size, return tree; } -GtkCssRbTree * -gtk_css_rb_tree_ref (GtkCssRbTree *tree) +GtkRbTree * +gtk_rb_tree_ref (GtkRbTree *tree) { tree->ref_count++; @@ -455,103 +455,103 @@ gtk_css_rb_tree_ref (GtkCssRbTree *tree) } void -gtk_css_rb_tree_unref (GtkCssRbTree *tree) +gtk_rb_tree_unref (GtkRbTree *tree) { tree->ref_count--; if (tree->ref_count > 0) return; if (tree->root) - gtk_css_rb_node_free_deep (tree, tree->root); + gtk_rb_node_free_deep (tree, tree->root); - g_slice_free (GtkCssRbTree, tree); + g_slice_free (GtkRbTree, tree); } gpointer -gtk_css_rb_tree_get_first (GtkCssRbTree *tree) +gtk_rb_tree_get_first (GtkRbTree *tree) { if (tree->root == NULL) return NULL; - return NODE_TO_POINTER (gtk_css_rb_node_get_first (tree->root)); + return NODE_TO_POINTER (gtk_rb_node_get_first (tree->root)); } gpointer -gtk_css_rb_tree_get_last (GtkCssRbTree *tree) +gtk_rb_tree_get_last (GtkRbTree *tree) { if (tree->root == NULL) return NULL; - return NODE_TO_POINTER (gtk_css_rb_node_get_last (tree->root)); + return NODE_TO_POINTER (gtk_rb_node_get_last (tree->root)); } gpointer -gtk_css_rb_tree_get_previous (GtkCssRbTree *tree, - gpointer node) +gtk_rb_tree_get_previous (GtkRbTree *tree, + gpointer node) { - return NODE_TO_POINTER (gtk_css_rb_node_get_previous (NODE_FROM_POINTER (node))); + return NODE_TO_POINTER (gtk_rb_node_get_previous (NODE_FROM_POINTER (node))); } gpointer -gtk_css_rb_tree_get_next (GtkCssRbTree *tree, - gpointer node) +gtk_rb_tree_get_next (GtkRbTree *tree, + gpointer node) { - return NODE_TO_POINTER (gtk_css_rb_node_get_next (NODE_FROM_POINTER (node))); + return NODE_TO_POINTER (gtk_rb_node_get_next (NODE_FROM_POINTER (node))); } gpointer -gtk_css_rb_tree_get_root (GtkCssRbTree *tree) +gtk_rb_tree_get_root (GtkRbTree *tree) { return NODE_TO_POINTER (tree->root); } gpointer -gtk_css_rb_tree_get_parent (GtkCssRbTree *tree, - gpointer node) +gtk_rb_tree_get_parent (GtkRbTree *tree, + gpointer node) { return NODE_TO_POINTER (NODE_FROM_POINTER (node)->parent); } gpointer -gtk_css_rb_tree_get_left (GtkCssRbTree *tree, - gpointer node) +gtk_rb_tree_get_left (GtkRbTree *tree, + gpointer node) { return NODE_TO_POINTER (NODE_FROM_POINTER (node)->left); } gpointer -gtk_css_rb_tree_get_right (GtkCssRbTree *tree, - gpointer node) +gtk_rb_tree_get_right (GtkRbTree *tree, + gpointer node) { return NODE_TO_POINTER (NODE_FROM_POINTER (node)->right); } gpointer -gtk_css_rb_tree_get_augment (GtkCssRbTree *tree, - gpointer node) +gtk_rb_tree_get_augment (GtkRbTree *tree, + gpointer node) { - GtkCssRbNode *rbnode = NODE_FROM_POINTER (node); + GtkRbNode *rbnode = NODE_FROM_POINTER (node); - gtk_css_rb_node_clean (tree, rbnode); + gtk_rb_node_clean (tree, rbnode); return NODE_TO_AUG_POINTER (tree, rbnode); } void -gtk_css_rb_tree_mark_dirty (GtkCssRbTree *tree, - gpointer node) +gtk_rb_tree_mark_dirty (GtkRbTree *tree, + gpointer node) { - gtk_css_rb_node_mark_dirty (NODE_FROM_POINTER (node), TRUE); + gtk_rb_node_mark_dirty (NODE_FROM_POINTER (node), TRUE); } gpointer -gtk_css_rb_tree_insert_before (GtkCssRbTree *tree, - gpointer node) +gtk_rb_tree_insert_before (GtkRbTree *tree, + gpointer node) { - GtkCssRbNode *result; + GtkRbNode *result; /* setup new node */ - result = gtk_css_rb_node_new (tree); + result = gtk_rb_node_new (tree); if (tree->root == NULL) { @@ -560,15 +560,15 @@ gtk_css_rb_tree_insert_before (GtkCssRbTree *tree, } else if (node == NULL) { - return gtk_css_rb_tree_insert_after (tree, gtk_css_rb_tree_get_last (tree)); + return gtk_rb_tree_insert_after (tree, gtk_rb_tree_get_last (tree)); } else { - GtkCssRbNode *current = NODE_FROM_POINTER (node); + GtkRbNode *current = NODE_FROM_POINTER (node); if (current->left) { - current = gtk_css_rb_node_get_last (current->left); + current = gtk_rb_node_get_last (current->left); current->right = result; } else @@ -576,22 +576,22 @@ gtk_css_rb_tree_insert_before (GtkCssRbTree *tree, current->left = result; } result->parent = current; - gtk_css_rb_node_mark_dirty (current, TRUE); + gtk_rb_node_mark_dirty (current, TRUE); } - gtk_css_rb_tree_insert_fixup (tree, result); + gtk_rb_tree_insert_fixup (tree, result); return NODE_TO_POINTER (result); } gpointer -gtk_css_rb_tree_insert_after (GtkCssRbTree *tree, - gpointer node) +gtk_rb_tree_insert_after (GtkRbTree *tree, + gpointer node) { - GtkCssRbNode *result; + GtkRbNode *result; /* setup new node */ - result = gtk_css_rb_node_new (tree); + result = gtk_rb_node_new (tree); if (tree->root == NULL) { @@ -600,15 +600,15 @@ gtk_css_rb_tree_insert_after (GtkCssRbTree *tree, } else if (node == NULL) { - return gtk_css_rb_tree_insert_before (tree, gtk_css_rb_tree_get_first (tree)); + return gtk_rb_tree_insert_before (tree, gtk_rb_tree_get_first (tree)); } else { - GtkCssRbNode *current = NODE_FROM_POINTER (node); + GtkRbNode *current = NODE_FROM_POINTER (node); if (current->right) { - current = gtk_css_rb_node_get_first (current->right); + current = gtk_rb_node_get_first (current->right); current->left = result; } else @@ -616,19 +616,19 @@ gtk_css_rb_tree_insert_after (GtkCssRbTree *tree, current->right = result; } result->parent = current; - gtk_css_rb_node_mark_dirty (current, TRUE); + gtk_rb_node_mark_dirty (current, TRUE); } - gtk_css_rb_tree_insert_fixup (tree, result); + gtk_rb_tree_insert_fixup (tree, result); return NODE_TO_POINTER (result); } void -gtk_css_rb_tree_remove (GtkCssRbTree *tree, - gpointer node) +gtk_rb_tree_remove (GtkRbTree *tree, + gpointer node) { - GtkCssRbNode *x, *y, *real_node; + GtkRbNode *x, *y, *real_node; real_node = NODE_FROM_POINTER (node); y = real_node; @@ -655,7 +655,7 @@ gtk_css_rb_tree_remove (GtkCssRbTree *tree, y->parent->left = x; else y->parent->right = x; - gtk_css_rb_node_mark_dirty (y->parent, TRUE); + gtk_rb_node_mark_dirty (y->parent, TRUE); } else { @@ -665,7 +665,7 @@ gtk_css_rb_tree_remove (GtkCssRbTree *tree, /* We need to clean up the validity of the tree. */ if (is_black (y)) - gtk_css_rb_tree_remove_node_fixup (tree, x, y->parent); + gtk_rb_tree_remove_node_fixup (tree, x, y->parent); if (y != real_node) { @@ -686,35 +686,35 @@ gtk_css_rb_tree_remove (GtkCssRbTree *tree, y->parent->left = y; else y->parent->right = y; - gtk_css_rb_node_mark_dirty (y->parent, TRUE); + gtk_rb_node_mark_dirty (y->parent, TRUE); } else { tree->root = y; } - gtk_css_rb_node_mark_dirty (y, TRUE); + gtk_rb_node_mark_dirty (y, TRUE); } - gtk_css_rb_node_free (tree, real_node); + gtk_rb_node_free (tree, real_node); } void -gtk_css_rb_tree_remove_all (GtkCssRbTree *tree) +gtk_rb_tree_remove_all (GtkRbTree *tree) { if (tree->root) - gtk_css_rb_node_free_deep (tree, tree->root); + gtk_rb_node_free_deep (tree, tree->root); tree->root = NULL; } gpointer -gtk_css_rb_tree_find (GtkCssRbTree *tree, - gpointer *out_before, - gpointer *out_after, - GtkCssRbTreeFindFunc find_func, - gpointer user_data) +gtk_rb_tree_find (GtkRbTree *tree, + gpointer *out_before, + gpointer *out_after, + GtkRbTreeFindFunc find_func, + gpointer user_data) { - GtkCssRbNode *node, *before = NULL, *after = NULL; + GtkRbNode *node, *before = NULL, *after = NULL; int cmp; if (tree->root == NULL) @@ -753,9 +753,9 @@ gtk_css_rb_tree_find (GtkCssRbTree *tree, } if (out_before) - *out_before = NODE_TO_POINTER (gtk_css_rb_node_get_previous (node)); + *out_before = NODE_TO_POINTER (gtk_rb_node_get_previous (node)); if (out_after) - *out_after = NODE_TO_POINTER (gtk_css_rb_node_get_next (node)); + *out_after = NODE_TO_POINTER (gtk_rb_node_get_next (node)); return NODE_TO_POINTER (node); } diff --git a/gtk/gtkrbtreeprivate.h b/gtk/gtkrbtreeprivate.h new file mode 100644 index 0000000000..b73c80708d --- /dev/null +++ b/gtk/gtkrbtreeprivate.h @@ -0,0 +1,89 @@ +/* gtkrbtree.h + * Copyright (C) 2000 Red Hat, Inc., Jonathan Blandford <jrb@redhat.com> + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Library General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with this library. If not, see <http://www.gnu.org/licenses/>. + */ + +/* A Red-Black Tree implementation used specifically by GtkTreeView. + */ +#ifndef __GTK_RB_TREE_H__ +#define __GTK_RB_TREE_H__ + +#include <glib.h> + + +G_BEGIN_DECLS + + +typedef struct _GtkRbTree GtkRbTree; + +typedef void (* GtkRbTreeAugmentFunc) (GtkRbTree *tree, + gpointer node_augment, + gpointer node, + gpointer left, + gpointer right); +typedef int (* GtkRbTreeFindFunc) (GtkRbTree *tree, + gpointer node, + gpointer user_data); + +GtkRbTree * gtk_rb_tree_new_for_size (gsize element_size, + gsize augment_size, + GtkRbTreeAugmentFunc augment_func, + GDestroyNotify clear_func, + GDestroyNotify clear_augment_func); +#define gtk_rb_tree_new(type, augment_type, augment_func, clear_func, clear_augment_func) \ + gtk_rb_tree_new_for_size (sizeof (type), sizeof (augment_type), (augment_func), (clear_func), (clear_augment_func)) + +GtkRbTree * gtk_rb_tree_ref (GtkRbTree *tree); +void gtk_rb_tree_unref (GtkRbTree *tree); + +gpointer gtk_rb_tree_get_first (GtkRbTree *tree); +gpointer gtk_rb_tree_get_last (GtkRbTree *tree); +gpointer gtk_rb_tree_get_previous (GtkRbTree *tree, + gpointer node); +gpointer gtk_rb_tree_get_next (GtkRbTree *tree, + gpointer node); + +gpointer gtk_rb_tree_get_root (GtkRbTree *tree); +gpointer gtk_rb_tree_get_parent (GtkRbTree *tree, + gpointer node); +gpointer gtk_rb_tree_get_left (GtkRbTree *tree, + gpointer node); +gpointer gtk_rb_tree_get_right (GtkRbTree *tree, + gpointer node); +gpointer gtk_rb_tree_get_augment (GtkRbTree *tree, + gpointer node); + +void gtk_rb_tree_mark_dirty (GtkRbTree *tree, + gpointer node); + +gpointer gtk_rb_tree_insert_before (GtkRbTree *tree, + gpointer node); +gpointer gtk_rb_tree_insert_after (GtkRbTree *tree, + gpointer node); +void gtk_rb_tree_remove (GtkRbTree *tree, + gpointer node); +void gtk_rb_tree_remove_all (GtkRbTree *tree); + +gpointer gtk_rb_tree_find (GtkRbTree *tree, + gpointer *out_before, + gpointer *out_after, + GtkRbTreeFindFunc find_func, + gpointer user_data); + + +G_END_DECLS + + +#endif /* __GTK_RB_TREE_H__ */ diff --git a/gtk/gtkslicelistmodel.c b/gtk/gtkslicelistmodel.c index 5144462e5c..712e46ca68 100644 --- a/gtk/gtkslicelistmodel.c +++ b/gtk/gtkslicelistmodel.c @@ -21,7 +21,6 @@ #include "gtkslicelistmodel.h" -#include "gtkcssrbtreeprivate.h" #include "gtkintl.h" #include "gtkprivate.h" diff --git a/gtk/gtktreelistmodel.c b/gtk/gtktreelistmodel.c index 186a25b967..af609e61ce 100644 --- a/gtk/gtktreelistmodel.c +++ b/gtk/gtktreelistmodel.c @@ -21,7 +21,7 @@ #include "gtktreelistmodel.h" -#include "gtkcssrbtreeprivate.h" +#include "gtkrbtreeprivate.h" #include "gtkintl.h" #include "gtkprivate.h" @@ -50,7 +50,7 @@ struct _TreeNode { GListModel *model; GtkTreeListRow *row; - GtkCssRbTree *children; + GtkRbTree *children; union { TreeNode *parent; GtkTreeListModel *list; @@ -112,19 +112,19 @@ static TreeNode * tree_node_get_nth_child (TreeNode *node, guint position) { - GtkCssRbTree *tree; + GtkRbTree *tree; TreeNode *child, *tmp; TreeAugment *aug; tree = node->children; - child = gtk_css_rb_tree_get_root (tree); + child = gtk_rb_tree_get_root (tree); while (child) { - tmp = gtk_css_rb_tree_get_left (tree, child); + tmp = gtk_rb_tree_get_left (tree, child); if (tmp) { - aug = gtk_css_rb_tree_get_augment (tree, tmp); + aug = gtk_rb_tree_get_augment (tree, tmp); if (position < aug->n_local) { child = tmp; @@ -138,7 +138,7 @@ tree_node_get_nth_child (TreeNode *node, position--; - child = gtk_css_rb_tree_get_right (tree, child); + child = gtk_rb_tree_get_right (tree, child); } return NULL; @@ -153,27 +153,27 @@ tree_node_get_n_children (TreeNode *node) if (node->children == NULL) return 0; - child_node = gtk_css_rb_tree_get_root (node->children); + child_node = gtk_rb_tree_get_root (node->children); if (child_node == NULL) return 0; - child_aug = gtk_css_rb_tree_get_augment (node->children, child_node); + child_aug = gtk_rb_tree_get_augment (node->children, child_node); return child_aug->n_items; } static guint -tree_node_get_local_position (GtkCssRbTree *tree, - TreeNode *node) +tree_node_get_local_position (GtkRbTree *tree, + TreeNode *node) { TreeNode *left, *parent; TreeAugment *left_aug; guint n; - left = gtk_css_rb_tree_get_left (tree, node); + left = gtk_rb_tree_get_left (tree, node); if (left) { - left_aug = gtk_css_rb_tree_get_augment (tree, left); + left_aug = gtk_rb_tree_get_augment (tree, left); n = left_aug->n_local; } else @@ -181,11 +181,11 @@ tree_node_get_local_position (GtkCssRbTree *tree, n = 0; } - for (parent = gtk_css_rb_tree_get_parent (tree, node); + for (parent = gtk_rb_tree_get_parent (tree, node); parent; - parent = gtk_css_rb_tree_get_parent (tree, node)) + parent = gtk_rb_tree_get_parent (tree, node)) { - left = gtk_css_rb_tree_get_left (tree, parent); + left = gtk_rb_tree_get_left (tree, parent); if (left == node) { /* we are the left node, nothing changes */ @@ -196,7 +196,7 @@ tree_node_get_local_position (GtkCssRbTree *tree, n++; if (left) { - left_aug = gtk_css_rb_tree_get_augment (tree, left); + left_aug = gtk_rb_tree_get_augment (tree, left); n += left_aug->n_local; } } @@ -209,7 +209,7 @@ tree_node_get_local_position (GtkCssRbTree *tree, static guint tree_node_get_position (TreeNode *node) { - GtkCssRbTree *tree; + GtkRbTree *tree; TreeNode *left, *parent; TreeAugment *left_aug; guint n; @@ -220,18 +220,18 @@ tree_node_get_position (TreeNode *node) { tree = node->parent->children; - left = gtk_css_rb_tree_get_left (tree, node); + left = gtk_rb_tree_get_left (tree, node); if (left) { - left_aug = gtk_css_rb_tree_get_augment (tree, left); + left_aug = gtk_rb_tree_get_augment (tree, left); n += left_aug->n_items; } - for (parent = gtk_css_rb_tree_get_parent (tree, node); + for (parent = gtk_rb_tree_get_parent (tree, node); parent; - parent = gtk_css_rb_tree_get_parent (tree, node)) + parent = gtk_rb_tree_get_parent (tree, node)) { - left = gtk_css_rb_tree_get_left (tree, parent); + left = gtk_rb_tree_get_left (tree, parent); if (left == node) { /* we are the left node, nothing changes */ @@ -242,7 +242,7 @@ tree_node_get_position (TreeNode *node) n += 1 + tree_node_get_n_children (parent); if (left) { - left_aug = gtk_css_rb_tree_get_augment (tree, left); + left_aug = gtk_rb_tree_get_augment (tree, left); n += left_aug->n_items; } } @@ -262,7 +262,7 @@ tree_node_mark_dirty (TreeNode *node) !node->is_root; node = node->parent) { - gtk_css_rb_tree_mark_dirty (node->parent->children, node); + gtk_rb_tree_mark_dirty (node->parent->children, node); } } @@ -270,7 +270,7 @@ static TreeNode * gtk_tree_list_model_get_nth (GtkTreeListModel *self, guint position) { - GtkCssRbTree *tree; + GtkRbTree *tree; TreeNode *node, *tmp; guint n_children; @@ -279,14 +279,14 @@ gtk_tree_list_model_get_nth (GtkTreeListModel *self, return NULL; tree = self->root_node.children; - node = gtk_css_rb_tree_get_root (tree); + node = gtk_rb_tree_get_root (tree); while (TRUE) { - tmp = gtk_css_rb_tree_get_left (tree, node); + tmp = gtk_rb_tree_get_left (tree, node); if (tmp) { - TreeAugment *aug = gtk_css_rb_tree_get_augment (tree, tmp); + TreeAugment *aug = gtk_rb_tree_get_augment (tree, tmp); if (position < aug->n_items) { node = tmp; @@ -304,12 +304,12 @@ gtk_tree_list_model_get_nth (GtkTreeListModel *self, if (position < n_children) { tree = node->children; - node = gtk_css_rb_tree_get_root (tree); + node = gtk_rb_tree_get_root (tree); continue; } position -= n_children; - node = gtk_css_rb_tree_get_right (tree, node); + node = gtk_rb_tree_get_right (tree, node); } g_return_val_if_reached (NULL); @@ -406,8 +406,8 @@ gtk_tree_list_model_items_changed_cb (GListModel *model, for (i = 0; i < removed; i++) { tmp = child; - child = gtk_css_rb_tree_get_next (node->children, child); - gtk_css_rb_tree_remove (node->children, tmp); + child = gtk_rb_tree_get_next (node->children, child); + gtk_rb_tree_remove (node->children, tmp); } } else @@ -418,7 +418,7 @@ gtk_tree_list_model_items_changed_cb (GListModel *model, tree_added = added; for (i = 0; i < added; i++) { - child = gtk_css_rb_tree_insert_before (node->children, child); + child = gtk_rb_tree_insert_before (node->children, child); child->parent = node; } if (self->autoexpand) @@ -426,7 +426,7 @@ gtk_tree_list_model_items_changed_cb (GListModel *model, for (i = 0; i < added; i++) { tree_added += gtk_tree_list_model_expand_node (self, child); - child = gtk_css_rb_tree_get_next (node->children, child); + child = gtk_rb_tree_get_next (node->children, child); } } @@ -456,15 +456,15 @@ gtk_tree_list_model_clear_node (gpointer data) g_object_unref (node->model); } if (node->children) - gtk_css_rb_tree_unref (node->children); + gtk_rb_tree_unref (node->children); } static void -gtk_tree_list_model_augment (GtkCssRbTree *tree, - gpointer _aug, - gpointer _node, - gpointer left, - gpointer right) +gtk_tree_list_model_augment (GtkRbTree *tree, + gpointer _aug, + gpointer _node, + gpointer left, + gpointer right) { TreeAugment *aug = _aug; @@ -474,13 +474,13 @@ gtk_tree_list_model_augment (GtkCssRbTree *tree, if (left) { - TreeAugment *left_aug = gtk_css_rb_tree_get_augment (tree, left); + TreeAugment *left_aug = gtk_rb_tree_get_augment (tree, left); aug->n_items += left_aug->n_items; aug->n_local += left_aug->n_local; } if (right) { - TreeAugment *right_aug = gtk_css_rb_tree_get_augment (tree, right); + TreeAugment *right_aug = gtk_rb_tree_get_augment (tree, right); aug->n_items += right_aug->n_items; aug->n_local += right_aug->n_local; } @@ -499,17 +499,17 @@ gtk_tree_list_model_init_node (GtkTreeListModel *list, "items-changed", G_CALLBACK (gtk_tree_list_model_items_changed_cb), self); - self->children = gtk_css_rb_tree_new (TreeNode, - TreeAugment, - gtk_tree_list_model_augment, - gtk_tree_list_model_clear_node, - NULL); + self->children = gtk_rb_tree_new (TreeNode, + TreeAugment, + gtk_tree_list_model_augment, + gtk_tree_list_model_clear_node, + NULL); n = g_list_model_get_n_items (model); node = NULL; for (i = 0; i < n; i++) { - node = gtk_css_rb_tree_insert_after (self->children, node); + node = gtk_rb_tree_insert_after (self->children, node); node->parent = self; if (list->autoexpand) gtk_tree_list_model_expand_node (list, node); @@ -561,7 +561,7 @@ gtk_tree_list_model_collapse_node (GtkTreeListModel *self, n_items = tree_node_get_n_children (node); - g_clear_pointer (&node->children, gtk_css_rb_tree_unref); + g_clear_pointer (&node->children, gtk_rb_tree_unref); g_clear_object (&node->model); tree_node_mark_dirty (node); @@ -683,7 +683,7 @@ gtk_tree_list_model_finalize (GObject *object) self->user_destroy (self->user_data); G_OBJECT_CLASS (gtk_tree_list_model_parent_class)->finalize (object); -}; +} static void gtk_tree_list_model_class_init (GtkTreeListModelClass *class) @@ -1026,7 +1026,7 @@ gtk_tree_list_row_dispose (GObject *object) self->node->row = NULL; G_OBJECT_CLASS (gtk_tree_list_row_parent_class)->dispose (object); -}; +} static void gtk_tree_list_row_class_init (GtkTreeListRowClass *class) diff --git a/gtk/meson.build b/gtk/meson.build index e2eb7af3a5..e45b18bf8e 100644 --- a/gtk/meson.build +++ b/gtk/meson.build @@ -79,7 +79,6 @@ gtk_private_sources = files([ 'gtkcssparser.c', 'gtkcsspathnode.c', 'gtkcsspositionvalue.c', - 'gtkcssrbtree.c', 'gtkcssrepeatvalue.c', 'gtkcssrgbavalue.c', 'gtkcssselector.c', @@ -132,6 +131,7 @@ gtk_private_sources = files([ 'gtkprintutils.c', 'gtkprivate.c', 'gtkprogresstracker.c', + 'gtkrbtree.c', 'gtkquery.c', 'gtkscaler.c', 'gtksearchengine.c', diff --git a/testsuite/gtk/meson.build b/testsuite/gtk/meson.build index 69dd63df7d..912dbb409a 100644 --- a/testsuite/gtk/meson.build +++ b/testsuite/gtk/meson.build @@ -17,7 +17,7 @@ tests = [ ['cellarea'], ['check-icon-names'], ['cssprovider'], - ['cssrbtree-crash', ['../../gtk/gtkcssrbtree.c'], ['-DGTK_COMPILATION', '-UG_ENABLE_DEBUG']], + ['rbtree-crash', ['../../gtk/gtkrbtree.c'], ['-DGTK_COMPILATION', '-UG_ENABLE_DEBUG']], ['defaultvalue'], ['entry'], ['filterlistmodel'], diff --git a/testsuite/gtk/cssrbtree-crash.c b/testsuite/gtk/rbtree-crash.c index 3d1036148f..ec46c45445 100644 --- a/testsuite/gtk/cssrbtree-crash.c +++ b/testsuite/gtk/rbtree-crash.c @@ -21,7 +21,7 @@ #include <gtk/gtk.h> -#include "gtk/gtkcssrbtreeprivate.h" +#include "gtk/gtkrbtreeprivate.h" typedef struct _Node Node; typedef struct _Aug Aug; @@ -35,11 +35,11 @@ struct _Aug { }; static void -augment (GtkCssRbTree *tree, - gpointer _aug, - gpointer _node, - gpointer left, - gpointer right) +augment (GtkRbTree *tree, + gpointer _aug, + gpointer _node, + gpointer left, + gpointer right) { Aug *aug = _aug; @@ -47,33 +47,33 @@ augment (GtkCssRbTree *tree, if (left) { - Aug *left_aug = gtk_css_rb_tree_get_augment (tree, left); + Aug *left_aug = gtk_rb_tree_get_augment (tree, left); aug->n_items += left_aug->n_items; } if (right) { - Aug *right_aug = gtk_css_rb_tree_get_augment (tree, right); + Aug *right_aug = gtk_rb_tree_get_augment (tree, right); aug->n_items += right_aug->n_items; } } static Node * -get (GtkCssRbTree *tree, - guint pos) +get (GtkRbTree *tree, + guint pos) { Node *node, *tmp; - node = gtk_css_rb_tree_get_root (tree); + node = gtk_rb_tree_get_root (tree); while (node) { - tmp = gtk_css_rb_tree_get_left (tree, node); + tmp = gtk_rb_tree_get_left (tree, node); if (tmp) { - Aug *aug = gtk_css_rb_tree_get_augment (tree, tmp); + Aug *aug = gtk_rb_tree_get_augment (tree, tmp); if (pos < aug->n_items) { node = tmp; @@ -86,45 +86,45 @@ get (GtkCssRbTree *tree, break; pos--; - node = gtk_css_rb_tree_get_right (tree, node); + node = gtk_rb_tree_get_right (tree, node); } return node; } static void -add (GtkCssRbTree *tree, - guint pos) +add (GtkRbTree *tree, + guint pos) { Node *node = get (tree, pos); - gtk_css_rb_tree_insert_before (tree, node); + gtk_rb_tree_insert_before (tree, node); } static void -delete (GtkCssRbTree *tree, - guint pos) +delete (GtkRbTree *tree, + guint pos) { Node *node = get (tree, pos); - gtk_css_rb_tree_remove (tree, node); + gtk_rb_tree_remove (tree, node); } static guint -print_node (GtkCssRbTree *tree, - Node *node, - guint depth, - const char *prefix, - guint n) +print_node (GtkRbTree *tree, + Node *node, + guint depth, + const char *prefix, + guint n) { Node *child; - child = gtk_css_rb_tree_get_left (tree, node); + child = gtk_rb_tree_get_left (tree, node); if (child) n = print_node (tree, child, depth + 1, "/", n); g_print ("%*s %u\n", 2 * depth, prefix, n); n++; - child = gtk_css_rb_tree_get_right (tree, node); + child = gtk_rb_tree_get_right (tree, node); if (child) n = print_node (tree, child, depth + 1, "\\", n); @@ -132,18 +132,18 @@ print_node (GtkCssRbTree *tree, } static void -print (GtkCssRbTree *tree) +print (GtkRbTree *tree) { - print_node (tree, gtk_css_rb_tree_get_root (tree), 0, "", 0); + print_node (tree, gtk_rb_tree_get_root (tree), 0, "", 0); } static void test_crash (void) { - GtkCssRbTree *tree; + GtkRbTree *tree; guint i; - tree = gtk_css_rb_tree_new (Node, Aug, augment, NULL, NULL); + tree = gtk_rb_tree_new (Node, Aug, augment, NULL, NULL); for (i = 0; i < 300; i++) add (tree, i); @@ -270,7 +270,7 @@ test_crash (void) print (tree); delete (tree, 102); - gtk_css_rb_tree_unref (tree); + gtk_rb_tree_unref (tree); } int |