Re: [PATCH 2/2] Rewrite jump_label.c to use binary search

[H. Peter Anvin]

On 09/22/2010 12:43 PM, Mathieu Desnoyers wrote:
> * H. Peter Anvin (hpa@xxxxxxxxx) wrote:
>> On 09/22/2010 03:08 AM, Andi Kleen wrote:
> 
> That's a very interesting idea, which applies very well to exception
> handlers, but tracepoints and static jumps suffer from the problem that
> there are many possible instances of the same key.
> 
> Tracepoints use a lookup by tracepoint name. Static jumps use a lookup
> by associated variable address (but this variable can be associated with
> many instances, e.g. in the case of static inline functions, or just
> when the same variable is used to control many instances of static
> jumps).
> 
> But maybe we could find a way to do an initial sort phase, so the
> perfect hash could point to the first entry corresponding to the looked
> up key ?
> 

In the case of multiple instances of the same key you want the perfect
hash to point to the cluster of solutions -- a list.  Since this is by
necessity something that needs to be done at compile time that list can
simply be an array.

	-hpa
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/