| Message ID | AM5PR0701MB265733F0AB2E8A999896F93BE47B0@AM5PR0701MB2657.eurprd07.prod.outlook.com |
|---|---|
| State | New |
| Headers | show |
| Series | Avoid excessive function type casts with splay-trees part 2 | expand |
On Fri, 2018-06-08 at 14:03 +0000, Bernd Edlinger wrote: > Hi! > > > This patch converts the splay-tree internals into a template, and > makes > the typed_splay_tree template really type-safe. Previously > everything > would break apart if KEY_TYPE or VALUE_TYPE would not be pointer > types. > This limitation is now removed. > > I took the freedom to add a remove function which is only for > completeness and test coverage, but not (yet) used in a productive > way. > > > Bootstrapped and reg-tested on x86_64-linux-gnu. > Is it OK for trunk? Was this testing done with "jit" enabled? (there's some usage of typed_splay_tree there, for jit's equivalent of switch statements) Note that the jit frontend isn't covered by "all" in --enable- languages; it has to be added manually, iirc since it requires -- enable-host-shared. Thanks Dave
On 06/08/18 16:28, David Malcolm wrote: > On Fri, 2018-06-08 at 14:03 +0000, Bernd Edlinger wrote: >> Hi! >> >> >> This patch converts the splay-tree internals into a template, and >> makes >> the typed_splay_tree template really type-safe. Previously >> everything >> would break apart if KEY_TYPE or VALUE_TYPE would not be pointer >> types. >> This limitation is now removed. >> >> I took the freedom to add a remove function which is only for >> completeness and test coverage, but not (yet) used in a productive >> way. >> >> >> Bootstrapped and reg-tested on x86_64-linux-gnu. >> Is it OK for trunk? > > Was this testing done with "jit" enabled? (there's some usage of > typed_splay_tree there, for jit's equivalent of switch statements) > > Note that the jit frontend isn't covered by "all" in --enable- > languages; it has to be added manually, iirc since it requires -- > enable-host-shared. > Yes, good point. I repeated the test with --enable-host-shared and all jit tests did pass. Thanks Bernd. > Thanks > Dave >
On Fri, 2018-06-08 at 20:41 +0000, Bernd Edlinger wrote: > On 06/08/18 16:28, David Malcolm wrote: > > On Fri, 2018-06-08 at 14:03 +0000, Bernd Edlinger wrote: > > > Hi! > > > > > > > > > This patch converts the splay-tree internals into a template, and > > > makes > > > the typed_splay_tree template really type-safe. Previously > > > everything > > > would break apart if KEY_TYPE or VALUE_TYPE would not be pointer > > > types. > > > This limitation is now removed. > > > > > > I took the freedom to add a remove function which is only for > > > completeness and test coverage, but not (yet) used in a > > > productive > > > way. > > > > > > > > > Bootstrapped and reg-tested on x86_64-linux-gnu. > > > Is it OK for trunk? > > > > Was this testing done with "jit" enabled? (there's some usage of > > typed_splay_tree there, for jit's equivalent of switch statements) > > > > Note that the jit frontend isn't covered by "all" in --enable- > > languages; it has to be added manually, iirc since it requires -- > > enable-host-shared. > > > > Yes, good point. I repeated the test with --enable-host-shared > and all jit tests did pass. Thanks! Dave
On Fri, 8 Jun 2018, Bernd Edlinger wrote: > Hi! > > > This patch converts the splay-tree internals into a template, and makes > the typed_splay_tree template really type-safe. Previously everything > would break apart if KEY_TYPE or VALUE_TYPE would not be pointer types. > This limitation is now removed. > > I took the freedom to add a remove function which is only for > completeness and test coverage, but not (yet) used in a productive way. > > > Bootstrapped and reg-tested on x86_64-linux-gnu. > Is it OK for trunk? It looks OK to me but I wonder if we can avoid some of the code duplication due to template instantiation by deriving from a non-templated base class somehow? The cc1* binaries keep growing with more and more template use :/ Thanks, Richard.
On 06/14/18 15:43, Richard Biener wrote: > On Fri, 8 Jun 2018, Bernd Edlinger wrote: > >> Hi! >> >> >> This patch converts the splay-tree internals into a template, and makes >> the typed_splay_tree template really type-safe. Previously everything >> would break apart if KEY_TYPE or VALUE_TYPE would not be pointer types. >> This limitation is now removed. >> >> I took the freedom to add a remove function which is only for >> completeness and test coverage, but not (yet) used in a productive way. >> >> >> Bootstrapped and reg-tested on x86_64-linux-gnu. >> Is it OK for trunk? > > It looks OK to me but I wonder if we can avoid some of the code > duplication due to template instantiation by deriving from a non-templated > base class somehow? The cc1* binaries keep growing with more and > more template use :/ > No problem. The first version used an approach where splay-tree exposes an extended interface with a context pointer. See: https://gcc.gnu.org/ml/gcc-patches/2018-05/msg00178.html But it has also a limitation when the value or type is a class, it will not be possible to cast to uintptr_t, it will fail to compile, which is still an improvement since the current version just casts incompatible function pointers, and since I had to silence the -Wcast-function-type the warning would not help either. If you like the original patch better than the template, I can cleanup the original patch as an alternative? Thanks Bernd.
On Thu, 14 Jun 2018, Bernd Edlinger wrote: > On 06/14/18 15:43, Richard Biener wrote: > > On Fri, 8 Jun 2018, Bernd Edlinger wrote: > > > >> Hi! > >> > >> > >> This patch converts the splay-tree internals into a template, and makes > >> the typed_splay_tree template really type-safe. Previously everything > >> would break apart if KEY_TYPE or VALUE_TYPE would not be pointer types. > >> This limitation is now removed. > >> > >> I took the freedom to add a remove function which is only for > >> completeness and test coverage, but not (yet) used in a productive way. > >> > >> > >> Bootstrapped and reg-tested on x86_64-linux-gnu. > >> Is it OK for trunk? > > > > It looks OK to me but I wonder if we can avoid some of the code > > duplication due to template instantiation by deriving from a non-templated > > base class somehow? The cc1* binaries keep growing with more and > > more template use :/ > > > > > No problem. The first version used an approach where splay-tree > exposes an extended interface with a context pointer. > > See: https://gcc.gnu.org/ml/gcc-patches/2018-05/msg00178.html > > But it has also a limitation when the value or type is a class, it will > not be possible to cast to uintptr_t, it will fail to compile, which is > still an improvement since the current version just casts incompatible > function pointers, and since I had to silence the -Wcast-function-type > the warning would not help either. > > > If you like the original patch better than the template, I can cleanup > the original patch as an alternative? No, I like the template more but wondered if we can somehow outline some of the main worker code? Thanks, Richard.
On 06/15/18 09:07, Richard Biener wrote: > On Thu, 14 Jun 2018, Bernd Edlinger wrote: > >> On 06/14/18 15:43, Richard Biener wrote: >>> On Fri, 8 Jun 2018, Bernd Edlinger wrote: >>> >>>> Hi! >>>> >>>> >>>> This patch converts the splay-tree internals into a template, and makes >>>> the typed_splay_tree template really type-safe. Previously everything >>>> would break apart if KEY_TYPE or VALUE_TYPE would not be pointer types. >>>> This limitation is now removed. >>>> >>>> I took the freedom to add a remove function which is only for >>>> completeness and test coverage, but not (yet) used in a productive way. >>>> >>>> >>>> Bootstrapped and reg-tested on x86_64-linux-gnu. >>>> Is it OK for trunk? >>> >>> It looks OK to me but I wonder if we can avoid some of the code >>> duplication due to template instantiation by deriving from a non-templated >>> base class somehow? The cc1* binaries keep growing with more and >>> more template use :/ >>> >> >> >> No problem. The first version used an approach where splay-tree >> exposes an extended interface with a context pointer. >> >> See: https://gcc.gnu.org/ml/gcc-patches/2018-05/msg00178.html >> >> But it has also a limitation when the value or type is a class, it will >> not be possible to cast to uintptr_t, it will fail to compile, which is >> still an improvement since the current version just casts incompatible >> function pointers, and since I had to silence the -Wcast-function-type >> the warning would not help either. >> >> >> If you like the original patch better than the template, I can cleanup >> the original patch as an alternative? > > No, I like the template more but wondered if we can somehow outline > some of the main worker code? > The major difficulty with that are the splay_tree_compare_fn and splay_tree_delete_key/value_fn callbacks which don't pass a context value in addition to the splay_tree_key and splay_tree_value. I thought about passing a "glue" object which contains a context pointer together with the true key and/or value object, but I gave up when I saw this in splay_tree_insert: if (sp->root) comparison = (*sp->comp)(sp->root->key, key); if (sp->root && comparison == 0) { /* If the root of the tree already has the indicated KEY, just replace the value with VALUE. */ if (sp->delete_value) (*sp->delete_value)(sp->root->value); sp->root->value = value; } There is a delete_key callback missing, and sp->root->key will not be updated. So the resource flow of the glue objects will not work. This code simply assumes that key equality implies pointer equality, or the key does not need to be freed after use, but this is not the case with glue objects. So, I don't see how to use the old code in a type-safe template without changing the C interface. Or maybe duplicating the C implementation... Currently there are not more than two or three uses of this template, so it will not be a big difference anyways. But shouldn't different template functions be folded together when the resulting code is identical? Or is there maybe another template where optimizing the code size would be more profitable? So, I would still prefer the splay tree template unless there is a better idea, how to proceed. Thanks Bernd.
On 6/15/18, Bernd Edlinger <bernd.edlinger@hotmail.de> wrote: > On 06/15/18 09:07, Richard Biener wrote: >> On Thu, 14 Jun 2018, Bernd Edlinger wrote: >> >>> On 06/14/18 15:43, Richard Biener wrote: >>>> On Fri, 8 Jun 2018, Bernd Edlinger wrote: >>>> >>>>> Hi! >>>>> >>>>> >>>>> This patch converts the splay-tree internals into a template, and >>>>> makes >>>>> the typed_splay_tree template really type-safe. Previously everything >>>>> would break apart if KEY_TYPE or VALUE_TYPE would not be pointer >>>>> types. >>>>> This limitation is now removed. >>>>> >>>>> I took the freedom to add a remove function which is only for >>>>> completeness and test coverage, but not (yet) used in a productive >>>>> way. >>>>> >>>>> >>>>> Bootstrapped and reg-tested on x86_64-linux-gnu. >>>>> Is it OK for trunk? >>>> >>>> It looks OK to me but I wonder if we can avoid some of the code >>>> duplication due to template instantiation by deriving from a >>>> non-templated >>>> base class somehow? The cc1* binaries keep growing with more and >>>> more template use :/ >>>> >>> >>> >>> No problem. The first version used an approach where splay-tree >>> exposes an extended interface with a context pointer. >>> >>> See: https://gcc.gnu.org/ml/gcc-patches/2018-05/msg00178.html >>> >>> But it has also a limitation when the value or type is a class, it will >>> not be possible to cast to uintptr_t, it will fail to compile, which is >>> still an improvement since the current version just casts incompatible >>> function pointers, and since I had to silence the -Wcast-function-type >>> the warning would not help either. >>> >>> >>> If you like the original patch better than the template, I can cleanup >>> the original patch as an alternative? >> >> No, I like the template more but wondered if we can somehow outline >> some of the main worker code? >> > > The major difficulty with that are the splay_tree_compare_fn and > splay_tree_delete_key/value_fn callbacks which don't pass a context > value in addition to the splay_tree_key and splay_tree_value. > > I thought about passing a "glue" object which contains a context > pointer together with the true key and/or value object, but I gave > up when I saw this in splay_tree_insert: > > if (sp->root) > comparison = (*sp->comp)(sp->root->key, key); > > if (sp->root && comparison == 0) > { > /* If the root of the tree already has the indicated KEY, just > replace the value with VALUE. */ > if (sp->delete_value) > (*sp->delete_value)(sp->root->value); > sp->root->value = value; > } > > There is a delete_key callback missing, and sp->root->key will not > be updated. So the resource flow of the glue objects will not work. > > This code simply assumes that key equality implies pointer equality, > or the key does not need to be freed after use, but this is not the > case with glue objects. > > > So, I don't see how to use the old code in a type-safe template without > changing the C interface. > > Or maybe duplicating the C implementation... > > Currently there are not more than two or three uses of this > template, so it will not be a big difference anyways. > > But shouldn't different template functions be folded together > when the resulting code is identical? > > Or is there maybe another template where optimizing the code size > would be more profitable? > > > So, I would still prefer the splay tree template unless there is a > better idea, how to proceed. > > While you're looking at changing splay trees, could you take a look at bug 30920, too? It's also about splay trees: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30920 Just an idea. Thanks! > Thanks > Bernd. >
On June 15, 2018 8:07:44 PM GMT+02:00, Bernd Edlinger <bernd.edlinger@hotmail.de> wrote: >On 06/15/18 09:07, Richard Biener wrote: >> On Thu, 14 Jun 2018, Bernd Edlinger wrote: >> >>> On 06/14/18 15:43, Richard Biener wrote: >>>> On Fri, 8 Jun 2018, Bernd Edlinger wrote: >>>> >>>>> Hi! >>>>> >>>>> >>>>> This patch converts the splay-tree internals into a template, and >makes >>>>> the typed_splay_tree template really type-safe. Previously >everything >>>>> would break apart if KEY_TYPE or VALUE_TYPE would not be pointer >types. >>>>> This limitation is now removed. >>>>> >>>>> I took the freedom to add a remove function which is only for >>>>> completeness and test coverage, but not (yet) used in a productive >way. >>>>> >>>>> >>>>> Bootstrapped and reg-tested on x86_64-linux-gnu. >>>>> Is it OK for trunk? >>>> >>>> It looks OK to me but I wonder if we can avoid some of the code >>>> duplication due to template instantiation by deriving from a >non-templated >>>> base class somehow? The cc1* binaries keep growing with more and >>>> more template use :/ >>>> >>> >>> >>> No problem. The first version used an approach where splay-tree >>> exposes an extended interface with a context pointer. >>> >>> See: https://gcc.gnu.org/ml/gcc-patches/2018-05/msg00178.html >>> >>> But it has also a limitation when the value or type is a class, it >will >>> not be possible to cast to uintptr_t, it will fail to compile, which >is >>> still an improvement since the current version just casts >incompatible >>> function pointers, and since I had to silence the >-Wcast-function-type >>> the warning would not help either. >>> >>> >>> If you like the original patch better than the template, I can >cleanup >>> the original patch as an alternative? >> >> No, I like the template more but wondered if we can somehow outline >> some of the main worker code? >> > >The major difficulty with that are the splay_tree_compare_fn and >splay_tree_delete_key/value_fn callbacks which don't pass a context >value in addition to the splay_tree_key and splay_tree_value. > >I thought about passing a "glue" object which contains a context >pointer together with the true key and/or value object, but I gave >up when I saw this in splay_tree_insert: > > if (sp->root) > comparison = (*sp->comp)(sp->root->key, key); > > if (sp->root && comparison == 0) > { > /* If the root of the tree already has the indicated KEY, just > replace the value with VALUE. */ > if (sp->delete_value) > (*sp->delete_value)(sp->root->value); > sp->root->value = value; > } > >There is a delete_key callback missing, and sp->root->key will not >be updated. So the resource flow of the glue objects will not work. > >This code simply assumes that key equality implies pointer equality, >or the key does not need to be freed after use, but this is not the >case with glue objects. > > >So, I don't see how to use the old code in a type-safe template without >changing the C interface. > >Or maybe duplicating the C implementation... > >Currently there are not more than two or three uses of this >template, so it will not be a big difference anyways. > >But shouldn't different template functions be folded together >when the resulting code is identical? > >Or is there maybe another template where optimizing the code size >would be more profitable? > > >So, I would still prefer the splay tree template unless there is a >better idea, how to proceed. OK, thanks for having another look. The patch is OK as-is. Richard. > >Thanks >Bernd.
Index: gcc/typed-splay-tree.c =================================================================== --- gcc/typed-splay-tree.c (revision 260952) +++ gcc/typed-splay-tree.c (working copy) @@ -47,7 +47,10 @@ test_str_to_int () t.insert ("a", 1); t.insert ("b", 2); t.insert ("c", 3); + t.insert ("d", 4); + t.remove ("d"); + ASSERT_EQ (1, t.lookup ("a")); ASSERT_EQ (2, t.lookup ("b")); ASSERT_EQ (3, t.lookup ("c")); Index: gcc/typed-splay-tree.h =================================================================== --- gcc/typed-splay-tree.h (revision 260952) +++ gcc/typed-splay-tree.h (working copy) @@ -20,8 +20,6 @@ along with GCC; see the file COPYING3. If not see #ifndef GCC_TYPED_SPLAY_TREE_H #define GCC_TYPED_SPLAY_TREE_H -#include "splay-tree.h" - /* Typesafe wrapper around libiberty's splay-tree.h. */ template <typename KEY_TYPE, typename VALUE_TYPE> class typed_splay_tree @@ -44,27 +42,66 @@ class typed_splay_tree value_type predecessor (key_type k); value_type successor (key_type k); void insert (key_type k, value_type v); + void remove (key_type k); value_type max (); value_type min (); int foreach (foreach_fn, void *); private: - /* Helper type for typed_splay_tree::foreach. */ - struct closure - { - closure (foreach_fn outer_cb, void *outer_user_data) - : m_outer_cb (outer_cb), m_outer_user_data (outer_user_data) {} + /* Copy and assignment ops are not supported. */ + typed_splay_tree (const typed_splay_tree &); + typed_splay_tree & operator = (const typed_splay_tree &); - foreach_fn m_outer_cb; - void *m_outer_user_data; + typedef key_type splay_tree_key; + typedef value_type splay_tree_value; + + /* The nodes in the splay tree. */ + struct splay_tree_node_s { + /* The key. */ + splay_tree_key key; + + /* The value. */ + splay_tree_value value; + + /* The left and right children, respectively. */ + splay_tree_node_s *left, *right; + + /* Used as temporary value for tree traversals. */ + splay_tree_node_s *back; }; + typedef splay_tree_node_s *splay_tree_node; - static int inner_foreach_fn (splay_tree_node node, void *user_data); + inline void KDEL (splay_tree_key); + inline void VDEL (splay_tree_value); + void splay_tree_delete_helper (splay_tree_node); + static inline void rotate_left (splay_tree_node *, + splay_tree_node, splay_tree_node); + static inline void rotate_right (splay_tree_node *, + splay_tree_node, splay_tree_node); + void splay_tree_splay (splay_tree_key); + static int splay_tree_foreach_helper (splay_tree_node, + foreach_fn, void*); + splay_tree_node splay_tree_insert (splay_tree_key, splay_tree_value); + void splay_tree_remove (splay_tree_key key); + splay_tree_node splay_tree_lookup (splay_tree_key key); + splay_tree_node splay_tree_predecessor (splay_tree_key); + splay_tree_node splay_tree_successor (splay_tree_key); + splay_tree_node splay_tree_max (); + splay_tree_node splay_tree_min (); static value_type node_to_value (splay_tree_node node); - private: - ::splay_tree m_inner; + /* The root of the tree. */ + splay_tree_node root; + + /* The comparision function. */ + compare_fn comp; + + /* The deallocate-key function. NULL if no cleanup is necessary. */ + delete_key_fn delete_key; + + /* The deallocate-value function. NULL if no cleanup is necessary. */ + delete_value_fn delete_value; }; /* Constructor for typed_splay_tree <K, V>. */ @@ -75,12 +112,10 @@ inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>:: delete_key_fn delete_key_fn, delete_value_fn delete_value_fn) { - m_inner = splay_tree_new ((splay_tree_compare_fn) - (void (*) (void)) compare_fn, - (splay_tree_delete_key_fn) - (void (*) (void)) delete_key_fn, - (splay_tree_delete_value_fn) - (void (*) (void)) delete_value_fn); + root = NULL; + comp = compare_fn; + delete_key = delete_key_fn; + delete_value = delete_value_fn; } /* Destructor for typed_splay_tree <K, V>. */ @@ -89,7 +124,7 @@ template <typename KEY_TYPE, typename VALUE_TYPE> inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>:: ~typed_splay_tree () { - splay_tree_delete (m_inner); + splay_tree_delete_helper (root); } /* Lookup KEY, returning a value if present, and NULL @@ -99,7 +134,7 @@ template <typename KEY_TYPE, typename VALUE_TYPE> inline VALUE_TYPE typed_splay_tree<KEY_TYPE, VALUE_TYPE>::lookup (key_type key) { - splay_tree_node node = splay_tree_lookup (m_inner, (splay_tree_key)key); + splay_tree_node node = splay_tree_lookup (key); return node_to_value (node); } @@ -110,7 +145,7 @@ template <typename KEY_TYPE, typename VALUE_TYPE> inline VALUE_TYPE typed_splay_tree<KEY_TYPE, VALUE_TYPE>::predecessor (key_type key) { - splay_tree_node node = splay_tree_predecessor (m_inner, (splay_tree_key)key); + splay_tree_node node = splay_tree_predecessor (key); return node_to_value (node); } @@ -119,9 +154,9 @@ typed_splay_tree<KEY_TYPE, VALUE_TYPE>::predecesso template <typename KEY_TYPE, typename VALUE_TYPE> inline VALUE_TYPE -typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type k) +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type key) { - splay_tree_node node = splay_tree_successor (m_inner, (splay_tree_key)k); + splay_tree_node node = splay_tree_successor (key); return node_to_value (node); } @@ -134,11 +169,18 @@ inline void typed_splay_tree<KEY_TYPE, VALUE_TYPE>::insert (key_type key, value_type value) { - splay_tree_insert (m_inner, - (splay_tree_key)key, - (splay_tree_value)value); + splay_tree_insert (key, value); } +/* Remove a node (associating KEY with VALUE). */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +inline void +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::remove (key_type key) +{ + splay_tree_remove (key); +} + /* Get the value with maximal key. */ template <typename KEY_TYPE, typename VALUE_TYPE> @@ -145,7 +187,7 @@ template <typename KEY_TYPE, typename VALUE_TYPE> inline VALUE_TYPE typed_splay_tree<KEY_TYPE, VALUE_TYPE>::max () { - return node_to_value (splay_tree_max (m_inner)); + return node_to_value (splay_tree_max ()); } /* Get the value with minimal key. */ @@ -154,7 +196,7 @@ template <typename KEY_TYPE, typename VALUE_TYPE> inline VALUE_TYPE typed_splay_tree<KEY_TYPE, VALUE_TYPE>::min () { - return node_to_value (splay_tree_min (m_inner)); + return node_to_value (splay_tree_min ()); } /* Call OUTER_CB, passing it the OUTER_USER_DATA, for every node, @@ -164,37 +206,447 @@ typed_splay_tree<KEY_TYPE, VALUE_TYPE>::min () template <typename KEY_TYPE, typename VALUE_TYPE> inline int -typed_splay_tree<KEY_TYPE, VALUE_TYPE>::foreach (foreach_fn outer_cb, - void *outer_user_data) +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::foreach (foreach_fn foreach_fn, + void *user_data) { - closure c (outer_cb, outer_user_data); + return splay_tree_foreach_helper (root, foreach_fn, user_data); +} - return splay_tree_foreach (m_inner, inner_foreach_fn, &c); +/* Internal function for converting from splay_tree_node to + VALUE_TYPE. */ +template <typename KEY_TYPE, typename VALUE_TYPE> +inline VALUE_TYPE +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::node_to_value (splay_tree_node node) +{ + if (node) + return node->value; + else + return 0; } -/* Helper function for typed_splay_tree::foreach. */ +template <typename KEY_TYPE, typename VALUE_TYPE> +inline void +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::KDEL(splay_tree_key x) +{ + if (delete_key) + (*delete_key)(x); +} template <typename KEY_TYPE, typename VALUE_TYPE> +inline void +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::VDEL(splay_tree_value x) +{ + if (delete_value) + (*delete_value)(x); +} + +/* Deallocate NODE (a member of SP), and all its sub-trees. */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +void +typed_splay_tree<KEY_TYPE, + VALUE_TYPE>::splay_tree_delete_helper (splay_tree_node node) +{ + splay_tree_node pending = NULL; + splay_tree_node active = NULL; + + if (!node) + return; + + KDEL (node->key); + VDEL (node->value); + + /* We use the "back" field to hold the "next" pointer. */ + node->back = pending; + pending = node; + + /* Now, keep processing the pending list until there aren't any + more. This is a little more complicated than just recursing, but + it doesn't toast the stack for large trees. */ + + while (pending) + { + active = pending; + pending = NULL; + while (active) + { + splay_tree_node temp; + + /* active points to a node which has its key and value + deallocated, we just need to process left and right. */ + + if (active->left) + { + KDEL (active->left->key); + VDEL (active->left->value); + active->left->back = pending; + pending = active->left; + } + if (active->right) + { + KDEL (active->right->key); + VDEL (active->right->value); + active->right->back = pending; + pending = active->right; + } + + temp = active; + active = temp->back; + delete temp; + } + } +} + +/* Rotate the edge joining the left child N with its parent P. PP is the + grandparents' pointer to P. */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +inline void +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::rotate_left (splay_tree_node *pp, + splay_tree_node p, + splay_tree_node n) +{ + splay_tree_node tmp; + tmp = n->right; + n->right = p; + p->left = tmp; + *pp = n; +} + +/* Rotate the edge joining the right child N with its parent P. PP is the + grandparents' pointer to P. */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +inline void +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::rotate_right (splay_tree_node *pp, + splay_tree_node p, + splay_tree_node n) +{ + splay_tree_node tmp; + tmp = n->left; + n->left = p; + p->right = tmp; + *pp = n; +} + +/* Bottom up splay of key. */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +void +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_splay (splay_tree_key key) +{ + if (root == NULL) + return; + + do { + int cmp1, cmp2; + splay_tree_node n, c; + + n = root; + cmp1 = (*comp) (key, n->key); + + /* Found. */ + if (cmp1 == 0) + return; + + /* Left or right? If no child, then we're done. */ + if (cmp1 < 0) + c = n->left; + else + c = n->right; + if (!c) + return; + + /* Next one left or right? If found or no child, we're done + after one rotation. */ + cmp2 = (*comp) (key, c->key); + if (cmp2 == 0 + || (cmp2 < 0 && !c->left) + || (cmp2 > 0 && !c->right)) + { + if (cmp1 < 0) + rotate_left (&root, n, c); + else + rotate_right (&root, n, c); + return; + } + + /* Now we have the four cases of double-rotation. */ + if (cmp1 < 0 && cmp2 < 0) + { + rotate_left (&n->left, c, c->left); + rotate_left (&root, n, n->left); + } + else if (cmp1 > 0 && cmp2 > 0) + { + rotate_right (&n->right, c, c->right); + rotate_right (&root, n, n->right); + } + else if (cmp1 < 0 && cmp2 > 0) + { + rotate_right (&n->left, c, c->right); + rotate_left (&root, n, n->left); + } + else if (cmp1 > 0 && cmp2 < 0) + { + rotate_left (&n->right, c, c->left); + rotate_right (&root, n, n->right); + } + } while (1); +} + +/* Call FN, passing it the DATA, for every node below NODE, all of + which are from SP, following an in-order traversal. If FN every + returns a non-zero value, the iteration ceases immediately, and the + value is returned. Otherwise, this function returns 0. */ + +template <typename KEY_TYPE, typename VALUE_TYPE> int -typed_splay_tree<KEY_TYPE, VALUE_TYPE>::inner_foreach_fn (splay_tree_node node, - void *user_data) +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_foreach_helper ( + splay_tree_node node, + foreach_fn fn, void *data) { - closure *c = (closure *)user_data; + int val; + splay_tree_node stack; - return c->m_outer_cb ((KEY_TYPE)node->key, (VALUE_TYPE)node->value, - c->m_outer_user_data); + /* A non-recursive implementation is used to avoid filling the stack + for large trees. Splay trees are worst case O(n) in the depth of + the tree. */ + + stack = NULL; + val = 0; + + for (;;) + { + while (node != NULL) + { + node->back = stack; + stack = node; + node = node->left; + } + + if (stack == NULL) + break; + + node = stack; + stack = stack->back; + + val = (*fn) (node->key, node->value, data); + if (val) + break; + + node = node->right; + } + + return val; } -/* Internal function for converting from splay_tree_node to - VALUE_TYPE. */ +/* Insert a new node (associating KEY with DATA) into SP. If a + previous node with the indicated KEY exists, its data is replaced + with the new value. Returns the new node. */ + template <typename KEY_TYPE, typename VALUE_TYPE> -inline VALUE_TYPE -typed_splay_tree<KEY_TYPE, VALUE_TYPE>::node_to_value (splay_tree_node node) +typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_insert ( + splay_tree_key key, + splay_tree_value value) { - if (node) - return (value_type)node->value; + int comparison = 0; + + splay_tree_splay (key); + + if (root) + comparison = (*comp)(root->key, key); + + if (root && comparison == 0) + { + /* If the root of the tree already has the indicated KEY, just + replace the value with VALUE. */ + VDEL(root->value); + root->value = value; + } else + { + /* Create a new node, and insert it at the root. */ + splay_tree_node node; + + node = new splay_tree_node_s; + node->key = key; + node->value = value; + + if (!root) + node->left = node->right = 0; + else if (comparison < 0) + { + node->left = root; + node->right = node->left->right; + node->left->right = 0; + } + else + { + node->right = root; + node->left = node->right->left; + node->right->left = 0; + } + + root = node; + } + + return root; +} + +/* Remove KEY from SP. It is not an error if it did not exist. */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +void +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_remove (splay_tree_key key) +{ + splay_tree_splay (key); + + if (root && (*comp) (root->key, key) == 0) + { + splay_tree_node left, right; + + left = root->left; + right = root->right; + + /* Delete the root node itself. */ + VDEL (root->value); + delete root; + + /* One of the children is now the root. Doesn't matter much + which, so long as we preserve the properties of the tree. */ + if (left) + { + root = left; + + /* If there was a right child as well, hang it off the + right-most leaf of the left child. */ + if (right) + { + while (left->right) + left = left->right; + left->right = right; + } + } + else + root = right; + } +} + +/* Lookup KEY in SP, returning VALUE if present, and NULL + otherwise. */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_lookup (splay_tree_key key) +{ + splay_tree_splay (key); + + if (root && (*comp)(root->key, key) == 0) + return root; + else return 0; } +/* Return the node in SP with the greatest key. */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_max () +{ + splay_tree_node n = root; + + if (!n) + return NULL; + + while (n->right) + n = n->right; + + return n; +} + +/* Return the node in SP with the smallest key. */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node +typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_min () +{ + splay_tree_node n = root; + + if (!n) + return NULL; + + while (n->left) + n = n->left; + + return n; +} + +/* Return the immediate predecessor KEY, or NULL if there is no + predecessor. KEY need not be present in the tree. */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node +typed_splay_tree<KEY_TYPE, + VALUE_TYPE>::splay_tree_predecessor (splay_tree_key key) +{ + int comparison; + splay_tree_node node; + + /* If the tree is empty, there is certainly no predecessor. */ + if (!root) + return NULL; + + /* Splay the tree around KEY. That will leave either the KEY + itself, its predecessor, or its successor at the root. */ + splay_tree_splay (key); + comparison = (*comp)(root->key, key); + + /* If the predecessor is at the root, just return it. */ + if (comparison < 0) + return root; + + /* Otherwise, find the rightmost element of the left subtree. */ + node = root->left; + if (node) + while (node->right) + node = node->right; + + return node; +} + +/* Return the immediate successor KEY, or NULL if there is no + successor. KEY need not be present in the tree. */ + +template <typename KEY_TYPE, typename VALUE_TYPE> +typename typed_splay_tree<KEY_TYPE, VALUE_TYPE>::splay_tree_node +typed_splay_tree<KEY_TYPE, + VALUE_TYPE>::splay_tree_successor (splay_tree_key key) +{ + int comparison; + splay_tree_node node; + + /* If the tree is empty, there is certainly no successor. */ + if (!root) + return NULL; + + /* Splay the tree around KEY. That will leave either the KEY + itself, its predecessor, or its successor at the root. */ + splay_tree_splay (key); + comparison = (*comp)(root->key, key); + + /* If the successor is at the root, just return it. */ + if (comparison > 0) + return root; + + /* Otherwise, find the leftmost element of the right subtree. */ + node = root->right; + if (node) + while (node->left) + node = node->left; + + return node; +} + #endif /* GCC_TYPED_SPLAY_TREE_H */