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

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

Introduce syscalls.
File size: 6.2 KB
RevLine 
[1]1/*
2 * htab.h - Generic embedded hash table definition.
3 *
[23]4 * Authors  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
25#ifndef _HTAB_H_
26#define _HTAB_H_
27
28#include <hal_types.h>
[23]29#include <rwlock.h>
[1]30#include <list.h>
31
[23]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 defined
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/////////////////////////////////////////////////////////////////////////////////////////
[1]53
[23]54#define HASHTAB_SIZE    64   // number of subsets
55
[1]56/****************************************************************************************
[23]57 * These typedef define the two item type specific function prototypes.
[1]58 ***************************************************************************************/
59
[23]60struct htab_s;
[1]61
[23]62typedef void *     htab_scan_t( struct htab_s * htab , uint32_t index , void * key );
[1]63
[23]64typedef uint32_t   htab_index_t( void * key );
65
[1]66/****************************************************************************************
[23]67 * This define the supported item types.
[1]68 ***************************************************************************************/
69
[23]70typedef enum
[1]71{
[23]72    HTAB_INODE_TYPE = 1,                     /*! item is a vfs_inode_t                 */
[1]73}
[23]74htab_item_type_t;
[1]75
76/****************************************************************************************
[23]77 * This structure defines the the root of a local hash table.
[1]78 ***************************************************************************************/
79
[23]80typedef struct htab_s
[1]81{
[23]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    rwlock_t          lock;                 /*! lock protecting hash table accesses    */
[1]87}
[23]88htab_t;
[1]89
90/****************************************************************************************
[23]91 * This function initialises an empty hash table (zero registered item).
[1]92 ****************************************************************************************
[23]93 * @ htab       : pointer on hash table.
94 * @ type       : item type.
[1]95 ***************************************************************************************/
[23]96void htab_init( htab_t           * htab,
97                htab_item_type_t   type );
[1]98
99/****************************************************************************************
[23]100 * This function register a new item in the hash table.
[1]101 ****************************************************************************************
[23]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.
[1]106 ***************************************************************************************/
[23]107error_t htab_insert( htab_t       * htab,
108                     void         * key,
109                     list_entry_t * list_entry );
[1]110
111/****************************************************************************************
[23]112 * This function remove an item from the hash table.
[1]113 ****************************************************************************************
[23]114 * @ header     : pointer on the hash table.
[1]115 * @ key        : pointer on the item identifier.
[23]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.
[1]118 ***************************************************************************************/
[23]119error_t htab_remove( htab_t       * htab,
120                     void         * key,
121                     list_entry_t * list_entry );
[1]122
123/****************************************************************************************
124 * This function returns a pointer on the node embedded in the item
125 * identified by its key.
126 ****************************************************************************************
[23]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.
[1]130 ***************************************************************************************/
[23]131void * htab_lookup( htab_t * htab,
132                    void   * key);
[1]133
134
[23]135#endif /* _HTAB_H_ */
Note: See TracBrowser for help on using the repository browser.