You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@httpd.apache.org by "Roy T. Fielding" <fi...@kiwi.ics.uci.edu> on 1999/01/02 09:40:40 UTC
fixing O(n^2) mem crap in mod_negotiation.c
I am most of the way finished on fixing the problem but am too tired
to do the rest tonight and haven't tested it yet. I could use some
feedback on the quality of this fix, at least in concept. It does compile.
Dean, this is your specialty, so I'd appreciate it if you could take
a look.
I'll probably get to the seven or so other O(n^2) similar cases tomorrow
and delete the merge_string_array() routine.
....Roy
Index: include/alloc.h
===================================================================
RCS file: /home/cvs/apache-1.3/src/include/alloc.h,v
retrieving revision 1.65
diff -u -r1.65 alloc.h
--- alloc.h 1999/01/01 19:04:38 1.65
+++ alloc.h 1999/01/02 08:29:39
@@ -149,6 +149,15 @@
API_EXPORT(array_header *) ap_append_arrays(pool *, const array_header *,
const array_header *);
+/* ap_array_pstrcat generates a new string from the pool containing
+ * the concatenated sequence of substrings referenced as elements within
+ * the array. The string will be empty if all substrings are empty or null,
+ * or if there are no elements in the array.
+ * If sep is non-NUL, it will be inserted between elements as a separator.
+ */
+API_EXPORT(char *) ap_array_pstrcat(pool *p, const array_header *arr,
+ const char sep);
+
/* copy_array copies the *entire* array. copy_array_hdr just copies
* the header, and arranges for the elements to be copied if (and only
* if) the code subsequently does a push or arraycat.
Index: main/alloc.c
===================================================================
RCS file: /home/cvs/apache-1.3/src/main/alloc.c,v
retrieving revision 1.104
diff -u -r1.104 alloc.c
--- alloc.c 1999/01/01 19:04:47 1.104
+++ alloc.c 1999/01/02 08:29:39
@@ -1047,6 +1047,60 @@
return res;
}
+/* ap_array_pstrcat generates a new string from the pool containing
+ * the concatenated sequence of substrings referenced as elements within
+ * the array. The string will be empty if all substrings are empty or null,
+ * or if there are no elements in the array.
+ * If sep is non-NUL, it will be inserted between elements as a separator.
+ */
+API_EXPORT(char *) ap_array_pstrcat(pool *p, const array_header *arr,
+ const char sep)
+{
+ char *cp, *res, **strpp;
+ int i, len;
+
+ if (arr->nelts <= 0) /* Empty table? Take the easy out. */
+ return (char *) ap_pcalloc(p, 1);
+
+ /* Pass one --- find length of required string */
+
+ len = 0;
+ for (i = 0, strpp = (char **) arr->elts; ; strpp += arr->elt_size) {
+ if (*strpp != NULL) {
+ len += strlen(*strpp);
+ }
+ if (++i >= arr->nelts)
+ break;
+ if (sep)
+ ++len;
+ }
+
+ /* Allocate the required string */
+
+ res = (char *) ap_palloc(p, len + 1);
+ cp = res;
+
+ /* Pass two --- copy the argument strings into the result space */
+
+ for (i = 0, strpp = (char **) arr->elts; ; strpp += arr->elt_size) {
+ if (*strpp != NULL) {
+ len = strlen(*strpp);
+ memcpy(cp, *strpp, len);
+ cp += len;
+ }
+ if (++i >= arr->nelts)
+ break;
+ if (sep)
+ *(cp++) = sep;
+ }
+
+ *cp = '\0';
+
+ /* Return the result string */
+
+ return res;
+}
+
/*****************************************************************
*
Index: modules/standard/mod_negotiation.c
===================================================================
RCS file: /home/cvs/apache-1.3/src/modules/standard/mod_negotiation.c,v
retrieving revision 1.91
diff -u -r1.91 mod_negotiation.c
--- mod_negotiation.c 1999/01/01 19:05:11 1.91
+++ mod_negotiation.c 1999/01/02 08:29:40
@@ -2259,14 +2259,20 @@
* choice response or 406 status body.
*/
-/* XXX: this is disgusting, this has O(n^2) behaviour! -djg */
-
static char *make_variant_list(request_rec *r, negotiation_state *neg)
{
+ array_header *arr;
int i;
- char *t;
+ const int max_vlist_array = (neg->avail_vars->nelts * 15) + 2;
+
+ /* In order to avoid O(n^2) memory copies in building the list,
+ * we preallocate a table with the maximum substrings possible,
+ * fill it with the variant list, and then concatenate the entire array.
+ */
+ arr = ap_make_array(r->pool, max_vlist_array, sizeof(char *));
- t = ap_pstrdup(r->pool, "Available variants:\n<ul>\n");
+ *((const char **) ap_push_array(arr)) = "Available variants:\n<ul>\n";
+
for (i = 0; i < neg->avail_vars->nelts; ++i) {
var_rec *variant = &((var_rec *) neg->avail_vars->elts)[i];
char *filename = variant->file_name ? variant->file_name : "";
@@ -2274,32 +2280,39 @@
char *description = variant->description ? variant->description : "";
/* The format isn't very neat, and it would be nice to make
- * the tags human readable (eg replace 'language en' with
- * 'English').
+ * the tags human readable (eg replace 'language en' with 'English').
+ * Note that if you change the number of substrings pushed, you also
+ * need to change the calculation of max_vlist_array above.
*/
- t = ap_pstrcat(r->pool, t, "<li><a href=\"", filename, "\">",
- filename, "</a> ", description, NULL);
+ *((const char **) ap_push_array(arr)) = "<li><a href=\"";
+ *((const char **) ap_push_array(arr)) = filename;
+ *((const char **) ap_push_array(arr)) = "\">";
+ *((const char **) ap_push_array(arr)) = filename;
+ *((const char **) ap_push_array(arr)) = "</a> ";
+ *((const char **) ap_push_array(arr)) = description;
+
if (variant->mime_type && *variant->mime_type) {
- t = ap_pstrcat(r->pool, t, ", type ", variant->mime_type, NULL);
+ *((const char **) ap_push_array(arr)) = ", type ";
+ *((const char **) ap_push_array(arr)) = variant->mime_type;
}
if (languages && languages->nelts) {
- t = ap_pstrcat(r->pool, t, ", language ",
- merge_string_array(r->pool, languages, ", "),
- NULL);
+ *((const char **) ap_push_array(arr)) = ", language ";
+ *((const char **) ap_push_array(arr)) = ap_array_pstrcat(r->pool,
+ languages, ',');
}
if (variant->content_charset && *variant->content_charset) {
- t = ap_pstrcat(r->pool, t, ", charset ", variant->content_charset,
- NULL);
+ *((const char **) ap_push_array(arr)) = ", charset ";
+ *((const char **) ap_push_array(arr)) = variant->content_charset;
}
if (variant->content_encoding) {
- t = ap_pstrcat(r->pool, t, ", encoding ",
- variant->content_encoding, NULL);
+ *((const char **) ap_push_array(arr)) = ", encoding ";
+ *((const char **) ap_push_array(arr)) = variant->content_encoding;
}
- t = ap_pstrcat(r->pool, t, "\n", NULL);
+ *((const char **) ap_push_array(arr)) = "\n";
}
- t = ap_pstrcat(r->pool, t, "</ul>\n", NULL);
+ *((const char **) ap_push_array(arr)) = "</ul>\n";
- return t;
+ return ap_array_pstrcat(r->pool, arr, '\0');
}
static void store_variant_list(request_rec *r, negotiation_state *neg)
Re: fixing O(n^2) mem crap in mod_negotiation.c
Posted by Dean Gaudet <dg...@arctic.org>.
On Sat, 2 Jan 1999, Roy T. Fielding wrote:
> I am most of the way finished on fixing the problem but am too tired
> to do the rest tonight and haven't tested it yet. I could use some
> feedback on the quality of this fix, at least in concept. It does compile.
> Dean, this is your specialty, so I'd appreciate it if you could take
> a look.
Looks cool :)
Dean