Changeset 188 for trunk/kernel/libk/xhtab.h
- Timestamp:
- Jul 12, 2017, 8:12:41 PM (7 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/kernel/libk/xhtab.h
r23 r188 38 38 // The main goal is to speedup search by key for a large number of items of same type. 39 39 // For this purpose the set of all registered items is split in several subsets. 40 // Each subset is organised an embedded double linked lists. 41 // - an item is uniquely identified by a <key>, that can be a single uint32_t, 42 // a name (character string), or a more complex structure. 43 // - From the pointer on <key>, we use an item type specific xhtab_index() function, 40 // Each subset is organised as an embedded double linked lists. 41 // - an item is uniquely identified by a <key>, that is a single uint32_t value. 42 // - From the <key> value,the hash table uses an item type specific xhtab_index() function, 44 43 // to compute an <index> value, defining a subset of registered items. 45 // - to discriminate between items that have the same <index>, the hash table uses another46 // item type specific "xhtab_scan()" function for theassociative search in subset.44 // - to discriminate between items that have the same <index>, the hash table makes 45 // an associative search in subset. 47 46 // - Each registered item is a structure, that must contain an embedded xlist_entry, 48 47 // that is part of the xlist implementing the subset. 49 48 // 50 // Implementation Note: for each supported item type ***, you must define the two 51 // xhtab_***_index() and xhtab_***_scan() functions, and 52 // update the xhtab_init() function. 49 // A total order is defined for all registered items by the increasing index values, 50 // and for each index value by the position in the partial xlist. 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: 56 // For each supported item type ***, you must define the three item-type-specific 57 // functions specified below, and you must update the xhtab_init() function 58 // and the xhtab_item_type_t. 53 59 /////////////////////////////////////////////////////////////////////////////////////////// 54 60 55 #define HASHTAB_SIZE 64 // number of subsets61 #define XHASHTAB_SIZE 64 // number of subsets 56 62 57 63 /****************************************************************************************** 58 * Th ese typedef define the twoitem type specific function prototypes.64 * This define the three item type specific function prototypes. 59 65 *****************************************************************************************/ 60 66 61 typedef xptr_t xhtab_scan_t( xptr_t xhtab_xp , uint32_t index, void * key );62 63 typedef uint32_t xhtab_index_t ( void * key );67 typedef bool_t xhtab_match_t ( xptr_t item_xp , void * key ); 68 typedef xptr_t xhtab_item_t ( xptr_t xlist_xp ); 69 typedef uint32_t xhtab_index_t ( void * key ); 64 70 65 71 /****************************************************************************************** … … 79 85 typedef struct xhtab_s 80 86 { 81 xlist_entry_t roots[HASHTAB_SIZE]; /*! array of roots of xlist */ 82 xhtab_index_t * index; /*! item specific function */ 83 xhtab_scan_t * scan; /*! item specific function */ 87 xlist_entry_t roots[XHASHTAB_SIZE]; /*! array of roots of xlist */ 88 xhtab_index_t * index_from_key; /*! item specific function */ 89 xhtab_match_t * item_match_key; /*! item specific function */ 90 xhtab_item_t * item_from_xlist; /*! item specific function */ 84 91 uint32_t items; /*! number of registered items */ 85 92 remote_rwlock_t lock; /*! lock protecting hash table accesses */ 93 uint32_t current_index; /*! current item subset index */ 94 xptr_t * current_xlist_xp; /*! xptr on current item xlist entry */ 86 95 } 87 96 xhtab_t; … … 131 140 void * key ); 132 141 142 /****************************************************************************************** 143 * This blocking function takes the lock protecting exclusive access to the hash table. 144 * It should be called before the xhtab_get_first() & xhtab_get_next() functions. 145 ****************************************************************************************** 146 * @ xhtab_xp : extended pointer on hash table. 147 *****************************************************************************************/ 148 void xhtab_read_lock( xptr_t xhtab_xp ); 149 150 /****************************************************************************************** 151 * This function releases the lock protecting exclusive access to the hash table. 152 * It should be called after the xhtab_get_first() & xhtab_get_next() functions. 153 ****************************************************************************************** 154 * @ xhtab_xp : extended pointer on hash table. 155 *****************************************************************************************/ 156 void xhtab_read_unlock( xptr_t xhtab_xp ); 157 158 /****************************************************************************************** 159 * This function returns an extended pointer on the first item registered in hash table, 160 * and register this pointer in the hash table header. 161 * The lock protecting the hash table must have been previously taken by the caller. 162 ****************************************************************************************** 163 * @ xhtab_xp : extended pointer on hash table. 164 * @ return extended pointer on item if success / XPTR_NULL if not found. 165 *****************************************************************************************/ 166 xptr_t xhtab_get_first( xptr_t xhtab_xp ); 167 168 /****************************************************************************************** 169 * This function returns an extended pointer on item following the currently pointed 170 * item in the hash table header. 171 * The lock protecting the hash table must have been previously taken by the caller. 172 ****************************************************************************************** 173 * @ xhtab_xp : extended pointer on hash table. 174 * @ return extended pointer on item if success / XPTR_NULL if not found. 175 *****************************************************************************************/ 176 xptr_t xhtab_get_next( xptr_t xhtab_xp ); 177 178 133 179 134 180 #endif /* _XHTAB_H_ */
Note: See TracChangeset
for help on using the changeset viewer.