diff options
| author | Claudio Jeker <claudio@cvs.openbsd.org> | 2010-03-01 08:55:46 +0000 |
|---|---|---|
| committer | Claudio Jeker <claudio@cvs.openbsd.org> | 2010-03-01 08:55:46 +0000 |
| commit | d0be46d1190cdab7acf5d33af2884d249753d4b8 (patch) | |
| tree | 4bbb4b9195cb01cbc65756ce3fce4f9fdfc8be83 | |
| parent | 99e738cdf70e193f4edc136b45aec8faf74dae11 (diff) | |
Implement lsa_find_lsid(), a function that searches the LSDB for a LSA
specified by type, adv_rtr and an LSA to compare against. This is needed
to find either a free LS ID or the previously assigned LS ID of an AS-ext
LSA. "looks like you know what you're doing" stsp@
| -rw-r--r-- | usr.sbin/ospf6d/rde.h | 7 | ||||
| -rw-r--r-- | usr.sbin/ospf6d/rde_lsdb.c | 41 |
2 files changed, 45 insertions, 3 deletions
diff --git a/usr.sbin/ospf6d/rde.h b/usr.sbin/ospf6d/rde.h index c28beac5248..ada301c4281 100644 --- a/usr.sbin/ospf6d/rde.h +++ b/usr.sbin/ospf6d/rde.h @@ -1,4 +1,4 @@ -/* $OpenBSD: rde.h,v 1.19 2010/02/22 08:03:06 stsp Exp $ */ +/* $OpenBSD: rde.h,v 1.20 2010/03/01 08:55:45 claudio Exp $ */ /* * Copyright (c) 2004, 2005 Esben Norby <norby@openbsd.org> @@ -150,7 +150,10 @@ void lsa_age(struct vertex *); struct vertex *lsa_find(struct iface *, u_int16_t, u_int32_t, u_int32_t); struct vertex *lsa_find_rtr(struct area *, u_int32_t); struct vertex *lsa_find_rtr_frag(struct area *, u_int32_t, unsigned int); -struct vertex *lsa_find_tree(struct lsa_tree *, u_int16_t, u_int32_t, u_int32_t); +struct vertex *lsa_find_tree(struct lsa_tree *, u_int16_t, u_int32_t, + u_int32_t); +u_int32_t lsa_find_lsid(struct lsa_tree *, u_int16_t, u_int32_t, + int (*)(struct lsa *, struct lsa *), struct lsa *); u_int16_t lsa_num_links(struct vertex *); void lsa_snap(struct rde_nbr *, u_int32_t); void lsa_dump(struct lsa_tree *, int, pid_t); diff --git a/usr.sbin/ospf6d/rde_lsdb.c b/usr.sbin/ospf6d/rde_lsdb.c index 4da07dcb711..df85bed4a5d 100644 --- a/usr.sbin/ospf6d/rde_lsdb.c +++ b/usr.sbin/ospf6d/rde_lsdb.c @@ -1,4 +1,4 @@ -/* $OpenBSD: rde_lsdb.c,v 1.29 2010/02/26 09:59:44 claudio Exp $ */ +/* $OpenBSD: rde_lsdb.c,v 1.30 2010/03/01 08:55:45 claudio Exp $ */ /* * Copyright (c) 2004, 2005 Claudio Jeker <claudio@openbsd.org> @@ -623,6 +623,45 @@ lsa_find_rtr_frag(struct area *area, u_int32_t rtr_id, unsigned int n) return (v); } +u_int32_t +lsa_find_lsid(struct lsa_tree *tree, u_int16_t type, u_int32_t adv_rtr, + int (*cmp)(struct lsa *, struct lsa *), struct lsa *lsa) +{ +#define MIN(x, y) ((x) < (y) ? (x) : (y)) + struct vertex *v; + struct vertex key; + u_int32_t min, cur; + + key.ls_id = 0; + key.adv_rtr = ntohl(adv_rtr); + key.type = ntohs(type); + + cur = 0; + min = 0xffffffffU; + v = RB_NFIND(lsa_tree, tree, &key); + while (v) { + if (v->type != key.type || + v->adv_rtr != key.adv_rtr) { + /* no more interesting LSAs */ + min = MIN(min, cur + 1); + return (htonl(min)); + } + if (cmp(lsa, v->lsa) == 0) { + /* match, return this ls_id */ + return (htonl(v->ls_id)); + } + if (v->ls_id > cur + 1) + min = cur + 1; + cur = v->ls_id; + if (cur + 1 < cur) + fatalx("King Bula sez: somebody got to many LSA"); + v = RB_NEXT(lsa_tree, tree, v); + } + min = MIN(min, cur + 1); + return (htonl(min)); +#undef MIN +} + u_int16_t lsa_num_links(struct vertex *v) { |