deps: update nghttp3

Signed-off-by: James M Snell <jasnell@gmail.com>

PR-URL: https://github.com/nodejs/node/pull/34752
Reviewed-By: Jiawen Geng <technicalcute@gmail.com>
Reviewed-By: Anna Henningsen <anna@addaleax.net>

11 files changed, 308 insertions, 117 deletions

diff --git a/deps/nghttp3/lib/nghttp3_conn.c b/deps/nghttp3/lib/nghttp3_conn.c
index c3c1fb01a31..3d10f393bf0 100644
--- a/deps/nghttp3/lib/nghttp3_conn.c
+++ b/deps/nghttp3/lib/nghttp3_conn.c
@@ -2351,12 +2351,13 @@ int nghttp3_conn_create_stream(nghttp3_conn *conn, nghttp3_stream **pstream,
 
 int nghttp3_conn_create_push_promise(nghttp3_conn *conn,
                                      nghttp3_push_promise **ppp,
-                                     int64_t push_id, nghttp3_tnode *parent) {
+                                     int64_t push_id,
+                                     nghttp3_tnode *assoc_tnode) {
   nghttp3_push_promise *pp;
   int rv;
 
-  rv =
-      nghttp3_push_promise_new(&pp, push_id, conn->next_seq, parent, conn->mem);
+  rv = nghttp3_push_promise_new(&pp, push_id, conn->next_seq, assoc_tnode,
+                                conn->mem);
   if (rv != 0) {
     return rv;
   }
@@ -3204,7 +3205,7 @@ void nghttp3_conn_settings_default(nghttp3_conn_settings *settings) {
 }
 
 int nghttp3_push_promise_new(nghttp3_push_promise **ppp, int64_t push_id,
-                             uint64_t seq, nghttp3_tnode *parent,
+                             uint64_t seq, nghttp3_tnode *assoc_tnode,
                              const nghttp3_mem *mem) {
   nghttp3_push_promise *pp;
   nghttp3_node_id nid;
@@ -3223,10 +3224,10 @@ int nghttp3_push_promise_new(nghttp3_push_promise **ppp, int64_t push_id,
   pp->http.status_code = -1;
   pp->http.content_length = -1;
 
-  if (parent) {
-    assert(parent->nid.type == NGHTTP3_NODE_ID_TYPE_STREAM);
+  if (assoc_tnode) {
+    assert(assoc_tnode->nid.type == NGHTTP3_NODE_ID_TYPE_STREAM);
 
-    pp->stream_id = parent->nid.id;
+    pp->stream_id = assoc_tnode->nid.id;
     pp->flags |= NGHTTP3_PUSH_PROMISE_FLAG_BOUND;
   } else {
     pp->stream_id = -1;
diff --git a/deps/nghttp3/lib/nghttp3_conn.h b/deps/nghttp3/lib/nghttp3_conn.h
index 81f7a6e22c2..720b6102426 100644
--- a/deps/nghttp3/lib/nghttp3_conn.h
+++ b/deps/nghttp3/lib/nghttp3_conn.h
@@ -180,7 +180,8 @@ int nghttp3_conn_create_stream(nghttp3_conn *conn, nghttp3_stream **pstream,
 
 int nghttp3_conn_create_push_promise(nghttp3_conn *conn,
                                      nghttp3_push_promise **ppp,
-                                     int64_t push_id, nghttp3_tnode *parent);
+                                     int64_t push_id,
+                                     nghttp3_tnode *assoc_tnode);
 
 nghttp3_ssize nghttp3_conn_read_bidi(nghttp3_conn *conn, size_t *pnproc,
                                      nghttp3_stream *stream, const uint8_t *src,
@@ -254,7 +255,7 @@ void nghttp3_conn_unschedule_stream(nghttp3_conn *conn, nghttp3_stream *stream);
 nghttp3_stream *nghttp3_conn_get_next_tx_stream(nghttp3_conn *conn);
 
 int nghttp3_push_promise_new(nghttp3_push_promise **ppp, int64_t push_id,
-                             uint64_t seq, nghttp3_tnode *parent,
+                             uint64_t seq, nghttp3_tnode *assoc_tnode,
                              const nghttp3_mem *mem);
 
 void nghttp3_push_promise_del(nghttp3_push_promise *pp, const nghttp3_mem *mem);
diff --git a/deps/nghttp3/lib/nghttp3_conv.h b/deps/nghttp3/lib/nghttp3_conv.h
index 309332defed..6fae9fc9684 100644
--- a/deps/nghttp3/lib/nghttp3_conv.h
+++ b/deps/nghttp3/lib/nghttp3_conv.h
@@ -38,6 +38,10 @@
 #  include <netinet/in.h>
 #endif /* HAVE_NETINET_IN_H */
 
+#ifdef HAVE_BYTESWAP_H
+#  include <byteswap.h>
+#endif /* HAVE_BYTESWAP_H */
+
 #ifdef HAVE_ENDIAN_H
 #  include <endian.h>
 #endif /* HAVE_ENDIAN_H */
@@ -48,15 +52,25 @@
 
 #include <nghttp3/nghttp3.h>
 
+#if defined HAVE_BSWAP_64 || HAVE_DECL_BSWAP_64
+#  define nghttp3_bswap64 bswap_64
+#else /* !HAVE_BSWAP_64 */
+#  define nghttp3_bswap64(N)                                                   \
+    ((uint64_t)(ntohl((uint32_t)(N))) << 32 | ntohl((uint32_t)((N) >> 32)))
+#endif /* !HAVE_BSWAP_64 */
+
 #if defined HAVE_BE64TOH || HAVE_DECL_BE64TOH
 #  define nghttp3_ntohl64(N) be64toh(N)
 #  define nghttp3_htonl64(N) htobe64(N)
 #else /* !HAVE_BE64TOH */
-#  define nghttp3_bswap64(N)                                                   \
-    ((uint64_t)(ntohl((uint32_t)(N))) << 32 | ntohl((uint32_t)((N) >> 32)))
-#  define nghttp3_ntohl64(N) nghttp3_bswap64(N)
-#  define nghttp3_htonl64(N) nghttp3_bswap64(N)
-#endif /* !HAVE_BE64TOH */
+#  if defined WORDS_BIGENDIAN
+#    define nghttp3_ntohl64(N) (N)
+#    define nghttp3_htonl64(N) (N)
+#  else /* !WORDS_BIGENDIAN */
+#    define nghttp3_ntohl64(N) nghttp3_bswap64(N)
+#    define nghttp3_htonl64(N) nghttp3_bswap64(N)
+#  endif /* !WORDS_BIGENDIAN */
+#endif   /* !HAVE_BE64TOH */
 
 #if defined(WIN32)
 /* Windows requires ws2_32 library for ntonl family of functions.  We
diff --git a/deps/nghttp3/lib/nghttp3_ksl.c b/deps/nghttp3/lib/nghttp3_ksl.c
index 958b03973c3..6a0f7c1de57 100644
--- a/deps/nghttp3/lib/nghttp3_ksl.c
+++ b/deps/nghttp3/lib/nghttp3_ksl.c
@@ -281,6 +281,13 @@ int nghttp3_ksl_insert(nghttp3_ksl *ksl, nghttp3_ksl_it *it,
     i = ksl_bsearch(ksl, blk, key, ksl->compar);
 
     if (blk->leaf) {
+      if (i < blk->n &&
+          !ksl->compar(key, nghttp3_ksl_nth_node(ksl, blk, i)->key)) {
+        if (it) {
+          *it = nghttp3_ksl_end(ksl);
+        }
+        return NGHTTP3_ERR_INVALID_ARGUMENT;
+      }
       ksl_insert_node(ksl, blk, i, key, data);
       ++ksl->n;
       if (it) {
@@ -453,8 +460,8 @@ static int key_equal(nghttp3_ksl_compar compar, const nghttp3_ksl_key *lhs,
   return !compar(lhs, rhs) && !compar(rhs, lhs);
 }
 
-void nghttp3_ksl_remove(nghttp3_ksl *ksl, nghttp3_ksl_it *it,
-                        const nghttp3_ksl_key *key) {
+int nghttp3_ksl_remove(nghttp3_ksl *ksl, nghttp3_ksl_it *it,
+                       const nghttp3_ksl_key *key) {
   nghttp3_ksl_blk *blk = ksl->head;
   nghttp3_ksl_node *node;
   size_t i;
@@ -468,10 +475,20 @@ void nghttp3_ksl_remove(nghttp3_ksl *ksl, nghttp3_ksl_it *it,
   for (;;) {
     i = ksl_bsearch(ksl, blk, key, ksl->compar);
 
-    assert(i < blk->n);
+    if (i == blk->n) {
+      if (it) {
+        *it = nghttp3_ksl_end(ksl);
+      }
+      return NGHTTP3_ERR_INVALID_ARGUMENT;
+    }
 
     if (blk->leaf) {
-      assert(i < blk->n);
+      if (ksl->compar(key, nghttp3_ksl_nth_node(ksl, blk, i)->key)) {
+        if (it) {
+          *it = nghttp3_ksl_end(ksl);
+        }
+        return NGHTTP3_ERR_INVALID_ARGUMENT;
+      }
       ksl_remove_node(ksl, blk, i);
       --ksl->n;
       if (it) {
@@ -481,7 +498,7 @@ void nghttp3_ksl_remove(nghttp3_ksl *ksl, nghttp3_ksl_it *it,
           nghttp3_ksl_it_init(it, ksl, blk, i);
         }
       }
-      return;
+      return 0;
     }
 
     node = nghttp3_ksl_nth_node(ksl, blk, i);
diff --git a/deps/nghttp3/lib/nghttp3_ksl.h b/deps/nghttp3/lib/nghttp3_ksl.h
index 88c636b0c1d..aeb77eea575 100644
--- a/deps/nghttp3/lib/nghttp3_ksl.h
+++ b/deps/nghttp3/lib/nghttp3_ksl.h
@@ -168,27 +168,33 @@ void nghttp3_ksl_free(nghttp3_ksl *ksl);
  * successful insertion, the iterator points to the inserted node is
  * stored in |*it|.
  *
- * This function assumes that |key| does not exist in |ksl|.
- *
  * This function returns 0 if it succeeds, or one of the following
  * negative error codes:
  *
  * NGHTTP3_ERR_NOMEM
  *   Out of memory.
+ * NGHTTP3_ERR_INVALID_ARGUMENT
+ *   |key| already exists.
  */
 int nghttp3_ksl_insert(nghttp3_ksl *ksl, nghttp3_ksl_it *it,
                        const nghttp3_ksl_key *key, void *data);
 
 /*
- * nghttp3_ksl_remove removes the |key| from |ksl|.  It assumes such
- * the key is included in |ksl|.
+ * nghttp3_ksl_remove removes the |key| from |ksl|.
  *
  * This function assigns the iterator to |*it|, which points to the
  * node which is located at the right next of the removed node if |it|
- * is not NULL.
+ * is not NULL.  If |key| is not found, no deletion takes place and
+ * the return value of nghttp3_ksl_end(ksl) is assigned to |*it|.
+ *
+ * This function returns 0 if it succeeds, or one of the following
+ * negative error codes:
+ *
+ * NGHTTP3_ERR_INVALID_ARGUMENT
+ *   |key| does not exist.
  */
-void nghttp3_ksl_remove(nghttp3_ksl *ksl, nghttp3_ksl_it *it,
-                        const nghttp3_ksl_key *key);
+int nghttp3_ksl_remove(nghttp3_ksl *ksl, nghttp3_ksl_it *it,
+                       const nghttp3_ksl_key *key);
 
 /*
  * nghttp3_ksl_lower_bound returns the iterator which points to the
diff --git a/deps/nghttp3/lib/nghttp3_map.c b/deps/nghttp3/lib/nghttp3_map.c
index e383d2b0b8a..e8eb811566d 100644
--- a/deps/nghttp3/lib/nghttp3_map.c
+++ b/deps/nghttp3/lib/nghttp3_map.c
@@ -27,6 +27,7 @@
 #include "nghttp3_map.h"
 
 #include <string.h>
+#include <assert.h>
 
 #include "nghttp3_conv.h"
 
@@ -36,7 +37,7 @@ int nghttp3_map_init(nghttp3_map *map, const nghttp3_mem *mem) {
   map->mem = mem;
   map->tablelen = INITIAL_TABLE_LENGTH;
   map->table =
-      nghttp3_mem_calloc(mem, map->tablelen, sizeof(nghttp3_map_entry *));
+      nghttp3_mem_calloc(mem, map->tablelen, sizeof(nghttp3_map_bucket));
   if (map->table == NULL) {
     return NGHTTP3_ERR_NOMEM;
   }
@@ -47,38 +48,82 @@ int nghttp3_map_init(nghttp3_map *map, const nghttp3_mem *mem) {
 }
 
 void nghttp3_map_free(nghttp3_map *map) {
+  size_t i;
+  nghttp3_map_bucket *bkt;
+
+  if (!map) {
+    return;
+  }
+
+  for (i = 0; i < map->tablelen; ++i) {
+    bkt = &map->table[i];
+    if (bkt->ksl) {
+      nghttp3_ksl_free(bkt->ksl);
+      nghttp3_mem_free(map->mem, bkt->ksl);
+    }
+  }
+
   nghttp3_mem_free(map->mem, map->table);
 }
 
-void nghttp3_map_each_free(const nghttp3_map *map,
+void nghttp3_map_each_free(nghttp3_map *map,
                            int (*func)(nghttp3_map_entry *entry, void *ptr),
                            void *ptr) {
   uint32_t i;
+  nghttp3_map_bucket *bkt;
+  nghttp3_ksl_it it;
+
   for (i = 0; i < map->tablelen; ++i) {
-    nghttp3_map_entry *entry;
-    for (entry = map->table[i]; entry;) {
-      nghttp3_map_entry *next = entry->next;
-      func(entry, ptr);
-      entry = next;
+    bkt = &map->table[i];
+
+    if (bkt->ptr) {
+      func(bkt->ptr, ptr);
+      bkt->ptr = NULL;
+      assert(bkt->ksl == NULL || nghttp3_ksl_len(bkt->ksl) == 0);
+      continue;
+    }
+
+    if (bkt->ksl) {
+      for (it = nghttp3_ksl_begin(bkt->ksl); !nghttp3_ksl_it_end(&it);
+           nghttp3_ksl_it_next(&it)) {
+        func(nghttp3_ksl_it_get(&it), ptr);
+      }
+
+      nghttp3_ksl_free(bkt->ksl);
+      nghttp3_mem_free(map->mem, bkt->ksl);
+      bkt->ksl = NULL;
     }
-    map->table[i] = NULL;
   }
 }
 
-int nghttp3_map_each(const nghttp3_map *map,
+int nghttp3_map_each(nghttp3_map *map,
                      int (*func)(nghttp3_map_entry *entry, void *ptr),
                      void *ptr) {
   int rv;
   uint32_t i;
+  nghttp3_map_bucket *bkt;
+  nghttp3_ksl_it it;
+
   for (i = 0; i < map->tablelen; ++i) {
-    nghttp3_map_entry *entry, *next;
-    for (entry = map->table[i]; entry;) {
-      next = entry->next;
-      rv = func(entry, ptr);
+    bkt = &map->table[i];
+
+    if (bkt->ptr) {
+      rv = func(bkt->ptr, ptr);
       if (rv != 0) {
         return rv;
       }
-      entry = next;
+      assert(bkt->ksl == NULL || nghttp3_ksl_len(bkt->ksl) == 0);
+      continue;
+    }
+
+    if (bkt->ksl) {
+      for (it = nghttp3_ksl_begin(bkt->ksl); !nghttp3_ksl_it_end(&it);
+           nghttp3_ksl_it_next(&it)) {
+        rv = func(nghttp3_ksl_it_get(&it), ptr);
+        if (rv != 0) {
+          return rv;
+        }
+      }
     }
   }
   return 0;
@@ -98,71 +143,125 @@ static uint32_t hash(key_type key, uint32_t mod) {
   p = (uint8_t *)&key;
   end = p + sizeof(key_type);
 
-  for (; p != end; ++p) {
-    h ^= *p;
-    h *= 0x01000193u;
+  for (; p != end;) {
+    h ^= *p++;
+    h += (h << 1) + (h << 4) + (h << 7) + (h << 8) + (h << 24);
   }
 
   return h & (mod - 1);
 }
 
-static int insert(nghttp3_map_entry **table, uint32_t tablelen,
-                  nghttp3_map_entry *entry) {
+static int less(const nghttp3_ksl_key *lhs, const nghttp3_ksl_key *rhs) {
+  return *(key_type *)lhs < *(key_type *)rhs;
+}
+
+static int map_insert(nghttp3_map *map, nghttp3_map_bucket *table,
+                      uint32_t tablelen, nghttp3_map_entry *entry) {
   uint32_t h = hash(entry->key, tablelen);
-  if (table[h] == NULL) {
-    table[h] = entry;
-  } else {
-    nghttp3_map_entry *p;
-    /* We won't allow duplicated key, so check it out. */
-    for (p = table[h]; p; p = p->next) {
-      if (p->key == entry->key) {
-        return NGHTTP3_ERR_INVALID_ARGUMENT;
-      }
+  nghttp3_map_bucket *bkt = &table[h];
+  const nghttp3_mem *mem = map->mem;
+  int rv;
+
+  if (bkt->ptr == NULL &&
+      (bkt->ksl == NULL || nghttp3_ksl_len(bkt->ksl) == 0)) {
+    bkt->ptr = entry;
+    return 0;
+  }
+
+  if (!bkt->ksl) {
+    bkt->ksl = nghttp3_mem_malloc(mem, sizeof(*bkt->ksl));
+    if (bkt->ksl == NULL) {
+      return NGHTTP3_ERR_NOMEM;
     }
-    entry->next = table[h];
-    table[h] = entry;
+    nghttp3_ksl_init(bkt->ksl, less, sizeof(key_type), mem);
   }
-  return 0;
+
+  if (bkt->ptr) {
+    rv = nghttp3_ksl_insert(bkt->ksl, NULL, &bkt->ptr->key, bkt->ptr);
+    if (rv != 0) {
+      return rv;
+    }
+
+    bkt->ptr = NULL;
+  }
+
+  return nghttp3_ksl_insert(bkt->ksl, NULL, &entry->key, entry);
 }
 
 /* new_tablelen must be power of 2 */
-static int resize(nghttp3_map *map, uint32_t new_tablelen) {
+static int map_resize(nghttp3_map *map, uint32_t new_tablelen) {
   uint32_t i;
-  nghttp3_map_entry **new_table;
+  nghttp3_map_bucket *new_table;
+  nghttp3_map_bucket *bkt;
+  nghttp3_ksl_it it;
+  int rv;
 
   new_table =
-      nghttp3_mem_calloc(map->mem, new_tablelen, sizeof(nghttp3_map_entry *));
+      nghttp3_mem_calloc(map->mem, new_tablelen, sizeof(nghttp3_map_bucket));
   if (new_table == NULL) {
     return NGHTTP3_ERR_NOMEM;
   }
 
   for (i = 0; i < map->tablelen; ++i) {
-    nghttp3_map_entry *entry;
-    for (entry = map->table[i]; entry;) {
-      nghttp3_map_entry *next = entry->next;
-      entry->next = NULL;
-      /* This function must succeed */
-      insert(new_table, new_tablelen, entry);
-      entry = next;
+    bkt = &map->table[i];
+
+    if (bkt->ptr) {
+      rv = map_insert(map, new_table, new_tablelen, bkt->ptr);
+      if (rv != 0) {
+        goto fail;
+      }
+      assert(bkt->ksl == NULL || nghttp3_ksl_len(bkt->ksl) == 0);
+      continue;
+    }
+
+    if (bkt->ksl) {
+      for (it = nghttp3_ksl_begin(bkt->ksl); !nghttp3_ksl_it_end(&it);
+           nghttp3_ksl_it_next(&it)) {
+        rv = map_insert(map, new_table, new_tablelen, nghttp3_ksl_it_get(&it));
+        if (rv != 0) {
+          goto fail;
+        }
+      }
+    }
+  }
+
+  for (i = 0; i < map->tablelen; ++i) {
+    bkt = &map->table[i];
+    if (bkt->ksl) {
+      nghttp3_ksl_free(bkt->ksl);
+      nghttp3_mem_free(map->mem, bkt->ksl);
     }
   }
+
   nghttp3_mem_free(map->mem, map->table);
   map->tablelen = new_tablelen;
   map->table = new_table;
 
   return 0;
+
+fail:
+  for (i = 0; i < new_tablelen; ++i) {
+    bkt = &new_table[i];
+    if (bkt->ksl) {
+      nghttp3_ksl_free(bkt->ksl);
+      nghttp3_mem_free(map->mem, bkt->ksl);
+    }
+  }
+
+  return rv;
 }
 
 int nghttp3_map_insert(nghttp3_map *map, nghttp3_map_entry *new_entry) {
   int rv;
+
   /* Load factor is 0.75 */
   if ((map->size + 1) * 4 > map->tablelen * 3) {
-    rv = resize(map, map->tablelen * 2);
+    rv = map_resize(map, map->tablelen * 2);
     if (rv != 0) {
       return rv;
     }
   }
-  rv = insert(map->table, map->tablelen, new_entry);
+  rv = map_insert(map, map->table, map->tablelen, new_entry);
   if (rv != 0) {
     return rv;
   }
@@ -170,44 +269,69 @@ int nghttp3_map_insert(nghttp3_map *map, nghttp3_map_entry *new_entry) {
   return 0;
 }
 
-nghttp3_map_entry *nghttp3_map_find(const nghttp3_map *map, key_type key) {
-  uint32_t h;
-  nghttp3_map_entry *entry;
-  h = hash(key, map->tablelen);
-  for (entry = map->table[h]; entry; entry = entry->next) {
-    if (entry->key == key) {
-      return entry;
+nghttp3_map_entry *nghttp3_map_find(nghttp3_map *map, key_type key) {
+  nghttp3_map_bucket *bkt = &map->table[hash(key, map->tablelen)];
+  nghttp3_ksl_it it;
+
+  if (bkt->ptr) {
+    if (bkt->ptr->key == key) {
+      return bkt->ptr;
     }
+    return NULL;
   }
+
+  if (bkt->ksl) {
+    it = nghttp3_ksl_lower_bound(bkt->ksl, &key);
+    if (nghttp3_ksl_it_end(&it) ||
+        *(key_type *)nghttp3_ksl_it_key(&it) != key) {
+      return NULL;
+    }
+    return nghttp3_ksl_it_get(&it);
+  }
+
   return NULL;
 }
 
 int nghttp3_map_remove(nghttp3_map *map, key_type key) {
-  uint32_t h;
-  nghttp3_map_entry **dst;
-
-  h = hash(key, map->tablelen);
+  nghttp3_map_bucket *bkt = &map->table[hash(key, map->tablelen)];
+  int rv;
 
-  for (dst = &map->table[h]; *dst; dst = &(*dst)->next) {
-    if ((*dst)->key != key) {
-      continue;
+  if (bkt->ptr) {
+    if (bkt->ptr->key == key) {
+      bkt->ptr = NULL;
+      --map->size;
+      return 0;
     }
+    return NGHTTP3_ERR_INVALID_ARGUMENT;
+  }
 
-    *dst = (*dst)->next;
+  if (bkt->ksl) {
+    rv = nghttp3_ksl_remove(bkt->ksl, NULL, &key);
+    if (rv != 0) {
+      return rv;
+    }
     --map->size;
     return 0;
   }
+
   return NGHTTP3_ERR_INVALID_ARGUMENT;
 }
 
 void nghttp3_map_clear(nghttp3_map *map) {
   uint32_t i;
+  nghttp3_map_bucket *bkt;
 
   for (i = 0; i < map->tablelen; ++i) {
-    map->table[i] = NULL;
+    bkt = &map->table[i];
+    bkt->ptr = NULL;
+    if (bkt->ksl) {
+      nghttp3_ksl_free(bkt->ksl);
+      nghttp3_mem_free(map->mem, bkt->ksl);
+      bkt->ksl = NULL;
+    }
   }
 
   map->size = 0;
 }
 
-size_t nghttp3_map_size(const nghttp3_map *map) { return map->size; }
+size_t nghttp3_map_size(nghttp3_map *map) { return map->size; }
diff --git a/deps/nghttp3/lib/nghttp3_map.h b/deps/nghttp3/lib/nghttp3_map.h
index 0b7c0d28c37..8a007119709 100644
--- a/deps/nghttp3/lib/nghttp3_map.h
+++ b/deps/nghttp3/lib/nghttp3_map.h
@@ -34,6 +34,7 @@
 #include <nghttp3/nghttp3.h>
 
 #include "nghttp3_mem.h"
+#include "nghttp3_ksl.h"
 
 /* Implementation of unordered map */
 
@@ -44,8 +45,13 @@ typedef struct nghttp3_map_entry {
   key_type key;
 } nghttp3_map_entry;
 
+typedef struct nghttp3_map_bucket {
+  nghttp3_map_entry *ptr;
+  nghttp3_ksl *ksl;
+} nghttp3_map_bucket;
+
 typedef struct {
-  nghttp3_map_entry **table;
+  nghttp3_map_bucket *table;
   const nghttp3_mem *mem;
   size_t size;
   uint32_t tablelen;
@@ -75,7 +81,7 @@ void nghttp3_map_free(nghttp3_map *map);
  * given the |entry| object. The |ptr| will be passed to the |func| as
  * send argument. The return value of the |func| will be ignored.
  */
-void nghttp3_map_each_free(const nghttp3_map *map,
+void nghttp3_map_each_free(nghttp3_map *map,
                            int (*func)(nghttp3_map_entry *entry, void *ptr),
                            void *ptr);
 
@@ -102,7 +108,7 @@ int nghttp3_map_insert(nghttp3_map *map, nghttp3_map_entry *entry);
  * Returns the entry associated by the key |key|.  If there is no such
  * entry, this function returns NULL.
  */
-nghttp3_map_entry *nghttp3_map_find(const nghttp3_map *map, key_type key);
+nghttp3_map_entry *nghttp3_map_find(nghttp3_map *map, key_type key);
 
 /*
  * Removes the entry associated by the key |key| from the |map|.  The
@@ -124,7 +130,7 @@ void nghttp3_map_clear(nghttp3_map *map);
 /*
  * Returns the number of items stored in the map |map|.
  */
-size_t nghttp3_map_size(const nghttp3_map *map);
+size_t nghttp3_map_size(nghttp3_map *map);
 
 /*
  * Applies the function |func| to each entry in the |map| with the
@@ -140,7 +146,7 @@ size_t nghttp3_map_size(const nghttp3_map *map);
  * Don't use this function to free each entry. Use
  * nghttp3_map_each_free() instead.
  */
-int nghttp3_map_each(const nghttp3_map *map,
+int nghttp3_map_each(nghttp3_map *map,
                      int (*func)(nghttp3_map_entry *entry, void *ptr),
                      void *ptr);
 
diff --git a/deps/nghttp3/lib/nghttp3_qpack.c b/deps/nghttp3/lib/nghttp3_qpack.c
index 370c3eb442b..d74e29f6fec 100644
--- a/deps/nghttp3/lib/nghttp3_qpack.c
+++ b/deps/nghttp3/lib/nghttp3_qpack.c
@@ -1043,8 +1043,10 @@ void nghttp3_qpack_encoder_shrink_dtable(nghttp3_qpack_encoder *encoder) {
 
 /*
  * qpack_encoder_add_stream_ref adds another dynamic table reference
- * to a stream denoted by |stream_id|.  |max_cnt| and |min_cnt| is the
- * maximum and minimum insert count it references respectively.
+ * to a stream denoted by |stream_id|.  |stream| must be NULL if no
+ * stream object is not found for the given stream ID.  |max_cnt| and
+ * |min_cnt| is the maximum and minimum insert count it references
+ * respectively.
  *
  * This function returns 0 if it succeeds, or one of the following
  * negative error codes:
@@ -1053,10 +1055,9 @@ void nghttp3_qpack_encoder_shrink_dtable(nghttp3_qpack_encoder *encoder) {
  *     Out of memory.
  */
 static int qpack_encoder_add_stream_ref(nghttp3_qpack_encoder *encoder,
-                                        int64_t stream_id, uint64_t max_cnt,
-                                        uint64_t min_cnt) {
-  nghttp3_qpack_stream *stream =
-      nghttp3_qpack_encoder_find_stream(encoder, stream_id);
+                                        int64_t stream_id,
+                                        nghttp3_qpack_stream *stream,
+                                        uint64_t max_cnt, uint64_t min_cnt) {
   nghttp3_qpack_header_block_ref *ref;
   const nghttp3_mem *mem = encoder->ctx.mem;
   uint64_t prev_max_cnt = 0;
@@ -1211,7 +1212,8 @@ int nghttp3_qpack_encoder_encode(nghttp3_qpack_encoder *encoder,
     return 0;
   }
 
-  rv = qpack_encoder_add_stream_ref(encoder, stream_id, max_cnt, min_cnt);
+  rv = qpack_encoder_add_stream_ref(encoder, stream_id, stream, max_cnt,
+                                    min_cnt);
   if (rv != 0) {
     goto fail;
   }
@@ -1308,19 +1310,6 @@ int nghttp3_qpack_encoder_stream_is_blocked(nghttp3_qpack_encoder *encoder,
   return stream && encoder->krcnt < nghttp3_qpack_stream_get_max_cnt(stream);
 }
 
-static uint32_t qpack_hash_name(const nghttp3_nv *nv) {
-  /* 32 bit FNV-1a: http://isthe.com/chongo/tech/comp/fnv/ */
-  uint32_t h = 2166136261u;
-  size_t i;
-
-  for (i = 0; i < nv->namelen; ++i) {
-    h ^= nv->name[i];
-    h += (h << 1) + (h << 4) + (h << 7) + (h << 8) + (h << 24);
-  }
-
-  return h;
-}
-
 /*
  * qpack_encoder_decide_indexing_mode determines and returns indexing
  * mode for header field |nv|.  |token| is a token of header field
@@ -1341,6 +1330,7 @@ qpack_encoder_decide_indexing_mode(nghttp3_qpack_encoder *encoder,
       return NGHTTP3_QPACK_INDEXING_MODE_NEVER;
     }
     break;
+  case -1:
   case NGHTTP3_QPACK_TOKEN__PATH:
   case NGHTTP3_QPACK_TOKEN_AGE:
   case NGHTTP3_QPACK_TOKEN_CONTENT_LENGTH:
@@ -1350,6 +1340,15 @@ qpack_encoder_decide_indexing_mode(nghttp3_qpack_encoder *encoder,
   case NGHTTP3_QPACK_TOKEN_LOCATION:
   case NGHTTP3_QPACK_TOKEN_SET_COOKIE:
     return NGHTTP3_QPACK_INDEXING_MODE_LITERAL;
+  case NGHTTP3_QPACK_TOKEN_HOST:
+  case NGHTTP3_QPACK_TOKEN_TE:
+  case NGHTTP3_QPACK_TOKEN__PROTOCOL:
+  case NGHTTP3_QPACK_TOKEN_PRIORITY:
+    break;
+  default:
+    if (token >= 1000) {
+      return NGHTTP3_QPACK_INDEXING_MODE_LITERAL;
+    }
   }
 
   if (table_space(nv->namelen, nv->valuelen) >
@@ -1461,7 +1460,20 @@ int nghttp3_qpack_encoder_encode_nv(nghttp3_qpack_encoder *encoder,
   if (static_entry) {
     hash = token_stable[token].hash;
   } else {
-    hash = qpack_hash_name(nv);
+    switch (token) {
+    case NGHTTP3_QPACK_TOKEN_HOST:
+      hash = 2952701295u;
+      break;
+    case NGHTTP3_QPACK_TOKEN_TE:
+      hash = 1011170994u;
+      break;
+    case NGHTTP3_QPACK_TOKEN__PROTOCOL:
+      hash = 1128642621u;
+      break;
+    case NGHTTP3_QPACK_TOKEN_PRIORITY:
+      hash = 2498028297u;
+      break;
+    }
   }
 
   indexing_mode = qpack_encoder_decide_indexing_mode(encoder, nv, token);
@@ -1474,7 +1486,8 @@ int nghttp3_qpack_encoder_encode_nv(nghttp3_qpack_encoder *encoder,
     }
   }
 
-  if (nghttp3_map_size(&encoder->streams) < NGHTTP3_QPACK_MAX_QPACK_STREAMS) {
+  if (hash &&
+      nghttp3_map_size(&encoder->streams) < NGHTTP3_QPACK_MAX_QPACK_STREAMS) {
     dres = nghttp3_qpack_encoder_lookup_dtable(encoder, nv, token, hash,
                                                indexing_mode, encoder->krcnt,
                                                allow_blocking);
@@ -2949,6 +2962,7 @@ nghttp3_ssize nghttp3_qpack_decoder_read_encoder(nghttp3_qpack_decoder *decoder,
       qpack_read_state_terminate_name(&decoder->rstate);
 
       decoder->state = NGHTTP3_QPACK_ES_STATE_CHECK_VALUE_HUFFMAN;
+      decoder->rstate.prefix = 7;
       break;
     case NGHTTP3_QPACK_ES_STATE_CHECK_VALUE_HUFFMAN:
       qpack_read_state_check_huffman(&decoder->rstate, *p);
diff --git a/deps/nghttp3/lib/nghttp3_qpack.h b/deps/nghttp3/lib/nghttp3_qpack.h
index 1a3097cae8d..ddfb2b66385 100644
--- a/deps/nghttp3/lib/nghttp3_qpack.h
+++ b/deps/nghttp3/lib/nghttp3_qpack.h
@@ -195,7 +195,7 @@ void nghttp3_qpack_read_state_free(nghttp3_qpack_read_state *rstate);
 
 void nghttp3_qpack_read_state_reset(nghttp3_qpack_read_state *rstate);
 
-#define NGHTTP3_QPACK_MAP_SIZE 128
+#define NGHTTP3_QPACK_MAP_SIZE 64
 
 typedef struct {
   nghttp3_qpack_entry *table[NGHTTP3_QPACK_MAP_SIZE];
diff --git a/deps/nghttp3/lib/nghttp3_ringbuf.c b/deps/nghttp3/lib/nghttp3_ringbuf.c
index 6eea9830da1..9ea91c81c8a 100644
--- a/deps/nghttp3/lib/nghttp3_ringbuf.c
+++ b/deps/nghttp3/lib/nghttp3_ringbuf.c
@@ -33,6 +33,16 @@
 
 #include "nghttp3_macro.h"
 
+#if defined(_MSC_VER) && defined(_M_ARM64)
+unsigned int __popcnt(unsigned int x) {
+  unsigned int c = 0;
+  for (; x; ++c) {
+    x &= x - 1;
+  }
+  return c;
+}
+#endif
+
 int nghttp3_ringbuf_init(nghttp3_ringbuf *rb, size_t nmemb, size_t size,
                          const nghttp3_mem *mem) {
   if (nmemb) {
@@ -107,8 +117,6 @@ void *nghttp3_ringbuf_get(nghttp3_ringbuf *rb, size_t offset) {
   return &rb->buf[offset * rb->size];
 }
 
-size_t nghttp3_ringbuf_len(nghttp3_ringbuf *rb) { return rb->len; }
-
 int nghttp3_ringbuf_full(nghttp3_ringbuf *rb) { return rb->len == rb->nmemb; }
 
 int nghttp3_ringbuf_reserve(nghttp3_ringbuf *rb, size_t nmemb) {
diff --git a/deps/nghttp3/lib/nghttp3_ringbuf.h b/deps/nghttp3/lib/nghttp3_ringbuf.h
index d11bb2b0318..51194bd6356 100644
--- a/deps/nghttp3/lib/nghttp3_ringbuf.h
+++ b/deps/nghttp3/lib/nghttp3_ringbuf.h
@@ -103,7 +103,7 @@ void nghttp3_ringbuf_resize(nghttp3_ringbuf *rb, size_t len);
 void *nghttp3_ringbuf_get(nghttp3_ringbuf *rb, size_t offset);
 
 /* nghttp3_ringbuf_len returns the number of elements stored. */
-size_t nghttp3_ringbuf_len(nghttp3_ringbuf *rb);
+#define nghttp3_ringbuf_len(RB) ((RB)->len)
 
 /* nghttp3_ringbuf_full returns nonzero if |rb| is full. */
 int nghttp3_ringbuf_full(nghttp3_ringbuf *rb);