diff options
Diffstat (limited to 'upb/table.int.h')
| -rw-r--r-- | upb/table.int.h | 391 |
1 files changed, 212 insertions, 179 deletions
diff --git a/upb/table.int.h b/upb/table.int.h index b6e8eb7..28e2cff 100644 --- a/upb/table.int.h +++ b/upb/table.int.h @@ -35,9 +35,9 @@ extern "C" { /* upb_value ******************************************************************/ -// A tagged union (stored untagged inside the table) so that we can check that -// clients calling table accessors are correctly typed without having to have -// an explosion of accessors. +/* A tagged union (stored untagged inside the table) so that we can check that + * clients calling table accessors are correctly typed without having to have + * an explosion of accessors. */ typedef enum { UPB_CTYPE_INT32 = 1, UPB_CTYPE_INT64 = 2, @@ -47,85 +47,54 @@ typedef enum { UPB_CTYPE_CSTR = 6, UPB_CTYPE_PTR = 7, UPB_CTYPE_CONSTPTR = 8, - UPB_CTYPE_FPTR = 9, + UPB_CTYPE_FPTR = 9 } upb_ctype_t; -typedef union { - int32_t int32; - int64_t int64; - uint64_t uint64; - uint32_t uint32; - bool _bool; - char *cstr; - void *ptr; - const void *constptr; - upb_func *fptr; -} _upb_value; - typedef struct { - _upb_value val; + uint64_t val; #ifndef NDEBUG - // In debug mode we carry the value type around also so we can check accesses - // to be sure the right member is being read. + /* In debug mode we carry the value type around also so we can check accesses + * to be sure the right member is being read. */ upb_ctype_t ctype; #endif } upb_value; -#ifdef UPB_C99 -#define UPB_VALUE_INIT(v, member) {.member = v} -#endif -#define UPB__VALUE_INIT_NONE UPB_VALUE_INIT(NULL, ptr) - #ifdef NDEBUG #define SET_TYPE(dest, val) UPB_UNUSED(val) -#define UPB_VALUE_INIT_NONE {UPB__VALUE_INIT_NONE} #else #define SET_TYPE(dest, val) dest = val -// Non-existent type, all reads will fail. -#define UPB_VALUE_INIT_NONE {UPB__VALUE_INIT_NONE, -1} #endif -#define UPB_VALUE_INIT_INT32(v) UPB_VALUE_INIT(v, int32) -#define UPB_VALUE_INIT_INT64(v) UPB_VALUE_INIT(v, int64) -#define UPB_VALUE_INIT_UINT32(v) UPB_VALUE_INIT(v, uint32) -#define UPB_VALUE_INIT_UINT64(v) UPB_VALUE_INIT(v, uint64) -#define UPB_VALUE_INIT_BOOL(v) UPB_VALUE_INIT(v, _bool) -#define UPB_VALUE_INIT_CSTR(v) UPB_VALUE_INIT(v, cstr) -#define UPB_VALUE_INIT_PTR(v) UPB_VALUE_INIT(v, ptr) -#define UPB_VALUE_INIT_CONSTPTR(v) UPB_VALUE_INIT(v, constptr) -#define UPB_VALUE_INIT_FPTR(v) UPB_VALUE_INIT(v, fptr) - -// Like strdup(), which isn't always available since it's not ANSI C. +/* Like strdup(), which isn't always available since it's not ANSI C. */ char *upb_strdup(const char *s); -// Variant that works with a length-delimited rather than NULL-delimited string, -// as supported by strtable. +/* Variant that works with a length-delimited rather than NULL-delimited string, + * as supported by strtable. */ char *upb_strdup2(const char *s, size_t len); -UPB_INLINE void _upb_value_setval(upb_value *v, _upb_value val, +UPB_INLINE void _upb_value_setval(upb_value *v, uint64_t val, upb_ctype_t ctype) { v->val = val; SET_TYPE(v->ctype, ctype); } -UPB_INLINE upb_value _upb_value_val(_upb_value val, upb_ctype_t ctype) { +UPB_INLINE upb_value _upb_value_val(uint64_t val, upb_ctype_t ctype) { upb_value ret; _upb_value_setval(&ret, val, ctype); return ret; } -// For each value ctype, define the following set of functions: -// -// // Get/set an int32 from a upb_value. -// int32_t upb_value_getint32(upb_value val); -// void upb_value_setint32(upb_value *val, int32_t cval); -// -// // Construct a new upb_value from an int32. -// upb_value upb_value_int32(int32_t val); -#define FUNCS(name, membername, type_t, proto_type) \ +/* For each value ctype, define the following set of functions: + * + * // Get/set an int32 from a upb_value. + * int32_t upb_value_getint32(upb_value val); + * void upb_value_setint32(upb_value *val, int32_t cval); + * + * // Construct a new upb_value from an int32. + * upb_value upb_value_int32(int32_t val); */ +#define FUNCS(name, membername, type_t, converter, proto_type) \ UPB_INLINE void upb_value_set ## name(upb_value *val, type_t cval) { \ - val->val.uint64 = 0; \ + val->val = (converter)cval; \ SET_TYPE(val->ctype, proto_type); \ - val->val.membername = cval; \ } \ UPB_INLINE upb_value upb_value_ ## name(type_t val) { \ upb_value ret; \ @@ -134,31 +103,41 @@ UPB_INLINE upb_value _upb_value_val(_upb_value val, upb_ctype_t ctype) { } \ UPB_INLINE type_t upb_value_get ## name(upb_value val) { \ assert(val.ctype == proto_type); \ - return val.val.membername; \ + return (type_t)(converter)val.val; \ } -FUNCS(int32, int32, int32_t, UPB_CTYPE_INT32); -FUNCS(int64, int64, int64_t, UPB_CTYPE_INT64); -FUNCS(uint32, uint32, uint32_t, UPB_CTYPE_UINT32); -FUNCS(uint64, uint64, uint64_t, UPB_CTYPE_UINT64); -FUNCS(bool, _bool, bool, UPB_CTYPE_BOOL); -FUNCS(cstr, cstr, char*, UPB_CTYPE_CSTR); -FUNCS(ptr, ptr, void*, UPB_CTYPE_PTR); -FUNCS(constptr, constptr, const void*, UPB_CTYPE_CONSTPTR); -FUNCS(fptr, fptr, upb_func*, UPB_CTYPE_FPTR); +FUNCS(int32, int32, int32_t, int32_t, UPB_CTYPE_INT32) +FUNCS(int64, int64, int64_t, int64_t, UPB_CTYPE_INT64) +FUNCS(uint32, uint32, uint32_t, uint32_t, UPB_CTYPE_UINT32) +FUNCS(uint64, uint64, uint64_t, uint64_t, UPB_CTYPE_UINT64) +FUNCS(bool, _bool, bool, bool, UPB_CTYPE_BOOL) +FUNCS(cstr, cstr, char*, uintptr_t, UPB_CTYPE_CSTR) +FUNCS(ptr, ptr, void*, uintptr_t, UPB_CTYPE_PTR) +FUNCS(constptr, constptr, const void*, uintptr_t, UPB_CTYPE_CONSTPTR) +FUNCS(fptr, fptr, upb_func*, uintptr_t, UPB_CTYPE_FPTR) #undef FUNCS +#undef SET_TYPE -/* upb_table ******************************************************************/ +/* upb_tabkey *****************************************************************/ + +/* Either: + * 1. an actual integer key, or + * 2. a pointer to a string prefixed by its uint32_t length, owned by us. + * + * ...depending on whether this is a string table or an int table. We would + * make this a union of those two types, but C89 doesn't support statically + * initializing a non-first union member. */ +typedef uintptr_t upb_tabkey; #define UPB_TABKEY_NUM(n) n #define UPB_TABKEY_NONE 0 -// The preprocessor isn't quite powerful enough to turn the compile-time string -// length into a byte-wise string representation, so code generation needs to -// help it along. -// -// "len1" is the low byte and len4 is the high byte. +/* The preprocessor isn't quite powerful enough to turn the compile-time string + * length into a byte-wise string representation, so code generation needs to + * help it along. + * + * "len1" is the low byte and len4 is the high byte. */ #ifdef UPB_BIG_ENDIAN #define UPB_TABKEY_STR(len1, len2, len3, len4, strval) \ (uintptr_t)(len4 len3 len2 len1 strval) @@ -167,53 +146,105 @@ FUNCS(fptr, fptr, upb_func*, UPB_CTYPE_FPTR); (uintptr_t)(len1 len2 len3 len4 strval) #endif -// Either: -// 1. an actual integer key, or -// 2. a pointer to a string prefixed by its uint32_t length, owned by us. -// -// ...depending on whether this is a string table or an int table. We would -// make this a union of those two types, but C89 doesn't support statically -// initializing a non-first union member. -typedef uintptr_t upb_tabkey; - -// Ideally we could use a structure like this instead of the memcpy() calls: -// -// typedef struct { -// uint32_t len; -// char data[1]; // Allocate to correct length. -// } upb_tabstr; -// -// But unfortuantely in C89 there is no way to statically initialize such a -// thing. So instead of memcpy() the length in and out of the string. - UPB_INLINE char *upb_tabstr(upb_tabkey key, uint32_t *len) { char* mem = (char*)key; if (len) memcpy(len, mem, sizeof(*len)); return mem + sizeof(*len); } + +/* upb_tabval *****************************************************************/ + +#ifdef __cplusplus + +/* Status initialization not supported. + * + * This separate definition is necessary because in C++, UINTPTR_MAX isn't + * reliably available. */ +typedef struct { + uint64_t val; +} upb_tabval; + +#else + +/* C -- supports static initialization, but to support static initialization of + * both integers and points for both 32 and 64 bit targets, it takes a little + * bit of doing. */ + +#if UINTPTR_MAX == 0xffffffffffffffffULL +#define UPB_PTR_IS_64BITS +#elif UINTPTR_MAX != 0xffffffff +#error Could not determine how many bits pointers are. +#endif + +typedef union { + /* For static initialization. + * + * Unfortunately this ugliness is necessary -- it is the only way that we can, + * with -std=c89 -pedantic, statically initialize this to either a pointer or + * an integer on 32-bit platforms. */ + struct { +#ifdef UPB_PTR_IS_64BITS + uintptr_t val; +#else + uintptr_t val1; + uintptr_t val2; +#endif + } staticinit; + + /* The normal accessor that we use for everything at runtime. */ + uint64_t val; +} upb_tabval; + +#ifdef UPB_PTR_IS_64BITS +#define UPB_TABVALUE_INT_INIT(v) {{v}} +#define UPB_TABVALUE_EMPTY_INIT {{-1}} +#else + +/* 32-bit pointers */ + +#ifdef UPB_BIG_ENDIAN +#define UPB_TABVALUE_INT_INIT(v) {{0, v}} +#define UPB_TABVALUE_EMPTY_INIT {{-1, -1}} +#else +#define UPB_TABVALUE_INT_INIT(v) {{v, 0}} +#define UPB_TABVALUE_EMPTY_INIT {{-1, -1}} +#endif + +#endif + +#define UPB_TABVALUE_PTR_INIT(v) UPB_TABVALUE_INT_INIT((uintptr_t)v) + +#undef UPB_PTR_IS_64BITS + +#endif /* __cplusplus */ + + +/* upb_table ******************************************************************/ + typedef struct _upb_tabent { upb_tabkey key; - _upb_value val; + upb_tabval val; - // Internal chaining. This is const so we can create static initializers for - // tables. We cast away const sometimes, but *only* when the containing - // upb_table is known to be non-const. This requires a bit of care, but - // the subtlety is confined to table.c. + /* Internal chaining. This is const so we can create static initializers for + * tables. We cast away const sometimes, but *only* when the containing + * upb_table is known to be non-const. This requires a bit of care, but + * the subtlety is confined to table.c. */ const struct _upb_tabent *next; } upb_tabent; typedef struct { - size_t count; // Number of entries in the hash part. - size_t mask; // Mask to turn hash value -> bucket. - upb_ctype_t ctype; // Type of all values. - uint8_t size_lg2; // Size of the hash table part is 2^size_lg2 entries. - - // Hash table entries. - // Making this const isn't entirely accurate; what we really want is for it to - // have the same const-ness as the table it's inside. But there's no way to - // declare that in C. So we have to make it const so that we can statically - // initialize const hash tables. Then we cast away const when we have to. + size_t count; /* Number of entries in the hash part. */ + size_t mask; /* Mask to turn hash value -> bucket. */ + upb_ctype_t ctype; /* Type of all values. */ + uint8_t size_lg2; /* Size of the hashtable part is 2^size_lg2 entries. */ + + /* Hash table entries. + * Making this const isn't entirely accurate; what we really want is for it to + * have the same const-ness as the table it's inside. But there's no way to + * declare that in C. So we have to make it const so that we can statically + * initialize const hash tables. Then we cast away const when we have to. + */ const upb_tabent *entries; } upb_table; @@ -228,10 +259,10 @@ typedef struct { UPB_STRTABLE_INIT(0, 0, ctype, 0, NULL) typedef struct { - upb_table t; // For entries that don't fit in the array part. - const _upb_value *array; // Array part of the table. See const note above. - size_t array_size; // Array part size. - size_t array_count; // Array part number of elements. + upb_table t; /* For entries that don't fit in the array part. */ + const upb_tabval *array; /* Array part of the table. See const note above. */ + size_t array_size; /* Array part size. */ + size_t array_count; /* Array part number of elements. */ } upb_inttable; #define UPB_INTTABLE_INIT(count, mask, ctype, size_lg2, ent, a, asize, acount) \ @@ -240,8 +271,7 @@ typedef struct { #define UPB_EMPTY_INTTABLE_INIT(ctype) \ UPB_INTTABLE_INIT(0, 0, ctype, 0, NULL, NULL, 0, 0) -#define UPB_ARRAY_EMPTYVAL -1 -#define UPB_ARRAY_EMPTYENT UPB_VALUE_INIT_INT64(UPB_ARRAY_EMPTYVAL) +#define UPB_ARRAY_EMPTYENT -1 UPB_INLINE size_t upb_table_size(const upb_table *t) { if (t->size_lg2 == 0) @@ -250,12 +280,12 @@ UPB_INLINE size_t upb_table_size(const upb_table *t) { return 1 << t->size_lg2; } -// Internal-only functions, in .h file only out of necessity. +/* Internal-only functions, in .h file only out of necessity. */ UPB_INLINE bool upb_tabent_isempty(const upb_tabent *e) { return e->key == 0; } -// Used by some of the unit tests for generic hashing functionality. +/* Used by some of the unit tests for generic hashing functionality. */ uint32_t MurmurHash2(const void * key, size_t len, uint32_t seed); UPB_INLINE uintptr_t upb_intkey(uintptr_t key) { @@ -270,93 +300,94 @@ static const upb_tabent *upb_getentry(const upb_table *t, uint32_t hash) { return t->entries + (hash & t->mask); } -UPB_INLINE bool upb_arrhas(_upb_value v) { - return v.uint64 != (uint64_t)UPB_ARRAY_EMPTYVAL; +UPB_INLINE bool upb_arrhas(upb_tabval key) { + return key.val != (uint64_t)-1; } -// Initialize and uninitialize a table, respectively. If memory allocation -// failed, false is returned that the table is uninitialized. +/* Initialize and uninitialize a table, respectively. If memory allocation + * failed, false is returned that the table is uninitialized. */ bool upb_inttable_init(upb_inttable *table, upb_ctype_t ctype); bool upb_strtable_init(upb_strtable *table, upb_ctype_t ctype); void upb_inttable_uninit(upb_inttable *table); void upb_strtable_uninit(upb_strtable *table); -// Returns the number of values in the table. +/* Returns the number of values in the table. */ size_t upb_inttable_count(const upb_inttable *t); UPB_INLINE size_t upb_strtable_count(const upb_strtable *t) { return t->t.count; } -// Inserts the given key into the hashtable with the given value. The key must -// not already exist in the hash table. For string tables, the key must be -// NULL-terminated, and the table will make an internal copy of the key. -// Inttables must not insert a value of UINTPTR_MAX. -// -// If a table resize was required but memory allocation failed, false is -// returned and the table is unchanged. +/* Inserts the given key into the hashtable with the given value. The key must + * not already exist in the hash table. For string tables, the key must be + * NULL-terminated, and the table will make an internal copy of the key. + * Inttables must not insert a value of UINTPTR_MAX. + * + * If a table resize was required but memory allocation failed, false is + * returned and the table is unchanged. */ bool upb_inttable_insert(upb_inttable *t, uintptr_t key, upb_value val); bool upb_strtable_insert2(upb_strtable *t, const char *key, size_t len, upb_value val); -// For NULL-terminated strings. +/* For NULL-terminated strings. */ UPB_INLINE bool upb_strtable_insert(upb_strtable *t, const char *key, upb_value val) { return upb_strtable_insert2(t, key, strlen(key), val); } -// Looks up key in this table, returning "true" if the key was found. -// If v is non-NULL, copies the value for this key into *v. +/* Looks up key in this table, returning "true" if the key was found. + * If v is non-NULL, copies the value for this key into *v. */ bool upb_inttable_lookup(const upb_inttable *t, uintptr_t key, upb_value *v); bool upb_strtable_lookup2(const upb_strtable *t, const char *key, size_t len, upb_value *v); -// For NULL-terminated strings. +/* For NULL-terminated strings. */ UPB_INLINE bool upb_strtable_lookup(const upb_strtable *t, const char *key, upb_value *v) { return upb_strtable_lookup2(t, key, strlen(key), v); } -// Removes an item from the table. Returns true if the remove was successful, -// and stores the removed item in *val if non-NULL. +/* Removes an item from the table. Returns true if the remove was successful, + * and stores the removed item in *val if non-NULL. */ bool upb_inttable_remove(upb_inttable *t, uintptr_t key, upb_value *val); bool upb_strtable_remove2(upb_strtable *t, const char *key, size_t len, upb_value *val); -// For NULL-terminated strings. +/* For NULL-terminated strings. */ UPB_INLINE bool upb_strtable_remove(upb_strtable *t, const char *key, upb_value *v) { return upb_strtable_remove2(t, key, strlen(key), v); } -// Updates an existing entry in an inttable. If the entry does not exist, -// returns false and does nothing. Unlike insert/remove, this does not -// invalidate iterators. +/* Updates an existing entry in an inttable. If the entry does not exist, + * returns false and does nothing. Unlike insert/remove, this does not + * invalidate iterators. */ bool upb_inttable_replace(upb_inttable *t, uintptr_t key, upb_value val); -// Handy routines for treating an inttable like a stack. May not be mixed with -// other insert/remove calls. +/* Handy routines for treating an inttable like a stack. May not be mixed with + * other insert/remove calls. */ bool upb_inttable_push(upb_inttable *t, upb_value val); upb_value upb_inttable_pop(upb_inttable *t); -// Convenience routines for inttables with pointer keys. +/* Convenience routines for inttables with pointer keys. */ bool upb_inttable_insertptr(upb_inttable *t, const void *key, upb_value val); bool upb_inttable_removeptr(upb_inttable *t, const void *key, upb_value *val); bool upb_inttable_lookupptr( const upb_inttable *t, const void *key, upb_value *val); -// Optimizes the table for the current set of entries, for both memory use and -// lookup time. Client should call this after all entries have been inserted; -// inserting more entries is legal, but will likely require a table resize. +/* Optimizes the table for the current set of entries, for both memory use and + * lookup time. Client should call this after all entries have been inserted; + * inserting more entries is legal, but will likely require a table resize. */ void upb_inttable_compact(upb_inttable *t); -// A special-case inlinable version of the lookup routine for 32-bit integers. +/* A special-case inlinable version of the lookup routine for 32-bit + * integers. */ UPB_INLINE bool upb_inttable_lookup32(const upb_inttable *t, uint32_t key, upb_value *v) { - *v = upb_value_int32(0); // Silence compiler warnings. + *v = upb_value_int32(0); /* Silence compiler warnings. */ if (key < t->array_size) { - _upb_value arrval = t->array[key]; + upb_tabval arrval = t->array[key]; if (upb_arrhas(arrval)) { - _upb_value_setval(v, arrval, t->t.ctype); + _upb_value_setval(v, arrval.val, t->t.ctype); return true; } else { return false; @@ -366,7 +397,7 @@ UPB_INLINE bool upb_inttable_lookup32(const upb_inttable *t, uint32_t key, if (t->t.entries == NULL) return false; for (e = upb_getentry(&t->t, upb_inthash(key)); true; e = e->next) { if ((uint32_t)e->key == key) { - _upb_value_setval(v, e->val, t->t.ctype); + _upb_value_setval(v, e->val.val, t->t.ctype); return true; } if (e->next == NULL) return false; @@ -374,42 +405,43 @@ UPB_INLINE bool upb_inttable_lookup32(const upb_inttable *t, uint32_t key, } } -// Exposed for testing only. +/* Exposed for testing only. */ bool upb_strtable_resize(upb_strtable *t, size_t size_lg2); /* Iterators ******************************************************************/ -// Iterators for int and string tables. We are subject to some kind of unusual -// design constraints: -// -// For high-level languages: -// - we must be able to guarantee that we don't crash or corrupt memory even if -// the program accesses an invalidated iterator. -// -// For C++11 range-based for: -// - iterators must be copyable -// - iterators must be comparable -// - it must be possible to construct an "end" value. -// -// Iteration order is undefined. -// -// Modifying the table invalidates iterators. upb_{str,int}table_done() is -// guaranteed to work even on an invalidated iterator, as long as the table it -// is iterating over has not been freed. Calling next() or accessing data from -// an invalidated iterator yields unspecified elements from the table, but it is -// guaranteed not to crash and to return real table elements (except when done() -// is true). +/* Iterators for int and string tables. We are subject to some kind of unusual + * design constraints: + * + * For high-level languages: + * - we must be able to guarantee that we don't crash or corrupt memory even if + * the program accesses an invalidated iterator. + * + * For C++11 range-based for: + * - iterators must be copyable + * - iterators must be comparable + * - it must be possible to construct an "end" value. + * + * Iteration order is undefined. + * + * Modifying the table invalidates iterators. upb_{str,int}table_done() is + * guaranteed to work even on an invalidated iterator, as long as the table it + * is iterating over has not been freed. Calling next() or accessing data from + * an invalidated iterator yields unspecified elements from the table, but it is + * guaranteed not to crash and to return real table elements (except when done() + * is true). */ /* upb_strtable_iter **********************************************************/ -// upb_strtable_iter i; -// upb_strtable_begin(&i, t); -// for(; !upb_strtable_done(&i); upb_strtable_next(&i)) { -// const char *key = upb_strtable_iter_key(&i); -// const upb_value val = upb_strtable_iter_value(&i); -// // ... -// } +/* upb_strtable_iter i; + * upb_strtable_begin(&i, t); + * for(; !upb_strtable_done(&i); upb_strtable_next(&i)) { + * const char *key = upb_strtable_iter_key(&i); + * const upb_value val = upb_strtable_iter_value(&i); + * // ... + * } + */ typedef struct { const upb_strtable *t; @@ -429,13 +461,14 @@ bool upb_strtable_iter_isequal(const upb_strtable_iter *i1, /* upb_inttable_iter **********************************************************/ -// upb_inttable_iter i; -// upb_inttable_begin(&i, t); -// for(; !upb_inttable_done(&i); upb_inttable_next(&i)) { -// uintptr_t key = upb_inttable_iter_key(&i); -// upb_value val = upb_inttable_iter_value(&i); -// // ... -// } +/* upb_inttable_iter i; + * upb_inttable_begin(&i, t); + * for(; !upb_inttable_done(&i); upb_inttable_next(&i)) { + * uintptr_t key = upb_inttable_iter_key(&i); + * upb_value val = upb_inttable_iter_value(&i); + * // ... + * } + */ typedef struct { const upb_inttable *t; |