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  
attempt choosing 1-of-N exclusively as described here:


and perhaps finish up "option groups" for feature parity with  
(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.