From patchwork Fri Jun 8 14:03:47 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bernd Edlinger X-Patchwork-Id: 926834 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-479350-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=hotmail.de Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="QpTqy3DC"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 412PKJ5dzVz9s1B for ; Sat, 9 Jun 2018 00:04:03 +1000 (AEST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:content-type:mime-version; q=dns; s=default; b=npAUnx/MGQisg+MR1HAq9iJecPOBxhpsXuDpxC8twjEWeLFVd2 8JR1rm7JPAHxx4RbKm4iSuJTeNgWO+2t06Q8I3G2PHk+PFiaorwB5s7cunogY6vf GE/gV4pZS2kgeeO7uq4rfXzmc6l+4iRdp8Qu6SiPf4X6s+3RfAQ8/MTpI= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:content-type:mime-version; s= default; bh=+VxNWhh37oVHVDqXg1oYfJO/h6k=; b=QpTqy3DCsHQZXOBoALS5 yomPqqJ8K0mJA8WJd3wxxP8/2XLSHz4RnqzlbY9xWjEQDBs0nIlIxIIgVS3iqjQB MfO6acZgpE4rTf5y6Tf5b+JX1q1+o4vAl5WyxmMinZwo0SB73yRRZ6165EoNuNAz jOzcDYSJaDKVzmM8tUJMrvE= Received: (qmail 102594 invoked by alias); 8 Jun 2018 14:03:55 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 102052 invoked by uid 89); 8 Jun 2018 14:03:54 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-10.3 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS, KAM_NUMSUBJECT, RCVD_IN_DNSWL_NONE, SPF_HELO_PASS, SPF_PASS autolearn=ham version=3.3.2 spammy=U*bernd.edlinger, bernd.edlinger@hotmail.de, D*hotmail.de, sk:bernd.e X-HELO: EUR03-VE1-obe.outbound.protection.outlook.com Received: from mail-oln040092072036.outbound.protection.outlook.com (HELO EUR03-VE1-obe.outbound.protection.outlook.com) (40.92.72.36) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 08 Jun 2018 14:03:51 +0000 Received: from VE1EUR03FT004.eop-EUR03.prod.protection.outlook.com (10.152.18.57) by VE1EUR03HT007.eop-EUR03.prod.protection.outlook.com (10.152.18.79) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P256) id 15.20.841.10; Fri, 8 Jun 2018 14:03:47 +0000 Received: from AM5PR0701MB2657.eurprd07.prod.outlook.com (10.152.18.52) by VE1EUR03FT004.mail.protection.outlook.com (10.152.18.106) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.20.841.10 via Frontend Transport; Fri, 8 Jun 2018 14:03:47 +0000 Received: from AM5PR0701MB2657.eurprd07.prod.outlook.com ([fe80::106:1799:3361:8e9a]) by AM5PR0701MB2657.eurprd07.prod.outlook.com ([fe80::106:1799:3361:8e9a%2]) with mapi id 15.20.0841.011; Fri, 8 Jun 2018 14:03:47 +0000 From: Bernd Edlinger To: "gcc-patches@gcc.gnu.org" CC: Richard Biener , Jakub Jelinek , David Malcolm Subject: [PATCH] Avoid excessive function type casts with splay-trees part 2 Date: Fri, 8 Jun 2018 14:03:47 +0000 Message-ID: x-clientproxiedby: AM5PR0601CA0033.eurprd06.prod.outlook.com (2603:10a6:203:68::19) To AM5PR0701MB2657.eurprd07.prod.outlook.com (2603:10a6:203:75::7) x-incomingtopheadermarker: OriginalChecksum:52C1368C25366491E7EF7799D3FE567391AE1426F0DA8E67C1A129DA148D5CA1; UpperCasedChecksum:7E605315248640F0FCBF8DFE150FAD22B31A03365F1DCBA957F6251B52AB4058; SizeAsReceived:7480; Count:48 x-ms-exchange-messagesentrepresentingtype: 1 x-tmn: [Zc8JkJ/iXKQN/gADIX1Td96PD2UXI/jZ] x-ms-publictraffictype: Email x-incomingheadercount: 48 x-eopattributedmessage: 0 x-ms-traffictypediagnostic: VE1EUR03HT007: x-forefront-prvs: 06973FFAD3 received-spf: None (protection.outlook.com: hotmail.de does not designate permitted sender hosts) authentication-results: spf=none (sender IP is ) smtp.mailfrom=bernd.edlinger@hotmail.de; MIME-Version: 1.0 X-MS-Office365-Filtering-Correlation-Id: 933e7f5e-30f8-46b3-642b-08d5cd48a6d1 X-OriginatorOrg: outlook.com X-MS-Exchange-CrossTenant-RMS-PersistedConsumerOrg: d4d70346-2c10-4f39-8c00-e767963926d9 X-MS-Exchange-CrossTenant-Network-Message-Id: 933e7f5e-30f8-46b3-642b-08d5cd48a6d1 X-MS-Exchange-CrossTenant-rms-persistedconsumerorg: d4d70346-2c10-4f39-8c00-e767963926d9 X-MS-Exchange-CrossTenant-originalarrivaltime: 08 Jun 2018 14:03:47.2404 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Internet X-MS-Exchange-CrossTenant-id: 84df9e7f-e9f6-40af-b435-aaaaaaaaaaaa X-MS-Exchange-Transport-CrossTenantHeadersStamped: VE1EUR03HT007 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? Thanks Bernd. 2018-06-08 Bernd Edlinger * typed-splay-tree.h (typed_splay_tree::remove): New function. (typed_splay_tree::closure, typed_splay_tree::inner_foreach_fn, typed_splay_tree::m_inner): Deleted. (typed_splay_tree::typed_splay_tree, typed_splay_tree::operator =): Declared private. (typed_splay_tree::splay_tree_key, typed_splay_tree::splay_tree_value, typed_splay_tree::splay_tree_node_s, typed_splay_tree::KDEL, typed_splay_tree::VDEL, typed_splay_tree::splay_tree_delete_helper, typed_splay_tree::rotate_left, typed_splay_tree::rotate_right, typed_splay_tree::splay_tree_splay, typed_splay_tree::splay_tree_foreach_helper, typed_splay_tree::splay_tree_insert, typed_splay_tree::splay_tree_remove, typed_splay_tree::splay_tree_lookup, typed_splay_tree::splay_tree_predecessor, typed_splay_tree::splay_tree_successor, typed_splay_tree::splay_tree_min, typed_splay_tree::splay_tree_max): Took over from splay-tree.c/.h. (typed_splay_tree::root, typed_splay_tree::comp, typed_splay_tree::delete_key, typed_splay_tree::delete_value): New data members. * typed-splay-tree.c (selftest::test_str_to_int): Add a test for typed_splay_tree::remove. 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 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 . */ @@ -75,12 +112,10 @@ inline typed_splay_tree:: 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 . */ @@ -89,7 +124,7 @@ template inline typed_splay_tree:: ~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 inline VALUE_TYPE typed_splay_tree::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 inline VALUE_TYPE typed_splay_tree::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::predecesso template inline VALUE_TYPE -typed_splay_tree::successor (key_type k) +typed_splay_tree::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::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 +inline void +typed_splay_tree::remove (key_type key) +{ + splay_tree_remove (key); +} + /* Get the value with maximal key. */ template @@ -145,7 +187,7 @@ template inline VALUE_TYPE typed_splay_tree::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 inline VALUE_TYPE typed_splay_tree::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::min () template inline int -typed_splay_tree::foreach (foreach_fn outer_cb, - void *outer_user_data) +typed_splay_tree::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 +inline VALUE_TYPE +typed_splay_tree::node_to_value (splay_tree_node node) +{ + if (node) + return node->value; + else + return 0; } -/* Helper function for typed_splay_tree::foreach. */ +template +inline void +typed_splay_tree::KDEL(splay_tree_key x) +{ + if (delete_key) + (*delete_key)(x); +} template +inline void +typed_splay_tree::VDEL(splay_tree_value x) +{ + if (delete_value) + (*delete_value)(x); +} + +/* Deallocate NODE (a member of SP), and all its sub-trees. */ + +template +void +typed_splay_tree::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 +inline void +typed_splay_tree::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 +inline void +typed_splay_tree::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 +void +typed_splay_tree::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 int -typed_splay_tree::inner_foreach_fn (splay_tree_node node, - void *user_data) +typed_splay_tree::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 -inline VALUE_TYPE -typed_splay_tree::node_to_value (splay_tree_node node) +typename typed_splay_tree::splay_tree_node +typed_splay_tree::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 +void +typed_splay_tree::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 typed_splay_tree::splay_tree_node +typed_splay_tree::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 typed_splay_tree::splay_tree_node +typed_splay_tree::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 typed_splay_tree::splay_tree_node +typed_splay_tree::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 typed_splay_tree::splay_tree_node +typed_splay_tree::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 typed_splay_tree::splay_tree_node +typed_splay_tree::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 */