1 files changed, 202 insertions, 78 deletions

diff --git a/Utilities/cmnghttp2/lib/nghttp2_map.c b/Utilities/cmnghttp2/lib/nghttp2_map.c
index 4d9f97b..e5db168 100644
--- a/Utilities/cmnghttp2/lib/nghttp2_map.c
+++ b/Utilities/cmnghttp2/lib/nghttp2_map.c
@@ -1,7 +1,8 @@
 /*
  * nghttp2 - HTTP/2 C Library
  *
- * Copyright (c) 2012 Tatsuhiro Tsujikawa
+ * Copyright (c) 2017 ngtcp2 contributors
+ * Copyright (c) 2012 nghttp2 contributors
  *
  * Permission is hereby granted, free of charge, to any person obtaining
  * a copy of this software and associated documentation files (the
@@ -25,14 +26,19 @@
 #include "nghttp2_map.h"
 
 #include <string.h>
+#include <assert.h>
+#include <stdio.h>
 
-#define INITIAL_TABLE_LENGTH 256
+#include "nghttp2_helper.h"
+
+#define NGHTTP2_INITIAL_TABLE_LENBITS 8
 
 int nghttp2_map_init(nghttp2_map *map, nghttp2_mem *mem) {
   map->mem = mem;
-  map->tablelen = INITIAL_TABLE_LENGTH;
+  map->tablelen = 1 << NGHTTP2_INITIAL_TABLE_LENBITS;
+  map->tablelenbits = NGHTTP2_INITIAL_TABLE_LENBITS;
   map->table =
-      nghttp2_mem_calloc(mem, map->tablelen, sizeof(nghttp2_map_entry *));
+      nghttp2_mem_calloc(mem, map->tablelen, sizeof(nghttp2_map_bucket));
   if (map->table == NULL) {
     return NGHTTP2_ERR_NOMEM;
   }
@@ -43,112 +49,188 @@ int nghttp2_map_init(nghttp2_map *map, nghttp2_mem *mem) {
 }
 
 void nghttp2_map_free(nghttp2_map *map) {
+  if (!map) {
+    return;
+  }
+
   nghttp2_mem_free(map->mem, map->table);
 }
 
-void nghttp2_map_each_free(nghttp2_map *map,
-                           int (*func)(nghttp2_map_entry *entry, void *ptr),
+void nghttp2_map_each_free(nghttp2_map *map, int (*func)(void *data, void *ptr),
                            void *ptr) {
   uint32_t i;
+  nghttp2_map_bucket *bkt;
+
   for (i = 0; i < map->tablelen; ++i) {
-    nghttp2_map_entry *entry;
-    for (entry = map->table[i]; entry;) {
-      nghttp2_map_entry *next = entry->next;
-      func(entry, ptr);
-      entry = next;
+    bkt = &map->table[i];
+
+    if (bkt->data == NULL) {
+      continue;
     }
-    map->table[i] = NULL;
+
+    func(bkt->data, ptr);
   }
 }
 
-int nghttp2_map_each(nghttp2_map *map,
-                     int (*func)(nghttp2_map_entry *entry, void *ptr),
+int nghttp2_map_each(nghttp2_map *map, int (*func)(void *data, void *ptr),
                      void *ptr) {
   int rv;
   uint32_t i;
+  nghttp2_map_bucket *bkt;
+
   for (i = 0; i < map->tablelen; ++i) {
-    nghttp2_map_entry *entry;
-    for (entry = map->table[i]; entry; entry = entry->next) {
-      rv = func(entry, ptr);
-      if (rv != 0) {
-        return rv;
-      }
+    bkt = &map->table[i];
+
+    if (bkt->data == NULL) {
+      continue;
+    }
+
+    rv = func(bkt->data, ptr);
+    if (rv != 0) {
+      return rv;
     }
   }
+
   return 0;
 }
 
-void nghttp2_map_entry_init(nghttp2_map_entry *entry, key_type key) {
-  entry->key = key;
-  entry->next = NULL;
+static uint32_t hash(nghttp2_map_key_type key) {
+  return (uint32_t)key * 2654435769u;
 }
 
-/* Same hash function in android HashMap source code. */
-/* The |mod| must be power of 2 */
-static uint32_t hash(int32_t key, uint32_t mod) {
-  uint32_t h = (uint32_t)key;
-  h ^= (h >> 20) ^ (h >> 12);
-  h ^= (h >> 7) ^ (h >> 4);
-  return h & (mod - 1);
+static size_t h2idx(uint32_t hash, uint32_t bits) {
+  return hash >> (32 - bits);
 }
 
-static int insert(nghttp2_map_entry **table, uint32_t tablelen,
-                  nghttp2_map_entry *entry) {
-  uint32_t h = hash(entry->key, tablelen);
-  if (table[h] == NULL) {
-    table[h] = entry;
-  } else {
-    nghttp2_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 NGHTTP2_ERR_INVALID_ARGUMENT;
-      }
+static size_t distance(uint32_t tablelen, uint32_t tablelenbits,
+                       nghttp2_map_bucket *bkt, size_t idx) {
+  return (idx - h2idx(bkt->hash, tablelenbits)) & (tablelen - 1);
+}
+
+static void map_bucket_swap(nghttp2_map_bucket *bkt, uint32_t *phash,
+                            nghttp2_map_key_type *pkey, void **pdata) {
+  uint32_t h = bkt->hash;
+  nghttp2_map_key_type key = bkt->key;
+  void *data = bkt->data;
+
+  bkt->hash = *phash;
+  bkt->key = *pkey;
+  bkt->data = *pdata;
+
+  *phash = h;
+  *pkey = key;
+  *pdata = data;
+}
+
+static void map_bucket_set_data(nghttp2_map_bucket *bkt, uint32_t hash,
+                                nghttp2_map_key_type key, void *data) {
+  bkt->hash = hash;
+  bkt->key = key;
+  bkt->data = data;
+}
+
+void nghttp2_map_print_distance(nghttp2_map *map) {
+  uint32_t i;
+  size_t idx;
+  nghttp2_map_bucket *bkt;
+
+  for (i = 0; i < map->tablelen; ++i) {
+    bkt = &map->table[i];
+
+    if (bkt->data == NULL) {
+      fprintf(stderr, "@%u <EMPTY>\n", i);
+      continue;
     }
-    entry->next = table[h];
-    table[h] = entry;
+
+    idx = h2idx(bkt->hash, map->tablelenbits);
+    fprintf(stderr, "@%u hash=%08x key=%d base=%zu distance=%zu\n", i,
+            bkt->hash, bkt->key, idx,
+            distance(map->tablelen, map->tablelenbits, bkt, idx));
+  }
+}
+
+static int insert(nghttp2_map_bucket *table, uint32_t tablelen,
+                  uint32_t tablelenbits, uint32_t hash,
+                  nghttp2_map_key_type key, void *data) {
+  size_t idx = h2idx(hash, tablelenbits);
+  size_t d = 0, dd;
+  nghttp2_map_bucket *bkt;
+
+  for (;;) {
+    bkt = &table[idx];
+
+    if (bkt->data == NULL) {
+      map_bucket_set_data(bkt, hash, key, data);
+      return 0;
+    }
+
+    dd = distance(tablelen, tablelenbits, bkt, idx);
+    if (d > dd) {
+      map_bucket_swap(bkt, &hash, &key, &data);
+      d = dd;
+    } else if (bkt->key == key) {
+      /* TODO This check is just a waste after first swap or if this
+         function is called from map_resize.  That said, there is no
+         difference with or without this conditional in performance
+         wise. */
+      return NGHTTP2_ERR_INVALID_ARGUMENT;
+    }
+
+    ++d;
+    idx = (idx + 1) & (tablelen - 1);
   }
-  return 0;
 }
 
-/* new_tablelen must be power of 2 */
-static int resize(nghttp2_map *map, uint32_t new_tablelen) {
+/* new_tablelen must be power of 2 and new_tablelen == (1 <<
+   new_tablelenbits) must hold. */
+static int map_resize(nghttp2_map *map, uint32_t new_tablelen,
+                      uint32_t new_tablelenbits) {
   uint32_t i;
-  nghttp2_map_entry **new_table;
+  nghttp2_map_bucket *new_table;
+  nghttp2_map_bucket *bkt;
+  int rv;
+  (void)rv;
 
   new_table =
-      nghttp2_mem_calloc(map->mem, new_tablelen, sizeof(nghttp2_map_entry *));
+      nghttp2_mem_calloc(map->mem, new_tablelen, sizeof(nghttp2_map_bucket));
   if (new_table == NULL) {
     return NGHTTP2_ERR_NOMEM;
   }
 
   for (i = 0; i < map->tablelen; ++i) {
-    nghttp2_map_entry *entry;
-    for (entry = map->table[i]; entry;) {
-      nghttp2_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->data == NULL) {
+      continue;
     }
+    rv = insert(new_table, new_tablelen, new_tablelenbits, bkt->hash, bkt->key,
+                bkt->data);
+
+    assert(0 == rv);
   }
+
   nghttp2_mem_free(map->mem, map->table);
   map->tablelen = new_tablelen;
+  map->tablelenbits = new_tablelenbits;
   map->table = new_table;
 
   return 0;
 }
 
-int nghttp2_map_insert(nghttp2_map *map, nghttp2_map_entry *new_entry) {
+int nghttp2_map_insert(nghttp2_map *map, nghttp2_map_key_type key, void *data) {
   int rv;
+
+  assert(data);
+
   /* 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, map->tablelenbits + 1);
     if (rv != 0) {
       return rv;
     }
   }
-  rv = insert(map->table, map->tablelen, new_entry);
+
+  rv = insert(map->table, map->tablelen, map->tablelenbits, hash(key), key,
+              data);
   if (rv != 0) {
     return rv;
   }
@@ -156,34 +238,76 @@ int nghttp2_map_insert(nghttp2_map *map, nghttp2_map_entry *new_entry) {
   return 0;
 }
 
-nghttp2_map_entry *nghttp2_map_find(nghttp2_map *map, key_type key) {
-  uint32_t h;
-  nghttp2_map_entry *entry;
-  h = hash(key, map->tablelen);
-  for (entry = map->table[h]; entry; entry = entry->next) {
-    if (entry->key == key) {
-      return entry;
+void *nghttp2_map_find(nghttp2_map *map, nghttp2_map_key_type key) {
+  uint32_t h = hash(key);
+  size_t idx = h2idx(h, map->tablelenbits);
+  nghttp2_map_bucket *bkt;
+  size_t d = 0;
+
+  for (;;) {
+    bkt = &map->table[idx];
+
+    if (bkt->data == NULL ||
+        d > distance(map->tablelen, map->tablelenbits, bkt, idx)) {
+      return NULL;
     }
+
+    if (bkt->key == key) {
+      return bkt->data;
+    }
+
+    ++d;
+    idx = (idx + 1) & (map->tablelen - 1);
   }
-  return NULL;
 }
 
-int nghttp2_map_remove(nghttp2_map *map, key_type key) {
-  uint32_t h;
-  nghttp2_map_entry **dst;
+int nghttp2_map_remove(nghttp2_map *map, nghttp2_map_key_type key) {
+  uint32_t h = hash(key);
+  size_t idx = h2idx(h, map->tablelenbits), didx;
+  nghttp2_map_bucket *bkt;
+  size_t d = 0;
 
-  h = hash(key, map->tablelen);
+  for (;;) {
+    bkt = &map->table[idx];
 
-  for (dst = &map->table[h]; *dst; dst = &(*dst)->next) {
-    if ((*dst)->key != key) {
-      continue;
+    if (bkt->data == NULL ||
+        d > distance(map->tablelen, map->tablelenbits, bkt, idx)) {
+      return NGHTTP2_ERR_INVALID_ARGUMENT;
+    }
+
+    if (bkt->key == key) {
+      map_bucket_set_data(bkt, 0, 0, NULL);
+
+      didx = idx;
+      idx = (idx + 1) & (map->tablelen - 1);
+
+      for (;;) {
+        bkt = &map->table[idx];
+        if (bkt->data == NULL ||
+            distance(map->tablelen, map->tablelenbits, bkt, idx) == 0) {
+          break;
+        }
+
+        map->table[didx] = *bkt;
+        map_bucket_set_data(bkt, 0, 0, NULL);
+        didx = idx;
+
+        idx = (idx + 1) & (map->tablelen - 1);
+      }
+
+      --map->size;
+
+      return 0;
     }
 
-    *dst = (*dst)->next;
-    --map->size;
-    return 0;
+    ++d;
+    idx = (idx + 1) & (map->tablelen - 1);
   }
-  return NGHTTP2_ERR_INVALID_ARGUMENT;
+}
+
+void nghttp2_map_clear(nghttp2_map *map) {
+  memset(map->table, 0, sizeof(*map->table) * map->tablelen);
+  map->size = 0;
 }
 
 size_t nghttp2_map_size(nghttp2_map *map) { return map->size; }