source: trunk/kernel/libk/htab.c @ 8

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

First import

File size: 3.2 KB
Line 
1/*
2 * htable.c - Generic, embedded hash table implementation.
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#include <htable.h>
27#include <kmem.h>
28#include <ppm.h>
29
30///////////////////////////////////////////////
31error_t ht_header_init( ht_header_t  * header,
32                        ht_hash_t    * hash,
33                        ht_compare_t * compare )
34{
35        uint32_t     i;
36        kmem_req_t   req;
37        page_t     * page;
38
39        req.type  = KMEM_PAGE;
40        req.size  = 0;
41        req.flags = AF_ZERO;
42        page      = kmem_alloc( &req );
43       
44        if( page == NULL ) return ENOMEM;
45
46        header->nb_buckets = CONFIG_PPM_PAGE_SIZE/sizeof( list_entry_t );
47        header->buckets    = ppm_page2base( page );
48        header->hash       = hash;
49        header->compare    = compare;
50
51        for( i=0 ; i < header->nb_buckets ; i++ )
52        {
53                list_root_init( &header->buckets[i] );
54        }
55
56        return 0;
57}
58
59////////////////////////////////////////
60error_t ht_node_init( ht_node_t * node )
61{
62        node->index = (uint32_t) -1;
63        list_entry_init( &node->list );
64
65        return 0;
66}
67
68/////////////////////////////////////////////////
69static ht_node_t * __hfind( ht_header_t * header,
70                            uint32_t      index,
71                            void        * key)
72{
73        ht_node_t    * node;
74        list_entry_t * root,
75    list_entry_t * iter;
76
77        root = &header->buckets[index % header->nb_buckets];
78
79        LIST_FOREACH( root , iter )
80        {
81                node = LIST_ELEMENT( iter , ht_node_t , list );
82                if( node->index == index )
83                {
84                        if( header->compare( node , key ) ) return node;
85                }
86        }
87
88        return NULL;
89}
90
91//////////////////////////////////////////
92ht_node_t * ht_find( ht_header_t * header,
93                     void        * key )
94{
95        uint32_t index = header->hash( key );
96
97        return __ht_find( header , index , key );
98}
99
100////////////////////////////////////////
101error_t ht_insert( ht_header_t * header,
102                   ht_node_t   * node,
103                   void        * key )
104{
105        uint32_t index = header->hash( key );
106
107        ht_node_t * node = __ht_find( header , index , key );
108
109        if( node != NULL ) return EINVAL;
110
111        list_entry_t * root = &header->buckets[index % header->nb_buckets];
112
113        list_add_first( root , &node->list);
114
115        node->index = index;
116
117        return 0;
118}
119
120////////////////////////////////////////
121error_t ht_remove( ht_header_t * header,
122                   void        * key )
123{
124        uint32_t index = header->hash( key );
125
126        ht_node_t * node = __ht_find( header , index , key );
127
128        if( node == NULL ) return EINVAL;
129
130        list_unlink( &node->list );
131
132        return 0;
133}
134
Note: See TracBrowser for help on using the repository browser.