diff options
Diffstat (limited to 'upb/table.c')
-rw-r--r-- | upb/table.c | 574 |
1 files changed, 574 insertions, 0 deletions
diff --git a/upb/table.c b/upb/table.c new file mode 100644 index 0000000..71aca16 --- /dev/null +++ b/upb/table.c @@ -0,0 +1,574 @@ +/* + * upb - a minimalist implementation of protocol buffers. + * + * Copyright (c) 2009 Google Inc. See LICENSE for details. + * Author: Josh Haberman <jhaberman@gmail.com> + * + * There are a few printf's strewn throughout this file, uncommenting them + * can be useful for debugging. + */ + +#include "upb/table.h" + +#include <assert.h> +#include <stdlib.h> +#include <string.h> + +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); + +/* Base table (shared code) ***************************************************/ + +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 = 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); +} + +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); +} + +static uint32_t upb_inttable_hashtablesize(upb_inttable *t) { + return upb_table_size(&t->t); +} + +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; + } +} + +void upb_inttable_init(upb_inttable *t, uint32_t hashsize, uint16_t value_size) { + upb_inttable_sizedinit(t, 0, hashsize, value_size); +} + +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 = 0; i < upb_inttable_hashtablesize(table); i++) { + upb_inttable_entry *e = intent(table, 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, uint32_t key, const 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)); + t->array_count++; + //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); + } + /* 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_val, val, upb_table_valuesize(&t->t)); + table_val->has_entry = true; + assert(upb_inttable_lookup(t, key) == table_val); +} + +// 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_table_count(&dst->t), upb_inttable_hashtablesize(dst)); + assert((double)(upb_table_count(&dst->t)) / + 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, 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 + // 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; + //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, 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. + 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)); + } + 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 = 0; + 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; + //printf("array_count: %d, array_size: %d, hash_size: %d, table size: %d\n", array_count, array_size, hash_size, upb_inttable_count(t)); + 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) { + //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); +} + +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 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->hdr.key = NULL; + e->hdr.next = UPB_END_OF_CHAIN; + } +} + +void upb_strtable_free(upb_strtable *t) { + // 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, const char *key) { + uint32_t hash = MurmurHash2(key, strlen(key), 0); + return (hash & t->t.mask); +} + +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->hdr.key && strcmp(e->hdr.key, key) == 0) return &e->val; + } while((bucket = e->hdr.next) != UPB_END_OF_CHAIN); + return NULL; +} + +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->hdr.key) return i; + } + assert(false); + return 0; +} + +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, key); + upb_strtable_entry *table_e = strent(t, bucket); + 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->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->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->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->hdr.next); + } + /* table_e remains set to our mainpos. */ + } + } + //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, 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.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, key, val); +} + +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_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 + 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 +//----------------------------------------------------------------------------- +// MurmurHash2, by Austin Appleby (released as public domain). +// Reformatted and C99-ified by Joshua Haberman. +// Note - This code makes a few assumptions about how your machine behaves - +// 1. We can read a 4-byte value from any address without crashing +// 2. sizeof(int) == 4 (in upb this limitation is removed by using uint32_t +// And it has a few limitations - +// 1. It will not work incrementally. +// 2. It will not produce the same results on little-endian and big-endian +// machines. +static uint32_t MurmurHash2(const void *key, size_t len, uint32_t seed) +{ + // 'm' and 'r' are mixing constants generated offline. + // They're not really 'magic', they just happen to work well. + const uint32_t m = 0x5bd1e995; + const int32_t r = 24; + + // Initialize the hash to a 'random' value + uint32_t h = seed ^ len; + + // Mix 4 bytes at a time into the hash + const uint8_t * data = (const uint8_t *)key; + while(len >= 4) { + uint32_t k = *(uint32_t *)data; + + k *= m; + k ^= k >> r; + k *= m; + + h *= m; + h ^= k; + + data += 4; + len -= 4; + } + + // Handle the last few bytes of the input array + switch(len) { + case 3: h ^= data[2] << 16; + case 2: h ^= data[1] << 8; + case 1: h ^= data[0]; h *= m; + }; + + // Do a few final mixes of the hash to ensure the last few + // bytes are well-incorporated. + h ^= h >> 13; + h *= m; + h ^= h >> 15; + + return h; +} + +#else // !UPB_UNALIGNED_READS_OK + +//----------------------------------------------------------------------------- +// MurmurHashAligned2, by Austin Appleby +// Same algorithm as MurmurHash2, but only does aligned reads - should be safer +// on certain platforms. +// Performance will be lower than MurmurHash2 + +#define MIX(h,k,m) { k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; } + +static uint32_t MurmurHash2(const void * key, size_t len, uint32_t seed) +{ + const uint32_t m = 0x5bd1e995; + const int32_t r = 24; + const uint8_t * data = (const uint8_t *)key; + uint32_t h = seed ^ len; + uint8_t align = (uintptr_t)data & 3; + + if(align && (len >= 4)) { + // Pre-load the temp registers + uint32_t t = 0, d = 0; + + switch(align) { + case 1: t |= data[2] << 16; + case 2: t |= data[1] << 8; + case 3: t |= data[0]; + } + + t <<= (8 * align); + + data += 4-align; + len -= 4-align; + + int32_t sl = 8 * (4-align); + int32_t sr = 8 * align; + + // Mix + + while(len >= 4) { + d = *(uint32_t *)data; + t = (t >> sr) | (d << sl); + + uint32_t k = t; + + MIX(h,k,m); + + t = d; + + data += 4; + len -= 4; + } + + // Handle leftover data in temp registers + + d = 0; + + if(len >= align) { + switch(align) { + case 3: d |= data[2] << 16; + case 2: d |= data[1] << 8; + case 1: d |= data[0]; + } + + uint32_t k = (t >> sr) | (d << sl); + MIX(h,k,m); + + data += align; + len -= align; + + //---------- + // Handle tail bytes + + switch(len) { + case 3: h ^= data[2] << 16; + case 2: h ^= data[1] << 8; + case 1: h ^= data[0]; h *= m; + }; + } else { + switch(len) { + case 3: d |= data[2] << 16; + case 2: d |= data[1] << 8; + case 1: d |= data[0]; + case 0: h ^= (t >> sr) | (d << sl); h *= m; + } + } + + h ^= h >> 13; + h *= m; + h ^= h >> 15; + + return h; + } else { + while(len >= 4) { + uint32_t k = *(uint32_t *)data; + + MIX(h,k,m); + + data += 4; + len -= 4; + } + + //---------- + // Handle tail bytes + + switch(len) { + case 3: h ^= data[2] << 16; + case 2: h ^= data[1] << 8; + case 1: h ^= data[0]; h *= m; + }; + + h ^= h >> 13; + h *= m; + h ^= h >> 15; + + return h; + } +} +#undef MIX + +#endif // UPB_UNALIGNED_READS_OK |