[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]

*To*: <xtech>*Subject*: general fix for bounded recursion in ent*From*: Eric Dean Tribble <tribble>*Date*: Thu, 18 Oct 90 23:54:32 PDT

While talking about archiving, MarkM brought up the worries about recursive algorithms in the ent. We bounced it around a bit and I think the following is a general solution: Recur till you hit some limit (we could just fix a limit: never recur more than 500 times...). Only check this limit in SplitLoafs. Blast with the splitRegion (the region that differentiates its left from its right) (we could also use the accumulated limitRegion for operations that compute one). Transform to global coordinates on the way up. Catch the blast at the top, splay the region carried by the blast, and try the operation again. This will work even for non region-based operations like version compare (Hmmm... except the walk upwards...). It will also be much simpler than rewriting all the alorithms to be iterative. Essentially, optimistically assume that the tree is balanced enough. In the exceptional case that it isn't, move the deepest loaf you can reach to near the top and try again. The walk upwards (currently implemented in 'inTrace:') is the only algorithm that goes up a tree, and it is simple enough to modularly write iteratively. dean

- Prev by Date:
**Re: for superclasses** - Next by Date:
**archiving notes** - Previous by thread:
**creating a new messageHandler** - Next by thread:
**archiving notes** - Index(es):