2N/A/*
2N/A * CDDL HEADER START
2N/A *
2N/A * The contents of this file are subject to the terms of the
2N/A * Common Development and Distribution License (the "License").
2N/A * You may not use this file except in compliance with the License.
2N/A *
2N/A * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
2N/A * or http://www.opensolaris.org/os/licensing.
2N/A * See the License for the specific language governing permissions
2N/A * and limitations under the License.
2N/A *
2N/A * When distributing Covered Code, include this CDDL HEADER in each
2N/A * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
2N/A * If applicable, add the following below this CDDL HEADER, with the
2N/A * fields enclosed by brackets "[]" replaced with your own identifying
2N/A * information: Portions Copyright [yyyy] [name of copyright owner]
2N/A *
2N/A * CDDL HEADER END
2N/A */
2N/A/*
2N/A * Copyright (c) 2007, 2011, Oracle and/or its affiliates. All rights reserved.
2N/A */
2N/A
2N/A#ifndef _SMBNS_HASH_H
2N/A#define _SMBNS_HASH_H
2N/A
2N/A/*
2N/A *
2N/A * Interface definition for the hash table library. The hash table is a
2N/A * user-specified array of pointers to items. Hash collisions are handled
2N/A * using linked lists from the table entries. A handle is associated with
2N/A * each table, which is used to maintain the hash table.
2N/A *
2N/A * +------+ +-------+ +----+ +----+
2N/A * |handle|---> |index 0|--->|item|--->|item|--->
2N/A * | ... | +-------+ +----+ +----+
2N/A * | ... | |index 1|--->
2N/A * +------+ +-------+ +----+ +----+ +----+
2N/A * |index 2|--->|item|--->|item|--->|item|--->
2N/A * +-------+ +----+ +----+ +----+
2N/A * | ... |--->
2N/A * +-------+
2N/A * | ... |--->
2N/A * +-------+
2N/A * |index n|--->
2N/A * +-------+
2N/A *
2N/A */
2N/A
2N/A#include <sys/types.h>
2N/A
2N/A#ifdef __cplusplus
2N/Aextern "C" {
2N/A#endif
2N/A
2N/A/*
2N/A * This is the hash multiplier value.
2N/A */
2N/A#define HASH_MESH_VALUE 77
2N/A
2N/A/*
2N/A * Each entry (item) in the hash table has a linked-list pointer, a key,
2N/A * a pointer to some user defined data (which may be null) and some flags.
2N/A * The key is a user provided key and is used to position the item within
2N/A * the table. The linked-list is used to store items whose hash values
2N/A * collide. The data pointer is never dereferenced in the hash code so
2N/A * it may be a null pointer.
2N/A *
2N/A * The item bit flags are:
2N/A *
2N/A * HTIF_DELETE: Specifies that an item is marked for deletion (see
2N/A * ht_mark_delete and ht_clean_table).
2N/A */
2N/A#define HTIF_MARKED_DELETED 0x01
2N/A#define HT_DELETE HTIF_MARKED_DELETED
2N/A
2N/Atypedef struct ht_item {
2N/A struct ht_item *hi_next;
2N/A char *hi_key;
2N/A void *hi_data;
2N/A size_t hi_flags;
2N/A} HT_ITEM;
2N/A
2N/A/*
2N/A * HT_TABLE_ENTRY is an opaque structure (to the public) used to maintain
2N/A * a pointer to the hash table and the number of items in the table entry.
2N/A * This number shows number of both available items and those are marked
2N/A * as deleted.
2N/A */
2N/Atypedef struct ht_table_entry {
2N/A HT_ITEM *he_head;
2N/A size_t he_count;
2N/A} HT_TABLE_ENTRY;
2N/A
2N/A/*
2N/A * The HT_HANDLE is an opaque handle that associates each request with
2N/A * a hash table. A handle is generated when a hash table is created and
2N/A * it is used to maintain all global data associated with the table.
2N/A *
2N/A * The handle bit flags are:
2N/A *
2N/A * HTHF_FIXED_KEY: Specifies that keys are fixed length and should
2N/A * not be assumed to be null terminated.
2N/A */
2N/A#define HTHF_FIXED_KEY 0x01
2N/A
2N/Atypedef struct ht_handle {
2N/A HT_TABLE_ENTRY *ht_table;
2N/A size_t ht_sequence;
2N/A size_t ht_table_size;
2N/A size_t ht_table_mask;
2N/A size_t ht_key_size;
2N/A size_t ht_total_items; /* show total number of available items */
2N/A size_t ht_flags;
2N/A size_t (*ht_hash)(struct ht_handle *handle, const char *key);
2N/A void (*ht_callback)(HT_ITEM *item);
2N/A int (*ht_cmp)(const char *key1, const char *key2, size_t n);
2N/A} HT_HANDLE;
2N/A
2N/A/*
2N/A * Typedefs for the optional user-installable functions.
2N/A */
2N/Atypedef void (*HT_CALLBACK)(HT_ITEM *item);
2N/A
2N/A/*
2N/A * Compare function cast to make all compare
2N/A * functions look like strncmp.
2N/A */
2N/Atypedef int (*HT_CMP)(const char *, const char *, size_t);
2N/A
2N/A/*
2N/A * Iterator used with ht_findfirst and ht_findnext to walk through
2N/A * all the items in a hash table. The iterator should be treated as
2N/A * an opaque handle. The sequence number in the iterator is used
2N/A * to maintain consistency with the table on which the iteration
2N/A * is being performed. If the table sequence number changes, the
2N/A * iterator becomes invalid.
2N/A */
2N/Atypedef struct ht_iterator {
2N/A HT_HANDLE *hti_handle;
2N/A HT_ITEM *hti_item;
2N/A size_t hti_index;
2N/A size_t hti_sequence;
2N/A} HT_ITERATOR;
2N/A
2N/A/*
2N/A * Public API to create and destroy hash tables, to change the hash
2N/A * function and to find out how many items are in a hash table.
2N/A */
2N/Aextern HT_HANDLE *ht_create_table(size_t table_size, size_t key_size,
2N/A size_t flags);
2N/Aextern void ht_destroy_table(HT_HANDLE *handle);
2N/Aextern void ht_set_cmpfn(HT_HANDLE *handle, HT_CMP cmpfn);
2N/Aextern size_t ht_get_total_items(HT_HANDLE *handle);
2N/A
2N/A/*
2N/A * Public API to add, remove, replace or find specific items
2N/A * in a hash table.
2N/A */
2N/Aextern HT_ITEM *ht_add_item(HT_HANDLE *handle, const char *key,
2N/A const void *data);
2N/Aextern HT_ITEM *ht_replace_item(HT_HANDLE *handle, const char *key,
2N/A const void *data);
2N/Aextern void *ht_remove_item(HT_HANDLE *handle, const char *key);
2N/Aextern HT_ITEM *ht_find_item(HT_HANDLE *handle, const char *key);
2N/A
2N/A/*
2N/A * Public API to iterate over a hash table. A mechanism is provided to
2N/A * mark items for deletion while searching the table so that the table
2N/A * is not modified during the search. When the search is complete, all
2N/A * of the marked items can be deleted by calling ht_clean_table. If
2N/A * the item data has been dynamically allocated, a callback can be
2N/A * registered to free the memory. The callback will be invoked with a
2N/A * pointer to each item as it is removed from the hash table.
2N/A */
2N/Aextern HT_ITEM *ht_findfirst(HT_HANDLE *handle, HT_ITERATOR *iterator);
2N/Aextern HT_ITEM *ht_findnext(HT_ITERATOR *iterator);
2N/Aextern void ht_mark_delete(HT_HANDLE *handle, HT_ITEM *item);
2N/Aextern void ht_clear_delete(HT_HANDLE *handle, HT_ITEM *item);
2N/Aextern size_t ht_clean_table(HT_HANDLE *handle);
2N/Aextern HT_CALLBACK ht_register_callback(HT_HANDLE *handle,
2N/A HT_CALLBACK callback);
2N/A
2N/A#ifdef __cplusplus
2N/A}
2N/A#endif
2N/A
2N/A#endif /* _SMBNS_HASH_H */