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

Last change on this file since 113 was 23, checked in by alain, 7 years ago

Introduce syscalls.
File size: 6.6 KB
RevLine 
[1]1/*
2 * xhtab.h - Remote access embedded hash table definition.
3 *
[23]4 * Author     Alain Greiner  (2016,2017)
[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>
[1]28#include <hal_types.h>
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.
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 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,
44//   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 another
46//   item type specific "xhtab_scan()" function for the associative search in subset.
47// - Each registered item is a structure, that must contain an embedded xlist_entry,
48//   that is part of the xlist implementing the subset.
49//
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.
53///////////////////////////////////////////////////////////////////////////////////////////
[1]54
55#define HASHTAB_SIZE    64   // number of subsets
56
57/******************************************************************************************
[23]58 * These typedef define the two item type specific function prototypes.
[1]59 *****************************************************************************************/
60
[23]61typedef  xptr_t    xhtab_scan_t( xptr_t xhtab_xp , uint32_t index , void * key );
62
[1]63typedef  uint32_t  xhtab_index_t( void * key );
64
65/******************************************************************************************
66 * This define the supported item types.
67 *****************************************************************************************/
68
69typedef enum
70{
[23]71    XHTAB_DENTRY_TYPE = 0,                    /*! item is a vfs_dentry_t                 */ 
[1]72}
73xhtab_item_type_t;
74
75/******************************************************************************************
[23]76 * This structure define the root of the remote accessible hash table.
[1]77 *****************************************************************************************/
78
79typedef struct xhtab_s
80{
81        xlist_entry_t      roots[HASHTAB_SIZE];   /*! array of roots of xlist                */
[23]82    xhtab_index_t    * index;                 /*! item specific function                 */
83    xhtab_scan_t     * scan;                  /*! item specific function                 */
[1]84    uint32_t           items;                 /*! number of registered items             */
[23]85    remote_rwlock_t    lock;                  /*! lock protecting hash table accesses    */
[1]86}
87xhtab_t;
88
89/******************************************************************************************
[23]90 * This function initializes an empty hash table (zero registered item).
[1]91 * The initialisation must be done by a thread running in cluster containing the table.
92 ******************************************************************************************
93 * @ xhtab   : local pointer on local xhtab to be initialized.
94 * @ type    : item type (see above).
95 *****************************************************************************************/
[23]96void xhtab_init( xhtab_t           * xhtab,
97                 xhtab_item_type_t   type );
[1]98
99/******************************************************************************************
100 * This function safely register an item in the hash table, using the lock protecting it.
101 ******************************************************************************************
102 * @ xhtab_xp   : extended pointer on hash table.
103 * @ key        : local pointer on item identifier.
104 * @ xlist_xp   : extended pointer on xlist_entry_t embedded in item to be registered.
[23]105 * @ return 0 if success / return EINVAL if item already registered.
[1]106 *****************************************************************************************/
[23]107error_t xhtab_insert( xptr_t   xhtab_xp,
108                      void   * key,
109                      xptr_t   xlist_xp );
[1]110
111/******************************************************************************************
112 * This function safely remove an item from the hash table, using the lock protecting it.
113 ******************************************************************************************
[23]114 * @ xhtab_xp       : extended pointer on hash table.
115 * @ key            : local pointer on item identifier.
116 * @ xlist_entry_xp : extended pointer on xlist_entry embedded in item to be removed.
117 * @ return 0 if success / return EINVAL if item not found.
[1]118 *****************************************************************************************/
[23]119error_t xhtab_remove( xptr_t   xhtab_xp,
120                      void   * key,
121                      xptr_t   xlist_entry_xp );
[1]122
123/******************************************************************************************
124 * This function search an item by its key in hash table, using the lock protecting it.
125 ******************************************************************************************
126 * @ xhtab_xp  : extended pointer on hash table.
127 * @ key       : local pointer on searched item identifier.
128 * @ return extended pointer on the searched item if found / XPTR_NULL if not found.
129 *****************************************************************************************/
130xptr_t  xhtab_lookup( xptr_t    xhtab_xp,
131                      void    * key );
132
133
134#endif  /* _XHTAB_H_ */
Note: See TracBrowser for help on using the repository browser.