lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


On Thu, Oct 19, 2017 at 01:33:45PM +0100, dyngeccetor8 wrote:
> On 10/18/2017 06:17 AM, Sean Conner wrote:
> >   Assume the following addresses/masks:
> > 
> > 	0000/0000	(our default match for "no match")
> > 	1000/1000	addresses 8-15
> > 	0100/1100	addresses 4-7
> > 	0010/1111	address 2
> > 
> > So address 0, 1 and 3 (if my data is correct) should be a "no match".  A
> > constructed tree will look like:
> > 
> >                   [*]		0000/0000
> >                   / \
> >                  0   1
> >                 /     \
> >               [ ]     [*]	1000/1000
> >               / \     
> >              0   1  
> >             /     \ 
> >           [ ]     [*]		0100/1100
> >             \
> >              1
> >               \
> >               [ ]
> >               /
> >              0
> >             /
> >           [*]			0010/1111
> > 
> 
> Looks like TRIE structure for me.

More specifically, a crit-bit tree.

  https://cr.yp.to/critbit.html