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