llc: Add move_and_merge method to llc_queue

This methods takes all LLC frames from the old LLC queue and moves
them into the current. If both queues are ordered chronologically
(recv_time), the resulting queue is also ordered.

Sponsored-by: On-Waves ehf

5 files changed, 112 insertions, 0 deletions

diff --git a/src/llc.cpp b/src/llc.cpp
index c071d0a1..79afc377 100644
--- a/src/llc.cpp
+++ b/src/llc.cpp
@@ -134,6 +134,59 @@ void gprs_llc_queue::clear(BTS *bts)
 	m_queue_octets = 0;
 }
 
+void gprs_llc_queue::move_and_merge(gprs_llc_queue *o)
+{
+	struct msgb *msg, *msg1 = NULL, *msg2 = NULL;
+	struct llist_head new_queue;
+	size_t queue_size = 0;
+	size_t queue_octets = 0;
+	INIT_LLIST_HEAD(&new_queue);
+
+	while (1) {
+		if (msg1 == NULL)
+			msg1 = msgb_dequeue(&m_queue);
+
+		if (msg2 == NULL)
+			msg2 = msgb_dequeue(&o->m_queue);
+
+		if (msg1 == NULL && msg2 == NULL)
+			break;
+
+		if (msg1 == NULL) {
+			msg = msg2;
+			msg2 = NULL;
+		} else if (msg2 == NULL) {
+			msg = msg1;
+			msg1 = NULL;
+		} else {
+			const MetaInfo *mi1 = (MetaInfo *)&msg1->cb[0];
+			const MetaInfo *mi2 = (MetaInfo *)&msg2->cb[0];
+
+			if (timercmp(&mi2->recv_time, &mi1->recv_time, >)) {
+				msg = msg1;
+				msg1 = NULL;
+			} else {
+				msg = msg2;
+				msg2 = NULL;
+			}
+		}
+
+		msgb_enqueue(&new_queue, msg);
+		queue_size += 1;
+		queue_octets += msgb_length(msg);
+	}
+
+	OSMO_ASSERT(llist_empty(&m_queue));
+	OSMO_ASSERT(llist_empty(&o->m_queue));
+
+	o->m_queue_size = 0;
+	o->m_queue_octets = 0;
+
+	llist_splice_init(&new_queue, &m_queue);
+	m_queue_size = queue_size;
+	m_queue_octets = queue_octets;
+}
+
 #define ALPHA 0.5f
 
 struct msgb *gprs_llc_queue::dequeue(const MetaInfo **info)
diff --git a/src/llc.h b/src/llc.h
index fe8958fd..94de16ed 100644
--- a/src/llc.h
+++ b/src/llc.h
@@ -80,6 +80,7 @@ struct gprs_llc_queue {
 	void enqueue(struct msgb *llc_msg, const MetaInfo *info = 0);
 	struct msgb *dequeue(const MetaInfo **info = 0);
 	void clear(BTS *bts);
+	void move_and_merge(gprs_llc_queue *o);
 	size_t size() const;
 	size_t octets() const;
 
diff --git a/tests/llc/LlcTest.cpp b/tests/llc/LlcTest.cpp
index a2e3c5e9..e972cf4e 100644
--- a/tests/llc/LlcTest.cpp
+++ b/tests/llc/LlcTest.cpp
@@ -165,6 +165,56 @@ static void test_llc_meta()
 	printf("=== end %s ===\n", __func__);
 }
 
+static void test_llc_merge()
+{
+	gprs_llc_queue queue1;
+	gprs_llc_queue queue2;
+	gprs_llc_queue::MetaInfo info = {0};
+
+	printf("=== start %s ===\n", __func__);
+
+	queue1.init();
+	queue2.init();
+
+	info.recv_time.tv_sec += 1;
+	enqueue_data(&queue1, "*A*", &info);
+
+	info.recv_time.tv_sec += 1;
+	enqueue_data(&queue1, "*B*", &info);
+
+	info.recv_time.tv_sec += 1;
+	enqueue_data(&queue2, "*C*", &info);
+
+	info.recv_time.tv_sec += 1;
+	enqueue_data(&queue1, "*D*", &info);
+
+	info.recv_time.tv_sec += 1;
+	enqueue_data(&queue2, "*E*", &info);
+
+	OSMO_ASSERT(queue1.size() == 3);
+	OSMO_ASSERT(queue1.octets() == 9);
+	OSMO_ASSERT(queue2.size() == 2);
+	OSMO_ASSERT(queue2.octets() == 6);
+
+	queue2.move_and_merge(&queue1);
+
+	OSMO_ASSERT(queue1.size() == 0);
+	OSMO_ASSERT(queue1.octets() == 0);
+	OSMO_ASSERT(queue2.size() == 5);
+	OSMO_ASSERT(queue2.octets() == 15);
+
+	dequeue_and_check(&queue2, "*A*");
+	dequeue_and_check(&queue2, "*B*");
+	dequeue_and_check(&queue2, "*C*");
+	dequeue_and_check(&queue2, "*D*");
+	dequeue_and_check(&queue2, "*E*");
+
+	OSMO_ASSERT(queue2.size() == 0);
+	OSMO_ASSERT(queue2.octets() == 0);
+
+	printf("=== end %s ===\n", __func__);
+}
+
 static const struct log_info_cat default_categories[] = {
 	{"DPCU", "", "GPRS Packet Control Unit (PCU)", LOGL_INFO, 1},
 };
@@ -200,6 +250,7 @@ int main(int argc, char **argv)
 
 	test_llc_queue();
 	test_llc_meta();
+	test_llc_merge();
 
 	if (getenv("TALLOC_REPORT_FULL"))
 		talloc_report_full(tall_pcu_ctx, stderr);
diff --git a/tests/llc/LlcTest.err b/tests/llc/LlcTest.err
index b28fe1df..f2c5cab8 100644
--- a/tests/llc/LlcTest.err
+++ b/tests/llc/LlcTest.err
@@ -2,3 +2,8 @@ dequeued msg, length 11 (expected 11), data 4c 4c 43 20 6d 65 73 73 61 67 65
 dequeued msg, length 17 (expected 17), data 6f 74 68 65 72 20 4c 4c 43 20 6d 65 73 73 61 67 65 
 dequeued msg, length 13 (expected 13), data 4c 4c 43 20 6d 65 73 73 61 67 65 20 31 
 dequeued msg, length 13 (expected 13), data 4c 4c 43 20 6d 65 73 73 61 67 65 20 32 
+dequeued msg, length 3 (expected 3), data 2a 41 2a 
+dequeued msg, length 3 (expected 3), data 2a 42 2a 
+dequeued msg, length 3 (expected 3), data 2a 43 2a 
+dequeued msg, length 3 (expected 3), data 2a 44 2a 
+dequeued msg, length 3 (expected 3), data 2a 45 2a 
diff --git a/tests/llc/LlcTest.ok b/tests/llc/LlcTest.ok
index 8a5f2354..311f37cd 100644
--- a/tests/llc/LlcTest.ok
+++ b/tests/llc/LlcTest.ok
@@ -2,3 +2,5 @@
 === end test_llc_queue ===
 === start test_llc_meta ===
 === end test_llc_meta ===
+=== start test_llc_merge ===
+=== end test_llc_merge ===