closed_hash_map.h | Explore in Territory

// Copyright 2016 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef COMPONENTS_URL_PATTERN_INDEX_CLOSED_HASH_MAP_H_
#define COMPONENTS_URL_PATTERN_INDEX_CLOSED_HASH_MAP_H_

#include <stddef.h>
#include <stdint.h>

#include <functional>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>

#include "base/bits.h"
#include "base/check_op.h"
#include "base/numerics/safe_conversions.h"

namespace url_pattern_index {

template <typename KeyType_, typename Hasher_>
class SimpleQuadraticProber;

template <typename KeyType_, typename ValueType_, typename Prober_>
class ClosedHashMap;

// The default Prober used by the HashMap.
DefaultProber;

// The default HashMap data structure meant to be used. For more fine-grained
// control one can use ClosedHashMap with their own Prober.
HashMap;

// An insert-only map implemented as a hash-table with open addressing (also
// called closed hashing). The table can contain up to 2^30 distinct keys. It is
// a 32-bit table independent of the process being 32-bit or 64-bit to ensure
// that tables can be read in processes of different bitness from those in which
// they were generated. This is a requirement of consumers of this data
// structure. In particular, the subresource_filter component in Weblayer
// generates tables in the 64-bit browser process but also accesses them the
// 32-bit renderer process.
//
// On normal operation load factor varies within range (1/4, 1/2]. The real load
// factor can be less or equal to 1/4 if rehashing is requested explicitly to
// allocate more memory for future insertions.
//
// The table discloses its internal structure in order to allow converting it to
// different formats. It consists of 2 vectors, |hash_table| and |entries|. The
// |entries| is a vector of pair<KeyType, ValueType>, whereas |hash_table|'s
// elements (also called slots) are indexes into the |entries| vector. If, for
// some i, hash_table[i] >= entries.size() then the i-th slot is empty. It is
// guaranteed that each of the entries is referenced by exactly one table slot.
//
// The Prober is a strategy class used to find a slot for a particular key by
// probing the key against a sequence of slots called a probe sequence. Often it
// stores one or more hashers - functors used to calculate hash values of the
// keys in order to parameterize the probe sequence. The Prober class should
// provide the following:
//
//  Public type(s):
//   KeyType - the type of the keys the table can store. Should be equal to the
//   ClosedHashTable's KeyType.
//
//  Public method(s):
//   template <typename SlotCompare>
//   uint32_t FindSlot(const KeyType& key,
//                     uint32_t table_size,
//                     const SlotCompare& compare) const;
//
//   Walks the probe sequence for the given |key| starting from some initial
//   slot calculated deterministically from the |key|, e.g. by computing its
//   hash code. The walk continues until it finds a hash table slot such that
//   compare(key, slot) returns true (which, for instance, can mean that the
//   slot is empty or its key is equal to |key|). Returns the index of that slot
//   in [0, table_size). The method is required to perform a finite number of
//   probes until it finds a slot.
//
// The same Prober class can be used to ensure compatibility when performing
// lookups in two different representations of what is conceptually the same
// hash map.
//
// TODO(pkalinnikov): Add key comparator.
template <typename KeyType_, typename ValueType_, typename Prober_>
class ClosedHashMap { … };

// The implementation of Prober that uses a simple form of quadratic probing.
// That is, for a given |key| the sequence of probes is the following (modulo
// the hash table size):
//   hash(key), hash(key) + 1, hash(key) + 3, ..., hash(key) + k * (k - 1) / 2
//
// To use this prober the hash table should maintain its size M equal to powers
// of two. It can be shown that in this case the aforementioned quadratic probe
// sequence for k <= M visits k distinct table slots.
//
// Template parameters:
//   KeyType_ - the type of the table's keys.
//   Hasher_ - the type of the functor used to calculate hashes of keys.
template <typename KeyType_, typename Hasher_>
class SimpleQuadraticProber { … };

}  // namespace url_pattern_index

#endif  // COMPONENTS_URL_PATTERN_INDEX_CLOSED_HASH_MAP_H_
chromium/components/url_pattern_index/closed_hash_map.h
