third_party/upb/tests/test_table.cc

   1 // Copyright (c) 2009-2021, Google LLC
   2 // All rights reserved.
   3 //
   4 // Redistribution and use in source and binary forms, with or without
   5 // modification, are permitted provided that the following conditions are met:
   6 //     * Redistributions of source code must retain the above copyright
   7 //       notice, this list of conditions and the following disclaimer.
   8 //     * Redistributions in binary form must reproduce the above copyright
   9 //       notice, this list of conditions and the following disclaimer in the
  10 //       documentation and/or other materials provided with the distribution.
  11 //     * Neither the name of Google LLC nor the
  12 //       names of its contributors may be used to endorse or promote products
  13 //       derived from this software without specific prior written permission.
  14 //
  15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
  16 // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  17 // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  18 // DISCLAIMED. IN NO EVENT SHALL Google LLC BE LIABLE FOR ANY
  19 // DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  20 // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  21 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  22 // ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  24 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25
  26 /*
  27  * Tests for upb_table.
  28  */
  29
  30 #include <limits.h>
  31 #include <string.h>
  32 #include <sys/resource.h>
  33 #include <iostream>
  34 #include <map>
  35 #include <set>
  36 #include <string>
  37 #include <unordered_map>
  38 #include <vector>
  39
  40 #include "tests/upb_test.h"
  41 #include "upb/upb.hpp"
  42 #include "upb/table_internal.h"
  43
  44 #include "upb/port_def.inc"
  45
  46 // Convenience interface for C++.  We don't put this in upb itself because
  47 // the table is not exposed to users.
  48
  49 namespace upb {
  50
  51 template <class T> upb_value MakeUpbValue(T val);
  52 template <class T> T GetUpbValue(upb_value val);
  53
  54 #define FUNCS(name, type_t, enumval) \
  55   template<> upb_value MakeUpbValue<type_t>(type_t val) { return upb_value_ ## name(val); } \
  56   template<> type_t GetUpbValue<type_t>(upb_value val) { return upb_value_get ## name(val); } \
  57
  58 FUNCS(int32,    int32_t,      UPB_CTYPE_INT32)
  59 FUNCS(int64,    int64_t,      UPB_CTYPE_INT64)
  60 FUNCS(uint32,   uint32_t,     UPB_CTYPE_UINT32)
  61 FUNCS(uint64,   uint64_t,     UPB_CTYPE_UINT64)
  62 FUNCS(bool,     bool,         UPB_CTYPE_BOOL)
  63 FUNCS(cstr,     char*,        UPB_CTYPE_CSTR)
  64 FUNCS(ptr,      void*,        UPB_CTYPE_PTR)
  65 FUNCS(constptr, const void*,  UPB_CTYPE_CONSTPTR)
  66 FUNCS(fptr,     upb_func*,    UPB_CTYPE_FPTR)
  67
  68 #undef FUNCS
  69
  70 class IntTable {
  71  public:
  72   IntTable() { upb_inttable_init(&table_, arena_.ptr()); }
  73
  74   size_t count() { return upb_inttable_count(&table_); }
  75
  76   bool Insert(uintptr_t key, upb_value val) {
  77     return upb_inttable_insert(&table_, key, val, arena_.ptr());
  78   }
  79
  80   bool Replace(uintptr_t key, upb_value val) {
  81     return upb_inttable_replace(&table_, key, val);
  82   }
  83
  84   std::pair<bool, upb_value> Remove(uintptr_t key) {
  85     std::pair<bool, upb_value> ret;
  86     ret.first = upb_inttable_remove(&table_, key, &ret.second);
  87     return ret;
  88   }
  89
  90   std::pair<bool, upb_value> Lookup(uintptr_t key) const {
  91     std::pair<bool, upb_value> ret;
  92     ret.first = upb_inttable_lookup(&table_, key, &ret.second);
  93     return ret;
  94   }
  95
  96   std::pair<bool, upb_value> Lookup32(uint32_t key) const {
  97     std::pair<bool, upb_value> ret;
  98     ret.first = upb_inttable_lookup(&table_, key, &ret.second);
  99     return ret;
 100   }
 101
 102   void Compact() { upb_inttable_compact(&table_, arena_.ptr()); }
 103
 104   class iterator : public std::iterator<std::forward_iterator_tag,
 105                                         std::pair<uintptr_t, upb_value> > {
 106    public:
 107     explicit iterator(IntTable* table) {
 108       upb_inttable_begin(&iter_, &table->table_);
 109     }
 110
 111     static iterator end(IntTable* table) {
 112       iterator iter(table);
 113       upb_inttable_iter_setdone(&iter.iter_);
 114       return iter;
 115     }
 116
 117     void operator++() {
 118       return upb_inttable_next(&iter_);
 119     }
 120
 121     std::pair<uintptr_t, upb_value> operator*() const {
 122       std::pair<uintptr_t, upb_value> ret;
 123       ret.first = upb_inttable_iter_key(&iter_);
 124       ret.second = upb_inttable_iter_value(&iter_);
 125       return ret;
 126     }
 127
 128     bool operator==(const iterator& other) const {
 129       return upb_inttable_iter_isequal(&iter_, &other.iter_);
 130     }
 131
 132     bool operator!=(const iterator& other) const {
 133       return !(*this == other);
 134     }
 135
 136    private:
 137     upb_inttable_iter iter_;
 138   };
 139
 140   upb::Arena arena_;
 141   upb_inttable table_;
 142 };
 143
 144 class StrTable {
 145  public:
 146   StrTable() { upb_strtable_init(&table_, 4, arena_.ptr()); }
 147
 148   size_t count() { return upb_strtable_count(&table_); }
 149
 150   bool Insert(const std::string& key, upb_value val) {
 151     return upb_strtable_insert(&table_, key.c_str(), key.size(), val,
 152                                arena_.ptr());
 153   }
 154
 155   std::pair<bool, upb_value> Remove(const std::string& key) {
 156     std::pair<bool, upb_value> ret;
 157     ret.first =
 158         upb_strtable_remove(&table_, key.c_str(), key.size(), &ret.second);
 159     return ret;
 160   }
 161
 162   std::pair<bool, upb_value> Lookup(const std::string& key) const {
 163     std::pair<bool, upb_value> ret;
 164     ret.first =
 165         upb_strtable_lookup2(&table_, key.c_str(), key.size(), &ret.second);
 166     return ret;
 167   }
 168
 169   void Resize(size_t size_lg2) {
 170     upb_strtable_resize(&table_, size_lg2, arena_.ptr());
 171   }
 172
 173   class iterator : public std::iterator<std::forward_iterator_tag,
 174                                         std::pair<std::string, upb_value> > {
 175    public:
 176     explicit iterator(StrTable* table) {
 177       upb_strtable_begin(&iter_, &table->table_);
 178     }
 179
 180     static iterator end(StrTable* table) {
 181       iterator iter(table);
 182       upb_strtable_iter_setdone(&iter.iter_);
 183       return iter;
 184     }
 185
 186     void operator++() {
 187       return upb_strtable_next(&iter_);
 188     }
 189
 190     std::pair<std::string, upb_value> operator*() const {
 191       std::pair<std::string, upb_value> ret;
 192       upb_strview view = upb_strtable_iter_key(&iter_);
 193       ret.first.assign(view.data, view.size);
 194       ret.second = upb_strtable_iter_value(&iter_);
 195       return ret;
 196     }
 197
 198     bool operator==(const iterator& other) const {
 199       return upb_strtable_iter_isequal(&iter_, &other.iter_);
 200     }
 201
 202     bool operator!=(const iterator& other) const {
 203       return !(*this == other);
 204     }
 205
 206    private:
 207     upb_strtable_iter iter_;
 208   };
 209
 210   upb::Arena arena_;
 211   upb_strtable table_;
 212 };
 213
 214 template <class T> class TypedStrTable {
 215  public:
 216   size_t count() { return table_.count(); }
 217
 218   bool Insert(const std::string &key, T val) {
 219     return table_.Insert(key, MakeUpbValue<T>(val));
 220   }
 221
 222   std::pair<bool, T> Remove(const std::string& key) {
 223     std::pair<bool, upb_value> found = table_.Remove(key);
 224     std::pair<bool, T> ret;
 225     ret.first = found.first;
 226     if (ret.first) {
 227       ret.second = GetUpbValue<T>(found.second);
 228     }
 229     return ret;
 230   }
 231
 232   std::pair<bool, T> Lookup(const std::string& key) const {
 233     std::pair<bool, upb_value> found = table_.Lookup(key);
 234     std::pair<bool, T> ret;
 235     ret.first = found.first;
 236     if (ret.first) {
 237       ret.second = GetUpbValue<T>(found.second);
 238     }
 239     return ret;
 240   }
 241
 242   void Resize(size_t size_lg2) {
 243     table_.Resize(size_lg2);
 244   }
 245
 246   class iterator : public std::iterator<std::forward_iterator_tag, std::pair<std::string, T> > {
 247    public:
 248     explicit iterator(TypedStrTable* table) : iter_(&table->table_) {}
 249     static iterator end(TypedStrTable* table) {
 250       iterator iter(table);
 251       iter.iter_ = StrTable::iterator::end(&table->table_);
 252       return iter;
 253     }
 254
 255     void operator++() { ++iter_; }
 256
 257     std::pair<std::string, T> operator*() const {
 258       std::pair<std::string, upb_value> val = *iter_;
 259       std::pair<std::string, T> ret;
 260       ret.first = val.first;
 261       ret.second = GetUpbValue<T>(val.second);
 262       return ret;
 263     }
 264
 265     bool operator==(const iterator& other) const {
 266       return iter_ == other.iter_;
 267     }
 268
 269     bool operator!=(const iterator& other) const {
 270       return iter_ != other.iter_;
 271     }
 272
 273    private:
 274     StrTable::iterator iter_;
 275   };
 276
 277   iterator begin() { return iterator(this); }
 278   iterator end() { return iterator::end(this); }
 279
 280   StrTable table_;
 281 };
 282
 283 template <class T> class TypedIntTable {
 284  public:
 285   size_t count() { return table_.count(); }
 286
 287   bool Insert(uintptr_t key, T val) {
 288     return table_.Insert(key, MakeUpbValue<T>(val));
 289   }
 290
 291   bool Replace(uintptr_t key, T val) {
 292     return table_.Replace(key, MakeUpbValue<T>(val));
 293   }
 294
 295   std::pair<bool, T> Remove(uintptr_t key) {
 296     std::pair<bool, upb_value> found = table_.Remove(key);
 297     std::pair<bool, T> ret;
 298     ret.first = found.first;
 299     if (ret.first) {
 300       ret.second = GetUpbValue<T>(found.second);
 301     }
 302     return ret;
 303   }
 304
 305   std::pair<bool, T> Lookup(uintptr_t key) const {
 306     std::pair<bool, upb_value> found = table_.Lookup(key);
 307     std::pair<bool, T> ret;
 308     ret.first = found.first;
 309     if (ret.first) {
 310       ret.second = GetUpbValue<T>(found.second);
 311     }
 312     return ret;
 313   }
 314
 315   void Compact() { table_.Compact(); }
 316
 317   class iterator : public std::iterator<std::forward_iterator_tag, std::pair<uintptr_t, T> > {
 318    public:
 319     explicit iterator(TypedIntTable* table) : iter_(&table->table_) {}
 320     static iterator end(TypedIntTable* table) {
 321       return IntTable::iterator::end(&table->table_);
 322     }
 323
 324     void operator++() { ++iter_; }
 325
 326     std::pair<uintptr_t, T> operator*() const {
 327       std::pair<uintptr_t, upb_value> val = *iter_;
 328       std::pair<uintptr_t, T> ret;
 329       ret.first = val.first;
 330       ret.second = GetUpbValue<T>(val.second);
 331       return ret;
 332     }
 333
 334     bool operator==(const iterator& other) const {
 335       return iter_ == other.iter_;
 336     }
 337
 338     bool operator!=(const iterator& other) const {
 339       return iter_ != other.iter_;
 340     }
 341
 342    private:
 343     IntTable::iterator iter_;
 344   };
 345
 346   iterator begin() { return iterator(this); }
 347   iterator end() { return iterator::end(this); }
 348
 349   IntTable table_;
 350 };
 351
 352 }
 353
 354 bool benchmark = false;
 355 #define CPU_TIME_PER_TEST 0.5
 356
 357 using std::vector;
 358
 359 double get_usertime() {
 360   struct rusage usage;
 361   getrusage(RUSAGE_SELF, &usage);
 362   return usage.ru_utime.tv_sec + (usage.ru_utime.tv_usec/1000000.0);
 363 }
 364
 365 /* num_entries must be a power of 2. */
 366 void test_strtable(const vector<std::string>& keys, uint32_t num_to_insert) {
 367   /* Initialize structures. */
 368   std::map<std::string, int32_t> m;
 369   typedef upb::TypedStrTable<int32_t> Table;
 370   Table table;
 371   std::set<std::string> all;
 372   for(size_t i = 0; i < num_to_insert; i++) {
 373     const std::string& key = keys[i];
 374     all.insert(key);
 375     table.Insert(key, key[0]);
 376     m[key] = key[0];
 377   }
 378
 379   /* Test correctness. */
 380   for(uint32_t i = 0; i < keys.size(); i++) {
 381     const std::string& key = keys[i];
 382     std::pair<bool, int32_t> found = table.Lookup(key);
 383     if(m.find(key) != m.end()) { /* Assume map implementation is correct. */
 384       ASSERT(found.first);
 385       ASSERT(found.second == key[0]);
 386       ASSERT(m[key] == key[0]);
 387     } else {
 388       ASSERT(!found.first);
 389     }
 390   }
 391
 392   for (Table::iterator it = table.begin(); it != table.end(); ++it) {
 393     std::set<std::string>::iterator i = all.find((*it).first);
 394     ASSERT(i != all.end());
 395     all.erase(i);
 396   }
 397   ASSERT(all.empty());
 398
 399   // Test iteration with resizes.
 400
 401   for (int i = 0; i < 10; i++) {
 402     for (Table::iterator it = table.begin(); it != table.end(); ++it) {
 403       // Even if we invalidate the iterator it should only return real elements.
 404       ASSERT((*it).second == m[(*it).first]);
 405
 406       // Force a resize even though the size isn't changing.
 407       // Also forces the table size to grow so some new buckets end up empty.
 408       int new_lg2 = table.table_.table_.t.size_lg2 + 1;
 409       // Don't use more than 64k tables, to avoid exhausting memory.
 410       new_lg2 = UPB_MIN(new_lg2, 16);
 411       table.Resize(new_lg2);
 412     }
 413   }
 414
 415 }
 416
 417 /* num_entries must be a power of 2. */
 418 void test_inttable(int32_t *keys, uint16_t num_entries, const char *desc) {
 419   /* Initialize structures. */
 420   typedef upb::TypedIntTable<uint32_t> Table;
 421   Table table;
 422   uint32_t largest_key = 0;
 423   std::map<uint32_t, uint32_t> m;
 424   std::unordered_map<uint32_t, uint32_t> hm;
 425   for(size_t i = 0; i < num_entries; i++) {
 426     int32_t key = keys[i];
 427     largest_key = UPB_MAX((int32_t)largest_key, key);
 428     table.Insert(key, key * 2);
 429     m[key] = key*2;
 430     hm[key] = key*2;
 431   }
 432
 433   /* Test correctness. */
 434   for(uint32_t i = 0; i <= largest_key; i++) {
 435     std::pair<bool, uint32_t> found = table.Lookup(i);
 436     if(m.find(i) != m.end()) { /* Assume map implementation is correct. */
 437       ASSERT(found.first);
 438       ASSERT(found.second == i*2);
 439       ASSERT(m[i] == i*2);
 440       ASSERT(hm[i] == i*2);
 441     } else {
 442       ASSERT(!found.first);
 443     }
 444   }
 445
 446   for(uint16_t i = 0; i < num_entries; i += 2) {
 447     std::pair<bool, uint32_t> found = table.Remove(keys[i]);
 448     ASSERT(found.first == (m.erase(keys[i]) == 1));
 449     if (found.first) ASSERT(found.second == (uint32_t)keys[i] * 2);
 450     hm.erase(keys[i]);
 451     m.erase(keys[i]);
 452   }
 453
 454   ASSERT(table.count() == hm.size());
 455
 456   /* Test correctness. */
 457   for(uint32_t i = 0; i <= largest_key; i++) {
 458     std::pair<bool, uint32_t> found = table.Lookup(i);
 459     if(m.find(i) != m.end()) { /* Assume map implementation is correct. */
 460       ASSERT(found.first);
 461       ASSERT(found.second == i*2);
 462       ASSERT(m[i] == i*2);
 463       ASSERT(hm[i] == i*2);
 464     } else {
 465       ASSERT(!found.first);
 466     }
 467   }
 468
 469   // Test replace.
 470   for(uint32_t i = 0; i <= largest_key; i++) {
 471     bool replaced = table.Replace(i, i*3);
 472     if(m.find(i) != m.end()) { /* Assume map implementation is correct. */
 473       ASSERT(replaced);
 474       m[i] = i * 3;
 475       hm[i] = i * 3;
 476     } else {
 477       ASSERT(!replaced);
 478     }
 479   }
 480
 481   // Compact and test correctness again.
 482   table.Compact();
 483   for(uint32_t i = 0; i <= largest_key; i++) {
 484     std::pair<bool, uint32_t> found = table.Lookup(i);
 485     if(m.find(i) != m.end()) { /* Assume map implementation is correct. */
 486       ASSERT(found.first);
 487       ASSERT(found.second == i*3);
 488       ASSERT(m[i] == i*3);
 489       ASSERT(hm[i] == i*3);
 490     } else {
 491       ASSERT(!found.first);
 492     }
 493   }
 494
 495   if(!benchmark) {
 496     return;
 497   }
 498
 499   printf("%s\n", desc);
 500
 501   /* Test performance. We only test lookups for keys that are known to exist. */
 502   uint16_t *rand_order = new uint16_t[num_entries];
 503   for(uint16_t i = 0; i < num_entries; i++) {
 504     rand_order[i] = i;
 505   }
 506   for(uint16_t i = num_entries - 1; i >= 1; i--) {
 507     uint16_t rand_i = (random() / (double)RAND_MAX) * i;
 508     ASSERT(rand_i <= i);
 509     uint16_t tmp = rand_order[rand_i];
 510     rand_order[rand_i] = rand_order[i];
 511     rand_order[i] = tmp;
 512   }
 513
 514   uintptr_t x = 0;
 515   const int mask = num_entries - 1;
 516   int time_mask = 0xffff;
 517
 518   printf("upb_inttable(seq): ");
 519   fflush(stdout);
 520   double before = get_usertime();
 521   unsigned int i;
 522
 523 #define MAYBE_BREAK \
 524     if ((i & time_mask) == 0 && (get_usertime() - before) > CPU_TIME_PER_TEST) \
 525       break;
 526   for(i = 0; true; i++) {
 527     MAYBE_BREAK;
 528     int32_t key = keys[i & mask];
 529     upb_value v;
 530     bool ok = upb_inttable_lookup(&table.table_.table_, key, &v);
 531     x += (uintptr_t)ok;
 532   }
 533   double total = get_usertime() - before;
 534   printf("%ld/s\n", (long)(i/total));
 535   double upb_seq_i = i / 100;  // For later percentage calcuation.
 536
 537   printf("upb_inttable(rand): ");
 538   fflush(stdout);
 539   before = get_usertime();
 540   for(i = 0; true; i++) {
 541     MAYBE_BREAK;
 542     int32_t key = keys[rand_order[i & mask]];
 543     upb_value v;
 544     bool ok = upb_inttable_lookup(&table.table_.table_, key, &v);
 545     x += (uintptr_t)ok;
 546   }
 547   total = get_usertime() - before;
 548   printf("%ld/s\n", (long)(i/total));
 549   double upb_rand_i = i / 100;  // For later percentage calculation.
 550
 551   printf("std::map<int32_t, int32_t>(seq): ");
 552   fflush(stdout);
 553   before = get_usertime();
 554   for(i = 0; true; i++) {
 555     MAYBE_BREAK;
 556     int32_t key = keys[i & mask];
 557     x += m[key];
 558   }
 559   total = get_usertime() - before;
 560   printf("%ld/s (%0.1f%% of upb)\n", (long)(i/total), i / upb_seq_i);
 561
 562   printf("std::map<int32_t, int32_t>(rand): ");
 563   fflush(stdout);
 564   before = get_usertime();
 565   for(i = 0; true; i++) {
 566     MAYBE_BREAK;
 567     int32_t key = keys[rand_order[i & mask]];
 568     x += m[key];
 569   }
 570   total = get_usertime() - before;
 571   printf("%ld/s (%0.1f%% of upb)\n", (long)(i/total), i / upb_rand_i);
 572
 573   printf("std::unordered_map<uint32_t, uint32_t>(seq): ");
 574   fflush(stdout);
 575   before = get_usertime();
 576   for(i = 0; true; i++) {
 577     MAYBE_BREAK;
 578     int32_t key = keys[rand_order[i & mask]];
 579     x += hm[key];
 580   }
 581   total = get_usertime() - before;
 582   printf("%ld/s (%0.1f%% of upb)\n", (long)(i/total), i / upb_seq_i);
 583
 584   printf("std::unordered_map<uint32_t, uint32_t>(rand): ");
 585   fflush(stdout);
 586   before = get_usertime();
 587   for(i = 0; true; i++) {
 588     MAYBE_BREAK;
 589     int32_t key = keys[rand_order[i & mask]];
 590     x += hm[key];
 591   }
 592   total = get_usertime() - before;
 593   if (x == INT_MAX) abort();
 594   printf("%ld/s (%0.1f%% of upb)\n\n", (long)(i/total), i / upb_rand_i);
 595   delete[] rand_order;
 596 }
 597
 598 /*
 599  * This test can't pass right now because the table can't store a value of
 600  * (uint64_t)-1.
 601  */
 602 void test_int64_max_value() {
 603 /*
 604   typedef upb::TypedIntTable<uint64_t> Table;
 605   Table table;
 606   uintptr_t uint64_max = (uint64_t)-1;
 607   table.Insert(1, uint64_max);
 608   std::pair<bool, uint64_t> found = table.Lookup(1);
 609   ASSERT(found.first);
 610   ASSERT(found.second == uint64_max);
 611 */
 612 }
 613
 614 int32_t *get_contiguous_keys(int32_t num) {
 615   int32_t *buf = new int32_t[num];
 616   for(int32_t i = 0; i < num; i++)
 617     buf[i] = i;
 618   return buf;
 619 }
 620
 621 void test_delete() {
 622   upb::Arena arena;
 623   upb_inttable t;
 624   upb_inttable_init(&t, arena.ptr());
 625   upb_inttable_insert(&t, 0, upb_value_bool(true), arena.ptr());
 626   upb_inttable_insert(&t, 2, upb_value_bool(true), arena.ptr());
 627   upb_inttable_insert(&t, 4, upb_value_bool(true), arena.ptr());
 628   upb_inttable_compact(&t, arena.ptr());
 629   upb_inttable_remove(&t, 0, NULL);
 630   upb_inttable_remove(&t, 2, NULL);
 631   upb_inttable_remove(&t, 4, NULL);
 632
 633   upb_inttable_iter iter;
 634   for (upb_inttable_begin(&iter, &t); !upb_inttable_done(&iter);
 635        upb_inttable_next(&iter)) {
 636     ASSERT(false);
 637   }
 638 }
 639
 640 void test_init() {
 641   for (int i = 0; i < 2048; i++) {
 642     /* Tests that the size calculations in init() (lg2 size for target load)
 643      * work for all expected sizes. */
 644     upb::Arena arena;
 645     upb_strtable t;
 646     upb_strtable_init(&t, i, arena.ptr());
 647   }
 648 }
 649
 650 extern "C" {
 651
 652 int run_tests(int argc, char *argv[]) {
 653   for (int i = 1; i < argc; i++) {
 654     if (strcmp(argv[i], "benchmark") == 0) benchmark = true;
 655   }
 656
 657   vector<std::string> keys;
 658   keys.push_back("google.protobuf.FileDescriptorSet");
 659   keys.push_back("google.protobuf.FileDescriptorProto");
 660   keys.push_back("google.protobuf.DescriptorProto");
 661   keys.push_back("google.protobuf.DescriptorProto.ExtensionRange");
 662   keys.push_back("google.protobuf.FieldDescriptorProto");
 663   keys.push_back("google.protobuf.EnumDescriptorProto");
 664   keys.push_back("google.protobuf.EnumValueDescriptorProto");
 665   keys.push_back("google.protobuf.ServiceDescriptorProto");
 666   keys.push_back("google.protobuf.MethodDescriptorProto");
 667   keys.push_back("google.protobuf.FileOptions");
 668   keys.push_back("google.protobuf.MessageOptions");
 669   keys.push_back("google.protobuf.FieldOptions");
 670   keys.push_back("google.protobuf.EnumOptions");
 671   keys.push_back("google.protobuf.EnumValueOptions");
 672   keys.push_back("google.protobuf.ServiceOptions");
 673   keys.push_back("google.protobuf.MethodOptions");
 674   keys.push_back("google.protobuf.UninterpretedOption");
 675   keys.push_back("google.protobuf.UninterpretedOption.NamePart");
 676
 677   for (int i = 0; i < 10; i++) {
 678     test_strtable(keys, 18);
 679   }
 680
 681   int32_t *keys1 = get_contiguous_keys(8);
 682   test_inttable(keys1, 8, "Table size: 8, keys: 1-8 ====");
 683   delete[] keys1;
 684
 685   int32_t *keys2 = get_contiguous_keys(64);
 686   test_inttable(keys2, 64, "Table size: 64, keys: 1-64 ====\n");
 687   delete[] keys2;
 688
 689   int32_t *keys3 = get_contiguous_keys(512);
 690   test_inttable(keys3, 512, "Table size: 512, keys: 1-512 ====\n");
 691   delete[] keys3;
 692
 693   int32_t *keys4 = new int32_t[64];
 694   for(int32_t i = 0; i < 64; i++) {
 695     if(i < 32)
 696       keys4[i] = i+1;
 697     else
 698       keys4[i] = 10101+i;
 699   }
 700   test_inttable(keys4, 64, "Table size: 64, keys: 1-32 and 10133-10164 ====\n");
 701   delete[] keys4;
 702
 703   test_delete();
 704   test_int64_max_value();
 705
 706   return 0;
 707 }
 708
 709 }