xref: /5.5.2/moxi/src/htgram.c (revision d0366df5)
1/* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2
3#include <platform/cbassert.h>
4#include <stdio.h>
5#include <stdlib.h>
6#include <string.h>
7#ifdef _MSC_VER
8#define snprintf _snprintf
9#else
10#include <strings.h>
11#endif
12#include <limits.h>
13#include <inttypes.h>
14
15#include "htgram.h"
16
17struct htgram_bin_st {
18    int64_t start;
19    int64_t width;
20    uint64_t count;
21};
22
23struct htgram_st {
24    int64_t bin_start;
25    int64_t bin_start_width;
26    double  bin_width_growth;
27    size_t  num_bins;
28
29    struct htgram_bin_st *bins;
30
31    uint64_t lt_count; /* For data points < the bins. */
32    uint64_t gt_count; /* For data points > the bins. */
33
34    /* For data points > the bins, there may be another */
35    /* histogram instead of using gt_count. */
36
37    HTGRAM_HANDLE next;
38};
39
40static void emit_bar(int64_t start, int64_t width, uint64_t count,
41                     uint64_t max_count, uint64_t tot_count, uint64_t run_count,
42                     char *buf, int buf_len,
43                     int plus_spaces, int equal_spaces, int space_spaces);
44
45HTGRAM_HANDLE htgram_mk(int64_t bin_start,
46                        int64_t bin_start_width,
47                        double  bin_width_growth,
48                        size_t  num_bins,
49                        HTGRAM_HANDLE next) {
50    int64_t r = bin_start;
51    int64_t w = bin_start_width;
52    struct htgram_st *h = calloc(sizeof(struct htgram_st), 1);
53    if (h == NULL) {
54        return NULL;
55    }
56
57    h->bin_start = bin_start;
58    h->bin_start_width = bin_start_width;
59    h->bin_width_growth = bin_width_growth;
60    h->num_bins = num_bins;
61    h->next = next;
62
63    if (num_bins > 0) {
64        size_t i;
65        h->bins = calloc(sizeof(struct htgram_bin_st), num_bins);
66        if (h->bins == NULL) {
67            free(h);
68            return NULL;
69        }
70
71        for (i = 0; i < num_bins; i++) {
72            h->bins[i].start = r;
73            h->bins[i].width = w;
74            r = r + w;
75            w = w * bin_width_growth;
76        }
77    }
78
79    return h;
80}
81
82void htgram_destroy(HTGRAM_HANDLE h) {
83    if (h->bins != NULL) {
84        free(h->bins);
85    }
86    if (h->next != NULL) {
87        htgram_destroy(h->next);
88    }
89    free(h);
90}
91
92int64_t htgram_get_bin_start(HTGRAM_HANDLE h) {
93    return h->bin_start;
94}
95
96int64_t htgram_get_bin_start_width(HTGRAM_HANDLE h) {
97    return h->bin_start_width;
98}
99
100double htgram_get_bin_width_growth(HTGRAM_HANDLE h) {
101    return h->bin_width_growth;
102}
103
104size_t htgram_get_num_bins(HTGRAM_HANDLE h) {
105    return h->num_bins;
106}
107
108void htgram_incr(HTGRAM_HANDLE h, int64_t data_point, uint64_t count) {
109    size_t i = 0;
110
111    if (data_point < h->bin_start) {
112        h->lt_count += count;
113        return;
114    }
115
116    if (h->bin_width_growth == 1.0) {
117        i = data_point / h->bin_start_width;
118    }
119
120    while (i < h->num_bins) {
121        if (data_point < (h->bins[i].start +
122                          h->bins[i].width)) {
123            h->bins[i].count += count;
124            return;
125        }
126
127        i++;
128    }
129
130    if (h->next != NULL) {
131        htgram_incr(h->next, data_point, count);
132        return;
133    }
134
135    h->gt_count += count;
136}
137
138bool htgram_get_bin_data(HTGRAM_HANDLE h, int bin_index,
139                         int64_t *out_bin_start,
140                         int64_t *out_bin_width,
141                         uint64_t *out_bin_count) {
142    if (bin_index < 0) {
143        *out_bin_count = h->lt_count;
144        return false;
145    }
146
147    if (bin_index >= (int) h->num_bins) {
148        if (h->next != NULL) {
149            return htgram_get_bin_data(h->next, bin_index - h->num_bins,
150                                       out_bin_start,
151                                       out_bin_width,
152                                       out_bin_count);
153        }
154
155        *out_bin_count = h->gt_count;
156        return false;
157    }
158
159    *out_bin_start = h->bins[bin_index].start;
160    *out_bin_width = h->bins[bin_index].width;
161    *out_bin_count = h->bins[bin_index].count;
162
163    return true;
164}
165
166void htgram_reset(HTGRAM_HANDLE h) {
167    size_t i;
168    for (i = 0; i < h->num_bins; i++) {
169        h->bins[i].count = 0;
170    }
171
172    h->lt_count = 0;
173    h->gt_count = 0;
174
175    if (h->next != NULL) {
176        htgram_reset(h->next);
177    }
178}
179
180void htgram_add(HTGRAM_HANDLE agg, HTGRAM_HANDLE x) {
181    int64_t  astart;
182    int64_t  awidth;
183    uint64_t acount;
184
185    int64_t  xstart;
186    int64_t  xwidth;
187    uint64_t xcount;
188
189    int i = 0;
190
191    while (htgram_get_bin_data(agg, i, &astart, &awidth, &acount) &&
192           htgram_get_bin_data(x,   i, &xstart, &xwidth, &xcount)) {
193        cb_assert(astart == xstart);
194        cb_assert(awidth == xwidth);
195
196        htgram_incr(agg, astart, xcount);
197
198        i++;
199    }
200}
201
202void htgram_dump(HTGRAM_HANDLE h,
203                 HTGRAM_DUMP_CALLBACK dump_callback, void *dump_callback_data) {
204    int64_t  max_start = 0;
205    int64_t  max_width = 0;
206    uint64_t max_count = 0;
207    int      end_num_bins = 0; /* Max non-zero bin. */
208    int      beg_bin = INT_MAX;
209    uint64_t tot_count = 0;
210    uint64_t run_count; /* Cummulative count. */
211    int64_t  start;
212    int64_t  width;
213    uint64_t count;
214    int      num_bins = 0;
215    int  max_plus = 0;  /* Width of the 'plus' column ('+'). */
216    int  max_equal = 0; /* Width of the 'equal' column ('='). */
217    int  max_space = 0; /* Width of the 'space' column (' '). */
218    char buf[2000];
219    int i;
220
221    if (h == NULL) {
222        return;
223    }
224
225    while (htgram_get_bin_data(h, num_bins, &start, &width, &count)) {
226        num_bins++;
227
228        if (count > 0) {
229            if (max_start < start) {
230                max_start = start;
231            }
232            if (max_width < width) {
233                max_width = width;
234            }
235            if (max_count < count) {
236                max_count = count;
237            }
238            if (end_num_bins < num_bins) {
239                end_num_bins = num_bins;
240            }
241            if (beg_bin > num_bins - 1) {
242                beg_bin = num_bins - 1;
243            }
244            tot_count = tot_count + count;
245        }
246    }
247
248    /* Columns in a row look like "START+WIDTH=COUNT PCT% BAR_GRAPH_LINE" */
249    run_count = 0;
250    for (i = beg_bin; i < end_num_bins + 1 && i < num_bins; i++) {
251        if (htgram_get_bin_data(h, i, &start, &width, &count)) {
252            char *s0, *s1, *s2;
253
254            emit_bar(start, width, count, max_count, tot_count, run_count,
255                     buf, sizeof(buf) - 1, 0, 0, 0);
256
257            s0 = strchr(buf, '+');
258            cb_assert(s0 != NULL);
259            if (max_plus < s0 - buf) {
260                max_plus = s0 - buf;
261            }
262            s1 = strchr(s0, '=');
263            cb_assert(s1 != NULL);
264            if (max_equal < s1 - s0) {
265                max_equal = s1 - s0;
266            }
267            s2 = strchr(s1, '%');
268            cb_assert(s2 != NULL);
269            if (max_space < s2 - s1) {
270                max_space = s2 - s1;
271            }
272
273            run_count += count;
274        }
275    }
276
277    run_count = 0;
278    for (i = beg_bin; i < end_num_bins + 1 && i < num_bins; i++) {
279        if (htgram_get_bin_data(h, i, &start, &width, &count)) {
280            char *s0, *s1, *s2;
281
282            emit_bar(start, width, count, max_count, tot_count, run_count,
283                     buf, sizeof(buf) - 1, 0, 0, 0);
284
285            s0 = strchr(buf, '+');
286            s1 = strchr(s0, '=');
287            s2 = strchr(s1, '%');
288
289            emit_bar(start, width, count, max_count, tot_count, run_count,
290                     buf, sizeof(buf) - 1,
291                     max_plus - (s0 - buf),
292                     max_equal - (s1 - s0),
293                     max_space - (s2 - s1));
294
295            dump_callback(h, buf, dump_callback_data);
296
297            run_count += count;
298        }
299    }
300}
301
302static void fill_spaces(char *buf, int buf_len, int num_spaces) {
303    int i;
304    for (i = 0; i < num_spaces && i < buf_len - 1; i++) {
305        buf[i] = ' ';
306    }
307    buf[i] = '\0';
308}
309
310static void emit_bar(int64_t start, int64_t width, uint64_t count,
311                     uint64_t max_count, uint64_t tot_count, uint64_t run_count,
312                     char *buf, int buf_len,
313                     int plus_spaces, int equal_spaces, int space_spaces) {
314    char bar_buf[25];
315    char plus_buf[40];
316    char equal_buf[40];
317    char space_buf[40];
318
319    size_t j = 0;
320
321    if (count > 0) {
322        uint64_t bar = (((sizeof(bar_buf) - 1) * count) / max_count);
323        while (j < bar && j < sizeof(bar_buf) - 1) {
324            bar_buf[j] = '*';
325            j++;
326        }
327    }
328    bar_buf[j] = '\0';
329
330    fill_spaces(plus_buf, sizeof(plus_buf), plus_spaces);
331    fill_spaces(equal_buf, sizeof(equal_buf), equal_spaces);
332    fill_spaces(space_buf, sizeof(space_buf), space_spaces);
333
334    snprintf(buf, buf_len - 1, "%s%"PRIu64"+%"PRIu64"%s=%"PRIu64" %s%.2f%% %s",
335             plus_buf, start, width, equal_buf, count, space_buf,
336             100.0 * ((float) (count + run_count) / (float) tot_count), bar_buf);
337}
338