[1] | 1 | /* |
---|
| 2 | * xhtab.h - Remote access embedded hash table definition. |
---|
| 3 | * |
---|
[459] | 4 | * Author Alain Greiner (2016,2017,2018) |
---|
[1] | 5 | * |
---|
| 6 | * Copyright (c) UPMC Sorbonne Universites |
---|
| 7 | * |
---|
| 8 | * This file is part of ALMOS-MKH. |
---|
| 9 | * |
---|
| 10 | * ALMOS-MKH is free software; you can redistribute it and/or modify it |
---|
| 11 | * under the terms of the GNU General Public License as published by |
---|
| 12 | * the Free Software Foundation; version 2.0 of the License. |
---|
| 13 | * |
---|
| 14 | * ALMOS-MKH is distributed in the hope that it will be useful, but |
---|
| 15 | * WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
| 16 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
---|
| 17 | * General Public License for more details. |
---|
| 18 | * |
---|
| 19 | * You should have received a copy of the GNU General Public License |
---|
| 20 | * along with ALMOS-MKH; if not, write to the Free Software Foundation, |
---|
| 21 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA |
---|
| 22 | */ |
---|
| 23 | |
---|
| 24 | #ifndef _XHTAB_H_ |
---|
| 25 | #define _XHTAB_H_ |
---|
| 26 | |
---|
[14] | 27 | #include <kernel_config.h> |
---|
[457] | 28 | #include <hal_kernel_types.h> |
---|
[1] | 29 | #include <remote_rwlock.h> |
---|
| 30 | #include <xlist.h> |
---|
| 31 | |
---|
| 32 | |
---|
[23] | 33 | /////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 34 | // This file define a generic, embedded, remotely accessible hash table. |
---|
| 35 | // |
---|
| 36 | // It can be accessed by any thread, running in any cluster. |
---|
| 37 | // It is generic as it can be used to register various types of items. |
---|
[204] | 38 | // The main goal is to speedup search by key in a large number of items of same type. |
---|
[23] | 39 | // For this purpose the set of all registered items is split in several subsets. |
---|
[563] | 40 | // Each subset is organised as an embedded double linked xlists. |
---|
[188] | 41 | // - an item is uniquely identified by a <key>, that is a single uint32_t value. |
---|
[204] | 42 | // - From the <key> value, the hash table uses an item type specific xhtab_index() |
---|
| 43 | // function, to compute an <index> value, defining a subset of registered items. |
---|
[188] | 44 | // - to discriminate between items that have the same <index>, the hash table makes |
---|
[204] | 45 | // an associative search on the key in subset. |
---|
[23] | 46 | // - Each registered item is a structure, that must contain an embedded xlist_entry, |
---|
| 47 | // that is part of the xlist implementing the subset. |
---|
| 48 | // |
---|
[204] | 49 | // For all registered items, a total order is defined by the increasing index values, |
---|
| 50 | // and for each index value, by the position in the partial xlist. |
---|
[188] | 51 | // This order is used by the two functions xhtab_get_first() and xhtab_get_next(), that |
---|
| 52 | // are used to scan all registered items. The two "current_index" and "current_xlist_xp" |
---|
| 53 | // fields in the hash table header register the current item during a scan. |
---|
| 54 | // |
---|
| 55 | // Implementation Note: |
---|
[459] | 56 | // To inroduce a new item type, you must define the four item-type-specific |
---|
[188] | 57 | // functions specified below, and you must update the xhtab_init() function |
---|
| 58 | // and the xhtab_item_type_t. |
---|
[23] | 59 | /////////////////////////////////////////////////////////////////////////////////////////// |
---|
[1] | 60 | |
---|
[204] | 61 | #define XHASHTAB_SIZE 8 // number of subsets |
---|
[1] | 62 | |
---|
| 63 | /****************************************************************************************** |
---|
[204] | 64 | * This define the four item_type_specific function prototypes that must be defined |
---|
| 65 | * for each item type. |
---|
[1] | 66 | *****************************************************************************************/ |
---|
| 67 | |
---|
[204] | 68 | typedef bool_t (item_match_key_t) ( xptr_t item_xp , void * key ); |
---|
| 69 | typedef xptr_t (item_from_xlist_t) ( xptr_t xlist_xp ); |
---|
| 70 | typedef uint32_t (index_from_key_t) ( void * key ); |
---|
| 71 | typedef void (item_print_key_t) ( xptr_t item_xp ); |
---|
[23] | 72 | |
---|
[1] | 73 | /****************************************************************************************** |
---|
| 74 | * This define the supported item types. |
---|
[610] | 75 | * - The XHTAB_DENTRY_TYPE is used to implement the set of directory entries for a |
---|
| 76 | * directory inode : the "children" inode field is an embedded xhtab. |
---|
[1] | 77 | *****************************************************************************************/ |
---|
| 78 | |
---|
| 79 | typedef enum |
---|
| 80 | { |
---|
[23] | 81 | XHTAB_DENTRY_TYPE = 0, /*! item is a vfs_dentry_t */ |
---|
[1] | 82 | } |
---|
| 83 | xhtab_item_type_t; |
---|
| 84 | |
---|
| 85 | /****************************************************************************************** |
---|
[459] | 86 | * This structure define the root of the remotely accessible hash table. |
---|
[1] | 87 | *****************************************************************************************/ |
---|
| 88 | |
---|
| 89 | typedef struct xhtab_s |
---|
| 90 | { |
---|
[204] | 91 | xlist_entry_t roots[XHASHTAB_SIZE]; /*! array of roots of xlist */ |
---|
| 92 | index_from_key_t * index_from_key; /*! item specific function pointer */ |
---|
| 93 | item_match_key_t * item_match_key; /*! item specific function pointer */ |
---|
| 94 | item_from_xlist_t * item_from_xlist; /*! item specific function pointer */ |
---|
| 95 | item_print_key_t * item_print_key; /*! item specific function pointer */ |
---|
| 96 | uint32_t items; /*! number of registered items */ |
---|
[563] | 97 | remote_busylock_t lock; /*! lock protecting hash table accesses */ |
---|
[204] | 98 | uint32_t current_index; /*! current item subset index */ |
---|
| 99 | xptr_t current_xlist_xp; /*! xptr on current item xlist entry */ |
---|
[1] | 100 | } |
---|
| 101 | xhtab_t; |
---|
| 102 | |
---|
| 103 | /****************************************************************************************** |
---|
[23] | 104 | * This function initializes an empty hash table (zero registered item). |
---|
[1] | 105 | * The initialisation must be done by a thread running in cluster containing the table. |
---|
| 106 | ****************************************************************************************** |
---|
[204] | 107 | * @ xhtab : local pointer on local xhtab to be initialized. |
---|
| 108 | * @ type : item type (see above). |
---|
[1] | 109 | *****************************************************************************************/ |
---|
[23] | 110 | void xhtab_init( xhtab_t * xhtab, |
---|
| 111 | xhtab_item_type_t type ); |
---|
[1] | 112 | |
---|
| 113 | /****************************************************************************************** |
---|
| 114 | * This function safely register an item in the hash table, using the lock protecting it. |
---|
| 115 | ****************************************************************************************** |
---|
| 116 | * @ xhtab_xp : extended pointer on hash table. |
---|
| 117 | * @ key : local pointer on item identifier. |
---|
| 118 | * @ xlist_xp : extended pointer on xlist_entry_t embedded in item to be registered. |
---|
[23] | 119 | * @ return 0 if success / return EINVAL if item already registered. |
---|
[1] | 120 | *****************************************************************************************/ |
---|
[23] | 121 | error_t xhtab_insert( xptr_t xhtab_xp, |
---|
| 122 | void * key, |
---|
| 123 | xptr_t xlist_xp ); |
---|
[1] | 124 | |
---|
| 125 | /****************************************************************************************** |
---|
| 126 | * This function safely remove an item from the hash table, using the lock protecting it. |
---|
| 127 | ****************************************************************************************** |
---|
[459] | 128 | * @ xhtab_xp : extended pointer on hash table. |
---|
| 129 | * @ key : local pointer on item identifier. |
---|
| 130 | * @ xlist_xp : extended pointer on xlist_entry embedded in item to be removed. |
---|
[603] | 131 | * @ return 0 if item found / return false if item not found. |
---|
[1] | 132 | *****************************************************************************************/ |
---|
[603] | 133 | bool_t xhtab_remove( xptr_t xhtab_xp, |
---|
| 134 | void * key, |
---|
| 135 | xptr_t xlist_entry_xp ); |
---|
[1] | 136 | |
---|
| 137 | /****************************************************************************************** |
---|
| 138 | * This function search an item by its key in hash table, using the lock protecting it. |
---|
| 139 | ****************************************************************************************** |
---|
| 140 | * @ xhtab_xp : extended pointer on hash table. |
---|
| 141 | * @ key : local pointer on searched item identifier. |
---|
| 142 | * @ return extended pointer on the searched item if found / XPTR_NULL if not found. |
---|
| 143 | *****************************************************************************************/ |
---|
| 144 | xptr_t xhtab_lookup( xptr_t xhtab_xp, |
---|
| 145 | void * key ); |
---|
| 146 | |
---|
[188] | 147 | /****************************************************************************************** |
---|
| 148 | * This blocking function takes the lock protecting exclusive access to the hash table. |
---|
| 149 | * It should be called before the xhtab_get_first() & xhtab_get_next() functions. |
---|
| 150 | ****************************************************************************************** |
---|
| 151 | * @ xhtab_xp : extended pointer on hash table. |
---|
| 152 | *****************************************************************************************/ |
---|
[563] | 153 | void xhtab_lock( xptr_t xhtab_xp ); |
---|
[1] | 154 | |
---|
[188] | 155 | /****************************************************************************************** |
---|
| 156 | * This function releases the lock protecting exclusive access to the hash table. |
---|
| 157 | * It should be called after the xhtab_get_first() & xhtab_get_next() functions. |
---|
| 158 | ****************************************************************************************** |
---|
| 159 | * @ xhtab_xp : extended pointer on hash table. |
---|
| 160 | *****************************************************************************************/ |
---|
[563] | 161 | void xhtab_unlock( xptr_t xhtab_xp ); |
---|
[188] | 162 | |
---|
| 163 | /****************************************************************************************** |
---|
| 164 | * This function returns an extended pointer on the first item registered in hash table, |
---|
| 165 | * and register this pointer in the hash table header. |
---|
| 166 | * The lock protecting the hash table must have been previously taken by the caller. |
---|
| 167 | ****************************************************************************************** |
---|
| 168 | * @ xhtab_xp : extended pointer on hash table. |
---|
| 169 | * @ return extended pointer on item if success / XPTR_NULL if not found. |
---|
| 170 | *****************************************************************************************/ |
---|
| 171 | xptr_t xhtab_get_first( xptr_t xhtab_xp ); |
---|
| 172 | |
---|
| 173 | /****************************************************************************************** |
---|
| 174 | * This function returns an extended pointer on item following the currently pointed |
---|
| 175 | * item in the hash table header. |
---|
| 176 | * The lock protecting the hash table must have been previously taken by the caller. |
---|
| 177 | ****************************************************************************************** |
---|
| 178 | * @ xhtab_xp : extended pointer on hash table. |
---|
| 179 | * @ return extended pointer on item if success / XPTR_NULL if not found. |
---|
| 180 | *****************************************************************************************/ |
---|
| 181 | xptr_t xhtab_get_next( xptr_t xhtab_xp ); |
---|
| 182 | |
---|
[204] | 183 | /****************************************************************************************** |
---|
| 184 | * This function displays the full content of an xhtab. |
---|
| 185 | ****************************************************************************************** |
---|
| 186 | * @ xhtab_xp : extended pointer on hash table. |
---|
| 187 | *****************************************************************************************/ |
---|
| 188 | void xhtab_display( xptr_t xhtab_xp ); |
---|
[188] | 189 | |
---|
[1] | 190 | #endif /* _XHTAB_H_ */ |
---|