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

Last change on this file since 267 was 204, checked in by alain, 7 years ago

Bug fix in kernel_init
-This line, and those below, will be ignored--

M params.mk
M kernel_config.h
M Makefile
M hdd/virt_hdd.dmg
M tools/bootloader_tsar/boot.c
M kernel/libk/bits.h
M kernel/libk/elf.c
M kernel/libk/xhtab.c
M kernel/libk/elf.h
M kernel/libk/xhtab.h
M kernel/devices/dev_pic.c
M kernel/mm/vmm.c
M kernel/mm/mapper.c
M kernel/mm/mapper.h
M kernel/vfs/devfs.h
M kernel/vfs/vfs.c
M kernel/vfs/vfs.h
M kernel/vfs/devfs.c
M kernel/kern/chdev.h
M kernel/kern/kernel_init.c
M kernel/kern/process.c
M kernel/kern/process.h
M hal/tsar_mips32/core/hal_remote.c
M hal/tsar_mips32/drivers/soclib_pic.c
File size: 10.2 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.
[204]38// The main goal is to speedup search by key in a large number of items of same type.
[23]39// For this purpose the set of all registered items is split in several subsets.
[188]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.
[204]42// - From the <key> value, the hash table uses an item type specific xhtab_index()
43//   function, to compute an <index> value, defining a subset of registered items.
[188]44// - to discriminate between items that have the same <index>, the hash table makes
[204]45//   an associative search on the key in subset.
[23]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//
[204]49// For all registered items, a total order is defined by the increasing index values,
50// and for each index value, by the position in the partial xlist.
[188]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:
[204]56// For each supported item type ***, you must define four item-type-specific
[188]57// functions specified below, and you must update the xhtab_init() function
58// and the xhtab_item_type_t.
[23]59///////////////////////////////////////////////////////////////////////////////////////////
[1]60
[204]61#define XHASHTAB_SIZE    8   // number of subsets
[1]62
63/******************************************************************************************
[204]64 * This define the four item_type_specific function prototypes that must be defined
65 * for each item type.
[1]66 *****************************************************************************************/
67
[204]68typedef  bool_t    (item_match_key_t)   ( xptr_t item_xp , void * key );
69typedef  xptr_t    (item_from_xlist_t)  ( xptr_t xlist_xp );
70typedef  uint32_t  (index_from_key_t)   ( void * key );
71typedef  void      (item_print_key_t)   ( xptr_t item_xp );
[23]72
[1]73/******************************************************************************************
74 * This define the supported item types.
75 *****************************************************************************************/
76
77typedef enum
78{
[23]79    XHTAB_DENTRY_TYPE = 0,                    /*! item is a vfs_dentry_t                 */ 
[1]80}
81xhtab_item_type_t;
82
83/******************************************************************************************
[23]84 * This structure define the root of the remote accessible hash table.
[1]85 *****************************************************************************************/
86
87typedef struct xhtab_s
88{
[204]89        xlist_entry_t       roots[XHASHTAB_SIZE];  /*! array of roots of xlist               */
90    index_from_key_t  * index_from_key;        /*! item specific function pointer        */
91    item_match_key_t  * item_match_key;        /*! item specific function pointer        */
92    item_from_xlist_t * item_from_xlist;       /*! item specific function pointer        */
93    item_print_key_t  * item_print_key;        /*! item specific function pointer        */
94    uint32_t            items;                 /*! number of registered items            */
95    remote_rwlock_t     lock;                  /*! lock protecting hash table accesses   */
96    uint32_t            current_index;         /*! current item subset index             */
97    xptr_t              current_xlist_xp;      /*! xptr on current item xlist entry      */
[1]98}
99xhtab_t;
100
101/******************************************************************************************
[23]102 * This function initializes an empty hash table (zero registered item).
[1]103 * The initialisation must be done by a thread running in cluster containing the table.
104 ******************************************************************************************
[204]105 * @ xhtab    : local pointer on local xhtab to be initialized.
106 * @ type     : item type (see above).
[1]107 *****************************************************************************************/
[23]108void xhtab_init( xhtab_t           * xhtab,
109                 xhtab_item_type_t   type );
[1]110
111/******************************************************************************************
112 * This function safely register an item in the hash table, using the lock protecting it.
113 ******************************************************************************************
114 * @ xhtab_xp   : extended pointer on hash table.
115 * @ key        : local pointer on item identifier.
116 * @ xlist_xp   : extended pointer on xlist_entry_t embedded in item to be registered.
[23]117 * @ return 0 if success / return EINVAL if item already registered.
[1]118 *****************************************************************************************/
[23]119error_t xhtab_insert( xptr_t   xhtab_xp,
120                      void   * key,
121                      xptr_t   xlist_xp );
[1]122
123/******************************************************************************************
124 * This function safely remove an item from the hash table, using the lock protecting it.
125 ******************************************************************************************
[23]126 * @ xhtab_xp       : extended pointer on hash table.
127 * @ key            : local pointer on item identifier.
128 * @ xlist_entry_xp : extended pointer on xlist_entry embedded in item to be removed.
129 * @ return 0 if success / return EINVAL if item not found.
[1]130 *****************************************************************************************/
[23]131error_t xhtab_remove( xptr_t   xhtab_xp,
132                      void   * key,
133                      xptr_t   xlist_entry_xp );
[1]134
135/******************************************************************************************
136 * This function search an item by its key in hash table, using the lock protecting it.
137 ******************************************************************************************
138 * @ xhtab_xp  : extended pointer on hash table.
139 * @ key       : local pointer on searched item identifier.
140 * @ return extended pointer on the searched item if found / XPTR_NULL if not found.
141 *****************************************************************************************/
142xptr_t  xhtab_lookup( xptr_t    xhtab_xp,
143                      void    * key );
144
[188]145/******************************************************************************************
146 * This blocking function takes the lock protecting exclusive access to the hash table.
147 * It should be called before the xhtab_get_first() & xhtab_get_next() functions.
148 ******************************************************************************************
149 * @ xhtab_xp  : extended pointer on hash table.
150 *****************************************************************************************/
151void xhtab_read_lock( xptr_t xhtab_xp );
[1]152
[188]153/******************************************************************************************
154 * This function releases the lock protecting exclusive access to the hash table.
155 * It should be called after the xhtab_get_first() & xhtab_get_next() functions.
156 ******************************************************************************************
157 * @ xhtab_xp  : extended pointer on hash table.
158 *****************************************************************************************/
159void xhtab_read_unlock( xptr_t xhtab_xp );
160
161/******************************************************************************************
162 * This function returns an extended pointer on the first item registered in hash table,
163 * and register this pointer in the hash table header.
164 * The lock protecting the hash table must have been previously taken by the caller.
165 ******************************************************************************************
166 * @ xhtab_xp  : extended pointer on hash table.
167 * @ return extended pointer on item if success / XPTR_NULL if not found.
168 *****************************************************************************************/
169xptr_t xhtab_get_first( xptr_t xhtab_xp );
170
171/******************************************************************************************
172 * This function returns an extended pointer on item following the currently pointed
173 * item in the hash table header.
174 * The lock protecting the hash table must have been previously taken by the caller.
175 ******************************************************************************************
176 * @ xhtab_xp  : extended pointer on hash table.
177 * @ return extended pointer on item if success / XPTR_NULL if not found.
178 *****************************************************************************************/
179xptr_t xhtab_get_next( xptr_t xhtab_xp );
180
[204]181/******************************************************************************************
182 * This function displays the full content of an xhtab.
183 ******************************************************************************************
184 * @ xhtab_xp  : extended pointer on hash table.
185 *****************************************************************************************/
186void xhtab_display( xptr_t  xhtab_xp );
[188]187
[1]188#endif  /* _XHTAB_H_ */
Note: See TracBrowser for help on using the repository browser.