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 */ 193