From patchwork Sun Dec 5 19:34:53 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Doug Evans X-Patchwork-Id: 74303 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id C3C06B70CD for ; Mon, 6 Dec 2010 06:35:10 +1100 (EST) Received: (qmail 23054 invoked by alias); 5 Dec 2010 19:35:03 -0000 Received: (qmail 22948 invoked by uid 22791); 5 Dec 2010 19:35:01 -0000 X-SWARE-Spam-Status: No, hits=-1.9 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, SPF_HELO_PASS, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from smtp-out.google.com (HELO smtp-out.google.com) (216.239.44.51) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sun, 05 Dec 2010 19:34:56 +0000 Received: from kpbe20.cbf.corp.google.com (kpbe20.cbf.corp.google.com [172.25.105.84]) by smtp-out.google.com with ESMTP id oB5JYsSr015409 for ; Sun, 5 Dec 2010 11:34:54 -0800 Received: from ruffy.mtv.corp.google.com (ruffy.mtv.corp.google.com [172.18.118.116]) by kpbe20.cbf.corp.google.com with ESMTP id oB5JYrYT011087 for ; Sun, 5 Dec 2010 11:34:53 -0800 Received: by ruffy.mtv.corp.google.com (Postfix, from userid 67641) id 428A72461AB; Sun, 5 Dec 2010 11:34:53 -0800 (PST) To: gcc-patches@sourceware.org Subject: [RFA] rewrite splay_tree_foreach_helper to be non-recursive Message-Id: <20101205193453.428A72461AB@ruffy.mtv.corp.google.com> Date: Sun, 5 Dec 2010 11:34:53 -0800 (PST) From: dje@google.com (Doug Evans) X-System-Of-Record: true 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 Hi. Splay trees are worst case O(n) in the depth of tree, and I have an example with ~300000 entries (reading of the address table piece of the .gdb_index section for a large program). gdb segfaults because it runs out of stack. This patch converts splay_tree_foreach_helper to be non-recursive. One might want to use malloc here and return if it runs out of space (library utilities should let the caller deal with such things), but the API doesn't really provide for it, and the new version's behaviour is no different than the existing behaviour. It didn't make sense to create another foreach API call just for this, so I just rewrote the existing one. One might want gdb/addrmap.c to use something besides splay-trees, but that's more work, and this patch is generally useful anyways. Tested by running the gdb testsuite on amd64-linux, no regressions. Ok to check in? 2010-12-05 Doug Evans * splay-tree.c (splay_tree_foreach_helper): Remove arg `sp', all callers updated. Rewrite to be non-recursive. Index: splay-tree.c =================================================================== RCS file: /cvs/src/src/libiberty/splay-tree.c,v retrieving revision 1.18 diff -u -p -r1.18 splay-tree.c --- splay-tree.c 10 Jun 2010 18:30:24 -0000 1.18 +++ splay-tree.c 5 Dec 2010 09:07:28 -0000 @@ -44,7 +44,7 @@ static inline void rotate_left (splay_tr static inline void rotate_right (splay_tree_node *, splay_tree_node, splay_tree_node); static void splay_tree_splay (splay_tree, splay_tree_key); -static int splay_tree_foreach_helper (splay_tree, splay_tree_node, +static int splay_tree_foreach_helper (splay_tree_node, splay_tree_foreach_fn, void*); /* Deallocate NODE (a member of SP), and all its sub-trees. */ @@ -204,25 +204,48 @@ splay_tree_splay (splay_tree sp, splay_t value is returned. Otherwise, this function returns 0. */ static int -splay_tree_foreach_helper (splay_tree sp, splay_tree_node node, +splay_tree_foreach_helper (splay_tree_node node, splay_tree_foreach_fn fn, void *data) { int val; + splay_tree_node *stack; + int stack_ptr, stack_size; - if (!node) - return 0; +#define INITIAL_STACK_SIZE 100 + stack_size = INITIAL_STACK_SIZE; + stack_ptr = 0; + stack = (splay_tree_node*) xmalloc (stack_size * sizeof (splay_tree_node)); + val = 0; + + for (;;) + { + while (node != NULL) + { + if (stack_ptr == stack_size) + { + stack_size *= 2; + stack = (splay_tree_node*) + xrealloc (stack, stack_size * sizeof (splay_tree_node)); + } + stack[stack_ptr++] = node; + node = node->left; + } - val = splay_tree_foreach_helper (sp, node->left, fn, data); - if (val) - return val; - - val = (*fn)(node, data); - if (val) - return val; + if (stack_ptr == 0) + break; - return splay_tree_foreach_helper (sp, node->right, fn, data); -} + node = stack[--stack_ptr]; + + val = (*fn) (node, data); + if (val) + break; + + node = node->right; + } + free (stack); + return val; +} /* An allocator and deallocator based on xmalloc. */ static void * @@ -537,7 +560,7 @@ splay_tree_successor (splay_tree sp, spl int splay_tree_foreach (splay_tree sp, splay_tree_foreach_fn fn, void *data) { - return splay_tree_foreach_helper (sp, sp->root, fn, data); + return splay_tree_foreach_helper (sp->root, fn, data); } /* Splay-tree comparison function, treating the keys as ints. */