Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!unmvax!ncar!tank!mimsy!chris
From: chris@mimsy.UUCP (Chris Torek)
Newsgroups: comp.lang.c
Subject: Re: one pass switch code (was forward references in typedefs)
Message-ID: <18764@mimsy.UUCP>
Date: 27 Jul 89 10:09:53 GMT
References: <55480@tut.cis.ohio-state.edu> <1989Jul20.152935.14872@utzoo.uucp> <67@motto.UUCP>
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 30

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

In article <67@motto.UUCP> dave@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@mimsy.umd.edu	Path:	uunet!mimsy!chris