[BlueZ, v3 6/9] sdp-xml: Optimise parsing large sequences

[Bastien Nocera <hadess@hadess.net>]

SDP sequences are stored as single-linked lists, so appending members
to a sequence requires finding the tail of the list before the
insertion.

Finding the tail of the list always starts at the beginning of the list,
so takes longer and longer as the list grows bigger.

Keep track of the tail to avoid that problem. This cuts down the
sequence_on_squared() test from around 3 to 4 seconds to less than
0.1 seconds.
---
 src/sdp-xml.c | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)

diff --git a/src/sdp-xml.c b/src/sdp-xml.c
index 816d19611f8b..97fb8b0c1af0 100644
--- a/src/sdp-xml.c
+++ b/src/sdp-xml.c
@@ -44,6 +44,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 context_data {
@@ -609,6 +610,7 @@ 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) {
 		case SDP_SEQ8:
 		case SDP_SEQ16:
@@ -616,10 +618,17 @@ static void element_end(GMarkupParseContext *context,
 		case SDP_ALT8:
 		case SDP_ALT16:
 		case SDP_ALT32:
-			ctx_data->stack_head->next->data->val.dataseq =
-				sdp_seq_append(ctx_data->stack_head->next->data->val.dataseq,
-								ctx_data->stack_head->data);
+			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;
 			break;
 		}
 
-- 
2.55.0