diff options
Diffstat (limited to 'test/utils.cpp')
| -rw-r--r-- | test/utils.cpp | 295 |
1 files changed, 205 insertions, 90 deletions
diff --git a/test/utils.cpp b/test/utils.cpp index b53e4e4..4e41d8f 100644 --- a/test/utils.cpp +++ b/test/utils.cpp @@ -8,7 +8,10 @@ #include <random> #include <string.h> #include <algorithm> - +#include <fstream> +#include <math.h> +#include <unistd.h> +#include <sstream> #include "fieldstat.h" #include "utils.hpp" @@ -32,24 +35,24 @@ string gen_rand_string(int len) /* taglist wrapper */ /* -------------------------------------------------------------------------- */ -Fieldstat_tag_list_wrapper::Fieldstat_tag_list_wrapper(const struct fieldstat_tag_list *tag_list) { - tag_list_c.tag = (struct fieldstat_tag *)malloc(sizeof(struct fieldstat_tag) * tag_list->n_tag); - tag_list_c.n_tag = tag_list->n_tag; - for (size_t i = 0; i < tag_list->n_tag; i++) +Fieldstat_tag_list_wrapper::Fieldstat_tag_list_wrapper(const struct field_list *tag_list) { + tag_list_c.field = (struct field *)malloc(sizeof(struct field) * tag_list->n_field); + tag_list_c.n_field = tag_list->n_field; + for (size_t i = 0; i < tag_list->n_field; i++) { // copy the tag_list - tag_list_c.tag[i].key = strdup(tag_list->tag[i].key); - tag_list_c.tag[i].type = tag_list->tag[i].type; - switch (tag_list->tag[i].type) + tag_list_c.field[i].key = strdup(tag_list->field[i].key); + tag_list_c.field[i].type = tag_list->field[i].type; + switch (tag_list->field[i].type) { - case TAG_INTEGER: - tag_list_c.tag[i].value_longlong = tag_list->tag[i].value_longlong; + case FIELD_VALUE_INTEGER: + tag_list_c.field[i].value_longlong = tag_list->field[i].value_longlong; break; - case TAG_DOUBLE: - tag_list_c.tag[i].value_double = tag_list->tag[i].value_double; + case FIELD_VALUE_DOUBLE: + tag_list_c.field[i].value_double = tag_list->field[i].value_double; break; - case TAG_CSTRING: - tag_list_c.tag[i].value_str = strdup(tag_list->tag[i].value_str); + case FIELD_VALUE_CSTRING: + tag_list_c.field[i].value_str = strdup(tag_list->field[i].value_str); break; default: break; @@ -59,84 +62,84 @@ Fieldstat_tag_list_wrapper::Fieldstat_tag_list_wrapper(const struct fieldstat_ta Fieldstat_tag_list_wrapper::Fieldstat_tag_list_wrapper(const char * key, int value) { - tag_list_c.tag = (struct fieldstat_tag *)malloc(sizeof(struct fieldstat_tag)); - tag_list_c.n_tag = 1; - tag_list_c.tag[0].key = strdup(key); - tag_list_c.tag[0].type = TAG_INTEGER; - tag_list_c.tag[0].value_longlong = value; + tag_list_c.field = (struct field *)malloc(sizeof(struct field)); + tag_list_c.n_field = 1; + tag_list_c.field[0].key = strdup(key); + tag_list_c.field[0].type = FIELD_VALUE_INTEGER; + tag_list_c.field[0].value_longlong = value; } Fieldstat_tag_list_wrapper::Fieldstat_tag_list_wrapper(const char * key, const char *value) { - tag_list_c.tag = (struct fieldstat_tag *)malloc(sizeof(struct fieldstat_tag)); - tag_list_c.n_tag = 1; - tag_list_c.tag[0].key = strdup(key); - tag_list_c.tag[0].type = TAG_CSTRING; - tag_list_c.tag[0].value_str = strdup(value); + tag_list_c.field = (struct field *)malloc(sizeof(struct field)); + tag_list_c.n_field = 1; + tag_list_c.field[0].key = strdup(key); + tag_list_c.field[0].type = FIELD_VALUE_CSTRING; + tag_list_c.field[0].value_str = strdup(value); } Fieldstat_tag_list_wrapper::~Fieldstat_tag_list_wrapper() { - for (size_t i = 0; i < tag_list_c.n_tag; i++) { - free((char *)tag_list_c.tag[i].key); - if (tag_list_c.tag[i].type == TAG_CSTRING) { - free((char *)tag_list_c.tag[i].value_str); + for (size_t i = 0; i < tag_list_c.n_field; i++) { + free((char *)tag_list_c.field[i].key); + if (tag_list_c.field[i].type == FIELD_VALUE_CSTRING) { + free((char *)tag_list_c.field[i].value_str); } } - free(tag_list_c.tag); + free(tag_list_c.field); } Fieldstat_tag_list_wrapper::Fieldstat_tag_list_wrapper(std::uniform_int_distribution<int> &dist, int tag_count) { - tag_list_c.tag = (struct fieldstat_tag *)malloc(sizeof(struct fieldstat_tag) * tag_count); - tag_list_c.n_tag = tag_count; + tag_list_c.field = (struct field *)malloc(sizeof(struct field) * tag_count); + tag_list_c.n_field = tag_count; std::mt19937 rng(1); for (int i = 0; i < tag_count; i++) { - tag_list_c.tag[i].key = strdup(gen_rand_string(10).c_str()); + tag_list_c.field[i].key = strdup(gen_rand_string(10).c_str()); int rand_ret = rand() % 3; if (rand_ret == 0) { - tag_list_c.tag[i].type = TAG_INTEGER; - tag_list_c.tag[i].value_longlong = static_cast<long long>(dist(rng)); + tag_list_c.field[i].type = FIELD_VALUE_INTEGER; + tag_list_c.field[i].value_longlong = static_cast<long long>(dist(rng)); } else if (rand_ret == 1) { - tag_list_c.tag[i].type = TAG_DOUBLE; - tag_list_c.tag[i].value_double = static_cast<double>(dist(rng)) + 0.5; + tag_list_c.field[i].type = FIELD_VALUE_DOUBLE; + tag_list_c.field[i].value_double = static_cast<double>(dist(rng)) + 0.5; } else { - tag_list_c.tag[i].type = TAG_CSTRING; - tag_list_c.tag[i].value_str = strdup(gen_rand_string(10).c_str()); + tag_list_c.field[i].type = FIELD_VALUE_CSTRING; + tag_list_c.field[i].value_str = strdup(gen_rand_string(10).c_str()); } } } Fieldstat_tag_list_wrapper::Fieldstat_tag_list_wrapper() { - tag_list_c.tag = NULL; - tag_list_c.n_tag = 0; + tag_list_c.field = NULL; + tag_list_c.n_field = 0; } Fieldstat_tag_list_wrapper::Fieldstat_tag_list_wrapper(const Fieldstat_tag_list_wrapper &tag_list_wrapper){ - const struct fieldstat_tag_list *tag_list = tag_list_wrapper.get_c_struct(); - tag_list_c.tag = (struct fieldstat_tag *)malloc(sizeof(struct fieldstat_tag) * tag_list->n_tag); - tag_list_c.n_tag = tag_list->n_tag; - for (size_t i = 0; i < tag_list->n_tag; i++) + const struct field_list *tag_list = tag_list_wrapper.get_c_struct(); + tag_list_c.field = (struct field *)malloc(sizeof(struct field) * tag_list->n_field); + tag_list_c.n_field = tag_list->n_field; + for (size_t i = 0; i < tag_list->n_field; i++) { // copy the tag_list - tag_list_c.tag[i].key = strdup(tag_list->tag[i].key); - tag_list_c.tag[i].type = tag_list->tag[i].type; - switch (tag_list->tag[i].type) + tag_list_c.field[i].key = strdup(tag_list->field[i].key); + tag_list_c.field[i].type = tag_list->field[i].type; + switch (tag_list->field[i].type) { - case TAG_INTEGER: - tag_list_c.tag[i].value_longlong = tag_list->tag[i].value_longlong; + case FIELD_VALUE_INTEGER: + tag_list_c.field[i].value_longlong = tag_list->field[i].value_longlong; break; - case TAG_DOUBLE: - tag_list_c.tag[i].value_double = tag_list->tag[i].value_double; + case FIELD_VALUE_DOUBLE: + tag_list_c.field[i].value_double = tag_list->field[i].value_double; break; - case TAG_CSTRING: - tag_list_c.tag[i].value_str = strdup(tag_list->tag[i].value_str); + case FIELD_VALUE_CSTRING: + tag_list_c.field[i].value_str = strdup(tag_list->field[i].value_str); break; default: break; @@ -144,38 +147,38 @@ Fieldstat_tag_list_wrapper::Fieldstat_tag_list_wrapper(const Fieldstat_tag_list_ } } -const struct fieldstat_tag *Fieldstat_tag_list_wrapper::get_tag() const +const struct field *Fieldstat_tag_list_wrapper::get_tag() const { - return tag_list_c.tag; + return tag_list_c.field; } size_t Fieldstat_tag_list_wrapper::get_tag_count() const { - return tag_list_c.n_tag; + return tag_list_c.n_field; } -const struct fieldstat_tag_list *Fieldstat_tag_list_wrapper::get_c_struct() const +const struct field_list *Fieldstat_tag_list_wrapper::get_c_struct() const { return &tag_list_c; } void Fieldstat_tag_list_wrapper::print_tag_list() const { - printf("tag_list_c.n_tag: %zu\n", tag_list_c.n_tag); - for (size_t i = 0; i < tag_list_c.n_tag; i++) + printf("tag_list_c.n_field: %zu\n", tag_list_c.n_field); + for (size_t i = 0; i < tag_list_c.n_field; i++) { - printf("tag_list_c.tag[%zu].key: %s\n", i, tag_list_c.tag[i].key); - printf("tag_list_c.tag[%zu].type: %d\n", i, (int)tag_list_c.tag[i].type); - switch (tag_list_c.tag[i].type) + printf("tag_list_c.field[%zu].key: %s\n", i, tag_list_c.field[i].key); + printf("tag_list_c.field[%zu].type: %d\n", i, (int)tag_list_c.field[i].type); + switch (tag_list_c.field[i].type) { - case TAG_INTEGER: - printf("tag_list_c.tag[%zu].value_longlong: %lld\n", i, tag_list_c.tag[i].value_longlong); + case FIELD_VALUE_INTEGER: + printf("tag_list_c.field[%zu].value_longlong: %lld\n", i, tag_list_c.field[i].value_longlong); break; - case TAG_DOUBLE: - printf("tag_list_c.tag[%zu].value_double: %lf\n", i, tag_list_c.tag[i].value_double); + case FIELD_VALUE_DOUBLE: + printf("tag_list_c.field[%zu].value_double: %lf\n", i, tag_list_c.field[i].value_double); break; - case TAG_CSTRING: - printf("tag_list_c.tag[%zu].value_str: %s\n", i, tag_list_c.tag[i].value_str); + case FIELD_VALUE_CSTRING: + printf("tag_list_c.field[%zu].value_str: %s\n", i, tag_list_c.field[i].value_str); break; default: break; @@ -187,20 +190,20 @@ void Fieldstat_tag_list_wrapper::print_tag_list() const string Fieldstat_tag_list_wrapper::to_string() const { string str = ""; - for (size_t i = 0; i < tag_list_c.n_tag; i++) + for (size_t i = 0; i < tag_list_c.n_field; i++) { - str += tag_list_c.tag[i].key; + str += tag_list_c.field[i].key; str += ":"; - switch (tag_list_c.tag[i].type) + switch (tag_list_c.field[i].type) { - case TAG_INTEGER: - str += std::to_string(tag_list_c.tag[i].value_longlong); + case FIELD_VALUE_INTEGER: + str += std::to_string(tag_list_c.field[i].value_longlong); break; - case TAG_DOUBLE: - str += std::to_string(tag_list_c.tag[i].value_double); + case FIELD_VALUE_DOUBLE: + str += std::to_string(tag_list_c.field[i].value_double); break; - case TAG_CSTRING: - str += tag_list_c.tag[i].value_str; + case FIELD_VALUE_CSTRING: + str += tag_list_c.field[i].value_str; break; default: break; @@ -212,30 +215,30 @@ string Fieldstat_tag_list_wrapper::to_string() const bool Fieldstat_tag_list_wrapper::operator==(const Fieldstat_tag_list_wrapper &tag_list_wrapper) const { - const struct fieldstat_tag_list *tag_list = tag_list_wrapper.get_c_struct(); - if (tag_list_c.n_tag != tag_list->n_tag) { + const struct field_list *tag_list = tag_list_wrapper.get_c_struct(); + if (tag_list_c.n_field != tag_list->n_field) { return false; } - for (size_t i = 0; i < tag_list_c.n_tag; i++) { - if (strcmp((char *)tag_list_c.tag[i].key, (char *)tag_list->tag[i].key) != 0) { + for (size_t i = 0; i < tag_list_c.n_field; i++) { + if (strcmp((char *)tag_list_c.field[i].key, (char *)tag_list->field[i].key) != 0) { return false; } - if (tag_list_c.tag[i].type != tag_list->tag[i].type) { + if (tag_list_c.field[i].type != tag_list->field[i].type) { return false; } - switch (tag_list_c.tag[i].type) { - case TAG_INTEGER: - if (tag_list_c.tag[i].value_longlong != tag_list->tag[i].value_longlong) { + switch (tag_list_c.field[i].type) { + case FIELD_VALUE_INTEGER: + if (tag_list_c.field[i].value_longlong != tag_list->field[i].value_longlong) { return false; } break; - case TAG_DOUBLE: - if (tag_list_c.tag[i].value_double != tag_list->tag[i].value_double) { + case FIELD_VALUE_DOUBLE: + if (tag_list_c.field[i].value_double != tag_list->field[i].value_double) { return false; } break; - case TAG_CSTRING: - if (strcmp((char *)tag_list_c.tag[i].value_str, (char *)tag_list->tag[i].value_str) != 0) { + case FIELD_VALUE_CSTRING: + if (strcmp((char *)tag_list_c.field[i].value_str, (char *)tag_list->field[i].value_str) != 0) { return false; } break; @@ -248,7 +251,7 @@ bool Fieldstat_tag_list_wrapper::operator==(const Fieldstat_tag_list_wrapper &ta Fieldstat_tag_list_wrapper& Fieldstat_tag_list_wrapper::sort_tag_list() { - std::sort(tag_list_c.tag, tag_list_c.tag + tag_list_c.n_tag, [](const struct fieldstat_tag &a, const struct fieldstat_tag &b) { + std::sort(tag_list_c.field, tag_list_c.field + tag_list_c.n_field, [](const struct field &a, const struct field &b) { return strcmp((char *)a.key, (char *)b.key) < 0; }); return *this; @@ -293,3 +296,115 @@ double test_cal_topk_accuracy(vector<struct Fieldstat_tag_list_wrapper *> &test_ double accuracy = (double)correct / test_result.size(); return accuracy; } + + +//=========================================================================== +//= Function to generate Zipf (power law) distributed random variables = +//= - Input: alpha and N = +//= - Output: Returns with Zipf distributed random variable = +//=========================================================================== +int zipf(double alpha, int n) +{ + static bool first = true; // Static first time flag + static double c = 0; // Normalization constant + double z; // Uniform random number (0 < z < 1) + double sum_prob; // Sum of probabilities + double zipf_value; // Computed exponential value to be returned + int i; // Loop counter + + // Compute normalization constant on first call only + if (first) + { + for (i=1; i<=n; i++) + c = c + (1.0 / pow((double) i, alpha)); + c = 1.0 / c; + first = false; + } + + // Pull a uniform random number (0 < z < 1) + do + { + z = (double)rand() / (double)RAND_MAX; + } + while ((z == 0.0) || (z == 1.0)); + + // Map z to the value + sum_prob = 0; + for (i=1; i<=n; i++) + { + sum_prob = sum_prob + c / pow((double) i, alpha); + if (sum_prob >= z) + { + zipf_value = i; + break; + } + } + + return(zipf_value); +} + +SpreadSketchZipfGenerator::SpreadSketchZipfGenerator(double alpha, int n) { + _alpha = alpha; + _n = n; + cursor = 0; + + // generate data and write them to file + std::string filename = "zipf_" + std::to_string(alpha) + "_" + std::to_string(n) + ".txt"; + + std::unordered_map<int, int> fanout_map; // src_ip_id -> fanout being used + + if (access(filename.c_str(), F_OK) != 0) { + printf("file %s not found, generating data\n", filename.c_str()); + + std::ofstream file(filename); + if (!file.is_open()) { + printf("failed to open file %s\n", filename.c_str()); + return; + } + + for (int i = 0; i < MAX_DATA; i++) { + int src_id = zipf(alpha, n); + int fanout = fanout_map.find(src_id) == fanout_map.end() ? 0 : fanout_map[src_id]; + fanout_map[src_id] = fanout + 1; + + file << "s_" << src_id << " d_" << fanout << std::endl; + } + + file.close(); + printf("data generated and saved to file %s\n", filename.c_str()); + } + + // load data + std::ifstream file(filename); + if (!file.is_open()) { + printf("failed to open file %s\n", filename.c_str()); + return; + } + + loadeds = new std::vector<std::pair<std::string, std::string>>; + std::string line; + while (std::getline(file, line)) { + std::istringstream iss(line); + std::string src_ip, dst_ip; + iss >> src_ip >> dst_ip; + loadeds->push_back(std::make_pair(src_ip, dst_ip)); + } + file.close(); + +} + +SpreadSketchZipfGenerator::~SpreadSketchZipfGenerator() { + delete loadeds; +} + +struct Flow SpreadSketchZipfGenerator::next() { + int r_cursor = cursor % loadeds->size(); + struct Flow flow; + + flow.src_ip = loadeds->at(r_cursor).first; + flow.dst_ip = loadeds->at(r_cursor).second; + + cursor++; + + return flow; +}
\ No newline at end of file |