From 6a1f3a66939308668ab8dce0d195afec16e02af9 Mon Sep 17 00:00:00 2001 From: Joshua Haberman Date: Thu, 14 Jul 2011 23:15:00 -0700 Subject: Major refactoring: upb_string is gone in favor of upb_strref. --- src/upb_table.c | 127 +++++++++++++++++++++++++++++++------------------------- 1 file changed, 71 insertions(+), 56 deletions(-) (limited to 'src/upb_table.c') diff --git a/src/upb_table.c b/src/upb_table.c index a754097..fc9e9de 100644 --- a/src/upb_table.c +++ b/src/upb_table.c @@ -97,7 +97,7 @@ static uint32_t empty_intbucket(upb_inttable *table) // 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) { +static void intinsert(upb_inttable *t, uint32_t key, const void *val) { assert(upb_inttable_lookup(t, key) == NULL); upb_inttable_value *table_val; if (_upb_inttable_isarrkey(t, key)) { @@ -160,7 +160,7 @@ static void upb_inttable_insertall(upb_inttable *dst, upb_inttable *src) { } } -void upb_inttable_insert(upb_inttable *t, upb_inttable_key_t key, void *val) { +void upb_inttable_insert(upb_inttable *t, uint32_t key, const 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 @@ -181,7 +181,7 @@ void upb_inttable_insert(upb_inttable *t, upb_inttable_key_t key, void *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; + uint32_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)); @@ -260,6 +260,8 @@ upb_inttable_iter upb_inttable_next(upb_inttable *t, upb_inttable_iter iter) { /* upb_strtable ***************************************************************/ static upb_strtable_entry *strent(upb_strtable *t, int32_t i) { + //fprintf(stderr, "i: %d, table_size: %d\n", i, upb_table_size(&t->t)); + assert(i <= (int32_t)upb_table_size(&t->t)); return UPB_INDEX(t->t.entries, i, t->t.entry_size); } @@ -267,121 +269,134 @@ 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) { +void upb_strtable_init(upb_strtable *t, uint32_t size, uint16_t valuesize) { + t->t.value_size = valuesize; + size_t entsize = upb_align_up(sizeof(upb_strtable_header) + valuesize, 8); 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; + e->hdr.key = NULL; + e->hdr.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); - } + // Free keys from the strtable. + upb_strtable_iter i; + for(upb_strtable_begin(&i, t); !upb_strtable_done(&i); upb_strtable_next(&i)) + free((char*)upb_strtable_iter_key(&i)); 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); +static uint32_t strtable_bucket(upb_strtable *t, const char *key) { + uint32_t hash = MurmurHash2(key, strlen(key), 0); return (hash & t->t.mask); } -void *upb_strtable_lookup(upb_strtable *t, upb_string *key) -{ +void *upb_strtable_lookup(upb_strtable *t, const char *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); + if(e->hdr.key && strcmp(e->hdr.key, key) == 0) return &e->val; + } while((bucket = e->hdr.next) != UPB_END_OF_CHAIN); return NULL; } -static uint32_t empty_strbucket(upb_strtable *table) -{ +void *upb_strtable_lookupl(upb_strtable *t, const char *key, size_t len) { + // TODO: improve. + char key2[len+1]; + memcpy(key2, key, len); + key2[len] = '\0'; + return upb_strtable_lookup(t, key2); +} + +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 = 0; i < upb_strtable_size(table); i++) { upb_strtable_entry *e = strent(table, i); - if(!e->key) return i; + if(!e->hdr.key) return i; } assert(false); return 0; } -static void strinsert(upb_strtable *t, upb_strtable_entry *e) -{ - assert(upb_strtable_lookup(t, e->key) == NULL); - e->key = upb_string_getref(e->key); +static void strinsert(upb_strtable *t, const char *key, const void *val) { + assert(upb_strtable_lookup(t, key) == NULL); t->t.count++; - uint32_t bucket = strtable_bucket(t, e->key); + uint32_t bucket = strtable_bucket(t, key); upb_strtable_entry *table_e = strent(t, bucket); - if(table_e->key) { /* Collision. */ - if(bucket == strtable_bucket(t, table_e->key)) { + if(table_e->hdr.key) { /* Collision. */ + if(bucket == strtable_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_strbucket(t); - while (table_e->next != UPB_END_OF_CHAIN) - table_e = strent(t, table_e->next); - table_e->next = empty_bucket; + while (table_e->hdr.next != UPB_END_OF_CHAIN) + table_e = strent(t, table_e->hdr.next); + table_e->hdr.next = empty_bucket; table_e = strent(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_strbucket(t); - uint32_t evictee_bucket = strtable_bucket(t, table_e->key); + uint32_t evictee_bucket = strtable_bucket(t, table_e->hdr.key); memcpy(strent(t, empty_bucket), table_e, t->t.entry_size); /* copies next */ upb_strtable_entry *evictee_e = strent(t, evictee_bucket); while(1) { - assert(evictee_e->key); - assert(evictee_e->next != UPB_END_OF_CHAIN); - if(evictee_e->next == bucket) { - evictee_e->next = empty_bucket; + assert(evictee_e->hdr.key); + assert(evictee_e->hdr.next != UPB_END_OF_CHAIN); + if(evictee_e->hdr.next == bucket) { + evictee_e->hdr.next = empty_bucket; break; } - evictee_e = strent(t, evictee_e->next); + evictee_e = strent(t, evictee_e->hdr.next); } /* table_e remains set to our mainpos. */ } } - 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); + //fprintf(stderr, "val: %p\n", val); + //fprintf(stderr, "val size: %d\n", t->t.value_size); + memcpy(&table_e->val, val, t->t.value_size); + table_e->hdr.key = strdup(key); + table_e->hdr.next = UPB_END_OF_CHAIN; + //fprintf(stderr, "Looking up, string=%s...\n", key); + assert(upb_strtable_lookup(t, key) == &table_e->val); //printf("Yay!\n"); } -void upb_strtable_insert(upb_strtable *t, upb_strtable_entry *e) -{ +void upb_strtable_insert(upb_strtable *t, const char *key, const void *val) { 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. //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; - for(old_e = upb_strtable_begin(t); old_e; old_e = upb_strtable_next(t, old_e)) - strinsert(&new_table, old_e); + upb_strtable_init(&new_table, upb_strtable_size(t)*2, t->t.value_size); + upb_strtable_iter i; + upb_strtable_begin(&i, t); + for(; !upb_strtable_done(&i); upb_strtable_next(&i)) { + strinsert(&new_table, + upb_strtable_iter_key(&i), + upb_strtable_iter_value(&i)); + } upb_strtable_free(t); *t = new_table; } - strinsert(t, e); + strinsert(t, key, val); } -void *upb_strtable_begin(upb_strtable *t) { - return upb_strtable_next(t, strent(t, -1)); +void upb_strtable_begin(upb_strtable_iter *i, upb_strtable *t) { + i->e = strent(t, -1); + i->t = t; + upb_strtable_next(i); } -void *upb_strtable_next(upb_strtable *t, upb_strtable_entry *cur) { - upb_strtable_entry *end = strent(t, upb_strtable_size(t)); +void upb_strtable_next(upb_strtable_iter *i) { + upb_strtable_entry *end = strent(i->t, upb_strtable_size(i->t)); + upb_strtable_entry *cur = i->e; do { - cur = (void*)((char*)cur + t->t.entry_size); - if(cur == end) return NULL; - } while(cur->key == NULL); - return cur; + cur = (void*)((char*)cur + i->t->t.entry_size); + if(cur == end) { i->e = NULL; return; } + } while(cur->hdr.key == NULL); + i->e = cur; } #ifdef UPB_UNALIGNED_READS_OK -- cgit v1.2.3