one pass switch code (was forward references in typedefs)

[Chris Torek]

>In article <18735 at mimsy.UUCP> chris at mimsy.UUCP (Chris Torek) writes:
>>... PCC has used ... direct, heap, and jump table switches ...

In article <67 at motto.UUCP> dave at motto.UUCP (dave brown) writes:
>I understand direct and jump table switches, but what's a heap switch?

This might be PCC's private name for it; everyone else seems to call
it a binary switch.  Basically, if you have a complete, sorted binary
tree, you can start at the root, compare, branch to case if equal,
branch to `must be on the right' if >, handle left subtree, branch
to default, generate label for `must be on the right', handle right
subtree.

Having a complete binary tree (which is a condition for heaps) means
shorter code paths.  A plain binary tree will work, but if it is
unbalanced you will end up doing more comparisons than necessary.
(`Complete' means that if you number the nodes like this:

			1
		2		3
	     4     5	     6     7
	    8 9  10 11     12 13 14 15

that the `holes' are at the bottom right, in the highest numbered
slots; this means there is a compact array representation for the
tree.  A tree can be balanced without being complete, but not vice
versa.)
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris at mimsy.umd.edu	Path:	uunet!mimsy!chris