1 // Protocol Buffers - Google's data interchange format
2 // Copyright 2023 Google LLC. All rights reserved.
3 //
4 // Use of this source code is governed by a BSD-style
5 // license that can be found in the LICENSE file or at
6 // https://developers.google.com/open-source/licenses/bsd
7
8 /*
9 * upb_table
10 *
11 * This header is INTERNAL-ONLY! Its interfaces are not public or stable!
12 * This file defines very fast int->upb_value (inttable) and string->upb_value
13 * (strtable) hash tables.
14 *
15 * The table uses chained scatter with Brent's variation (inspired by the Lua
16 * implementation of hash tables). The hash function for strings is Austin
17 * Appleby's "MurmurHash."
18 *
19 * The inttable uses uintptr_t as its key, which guarantees it can be used to
20 * store pointers or integers of at least 32 bits (upb isn't really useful on
21 * systems where sizeof(void*) < 4).
22 *
23 * The table must be homogeneous (all values of the same type). In debug
24 * mode, we check this on insert and lookup.
25 */
26
27 #ifndef UPB_HASH_COMMON_H_
28 #define UPB_HASH_COMMON_H_
29
30 #include <string.h>
31
32 #include "upb/base/string_view.h"
33 #include "upb/mem/arena.h"
34
35 // Must be last.
36 #include "upb/port/def.inc"
37
38 #ifdef __cplusplus
39 extern "C" {
40 #endif
41
42 /* upb_value ******************************************************************/
43
44 typedef struct {
45 uint64_t val;
46 } upb_value;
47
_upb_value_setval(upb_value * v,uint64_t val)48 UPB_INLINE void _upb_value_setval(upb_value* v, uint64_t val) { v->val = val; }
49
50 /* For each value ctype, define the following set of functions:
51 *
52 * // Get/set an int32 from a upb_value.
53 * int32_t upb_value_getint32(upb_value val);
54 * void upb_value_setint32(upb_value *val, int32_t cval);
55 *
56 * // Construct a new upb_value from an int32.
57 * upb_value upb_value_int32(int32_t val); */
58 #define FUNCS(name, membername, type_t, converter) \
59 UPB_INLINE void upb_value_set##name(upb_value* val, type_t cval) { \
60 val->val = (converter)cval; \
61 } \
62 UPB_INLINE upb_value upb_value_##name(type_t val) { \
63 upb_value ret; \
64 upb_value_set##name(&ret, val); \
65 return ret; \
66 } \
67 UPB_INLINE type_t upb_value_get##name(upb_value val) { \
68 return (type_t)(converter)val.val; \
69 }
70
FUNCS(int32,int32,int32_t,int32_t)71 FUNCS(int32, int32, int32_t, int32_t)
72 FUNCS(int64, int64, int64_t, int64_t)
73 FUNCS(uint32, uint32, uint32_t, uint32_t)
74 FUNCS(uint64, uint64, uint64_t, uint64_t)
75 FUNCS(bool, _bool, bool, bool)
76 FUNCS(cstr, cstr, char*, uintptr_t)
77 FUNCS(uintptr, uptr, uintptr_t, uintptr_t)
78 FUNCS(ptr, ptr, void*, uintptr_t)
79 FUNCS(constptr, constptr, const void*, uintptr_t)
80
81 #undef FUNCS
82
83 UPB_INLINE void upb_value_setfloat(upb_value* val, float cval) {
84 memcpy(&val->val, &cval, sizeof(cval));
85 }
86
upb_value_setdouble(upb_value * val,double cval)87 UPB_INLINE void upb_value_setdouble(upb_value* val, double cval) {
88 memcpy(&val->val, &cval, sizeof(cval));
89 }
90
upb_value_float(float cval)91 UPB_INLINE upb_value upb_value_float(float cval) {
92 upb_value ret;
93 upb_value_setfloat(&ret, cval);
94 return ret;
95 }
96
upb_value_double(double cval)97 UPB_INLINE upb_value upb_value_double(double cval) {
98 upb_value ret;
99 upb_value_setdouble(&ret, cval);
100 return ret;
101 }
102
103 /* upb_tabkey *****************************************************************/
104
105 /* Either:
106 * 1. an actual integer key, or
107 * 2. a pointer to a string prefixed by its uint32_t length, owned by us.
108 *
109 * ...depending on whether this is a string table or an int table. We would
110 * make this a union of those two types, but C89 doesn't support statically
111 * initializing a non-first union member. */
112 typedef uintptr_t upb_tabkey;
113
upb_tabstr(upb_tabkey key,uint32_t * len)114 UPB_INLINE char* upb_tabstr(upb_tabkey key, uint32_t* len) {
115 char* mem = (char*)key;
116 if (len) memcpy(len, mem, sizeof(*len));
117 return mem + sizeof(*len);
118 }
119
upb_tabstrview(upb_tabkey key)120 UPB_INLINE upb_StringView upb_tabstrview(upb_tabkey key) {
121 upb_StringView ret;
122 uint32_t len;
123 ret.data = upb_tabstr(key, &len);
124 ret.size = len;
125 return ret;
126 }
127
128 /* upb_tabval *****************************************************************/
129
130 typedef struct upb_tabval {
131 uint64_t val;
132 } upb_tabval;
133
134 #define UPB_TABVALUE_EMPTY_INIT \
135 { -1 }
136
137 /* upb_table ******************************************************************/
138
139 typedef struct _upb_tabent {
140 upb_tabkey key;
141 upb_tabval val;
142
143 /* Internal chaining. This is const so we can create static initializers for
144 * tables. We cast away const sometimes, but *only* when the containing
145 * upb_table is known to be non-const. This requires a bit of care, but
146 * the subtlety is confined to table.c. */
147 const struct _upb_tabent* next;
148 } upb_tabent;
149
150 typedef struct {
151 size_t count; /* Number of entries in the hash part. */
152 uint32_t mask; /* Mask to turn hash value -> bucket. */
153 uint32_t max_count; /* Max count before we hit our load limit. */
154 uint8_t size_lg2; /* Size of the hashtable part is 2^size_lg2 entries. */
155 upb_tabent* entries;
156 } upb_table;
157
upb_table_size(const upb_table * t)158 UPB_INLINE size_t upb_table_size(const upb_table* t) {
159 return t->size_lg2 ? 1 << t->size_lg2 : 0;
160 }
161
162 // Internal-only functions, in .h file only out of necessity.
163
upb_tabent_isempty(const upb_tabent * e)164 UPB_INLINE bool upb_tabent_isempty(const upb_tabent* e) { return e->key == 0; }
165
166 uint32_t _upb_Hash(const void* p, size_t n, uint64_t seed);
167
168 #ifdef __cplusplus
169 } /* extern "C" */
170 #endif
171
172 #include "upb/port/undef.inc"
173
174 #endif /* UPB_HASH_COMMON_H_ */
175