source: trunk/kernel/libk/xhtab.h @ 194

Last change on this file since 194 was 188, checked in by alain, 7 years ago

Redefine the PIC device API.
File size: 9.6 KB
Line 
1/*
2 * xhtab.h - Remote access embedded hash table definition.
3 *
4 * Author     Alain Greiner  (2016,2017)
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
27#include <kernel_config.h>
28#include <hal_types.h>
29#include <remote_rwlock.h>
30#include <xlist.h>
31
32
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.
38// The main goal is to speedup search by key for a large number of items of same type.
39// For this purpose the set of all registered items is split in several subsets.
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,
43//   to compute an <index> value, defining a subset of registered items.
44// - to discriminate between items that have the same <index>, the hash table makes
45//   an associative search in subset.
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//
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.
59///////////////////////////////////////////////////////////////////////////////////////////
60
61#define XHASHTAB_SIZE    64   // number of subsets
62
63/******************************************************************************************
64 * This define the three item type specific function prototypes.
65 *****************************************************************************************/
66
67typedef  bool_t    xhtab_match_t ( xptr_t item_xp , void * key );
68typedef  xptr_t    xhtab_item_t  ( xptr_t xlist_xp );
69typedef  uint32_t  xhtab_index_t ( void * key );
70
71/******************************************************************************************
72 * This define the supported item types.
73 *****************************************************************************************/
74
75typedef enum
76{
77    XHTAB_DENTRY_TYPE = 0,                    /*! item is a vfs_dentry_t                 */ 
78}
79xhtab_item_type_t;
80
81/******************************************************************************************
82 * This structure define the root of the remote accessible hash table.
83 *****************************************************************************************/
84
85typedef struct xhtab_s
86{
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                 */
91    uint32_t           items;                 /*! number of registered items             */
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       */
95}
96xhtab_t;
97
98/******************************************************************************************
99 * This function initializes an empty hash table (zero registered item).
100 * The initialisation must be done by a thread running in cluster containing the table.
101 ******************************************************************************************
102 * @ xhtab   : local pointer on local xhtab to be initialized.
103 * @ type    : item type (see above).
104 *****************************************************************************************/
105void xhtab_init( xhtab_t           * xhtab,
106                 xhtab_item_type_t   type );
107
108/******************************************************************************************
109 * This function safely register an item in the hash table, using the lock protecting it.
110 ******************************************************************************************
111 * @ xhtab_xp   : extended pointer on hash table.
112 * @ key        : local pointer on item identifier.
113 * @ xlist_xp   : extended pointer on xlist_entry_t embedded in item to be registered.
114 * @ return 0 if success / return EINVAL if item already registered.
115 *****************************************************************************************/
116error_t xhtab_insert( xptr_t   xhtab_xp,
117                      void   * key,
118                      xptr_t   xlist_xp );
119
120/******************************************************************************************
121 * This function safely remove an item from the hash table, using the lock protecting it.
122 ******************************************************************************************
123 * @ xhtab_xp       : extended pointer on hash table.
124 * @ key            : local pointer on item identifier.
125 * @ xlist_entry_xp : extended pointer on xlist_entry embedded in item to be removed.
126 * @ return 0 if success / return EINVAL if item not found.
127 *****************************************************************************************/
128error_t xhtab_remove( xptr_t   xhtab_xp,
129                      void   * key,
130                      xptr_t   xlist_entry_xp );
131
132/******************************************************************************************
133 * This function search an item by its key in hash table, using the lock protecting it.
134 ******************************************************************************************
135 * @ xhtab_xp  : extended pointer on hash table.
136 * @ key       : local pointer on searched item identifier.
137 * @ return extended pointer on the searched item if found / XPTR_NULL if not found.
138 *****************************************************************************************/
139xptr_t  xhtab_lookup( xptr_t    xhtab_xp,
140                      void    * key );
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 *****************************************************************************************/
148void 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 *****************************************************************************************/
156void 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 *****************************************************************************************/
166xptr_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 *****************************************************************************************/
176xptr_t xhtab_get_next( xptr_t xhtab_xp );
177
178
179
180#endif  /* _XHTAB_H_ */
Note: See TracBrowser for help on using the repository browser.