source: trunk/kernel/libk/htab.h @ 609

Last change on this file since 609 was 563, checked in by alain, 6 years ago

Complete restructuration of kernel spinlocks.

File size: 6.2 KB
Line 
1/*
2 * htab.h - Generic embedded hash table definition.
3 *
4 * Authors  Alain Greiner (2016,2017,2018)
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
25#ifndef _HTAB_H_
26#define _HTAB_H_
27
28#include <hal_kernel_types.h>
29#include <rwlock.h>
30#include <list.h>
31
32/////////////////////////////////////////////////////////////////////////////////////////
33// This file define a generic, embedded, hash table.
34//
35// It can only be accessed by threads running in the local cluster.
36// It is generic as it can be used to register various types of items.
37// The main goal is to provide fast retrieval for a large number of items of same type.
38// For this purpose the set of all registered items is split in several subsets.
39// Each subset is organised as a double linked lists.
40// - an item is uniquely identified by a <key>, that can be a single uint32_t,
41//   a character string, or a more complex structure.
42// - From the pointer on <key>, we use an item type specific htab_index() function,
43//   to compute an <index> value, defining a subset of registered items.
44// - As several items can have the same <index>, we use the item type specific
45//   htab_scan() function for a final associative search on the subset.
46// - Each registered item is a structure, that must contain an embedded list_entry_t,
47//   that is part of a rooted double linked list.
48//
49// Implementation Note: for each supported item type ***, you must define the two
50//                      htab_***_index() and htab_***_scan() functions, and
51//                      update the htab_init() function.
52/////////////////////////////////////////////////////////////////////////////////////////
53
54#define HASHTAB_SIZE    64   // number of subsets
55
56/****************************************************************************************
57 * These typedef define the two item type specific function prototypes.
58 ***************************************************************************************/
59
60struct htab_s;
61
62typedef void *     htab_scan_t( struct htab_s * htab , uint32_t index , void * key );
63
64typedef uint32_t   htab_index_t( void * key );
65
66/****************************************************************************************
67 * This define the supported item types.
68 ***************************************************************************************/
69
70typedef enum
71{
72    HTAB_INODE_TYPE = 1,                     /*! item is a vfs_inode_t                 */
73}
74htab_item_type_t;
75
76/****************************************************************************************
77 * This structure defines the the root of a local hash table.
78 ***************************************************************************************/
79
80typedef struct htab_s
81{
82        list_entry_t      roots[HASHTAB_SIZE];  /*! array of roots of partial lists        */
83        htab_index_t    * index;                /*! item type  specific function           */
84        htab_scan_t     * scan;                 /*! item type specific function            */
85    uint32_t          items;                /*! number of registered items             */
86    busylock_t        lock;                 /*! lock protecting hash table accesses    */
87}
88htab_t;
89
90/****************************************************************************************
91 * This function initialises an empty hash table (zero registered item).
92 ****************************************************************************************
93 * @ htab       : pointer on hash table.
94 * @ type       : item type.
95 ***************************************************************************************/
96void htab_init( htab_t           * htab,
97                htab_item_type_t   type );
98
99/****************************************************************************************
100 * This function register a new item in the hash table.
101 ****************************************************************************************
102 * @ htab       : pointer on the hash table.
103 * @ key        : pointer on the item identifier.
104 * @ list_entry : pointer on list_entry_t embedded in item to be registered.
105 * @ return 0 if success / return EINVAL if item already registered.
106 ***************************************************************************************/
107error_t htab_insert( htab_t       * htab,
108                     void         * key,
109                     list_entry_t * list_entry );
110
111/****************************************************************************************
112 * This function remove an item from the hash table.
113 ****************************************************************************************
114 * @ header     : pointer on the hash table.
115 * @ key        : pointer on the item identifier.
116 * @ list_entry : pointer on list_entry_t embedded in item to be removed.
117 * @ return 0 if success / return EINVAL if item not found.
118 ***************************************************************************************/
119error_t htab_remove( htab_t       * htab,
120                     void         * key,
121                     list_entry_t * list_entry );
122
123/****************************************************************************************
124 * This function returns a pointer on the node embedded in the item
125 * identified by its key.
126 ****************************************************************************************
127 * @ htab      : pointer on the hash table.
128 * @ key       : pointer on the item identifier.
129 * @ return pointer on item if found / return NULL if not found.
130 ***************************************************************************************/
131void * htab_lookup( htab_t * htab,
132                    void   * key);
133
134
135#endif /* _HTAB_H_ */
Note: See TracBrowser for help on using the repository browser.