[ovs-dev] [classifier-opt 28/28] Introduce sparse flows and masks, to reduce memory usage and improve speed.

[Isaku Yamahata]

On Fri, Jul 20, 2012 at 04:25:25PM -0700, Ben Pfaff wrote:
> diff --git a/lib/flow.c b/lib/flow.c
> index a5076bb..7b50b0b 100644
> --- a/lib/flow.c
> +++ b/lib/flow.c

...snip...

> +/* Initializes 'dst' as the bit-wise "and" of 'a' and 'b'.
> + *
> + * The caller must provide room for FLOW_U32S "uint32_t"s in 'storage', for use
> + * by 'dst'.  The caller must *not* free 'dst' with minimask_destroy(). */
> +void
> +minimask_combine(struct minimask *dst_,
> +                 const struct minimask *a_, const struct minimask *b_,
> +                 uint32_t storage[FLOW_U32S])
> +{
> +    struct miniflow *dst = &dst_->masks;
> +    const struct miniflow *a = &a_->masks;
> +    const struct miniflow *b = &b_->masks;
> +    int i, n;
> +
> +    n = 0;
> +    dst->values = storage;
> +    for (i = 0; i < MINI_N_MAPS; i++) {
> +        uint32_t map = a->map[i] & b->map[i];
> +
> +        dst->map[i] = 0;
> +        for (map = dst->map[i]; map; map = zero_rightmost_1bit(map)) {
                ^^^^^^^^^^^^^^^^^
                map = a->map[i] & b->map[i];
typo.


> +            int ofs = raw_ctz(map) + i * 32;
> +            uint32_t mask = miniflow_get(a, ofs) & miniflow_get(b, ofs);
> +
> +            if (mask) {
> +                dst->map[i] |= rightmost_1bit(map);
> +                dst->values[n++] = mask;
> +            }
> +        }
> +    }
> +}
-- 
yamahata