1 /*
2 * Copyright (c) 2009-2021, Google LLC
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 * * Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of Google LLC nor the
13 * names of its contributors may be used to endorse or promote products
14 * derived from this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL Google LLC BE LIABLE FOR ANY DIRECT,
20 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28 /*
29 * upb_table
30 *
31 * This header is INTERNAL-ONLY! Its interfaces are not public or stable!
32 * This file defines very fast int->upb_value (inttable) and string->upb_value
33 * (strtable) hash tables.
34 *
35 * The table uses chained scatter with Brent's variation (inspired by the Lua
36 * implementation of hash tables). The hash function for strings is Austin
37 * Appleby's "MurmurHash."
38 *
39 * The inttable uses uintptr_t as its key, which guarantees it can be used to
40 * store pointers or integers of at least 32 bits (upb isn't really useful on
41 * systems where sizeof(void*) < 4).
42 *
43 * The table must be homogeneous (all values of the same type). In debug
44 * mode, we check this on insert and lookup.
45 */
46
47 #ifndef UPB_HASH_COMMON_H_
48 #define UPB_HASH_COMMON_H_
49
50 #include <string.h>
51
52 #include "upb/base/string_view.h"
53 #include "upb/mem/arena.h"
54
55 // Must be last.
56 #include "upb/port/def.inc"
57
58 #ifdef __cplusplus
59 extern "C" {
60 #endif
61
62 /* upb_value ******************************************************************/
63
64 typedef struct {
65 uint64_t val;
66 } upb_value;
67
68 /* Variant that works with a length-delimited rather than NULL-delimited string,
69 * as supported by strtable. */
70 char* upb_strdup2(const char* s, size_t len, upb_Arena* a);
71
_upb_value_setval(upb_value * v,uint64_t val)72 UPB_INLINE void _upb_value_setval(upb_value* v, uint64_t val) { v->val = val; }
73
74 /* For each value ctype, define the following set of functions:
75 *
76 * // Get/set an int32 from a upb_value.
77 * int32_t upb_value_getint32(upb_value val);
78 * void upb_value_setint32(upb_value *val, int32_t cval);
79 *
80 * // Construct a new upb_value from an int32.
81 * upb_value upb_value_int32(int32_t val); */
82 #define FUNCS(name, membername, type_t, converter, proto_type) \
83 UPB_INLINE void upb_value_set##name(upb_value* val, type_t cval) { \
84 val->val = (converter)cval; \
85 } \
86 UPB_INLINE upb_value upb_value_##name(type_t val) { \
87 upb_value ret; \
88 upb_value_set##name(&ret, val); \
89 return ret; \
90 } \
91 UPB_INLINE type_t upb_value_get##name(upb_value val) { \
92 return (type_t)(converter)val.val; \
93 }
94
FUNCS(int32,int32,int32_t,int32_t,UPB_CTYPE_INT32)95 FUNCS(int32, int32, int32_t, int32_t, UPB_CTYPE_INT32)
96 FUNCS(int64, int64, int64_t, int64_t, UPB_CTYPE_INT64)
97 FUNCS(uint32, uint32, uint32_t, uint32_t, UPB_CTYPE_UINT32)
98 FUNCS(uint64, uint64, uint64_t, uint64_t, UPB_CTYPE_UINT64)
99 FUNCS(bool, _bool, bool, bool, UPB_CTYPE_BOOL)
100 FUNCS(cstr, cstr, char*, uintptr_t, UPB_CTYPE_CSTR)
101 FUNCS(ptr, ptr, void*, uintptr_t, UPB_CTYPE_PTR)
102 FUNCS(constptr, constptr, const void*, uintptr_t, UPB_CTYPE_CONSTPTR)
103
104 #undef FUNCS
105
106 UPB_INLINE void upb_value_setfloat(upb_value* val, float cval) {
107 memcpy(&val->val, &cval, sizeof(cval));
108 }
109
upb_value_setdouble(upb_value * val,double cval)110 UPB_INLINE void upb_value_setdouble(upb_value* val, double cval) {
111 memcpy(&val->val, &cval, sizeof(cval));
112 }
113
upb_value_float(float cval)114 UPB_INLINE upb_value upb_value_float(float cval) {
115 upb_value ret;
116 upb_value_setfloat(&ret, cval);
117 return ret;
118 }
119
upb_value_double(double cval)120 UPB_INLINE upb_value upb_value_double(double cval) {
121 upb_value ret;
122 upb_value_setdouble(&ret, cval);
123 return ret;
124 }
125
126 #undef SET_TYPE
127
128 /* upb_tabkey *****************************************************************/
129
130 /* Either:
131 * 1. an actual integer key, or
132 * 2. a pointer to a string prefixed by its uint32_t length, owned by us.
133 *
134 * ...depending on whether this is a string table or an int table. We would
135 * make this a union of those two types, but C89 doesn't support statically
136 * initializing a non-first union member. */
137 typedef uintptr_t upb_tabkey;
138
upb_tabstr(upb_tabkey key,uint32_t * len)139 UPB_INLINE char* upb_tabstr(upb_tabkey key, uint32_t* len) {
140 char* mem = (char*)key;
141 if (len) memcpy(len, mem, sizeof(*len));
142 return mem + sizeof(*len);
143 }
144
upb_tabstrview(upb_tabkey key)145 UPB_INLINE upb_StringView upb_tabstrview(upb_tabkey key) {
146 upb_StringView ret;
147 uint32_t len;
148 ret.data = upb_tabstr(key, &len);
149 ret.size = len;
150 return ret;
151 }
152
153 /* upb_tabval *****************************************************************/
154
155 typedef struct upb_tabval {
156 uint64_t val;
157 } upb_tabval;
158
159 #define UPB_TABVALUE_EMPTY_INIT \
160 { -1 }
161
162 /* upb_table ******************************************************************/
163
164 typedef struct _upb_tabent {
165 upb_tabkey key;
166 upb_tabval val;
167
168 /* Internal chaining. This is const so we can create static initializers for
169 * tables. We cast away const sometimes, but *only* when the containing
170 * upb_table is known to be non-const. This requires a bit of care, but
171 * the subtlety is confined to table.c. */
172 const struct _upb_tabent* next;
173 } upb_tabent;
174
175 typedef struct {
176 size_t count; /* Number of entries in the hash part. */
177 uint32_t mask; /* Mask to turn hash value -> bucket. */
178 uint32_t max_count; /* Max count before we hit our load limit. */
179 uint8_t size_lg2; /* Size of the hashtable part is 2^size_lg2 entries. */
180 upb_tabent* entries;
181 } upb_table;
182
upb_table_size(const upb_table * t)183 UPB_INLINE size_t upb_table_size(const upb_table* t) {
184 return t->size_lg2 ? 1 << t->size_lg2 : 0;
185 }
186
187 // Internal-only functions, in .h file only out of necessity.
188
upb_tabent_isempty(const upb_tabent * e)189 UPB_INLINE bool upb_tabent_isempty(const upb_tabent* e) { return e->key == 0; }
190
191 uint32_t _upb_Hash(const void* p, size_t n, uint64_t seed);
192
193 #ifdef __cplusplus
194 } /* extern "C" */
195 #endif
196
197 #include "upb/port/undef.inc"
198
199 #endif /* UPB_HASH_COMMON_H_ */
200