Directory restructuring.

3 files changed, 401 insertions, 0 deletions

diff --git a/tests/test_table.cc b/tests/test_table.cc
new file mode 100644
index 0000000..0337eaa
--- /dev/null
+++ b/tests/test_table.cc
@@ -0,0 +1,276 @@
+
+#include "upb_table.h"
+#include "test_util.h"
+#include <assert.h>
+#include <map>
+#include <string>
+#include <vector>
+#include <set>
+#include <ext/hash_map>
+#include <sys/resource.h>
+#include <iostream>
+
+using std::string;
+using std::vector;
+
+struct inttable_entry {
+  struct upb_inttable_entry e;
+  uint32_t value;  /* key*2 */
+};
+
+struct strtable_entry {
+  struct upb_strtable_entry e;
+  int32_t value;  /* ASCII Value of first letter */
+};
+
+double get_usertime()
+{
+  struct rusage usage;
+  getrusage(RUSAGE_SELF, &usage);
+  return usage.ru_utime.tv_sec + (usage.ru_utime.tv_usec/1000000.0);
+}
+
+struct upb_string *get_upbstring(const string& key) {
+  static struct upb_string str;
+  str.ptr = (char*)key.c_str();
+  str.byte_len = key.size();
+  return &str;
+}
+
+/* num_entries must be a power of 2. */
+void test_strtable(const vector<string>& keys, uint32_t num_to_insert)
+{
+  /* Initialize structures. */
+  struct upb_strtable table;
+  std::map<string, int32_t> m;
+  upb_strtable_init(&table, 0, sizeof(struct strtable_entry));
+  std::set<string> all;
+  for(size_t i = 0; i < num_to_insert; i++) {
+    const string& key = keys[i];
+    all.insert(key);
+    struct strtable_entry e;
+    e.value = key[0];
+    e.e.key = *get_upbstring(key);
+    upb_strtable_insert(&table, &e.e);
+    m[key] = key[0];
+  }
+
+  /* Test correctness. */
+  for(uint32_t i = 0; i < keys.size(); i++) {
+    const string& key = keys[i];
+    struct upb_string *str = get_upbstring(key);
+    struct strtable_entry *e =
+        (struct strtable_entry*)upb_strtable_lookup( &table, str);
+    if(m.find(key) != m.end()) { /* Assume map implementation is correct. */
+      assert(e);
+      assert(upb_streql(&e->e.key, get_upbstring(key)));
+      assert(e->value == key[0]);
+      assert(m[key] == key[0]);
+    } else {
+      assert(e == NULL);
+    }
+  }
+
+  struct strtable_entry *e;
+  for(e = (struct strtable_entry*)upb_strtable_begin(&table); e;
+      e = (struct strtable_entry*)upb_strtable_next(&table, &e->e)) {
+    string tmp(e->e.key.ptr, e->e.key.byte_len);
+    std::set<string>::iterator i = all.find(tmp);
+    assert(i != all.end());
+    all.erase(i);
+  }
+  assert(all.empty());
+
+  upb_strtable_free(&table);
+}
+
+/* num_entries must be a power of 2. */
+void test_inttable(int32_t *keys, size_t num_entries)
+{
+  /* Initialize structures. */
+  struct upb_inttable table;
+  uint32_t largest_key = 0;
+  std::map<uint32_t, uint32_t> m;
+  __gnu_cxx::hash_map<uint32_t, uint32_t> hm;
+  upb_inttable_init(&table, num_entries, sizeof(struct inttable_entry));
+  for(size_t i = 0; i < num_entries; i++) {
+    int32_t key = keys[i];
+    largest_key = max(largest_key, key);
+    struct inttable_entry e;
+    e.e.key = key;
+    e.value = key*2;
+    upb_inttable_insert(&table, &e.e);
+    m[key] = key*2;
+    hm[key] = key*2;
+  }
+
+  /* Test correctness. */
+  for(uint32_t i = 1; i <= largest_key; i++) {
+    struct inttable_entry *e = (struct inttable_entry*)upb_inttable_lookup(
+        &table, i, sizeof(struct inttable_entry));
+    if(m.find(i) != m.end()) { /* Assume map implementation is correct. */
+      assert(e);
+      assert(e->e.key == i);
+      assert(e->value == i*2);
+      assert(m[i] == i*2);
+      assert(hm[i] == i*2);
+    } else {
+      assert(e == NULL);
+    }
+  }
+
+  /* Test performance. We only test lookups for keys that are known to exist. */
+  uintptr_t x = 0;
+  const unsigned int iterations = 0xFFFFFF;
+  const int32_t mask = num_entries - 1;
+  printf("Measuring sequential loop overhead...");
+  fflush(stdout);
+  double before = get_usertime();
+  for(unsigned int i = 0; i < iterations; i++) {
+    int32_t key = keys[i & mask];
+    x += key;
+  }
+  double seq_overhead = get_usertime() - before;
+  printf("%0.3f seconds for %d iterations\n", seq_overhead, iterations);
+
+  printf("Measuring random loop overhead...");
+  rand();
+  fflush(stdout);
+  before = get_usertime();
+  for(unsigned int i = 0; i < iterations; i++) {
+    int32_t key = keys[rand() & mask];
+    x += key;
+  }
+  double rand_overhead = get_usertime() - before;
+  printf("%0.3f seconds for %d iterations\n", rand_overhead, iterations);
+
+  printf("upb_table(seq): ");
+  fflush(stdout);
+  before = get_usertime();
+  for(unsigned int i = 0; i < iterations; i++) {
+    int32_t key = keys[i & mask];
+    struct inttable_entry *e = (struct inttable_entry*)upb_inttable_lookup(
+        &table, key, sizeof(struct inttable_entry));
+    x += (uintptr_t)e;
+  }
+  double total = get_usertime() - before;
+  double without_overhead = total - seq_overhead;
+  printf("%0.3f seconds (%0.3f - %0.3f overhead) for %d iterations.  %s/s\n", without_overhead, total, seq_overhead, iterations, eng(iterations/without_overhead, 3, false));
+
+  printf("upb_table(rand): ");
+  fflush(stdout);
+  before = get_usertime();
+  for(unsigned int i = 0; i < iterations; i++) {
+    int32_t key = keys[rand() & mask];
+    struct inttable_entry *e = (struct inttable_entry*)upb_inttable_lookup(
+        &table, key, sizeof(struct inttable_entry));
+    x += (uintptr_t)e;
+  }
+  total = get_usertime() - before;
+  without_overhead = total - rand_overhead;
+  printf("%0.3f seconds (%0.3f - %0.3f overhead) for %d iterations.  %s/s\n", without_overhead, total, rand_overhead, iterations, eng(iterations/without_overhead, 3, false));
+
+  printf("map(seq): ");
+  fflush(stdout);
+  before = get_usertime();
+  for(unsigned int i = 0; i < iterations; i++) {
+    int32_t key = keys[i & mask];
+    x += m[key];
+  }
+  total = get_usertime() - before;
+  without_overhead = total - seq_overhead;
+  printf("%0.3f seconds (%0.3f - %0.3f overhead) for %d iterations.  %s/s\n", without_overhead, total, seq_overhead, iterations, eng(iterations/without_overhead, 3, false));
+
+  printf("map(rand): ");
+  fflush(stdout);
+  before = get_usertime();
+  for(unsigned int i = 0; i < iterations; i++) {
+    int32_t key = keys[rand() & mask];
+    x += m[key];
+  }
+  total = get_usertime() - before;
+  without_overhead = total - rand_overhead;
+  printf("%0.3f seconds (%0.3f - %0.3f overhead) for %d iterations.  %s/s\n", without_overhead, total, rand_overhead, iterations, eng(iterations/without_overhead, 3, false));
+
+  printf("hash_map(seq): ");
+  fflush(stdout);
+  before = get_usertime();
+  for(unsigned int i = 0; i < iterations; i++) {
+    int32_t key = keys[i & mask];
+    x += hm[key];
+  }
+  total = get_usertime() - before;
+  without_overhead = total - seq_overhead;
+  printf("%0.3f seconds (%0.3f - %0.3f overhead) for %d iterations.  %s/s\n", without_overhead, total, seq_overhead, iterations, eng(iterations/without_overhead, 3, false));
+
+  printf("hash_map(rand): ");
+  fflush(stdout);
+  before = get_usertime();
+  for(unsigned int i = 0; i < iterations; i++) {
+    int32_t key = keys[rand() & mask];
+    x += hm[key];
+  }
+  total = get_usertime() - before;
+  without_overhead = total - rand_overhead;
+  printf("%0.3f seconds (%0.3f - %0.3f overhead) for %d iterations.  %s/s\n\n", without_overhead, total, rand_overhead, iterations, eng(iterations/without_overhead, 3, false));
+  upb_inttable_free(&table);
+}
+
+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+1;
+  return buf;
+}
+
+int main()
+{
+  vector<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");
+
+  test_strtable(keys, 18);
+
+  int32_t *keys1 = get_contiguous_keys(8);
+  printf("Contiguous 1-8 ====\n");
+  test_inttable(keys1, 8);
+  delete[] keys1;
+
+  int32_t *keys2 = get_contiguous_keys(64);
+  printf("Contiguous 1-64 ====\n");
+  test_inttable(keys2, 64);
+  delete[] keys2;
+
+  int32_t *keys3 = get_contiguous_keys(512);
+  printf("Contiguous 1-512 ====\n");
+  test_inttable(keys3, 512);
+  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;
+  }
+  printf("1-32 and 10133-10164 ====\n");
+  test_inttable(keys4, 64);
+  delete[] keys4;
+}
diff --git a/tests/test_util.h b/tests/test_util.h
new file mode 100644
index 0000000..a998a19
--- /dev/null
+++ b/tests/test_util.h
@@ -0,0 +1,53 @@
+/* Function for printing numbers using si prefixes (k, M, G, etc.).
+ * From http://www.cs.tut.fi/~jkorpela/c/eng.html */
+
+#define PREFIX_START (-24)
+/* Smallest power of then for which there is a prefix defined.
+   If the set of prefixes will be extended, change this constant
+   and update the table "prefix". */
+
+#include <stdio.h>
+#include <math.h>
+
+static char *eng(double value, int digits, int numeric)
+{
+  static const char *prefix[] = {
+  "y", "z", "a", "f", "p", "n", "u", "m", "",
+  "k", "M", "G", "T", "P", "E", "Z", "Y"
+  };
+#define PREFIX_END (PREFIX_START+\
+(int)((sizeof(prefix)/sizeof(char *)-1)*3))
+
+      int expof10;
+      static char result[100];
+      char *res = result;
+
+      if (value < 0.)
+        {
+            *res++ = '-';
+            value = -value;
+        }
+
+      expof10 = (int) log10(value);
+      if(expof10 > 0)
+        expof10 = (expof10/3)*3;
+      else
+        expof10 = (-expof10+3)/3*(-3); 
+
+      value *= pow(10,-expof10);
+
+      if (value >= 1000.)
+         { value /= 1000.0; expof10 += 3; }
+      else if(value >= 100.0)
+         digits -= 2;
+      else if(value >= 10.0)
+         digits -= 1;
+
+      if(numeric || (expof10 < PREFIX_START) ||    
+                    (expof10 > PREFIX_END))
+        sprintf(res, "%.*fe%d", digits-1, value, expof10); 
+      else
+        sprintf(res, "%.*f %s", digits-1, value, 
+          prefix[(expof10-PREFIX_START)/3]);
+      return result;
+}
diff --git a/tests/tests.c b/tests/tests.c
new file mode 100644
index 0000000..7bc5dde
--- /dev/null
+++ b/tests/tests.c
@@ -0,0 +1,72 @@
+
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include "descriptor.c"
+#include "upb_enum.c"
+#include "upb_parse.c"
+#include "upb_context.c"
+#include "upb_msg.c"
+#include "upb_table.c"
+
+void test_get_v_uint64_t()
+{
+  upb_status_t status;
+
+  uint8_t zero[] = {0x00};
+  void *zero_buf = zero;
+  uint64_t zero_val = 0;
+  status = get_v_uint64_t(&zero_buf, zero + sizeof(zero), &zero_val);
+  assert(status == UPB_STATUS_OK);
+  assert(zero_val == 0);
+  assert(zero_buf == zero + sizeof(zero));
+
+  uint8_t one[] = {0x01};
+  void *one_buf = one;
+  uint64_t one_val = 0;
+  status = get_v_uint64_t(&one_buf, one + sizeof(one), &one_val);
+  assert(status == UPB_STATUS_OK);
+  assert(one_val == 1);
+  assert(one_buf == one + sizeof(one));
+
+  uint8_t twobyte[] = {0xAC, 0x02};
+  void *twobyte_buf = twobyte;
+  uint64_t twobyte_val = 0;
+  status = get_v_uint64_t(&twobyte_buf, twobyte + sizeof(twobyte), &twobyte_val);
+  assert(status == UPB_STATUS_OK);
+  assert(twobyte_val == 300);
+  assert(twobyte_buf == twobyte + sizeof(twobyte));
+
+  uint8_t tenbyte[] = {0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x7F};
+  void *tenbyte_buf = tenbyte;
+  uint64_t tenbyte_val = 0;
+  status = get_v_uint64_t(&tenbyte_buf, tenbyte + sizeof(tenbyte), &tenbyte_val);
+  assert(status == UPB_STATUS_OK);
+  assert(tenbyte_val == 0x89101c305080c101);
+  assert(tenbyte_buf == tenbyte + sizeof(tenbyte));
+
+  uint8_t elevenbyte[] = {0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x01};
+  void *elevenbyte_buf = elevenbyte;
+  uint64_t elevenbyte_val = 0;
+  status = get_v_uint64_t(&elevenbyte_buf, elevenbyte + sizeof(elevenbyte), &elevenbyte_val);
+  assert(status == UPB_ERROR_UNTERMINATED_VARINT);
+  status = get_v_uint64_t(&elevenbyte_buf, elevenbyte + sizeof(elevenbyte)-1, &elevenbyte_val);
+  /* Byte 10 is 0x80, so we know it's unterminated. */
+  assert(status == UPB_ERROR_UNTERMINATED_VARINT);
+  status = get_v_uint64_t(&elevenbyte_buf, elevenbyte + sizeof(elevenbyte)-2, &elevenbyte_val);
+  assert(status == UPB_STATUS_NEED_MORE_DATA);
+}
+
+void test_upb_context() {
+  struct upb_context c;
+  assert(upb_context_init(&c));
+  upb_context_free(&c);
+}
+
+int main()
+{
+  test_get_v_uint64_t();
+  test_upb_context();
+  printf("All tests passed.\n");
+  return 0;
+}