third_party/upb/upb/table_internal.h

   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" AND
  17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19  * DISCLAIMED. IN NO EVENT SHALL Google LLC BE LIABLE FOR ANY
  20  * DIRECT, 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_TABLE_H_
  48 #define UPB_TABLE_H_
  49
  50 #include <stdint.h>
  51 #include <string.h>
  52 #include "upb/upb.h"
  53
  54 #include "upb/port_def.inc"
  55
  56 #ifdef __cplusplus
  57 extern "C" {
  58 #endif
  59
  60
  61 /* upb_value ******************************************************************/
  62
  63 typedef struct {
  64   uint64_t val;
  65 } upb_value;
  66
  67 /* Variant that works with a length-delimited rather than NULL-delimited string,
  68  * as supported by strtable. */
  69 char *upb_strdup2(const char *s, size_t len, upb_arena *a);
  70
  71 UPB_INLINE void _upb_value_setval(upb_value *v, uint64_t val) {
  72   v->val = val;
  73 }
  74
  75 /* For each value ctype, define the following set of functions:
  76  *
  77  * // Get/set an int32 from a upb_value.
  78  * int32_t upb_value_getint32(upb_value val);
  79  * void upb_value_setint32(upb_value *val, int32_t cval);
  80  *
  81  * // Construct a new upb_value from an int32.
  82  * upb_value upb_value_int32(int32_t val); */
  83 #define FUNCS(name, membername, type_t, converter, proto_type) \
  84   UPB_INLINE void upb_value_set ## name(upb_value *val, type_t cval) { \
  85     val->val = (converter)cval; \
  86   } \
  87   UPB_INLINE upb_value upb_value_ ## name(type_t val) { \
  88     upb_value ret; \
  89     upb_value_set ## name(&ret, val); \
  90     return ret; \
  91   } \
  92   UPB_INLINE type_t upb_value_get ## name(upb_value val) { \
  93     return (type_t)(converter)val.val; \
  94   }
  95
  96 FUNCS(int32,    int32,        int32_t,      int32_t,    UPB_CTYPE_INT32)
  97 FUNCS(int64,    int64,        int64_t,      int64_t,    UPB_CTYPE_INT64)
  98 FUNCS(uint32,   uint32,       uint32_t,     uint32_t,   UPB_CTYPE_UINT32)
  99 FUNCS(uint64,   uint64,       uint64_t,     uint64_t,   UPB_CTYPE_UINT64)
 100 FUNCS(bool,     _bool,        bool,         bool,       UPB_CTYPE_BOOL)
 101 FUNCS(cstr,     cstr,         char*,        uintptr_t,  UPB_CTYPE_CSTR)
 102 FUNCS(ptr,      ptr,          void*,        uintptr_t,  UPB_CTYPE_PTR)
 103 FUNCS(constptr, constptr,     const void*,  uintptr_t,  UPB_CTYPE_CONSTPTR)
 104 FUNCS(fptr,     fptr,         upb_func*,    uintptr_t,  UPB_CTYPE_FPTR)
 105
 106 #undef FUNCS
 107
 108 UPB_INLINE void upb_value_setfloat(upb_value *val, float cval) {
 109   memcpy(&val->val, &cval, sizeof(cval));
 110 }
 111
 112 UPB_INLINE void upb_value_setdouble(upb_value *val, double cval) {
 113   memcpy(&val->val, &cval, sizeof(cval));
 114 }
 115
 116 UPB_INLINE upb_value upb_value_float(float cval) {
 117   upb_value ret;
 118   upb_value_setfloat(&ret, cval);
 119   return ret;
 120 }
 121
 122 UPB_INLINE upb_value upb_value_double(double cval) {
 123   upb_value ret;
 124   upb_value_setdouble(&ret, cval);
 125   return ret;
 126 }
 127
 128 #undef SET_TYPE
 129
 130
 131 /* upb_tabkey *****************************************************************/
 132
 133 /* Either:
 134  *   1. an actual integer key, or
 135  *   2. a pointer to a string prefixed by its uint32_t length, owned by us.
 136  *
 137  * ...depending on whether this is a string table or an int table.  We would
 138  * make this a union of those two types, but C89 doesn't support statically
 139  * initializing a non-first union member. */
 140 typedef uintptr_t upb_tabkey;
 141
 142 UPB_INLINE char *upb_tabstr(upb_tabkey key, uint32_t *len) {
 143   char* mem = (char*)key;
 144   if (len) memcpy(len, mem, sizeof(*len));
 145   return mem + sizeof(*len);
 146 }
 147
 148 UPB_INLINE upb_strview upb_tabstrview(upb_tabkey key) {
 149   upb_strview ret;
 150   uint32_t len;
 151   ret.data = upb_tabstr(key, &len);
 152   ret.size = len;
 153   return ret;
 154 }
 155
 156 /* upb_tabval *****************************************************************/
 157
 158 typedef struct upb_tabval {
 159   uint64_t val;
 160 } upb_tabval;
 161
 162 #define UPB_TABVALUE_EMPTY_INIT  {-1}
 163
 164 /* upb_table ******************************************************************/
 165
 166 typedef struct _upb_tabent {
 167   upb_tabkey key;
 168   upb_tabval val;
 169
 170   /* Internal chaining.  This is const so we can create static initializers for
 171    * tables.  We cast away const sometimes, but *only* when the containing
 172    * upb_table is known to be non-const.  This requires a bit of care, but
 173    * the subtlety is confined to table.c. */
 174   const struct _upb_tabent *next;
 175 } upb_tabent;
 176
 177 typedef struct {
 178   size_t count;          /* Number of entries in the hash part. */
 179   uint32_t mask;         /* Mask to turn hash value -> bucket. */
 180   uint32_t max_count;    /* Max count before we hit our load limit. */
 181   uint8_t size_lg2;      /* Size of the hashtable part is 2^size_lg2 entries. */
 182   upb_tabent *entries;
 183 } upb_table;
 184
 185 typedef struct {
 186   upb_table t;
 187 } upb_strtable;
 188
 189 typedef struct {
 190   upb_table t;              /* For entries that don't fit in the array part. */
 191   const upb_tabval *array;  /* Array part of the table. See const note above. */
 192   size_t array_size;        /* Array part size. */
 193   size_t array_count;       /* Array part number of elements. */
 194 } upb_inttable;
 195
 196 UPB_INLINE size_t upb_table_size(const upb_table *t) {
 197   if (t->size_lg2 == 0)
 198     return 0;
 199   else
 200     return 1 << t->size_lg2;
 201 }
 202
 203 /* Internal-only functions, in .h file only out of necessity. */
 204 UPB_INLINE bool upb_tabent_isempty(const upb_tabent *e) {
 205   return e->key == 0;
 206 }
 207
 208 /* Initialize and uninitialize a table, respectively.  If memory allocation
 209  * failed, false is returned that the table is uninitialized. */
 210 bool upb_inttable_init(upb_inttable *table, upb_arena *a);
 211 bool upb_strtable_init(upb_strtable *table, size_t expected_size, upb_arena *a);
 212
 213 /* Returns the number of values in the table. */
 214 size_t upb_inttable_count(const upb_inttable *t);
 215 UPB_INLINE size_t upb_strtable_count(const upb_strtable *t) {
 216   return t->t.count;
 217 }
 218
 219 void upb_strtable_clear(upb_strtable *t);
 220
 221 /* Inserts the given key into the hashtable with the given value.  The key must
 222  * not already exist in the hash table.  For string tables, the key must be
 223  * NULL-terminated, and the table will make an internal copy of the key.
 224  * Inttables must not insert a value of UINTPTR_MAX.
 225  *
 226  * If a table resize was required but memory allocation failed, false is
 227  * returned and the table is unchanged. */
 228 bool upb_inttable_insert(upb_inttable *t, uintptr_t key, upb_value val,
 229                          upb_arena *a);
 230 bool upb_strtable_insert(upb_strtable *t, const char *key, size_t len,
 231                          upb_value val, upb_arena *a);
 232
 233 /* Looks up key in this table, returning "true" if the key was found.
 234  * If v is non-NULL, copies the value for this key into *v. */
 235 bool upb_inttable_lookup(const upb_inttable *t, uintptr_t key, upb_value *v);
 236 bool upb_strtable_lookup2(const upb_strtable *t, const char *key, size_t len,
 237                           upb_value *v);
 238
 239 /* For NULL-terminated strings. */
 240 UPB_INLINE bool upb_strtable_lookup(const upb_strtable *t, const char *key,
 241                                     upb_value *v) {
 242   return upb_strtable_lookup2(t, key, strlen(key), v);
 243 }
 244
 245 /* Removes an item from the table.  Returns true if the remove was successful,
 246  * and stores the removed item in *val if non-NULL. */
 247 bool upb_inttable_remove(upb_inttable *t, uintptr_t key, upb_value *val);
 248 bool upb_strtable_remove(upb_strtable *t, const char *key, size_t len,
 249                           upb_value *val);
 250
 251 /* Updates an existing entry in an inttable.  If the entry does not exist,
 252  * returns false and does nothing.  Unlike insert/remove, this does not
 253  * invalidate iterators. */
 254 bool upb_inttable_replace(upb_inttable *t, uintptr_t key, upb_value val);
 255
 256 /* Optimizes the table for the current set of entries, for both memory use and
 257  * lookup time.  Client should call this after all entries have been inserted;
 258  * inserting more entries is legal, but will likely require a table resize. */
 259 void upb_inttable_compact(upb_inttable *t, upb_arena *a);
 260
 261 /* Exposed for testing only. */
 262 bool upb_strtable_resize(upb_strtable *t, size_t size_lg2, upb_arena *a);
 263
 264 /* Iterators ******************************************************************/
 265
 266 /* Iterators for int and string tables.  We are subject to some kind of unusual
 267  * design constraints:
 268  *
 269  * For high-level languages:
 270  *  - we must be able to guarantee that we don't crash or corrupt memory even if
 271  *    the program accesses an invalidated iterator.
 272  *
 273  * For C++11 range-based for:
 274  *  - iterators must be copyable
 275  *  - iterators must be comparable
 276  *  - it must be possible to construct an "end" value.
 277  *
 278  * Iteration order is undefined.
 279  *
 280  * Modifying the table invalidates iterators.  upb_{str,int}table_done() is
 281  * guaranteed to work even on an invalidated iterator, as long as the table it
 282  * is iterating over has not been freed.  Calling next() or accessing data from
 283  * an invalidated iterator yields unspecified elements from the table, but it is
 284  * guaranteed not to crash and to return real table elements (except when done()
 285  * is true). */
 286
 287
 288 /* upb_strtable_iter **********************************************************/
 289
 290 /*   upb_strtable_iter i;
 291  *   upb_strtable_begin(&i, t);
 292  *   for(; !upb_strtable_done(&i); upb_strtable_next(&i)) {
 293  *     const char *key = upb_strtable_iter_key(&i);
 294  *     const upb_value val = upb_strtable_iter_value(&i);
 295  *     // ...
 296  *   }
 297  */
 298
 299 typedef struct {
 300   const upb_strtable *t;
 301   size_t index;
 302 } upb_strtable_iter;
 303
 304 void upb_strtable_begin(upb_strtable_iter *i, const upb_strtable *t);
 305 void upb_strtable_next(upb_strtable_iter *i);
 306 bool upb_strtable_done(const upb_strtable_iter *i);
 307 upb_strview upb_strtable_iter_key(const upb_strtable_iter *i);
 308 upb_value upb_strtable_iter_value(const upb_strtable_iter *i);
 309 void upb_strtable_iter_setdone(upb_strtable_iter *i);
 310 bool upb_strtable_iter_isequal(const upb_strtable_iter *i1,
 311                                const upb_strtable_iter *i2);
 312
 313
 314 /* upb_inttable_iter **********************************************************/
 315
 316 /*   upb_inttable_iter i;
 317  *   upb_inttable_begin(&i, t);
 318  *   for(; !upb_inttable_done(&i); upb_inttable_next(&i)) {
 319  *     uintptr_t key = upb_inttable_iter_key(&i);
 320  *     upb_value val = upb_inttable_iter_value(&i);
 321  *     // ...
 322  *   }
 323  */
 324
 325 typedef struct {
 326   const upb_inttable *t;
 327   size_t index;
 328   bool array_part;
 329 } upb_inttable_iter;
 330
 331 UPB_INLINE const upb_tabent *str_tabent(const upb_strtable_iter *i) {
 332   return &i->t->t.entries[i->index];
 333 }
 334
 335 void upb_inttable_begin(upb_inttable_iter *i, const upb_inttable *t);
 336 void upb_inttable_next(upb_inttable_iter *i);
 337 bool upb_inttable_done(const upb_inttable_iter *i);
 338 uintptr_t upb_inttable_iter_key(const upb_inttable_iter *i);
 339 upb_value upb_inttable_iter_value(const upb_inttable_iter *i);
 340 void upb_inttable_iter_setdone(upb_inttable_iter *i);
 341 bool upb_inttable_iter_isequal(const upb_inttable_iter *i1,
 342                                const upb_inttable_iter *i2);
 343
 344
 345 #ifdef __cplusplus
 346 }  /* extern "C" */
 347 #endif
 348
 349 #include "upb/port_undef.inc"
 350
 351 #endif  /* UPB_TABLE_H_ */