legacy-libs/grpc-cloned/deps/grpc/third_party/upb/upb/table.c

   1 /*
   2 ** upb_table Implementation
   3 **
   4 ** Implementation is heavily inspired by Lua's ltable.c.
   5 */
   6
   7 #include "upb/table.int.h"
   8
   9 #include <string.h>
  10
  11 #include "upb/port_def.inc"
  12
  13 #define UPB_MAXARRSIZE 16  /* 64k. */
  14
  15 /* From Chromium. */
  16 #define ARRAY_SIZE(x) \
  17     ((sizeof(x)/sizeof(0[x])) / ((size_t)(!(sizeof(x) % sizeof(0[x])))))
  18
  19 static void upb_check_alloc(upb_table *t, upb_alloc *a) {
  20   UPB_UNUSED(t);
  21   UPB_UNUSED(a);
  22   UPB_ASSERT_DEBUGVAR(t->alloc == a);
  23 }
  24
  25 static const double MAX_LOAD = 0.85;
  26
  27 /* The minimum utilization of the array part of a mixed hash/array table.  This
  28  * is a speed/memory-usage tradeoff (though it's not straightforward because of
  29  * cache effects).  The lower this is, the more memory we'll use. */
  30 static const double MIN_DENSITY = 0.1;
  31
  32 bool is_pow2(uint64_t v) { return v == 0 || (v & (v - 1)) == 0; }
  33
  34 int log2ceil(uint64_t v) {
  35   int ret = 0;
  36   bool pow2 = is_pow2(v);
  37   while (v >>= 1) ret++;
  38   ret = pow2 ? ret : ret + 1;  /* Ceiling. */
  39   return UPB_MIN(UPB_MAXARRSIZE, ret);
  40 }
  41
  42 char *upb_strdup(const char *s, upb_alloc *a) {
  43   return upb_strdup2(s, strlen(s), a);
  44 }
  45
  46 char *upb_strdup2(const char *s, size_t len, upb_alloc *a) {
  47   size_t n;
  48   char *p;
  49
  50   /* Prevent overflow errors. */
  51   if (len == SIZE_MAX) return NULL;
  52   /* Always null-terminate, even if binary data; but don't rely on the input to
  53    * have a null-terminating byte since it may be a raw binary buffer. */
  54   n = len + 1;
  55   p = upb_malloc(a, n);
  56   if (p) {
  57     memcpy(p, s, len);
  58     p[len] = 0;
  59   }
  60   return p;
  61 }
  62
  63 /* A type to represent the lookup key of either a strtable or an inttable. */
  64 typedef union {
  65   uintptr_t num;
  66   struct {
  67     const char *str;
  68     size_t len;
  69   } str;
  70 } lookupkey_t;
  71
  72 static lookupkey_t strkey2(const char *str, size_t len) {
  73   lookupkey_t k;
  74   k.str.str = str;
  75   k.str.len = len;
  76   return k;
  77 }
  78
  79 static lookupkey_t intkey(uintptr_t key) {
  80   lookupkey_t k;
  81   k.num = key;
  82   return k;
  83 }
  84
  85 typedef uint32_t hashfunc_t(upb_tabkey key);
  86 typedef bool eqlfunc_t(upb_tabkey k1, lookupkey_t k2);
  87
  88 /* Base table (shared code) ***************************************************/
  89
  90 /* For when we need to cast away const. */
  91 static upb_tabent *mutable_entries(upb_table *t) {
  92   return (upb_tabent*)t->entries;
  93 }
  94
  95 static bool isfull(upb_table *t) {
  96   if (upb_table_size(t) == 0) {
  97     return true;
  98   } else {
  99     return ((double)(t->count + 1) / upb_table_size(t)) > MAX_LOAD;
 100   }
 101 }
 102
 103 static bool init(upb_table *t, upb_ctype_t ctype, uint8_t size_lg2,
 104                  upb_alloc *a) {
 105   size_t bytes;
 106
 107   t->count = 0;
 108   t->ctype = ctype;
 109   t->size_lg2 = size_lg2;
 110   t->mask = upb_table_size(t) ? upb_table_size(t) - 1 : 0;
 111 #ifndef NDEBUG
 112   t->alloc = a;
 113 #endif
 114   bytes = upb_table_size(t) * sizeof(upb_tabent);
 115   if (bytes > 0) {
 116     t->entries = upb_malloc(a, bytes);
 117     if (!t->entries) return false;
 118     memset(mutable_entries(t), 0, bytes);
 119   } else {
 120     t->entries = NULL;
 121   }
 122   return true;
 123 }
 124
 125 static void uninit(upb_table *t, upb_alloc *a) {
 126   upb_check_alloc(t, a);
 127   upb_free(a, mutable_entries(t));
 128 }
 129
 130 static upb_tabent *emptyent(upb_table *t) {
 131   upb_tabent *e = mutable_entries(t) + upb_table_size(t);
 132   while (1) { if (upb_tabent_isempty(--e)) return e; UPB_ASSERT(e > t->entries); }
 133 }
 134
 135 static upb_tabent *getentry_mutable(upb_table *t, uint32_t hash) {
 136   return (upb_tabent*)upb_getentry(t, hash);
 137 }
 138
 139 static const upb_tabent *findentry(const upb_table *t, lookupkey_t key,
 140                                    uint32_t hash, eqlfunc_t *eql) {
 141   const upb_tabent *e;
 142
 143   if (t->size_lg2 == 0) return NULL;
 144   e = upb_getentry(t, hash);
 145   if (upb_tabent_isempty(e)) return NULL;
 146   while (1) {
 147     if (eql(e->key, key)) return e;
 148     if ((e = e->next) == NULL) return NULL;
 149   }
 150 }
 151
 152 static upb_tabent *findentry_mutable(upb_table *t, lookupkey_t key,
 153                                      uint32_t hash, eqlfunc_t *eql) {
 154   return (upb_tabent*)findentry(t, key, hash, eql);
 155 }
 156
 157 static bool lookup(const upb_table *t, lookupkey_t key, upb_value *v,
 158                    uint32_t hash, eqlfunc_t *eql) {
 159   const upb_tabent *e = findentry(t, key, hash, eql);
 160   if (e) {
 161     if (v) {
 162       _upb_value_setval(v, e->val.val, t->ctype);
 163     }
 164     return true;
 165   } else {
 166     return false;
 167   }
 168 }
 169
 170 /* The given key must not already exist in the table. */
 171 static void insert(upb_table *t, lookupkey_t key, upb_tabkey tabkey,
 172                    upb_value val, uint32_t hash,
 173                    hashfunc_t *hashfunc, eqlfunc_t *eql) {
 174   upb_tabent *mainpos_e;
 175   upb_tabent *our_e;
 176
 177   UPB_ASSERT(findentry(t, key, hash, eql) == NULL);
 178   UPB_ASSERT_DEBUGVAR(val.ctype == t->ctype);
 179
 180   t->count++;
 181   mainpos_e = getentry_mutable(t, hash);
 182   our_e = mainpos_e;
 183
 184   if (upb_tabent_isempty(mainpos_e)) {
 185     /* Our main position is empty; use it. */
 186     our_e->next = NULL;
 187   } else {
 188     /* Collision. */
 189     upb_tabent *new_e = emptyent(t);
 190     /* Head of collider's chain. */
 191     upb_tabent *chain = getentry_mutable(t, hashfunc(mainpos_e->key));
 192     if (chain == mainpos_e) {
 193       /* Existing ent is in its main posisiton (it has the same hash as us, and
 194        * is the head of our chain).  Insert to new ent and append to this chain. */
 195       new_e->next = mainpos_e->next;
 196       mainpos_e->next = new_e;
 197       our_e = new_e;
 198     } else {
 199       /* Existing ent is not in its main position (it is a node in some other
 200        * chain).  This implies that no existing ent in the table has our hash.
 201        * Evict it (updating its chain) and use its ent for head of our chain. */
 202       *new_e = *mainpos_e;  /* copies next. */
 203       while (chain->next != mainpos_e) {
 204         chain = (upb_tabent*)chain->next;
 205         UPB_ASSERT(chain);
 206       }
 207       chain->next = new_e;
 208       our_e = mainpos_e;
 209       our_e->next = NULL;
 210     }
 211   }
 212   our_e->key = tabkey;
 213   our_e->val.val = val.val;
 214   UPB_ASSERT(findentry(t, key, hash, eql) == our_e);
 215 }
 216
 217 static bool rm(upb_table *t, lookupkey_t key, upb_value *val,
 218                upb_tabkey *removed, uint32_t hash, eqlfunc_t *eql) {
 219   upb_tabent *chain = getentry_mutable(t, hash);
 220   if (upb_tabent_isempty(chain)) return false;
 221   if (eql(chain->key, key)) {
 222     /* Element to remove is at the head of its chain. */
 223     t->count--;
 224     if (val) _upb_value_setval(val, chain->val.val, t->ctype);
 225     if (removed) *removed = chain->key;
 226     if (chain->next) {
 227       upb_tabent *move = (upb_tabent*)chain->next;
 228       *chain = *move;
 229       move->key = 0;  /* Make the slot empty. */
 230     } else {
 231       chain->key = 0;  /* Make the slot empty. */
 232     }
 233     return true;
 234   } else {
 235     /* Element to remove is either in a non-head position or not in the
 236      * table. */
 237     while (chain->next && !eql(chain->next->key, key)) {
 238       chain = (upb_tabent*)chain->next;
 239     }
 240     if (chain->next) {
 241       /* Found element to remove. */
 242       upb_tabent *rm = (upb_tabent*)chain->next;
 243       t->count--;
 244       if (val) _upb_value_setval(val, chain->next->val.val, t->ctype);
 245       if (removed) *removed = rm->key;
 246       rm->key = 0;  /* Make the slot empty. */
 247       chain->next = rm->next;
 248       return true;
 249     } else {
 250       /* Element to remove is not in the table. */
 251       return false;
 252     }
 253   }
 254 }
 255
 256 static size_t next(const upb_table *t, size_t i) {
 257   do {
 258     if (++i >= upb_table_size(t))
 259       return SIZE_MAX;
 260   } while(upb_tabent_isempty(&t->entries[i]));
 261
 262   return i;
 263 }
 264
 265 static size_t begin(const upb_table *t) {
 266   return next(t, -1);
 267 }
 268
 269
 270 /* upb_strtable ***************************************************************/
 271
 272 /* A simple "subclass" of upb_table that only adds a hash function for strings. */
 273
 274 static upb_tabkey strcopy(lookupkey_t k2, upb_alloc *a) {
 275   uint32_t len = (uint32_t) k2.str.len;
 276   char *str = upb_malloc(a, k2.str.len + sizeof(uint32_t) + 1);
 277   if (str == NULL) return 0;
 278   memcpy(str, &len, sizeof(uint32_t));
 279   memcpy(str + sizeof(uint32_t), k2.str.str, k2.str.len + 1);
 280   return (uintptr_t)str;
 281 }
 282
 283 static uint32_t strhash(upb_tabkey key) {
 284   uint32_t len;
 285   char *str = upb_tabstr(key, &len);
 286   return upb_murmur_hash2(str, len, 0);
 287 }
 288
 289 static bool streql(upb_tabkey k1, lookupkey_t k2) {
 290   uint32_t len;
 291   char *str = upb_tabstr(k1, &len);
 292   return len == k2.str.len && memcmp(str, k2.str.str, len) == 0;
 293 }
 294
 295 bool upb_strtable_init2(upb_strtable *t, upb_ctype_t ctype, upb_alloc *a) {
 296   return init(&t->t, ctype, 2, a);
 297 }
 298
 299 void upb_strtable_uninit2(upb_strtable *t, upb_alloc *a) {
 300   size_t i;
 301   for (i = 0; i < upb_table_size(&t->t); i++)
 302     upb_free(a, (void*)t->t.entries[i].key);
 303   uninit(&t->t, a);
 304 }
 305
 306 bool upb_strtable_resize(upb_strtable *t, size_t size_lg2, upb_alloc *a) {
 307   upb_strtable new_table;
 308   upb_strtable_iter i;
 309
 310   upb_check_alloc(&t->t, a);
 311
 312   if (!init(&new_table.t, t->t.ctype, size_lg2, a))
 313     return false;
 314   upb_strtable_begin(&i, t);
 315   for ( ; !upb_strtable_done(&i); upb_strtable_next(&i)) {
 316     upb_strtable_insert3(
 317         &new_table,
 318         upb_strtable_iter_key(&i),
 319         upb_strtable_iter_keylength(&i),
 320         upb_strtable_iter_value(&i),
 321         a);
 322   }
 323   upb_strtable_uninit2(t, a);
 324   *t = new_table;
 325   return true;
 326 }
 327
 328 bool upb_strtable_insert3(upb_strtable *t, const char *k, size_t len,
 329                           upb_value v, upb_alloc *a) {
 330   lookupkey_t key;
 331   upb_tabkey tabkey;
 332   uint32_t hash;
 333
 334   upb_check_alloc(&t->t, a);
 335
 336   if (isfull(&t->t)) {
 337     /* Need to resize.  New table of double the size, add old elements to it. */
 338     if (!upb_strtable_resize(t, t->t.size_lg2 + 1, a)) {
 339       return false;
 340     }
 341   }
 342
 343   key = strkey2(k, len);
 344   tabkey = strcopy(key, a);
 345   if (tabkey == 0) return false;
 346
 347   hash = upb_murmur_hash2(key.str.str, key.str.len, 0);
 348   insert(&t->t, key, tabkey, v, hash, &strhash, &streql);
 349   return true;
 350 }
 351
 352 bool upb_strtable_lookup2(const upb_strtable *t, const char *key, size_t len,
 353                           upb_value *v) {
 354   uint32_t hash = upb_murmur_hash2(key, len, 0);
 355   return lookup(&t->t, strkey2(key, len), v, hash, &streql);
 356 }
 357
 358 bool upb_strtable_remove3(upb_strtable *t, const char *key, size_t len,
 359                          upb_value *val, upb_alloc *alloc) {
 360   uint32_t hash = upb_murmur_hash2(key, len, 0);
 361   upb_tabkey tabkey;
 362   if (rm(&t->t, strkey2(key, len), val, &tabkey, hash, &streql)) {
 363     upb_free(alloc, (void*)tabkey);
 364     return true;
 365   } else {
 366     return false;
 367   }
 368 }
 369
 370 /* Iteration */
 371
 372 static const upb_tabent *str_tabent(const upb_strtable_iter *i) {
 373   return &i->t->t.entries[i->index];
 374 }
 375
 376 void upb_strtable_begin(upb_strtable_iter *i, const upb_strtable *t) {
 377   i->t = t;
 378   i->index = begin(&t->t);
 379 }
 380
 381 void upb_strtable_next(upb_strtable_iter *i) {
 382   i->index = next(&i->t->t, i->index);
 383 }
 384
 385 bool upb_strtable_done(const upb_strtable_iter *i) {
 386   if (!i->t) return true;
 387   return i->index >= upb_table_size(&i->t->t) ||
 388          upb_tabent_isempty(str_tabent(i));
 389 }
 390
 391 const char *upb_strtable_iter_key(const upb_strtable_iter *i) {
 392   UPB_ASSERT(!upb_strtable_done(i));
 393   return upb_tabstr(str_tabent(i)->key, NULL);
 394 }
 395
 396 size_t upb_strtable_iter_keylength(const upb_strtable_iter *i) {
 397   uint32_t len;
 398   UPB_ASSERT(!upb_strtable_done(i));
 399   upb_tabstr(str_tabent(i)->key, &len);
 400   return len;
 401 }
 402
 403 upb_value upb_strtable_iter_value(const upb_strtable_iter *i) {
 404   UPB_ASSERT(!upb_strtable_done(i));
 405   return _upb_value_val(str_tabent(i)->val.val, i->t->t.ctype);
 406 }
 407
 408 void upb_strtable_iter_setdone(upb_strtable_iter *i) {
 409   i->t = NULL;
 410   i->index = SIZE_MAX;
 411 }
 412
 413 bool upb_strtable_iter_isequal(const upb_strtable_iter *i1,
 414                                const upb_strtable_iter *i2) {
 415   if (upb_strtable_done(i1) && upb_strtable_done(i2))
 416     return true;
 417   return i1->t == i2->t && i1->index == i2->index;
 418 }
 419
 420
 421 /* upb_inttable ***************************************************************/
 422
 423 /* For inttables we use a hybrid structure where small keys are kept in an
 424  * array and large keys are put in the hash table. */
 425
 426 static uint32_t inthash(upb_tabkey key) { return upb_inthash(key); }
 427
 428 static bool inteql(upb_tabkey k1, lookupkey_t k2) {
 429   return k1 == k2.num;
 430 }
 431
 432 static upb_tabval *mutable_array(upb_inttable *t) {
 433   return (upb_tabval*)t->array;
 434 }
 435
 436 static upb_tabval *inttable_val(upb_inttable *t, uintptr_t key) {
 437   if (key < t->array_size) {
 438     return upb_arrhas(t->array[key]) ? &(mutable_array(t)[key]) : NULL;
 439   } else {
 440     upb_tabent *e =
 441         findentry_mutable(&t->t, intkey(key), upb_inthash(key), &inteql);
 442     return e ? &e->val : NULL;
 443   }
 444 }
 445
 446 static const upb_tabval *inttable_val_const(const upb_inttable *t,
 447                                             uintptr_t key) {
 448   return inttable_val((upb_inttable*)t, key);
 449 }
 450
 451 size_t upb_inttable_count(const upb_inttable *t) {
 452   return t->t.count + t->array_count;
 453 }
 454
 455 static void check(upb_inttable *t) {
 456   UPB_UNUSED(t);
 457 #if defined(UPB_DEBUG_TABLE) && !defined(NDEBUG)
 458   {
 459     /* This check is very expensive (makes inserts/deletes O(N)). */
 460     size_t count = 0;
 461     upb_inttable_iter i;
 462     upb_inttable_begin(&i, t);
 463     for(; !upb_inttable_done(&i); upb_inttable_next(&i), count++) {
 464       UPB_ASSERT(upb_inttable_lookup(t, upb_inttable_iter_key(&i), NULL));
 465     }
 466     UPB_ASSERT(count == upb_inttable_count(t));
 467   }
 468 #endif
 469 }
 470
 471 bool upb_inttable_sizedinit(upb_inttable *t, upb_ctype_t ctype,
 472                             size_t asize, int hsize_lg2, upb_alloc *a) {
 473   size_t array_bytes;
 474
 475   if (!init(&t->t, ctype, hsize_lg2, a)) return false;
 476   /* Always make the array part at least 1 long, so that we know key 0
 477    * won't be in the hash part, which simplifies things. */
 478   t->array_size = UPB_MAX(1, asize);
 479   t->array_count = 0;
 480   array_bytes = t->array_size * sizeof(upb_value);
 481   t->array = upb_malloc(a, array_bytes);
 482   if (!t->array) {
 483     uninit(&t->t, a);
 484     return false;
 485   }
 486   memset(mutable_array(t), 0xff, array_bytes);
 487   check(t);
 488   return true;
 489 }
 490
 491 bool upb_inttable_init2(upb_inttable *t, upb_ctype_t ctype, upb_alloc *a) {
 492   return upb_inttable_sizedinit(t, ctype, 0, 4, a);
 493 }
 494
 495 void upb_inttable_uninit2(upb_inttable *t, upb_alloc *a) {
 496   uninit(&t->t, a);
 497   upb_free(a, mutable_array(t));
 498 }
 499
 500 bool upb_inttable_insert2(upb_inttable *t, uintptr_t key, upb_value val,
 501                           upb_alloc *a) {
 502   upb_tabval tabval;
 503   tabval.val = val.val;
 504   UPB_ASSERT(upb_arrhas(tabval));  /* This will reject (uint64_t)-1.  Fix this. */
 505
 506   upb_check_alloc(&t->t, a);
 507
 508   if (key < t->array_size) {
 509     UPB_ASSERT(!upb_arrhas(t->array[key]));
 510     t->array_count++;
 511     mutable_array(t)[key].val = val.val;
 512   } else {
 513     if (isfull(&t->t)) {
 514       /* Need to resize the hash part, but we re-use the array part. */
 515       size_t i;
 516       upb_table new_table;
 517
 518       if (!init(&new_table, t->t.ctype, t->t.size_lg2 + 1, a)) {
 519         return false;
 520       }
 521
 522       for (i = begin(&t->t); i < upb_table_size(&t->t); i = next(&t->t, i)) {
 523         const upb_tabent *e = &t->t.entries[i];
 524         uint32_t hash;
 525         upb_value v;
 526
 527         _upb_value_setval(&v, e->val.val, t->t.ctype);
 528         hash = upb_inthash(e->key);
 529         insert(&new_table, intkey(e->key), e->key, v, hash, &inthash, &inteql);
 530       }
 531
 532       UPB_ASSERT(t->t.count == new_table.count);
 533
 534       uninit(&t->t, a);
 535       t->t = new_table;
 536     }
 537     insert(&t->t, intkey(key), key, val, upb_inthash(key), &inthash, &inteql);
 538   }
 539   check(t);
 540   return true;
 541 }
 542
 543 bool upb_inttable_lookup(const upb_inttable *t, uintptr_t key, upb_value *v) {
 544   const upb_tabval *table_v = inttable_val_const(t, key);
 545   if (!table_v) return false;
 546   if (v) _upb_value_setval(v, table_v->val, t->t.ctype);
 547   return true;
 548 }
 549
 550 bool upb_inttable_replace(upb_inttable *t, uintptr_t key, upb_value val) {
 551   upb_tabval *table_v = inttable_val(t, key);
 552   if (!table_v) return false;
 553   table_v->val = val.val;
 554   return true;
 555 }
 556
 557 bool upb_inttable_remove(upb_inttable *t, uintptr_t key, upb_value *val) {
 558   bool success;
 559   if (key < t->array_size) {
 560     if (upb_arrhas(t->array[key])) {
 561       upb_tabval empty = UPB_TABVALUE_EMPTY_INIT;
 562       t->array_count--;
 563       if (val) {
 564         _upb_value_setval(val, t->array[key].val, t->t.ctype);
 565       }
 566       mutable_array(t)[key] = empty;
 567       success = true;
 568     } else {
 569       success = false;
 570     }
 571   } else {
 572     success = rm(&t->t, intkey(key), val, NULL, upb_inthash(key), &inteql);
 573   }
 574   check(t);
 575   return success;
 576 }
 577
 578 bool upb_inttable_push2(upb_inttable *t, upb_value val, upb_alloc *a) {
 579   upb_check_alloc(&t->t, a);
 580   return upb_inttable_insert2(t, upb_inttable_count(t), val, a);
 581 }
 582
 583 upb_value upb_inttable_pop(upb_inttable *t) {
 584   upb_value val;
 585   bool ok = upb_inttable_remove(t, upb_inttable_count(t) - 1, &val);
 586   UPB_ASSERT(ok);
 587   return val;
 588 }
 589
 590 bool upb_inttable_insertptr2(upb_inttable *t, const void *key, upb_value val,
 591                              upb_alloc *a) {
 592   upb_check_alloc(&t->t, a);
 593   return upb_inttable_insert2(t, (uintptr_t)key, val, a);
 594 }
 595
 596 bool upb_inttable_lookupptr(const upb_inttable *t, const void *key,
 597                             upb_value *v) {
 598   return upb_inttable_lookup(t, (uintptr_t)key, v);
 599 }
 600
 601 bool upb_inttable_removeptr(upb_inttable *t, const void *key, upb_value *val) {
 602   return upb_inttable_remove(t, (uintptr_t)key, val);
 603 }
 604
 605 void upb_inttable_compact2(upb_inttable *t, upb_alloc *a) {
 606   /* A power-of-two histogram of the table keys. */
 607   size_t counts[UPB_MAXARRSIZE + 1] = {0};
 608
 609   /* The max key in each bucket. */
 610   uintptr_t max[UPB_MAXARRSIZE + 1] = {0};
 611
 612   upb_inttable_iter i;
 613   size_t arr_count;
 614   int size_lg2;
 615   upb_inttable new_t;
 616
 617   upb_check_alloc(&t->t, a);
 618
 619   upb_inttable_begin(&i, t);
 620   for (; !upb_inttable_done(&i); upb_inttable_next(&i)) {
 621     uintptr_t key = upb_inttable_iter_key(&i);
 622     int bucket = log2ceil(key);
 623     max[bucket] = UPB_MAX(max[bucket], key);
 624     counts[bucket]++;
 625   }
 626
 627   /* Find the largest power of two that satisfies the MIN_DENSITY
 628    * definition (while actually having some keys). */
 629   arr_count = upb_inttable_count(t);
 630
 631   for (size_lg2 = ARRAY_SIZE(counts) - 1; size_lg2 > 0; size_lg2--) {
 632     if (counts[size_lg2] == 0) {
 633       /* We can halve again without losing any entries. */
 634       continue;
 635     } else if (arr_count >= (1 << size_lg2) * MIN_DENSITY) {
 636       break;
 637     }
 638
 639     arr_count -= counts[size_lg2];
 640   }
 641
 642   UPB_ASSERT(arr_count <= upb_inttable_count(t));
 643
 644   {
 645     /* Insert all elements into new, perfectly-sized table. */
 646     size_t arr_size = max[size_lg2] + 1;  /* +1 so arr[max] will fit. */
 647     size_t hash_count = upb_inttable_count(t) - arr_count;
 648     size_t hash_size = hash_count ? (hash_count / MAX_LOAD) + 1 : 0;
 649     int hashsize_lg2 = log2ceil(hash_size);
 650
 651     upb_inttable_sizedinit(&new_t, t->t.ctype, arr_size, hashsize_lg2, a);
 652     upb_inttable_begin(&i, t);
 653     for (; !upb_inttable_done(&i); upb_inttable_next(&i)) {
 654       uintptr_t k = upb_inttable_iter_key(&i);
 655       upb_inttable_insert2(&new_t, k, upb_inttable_iter_value(&i), a);
 656     }
 657     UPB_ASSERT(new_t.array_size == arr_size);
 658     UPB_ASSERT(new_t.t.size_lg2 == hashsize_lg2);
 659   }
 660   upb_inttable_uninit2(t, a);
 661   *t = new_t;
 662 }
 663
 664 /* Iteration. */
 665
 666 static const upb_tabent *int_tabent(const upb_inttable_iter *i) {
 667   UPB_ASSERT(!i->array_part);
 668   return &i->t->t.entries[i->index];
 669 }
 670
 671 static upb_tabval int_arrent(const upb_inttable_iter *i) {
 672   UPB_ASSERT(i->array_part);
 673   return i->t->array[i->index];
 674 }
 675
 676 void upb_inttable_begin(upb_inttable_iter *i, const upb_inttable *t) {
 677   i->t = t;
 678   i->index = -1;
 679   i->array_part = true;
 680   upb_inttable_next(i);
 681 }
 682
 683 void upb_inttable_next(upb_inttable_iter *iter) {
 684   const upb_inttable *t = iter->t;
 685   if (iter->array_part) {
 686     while (++iter->index < t->array_size) {
 687       if (upb_arrhas(int_arrent(iter))) {
 688         return;
 689       }
 690     }
 691     iter->array_part = false;
 692     iter->index = begin(&t->t);
 693   } else {
 694     iter->index = next(&t->t, iter->index);
 695   }
 696 }
 697
 698 bool upb_inttable_done(const upb_inttable_iter *i) {
 699   if (!i->t) return true;
 700   if (i->array_part) {
 701     return i->index >= i->t->array_size ||
 702            !upb_arrhas(int_arrent(i));
 703   } else {
 704     return i->index >= upb_table_size(&i->t->t) ||
 705            upb_tabent_isempty(int_tabent(i));
 706   }
 707 }
 708
 709 uintptr_t upb_inttable_iter_key(const upb_inttable_iter *i) {
 710   UPB_ASSERT(!upb_inttable_done(i));
 711   return i->array_part ? i->index : int_tabent(i)->key;
 712 }
 713
 714 upb_value upb_inttable_iter_value(const upb_inttable_iter *i) {
 715   UPB_ASSERT(!upb_inttable_done(i));
 716   return _upb_value_val(
 717       i->array_part ? i->t->array[i->index].val : int_tabent(i)->val.val,
 718       i->t->t.ctype);
 719 }
 720
 721 void upb_inttable_iter_setdone(upb_inttable_iter *i) {
 722   i->t = NULL;
 723   i->index = SIZE_MAX;
 724   i->array_part = false;
 725 }
 726
 727 bool upb_inttable_iter_isequal(const upb_inttable_iter *i1,
 728                                           const upb_inttable_iter *i2) {
 729   if (upb_inttable_done(i1) && upb_inttable_done(i2))
 730     return true;
 731   return i1->t == i2->t && i1->index == i2->index &&
 732          i1->array_part == i2->array_part;
 733 }
 734
 735 #if defined(UPB_UNALIGNED_READS_OK) || defined(__s390x__)
 736 /* -----------------------------------------------------------------------------
 737  * MurmurHash2, by Austin Appleby (released as public domain).
 738  * Reformatted and C99-ified by Joshua Haberman.
 739  * Note - This code makes a few assumptions about how your machine behaves -
 740  *   1. We can read a 4-byte value from any address without crashing
 741  *   2. sizeof(int) == 4 (in upb this limitation is removed by using uint32_t
 742  * And it has a few limitations -
 743  *   1. It will not work incrementally.
 744  *   2. It will not produce the same results on little-endian and big-endian
 745  *      machines. */
 746 uint32_t upb_murmur_hash2(const void *key, size_t len, uint32_t seed) {
 747   /* 'm' and 'r' are mixing constants generated offline.
 748    * They're not really 'magic', they just happen to work well. */
 749   const uint32_t m = 0x5bd1e995;
 750   const int32_t r = 24;
 751
 752   /* Initialize the hash to a 'random' value */
 753   uint32_t h = seed ^ len;
 754
 755   /* Mix 4 bytes at a time into the hash */
 756   const uint8_t * data = (const uint8_t *)key;
 757   while(len >= 4) {
 758     uint32_t k = *(uint32_t *)data;
 759
 760     k *= m;
 761     k ^= k >> r;
 762     k *= m;
 763
 764     h *= m;
 765     h ^= k;
 766
 767     data += 4;
 768     len -= 4;
 769   }
 770
 771   /* Handle the last few bytes of the input array */
 772   switch(len) {
 773     case 3: h ^= data[2] << 16;
 774     case 2: h ^= data[1] << 8;
 775     case 1: h ^= data[0]; h *= m;
 776   };
 777
 778   /* Do a few final mixes of the hash to ensure the last few
 779    * bytes are well-incorporated. */
 780   h ^= h >> 13;
 781   h *= m;
 782   h ^= h >> 15;
 783
 784   return h;
 785 }
 786
 787 #else /* !UPB_UNALIGNED_READS_OK */
 788
 789 /* -----------------------------------------------------------------------------
 790  * MurmurHashAligned2, by Austin Appleby
 791  * Same algorithm as MurmurHash2, but only does aligned reads - should be safer
 792  * on certain platforms.
 793  * Performance will be lower than MurmurHash2 */
 794
 795 #define MIX(h,k,m) { k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; }
 796
 797 uint32_t upb_murmur_hash2(const void * key, size_t len, uint32_t seed) {
 798   const uint32_t m = 0x5bd1e995;
 799   const int32_t r = 24;
 800   const uint8_t * data = (const uint8_t *)key;
 801   uint32_t h = (uint32_t)(seed ^ len);
 802   uint8_t align = (uintptr_t)data & 3;
 803
 804   if(align && (len >= 4)) {
 805     /* Pre-load the temp registers */
 806     uint32_t t = 0, d = 0;
 807     int32_t sl;
 808     int32_t sr;
 809
 810     switch(align) {
 811       case 1: t |= data[2] << 16;
 812       case 2: t |= data[1] << 8;
 813       case 3: t |= data[0];
 814     }
 815
 816     t <<= (8 * align);
 817
 818     data += 4-align;
 819     len -= 4-align;
 820
 821     sl = 8 * (4-align);
 822     sr = 8 * align;
 823
 824     /* Mix */
 825
 826     while(len >= 4) {
 827       uint32_t k;
 828
 829       d = *(uint32_t *)data;
 830       t = (t >> sr) | (d << sl);
 831
 832       k = t;
 833
 834       MIX(h,k,m);
 835
 836       t = d;
 837
 838       data += 4;
 839       len -= 4;
 840     }
 841
 842     /* Handle leftover data in temp registers */
 843
 844     d = 0;
 845
 846     if(len >= align) {
 847       uint32_t k;
 848
 849       switch(align) {
 850         case 3: d |= data[2] << 16;
 851         case 2: d |= data[1] << 8;
 852         case 1: d |= data[0];
 853       }
 854
 855       k = (t >> sr) | (d << sl);
 856       MIX(h,k,m);
 857
 858       data += align;
 859       len -= align;
 860
 861       /* ----------
 862        * Handle tail bytes */
 863
 864       switch(len) {
 865         case 3: h ^= data[2] << 16;
 866         case 2: h ^= data[1] << 8;
 867         case 1: h ^= data[0]; h *= m;
 868       };
 869     } else {
 870       switch(len) {
 871         case 3: d |= data[2] << 16;
 872         case 2: d |= data[1] << 8;
 873         case 1: d |= data[0];
 874         case 0: h ^= (t >> sr) | (d << sl); h *= m;
 875       }
 876     }
 877
 878     h ^= h >> 13;
 879     h *= m;
 880     h ^= h >> 15;
 881
 882     return h;
 883   } else {
 884     while(len >= 4) {
 885       uint32_t k = *(uint32_t *)data;
 886
 887       MIX(h,k,m);
 888
 889       data += 4;
 890       len -= 4;
 891     }
 892
 893     /* ----------
 894      * Handle tail bytes */
 895
 896     switch(len) {
 897       case 3: h ^= data[2] << 16;
 898       case 2: h ^= data[1] << 8;
 899       case 1: h ^= data[0]; h *= m;
 900     };
 901
 902     h ^= h >> 13;
 903     h *= m;
 904     h ^= h >> 15;
 905
 906     return h;
 907   }
 908 }
 909 #undef MIX
 910
 911 #endif /* UPB_UNALIGNED_READS_OK */