2  * qdist.c - QEMU helpers for handling frequency distributions of data.
7  *   See the COPYING file in the top-level directory.
21     dist->entries = g_new(struct qdist_entry, 1);  in qdist_init()
22     dist->size = 1;  in qdist_init()
23     dist->n = 0;  in qdist_init()
28     g_free(dist->entries);  in qdist_destroy()
36         return -1;  in qdist_cmp_double()
46     return qdist_cmp_double(a->x, b->x);  in qdist_cmp()
53     if (dist->n) {  in qdist_add()
57         entry = bsearch(&e, dist->entries, dist->n, sizeof(e), qdist_cmp);  in qdist_add()
61         entry->count += count;  in qdist_add()
65     if (unlikely(dist->n == dist->size)) {  in qdist_add()
66         dist->size *= 2;  in qdist_add()
67         dist->entries = g_renew(struct qdist_entry, dist->entries, dist->size);  in qdist_add()
69     dist->n++;  in qdist_add()
70     entry = &dist->entries[dist->n - 1];  in qdist_add()
71     entry->x = x;  in qdist_add()
72     entry->count = count;  in qdist_add()
73     qsort(dist->entries, dist->n, sizeof(*entry), qdist_cmp);  in qdist_add()
108     double min, max;  in qdist_pr_internal()  local
113     if (dist->n == 1) {  in qdist_pr_internal()
114         if (dist->entries[0].count) {  in qdist_pr_internal()
115             g_string_append_unichar(s, qdist_blocks[QDIST_NR_BLOCK_CODES - 1]);  in qdist_pr_internal()
122     /* get min and max counts */  in qdist_pr_internal()
123     min = dist->entries[0].count;  in qdist_pr_internal()
124     max = min;  in qdist_pr_internal()
125     for (i = 0; i < dist->n; i++) {  in qdist_pr_internal()
126         struct qdist_entry *e = &dist->entries[i];  in qdist_pr_internal()
128         if (e->count < min) {  in qdist_pr_internal()
129             min = e->count;  in qdist_pr_internal()
131         if (e->count > max) {  in qdist_pr_internal()
132             max = e->count;  in qdist_pr_internal()
136     for (i = 0; i < dist->n; i++) {  in qdist_pr_internal()
137         struct qdist_entry *e = &dist->entries[i];  in qdist_pr_internal()
141         if (e->count) {  in qdist_pr_internal()
142             /* divide first to avoid loss of precision when e->count == max */  in qdist_pr_internal()
143             index = (e->count - min) / (max - min) * (QDIST_NR_BLOCK_CODES - 1);  in qdist_pr_internal()
154  * Bin the distribution in @from into @n bins of consecutive, non-overlapping
160  * Note: calling this function on an already-binned qdist is a bug.
162  * If @n == 0 or @from->n == 1, use @from->n.
172     if (from->n == 0) {  in qdist_bin__internal()
175     if (n == 0 || from->n == 1) {  in qdist_bin__internal()
176         n = from->n;  in qdist_bin__internal()
179     /* set equally-sized bins between @from's left and right */  in qdist_bin__internal()
182     step = (xmax - xmin) / n;  in qdist_bin__internal()
184     if (n == from->n) {  in qdist_bin__internal()
185         /* if @from's entries are equally spaced, no need to re-bin */  in qdist_bin__internal()
186         for (i = 0; i < from->n; i++) {  in qdist_bin__internal()
187             if (from->entries[i].x != xmin + i * step) {  in qdist_bin__internal()
192         to->entries = g_renew(struct qdist_entry, to->entries, n);  in qdist_bin__internal()
193         to->n = from->n;  in qdist_bin__internal()
194         memcpy(to->entries, from->entries, sizeof(*to->entries) * to->n);  in qdist_bin__internal()
212          * To avoid double-counting we capture [left, right) ranges, except for  in qdist_bin__internal()
215         while (j < from->n && (from->entries[j].x < right || i == n - 1)) {  in qdist_bin__internal()
216             struct qdist_entry *o = &from->entries[j];  in qdist_bin__internal()
218             qdist_add(to, x, o->count);  in qdist_bin__internal()
225  * Print @dist into a string, after re-binning it into @n bins of consecutive,
226  * non-overlapping intervals.
228  * If @n == 0, use @orig->n.
237     if (dist->n == 0) {  in qdist_pr_plain()
266     n = n_bins ? n_bins : dist->n;  in qdist_pr_label()
268     step = (qdist_xmax(dist) - qdist_xmin(dist)) / n;  in qdist_pr_label()
285             x1 = x - step;  in qdist_pr_label()
312     if (dist->n == 0) {  in qdist_pr()
332     if (dist->n == 0) {  in qdist_x()
335     return dist->entries[index].x;  in qdist_x()
345     return qdist_x(dist, dist->n - 1);  in qdist_xmax()
350     return dist->n;  in qdist_unique_entries()
358     for (i = 0; i < dist->n; i++) {  in qdist_sample_count()
359         struct qdist_entry *e = &dist->entries[i];  in qdist_sample_count()
361         count += e->count;  in qdist_sample_count()
375             struct qdist_entry *e = &dist->entries[index + i];  in qdist_pairwise_avg()
377             ret += e->x * e->count / count;  in qdist_pairwise_avg()
384                qdist_pairwise_avg(dist, index + n2, n - n2, count);  in qdist_pairwise_avg()
396     return qdist_pairwise_avg(dist, 0, dist->n, count);  in qdist_avg()