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

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

First import
File size: 6.7 KB
RevLine 
[1]1/*
2 * htab.h - Generic embedded hash table definition.
3 *
4 * Author     Ghassan Almalles (2008,2009,2010,2011,2012)
5 *            Mohamed Lamine Karaoui (2015)
6 *            Alain Greiner (2016)
7 *
8 * Copyright (c) UPMC Sorbonne Universites
9 *
10 * This file is part of ALMOS-MKH.
11 *
12 * ALMOS-MKH is free software; you can redistribute it and/or modify it
13 * under the terms of the GNU General Public License as published by
14 * the Free Software Foundation; version 2.0 of the License.
15 *
16 * ALMOS-MKH is distributed in the hope that it will be useful, but
17 * WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
19 * General Public License for more details.
20 *
21 * You should have received a copy of the GNU General Public License
22 * along with ALMOS-MKH; if not, write to the Free Software Foundation,
23 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
24 */
25
26
27#ifndef _HTAB_H_
28#define _HTAB_H_
29
30#include <hal_types.h>
31#include <list.h>
32
33/****************************************************************************************
34 * This file define a generic, embedded, hash table.
35 * The main goal is to provide fast retrieval for a large number of items of same type
36 * in a given cluster. For this purpose the set of all registered items is split
37 * in several subsets. Each subset is organised as a double linked lists.
38 * - an item is uniquely identified by a <key>, that can be a single uint32_t,
39 *   a character string, or a more complex structure.
40 * - From the pointer on the <key>, the hash table uses an user defined ht_hash()
41 *   function, to compute an <index> value, defining a subset of registered
42 *   items, to restrict the associative search.
43 * - As several items can have the same <index>, the hash table uses the user defined
44 *   ht_compare() function for a final associative search on the subset.
45 * - Each registered item is a structure, that must contain an embedded ht_node_t,
46 *   This ht_node_t is part of a rooted double linked list, and contains the <index>.
47 * - Finally, the hash table returns a pointer on the embedded ht_node_t, and the
48 *   pointer on the searched item can be obtained by a simple offset.
49 ***************************************************************************************/
50
51/****************************************************************************************
52 * This define the generic, user defined, function types.
53 ***************************************************************************************/
54
55struct ht_node_s;
56
57typedef bool_t     ht_compare_t( struct ht_node_s * node , void * key );
58typedef uint32_t   ht_hash_t( void * key );
59
60/****************************************************************************************
61 * This structure defines the hash table header.
62 ***************************************************************************************/
63
64typedef struct ht_header_s
65{
66        uint32_t        nb_buckets;   /*! number of subsets (one linked list per subset)   */
67        ht_hash_t     * hash;         /*! user defined hash function                       */ 
68        ht_compare_t  * compare;      /*! user defined compare function                    */
69        list_entry_t  * buckets;      /*! array of root of partial lists of ht_node_t      */
70}
71ht_header_t;
72
73/****************************************************************************************
74 * This structure defines one hash table node.
75 ***************************************************************************************/
76
77typedef struct ht_node_s
78{
79        uint32_t     index;           /*! integer value computed from the key              */
80        list_entry_t list;                /*! member of list of all nodes in same bucket       */
81}
82ht_node_t;
83
84/****************************************************************************************
85 * This function initialises one hash table node.
86 ****************************************************************************************
87ccccc
88 ***************************************************************************************/
89void ht_node_init( ht_node_t * node );
90
91/****************************************************************************************
92 * This function allocates memory for the buckets array, and initializes the header.
93 * The number of buckets (number of subsets) is PAGE_SIZE / sizeof(list_entry_t)
94 ****************************************************************************************
95 * @ header     : pointer on the hash table header.
96 * @ ht_hash    : pointer on the user defined hash function.
97 * @ ht_compare : pointer on the user defined compare function.
98 * @ return 0 if success / return ENOMEM if error.
99 ***************************************************************************************/
100error_t ht_header_init( ht_header_t  * header,
101                        ht_hash_t    * ht_hash,
102                        ht_compare_t * ht_compare );
103
104/****************************************************************************************
105 * This function register a new node in the hash table.
106 ****************************************************************************************
107 * @ header     : pointer on the hash table header.
108 * @ node       : pointer on the node to be registered (embedded in item).
109 * @ key        : pointer on the item identifier.
110 * @ return 0 if success / return EINVAL if node already registered...
111 ***************************************************************************************/
112error_t ht_insert( ht_header_t * header,
113                   ht_node_t   * node,
114                   void        * key );
115
116/****************************************************************************************
117 * This function returns a pointer on the node embedded in the item
118 * identified by its key.
119 ****************************************************************************************
120 * @ header     : pointer on the hash table header.
121 * @ key        : pointer on the item identifier.
122 * @ return pointer on node if found / return NULL if not found.
123 ***************************************************************************************/
124ht_node_t * ht_find( ht_header_t * header,
125                     void        * key);
126
127/****************************************************************************************
128 * This function remove an item from the hash table.
129 ****************************************************************************************
130 * @ header     : pointer on the hash table header.
131 * @ key        : pointer on the item identifier.
132 * @ return 0 if success / return EINVAL if not found.
133 ***************************************************************************************/
134error_t ht_remove( ht_header_t * header,
135                   void        * key );
136
137#endif /* _HTABLE_H_ */
Note: See TracBrowser for help on using the repository browser.