diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/Makefile.am | 4 | ||||
| -rw-r--r-- | lib/command.c | 1 | ||||
| -rw-r--r-- | lib/grammar_sandbox.c | 7 | ||||
| -rw-r--r-- | lib/json.c | 2 | ||||
| -rw-r--r-- | lib/libfrr.c | 4 | ||||
| -rw-r--r-- | lib/log.c | 82 | ||||
| -rw-r--r-- | lib/log.h | 9 | ||||
| -rw-r--r-- | lib/mpls.h | 4 | ||||
| -rw-r--r-- | lib/ns.c | 6 | ||||
| -rw-r--r-- | lib/openbsd-tree.c | 644 | ||||
| -rw-r--r-- | lib/openbsd-tree.h | 642 | ||||
| -rw-r--r-- | lib/routemap.c | 2 | ||||
| -rw-r--r-- | lib/termtable.c | 487 | ||||
| -rw-r--r-- | lib/termtable.h | 293 | ||||
| -rw-r--r-- | lib/vrf.c | 40 | ||||
| -rw-r--r-- | lib/vty.c | 31 | ||||
| -rw-r--r-- | lib/vty.h | 3 | ||||
| -rw-r--r-- | lib/zebra.h | 2 |
18 files changed, 1727 insertions, 536 deletions
diff --git a/lib/Makefile.am b/lib/Makefile.am index f1356d2be4..e1b84587da 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -18,7 +18,7 @@ libfrr_la_LDFLAGS = -version-info 0:0:0 libfrr_la_SOURCES = \ network.c pid_output.c getopt.c getopt1.c \ - checksum.c vector.c linklist.c vty.c \ + checksum.c vector.c linklist.c vty.c openbsd-tree.c \ graph.c command_parse.y command_lex.l command_match.c \ command_graph.c \ command.c \ @@ -40,6 +40,7 @@ libfrr_la_SOURCES = \ module.c \ hook.c \ frr_pthread.c \ + termtable.c \ # end BUILT_SOURCES = route_types.h gitversion.h command_parse.h command_lex.h @@ -84,6 +85,7 @@ pkginclude_HEADERS = \ sha256.h \ frr_pthread.h \ vrf_int.h \ + termtable.h \ # end noinst_HEADERS = \ diff --git a/lib/command.c b/lib/command.c index 8a4250bce5..5853710999 100644 --- a/lib/command.c +++ b/lib/command.c @@ -534,7 +534,6 @@ cmd_try_do_shortcut (enum node_type node, char* first_word) { node != AUTH_NODE && node != VIEW_NODE && node != AUTH_ENABLE_NODE && - node != ENABLE_NODE && 0 == strcmp( "do", first_word ) ) return 1; return 0; diff --git a/lib/grammar_sandbox.c b/lib/grammar_sandbox.c index cfc3fb7982..f4a8df26c0 100644 --- a/lib/grammar_sandbox.c +++ b/lib/grammar_sandbox.c @@ -503,9 +503,8 @@ struct message tokennames[] = { item(JOIN_TKN), item(START_TKN), // first token in line item(END_TKN), // last token in line - { 0, NULL } + { 0 } }; -size_t tokennames_max = array_size(tokennames); /** * Pretty-prints a graph, assuming it is a tree. @@ -522,7 +521,7 @@ pretty_print_graph (struct vty *vty, struct graph_node *start, int level, struct cmd_token *tok = start->data; snprintf(tokennum, sizeof(tokennum), "%d?", tok->type); - vty_out(vty, "%s", LOOKUP_DEF(tokennames, tok->type, tokennum)); + vty_out(vty, "%s", lookup_msg(tokennames, tok->type, NULL)); if (tok->text) vty_out(vty, ":\"%s\"", tok->text); if (tok->varname) @@ -591,7 +590,7 @@ pretty_print_dot (FILE *ofd, unsigned opts, struct graph_node *start, snprintf(tokennum, sizeof(tokennum), "%d?", tok->type); fprintf(ofd, " n%p [ shape=box, label=<", start); - fprintf(ofd, "<b>%s</b>", LOOKUP_DEF(tokennames, tok->type, tokennum)); + fprintf(ofd, "<b>%s</b>", lookup_msg(tokennames, tok->type, NULL)); if (tok->attr == CMD_ATTR_DEPRECATED) fprintf(ofd, " (d)"); else if (tok->attr == CMD_ATTR_HIDDEN) diff --git a/lib/json.c b/lib/json.c index 186efc9f48..5b7c3e9ffa 100644 --- a/lib/json.c +++ b/lib/json.c @@ -34,7 +34,7 @@ use_json (const int argc, struct cmd_token *argv[]) if (argc == 0) return 0; - if (argv[argc-1]->arg && strcmp(argv[argc-1]->arg, "json") == 0) + if (argv[argc-1]->arg && strmatch (argv[argc-1]->text, "json")) return 1; return 0; diff --git a/lib/libfrr.c b/lib/libfrr.c index ff4160a243..132f7d4d2c 100644 --- a/lib/libfrr.c +++ b/lib/libfrr.c @@ -36,8 +36,8 @@ const char frr_sysconfdir[] = SYSCONFDIR; const char frr_vtydir[] = DAEMON_VTY_DIR; const char frr_moduledir[] = MODULE_PATH; -char frr_protoname[] = "NONE"; -char frr_protonameinst[] = "NONE"; +char frr_protoname[256] = "NONE"; +char frr_protonameinst[256] = "NONE"; char config_default[256]; static char pidfile_default[256]; @@ -85,8 +85,33 @@ static void write_wrapper (int fd, const void *buf, size_t count) return; } -/* For time string format. */ +/** + * Looks up a message in a message list by key. + * + * If the message is not found, returns the provided error message. + * + * Terminates when it hits a struct message that's all zeros. + * + * @param mz the message list + * @param kz the message key + * @param nf the message to return if not found + * @return the message + */ +const char * +lookup_msg(const struct message *mz, int kz, const char *nf) +{ + static struct message nt = { 0 }; + const char *rz = nf ? nf : "(no message found)"; + const struct message *pnt; + for (pnt = mz; memcmp(pnt, &nt, sizeof(struct message)); pnt++) + if (pnt->key == kz) { + rz = pnt->str ? pnt->str : rz; + break; + } + return rz; +} +/* For time string format. */ size_t quagga_timestamp(int timestamp_precision, char *buf, size_t buflen) { @@ -851,61 +876,6 @@ zlog_rotate (void) return 1; } -/* Message lookup function. */ -const char * -lookup (const struct message *mes, int key) -{ - const struct message *pnt; - - for (pnt = mes; pnt->key != 0; pnt++) - if (pnt->key == key) - return pnt->str; - - return ""; -} - -/* Older/faster version of message lookup function, but requires caller to pass - * in the array size (instead of relying on a 0 key to terminate the search). - * - * The return value is the message string if found, or the 'none' pointer - * provided otherwise. - */ -const char * -mes_lookup (const struct message *meslist, int max, int index, - const char *none, const char *mesname) -{ - int pos = index - meslist[0].key; - - /* first check for best case: index is in range and matches the key - * value in that slot. - * NB: key numbering might be offset from 0. E.g. protocol constants - * often start at 1. - */ - if ((pos >= 0) && (pos < max) - && (meslist[pos].key == index)) - return meslist[pos].str; - - /* fall back to linear search */ - { - int i; - - for (i = 0; i < max; i++, meslist++) - { - if (meslist->key == index) - { - const char *str = (meslist->str ? meslist->str : none); - - zlog_debug ("message index %d [%s] found in %s at position %d (max is %d)", - index, str, mesname, i, max); - return str; - } - } - } - zlog_err("message index %d not found in %s (max is %d)", index, mesname, max); - assert (none); - return none; -} - /* Wrapper around strerror to handle case where it returns NULL. */ const char * safe_strerror(int errnum) @@ -99,14 +99,7 @@ extern int zlog_reset_file (void); /* Rotate log. */ extern int zlog_rotate (void); -/* For hackey message lookup and check */ -#define LOOKUP_DEF(x, y, def) mes_lookup(x, x ## _max, y, def, #x) -#define LOOKUP(x, y) LOOKUP_DEF(x, y, "(no item found)") - -extern const char *lookup (const struct message *, int); -extern const char *mes_lookup (const struct message *meslist, - int max, int index, - const char *no_item, const char *mesname); +const char *lookup_msg (const struct message *mz, int kz, const char *nf); /* Safe version of strerror -- never returns NULL. */ extern const char *safe_strerror(int errnum); diff --git a/lib/mpls.h b/lib/mpls.h index 6cf0142755..c963e55087 100644 --- a/lib/mpls.h +++ b/lib/mpls.h @@ -40,6 +40,10 @@ #define MPLS_MIN_UNRESERVED_LABEL 16 #define MPLS_MAX_UNRESERVED_LABEL 1048575 +/* Default min and max SRGB label range */ +#define MPLS_DEFAULT_MIN_SRGB_LABEL 16000 +#define MPLS_DEFAULT_MAX_SRGB_LABEL 23999 + #define IS_MPLS_RESERVED_LABEL(label) \ (label >= MPLS_MIN_RESERVED_LABEL && label <= MPLS_MAX_RESERVED_LABEL) @@ -39,7 +39,7 @@ DEFINE_MTYPE_STATIC(LIB, NS, "Logical-Router") DEFINE_MTYPE_STATIC(LIB, NS_NAME, "Logical-Router Name") -static __inline int ns_compare (struct ns *, struct ns *); +static __inline int ns_compare (const struct ns *, const struct ns *); static struct ns *ns_lookup (ns_id_t); RB_GENERATE (ns_head, ns, entry, ns_compare) @@ -108,7 +108,7 @@ static int ns_enable (struct ns *ns); static void ns_disable (struct ns *ns); static __inline int -ns_compare(struct ns *a, struct ns *b) +ns_compare(const struct ns *a, const struct ns *b) { return (a->ns_id - b->ns_id); } @@ -453,7 +453,7 @@ ns_terminate (void) { struct ns *ns; - while ((ns = RB_ROOT (&ns_tree)) != NULL) + while ((ns = RB_ROOT (ns_head, &ns_tree)) != NULL) ns_delete (ns); } diff --git a/lib/openbsd-tree.c b/lib/openbsd-tree.c new file mode 100644 index 0000000000..7e753554c9 --- /dev/null +++ b/lib/openbsd-tree.c @@ -0,0 +1,644 @@ +/* $OpenBSD: subr_tree.c,v 1.9 2017/06/08 03:30:52 dlg Exp $ */ + +/* + * Copyright 2002 Niels Provos <provos@citi.umich.edu> + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/* + * Copyright (c) 2016 David Gwynne <dlg@openbsd.org> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <stdlib.h> + +#include <lib/openbsd-tree.h> + +static inline struct rb_entry * +rb_n2e(const struct rb_type *t, void *node) +{ + unsigned long addr = (unsigned long)node; + + return ((struct rb_entry *)(addr + t->t_offset)); +} + +static inline void * +rb_e2n(const struct rb_type *t, struct rb_entry *rbe) +{ + unsigned long addr = (unsigned long)rbe; + + return ((void *)(addr - t->t_offset)); +} + +#define RBE_LEFT(_rbe) (_rbe)->rbt_left +#define RBE_RIGHT(_rbe) (_rbe)->rbt_right +#define RBE_PARENT(_rbe) (_rbe)->rbt_parent +#define RBE_COLOR(_rbe) (_rbe)->rbt_color + +#define RBH_ROOT(_rbt) (_rbt)->rbt_root + +static inline void +rbe_set(struct rb_entry *rbe, struct rb_entry *parent) +{ + RBE_PARENT(rbe) = parent; + RBE_LEFT(rbe) = RBE_RIGHT(rbe) = NULL; + RBE_COLOR(rbe) = RB_RED; +} + +static inline void +rbe_set_blackred(struct rb_entry *black, struct rb_entry *red) +{ + RBE_COLOR(black) = RB_BLACK; + RBE_COLOR(red) = RB_RED; +} + +static inline void +rbe_augment(const struct rb_type *t, struct rb_entry *rbe) +{ + (*t->t_augment)(rb_e2n(t, rbe)); +} + +static inline void +rbe_if_augment(const struct rb_type *t, struct rb_entry *rbe) +{ + if (t->t_augment != NULL) + rbe_augment(t, rbe); +} + +static inline void +rbe_rotate_left(const struct rb_type *t, struct rbt_tree *rbt, + struct rb_entry *rbe) +{ + struct rb_entry *parent; + struct rb_entry *tmp; + + tmp = RBE_RIGHT(rbe); + RBE_RIGHT(rbe) = RBE_LEFT(tmp); + if (RBE_RIGHT(rbe) != NULL) + RBE_PARENT(RBE_LEFT(tmp)) = rbe; + + parent = RBE_PARENT(rbe); + RBE_PARENT(tmp) = parent; + if (parent != NULL) { + if (rbe == RBE_LEFT(parent)) + RBE_LEFT(parent) = tmp; + else + RBE_RIGHT(parent) = tmp; + } else + RBH_ROOT(rbt) = tmp; + + RBE_LEFT(tmp) = rbe; + RBE_PARENT(rbe) = tmp; + + if (t->t_augment != NULL) { + rbe_augment(t, rbe); + rbe_augment(t, tmp); + parent = RBE_PARENT(tmp); + if (parent != NULL) + rbe_augment(t, parent); + } +} + +static inline void +rbe_rotate_right(const struct rb_type *t, struct rbt_tree *rbt, + struct rb_entry *rbe) +{ + struct rb_entry *parent; + struct rb_entry *tmp; + + tmp = RBE_LEFT(rbe); + RBE_LEFT(rbe) = RBE_RIGHT(tmp); + if (RBE_LEFT(rbe) != NULL) + RBE_PARENT(RBE_RIGHT(tmp)) = rbe; + + parent = RBE_PARENT(rbe); + RBE_PARENT(tmp) = parent; + if (parent != NULL) { + if (rbe == RBE_LEFT(parent)) + RBE_LEFT(parent) = tmp; + else + RBE_RIGHT(parent) = tmp; + } else + RBH_ROOT(rbt) = tmp; + + RBE_RIGHT(tmp) = rbe; + RBE_PARENT(rbe) = tmp; + + if (t->t_augment != NULL) { + rbe_augment(t, rbe); + rbe_augment(t, tmp); + parent = RBE_PARENT(tmp); + if (parent != NULL) + rbe_augment(t, parent); + } +} + +static inline void +rbe_insert_color(const struct rb_type *t, struct rbt_tree *rbt, + struct rb_entry *rbe) +{ + struct rb_entry *parent, *gparent, *tmp; + + while ((parent = RBE_PARENT(rbe)) != NULL && + RBE_COLOR(parent) == RB_RED) { + gparent = RBE_PARENT(parent); + + if (parent == RBE_LEFT(gparent)) { + tmp = RBE_RIGHT(gparent); + if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) { + RBE_COLOR(tmp) = RB_BLACK; + rbe_set_blackred(parent, gparent); + rbe = gparent; + continue; + } + + if (RBE_RIGHT(parent) == rbe) { + rbe_rotate_left(t, rbt, parent); + tmp = parent; + parent = rbe; + rbe = tmp; + } + + rbe_set_blackred(parent, gparent); + rbe_rotate_right(t, rbt, gparent); + } else { + tmp = RBE_LEFT(gparent); + if (tmp != NULL && RBE_COLOR(tmp) == RB_RED) { + RBE_COLOR(tmp) = RB_BLACK; + rbe_set_blackred(parent, gparent); + rbe = gparent; + continue; + } + + if (RBE_LEFT(parent) == rbe) { + rbe_rotate_right(t, rbt, parent); + tmp = parent; + parent = rbe; + rbe = tmp; + } + + rbe_set_blackred(parent, gparent); + rbe_rotate_left(t, rbt, gparent); + } + } + + RBE_COLOR(RBH_ROOT(rbt)) = RB_BLACK; +} + +static inline void +rbe_remove_color(const struct rb_type *t, struct rbt_tree *rbt, + struct rb_entry *parent, struct rb_entry *rbe) +{ + struct rb_entry *tmp; + + /* Silence clang possible NULL deference warning. */ + if (parent == NULL) + return; + + while ((rbe == NULL || RBE_COLOR(rbe) == RB_BLACK) && + rbe != RBH_ROOT(rbt)) { + if (RBE_LEFT(parent) == rbe) { + tmp = RBE_RIGHT(parent); + if (RBE_COLOR(tmp) == RB_RED) { + rbe_set_blackred(tmp, parent); + rbe_rotate_left(t, rbt, parent); + tmp = RBE_RIGHT(parent); + } + if ((RBE_LEFT(tmp) == NULL || + RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) && + (RBE_RIGHT(tmp) == NULL || + RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) { + RBE_COLOR(tmp) = RB_RED; + rbe = parent; + parent = RBE_PARENT(rbe); + } else { + if (RBE_RIGHT(tmp) == NULL || + RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK) { + struct rb_entry *oleft; + + oleft = RBE_LEFT(tmp); + if (oleft != NULL) + RBE_COLOR(oleft) = RB_BLACK; + + RBE_COLOR(tmp) = RB_RED; + rbe_rotate_right(t, rbt, tmp); + tmp = RBE_RIGHT(parent); + } + + RBE_COLOR(tmp) = RBE_COLOR(parent); + RBE_COLOR(parent) = RB_BLACK; + if (RBE_RIGHT(tmp)) + RBE_COLOR(RBE_RIGHT(tmp)) = RB_BLACK; + + rbe_rotate_left(t, rbt, parent); + rbe = RBH_ROOT(rbt); + break; + } + } else { + tmp = RBE_LEFT(parent); + if (RBE_COLOR(tmp) == RB_RED) { + rbe_set_blackred(tmp, parent); + rbe_rotate_right(t, rbt, parent); + tmp = RBE_LEFT(parent); + } + + if ((RBE_LEFT(tmp) == NULL || + RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) && + (RBE_RIGHT(tmp) == NULL || + RBE_COLOR(RBE_RIGHT(tmp)) == RB_BLACK)) { + RBE_COLOR(tmp) = RB_RED; + rbe = parent; + parent = RBE_PARENT(rbe); + } else { + if (RBE_LEFT(tmp) == NULL || + RBE_COLOR(RBE_LEFT(tmp)) == RB_BLACK) { + struct rb_entry *oright; + + oright = RBE_RIGHT(tmp); + if (oright != NULL) + RBE_COLOR(oright) = RB_BLACK; + + RBE_COLOR(tmp) = RB_RED; + rbe_rotate_left(t, rbt, tmp); + tmp = RBE_LEFT(parent); + } + + RBE_COLOR(tmp) = RBE_COLOR(parent); + RBE_COLOR(parent) = RB_BLACK; + if (RBE_LEFT(tmp) != NULL) + RBE_COLOR(RBE_LEFT(tmp)) = RB_BLACK; + + rbe_rotate_right(t, rbt, parent); + rbe = RBH_ROOT(rbt); + break; + } + } + } + + if (rbe != NULL) + RBE_COLOR(rbe) = RB_BLACK; +} + +static inline struct rb_entry * +rbe_remove(const struct rb_type *t, struct rbt_tree *rbt, struct rb_entry *rbe) +{ + struct rb_entry *child, *parent, *old = rbe; + unsigned int color; + + if (RBE_LEFT(rbe) == NULL) + child = RBE_RIGHT(rbe); + else if (RBE_RIGHT(rbe) == NULL) + child = RBE_LEFT(rbe); + else { + struct rb_entry *tmp; + + rbe = RBE_RIGHT(rbe); + while ((tmp = RBE_LEFT(rbe)) != NULL) + rbe = tmp; + + child = RBE_RIGHT(rbe); + parent = RBE_PARENT(rbe); + color = RBE_COLOR(rbe); + if (child != NULL) + RBE_PARENT(child) = parent; + if (parent != NULL) { + if (RBE_LEFT(parent) == rbe) + RBE_LEFT(parent) = child; + else + RBE_RIGHT(parent) = child; + + rbe_if_augment(t, parent); + } else + RBH_ROOT(rbt) = child; + if (RBE_PARENT(rbe) == old) + parent = rbe; + *rbe = *old; + + tmp = RBE_PARENT(old); + if (tmp != NULL) { + if (RBE_LEFT(tmp) == old) + RBE_LEFT(tmp) = rbe; + else + RBE_RIGHT(tmp) = rbe; + + rbe_if_augment(t, parent); + } else + RBH_ROOT(rbt) = rbe; + + RBE_PARENT(RBE_LEFT(old)) = rbe; + if (RBE_RIGHT(old)) + RBE_PARENT(RBE_RIGHT(old)) = rbe; + + if (t->t_augment != NULL && parent != NULL) { + tmp = parent; + do { + rbe_augment(t, tmp); + tmp = RBE_PARENT(tmp); + } while (tmp != NULL); + } + + goto color; + } + + parent = RBE_PARENT(rbe); + color = RBE_COLOR(rbe); + + if (child != NULL) + RBE_PARENT(child) = parent; + if (parent != NULL) { + if (RBE_LEFT(parent) == rbe) + RBE_LEFT(parent) = child; + else + RBE_RIGHT(parent) = child; + + rbe_if_augment(t, parent); + } else + RBH_ROOT(rbt) = child; +color: + if (color == RB_BLACK) + rbe_remove_color(t, rbt, parent, child); + + return (old); +} + +void * +_rb_remove(const struct rb_type *t, struct rbt_tree *rbt, void *elm) +{ + struct rb_entry *rbe = rb_n2e(t, elm); + struct rb_entry *old; + + old = rbe_remove(t, rbt, rbe); + + return (old == NULL ? NULL : rb_e2n(t, old)); +} + +void * +_rb_insert(const struct rb_type *t, struct rbt_tree *rbt, void *elm) +{ + struct rb_entry *rbe = rb_n2e(t, elm); + struct rb_entry *tmp; + struct rb_entry *parent = NULL; + void *node; + int comp = 0; + + tmp = RBH_ROOT(rbt); + while (tmp != NULL) { + parent = tmp; + + node = rb_e2n(t, tmp); + comp = (*t->t_compare)(elm, node); + if (comp < 0) + tmp = RBE_LEFT(tmp); + else if (comp > 0) + tmp = RBE_RIGHT(tmp); + else + return (node); + } + + rbe_set(rbe, parent); + + if (parent != NULL) { + if (comp < 0) + RBE_LEFT(parent) = rbe; + else + RBE_RIGHT(parent) = rbe; + + rbe_if_augment(t, parent); + } else + RBH_ROOT(rbt) = rbe; + + rbe_insert_color(t, rbt, rbe); + + return (NULL); +} + +/* Finds the node with the same key as elm */ +void * +_rb_find(const struct rb_type *t, struct rbt_tree *rbt, const void *key) +{ + struct rb_entry *tmp = RBH_ROOT(rbt); + void *node; + int comp; + + while (tmp != NULL) { + node = rb_e2n(t, tmp); + comp = (*t->t_compare)(key, node); + if (comp < 0) + tmp = RBE_LEFT(tmp); + else if (comp > 0) + tmp = RBE_RIGHT(tmp); + else + return (node); + } + + return (NULL); +} + +/* Finds the first node greater than or equal to the search key */ +void * +_rb_nfind(const struct rb_type *t, struct rbt_tree *rbt, const void *key) +{ + struct rb_entry *tmp = RBH_ROOT(rbt); + void *node; + void *res = NULL; + int comp; + + while (tmp != NULL) { + node = rb_e2n(t, tmp); + comp = (*t->t_compare)(key, node); + if (comp < 0) { + res = node; + tmp = RBE_LEFT(tmp); + } else if (comp > 0) + tmp = RBE_RIGHT(tmp); + else + return (node); + } + + return (res); +} + +void * +_rb_next(const struct rb_type *t, void *elm) +{ + struct rb_entry *rbe = rb_n2e(t, elm); + + if (RBE_RIGHT(rbe) != NULL) { + rbe = RBE_RIGHT(rbe); + while (RBE_LEFT(rbe) != NULL) + rbe = RBE_LEFT(rbe); + } else { + if (RBE_PARENT(rbe) && + (rbe == RBE_LEFT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + else { + while (RBE_PARENT(rbe) && + (rbe == RBE_RIGHT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + rbe = RBE_PARENT(rbe); + } + } + + return (rbe == NULL ? NULL : rb_e2n(t, rbe)); +} + +void * +_rb_prev(const struct rb_type *t, void *elm) +{ + struct rb_entry *rbe = rb_n2e(t, elm); + + if (RBE_LEFT(rbe)) { + rbe = RBE_LEFT(rbe); + while (RBE_RIGHT(rbe)) + rbe = RBE_RIGHT(rbe); + } else { + if (RBE_PARENT(rbe) && + (rbe == RBE_RIGHT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + else { + while (RBE_PARENT(rbe) && + (rbe == RBE_LEFT(RBE_PARENT(rbe)))) + rbe = RBE_PARENT(rbe); + rbe = RBE_PARENT(rbe); + } + } + + return (rbe == NULL ? NULL : rb_e2n(t, rbe)); +} + +void * +_rb_root(const struct rb_type *t, struct rbt_tree *rbt) +{ + struct rb_entry *rbe = RBH_ROOT(rbt); + + return (rbe == NULL ? rbe : rb_e2n(t, rbe)); +} + +void * +_rb_min(const struct rb_type *t, struct rbt_tree *rbt) +{ + struct rb_entry *rbe = RBH_ROOT(rbt); + struct rb_entry *parent = NULL; + + while (rbe != NULL) { + parent = rbe; + rbe = RBE_LEFT(rbe); + } + + return (parent == NULL ? NULL : rb_e2n(t, parent)); +} + +void * +_rb_max(const struct rb_type *t, struct rbt_tree *rbt) +{ + struct rb_entry *rbe = RBH_ROOT(rbt); + struct rb_entry *parent = NULL; + + while (rbe != NULL) { + parent = rbe; + rbe = RBE_RIGHT(rbe); + } + + return (parent == NULL ? NULL : rb_e2n(t, parent)); +} + +void * +_rb_left(const struct rb_type *t, void *node) +{ + struct rb_entry *rbe = rb_n2e(t, node); + rbe = RBE_LEFT(rbe); + return (rbe == NULL ? NULL : rb_e2n(t, rbe)); +} + +void * +_rb_right(const struct rb_type *t, void *node) +{ + struct rb_entry *rbe = rb_n2e(t, node); + rbe = RBE_RIGHT(rbe); + return (rbe == NULL ? NULL : rb_e2n(t, rbe)); +} + +void * +_rb_parent(const struct rb_type *t, void *node) +{ + struct rb_entry *rbe = rb_n2e(t, node); + rbe = RBE_PARENT(rbe); + return (rbe == NULL ? NULL : rb_e2n(t, rbe)); +} + +void +_rb_set_left(const struct rb_type *t, void *node, void *left) +{ + struct rb_entry *rbe = rb_n2e(t, node); + struct rb_entry *rbl = (left == NULL) ? NULL : rb_n2e(t, left); + + RBE_LEFT(rbe) = rbl; +} + +void +_rb_set_right(const struct rb_type *t, void *node, void *right) +{ + struct rb_entry *rbe = rb_n2e(t, node); + struct rb_entry *rbr = (right == NULL) ? NULL : rb_n2e(t, right); + + RBE_RIGHT(rbe) = rbr; +} + +void +_rb_set_parent(const struct rb_type *t, void *node, void *parent) +{ + struct rb_entry *rbe = rb_n2e(t, node); + struct rb_entry *rbp = (parent == NULL) ? NULL : rb_n2e(t, parent); + + RBE_PARENT(rbe) = rbp; +} + +void +_rb_poison(const struct rb_type *t, void *node, unsigned long poison) +{ + struct rb_entry *rbe = rb_n2e(t, node); + + RBE_PARENT(rbe) = RBE_LEFT(rbe) = RBE_RIGHT(rbe) = + (struct rb_entry *)poison; +} + +int +_rb_check(const struct rb_type *t, void *node, unsigned long poison) +{ + struct rb_entry *rbe = rb_n2e(t, node); + + return ((unsigned long)RBE_PARENT(rbe) == poison && + (unsigned long)RBE_LEFT(rbe) == poison && + (unsigned long)RBE_RIGHT(rbe) == poison); +} diff --git a/lib/openbsd-tree.h b/lib/openbsd-tree.h index e6502b1e74..22cb9252f5 100644 --- a/lib/openbsd-tree.h +++ b/lib/openbsd-tree.h @@ -287,462 +287,262 @@ void name##_SPLAY_MINMAX(struct name *head, int __comp) \ (x) != NULL; \ (x) = SPLAY_NEXT(name, head, x)) -/* Macros that define a red-black tree */ -#define RB_HEAD(name, type) \ -struct name { \ - struct type *rbh_root; /* root of the tree */ \ -} - -#define RB_INITIALIZER(root) \ - { NULL } - -#define RB_INIT(root) do { \ - (root)->rbh_root = NULL; \ -} while (0) +/* + * Copyright (c) 2016 David Gwynne <dlg@openbsd.org> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ #define RB_BLACK 0 #define RB_RED 1 -#define RB_ENTRY(type) \ -struct { \ - struct type *rbe_left; /* left element */ \ - struct type *rbe_right; /* right element */ \ - struct type *rbe_parent; /* parent element */ \ - int rbe_color; /* node color */ \ -} - -#define RB_LEFT(elm, field) (elm)->field.rbe_left -#define RB_RIGHT(elm, field) (elm)->field.rbe_right -#define RB_PARENT(elm, field) (elm)->field.rbe_parent -#define RB_COLOR(elm, field) (elm)->field.rbe_color -#define RB_ROOT(head) (head)->rbh_root -#define RB_EMPTY(head) (RB_ROOT(head) == NULL) - -#define RB_SET(elm, parent, field) do { \ - RB_PARENT(elm, field) = parent; \ - RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ - RB_COLOR(elm, field) = RB_RED; \ -} while (0) -#define RB_SET_BLACKRED(black, red, field) do { \ - RB_COLOR(black, field) = RB_BLACK; \ - RB_COLOR(red, field) = RB_RED; \ -} while (0) +struct rb_type { + int (*t_compare)(const void *, const void *); + void (*t_augment)(void *); + unsigned int t_offset; /* offset of rb_entry in type */ +}; + +struct rbt_tree { + struct rb_entry *rbt_root; +}; + +struct rb_entry { + struct rb_entry *rbt_parent; + struct rb_entry *rbt_left; + struct rb_entry *rbt_right; + unsigned int rbt_color; +}; + +#define RB_HEAD(_name, _type) \ +struct _name { \ + struct rbt_tree rbh_root; \ +} -#ifndef RB_AUGMENT -#define RB_AUGMENT(x) do {} while (0) -#endif +#define RB_ENTRY(_type) struct rb_entry -#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ - (tmp) = RB_RIGHT(elm, field); \ - if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ - RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ - } \ - RB_AUGMENT(elm); \ - if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ - if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ - RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ - else \ - RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ - } else \ - (head)->rbh_root = (tmp); \ - RB_LEFT(tmp, field) = (elm); \ - RB_PARENT(elm, field) = (tmp); \ - RB_AUGMENT(tmp); \ - if ((RB_PARENT(tmp, field))) \ - RB_AUGMENT(RB_PARENT(tmp, field)); \ -} while (0) +static inline void +_rb_init(struct rbt_tree *rbt) +{ + rbt->rbt_root = NULL; +} -#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ - (tmp) = RB_LEFT(elm, field); \ - if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ - RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ - } \ - RB_AUGMENT(elm); \ - if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ - if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ - RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ - else \ - RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ - } else \ - (head)->rbh_root = (tmp); \ - RB_RIGHT(tmp, field) = (elm); \ - RB_PARENT(elm, field) = (tmp); \ - RB_AUGMENT(tmp); \ - if ((RB_PARENT(tmp, field))) \ - RB_AUGMENT(RB_PARENT(tmp, field)); \ -} while (0) +static inline int +_rb_empty(struct rbt_tree *rbt) +{ + return (rbt->rbt_root == NULL); +} -/* Generates prototypes and inline functions */ -#define RB_PROTOTYPE(name, type, field, cmp) \ - RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) -#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ - RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) -#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ -attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ -attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ -attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ -attr struct type *name##_RB_INSERT(struct name *, struct type *); \ -attr struct type *name##_RB_FIND(struct name *, struct type *); \ -attr struct type *name##_RB_NFIND(struct name *, struct type *); \ -attr struct type *name##_RB_NEXT(struct type *); \ -attr struct type *name##_RB_PREV(struct type *); \ -attr struct type *name##_RB_MINMAX(struct name *, int); \ +void *_rb_insert(const struct rb_type *, struct rbt_tree *, void *); +void *_rb_remove(const struct rb_type *, struct rbt_tree *, void *); +void *_rb_find(const struct rb_type *, struct rbt_tree *, const void *); +void *_rb_nfind(const struct rb_type *, struct rbt_tree *, const void *); +void *_rb_root(const struct rb_type *, struct rbt_tree *); +void *_rb_min(const struct rb_type *, struct rbt_tree *); +void *_rb_max(const struct rb_type *, struct rbt_tree *); +void *_rb_next(const struct rb_type *, void *); +void *_rb_prev(const struct rb_type *, void *); +void *_rb_left(const struct rb_type *, void *); +void *_rb_right(const struct rb_type *, void *); +void *_rb_parent(const struct rb_type *, void *); +void _rb_set_left(const struct rb_type *, void *, void *); +void _rb_set_right(const struct rb_type *, void *, void *); +void _rb_set_parent(const struct rb_type *, void *, void *); +void _rb_poison(const struct rb_type *, void *, unsigned long); +int _rb_check(const struct rb_type *, void *, unsigned long); + +#define RB_INITIALIZER(_head) { { NULL } } + +#define RB_PROTOTYPE(_name, _type, _field, _cmp) \ +extern const struct rb_type *const _name##_RB_TYPE; \ \ - -/* Main rb operation. - * Moves node close to the key of elm to top - */ -#define RB_GENERATE(name, type, field, cmp) \ - RB_GENERATE_INTERNAL(name, type, field, cmp,) -#define RB_GENERATE_STATIC(name, type, field, cmp) \ - RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) -#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ -attr void \ -name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ +__attribute__((__unused__)) static inline void \ +_name##_RB_INIT(struct _name *head) \ { \ - struct type *parent, *gparent, *tmp; \ - while ((parent = RB_PARENT(elm, field)) && \ - RB_COLOR(parent, field) == RB_RED) { \ - gparent = RB_PARENT(parent, field); \ - if (parent == RB_LEFT(gparent, field)) { \ - tmp = RB_RIGHT(gparent, field); \ - if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ - RB_COLOR(tmp, field) = RB_BLACK; \ - RB_SET_BLACKRED(parent, gparent, field);\ - elm = gparent; \ - continue; \ - } \ - if (RB_RIGHT(parent, field) == elm) { \ - RB_ROTATE_LEFT(head, parent, tmp, field);\ - tmp = parent; \ - parent = elm; \ - elm = tmp; \ - } \ - RB_SET_BLACKRED(parent, gparent, field); \ - RB_ROTATE_RIGHT(head, gparent, tmp, field); \ - } else { \ - tmp = RB_LEFT(gparent, field); \ - if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ - RB_COLOR(tmp, field) = RB_BLACK; \ - RB_SET_BLACKRED(parent, gparent, field);\ - elm = gparent; \ - continue; \ - } \ - if (RB_LEFT(parent, field) == elm) { \ - RB_ROTATE_RIGHT(head, parent, tmp, field);\ - tmp = parent; \ - parent = elm; \ - elm = tmp; \ - } \ - RB_SET_BLACKRED(parent, gparent, field); \ - RB_ROTATE_LEFT(head, gparent, tmp, field); \ - } \ - } \ - RB_COLOR(head->rbh_root, field) = RB_BLACK; \ + _rb_init(&head->rbh_root); \ } \ \ -attr void \ -name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_INSERT(struct _name *head, struct _type *elm) \ { \ - struct type *tmp; \ - while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ - elm != RB_ROOT(head)) { \ - if (RB_LEFT(parent, field) == elm) { \ - tmp = RB_RIGHT(parent, field); \ - if (RB_COLOR(tmp, field) == RB_RED) { \ - RB_SET_BLACKRED(tmp, parent, field); \ - RB_ROTATE_LEFT(head, parent, tmp, field);\ - tmp = RB_RIGHT(parent, field); \ - } \ - if ((RB_LEFT(tmp, field) == NULL || \ - RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ - (RB_RIGHT(tmp, field) == NULL || \ - RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ - RB_COLOR(tmp, field) = RB_RED; \ - elm = parent; \ - parent = RB_PARENT(elm, field); \ - } else { \ - if (RB_RIGHT(tmp, field) == NULL || \ - RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ - struct type *oleft; \ - if ((oleft = RB_LEFT(tmp, field)))\ - RB_COLOR(oleft, field) = RB_BLACK;\ - RB_COLOR(tmp, field) = RB_RED; \ - RB_ROTATE_RIGHT(head, tmp, oleft, field);\ - tmp = RB_RIGHT(parent, field); \ - } \ - RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ - RB_COLOR(parent, field) = RB_BLACK; \ - if (RB_RIGHT(tmp, field)) \ - RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ - RB_ROTATE_LEFT(head, parent, tmp, field);\ - elm = RB_ROOT(head); \ - break; \ - } \ - } else { \ - tmp = RB_LEFT(parent, field); \ - if (RB_COLOR(tmp, field) == RB_RED) { \ - RB_SET_BLACKRED(tmp, parent, field); \ - RB_ROTATE_RIGHT(head, parent, tmp, field);\ - tmp = RB_LEFT(parent, field); \ - } \ - if ((RB_LEFT(tmp, field) == NULL || \ - RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ - (RB_RIGHT(tmp, field) == NULL || \ - RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ - RB_COLOR(tmp, field) = RB_RED; \ - elm = parent; \ - parent = RB_PARENT(elm, field); \ - } else { \ - if (RB_LEFT(tmp, field) == NULL || \ - RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ - struct type *oright; \ - if ((oright = RB_RIGHT(tmp, field)))\ - RB_COLOR(oright, field) = RB_BLACK;\ - RB_COLOR(tmp, field) = RB_RED; \ - RB_ROTATE_LEFT(head, tmp, oright, field);\ - tmp = RB_LEFT(parent, field); \ - } \ - RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ - RB_COLOR(parent, field) = RB_BLACK; \ - if (RB_LEFT(tmp, field)) \ - RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ - RB_ROTATE_RIGHT(head, parent, tmp, field);\ - elm = RB_ROOT(head); \ - break; \ - } \ - } \ - } \ - if (elm) \ - RB_COLOR(elm, field) = RB_BLACK; \ + return _rb_insert(_name##_RB_TYPE, &head->rbh_root, elm); \ } \ \ -attr struct type * \ -name##_RB_REMOVE(struct name *head, struct type *elm) \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_REMOVE(struct _name *head, struct _type *elm) \ { \ - struct type *child, *parent, *old = elm; \ - int color; \ - if (RB_LEFT(elm, field) == NULL) \ - child = RB_RIGHT(elm, field); \ - else if (RB_RIGHT(elm, field) == NULL) \ - child = RB_LEFT(elm, field); \ - else { \ - struct type *left; \ - elm = RB_RIGHT(elm, field); \ - while ((left = RB_LEFT(elm, field))) \ - elm = left; \ - child = RB_RIGHT(elm, field); \ - parent = RB_PARENT(elm, field); \ - color = RB_COLOR(elm, field); \ - if (child) \ - RB_PARENT(child, field) = parent; \ - if (parent) { \ - if (RB_LEFT(parent, field) == elm) \ - RB_LEFT(parent, field) = child; \ - else \ - RB_RIGHT(parent, field) = child; \ - RB_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = child; \ - if (RB_PARENT(elm, field) == old) \ - parent = elm; \ - (elm)->field = (old)->field; \ - if (RB_PARENT(old, field)) { \ - if (RB_LEFT(RB_PARENT(old, field), field) == old)\ - RB_LEFT(RB_PARENT(old, field), field) = elm;\ - else \ - RB_RIGHT(RB_PARENT(old, field), field) = elm;\ - RB_AUGMENT(RB_PARENT(old, field)); \ - } else \ - RB_ROOT(head) = elm; \ - RB_PARENT(RB_LEFT(old, field), field) = elm; \ - if (RB_RIGHT(old, field)) \ - RB_PARENT(RB_RIGHT(old, field), field) = elm; \ - if (parent) { \ - left = parent; \ - do { \ - RB_AUGMENT(left); \ - } while ((left = RB_PARENT(left, field))); \ - } \ - goto color; \ - } \ - parent = RB_PARENT(elm, field); \ - color = RB_COLOR(elm, field); \ - if (child) \ - RB_PARENT(child, field) = parent; \ - if (parent) { \ - if (RB_LEFT(parent, field) == elm) \ - RB_LEFT(parent, field) = child; \ - else \ - RB_RIGHT(parent, field) = child; \ - RB_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = child; \ -color: \ - if (color == RB_BLACK) \ - name##_RB_REMOVE_COLOR(head, parent, child); \ - return (old); \ + return _rb_remove(_name##_RB_TYPE, &head->rbh_root, elm); \ } \ \ -/* Inserts a node into the RB tree */ \ -attr struct type * \ -name##_RB_INSERT(struct name *head, struct type *elm) \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_FIND(struct _name *head, const struct _type *key) \ { \ - struct type *tmp; \ - struct type *parent = NULL; \ - int comp = 0; \ - tmp = RB_ROOT(head); \ - while (tmp) { \ - parent = tmp; \ - comp = (cmp)(elm, parent); \ - if (comp < 0) \ - tmp = RB_LEFT(tmp, field); \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - RB_SET(elm, parent, field); \ - if (parent != NULL) { \ - if (comp < 0) \ - RB_LEFT(parent, field) = elm; \ - else \ - RB_RIGHT(parent, field) = elm; \ - RB_AUGMENT(parent); \ - } else \ - RB_ROOT(head) = elm; \ - name##_RB_INSERT_COLOR(head, elm); \ - return (NULL); \ + return _rb_find(_name##_RB_TYPE, &head->rbh_root, key); \ } \ \ -/* Finds the node with the same key as elm */ \ -attr struct type * \ -name##_RB_FIND(struct name *head, struct type *elm) \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_NFIND(struct _name *head, const struct _type *key) \ { \ - struct type *tmp = RB_ROOT(head); \ - int comp; \ - while (tmp) { \ - comp = cmp(elm, tmp); \ - if (comp < 0) \ - tmp = RB_LEFT(tmp, field); \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - return (NULL); \ + return _rb_nfind(_name##_RB_TYPE, &head->rbh_root, key); \ } \ \ -/* Finds the first node greater than or equal to the search key */ \ -attr struct type * \ -name##_RB_NFIND(struct name *head, struct type *elm) \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_ROOT(struct _name *head) \ { \ - struct type *tmp = RB_ROOT(head); \ - struct type *res = NULL; \ - int comp; \ - while (tmp) { \ - comp = cmp(elm, tmp); \ - if (comp < 0) { \ - res = tmp; \ - tmp = RB_LEFT(tmp, field); \ - } \ - else if (comp > 0) \ - tmp = RB_RIGHT(tmp, field); \ - else \ - return (tmp); \ - } \ - return (res); \ + return _rb_root(_name##_RB_TYPE, &head->rbh_root); \ } \ \ -/* ARGSUSED */ \ -attr struct type * \ -name##_RB_NEXT(struct type *elm) \ +__attribute__((__unused__)) static inline int \ +_name##_RB_EMPTY(struct _name *head) \ { \ - if (RB_RIGHT(elm, field)) { \ - elm = RB_RIGHT(elm, field); \ - while (RB_LEFT(elm, field)) \ - elm = RB_LEFT(elm, field); \ - } else { \ - if (RB_PARENT(elm, field) && \ - (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - else { \ - while (RB_PARENT(elm, field) && \ - (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ - elm = RB_PARENT(elm, field); \ - elm = RB_PARENT(elm, field); \ - } \ - } \ - return (elm); \ + return _rb_empty(&head->rbh_root); \ } \ \ -/* ARGSUSED */ \ -attr struct type * \ -name##_RB_PREV(struct type *elm) \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_MIN(struct _name *head) \ { \ - if (RB_LEFT(elm, field)) { \ - elm = RB_LEFT(elm, field); \ - while (RB_RIGHT(elm, field)) \ - elm = RB_RIGHT(elm, field); \ - } else { \ - if (RB_PARENT(elm, field) && \ - (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ - elm = RB_PARENT(elm, field); \ - else { \ - while (RB_PARENT(elm, field) && \ - (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ - elm = RB_PARENT(elm, field); \ - elm = RB_PARENT(elm, field); \ - } \ - } \ - return (elm); \ + return _rb_min(_name##_RB_TYPE, &head->rbh_root); \ } \ \ -attr struct type * \ -name##_RB_MINMAX(struct name *head, int val) \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_MAX(struct _name *head) \ { \ - struct type *tmp = RB_ROOT(head); \ - struct type *parent = NULL; \ - while (tmp) { \ - parent = tmp; \ - if (val < 0) \ - tmp = RB_LEFT(tmp, field); \ - else \ - tmp = RB_RIGHT(tmp, field); \ - } \ - return (parent); \ + return _rb_max(_name##_RB_TYPE, &head->rbh_root); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_NEXT(struct _type *elm) \ +{ \ + return _rb_next(_name##_RB_TYPE, elm); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_PREV(struct _type *elm) \ +{ \ + return _rb_prev(_name##_RB_TYPE, elm); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_LEFT(struct _type *elm) \ +{ \ + return _rb_left(_name##_RB_TYPE, elm); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_RIGHT(struct _type *elm) \ +{ \ + return _rb_right(_name##_RB_TYPE, elm); \ +} \ + \ +__attribute__((__unused__)) static inline struct _type * \ +_name##_RB_PARENT(struct _type *elm) \ +{ \ + return _rb_parent(_name##_RB_TYPE, elm); \ +} \ + \ +__attribute__((__unused__)) static inline void \ +_name##_RB_SET_LEFT(struct _type *elm, struct _type *left) \ +{ \ + return _rb_set_left(_name##_RB_TYPE, elm, left); \ +} \ + \ +__attribute__((__unused__)) static inline void \ +_name##_RB_SET_RIGHT(struct _type *elm, struct _type *right) \ +{ \ + return _rb_set_right(_name##_RB_TYPE, elm, right); \ +} \ + \ +__attribute__((__unused__)) static inline void \ +_name##_RB_SET_PARENT(struct _type *elm, struct _type *parent) \ +{ \ + return _rb_set_parent(_name##_RB_TYPE, elm, parent); \ +} \ + \ +__attribute__((__unused__)) static inline void \ +_name##_RB_POISON(struct _type *elm, unsigned long poison) \ +{ \ + return _rb_poison(_name##_RB_TYPE, elm, poison); \ +} \ + \ +__attribute__((__unused__)) static inline int \ +_name##_RB_CHECK(struct _type *elm, unsigned long poison) \ +{ \ + return _rb_check(_name##_RB_TYPE, elm, poison); \ } -#define RB_NEGINF -1 -#define RB_INF 1 - -#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) -#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) -#define RB_FIND(name, x, y) name##_RB_FIND(x, y) -#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) -#define RB_NEXT(name, x, y) name##_RB_NEXT(y) -#define RB_PREV(name, x, y) name##_RB_PREV(y) -#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) -#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) - -#define RB_FOREACH(x, name, head) \ - for ((x) = RB_MIN(name, head); \ - (x) != NULL; \ - (x) = name##_RB_NEXT(x)) - -#define RB_FOREACH_SAFE(x, name, head, y) \ - for ((x) = RB_MIN(name, head); \ - ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \ - (x) = (y)) - -#define RB_FOREACH_REVERSE(x, name, head) \ - for ((x) = RB_MAX(name, head); \ - (x) != NULL; \ - (x) = name##_RB_PREV(x)) - -#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ - for ((x) = RB_MAX(name, head); \ - ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \ - (x) = (y)) +#define RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) \ +static int \ +_name##_RB_COMPARE(const void *lptr, const void *rptr) \ +{ \ + const struct _type *l = lptr, *r = rptr; \ + return _cmp(l, r); \ +} \ +static const struct rb_type _name##_RB_INFO = { \ + _name##_RB_COMPARE, \ + _aug, \ + offsetof(struct _type, _field), \ +}; \ +const struct rb_type *const _name##_RB_TYPE = &_name##_RB_INFO; + +#define RB_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \ +static void \ +_name##_RB_AUGMENT(void *ptr) \ +{ \ + struct _type *p = ptr; \ + return _aug(p); \ +} \ +RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RB_AUGMENT) + +#define RB_GENERATE(_name, _type, _field, _cmp) \ + RB_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL) + +#define RB_INIT(_name, _head) _name##_RB_INIT(_head) +#define RB_INSERT(_name, _head, _elm) _name##_RB_INSERT(_head, _elm) +#define RB_REMOVE(_name, _head, _elm) _name##_RB_REMOVE(_head, _elm) +#define RB_FIND(_name, _head, _key) _name##_RB_FIND(_head, _key) +#define RB_NFIND(_name, _head, _key) _name##_RB_NFIND(_head, _key) +#define RB_ROOT(_name, _head) _name##_RB_ROOT(_head) +#define RB_EMPTY(_name, _head) _name##_RB_EMPTY(_head) +#define RB_MIN(_name, _head) _name##_RB_MIN(_head) +#define RB_MAX(_name, _head) _name##_RB_MAX(_head) +#define RB_NEXT(_name, _elm) _name##_RB_NEXT(_elm) +#define RB_PREV(_name, _elm) _name##_RB_PREV(_elm) +#define RB_LEFT(_name, _elm) _name##_RB_LEFT(_elm) +#define RB_RIGHT(_name, _elm) _name##_RB_RIGHT(_elm) +#define RB_PARENT(_name, _elm) _name##_RB_PARENT(_elm) +#define RB_SET_LEFT(_name, _elm, _l) _name##_RB_SET_LEFT(_elm, _l) +#define RB_SET_RIGHT(_name, _elm, _r) _name##_RB_SET_RIGHT(_elm, _r) +#define RB_SET_PARENT(_name, _elm, _p) _name##_RB_SET_PARENT(_elm, _p) +#define RB_POISON(_name, _elm, _p) _name##_RB_POISON(_elm, _p) +#define RB_CHECK(_name, _elm, _p) _name##_RB_CHECK(_elm, _p) + +#define RB_FOREACH(_e, _name, _head) \ + for ((_e) = RB_MIN(_name, (_head)); \ + (_e) != NULL; \ + (_e) = RB_NEXT(_name, (_e))) + +#define RB_FOREACH_SAFE(_e, _name, _head, _n) \ + for ((_e) = RB_MIN(_name, (_head)); \ + (_e) != NULL && ((_n) = RB_NEXT(_name, (_e)), 1); \ + (_e) = (_n)) + +#define RB_FOREACH_REVERSE(_e, _name, _head) \ + for ((_e) = RB_MAX(_name, (_head)); \ + (_e) != NULL; \ + (_e) = RB_PREV(_name, (_e))) + +#define RB_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \ + for ((_e) = RB_MAX(_name, (_head)); \ + (_e) != NULL && ((_n) = RB_PREV(_name, (_e)), 1); \ + (_e) = (_n)) #endif /* _SYS_TREE_H_ */ diff --git a/lib/routemap.c b/lib/routemap.c index ed79beb1e7..fcd3c7a7aa 100644 --- a/lib/routemap.c +++ b/lib/routemap.c @@ -2745,7 +2745,7 @@ DEFUN (no_rmap_continue, } -DEFUN_NOSH (rmap_show_name, +DEFUN (rmap_show_name, rmap_show_name_cmd, "show route-map [WORD]", SHOW_STR diff --git a/lib/termtable.c b/lib/termtable.c new file mode 100644 index 0000000000..283fa173d8 --- /dev/null +++ b/lib/termtable.c @@ -0,0 +1,487 @@ +/* + * ASCII table generator. + * Copyright (C) 2017 Cumulus Networks + * Quentin Young + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the Free + * Software Foundation; either version 2 of the License, or (at your option) + * any later version. + * + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; see the file COPYING; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ +#include <zebra.h> +#include <stdio.h> + +#include "memory.h" +#include "termtable.h" + +DEFINE_MTYPE_STATIC(LIB, TTABLE, "ASCII table") + +/* clang-format off */ +struct ttable_style ttable_styles[] = { + { // default ascii + .corner = '+', + .rownums_on = false, + .indent = 1, + .border.top = '-', + .border.bottom = '-', + .border.left = '|', + .border.right = '|', + .border.top_on = true, + .border.bottom_on = true, + .border.left_on = true, + .border.right_on = true, + .cell.lpad = 1, + .cell.rpad = 1, + .cell.align = LEFT, + .cell.border.bottom = '-', + .cell.border.bottom_on = true, + .cell.border.top = '-', + .cell.border.top_on = false, + .cell.border.right = '|', + .cell.border.right_on = true, + .cell.border.left = '|', + .cell.border.left_on = false, + }, { // blank, suitable for plaintext alignment + .corner = ' ', + .rownums_on = false, + .indent = 1, + .border.top = ' ', + .border.bottom = ' ', + .border.left = ' ', + .border.right = ' ', + .border.top_on = false, + .border.bottom_on = false, + .border.left_on = false, + .border.right_on = false, + .cell.lpad = 0, + .cell.rpad = 3, + .cell.align = LEFT, + .cell.border.bottom = ' ', + .cell.border.bottom_on = false, + .cell.border.top = ' ', + .cell.border.top_on = false, + .cell.border.right = ' ', + .cell.border.right_on = false, + .cell.border.left = ' ', + .cell.border.left_on = false, + } +}; +/* clang-format on */ + +void ttable_del(struct ttable *tt) +{ + for (int i = tt->nrows - 1; i >= 0; i--) + ttable_del_row(tt, i); + + XFREE(MTYPE_TTABLE, tt->table); + XFREE(MTYPE_TTABLE, tt); +} + +struct ttable *ttable_new(struct ttable_style *style) +{ + struct ttable *tt; + + tt = XCALLOC(MTYPE_TTABLE, sizeof(struct ttable)); + tt->style = *style; + tt->nrows = 0; + tt->ncols = 0; + tt->size = 0; + tt->table = NULL; + + return tt; +} + +/** + * Inserts or appends a new row at the specified index. + * + * If the index is -1, the row is added to the end of the table. Otherwise the + * index must be a valid index into tt->table. + * + * If the table already has at least one row (and therefore a determinate + * number of columns), a format string specifying a number of columns not equal + * to tt->ncols will result in a no-op and a return value of NULL. + * + * @param tt table to insert into + * @param i insertion index; inserted row will be (i + 1)'th row + * @param format printf format string as in ttable_[add|insert]_row() + * @param ap pre-initialized variadic list of arguments for format string + * + * @return pointer to the first cell of allocated row + */ +static struct ttable_cell *ttable_insert_row_va(struct ttable *tt, int i, + const char *format, va_list ap) +{ + assert(i >= -1 && i < tt->nrows); + + char *res, *orig, *section; + struct ttable_cell *row; + int col = 0; + int ncols = 0; + + /* count how many columns we have */ + for (int i = 0; format[i]; i++) + ncols += !!(format[i] == '|'); + ncols++; + + if (tt->ncols == 0) + tt->ncols = ncols; + else if (ncols != tt->ncols) + return NULL; + + /* reallocate chunk if necessary */ + while (tt->size < (tt->nrows + 1) * sizeof(struct ttable_cell *)) { + tt->size = MAX(2 * tt->size, 2 * sizeof(struct ttable_cell *)); + tt->table = XREALLOC(MTYPE_TTABLE, tt->table, tt->size); + } + + /* CALLOC a block of cells */ + row = XCALLOC(MTYPE_TTABLE, tt->ncols * sizeof(struct ttable_cell)); + + res = NULL; + vasprintf(&res, format, ap); + + orig = res; + + while (res) { + section = strsep(&res, "|"); + row[col].text = XSTRDUP(MTYPE_TTABLE, section); + row[col].style = tt->style.cell; + col++; + } + + free(orig); + + /* insert row */ + if (i == -1 || i == tt->nrows) + tt->table[tt->nrows] = row; + else { + memmove(&tt->table[i + 1], &tt->table[i], + (tt->nrows - i) * sizeof(struct ttable_cell *)); + tt->table[i] = row; + } + + tt->nrows++; + + return row; +} + +struct ttable_cell *ttable_insert_row(struct ttable *tt, unsigned int i, + const char *format, ...) +{ + struct ttable_cell *ret; + va_list ap; + + va_start(ap, format); + ret = ttable_insert_row_va(tt, i, format, ap); + va_end(ap); + + return ret; +} + +struct ttable_cell *ttable_add_row(struct ttable *tt, const char *format, ...) +{ + struct ttable_cell *ret; + va_list ap; + + va_start(ap, format); + ret = ttable_insert_row_va(tt, -1, format, ap); + va_end(ap); + + return ret; +} + +void ttable_del_row(struct ttable *tt, unsigned int i) +{ + assert((int)i < tt->nrows); + + for (int j = 0; j < tt->ncols; j++) + XFREE(MTYPE_TTABLE, tt->table[i][j].text); + + XFREE(MTYPE_TTABLE, tt->table[i]); + + memmove(&tt->table[i], &tt->table[i + 1], + (tt->nrows - i - 1) * sizeof(struct ttable_cell *)); + + tt->nrows--; + + if (tt->nrows == 0) + tt->ncols = 0; +} + +void ttable_align(struct ttable *tt, unsigned int row, unsigned int col, + unsigned int nrow, unsigned int ncol, enum ttable_align align) +{ + assert((int)row < tt->nrows); + assert((int)col < tt->ncols); + assert((int)row + (int)nrow <= tt->nrows); + assert((int)col + (int)ncol <= tt->ncols); + + for (unsigned int i = row; i < row + nrow; i++) + for (unsigned int j = col; j < col + ncol; j++) + tt->table[i][j].style.align = align; +} + +static void ttable_cell_pad(struct ttable_cell *cell, enum ttable_align align, + short pad) +{ + if (align == LEFT) + cell->style.lpad = pad; + else + cell->style.rpad = pad; +} + +void ttable_pad(struct ttable *tt, unsigned int row, unsigned int col, + unsigned int nrow, unsigned int ncol, enum ttable_align align, + short pad) +{ + assert((int)row < tt->nrows); + assert((int)col < tt->ncols); + assert((int)row + (int)nrow <= tt->nrows); + assert((int)col + (int)ncol <= tt->ncols); + + for (unsigned int i = row; i < row + nrow; i++) + for (unsigned int j = col; j < col + ncol; j++) + ttable_cell_pad(&tt->table[i][j], align, pad); +} + +void ttable_restyle(struct ttable *tt) +{ + for (int i = 0; i < tt->nrows; i++) + for (int j = 0; j < tt->ncols; j++) + tt->table[i][j].style = tt->style.cell; +} + +void ttable_colseps(struct ttable *tt, unsigned int col, + enum ttable_align align, bool on, char sep) +{ + for (int i = 0; i < tt->nrows; i++) { + if (align == RIGHT) { + tt->table[i][col].style.border.right_on = on; + tt->table[i][col].style.border.right = sep; + } else { + tt->table[i][col].style.border.left_on = on; + tt->table[i][col].style.border.left = sep; + } + } +} + +void ttable_rowseps(struct ttable *tt, unsigned int row, + enum ttable_align align, bool on, char sep) +{ + for (int i = 0; i < tt->ncols; i++) { + if (align == TOP) { + tt->table[row][i].style.border.top_on = on; + tt->table[row][i].style.border.top = sep; + } else { + tt->table[row][i].style.border.bottom_on = on; + tt->table[row][i].style.border.bottom = sep; + } + } +} + +char *ttable_dump(struct ttable *tt, const char *newline) +{ + /* clang-format off */ + char *buf; // print buffer + size_t pos; // position in buffer + size_t nl_len; // strlen(newline) + int cw[tt->ncols]; // calculated column widths + int nlines; // total number of newlines / table lines + size_t width; // length of one line, with newline + int abspad; // calculated whitespace for sprintf + char *left; // left part of line + size_t lsize; // size of above + char *right; // right part of line + size_t rsize; // size of above + struct ttable_cell *cell, *row; // iteration pointers + /* clang-format on */ + + nl_len = strlen(newline); + + /* calculate width of each column */ + memset(cw, 0x00, sizeof(int) * tt->ncols); + + for (int j = 0; j < tt->ncols; j++) + for (int i = 0, cellw = 0; i < tt->nrows; i++) { + cell = &tt->table[i][j]; + cellw = 0; + cellw += (int)strlen(cell->text); + cellw += cell->style.lpad; + cellw += cell->style.rpad; + if (j != 0) + cellw += cell->style.border.left_on ? 1 : 0; + if (j != tt->ncols - 1) + cellw += cell->style.border.right_on ? 1 : 0; + cw[j] = MAX(cw[j], cellw); + } + + /* calculate overall line width, including newline */ + width = 0; + width += tt->style.indent; + width += tt->style.border.left_on ? 1 : 0; + width += tt->style.border.right_on ? 1 : 0; + width += strlen(newline); + for (int i = 0; i < tt->ncols; i++) + width += cw[i]; + + /* calculate number of lines en total */ + nlines = tt->nrows; + nlines += tt->style.border.top_on ? 1 : 0; + nlines += 1; // tt->style.border.bottom_on ? 1 : 1; makes life easier + for (int i = 0; i < tt->nrows; i++) { + /* if leftmost cell has top / bottom border, whole row does */ + nlines += tt->table[i][0].style.border.top_on ? 1 : 0; + nlines += tt->table[i][0].style.border.bottom_on ? 1 : 0; + } + + /* initialize left & right */ + lsize = tt->style.indent + (tt->style.border.left_on ? 1 : 0); + left = XCALLOC(MTYPE_TTABLE, lsize); + rsize = nl_len + (tt->style.border.right_on ? 1 : 0); + right = XCALLOC(MTYPE_TTABLE, rsize); + + memset (left, ' ', lsize); + + if (tt->style.border.left_on) + left[lsize - 1] = tt->style.border.left; + + if (tt->style.border.right_on) { + right[0] = tt->style.border.right; + memcpy(&right[1], newline, nl_len); + } else + memcpy(&right[0], newline, nl_len); + + /* allocate print buffer */ + buf = XCALLOC(MTYPE_TMP, width * (nlines + 1) + 1); + pos = 0; + + if (tt->style.border.top_on) { + memcpy(&buf[pos], left, lsize); + pos += lsize; + + for (size_t i = 0; i < width - lsize - rsize; i++) + buf[pos++] = tt->style.border.top; + + memcpy(&buf[pos], right, rsize); + pos += rsize; + } + + for (int i = 0; i < tt->nrows; i++) { + row = tt->table[i]; + + /* if top border and not first row, print top row border */ + if (row[0].style.border.top_on && i != 0) { + memcpy(&buf[pos], left, lsize); + pos += lsize; + + for (size_t i = 0; i < width - lsize - rsize; i++) + buf[pos++] = row[0].style.border.top; + + pos -= width - lsize - rsize; + for (int k = 0; k < tt->ncols; k++) { + if (k != 0 && row[k].style.border.left_on) + buf[pos] = tt->style.corner; + pos += cw[k]; + if (row[k].style.border.right_on + && k != tt->ncols - 1) + buf[pos - 1] = tt->style.corner; + } + + memcpy(&buf[pos], right, rsize); + pos += rsize; + } + + memcpy(&buf[pos], left, lsize); + pos += lsize; + + for (int j = 0; j < tt->ncols; j++) { + /* if left border && not first col print left border */ + if (row[j].style.border.left_on && j != 0) + buf[pos++] = row[j].style.border.left; + + /* print left padding */ + for (int i = 0; i < row[j].style.lpad; i++) + buf[pos++] = ' '; + + /* calculate padding for sprintf */ + abspad = cw[j]; + abspad -= row[j].style.rpad; + abspad -= row[j].style.lpad; + if (j != 0) + abspad -= row[j].style.border.left_on ? 1 : 0; + if (j != tt->ncols - 1) + abspad -= row[j].style.border.right_on ? 1 : 0; + + /* print text */ + const char *fmt; + if (row[j].style.align == LEFT) + fmt = "%-*s"; + else + fmt = "%*s"; + + pos += sprintf(&buf[pos], fmt, abspad, row[j].text); + + /* print right padding */ + for (int i = 0; i < row[j].style.rpad; i++) + buf[pos++] = ' '; + + /* if right border && not last col print right border */ + if (row[j].style.border.right_on && j != tt->ncols - 1) + buf[pos++] = row[j].style.border.right; + } + + memcpy(&buf[pos], right, rsize); + pos += rsize; + + /* if bottom border and not last row, print bottom border */ + if (row[0].style.border.bottom_on && i != tt->nrows - 1) { + memcpy(&buf[pos], left, lsize); + pos += lsize; + + for (size_t i = 0; i < width - lsize - rsize; i++) + buf[pos++] = row[0].style.border.bottom; + + pos -= width - lsize - rsize; + for (int k = 0; k < tt->ncols; k++) { + if (k != 0 && row[k].style.border.left_on) + buf[pos] = tt->style.corner; + pos += cw[k]; + if (row[k].style.border.right_on + && k != tt->ncols - 1) + buf[pos - 1] = tt->style.corner; + } + + memcpy(&buf[pos], right, rsize); + pos += rsize; + } + + assert(!buf[pos]); /* pos == & of first \0 in buf */ + } + + if (tt->style.border.bottom_on) { + memcpy(&buf[pos], left, lsize); + pos += lsize; + + for (size_t i = 0; i < width - lsize - rsize; i++) + buf[pos++] = tt->style.border.bottom; + + memcpy(&buf[pos], right, rsize); + pos += rsize; + } + + buf[pos] = '\0'; + + XFREE(MTYPE_TTABLE, left); + XFREE(MTYPE_TTABLE, right); + + return buf; +} diff --git a/lib/termtable.h b/lib/termtable.h new file mode 100644 index 0000000000..6953002e90 --- /dev/null +++ b/lib/termtable.h @@ -0,0 +1,293 @@ +/* + * ASCII table generator. + * Copyright (C) 2017 Cumulus Networks + * Quentin Young + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the Free + * Software Foundation; either version 2 of the License, or (at your option) + * any later version. + * + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; see the file COPYING; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ +#ifndef _TERMTABLE_H_ +#define _TERMTABLE_H_ + +enum ttable_align { + LEFT, + RIGHT, + TOP, + BOTTOM, +}; + +struct ttable_border { + char top; + char bottom; + char left; + char right; + + bool top_on; + bool bottom_on; + bool left_on; + bool right_on; +}; + +/* cell style and cell */ +struct ttable_cellstyle { + short lpad; + short rpad; + enum ttable_align align; + struct ttable_border border; +}; + +struct ttable_cell { + char *text; + struct ttable_cellstyle style; +}; + +/* table style and table */ +struct ttable_style { + char corner; /* intersection */ + int indent; /* left table indent */ + bool rownums_on; /* show row numbers; unimplemented */ + + struct ttable_border border; + struct ttable_cellstyle cell; +}; + +struct ttable { + int nrows; /* number of rows */ + int ncols; /* number of cols */ + struct ttable_cell **table; /* table, row x col */ + size_t size; /* size */ + struct ttable_style style; /* style */ +}; + +/* some predefined styles */ +#define TTSTYLE_ASCII 0 +#define TTSTYLE_BLANK 1 + +extern struct ttable_style ttable_styles[2]; + +/** + * Creates a new table with the default style, which looks like this: + * + * +----------+----------+ + * | column 1 | column 2 | + * +----------+----------+ + * | data... | data!! | + * +----------+----------+ + * | datums | 12345 | + * +----------+----------+ + * + * @return the created table + */ +struct ttable *ttable_new(struct ttable_style *tts); + +/** + * Deletes a table and releases all associated resources. + * + * @param tt the table to destroy + */ +void ttable_del(struct ttable *tt); + +/** + * Deletes an individual cell. + * + * @param cell the cell to destroy + */ +void ttable_cell_del(struct ttable_cell *cell); + +/** + * Inserts a new row at the given index. + * + * The row contents are determined by a format string. The format string has + * the same form as a regular printf format string, except that columns are + * delimited by '|'. For example, to make the first column of the table above, + * the call is: + * + * ttable_insert_row(<tt>, <n>, "%s|%s", "column 1", "column 2"); + * + * All features of printf format strings are permissible here. + * + * Caveats: + * - At present you cannot insert '|' into a cell's contents. + * - If there are N columns, '|' must appear n-1 times or the row will not be + * created + * + * @param tt table to insert row into + * @param row the row number (begins at 0) + * @param format column-separated format string + * @param ... arguments to format string + * + * @return pointer to the first cell in the created row, or NULL if not enough + * columns were specified + */ +struct ttable_cell *ttable_insert_row(struct ttable *tt, unsigned int row, + const char *format, ...); +/** + * Inserts a new row at the end of the table. + * + * The row contents are determined by a format string. The format string has + * the same form as a regular printf format string, except that columns are + * delimited by '|'. For example, to make the first column of the table above, + * the call is: + * + * ttable_add_row(<tt>, "%s|%s", "column 1", "column 2"); + * + * All features of printf format strings are permissible here. + * + * Caveats: + * - At present you cannot insert '|' into a cell's contents. + * - If there are N columns, '|' must appear n-1 times or the row will not be + * created + * + * @param tt table to insert row into + * @param format column-separated format string + * @param ... arguments to format string + * + * @return pointer to the first cell in the created row, or NULL if not enough + * columns were specified + */ +struct ttable_cell *ttable_add_row(struct ttable *tt, const char *format, ...); + +/** + * Removes a row from the table. + * + * @param tt table to delete row from + * @param row the row number (begins at 0) + */ +void ttable_del_row(struct ttable *tt, unsigned int row); + +/** + * Sets alignment for a range of cells. + * + * Available alignments are LEFT and RIGHT. Cell contents will be aligned + * accordingly, while respecting padding (if any). Suppose a cell has: + * + * lpad = 1 + * rpad = 1 + * align = RIGHT + * text = 'datums' + * + * The cell would look like: + * + * +-------------------+ + * | datums | + * +-------------------+ + * + * On the other hand: + * + * lpad = 1 + * rpad = 10 + * align = RIGHT + * text = 'datums' + * + * +-------------------+ + * | datums | + * +-------------------+ + * + * The default alignment is LEFT. + * + * @param tt the table to set alignment on + * @param srow starting row index + * @param scol starting column index + * @param nrow # rows to align + * @param ncol # cols to align + * @param align the alignment to set + */ +void ttable_align(struct ttable *tt, unsigned int srow, unsigned int scol, + unsigned int erow, unsigned int ecol, + enum ttable_align align); + +/** + * Sets padding for a range of cells. + * + * Available padding options are LEFT and RIGHT (the alignment enum is reused). + * Both options may be set. Padding is treated as though it is stuck to the + * walls of the cell. Suppose a cell has: + * + * lpad = 4 + * rpad = 2 + * align = RIGHT + * text = 'datums' + * + * The cell padding, marked by '.', would look like: + * + * +--------------+ + * | .datums. | + * +--------------+ + * + * If the column is wider than the cell, the cell contents are aligned in an + * additional padded field according to the cell alignment. + * + * +--------------------+ + * | Data!!!11!~~~~~:-) | + * +--------------------+ + * | . datums. | + * +--------------------+ + * + * @param tt the table to set padding on + * @param srow starting row index + * @param scol starting column index + * @param nrow # rows to pad + * @param ncol # cols to pad + * @param align LEFT or RIGHT + * @param pad # spaces to pad with + */ +void ttable_pad(struct ttable *tt, unsigned int srow, unsigned int scol, + unsigned int nrow, unsigned int ncol, enum ttable_align align, + short pad); + +/** + * Restyle all cells according to table.cell.style. + * + * @param tt table to restyle + */ +void ttable_restyle(struct ttable *tt); + +/** + * Turn left/right column separators on or off for specified column. + * + * @param tt table + * @param col column index + * @param align left or right separators + * @param on true/false for on/off + * @param sep character to use + */ +void ttable_colseps(struct ttable *tt, unsigned int col, + enum ttable_align align, bool on, char sep); + +/** + * Turn bottom row separators on or off for specified row. + * + * @param tt table + * @param row row index + * @param align left or right separators + * @param on true/false for on/off + * @param sep character to use + */ +void ttable_rowseps(struct ttable *tt, unsigned int row, + enum ttable_align align, bool on, char sep); + +/** + * Dumps a table to a heap-allocated string. + * + * Caller must free this string after use with + * + * XFREE (MTYPE_TMP, str); + * + * @param tt the table to dump + * @param newline the desired newline sequence to use, null terminated. + * @return table in text form + */ +char *ttable_dump(struct ttable *tt, const char *newline); + +#endif /* _TERMTABLE_H */ @@ -35,11 +35,11 @@ DEFINE_MTYPE_STATIC(LIB, VRF_BITMAP, "VRF bit-map") DEFINE_QOBJ_TYPE(vrf) -static __inline int vrf_id_compare (struct vrf *, struct vrf *); -static __inline int vrf_name_compare (struct vrf *, struct vrf *); +static __inline int vrf_id_compare (const struct vrf *, const struct vrf *); +static __inline int vrf_name_compare (const struct vrf *, const struct vrf *); -RB_GENERATE (vrf_id_head, vrf, id_entry, vrf_id_compare) -RB_GENERATE (vrf_name_head, vrf, name_entry, vrf_name_compare) +RB_GENERATE (vrf_id_head, vrf, id_entry, vrf_id_compare); +RB_GENERATE (vrf_name_head, vrf, name_entry, vrf_name_compare); struct vrf_id_head vrfs_by_id = RB_INITIALIZER (&vrfs_by_id); struct vrf_name_head vrfs_by_name = RB_INITIALIZER (&vrfs_by_name); @@ -72,13 +72,13 @@ vrf_lookup_by_name (const char *name) } static __inline int -vrf_id_compare (struct vrf *a, struct vrf *b) +vrf_id_compare (const struct vrf *a, const struct vrf *b) { return (a->vrf_id - b->vrf_id); } static int -vrf_name_compare (struct vrf *a, struct vrf *b) +vrf_name_compare (const struct vrf *a, const struct vrf *b) { return strcmp (a->name, b->name); } @@ -377,6 +377,28 @@ vrf_bitmap_check (vrf_bitmap_t bmap, vrf_id_t vrf_id) VRF_BITMAP_FLAG (offset)) ? 1 : 0; } +static void +vrf_autocomplete (vector comps, struct cmd_token *token) +{ + struct vrf *vrf = NULL; + + RB_FOREACH (vrf, vrf_name_head, &vrfs_by_name) + { + if (vrf->vrf_id != 0) + vector_set (comps, XSTRDUP (MTYPE_COMPLETION, vrf->name)); + } +} + +static const struct cmd_variable_handler vrf_var_handlers[] = { + { + .varname = "vrf", + .completions = vrf_autocomplete, + }, + { + .completions = NULL + }, +}; + /* Initialize VRF module. */ void vrf_init (int (*create)(struct vrf *), @@ -408,6 +430,8 @@ vrf_init (int (*create)(struct vrf *), zlog_err ("vrf_init: failed to enable the default VRF!"); exit (1); } + + cmd_variable_handler_register (vrf_var_handlers); } /* Terminate VRF module. */ @@ -419,9 +443,9 @@ vrf_terminate (void) if (debug_vrf) zlog_debug ("%s: Shutting down vrf subsystem", __PRETTY_FUNCTION__); - while ((vrf = RB_ROOT (&vrfs_by_id)) != NULL) + while ((vrf = RB_ROOT (vrf_id_head, &vrfs_by_id)) != NULL) vrf_delete (vrf); - while ((vrf = RB_ROOT (&vrfs_by_name)) != NULL) + while ((vrf = RB_ROOT (vrf_name_head, &vrfs_by_name)) != NULL) vrf_delete (vrf); } @@ -2212,7 +2212,10 @@ vtysh_read (struct thread *thread) } } - vty_event (VTYSH_READ, sock, vty); + if (vty->status == VTY_CLOSE) + vty_close (vty); + else + vty_event (VTYSH_READ, sock, vty); return 0; } @@ -3151,29 +3154,3 @@ vty_terminate (void) Vvty_serv_thread = NULL; } } - -/* Utility functions to get arguments from commands generated - by the xml2cli.pl script. */ -const char * -vty_get_arg_value (struct vty_arg *args[], const char *arg) -{ - while (*args) - { - if (strcmp ((*args)->name, arg) == 0) - return (*args)->value; - args++; - } - return NULL; -} - -struct vty_arg * -vty_get_arg (struct vty_arg *args[], const char *arg) -{ - while (*args) - { - if (strcmp ((*args)->name, arg) == 0) - return *args; - args++; - } - return NULL; -} @@ -342,7 +342,4 @@ extern void vty_hello (struct vty *); an async-signal-safe function. */ extern void vty_log_fixed (char *buf, size_t len); -extern const char *vty_get_arg_value (struct vty_arg **, const char *); -extern struct vty_arg *vty_get_arg (struct vty_arg **, const char *); - #endif /* _ZEBRA_VTY_H */ diff --git a/lib/zebra.h b/lib/zebra.h index 0a61c433d9..2cc433a863 100644 --- a/lib/zebra.h +++ b/lib/zebra.h @@ -126,6 +126,8 @@ typedef unsigned char u_int8_t; #define __APPLE_USE_RFC_3542 #endif +#include "lib/openbsd-tree.h" + #include <netinet/in.h> #include <netinet/in_systm.h> #include <netinet/ip.h> |