[PATCH BlueZ v1] sdp-xml: Use a queue to collect sequence members

[PATCH BlueZ v1] sdp-xml: Use a queue to collect sequence members

[Luiz Augusto von Dentz]

From: Luiz Augusto von Dentz <luiz.von.dentz@intel.com>

Appending a member to a sequence with sdp_seq_append() walks the
single-linked list to find its tail, so building a sequence is O(n^2).

This was previously worked around by caching the tail of the sequence in
struct sdp_xml_data, which required the caller to pick between appending
to the cached tail and initialising val.dataseq, and to keep the cache in
sync on every append.

Collect the members in a struct queue instead, which tracks its own tail,
and link them into val.dataseq once the element is closed. Appending is a
plain queue_push_tail(), and the queue is destroyed along with the rest
of the element so members that were never linked, such as on malformed
input, are still freed.

The sequence_on_squared() test stays at less than 0.1 seconds.

Assisted-by: Claude:claude-opus-5
---
 src/sdp-xml.c | 60 ++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 43 insertions(+), 17 deletions(-)

diff --git a/src/sdp-xml.c b/src/sdp-xml.c
index 5b448fe83410..bad9e289344f 100644
--- a/src/sdp-xml.c
+++ b/src/sdp-xml.c
@@ -25,6 +25,8 @@
 #include "bluetooth/sdp.h"
 #include "bluetooth/sdp_lib.h"
 
+#include "shared/queue.h"
+
 #include "sdp-xml.h"
 
 #define DBG(...) (void)(0)
@@ -44,7 +46,7 @@ struct sdp_xml_data {
 	char type;			/* 0 = Text or Hexadecimal */
 	char *name;			/* Name, optional in the dtd */
 	/* TODO: What is it used for? */
-	sdp_data_t *tail;		/* Tail for O(1) dataseq append */
+	struct queue *seq;		/* Members of a dataseq, if any */
 };
 
 struct context_data {
@@ -510,8 +512,37 @@ static void element_start(GMarkupParseContext *context,
 	}
 }
 
+/*
+ * Link the members collected in elem->seq into elem->data->val.dataseq.
+ *
+ * Members are collected in a queue so that appending is O(1), sdp_seq_append()
+ * would otherwise have to walk to the tail of the sequence on every append.
+ */
+static void sdp_xml_data_flush_seq(struct sdp_xml_data *elem)
+{
+	const struct queue_entry *entry;
+	sdp_data_t *tail = NULL;
+
+	if (!elem->seq)
+		return;
+
+	for (entry = queue_get_entries(elem->seq); entry; entry = entry->next) {
+		if (tail)
+			sdp_seq_append(tail, entry->data);
+		else
+			elem->data->val.dataseq = sdp_seq_append(NULL,
+								entry->data);
+		tail = entry->data;
+	}
+
+	queue_destroy(elem->seq, NULL);
+	elem->seq = NULL;
+}
+
 static void sdp_xml_data_free(struct sdp_xml_data *elem)
 {
+	queue_destroy(elem->seq, (queue_destroy_func_t) sdp_data_free);
+
 	if (elem->data)
 		sdp_data_free(elem->data);
 
@@ -568,6 +599,8 @@ static void element_end(GMarkupParseContext *context,
 		return;
 	}
 
+	sdp_xml_data_flush_seq(ctx_data->stack_head);
+
 	if (!strcmp(element_name, "sequence")) {
 		if (!SDP_IS_SEQ(ctx_data->stack_head->data->dtd)) {
 			g_set_error(err, G_MARKUP_ERROR,
@@ -610,28 +643,21 @@ static void element_end(GMarkupParseContext *context,
 
 	if (ctx_data->stack_head->next && ctx_data->stack_head->data &&
 					ctx_data->stack_head->next->data) {
-		sdp_data_t *tail;
-		switch (ctx_data->stack_head->next->data->dtd) {
+		struct sdp_xml_data *parent = ctx_data->stack_head->next;
+
+		switch (parent->data->dtd) {
 		case SDP_SEQ8:
 		case SDP_SEQ16:
 		case SDP_SEQ32:
 		case SDP_ALT8:
 		case SDP_ALT16:
 		case SDP_ALT32:
-			tail = ctx_data->stack_head->next->data->val.dataseq ?
-				ctx_data->stack_head->next->tail : NULL;
-			if (tail) {
-				sdp_seq_append(tail,
-					ctx_data->stack_head->data);
-			} else {
-				ctx_data->stack_head->next->data->val.dataseq =
-					sdp_seq_append(NULL,
-						ctx_data->stack_head->data);
-			}
-			ctx_data->stack_head->next->tail =
-					ctx_data->stack_head->data;
-			ctx_data->stack_head->data = NULL;
-			ctx_data->stack_head->tail = NULL;
+			if (!parent->seq)
+				parent->seq = queue_new();
+
+			if (queue_push_tail(parent->seq,
+						ctx_data->stack_head->data))
+				ctx_data->stack_head->data = NULL;
 			break;
 		}
 
-- 
2.54.0

RE: [BlueZ,v1] sdp-xml: Use a queue to collect sequence members

[bluez.test.bot]

[-- Attachment #1: Type: text/plain, Size: 527 bytes --]

This is an automated email and please do not reply to this email.

Dear Submitter,

Thank you for submitting the patches to the linux bluetooth mailing list.
While preparing the CI tests, the patches you submitted couldn't be applied to the current HEAD of the repository.

----- Output -----

error: patch failed: src/sdp-xml.c:44
error: src/sdp-xml.c: patch does not apply
hint: Use 'git am --show-current-patch' to see the failed patch

Please resolve the issue and submit the patches again.


---
Regards,
Linux Bluetooth