usr/src/uts/common/smbsrv/hash_table.h

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21 /*
  22  * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
  23  * Use is subject to license terms.
  24  */
  25
  26 #ifndef _SMBSRV_HASH_TABLE_H
  27 #define _SMBSRV_HASH_TABLE_H
  28
  29 #pragma ident   "%Z%%M% %I%     %E% SMI"
  30
  31 /*
  32  *
  33  * Interface definition for the hash table library. The hash table is a
  34  * user-specified array of pointers to items. Hash collisions are handled
  35  * using linked lists from the table entries. A handle is associated with
  36  * each table, which is used to maintain the hash table.
  37  *
  38  * +------+     +-------+    +----+    +----+
  39  * |handle|---> |index 0|--->|item|--->|item|--->
  40  * | ...  |     +-------+    +----+    +----+
  41  * | ...  |     |index 1|--->
  42  * +------+     +-------+    +----+    +----+    +----+
  43  *              |index 2|--->|item|--->|item|--->|item|--->
  44  *              +-------+    +----+    +----+    +----+
  45  *              | ...   |--->
  46  *              +-------+
  47  *              | ...   |--->
  48  *              +-------+
  49  *              |index n|--->
  50  *              +-------+
  51  *
  52  */
  53
  54 #include <sys/types.h>
  55
  56 #ifdef __cplusplus
  57 extern "C" {
  58 #endif
  59
  60 /*
  61  * This is the hash multiplier value.
  62  */
  63 #define HASH_MESH_VALUE         77
  64
  65 /*
  66  * Each entry (item) in the hash table has a linked-list pointer, a key,
  67  * a pointer to some user defined data (which may be null) and some flags.
  68  * The key is a user provided key and is used to position the item within
  69  * the table. The linked-list is used to store items whose hash values
  70  * collide. The data pointer is never dereferenced in the hash code so
  71  * it may be a null pointer.
  72  *
  73  * The item bit flags are:
  74  *
  75  * HTIF_DELETE:    Specifies that an item is marked for deletion (see
  76  *               ht_mark_delete and ht_clean_table).
  77  */
  78 #define HTIF_MARKED_DELETED     0x01
  79 #define HT_DELETE               HTIF_MARKED_DELETED
  80
  81 typedef struct ht_item {
  82         struct ht_item *hi_next;
  83         char *hi_key;
  84         void *hi_data;
  85         size_t hi_flags;
  86 } HT_ITEM;
  87
  88 /*
  89  * HT_TABLE_ENTRY is an opaque structure (to the public) used to maintain
  90  * a pointer to the hash table and the number of items in the table entry.
  91  * This number shows number of both available items and those are marked
  92  * as deleted.
  93  */
  94 typedef struct ht_table_entry {
  95         HT_ITEM *he_head;
  96         size_t he_count;
  97 } HT_TABLE_ENTRY;
  98
  99 /*
 100  * The HT_HANDLE is an opaque handle that associates each request with
 101  * a hash table. A handle is generated when a hash table is created and
 102  * it is used to maintain all global data associated with the table.
 103  *
 104  * The handle bit flags are:
 105  *
 106  * HTHF_FIXED_KEY:    Specifies that keys are fixed length and should
 107  *                    not be assumed to be null terminated.
 108  */
 109 #define HTHF_FIXED_KEY          0x01
 110
 111 typedef struct ht_handle {
 112         HT_TABLE_ENTRY *ht_table;
 113         size_t ht_sequence;
 114         size_t ht_table_size;
 115         size_t ht_table_mask;
 116         size_t ht_key_size;
 117         size_t ht_total_items;  /* show total number of available items */
 118         size_t ht_flags;
 119         size_t (*ht_hash)(struct ht_handle *handle, const char *key);
 120         void (*ht_callback)(HT_ITEM *item);
 121         int (*ht_cmp)(const char *key1, const char *key2, size_t n);
 122 } HT_HANDLE;
 123
 124 /*
 125  * Typedefs for the optional user-installable functions.
 126  */
 127 typedef void (*HT_CALLBACK)(HT_ITEM *item);
 128
 129 /*
 130  * Compare function cast to make all compare
 131  * functions look like strncmp.
 132  */
 133 typedef int (*HT_CMP)(const char *, const char *, size_t);
 134
 135 /*
 136  * Iterator used with ht_findfirst and ht_findnext to walk through
 137  * all the items in a hash table. The iterator should be treated as
 138  * an opaque handle. The sequence number in the iterator is used
 139  * to maintain consistency with the table on which the iteration
 140  * is being performed. If the table sequence number changes, the
 141  * iterator becomes invalid.
 142  */
 143 typedef struct ht_iterator {
 144         HT_HANDLE *hti_handle;
 145         HT_ITEM *hti_item;
 146         size_t hti_index;
 147         size_t hti_sequence;
 148 } HT_ITERATOR;
 149
 150 /*
 151  * Public API to create and destroy hash tables, to change the hash
 152  * function and to find out how many items are in a hash table.
 153  */
 154 extern HT_HANDLE *ht_create_table(size_t table_size, size_t key_size,
 155     size_t flags);
 156 extern void ht_destroy_table(HT_HANDLE *handle);
 157 extern void ht_set_cmpfn(HT_HANDLE *handle, HT_CMP cmpfn);
 158 extern size_t ht_get_total_items(HT_HANDLE *handle);
 159
 160 /*
 161  * Public API to add, remove, replace or find specific items
 162  * in a hash table.
 163  */
 164 extern HT_ITEM *ht_add_item(HT_HANDLE *handle, const char *key,
 165     const void *data);
 166 extern HT_ITEM *ht_replace_item(HT_HANDLE *handle, const char *key,
 167     const void *data);
 168 extern void *ht_remove_item(HT_HANDLE *handle, const char *key);
 169 extern HT_ITEM *ht_find_item(HT_HANDLE *handle, const char *key);
 170
 171 /*
 172  * Public API to iterate over a hash table. A mechanism is provided to
 173  * mark items for deletion while searching the table so that the table
 174  * is not modified during the search. When the search is complete, all
 175  * of the marked items can be deleted by calling ht_clean_table. If
 176  * the item data has been dynamically allocated, a callback can be
 177  * registered to free the memory. The callback will be invoked with a
 178  * pointer to each item as it is removed from the hash table.
 179  */
 180 extern HT_ITEM *ht_findfirst(HT_HANDLE *handle, HT_ITERATOR *iterator);
 181 extern HT_ITEM *ht_findnext(HT_ITERATOR *iterator);
 182 extern void ht_mark_delete(HT_HANDLE *handle, HT_ITEM *item);
 183 extern void ht_clear_delete(HT_HANDLE *handle, HT_ITEM *item);
 184 extern size_t ht_clean_table(HT_HANDLE *handle);
 185 extern HT_CALLBACK ht_register_callback(HT_HANDLE *handle,
 186     HT_CALLBACK callback);
 187
 188 #ifdef __cplusplus
 189 }
 190 #endif
 191
 192 #endif /* _SMBSRV_HASH_TABLE_H */