-/* Returns true if 'a' and 'b' match, ignoring fields for which the wildcards
- * in 'wildcards' are set. 'nw_src_mask' and 'nw_dst_mask' must be those that
- * would be set for 'wildcards' by cls_rule_set_masks(). 'field_idx' is the
- * index of the first field to be compared; fields before 'field_idx' are
- * assumed to match. (Always returns true if 'field_idx' is CLS_N_FIELDS.) */
-static bool
-rules_match(const struct cls_rule *a, const struct cls_rule *b,
- uint32_t wildcards, uint32_t nw_src_mask, uint32_t nw_dst_mask,
- int field_idx)
-{
- /* This is related to Duff's device (see
- * http://en.wikipedia.org/wiki/Duff's_device). */
- switch (field_idx) {
-#define CLS_FIELD(WILDCARDS, MEMBER, NAME) \
- case CLS_F_IDX_##NAME: \
- if (!field_matches(&a->flow, &b->flow, \
- wildcards, nw_src_mask, nw_dst_mask, \
- WILDCARDS, offsetof(flow_t, MEMBER), \
- sizeof a->flow.MEMBER)) { \
- return false; \
- } \
- /* Fall though */
- CLS_FIELDS
-#undef CLS_FIELD
+/* Return min(TRIE_PREFIX_BITS, plen) bits of the 'prefix', starting at bit
+ * offset 'ofs'. Prefixes are in the network byte order, and the offset 0
+ * corresponds to the most significant bit of the first byte. The offset can
+ * be read as "how many bits to skip from the start of the prefix starting at
+ * 'pr'". */
+static uint32_t
+trie_get_prefix(const ovs_be32 pr[], unsigned int ofs, unsigned int plen)
+{
+ if (!plen) {
+ return 0;
+ }
+ if (plen > TRIE_PREFIX_BITS) {
+ plen = TRIE_PREFIX_BITS; /* Get at most TRIE_PREFIX_BITS. */
+ }
+ /* Return with unwanted bits cleared. */
+ return raw_get_prefix(pr, ofs, plen) & ~0u << (32 - plen);
+}
+
+/* Return the number of equal bits in 'nbits' of 'prefix's MSBs and a 'value'
+ * starting at "MSB 0"-based offset 'ofs'. */
+static unsigned int
+prefix_equal_bits(uint32_t prefix, unsigned int nbits, const ovs_be32 value[],
+ unsigned int ofs)
+{
+ uint64_t diff = prefix ^ raw_get_prefix(value, ofs, nbits);
+ /* Set the bit after the relevant bits to limit the result. */
+ return raw_clz64(diff << 32 | UINT64_C(1) << (63 - nbits));
+}
+
+/* Return the number of equal bits in 'node' prefix and a 'prefix' of length
+ * 'plen', starting at "MSB 0"-based offset 'ofs'. */
+static unsigned int
+trie_prefix_equal_bits(const struct trie_node *node, const ovs_be32 prefix[],
+ unsigned int ofs, unsigned int plen)
+{
+ return prefix_equal_bits(node->prefix, MIN(node->nbits, plen - ofs),
+ prefix, ofs);
+}
+
+/* Return the bit at ("MSB 0"-based) offset 'ofs' as an int. 'ofs' can
+ * be greater than 31. */
+static unsigned int
+be_get_bit_at(const ovs_be32 value[], unsigned int ofs)
+{
+ return (((const uint8_t *)value)[ofs / 8] >> (7 - ofs % 8)) & 1u;
+}
+
+/* Return the bit at ("MSB 0"-based) offset 'ofs' as an int. 'ofs' must
+ * be between 0 and 31, inclusive. */
+static unsigned int
+get_bit_at(const uint32_t prefix, unsigned int ofs)
+{
+ return (prefix >> (31 - ofs)) & 1u;
+}
+
+/* Create new branch. */
+static struct trie_node *
+trie_branch_create(const ovs_be32 *prefix, unsigned int ofs, unsigned int plen,
+ unsigned int n_rules)
+{
+ struct trie_node *node = xmalloc(sizeof *node);
+
+ node->prefix = trie_get_prefix(prefix, ofs, plen);
+
+ if (plen <= TRIE_PREFIX_BITS) {
+ node->nbits = plen;
+ node->edges[0] = NULL;
+ node->edges[1] = NULL;
+ node->n_rules = n_rules;
+ } else { /* Need intermediate nodes. */
+ struct trie_node *subnode = trie_branch_create(prefix,
+ ofs + TRIE_PREFIX_BITS,
+ plen - TRIE_PREFIX_BITS,
+ n_rules);
+ int bit = get_bit_at(subnode->prefix, 0);
+ node->nbits = TRIE_PREFIX_BITS;
+ node->edges[bit] = subnode;
+ node->edges[!bit] = NULL;
+ node->n_rules = 0;
+ }
+ return node;
+}
+
+static void
+trie_node_destroy(struct trie_node *node)
+{
+ free(node);
+}
+
+static void
+trie_destroy(struct trie_node *node)
+{
+ if (node) {
+ trie_destroy(node->edges[0]);
+ trie_destroy(node->edges[1]);
+ free(node);