Re: [PATCH v2 11/17] libtraceeval histogram: Add iterator APIs

[Ross Zwisler <zwisler@google.com>]

On Fri, Aug 11, 2023 at 01:39:34AM -0400, Steven Rostedt wrote:
> From: "Steven Rostedt (Google)" <rostedt@goodmis.org>
> 
> Provide an interface for the application to iterate over all the entries
> in the traceeval histogram.
> 
>  traceeval_iterator_get() - acquire an iterator for the given traceeval
>  traceveal_iterator_put() - release the iterator
>  traceeval_iterator_sort() - sort the iterator for a given key/value
>  traceeval_iterator_next() - return the keys of the next entry in the
>                              traceeval
> 
> Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
> ---
>  include/traceeval-hist.h |   7 ++
>  src/eval-local.h         |  11 ++
>  src/hash.c               |   4 +
>  src/histograms.c         | 255 ++++++++++++++++++++++++++++++++++++++-
>  4 files changed, 276 insertions(+), 1 deletion(-)
> 
<>
> diff --git a/src/histograms.c b/src/histograms.c
> index 9a8ec4d85301..2b823ad5c26d 100644
> --- a/src/histograms.c
> +++ b/src/histograms.c
> @@ -37,7 +37,7 @@ static void print_err(const char *fmt, ...)
>   * -1 for the other way around, and -2 on error.
>   */
>  static int compare_traceeval_data(struct traceeval *teval,
> -				  union traceeval_data *orig,
> +				  const union traceeval_data *orig,
>  				  const union traceeval_data *copy,
>  				  struct traceeval_type *type)
>  {
> @@ -904,3 +904,256 @@ int traceeval_insert(struct traceeval *teval,
>  	else
>  		return update_entry(teval, entry, vals);
>  }
> +
> +/**
> + * traceeval_iterator_put - release a given iterator
> + * @iter: The iterartor to release
> + *
> + * Frees the resources of an @iter that was created by
> + * traceeval_iterator_get().
> + */
> +void traceeval_iterator_put(struct traceeval_iterator *iter)
> +{
> +	if (!iter)
> +		return;
> +
> +	free(iter->entries);

I think we also need to free **sort and *direction, which are both allocated
in traceeval_iterator_sort().    Probably need to update the function comment
as well to include allocs from that function.

> +	free(iter);
> +}
<>
> +/**
> + * traceeval_iterator_sort - sort the entries that an iterator will return
> + * @iter: The iterator to specify the sort order of the entries
> + * @sort_field: The name of the key or value to sort with.
> + * @level: The level of sorting (0 for first order, 1 for second, ...)
> + * @ascending: If the sort should go forward or backward.
> + *
> + * The iterator has a list of entries to produce with traceeval_iterator_next().
> + * This function specifies what the order of the output of that function will
> + * be. Note, whenever this function is called, it resets the @iter so that
> + * the traceveal_iterator_next() will start from the beginning again.
> + *
> + * In other words, be very careful to ever call this function in a middle
> + * of a loop that is using traceeval_iterator_next(), otherwise you may end
> + * up in an infinite loop!
> + *
> + * The @level specifies the level of sorting. That is, for @level = 0,
> + * it will decide the main sorting of the @iter. For @level = 1, it will
> + * be the tie breaker for two entries that are equal for the @level = 0
> + * sort. @level = 2, will be the tie breaker for @level = 1, and so on.
> + *
> + * Note, if traceeval_iterator_next() is called, and there's a missing @level,
> + * it will fail. That is, if this function is called once with @level = 0 and
> + * againg with @level = 2, but never with @level = 1, the call to
> + * traceeval_iterator_next() will fail.
> + *
> + * If this function is called multiple times with the same @level, then the
> + * last call will define the what that @level will do.
> + *
> + * The @ascending will determine if "smaller" items go first if true, and
> + * "larger" items go first if false.
> + *
> + * Return 0 on success and -1 on failure.
> + */
> +int traceeval_iterator_sort(struct traceeval_iterator *iter, const char *sort_field,
> +			    int level, bool ascending)
> +{
> +	bool *direction = iter->direction;
> +	struct traceeval_type **sort = iter->sort;
> +	struct traceeval_type *type;
> +
> +	type = find_sort_type(iter->teval, sort_field);
> +	if (!type)
> +		return -1;
> +
> +	/* pointer and dynamic types must have a cmp function */
> +	switch (type->type) {
> +	case TRACEEVAL_TYPE_POINTER:
> +	case TRACEEVAL_TYPE_DYNAMIC:
> +		if (!type->cmp)
> +			return -1;
> +		break;
> +	default:
> +		break;
> +	}
> +

nit: It'd probably help with readability to have:

  int num_levels = level + 1;

and use that instead of (level + 1).

> +	if ((level + 1) > iter->nr_sort) {
> +		sort = realloc(sort, sizeof(*sort) * (level + 1));
> +		if (!sort)
> +			return -1;
> +
> +		iter->sort = sort;
> +
> +		direction = realloc(direction, sizeof(*direction) * (level + 1));
> +		if (!direction)
> +			return -1;
> +
> +		iter->direction = direction;
> +
> +		/* Make sure the newly allocated contain NULL */
> +		for (int i = iter->nr_sort; i < (level + 1); i++)
> +			sort[i] = NULL;
> +
> +		iter->nr_sort = level + 1;
> +	}
> +
> +	sort[level] = type;
> +	direction[level] = ascending;
> +	iter->needs_sort = true;
> +	return 0;
> +}
<>
> +static int sort_iter(struct traceeval_iterator *iter)
> +{
> +	int i;
> +
> +	/* Make sure all levels are filled */
> +	for (i = 0; i < iter->nr_sort; i++) {
> +		if (!iter->sort[i])
> +			return -1;
> +	}
> +
> +	qsort_r(iter->entries, iter->nr_entries, sizeof(*iter->entries),
> +		iter_cmp, iter);
> +
> +	iter->needs_sort = false;
> +	iter->next = 0;
> +
> +	return 0;
> +}
> +
> +/**
> + * traceeval_iterator_next - retrieve the next entry from an iterator
> + * @iter: The iterator to retrieve the next entry from
> + * @keys: The returned keys of the next entry (if exists)
> + *
> + * This returns the keys for the next entry in the traceeval being
> + * iterated over by @iter. If there are no more entries, 0 is returned
> + * and @keys are untouched.
> + *
> + * Returns 1 if another entry is returned, or 0 if not (or negative on error)
> + */
> +int traceeval_iterator_next(struct traceeval_iterator *iter,
> +			    const union traceeval_data **keys)
> +{
> +	struct entry *entry;
> +	int ret;
> +
> +	if (iter->needs_sort) {
> +		ret = sort_iter(iter);
> +		if (ret < 0)
> +			return ret;
> +		iter->next = 0;

This is already done in sort_iter().

> +	}
> +
> +	if (iter->next >= iter->nr_entries)
> +		return 0;
> +
> +	entry = iter->entries[iter->next++];
> +	*keys = entry->keys;
> +	return 1;
> +}
> -- 
> 2.40.1
>