Path: csiph.com!usenet.pasdenom.info!gegeweb.org!de-l.enfer-du-nord.net!feeder2.enfer-du-nord.net!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: Rainer Weikusat <rweikusat@mssgmbh.com>
Newsgroups: comp.programming,comp.unix.programmer
Subject: Re: hash function over IP address
Date: Thu, 05 Apr 2012 15:04:12 +0100
Lines: 44
Message-ID: <87bon65l7n.fsf@sapphire.mobileactivedefense.com>
References: <jliber$ocn$1@speranza.aioe.org> <jlir5m$dd8$1@dont-email.me> <jlk3um$pog$1@speranza.aioe.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Trace: individual.net 5lfk6PXU3GH0f3TBXDMtRQQxxOKFhRInAlpOY5y+TagptADIc=
Cancel-Lock: sha1:DLBN1irc+Gj4/WTHUB7EbxZ2Dyc= sha1:JIxIhdWJF4EYzZqUzu+jurX7t3M=
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.2 (gnu/linux)
Xref: csiph.com comp.programming:1426 comp.unix.programmer:2368

"Mark" <mark_cruzNOTFORSPAM@hotmail.com> writes:
> First of all, thanks for comments. What I'm trying to solve is to find a way 
> to search in  AVL tree used in IP routing application. Initially a tree's 
> node looked simple:
>
> struct nhlfe_entry
> {
>   u_int32_t nhlfe_ix;
>   u_char opcode;
>   ...
>   struct nhlfe_key key;  /* nexthop key */
> }
>
> /* defines a search key. */
> struct nhlfe_key
> {
>   struct in_addr nh_addr;
>   u_int32_t oif_ix;
>   u_int32_t out_label;
> }
>
> So the search was based on 'struct nhlfe_key'. Now, what I'm trying to add 
> support for multiple next hops, that is I add a linked list in nhlfe_entry:
> struct nhlfe_entry{  u_int32_t nhlfe_ix;  u_char opcode;  ...  struct list 
> *nhkey_list;}where 'struct list' is struct listnode that embeds 'void *data' 
> pointer to caller'sprivate data, and this is 'struct nhlfe_key'.So I'm 
> trying to find the way to generate key based on multiple elements in the 
> list to store/search nodes in the tree.

The simplest solution would be to concatenate all 'next hops' in
order to form a key. A better idea would be to build a so-called radix
search trie based on keys like this. The best online description of
that I found quickly is:

	http://www.cs.hut.fi/Opinnot/T-106.253/k2002/english/extra/digital_search_tree.html

At least the ancient version of this book

	http://www.informit.com/store/product.aspx?isbn=0201314525

I happen to own contains a good description. In contrast to this, the
Wikipedia article completely useless, except as an excellent example
how language can be used to obscure phenomenons instead of explaining
them.