[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: [Lua Workshop 2017] RE: Efficient Layer 7 Search of IP Address Space in LuaJIT/OpenResty
- From: Russell Haley <russ.haley@...>
- Date: Thu, 19 Oct 2017 10:54:48 -0700
On Thu, Oct 19, 2017 at 10:47 AM, William Ahern
<william@25thandclement.com> wrote:
> 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
I ❤ Daniel Bernstein. He's my hero.
Russ
