source: trunk/kernel/kern/keysdb.h @ 1

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

First import
File size: 6.2 KB
Line 
1/*
2 * keysdb.h - Two Levels Radix-tree Interface
3 *
4 * Authors Ghassan Almalless (2008,2009,2010,2011,2012)
5 *         Alain Greiner (2016)
6 *
7 * Copyright  UPMC Sorbonne Universites
8 *
9 * This file is part of ALMOS-kernel.
10 *
11 * ALMOS-kernel is free software; you can redistribute it and/or modify it
12 * under the terms of the GNU General Public License as published by
13 * the Free Software Foundation; version 2.0 of the License.
14 *
15 * ALMOS-kernel is distributed in the hope that it will be useful, but
16 * WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18 * General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with ALMOS-kernel; if not, write to the Free Software Foundation,
22 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
23 */
24
25#ifndef _KEYS_DB_H_
26#define _KEYS_DB_H_
27
28#include <types.h>
29#include <kmem.h>
30
31#define KEYS_PER_REC        64
32
33/*******************************************************************************************
34 * This define the second level in the two level radix-tree, called a record.
35 * A record is an array of KEYS_PER_RECORD pointers.
36 * Each entry is a (void *) pointer on a key-addressable item.
37 * The memory is dynamically allocated for a record only if this record contains
38 * a least one non NULL entry.
39 ******************************************************************************************/
40
41typedef struct keys_record_s
42{
43        void * tbl[KEYS_PER_REC];
44}
45keys_record_t;
46
47/*******************************************************************************************
48 * This structure defines the two levels radix-tree descriptor.
49 * The key is split in two fields : a record_index (MSB) / a key_index (LSB)
50 * The first level in the two levels radix-tree is an array of pointers on records.
51 * The number of entries in this array is fixed as [sizeof(page) / sizeof(pointer)].
52 * The total number of key values is [sizeof(page) / sizeof(pointer)] * KEYS_PER_RECORD.
53 ******************************************************************************************/
54
55typedef struct keysdb_s
56{
57        keys_record_t ** root;           /*! pointer on array of records pointers             */
58        uint32_t         records_nr;     /*! number of entries in records array               */
59        uint32_t         records_bits;   /*! number of bits to code the record index          */
60    uint32_t         keys_nr;        /*! number of entries (keys) in a record             */
61        uint32_t         keys_bits;      /*! number of bits to code the key index             */
62        page_t         * page;           /*! page descriptor containing the records array     */
63}
64keysdb_t;
65
66
67/*******************************************************************************************
68 * This function initialises the two levels radix-tree descriptor, and allocates
69 * memory (one physical page) to store the records array.
70 * @ db      : pointer on the radix-tree descriptor.
71 * @ returns 0 if success / returns ENOMEM if no more memory.     
72 ******************************************************************************************/
73error_t keysdb_init( keysdb_t * db );
74
75/*******************************************************************************************
76 * This function releases all memory allocated to store the array of records pointers,
77 * and the records themselve.
78 * @ db      : pointer on the radix-tree descriptor.
79 ******************************************************************************************/
80void keysdb_destroy( keysdb_t * db );
81
82/*******************************************************************************************
83 * This function insert a new item in the two level radix-tree.
84 * It dynamically allocates memory for a new record if required.
85 * @ db      : pointer on the radix-tree descriptor.
86 * @ key     : key value used to address the radix tree
87 * @ value   : pointer on item to be registered in radix-tree.
88 * @ returns 0 if success / returns EINVAL if illegal key value.
89 ******************************************************************************************/
90error_t keysdb_insert( keysdb_t * db,
91                       uint32_t   key,
92                       void     * value );
93
94/*******************************************************************************************
95 * This function removes an item identified by its key, and returns a pointer
96 * on the removed item.
97 * @ db      : pointer on the radix-tree descriptor.
98 * @ key     : key value.
99 * @ returns item pointer if success / returns NULL if failure.
100 ******************************************************************************************/
101void * keysdb_remove( keysdb_t * db,
102                      uint32_t   key );
103
104/*******************************************************************************************
105 * This function returns the pointer on the item identified by its key.
106 * @ db      : pointer on the radix-tree descriptor.
107 * @ key     : key value.
108 * @ returns item pointer if success / returns NULL if failure.
109 ******************************************************************************************/
110void * keysdb_lookup( keysdb_t * db, 
111                      uint32_t   key );
112
113/*******************************************************************************************
114 * This function displays the content of a two levels radix_tree.
115 * @ db      : pointer on the radix-tree descriptor.
116 * @ name    : string identifying the radix-tree.
117 ******************************************************************************************/
118void keysdb_print( keysdb_t * db,
119                   char     * name );
120
121
122/* TODO the two following functions deprecated [AG] */
123
124/*******************************************************************************************
125 ******************************************************************************************/
126error_t keysdb_bind( keysdb_t *db, uint32_t key_start, uint32_t keys_nr, void *value);
127
128/*******************************************************************************************
129 ******************************************************************************************/
130error_t keysdb_unbind( keysdb_t *db, uint32_t key_start, uint32_t keys_nr);
131
132#endif  /* _KEYS_DB_H_ */
133
Note: See TracBrowser for help on using the repository browser.