cctools
bucketing.h
1#ifndef BUCKETING_H
2#define BUCKETING_H
3
4#include "list.h"
5
6/* all modes of bucketing */
7typedef enum {
8 BUCKETING_MODE_GREEDY,
9 BUCKETING_MODE_EXHAUSTIVE
10} bucketing_mode_t;
11
12/* Bucketing has two operations, add and predict */
13typedef 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) */
22typedef 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 */
35typedef struct
36{
37 /* value */
38 double val;
39
40 /* probability */
41 double prob;
43
44/* State of the bucket */
45typedef 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 */
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 */
108bucketing_bucket_t* bucketing_bucket_create(double val, double prob);
109
110/* Delete a bucketing bucket
111 * @param b the bucket to be deleted */
112void 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 */
123bucketing_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 */
128void 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 */
135void 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 */
140void 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 */
149double 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 */
157void bucketing_sorted_buckets_print(struct list* l);
158
159/* Print a sorted list of bucketing_point_t
160 * @param l the list of points */
161void bucketing_sorted_points_print(struct list* l);
162
165#endif
Robust, reentrant linked list structure.
Definition bucketing.h:36
Definition bucketing.h:23
Definition bucketing.h:46
double default_value
End: internally maintained fields.
Definition bucketing.h:80
struct list * sorted_points
Begin: internally maintained fields.
Definition bucketing.h:51