blob: e19a74a50de4e34d4e4e1bcc50b18f9ed6388192 [file] [log] [blame]
/*
*
* Tests for upb_table.
*/
#include <limits.h>
#include <string.h>
#include <sys/resource.h>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>
#include "tests/upb_test.h"
#include "upb/table.int.h"
#include "upb/port_def.inc"
// Convenience interface for C++. We don't put this in upb itself because
// the table is not exposed to users.
namespace upb {
template <class T> upb_value MakeUpbValue(T val);
template <class T> T GetUpbValue(upb_value val);
template <class T> upb_ctype_t GetUpbValueType();
#define FUNCS(name, type_t, enumval) \
template<> upb_value MakeUpbValue<type_t>(type_t val) { return upb_value_ ## name(val); } \
template<> type_t GetUpbValue<type_t>(upb_value val) { return upb_value_get ## name(val); } \
template<> upb_ctype_t GetUpbValueType<type_t>() { return enumval; }
FUNCS(int32, int32_t, UPB_CTYPE_INT32)
FUNCS(int64, int64_t, UPB_CTYPE_INT64)
FUNCS(uint32, uint32_t, UPB_CTYPE_UINT32)
FUNCS(uint64, uint64_t, UPB_CTYPE_UINT64)
FUNCS(bool, bool, UPB_CTYPE_BOOL)
FUNCS(cstr, char*, UPB_CTYPE_CSTR)
FUNCS(ptr, void*, UPB_CTYPE_PTR)
FUNCS(constptr, const void*, UPB_CTYPE_CONSTPTR)
FUNCS(fptr, upb_func*, UPB_CTYPE_FPTR)
#undef FUNCS
class IntTable {
public:
IntTable(upb_ctype_t value_type) { upb_inttable_init(&table_, value_type); }
~IntTable() { upb_inttable_uninit(&table_); }
size_t count() { return upb_inttable_count(&table_); }
bool Insert(uintptr_t key, upb_value val) {
return upb_inttable_insert(&table_, key, val);
}
bool Replace(uintptr_t key, upb_value val) {
return upb_inttable_replace(&table_, key, val);
}
std::pair<bool, upb_value> Remove(uintptr_t key) {
std::pair<bool, upb_value> ret;
ret.first = upb_inttable_remove(&table_, key, &ret.second);
return ret;
}
std::pair<bool, upb_value> Lookup(uintptr_t key) const {
std::pair<bool, upb_value> ret;
ret.first = upb_inttable_lookup(&table_, key, &ret.second);
return ret;
}
std::pair<bool, upb_value> Lookup32(uint32_t key) const {
std::pair<bool, upb_value> ret;
ret.first = upb_inttable_lookup32(&table_, key, &ret.second);
return ret;
}
void Compact() { upb_inttable_compact(&table_); }
class iterator : public std::iterator<std::forward_iterator_tag,
std::pair<uintptr_t, upb_value> > {
public:
explicit iterator(IntTable* table) {
upb_inttable_begin(&iter_, &table->table_);
}
static iterator end(IntTable* table) {
iterator iter(table);
upb_inttable_iter_setdone(&iter.iter_);
return iter;
}
void operator++() {
return upb_inttable_next(&iter_);
}
std::pair<uintptr_t, upb_value> operator*() const {
std::pair<uintptr_t, upb_value> ret;
ret.first = upb_inttable_iter_key(&iter_);
ret.second = upb_inttable_iter_value(&iter_);
return ret;
}
bool operator==(const iterator& other) const {
return upb_inttable_iter_isequal(&iter_, &other.iter_);
}
bool operator!=(const iterator& other) const {
return !(*this == other);
}
private:
upb_inttable_iter iter_;
};
upb_inttable table_;
};
class StrTable {
public:
StrTable(upb_ctype_t value_type) { upb_strtable_init(&table_, value_type); }
~StrTable() { upb_strtable_uninit(&table_); }
size_t count() { return upb_strtable_count(&table_); }
bool Insert(const std::string& key, upb_value val) {
return upb_strtable_insert2(&table_, key.c_str(), key.size(), val);
}
std::pair<bool, upb_value> Remove(const std::string& key) {
std::pair<bool, upb_value> ret;
ret.first =
upb_strtable_remove2(&table_, key.c_str(), key.size(), &ret.second);
return ret;
}
std::pair<bool, upb_value> Lookup(const std::string& key) const {
std::pair<bool, upb_value> ret;
ret.first =
upb_strtable_lookup2(&table_, key.c_str(), key.size(), &ret.second);
return ret;
}
void Resize(size_t size_lg2) {
upb_strtable_resize(&table_, size_lg2, &upb_alloc_global);
}
class iterator : public std::iterator<std::forward_iterator_tag,
std::pair<std::string, upb_value> > {
public:
explicit iterator(StrTable* table) {
upb_strtable_begin(&iter_, &table->table_);
}
static iterator end(StrTable* table) {
iterator iter(table);
upb_strtable_iter_setdone(&iter.iter_);
return iter;
}
void operator++() {
return upb_strtable_next(&iter_);
}
std::pair<std::string, upb_value> operator*() const {
std::pair<std::string, upb_value> ret;
upb_strview view = upb_strtable_iter_key(&iter_);
ret.first.assign(view.data, view.size);
ret.second = upb_strtable_iter_value(&iter_);
return ret;
}
bool operator==(const iterator& other) const {
return upb_strtable_iter_isequal(&iter_, &other.iter_);
}
bool operator!=(const iterator& other) const {
return !(*this == other);
}
private:
upb_strtable_iter iter_;
};
upb_strtable table_;
};
template <class T> class TypedStrTable {
public:
TypedStrTable() : table_(GetUpbValueType<T>()) {}
size_t count() { return table_.count(); }
bool Insert(const std::string &key, T val) {
return table_.Insert(key, MakeUpbValue<T>(val));
}
std::pair<bool, T> Remove(const std::string& key) {
std::pair<bool, upb_value> found = table_.Remove(key);
std::pair<bool, T> ret;
ret.first = found.first;
if (ret.first) {
ret.second = GetUpbValue<T>(found.second);
}
return ret;
}
std::pair<bool, T> Lookup(const std::string& key) const {
std::pair<bool, upb_value> found = table_.Lookup(key);
std::pair<bool, T> ret;
ret.first = found.first;
if (ret.first) {
ret.second = GetUpbValue<T>(found.second);
}
return ret;
}
void Resize(size_t size_lg2) {
table_.Resize(size_lg2);
}
class iterator : public std::iterator<std::forward_iterator_tag, std::pair<std::string, T> > {
public:
explicit iterator(TypedStrTable* table) : iter_(&table->table_) {}
static iterator end(TypedStrTable* table) {
iterator iter(table);
iter.iter_ = StrTable::iterator::end(&table->table_);
return iter;
}
void operator++() { ++iter_; }
std::pair<std::string, T> operator*() const {
std::pair<std::string, upb_value> val = *iter_;
std::pair<std::string, T> ret;
ret.first = val.first;
ret.second = GetUpbValue<T>(val.second);
return ret;
}
bool operator==(const iterator& other) const {
return iter_ == other.iter_;
}
bool operator!=(const iterator& other) const {
return iter_ != other.iter_;
}
private:
StrTable::iterator iter_;
};
iterator begin() { return iterator(this); }
iterator end() { return iterator::end(this); }
StrTable table_;
};
template <class T> class TypedIntTable {
public:
TypedIntTable() : table_(GetUpbValueType<T>()) {}
size_t count() { return table_.count(); }
bool Insert(uintptr_t key, T val) {
return table_.Insert(key, MakeUpbValue<T>(val));
}
bool Replace(uintptr_t key, T val) {
return table_.Replace(key, MakeUpbValue<T>(val));
}
std::pair<bool, T> Remove(uintptr_t key) {
std::pair<bool, upb_value> found = table_.Remove(key);
std::pair<bool, T> ret;
ret.first = found.first;
if (ret.first) {
ret.second = GetUpbValue<T>(found.second);
}
return ret;
}
std::pair<bool, T> Lookup(uintptr_t key) const {
std::pair<bool, upb_value> found = table_.Lookup(key);
std::pair<bool, T> ret;
ret.first = found.first;
if (ret.first) {
ret.second = GetUpbValue<T>(found.second);
}
return ret;
}
void Compact() { table_.Compact(); }
class iterator : public std::iterator<std::forward_iterator_tag, std::pair<uintptr_t, T> > {
public:
explicit iterator(TypedIntTable* table) : iter_(&table->table_) {}
static iterator end(TypedIntTable* table) {
return IntTable::iterator::end(&table->table_);
}
void operator++() { ++iter_; }
std::pair<uintptr_t, T> operator*() const {
std::pair<uintptr_t, upb_value> val = *iter_;
std::pair<uintptr_t, T> ret;
ret.first = val.first;
ret.second = GetUpbValue<T>(val.second);
return ret;
}
bool operator==(const iterator& other) const {
return iter_ == other.iter_;
}
bool operator!=(const iterator& other) const {
return iter_ != other.iter_;
}
private:
IntTable::iterator iter_;
};
iterator begin() { return iterator(this); }
iterator end() { return iterator::end(this); }
IntTable table_;
};
}
bool benchmark = false;
#define CPU_TIME_PER_TEST 0.5
using std::vector;
double get_usertime() {
struct rusage usage;
getrusage(RUSAGE_SELF, &usage);
return usage.ru_utime.tv_sec + (usage.ru_utime.tv_usec/1000000.0);
}
/* num_entries must be a power of 2. */
void test_strtable(const vector<std::string>& keys, uint32_t num_to_insert) {
/* Initialize structures. */
std::map<std::string, int32_t> m;
typedef upb::TypedStrTable<int32_t> Table;
Table table;
std::set<std::string> all;
for(size_t i = 0; i < num_to_insert; i++) {
const std::string& key = keys[i];
all.insert(key);
table.Insert(key, key[0]);
m[key] = key[0];
}
/* Test correctness. */
for(uint32_t i = 0; i < keys.size(); i++) {
const std::string& key = keys[i];
std::pair<bool, int32_t> found = table.Lookup(key);
if(m.find(key) != m.end()) { /* Assume map implementation is correct. */
ASSERT(found.first);
ASSERT(found.second == key[0]);
ASSERT(m[key] == key[0]);
} else {
ASSERT(!found.first);
}
}
for (Table::iterator it = table.begin(); it != table.end(); ++it) {
std::set<std::string>::iterator i = all.find((*it).first);
ASSERT(i != all.end());
all.erase(i);
}
ASSERT(all.empty());
// Test iteration with resizes.
for (int i = 0; i < 10; i++) {
for (Table::iterator it = table.begin(); it != table.end(); ++it) {
// Even if we invalidate the iterator it should only return real elements.
ASSERT((*it).second == m[(*it).first]);
// Force a resize even though the size isn't changing.
// Also forces the table size to grow so some new buckets end up empty.
int new_lg2 = table.table_.table_.t.size_lg2 + 1;
// Don't use more than 64k tables, to avoid exhausting memory.
new_lg2 = UPB_MIN(new_lg2, 16);
table.Resize(new_lg2);
}
}
}
/* num_entries must be a power of 2. */
void test_inttable(int32_t *keys, uint16_t num_entries, const char *desc) {
/* Initialize structures. */
typedef upb::TypedIntTable<uint32_t> Table;
Table table;
uint32_t largest_key = 0;
std::map<uint32_t, uint32_t> m;
std::unordered_map<uint32_t, uint32_t> hm;
for(size_t i = 0; i < num_entries; i++) {
int32_t key = keys[i];
largest_key = UPB_MAX((int32_t)largest_key, key);
table.Insert(key, key * 2);
m[key] = key*2;
hm[key] = key*2;
}
/* Test correctness. */
for(uint32_t i = 0; i <= largest_key; i++) {
std::pair<bool, uint32_t> found = table.Lookup(i);
if(m.find(i) != m.end()) { /* Assume map implementation is correct. */
ASSERT(found.first);
ASSERT(found.second == i*2);
ASSERT(m[i] == i*2);
ASSERT(hm[i] == i*2);
} else {
ASSERT(!found.first);
}
}
for(uint16_t i = 0; i < num_entries; i += 2) {
std::pair<bool, uint32_t> found = table.Remove(keys[i]);
ASSERT(found.first == (m.erase(keys[i]) == 1));
if (found.first) ASSERT(found.second == (uint32_t)keys[i] * 2);
hm.erase(keys[i]);
m.erase(keys[i]);
}
ASSERT(table.count() == hm.size());
/* Test correctness. */
for(uint32_t i = 0; i <= largest_key; i++) {
std::pair<bool, uint32_t> found = table.Lookup(i);
if(m.find(i) != m.end()) { /* Assume map implementation is correct. */
ASSERT(found.first);
ASSERT(found.second == i*2);
ASSERT(m[i] == i*2);
ASSERT(hm[i] == i*2);
} else {
ASSERT(!found.first);
}
}
// Test replace.
for(uint32_t i = 0; i <= largest_key; i++) {
bool replaced = table.Replace(i, i*3);
if(m.find(i) != m.end()) { /* Assume map implementation is correct. */
ASSERT(replaced);
m[i] = i * 3;
hm[i] = i * 3;
} else {
ASSERT(!replaced);
}
}
// Compact and test correctness again.
table.Compact();
for(uint32_t i = 0; i <= largest_key; i++) {
std::pair<bool, uint32_t> found = table.Lookup(i);
if(m.find(i) != m.end()) { /* Assume map implementation is correct. */
ASSERT(found.first);
ASSERT(found.second == i*3);
ASSERT(m[i] == i*3);
ASSERT(hm[i] == i*3);
} else {
ASSERT(!found.first);
}
}
if(!benchmark) {
return;
}
printf("%s\n", desc);
/* Test performance. We only test lookups for keys that are known to exist. */
uint16_t *rand_order = new uint16_t[num_entries];
for(uint16_t i = 0; i < num_entries; i++) {
rand_order[i] = i;
}
for(uint16_t i = num_entries - 1; i >= 1; i--) {
uint16_t rand_i = (random() / (double)RAND_MAX) * i;
ASSERT(rand_i <= i);
uint16_t tmp = rand_order[rand_i];
rand_order[rand_i] = rand_order[i];
rand_order[i] = tmp;
}
uintptr_t x = 0;
const int mask = num_entries - 1;
int time_mask = 0xffff;
printf("upb_inttable(seq): ");
fflush(stdout);
double before = get_usertime();
unsigned int i;
#define MAYBE_BREAK \
if ((i & time_mask) == 0 && (get_usertime() - before) > CPU_TIME_PER_TEST) \
break;
for(i = 0; true; i++) {
MAYBE_BREAK;
int32_t key = keys[i & mask];
upb_value v;
bool ok = upb_inttable_lookup32(&table.table_.table_, key, &v);
x += (uintptr_t)ok;
}
double total = get_usertime() - before;
printf("%ld/s\n", (long)(i/total));
double upb_seq_i = i / 100; // For later percentage calcuation.
printf("upb_inttable(rand): ");
fflush(stdout);
before = get_usertime();
for(i = 0; true; i++) {
MAYBE_BREAK;
int32_t key = keys[rand_order[i & mask]];
upb_value v;
bool ok = upb_inttable_lookup32(&table.table_.table_, key, &v);
x += (uintptr_t)ok;
}
total = get_usertime() - before;
printf("%ld/s\n", (long)(i/total));
double upb_rand_i = i / 100; // For later percentage calculation.
printf("std::map<int32_t, int32_t>(seq): ");
fflush(stdout);
before = get_usertime();
for(i = 0; true; i++) {
MAYBE_BREAK;
int32_t key = keys[i & mask];
x += m[key];
}
total = get_usertime() - before;
printf("%ld/s (%0.1f%% of upb)\n", (long)(i/total), i / upb_seq_i);
printf("std::map<int32_t, int32_t>(rand): ");
fflush(stdout);
before = get_usertime();
for(i = 0; true; i++) {
MAYBE_BREAK;
int32_t key = keys[rand_order[i & mask]];
x += m[key];
}
total = get_usertime() - before;
printf("%ld/s (%0.1f%% of upb)\n", (long)(i/total), i / upb_rand_i);
printf("std::unordered_map<uint32_t, uint32_t>(seq): ");
fflush(stdout);
before = get_usertime();
for(i = 0; true; i++) {
MAYBE_BREAK;
int32_t key = keys[rand_order[i & mask]];
x += hm[key];
}
total = get_usertime() - before;
printf("%ld/s (%0.1f%% of upb)\n", (long)(i/total), i / upb_seq_i);
printf("std::unordered_map<uint32_t, uint32_t>(rand): ");
fflush(stdout);
before = get_usertime();
for(i = 0; true; i++) {
MAYBE_BREAK;
int32_t key = keys[rand_order[i & mask]];
x += hm[key];
}
total = get_usertime() - before;
if (x == INT_MAX) abort();
printf("%ld/s (%0.1f%% of upb)\n\n", (long)(i/total), i / upb_rand_i);
delete[] rand_order;
}
/*
* This test can't pass right now because the table can't store a value of
* (uint64_t)-1.
*/
void test_int64_max_value() {
/*
typedef upb::TypedIntTable<uint64_t> Table;
Table table;
uintptr_t uint64_max = (uint64_t)-1;
table.Insert(1, uint64_max);
std::pair<bool, uint64_t> found = table.Lookup(1);
ASSERT(found.first);
ASSERT(found.second == uint64_max);
*/
}
int32_t *get_contiguous_keys(int32_t num) {
int32_t *buf = new int32_t[num];
for(int32_t i = 0; i < num; i++)
buf[i] = i;
return buf;
}
void test_delete() {
upb_inttable t;
upb_inttable_init(&t, UPB_CTYPE_BOOL);
upb_inttable_insert(&t, 0, upb_value_bool(true));
upb_inttable_insert(&t, 2, upb_value_bool(true));
upb_inttable_insert(&t, 4, upb_value_bool(true));
upb_inttable_compact(&t);
upb_inttable_remove(&t, 0, NULL);
upb_inttable_remove(&t, 2, NULL);
upb_inttable_remove(&t, 4, NULL);
upb_inttable_iter iter;
for (upb_inttable_begin(&iter, &t); !upb_inttable_done(&iter);
upb_inttable_next(&iter)) {
ASSERT(false);
}
upb_inttable_uninit(&t);
}
extern "C" {
int run_tests(int argc, char *argv[]) {
for (int i = 1; i < argc; i++) {
if (strcmp(argv[i], "benchmark") == 0) benchmark = true;
}
vector<std::string> keys;
keys.push_back("google.protobuf.FileDescriptorSet");
keys.push_back("google.protobuf.FileDescriptorProto");
keys.push_back("google.protobuf.DescriptorProto");
keys.push_back("google.protobuf.DescriptorProto.ExtensionRange");
keys.push_back("google.protobuf.FieldDescriptorProto");
keys.push_back("google.protobuf.EnumDescriptorProto");
keys.push_back("google.protobuf.EnumValueDescriptorProto");
keys.push_back("google.protobuf.ServiceDescriptorProto");
keys.push_back("google.protobuf.MethodDescriptorProto");
keys.push_back("google.protobuf.FileOptions");
keys.push_back("google.protobuf.MessageOptions");
keys.push_back("google.protobuf.FieldOptions");
keys.push_back("google.protobuf.EnumOptions");
keys.push_back("google.protobuf.EnumValueOptions");
keys.push_back("google.protobuf.ServiceOptions");
keys.push_back("google.protobuf.MethodOptions");
keys.push_back("google.protobuf.UninterpretedOption");
keys.push_back("google.protobuf.UninterpretedOption.NamePart");
for (int i = 0; i < 10; i++) {
test_strtable(keys, 18);
}
int32_t *keys1 = get_contiguous_keys(8);
test_inttable(keys1, 8, "Table size: 8, keys: 1-8 ====");
delete[] keys1;
int32_t *keys2 = get_contiguous_keys(64);
test_inttable(keys2, 64, "Table size: 64, keys: 1-64 ====\n");
delete[] keys2;
int32_t *keys3 = get_contiguous_keys(512);
test_inttable(keys3, 512, "Table size: 512, keys: 1-512 ====\n");
delete[] keys3;
int32_t *keys4 = new int32_t[64];
for(int32_t i = 0; i < 64; i++) {
if(i < 32)
keys4[i] = i+1;
else
keys4[i] = 10101+i;
}
test_inttable(keys4, 64, "Table size: 64, keys: 1-32 and 10133-10164 ====\n");
delete[] keys4;
test_delete();
test_int64_max_value();
return 0;
}
}