da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * CDDL HEADER START
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * The contents of this file are subject to the terms of the
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Common Development and Distribution License (the "License").
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * You may not use this file except in compliance with the License.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * See the License for the specific language governing permissions
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * and limitations under the License.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * When distributing Covered Code, include this CDDL HEADER in each
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * If applicable, add the following below this CDDL HEADER, with the
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * fields enclosed by brackets "[]" replaced with your own identifying
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * information: Portions Copyright [yyyy] [name of copyright owner]
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * CDDL HEADER END
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Use is subject to license terms.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw#pragma ident "%Z%%M% %I% %E% SMI"
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Generic hash table library. The hash table is an array of pointers
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * to items. Hash collisions are handled using linked lists from the
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * table entries. A handle is associated with each table, which is used
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * to maintain the hash table.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * +------+ +-------+ +----+ +----+
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * |handle|---> |index 0|--->|item|--->|item|--->
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * | ... | +-------+ +----+ +----+
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * | ... | |index 1|--->
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * +------+ +-------+ +----+ +----+ +----+
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * |index 2|--->|item|--->|item|--->|item|--->
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * +-------+ +----+ +----+ +----+
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * | ... |--->
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * +-------+
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * | ... |--->
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * +-------+
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * |index n|--->
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * +-------+
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amwstatic size_t ht_default_hash(HT_HANDLE *handle, const char *key);
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * ht_is_power2
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Inline function to determine if a value is a power of two. This
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * function is used by the library to validate the table size when
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * a new table is created.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Returns 1 if value given is power of two, otherwise returns 0.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * ht_create_table
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Create a hash table. The table size must be a positive integer and
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * must be a power of two. The key size must be a positive integer.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * For null terminated keys, the key size does not need to include the
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * null terminating character. The type of key is indicated by the
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * flags (see hash_table.h).
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * The handle and the table are are malloc'd using a single call, to
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * avoid two allocations. The table is located immediately after the
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * On success a pointer to an opaque handle is returned. Otherwise a
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * null pointer is returned.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amwht_create_table(size_t table_size, size_t key_size, size_t flags)
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw msize = sizeof (HT_HANDLE) + (sizeof (HT_TABLE_ENTRY) * table_size);
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw /*LINTED E_BAD_PTR_CAST_ALIGN*/
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw ht->ht_table = (HT_TABLE_ENTRY *)((char *)ht + sizeof (HT_HANDLE));
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw for (i = 0; i < table_size; i++)
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * ht_destroy_table
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Destroy a hash table. All entries in the table are removed, which
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * may invoke the callback if it's installed, and the memory is freed.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw /* To remove marked entries */
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * ht_get_total_items
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Return the total number of items in the table. Returns -1 if the
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * handle is invalid.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * ht_default_hash
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Default hash function to compute the table index (hash value) based
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * on the specified key. This will identify the location for the
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * corresponding item in the hash table. The handle and key pointers
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * should be validated before this function is called.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Returns the table index location for the item.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw while (*key) {
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw while (key_len--) {
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw rval = (hash_ndx * HASH_MESH_VALUE) & handle->ht_table_mask;
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * ht_set_cmpfn
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Replace the current compare function. As the this is function
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * for comparing items' key, it should not be called while there are
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * items in the table.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * ht_add_item
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Adds an item to a hash table. The hash table is identified by the
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * handle and the key is used to generate a hashed index. The data
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * item can be null; it is never dereferenced. We don't check for
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * duplicates. If duplicate keys are added to the table, the last
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * item added will be to the front of the duplicate list.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * The table sequence number may be modified here.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * If the item is successfully inserted, a pointer to the item object
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * is returned. Otherwise a null pointer is returned.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amwht_add_item(HT_HANDLE *handle, const char *key, const void *data)
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw /* Include the null terminator */
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Add to the front of the list.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * ht_replace_item
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Replace an item in a hash table. The item associated with key is removed
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * using ht_remove_item and a new item is added using ht_add_item. We rely
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * on parameter validation in ht_remove_item and ht_add_item.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * The table sequence number may be modified here.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amwht_replace_item(HT_HANDLE *handle, const char *key, const void *data)
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * ht_remove_item
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Remove an item from a hash table. If there are duplicate keys, then the
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * first key found will be deleted. Note that the data pointer is never
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * dereferenced. If a callback is installed, it will be invoked and the
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * return value will be null. Otherwise, the data pointer supplied by the
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * application will be returned. If there is an error, a null pointer will
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * be returned.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * The table sequence number may be modified here.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw /* found key */
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Since the key and the item were allocated as
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * a single chunk, we only need one free here.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * ht_find_item
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Find an item in a hash table. If there are duplicate keys then the
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * first item found (which will be the last one added) will be returned.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Returns a pointer to an item. Otherwise returns a null pointer to
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * indicate an error or that the key didn't match anything in the table.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * ht_register_callback
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Register an application callback function that can be used to process
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * an item when it is removed from the table, i.e. free any memory
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * allocated for that data item.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * The previous callback function pointer, which may be null, before
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * registering the new one. This provides the caller with the option to
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * restore a previous callback as required.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amwht_register_callback(HT_HANDLE *handle, HT_CALLBACK callback)
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * ht_clean_table
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * This function removes all the items that are marked for deletion. Note
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * that this will invoke the callback, if one has been installed. If this
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * call is used, the callback mechanism is the only way for an application
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * to free the item data if it was dynamically allocated.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * The table sequence number may be modified here.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Returns 0 if the handle is valid; otherwise returns -1.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * We have a marked item: remove it.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Since the key and the item were allocated as
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * a single chunk, we only need one free here.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw return (0);
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * ht_mark_delete
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * This function marks an item for deletion, which may be useful when
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * using findfirst/findnext to avoid modifying the table during the
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * table scan. Marked items can be removed later using ht_clean_table.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * ht_clear_delete
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * This function clear an item from marked for deletion list.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * ht_bucket_search
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Returns first item which is not marked as deleted
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * in the specified bucket by 'head'
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw while ((item != 0) && (item->hi_flags & HTIF_MARKED_DELETED))
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * ht_findfirst
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * This function is used to begin an iteration through the hash table.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * The iterator is initialized and the first item in the table (as
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * determined by the hash algorithm) is returned. The current sequence
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * number is stored in the iterator to determine whether or not the
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * the table has changed between calls. If the table is empty, a null
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * pointer is returned.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw if (handle == 0 || iterator == 0 || handle->ht_total_items == 0)
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw for (h_index = 0; h_index < handle->ht_table_size; ++h_index) {
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw item = ht_bucket_search(handle->ht_table[h_index].he_head);
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw if (item != 0) {
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * ht_findnext
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Find the next item in the table for the given iterator. Iterators must
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * be initialized by ht_findfirst, which will also return the first item
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * in the table. If an item is available, a pointer to it is returned.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Otherwise a null pointer is returned. A null pointer may indicate:
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * - an invalid iterator (i.e. ht_findfirst has not been called)
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * - the table has changed since the previous findfirst/findnext
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * - the entire table has been traversed
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * The caller can use ht_get_total_items to determine whether or not all
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * of the items in the table have been visited.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw /* Invalid iterator */
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * No more items or the table has changed
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * since the last call.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Check for another item in the current bucket.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw if (item != 0) {
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * Nothing else in the current bucket. Look for another
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw * bucket with something in it and return the head item.
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw for (index = iterator->hti_index + 1; index < total; ++index) {
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw item = ht_bucket_search(handle->ht_table[index].he_head);
da6c28aaf62fa55f0fdb8004aa40f88f23bf53f0amw if (item != 0) {