Trivial change to compile under ultrix
[dyninst.git] / common / src / hist.C
1 /* 
2  * Copyright (c) 1992 Barton P. Miller, Morgan Clark, Timothy Torzewski,
3  *     Jeff Hollingsworth, and Bruce Irvin. All rights reserved.
4  *
5  * This software is furnished under the condition that it may not
6  * be provided or otherwise made available to, or used by, any
7  * other person.  No title to or ownership of the software is
8  * hereby transferred.  The name of the principals
9  * may not be used in any advertising or publicity related to this
10  * software without specific, written prior authorization.
11  * Any use of this software must include the above copyright notice.
12  *
13  */
14
15 /*
16  * hist.C - routines to manage hisograms.
17  *
18  * $Log: hist.C,v $
19  * Revision 1.2  1994/01/26 04:53:42  hollings
20  * Change to using <module>/h/*.h
21  *
22  * Revision 1.1  1994/01/25  20:50:25  hollings
23  * First real version of utility library.
24  *
25  * Revision 1.4  1993/12/15  21:06:23  hollings
26  * changed initial bucket width to 0.1.
27  *
28  * Revision 1.3  1993/08/11  18:03:54  hollings
29  * removed printf for folding hist.
30  *
31  * Revision 1.2  1993/08/05  18:55:08  hollings
32  * general fixups and include format.
33  *
34  * Revision 1.1  1993/05/07  20:19:17  hollings
35  * Initial revision
36  *
37  *
38  */
39
40 #include <stdio.h>
41 #include <assert.h>
42 #include <string.h>
43 #include <stdlib.h>
44
45 #include "util/h/hist.h"
46
47 /* number of intervals at which we switch to regular histograms */
48 #define MAX_INTERVALS   15
49
50 static void smoothBins(Bin *bins, int i, timeStamp bucketSize);
51
52 int Histogram::numBins = 1000;
53 timeStamp Histogram::bucketSize = 0.1;
54 timeStamp Histogram::total_time = (Histogram::numBins * Histogram::bucketSize);
55 Histogram *Histogram::allHist = NULL;
56 int Histogram::lastGlobalBin = 0;
57
58 Histogram::Histogram(metricStyle type)
59 {
60     smooth = False;
61     lastBin = 0;
62     metricType = type;
63     intervalCount = 0;
64     intervalLimit = MAX_INTERVALS;
65     storageType = HistInterval;
66     dataPtr.intervals = (Interval *) calloc(sizeof(Interval)*intervalLimit, 1);
67     next = allHist;
68     allHist = this;
69 }
70
71 /*
72  * Given an array of buckets - turn them into a histogram.
73  *
74  */
75 Histogram::Histogram(Bin *buckets, metricStyle type)
76 {
77     // First call default constructor.
78     Histogram(type);
79
80     storageType = HistBucket;
81     dataPtr.buckets = (Bin *) calloc(sizeof(Bin), numBins);
82     memcpy(dataPtr.buckets, buckets, sizeof(Bin)*numBins);
83 }
84
85 #define MAX(a, b)       ((a) > (b) ? (a):(b))
86
87 /*
88  * addInterval - add a value to a histogram from start to end.
89  *
90  * start, and end are relative to the global start time (i.e. 0.0 is the
91  *   left side of the first hist bin).
92  */
93 void Histogram::addInterval(timeStamp start, 
94                             timeStamp end, 
95                             sampleValue value, 
96                             Boolean smooth)
97 {
98     Histogram *h;
99     List<HistogramSubscriber*> currS;
100     Interval *currentInterval;
101
102
103     while ((end >= total_time) || (start >= total_time)) {
104         // colapse histogram.
105         foldAllHist();
106     }
107
108     lastBin = (int) (end / bucketSize);
109     lastGlobalBin = lastBin;
110     for (h=allHist; h; h=h->next) {
111         if ((h->status == histActive) && (h->lastBin < lastGlobalBin)) {
112             lastGlobalBin = h->lastBin;
113         }
114     }
115
116     if (value == 0.0) return;
117
118     if (storageType == HistInterval) {
119         if (intervalCount == intervalLimit) {
120             intervalLimit *= 2;
121             if (intervalLimit * sizeof(Interval) < 
122                 numBins * sizeof(Bin)) {
123                 dataPtr.intervals = (Interval *) 
124                     realloc(dataPtr.intervals, 
125                     sizeof(Interval)*intervalLimit);
126                     goto normal;
127             } else {
128                 /* convert to buckets */
129                 convertToBins();
130                 bucketValue(start, end, value, smooth);
131             }
132         } else {
133 normal:
134             currentInterval = &(dataPtr.intervals[intervalCount]);
135             assert(start >= 0.0);
136             assert(start <= total_time);
137             currentInterval->start = start;
138
139             assert(end >= 0.0);
140             assert(end <= total_time);
141             currentInterval->end = end;
142
143             currentInterval->value = value;
144             intervalCount++;
145         }
146     } else {
147         bucketValue(start, end, value, smooth);
148     }
149     for (currS = subscribers; *currS; currS++) {
150         (*currS)->callBack(HistNewValue, end, (*currS)->userData);
151     }
152 }
153
154 void Histogram::convertToBins()
155 {
156     int i;
157     Interval *intervals;
158     Interval *currentInterval;
159
160     if (storageType == HistBucket) return;
161
162     intervals = dataPtr.intervals;
163     dataPtr.buckets = (Bin *) calloc(sizeof(Bin), numBins);
164     memset(dataPtr.buckets, '\0', sizeof(Bin)*numBins);
165     for (i=0; i < intervalCount; i++) {
166         currentInterval = &(intervals[i]);
167         bucketValue(currentInterval->start, currentInterval->end, 
168             currentInterval->value, smooth);
169     }
170     free(intervals);
171     intervalCount = -1;
172     intervalLimit = 0;
173     storageType = HistBucket;
174 }
175
176 void Histogram::foldAllHist()
177 {
178     int i;
179     Bin *bins;
180     Histogram *curr;
181     List<HistogramSubscriber*> currS;
182
183
184     bucketSize *= 2.0;
185     total_time = (numBins * bucketSize);
186
187     lastGlobalBin = 0;
188     for (curr=allHist; curr; curr= curr->next) {
189         // fold individual hist.
190         if (curr->storageType == HistBucket) {
191             bins = curr->dataPtr.buckets;
192             for (i=0; i < numBins/2; i++) {
193                 bins[i] = bins[i*2] + bins[i*2+1];
194             }
195             curr->lastBin = i-1;
196             memset(&bins[i], '\0', (numBins - i) * sizeof(Bin));
197         }
198         for (currS = curr->subscribers; *currS; currS++) {
199             (*currS)->callBack(HistNewTimeBase, bucketSize, (*currS)->userData);
200         }
201     }
202 }
203
204 int Histogram::subscribe(timeStamp maxRate, 
205                            subscriberCallBack func, 
206                            void *userData)
207 {
208     HistogramSubscriber *curr;
209
210     curr = new HistogramSubscriber(maxRate, func, userData);
211     subscribers.add(curr);
212     return((int) curr);
213 }
214
215 void Histogram::bucketValue(timeStamp start_clock, 
216                            timeStamp end_clock, 
217                            sampleValue value, 
218                            Boolean smooth)
219 {
220     register int i;
221     int first_bin, last_bin;
222     timeStamp elapsed_clock = (timeStamp) 0.0;
223     timeStamp first_bin_start, last_bin_start;
224     sampleValue amt_first_bin, amt_last_bin, amt_other_bins;
225     timeStamp time_in_first_bin, time_in_last_bin, time_in_other_bins;
226
227
228     elapsed_clock = end_clock - start_clock;
229
230     /* set starting and ending bins */
231     first_bin = (int) (start_clock / bucketSize);
232     assert(first_bin >= 0);
233     assert(first_bin <= numBins);
234     if (first_bin == numBins)
235         first_bin = numBins-1;
236     last_bin = (int) (end_clock / bucketSize);
237     assert(last_bin >= 0);
238     assert(last_bin <= numBins);
239     if (last_bin == numBins)
240         last_bin = numBins-1;
241     /* set starting times for first & last bins */
242     first_bin_start = bucketSize * first_bin;
243     last_bin_start = bucketSize  * last_bin;
244
245     if (metricType == SampledFunction) {
246         for (i=first_bin; i <= last_bin; i++) {
247             dataPtr.buckets[i] = value * bucketSize;
248         }
249     } else {
250         if (last_bin == first_bin) {
251             dataPtr.buckets[first_bin] += value;
252             if (smooth && (dataPtr.buckets[first_bin] > bucketSize)) {
253                 /* value > 100% */
254                 smoothBins(dataPtr.buckets, first_bin, bucketSize);
255             }
256             return;
257         }
258
259         /* determine how much of the first & last bins were in this interval */
260         time_in_first_bin = bucketSize - (start_clock - first_bin_start);
261         time_in_last_bin = end_clock - last_bin_start;
262         time_in_other_bins = 
263             MAX(elapsed_clock - (time_in_first_bin + time_in_last_bin), 0);
264
265         /* determine how much of value should be in each bin in the interval */
266         amt_first_bin = (time_in_first_bin / elapsed_clock) * value;
267         amt_last_bin  = (time_in_last_bin  / elapsed_clock) * value;
268         amt_other_bins = (time_in_other_bins / elapsed_clock) * value;
269         if (last_bin > first_bin+1) 
270             amt_other_bins /= (last_bin - first_bin) - 1.0;
271
272         /* add the appropriate amount of time to each bin */
273         dataPtr.buckets[first_bin] += amt_first_bin;
274         dataPtr.buckets[last_bin]  += amt_last_bin;
275         for (i=first_bin+1; i < last_bin; i++)
276             dataPtr.buckets[i]  += amt_other_bins;
277     }
278
279     /* limit absurd time values - anything over 100% is pushed back into 
280        previous buckets */
281     if (smooth) {
282         for (i = first_bin; i <= last_bin; i++) {
283             if (dataPtr.buckets[i] > bucketSize) 
284                 smoothBins(dataPtr.buckets, i, bucketSize);
285         }
286     }
287 }
288
289
290 static void smoothBins(Bin *bins, int i, timeStamp bucketSize)
291 {
292     int j;
293     sampleValue extra_time;
294
295     extra_time = (bins[i] - bucketSize);
296     bins[i] = bucketSize;
297     j = i - 1;
298     while ((j >= 0) && (extra_time > 0.0)) {
299         bins[j] += extra_time;
300         extra_time = 0.0;
301         if (bins[j] > bucketSize) {
302             extra_time = (bins[j] - bucketSize);
303             bins[j] = bucketSize;
304         }
305         j--;
306     }
307     if (extra_time > 0.0) {
308         fprintf(stderr, "**** Unable to bucket %f seconds\n", extra_time);
309         abort();
310     }
311 }
312
313
314 static double splitTime(timeStamp startInterval, 
315                         timeStamp endInterval, 
316                         timeStamp startLimit, 
317                         timeStamp endLimit, 
318                         sampleValue value)
319 {
320     sampleValue time;
321     timeStamp inv_length;
322
323     inv_length = endInterval-startInterval;
324     if ((startInterval >= startLimit) && (endInterval <= endLimit)) {   
325         time = value;
326     } else if (startInterval == endInterval) {  
327         /* can't split delta functions */               
328         time = 0.0;
329     } else if ((startInterval >= startLimit) && (startInterval <= endLimit)) {
330         /* overlaps the end */                          
331         time = value * (endLimit - startInterval) / inv_length;
332     } else if ((endInterval <= endLimit) && (endInterval >= startLimit)) { 
333         /* overlaps the end */                          
334         time = value * (endInterval - startLimit) / inv_length;    
335     } else if ((startInterval < startLimit) && (endInterval > endLimit)) {
336         /* detail contains interval */
337         time = value * (endLimit - startLimit) / inv_length;
338     } else {
339         /* no overlap of time */
340         time = 0.0;
341     }
342     return(time);
343 }
344
345 /*
346  * Get the component of the histogram from start to end.
347  *
348  */
349 sampleValue Histogram::getValue(timeStamp start, timeStamp end)
350 {               
351     int i;
352     Interval *cp;
353     sampleValue retVal = 0.0;
354     int first_bin, last_bin;
355     double pct_first_bin, pct_last_bin;
356
357     if (storageType == HistInterval) {
358         if (metricType == SampledFunction) {
359             // compute weight average of sample.
360             for (i=0; i < intervalCount; i++) {
361                 cp = &(dataPtr.intervals[i]);
362                 retVal += cp->value * (cp->end - cp->start);
363             }
364         } else {
365             // total over the interval.
366             for (i=0; i < intervalCount; i++) {
367                 cp = &(dataPtr.intervals[i]);
368                 retVal += splitTime(cp->start, cp->end, start, end, cp->value);
369             }
370         }
371     } else {
372         first_bin = (int) (start/bucketSize);
373         /* round up */
374         last_bin = (int) (end/bucketSize+0.5);
375         if (last_bin >= numBins) last_bin = numBins-1;
376         if (first_bin == last_bin) {
377             retVal = dataPtr.buckets[first_bin];
378         } else {
379             /* (first_bin+1)*bucketSize == time at end of first bucket */
380             pct_first_bin = (((first_bin+1)*bucketSize)-start)/bucketSize;
381             retVal += pct_first_bin * dataPtr.buckets[first_bin];
382             /* last_bin+*bucketSize == time at start of last bucket */
383             pct_last_bin = (end - last_bin*bucketSize)/bucketSize;
384             retVal += pct_last_bin * dataPtr.buckets[last_bin];
385             for (i=first_bin+1; i <= last_bin-1; i++) {
386                 retVal += dataPtr.buckets[i];
387             }
388         }
389     }
390     return(retVal);
391 }
392
393 sampleValue Histogram::getValue()
394 {               
395     return(getValue(0.0, numBins * bucketSize));
396 }
397
398 HistogramSubscriber::HistogramSubscriber(timeStamp max, 
399                                          subscriberCallBack func, 
400                                          void *u)
401 {
402     interval = max;
403     userData = u;
404     callBack = func;
405 }