hash_table.h

/*
 *
 * Copyright 2015, Google Inc.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following disclaimer
 * in the documentation and/or other materials provided with the
 * distribution.
 *     * Neither the name of Google Inc. nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */

#ifndef GRPC_INTERNAL_CORE_STATISTICS_HASH_TABLE_H
#define GRPC_INTERNAL_CORE_STATISTICS_HASH_TABLE_H

#include <stddef.h>

#include <grpc/support/port_platform.h>

/* A chain based hash table with fixed number of buckets.
   Your probably shouldn't use this code directly. It is implemented for the
   use case in census trace store and stats store, where number of entries in
   the table is in the scale of upto several thousands, entries are added and
   removed from the table very frequently (~100k/s), the frequency of find()
   operations is roughly several times of the frequency of insert() and erase()
   Comparing to find(), the insert(), erase() and get_all_entries() operations
   are much less freqent (<1/s).

   Per bucket memory overhead is about (8 + sizeof(intptr_t) bytes.
   Per entry memory overhead is about (8 + 2 * sizeof(intptr_t) bytes.

   All functions are not thread-safe. Synchronization will be provided in the
   upper layer (in trace store and stats store).
*/

/* Opaque hash table struct */
typedef struct unresizable_hash_table census_ht;

/* Currently, the hash_table can take two types of keys. (uint64 for trace
   store and const char* for stats store). */
typedef union {
  gpr_uint64 val;
  void* ptr;
} census_ht_key;

typedef enum census_ht_key_type {
  CENSUS_HT_UINT64 = 0,
  CENSUS_HT_POINTER = 1
} census_ht_key_type;

typedef struct census_ht_option {
  /* Type of hash key */
  census_ht_key_type key_type;
  /* Desired number of buckets, preferably a prime number */
  gpr_int32 num_buckets;
  /* Fucntion to calculate uint64 hash value of the key. Only takes effect if
     key_type is POINTER. */
  gpr_uint64 (*hash)(const void*);
  /* Function to compare two keys, returns 0 iff equal. Only takes effect if
     key_type is POINTER */
  int (*compare_keys)(const void* k1, const void* k2);
  /* Value deleter. NULL if no specialized delete function is needed. */
  void (*delete_data)(void*);
  /* Key deleter. NULL if table does not own the key. (e.g. key is part of the
     value or key is not owned by the table.) */
  void (*delete_key)(void*);
} census_ht_option;

/* Creates a hashtable with fixed number of buckets according to the settings
   specified in 'options' arg. Function pointers "hash" and "compare_keys" must
   be provided if key_type is POINTER. Asserts if fail to create. */
census_ht* census_ht_create(const census_ht_option* options);

/* Deletes hash table instance. Frees all dynamic memory owned by ht.*/
void census_ht_destroy(census_ht* ht);

/* Inserts the input key-val pair into hash_table. If an entry with the same key
   exists in the table, the corresponding value will be overwritten by the input
   val. */
void census_ht_insert(census_ht* ht, census_ht_key key, void* val);

/* Returns pointer to data, returns NULL if not found. */
void* census_ht_find(const census_ht* ht, census_ht_key key);

/* Erase hash table entry with input key. Noop if key is not found. */
void census_ht_erase(census_ht* ht, census_ht_key key);

typedef struct census_ht_kv {
  census_ht_key k;
  void* v;
} census_ht_kv;

/* Returns an array of pointers to all values in the hash table. Order of the
   elements can be arbitrary. Sets 'num' to the size of returned array. Caller
   owns returned array. */
census_ht_kv* census_ht_get_all_elements(const census_ht* ht, size_t* num);

/* Returns number of elements kept. */
size_t census_ht_get_size(const census_ht* ht);

/* Functor applied on each key-value pair while iterating through entries in the
   table. The functor should not mutate data. */
typedef void (*census_ht_itr_cb)(census_ht_key key, const void* val_ptr,
                                 void* state);

/* Iterates through all key-value pairs in the hash_table. The callback function
   should not invalidate data entries. */
gpr_uint64 census_ht_for_all(const census_ht* ht, census_ht_itr_cb);

#endif  /* GRPC_INTERNAL_CORE_STATISTICS_HASH_TABLE_H */