Make array options a sparse tree instead of an array of char * and

remove the size limit.

1 files changed, 111 insertions, 51 deletions

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));