From f1e1cc4695b34b292454e903adbf09e66cf2e9d5 Mon Sep 17 00:00:00 2001 From: Joshua Haberman Date: Thu, 17 Feb 2011 19:14:53 -0800 Subject: Split inttable into a hash part and an array part. upb_inttable() now supports a "compact" operation that will decide on an array size and put all entries with small enough keys into the array part for faster lookup. Also exposed the upb_itof_ent structure and put a few useful values there, so they are one fewer pointer chase away. --- src/upb.h | 6 + src/upb_decoder.c | 28 ++++- src/upb_def.c | 19 ++- src/upb_def.h | 30 +++-- src/upb_table.c | 360 ++++++++++++++++++++++++++++++++++++++---------------- src/upb_table.h | 164 ++++++++++++++++--------- 6 files changed, 413 insertions(+), 194 deletions(-) (limited to 'src') diff --git a/src/upb.h b/src/upb.h index 837fc52..c5b4310 100644 --- a/src/upb.h +++ b/src/upb.h @@ -29,6 +29,12 @@ extern "C" { #define UPB_MIN(x, y) ((x) < (y) ? (x) : (y)) #define UPB_INDEX(base, i, m) (void*)((char*)(base) + ((i)*(m))) +// Rounds val up to the next multiple of align. +INLINE size_t upb_align_up(size_t val, size_t align) { + return val % align == 0 ? val : val + align - (val % align); +} + + // The maximum that any submessages can be nested. Matches proto2's limit. #define UPB_MAX_NESTING 64 diff --git a/src/upb_decoder.c b/src/upb_decoder.c index 9c216d5..4467440 100644 --- a/src/upb_decoder.c +++ b/src/upb_decoder.c @@ -11,6 +11,12 @@ #include #include "upb_def.h" +// If the return value is other than UPB_CONTINUE, that is what the last +// callback returned. +extern upb_flow_t upb_fastdecode(const char **p, const char *end, + upb_value_handler_t *value_cb, void *closure, + void *table, int table_size); + /* Pure Decoding **************************************************************/ // The key fast-path varint-decoding routine. Here we can assume we have at @@ -329,6 +335,12 @@ void upb_decoder_run(upb_src *src, upb_status *status) { CHECK_FLOW(upb_pop(d)); } + // Decodes as many fields as possible, updating d->ptr appropriately, + // before falling through to the slow(er) path. + //CHECK_FLOW(upb_fastdecode(&d->ptr, d->end, + // d->dispatcher->top->handlers.set->value, + // d->top->handlers.closure)); + // Parse/handle tag. upb_tag tag; if (!upb_decode_tag(d, &tag)) { @@ -373,15 +385,19 @@ void upb_decoder_run(upb_src *src, upb_status *status) { } // Look up field by tag number. - upb_fielddef *f = upb_msgdef_itof(d->top->msgdef, tag.field_number); + upb_itof_ent *e = upb_msgdef_itofent(d->top->msgdef, tag.field_number); - if (!f) { + if (!e) { if (tag.wire_type == UPB_WIRE_TYPE_DELIMITED) CHECK(upb_decode_string(d, &val, &d->tmp)); CHECK_FLOW(upb_dispatch_unknownval(&d->dispatcher, tag.field_number, val)); continue; - } else if (!upb_check_type(tag.wire_type, f->type)) { - // TODO: put more details in this error msg. + } + + upb_fielddef *f = e->f; + + if (tag.wire_type != e->native_wire_type) { + // TODO: Support packed fields. upb_seterr(status, UPB_ERROR, "Field had incorrect type, name: " UPB_STRFMT ", field type: %d, expected wire type %d, actual wire type: %d", UPB_STRARG(f->name), f->type, upb_types[f->type].native_wire_type, @@ -398,10 +414,10 @@ void upb_decoder_run(upb_src *src, upb_status *status) { // that the top 32 bits all match the highest bit of the low 32 bits. // If this is not true we are losing data. But the main protobuf library // doesn't check this, and it would slow us down, so pass for now. - switch (f->type) { + switch (e->field_type) { case UPB_TYPE(MESSAGE): case UPB_TYPE(GROUP): - CHECK_FLOW(upb_push(d, f, val, f->type)); + CHECK_FLOW(upb_push(d, f, val, e->field_type)); continue; // We have no value to dispatch. case UPB_TYPE(STRING): case UPB_TYPE(BYTES): diff --git a/src/upb_def.c b/src/upb_def.c index 7e962c8..01143da 100644 --- a/src/upb_def.c +++ b/src/upb_def.c @@ -12,11 +12,6 @@ #define alignof(t) offsetof(struct { char c; t x; }, x) -/* Rounds p up to the next multiple of t. */ -static size_t upb_align_up(size_t val, size_t align) { - return val % align == 0 ? val : val + align - (val % align); -} - static int upb_div_round_up(int numerator, int denominator) { /* cf. http://stackoverflow.com/questions/17944/how-to-round-up-the-result-of-integer-division */ return numerator > 0 ? (numerator - 1) / denominator + 1 : 0; @@ -491,10 +486,10 @@ static upb_flow_t upb_enumdef_EnumValueDescriptorProto_endmsg(void *_b) { return UPB_BREAK; } upb_ntoi_ent ntoi_ent = {{b->name, 0}, b->number}; - upb_iton_ent iton_ent = {{b->number, 0}, b->name}; + upb_iton_ent iton_ent = {0, b->name}; upb_enumdef *e = upb_downcast_enumdef(upb_defbuilder_last(b)); upb_strtable_insert(&e->ntoi, &ntoi_ent.e); - upb_inttable_insert(&e->iton, &iton_ent.e); + upb_inttable_insert(&e->iton, b->number, &iton_ent); // We don't unref "name" because we pass our ref to the iton entry of the // table. strtables can ref their keys, but the inttable doesn't know that // the value is a string. @@ -579,8 +574,7 @@ upb_enum_iter upb_enum_begin(upb_enumdef *e) { } upb_enum_iter upb_enum_next(upb_enumdef *e, upb_enum_iter iter) { - assert(iter); - return upb_inttable_next(&e->iton, &iter->e); + return upb_inttable_next(&e->iton, iter); } upb_string *upb_enumdef_iton(upb_enumdef *def, upb_enumval_t num) { @@ -621,9 +615,9 @@ static upb_flow_t upb_fielddef_endmsg(void *_b) { // Field was successfully read, add it as a field of the msgdef. upb_msgdef *m = upb_defbuilder_top(b); - upb_itof_ent itof_ent = {{f->number, 0}, f}; + upb_itof_ent itof_ent = {0, upb_types[f->type].native_wire_type, f->type, f}; upb_ntof_ent ntof_ent = {{f->name, 0}, f}; - upb_inttable_insert(&m->itof, &itof_ent.e); + upb_inttable_insert(&m->itof, f->number, &itof_ent); upb_strtable_insert(&m->ntof, &ntof_ent.e); return UPB_CONTINUE; } @@ -702,6 +696,7 @@ static upb_flow_t upb_msgdef_endmsg(void *_b) { return UPB_BREAK; } + upb_inttable_compact(&m->itof); // Create an ordering over the fields. upb_field_count_t n = upb_msgdef_numfields(m); upb_fielddef **sorted_fields = malloc(sizeof(upb_fielddef*) * n); @@ -830,7 +825,7 @@ upb_msg_iter upb_msg_begin(upb_msgdef *m) { } upb_msg_iter upb_msg_next(upb_msgdef *m, upb_msg_iter iter) { - return upb_inttable_next(&m->itof, &iter->e); + return upb_inttable_next(&m->itof, iter); } /* upb_symtab adding defs *****************************************************/ diff --git a/src/upb_def.h b/src/upb_def.h index 6e4bc25..cca908b 100644 --- a/src/upb_def.h +++ b/src/upb_def.h @@ -162,7 +162,9 @@ typedef struct _upb_msgdef { // Hash table entries for looking up fields by name or number. typedef struct { - upb_inttable_entry e; + bool junk; + upb_wire_type_t native_wire_type; + upb_fieldtype_t field_type; upb_fielddef *f; } upb_itof_ent; typedef struct { @@ -173,9 +175,13 @@ typedef struct { // Looks up a field by name or number. While these are written to be as fast // as possible, it will still be faster to cache the results of this lookup if // possible. These return NULL if no such field is found. +INLINE upb_itof_ent *upb_msgdef_itofent(upb_msgdef *m, uint32_t num) { + return (upb_itof_ent*)upb_inttable_fastlookup( + &m->itof, num, sizeof(upb_itof_ent)); +} + INLINE upb_fielddef *upb_msgdef_itof(upb_msgdef *m, uint32_t num) { - upb_itof_ent *e = - (upb_itof_ent*)upb_inttable_fastlookup(&m->itof, num, sizeof(*e)); + upb_itof_ent *e = upb_msgdef_itofent(m, num); return e ? e->f : NULL; } @@ -194,14 +200,15 @@ INLINE upb_field_count_t upb_msgdef_numfields(upb_msgdef *m) { // upb_fielddef *f = upb_msg_iter_field(i); // // ... // } -typedef upb_itof_ent *upb_msg_iter; +typedef upb_inttable_iter upb_msg_iter; upb_msg_iter upb_msg_begin(upb_msgdef *m); upb_msg_iter upb_msg_next(upb_msgdef *m, upb_msg_iter iter); -INLINE bool upb_msg_done(upb_msg_iter iter) { return iter == NULL; } +INLINE bool upb_msg_done(upb_msg_iter iter) { return upb_inttable_done(iter); } INLINE upb_fielddef *upb_msg_iter_field(upb_msg_iter iter) { - return iter->f; + upb_itof_ent *ent = (upb_itof_ent*)upb_inttable_iter_value(iter); + return ent->f; } /* upb_enumdef ****************************************************************/ @@ -218,7 +225,7 @@ typedef struct { } upb_ntoi_ent; typedef struct { - upb_inttable_entry e; + bool junk; upb_string *string; } upb_iton_ent; @@ -234,17 +241,18 @@ upb_string *upb_enumdef_iton(upb_enumdef *e, upb_enumval_t num); // for(i = upb_enum_begin(e); !upb_enum_done(i); i = upb_enum_next(e, i)) { // // ... // } -typedef upb_iton_ent *upb_enum_iter; +typedef upb_inttable_iter upb_enum_iter; upb_enum_iter upb_enum_begin(upb_enumdef *e); upb_enum_iter upb_enum_next(upb_enumdef *e, upb_enum_iter iter); -INLINE bool upb_enum_done(upb_enum_iter iter) { return iter == NULL; } +INLINE bool upb_enum_done(upb_enum_iter iter) { return upb_inttable_done(iter); } INLINE upb_string *upb_enum_iter_name(upb_enum_iter iter) { - return iter->string; + upb_iton_ent *e = (upb_iton_ent*)upb_inttable_iter_value(iter); + return e->string; } INLINE int32_t upb_enum_iter_number(upb_enum_iter iter) { - return iter->e.key; + return upb_inttable_iter_key(iter); } diff --git a/src/upb_table.c b/src/upb_table.c index 720cc62..9a6cf7a 100644 --- a/src/upb_table.c +++ b/src/upb_table.c @@ -1,6 +1,8 @@ /* * upb - a minimalist implementation of protocol buffers. * + * There are a few printf's strewn throughout this file, uncommenting them + * can be useful for debugging. * Copyright (c) 2009 Joshua Haberman. See LICENSE for details. */ @@ -13,140 +15,294 @@ static const double MAX_LOAD = 0.85; +// The minimum percentage of an array part that we will allow. This is a +// speed/memory-usage tradeoff (though it's not straightforward because of +// cache effects). The lower this is, the more memory we'll use. +static const double MIN_DENSITY = 0.1; + static uint32_t MurmurHash2(const void *key, size_t len, uint32_t seed); -/* We use 1-based indexes into the table so that 0 can be "NULL". */ -static upb_inttable_entry *intent(upb_inttable *t, int32_t i) { - return UPB_INDEX(t->t.entries, i-1, t->t.entry_size); -} -static upb_strtable_entry *strent(upb_strtable *t, int32_t i) { - return UPB_INDEX(t->t.entries, i-1, t->t.entry_size); -} +/* Base table (shared code) ***************************************************/ -void upb_table_init(upb_table *t, uint32_t size, uint16_t entry_size) -{ +static uint32_t upb_table_size(upb_table *t) { return 1 << t->size_lg2; } +static size_t upb_table_entrysize(upb_table *t) { return t->entry_size; } +static size_t upb_table_valuesize(upb_table *t) { return t->value_size; } + +void upb_table_init(upb_table *t, uint32_t size, uint16_t entry_size) { t->count = 0; t->entry_size = entry_size; - t->size_lg2 = 0; - while(size >>= 1) t->size_lg2++; + t->size_lg2 = 1; + while(upb_table_size(t) < size) t->size_lg2++; size_t bytes = upb_table_size(t) * t->entry_size; t->mask = upb_table_size(t) - 1; t->entries = malloc(bytes); - memset(t->entries, 0, bytes); /* Both tables consider 0's an empty entry. */ } -void upb_inttable_init(upb_inttable *t, uint32_t size, uint16_t entsize) -{ - upb_table_init(&t->t, size, entsize); +void upb_table_free(upb_table *t) { free(t->entries); } + +/* upb_inttable ***************************************************************/ + +static upb_inttable_entry *intent(upb_inttable *t, int32_t i) { + //printf("looking up int entry %d, size of entry: %d\n", i, t->t.entry_size); + return UPB_INDEX(t->t.entries, i, t->t.entry_size); } -void upb_strtable_init(upb_strtable *t, uint32_t size, uint16_t entsize) -{ - upb_table_init(&t->t, size, entsize); +static uint32_t upb_inttable_hashtablesize(upb_inttable *t) { + return upb_table_size(&t->t); } -void upb_table_free(upb_table *t) { free(t->entries); } -void upb_inttable_free(upb_inttable *t) { upb_table_free(&t->t); } -void upb_strtable_free(upb_strtable *t) { - // Free refs from the strtable. - upb_strtable_entry *e = upb_strtable_begin(t); - for(; e; e = upb_strtable_next(t, e)) { - upb_string_unref(e->key); +void upb_inttable_sizedinit(upb_inttable *t, uint32_t arrsize, uint32_t hashsize, + uint16_t value_size) { + size_t entsize = _upb_inttable_entrysize(value_size); + upb_table_init(&t->t, hashsize, entsize); + for (uint32_t i = 0; i < upb_table_size(&t->t); i++) { + upb_inttable_entry *e = intent(t, i); + e->hdr.key = 0; + e->hdr.next = UPB_END_OF_CHAIN; + e->val.has_entry = 0; + } + t->t.value_size = value_size; + // Always make the array part at least 1 long, so that we know key 0 + // won't be in the hash part (which lets us speed up that code path). + t->array_size = UPB_MAX(1, arrsize); + t->array = malloc(upb_table_valuesize(&t->t) * t->array_size); + t->array_count = 0; + for (uint32_t i = 0; i < t->array_size; i++) { + upb_inttable_value *val = UPB_INDEX(t->array, i, upb_table_valuesize(&t->t)); + val->has_entry = false; } - upb_table_free(&t->t); } -static uint32_t strtable_bucket(upb_strtable *t, upb_string *key) -{ - uint32_t hash = MurmurHash2(upb_string_getrobuf(key), upb_string_len(key), 0); - return (hash & (upb_strtable_size(t)-1)) + 1; +void upb_inttable_init(upb_inttable *t, uint32_t hashsize, uint16_t value_size) { + upb_inttable_sizedinit(t, 0, hashsize, value_size); } -void *upb_strtable_lookup(upb_strtable *t, upb_string *key) -{ - uint32_t bucket = strtable_bucket(t, key); - upb_strtable_entry *e; - do { - e = strent(t, bucket); - if(e->key && upb_streql(e->key, key)) return e; - } while((bucket = e->next) != UPB_END_OF_CHAIN); - return NULL; +void upb_inttable_free(upb_inttable *t) { + upb_table_free(&t->t); + free(t->array); } static uint32_t empty_intbucket(upb_inttable *table) { - /* TODO: does it matter that this is biased towards the front of the table? */ - for(uint32_t i = 1; i <= upb_inttable_size(table); i++) { + // TODO: does it matter that this is biased towards the front of the table? + for(uint32_t i = 0; i < upb_inttable_hashtablesize(table); i++) { upb_inttable_entry *e = intent(table, i); - if(!e->has_entry) return i; + if(!e->val.has_entry) return i; } assert(false); return 0; } -/* The insert routines have a lot more code duplication between int/string - * variants than I would like, but there's just a bit too much that varies to - * parameterize them. */ -static void intinsert(upb_inttable *t, upb_inttable_entry *e) -{ - assert(upb_inttable_lookup(t, e->key) == NULL); - t->t.count++; - uint32_t bucket = upb_inttable_bucket(t, e->key); - upb_inttable_entry *table_e = intent(t, bucket); - if(table_e->has_entry) { /* Collision. */ - if(bucket == upb_inttable_bucket(t, table_e->key)) { - /* Existing element is in its main posisiton. Find an empty slot to - * 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); - table_e->next = empty_bucket; - table_e = intent(t, empty_bucket); - } else { - /* Existing element is not in its main position. Move it to an empty - * slot and put our element in its main position. */ - uint32_t empty_bucket = empty_intbucket(t); - uint32_t evictee_bucket = upb_inttable_bucket(t, table_e->key); - memcpy(intent(t, empty_bucket), table_e, t->t.entry_size); /* copies next */ - upb_inttable_entry *evictee_e = intent(t, evictee_bucket); - while(1) { - assert(evictee_e->has_entry); - assert(evictee_e->next != UPB_END_OF_CHAIN); - if(evictee_e->next == bucket) { - evictee_e->next = empty_bucket; - break; +// The insert routines have a lot more code duplication between int/string +// variants than I would like, but there's just a bit too much that varies to +// parameterize them. +static void intinsert(upb_inttable *t, upb_inttable_key_t key, void *val) { + assert(upb_inttable_lookup(t, key) == NULL); + upb_inttable_value *table_val; + if (_upb_inttable_isarrkey(t, key)) { + table_val = UPB_INDEX(t->array, key, upb_table_valuesize(&t->t)); + //printf("Inserting key %d to Array part! %p\n", key, table_val); + } else { + t->t.count++; + uint32_t bucket = _upb_inttable_bucket(t, key); + upb_inttable_entry *table_e = intent(t, bucket); + //printf("Hash part! Inserting into bucket %d?\n", bucket); + if(table_e->val.has_entry) { /* Collision. */ + //printf("Collision!\n"); + if(bucket == _upb_inttable_bucket(t, table_e->hdr.key)) { + /* Existing element is in its main posisiton. Find an empty slot to + * place our new element and append it to this key's chain. */ + uint32_t empty_bucket = empty_intbucket(t); + while (table_e->hdr.next != UPB_END_OF_CHAIN) + table_e = intent(t, table_e->hdr.next); + table_e->hdr.next = empty_bucket; + table_e = intent(t, empty_bucket); + } else { + /* Existing element is not in its main position. Move it to an empty + * slot and put our element in its main position. */ + uint32_t empty_bucket = empty_intbucket(t); + uint32_t evictee_bucket = _upb_inttable_bucket(t, table_e->hdr.key); + memcpy(intent(t, empty_bucket), table_e, t->t.entry_size); /* copies next */ + upb_inttable_entry *evictee_e = intent(t, evictee_bucket); + while(1) { + assert(evictee_e->val.has_entry); + assert(evictee_e->hdr.next != UPB_END_OF_CHAIN); + if(evictee_e->hdr.next == bucket) { + evictee_e->hdr.next = empty_bucket; + break; + } + evictee_e = intent(t, evictee_e->hdr.next); } - evictee_e = intent(t, evictee_e->next); + /* table_e remains set to our mainpos. */ } - /* table_e remains set to our mainpos. */ } + //printf("Inserting! to:%p, copying to: %p\n", table_e, &table_e->val); + table_val = &table_e->val; + table_e->hdr.key = key; + table_e->hdr.next = UPB_END_OF_CHAIN; } - memcpy(table_e, e, t->t.entry_size); - table_e->next = UPB_END_OF_CHAIN; - table_e->has_entry = true; - assert(upb_inttable_lookup(t, e->key) == table_e); + memcpy(table_val, val, upb_table_valuesize(&t->t)); + table_val->has_entry = true; + assert(upb_inttable_lookup(t, key) == table_val); } -void upb_inttable_insert(upb_inttable *t, upb_inttable_entry *e) -{ - if((double)(t->t.count + 1) / upb_inttable_size(t) > MAX_LOAD) { - /* Need to resize. New table of double the size, add old elements to it. */ +// Insert all elements from src into dest. Caller ensures that a resize will +// not be necessary. +static void upb_inttable_insertall(upb_inttable *dst, upb_inttable *src) { + for(upb_inttable_iter i = upb_inttable_begin(src); !upb_inttable_done(i); + i = upb_inttable_next(src, i)) { + //printf("load check: %d %d\n", upb_inttable_count(dst), upb_inttable_hashtablesize(dst)); + assert((double)(upb_inttable_count(dst)) / + upb_inttable_hashtablesize(dst) <= MAX_LOAD); + intinsert(dst, upb_inttable_iter_key(i), upb_inttable_iter_value(i)); + } +} + +void upb_inttable_insert(upb_inttable *t, upb_inttable_key_t key, void *val) { + if((double)(t->t.count + 1) / upb_inttable_hashtablesize(t) > MAX_LOAD) { + //printf("RESIZE!\n"); + // Need to resize. Allocate new table with double the size of however many + // elements we have now, add old elements to it. We create the new hash + // table without an array part, even if the old table had an array part. + // If/when the user calls upb_inttable_compact() again, we'll create an + // array part then. upb_inttable new_table; - upb_inttable_init(&new_table, upb_inttable_size(t)*2, t->t.entry_size); - new_table.t.count = t->t.count; - upb_inttable_entry *old_e; - for(old_e = upb_inttable_begin(t); old_e; old_e = upb_inttable_next(t, old_e)) - intinsert(&new_table, old_e); + //printf("Old table count=%d, size=%d\n", upb_inttable_count(t), upb_inttable_hashtablesize(t)); + upb_inttable_init(&new_table, upb_inttable_count(t)*2, upb_table_valuesize(&t->t)); + upb_inttable_insertall(&new_table, t); upb_inttable_free(t); *t = new_table; } - intinsert(t, e); + intinsert(t, key, val); +} + +void upb_inttable_compact(upb_inttable *t) { + // Find the largest array part we can that satisfies the MIN_DENSITY + // definition. For now we just count down powers of two. + upb_inttable_key_t largest_key = 0; + for(upb_inttable_iter i = upb_inttable_begin(t); !upb_inttable_done(i); + i = upb_inttable_next(t, i)) { + largest_key = UPB_MAX(largest_key, upb_inttable_iter_key(i)); + } + int lg2_array = 0; + while ((1UL << lg2_array) < largest_key) ++lg2_array; + ++lg2_array; // Undo the first iteration. + size_t array_size; + int array_count; + while (lg2_array > 0) { + array_size = (1 << --lg2_array); + //printf("Considering size %d (btw, our table has %d things total)\n", array_size, upb_inttable_count(t)); + if ((double)upb_inttable_count(t) / array_size < MIN_DENSITY) { + // Even if 100% of the keys were in the array pary, an array of this + // size would not be dense enough. + continue; + } + array_count = 0; + for(upb_inttable_iter i = upb_inttable_begin(t); !upb_inttable_done(i); + i = upb_inttable_next(t, i)) { + if (upb_inttable_iter_key(i) < array_size) + array_count++; + } + //printf("There would be %d things in that array\n", array_count); + if ((double)array_count / array_size >= MIN_DENSITY) break; + } + upb_inttable new_table; + int hash_size = (upb_inttable_count(t) - array_count + 1) / MAX_LOAD; + upb_inttable_sizedinit(&new_table, array_size, hash_size, + upb_table_valuesize(&t->t)); + //printf("For %d things, using array size=%d, hash_size = %d\n", upb_inttable_count(t), array_size, hash_size); + upb_inttable_insertall(&new_table, t); + upb_inttable_free(t); + *t = new_table; +} + +upb_inttable_iter upb_inttable_begin(upb_inttable *t) { + upb_inttable_iter iter = {-1, NULL, true}; // -1 will overflow to 0 on the first iteration. + return upb_inttable_next(t, iter); +} + +upb_inttable_iter upb_inttable_next(upb_inttable *t, upb_inttable_iter iter) { + const size_t hdrsize = sizeof(upb_inttable_header); + const size_t entsize = upb_table_entrysize(&t->t); + if (iter.array_part) { + while (++iter.key < t->array_size) { + //printf("considering value %d\n", iter.key); + iter.value = UPB_INDEX(t->array, iter.key, t->t.value_size); + if (iter.value->has_entry) return iter; + } + //printf("Done with array part!\n"); + iter.array_part = false; + // Point to the value of the table[-1] entry. + iter.value = UPB_INDEX(intent(t, -1), 1, hdrsize); + } + void *end = intent(t, upb_inttable_hashtablesize(t)); + // Point to the entry for the value that was previously in iter. + upb_inttable_entry *e = UPB_INDEX(iter.value, -1, hdrsize); + do { + e = UPB_INDEX(e, 1, entsize); + //printf("considering value %p (val: %p)\n", e, &e->val); + if(e == end) { + //printf("No values.\n"); + iter.value = NULL; + return iter; + } + } while(!e->val.has_entry); + //printf("USING VALUE! %p\n", e); + iter.key = e->hdr.key; + iter.value = &e->val; + return iter; +} + + +/* upb_strtable ***************************************************************/ + +static upb_strtable_entry *strent(upb_strtable *t, int32_t i) { + return UPB_INDEX(t->t.entries, i, t->t.entry_size); +} + +static uint32_t upb_strtable_size(upb_strtable *t) { + return upb_table_size(&t->t); +} + +void upb_strtable_init(upb_strtable *t, uint32_t size, uint16_t entsize) { + upb_table_init(&t->t, size, entsize); + for (uint32_t i = 0; i < upb_table_size(&t->t); i++) { + upb_strtable_entry *e = strent(t, i); + e->key = NULL; + e->next = UPB_END_OF_CHAIN; + } +} + +void upb_strtable_free(upb_strtable *t) { + // Free refs from the strtable. + upb_strtable_entry *e = upb_strtable_begin(t); + for(; e; e = upb_strtable_next(t, e)) { + upb_string_unref(e->key); + } + upb_table_free(&t->t); +} + +static uint32_t strtable_bucket(upb_strtable *t, upb_string *key) +{ + uint32_t hash = MurmurHash2(upb_string_getrobuf(key), upb_string_len(key), 0); + return (hash & t->t.mask); +} + +void *upb_strtable_lookup(upb_strtable *t, upb_string *key) +{ + uint32_t bucket = strtable_bucket(t, key); + upb_strtable_entry *e; + do { + e = strent(t, bucket); + if(e->key && upb_streql(e->key, key)) return e; + } while((bucket = e->next) != UPB_END_OF_CHAIN); + return NULL; } static uint32_t empty_strbucket(upb_strtable *table) { - /* TODO: does it matter that this is biased towards the front of the table? */ - for(uint32_t i = 1; i <= upb_strtable_size(table); i++) { + // TODO: does it matter that this is biased towards the front of the table? + for(uint32_t i = 0; i < upb_strtable_size(table); i++) { upb_strtable_entry *e = strent(table, i); if(!e->key) return i; } @@ -191,13 +347,16 @@ static void strinsert(upb_strtable *t, upb_strtable_entry *e) } memcpy(table_e, e, t->t.entry_size); table_e->next = UPB_END_OF_CHAIN; + //printf("Looking up, string=" UPB_STRFMT "...\n", UPB_STRARG(e->key)); assert(upb_strtable_lookup(t, e->key) == table_e); + //printf("Yay!\n"); } void upb_strtable_insert(upb_strtable *t, upb_strtable_entry *e) { if((double)(t->t.count + 1) / upb_strtable_size(t) > MAX_LOAD) { - /* Need to resize. New table of double the size, add old elements to it. */ + // Need to resize. New table of double the size, add old elements to it. + //printf("RESIZE!!\n"); upb_strtable new_table; upb_strtable_init(&new_table, upb_strtable_size(t)*2, t->t.entry_size); upb_strtable_entry *old_e; @@ -209,25 +368,12 @@ void upb_strtable_insert(upb_strtable *t, upb_strtable_entry *e) strinsert(t, e); } -void *upb_inttable_begin(upb_inttable *t) { - return upb_inttable_next(t, intent(t, 0)); -} - -void *upb_inttable_next(upb_inttable *t, upb_inttable_entry *cur) { - upb_inttable_entry *end = intent(t, upb_inttable_size(t)+1); - do { - cur = (void*)((char*)cur + t->t.entry_size); - if(cur == end) return NULL; - } while(!cur->has_entry); - return cur; -} - void *upb_strtable_begin(upb_strtable *t) { - return upb_strtable_next(t, strent(t, 0)); + return upb_strtable_next(t, strent(t, -1)); } void *upb_strtable_next(upb_strtable *t, upb_strtable_entry *cur) { - upb_strtable_entry *end = strent(t, upb_strtable_size(t)+1); + upb_strtable_entry *end = strent(t, upb_strtable_size(t)); do { cur = (void*)((char*)cur + t->t.entry_size); if(cur == end) return NULL; diff --git a/src/upb_table.h b/src/upb_table.h index b173101..3903c75 100644 --- a/src/upb_table.h +++ b/src/upb_table.h @@ -25,12 +25,21 @@ extern "C" { typedef uint32_t upb_inttable_key_t; -#define UPB_END_OF_CHAIN (uint32_t)0 +#define UPB_END_OF_CHAIN (uint32_t)-1 typedef struct { - upb_inttable_key_t key; bool has_entry:1; - uint32_t next:31; // Internal chaining. + // The rest of the bits are the user's. +} upb_inttable_value; + +typedef struct { + upb_inttable_key_t key; + uint32_t next; // Internal chaining. +} upb_inttable_header; + +typedef struct { + upb_inttable_header hdr; + upb_inttable_value val; } upb_inttable_entry; // TODO: consider storing the hash in the entry. This would avoid the need to @@ -43,11 +52,12 @@ typedef struct { } upb_strtable_entry; typedef struct { - void *entries; - uint32_t count; /* How many elements are currently in the table? */ - uint16_t entry_size; /* How big is each entry? */ - uint8_t size_lg2; /* The table is 2^size_lg2 in size. */ - uint32_t mask; + void *entries; // Hash table. + uint32_t count; // Number of entries in the hash part. + uint32_t mask; // Mask to turn hash value -> bucket. + uint16_t entry_size; // Size of each entry. + uint16_t value_size; // Size of each value. + uint8_t size_lg2; // Size of the hash table part is 2^size_lg2 entries. } upb_table; typedef struct { @@ -56,83 +66,121 @@ typedef struct { typedef struct { upb_table t; + void *array; // Array part of the table. + uint32_t array_size; // Array part size. + uint32_t array_count; // Array part number of elements. } upb_inttable; -/* Initialize and free a table, respectively. Specify the initial size - * with 'size' (the size will be increased as necessary). Entry size - * specifies how many bytes each entry in the table is. */ -void upb_inttable_init(upb_inttable *table, uint32_t size, uint16_t entry_size); +// Initialize and free a table, respectively. Specify the initial size +// with 'size' (the size will be increased as necessary). Value size +// specifies how many bytes each value in the table is. +// +// WARNING! The lowest bit of every entry is reserved by the hash table. +// It will always be overwritten when you insert, and must not be modified +// when looked up! +void upb_inttable_init(upb_inttable *table, uint32_t size, uint16_t value_size); void upb_inttable_free(upb_inttable *table); -void upb_strtable_init(upb_strtable *table, uint32_t size, uint16_t entry_size); +void upb_strtable_init(upb_strtable *table, uint32_t size, uint16_t entry_size); // TODO: update void upb_strtable_free(upb_strtable *table); -INLINE uint32_t upb_table_size(upb_table *t) { return 1 << t->size_lg2; } -INLINE uint32_t upb_inttable_size(upb_inttable *t) { - return upb_table_size(&t->t); -} -INLINE uint32_t upb_strtable_size(upb_strtable *t) { - return upb_table_size(&t->t); -} - +// Number of values in the hash table. INLINE uint32_t upb_table_count(upb_table *t) { return t->count; } INLINE uint32_t upb_inttable_count(upb_inttable *t) { - return upb_table_count(&t->t); + return t->array_count + upb_table_count(&t->t); } INLINE uint32_t upb_strtable_count(upb_strtable *t) { return upb_table_count(&t->t); } -/* Inserts the given key into the hashtable with the given value. The key must - * not already exist in the hash table. The data will be copied from e into - * the hashtable (the amount of data copied comes from entry_size when the - * table was constructed). Therefore the data at val may be freed once the - * call returns. */ -void upb_inttable_insert(upb_inttable *t, upb_inttable_entry *e); -void upb_strtable_insert(upb_strtable *t, upb_strtable_entry *e); +// Inserts the given key into the hashtable with the given value. The key must +// not already exist in the hash table. The data will be copied from val into +// the hashtable (the amount of data copied comes from value_size when the +// table was constructed). Therefore the data at val may be freed once the +// call returns. For string tables, the table takes a ref on str. +// +// WARNING: the lowest bit of val is reserved and will be overwritten! +void upb_inttable_insert(upb_inttable *t, upb_inttable_key_t key, void *val); +void upb_strtable_insert(upb_strtable *t, upb_strtable_entry *ent); // TODO: update +void upb_inttable_compact(upb_inttable *t); + +INLINE uint32_t _upb_inttable_bucket(upb_inttable *t, upb_inttable_key_t k) { + uint32_t bucket = k & t->t.mask; // Identity hash for ints. + assert(bucket != UPB_END_OF_CHAIN); + return bucket; +} -INLINE uint32_t upb_inttable_bucket(upb_inttable *t, upb_inttable_key_t k) { - return (k & t->t.mask) + 1; /* Identity hash for ints. */ +// Returns true if this key belongs in the array part of the table. +INLINE bool _upb_inttable_isarrkey(upb_inttable *t, upb_inttable_key_t k) { + return (k < t->array_size); } -/* Looks up key in this table. Inlined because this is in the critical path of - * decoding. We have the caller specify the entry_size because fixing this as - * a literal (instead of reading table->entry_size) gives the compiler more - * ability to optimize. */ -INLINE void *upb_inttable_fastlookup(upb_inttable *t, uint32_t key, - uint32_t entry_size) { - uint32_t bucket = upb_inttable_bucket(t, key); +// Looks up key in this table, returning a pointer to the user's inserted data. +// We have the caller specify the entry_size because fixing this as a literal +// (instead of reading table->entry_size) gives the compiler more ability to +// optimize. +INLINE void *_upb_inttable_fastlookup(upb_inttable *t, uint32_t key, + size_t entry_size, size_t value_size) { + upb_inttable_value *arrval = + (upb_inttable_value*)UPB_INDEX(t->array, key, value_size); + if (_upb_inttable_isarrkey(t, key)) { + //printf("array lookup for key %d, &val=%p, has_entry=%d\n", key, val, val->has_entry); + return (arrval->has_entry) ? arrval : NULL; + } + uint32_t bucket = _upb_inttable_bucket(t, key); upb_inttable_entry *e = - (upb_inttable_entry*)UPB_INDEX(t->t.entries, bucket-1, entry_size); - if (key == 0) { - while (1) { - if (e->key == 0 && e->has_entry) return e; - if ((bucket = e->next) == UPB_END_OF_CHAIN) return NULL; - e = (upb_inttable_entry*)UPB_INDEX(t->t.entries, bucket-1, entry_size); - } - } else { - while (1) { - if (e->key == key) return e; - if ((bucket = e->next) == UPB_END_OF_CHAIN) return NULL; - e = (upb_inttable_entry*)UPB_INDEX(t->t.entries, bucket-1, entry_size); - } + (upb_inttable_entry*)UPB_INDEX(t->t.entries, bucket, entry_size); + //printf("looking in first bucket %d, entry size=%zd, addr=%p\n", bucket, entry_size, e); + while (1) { + //printf("%d, %d, %d\n", e->val.has_entry, e->hdr.key, key); + if (e->hdr.key == key) return &e->val; + if ((bucket = e->hdr.next) == UPB_END_OF_CHAIN) return NULL; + //printf("looking in bucket %d\n", bucket); + e = (upb_inttable_entry*)UPB_INDEX(t->t.entries, bucket, entry_size); } } +INLINE size_t _upb_inttable_entrysize(size_t value_size) { + return upb_align_up(sizeof(upb_inttable_header) + value_size, 8); +} + +INLINE void *upb_inttable_fastlookup(upb_inttable *t, uint32_t key, + uint32_t value_size) { + return _upb_inttable_fastlookup(t, key, _upb_inttable_entrysize(value_size), value_size); +} + INLINE void *upb_inttable_lookup(upb_inttable *t, uint32_t key) { - return upb_inttable_fastlookup(t, key, t->t.entry_size); + return _upb_inttable_fastlookup(t, key, t->t.entry_size, t->t.value_size); } void *upb_strtable_lookup(upb_strtable *t, upb_string *key); -/* Provides iteration over the table. The order in which the entries are - * returned is undefined. Insertions invalidate iterators. The _next - * functions return NULL when the end has been reached. */ -void *upb_inttable_begin(upb_inttable *t); -void *upb_inttable_next(upb_inttable *t, upb_inttable_entry *cur); - +// Provides iteration over the table. The order in which the entries are +// returned is undefined. Insertions invalidate iterators. void *upb_strtable_begin(upb_strtable *t); void *upb_strtable_next(upb_strtable *t, upb_strtable_entry *cur); +// Inttable iteration (should update strtable iteration to use this scheme too). +// The order is undefined. +// for(upb_inttable_iter i = upb_inttable_begin(t); !upb_inttable_done(i); +// i = upb_inttable_next(t, i)) { +// // ... +// } +typedef struct { + upb_inttable_key_t key; + upb_inttable_value *value; + bool array_part; +} upb_inttable_iter; + +upb_inttable_iter upb_inttable_begin(upb_inttable *t); +upb_inttable_iter upb_inttable_next(upb_inttable *t, upb_inttable_iter iter); +INLINE bool upb_inttable_done(upb_inttable_iter iter) { return iter.value == NULL; } +INLINE upb_inttable_key_t upb_inttable_iter_key(upb_inttable_iter iter) { + return iter.key; +} +INLINE void *upb_inttable_iter_value(upb_inttable_iter iter) { + return iter.value; +} + #ifdef __cplusplus } /* extern "C" */ #endif -- cgit v1.2.3