[PATCH BlueZ v2 1/4] sdp-xml: Use a queue to collect sequence members

From: Luiz Augusto von Dentz <[email protected]>

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
---
 Makefile.tools |  4 +++-
 src/sdp-xml.c  | 60 ++++++++++++++++++++++++++++++++++++--------------
 2 files changed, 46 insertions(+), 18 deletions(-)

diff --git a/Makefile.tools b/Makefile.tools
index 1a4e5660813b..b3ef4ae1c3df 100644
--- a/Makefile.tools
+++ b/Makefile.tools
@@ -437,7 +437,9 @@ tools_hciconfig_LDADD = lib/libbluetooth-internal.la
 tools_hcitool_SOURCES = tools/hcitool.c src/oui.h src/oui.c
 tools_hcitool_LDADD = lib/libbluetooth-internal.la $(UDEV_LIBS)
 
-tools_sdptool_SOURCES = tools/sdptool.c src/sdp-xml.h src/sdp-xml.c
+tools_sdptool_SOURCES = tools/sdptool.c src/sdp-xml.h src/sdp-xml.c \
+			src/shared/queue.h src/shared/queue.c \
+			src/shared/util.h src/shared/util.c
 tools_sdptool_LDADD = lib/libbluetooth-internal.la $(GLIB_LIBS)
 
 tools_ciptool_LDADD = lib/libbluetooth-internal.la
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