Merge github.com:grpc/grpc into cq-drop

2 files changed, 54 insertions, 4 deletions

diff --git a/src/core/lib/slice/slice_hash_table.c b/src/core/lib/slice/slice_hash_table.c
index 444f22aa19..2d9ff61c95 100644
--- a/src/core/lib/slice/slice_hash_table.c
+++ b/src/core/lib/slice/slice_hash_table.c
@@ -43,6 +43,7 @@
 struct grpc_slice_hash_table {
   gpr_refcount refs;
   void (*destroy_value)(grpc_exec_ctx* exec_ctx, void* value);
+  int (*value_cmp)(void* a, void* b);
   size_t size;
   size_t max_num_probes;
   grpc_slice_hash_table_entry* entries;
@@ -72,10 +73,12 @@ static void grpc_slice_hash_table_add(grpc_slice_hash_table* table,
 
 grpc_slice_hash_table* grpc_slice_hash_table_create(
     size_t num_entries, grpc_slice_hash_table_entry* entries,
-    void (*destroy_value)(grpc_exec_ctx* exec_ctx, void* value)) {
+    void (*destroy_value)(grpc_exec_ctx* exec_ctx, void* value),
+    int (*value_cmp)(void* a, void* b)) {
   grpc_slice_hash_table* table = gpr_zalloc(sizeof(*table));
   gpr_ref_init(&table->refs, 1);
   table->destroy_value = destroy_value;
+  table->value_cmp = value_cmp;
   // Keep load factor low to improve performance of lookups.
   table->size = num_entries * 2;
   const size_t entry_size = sizeof(grpc_slice_hash_table_entry) * table->size;
@@ -121,3 +124,37 @@ void* grpc_slice_hash_table_get(const grpc_slice_hash_table* table,
   }
   return NULL;  // Not found.
 }
+
+static int pointer_cmp(void* a, void* b) { return GPR_ICMP(a, b); }
+int grpc_slice_hash_table_cmp(const grpc_slice_hash_table* a,
+                              const grpc_slice_hash_table* b) {
+  int (*const value_cmp_fn_a)(void* a, void* b) =
+      a->value_cmp != NULL ? a->value_cmp : pointer_cmp;
+  int (*const value_cmp_fn_b)(void* a, void* b) =
+      b->value_cmp != NULL ? b->value_cmp : pointer_cmp;
+  // Compare value_fns
+  const int value_fns_cmp =
+      GPR_ICMP((void*)value_cmp_fn_a, (void*)value_cmp_fn_b);
+  if (value_fns_cmp != 0) return value_fns_cmp;
+  // Compare sizes
+  if (a->size < b->size) return -1;
+  if (a->size > b->size) return 1;
+  // Compare rows.
+  for (size_t i = 0; i < a->size; ++i) {
+    if (is_empty(&a->entries[i])) {
+      if (!is_empty(&b->entries[i])) {
+        return -1;  // a empty but b non-empty
+      }
+      continue;  // both empty, no need to check key or value
+    } else if (is_empty(&b->entries[i])) {
+      return 1;  // a non-empty but b empty
+    }
+    // neither entry is empty
+    const int key_cmp = grpc_slice_cmp(a->entries[i].key, b->entries[i].key);
+    if (key_cmp != 0) return key_cmp;
+    const int value_cmp =
+        value_cmp_fn_a(a->entries[i].value, b->entries[i].value);
+    if (value_cmp != 0) return value_cmp;
+  }
+  return 0;
+}
diff --git a/src/core/lib/slice/slice_hash_table.h b/src/core/lib/slice/slice_hash_table.h
index 1e61c5eb11..07988abff4 100644
--- a/src/core/lib/slice/slice_hash_table.h
+++ b/src/core/lib/slice/slice_hash_table.h
@@ -54,11 +54,15 @@ typedef struct grpc_slice_hash_table_entry {
 } grpc_slice_hash_table_entry;
 
 /** Creates a new hash table of containing \a entries, which is an array
-    of length \a num_entries.  Takes ownership of all keys and values in
-    \a entries.  Values will be cleaned up via \a destroy_value(). */
+    of length \a num_entries.  Takes ownership of all keys and values in \a
+    entries.  Values will be cleaned up via \a destroy_value(). If not NULL, \a
+    value_cmp will be used to compare values in the context of \a
+    grpc_slice_hash_table_cmp. If NULL, raw pointer (\a GPR_ICMP) comparison
+    will be used. */
 grpc_slice_hash_table *grpc_slice_hash_table_create(
     size_t num_entries, grpc_slice_hash_table_entry *entries,
-    void (*destroy_value)(grpc_exec_ctx *exec_ctx, void *value));
+    void (*destroy_value)(grpc_exec_ctx *exec_ctx, void *value),
+    int (*value_cmp)(void *a, void *b));
 
 grpc_slice_hash_table *grpc_slice_hash_table_ref(grpc_slice_hash_table *table);
 void grpc_slice_hash_table_unref(grpc_exec_ctx *exec_ctx,
@@ -69,4 +73,13 @@ void grpc_slice_hash_table_unref(grpc_exec_ctx *exec_ctx,
 void *grpc_slice_hash_table_get(const grpc_slice_hash_table *table,
                                 const grpc_slice key);
 
+/** Compares \a a vs. \a b.
+ * A table is considered "smaller" (resp. "greater") if:
+ *  - GPR_ICMP(a->value_cmp, b->value_cmp) < 1 (resp. > 1),
+ *  - else, it contains fewer (resp. more) entries,
+ *  - else, if strcmp(a_key, b_key) < 1 (resp. > 1),
+ *  - else, if value_cmp(a_value, b_value) < 1 (resp. > 1). */
+int grpc_slice_hash_table_cmp(const grpc_slice_hash_table *a,
+                              const grpc_slice_hash_table *b);
+
 #endif /* GRPC_CORE_LIB_SLICE_SLICE_HASH_TABLE_H */