diff options
| -rw-r--r-- | lib/command.c | 182 | ||||
| -rw-r--r-- | lib/memory.c | 40 | ||||
| -rw-r--r-- | lib/memory.h | 6 | ||||
| -rw-r--r-- | lib/memtypes.c | 8 | ||||
| -rw-r--r-- | lib/vector.c | 1192 | ||||
| -rw-r--r-- | lib/vector.h | 276 | ||||
| -rw-r--r-- | lib/vty.c | 122 |
7 files changed, 1539 insertions, 287 deletions
diff --git a/lib/command.c b/lib/command.c index 31c067a3..60880f49 100644 --- a/lib/command.c +++ b/lib/command.c @@ -1,11 +1,11 @@ /* $Id$ - + Command interpreter routine for virtual terminal [aka TeletYpe] Copyright (C) 1997, 98, 99 Kunihiro Ishiguro This file is part of GNU Zebra. - + GNU Zebra 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, or (at your @@ -93,7 +93,7 @@ static struct facility_map { int facility; const char *name; size_t match; -} syslog_facilities[] = +} syslog_facilities[] = { { LOG_KERN, "kern", 1 }, { LOG_USER, "user", 2 }, @@ -145,7 +145,7 @@ static int level_match(const char *s) { int level ; - + for ( level = 0 ; zlog_priority [level] != NULL ; level ++ ) if (!strncmp (s, zlog_priority[level], 2)) return level; @@ -160,7 +160,7 @@ print_version (const char *progname) printf ("%s\n", QUAGGA_COPYRIGHT); } - + /* Utility function to concatenate argv argument into a single string with inserting ' ' character between each argument. */ char * @@ -190,30 +190,24 @@ argv_concat (const char **argv, int argc, int shift) /* Install top node of command vector. */ void -install_node (struct cmd_node *node, +install_node (struct cmd_node *node, int (*func) (struct vty *)) { vector_set_index (cmdvec, node->node, node); node->func = func; - node->cmd_vector = vector_init (VECTOR_MIN_SIZE); + node->cmd_vector = vector_init (0); } /* Compare two command's string. Used in sort_node (). */ static int -cmp_node (const void *p, const void *q) +cmp_node (const struct cmd_element *a, const struct cmd_element *b) { - const struct cmd_element *a = *(struct cmd_element * const *)p; - const struct cmd_element *b = *(struct cmd_element * const *)q; - return strcmp (a->string, b->string); } static int -cmp_desc (const void *p, const void *q) +cmp_desc (const struct desc *a, const struct desc *b) { - const struct desc *a = *(struct desc * const *)p; - const struct desc *b = *(struct desc * const *)q; - return strcmp (a->cmd, b->cmd); } @@ -223,24 +217,21 @@ sort_node () { unsigned int i, j; struct cmd_node *cnode; - vector descvec; struct cmd_element *cmd_element; for (i = 0; i < vector_active (cmdvec); i++) if ((cnode = vector_slot (cmdvec, i)) != NULL) - { + { vector cmd_vector = cnode->cmd_vector; - qsort (cmd_vector->index, vector_active (cmd_vector), - sizeof (void *), cmp_node); + vector_sort(cmd_vector, (vector_sort_cmp*)cmp_node) ; for (j = 0; j < vector_active (cmd_vector); j++) if ((cmd_element = vector_slot (cmd_vector, j)) != NULL && vector_active (cmd_element->strvec)) { - descvec = vector_slot (cmd_element->strvec, + vector descvec = vector_slot (cmd_element->strvec, vector_active (cmd_element->strvec) - 1); - qsort (descvec->index, vector_active (descvec), - sizeof (void *), cmp_desc); + vector_sort(descvec, (vector_sort_cmp*)cmp_desc) ; } } } @@ -255,10 +246,10 @@ cmd_make_strvec (const char *string) char *token; int strlen; vector strvec; - + if (string == NULL) return NULL; - + cp = string; /* Skip white spaces. */ @@ -273,10 +264,10 @@ cmd_make_strvec (const char *string) return NULL; /* Prepare return vector. */ - strvec = vector_init (VECTOR_MIN_SIZE); + strvec = vector_init (0); /* Copy each command piece and set into vector. */ - while (1) + while (1) { start = cp; while (!(isspace ((int) *cp) || *cp == '\r' || *cp == '\n') && @@ -321,7 +312,7 @@ cmd_desc_str (const char **string) const char *cp, *start; char *token; int strlen; - + cp = *string; if (cp == NULL) @@ -370,7 +361,7 @@ cmd_make_descvec (const char *string, const char *descstr) if (cp == NULL) return NULL; - allvec = vector_init (VECTOR_MIN_SIZE); + allvec = vector_init (0); while (1) { @@ -396,7 +387,7 @@ cmd_make_descvec (const char *string, const char *descstr) } cp++; } - + while (isspace ((int) *cp) && *cp != '\0') cp++; @@ -406,7 +397,7 @@ cmd_make_descvec (const char *string, const char *descstr) cp++; } - if (*cp == '\0') + if (*cp == '\0') return allvec; sp = cp; @@ -428,14 +419,14 @@ cmd_make_descvec (const char *string, const char *descstr) { if (multiple == 1) { - strvec = vector_init (VECTOR_MIN_SIZE); + strvec = vector_init (0); vector_set (allvec, strvec); } multiple++; } else { - strvec = vector_init (VECTOR_MIN_SIZE); + strvec = vector_init (0); vector_set (allvec, strvec); } vector_set (strvec, desc); @@ -484,14 +475,14 @@ void install_element (enum node_type ntype, struct cmd_element *cmd) { struct cmd_node *cnode; - + /* cmd_init hasn't been called */ if (!cmdvec) return; - + cnode = vector_slot (cmdvec, ntype); - if (cnode == NULL) + if (cnode == NULL) { fprintf (stderr, "Command node %d doesn't exist, please check it\n", ntype); @@ -506,13 +497,13 @@ install_element (enum node_type ntype, struct cmd_element *cmd) cmd->cmdsize = cmd_cmdsize (cmd->strvec); } -static unsigned char itoa64[] = +static unsigned char itoa64[] = "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; static void to64(char *s, long v, int n) { - while (--n >= 0) + while (--n >= 0) { *s++ = itoa64[v&0x3f]; v >>= 6; @@ -527,7 +518,7 @@ zencrypt (const char *passwd) char *crypt (const char *, const char *); gettimeofday(&tv,0); - + to64(&salt[0], random(), 3); to64(&salt[3], tv.tv_usec, 3); salt[5] = '\0'; @@ -545,9 +536,9 @@ config_write_host (struct vty *vty) if (host.encrypt) { if (host.password_encrypt) - vty_out (vty, "password 8 %s%s", host.password_encrypt, VTY_NEWLINE); + vty_out (vty, "password 8 %s%s", host.password_encrypt, VTY_NEWLINE); if (host.enable_encrypt) - vty_out (vty, "enable password 8 %s%s", host.enable_encrypt, VTY_NEWLINE); + vty_out (vty, "enable password 8 %s%s", host.enable_encrypt, VTY_NEWLINE); } else { @@ -684,7 +675,7 @@ cmd_filter_by_symbol (char *command, char *symbol) #endif /* Completion match types. */ -enum match_type +enum match_type { no_match, extend_match, @@ -695,7 +686,7 @@ enum match_type range_match, vararg_match, partly_match, - exact_match + exact_match }; static enum match_type @@ -866,7 +857,7 @@ cmd_ipv6_match (const char *str) * ::1.2.3.4 */ ret = inet_pton(AF_INET6, str, &sin6_dummy.sin6_addr); - + if (ret == 1) return exact_match; @@ -1071,7 +1062,7 @@ cmd_ipv6_prefix_match (const char *str) if (mask < 0 || mask > 128) return no_match; - + /* I don't know why mask < 13 makes command match partly. Forgive me to make this comments. I Want to set static default route because of lack of function to originate default in ospf6d; sorry @@ -1162,7 +1153,7 @@ cmd_filter_by_completion (char *command, vector v, unsigned int index) if ((desc = vector_slot (descvec, j))) { str = desc->cmd; - + if (CMD_VARARG (str)) { if (match_type < vararg_match) @@ -1378,7 +1369,7 @@ is_cmd_ambiguous (char *command, vector v, int index, enum match_type type) if ((desc = vector_slot (descvec, j))) { enum match_type ret; - + str = desc->cmd; switch (type) @@ -1567,7 +1558,7 @@ desc_unique_string (vector v, const char *str) return 0; } -static int +static int cmd_try_do_shortcut (enum node_type node, char* first_word) { if ( first_word != NULL && node != AUTH_NODE && @@ -1602,7 +1593,7 @@ cmd_describe_command_real (vector vline, struct vty *vty, int *status) } else index = vector_active (vline) - 1; - + /* Make copy vector of current node's command vector. */ cmd_vector = vector_copy (cmd_node_vector (cmdvec, vty->node)); @@ -1615,7 +1606,7 @@ cmd_describe_command_real (vector vline, struct vty *vty, int *status) if ((command = vector_slot (vline, i))) { match = cmd_filter_by_completion (command, cmd_vector, i); - + if (match == vararg_match) { struct cmd_element *cmd_element; @@ -1634,7 +1625,7 @@ cmd_describe_command_real (vector vline, struct vty *vty, int *status) vector_set (matchvec, desc); } } - + vector_set (matchvec, &desc_cr); vector_free (cmd_vector); @@ -1734,7 +1725,7 @@ cmd_describe_command (vector vline, struct vty *vty, int *status) shifted_vline = vector_init (vector_count(vline)); /* use memcpy? */ - for (index = 1; index < vector_active (vline); index++) + for (index = 1; index < vector_active (vline); index++) { vector_set_index (shifted_vline, index-1, vector_lookup(vline, index)); } @@ -1836,7 +1827,7 @@ cmd_complete_command_real (vector vline, struct vty *vty, int *status) } */ } - + /* Prepare match vector. */ matchvec = vector_init (INIT_MATCHVEC_SIZE); @@ -1858,7 +1849,7 @@ cmd_complete_command_real (vector vline, struct vty *vty, int *status) for (j = 0; j < vector_active (descvec); j++) if ((desc = vector_slot (descvec, j))) { - if ((string = + if ((string = cmd_entry_function (vector_slot (vline, index), desc->cmd))) if (cmd_unique_string (matchvec, string)) @@ -1884,10 +1875,11 @@ cmd_complete_command_real (vector vline, struct vty *vty, int *status) return NULL; } +/* XXX: TODO: stop poking around inside vector */ /* Only one matched */ if (vector_slot (matchvec, 1) == NULL) { - match_str = (char **) matchvec->index; + match_str = (char **) matchvec->VECTOR_INDEX; vector_only_wrapper_free (matchvec); *status = CMD_COMPLETE_FULL_MATCH; return match_str; @@ -1898,7 +1890,7 @@ cmd_complete_command_real (vector vline, struct vty *vty, int *status) /* Check LCD of matched strings. */ if (vector_slot (vline, index) != NULL) { - lcd = cmd_lcd ((char **) matchvec->index); + lcd = cmd_lcd ((char **) matchvec->VECTOR_INDEX); if (lcd) { @@ -1909,7 +1901,7 @@ cmd_complete_command_real (vector vline, struct vty *vty, int *status) char *lcdstr; lcdstr = XMALLOC (MTYPE_STRVEC, lcd + 1); - memcpy (lcdstr, matchvec->index[0], lcd); + memcpy (lcdstr, matchvec->VECTOR_INDEX[0], lcd); lcdstr[lcd] = '\0'; /* match_str = (char **) &lcdstr; */ @@ -1925,7 +1917,7 @@ cmd_complete_command_real (vector vline, struct vty *vty, int *status) /* Make new matchvec. */ matchvec = vector_init (INIT_MATCHVEC_SIZE); vector_set (matchvec, lcdstr); - match_str = (char **) matchvec->index; + match_str = (char **) matchvec->VECTOR_INDEX; vector_only_wrapper_free (matchvec); *status = CMD_COMPLETE_MATCH; @@ -1934,7 +1926,7 @@ cmd_complete_command_real (vector vline, struct vty *vty, int *status) } } - match_str = (char **) matchvec->index; + match_str = (char **) matchvec->VECTOR_INDEX; vector_only_wrapper_free (matchvec); *status = CMD_COMPLETE_LIST_MATCH; return match_str; @@ -1957,7 +1949,7 @@ cmd_complete_command (vector vline, struct vty *vty, int *status) shifted_vline = vector_init (vector_count(vline)); /* use memcpy? */ - for (index = 1; index < vector_active (vline); index++) + for (index = 1; index < vector_active (vline); index++) { vector_set_index (shifted_vline, index-1, vector_lookup(vline, index)); } @@ -2030,7 +2022,7 @@ cmd_execute_command_real (vector vline, struct vty *vty, if (match == vararg_match) break; - + ret = is_cmd_ambiguous (command, cmd_vector, index, match); if (ret == 1) @@ -2141,7 +2133,7 @@ cmd_execute_command (vector vline, struct vty *vty, struct cmd_element **cmd, shifted_vline = vector_init (vector_count(vline)); /* use memcpy? */ - for (index = 1; index < vector_active (vline); index++) + for (index = 1; index < vector_active (vline); index++) { vector_set_index (shifted_vline, index-1, vector_lookup(vline, index)); } @@ -2160,7 +2152,7 @@ cmd_execute_command (vector vline, struct vty *vty, struct cmd_element **cmd, return saved_ret; /* This assumes all nodes above CONFIG_NODE are childs of CONFIG_NODE */ - while ( ret != CMD_SUCCESS && ret != CMD_WARNING + while ( ret != CMD_SUCCESS && ret != CMD_WARNING && vty->node > CONFIG_NODE ) { try_node = node_parent(try_node); @@ -2204,14 +2196,14 @@ cmd_execute_command_strict (vector vline, struct vty *vty, if ((command = vector_slot (vline, index))) { int ret; - + match = cmd_filter_by_string (vector_slot (vline, index), cmd_vector, index); /* If command meets '.VARARG' then finish matching. */ if (match == vararg_match) break; - + ret = is_cmd_ambiguous (command, cmd_vector, index, match); if (ret == 1) { @@ -2351,7 +2343,7 @@ DEFUN (config_terminal, } /* Enable command */ -DEFUN (enable, +DEFUN (enable, config_enable_cmd, "enable", "Turn on privileged mode command\n") @@ -2367,7 +2359,7 @@ DEFUN (enable, } /* Disable command */ -DEFUN (disable, +DEFUN (disable, config_disable_cmd, "disable", "Turn off privileged mode command\n") @@ -2432,7 +2424,7 @@ ALIAS (config_exit, config_quit_cmd, "quit", "Exit current mode and down to previous mode\n") - + /* End of configuration. */ DEFUN (config_end, config_end_cmd, @@ -2494,7 +2486,7 @@ DEFUN (config_help, "help", "Description of the interactive help system\n") { - vty_out (vty, + vty_out (vty, "Quagga VTY provides advanced help feature. When you need help,%s\ anytime at the command line please press '?'.%s\ %s\ @@ -2532,9 +2524,9 @@ DEFUN (config_list, } /* Write current configuration into file. */ -DEFUN (config_write_file, +DEFUN (config_write_file, config_write_file_cmd, - "write file", + "write file", "Write running configuration to memory, network, or terminal\n" "Write to configuration file\n") { @@ -2557,7 +2549,7 @@ DEFUN (config_write_file, /* Get filename. */ config_file = host.config; - + config_file_sav = XMALLOC (MTYPE_TMP, strlen (config_file) + strlen (CONF_BACKUP_EXT) + 1); strcpy (config_file_sav, config_file); @@ -2566,7 +2558,7 @@ DEFUN (config_write_file, config_file_tmp = XMALLOC (MTYPE_TMP, strlen (config_file) + 8); sprintf (config_file_tmp, "%s.XXXXXX", config_file); - + /* Open file to configuration write. */ fd = mkstemp (config_file_tmp); if (fd < 0) @@ -2575,7 +2567,7 @@ DEFUN (config_write_file, VTY_NEWLINE); goto finished; } - + /* Make vty for configuration file. */ file_vty = vty_new (); file_vty->fd = fd; @@ -2621,10 +2613,10 @@ DEFUN (config_write_file, goto finished; } sync (); - + if (chmod (config_file, CONFIGFILE_MASK) != 0) { - vty_out (vty, "Can't chmod configuration file %s: %s (%d).%s", + vty_out (vty, "Can't chmod configuration file %s: %s (%d).%s", config_file, safe_strerror(errno), errno, VTY_NEWLINE); goto finished; } @@ -2640,20 +2632,20 @@ finished: return ret; } -ALIAS (config_write_file, +ALIAS (config_write_file, config_write_cmd, - "write", + "write", "Write running configuration to memory, network, or terminal\n") -ALIAS (config_write_file, +ALIAS (config_write_file, config_write_memory_cmd, - "write memory", + "write memory", "Write running configuration to memory, network, or terminal\n" "Write configuration to the file (same as write file)\n") -ALIAS (config_write_file, +ALIAS (config_write_file, copy_runningconfig_startupconfig_cmd, - "copy running-config startup-config", + "copy running-config startup-config", "Copy configuration\n" "Copy running config to... \n" "Copy running config to startup config (same as write file)\n") @@ -2736,7 +2728,7 @@ DEFUN (show_startup_config, } /* Hostname configuration */ -DEFUN (config_hostname, +DEFUN (config_hostname, hostname_cmd, "hostname WORD", "Set system's network name\n" @@ -2750,12 +2742,12 @@ DEFUN (config_hostname, if (host.name) XFREE (MTYPE_HOST, host.name); - + host.name = XSTRDUP (MTYPE_HOST, argv[0]); return CMD_SUCCESS; } -DEFUN (config_no_hostname, +DEFUN (config_no_hostname, no_hostname_cmd, "no hostname [HOSTNAME]", NO_STR @@ -2804,7 +2796,7 @@ DEFUN (config_password, password_cmd, if (!isalnum ((int) *argv[0])) { - vty_out (vty, + vty_out (vty, "Please specify string starting with alphanumeric%s", VTY_NEWLINE); return CMD_WARNING; } @@ -2870,7 +2862,7 @@ DEFUN (config_enable_password, enable_password_cmd, if (!isalnum ((int) *argv[0])) { - vty_out (vty, + vty_out (vty, "Please specify string starting with alphanumeric%s", VTY_NEWLINE); return CMD_WARNING; } @@ -2916,7 +2908,7 @@ DEFUN (no_config_enable_password, no_enable_password_cmd, return CMD_SUCCESS; } - + DEFUN (service_password_encrypt, service_password_encrypt_cmd, "service password-encryption", @@ -3195,19 +3187,19 @@ set_log_file(struct vty *vty, const char *fname, int loglevel) int ret; char *p = NULL; const char *fullpath; - + /* Path detection. */ if (! IS_DIRECTORY_SEP (*fname)) { char cwd[MAXPATHLEN+1]; cwd[MAXPATHLEN] = '\0'; - + if (getcwd (cwd, MAXPATHLEN) == NULL) { zlog_err ("config_log_file: Unable to alloc mem!"); return CMD_WARNING; } - + if ( (p = XMALLOC (MTYPE_TMP, strlen (cwd) + strlen (fname) + 2)) == NULL) { @@ -3391,7 +3383,7 @@ DEFUN_DEPRECATED (config_log_trap, { int new_level ; int i; - + if ((new_level = level_match(argv[0])) == ZLOG_DISABLED) return CMD_ERR_NO_MATCH; @@ -3500,7 +3492,7 @@ DEFUN (no_banner_motd, "Strings for motd\n") { host.motd = NULL; - if (host.motdfile) + if (host.motdfile) XFREE (MTYPE_HOST, host.motdfile); host.motdfile = NULL; return CMD_SUCCESS; @@ -3540,7 +3532,7 @@ cmd_init (int terminal) desc_cr.str = XSTRDUP(MTYPE_STRVEC, ""); /* Allocate initial top vector of commands. */ - cmdvec = vector_init (VECTOR_MIN_SIZE); + cmdvec = vector_init (0); /* Default host value settings. */ host.name = NULL; @@ -3604,7 +3596,7 @@ cmd_init (int terminal) install_default (CONFIG_NODE); } - + install_element (CONFIG_NODE, &hostname_cmd); install_element (CONFIG_NODE, &no_hostname_cmd); @@ -3667,7 +3659,7 @@ cmd_terminate () if (cmdvec) { - for (i = 0; i < vector_active (cmdvec); i++) + for (i = 0; i < vector_active (cmdvec); i++) if ((cmd_node = vector_slot (cmdvec, i)) != NULL) { cmd_node_v = cmd_node->cmd_vector; diff --git a/lib/memory.c b/lib/memory.c index dc09d8a6..333f59ad 100644 --- a/lib/memory.c +++ b/lib/memory.c @@ -17,7 +17,7 @@ * You should have received a copy of the GNU General Public License * along with GNU Zebra; see the file COPYING. If not, write to the Free * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA - * 02111-1307, USA. + * 02111-1307, USA. */ #include <zebra.h> @@ -32,22 +32,22 @@ static void alloc_inc (int); static void alloc_dec (int); static void log_memstats(int log_priority); - + static const struct message mstr [] = { { MTYPE_THREAD, "thread" }, { MTYPE_THREAD_MASTER, "thread_master" }, { MTYPE_VECTOR, "vector" }, - { MTYPE_VECTOR_INDEX, "vector_index" }, + { MTYPE_VECTOR_BODY, "vector_index" }, { MTYPE_IF, "interface" }, { 0, NULL }, }; - + /* Fatal memory allocation error occured. */ static void __attribute__ ((noreturn)) zerror (const char *fname, int type, size_t size) { - zlog_err ("%s : can't allocate memory for `%s' size %d: %s\n", + zlog_err ("%s : can't allocate memory for `%s' size %d: %s\n", fname, lookup (mstr, type), (int) size, safe_strerror(errno)); log_memstats(LOG_WARNING); /* N.B. It might be preferable to call zlog_backtrace_sigsafe here, since @@ -122,9 +122,9 @@ zstrdup (int type, const char *str) alloc_inc (type); return dup; } - + #ifdef MEMORY_LOG -static struct +static struct { const char *name; long alloc; @@ -187,7 +187,7 @@ mtype_zrealloc (const char *file, int line, int type, void *ptr, size_t size) } /* Important function. */ -void +void mtype_zfree (const char *file, int line, int type, void *ptr) { mstat[type].t_free++; @@ -205,13 +205,13 @@ mtype_zstrdup (const char *file, int line, int type, const char *str) mstat[type].c_strdup++; memory = zstrdup (type, str); - + mtype_log ("xstrdup", memory, file, line, type); return memory; } #else -static struct +static struct { char *name; long alloc; @@ -231,7 +231,7 @@ alloc_dec (int type) { mstat[type].alloc--; } - + /* Looking up memory status from vty interface. */ #include "vector.h" #include "vty.h" @@ -329,7 +329,7 @@ show_memory_mallinfo (struct vty *vty) { struct mallinfo minfo = mallinfo(); char buf[MTYPE_MEMSTR_LEN]; - + vty_out (vty, "System allocator statistics:%s", VTY_NEWLINE); vty_out (vty, " Total heap allocated: %s%s", mtype_memstr (buf, MTYPE_MEMSTR_LEN, minfo.arena), @@ -373,11 +373,11 @@ DEFUN (show_memory_all, { struct mlist *ml; int needsep = 0; - + #ifdef HAVE_MALLINFO needsep = show_memory_mallinfo (vty); #endif /* HAVE_MALLINFO */ - + for (ml = mlists; ml->list; ml++) { if (needsep) @@ -516,7 +516,7 @@ memory_init (void) install_element (ENABLE_NODE, &show_memory_ospf6_cmd); install_element (ENABLE_NODE, &show_memory_isis_cmd); } - + /* Stats querying from users */ /* Return a pointer to a human friendly string describing * the byte count passed in. E.g: @@ -529,13 +529,13 @@ const char * mtype_memstr (char *buf, size_t len, unsigned long bytes) { unsigned int t, g, m, k; - + /* easy cases */ if (!bytes) return "0 bytes"; if (bytes == 1) return "1 byte"; - + if (sizeof (unsigned long) >= 8) /* Hacked to make it not warn on ILP32 machines * Shift will always be 40 at runtime. See below too */ @@ -545,11 +545,11 @@ mtype_memstr (char *buf, size_t len, unsigned long bytes) g = bytes >> 30; m = bytes >> 20; k = bytes >> 10; - + if (t > 10) { /* The shift will always be 39 at runtime. - * Just hacked to make it not warn on 'smaller' machines. + * Just hacked to make it not warn on 'smaller' machines. * Static compiler analysis should mean no extra code */ if (bytes & (1UL << (sizeof (unsigned long) >= 8 ? 39 : 0))) @@ -576,7 +576,7 @@ mtype_memstr (char *buf, size_t len, unsigned long bytes) } else snprintf (buf, len, "%ld bytes", bytes); - + return buf; } diff --git a/lib/memory.h b/lib/memory.h index 42eb5cae..037efef2 100644 --- a/lib/memory.h +++ b/lib/memory.h @@ -32,7 +32,7 @@ struct mlist { struct memory_list *list; const char *name; }; - + #include "lib/memtypes.h" extern struct mlist mlists[]; @@ -60,6 +60,8 @@ extern struct mlist mlists[]; #define XSTRDUP(mtype, str) zstrdup ((mtype), (str)) #endif /* MEMORY_LOG */ +#define SIZE(t,n) (sizeof(t) * (n)) + /* Prototypes of memory function. */ extern void *zmalloc (int type, size_t size); extern void *zcalloc (int type, size_t size); @@ -69,7 +71,7 @@ extern char *zstrdup (int type, const char *str); extern void *mtype_zmalloc (const char *file, int line, int type, size_t size); -extern void *mtype_zcalloc (const char *file, int line, int type, +extern void *mtype_zcalloc (const char *file, int line, int type, size_t num, size_t size); extern void *mtype_zrealloc (const char *file, int line, int type, void *ptr, diff --git a/lib/memtypes.c b/lib/memtypes.c index 05d93225..e7269206 100644 --- a/lib/memtypes.c +++ b/lib/memtypes.c @@ -1,6 +1,6 @@ /* * Memory type definitions. This file is parsed by memtypes.awk to extract - * MTYPE_ and memory_list_.. information in order to autogenerate + * MTYPE_ and memory_list_.. information in order to autogenerate * memtypes.h. * * The script is sensitive to the format (though not whitespace), see @@ -16,8 +16,8 @@ struct memory_list memory_list_lib[] = { { MTYPE_TMP, "Temporary memory" }, { MTYPE_STRVEC, "String vector" }, - { MTYPE_VECTOR, "Vector" }, - { MTYPE_VECTOR_INDEX, "Vector index" }, + { MTYPE_VECTOR, "Vector structure" }, + { MTYPE_VECTOR_BODY, "Vector body" }, { MTYPE_LINK_LIST, "Link List" }, { MTYPE_LINK_NODE, "Link Node" }, { MTYPE_THREAD, "Thread" }, @@ -75,7 +75,7 @@ struct memory_list memory_list_lib[] = { -1, NULL }, }; -struct memory_list memory_list_zebra[] = +struct memory_list memory_list_zebra[] = { { MTYPE_RTADV_PREFIX, "Router Advertisement Prefix" }, { MTYPE_VRF, "VRF" }, diff --git a/lib/vector.c b/lib/vector.c index 7c148628..8268c830 100644 --- a/lib/vector.c +++ b/lib/vector.c @@ -1,6 +1,9 @@ -/* Generic vector interface routine +/* Generic vector interface routine -- functions * Copyright (C) 1997 Kunihiro Ishiguro * + * 24-Nov-2009 -- extended to add a number of new operations on vectors. + * Copyright (C) 2009 Chris Hall (GMCH), Highwayman + * * This file is part of GNU Zebra. * * GNU Zebra is free software; you can redistribute it and/or modify it @@ -16,7 +19,7 @@ * You should have received a copy of the GNU General Public License * along with GNU Zebra; see the file COPYING. If not, write to the Free * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA - * 02111-1307, USA. + * 02111-1307, USA. */ #include <zebra.h> @@ -24,87 +27,757 @@ #include "vector.h" #include "memory.h" -/* Initialize vector : allocate memory and return vector. */ +/* Vectors are implemented as a structure which points to an array of pointers + * to vector items. That array -- the body of the vector -- can change size, + * and therefore may move around in memory. + * + * The vector structure may be statically allocated, embedded in another + * structure, or allocated dynamically. In any case the vector operations + * require the address of the vector structure -- see typedef for vector. + * + * Vector items are accessed by index, fetching and storing pointers to + * those items. Can also push and pop items. + * + * A vector has a known (logical) end position. Everything beyond the end is + * defined to be NULL. When a vector is initialised it is set empty. + * + * At any given moment the vector body has a limit on the number of items it + * can accommodate (the physical end). + * + * A vector will grow to accommodate what is put into it. Adding items beyond + * the (logical) end moves it. Adding items beyond the (physical) limit causes + * the body to be extended to suit, and to leave some spare space for future + * expansion. + * + * While the vector is small (see VECTOR_LIMIT_DOUBLE_MAX) the body will grow by + * doubling in size. When it is larger, it grows to be multiples of + * VECTOR_LIMIT_DOUBLE_MAX. + * + * Deleting items reduces the (logical) end position, but does NOT release + * memory -- the (physical) limit is not changed. + * + * To release memory: vector_chop will release everything beyond the current + * end; vector_decant will create a new body of exactly the current size, + * releasing the old body; vector_discard will release everything beyond a + * given position. + * + * NB: you can set a vector item to be NULL. If you set a vector item beyond + * the current end, NULL items are inserted in the vector. + * + * NB: when setting a vector item it is the caller's responsibility to + * deallocate any pre-existing value of the item. + * + * NB: when deleting items it is also the caller's responsibility to deallocate + * any values that require it. + * + * Implementation Notes + * + * Everything beyond the (logical) end is implicitly NULL. + * + * Actual memory between (logical) end and (physical) limit is UNDEFINED. So + * when advancing the end some care has to be taken to ensure that any new + * items in the vector are either set to something or cleared to NULL. + * + * It would have been possible to ensure that everything between end and limit + * is cleared to NULL, but that is more work -- in particular it creates work + * when it is not always required. + */ + +#define P_ITEMS_SIZE(n) SIZE(p_vector_item, n) +/*============================================================================== + * Initialisation, allocation, reset etc. + */ + +/* Initialise a brand new vector, setting it empty. + * + * Allocates vector structure if none given -- that is, if v == NULL. + * + * If size is given as zero, no body is allocated, otherwise body of exactly + * the required size is allocated. + * + * NB: discards any existing vector body -- so it is the caller's responsibility + * to release any existing body, and any items in that body. + */ vector -vector_init (unsigned int size) +vector_init_new(vector v, unsigned int size) { - vector v = XCALLOC (MTYPE_VECTOR, sizeof (struct _vector)); + if (v == NULL) + v = XCALLOC(MTYPE_VECTOR, sizeof(struct vector)) ; + else + memset(v, 0, sizeof(struct vector)) ; - /* allocate at least one slot */ - if (size == 0) - size = 1; + if (size != 0) + { + v->p_items = XMALLOC(MTYPE_VECTOR_BODY, P_ITEMS_SIZE(size)) ; + v->limit = size ; + } ; - v->alloced = size; - v->active = 0; - v->index = XCALLOC (MTYPE_VECTOR_INDEX, sizeof (void *) * size); - return v; -} + return v ; +} ; +/* Initialize vector : allocate memory and return vector. + * allocates body with at least 1 entry. + */ +vector +vector_init (unsigned int size) +{ + return vector_init_new(NULL, size ? size : 1) ; /* at least 1 entry */ +} ; + +/* Basic: free the given vector structure. NB: Orphans any existing body !! */ void vector_only_wrapper_free (vector v) { XFREE (MTYPE_VECTOR, v); } +/* Basic: free the vector body. */ void -vector_only_index_free (void *index) +vector_only_index_free (void *body) { - XFREE (MTYPE_VECTOR_INDEX, index); + XFREE (MTYPE_VECTOR_BODY, body); } +/* Basic: free the vector body and the vector structure. */ void vector_free (vector v) { - XFREE (MTYPE_VECTOR_INDEX, v->index); + XFREE (MTYPE_VECTOR_BODY, v->p_items); XFREE (MTYPE_VECTOR, v); } +/* Re-Initialize vector (or create new one), setting it empty. + * + * Allocates vector structure if none given -- that is, if v == NULL. + * + * If size is given as zero, no body is allocated, but any existing body is + * retained. (vector_reset() will discard body.) + * + * Otherwise ensures existing body is at least the required size, or a body + * of exactly the required size is allocated. + * + * NB: when re-initialising an existing vector it is the caller's + * responsibility to release any vector item values *before* doing this. + * */ +vector +vector_re_init(vector v, unsigned int size) +{ + if ((v == NULL) || (v->p_items == NULL)) + return vector_init_new(v, size) ; + + v->end = 0 ; + + if (v->limit < size) + { + v->p_items = XREALLOC(MTYPE_VECTOR_BODY, v->p_items, P_ITEMS_SIZE(size)) ; + v->limit = size ; + } ; + + return v ; +} ; + +/* Free the vector body, and free the vector structure or reset it. + * + * Return NULL if releases vector, otherwise the address of the vector. + * + * NB: it is the caller's responsibility to release any vector item values + * *before* doing this. + */ +vector +vector_reset(vector v, int free_structure) +{ + if (v == NULL) + return NULL ; /* allow for already freed vector */ + + if (v->p_items != NULL) + XFREE(MTYPE_VECTOR_BODY, v->p_items) ; + + if (free_structure) + { + XFREE(MTYPE_VECTOR, v) ; + return NULL ; + } + else + return vector_init_new(v, 0) ; +} ; + +/* Pop item from vector, stepping past any NULLs. + * + * If vector is empty, free the body and, if required, the vector structure. + * + * Useful for emptying out and discarding a vector: + * + * while ((p_v = vector_ream_out(v, 1))) + * ... do what's required to release the item p_v + * + * Returns NULL if vector was empty and has now been freed as required. + */ +p_vector_item +vector_ream(vector v, int free_structure) +{ + p_vector_item p_v ; + + if (v == NULL) + return NULL ; + + while (v->end != 0) + { + p_v = v->p_items[--v->end] ; + if (p_v != NULL) + return p_v ; /* return non-NULL item */ + } ; + + /* vector is empty: free the body, and (if required) the vector structure. */ + vector_reset(v, free_structure) ; + + return NULL ; /* signals end */ +} ; + +/*============================================================================== + * Inserting and deleting items. + */ + +/* Insert item in vector, before item at given position + * Move items and extend vector as required. + */ +void +vector_insert_item(vector v, vector_index i, void* p_v) +{ + if ((i == v->end) && (i < v->limit)) + ++v->end ; + else + vector_insert(v, i, 1) ; + + v->p_items[i] = (p_vector_item)p_v ; +} ; + +/* Insert item in vector at given position with rider: + * + * rider < 0 -- insert before the item at the given position + * rider == 0 -- insert at the given position -- REPLACING any existing value + * rider > 0 -- insert after the item at the given position + * + * NB: when an item is replaced, it is the caller's responsibility to release + * any memory used by the item, if required. + * + * Move items and extend vector as required. + */ +void +vector_insert_item_here(vector v, vector_index i, int rider, + p_vector_item p_v) +{ + if (rider == 0) + return vector_set_item(v, i, p_v) ; + + if (rider > 0) + ++i ; /* insert before next item */ + vector_insert_item(v, i, p_v) ; +} ; + +/* Delete item from vector. + * + * Move items as required. Reduces number of items in the vector (unless + * the item in question is beyond the end of the vector !) + * + * NB: it is the caller's responsibility to release memory used by any + * current value of the item, if required. + * + * NB: does NOT change the size of the vector body. + */ +p_vector_item +vector_delete_item(vector v, vector_index i) +{ + p_vector_item p_e ; + if (i < v->end) + { + p_e = v->p_items[i] ; /* pick up the current value */ + if (i != (v->end - 1)) + vector_delete(v, i, 1) ; + else + v->end = i ; + return p_e ; + } + else + return NULL ; +} ; + +/*============================================================================== + * Moving items within vector. + */ + +/* Move item in vector from source position to destination position. + * Moves intervening items up or down as required. + * Extends vector to include the destination, if required. + * A source item beyond the end of the vector is implicitly NULL. + */ +void +vector_move_item(vector v, vector_index i_dst, vector_index i_src) +{ + p_vector_item* pp_s ; + p_vector_item* pp_d ; + p_vector_item p_e ; + + vector_index old_end = v->end ; + + /* Worry about whether both source and destination exist. */ + if (i_dst >= old_end) + { + vector_insert(v, i_dst, 1) ; /* ensure destination exists */ + if (i_src >= old_end) + return ; /* both were beyond the end */ + } + else if (i_src >= old_end) + { + i_src = old_end ; /* clamp to just beyond last */ + vector_insert(v, i_src, 1) ; /* create empty entry */ + } ; + + if (i_dst == i_src) /* avoid work and edge case */ + return ; + + /* Both src and dst are within the vector and src != dst */ + pp_s = &v->p_items[i_src] ; /* address of src entry */ + pp_d = &v->p_items[i_dst] ; /* address of dst entry */ + p_e = *pp_s ; /* pick up item to move */ + if (i_src < i_dst) + memmove(pp_s, pp_s+1, P_ITEMS_SIZE(i_dst - i_src)) ; + else + memmove(pp_d+1, pp_d, P_ITEMS_SIZE(i_src - i_dst)) ; + *pp_d = p_e ; /* put down the item to move */ +} ; + +/* Move item in vector to given position with rider: + * + * rider < 0 -- move to before the item at the given position + * rider == 0 -- move to replace item at the given position + * rider > 0 -- insert after the item at the given position + * + * NB: it is the caller's responsibility to release the any existing value + * that will be replaced. + * + * Move items and extend vector as required. + */ +void +vector_move_item_here(vector v, vector_index i_dst, int rider, + vector_index i_src) +{ + if (rider != 0) + { + if (rider > 0) + ++i_dst ; + vector_move_item(v, i_dst, i_src) ; + } + else + { + /* to replace: copy and then delete. */ + vector_set_item(v, i_dst, vector_get_item(v, i_src)) ; + vector_delete_item(v, i_src) ; + } ; +} ; + +/* Reverse vector: reverse the order of items in the vector. + */ +void +vector_reverse(vector v) +{ + if (v != NULL) + vector_part_reverse(v, 0, v->end) ; +} ; + +/* Reverse portion of vector. + */ +void +vector_part_reverse(vector v, vector_index i, unsigned int n) +{ + vector_index j ; + + if (v == NULL) + return ; + + if ((i + n) > v->limit) + vector_extend(v, i + n) ; /* ensure portion exists */ + + if (n <= 1) + return ; + + j = i + n - 1 ; /* j > i, because n > 1 */ + do + { + p_vector_item p_i = v->p_items[i] ; + v->p_items[i++] = v->p_items[j] ; + v->p_items[j--] = p_i ; + } while (j > i) ; +} ; + +/*============================================================================== + * Copying, moving and appending entire vectors. + */ + +static void vector_new_limit(vector v, vector_index new_end) ; + +/* Shallow vector copy -- copies pointers to item values, not the values. */ +/* Creates a new vector. */ +/* NB: copies whole body, including stuff beyond (logical) end ! */ +/* TODO: is this behaviour required ? */ vector vector_copy (vector v) { - unsigned int size; - vector new = XCALLOC (MTYPE_VECTOR, sizeof (struct _vector)); + vector new = vector_init_new(NULL, v->limit) ; - new->active = v->active; - new->alloced = v->alloced; + new->end = v->end; - size = sizeof (void *) * (v->alloced); - new->index = XCALLOC (MTYPE_VECTOR_INDEX, size); - memcpy (new->index, v->index, size); + if (v->limit > 0) + memcpy(new->p_items, v->p_items, P_ITEMS_SIZE(v->limit)) ; return new; } -/* Check assigned index, and if it runs short double index pointer */ -void -vector_ensure (vector v, unsigned int num) +/* Shallow vector copy -- copies pointers to item values, not the values. + * Creates a new vector or re-initialises an existing one. + * + * NB: creates new vector with same limit as existing one, but copies only + * the known items (ie up to end, not up to limit). + * + * NB: if re-initialising existing vector, it is the caller's responsibility + * to release any existing items if that is required. + * + * NB: if re-initialising existing vector, it is the caller's responsibility + * to ensure the vector structure is currently valid. + * + * NB: do NOT try copying a vector to itself !! + */ +vector +vector_copy_here(vector dst, vector src) { - if (v->alloced > num) - return; + assert((src != NULL) && (src != dst)) ; + + dst = vector_re_init(dst, src->limit) ; - v->index = XREALLOC (MTYPE_VECTOR_INDEX, - v->index, sizeof (void *) * (v->alloced * 2)); - memset (&v->index[v->alloced], 0, sizeof (void *) * v->alloced); - v->alloced *= 2; - - if (v->alloced <= num) - vector_ensure (v, num); + dst->end = src->end; + + if (src->end > 0) + memcpy(dst->p_items, src->p_items, P_ITEMS_SIZE(src->end)) ; + + return dst ; +} ; + +/* Vector move -- moves body of vector. + * Creates a new vector or re-initialises an existing one. + * Leaves the source vector empty -- does not release the structure. + * + * NB: if re-initialising existing vector, it is the caller's responsibility + * to release any existing items if that is required. + * + * NB: if re-initialising existing vector, it is the caller's responsibility + * to ensure the vector structure is currently valid. + * + * NB: do NOT try moving a vector to itself !! + */ +vector +vector_move_here(vector dst, vector src) +{ + assert((src != NULL) && (src != dst)) ; + + if (dst != NULL) + dst = vector_reset(dst, 0) ; /* Reset to deallocate any existing body */ + else + dst = vector_init_new(dst, 0) ; /* Create new structure sans body. */ + + *dst = *src ; /* Copy the vector structure */ + + vector_init_new(src, 0) ; /* Set empty, forgetting body */ + + return dst ; } -/* This function only returns next empty slot index. It dose not mean +/* Shallow vector copy append -- copies pointers to item values, not the values. + * Appends copied pointers to the destination vector. + * Creates a new destination vector if required. + * + * NB: Can append to self. + */ +vector +vector_copy_append(vector dst, vector src) +{ + vector_index new_end ; + + assert(src != NULL) ; + + if (dst != NULL) + { + new_end = dst->end + src->end ; + if (new_end > dst->limit) + vector_new_limit(dst, new_end) ; + } + else + { + new_end = src->end ; + vector_init_new(dst, new_end) ; + } ; + + if (src->end) + memcpy(&dst->p_items[dst->end], src->p_items, P_ITEMS_SIZE(src->end)) ; + + dst->end = new_end ; /* Done last, allows for append to self ! */ + return dst ; +} ; + +/* Vector move append -- moves pointers to item values. + * Appends moved pointers to the destination vector. + * Creates a new destination vector if required (dst == NULL). + * Leaves the source vector empty -- does not release the structure. + * + * NB: do NOT try moving a vector to itself !! + */ +vector +vector_move_append(vector dst, vector src) +{ + assert((src != NULL) && (src != dst)) ; + + if ((dst == NULL) || (dst->end == 0)) + return vector_move_here(dst, src) ; /* Easy way to do it if dst empty */ + + vector_copy_append(dst, src) ; /* Extend dst and copy src */ + vector_init_new(src, 0) ; /* Set empty, forgetting body */ + + return dst ; +} ; + +/*============================================================================== + * Portmanteau splice/extract/replace function. + * + * All take a portion of 'src' vector and: + * + * splice: + * + * a) replace a portion of the 'dst' vector by a portion of the 'src' vector + * copying the replaced portion of the 'dst' vector to the 'to' vector + * b) either: leave 'src' unchanged -- copy + * or: remove the stuff copied from 'src' -- move + * + * Arguments: to_copy -- true + * to -- vector, or NULL => allocate new vector + * dst -- vector + * i_dst -- start of portion to replace + * n_dst -- length of portion to replace. 0 => insertion. + * src -- vector, or NULL => nothing to copy/move + * i_src -- start of portion to copy/move + * n_src -- length of portion to copy/move. 0 => nothing. + * src_move -- true => move, otherwise copy. + * + * Returns: the (possibly new) 'to' vector + * + * NB: 'to', 'dst' and 'src' must be distinct vectors. + * + * extract: + * + * a) copy a portion of the 'src' vector to the 'to' vector + * c) either: leave 'src' unchanged -- copy + * or: remove the stuff copied from 'src' -- move + * + * Arguments: to_copy -- true + * to -- vector, or NULL => allocate new vector + * dst -- NULL + * i_dst -- ignored + * n_dst -- ignored + * src -- vector, or NULL => nothing to copy/move + * i_src -- start of portion to copy/move + * n_src -- length of portion to copy/move. 0 => nothing. + * src_move -- true => move, otherwise copy. + * + * Returns: the (possibly new) 'to' vector + * + * NB: 'to' and 'src' must be distinct vectors. + * + * replace: + * + * a) replace a portion of the 'dst' vector by a portion of the 'src' vector + * b) either: leave 'src' unchanged -- copy + * or: remove the stuff copied from 'src' -- move + * + * Arguments: to_copy -- false + * to -- ignored + * dst -- vector + * i_dst -- start of portion to replace + * n_dst -- length of portion to replace. 0 => insertion. + * src -- vector, or NULL => nothing to copy/move + * i_src -- start of portion to copy/move + * n_src -- length of portion to copy/move. 0 => nothing. + * src_move -- true => move, otherwise copy. + * + * Returns: original 'to' argument + * + * NB: 'dst' and 'src' must be distinct vectors. + * + * All copies are shallow -- pointers to item values are copied, not the values. + * + * NB: any existing contents of the 'to' vector are discarded. + * + * NB: it is the caller's responsibility to release memory allocated to any + * items which are discarded in these operations. + * + * NB: for splice and replace, the resulting destination vector will be at + * least i_dst + n_src long. (Even if is copying actual or implied NULLs + * from the source.) + * + * NB: where new vectors are created, they will be of exactly the required size. + * + * NB: where an existing vector is reused, it is the caller's responsibility + * to ensure the vector structure is currently valid (by vector_init_new() + * or by ensuring it is zeroized). + */ +vector +vector_sak(int to_copy, vector to, + vector dst, vector_index i_dst, unsigned int n_dst, + vector src, vector_index i_src, unsigned int n_src, int src_move) +{ + int dst_replace ; /* true => replace portion of 'dst' */ + + vector_index new_dst_end = 0 ; /* new end of dst */ + + unsigned int n_dst_nulls ; /* number of implicit NULLs to add */ + unsigned int n_dst_move ; /* number of items to move up or down */ + unsigned int n_src_real ; /* number of items to really copy */ + unsigned int n_src_nulls ; /* number of implicit NULLs to "copy" */ + + assert((to == NULL) || (dst == NULL) || (to != dst)) ; + assert((src == NULL) || (dst == NULL) || (src != dst)) ; + + /* Worry about how much we really have in the source vector. */ + + n_src_real = n_src ; /* assume all real */ + n_src_nulls = 0 ; /* so no NULLs to "copy" */ + + if (n_src != 0) + { + if ((src == NULL) || (i_src >= src->end)) + n_src_real = 0 ; + else if ((i_src + n_src) > src->end) + n_src_real = src->end - i_src ; + n_src_nulls = n_src - n_src_real ; + } ; + + /* If no 'dst' vector, then this is an extract. */ + + n_dst_move = 0 ; /* assume nothing to move */ + n_dst_nulls = 0 ; /* assume no NULLs to add */ + + if (dst == NULL) + /* For extract: set up dst, i_dst and n_dst so that can copy to the */ + /* 'to' vector as if from 'dst'. */ + { + dst_replace = 0 ; /* no replacement operation */ + dst = src ; /* copy from here */ + i_dst = i_src ; + n_dst = n_src_real ; + } + else + /* Reduce n_dst to the number of actual items to be replaced. */ + /* */ + /* Calculate the new end of 'dst'. */ + { + dst_replace = 1 ; /* have replacement to do */ + if (i_dst >= dst->end) + /* If i_dst is beyond the end of 'dst', then there is nothing */ + /* to replace (so set n_dst == 0). Will be adding n_src items */ + /* at i_dst -- so new end must be i_dst + n_src. */ + { + n_dst_nulls = i_dst - dst->end ; /* fill from end to i_dst */ + n_dst = 0 ; /* nothing to replace */ + new_dst_end = i_dst + n_src ; /* all beyond current end */ + } + else + /* If i_dst + n_dst is beyond the end of 'dst', reduce n_dst to */ + /* number of items up to the end. */ + /* Will remove n_dst items and insert n_src, so end will move */ + /* by n_src - n_dst. */ + { + if ((i_dst + n_dst) > dst->end) + n_dst = dst->end - i_dst ; /* what we actually replace */ + else if (n_dst != n_src) + n_dst_move = dst->end - (i_dst + n_dst) ; + /* what we move up or down */ + + new_dst_end = dst->end + n_src - n_dst ; + /* end depends on amount added */ + /* & amount actually replaced */ + } ; + } ; + + /* Copy portion of 'dst' (or of 'src') to 'to', if required. */ + /* */ + /* Have arranged: n_dst -- number of items to copy, all existent */ + /* dst -- vector to copy from -- if n_dst > 0 */ + /* i_dst -- first item to copy -- if n_dst > 0 */ + + if (to_copy) + { + to = vector_re_init(to, n_dst) ; /* reinitialise or create */ + to->end = n_dst ; + if (n_dst > 0) + memcpy(to->p_items, &dst->p_items[i_dst], P_ITEMS_SIZE(n_dst)) ; + } ; + + /* Replace portion of 'dst' by portion of 'src', if required. */ + /* */ + /* Have arranged: */ + /* */ + /* new_dst_end -- end of dst once dust settles */ + /* n_dst_nulls -- number of NULLs to insert at dst->end to fill up */ + /* to i_dst (when i_dst is beyond old end.) */ + /* n_dst_move -- number of items in dst to move up or down to */ + /* leave n_src item hole at i_dst to fill in. */ + /* n_src_real -- number of real src items at i_src to copy to dst */ + /* at i_dst. */ + /* n_src_nulls -- number of nulls to add to fill to i_dst + n_src. */ + + if (dst_replace) + { + if (new_dst_end > dst->limit) /* extend body if required */ + vector_new_limit(dst, new_dst_end) ; + + if (n_dst_nulls > 0) + memset(&dst->p_items[dst->end], 0, P_ITEMS_SIZE(n_dst_nulls)) ; + if (n_dst_move > 0) + memmove(&dst->p_items[i_dst + n_dst], &dst->p_items[i_dst + n_src], + P_ITEMS_SIZE(n_dst_move)) ; + if (n_src_real > 0) + memcpy(&dst->p_items[i_dst], &src->p_items[i_src], + P_ITEMS_SIZE(n_src_real)) ; + if (n_src_nulls > 0) + memset(&dst->p_items[i_dst + n_src_real], 0, + P_ITEMS_SIZE(n_src_nulls)) ; + dst->end = new_dst_end ; + } ; + + /* Delete portion of 'src', if required (and have 'src' !) */ + + if (src_move && (n_src_real != 0)) + vector_delete(src, i_src, n_src_real) ; + + /* Done -- return 'to' vector as promised. */ + + return to ; +} ; + +/*============================================================================== + * Legacy Vector Operations + */ + +/* This function only returns next empty slot index. It does not mean the slot's index memory is assigned, please call vector_ensure() - after calling this function. */ + after calling this function. + + Index returned is <= current (logical) end. +*/ int vector_empty_slot (vector v) { - unsigned int i; - - if (v->active == 0) - return 0; + vector_index i; - for (i = 0; i < v->active; i++) - if (v->index[i] == 0) - return i; + for (i = 0; i < v->end; i++) + if (v->p_items[i] == NULL) + break ; return i; } @@ -113,77 +786,436 @@ vector_empty_slot (vector v) int vector_set (vector v, void *val) { - unsigned int i; - - i = vector_empty_slot (v); - vector_ensure (v, i); + vector_index i; + i = vector_empty_slot(v) ; /* NB: i <= v->end */ + if (i == v->end) + i = vector_extend_by_1(v) ; - v->index[i] = val; - - if (v->active <= i) - v->active = i + 1; + v->p_items[i] = val; return i; } /* Set value to specified index slot. */ int -vector_set_index (vector v, unsigned int i, void *val) +vector_set_index (vector v, vector_index i, void *val) { vector_ensure (v, i); - - v->index[i] = val; - - if (v->active <= i) - v->active = i + 1; - + v->p_items[i] = val; return i; } /* Look up vector. */ -void * -vector_lookup (vector v, unsigned int i) +p_vector_item +vector_lookup (vector v, vector_index i) { - if (i >= v->active) + if (i >= v->end) return NULL; - return v->index[i]; + return v->p_items[i]; } /* Lookup vector, ensure it. */ -void * -vector_lookup_ensure (vector v, unsigned int i) +p_vector_item +vector_lookup_ensure (vector v, vector_index i) { vector_ensure (v, i); - return v->index[i]; + return v->p_items[i]; } /* Unset value at specified index slot. */ void -vector_unset (vector v, unsigned int i) +vector_unset (vector v, vector_index i) { - if (i >= v->alloced) - return; + vector_index j ; + if (i >= v->end) + return; /* Everything beyond or at end is implicitly NULL */ - v->index[i] = NULL; + v->p_items[i] = NULL; - if (i + 1 == v->active) - { - v->active--; - while (i && v->index[--i] == NULL && v->active--) + /* See if everything ahead of 'i' is also NULL. */ + j = i ; + while (++j < v->end) + if (v->p_items[j] != NULL) + return ; /* Finished if anything ahead 'i' is not NULL */ + + /* Everything from 'i' onwards is NULL. + * Step backwards across any NULLs and then set the new end. + */ +#if 0 + v->end--; + while (i && v->p_items[--i] == NULL && v->end--) ; /* Is this ugly ? */ - } +#endif + while ((i != 0) && (v->p_items[i - 1] == NULL)) + --i ; + + v->end = i ; } -/* Count the number of not emplty slot. */ -unsigned int +/* Count the number of not empty slots. */ +vector_index vector_count (vector v) { - unsigned int i; + vector_index i; unsigned count = 0; - for (i = 0; i < v->active; i++) - if (v->index[i] != NULL) + for (i = 0; i < v->end; i++) + if (v->p_items[i] != NULL) count++; return count; } + +/*============================================================================== + * Sorting and Searching vector. + */ + +/* Sort the given vector. + * + * NB: the comparison function receives a pointer to the pointer to the + * vector item's value. + * + * NB: if there are NULL items in the vector, the comparison function MUST + * be ready for them. + */ +void +vector_sort(vector v, vector_sort_cmp* cmp) +{ + if (v->end <= 1) + return ; /* Stop dead if 0 or 1 items */ + + typedef int qsort_cmp(const void*, const void*) ; + + qsort(v->p_items, v->end, sizeof(p_vector_item), (qsort_cmp*)cmp) ; +} ; + +/* Perform binary search on the given vector. + * + * The vector MUST be sorted in the order implied by the comparison function + * given. The vector need not contain unique values, but this search makes + * no effort to select any particular instance of a sequence of equals. + * + * Returns: + * + * result == 0: found an equal value. + * index returned is of first entry found which is equal to + * the value sought. There may be other equal values, before + * and/or after this one in the vector. + * + * result == +1: value not found and vector not empty. + * index returned is of the largest entry whose value is less + * than the value sought. + * (The value sought belongs after this point.) + * + * result == -1: value is less than everything in the vector, or the + * vector is empty. + * index returned is 0 + * + * NB: The comparison function takes arguments which are: + * + * const void** pointer to pointer to value being searched for. + * const void** pointer to pointer to vector item to compare with + * + * The value being searched for need not be in the same form as a vector + * item. However, if it is then the same comparison function can be used + * to sort and search. + * + * NB: if there are NULL items in the vector, the comparison function MUST + * be ready for them. + */ +vector_index +vector_bsearch(vector v, vector_bsearch_cmp* cmp, const void* p_val, + int* result) +{ + vector_index il, iv, ih ; + int c ; + + if (v->end <= 1) + { + *result = (v->end == 0) ? -1 : cmp(&p_val, (const void**)&v->p_items[0]) ; + return 0 ; /* Stop dead if 0 or 1 items */ + } ; + + /* We have at least two items. */ + il = 0 ; + ih = v->end - 1 ; + + /* Pick off the edge cases: >= last and <= first. */ + if ((c = cmp(&p_val, (const void**)&v->p_items[ih])) >= 0) + { + *result = c ; /* 0 => found. +1 => val > last */ + return ih ; /* return high index. */ + } ; + if ((c = cmp(&p_val, (const void**)&v->p_items[il])) <= 0) + { + *result = c ; /* 0 => found. -1 => val < first */ + return il ; /* return low index. */ + } + + /* Now binary chop. We know that item[il] < val < item[ih] */ + /* We also know that il < ih */ + while (1) + { + iv = (il + ih) / 2 ; + if (iv == il) /* true if (ih == il+1) */ + { + *result = +1 ; + return il ; /* return il: item[il] < val < item[il+1] */ + } ; + /* We now know that il < iv < ih */ + c = cmp(&p_val, (const void**)&v->p_items[iv]) ; + if (c == 0) + { + *result = 0 ; + return iv ; /* found !! */ + } + if (c < 0) + ih = iv ; /* step down iv > il, so new ih > il */ + else + il = iv ; /* step up iv < ih, so new il < ih */ + } ; +} ; + +/*============================================================================== + * Mechanics for adding/deleting items and managing the vector (logical) end + * and (physical) limit. + */ + +/* Extract the LS bit of unsigned integer 'x'. */ +#define lsbit(x) ((x) & ((~(x)) + 1)) +/* Round 'x' up to a multiple of 'm' */ +#define multiple(x, m) ((((x) + (m) - 1) / (m)) * (m)) + +/* Set new limit to suit new end for given vector. + * + * The new limit will be at least: VECTOR_LIMIT_MIN. + * + * While the vector is relatively small, the limit is doubled until there + * is at least 1/8 of the new vector free. + * + * Beyond VECTOR_LIMIT_DOUBLE_MAX, however, the limit is set to the + * smallest multiple of VECTOR_LIMIT_DOUBLE_MAX which gives at least + * VECTOR_LIMIT_SLACK_MIN free entries beyond the new end. + * + * This is an attempt to balance the cost of repeated reallocations of + * memory against the cost of possible wasted space at the end of the + * vector. + * + * NB: the new_limit depends entirely on the new end position. (Current + * end position is ignored.) + * + * NB: the new limit may be less than the current limit, in which case the + * vector body is reduced in size. + * + * Except for any size set when the vector is initialised, the vector body + * size will be a power of 2 or a multiple of VECTOR_LIMIT_DOUBLE_MAX. + * (Vectors are regular in their habits, which may help the memory allocator). + * + * TODO: what to do if calculation of new_limit overflows, or calculation + * of P_ITEMS_SIZE will ? + */ +static void +vector_new_limit(vector v, vector_index new_end) +{ + vector_index old_limit = v->limit ; + vector_index new_limit ; + + if (new_end > ((VECTOR_LIMIT_DOUBLE_MAX * 7) / 8)) + { + new_limit = multiple(new_end + VECTOR_LIMIT_SLACK_MIN, + VECTOR_LIMIT_DOUBLE_MAX) ; + } + else + { + /* Want the new_limit to be a power of 2. */ + /* If the old_limit was a power of 2, start from there. */ + /* Otherwise start from a power of 2 less than new_end: either the */ + /* minimum value or a value mid way to VECTOR_LIMIT_DOUBLE_MAX. */ + if ( (old_limit != 0) && (old_limit == lsbit(old_limit)) + && (new_end >= old_limit) ) + new_limit = old_limit ; + else + new_limit = (new_end < VECTOR_LIMIT_MID) ? VECTOR_LIMIT_MIN + : VECTOR_LIMIT_MID ; + while (new_end > ((new_limit * 7) / 8)) + new_limit *= 2 ; + } ; + + v->p_items = + XREALLOC(MTYPE_VECTOR_BODY, v->p_items, P_ITEMS_SIZE(new_limit)) ; + + v->limit = new_limit ; +} ; + +/* Extend vector and set new (logical) end. + * + * Extends body if required. + * Ensures everything between old and new end is set NULL. + * + * NB: expects new end > old end, but copes with new end <= old end. + */ +void +vector_extend(vector v, vector_index new_end) +{ + vector_index old_end = v->end ; + + if (new_end > v->limit) + vector_new_limit(v, new_end) ; + v->end = new_end ; + + if (new_end > old_end) + memset(&v->p_items[old_end], 0, P_ITEMS_SIZE(new_end - old_end)) ; +} ; + +/* Insert entries into vector: insert 'n' NULL entries at location 'i'. + * + * Updates end (and limit) to be at least 'i' + 'n'. + * (So if 'i' < end then end becomes end + 'n', else end becomes 'i' + 'n'.) + */ +void +vector_insert(vector v, vector_index i, unsigned int n) +{ + vector_index old_end, new_end ; + unsigned int n_above ; + + /* If i < old end, then we are inserting n NULLs, and need + * to shuffle at least one item up. + * else we are setting new end to i + n and need to NULL + * fill from old end to the new end. + */ + old_end = v->end ; + if (i < old_end) + { + if (n == 0) + return ; /* give up now if not inserting anything */ + n_above = old_end - i ; /* number of items to shuffle up.. >= 1 */ + new_end = old_end + n ; + } + else + { + n_above = 0 ; /* nothing to shuffle up. */ + new_end = i + n ; + i = old_end ; /* where to zeroize from */ + n = new_end - old_end ; /* how much to zeroize */ + } ; + + /* Now we extend the body if we need to. */ + if (new_end > v->limit) + vector_new_limit(v, new_end) ; + v->end = new_end ; + + if (n_above > 0) + memmove(&v->p_items[i + n], &v->p_items[i], P_ITEMS_SIZE(n_above)) ; + + memset(&v->p_items[i], 0, P_ITEMS_SIZE(n)) ; +} ; + +/* Delete items from vector: delete 'n' items at location 'i'. + * + * Does nothing if 'i' is beyond current end of vector or if 'n' == 0. + * + * Deletes from 'i' to end if less than 'n' items to the end. + * + * NB: does NOT change the size of the body. + * + * NB: it is the caller's responsibility to have released any memory allocated + * for the items that are being deleted. +*/ +void +vector_delete(vector v, vector_index i, unsigned int n) +{ + vector_index old_end, new_end ; + + old_end = v->end ; + + if ((i >= old_end) || (n == 0)) + return ; + + /* If i + n < old_end, we have 1 or more items to keep and move down */ + if ((i + n) < old_end) + { + memmove(&v->p_items[i], &v->p_items[i + n], + P_ITEMS_SIZE(old_end - (i + n))) ; + new_end = old_end - n ; + } + else + { + new_end = i ; /* We are keeping nothing above 'i' */ + /* NB: new_end < old_end */ + } ; + + v->end = new_end ; /* account for stuff dropped */ +} ; + +/* Discard entries from vector: discard entries from location 'i' onwards. + * + * Releases memory from 'i' onwards. + * Releases the body altogether if this sets the vector empty ('i' == 0). + * Sets new end of vector iff 'i' < current end. + * + * Does nothing if 'i' is beyond current limit (physical end) of vector. + * + * NB: it is the caller's responsibility to have released any memory allocated + * for the items that are being discarded. +*/ +void +vector_discard(vector v, vector_index i) +{ + if (i >= v->limit) + return ; + + if (i == 0) + vector_reset(v, 0) ; /* reset, without releasing the structure */ + else + { + v->limit = i ; + if (i < v->end) + v->end = i ; + v->p_items = XREALLOC(MTYPE_VECTOR_BODY, v->p_items, P_ITEMS_SIZE(i)) ; + } ; +} ; + +/* Chop vector at the current (logical) end. + * + * Releases the body altogether if the vector is currently empty. +*/ +void +vector_chop(vector v) +{ + vector_index new_limit = v->end ; + + if (new_limit == 0) + vector_reset(v, 0) ; /* reset, without releasing the structure */ + else if (new_limit != v->limit) + { + v->limit = new_limit ; + v->p_items = XREALLOC(MTYPE_VECTOR_BODY, v->p_items, P_ITEMS_SIZE(new_limit)) ; + } ; +} ; + +/* Decant vector into a new body allocated to current logical size, and + * release the old body. + * + * Releases the body altogether if the vector is currently empty. +*/ +void +vector_decant(vector v) +{ + p_vector_item* p_old_body ; + vector_index new_limit = v->end ; + + if (new_limit == 0) + vector_reset(v, 0) ; /* reset, without releasing the structure */ + else + { + p_old_body = v->p_items ; + + vector_init_new(v, new_limit) ; /* initialise with new body */ + + memcpy(v->p_items, p_old_body, P_ITEMS_SIZE(new_limit)) ; + /* copy the old body across */ + v->end = new_limit ; + + XFREE(MTYPE_VECTOR_BODY, p_old_body) ; + } ; +} ; diff --git a/lib/vector.h b/lib/vector.h index 6b27fd96..3a7e7ca5 100644 --- a/lib/vector.h +++ b/lib/vector.h @@ -1,7 +1,9 @@ -/* - * Generic vector interface header. +/* Generic vector interface header. * Copyright (C) 1997, 98 Kunihiro Ishiguro * + * 24-Nov-2009 -- extended to add a number of new operations on vectors. + * Copyright (C) 2009 Chris Hall (GMCH), Highwayman + * * This file is part of GNU Zebra. * * GNU Zebra is free software; you can redistribute it and/or modify it @@ -17,47 +19,271 @@ * You should have received a copy of the GNU General Public License * along with GNU Zebra; see the file COPYING. If not, write to the Free * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA - * 02111-1307, USA. + * 02111-1307, USA. */ #ifndef _ZEBRA_VECTOR_H #define _ZEBRA_VECTOR_H -/* struct for vector */ -struct _vector +/* Macro in case there are particular compiler issues. */ +#ifndef Inline + #define Inline static inline +#endif + +/* types and struct for vector */ +/* */ +/* NB: an entirely zero structure represents an entirely empty vector. */ +/* */ +/* TODO: could force vector_index to be 32 bits ? */ + +typedef void* p_vector_item ; +typedef unsigned int vector_index ; + +struct vector { - unsigned int active; /* number of active slots */ - unsigned int alloced; /* number of allocated slot */ - void **index; /* index to data */ + p_vector_item *p_items ; /* pointer to array of vector item pointers */ + vector_index end ; /* number of "active" item entries */ + vector_index limit ; /* number of allocated item entries */ }; -typedef struct _vector *vector; +typedef struct vector *vector; + +/* Values that control the allocation of the vector body. */ +/* NB: these must all be powers of 2. */ + +/* The body, when allocated, will have at least this many entries. */ +#define VECTOR_LIMIT_MIN 8 +/* When the body grows, it doubles in size, until it is this big. */ +/* After that it grows in units of this much. */ +#define VECTOR_LIMIT_DOUBLE_MAX 2048 +/* "Midway" between VECTOR_LIMIT_MIN and VECTOR_LIMIT_DOUBLE_MAX. */ +#define VECTOR_LIMIT_MID 128 +/* When growing in units of VECTOR_LIMIT_DOUBLE_MAX, this is the */ +/* minimum slack space to leave after the logical end of the vector. */ +#define VECTOR_LIMIT_SLACK_MIN ((VECTOR_LIMIT_DOUBLE_MAX) / 8) + +/* (Sometimes) useful macros. */ -#define VECTOR_MIN_SIZE 1 +/* Reference item at given index. */ +/* NB: does not guarantee the item is "active" (that is: within the */ +/* (logical) vector) -- but see vector_ensure. */ +/* Returns address of vector item. */ +/* See: VECTOR_ITEMS() for walking items in a vector. */ +/* See: vector_get_item(), which is preferable. */ +#define vector_slot(V,I) ((V)->p_items[(I)]) + +/* Number of "active" item entries -- (logical) end of the vector. */ +/* Note that this differs from vector_count() as this count will */ +/* include any NULL items. */ +#define vector_active(V) ((V)->end) + +/* TODO: fix where this is used to poke around inside a vector */ +#define VECTOR_INDEX p_items + +/* To walk all items in a vector: + * + * vector_index i ; + * xxxxx* p_v ; + * + * for (VECTOR_ITEMS(v, p_v, i)) + * { + * ... i is index of current item + * ... p_v is address of current item value -- may be NULL + * } ; + * + * ... i is number of items in vector (including any NULLs) + */ +#define VECTOR_ITEMS(v, p_v, i)\ + (i) = 0 ;\ + (i) < (v)->end ? (((p_v) = (void*)(v)->p_items[i]), 1) \ + : (((p_v) = NULL), 0) ;\ + ++(i) -/* (Sometimes) usefull macros. This macro convert index expression to - array expression. */ -/* Reference slot at given index, caller must ensure slot is active */ -#define vector_slot(V,I) ((V)->index[(I)]) -/* Number of active slots. - * Note that this differs from vector_count() as it the count returned - * will include any empty slots +/*============================================================================== + * Prototypes. */ -#define vector_active(V) ((V)->active) -/* Prototypes. */ extern vector vector_init (unsigned int size); -extern void vector_ensure (vector v, unsigned int num); +Inline void vector_ensure(vector v, vector_index i) ; extern int vector_empty_slot (vector v); extern int vector_set (vector v, void *val); -extern int vector_set_index (vector v, unsigned int i, void *val); -extern void vector_unset (vector v, unsigned int i); -extern unsigned int vector_count (vector v); +extern int vector_set_index (vector v, vector_index i, void *val); +extern void vector_unset (vector v, vector_index i); +extern vector_index vector_count (vector v); extern void vector_only_wrapper_free (vector v); extern void vector_only_index_free (void *index); extern void vector_free (vector v); extern vector vector_copy (vector v); -extern void *vector_lookup (vector, unsigned int); -extern void *vector_lookup_ensure (vector, unsigned int); +extern void *vector_lookup (vector, vector_index); +extern void *vector_lookup_ensure (vector, vector_index); + +extern vector vector_init_new(vector v, unsigned int size) ; +extern vector vector_re_init(vector v, unsigned int size) ; +extern vector vector_reset(vector v, int free_structure) ; +extern p_vector_item vector_ream(vector v, int free_structure) ; + +/* Reset vector and free the vector structure. */ +#define vector_reset_free(v) vector_reset(v, 1) +/* Reset vector but free the heap structure. */ +#define vector_reset_keep(v) vector_reset(v, 0) +/* Ream out vector and free the vector structure. */ +#define vector_ream_free(v) vector_ream(v, 1) +/* Ream out vector but keep the vector structure. */ +#define vector_ream_keep(v) vector_ream(v, 0) + +Inline vector_index vector_end(vector v) ; +Inline int vector_is_empty(vector v) ; + +Inline p_vector_item vector_get_item(vector v, vector_index i) ; +Inline p_vector_item vector_get_first_item(vector v) ; +Inline p_vector_item vector_get_last_item(vector v) ; +Inline void vector_set_item(vector v, vector_index i, p_vector_item p_v) ; + +extern void vector_insert_item(vector v, vector_index i, p_vector_item p_v) ; +extern void vector_insert_item_here(vector v, vector_index i, int rider, + p_vector_item p_v) ; +extern void vector_move_item(vector v, vector_index dst, vector_index src) ; +extern void vector_move_item_here(vector v, vector_index dst, int rider, + vector_index src) ; +extern p_vector_item vector_delete_item(vector v, vector_index i) ; +extern void vector_reverse(vector v) ; +extern void vector_part_reverse(vector v, vector_index i, unsigned int n) ; + +Inline void vector_push_item(vector v, p_vector_item p_v) ; +Inline p_vector_item vector_pop_item(vector v) ; + +extern void vector_insert(vector v, vector_index i, unsigned int n) ; +extern void vector_delete(vector v, vector_index i, unsigned int n) ; + +typedef int vector_bsearch_cmp(const void** pp_val, const void** item) ; +vector_index vector_bsearch(vector v, vector_bsearch_cmp* cmp, + const void* p_val, int* result) ; +typedef int vector_sort_cmp(const void** a, const void** b) ; +void vector_sort(vector v, vector_sort_cmp* cmp) ; + +extern vector vector_copy_here(vector dst, vector src) ; +extern vector vector_move_here(vector dst, vector src) ; +extern vector vector_copy_append(vector dst, vector src) ; +extern vector vector_move_append(vector dst, vector src) ; + +#define vector_copy_extract(to, src, i_src, n_src) \ + vector_sak(1, to, NULL, 0, 0, src, i_src, n_src, 0) +#define vector_move_extract(to, src, i_src, n_src) \ + vector_sak(1, to, NULL, 0, 0, src, i_src, n_src, 1) +#define vector_copy_splice(to, dst, i_dst, n_dst, src, i_src, n_src) \ + vector_sak(1, to, dst, i_dst, n_dst, src, i_src, n_src, 0) +#define vector_move_splice(to, dst, i_dst, n_dst, src, i_src, n_src) \ + vector_sak(1, to, dst, i_dst, n_dst, src, i_src, n_src, 1) +#define vector_copy_replace(dst, i_dst, n_dst, src, i_src, n_src) \ + vector_sak(0, NULL, dst, i_dst, n_dst, src, i_src, n_src, 0) +#define vector_move_replace(dst, i_dst, n_dst, src, i_src, n_src) \ + vector_sak(0, NULL, dst, i_dst, n_dst, src, i_src, n_src, 1) + +extern vector vector_sak(int to_copy, vector to, + vector dst, vector_index i_dst, unsigned int n_dst, + vector src, vector_index i_src, unsigned int n_src, int src_move) ; + +extern void vector_discard(vector v, vector_index i) ; +extern void vector_chop(vector v) ; +extern void vector_decant(vector v) ; + +Inline vector_index vector_extend_by_1(vector v) ; +extern void vector_extend(vector v, vector_index new_end) ; + +/*============================================================================== + * The inline functions: + */ + +/* Extend vector by one item at the end, which is about to be set. */ +/* Returns index of new least item in the vector. */ +/* NB: if left unset, the item may be UNDEFINED. */ +Inline vector_index +vector_extend_by_1(vector v) +{ + vector_index i = v->end ; + + if (i < v->limit) + return v->end++ ; /* simple if we have room */ + + vector_extend(v, i + 1) ; /* the hard way */ + return i ; +} ; + +/* Ensure given index is "active". */ +/* Adjusts logical and physical end of the vector as required, filling */ +/* with NULLs upto any new logical end. */ +Inline void +vector_ensure(vector v, vector_index i) +{ + if (i < v->end) /* trivial if within vector */ + return ; + if ((i == v->end) && (i < v->limit)) /* simple if end and have room */ + v->p_items[v->end++] = NULL ; /* set NULL for complete safety */ + else + vector_extend(v, i + 1) ; /* do it the hard way */ +} ; + +/* Return index of end of vector (index of last item + 1) */ +Inline vector_index +vector_end(vector v) +{ + return v->end ; +} ; + +/* Returns whether vector is empty or not. */ +Inline int +vector_is_empty(vector v) +{ + return (v->end == 0) ; +} ; + +/* Access functions -- Inline for obvious reasons. */ + +/* Get pointer to item. Returns NULL if accessing beyond end. */ +Inline p_vector_item +vector_get_item(vector v, vector_index i) +{ + return (i < v->end) ? v->p_items[i] : NULL ; +} ; + +/* Get pointer to first item. Returns NULL if vector empty. */ +Inline p_vector_item +vector_get_first_item(vector v) +{ + return (v->end != 0) ? v->p_items[0] : NULL ; +} ; + +/* Get pointer to last item. Returns NULL if vector empty. */ +Inline p_vector_item +vector_get_last_item(vector v) +{ + return (v->end != 0) ? v->p_items[v->end - 1] : NULL ; +} ; + +/* Set item value in vector. Extend vector if required. */ +/* NB: it is the caller's responsibility to release memory used by any */ +/* current value of the item, if required. */ +Inline void +vector_set_item(vector v, vector_index i, void* p_v) +{ + vector_ensure(v, i) ; + v->p_items[i] = (p_vector_item)p_v ; +} ; + +/* Push value onto vector, extending as required. */ +Inline void +vector_push_item(vector v, void* p_v) +{ + vector_index i = vector_extend_by_1(v) ; + v->p_items[i] = (p_vector_item)p_v ; +} ; + +/* Pop value from vector. Returns NULL if vector is empty. */ +/* NB: does NOT change the size of the vector body. */ +Inline p_vector_item +vector_pop_item(vector v) +{ + return (v->end > 0) ? v->p_items[--v->end] : NULL ; +} ; #endif /* _ZEBRA_VECTOR_H */ @@ -17,7 +17,7 @@ * You should have received a copy of the GNU General Public License * along with GNU Zebra; see the file COPYING. If not, write to the Free * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA - * 02111-1307, USA. + * 02111-1307, USA. */ #include <zebra.h> @@ -40,7 +40,7 @@ #include <arpa/telnet.h> /* Vty events */ -enum event +enum event { VTY_SERV, VTY_READ, @@ -57,7 +57,7 @@ static void vty_event (enum event, int, struct vty *); /* Extern host structure from command.c */ extern struct host host; - + /* Vector which store each vty structure. */ static vector vtyvec; @@ -89,7 +89,7 @@ static u_char restricted_mode = 0; /* Integrated configuration file path */ char integrate_default[] = SYSCONFDIR INTEGRATE_DEFAULT_CONFIG; - + /* VTY standard output function. */ int vty_out (struct vty *vty, const char *format, ...) @@ -209,7 +209,7 @@ void vty_time_print (struct vty *vty, int cr) { char buf [25]; - + if (quagga_timestamp(0, buf, sizeof(buf)) == 0) { zlog (NULL, LOG_INFO, "quagga_timestamp error"); @@ -382,7 +382,7 @@ vty_auth (struct vty *vty, char *buf) vty_out (vty, "%% Bad passwords, too many failures!%s", VTY_NEWLINE); vty->status = VTY_CLOSE; } - else + else { /* AUTH_ENABLE_NODE */ vty->fail = 0; @@ -423,7 +423,7 @@ vty_command (struct vty *vty, char *buf) protocolname = zlog_proto_names[zlog_default->protocol]; else protocolname = zlog_proto_names[ZLOG_NONE]; - + #ifdef CONSUMED_TIME_CHECK GETRUSAGE(&after); if ((realtime = thread_consumed_time(&after, &before, &cputime)) > @@ -455,7 +455,7 @@ vty_command (struct vty *vty, char *buf) return ret; } - + static const char telnet_backward_char = 0x08; static const char telnet_space_char = ' '; @@ -646,7 +646,7 @@ vty_forward_word (struct vty *vty) { while (vty->cp != vty->length && vty->buf[vty->cp] != ' ') vty_forward_char (vty); - + while (vty->cp != vty->length && vty->buf[vty->cp] == ' ') vty_forward_char (vty); } @@ -746,7 +746,7 @@ vty_delete_char (struct vty *vty) vty->length--; memmove (&vty->buf[vty->cp], &vty->buf[vty->cp + 1], size - 1); vty->buf[vty->length] = '\0'; - + if (vty->node == AUTH_NODE || vty->node == AUTH_ENABLE_NODE) return; @@ -776,7 +776,7 @@ vty_kill_line (struct vty *vty) int size; size = vty->length - vty->cp; - + if (size == 0) return; @@ -871,7 +871,7 @@ vty_complete_command (struct vty *vty) vector_set (vline, '\0'); matched = cmd_complete_command (vline, vty, &ret); - + cmd_free_strvec (vline); vty_out (vty, "%s", VTY_NEWLINE); @@ -985,7 +985,7 @@ vty_describe_command (struct vty *vty) vline = vector_init (1); vector_set (vline, '\0'); } - else + else if (isspace ((int) vty->buf[vty->length - 1])) vector_set (vline, '\0'); @@ -1004,7 +1004,7 @@ vty_describe_command (struct vty *vty) vty_out (vty, "%% There is no matched command.%s", VTY_NEWLINE); goto out; break; - } + } /* Get width of command string. */ width = 0; @@ -1033,7 +1033,7 @@ vty_describe_command (struct vty *vty) { if (desc->cmd[0] == '\0') continue; - + if (strcmp (desc->cmd, command_cr) == 0) { desc_cr = desc; @@ -1220,7 +1220,7 @@ vty_telnet_option (struct vty *vty, unsigned char *buf, int nbytes) vty->iac_sb_in_progress = 1; return 0; break; - case SE: + case SE: { if (!vty->iac_sb_in_progress) return 0; @@ -1364,7 +1364,7 @@ vty_read (struct thread *thread) vty->status = VTY_CLOSE; } - for (i = 0; i < nbytes; i++) + for (i = 0; i < nbytes; i++) { if (buf[i] == IAC) { @@ -1378,7 +1378,7 @@ vty_read (struct thread *thread) vty->iac = 0; } } - + if (vty->iac_sb_in_progress && !vty->iac) { if (vty->sb_len < sizeof(vty->sb_buf)) @@ -1396,7 +1396,7 @@ vty_read (struct thread *thread) i += ret; continue; } - + if (vty->status == VTY_MORE) { @@ -1722,10 +1722,10 @@ vty_accept (struct thread *thread) (buf = sockunion_su2str (&su))); free (buf); close (vty_sock); - + /* continue accepting connections */ vty_event (VTY_SERV, accept_sock, NULL); - + prefix_free (p); return 0; @@ -1744,24 +1744,24 @@ vty_accept (struct thread *thread) (buf = sockunion_su2str (&su))); free (buf); close (vty_sock); - + /* continue accepting connections */ vty_event (VTY_SERV, accept_sock, NULL); - + prefix_free (p); return 0; } } #endif /* HAVE_IPV6 */ - + prefix_free (p); on = 1; - ret = setsockopt (vty_sock, IPPROTO_TCP, TCP_NODELAY, + ret = setsockopt (vty_sock, IPPROTO_TCP, TCP_NODELAY, (char *) &on, sizeof (on)); if (ret < 0) - zlog (NULL, LOG_INFO, "can't set sockopt to vty_sock : %s", + zlog (NULL, LOG_INFO, "can't set sockopt to vty_sock : %s", safe_strerror (errno)); vty = vty_create (vty_sock, &su); @@ -1821,7 +1821,7 @@ vty_serv_sock_addrinfo (const char *hostname, unsigned short port) } ret = listen (sock, 3); - if (ret < 0) + if (ret < 0) { close (sock); /* Avoid sd leak. */ continue; @@ -1854,7 +1854,7 @@ vty_serv_sock_family (const char* addr, unsigned short port, int family) #ifdef HAVE_IPV6 case AF_INET6: naddr=&su.sin6.sin6_addr; -#endif +#endif } if(naddr) @@ -1889,7 +1889,7 @@ vty_serv_sock_family (const char* addr, unsigned short port, int family) /* Listen socket under queue 3. */ ret = listen (accept_sock, 3); - if (ret < 0) + if (ret < 0) { zlog (NULL, LOG_WARNING, "can't listen socket"); close (accept_sock); /* Avoid sd leak. */ @@ -1913,7 +1913,7 @@ vty_serv_un (const char *path) struct sockaddr_un serv; mode_t old_mask; struct zprivs_ids_t ids; - + /* First of all, unlink existing socket */ unlink (path); @@ -1957,7 +1957,7 @@ vty_serv_un (const char *path) umask (old_mask); zprivs_get_ids(&ids); - + if (ids.gid_vty > 0) { /* set group of socket */ @@ -1981,7 +1981,7 @@ vtysh_accept (struct thread *thread) int client_len; struct sockaddr_un client; struct vty *vty; - + accept_sock = THREAD_FD (thread); vty_event (VTYSH_SERV, accept_sock, NULL); @@ -2005,7 +2005,7 @@ vtysh_accept (struct thread *thread) close (sock); return -1; } - + #ifdef VTYSH_DEBUG printf ("VTY shell accept\n"); #endif /* VTYSH_DEBUG */ @@ -2228,11 +2228,11 @@ vty_read_file (FILE *confp) vty->fd = 0; /* stdout */ vty->type = VTY_TERM; vty->node = CONFIG_NODE; - + /* Execute configuration file */ ret = config_from_file (vty, confp); - if ( !((ret == CMD_SUCCESS) || (ret == CMD_ERR_NOTHING_TODO)) ) + if ( !((ret == CMD_SUCCESS) || (ret == CMD_ERR_NOTHING_TODO)) ) { switch (ret) { @@ -2243,7 +2243,7 @@ vty_read_file (FILE *confp) fprintf (stderr, "There is no such command.\n"); break; } - fprintf (stderr, "Error occured during reading below line.\n%s\n", + fprintf (stderr, "Error occured during reading below line.\n%s\n", vty->buf); vty_close (vty); exit (1); @@ -2261,7 +2261,7 @@ vty_use_backup_config (char *fullpath) int tmp, sav; int c; char buffer[512]; - + fullpath_sav = malloc (strlen (fullpath) + strlen (CONF_BACKUP_EXT) + 1); strcpy (fullpath_sav, fullpath); strcat (fullpath_sav, CONF_BACKUP_EXT); @@ -2273,7 +2273,7 @@ vty_use_backup_config (char *fullpath) fullpath_tmp = malloc (strlen (fullpath) + 8); sprintf (fullpath_tmp, "%s.XXXXXX", fullpath); - + /* Open file to configuration write. */ tmp = mkstemp (fullpath_tmp); if (tmp < 0) @@ -2291,13 +2291,13 @@ vty_use_backup_config (char *fullpath) free (fullpath_tmp); return NULL; } - + while((c = read (sav, buffer, 512)) > 0) write (tmp, buffer, c); - + close (sav); close (tmp); - + if (chmod(fullpath_tmp, CONFIGFILE_MASK) != 0) { unlink (fullpath_tmp); @@ -2305,12 +2305,12 @@ vty_use_backup_config (char *fullpath) free (fullpath_tmp); return NULL; } - + if (link (fullpath_tmp, fullpath) == 0) ret = fopen (fullpath, "r"); unlink (fullpath_tmp); - + free (fullpath_sav); free (fullpath_tmp); return ret; @@ -2332,7 +2332,7 @@ vty_read_config (char *config_file, if (! IS_DIRECTORY_SEP (config_file[0])) { getcwd (cwd, MAXPATHLEN); - tmp = XMALLOC (MTYPE_TMP, + tmp = XMALLOC (MTYPE_TMP, strlen (cwd) + strlen (config_file) + 2); sprintf (tmp, "%s/%s", cwd, config_file); fullpath = tmp; @@ -2346,13 +2346,13 @@ vty_read_config (char *config_file, { fprintf (stderr, "%s: failed to open configuration file %s: %s\n", __func__, fullpath, safe_strerror (errno)); - + confp = vty_use_backup_config (fullpath); if (confp) fprintf (stderr, "WARNING: using backup configuration file!\n"); else { - fprintf (stderr, "can't open configuration file [%s]\n", + fprintf (stderr, "can't open configuration file [%s]\n", config_file); exit(1); } @@ -2391,7 +2391,7 @@ vty_read_config (char *config_file, { fprintf (stderr, "%s: failed to open configuration file %s: %s\n", __func__, config_default_dir, safe_strerror (errno)); - + confp = vty_use_backup_config (config_default_dir); if (confp) { @@ -2404,7 +2404,7 @@ vty_read_config (char *config_file, config_default_dir); exit (1); } - } + } else fullpath = config_default_dir; } @@ -2414,7 +2414,7 @@ vty_read_config (char *config_file, fclose (confp); host_config_set (fullpath); - + if (tmp) XFREE (MTYPE_TMP, fullpath); } @@ -2426,7 +2426,7 @@ vty_log (const char *level, const char *proto_str, { unsigned int i; struct vty *vty; - + if (!vtyvec) return; @@ -2451,7 +2451,7 @@ vty_log_fixed (const char *buf, size_t len) /* vty may not have been initialised */ if (!vtyvec) return; - + iov[0].iov_base = (void *)buf; iov[0].iov_len = len; iov[1].iov_base = (void *)"\r\n"; @@ -2488,7 +2488,7 @@ vty_config_unlock (struct vty *vty) } return vty->config; } - + /* Master of the threads. */ static struct thread_master *master; @@ -2522,7 +2522,7 @@ vty_event (enum event event, int sock, struct vty *vty) { if (vty->t_timeout) thread_cancel (vty->t_timeout); - vty->t_timeout = + vty->t_timeout = thread_add_timer (master, vty_timeout, vty, vty->v_timeout); } break; @@ -2538,13 +2538,13 @@ vty_event (enum event event, int sock, struct vty *vty) } if (vty->v_timeout) { - vty->t_timeout = + vty->t_timeout = thread_add_timer (master, vty_timeout, vty, vty->v_timeout); } break; } } - + DEFUN (config_who, config_who_cmd, "who", @@ -2833,14 +2833,14 @@ vty_config_write (struct vty *vty) /* exec-timeout */ if (vty_timeout_val != VTY_TIMEOUT_DEFAULT) - vty_out (vty, " exec-timeout %ld %ld%s", + vty_out (vty, " exec-timeout %ld %ld%s", vty_timeout_val / 60, vty_timeout_val % 60, VTY_NEWLINE); /* login */ if (no_password_check) vty_out (vty, " no login%s", VTY_NEWLINE); - + if (restricted_mode != restricted_mode_default) { if (restricted_mode_default) @@ -2848,7 +2848,7 @@ vty_config_write (struct vty *vty) else vty_out (vty, " anonymous restricted%s", VTY_NEWLINE); } - + vty_out (vty, "!%s", VTY_NEWLINE); return CMD_SUCCESS; @@ -2939,7 +2939,7 @@ vty_shell_serv (struct vty *vty) void vty_init_vtysh () { - vtyvec = vector_init (VECTOR_MIN_SIZE); + vtyvec = vector_init (0); } /* Install vty's own commands like `who' command. */ @@ -2949,12 +2949,12 @@ vty_init (struct thread_master *master_thread) /* For further configuration read, preserve current directory. */ vty_save_cwd (); - vtyvec = vector_init (VECTOR_MIN_SIZE); + vtyvec = vector_init (0); master = master_thread; /* Initilize server thread vector. */ - Vvty_serv_thread = vector_init (VECTOR_MIN_SIZE); + Vvty_serv_thread = vector_init (0); /* Install bgp top node. */ install_node (&vty_node, vty_config_write); |