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

Last change on this file since 2 was 1, checked in by alain, 8 years ago

First import
File size: 9.4 KB
Line 
1/*
2 * xhtab.h - Remote access embedded hash table definition.
3 *
4 * Author     Alain Greiner          (2016)
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 <almos_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, hash table that can be remotely accessed by
35 * any thread running in any cluster.
36 * The main goal is to speedup search by key in a set of items identified by their key.
37 * For this purpose the set of all registered items is split in several subsets:
38 * Each subset is organised an embedded double linked lists.
39 * - an item is uniquely identified by a <key>, that can be a single uint32_t,
40 *   a name (character string), or a more complex structure.
41 * - From the <key>, the hash table uses an item type specific "xhtab_index()" function,
42 *   to compute an <index> value, defining a subset of registered items.
43 * - to discriminate between items that have the same <index>, the hash table uses another
44 *   item type specific "xhtab_compare()" function for the associative search in subset.
45 * - Each registered item is a structure, that must contain an embedded xlist_entry,
46 *   that is part of the xlist implementing the subset.
47 * - The xhtab header contains an array indexed by <index> and containing the roots
48 *   of the various xlists implementing the subsets.
49 *   pointer on the searched item can be obtained by a simple offset.
50 * Implementation note:
51 * to use this generic infrastructure for a new type of item, you must define a new
52 * type in the xhtan_item_type_t" below, and to define the two  associated
53 * "xhtab_compare() and xhtab_index().
54 *****************************************************************************************/
55
56#define HASHTAB_SIZE    64   // number of subsets
57
58/******************************************************************************************
59 * These typedef define the generic xhtab_compare() and xhtab_index() function prototypes.
60 * It must exist a specific couple of functions for each item type.
61 * @ entry_xp : extended pointer on an xlist_entry_t in a partial xlist.
62 * @ key      : local pointer on the searched item key.
63 * @ item_xp  : buffer to store extended pointer on found item.
64 *****************************************************************************************/
65
66typedef  bool_t    xhtab_compare_t( xptr_t entry_xp , void * key , xptr_t * item_xp );
67typedef  uint32_t  xhtab_index_t( void * key );
68
69/******************************************************************************************
70 * This define the supported item types.
71 *****************************************************************************************/
72
73typedef enum
74{
75    XHTAB_DENTRY_TYPE = 1,                   /*! item is a vfs_dentry_t                  */
76    XHTAB_INODE_TYPE  = 2,                   /*! item is a vfs_inode_t                   */
77}
78xhtab_item_type_t;
79
80/******************************************************************************************
81 * This structure define the root of a generic, remote accessible, hash table.
82 *****************************************************************************************/
83
84typedef struct xhtab_s
85{
86        xlist_entry_t      roots[HASHTAB_SIZE];   /*! array of roots of xlist                */
87    xhtab_compare_t  * compare;               /*! item specific index function           */
88    xhtab_index_t    * index;                 /*! item specific compare function         */
89    uint32_t           items;                 /*! number of registered items             */
90    remote_rwlock_t  lock;                  /*! lock protecting hash table modifs      */
91}
92xhtab_t;
93
94/******************************************************************************************
95 * This function initializes an empty hash table (zero children).
96 * The initialisation must be done by a thread running in cluster containing the table.
97 ******************************************************************************************
98 * @ xhtab   : local pointer on local xhtab to be initialized.
99 * @ type    : item type (see above).
100 *****************************************************************************************/
101void xhtab_init( xhtab_t * xhtab,
102                 uint32_t  type );
103
104/******************************************************************************************
105 * This function safely register an item in the hash table, using the lock protecting it.
106 ******************************************************************************************
107 * @ xhtab_xp   : extended pointer on hash table.
108 * @ key        : local pointer on item identifier.
109 * @ xlist_xp   : extended pointer on xlist_entry_t embedded in item to be registered.
110 *****************************************************************************************/
111void xhtab_register( xptr_t   xhtab_xp,
112                     void   * key,
113                     xptr_t   xlist_xp );
114
115/******************************************************************************************
116 * This function safely remove an item from the hash table, using the lock protecting it.
117 ******************************************************************************************
118 * @ xhtab_xp : extended pointer on hash table.
119 * @ key      : local pointer on item identifier.
120 *****************************************************************************************/
121void xhtab_remove( xptr_t   xhtab_xp,
122                   void   * key );
123
124/******************************************************************************************
125 * This function search an item by its key in hash table, using the lock protecting it.
126 ******************************************************************************************
127 * @ xhtab_xp  : extended pointer on hash table.
128 * @ key       : local pointer on searched item identifier.
129 * @ return extended pointer on the searched item if found / XPTR_NULL if not found.
130 *****************************************************************************************/
131xptr_t  xhtab_lookup( xptr_t    xhtab_xp,
132                      void    * key );
133
134
135/************************  vfs_dentry_t specific functions  ******************************/
136
137/******************************************************************************************
138 * This function compute the hash index from the key, when the item is a vhs_dentry_t.
139 ******************************************************************************************
140 * @ key      : local pointer on dentry name.
141 * @ return the index value, from 0 to (HASHTAB_SIZE - 1)
142 *****************************************************************************************/
143uint32_t xhtab_dentry_index( void * key );
144
145/******************************************************************************************
146 * This function check the key value for a given item, when the item is a vhs_dentry_t.
147 ******************************************************************************************
148 * @ xlist_xp : extended pointer on xlist_entry_t contained in a vfs_dentry_t.
149 * @ key      : local pointer on searched dentry name.
150 * @ return true if the item name matches the searched name.
151 *****************************************************************************************/
152bool_t xhtab_dentry_compare( xptr_t   xlist_xp,
153                             void   * key,
154                             xptr_t * item_xp );
155
156
157/************************  vfs_inode_t specific functions  *******************************/
158
159/******************************************************************************************
160 * This function compute the hash index from the key, when the item is a vhs_inode_t.
161 ******************************************************************************************
162 * @ key      : local pointer on dentry name.
163 * @ return the index value, from 0 to (HASHTAB_SIZE - 1)
164 *****************************************************************************************/
165uint32_t xhtab_inode_index( void * key );
166
167/******************************************************************************************
168 * This function check the key value for a given item, when the item is a vhs_inode_t.
169 ******************************************************************************************
170 * @ xlist_xp : extended pointer on xlist_entry_t contained in a vfs_dentry_t.
171 * @ key      : local pointer on searched dentry name.
172 * @ return true if the item name matches the searched name.
173 *****************************************************************************************/
174bool_t xhtab_inode_compare( xptr_t   xlist_xp,
175                            void   * key,
176                            xptr_t * item_xp );
177
178#endif  /* _XHTAB_H_ */
Note: See TracBrowser for help on using the repository browser.