cctools
bucketing.h
1 #ifndef BUCKETING_H
2 #define BUCKETING_H
3 
4 #include "list.h"
5 
6 /* all modes of bucketing */
7 typedef enum {
8  BUCKETING_MODE_GREEDY,
9  BUCKETING_MODE_EXHAUSTIVE
10 } bucketing_mode_t;
11 
12 /* Bucketing has two operations, add and predict */
13 typedef enum {
14  BUCKETING_OP_ADD = 0,
15  BUCKETING_OP_PREDICT,
16  BUCKETING_OP_NULL //only used when initializing
17 } bucketing_operation_t;
18 
19 /* Each point (e.g., a task) in a bucket is a pair of value
20  * (e.g., memory consumption) and significance
21  * (encoding relative time position of task) */
22 typedef struct
23 {
24  /* value */
25  double val;
26 
27  /* significance */
28  double sig;
30 
31 /* Each bucket is a pair of value (top delimiter) and probability
32  * that the next task falls into its range (lo, hi) where lo is
33  * the top delimiter of the right below bucket (or zero if bucket
34  * is the lowest) and hi is value */
35 typedef struct
36 {
37  /* value */
38  double val;
39 
40  /* probability */
41  double prob;
43 
44 /* State of the bucket */
45 typedef struct
46 {
48  /* a doubly linked list of pointers to points of type 'bucketing_point_t'
49  * sorted by 'point->val' in increasing order
50  * sorted_points and sequence_points share the same set of pointers */
51  struct list *sorted_points;
52 
53  /* a doubly linked list of pointers to points of type 'bucketing_point_t'
54  * sorted by 'point->sig' in increasing order
55  * sequence_points and sorted_points share the same set of pointers */
56  struct list *sequence_points;
57 
58  /* a doubly linked list of pointers to buckets of type 'bucketing_bucket_t'
59  * sorted by 'bucket->val' in increasing order */
60  struct list *sorted_buckets;
61 
62  /* total number of points */
63  int num_points;
64 
65  /* whether bucketing is in sampling phase, 1 is yes, 0 is no */
66  int in_sampling_phase;
67 
68  /* track previous operation, this helps with the decision to find
69  * buckets or not. This is -1 in the beginning as there's no previous
70  * operation. */
71  bucketing_operation_t prev_op;
72 
73  /* the significance value of the next task to be added */
74  int next_task_sig;
75 
79  /* default value to be used in sampling phase */
80  double default_value;
81 
82  /* number of points needed to transition from sampling to predicting phase */
83  int num_sampling_points;
84 
85  /* rate to increase a value when in sampling phase or exceeded max value in
86  * predicting phase */
87  double increase_rate;
88 
89  /* the maximum number of buckets to break (only exhaustive bucketing) */
90  int max_num_buckets;
91 
92  /* the update mode to use */
93  bucketing_mode_t mode;
94 
95  /* The number of iterations before another bucketing happens */
96  int update_epoch;
97 
100 
103 /* Create a bucketing bucket
104  * @param val value of bucket
105  * @param prob probability of bucket
106  * @return pointer to created bucket
107  * @return 0 if failure */
108 bucketing_bucket_t* bucketing_bucket_create(double val, double prob);
109 
110 /* Delete a bucketing bucket
111  * @param b the bucket to be deleted */
112 void bucketing_bucket_delete(bucketing_bucket_t* b);
113 
114 /* Create a bucketing state
115  * @param default_value default value in sampling state
116  * @param num_sampling_points number of needed sampling points
117  * @param increase_rate rate to increase values
118  * @param max_num_buckets the maximum number of buckets to find (only for exhaustive bucketing)
119  * @param mode specify which update mode of bucketing state
120  * @param update_epoch number of iterations to wait before updating the bucketing state
121  * @return pointer to created bucketing state
122  * @return 0 if failure */
123 bucketing_state_t* bucketing_state_create(double default_value, int num_sampling_points,
124  double increase_rate, int max_num_buckets, bucketing_mode_t mode, int update_epoch);
125 
126 /* Delete a bucketing state
127  * @param s pointer to bucketing state to be deleted */
128 void bucketing_state_delete(bucketing_state_t* s);
129 
130 /* Tune externally provided fields
131  * @param s the bucketing state
132  * @param field string describing the field, must be the same as external fields
133  * defined in bucketing state
134  * @param val value to be casted inside this function, -1 otherwise */
135 void bucketing_state_tune(bucketing_state_t* s, const char* field, void* val);
136 
137 /* Add a point
138  * @param s the relevant bucketing state
139  * @param val value of point to be added */
140 void bucketing_add(bucketing_state_t* s, double val);
141 
142 /* Predict a value, only predict when we need a new higher value, don't predict when prev value
143  * (if available) is usable
144  * @param s the relevant bucketing_state_t
145  * @param prev_val previous value to consider, -1 if no previous value,
146  * > 0 means a larger value is expected from prediction
147  * @return the predicted value
148  * @return -1 if failure */
149 double bucketing_predict(bucketing_state_t* s, double prev_val);
150 
155 /* Print a sorted list of bucketing_bucket_t
156  * @param l the list of buckets */
157 void bucketing_sorted_buckets_print(struct list* l);
158 
159 /* Print a sorted list of bucketing_point_t
160  * @param l the list of points */
161 void bucketing_sorted_points_print(struct list* l);
162 
165 #endif
bucketing_state_t::sorted_points
struct list * sorted_points
Begin: internally maintained fields.
Definition: bucketing.h:51
bucketing_state_t::default_value
double default_value
End: internally maintained fields.
Definition: bucketing.h:80
bucketing_point_t
Definition: bucketing.h:22
bucketing_state_t
Definition: bucketing.h:45
list.h
bucketing_bucket_t
Definition: bucketing.h:35