diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | test_table.cc | 29 | ||||
| -rw-r--r-- | upb_table.c | 13 | ||||
| -rw-r--r-- | upb_table.h | 5 |
4 files changed, 26 insertions, 23 deletions
@@ -3,7 +3,7 @@ CC=gcc CXX=g++ CFLAGS=-std=c99 -CPPFLAGS=-O3 -Wall -Wextra -pedantic -g -DNDEBUG -DUPB_UNALIGNED_READS_OK -fomit-frame-pointer +CPPFLAGS=-O3 -Wall -Wextra -pedantic -g -DUPB_UNALIGNED_READS_OK -fomit-frame-pointer OBJ=upb_parse.o upb_table.o upb_msg.o upb_context.o descriptor.o all: $(OBJ) test_table tests clean: diff --git a/test_table.cc b/test_table.cc index 67e0314..0e5657c 100644 --- a/test_table.cc +++ b/test_table.cc @@ -8,7 +8,7 @@ struct table_entry { struct upb_inttable_entry e; - int32_t value; /* key+2 */ + uint32_t value; /* key*2 */ }; double get_usertime() @@ -24,25 +24,24 @@ static uint32_t max(uint32_t a, uint32_t b) { return a > b ? a : b; } void test(int32_t *keys, size_t num_entries) { /* Initialize structures. */ - struct table_entry *entries = new table_entry[num_entries]; struct upb_inttable table; - int32_t largest_key = 0; - std::map<int32_t, int32_t> m; - __gnu_cxx::hash_map<int32_t, int32_t> hm; + 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 table_entry)); for(size_t i = 0; i < num_entries; i++) { int32_t key = keys[i]; largest_key = max(largest_key, key); - entries[i].e.key = key; - entries[i].value = key*2; + struct table_entry e; + e.e.key = key; + e.value = key*2; + upb_inttable_insert(&table, &e.e); m[key] = key*2; hm[key] = key*2; } - upb_inttable_init(&table, entries, num_entries, sizeof(struct table_entry)); - printf("size: %lu\n", sizeof(struct table_entry)); - delete[] entries; /* Test correctness. */ - for(int32_t i = 0; i < largest_key; i++) { + for(uint32_t i = 1; i <= largest_key; i++) { struct table_entry *e = (struct table_entry*)upb_inttable_lookup( &table, i, sizeof(struct table_entry)); if(m.find(i) != m.end()) { /* Assume map implementation is correct. */ @@ -157,7 +156,7 @@ 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; + buf[i] = i+1; return buf; } @@ -181,11 +180,11 @@ int main() int32_t *keys4 = new int32_t[64]; for(int32_t i = 0; i < 64; i++) { if(i < 32) - keys4[i] = i; + keys4[i] = i+1; else - keys4[i] = 10100+i; + keys4[i] = 10101+i; } - printf("1-32 and 10033-10064 ====\n"); + printf("1-32 and 10133-10164 ====\n"); test(keys4, 64); delete[] keys4; } diff --git a/upb_table.c b/upb_table.c index 9753088..e74e47a 100644 --- a/upb_table.c +++ b/upb_table.c @@ -89,7 +89,7 @@ static void intinsert(struct upb_inttable *t, struct upb_inttable_entry *e) * place our new element and append it to this key's chain. */ uint32_t empty_bucket = empty_intbucket(t); while (table_e->next != UPB_END_OF_CHAIN) - table_e = intent(t, table_e->next-1); + table_e = intent(t, table_e->next); table_e->next = empty_bucket; table_e = intent(t, empty_bucket); } else { @@ -101,7 +101,7 @@ static void intinsert(struct upb_inttable *t, struct upb_inttable_entry *e) struct upb_inttable_entry *evictee_e = intent(t, evictee_bucket); while(1) { assert(evictee_e->key != UPB_EMPTY_ENTRY); - assert(evictee_e->next != END_OF_CHAIN); + assert(evictee_e->next != UPB_END_OF_CHAIN); if(evictee_e->next == bucket) { evictee_e->next = empty_bucket; break; @@ -116,6 +116,7 @@ static void intinsert(struct upb_inttable *t, struct upb_inttable_entry *e) void upb_inttable_insert(struct upb_inttable *t, struct upb_inttable_entry *e) { + assert(e->key != 0); if((double)++t->t.count / upb_inttable_size(t) > MAX_LOAD) { /* Need to resize. New table of double the size, add old elements to it. */ struct upb_inttable new_table; @@ -127,7 +128,7 @@ void upb_inttable_insert(struct upb_inttable *t, struct upb_inttable_entry *e) upb_inttable_free(t); *t = new_table; } - intinsert(t->t.entries, e); + intinsert(t, e); } static uint32_t empty_strbucket(struct upb_strtable *table) @@ -151,7 +152,7 @@ static void strinsert(struct upb_strtable *t, struct upb_strtable_entry *e) * place our new element and append it to this key's chain. */ uint32_t empty_bucket = empty_strbucket(t); while (table_e->next != UPB_END_OF_CHAIN) - table_e = strent(t, table_e->next-1); + table_e = strent(t, table_e->next); table_e->next = empty_bucket; table_e = strent(t, empty_bucket); } else { @@ -162,8 +163,8 @@ static void strinsert(struct upb_strtable *t, struct upb_strtable_entry *e) memcpy(strent(t, empty_bucket), table_e, t->t.entry_size); /* copies next */ struct upb_strtable_entry *evictee_e = strent(t, evictee_bucket); while(1) { - assert(evictee_e->key != UPB_EMPTY_ENTRY); - assert(evictee_e->next != END_OF_CHAIN); + assert(evictee_e->key.byte_len != 0); + assert(evictee_e->next != UPB_END_OF_CHAIN); if(evictee_e->next == bucket) { evictee_e->next = empty_bucket; break; diff --git a/upb_table.h b/upb_table.h index 0c4df93..d024b85 100644 --- a/upb_table.h +++ b/upb_table.h @@ -15,6 +15,7 @@ #ifndef UPB_TABLE_H_ #define UPB_TABLE_H_ +#include <assert.h> #include "upb.h" #ifdef __cplusplus @@ -24,7 +25,8 @@ extern "C" { typedef uint32_t upb_inttable_key_t; #define UPB_END_OF_CHAIN (uint32_t)0 -#define UPB_INDEX(base, i, m) (void*)((char*)base + (i*m)) +#define UPB_EMPTY_ENTRY (uint32_t)0 +#define UPB_INDEX(base, i, m) (void*)((char*)(base) + ((i)*(m))) struct upb_inttable_entry { upb_inttable_key_t key; @@ -91,6 +93,7 @@ INLINE uint32_t upb_inttable_bucket(struct upb_inttable *t, upb_inttable_key_t k * compiler more ability to optimize. */ INLINE void *upb_inttable_lookup(struct upb_inttable *t, uint32_t key, uint32_t entry_size) { + assert(key != 0); uint32_t bucket = upb_inttable_bucket(t, key); struct upb_inttable_entry *e; do { |