third_party/upb/upb/table.c

   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 Implementation
  30  *
  31  * Implementation is heavily inspired by Lua's ltable.c.
  32  */
  33
  34 #include <string.h>
  35
  36 #include "upb/table_internal.h"
  37
  38 /* Must be last. */
  39 #include "upb/port_def.inc"
  40
  41 #define UPB_MAXARRSIZE 16  /* 64k. */
  42
  43 /* From Chromium. */
  44 #define ARRAY_SIZE(x) \
  45     ((sizeof(x)/sizeof(0[x])) / ((size_t)(!(sizeof(x) % sizeof(0[x])))))
  46
  47 static const double MAX_LOAD = 0.85;
  48
  49 /* The minimum utilization of the array part of a mixed hash/array table.  This
  50  * is a speed/memory-usage tradeoff (though it's not straightforward because of
  51  * cache effects).  The lower this is, the more memory we'll use. */
  52 static const double MIN_DENSITY = 0.1;
  53
  54 static bool is_pow2(uint64_t v) { return v == 0 || (v & (v - 1)) == 0; }
  55
  56 static upb_value _upb_value_val(uint64_t val) {
  57   upb_value ret;
  58   _upb_value_setval(&ret, val);
  59   return ret;
  60 }
  61
  62 static int log2ceil(uint64_t v) {
  63   int ret = 0;
  64   bool pow2 = is_pow2(v);
  65   while (v >>= 1) ret++;
  66   ret = pow2 ? ret : ret + 1;  /* Ceiling. */
  67   return UPB_MIN(UPB_MAXARRSIZE, ret);
  68 }
  69
  70 char *upb_strdup2(const char *s, size_t len, upb_arena *a) {
  71   size_t n;
  72   char *p;
  73
  74   /* Prevent overflow errors. */
  75   if (len == SIZE_MAX) return NULL;
  76   /* Always null-terminate, even if binary data; but don't rely on the input to
  77    * have a null-terminating byte since it may be a raw binary buffer. */
  78   n = len + 1;
  79   p = upb_arena_malloc(a, n);
  80   if (p) {
  81     memcpy(p, s, len);
  82     p[len] = 0;
  83   }
  84   return p;
  85 }
  86
  87 /* A type to represent the lookup key of either a strtable or an inttable. */
  88 typedef union {
  89   uintptr_t num;
  90   struct {
  91     const char *str;
  92     size_t len;
  93   } str;
  94 } lookupkey_t;
  95
  96 static lookupkey_t strkey2(const char *str, size_t len) {
  97   lookupkey_t k;
  98   k.str.str = str;
  99   k.str.len = len;
 100   return k;
 101 }
 102
 103 static lookupkey_t intkey(uintptr_t key) {
 104   lookupkey_t k;
 105   k.num = key;
 106   return k;
 107 }
 108
 109 typedef uint32_t hashfunc_t(upb_tabkey key);
 110 typedef bool eqlfunc_t(upb_tabkey k1, lookupkey_t k2);
 111
 112 /* Base table (shared code) ***************************************************/
 113
 114 static uint32_t upb_inthash(uintptr_t key) {
 115   return (uint32_t)key;
 116 }
 117
 118 static const upb_tabent *upb_getentry(const upb_table *t, uint32_t hash) {
 119   return t->entries + (hash & t->mask);
 120 }
 121
 122 static bool upb_arrhas(upb_tabval key) {
 123   return key.val != (uint64_t)-1;
 124 }
 125
 126
 127 static bool isfull(upb_table *t) {
 128   return t->count == t->max_count;
 129 }
 130
 131 static bool init(upb_table *t, uint8_t size_lg2, upb_arena *a) {
 132   size_t bytes;
 133
 134   t->count = 0;
 135   t->size_lg2 = size_lg2;
 136   t->mask = upb_table_size(t) ? upb_table_size(t) - 1 : 0;
 137   t->max_count = upb_table_size(t) * MAX_LOAD;
 138   bytes = upb_table_size(t) * sizeof(upb_tabent);
 139   if (bytes > 0) {
 140     t->entries = upb_arena_malloc(a, bytes);
 141     if (!t->entries) return false;
 142     memset(t->entries, 0, bytes);
 143   } else {
 144     t->entries = NULL;
 145   }
 146   return true;
 147 }
 148
 149 static upb_tabent *emptyent(upb_table *t, upb_tabent *e) {
 150   upb_tabent *begin = t->entries;
 151   upb_tabent *end = begin + upb_table_size(t);
 152   for (e = e + 1; e < end; e++) {
 153     if (upb_tabent_isempty(e)) return e;
 154   }
 155   for (e = begin; e < end; e++) {
 156     if (upb_tabent_isempty(e)) return e;
 157   }
 158   UPB_ASSERT(false);
 159   return NULL;
 160 }
 161
 162 static upb_tabent *getentry_mutable(upb_table *t, uint32_t hash) {
 163   return (upb_tabent*)upb_getentry(t, hash);
 164 }
 165
 166 static const upb_tabent *findentry(const upb_table *t, lookupkey_t key,
 167                                    uint32_t hash, eqlfunc_t *eql) {
 168   const upb_tabent *e;
 169
 170   if (t->size_lg2 == 0) return NULL;
 171   e = upb_getentry(t, hash);
 172   if (upb_tabent_isempty(e)) return NULL;
 173   while (1) {
 174     if (eql(e->key, key)) return e;
 175     if ((e = e->next) == NULL) return NULL;
 176   }
 177 }
 178
 179 static upb_tabent *findentry_mutable(upb_table *t, lookupkey_t key,
 180                                      uint32_t hash, eqlfunc_t *eql) {
 181   return (upb_tabent*)findentry(t, key, hash, eql);
 182 }
 183
 184 static bool lookup(const upb_table *t, lookupkey_t key, upb_value *v,
 185                    uint32_t hash, eqlfunc_t *eql) {
 186   const upb_tabent *e = findentry(t, key, hash, eql);
 187   if (e) {
 188     if (v) {
 189       _upb_value_setval(v, e->val.val);
 190     }
 191     return true;
 192   } else {
 193     return false;
 194   }
 195 }
 196
 197 /* The given key must not already exist in the table. */
 198 static void insert(upb_table *t, lookupkey_t key, upb_tabkey tabkey,
 199                    upb_value val, uint32_t hash,
 200                    hashfunc_t *hashfunc, eqlfunc_t *eql) {
 201   upb_tabent *mainpos_e;
 202   upb_tabent *our_e;
 203
 204   UPB_ASSERT(findentry(t, key, hash, eql) == NULL);
 205
 206   t->count++;
 207   mainpos_e = getentry_mutable(t, hash);
 208   our_e = mainpos_e;
 209
 210   if (upb_tabent_isempty(mainpos_e)) {
 211     /* Our main position is empty; use it. */
 212     our_e->next = NULL;
 213   } else {
 214     /* Collision. */
 215     upb_tabent *new_e = emptyent(t, mainpos_e);
 216     /* Head of collider's chain. */
 217     upb_tabent *chain = getentry_mutable(t, hashfunc(mainpos_e->key));
 218     if (chain == mainpos_e) {
 219       /* Existing ent is in its main position (it has the same hash as us, and
 220        * is the head of our chain).  Insert to new ent and append to this chain. */
 221       new_e->next = mainpos_e->next;
 222       mainpos_e->next = new_e;
 223       our_e = new_e;
 224     } else {
 225       /* Existing ent is not in its main position (it is a node in some other
 226        * chain).  This implies that no existing ent in the table has our hash.
 227        * Evict it (updating its chain) and use its ent for head of our chain. */
 228       *new_e = *mainpos_e;  /* copies next. */
 229       while (chain->next != mainpos_e) {
 230         chain = (upb_tabent*)chain->next;
 231         UPB_ASSERT(chain);
 232       }
 233       chain->next = new_e;
 234       our_e = mainpos_e;
 235       our_e->next = NULL;
 236     }
 237   }
 238   our_e->key = tabkey;
 239   our_e->val.val = val.val;
 240   UPB_ASSERT(findentry(t, key, hash, eql) == our_e);
 241 }
 242
 243 static bool rm(upb_table *t, lookupkey_t key, upb_value *val,
 244                upb_tabkey *removed, uint32_t hash, eqlfunc_t *eql) {
 245   upb_tabent *chain = getentry_mutable(t, hash);
 246   if (upb_tabent_isempty(chain)) return false;
 247   if (eql(chain->key, key)) {
 248     /* Element to remove is at the head of its chain. */
 249     t->count--;
 250     if (val) _upb_value_setval(val, chain->val.val);
 251     if (removed) *removed = chain->key;
 252     if (chain->next) {
 253       upb_tabent *move = (upb_tabent*)chain->next;
 254       *chain = *move;
 255       move->key = 0;  /* Make the slot empty. */
 256     } else {
 257       chain->key = 0;  /* Make the slot empty. */
 258     }
 259     return true;
 260   } else {
 261     /* Element to remove is either in a non-head position or not in the
 262      * table. */
 263     while (chain->next && !eql(chain->next->key, key)) {
 264       chain = (upb_tabent*)chain->next;
 265     }
 266     if (chain->next) {
 267       /* Found element to remove. */
 268       upb_tabent *rm = (upb_tabent*)chain->next;
 269       t->count--;
 270       if (val) _upb_value_setval(val, chain->next->val.val);
 271       if (removed) *removed = rm->key;
 272       rm->key = 0;  /* Make the slot empty. */
 273       chain->next = rm->next;
 274       return true;
 275     } else {
 276       /* Element to remove is not in the table. */
 277       return false;
 278     }
 279   }
 280 }
 281
 282 static size_t next(const upb_table *t, size_t i) {
 283   do {
 284     if (++i >= upb_table_size(t))
 285       return SIZE_MAX - 1;  /* Distinct from -1. */
 286   } while(upb_tabent_isempty(&t->entries[i]));
 287
 288   return i;
 289 }
 290
 291 static size_t begin(const upb_table *t) {
 292   return next(t, -1);
 293 }
 294
 295
 296 /* upb_strtable ***************************************************************/
 297
 298 /* A simple "subclass" of upb_table that only adds a hash function for strings. */
 299
 300 static upb_tabkey strcopy(lookupkey_t k2, upb_arena *a) {
 301   uint32_t len = (uint32_t) k2.str.len;
 302   char *str = upb_arena_malloc(a, k2.str.len + sizeof(uint32_t) + 1);
 303   if (str == NULL) return 0;
 304   memcpy(str, &len, sizeof(uint32_t));
 305   if (k2.str.len) memcpy(str + sizeof(uint32_t), k2.str.str, k2.str.len);
 306   str[sizeof(uint32_t) + k2.str.len] = '\0';
 307   return (uintptr_t)str;
 308 }
 309
 310 /* Adapted from ABSL's wyhash. */
 311
 312 static uint64_t UnalignedLoad64(const void *p) {
 313   uint64_t val;
 314   memcpy(&val, p, 8);
 315   return val;
 316 }
 317
 318 static uint32_t UnalignedLoad32(const void *p) {
 319   uint32_t val;
 320   memcpy(&val, p, 4);
 321   return val;
 322 }
 323
 324 #if defined(_MSC_VER) && defined(_M_X64)
 325 #include <intrin.h>
 326 #endif
 327
 328 /* Computes a * b, returning the low 64 bits of the result and storing the high
 329  * 64 bits in |*high|. */
 330 static uint64_t upb_umul128(uint64_t v0, uint64_t v1, uint64_t* out_high) {
 331 #ifdef __SIZEOF_INT128__
 332   __uint128_t p = v0;
 333   p *= v1;
 334   *out_high = (uint64_t)(p >> 64);
 335   return (uint64_t)p;
 336 #elif defined(_MSC_VER) && defined(_M_X64)
 337   return _umul128(v0, v1, out_high);
 338 #else
 339   uint64_t a32 = v0 >> 32;
 340   uint64_t a00 = v0 & 0xffffffff;
 341   uint64_t b32 = v1 >> 32;
 342   uint64_t b00 = v1 & 0xffffffff;
 343   uint64_t high = a32 * b32;
 344   uint64_t low = a00 * b00;
 345   uint64_t mid1 = a32 * b00;
 346   uint64_t mid2 = a00 * b32;
 347   low += (mid1 << 32) + (mid2 << 32);
 348   // Omit carry bit, for mixing we do not care about exact numerical precision.
 349   high += (mid1 >> 32) + (mid2 >> 32);
 350   *out_high = high;
 351   return low;
 352 #endif
 353 }
 354
 355 static uint64_t WyhashMix(uint64_t v0, uint64_t v1) {
 356   uint64_t high;
 357   uint64_t low = upb_umul128(v0, v1, &high);
 358   return low ^ high;
 359 }
 360
 361 static uint64_t Wyhash(const void *data, size_t len, uint64_t seed,
 362                        const uint64_t salt[]) {
 363   const uint8_t* ptr = (const uint8_t*)data;
 364   uint64_t starting_length = (uint64_t)len;
 365   uint64_t current_state = seed ^ salt[0];
 366
 367   if (len > 64) {
 368     // If we have more than 64 bytes, we're going to handle chunks of 64
 369     // bytes at a time. We're going to build up two separate hash states
 370     // which we will then hash together.
 371     uint64_t duplicated_state = current_state;
 372
 373     do {
 374       uint64_t a = UnalignedLoad64(ptr);
 375       uint64_t b = UnalignedLoad64(ptr + 8);
 376       uint64_t c = UnalignedLoad64(ptr + 16);
 377       uint64_t d = UnalignedLoad64(ptr + 24);
 378       uint64_t e = UnalignedLoad64(ptr + 32);
 379       uint64_t f = UnalignedLoad64(ptr + 40);
 380       uint64_t g = UnalignedLoad64(ptr + 48);
 381       uint64_t h = UnalignedLoad64(ptr + 56);
 382
 383       uint64_t cs0 = WyhashMix(a ^ salt[1], b ^ current_state);
 384       uint64_t cs1 = WyhashMix(c ^ salt[2], d ^ current_state);
 385       current_state = (cs0 ^ cs1);
 386
 387       uint64_t ds0 = WyhashMix(e ^ salt[3], f ^ duplicated_state);
 388       uint64_t ds1 = WyhashMix(g ^ salt[4], h ^ duplicated_state);
 389       duplicated_state = (ds0 ^ ds1);
 390
 391       ptr += 64;
 392       len -= 64;
 393     } while (len > 64);
 394
 395     current_state = current_state ^ duplicated_state;
 396   }
 397
 398   // We now have a data `ptr` with at most 64 bytes and the current state
 399   // of the hashing state machine stored in current_state.
 400   while (len > 16) {
 401     uint64_t a = UnalignedLoad64(ptr);
 402     uint64_t b = UnalignedLoad64(ptr + 8);
 403
 404     current_state = WyhashMix(a ^ salt[1], b ^ current_state);
 405
 406     ptr += 16;
 407     len -= 16;
 408   }
 409
 410   // We now have a data `ptr` with at most 16 bytes.
 411   uint64_t a = 0;
 412   uint64_t b = 0;
 413   if (len > 8) {
 414     // When we have at least 9 and at most 16 bytes, set A to the first 64
 415     // bits of the input and B to the last 64 bits of the input. Yes, they will
 416     // overlap in the middle if we are working with less than the full 16
 417     // bytes.
 418     a = UnalignedLoad64(ptr);
 419     b = UnalignedLoad64(ptr + len - 8);
 420   } else if (len > 3) {
 421     // If we have at least 4 and at most 8 bytes, set A to the first 32
 422     // bits and B to the last 32 bits.
 423     a = UnalignedLoad32(ptr);
 424     b = UnalignedLoad32(ptr + len - 4);
 425   } else if (len > 0) {
 426     // If we have at least 1 and at most 3 bytes, read all of the provided
 427     // bits into A, with some adjustments.
 428     a = ((ptr[0] << 16) | (ptr[len >> 1] << 8) | ptr[len - 1]);
 429     b = 0;
 430   } else {
 431     a = 0;
 432     b = 0;
 433   }
 434
 435   uint64_t w = WyhashMix(a ^ salt[1], b ^ current_state);
 436   uint64_t z = salt[1] ^ starting_length;
 437   return WyhashMix(w, z);
 438 }
 439
 440 const uint64_t kWyhashSalt[5] = {
 441     0x243F6A8885A308D3ULL, 0x13198A2E03707344ULL, 0xA4093822299F31D0ULL,
 442     0x082EFA98EC4E6C89ULL, 0x452821E638D01377ULL,
 443 };
 444
 445 static uint32_t table_hash(const char *p, size_t n) {
 446   return Wyhash(p, n, 0, kWyhashSalt);
 447 }
 448
 449 static uint32_t strhash(upb_tabkey key) {
 450   uint32_t len;
 451   char *str = upb_tabstr(key, &len);
 452   return table_hash(str, len);
 453 }
 454
 455 static bool streql(upb_tabkey k1, lookupkey_t k2) {
 456   uint32_t len;
 457   char *str = upb_tabstr(k1, &len);
 458   return len == k2.str.len && (len == 0 || memcmp(str, k2.str.str, len) == 0);
 459 }
 460
 461 bool upb_strtable_init(upb_strtable *t, size_t expected_size, upb_arena *a) {
 462   // Multiply by approximate reciprocal of MAX_LOAD (0.85), with pow2 denominator.
 463   size_t need_entries = (expected_size + 1) * 1204 / 1024;
 464   UPB_ASSERT(need_entries >= expected_size * 0.85);
 465   int size_lg2 = _upb_lg2ceil(need_entries);
 466   return init(&t->t, size_lg2, a);
 467 }
 468
 469 void upb_strtable_clear(upb_strtable *t) {
 470   size_t bytes = upb_table_size(&t->t) * sizeof(upb_tabent);
 471   t->t.count = 0;
 472   memset((char*)t->t.entries, 0, bytes);
 473 }
 474
 475 bool upb_strtable_resize(upb_strtable *t, size_t size_lg2, upb_arena *a) {
 476   upb_strtable new_table;
 477   upb_strtable_iter i;
 478
 479   if (!init(&new_table.t, size_lg2, a))
 480     return false;
 481   upb_strtable_begin(&i, t);
 482   for ( ; !upb_strtable_done(&i); upb_strtable_next(&i)) {
 483     upb_strview key = upb_strtable_iter_key(&i);
 484     upb_strtable_insert(&new_table, key.data, key.size,
 485                         upb_strtable_iter_value(&i), a);
 486   }
 487   *t = new_table;
 488   return true;
 489 }
 490
 491 bool upb_strtable_insert(upb_strtable *t, const char *k, size_t len,
 492                          upb_value v, upb_arena *a) {
 493   lookupkey_t key;
 494   upb_tabkey tabkey;
 495   uint32_t hash;
 496
 497   if (isfull(&t->t)) {
 498     /* Need to resize.  New table of double the size, add old elements to it. */
 499     if (!upb_strtable_resize(t, t->t.size_lg2 + 1, a)) {
 500       return false;
 501     }
 502   }
 503
 504   key = strkey2(k, len);
 505   tabkey = strcopy(key, a);
 506   if (tabkey == 0) return false;
 507
 508   hash = table_hash(key.str.str, key.str.len);
 509   insert(&t->t, key, tabkey, v, hash, &strhash, &streql);
 510   return true;
 511 }
 512
 513 bool upb_strtable_lookup2(const upb_strtable *t, const char *key, size_t len,
 514                           upb_value *v) {
 515   uint32_t hash = table_hash(key, len);
 516   return lookup(&t->t, strkey2(key, len), v, hash, &streql);
 517 }
 518
 519 bool upb_strtable_remove(upb_strtable *t, const char *key, size_t len,
 520                          upb_value *val) {
 521   uint32_t hash = table_hash(key, len);
 522   upb_tabkey tabkey;
 523   return rm(&t->t, strkey2(key, len), val, &tabkey, hash, &streql);
 524 }
 525
 526 /* Iteration */
 527
 528 void upb_strtable_begin(upb_strtable_iter *i, const upb_strtable *t) {
 529   i->t = t;
 530   i->index = begin(&t->t);
 531 }
 532
 533 void upb_strtable_next(upb_strtable_iter *i) {
 534   i->index = next(&i->t->t, i->index);
 535 }
 536
 537 bool upb_strtable_done(const upb_strtable_iter *i) {
 538   if (!i->t) return true;
 539   return i->index >= upb_table_size(&i->t->t) ||
 540          upb_tabent_isempty(str_tabent(i));
 541 }
 542
 543 upb_strview upb_strtable_iter_key(const upb_strtable_iter *i) {
 544   upb_strview key;
 545   uint32_t len;
 546   UPB_ASSERT(!upb_strtable_done(i));
 547   key.data = upb_tabstr(str_tabent(i)->key, &len);
 548   key.size = len;
 549   return key;
 550 }
 551
 552 upb_value upb_strtable_iter_value(const upb_strtable_iter *i) {
 553   UPB_ASSERT(!upb_strtable_done(i));
 554   return _upb_value_val(str_tabent(i)->val.val);
 555 }
 556
 557 void upb_strtable_iter_setdone(upb_strtable_iter *i) {
 558   i->t = NULL;
 559   i->index = SIZE_MAX;
 560 }
 561
 562 bool upb_strtable_iter_isequal(const upb_strtable_iter *i1,
 563                                const upb_strtable_iter *i2) {
 564   if (upb_strtable_done(i1) && upb_strtable_done(i2))
 565     return true;
 566   return i1->t == i2->t && i1->index == i2->index;
 567 }
 568
 569
 570 /* upb_inttable ***************************************************************/
 571
 572 /* For inttables we use a hybrid structure where small keys are kept in an
 573  * array and large keys are put in the hash table. */
 574
 575 static uint32_t inthash(upb_tabkey key) { return upb_inthash(key); }
 576
 577 static bool inteql(upb_tabkey k1, lookupkey_t k2) {
 578   return k1 == k2.num;
 579 }
 580
 581 static upb_tabval *mutable_array(upb_inttable *t) {
 582   return (upb_tabval*)t->array;
 583 }
 584
 585 static upb_tabval *inttable_val(upb_inttable *t, uintptr_t key) {
 586   if (key < t->array_size) {
 587     return upb_arrhas(t->array[key]) ? &(mutable_array(t)[key]) : NULL;
 588   } else {
 589     upb_tabent *e =
 590         findentry_mutable(&t->t, intkey(key), upb_inthash(key), &inteql);
 591     return e ? &e->val : NULL;
 592   }
 593 }
 594
 595 static const upb_tabval *inttable_val_const(const upb_inttable *t,
 596                                             uintptr_t key) {
 597   return inttable_val((upb_inttable*)t, key);
 598 }
 599
 600 size_t upb_inttable_count(const upb_inttable *t) {
 601   return t->t.count + t->array_count;
 602 }
 603
 604 static void check(upb_inttable *t) {
 605   UPB_UNUSED(t);
 606 #if defined(UPB_DEBUG_TABLE) && !defined(NDEBUG)
 607   {
 608     /* This check is very expensive (makes inserts/deletes O(N)). */
 609     size_t count = 0;
 610     upb_inttable_iter i;
 611     upb_inttable_begin(&i, t);
 612     for(; !upb_inttable_done(&i); upb_inttable_next(&i), count++) {
 613       UPB_ASSERT(upb_inttable_lookup(t, upb_inttable_iter_key(&i), NULL));
 614     }
 615     UPB_ASSERT(count == upb_inttable_count(t));
 616   }
 617 #endif
 618 }
 619
 620 bool upb_inttable_sizedinit(upb_inttable *t, size_t asize, int hsize_lg2,
 621                             upb_arena *a) {
 622   size_t array_bytes;
 623
 624   if (!init(&t->t, hsize_lg2, a)) return false;
 625   /* Always make the array part at least 1 long, so that we know key 0
 626    * won't be in the hash part, which simplifies things. */
 627   t->array_size = UPB_MAX(1, asize);
 628   t->array_count = 0;
 629   array_bytes = t->array_size * sizeof(upb_value);
 630   t->array = upb_arena_malloc(a, array_bytes);
 631   if (!t->array) {
 632     return false;
 633   }
 634   memset(mutable_array(t), 0xff, array_bytes);
 635   check(t);
 636   return true;
 637 }
 638
 639 bool upb_inttable_init(upb_inttable *t, upb_arena *a) {
 640   return upb_inttable_sizedinit(t, 0, 4, a);
 641 }
 642
 643 bool upb_inttable_insert(upb_inttable *t, uintptr_t key, upb_value val,
 644                          upb_arena *a) {
 645   upb_tabval tabval;
 646   tabval.val = val.val;
 647   UPB_ASSERT(upb_arrhas(tabval));  /* This will reject (uint64_t)-1.  Fix this. */
 648
 649   if (key < t->array_size) {
 650     UPB_ASSERT(!upb_arrhas(t->array[key]));
 651     t->array_count++;
 652     mutable_array(t)[key].val = val.val;
 653   } else {
 654     if (isfull(&t->t)) {
 655       /* Need to resize the hash part, but we re-use the array part. */
 656       size_t i;
 657       upb_table new_table;
 658
 659       if (!init(&new_table, t->t.size_lg2 + 1, a)) {
 660         return false;
 661       }
 662
 663       for (i = begin(&t->t); i < upb_table_size(&t->t); i = next(&t->t, i)) {
 664         const upb_tabent *e = &t->t.entries[i];
 665         uint32_t hash;
 666         upb_value v;
 667
 668         _upb_value_setval(&v, e->val.val);
 669         hash = upb_inthash(e->key);
 670         insert(&new_table, intkey(e->key), e->key, v, hash, &inthash, &inteql);
 671       }
 672
 673       UPB_ASSERT(t->t.count == new_table.count);
 674
 675       t->t = new_table;
 676     }
 677     insert(&t->t, intkey(key), key, val, upb_inthash(key), &inthash, &inteql);
 678   }
 679   check(t);
 680   return true;
 681 }
 682
 683 bool upb_inttable_lookup(const upb_inttable *t, uintptr_t key, upb_value *v) {
 684   const upb_tabval *table_v = inttable_val_const(t, key);
 685   if (!table_v) return false;
 686   if (v) _upb_value_setval(v, table_v->val);
 687   return true;
 688 }
 689
 690 bool upb_inttable_replace(upb_inttable *t, uintptr_t key, upb_value val) {
 691   upb_tabval *table_v = inttable_val(t, key);
 692   if (!table_v) return false;
 693   table_v->val = val.val;
 694   return true;
 695 }
 696
 697 bool upb_inttable_remove(upb_inttable *t, uintptr_t key, upb_value *val) {
 698   bool success;
 699   if (key < t->array_size) {
 700     if (upb_arrhas(t->array[key])) {
 701       upb_tabval empty = UPB_TABVALUE_EMPTY_INIT;
 702       t->array_count--;
 703       if (val) {
 704         _upb_value_setval(val, t->array[key].val);
 705       }
 706       mutable_array(t)[key] = empty;
 707       success = true;
 708     } else {
 709       success = false;
 710     }
 711   } else {
 712     success = rm(&t->t, intkey(key), val, NULL, upb_inthash(key), &inteql);
 713   }
 714   check(t);
 715   return success;
 716 }
 717
 718 void upb_inttable_compact(upb_inttable *t, upb_arena *a) {
 719   /* A power-of-two histogram of the table keys. */
 720   size_t counts[UPB_MAXARRSIZE + 1] = {0};
 721
 722   /* The max key in each bucket. */
 723   uintptr_t max[UPB_MAXARRSIZE + 1] = {0};
 724
 725   upb_inttable_iter i;
 726   size_t arr_count;
 727   int size_lg2;
 728   upb_inttable new_t;
 729
 730   upb_inttable_begin(&i, t);
 731   for (; !upb_inttable_done(&i); upb_inttable_next(&i)) {
 732     uintptr_t key = upb_inttable_iter_key(&i);
 733     int bucket = log2ceil(key);
 734     max[bucket] = UPB_MAX(max[bucket], key);
 735     counts[bucket]++;
 736   }
 737
 738   /* Find the largest power of two that satisfies the MIN_DENSITY
 739    * definition (while actually having some keys). */
 740   arr_count = upb_inttable_count(t);
 741
 742   for (size_lg2 = ARRAY_SIZE(counts) - 1; size_lg2 > 0; size_lg2--) {
 743     if (counts[size_lg2] == 0) {
 744       /* We can halve again without losing any entries. */
 745       continue;
 746     } else if (arr_count >= (1 << size_lg2) * MIN_DENSITY) {
 747       break;
 748     }
 749
 750     arr_count -= counts[size_lg2];
 751   }
 752
 753   UPB_ASSERT(arr_count <= upb_inttable_count(t));
 754
 755   {
 756     /* Insert all elements into new, perfectly-sized table. */
 757     size_t arr_size = max[size_lg2] + 1;  /* +1 so arr[max] will fit. */
 758     size_t hash_count = upb_inttable_count(t) - arr_count;
 759     size_t hash_size = hash_count ? (hash_count / MAX_LOAD) + 1 : 0;
 760     int hashsize_lg2 = log2ceil(hash_size);
 761
 762     upb_inttable_sizedinit(&new_t, arr_size, hashsize_lg2, a);
 763     upb_inttable_begin(&i, t);
 764     for (; !upb_inttable_done(&i); upb_inttable_next(&i)) {
 765       uintptr_t k = upb_inttable_iter_key(&i);
 766       upb_inttable_insert(&new_t, k, upb_inttable_iter_value(&i), a);
 767     }
 768     UPB_ASSERT(new_t.array_size == arr_size);
 769     UPB_ASSERT(new_t.t.size_lg2 == hashsize_lg2);
 770   }
 771   *t = new_t;
 772 }
 773
 774 /* Iteration. */
 775
 776 static const upb_tabent *int_tabent(const upb_inttable_iter *i) {
 777   UPB_ASSERT(!i->array_part);
 778   return &i->t->t.entries[i->index];
 779 }
 780
 781 static upb_tabval int_arrent(const upb_inttable_iter *i) {
 782   UPB_ASSERT(i->array_part);
 783   return i->t->array[i->index];
 784 }
 785
 786 void upb_inttable_begin(upb_inttable_iter *i, const upb_inttable *t) {
 787   i->t = t;
 788   i->index = -1;
 789   i->array_part = true;
 790   upb_inttable_next(i);
 791 }
 792
 793 void upb_inttable_next(upb_inttable_iter *iter) {
 794   const upb_inttable *t = iter->t;
 795   if (iter->array_part) {
 796     while (++iter->index < t->array_size) {
 797       if (upb_arrhas(int_arrent(iter))) {
 798         return;
 799       }
 800     }
 801     iter->array_part = false;
 802     iter->index = begin(&t->t);
 803   } else {
 804     iter->index = next(&t->t, iter->index);
 805   }
 806 }
 807
 808 bool upb_inttable_done(const upb_inttable_iter *i) {
 809   if (!i->t) return true;
 810   if (i->array_part) {
 811     return i->index >= i->t->array_size ||
 812            !upb_arrhas(int_arrent(i));
 813   } else {
 814     return i->index >= upb_table_size(&i->t->t) ||
 815            upb_tabent_isempty(int_tabent(i));
 816   }
 817 }
 818
 819 uintptr_t upb_inttable_iter_key(const upb_inttable_iter *i) {
 820   UPB_ASSERT(!upb_inttable_done(i));
 821   return i->array_part ? i->index : int_tabent(i)->key;
 822 }
 823
 824 upb_value upb_inttable_iter_value(const upb_inttable_iter *i) {
 825   UPB_ASSERT(!upb_inttable_done(i));
 826   return _upb_value_val(
 827       i->array_part ? i->t->array[i->index].val : int_tabent(i)->val.val);
 828 }
 829
 830 void upb_inttable_iter_setdone(upb_inttable_iter *i) {
 831   i->t = NULL;
 832   i->index = SIZE_MAX;
 833   i->array_part = false;
 834 }
 835
 836 bool upb_inttable_iter_isequal(const upb_inttable_iter *i1,
 837                                           const upb_inttable_iter *i2) {
 838   if (upb_inttable_done(i1) && upb_inttable_done(i2))
 839     return true;
 840   return i1->t == i2->t && i1->index == i2->index &&
 841          i1->array_part == i2->array_part;
 842 }