[clug] access control list search algorithms

[Paul TBBle Hampson]

On Thu, Apr 02, 2009 at 02:37:06PM +1100, jm wrote:
> jm wrote:
> >Does anyone know of any algorithms for speeding up searching of access control lists? Is there anything more efficient than a sequential search?

> >Jeff.

> I should elaborate. I'm mucking about with email trying to develop a
> progrom to give finer control over smtp delivery. My ACL is made up of
> senders and recipients with wildcards thrown in for good measure. For
> example,

> index        sender                           recipient                  action
> 1              fred at example.org         '*'                             allow
> 2              '*'                                  joe at example.org     deny
> 3             admin at example.org    '*'                               allow

Key-value DB or equivalent is prolly the best you're going to get,
although you're really looking at doing up to four lookups:
sender-recipient, sender-*, *-recipient, *-* (default).

If you're looking at more interesting wildcards... Then maybe not. But
wildcards are _always_ gonna be slow. If you limit it to *@example.org
then you're just adding another... 4 lookups at the worst case.

If you're doing this for Postfix's policy support thing, then that's
prolly sufficient. You might even be able to mangle postmap into doing
the db generation for you.

Someone needs to invent a regexp-value DB maybe... Pregenerate hashes
for certain common regexps?

-- 
-----------------------------------------------------------
Paul "TBBle" Hampson, B.Sc, LPI, MCSE
Very-later-year Asian Studies student, ANU
The Boss, Bubblesworth Pty Ltd (ABN: 51 095 284 361)
Paul.Hampson at Pobox.com

Of course Pacman didn't influence us as kids. If it did,
we'd be running around in darkened rooms, popping pills and
listening to repetitive music.
 -- Kristian Wilson, Nintendo, Inc, 1989

License: http://creativecommons.org/licenses/by/2.5/au/
-----------------------------------------------------------
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 197 bytes
Desc: not available
Url : http://lists.samba.org/archive/linux/attachments/20090402/43b9f2ce/attachment.bin