+ /* Must insert a new tree branch for the new rule. */
+ *edge = trie_branch_create(prefix, ofs, mlen - ofs, 1);
+}
+
+/* 'mlen' must be the (non-zero) CIDR prefix length of the 'trie->field' mask
+ * in 'rule'. */
+static void
+trie_remove(struct cls_trie *trie, const struct cls_rule *rule, int mlen)
+{
+ const ovs_be32 *prefix = minimatch_get_prefix(&rule->match, trie->field);
+ struct trie_node *node;
+ struct trie_node **edges[sizeof(union mf_value) * 8];
+ int depth = 0, ofs = 0;
+
+ /* Walk the tree. */
+ for (edges[depth] = &trie->root;
+ (node = *edges[depth]) != NULL;
+ edges[++depth] = trie_next_edge(node, prefix, ofs)) {
+ unsigned int eqbits = trie_prefix_equal_bits(node, prefix, ofs, mlen);
+ if (eqbits < node->nbits) {
+ /* Mismatch, nothing to be removed. This should never happen, as
+ * only rules in the classifier are ever removed. */
+ break; /* Log a warning. */
+ }
+ /* Full match so far. */
+ ofs += eqbits;
+
+ if (ofs == mlen) {
+ /* Full prefix match at the current node, remove rule here. */
+ if (!node->n_rules) {
+ break; /* Log a warning. */
+ }
+ node->n_rules--;
+
+ /* Check if can prune the tree. */
+ while (!node->n_rules && !(node->edges[0] && node->edges[1])) {
+ /* No rules and at most one child node, remove this node. */
+ struct trie_node *next;
+ next = node->edges[0] ? node->edges[0] : node->edges[1];
+
+ if (next) {
+ if (node->nbits + next->nbits > TRIE_PREFIX_BITS) {
+ break; /* Cannot combine. */
+ }
+ /* Combine node with next. */
+ next->prefix = node->prefix | next->prefix >> node->nbits;
+ next->nbits += node->nbits;
+ }
+ trie_node_destroy(node);
+ /* Update the parent's edge. */
+ *edges[depth] = next;
+ if (next || !depth) {
+ /* Branch not pruned or at root, nothing more to do. */
+ break;
+ }
+ node = *edges[--depth];
+ }
+ return;
+ }