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 /*
  30  *
  31  * Interface definition for the hash table library. The hash table is a
  32  * user-specified array of pointers to items. Hash collisions are handled
  33  * using linked lists from the table entries. A handle is associated with
  34  * each table, which is used to maintain the hash table.
  35  *
  36  * +------+     +-------+    +----+    +----+
  37  * |handle|---> |index 0|--->|item|--->|item|--->
  38  * | ...  |     +-------+    +----+    +----+
  39  * | ...  |     |index 1|--->
  40  * +------+     +-------+    +----+    +----+    +----+
  41  *              |index 2|--->|item|--->|item|--->|item|--->
  42  *              +-------+    +----+    +----+    +----+
  43  *              | ...   |--->
  44  *              +-------+
  45  *              | ...   |--->
  46  *              +-------+
  47  *              |index n|--->
  48  *              +-------+
  49  *
  50  */
  51
  52 #include <sys/types.h>
  53
  54 #ifdef __cplusplus
  55 extern "C" {
  56 #endif
  57
  58 /*
  59  * This is the hash multiplier value.
  60  */
  61 #define HASH_MESH_VALUE         77
  62
  63 /*
  64  * Each entry (item) in the hash table has a linked-list pointer, a key,
  65  * a pointer to some user defined data (which may be null) and some flags.
  66  * The key is a user provided key and is used to position the item within
  67  * the table. The linked-list is used to store items whose hash values
  68  * collide. The data pointer is never dereferenced in the hash code so
  69  * it may be a null pointer.
  70  *
  71  * The item bit flags are:
  72  *
  73  * HTIF_DELETE:    Specifies that an item is marked for deletion (see
  74  *               ht_mark_delete and ht_clean_table).
  75  */
  76 #define HTIF_MARKED_DELETED     0x01
  77 #define HT_DELETE               HTIF_MARKED_DELETED
  78
  79 typedef struct ht_item {
  80         struct ht_item *hi_next;
  81         char *hi_key;
  82         void *hi_data;
  83         size_t hi_flags;
  84 } HT_ITEM;
  85
  86 /*
  87  * HT_TABLE_ENTRY is an opaque structure (to the public) used to maintain
  88  * a pointer to the hash table and the number of items in the table entry.
  89  * This number shows number of both available items and those are marked
  90  * as deleted.
  91  */
  92 typedef struct ht_table_entry {
  93         HT_ITEM *he_head;
  94         size_t he_count;
  95 } HT_TABLE_ENTRY;
  96
  97 /*
  98  * The HT_HANDLE is an opaque handle that associates each request with
  99  * a hash table. A handle is generated when a hash table is created and
 100  * it is used to maintain all global data associated with the table.
 101  *
 102  * The handle bit flags are:
 103  *
 104  * HTHF_FIXED_KEY:    Specifies that keys are fixed length and should
 105  *                    not be assumed to be null terminated.
 106  */
 107 #define HTHF_FIXED_KEY          0x01
 108
 109 typedef struct ht_handle {
 110         HT_TABLE_ENTRY *ht_table;
 111         size_t ht_sequence;
 112         size_t ht_table_size;
 113         size_t ht_table_mask;
 114         size_t ht_key_size;
 115         size_t ht_total_items;  /* show total number of available items */
 116         size_t ht_flags;
 117         size_t (*ht_hash)(struct ht_handle *handle, const char *key);
 118         void (*ht_callback)(HT_ITEM *item);
 119         int (*ht_cmp)(const char *key1, const char *key2, size_t n);
 120 } HT_HANDLE;
 121
 122 /*
 123  * Typedefs for the optional user-installable functions.
 124  */
 125 typedef void (*HT_CALLBACK)(HT_ITEM *item);
 126
 127 /*
 128  * Compare function cast to make all compare
 129  * functions look like strncmp.
 130  */
 131 typedef int (*HT_CMP)(const char *, const char *, size_t);
 132
 133 /*
 134  * Iterator used with ht_findfirst and ht_findnext to walk through
 135  * all the items in a hash table. The iterator should be treated as
 136  * an opaque handle. The sequence number in the iterator is used
 137  * to maintain consistency with the table on which the iteration
 138  * is being performed. If the table sequence number changes, the
 139  * iterator becomes invalid.
 140  */
 141 typedef struct ht_iterator {
 142         HT_HANDLE *hti_handle;
 143         HT_ITEM *hti_item;
 144         size_t hti_index;
 145         size_t hti_sequence;
 146 } HT_ITERATOR;
 147
 148 /*
 149  * Public API to create and destroy hash tables, to change the hash
 150  * function and to find out how many items are in a hash table.
 151  */
 152 extern HT_HANDLE *ht_create_table(size_t table_size, size_t key_size,
 153     size_t flags);
 154 extern void ht_destroy_table(HT_HANDLE *handle);
 155 extern void ht_set_cmpfn(HT_HANDLE *handle, HT_CMP cmpfn);
 156 extern size_t ht_get_total_items(HT_HANDLE *handle);
 157
 158 /*
 159  * Public API to add, remove, replace or find specific items
 160  * in a hash table.
 161  */
 162 extern HT_ITEM *ht_add_item(HT_HANDLE *handle, const char *key,
 163     const void *data);
 164 extern HT_ITEM *ht_replace_item(HT_HANDLE *handle, const char *key,
 165     const void *data);
 166 extern void *ht_remove_item(HT_HANDLE *handle, const char *key);
 167 extern HT_ITEM *ht_find_item(HT_HANDLE *handle, const char *key);
 168
 169 /*
 170  * Public API to iterate over a hash table. A mechanism is provided to
 171  * mark items for deletion while searching the table so that the table
 172  * is not modified during the search. When the search is complete, all
 173  * of the marked items can be deleted by calling ht_clean_table. If
 174  * the item data has been dynamically allocated, a callback can be
 175  * registered to free the memory. The callback will be invoked with a
 176  * pointer to each item as it is removed from the hash table.
 177  */
 178 extern HT_ITEM *ht_findfirst(HT_HANDLE *handle, HT_ITERATOR *iterator);
 179 extern HT_ITEM *ht_findnext(HT_ITERATOR *iterator);
 180 extern void ht_mark_delete(HT_HANDLE *handle, HT_ITEM *item);
 181 extern void ht_clear_delete(HT_HANDLE *handle, HT_ITEM *item);
 182 extern size_t ht_clean_table(HT_HANDLE *handle);
 183 extern HT_CALLBACK ht_register_callback(HT_HANDLE *handle,
 184     HT_CALLBACK callback);
 185
 186 #ifdef __cplusplus
 187 }
 188 #endif
 189
 190 #endif /* _SMBSRV_HASH_TABLE_H */