src/core/ext/census/intrusive_hash_map.h

/*
 *
 * Copyright 2017 gRPC authors.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 */

#ifndef GRPC_CORE_EXT_CENSUS_INTRUSIVE_HASH_MAP_H
#define GRPC_CORE_EXT_CENSUS_INTRUSIVE_HASH_MAP_H

#include "src/core/ext/census/intrusive_hash_map_internal.h"

#ifdef __cplusplus
extern "C" {
#endif

/* intrusive_hash_map is a fast chained hash table. This hash map is faster than
 * a dense hash map when the application calls insert and erase more often than
 * find. When the workload is dominated by find() a dense hash map may be
 * faster.
 *
 * intrusive_hash_map uses an intrusive header placed within a user defined
 * struct. The header field IHM_key MUST be set to a valid value before
 * insertion into the hash map or undefined behavior may occur. The header field
 * IHM_hash_link MUST to be set to NULL initially.
 *
 * EXAMPLE USAGE:
 *
 *  typedef struct string_item {
 *    INTRUSIVE_HASH_MAP_HEADER;
 *    // User data.
 *    char *str_buf;
 *    uint16_t len;
 *  } string_item;
 *
 *  static string_item *make_string_item(uint64_t key, const char *buf,
 *                                       uint16_t len) {
 *    string_item *item = (string_item *)gpr_malloc(sizeof(string_item));
 *    item->IHM_key = key;
 *    item->IHM_hash_link = NULL;
 *    item->len = len;
 *    item->str_buf = (char *)malloc(len);
 *    memcpy(item->str_buf, buf, len);
 *    return item;
 *  }
 *
 *  intrusive_hash_map hash_map;
 *  intrusive_hash_map_init(&hash_map, 4);
 *  string_item *new_item1 = make_string_item(10, "test1", 5);
 *  bool ok = intrusive_hash_map_insert(&hash_map, (hm_item *)new_item1);
 *
 *  string_item *item1 =
 *    (string_item *)intrusive_hash_map_find(&hash_map, 10);
 */

/* Hash map item. Stores key and a pointer to the actual object. A user defined
 * version of this can be passed in provided the first 2 entries (key and
 * hash_link) are the same. These entries must be first in the user defined
 * struct. Pointer to struct will need to be cast as (hm_item *) when passed to
 * hash map. This allows it to be intrusive. */
typedef struct hm_item {
  uint64_t key;
  struct hm_item *hash_link;
  /* Optional user defined data after this. */
} hm_item;

/* Macro provided for ease of use.  This must be first in the user defined
 * struct (i.e. uint64_t key and hm_item * must be the first two elements in
 * that order). */
#define INTRUSIVE_HASH_MAP_HEADER \
  uint64_t IHM_key;               \
  struct hm_item *IHM_hash_link

/* Index struct which acts as a pseudo-iterator within the hash map. */
typedef struct hm_index {
  uint32_t bucket_index;  // hash map bucket index.
  hm_item *item;          // Pointer to hm_item within the hash map.
} hm_index;

/* Returns true if two hm_indices point to the same object within the hash map
 * and false otherwise. */
__inline bool hm_index_compare(const hm_index *A, const hm_index *B) {
  return (A->item == B->item && A->bucket_index == B->bucket_index);
}

/*
 * Helper functions for iterating over the hash map.
 */

/* On return idx will contain an invalid index which is always equal to
 * hash_map->buckets.size_ */
void intrusive_hash_map_end(const intrusive_hash_map *hash_map, hm_index *idx);

/* Iterates index to the next valid entry in the hash map and stores the
 * index within idx. If end of table is reached, idx will contain the same
 * values as if intrusive_hash_map_end() was called. */
void intrusive_hash_map_next(const intrusive_hash_map *hash_map, hm_index *idx);

/* On return, idx will contain the index of the first non-null entry in the hash
 * map. If the hash map is empty, idx will contain the same values as if
 * intrusive_hash_map_end() was called. */
void intrusive_hash_map_begin(const intrusive_hash_map *hash_map,
                              hm_index *idx);

/* Initialize intrusive hash map data structure. This must be called before
 * the hash map can be used. The initial size of an intrusive hash map will be
 * 2^initial_log2_map_size (valid range is [0, 31]). */
void intrusive_hash_map_init(intrusive_hash_map *hash_map,
                             uint32_t initial_log2_map_size);

/* Returns true if the hash map is empty and false otherwise. */
bool intrusive_hash_map_empty(const intrusive_hash_map *hash_map);

/* Returns the number of elements currently in the hash map. */
size_t intrusive_hash_map_size(const intrusive_hash_map *hash_map);

/* Find a hm_item within the hash map by key. Returns NULL if item was not
 * found. */
hm_item *intrusive_hash_map_find(const intrusive_hash_map *hash_map,
                                 uint64_t key);

/* Erase the hm_item that corresponds with key. If the hm_item is found, return
 * the pointer to the hm_item. Else returns NULL. */
hm_item *intrusive_hash_map_erase(intrusive_hash_map *hash_map, uint64_t key);

/* Attempts to insert a new hm_item into the hash map.  If an element with the
 * same key already exists, it will not insert the new item and return false.
 * Otherwise, it will insert the new item and return true. */
bool intrusive_hash_map_insert(intrusive_hash_map *hash_map, hm_item *item);

/* Clears entire contents of the hash map, but leaves internal data structure
 * untouched. Second argument takes a function pointer to a function that will
 * free the object designated by the user and pointed to by hash_map->value. */
void intrusive_hash_map_clear(intrusive_hash_map *hash_map,
                              void (*free_object)(void *));

/* Erase all contents of hash map and free the memory. Hash map is invalid
 * after calling this function and cannot be used until it has been
 * reinitialized (intrusive_hash_map_init()). This function takes a function
 * pointer to a function that will free the object designated by the user and
 * pointed to by hash_map->value. */
void intrusive_hash_map_free(intrusive_hash_map *hash_map,
                             void (*free_object)(void *));

#ifdef __cplusplus
}
#endif

#endif /* GRPC_CORE_EXT_CENSUS_INTRUSIVE_HASH_MAP_H */