source: trunk/kernel/libk/grdxt.h @ 442

Last change on this file since 442 was 406, checked in by alain, 7 years ago

This version executed successfully the user "init" process on a mono-processor TSAR architecture.
File size: 6.7 KB
RevLine 
[1]1/*
2 * grdxt.h - Three-levels Generic Radix-tree interface
3 *
4 * Authors  Alain Greiner (2016)
5 *
6 * Copyright  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#ifndef _GRDXT_H_
25#define _GRDXT_H_
26
27#include <hal_types.h>
28
29/*******************************************************************************************
30 * This structure defines a three levels radix-tree descriptor.
31 * The key is split in three fields : ix1 (MSB) / ix2 / ix3 (LSB) to index the first,
32 * second and third level arrays respectively.
33 * The pointers on the registered items are stored in the third level arrays.
34 * The number or bits for each field are parameters for the grdxt_init() function.
35 * Memory for the first level array is allocated by the grdxt_init() function.
36 * Memory for the second and third levels arrays is dynamically allocated by the
37 * grdxt_insert() function and is only released by grdxt_destroy().
[406]38 * It is used by the MAPPER to implement the file cache: key is the page index in file.
[1]39 ******************************************************************************************/
40
41typedef struct grdxt_s
42{
43        void          ** root;           /*! pointer on first level array of pointers         */
44        uint32_t         ix1_width;      /*! number of bits for first level array index       */
45        uint32_t         ix2_width;      /*! number of bits for second level array index      */
46    uint32_t         ix3_width;      /*! number of bits for third level array index       */
47}
48grdxt_t;
49
50/*******************************************************************************************
51 * This function initialises the radix-tree descriptor,
52 * and allocates memory for the first level array of pointers.
53 *******************************************************************************************
54 * @ rt        : pointer on the radix-tree descriptor.
55 * @ ix1_width : number of bits in ix1 field
56 * @ ix2_width : number of bits in ix2 field
57 * @ ix3_width : number of bits in ix3 field
58 * @ returns 0 if success / returns ENOMEM if no more memory.     
59 ******************************************************************************************/
60error_t grdxt_init( grdxt_t  * rt,
61                    uint32_t   ix1_width,
62                    uint32_t   ix2_width,
63                    uint32_t   ix3_width );
64
65/*******************************************************************************************
66 * This function releases all memory allocated to the radix-tree infrastructure.
67 * The radix-tree is supposed to be empty, but this is NOT checked by this function.
68 *******************************************************************************************
69 * @ rt      : pointer on the radix-tree descriptor.
70 ******************************************************************************************/
71void grdxt_destroy( grdxt_t * rt );
72
73/*******************************************************************************************
74 * This function insert a new item in the radix-tree.
75 * It dynamically allocates memory for new second and third level arrays if required.
76 *******************************************************************************************
77 * @ rt      : pointer on the radix-tree descriptor.
78 * @ key     : key value.
79 * @ value   : pointer on item to be registered in radix-tree.
80 * @ returns 0 if success / returns ENOMEM if no memory, or EINVAL if illegal key.
81 ******************************************************************************************/
82error_t grdxt_insert( grdxt_t  * rt,
83                      uint32_t   key,
84                      void     * value );
85
86/*******************************************************************************************
87 * This function removes an item identified by its key, and returns a pointer
88 * on the removed item. No memory is released.
89 *******************************************************************************************
90 * @ rt      : pointer on the radix-tree descriptor.
91 * @ key     : key value.
92 * @ returns pointer on removed item if success / returns NULL if failure.
93 ******************************************************************************************/
94void * grdxt_remove( grdxt_t  * rt,
95                     uint32_t   key );
96
97/*******************************************************************************************
98 * This function returns the pointer on the item identified by its key.
99 *******************************************************************************************
100 * @ rt      : pointer on the radix-tree descriptor.
101 * @ key     : key value.
102 * @ returns pointer on found item if success / returns NULL if failure.
103 ******************************************************************************************/
104void * grdxt_lookup( grdxt_t  * rt, 
105                     uint32_t   key );
106
107/*******************************************************************************************
108 * This function scan all radix-tree entries in increasing key order, starting from
109 * the value defined by the <key> argument, and return a pointer on the first valid
110 * registered item, and the found item key value.
111 *******************************************************************************************
112 * @ rt         : pointer on the radix-tree descriptor.
113 * @ start_key  : key starting value for the scan.
114 * @ found_key  : [out] buffer for found key value.
115 * return pointer on first valid item if found / return NULL if not found.
116 ******************************************************************************************/
117void * grdxt_get_first( grdxt_t  * rt,
118                        uint32_t   start_key,
119                        uint32_t * found_key );
120
121/*******************************************************************************************
[406]122 * This function displays the current content of a radix_tree.
[1]123 *******************************************************************************************
124 * @ rt      : pointer on the radix-tree descriptor.
[406]125 * @ string  : radix tree identifier.
[1]126 ******************************************************************************************/
127void grdxt_print( grdxt_t * rt,
[406]128                  char    * string );
[1]129
130
131#endif  /* _GRDXT_H_ */
132
Note: See TracBrowser for help on using the repository browser.