Submitter | Doug Evans |
---|---|

Date | Dec. 5, 2010, 7:34 p.m. |

Message ID | <20101205193453.428A72461AB@ruffy.mtv.corp.google.com> |

Download | mbox | patch |

Permalink | /patch/74303/ |

State | New |

Headers | show |

## Comments

On Sun, Dec 5, 2010 at 11:34 AM, Doug Evans <dje@google.com> wrote: > 2010-12-05 Doug Evans <dje@google.com> > > * splay-tree.c (splay_tree_foreach_helper): Remove arg `sp', > all callers updated. Rewrite to be non-recursive. This is OK if you rewrite xmalloc to XNEWVEC, xrealloc to XRESIZEVEC, and free to XDELETEVEC. Thanks. Ian

## Patch

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. */