From ce6be7afd4d10b542f9cce8634d6bdd81754f775 Mon Sep 17 00:00:00 2001 From: nicm Date: Mon, 18 Mar 2019 11:58:40 +0000 Subject: Make array options a sparse tree instead of an array of char * and remove the size limit. --- options.c | 162 ++++++++++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 111 insertions(+), 51 deletions(-) (limited to 'options.c') diff --git a/options.c b/options.c index 9ea5c118..6a7c37d6 100644 --- a/options.c +++ b/options.c @@ -30,6 +30,23 @@ * a red-black tree. */ +struct options_array_item { + u_int index; + char *value; + RB_ENTRY(options_array_item) entry; +}; +RB_HEAD(options_array, options_array_item); +static int +options_array_cmp(struct options_array_item *a1, struct options_array_item *a2) +{ + if (a1->index < a2->index) + return (-1); + if (a1->index > a2->index) + return (1); + return (0); +} +RB_GENERATE_STATIC(options_array, options_array_item, entry, options_array_cmp); + struct options_entry { struct options *owner; @@ -40,10 +57,7 @@ struct options_entry { char *string; long long number; struct style style; - struct { - const char **array; - u_int arraysize; - }; + struct options_array array; }; RB_ENTRY(options_entry) entry; @@ -56,8 +70,6 @@ struct options { static struct options_entry *options_add(struct options *, const char *); -#define OPTIONS_ARRAY_LIMIT 1000 - #define OPTIONS_IS_STRING(o) \ ((o)->tableentry == NULL || \ (o)->tableentry->type == OPTIONS_TABLE_STRING) @@ -163,6 +175,9 @@ options_empty(struct options *oo, const struct options_table_entry *oe) o = options_add(oo, oe->name); o->tableentry = oe; + if (oe->type == OPTIONS_TABLE_ARRAY) + RB_INIT(&o->array); + return (o); } @@ -210,15 +225,11 @@ void options_remove(struct options_entry *o) { struct options *oo = o->owner; - u_int i; if (OPTIONS_IS_STRING(o)) - free((void *)o->string); - else if (OPTIONS_IS_ARRAY(o)) { - for (i = 0; i < o->arraysize; i++) - free((void *)o->array[i]); - free(o->array); - } + free(o->string); + else if (OPTIONS_IS_ARRAY(o)) + options_array_clear(o); RB_REMOVE(options_tree, &oo->tree, o); free(o); @@ -236,62 +247,79 @@ options_table_entry(struct options_entry *o) return (o->tableentry); } +static struct options_array_item * +options_array_item(struct options_entry *o, u_int idx) +{ + struct options_array_item a; + + a.index = idx; + return (RB_FIND(options_array, &o->array, &a)); +} + +static void +options_array_free(struct options_entry *o, struct options_array_item *a) +{ + free(a->value); + RB_REMOVE(options_array, &o->array, a); + free(a); +} + void options_array_clear(struct options_entry *o) { - if (OPTIONS_IS_ARRAY(o)) - o->arraysize = 0; + struct options_array_item *a, *a1; + + if (!OPTIONS_IS_ARRAY(o)) + return; + + RB_FOREACH_SAFE(a, options_array, &o->array, a1) + options_array_free(o, a); } const char * options_array_get(struct options_entry *o, u_int idx) { + struct options_array_item *a; + if (!OPTIONS_IS_ARRAY(o)) return (NULL); - if (idx >= o->arraysize) + a = options_array_item(o, idx); + if (a == NULL) return (NULL); - return (o->array[idx]); + return (a->value); } int options_array_set(struct options_entry *o, u_int idx, const char *value, int append) { - char *new; - u_int i; + struct options_array_item *a; + char *new; if (!OPTIONS_IS_ARRAY(o)) return (-1); - if (idx >= OPTIONS_ARRAY_LIMIT) - return (-1); - if (idx >= o->arraysize) { - o->array = xreallocarray(o->array, idx + 1, sizeof *o->array); - for (i = o->arraysize; i < idx + 1; i++) - o->array[i] = NULL; - o->arraysize = idx + 1; + a = options_array_item(o, idx); + if (value == NULL) { + if (a != NULL) + options_array_free(o, a); + return (0); } - new = NULL; - if (value != NULL) { - if (o->array[idx] != NULL && append) - xasprintf(&new, "%s%s", o->array[idx], value); + if (a == NULL) { + a = xcalloc(1, sizeof *a); + a->index = idx; + a->value = xstrdup(value); + RB_INSERT(options_array, &o->array, a); + } else { + free(a->value); + if (a != NULL && append) + xasprintf(&new, "%s%s", a->value, value); else new = xstrdup(value); + a->value = new; } - free((void *)o->array[idx]); - o->array[idx] = new; - return (0); -} - -int -options_array_size(struct options_entry *o, u_int *size) -{ - if (!OPTIONS_IS_ARRAY(o)) - return (-1); - if (size != NULL) - *size = o->arraysize; return (0); } @@ -310,37 +338,69 @@ options_array_assign(struct options_entry *o, const char *s) while ((next = strsep(&string, separator)) != NULL) { if (*next == '\0') continue; - for (i = 0; i < OPTIONS_ARRAY_LIMIT; i++) { - if (i >= o->arraysize || o->array[i] == NULL) + for (i = 0; i < UINT_MAX; i++) { + if (options_array_item(o, i) == NULL) break; } - if (i == OPTIONS_ARRAY_LIMIT) + if (i == UINT_MAX) break; options_array_set(o, i, next, 0); } free(copy); } +struct options_array_item * +options_array_first(struct options_entry *o) +{ + if (!OPTIONS_IS_ARRAY(o)) + return (NULL); + return (RB_MIN(options_array, &o->array)); +} + +struct options_array_item * +options_array_next(struct options_array_item *a) +{ + return (RB_NEXT(options_array, &o->array, a)); +} + +u_int +options_array_item_index(struct options_array_item *a) +{ + return (a->index); +} + +const char * +options_array_item_value(struct options_array_item *a) +{ + return (a->value); +} + +int +options_isarray(struct options_entry *o) +{ + return (OPTIONS_IS_ARRAY(o)); +} + int options_isstring(struct options_entry *o) { - if (o->tableentry == NULL) - return (1); return (OPTIONS_IS_STRING(o) || OPTIONS_IS_ARRAY(o)); } const char * options_tostring(struct options_entry *o, int idx, int numeric) { - static char s[1024]; - const char *tmp; + static char s[1024]; + const char *tmp; + struct options_array_item *a; if (OPTIONS_IS_ARRAY(o)) { if (idx == -1) return (NULL); - if ((u_int)idx >= o->arraysize || o->array[idx] == NULL) + a = options_array_item(o, idx); + if (a == NULL) return (""); - return (o->array[idx]); + return (a->value); } if (OPTIONS_IS_STYLE(o)) return (style_tostring(&o->style)); -- cgit