Changeset 23 for trunk/kernel/libk/htab.c
- Timestamp:
- Jun 18, 2017, 10:06:41 PM (7 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/kernel/libk/htab.c
r1 r23 2 2 * htable.c - Generic, embedded hash table implementation. 3 3 * 4 * Author Ghassan Almalles (2008,2009,2010,2011,2012) 5 * Mohamed Lamine Karaoui (2015) 6 * Alain Greiner (2016) 4 * Author Alain Greiner (2016,2017) 7 5 * 8 6 * Copyright (c) UPMC Sorbonne Universites … … 10 8 * This file is part of ALMOS-MKH. 11 9 * 12 * ALMOS-MKH .is free software; you can redistribute it and/or modify it10 * ALMOS-MKH is free software; you can redistribute it and/or modify it 13 11 * under the terms of the GNU General Public License as published by 14 12 * the Free Software Foundation; version 2.0 of the License. 15 13 * 16 * ALMOS-MKH .is distributed in the hope that it will be useful, but14 * ALMOS-MKH is distributed in the hope that it will be useful, but 17 15 * WITHOUT ANY WARRANTY; without even the implied warranty of 18 16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU … … 20 18 * 21 19 * 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,20 * along with ALMOS-MKH; if not, write to the Free Software Foundation, 23 21 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 24 22 */ 25 23 26 #include <htable.h> 27 #include <kmem.h> 28 #include <ppm.h> 29 30 /////////////////////////////////////////////// 31 error_t ht_header_init( ht_header_t * header, 32 ht_hash_t * hash, 33 ht_compare_t * compare ) 24 #include <kernel_config.h> 25 #include <hal_types.h> 26 #include <hal_special.h> 27 #include <htab.h> 28 #include <rwlock.h> 29 #include <list.h> 30 #include <printk.h> 31 #include <vfs.h> 32 33 /////////////////////////////////////////////////////////////////////////////////////////// 34 // Item type specific (static) functions (two functions for each item type). 35 // Example below if for <vhs_inode_t>, where the identifier is the inum field. 36 /////////////////////////////////////////////////////////////////////////////////////////// 37 38 /////////////////////////////////////////////////////////////////////////////////////////// 39 // These static functions compute the hash index from the key. 40 /////////////////////////////////////////////////////////////////////////////////////////// 41 // @ key : local pointer on key. 42 // @ return the index value, from 0 to (HASHTAB_SIZE - 1) 43 /////////////////////////////////////////////////////////////////////////////////////////// 44 45 static uint32_t htab_inode_index( void * key ) 46 { 47 uint32_t * inum = key; 48 return (((*inum) >> 16) ^ ((*inum) & 0xFFFF)) % HASHTAB_SIZE; 49 } 50 51 /////////////////////////////////////////////////////////////////////////////////////// 52 // These static functions are used by htab_lookup(), htab_insert(), and htab_remove(). 53 // They scan one sub-list identified by <index> to find an item identified by <key>. 54 // The sub-list is not modified, but the lock must have been taken by the caller. 55 /////////////////////////////////////////////////////////////////////////////////////// 56 // @ htab : pointer on hash table. 57 // @ index : index of sub-list to be scanned. 58 // @ key : pointer on item identifier. 59 // @ return pointer on item if found / return NULL if not found. 60 /////////////////////////////////////////////////////////////////////////////////////// 61 62 static void * htab_inode_scan( htab_t * htab, 63 uint32_t index, 64 void * key ) 65 { 66 list_entry_t * list_entry; // pointer on list_entry_t (iterator) 67 vfs_inode_t * inode; // pointer on item 68 69 LIST_FOREACH( &htab->roots[index] , list_entry ) 70 { 71 inode = (vfs_inode_t *)LIST_ELEMENT( list_entry , vfs_inode_t , list ); 72 if( inode->inum == *(uint32_t *)key ) return inode; 73 } 74 75 // no matching item found 76 return NULL; 77 } 78 79 //////////////////////////////////////////////////////////////////////////////////////// 80 // Generic access functions 81 //////////////////////////////////////////////////////////////////////////////////////// 82 83 //////////////////////////////////////// 84 void htab_init( htab_t * htab, 85 htab_item_type_t type ) 34 86 { 35 87 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 //////////////////////////////////////// 60 error_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 ///////////////////////////////////////////////// 69 static 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 ////////////////////////////////////////// 92 ht_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 //////////////////////////////////////// 101 error_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 //////////////////////////////////////// 121 error_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 88 89 // initialize readlock 90 rwlock_init( &htab->lock ); 91 92 htab->items = 0; 93 94 if( type == HTAB_INODE_TYPE ) 95 { 96 htab->scan = &htab_inode_scan; 97 htab->index = &htab_inode_index; 98 } 99 else 100 { 101 printk("\n[PANIC] in %s : undefined item type\n", __FUNCTION__ ); 102 hal_core_sleep(); 103 } 104 105 // initialize partial lists 106 for( i = 0 ; i < HASHTAB_SIZE ; i++ ) 107 { 108 list_root_init( &htab->roots[i] ); 109 } 110 } 111 112 ///////////////////////////////////////// 113 error_t htab_insert( htab_t * htab, 114 void * key, 115 list_entry_t * list_entry ) 116 { 117 // compute index from key 118 uint32_t index = htab->index( key ); 119 120 // take the lock in write mode 121 rwlock_wr_lock( &htab->lock ); 122 123 // scan sub-list to check if item exist 124 void * item = htab->scan( htab , index , key ); 125 126 if( item != NULL ) // item exist => return error 127 { 128 // release lock 129 rwlock_wr_unlock( &htab->lock ); 130 131 return -1; 132 } 133 else // item doesn't exist => register 134 { 135 // register item in hash table 136 list_add_last( &htab->roots[index] , list_entry ); 137 138 // update items number 139 htab->items++; 140 141 // release lock 142 rwlock_wr_unlock( &htab->lock ); 143 144 return 0; 145 } 146 } 147 148 ///////////////////////////////////////// 149 error_t htab_remove( htab_t * htab, 150 void * key, 151 list_entry_t * list_entry ) 152 { 153 // compute index from key 154 uint32_t index = htab->index( key ); 155 156 // take the lock in write mode 157 rwlock_wr_lock( &htab->lock ); 158 159 // scan sub-list to chek if item exist 160 void * item = htab->scan( htab , index , key ); 161 162 if( item == NULL ) // item doesn't exist 163 { 164 // release lock 165 rwlock_wr_unlock( &htab->lock ); 166 167 return -1; 168 } 169 else // item exist => remove it 170 { 171 // remove item from hash table 172 list_unlink( list_entry ); 173 174 // update items number 175 htab->items--; 176 177 // release lock 178 rwlock_wr_unlock( &htab->lock ); 179 180 return 0; 181 } 182 } 183 184 ////////////////////////////////// 185 void * htab_lookup( htab_t * htab, 186 void * key ) 187 { 188 // compute index from key 189 uint32_t index = htab->index( key ); 190 191 // take the lock in read mode 192 rwlock_rd_lock( &htab->lock ); 193 194 // scan sub-list 195 void * item = htab->scan( htab , index , key ); 196 197 // release lock 198 rwlock_rd_unlock( &htab->lock ); 199 200 return item; 201 } 202 203 204
Note: See TracChangeset
for help on using the changeset viewer.