GRPC C++  1.26.0
slice_hash_table.h
Go to the documentation of this file.
1 /*
2  * Copyright 2016 gRPC authors.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef GRPC_CORE_LIB_SLICE_SLICE_HASH_TABLE_H
18 #define GRPC_CORE_LIB_SLICE_SLICE_HASH_TABLE_H
19 
21 
22 #include <string.h>
23 
24 #include <grpc/support/alloc.h>
25 #include <grpc/support/log.h>
26 
32 
42 
43 namespace grpc_core {
44 
45 template <typename T>
46 class SliceHashTable : public RefCounted<SliceHashTable<T>> {
47  public:
48  struct Entry {
50  T value;
51  bool is_set;
52  };
53 
54  // Function for comparing values.
55  // TODO(roth): Eliminate this and the Cmp() method from this API once
56  // grpc_channel_args is redesigned to require that keys are unique.
57  typedef int (*ValueCmp)(const T&, const T&);
58 
64  static RefCountedPtr<SliceHashTable> Create(size_t num_entries,
65  Entry* entries,
66  ValueCmp value_cmp);
67 
68  // Use Create function instead of using this directly.
69  SliceHashTable(size_t num_entries, Entry* entries, ValueCmp value_cmp);
70  virtual ~SliceHashTable();
71 
74  const T* Get(const grpc_slice& key) const;
75 
82  static int Cmp(const SliceHashTable& a, const SliceHashTable& b);
83 
84  private:
85  void Add(const grpc_slice& key, T& value);
86 
87  // Default value comparison function, if none specified by caller.
88  static int DefaultValueCmp(const T& a, const T& b) { return GPR_ICMP(a, b); }
89 
90  const ValueCmp value_cmp_;
91  const size_t size_;
92  size_t max_num_probes_;
93  Entry* entries_;
94 };
95 
96 //
97 // implementation -- no user-serviceable parts below
98 //
99 
100 template <typename T>
102  Entry* entries,
103  ValueCmp value_cmp) {
104  return MakeRefCounted<SliceHashTable<T>>(num_entries, entries, value_cmp);
105 }
106 
107 template <typename T>
108 SliceHashTable<T>::SliceHashTable(size_t num_entries, Entry* entries,
109  ValueCmp value_cmp)
110  : value_cmp_(value_cmp),
111  // Keep load factor low to improve performance of lookups.
112  size_(num_entries * 2),
113  max_num_probes_(0) {
114  entries_ = static_cast<Entry*>(gpr_zalloc(sizeof(Entry) * size_));
115  for (size_t i = 0; i < num_entries; ++i) {
116  Entry* entry = &entries[i];
117  Add(entry->key, entry->value);
118  }
119 }
120 
121 template <typename T>
123  for (size_t i = 0; i < size_; ++i) {
124  Entry& entry = entries_[i];
125  if (entry.is_set) {
127  entry.value.~T();
128  }
129  }
130  gpr_free(entries_);
131 }
132 
133 template <typename T>
134 void SliceHashTable<T>::Add(const grpc_slice& key, T& value) {
135  const size_t hash = grpc_slice_hash_internal(key);
136  for (size_t offset = 0; offset < size_; ++offset) {
137  const size_t idx = (hash + offset) % size_;
138  if (!entries_[idx].is_set) {
139  entries_[idx].is_set = true;
140  entries_[idx].key = key;
141  entries_[idx].value = std::move(value);
142  // Keep track of the maximum number of probes needed, since this
143  // provides an upper bound for lookups.
144  if (offset > max_num_probes_) max_num_probes_ = offset;
145  return;
146  }
147  }
148  GPR_ASSERT(false); // Table should never be full.
149 }
150 
151 template <typename T>
152 const T* SliceHashTable<T>::Get(const grpc_slice& key) const {
153  const size_t hash = grpc_slice_hash_internal(key);
154  // We cap the number of probes at the max number recorded when
155  // populating the table.
156  for (size_t offset = 0; offset <= max_num_probes_; ++offset) {
157  const size_t idx = (hash + offset) % size_;
158  if (!entries_[idx].is_set) break;
159  if (grpc_slice_eq(entries_[idx].key, key)) {
160  return &entries_[idx].value;
161  }
162  }
163  return nullptr; // Not found.
164 }
165 
166 template <typename T>
168  ValueCmp value_cmp_a =
169  a.value_cmp_ != nullptr ? a.value_cmp_ : DefaultValueCmp;
170  ValueCmp value_cmp_b =
171  b.value_cmp_ != nullptr ? b.value_cmp_ : DefaultValueCmp;
172  // Compare value_fns
173  const int value_fns_cmp = GPR_ICMP((void*)value_cmp_a, (void*)value_cmp_b);
174  if (value_fns_cmp != 0) return value_fns_cmp;
175  // Compare sizes
176  if (a.size_ < b.size_) return -1;
177  if (a.size_ > b.size_) return 1;
178  // Compare rows.
179  for (size_t i = 0; i < a.size_; ++i) {
180  if (!a.entries_[i].is_set) {
181  if (b.entries_[i].is_set) {
182  return -1; // a empty but b non-empty
183  }
184  continue; // both empty, no need to check key or value
185  } else if (!b.entries_[i].is_set) {
186  return 1; // a non-empty but b empty
187  }
188  // neither entry is empty
189  const int key_cmp = grpc_slice_cmp(a.entries_[i].key, b.entries_[i].key);
190  if (key_cmp != 0) return key_cmp;
191  const int value_cmp = value_cmp_a(a.entries_[i].value, b.entries_[i].value);
192  if (value_cmp != 0) return value_cmp;
193  }
194  return 0;
195 }
196 
197 } // namespace grpc_core
198 
199 #endif /* GRPC_CORE_LIB_SLICE_SLICE_HASH_TABLE_H */
Definition: ref_counted.h:248
Definition: ref_counted_ptr.h:35
Definition: slice_hash_table.h:46
static int Cmp(const SliceHashTable &a, const SliceHashTable &b)
Compares a vs.
Definition: slice_hash_table.h:167
int(* ValueCmp)(const T &, const T &)
Definition: slice_hash_table.h:57
static RefCountedPtr< SliceHashTable > Create(size_t num_entries, Entry *entries, ValueCmp value_cmp)
Creates a new hash table containing entries, which is an array of length num_entries.
Definition: slice_hash_table.h:101
virtual ~SliceHashTable()
Definition: slice_hash_table.h:122
SliceHashTable(size_t num_entries, Entry *entries, ValueCmp value_cmp)
Definition: slice_hash_table.h:108
const T * Get(const grpc_slice &key) const
Returns the value from the table associated with key.
Definition: slice_hash_table.h:152
GPRAPI int grpc_slice_eq(grpc_slice a, grpc_slice b)
GPRAPI int grpc_slice_cmp(grpc_slice a, grpc_slice b)
Returns <0 if a < b, ==0 if a == b, >0 if a > b The order is arbitrary, and is not guaranteed to be s...
#define GPR_ASSERT(x)
abort() the process if x is zero, having written a line to the log.
Definition: log.h:94
GPRAPI void gpr_free(void *ptr)
free
GPRAPI void * gpr_zalloc(size_t size)
like malloc, but zero all bytes before returning them
Internal thread interface.
Definition: backoff.h:26
void grpc_slice_unref_internal(const grpc_slice &slice)
Definition: slice_internal.h:272
uint32_t grpc_slice_hash_internal(const grpc_slice &s)
Definition: slice_internal.h:333
Definition: slice_hash_table.h:48
bool is_set
Definition: slice_hash_table.h:51
T value
Definition: slice_hash_table.h:50
grpc_slice key
Definition: slice_hash_table.h:49
A grpc_slice s, if initialized, represents the byte range s.bytes[0..s.length-1].
Definition: slice.h:60
#define GPR_ICMP(a, b)
Definition: useful.h:60