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