[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]
general fix for bounded recursion in ent
- 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.