upb/hash/common.h

0001 // Protocol Buffers - Google's data interchange format
0002 // Copyright 2023 Google LLC.  All rights reserved.
0003 //
0004 // Use of this source code is governed by a BSD-style
0005 // license that can be found in the LICENSE file or at
0006 // https://developers.google.com/open-source/licenses/bsd
0007
0008 /*
0009  * upb_table
0010  *
0011  * This header is INTERNAL-ONLY!  Its interfaces are not public or stable!
0012  * This file defines very fast int->upb_value (inttable) and string->upb_value
0013  * (strtable) hash tables.
0014  *
0015  * The table uses chained scatter with Brent's variation (inspired by the Lua
0016  * implementation of hash tables).  The hash function for strings is Austin
0017  * Appleby's "MurmurHash."
0018  *
0019  * The inttable uses uintptr_t as its key, which guarantees it can be used to
0020  * store pointers or integers of at least 32 bits (upb isn't really useful on
0021  * systems where sizeof(void*) < 4).
0022  *
0023  * The table must be homogeneous (all values of the same type).  In debug
0024  * mode, we check this on insert and lookup.
0025  */
0026
0027 #ifndef UPB_HASH_COMMON_H_
0028 #define UPB_HASH_COMMON_H_
0029
0030 #include <string.h>
0031
0032 #include "upb/base/string_view.h"
0033 #include "upb/mem/arena.h"
0034
0035 // Must be last.
0036 #include "upb/port/def.inc"
0037
0038 #ifdef __cplusplus
0039 extern "C" {
0040 #endif
0041
0042 /* upb_value ******************************************************************/
0043
0044 typedef struct {
0045   uint64_t val;
0046 } upb_value;
0047
0048 UPB_INLINE void _upb_value_setval(upb_value* v, uint64_t val) { v->val = val; }
0049
0050 /* For each value ctype, define the following set of functions:
0051  *
0052  * // Get/set an int32 from a upb_value.
0053  * int32_t upb_value_getint32(upb_value val);
0054  * void upb_value_setint32(upb_value *val, int32_t cval);
0055  *
0056  * // Construct a new upb_value from an int32.
0057  * upb_value upb_value_int32(int32_t val); */
0058 #define FUNCS(name, membername, type_t, converter)                   \
0059   UPB_INLINE void upb_value_set##name(upb_value* val, type_t cval) { \
0060     val->val = (converter)cval;                                      \
0061   }                                                                  \
0062   UPB_INLINE upb_value upb_value_##name(type_t val) {                \
0063     upb_value ret;                                                   \
0064     upb_value_set##name(&ret, val);                                  \
0065     return ret;                                                      \
0066   }                                                                  \
0067   UPB_INLINE type_t upb_value_get##name(upb_value val) {             \
0068     return (type_t)(converter)val.val;                               \
0069   }
0070
0071 FUNCS(int32, int32, int32_t, int32_t)
0072 FUNCS(int64, int64, int64_t, int64_t)
0073 FUNCS(uint32, uint32, uint32_t, uint32_t)
0074 FUNCS(uint64, uint64, uint64_t, uint64_t)
0075 FUNCS(bool, _bool, bool, bool)
0076 FUNCS(cstr, cstr, char*, uintptr_t)
0077 FUNCS(uintptr, uptr, uintptr_t, uintptr_t)
0078 FUNCS(ptr, ptr, void*, uintptr_t)
0079 FUNCS(constptr, constptr, const void*, uintptr_t)
0080
0081 #undef FUNCS
0082
0083 UPB_INLINE void upb_value_setfloat(upb_value* val, float cval) {
0084   memcpy(&val->val, &cval, sizeof(cval));
0085 }
0086
0087 UPB_INLINE void upb_value_setdouble(upb_value* val, double cval) {
0088   memcpy(&val->val, &cval, sizeof(cval));
0089 }
0090
0091 UPB_INLINE upb_value upb_value_float(float cval) {
0092   upb_value ret;
0093   upb_value_setfloat(&ret, cval);
0094   return ret;
0095 }
0096
0097 UPB_INLINE upb_value upb_value_double(double cval) {
0098   upb_value ret;
0099   upb_value_setdouble(&ret, cval);
0100   return ret;
0101 }
0102
0103 /* upb_tabkey *****************************************************************/
0104
0105 /* Either:
0106  *   1. an actual integer key, or
0107  *   2. a pointer to a string prefixed by its uint32_t length, owned by us.
0108  *
0109  * ...depending on whether this is a string table or an int table.  We would
0110  * make this a union of those two types, but C89 doesn't support statically
0111  * initializing a non-first union member. */
0112 typedef uintptr_t upb_tabkey;
0113
0114 UPB_INLINE char* upb_tabstr(upb_tabkey key, uint32_t* len) {
0115   char* mem = (char*)key;
0116   if (len) memcpy(len, mem, sizeof(*len));
0117   return mem + sizeof(*len);
0118 }
0119
0120 UPB_INLINE upb_StringView upb_tabstrview(upb_tabkey key) {
0121   upb_StringView ret;
0122   uint32_t len;
0123   ret.data = upb_tabstr(key, &len);
0124   ret.size = len;
0125   return ret;
0126 }
0127
0128 /* upb_tabval *****************************************************************/
0129
0130 typedef struct upb_tabval {
0131   uint64_t val;
0132 } upb_tabval;
0133
0134 #define UPB_TABVALUE_EMPTY_INIT \
0135   { -1 }
0136
0137 /* upb_table ******************************************************************/
0138
0139 typedef struct _upb_tabent {
0140   upb_tabkey key;
0141   upb_tabval val;
0142
0143   /* Internal chaining.  This is const so we can create static initializers for
0144    * tables.  We cast away const sometimes, but *only* when the containing
0145    * upb_table is known to be non-const.  This requires a bit of care, but
0146    * the subtlety is confined to table.c. */
0147   const struct _upb_tabent* next;
0148 } upb_tabent;
0149
0150 typedef struct {
0151   size_t count;       /* Number of entries in the hash part. */
0152   uint32_t mask;      /* Mask to turn hash value -> bucket. */
0153   uint32_t max_count; /* Max count before we hit our load limit. */
0154   uint8_t size_lg2;   /* Size of the hashtable part is 2^size_lg2 entries. */
0155   upb_tabent* entries;
0156 } upb_table;
0157
0158 UPB_INLINE size_t upb_table_size(const upb_table* t) {
0159   return t->size_lg2 ? 1 << t->size_lg2 : 0;
0160 }
0161
0162 // Internal-only functions, in .h file only out of necessity.
0163
0164 UPB_INLINE bool upb_tabent_isempty(const upb_tabent* e) { return e->key == 0; }
0165
0166 uint32_t _upb_Hash(const void* p, size_t n, uint64_t seed);
0167
0168 #ifdef __cplusplus
0169 } /* extern "C" */
0170 #endif
0171
0172 #include "upb/port/undef.inc"
0173
0174 #endif /* UPB_HASH_COMMON_H_ */