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