RPM Community Forums

Mailing List Message of <popt-devel>

Fwd: Adding option bit sets using Bloom filters?

From: Jeff Johnson <n3npq@mac.com>
Date: Sat 25 Jul 2009 - 18:09:17 CEST
Message-id: <24E30C10-1B92-4F83-A86C-49FC49D50174@mac.com>
Hmmm, this message never made it to popt-devel.

I'm attempting a Bloom filter implementation in popt now, will likely  
also
attempt choosing 1-of-N exclusively as described here:

	http://rpm5.org/community/popt-devel/0112.html

and perhaps finish up "option groups" for feature parity with  
getopt_long()
(but perhaps not, option groups would be very annoying to do correctly).

So last chance to voice an opinion ...

73 de Jeff

Begin forwarded message:

> From: Jeff Johnson <n3npq@mac.com>
> Date: July 10, 2009 11:24:46 AM EDT
> To: popt-devel@rpm5.org
> Subject: Adding option bit sets using Bloom filters?
>
> One of the problems that I frequently encounter in RPM using
> POPT is the tedium of keeping track of bits and names and
> options and functionality, i.e. all the bleeping baggage.
>
> The usual problem that I have in RPM is that I end up running out of  
> bits.
>
> One solution would be to use a Bloom filter for a open-ended class  
> of options
> that map to bits. One Bloom filter would be needed to establish
> whether an option is in the permitted set, another Bloom filter would
> be needed to return values that were explicitly mentioned.
>
> The nice thing about Bloom filters is that they partition all
> possible option strings without the tedium of committing to
> an explicit mapping onto bits.
>
> I'd likely do the implementation slightly differently than
> most option processing, marking a subtable (which carries the strings
> necessary to initialize the permitted option Bloom filter) in
> this field in struct poptOption:
> 	/*@observer@*/ /*@null@*/
> 	const char * longName;
> and returning which (possibly multiple) options were seen (as always  
> in popt) in
> 	/*@shared@*/ /*@null@*/
> 	void * arg;                 /*!< depends on argInfo */
> with the {m,k} parameters used for the Bloom filter overloaded into
> 	char shortName; 	    /*!< may be NUL */
> 	int val;                    /*!< 0 means don't return, just update  
> flag */
>
> For more on Bloom filters, see
>
> 	http://en.wikipedia.org/wiki/Bloom_filters
>
> I already have an implementation in RPM that could be moved
> to POPT, the implementation is quite straight-forward.
>
> Opinions? I'll likely proceed with an implementation the
> next time I get to popt hacking.
>
> 73 de Jeff
>
Received on Sat Jul 25 18:09:52 2009
Driven by Jeff Johnson and the RPM project team.
Hosted by OpenPKG and Ralf S. Engelschall.
Powered by FreeBSD and OpenPKG.