From 4ec3d7c7578e827a543cc0989a6cd4c1a10ee291 Mon Sep 17 00:00:00 2001 From: Daniele Di Proietto Date: Wed, 6 Apr 2016 18:53:59 -0700 Subject: [PATCH] hmap: Add HMAP_FOR_EACH_POP. Makes popping each member of the hmap a bit easier. Signed-off-by: Daniele Di Proietto Acked-by: Ben Pfaff --- lib/cfm.c | 5 ++--- lib/hmap.h | 20 +++++++++++++++++ lib/id-pool.c | 5 ++--- lib/learning-switch.c | 5 ++--- lib/netdev-linux.c | 5 ++--- lib/odp-util.c | 7 +++--- ofproto/bond.c | 10 ++++----- ofproto/in-band.c | 5 ++--- ofproto/ofproto-dpif-ipfix.c | 5 ++--- ofproto/ofproto-dpif-xlate.c | 5 ++--- ofproto/ofproto.c | 5 ++--- ofproto/pinsched.c | 5 ++--- ovn/controller/encaps.c | 5 ++--- ovn/controller/lport.c | 5 ++--- ovn/controller/ofctrl.c | 5 ++--- ovn/controller/physical.c | 4 +--- ovn/controller/pinctrl.c | 5 ++--- ovn/lib/expr.c | 5 ++--- ovn/northd/ovn-northd.c | 10 ++++----- ovsdb/monitor.c | 5 ++--- ovsdb/row.c | 5 ++--- tests/library.at | 2 +- tests/test-hmap.c | 42 ++++++++++++++++++++++++++++++++++++ 23 files changed, 107 insertions(+), 68 deletions(-) diff --git a/lib/cfm.c b/lib/cfm.c index cf1f72596..fb077de40 100644 --- a/lib/cfm.c +++ b/lib/cfm.c @@ -374,7 +374,7 @@ cfm_create(const struct netdev *netdev) OVS_EXCLUDED(mutex) void cfm_unref(struct cfm *cfm) OVS_EXCLUDED(mutex) { - struct remote_mp *rmp, *rmp_next; + struct remote_mp *rmp; if (!cfm) { return; @@ -389,8 +389,7 @@ cfm_unref(struct cfm *cfm) OVS_EXCLUDED(mutex) hmap_remove(all_cfms, &cfm->hmap_node); ovs_mutex_unlock(&mutex); - HMAP_FOR_EACH_SAFE (rmp, rmp_next, node, &cfm->remote_mps) { - hmap_remove(&cfm->remote_mps, &rmp->node); + HMAP_FOR_EACH_POP (rmp, node, &cfm->remote_mps) { free(rmp); } diff --git a/lib/hmap.h b/lib/hmap.h index 53e75cc62..f3da79ed7 100644 --- a/lib/hmap.h +++ b/lib/hmap.h @@ -193,6 +193,26 @@ bool hmap_contains(const struct hmap *, const struct hmap_node *); (NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER)) || (NODE = NULL); \ ASSIGN_CONTAINER(NODE, hmap_next(HMAP, &(NODE)->MEMBER), MEMBER)) +static inline struct hmap_node * +hmap_pop_helper__(struct hmap *hmap, size_t *bucket) { + + for (; *bucket <= hmap->mask; (*bucket)++) { + struct hmap_node *node = hmap->buckets[*bucket]; + + if (node) { + hmap_remove(hmap, node); + return node; + } + } + + return NULL; +} + +#define HMAP_FOR_EACH_POP(NODE, MEMBER, HMAP) \ + for (size_t bucket__ = 0; \ + INIT_CONTAINER(NODE, hmap_pop_helper__(HMAP, &bucket__), MEMBER), \ + (NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER)) || (NODE = NULL);) + static inline struct hmap_node *hmap_first(const struct hmap *); static inline struct hmap_node *hmap_next(const struct hmap *, const struct hmap_node *); diff --git a/lib/id-pool.c b/lib/id-pool.c index 6b93d3742..f32c008c9 100644 --- a/lib/id-pool.c +++ b/lib/id-pool.c @@ -69,10 +69,9 @@ id_pool_init(struct id_pool *pool, uint32_t base, uint32_t n_ids) static void id_pool_uninit(struct id_pool *pool) { - struct id_node *id_node, *next; + struct id_node *id_node; - HMAP_FOR_EACH_SAFE(id_node, next, node, &pool->map) { - hmap_remove(&pool->map, &id_node->node); + HMAP_FOR_EACH_POP(id_node, node, &pool->map) { free(id_node); } diff --git a/lib/learning-switch.c b/lib/learning-switch.c index c69ca4c62..b420fe5c3 100644 --- a/lib/learning-switch.c +++ b/lib/learning-switch.c @@ -269,11 +269,10 @@ void lswitch_destroy(struct lswitch *sw) { if (sw) { - struct lswitch_port *node, *next; + struct lswitch_port *node; rconn_destroy(sw->rconn); - HMAP_FOR_EACH_SAFE (node, next, hmap_node, &sw->queue_numbers) { - hmap_remove(&sw->queue_numbers, &node->hmap_node); + HMAP_FOR_EACH_POP (node, hmap_node, &sw->queue_numbers) { free(node); } shash_destroy(&sw->queue_names); diff --git a/lib/netdev-linux.c b/lib/netdev-linux.c index a2b6b8a25..2953964b6 100644 --- a/lib/netdev-linux.c +++ b/lib/netdev-linux.c @@ -3851,10 +3851,9 @@ static void htb_tc_destroy(struct tc *tc) { struct htb *htb = CONTAINER_OF(tc, struct htb, tc); - struct htb_class *hc, *next; + struct htb_class *hc; - HMAP_FOR_EACH_SAFE (hc, next, tc_queue.hmap_node, &htb->tc.queues) { - hmap_remove(&htb->tc.queues, &hc->tc_queue.hmap_node); + HMAP_FOR_EACH_POP (hc, tc_queue.hmap_node, &htb->tc.queues) { free(hc); } tc_destroy(tc); diff --git a/lib/odp-util.c b/lib/odp-util.c index 10fb6c24f..e0a1ad475 100644 --- a/lib/odp-util.c +++ b/lib/odp-util.c @@ -2081,10 +2081,9 @@ odp_portno_names_get(const struct hmap *portno_names, odp_port_t port_no) void odp_portno_names_destroy(struct hmap *portno_names) { - struct odp_portno_names *odp_portno_names, *odp_portno_names_next; - HMAP_FOR_EACH_SAFE (odp_portno_names, odp_portno_names_next, - hmap_node, portno_names) { - hmap_remove(portno_names, &odp_portno_names->hmap_node); + struct odp_portno_names *odp_portno_names; + + HMAP_FOR_EACH_POP (odp_portno_names, hmap_node, portno_names) { free(odp_portno_names->name); free(odp_portno_names); } diff --git a/ofproto/bond.c b/ofproto/bond.c index 0dbd0d270..032b8f61d 100644 --- a/ofproto/bond.c +++ b/ofproto/bond.c @@ -257,8 +257,8 @@ bond_ref(const struct bond *bond_) void bond_unref(struct bond *bond) { - struct bond_slave *slave, *next_slave; - struct bond_pr_rule_op *pr_op, *next_op; + struct bond_pr_rule_op *pr_op; + struct bond_slave *slave; if (!bond || ovs_refcount_unref_relaxed(&bond->ref_cnt) != 1) { return; @@ -268,8 +268,7 @@ bond_unref(struct bond *bond) hmap_remove(all_bonds, &bond->hmap_node); ovs_rwlock_unlock(&rwlock); - HMAP_FOR_EACH_SAFE (slave, next_slave, hmap_node, &bond->slaves) { - hmap_remove(&bond->slaves, &slave->hmap_node); + HMAP_FOR_EACH_POP (slave, hmap_node, &bond->slaves) { /* Client owns 'slave->netdev'. */ free(slave->name); free(slave); @@ -280,8 +279,7 @@ bond_unref(struct bond *bond) free(bond->hash); free(bond->name); - HMAP_FOR_EACH_SAFE(pr_op, next_op, hmap_node, &bond->pr_rule_ops) { - hmap_remove(&bond->pr_rule_ops, &pr_op->hmap_node); + HMAP_FOR_EACH_POP (pr_op, hmap_node, &bond->pr_rule_ops) { free(pr_op); } hmap_destroy(&bond->pr_rule_ops); diff --git a/ofproto/in-band.c b/ofproto/in-band.c index efea19fd8..36e80f493 100644 --- a/ofproto/in-band.c +++ b/ofproto/in-band.c @@ -449,10 +449,9 @@ void in_band_destroy(struct in_band *ib) { if (ib) { - struct in_band_rule *rule, *next; + struct in_band_rule *rule; - HMAP_FOR_EACH_SAFE (rule, next, hmap_node, &ib->rules) { - hmap_remove(&ib->rules, &rule->hmap_node); + HMAP_FOR_EACH_POP (rule, hmap_node, &ib->rules) { free(rule); } hmap_destroy(&ib->rules); diff --git a/ofproto/ofproto-dpif-ipfix.c b/ofproto/ofproto-dpif-ipfix.c index 6d088a6f2..59cd88429 100644 --- a/ofproto/ofproto-dpif-ipfix.c +++ b/ofproto/ofproto-dpif-ipfix.c @@ -941,13 +941,12 @@ dpif_ipfix_get_bridge_exporter_tunnel_sampling(const struct dpif_ipfix *di) static void dpif_ipfix_clear(struct dpif_ipfix *di) OVS_REQUIRES(mutex) { - struct dpif_ipfix_flow_exporter_map_node *exp_node, *exp_next; + struct dpif_ipfix_flow_exporter_map_node *exp_node; struct dpif_ipfix_port *dip, *next; dpif_ipfix_bridge_exporter_clear(&di->bridge_exporter); - HMAP_FOR_EACH_SAFE (exp_node, exp_next, node, &di->flow_exporter_map) { - hmap_remove(&di->flow_exporter_map, &exp_node->node); + HMAP_FOR_EACH_POP (exp_node, node, &di->flow_exporter_map) { dpif_ipfix_flow_exporter_destroy(&exp_node->exporter); free(exp_node); } diff --git a/ofproto/ofproto-dpif-xlate.c b/ofproto/ofproto-dpif-xlate.c index 7a201bde1..ef770f286 100644 --- a/ofproto/ofproto-dpif-xlate.c +++ b/ofproto/ofproto-dpif-xlate.c @@ -4903,10 +4903,9 @@ count_skb_priorities(const struct xport *xport) static void clear_skb_priorities(struct xport *xport) { - struct skb_priority_to_dscp *pdscp, *next; + struct skb_priority_to_dscp *pdscp; - HMAP_FOR_EACH_SAFE (pdscp, next, hmap_node, &xport->skb_priorities) { - hmap_remove(&xport->skb_priorities, &pdscp->hmap_node); + HMAP_FOR_EACH_POP (pdscp, hmap_node, &xport->skb_priorities) { free(pdscp); } } diff --git a/ofproto/ofproto.c b/ofproto/ofproto.c index ff6affd5d..89e75d55f 100644 --- a/ofproto/ofproto.c +++ b/ofproto/ofproto.c @@ -1578,7 +1578,7 @@ ofproto_destroy(struct ofproto *p, bool del) OVS_EXCLUDED(ofproto_mutex) { struct ofport *ofport, *next_ofport; - struct ofport_usage *usage, *next_usage; + struct ofport_usage *usage; if (!p) { return; @@ -1596,8 +1596,7 @@ ofproto_destroy(struct ofproto *p, bool del) ofport_destroy(ofport, del); } - HMAP_FOR_EACH_SAFE (usage, next_usage, hmap_node, &p->ofport_usage) { - hmap_remove(&p->ofport_usage, &usage->hmap_node); + HMAP_FOR_EACH_POP (usage, hmap_node, &p->ofport_usage) { free(usage); } diff --git a/ofproto/pinsched.c b/ofproto/pinsched.c index 4b2dfd898..ee252f4f9 100644 --- a/ofproto/pinsched.c +++ b/ofproto/pinsched.c @@ -257,10 +257,9 @@ void pinsched_destroy(struct pinsched *ps) { if (ps) { - struct pinqueue *q, *next; + struct pinqueue *q; - HMAP_FOR_EACH_SAFE (q, next, node, &ps->queues) { - hmap_remove(&ps->queues, &q->node); + HMAP_FOR_EACH_POP (q, node, &ps->queues) { ofpbuf_list_delete(&q->packets); free(q); } diff --git a/ovn/controller/encaps.c b/ovn/controller/encaps.c index dfb11c081..149698e2c 100644 --- a/ovn/controller/encaps.c +++ b/ovn/controller/encaps.c @@ -280,9 +280,8 @@ encaps_run(struct controller_ctx *ctx, const struct ovsrec_bridge *br_int, } /* Delete any existing OVN tunnels that were not still around. */ - struct port_hash_node *hash_node, *next_hash_node; - HMAP_FOR_EACH_SAFE (hash_node, next_hash_node, node, &tc.tunnel_hmap) { - hmap_remove(&tc.tunnel_hmap, &hash_node->node); + struct port_hash_node *hash_node; + HMAP_FOR_EACH_POP (hash_node, node, &tc.tunnel_hmap) { bridge_delete_port(hash_node->bridge, hash_node->port); free(hash_node); } diff --git a/ovn/controller/lport.c b/ovn/controller/lport.c index e1ecf21fd..a7ae320bd 100644 --- a/ovn/controller/lport.c +++ b/ovn/controller/lport.c @@ -59,9 +59,8 @@ lport_index_destroy(struct lport_index *lports) /* Destroy all of the "struct lport"s. * * We don't have to remove the node from both indexes. */ - struct lport *port, *next; - HMAP_FOR_EACH_SAFE (port, next, name_node, &lports->by_name) { - hmap_remove(&lports->by_name, &port->name_node); + struct lport *port; + HMAP_FOR_EACH_POP (port, name_node, &lports->by_name) { free(port); } diff --git a/ovn/controller/ofctrl.c b/ovn/controller/ofctrl.c index b9e215323..f537bc008 100644 --- a/ovn/controller/ofctrl.c +++ b/ovn/controller/ofctrl.c @@ -567,9 +567,8 @@ ovn_flow_destroy(struct ovn_flow *f) static void ovn_flow_table_clear(struct hmap *flow_table) { - struct ovn_flow *f, *next; - HMAP_FOR_EACH_SAFE (f, next, hmap_node, flow_table) { - hmap_remove(flow_table, &f->hmap_node); + struct ovn_flow *f; + HMAP_FOR_EACH_POP (f, hmap_node, flow_table) { ovn_flow_destroy(f); } } diff --git a/ovn/controller/physical.c b/ovn/controller/physical.c index e10909d83..576c695ea 100644 --- a/ovn/controller/physical.c +++ b/ovn/controller/physical.c @@ -723,9 +723,7 @@ physical_run(struct controller_ctx *ctx, enum mf_field_id mff_ovn_geneve, ofpbuf_uninit(&ofpacts); simap_destroy(&localvif_to_ofport); - struct chassis_tunnel *tun_next; - HMAP_FOR_EACH_SAFE (tun, tun_next, hmap_node, &tunnels) { - hmap_remove(&tunnels, &tun->hmap_node); + HMAP_FOR_EACH_POP (tun, hmap_node, &tunnels) { free(tun); } hmap_destroy(&tunnels); diff --git a/ovn/controller/pinctrl.c b/ovn/controller/pinctrl.c index cbac50e54..289a99575 100644 --- a/ovn/controller/pinctrl.c +++ b/ovn/controller/pinctrl.c @@ -478,9 +478,8 @@ wait_put_arps(struct controller_ctx *ctx) static void flush_put_arps(void) { - struct put_arp *pa, *next; - HMAP_FOR_EACH_SAFE (pa, next, hmap_node, &put_arps) { - hmap_remove(&put_arps, &pa->hmap_node); + struct put_arp *pa; + HMAP_FOR_EACH_POP (pa, hmap_node, &put_arps) { free(pa); } } diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c index 05dd49836..f274ab46f 100644 --- a/ovn/lib/expr.c +++ b/ovn/lib/expr.c @@ -2511,10 +2511,9 @@ expr_to_matches(const struct expr *expr, void expr_matches_destroy(struct hmap *matches) { - struct expr_match *m, *n; + struct expr_match *m; - HMAP_FOR_EACH_SAFE (m, n, hmap_node, matches) { - hmap_remove(matches, &m->hmap_node); + HMAP_FOR_EACH_POP (m, hmap_node, matches) { free(m->conjunctions); free(m); } diff --git a/ovn/northd/ovn-northd.c b/ovn/northd/ovn-northd.c index e3436da44..d0319d59f 100644 --- a/ovn/northd/ovn-northd.c +++ b/ovn/northd/ovn-northd.c @@ -188,9 +188,8 @@ struct tnlid_node { static void destroy_tnlids(struct hmap *tnlids) { - struct tnlid_node *node, *next; - HMAP_FOR_EACH_SAFE (node, next, hmap_node, tnlids) { - hmap_remove(tnlids, &node->hmap_node); + struct tnlid_node *node; + HMAP_FOR_EACH_POP (node, hmap_node, tnlids) { free(node); } hmap_destroy(tnlids); @@ -2266,7 +2265,7 @@ ovnsb_db_run(struct northd_context *ctx) struct lport_hash_node { struct hmap_node node; const struct nbrec_logical_port *nb; - } *hash_node, *hash_node_next; + } *hash_node; hmap_init(&lports_hmap); @@ -2303,8 +2302,7 @@ ovnsb_db_run(struct northd_context *ctx) } } - HMAP_FOR_EACH_SAFE(hash_node, hash_node_next, node, &lports_hmap) { - hmap_remove(&lports_hmap, &hash_node->node); + HMAP_FOR_EACH_POP(hash_node, node, &lports_hmap) { free(hash_node); } hmap_destroy(&lports_hmap); diff --git a/ovsdb/monitor.c b/ovsdb/monitor.c index bbeb0e16a..e910e3fe7 100644 --- a/ovsdb/monitor.c +++ b/ovsdb/monitor.c @@ -183,10 +183,9 @@ ovsdb_monitor_json_cache_insert(struct ovsdb_monitor *dbmon, static void ovsdb_monitor_json_cache_flush(struct ovsdb_monitor *dbmon) { - struct ovsdb_monitor_json_cache_node *node, *next; + struct ovsdb_monitor_json_cache_node *node; - HMAP_FOR_EACH_SAFE(node, next, hmap_node, &dbmon->json_cache) { - hmap_remove(&dbmon->json_cache, &node->hmap_node); + HMAP_FOR_EACH_POP(node, hmap_node, &dbmon->json_cache) { json_destroy(node->json); free(node); } diff --git a/ovsdb/row.c b/ovsdb/row.c index 23b024313..572c10321 100644 --- a/ovsdb/row.c +++ b/ovsdb/row.c @@ -341,10 +341,9 @@ ovsdb_row_hash_init(struct ovsdb_row_hash *rh, void ovsdb_row_hash_destroy(struct ovsdb_row_hash *rh, bool destroy_rows) { - struct ovsdb_row_hash_node *node, *next; + struct ovsdb_row_hash_node *node; - HMAP_FOR_EACH_SAFE (node, next, hmap_node, &rh->rows) { - hmap_remove(&rh->rows, &node->hmap_node); + HMAP_FOR_EACH_POP (node, hmap_node, &rh->rows) { if (destroy_rows) { ovsdb_row_destroy(CONST_CAST(struct ovsdb_row *, node->row)); } diff --git a/tests/library.at b/tests/library.at index e1bac9216..8b1c443e8 100644 --- a/tests/library.at +++ b/tests/library.at @@ -17,7 +17,7 @@ AT_CLEANUP AT_SETUP([test hash map]) AT_KEYWORDS([hmap]) -AT_CHECK([ovstest test-hmap], [0], [......... +AT_CHECK([ovstest test-hmap], [0], [............ ]) AT_CLEANUP diff --git a/tests/test-hmap.c b/tests/test-hmap.c index f65d782fc..c63bd8022 100644 --- a/tests/test-hmap.c +++ b/tests/test-hmap.c @@ -272,6 +272,47 @@ test_hmap_for_each_safe(hash_func *hash) } } +/* Tests that HMAP_FOR_EACH_POP removes every element of a hmap. */ +static void +test_hmap_for_each_pop(hash_func *hash) +{ + enum { MAX_ELEMS = 10 }; + size_t n; + + for (n = 0; n <= MAX_ELEMS; n++) { + struct element elements[MAX_ELEMS]; + int values[MAX_ELEMS]; + struct hmap hmap; + struct element *e; + size_t n_remaining, i; + + make_hmap(&hmap, elements, values, n, hash); + + i = 0; + n_remaining = n; + HMAP_FOR_EACH_POP (e, node, &hmap) { + size_t j; + + assert(i < n); + + for (j = 0; ; j++) { + assert(j < n_remaining); + if (values[j] == e->value) { + values[j] = values[--n_remaining]; + break; + } + } + /* Trash the element memory (including the hmap node) */ + memset(e, 0, sizeof *e); + check_hmap(&hmap, values, n_remaining, hash); + i++; + } + assert(i == n); + + hmap_destroy(&hmap); + } +} + static void run_test(void (*function)(hash_func *)) { @@ -291,6 +332,7 @@ test_hmap_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) run_test(test_hmap_insert_delete); run_test(test_hmap_for_each_safe); run_test(test_hmap_reserve_shrink); + run_test(test_hmap_for_each_pop); printf("\n"); } -- 2.20.1