htrace-c/src/util/htable.h

/**
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you 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 APACHE_HTRACE_HTABLE_H
#define APACHE_HTRACE_HTABLE_H

/**
 * @file htable.h
 *
 * Interfaces for a hash table that uses probing.
 *
 * This is an internal header, not intended for external use.
 */

#include <inttypes.h>
#include <stdio.h>
#include <stdint.h>

#define HTABLE_MIN_SIZE 4

struct htable;

/**
 * An HTable hash function.
 *
 * @param key       The key.
 * @param capacity  The total capacity.
 *
 * @return          The hash slot.  Must be less than the capacity.
 */
typedef uint32_t (*htable_hash_fn_t)(const void *key, uint32_t capacity);

/**
 * An HTable equality function.  Compares two keys.
 *
 * @param a         First key.
 * @param b         Second key.
 *
 * @return          nonzero if the keys are equal.
 */
typedef int (*htable_eq_fn_t)(const void *a, const void *b);

/**
 * Allocate a new hash table.
 *
 * @param capacity  The minimum suggested starting capacity.
 * @param hash_fun  The hash function to use in this hash table.
 * @param eq_fun    The equals function to use in this hash table.
 *
 * @return          The new hash table on success; NULL on OOM.
 */
struct htable *htable_alloc(uint32_t capacity, htable_hash_fn_t hash_fun,
                            htable_eq_fn_t eq_fun);

typedef void (*visitor_fn_t)(void *ctx, void *key, void *val);

/**
 * Visit all of the entries in the hash table.
 *
 * @param htable    The hash table.
 * @param fun       The callback function to invoke on each key and value.
 * @param ctx       Context pointer to pass to the callback.
 */
void htable_visit(struct htable *htable, visitor_fn_t fun, void *ctx);

/**
 * Free the hash table.
 *
 * It is up the calling code to ensure that the keys and values inside the
 * table are de-allocated, if that is necessary.
 *
 * @param htable    The hash table.
 */
void htable_free(struct htable *htable);

/**
 * Add an entry to the hash table.
 *
 * @param htable    The hash table.
 * @param key       The key to add.  This cannot be NULL.
 * @param fun       The value to add.  This cannot be NULL.
 *
 * @return          0 on success;
 *                  EINVAL if we're trying to insert a NULL key or value.
 *                  ENOMEM if there is not enough memory to add the element.
 *                  EFBIG if the hash table has too many entries to fit in 32
 *                      bits.
 */
int htable_put(struct htable *htable, void *key, void *val);

/**
 * Get an entry from the hash table.
 *
 * @param htable    The hash table.
 * @param key       The key to find.
 *
 * @return          NULL if there is no such entry; the entry otherwise.
 */
void *htable_get(const struct htable *htable, const void *key);

/**
 * Get an entry from the hash table and remove it.
 *
 * @param htable    The hash table.
 * @param key       The key for the entry find and remove.
 * @param found_key (out param) NULL if the entry was not found; the found key
 *                      otherwise.
 * @param found_val (out param) NULL if the entry was not found; the found
 *                      value otherwise.
 */
void htable_pop(struct htable *htable, const void *key,
                void **found_key, void **found_val);

/**
 * Get the number of entries used in the hash table.
 *
 * @param htable    The hash table.
 *
 * @return          The number of entries used in the hash table.
 */
uint32_t htable_used(const struct htable *htable);

/**
 * Get the capacity of the hash table.
 *
 * @param htable    The hash table.
 *
 * @return          The capacity of the hash table.
 */
uint32_t htable_capacity(const struct htable *htable);

/**
 * Hash a string.
 *
 * @param str       The string.
 * @param max       Maximum hash value
 *
 * @return          A number less than max.
 */
uint32_t ht_hash_string(const void *str, uint32_t max);

/**
 * Compare two strings.
 *
 * @param a         The first string.
 * @param b         The second string.
 *
 * @return          1 if the strings are identical; 0 otherwise.
 */
int ht_compare_string(const void *a, const void *b);

#endif

// vim: ts=4:sw=4:tw=79:et