+/*
+ * Gets called when a session feed packet was received. Either creates
+ * a VCD file header (once in the output module's lifetime), or an empty
+ * GString. Callers will append the text representation of sample data
+ * to that string as needed.
+ */
+static GString *chk_header(const struct sr_output *o)
+{
+ struct context *ctx;
+ GString *s;
+
+ ctx = o->priv;
+
+ if (!ctx->header_done) {
+ ctx->header_done = TRUE;
+ s = gen_header(o);
+ } else {
+ s = g_string_sized_new(512);
+ }
+
+ return s;
+}
+
+/*
+ * Helpers to "merge sort" sample data that we have received in chunks
+ * at different times in different code paths. Queue the data until we
+ * have seen samples from all involved channels for a given samplenumber.
+ * Data for a given sample number can only get emitted when we are sure
+ * no other channel's data can arrive any more.
+ */
+
+static struct vcd_queue_item *queue_alloc_item(struct context *ctx, uint64_t snum)
+{
+ GSList *node;
+ struct vcd_queue_item *item;
+
+ /* Get an item from the free list if available. */
+ node = ctx->free_list;
+ if (node) {
+ ctx->reused++;
+
+ /* Unlink GSList node from the free list. */
+ ctx->free_list = node->next;
+ node->next = NULL;
+ item = node->data;
+ node->data = NULL;
+
+ /* Setup content of the item. */
+ item->samplenum = snum;
+ if (!item->values)
+ item->values = g_string_sized_new(32);
+ else
+ g_string_truncate(item->values, 0);
+
+ /* Keep GSList node in the used list (avoid free/alloc). */
+ node->next = ctx->used_list;
+ ctx->used_list = node;
+
+ return item;
+ }
+
+ /* Dynamic allocation of an item. */
+ ctx->alloced++;
+ item = g_malloc0(sizeof(*item));
+ if (!item)
+ return NULL;
+ item->samplenum = snum;
+ item->values = g_string_sized_new(32);
+
+ /* Create a used list item, to later move to the free list. */
+ ctx->used_list = g_slist_prepend(ctx->used_list, item);
+
+ return item;
+}
+
+static void queue_free_item(struct context *ctx, struct vcd_queue_item *item)
+{
+ GSList *node;
+
+ /*
+ * Put item back into the free list. We can assume to find a
+ * used list node, it got allocated when the item was acquired.
+ */
+ node = ctx->used_list;
+ if (node) {
+ ctx->pooled++;
+
+ ctx->used_list = node->next;
+ node->next = NULL;
+ node->data = item;
+
+ item->samplenum = 0;
+ g_string_truncate(item->values, 0);
+
+ node->next = ctx->free_list;
+ ctx->free_list = node;
+
+ return;
+ }
+
+ /*
+ * Release dynamically allocated resources. Could also be used
+ * to release free list items when the use list is empty.
+ */
+ ctx->freed++;
+ if (item->values)
+ g_string_free(item->values, TRUE);
+ g_free(item);
+}
+
+static void queue_drain_pool_cb(gpointer data, gpointer cb_data)
+{
+ struct context *ctx;
+ struct vcd_queue_item *item;
+
+ item = data;
+ ctx = cb_data;
+ queue_free_item(ctx, item);
+}
+
+static void queue_drain_pool(struct context *ctx)
+{
+ GSList *list;
+
+ /*
+ * Grab the list and "empty" the context member. Then
+ * iterate over the items, have dymamic memory released.
+ * Then free the GSList nodes (but not their data parts).
+ * Do this for the used and the free lists.
+ */
+ list = ctx->used_list;
+ ctx->used_list = NULL;
+ g_slist_foreach(list, queue_drain_pool_cb, ctx);
+ g_slist_free(list);
+
+ list = ctx->free_list;
+ ctx->free_list = NULL;
+ g_slist_foreach(list, queue_drain_pool_cb, ctx);
+ g_slist_free(list);
+}
+
+static int cmp_snum(gconstpointer l, gconstpointer d)
+{
+ const struct vcd_queue_item *list_item;
+ const uint64_t *snum_ptr;
+
+ list_item = l;
+ snum_ptr = d;
+ if (list_item->samplenum > *snum_ptr)
+ return +1;
+ if (list_item->samplenum < *snum_ptr)
+ return -1;
+ return 0;
+}
+
+static int cmp_items(gconstpointer a, gconstpointer b)
+{
+ const struct vcd_queue_item *item_a, *item_b;
+
+ item_a = a;
+ item_b = b;
+ if (item_a->samplenum > item_b->samplenum)
+ return +1;
+ if (item_a->samplenum < item_b->samplenum)
+ return -1;
+ return 0;
+}
+
+/*
+ * Position the current pointer of the VCD value queue to a specific
+ * sample number. Create a new queue item when needed. The logic assumes
+ * a specific use pattern: Reception of striped sample data for channels
+ * and processing in strict order of sample numbers within a channel.
+ * Lower sample numbers near the start of the queue when channels change
+ * between session feed packets, before another linear sequence follows.
+ *
+ * Naive use of convenience glib routines would severely lose performance.
+ * That's why custom code is used, which is as complex as it needs to be,
+ * yet shall execute faster than a simpler implementation. For trivial
+ * cases (logic only, one analog channel only) this queue is bypassed.
+ */
+static int queue_samplenum(struct context *ctx, uint64_t snum)
+{
+ struct vcd_queue_item *item, *add_item;
+ GList *walk_list, *after_snum, *before_snum, *add_list;
+ GList *last;
+ gboolean add_after_last, do_search;
+
+ /* Already at that position? */
+ item = ctx->vcd_queue_last ? ctx->vcd_queue_last->data : NULL;
+ if (item && item->samplenum == snum)
+ return SR_OK;
+
+ /*
+ * Search after the current position in the remaining queue. The
+ * custom code uses the queue's being sorted by sample number.
+ * Narrow down a later insert position as much as possible. This
+ * avoids linear search in huge spaces later on.
+ */
+ last = NULL;
+ add_after_last = FALSE;
+ after_snum = NULL;
+ before_snum = NULL;
+ walk_list = ctx->vcd_queue_last;
+ while (walk_list) {
+ item = walk_list->data;
+ if (!item)
+ break;
+ if (item->samplenum == snum) {
+ ctx->vcd_queue_last = walk_list;
+ return SR_OK;
+ }
+ last = walk_list;
+ if (item->samplenum < snum)
+ before_snum = walk_list;
+ if (item->samplenum > snum) {
+ after_snum = walk_list;
+ break;
+ }
+ if (!walk_list->next)
+ add_after_last = TRUE;
+ walk_list = walk_list->next;
+ }
+
+ /*
+ * No exact match at or beyond the current position. Run another
+ * search from the start of the queue, again restrict the space
+ * which is searched, and narrow down the insert position when
+ * no match is found.
+ *
+ * If the searched sample number is larger than any we have seen
+ * before, or was in the above covered range but was not found,
+ * then we know that another queue item needs to get added, and
+ * where to put it. In that case we need not iterate the earlier
+ * list items.
+ */
+ walk_list = ctx->vcd_queue_list;
+ do_search = TRUE;
+ if (add_after_last)
+ do_search = FALSE;
+ if (before_snum)
+ do_search = FALSE;
+ while (do_search && walk_list && walk_list != ctx->vcd_queue_last) {
+ item = walk_list->data;
+ if (!item)
+ break;
+ if (item->samplenum == snum) {
+ ctx->vcd_queue_last = walk_list;
+ return SR_OK;
+ }
+ if (item->samplenum < snum)
+ before_snum = walk_list;
+ if (item->samplenum > snum) {
+ after_snum = walk_list;
+ break;
+ }
+ walk_list = walk_list->next;
+ }
+
+ /*
+ * The complete existing queue was exhausted, no exact match was
+ * found. A new queue item must get inserted. Identify a good
+ * position where to start searching for the exact position to
+ * link the new item to the list. Assume that the combination of
+ * the glib routine's list traversal and the sample number check
+ * in the callback is expensive, reduce the amount of work done.
+ *
+ * If we have seen an item with a larger sample number than the
+ * wanted, check its immediate predecessor. If this has a smaller
+ * sample number, then we found a perfect location to insert the
+ * new item. If we know that the new item must be inserted after
+ * the last traversed queue item, start there.
+ */
+ if (!before_snum) do {
+ if (add_after_last)
+ break;
+ if (!after_snum)
+ break;
+ walk_list = after_snum->prev;
+ if (!walk_list)
+ break;
+ item = walk_list->data;
+ if (!item)
+ break;
+ if (item->samplenum == snum) {
+ ctx->vcd_queue_last = walk_list;
+ return SR_OK;
+ }
+ if (item->samplenum < snum)
+ before_snum = walk_list;
+ } while (0);
+ add_list = add_after_last ? last : before_snum;
+ if (!add_list) {
+ walk_list = ctx->vcd_queue_list;
+ while (walk_list) {
+ item = walk_list->data;
+ if (!item)
+ break;
+ if (item->samplenum == snum) {
+ ctx->vcd_queue_last = walk_list;
+ return SR_OK;
+ }
+ if (item->samplenum > snum) {
+ after_snum = walk_list;
+ break;
+ }
+ add_list = walk_list;
+ walk_list = walk_list->next;
+ }
+ }
+ if (add_list && (item = add_list->data) && item->samplenum == snum) {
+ ctx->vcd_queue_last = add_list;
+ return SR_OK;
+ }
+
+ /*
+ * Create a new queue item for the so far untracked sample
+ * number. Immediately search for the inserted position (is
+ * unfortunately not returned from the insert call), and
+ * cache that position for subsequent lookups.
+ */
+ if (with_queue_stats)
+ sr_dbg("%s(), queue nr %" PRIu64, __func__, snum);
+ add_item = queue_alloc_item(ctx, snum);
+ if (!add_item)
+ return SR_ERR_MALLOC;
+ if (!add_list)
+ add_list = ctx->vcd_queue_list;
+ if (add_list && add_list->prev)
+ add_list = add_list->prev;
+ walk_list = g_list_insert_sorted(add_list, add_item, cmp_items);
+ if (!walk_list->prev)
+ ctx->vcd_queue_list = walk_list;
+ walk_list = g_list_find_custom(walk_list, &snum, cmp_snum);
+ item = walk_list ? walk_list->data : NULL;
+ if (item && item->samplenum == snum) {
+ ctx->vcd_queue_last = walk_list;
+ }
+ return SR_OK;
+}
+
+/*
+ * Prepare to append another text fragment for a value change to the
+ * queue item which corresponds to the current sample number. Return
+ * the GString which the caller then will append to.
+ */
+static GString *queue_value_text_prep(struct context *ctx)
+{
+ struct vcd_queue_item *item;
+ GString *buff;
+
+ /* Cope with not-yet-positioned write pointers. */
+ item = ctx->vcd_queue_last ? ctx->vcd_queue_last->data : NULL;
+ if (!item)
+ return NULL;
+
+ /* Create a GString if not done already. */
+ buff = item->values;
+ if (!buff) {
+ buff = g_string_sized_new(20);
+ item->values = buff;
+ }
+
+ /* Separate items with spaces (if previous content is present). */
+ if (buff->len)
+ g_string_append_c(buff, ' ');
+
+ return buff;
+}
+
+static double snum_to_ts(struct context *ctx, uint64_t snum)