legacy-libs/grpc-cloned/deps/grpc/third_party/upb/upb/table.int.h

   1 /*
   2 ** upb_table
   3 **
   4 ** This header is INTERNAL-ONLY!  Its interfaces are not public or stable!
   5 ** This file defines very fast int->upb_value (inttable) and string->upb_value
   6 ** (strtable) hash tables.
   7 **
   8 ** The table uses chained scatter with Brent's variation (inspired by the Lua
   9 ** implementation of hash tables).  The hash function for strings is Austin
  10 ** Appleby's "MurmurHash."
  11 **
  12 ** The inttable uses uintptr_t as its key, which guarantees it can be used to
  13 ** store pointers or integers of at least 32 bits (upb isn't really useful on
  14 ** systems where sizeof(void*) < 4).
  15 **
  16 ** The table must be homogenous (all values of the same type).  In debug
  17 ** mode, we check this on insert and lookup.
  18 */
  19
  20 #ifndef UPB_TABLE_H_
  21 #define UPB_TABLE_H_
  22
  23 #include <stdint.h>
  24 #include <string.h>
  25 #include "upb/upb.h"
  26
  27 #include "upb/port_def.inc"
  28
  29 #ifdef __cplusplus
  30 extern "C" {
  31 #endif
  32
  33
  34 /* upb_value ******************************************************************/
  35
  36 /* A tagged union (stored untagged inside the table) so that we can check that
  37  * clients calling table accessors are correctly typed without having to have
  38  * an explosion of accessors. */
  39 typedef enum {
  40   UPB_CTYPE_INT32    = 1,
  41   UPB_CTYPE_INT64    = 2,
  42   UPB_CTYPE_UINT32   = 3,
  43   UPB_CTYPE_UINT64   = 4,
  44   UPB_CTYPE_BOOL     = 5,
  45   UPB_CTYPE_CSTR     = 6,
  46   UPB_CTYPE_PTR      = 7,
  47   UPB_CTYPE_CONSTPTR = 8,
  48   UPB_CTYPE_FPTR     = 9,
  49   UPB_CTYPE_FLOAT    = 10,
  50   UPB_CTYPE_DOUBLE   = 11
  51 } upb_ctype_t;
  52
  53 typedef struct {
  54   uint64_t val;
  55 #ifndef NDEBUG
  56   /* In debug mode we carry the value type around also so we can check accesses
  57    * to be sure the right member is being read. */
  58   upb_ctype_t ctype;
  59 #endif
  60 } upb_value;
  61
  62 #ifdef NDEBUG
  63 #define SET_TYPE(dest, val)      UPB_UNUSED(val)
  64 #else
  65 #define SET_TYPE(dest, val) dest = val
  66 #endif
  67
  68 /* Like strdup(), which isn't always available since it's not ANSI C. */
  69 char *upb_strdup(const char *s, upb_alloc *a);
  70 /* Variant that works with a length-delimited rather than NULL-delimited string,
  71  * as supported by strtable. */
  72 char *upb_strdup2(const char *s, size_t len, upb_alloc *a);
  73
  74 UPB_INLINE char *upb_gstrdup(const char *s) {
  75   return upb_strdup(s, &upb_alloc_global);
  76 }
  77
  78 UPB_INLINE void _upb_value_setval(upb_value *v, uint64_t val,
  79                                   upb_ctype_t ctype) {
  80   v->val = val;
  81   SET_TYPE(v->ctype, ctype);
  82 }
  83
  84 UPB_INLINE upb_value _upb_value_val(uint64_t val, upb_ctype_t ctype) {
  85   upb_value ret;
  86   _upb_value_setval(&ret, val, ctype);
  87   return ret;
  88 }
  89
  90 /* For each value ctype, define the following set of functions:
  91  *
  92  * // Get/set an int32 from a upb_value.
  93  * int32_t upb_value_getint32(upb_value val);
  94  * void upb_value_setint32(upb_value *val, int32_t cval);
  95  *
  96  * // Construct a new upb_value from an int32.
  97  * upb_value upb_value_int32(int32_t val); */
  98 #define FUNCS(name, membername, type_t, converter, proto_type) \
  99   UPB_INLINE void upb_value_set ## name(upb_value *val, type_t cval) { \
 100     val->val = (converter)cval; \
 101     SET_TYPE(val->ctype, proto_type); \
 102   } \
 103   UPB_INLINE upb_value upb_value_ ## name(type_t val) { \
 104     upb_value ret; \
 105     upb_value_set ## name(&ret, val); \
 106     return ret; \
 107   } \
 108   UPB_INLINE type_t upb_value_get ## name(upb_value val) { \
 109     UPB_ASSERT_DEBUGVAR(val.ctype == proto_type); \
 110     return (type_t)(converter)val.val; \
 111   }
 112
 113 FUNCS(int32,    int32,        int32_t,      int32_t,    UPB_CTYPE_INT32)
 114 FUNCS(int64,    int64,        int64_t,      int64_t,    UPB_CTYPE_INT64)
 115 FUNCS(uint32,   uint32,       uint32_t,     uint32_t,   UPB_CTYPE_UINT32)
 116 FUNCS(uint64,   uint64,       uint64_t,     uint64_t,   UPB_CTYPE_UINT64)
 117 FUNCS(bool,     _bool,        bool,         bool,       UPB_CTYPE_BOOL)
 118 FUNCS(cstr,     cstr,         char*,        uintptr_t,  UPB_CTYPE_CSTR)
 119 FUNCS(ptr,      ptr,          void*,        uintptr_t,  UPB_CTYPE_PTR)
 120 FUNCS(constptr, constptr,     const void*,  uintptr_t,  UPB_CTYPE_CONSTPTR)
 121 FUNCS(fptr,     fptr,         upb_func*,    uintptr_t,  UPB_CTYPE_FPTR)
 122
 123 #undef FUNCS
 124
 125 UPB_INLINE void upb_value_setfloat(upb_value *val, float cval) {
 126   memcpy(&val->val, &cval, sizeof(cval));
 127   SET_TYPE(val->ctype, UPB_CTYPE_FLOAT);
 128 }
 129
 130 UPB_INLINE void upb_value_setdouble(upb_value *val, double cval) {
 131   memcpy(&val->val, &cval, sizeof(cval));
 132   SET_TYPE(val->ctype, UPB_CTYPE_DOUBLE);
 133 }
 134
 135 UPB_INLINE upb_value upb_value_float(float cval) {
 136   upb_value ret;
 137   upb_value_setfloat(&ret, cval);
 138   return ret;
 139 }
 140
 141 UPB_INLINE upb_value upb_value_double(double cval) {
 142   upb_value ret;
 143   upb_value_setdouble(&ret, cval);
 144   return ret;
 145 }
 146
 147 #undef SET_TYPE
 148
 149
 150 /* upb_tabkey *****************************************************************/
 151
 152 /* Either:
 153  *   1. an actual integer key, or
 154  *   2. a pointer to a string prefixed by its uint32_t length, owned by us.
 155  *
 156  * ...depending on whether this is a string table or an int table.  We would
 157  * make this a union of those two types, but C89 doesn't support statically
 158  * initializing a non-first union member. */
 159 typedef uintptr_t upb_tabkey;
 160
 161 UPB_INLINE char *upb_tabstr(upb_tabkey key, uint32_t *len) {
 162   char* mem = (char*)key;
 163   if (len) memcpy(len, mem, sizeof(*len));
 164   return mem + sizeof(*len);
 165 }
 166
 167
 168 /* upb_tabval *****************************************************************/
 169
 170 typedef struct {
 171   uint64_t val;
 172 } upb_tabval;
 173
 174 #define UPB_TABVALUE_EMPTY_INIT  {-1}
 175
 176
 177 /* upb_table ******************************************************************/
 178
 179 typedef struct _upb_tabent {
 180   upb_tabkey key;
 181   upb_tabval val;
 182
 183   /* Internal chaining.  This is const so we can create static initializers for
 184    * tables.  We cast away const sometimes, but *only* when the containing
 185    * upb_table is known to be non-const.  This requires a bit of care, but
 186    * the subtlety is confined to table.c. */
 187   const struct _upb_tabent *next;
 188 } upb_tabent;
 189
 190 typedef struct {
 191   size_t count;          /* Number of entries in the hash part. */
 192   size_t mask;           /* Mask to turn hash value -> bucket. */
 193   upb_ctype_t ctype;     /* Type of all values. */
 194   uint8_t size_lg2;      /* Size of the hashtable part is 2^size_lg2 entries. */
 195
 196   /* Hash table entries.
 197    * Making this const isn't entirely accurate; what we really want is for it to
 198    * have the same const-ness as the table it's inside.  But there's no way to
 199    * declare that in C.  So we have to make it const so that we can statically
 200    * initialize const hash tables.  Then we cast away const when we have to.
 201    */
 202   const upb_tabent *entries;
 203
 204 #ifndef NDEBUG
 205   /* This table's allocator.  We make the user pass it in to every relevant
 206    * function and only use this to check it in debug mode.  We do this solely
 207    * to keep upb_table as small as possible.  This might seem slightly paranoid
 208    * but the plan is to use upb_table for all map fields and extension sets in
 209    * a forthcoming message representation, so there could be a lot of these.
 210    * If this turns out to be too annoying later, we can change it (since this
 211    * is an internal-only header file). */
 212   upb_alloc *alloc;
 213 #endif
 214 } upb_table;
 215
 216 typedef struct {
 217   upb_table t;
 218 } upb_strtable;
 219
 220 typedef struct {
 221   upb_table t;              /* For entries that don't fit in the array part. */
 222   const upb_tabval *array;  /* Array part of the table. See const note above. */
 223   size_t array_size;        /* Array part size. */
 224   size_t array_count;       /* Array part number of elements. */
 225 } upb_inttable;
 226
 227 #define UPB_INTTABLE_INIT(count, mask, ctype, size_lg2, ent, a, asize, acount) \
 228   {UPB_TABLE_INIT(count, mask, ctype, size_lg2, ent), a, asize, acount}
 229
 230 #define UPB_EMPTY_INTTABLE_INIT(ctype) \
 231   UPB_INTTABLE_INIT(0, 0, ctype, 0, NULL, NULL, 0, 0)
 232
 233 #define UPB_ARRAY_EMPTYENT -1
 234
 235 UPB_INLINE size_t upb_table_size(const upb_table *t) {
 236   if (t->size_lg2 == 0)
 237     return 0;
 238   else
 239     return 1 << t->size_lg2;
 240 }
 241
 242 /* Internal-only functions, in .h file only out of necessity. */
 243 UPB_INLINE bool upb_tabent_isempty(const upb_tabent *e) {
 244   return e->key == 0;
 245 }
 246
 247 /* Used by some of the unit tests for generic hashing functionality. */
 248 uint32_t upb_murmur_hash2(const void * key, size_t len, uint32_t seed);
 249
 250 UPB_INLINE uintptr_t upb_intkey(uintptr_t key) {
 251   return key;
 252 }
 253
 254 UPB_INLINE uint32_t upb_inthash(uintptr_t key) {
 255   return (uint32_t)key;
 256 }
 257
 258 static const upb_tabent *upb_getentry(const upb_table *t, uint32_t hash) {
 259   return t->entries + (hash & t->mask);
 260 }
 261
 262 UPB_INLINE bool upb_arrhas(upb_tabval key) {
 263   return key.val != (uint64_t)-1;
 264 }
 265
 266 /* Initialize and uninitialize a table, respectively.  If memory allocation
 267  * failed, false is returned that the table is uninitialized. */
 268 bool upb_inttable_init2(upb_inttable *table, upb_ctype_t ctype, upb_alloc *a);
 269 bool upb_strtable_init2(upb_strtable *table, upb_ctype_t ctype, upb_alloc *a);
 270 void upb_inttable_uninit2(upb_inttable *table, upb_alloc *a);
 271 void upb_strtable_uninit2(upb_strtable *table, upb_alloc *a);
 272
 273 UPB_INLINE bool upb_inttable_init(upb_inttable *table, upb_ctype_t ctype) {
 274   return upb_inttable_init2(table, ctype, &upb_alloc_global);
 275 }
 276
 277 UPB_INLINE bool upb_strtable_init(upb_strtable *table, upb_ctype_t ctype) {
 278   return upb_strtable_init2(table, ctype, &upb_alloc_global);
 279 }
 280
 281 UPB_INLINE void upb_inttable_uninit(upb_inttable *table) {
 282   upb_inttable_uninit2(table, &upb_alloc_global);
 283 }
 284
 285 UPB_INLINE void upb_strtable_uninit(upb_strtable *table) {
 286   upb_strtable_uninit2(table, &upb_alloc_global);
 287 }
 288
 289 /* Returns the number of values in the table. */
 290 size_t upb_inttable_count(const upb_inttable *t);
 291 UPB_INLINE size_t upb_strtable_count(const upb_strtable *t) {
 292   return t->t.count;
 293 }
 294
 295 void upb_inttable_packedsize(const upb_inttable *t, size_t *size);
 296 void upb_strtable_packedsize(const upb_strtable *t, size_t *size);
 297 upb_inttable *upb_inttable_pack(const upb_inttable *t, void *p, size_t *ofs,
 298                                 size_t size);
 299 upb_strtable *upb_strtable_pack(const upb_strtable *t, void *p, size_t *ofs,
 300                                 size_t size);
 301
 302 /* Inserts the given key into the hashtable with the given value.  The key must
 303  * not already exist in the hash table.  For string tables, the key must be
 304  * NULL-terminated, and the table will make an internal copy of the key.
 305  * Inttables must not insert a value of UINTPTR_MAX.
 306  *
 307  * If a table resize was required but memory allocation failed, false is
 308  * returned and the table is unchanged. */
 309 bool upb_inttable_insert2(upb_inttable *t, uintptr_t key, upb_value val,
 310                           upb_alloc *a);
 311 bool upb_strtable_insert3(upb_strtable *t, const char *key, size_t len,
 312                           upb_value val, upb_alloc *a);
 313
 314 UPB_INLINE bool upb_inttable_insert(upb_inttable *t, uintptr_t key,
 315                                     upb_value val) {
 316   return upb_inttable_insert2(t, key, val, &upb_alloc_global);
 317 }
 318
 319 UPB_INLINE bool upb_strtable_insert2(upb_strtable *t, const char *key,
 320                                      size_t len, upb_value val) {
 321   return upb_strtable_insert3(t, key, len, val, &upb_alloc_global);
 322 }
 323
 324 /* For NULL-terminated strings. */
 325 UPB_INLINE bool upb_strtable_insert(upb_strtable *t, const char *key,
 326                                     upb_value val) {
 327   return upb_strtable_insert2(t, key, strlen(key), val);
 328 }
 329
 330 /* Looks up key in this table, returning "true" if the key was found.
 331  * If v is non-NULL, copies the value for this key into *v. */
 332 bool upb_inttable_lookup(const upb_inttable *t, uintptr_t key, upb_value *v);
 333 bool upb_strtable_lookup2(const upb_strtable *t, const char *key, size_t len,
 334                           upb_value *v);
 335
 336 /* For NULL-terminated strings. */
 337 UPB_INLINE bool upb_strtable_lookup(const upb_strtable *t, const char *key,
 338                                     upb_value *v) {
 339   return upb_strtable_lookup2(t, key, strlen(key), v);
 340 }
 341
 342 /* Removes an item from the table.  Returns true if the remove was successful,
 343  * and stores the removed item in *val if non-NULL. */
 344 bool upb_inttable_remove(upb_inttable *t, uintptr_t key, upb_value *val);
 345 bool upb_strtable_remove3(upb_strtable *t, const char *key, size_t len,
 346                           upb_value *val, upb_alloc *alloc);
 347
 348 UPB_INLINE bool upb_strtable_remove2(upb_strtable *t, const char *key,
 349                                      size_t len, upb_value *val) {
 350   return upb_strtable_remove3(t, key, len, val, &upb_alloc_global);
 351 }
 352
 353 /* For NULL-terminated strings. */
 354 UPB_INLINE bool upb_strtable_remove(upb_strtable *t, const char *key,
 355                                     upb_value *v) {
 356   return upb_strtable_remove2(t, key, strlen(key), v);
 357 }
 358
 359 /* Updates an existing entry in an inttable.  If the entry does not exist,
 360  * returns false and does nothing.  Unlike insert/remove, this does not
 361  * invalidate iterators. */
 362 bool upb_inttable_replace(upb_inttable *t, uintptr_t key, upb_value val);
 363
 364 /* Handy routines for treating an inttable like a stack.  May not be mixed with
 365  * other insert/remove calls. */
 366 bool upb_inttable_push2(upb_inttable *t, upb_value val, upb_alloc *a);
 367 upb_value upb_inttable_pop(upb_inttable *t);
 368
 369 UPB_INLINE bool upb_inttable_push(upb_inttable *t, upb_value val) {
 370   return upb_inttable_push2(t, val, &upb_alloc_global);
 371 }
 372
 373 /* Convenience routines for inttables with pointer keys. */
 374 bool upb_inttable_insertptr2(upb_inttable *t, const void *key, upb_value val,
 375                              upb_alloc *a);
 376 bool upb_inttable_removeptr(upb_inttable *t, const void *key, upb_value *val);
 377 bool upb_inttable_lookupptr(
 378     const upb_inttable *t, const void *key, upb_value *val);
 379
 380 UPB_INLINE bool upb_inttable_insertptr(upb_inttable *t, const void *key,
 381                                        upb_value val) {
 382   return upb_inttable_insertptr2(t, key, val, &upb_alloc_global);
 383 }
 384
 385 /* Optimizes the table for the current set of entries, for both memory use and
 386  * lookup time.  Client should call this after all entries have been inserted;
 387  * inserting more entries is legal, but will likely require a table resize. */
 388 void upb_inttable_compact2(upb_inttable *t, upb_alloc *a);
 389
 390 UPB_INLINE void upb_inttable_compact(upb_inttable *t) {
 391   upb_inttable_compact2(t, &upb_alloc_global);
 392 }
 393
 394 /* A special-case inlinable version of the lookup routine for 32-bit
 395  * integers. */
 396 UPB_INLINE bool upb_inttable_lookup32(const upb_inttable *t, uint32_t key,
 397                                       upb_value *v) {
 398   *v = upb_value_int32(0);  /* Silence compiler warnings. */
 399   if (key < t->array_size) {
 400     upb_tabval arrval = t->array[key];
 401     if (upb_arrhas(arrval)) {
 402       _upb_value_setval(v, arrval.val, t->t.ctype);
 403       return true;
 404     } else {
 405       return false;
 406     }
 407   } else {
 408     const upb_tabent *e;
 409     if (t->t.entries == NULL) return false;
 410     for (e = upb_getentry(&t->t, upb_inthash(key)); true; e = e->next) {
 411       if ((uint32_t)e->key == key) {
 412         _upb_value_setval(v, e->val.val, t->t.ctype);
 413         return true;
 414       }
 415       if (e->next == NULL) return false;
 416     }
 417   }
 418 }
 419
 420 /* Exposed for testing only. */
 421 bool upb_strtable_resize(upb_strtable *t, size_t size_lg2, upb_alloc *a);
 422
 423 /* Iterators ******************************************************************/
 424
 425 /* Iterators for int and string tables.  We are subject to some kind of unusual
 426  * design constraints:
 427  *
 428  * For high-level languages:
 429  *  - we must be able to guarantee that we don't crash or corrupt memory even if
 430  *    the program accesses an invalidated iterator.
 431  *
 432  * For C++11 range-based for:
 433  *  - iterators must be copyable
 434  *  - iterators must be comparable
 435  *  - it must be possible to construct an "end" value.
 436  *
 437  * Iteration order is undefined.
 438  *
 439  * Modifying the table invalidates iterators.  upb_{str,int}table_done() is
 440  * guaranteed to work even on an invalidated iterator, as long as the table it
 441  * is iterating over has not been freed.  Calling next() or accessing data from
 442  * an invalidated iterator yields unspecified elements from the table, but it is
 443  * guaranteed not to crash and to return real table elements (except when done()
 444  * is true). */
 445
 446
 447 /* upb_strtable_iter **********************************************************/
 448
 449 /*   upb_strtable_iter i;
 450  *   upb_strtable_begin(&i, t);
 451  *   for(; !upb_strtable_done(&i); upb_strtable_next(&i)) {
 452  *     const char *key = upb_strtable_iter_key(&i);
 453  *     const upb_value val = upb_strtable_iter_value(&i);
 454  *     // ...
 455  *   }
 456  */
 457
 458 typedef struct {
 459   const upb_strtable *t;
 460   size_t index;
 461 } upb_strtable_iter;
 462
 463 void upb_strtable_begin(upb_strtable_iter *i, const upb_strtable *t);
 464 void upb_strtable_next(upb_strtable_iter *i);
 465 bool upb_strtable_done(const upb_strtable_iter *i);
 466 const char *upb_strtable_iter_key(const upb_strtable_iter *i);
 467 size_t upb_strtable_iter_keylength(const upb_strtable_iter *i);
 468 upb_value upb_strtable_iter_value(const upb_strtable_iter *i);
 469 void upb_strtable_iter_setdone(upb_strtable_iter *i);
 470 bool upb_strtable_iter_isequal(const upb_strtable_iter *i1,
 471                                const upb_strtable_iter *i2);
 472
 473
 474 /* upb_inttable_iter **********************************************************/
 475
 476 /*   upb_inttable_iter i;
 477  *   upb_inttable_begin(&i, t);
 478  *   for(; !upb_inttable_done(&i); upb_inttable_next(&i)) {
 479  *     uintptr_t key = upb_inttable_iter_key(&i);
 480  *     upb_value val = upb_inttable_iter_value(&i);
 481  *     // ...
 482  *   }
 483  */
 484
 485 typedef struct {
 486   const upb_inttable *t;
 487   size_t index;
 488   bool array_part;
 489 } upb_inttable_iter;
 490
 491 void upb_inttable_begin(upb_inttable_iter *i, const upb_inttable *t);
 492 void upb_inttable_next(upb_inttable_iter *i);
 493 bool upb_inttable_done(const upb_inttable_iter *i);
 494 uintptr_t upb_inttable_iter_key(const upb_inttable_iter *i);
 495 upb_value upb_inttable_iter_value(const upb_inttable_iter *i);
 496 void upb_inttable_iter_setdone(upb_inttable_iter *i);
 497 bool upb_inttable_iter_isequal(const upb_inttable_iter *i1,
 498                                const upb_inttable_iter *i2);
 499
 500
 501 #ifdef __cplusplus
 502 }  /* extern "C" */
 503 #endif
 504
 505 #include "upb/port_undef.inc"
 506
 507 #endif  /* UPB_TABLE_H_ */