httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Roy T. Fielding" <field...@kiwi.ics.uci.edu>
Subject fixing O(n^2) mem crap in mod_negotiation.c
Date Sat, 02 Jan 1999 08:40:40 GMT
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)

Mime
View raw message