source: trunk/kernel/libk/xhtab.c @ 7

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

First import

File size: 8.3 KB
Line 
1/*
2 * xhtab.c - Remote access embedded hash table implementation.
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#include <almos_config.h>
25#include <hal_types.h>
26#include <hal_special.h>
27#include <hal_remote.h>
28#include <xlist.h>
29#include <remote_rwlock.h>
30#include <string.h>
31#include <printk.h>
32#include <xhtab.h>
33#include <vfs.h>
34
35
36///////////////////////////////////////////////////////////////////////////////////////
37// This static function s called by the xhtab_lookup() and xhtab_register() functions.
38// It scan one sub-list identified by  <index> to find an item  identified by <key>.
39// The hash table is identified by <cxy> and local pointer <xhtab>.
40// The sub-list is not modified, but the readlock must have been taken by the caller.
41///////////////////////////////////////////////////////////////////////////////////////
42// @ cxy       : hash table cluster.
43// @ xhtab_xp  : hash table local pointer.
44// @ index     : index of sub-list to be scanned.
45// @ key       : local pointer on item identifier.
46///////////////////////////////////////////////////////////////////////////////////////
47static xptr_t xhtab_scan( cxy_t     cxy,
48                          xhtab_t * xhtab,
49                          uint32_t  index,
50                          void    * key )
51{
52    xptr_t   xlist_xp;    // extended pointer on xlist_entry_t (iterator)
53    xptr_t   item_xp;     // extended pointer on found item (return value)
54   
55    // scan the sub-list[index]
56        XLIST_FOREACH( XPTR( cxy , &xhtab->roots[index] ) , xlist_xp )
57        {
58        if ( xhtab->compare( xlist_xp , key , &item_xp ) ) return item_xp;
59    }
60
61    // no matching item found
62        return XPTR_NULL;
63}
64
65/////////////////////////////////
66void xhtab_init( xhtab_t * xhtab,
67                 uint32_t  type )
68{
69        uint32_t i;
70
71    // initialize readlock
72    remote_rwlock_init( XPTR( local_cxy , &xhtab->lock) );
73
74    xhtab->items  = 0;
75
76    if( type == XHTAB_DENTRY_TYPE )
77    {
78        hal_remote_spt( XPTR( local_cxy , &xhtab->compare ) , &xhtab_dentry_compare );
79        hal_remote_spt( XPTR( local_cxy , &xhtab->index   ) , &xhtab_dentry_index   );
80    }
81    else
82    {
83        printk("\n[PANIC] in %s : illegal item type\n", __FUNCTION__ );
84        hal_core_sleep();
85    }
86
87        for( i=0 ; i < HASHTAB_SIZE ; i++ )
88    {
89                xlist_root_init( XPTR( local_cxy , &xhtab->roots[i] ) );
90    } 
91}
92
93///////////////////////////////////////
94void xhtab_register( xptr_t   xhtab_xp,
95                     void   * key,
96                     xptr_t   xlist_xp )
97{
98    // get xhtab cluster and local pointer
99    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
100    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
101
102    // compute index from key
103        uint32_t index = xhtab_ptr->index( key );
104
105    // take the lock protecting hash table
106    remote_rwlock_wr_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
107
108    // register item in hash table
109        xlist_add_last( XPTR( xhtab_cxy , &xhtab_ptr->roots[index] ) , xlist_xp );
110
111    // update number of registered items
112    hal_remote_atomic_add( XPTR( xhtab_cxy , &xhtab_ptr->items ) , 1 );
113
114    // release the lock protecting hash table
115    remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
116
117}  // end xhtab_register()
118
119/////////////////////////////////////
120void xhtab_remove( xptr_t   xhtab_xp,
121                   void   * key )
122{
123    // get xhtab cluster and local pointer
124    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
125    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
126
127    // take the lock protecting hash table
128    remote_rwlock_wr_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
129
130    // compute index from key
131        uint32_t index = xhtab_ptr->index( key );
132
133    // get extended pointer on item to remove
134    xptr_t item_xp = xhtab_scan( xhtab_cxy , xhtab_ptr , index , key );
135
136    if( item_xp == XPTR_NULL )    // do nothing if not found
137    {
138        // release the lock protecting hash table
139        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
140    }
141    else                          // remove item if found
142    {
143        // get item cluster and local pointer
144        cxy_t          item_cxy = GET_CXY( item_xp );
145        vfs_dentry_t * item_ptr = (vfs_dentry_t *)GET_PTR( item_xp );
146
147        // remove item from hash table <=> unlink xlist_entry_t
148        xlist_unlink( XPTR( item_cxy , &item_ptr->xlist ) );
149
150        // update number of registered items
151        hal_remote_atomic_add( XPTR( xhtab_cxy , &xhtab_ptr->items ) , -1 );
152
153        // release the lock protecting hash table
154        remote_rwlock_wr_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
155    }
156}  // end xhtab_unregister()
157
158/////////////////////////////////////////
159xptr_t  xhtab_lookup( xptr_t    xhtab_xp,
160                      void    * key )
161{
162    xptr_t  item_xp;
163
164    // get xhtab cluster and local pointer
165    cxy_t     xhtab_cxy = GET_CXY( xhtab_xp );
166    xhtab_t * xhtab_ptr = (xhtab_t *)GET_PTR( xhtab_xp );
167
168    // compute index from key
169        uint32_t index = xhtab_ptr->index( key );
170
171    // take the lock protecting hash table
172    remote_rwlock_rd_lock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
173
174    // scan sub-list
175    item_xp = xhtab_scan( xhtab_cxy , xhtab_ptr , index , key );
176
177    // release the lock protecting hash table
178    remote_rwlock_rd_unlock( XPTR( xhtab_cxy , &xhtab_ptr->lock ) );
179
180    return item_xp;
181
182}  // end xhtab_lookup()
183
184
185
186/////////////////////////////////////////
187uint32_t xhtab_dentry_index( void * key )
188{
189        char    * str   = key;
190        uint32_t  index = 0;
191 
192        while( *str ) index = index + (*(str++) ^ index);
193
194        return index % HASHTAB_SIZE;
195} 
196
197///////////////////////////////////////////////
198bool_t xhtab_dentry_compare( xptr_t   xlist_xp,
199                             void   * key,
200                             xptr_t * item_xp )
201{
202    char   tested_name[256];      // local copy of name stored in remote hash table
203
204    char * searched_name = key;   // local pointer on searched name
205
206    // compute name length
207    uint32_t length = strlen( searched_name );
208
209    // get extended pointer on dentry containing the xlist_entry_t
210        xptr_t dentry_xp = XLIST_ELEMENT( xlist_xp , vfs_dentry_t , xlist );
211
212    // get dentry cluster and local pointer
213    cxy_t          dentry_cxy = GET_CXY( dentry_xp );
214    vfs_dentry_t * dentry_ptr = (vfs_dentry_t *)GET_PTR( dentry_xp );
215   
216    // make a local copy of remote dentry name
217    hal_remote_memcpy( XPTR( local_cxy  , tested_name ) ,
218                       XPTR( dentry_cxy , dentry_ptr->name ) , length );
219
220    // check matching / return if match
221    if( strcmp( tested_name , searched_name ) == 0 )
222    {
223        return true;
224        *item_xp = dentry_xp;
225    }
226    else
227    {
228        return false;
229    }
230}
231
232
233 
234////////////////////////////////////////
235uint32_t xhtab_inode_index( void * key )
236{
237        uint32_t * inum = key;
238
239        return (((*inum) >> 16) ^ ((*inum) & 0xFFFF)) % HASHTAB_SIZE;
240} 
241
242///////////////////////////////////////////////
243bool_t xhtab_inode_compare( xptr_t   xlist_xp,
244                            void   * key,
245                            xptr_t * item_xp )
246{
247    uint32_t * searched_inum = key;
248    uint32_t   tested_inum;   
249
250    // get extended pointer on inode containing the xlist_entry_t
251        xptr_t inode_xp = XLIST_ELEMENT( xlist_xp , vfs_inode_t , xlist );
252
253    // get inode cluster and local pointer
254    cxy_t         inode_cxy = GET_CXY( inode_xp );
255    vfs_inode_t * inode_ptr = (vfs_inode_t *)GET_PTR( inode_xp );
256   
257    // get tested inode inum
258    tested_inum = hal_remote_lw( XPTR( inode_cxy , &inode_ptr->inum ) );
259
260    // check matching / return if match
261    if( tested_inum == *searched_inum )
262    {
263        return true;
264        *item_xp = inode_xp;
265    }
266    else
267    {
268        return false;
269    }
270} 
271
Note: See TracBrowser for help on using the repository browser.