a15c4a7f8c — curl

Subject

headers: avoid O(n^2) rescans in curl_easy_nextheader()

Binary

No binary (build failed)

Architecture & Compiler Flags

Architecture: x86_64-linux-gnu Compiler: gcc (Ubuntu 11.4.0-1ubuntu1~22.04.3) 11.4.0

—

Build Log

(log yok)

Commit Diff GitHub →

lib/headers.c +99 -12 lib/headers.h +2 -0 lib/urldata.h +4 -0 tests/data/test1945 +5 -3

lib/headers.c+99 -12

@@ -27,6 +27,7 @@
	#include "sendf.h"
	#include "curl_trc.h"
	#include "headers.h"
+	#include "strcase.h"

	#if !defined(CURL_DISABLE_HTTP) && !defined(CURL_DISABLE_HEADERS_API)

@@ -139,6 +140,80 @@ out:
	return hresult;
	}

+	struct nextheader_cache_entry {
+	struct Curl_header_store *header;
+	size_t order;
+	};
+
+	static int nextheader_compare(const void p1, const void p2)
+	{
+	const struct nextheader_cache_entry *e1 = p1;
+	const struct nextheader_cache_entry *e2 = p2;
+	const struct Curl_header_store *h1 = e1->header;
+	const struct Curl_header_store *h2 = e2->header;
+	const char *n1 = h1->name;
+	const char *n2 = h2->name;
+
+	while(n1 && n2) {
+	unsigned char c1 = (unsigned char)Curl_raw_toupper(*n1++);
+	unsigned char c2 = (unsigned char)Curl_raw_toupper(*n2++);
+	if(c1 != c2)
+	return c1 > c2 ? 1 : -1;
+	}
+	if(*n1)
+	return 1;
+	if(*n2)
+	return -1;
+	if(e1->order != e2->order)
+	return e1->order > e2->order ? 1 : -1;
+	return 0;
+	}
+
+	static bool nextheader_cache_build(struct Curl_easy *data,
+	unsigned int origin,
+	int request, size_t count)
+	{
+	struct nextheader_cache_entry *headers;
+	struct Curl_llist_node *e;
+	size_t i = 0;
+	size_t first;
+
+	headers = curlx_malloc(sizeof(headers) count);
+	if(!headers)
+	return FALSE;
+
+	for(e = Curl_llist_head(&data->state.httphdrs); e;
+	e = Curl_node_next(e)) {
+	struct Curl_header_store *hs = Curl_node_elem(e);
+	if((hs->type & origin) && (hs->request == request)) {
+	headers[i].header = hs;
+	headers[i].order = i;
+	i++;
+	}
+	}
+
+	qsort(headers, i, sizeof(*headers), nextheader_compare);
+	for(first = 0; first < i;) {
+	size_t last = first + 1;
+	size_t index;
+	while((last < i) &&
+	curl_strequal(headers[first].header->name,
+	headers[last].header->name))
+	last++;
+	for(index = first; index < last; index++) {
+	headers[index].header->nh_amount = last - first;
+	headers[index].header->nh_index = index - first;
+	}
+	first = last;
+	}
+	curlx_free(headers);
+
+	data->state.nh_origin = origin;
+	data->state.nh_request = request;
+	data->state.nh_count = count;
+	return TRUE;
+	}
+
	/* public API */
	struct curl_header curl_easy_nextheader(CURL curl,
	unsigned int origin,
@@ -156,6 +231,7 @@ struct curl_header curl_easy_nextheader(CURL curl,
	struct Curl_header_store *hs;
	size_t amount = 0;
	size_t index = 0;
+	size_t count;

	if(request > data->state.requests)
	goto out;
@@ -187,19 +263,29 @@ struct curl_header curl_easy_nextheader(CURL curl,
	goto out;

	hs = Curl_node_elem(pick);
-
-	/* count number of occurrences of this name within the mask and figure out
-	the index for the currently selected entry */
-	for(e = Curl_llist_head(&data->state.httphdrs); e; e = Curl_node_next(e)) {
-	struct Curl_header_store *check = Curl_node_elem(e);
-	if(curl_strequal(hs->name, check->name) &&
-	(check->request == request) &&
-	(check->type & origin))
-	amount++;
-	if(e == pick)
-	index = amount - 1;
+	count = Curl_llist_count(&data->state.httphdrs);
+
+	if(((data->state.nh_count == count) &&
+	(data->state.nh_origin == origin) &&
+	(data->state.nh_request == request)) \|\|
+	nextheader_cache_build(data, origin, request, count)) {
+	amount = hs->nh_amount;
+	index = hs->nh_index;
+	}
+	else {
+	/* count number of occurrences of this name within the mask and figure
+	out the index for the currently selected entry */
+	for(e = Curl_llist_head(&data->state.httphdrs); e;
+	e = Curl_node_next(e)) {
+	struct Curl_header_store *check = Curl_node_elem(e);
+	if(curl_strequal(hs->name, check->name) &&
+	(check->request == request) &&
+	(check->type & origin))
+	amount++;
+	if(e == pick)
+	index = amount - 1;
+	}
	}
-
	copy_header_external(hs, index, amount, pick,
	&data->state.headerout[1]);
	hd = &data->state.headerout[1];
@@ -316,6 +402,7 @@ CURLcode Curl_headers_push(struct Curl_easy data, const char header,
	static void headers_reset(struct Curl_easy *data)
	{
	Curl_llist_init(&data->state.httphdrs, NULL);
+	data->state.nh_count = 0;
	}

	struct hds_cw_collect_ctx {

lib/headers.h+2 -0

@@ -31,6 +31,8 @@ struct Curl_header_store {
	struct Curl_llist_node node;
	char name; / points into 'buffer' */
	char value; / points into 'buffer' */
+	size_t nh_amount; /* cached amount for curl_easy_nextheader() */
+	size_t nh_index; /* cached index for curl_easy_nextheader() */
	int request; /* 0 is the first request, then 1.. 2.. */
	unsigned char type; /* CURLH_* defines */
	char buffer[1]; /* this is the raw header blob */

lib/urldata.h+4 -0

@@ -594,6 +594,10 @@ struct UrlState {
	#endif
	struct Curl_llist httphdrs; /* received headers */
	struct curl_header headerout[2]; /* for external purposes */
+	/* curl_easy_nextheader() cache parameters */
+	unsigned int nh_origin;
+	int nh_request;
+	size_t nh_count; /* httphdrs count when the cache was filled */
	#endif
	#ifndef CURL_DISABLE_COOKIES
	struct curl_slist cookielist; / list of cookie files set by

tests/data/test1945+5 -3

@@ -18,6 +18,7 @@ Content-Length: 0
	Set-Cookie: onecookie=data;
	Set-Cookie: secondcookie=2data;
	Set-Cookie: cookie3=data3;
+	set-cookie: lowercase=data4;
	Location: /%TESTNUMBER0002

	</data>
@@ -68,9 +69,10 @@ Proxy-Connection: Keep-Alive
	Server == test with trailing space (1/2)
	Content-Type == text/html (0/1)
	Content-Length == 0 (0/1)
-	Set-Cookie == onecookie=data; (0/3)
-	Set-Cookie == secondcookie=2data; (1/3)
-	Set-Cookie == cookie3=data3; (2/3)
+	Set-Cookie == onecookie=data; (0/4)
+	Set-Cookie == secondcookie=2data; (1/4)
+	Set-Cookie == cookie3=data3; (2/4)
+	set-cookie == lowercase=data4; (3/4)
	Location == /19450002 (0/1)
	</stdout>
	</verify>