+/*
+ * 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)
+{
+ double ts;
+
+ ts = (double)snum;
+ ts /= ctx->samplerate;
+ ts *= ctx->period;
+
+ return ts;
+}
+
+/*
+ * Unqueue one item of the VCD values queue which corresponds to one
+ * sample number. Append all of the text to the passed in GString.
+ */
+static int unqueue_item(struct context *ctx,
+ struct vcd_queue_item *item, GString *s)
+{
+ double ts;
+ GString *buff;
+ gboolean is_empty;
+
+ /*
+ * Start the sample number's string with the timestamp. Append
+ * all value changes. Terminate lines for items which have a
+ * timestamp but no value changes, assuming this is the last
+ * entry which corresponds to SR_DF_END.
+ */
+ ts = snum_to_ts(ctx, item->samplenum);
+ buff = item->values;
+ is_empty = !buff || !buff->len || !buff->str || !*buff->str;
+ append_vcd_timestamp(s, ts, is_empty);
+ if (!is_empty)
+ g_string_append(s, buff->str);
+
+ return SR_OK;
+}
+
+/*
+ * Get the last sample number which logic data was received for. This
+ * implementation assumes that all logic channels get received within
+ * exactly one packet of corresponding unitsize.
+ */
+static uint64_t get_last_snum_logic(struct context *ctx)
+{
+ size_t i;
+ struct vcd_channel_desc *desc;
+
+ for (i = 0; i < ctx->enabled_count; i++) {
+ desc = &ctx->channels[i];
+ if (desc->type != SR_CHANNEL_LOGIC)
+ continue;
+ return desc->last_rcvd_snum;
+ }
+
+ return 0;
+}
+
+/*
+ * Update the last sample number which logic data was received for.
+ */
+static void upd_last_snum_logic(struct context *ctx, uint64_t inc)
+{
+ size_t i;
+ struct vcd_channel_desc *desc;
+
+ for (i = 0; i < ctx->enabled_count; i++) {
+ desc = &ctx->channels[i];
+ if (desc->type != SR_CHANNEL_LOGIC)
+ continue;
+ desc->last_rcvd_snum += inc;
+ }
+}
+
+/*
+ * Get and update the last sample number which analog data was received
+ * for on a specific channel (which the caller already has identified).
+ */
+
+static uint64_t get_last_snum_analog(struct vcd_channel_desc *desc)
+{
+
+ return desc->last_rcvd_snum;
+}
+
+static void upd_last_snum_analog(struct vcd_channel_desc *desc, uint64_t inc)
+{
+
+ if (!desc)
+ return;
+ desc->last_rcvd_snum += inc;
+}
+
+/*
+ * Determine the maximum sample number which data from all involved
+ * channels was received for.
+ */
+static uint64_t get_max_snum_export(struct context *ctx)
+{
+ uint64_t snum;
+ size_t i;
+ struct vcd_channel_desc *desc;
+
+ snum = ~UINT64_C(0);
+ for (i = 0; i < ctx->enabled_count; i++) {
+ desc = &ctx->channels[i];
+ if (snum > desc->last_rcvd_snum)
+ snum = desc->last_rcvd_snum;
+ }
+
+ return snum;
+}
+
+/*
+ * Determine the maximum sample number of any channel we may have
+ * received data for. Then pretend we had seen that number of samples
+ * on all channels. Such that the next export can flush all previously
+ * queued data up to and including the final number, which serves as
+ * some kind of termination of the VCD output data.
+ */
+static uint64_t get_max_snum_flush(struct context *ctx)
+{
+ uint64_t snum;
+ size_t i;
+ struct vcd_channel_desc *desc;
+
+ /* Determine the maximum sample number. */
+ snum = 0;
+ for (i = 0; i < ctx->enabled_count; i++) {
+ desc = &ctx->channels[i];
+ if (snum < desc->last_rcvd_snum)
+ snum = desc->last_rcvd_snum;
+ }
+
+ /* Record that number as "seen" with all channels. */
+ for (i = 0; i < ctx->enabled_count; i++) {
+ desc = &ctx->channels[i];
+ desc->last_rcvd_snum = snum + 1;
+ }
+
+ return snum;
+}
+
+/*
+ * Pass all queued value changes when we are certain we have received
+ * data from all channels.
+ */
+static int write_completed_changes(struct context *ctx, GString *out)
+{
+ uint64_t upto_snum;
+ GList **listref, *node;
+ struct vcd_queue_item *item;
+ int rc;
+ size_t dumped;
+
+ /* Determine the number which all data was received for so far. */
+ upto_snum = get_max_snum_export(ctx);
+ if (with_queue_stats)
+ sr_spew("%s(), check up to %" PRIu64, __func__, upto_snum);
+
+ /*
+ * Forward and consume those items from the head of the list
+ * which we completely have accumulated and are certain about.
+ */
+ dumped = 0;
+ listref = &ctx->vcd_queue_list;
+ while (*listref) {
+ /* Find items before the targetted sample number. */
+ node = *listref;
+ item = node->data;
+ if (!item)
+ break;
+ if (item->samplenum >= upto_snum)
+ break;
+
+ /*
+ * Unlink the item from the list. Void cached positions.
+ * Append its timestamp and values to the caller's text.
+ */
+ dumped++;
+ if (with_queue_stats)
+ sr_dbg("%s(), dump nr %" PRIu64,
+ __func__, item->samplenum);
+ if (ctx->vcd_queue_last == node)
+ ctx->vcd_queue_last = NULL;
+ *listref = g_list_remove_link(*listref, node);
+ rc = unqueue_item(ctx, item, out);
+ queue_free_item(ctx, item);
+ if (rc != SR_OK)
+ return rc;
+ }
+
+ return SR_OK;
+}
+
+/* Get packets from the session feed, generate output text. */
+static int receive(const struct sr_output *o,
+ const struct sr_datafeed_packet *packet, GString **out)